source: to-imperative/trunk/runtime/rf_expr.hh @ 288

// $Source$
// $Revision: 288 $
// $Date: 2002-12-19 12:11:29 +0000 (Thu, 19 Dec 2002) $

#ifndef __rf_expr_hh__
#define __rf_expr_hh__

#include "rf_common.hh"
#include "rf_term.hh"
#include "pxx_memory_chunk.hh"

#include <new>
#include <string.h>

namespace rfrt
{

//
// expression splitting directions
enum Direction
{
  d_lt,         // split from left
  d_rt          // split from right
};

//
// Refal+ expression class
class Expr
{

//
// iterator is our friend
template <Direction D = d_lt>
friend class SplitIterator ;

//
// term is our friend
friend class Term ;

private:

  //
  // pointer to the first term
  Term* first;
  //
  // pointer beyond the last term
  Term* last;
  //
  // pointer to expression's holder in memory
  M_Chunk* mem_chunk;
  //
  // flag pointing that expression has bracket terms
  uintptr_t flags;

private:

  //
  // private constructor reserving for expression with specified len
  inline Expr (size_t const _len, int _d)
  {
    init(_len, _d);
    flags = 0;
    D( printf("+ %p(%p,%p,%p) of size %d\n", this, first, last, mem_chunk, _len); )
  }

public:

  //
  // constructor from character string
  inline Expr (char const* _s = null)
  {
    //
    // initialize expression
    init(_s != null ? strlen(_s) : 0, 0);
    //
    // in a loop...
    for (Term* p = first; p < last; p++, _s++) {
      //
      // ...create a symbol in place
      new(p) Term(*_s);
    }
    //
    // mark expression as flat
    flags = 0;
    D( printf("+ %p(%p,%p,%p) from %s\n", this, first, last, mem_chunk, _s); )
  }

  //
  // constructor from expression holder
  inline Expr( Term const* _cp )
  {
    //
    // if we really have a reference to expression...
    if( _cp->is_ref() ) {
      //
      // ...get its first term...
      first = _cp->get_first();
      //
      // ...and last term
      last = _cp->get_last();
      //
      // obtain a pointer to expression's memory chunk
      mem_chunk = _cp->get_mem_chunk();
      //
      // increment reference counter
      mem_chunk->inc_ref_count();
      //
      // check whether reference expression is flat and set a flag otherwise
      flags = _cp->data1 & REF_BIT;
      D( printf("+ %p(%p,%p,%p) from %p()\n", this, first, last, mem_chunk, _cp); )
    }
    //
    // no, we have a symbol...
    else {
      //
      // ...and this is the error
      FATAL( "Unable to construct expression from symbol" );
    }
  }

  //
  //! Dereference constructor. Should be called only with valid
  //  position.
  inline Expr (Expr const& _expr, uintptr_t _pos)
  {
    new(this) Expr(_expr.first + _pos);
  }
 
  //
  //! Subexpression constructor
  inline Expr (Expr const& _expr, uintptr_t _pos, uintptr_t _length)
  {
    new(this) Expr(
      _expr.first + _pos, _expr.first + _pos + _length,
      _expr.mem_chunk,
      _expr.flags
    );
  }

  //
  // constructor from term
  inline Expr (Term const& _cp)
  {
    init(1, 0);
    *first = _cp;
    flags |= REF_BIT;
//    ref_childs();
    D( printf("+ %p(%p,%p,%p) by copy from term %p\n",
          this, first, last, mem_chunk, &_cp); )
  }

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

  //
  // generic constructor - should not be called directly
  inline Expr (
    Term* const _first, Term* const _last,
    M_Chunk* const _mem_chunk, uintptr_t const _flags
  ) :
    first (_first),
    last (_last),
    mem_chunk (_mem_chunk),
    flags (_flags)
  {
    //
    // increment a reference counter to allocated block
    mem_chunk->inc_ref_count();
    D( printf("+ %p(%p,%p,%p) by generic constructor",
          this, first, last, mem_chunk); )
  }

