app/willard/paige.cc

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //  This file is generated automatically using Prop (version 2.3.5),
   3 //  last updated on Jun 18, 1997.
   4 //  The original source file is "paige.pcc".
   5 ///////////////////////////////////////////////////////////////////////////////
   6
   7 #define PROP_REWRITING_USED
   8 #define PROP_STRCMP_USED
   9 #define PROP_QUARK_USED
  10 #define PROP_TUPLE2_USED
  11 #include <propdefs.h>
  12 #line 1 "paige.pcc"
  13 #include <assert.h>
  14 #include <iostream.h>
  15 #include <fstream.h>
  16 #include <AD/pretty/postream.h>
  17 #include "paige.h"
  18 #include "willard-ast.h"
  19
  20 ///////////////////////////////////////////////////////////////////////////////
  21 //
  22 //  Constructor for the Paige/Goyal query transformer
  23 //
  24 ///////////////////////////////////////////////////////////////////////////////
  25 PaigeGoyal::PaigeGoyal() : log(*new ofstream), errlog(cerr)
  26 {  True     = LIT(BOOL(true));
  27    False    = LIT(BOOL(false));
  28    Zero     = LIT(INT(0));
  29    One      = LIT(INT(1));
  30    Two      = LIT(INT(2));
  31    EmptySet = GENERATOR(
  32 #line 19 "paige.pcc"
  33 #line 19 "paige.pcc"
  34 nil_1_
  35 #line 19 "paige.pcc"
  36 #line 19 "paige.pcc"
  37 ,
  38 #line 19 "paige.pcc"
  39 #line 19 "paige.pcc"
  40 nil_1_
  41 #line 19 "paige.pcc"
  42 #line 19 "paige.pcc"
  43 ,Zero);
  44    new_name = 0;
  45    subquery_names =
  46 #line 21 "paige.pcc"
  47 #line 21 "paige.pcc"
  48 nil_1_
  49 #line 21 "paige.pcc"
  50 #line 21 "paige.pcc"
  51 ;
  52    subqueries =
  53 #line 22 "paige.pcc"
  54 #line 22 "paige.pcc"
  55 nil_1_
  56 #line 22 "paige.pcc"
  57 #line 22 "paige.pcc"
  58 ;
  59 }
  60
  61 ///////////////////////////////////////////////////////////////////////////////
  62 //
  63 //  Destructor for the Paige/Goyal query transformer
  64 //
  65 ///////////////////////////////////////////////////////////////////////////////
  66 PaigeGoyal::~PaigeGoyal()
  67 {
  68 }
  69
  70 ///////////////////////////////////////////////////////////////////////////////
  71 //
  72 //  Method to add a subquery
  73 //
  74 ///////////////////////////////////////////////////////////////////////////////
  75 void PaigeGoyal::add_subquery(Id x, Exp e)
  76 {  // PrettyOStream S;
  77    // S << "Subquery: " << x << '=' << e << '\n';
  78    subquery_names =
  79 #line 42 "paige.pcc"
  80 #line 42 "paige.pcc"
  81 list_1_(x,subquery_names)
  82 #line 42 "paige.pcc"
  83 #line 42 "paige.pcc"
  84 ;
  85    subqueries     =
  86 #line 43 "paige.pcc"
  87 #line 43 "paige.pcc"
  88 list_1_(e,subqueries)
  89 #line 43 "paige.pcc"
  90 #line 43 "paige.pcc"
  91 ;
  92 }
  93 Bool PaigeGoyal::has_subqueries() const { return subqueries !=
  94 #line 45 "paige.pcc"
  95 #line 45 "paige.pcc"
  96 nil_1_
  97 #line 45 "paige.pcc"
  98 #line 45 "paige.pcc"
  99 ; }
 100
 101 ///////////////////////////////////////////////////////////////////////////////
 102 //
 103 //  Method to collect subqueries into a LET
 104 //
 105 ///////////////////////////////////////////////////////////////////////////////
 106 Exp PaigeGoyal::collect_subqueries(Exp exp)
 107 {  exp = make_let(subquery_names, subqueries, exp);
 108    subquery_names =
 109 #line 54 "paige.pcc"
 110 #line 54 "paige.pcc"
 111 nil_1_
 112 #line 54 "paige.pcc"
 113 #line 54 "paige.pcc"
 114 ;
 115    subqueries     =
 116 #line 55 "paige.pcc"
 117 #line 55 "paige.pcc"
 118 nil_1_
 119 #line 55 "paige.pcc"
 120 #line 55 "paige.pcc"
 121 ;
 122    return exp;
 123 }
 124
 125 ///////////////////////////////////////////////////////////////////////////////
 126 //
 127 //  Method to make a nested LET
 128 //
 129 ///////////////////////////////////////////////////////////////////////////////
 130 Exp PaigeGoyal::make_let(Ids xs, Exps es, Exp exp)
 131 {
 132 #line 65 "paige.pcc"
 133 #line 71 "paige.pcc"
 134 {
 135    for (;;) {
 136       if (xs) {
 137          if (es) {
 138 #line 67 "paige.pcc"
 139           Id  x = xs->_1;
 140                  Exp e = es->_1;
 141                  exp = LET(x,e,exp);
 142                  xs = xs->_2; es = es->_2;
 143
 144 #line 71 "paige.pcc"
 145          } else { goto L1; }
 146       } else { goto L1; }
 147    }
 148    L1:;
 149 }
 150 #line 72 "paige.pcc"
 151 #line 72 "paige.pcc"
 152
 153    return exp;
 154 }
 155
 156 ///////////////////////////////////////////////////////////////////////////////
 157 //
 158 //  Methods to define/lookup the range of a variable
 159 //
 160 ///////////////////////////////////////////////////////////////////////////////
 161 void PaigeGoyal::define_range(Id x, Exp e) { var_range.insert(x,e); }
 162 void PaigeGoyal::define_range(Ids xs, Exps es)
 163 {  Ids  ids = xs;
 164    Exps exps = es;
 165
 166 #line 85 "paige.pcc"
 167 #line 86 "paige.pcc"
 168 {
 169    for (;;) {
 170       if (ids) {
 171          if (exps) {
 172 #line 86 "paige.pcc"
 173            define_range(ids->_1,exps->_1); ids = ids->_2; exps = exps->_2;
 174 #line 86 "paige.pcc"
 175          } else { goto L2; }
 176       } else { goto L2; }
 177    }
 178    L2:;
 179 }
 180 #line 87 "paige.pcc"
 181 #line 87 "paige.pcc"
 182
 183    if (ids !=
 184 #line 88 "paige.pcc"
 185 #line 88 "paige.pcc"
 186 nil_1_
 187 #line 88 "paige.pcc"
 188 #line 88 "paige.pcc"
 189  || exps !=
 190 #line 88 "paige.pcc"
 191 #line 88 "paige.pcc"
 192 nil_1_
 193 #line 88 "paige.pcc"
 194 #line 88 "paige.pcc"
 195 )
 196       errlog << "Arity mismatch in " << xs << "in" << es << ::newline;
 197 }
 198
 199 Exp  PaigeGoyal::range_of(Id x)
 200 {  assert(var_range.contains(x));
 201    return var_range[x];
 202 }
 203
 204 ///////////////////////////////////////////////////////////////////////////////
 205 //
 206 //  Method to print messages
 207 //
 208 ///////////////////////////////////////////////////////////////////////////////
 209 void PaigeGoyal::message(const char * msg, Exp e)
 210 {  log << ::indent << e << ::newline << ::newline << ::unindent
 211        << '[' << msg << ']' << ::newline << ::newline;
 212 }
 213
 214 void PaigeGoyal::error(const char * msg, Exp e)
 215 {  errlog << '[' << "ERROR:" << msg << ']' << ::newline << ::indent
 216           << e << ::newline << ::unindent;
 217 }
 218
 219 void PaigeGoyal::set_log(ostream& f) { log.set_stream(f); }
 220 void PaigeGoyal::set_error(ostream& f) { errlog.set_stream(f); }
 221
 222 ///////////////////////////////////////////////////////////////////////////////
 223 //
 224 //  Method to add an edge into the query graph
 225 //
 226 ///////////////////////////////////////////////////////////////////////////////
 227 void PaigeGoyal::add_edge(Id x, Id y)
 228 {  if (parent.contains(y))
 229    {  Id z = parent[y];
 230       if (x != z)
 231          errlog << "Edge: " << x << "->" << y << "conflicts with"
 232                 << z << "->" << y << "in the query graph\n";
 233    }
 234    parent.insert(y,x);
 235 }
 236
 237 Bool PaigeGoyal::has_edge(Id x, Id y) const
 238 {  if (! parent.contains(y)) return false;
 239    return parent[y] == x;
 240 }
 241
 242 void PaigeGoyal::add_edge_query(Id x, Id y, Exp q)
 243 {
 244    edge_queries.insert(
 245 #line 137 "paige.pcc"
 246 #line 137 "paige.pcc"
 247 mkTuple2(x,y)
 248 #line 137 "paige.pcc"
 249 #line 137 "paige.pcc"
 250 ,q);
 251 }
 252
 253 ///////////////////////////////////////////////////////////////////////////////
 254 //
 255 //  Method to compute the transitive closure of the query graph
 256 //
 257 ///////////////////////////////////////////////////////////////////////////////
 258 void PaigeGoyal::compute_transitive_closure()
 259 {  foreach (i,parent)
 260    {  parent_closure.insert(parent.key(i),parent.value(i));
 261    }
 262 }
 263
 264 ///////////////////////////////////////////////////////////////////////////////
 265 //
 266 //  Methods to push/pop from the quantifier stack
 267 //
 268 ///////////////////////////////////////////////////////////////////////////////
 269 void PaigeGoyal::push_quantifier(Id x) { quantifier_vars.push(x); }
 270 void PaigeGoyal::push_quantifier(Ids xs)
 271 {
 272 #line 158 "paige.pcc"
 273 #line 158 "paige.pcc"
 274 {
 275    for (;;) {
 276       if (xs) {
 277 #line 158 "paige.pcc"
 278         push_quantifier(xs->_1); xs = xs->_2;
 279 #line 158 "paige.pcc"
 280       } else { goto L3; }
 281    }
 282    L3:;
 283 }
 284 #line 158 "paige.pcc"
 285 #line 158 "paige.pcc"
 286  }
 287 void PaigeGoyal::pop_quantifier(Id x) { quantifier_vars.pop(); }
 288 void PaigeGoyal::pop_quantifier(Ids xs)
 289 {
 290 #line 161 "paige.pcc"
 291 #line 161 "paige.pcc"
 292 {
 293    for (;;) {
 294       if (xs) {
 295 #line 161 "paige.pcc"
 296         pop_quantifier(xs->_1); xs = xs->_2;
 297 #line 161 "paige.pcc"
 298       } else { goto L4; }
 299    }
 300    L4:;
 301 }
 302 #line 161 "paige.pcc"
 303 #line 161 "paige.pcc"
 304  }
 305
 306 ///////////////////////////////////////////////////////////////////////////////
 307 //
 308 //  Method to print the query graph
 309 //
 310 ///////////////////////////////////////////////////////////////////////////////
 311 void PaigeGoyal::print_query_graph()
 312 {  log << ::tab << "[Query Graph]" << ::newline << ::indent;
 313    foreach (i,parent)
 314    {  Id x = parent.value(i);
 315       Id y = parent.key(i);
 316       log << ::tab << "edge" << x << "->" << y;
 317       if (edge_queries.contains(
 318 #line 174 "paige.pcc"
 319 #line 174 "paige.pcc"
 320 mkTuple2(x,y)
 321 #line 174 "paige.pcc"
 322 #line 174 "paige.pcc"
 323 ))
 324           log << '\t' << edge_queries[
 325 #line 175 "paige.pcc"
 326 #line 175 "paige.pcc"
 327 mkTuple2(x,y)
 328 #line 175 "paige.pcc"
 329 #line 175 "paige.pcc"
 330 ];
 331       log << ::newline;
 332    }
 333    log << ::unindent;
 334 }
 335
 336 ///////////////////////////////////////////////////////////////////////////////
 337 //
 338 //  Main method to decompose a query
 339 //
 340 ///////////////////////////////////////////////////////////////////////////////
 341 Exp PaigeGoyal::decompose(Exp e)
 342 {  subqueries =
 343 #line 187 "paige.pcc"
 344 #line 187 "paige.pcc"
 345 nil_1_
 346 #line 187 "paige.pcc"
 347 #line 187 "paige.pcc"
 348 ;
 349    do {
 350       changed = false;
 351       e = remove_duplicate_names(e);
 352       e = phase1(e);   // DNF construction
 353       e = construct_query_graph(e); // query graph construction
 354       e = phase2(e);   // quantifier elimination
 355       e = phase3(e);   // disjunction removal
 356       e = phase4(e);   // conjunction removal
 357       e = projection_recognition(e);
 358       e = phase5(e);
 359       if (changed) message("Reiterating the transformation",e);
 360    } while (changed);
 361    return e;
 362 }
 363 #line 202 "paige.pcc"
 364 /*
 365 ------------------------------- Statistics -------------------------------
 366 Merge matching rules         = yes
 367 Number of DFA nodes merged   = 8
 368 Number of ifs generated      = 6
 369 Number of switches generated = 0
 370 Number of labels             = 0
 371 Number of gotos              = 0
 372 Adaptive matching            = disabled
 373 Fast string matching         = disabled
 374 Inline downcasts             = disabled
 375 --------------------------------------------------------------------------
 376 */