<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>FAUST compiler: patternmatcher.cpp Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<!-- Generated by Doxygen 1.6.3 -->
<div class="navigation" id="top">
<div class="tabs">
<ul>
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="annotated.html"><span>Classes</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
</ul>
</div>
<div class="tabs">
<ul>
<li><a href="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>File Members</span></a></li>
</ul>
</div>
<h1>patternmatcher.cpp</h1><a href="patternmatcher_8cpp.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001
<a name="l00002"></a>00002 <span class="comment">/* compiler/patternmatcher/patternmatcher.cpp: implementation of the Faust</span>
<a name="l00003"></a>00003 <span class="comment"> rewriting engine */</span>
<a name="l00004"></a>00004
<a name="l00005"></a>00005 <span class="preprocessor">#include "<a class="code" href="tlib_8hh.html">tlib.hh</a>"</span>
<a name="l00006"></a>00006 <span class="preprocessor">#include "<a class="code" href="list_8hh.html">list.hh</a>"</span>
<a name="l00007"></a>00007 <span class="preprocessor">#include "<a class="code" href="boxes_8hh.html">boxes.hh</a>"</span>
<a name="l00008"></a>00008 <span class="preprocessor">#include "<a class="code" href="ppbox_8hh.html">ppbox.hh</a>"</span>
<a name="l00009"></a>00009 <span class="preprocessor">#include "<a class="code" href="eval_8hh.html" title="Interface of the block diagram evaluator.">eval.hh</a>"</span>
<a name="l00010"></a>00010 <span class="preprocessor">#include "<a class="code" href="patternmatcher_8hh.html">patternmatcher.hh</a>"</span>
<a name="l00011"></a>00011
<a name="l00012"></a>00012 <span class="keyword">using namespace </span>std;
<a name="l00013"></a>00013 <span class="preprocessor">#include <vector></span>
<a name="l00014"></a>00014 <span class="preprocessor">#include <list></span>
<a name="l00015"></a>00015 <span class="preprocessor">#include <set></span>
<a name="l00016"></a>00016 <span class="preprocessor">#include <utility></span>
<a name="l00017"></a>00017
<a name="l00018"></a>00018 <span class="comment">/* Uncomment for debugging output. */</span>
<a name="l00019"></a>00019 <span class="comment">//#define DEBUG</span>
<a name="l00020"></a>00020
<a name="l00021"></a>00021 <span class="comment">/* Additional Tree deconstruction operations. */</span>
<a name="l00022"></a>00022
<a name="l00023"></a>00023 <span class="comment">/* Check for cons (nonempty list) nodes. */</span>
<a name="l00024"></a>00024
<a name="l00025"></a><a class="code" href="patternmatcher_8cpp.html#a50ea341d53b07dacd749c6bd25d57452">00025</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="patternmatcher_8cpp.html#a50ea341d53b07dacd749c6bd25d57452">isCons</a>(<a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> x, <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a>& h, <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a>& t)
<a name="l00026"></a>00026 {
<a name="l00027"></a>00027 <span class="keywordflow">if</span> (<a class="code" href="list_8hh.html#a8bdd73641276e0c0f999f504348eacc1">isList</a>(x)) {
<a name="l00028"></a>00028 h = <a class="code" href="list_8hh.html#a067ad6f83087b420a1c44e48e56be389">hd</a>(x); t = <a class="code" href="list_8hh.html#a4075748f5c7156306ec898795313a2e0">tl</a>(x);
<a name="l00029"></a>00029 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00030"></a>00030 } <span class="keywordflow">else</span>
<a name="l00031"></a>00031 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00032"></a>00032 }
<a name="l00033"></a>00033
<a name="l00034"></a>00034 <span class="comment">/* Deconstruct a (BDA) op pattern (YO). */</span>
<a name="l00035"></a>00035
<a name="l00036"></a><a class="code" href="patternmatcher_8cpp.html#a34cbd25863b5da67208a859cd4e39bb8">00036</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="patternmatcher_8cpp.html#a34cbd25863b5da67208a859cd4e39bb8">isBoxPatternOp</a>(<a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> box, <a class="code" href="classNode.html" title="Class Node = (type x (int + double + Sym + void*)).">Node</a>& n, <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a>& t1, <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a>& t2)
<a name="l00037"></a>00037 {
<a name="l00038"></a>00038 <span class="keywordflow">if</span> ( <a class="code" href="boxes_8cpp.html#a8a24d365092cfdabb32218ab8e446dc6">isBoxPar</a>(box, t1, t2) ||
<a name="l00039"></a>00039 <a class="code" href="boxes_8cpp.html#ad7c79f7a1c0aa3109ab0548e59194d48">isBoxSeq</a>(box, t1, t2) ||
<a name="l00040"></a>00040 <a class="code" href="boxes_8cpp.html#a654a2a97bdc734448e669899976bdbd0">isBoxSplit</a>(box, t1, t2) ||
<a name="l00041"></a>00041 <a class="code" href="boxes_8cpp.html#a7b7d0ce5bacf1a799517f7b50dfe7a3e">isBoxMerge</a>(box, t1, t2) ||
<a name="l00042"></a>00042 <a class="code" href="boxes_8cpp.html#a1b73cc14722de085e72c0a008fa56af3">isBoxHGroup</a>(box, t1, t2) ||
<a name="l00043"></a>00043 <a class="code" href="boxes_8cpp.html#a5643302db2568cf9eaa48fd6f7d336a9">isBoxVGroup</a>(box, t1, t2) ||
<a name="l00044"></a>00044 <a class="code" href="boxes_8cpp.html#a3e76d86869cc8b1df759a4bcb972cf2d">isBoxTGroup</a>(box, t1, t2) ||
<a name="l00045"></a>00045 <a class="code" href="boxes_8cpp.html#a97de4dc9680e2d0820a5d1d18255fa35">isBoxRec</a>(box, t1, t2) )
<a name="l00046"></a>00046 {
<a name="l00047"></a>00047 n = box-><a class="code" href="classCTree.html#a8de786fec095c8304b9ffa7c1c316237" title="return the content of the tree">node</a>();
<a name="l00048"></a>00048 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00049"></a>00049 } <span class="keywordflow">else</span> {
<a name="l00050"></a>00050 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00051"></a>00051 }
<a name="l00052"></a>00052 }
<a name="l00053"></a>00053
<a name="l00054"></a>00054 <span class="comment">/* TA data structures. */</span>
<a name="l00055"></a>00055
<a name="l00056"></a>00056 <span class="comment">/* subterm paths */</span>
<a name="l00057"></a>00057
<a name="l00058"></a><a class="code" href="patternmatcher_8cpp.html#a9d962b10c8fdb6619915dd0807f8fcec">00058</a> <span class="keyword">typedef</span> vector<int> <a class="code" href="patternmatcher_8cpp.html#a9d962b10c8fdb6619915dd0807f8fcec">Path</a>;
<a name="l00059"></a>00059
<a name="l00060"></a>00060 <span class="comment">/* Subterm at given path in given term tree. */</span>
<a name="l00061"></a>00061
<a name="l00062"></a><a class="code" href="patternmatcher_8cpp.html#abf5fce930015999bd6e95513ee9aee2a">00062</a> <span class="keyword">static</span> <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> <a class="code" href="patternmatcher_8cpp.html#abf5fce930015999bd6e95513ee9aee2a">subtree</a>(<a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> X, <span class="keywordtype">int</span> i, <span class="keyword">const</span> <a class="code" href="patternmatcher_8cpp.html#a9d962b10c8fdb6619915dd0807f8fcec">Path</a>& p)
<a name="l00063"></a>00063 {
<a name="l00064"></a>00064 <span class="keywordtype">int</span> n = p.size();
<a name="l00065"></a>00065 <a class="code" href="classNode.html" title="Class Node = (type x (int + double + Sym + void*)).">Node</a> op(0);
<a name="l00066"></a>00066 <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> x0, x1;
<a name="l00067"></a>00067 <span class="keywordflow">if</span> (i < n && <a class="code" href="patternmatcher_8cpp.html#a34cbd25863b5da67208a859cd4e39bb8">isBoxPatternOp</a>(X, op, x0, x1))
<a name="l00068"></a>00068 <span class="keywordflow">return</span> <a class="code" href="patternmatcher_8cpp.html#abf5fce930015999bd6e95513ee9aee2a">subtree</a>((p[i]==0)?x0:x1, i+1, p);
<a name="l00069"></a>00069 <span class="keywordflow">else</span>
<a name="l00070"></a>00070 <span class="keywordflow">return</span> X;
<a name="l00071"></a>00071 }
<a name="l00072"></a>00072
<a name="l00073"></a>00073 <span class="comment">/* rule markers */</span>
<a name="l00074"></a>00074
<a name="l00075"></a><a class="code" href="structRule.html">00075</a> <span class="keyword">struct </span><a class="code" href="structRule.html">Rule</a> {
<a name="l00076"></a><a class="code" href="structRule.html#ac6097dd32d7ca061023f151b572a1e5e">00076</a> <span class="keywordtype">int</span> <a class="code" href="structRule.html#ac6097dd32d7ca061023f151b572a1e5e">r</a>; <span class="comment">// rule number</span>
<a name="l00077"></a><a class="code" href="structRule.html#a41291d97b9ca70ebffda11a40a0772de">00077</a> <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> <a class="code" href="structRule.html#a41291d97b9ca70ebffda11a40a0772de">id</a>; <span class="comment">// matched variable (NULL if none)</span>
<a name="l00078"></a><a class="code" href="structRule.html#a3a6e90a688d4fe3082d17a62cbe2e6dc">00078</a> <a class="code" href="patternmatcher_8cpp.html#a9d962b10c8fdb6619915dd0807f8fcec">Path</a> <a class="code" href="structRule.html#a3a6e90a688d4fe3082d17a62cbe2e6dc">p</a>; <span class="comment">// subterm path indicating where variable value is found</span>
<a name="l00079"></a>00079
<a name="l00080"></a><a class="code" href="structRule.html#a08c7ed30058f87757a0f0984b805112f">00080</a> <a class="code" href="structRule.html#a08c7ed30058f87757a0f0984b805112f">Rule</a>(<span class="keywordtype">int</span> _r, <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> _id) : <a class="code" href="structRule.html#ac6097dd32d7ca061023f151b572a1e5e">r</a>(_r), <a class="code" href="structRule.html#a41291d97b9ca70ebffda11a40a0772de">id</a>(_id), <a class="code" href="structRule.html#a3a6e90a688d4fe3082d17a62cbe2e6dc">p</a>(<a class="code" href="patternmatcher_8cpp.html#a9d962b10c8fdb6619915dd0807f8fcec">Path</a>()) {}
<a name="l00081"></a><a class="code" href="structRule.html#a7eb37c534d07c6808a4153fc685a2298">00081</a> <a class="code" href="structRule.html#a7eb37c534d07c6808a4153fc685a2298">Rule</a>(<span class="keywordtype">int</span> _r, <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> _id, <span class="keyword">const</span> <a class="code" href="patternmatcher_8cpp.html#a9d962b10c8fdb6619915dd0807f8fcec">Path</a>& _p) : <a class="code" href="structRule.html#ac6097dd32d7ca061023f151b572a1e5e">r</a>(_r), <a class="code" href="structRule.html#a41291d97b9ca70ebffda11a40a0772de">id</a>(_id), <a class="code" href="structRule.html#a3a6e90a688d4fe3082d17a62cbe2e6dc">p</a>(_p) {}
<a name="l00082"></a><a class="code" href="structRule.html#afdab5cca4e8a31c807e6cf760e7479c8">00082</a> <a class="code" href="structRule.html#afdab5cca4e8a31c807e6cf760e7479c8">Rule</a>(<span class="keyword">const</span> <a class="code" href="structRule.html">Rule</a>& rule) : <a class="code" href="structRule.html#ac6097dd32d7ca061023f151b572a1e5e">r</a>(rule.<a class="code" href="structRule.html#ac6097dd32d7ca061023f151b572a1e5e">r</a>), <a class="code" href="structRule.html#a41291d97b9ca70ebffda11a40a0772de">id</a>(rule.<a class="code" href="structRule.html#a41291d97b9ca70ebffda11a40a0772de">id</a>), <a class="code" href="structRule.html#a3a6e90a688d4fe3082d17a62cbe2e6dc">p</a>(rule.<a class="code" href="structRule.html#a3a6e90a688d4fe3082d17a62cbe2e6dc">p</a>) {}
<a name="l00083"></a>00083
<a name="l00084"></a><a class="code" href="structRule.html#a1d1dc81d8e37cfc88f95de8eefb835f8">00084</a> <a class="code" href="structRule.html">Rule</a>& <a class="code" href="structRule.html#a1d1dc81d8e37cfc88f95de8eefb835f8">operator = </a>(<span class="keyword">const</span> <a class="code" href="structRule.html">Rule</a>& rule)
<a name="l00085"></a>00085 { <a class="code" href="structRule.html#ac6097dd32d7ca061023f151b572a1e5e">r</a> = rule.<a class="code" href="structRule.html#ac6097dd32d7ca061023f151b572a1e5e">r</a>; <span class="keywordtype">id</span> = rule.<a class="code" href="structRule.html#a41291d97b9ca70ebffda11a40a0772de">id</a>; <a class="code" href="structRule.html#a3a6e90a688d4fe3082d17a62cbe2e6dc">p</a> = rule.<a class="code" href="structRule.html#a3a6e90a688d4fe3082d17a62cbe2e6dc">p</a>; <span class="keywordflow">return</span> *<span class="keyword">this</span>; }
<a name="l00086"></a>00086
<a name="l00087"></a><a class="code" href="structRule.html#a77f742fc7f51a37f0271dc3c9dc70a05">00087</a> <span class="keywordtype">bool</span> <a class="code" href="structRule.html#a77f742fc7f51a37f0271dc3c9dc70a05">operator == </a>(<span class="keyword">const</span> <a class="code" href="structRule.html">Rule</a>& rule)<span class="keyword"> const</span>
<a name="l00088"></a>00088 <span class="keyword"> </span>{ <span class="keywordflow">return</span> <a class="code" href="structRule.html#ac6097dd32d7ca061023f151b572a1e5e">r</a> == rule.<a class="code" href="structRule.html#ac6097dd32d7ca061023f151b572a1e5e">r</a>; }
<a name="l00089"></a><a class="code" href="structRule.html#a0531d32ba4712d2f2c0ad32ad91b3c81">00089</a> <span class="keywordtype">bool</span> <a class="code" href="structRule.html#a0531d32ba4712d2f2c0ad32ad91b3c81">operator < </a>(<span class="keyword">const</span> <a class="code" href="structRule.html">Rule</a>& rule)<span class="keyword"> const</span>
<a name="l00090"></a>00090 <span class="keyword"> </span>{ <span class="keywordflow">return</span> <a class="code" href="structRule.html#ac6097dd32d7ca061023f151b572a1e5e">r</a> < rule.<a class="code" href="structRule.html#ac6097dd32d7ca061023f151b572a1e5e">r</a>; }
<a name="l00091"></a>00091
<a name="l00092"></a>00092 <span class="preprocessor">#ifdef DEBUG</span>
<a name="l00093"></a>00093 <span class="preprocessor"></span> ostream& <a class="code" href="list_8cpp.html#a850f2e459a901e0c9908d3a3a54b306e">print</a>(ostream& fout) <span class="keyword">const</span>;
<a name="l00094"></a>00094 <span class="preprocessor">#endif</span>
<a name="l00095"></a>00095 <span class="preprocessor"></span>};
<a name="l00096"></a>00096
<a name="l00097"></a>00097 <span class="keyword">struct </span><a class="code" href="structState.html">State</a>;
<a name="l00098"></a>00098
<a name="l00099"></a>00099 <span class="comment">/* transitions */</span>
<a name="l00100"></a>00100
<a name="l00101"></a><a class="code" href="structTrans.html">00101</a> <span class="keyword">struct </span><a class="code" href="structTrans.html">Trans</a> {
<a name="l00102"></a><a class="code" href="structTrans.html#a483dd010b4dfda68a38f24817fc6e502">00102</a> <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> <a class="code" href="structTrans.html#a483dd010b4dfda68a38f24817fc6e502">x</a>; <span class="comment">// symbol or constant (NULL for variable)</span>
<a name="l00103"></a><a class="code" href="structTrans.html#afcf20306d837dfceefa94998f3a731ba">00103</a> <a class="code" href="classNode.html" title="Class Node = (type x (int + double + Sym + void*)).">Node</a> <a class="code" href="structTrans.html#afcf20306d837dfceefa94998f3a731ba">n</a>; <span class="comment">// operator symbol (if arity>0)</span>
<a name="l00104"></a><a class="code" href="structTrans.html#a31e295ad281faabe3253735ba133b481">00104</a> <span class="keywordtype">int</span> <a class="code" href="structTrans.html#a31e295ad281faabe3253735ba133b481">arity</a>; <span class="comment">// symbol arity</span>
<a name="l00105"></a><a class="code" href="structTrans.html#a0b2b7f7c785a12189d3c8f2a7945982a">00105</a> <a class="code" href="structState.html">State</a> *<a class="code" href="structTrans.html#a0b2b7f7c785a12189d3c8f2a7945982a">state</a>; <span class="comment">// successor state</span>
<a name="l00106"></a>00106
<a name="l00107"></a>00107 <a class="code" href="structTrans.html#acba0416dcf23214d202b5b5070bfe0c9">Trans</a>(<a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> _x);
<a name="l00108"></a>00108 <a class="code" href="structTrans.html#acba0416dcf23214d202b5b5070bfe0c9">Trans</a>(<span class="keyword">const</span> <a class="code" href="classNode.html" title="Class Node = (type x (int + double + Sym + void*)).">Node</a>& _n, <span class="keywordtype">int</span> _arity);
<a name="l00109"></a>00109 <a class="code" href="structTrans.html#acba0416dcf23214d202b5b5070bfe0c9">Trans</a>(<span class="keyword">const</span> <a class="code" href="structTrans.html">Trans</a>& trans);
<a name="l00110"></a>00110 <a class="code" href="structTrans.html#a147afaa3bea4d31de21da3a355433549">~Trans</a>();
<a name="l00111"></a>00111
<a name="l00112"></a>00112 <a class="code" href="structTrans.html">Trans</a>& <a class="code" href="structTrans.html#a4e656fffa98802f441b7555729b2e933">operator = </a>(<span class="keyword">const</span> <a class="code" href="structTrans.html">Trans</a>& trans);
<a name="l00113"></a>00113
<a name="l00114"></a><a class="code" href="structTrans.html#aaf272c8c6f0592f744fb9cd13e62bdaf">00114</a> <span class="keywordtype">bool</span> <a class="code" href="structTrans.html#aaf272c8c6f0592f744fb9cd13e62bdaf">is_var_trans</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="structTrans.html#a31e295ad281faabe3253735ba133b481">arity</a> == 0 && <a class="code" href="structTrans.html#a483dd010b4dfda68a38f24817fc6e502">x</a> == NULL; }
<a name="l00115"></a><a class="code" href="structTrans.html#a12430a0802d69209f784113757a40609">00115</a> <span class="keywordtype">bool</span> <a class="code" href="structTrans.html#a12430a0802d69209f784113757a40609">is_cst_trans</a>(<a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> &_x)<span class="keyword"> const </span>{ _x = <a class="code" href="structTrans.html#a483dd010b4dfda68a38f24817fc6e502">x</a>; <span class="keywordflow">return</span> <a class="code" href="structTrans.html#a31e295ad281faabe3253735ba133b481">arity</a> == 0 && <a class="code" href="structTrans.html#a483dd010b4dfda68a38f24817fc6e502">x</a> != NULL; }
<a name="l00116"></a><a class="code" href="structTrans.html#a5c406e56ce83bdfd90f9bc0845af36f4">00116</a> <span class="keywordtype">bool</span> <a class="code" href="structTrans.html#a5c406e56ce83bdfd90f9bc0845af36f4">is_op_trans</a>(<a class="code" href="classNode.html" title="Class Node = (type x (int + double + Sym + void*)).">Node</a> &_n)<span class="keyword"> const </span>{ _n = <a class="code" href="structTrans.html#afcf20306d837dfceefa94998f3a731ba">n</a>; <span class="keywordflow">return</span> <a class="code" href="structTrans.html#a31e295ad281faabe3253735ba133b481">arity</a> > 0; }
<a name="l00117"></a>00117
<a name="l00118"></a><a class="code" href="structTrans.html#a72ba3a050ef71f88a66f7dd1619cf837">00118</a> <span class="keywordtype">bool</span> <a class="code" href="structTrans.html#a72ba3a050ef71f88a66f7dd1619cf837">operator == </a>(<span class="keyword">const</span> <a class="code" href="structTrans.html">Trans</a>& trans)<span class="keyword"> const</span>
<a name="l00119"></a>00119 <span class="keyword"> </span>{ <span class="keywordflow">return</span> <a class="code" href="structTrans.html#a31e295ad281faabe3253735ba133b481">arity</a> == trans.<a class="code" href="structTrans.html#a31e295ad281faabe3253735ba133b481">arity</a> && <a class="code" href="structTrans.html#a483dd010b4dfda68a38f24817fc6e502">x</a> == trans.<a class="code" href="structTrans.html#a483dd010b4dfda68a38f24817fc6e502">x</a> && <a class="code" href="structTrans.html#afcf20306d837dfceefa94998f3a731ba">n</a> == trans.<a class="code" href="structTrans.html#afcf20306d837dfceefa94998f3a731ba">n</a>; }
<a name="l00120"></a><a class="code" href="structTrans.html#a5dc5de24ace17887b77b8f13ce38f55b">00120</a> <span class="keywordtype">bool</span> <a class="code" href="structTrans.html#a5dc5de24ace17887b77b8f13ce38f55b">operator < </a>(<span class="keyword">const</span> <a class="code" href="structTrans.html">Trans</a>& trans)<span class="keyword"> const</span>
<a name="l00121"></a>00121 <span class="keyword"> </span>{ <span class="keywordflow">return</span> (<a class="code" href="structTrans.html#a31e295ad281faabe3253735ba133b481">arity</a> < trans.<a class="code" href="structTrans.html#a31e295ad281faabe3253735ba133b481">arity</a>) ? 1 :
<a name="l00122"></a>00122 (<a class="code" href="structTrans.html#a31e295ad281faabe3253735ba133b481">arity</a> > trans.<a class="code" href="structTrans.html#a31e295ad281faabe3253735ba133b481">arity</a>) ? 0 :
<a name="l00123"></a>00123 (<a class="code" href="structTrans.html#a31e295ad281faabe3253735ba133b481">arity</a> == 0) ? (<a class="code" href="structTrans.html#a483dd010b4dfda68a38f24817fc6e502">x</a> < trans.<a class="code" href="structTrans.html#a483dd010b4dfda68a38f24817fc6e502">x</a>) :
<a name="l00124"></a>00124 (<a class="code" href="structTrans.html#afcf20306d837dfceefa94998f3a731ba">n</a>.<a class="code" href="classNode.html#a9e9dc25c550f5a1fa55a68ff3c5d81cf">getSym</a>() < trans.<a class="code" href="structTrans.html#afcf20306d837dfceefa94998f3a731ba">n</a>.<a class="code" href="classNode.html#a9e9dc25c550f5a1fa55a68ff3c5d81cf">getSym</a>()); }
<a name="l00125"></a>00125
<a name="l00126"></a>00126 <span class="preprocessor">#ifdef DEBUG</span>
<a name="l00127"></a>00127 <span class="preprocessor"></span> ostream& <a class="code" href="list_8cpp.html#a850f2e459a901e0c9908d3a3a54b306e">print</a>(ostream& fout) <span class="keyword">const</span>;
<a name="l00128"></a>00128 <span class="preprocessor">#endif</span>
<a name="l00129"></a>00129 <span class="preprocessor"></span>};
<a name="l00130"></a>00130
<a name="l00131"></a>00131 <span class="comment">/* states */</span>
<a name="l00132"></a>00132
<a name="l00133"></a><a class="code" href="structState.html">00133</a> <span class="keyword">struct </span><a class="code" href="structState.html">State</a> {
<a name="l00134"></a><a class="code" href="structState.html#a6145c011cb54cbc1f482a40892225f02">00134</a> <span class="keywordtype">int</span> <a class="code" href="structState.html#a6145c011cb54cbc1f482a40892225f02">s</a>; <span class="comment">// state number</span>
<a name="l00135"></a><a class="code" href="structState.html#a2225f67349e58c22f65984327e0928da">00135</a> <span class="keywordtype">bool</span> <a class="code" href="structState.html#a2225f67349e58c22f65984327e0928da">match_num</a>; <span class="comment">// whether state has a transition on a numeric constant</span>
<a name="l00136"></a><a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">00136</a> list<Rule> <a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">rules</a>; <span class="comment">// rule markers</span>
<a name="l00137"></a><a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">00137</a> list<Trans> <a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>; <span class="comment">// transitions (1st transition is on variable if available)</span>
<a name="l00138"></a><a class="code" href="structState.html#ab91bb1dd5aa6260ab2a456581daf9ec2">00138</a> <a class="code" href="structState.html#ab91bb1dd5aa6260ab2a456581daf9ec2">State</a>() :
<a name="l00139"></a>00139 <a class="code" href="structState.html#a6145c011cb54cbc1f482a40892225f02">s</a>(0), <a class="code" href="structState.html#a2225f67349e58c22f65984327e0928da">match_num</a>(false), <a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">rules</a>(list<<a class="code" href="structRule.html">Rule</a>>()), <a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>(list<<a class="code" href="structTrans.html">Trans</a>>()) {}
<a name="l00140"></a><a class="code" href="structState.html#a5107a6d9c2cd2ae0da0a32c13b1e906f">00140</a> <a class="code" href="structState.html#ab91bb1dd5aa6260ab2a456581daf9ec2">State</a>(<span class="keyword">const</span> <a class="code" href="structState.html">State</a>& state) :
<a name="l00141"></a>00141 <a class="code" href="structState.html#a6145c011cb54cbc1f482a40892225f02">s</a>(state.<a class="code" href="structState.html#a6145c011cb54cbc1f482a40892225f02">s</a>), <a class="code" href="structState.html#a2225f67349e58c22f65984327e0928da">match_num</a>(state.<a class="code" href="structState.html#a2225f67349e58c22f65984327e0928da">match_num</a>),
<a name="l00142"></a>00142 <a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">rules</a>(state.<a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">rules</a>), <a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>(state.<a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>) {}
<a name="l00143"></a>00143
<a name="l00144"></a><a class="code" href="structState.html#a67566f0eb8783b288fadbe5904e1716f">00144</a> <a class="code" href="structState.html">State</a>& <a class="code" href="structState.html#a67566f0eb8783b288fadbe5904e1716f">operator = </a>(<span class="keyword">const</span> <a class="code" href="structState.html">State</a>& state)
<a name="l00145"></a>00145 { <a class="code" href="structState.html#a6145c011cb54cbc1f482a40892225f02">s</a> = state.<a class="code" href="structState.html#a6145c011cb54cbc1f482a40892225f02">s</a>; <a class="code" href="structState.html#a2225f67349e58c22f65984327e0928da">match_num</a> = state.<a class="code" href="structState.html#a2225f67349e58c22f65984327e0928da">match_num</a>;
<a name="l00146"></a>00146 <a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">rules</a> = state.<a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">rules</a>; <a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a> = state.<a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>;
<a name="l00147"></a>00147 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00148"></a>00148 }
<a name="l00149"></a>00149
<a name="l00150"></a>00150 <span class="preprocessor">#ifdef DEBUG</span>
<a name="l00151"></a>00151 <span class="preprocessor"></span> ostream& <a class="code" href="list_8cpp.html#a850f2e459a901e0c9908d3a3a54b306e">print</a>(ostream& fout) <span class="keyword">const</span>;
<a name="l00152"></a>00152 <span class="preprocessor">#endif</span>
<a name="l00153"></a>00153 <span class="preprocessor"></span>};
<a name="l00154"></a>00154
<a name="l00155"></a>00155 <span class="comment">// these need to come here so that the storage size of struct State is known</span>
<a name="l00156"></a>00156
<a name="l00157"></a><a class="code" href="structTrans.html#acba0416dcf23214d202b5b5070bfe0c9">00157</a> <a class="code" href="structTrans.html#acba0416dcf23214d202b5b5070bfe0c9">Trans::Trans</a>(<a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> _x) :
<a name="l00158"></a>00158 x(_x), n(0), arity(0), state(new <a class="code" href="structState.html">State</a>)
<a name="l00159"></a>00159 {
<a name="l00160"></a>00160 }
<a name="l00161"></a>00161
<a name="l00162"></a><a class="code" href="structTrans.html#a54807e64e96801abb1a4cf5f0085c6b5">00162</a> <a class="code" href="structTrans.html#acba0416dcf23214d202b5b5070bfe0c9">Trans::Trans</a>(<span class="keyword">const</span> <a class="code" href="classNode.html" title="Class Node = (type x (int + double + Sym + void*)).">Node</a>& _n, <span class="keywordtype">int</span> _arity) :
<a name="l00163"></a>00163 x(NULL), n(_n), arity(_arity), state(new <a class="code" href="structState.html">State</a>)
<a name="l00164"></a>00164 {
<a name="l00165"></a>00165 }
<a name="l00166"></a>00166
<a name="l00167"></a><a class="code" href="structTrans.html#a7b0985d339397607d97e8ca8d015d0a0">00167</a> <a class="code" href="structTrans.html#acba0416dcf23214d202b5b5070bfe0c9">Trans::Trans</a>(<span class="keyword">const</span> <a class="code" href="structTrans.html">Trans</a>& trans) :
<a name="l00168"></a>00168 x(trans.x), n(trans.n), arity(trans.arity)
<a name="l00169"></a>00169 {
<a name="l00170"></a>00170 <a class="code" href="structTrans.html#a0b2b7f7c785a12189d3c8f2a7945982a">state</a> = <span class="keyword">new</span> <a class="code" href="structState.html">State</a>(*trans.<a class="code" href="structTrans.html#a0b2b7f7c785a12189d3c8f2a7945982a">state</a>);
<a name="l00171"></a>00171 }
<a name="l00172"></a>00172
<a name="l00173"></a><a class="code" href="structTrans.html#a147afaa3bea4d31de21da3a355433549">00173</a> <a class="code" href="structTrans.html#a147afaa3bea4d31de21da3a355433549">Trans::~Trans</a>()
<a name="l00174"></a>00174 {
<a name="l00175"></a>00175 <span class="keyword">delete</span> <a class="code" href="structTrans.html#a0b2b7f7c785a12189d3c8f2a7945982a">state</a>;
<a name="l00176"></a>00176 }
<a name="l00177"></a>00177
<a name="l00178"></a><a class="code" href="structTrans.html#a4e656fffa98802f441b7555729b2e933">00178</a> <a class="code" href="structTrans.html">Trans</a>& <a class="code" href="structTrans.html#a4e656fffa98802f441b7555729b2e933">Trans::operator = </a>(<span class="keyword">const</span> <a class="code" href="structTrans.html">Trans</a>& trans)
<a name="l00179"></a>00179 {
<a name="l00180"></a>00180 <a class="code" href="structTrans.html#a483dd010b4dfda68a38f24817fc6e502">x</a> = trans.<a class="code" href="structTrans.html#a483dd010b4dfda68a38f24817fc6e502">x</a>; <a class="code" href="structTrans.html#afcf20306d837dfceefa94998f3a731ba">n</a> = trans.<a class="code" href="structTrans.html#afcf20306d837dfceefa94998f3a731ba">n</a>; <a class="code" href="structTrans.html#a31e295ad281faabe3253735ba133b481">arity</a> = trans.<a class="code" href="structTrans.html#a31e295ad281faabe3253735ba133b481">arity</a>;
<a name="l00181"></a>00181 <a class="code" href="structTrans.html#a0b2b7f7c785a12189d3c8f2a7945982a">state</a> = <span class="keyword">new</span> <a class="code" href="structState.html">State</a>(*trans.<a class="code" href="structTrans.html#a0b2b7f7c785a12189d3c8f2a7945982a">state</a>);
<a name="l00182"></a>00182 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00183"></a>00183 }
<a name="l00184"></a>00184
<a name="l00185"></a>00185 <span class="comment">/* the automaton */</span>
<a name="l00186"></a>00186
<a name="l00187"></a><a class="code" href="structAutomaton.html">00187</a> <span class="keyword">struct </span><a class="code" href="structAutomaton.html">Automaton</a> {
<a name="l00188"></a><a class="code" href="structAutomaton.html#ae12943b3fadba9d0c0984cc0fa839efb">00188</a> vector<State*> <a class="code" href="structAutomaton.html#ae12943b3fadba9d0c0984cc0fa839efb">state</a>;
<a name="l00189"></a><a class="code" href="structAutomaton.html#a11d18ab1675e9d32433e799a2b20d26e">00189</a> vector<Tree> <a class="code" href="structAutomaton.html#a11d18ab1675e9d32433e799a2b20d26e">rhs</a>;
<a name="l00190"></a>00190
<a name="l00191"></a><a class="code" href="structAutomaton.html#a5d2b6e09517175faea87c5724cc3edea">00191</a> <a class="code" href="structAutomaton.html#a5d2b6e09517175faea87c5724cc3edea">Automaton</a>() : <a class="code" href="structAutomaton.html#ae12943b3fadba9d0c0984cc0fa839efb">state</a>(vector<<a class="code" href="structState.html">State</a>*>()), <a class="code" href="structAutomaton.html#a11d18ab1675e9d32433e799a2b20d26e">rhs</a>(vector<<a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a>>()), <a class="code" href="structAutomaton.html#a12b5aa75d9587716b139bc41fbb5d695">s</a>(0) {}
<a name="l00192"></a>00192
<a name="l00193"></a>00193 <span class="comment">// number of rules</span>
<a name="l00194"></a><a class="code" href="structAutomaton.html#ac244771866c62c3bbca1ec5201d5ed54">00194</a> <span class="keywordtype">int</span> <a class="code" href="structAutomaton.html#ac244771866c62c3bbca1ec5201d5ed54">n_rules</a>() { <span class="keywordflow">return</span> <a class="code" href="structAutomaton.html#a11d18ab1675e9d32433e799a2b20d26e">rhs</a>.size(); }
<a name="l00195"></a>00195 <span class="comment">// markers of rules still active in state s</span>
<a name="l00196"></a><a class="code" href="structAutomaton.html#adb969b0985e71dd5415ed70369b937f4">00196</a> <span class="keyword">const</span> list<Rule>& <a class="code" href="structAutomaton.html#adb969b0985e71dd5415ed70369b937f4">rules</a>(<span class="keywordtype">int</span> <a class="code" href="structAutomaton.html#a12b5aa75d9587716b139bc41fbb5d695">s</a>) { <span class="keywordflow">return</span> <a class="code" href="structAutomaton.html#ae12943b3fadba9d0c0984cc0fa839efb">state</a>[s]->rules; }
<a name="l00197"></a>00197 <span class="comment">// transitions in state s</span>
<a name="l00198"></a><a class="code" href="structAutomaton.html#a0f1678cbdb43070122bb9d6caa841697">00198</a> <span class="keyword">const</span> list<Trans>& <a class="code" href="structAutomaton.html#a0f1678cbdb43070122bb9d6caa841697">trans</a>(<span class="keywordtype">int</span> <a class="code" href="structAutomaton.html#a12b5aa75d9587716b139bc41fbb5d695">s</a>) { <span class="keywordflow">return</span> <a class="code" href="structAutomaton.html#ae12943b3fadba9d0c0984cc0fa839efb">state</a>[s]->trans; }
<a name="l00199"></a>00199 <span class="comment">// is s a final state?</span>
<a name="l00200"></a><a class="code" href="structAutomaton.html#a92020994f3a89b85ac0f8f6ccd3273ff">00200</a> <span class="keywordtype">bool</span> <span class="keyword">final</span>(<span class="keywordtype">int</span> <a class="code" href="structAutomaton.html#a12b5aa75d9587716b139bc41fbb5d695">s</a>) { <span class="keywordflow">return</span> <a class="code" href="structAutomaton.html#a0f1678cbdb43070122bb9d6caa841697">trans</a>(<a class="code" href="structAutomaton.html#a12b5aa75d9587716b139bc41fbb5d695">s</a>).empty(); }
<a name="l00201"></a>00201
<a name="l00202"></a>00202 <span class="comment">// assign state numbers and build the state table</span>
<a name="l00203"></a><a class="code" href="structAutomaton.html#a12b5aa75d9587716b139bc41fbb5d695">00203</a> <span class="keywordtype">int</span> <a class="code" href="structAutomaton.html#a12b5aa75d9587716b139bc41fbb5d695">s</a>;
<a name="l00204"></a>00204 <span class="keywordtype">void</span> <a class="code" href="structAutomaton.html#a3305f434c8c0e6b2d3e446da7cd4ec74">build</a>(<a class="code" href="structState.html">State</a> *st);
<a name="l00205"></a>00205
<a name="l00206"></a>00206 <span class="preprocessor">#ifdef DEBUG</span>
<a name="l00207"></a>00207 <span class="preprocessor"></span> ostream& <a class="code" href="list_8cpp.html#a850f2e459a901e0c9908d3a3a54b306e">print</a>(ostream& fout) <span class="keyword">const</span>;
<a name="l00208"></a>00208 <span class="preprocessor">#endif</span>
<a name="l00209"></a>00209 <span class="preprocessor"></span>};
<a name="l00210"></a>00210
<a name="l00211"></a><a class="code" href="structAutomaton.html#a3305f434c8c0e6b2d3e446da7cd4ec74">00211</a> <span class="keywordtype">void</span> <a class="code" href="structAutomaton.html#a3305f434c8c0e6b2d3e446da7cd4ec74">Automaton::build</a>(<a class="code" href="structState.html">State</a> *st)
<a name="l00212"></a>00212 {
<a name="l00213"></a>00213 <a class="code" href="structAutomaton.html#ae12943b3fadba9d0c0984cc0fa839efb">state</a>.push_back(st);
<a name="l00214"></a>00214 st-><a class="code" href="structState.html#a6145c011cb54cbc1f482a40892225f02">s</a> = <a class="code" href="structAutomaton.html#a12b5aa75d9587716b139bc41fbb5d695">s</a>++;
<a name="l00215"></a>00215 list<Trans>::const_iterator t;
<a name="l00216"></a>00216 <span class="keywordflow">for</span> (t = st-><a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>.begin(); t != st-><a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>.end(); t++) {
<a name="l00217"></a>00217 <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> x;
<a name="l00218"></a>00218 <span class="keywordtype">double</span> f;
<a name="l00219"></a>00219 <span class="keywordtype">int</span> i;
<a name="l00220"></a>00220 <span class="keywordflow">if</span> (t->is_cst_trans(x) &&
<a name="l00221"></a>00221 (<a class="code" href="boxes_8cpp.html#a7904414896442fcfa0947156b6563d52">isBoxInt</a>(x, &i) || <a class="code" href="boxes_8cpp.html#a292a68d93ea73f703bc880cca4d01bc2">isBoxReal</a>(x, &f)))
<a name="l00222"></a>00222 st-><a class="code" href="structState.html#a2225f67349e58c22f65984327e0928da">match_num</a> = <span class="keyword">true</span>;
<a name="l00223"></a>00223 <a class="code" href="structAutomaton.html#a3305f434c8c0e6b2d3e446da7cd4ec74">build</a>(t->state);
<a name="l00224"></a>00224 }
<a name="l00225"></a>00225 }
<a name="l00226"></a>00226
<a name="l00227"></a>00227 <span class="comment">/* Debugging output. */</span>
<a name="l00228"></a>00228
<a name="l00229"></a>00229 <span class="preprocessor">#ifdef DEBUG</span>
<a name="l00230"></a>00230 <span class="preprocessor"></span><span class="keyword">inline</span> ostream& <a class="code" href="ppbox_8hh.html#a23b1718100bac6cb41d43dd01f226eef">operator << </a>(ostream& s, <span class="keyword">const</span> <a class="code" href="structRule.html">Rule</a>& x)
<a name="l00231"></a>00231 { <span class="keywordflow">return</span> x.print(s); }
<a name="l00232"></a>00232 <span class="keyword">inline</span> ostream& <a class="code" href="ppbox_8hh.html#a23b1718100bac6cb41d43dd01f226eef">operator << </a>(ostream& s, <span class="keyword">const</span> <a class="code" href="structTrans.html">Trans</a>& x)
<a name="l00233"></a>00233 { <span class="keywordflow">return</span> x.print(s); }
<a name="l00234"></a>00234 <span class="keyword">inline</span> ostream& <a class="code" href="ppbox_8hh.html#a23b1718100bac6cb41d43dd01f226eef">operator << </a>(ostream& s, <span class="keyword">const</span> <a class="code" href="structState.html">State</a>& x)
<a name="l00235"></a>00235 { <span class="keywordflow">return</span> x.print(s); }
<a name="l00236"></a>00236 <span class="keyword">inline</span> ostream& <a class="code" href="ppbox_8hh.html#a23b1718100bac6cb41d43dd01f226eef">operator << </a>(ostream& s, <span class="keyword">const</span> <a class="code" href="structAutomaton.html">Automaton</a>& x)
<a name="l00237"></a>00237 { <span class="keywordflow">return</span> x.print(s); }
<a name="l00238"></a>00238
<a name="l00239"></a>00239 ostream& <a class="code" href="list_8cpp.html#a850f2e459a901e0c9908d3a3a54b306e">Rule::print</a>(ostream& fout)<span class="keyword"> const</span>
<a name="l00240"></a>00240 <span class="keyword"></span>{
<a name="l00241"></a>00241 <span class="keywordflow">if</span> (<span class="keywordtype">id</span> != NULL)
<a name="l00242"></a>00242 fout << <span class="stringliteral">"#"</span> << <a class="code" href="structRule.html#ac6097dd32d7ca061023f151b572a1e5e">r</a> << <span class="stringliteral">"("</span> << *<span class="keywordtype">id</span> << <span class="stringliteral">")"</span>;
<a name="l00243"></a>00243 <span class="keywordflow">else</span>
<a name="l00244"></a>00244 fout << <span class="stringliteral">"#"</span> << <a class="code" href="structRule.html#ac6097dd32d7ca061023f151b572a1e5e">r</a>;
<a name="l00245"></a>00245 <span class="keywordflow">return</span> fout;
<a name="l00246"></a>00246 }
<a name="l00247"></a>00247
<a name="l00248"></a>00248 ostream& <a class="code" href="list_8cpp.html#a850f2e459a901e0c9908d3a3a54b306e">Trans::print</a>(ostream& fout)<span class="keyword"> const</span>
<a name="l00249"></a>00249 <span class="keyword"></span>{
<a name="l00250"></a>00250 <span class="keywordflow">if</span> (<a class="code" href="structTrans.html#a31e295ad281faabe3253735ba133b481">arity</a> > 0)
<a name="l00251"></a>00251 fout << <span class="stringliteral">"\top "</span> << <a class="code" href="structTrans.html#afcf20306d837dfceefa94998f3a731ba">n</a> << <span class="stringliteral">": state "</span> << <a class="code" href="structTrans.html#a0b2b7f7c785a12189d3c8f2a7945982a">state</a>-><a class="code" href="structState.html#a6145c011cb54cbc1f482a40892225f02">s</a> << endl;
<a name="l00252"></a>00252 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (x == NULL)
<a name="l00253"></a>00253 fout << <span class="stringliteral">"\tvar _: state "</span> << <a class="code" href="structTrans.html#a0b2b7f7c785a12189d3c8f2a7945982a">state</a>-><a class="code" href="structState.html#a6145c011cb54cbc1f482a40892225f02">s</a> << endl;
<a name="l00254"></a>00254 <span class="keywordflow">else</span>
<a name="l00255"></a>00255 fout << <span class="stringliteral">"\tcst "</span> << *x << <span class="stringliteral">": state "</span> << <a class="code" href="structTrans.html#a0b2b7f7c785a12189d3c8f2a7945982a">state</a>-><a class="code" href="structState.html#a6145c011cb54cbc1f482a40892225f02">s</a> << endl;
<a name="l00256"></a>00256 <span class="keywordflow">return</span> fout;
<a name="l00257"></a>00257 }
<a name="l00258"></a>00258
<a name="l00259"></a>00259 ostream& <a class="code" href="list_8cpp.html#a850f2e459a901e0c9908d3a3a54b306e">State::print</a>(ostream& fout)<span class="keyword"> const</span>
<a name="l00260"></a>00260 <span class="keyword"></span>{
<a name="l00261"></a>00261 fout << <span class="stringliteral">"state "</span> << s << <span class="stringliteral">":"</span>;
<a name="l00262"></a>00262 list<Rule>::const_iterator r;
<a name="l00263"></a>00263 <span class="keywordflow">for</span> (r = <a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">rules</a>.begin(); r != <a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">rules</a>.end(); r++)
<a name="l00264"></a>00264 fout << <span class="stringliteral">" "</span> << *r;
<a name="l00265"></a>00265 fout << endl;
<a name="l00266"></a>00266 list<Trans>::const_iterator t;
<a name="l00267"></a>00267 <span class="keywordflow">for</span> (t = <a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>.begin(); t != <a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>.end(); t++)
<a name="l00268"></a>00268 fout << *t;
<a name="l00269"></a>00269 <span class="keywordflow">return</span> fout;
<a name="l00270"></a>00270 }
<a name="l00271"></a>00271
<a name="l00272"></a>00272 ostream& <a class="code" href="list_8cpp.html#a850f2e459a901e0c9908d3a3a54b306e">Automaton::print</a>(ostream& fout)<span class="keyword"> const</span>
<a name="l00273"></a>00273 <span class="keyword"></span>{
<a name="l00274"></a>00274 <span class="keywordtype">int</span> i, n = <a class="code" href="structAutomaton.html#a11d18ab1675e9d32433e799a2b20d26e">rhs</a>.size();
<a name="l00275"></a>00275 <span class="keywordflow">for</span> (i = 0; i < n; i++)
<a name="l00276"></a>00276 fout << <span class="stringliteral">"rule #"</span> << i << <span class="stringliteral">": "</span> << *<a class="code" href="structAutomaton.html#a11d18ab1675e9d32433e799a2b20d26e">rhs</a>[i] << endl;
<a name="l00277"></a>00277 n = <a class="code" href="structAutomaton.html#ae12943b3fadba9d0c0984cc0fa839efb">state</a>.size();
<a name="l00278"></a>00278 <span class="keywordflow">for</span> (i = 0; i < n; i++)
<a name="l00279"></a>00279 fout << *<a class="code" href="structAutomaton.html#ae12943b3fadba9d0c0984cc0fa839efb">state</a>[i];
<a name="l00280"></a>00280 <span class="keywordflow">return</span> fout;
<a name="l00281"></a>00281 }
<a name="l00282"></a>00282 <span class="preprocessor">#endif</span>
<a name="l00283"></a>00283 <span class="preprocessor"></span>
<a name="l00284"></a>00284 <span class="comment">/* Construction algorithm for the pattern matching automaton.</span>
<a name="l00285"></a>00285 <span class="comment"> *</span>
<a name="l00286"></a>00286 <span class="comment"> * We employ the incremental technique described in Graef: Left-To-Right Tree</span>
<a name="l00287"></a>00287 <span class="comment"> * Pattern Matching, Proc. RTA 1991, Springer 1991 (LNCS 488) to construct a</span>
<a name="l00288"></a>00288 <span class="comment"> * tree automaton (TA) for the given patterns. The basic outline of the</span>
<a name="l00289"></a>00289 <span class="comment"> * technique is as follows. Initially, the automaton is empty. From each</span>
<a name="l00290"></a>00290 <span class="comment"> * pattern we produce a trie (considering the pattern as a string of variable</span>
<a name="l00291"></a>00291 <span class="comment"> * and function symbols and constants). This trie is then merged with the TA</span>
<a name="l00292"></a>00292 <span class="comment"> * obtained so far. The latter process is similar to merging two deterministic</span>
<a name="l00293"></a>00293 <span class="comment"> * finite automata, but it also takes into account the variables (see the</span>
<a name="l00294"></a>00294 <span class="comment"> * merge_state() routine below).</span>
<a name="l00295"></a>00295 <span class="comment"> */</span>
<a name="l00296"></a>00296
<a name="l00297"></a>00297 <span class="comment">/* Construct a trie from a term tree. Takes the "start" and returns the "end"</span>
<a name="l00298"></a>00298 <span class="comment"> state of the (sub-)trie. */</span>
<a name="l00299"></a>00299
<a name="l00300"></a><a class="code" href="patternmatcher_8cpp.html#a32860dbb992bf1f234543c6a4da4c2bb">00300</a> <span class="keyword">static</span> <a class="code" href="structState.html">State</a> *<a class="code" href="patternmatcher_8cpp.html#a32860dbb992bf1f234543c6a4da4c2bb">make_state</a>(<a class="code" href="structState.html">State</a> *state, <span class="keywordtype">int</span> r, <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> x, <a class="code" href="patternmatcher_8cpp.html#a9d962b10c8fdb6619915dd0807f8fcec">Path</a>& p)
<a name="l00301"></a>00301 {
<a name="l00302"></a>00302 <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> id, x0, x1;
<a name="l00303"></a>00303 <a class="code" href="classNode.html" title="Class Node = (type x (int + double + Sym + void*)).">Node</a> op(0);
<a name="l00304"></a>00304 <span class="keywordflow">if</span> (<a class="code" href="boxes_8cpp.html#ad166878e0270e4eab4adf2fb5f81fc31">isBoxPatternVar</a>(x, <span class="keywordtype">id</span>)) {
<a name="l00305"></a>00305 <span class="comment">/* variable */</span>
<a name="l00306"></a>00306 <a class="code" href="structRule.html">Rule</a> rule(r, <span class="keywordtype">id</span>, p);
<a name="l00307"></a>00307 state-><a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">rules</a>.push_back(rule);
<a name="l00308"></a>00308 <a class="code" href="structTrans.html">Trans</a> trans(NULL);
<a name="l00309"></a>00309 state-><a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>.push_back(trans);
<a name="l00310"></a>00310 <span class="keywordflow">return</span> state-><a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>.begin()->state;
<a name="l00311"></a>00311 } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (<a class="code" href="patternmatcher_8cpp.html#a34cbd25863b5da67208a859cd4e39bb8">isBoxPatternOp</a>(x, op, x0, x1)) {
<a name="l00312"></a>00312 <span class="comment">/* composite pattern */</span>
<a name="l00313"></a>00313 <a class="code" href="structRule.html">Rule</a> rule(r, NULL);
<a name="l00314"></a>00314 state-><a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">rules</a>.push_back(rule);
<a name="l00315"></a>00315 <a class="code" href="structTrans.html">Trans</a> trans(op, 2);
<a name="l00316"></a>00316 state-><a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>.push_back(trans);
<a name="l00317"></a>00317 <a class="code" href="structState.html">State</a> *next = state-><a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>.begin()->state;
<a name="l00318"></a>00318 p.push_back(0);
<a name="l00319"></a>00319 next = <a class="code" href="patternmatcher_8cpp.html#a32860dbb992bf1f234543c6a4da4c2bb">make_state</a>(next, r, x0, p);
<a name="l00320"></a>00320 p.pop_back();
<a name="l00321"></a>00321 p.push_back(1);
<a name="l00322"></a>00322 next = <a class="code" href="patternmatcher_8cpp.html#a32860dbb992bf1f234543c6a4da4c2bb">make_state</a>(next, r, x1, p);
<a name="l00323"></a>00323 p.pop_back();
<a name="l00324"></a>00324 <span class="keywordflow">return</span> next;
<a name="l00325"></a>00325 } <span class="keywordflow">else</span> {
<a name="l00326"></a>00326 <span class="comment">/* constant */</span>
<a name="l00327"></a>00327 <a class="code" href="structRule.html">Rule</a> rule(r, NULL);
<a name="l00328"></a>00328 state-><a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">rules</a>.push_back(rule);
<a name="l00329"></a>00329 <a class="code" href="structTrans.html">Trans</a> trans(x);
<a name="l00330"></a>00330 state-><a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>.push_back(trans);
<a name="l00331"></a>00331 <span class="keywordflow">return</span> state-><a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>.begin()->state;
<a name="l00332"></a>00332 }
<a name="l00333"></a>00333 }
<a name="l00334"></a>00334
<a name="l00335"></a>00335 <span class="comment">/* Take a copy of a state and prefix it with n variable transitions. */</span>
<a name="l00336"></a>00336
<a name="l00337"></a><a class="code" href="patternmatcher_8cpp.html#ac71a889c61cb15a769ba2a6c70fa28fd">00337</a> <span class="keyword">static</span> <a class="code" href="structState.html">State</a> *<a class="code" href="patternmatcher_8cpp.html#ac71a889c61cb15a769ba2a6c70fa28fd">make_var_state</a>(<span class="keywordtype">int</span> n, <a class="code" href="structState.html">State</a> *state)
<a name="l00338"></a>00338 {
<a name="l00339"></a>00339 <span class="keywordflow">if</span> (n <= 0)
<a name="l00340"></a>00340 <span class="keywordflow">return</span> <span class="keyword">new</span> <a class="code" href="structState.html">State</a>(*state);
<a name="l00341"></a>00341 list<Rule>rules = state-><a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">rules</a>;
<a name="l00342"></a>00342 list<Rule>::iterator r;
<a name="l00343"></a>00343 <span class="keywordflow">for</span> (r = rules.begin(); r != rules.end(); r++) {
<a name="l00344"></a>00344 r->id = NULL; r->p = <a class="code" href="patternmatcher_8cpp.html#a9d962b10c8fdb6619915dd0807f8fcec">Path</a>();
<a name="l00345"></a>00345 }
<a name="l00346"></a>00346 <a class="code" href="structState.html">State</a> *prefix = <span class="keyword">new</span> <a class="code" href="structState.html">State</a>, *current = prefix;
<a name="l00347"></a>00347 <span class="keywordflow">while</span> (n-- > 0) {
<a name="l00348"></a>00348 current-><a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">rules</a> = rules;
<a name="l00349"></a>00349 <a class="code" href="structTrans.html">Trans</a> trans(NULL);
<a name="l00350"></a>00350 current-><a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>.push_back(trans);
<a name="l00351"></a>00351 current = current-><a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>.begin()->state;
<a name="l00352"></a>00352 }
<a name="l00353"></a>00353 *current = *state;
<a name="l00354"></a>00354 <span class="keywordflow">return</span> prefix;
<a name="l00355"></a>00355 }
<a name="l00356"></a>00356
<a name="l00357"></a>00357 <span class="comment">/* Merge two tree automata. Merges the tree automaton rooted at state2 into</span>
<a name="l00358"></a>00358 <span class="comment"> the automaton rooted at state1. We assume that state2 is in "trie" form,</span>
<a name="l00359"></a>00359 <span class="comment"> i.e., each state has at most one transition, which is always guaranteed</span>
<a name="l00360"></a>00360 <span class="comment"> here and simplifies the algorithm. */</span>
<a name="l00361"></a>00361
<a name="l00362"></a>00362 <span class="keyword">static</span> <span class="keywordtype">void</span> <a class="code" href="patternmatcher_8cpp.html#abd7baff1fa736df511b4e584faf9b94c">merge_state</a>(<a class="code" href="structState.html">State</a> *state1, <a class="code" href="structState.html">State</a> *state2);
<a name="l00363"></a>00363
<a name="l00364"></a><a class="code" href="patternmatcher_8cpp.html#a464229ee18218cccc0459ea79c8d932a">00364</a> <span class="keyword">static</span> <span class="keywordtype">void</span> <span class="keyword">inline</span> <a class="code" href="patternmatcher_8cpp.html#a464229ee18218cccc0459ea79c8d932a">merge_rules</a>(list<Rule>& rules1, list<Rule>& rules2)
<a name="l00365"></a>00365 {
<a name="l00366"></a>00366 list<Rule> cprules2 = rules2;
<a name="l00367"></a>00367 rules1.merge(cprules2);
<a name="l00368"></a>00368 }
<a name="l00369"></a>00369
<a name="l00370"></a><a class="code" href="patternmatcher_8cpp.html#aae0ba39b2aa456efe53ce535d4e20d7e">00370</a> <span class="keyword">static</span> <span class="keywordtype">void</span> <a class="code" href="patternmatcher_8cpp.html#aae0ba39b2aa456efe53ce535d4e20d7e">merge_trans_var</a>(list<Trans>& trans, <a class="code" href="structState.html">State</a> *state)
<a name="l00371"></a>00371 {
<a name="l00372"></a>00372 <span class="keywordflow">if</span> (!trans.begin()->is_var_trans()) {
<a name="l00373"></a>00373 <span class="comment">/* If we don't have a variable transition in this state yet then create a</span>
<a name="l00374"></a>00374 <span class="comment"> new one. */</span>
<a name="l00375"></a>00375 <a class="code" href="structTrans.html">Trans</a> tr(NULL);
<a name="l00376"></a>00376 trans.push_front(tr);
<a name="l00377"></a>00377 }
<a name="l00378"></a>00378 list<Trans>::const_iterator t;
<a name="l00379"></a>00379 <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> x;
<a name="l00380"></a>00380 <a class="code" href="classNode.html" title="Class Node = (type x (int + double + Sym + void*)).">Node</a> op(0);
<a name="l00381"></a>00381 <span class="keywordflow">for</span> (t = trans.begin(); t != trans.end(); t++) {
<a name="l00382"></a>00382 <span class="keywordflow">if</span> (t->is_var_trans())
<a name="l00383"></a>00383 <a class="code" href="patternmatcher_8cpp.html#abd7baff1fa736df511b4e584faf9b94c">merge_state</a>(t->state, state);
<a name="l00384"></a>00384 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (t->is_cst_trans(x)) {
<a name="l00385"></a>00385 <span class="comment">/* add the completion of the given state for a constant */</span>
<a name="l00386"></a>00386 <a class="code" href="patternmatcher_8cpp.html#abd7baff1fa736df511b4e584faf9b94c">merge_state</a>(t->state, state);
<a name="l00387"></a>00387 } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (t->is_op_trans(op)) {
<a name="l00388"></a>00388 <span class="comment">/* add the completion of the given state for an arity>0 op */</span>
<a name="l00389"></a>00389 <a class="code" href="structState.html">State</a> *state1 = <a class="code" href="patternmatcher_8cpp.html#ac71a889c61cb15a769ba2a6c70fa28fd">make_var_state</a>(t->arity, state);
<a name="l00390"></a>00390 <a class="code" href="patternmatcher_8cpp.html#abd7baff1fa736df511b4e584faf9b94c">merge_state</a>(t->state, state1);
<a name="l00391"></a>00391 <span class="keyword">delete</span> state1;
<a name="l00392"></a>00392 }
<a name="l00393"></a>00393 }
<a name="l00394"></a>00394 }
<a name="l00395"></a>00395
<a name="l00396"></a><a class="code" href="patternmatcher_8cpp.html#a6adf2c908011694d8f0d5975c084e584">00396</a> <span class="keyword">static</span> <span class="keywordtype">void</span> <a class="code" href="patternmatcher_8cpp.html#a6adf2c908011694d8f0d5975c084e584">merge_trans_cst</a>(list<Trans>& trans, <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> x, <a class="code" href="structState.html">State</a> *state)
<a name="l00397"></a>00397 {
<a name="l00398"></a>00398 list<Trans>::iterator t0 = trans.begin(), t1 = t0, t;
<a name="l00399"></a>00399 <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> x1;
<a name="l00400"></a>00400 <span class="keywordflow">if</span> (t0->is_var_trans()) t1++;
<a name="l00401"></a>00401 <span class="keywordflow">for</span> (t = t1; t != trans.end(); t++) {
<a name="l00402"></a>00402 <span class="keywordflow">if</span> (t->is_cst_trans(x1)) {
<a name="l00403"></a>00403 <span class="keywordflow">if</span> (x == x1) {
<a name="l00404"></a>00404 <a class="code" href="patternmatcher_8cpp.html#abd7baff1fa736df511b4e584faf9b94c">merge_state</a>(t->state, state);
<a name="l00405"></a>00405 <span class="keywordflow">return</span>;
<a name="l00406"></a>00406 } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (x < x1)
<a name="l00407"></a>00407 <span class="keywordflow">break</span>;
<a name="l00408"></a>00408 }
<a name="l00409"></a>00409 }
<a name="l00410"></a>00410 <span class="comment">/* no matching transition has been found; add a new one */</span>
<a name="l00411"></a>00411 <a class="code" href="structTrans.html">Trans</a> tr(x);
<a name="l00412"></a>00412 trans.insert(t, tr); t--;
<a name="l00413"></a>00413 <a class="code" href="structState.html">State</a> *state1 = t->state;
<a name="l00414"></a>00414 *state1 = *state;
<a name="l00415"></a>00415 <span class="keywordflow">if</span> (t1 != t0) {
<a name="l00416"></a>00416 <span class="comment">/* if we have a variable transition in the current state, we also need to</span>
<a name="l00417"></a>00417 <span class="comment"> merge its completion for the current symbol/constant */</span>
<a name="l00418"></a>00418 <a class="code" href="patternmatcher_8cpp.html#abd7baff1fa736df511b4e584faf9b94c">merge_state</a>(state1, t0->state);
<a name="l00419"></a>00419 }
<a name="l00420"></a>00420 }
<a name="l00421"></a>00421
<a name="l00422"></a><a class="code" href="patternmatcher_8cpp.html#a7d5e6c63720d1524aad5798f7d2d8619">00422</a> <span class="keyword">static</span> <span class="keywordtype">void</span> <a class="code" href="patternmatcher_8cpp.html#a7d5e6c63720d1524aad5798f7d2d8619">merge_trans_op</a>(list<Trans>& trans, <span class="keyword">const</span> <a class="code" href="classNode.html" title="Class Node = (type x (int + double + Sym + void*)).">Node</a>& op,
<a name="l00423"></a>00423 <span class="keywordtype">int</span> arity, <a class="code" href="structState.html">State</a> *state)
<a name="l00424"></a>00424 {
<a name="l00425"></a>00425 <span class="comment">/* analogous to merge_trans_cst above, but handles the arity>0 case */</span>
<a name="l00426"></a>00426 list<Trans>::iterator t0 = trans.begin(), t1 = t0, t;
<a name="l00427"></a>00427 <a class="code" href="classNode.html" title="Class Node = (type x (int + double + Sym + void*)).">Node</a> op1(0);
<a name="l00428"></a>00428 <span class="keywordflow">if</span> (t0->is_var_trans()) t1++;
<a name="l00429"></a>00429 <span class="keywordflow">for</span> (t = t1; t != trans.end(); t++) {
<a name="l00430"></a>00430 <span class="keywordflow">if</span> (t->is_op_trans(op1)) {
<a name="l00431"></a>00431 <span class="keywordflow">if</span> (op == op1) {
<a name="l00432"></a>00432 <a class="code" href="patternmatcher_8cpp.html#abd7baff1fa736df511b4e584faf9b94c">merge_state</a>(t->state, state);
<a name="l00433"></a>00433 <span class="keywordflow">return</span>;
<a name="l00434"></a>00434 } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (op.<a class="code" href="classNode.html#a9e9dc25c550f5a1fa55a68ff3c5d81cf">getSym</a>() < op1.<a class="code" href="classNode.html#a9e9dc25c550f5a1fa55a68ff3c5d81cf">getSym</a>())
<a name="l00435"></a>00435 <span class="keywordflow">break</span>;
<a name="l00436"></a>00436 }
<a name="l00437"></a>00437 }
<a name="l00438"></a>00438 <a class="code" href="structTrans.html">Trans</a> tr(op, arity);
<a name="l00439"></a>00439 trans.insert(t, tr); t--;
<a name="l00440"></a>00440 <a class="code" href="structState.html">State</a> *state1 = t->state;
<a name="l00441"></a>00441 *state1 = *state;
<a name="l00442"></a>00442 <span class="keywordflow">if</span> (t1 != t0) {
<a name="l00443"></a>00443 <a class="code" href="structState.html">State</a> *state2 = <a class="code" href="patternmatcher_8cpp.html#ac71a889c61cb15a769ba2a6c70fa28fd">make_var_state</a>(arity, t0->state);
<a name="l00444"></a>00444 <a class="code" href="patternmatcher_8cpp.html#abd7baff1fa736df511b4e584faf9b94c">merge_state</a>(state1, state2);
<a name="l00445"></a>00445 <span class="keyword">delete</span> state2;
<a name="l00446"></a>00446 }
<a name="l00447"></a>00447 }
<a name="l00448"></a>00448
<a name="l00449"></a><a class="code" href="patternmatcher_8cpp.html#ab85e85c28fd630071fed5dc7edc83f70">00449</a> <span class="keyword">static</span> <span class="keywordtype">void</span> <a class="code" href="patternmatcher_8cpp.html#ab85e85c28fd630071fed5dc7edc83f70">merge_trans</a>(list<Trans>& trans1, list<Trans>& trans2)
<a name="l00450"></a>00450 {
<a name="l00451"></a>00451 <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> x;
<a name="l00452"></a>00452 <a class="code" href="classNode.html" title="Class Node = (type x (int + double + Sym + void*)).">Node</a> op(0);
<a name="l00453"></a>00453 <span class="keywordflow">if</span> (trans2.empty())
<a name="l00454"></a>00454 ;
<a name="l00455"></a>00455 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (trans1.empty()) {
<a name="l00456"></a>00456 list<Trans> cptrans2 = trans2;
<a name="l00457"></a>00457 <span class="comment">/* append a copy of trans2 to trans1 */</span>
<a name="l00458"></a>00458 trans1.splice(trans1.end(), cptrans2);
<a name="l00459"></a>00459 } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (trans2.begin()->is_var_trans())
<a name="l00460"></a>00460 <span class="comment">/* merge a variable transition */</span>
<a name="l00461"></a>00461 <a class="code" href="patternmatcher_8cpp.html#aae0ba39b2aa456efe53ce535d4e20d7e">merge_trans_var</a>(trans1, trans2.begin()->state);
<a name="l00462"></a>00462 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (trans2.begin()->is_cst_trans(x))
<a name="l00463"></a>00463 <span class="comment">/* merge a constant transition */</span>
<a name="l00464"></a>00464 <a class="code" href="patternmatcher_8cpp.html#a6adf2c908011694d8f0d5975c084e584">merge_trans_cst</a>(trans1, x, trans2.begin()->state);
<a name="l00465"></a>00465 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (trans2.begin()->is_op_trans(op))
<a name="l00466"></a>00466 <span class="comment">/* merge a BDA op transition */</span>
<a name="l00467"></a>00467 <a class="code" href="patternmatcher_8cpp.html#a7d5e6c63720d1524aad5798f7d2d8619">merge_trans_op</a>(trans1, op, trans2.begin()->arity, trans2.begin()->state);
<a name="l00468"></a>00468 }
<a name="l00469"></a>00469
<a name="l00470"></a><a class="code" href="patternmatcher_8cpp.html#abd7baff1fa736df511b4e584faf9b94c">00470</a> <span class="keyword">static</span> <span class="keywordtype">void</span> <a class="code" href="patternmatcher_8cpp.html#abd7baff1fa736df511b4e584faf9b94c">merge_state</a>(<a class="code" href="structState.html">State</a> *state1, <a class="code" href="structState.html">State</a> *state2)
<a name="l00471"></a>00471 {
<a name="l00472"></a>00472 <a class="code" href="patternmatcher_8cpp.html#a464229ee18218cccc0459ea79c8d932a">merge_rules</a>(state1-><a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">rules</a>, state2-><a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">rules</a>);
<a name="l00473"></a>00473 <a class="code" href="patternmatcher_8cpp.html#ab85e85c28fd630071fed5dc7edc83f70">merge_trans</a>(state1-><a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>, state2-><a class="code" href="structState.html#ac263d79bcd1c0055a3b49e7259f0136e">trans</a>);
<a name="l00474"></a>00474 }
<a name="l00475"></a>00475
<a name="l00476"></a>00476 <span class="comment">/* Take the rules of a BoxCase expression and return a pointer to the</span>
<a name="l00477"></a>00477 <span class="comment"> corresponding TA automaton (interface operation). */</span>
<a name="l00478"></a>00478
<a name="l00479"></a><a class="code" href="patternmatcher_8hh.html#a81bb4084b45da5ba7e9bf6f562877543">00479</a> <a class="code" href="structAutomaton.html">Automaton</a> *<a class="code" href="patternmatcher_8cpp.html#a81bb4084b45da5ba7e9bf6f562877543">make_pattern_matcher</a>(<a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> R)
<a name="l00480"></a>00480 <span class="comment">/* Tree R encodes the rules of a case box expressions as a Tree object, as</span>
<a name="l00481"></a>00481 <span class="comment"> follows:</span>
<a name="l00482"></a>00482 <span class="comment"></span>
<a name="l00483"></a>00483 <span class="comment"> Rules ::= cons Rule (cons Rule ... nil)</span>
<a name="l00484"></a>00484 <span class="comment"> Rule ::= cons Lhs Rhs</span>
<a name="l00485"></a>00485 <span class="comment"> Lhs ::= cons Pattern (cons Pattern ... nil)</span>
<a name="l00486"></a>00486 <span class="comment"> Pattern ::= Tree (parameter pattern)</span>
<a name="l00487"></a>00487 <span class="comment"> Rhs ::= Tree</span>
<a name="l00488"></a>00488 <span class="comment"></span>
<a name="l00489"></a>00489 <span class="comment"> NOTE: The lists of rules and patterns are actually delivered in reverse</span>
<a name="l00490"></a>00490 <span class="comment"> order by the parser, so we have to reverse them on the fly. */</span>
<a name="l00491"></a>00491 {
<a name="l00492"></a>00492 <a class="code" href="structAutomaton.html">Automaton</a> *A = <span class="keyword">new</span> <a class="code" href="structAutomaton.html">Automaton</a>;
<a name="l00493"></a>00493 <span class="keywordtype">int</span> n = <a class="code" href="list_8cpp.html#a0b58ea1a5d8649e8afb0f70c48776347">len</a>(R), r = n;
<a name="l00494"></a>00494 <a class="code" href="structState.html">State</a> *start = <span class="keyword">new</span> <a class="code" href="structState.html">State</a>;
<a name="l00495"></a>00495 <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> rule, rest;
<a name="l00496"></a>00496 vector<Tree> rules(n, (<a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a>)NULL);
<a name="l00497"></a>00497 vector< vector<Tree> > testpats(n);
<a name="l00498"></a>00498 <span class="keywordflow">while</span> (<a class="code" href="patternmatcher_8cpp.html#a50ea341d53b07dacd749c6bd25d57452">isCons</a>(R, rule, rest)) {
<a name="l00499"></a>00499 rules[--r] = rule;
<a name="l00500"></a>00500 R = rest;
<a name="l00501"></a>00501 }
<a name="l00502"></a>00502 <span class="keywordflow">for</span> (r = 0; r < n; r++) {
<a name="l00503"></a>00503 <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> lhs, rhs;
<a name="l00504"></a>00504 <span class="keywordflow">if</span> (<a class="code" href="patternmatcher_8cpp.html#a50ea341d53b07dacd749c6bd25d57452">isCons</a>(rules[r], lhs, rhs)) {
<a name="l00505"></a>00505 <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> pat, rest;
<a name="l00506"></a>00506 <span class="keywordtype">int</span> m = <a class="code" href="list_8cpp.html#a0b58ea1a5d8649e8afb0f70c48776347">len</a>(lhs), i = m;
<a name="l00507"></a>00507 vector<Tree> pats(<a class="code" href="list_8cpp.html#a0b58ea1a5d8649e8afb0f70c48776347">len</a>(lhs), (<a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a>)NULL);
<a name="l00508"></a>00508 <a class="code" href="structState.html">State</a> *state0 = <span class="keyword">new</span> <a class="code" href="structState.html">State</a>, *state = state0;
<a name="l00509"></a>00509 A-><a class="code" href="structAutomaton.html#a11d18ab1675e9d32433e799a2b20d26e">rhs</a>.push_back(rhs);
<a name="l00510"></a>00510 <span class="keywordflow">while</span> (<a class="code" href="patternmatcher_8cpp.html#a50ea341d53b07dacd749c6bd25d57452">isCons</a>(lhs, pat, rest)) {
<a name="l00511"></a>00511 pats[--i] = pat;
<a name="l00512"></a>00512 lhs = rest;
<a name="l00513"></a>00513 }
<a name="l00514"></a>00514 testpats[r] = pats;
<a name="l00515"></a>00515 <span class="keywordflow">for</span> (i = 0; i < m; i++) {
<a name="l00516"></a>00516 <a class="code" href="patternmatcher_8cpp.html#a9d962b10c8fdb6619915dd0807f8fcec">Path</a> p;
<a name="l00517"></a>00517 state = <a class="code" href="patternmatcher_8cpp.html#a32860dbb992bf1f234543c6a4da4c2bb">make_state</a>(state, r, pats[i], p);
<a name="l00518"></a>00518 }
<a name="l00519"></a>00519 <a class="code" href="structRule.html">Rule</a> rule(r, NULL);
<a name="l00520"></a>00520 state-><a class="code" href="structState.html#a5016f714ddfc2dc5890cbb949b7c2c70">rules</a>.push_back(rule);
<a name="l00521"></a>00521 <a class="code" href="patternmatcher_8cpp.html#abd7baff1fa736df511b4e584faf9b94c">merge_state</a>(start, state0);
<a name="l00522"></a>00522 <span class="keyword">delete</span> state0;
<a name="l00523"></a>00523 }
<a name="l00524"></a>00524 }
<a name="l00525"></a>00525 A-><a class="code" href="structAutomaton.html#a3305f434c8c0e6b2d3e446da7cd4ec74">build</a>(start);
<a name="l00526"></a>00526 <span class="comment">/* Check for shadowed rules. Note that because of potential nonlinearities</span>
<a name="l00527"></a>00527 <span class="comment"> it is *not* enough to just check the rule lists of final states and</span>
<a name="l00528"></a>00528 <span class="comment"> determine whether they have multiple matched rules. */</span>
<a name="l00529"></a>00529 <span class="keywordflow">for</span> (r = 0; r < n; r++) {
<a name="l00530"></a>00530 <span class="keywordtype">int</span> s = 0, m = testpats[r].size();
<a name="l00531"></a>00531 <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> C;
<a name="l00532"></a>00532 vector<Tree> E(n, <a class="code" href="list_8cpp.html#a538b704dd07794b7237108f1917c471e">nil</a>);
<a name="l00533"></a>00533 <span class="comment">/* try to match the lhs of rule #r */</span>
<a name="l00534"></a>00534 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i < m; i++) {
<a name="l00535"></a>00535 s = <a class="code" href="patternmatcher_8cpp.html#a9a0cd806f9df515fe14799df5760021b">apply_pattern_matcher</a>(A, s, testpats[r][i], C, E);
<a name="l00536"></a>00536 <span class="keywordflow">if</span> (s < 0) <span class="keywordflow">break</span>;
<a name="l00537"></a>00537 }
<a name="l00538"></a>00538 <span class="keywordflow">if</span> (A-><a class="code" href="structAutomaton.html#a92020994f3a89b85ac0f8f6ccd3273ff">final</a>(s)) {
<a name="l00539"></a>00539 list<Rule>::const_iterator ru;
<a name="l00540"></a>00540 <span class="keywordflow">for</span> (ru = A-><a class="code" href="structAutomaton.html#adb969b0985e71dd5415ed70369b937f4">rules</a>(s).begin(); ru != A-><a class="code" href="structAutomaton.html#adb969b0985e71dd5415ed70369b937f4">rules</a>(s).end(); ru++)
<a name="l00541"></a>00541 <span class="keywordflow">if</span> (!<a class="code" href="boxes_8cpp.html#a0f492ef7453000e0b40455ac32bd76d4">isBoxError</a>(E[ru->r]))
<a name="l00542"></a>00542 <span class="keywordflow">if</span> (ru->r < r) {
<a name="l00543"></a>00543 <span class="comment">/* Lhs of rule #r matched a higher-priority rule, so rule #r may</span>
<a name="l00544"></a>00544 <span class="comment"> be shadowed. */</span>
<a name="l00545"></a>00545 <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> lhs1, rhs1, lhs2, rhs2;
<a name="l00546"></a>00546 <span class="keywordflow">if</span> (<a class="code" href="patternmatcher_8cpp.html#a50ea341d53b07dacd749c6bd25d57452">isCons</a>(rules[ru->r], lhs1, rhs1) && <a class="code" href="patternmatcher_8cpp.html#a50ea341d53b07dacd749c6bd25d57452">isCons</a>(rules[r], lhs2, rhs2)) {
<a name="l00547"></a>00547 cerr << <span class="stringliteral">"WARNING : shadowed pattern-matching rule: "</span>
<a name="l00548"></a>00548 << <a class="code" href="classboxpp.html">boxpp</a>(<a class="code" href="list_8cpp.html#a8e15f8d6fcc6cd319059c2e0544145bb">reverse</a>(lhs2)) << <span class="stringliteral">" => "</span> << <a class="code" href="classboxpp.html">boxpp</a>(rhs2) << <span class="stringliteral">";"</span>
<a name="l00549"></a>00549 << <span class="stringliteral">" previous rule was: "</span>
<a name="l00550"></a>00550 << <a class="code" href="classboxpp.html">boxpp</a>(<a class="code" href="list_8cpp.html#a8e15f8d6fcc6cd319059c2e0544145bb">reverse</a>(lhs1)) << <span class="stringliteral">" => "</span> << <a class="code" href="classboxpp.html">boxpp</a>(rhs1) << <span class="stringliteral">";"</span>
<a name="l00551"></a>00551 << endl;
<a name="l00552"></a>00552 } <span class="keywordflow">else</span> {
<a name="l00553"></a>00553 cerr << <span class="stringliteral">"INTERNAL ERROR : "</span> << __FILE__ << <span class="stringliteral">":"</span> << __LINE__ << endl;
<a name="l00554"></a>00554 exit(1);
<a name="l00555"></a>00555 }
<a name="l00556"></a>00556 } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (ru->r >= r)
<a name="l00557"></a>00557 <span class="keywordflow">break</span>;
<a name="l00558"></a>00558 }
<a name="l00559"></a>00559 }
<a name="l00560"></a>00560 <span class="preprocessor">#ifdef DEBUG</span>
<a name="l00561"></a>00561 <span class="preprocessor"></span> cout << <span class="stringliteral">"automaton "</span> << A << endl << *A << <span class="stringliteral">"end automaton"</span> << endl;
<a name="l00562"></a>00562 <span class="preprocessor">#endif</span>
<a name="l00563"></a>00563 <span class="preprocessor"></span> <span class="keywordflow">return</span> A;
<a name="l00564"></a>00564 }
<a name="l00565"></a>00565
<a name="l00566"></a>00566 <span class="comment">/* Helper type to represent variable substitutions which are recorded during</span>
<a name="l00567"></a>00567 <span class="comment"> matching. Each variable is associated with the path pointing at the subterm</span>
<a name="l00568"></a>00568 <span class="comment"> of the argument where the substitution of the matched variable is to be</span>
<a name="l00569"></a>00569 <span class="comment"> found. */</span>
<a name="l00570"></a>00570
<a name="l00571"></a><a class="code" href="structAssoc.html">00571</a> <span class="keyword">struct </span><a class="code" href="structAssoc.html">Assoc</a> {
<a name="l00572"></a><a class="code" href="structAssoc.html#a31cd29bc585193aa9abb93a882b832bb">00572</a> <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> <a class="code" href="structAssoc.html#a31cd29bc585193aa9abb93a882b832bb">id</a>;
<a name="l00573"></a><a class="code" href="structAssoc.html#a04ce3e8f65f2c4803637a13a7eb33f1f">00573</a> <a class="code" href="patternmatcher_8cpp.html#a9d962b10c8fdb6619915dd0807f8fcec">Path</a> <a class="code" href="structAssoc.html#a04ce3e8f65f2c4803637a13a7eb33f1f">p</a>;
<a name="l00574"></a><a class="code" href="structAssoc.html#a29d5b9c9bfbf238e17d0dd65636d950c">00574</a> <a class="code" href="structAssoc.html#a29d5b9c9bfbf238e17d0dd65636d950c">Assoc</a>(<a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> _id, <span class="keyword">const</span> <a class="code" href="patternmatcher_8cpp.html#a9d962b10c8fdb6619915dd0807f8fcec">Path</a>& _p) : <a class="code" href="structAssoc.html#a31cd29bc585193aa9abb93a882b832bb">id</a>(_id), <a class="code" href="structAssoc.html#a04ce3e8f65f2c4803637a13a7eb33f1f">p</a>(_p) {}
<a name="l00575"></a>00575 };
<a name="l00576"></a><a class="code" href="patternmatcher_8cpp.html#a67cf4bdbfb11718a7a1b859dcb7195af">00576</a> <span class="keyword">typedef</span> list<Assoc> <a class="code" href="patternmatcher_8cpp.html#a67cf4bdbfb11718a7a1b859dcb7195af">Subst</a>;
<a name="l00577"></a>00577
<a name="l00578"></a>00578 <span class="comment">/* add all substitutions for a given state */</span>
<a name="l00579"></a>00579
<a name="l00580"></a><a class="code" href="patternmatcher_8cpp.html#a3be3407c099f863001ce04465497b355">00580</a> <span class="keyword">static</span> <span class="keywordtype">void</span> <a class="code" href="patternmatcher_8cpp.html#a3be3407c099f863001ce04465497b355">add_subst</a>(vector<Subst>& <a class="code" href="Text_8cpp.html#af50e951c134c2c98c4c75d687f8fca7a">subst</a>, <a class="code" href="structAutomaton.html">Automaton</a> *A, <span class="keywordtype">int</span> s)
<a name="l00581"></a>00581 {
<a name="l00582"></a>00582 list<Rule> rules = A-><a class="code" href="structAutomaton.html#adb969b0985e71dd5415ed70369b937f4">rules</a>(s);
<a name="l00583"></a>00583 list<Rule>::const_iterator r;
<a name="l00584"></a>00584 <span class="keywordflow">for</span> (r = rules.begin(); r != rules.end(); r++)
<a name="l00585"></a>00585 <span class="keywordflow">if</span> (r->id != NULL)
<a name="l00586"></a>00586 subst[r->r].push_back(<a class="code" href="structAssoc.html">Assoc</a>(r->id, r->p));
<a name="l00587"></a>00587 }
<a name="l00588"></a>00588
<a name="l00589"></a>00589 <span class="comment">/* Process a given term tree X starting from state s, modify variable</span>
<a name="l00590"></a>00590 <span class="comment"> substitutions accordingly. Returns the resulting state, or -1 if no</span>
<a name="l00591"></a>00591 <span class="comment"> match. This does all the grunt work of matching. */</span>
<a name="l00592"></a>00592
<a name="l00593"></a><a class="code" href="patternmatcher_8cpp.html#a7d18b0f8abb16b7a412e8a1cc8608052">00593</a> <span class="keyword">static</span> <span class="keywordtype">int</span> <a class="code" href="patternmatcher_8cpp.html#a7d18b0f8abb16b7a412e8a1cc8608052">apply_pattern_matcher_internal</a>(<a class="code" href="structAutomaton.html">Automaton</a> *A, <span class="keywordtype">int</span> s, <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> X,
<a name="l00594"></a>00594 vector<Subst>& <a class="code" href="Text_8cpp.html#af50e951c134c2c98c4c75d687f8fca7a">subst</a>)
<a name="l00595"></a>00595 {
<a name="l00596"></a>00596 <span class="comment">/* FIXME: rewrite this non-recursively? */</span>
<a name="l00597"></a>00597 <span class="keywordflow">if</span> (s >= 0) {
<a name="l00598"></a>00598 list<Trans>::const_iterator t;
<a name="l00599"></a>00599 <span class="keywordflow">if</span> (A-><a class="code" href="structAutomaton.html#ae12943b3fadba9d0c0984cc0fa839efb">state</a>[s]->match_num)
<a name="l00600"></a>00600 <span class="comment">/* simplify possible numeric argument on the fly */</span>
<a name="l00601"></a>00601 X = <a class="code" href="eval_8cpp.html#a49268100cc006f566fec7f848c65d27a" title="Simplify a block-diagram pattern by computing its numerical sub-expressions.">simplifyPattern</a>(X);
<a name="l00602"></a>00602 <span class="comment">/* first check for applicable non-variable transitions */</span>
<a name="l00603"></a>00603 <span class="keywordflow">for</span> (t = A-><a class="code" href="structAutomaton.html#a0f1678cbdb43070122bb9d6caa841697">trans</a>(s).begin(); t != A-><a class="code" href="structAutomaton.html#a0f1678cbdb43070122bb9d6caa841697">trans</a>(s).end(); t++) {
<a name="l00604"></a>00604 <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> x;
<a name="l00605"></a>00605 <a class="code" href="classNode.html" title="Class Node = (type x (int + double + Sym + void*)).">Node</a> op(0), op1(0);
<a name="l00606"></a>00606 <span class="keywordflow">if</span> (t->is_var_trans())
<a name="l00607"></a>00607 <span class="keywordflow">continue</span>;
<a name="l00608"></a>00608 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (t->is_cst_trans(x)) {
<a name="l00609"></a>00609 <span class="keywordflow">if</span> (X==x) {
<a name="l00610"></a>00610 <span class="comment">/* transition on constant */</span>
<a name="l00611"></a>00611 <span class="preprocessor">#ifdef DEBUG</span>
<a name="l00612"></a>00612 <span class="preprocessor"></span> cout << <span class="stringliteral">"state "</span> << s << <span class="stringliteral">", "</span> << *x << <span class="stringliteral">": goto state "</span> << t->state->s << endl;
<a name="l00613"></a>00613 <span class="preprocessor">#endif</span>
<a name="l00614"></a>00614 <span class="preprocessor"></span> <a class="code" href="patternmatcher_8cpp.html#a3be3407c099f863001ce04465497b355">add_subst</a>(subst, A, s);
<a name="l00615"></a>00615 s = t->state->s;
<a name="l00616"></a>00616 <span class="keywordflow">return</span> s;
<a name="l00617"></a>00617 }
<a name="l00618"></a>00618 } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (t->is_op_trans(op)) {
<a name="l00619"></a>00619 <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> x0, x1;
<a name="l00620"></a>00620 <span class="keywordflow">if</span> (<a class="code" href="patternmatcher_8cpp.html#a34cbd25863b5da67208a859cd4e39bb8">isBoxPatternOp</a>(X, op1, x0, x1) && op == op1) {
<a name="l00621"></a>00621 <span class="comment">/* transition on operation symbol */</span>
<a name="l00622"></a>00622 <span class="preprocessor">#ifdef DEBUG</span>
<a name="l00623"></a>00623 <span class="preprocessor"></span> cout << <span class="stringliteral">"state "</span> << s << <span class="stringliteral">", "</span> << op << <span class="stringliteral">": goto state "</span> << t->state->s << endl;
<a name="l00624"></a>00624 <span class="preprocessor">#endif</span>
<a name="l00625"></a>00625 <span class="preprocessor"></span> <a class="code" href="patternmatcher_8cpp.html#a3be3407c099f863001ce04465497b355">add_subst</a>(subst, A, s);
<a name="l00626"></a>00626 s = t->state->s;
<a name="l00627"></a>00627 <span class="keywordflow">if</span> (s >= 0)
<a name="l00628"></a>00628 s = <a class="code" href="patternmatcher_8cpp.html#a7d18b0f8abb16b7a412e8a1cc8608052">apply_pattern_matcher_internal</a>(A, s, x0, subst);
<a name="l00629"></a>00629 <span class="keywordflow">if</span> (s >= 0)
<a name="l00630"></a>00630 s = <a class="code" href="patternmatcher_8cpp.html#a7d18b0f8abb16b7a412e8a1cc8608052">apply_pattern_matcher_internal</a>(A, s, x1, subst);
<a name="l00631"></a>00631 <span class="keywordflow">return</span> s;
<a name="l00632"></a>00632 }
<a name="l00633"></a>00633 }
<a name="l00634"></a>00634 }
<a name="l00635"></a>00635 <span class="comment">/* check for variable transition (is always first in the list of</span>
<a name="l00636"></a>00636 <span class="comment"> transitions) */</span>
<a name="l00637"></a>00637 t = A-><a class="code" href="structAutomaton.html#a0f1678cbdb43070122bb9d6caa841697">trans</a>(s).begin();
<a name="l00638"></a>00638 <span class="keywordflow">if</span> (t->is_var_trans()) {
<a name="l00639"></a>00639 <span class="preprocessor">#ifdef DEBUG</span>
<a name="l00640"></a>00640 <span class="preprocessor"></span> cout << <span class="stringliteral">"state "</span> << s << <span class="stringliteral">", _: goto state "</span> << t->state->s << endl;
<a name="l00641"></a>00641 <span class="preprocessor">#endif</span>
<a name="l00642"></a>00642 <span class="preprocessor"></span> <a class="code" href="patternmatcher_8cpp.html#a3be3407c099f863001ce04465497b355">add_subst</a>(subst, A, s);
<a name="l00643"></a>00643 s = t->state->s;
<a name="l00644"></a>00644 } <span class="keywordflow">else</span> {
<a name="l00645"></a>00645 <span class="preprocessor">#ifdef DEBUG</span>
<a name="l00646"></a>00646 <span class="preprocessor"></span> cout << <span class="stringliteral">"state "</span> << s << <span class="stringliteral">", *** match failed ***"</span> << endl;
<a name="l00647"></a>00647 <span class="preprocessor">#endif</span>
<a name="l00648"></a>00648 <span class="preprocessor"></span> s = -1;
<a name="l00649"></a>00649 }
<a name="l00650"></a>00650 }
<a name="l00651"></a>00651 <span class="keywordflow">return</span> s;
<a name="l00652"></a>00652 }
<a name="l00653"></a>00653
<a name="l00654"></a>00654 <span class="comment">/* Apply the pattern matcher to a single argument, starting from a given state</span>
<a name="l00655"></a>00655 <span class="comment"> (interface operation). Returns the resulting state, modifies the variable</span>
<a name="l00656"></a>00656 <span class="comment"> bindings E accordingly, and sets C to the resulting closure if a final</span>
<a name="l00657"></a>00657 <span class="comment"> state is reached. Result will be -1 to indicate a matching failure, and C</span>
<a name="l00658"></a>00658 <span class="comment"> will be set to nil if no final state has been reached yet. */</span>
<a name="l00659"></a>00659
<a name="l00660"></a><a class="code" href="patternmatcher_8hh.html#a9a0cd806f9df515fe14799df5760021b">00660</a> <span class="keywordtype">int</span> <a class="code" href="patternmatcher_8cpp.html#a9a0cd806f9df515fe14799df5760021b">apply_pattern_matcher</a>(<a class="code" href="structAutomaton.html">Automaton</a> *A, <span class="comment">// automaton</span>
<a name="l00661"></a>00661 <span class="keywordtype">int</span> s, <span class="comment">// start state</span>
<a name="l00662"></a>00662 <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> X, <span class="comment">// arg to be matched</span>
<a name="l00663"></a>00663 <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a>& C, <span class="comment">// output closure (if any)</span>
<a name="l00664"></a>00664 vector<Tree>& E) <span class="comment">// modified output environments</span>
<a name="l00665"></a>00665 {
<a name="l00666"></a>00666 <span class="keywordtype">int</span> n = A-><a class="code" href="structAutomaton.html#ac244771866c62c3bbca1ec5201d5ed54">n_rules</a>();
<a name="l00667"></a>00667 vector<Subst> <a class="code" href="Text_8cpp.html#af50e951c134c2c98c4c75d687f8fca7a">subst</a>(n, <a class="code" href="patternmatcher_8cpp.html#a67cf4bdbfb11718a7a1b859dcb7195af">Subst</a>());
<a name="l00668"></a>00668 <span class="comment">/* perform matching, record variable substitutions */</span>
<a name="l00669"></a>00669 <span class="preprocessor">#ifdef DEBUG</span>
<a name="l00670"></a>00670 <span class="preprocessor"></span> cout << <span class="stringliteral">"automaton "</span> << A << <span class="stringliteral">", state "</span> << s << <span class="stringliteral">", start match on arg: "</span> << *X << endl;
<a name="l00671"></a>00671 <span class="preprocessor">#endif</span>
<a name="l00672"></a>00672 <span class="preprocessor"></span> s = <a class="code" href="patternmatcher_8cpp.html#a7d18b0f8abb16b7a412e8a1cc8608052">apply_pattern_matcher_internal</a>(A, s, X, subst);
<a name="l00673"></a>00673 C = <a class="code" href="list_8cpp.html#a538b704dd07794b7237108f1917c471e">nil</a>;
<a name="l00674"></a>00674 <span class="keywordflow">if</span> (s < 0)
<a name="l00675"></a>00675 <span class="comment">/* failed match */</span>
<a name="l00676"></a>00676 <span class="keywordflow">return</span> s;
<a name="l00677"></a>00677 <span class="comment">/* process variable substitutions */</span>
<a name="l00678"></a>00678 list<Rule>::const_iterator r;
<a name="l00679"></a>00679 <span class="keywordflow">for</span> (r = A-><a class="code" href="structAutomaton.html#adb969b0985e71dd5415ed70369b937f4">rules</a>(s).begin(); r != A-><a class="code" href="structAutomaton.html#adb969b0985e71dd5415ed70369b937f4">rules</a>(s).end(); r++) {
<a name="l00680"></a>00680 <span class="comment">// all rules still active in state s</span>
<a name="l00681"></a>00681 <span class="keywordflow">if</span> (!<a class="code" href="boxes_8cpp.html#a0f492ef7453000e0b40455ac32bd76d4">isBoxError</a>(E[r->r])) { <span class="comment">// and still viable</span>
<a name="l00682"></a>00682 Subst::const_iterator assoc;
<a name="l00683"></a>00683 <span class="keywordflow">for</span> (assoc = subst[r->r].begin(); assoc != subst[r->r].end(); assoc++) {
<a name="l00684"></a>00684 <a class="code" href="classCTree.html" title="A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches...">Tree</a> Z, Z1 = <a class="code" href="patternmatcher_8cpp.html#abf5fce930015999bd6e95513ee9aee2a">subtree</a>(X, 0, assoc->p);
<a name="l00685"></a>00685 <span class="keywordflow">if</span> (<a class="code" href="eval_8cpp.html#adf6ba37a28536372e3be65128c79e615" title="Search the environment for the definition of a symbol ID and return it.">searchIdDef</a>(assoc->id, Z, E[r->r])) {
<a name="l00686"></a>00686 <span class="keywordflow">if</span> (Z != Z1) {
<a name="l00687"></a>00687 <span class="comment">/* failed nonlinearity, add to the set of nonviable rules */</span>
<a name="l00688"></a>00688 <span class="preprocessor">#ifdef DEBUG</span>
<a name="l00689"></a>00689 <span class="preprocessor"></span> cout << <span class="stringliteral">"state "</span> << s << <span class="stringliteral">", rule #"</span> << r->r << <span class="stringliteral">": "</span> <<
<a name="l00690"></a>00690 *assoc->id << <span class="stringliteral">" := "</span> << *Z1 << <span class="stringliteral">" *** failed *** old value: "</span> <<
<a name="l00691"></a>00691 *Z << endl;
<a name="l00692"></a>00692 <span class="preprocessor">#endif</span>
<a name="l00693"></a>00693 <span class="preprocessor"></span> E[r->r] = <a class="code" href="boxes_8cpp.html#ab4f4d00d6bc173a3c9d20cd7054ffdb7">boxError</a>();
<a name="l00694"></a>00694 }
<a name="l00695"></a>00695 } <span class="keywordflow">else</span> {
<a name="l00696"></a>00696 <span class="comment">/* bind a variable for the current rule */</span>
<a name="l00697"></a>00697 <span class="preprocessor">#ifdef DEBUG</span>
<a name="l00698"></a>00698 <span class="preprocessor"></span> cout << <span class="stringliteral">"state "</span> << s << <span class="stringliteral">", rule #"</span> << r->r << <span class="stringliteral">": "</span> <<
<a name="l00699"></a>00699 *assoc->id << <span class="stringliteral">" := "</span> << *Z1 << endl;
<a name="l00700"></a>00700 <span class="preprocessor">#endif</span>
<a name="l00701"></a>00701 <span class="preprocessor"></span> E[r->r] = <a class="code" href="eval_8cpp.html#ad057f174a67a40fd689fc379a5a21c2d" title="Push a new layer and add a single definition.">pushValueDef</a>(assoc->id, Z1, E[r->r]);
<a name="l00702"></a>00702 }
<a name="l00703"></a>00703 }
<a name="l00704"></a>00704 }
<a name="l00705"></a>00705 }
<a name="l00706"></a>00706 <span class="keywordflow">if</span> (A-><a class="code" href="structAutomaton.html#a92020994f3a89b85ac0f8f6ccd3273ff">final</a>(s)) {
<a name="l00707"></a>00707 <span class="comment">/* if in a final state then return the right-hand side together with the</span>
<a name="l00708"></a>00708 <span class="comment"> corresponding variable environment */</span>
<a name="l00709"></a>00709 <span class="keywordflow">for</span> (r = A-><a class="code" href="structAutomaton.html#adb969b0985e71dd5415ed70369b937f4">rules</a>(s).begin(); r != A-><a class="code" href="structAutomaton.html#adb969b0985e71dd5415ed70369b937f4">rules</a>(s).end(); r++) <span class="comment">// all rules matched in state s</span>
<a name="l00710"></a>00710 <span class="keywordflow">if</span> (!<a class="code" href="boxes_8cpp.html#a0f492ef7453000e0b40455ac32bd76d4">isBoxError</a>(E[r->r])) { <span class="comment">// and still viable</span>
<a name="l00711"></a>00711 <span class="comment">/* return the rhs of the matched rule */</span>
<a name="l00712"></a>00712 C = <a class="code" href="boxes_8cpp.html#a321a193061eae875a5a8763bfd992f38">closure</a>(A-><a class="code" href="structAutomaton.html#a11d18ab1675e9d32433e799a2b20d26e">rhs</a>[r->r], <a class="code" href="list_8cpp.html#a538b704dd07794b7237108f1917c471e">nil</a>, <a class="code" href="list_8cpp.html#a538b704dd07794b7237108f1917c471e">nil</a>, E[r->r]);
<a name="l00713"></a>00713 <span class="preprocessor">#ifdef DEBUG</span>
<a name="l00714"></a>00714 <span class="preprocessor"></span> cout << <span class="stringliteral">"state "</span> << s << <span class="stringliteral">", complete match yields rhs #"</span> << r->r <<
<a name="l00715"></a>00715 <span class="stringliteral">": "</span> << *A-><a class="code" href="structAutomaton.html#a11d18ab1675e9d32433e799a2b20d26e">rhs</a>[r->r] << endl;
<a name="l00716"></a>00716 <span class="preprocessor">#endif</span>
<a name="l00717"></a>00717 <span class="preprocessor"></span> <span class="keywordflow">return</span> s;
<a name="l00718"></a>00718 }
<a name="l00719"></a>00719 <span class="comment">/* if none of the rules were matched then declare a failed match */</span>
<a name="l00720"></a>00720 <span class="preprocessor">#ifdef DEBUG</span>
<a name="l00721"></a>00721 <span class="preprocessor"></span> cout << <span class="stringliteral">"state "</span> << s << <span class="stringliteral">", *** match failed ***"</span> << endl;
<a name="l00722"></a>00722 <span class="preprocessor">#endif</span>
<a name="l00723"></a>00723 <span class="preprocessor"></span> <span class="keywordflow">return</span> -1;
<a name="l00724"></a>00724 }
<a name="l00725"></a>00725 <span class="preprocessor">#ifdef DEBUG</span>
<a name="l00726"></a>00726 <span class="preprocessor"></span> cout << <span class="stringliteral">"state "</span> << s << <span class="stringliteral">", successful incomplete match"</span> << endl;
<a name="l00727"></a>00727 <span class="preprocessor">#endif</span>
<a name="l00728"></a>00728 <span class="preprocessor"></span> <span class="keywordflow">return</span> s;
<a name="l00729"></a>00729 }
</pre></div></div>
<hr class="footer"/><address style="text-align: right;"><small>Generated on Wed Apr 28 23:59:59 2010 for FAUST compiler by
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.6.3 </small></address>
</body>
</html>