  inline Expr (Expr const* _expr) :
    first (_expr->first),
    last (_expr->last),
    mem_chunk (_expr->mem_chunk),
    flags (_expr->flags)
  {
    //
    // increment a reference counter to allocated block
//    inc_ref_count();
    D( printf("+ %p(%p,%p,%p) from *%p\n",
          this, first, last, mem_chunk, _expr); )
  }

  //
  // destructor
  inline ~Expr ()
  {
    D( printf("- %p(%p,%p,%p)\n", this, first, last, mem_chunk); )
    drop();
  }

  //
  //! Drop an expression
  inline void drop()
  {
    //
    // decrement reference counter and destroy an object if it is zero
    if( mem_chunk != null && !mem_chunk->dec_ref_count() ) {
      //
      // walk through and decrement reference counters on childs
      deref_childs();
      //
      // destruct expression holder in memory
      mem_chunk->destruct( &allocator );
      D( printf("-- %p\n", mem_chunk); )
    }
//    first = last = null;
    mem_chunk = null;
//    flags = 0;
  }

  //
  // assignment operator
  inline const Expr &operator=( const Expr &_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();
      //
      // and build a copy in place
      // new(this) Expr(_expr);     // not very good idea indeed
      first     = _expr.first;
      last      = _expr.last;
      mem_chunk = _expr.mem_chunk;
      flags     = _expr.flags;
      //
      //
      mem_chunk->inc_ref_count();
    }
    //
    // return reference to self
    return *this;
  }

private:

  //
  // init an expression
  inline void init( size_t _len, int _d )
  {
    D( printf("init is called for %p\n", this); )
    //
    // construct new memory chunk with a help from allocator
    mem_chunk = pxx::construct_mem_chunk( &allocator, _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 () );
    //
    // if we place expression at the left side of allocated block...
    if( _d > 0 ) {
      first = start;
      last  = first + _len;
    }
    //
    // ...or at the right side of allocated block...
    else if( _d < 0 ) {
      last  = end;
      first = last - _len;
    }
    //
    // ...or in the middle of allocated block
    else {
      first = start + (mem_chunk->get_size() / sizeof(Term) - _len) / 2;
      last  = first + _len;
    }
    Term* prev = first - 1;
    //
    // if we have at least one term to the left of the first term
    if( prev >= start ) {
      //
      // setup border symbol
      prev ->data1 = SYM_BORDER;
      start->data1 = SYM_EMPTY;
      start->data2 = first - start;
    }
    //
    // if we have at least one term to the right of the last term
    if( last < end ) {
      //
      // setup border symbol
      last->data1 = SYM_BORDER;
    }
  }

  inline void ref_childs() const
  {
    for( Term *p = first; p < last; p++ )
    {
      if( p->is_ref() )
        p->get_mem_chunk()->inc_ref_count();
    }
  }
/*
    Term* p = first;
    while (p < last) {
      if (p->is_ref()) {
        Expr e(p);
        e.inc_ref_count();
        
      }
      p++;
    }
  }
*/

  inline void deref_childs () const
  {
    Term *p = static_cast<Term*>( mem_chunk->get_first() );
    Term *q = static_cast<Term*>( mem_chunk->get_last() );
    if (p->data1 == SYM_EMPTY) p += p->data2;
    // ОК, сейчас попали на первый терм выражения, под которое выделялся
    // chunk. Так как deref_childs вызывается только из деструктора, то это
    // выражение всегда совпадает с *this. Или это неправда???
    //
    // Между прочим, SYM_EMPTY нужен только для этого - находить
    // первоначальное выражение в chunk'е.
    // 
    // Итого:
    //    Едем по куску chunk'а, который был отдан под изначальное выражение
    //    (для которого он выделялся).
    //    
    //    Для каждого встретившегося скобочного терма, уменьшаем кол-во ссылок
    //    на него.
    //
    //    Если встретили this выражение, и оно flat, то пропускаем его
    //    полностью, что разумно.
    //
    while ((p < q) && !p->is_border()) {
      if (p == first && is_flat()) { p = last; continue; }
      if (p->is_ref()) {
        p->get_mem_chunk()->dec_ref_count();
      }
      p++;
    }
  }

public:

