prop-src/indexing.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 "indexing.pcc".
   5 ///////////////////////////////////////////////////////////////////////////////
   6
   7 #line 1 "indexing.pcc"
   8 ///////////////////////////////////////////////////////////////////////////////
   9 //  Indexing optimizations for pattern matching.
  10 //
  11 //  The following indexing schemes is largely inspired by the work of
  12 //  Sekar, Ramesh and Ramakrishnan in ``Adaptive Pattern Matching.''
  13 //  Techreport, SUNY at Stony Brook (year 91+ but unknown).
  14 //
  15 //  Intuitively, an index is the next position of a pattern that must be
  16 //  inspected to determine a match(Levy and Huet).  Given a set of
  17 //  prioritized patterns, at least an index must exist at each position.
  18 //  The algorithm of SRR attempts to locate the index at each position
  19 //  when constructing the the DFA-like matching automata.
  20 //
  21 //  In the previous algorithm I've implemented, merging of matching trees at
  22 //  identical positions are performed and the resulting automaton guarantees
  23 //  that the same position is only examined once.  This is an improvement
  24 //  over Wadler's algorithm, which may examine the same position more than
  25 //  once in a match.  However, we may examine a position even if it is not
  26 //  needed.
  27 //
  28 //    For example, in
  29 //
  30 //       f(_,a,b):
  31 //       f(a,a,_):
  32 //       f(_,b,c):
  33 //
  34 //   We exam position 1, 2, 3 in sequence in term f even though it is
  35 // best to exam position 2 first.
  36 //
  37 //  I think my algorithm is similar to the one by Graf.  In any case,
  38 //  My, Graf's and Wadler's algorithms all use a fixed traversal order
  39 //  (usually left-to-right).  However, the intuition is that in many instances
  40 //  it is best if the traversal order *adapts* itself according to the
  41 //  pattern.  This is the essential idea of SRR's algorithm.
  42 //
  43 //  Sekar et al. have shown that constructing a DFA-like matching
  44 //  automata can be exponential in time and space.  They have
  45 //  developed a polynomial time algorithm for computing indices for untyped
  46 //  terms.  Unfortunately, in our typed case the time complexity of index
  47 //  computation is co-NP.
  48 //
  49 //  So we'll just use a few heuristics to compute something close to
  50 //  the notion of an index, and cross our fingers and hope for the best.
  51 ///////////////////////////////////////////////////////////////////////////////
  52 #include "ir.h"
  53 #include "ast.h"
  54 #include "matchcom.h"
  55 #include "hashtab.h"
  56
  57 ///////////////////////////////////////////////////////////////////////////////
  58 //
  59 //  Hash function on position list
  60 //
  61 ///////////////////////////////////////////////////////////////////////////////
  62 unsigned int pos_hash (HashTable::Key p)
  63 {  Pos pos = (Pos)p;
  64    unsigned int h = 37;
  65
  66 #line 58 "indexing.pcc"
  67 #line 63 "indexing.pcc"
  68 {
  69    for (;;) {
  70       if (boxed(pos)) {
  71          switch (untagp(pos)) {
  72             case a_Pos::tag_POSint: {
  73 #line 61 "indexing.pcc"
  74               h += ((Pos_POSint *)pos)->_1; pos = ((Pos_POSint *)pos)->_2;
  75 #line 61 "indexing.pcc"
  76                } break;
  77             case a_Pos::tag_POSlabel: {
  78 #line 62 "indexing.pcc"
  79               h += (unsigned int)((Pos_POSlabel *)derefp(pos))->_1; pos = ((Pos_POSlabel *)derefp(pos))->_2;
  80 #line 62 "indexing.pcc"
  81                } break;
  82             default: {
  83 #line 63 "indexing.pcc"
  84               h += ((Pos_POSadaptive *)derefp(pos))->_1 + 437; pos = ((Pos_POSadaptive *)derefp(pos))->_3;
  85 #line 63 "indexing.pcc"
  86                } break;
  87          }
  88       } else {
  89          if (pos) {
  90
  91 #line 60 "indexing.pcc"
  92            return h + 83;
  93 #line 60 "indexing.pcc"
  94          } else {
  95
  96 #line 59 "indexing.pcc"
  97            return h;
  98 #line 59 "indexing.pcc"
  99          }
 100       }
 101    }
 102 }
 103 #line 64 "indexing.pcc"
 104 #line 64 "indexing.pcc"
 105
 106 }
 107
 108 ///////////////////////////////////////////////////////////////////////////////
 109 //
 110 //  Checks if a pattern is refutable.
 111 //
 112 ///////////////////////////////////////////////////////////////////////////////
 113 Bool is_refutable(Pat pat)
 114 {
 115 #line 73 "indexing.pcc"
 116 #line 98 "indexing.pcc"
 117 {
 118    for (;;) {
 119       if (pat) {
 120          switch (pat->tag__) {
 121             case a_Pat::tag_WILDpat: {
 122                L3:;
 123 #line 74 "indexing.pcc"
 124               return false;
 125 #line 74 "indexing.pcc"
 126                } break;
 127             case a_Pat::tag_IDpat: {
 128                if (((Pat_IDpat *)pat)->_3) {
 129                   L4:;
 130 #line 76 "indexing.pcc"
 131                  return true;
 132 #line 76 "indexing.pcc"
 133                } else { goto L3; }
 134                } break;
 135             case a_Pat::tag_CONSpat: {
 136                if (((Pat_CONSpat *)pat)->CONSpat) {
 137                   if (((Pat_CONSpat *)pat)->CONSpat->alg_ty) {
 138                      switch (((Pat_CONSpat *)pat)->CONSpat->alg_ty->tag__) {
 139                         case a_Ty::tag_TYCONty: {
 140                            if (boxed(((Ty_TYCONty *)((Pat_CONSpat *)pat)->CONSpat->alg_ty)->_1)) {
 141                               switch (((Ty_TYCONty *)((Pat_CONSpat *)pat)->CONSpat->alg_ty)->_1->tag__) {
 142                                  case a_TyCon::tag_DATATYPEtycon: {
 143 #line 92 "indexing.pcc"
 144                                   return ((((TyCon_DATATYPEtycon *)((Ty_TYCONty *)((Pat_CONSpat *)pat)->CONSpat->alg_ty)->_1)->unit + ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)((Pat_CONSpat *)pat)->CONSpat->alg_ty)->_1)->arg > 1) || (((TyCon_DATATYPEtycon *)((Ty_TYCONty *)((Pat_CONSpat *)pat)->CONSpat->alg_ty)->_1)->qualifiers & QUALextensible));
 145 #line 92 "indexing.pcc"
 146                                     } break;
 147                                  default: {
 148                                     L5:;
 149 #line 98 "indexing.pcc"
 150                                    bug("is_refutable()");
 151 #line 98 "indexing.pcc"
 152                                     } break;
 153                               }
 154                            } else { goto L5; }
 155                            } break;
 156                         default: { goto L5; } break;
 157                      }
 158                   } else { goto L5; }
 159                } else { goto L5; }
 160                } break;
 161             case a_Pat::tag_APPpat: {
 162 #line 93 "indexing.pcc"
 163               return is_refutable(((Pat_APPpat *)pat)->_1) || is_refutable(((Pat_APPpat *)pat)->_2);
 164 #line 93 "indexing.pcc"
 165                } break;
 166             case a_Pat::tag_TYPEDpat: {
 167 #line 78 "indexing.pcc"
 168               pat = ((Pat_TYPEDpat *)pat)->_1;
 169 #line 78 "indexing.pcc"
 170                } break;
 171             case a_Pat::tag_ASpat: {
 172                if (((Pat_ASpat *)pat)->_4) { goto L4; } else {
 173 #line 77 "indexing.pcc"
 174                  pat = ((Pat_ASpat *)pat)->_2;
 175 #line 77 "indexing.pcc"
 176                }
 177                } break;
 178             case a_Pat::tag_CONTEXTpat: {
 179 #line 86 "indexing.pcc"
 180               return is_refutable(((Pat_CONTEXTpat *)pat)->_2);
 181 #line 86 "indexing.pcc"
 182                } break;
 183             case a_Pat::tag_ARRAYpat: {
 184 #line 82 "indexing.pcc"
 185               return is_refutable(((Pat_ARRAYpat *)pat)->_1);
 186 #line 82 "indexing.pcc"
 187                } break;
 188             case a_Pat::tag_TUPLEpat: {
 189 #line 81 "indexing.pcc"
 190               return is_refutable(((Pat_TUPLEpat *)pat)->TUPLEpat);
 191 #line 81 "indexing.pcc"
 192                } break;
 193             case a_Pat::tag_RECORDpat: {
 194 #line 85 "indexing.pcc"
 195               return is_refutable(((Pat_RECORDpat *)pat)->_1);
 196 #line 85 "indexing.pcc"
 197                } break;
 198             case a_Pat::tag_LISTpat: {
 199 #line 95 "indexing.pcc"
 200              if (is_refutable(((Pat_LISTpat *)pat)->head)) return true;
 201                pat = ((Pat_LISTpat *)pat)->tail;
 202
 203 #line 97 "indexing.pcc"
 204                } break;
 205             case a_Pat::tag_VECTORpat: {
 206 #line 84 "indexing.pcc"
 207               return is_refutable(((Pat_VECTORpat *)pat)->len) || is_refutable(((Pat_VECTORpat *)pat)->elements);
 208 #line 84 "indexing.pcc"
 209                } break;
 210             case a_Pat::tag_LOGICALpat: {
 211 #line 80 "indexing.pcc"
 212               return is_refutable(((Pat_LOGICALpat *)pat)->_2) || is_refutable(((Pat_LOGICALpat *)pat)->_3);
 213 #line 80 "indexing.pcc"
 214                } break;
 215             case a_Pat::tag_MARKEDpat: {
 216 #line 79 "indexing.pcc"
 217               pat = ((Pat_MARKEDpat *)pat)->_2;
 218 #line 79 "indexing.pcc"
 219                } break;
 220             case a_Pat::tag_LITERALpat:
 221             case a_Pat::tag_LEXEMEpat: { goto L4; } break;
 222             default: { goto L5; } break;
 223          }
 224       } else { goto L3; }
 225    }
 226 }
 227 #line 99 "indexing.pcc"
 228 #line 99 "indexing.pcc"
 229
 230 }
 231
 232 ///////////////////////////////////////////////////////////////////////////////
 233 //
 234 //  Is a pattern list refutable?
 235 //
 236 ///////////////////////////////////////////////////////////////////////////////
 237 Bool is_refutable(Pats pats)
 238 {  for_each (Pat, p, pats) if (is_refutable(p)) return true;
 239    return false;
 240 }
 241
 242 ///////////////////////////////////////////////////////////////////////////////
 243 //
 244 //  Is a labeled pattern list refutable?
 245 //
 246 ///////////////////////////////////////////////////////////////////////////////
 247 Bool is_refutable(LabPats pats)
 248 {  for_each (LabPat, p, pats) if (is_refutable(p.pat)) return true;
 249    return false;
 250 }
 251
 252 ///////////////////////////////////////////////////////////////////////////////
 253 //
 254 //  Method to compute the indices.
 255 //
 256 ///////////////////////////////////////////////////////////////////////////////
 257 void indexing(int priority, Pat pat, Pos pos, HashTable& index_map)
 258 {
 259 #line 128 "indexing.pcc"
 260 #line 146 "indexing.pcc"
 261 {
 262    for (;;) {
 263       if (pat) {
 264          switch (pat->tag__) {
 265             case a_Pat::tag_APPpat: {
 266                if (((Pat_APPpat *)pat)->_1) {
 267                   switch (((Pat_APPpat *)pat)->_1->tag__) {
 268                      case a_Pat::tag_CONSpat: {
 269                         if (((Pat_CONSpat *)((Pat_APPpat *)pat)->_1)->CONSpat) {
 270                            if (((Pat_CONSpat *)((Pat_APPpat *)pat)->_1)->CONSpat->alg_ty) {
 271                               switch (((Pat_CONSpat *)((Pat_APPpat *)pat)->_1)->CONSpat->alg_ty->tag__) {
 272                                  case a_Ty::tag_TYCONty: {
 273                                     if (boxed(((Ty_TYCONty *)((Pat_CONSpat *)((Pat_APPpat *)pat)->_1)->CONSpat->alg_ty)->_1)) {
 274                                        switch (((Ty_TYCONty *)((Pat_CONSpat *)((Pat_APPpat *)pat)->_1)->CONSpat->alg_ty)->_1->tag__) {
 275                                           case a_TyCon::tag_DATATYPEtycon: {
 276                                              if (((Pat_APPpat *)pat)->_2) {
 277 #line 136 "indexing.pcc"
 278                                               indexing(priority, ((Pat_APPpat *)pat)->_2, POSint(((Pat_CONSpat *)((Pat_APPpat *)pat)->_1)->CONSpat->tag + ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)((Pat_CONSpat *)((Pat_APPpat *)pat)->_1)->CONSpat->alg_ty)->_1)->unit, pos), index_map); return;
 279 #line 136 "indexing.pcc"
 280                                              } else { goto L6; }
 281                                              } break;
 282                                           default: { goto L6; } break;
 283                                        }
 284                                     } else { goto L6; }
 285                                     } break;
 286                                  default: { goto L6; } break;
 287                               }
 288                            } else { goto L6; }
 289                         } else { goto L6; }
 290                         } break;
 291                      default: { goto L6; } break;
 292                   }
 293                } else { goto L6; }
 294                } break;
 295             case a_Pat::tag_TYPEDpat: {
 296 #line 130 "indexing.pcc"
 297               pat = ((Pat_TYPEDpat *)pat)->_1;
 298 #line 130 "indexing.pcc"
 299                } break;
 300             case a_Pat::tag_ASpat: {
 301 #line 129 "indexing.pcc"
 302               pat = ((Pat_ASpat *)pat)->_2;
 303 #line 129 "indexing.pcc"
 304                } break;
 305             case a_Pat::tag_CONTEXTpat: {
 306 #line 132 "indexing.pcc"
 307               pat = ((Pat_CONTEXTpat *)pat)->_2;
 308 #line 132 "indexing.pcc"
 309                } break;
 310             case a_Pat::tag_ARRAYpat: {
 311 #line 138 "indexing.pcc"
 312               indexing(priority, ((Pat_ARRAYpat *)pat)->_1, pos, index_map); return;
 313 #line 138 "indexing.pcc"
 314                } break;
 315             case a_Pat::tag_TUPLEpat: {
 316 #line 137 "indexing.pcc"
 317               indexing(priority, ((Pat_TUPLEpat *)pat)->TUPLEpat, pos, index_map); return;
 318 #line 137 "indexing.pcc"
 319                } break;
 320             case a_Pat::tag_RECORDpat: {
 321 #line 142 "indexing.pcc"
 322              for_each(LabPat, p, ((Pat_RECORDpat *)pat)->_1)
 323                indexing(priority, p.pat, POSlabel(p.label,pos), index_map);
 324                return;
 325
 326 #line 145 "indexing.pcc"
 327                } break;
 328             case a_Pat::tag_VECTORpat: {
 329 #line 140 "indexing.pcc"
 330               indexing(priority,
 331 #line 140 "indexing.pcc"
 332 #line 140 "indexing.pcc"
 333                list_1_(((Pat_VECTORpat *)pat)->len,((Pat_VECTORpat *)pat)->elements)
 334 #line 140 "indexing.pcc"
 335 #line 140 "indexing.pcc"
 336                , pos, index_map); return;
 337 #line 140 "indexing.pcc"
 338                } break;
 339             case a_Pat::tag_LOGICALpat: {
 340 #line 146 "indexing.pcc"
 341               indexing(priority,((Pat_LOGICALpat *)pat)->_2,pos,index_map); pat = ((Pat_LOGICALpat *)pat)->_3;
 342 #line 146 "indexing.pcc"
 343                } break;
 344             case a_Pat::tag_MARKEDpat: {
 345 #line 131 "indexing.pcc"
 346               pat = ((Pat_MARKEDpat *)pat)->_2;
 347 #line 131 "indexing.pcc"
 348                } break;
 349             default: { goto L6; } break;
 350          }
 351       } else { goto L6; }
 352    }
 353    L6:;
 354 }
 355 #line 147 "indexing.pcc"
 356 #line 147 "indexing.pcc"
 357
 358 }
 359
 360 ///////////////////////////////////////////////////////////////////////////////
 361 //
 362 //  Method to compute the indices.
 363 //
 364 ///////////////////////////////////////////////////////////////////////////////
 365 void indexing(int priority, Pats pats, Pos pos, HashTable& index_map)
 366 {  int n;
 367    Pat Ps[32];
 368
 369    int i = 0;
 370    // initialize the pattern array
 371    {  for_each (Pat, p, pats) Ps[i++] = p; }
 372    n = i;
 373    if (n <= 0 || n > 32) return;
 374
 375    // compute the set of index positions for this pattern list
 376    unsigned long indices = 0;
 377    for (i = 0; i < n; i++)
 378       if (is_refutable(Ps[i])) indices |= 1 << i;
 379
 380    // Locate the position ranking
 381    HashTable::Entry * e = index_map.lookup(pos);
 382    int * ranks;
 383    if (e) {
 384       // Heuristic to update the ranks given new index and priority
 385       // informations.
 386       ranks = (int*)index_map.value(e);
 387
 388    } else {
 389       // Initialize the new ranking array.
 390       // Put all used positions in front and
 391       // the rest the the back.
 392       ranks = (int*)mem_pool[n * sizeof(int)];
 393       int j = 0;
 394       for (i = 0; i < n; i++) if (indices & (1 << i))     ranks[j++] = i;
 395       for (i = 0; i < n; i++) if (! (indices & (1 << i))) ranks[j++] = i;
 396       index_map.insert(pos, ranks);
 397    }
 398
 399    // Recursive on subcomponents, and insert an adaptive rank.
 400    for (i = 0; i < n; i++)
 401       indexing(priority, Ps[i], POSadaptive(i,ranks,pos), index_map);
 402 }
 403
 404 ///////////////////////////////////////////////////////////////////////////////
 405 //
 406 //  Method to compute the indices information for a set of pattern matching
 407 //  rules.
 408 //
 409 ///////////////////////////////////////////////////////////////////////////////
 410 void indexing (MatchRules rules, HashTable& index_map)
 411 {  int priority = 0;
 412    for_each (MatchRule, r, rules)
 413    {
 414 #line 203 "indexing.pcc"
 415 #line 207 "indexing.pcc"
 416 {
 417 #line 205 "indexing.pcc"
 418  indexing(priority, r->_2, POSzero, index_map);
 419    priority++;
 420
 421 #line 207 "indexing.pcc"
 422 }
 423 #line 208 "indexing.pcc"
 424 #line 208 "indexing.pcc"
 425
 426    }
 427 }
 428 #line 211 "indexing.pcc"
 429 /*
 430 ------------------------------- Statistics -------------------------------
 431 Merge matching rules         = yes
 432 Number of DFA nodes merged   = 201
 433 Number of ifs generated      = 14
 434 Number of switches generated = 8
 435 Number of labels             = 3
 436 Number of gotos              = 9
 437 Adaptive matching            = enabled
 438 Fast string matching         = disabled
 439 Inline downcasts             = enabled
 440 --------------------------------------------------------------------------
 441 */