Erosion and dilasion by square successfully tested.
[Faustine.git] / interpretor / faust-0.9.47mr3 / compiler / tlib / 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