  inline void write (FILE* _fp) const
  {
    bool chars_flag = false;
    for (Term* p = first; p < last; p++) {
      if (p->is_sym()) {
        if (p->is_char()) {
          if (!chars_flag) {
            if (p != first) fputc(' ', _fp);
            fputc('\'', _fp);
            chars_flag = true;
          }
          fputc(p->get_char(), _fp);
        } else {
          FATAL("Not supported yet");
        }
      } else {
        if (chars_flag) {
          fputc('\'', _fp);
          chars_flag = false;
        }
        if (p != first) fputc(' ', _fp);
        fputc('(', _fp);
        Expr e(p);
        e.write(_fp);
        fputc(')', _fp);
      }
    }
    if (chars_flag) {
      fputc('\'', _fp);
    }
  }

  inline void writeln (FILE* _fp) const
  {
    write (_fp);
    fputc('\n', _fp);
  }

private:

  inline bool rt_alloc( uintptr_t _len ) const
  {
    Term *p = static_cast<Term*>( mem_chunk->get_last() );
    //
    // Если на наш chunk есть только одна ссылка (значит с нашего выражения),
    // то убираем по ссылке со всех скобочных термов, которые лежат правее
    // нашего выражения.
    // 
    // Если справа от нашего выражения есть пространство, то выставляем
    // границу после последнего терма нашего выражения. А почему её там не
    // стояло????? !!!!!
    //
    if( mem_chunk->no_extern_refs() )
    {
      for( Term* q = last; (q < p) && (q->data1 != SYM_BORDER); q++ )
      {
        if( q->is_ref() )
          q->get_mem_chunk()->dec_ref_count();
      }
      if( last < p )
        last->data1 = SYM_BORDER;
    }
    //
    // Если справа от нашего выражения есть достаточно места (_len) и
    // выставлена граница после последнего терма (БЛИН!!! КАК она может быть
    // НЕ выставлена????? Если _len == 0 ???), то выставить новую границу,
    // если ещё остаётся место и вернуть true.
    //
    // Иначе вернуть false.
    //
    if( (last + _len <= p) && (last->data1 == SYM_BORDER) )
    {
      if( last + _len < p )
      {
        (last + _len)->data1 = SYM_BORDER;
      }
      return true;
    }
    else
      return false;
  }

  inline bool lt_alloc( uintptr_t _len ) const
  {
    Term *p = static_cast<Term*>( mem_chunk->get_first() );
    if( mem_chunk->no_extern_refs() )
    {
      for( Term* q = first - 1; (q >= p) && (q->data1 != SYM_BORDER); q-- )
      {
        if( q->is_ref() )
          q->get_mem_chunk()->dec_ref_count();
      }
      if( first > p )
      {
        (first - 1)->data1 = SYM_BORDER;
        p->data2 = first - p;
      }
    }
    if( (first - _len >= p) && ((first - 1)->data1 == SYM_BORDER) )
    {
      if( first - _len > p )
      {
        (first - (_len + 1))->data1 = SYM_BORDER;
        p->data2 = (first - _len) - p;
      }
      return true;
    }
    else
      return false;
  }
  //
  // Гм. Чтобы это могло лежать справа и слева от выражения,
  // если ref_count == 1 ??? !!!!!
  //

public:

