interpreter/preprocessor/faust-0.9.47mr3/compiler/headers/tree.hh

   1 /************************************************************************
   2  ************************************************************************
   3     FAUST compiler
   4         Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale
   5     ---------------------------------------------------------------------
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19  ************************************************************************
  20  ************************************************************************/
  21
  22
  23 /*****************************************************************************
  24 ******************************************************************************/
  25
  26 /** \file tree.hh
  27  * A tree library with hashconsing and maximal sharing capabilities.
  28  *
  29  * A tree library with hashconsing and maximal sharing capabilities.
  30  *
  31  * <b>API:</b>
  32  *
  33  * \li tree (n)                                 : tree of node n with no branch
  34  * \li tree (n, t1)                     : tree of node n with a branch t
  35  * \li tree (n, t1,...,tm)              : tree of node n with m branches t1,...,tm
  36  *
  37  * <b>Useful conversions :</b>
  38  *
  39  * \li int                      tree2int (t)    : if t has a node of type int, return it otherwise error
  40  * \li float            tree2float (t)  : if t has a node of type float, return it otherwise error
  41  * \li const char*      tree2str (t)    : if t has a node of type symbol, return its name otherwise error
  42  * \li void*            tree2ptr (t)    : if t has a node of type ptr, return it otherwise error
  43  *
  44  * <b>Pattern matching :</b>
  45  *
  46  * \li if (isTree (t, n))               ...     : t has node n and no branches;
  47  * \li if (isTree (t, n, &t1)           ... : t has node n and 1 branch, t1 is set accordingly;
  48  * \li if (isTree (t, n, &t1...&tm)...  : t has node n and m branches, ti's are set accordingly;
  49  *
  50  * <b>Accessors :</b>
  51  *
  52  * \li t->node()                : the node of t         { return fNode; }
  53  * \li t->height()              : lambda height such that H(x)=0, H(\x.e)=1+H(e), H(e*f)=max(H(e),H(f))
  54  * \li t->arity()               : the number of branches of t { return fArity; }
  55  * \li t->branch(i)     : the ith branch of t
  56  *
  57  * <b>Attributs :</b>
  58  *
  59  * \li t->attribut()    : return the attribut (also a tree) of t
  60  * \li t->attribut(t')  : set the attribut of t to t'
  61  *
  62  *
  63  * <b>Properties:</b>
  64  *
  65  * If p and q are two CTree pointers  :
  66  *              p != q  <=>  *p != *q
  67  *
  68  **/
  69
  70 /*****************************************************************************
  71 ******************************************************************************/
  72
  73
  74
  75 #ifndef     __TREE__
  76 #define     __TREE__
  77
  78 #include "symbol.hh"
  79 #include "node.hh"
  80 #include <vector>
  81 #include <map>
  82 #include <assert.h>
  83
  84 //---------------------------------API---------------------------------------
  85
  86 class   CTree;
  87 typedef CTree* Tree;
  88
  89 typedef map<Tree, Tree> plist;
  90 typedef vector<Tree>    tvec;
  91
  92 /**
  93  * A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches.
  94  * A CTree = (Node x [CTree]) is the association of a content Node and a list of subtrees
  95  * called branches. In order to maximize the sharing of trees, hashconsing techniques are used.
  96  * Ctrees at different addresses always have a different content. A first consequence of this
  97  * approach is that a fast equality test on pointers can be used as an equality test on CTrees.
  98  * A second consequence is that a CTree can NEVER be modified. But a property list is associated
  99  * to each CTree that can be used to attach arbitrary information to it. Due to the maximal
 100  * sharing property it is therefore easy to do memoization using these property lists.
 101  *
 102  * Means are also provided to do maximal sharing on recursive trees. The idea is to start from
 103  * a deBruijn representation and progressively build a classical representation such that
 104  * alpha-equivalent recursive CTrees are necesseraly identical (and therefore shared).
 105  *
 106  * WARNING : in the current implementation CTrees are allocated but never deleted
 107  **/
 108
 109 class CTree
 110 {
 111  private:
 112         static const int        kHashTableSize = 2000000; //510511;     ///< size of the hash table used for "hash consing"
 113         static Tree                     gHashTable[kHashTableSize];     ///< hash table used for "hash consing"
 114
 115  public:
 116         static bool                     gDetails;                                       ///< Ctree::print() print with more details when true
 117     static unsigned int gVisitTime;                 ///< Should be incremented for each new visit to keep track of visited tree.
 118
 119  private:
 120         // fields
 121     Tree            fNext;                              ///< next tree in the same hashtable entry
 122     Node            fNode;                              ///< the node content of the tree
 123     void*           fType;                              ///< the type of a tree
 124     plist           fProperties;                ///< the properties list attached to the tree
 125     unsigned int        fHashKey;                       ///< the hashtable key
 126     int             fAperture;                  ///< how "open" is a tree (synthezised field)
 127     unsigned int        fVisitTime;                     ///< keep track of visits
 128     tvec            fBranch;                    ///< the subtrees
 129
 130         CTree (unsigned int hk, const Node& n, const tvec& br);                                                 ///< construction is private, uses tree::make instead
 131
 132         bool            equiv                           (const Node& n, const tvec& br) const;  ///< used to check if an equivalent tree already exists
 133         static unsigned int     calcTreeHash            (const Node& n, const tvec& br);                ///< compute the hash key of a tree according to its node and branches
 134         static int      calcTreeAperture        (const Node& n, const tvec& br);                ///< compute how open is a tree
 135
 136  public:
 137         ~CTree ();
 138
 139         static Tree make (const Node& n, int ar, Tree br[]);            ///< return a new tree or an existing equivalent one
 140         static Tree make(const Node& n, const tvec& br);                        ///< return a new tree or an existing equivalent one
 141
 142         // Accessors
 143         const Node& node() const                { return fNode;                 }       ///< return the content of the tree
 144         int             arity() const           { return fBranch.size();}       ///< return the number of branches (subtrees) of a tree
 145         Tree            branch(int i) const     { return fBranch[i];    }       ///< return the ith branch (subtree) of a tree
 146         unsigned int            hashkey() const         { return fHashKey;              }       ///< return the hashkey of the tree
 147         int             aperture() const        { return fAperture;     }       ///< return how "open" is a tree in terms of free variables
 148         void            setAperture(int a)      { fAperture=a;                  }       ///< modify the aperture of a tree
 149
 150
 151         // Print a tree and the hash table (for debugging purposes)
 152         ostream&        print (ostream& fout) const;                                    ///< print recursively the content of a tree on a stream
 153         static void control ();                                                                         ///< print the hash table content (for debug purpose)
 154
 155         // type information
 156         void            setType(void* t)        { fType = t; }
 157         void*           getType()                       { return fType; }
 158
 159     // Keep track of visited trees (WARNING : non reentrant)
 160     static void     startNewVisit()                 { ++gVisitTime; }
 161     bool            isAlreadyVisited()              { return fVisitTime==gVisitTime; }
 162     void            setVisited()                    { /*assert(fVisitTime!=gVisitTime);*/ fVisitTime=gVisitTime; }
 163
 164
 165         // Property list of a tree
 166         void            setProperty(Tree key, Tree value) { fProperties[key] = value; }
 167         void            clearProperty(Tree key) { fProperties.erase(key); }
 168         void            clearProperties()               { fProperties = plist(); }
 169
 170         void            exportProperties(vector<Tree>& keys, vector<Tree>& values);
 171
 172         Tree            getProperty(Tree key) {
 173                 plist::iterator i = fProperties.find(key);
 174                 if (i==fProperties.end()) {
 175                         return 0;
 176                 } else {
 177                         return i->second;
 178                 }
 179         }
 180 };
 181
 182 //---------------------------------API---------------------------------------
 183
 184 // to build trees
 185 inline Tree tree (const Node& n) { Tree br[1]; return CTree::make(n, 0, br); }
 186 inline Tree tree (const Node& n, const Tree& a) { Tree br[]= {a}; return CTree::make(n, 1, br); }
 187 inline Tree tree (const Node& n, const Tree& a, const Tree& b) { Tree br[]= {a,b}; return CTree::make(n, 2, br); }
 188 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); }
 189 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); }
 190
 191 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); }
 192
 193 // useful conversions
 194 int             tree2int (Tree t);              ///< if t has a node of type int, return it otherwise error
 195 double      tree2float (Tree t);    ///< if t has a node of type float, return it otherwise error
 196 double      tree2double (Tree t);    ///< if t has a node of type float, return it otherwise error
 197 const char* tree2str (Tree t);          ///< if t has a node of type symbol, return its name otherwise error
 198 void*           tree2ptr (Tree t);              ///< if t has a node of type ptr, return it otherwise error
 199 void*           getUserData(Tree t);    ///< if t has a node of type symbol, return the associated user data
 200
 201 // pattern matching
 202 bool isTree (const Tree& t, const Node& n);
 203 bool isTree (const Tree& t, const Node& n, Tree& a);
 204 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b);
 205 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c);
 206 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d);
 207 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d, Tree& e);
 208
 209 //printing
 210 inline ostream& operator << (ostream& s, const CTree& t) { return t.print(s); }
 211
 212
 213 //-----------------------------------------------------------------------------
 214 // recursive trees
 215 //-----------------------------------------------------------------------------
 216
 217 // creation a recursive trees
 218
 219 Tree rec(Tree body);                                            ///< create a de Bruijn recursive tree
 220 Tree rec(Tree id, Tree body);                           ///< create a symbolic recursive tree
 221
 222 bool isRec(Tree t, Tree& body);                         ///< is t a de Bruijn recursive tree
 223 bool isRec(Tree t, Tree& id, Tree& body);       ///< is t a symbolic recursive tree
 224
 225 // creation of recursive references
 226
 227 Tree ref(int level);                                            ///< create a de Bruijn recursive reference
 228 Tree ref(Tree id);                                                      ///< create a symbolic recursive reference
 229
 230 bool isRef(Tree t, int& level);                         ///< is t a de Bruijn recursive reference
 231 bool isRef(Tree t, Tree& id);                           ///< is t a symbolic recursive reference
 232
 233
 234 // Open vs Closed regarding de Bruijn references
 235
 236 inline bool isOpen(Tree t)       { return t->aperture() > 0; }  ///< t contains free de Bruijn references
 237 inline bool isClosed(Tree t) { return t->aperture() <= 0;}      ///< t dont contain free de Bruijn ref
 238
 239 // lift by 1 the free de Bruijn references
 240
 241 Tree lift(Tree t);                                                      ////< add 1 to the free de bruijn references of t
 242
 243 Tree deBruijn2Sym (Tree t);                                     ////< transform a tree from deBruijn to symbolic notation
 244 void updateAperture (Tree t);                           ////< update aperture field of a tree in symbolic notation
 245
 246 //---------------------------------------------------------------------------
 247
 248 class Tabber
 249 {
 250         int fIndent;
 251     int fPostInc;
 252   public:
 253     Tabber(int n=0) : fIndent(n), fPostInc(0)   {}
 254     Tabber& operator++()                        { fPostInc++; return *this;}
 255         Tabber& operator--()                    { assert(fIndent > 0); fIndent--; return *this; }
 256
 257         ostream& print (ostream& fout)
 258                         { for (int i=0; i<fIndent; i++) fout << '\t';  fIndent+=fPostInc; fPostInc=0; return fout; }
 259 };
 260
 261 //printing
 262 inline ostream& operator << (ostream& s, Tabber& t) { return t.print(s); }
 263
 264 extern Tabber TABBER;
 265
 266
 267 #endif