00001
00002
00003
00004
00005 #include "tlib.hh"
00006 #include "list.hh"
00007 #include "boxes.hh"
00008 #include "ppbox.hh"
00009 #include "eval.hh"
00010 #include "patternmatcher.hh"
00011
00012 using namespace std;
00013 #include <vector>
00014 #include <list>
00015 #include <set>
00016 #include <utility>
00017
00018
00019
00020
00021
00022
00023
00024
00025 static inline bool isCons(Tree x, Tree& h, Tree& t)
00026 {
00027 if (isList(x)) {
00028 h = hd(x); t = tl(x);
00029 return true;
00030 } else
00031 return false;
00032 }
00033
00034
00035
00036 static inline bool isBoxPatternOp(Tree box, Node& n, Tree& t1, Tree& t2)
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 }
00053
00054
00055
00056
00057
00058 typedef vector<int> Path;
00059
00060
00061
00062 static Tree subtree(Tree X, int i, const Path& p)
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 }
00072
00073
00074
00075 struct Rule {
00076 int r;
00077 Tree id;
00078 Path p;
00079
00080 Rule(int _r, Tree _id) : r(_r), id(_id), p(Path()) {}
00081 Rule(int _r, Tree _id, const Path& _p) : r(_r), id(_id), p(_p) {}
00082 Rule(const Rule& rule) : r(rule.r), id(rule.id), p(rule.p) {}
00083
00084 Rule& operator = (const Rule& rule)
00085 { r = rule.r; id = rule.id; p = rule.p; return *this; }
00086
00087 bool operator == (const Rule& rule) const
00088 { return r == rule.r; }
00089 bool operator < (const Rule& rule) const
00090 { return r < rule.r; }
00091
00092 #ifdef DEBUG
00093 ostream& print(ostream& fout) const;
00094 #endif
00095 };
00096
00097 struct State;
00098
00099
00100
00101 struct Trans {
00102 Tree x;
00103 Node n;
00104 int arity;
00105 State *state;
00106
00107 Trans(Tree _x);
00108 Trans(const Node& _n, int _arity);
00109 Trans(const Trans& trans);
00110 ~Trans();
00111
00112 Trans& operator = (const Trans& trans);
00113
00114 bool is_var_trans() const { return arity == 0 && x == NULL; }
00115 bool is_cst_trans(Tree &_x) const { _x = x; return arity == 0 && x != NULL; }
00116 bool is_op_trans(Node &_n) const { _n = n; return arity > 0; }
00117
00118 bool operator == (const Trans& trans) const
00119 { return arity == trans.arity && x == trans.x && n == trans.n; }
00120 bool operator < (const Trans& trans) const
00121 { return (arity < trans.arity) ? 1 :
00122 (arity > trans.arity) ? 0 :
00123 (arity == 0) ? (x < trans.x) :
00124 (n.getSym() < trans.n.getSym()); }
00125
00126 #ifdef DEBUG
00127 ostream& print(ostream& fout) const;
00128 #endif
00129 };
00130
00131
00132
00133 struct State {
00134 int s;
00135 bool match_num;
00136 list<Rule> rules;
00137 list<Trans> trans;
00138 State() :
00139 s(0), match_num(false), rules(list<Rule>()), trans(list<Trans>()) {}
00140 State(const State& state) :
00141 s(state.s), match_num(state.match_num),
00142 rules(state.rules), trans(state.trans) {}
00143
00144 State& operator = (const State& state)
00145 { s = state.s; match_num = state.match_num;
00146 rules = state.rules; trans = state.trans;
00147 return *this;
00148 }
00149
00150 #ifdef DEBUG
00151 ostream& print(ostream& fout) const;
00152 #endif
00153 };
00154
00155
00156
00157 Trans::Trans(Tree _x) :
00158 x(_x), n(0), arity(0), state(new State)
00159 {
00160 }
00161
00162 Trans::Trans(const Node& _n, int _arity) :
00163 x(NULL), n(_n), arity(_arity), state(new State)
00164 {
00165 }
00166
00167 Trans::Trans(const Trans& trans) :
00168 x(trans.x), n(trans.n), arity(trans.arity)
00169 {
00170 state = new State(*trans.state);
00171 }
00172
00173 Trans::~Trans()
00174 {
00175 delete state;
00176 }
00177
00178 Trans& Trans::operator = (const Trans& trans)
00179 {
00180 x = trans.x; n = trans.n; arity = trans.arity;
00181 state = new State(*trans.state);
00182 return *this;
00183 }
00184
00185
00186
00187 struct Automaton {
00188 vector<State*> state;
00189 vector<Tree> rhs;
00190
00191 Automaton() : state(vector<State*>()), rhs(vector<Tree>()), s(0) {}
00192
00193
00194 int n_rules() { return rhs.size(); }
00195
00196 const list<Rule>& rules(int s) { return state[s]->rules; }
00197
00198 const list<Trans>& trans(int s) { return state[s]->trans; }
00199
00200 bool final(int s) { return trans(s).empty(); }
00201
00202
00203 int s;
00204 void build(State *st);
00205
00206 #ifdef DEBUG
00207 ostream& print(ostream& fout) const;
00208 #endif
00209 };
00210
00211 void Automaton::build(State *st)
00212 {
00213 state.push_back(st);
00214 st->s = s++;
00215 list<Trans>::const_iterator t;
00216 for (t = st->trans.begin(); t != st->trans.end(); t++) {
00217 Tree x;
00218 float f;
00219 int i;
00220 if (t->is_cst_trans(x) &&
00221 (isBoxInt(x, &i) || isBoxReal(x, &f)))
00222 st->match_num = true;
00223 build(t->state);
00224 }
00225 }
00226
00227
00228
00229 #ifdef DEBUG
00230 inline ostream& operator << (ostream& s, const Rule& x)
00231 { return x.print(s); }
00232 inline ostream& operator << (ostream& s, const Trans& x)
00233 { return x.print(s); }
00234 inline ostream& operator << (ostream& s, const State& x)
00235 { return x.print(s); }
00236 inline ostream& operator << (ostream& s, const Automaton& x)
00237 { return x.print(s); }
00238
00239 ostream& Rule::print(ostream& fout) const
00240 {
00241 if (id != NULL)
00242 fout << "#" << r << "(" << *id << ")";
00243 else
00244 fout << "#" << r;
00245 return fout;
00246 }
00247
00248 ostream& Trans::print(ostream& fout) const
00249 {
00250 if (arity > 0)
00251 fout << "\top " << n << ": state " << state->s << endl;
00252 else if (x == NULL)
00253 fout << "\tvar _: state " << state->s << endl;
00254 else
00255 fout << "\tcst " << *x << ": state " << state->s << endl;
00256 return fout;
00257 }
00258
00259 ostream& State::print(ostream& fout) const
00260 {
00261 fout << "state " << s << ":";
00262 list<Rule>::const_iterator r;
00263 for (r = rules.begin(); r != rules.end(); r++)
00264 fout << " " << *r;
00265 fout << endl;
00266 list<Trans>::const_iterator t;
00267 for (t = trans.begin(); t != trans.end(); t++)
00268 fout << *t;
00269 return fout;
00270 }
00271
00272 ostream& Automaton::print(ostream& fout) const
00273 {
00274 int i, n = rhs.size();
00275 for (i = 0; i < n; i++)
00276 fout << "rule #" << i << ": " << *rhs[i] << endl;
00277 n = state.size();
00278 for (i = 0; i < n; i++)
00279 fout << *state[i];
00280 return fout;
00281 }
00282 #endif
00283
00284
00285
00286
00287
00288
00289
00290
00291
00292
00293
00294
00295
00296
00297
00298
00299
00300 static State *make_state(State *state, int r, Tree x, Path& p)
00301 {
00302 Tree id, x0, x1;
00303 Node op(0);
00304 if (isBoxPatternVar(x, id)) {
00305
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
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
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 }
00334
00335
00336
00337 static State *make_var_state(int n, State *state)
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 }
00356
00357
00358
00359
00360
00361
00362 static void merge_state(State *state1, State *state2);
00363
00364 static void inline merge_rules(list<Rule>& rules1, list<Rule>& rules2)
00365 {
00366 list<Rule> cprules2 = rules2;
00367 rules1.merge(cprules2);
00368 }
00369
00370 static void merge_trans_var(list<Trans>& trans, State *state)
00371 {
00372 if (!trans.begin()->is_var_trans()) {
00373
00374
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
00386 merge_state(t->state, state);
00387 } else if (t->is_op_trans(op)) {
00388
00389 State *state1 = make_var_state(t->arity, state);
00390 merge_state(t->state, state1);
00391 delete state1;
00392 }
00393 }
00394 }
00395
00396 static void merge_trans_cst(list<Trans>& trans, Tree x, State *state)
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
00411 Trans tr(x);
00412 trans.insert(t, tr); t--;
00413 State *state1 = t->state;
00414 *state1 = *state;
00415 if (t1 != t0) {
00416
00417
00418 merge_state(state1, t0->state);
00419 }
00420 }
00421
00422 static void merge_trans_op(list<Trans>& trans, const Node& op,
00423 int arity, State *state)
00424 {
00425
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 }
00448
00449 static void merge_trans(list<Trans>& trans1, list<Trans>& trans2)
00450 {
00451 Tree x;
00452 Node op(0);
00453 if (trans2.empty())
00454 ;
00455 else if (trans1.empty()) {
00456 list<Trans> cptrans2 = trans2;
00457
00458 trans1.splice(trans1.end(), cptrans2);
00459 } else if (trans2.begin()->is_var_trans())
00460
00461 merge_trans_var(trans1, trans2.begin()->state);
00462 else if (trans2.begin()->is_cst_trans(x))
00463
00464 merge_trans_cst(trans1, x, trans2.begin()->state);
00465 else if (trans2.begin()->is_op_trans(op))
00466
00467 merge_trans_op(trans1, op, trans2.begin()->arity, trans2.begin()->state);
00468 }
00469
00470 static void merge_state(State *state1, State *state2)
00471 {
00472 merge_rules(state1->rules, state2->rules);
00473 merge_trans(state1->trans, state2->trans);
00474 }
00475
00476
00477
00478
00479 Automaton *make_pattern_matcher(Tree R)
00480
00481
00482
00483
00484
00485
00486
00487
00488
00489
00490
00491 {
00492 Automaton *A = new Automaton;
00493 int n = len(R), r = n;
00494 State *start = new State;
00495 Tree rule, rest;
00496 vector<Tree> rules(n, (Tree)NULL);
00497 vector< vector<Tree> > testpats(n);
00498 while (isCons(R, rule, rest)) {
00499 rules[--r] = rule;
00500 R = rest;
00501 }
00502 for (r = 0; r < n; r++) {
00503 Tree lhs, rhs;
00504 if (isCons(rules[r], lhs, rhs)) {
00505 Tree pat, rest;
00506 int m = len(lhs), i = m;
00507 vector<Tree> pats(len(lhs), (Tree)NULL);
00508 State *state0 = new State, *state = state0;
00509 A->rhs.push_back(rhs);
00510 while (isCons(lhs, pat, rest)) {
00511 pats[--i] = pat;
00512 lhs = rest;
00513 }
00514 testpats[r] = pats;
00515 for (i = 0; i < m; i++) {
00516 Path p;
00517 state = make_state(state, r, pats[i], p);
00518 }
00519 Rule rule(r, NULL);
00520 state->rules.push_back(rule);
00521 merge_state(start, state0);
00522 delete state0;
00523 }
00524 }
00525 A->build(start);
00526
00527
00528
00529 for (r = 0; r < n; r++) {
00530 int s = 0, m = testpats[r].size();
00531 Tree C;
00532 vector<Tree> E(n, nil);
00533
00534 for (int i = 0; i < m; i++) {
00535 s = apply_pattern_matcher(A, s, testpats[r][i], C, E);
00536 if (s < 0) break;
00537 }
00538 if (A->final(s)) {
00539 list<Rule>::const_iterator ru;
00540 for (ru = A->rules(s).begin(); ru != A->rules(s).end(); ru++)
00541 if (!isBoxError(E[ru->r]))
00542 if (ru->r < r) {
00543
00544
00545 Tree lhs1, rhs1, lhs2, rhs2;
00546 if (isCons(rules[ru->r], lhs1, rhs1) && isCons(rules[r], lhs2, rhs2)) {
00547 cerr << "WARNING : shadowed pattern-matching rule: "
00548 << boxpp(reverse(lhs2)) << " => " << boxpp(rhs2) << ";"
00549 << " previous rule was: "
00550 << boxpp(reverse(lhs1)) << " => " << boxpp(rhs1) << ";"
00551 << endl;
00552 } else {
00553 cerr << "INTERNAL ERROR : " << __FILE__ << ":" << __LINE__ << endl;
00554 exit(1);
00555 }
00556 } else if (ru->r >= r)
00557 break;
00558 }
00559 }
00560 #ifdef DEBUG
00561 cout << "automaton " << A << endl << *A << "end automaton" << endl;
00562 #endif
00563 return A;
00564 }
00565
00566
00567
00568
00569
00570
00571 struct Assoc {
00572 Tree id;
00573 Path p;
00574 Assoc(Tree _id, const Path& _p) : id(_id), p(_p) {}
00575 };
00576 typedef list<Assoc> Subst;
00577
00578
00579
00580 static void add_subst(vector<Subst>& subst, Automaton *A, int s)
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 }
00588
00589
00590
00591
00592
00593 static int apply_pattern_matcher_internal(Automaton *A, int s, Tree X,
00594 vector<Subst>& subst)
00595 {
00596
00597 if (s >= 0) {
00598 list<Trans>::const_iterator t;
00599 if (A->state[s]->match_num)
00600
00601 X = simplifyPattern(X);
00602
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
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
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
00636
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 }
00653
00654
00655
00656
00657
00658
00659
00660 int apply_pattern_matcher(Automaton *A,
00661 int s,
00662 Tree X,
00663 Tree& C,
00664 vector<Tree>& E)
00665 {
00666 int n = A->n_rules();
00667 vector<Subst> subst(n, Subst());
00668
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
00676 return s;
00677
00678 list<Rule>::const_iterator r;
00679 for (r = A->rules(s).begin(); r != A->rules(s).end(); r++) {
00680
00681 if (!isBoxError(E[r->r])) {
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
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
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
00708
00709 for (r = A->rules(s).begin(); r != A->rules(s).end(); r++)
00710 if (!isBoxError(E[r->r])) {
00711
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
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 }