  inline Expr operator + (Expr const& _expr) const
  {
    D( printf("Adding %p to %p\n", &_expr, this); )
    uintptr_t len1 = last - first;
    uintptr_t len2 = _expr.last - _expr.first;
    uintptr_t len = len1 + len2;
    if (len2 == 0) {
      #if DEBUG
      empty_copy++;
      #endif
      return *this;
    } else if (len1 == 0) {
      #if DEBUG
      empty_copy++;
      #endif
      return _expr;
    } else if (rt_alloc(len2)) {
      //
      // Copy second arg
      #if DEBUG
      rt_copy++;
      #endif
      if (!_expr.is_flat()) _expr.ref_childs();
      Expr e(*this);
      e.flags |= _expr.flags;
      memcpy(e.last, _expr.first, len2 * sizeof(Term));
      e.last += len2;
      return e;
    } else if (_expr.lt_alloc(len1)) {
      //
      // Copy first arg
      #if DEBUG
      lt_copy++;
      #endif
      if (!is_flat()) ref_childs();
      Expr e(_expr);
      e.flags |= flags;
      e.first -= len1;
      memcpy(e.first, first, len1 * sizeof(Term));
      return e;
    } else {
      //
      // Copy both args
      #if DEBUG
      both_copy++;
      #endif
      Expr e(len, len1 >= len2 ? 1 : -1);
      e.flags = flags | _expr.flags;
      memcpy(e.first, first, len1 * sizeof(Term));
      memcpy(e.first + len1, _expr.first, len2 * sizeof(Term));
      if (!e.is_flat()) e.ref_childs();
      return e;
    }
  }

  inline Term operator () () const
//  inline Expr operator () () const
  {
    return Term(*this);
//    return Expr(Term(self));
  }

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

  inline Expr operator + (Term const& _term) const
  {
    uintptr_t len1 = last - first;
    uintptr_t len = len1 + 1;
    if (rt_alloc(1)) {
      //
      // Copy second arg
      #if DEBUG
      rt_copy++;
      #endif
      Expr e(*this);
      if (_term.is_ref()) e.flags |= REF_BIT;
      *e.last = _term;
      e.last++;
      return e;
    } else {
      //
      // Copy both args
      #if DEBUG
      both_copy++;
      #endif
      Expr e(len, 1);
      if (!is_flat()) {
        e.flags = REF_BIT;
        ref_childs();
      }
      if (_term.is_ref()) e.flags |= REF_BIT;
      memcpy(e.first, first, len1 * sizeof(Term));
      *(e.first + len1) = _term;
      return e;
    }
  }

  friend
  inline Expr operator + (Term const& _term, Expr const& _expr)
  {
    uintptr_t len1 = _expr.last - _expr.first;
    uintptr_t len = len1 + 1;
    if (_expr.lt_alloc(1)) {
      //
      // Copy first arg
      #if DEBUG
      lt_copy++;
      #endif
      Expr e(_expr);
      if (_term.is_ref()) e.flags |= REF_BIT;
      e.first--;
      *e.first = _term;
      return e;
    } else {
      //
      // Copy both args
      #if DEBUG
      both_copy++;
      #endif
      Expr e(len, -1);
      if (!_expr.is_flat()) {
        e.flags = REF_BIT;
        _expr.ref_childs();
      }
      if (_term.is_ref()) e.flags |= REF_BIT;
      memcpy(e.first + 1, _expr.first, len1 * sizeof(Term));
      *(e.first) = _term;
      return e;
    }
  }

  friend
  inline Expr operator + (Term const& _term1, Term const& _term2)
  {
    //
    // Copy both args
    #if DEBUG
    both_copy++;
    #endif
    Expr e(2, 0);
    if (_term1.is_ref() || _term2.is_ref()) {
      e.flags |= REF_BIT;
    }
    *(e.first) = _term1;
    *(e.first + 1) = _term2;
    return e;
  }

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

  inline bool is_flat () const
  {
    return flags == 0;
  }

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

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

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

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

  inline uintptr_t get_flags () const
  {
    return flags;
  }

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

