term.hh

Go to the documentation of this file.

// This file is a part of Aurelia.
// Copyright (C) 2010  Valentin David
// Copyright (C) 2010  University of Bergen
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.


#ifndef __TERM_HH
# define __TERM_HH

# include "constructor.hh"
# include <cassert>
# include <cstdlib>
# include "../strategies/failure.hh"
# include "../lists/listable.hh"
# include "../max_shared/max_shared_ptr.hh"
# include "../memory/pool_allocator.hh"

namespace aurelia {

  template <typename Pool>
  struct untyped_term;

  template <typename Pool>
  struct untyped_term_core {
  private:
    untyped_constructor<Pool> _constructor;
    const untyped_term<Pool>* children;
    unsigned _hash;

  public:
    ~untyped_term_core() {
      if (children != NULL) {
        for (unsigned i = 0; i < _constructor->arity(); ++i)
          (children+i)->~untyped_term();
        free((void*)children);
      }
    }

    untyped_term_core(): _constructor("", 0), _hash(0) {
      children = NULL;
    }

  private:
    void copy(const list_nil&, untyped_term<Pool>*) {
    }

    template <typename T,
              typename M =
              typename aurelia::list_model<T>::model,
              typename = typename
              std::enable_if<!std::is_same<void,
                                           typename M::head_t>::value>::type>
    void copy(const T& l, untyped_term<Pool>* list) {
      typedef typename aurelia::list_concept<M>::check require;
      new (list+(unsigned)M::size-1) untyped_term<Pool>(head(l));
      copy(tail(l), list);
    }

  public:

    template <typename OtherPool,
              typename =
              typename
              std::enable_if<!std::is_same<Pool, OtherPool>::value>::type>
    untyped_term_core(const untyped_term<OtherPool>& other):
      _constructor(other->constructor()) {
      untyped_term<Pool>* tc = NULL;
      _hash = _constructor->hash();
      if (_constructor->arity() != 0) {
        tc = (untyped_term<Pool>*)malloc(_constructor->arity()*sizeof(untyped_term<Pool>));
        for (unsigned i = 0; i < _constructor->arity(); ++i) {
          new (tc+i) untyped_term<Pool>((*other)[i]);
          _hash ^= tc[i]->hash();
          _hash = (_hash << 11) | (_hash >> 21);
        }
      }
      children = tc;
    }

    template <typename L,
              typename M = typename list_model<L>::model>
    untyped_term_core(const untyped_constructor<Pool>& c, const L& ch):
      _constructor(c), children(NULL)
    {
      if (c->arity() != M::size) {
        throw failure();
      }
      _hash = c->hash();
      untyped_term<Pool>* tc = NULL;
      if (M::size != 0)
        tc = (untyped_term<Pool>*)malloc((unsigned)M::size*sizeof(untyped_term<Pool>));
      copy(ch, tc);
      children = tc;
      for (unsigned i = 0; i < c->arity(); ++i) {
        _hash ^= children[i]->hash();
        _hash = (_hash << 11) | (_hash >> 21);
      }
    }

    untyped_term_core(const untyped_constructor<Pool>& c, const untyped_term<Pool>& ch)
      : _constructor(c) {
      if (c->arity() != 1) {
        children = NULL;
        throw failure();
      }
      _hash = c.hash();
      untyped_term<Pool>* tc = (untyped_term<Pool>*)malloc(sizeof(untyped_term<Pool>));
      new (tc) untyped_term<Pool>(ch);
      _hash ^= tc[0]->hash();
      _hash = (_hash << 11) | (_hash >> 21);
      children = tc;
    }

    untyped_term_core(const untyped_constructor<Pool>& c, const untyped_term<Pool>* ch)
      : _constructor(c) {
      _hash = c->hash();
      if (c->arity() != 0)
        children = ch;
      else
        children = NULL;
      for (unsigned i = 0; i < c->arity(); ++i) {
        _hash ^= children[i]->hash();
        _hash = (_hash << 11) | (_hash >> 21);
      }
    }

    untyped_term_core(untyped_term_core&& other):
      _constructor(std::move(other._constructor)),
      children(NULL),
      _hash(other._hash)
    {
      std::swap(children, other.children);
    }

    untyped_term_core(const untyped_term_core& other)
      : _constructor(other._constructor) {
      _hash = other._hash;
      untyped_term<Pool>* tc = NULL;
      if (_constructor->arity() != 0) {
        tc = (untyped_term<Pool>*)malloc(_constructor->arity()*sizeof(untyped_term<Pool>));
        for (unsigned i = 0; i < _constructor->arity(); ++i) {
          new (tc+i) untyped_term<Pool>(other.children[i]);
        }
      }
      children = tc;
    }

    untyped_term_core& operator=(const untyped_term_core& other) {
      return (*this) = untyped_term_core(other);
    }

    untyped_term_core& operator=(untyped_term_core&& other) {
      std::swap(_constructor, other._constructor);
      std::swap(children, other.children);
      std::swap(_hash, other._hash);
      return *this;
    }

    unsigned hash() const {
      return _hash;
    }

    bool operator==(const untyped_term_core& other) const {
      if (_constructor != other._constructor)
        return false;
      for (unsigned i = 0; i < _constructor->arity(); ++i)
        if (children[i] != other.children[i])
          return false;
      return true;
    }

    const untyped_term<Pool>& operator[](unsigned n) const {
      if (n >= _constructor->arity())
        throw failure();
      return children[n];
    }

