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 #include <set>
26
27 #include "exception.hh"
28 #include "global.hh"
29 #include "ppsig.hh"
30 #include "property.hh"
31 #include "recursivness.hh"
32 #include "signals.hh"
33
34 using namespace std;
35
36 /**
37 * @file recursivness.cpp
38 * Annotate a signal expression with recursivness information. Recursiveness
39 * indicates the amount of recursive dependencies of a signal. A closed signal
40 * has a recursivness of 0 because is has no recursive dependencies. This means
41 * that the succesive samples of this signal can be computed in parallel.
42 * In a signal of type \x.(...F(x)...), F(x) has a recursivness of 1. In a
43 * signal of type \x.(... \y.(...F(x)...G(y)...)...) F(x) has a recursivness of 2
44 * while G(y) has a recursivness of 1.
45 */
46
47 //--------------------------------------------------------------------------
48 static int annotate(Tree env, Tree sig);
49 static int position(Tree env, Tree t, int p = 1);
50 //--------------------------------------------------------------------------
51
52 /**
53 * Annotate a signal with recursivness. Should be used before
54 * calling getRecursivness
55 * @param sig signal to annotate
56 */
recursivnessAnnotation(Tree sig)57 void recursivnessAnnotation(Tree sig)
58 {
59 annotate(gGlobal->nil, sig);
60 }
61
62 /**
63 * Return the recursivness of a previously
64 * annotated signal. An error is generated
65 * if the signal has no recursivness property
66 * @param sig signal
67 * @return recursivness of the signal
68 */
getRecursivness(Tree sig)69 int getRecursivness(Tree sig)
70 {
71 Tree tr;
72 if (!getProperty(sig, gGlobal->RECURSIVNESS, tr)) {
73 stringstream error;
74 error << "ERROR in getRecursivness of " << *sig << endl;
75 throw faustexception(error.str());
76 }
77 return tree2int(tr);
78 }
79
80 //-------------------------------------- IMPLEMENTATION ------------------------------------
81 /**
82 * Annotate a signal with recursivness
83 * @param env the current environment
84 * @param sig signal to annotate
85 * @return recursivness of the signal
86 */
annotate(Tree env,Tree sig)87 static int annotate(Tree env, Tree sig)
88 {
89 Tree tr, var, body;
90
91 if (getProperty(sig, gGlobal->RECURSIVNESS, tr)) {
92 return tree2int(tr); // already annotated
93 } else if (isRec(sig, var, body)) {
94 int p = position(env, sig);
95 if (p > 0) {
96 return p; // we are inside \x.(...)
97 } else {
98 int r = annotate(cons(sig, env), body) - 1;
99 if (r < 0) r = 0;
100 setProperty(sig, gGlobal->RECURSIVNESS, tree(r));
101 return r;
102 }
103 } else {
104 int rmax = 0;
105 vector<Tree> v;
106 getSubSignals(sig, v);
107 for (unsigned int i = 0; i < v.size(); i++) {
108 int r = annotate(env, v[i]);
109 if (r > rmax) rmax = r;
110 }
111 setProperty(sig, gGlobal->RECURSIVNESS, tree(rmax));
112 return rmax;
113 }
114 }
115
116 /**
117 * Return the position of a signal in the current recursive environment
118 * @param env the current recursive environment of the signal
119 * @param t signal we want to know the position
120 * @return the position in the recursive environment
121 */
position(Tree env,Tree t,int p)122 static int position(Tree env, Tree t, int p)
123 {
124 if (isNil(env)) return 0; // was not in the environment
125 if (hd(env) == t) {
126 return p;
127 } else {
128 return position(tl(env), t, p + 1);
129 }
130 }
131
132 //-----------------------------------list recursive symbols-----------------------
133
134 /**
135 * Return the set of recursive symbols appearing in a signal.
136 * @param sig the signal to analyze
137 * @return the set of symbols
138 */
139
symlistVisit(Tree sig,set<Tree> & visited)140 Tree symlistVisit(Tree sig, set<Tree>& visited)
141 {
142 Tree S;
143
144 if (gGlobal->gSymListProp->get(sig, S)) {
145 return S;
146 } else if (visited.count(sig) > 0) {
147 return gGlobal->nil;
148 } else {
149 visited.insert(sig);
150 Tree id, body;
151 if (isRec(sig, id, body)) {
152 Tree U = singleton(sig);
153 for (int i = 0; i < len(body); i++) {
154 U = setUnion(U, symlistVisit(nth(body, i), visited));
155 }
156 return U;
157 } else {
158 vector<Tree> subsigs;
159 int n = getSubSignals(sig, subsigs, true); // il faut visiter aussi les tables
160 Tree U = gGlobal->nil;
161 for (int i = 0; i < n; i++) {
162 U = setUnion(U, symlistVisit(subsigs[i], visited));
163 }
164 return U;
165 }
166 }
167 }
168
symlist(Tree sig)169 Tree symlist(Tree sig)
170 {
171 Tree S;
172
173 if (!gGlobal->gSymListProp->get(sig, S)) {
174 set<Tree> visited;
175 S = symlistVisit(sig, visited);
176 gGlobal->gSymListProp->set(sig, S);
177 }
178 // cerr << "SYMLIST " << *S << " OF " << ppsig(sig) << endl;
179 return S;
180 }
181