#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:
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 Documentation
| typedef vector<int> Path |
Definition at line 58 of file patternmatcher.cpp.
Definition at line 576 of file patternmatcher.cpp.
Function Documentation
Definition at line 580 of file patternmatcher.cpp.
References Automaton::rules().
Referenced by apply_pattern_matcher_internal().
{
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));
}
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().
{
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;
}
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().
{
/* 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;
}
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().
{
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;
}
}
Here is the call graph for this function:
Here is the caller graph for this function:
Definition at line 25 of file patternmatcher.cpp.
References hd(), isList(), and tl().
Referenced by make_pattern_matcher().
Here is the call graph for this function:
Here is the caller graph for this function:
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, State::rules, and Automaton::rules().
Referenced by evalCase().
{
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;
}
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().
{
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;
}
}
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().
{
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;
}
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().
{
list<Rule> cprules2 = rules2;
rules1.merge(cprules2);
}
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().
{
merge_rules(state1->rules, state2->rules);
merge_trans(state1->trans, state2->trans);
}
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().
{
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);
}
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().
{
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);
}
}
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().
{
/* 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;
}
}
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().
{
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;
}
}
}
Here is the call graph for this function:
Here is the caller graph for this function:
Definition at line 62 of file patternmatcher.cpp.
References isBoxPatternOp().
Referenced by apply_pattern_matcher().
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
