X-Git-Url: https://scm.cri.ensmp.fr/git/Faustine.git/blobdiff_plain/c7f552fd8888da2f0d8cfb228fe0f28d3df3a12c..b4b6f2ea75b9f0f3ca918f5b84016610bf7a4d4f:/interpretor/preprocessor/faust-0.9.47mr3/compiler/signals/recursivness.cpp

diff --git a/interpretor/preprocessor/faust-0.9.47mr3/compiler/signals/recursivness.cpp b/interpretor/preprocessor/faust-0.9.47mr3/compiler/signals/recursivness.cpp
new file mode 100644
index 0000000..c22b9cb
--- /dev/null
+++ b/interpretor/preprocessor/faust-0.9.47mr3/compiler/signals/recursivness.cpp
@@ -0,0 +1,184 @@
+/************************************************************************
+ ************************************************************************
+    FAUST compiler
+	Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale
+    ---------------------------------------------------------------------
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License
+    along with this program; if not, write to the Free Software
+    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ ************************************************************************
+ ************************************************************************/
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+#include "recursivness.hh"
+#include "property.hh"
+
+#include "signals.hh"
+#include "ppsig.hh"
+#include "set"
+
+using namespace std;
+
+
+/**
+ * @file recursivness.cpp
+ * Annotate a signal expression with recursivness information. Recursiveness
+ * indicates the amount of recursive dependencies of a signal. A closed signal
+ * has a recursivness of 0 because is has no recursive dependencies. This means
+ * that the succesive samples of this signal can be computed in parallel.
+ * In a signal of type \x.(...F(x)...), F(x) has a recursivness of 1. In a
+ * signal of type \x.(... \y.(...F(x)...G(y)...)...) F(x) has a recursivness of 2
+ * while G(y) has a recursivness of 1.
+ */
+
+//--------------------------------------------------------------------------
+static int annotate(Tree env, Tree sig);
+static int position (Tree env, Tree t, int p=1);
+
+Tree RECURSIVNESS = tree(symbol("RecursivnessProp"));
+//--------------------------------------------------------------------------
+
+
+/**
+ * Annotate a signal with recursivness. Should be used before
+ * calling getRecursivness
+ * @param sig signal to annotate
+ */
+void recursivnessAnnotation(Tree sig)
+{
+	annotate(nil, sig);
+}
+
+
+/**
+ * Return the recursivness of a previously
+ * annotated signal. An error is generated
+ * if the signal has no recursivness property
+ * @param sig signal
+ * @return recursivness of the signal
+ */
+int getRecursivness(Tree sig)
+{
+	Tree tr;
+	if ( ! getProperty(sig, RECURSIVNESS, tr)) {
+		cerr << "Error in getRecursivness of " << *sig << endl;
+		exit(1);
+	}
+	return tree2int(tr);
+}
+
+//-------------------------------------- IMPLEMENTATION ------------------------------------
+/**
+ * Annotate a signal with recursivness
+ * @param env the current environment
+ * @param sig signal to annotate
+ * @return recursivness of the signal
+ */
+static int annotate(Tree env, Tree sig)
+{
+	Tree tr, var, body;
+
+	if (getProperty(sig, RECURSIVNESS, tr)) {
+		return tree2int(tr);	// already annotated
+	} else if (isRec(sig, var, body)) {
+		int p = position(env, sig);
+		if (p > 0) {
+			return p;	// we are inside \x.(...)
+		} else {
+			int r = annotate(cons(sig, env), body) - 1;
+			if (r<0) r=0;
+			setProperty(sig, RECURSIVNESS, tree(r));
+			return r;
+		}
+	} else {
+		int rmax = 0;
+		vector<Tree> v; getSubSignals(sig, v);
+		for (unsigned int i=0; i<v.size(); i++) {
+			int r = annotate(env, v[i]);
+			if (r>rmax) rmax=r;
+		}
+		setProperty(sig, RECURSIVNESS, tree(rmax));
+		return rmax;
+	}
+}
+
+
+
+/**
+ * return the position of a signal in the current recursive environment
+ * @param env the current recursive environment of the signal
+ * @param t signal we want to know the position
+ * @return the position in the recursive environment
+ */
+static int position (Tree env, Tree t, int p)
+{
+	if (isNil(env)) return 0;	// was not in the environment
+	if (hd(env) == t) return p;
+	else return position (tl(env), t, p+1);
+}
+
+
+//-----------------------------------list recursive symbols-----------------------
+
+
+
+/**
+ * return the set of recursive symbols appearing in a signal.
+ * @param sig the signal to analyze
+ * @return the set of symbols
+ */
+
+// the property used to memoize the results
+property<Tree>  SymListProp;
+
+Tree    symlistVisit(Tree sig, set<Tree>& visited)
+{
+    Tree S;
+    if (SymListProp.get(sig, S)) {
+        return S;
+    } else if ( visited.count(sig) > 0 ){
+        return nil;
+    } else {
+        visited.insert(sig);
+        Tree id, body;
+        if (isRec(sig, id, body)) {
+            Tree U = singleton(sig);
+            for (int i=0; i<len(body); i++) {
+                U = setUnion(U, symlistVisit(nth(body,i), visited));
+            }
+            return U;
+        } else {
+            vector<Tree> subsigs;
+            int n = getSubSignals(sig, subsigs, true); // il faut visiter aussi les tables
+            Tree U = nil;
+            for (int i=0; i<n; i++) {
+                U = setUnion(U, symlistVisit(subsigs[i], visited));
+            }
+            return U;
+        }
+    }
+}
+
+Tree    symlist(Tree sig)
+{
+    Tree    S;
+    if (!SymListProp.get(sig, S)) {
+        set<Tree> visited;
+        S = symlistVisit(sig, visited);
+        SymListProp.set(sig, S);
+    }
+    //cerr << "SYMLIST " << *S << " OF " << ppsig(sig) << endl;
+    return S;
+}