patternmatcher.cpp File Reference

#include "tlib.hh"
#include "list.hh"
#include "boxes.hh"
#include "ppbox.hh"
#include "eval.hh"
#include "patternmatcher.hh"
#include <vector>
#include <list>
#include <set>
#include <utility>
Include dependency graph for patternmatcher.cpp:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  Rule
struct  Trans
struct  State
struct  Automaton
struct  Assoc

Typedefs

typedef vector< int > Path
typedef list< AssocSubst

Functions

static bool isCons (Tree x, Tree &h, Tree &t)
static bool isBoxPatternOp (Tree box, Node &n, Tree &t1, Tree &t2)
static Tree subtree (Tree X, int i, const Path &p)
static Statemake_state (State *state, int r, Tree x, Path &p)
static Statemake_var_state (int n, State *state)
static void merge_state (State *state1, State *state2)
static void merge_rules (list< Rule > &rules1, list< Rule > &rules2)
static void merge_trans_var (list< Trans > &trans, State *state)
static void merge_trans_cst (list< Trans > &trans, Tree x, State *state)
static void merge_trans_op (list< Trans > &trans, const Node &op, int arity, State *state)
static void merge_trans (list< Trans > &trans1, list< Trans > &trans2)
Automatonmake_pattern_matcher (Tree R)
static void add_subst (vector< Subst > &subst, Automaton *A, int s)
static int apply_pattern_matcher_internal (Automaton *A, int s, Tree X, vector< Subst > &subst)
int apply_pattern_matcher (Automaton *A, int s, Tree X, Tree &C, vector< Tree > &E)

Typedef Documentation

typedef vector<int> Path

Definition at line 58 of file patternmatcher.cpp.

typedef list<Assoc> Subst

Definition at line 576 of file patternmatcher.cpp.


Function Documentation

static void add_subst ( vector< Subst > &  subst,
Automaton A,
int  s 
) [static]

Definition at line 580 of file patternmatcher.cpp.

References Automaton::rules().

Referenced by apply_pattern_matcher_internal().

00581 {
00582   list<Rule> rules = A->rules(s);
00583   list<Rule>::const_iterator r;
00584   for (r = rules.begin(); r != rules.end(); r++)
00585     if (r->id != NULL)
00586       subst[r->r].push_back(Assoc(r->id, r->p));
00587 }

Here is the call graph for this function:

Here is the caller graph for this function:

int apply_pattern_matcher ( Automaton A,
int  s,
Tree  X,
Tree C,
vector< Tree > &  E 
)

Definition at line 660 of file patternmatcher.cpp.

References apply_pattern_matcher_internal(), boxError(), closure(), Automaton::final(), isBoxError(), Automaton::n_rules(), nil, pushValueDef(), Automaton::rhs, Automaton::rules(), searchIdDef(), subst(), and subtree().

Referenced by applyList(), and make_pattern_matcher().

00665 {
00666   int n = A->n_rules();
00667   vector<Subst> subst(n, Subst());
00668   /* perform matching, record variable substitutions */
00669 #ifdef DEBUG
00670   cout << "automaton " << A << ", state " << s << ", start match on arg: " << *X << endl;
00671 #endif
00672   s = apply_pattern_matcher_internal(A, s, X, subst);
00673   C = nil;
00674   if (s < 0)
00675     /* failed match */
00676     return s;
00677   /* process variable substitutions */
00678   list<Rule>::const_iterator r;
00679   for (r = A->rules(s).begin(); r != A->rules(s).end(); r++) {
00680     // all rules still active in state s
00681     if (!isBoxError(E[r->r])) { // and still viable
00682       Subst::const_iterator assoc;
00683       for (assoc = subst[r->r].begin(); assoc != subst[r->r].end(); assoc++) {
00684     Tree Z, Z1 = subtree(X, 0, assoc->p);
00685     if (searchIdDef(assoc->id, Z, E[r->r])) {
00686       if (Z != Z1) {
00687         /* failed nonlinearity, add to the set of nonviable rules */
00688 #ifdef DEBUG
00689       cout << "state " << s << ", rule #" << r->r << ": " <<
00690         *assoc->id << " := " << *Z1 << " *** failed *** old value: " <<
00691         *Z << endl;
00692 #endif
00693         E[r->r] = boxError();
00694       }
00695     } else {
00696       /* bind a variable for the current rule */
00697 #ifdef DEBUG
00698       cout << "state " << s << ", rule #" << r->r << ": " <<
00699         *assoc->id << " := " << *Z1 << endl;
00700 #endif
00701       E[r->r] = pushValueDef(assoc->id, Z1, E[r->r]);
00702     }
00703       }
00704     }
00705   }
00706   if (A->final(s)) {
00707     /* if in a final state then return the right-hand side together with the
00708        corresponding variable environment */
00709     for (r = A->rules(s).begin(); r != A->rules(s).end(); r++) // all rules matched in state s
00710       if (!isBoxError(E[r->r])) { // and still viable
00711     /* return the rhs of the matched rule */
00712     C = closure(A->rhs[r->r], nil, nil, E[r->r]);
00713 #ifdef DEBUG
00714     cout << "state " << s << ", complete match yields rhs #" << r->r <<
00715       ": " << *A->rhs[r->r] << endl;
00716 #endif
00717     return s;
00718       }
00719     /* if none of the rules were matched then declare a failed match */
00720 #ifdef DEBUG
00721     cout << "state " << s << ", *** match failed ***" << endl;
00722 #endif
00723     return -1;
00724   }
00725 #ifdef DEBUG
00726   cout << "state " << s << ", successful incomplete match" << endl;
00727 #endif
00728   return s;
00729 }

