prop-src/matchgen.pcc

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  This file implements the backend for pattern matching,
   4 //  string matching, and lexical scanning constructs.  C++ code is
   5 //  emitted in this file.
   6 //
   7 ///////////////////////////////////////////////////////////////////////////////
   8
   9 #include <limits.h>
  10 #include <iostream>
  11 #include <strstream.h>
  12 #include <AD/contain/bitset.h>
  13 #include <AD/automata/lexergen.h>
  14 #include <AD/strings/charesc.h>
  15 #include <AD/memory/mempool.h>
  16 #include <AD/sort/heapsort.h>
  17 #include <AD/sort/heapsrt2.h>
  18 #include "ir.ph"
  19 #include "ast.ph"
  20 #include "matchcom.ph"
  21 #include "type.h"
  22 #include "labelgen.h"
  23 #include "hashtab.h"
  24 #include "config.h"
  25 #include "options.h"
  26 #include "list.h"
  27
  28 ///////////////////////////////////////////////////////////////////////////////
  29 //
  30 //  Class to mark the current rule.
  31 //
  32 ///////////////////////////////////////////////////////////////////////////////
  33 MarkCurrentRule::MarkCurrentRule(MatchRule& c, MatchRule n)
  34    : current_rule(c), old_rule(c) { c = n; }
  35 MarkCurrentRule::~MarkCurrentRule() { current_rule = old_rule; }
  36
  37 ///////////////////////////////////////////////////////////////////////////////
  38 //
  39 //  Method to extract the line number of the current rule
  40 //
  41 ///////////////////////////////////////////////////////////////////////////////
  42 int MatchCompiler::current_rule_line() const
  43 {  if (current_rule == 0) bug("MatchCompiler::current_rule_line()\n");
  44    return current_rule->begin_line;
  45 }
  46
  47 ///////////////////////////////////////////////////////////////////////////////
  48 //
  49 //  Method to extract the text of the current rule
  50 //
  51 ///////////////////////////////////////////////////////////////////////////////
  52 const char * MatchCompiler::current_rule_text() const
  53 {  if (current_rule == 0) bug("MatchCompiler::current_rule_text()\n");
  54    char buffer[4096];
  55    ostrstream stream(buffer,sizeof(buffer));
  56    std::ostream& s = stream;
  57    s << current_rule << ends;
  58    buffer[sizeof(buffer)-1] = '\0';
  59    return make_quoted_string(buffer);
  60 }
  61
  62 ///////////////////////////////////////////////////////////////////////////////
  63 //
  64 //  Current index map.
  65 //
  66 ///////////////////////////////////////////////////////////////////////////////
  67 HashTable * current_index_map = 0;
  68 Bool        merge_match       = true;  // should we merge the DFAs?
  69 Id          current_failure   = 0;     // jump label for failure
  70
  71 ///////////////////////////////////////////////////////////////////////////////
  72 //
  73 //  Is the expression simple?
  74 //
  75 ///////////////////////////////////////////////////////////////////////////////
  76 Bool is_simple_exp (Exp exp)
  77 {  match while (exp)
  78    {  IDexp _ || LITERALexp _: { return true; }
  79    |  MARKEDexp(_,e):          { exp = e; }
  80    |  _:                       { return false; }
  81    }
  82 }
  83
  84
  85 ///////////////////////////////////////////////////////////////////////////////
  86 //
  87 //  Generate match variable bindings for complex match expressions.
  88 //
  89 ///////////////////////////////////////////////////////////////////////////////
  90 void compute_match_variables(MatchExps exps)
  91 {  static LabelGen vars("_V");
  92    for_each (MatchExp, me, exps)
  93    {  match (me)
  94       {  MATCHexp(e,mv) | mv == 0 && ! is_simple_exp(e):
  95          {  mv = vars.new_label(); }
  96       |  _: { /* skip */ }
  97       }
  98    }
  99 }
 100
 101 ///////////////////////////////////////////////////////////////////////////////
 102 //
 103 //  Generate pattern matching code from a match dag
 104 //
 105 ///////////////////////////////////////////////////////////////////////////////
 106 void MatchCompiler::gen(Match mt, MatchOptions match_options, Ty match_ty)
 107 {
 108    if (mt == FAILmatch) {
 109       if (current_failure) pr ("%? goto %s; ", current_failure);
 110       return;
 111    }
 112
 113    // check for duplicates
 114    if (mt->label)      { pr ("%? goto %s; ", mt->label); gotos++; return; }
 115    if (mt->shared > 1) { goto_labels++;
 116                         pr ("%^%s:; ", mt->label = labels.new_label()); }
 117    match (mt)
 118    {  FAILmatch:                                 // skip
 119    |  SUCCESSmatch(_, r as MATCHrule(_,_,_,_,decls)):
 120       { MarkCurrentRule mark(current_rule,r); pr ("%&", decls); }
 121    |  COSTmatch(n,_,set,rules):     { gen_cost_success_match(n,set,rules); }
 122    |  TREECOSTmatch(m,set,rules):   { gen_treecost_match(m,set,rules); }
 123    |  TREELABELmatch(m,t1,t2,i):    { gen_treelabel_match(m,t1,t2,i); }
 124    |  SUCCESSESmatch (n,set,rules):
 125       { if (current_options & MATCHwithtreecost)
 126           gen_treecost_match(FAILmatch,set,rules);
 127         else
 128           gen_success_match(n,set,rules);
 129       }
 130    |  RANGEmatch(pos,e,lo,hi,a,b):  { gen_range_match(pos,e,lo,hi,a,b,mt); }
 131    |  GUARDmatch (e,a,b):
 132       {  ifs++; pr ("%^if (%E) {%+%^%m%-%?} else {%+%^%m%-%?}\n",e,a,b); }
 133    |  CONSmatch (_,e,ty,
 134         DATATYPEty({ view_match, id, terms, qualifiers, opt ... },_),n,m,d)
 135       | qualifiers & QUALview:
 136       { gen_view_match (id, e, view_match, n, terms, m, d,
 137                         opt, qualifiers & QUALextensible); }
 138    |  CONSmatch (_,e,ty,
 139         DATATYPEty({ id, unit, arg = 0, terms, qualifiers, opt ... },_),n,m,d):
 140       { gen_switch (id, e, ty, unit, terms, m, d, mt->shared,
 141                     false, false, opt, qualifiers & QUALextensible); }
 142    |  CONSmatch (_,e,ty,
 143         DATATYPEty({ id, unit = 0, arg, terms, qualifiers, opt ... },_),n,m,d):
 144       { gen_switch (id, e, ty, arg, terms, m, d, mt->shared,
 145                     false, true, opt, qualifiers & QUALextensible); }
 146    |  CONSmatch (_,e,ty,
 147         DATATYPEty({ id, unit, arg, terms, opt, qualifiers ... },_),n,m,d):
 148       {  ifs++;
 149          pr ((unit > 1 ? "%^if (boxed(%e)) {%+" : "%^if (%e) {%+"), e);
 150          gen_switch (id, e, ty, arg, terms + unit, m + unit, d, mt->shared,
 151                      true, true, opt, qualifiers & QUALextensible);
 152          pr ("%-%?} else {%+");
 153          gen_switch (id, e, ty, unit, terms, m, d, mt->shared,
 154                      true, false, opt, qualifiers & QUALextensible);
 155          pr ("%-%?}\n");
 156       }
 157    |  LITERALmatch(_,e,l as [BOOLlit _ || INTlit _ || CHARlit _], n, a, b):
 158       {  Bool is_boolean;
 159          match (l[0])
 160          {  BOOLlit _: { is_boolean = true; }
 161          |  _:         { is_boolean = false; }
 162          }
 163          switches++;
 164          pr ("%^switch (%e) {\n%+", e);
 165          for (int i = 0; i < n; ) {
 166             int j;
 167             for (j = i+1; j < n; j++) if (a[i] != a[j]) break;
 168             int k = i;
 169             if (is_boolean && j == n && n == 2) {
 170                pr ("%^default:"); i = n;
 171             } else {
 172                for ( ; i < j; i++) {
 173                   pr ("%^case %l:", l[i]);
 174                   if (i != j - 1) pr ("\n");
 175                }
 176             }
 177             pr(" {%+%m%-%?} break;\n", a[k]);
 178          }
 179          if (! is_boolean || n < 2) pr ("%^default: {%+%m%-%?}", b);
 180          pr("%-%^}\n");
 181       }
 182    |  LITERALmatch(_,e,l as [REALlit _ || STRINGlit _], n, a, b):
 183       { gen_binary_search_on_literals(e,n,l,a,b); }
 184    |  LITERALmatch(_,e,l as [REGEXPlit _], n, a, b):
 185       { if (options.generate_report) open_logfile() << mt << '\n';
 186         gen_regexp_match(e,n,l,a,b,match_options,match_ty);
 187       }
 188    |  LITERALmatch(_,e,l as [QUARKlit _], n, a, b):
 189       { gen_quark_match(e,n,l,a,b,match_options); }
 190    |  _:  { bug ("gen(Match)"); }
 191    }
 192 }
 193
 194 ///////////////////////////////////////////////////////////////////////////////
 195 //
 196 //  Method to generate a bitmap of all the successful matching rules.
 197 //
 198 ///////////////////////////////////////////////////////////////////////////////
 199 void MatchCompiler::gen_success_match(int n, const BitSet * set, MatchRules)
 200 {  pr ("%^{%+  static const unsigned char matched_set__[%i] =\n%^{  %+",
 201        (n + 7) / 8
 202       );
 203    for(int i = 0; i < (n + 7) / 8; i++) {
 204       if (i > 0) pr (", ");
 205       if (i != 0 && (i % 8) == 0) pr ("%^");
 206       pr ("%i ", (int)set->byte(i));
 207    }
 208    pr ("%-};\n"
 209        "%^m__ = matched_set__;\n"
 210        "%-%^}\n"
 211       );
 212 }
 213
 214 ///////////////////////////////////////////////////////////////////////////////
 215 //
 216 //  Method to generate code for cost minimalization.
 217 //
 218 ///////////////////////////////////////////////////////////////////////////////
 219 void MatchCompiler::gen_cost_success_match(int n, const BitSet * set,
 220                                            MatchRules rules)
 221 {  int rule_no = 0;
 222    match while (rules)
 223    {  #[ one ... rest ]:
 224       {  if ((*set)[rule_no])
 225          {  match (one)
 226             {  MATCHrule (_,_,_,cost,_):
 227                {  match (cost)
 228                   {  NOcost:
 229                   |  INTcost c:
 230                   |  EXPcost e:
 231                   }
 232                }
 233             }
 234          }
 235          rules = rest;
 236          rule_no++;
 237       }
 238    }
 239 }
 240
 241 ///////////////////////////////////////////////////////////////////////////////
 242 //
 243 //  Method to generate a switch statement for pattern matching.
 244 //  This method is responsible for generating optimized code for a one-level
 245 //  match using C++'s "switch" statement.
 246 //
 247 ///////////////////////////////////////////////////////////////////////////////
 248 void MatchCompiler::gen_switch
 249    (Id id, Exp e, Ty ty, int n, Cons terms[], Match m[], Match def, int shared,
 250     Bool variant, Bool boxed, TyOpt optimizations, Bool is_refutable)
 251 {
 252    if (n == 1) {          // only one arm
 253       gen(m[0]);
 254    } else if (n == 2) {   // two arms, use "if"
 255       if (m[0] == m[1]) {
 256          merges++; if (m[0] != FAILmatch) m[0]->shared -= shared; gen(m[0]);
 257       } else {
 258          ifs++;
 259          Id prefix, suffix;
 260          if (boxed) {
 261             if (optimizations & OPTtaggedpointer)
 262             { prefix = "untagp("; suffix = ")"; }
 263             else
 264             { prefix = ""; suffix = "->tag__"; }
 265          } else { prefix = suffix = ""; }
 266
 267          pr ("%^if (%s%e%s) {%+%^%m%-%?} else {%+%^%m%-%?}\n",
 268              prefix, e, suffix, m[1], m[0]);
 269       }
 270    } else {
 271       /////////////////////////////////////////////////////////////////////////
 272       //  The following is the general case for handling n-ary branches.
 273       /////////////////////////////////////////////////////////////////////////
 274       int i, j;
 275
 276       /////////////////////////////////////////////////////////////////////////
 277       // If all n branches are the same, eliminate the match
 278       /////////////////////////////////////////////////////////////////////////
 279       for (i = n - 1; i > 0; i--) if (m[i] != m[i-1]) break;
 280       if (i == 0) { if (m[0] != FAILmatch) m[0]->shared -= (n-1) * shared;
 281                     merges++; gen(m[0]); return;
 282                   }
 283
 284       switches++;
 285       Id prefix, suffix;
 286
 287       /////////////////////////////////////////////////////////////////////////
 288       // Generate the "switch" expression.
 289       /////////////////////////////////////////////////////////////////////////
 290       if (boxed) {
 291          if (optimizations & OPTtaggedpointer)
 292          { prefix = "untagp("; suffix = ")"; }
 293          else
 294          { prefix = ""; suffix = "->tag__"; }
 295       } else {
 296          if (variant)
 297          { prefix = "(int)"; suffix = ""; }
 298          else
 299          { prefix = suffix = ""; }
 300       }
 301       pr ("%^switch (%s%e%s) {\n%+", prefix, e, suffix);
 302
 303       /////////////////////////////////////////////////////////////////////////
 304       //  Partition the arms of the matches into alternatives with the
 305       //  same actions.  Sort the partitions in increasing sizes.
 306       /////////////////////////////////////////////////////////////////////////
 307       struct ConsMatch
 308       { Cons term; Match action; int tag; };
 309       struct MatchPartition
 310       { int count; Conses terms; Match action; int first_tag; };
 311       ConsMatch      * sorted  = (ConsMatch *)mem_pool.c_alloc
 312                                      (sizeof(ConsMatch) * n);
 313       MatchPartition * parts   = (MatchPartition *)mem_pool.c_alloc
 314                                      (sizeof(MatchPartition) * n);
 315       int number_of_parts = 0;
 316       {  for (i = 0; i < n; i++)
 317          {  sorted[i].term      = terms[i];
 318             sorted[i].action    = m[i];
 319             if (terms[i] != NOcons) sorted[i].tag = terms[i]->tag;
 320          }
 321
 322          // sort branches according the actions
 323          heapSort(ConsMatch, sorted, n,
 324                   (key.action < sorted[i].action ||
 325                    key.action == sorted[i].action &&
 326                    key.tag < sorted[i].tag));
 327
 328          // partition each branch by action
 329          for (i = n - 1; i >= 0; i--)
 330          {  if (i == n-1 || sorted[i].action != sorted[i+1].action)
 331             {  parts[number_of_parts].terms  = #[sorted[i].term];
 332                parts[number_of_parts].action = sorted[i].action;
 333                parts[number_of_parts].count  = 1;
 334                parts[number_of_parts].first_tag = sorted[i].tag;
 335                number_of_parts++;
 336             } else {
 337                parts[number_of_parts-1].terms =
 338                    #[sorted[i].term ... parts[number_of_parts-1].terms];
 339                parts[number_of_parts-1].count++;
 340                if (parts[number_of_parts-1].first_tag > sorted[i].tag)
 341                   parts[number_of_parts-1].first_tag = sorted[i].tag;
 342             }
 343          }
 344
 345          // Sort partitions in order of frequency; so that
 346          // the most frequent case becomes the "default" inside
 347          // the "switch" statement.
 348          heapSort(MatchPartition, parts, number_of_parts,
 349                   (key.count < parts[i].count ||
 350                    key.count == parts[i].count &&
 351                    key.first_tag < parts[i].first_tag));
 352       }
 353
 354       /////////////////////////////////////////////////////////////////////////
 355       // Generate the arms of the "switch".
 356       // We try to combine the arms that are the same together into
 357       // one rule to help the compiler.
 358       /////////////////////////////////////////////////////////////////////////
 359       for (i = 0; i < number_of_parts; i++)
 360       {  if (i == number_of_parts - 1) {
 361             pr ("%^default:");
 362          } else {
 363             Conses tags = parts[i].terms;
 364             match while (tags)
 365             {  #[ one ... rest ]:
 366                {  pr ("%^case %*:", one, false);
 367                   if (rest != #[]) pr ("\n");
 368                   tags = rest;
 369                }
 370             }
 371          }
 372          if (parts[i].action != FAILmatch)
 373             parts[i].action->shared -= (parts[i].count - 1) * shared;
 374          pr (" {%+%?%m%?} break;\n%-", parts[i].action);
 375       }
 376
 377       pr ("%-%^}\n");
 378    }
 379 }
 380
 381 ///////////////////////////////////////////////////////////////////////////////
 382 //
 383 //  Generate binary search for testing literals
 384 //
 385 ///////////////////////////////////////////////////////////////////////////////
 386 void MatchCompiler::gen_binary_search_on_literals
 387    (Exp e, int n, Literal l[], Match m[], Match d)
 388 {  if (n <= 4) {
 389       /////////////////////////////////////////////////////////////////////////
 390       //  Generate linear tests for simple literal tests.
 391       /////////////////////////////////////////////////////////////////////////
 392       for (int i = 0; i < n; i++) {
 393          ifs++;
 394          if (i > 0) pr("%^else "); else pr ("%^");
 395          pr ("if (%=(%e,%l)) {%m}\n",l[i], e, l[i], m[i]);
 396       }
 397       if (d != FAILmatch) pr ("%^else {%m}\n", d);
 398       else if (current_failure) pr ("%^else goto %s;\n", current_failure);
 399    } else {
 400       /////////////////////////////////////////////////////////////////////////
 401       //  Generate binary search for tests containing many alternatives.
 402       /////////////////////////////////////////////////////////////////////////
 403       int k = (n+1)/2;
 404       ifs++;
 405       pr ("%^if (%<(%e,%l)) {\n%+", l[k], e, l[k]);
 406       gen_binary_search_on_literals(e,k,l,m,d);
 407       pr ("%-%^} else {\n%+");
 408       gen_binary_search_on_literals(e,n-k,l+k,m+k,d);
 409       pr ("%-%^}\n");
 410    }
 411 }
 412
 413 ///////////////////////////////////////////////////////////////////////////////
 414 //
 415 //  Generate range matching
 416 //
 417 ///////////////////////////////////////////////////////////////////////////////
 418 void MatchCompiler::gen_range_match
 419    (Pos pos, Exp e, int lo, int hi, Match a, Match b, Match m)
 420 {  if (lo == hi)
 421    {  switches++;
 422       pr ("%^switch (%e) {%+",e);
 423       match while (m)
 424       {  RANGEmatch (p, e, low, high, a, b) | low == high && pos_equal(pos,p):
 425          { pr ("%^case %i: {%+%m%-%?} break;", low, a); m = b; }
 426       }
 427       pr ("%^default: {%+%m%-%?}"
 428           "%-%^}\n", m
 429          );
 430    } else
 431    {  ifs++;
 432       if (lo == 0) {
 433          pr ("%^if (%e <= %i) {%+%^%m%-%?} else {%+%^%m%-%?}\n",e,hi,a,b);
 434       } else if (hi == INT_MAX) {
 435          pr ("%^if (%e >= %i) {%+%^%m%-%?} else {%+%^%m%-%?}\n",e,lo,a,b);
 436       } else {
 437          pr ("%^if (%i <= %e && %e <= %i) {%+%^%m%-%?} else {%+%^%m%-%?}\n",
 438              lo,e,e,hi,a,b);
 439       }
 440    }
 441 }
 442
 443 ///////////////////////////////////////////////////////////////////////////////
 444 //
 445 //  Generate view matching
 446 //
 447 ///////////////////////////////////////////////////////////////////////////////
 448 void MatchCompiler::gen_view_match
 449    (Id id, Exp e, Exp view_match, int n, Cons terms [], Match m[], Match d,
 450     TyOpt opt, TyQual qual)
 451 {  if (view_match != NOexp)
 452    {  switches++;
 453       pr ("%^switch (%e) {%+", subst(view_match,&e));
 454       for (int i = 0; i < n; i++)
 455       {  pr ("%^case %e: {%+%m%-%?} break;", terms[i]->view_predicate, m[i]);
 456       }
 457       pr ("%-%^}\n");
 458    } else
 459    {  int i;
 460       for (i = 0; i < n; i++)
 461       {  int j;
 462          for (j = i + 1; j < n; j++) if (m[i] != m[j]) break;
 463          if (j == n) break;
 464          Exp predicate_fun = terms[i]->view_predicate;
 465          Exp predicate     = subst(predicate_fun,&e);
 466          ifs++;
 467          pr("%^%sif (%e) {%+%^%m%-%?} ",
 468             (i > 0 ? "else " : ""), predicate, m[i]);
 469       }
 470       if (i < n)
 471          pr ("%^%s{%+%^%m%-%?}\n", (i > 0 ? "else " : ""), m[i]);
 472    }
 473 }
 474
 475 ///////////////////////////////////////////////////////////////////////////////
 476 //
 477 //  Generate regular expression matching as a DFA.
 478 //
 479 ///////////////////////////////////////////////////////////////////////////////
 480 void MatchCompiler::gen_regexp_match
 481    (Exp e, int n, Literal l[], Match m[], Match d,
 482     MatchOptions options, Ty match_ty)
 483 {  LexerGen lexerGen;
 484    const char ** regexps = (const char **)mem_pool[n * sizeof(const char *)];
 485    const char ** contexts = 0;
 486
 487    ////////////////////////////////////////////////////////////////////////////
 488    //  If we have a match type, locate the set of contexts.
 489    ////////////////////////////////////////////////////////////////////////////
 490    if (options & MATCHscanner)
 491    {  match (deref_all(match_ty))
 492       {  NOty: // skip
 493       |  DATATYPEty({ terms, unit ... },_):
 494          {  contexts = (const char **)mem_pool[(unit+1)*sizeof(const char *)];
 495             if (unit <= 1)
 496                msg("%L%wdatatype has less than 2 unit constructors for contexts");
 497             for (int i = 1; i < unit; i++)
 498             {  match (terms[i])
 499                {  ONEcons { name ... }: { contexts[i-1] = name; }
 500                |  _: // skip
 501                }
 502             }
 503             contexts[unit-1] = 0;
 504          }
 505       |  _: { error ("%Lillegal context type: %T\n", match_ty); }
 506       }
 507    }
 508
 509    ////////////////////////////////////////////////////////////////////////////
 510    //  Allocate a regexp array
 511    ////////////////////////////////////////////////////////////////////////////
 512    for (int i = 0; i < n; i++)
 513    {  match (l[i])
 514       {  REGEXPlit re:
 515          {  int len           = strlen(re);
 516             char * regexp     = str_pool(re+1,len-1);
 517             regexp[len-2]     = '\0';
 518             regexps[i]        = regexp;
 519          }
 520       |  _: { bug("gen_regexp_match"); }
 521       }
 522    }
 523
 524    int opt = LexerGen::None;
 525    if (options & MATCHscanner)
 526    {  opt |= LexerGen::Backtracking;
 527       debug_msg("%Lgenerating backtracking scanner\n");
 528    }
 529    if (options & MATCHcaseinsensitive) opt |= LexerGen::CaseInsensitive;
 530
 531    lexerGen.compile(n, regexps, contexts, 255, opt);
 532
 533    if (! lexerGen.ok()) {
 534       error ("%L%s in: %l\n", lexerGen.error_message(), l[lexerGen.bad()]);
 535    } else {
 536       /////////////////////////////////////////////////////////////////////////
 537       //  Generate the action code
 538       /////////////////////////////////////////////////////////////////////////
 539       Id id = vars.new_label();
 540       pr ("%^{\n%+");
 541       lexerGen.gen_code(*output, id);
 542       switches++;
 543       pr ("%^static const RegexMatch %s"
 544           "%^                 ( %s_base,"
 545           "%^                   %s_check,"
 546           "%^                   %s_def,"
 547           "%^                   %s_next,"
 548           "%^                   %s_accept_rule,"
 549           "%^                   %s_equiv_classes );\n",
 550           id, id, id, id, id, id, id);
 551       Id rule_binding = "";
 552       if (options & MATCHlexemepat)
 553       {  pr ("%^int rule__;");
 554          rule_binding = "rule__ = ";
 555       }
 556       if (options & MATCHscanner) {
 557          pr ("%^const char * next;\n"
 558              "%^switch(%s%s.MatchText(RegexMatch::start_state,%e,next)) {%+",
 559              rule_binding, id, e);
 560       } else {
 561          pr ("%^switch(%s%s.MatchText(%e)) {%+", rule_binding, id, e);
 562       }
 563       for (int i = 0; i < n; i++)
 564          pr ("%^case %i: {%+%m%-%?} break;", i+1, m[i]);
 565       pr ("%^default: {%+%m%-%?}", d);
 566       pr ("%-%^}\n"
 567           "%-%^}\n");
 568
 569       /////////////////////////////////////////////////////////////////////////
 570       //  Generate a report
 571       /////////////////////////////////////////////////////////////////////////
 572       if (::options.generate_report) lexerGen.print_report(open_logfile());
 573    }
 574 }
 575
 576 ///////////////////////////////////////////////////////////////////////////////
 577 //
 578 //  Generate quark pattern matching
 579 //
 580 ///////////////////////////////////////////////////////////////////////////////
 581 void MatchCompiler::gen_quark_match
 582    (Exp e, int n, Literal l[], Match m[], Match d, MatchOptions options)
 583 {  for (int i = 0; i < n; i++)
 584    {  ifs++;
 585       pr ("%^%sif (%e == %l) {%+%^%m%-%?} ",
 586           (i > 0 ? "else " : ""), e, l[i], m[i]);
 587    }
 588    pr ("%^%s{%+%^%m%-%?}\n", (n > 0 ? "else " : ""), d);
 589 }
 590
 591 ///////////////////////////////////////////////////////////////////////////////
 592 //
 593 //  Method to translate and merge a set of patterns
 594 //
 595 ///////////////////////////////////////////////////////////////////////////////
 596 Match MatchCompiler::trans_merge
 597    (int n, MatchRules rules, int match_options, Cost * costs)
 598 {  Match m = FAILmatch;
 599    int rule_no = 0;
 600    for_each(MatchRule, r, rules)
 601    {  match (r)
 602       {  MATCHrule(_, pat, guard, cost, decls):
 603          {  if (! r->is_chain_rule)
 604             {  Match rhs;
 605                if (match_options & (MATCHall | MATCHwithcost)) {
 606                   BitSet * set = new (mem_pool,n) BitSet;
 607                   set->add(rule_no);
 608                   if (costs && ! (match_options & MATCHwithtreecost))
 609                       rhs = COSTmatch(n,costs,set,rules);
 610                   else
 611                       rhs = SUCCESSESmatch(n,set,rules);
 612                } else {
 613                   r->used = false; rhs = SUCCESSmatch(rule_no,r);
 614                }
 615                if (guard != NOexp) rhs = GUARDmatch(guard,rhs,FAILmatch);
 616                rhs = trans(pat, POSzero, false, rhs, FAILmatch);
 617                debug_msg("%r => %M\n", r, rhs);
 618                m = merge (m, rhs);
 619             }
 620             rule_no++;
 621          }
 622       }
 623    }
 624    return m;
 625 }
 626
 627 ///////////////////////////////////////////////////////////////////////////////
 628 //
 629 //  Method to translate but do not merge a set of patterns.
 630 //  Use Wadler's algorithm.
 631 //
 632 ///////////////////////////////////////////////////////////////////////////////
 633 Match MatchCompiler::trans_no_merge
 634    (int n, int rule_no, MatchRules rules, int match_options, Cost * costs)
 635 {
 636    if (rules == #[]) return FAILmatch;
 637    else {
 638       match (rules->#1)
 639       {  r as MATCHrule(_, pat, guard, cost, decls):
 640          {  Match rhs;
 641             if (match_options & (MATCHall | MATCHwithcost)) {
 642                BitSet * set = new (mem_pool,n) BitSet;
 643                set->add(rule_no);
 644                if (costs) rhs = COSTmatch(n,costs,set,rules);
 645                else       rhs = SUCCESSESmatch(n,set,rules);
 646             } else {
 647                r->used = false; rhs = SUCCESSmatch(rule_no,r);
 648             }
 649             Match no =
 650                trans_no_merge(n, rule_no+1, rules->#2, match_options, costs);
 651             if (guard != NOexp) rhs = GUARDmatch(guard,rhs,no);
 652             return trans(pat, POSzero, false, rhs, no);
 653          }
 654       }
 655    }
 656 }
 657
 658 ///////////////////////////////////////////////////////////////////////////////
 659 //
 660 //  Instrument the matching code if tracing is on
 661 //
 662 ///////////////////////////////////////////////////////////////////////////////
 663 void MatchCompiler::instrument_trace(MatchRules rules)
 664 {  for_each(MatchRule, r, rules)
 665    {  match (r)
 666       {  MATCHrule(id,pat,guard,cost,action):
 667          {  char buffer[4096];
 668             ostrstream stream(buffer, sizeof(buffer));
 669             std::ostream& s = stream;
 670             s << r << ends;
 671             action =
 672               #[ EXPdecl(
 673                    APPexp(IDexp("PROP_TRACE"),
 674                      TUPLEexp(#[
 675                        LITERALexp(STRINGlit(make_quoted_string(buffer))),
 676                        LITERALexp(STRINGlit(make_quoted_string(r->file_name))),
 677                        LITERALexp(INTlit(r->begin_line))
 678                      ]))),
 679                  OPAQUEdecl(";") ...
 680                  action
 681               ];
 682          }
 683       }
 684    }
 685 }
 686
 687 ///////////////////////////////////////////////////////////////////////////////
 688 //
 689 //  Compute the match dag from a set of pattern matching rules.
 690 //
 691 ///////////////////////////////////////////////////////////////////////////////
 692 Match MatchCompiler::match_of
 693    (int n, MatchRules rules, MatchOptions match_options)
 694 {  Match m;
 695
 696    ////////////////////////////////////////////////////////////////////////////
 697    //  Save the last index map.
 698    ////////////////////////////////////////////////////////////////////////////
 699    HashTable * last_index_map = current_index_map;
 700
 701    ////////////////////////////////////////////////////////////////////////////
 702    //  Create index map for this pattern set if necessary.
 703    ////////////////////////////////////////////////////////////////////////////
 704    if (options.adaptive_matching) {
 705       debug_msg("Creating index map\n");
 706       current_index_map = new HashTable(pos_hash, pos_equal, 129);
 707       indexing(rules, *current_index_map);
 708       debug_msg("Finished indexing\n");
 709    } else {
 710       current_index_map = 0;
 711    }
 712
 713    ////////////////////////////////////////////////////////////////////////////
 714    //  If tracing is on, instrument the code.
 715    ////////////////////////////////////////////////////////////////////////////
 716    if (options.trace && (match_options & MATCHnotrace) == 0)
 717       instrument_trace(rules);
 718
 719    ////////////////////////////////////////////////////////////////////////////
 720    //  Make a cost vector if cost minimization is in effect
 721    ////////////////////////////////////////////////////////////////////////////
 722    Cost * cost_vector = 0;
 723    if (match_options & MATCHwithintcost)
 724    {  cost_vector = (Cost*)mem_pool[n * sizeof(Cost)];
 725       int i = 0;
 726       for_each(MatchRule, r, rules)
 727       {  match (r)
 728          {  MATCHrule(_,_,_,cost,_): { cost_vector[i] = cost; i++; } }
 729       }
 730    }
 731
 732    ////////////////////////////////////////////////////////////////////////////
 733    //  Translate each pattern into a matching tree and merge them together.
 734    ////////////////////////////////////////////////////////////////////////////
 735    if (merge_match)
 736       m = trans_merge(n, rules, match_options, cost_vector);
 737    else
 738       m = trans_no_merge(n, 0, rules, match_options, cost_vector);
 739
 740    m = make_dag (m, match_options, rules);
 741    debug_msg("Matching DFA: %M\n", m);
 742
 743    ////////////////////////////////////////////////////////////////////////////
 744    // Error checking.
 745    ////////////////////////////////////////////////////////////////////////////
 746    // BUG 3/6/97: Always check for selectability!!!
 747    if (true || (match_options & MATCHnocheck) == 0) {
 748       if (match_options & (MATCHall | MATCHwithcost)) {
 749          BitSet * may_match = new (mem_pool,n) BitSet;
 750          matchables(m,*may_match);
 751          int i = 0;
 752          for_each (MatchRule, r, rules)
 753          {  if (! may_match->contains(i) && ! r->is_chain_rule)
 754                error("%!this rule is never selected: %r\n", r->loc(), r);
 755             i++;
 756          }
 757       } else {
 758          {  for_each (MatchRule,r,rules)
 759             {  if (! r->used)
 760                   error ("%!this rule is never used: %r\n", r->loc(), r);
 761             }
 762          }
 763       }
 764    }
 765
 766    ////////////////////////////////////////////////////////////////////////////
 767    //  Clean up the index map
 768    ////////////////////////////////////////////////////////////////////////////
 769    if (current_index_map) delete current_index_map;
 770    current_index_map = last_index_map;
 771    return m;
 772 }
 773
 774 ///////////////////////////////////////////////////////////////////////////////
 775 //
 776 //  Returns true if the set of rules involve cost expressions.
 777 //
 778 ///////////////////////////////////////////////////////////////////////////////
 779 int involve_cost(MatchRules rules)
 780 {  int options = MATCHnone;
 781    for_each(MatchRule, r, rules)
 782    {  match (r)
 783       {  MATCHrule(_,_,_,INTcost _, _):
 784          { options |= MATCHwithcost | MATCHwithintcost; }
 785       |  MATCHrule(_,_,_,EXPcost _, _):
 786          { options |= MATCHwithcost | MATCHwithexpcost; }
 787       |  _:
 788       }
 789    }
 790    return options;
 791 }
 792
 793 ///////////////////////////////////////////////////////////////////////////////
 794 //
 795 //  Method to check for refutable set of rules and print out
 796 //  warning/error messages.
 797 //
 798 ///////////////////////////////////////////////////////////////////////////////
 799 static Bool check_refutable
 800    (Match m, MatchRules rules, MatchOptions match_options)
 801 {   Bool is_refutable = refutable(m);            // error checking
 802     if (! (match_options & MATCHnocheck) &&
 803         ! (match_options & MATCHwhile) && is_refutable) {
 804       msg ("%!%wpatterns are not exhaustive:\n", rules->#1->loc());
 805       for_each(MatchRule,r,rules) msg("%!\t%r\n", r->loc(), r);
 806     }
 807     return is_refutable;
 808 }
 809
 810 ///////////////////////////////////////////////////////////////////////////////
 811 //
 812 //  Compile a match/matchall statement.
 813 //
 814 ///////////////////////////////////////////////////////////////////////////////
 815 void MatchCompiler::gen_match_stmt
 816    (MatchExps exps, MatchRules rules, MatchOptions match_options, Ty match_ty)
 817 {  MemPoolMark marker = mem_pool.getMark();     // set heap marker
 818    int n              = length(rules);
 819    Ty pattern_tys     = type_match_rules(rules);    // type inference
 820    Id save_failure    = current_failure;
 821    current_failure    = 0;
 822    MatchOptions save  = current_options;
 823    current_options    = match_options;
 824
 825    if (pattern_tys != NOty) {
 826       pr ("%^{\n%+");
 827       if (match_options & MATCHwhile) {
 828          pr ("%^for (;;) {%+"); current_failure = labels.new_label();
 829       }
 830
 831       // check for cost expressions
 832       int cost_opts = involve_cost(rules);
 833       if (cost_opts & MATCHwithcost) {
 834          if (match_options & MATCHall)
 835             if (! (match_options & MATCHwithtreecost))
 836                msg ("%L%wmatching costs are ignored.\n");
 837          else
 838             match_options |= cost_opts;
 839       }
 840
 841       Match m = match_of(n, rules, match_options); // compile patterns
 842       Bool is_refutable = check_refutable(m, rules, match_options);
 843
 844       // prefix code for matchall
 845       if ((match_options & (MATCHall | MATCHwithcost)) &&
 846           ! (match_options & MATCHwithtreecost))
 847          pr ("%^const unsigned char * m__%s;\n", (is_refutable ? " = 0" : ""));
 848
 849       gen_match_variables(exps, pattern_tys);
 850       gen(m, match_options, match_ty);
 851
 852       // suffix code for cost minimization
 853       if (! (match_options & MATCHwithtreecost))
 854       {  if (match_options & MATCHwithexpcost)
 855             gen_match_cost_minimization(n, m, rules, is_refutable);
 856
 857          // suffix code for matchall
 858          else if (match_options & MATCHall)
 859             gen_matchall_suffix(n, m, rules, is_refutable);
 860       }
 861
 862       if (match_options & MATCHwhile)
 863       {  pr ("%-%^}");
 864          if (is_refutable) pr("%^%s:;", current_failure);
 865       }
 866       pr ("%-%^}");
 867    }
 868    mem_pool.setMark(marker); // release all memory used
 869    current_failure = save_failure;
 870    current_options = save;
 871 }
 872
 873 ///////////////////////////////////////////////////////////////////////////////
 874 //
 875 //  Generate suffix code for a matchall statement.
 876 //  The suffix code goes thru the bitmap and select all rule with
 877 //  its bit set.
 878 //
 879 ///////////////////////////////////////////////////////////////////////////////
 880 void MatchCompiler::gen_matchall_suffix
 881    (int n, Match m, MatchRules rules, Bool is_refutable)
 882 {  int index = 0; int bit = 0;
 883    const BitSet& always_match = always_matchables(m,n);
 884    if (is_refutable) { ifs++; pr ("%^if (m__) {%+"); }
 885
 886    for_each (MatchRule, r, rules)
 887    {  match (r)
 888       {  MATCHrule(_,_,_,_,action):
 889          {  if (! always_match.contains(index * 8 + bit)) {
 890                ifs++;
 891                pr ("%^if (m__[%i] & %i) ", index, 1 << bit);
 892             } else {
 893                pr ("%^");
 894             }
 895             MarkCurrentRule mark(current_rule,r);
 896             pr ("{%+%&%-%?}\n", action);
 897             if (++bit == 8) { bit = 0; index++; }
 898          }
 899       }
 900    }
 901    if (is_refutable) pr ("%-%^}");
 902 }
 903
 904 ///////////////////////////////////////////////////////////////////////////////
 905 //
 906 //  Generate suffix code for a match statement with cost minimization.
 907 //  The bitmap selected with determine which cost function to execute.
 908 //  When all the appropriate cost functions are executed, we choose the
 909 //  matched rule with the lowest cost.  Ties are broken by the lexical
 910 //  order of the rules.
 911 //
 912 ///////////////////////////////////////////////////////////////////////////////
 913 void MatchCompiler::gen_match_cost_minimization
 914    (int n, Match m, MatchRules rules, Bool is_refutable)
 915 {  int index, bit;
 916    const BitSet& always_match = always_matchables(m,n);
 917
 918    pr ("%^do {%+"
 919        "%^int tmp_cost__, cost__ = %i, rule__ = -1;", MAX_COST);
 920    if (is_refutable) { ifs++; pr ("%^if (m__) {%+"); }
 921    {  index = bit = 0;
 922       for_each (MatchRule, r, rules)
 923       {  pr ("%^");
 924          if (! always_match.contains(index * 8 + bit)) {
 925             ifs++;
 926             pr ("if (m__[%i] & %i) ", index, 1 << bit);
 927          }
 928          int rule_no = index * 8 + bit;
 929          match (r)
 930          {  MATCHrule (_,_,_,EXPcost(e,_),_):
 931             {  pr ("if ((tmp_cost__ = %e) < cost__) { cost__ = tmp_cost__; rule_ = %i; }",
 932                    e, rule_no);
 933             }
 934          |  MATCHrule (_,_,_,NOcost,_):
 935             {  pr ("{ rule__ = %i; break; }", rule_no);  }
 936          |  MATCHrule (_,_,_,INTcost c,_):
 937             {  pr ("if (cost__ > %i) { cost__ = %i; rule__ = %i; }", c, c, rule_no); }
 938          }
 939          if (++bit == 8) { bit = 0; index++; }
 940       }
 941    }
 942    if (is_refutable) pr ("%-%^}");
 943    pr ("%-%^} while (0);"
 944        "%^switch (rule__) {%+");
 945    {  int i = 0;
 946       for_each(MatchRule, r, rules)
 947       {  match (r)
 948          {  MATCHrule (_,_,_,cost,action):
 949             {  MarkCurrentRule mark(current_rule,r);
 950                pr ("%^case %i: {%+%&%-%?} break;", i, action);
 951                i++;
 952             }
 953          }
 954       }
 955    }
 956    pr ("%-%^}");
 957 }
 958
 959 ///////////////////////////////////////////////////////////////////////////////
 960 //
 961 //  Generate code that binds match variables.
 962 //
 963 ///////////////////////////////////////////////////////////////////////////////
 964 void MatchCompiler::gen_match_variables(MatchExps es, Ty ty)
 965 {  Tys tys;
 966    if (length(es) > 1) {
 967       match (deref(ty))
 968       {  TUPLEty ts: { tys = ts; }
 969       |  _:          { bug("gen_match_variables()"); }
 970       }
 971    } else {
 972       tys = #[ty];
 973    }
 974    for ( ; es && tys; es = es->#2, tys = tys->#2) {
 975       match (es->#1)
 976       {  me as MATCHexp(e,mv) | mv != 0:
 977          {  if (! is_ground(tys->#1))
 978                error ("%!missing type info in expression %e : %T\n",
 979                       me->loc(), e, tys->#1);
 980             pr ("%^%t = %e;\n", tys->#1, mv, e);
 981          }
 982       |  _:  { /* skip */ }
 983       }
 984    }
 985 }
 986
 987 ///////////////////////////////////////////////////////////////////////////////
 988 //
 989 //  Generate code for a set of function definitions.
 990 //
 991 ///////////////////////////////////////////////////////////////////////////////
 992 void MatchCompiler::gen_fun_def (FunDefs fundefs)
 993 {  // Generate the prototype first (to deal with recursive definitions).
 994    MemPoolMark marker = mem_pool.getMark();     // set heap marker
 995    {  for_each (FunDef, f, fundefs)
 996       {  match (f)
 997          {  FUNdef(id, arg_ty, return_ty, rules):
 998             {  arg_ty = type_match_rules(rules);
 999                char buf[1024];
1000                std::ostrstream b(buf,sizeof(buf));
1001                std::ostream& s = b;
1002                s << id << std::ends;
1003                Ty ret_ty = return_ty == NOty ? void_ty : return_ty;
1004                pr ("%^%t %b;\n",
1005                    ret_ty, buf, arg_ty, "1", TYformal);
1006                if (! is_ground(arg_ty))
1007                   error ("%!missing type info in function %q %T\n",
1008                          f->loc(), id, arg_ty);
1009             }
1010          }
1011       }
1012    }
1013
1014    // Then generate the body of the functions.
1015    {  for_each (FunDef, f, fundefs)
1016       {  match (f)
1017          {  FUNdef(id, arg_ty, return_ty, rules):
1018             {  int n = length(rules);
1019                Match m = match_of(n, rules, MATCHnone);
1020                check_refutable(m, rules, MATCHnone);
1021                Ty ret_ty = return_ty == NOty ? void_ty : return_ty;
1022                char buf[1024];
1023                std::ostrstream b(buf,sizeof(buf));
1024                std::ostream& s = b;
1025                s << id << std::ends;
1026                pr ("%^%t %b\n{\n%+",
1027                    ret_ty, buf, arg_ty, "1", TYformal);
1028                gen(m);
1029                pr ("%-%^}\n");
1030             }
1031          }
1032       }
1033    }
1034    mem_pool.setMark(marker); // release all memory used
1035 }