-
-/* compiler/patternmatcher/patternmatcher.cpp: implementation of the Faust
- rewriting engine */
-
-#include "tlib.hh"
-#include "list.hh"
-#include "boxes.hh"
-#include "ppbox.hh"
-#include "eval.hh"
-#include "patternmatcher.hh"
-
-using namespace std;
-#include <vector>
-#include <list>
-#include <set>
-#include <utility>
-
-/* Uncomment for debugging output. */
-//#define DEBUG
-
-/* Additional Tree deconstruction operations. */
-
-/* Check for cons (nonempty list) nodes. */
-
-static inline bool isCons(Tree x, Tree& h, Tree& t)
-{
- if (isList(x)) {
- h = hd(x); t = tl(x);
- return true;
- } else
- return false;
-}
-
-/* Deconstruct a (BDA) op pattern (YO). */
-
-static inline bool isBoxPatternOp(Tree box, Node& n, Tree& t1, Tree& t2)
-{
- if ( isBoxPar(box, t1, t2) ||
- isBoxSeq(box, t1, t2) ||
- isBoxSplit(box, t1, t2) ||
- isBoxMerge(box, t1, t2) ||
- isBoxHGroup(box, t1, t2) ||
- isBoxVGroup(box, t1, t2) ||
- isBoxTGroup(box, t1, t2) ||
- isBoxRec(box, t1, t2) )
- {
- n = box->node();
- return true;
- } else {
- return false;
- }
-}
-
-/* TA data structures. */
-
-/* subterm paths */
-
-typedef vector<int> Path;
-
-/* Subterm at given path in given term tree. */
-
-static Tree subtree(Tree X, int i, const Path& p)
-{
- int n = p.size();
- Node op(0);
- Tree x0, x1;
- if (i < n && isBoxPatternOp(X, op, x0, x1))
- return subtree((p[i]==0)?x0:x1, i+1, p);
- else
- return X;
-}
-
-/* rule markers */
-
-struct Rule {
- int r; // rule number
- Tree id; // matched variable (NULL if none)
- Path p; // subterm path indicating where variable value is found
-
- Rule(int _r, Tree _id) : r(_r), id(_id), p(Path()) {}
- Rule(int _r, Tree _id, const Path& _p) : r(_r), id(_id), p(_p) {}
- Rule(const Rule& rule) : r(rule.r), id(rule.id), p(rule.p) {}
-
- Rule& operator = (const Rule& rule)
- { r = rule.r; id = rule.id; p = rule.p; return *this; }
-
- bool operator == (const Rule& rule) const
- { return r == rule.r; }
- bool operator < (const Rule& rule) const
- { return r < rule.r; }
-
-#ifdef DEBUG
- ostream& print(ostream& fout) const;
-#endif
-};
-
-struct State;
-
-/* transitions */
-
-struct Trans {
- Tree x; // symbol or constant (NULL for variable)
- Node n; // operator symbol (if arity>0)
- int arity; // symbol arity
- State *state; // successor state
-
- Trans(Tree _x);
- Trans(const Node& _n, int _arity);
- Trans(const Trans& trans);
- ~Trans();
-
- Trans& operator = (const Trans& trans);
-
- bool is_var_trans() const { return arity == 0 && x == NULL; }
- bool is_cst_trans(Tree &_x) const { _x = x; return arity == 0 && x != NULL; }
- bool is_op_trans(Node &_n) const { _n = n; return arity > 0; }
-
- bool operator == (const Trans& trans) const
- { return arity == trans.arity && x == trans.x && n == trans.n; }
- bool operator < (const Trans& trans) const
- { return (arity < trans.arity) ? 1 :
- (arity > trans.arity) ? 0 :
- (arity == 0) ? (x < trans.x) :
- (n.getSym() < trans.n.getSym()); }
-
-#ifdef DEBUG
- ostream& print(ostream& fout) const;
-#endif
-};
-
-/* states */
-
-struct State {
- int s; // state number
- bool match_num; // whether state has a transition on a numeric constant
- list<Rule> rules; // rule markers
- list<Trans> trans; // transitions (1st transition is on variable if available)
- State() :
- s(0), match_num(false), rules(list<Rule>()), trans(list<Trans>()) {}
- State(const State& state) :
- s(state.s), match_num(state.match_num),
- rules(state.rules), trans(state.trans) {}
-
- State& operator = (const State& state)
- { s = state.s; match_num = state.match_num;
- rules = state.rules; trans = state.trans;
- return *this;
- }
-
-#ifdef DEBUG
- ostream& print(ostream& fout) const;
-#endif
-};
-
-// these need to come here so that the storage size of struct State is known
-
-Trans::Trans(Tree _x) :
- x(_x), n(0), arity(0), state(new State)
-{
-}
-
-Trans::Trans(const Node& _n, int _arity) :
- x(NULL), n(_n), arity(_arity), state(new State)
-{
-}
-
-Trans::Trans(const Trans& trans) :
- x(trans.x), n(trans.n), arity(trans.arity)
-{
- state = new State(*trans.state);
-}
-
-Trans::~Trans()
-{
- delete state;
-}
-
-Trans& Trans::operator = (const Trans& trans)
-{
- x = trans.x; n = trans.n; arity = trans.arity;
- state = new State(*trans.state);
- return *this;
-}
-
-/* the automaton */
-
-struct Automaton {
- vector<State*> state;
- vector<Tree> rhs;
-
- Automaton() : state(vector<State*>()), rhs(vector<Tree>()), s(0) {}
-
- // number of rules
- int n_rules() { return rhs.size(); }
- // markers of rules still active in state s
- const list<Rule>& rules(int s) { return state[s]->rules; }
- // transitions in state s
- const list<Trans>& trans(int s) { return state[s]->trans; }
- // is s a final state?
- bool final(int s) { return trans(s).empty(); }
-
- // assign state numbers and build the state table
- int s;
- void build(State *st);
-
-#ifdef DEBUG
- ostream& print(ostream& fout) const;
-#endif
-};
-
-void Automaton::build(State *st)
-{
- state.push_back(st);
- st->s = s++;
- list<Trans>::const_iterator t;
- for (t = st->trans.begin(); t != st->trans.end(); t++) {
- Tree x;
- double f;
- int i;
- if (t->is_cst_trans(x) &&
- (isBoxInt(x, &i) || isBoxReal(x, &f)))
- st->match_num = true;
- build(t->state);
- }
-}
-
-/* Debugging output. */
-
-#ifdef DEBUG
-inline ostream& operator << (ostream& s, const Rule& x)
-{ return x.print(s); }
-inline ostream& operator << (ostream& s, const Trans& x)
-{ return x.print(s); }
-inline ostream& operator << (ostream& s, const State& x)
-{ return x.print(s); }
-inline ostream& operator << (ostream& s, const Automaton& x)
-{ return x.print(s); }
-
-ostream& Rule::print(ostream& fout) const
-{
- if (id != NULL)
- fout << "#" << r << "(" << *id << ")";
- else
- fout << "#" << r;
- return fout;
-}
-
-ostream& Trans::print(ostream& fout) const
-{
- if (arity > 0)
- fout << "\top " << n << ": state " << state->s << endl;
- else if (x == NULL)
- fout << "\tvar _: state " << state->s << endl;
- else
- fout << "\tcst " << *x << ": state " << state->s << endl;
- return fout;
-}
-
-ostream& State::print(ostream& fout) const
-{
- fout << "state " << s << ":";
- list<Rule>::const_iterator r;
- for (r = rules.begin(); r != rules.end(); r++)
- fout << " " << *r;
- fout << endl;
- list<Trans>::const_iterator t;
- for (t = trans.begin(); t != trans.end(); t++)
- fout << *t;
- return fout;
-}
-
-ostream& Automaton::print(ostream& fout) const
-{
- int i, n = rhs.size();
- for (i = 0; i < n; i++)
- fout << "rule #" << i << ": " << *rhs[i] << endl;
- n = state.size();
- for (i = 0; i < n; i++)
- fout << *state[i];
- return fout;
-}
-#endif
-
-/* Construction algorithm for the pattern matching automaton.
- *
- * We employ the incremental technique described in Graef: Left-To-Right Tree
- * Pattern Matching, Proc. RTA 1991, Springer 1991 (LNCS 488) to construct a
- * tree automaton (TA) for the given patterns. The basic outline of the
- * technique is as follows. Initially, the automaton is empty. From each
- * pattern we produce a trie (considering the pattern as a string of variable
- * and function symbols and constants). This trie is then merged with the TA
- * obtained so far. The latter process is similar to merging two deterministic
- * finite automata, but it also takes into account the variables (see the
- * merge_state() routine below).
- */
-
-/* Construct a trie from a term tree. Takes the "start" and returns the "end"
- state of the (sub-)trie. */
-
-static State *make_state(State *state, int r, Tree x, Path& p)
-{
- Tree id, x0, x1;
- Node op(0);
- if (isBoxPatternVar(x, id)) {
- /* variable */
- Rule rule(r, id, p);
- state->rules.push_back(rule);
- Trans trans(NULL);
- state->trans.push_back(trans);
- return state->trans.begin()->state;
- } else if (isBoxPatternOp(x, op, x0, x1)) {
- /* composite pattern */
- Rule rule(r, NULL);
- state->rules.push_back(rule);
- Trans trans(op, 2);
- state->trans.push_back(trans);
- State *next = state->trans.begin()->state;
- p.push_back(0);
- next = make_state(next, r, x0, p);
- p.pop_back();
- p.push_back(1);
- next = make_state(next, r, x1, p);
- p.pop_back();
- return next;
- } else {
- /* constant */
- Rule rule(r, NULL);
- state->rules.push_back(rule);
- Trans trans(x);
- state->trans.push_back(trans);
- return state->trans.begin()->state;
- }
-}
-
-/* Take a copy of a state and prefix it with n variable transitions. */
-
-static State *make_var_state(int n, State *state)
-{
- if (n <= 0)
- return new State(*state);
- list<Rule>rules = state->rules;
- list<Rule>::iterator r;
- for (r = rules.begin(); r != rules.end(); r++) {
- r->id = NULL; r->p = Path();
- }
- State *prefix = new State, *current = prefix;
- while (n-- > 0) {
- current->rules = rules;
- Trans trans(NULL);
- current->trans.push_back(trans);
- current = current->trans.begin()->state;
- }
- *current = *state;
- return prefix;
-}
-
-/* Merge two tree automata. Merges the tree automaton rooted at state2 into
- the automaton rooted at state1. We assume that state2 is in "trie" form,
- i.e., each state has at most one transition, which is always guaranteed
- here and simplifies the algorithm. */
-
-static void merge_state(State *state1, State *state2);
-
-static void inline merge_rules(list<Rule>& rules1, list<Rule>& rules2)
-{
- list<Rule> cprules2 = rules2;
- rules1.merge(cprules2);
-}
-
-static void merge_trans_var(list<Trans>& trans, State *state)
-{
- if (!trans.begin()->is_var_trans()) {
- /* If we don't have a variable transition in this state yet then create a
- new one. */
- Trans tr(NULL);
- trans.push_front(tr);
- }
- list<Trans>::const_iterator t;
- Tree x;
- Node op(0);
- for (t = trans.begin(); t != trans.end(); t++) {
- if (t->is_var_trans())
- merge_state(t->state, state);
- else if (t->is_cst_trans(x)) {
- /* add the completion of the given state for a constant */
- merge_state(t->state, state);
- } else if (t->is_op_trans(op)) {
- /* add the completion of the given state for an arity>0 op */
- State *state1 = make_var_state(t->arity, state);
- merge_state(t->state, state1);
- delete state1;
- }
- }
-}
-
-static void merge_trans_cst(list<Trans>& trans, Tree x, State *state)
-{
- list<Trans>::iterator t0 = trans.begin(), t1 = t0, t;
- Tree x1;
- if (t0->is_var_trans()) t1++;
- for (t = t1; t != trans.end(); t++) {
- if (t->is_cst_trans(x1)) {
- if (x == x1) {
- merge_state(t->state, state);
- return;
- } else if (x < x1)
- break;
- }
- }
- /* no matching transition has been found; add a new one */
- Trans tr(x);
- trans.insert(t, tr); t--;
- State *state1 = t->state;
- *state1 = *state;
- if (t1 != t0) {
- /* if we have a variable transition in the current state, we also need to
- merge its completion for the current symbol/constant */
- merge_state(state1, t0->state);
- }
-}
-
-static void merge_trans_op(list<Trans>& trans, const Node& op,
- int arity, State *state)
-{
- /* analogous to merge_trans_cst above, but handles the arity>0 case */
- list<Trans>::iterator t0 = trans.begin(), t1 = t0, t;
- Node op1(0);
- if (t0->is_var_trans()) t1++;
- for (t = t1; t != trans.end(); t++) {
- if (t->is_op_trans(op1)) {
- if (op == op1) {
- merge_state(t->state, state);
- return;
- } else if (op.getSym() < op1.getSym())
- break;
- }
- }
- Trans tr(op, arity);
- trans.insert(t, tr); t--;
- State *state1 = t->state;
- *state1 = *state;
- if (t1 != t0) {
- State *state2 = make_var_state(arity, t0->state);
- merge_state(state1, state2);
- delete state2;
- }
-}
-
-static void merge_trans(list<Trans>& trans1, list<Trans>& trans2)
-{
- Tree x;
- Node op(0);
- if (trans2.empty())
- ;
- else if (trans1.empty()) {
- list<Trans> cptrans2 = trans2;
- /* append a copy of trans2 to trans1 */
- trans1.splice(trans1.end(), cptrans2);
- } else if (trans2.begin()->is_var_trans())
- /* merge a variable transition */
- merge_trans_var(trans1, trans2.begin()->state);
- else if (trans2.begin()->is_cst_trans(x))
- /* merge a constant transition */
- merge_trans_cst(trans1, x, trans2.begin()->state);
- else if (trans2.begin()->is_op_trans(op))
- /* merge a BDA op transition */
- merge_trans_op(trans1, op, trans2.begin()->arity, trans2.begin()->state);
-}
-
-static void merge_state(State *state1, State *state2)
-{
- merge_rules(state1->rules, state2->rules);
- merge_trans(state1->trans, state2->trans);
-}
-
-/* Take the rules of a BoxCase expression and return a pointer to the
- corresponding TA automaton (interface operation). */
-
-Automaton *make_pattern_matcher(Tree R)
-/* Tree R encodes the rules of a case box expressions as a Tree object, as
- follows:
-
- Rules ::= cons Rule (cons Rule ... nil)
- Rule ::= cons Lhs Rhs
- Lhs ::= cons Pattern (cons Pattern ... nil)
- Pattern ::= Tree (parameter pattern)
- Rhs ::= Tree
-
- NOTE: The lists of rules and patterns are actually delivered in reverse
- order by the parser, so we have to reverse them on the fly. */
-{
- Automaton *A = new Automaton;
- int n = len(R), r = n;
- State *start = new State;
- Tree rule, rest;
- vector<Tree> rules(n, (Tree)NULL);
- vector< vector<Tree> > testpats(n);
- while (isCons(R, rule, rest)) {
- rules[--r] = rule;
- R = rest;
- }
- for (r = 0; r < n; r++) {
- Tree lhs, rhs;
- if (isCons(rules[r], lhs, rhs)) {
- Tree pat, rest;
- int m = len(lhs), i = m;
- vector<Tree> pats(len(lhs), (Tree)NULL);
- State *state0 = new State, *state = state0;
- A->rhs.push_back(rhs);
- while (isCons(lhs, pat, rest)) {
- pats[--i] = pat;
- lhs = rest;
- }
- testpats[r] = pats;
- for (i = 0; i < m; i++) {
- Path p;
- state = make_state(state, r, pats[i], p);
- }
- Rule rule(r, NULL);
- state->rules.push_back(rule);
- merge_state(start, state0);
- delete state0;
- }
- }
- A->build(start);
- /* Check for shadowed rules. Note that because of potential nonlinearities
- it is *not* enough to just check the rule lists of final states and
- determine whether they have multiple matched rules. */
- for (r = 0; r < n; r++) {
- int s = 0, m = testpats[r].size();
- Tree C;
- vector<Tree> E(n, nil);
- /* try to match the lhs of rule #r */
- for (int i = 0; i < m; i++) {
- s = apply_pattern_matcher(A, s, testpats[r][i], C, E);
- if (s < 0) break;
- }
- if (A->final(s)) {
- list<Rule>::const_iterator ru;
- for (ru = A->rules(s).begin(); ru != A->rules(s).end(); ru++)
- if (!isBoxError(E[ru->r]))
- if (ru->r < r) {
- /* Lhs of rule #r matched a higher-priority rule, so rule #r may
- be shadowed. */
- Tree lhs1, rhs1, lhs2, rhs2;
- if (isCons(rules[ru->r], lhs1, rhs1) && isCons(rules[r], lhs2, rhs2)) {
- cerr << "WARNING : shadowed pattern-matching rule: "
- << boxpp(reverse(lhs2)) << " => " << boxpp(rhs2) << ";"
- << " previous rule was: "
- << boxpp(reverse(lhs1)) << " => " << boxpp(rhs1) << ";"
- << endl;
- } else {
- cerr << "INTERNAL ERROR : " << __FILE__ << ":" << __LINE__ << endl;
- exit(1);
- }
- } else if (ru->r >= r)
- break;
- }
- }
-#ifdef DEBUG
- cerr << "automaton " << A << endl << *A << "end automaton" << endl;
-#endif
- return A;
-}
-
-/* Helper type to represent variable substitutions which are recorded during
- matching. Each variable is associated with the path pointing at the subterm
- of the argument where the substitution of the matched variable is to be
- found. */
-
-struct Assoc {
- Tree id;
- Path p;
- Assoc(Tree _id, const Path& _p) : id(_id), p(_p) {}
-};
-typedef list<Assoc> Subst;
-
-/* add all substitutions for a given state */
-
-static void add_subst(vector<Subst>& subst, Automaton *A, int s)
-{
- list<Rule> rules = A->rules(s);
- list<Rule>::const_iterator r;
- for (r = rules.begin(); r != rules.end(); r++)
- if (r->id != NULL)
- subst[r->r].push_back(Assoc(r->id, r->p));
-}
-
-/* Process a given term tree X starting from state s, modify variable
- substitutions accordingly. Returns the resulting state, or -1 if no
- match. This does all the grunt work of matching. */
-
-static int apply_pattern_matcher_internal(Automaton *A, int s, Tree X,
- vector<Subst>& subst)
-{
- /* FIXME: rewrite this non-recursively? */
- if (s >= 0) {
- list<Trans>::const_iterator t;
- if (A->state[s]->match_num)
- /* simplify possible numeric argument on the fly */
- X = simplifyPattern(X);
- /* first check for applicable non-variable transitions */
- for (t = A->trans(s).begin(); t != A->trans(s).end(); t++) {
- Tree x;
- Node op(0), op1(0);
- if (t->is_var_trans())
- continue;
- else if (t->is_cst_trans(x)) {
- if (X==x) {
- /* transition on constant */
-#ifdef DEBUG
- cerr << "state " << s << ", " << *x << ": goto state " << t->state->s << endl;
-#endif
- add_subst(subst, A, s);
- s = t->state->s;
- return s;
- }
- } else if (t->is_op_trans(op)) {
- Tree x0, x1;
- if (isBoxPatternOp(X, op1, x0, x1) && op == op1) {
- /* transition on operation symbol */
-#ifdef DEBUG
- cerr << "state " << s << ", " << op << ": goto state " << t->state->s << endl;
-#endif
- add_subst(subst, A, s);
- s = t->state->s;
- if (s >= 0)
- s = apply_pattern_matcher_internal(A, s, x0, subst);
- if (s >= 0)
- s = apply_pattern_matcher_internal(A, s, x1, subst);
- return s;
- }
- }
- }
- /* check for variable transition (is always first in the list of
- transitions) */
- t = A->trans(s).begin();
- if (t->is_var_trans()) {
-#ifdef DEBUG
- cerr << "state " << s << ", _: goto state " << t->state->s << endl;
-#endif
- add_subst(subst, A, s);
- s = t->state->s;
- } else {
-#ifdef DEBUG
- cerr << "state " << s << ", *** match failed ***" << endl;
-#endif
- s = -1;
- }
- }
- return s;
-}
-
-/* Apply the pattern matcher to a single argument, starting from a given state
- (interface operation). Returns the resulting state, modifies the variable
- bindings E accordingly, and sets C to the resulting closure if a final
- state is reached. Result will be -1 to indicate a matching failure, and C
- will be set to nil if no final state has been reached yet. */
-
-int apply_pattern_matcher(Automaton *A, // automaton
- int s, // start state
- Tree X, // arg to be matched
- Tree& C, // output closure (if any)
- vector<Tree>& E) // modified output environments
-{
- int n = A->n_rules();
- vector<Subst> subst(n, Subst());
- /* perform matching, record variable substitutions */
-#ifdef DEBUG
- cerr << "automaton " << A << ", state " << s << ", start match on arg: " << *X << endl;
-#endif
- s = apply_pattern_matcher_internal(A, s, X, subst);
- C = nil;
- if (s < 0)
- /* failed match */
- return s;
- /* process variable substitutions */
- list<Rule>::const_iterator r;
- for (r = A->rules(s).begin(); r != A->rules(s).end(); r++) {
- // all rules still active in state s
- if (!isBoxError(E[r->r])) { // and still viable
- Subst::const_iterator assoc;
- for (assoc = subst[r->r].begin(); assoc != subst[r->r].end(); assoc++) {
- Tree Z, Z1 = subtree(X, 0, assoc->p);
- if (searchIdDef(assoc->id, Z, E[r->r])) {
- if (Z != Z1) {
- /* failed nonlinearity, add to the set of nonviable rules */
-#ifdef DEBUG
- cerr << "state " << s << ", rule #" << r->r << ": " <<
- *assoc->id << " := " << *Z1 << " *** failed *** old value: " <<
- *Z << endl;
-#endif
- E[r->r] = boxError();
- }
- } else {
- /* bind a variable for the current rule */
-#ifdef DEBUG
- cerr << "state " << s << ", rule #" << r->r << ": " <<
- *assoc->id << " := " << *Z1 << endl;
-#endif
- E[r->r] = pushValueDef(assoc->id, Z1, E[r->r]);
- }
- }
- }
- }
- if (A->final(s)) {
- /* if in a final state then return the right-hand side together with the
- corresponding variable environment */
- for (r = A->rules(s).begin(); r != A->rules(s).end(); r++) // all rules matched in state s
- if (!isBoxError(E[r->r])) { // and still viable
- /* return the rhs of the matched rule */
- C = closure(A->rhs[r->r], nil, nil, E[r->r]);
-#ifdef DEBUG
- cerr << "state " << s << ", complete match yields rhs #" << r->r <<
- ": " << *A->rhs[r->r] << endl;
-#endif
- return s;
- }
- /* if none of the rules were matched then declare a failed match */
-#ifdef DEBUG
- cerr << "state " << s << ", *** match failed ***" << endl;
-#endif
- return -1;
- }
-#ifdef DEBUG
- cerr << "state " << s << ", successful incomplete match" << endl;
-#endif
- return s;
-}
projects / Faustine.git / blobdiff