00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #include <assert.h>
00025 #include <stdio.h>
00026 #include <stdlib.h>
00027 #include <limits.h>
00028 #include "tlib.hh"
00029
00030
00031 static Tree calcDeBruijn2Sym (Tree t);
00032 static Tree substitute(Tree t, int n, Tree id);
00033 static Tree liftn(Tree t, int threshold);
00034
00035
00036
00037 Sym DEBRUIJN = symbol ("DEBRUIJN");
00038 Sym DEBRUIJNREF = symbol ("DEBRUIJNREF");
00039
00040 Sym SYMREC = symbol ("SYMREC");
00041 Sym SYMRECREF = symbol ("SYMRECREF");
00042
00043
00044
00045
00046
00047
00048
00049
00050 Tree rec(Tree body)
00051 {
00052 return tree(DEBRUIJN, body);
00053 }
00054
00055 bool isRec(Tree t, Tree& body)
00056 {
00057 return isTree(t, DEBRUIJN, body);
00058 }
00059
00060 Tree ref(int level)
00061 {
00062 assert(level > 0);
00063 return tree(DEBRUIJNREF, tree(level));
00064 }
00065
00066 bool isRef(Tree t, int& level)
00067 {
00068 Tree u;
00069
00070 if (isTree(t, DEBRUIJNREF, u)) {
00071 return isInt(u->node(), &level);
00072 } else {
00073 return false;
00074 }
00075 }
00076
00077
00078
00079
00080
00081 Tree RECDEF = tree(symbol("RECDEF"));
00082
00083
00084 Tree rec(Tree var, Tree body)
00085 {
00086 Tree t = tree(SYMREC, var);
00087 t->setProperty(RECDEF, body);
00088 return t;
00089 }
00090
00091 bool isRec(Tree t, Tree& var, Tree& body)
00092 {
00093 if (isTree(t, SYMREC, var)) {
00094 body = t->getProperty(RECDEF);
00095 return true;
00096 } else {
00097 return false;
00098 }
00099 }
00100
00101
00102 Tree ref(Tree id)
00103 {
00104 return tree(SYMREC, id);
00105 }
00106
00107 bool isRef(Tree t, Tree& v)
00108 {
00109 return isTree(t, SYMREC, v);
00110 }
00111
00112
00113
00114
00115
00116
00117 int CTree::calcTreeAperture( const Node& n, const tvec& br )
00118 {
00119 int x;
00120 if (n == DEBRUIJNREF) {
00121
00122 if (isInt(br[0]->node(), &x)) {
00123 return x;
00124 } else {
00125 return 0;
00126 }
00127
00128 } else if (n == DEBRUIJN) {
00129
00130 return br[0]->fAperture - 1;
00131
00132 } else {
00133
00134 int rc = 0;
00135 tvec::const_iterator b = br.begin();
00136 tvec::const_iterator z = br.end();
00137 while (b != z) {
00138 if ((*b)->aperture() > rc) rc = (*b)->aperture();
00139 ++b;
00140 }
00141 return rc;
00142 }
00143 }
00144
00145 Tree lift(Tree t) { return liftn(t, 1); }
00146
00147 void printSignal(Tree sig, FILE* out, int prec=0);
00148
00149
00150
00151 #if 0
00152 static Tree _liftn(Tree t, int threshold);
00153
00154 static Tree liftn(Tree t, int threshold)
00155 {
00156 fprintf(stderr, "call of liftn("); printSignal(t, stderr); fprintf(stderr, ", %d)\n", threshold);
00157 Tree r = _liftn(t, threshold);
00158 fprintf(stderr, "return of liftn("); printSignal(t, stderr); fprintf(stderr, ", %d) -> ", threshold);
00159 printSignal(r, stderr); fprintf(stderr, "\n");
00160 return r;
00161 }
00162 #endif
00163
00164 static Tree liftn(Tree t, int threshold)
00165 {
00166 int n;
00167 Tree u;
00168
00169 if (isClosed(t)) {
00170
00171 return t;
00172
00173 } else if (isRef(t,n)) {
00174
00175 if (n < threshold) {
00176
00177 return t;
00178 } else {
00179
00180 return ref(n+1);
00181 }
00182
00183 } else if (isRec(t,u)) {
00184
00185 return rec(liftn(u, threshold+1));
00186
00187 } else {
00188 int n = t->arity();
00189
00190 tvec br(n);
00191 for (int i = 0; i < n; i++) {
00192 br[i] = liftn(t->branch(i), threshold);
00193 }
00194
00195 return CTree::make(t->node(), br);
00196 }
00197
00198 }
00199
00200
00201
00202
00203 Tree DEBRUIJN2SYM = tree(symbol("deBruijn2Sym"));
00204
00205 Tree deBruijn2Sym (Tree t)
00206 {
00207 assert(isClosed(t));
00208 Tree t2 = t->getProperty(DEBRUIJN2SYM);
00209
00210 if (!t2) {
00211 t2 = calcDeBruijn2Sym(t);
00212 t->setProperty(DEBRUIJN2SYM, t2);
00213 }
00214 return t2;
00215 }
00216
00217 static Tree calcDeBruijn2Sym (Tree t)
00218 {
00219 Tree body, var;
00220 int i;
00221
00222 if (isRec(t,body)) {
00223
00224 var = tree(unique("W"));
00225 return rec(var, deBruijn2Sym(substitute(body,1,ref(var))));
00226
00227 } else if (isRef(t,var)) {
00228
00229 return t;
00230
00231 } else if (isRef(t,i)) {
00232
00233 fprintf(stderr, "ERREUR, une reference de Bruijn touvee ! : ");
00234 printSignal(t, stderr);
00235 fprintf(stderr, ")\n");
00236 exit(1);
00237 return t;
00238
00239 } else {
00240
00241
00242 int a = t->arity();
00243 tvec br(a);
00244
00245 for (int i = 0; i < a; i++) {
00246 br[i] = deBruijn2Sym(t->branch(i));
00247 }
00248
00249 return CTree::make(t->node(), br);
00250 }
00251 }
00252
00253 static Tree substitute(Tree t, int level, Tree id)
00254 {
00255 int l;
00256 Tree body;
00257
00258 if (t->aperture()<level) {
00259
00260 return t;
00261 }
00262 if (isRef(t,l)) return (l == level) ? id : t;
00263 if (isRec(t,body)) return rec(substitute(body, level+1, id));
00264
00265 int ar = t->arity();
00266
00267 tvec br(ar);
00268 for (int i = 0; i < ar; i++) {
00269 br[i] = substitute(t->branch(i), level, id);
00270 }
00271
00272 return CTree::make(t->node(), br);
00273 }
00274
00275
00276
00277
00278
00279
00280 struct Env {
00281 Tree fTree; Env* fNext;
00282 Env(Tree t, Env* nxt) : fTree(t), fNext(nxt) {}
00283 };
00284
00285 static void markOpen(Tree t);
00286 static int recomputeAperture(Tree t, Env* p);
00287 static int orderof (Tree t, Env* p);
00288
00289 void updateAperture(Tree t)
00290 {
00291 markOpen(t);
00292 recomputeAperture(t, NULL);
00293 }
00294
00295
00296
00297 static void markOpen(Tree t)
00298 {
00299 if (t->aperture() == INT_MAX) return;
00300 t->setAperture(INT_MAX);
00301 int ar = t->arity();
00302 for (int i = 0; i < ar; i++) {
00303 markOpen(t->branch(i));
00304 }
00305 }
00306
00307 static int recomputeAperture(Tree t, Env* env)
00308 {
00309 Tree var, body;
00310
00311 if (t->aperture() == 0) return 0;
00312
00313 if (isRef(t, var)) {
00314
00315 return orderof(var, env);
00316
00317 } else if (isRec(t, var, body)) {
00318
00319 Env e(var,env);
00320 int a = recomputeAperture(body, &e) - 1;
00321 if (a<=0) { t->setAperture(0); }
00322 return a;
00323
00324 } else {
00325
00326 int ma = 0;
00327 int ar = t->arity();
00328 for (int i = 0; i<ar; i++) {
00329 int a = recomputeAperture(t->branch(i), env);
00330 if (ma < a) ma = a;
00331 }
00332 if (ma <= 0) { t->setAperture(0); }
00333 return ma;
00334 }
00335 }
00336
00337
00338 static int orderof (Tree t, Env* p)
00339 {
00340 if (p == NULL) return 0;
00341 if (t == p->fTree) return 1;
00342
00343 int pos = 1;
00344 while (p != NULL) {
00345 if (t == p->fTree) return pos;
00346 p = p->fNext;
00347 pos++;
00348 }
00349 return 0;
00350 }