prop-src/funmap.ph

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  This file decribes the functor map data structure, which is
   4 //  used internally during rewriting compilation.
   5 //
   6 ///////////////////////////////////////////////////////////////////////////////
   7 #ifndef functor_map_h
   8 #define functor_map_h
   9
  10 #include <AD/automata/treegram.h>
  11 #include "ir.h"
  12 #include "ast.h"
  13 #include "type.h"
  14 #include "hashtab.h"
  15 #include "functortab.h"
  16
  17 ///////////////////////////////////////////////////////////////////////////////
  18 //
  19 //  Import some type definitions from the tree grammar and hash table
  20 //  classes.
  21 //
  22 ///////////////////////////////////////////////////////////////////////////////
  23 class ostream;
  24 class TreeAutomaton;
  25 class TopDownGen;
  26 typedef TreeGrammar::Functor        Functor;
  27 typedef TreeGrammar::Variable       Variable;
  28
  29 ///////////////////////////////////////////////////////////////////////////////
  30 //
  31 //  Vector Id
  32 //
  33 ///////////////////////////////////////////////////////////////////////////////
  34 datatype VectorId : MEM = vector_id { cons : Cons, ty : Ty, arity : int };
  35
  36 ///////////////////////////////////////////////////////////////////////////////
  37 //
  38 //  Functor mapping table.
  39 //
  40 ///////////////////////////////////////////////////////////////////////////////
  41 class FunctorMap {
  42    FunctorMap(const FunctorMap&);      // no copy constructor
  43    void operator = (const FunctorMap&);  // no assignment
  44 public:
  45    ////////////////////////////////////////////////////////////////////////////
  46    //  Internals
  47    ////////////////////////////////////////////////////////////////////////////
  48    FunctorTable   literal_map;  // mapping from literals to Functors
  49    FunctorTable   type_map;     // mapping from types to Functors
  50    FunctorTable   vector_map;   // mapping from vector constructors to Functors
  51    FunctorTable   var_map;      // mapping from non-terminals to Functors
  52    HashTable      rule_map;     // mapping from types to rule lists
  53    HashTable      topdown_rule_map; // mapping from types to topdown rules
  54    HashTable      before_rule_map;  // mapping from types to before rules
  55    HashTable      preorder_rule_map;  // mapping from types to preorder rules
  56    HashTable      postorder_rule_map; // mapping from types to postorder rules
  57    HashTable*     rule_maps[MatchRuleInfo::LAST_REWRITING_MODE]; // rule maps
  58    HashTable      protocols;    // mapping from type to type
  59    HashTable      nonterm_map;  // mapping from (lhs) nonterminal to type
  60    HashTable      nonterm_rules;// mapping from (lhs) nonterminal to rules.
  61    HashTable      nonterm_rules_bits;// mapping from (lhs) nonterminal to size of rules.
  62    HashTable      chain_rules;  // mapping of rhs to rules of form lhs -> rhs
  63    TreeGrammar     G;           // the current tree grammar
  64    TreeGrammar::Functor         functors;    // number of functors
  65    TreeGrammar::Variable        variables;   // number of variables
  66    TreeAutomaton * tree_gen;    // the tree automaton generator
  67    TopDownGen *    topdown_gen; // topdown tree automaton generator
  68    Bool        use_compression; // should we use index compression?
  69    Bool        has_guard;       // the set of rules contain guards?
  70    Bool        has_cost;        // the set of rules contain costs?
  71    Bool        has_cost_exp;    // the set of rules contain cost exprs?
  72    Bool        has_syn_attrib;  // are we using synthesized attributes?
  73    Bool        has_replacement; // the set of rules have replacements?
  74    Bool        is_applicative;  // Is rewriting done applicatively?
  75    Bool        gen_reducers;    // Should we generate a reducer?
  76    Bool        dynamic_search;  // Use runtime search?
  77    int         N;               // number of rules
  78    int         max_arity;       // maximum arity of patterns.
  79    Id          class_name;      // name of rewrite class
  80    Id *        functor_names;   // names of functors
  81    Id *        variable_names;  // names of variables
  82    Bool        is_ok;           // no errors found?
  83    MatchRules  bottomup_rules;  // only the bottomup rules are here
  84
  85    ////////////////////////////////////////////////////////////////////////////
  86    //
  87    //  Constructor
  88    //
  89    ////////////////////////////////////////////////////////////////////////////
  90    FunctorMap(Id name, MatchRules rules);
  91
  92    ////////////////////////////////////////////////////////////////////////////
  93    //
  94    //  Check whether we have an error
  95    //
  96    ////////////////////////////////////////////////////////////////////////////
  97    inline Bool ok() const { return is_ok; }
  98
  99    ////////////////////////////////////////////////////////////////////////////
 100    //
 101    //  Check whether a type known to the compiler?
 102    //
 103    ////////////////////////////////////////////////////////////////////////////
 104    Bool is_known_type      (Ty);
 105    Bool is_rewritable_type (Ty);
 106
 107    ////////////////////////////////////////////////////////////////////////////
 108    //
 109    //  Methods to compute the cost expression of a pattern.
 110    //
 111    ////////////////////////////////////////////////////////////////////////////
 112    Exp cost_expr (Id, Pat);
 113    Exp cost_expr (Id, Pat,     Exp);
 114    Exp cost_expr (Id, Pats,    Exp);
 115    Exp cost_expr (Id, LabPats, Exp);
 116
 117    ////////////////////////////////////////////////////////////////////////////
 118    //
 119    //  Method to print a report detailing the functor/variable encoding,
 120    //  the tree grammar and the generated table size
 121    //
 122    ////////////////////////////////////////////////////////////////////////////
 123    void print_report(ostream&);
 124
 125 private:
 126    ////////////////////////////////////////////////////////////////////////////
 127    //
 128    //  Methods to build the protocol list
 129    //
 130    ////////////////////////////////////////////////////////////////////////////
 131    void enter_protocols ();
 132    void check_for_missing_protocols ();
 133
 134    ////////////////////////////////////////////////////////////////////////////
 135    //
 136    //  Methods to convert literal patterns into guards
 137    //
 138    ////////////////////////////////////////////////////////////////////////////
 139    void    make_guard (MatchRules);
 140    Pat     make_guard (Pat, Exp&);
 141    Pats    make_guard (Pats, Exp&);
 142    LabPats make_guard (LabPats, Exp&);
 143
 144    ////////////////////////////////////////////////////////////////////////////
 145    //
 146    //  Method to build the tree grammar
 147    //
 148    ////////////////////////////////////////////////////////////////////////////
 149    void build_tree_grammar (MatchRules);
 150
 151    ////////////////////////////////////////////////////////////////////////////
 152    //
 153    //  Encoding methods
 154    //
 155    ////////////////////////////////////////////////////////////////////////////
 156    void encode (Ty);  // encode a type
 157    void encode (Pat); // encode a pattern
 158    void encode (Id);  // encode a non-terminal
 159    Id   chain_rule_rhs (Pat);
 160
 161    ////////////////////////////////////////////////////////////////////////////
 162    //
 163    //  Translation methods
 164    //
 165    ////////////////////////////////////////////////////////////////////////////
 166    TreeTerm trans(Pat);
 167
 168    ////////////////////////////////////////////////////////////////////////////
 169    //
 170    //  Method to partition a set of rules according to the types of the
 171    //  top level pattern, also encode the pattern in the process.
 172    //
 173    ////////////////////////////////////////////////////////////////////////////
 174    MatchRules partition_rules (MatchRules);
 175
 176    ////////////////////////////////////////////////////////////////////////////
 177    //
 178    //  Method to compute the functor and variable names
 179    //
 180    ////////////////////////////////////////////////////////////////////////////
 181    void compute_names ();
 182 };
 183
 184 #endif