Erosion and dilation algorithme successfully tested.
[Faustine.git] / interpretor / faust-0.9.47mr3 / compiler / patternmatcher / patternmatcher.cpp
1
2 /* compiler/patternmatcher/patternmatcher.cpp: implementation of the Faust
3 rewriting engine */
4
5 #include "tlib.hh"
6 #include "list.hh"
7 #include "boxes.hh"
8 #include "ppbox.hh"
9 #include "eval.hh"
10 #include "patternmatcher.hh"
11
12 using namespace std;
13 #include <vector>
14 #include <list>
15 #include <set>
16 #include <utility>
17
18 /* Uncomment for debugging output. */
19 //#define DEBUG
20
21 /* Additional Tree deconstruction operations. */
22
23 /* Check for cons (nonempty list) nodes. */
24
25 static inline bool isCons(Tree x, Tree& h, Tree& t)
26 {
27 if (isList(x)) {
28 h = hd(x); t = tl(x);
29 return true;
30 } else
31 return false;
32 }
33
34 /* Deconstruct a (BDA) op pattern (YO). */
35
36 static inline bool isBoxPatternOp(Tree box, Node& n, Tree& t1, Tree& t2)
37 {
38 if ( isBoxPar(box, t1, t2) ||
39 isBoxSeq(box, t1, t2) ||
40 isBoxSplit(box, t1, t2) ||
41 isBoxMerge(box, t1, t2) ||
42 isBoxHGroup(box, t1, t2) ||
43 isBoxVGroup(box, t1, t2) ||
44 isBoxTGroup(box, t1, t2) ||
45 isBoxRec(box, t1, t2) )
46 {
47 n = box->node();
48 return true;
49 } else {
50 return false;
51 }
52 }
53
54 /* TA data structures. */
55
56 /* subterm paths */
57
58 typedef vector<int> Path;
59
60 /* Subterm at given path in given term tree. */
61
62 static Tree subtree(Tree X, int i, const Path& p)
63 {
64 int n = p.size();
65 Node op(0);
66 Tree x0, x1;
67 if (i < n && isBoxPatternOp(X, op, x0, x1))
68 return subtree((p[i]==0)?x0:x1, i+1, p);
69 else
70 return X;
71 }
72
73 /* rule markers */
74
75 struct Rule {
76 int r; // rule number
77 Tree id; // matched variable (NULL if none)
78 Path p; // subterm path indicating where variable value is found
79
80 Rule(int _r, Tree _id) : r(_r), id(_id), p(Path()) {}
81 Rule(int _r, Tree _id, const Path& _p) : r(_r), id(_id), p(_p) {}
82 Rule(const Rule& rule) : r(rule.r), id(rule.id), p(rule.p) {}
83
84 Rule& operator = (const Rule& rule)
85 { r = rule.r; id = rule.id; p = rule.p; return *this; }
86
87 bool operator == (const Rule& rule) const
88 { return r == rule.r; }
89 bool operator < (const Rule& rule) const
90 { return r < rule.r; }
91
92 #ifdef DEBUG
93 ostream& print(ostream& fout) const;
94 #endif
95 };
96
97 struct State;
98
99 /* transitions */
100
101 struct Trans {
102 Tree x; // symbol or constant (NULL for variable)
103 Node n; // operator symbol (if arity>0)
104 int arity; // symbol arity
105 State *state; // successor state
106
107 Trans(Tree _x);
108 Trans(const Node& _n, int _arity);
109 Trans(const Trans& trans);
110 ~Trans();
111
112 Trans& operator = (const Trans& trans);
113
114 bool is_var_trans() const { return arity == 0 && x == NULL; }
115 bool is_cst_trans(Tree &_x) const { _x = x; return arity == 0 && x != NULL; }
116 bool is_op_trans(Node &_n) const { _n = n; return arity > 0; }
117
118 bool operator == (const Trans& trans) const
119 { return arity == trans.arity && x == trans.x && n == trans.n; }
120 bool operator < (const Trans& trans) const
121 { return (arity < trans.arity) ? 1 :
122 (arity > trans.arity) ? 0 :
123 (arity == 0) ? (x < trans.x) :
124 (n.getSym() < trans.n.getSym()); }
125
126 #ifdef DEBUG
127 ostream& print(ostream& fout) const;
128 #endif
129 };
130
131 /* states */
132
133 struct State {
134 int s; // state number
135 bool match_num; // whether state has a transition on a numeric constant
136 list<Rule> rules; // rule markers
137 list<Trans> trans; // transitions (1st transition is on variable if available)
138 State() :
139 s(0), match_num(false), rules(list<Rule>()), trans(list<Trans>()) {}
140 State(const State& state) :
141 s(state.s), match_num(state.match_num),
142 rules(state.rules), trans(state.trans) {}
143
144 State& operator = (const State& state)
145 { s = state.s; match_num = state.match_num;
146 rules = state.rules; trans = state.trans;
147 return *this;
148 }
149
150 #ifdef DEBUG
151 ostream& print(ostream& fout) const;
152 #endif
153 };
154
155 // these need to come here so that the storage size of struct State is known
156
157 Trans::Trans(Tree _x) :
158 x(_x), n(0), arity(0), state(new State)
159 {
160 }
161
162 Trans::Trans(const Node& _n, int _arity) :
163 x(NULL), n(_n), arity(_arity), state(new State)
164 {
165 }
166
167 Trans::Trans(const Trans& trans) :
168 x(trans.x), n(trans.n), arity(trans.arity)
169 {
170 state = new State(*trans.state);
171 }
172
173 Trans::~Trans()
174 {
175 delete state;
176 }
177
178 Trans& Trans::operator = (const Trans& trans)
179 {
180 x = trans.x; n = trans.n; arity = trans.arity;
181 state = new State(*trans.state);
182 return *this;
183 }
184
185 /* the automaton */
186
187 struct Automaton {
188 vector<State*> state;
189 vector<Tree> rhs;
190
191 Automaton() : state(vector<State*>()), rhs(vector<Tree>()), s(0) {}
192
193 // number of rules
194 int n_rules() { return rhs.size(); }
195 // markers of rules still active in state s
196 const list<Rule>& rules(int s) { return state[s]->rules; }
197 // transitions in state s
198 const list<Trans>& trans(int s) { return state[s]->trans; }
199 // is s a final state?
200 bool final(int s) { return trans(s).empty(); }
201
202 // assign state numbers and build the state table
203 int s;
204 void build(State *st);
205
206 #ifdef DEBUG
207 ostream& print(ostream& fout) const;
208 #endif
209 };
210
211 void Automaton::build(State *st)
212 {
213 state.push_back(st);
214 st->s = s++;
215 list<Trans>::const_iterator t;
216 for (t = st->trans.begin(); t != st->trans.end(); t++) {
217 Tree x;
218 double f;
219 int i;
220 if (t->is_cst_trans(x) &&
221 (isBoxInt(x, &i) || isBoxReal(x, &f)))
222 st->match_num = true;
223 build(t->state);
224 }
225 }
226
227 /* Debugging output. */
228
229 #ifdef DEBUG
230 inline ostream& operator << (ostream& s, const Rule& x)
231 { return x.print(s); }
232 inline ostream& operator << (ostream& s, const Trans& x)
233 { return x.print(s); }
234 inline ostream& operator << (ostream& s, const State& x)
235 { return x.print(s); }
236 inline ostream& operator << (ostream& s, const Automaton& x)
237 { return x.print(s); }
238
239 ostream& Rule::print(ostream& fout) const
240 {
241 if (id != NULL)
242 fout << "#" << r << "(" << *id << ")";
243 else
244 fout << "#" << r;
245 return fout;
246 }
247
248 ostream& Trans::print(ostream& fout) const
249 {
250 if (arity > 0)
251 fout << "\top " << n << ": state " << state->s << endl;
252 else if (x == NULL)
253 fout << "\tvar _: state " << state->s << endl;
254 else
255 fout << "\tcst " << *x << ": state " << state->s << endl;
256 return fout;
257 }
258
259 ostream& State::print(ostream& fout) const
260 {
261 fout << "state " << s << ":";
262 list<Rule>::const_iterator r;
263 for (r = rules.begin(); r != rules.end(); r++)
264 fout << " " << *r;
265 fout << endl;
266 list<Trans>::const_iterator t;
267 for (t = trans.begin(); t != trans.end(); t++)
268 fout << *t;
269 return fout;
270 }
271
272 ostream& Automaton::print(ostream& fout) const
273 {
274 int i, n = rhs.size();
275 for (i = 0; i < n; i++)
276 fout << "rule #" << i << ": " << *rhs[i] << endl;
277 n = state.size();
278 for (i = 0; i < n; i++)
279 fout << *state[i];
280 return fout;
281 }
282 #endif
283
284 /* Construction algorithm for the pattern matching automaton.
285 *
286 * We employ the incremental technique described in Graef: Left-To-Right Tree
287 * Pattern Matching, Proc. RTA 1991, Springer 1991 (LNCS 488) to construct a
288 * tree automaton (TA) for the given patterns. The basic outline of the
289 * technique is as follows. Initially, the automaton is empty. From each
290 * pattern we produce a trie (considering the pattern as a string of variable
291 * and function symbols and constants). This trie is then merged with the TA
292 * obtained so far. The latter process is similar to merging two deterministic
293 * finite automata, but it also takes into account the variables (see the
294 * merge_state() routine below).
295 */
296
297 /* Construct a trie from a term tree. Takes the "start" and returns the "end"
298 state of the (sub-)trie. */
299
300 static State *make_state(State *state, int r, Tree x, Path& p)
301 {
302 Tree id, x0, x1;
303 Node op(0);
304 if (isBoxPatternVar(x, id)) {
305 /* variable */
306 Rule rule(r, id, p);
307 state->rules.push_back(rule);
308 Trans trans(NULL);
309 state->trans.push_back(trans);
310 return state->trans.begin()->state;
311 } else if (isBoxPatternOp(x, op, x0, x1)) {
312 /* composite pattern */
313 Rule rule(r, NULL);
314 state->rules.push_back(rule);
315 Trans trans(op, 2);
316 state->trans.push_back(trans);
317 State *next = state->trans.begin()->state;
318 p.push_back(0);
319 next = make_state(next, r, x0, p);
320 p.pop_back();
321 p.push_back(1);
322 next = make_state(next, r, x1, p);
323 p.pop_back();
324 return next;
325 } else {
326 /* constant */
327 Rule rule(r, NULL);
328 state->rules.push_back(rule);
329 Trans trans(x);
330 state->trans.push_back(trans);
331 return state->trans.begin()->state;
332 }
333 }
334
335 /* Take a copy of a state and prefix it with n variable transitions. */
336
337 static State *make_var_state(int n, State *state)
338 {
339 if (n <= 0)
340 return new State(*state);
341 list<Rule>rules = state->rules;
342 list<Rule>::iterator r;
343 for (r = rules.begin(); r != rules.end(); r++) {
344 r->id = NULL; r->p = Path();
345 }
346 State *prefix = new State, *current = prefix;
347 while (n-- > 0) {
348 current->rules = rules;
349 Trans trans(NULL);
350 current->trans.push_back(trans);
351 current = current->trans.begin()->state;
352 }
353 *current = *state;
354 return prefix;
355 }
356
357 /* Merge two tree automata. Merges the tree automaton rooted at state2 into
358 the automaton rooted at state1. We assume that state2 is in "trie" form,
359 i.e., each state has at most one transition, which is always guaranteed
360 here and simplifies the algorithm. */
361
362 static void merge_state(State *state1, State *state2);
363
364 static void inline merge_rules(list<Rule>& rules1, list<Rule>& rules2)
365 {
366 list<Rule> cprules2 = rules2;
367 rules1.merge(cprules2);
368 }
369
370 static void merge_trans_var(list<Trans>& trans, State *state)
371 {
372 if (!trans.begin()->is_var_trans()) {
373 /* If we don't have a variable transition in this state yet then create a
374 new one. */
375 Trans tr(NULL);
376 trans.push_front(tr);
377 }
378 list<Trans>::const_iterator t;
379 Tree x;
380 Node op(0);
381 for (t = trans.begin(); t != trans.end(); t++) {
382 if (t->is_var_trans())
383 merge_state(t->state, state);
384 else if (t->is_cst_trans(x)) {
385 /* add the completion of the given state for a constant */
386 merge_state(t->state, state);
387 } else if (t->is_op_trans(op)) {
388 /* add the completion of the given state for an arity>0 op */
389 State *state1 = make_var_state(t->arity, state);
390 merge_state(t->state, state1);
391 delete state1;
392 }
393 }
394 }
395
396 static void merge_trans_cst(list<Trans>& trans, Tree x, State *state)
397 {
398 list<Trans>::iterator t0 = trans.begin(), t1 = t0, t;
399 Tree x1;
400 if (t0->is_var_trans()) t1++;
401 for (t = t1; t != trans.end(); t++) {
402 if (t->is_cst_trans(x1)) {
403 if (x == x1) {
404 merge_state(t->state, state);
405 return;
406 } else if (x < x1)
407 break;
408 }
409 }
410 /* no matching transition has been found; add a new one */
411 Trans tr(x);
412 trans.insert(t, tr); t--;
413 State *state1 = t->state;
414 *state1 = *state;
415 if (t1 != t0) {
416 /* if we have a variable transition in the current state, we also need to
417 merge its completion for the current symbol/constant */
418 merge_state(state1, t0->state);
419 }
420 }
421
422 static void merge_trans_op(list<Trans>& trans, const Node& op,
423 int arity, State *state)
424 {
425 /* analogous to merge_trans_cst above, but handles the arity>0 case */
426 list<Trans>::iterator t0 = trans.begin(), t1 = t0, t;
427 Node op1(0);
428 if (t0->is_var_trans()) t1++;
429 for (t = t1; t != trans.end(); t++) {
430 if (t->is_op_trans(op1)) {
431 if (op == op1) {
432 merge_state(t->state, state);
433 return;
434 } else if (op.getSym() < op1.getSym())
435 break;
436 }
437 }
438 Trans tr(op, arity);
439 trans.insert(t, tr); t--;
440 State *state1 = t->state;
441 *state1 = *state;
442 if (t1 != t0) {
443 State *state2 = make_var_state(arity, t0->state);
444 merge_state(state1, state2);
445 delete state2;
446 }
447 }
448
449 static void merge_trans(list<Trans>& trans1, list<Trans>& trans2)
450 {
451 Tree x;
452 Node op(0);
453 if (trans2.empty())
454 ;
455 else if (trans1.empty()) {
456 list<Trans> cptrans2 = trans2;
457 /* append a copy of trans2 to trans1 */
458 trans1.splice(trans1.end(), cptrans2);
459 } else if (trans2.begin()->is_var_trans())
460 /* merge a variable transition */
461 merge_trans_var(trans1, trans2.begin()->state);
462 else if (trans2.begin()->is_cst_trans(x))
463 /* merge a constant transition */
464 merge_trans_cst(trans1, x, trans2.begin()->state);
465 else if (trans2.begin()->is_op_trans(op))
466 /* merge a BDA op transition */
467 merge_trans_op(trans1, op, trans2.begin()->arity, trans2.begin()->state);
468 }
469
470 static void merge_state(State *state1, State *state2)
471 {
472 merge_rules(state1->rules, state2->rules);
473 merge_trans(state1->trans, state2->trans);
474 }
475
476 /* Take the rules of a BoxCase expression and return a pointer to the
477 corresponding TA automaton (interface operation). */
478
479 Automaton *make_pattern_matcher(Tree R)
480 /* Tree R encodes the rules of a case box expressions as a Tree object, as
481 follows:
482
483 Rules ::= cons Rule (cons Rule ... nil)
484 Rule ::= cons Lhs Rhs
485 Lhs ::= cons Pattern (cons Pattern ... nil)
486 Pattern ::= Tree (parameter pattern)
487 Rhs ::= Tree
488
489 NOTE: The lists of rules and patterns are actually delivered in reverse
490 order by the parser, so we have to reverse them on the fly. */
491 {
492 Automaton *A = new Automaton;
493 int n = len(R), r = n;
494 State *start = new State;
495 Tree rule, rest;
496 vector<Tree> rules(n, (Tree)NULL);
497 vector< vector<Tree> > testpats(n);
498 while (isCons(R, rule, rest)) {
499 rules[--r] = rule;
500 R = rest;
501 }
502 for (r = 0; r < n; r++) {
503 Tree lhs, rhs;
504 if (isCons(rules[r], lhs, rhs)) {
505 Tree pat, rest;
506 int m = len(lhs), i = m;
507 vector<Tree> pats(len(lhs), (Tree)NULL);
508 State *state0 = new State, *state = state0;
509 A->rhs.push_back(rhs);
510 while (isCons(lhs, pat, rest)) {
511 pats[--i] = pat;
512 lhs = rest;
513 }
514 testpats[r] = pats;
515 for (i = 0; i < m; i++) {
516 Path p;
517 state = make_state(state, r, pats[i], p);
518 }
519 Rule rule(r, NULL);
520 state->rules.push_back(rule);
521 merge_state(start, state0);
522 delete state0;
523 }
524 }
525 A->build(start);
526 /* Check for shadowed rules. Note that because of potential nonlinearities
527 it is *not* enough to just check the rule lists of final states and
528 determine whether they have multiple matched rules. */
529 for (r = 0; r < n; r++) {
530 int s = 0, m = testpats[r].size();
531 Tree C;
532 vector<Tree> E(n, nil);
533 /* try to match the lhs of rule #r */
534 for (int i = 0; i < m; i++) {
535 s = apply_pattern_matcher(A, s, testpats[r][i], C, E);
536 if (s < 0) break;
537 }
538 if (A->final(s)) {
539 list<Rule>::const_iterator ru;
540 for (ru = A->rules(s).begin(); ru != A->rules(s).end(); ru++)
541 if (!isBoxError(E[ru->r]))
542 if (ru->r < r) {
543 /* Lhs of rule #r matched a higher-priority rule, so rule #r may
544 be shadowed. */
545 Tree lhs1, rhs1, lhs2, rhs2;
546 if (isCons(rules[ru->r], lhs1, rhs1) && isCons(rules[r], lhs2, rhs2)) {
547 cerr << "WARNING : shadowed pattern-matching rule: "
548 << boxpp(reverse(lhs2)) << " => " << boxpp(rhs2) << ";"
549 << " previous rule was: "
550 << boxpp(reverse(lhs1)) << " => " << boxpp(rhs1) << ";"
551 << endl;
552 } else {
553 cerr << "INTERNAL ERROR : " << __FILE__ << ":" << __LINE__ << endl;
554 exit(1);
555 }
556 } else if (ru->r >= r)
557 break;
558 }
559 }
560 #ifdef DEBUG
561 cerr << "automaton " << A << endl << *A << "end automaton" << endl;
562 #endif
563 return A;
564 }
565
566 /* Helper type to represent variable substitutions which are recorded during
567 matching. Each variable is associated with the path pointing at the subterm
568 of the argument where the substitution of the matched variable is to be
569 found. */
570
571 struct Assoc {
572 Tree id;
573 Path p;
574 Assoc(Tree _id, const Path& _p) : id(_id), p(_p) {}
575 };
576 typedef list<Assoc> Subst;
577
578 /* add all substitutions for a given state */
579
580 static void add_subst(vector<Subst>& subst, Automaton *A, int s)
581 {
582 list<Rule> rules = A->rules(s);
583 list<Rule>::const_iterator r;
584 for (r = rules.begin(); r != rules.end(); r++)
585 if (r->id != NULL)
586 subst[r->r].push_back(Assoc(r->id, r->p));
587 }
588
589 /* Process a given term tree X starting from state s, modify variable
590 substitutions accordingly. Returns the resulting state, or -1 if no
591 match. This does all the grunt work of matching. */
592
593 static int apply_pattern_matcher_internal(Automaton *A, int s, Tree X,
594 vector<Subst>& subst)
595 {
596 /* FIXME: rewrite this non-recursively? */
597 if (s >= 0) {
598 list<Trans>::const_iterator t;
599 if (A->state[s]->match_num)
600 /* simplify possible numeric argument on the fly */
601 X = simplifyPattern(X);
602 /* first check for applicable non-variable transitions */
603 for (t = A->trans(s).begin(); t != A->trans(s).end(); t++) {
604 Tree x;
605 Node op(0), op1(0);
606 if (t->is_var_trans())
607 continue;
608 else if (t->is_cst_trans(x)) {
609 if (X==x) {
610 /* transition on constant */
611 #ifdef DEBUG
612 cerr << "state " << s << ", " << *x << ": goto state " << t->state->s << endl;
613 #endif
614 add_subst(subst, A, s);
615 s = t->state->s;
616 return s;
617 }
618 } else if (t->is_op_trans(op)) {
619 Tree x0, x1;
620 if (isBoxPatternOp(X, op1, x0, x1) && op == op1) {
621 /* transition on operation symbol */
622 #ifdef DEBUG
623 cerr << "state " << s << ", " << op << ": goto state " << t->state->s << endl;
624 #endif
625 add_subst(subst, A, s);
626 s = t->state->s;
627 if (s >= 0)
628 s = apply_pattern_matcher_internal(A, s, x0, subst);
629 if (s >= 0)
630 s = apply_pattern_matcher_internal(A, s, x1, subst);
631 return s;
632 }
633 }
634 }
635 /* check for variable transition (is always first in the list of
636 transitions) */
637 t = A->trans(s).begin();
638 if (t->is_var_trans()) {
639 #ifdef DEBUG
640 cerr << "state " << s << ", _: goto state " << t->state->s << endl;
641 #endif
642 add_subst(subst, A, s);
643 s = t->state->s;
644 } else {
645 #ifdef DEBUG
646 cerr << "state " << s << ", *** match failed ***" << endl;
647 #endif
648 s = -1;
649 }
650 }
651 return s;
652 }
653
654 /* Apply the pattern matcher to a single argument, starting from a given state
655 (interface operation). Returns the resulting state, modifies the variable
656 bindings E accordingly, and sets C to the resulting closure if a final
657 state is reached. Result will be -1 to indicate a matching failure, and C
658 will be set to nil if no final state has been reached yet. */
659
660 int apply_pattern_matcher(Automaton *A, // automaton
661 int s, // start state
662 Tree X, // arg to be matched
663 Tree& C, // output closure (if any)
664 vector<Tree>& E) // modified output environments
665 {
666 int n = A->n_rules();
667 vector<Subst> subst(n, Subst());
668 /* perform matching, record variable substitutions */
669 #ifdef DEBUG
670 cerr << "automaton " << A << ", state " << s << ", start match on arg: " << *X << endl;
671 #endif
672 s = apply_pattern_matcher_internal(A, s, X, subst);
673 C = nil;
674 if (s < 0)
675 /* failed match */
676 return s;
677 /* process variable substitutions */
678 list<Rule>::const_iterator r;
679 for (r = A->rules(s).begin(); r != A->rules(s).end(); r++) {
680 // all rules still active in state s
681 if (!isBoxError(E[r->r])) { // and still viable
682 Subst::const_iterator assoc;
683 for (assoc = subst[r->r].begin(); assoc != subst[r->r].end(); assoc++) {
684 Tree Z, Z1 = subtree(X, 0, assoc->p);
685 if (searchIdDef(assoc->id, Z, E[r->r])) {
686 if (Z != Z1) {
687 /* failed nonlinearity, add to the set of nonviable rules */
688 #ifdef DEBUG
689 cerr << "state " << s << ", rule #" << r->r << ": " <<
690 *assoc->id << " := " << *Z1 << " *** failed *** old value: " <<
691 *Z << endl;
692 #endif
693 E[r->r] = boxError();
694 }
695 } else {
696 /* bind a variable for the current rule */
697 #ifdef DEBUG
698 cerr << "state " << s << ", rule #" << r->r << ": " <<
699 *assoc->id << " := " << *Z1 << endl;
700 #endif
701 E[r->r] = pushValueDef(assoc->id, Z1, E[r->r]);
702 }
703 }
704 }
705 }
706 if (A->final(s)) {
707 /* if in a final state then return the right-hand side together with the
708 corresponding variable environment */
709 for (r = A->rules(s).begin(); r != A->rules(s).end(); r++) // all rules matched in state s
710 if (!isBoxError(E[r->r])) { // and still viable
711 /* return the rhs of the matched rule */
712 C = closure(A->rhs[r->r], nil, nil, E[r->r]);
713 #ifdef DEBUG
714 cerr << "state " << s << ", complete match yields rhs #" << r->r <<
715 ": " << *A->rhs[r->r] << endl;
716 #endif
717 return s;
718 }
719 /* if none of the rules were matched then declare a failed match */
720 #ifdef DEBUG
721 cerr << "state " << s << ", *** match failed ***" << endl;
722 #endif
723 return -1;
724 }
725 #ifdef DEBUG
726 cerr << "state " << s << ", successful incomplete match" << endl;
727 #endif
728 return s;
729 }