app/willard/paige.pcc

   1 #include <assert.h>
   2 #include <iostream.h>
   3 #include <fstream.h>
   4 #include <AD/pretty/postream.h>
   5 #include "paige.ph"
   6 #include "willard-ast.ph"
   7
   8 ///////////////////////////////////////////////////////////////////////////////
   9 //
  10 //  Constructor for the Paige/Goyal query transformer
  11 //
  12 ///////////////////////////////////////////////////////////////////////////////
  13 PaigeGoyal::PaigeGoyal() : log(*new ofstream), errlog(cerr)
  14 {  True     = LIT(BOOL(true));
  15    False    = LIT(BOOL(false));
  16    Zero     = LIT(INT(0));
  17    One      = LIT(INT(1));
  18    Two      = LIT(INT(2));
  19    EmptySet = GENERATOR(#[],#[],Zero);
  20    new_name = 0;
  21    subquery_names = #[];
  22    subqueries = #[];
  23 }
  24
  25 ///////////////////////////////////////////////////////////////////////////////
  26 //
  27 //  Destructor for the Paige/Goyal query transformer
  28 //
  29 ///////////////////////////////////////////////////////////////////////////////
  30 PaigeGoyal::~PaigeGoyal()
  31 {
  32 }
  33
  34 ///////////////////////////////////////////////////////////////////////////////
  35 //
  36 //  Method to add a subquery
  37 //
  38 ///////////////////////////////////////////////////////////////////////////////
  39 void PaigeGoyal::add_subquery(Id x, Exp e)
  40 {  // PrettyOStream S;
  41    // S << "Subquery: " << x << '=' << e << '\n';
  42    subquery_names = #[ x ... subquery_names ];
  43    subqueries     = #[ e ... subqueries ];
  44 }
  45 Bool PaigeGoyal::has_subqueries() const { return subqueries != #[]; }
  46
  47 ///////////////////////////////////////////////////////////////////////////////
  48 //
  49 //  Method to collect subqueries into a LET
  50 //
  51 ///////////////////////////////////////////////////////////////////////////////
  52 Exp PaigeGoyal::collect_subqueries(Exp exp)
  53 {  exp = make_let(subquery_names, subqueries, exp);
  54    subquery_names = #[];
  55    subqueries     = #[];
  56    return exp;
  57 }
  58
  59 ///////////////////////////////////////////////////////////////////////////////
  60 //
  61 //  Method to make a nested LET
  62 //
  63 ///////////////////////////////////////////////////////////////////////////////
  64 Exp PaigeGoyal::make_let(Ids xs, Exps es, Exp exp)
  65 {  match while (xs) and (es) of
  66       #[a ... b], #[c ... d]:
  67       {  Id  x = a;
  68          Exp e = c;
  69          exp = LET(x,e,exp);
  70          xs = b; es = d;
  71       }
  72    end match;
  73    return exp;
  74 }
  75
  76 ///////////////////////////////////////////////////////////////////////////////
  77 //
  78 //  Methods to define/lookup the range of a variable
  79 //
  80 ///////////////////////////////////////////////////////////////////////////////
  81 void PaigeGoyal::define_range(Id x, Exp e) { var_range.insert(x,e); }
  82 void PaigeGoyal::define_range(Ids xs, Exps es)
  83 {  Ids  ids = xs;
  84    Exps exps = es;
  85    match while (ids) and (exps) of
  86       #[x ... xs], #[e ... es]: { define_range(x,e); ids = xs; exps = es; }
  87    end match;
  88    if (ids != #[] || exps != #[])
  89       errlog << "Arity mismatch in " << xs << "in" << es << ::newline;
  90 }
  91
  92 Exp  PaigeGoyal::range_of(Id x)
  93 {  assert(var_range.contains(x));
  94    return var_range[x];
  95 }
  96
  97 ///////////////////////////////////////////////////////////////////////////////
  98 //
  99 //  Method to print messages
 100 //
 101 ///////////////////////////////////////////////////////////////////////////////
 102 void PaigeGoyal::message(const char * msg, Exp e)
 103 {  log << ::indent << e << ::newline << ::newline << ::unindent
 104        << '[' << msg << ']' << ::newline << ::newline;
 105 }
 106
 107 void PaigeGoyal::error(const char * msg, Exp e)
 108 {  errlog << '[' << "ERROR:" << msg << ']' << ::newline << ::indent
 109           << e << ::newline << ::unindent;
 110 }
 111
 112 void PaigeGoyal::set_log(ostream& f) { log.set_stream(f); }
 113 void PaigeGoyal::set_error(ostream& f) { errlog.set_stream(f); }
 114
 115 ///////////////////////////////////////////////////////////////////////////////
 116 //
 117 //  Method to add an edge into the query graph
 118 //
 119 ///////////////////////////////////////////////////////////////////////////////
 120 void PaigeGoyal::add_edge(Id x, Id y)
 121 {  if (parent.contains(y))
 122    {  Id z = parent[y];
 123       if (x != z)
 124          errlog << "Edge: " << x << "->" << y << "conflicts with"
 125                 << z << "->" << y << "in the query graph\n";
 126    }
 127    parent.insert(y,x);
 128 }
 129
 130 Bool PaigeGoyal::has_edge(Id x, Id y) const
 131 {  if (! parent.contains(y)) return false;
 132    return parent[y] == x;
 133 }
 134
 135 void PaigeGoyal::add_edge_query(Id x, Id y, Exp q)
 136 {
 137    edge_queries.insert(.(x,y),q);
 138 }
 139
 140 ///////////////////////////////////////////////////////////////////////////////
 141 //
 142 //  Method to compute the transitive closure of the query graph
 143 //
 144 ///////////////////////////////////////////////////////////////////////////////
 145 void PaigeGoyal::compute_transitive_closure()
 146 {  foreach (i,parent)
 147    {  parent_closure.insert(parent.key(i),parent.value(i));
 148    }
 149 }
 150
 151 ///////////////////////////////////////////////////////////////////////////////
 152 //
 153 //  Methods to push/pop from the quantifier stack
 154 //
 155 ///////////////////////////////////////////////////////////////////////////////
 156 void PaigeGoyal::push_quantifier(Id x) { quantifier_vars.push(x); }
 157 void PaigeGoyal::push_quantifier(Ids xs)
 158 {  match while (xs) of #[h ... t]: { push_quantifier(h); xs = t; } end match; }
 159 void PaigeGoyal::pop_quantifier(Id x) { quantifier_vars.pop(); }
 160 void PaigeGoyal::pop_quantifier(Ids xs)
 161 {  match while (xs) of #[h ... t]: { pop_quantifier(h); xs = t; } end match; }
 162
 163 ///////////////////////////////////////////////////////////////////////////////
 164 //
 165 //  Method to print the query graph
 166 //
 167 ///////////////////////////////////////////////////////////////////////////////
 168 void PaigeGoyal::print_query_graph()
 169 {  log << ::tab << "[Query Graph]" << ::newline << ::indent;
 170    foreach (i,parent)
 171    {  Id x = parent.value(i);
 172       Id y = parent.key(i);
 173       log << ::tab << "edge" << x << "->" << y;
 174       if (edge_queries.contains(.(x,y)))
 175           log << '\t' << edge_queries[.(x,y)];
 176       log << ::newline;
 177    }
 178    log << ::unindent;
 179 }
 180
 181 ///////////////////////////////////////////////////////////////////////////////
 182 //
 183 //  Main method to decompose a query
 184 //
 185 ///////////////////////////////////////////////////////////////////////////////
 186 Exp PaigeGoyal::decompose(Exp e)
 187 {  subqueries = #[];
 188    do {
 189       changed = false;
 190       e = remove_duplicate_names(e);
 191       e = phase1(e);   // DNF construction
 192       e = construct_query_graph(e); // query graph construction
 193       e = phase2(e);   // quantifier elimination
 194       e = phase3(e);   // disjunction removal
 195       e = phase4(e);   // conjunction removal
 196       e = projection_recognition(e);
 197       e = phase5(e);
 198       if (changed) message("Reiterating the transformation",e);
 199    } while (changed);
 200    return e;
 201 }