  friend
  inline bool eq (
    Term const* _f1, Term const* _l1, Term const* _f2, Term const* _l2
  )
  {
    if ((_l1 - _f1) == (_l2 - _f2)) {
      for (; _f1 < _l1; _f1++, _f2++) {
        if (*_f1 != *_f2) return false;
      }
      return true;
    }
    return false;
  }

friend
inline bool eq_expr (
  const Expr &_e1, uintptr_t _pos1, uintptr_t _len1,
  const Expr &_e2, uintptr_t _pos2, uintptr_t _len2
)
{
  if (_len1 == _len2) {
    Term *p1 = _e1.get_first() + _pos1;
    Term *p2 = _e2.get_first() + _pos2;
    Term *l1 = p1  + _len1;
    for (; p1 < l1; p1++, p2++) {
      if (*p1 != *p2) return false;
    }
    return true;
  }
  return false;
}


friend
inline bool flat_eq (
  const Expr &_e1, uintptr_t _pos1,
  const Expr &_e2, uintptr_t _pos2, uintptr_t _len
)
{
  Term *p1 = _e1.get_first() + _pos1;
  Term *p2 = _e2.get_first() + _pos2;
  Term *l1 = p1  + _len;
  for (; p1 < l1; p1++, p2++) {
    if (p1->get_type() != p2->get_type() || p1->data2 != p2->data2)
      return false;
  }
  return true;
}

  friend
  inline bool operator == (Term const& _t1, Term const& _t2)
  {
    if (_t1.is_sym() && _t2.is_sym()) {
      if (_t1.get_type() == _t2.get_type()) {
        if (_t1.data2 == _t2.data2) {
          return true;
        }
      }
    } else if (_t1.is_ref() && _t2.is_ref()) {
      return
        eq(_t1.get_first(), _t1.get_last(), _t2.get_first(), _t2.get_last());
    }
    return false;
  }

// _t1.is_sym() && _t2.is_sym()
// have_same_type(_t1, _t2)
// _t1.data2 == _t2.data2 || (_t1.is_compound() && _t1->data2 == _t2->data2)
// В принципе, компилятор мог бы знать с каким типом мы имеем дело. Тогда можно
// было бы избежать лишней проверки is_compound().
// _t1.is_ref() && _t2.is_ref()

  friend
  inline bool operator != (Term const& _t1, Term const& _t2)
  {
    return !(_t1 == _t2);
  }

  inline bool operator == (Expr const& _expr) const
  {
    return eq(first, last, _expr.first, _expr.last);
  }

  inline bool operator != (Expr const& _expr) const
  {
    return !eq(first, last, _expr.first, _expr.last);
  }

  inline M_Chunk *get_mem_chunk()
  {
    return mem_chunk;
  }

  inline void set_mem_chunk( M_Chunk *_ptr )
  {
    mem_chunk = _ptr;
  }

  class Iterator
  {

  private:

    Expr& expr ;
    Term* ptr ;

  public:

    inline Iterator (Expr& _expr) :
      expr (_expr),
      ptr (_expr.first)
    {}

    inline ~Iterator ()
    {}

    inline operator bool () const
    {
      return (ptr < expr.last) && (ptr >= expr.first);
    }

    inline Term* operator -> () const
    {
      #ifdef PARANOIA
      if (!*this) FATAL("Attempt to obtain pointer to invalid term");
      #endif
      return ptr;
    }

    inline Iterator& operator ++ ()
    {
      ptr++;
      return *this;
    }

    inline Iterator& operator ++ (int)
    {
      return operator++();
    }

    inline Iterator& operator -- ()
    {
      ptr--;
      return *this;
    }

    inline Iterator& operator -- (int)
    {
      return operator--();
    }

    inline Iterator& operator += (int _offset)
    {
      ptr +=_offset;
      return *this;
    }

    inline Iterator& operator -= (int _offset)
    {
      ptr -=_offset;
      return *this;
    }

  };

};