Here is the call graph for this function:

Here is the caller graph for this function:

static int apply_pattern_matcher_internal ( Automaton A,
int  s,
Tree  X,
vector< Subst > &  subst 
) [static]

Definition at line 593 of file patternmatcher.cpp.

References add_subst(), isBoxPatternOp(), simplifyPattern(), Automaton::state, and Automaton::trans().

Referenced by apply_pattern_matcher().

00595 {
00596   /* FIXME: rewrite this non-recursively? */
00597   if (s >= 0) {
00598     list<Trans>::const_iterator t;
00599     if (A->state[s]->match_num)
00600       /* simplify possible numeric argument on the fly */
00601       X = simplifyPattern(X);
00602     /* first check for applicable non-variable transitions */
00603     for (t = A->trans(s).begin(); t != A->trans(s).end(); t++) {
00604       Tree x;
00605       Node op(0), op1(0);
00606       if (t->is_var_trans())
00607     continue;
00608       else if (t->is_cst_trans(x)) {
00609     if (X==x) {
00610       /* transition on constant */
00611 #ifdef DEBUG
00612       cout << "state " << s << ", " << *x << ": goto state " << t->state->s << endl;
00613 #endif
00614       add_subst(subst, A, s);
00615       s = t->state->s;
00616       return s;
00617     }
00618       } else if (t->is_op_trans(op)) {
00619     Tree x0, x1;
00620     if (isBoxPatternOp(X, op1, x0, x1) && op == op1) {
00621       /* transition on operation symbol */
00622 #ifdef DEBUG
00623       cout << "state " << s << ", " << op << ": goto state " << t->state->s << endl;
00624 #endif
00625       add_subst(subst, A, s);
00626       s = t->state->s;
00627       if (s >= 0)
00628         s = apply_pattern_matcher_internal(A, s, x0, subst);
00629       if (s >= 0)
00630         s = apply_pattern_matcher_internal(A, s, x1, subst);
00631       return s;
00632     }
00633       }
00634     }
00635     /* check for variable transition (is always first in the list of
00636        transitions) */
00637     t = A->trans(s).begin();
00638     if (t->is_var_trans()) {
00639 #ifdef DEBUG
00640       cout << "state " << s << ", _: goto state " << t->state->s << endl;
00641 #endif
00642       add_subst(subst, A, s);
00643       s = t->state->s;
00644     } else {
00645 #ifdef DEBUG
00646       cout << "state " << s << ", *** match failed ***" << endl;
00647 #endif
00648       s = -1;
00649     }
00650   }
00651   return s;
00652 }

Here is the call graph for this function:

Here is the caller graph for this function:

static bool isBoxPatternOp ( Tree  box,
Node n,
Tree t1,
Tree t2 
) [inline, static]

Definition at line 36 of file patternmatcher.cpp.

References isBoxHGroup(), isBoxMerge(), isBoxPar(), isBoxRec(), isBoxSeq(), isBoxSplit(), isBoxTGroup(), isBoxVGroup(), and CTree::node().

Referenced by apply_pattern_matcher_internal(), make_state(), and subtree().

