prop-src/ir.ph

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  This file contains the definitions for the intermediate data structures
   4 //  used within the Prop -> C++ translator.  Definitions for types, patterns,
   5 //  decision trees, and pretty printing formats are located here.
   6 //
   7 ///////////////////////////////////////////////////////////////////////////////
   8 #ifndef intermediate_representations_h
   9 #define intermediate_representations_h
  10
  11 #include "basics.ph"
  12
  13 ///////////////////////////////////////////////////////////////////////////////
  14 //
  15 //  Forward datatype declarations
  16 //
  17 ///////////////////////////////////////////////////////////////////////////////
  18 datatype Exp and Stmt and Decl and MatchRule and CollectionDesc;
  19
  20 class GraphTypeDef;
  21 class EdgeDef;
  22 class NodeDef;
  23 class DatatypeHierarchy;
  24 class DatatypeClass;
  25
  26 ///////////////////////////////////////////////////////////////////////////////
  27 //
  28 //  Qualifiers determines various implementation characteristics
  29 //  of the type.
  30 //
  31 ///////////////////////////////////////////////////////////////////////////////
  32 enum { QUALnone          = 0,      // no qualifiers
  33        QUALprintable     = 1<<0,   // pretty printable
  34        QUALtracable      = 1<<1,   // reference countable
  35        QUALcollectable   = 1<<2,   // garbage collectable
  36        QUALrewritable    = 1<<3,   // rewritable
  37        QUALrelation      = 1<<4,   // a relation
  38        QUALpersistent    = 1<<5,   // persistent type
  39        QUALclass         = 1<<6,   // class type
  40        QUALconst         = 1<<7,   // const
  41        QUALunsigned      = 1<<8,   // unsigned
  42        QUALsigned        = 1<<9,   // signed
  43        QUALvirtual       = 1<<10,  // virtual inheritance
  44        QUALextensible    = 1<<11,  // extensible type
  45        QUALview          = 1<<12,  // a view
  46        QUALunifiable     = 1<<13,  // an unifiable term
  47        QUALtaggedpointer = 1<<14,  // use tagged pointers for representation
  48        QUALunboxed       = 1<<15,  // use unboxed presentation if possible
  49        QUALfinalizable   = 1<<16,  // object should be finalized
  50        QUALapplicative   = 1<<17,  // applicative rewrite
  51        QUALtreeparser    = 1<<18,  // tree parsing
  52        QUALparser        = 1<<19,  // parser class
  53        QUALlexeme        = 1<<20,  // usable as tokens
  54        QUALbitfield      = 1<<21,  // an opcode or opcode bitfield
  55        QUALtopdown       = 1<<22,  // use topdown tree matching in rewriting
  56        QUALvariable      = 1<<23,  // unifiable variable
  57        QUALgraphtype     = 1<<24,  // a graph type
  58        QUALgraphnode     = 1<<25,  // a graph node
  59        QUALgraphedge     = 1<<26,  // a graph edge
  60        QUALvirtualdestr  = 1<<27,  // virtual destructor
  61        QUALinline        = 1<<28,  // inline methods
  62        QUALextern        = 1<<29   // noninline methods
  63      };
  64
  65 ///////////////////////////////////////////////////////////////////////////////
  66 //
  67 //  Optimization options
  68 //
  69 ///////////////////////////////////////////////////////////////////////////////
  70 enum { OPTnone          = 0,     // no optimization
  71        OPTtagless       = 1<<0,  // omit the embedded variant tag
  72        OPTsubclassless  = 1<<1,  // omit the subclass hierarchy
  73        OPTbaseclassless = 1<<2,  // omit inheritance from base class
  74        OPTtaggedpointer = 1<<3,  // embedded the variant tag in lower bits
  75                                  // of the pointer.
  76        OPTunboxed       = 1<<4,  // use unboxed representation if possible
  77        OPTtaggedvar     = 1<<5   // tagged variables
  78      };
  79
  80 ///////////////////////////////////////////////////////////////////////////////
  81 //
  82 //  Scoping
  83 //
  84 ///////////////////////////////////////////////////////////////////////////////
  85 datatype Scope = PRIVATEscope
  86                | PROTECTEDscope
  87                | PUBLICscope
  88
  89 ///////////////////////////////////////////////////////////////////////////////
  90 //
  91 //  Formal/actual parameters.
  92 //
  93 ///////////////////////////////////////////////////////////////////////////////
  94 and  Parameter = TYbody | TYformal | TYsimpleformal | TYactual
  95
  96 ///////////////////////////////////////////////////////////////////////////////
  97 //
  98 //  Pattern variable polarity.
  99 //
 100 ///////////////////////////////////////////////////////////////////////////////
 101 and   Polarity = ISpositive
 102                | ISnegative
 103                | ISneither
 104
 105 ///////////////////////////////////////////////////////////////////////////////
 106 //
 107 //  Type expression.
 108 //
 109 //  Note: All variant datatypes with arguments in the translator are
 110 //  either inherited from class MEM or class Loc.  Class MEM
 111 //  redefines the operator new() to allocate from a global memory pool,
 112 //  which is much faster than the built-in malloc/free.  Class Loc,
 113 //  which is derived from MEM, also keeps track of the source position
 114 //  at the same time.
 115 //
 116 ///////////////////////////////////////////////////////////////////////////////
 117 and   Ty : public MEM
 118                = NOty                          // no type
 119                | VARty    (Ty)                 // a type variable
 120                | INDty    (Id, int)            // indexed to quantifier table.
 121                | QUALty   (TyQual, Ty)         // a qualified type
 122                | TYCONty  (TyCon, List<Ty>)    // type constructor
 123                | POLYty   (Ty, int, TyVar [])  // quantified polymorphic type
 124                | DEFVALty (Ty, Exp)            // default argument.
 125                | NESTEDty (Ty, Ty)             // e.g. Class::type
 126
 127 ///////////////////////////////////////////////////////////////////////////////
 128 //
 129 //  Type constructor.
 130 //
 131 ///////////////////////////////////////////////////////////////////////////////
 132 and TyCon : public MEM
 133                 = POINTERtycon                  // pointer type
 134                 | REFtycon                      // reference type
 135                 | IDtycon (Id)                  // constructor name
 136                 | TUPLEtycon                    // tuple type
 137                 | EXTUPLEtycon                  // explicit tuple type
 138                 | FUNtycon                      // function type
 139                 | TYPEtycon                     // type of type
 140                 | RECORDtycon (List<Id>, Bool)  // record type
 141                 | ARRAYtycon  (Exp)             // array type
 142                 | BITFIELDtycon                 // bitfield type
 143                   { width     : int,            // width of field
 144                     is_signed : Bool = false    // signed extended?
 145                   }
 146                 | DATATYPEtycon                 // algebraic datatype
 147                   { id         : Id,            // name of type
 148                     unit       : int,           // number of unit constructors
 149                     arg        : int,           // number of arg. constructors
 150                     terms      : Cons [],       // constructor descriptors
 151                     tyvars     : TyVars,        // type variables (if any)
 152                     polyty     : Ty,            // polymorphic type scheme
 153                     inherit    : List<Inherit>, // inheritance relation
 154                     qualifiers : TyQual,        // type qualifiers
 155                     opt        : TyOpt,         // optimization flags
 156                     body       : List<Decl>,    // additional declarations
 157                     view_match : Exp,           //
 158                     location   : const Loc *,   // location.
 159                     hierarchy  : DatatypeHierarchy * = 0
 160                   }
 161                 | COLtycon   (CollectionDesc)   // collection type
 162                 | GRAPHtycon (GraphTypeDef *)   // a graph type
 163                 | NODEtycon (NodeDef *)         // a node type
 164                 | EDGEtycon (EdgeDef *)         // an edge type
 165
 166 ///////////////////////////////////////////////////////////////////////////////
 167 //
 168 //  Patterns.
 169 //
 170 ///////////////////////////////////////////////////////////////////////////////
 171 and  Pat : public MEM
 172                = NOpat                               // no pattern
 173                | WILDpat    ()                       // wild card '_'
 174                | INDpat     (Id, int, Ty)            // an index to quantifiers
 175                | POLYpat    (Id, int, Ids, Pat, Exp, Bool) // a pattern scheme
 176                | IDpat      (Id, Ty, Exp)            // pattern variable
 177                | CONSpat    (Cons)                   // constructor pattern
 178                | APPpat     (Pat, Pat)               // pattern application
 179                | TYPEDpat   (Pat, Ty)                // typed pattern
 180                | ASpat      (Id, Pat, Ty, Exp)       // 'as' pattern
 181                | LITERALpat (Literal)                // literal pattern
 182                | CONTEXTpat (Conses, Pat)            // context pattern
 183                | LEXEMEpat  (Id, Ty, int, Cons [])   // lexeme pattern
 184                | ARRAYpat   (List<Pat>, Bool)        // array pattern
 185                | TUPLEpat   (List<Pat>)              // implicit tuple pattern
 186                | EXTUPLEpat (List<Pat>)              // explicit tuple pattern
 187                | RECORDpat  (List<LabPat>, Bool)     // record pattern
 188                | LISTpat    { cons : Cons,           // cons constructor
 189                               nil  : Cons,           // nil constructor
 190                               head : List<Pat>,      // head of list
 191                               tail : Pat             // tail of list
 192                             }                        // list pattern
 193                | VECTORpat  { cons  : Cons,          // constructor info
 194                               len   : Pat,           // length pattern
 195                               array : Pat,           // array pattern
 196                               elements  : List<Pat>, // elements of vector
 197                               head_flex : Bool,      // head flexible?
 198                               tail_flex : Bool       // tail flexible?
 199                             }                        // vector pattern
 200                | APPENDpat  (Pat, Pat, Ty)           // append pattern
 201                | GUARDpat   (Pat, Exp)               // guard pattern
 202                | LOGICALpat (LogicalPat, Pat, Pat = NOpat) // logical patterns
 203                | BACKEDGEpat(int,Id,Pat)             // backedge (for loops)
 204                | UNIFYpat   (Pat,Exp)                // for unification
 205                | MARKEDpat  (Loc, Pat)               // marked with location
 206                public: { Exp selector; Ty ty; }
 207
 208 ///////////////////////////////////////////////////////////////////////////////
 209 //
 210 //  Logical pattern connectives.
 211 //  These are used to alter the standard interpretation of a pattern.
 212 //  For example, ! pat matches iff pat does not match, and so on.
 213 //
 214 ///////////////////////////////////////////////////////////////////////////////
 215 and LogicalPat = NOTpat       // ! pat
 216                | ANDpat       // pat && pat
 217                | ORpat        // pat || pat
 218                | EQUIVpat     // pat equiv: pat
 219                | XORpat       // pat xor: pat
 220                | IMPLIESpat   // pat implies: pat
 221
 222 ///////////////////////////////////////////////////////////////////////////////
 223 //
 224 //  Literal constants.
 225 //
 226 ///////////////////////////////////////////////////////////////////////////////
 227 and Literal : public MEM
 228                   = INTlit    (int)          // integer literal
 229                   | BOOLlit   (Bool)         // boolean literal
 230                   | CHARlit   (char)         // character literal
 231                   | REALlit   (double)       // floating point literal
 232                   | STRINGlit (const char *) // string literal
 233                   | REGEXPlit (const char *) // regular expression literal
 234                   | QUARKlit  (const char *) // quark literal(i.e atom strings)
 235                   | BIGINTlit (const char *) // big integer literal
 236
 237 ///////////////////////////////////////////////////////////////////////////////
 238 //
 239 //  Constructor descriptor.
 240 //
 241 ///////////////////////////////////////////////////////////////////////////////
 242 and Cons : public MEM
 243           = NOcons
 244           | ONEcons
 245             { name           : Id,                 // constructor name
 246               alg_ty         : Ty,                 // algebraic type
 247               cons_ty        : Ty,                 // type of this constructor
 248               ty             : Ty,                 // type of argument
 249               tag            : int,                // tag assigned
 250               print_formats  : PrintFormats,       // printing format
 251               location       : const Loc *,        // location
 252               inherit        : List<Inherit>,      // inheritance relation
 253               body           : List<Decl>,         // additional decls.
 254               opt            : TyOpt,              // optimizations
 255               qual           : TyQual,             // qualifiers
 256               view_predicate : Exp,                // view predicate
 257               view_selectors : Exp [],             // selectors
 258               lexeme_pattern : Pat,                // pattern
 259               class_def      : DatatypeClass * = 0
 260             }
 261
 262 ///////////////////////////////////////////////////////////////////////////////
 263 //
 264 //  Production symbols formats.
 265 //
 266 ///////////////////////////////////////////////////////////////////////////////
 267 and  ProductionSymbol : public Loc
 268          = TERMsym      (char)          // terminal symbol
 269          | TERMSTRINGsym(const char *)  // strings
 270          | TERMREGEXPsym(const char *)  // regular expression
 271          | TOKENsym     (Cons)          // terminal token
 272          | NONTERMsym   (Id)            // non terminal
 273          | POSNONTERMsym(int)           // positional non terminal
 274          | ACTIONsym    (List<Decl>)    // action symbol
 275          | PREDICATEsym (Exp)           // semantic predicate
 276          | PRECsym      (Cons)          // precedence symbol
 277          | ERRORsym     ()              // error terminal
 278          | SPECIALsym   (char)          // special sequence
 279
 280 ///////////////////////////////////////////////////////////////////////////////
 281 //
 282 //  Persistent type id
 283 //
 284 ///////////////////////////////////////////////////////////////////////////////
 285 and Pid : public MEM = PERSISTid  (const char *)
 286                      | PERSISTnone
 287 ///////////////////////////////////////////////////////////////////////////////
 288 //
 289 //  Inheritance
 290 //
 291 ///////////////////////////////////////////////////////////////////////////////
 292 and Inherit : public Loc = INHERIT
 293                            { super_class : Ty,
 294                              scope       : Scope = PUBLICscope,
 295                              qualifiers  : TyQual = QUALnone
 296                            }
 297
 298 ///////////////////////////////////////////////////////////////////////////////
 299 //
 300 //  Pattern laws.
 301 //     Common abbreviations of function, pointer and reference types, etc.
 302 //
 303 ///////////////////////////////////////////////////////////////////////////////
 304 law FUNty (a,b)     = TYCONty(FUNtycon, #[ a, b ])
 305   | POINTERty a     = TYCONty(POINTERtycon, #[ a ])
 306   | REFty     a     = TYCONty(REFtycon, #[ a ])
 307   | TUPLEty   a     = TYCONty(TUPLEtycon, a)
 308   | EXTUPLEty a     = TYCONty(EXTUPLEtycon, a)
 309   | RECORDty(l,f,a) = TYCONty(RECORDtycon(l,f),a)
 310   | ARRAYty(t,e)    = TYCONty(ARRAYtycon(e),#[ t ])
 311   | IDty (id,a)     = TYCONty(IDtycon id, a)
 312   | DATATYPEty(d,a) = TYCONty(DATATYPEtycon d, a)
 313   | BITFIELDty desc = TYCONty(BITFIELDtycon desc, #[])
 314   | TYPEty          = TYCONty(TYPEtycon, #[])
 315   | GRAPHty G       = TYCONty(GRAPHtycon G,_)
 316   | NODEty n        = TYCONty(NODEtycon n,_)
 317   | EDGEty e        = TYCONty(EDGEtycon e,_)
 318
 319   | INTpat    i     = LITERALpat(INTlit i)
 320   | REALpat   r     = LITERALpat(REALlit r)
 321   | BOOLpat   b     = LITERALpat(BOOLlit b)
 322   | CHARpat   c     = LITERALpat(CHARlit c)
 323   | BIGINTpat b     = LITERALpat(BIGINTlit b)
 324   | STRINGpat s     = LITERALpat(STRINGlit s)
 325   | QUARKpat  q     = LITERALpat(QUARKlit q)
 326   | REGEXPpat re    = LITERALpat(REGEXPlit re)
 327
 328 ///////////////////////////////////////////////////////////////////////////////
 329 //
 330 //  Miscellaneous type abbreviations.
 331 //
 332 ///////////////////////////////////////////////////////////////////////////////
 333 where type TyQual       = int   // qualifier flags
 334 and        TyOpt        = int   // optimizer flags
 335 and        LabTy        = { label : Id, ty : Ty }
 336 and        LabPat       = { label : Id, pat : Pat }
 337 and        Inherits     = List<Inherit>
 338 and        Conses       = List<Cons>
 339 and        Tys          = List<Ty>
 340 and        LabTys       = List<LabTy>
 341 and        Pats         = List<Pat>
 342 and        LabPats      = List<LabPat>
 343 and        TyVar        = Id
 344 and        TyVars       = List<TyVar>
 345 and        PrintFormats = List<ProductionSymbol>
 346 ;
 347
 348 ///////////////////////////////////////////////////////////////////////////////
 349 //
 350 //  Pretty printing methods
 351 //
 352 ///////////////////////////////////////////////////////////////////////////////
 353 extern std::ostream& operator << (std::ostream&, Ids);
 354 extern std::ostream& operator << (std::ostream&, Scope);
 355 extern std::ostream& operator << (std::ostream&, Ty);
 356 extern std::ostream& operator << (std::ostream&, List<Ty>);
 357 extern std::ostream& operator << (std::ostream&, Pat);
 358 extern std::ostream& operator << (std::ostream&, LabPat);
 359 extern std::ostream& operator << (std::ostream&, List<Pat>);
 360 extern std::ostream& operator << (std::ostream&, List<LabPat>);
 361 extern std::ostream& operator << (std::ostream&, Literal);
 362 extern std::ostream& operator << (std::ostream&, Inherit);
 363 extern std::ostream& operator << (std::ostream&, List<Inherit>);
 364 extern std::ostream& operator << (std::ostream&, Pid);
 365 extern std::ostream& print_cons (std::ostream&, Cons);
 366 extern void     print_parameter (std::ostream&, Ty, Id, Parameter);
 367 extern void     print_tyvars    (std::ostream&, TyVars, char, char, Bool);
 368 extern Id       index_of (int, Id = 0);
 369
 370 #endif