prop-src/graphtype.ph

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 // This file implements the graph type generator
   4 //
   5 ///////////////////////////////////////////////////////////////////////////////
   6 #ifndef graph_type_generator_h
   7 #define graph_type_generator_h
   8
   9 #include "basics.ph"
  10 #include "ir.h"
  11 #include "ast.h"
  12 #include "codegen.h"
  13 #include "classdef.h"
  14
  15 ///////////////////////////////////////////////////////////////////////////////
  16 //
  17 //  Forward type definitions
  18 //
  19 ///////////////////////////////////////////////////////////////////////////////
  20 class NodeDef;
  21 class EdgeDef;
  22 class GraphTypeDef;
  23
  24 type NodeDefs = List<NodeDef *>
  25 and  EdgeDefs = List<EdgeDef *>
  26 ;
  27
  28 ///////////////////////////////////////////////////////////////////////////////
  29 //
  30 //  Indexing options of graph types
  31 //
  32 ///////////////////////////////////////////////////////////////////////////////
  33 enum { NOindex        = 0,
  34        DOMindex       = 1<<0,   // index on domain
  35        RANindex       = 1<<1,   // index on range
  36        COUNTindex     = 1<<2,   // counting index
  37        FORWARDindex   = 1<<3,   // map from domain to range
  38        INVERSEindex   = 1<<4,   // map from range to domain
  39        BITMAPindex    = 1<<5,   // use bitmaps to represent index
  40        UNIONFINDindex = 1<<6    // use union/find to represent index
  41      };
  42
  43 enum { UNBASEDrep       = 0,    // unbased
  44        WEAKLYBASEDrep   = 1<<1, // weakly based
  45        STRONGLYBASEDrep = 1<<2, // strongly based
  46        TABLEDrep        = 1<<3  // also allow address arithmetic on base
  47      };
  48
  49 enum { NOgop          = 0,      // no operations
  50        SIZEgop        = 1<<0,   // # f
  51        DOMgop         = 1<<1,   // dom f
  52        RANgop         = 1<<2,   // ran f
  53        DOMSIZEgop     = 1<<3,   // # dom f
  54        RANSIZEgop     = 1<<4,   // # ran f
  55        IMAGEgop       = 1<<5,   // f(x)
  56        IMAGESETgop    = 1<<6,   // f{x}
  57        REVIMAGEgop    = 1<<7,   // (inv f)(x)
  58        REVIMAGEMAPgop = 1<<8,   // (inv f){x}
  59        UNIONgop       = 1<<9,   // f union := g
  60        BITSETgop      = 1<<10,  // bitvector operations
  61        UNIONFINDgop   = 1<<11,  // union find operations
  62        INDOMgop       = 1<<12,  // x in dom f
  63        INRANgop       = 1<<13,  // x in ran f
  64        INgop          = 1<<14,  // x in f
  65        UPDATEIMAGEgop = 1<<15   // f(x) := y or f{x} with := y
  66      };
  67
  68 type GraphIndexing = int;
  69 type GraphOps      = int;
  70 type GraphRep      = int;
  71
  72 ///////////////////////////////////////////////////////////////////////////////
  73 //
  74 //  Class to represent a graph type definition.
  75 //
  76 ///////////////////////////////////////////////////////////////////////////////
  77 class GraphTypeDef : public ClassDefinition
  78 {  GraphTypeDef(const GraphTypeDef&);
  79    void operator = (const GraphTypeDef&);
  80 protected:
  81    friend class NodeDef;
  82    friend class EdgeDef;
  83    NodeDefs node_defs;
  84    EdgeDefs edge_defs;
  85 public:
  86    GraphTypeDef(Id name, Inherits, TyQual,
  87                 NodeDefs=#[], EdgeDefs=#[], Decls=#[]);
  88    virtual ~GraphTypeDef();
  89
  90    virtual NodeDef * lookup_node (Id);
  91    virtual EdgeDef * lookup_edge (Id);
  92    virtual void choose_representation();
  93    virtual void print_report(CodeGen&);
  94    void    set_nodes (NodeDefs);
  95    void    set_edges (EdgeDefs);
  96    void    set_body  (Decls);
  97 protected:
  98    virtual void gen_class_predefinition (CodeGen&);
  99    virtual void gen_class_interface (CodeGen&);
 100    virtual void gen_class_implementation (CodeGen&);
 101    void gen_init_graph(CodeGen&);
 102    void gen_lookup_node(CodeGen&);
 103    void gen_insert_node(CodeGen&);
 104    void gen_remove_node(CodeGen&);
 105 };
 106
 107 ///////////////////////////////////////////////////////////////////////////////
 108 //
 109 //  Class to represent a node definition.
 110 //
 111 ///////////////////////////////////////////////////////////////////////////////
 112 class NodeDef : public Loc
 113 {  NodeDef(const NodeDef&);
 114    void operator = (const NodeDef&);
 115 protected:
 116    friend class GraphTypeDef;
 117    friend class EdgeDef;
 118    GraphTypeDef * G;       // the parent graph
 119    Id       node_name;     // name of this node
 120    Ty       node_type;     // node label is a value from this type
 121    Id       hash_fun;      // hash function
 122    Id       eq_fun;        // equality function
 123    LabTys   attributes;    // additional attributes
 124    GraphRep rep;           // representation of this domain
 125 public:
 126    NodeDef(GraphTypeDef *, Id, Ty = NOty, Id = 0, Id = 0, LabTys = #[]);
 127    virtual ~NodeDef();
 128
 129    inline  Id name () const { return node_name; }
 130    inline  GraphTypeDef * graph () const { return G; }
 131    virtual void choose_representation();
 132    virtual void generate_forward_decls  (CodeGen&);
 133    virtual void generate_representation (CodeGen&);
 134    virtual void generate_interface      (CodeGen&);
 135    virtual void generate_implementation (CodeGen&);
 136    virtual void print_report(CodeGen&);
 137 };
 138
 139 ///////////////////////////////////////////////////////////////////////////////
 140 //
 141 //  Class to represent an edge definition.
 142 //
 143 ///////////////////////////////////////////////////////////////////////////////
 144 class EdgeDef : public Loc
 145 {  EdgeDef(const EdgeDef&);
 146    void operator = (const EdgeDef&);
 147 protected:
 148    friend class GraphTypeDef;
 149    friend class NodeDef;
 150    GraphTypeDef * graph;       // our graph
 151    Id             edge_name;   // name of this edge
 152    NodeDef*       domain_type; // domain of this type
 153    NodeDef*       range_type;  // range of this type
 154    GraphIndexing  indexing;    // indexing information
 155    LabTys         attributes;  // additional attributes
 156    GraphOps       ops;         // defined operations
 157
 158 protected:
 159    EdgeDef(GraphTypeDef *, Id, NodeDef*, NodeDef*,
 160            GraphIndexing, LabTys = #[]);
 161    virtual ~EdgeDef();
 162 public:
 163
 164    inline  Id name () const { return edge_name; }
 165    virtual void choose_representation ();
 166    virtual void generate_node_representation (CodeGen&, NodeDef *);
 167    virtual void generate_edge_representation (CodeGen&);
 168    virtual void generate_interface      (CodeGen&);
 169    virtual void generate_implementation (CodeGen&);
 170    virtual void print_report(CodeGen&);
 171
 172 protected:
 173
 174    virtual void generate_edge_rep(CodeGen&);
 175    virtual void generate_dom_rep (CodeGen&);
 176    virtual void generate_ran_rep (CodeGen&);
 177    virtual void generate_interf  (CodeGen&);
 178    virtual void generate_impl    (CodeGen&);
 179
 180    ////////////////////////////////////////////////////////////////////////////
 181    //
 182    //  Methods to generate various methods to implement various set operations
 183    //
 184    ////////////////////////////////////////////////////////////////////////////
 185    virtual void gen_dom         (CodeGen&); // dom f
 186    virtual void gen_ran         (CodeGen&); // ran f
 187    virtual void gen_in_dom      (CodeGen&); // x in dom f
 188    virtual void gen_in_ran      (CodeGen&); // x in ran f
 189    virtual void gen_in          (CodeGen&) = 0; // x in f
 190    virtual void gen_size        (CodeGen&); // # f
 191    virtual void gen_dom_size    (CodeGen&); // # dom f
 192    virtual void gen_ran_size    (CodeGen&); // # ran f
 193    virtual void gen_image       (CodeGen&); // f(x)  or f{x}
 194    virtual void gen_update_image(CodeGen&); // f(x) := y or f{x} with := y
 195 };
 196
 197 #endif