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 #include <limits.h>
23 #include <stdio.h>
24 #include <stdlib.h>
25
26 #include "exception.hh"
27 #include "global.hh"
28 #include "tlib.hh"
29
30 // Declaration of implementation
31 static Tree calcDeBruijn2Sym(Tree t);
32 static Tree substitute(Tree t, int n, Tree id);
33 static Tree calcsubstitute(Tree t, int level, Tree id);
34 Tree liftn(Tree t, int threshold);
35 static Tree calcliftn(Tree t, int threshold);
36
37 // Tree NOVAR = tree("NOVAR");
38
39 //-----------------------------------------------------------------------------------------
40 // rec, isRec : declare recursive trees
41 //-----------------------------------------------------------------------------------------
42
43 // de Bruijn declaration of a recursive tree
rec(Tree body)44 Tree rec(Tree body)
45 {
46 return tree(gGlobal->DEBRUIJN, body);
47 }
48
isRec(Tree t,Tree & body)49 bool isRec(Tree t, Tree& body)
50 {
51 return isTree(t, gGlobal->DEBRUIJN, body);
52 }
53
ref(int level)54 Tree ref(int level)
55 {
56 faustassert(level > 0);
57 return tree(gGlobal->DEBRUIJNREF, tree(level)); // reference to enclosing recursive tree starting from 1
58 }
59
isRef(Tree t,int & level)60 bool isRef(Tree t, int& level)
61 {
62 Tree u;
63
64 if (isTree(t, gGlobal->DEBRUIJNREF, u)) {
65 return isInt(u->node(), &level);
66 } else {
67 return false;
68 }
69 }
70
71 //-----------------------------------------------------------------------------------------
72 // Recursive tree in symbolic notation (using a recursive definition property)
73 //-----------------------------------------------------------------------------------------
74
75 // declaration of a recursive tree using a symbolic variable
rec(Tree var,Tree body)76 Tree rec(Tree var, Tree body)
77 {
78 Tree t = tree(gGlobal->SYMREC, var);
79 t->setProperty(gGlobal->RECDEF, body);
80 return t;
81 }
82
isRec(Tree t,Tree & var,Tree & body)83 bool isRec(Tree t, Tree& var, Tree& body)
84 {
85 if (isTree(t, gGlobal->SYMREC, var)) {
86 body = t->getProperty(gGlobal->RECDEF);
87 return true;
88 } else {
89 return false;
90 }
91 }
92
ref(Tree id)93 Tree ref(Tree id)
94 {
95 return tree(gGlobal->SYMREC, id); // reference to a symbolic id
96 }
97
isRef(Tree t,Tree & v)98 bool isRef(Tree t, Tree& v)
99 {
100 return isTree(t, gGlobal->SYMREC, v);
101 }
102
103 //-----------------------------------------------------------------------------------------
104 // L'aperture d'un arbre est la plus profonde reference de Bruijn qu'il contienne.
105 // Les references symboliques compte pour zero ce qui veut dire qu'un arbre d'aperture
106 // 0 ne compte aucun reference de bruijn libres.
107
calcTreeAperture(const Node & n,const tvec & br)108 int CTree::calcTreeAperture(const Node& n, const tvec& br)
109 {
110 int x;
111 if (n == gGlobal->DEBRUIJNREF) {
112 faustassert(br[0]);
113 if (isInt(br[0]->node(), &x)) {
114 return x;
115 } else {
116 return 0;
117 }
118
119 } else if (n == gGlobal->DEBRUIJN) {
120 faustassert(br[0]);
121 return br[0]->fAperture - 1;
122
123 } else {
124 // return max aperture of branches
125 int rc = 0;
126 tvec::const_iterator b = br.begin();
127 tvec::const_iterator z = br.end();
128 while (b != z) {
129 if ((*b)->aperture() > rc) rc = (*b)->aperture();
130 ++b;
131 }
132 return rc;
133 }
134 }
135
lift(Tree t)136 Tree lift(Tree t)
137 {
138 return liftn(t, 1);
139 }
140
141 void printSignal(Tree sig, FILE* out, int prec = 0);
142
143 // lift (t) : increase free references by 1
144
145 #if 0
146 static Tree _liftn(Tree t, int threshold);
147
148 Tree liftn(Tree t, int threshold)
149 {
150 fprintf(stderr, "call of liftn("); printSignal(t, stderr); fprintf(stderr, ", %d)\n", threshold);
151 Tree r = _liftn(t, threshold);
152 fprintf(stderr, "return of liftn("); printSignal(t, stderr); fprintf(stderr, ", %d) -> ", threshold);
153 printSignal(r, stderr); fprintf(stderr, "\n");
154 return r;
155 }
156 #endif
157
liftn(Tree t,int threshold)158 Tree liftn(Tree t, int threshold)
159 {
160 Tree L = tree(Node(gGlobal->SYMLIFTN), tree(Node(threshold)));
161 Tree t2 = t->getProperty(L);
162
163 if (!t2) {
164 t2 = calcliftn(t, threshold);
165 t->setProperty(L, t2);
166 }
167 return t2;
168 }
169
calcliftn(Tree t,int threshold)170 static Tree calcliftn(Tree t, int threshold)
171 {
172 int n;
173 Tree u;
174
175 if (isClosed(t)) {
176 return t;
177
178 } else if (isRef(t, n)) {
179 if (n < threshold) {
180 // it is a bounded reference
181 return t;
182 } else {
183 // it is a free reference
184 return ref(n + 1);
185 }
186
187 } else if (isRec(t, u)) {
188 return rec(liftn(u, threshold + 1));
189
190 } else {
191 int n1 = t->arity();
192 // Tree br[4];
193 tvec br(n1);
194 for (int i = 0; i < n1; i++) {
195 br[i] = liftn(t->branch(i), threshold);
196 }
197 // return CTree::make(t->node(), n, br);
198 return CTree::make(t->node(), br);
199 }
200 }
201
202 //-----------------------------------------------------------
203 // Transform a tree from deBruijn to symbolic representation
204 //-----------------------------------------------------------
205
deBruijn2Sym(Tree t)206 Tree deBruijn2Sym(Tree t)
207 {
208 faustassert(isClosed(t));
209 Tree t2 = t->getProperty(gGlobal->DEBRUIJN2SYM);
210
211 if (!t2) {
212 t2 = calcDeBruijn2Sym(t);
213 t->setProperty(gGlobal->DEBRUIJN2SYM, t2);
214 }
215 return t2;
216 }
217
calcDeBruijn2Sym(Tree t)218 static Tree calcDeBruijn2Sym(Tree t)
219 {
220 Tree body, var;
221 int i;
222
223 if (isRec(t, body)) {
224 var = tree(unique("W"));
225 return rec(var, deBruijn2Sym(substitute(body, 1, ref(var))));
226
227 } else if (isRef(t, var)) {
228 return t;
229
230 } else if (isRef(t, i)) {
231 throw faustexception("ERROR : one Bruijn reference found !\n");
232 return t;
233
234 } else {
235 // Tree br[4];
236 int a = t->arity();
237 tvec br(a);
238
239 for (int i1 = 0; i1 < a; i1++) {
240 br[i1] = deBruijn2Sym(t->branch(i1));
241 }
242 // return CTree::make(t->node(), a, br);
243 return CTree::make(t->node(), br);
244 }
245 }
246
substitute(Tree t,int level,Tree id)247 static Tree substitute(Tree t, int level, Tree id)
248 {
249 Tree S = tree(Node(gGlobal->SUBSTITUTE), tree(Node(level)), id);
250 Tree t2 = t->getProperty(S);
251
252 if (!t2) {
253 t2 = calcsubstitute(t, level, id);
254 t->setProperty(S, t2);
255 }
256 return t2;
257 }
258
calcsubstitute(Tree t,int level,Tree id)259 static Tree calcsubstitute(Tree t, int level, Tree id)
260 {
261 int l;
262 Tree body;
263
264 if (t->aperture() < level) {
265 // fprintf(stderr, "aperture %d < level %d !!\n", t->aperture(), level);
266 return t;
267 }
268 if (isRef(t, l)) return (l == level) ? id : t;
269 if (isRec(t, body)) return rec(substitute(body, level + 1, id));
270
271 int ar = t->arity();
272 // Tree br[4];
273 tvec br(ar);
274 for (int i = 0; i < ar; i++) {
275 br[i] = substitute(t->branch(i), level, id);
276 }
277 // return CTree::make(t->node(), ar, br);
278 return CTree::make(t->node(), br);
279 }
280