app/willard/paige.h

   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.ph".
   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.ph"
  13 #ifndef paige_doyal_h
  14 #define paige_doyal_h
  15
  16 #include <AD/pretty/postream.h>
  17 #include <AD/contain/varstack.h>
  18 #include "willard-ast.h"
  19 #include "idset.h"
  20 #include "smap.h"
  21
  22 class ostream;
  23
  24 ///////////////////////////////////////////////////////////////////////////////
  25 //
  26 //   This class implements the transformation algorithm as developed by
  27 //   Bob Paige and Deepak Goyal.
  28 //
  29 ///////////////////////////////////////////////////////////////////////////////
  30 class PaigeGoyal
  31 {  PaigeGoyal(const PaigeGoyal&);
  32    void operator = (const PaigeGoyal&);
  33
  34    ////////////////////////////////////////////////////////////////////////////
  35    //
  36    //  Internal data
  37    //
  38    ////////////////////////////////////////////////////////////////////////////
  39 protected:
  40    PrettyOStream    log, errlog; // pretty printing stream for message logging
  41    int              new_name;    // counter for new names
  42    Ids              subquery_names; // set of subqueries currently generated.
  43    Exps             subqueries;  // set of subqueries currently generated.
  44    SMap<Id,Exp>     var_range;   // record the range of each variable
  45    SMap<Id,Id>      parent;      // the query graph:
  46                                  //   mapping from child to parent
  47    SMap<Id,Id>      parent_closure; // the query graph (in closure form):
  48    SMap<
  49 #line 36 "paige.ph"
  50 Tuple2<Id, Id>
  51 #line 36 "paige.ph"
  52 ,Exp> edge_queries; // mapping from edge (x,y) to query Q(x,y)
  53    VarStack<Id> quantifier_vars;    // quantifier vars currently in scope
  54 protected:
  55
  56    ////////////////////////////////////////////////////////////////////////////
  57    //
  58    // Internal methods
  59    //
  60    ////////////////////////////////////////////////////////////////////////////
  61
  62    ////////////////////////////////////////////////////////////////////////////
  63    // Common predefined constants
  64    ////////////////////////////////////////////////////////////////////////////
  65    Exp True, False, Zero, One, Two, EmptySet;
  66
  67    ////////////////////////////////////////////////////////////////////////////
  68    // Methods to construct the query graph
  69    ////////////////////////////////////////////////////////////////////////////
  70    void add_edge(Id x, Id y);
  71    Bool has_edge(Id x, Id y) const;
  72    void add_edge_query(Id x, Id y, Exp query);
  73    void compute_transitive_closure();
  74    void print_query_graph();
  75
  76    ////////////////////////////////////////////////////////////////////////////
  77    // Methods to collect free variables in an expression.
  78    ////////////////////////////////////////////////////////////////////////////
  79    void free_vars(Ids,  IdSet&) const;
  80    void free_vars(Exp,  IdSet&) const;
  81    void free_vars(Exps, IdSet&) const;
  82    void remove_vars (IdSet&, Ids) const;
  83    void remove_vars (IdSet&, const IdSet&) const;
  84
  85    ////////////////////////////////////////////////////////////////////////////
  86    // Is x free in e?
  87    ////////////////////////////////////////////////////////////////////////////
  88    Bool is_free(Id x, Exp e) const;
  89    Bool is_free(Ids xs, Exp e) const;
  90
  91    ////////////////////////////////////////////////////////////////////////////
  92    // Methods to generate new names
  93    ////////////////////////////////////////////////////////////////////////////
  94    Id gensym();
  95    Id gensym(Id prefix);
  96
  97    ////////////////////////////////////////////////////////////////////////////
  98    // Methods to generate and collect subqueries
  99    ////////////////////////////////////////////////////////////////////////////
 100    void add_subquery(Id, Exp);
 101    Exp collect_subqueries(Exp);
 102    Bool has_subqueries() const;
 103
 104    ////////////////////////////////////////////////////////////////////////////
 105    // Method to record the range of each variable.
 106    ////////////////////////////////////////////////////////////////////////////
 107    void define_range(Id, Exp);
 108    void define_range(Ids, Exps);
 109    Exp  range_of(Id);
 110
 111    ////////////////////////////////////////////////////////////////////////////
 112    // Methods to push/pop from the quantifier stack
 113    ////////////////////////////////////////////////////////////////////////////
 114    void push_quantifier(Id x);
 115    void push_quantifier(Ids xs);
 116    void pop_quantifier(Id x);
 117    void pop_quantifier(Ids xs);
 118
 119    ////////////////////////////////////////////////////////////////////////////
 120    // Set by subclasses if re-iteration of the transformation process
 121    // is required.
 122    ////////////////////////////////////////////////////////////////////////////
 123    Bool changed;
 124
 125    ////////////////////////////////////////////////////////////////////////////
 126    // Method to create a nested let
 127    ////////////////////////////////////////////////////////////////////////////
 128 public:
 129    static Exp make_let(Ids, Exps, Exp);
 130 public:
 131             PaigeGoyal();
 132    virtual ~PaigeGoyal();
 133
 134    ////////////////////////////////////////////////////////////////////////////
 135    // Main decomposition method
 136    ////////////////////////////////////////////////////////////////////////////
 137    virtual Exp decompose(Exp);
 138
 139    ////////////////////////////////////////////////////////////////////////////
 140    // Method to print messages
 141    ////////////////////////////////////////////////////////////////////////////
 142    void message(const char * mesg, Exp e);
 143    void error(const char * mesg, Exp e);
 144    void set_log  (ostream&);
 145    void set_error(ostream&);
 146 protected:
 147
 148    ////////////////////////////////////////////////////////////////////////////
 149    // The following are the different phases implemented in subclasses.
 150    ////////////////////////////////////////////////////////////////////////////
 151    virtual Exp remove_duplicate_names(Exp) = 0;
 152    virtual Exp construct_query_graph(Exp) = 0; // query graph construction
 153    virtual Exp projection_recognition(Exp) = 0;
 154    virtual Exp phase1(Exp) = 0;  // DNF construction
 155    virtual Exp phase2(Exp) = 0;  // quantifier elimination
 156    virtual Exp phase3(Exp) = 0;  // disjunction removal
 157    virtual Exp phase4(Exp) = 0;  // join decomposition
 158    virtual Exp phase5(Exp) = 0;  // simple count/find query decomposition
 159 };
 160
 161 #endif
 162 /*
 163 ------------------------------- Statistics -------------------------------
 164 Merge matching rules         = yes
 165 Number of DFA nodes merged   = 0
 166 Number of ifs generated      = 0
 167 Number of switches generated = 0
 168 Number of labels             = 0
 169 Number of gotos              = 0
 170 Adaptive matching            = disabled
 171 Fast string matching         = disabled
 172 Inline downcasts             = disabled
 173 --------------------------------------------------------------------------
 174 */