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:

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.

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().

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

inlinestatic

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:

static bool isCons ( Tree  x, Tree &  h, Tree &  t  )

inlinestatic

Definition at line 25 of file patternmatcher.cpp.

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

Referenced by make_pattern_matcher().

{
  if (isList(x)) {
    h = hd(x); t = tl(x);
    return true;
  } else
    return false;
}

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, 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 = (int)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  )

inlinestatic

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:

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().

{
  int n = (int)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: