zeta/typesub.c

   1 #include "a.h"
   2 #include "type.h"
   3 #include "runtime.h"
   4 #include "grammar.h"
   5
   6 // Can nil be used as this type?
   7 // It's safe for nil to be used as any type--zero is the initial
   8 // value for all variables--but we want to avoid weirdness
   9 // like using nil as a bool or number.
  10 int
  11 nillable(TypeOp op)
  12 {
  13         return op == TypeString ||
  14                 op == TypeTuple ||
  15                 op == TypeList ||
  16                 op == TypeArray ||
  17                 op == TypeMap ||
  18                 op == TypeFmap ||
  19                 op == TypeFn ||
  20                 op == TypeStruct ||
  21                 op == TypeWrapper ||
  22                 op == TypeNil ||
  23                 op == TypeGram;
  24 }
  25
  26 // Is t1 a subtype of t2?
  27 // Remember that nil (didn't type check) is different from typenil().
  28 int
  29 issubtype(Type *t1, Type *t2)
  30 {
  31         NameL *l1, *l2;
  32
  33         if(t1 == nil || t2 == nil)
  34                 return 0;
  35
  36         if(t1 == t2)
  37                 return 1;
  38         // TypeAny is used when there is no instance of an actual type.
  39         // For example, list [] has type list TypeAny.  Essentially TypeAny
  40         // is a giant wildcard, taking on any type imaginable at any time.
  41         if(t1->op == TypeAny || t2->op == TypeAny)
  42                 return 1;
  43         if(t1->op == TypeNil)
  44                 return nillable(t2->op);
  45         if(t1->op != t2->op)
  46                 return 0;
  47         if(t1->op == TypeStruct){
  48                 for(; t1; t1=t1->super)
  49                         if(t1 == t2)
  50                                 return 1;
  51                 return 0;
  52         }
  53         if(t1->op == TypeGram){
  54                 if(t2->gram == nil)
  55                         return 1;
  56                 if(t1->gram != t2->gram)
  57                         return 0;
  58                 if(t2->sym && t1->sym != t2->sym)
  59                         return 0;
  60                 while(t1->sym)
  61                         t1 = t1->left;
  62                 while(t2->sym)
  63                         t2 = t2->left;
  64                 // t2 must have all of t1's names,
  65                 // unless it is gram+?
  66                 // The lists are in sorted order.
  67                 if(t2->gramx && !t2->gramx->tl && t2->gramx->hd == N("?"))
  68                         return 1;
  69                 l1 = t1->gramx;
  70                 for(l2=t2->gramx; l2; l2=l2->tl)
  71                         if(l1 && l1->hd == l2->hd)
  72                                 l1 = l1->tl;
  73                 if(l1)
  74                         return 0;
  75                 return 1;
  76         }
  77         return 0;
  78 }
  79
  80 // Take minimum of two types.
  81 // Remember that nil (no constraint) is different from typenil().
  82 // Lattice and type theory weenies call this the meet or infimum.
  83 int
  84 typemin(Type *t1, Type *t2, Type **min)
  85 {
  86         if(t1 == nil){
  87                 *min = t2;
  88                 return 0;
  89         }
  90         if(t2 == nil){
  91                 *min = t1;
  92                 return 0;
  93         }
  94
  95         // A constraint t1 says that the desired type needs to be
  96         // t1 or a descendant (subtype) of t1 in the type hiearchy.
  97         // Since the type hierarchy is a tree, the only way to satisfy
  98         // constraints t1 and t2 is if t1 is a subtype of t2 or vice versa.
  99         //
 100         // Actually the hierarchy is not a tree--the expression "nil"
 101         // can be a string or a list or an array, which makes it a dag--
 102         // but since nil is itself a minimum type, that doesn't break anything.
 103         //
 104         // XXX Do we have to treat the grammar types specially in typemin?
 105
 106         if(issubtype(t1, t2)){
 107                 *min = t1;
 108                 return 0;
 109         }
 110         if(issubtype(t2, t1)){
 111                 *min = t2;
 112                 return 0;
 113         }
 114         return -1;
 115 }
 116
 117 static int
 118 isquest(Type *t)
 119 {
 120         return t->gramx && t->gramx->tl == nil && t->gramx->hd == N("?");
 121 }
 122
 123 // Take maximum of two types.  t1==nil or t2==nil means no constraint.
 124 // Remember that nil is different from typenil().
 125 // Lattice and type theory weenies call this the join or supremum.
 126 int
 127 _typemax(Type *t1, Type *t2, Type **max)
 128 {
 129         Type *t;
 130         CfgSym *sym;
 131
 132         // max(nil, x) = x for x = nillable type.
 133         if(t2->op == TypeNil){
 134                 t = t2;
 135                 t2 = t1;
 136                 t1 = t;
 137         }
 138         if(t1->op == TypeNil){
 139                 if(nillable(t2->op)){
 140                         *max = t2;
 141                         return 0;
 142                 }
 143         }
 144
 145         // Many axes for grammar types.
 146         if(t1->op == TypeGram){
 147                 if(t2->op != TypeGram)
 148                         return -1;
 149                 if(t1->gram == nil || t2->gram == nil || t1->gram != t2->gram){
 150                         *max = typegram1(nil, nil);
 151                         return 0;
 152                 }
 153                 sym = nil;
 154                 if(t1->sym == t2->sym)
 155                         sym = t1->sym;
 156                 t1 = typegramsym(t1, nil, nil);
 157                 t2 = typegramsym(t2, nil, nil);
 158                 if(t1 == t2){
 159                         assert(sym == nil);
 160                         *max = t1;
 161                         return 0;
 162                 }
 163                 if(isquest(t1))
 164                         t = t1;
 165                 else if(isquest(t2))
 166                         t = t2;
 167                 else
 168                         t = typegramx(t1, addNameL(copyNameL(t1->gramx), t2->gramx));
 169                 if(sym)
 170                         t = typegramsym(t, sym->name, sym);
 171                 *max = t;
 172                 return 0;
 173         }
 174
 175         if(t1->op == TypeStruct){
 176                 if(t2->op != TypeStruct)
 177                         return -1;
 178                 for(; t1; t1=t1->super)
 179                         for(t=t2; t; t=t->super)
 180                                 if(t == t1){
 181                                         *max = t1;
 182                                         return 0;
 183                                 }
 184                 return -1;
 185         }
 186
 187         // TODO: More typemax cases go here, as needed.
 188 fprint(2, "no max %T %T\n", t1, t2);
 189
 190         return -1;
 191 }
 192
 193 int
 194 typemax(Type *t1, Type *t2, Type **max)
 195 {
 196         static Hash *h1;
 197         Hash *h2;
 198         Type *t;
 199
 200         if(t1 == nil){
 201                 *max = t2;
 202                 return 0;
 203         }
 204         if(t2 == nil){
 205                 *max = t1;
 206                 return 0;
 207         }
 208         if(t1 == t2){
 209                 *max = t1;
 210                 return 0;
 211         }
 212         if(t1->op == TypeGram && t2->op == TypeGram){
 213                 if(t1->sym != t2->sym){
 214                         while(t1->sym)
 215                                 t1 = t1->left;
 216                         while(t2->sym)
 217                                 t2 = t2->left;
 218                 }
 219                 if(t1 == t2){
 220                         *max = t1;
 221                         return 0;
 222                 }
 223         }
 224
 225         if(h1 == nil)
 226                 h1 = mkhash();
 227         if((h2 = hashget(h1, t1)) == nil)
 228                 hashput(h1, t1, h2 = mkhash());
 229         t = hashget(h2, t2);
 230         if(t){
 231                 *max = t;
 232                 return 0;
 233         }
 234         if(_typemax(t1, t2, max) >= 0){
 235                 hashput(h2, t2, *max);
 236                 return 0;
 237         }
 238         return -1;
 239 }
 240
 241 Type*
 242 typegramadd(Type *t1, Type *t2)
 243 {
 244         Type *t;
 245
 246         if(t1 == nil)
 247                 return t2;
 248         if(t2 == nil)
 249                 return t1;
 250         if(t1->op != TypeGram || t2->op != TypeGram){
 251         NoAdd:
 252                 werrstr("cannot add %T and %T", t1, t2);
 253                 return nil;
 254         }
 255         if(t1->gram == nil || t2->gram == nil || t1->gram != t2->gram)
 256                 goto NoAdd;
 257         t = nil;
 258         if(typemax(t1, t2, &t) < 0)
 259                 goto NoAdd;
 260         return t;
 261 }
 262
 263 Type*
 264 typegramquest(Type *t1)
 265 {
 266         return typegramxl(t1, N("?"), nil);
 267 }