//
// is needed for () operation
inline Term::Term (Expr const& _expr) :
  data1 ((uintptr_t)_expr.first | ORDER1(_expr.mem_chunk->get_order())),
  data2 ((uintptr_t)_expr.last | ORDER2(_expr.mem_chunk->get_order()))
{
  D( printf("+ term %p from expression %p(%p,%p,%p)\n",
        this, &_expr, _expr.first, _expr.last, _expr.mem_chunk); )
  data1 |= (_expr.flags & REF_BIT);
  _expr.mem_chunk->inc_ref_count();
}

template <Direction D>
class SplitIterator
{

  Expr lt ;
  Expr rt ;
  bool state ;

public:

  inline SplitIterator (Expr const& _expr, uintptr_t _min_len = 0)
  {
    FATAL("Not supported yet");
  }

  ~SplitIterator ()
  {}

  inline SplitIterator& operator ++ () {
    if (lt.last < rt.last) {
      if (lt.last->is_ref()) lt.flags |= REF_BIT;
      lt.last++;
      rt.first++;
    } else {
      state = false;
    }
    return *this;
  }

  inline SplitIterator& operator -- () {
    if (lt.first < rt.first) {
      lt.last--;
      rt.first--;
      if (rt.first->is_ref()) rt.flags |= REF_BIT;
    } else {
      state = false;
    }
    return *this;
  }

  inline SplitIterator& operator ++ (int) {
    return operator++();
  }

  inline SplitIterator& operator -- (int) {
    return operator--();
  }

  inline operator bool ()
  {
    return state;
  }

  inline Expr const& get_left () const
  {
    return lt;
  }

  inline Expr const& get_right () const
  {
    return rt;
  }

};

template <>
inline SplitIterator<d_lt>::SplitIterator (
  Expr const& _expr, uintptr_t _min_len
) :
  lt (_expr.get_first(), _expr.get_first() + _min_len,
      _expr.mem_chunk, 0),
  rt (_expr.get_first() + _min_len, _expr.get_last(),
      _expr.mem_chunk, 0),
  state (true)
{}

#define iter(e) e##_iter

#define lsplit(e, minlen, le, re) \
  SplitIterator<d_lt> iter(e)(e, minlen); \
  Expr const& le = iter(e).get_left(); \
  Expr const& re = iter(e).get_right()

#if 0
#define lsplit_e(e, le, re) \
  SplitIterator<d_lt> iter(e)(e, 0); \
  Expr const& le = iter(e).get_left(); \
  Expr const& re = iter(e).get_right()

#define lsplit_v(e, le, re) \
  SplitIterator<d_lt> iter(e)(e, 1); \
  Expr const& le = iter(e).get_left(); \
  Expr const& re = iter(e).get_right()

#define can_lsplit_s(e) \
  (e.get_len() >= 1 && e.get_first()->is_sym())

#define lsplit_s(e, le, re) \
  Expr le(e.get_first(), e.get_first() + 1, e.get_ref_count(), 0); \
  Expr re(e.get_first() + 1, e.get_last(), e.get_ref_count(), e.get_flags()); \

#define can_lsplit_t(e) \
  (e.get_len() >= 1)

#define lsplit_t(e, le, re) \
  Expr le( \
    e.get_first(), e.get_first() + 1, \
    e.get_ref_count(), e.get_first()->is_sym() ? 0 : REF_BIT \
  ); \
  Expr re(e.get_first() + 1, e.get_last(), e.get_ref_count(), e.get_flags()); \

#define can_lsplit_h(e, he) ( \
  e.get_len() >= he.get_len() && \
  eq( \
    e.get_first(), e.get_first() + he.get_len(), \
    he.get_first(), he.get_last() \
  ) \
)

#define lsplit_h(e, le, re) \
  Expr re( \
    e.get_first() + le.get_len(), e.get_last(), \
    e.get_ref_count(), e.get_flags() \
  );
#endif

}

#endif // __rf_expr_hh__