prop-src/matchcom.ph

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  This file describes the interface to the pattern matching compiler.
   4 //
   5 ///////////////////////////////////////////////////////////////////////////////
   6 #ifndef match_compiler_h
   7 #define match_compiler_h
   8
   9 #include "ir.h"
  10 #include "ast.h"
  11 #include "patenv.h"
  12 #include "hashtab.h"
  13 #include "labelgen.h"
  14 #include "codegen.h"
  15
  16 ///////////////////////////////////////////////////////////////////////////////
  17 //
  18 //  Forward type declarations.
  19 //
  20 ///////////////////////////////////////////////////////////////////////////////
  21 class BitSet;       // bit sets
  22
  23 ///////////////////////////////////////////////////////////////////////////////
  24 //
  25 //  Pattern matching decision tree (dag)
  26 //
  27 ///////////////////////////////////////////////////////////////////////////////
  28 struct MatchBase : public MEM
  29 {
  30    int shared; Id label;
  31    MatchBase();
  32 };
  33
  34 datatype Match : public MatchBase =
  35      FAILmatch
  36    | SUCCESSmatch   (int, MatchRule)
  37    | SUCCESSESmatch (int, BitSet *, MatchRules)
  38    | COSTmatch      (int, Cost [], BitSet *, MatchRules)
  39    | GUARDmatch     (Exp, Match, Match)
  40    | LITERALmatch   (Pos, Exp, Literal [], int, Match [], Match)
  41    | RANGEmatch     (Pos, Exp, int, int, Match, Match)
  42    | CONSmatch      (Pos, Exp, Ty, Ty, int, Match [], Match)
  43      // special nodes
  44    | TREECOSTmatch  (Match, BitSet *, MatchRules)
  45    | TREELABELmatch (Match, Ty, Ty, int)
  46    | DONTCAREmatch                    // unused alternative
  47    | BACKEDGEmatch  (int, Id, Match)  // used for forming loops
  48
  49 ///////////////////////////////////////////////////////////////////////////////
  50 //
  51 //  Cost of a pattern matching/rewrite rule
  52 //
  53 ///////////////////////////////////////////////////////////////////////////////
  54 and Cost : MEM = NOcost                   // zero cost
  55                | EXPcost (Exp,Ty = NOty)  // cost is a function
  56                | INTcost (int)            // cost is an integer
  57
  58 ///////////////////////////////////////////////////////////////////////////////
  59 //
  60 //  Position element (for use during pattern matching compilation.)
  61 //
  62 ///////////////////////////////////////////////////////////////////////////////
  63 and  Pos : MEM = POSzero
  64                | POSinfinity
  65                | POSint      (int, Pos)
  66                | POSlabel    (Id,  Pos)
  67                | POSadaptive (int, int [], Pos)
  68 ;
  69
  70 ///////////////////////////////////////////////////////////////////////////////
  71 //
  72 //  Pretty printer for matching trees.
  73 //
  74 ///////////////////////////////////////////////////////////////////////////////
  75 extern std::ostream& operator << (std::ostream&, Match);
  76
  77 ///////////////////////////////////////////////////////////////////////////////
  78 //
  79 //  Function to reverse the polarity of a pattern.
  80 //
  81 ///////////////////////////////////////////////////////////////////////////////
  82 extern Polarity rev (Polarity);
  83
  84 ///////////////////////////////////////////////////////////////////////////////
  85 //
  86 //  Function to compute the match variables for a list of match expressions.
  87 //  Match variables are temporaries generated for complex expressions to
  88 //  prevent redundent evaluations.
  89 //
  90 ///////////////////////////////////////////////////////////////////////////////
  91 extern void compute_match_variables (MatchExps);
  92
  93 ///////////////////////////////////////////////////////////////////////////////
  94 //
  95 //  Function to convert a string into an array pattern.  This converts string
  96 //  patterns to be decomposed into a web of character patterns, allowing
  97 //  (potentially) more efficient matching.
  98 //
  99 ///////////////////////////////////////////////////////////////////////////////
 100 extern Pats make_string_pattern (const char *);
 101
 102 ///////////////////////////////////////////////////////////////////////////////
 103 //
 104 //  Functions to decorate the pattern for projection bindings.
 105 //  These are called to annotate a pattern with pattern variable bindings.
 106 //  The new bindings are entered into the pattern variable environments.
 107 //  These are called from the parser.
 108 //
 109 ///////////////////////////////////////////////////////////////////////////////
 110 extern void decor (Pat, Exp, Polarity, Bool, PatternVarEnv&, int&);
 111 extern void decor (MatchExps, Pat, Polarity, Bool, PatternVarEnv&, int&);
 112 extern void decor (MatchExps&, Pat, PatternVarEnv&, int&, int = -1);
 113
 114 ///////////////////////////////////////////////////////////////////////////////
 115 //
 116 //  Functions to decorate the pattern for attribute and cost bindings
 117 //  inside rewrite rules.  These are also called from the parser.
 118 //
 119 ///////////////////////////////////////////////////////////////////////////////
 120 extern int decor_rewrite (Pat,  int, int, PatternVarEnv&);
 121 extern int decor_rewrite (Pats, int, int, PatternVarEnv&);
 122 extern int decor_rewrite (Pat,  int, PatternVarEnv&);
 123
 124 ///////////////////////////////////////////////////////////////////////////////
 125 //
 126 //  Auxiliary function to retrieve the position vector of a decision tree.
 127 //  This is used during the pattern matching compilation process.
 128 //
 129 ///////////////////////////////////////////////////////////////////////////////
 130 extern Pos get_pos (Match);
 131
 132 ///////////////////////////////////////////////////////////////////////////////
 133 //
 134 //  Auxiliary functions to compute information on a matching tree.
 135 //  These are used during the pattern matching compilation process to
 136 //  eliminate redundant tests and for error detection.
 137 //
 138 ///////////////////////////////////////////////////////////////////////////////
 139 Bool          refutable         (Match);          // Is the pattern refutable?
 140 void          matchables        (Match, BitSet&); // Set of matchable rules.
 141 void          always_matchables (Match, BitSet&); // Set of always matching
 142 const BitSet& always_matchables (Match, int);     // rules.
 143
 144 ///////////////////////////////////////////////////////////////////////////////
 145 //
 146 //  Functions to perform substitutions on expressions.
 147 //  All INDexp(i) nodes are substituted with the corresponding replacement.
 148 //
 149 ///////////////////////////////////////////////////////////////////////////////
 150 extern Exp     subst (Exp,     Exp replacements[]);
 151 extern Exps    subst (Exps,    Exp replacements[]);
 152 extern LabExps subst (LabExps, Exp replacements[]);
 153
 154 ///////////////////////////////////////////////////////////////////////////////
 155 //
 156 //  Hashing and equality for literals.
 157 //  These are used in the matching tree -> dag conversion process.
 158 //
 159 ///////////////////////////////////////////////////////////////////////////////
 160 extern unsigned int literal_hash  (HashTable::Key);
 161 extern Bool         literal_equal (HashTable::Key, HashTable::Key);
 162
 163 ///////////////////////////////////////////////////////////////////////////////
 164 //
 165 //  Hashing and equality for position vectors.
 166 //  These are used in the matching tree -> dag conversion process.
 167 //
 168 ///////////////////////////////////////////////////////////////////////////////
 169 extern unsigned int pos_hash  (HashTable::Key);
 170 extern Bool         pos_equal (HashTable::Key, HashTable::Key);
 171
 172 ///////////////////////////////////////////////////////////////////////////////
 173 //
 174 //  Functions to check for refutability of a pattern.  These are used
 175 //  in the pattern sindexing scheme.
 176 //
 177 ///////////////////////////////////////////////////////////////////////////////
 178 extern Bool is_refutable  (Pat);
 179 extern Bool is_refutable  (Pats);
 180 extern Bool is_refutable  (LabPats);
 181
 182 ///////////////////////////////////////////////////////////////////////////////
 183 //
 184 //  The current index map.  This map is computed when using the adaptive
 185 //  pattern matching scheme.
 186 //
 187 ///////////////////////////////////////////////////////////////////////////////
 188 extern HashTable * current_index_map;
 189
 190 ///////////////////////////////////////////////////////////////////////////////
 191 //
 192 //  Methods for compute indexing information of a pattern.  These are
 193 //  used in the adaptive scheme.
 194 //
 195 ///////////////////////////////////////////////////////////////////////////////
 196 extern void indexing (int, Pat, Pos, HashTable&);
 197 extern void indexing (int, Pats, Pos, HashTable&);
 198 extern void indexing (MatchRules, HashTable&);
 199
 200 extern       Bool same_selectors;
 201
 202 extern Exp select (Exp, Cons, Ty = NOty);
 203
 204 ///////////////////////////////////////////////////////////////////////////////
 205 //
 206 //   Equality on expressions.
 207 //
 208 ///////////////////////////////////////////////////////////////////////////////
 209 extern Bool equal (Exp, Exp);
 210 extern Bool equal (Exps, Exps);
 211 extern Bool equal (LabExps, LabExps);
 212
 213 ///////////////////////////////////////////////////////////////////////////////
 214 //
 215 //  Substitution functions on patterns.  These are used to implement
 216 //  pattern laws.
 217 //
 218 ///////////////////////////////////////////////////////////////////////////////
 219 extern Pat     subst (Pat,     Pat [], Bool);
 220 extern Pats    subst (Pats,    Pat [], Bool);
 221 extern LabPats subst (LabPats, Pat [], Bool);
 222
 223 ///////////////////////////////////////////////////////////////////////////////
 224 //
 225 //  Methods to translate a match tree into an anotated tree with tree parsing
 226 //  cost.
 227 //
 228 ///////////////////////////////////////////////////////////////////////////////
 229 extern Match translate_treecost (Match, MatchRules);
 230
 231 ///////////////////////////////////////////////////////////////////////////////
 232 //
 233 //  Methods to enter and lookup a pattern constructor.
 234 //  These interact with the pattern/constructor environment.
 235 //  Called from the parser.
 236 //
 237 ///////////////////////////////////////////////////////////////////////////////
 238 extern Pat  apply_pat  (Pat, Pat);
 239
 240 ///////////////////////////////////////////////////////////////////////////////
 241 //
 242 //  The following is the interface definition of the pattern matching compiler.
 243 //
 244 ///////////////////////////////////////////////////////////////////////////////
 245 class MatchCompiler : virtual public CodeGen {
 246
 247    MatchCompiler(const MatchCompiler&);    // no copy constructor
 248    void operator = (const MatchCompiler&); // no assignment
 249
 250 protected:
 251    LabelGen vars, labels;                         // labels generators
 252    int merges, ifs, switches, gotos, goto_labels; // match compiler statistics
 253    MatchOptions     current_options;
 254    MatchRule        current_rule;
 255
 256    static HashTable quark_map;
 257    static LabelGen  quark_labels;
 258
 259 public:
 260    ////////////////////////////////////////////////////////////////////////////
 261    //
 262    //  Constructor and destructor
 263    //
 264    ////////////////////////////////////////////////////////////////////////////
 265             MatchCompiler();
 266    virtual ~MatchCompiler();
 267
 268    static Id quark_name(Id);
 269
 270    ////////////////////////////////////////////////////////////////////////////
 271    //
 272    //  Methods to compute the selection/projection function from a datatype
 273    //  domain.  This is used in the pattern binding annotation process.
 274    //
 275    ////////////////////////////////////////////////////////////////////////////
 276    static Exp untag(Exp, Ty);
 277    static Exp untag_one(Exp, Cons);
 278    static Exp make_select (Exp, Cons, Ty = NOty, Id = 0);
 279    static Exp tag_name_of (Cons, Bool normalized);
 280
 281 protected:
 282    ////////////////////////////////////////////////////////////////////////////
 283    //
 284    //  Methods to compile pattern matching.
 285    //
 286    ////////////////////////////////////////////////////////////////////////////
 287
 288    ////////////////////////////////////////////////////////////////////////////
 289    //
 290    //  Methods to for translation a pattern into a pattern matching tree.
 291    //
 292    ////////////////////////////////////////////////////////////////////////////
 293    Match trans          (Pat, Pos, Bool, Match, Match);
 294    Match trans          (Pats, int, Pos, Bool, Match, Match);
 295    Match trans          (Pats, Pos, Bool, Match, Match, int []);
 296    Match trans          (LabPats, Pos, Bool, Match, Match);
 297    Match trans_merge    (int, MatchRules, int, Cost *);
 298    Match trans_no_merge (int, int, MatchRules, int, Cost *);
 299
 300    ////////////////////////////////////////////////////////////////////////////
 301    //
 302    //  Methods to for tree composition/merging and tree to dag conversion.
 303    //
 304    ////////////////////////////////////////////////////////////////////////////
 305    Match compose        (Match, Match);
 306    Match merge          (Match, Match);
 307    Match make_dag       (Match, MatchOptions, MatchRules);
 308    Match match_of       (int, MatchRules, MatchOptions);
 309
 310    ////////////////////////////////////////////////////////////////////////////
 311    //
 312    //  Methods for generating high level statements and trace instrumentation.
 313    //
 314    ////////////////////////////////////////////////////////////////////////////
 315    void gen_match_stmt              (MatchExps, MatchRules,
 316                                      MatchOptions = MATCHnone, Ty = NOty);
 317    void gen_fun_def                 (FunDefs);
 318    void gen_match_variables         (MatchExps, Ty);
 319    void gen                         (Match, MatchOptions=MATCHnone, Ty=NOty);
 320    void gen_matchall_suffix         (int, Match, MatchRules, Bool);
 321    void gen_match_cost_minimization (int, Match, MatchRules, Bool);
 322    void gen_success_match           (int, const BitSet *, MatchRules);
 323    void gen_cost_success_match      (int, const BitSet *, MatchRules);
 324    virtual void gen_treecost_match  (Match, const BitSet *, MatchRules) = 0;
 325    virtual void gen_treelabel_match (Match, Ty, Ty, int) = 0;
 326
 327    void instrument_trace            (MatchRules);
 328
 329    ////////////////////////////////////////////////////////////////////////////
 330    //
 331    //  Method for generating range matching
 332    //
 333    ////////////////////////////////////////////////////////////////////////////
 334    void gen_range_match (Pos, Exp, int, int, Match, Match, Match);
 335
 336    ////////////////////////////////////////////////////////////////////////////
 337    //
 338    //  Method for generating view matching
 339    //
 340    ////////////////////////////////////////////////////////////////////////////
 341    void gen_view_match (Id, Exp, Exp, int, Cons [], Match [], Match,
 342                         TyOpt, TyQual);
 343
 344    ////////////////////////////////////////////////////////////////////////////
 345    //
 346    //  Low level methods for specific pattern matching constructs:
 347    //  C/C++ switches, binary search on literals, regular expression matching,
 348    //  and quarks matching code.
 349    //
 350    ////////////////////////////////////////////////////////////////////////////
 351    void gen_switch  (Id, Exp, Ty, int, Cons [], Match [], Match, int shared,
 352                      Bool, Bool, TyOpt, Bool);
 353    void gen_binary_search_on_literals(Exp, int, Literal [], Match [], Match);
 354    void gen_regexp_match
 355         (Exp, int, Literal [], Match [], Match, MatchOptions, Ty);
 356    void gen_quark_match
 357         (Exp, int, Literal [], Match [], Match, MatchOptions);
 358
 359    ////////////////////////////////////////////////////////////////////////////
 360    //
 361    //  Methods to generating debugging code.
 362    //
 363    ////////////////////////////////////////////////////////////////////////////
 364    int current_rule_line () const;
 365    const char * current_rule_text () const;
 366
 367 private:
 368    ///////////////////////////////////////////////////////////////////////////////
 369    //
 370    //  Functions for allocating arrays of Literal and Match.
 371    //  Used during the pattern matching compilation process.
 372    //
 373    ///////////////////////////////////////////////////////////////////////////////
 374    Literal * Literals (int);
 375    Match *   Matches  (int);
 376 };
 377
 378 ///////////////////////////////////////////////////////////////////////////////
 379 //
 380 //  Object to mark the current rule
 381 //
 382 ///////////////////////////////////////////////////////////////////////////////
 383 class MarkCurrentRule {
 384    MarkCurrentRule();
 385    MarkCurrentRule(const MarkCurrentRule&);
 386    void operator = (const MarkCurrentRule&);
 387    MatchRule& current_rule;
 388    MatchRule  old_rule;
 389 protected:
 390    MarkCurrentRule(MatchRule&, MatchRule);
 391   ~MarkCurrentRule();
 392    friend class MatchCompiler;
 393    friend class RewritingCompiler;
 394 };
 395
 396 #endif