prop-src/matchcom.h

   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 "matchcom.ph".
   5 ///////////////////////////////////////////////////////////////////////////////
   6
   7 #line 1 "matchcom.ph"
   8 ///////////////////////////////////////////////////////////////////////////////
   9 //
  10 //  This file describes the interface to the pattern matching compiler.
  11 //
  12 ///////////////////////////////////////////////////////////////////////////////
  13 #ifndef match_compiler_h
  14 #define match_compiler_h
  15
  16 #include "ir.h"
  17 #include "ast.h"
  18 #include "patenv.h"
  19 #include "hashtab.h"
  20 #include "labelgen.h"
  21 #include "codegen.h"
  22
  23 ///////////////////////////////////////////////////////////////////////////////
  24 //
  25 //  Forward type declarations.
  26 //
  27 ///////////////////////////////////////////////////////////////////////////////
  28 class BitSet;       // bit sets
  29
  30 ///////////////////////////////////////////////////////////////////////////////
  31 //
  32 //  Pattern matching decision tree (dag)
  33 //
  34 ///////////////////////////////////////////////////////////////////////////////
  35 struct MatchBase : public MEM
  36 {
  37    int shared; Id label;
  38    MatchBase();
  39 };
  40
  41 #line 34 "matchcom.ph"
  42 #line 68 "matchcom.ph"
  43 ///////////////////////////////////////////////////////////////////////////////
  44 //
  45 // Forward class definition for Match
  46 //
  47 ///////////////////////////////////////////////////////////////////////////////
  48 #ifndef datatype_Match_defined
  49 #define datatype_Match_defined
  50    class a_Match;
  51    typedef a_Match * Match;
  52 #endif
  53
  54 #  define FAILmatch (Match)0
  55 #  define DONTCAREmatch (Match)1
  56
  57 ///////////////////////////////////////////////////////////////////////////////
  58 //
  59 // Forward class definition for Cost
  60 //
  61 ///////////////////////////////////////////////////////////////////////////////
  62 #ifndef datatype_Cost_defined
  63 #define datatype_Cost_defined
  64    class a_Cost;
  65    typedef a_Cost * Cost;
  66 #endif
  67
  68 #  define NOcost (Cost)0
  69
  70 ///////////////////////////////////////////////////////////////////////////////
  71 //
  72 // Forward class definition for Pos
  73 //
  74 ///////////////////////////////////////////////////////////////////////////////
  75 #ifndef datatype_Pos_defined
  76 #define datatype_Pos_defined
  77    class a_Pos;
  78    typedef a_Pos * Pos;
  79 #endif
  80
  81 #  define POSzero (Pos)0
  82 #  define POSinfinity (Pos)1
  83
  84 ///////////////////////////////////////////////////////////////////////////////
  85 //
  86 // Base class for datatype Match
  87 //
  88 ///////////////////////////////////////////////////////////////////////////////
  89 class a_Match : public MatchBase {
  90 public:
  91    enum Tag_Match {
  92       tag_SUCCESSmatch = 0, tag_SUCCESSESmatch = 1, tag_COSTmatch = 2,
  93       tag_GUARDmatch = 3, tag_LITERALmatch = 4, tag_RANGEmatch = 5,
  94       tag_CONSmatch = 6, tag_TREECOSTmatch = 7, tag_TREELABELmatch = 8,
  95       tag_BACKEDGEmatch = 9
  96    };
  97
  98 public:
  99    const Tag_Match tag__; // variant tag
 100 protected:
 101    inline a_Match(Tag_Match t__) : tag__(t__) {}
 102 public:
 103 };
 104 inline int boxed(const a_Match * x) { return (unsigned long)x >= 2; }
 105 inline int untag(const a_Match * x) { return boxed(x) ? x->tag__ + 2 : (int)x; }
 106 ///////////////////////////////////////////////////////////////////////////////
 107 //
 108 // Class for datatype constructor Match::SUCCESSmatch
 109 //
 110 ///////////////////////////////////////////////////////////////////////////////
 111 class Match_SUCCESSmatch : public a_Match {
 112 public:
 113 #line 36 "matchcom.ph"
 114    int _1; MatchRule _2;
 115    Match_SUCCESSmatch (int x_1, MatchRule x_2);
 116 };
 117
 118 ///////////////////////////////////////////////////////////////////////////////
 119 //
 120 // Class for datatype constructor Match::SUCCESSESmatch
 121 //
 122 ///////////////////////////////////////////////////////////////////////////////
 123 class Match_SUCCESSESmatch : public a_Match {
 124 public:
 125 #line 37 "matchcom.ph"
 126    int _1; BitSet * _2; MatchRules _3;
 127    Match_SUCCESSESmatch (int x_1, BitSet * x_2, MatchRules x_3);
 128 };
 129
 130 ///////////////////////////////////////////////////////////////////////////////
 131 //
 132 // Class for datatype constructor Match::COSTmatch
 133 //
 134 ///////////////////////////////////////////////////////////////////////////////
 135 class Match_COSTmatch : public a_Match {
 136 public:
 137 #line 38 "matchcom.ph"
 138    int _1; Cost * _2; BitSet * _3; MatchRules _4;
 139    Match_COSTmatch (int x_1, Cost * x_2, BitSet * x_3, MatchRules x_4);
 140 };
 141
 142 ///////////////////////////////////////////////////////////////////////////////
 143 //
 144 // Class for datatype constructor Match::GUARDmatch
 145 //
 146 ///////////////////////////////////////////////////////////////////////////////
 147 class Match_GUARDmatch : public a_Match {
 148 public:
 149 #line 39 "matchcom.ph"
 150    Exp _1; Match _2; Match _3;
 151    Match_GUARDmatch (Exp x_1, Match x_2, Match x_3);
 152 };
 153
 154 ///////////////////////////////////////////////////////////////////////////////
 155 //
 156 // Class for datatype constructor Match::LITERALmatch
 157 //
 158 ///////////////////////////////////////////////////////////////////////////////
 159 class Match_LITERALmatch : public a_Match {
 160 public:
 161 #line 40 "matchcom.ph"
 162    Pos _1; Exp _2; Literal * _3; int _4; Match * _5; Match _6;
 163    Match_LITERALmatch (Pos x_1, Exp x_2, Literal * x_3, int x_4, Match * x_5, Match x_6);
 164 };
 165
 166 ///////////////////////////////////////////////////////////////////////////////
 167 //
 168 // Class for datatype constructor Match::RANGEmatch
 169 //
 170 ///////////////////////////////////////////////////////////////////////////////
 171 class Match_RANGEmatch : public a_Match {
 172 public:
 173 #line 41 "matchcom.ph"
 174    Pos _1; Exp _2; int _3; int _4; Match _5; Match _6;
 175    Match_RANGEmatch (Pos x_1, Exp x_2, int x_3, int x_4, Match x_5, Match x_6);
 176 };
 177
 178 ///////////////////////////////////////////////////////////////////////////////
 179 //
 180 // Class for datatype constructor Match::CONSmatch
 181 //
 182 ///////////////////////////////////////////////////////////////////////////////
 183 class Match_CONSmatch : public a_Match {
 184 public:
 185 #line 42 "matchcom.ph"
 186    Pos _1; Exp _2; Ty _3; Ty _4; int _5; Match * _6; Match _7;
 187    Match_CONSmatch (Pos x_1, Exp x_2, Ty x_3, Ty x_4, int x_5, Match * x_6, Match x_7);
 188 };
 189
 190 ///////////////////////////////////////////////////////////////////////////////
 191 //
 192 // Class for datatype constructor Match::TREECOSTmatch
 193 //
 194 ///////////////////////////////////////////////////////////////////////////////
 195 class Match_TREECOSTmatch : public a_Match {
 196 public:
 197 #line 44 "matchcom.ph"
 198    Match _1; BitSet * _2; MatchRules _3;
 199    Match_TREECOSTmatch (Match x_1, BitSet * x_2, MatchRules x_3);
 200 };
 201
 202 ///////////////////////////////////////////////////////////////////////////////
 203 //
 204 // Class for datatype constructor Match::TREELABELmatch
 205 //
 206 ///////////////////////////////////////////////////////////////////////////////
 207 class Match_TREELABELmatch : public a_Match {
 208 public:
 209 #line 45 "matchcom.ph"
 210    Match _1; Ty _2; Ty _3; int _4;
 211    Match_TREELABELmatch (Match x_1, Ty x_2, Ty x_3, int x_4);
 212 };
 213
 214 ///////////////////////////////////////////////////////////////////////////////
 215 //
 216 // Class for datatype constructor Match::BACKEDGEmatch
 217 //
 218 ///////////////////////////////////////////////////////////////////////////////
 219 class Match_BACKEDGEmatch : public a_Match {
 220 public:
 221 #line 47 "matchcom.ph"
 222    int _1; Id _2; Match _3;
 223    Match_BACKEDGEmatch (int x_1, Id x_2, Match x_3);
 224 };
 225
 226 ///////////////////////////////////////////////////////////////////////////////
 227 //
 228 // Datatype constructor functions for Match
 229 //
 230 ///////////////////////////////////////////////////////////////////////////////
 231 extern a_Match * SUCCESSmatch (int x_1, MatchRule x_2);
 232 extern a_Match * SUCCESSESmatch (int x_1, BitSet * x_2, MatchRules x_3);
 233 extern a_Match * COSTmatch (int x_1, Cost * x_2, BitSet * x_3, MatchRules x_4);
 234 extern a_Match * GUARDmatch (Exp x_1, Match x_2, Match x_3);
 235 extern a_Match * LITERALmatch (Pos x_1, Exp x_2, Literal * x_3, int x_4, Match * x_5, Match x_6);
 236 extern a_Match * RANGEmatch (Pos x_1, Exp x_2, int x_3, int x_4, Match x_5, Match x_6);
 237 extern a_Match * CONSmatch (Pos x_1, Exp x_2, Ty x_3, Ty x_4, int x_5, Match * x_6, Match x_7);
 238 extern a_Match * TREECOSTmatch (Match x_1, BitSet * x_2, MatchRules x_3);
 239 extern a_Match * TREELABELmatch (Match x_1, Ty x_2, Ty x_3, int x_4);
 240 extern a_Match * BACKEDGEmatch (int x_1, Id x_2, Match x_3);
 241
 242 ///////////////////////////////////////////////////////////////////////////////
 243 //
 244 // Base class for datatype Cost
 245 //
 246 ///////////////////////////////////////////////////////////////////////////////
 247 class a_Cost : public MEM {
 248 public:
 249    enum Tag_Cost {
 250       tag_EXPcost = 0, tag_INTcost = 1
 251    };
 252
 253 public:
 254 };
 255 inline int boxed(const a_Cost * x) { return x != 0; }
 256 ///////////////////////////////////////////////////////////////////////////////
 257 //
 258 // Embbeded tag extraction functions
 259 //
 260 ///////////////////////////////////////////////////////////////////////////////
 261 inline int untagp(const a_Cost * x)
 262    { return (unsigned long)x & 3; }
 263 inline a_Cost * derefp(const a_Cost * x)
 264    { return (a_Cost*)((unsigned long)x & ~3); }
 265 inline int untag(const a_Cost * x) { return x ? untagp(x)+1 : 0; }
 266 ///////////////////////////////////////////////////////////////////////////////
 267 //
 268 // Class for datatype constructor Cost::EXPcost
 269 //
 270 ///////////////////////////////////////////////////////////////////////////////
 271 class Cost_EXPcost : public a_Cost {
 272 public:
 273 #line 55 "matchcom.ph"
 274    Exp _1; Ty _2;
 275    Cost_EXPcost (Exp x_1, Ty x_2 = NOty);
 276 };
 277
 278 ///////////////////////////////////////////////////////////////////////////////
 279 //
 280 // Class for datatype constructor Cost::INTcost
 281 //
 282 ///////////////////////////////////////////////////////////////////////////////
 283 class Cost_INTcost : public a_Cost {
 284 public:
 285 #line 56 "matchcom.ph"
 286    int INTcost;
 287    Cost_INTcost (int x_INTcost);
 288 };
 289
 290 ///////////////////////////////////////////////////////////////////////////////
 291 //
 292 // Datatype constructor functions for Cost
 293 //
 294 ///////////////////////////////////////////////////////////////////////////////
 295 extern a_Cost * EXPcost (Exp x_1, Ty x_2 = NOty);
 296 extern a_Cost * INTcost (int x_INTcost);
 297
 298 ///////////////////////////////////////////////////////////////////////////////
 299 //
 300 // Base class for datatype Pos
 301 //
 302 ///////////////////////////////////////////////////////////////////////////////
 303 class a_Pos : public MEM {
 304 public:
 305    enum Tag_Pos {
 306       tag_POSint = 0, tag_POSlabel = 1, tag_POSadaptive = 2
 307    };
 308
 309 public:
 310 };
 311 inline int boxed(const a_Pos * x) { return (unsigned long)x >= 2; }
 312 ///////////////////////////////////////////////////////////////////////////////
 313 //
 314 // Embbeded tag extraction functions
 315 //
 316 ///////////////////////////////////////////////////////////////////////////////
 317 inline int untagp(const a_Pos * x)
 318    { return (unsigned long)x & 3; }
 319 inline a_Pos * derefp(const a_Pos * x)
 320    { return (a_Pos*)((unsigned long)x & ~3); }
 321 inline int untag(const a_Pos * x) { return boxed(x) ? untagp(x) + 2 : (int)x; }
 322 ///////////////////////////////////////////////////////////////////////////////
 323 //
 324 // Class for datatype constructor Pos::POSint
 325 //
 326 ///////////////////////////////////////////////////////////////////////////////
 327 class Pos_POSint : public a_Pos {
 328 public:
 329 #line 65 "matchcom.ph"
 330    int _1; Pos _2;
 331    Pos_POSint (int x_1, Pos x_2);
 332 };
 333
 334 ///////////////////////////////////////////////////////////////////////////////
 335 //
 336 // Class for datatype constructor Pos::POSlabel
 337 //
 338 ///////////////////////////////////////////////////////////////////////////////
 339 class Pos_POSlabel : public a_Pos {
 340 public:
 341 #line 66 "matchcom.ph"
 342    Id _1; Pos _2;
 343    Pos_POSlabel (Id x_1, Pos x_2);
 344 };
 345
 346 ///////////////////////////////////////////////////////////////////////////////
 347 //
 348 // Class for datatype constructor Pos::POSadaptive
 349 //
 350 ///////////////////////////////////////////////////////////////////////////////
 351 class Pos_POSadaptive : public a_Pos {
 352 public:
 353 #line 67 "matchcom.ph"
 354    int _1; int * _2; Pos _3;
 355    Pos_POSadaptive (int x_1, int * x_2, Pos x_3);
 356 };
 357
 358 ///////////////////////////////////////////////////////////////////////////////
 359 //
 360 // Datatype constructor functions for Pos
 361 //
 362 ///////////////////////////////////////////////////////////////////////////////
 363 extern a_Pos * POSint (int x_1, Pos x_2);
 364 extern a_Pos * POSlabel (Id x_1, Pos x_2);
 365 extern a_Pos * POSadaptive (int x_1, int * x_2, Pos x_3);
 366
 367 #line 68 "matchcom.ph"
 368 #line 68 "matchcom.ph"
 369
 370
 371 ///////////////////////////////////////////////////////////////////////////////
 372 //
 373 //  Pretty printer for matching trees.
 374 //
 375 ///////////////////////////////////////////////////////////////////////////////
 376 extern std::ostream& operator << (std::ostream&, Match);
 377
 378 ///////////////////////////////////////////////////////////////////////////////
 379 //
 380 //  Function to reverse the polarity of a pattern.
 381 //
 382 ///////////////////////////////////////////////////////////////////////////////
 383 extern Polarity rev (Polarity);
 384
 385 ///////////////////////////////////////////////////////////////////////////////
 386 //
 387 //  Function to compute the match variables for a list of match expressions.
 388 //  Match variables are temporaries generated for complex expressions to
 389 //  prevent redundent evaluations.
 390 //
 391 ///////////////////////////////////////////////////////////////////////////////
 392 extern void compute_match_variables (MatchExps);
 393
 394 ///////////////////////////////////////////////////////////////////////////////
 395 //
 396 //  Function to convert a string into an array pattern.  This converts string
 397 //  patterns to be decomposed into a web of character patterns, allowing
 398 //  (potentially) more efficient matching.
 399 //
 400 ///////////////////////////////////////////////////////////////////////////////
 401 extern Pats make_string_pattern (const char *);
 402
 403 ///////////////////////////////////////////////////////////////////////////////
 404 //
 405 //  Functions to decorate the pattern for projection bindings.
 406 //  These are called to annotate a pattern with pattern variable bindings.
 407 //  The new bindings are entered into the pattern variable environments.
 408 //  These are called from the parser.
 409 //
 410 ///////////////////////////////////////////////////////////////////////////////
 411 extern void decor (Pat, Exp, Polarity, Bool, PatternVarEnv&, int&);
 412 extern void decor (MatchExps, Pat, Polarity, Bool, PatternVarEnv&, int&);
 413 extern void decor (MatchExps&, Pat, PatternVarEnv&, int&, int = -1);
 414
 415 ///////////////////////////////////////////////////////////////////////////////
 416 //
 417 //  Functions to decorate the pattern for attribute and cost bindings
 418 //  inside rewrite rules.  These are also called from the parser.
 419 //
 420 ///////////////////////////////////////////////////////////////////////////////
 421 extern int decor_rewrite (Pat,  int, int, PatternVarEnv&);
 422 extern int decor_rewrite (Pats, int, int, PatternVarEnv&);
 423 extern int decor_rewrite (Pat,  int, PatternVarEnv&);
 424
 425 ///////////////////////////////////////////////////////////////////////////////
 426 //
 427 //  Auxiliary function to retrieve the position vector of a decision tree.
 428 //  This is used during the pattern matching compilation process.
 429 //
 430 ///////////////////////////////////////////////////////////////////////////////
 431 extern Pos get_pos (Match);
 432
 433 ///////////////////////////////////////////////////////////////////////////////
 434 //
 435 //  Auxiliary functions to compute information on a matching tree.
 436 //  These are used during the pattern matching compilation process to
 437 //  eliminate redundant tests and for error detection.
 438 //
 439 ///////////////////////////////////////////////////////////////////////////////
 440 Bool          refutable         (Match);          // Is the pattern refutable?
 441 void          matchables        (Match, BitSet&); // Set of matchable rules.
 442 void          always_matchables (Match, BitSet&); // Set of always matching
 443 const BitSet& always_matchables (Match, int);     // rules.
 444
 445 ///////////////////////////////////////////////////////////////////////////////
 446 //
 447 //  Functions to perform substitutions on expressions.
 448 //  All INDexp(i) nodes are substituted with the corresponding replacement.
 449 //
 450 ///////////////////////////////////////////////////////////////////////////////
 451 extern Exp     subst (Exp,     Exp replacements[]);
 452 extern Exps    subst (Exps,    Exp replacements[]);
 453 extern LabExps subst (LabExps, Exp replacements[]);
 454
 455 ///////////////////////////////////////////////////////////////////////////////
 456 //
 457 //  Hashing and equality for literals.
 458 //  These are used in the matching tree -> dag conversion process.
 459 //
 460 ///////////////////////////////////////////////////////////////////////////////
 461 extern unsigned int literal_hash  (HashTable::Key);
 462 extern Bool         literal_equal (HashTable::Key, HashTable::Key);
 463
 464 ///////////////////////////////////////////////////////////////////////////////
 465 //
 466 //  Hashing and equality for position vectors.
 467 //  These are used in the matching tree -> dag conversion process.
 468 //
 469 ///////////////////////////////////////////////////////////////////////////////
 470 extern unsigned int pos_hash  (HashTable::Key);
 471 extern Bool         pos_equal (HashTable::Key, HashTable::Key);
 472
 473 ///////////////////////////////////////////////////////////////////////////////
 474 //
 475 //  Functions to check for refutability of a pattern.  These are used
 476 //  in the pattern sindexing scheme.
 477 //
 478 ///////////////////////////////////////////////////////////////////////////////
 479 extern Bool is_refutable  (Pat);
 480 extern Bool is_refutable  (Pats);
 481 extern Bool is_refutable  (LabPats);
 482
 483 ///////////////////////////////////////////////////////////////////////////////
 484 //
 485 //  The current index map.  This map is computed when using the adaptive
 486 //  pattern matching scheme.
 487 //
 488 ///////////////////////////////////////////////////////////////////////////////
 489 extern HashTable * current_index_map;
 490
 491 ///////////////////////////////////////////////////////////////////////////////
 492 //
 493 //  Methods for compute indexing information of a pattern.  These are
 494 //  used in the adaptive scheme.
 495 //
 496 ///////////////////////////////////////////////////////////////////////////////
 497 extern void indexing (int, Pat, Pos, HashTable&);
 498 extern void indexing (int, Pats, Pos, HashTable&);
 499 extern void indexing (MatchRules, HashTable&);
 500
 501 extern       Bool same_selectors;
 502
 503 extern Exp select (Exp, Cons, Ty = NOty);
 504
 505 ///////////////////////////////////////////////////////////////////////////////
 506 //
 507 //   Equality on expressions.
 508 //
 509 ///////////////////////////////////////////////////////////////////////////////
 510 extern Bool equal (Exp, Exp);
 511 extern Bool equal (Exps, Exps);
 512 extern Bool equal (LabExps, LabExps);
 513
 514 ///////////////////////////////////////////////////////////////////////////////
 515 //
 516 //  Substitution functions on patterns.  These are used to implement
 517 //  pattern laws.
 518 //
 519 ///////////////////////////////////////////////////////////////////////////////
 520 extern Pat     subst (Pat,     Pat [], Bool);
 521 extern Pats    subst (Pats,    Pat [], Bool);
 522 extern LabPats subst (LabPats, Pat [], Bool);
 523
 524 ///////////////////////////////////////////////////////////////////////////////
 525 //
 526 //  Methods to translate a match tree into an anotated tree with tree parsing
 527 //  cost.
 528 //
 529 ///////////////////////////////////////////////////////////////////////////////
 530 extern Match translate_treecost (Match, MatchRules);
 531
 532 ///////////////////////////////////////////////////////////////////////////////
 533 //
 534 //  Methods to enter and lookup a pattern constructor.
 535 //  These interact with the pattern/constructor environment.
 536 //  Called from the parser.
 537 //
 538 ///////////////////////////////////////////////////////////////////////////////
 539 extern Pat  apply_pat  (Pat, Pat);
 540
 541 ///////////////////////////////////////////////////////////////////////////////
 542 //
 543 //  The following is the interface definition of the pattern matching compiler.
 544 //
 545 ///////////////////////////////////////////////////////////////////////////////
 546 class MatchCompiler : virtual public CodeGen {
 547
 548    MatchCompiler(const MatchCompiler&);    // no copy constructor
 549    void operator = (const MatchCompiler&); // no assignment
 550
 551 protected:
 552    LabelGen vars, labels;                         // labels generators
 553    int merges, ifs, switches, gotos, goto_labels; // match compiler statistics
 554    MatchOptions     current_options;
 555    MatchRule        current_rule;
 556
 557    static HashTable quark_map;
 558    static LabelGen  quark_labels;
 559
 560 public:
 561    ////////////////////////////////////////////////////////////////////////////
 562    //
 563    //  Constructor and destructor
 564    //
 565    ////////////////////////////////////////////////////////////////////////////
 566             MatchCompiler();
 567    virtual ~MatchCompiler();
 568
 569    static Id quark_name(Id);
 570
 571    ////////////////////////////////////////////////////////////////////////////
 572    //
 573    //  Methods to compute the selection/projection function from a datatype
 574    //  domain.  This is used in the pattern binding annotation process.
 575    //
 576    ////////////////////////////////////////////////////////////////////////////
 577    static Exp untag(Exp, Ty);
 578    static Exp untag_one(Exp, Cons);
 579    static Exp make_select (Exp, Cons, Ty = NOty, Id = 0);
 580    static Exp tag_name_of (Cons, Bool normalized);
 581
 582 protected:
 583    ////////////////////////////////////////////////////////////////////////////
 584    //
 585    //  Methods to compile pattern matching.
 586    //
 587    ////////////////////////////////////////////////////////////////////////////
 588
 589    ////////////////////////////////////////////////////////////////////////////
 590    //
 591    //  Methods to for translation a pattern into a pattern matching tree.
 592    //
 593    ////////////////////////////////////////////////////////////////////////////
 594    Match trans          (Pat, Pos, Bool, Match, Match);
 595    Match trans          (Pats, int, Pos, Bool, Match, Match);
 596    Match trans          (Pats, Pos, Bool, Match, Match, int []);
 597    Match trans          (LabPats, Pos, Bool, Match, Match);
 598    Match trans_merge    (int, MatchRules, int, Cost *);
 599    Match trans_no_merge (int, int, MatchRules, int, Cost *);
 600
 601    ////////////////////////////////////////////////////////////////////////////
 602    //
 603    //  Methods to for tree composition/merging and tree to dag conversion.
 604    //
 605    ////////////////////////////////////////////////////////////////////////////
 606    Match compose        (Match, Match);
 607    Match merge          (Match, Match);
 608    Match make_dag       (Match, MatchOptions, MatchRules);
 609    Match match_of       (int, MatchRules, MatchOptions);
 610
 611    ////////////////////////////////////////////////////////////////////////////
 612    //
 613    //  Methods for generating high level statements and trace instrumentation.
 614    //
 615    ////////////////////////////////////////////////////////////////////////////
 616    void gen_match_stmt              (MatchExps, MatchRules,
 617                                      MatchOptions = MATCHnone, Ty = NOty);
 618    void gen_fun_def                 (FunDefs);
 619    void gen_match_variables         (MatchExps, Ty);
 620    void gen                         (Match, MatchOptions=MATCHnone, Ty=NOty);
 621    void gen_matchall_suffix         (int, Match, MatchRules, Bool);
 622    void gen_match_cost_minimization (int, Match, MatchRules, Bool);
 623    void gen_success_match           (int, const BitSet *, MatchRules);
 624    void gen_cost_success_match      (int, const BitSet *, MatchRules);
 625    virtual void gen_treecost_match  (Match, const BitSet *, MatchRules) = 0;
 626    virtual void gen_treelabel_match (Match, Ty, Ty, int) = 0;
 627
 628    void instrument_trace            (MatchRules);
 629
 630    ////////////////////////////////////////////////////////////////////////////
 631    //
 632    //  Method for generating range matching
 633    //
 634    ////////////////////////////////////////////////////////////////////////////
 635    void gen_range_match (Pos, Exp, int, int, Match, Match, Match);
 636
 637    ////////////////////////////////////////////////////////////////////////////
 638    //
 639    //  Method for generating view matching
 640    //
 641    ////////////////////////////////////////////////////////////////////////////
 642    void gen_view_match (Id, Exp, Exp, int, Cons [], Match [], Match,
 643                         TyOpt, TyQual);
 644
 645    ////////////////////////////////////////////////////////////////////////////
 646    //
 647    //  Low level methods for specific pattern matching constructs:
 648    //  C/C++ switches, binary search on literals, regular expression matching,
 649    //  and quarks matching code.
 650    //
 651    ////////////////////////////////////////////////////////////////////////////
 652    void gen_switch  (Id, Exp, Ty, int, Cons [], Match [], Match, int shared,
 653                      Bool, Bool, TyOpt, Bool);
 654    void gen_binary_search_on_literals(Exp, int, Literal [], Match [], Match);
 655    void gen_regexp_match
 656         (Exp, int, Literal [], Match [], Match, MatchOptions, Ty);
 657    void gen_quark_match
 658         (Exp, int, Literal [], Match [], Match, MatchOptions);
 659
 660    ////////////////////////////////////////////////////////////////////////////
 661    //
 662    //  Methods to generating debugging code.
 663    //
 664    ////////////////////////////////////////////////////////////////////////////
 665    int current_rule_line () const;
 666    const char * current_rule_text () const;
 667
 668 private:
 669    ///////////////////////////////////////////////////////////////////////////////
 670    //
 671    //  Functions for allocating arrays of Literal and Match.
 672    //  Used during the pattern matching compilation process.
 673    //
 674    ///////////////////////////////////////////////////////////////////////////////
 675    Literal * Literals (int);
 676    Match *   Matches  (int);
 677 };
 678
 679 ///////////////////////////////////////////////////////////////////////////////
 680 //
 681 //  Object to mark the current rule
 682 //
 683 ///////////////////////////////////////////////////////////////////////////////
 684 class MarkCurrentRule {
 685    MarkCurrentRule();
 686    MarkCurrentRule(const MarkCurrentRule&);
 687    void operator = (const MarkCurrentRule&);
 688    MatchRule& current_rule;
 689    MatchRule  old_rule;
 690 protected:
 691    MarkCurrentRule(MatchRule&, MatchRule);
 692   ~MarkCurrentRule();
 693    friend class MatchCompiler;
 694    friend class RewritingCompiler;
 695 };
 696
 697 #endif
 698 #line 397 "matchcom.ph"
 699 /*
 700 ------------------------------- Statistics -------------------------------
 701 Merge matching rules         = yes
 702 Number of DFA nodes merged   = 0
 703 Number of ifs generated      = 0
 704 Number of switches generated = 0
 705 Number of labels             = 0
 706 Number of gotos              = 0
 707 Adaptive matching            = enabled
 708 Fast string matching         = disabled
 709 Inline downcasts             = enabled
 710 --------------------------------------------------------------------------
 711 */