include/AD/automata/treeauto.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef compressed_tree_automaton_h
  26 #define compressed_tree_automaton_h
  27
  28 /////////////////////////////////////////////////////////////////////////////
  29 // Class |TreeAutomaton| represents a compressed tree automaton
  30 // using a flattened multidimensional transition table\cite{Chase}.
  31 //
  32 // Three tables are used to represent the transition tables:
  33 // ``arity'', ``base'', and ``index''.  The table ``arity'' is a mapping
  34 // from functors to their arities.  The table ``base'' maps each functor
  35 // to the starting offset of the index table.  Each functor |A|'s index table
  36 // is comprised of two components: the first is a list of index tables
  37 // $\mu_Ai$ for each arity $i$; followed by the compressed transition
  38 // table $\theta_A$.   The multidimensional transition table is
  39 // ``flattened'' into linear form so that multiplication is unnecessary
  40 // when computing the indices.
  41 /////////////////////////////////////////////////////////////////////////////
  42
  43 #include <iostream>
  44 #include <AD/automata/treetab.h>   // tree automata tables
  45 #include <AD/automata/treegram.h>  // tree grammar
  46 #include <AD/automata/sparsdfa.h>  // DFA compression
  47 #include <AD/memory/mem.h>         // memory managers
  48 #include <AD/contain/bitset.h>     // bit sets
  49
  50 /////////////////////////////////////////////////////////////////////////////
  51 //  Class TreeAutomaton is the base class of the tree parser/matcher
  52 //  generators.  Algorithms are based on ``bottomup techniques,'' phrased
  53 //  in terms of tree-automata(or equivalently, non-unary multisorted
  54 //  algebra.)
  55 /////////////////////////////////////////////////////////////////////////////
  56 class TreeAutomaton : public TreeTables {
  57
  58    TreeAutomaton(const TreeAutomaton&);     // no copy constructor
  59    void operator = (const TreeAutomaton&);  // no assignment
  60
  61 public:
  62
  63    //////////////////////////////////////////////////////////////////////////
  64    // Make inherited types visible.
  65    //////////////////////////////////////////////////////////////////////////
  66    typedef TreeTables         Super;
  67    typedef Super::Offset      Offset;      // table offsets
  68    typedef Super::State       State;       // a state in the tree automaton
  69    typedef Super::Functor     Functor;     // constructor of a term
  70    typedef Super::Variable    Variable;    // pattern variables
  71    typedef Super::NonTerminal NonTerminal; // non-terminals
  72    typedef Super::Cost        Cost;        // reduction cost
  73    typedef Super::Arity       Arity;       // arity of a functor
  74    typedef Super::Rule        Rule;        // rule number
  75    typedef Super::State       Equiv;       // equivalence class
  76
  77 protected:
  78
  79    //////////////////////////////////////////////////////////////////////////
  80    // A memory pool
  81    //////////////////////////////////////////////////////////////////////////
  82    Mem&                mem;  // internal memory pool
  83    const TreeGrammar * G;    // supplied tree grammar
  84
  85    //////////////////////////////////////////////////////////////////////////
  86    // Uncompressed tables.
  87    //    The transition map (as per David Chase) for each functor is
  88    // actually represented by a set of tables:
  89    //    (1) An index equivalence class map 'mu' for each arity.   I.e. two
  90    //        states that'll have the same effect on that arity are mapped
  91    //        into the same equivalence class.
  92    //    (2) A multidimensional array representing the transition.
  93    // The transition function for each functor is computed as
  94    //
  95    //     f(a_1, ..., a_n) = delta[mu_1[a_1]] ... [mu_n[a_n]]
  96    //////////////////////////////////////////////////////////////////////////
  97    State ***           mu;       // mapping from state x functor x arity -> equivclass
  98    Equiv **            mu_equiv; // mapping from functor x arity -> next equivclass #
  99    class DeltaTable ** delta;    // transition table is an n-dimensional array
 100                                  // indexed by functor.  The actual definition
 101                                  // of this array type is hidden in the
 102                                  // implementation.
 103    State *     singleton_delta;  // transition table for unit functors
 104    int         delta_size;       // size of this table.
 105
 106    //////////////////////////////////////////////////////////////////////////
 107    // Tables
 108    //////////////////////////////////////////////////////////////////////////
 109    Arity  *  arity;         // functor to arity mapping
 110    BitSet ** accept;        // state -> accepted rules set mapping
 111    Rule   *  accept1;       // state -> *first* accepted rule mapping
 112    Cost   *  accept1_cost;  // state -> *first* minimal cost rule mapping
 113    Offset *  accept_base;   // state -> accept offset
 114    Rule   *  accept_vector; // offset -> accept vector
 115    int       accept_vector_size;   // size of the accept vector
 116
 117    //////////////////////////////////////////////////////////////////////////
 118    // Flags to keep track of which things are used
 119    //////////////////////////////////////////////////////////////////////////
 120    Bool mu_used, mu_index_used, accept_used, accept_bitmap_used, accept1_used;
 121
 122    //////////////////////////////////////////////////////////////////////////
 123    // Sizes of these tables
 124    //////////////////////////////////////////////////////////////////////////
 125    int arity_size;       // size of the arity table
 126    int max_state;        // current maximum state
 127
 128    //////////////////////////////////////////////////////////////////////////
 129    // Compressed tables
 130    //////////////////////////////////////////////////////////////////////////
 131    SparseDFA dfa_compiler;             // DFA compression object
 132    int **    mu_index;                 // mapping from functor x arity -> compressed index
 133    int       total_index_entries;      // size of all index maps together
 134    int       non_error_index_entries;  // size of all non-empty index maps
 135
 136    //////////////////////////////////////////////////////////////////////////
 137    // Error checking;
 138    //////////////////////////////////////////////////////////////////////////
 139    Bool exhaustive;   // set of patterns are exhaustive?
 140
 141    //////////////////////////////////////////////////////////////////////////
 142    // Others
 143    //////////////////////////////////////////////////////////////////////////
 144    int state_count;      // number of states
 145
 146    //////////////////////////////////////////////////////////////////////////
 147    // State expansion
 148    //////////////////////////////////////////////////////////////////////////
 149    virtual void grow_states(int increment);
 150
 151 public:
 152
 153    //////////////////////////////////////////////////////////////////////////
 154    // Constructor and destructor
 155    //////////////////////////////////////////////////////////////////////////
 156             TreeAutomaton( Mem& );
 157    virtual ~TreeAutomaton();
 158
 159    //////////////////////////////////////////////////////////////////////////
 160    // Table compilation
 161    //////////////////////////////////////////////////////////////////////////
 162    virtual void compile                   (TreeGrammar&);
 163    virtual void compile_compression_index ();
 164
 165    //////////////////////////////////////////////////////////////////////////
 166    // Selectors
 167    //////////////////////////////////////////////////////////////////////////
 168    inline int    number_of_states()              const { return state_count; }
 169    inline Arity  arity_of(Functor f)             const { return arity[f]; }
 170    inline int    index_range(Functor f, Arity i) const { return mu_equiv[f][i]; }
 171    inline Equiv  index_map(Functor f, Arity i, State s) const { return mu[s][f][i]; }
 172           State  get_delta(Functor f, const int []) const;
 173    inline const BitSet& accept_rules(State s)    const { return *accept[s]; }
 174    inline       BitSet& accept_rules(State s)          { return *accept[s]; }
 175    inline Rule          accept1_rule(State s)    const { return accept1[s]; }
 176    inline Bool is_accept_state(State s) const { return accept1[s] >= 0; }
 177    inline Cost          min_accept_cost(State s) const { return accept1_cost[s]; }
 178    inline Bool is_exhaustive () const { return exhaustive; }
 179
 180    //////////////////////////////////////////////////////////////////////////
 181    // Methods to add a new state.
 182    //////////////////////////////////////////////////////////////////////////
 183           void new_state(State);
 184    inline void add_mu(Functor f, int i, State s0, State s1)
 185           {  if (s0 > s1) mu[s0][f][i] = mu[s1][f][i];
 186              else         mu[s0][f][i] = mu_equiv[f][i]++;
 187           }
 188    inline void add_delta (Functor f, State s) { singleton_delta[f] = s; }
 189           void add_delta (Functor, const int [], State);
 190    inline void set_accept1 (State s, Rule r)  { accept1[s] = r; }
 191    inline void set_accept1 (State s, Rule r, Cost c)
 192           { accept1[s] = r; accept1_cost[s] = c; }
 193
 194    //////////////////////////////////////////////////////////////////////////
 195    //  Methods dealing with mu-compression.
 196    //////////////////////////////////////////////////////////////////////////
 197    inline int     compressed_index(Functor f, Arity i) const
 198       { return mu_index[f][i]; }
 199    inline Offset  compressed_offset(Functor f, Arity i) const
 200       { return dfa_compiler.state_offset(mu_index[f][i]); }
 201    virtual double compression_rate() const;
 202
 203    //////////////////////////////////////////////////////////////////////////
 204    // Code emission methods.
 205    //    gen_code  -- generate compressed tables.
 206    //    gen_index -- generate index table for one arity of a functor.
 207    //    gen_theta -- generate transition table for one functor.
 208    //////////////////////////////////////////////////////////////////////////
 209    const char * get_state_type () const;
 210    const char * get_rule_type () const;
 211    virtual std::ostream& gen_index(std::ostream&, Functor, Arity, const char []) const;
 212    virtual std::ostream& gen_theta(std::ostream&, Functor, const char []) const;
 213    virtual std::ostream& gen_accept          (std::ostream&, const char name[]) const;
 214    virtual std::ostream& gen_bitmap_accept   (std::ostream&, const char name[]) const;
 215    virtual std::ostream& gen_accept1         (std::ostream&, const char name[]) const;
 216    virtual std::ostream& gen_compressed_index(std::ostream&, const char name[]) const;
 217
 218    //////////////////////////////////////////////////////////////////////////
 219    // Advance one state within the tree automaton.
 220    //    The first go() function is an optimized form for a unit functor--
 221    // i.e. a functor with 0 arity.  The second go() function is the general
 222    // form which looks up all three tables.
 223    //////////////////////////////////////////////////////////////////////////
 224    inline State go(Functor f) const { return singleton_delta[f]; }
 225
 226    //////////////////////////////////////////////////////////////////////////
 227    //  Method for printing a report
 228    //////////////////////////////////////////////////////////////////////////
 229    virtual std::ostream& print_report(std::ostream&) const;
 230    virtual std::ostream& print_state(std::ostream&, State) const;
 231
 232    //////////////////////////////////////////////////////////////////////////
 233    //  Name of algorithm
 234    //////////////////////////////////////////////////////////////////////////
 235    virtual const char * algorithm () const = 0;
 236
 237 protected:
 238    virtual void compute_accept_tables ();
 239 };
 240
 241 #endif