00037 {
00038     if (    isBoxPar(box, t1, t2) ||
00039             isBoxSeq(box, t1, t2) ||
00040             isBoxSplit(box, t1, t2) ||
00041             isBoxMerge(box, t1, t2) ||
00042             isBoxHGroup(box, t1, t2) ||
00043             isBoxVGroup(box, t1, t2) ||
00044             isBoxTGroup(box, t1, t2) ||
00045             isBoxRec(box, t1, t2)    )
00046     {
00047         n = box->node();
00048         return true;
00049     } else {
00050         return false;
00051     }
00052 }

Here is the call graph for this function:

Here is the caller graph for this function:

static bool isCons ( Tree  x,
Tree h,
Tree t 
) [inline, static]

Definition at line 25 of file patternmatcher.cpp.

References hd(), isList(), and tl().

Referenced by make_pattern_matcher().

00026 {
00027   if (isList(x)) {
00028     h = hd(x); t = tl(x);
00029     return true;
00030   } else
00031     return false;
00032 }

Here is the call graph for this function:

Here is the caller graph for this function:

Automaton* make_pattern_matcher ( Tree  R  ) 

Definition at line 479 of file patternmatcher.cpp.

References apply_pattern_matcher(), Automaton::build(), Automaton::final(), isBoxError(), isCons(), len(), make_state(), merge_state(), nil, reverse(), Automaton::rhs, Automaton::rules(), and State::rules.

Referenced by evalCase().

