X-Git-Url: https://scm.cri.ensmp.fr/git/Faustine.git/blobdiff_plain/c7f552fd8888da2f0d8cfb228fe0f28d3df3a12c..b4b6f2ea75b9f0f3ca918f5b84016610bf7a4d4f:/interpretor/preprocessor/faust-0.9.47mr3/compiler/tlib/tree.hh diff --git a/interpretor/preprocessor/faust-0.9.47mr3/compiler/tlib/tree.hh b/interpretor/preprocessor/faust-0.9.47mr3/compiler/tlib/tree.hh new file mode 100644 index 0000000..9ab6170 --- /dev/null +++ b/interpretor/preprocessor/faust-0.9.47mr3/compiler/tlib/tree.hh @@ -0,0 +1,267 @@ +/************************************************************************ + ************************************************************************ + FAUST compiler + Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale + --------------------------------------------------------------------- + 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 2 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, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + ************************************************************************ + ************************************************************************/ + + +/***************************************************************************** +******************************************************************************/ + +/** \file tree.hh + * A tree library with hashconsing and maximal sharing capabilities. + * + * A tree library with hashconsing and maximal sharing capabilities. + * + * API: + * + * \li tree (n) : tree of node n with no branch + * \li tree (n, t1) : tree of node n with a branch t + * \li tree (n, t1,...,tm) : tree of node n with m branches t1,...,tm + * + * Useful conversions : + * + * \li int tree2int (t) : if t has a node of type int, return it otherwise error + * \li float tree2float (t) : if t has a node of type float, return it otherwise error + * \li const char* tree2str (t) : if t has a node of type symbol, return its name otherwise error + * \li void* tree2ptr (t) : if t has a node of type ptr, return it otherwise error + * + * Pattern matching : + * + * \li if (isTree (t, n)) ... : t has node n and no branches; + * \li if (isTree (t, n, &t1) ... : t has node n and 1 branch, t1 is set accordingly; + * \li if (isTree (t, n, &t1...&tm)... : t has node n and m branches, ti's are set accordingly; + * + * Accessors : + * + * \li t->node() : the node of t { return fNode; } + * \li t->height() : lambda height such that H(x)=0, H(\x.e)=1+H(e), H(e*f)=max(H(e),H(f)) + * \li t->arity() : the number of branches of t { return fArity; } + * \li t->branch(i) : the ith branch of t + * + * Attributs : + * + * \li t->attribut() : return the attribut (also a tree) of t + * \li t->attribut(t') : set the attribut of t to t' + * + * + * Properties: + * + * If p and q are two CTree pointers : + * p != q <=> *p != *q + * + **/ + +/***************************************************************************** +******************************************************************************/ + + + +#ifndef __TREE__ +#define __TREE__ + +#include "symbol.hh" +#include "node.hh" +#include +#include +#include + +//---------------------------------API--------------------------------------- + +class CTree; +typedef CTree* Tree; + +typedef map plist; +typedef vector tvec; + +/** + * A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches. + * A CTree = (Node x [CTree]) is the association of a content Node and a list of subtrees + * called branches. In order to maximize the sharing of trees, hashconsing techniques are used. + * Ctrees at different addresses always have a different content. A first consequence of this + * approach is that a fast equality test on pointers can be used as an equality test on CTrees. + * A second consequence is that a CTree can NEVER be modified. But a property list is associated + * to each CTree that can be used to attach arbitrary information to it. Due to the maximal + * sharing property it is therefore easy to do memoization using these property lists. + * + * Means are also provided to do maximal sharing on recursive trees. The idea is to start from + * a deBruijn representation and progressively build a classical representation such that + * alpha-equivalent recursive CTrees are necesseraly identical (and therefore shared). + * + * WARNING : in the current implementation CTrees are allocated but never deleted + **/ + +class CTree +{ + private: + static const int kHashTableSize = 2000000; //510511; ///< size of the hash table used for "hash consing" + static Tree gHashTable[kHashTableSize]; ///< hash table used for "hash consing" + + public: + static bool gDetails; ///< Ctree::print() print with more details when true + static unsigned int gVisitTime; ///< Should be incremented for each new visit to keep track of visited tree. + + private: + // fields + Tree fNext; ///< next tree in the same hashtable entry + Node fNode; ///< the node content of the tree + void* fType; ///< the type of a tree + plist fProperties; ///< the properties list attached to the tree + unsigned int fHashKey; ///< the hashtable key + int fAperture; ///< how "open" is a tree (synthezised field) + unsigned int fVisitTime; ///< keep track of visits + tvec fBranch; ///< the subtrees + + CTree (unsigned int hk, const Node& n, const tvec& br); ///< construction is private, uses tree::make instead + + bool equiv (const Node& n, const tvec& br) const; ///< used to check if an equivalent tree already exists + static unsigned int calcTreeHash (const Node& n, const tvec& br); ///< compute the hash key of a tree according to its node and branches + static int calcTreeAperture (const Node& n, const tvec& br); ///< compute how open is a tree + + public: + ~CTree (); + + static Tree make (const Node& n, int ar, Tree br[]); ///< return a new tree or an existing equivalent one + static Tree make(const Node& n, const tvec& br); ///< return a new tree or an existing equivalent one + + // Accessors + const Node& node() const { return fNode; } ///< return the content of the tree + int arity() const { return fBranch.size();} ///< return the number of branches (subtrees) of a tree + Tree branch(int i) const { return fBranch[i]; } ///< return the ith branch (subtree) of a tree + unsigned int hashkey() const { return fHashKey; } ///< return the hashkey of the tree + int aperture() const { return fAperture; } ///< return how "open" is a tree in terms of free variables + void setAperture(int a) { fAperture=a; } ///< modify the aperture of a tree + + + // Print a tree and the hash table (for debugging purposes) + ostream& print (ostream& fout) const; ///< print recursively the content of a tree on a stream + static void control (); ///< print the hash table content (for debug purpose) + + // type information + void setType(void* t) { fType = t; } + void* getType() { return fType; } + + // Keep track of visited trees (WARNING : non reentrant) + static void startNewVisit() { ++gVisitTime; } + bool isAlreadyVisited() { return fVisitTime==gVisitTime; } + void setVisited() { /*assert(fVisitTime!=gVisitTime);*/ fVisitTime=gVisitTime; } + + + // Property list of a tree + void setProperty(Tree key, Tree value) { fProperties[key] = value; } + void clearProperty(Tree key) { fProperties.erase(key); } + void clearProperties() { fProperties = plist(); } + + void exportProperties(vector& keys, vector& values); + + Tree getProperty(Tree key) { + plist::iterator i = fProperties.find(key); + if (i==fProperties.end()) { + return 0; + } else { + return i->second; + } + } +}; + +//---------------------------------API--------------------------------------- + +// to build trees +inline Tree tree (const Node& n) { Tree br[1]; return CTree::make(n, 0, br); } +inline Tree tree (const Node& n, const Tree& a) { Tree br[]= {a}; return CTree::make(n, 1, br); } +inline Tree tree (const Node& n, const Tree& a, const Tree& b) { Tree br[]= {a,b}; return CTree::make(n, 2, br); } +inline Tree tree (const Node& n, const Tree& a, const Tree& b, const Tree& c) { Tree br[]= {a,b,c}; return CTree::make(n, 3, br); } +inline Tree tree (const Node& n, const Tree& a, const Tree& b, const Tree& c, const Tree& d) { Tree br[]= {a,b,c,d}; return CTree::make(n, 4, br); } + +inline Tree tree (const Node& n, const Tree& a, const Tree& b, const Tree& c, const Tree& d, const Tree& e) { Tree br[]= {a,b,c,d,e}; return CTree::make(n, 5, br); } + +// useful conversions +int tree2int (Tree t); ///< if t has a node of type int, return it otherwise error +double tree2float (Tree t); ///< if t has a node of type float, return it otherwise error +double tree2double (Tree t); ///< if t has a node of type float, return it otherwise error +const char* tree2str (Tree t); ///< if t has a node of type symbol, return its name otherwise error +void* tree2ptr (Tree t); ///< if t has a node of type ptr, return it otherwise error +void* getUserData(Tree t); ///< if t has a node of type symbol, return the associated user data + +// pattern matching +bool isTree (const Tree& t, const Node& n); +bool isTree (const Tree& t, const Node& n, Tree& a); +bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b); +bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c); +bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d); +bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d, Tree& e); + +//printing +inline ostream& operator << (ostream& s, const CTree& t) { return t.print(s); } + + +//----------------------------------------------------------------------------- +// recursive trees +//----------------------------------------------------------------------------- + +// creation a recursive trees + +Tree rec(Tree body); ///< create a de Bruijn recursive tree +Tree rec(Tree id, Tree body); ///< create a symbolic recursive tree + +bool isRec(Tree t, Tree& body); ///< is t a de Bruijn recursive tree +bool isRec(Tree t, Tree& id, Tree& body); ///< is t a symbolic recursive tree + +// creation of recursive references + +Tree ref(int level); ///< create a de Bruijn recursive reference +Tree ref(Tree id); ///< create a symbolic recursive reference + +bool isRef(Tree t, int& level); ///< is t a de Bruijn recursive reference +bool isRef(Tree t, Tree& id); ///< is t a symbolic recursive reference + + +// Open vs Closed regarding de Bruijn references + +inline bool isOpen(Tree t) { return t->aperture() > 0; } ///< t contains free de Bruijn references +inline bool isClosed(Tree t) { return t->aperture() <= 0;} ///< t dont contain free de Bruijn ref + +// lift by 1 the free de Bruijn references + +Tree lift(Tree t); ////< add 1 to the free de bruijn references of t + +Tree deBruijn2Sym (Tree t); ////< transform a tree from deBruijn to symbolic notation +void updateAperture (Tree t); ////< update aperture field of a tree in symbolic notation + +//--------------------------------------------------------------------------- + +class Tabber +{ + int fIndent; + int fPostInc; + public: + Tabber(int n=0) : fIndent(n), fPostInc(0) {} + Tabber& operator++() { fPostInc++; return *this;} + Tabber& operator--() { assert(fIndent > 0); fIndent--; return *this; } + + ostream& print (ostream& fout) + { for (int i=0; i