1 /************************************************************************
2 ************************************************************************
3 FAUST compiler
4 Copyright (C) 2003-2018 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 /** \file tree.hh
26 * A tree library with hashconsing and maximal sharing capabilities.
27 *
28 * A tree library with hashconsing and maximal sharing capabilities.
29 *
30 * <b>API:</b>
31 *
32 * \li tree (n) : tree of node n with no branch
33 * \li tree (n, t1) : tree of node n with a branch t
34 * \li tree (n, t1,...,tm) : tree of node n with m branches t1,...,tm
35 *
36 * <b>Useful conversions :</b>
37 *
38 * \li int tree2int (t) : if t has a node of type int, return it otherwise error
39 * \li float tree2float (t) : if t has a node of type float, return it otherwise error
40 * \li const char* tree2str (t) : if t has a node of type symbol, return its name otherwise error
41 * \li void* tree2ptr (t) : if t has a node of type ptr, return it otherwise error
42 *
43 * <b>Pattern matching :</b>
44 *
45 * \li if (isTree (t, n)) ... : t has node n and no branches;
46 * \li if (isTree (t, n, &t1) ... : t has node n and 1 branch, t1 is set accordingly;
47 * \li if (isTree (t, n, &t1...&tm)... : t has node n and m branches, ti's are set accordingly;
48 *
49 * <b>Accessors :</b>
50 *
51 * \li t->node() : the node of t { return fNode; }
52 * \li t->height() : lambda height such that H(x)=0, H(\x.e)=1+H(e), H(e*f)=max(H(e),H(f))
53 * \li t->arity() : the number of branches of t { return fArity; }
54 * \li t->branch(i) : the ith branch of t
55 *
56 * <b>Attributs :</b>
57 *
58 * \li t->attribut() : return the attribut (also a tree) of t
59 * \li t->attribut(t') : set the attribut of t to t'
60 *
61 *
62 * <b>Properties:</b>
63 *
64 * If p and q are two CTree pointers :
65 * p != q <=> *p != *q
66 *
67 **/
68
69 /*****************************************************************************
70 ******************************************************************************/
71
72 #ifndef __TREE__
73 #define __TREE__
74
75 #include <map>
76 #include <vector>
77
78 #include "exception.hh"
79 #include "garbageable.hh"
80 #include "node.hh"
81 #include "symbol.hh"
82
83 //---------------------------------API---------------------------------------
84
85 class CTree;
86 typedef CTree* Tree;
87
88 typedef map<Tree, Tree> plist;
89 typedef vector<Tree> tvec;
90
91 /**
92 * A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches.
93 * A CTree = (Node x [CTree]) is the association of a content Node and a list of subtrees
94 * called branches. In order to maximize the sharing of trees, hashconsing techniques are used.
95 * Ctrees at different addresses always have a different content. A first consequence of this
96 * approach is that a fast equality test on pointers can be used as an equality test on CTrees.
97 * A second consequence is that a CTree can NEVER be modified. But a property list is associated
98 * to each CTree that can be used to attach arbitrary information to it. Due to the maximal
99 * sharing property it is therefore easy to do memoization using these property lists.
100 *
101 * Means are also provided to do maximal sharing on recursive trees. The idea is to start from
102 * a deBruijn representation and progressively build a classical representation such that
103 * alpha-equivalent recursive CTrees are necesseraly identical (and therefore shared).
104 *
105 * WARNING : in the current implementation CTrees are allocated but never deleted
106 **/
107
108 class CTree : public virtual Garbageable {
109 private:
110 static const int kHashTableSize = 400009; ///< size of the hash table (prime number)
111 static size_t gSerialCounter; ///< the serial number counter
112 static Tree gHashTable[kHashTableSize]; ///< hash table used for "hash consing"
113
114 public:
115 static bool gDetails; ///< Ctree::print() print with more details when true
116 static unsigned int gVisitTime; ///< Should be incremented for each new visit to keep track of visited tree.
117
118 private:
119 // fields
120 Tree fNext; ///< next tree in the same hashtable entry
121 Node fNode; ///< the node content of the tree
122 void* fType; ///< the type of a tree
123 plist fProperties; ///< the properties list attached to the tree
124 size_t fHashKey; ///< the hashtable key
125 size_t fSerial; ///< the increasing serial number
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(size_t 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 size_t calcTreeHash(const Node& n,
134 const tvec& br); ///< compute the hash key of a tree according to its node and branches
135 static int calcTreeAperture(const Node& n, const tvec& br); ///< compute how open is a tree
136
137 public:
138 virtual ~CTree();
139
140 static Tree make(const Node& n, int ar, Tree br[]); ///< return a new tree or an existing equivalent one
141 static Tree make(const Node& n, const tvec& br); ///< return a new tree or an existing equivalent one
142
143 // Accessors
node() const144 const Node& node() const { return fNode; } ///< return the content of the tree
arity() const145 int arity() const { return (int)fBranch.size(); } ///< return the number of branches (subtrees) of a tree
branch(int i) const146 Tree branch(int i) const { return fBranch[i]; } ///< return the ith branch (subtree) of a tree
branches() const147 const tvec& branches() const { return fBranch; } ///< return all branches (subtrees) of a tree
hashkey() const148 size_t hashkey() const { return fHashKey; } ///< return the hashkey of the tree
serial() const149 size_t serial() const { return fSerial; } ///< return the serial of the tree
aperture() const150 int aperture() const { return fAperture; } ///< return how "open" is a tree in terms of free variables
setAperture(int a)151 void setAperture(int a) { fAperture = a; } ///< modify the aperture of a tree
152
153 // Print a tree and the hash table (for debugging purposes)
154 ostream& print(ostream& fout) const; ///< print recursively the content of a tree on a stream
155 static void control(); ///< print the hash table content (for debug purpose)
156
157 static void init();
158
159 // type information
setType(void * t)160 void setType(void* t) { fType = t; }
getType()161 void* getType() { return fType; }
162
163 // Keep track of visited trees (WARNING : non reentrant)
startNewVisit()164 static void startNewVisit() { ++gVisitTime; }
isAlreadyVisited()165 bool isAlreadyVisited() { return fVisitTime == gVisitTime; }
setVisited()166 void setVisited()
167 { /*faustassert(fVisitTime!=gVisitTime);*/
168 fVisitTime = gVisitTime;
169 }
170
171 // Property list of a tree
setProperty(Tree key,Tree value)172 void setProperty(Tree key, Tree value) { fProperties[key] = value; }
clearProperty(Tree key)173 void clearProperty(Tree key) { fProperties.erase(key); }
clearProperties()174 void clearProperties() { fProperties = plist(); }
175
176 void exportProperties(vector<Tree>& keys, vector<Tree>& values);
177
getProperty(Tree key)178 Tree getProperty(Tree key)
179 {
180 plist::iterator i = fProperties.find(key);
181 if (i == fProperties.end()) {
182 return 0;
183 } else {
184 return i->second;
185 }
186 }
187 };
188
189 //---------------------------------API---------------------------------------
190
191 // to build trees
tree(const Node & n)192 inline Tree tree(const Node& n)
193 {
194 Tree br[1];
195 return CTree::make(n, 0, br);
196 }
tree(const Node & n,const Tree & a)197 inline Tree tree(const Node& n, const Tree& a)
198 {
199 Tree br[] = {a};
200 return CTree::make(n, 1, br);
201 }
tree(const Node & n,const Tree & a,const Tree & b)202 inline Tree tree(const Node& n, const Tree& a, const Tree& b)
203 {
204 Tree br[] = {a, b};
205 return CTree::make(n, 2, br);
206 }
tree(const Node & n,const Tree & a,const Tree & b,const Tree & c)207 inline Tree tree(const Node& n, const Tree& a, const Tree& b, const Tree& c)
208 {
209 Tree br[] = {a, b, c};
210 return CTree::make(n, 3, br);
211 }
tree(const Node & n,const Tree & a,const Tree & b,const Tree & c,const Tree & d)212 inline Tree tree(const Node& n, const Tree& a, const Tree& b, const Tree& c, const Tree& d)
213 {
214 Tree br[] = {a, b, c, d};
215 return CTree::make(n, 4, br);
216 }
217
tree(const Node & n,const Tree & a,const Tree & b,const Tree & c,const Tree & d,const Tree & e)218 inline Tree tree(const Node& n, const Tree& a, const Tree& b, const Tree& c, const Tree& d, const Tree& e)
219 {
220 Tree br[] = {a, b, c, d, e};
221 return CTree::make(n, 5, br);
222 }
tree(const Node & n,const tvec & br)223 inline Tree tree(const Node& n, const tvec& br)
224 {
225 return CTree::make(n, br);
226 }
227
228 // useful conversions
229 int tree2int(Tree t); ///< if t has a node of type int, return it otherwise error
230 double tree2float(Tree t); ///< if t has a node of type float, return it otherwise error
231 double tree2double(Tree t); ///< if t has a node of type float, return it otherwise error
232 const char* tree2str(Tree t); ///< if t has a node of type symbol, return its name otherwise error
233 string tree2quotedstr(Tree t);
234 void* tree2ptr(Tree t); ///< if t has a node of type ptr, return it otherwise error
235 void* getUserData(Tree t); ///< if t has a node of type symbol, return the associated user data
236
237 // pattern matching
238 bool isTree(const Tree& t, const Node& n);
239 bool isTree(const Tree& t, const Node& n, Tree& a);
240 bool isTree(const Tree& t, const Node& n, Tree& a, Tree& b);
241 bool isTree(const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c);
242 bool isTree(const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d);
243 bool isTree(const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d, Tree& e);
244
245 // printing
operator <<(ostream & s,const CTree & t)246 inline ostream& operator<<(ostream& s, const CTree& t)
247 {
248 return t.print(s);
249 }
250
251 //-----------------------------------------------------------------------------
252 // recursive trees
253 //-----------------------------------------------------------------------------
254
255 // creation a recursive trees
256
257 Tree rec(Tree body); ///< create a de Bruijn recursive tree
258 Tree rec(Tree id, Tree body); ///< create a symbolic recursive tree
259
260 bool isRec(Tree t, Tree& body); ///< is t a de Bruijn recursive tree
261 bool isRec(Tree t, Tree& id, Tree& body); ///< is t a symbolic recursive tree
262
263 // creation of recursive references
264
265 Tree ref(int level); ///< create a de Bruijn recursive reference
266 Tree ref(Tree id); ///< create a symbolic recursive reference
267
268 bool isRef(Tree t, int& level); ///< is t a de Bruijn recursive reference
269 bool isRef(Tree t, Tree& id); ///< is t a symbolic recursive reference
270
271 // Open vs Closed regarding de Bruijn references
272
isOpen(Tree t)273 inline bool isOpen(Tree t)
274 {
275 return t->aperture() > 0;
276 } ///< t contains free de Bruijn references
isClosed(Tree t)277 inline bool isClosed(Tree t)
278 {
279 return t->aperture() <= 0;
280 } ///< t dont contain free de Bruijn ref
281
282 // lift by 1 the free de Bruijn references
283
284 Tree lift(Tree t); ////< add 1 to the free de bruijn references of t
285
286 Tree deBruijn2Sym(Tree t); ////< transform a tree from deBruijn to symbolic notation
287
288 //---------------------------------------------------------------------------
289
290 class Tabber {
291 int fIndent;
292 int fPostInc;
293
294 public:
Tabber(int n=0)295 Tabber(int n = 0) : fIndent(n), fPostInc(0) {}
operator ++()296 Tabber& operator++()
297 {
298 fPostInc++;
299 return *this;
300 }
operator --()301 Tabber& operator--()
302 {
303 faustassert(fIndent > 0);
304 fIndent--;
305 return *this;
306 }
307
print(ostream & fout)308 ostream& print(ostream& fout)
309 {
310 for (int i = 0; i < fIndent; i++) fout << '\t';
311 fIndent += fPostInc;
312 fPostInc = 0;
313 return fout;
314 }
315 };
316
317 // printing
operator <<(ostream & s,Tabber & t)318 inline ostream& operator<<(ostream& s, Tabber& t)
319 {
320 return t.print(s);
321 }
322
323 #endif
324