    const untyped_constructor<Pool>& constructor() const {
      return _constructor;
    }
  };

  template <typename Pool>
  struct untyped_term:
    public max_shared_ptr<untyped_term_core<Pool>,
                          member_hash,
                          std::equal_to<untyped_term_core<Pool> >,
                          pool_allocator<untyped_term_core<Pool> > > {
  public:
    typedef max_shared_ptr<untyped_term_core<Pool>,
                           member_hash,
                           std::equal_to<untyped_term_core<Pool> >,
                           pool_allocator<untyped_term_core<Pool> > > super;

    untyped_term(const untyped_term& other): super((const super&)(other)) {
    }

    untyped_term(untyped_term&& other): super((super&&)std::move(other)) {
    }

    untyped_term(): super() {
    }

    template <typename OtherPool,
              typename =
              typename
              std::enable_if<!std::is_same<Pool, OtherPool>::value>::type>
    bool operator==(const untyped_term<OtherPool>& other) const {
      return *this == untyped_term(other);
    }

    bool operator==(const untyped_term& other) const {
      return this->super::operator==(other);
    }

    untyped_term& operator=(const untyped_term& other) {
      this->super::operator=(other);
      return *this;
    }

    untyped_term& operator=(untyped_term&& other) {
      this->super::operator=(other);
      return *this;
    }

    template <typename OtherPool,
              typename =
              typename
              std::enable_if<!std::is_same<Pool, OtherPool>::value>::type>
    untyped_term(const untyped_term<OtherPool>& other): super(other) {}

    template <typename L,
              typename M = typename list_model<L>::model>
    untyped_term(const untyped_constructor<Pool>& c, const L&l): super(c, l) {
    }

    untyped_term(const untyped_constructor<Pool>& c, const untyped_term<Pool>&l): super(c, l) {
    }

    untyped_term(const untyped_constructor<Pool>& c, const untyped_term<Pool>* l): super(c, l) {
    }

    untyped_term(const untyped_constructor<Pool>& c): super(c, list_nil()) {}

    untyped_constructor<Pool> constructor() const {
      return (*this)->constructor();
    }

    const untyped_term<Pool>& operator[](unsigned i) const {
      return (**this)[i];
    }

    operator list_cons<untyped_term<Pool>, list_nil>() const {
      return list_cons<untyped_term<Pool>, list_nil>()(*this, list_nil());
    }

    unsigned hash() const {
      return (*this)->hash();
    }
  };

  template <typename Stream, typename Pool>
  void print(Stream& s, const untyped_term<Pool>& t, bool inlist = false) {
    if (t.constructor() == untyped_constructor<Pool>::AS_EMPTY_LIST) {
      if (!inlist)
        s << "[]";
    } else if (t.constructor() == untyped_constructor<Pool>::AS_LIST) {
      if (!inlist)
        s << "[";
      else
        s << ",";
      bool snd = false;
      for (unsigned i = 0;
           i < t.constructor().arity();
           ++i) {
        print(s, t[i],snd);
      snd = true;
      }
      if (!inlist)
        s << "]";
    } else {
      s << t.constructor().name();
      if (t.constructor().arity() != 0)
        s << "(";
      for (unsigned i = 0;
           i < t.constructor().arity();
           ++i) {
        if (i != 0)
        s << ",";
        print(s, t[i]);
      }
      if (t.constructor().arity() != 0)
        s << ")";
    }
  }

  template <typename Stream, typename Pool>
  Stream& operator<<(Stream& s, const untyped_term<Pool>& t) {
    print(s, t);
    return s;
  }

  template <typename Pool>
  struct listable_model<untyped_term<Pool> > {
    struct model {
      typedef untyped_term<Pool> type;
    };
  };

  template <typename Pool>
  template <typename L,
            typename,
            template <typename> class,
            typename>
  untyped_term<Pool> untyped_constructor<Pool>::operator[](const L& l) const {
    return untyped_term<Pool>(*this, l);
  }

}

namespace std {
  template <typename Pool>
  struct hash<aurelia::untyped_term<Pool> > {
    unsigned operator()(const aurelia::untyped_term<Pool>& t) const {
      return t.hash();
    }
  };
}

namespace aurelia {

  template <typename T>
  bool diff_no_conv(const T& a, const T& b) {
    return a != b;
  }

  template <typename T, typename U>
  bool diff_no_conv(const T& a, const U& b) {
    return true;
  }

  template <typename Strat, typename T>
  untyped_term<T> all_primitive(const Strat& s, const untyped_term<T>& term) {
    if (term.constructor().arity()) {
      bool changed = false;
      unsigned i = 0;
      untyped_term<T> *list = NULL;
      try {
        list = (untyped_term<T>*)malloc(term.constructor()->arity()
                                *sizeof(untyped_term<T>));
        if (list == NULL)
          throw failure();
        for (;
             i < term.constructor().arity();
             ++i) {
          new (list+i) untyped_term<T>(s(term[i]));
          changed = changed || diff_no_conv(list[i], term[i]);
        }
      }
      catch (...) {
        if (list == NULL)
          throw ;
        for (unsigned j = 0; j < i; ++j) {
          (list+j)->~untyped_term<T>();
        }
        free(list);
      throw ;
      }
      if (changed)
        return untyped_term<T>(term.constructor(), list);
      else {
        for (unsigned j = 0;
             j < term.constructor().arity();
             ++j)
          (list+j)->~untyped_term<T>();
        free(list);
        return term;
      }
    }
    else
      return term;
  }

}

#endif