#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>
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< Assoc > | Subst |
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 State * | make_state (State *state, int r, Tree x, Path &p) |
static State * | make_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) |
Automaton * | make_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 vector<int> Path |
Definition at line 58 of file patternmatcher.cpp.
Definition at line 576 of file patternmatcher.cpp.
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 }
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 }
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 }
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 }
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 }
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; }
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 }
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 }
Definition at line 364 of file patternmatcher.cpp.
Referenced by merge_state().
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 }
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 }
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 }
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 }
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 }
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 }