source: to-imperative/trunk/runtime/rf_expr.ih @ 1140

//-----------------------------------------------------------------------------
/// @file rf_expr.ih
///
/// Refal+ expression inline method implementation
//
//  $Source$
//  $Revision: 1140 $
//  $Date: 2003-08-10 21:42:33 +0000 (Sun, 10 Aug 2003) $
//-----------------------------------------------------------------------------

#ifndef __rf_expr_ih__
#define __rf_expr_ih__

#include "rf_expr.hh"
#include "rf_term.ih"
#include "rf_object_ref.ih"
#include "rf_integer.ih"
#include "rf_short_int.ih"
#include "pxx_heap_allocator.ih"
#include "pxx_common.ih"

#include <wchar.h>
#include <wctype.h>

namespace rfrt
{

using namespace rftype ;

inline Expr::Expr (
  Term* const _first, Term* const _last,
  MemoryChunk* const _mem_chunk, uintptr_t const _flags
) :
  first (_first),
  last (_last),
  mem_chunk (_mem_chunk),
  flags (_flags)
{
  //
  // Increment a reference counter to memory block containing an expression
  mem_chunk->inc_ref_count();
  D(printf("+ %p(%p,%p,%p) by generic constructor",
           this, first, last, mem_chunk);)
}

inline Expr::Expr (Expr const* _expr) :
  first (_expr->first),
  last (_expr->last),
  mem_chunk (_expr->mem_chunk),
  flags (_expr->flags)
{
  //
  // This is a special kind of copy constructor used to get arguments and
  // results from stack. Do not increment a reference counter to memory block!
//    inc_ref_count();
  D(printf("+ %p(%p,%p,%p) from *%p\n",
           this, first, last, mem_chunk, _expr);)
}

inline Expr::Expr (size_t _len, int _align)
{
  //
  // Initialize an expression with requested length
  init(_len, _align);
  D(printf("+ %p(%p,%p,%p) of size %d\n", this, first, last, mem_chunk, _len);)
}

inline Expr::Expr (Object* _obj)
{
  init(1, 0);
  new(first) ObjectRef(_obj);
}

#if 0
inline Expr::Expr (char const* _string /* = null */)
{
  //
  // Initialize an expression with necessary length
  init(_string != null ? strlen(_string) : 0, 0);
  //
  // In a loop...
  for (Term* p = first; p < last; p++, _string++) {
    //
    // ...create a symbol in place
    new(p) Term(*_string);
  }
  //
  // Mark expression as flat
  flags = FLAT_BIT;
  D(printf("+ %p(%p,%p,%p) from %s\n", this, first, last, mem_chunk, _string);)
}
#endif

inline Expr::Expr ()
{
  init(0, 0);
}

inline Expr::Expr (Term const* _cp)
{
  //
  // If we really have a reference term...
  if (_cp->is_ref()) {
    //
    // ...get a first term of referenced expression...
    first = _cp->get_first();
    //
    // ...and its right margin
    last = _cp->get_last();
    //
    // Obtain a pointer to a memory block containing an expression
    mem_chunk = _cp->get_mem_chunk();
    //
    // Increment reference counter to this memory block
    mem_chunk->inc_ref_count();
    //
    // Check whether reference expression is flat and set a flag appropriately
    flags = _cp->data1 & FLAT_BIT;
    D(printf("+ %p(%p,%p,%p) from %p()\n", this, first, last, mem_chunk, _cp);)
  }
  //
  // Oh, no, we have a symbol...
  else {
    //
    // ...and this is the error
    FATAL("Attempt to dereference a symbol" );
  }
}

inline Expr::Expr (Expr const& _expr, uintptr_t _index)
{
  new(this) Expr(_expr.first + _index);
}

inline Expr::Expr (Expr const& _expr, uintptr_t _index, uintptr_t _length)
{
  //
  // Call a generic constructor
  new(this) Expr(
    _expr.first + _index, _expr.first + _index + _length,
    _expr.mem_chunk, _expr.flags
  );
}

inline Expr::Expr (Expr const& _expr) :
  first (_expr.first),
  last (_expr.last),
  mem_chunk (_expr.mem_chunk),
  flags (_expr.flags)
{
  //
  // Increment a reference counter to memory block
  mem_chunk->inc_ref_count();
  D(printf("+ %p(%p,%p,%p) by copy from %p\n",
           this, first, last, mem_chunk, &_expr);)
}

inline Expr::~Expr ()
{
  D(printf("- %p(%p,%p,%p)\n", this, first, last, mem_chunk);)
  //
  // Destructor only calls a drop() method
  drop();
}

inline Expr& Expr::operator = (Expr const& _expr)
{
  D(printf("%p(%p,%p,%p) = %p(%p,%p,%p)\n",
           this, first, last, mem_chunk,
           &_expr, _expr.first, _expr.last, _expr.mem_chunk);)
  //
  // If we are not assigning to self
  if( this != &_expr ) {
    //
    // Destroy old expression
    drop();
    //
    // Build a copy in place
    new(this) Expr(_expr);
  }
  //
  // Return reference to self
  return *this;
}

inline Expr Expr::operator () () const
{
//  return Expr(Term(self));
  Expr res(1, 0);
  new(res.first) Term(self);
  res.flags = 0;
  return res;
}

inline Expr Expr::operator * () const
{
  if (last - first == 1) {
    return Expr(first);
  } else {
    FATAL("Expression length not equal to 1");
  }
}

inline bool Expr::symbol_at (uintptr_t _index) const
{
  return (first + _index)->is_sym();
}

inline bool Expr::is_flat () const
{
  return flags & FLAT_BIT;
}

inline bool Expr::is_empty () const
{
  return first == last;
}

inline Term* Expr::get_first () const
{
  return first;
}

inline Term* Expr::get_last () const
{
  return last;
}

inline uintptr_t Expr::get_len () const
{
  return last - first;
}

inline uintptr_t Expr::get_flags () const
{
  return flags;
}

inline void Expr::dump () const
{
  Term* p;
  printf("%p, %p, %"PRIuPTR": ", first, last, last - first);
  for (p = first; p < last; p++) {
    printf("[%08"PRIxPTR" %08"PRIxPTR"]", p->data1, p->uint_data2);
  }
  printf("\n");
}

inline void Expr::drop ()
{
  //
  // Decrement reference counter and destroy an object if it is zero
  if (mem_chunk != null && mem_chunk->dec_ref_count() == 0) {
    //
    // Walk through and decrement reference counters on childs
//    deref_childs();
    deref_childs(first, is_flat() ? last : first, mem_chunk);
    //
    // Deallocate expression holder in memory
    MemoryChunk::destroy_instance(mem_chunk);
    D(printf("-- %p\n", mem_chunk);)
  }
  mem_chunk = null;
}

#if 0
inline void Expr::ref_childs () const
{
  for (Term* p = first; p < last; p++) {
    if (p->is_ref()) p->get_mem_chunk()->inc_ref_count();
  }
}
#endif

inline bool Expr::writeln (FILE* _fp) const
{
  if (!write (_fp)) return false;
  if (fputc('\n', _fp) == EOF) return false;
  return true;
}

inline bool Expr::println (FILE* _fp) const
{
  if (!print (_fp)) return false;
  if (fputc('\n', _fp) == EOF) return false;
  return true;
}

//
// We prefer to have inline functions instead of macros, but changing macros
// below to inline functions gives worse execution times

///
/// Check whether a term pointer is not a right margin of used area in
/// a memory block
#define is_not_right_margin(_p, _last) \
  (((_p) < (_last)) && ((_p)->data1 != SYM_BORDER))

///
/// Check whether a term pointer is not a left margin of used area in
/// a memory block
#define is_not_left_margin(_p, _first) \
  (((_p) >= (_first)) && ((_p)->data1 != SYM_BORDER))

inline bool Expr::rt_alloc (uintptr_t _len) const
{
  //
  // Get a pointer beyond the term area in our memory block
  Term *p = static_cast<Term*>(mem_chunk->get_last());
  //
  // If our expression is the only one referencing a memory block than we can
  // go to the right and destroy all terms there, because they are not a part
  // of any expression
  if (mem_chunk->no_extern_refs()) {
    for (Term* q = last; is_not_right_margin(q, p); q++ ) {
      q->~Term();
    }
    //
    // Set correct right margin of used area in a memory block
    if (last < p) last->data1 = SYM_BORDER;
  } else {
    //
    // If there are other references to our memory block than if last is not
    // a right margin of used area, we cannot allocate some space.
    if (is_not_right_margin(last, p)) return false;
  }
  //
  // Ok, here last is a a right margin of used area. Check whether we have
  // enough space.
  if (last + _len > p) return false;
  //
  // Set right margin if needed.
  if (last + _len < p) (last + _len)->data1 = SYM_BORDER;
  return true;
}

inline bool Expr::lt_alloc (uintptr_t _len) const
{
  Term* p = static_cast<Term*>(mem_chunk->get_first());
  Term* f = first - 1;
  if (mem_chunk->no_extern_refs()) {
    for (Term* q = f; is_not_left_margin(q, p); q--) {
      q->~Term();
    }
    if (f >= p) f->data1 = SYM_BORDER;
  } else {
    if (is_not_left_margin(f, p)) return false;
  }
  --p;
  if (f - _len < p) return false;
  if (f - _len > p) (f - _len)->data1 = SYM_BORDER;
  return true;
}

//
// FIXME: should be a real hash computation
inline uint32_t Expr::hash () const
{
  return 0;
}

inline bool Expr::term_eq (Expr const& _expr, uintptr_t _index) const
{
  return *first == *(_expr.first + _index);
}

inline bool Expr::eq (Expr const& _expr, uintptr_t _index) const
{
  Term *f = _expr.first + _index;
  if (first == f) {
    #if DEBUG
    identical++;
    #endif
    return true;
  }
  return Term::eq(first, f, get_len());
}

inline bool Expr::eq (Expr const& _expr, uintptr_t _index)
{
  Term *f = _expr.first + _index;
  if (first == f) {
    #if DEBUG
    identical++;
    #endif
    return true;
  }
  bool res = Term::eq(first, f, get_len());
  if (res) {
    #if DEBUG
    unifications++;
    #endif
    uintptr_t new_flags = flags | _expr.flags;
    drop();
    new(this) Expr(f, f + get_len(), _expr.mem_chunk, new_flags);
  }
  return res;
}

inline bool Expr::operator == (Expr const& _expr) const
{
  if (get_len() != _expr.get_len()) return false;
  return eq(_expr, 0);
}

inline bool Expr::operator != (Expr const& _expr) const
{
  if (get_len() != _expr.get_len()) return true;
  return !eq(_expr, 0);
}

inline bool Expr::operator == (Expr& _expr)
{
  if (first == _expr.first && last == _expr.last) {
    #if DEBUG
    identical++;
    #endif
    return true;
  } else {
    bool res = Term::eq(first, last, _expr.first, _expr.last);
    if (res) {
      #if DEBUG
      unifications++;
      #endif
      if (mem_chunk->get_ref_count() >= _expr.mem_chunk->get_ref_count()) {
        flags |= _expr.flags;
        _expr = self;
      } else {
        _expr.flags |= flags;
        self = _expr;
      }
    }
    return res;
  }
}

inline bool Expr::operator != (Expr& _expr)
{
  return !(self == _expr);
}

inline int Expr::compare (Expr const& _expr1, Expr const& _expr2)
{
  return Term::compare(_expr1.get_first(), _expr1.get_last(),
                       _expr2.get_first(), _expr2.get_last());
}

inline MemoryChunk* Expr::get_mem_chunk () const
{
  return mem_chunk;
}

inline void Expr::set_mem_chunk (MemoryChunk* _ptr)
{
  mem_chunk = _ptr;
}

//
// explicit specialization for SplitIterator constructor with left splitting
template <>
inline SplitIterator<d_lt>::SplitIterator (
  Expr const& _expr, uintptr_t _min_len
) :
  lt (_expr.get_first(), _expr.get_first() + _min_len,
      _expr.get_mem_chunk(), _expr.get_flags()),
  rt (_expr.get_first() + _min_len, _expr.get_last(),
      _expr.get_mem_chunk(), _expr.get_flags()),
  state (true)
{
//  if (_min_len == 0) lt.flags = FLAT_BIT;
}

//
// explicit specialization for SplitIterator constructor with right splitting
template <>
inline SplitIterator<d_rt>::SplitIterator (
  Expr const& _expr, uintptr_t _min_len
) :
  lt (_expr.get_first(), _expr.get_last() - _min_len,
      _expr.get_mem_chunk(), _expr.get_flags()),
  rt (_expr.get_last() - _min_len, _expr.get_last(),
      _expr.get_mem_chunk(), _expr.get_flags()),
  state (true)
{
//  if (_min_len == 0) lt.flags = FLAT_BIT;
}

template <Direction D>
SplitIterator<D>::~SplitIterator ()
{}

template <Direction D>
inline SplitIterator<D>& SplitIterator<D>::operator ++ ()
{
  if (lt.last < rt.last) {
    //
    // FIXME: correctly we only should clear FLAT_BIT
//    if (lt.last->is_ref()) lt.flags = 0;
    lt.last++;
    rt.first++;
  } else {
    state = false;
  }
  return *this;
}

template <Direction D>
inline SplitIterator<D>& SplitIterator<D>::operator ++ (int)
{
  return operator++();
}

template <Direction D>
inline SplitIterator<D>& SplitIterator<D>::operator -- ()
{
  if (lt.first < rt.first) {
    lt.last--;
    rt.first--;
    //
    // FIXME: correctly we only should clear FLAT_BIT
//    if (rt.first->is_ref()) rt.flags = 0;
  } else {
    state = false;
  }
  return *this;
}

template <Direction D>
inline SplitIterator<D>& SplitIterator<D>::operator -- (int)
{
  return operator--();
}

template <Direction D>
inline SplitIterator<D>::operator bool ()
{
  return state;
}

template <Direction D>
inline Expr const& SplitIterator<D>::get_left () const
{
  return lt;
}

template <Direction D>
inline Expr const& SplitIterator<D>::get_right () const
{
  return rt;
}

#if defined(ALL_INLINE) || defined(INSTANTIATE_INLINE)

INLINE Expr Expr::operator + (Expr const& _expr) const
{
  D(printf("Adding %p to %p\n", &_expr, this);)
  if (last == _expr.first) {
    #if DEBUG
    empty_copy++;
    #endif
    //
    // Call a generic constructor
    return Expr (first, _expr.last, mem_chunk, flags & _expr.flags);
  }
  //
  // Get lentgths of both arguments
  uintptr_t len1 = last - first;
  uintptr_t len2 = _expr.last - _expr.first;
  //
  // If a length of a second argument is zero do nothing and return a copy of
  // a first argument
  if (len2 == 0) {
    #if DEBUG
    empty_copy++;
    #endif
    return *this;
  //
  // If a length of a first argument is zero do nothing and return a copy of
  // a second argument
  } else if (len1 == 0) {
    #if DEBUG
    empty_copy++;
    #endif
    return _expr;
  //
  // Try to get a memory to the right of the first argument that able to
  // contain a second argument
  } else if (rt_alloc(len2)) {
    //
    // On success copy a contents of a second argument
    #if DEBUG
    rt_copy++;
    #endif
    //
    // A legal method of copying expression contents is by perform per-term
    // assignment. But in a case of a flat expression we need not that
    // overhead. So we simply do memcpy() and advance child references only if
    // needed.
    //
    // In a case of not flat expression advance reference counters for child
    // memory blocks
//    if (!_expr.is_flat()) _expr.ref_childs();
    //
    // Initialize expression by a copy of a first argument
    Expr e(*this);
//    memcpy(e.last, _expr.first, len2 * sizeof(Term));
    if (_expr.is_flat())
      memcpy(e.last, _expr.first, len2 * sizeof(Term));
    else {
      Term* to = e.last;
      Term const* from = _expr.first;
      while (from != _expr.last) {
        new(to) Term(*from);
        from++; to++;
      }
    }
    //
    // Adjust flags
    e.flags &= _expr.flags;
    //
    // Adjust expression length
    e.last += len2;
    return e;
  //
  // Try to get a memory to the left of the second argument that able to
  // contain a first argument
  } else if (_expr.lt_alloc(len1)) {
    //
    // On success copy a contents of a first argument. This is almost the
    // same as described above.
    #if DEBUG
    lt_copy++;
    #endif
//    if (!is_flat()) ref_childs();
    Expr e(_expr);
    e.first -= len1;
//    memcpy(e.first, first, len1 * sizeof(Term));
    if (is_flat()) memcpy(e.first, first, len1 * sizeof(Term));
    else {
      Term* to = e.first;
      Term const* from = first;
      while (from != last) {
        new(to) Term(*from);
        from++; to++;
      }
    }
    e.flags &= flags;
    return e;
  //
  // If all optimized copy methods fail, copy both arguments
  } else {
    #if DEBUG
    both_copy++;
    #endif
    //
    // Create a new expression with specified length. Use simple euristic to
    // define appropriate alignment
    Expr e(len1 + len2, len1 >= len2 ? 1 : -1);
    //
    // Child references are incremented separately for two arguments rather
    // then for the resulting expression. This advances our chances to avoid
    // some work in a case if at least one of two expressions is flat.
    if (is_flat()) memcpy(e.first, first, len1 * sizeof(Term));
    else {
      Term* to = e.first;
      Term const* from = first;
      while (from != last) {
        new(to) Term(*from);
        from++; to++;
      }
    }
    if (_expr.is_flat())
      memcpy(e.first + len1, _expr.first, len2 * sizeof(Term));
    else {
      Term* to = e.first + len1;
      Term const* from = _expr.first;
      while (from != _expr.last) {
        new(to) Term(*from);
        from++; to++;
      }
    }
    //
    // Adjust flags
    e.flags = flags & _expr.flags;
//    if (!e.is_flat()) e.ref_childs();
    return e;
  }
}

INLINE void Expr::init (size_t _len, int _align)
{
  D(printf("init is called for %p\n", this);)
  //
  // Create a new memory block via allocator
  mem_chunk = MemoryChunk::create_instance(_len * sizeof(Term));
  //
  // Get pointers to the first and beyond the last terms in allocated block
  Term *start = static_cast<Term*>(mem_chunk->get_first());
  Term *end   = static_cast<Term*>(mem_chunk->get_last());
  //
  // Compute expression margins depending on alignment inside memory block
  if( _align > 0 ) {
    //
    // Left aligned expression
    first = start;
    last  = first + _len;
  } else if( _align < 0 ) {
    //
    // Right aligned expression
    last  = end;
    first = last - _len;
  } else {
    //
    // Center aligned expression
    first = start + (mem_chunk->get_size() / sizeof(Term) - _len) / 2;
    last  = first + _len;
  }
  //
  // Setup border symbols if necessary
  // FIXME: it is possible to slightly optimize this by moving a code below
  // into appropriate parts of conditional operator above (for example, in a
  // case of left aligned expression we never need to setup left border
  // symbol).
  if (first > start) {
    (first - 1)->data1 = SYM_BORDER;
  }
  if (last < end) {
    last->data1 = SYM_BORDER;
  }
  //
  // Expression with zero length is always "flat"
  if (_len == 0) flags = FLAT_BIT;
  else flags = 0;
}

INLINE void Expr::deref_childs (
  Term* _first, Term* _last, MemoryChunk* _mem
)
{
  //
  // First go to the left, and deal with all reference terms there.
  _first--;
  Term* p = _mem->get_first();
  while (is_not_left_margin(_first, p)) {
    _first->~Term();
    _first--;
  }
  //
  // Go to the right, and deal with all reference terms there.
  p = _mem->get_last();
  while (is_not_right_margin(_last, p)) {
    _last->~Term();
    _last++;
  }
}

INLINE void Expr::deref_childs () const
{
  //
  // First go to the left, and deal with all reference terms there.
  Term* r = first - 1;
  Term* p = mem_chunk->get_first();
  while (is_not_left_margin(r, p)) {
    r->~Term();
    r--;
  }
  //
  // If our expression is flat we may skip its body
  r = is_flat() ? last : first;
  //
  // Go to the right, and deal with all reference terms there.
  p = mem_chunk->get_last();
  while (is_not_right_margin(r, p)) {
    r->~Term();
    r++;
  }
}

static INLINE bool is_good_wstr (WString const& _ws)
{
  wchar_t const* p = _ws.get_data();
  wchar_t wc;
  bool first = true;
  if (*p == null) return false;
  while ((wc = *p++) != null) {
    if (!iswalnum(wc) && wc != L'!' && wc != L'?' && wc != L'-') return false;
    if (first && !iswupper(wc)) return false;
    first = false;
  }
  return true;
}

static INLINE bool write_wstr (FILE* _fp, WString const& _ws)
{
  wchar_t const* p = _ws.get_data();
  wchar_t wc;
  char buf[MB_CUR_MAX + 1];
  while ((wc = *p++) != null) {
    switch (wc) {
    case L'\t':
      if (fputs("\\t", _fp) == EOF) return false; break;
    case L'\r':
      if (fputs("\\r", _fp) == EOF) return false; break;
    case L'\n':
      if (fputs("\\n", _fp) == EOF) return false; break;
    case L'\v':
      if (fputs("\\v", _fp) == EOF) return false; break;
    case L'\\':
      if (fputs("\\\\", _fp) == EOF) return false; break;
    case L'\'':
      if (fputs("\\\'", _fp) == EOF) return false; break;
    case L'\"':
      if (fputs("\\\"", _fp) == EOF) return false; break;
    default:
      if (iswprint(wc)) {
        size_t n = wctomb(buf, wc);
        if (n != (size_t)(-1)) {
          buf[n] = 0;
          if (fputs(buf, _fp) == EOF) return false;
        } else {
          if (fprintf(_fp, "\\%04x", wc) == -1) return false;
        }
      } else {
        if (fprintf(_fp, "\\%04x", wc) == -1) return false;
      }
    }
  }
  return true;
}

INLINE bool Expr::write (FILE* _fp) const
{
  bool chars_flag = false;
  for (Term* p = first; p < last; p++) {
    if (p->get_type() == type_char) {
      if (!chars_flag) {
        if (p != first) {
          if (fputc(' ', _fp) == EOF) return false;
        }
        if (fputc('\'', _fp) == EOF) return false;
        chars_flag = true;
      }
      if (!write_wstr(_fp, (WString)(*p))) return false;
    } else {
      if (chars_flag) {
        if (fputc('\'', _fp) == EOF) return false;
        chars_flag = false;
      }
      if (p != first) fputc(' ', _fp);
      if (p->get_type() == type_ref) {
        if (fputc('(', _fp) == EOF) return false;
        Expr e(p);
        if (!e.write(_fp)) return false;
        if (fputc(')', _fp) == EOF) return false;
      } else if (p->get_type() == type_word) {
        WString ws = (WString)(*p);
        bool f = is_good_wstr(ws);
        if (!f) fputc('\"', _fp);
        if (!write_wstr(_fp, ws)) return false;
        if (!f) fputc('\"', _fp);
      } else if (p->get_type() == type_int32) {
        if (fprintf(_fp, "%" PRIdPTR, ((Int32 const&)(*p)).to_int()) == -1)
          return false;
      } else if (p->get_type() == type_int) {
        mpz_t* z = static_cast<Integer*>(p)->get_mpz_ptr();
        if (!mpz_out_str(_fp, 10, *z)) return false;
//        if (!write_wstr(_fp, (WString)(*p))) return false;
      } else {
        FATAL("Not supported yet");
      }
    }
  }
  if (chars_flag) {
    if (fputc('\'', _fp) == EOF) return false;
  }
  return true;
}

INLINE bool Expr::print (FILE* _fp) const
{
  for (Term* p = first; p < last; p++) {
    if (p->is_sym()) {
      WString s = (WString)(*p);
      size_t len = s.get_length();
      char buf[MB_CUR_MAX + 1];
      for (size_t i = 0; i < len; i++) {
        size_t n = wctomb(buf, s[i]);
        if (n != (size_t)(-1)) {
          buf[n] = 0;
          if (fputs(buf, _fp) == EOF) return false;
        } else {
          if (fputc('?', _fp) == EOF) return false;
        }
      }
    } else if (p->is_ref()) {
      if (fputc('(', _fp) == EOF) return false;
      Expr e(p);
      if (!e.print(_fp)) return false;
      if (fputc(')', _fp) == EOF) return false;
    } else {
      FATAL("Not supported yet");
    }
  }
  return true;
}

INLINE Expr::operator WString () const
{
  WString res;
  for (Term* p = first; p < last; p++) {
    if (p->is_sym()) {
      res = res + (WString)(*p);
    } else if (p->is_ref()) {
      res = res + WString(L"(") + (WString)(Expr(p)) + WString(L")");
    } else {
      FATAL("Not supported yet");
    }
  }
  return res;
}

#endif // ALL_INLINE

#undef is_not_right_margin
#undef is_not_left_margin

}

#endif // __rf_expr_ih__