prop-src/rwgen.cc

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //  This file is generated automatically using Prop (version 2.3.6),
   3 //  last updated on Nov 2, 1999.
   4 //  The original source file is "rwgen.pcc".
   5 ///////////////////////////////////////////////////////////////////////////////
   6
   7 #define PROP_QUARK_USED
   8 #include <propdefs.h>
   9 ///////////////////////////////////////////////////////////////////////////////
  10 //  Quark literals
  11 ///////////////////////////////////////////////////////////////////////////////
  12 static const Quark _r_w_g_e_nco_c_c_Q1("redex");
  13 #line 1 "rwgen.pcc"
  14 ///////////////////////////////////////////////////////////////////////////////
  15 //
  16 //  This file implements the tree rewriting/tree parsing compiler.
  17 //  This is used to implement the rewrite class/rewrite constructs of Prop.
  18 //
  19 ///////////////////////////////////////////////////////////////////////////////
  20 #include <iostream>
  21 #include <strstream>
  22 #include <AD/automata/treegram.h>
  23 #include <AD/automata/treegen.h>
  24 #include <AD/automata/topdowng.h>
  25 #include <AD/rewrite/burs_gen.h>
  26 #include <AD/strings/quark.h>
  27 #include "funmap.h"
  28 #include "ir.h"
  29 #include "ast.h"
  30 #include "matchcom.h"
  31 #include "type.h"
  32 #include "hashtab.h"
  33 #include "datagen.h"
  34 #include "config.h"
  35 #include "rwgen.h"
  36 #include "options.h"
  37 #include "trs.h"
  38
  39 ///////////////////////////////////////////////////////////////////////////////
  40 //
  41 //  Constructor and destructor of the rewriting compiler.
  42 //
  43 ///////////////////////////////////////////////////////////////////////////////
  44 RewritingCompiler::RewritingCompiler()
  45    : rewriters(
  46 #line 32 "rwgen.pcc"
  47 #line 32 "rwgen.pcc"
  48 nil_1_
  49 #line 32 "rwgen.pcc"
  50 #line 32 "rwgen.pcc"
  51 ), Fmap(0), trs(0) {}
  52 RewritingCompiler::~RewritingCompiler() {}
  53
  54 ///////////////////////////////////////////////////////////////////////////////
  55 //
  56 //  Import some type definitions from the tree grammar and hash table
  57 //  classes.
  58 //
  59 ///////////////////////////////////////////////////////////////////////////////
  60 typedef TreeGrammar::TreeProduction TreeProduction;
  61 typedef TreeGrammar::Cost           TreeCost;
  62
  63 ///////////////////////////////////////////////////////////////////////////////
  64 //
  65 //  Compute the name of the redex.
  66 //
  67 ///////////////////////////////////////////////////////////////////////////////
  68 Id redex_name (Ty ty)
  69 {
  70 #line 50 "rwgen.pcc"
  71 #line 53 "rwgen.pcc"
  72 {
  73    Ty _V1 = deref_all(ty);
  74    if (_V1) {
  75       switch (_V1->tag__) {
  76          case a_Ty::tag_TYCONty: {
  77             if (boxed(((Ty_TYCONty *)_V1)->_1)) {
  78                switch (((Ty_TYCONty *)_V1)->_1->tag__) {
  79                   case a_TyCon::tag_DATATYPEtycon: {
  80                      if (
  81 #line 51 "rwgen.pcc"
  82                      (((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V1)->_1)->opt & OPTtaggedpointer)
  83 #line 51 "rwgen.pcc"
  84 ) {
  85
  86 #line 52 "rwgen.pcc"
  87                        return "derefp(redex)";
  88 #line 52 "rwgen.pcc"
  89                      } else {
  90
  91                         L1:;
  92 #line 53 "rwgen.pcc"
  93                        return "redex";
  94 #line 53 "rwgen.pcc"
  95                      }
  96                      } break;
  97                   default: { goto L1; } break;
  98                }
  99             } else { goto L1; }
 100             } break;
 101          default: { goto L1; } break;
 102       }
 103    } else { goto L1; }
 104 }
 105 #line 54 "rwgen.pcc"
 106 #line 54 "rwgen.pcc"
 107
 108 }
 109
 110 ///////////////////////////////////////////////////////////////////////////////
 111 //
 112 //  Method to create a RewriteClass
 113 //
 114 ///////////////////////////////////////////////////////////////////////////////
 115 RewriteClass::RewriteClass(Id id, Protocols p, Inherits i, TyQual q, Decls b)
 116    : ClassDefinition(REWRITE_CLASS,id,
 117 #line 63 "rwgen.pcc"
 118 #line 63 "rwgen.pcc"
 119 nil_1_
 120 #line 63 "rwgen.pcc"
 121 #line 63 "rwgen.pcc"
 122 ,add_inherit("BURS",
 123 #line 63 "rwgen.pcc"
 124 #line 63 "rwgen.pcc"
 125 nil_1_
 126 #line 63 "rwgen.pcc"
 127 #line 63 "rwgen.pcc"
 128 ,i),q,b),
 129      index_info(ty_hash,ty_equal)
 130      {  protocols = p;
 131         RewritingCompiler::add_rewrite_class(this);
 132      }
 133 RewriteClass::~RewriteClass() {}
 134
 135 ///////////////////////////////////////////////////////////////////////////////
 136 //
 137 //  Method to generate an interface of a rewrite class.
 138 //
 139 ///////////////////////////////////////////////////////////////////////////////
 140 void RewriteClass::gen_class_interface (CodeGen& C)
 141 {  Bool is_app = qualifiers & QUALapplicative;
 142    C.pr ("%-%^private:%+"
 143          "%^%s(const %s&);               // no copy constructor"
 144          "%^void operator = (const %s&); // no assignment"
 145          "%-%^public:%+"
 146          "%^struct %s_StateRec * stack__, * stack_top__;",
 147          class_name, class_name, class_name, class_name
 148         );
 149
 150    Bool gen_reducers = qualifiers & QUALtreeparser;
 151
 152    if (! gen_reducers)
 153       C.pr ("%-%^public:%+"
 154             "%^%s labeler(const char *, int&, int);"
 155             "%^%s labeler(Quark, int&, int);",
 156             (is_app ? "const char *" : "void"),
 157             (is_app ? "Quark       " : "void")
 158            );
 159
 160    {  for_each (Protocol, p, protocols)
 161       {
 162 #line 96 "rwgen.pcc"
 163 #line 130 "rwgen.pcc"
 164 {
 165 #line 98 "rwgen.pcc"
 166  Ty t = (is_app || gen_reducers) ? p->ty : mkrefty(p->ty);
 167    Ty r = (is_app || gen_reducers) ? p->ty : void_ty;
 168    if (gen_reducers)
 169     C.pr("%^       void labeler(%t);"
 170          "%^inline virtual void operator () (%t) { labeler(redex); }",
 171           t, "redex", t, "redex"
 172         );
 173    else
 174     C.pr("%^       %t labeler(%t, int&, int);"
 175          "%^inline virtual %t operator () (%t) { int s; %slabeler(redex,s,0); }",
 176           r, "", t, "redex",
 177           r, "", t, "redex",
 178           (is_app ? "return " : "")
 179         );
 180    if (gen_reducers)
 181    {  if (p->inh != NOty)
 182        C.pr("%^       %t reduce(%t,%t,int lhs = 1);",
 183             (p->syn == NOty ? void_ty : p->syn), "", p->ty, "redex",
 184              p->inh, "inh__");
 185       else
 186        C.pr("%^       %t reduce(%t,int lhs = 1);",
 187             (p->syn == NOty ? void_ty : p->syn), "", p->ty, "redex");
 188    }
 189    if (! gen_reducers && p->syn != NOty)
 190       error("%Lsynthesized attribute '%T' can only be used in treeparser mode in rewrite class %s\n",
 191             p->syn, class_name);
 192    if (! gen_reducers && p->inh != NOty)
 193       error("%Linherited attribute '%T' can only be used in treeparser mode in rewrite class %s\n",
 194             p->syn, class_name);
 195    //if (gen_reducers && ! has_qual(QUALrewritable,deref_all(ty)))
 196    //   error("%Ltype '%T' is not rewritable in treeparser mode rewrite class %s\n",
 197    //         ty, class_name);
 198
 199 #line 130 "rwgen.pcc"
 200 }
 201 #line 131 "rwgen.pcc"
 202 #line 131 "rwgen.pcc"
 203
 204       }
 205    }
 206
 207    C.pr ("%-%^private:%+");
 208 }
 209
 210 ///////////////////////////////////////////////////////////////////////////////
 211 //
 212 //  Method to generate the body of a rewrite class
 213 //
 214 ///////////////////////////////////////////////////////////////////////////////
 215 void RewritingCompiler::gen_rewrite
 216    (Id name, RewriteIndexings Is, MatchRules rules)
 217 {  ////////////////////////////////////////////////////////////////////////////
 218    // Get the current limit on the memory pool
 219    ////////////////////////////////////////////////////////////////////////////
 220    MemPoolMark marker = mem_pool.getMark();
 221
 222    indices = Is;
 223
 224
 225    ////////////////////////////////////////////////////////////////////////////
 226    // Instrument the rules if tracing is used.
 227    ////////////////////////////////////////////////////////////////////////////
 228    if (options.trace) instrument_trace(rules);
 229
 230    ////////////////////////////////////////////////////////////////////////////
 231    // Create a functor map
 232    ////////////////////////////////////////////////////////////////////////////
 233    FunctorMap F(name,rules);
 234    FunctorMap * oldFmap = Fmap;
 235    Fmap = &F;
 236
 237    ////////////////////////////////////////////////////////////////////////////
 238    // Compile rules into a tree grammar
 239    ////////////////////////////////////////////////////////////////////////////
 240    if (F.ok())
 241    {  gen_trace_macro (name, F);
 242       if (F.dynamic_search) gen_dynamic_rewriter(F);
 243       else                  gen_static_rewriter(F);
 244    }
 245
 246    ////////////////////////////////////////////////////////////////////////////
 247    // Reset the limit on the memory pool
 248    ////////////////////////////////////////////////////////////////////////////
 249    mem_pool.setMark(marker);
 250    Fmap = oldFmap;
 251 }
 252
 253 ///////////////////////////////////////////////////////////////////////////////
 254 //
 255 //  Method to generate a bottom-up tree automaton, with static tables.
 256 //  This is faster than the dynamic method but may utilize much more space
 257 //  and preprocessing time.
 258 //
 259 ///////////////////////////////////////////////////////////////////////////////
 260 void RewritingCompiler::gen_static_rewriter (FunctorMap& F)
 261 {
 262    MemPool my_pool(4096);                    // Create a new memory pool
 263    // Create a new tree automaton
 264    if (F.has_cost) F.tree_gen = new BURS_Gen(my_pool);
 265    else            F.tree_gen = new TreeGen (my_pool);
 266    F.tree_gen->compile(F.G);                 // Compile the tree grammar
 267    F.tree_gen->compile_compression_index();  // Generate the compressed index
 268    if (options.optimize_rewrite)
 269    {  optimize_rewrite();
 270    }
 271
 272    ////////////////////////////////////////////////////////////////////////////
 273    // Check whether we should use the compressed index maps.
 274    ////////////////////////////////////////////////////////////////////////////
 275    double shrinkage = F.tree_gen->compression_rate();
 276    if (shrinkage <= 0.3 || F.tree_gen->number_of_states() <= 40)
 277       F.use_compression = false;
 278
 279    ////////////////////////////////////////////////////////////////////////////
 280    // Generate the set of tables
 281    ////////////////////////////////////////////////////////////////////////////
 282    generate_tables(F);
 283
 284    ////////////////////////////////////////////////////////////////////////////
 285    // Generate code for the labelers
 286    ////////////////////////////////////////////////////////////////////////////
 287    generate_static_labelers(F);
 288
 289    ////////////////////////////////////////////////////////////////////////////
 290    // Generate code for the reducers
 291    ////////////////////////////////////////////////////////////////////////////
 292    if (F.gen_reducers) generate_reducers(F);
 293
 294    ////////////////////////////////////////////////////////////////////////////
 295    // Print a report
 296    ////////////////////////////////////////////////////////////////////////////
 297    if (options.generate_report)
 298    {  F.print_report(open_logfile());
 299       if (trs) trs->print_report(open_logfile());
 300    }
 301
 302    ////////////////////////////////////////////////////////////////////////////
 303    // Cleanup the tree automaton compiler.
 304    ////////////////////////////////////////////////////////////////////////////
 305    delete F.tree_gen;
 306    delete F.topdown_gen;
 307    delete trs;
 308    F.tree_gen = 0;
 309    F.topdown_gen = 0;
 310 }
 311
 312 ///////////////////////////////////////////////////////////////////////////////
 313 //
 314 //  Method to generate the labelers.  The labelers are responsible for
 315 //  traversing the tree bottom-up and compute the states.
 316 //
 317 ///////////////////////////////////////////////////////////////////////////////
 318 void RewritingCompiler::generate_static_labelers(FunctorMap& F)
 319 {  ////////////////////////////////////////////////////////////////////////////
 320    // Generate the labelers for the literals
 321    ////////////////////////////////////////////////////////////////////////////
 322    gen_literal_labeler(F, string_ty);
 323    gen_literal_labeler(F, quark_ty);
 324
 325    ////////////////////////////////////////////////////////////////////////////
 326    // Generate the labelers for the datatypes
 327    ////////////////////////////////////////////////////////////////////////////
 328    foreach_entry (e, F.type_map)
 329    {  Ty ty = Ty(F.type_map.key(e));
 330       debug_msg("[Rewrite class %s: generating labeler for datatype %T\n",
 331                 F.class_name, ty);
 332       gen_datatype_labeler(F, ty);
 333    }
 334 }
 335
 336 ///////////////////////////////////////////////////////////////////////////////
 337 //
 338 //  Method to generate the automaton tables for a rewrite class.
 339 //
 340 ///////////////////////////////////////////////////////////////////////////////
 341 void RewritingCompiler::generate_tables(FunctorMap& F)
 342 {  Id id = F.class_name;
 343
 344    ////////////////////////////////////////////////////////////////////////////
 345    // Table of the first matching rule.
 346    ////////////////////////////////////////////////////////////////////////////
 347    if (F.gen_reducers && ! F.has_guard) F.tree_gen->gen_accept1(*output,id);
 348
 349    ////////////////////////////////////////////////////////////////////////////
 350    // Table of bitmaps of all the accepted rules.
 351    ////////////////////////////////////////////////////////////////////////////
 352    // if (F.has_cost_exp) F.tree_gen->gen_bitmap_accept(*output,id);
 353
 354    ////////////////////////////////////////////////////////////////////////////
 355    // Table of lists of all the accepted rules.
 356    ////////////////////////////////////////////////////////////////////////////
 357    if (F.has_guard || F.has_cost_exp) F.tree_gen->gen_accept(*output,id);
 358
 359    ////////////////////////////////////////////////////////////////////////////
 360    // Generate the theta tables
 361    ////////////////////////////////////////////////////////////////////////////
 362    for(Functor f = F.G.min_functor(); f <= F.G.max_functor(); f++)
 363    {  if (F.G.arity(f) > 0)
 364       {  Bool is_singleton = true;
 365          for (int i = 0; i < F.G.arity(f); i++)
 366          {  if (F.tree_gen->index_range(f,i) > 1)
 367             { is_singleton = false; break; }
 368          }
 369          if (! is_singleton)
 370          {  pr("%^");
 371             F.tree_gen->gen_theta(*output,f,id);
 372             pr("\n\n");
 373          }
 374       }
 375    }
 376
 377    ////////////////////////////////////////////////////////////////////////////
 378    // Generate the mu tables
 379    ////////////////////////////////////////////////////////////////////////////
 380    if (F.use_compression)
 381    {  ////////////////////////////////////////////////////////////////////////
 382       // Generate the compressed mu's
 383       ////////////////////////////////////////////////////////////////////////
 384       F.tree_gen->gen_compressed_index(*output,id);
 385    } else
 386    {  ////////////////////////////////////////////////////////////////////////
 387       // Generate the uncompressed mu's
 388       ////////////////////////////////////////////////////////////////////////
 389       for(Functor f = F.G.min_functor(); f <= F.G.max_functor(); f++)
 390       {  for (int i = 0; i < F.G.arity(f); i++)
 391          {  if (F.tree_gen->index_range(f,i) > 1)
 392             {  pr("%^");
 393                F.tree_gen->gen_index(*output,f,i,id);
 394                pr("\n\n");
 395             }
 396          }
 397       }
 398    }
 399 }
 400
 401 ///////////////////////////////////////////////////////////////////////////////
 402 //
 403 //  Method to generate the literal labelers.
 404 //
 405 ///////////////////////////////////////////////////////////////////////////////
 406 void RewritingCompiler::gen_literal_labeler(FunctorMap& F, Ty ty)
 407 {  ///////////////////////////////////////////////////////////////////////////
 408    // Protocol of this new labeler
 409    ///////////////////////////////////////////////////////////////////////////
 410    pr ("%^inline %t %s::labeler(%t,int& s__,int)"
 411        "%^{%+",
 412        (F.is_applicative ? ty : void_ty), "", // return type
 413        F.class_name, ty, "redex"              // argument is always named redex
 414       );
 415
 416    ///////////////////////////////////////////////////////////////////////////
 417    // Rules to apply before rewriting
 418    ///////////////////////////////////////////////////////////////////////////
 419    gen_before_rules(F,ty);
 420    gen_preorder_rules(F,ty);
 421    gen_topdown_rules(F,ty);
 422
 423    ///////////////////////////////////////////////////////////////////////////
 424    // The selector is named 'redex'
 425    ///////////////////////////////////////////////////////////////////////////
 426    Exp        selector = IDexp("redex");
 427    MatchExps  exps     =
 428 #line 355 "rwgen.pcc"
 429 #line 355 "rwgen.pcc"
 430 list_1_(MATCHexp(selector,0))
 431 #line 355 "rwgen.pcc"
 432 #line 355 "rwgen.pcc"
 433 ;
 434    MatchRules rules    = // Default is state zero.
 435
 436 #line 357 "rwgen.pcc"
 437 #line 357 "rwgen.pcc"
 438 list_1_(MATCHrule(0,WILDpat(),NOexp,NOcost,list_1_(SETSTATEdecl(0))))
 439 #line 357 "rwgen.pcc"
 440 #line 357 "rwgen.pcc"
 441 ;
 442
 443    ///////////////////////////////////////////////////////////////////////////
 444    // Now translate the pattern literals into a matching rule
 445    ///////////////////////////////////////////////////////////////////////////
 446    foreach_entry (e,F.literal_map)
 447    {  Literal l = Literal(F.literal_map.key(e));
 448       if (type_of(l) == ty)
 449       {  Functor f      = F.literal_map.value(e);
 450          Pat pat        = LITERALpat(l);
 451          pat->selector  = selector;
 452          MatchRule rule = MATCHrule(0,pat,NOexp,NOcost,
 453
 454 #line 369 "rwgen.pcc"
 455 #line 369 "rwgen.pcc"
 456 list_1_(SETSTATEdecl(F.tree_gen->go(f)))
 457 #line 369 "rwgen.pcc"
 458 #line 369 "rwgen.pcc"
 459 );
 460          rules =
 461 #line 370 "rwgen.pcc"
 462 #line 370 "rwgen.pcc"
 463 list_1_(rule,rules)
 464 #line 370 "rwgen.pcc"
 465 #line 370 "rwgen.pcc"
 466 ;
 467       }
 468    }
 469
 470    ///////////////////////////////////////////////////////////////////////////
 471    // Call the pattern matching compiler to generate the match statement.
 472    // Disable tracing code since this is not properly part of the user
 473    // program.
 474    ///////////////////////////////////////////////////////////////////////////
 475    gen_match_stmt(exps,rules,MATCHnotrace);
 476
 477    ///////////////////////////////////////////////////////////////////////////
 478    //  Rules to apply after rewriting
 479    ///////////////////////////////////////////////////////////////////////////
 480    gen_postorder_rules(F,ty);
 481
 482    ///////////////////////////////////////////////////////////////////////////
 483    // End of this routine
 484    ///////////////////////////////////////////////////////////////////////////
 485    if (F.is_applicative) pr("%^return redex;");
 486    pr("%-%^}\n\n");
 487 }
 488
 489 ///////////////////////////////////////////////////////////////////////////////
 490 //
 491 //  Method to generate the datatype labeler
 492 //
 493 ///////////////////////////////////////////////////////////////////////////////
 494 void RewritingCompiler::gen_datatype_labeler(FunctorMap& F, Ty ty)
 495 {  Ty   arg_ty = F.is_applicative ? ty : mkrefty(ty); // argument type
 496    Ty   ret_ty = F.is_applicative ? ty : void_ty;     // return type
 497
 498    ///////////////////////////////////////////////////////////////////////////
 499    // Should we cache the state we've computed?
 500    // Do so if the type is declared to be rewritable and it has at least
 501    // one boxed variant.
 502    ///////////////////////////////////////////////////////////////////////////
 503    // Bool cache_state = boxed_variants(ty) && has_qual(QUALrewritable,ty) &&
 504    //                   (Used::replacement || F.gen_reducers);
 505    Bool has_topdown_rules = F.topdown_rule_map.contains(ty);
 506
 507    ///////////////////////////////////////////////////////////////////////////
 508    // Generate the protocol of this labeler routine
 509    ///////////////////////////////////////////////////////////////////////////
 510    pr ("%^%t %s::labeler (%t, int& s__, int r__)"
 511        "%^{",
 512        ret_ty, "", F.class_name, arg_ty, "redex");
 513
 514    ///////////////////////////////////////////////////////////////////////////
 515    // Name of the redex inside this routine.
 516    ///////////////////////////////////////////////////////////////////////////
 517    gen_before_rules(F,ty);
 518
 519    pr ("%^replacement__:%+");
 520
 521    gen_preorder_rules(F,ty);
 522
 523    if (has_topdown_rules)
 524       pr("%^for (int topdown__ = 0; topdown__ <= 1; topdown__++) {%+");
 525
 526    ///////////////////////////////////////////////////////////////////////////
 527    // Name of the redex inside this routine.
 528    ///////////////////////////////////////////////////////////////////////////
 529    Id redex = redex_name(ty);
 530
 531    ///////////////////////////////////////////////////////////////////////////
 532    // Generate code to cut short the labeling process if we are caching the
 533    // state.
 534    ///////////////////////////////////////////////////////////////////////////
 535    // if (cache_state)
 536    //    pr ("%^if (r__ && boxed(redex) && %s->has_rewrite_state())"
 537    //        "%^{ s__ = %s->get_rewrite_state(); return%s; }",
 538    //        redex, redex, (F.is_applicative ? " redex" : ""));
 539    gen_get_rewrite_state(ty,redex);
 540
 541    gen_topdown_rules(F,ty);
 542
 543    ///////////////////////////////////////////////////////////////////////////
 544    // Generate code for bottomup traversal on the datatype
 545    ///////////////////////////////////////////////////////////////////////////
 546    gen_bottomup_traversals(F, ty);
 547
 548    ///////////////////////////////////////////////////////////////////////////
 549    // Generate the suffix for topdown rules.
 550    ///////////////////////////////////////////////////////////////////////////
 551    if (has_topdown_rules)
 552       pr("%-%^}");
 553
 554    ///////////////////////////////////////////////////////////////////////////
 555    // Generate code for the action routines
 556    ///////////////////////////////////////////////////////////////////////////
 557    gen_action(F,ty);
 558
 559    ///////////////////////////////////////////////////////////////////////////
 560    // Generate code to update the cached state(when applicable)
 561    ///////////////////////////////////////////////////////////////////////////
 562    // pr("%-%^update_state__: ;%+");
 563    // if (cache_state)
 564    // {  pr ("%^if (boxed(redex)) {%+"
 565    //        "%^%s->set_rewrite_state(s__);", redex);
 566    //    if (F.gen_reducers)
 567    //       pr ("%^%s->set_rewrite_rule(rule__);", redex);
 568    //    pr ("%-%^}");
 569    // }
 570    gen_set_rewrite_state_and_rule(ty,redex);
 571
 572    ///////////////////////////////////////////////////////////////////////////
 573    //  Rules to apply after rewriting
 574    ///////////////////////////////////////////////////////////////////////////
 575    gen_postorder_rules(F,ty);
 576
 577    ///////////////////////////////////////////////////////////////////////////
 578    // If it is applicative, generate a return statement
 579    ///////////////////////////////////////////////////////////////////////////
 580    if (F.is_applicative) pr ("%^return redex;");
 581
 582    ///////////////////////////////////////////////////////////////////////////
 583    // End of this routine
 584    ///////////////////////////////////////////////////////////////////////////
 585    pr ("%^%-%^}\n\n");
 586 }
 587
 588 ///////////////////////////////////////////////////////////////////////////////
 589 //
 590 //  Method to generate the bottomup traversal code for a datatype labeler.
 591 //
 592 ///////////////////////////////////////////////////////////////////////////////
 593 void RewritingCompiler::gen_bottomup_traversals(FunctorMap& F, Ty ty)
 594 {  Id redex  = redex_name(ty);
 595    Functor f = F.type_map[ty];             // functor encoding
 596
 597 #line 500 "rwgen.pcc"
 598 #line 539 "rwgen.pcc"
 599 {
 600    Ty _V2 = deref_all(ty);
 601    if (_V2) {
 602       switch (_V2->tag__) {
 603          case a_Ty::tag_TYCONty: {
 604             if (boxed(((Ty_TYCONty *)_V2)->_1)) {
 605                switch (((Ty_TYCONty *)_V2)->_1->tag__) {
 606                   case a_TyCon::tag_DATATYPEtycon: {
 607 #line 502 "rwgen.pcc"
 608                    int  arity         = ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->unit + ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->arg;  // arity of this datatype
 609                      Bool fast_encoding = false;
 610                      int  first_state   = F.tree_gen->go(f);
 611
 612                      // Check whether fast encoding should be used.
 613                      // This changes a switch statement into addition.
 614                      if (((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->arg == 0)
 615                      {  int i;
 616                         for (i = arity - 1; i >= 0; i--)
 617                            if (first_state + i != F.tree_gen->go(f+i)) break;
 618                         fast_encoding = i < 0;
 619                      }
 620
 621                      //
 622                      // Views cannot use the fast encoding
 623                      //
 624                      if (((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->qualifiers & QUALview) fast_encoding = false;
 625
 626                      if (fast_encoding)
 627                      {  pr ("%^s__ = redex + %i;", F.tree_gen->go(f)); }
 628                      else  // Slower encoding
 629                      {  if (((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->qualifiers & QUALview)
 630                         {  gen_bottomup_traversals(F, f, ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->unit + ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->arg, ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->terms, ty); }
 631                         else if (((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->arg == 0)  // all unit functors
 632                         {  gen_bottomup_traversals(F, f, ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->unit, ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->terms, ty); }
 633                         else if (((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->unit == 0)  // all argument functors
 634                         {  gen_bottomup_traversals(F, f, ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->arg, ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->terms, ty); }
 635                         else
 636                         {  pr("%^if (%s(redex)) {%+", (((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->unit > 1 ? "boxed" : ""));
 637                            gen_bottomup_traversals(F, f + ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->unit, ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->arg, ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->terms + ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->unit, ty);
 638                            pr("%-%^} else {%+");
 639                            gen_bottomup_traversals(F, f, ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->unit, ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->terms, ty);
 640                            pr("%-%^}");
 641                         }
 642                      }
 643
 644 #line 537 "rwgen.pcc"
 645                      } break;
 646                   default: {
 647                      L2:; } break;
 648                }
 649             } else { goto L2; }
 650             } break;
 651          default: { goto L2; } break;
 652       }
 653    } else { goto L2; }
 654 }
 655 #line 539 "rwgen.pcc"
 656 #line 539 "rwgen.pcc"
 657
 658 }
 659
 660 ///////////////////////////////////////////////////////////////////////////////
 661 //
 662 //  Method to generate a traversal routine for a set of terms in a datatype.
 663 //
 664 ///////////////////////////////////////////////////////////////////////////////
 665 void RewritingCompiler::gen_bottomup_traversals
 666    (FunctorMap& F, Functor f, int arity, Cons terms[], Ty ty)
 667 {  Bool is_boxed = terms[0]->ty != NOty; // are we dealing with boxed terms?
 668    //Id redex    = is_boxed ? redex_name(ty) : "(int)redex";
 669    //Id untagger = is_boxed ? "->tag__" : "";
 670    Exp redex = IDexp(
 671 #line 552 "rwgen.pcc"
 672 #line 552 "rwgen.pcc"
 673 _r_w_g_e_nco_c_c_Q1
 674 #line 552 "rwgen.pcc"
 675 #line 552 "rwgen.pcc"
 676 );
 677
 678    if (arity == 1)
 679    {  ////////////////////////////////////////////////////////////////////////
 680       //  (1 branch) No ifs or switches
 681       ////////////////////////////////////////////////////////////////////////
 682       gen_one_traversal(F, f, terms[0], ty);
 683    } else if (arity == 2)
 684    {  ////////////////////////////////////////////////////////////////////////
 685       //  (2 branches) Generate an if
 686       ////////////////////////////////////////////////////////////////////////
 687       pr("%^if (%e) {%+", untag_one(redex, terms[0]));
 688       gen_one_traversal(F, f + 1, terms[1], ty);
 689       pr("%-%^} else {%+");
 690       gen_one_traversal(F, f, terms[0], ty);
 691       pr("%-%^}");
 692    } else
 693    {  ////////////////////////////////////////////////////////////////////////
 694       // (n-branches) Generate a switch
 695       ////////////////////////////////////////////////////////////////////////
 696       pr("%^switch(%e) {%+",untag_one(redex,terms[0]));
 697       for (int i = 0; i < arity; i++)
 698       {  pr(i == arity - 1 ? "%^default: { %+" : "%^case %*: { %+",
 699             terms[i], false);
 700          gen_one_traversal(F, f+i, terms[i], ty);
 701          pr("} break;%-");
 702       }
 703       pr("%-%^}");
 704    }
 705 }
 706
 707 ///////////////////////////////////////////////////////////////////////////////
 708 //
 709 //  Method to generate a traversal routine for one term in a datatype.
 710 //
 711 ///////////////////////////////////////////////////////////////////////////////
 712 void RewritingCompiler::gen_one_traversal
 713   (FunctorMap& F, Functor f, Cons term, Ty ty)
 714 {  if (is_array_constructor(term->name))
 715    {  ////////////////////////////////////////////////////////////////////////
 716       // Generate array code
 717       ////////////////////////////////////////////////////////////////////////
 718       bug("RewritingCompiler::gen_one_traversal");
 719    } else
 720    {  gen_component_traversal(F, f, term, ty);
 721    }
 722 }
 723
 724 ///////////////////////////////////////////////////////////////////////////////
 725 //
 726 //  Method to generate code to traverse a component of a term.
 727 //
 728 ///////////////////////////////////////////////////////////////////////////////
 729 void RewritingCompiler::gen_component_traversal
 730    (FunctorMap& F, Functor f, Cons term, Ty ty)
 731 {  Ty  arg_ty = component_ty(ty, term);  // argument type of the term.
 732    int arity  = arity_of(arg_ty);        // arity of this type.
 733    Bool relevant[256];
 734    Bool is_record = false;
 735
 736    ///////////////////////////////////////////////////////////////////////////
 737    // Generate code for the state temporary variables.
 738    ///////////////////////////////////////////////////////////////////////////
 739    { for (int i = 0; i < arity; i++) pr ("%^int s%i__;", i); }
 740
 741    ///////////////////////////////////////////////////////////////////////////
 742    // Optimize out singleton.
 743    ///////////////////////////////////////////////////////////////////////////
 744    Bool is_singleton = true;
 745    //{ for (int i = 0; i < arity; i++)
 746    { for (int i = 0; i < F.G.arity(f); i++)
 747         if (F.tree_gen->index_range(f,i) > 1) is_singleton = false;
 748    }
 749
 750    ///////////////////////////////////////////////////////////////////////////
 751    // Call the constructor if it is applicative
 752    ///////////////////////////////////////////////////////////////////////////
 753    if (F.is_applicative) pr ("%^redex = %S%+", term->name);
 754    if (F.is_applicative && term->ty != NOty) pr("(\n");
 755
 756    ///////////////////////////////////////////////////////////////////////////
 757    // Generate code to call the labeler on subcomponents.
 758    ///////////////////////////////////////////////////////////////////////////
 759
 760 #line 635 "rwgen.pcc"
 761 #line 643 "rwgen.pcc"
 762 {
 763    if (arg_ty) {
 764       switch (arg_ty->tag__) {
 765          case a_Ty::tag_TYCONty: {
 766             if (boxed(((Ty_TYCONty *)arg_ty)->_1)) {
 767                switch (((Ty_TYCONty *)arg_ty)->_1->tag__) {
 768                   case a_TyCon::tag_RECORDtycon: {
 769 #line 640 "rwgen.pcc"
 770                     gen_record_component_traversal(F,term,arity,relevant,((TyCon_RECORDtycon *)((Ty_TYCONty *)arg_ty)->_1)->_1,((Ty_TYCONty *)arg_ty)->_2);
 771                      is_record = true;
 772
 773 #line 642 "rwgen.pcc"
 774                      } break;
 775                   default: {
 776                      L3:;
 777 #line 643 "rwgen.pcc"
 778                     gen_single_component_traversal(F,term,arg_ty);
 779 #line 643 "rwgen.pcc"
 780                      } break;
 781                }
 782             } else {
 783                switch ((int)((Ty_TYCONty *)arg_ty)->_1) {
 784                   case ((int)TUPLEtycon): {
 785 #line 638 "rwgen.pcc"
 786                     gen_tuple_component_traversal(F,term,arity,((Ty_TYCONty *)arg_ty)->_2);
 787 #line 638 "rwgen.pcc"
 788                      } break;
 789                   default: { goto L3; } break;
 790                }
 791             }
 792             } break;
 793          default: { goto L3; } break;
 794       }
 795    } else {}
 796 }
 797 #line 644 "rwgen.pcc"
 798 #line 644 "rwgen.pcc"
 799
 800
 801    if (F.is_applicative && term->ty != NOty) pr("%^)");
 802    if (F.is_applicative) pr(";\n%-");
 803
 804    ///////////////////////////////////////////////////////////////////////////
 805    // Generate code to compute the new state
 806    ///////////////////////////////////////////////////////////////////////////
 807    if (F.tree_gen->arity_of(f) == 0 && arg_ty != NOty) pr("%?s__ = 0;");
 808    else if (is_singleton) pr("%?s__ = %i;", F.tree_gen->go(f));
 809    else // theta code
 810    {  pr ("%^s__ = %s_theta_%i", F.class_name, f);
 811       for (int i = 0, j = 0; i < arity; i++)
 812       {  if (is_record && ! relevant[i]) continue;
 813          if (F.tree_gen->index_range(f,i) == 1) pr("[0]");
 814          else if (F.use_compression)
 815             pr("[%s_check[%i + s%i__] == %i ? %s_next[%i + s%i__] : 0]",
 816                F.class_name, F.tree_gen->compressed_offset(f,j), j,
 817                F.tree_gen->compressed_index(f,j),
 818                F.class_name, F.tree_gen->compressed_offset(f,j), j);
 819          else
 820             pr("[%s_mu_%i_%i[s%i__]]", F.class_name, f, j, j);
 821          j++;
 822       }
 823       pr("; ");
 824    }
 825 }
 826
 827 ///////////////////////////////////////////////////////////////////////////////
 828 //
 829 //  Method to generate traversal code on one single component of a datatype
 830 //
 831 ///////////////////////////////////////////////////////////////////////////////
 832 void RewritingCompiler::gen_single_component_traversal
 833   (FunctorMap& F, Cons term, Ty arg_ty)
 834 {  Exp e = select(IDexp("redex"),term);
 835    if (is_array_constructor(term->name))
 836    {  if (F.is_known_type(arg_ty)) // generate traversal code for vectors
 837       {  if (F.is_applicative)
 838          { bug("RewritingCompiler::gen_single_component_traversal");
 839          } else
 840          { bug("RewritingCompiler::gen_single_component_traversal");
 841          }
 842       } else                       // type is unknown.
 843       {  if (F.is_applicative)
 844          { bug("RewritingCompiler::gen_single_component_traversal");
 845          } else
 846          {  pr("%^s0__ = 0; // %T", arg_ty); }
 847       }
 848    } else
 849    {  if (F.is_known_type(arg_ty))
 850       {  pr("%^labeler(%e, s0__, r__)%s\n", e, (F.is_applicative ? "" : ";")); }
 851       else if (F.is_applicative)
 852       {  pr("%^(s0__ = 0, %e) // %T\n", e, arg_ty); }
 853       else
 854       {  pr("%^s0__ = 0; // %T\n", arg_ty); }
 855    }
 856 }
 857
 858 ///////////////////////////////////////////////////////////////////////////////
 859 //
 860 //  Method to generate traversal code on the tuple component of a datatype
 861 //
 862 ///////////////////////////////////////////////////////////////////////////////
 863 void RewritingCompiler::gen_tuple_component_traversal
 864   (FunctorMap& F, Cons term, int arity, Tys tys)
 865 {  Tys ts; int i;
 866    Exp e = select(IDexp("redex"),term);
 867    for (i = 0, ts = tys; i < arity && ts; i++, ts = ts->_2)
 868    {  Ty ty   = ts->_1;
 869       Id mark = F.is_applicative ? (i != arity - 1 ? "," : "") : ";";
 870       Exp  e_i  = DOTexp(e,index_of(i+1));
 871       if (F.is_known_type(ty))
 872          pr("%^labeler(%e, s%i__, r__)%s\n", e_i, i, mark);
 873       else if (F.is_applicative)
 874          pr("%^(s%i__ = 0, %e)%s // %T\n", i, e_i, mark, ty);
 875       else
 876          pr("%^s%i__ = 0; // %T\n", i, ty);
 877    }
 878 }
 879
 880 ///////////////////////////////////////////////////////////////////////////////
 881 //
 882 //  Method to generate traversal code on the record component of a datatype
 883 //
 884 ///////////////////////////////////////////////////////////////////////////////
 885 void RewritingCompiler::gen_record_component_traversal
 886    (FunctorMap& F, Cons term, int arity, Bool relevant[], Ids labs, Tys tys)
 887 {  Tys ts; Ids ids; int i;
 888    Exp e = select(IDexp("redex"),term);
 889    for (ids = labs, ts = tys, i = 0; ids && ts; ids=ids->_2, ts=ts->_2, i++)
 890    {  Ty   ty   = ts->_1;
 891       Exp  e_i  = DOTexp(e,ids->_1);
 892       Id   mark = F.is_applicative ? (i != arity - 1 ? "," : "") : ";";
 893       if (F.is_known_type(ty))
 894       {  relevant[i] = true;
 895          pr("%^labeler(%e,s%i__,r__)%s\n", e_i, i, mark);
 896       } else if (F.is_applicative)
 897       {  relevant[i] = false;
 898          pr("%^(s%i__ = 0, %e)%s // %T\n",i, e_i, mark, ty);
 899       } else
 900       {  relevant[i] = false;
 901          pr("%^s%i__ = 0; // %T\n",i,ty);
 902       }
 903    }
 904 }
 905
 906 ///////////////////////////////////////////////////////////////////////////////
 907 //
 908 //  Method to generate the action code for a datatype
 909 //
 910 ///////////////////////////////////////////////////////////////////////////////
 911 void RewritingCompiler::gen_action (FunctorMap& F, Ty ty)
 912 {  HashTable::Entry * e = F.rule_map.lookup(ty);
 913    if (e == 0) return; // no rules, no action
 914
 915    ////////////////////////////////////////////////////////////////////////////
 916    // The set of rules on type 'ty.'
 917    ////////////////////////////////////////////////////////////////////////////
 918    MatchRules rules = MatchRules(F.rule_map.value(e));
 919
 920    ////////////////////////////////////////////////////////////////////////////
 921    // Check whether this set of rules have guards and costs and cost exprs.
 922    ////////////////////////////////////////////////////////////////////////////
 923    Bool has_conditional_rules = false;
 924    Bool has_cost              = false;
 925    Bool has_cost_exp          = false;
 926    {  for_each(MatchRule, r, rules)
 927       {
 928 #line 772 "rwgen.pcc"
 929 #line 781 "rwgen.pcc"
 930 {
 931 #line 774 "rwgen.pcc"
 932  if (r->_3 != NOexp || (r->option & MatchRuleInfo::FAILREWRITE))
 933    has_conditional_rules = true;
 934
 935 #line 776 "rwgen.pcc"
 936 #line 779 "rwgen.pcc"
 937    {
 938       Cost _V3 = r->_4;
 939       if (_V3) {
 940          if (untagp(_V3)) {
 941
 942 #line 778 "rwgen.pcc"
 943            has_cost = true;
 944 #line 778 "rwgen.pcc"
 945          } else {
 946
 947 #line 779 "rwgen.pcc"
 948            has_cost_exp = true;
 949 #line 779 "rwgen.pcc"
 950          }
 951       } else {}
 952    }
 953 #line 780 "rwgen.pcc"
 954 #line 780 "rwgen.pcc"
 955
 956
 957 #line 781 "rwgen.pcc"
 958 }
 959 #line 782 "rwgen.pcc"
 960 #line 782 "rwgen.pcc"
 961
 962       }
 963    }
 964
 965    ////////////////////////////////////////////////////////////////////////////
 966    //  Generate a rule variable if we have to deal with cost functions
 967    //  and/or annotate the tree for reducers.
 968    ////////////////////////////////////////////////////////////////////////////
 969    // if (has_cost_exp || F.gen_reducers) pr ("%^Rule r__ = -1;");
 970
 971    ////////////////////////////////////////////////////////////////////////////
 972    //
 973    //  Split into subcases
 974    //
 975    ////////////////////////////////////////////////////////////////////////////
 976    if (F.gen_reducers)
 977    {  if (F.has_cost_exp)
 978          gen_cost_labeler_action(F,ty,rules,has_conditional_rules);
 979       else
 980          if (has_conditional_rules)
 981             gen_costless_guarded_labeler_action(F,rules);
 982          else
 983             gen_costless_guardless_labeler_action(F,rules);
 984    } else
 985    {  if (F.has_cost_exp)
 986          gen_cost_rewriter_action(F,rules);
 987       else
 988          if (has_conditional_rules)
 989             gen_costless_guarded_rewriter_action(F,rules);
 990          else
 991             gen_costless_guardless_rewriter_action(F,rules);
 992    }
 993 }
 994
 995 ///////////////////////////////////////////////////////////////////////////////
 996 //
 997 //  Generate the action for a cost minimizing labeler.
 998 //
 999 ///////////////////////////////////////////////////////////////////////////////
1000 void RewritingCompiler::gen_cost_labeler_action
1001    (FunctorMap& F, Ty ty, MatchRules rules, Bool has_guard)
1002 {
1003    bug("RewritingCompiler::gen_cost_labeler_action");
1004 }
1005
1006 ///////////////////////////////////////////////////////////////////////////////
1007 //
1008 //  Generate the action for a simple labeler with guards.
1009 //
1010 ///////////////////////////////////////////////////////////////////////////////
1011 void RewritingCompiler::gen_costless_guarded_labeler_action
1012    (FunctorMap& F, MatchRules rules)
1013 {
1014    ////////////////////////////////////////////////////////////////////////////
1015    // Generate code to perform the mapping from state to the accept rule.
1016    ////////////////////////////////////////////////////////////////////////////
1017    pr("%^const %s* o__ = %s_accept_vector + %s_accept_base[s__];"
1018       "%-%^accept__:%+"
1019       "%^switch (*o__) {%+",
1020        F.tree_gen->get_rule_type(), F.class_name, F.class_name
1021      );
1022    for_each (MatchRule, r, rules)
1023    {
1024 #line 844 "rwgen.pcc"
1025 #line 850 "rwgen.pcc"
1026 {
1027 #line 846 "rwgen.pcc"
1028  if (r->_3 != NOexp)
1029    {  pr ("%^case %i: if (! (%e)) { ++o__; goto accept__; }",
1030           r->rule_number, r->_3);
1031    }
1032
1033 #line 850 "rwgen.pcc"
1034 }
1035 #line 851 "rwgen.pcc"
1036 #line 851 "rwgen.pcc"
1037
1038    }
1039    pr("%-%^}"
1040       "%^%srule__ = *o__;", F.tree_gen->get_rule_type());
1041 }
1042
1043 ///////////////////////////////////////////////////////////////////////////////
1044 //
1045 //  Generate the action for a simple labeler without guards.
1046 //
1047 ///////////////////////////////////////////////////////////////////////////////
1048 void RewritingCompiler::gen_costless_guardless_labeler_action
1049    (FunctorMap& F, MatchRules rules)
1050 {
1051    ////////////////////////////////////////////////////////////////////////////
1052    // Generate code to perform the mapping from state to the first accept rule.
1053    ////////////////////////////////////////////////////////////////////////////
1054    pr("%^%srule__ = %s_accept1[s__];",
1055       F.tree_gen->get_rule_type(), F.class_name);
1056 }
1057
1058 ///////////////////////////////////////////////////////////////////////////////
1059 //
1060 //  Generate the action for a cost minimizing rewriter.
1061 //
1062 ///////////////////////////////////////////////////////////////////////////////
1063 void RewritingCompiler::gen_cost_rewriter_action
1064    (FunctorMap& F, MatchRules rules)
1065 {
1066    ////////////////////////////////////////////////////////////////////////////
1067    // Generate code to perform the mapping from state to set of accept rule.
1068    ////////////////////////////////////////////////////////////////////////////
1069    pr("%^const %s* o__ = %s_accept_vector + %s_accept_base[s__];"
1070       "%^TreeTables::Rule rule__ = -1;"
1071       "%^TreeTables::Cost min_cost__  = TreeTables::infinite_cost;"
1072       "%^TreeTables::Cost temp_cost__;",
1073       F.tree_gen->get_rule_type(), F.class_name, F.class_name
1074      );
1075
1076    ////////////////////////////////////////////////////////////////////////////
1077    //
1078    // Generate the cost minimalization code for each accept rule.
1079    //
1080    ////////////////////////////////////////////////////////////////////////////
1081    pr ("%^for ( ;*o__ >= 0; o__++) {%+"
1082           "%^switch (*o__) {%+"
1083       );
1084
1085    {  for_each (MatchRule, r, rules)
1086       {
1087 #line 900 "rwgen.pcc"
1088 #line 918 "rwgen.pcc"
1089 {
1090 #line 902 "rwgen.pcc"
1091  pr("%^case %i: %+",r->rule_number);
1092    if (r->_3 != NOexp) pr ("%^if (%e)%+", r->_3);
1093
1094 #line 904 "rwgen.pcc"
1095 #line 914 "rwgen.pcc"
1096    {
1097       Cost _V4 = r->_4;
1098       if (_V4) {
1099          if (untagp(_V4)) {
1100
1101 #line 908 "rwgen.pcc"
1102            pr ("%^if (min_cost__ > %i) { min_cost__ = %i; rule__ = %i; }",
1103             ((Cost_INTcost *)derefp(_V4))->INTcost, ((Cost_INTcost *)derefp(_V4))->INTcost, r->rule_number);
1104
1105 #line 910 "rwgen.pcc"
1106          } else {
1107
1108 #line 912 "rwgen.pcc"
1109            pr ("%^if (min_cost__ > (temp_cost__ = %e)) { min_cost__ = temp_cost__; rule__ = %i; }",
1110             ((Cost_EXPcost *)_V4)->_1, r->rule_number);
1111
1112 #line 914 "rwgen.pcc"
1113          }
1114       } else {
1115 #line 906 "rwgen.pcc"
1116         pr ("%^{ rule__ = %i; goto found__; }", r->rule_number);
1117 #line 906 "rwgen.pcc"
1118       }
1119    }
1120 #line 915 "rwgen.pcc"
1121 #line 915 "rwgen.pcc"
1122
1123    if (r->_3 != NOexp) pr ("%-");
1124    pr ("%- break; ");
1125
1126 #line 918 "rwgen.pcc"
1127 }
1128 #line 919 "rwgen.pcc"
1129 #line 919 "rwgen.pcc"
1130
1131       }
1132    }
1133    pr ("%-%^}"
1134        "%-%^}"
1135        "%^found__: ;\n\n"
1136       );
1137
1138    ////////////////////////////////////////////////////////////////////////////
1139    //
1140    // Now generate the action code
1141    //
1142    ////////////////////////////////////////////////////////////////////////////
1143    pr("%^switch (rule__) {%+");
1144    {  for_each (MatchRule, r, rules)
1145       {
1146 #line 934 "rwgen.pcc"
1147 #line 938 "rwgen.pcc"
1148 {
1149 #line 936 "rwgen.pcc"
1150  MarkCurrentRule mark(current_rule,r);
1151                pr("%^case %i: %+{%&}%- break;", r->rule_number, r->_5);
1152
1153 #line 938 "rwgen.pcc"
1154 }
1155 #line 939 "rwgen.pcc"
1156 #line 939 "rwgen.pcc"
1157
1158       }
1159    }
1160    pr("%-%^}\n\n");
1161 }
1162
1163 ///////////////////////////////////////////////////////////////////////////////
1164 //
1165 //  Generate the action for a simple rewriter.
1166 //
1167 ///////////////////////////////////////////////////////////////////////////////
1168 void RewritingCompiler::gen_costless_guarded_rewriter_action
1169    (FunctorMap& F, MatchRules rules)
1170 {
1171    ////////////////////////////////////////////////////////////////////////////
1172    // Generate code to perform the mapping from state to accept rule.
1173    ////////////////////////////////////////////////////////////////////////////
1174    pr("%^const %s* o__ = %s_accept_vector + %s_accept_base[s__];"
1175       "%-%^accept__:%+"
1176       "%^switch (*o__) {%+",
1177        F.tree_gen->get_rule_type(), F.class_name, F.class_name);
1178    for_each (MatchRule, r, rules)
1179    {
1180 #line 961 "rwgen.pcc"
1181 #line 969 "rwgen.pcc"
1182 {
1183 #line 963 "rwgen.pcc"
1184  pr("%^case %i: ", r->rule_number);
1185    if (r->_3 != NOexp) pr ("if (%e)%^", r->_3);
1186    MarkCurrentRule mark(current_rule,r);
1187    pr("%+{%&}%-", r->_5);
1188    if (r->_3 != NOexp) pr ("%^else { ++o__; goto accept__; }");
1189    pr(" break;");
1190
1191 #line 969 "rwgen.pcc"
1192 }
1193 #line 970 "rwgen.pcc"
1194 #line 970 "rwgen.pcc"
1195
1196    }
1197    pr("%-%^}");
1198 }
1199
1200 ///////////////////////////////////////////////////////////////////////////////
1201 //
1202 //  Generate the action for a simple rewriter.
1203 //
1204 ///////////////////////////////////////////////////////////////////////////////
1205 void RewritingCompiler::gen_costless_guardless_rewriter_action
1206    (FunctorMap& F, MatchRules rules)
1207 {
1208    ////////////////////////////////////////////////////////////////////////////
1209    // Generate code with cases corresponding to the accept state directly.
1210    ////////////////////////////////////////////////////////////////////////////
1211    pr("%^switch (s__) {%+");
1212    for_each (MatchRule, r, rules)
1213    {
1214 #line 988 "rwgen.pcc"
1215 #line 997 "rwgen.pcc"
1216 {
1217 #line 990 "rwgen.pcc"
1218  Bool used = false;
1219    for (int s = F.tree_gen->number_of_states() - 1; s >= 0; s--)
1220    {  if (F.tree_gen->accept1_rule(s) == r->rule_number)
1221       {  pr ("%^case %i: ", s); used = true; }
1222    }
1223    MarkCurrentRule mark(current_rule,r);
1224    if (used) pr ("%+{%&}%- break;", r->_5);
1225
1226 #line 997 "rwgen.pcc"
1227 }
1228 #line 998 "rwgen.pcc"
1229 #line 998 "rwgen.pcc"
1230
1231    }
1232    pr("%-%^}");
1233 }
1234
1235 ///////////////////////////////////////////////////////////////////////////////
1236 //
1237 //  Method to generate the reducers.  Reducers take an rewrite
1238 //  tree annotated with the accept rule(s) and traverse it perform
1239 //  the reduction actions.
1240 //
1241 ///////////////////////////////////////////////////////////////////////////////
1242 void RewritingCompiler::generate_reducers(FunctorMap& F)
1243 {  ///////////////////////////////////////////////////////////////////////////
1244    // Generate reducers for all datatypes
1245    ///////////////////////////////////////////////////////////////////////////
1246    foreach_entry (e, F.type_map)
1247    {  Ty ty = Ty(F.type_map.key(e));
1248       debug_msg("[Rewrite class %s: generating reducer for datatype %T\n",
1249                 F.class_name, ty);
1250       gen_datatype_reducer(F, ty);
1251    }
1252 }
1253
1254 ///////////////////////////////////////////////////////////////////////////////
1255 //
1256 //  Method to generate the datatype reducer.
1257 //
1258 ///////////////////////////////////////////////////////////////////////////////
1259 void RewritingCompiler::gen_datatype_reducer(FunctorMap& F, Ty ty)
1260 {  HashTable::Entry * e = F.rule_map.lookup(ty);
1261    if (e == 0) return; // we have no rules for this type. Do nothing
1262
1263    MatchRules rules  = MatchRules(F.rule_map.value(e)); // The set of rules
1264    Functor    f      = F.type_map[ty];         // The starting functor encoding
1265    Protocol   proto  = Protocol(F.protocols[ty]); // The protocol for this type
1266
1267    ///////////////////////////////////////////////////////////////////////////
1268    // The synthesized attribute type.
1269    ///////////////////////////////////////////////////////////////////////////
1270    Ty         syn_ty = proto->syn == NOty ? void_ty : proto->syn;
1271    Ty         inh_ty = proto->inh;
1272
1273    ///////////////////////////////////////////////////////////////////////////
1274    // Generate the protocol of this reducer (4 cases to worry about)
1275    ///////////////////////////////////////////////////////////////////////////
1276    if (syn_ty == void_ty && inh_ty == NOty)
1277       pr ("%^void %s::reduce(%t,int lhs)", F.class_name, ty, "redex");
1278    if (syn_ty == void_ty && inh_ty != NOty)
1279       pr ("%^void %s::reduce(%t, %t,int lhs)", F.class_name, ty, "redex",
1280           inh_ty, "inh__");
1281    if (syn_ty != void_ty && inh_ty == NOty)
1282       pr ("%^%t %s::reduce(%t,int lhs)", syn_ty, "", F.class_name, ty, "redex");
1283    if (syn_ty != void_ty && inh_ty != NOty)
1284       pr ("%^%t %s::reduce(%t,%t,int lhs)", syn_ty, "", F.class_name, ty, "redex",
1285           inh_ty, "inh__");
1286
1287    pr ("%^{%+");
1288
1289    ///////////////////////////////////////////////////////////////////////////
1290    // Generate a temporary called "__" for the synthesized attribute.
1291    // Also assigns redex to it if it is the same type.
1292    ///////////////////////////////////////////////////////////////////////////
1293    if (syn_ty != void_ty)
1294        pr ("%^%t%s;",syn_ty,"__",
1295            ty_equal(syn_ty,ty) ? " = redex" : "");
1296
1297    ///////////////////////////////////////////////////////////////////////////
1298    // Generate the code that computes the accept rule
1299    ///////////////////////////////////////////////////////////////////////////
1300    if (F.dynamic_search)
1301    {  pr ("%^const %s_StateRec * _state_rec = (const %s_StateRec *)(%s->get_state_rec());"
1302           "%^int r__;"
1303           "%^switch (lhs) {%+",
1304           F.class_name, F.class_name, redex_name(ty)
1305          );
1306       foreach_entry (p,F.var_map)
1307       {  Id  lhs        = Id(p->k);
1308          int nonterm_no = int(p->v);
1309          pr ("%^case %i: r__ = %s_%S_accept[_state_rec->rule._%S]; break;",
1310              nonterm_no, F.class_name, lhs, lhs);
1311       }
1312       pr ("%^default: r__ = -1; break;%-"
1313           "%^}");
1314    }
1315    else
1316    {
1317 #line 1084 "rwgen.pcc"
1318 #line 1123 "rwgen.pcc"
1319 {
1320    Ty _V5 = deref_all(ty);
1321    if (_V5) {
1322       switch (_V5->tag__) {
1323          case a_Ty::tag_TYCONty: {
1324             if (boxed(((Ty_TYCONty *)_V5)->_1)) {
1325                switch (((Ty_TYCONty *)_V5)->_1->tag__) {
1326                   case a_TyCon::tag_DATATYPEtycon: {
1327 #line 1086 "rwgen.pcc"
1328                    Id var        = redex_name(ty);
1329                      Id table_name = 0;
1330
1331                      // generate mapping from unit tag to accept rule if necessary.
1332                      if (((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V5)->_1)->unit > 1)
1333                      {  table_name = vars.new_label();
1334                         pr("%^static const %s%s[] = { ",
1335                                   F.tree_gen->get_rule_type(), table_name);
1336                         for (int i = 0; i < ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V5)->_1)->unit; i++)
1337                         {  pr ("%i", F.tree_gen->accept1_rule(F.tree_gen->go(f+i)));
1338                            if (i != ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V5)->_1)->unit - 1) pr(", ");
1339                         }
1340                         pr (" };");
1341                      }
1342
1343                      // Generate code that computes the accept rule(try to optimize a bit).
1344                      if (((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V5)->_1)->unit == 0)       // all boxed
1345                      {  // pr ("%^int r__ = %s->get_rewrite_rule();",var);
1346                         pr ("%^int r__ = ");
1347                         gen_get_rewrite_rule(ty,var);
1348                         pr (";");
1349                      } else if (((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V5)->_1)->arg == 0)   // all unboxed
1350                      {         pr ("%^int r__ = %s[redex]",table_name);
1351                      } else if (((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V5)->_1)->unit == 1)  // one is unboxed
1352                      {  // pr ("%^int r__ = redex ? %s->get_rewrite_rule() : %i;",var,
1353                         //     F.tree_gen->accept1_rule(F.tree_gen->go(f)));
1354                         pr ("%^int r__ = redex ? ");
1355                         gen_get_rewrite_rule(ty,var);
1356                         pr (" : %i;",F.tree_gen->accept1_rule(F.tree_gen->go(f)));
1357                      } else
1358                      {  // pr ("%^int r__ = boxed(redex) ? %s->get_rewrite_rule() : %s[(int)redex];",
1359                         //     var, table_name);
1360                         pr ("%^int r__ = boxed(redex) ? ");
1361                         gen_get_rewrite_rule(ty,var);
1362                         pr (" : %s[(int)redex];", table_name);
1363                      }
1364
1365 #line 1122 "rwgen.pcc"
1366                      } break;
1367                   default: {
1368                      L4:;
1369 #line 1123 "rwgen.pcc"
1370                     bug("RewritingCompiler::gen_datatype_labeler");
1371 #line 1123 "rwgen.pcc"
1372                      } break;
1373                }
1374             } else { goto L4; }
1375             } break;
1376          default: { goto L4; } break;
1377       }
1378    } else { goto L4; }
1379 }
1380 #line 1124 "rwgen.pcc"
1381 #line 1124 "rwgen.pcc"
1382
1383    }
1384
1385    ///////////////////////////////////////////////////////////////////////////
1386    // Generate the switch statement, one for each rule
1387    ///////////////////////////////////////////////////////////////////////////
1388    pr ("%^switch (r__) {%+");
1389    for_each(MatchRule, r, rules)
1390    {
1391 #line 1132 "rwgen.pcc"
1392 #line 1138 "rwgen.pcc"
1393 {
1394 #line 1134 "rwgen.pcc"
1395   pr ("%^case %i: {%+ // %p\n", r->rule_number, r->_2);
1396    gen_pattern_traversal(F, r->_1, r->_2, 0);
1397    MarkCurrentRule mark(current_rule,r);
1398    pr ("%^%&} break;%-", r->_5);
1399
1400 #line 1138 "rwgen.pcc"
1401 }
1402 #line 1139 "rwgen.pcc"
1403 #line 1139 "rwgen.pcc"
1404
1405    }
1406    pr ("%-%^}");
1407
1408    ///////////////////////////////////////////////////////////////////////////
1409    // Return the value of the synthesized attribute (if any)
1410    ///////////////////////////////////////////////////////////////////////////
1411    if (syn_ty != void_ty) pr("%^return __; ");
1412
1413    ///////////////////////////////////////////////////////////////////////////
1414    // End of routine
1415    ///////////////////////////////////////////////////////////////////////////
1416    pr ("%-%^}\n\n");
1417 }
1418
1419 ///////////////////////////////////////////////////////////////////////////////
1420 //
1421 //  Method to generate a reducer recursive call for one pattern.
1422 //
1423 ///////////////////////////////////////////////////////////////////////////////
1424 int RewritingCompiler::gen_pattern_traversal(FunctorMap& F, Id lhs, Pat pat, int i)
1425 {
1426 #line 1160 "rwgen.pcc"
1427 #line 1198 "rwgen.pcc"
1428 {
1429    if (pat) {
1430       switch (pat->tag__) {
1431          case a_Pat::tag_APPpat: {
1432 #line 1167 "rwgen.pcc"
1433            i = gen_pattern_traversal(F,lhs,((Pat_APPpat *)pat)->_2,i);
1434 #line 1167 "rwgen.pcc"
1435             } break;
1436          case a_Pat::tag_TYPEDpat: {
1437 #line 1164 "rwgen.pcc"
1438            i = gen_pattern_traversal(F,lhs,((Pat_TYPEDpat *)pat)->_1,i);
1439 #line 1164 "rwgen.pcc"
1440             } break;
1441          case a_Pat::tag_ASpat: {
1442 #line 1163 "rwgen.pcc"
1443            i = gen_pattern_traversal(F,lhs,((Pat_ASpat *)pat)->_2,i);
1444 #line 1163 "rwgen.pcc"
1445             } break;
1446          case a_Pat::tag_ARRAYpat: {
1447 #line 1168 "rwgen.pcc"
1448            i = gen_pattern_traversal(F,lhs,((Pat_ARRAYpat *)pat)->_1,i);
1449 #line 1168 "rwgen.pcc"
1450             } break;
1451          case a_Pat::tag_TUPLEpat: {
1452 #line 1169 "rwgen.pcc"
1453            i = gen_pattern_traversal(F,lhs,((Pat_TUPLEpat *)pat)->TUPLEpat,i);
1454 #line 1169 "rwgen.pcc"
1455             } break;
1456          case a_Pat::tag_EXTUPLEpat: {
1457 #line 1170 "rwgen.pcc"
1458            i = gen_pattern_traversal(F,lhs,((Pat_EXTUPLEpat *)pat)->EXTUPLEpat,i);
1459 #line 1170 "rwgen.pcc"
1460             } break;
1461          case a_Pat::tag_RECORDpat: {
1462 #line 1171 "rwgen.pcc"
1463            i = gen_pattern_traversal(F,lhs,((Pat_RECORDpat *)pat)->_1,i);
1464 #line 1171 "rwgen.pcc"
1465             } break;
1466          case a_Pat::tag_LISTpat: {
1467 #line 1173 "rwgen.pcc"
1468            i = gen_pattern_traversal(F,lhs,((Pat_LISTpat *)pat)->head,i);
1469             i = gen_pattern_traversal(F,lhs,((Pat_LISTpat *)pat)->tail,i);
1470
1471 #line 1175 "rwgen.pcc"
1472             } break;
1473          case a_Pat::tag_VECTORpat: {
1474 #line 1177 "rwgen.pcc"
1475            i = gen_pattern_traversal(F,lhs,((Pat_VECTORpat *)pat)->elements,i);
1476             i = gen_pattern_traversal(F,lhs,((Pat_VECTORpat *)pat)->array,i);
1477             i = gen_pattern_traversal(F,lhs,((Pat_VECTORpat *)pat)->len,i);
1478
1479 #line 1180 "rwgen.pcc"
1480             } break;
1481          case a_Pat::tag_GUARDpat: {
1482 #line 1166 "rwgen.pcc"
1483            i = gen_pattern_traversal(F,lhs,((Pat_GUARDpat *)pat)->_1,i);
1484 #line 1166 "rwgen.pcc"
1485             } break;
1486          case a_Pat::tag_MARKEDpat: {
1487 #line 1165 "rwgen.pcc"
1488            i = gen_pattern_traversal(F,lhs,((Pat_MARKEDpat *)pat)->_2,i);
1489 #line 1165 "rwgen.pcc"
1490             } break;
1491          case a_Pat::tag_WILDpat:
1492          case a_Pat::tag_IDpat: {
1493 #line 1182 "rwgen.pcc"
1494           if (F.is_rewritable_type(pat->ty))
1495             {  Protocol proto = Protocol(F.protocols[pat->ty]);
1496                Ty inh_ty = proto->inh, syn_ty = proto->syn;
1497                Id inh_exp = inh_ty != NOty ? ",inh__" : "";
1498                int nonterm_no = (lhs && F.var_map.contains(lhs))
1499                     ? int(F.var_map[lhs]) : 0;
1500                Id nonterm = lhs ? lhs : "(none)";
1501                if (syn_ty != NOty)
1502                   pr("%^%t _%i__ = reduce(%e%s,%i); // %s",
1503                       syn_ty,"",i,pat->selector,inh_exp,nonterm_no,nonterm);
1504                else
1505                   pr("%^reduce(%e%s,%i); // %s",
1506                      pat->selector,inh_exp,nonterm_no,nonterm);
1507                i++;
1508             }
1509
1510 #line 1197 "rwgen.pcc"
1511             } break;
1512          case a_Pat::tag_CONSpat:
1513          case a_Pat::tag_LITERALpat:
1514          case a_Pat::tag_CONTEXTpat:
1515          case a_Pat::tag_LEXEMEpat: {
1516             L5:; } break;
1517          default: {
1518 #line 1198 "rwgen.pcc"
1519            bug("RewritingCompiler::gen_pattern_traversal on %p\n",pat);
1520 #line 1198 "rwgen.pcc"
1521             } break;
1522       }
1523    } else { goto L5; }
1524 }
1525 #line 1199 "rwgen.pcc"
1526 #line 1199 "rwgen.pcc"
1527
1528    return i;
1529 }
1530
1531 ///////////////////////////////////////////////////////////////////////////////
1532 //
1533 //  Method to generate a reducer recursive call for one pattern list.
1534 //
1535 ///////////////////////////////////////////////////////////////////////////////
1536 int RewritingCompiler::gen_pattern_traversal(FunctorMap& F, Id lhs, Pats pats, int i)
1537 {  for_each (Pat, p, pats) i = gen_pattern_traversal(F,lhs,p,i);
1538    return i;
1539 }
1540
1541 ///////////////////////////////////////////////////////////////////////////////
1542 //
1543 //  Method to generate a reducer recursive call for one labeled pattern list.
1544 //
1545 ///////////////////////////////////////////////////////////////////////////////
1546 int RewritingCompiler::gen_pattern_traversal(FunctorMap& F, Id lhs, LabPats ps, int i)
1547 {  for_each (LabPat, p, ps) i = gen_pattern_traversal(F,lhs,p.pat,i);
1548    return i;
1549 }
1550 #line 1222 "rwgen.pcc"
1551 /*
1552 ------------------------------- Statistics -------------------------------
1553 Merge matching rules         = yes
1554 Number of DFA nodes merged   = 101
1555 Number of ifs generated      = 14
1556 Number of switches generated = 10
1557 Number of labels             = 5
1558 Number of gotos              = 13
1559 Adaptive matching            = enabled
1560 Fast string matching         = disabled
1561 Inline downcasts             = enabled
1562 --------------------------------------------------------------------------
1563 */