recursivness.cpp

Go to the documentation of this file.

/************************************************************************
 ************************************************************************
    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;


//--------------------------------------------------------------------------
static int annotate(Tree env, Tree sig);
static int position (Tree env, Tree t, int p=1);

Tree RECURSIVNESS = tree(symbol("RecursivnessProp"));
//--------------------------------------------------------------------------


void recursivnessAnnotation(Tree sig)
{
    annotate(nil, sig);
}


int getRecursivness(Tree sig)
{
    Tree tr;
    if ( ! getProperty(sig, RECURSIVNESS, tr)) {
        cerr << "Error in getRecursivness of " << *sig << endl;
        exit(1);
    }
    return tree2int(tr);
}

//-------------------------------------- IMPLEMENTATION ------------------------------------
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;
    }
}



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-----------------------



// 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;
}