00482           :
00483 
00484    Rules    ::= cons Rule (cons Rule ... nil)
00485    Rule     ::= cons Lhs Rhs
00486    Lhs      ::= cons Pattern (cons Pattern ... nil)
00487    Pattern  ::= Tree (parameter pattern)
00488    Rhs      ::= Tree
00489 
00490    NOTE: The lists of rules and patterns are actually delivered in reverse
00491    order by the parser, so we have to reverse them on the fly. */
00492 {
00493   Automaton *A = new Automaton;
00494   int n = len(R), r = n;
00495   State *start = new State;
00496   Tree rule, rest;
00497   vector<Tree> rules(n, (Tree)NULL);
00498   vector< vector<Tree> > testpats(n);
00499   while (isCons(R, rule, rest)) {
00500     rules[--r] = rule;
00501     R = rest;
00502   }
00503   for (r = 0; r < n; r++) {
00504     Tree lhs, rhs;
00505     if (isCons(rules[r], lhs, rhs)) {
00506       Tree pat, rest;
00507       int m = len(lhs), i = m;
00508       vector<Tree> pats(len(lhs), (Tree)NULL);
00509       State *state0 = new State, *state = state0;
00510       A->rhs.push_back(rhs);
00511       while (isCons(lhs, pat, rest)) {
00512     pats[--i] = pat;
00513     lhs = rest;
00514       }
00515       testpats[r] = pats;
00516       for (i = 0; i < m; i++) {
00517     Path p;
00518     state = make_state(state, r, pats[i], p);
00519       }
00520       Rule rule(r, NULL);
00521       state->rules.push_back(rule);
00522       merge_state(start, state0);
00523       delete state0;
00524     }
00525   }
00526   A->build(start);
00527   /* Check for shadowed rules. Note that because of potential nonlinearities
00528      it is *not* enough to just check the rule lists of final states and
00529      determine whether they have multiple matched rules. */
00530   for (r = 0; r < n; r++) {
00531     int s = 0, m = testpats[r].size();
00532     Tree C;
00533     vector<Tree> E(n, nil);
00534     /* try to match the lhs of rule #r */
00535     for (int i = 0; i < m; i++) {
00536       s = apply_pattern_matcher(A, s, testpats[r][i], C, E);
00537       if (s < 0) break;
00538     }
00539     if (A->final(s)) {
00540       list<Rule>::const_iterator ru;
00541       for (ru = A->rules(s).begin(); ru != A->rules(s).end(); ru++)
00542     if (!isBoxError(E[ru->r]))
00543       if (ru->r < r) {
00544         /* Lhs of rule #r matched a higher-priority rule, so rule #r may
00545            be shadowed. */
00546         Tree lhs1, rhs1, lhs2, rhs2;
00547         if (isCons(rules[ru->r], lhs1, rhs1) &&  isCons(rules[r], lhs2, rhs2)) {
00548             cerr    << "WARNING : shadowed pattern-matching rule: "
00549                 << boxpp(reverse(lhs2)) << " => " << boxpp(rhs2) << ";"
00550                 << " previous rule was: " 
00551                 << boxpp(reverse(lhs1)) << " => " << boxpp(rhs1) << ";"
00552                 << endl;
00553         } else {
00554             cerr << "INTERNAL ERROR : " << __FILE__ << ":" << __LINE__ << endl;
00555             exit(1);
00556         }
00557       } else if (ru->r >= r)
00558         break;
00559     }
00560   }
00561 #ifdef DEBUG
00562   cout << "automaton " << A << endl << *A << "end automaton" << endl;
00563 #endif
00564   return A;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static State* make_state ( State state,
int  r,
Tree  x,
Path p 
) [static]

Definition at line 300 of file patternmatcher.cpp.

References isBoxPatternOp(), isBoxPatternVar(), State::rules, and State::trans.

Referenced by make_pattern_matcher().

00301 {
00302   Tree id, x0, x1;
00303   Node op(0);
00304   if (isBoxPatternVar(x, id)) {
00305     /* variable */
00306     Rule rule(r, id, p);
00307     state->rules.push_back(rule);
00308     Trans trans(NULL);
00309     state->trans.push_back(trans);
00310     return state->trans.begin()->state;
00311   } else if (isBoxPatternOp(x, op, x0, x1)) {
00312     /* composite pattern */
00313     Rule rule(r, NULL);
00314     state->rules.push_back(rule);
00315     Trans trans(op, 2);
00316     state->trans.push_back(trans);
00317     State *next = state->trans.begin()->state;
00318     p.push_back(0);
00319     next = make_state(next, r, x0, p);
00320     p.pop_back();
00321     p.push_back(1);
00322     next = make_state(next, r, x1, p);
00323     p.pop_back();
00324     return next;
00325   } else {
00326     /* constant */
00327     Rule rule(r, NULL);
00328     state->rules.push_back(rule);
00329     Trans trans(x);
00330     state->trans.push_back(trans);
00331     return state->trans.begin()->state;
00332   }
00333 }

Here is the call graph for this function:

Here is the caller graph for this function:

static State* make_var_state ( int  n,
State state 
) [static]

Definition at line 337 of file patternmatcher.cpp.

References State::rules, and State::trans.

Referenced by merge_trans_op(), and merge_trans_var().

00338 {
00339   if (n <= 0)
00340     return new State(*state);
00341   list<Rule>rules = state->rules;
00342   list<Rule>::iterator r;
00343   for (r = rules.begin(); r != rules.end(); r++) {
00344     r->id = NULL; r->p = Path();
00345   }
00346   State *prefix = new State, *current = prefix;
00347   while (n-- > 0) {
00348     current->rules = rules;
00349     Trans trans(NULL);
00350     current->trans.push_back(trans);
00351     current = current->trans.begin()->state;
00352   }
00353   *current = *state;
00354   return prefix;
00355 }

Here is the caller graph for this function:

static void merge_rules ( list< Rule > &  rules1,
list< Rule > &  rules2 
) [inline, static]

Definition at line 364 of file patternmatcher.cpp.

Referenced by merge_state().

00365 {
00366   list<Rule> cprules2 = rules2;
00367   rules1.merge(cprules2);
00368 }

Here is the caller graph for this function:

static void merge_state ( State state1,
State state2 
) [static]

Definition at line 470 of file patternmatcher.cpp.

References merge_rules(), merge_trans(), State::rules, and State::trans.

Referenced by make_pattern_matcher(), merge_trans_cst(), merge_trans_op(), and merge_trans_var().

00471 {
00472   merge_rules(state1->rules, state2->rules);
00473   merge_trans(state1->trans, state2->trans);
00474 }

Here is the call graph for this function:

Here is the caller graph for this function:

static void merge_trans ( list< Trans > &  trans1,
list< Trans > &  trans2 
) [static]

Definition at line 449 of file patternmatcher.cpp.

References merge_trans_cst(), merge_trans_op(), and merge_trans_var().

Referenced by merge_state().

00450 {
00451   Tree x;
00452   Node op(0);
00453   if (trans2.empty())
00454     ;
00455   else if (trans1.empty()) {
00456     list<Trans> cptrans2 = trans2;
00457     /* append a copy of trans2 to trans1 */
00458     trans1.splice(trans1.end(), cptrans2);
00459   } else if (trans2.begin()->is_var_trans())
00460     /* merge a variable transition */
00461     merge_trans_var(trans1, trans2.begin()->state);
00462   else if (trans2.begin()->is_cst_trans(x))
00463     /* merge a constant transition */
00464     merge_trans_cst(trans1, x, trans2.begin()->state);
00465   else if (trans2.begin()->is_op_trans(op))
00466     /* merge a BDA op transition */
00467     merge_trans_op(trans1, op, trans2.begin()->arity, trans2.begin()->state);
00468 }

Here is the call graph for this function:

Here is the caller graph for this function:

static void merge_trans_cst ( list< Trans > &  trans,
Tree  x,
State state 
) [static]

Definition at line 396 of file patternmatcher.cpp.

References merge_state().

Referenced by merge_trans().

00397 {
00398   list<Trans>::iterator t0 = trans.begin(), t1 = t0, t;
00399   Tree x1;
00400   if (t0->is_var_trans()) t1++;
00401   for (t = t1; t != trans.end(); t++) {
00402     if (t->is_cst_trans(x1)) {
00403       if (x == x1) {
00404     merge_state(t->state, state);
00405     return;
00406       } else if (x < x1)
00407     break;
00408     }
00409   }
00410   /* no matching transition has been found; add a new one */
00411   Trans tr(x);
00412   trans.insert(t, tr); t--;
00413   State *state1 = t->state;
00414   *state1 = *state;
00415   if (t1 != t0) {
00416     /* if we have a variable transition in the current state, we also need to
00417        merge its completion for the current symbol/constant */
00418     merge_state(state1, t0->state);
00419   }
00420 }

Here is the call graph for this function:

Here is the caller graph for this function:

static void merge_trans_op ( list< Trans > &  trans,
const Node op,
int  arity,
State state 
) [static]

Definition at line 422 of file patternmatcher.cpp.

References Node::getSym(), make_var_state(), and merge_state().

Referenced by merge_trans().

00424 {
00425   /* analogous to merge_trans_cst above, but handles the arity>0 case */
00426   list<Trans>::iterator t0 = trans.begin(), t1 = t0, t;
00427   Node op1(0);
00428   if (t0->is_var_trans()) t1++;
00429   for (t = t1; t != trans.end(); t++) {
00430     if (t->is_op_trans(op1)) {
00431       if (op == op1) {
00432     merge_state(t->state, state);
00433     return;
00434       } else if (op.getSym() < op1.getSym())
00435     break;
00436     }
00437   }
00438   Trans tr(op, arity);
00439   trans.insert(t, tr); t--;
00440   State *state1 = t->state;
00441   *state1 = *state;
00442   if (t1 != t0) {
00443     State *state2 = make_var_state(arity, t0->state);
00444     merge_state(state1, state2);
00445     delete state2;
00446   }
00447 }

Here is the call graph for this function:

Here is the caller graph for this function:

static void merge_trans_var ( list< Trans > &  trans,
State state 
) [static]

Definition at line 370 of file patternmatcher.cpp.

References make_var_state(), and merge_state().

Referenced by merge_trans().

00371 {
00372   if (!trans.begin()->is_var_trans()) {
00373     /* If we don't have a variable transition in this state yet then create a
00374        new one. */
00375     Trans tr(NULL);
00376     trans.push_front(tr);
00377   }
00378   list<Trans>::const_iterator t;
00379   Tree x;
00380   Node op(0);
00381   for (t = trans.begin(); t != trans.end(); t++) {
00382     if (t->is_var_trans())
00383       merge_state(t->state, state);
00384     else if (t->is_cst_trans(x)) {
00385       /* add the completion of the given state for a constant */
00386       merge_state(t->state, state);
00387     } else if (t->is_op_trans(op)) {
00388       /* add the completion of the given state for an arity>0 op */
00389       State *state1 = make_var_state(t->arity, state);
00390       merge_state(t->state, state1);
00391       delete state1;
00392     }
00393   }
00394 }

Here is the call graph for this function:

Here is the caller graph for this function:

static Tree subtree ( Tree  X,
int  i,
const Path p 
) [static]

Definition at line 62 of file patternmatcher.cpp.

References isBoxPatternOp().

Referenced by apply_pattern_matcher().

00063 {
00064   int n = p.size();
00065   Node op(0);
00066   Tree x0, x1;
00067   if (i < n && isBoxPatternOp(X, op, x0, x1))
00068     return subtree((p[i]==0)?x0:x1, i+1, p);
00069   else
00070     return X;
00071 }

Here is the call graph for this function:

Here is the caller graph for this function:

Generated on Thu Jul 15 15:47:13 2010 for FAUST compiler by  doxygen 1.6.3