prop-src/rwgen.pcc.old

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  This file implements the tree rewriting/tree parsing compiler.
   4 //  This is used to implement the rewrite class/rewrite constructs of Prop.
   5 //
   6 ///////////////////////////////////////////////////////////////////////////////
   7 #include <iostream.h>
   8 #include <strstream.h>
   9 #include <AD/automata/treegram.ph>
  10 #include <AD/automata/treegen.h>
  11 #include <AD/rewrite/burs_gen.h>
  12 #include <AD/strings/quark.h>
  13 #include "funmap.ph"
  14 #include "ir.ph"
  15 #include "ast.ph"
  16 #include "matchcom.ph"
  17 #include "type.h"
  18 #include "hashtab.h"
  19 #include "datagen.h"
  20 #include "config.h"
  21 #include "rwgen.h"
  22 #include "options.h"
  23
  24 ///////////////////////////////////////////////////////////////////////////////
  25 //
  26 //  Constructor and destructor of the rewriting compiler.
  27 //
  28 ///////////////////////////////////////////////////////////////////////////////
  29 RewritingCompiler::RewritingCompiler(ostream& f)
  30    : CodeGen(f), MatchCompiler(f), rewriters(#[]) {}
  31 RewritingCompiler::~RewritingCompiler() {}
  32
  33 ///////////////////////////////////////////////////////////////////////////////
  34 //
  35 //  Import some type definitions from the tree grammar and hash table
  36 //  classes.
  37 //
  38 ///////////////////////////////////////////////////////////////////////////////
  39 typedef TreeGrammar::TreeProduction TreeProduction;
  40 typedef TreeGrammar::Cost           TreeCost;
  41 typedef HashTable::Key              Key;
  42 typedef HashTable::Value            Value;
  43
  44 ///////////////////////////////////////////////////////////////////////////////
  45 //
  46 //  Method to generate the inference for a rewrite class.
  47 //
  48 ///////////////////////////////////////////////////////////////////////////////
  49 void DatatypeCompiler::gen_rewrite_class
  50    (Id class_name, Protocols protocols, TyQual qual)
  51 {  Bool is_app = qual & QUALapplicative;
  52    pr ("%-%^private:%+"
  53        "%^%s(const %s&);               // no copy constructor"
  54        "%^void operator = (const %s&); // no assignment"
  55        "%-%^public:%+"
  56        "%^struct %s_StateRec * stack__, * stack_top__;",
  57        class_name, class_name, class_name, class_name
  58       );
  59
  60    pr ("%-%^public:%+"
  61        "%^%s reduce(int, int&, int);"
  62        "%^%s reduce(char, int&, int);"
  63        "%^%s reduce(const char *, int&, int);"
  64        "%^%s reduce(Quark, int&, int);"
  65        "%^%s reduce(double, int&, int);"
  66        "%n#ifdef PROP_BOOL_IS_IMPLEMENTED"
  67        "%^%s reduce(bool, int&, int);"
  68        "%n#endif",
  69        (is_app ? "int         " : "void"),
  70        (is_app ? "char        " : "void"),
  71        (is_app ? "const char *" : "void"),
  72        (is_app ? "Quark       " : "void"),
  73        (is_app ? "double      " : "void"),
  74        (is_app ? "bool        " : "void")
  75       );
  76
  77    Bool gen_traversal = qual & QUALtreeparser;
  78
  79    {  for_each (Protocol, p, protocols)
  80       {  match (p)
  81          {  PROTOCOL { ty, syn = ! NOty ... }:
  82             {  gen_traversal = true;
  83             }
  84          |  _:
  85          }
  86       }
  87    }
  88
  89    {  for_each (Protocol, p, protocols)
  90       {  match (p)
  91          {  PROTOCOL { ty, syn ... }:
  92             {  Ty t = is_app ? ty : mkrefty(ty);
  93                Ty r = is_app ? ty : void_ty;
  94                pr("%^       %t reduce(%t, int&, int);"
  95                   "%^inline virtual %t operator () (%t) { int s; %sreduce(redex,s,0); }",
  96                    r, "", t, "redex",
  97                    r, "", t, "redex",
  98                    (is_app ? "return " : "")
  99                  );
 100                if (gen_traversal) {
 101                   pr("%^       %t traverse(%t);",
 102                      (syn == NOty ? void_ty : syn), "", ty, "redex");
 103                }
 104             }
 105          }
 106       }
 107    }
 108
 109    pr ("%-%^private:%+");
 110 }
 111
 112 ///////////////////////////////////////////////////////////////////////////////
 113 //
 114 //  Method to generate literals matching code.
 115 //
 116 ///////////////////////////////////////////////////////////////////////////////
 117 void RewritingCompiler::gen_bottomup_literal
 118    ( Id             rewrite_class,  // name of the rewrite class
 119      TyQual         qual,           // type qualifiers
 120      Ty             ty,             // type of literal
 121      FunctorMap&    F               // functor map
 122    )
 123 {  Bool is_app = qual & QUALapplicative;
 124    pr ("%^inline %t %s::reduce(%t, int& s__, int r__)"
 125        "%^{%+",
 126        (is_app ? ty : void_ty), "",
 127        rewrite_class, ty, "redex");
 128
 129    Exp selector     = IDexp("redex");
 130    MatchExps  exps  = #[ MATCHexp(selector,0) ];
 131    MatchRules rules = #[];
 132
 133    // Translate patterns into matching rules.
 134    foreach_entry (e, F.literal_map)
 135    {  Literal l = (Literal)F.literal_map.key(e);
 136       if (type_of(l) == ty)
 137       {  Functor f = (Functor)F.literal_map.value(e);
 138          Pat pat   = LITERALpat(l);
 139          pat->selector = selector;
 140          MatchRule r = MATCHrule(0,pat,NOexp,NOcost,
 141                           #[ SETSTATEdecl(F.tree_gen->go(f)) ]);
 142
 143          if (rules == #[])
 144             rules =
 145               #[ MATCHrule(0,WILDpat(), NOexp, NOcost, #[SETSTATEdecl(0)])];
 146          rules = #[ r ... rules ];
 147       }
 148    }
 149
 150    // Compile the matching code.
 151    if (rules != #[])  gen_match_stmt(exps,rules,MATCHnotrace);
 152    else               pr ("%^s__ = 0;");
 153
 154    if (is_app) pr ("%^return redex;");
 155    pr ("%-%^}\n\n");
 156 }
 157
 158 ///////////////////////////////////////////////////////////////////////////////
 159 //
 160 //  Method to generate the bottom up traversal code for one constructor.
 161 //
 162 ///////////////////////////////////////////////////////////////////////////////
 163 static void gen_one_traversal
 164    (RewritingCompiler& C, FunctorMap& F, Id id,
 165     TyQual qual, Functor f, Cons cons, int arity, Ty datatype_ty)
 166 {  Bool is_app = qual & QUALapplicative;
 167    const TreeAutomaton& treeGen = *F.tree_gen;
 168    Bool is_array_con = is_array_constructor(cons->name);
 169    Ty ty = component_ty(datatype_ty, cons);
 170    Exp e = select(IDexp("redex"),cons);
 171    Bool relevant[256];
 172    Bool is_record = false;
 173
 174    // generate temporaries
 175    int n = arity < 0 ? arity_of(ty) : arity;
 176    {  for (int j = 0; j < n; j++) C.pr("%^int s%i__;\n",j);  }
 177
 178    // Optimize out singletons
 179    Bool is_singleton = true;
 180    {  for (int i = n - 1; i >= 0; i--)
 181          if (treeGen.index_range(f,i) > 1) is_singleton = false;
 182    }
 183
 184    // Generate code to traversal the components and tally up the
 185    // costs of the subcomponents.
 186    if (is_app) C.pr("%^redex = %S%+", cons->name);
 187    match (ty)
 188    {  NOty: { if (is_app) C.pr ("%-;\n"); }
 189    |  TYCONty(TUPLEtycon, tys):
 190       {  int i; Tys ts;
 191          if (is_app) C.pr("(");
 192          for(i = 0, ts = tys; i < n && ts; i++, ts = ts->_2)
 193          {  if (F.is_known_type(ts->_1))
 194             {  C.pr ("%^reduce(%e, s%i__, r__)%s\n",
 195                      DOTexp(e,index_of(i+1)), i,
 196                      (is_app ? (i != n - 1 ? "," : "") : ";")
 197                     );
 198             } else {
 199                if (is_app)
 200                   C.pr ("%^(s%i__ = 0, %e)%s // %T\n",
 201                         i, DOTexp(e,index_of(i+1)),
 202                         (i != n - 1 ? "," : ""), ts->_1);
 203                else
 204                   C.pr ("%^s%i__ = 0; // %T\n", i, ts->_1);
 205             }
 206          }
 207          if (is_app) C.pr("%-%^);\n");
 208       }
 209    |  TYCONty(RECORDtycon (labs,_), tys):
 210       {  int i; Tys ts; Ids l;
 211          int n = length(tys);
 212          is_record = true;
 213          if (is_app) C.pr("(");
 214          for (l = labs, ts = tys, i = 0; l && ts; l = l->_2, ts = ts->_2, i++)
 215          {  if (F.is_known_type(ts->_1))
 216             {  C.pr ("%^reduce(%e, s%i__, r__)%s\n", DOTexp(e,l->_1), i,
 217                      (is_app ? (i != n - 1 ? "," : "") : ";"));
 218                relevant[i] = true;
 219             } else
 220             {  if (is_app)
 221                   C.pr ("%^(s%i__ = 0, %e)%s // %T\n",
 222                         i, DOTexp(e,l->_1),
 223                         (i != n - 1 ? "," : ""), ts->_1);
 224                else
 225                   C.pr ("%^s%i__ = 0; // %T\n", i, ts->_1);
 226                relevant[i] = false;
 227             }
 228          }
 229          if (is_app) C.pr("%-%^);\n");
 230       }
 231    |  _:
 232       {  if (is_app) C.pr("(");
 233          if (is_array_con)
 234          {  if (F.is_known_type(ty))
 235             {  for (int i = 0; i < arity; i++)
 236                {  C.pr ("%^reduce(%e(%i), s%i__, r__)%s\n",
 237                         DOTexp(e,"at"), i, i,
 238                         (is_app ? (i != n - 1 ? "," : "") : ";"));
 239                }
 240             } else
 241             {  for (int i = 0; i < arity; i++)
 242                {  C.pr ("%^(s_%i__ = 0, %e(%i))%s// %T\n",
 243                         i, DOTexp(e,"at"), i,
 244                         (is_app ? (i != n - 1 ? "," : "") : ";"), ty);
 245                }
 246             }
 247          } else
 248          {  if (F.is_known_type(ty))
 249             {  C.pr ("%^reduce(%e, s0__, r__)%s\n", e, (is_app ? "" : ";"));
 250             } else {
 251                if (is_app)
 252                   C.pr ("%^(s0__ = 0, %e) // %T\n", e, ty);
 253                else
 254                   C.pr ("%^s0__ = 0; // %T\n", ty);
 255             }
 256          }
 257          if (is_app) C.pr("%-%^);\n");
 258       }
 259    }
 260
 261    // Generate code to compute the new state.
 262    if (treeGen.arity_of(f) == 0 && ty != NOty) C.pr ("%?s__ = 0;");
 263    else if (is_singleton) C.pr ("%?s__ = %i;", treeGen.go(f));
 264    else {
 265       C.pr ("%^s__ = %s_theta_%i", id, f);
 266       for (int i = 0, j = 0; i < n; i++)
 267       {  if (is_record && ! relevant[i]) continue;
 268          if (treeGen.index_range(f,i) == 1)
 269             C.pr ("[0]");
 270          else if (F.use_compression)
 271             C.pr ("[%s_check[%i + s%i__] == %i ? %s_next[%i + s%i__] : 0]",
 272                   id, treeGen.compressed_offset(f,j), j,
 273                   treeGen.compressed_index(f,j),
 274                   id, treeGen.compressed_offset(f,j), j);
 275          else
 276             C.pr ("[%s_mu_%i_%i[s%i__]]", id, f, j, j);
 277          j++;
 278       }
 279       C.pr("; ");
 280    }
 281 }
 282
 283 ///////////////////////////////////////////////////////////////////////////////
 284 //
 285 //  Method to generate the bottom up traversal code.
 286 //
 287 ///////////////////////////////////////////////////////////////////////////////
 288 static void gen_traversal
 289    (RewritingCompiler& C, FunctorMap& F, Id id,
 290     TyQual qual, Functor f, Cons cons, Ty this_ty)
 291 {  if (is_array_constructor(cons->name))
 292    {  Exp vec_exp   = select(IDexp("redex"),cons);
 293       Exp len_exp   = DOTexp(vec_exp,"len()");
 294       Exp array_exp = DOTexp(vec_exp,"at");
 295       Bool is_app = qual & QUALapplicative;
 296
 297       // switch on the length of the vector
 298       C.pr("%^switch (%e) {%+\n", len_exp);
 299
 300       // generate traversals with specific lengths
 301       foreach_entry (i, F.vector_map)
 302       {  VectorId vec_id = (VectorId)F.vector_map.key(i);
 303          Functor  fnct   = (Functor)F.vector_map.value(i);
 304          if (vec_id->cons == cons && ty_equal(vec_id->ty, this_ty))
 305          {  C.pr("%^case %i: {%+", vec_id->arity);
 306             gen_one_traversal(C,F,id,qual,fnct,cons,vec_id->arity,this_ty);
 307             C.pr("%-%^} break;");
 308          }
 309       }
 310
 311       // generate traversals of other lengths
 312       C.pr("%^default: {%+");
 313       C.pr ("%^int s0__;");
 314       if (is_app)
 315          C.pr("%^%t args_[256];", this_ty, "");
 316       C.pr("%^for(int _i_ = 0; _i_ < %e; _i_++)"
 317            "%^{  %sreduce(%e(_i_), s0__, r__); }\n",
 318            len_exp, (is_app ? "args_[_i_] = " : ""), array_exp);
 319       if (is_app)
 320          C.pr("%^redex = %S(%e,args_);\n", mangle(cons->name), len_exp);
 321       C.pr("%^s__ = 0;\n"
 322            "%-%^}%-%^}");
 323    } else
 324    {  gen_one_traversal(C,F,id,qual,f,cons,-1,this_ty);
 325    }
 326 }
 327
 328 ///////////////////////////////////////////////////////////////////////////////
 329 //
 330 //  Method to generate one set of traversals
 331 //
 332 ///////////////////////////////////////////////////////////////////////////////
 333 void gen_traversals
 334    (RewritingCompiler& C, FunctorMap& F, Id rewrite_class, Functor f,
 335     int n, Cons terms[], int opt, TyQual qual, Ty this_ty)
 336 {  Bool is_boxed = terms[0]->ty != NOty;
 337    Id prefix, suffix;
 338    if (opt & OPTtaggedpointer) { prefix = "untagp("; suffix = ")"; }
 339    else if (is_boxed) { prefix = ""; suffix = "->untag()"; }
 340    else { prefix = suffix = ""; }
 341    if (n == 1) {
 342       gen_traversal(C, F, rewrite_class, qual, f, terms[0], this_ty);
 343    } else if (n == 2) {
 344       C.pr ("%^if (%sredex%s) {%+", prefix, suffix);
 345       gen_traversal(C, F, rewrite_class, qual, f+1, terms[1], this_ty);
 346       C.pr ("%-%^} else {%+");
 347       gen_traversal(C, F, rewrite_class, qual, f, terms[0], this_ty);
 348       C.pr ("%-%^}");
 349    } else {
 350       C.pr ("%^switch ((int)%sredex%s) {%+", prefix, suffix);
 351       for (int i = 0; i < n; i++)
 352       {  C.pr ((i == n - 1 ? "%^default: { %+" : "%^case %*: { %+"),
 353                terms[i], #[], false);
 354          gen_traversal(C, F, rewrite_class, qual, f + i, terms[i], this_ty);
 355          C.pr ("} break;%-");
 356       }
 357       C.pr ("%-%^}");
 358    }
 359 }
 360
 361 ///////////////////////////////////////////////////////////////////////////////
 362 //
 363 //  Method to generate action code for a datatype rewrite.
 364 //
 365 ///////////////////////////////////////////////////////////////////////////////
 366 static void gen_action(RewritingCompiler& C, FunctorMap& F, Id id, Ty ty)
 367 {
 368    HashTable::Entry * e = F.rule_map.lookup(ty);
 369    if (e) {
 370       const TreeAutomaton& treeGen = *F.tree_gen;
 371
 372       // Check whether this subset of rules contains guards or
 373       // cost expressions.
 374       MatchRules rules = (MatchRules)F.rule_map.value(e);
 375       Bool has_guard    = false;
 376       Bool has_cost_exp = false;
 377       {  for_each (MatchRule, r, rules)
 378          {  match (r)
 379             {  MATCHrule(_,_,guard,cost,_):
 380                {  if (guard != NOexp) has_guard = true;
 381                   match (cost)
 382                   {  EXPcost _: { has_cost_exp = true; }
 383                   |  _: // skip
 384                   }
 385                }
 386             }
 387          }
 388       }
 389
 390       if (has_cost_exp || F.has_syn_attrib || F.gen_traversal)
 391          C.pr("%^Rule rule__ = -1;");
 392
 393       if (has_cost_exp) {
 394          // Case when there are cost minimization to perform.
 395          C.pr ("%^const unsigned char * a__ = %s_accept[s__];"
 396                "%^Cost cost__ = infinite_cost, tmp_cost__;"
 397                "%^do {%+",
 398                id);
 399
 400          // Generate guard and cost minimization code.
 401          for_each (MatchRule, r, rules)
 402          {  match (r)
 403             {  MATCHrule(_,_,guard,cost,action):
 404                {  int rule_no = r->rule_number;
 405                   C.pr ("%^if (a__[%i] & %i)%+%^",
 406                         (rule_no / 8), 1 << (rule_no & 7));
 407                   if (guard != NOexp) C.pr("if (%e) ", guard);
 408                   match (cost)
 409                   {  NOcost:        // if no cost is used, assume cost of zero
 410                      { C.pr("{ cost__ = 0; rule__ = %i; }", rule_no); }
 411                   |  INTcost i:     // a constant integer cost
 412                      { C.pr("if (%i < cost__)"
 413                             "%+%^{ cost__ = %i; rule__ = %i; }%-",
 414                              i, i, rule_no); }
 415                   |  EXPcost (e,_): // a cost expression
 416                      { C.pr("if ((tmp_cost__ = %e) < cost__)"
 417                             "%+%^{ cost__ = tmp_cost__; rule__ = %i; }%-",
 418                              e, rule_no); }
 419                   }
 420                   C.pr("%-");
 421                }
 422             }
 423          }
 424
 425          // Update the new cost
 426          C.pr ("%-%^} while (0);");
 427
 428          if (! F.gen_traversal)
 429          {  C.pr ("%^switch (rule__) {%+");
 430
 431             // Gererate all the actions.
 432             {  for_each (MatchRule, r, rules)
 433                {  match (r)
 434                   {  MATCHrule(_,_,_,_,action):
 435                      { C.pr ("%^case %i: {%+%&%-%?} break;", r->rule_number, action); }
 436                   }
 437                }
 438             }
 439             C.pr ("%-%^}");
 440          }
 441
 442       } else {
 443          // Case when all the costs are zero.
 444
 445          // If we have a guard then generate code that performs
 446          // state to accept rule decoding at runtime.
 447          // Otherwise, perform the decoding at compile time.
 448          if (has_guard) {
 449             C.pr("%^const Rule * o__ = %s_accept_vector + %s_accept_base[s__];"
 450                  "%-%^accept__:%+"
 451                  "%^switch (*o__) {%+", id, id);
 452          } else if (F.gen_traversal) {
 453             C.pr("%^rule__ = %s_accept1[s__];",id);
 454          } else {
 455             C.pr("%^switch (s__) {%+");
 456          }
 457
 458          //  Now emit all the action code.
 459          if (! F.gen_traversal || has_guard)
 460          {  for_each (MatchRule, r, rules)
 461             {  match (r)
 462                {  MATCHrule(_,_,guard,_,action):
 463                   {  if (has_guard) {
 464                         C.pr("%^case %i: ", r->rule_number);
 465                      } else {
 466                         int rule_no = r->rule_number;
 467                         Bool used = false;
 468                         for (int s = treeGen.number_of_states() - 1; s >= 0; s--)
 469                            if (treeGen.accept1_rule(s) == rule_no)
 470                            {  C.pr ("%^case %i: ", s); used = true; }
 471                         if (! used) continue;
 472                         }
 473                      if (guard != NOexp) C.pr ("if (%e)%^", guard);
 474                      if (F.gen_traversal)
 475                         C.pr ("rule__ = %i;", r->rule_number);
 476                      else
 477                         C.pr ("%+{%&}%-", action);
 478                      if (guard != NOexp)
 479                          C.pr ("%^else { ++o__; goto accept__; }");
 480                      C.pr (" break;");
 481                   }
 482                }
 483             }
 484             C.pr("%-%^}");
 485          }
 486       }
 487    }
 488 }
 489
 490 ///////////////////////////////////////////////////////////////////////////////
 491 //
 492 //  Method to generate datatype rewriting code.
 493 //
 494 ///////////////////////////////////////////////////////////////////////////////
 495 void RewritingCompiler::gen_bottomup_datatype
 496    ( Id             rewrite_class,  // name of the rewrite class
 497      TyQual         qual,           // type qualifiers
 498      Ty             ty,             // type of datatype
 499      FunctorMap&    F               // functor map
 500    )
 501 {  Bool is_app = qual & QUALapplicative;
 502    Ty arg_ty = is_app ? ty : mkrefty( ty );
 503    Ty ret_ty = is_app ? ty : void_ty;
 504    pr ("%^%t %s::reduce(%t, int& s__, int r__)"
 505        "%^{"
 506        "%^replacement__:%+",
 507        ret_ty, "", rewrite_class, arg_ty, "redex");
 508
 509    Bool cache_state =
 510       (Used::replacement || F.has_syn_attrib || F.gen_traversal) &&
 511        has_qual(QUALrewritable,ty) &&
 512        boxed_variants(ty) > 0;
 513
 514    Id redex;
 515
 516    match (ty)
 517    {  TYCONty(DATATYPEtycon { opt ... }, _) | opt & OPTtaggedpointer:
 518          { redex = "derefp(redex)"; }
 519    |  _: { redex = "redex"; }
 520    }
 521
 522    // generate code to cut short replacement.
 523    if (cache_state)
 524       pr ("%^if (r__ && boxed(redex) && %s->has_rewrite_state())"
 525           "%^{ s__ = %s->get_rewrite_state(); return%s; }",
 526           redex, redex, (is_app ? " redex" : ""));
 527
 528    // if we have cost or synthesized attribute then allocate a new
 529    // state record.
 530    if (F.iso_tree)
 531       pr ("%^%s_StateRec * t__ = "
 532           "%^   (%s_StateRec *)mem[sizeof(%s_StateRec)];",
 533           F.class_name, F.class_name, F.class_name);
 534
 535    Functor f = (Functor)F.type_map[ty];
 536
 537    // Generate code for bottom up traversal and state computation.
 538    match (ty)
 539    {  TYCONty(DATATYPEtycon { unit, arg, terms, opt ... }, _):
 540       {  int arity = unit + arg;
 541          Bool fast_encoding = false;
 542          int first_state = F.tree_gen->go(f);
 543          if (arg == 0) {
 544             int j;
 545             for (j = arity - 1; j >= 0; j--)
 546                if (first_state + j != F.tree_gen->go(f+j)) break;
 547             fast_encoding = j < 0;
 548          }
 549
 550          if (fast_encoding) {
 551             pr ("%^s__ = redex + %i;", F.tree_gen->go(f));
 552          } else {
 553             if (arg == 0) {
 554                gen_traversals(*this, F, rewrite_class, f, unit, terms, opt, qual, ty);
 555             } else if (unit == 0) {
 556                gen_traversals(*this, F, rewrite_class, f, arg, terms, opt, qual, ty);
 557             } else {
 558                pr ("%^if (%s(redex)) {%+", (unit > 1 ? "boxed" : ""));
 559                gen_traversals(*this, F, rewrite_class, f + unit, arg, terms + unit, opt, qual, ty);
 560                pr ("%-%^} else {%+");
 561                gen_traversals(*this, F, rewrite_class, f, unit, terms, opt, qual, ty);
 562                pr ("%-%^}");
 563             }
 564          }
 565       }
 566    |  _:  // skip
 567    }
 568
 569    // Generate code for rewriting actions
 570    gen_action(*this, F, rewrite_class, ty);
 571
 572    // if (F.has_cost) pr ("%^t__->cost = cost__;");
 573
 574    // Generate code to cache the current state.
 575    if (cache_state) {
 576        pr ("%^if (boxed(redex)) {%+"
 577            "%^%s->set_rewrite_state(s__);", redex);
 578        if (F.gen_traversal) pr ("%^%s->set_rewrite_rule(rule__);", redex);
 579        pr ("%-%^}");
 580    }
 581
 582    if (is_app) pr ("%^return redex;");
 583    pr ("%-%^}\n\n");
 584 }
 585
 586 ///////////////////////////////////////////////////////////////////////////////
 587 //
 588 //  Method to generate the tree automaton tables.
 589 //
 590 ///////////////////////////////////////////////////////////////////////////////
 591 void generate_tables
 592    (Id id, RewritingCompiler& C, const TreeGrammar& G, FunctorMap& F)
 593 {  ostream& out = C.pr("");
 594
 595    if (F.gen_traversal) {
 596       // Emit the accept state tables.
 597       F.tree_gen->gen_accept1(out,id) << '\n';
 598    }
 599
 600    if (F.has_cost_exp) {
 601       // Emit the bitmap table if we have cost expressions.
 602       F.tree_gen->gen_bitmap_accept(out,id) << '\n';
 603    }
 604    if (F.has_guard) {
 605       // Emit the base/check accept state table also if we have guards.
 606       F.tree_gen->gen_accept(out,id) << '\n';
 607    }
 608
 609    // Elided in the new accept table scheme
 610    // if (F.has_guard) {
 611    //    // Generate a function that looks for the next accept rule given
 612    //    // the current state and the current rule.  This function is called
 613    //    // when the current guard fails.
 614    //    C.pr("%^static int %s_next_rule(register int s, register int r)"
 615    //         "%^{  register const unsigned char * mask = %s_accept[s];"
 616    //         "%^   while (++r < %i && (mask[r/8] & (1 << (r & 7))) == 0);"
 617    //         "%^   return r;"
 618    //         "%^}\n\n",
 619    //         id, id, F.N);
 620    // }
 621
 622    // Emit the theta tables
 623    {  for (Functor f = G.min_functor(); f <= G.max_functor(); f++)
 624       {  if (G.arity(f) > 0) {
 625             C.pr ("%^static const TreeTables::State %s_theta_%i", id, f);
 626             F.tree_gen->gen_delta(out,f);
 627             C.pr ("\n\n");
 628          }
 629       }
 630    }
 631
 632    if (F.use_compression) {
 633       // Emit the compressed index map.
 634       F.tree_gen->gen_compressed_index(out,id) << '\n';
 635       // C.pr ("%^inline int %s_go (int s, int offset)"
 636       //       "%^{ return %s_check[offset] == s ? %s_next[offset] : 0; }\n\n",
 637       //       id, id, id);
 638    } else {
 639       // Emit the index maps for each arity of each functor.
 640       {  for (Functor f = G.min_functor(); f <= G.max_functor(); f++)
 641             for (int i = 0; i < G.arity(f); i++)
 642             {  C.pr ("%^static const TreeTables::State %s_mu_%i_%i", id, f, i);
 643                F.tree_gen->gen_index(out,f,i);
 644                C.pr ("\n\n");
 645             }
 646       }
 647    }
 648 }
 649
 650 ///////////////////////////////////////////////////////////////////////////////
 651 //
 652 //  Generate the state record type.
 653 //
 654 ///////////////////////////////////////////////////////////////////////////////
 655 static void gen_state_record
 656    ( RewritingCompiler& C, FunctorMap& F,
 657      Id class_name, Protocols protocols, MatchRules rules)
 658 {
 659    C.pr ("%^%/%^// State record for rewrite class %s%^%/"
 660          "%^struct %s_StateRec {%+", class_name, class_name);
 661
 662    C.pr ("%^BURS::Rule  rule;  // reduction rule"
 663          "%^BURS::State state; // current state",
 664          class_name);
 665
 666    // Generate the cost vector
 667    if (F.has_cost)
 668    {  C.pr ("%^BURS::Cost cost__[%i];", F.type_map.size());
 669    }
 670
 671    // Map from rewrite type to type of synthesized attribute.
 672    if (F.has_syn_attrib) {
 673       HashTable syn_map (ty_hash, ty_equal);
 674       {  for_each (Protocol, p, protocols)
 675          {  match (p)
 676             {  PROTOCOL { ty, syn = syn as ! NOty ... }:
 677                { syn_map.insert(ty, syn); }
 678             |  _:
 679             }
 680          }
 681       }
 682
 683       C.pr("%^union {%+");
 684
 685       // Generate the inherited attributes for each rule that needs
 686       // an attribute.
 687       {  int i = 0;
 688          for_each (MatchRule, r, rules)
 689          {  Ty ty = r->ty;
 690             HashTable::Entry * e = syn_map.lookup(ty);
 691             if (e) {
 692                Ty syn_ty = (Ty)syn_map.value(e);
 693                C.pr ("%^%t;", syn_ty, index_of(i));
 694             }
 695             i++;
 696          }
 697       }
 698       C.pr ("%^int dummy;"
 699             "%-%^} u;");
 700    }
 701
 702
 703    if (F.has_cost)
 704       C.pr ("%^%s_StateRec * kids[%i]; // children", class_name, F.max_arity);
 705
 706    C.pr ("%-%^};\n\n");
 707 }
 708
 709 ///////////////////////////////////////////////////////////////////////////////
 710 //
 711 //  Generate a traversal function for one pattern.
 712 //
 713 ///////////////////////////////////////////////////////////////////////////////
 714 int RewritingCompiler::gen_pattern_traversal(FunctorMap& F, Pat pat, int i)
 715 {  match (pat)
 716    {  NOpat || LITERALpat _ || CONSpat _ || CONTEXTpat _ ||
 717          LEXEMEpat _: // skip
 718    |  ASpat(_,p,_,_): { i = gen_pattern_traversal(F,p,i); }
 719    |  TYPEDpat(p,_):  { i = gen_pattern_traversal(F,p,i); }
 720    |  MARKEDpat(_,p): { i = gen_pattern_traversal(F,p,i); }
 721    |  GUARDpat(p,_):  { i = gen_pattern_traversal(F,p,i); }
 722    |  APPpat (_,p):   { i = gen_pattern_traversal(F,p,i); }
 723    |  IDpat _ || WILDpat _:
 724       {  if (F.is_rewritable_type(pat->ty)) {
 725             Protocol proto = (Protocol)F.protocols[pat->ty];
 726             if (! has_qual(QUALrewritable,deref_all(pat->ty)))
 727             {  error ("%Ldatatype %T must be rewritable\n", pat->ty);
 728             }
 729             match (proto)
 730             {  PROTOCOL { syn = NOty ... }:
 731                { pr("%^traverse(%e);", pat->selector); }
 732             |  PROTOCOL { syn ... }:
 733                { pr("%^%t _%i__ = traverse(%e);", syn, "", i, pat->selector); }
 734             }
 735          }
 736          return i+1;
 737       }
 738    |  ARRAYpat(ps,_): { for_each(Pat, p, ps) i = gen_pattern_traversal(F,p,i);}
 739    |  TUPLEpat ps: { for_each(Pat, p, ps) i = gen_pattern_traversal(F,p,i); }
 740    |  EXTUPLEpat ps: { for_each(Pat, p, ps) i = gen_pattern_traversal(F,p,i); }
 741    |  RECORDpat (labPs,_):
 742          { for_each (LabPat, p, labPs) i = gen_pattern_traversal(F,p.pat,i); }
 743    |  LISTpat { head, tail ... }:
 744       {  for_each (Pat, p, head) i = gen_pattern_traversal(F,p,i);
 745          i = gen_pattern_traversal(F,tail,i);
 746       }
 747    |  VECTORpat { array, elements, len ... }:
 748       {  for_each (Pat, p, elements) i = gen_pattern_traversal(F,p,i);
 749          i = gen_pattern_traversal(F,array,i);
 750          i = gen_pattern_traversal(F,len,i);
 751       }
 752    |  _:  { bug("RewritingCompiler::gen_pattern_traversal: %p", pat); }
 753    }
 754    return i;
 755 }
 756
 757 ///////////////////////////////////////////////////////////////////////////////
 758 //
 759 //  Method to generate an attribute evaluation traversal routine for
 760 //  a datatype.  This is the second pass of the algorithm.  We assume
 761 //  that the tree has already been properly labeled.
 762 //
 763 ///////////////////////////////////////////////////////////////////////////////
 764 void RewritingCompiler::gen_datatype_traversal (FunctorMap& F, Ty ty)
 765 {  HashTable::Entry * e = F.rule_map.lookup(ty);
 766    if (e)
 767    {  MatchRules rules = (MatchRules)F.rule_map.value(e);
 768       Functor    f     = (Functor)F.type_map[ty];
 769       Ty syn_ty;
 770
 771       // Check the protocol of this datatype
 772       Protocol proto = (Protocol)F.protocols[ty];
 773       match (proto)
 774       {  PROTOCOL { syn = NOty ... }: { syn_ty = void_ty; }
 775       |  PROTOCOL { syn ... }:        { syn_ty = syn; }
 776       }
 777
 778       // The name and protocol of this traversal function
 779       pr("%^%t %s::traverse(%t)"
 780          "%^{%+",
 781          syn_ty, "", F.class_name, ty, "redex"
 782         );
 783
 784       if (syn_ty != void_ty) pr ("%^%t;", syn_ty, "__");
 785
 786       // The name and protocol of this traversal function
 787       match (ty)
 788       {  TYCONty(DATATYPEtycon { unit = 0, arg, opt ... }, _):
 789          {  Id redex_var = (opt & OPTtaggedpointer) ? "derefp(redex)" : "redex";
 790             pr("%^int r__ = %s->get_rewrite_rule();", redex_var); }
 791       |  TYCONty(DATATYPEtycon { unit, arg, opt ... }, _):
 792          {  Id table_name = vars.new_label();
 793             Id redex_var = (opt & OPTtaggedpointer) ? "derefp(redex)" : "redex";
 794             if (unit > 1)
 795             {  pr("%^static const Rule %s[] = { ",table_name);
 796                for (int i = 0; i < unit; i++)
 797                {  pr ("%i", F.tree_gen->accept1_rule(F.tree_gen->go(f+i)));
 798                   if (i != unit - 1) pr (", ");
 799                }
 800                pr (" };\n");
 801                pr("%^int r__ = boxed(redex) ? %s->get_rewrite_rule() : %s[int(%s)];",
 802                   redex_var, table_name, redex_var);
 803             } else
 804                pr("%^int r__ = boxed(redex) ? %s->get_rewrite_rule() : %i;",
 805                   redex_var, F.tree_gen->accept1_rule(F.tree_gen->go(f)));
 806          }
 807       |  _: { bug("RewritingCompiler::gen_datatype_traversal()"); }
 808       }
 809
 810       // The rule actions
 811       pr ("%^switch (r__) {%+");
 812
 813       for_each(MatchRule, r, rules)
 814       {  match (r)
 815          {  MATCHrule(_,pat,_,_,action):
 816             {  pr ("%^case %i: {%+", r->rule_number);
 817                gen_pattern_traversal(F,pat,0);
 818                pr ("%^%&} break;%-", action);
 819             }
 820          }
 821       }
 822
 823       // Epilogue
 824       pr("%-%^}");
 825       if (syn_ty != void_ty) pr ("%^return __;");
 826       pr("%-%^}\n\n");
 827    }
 828 }
 829
 830 ///////////////////////////////////////////////////////////////////////////////
 831 //
 832 //  Top level method to compile a set of rewrite rules.
 833 //
 834 ///////////////////////////////////////////////////////////////////////////////
 835 void RewritingCompiler::gen_rewrite(Id rewrite_class, MatchRules rules)
 836 {
 837    MemPoolMark marker = mem_pool.getMark(); // get a memory pool marker
 838    int         N      = length(rules);      // number of rules
 839    FunctorMap  F(N,rewrite_class);          // the functor encoding map.
 840    int    last_errors = errors;
 841    Protocols protocols = lookup_rewrite_class(rewrite_class);
 842
 843    // Encodes and enters all protocols.
 844    {  for_each (Protocol, p, protocols)
 845       {  match (p)
 846          {  PROTOCOL { ty, syn ... }:
 847             {  F.encode(ty); F.protocols.insert(ty,p);
 848                if (syn != NOty) F.has_syn_attrib = true;
 849             }
 850          }
 851       }
 852    }
 853
 854    // instrument code
 855    if (PropOptions::trace) instrument_trace(rules);
 856
 857    // Type checking, then partition rules by type and encode the patterns.
 858    F.partition_rules (rules);
 859
 860    // Checks for missing protocols.
 861    foreach_entry (e, F.type_map)
 862    {  Ty ty = (Ty)F.type_map.key(e);
 863       if (! F.protocols.contains(ty))
 864          error ("%Lmissing type %T in the protocols of rewrite class %s\n",
 865                 ty, rewrite_class);
 866    }
 867
 868    if (errors == last_errors)
 869    {
 870       // Tree grammar
 871       TreeGrammar G;
 872       TreeProduction * productions
 873          = (TreeProduction *)mem_pool.c_alloc(sizeof(TreeProduction) * N);
 874       Id * functor_names
 875          = (Id *)mem_pool.c_alloc(sizeof(Id) * F.functors);
 876       Id * variable_names
 877          = (Id *)mem_pool.c_alloc(sizeof(Id) * (F.variables + N + 4));
 878       TyQual qual = TyQual(rewrite_qual.lookup(rewrite_class)->v);
 879       F.gen_traversal = (qual & QUALtreeparser) || F.has_syn_attrib;
 880
 881       // translate patterns into terms
 882       {  int i = 0;
 883          for_each (MatchRule, r, rules)
 884          {  match (r)
 885             {  MATCHrule(lhs,pat,guard,cost,_):
 886                {  int rule_no = lhs ? Variable(F.var_map.lookup(lhs)->v) : 0;
 887                   int cst;
 888                   match (cost)  // extract cost
 889                   {  NOcost:     { cst = TreeTables::zero_cost; }
 890                   |  INTcost c:  { cst = c;
 891                                    if (c != 0) F.has_cost = true;
 892                                  }
 893                   |  EXPcost _:  { cst = TreeTables::zero_cost;
 894                                    F.has_cost_exp = true;
 895                                  }
 896                   }
 897                   productions[i] = TreeProduction(rule_no,F.trans(pat),cst);
 898                   if (guard != NOexp) F.has_guard = true;
 899                   i++;
 900                }
 901             }
 902          }
 903       }
 904
 905       F.compute_names (functor_names, variable_names);
 906
 907       // compile the tree grammar
 908       G.compile (N, productions, functor_names, variable_names,
 909                  0, F.functors - 1, 0);
 910
 911       if (qual & QUALtopdown)
 912          gen_topdown (rewrite_class,rules,N,protocols,F,qual,
 913                       G,functor_names,variable_names);
 914       else
 915          gen_bottomup(rewrite_class,rules,N,protocols,F,qual,
 916                       G,functor_names,variable_names);
 917    }
 918    mem_pool.setMark(marker);  // reset the memory pool to reclaim memory
 919 }
 920
 921 ///////////////////////////////////////////////////////////////////////////////
 922 //
 923 //   Generate code for bottom-up rewriting.
 924 //
 925 ///////////////////////////////////////////////////////////////////////////////
 926 void RewritingCompiler::gen_bottomup( Id           rewrite_class,
 927                                       MatchRules   rules,
 928                                       int          N,
 929                                       Protocols    protocols,
 930                                       FunctorMap&  F,
 931                                       TyQual       qual,
 932                                       TreeGrammar& G,
 933                                       Id           functor_names[],
 934                                       Id           variable_names[]
 935                                     )
 936 {
 937    // Create a new memory pool
 938    MemPool my_pool(4096);
 939
 940    // allocate a new tree automata compiler
 941    debug_msg("[Compiling %i rewriting rules for class %s]\n",
 942           N, rewrite_class);
 943    if (PropOptions::burs || F.has_cost)
 944       F.tree_gen = new BURS_Gen (my_pool);
 945    else
 946       F.tree_gen = new TreeGen (my_pool);
 947
 948    // compile the tree automata
 949    F.tree_gen->compile (G);
 950    debug_msg("[Compressing index maps for class %s]\n", rewrite_class);
 951    F.tree_gen->compile_compression_index();
 952    debug_msg("[Done]\n");
 953
 954    // check for compression rate
 955    double shrinkage = F.tree_gen->compression_rate();
 956    if (shrinkage <= 0.3 || F.tree_gen->number_of_states() <= 40) {
 957       F.use_compression = false;
 958    }
 959
 960    // Generate the state record type.
 961    gen_state_record(*this, F, rewrite_class, protocols, rules);
 962
 963    // generate the tables
 964    generate_tables(rewrite_class, *this, G, F);
 965
 966    // Choose whether to build an isomorphic parse tree or
 967    // using the semantic value stack (or neither)
 968    if (F.has_cost)       { F.iso_tree = true; }
 969    if (F.has_syn_attrib) { F.use_stack = true; }
 970    print_semantic_stack = F.use_stack;
 971
 972    // generate the matching code for literals
 973    gen_bottomup_literal(rewrite_class, qual, integer_ty, F);
 974    gen_bottomup_literal(rewrite_class, qual, character_ty, F);
 975    gen_bottomup_literal(rewrite_class, qual, real_ty, F);
 976    gen_bottomup_literal(rewrite_class, qual, string_ty, F);
 977    gen_bottomup_literal(rewrite_class, qual, quark_ty, F);
 978    pr ("%n#ifdef PROP_BOOL_IS_IMPLEMENTED\n");
 979    gen_bottomup_literal(rewrite_class, qual, bool_ty, F);
 980    pr ("#endif\n\n");
 981
 982    // generate the matching code for datatypes
 983    {  foreach_entry(e, F.type_map)
 984       {  Ty ty = (Ty)F.type_map.key(e);
 985          gen_bottomup_datatype(rewrite_class, qual, ty, F);
 986          if (F.gen_traversal)
 987             gen_datatype_traversal(F, ty);
 988       }
 989    }
 990
 991    // print report if necessary
 992    if (PropOptions::generate_report) F.print_report(open_logfile());
 993
 994    // Clean up
 995    delete F.tree_gen;
 996 }