librune/type.c

   1 /*
   2  * TYPE.C
   3  *
   4  * (c)Copyright 1993-2014, Matthew Dillon, All Rights Reserved.  See the
   5  *    COPYRIGHT file at the base of the distribution.
   6  */
   7
   8 #include "defs.h"
   9
  10 Type DynamicLValueType;
  11 Type DynamicRValueType;
  12
  13 Type NumericType;
  14 Type IntegerType;
  15 Type VoidType;
  16 Type BoolType;
  17 Type Int8Type;
  18 Type UInt8Type;
  19 Type Int16Type;
  20 Type UInt16Type;
  21 Type Int32Type;
  22 Type UInt32Type;
  23 Type Int64Type;
  24 Type UInt64Type;
  25
  26 Type IntPtrType;
  27 Type UIntPtrType;
  28 Type OffType;
  29 Type SizeType;
  30 Type SSizeType;
  31
  32 Type Float32Type;
  33 Type Float64Type;
  34 Type Float128Type;
  35
  36 Type CCharType;         /* const char           */
  37 Type StrType;           /* const char *         */
  38 Type CharPtrType;       /* char *               */
  39 Type CharPtrPtrType;    /* char **              */
  40 Type VoidPtrType;       /* void *               */
  41 Type VoidRefType;       /* void @               */
  42 Type CVoidPtrType;      /* const void *         */
  43 Type LVoidPtrType;      /* lvalue void *        */
  44
  45 Type PointerType;       /* generic pointer placeholder */
  46
  47 static List DynamicTypeList = INITLIST(DynamicTypeList);
  48 static List CompoundTypeList = INITLIST(CompoundTypeList);
  49 static List ArgsTypeList = INITLIST(ArgsTypeList);
  50 static List StorageTypeList = INITLIST(StorageTypeList);
  51
  52 void
  53 initType(Type *type, List *list, int op)
  54 {
  55         type->ty_Op = op;
  56         initList(&type->ty_QList);
  57         if (list)
  58                 addTail(list, &type->ty_Node);
  59         type->ty_SQList = list;
  60 }
  61
  62 void
  63 initQualType(Type *type, List *list, int op, int sqflags)
  64 {
  65         initType(type, list, op);
  66         type->ty_SQFlags = sqflags;
  67 }
  68
  69 void
  70 initPtrType(Type *type, Type *ptrto, int sqflags)
  71 {
  72         initQualType(type, &ptrto->ty_QList, TY_PTRTO, sqflags);
  73         type->ty_PtrType.et_Type = ptrto;
  74         type->ty_PtrType.et_RefNull.rs_Type = ptrto;
  75         type->ty_PtrType.et_RefNull.rs_Refs = 1;
  76 }
  77
  78 static void
  79 initRefType(Type *type, Type *refto, int sqflags)
  80 {
  81         initQualType(type, &refto->ty_QList, TY_REFTO, sqflags);
  82         type->ty_RefType.et_Type = refto;
  83         type->ty_RefType.et_RefNull.rs_Type = refto;
  84         type->ty_RefType.et_RefNull.rs_Refs = 1;
  85 }
  86
  87 void
  88 TypeInit(void)
  89 {
  90         initQualType(&DynamicLValueType, &DynamicTypeList,
  91                      TY_DYNAMIC, SF_LVALUE);
  92         initType(&DynamicRValueType, &DynamicTypeList, TY_DYNAMIC);
  93         initType(&NumericType, NULL, TY_UNRESOLVED);
  94         initType(&IntegerType, NULL, TY_UNRESOLVED);
  95         initType(&VoidType, NULL, TY_UNRESOLVED);
  96         initType(&BoolType, NULL, TY_UNRESOLVED);
  97         initType(&Int8Type, NULL, TY_UNRESOLVED);
  98         initType(&UInt8Type, NULL, TY_UNRESOLVED);
  99         initType(&Int16Type, NULL, TY_UNRESOLVED);
 100         initType(&UInt16Type, NULL, TY_UNRESOLVED);
 101         initType(&Int32Type, NULL, TY_UNRESOLVED);
 102         initType(&UInt32Type, NULL, TY_UNRESOLVED);
 103         initType(&Int64Type, NULL, TY_UNRESOLVED);
 104         initType(&UInt64Type, NULL, TY_UNRESOLVED);
 105
 106         initType(&IntPtrType, NULL, TY_UNRESOLVED);
 107         initType(&UIntPtrType, NULL, TY_UNRESOLVED);
 108         initType(&OffType, NULL, TY_UNRESOLVED);
 109         initType(&SizeType, NULL, TY_UNRESOLVED);
 110         initType(&SSizeType, NULL, TY_UNRESOLVED);
 111
 112         initType(&Float32Type, NULL, TY_UNRESOLVED);
 113         initType(&Float64Type, NULL, TY_UNRESOLVED);
 114         initType(&Float128Type, NULL, TY_UNRESOLVED);
 115
 116         initQualType(&CCharType, NULL, TY_UNRESOLVED, SF_CONST);
 117         initPtrType(&StrType, &CCharType, 0);
 118         initPtrType(&CharPtrType, &UInt8Type, 0);
 119         initPtrType(&CharPtrPtrType, &CharPtrType, 0);
 120         initPtrType(&VoidPtrType, &VoidType, 0);
 121         initRefType(&VoidRefType, &VoidType, 0);
 122         initPtrType(&CVoidPtrType, &VoidType, SF_CONST);
 123         initPtrType(&LVoidPtrType, &VoidType, SF_LVALUE);
 124
 125         initType(&PointerType, NULL, TY_UNRESOLVED);
 126
 127         StrTableAlloc("__internal_void", 15, SPECIAL_INTERNAL_VOID);
 128         StrTableAlloc("__internal_bool", 15, SPECIAL_INTERNAL_BOOL);
 129         StrTableAlloc("__internal_int8", 15, SPECIAL_INTERNAL_INT8);
 130         StrTableAlloc("__internal_uint8", 16, SPECIAL_INTERNAL_UINT8);
 131         StrTableAlloc("__internal_int16", 16, SPECIAL_INTERNAL_INT16);
 132         StrTableAlloc("__internal_uint16", 17, SPECIAL_INTERNAL_UINT16);
 133         StrTableAlloc("__internal_int32", 16, SPECIAL_INTERNAL_INT32);
 134         StrTableAlloc("__internal_uint32", 17, SPECIAL_INTERNAL_UINT32);
 135         StrTableAlloc("__internal_int64", 16, SPECIAL_INTERNAL_INT64);
 136         StrTableAlloc("__internal_uint64", 17, SPECIAL_INTERNAL_UINT64);
 137
 138         StrTableAlloc("__internal_float32", 18, SPECIAL_INTERNAL_FLOAT32);
 139         StrTableAlloc("__internal_float64", 18, SPECIAL_INTERNAL_FLOAT64);
 140         StrTableAlloc("__internal_float128", 19, SPECIAL_INTERNAL_FLOAT128);
 141
 142         StrTableAlloc("__internal_pointer", 18, SPECIAL_INTERNAL_POINTER);
 143         StrTableAlloc("__internal_intptr", 17, SPECIAL_INTERNAL_INTPTR);
 144         StrTableAlloc("__internal_uintptr", 18, SPECIAL_INTERNAL_UINTPTR);
 145         StrTableAlloc("__internal_size", 15, SPECIAL_INTERNAL_SIZE);
 146         StrTableAlloc("__internal_ssize", 16, SPECIAL_INTERNAL_SSIZE);
 147         StrTableAlloc("__internal_off", 14, SPECIAL_INTERNAL_OFF);
 148
 149         StrTableAlloc("__internal_numeric", 18, SPECIAL_INTERNAL_NUMERIC);
 150         StrTableAlloc("__internal_integer", 18, SPECIAL_INTERNAL_INTEGER);
 151
 152         StrTableAlloc("__count",        7,      SPECIAL_COUNT);
 153         StrTableAlloc("__data",         6,      SPECIAL_DATA);
 154         StrTableAlloc("__varcount",     10,     SPECIAL_VAR_COUNT);
 155         StrTableAlloc("__vardata",      9,      SPECIAL_VAR_DATA);
 156         StrTableAlloc("__typeid",       8,      SPECIAL_TYPEID);
 157         StrTableAlloc("__typestr",      9,      SPECIAL_TYPESTR);
 158         StrTableAlloc("NULL",           4,      SPECIAL_NULL);
 159 }
 160
 161 int
 162 InternalTypeAttach(Parse *p, int t, Declaration *d)
 163 {
 164         Type *itype = NULL;
 165         int s;
 166
 167         dassert_decl(d, d->d_Op == DOP_TYPEDEF);
 168
 169         if ((s = StrTableSpecial(d->d_Id)) & SPECIALF_INTERNAL) {
 170                 switch(s) {
 171                 case SPECIAL_INTERNAL_VOID:
 172                         itype = &VoidType;
 173                         break;
 174                 case SPECIAL_INTERNAL_BOOL:
 175                         itype = &BoolType;
 176                         break;
 177                 case SPECIAL_INTERNAL_INT8:
 178                         itype = &Int8Type;
 179                         break;
 180                 case SPECIAL_INTERNAL_UINT8:
 181                         itype = &UInt8Type;
 182                         break;
 183                 case SPECIAL_INTERNAL_INT16:
 184                         itype = &Int16Type;
 185                         break;
 186                 case SPECIAL_INTERNAL_UINT16:
 187                         itype = &UInt16Type;
 188                         break;
 189                 case SPECIAL_INTERNAL_INT32:
 190                         itype = &Int32Type;
 191                         break;
 192                 case SPECIAL_INTERNAL_UINT32:
 193                         itype = &UInt32Type;
 194                         break;
 195                 case SPECIAL_INTERNAL_INT64:
 196                         itype = &Int64Type;
 197                         break;
 198                 case SPECIAL_INTERNAL_UINT64:
 199                         itype = &UInt64Type;
 200                         break;
 201
 202                 case SPECIAL_INTERNAL_FLOAT32:
 203                         itype = &Float32Type;
 204                         break;
 205                 case SPECIAL_INTERNAL_FLOAT64:
 206                         itype = &Float64Type;
 207                         break;
 208                 case SPECIAL_INTERNAL_FLOAT128:
 209                         itype = &Float128Type;
 210                         break;
 211
 212                 case SPECIAL_INTERNAL_INTPTR:
 213                         itype = &IntPtrType;
 214                         break;
 215                 case SPECIAL_INTERNAL_UINTPTR:
 216                         itype = &UIntPtrType;
 217                         break;
 218                 case SPECIAL_INTERNAL_OFF:
 219                         itype = &OffType;
 220                         break;
 221                 case SPECIAL_INTERNAL_SIZE:
 222                         itype = &SizeType;
 223                         break;
 224                 case SPECIAL_INTERNAL_SSIZE:
 225                         itype = &SSizeType;
 226                         break;
 227
 228                 case SPECIAL_INTERNAL_POINTER:
 229                         itype = &PointerType;
 230                         break;
 231                 case SPECIAL_INTERNAL_NUMERIC:
 232                         itype = &NumericType;
 233                         break;
 234                 case SPECIAL_INTERNAL_INTEGER:
 235                         itype = &IntegerType;
 236                         break;
 237                 default:
 238                         itype = InternalRegisteredTypeLookup(d->d_Id);
 239                         if (itype == NULL)
 240                                 dassert(0);
 241                         break;
 242                 }
 243         }
 244         if (itype) {
 245                 if (itype->ty_Op != TY_UNRESOLVED) {
 246                         t = LexError(&p->p_Token, TOK_ERR_DUPLICATE_ATTACH);
 247                 } else {
 248                         Type *ntype = d->d_TypedefDecl.ed_Type;
 249
 250                         TypeToQualType(ntype, itype, ntype->ty_SQFlags, NULL);
 251
 252                         /*
 253                          * fixup for const int8 pointers... we did not have
 254                          * a QList to put CCharType on until now.  It will
 255                          * wind up on the SemGroup's sg_ClassList.
 256                          */
 257                         if (itype == &UInt8Type) {
 258                                 TypeToQualType(ntype, &CCharType,
 259                                         ntype->ty_SQFlags | SF_CONST, NULL);
 260                         }
 261                 }
 262         } else {
 263                 t = LexError(&p->p_Token, TOK_ERR_UNRECOGNIZED_ATTACH);
 264         }
 265         return(t);
 266 }
 267
 268 Type *
 269 AllocType(List *list, int op)
 270 {
 271         Type *type = zalloc(sizeof(Type));
 272
 273         initType(type, list, op);
 274         return(type);
 275 }
 276
 277 /*
 278  * XXX match the compound type(s)
 279  *
 280  * May be used to generate a varargs compound type, in which case the
 281  * semgroup may already be resolved.
 282  */
 283 Type *
 284 AllocCompoundType(SemGroup *sg)
 285 {
 286         Type *type;
 287
 288         type = AllocType(&CompoundTypeList, TY_COMPOUND);
 289         type->ty_CompType.et_SemGroup = sg;
 290         dassert((sg->sg_Flags & SGF_RESOLVED) == 0);
 291         return(type);
 292 }
 293
 294 /*
 295  * XXX match the compound type(s)
 296  */
 297 Type *
 298 AllocArgsType(SemGroup *sg)
 299 {
 300         Type *type;
 301
 302         type = AllocType(&ArgsTypeList, TY_ARGS);
 303         type->ty_ArgsType.et_SemGroup = sg;
 304         return(type);
 305 }
 306
 307 Type *
 308 AllocStorageType(runesize_t bytes)
 309 {
 310         Type *type;
 311
 312         for (
 313                 type = getHead(&StorageTypeList);
 314                 type;
 315                 type = getSucc(&StorageTypeList, &type->ty_Node)
 316         ) {
 317                 if (type->ty_Op == TY_STORAGE &&
 318                         type->ty_StorType.et_Bytes == bytes
 319                 ) {
 320                         return(type);
 321                 }
 322         }
 323         type = AllocType(&StorageTypeList, TY_STORAGE);
 324         type->ty_StorType.et_Bytes = bytes;
 325         return(type);
 326 }
 327
 328 Type *
 329 AllocUnresolvedType(SemGroup *isg, SemGroup *sg, string_t *ary, int eatAry)
 330 {
 331         Type *type = NULL;
 332
 333         dassert_semgrp(sg, ary != NULL);
 334
 335         for (
 336                 type = getHead(&sg->sg_ClassList);
 337                 type;
 338                 type = getSucc(&sg->sg_ClassList, &type->ty_Node)
 339         ) {
 340                 int i;
 341
 342                 if (type->ty_Op != TY_UNRESOLVED)
 343                         continue;
 344                 if (type->ty_UnresType.et_ImportSemGroup != isg)
 345                         continue;
 346
 347                 for (i = 0; ary[i]; ++i) {
 348                         if (ary[i] != type->ty_UnresType.et_DottedId[i])
 349                                 break;
 350                 }
 351                 if (ary[i] == NULL &&
 352                     type->ty_UnresType.et_DottedId[i] == NULL) {
 353                         if (eatAry)
 354                                 FreeDotIdAry(ary);
 355                         return(type);
 356                 }
 357         }
 358         type = AllocType((sg ? &sg->sg_ClassList : NULL), TY_UNRESOLVED);
 359         type->ty_UnresType.et_DottedId = ary;
 360         type->ty_UnresType.et_SemGroup = sg;            /* may be NULL */
 361         type->ty_UnresType.et_ImportSemGroup = isg;     /* may be NULL */
 362         return(type);
 363 }
 364
 365 /*
 366  * AllocClassType() - allocate a type representing a the semgroup which
 367  *                      in turn represents (typically) a class.
 368  */
 369 Type *
 370 AllocClassType(List *list, Type *super, SemGroup *sg, int visibility)
 371 {
 372         Type *type;
 373
 374         for (type = getHead(list); type; type = getSucc(list, &type->ty_Node)) {
 375                 if (type->ty_Op == TY_CLASS &&
 376                     type->ty_ClassType.et_SemGroup == sg &&
 377                     type->ty_ClassType.et_Super == super &&
 378                     type->ty_Visibility == visibility
 379                 ) {
 380                         return(type);
 381                 }
 382         }
 383         type = AllocType(list, TY_CLASS);
 384         type->ty_ClassType.et_SemGroup = sg;
 385         type->ty_ClassType.et_Super = super;
 386         type->ty_Visibility = visibility;
 387         return(type);
 388 }
 389
 390 Type *
 391 AllocImportType(List *list, SemGroup *sg, int visibility)
 392 {
 393         Type *type = AllocType(list, TY_IMPORT);
 394
 395         type->ty_ImportType.et_SemGroup = sg;
 396         type->ty_Visibility = visibility;
 397         return(type);
 398 }
 399
 400 Type *
 401 TypeToQualType(Type *otype, Type *ntype, int sqFlags, Exp *exp)
 402 {
 403         /*
 404          * Combine with existing qualifiers, Shortcut if no changes made.
 405          */
 406         if (ntype == NULL &&
 407             sqFlags == otype->ty_SQFlags &&
 408             (exp == NULL || exp == otype->ty_AssExp)
 409         ) {
 410                 return(otype);
 411         }
 412
 413         /*
 414          * See if we already have a matching qualified type (only if storage
 415          * for the new type is not being provided).  Note: the provided storage
 416          * has already been initType()d
 417          */
 418         if (ntype == NULL) {
 419                 for (ntype = getHead(otype->ty_SQList);
 420                      ntype;
 421                      ntype = getSucc(otype->ty_SQList, &ntype->ty_Node)
 422                 ) {
 423                         if (ntype->ty_Op == otype->ty_Op &&
 424                             ntype->ty_SQFlags == sqFlags &&
 425                             (exp == NULL || ntype->ty_AssExp == exp)
 426                         ) {
 427                                 if (SameType(ntype, otype, sqFlags))
 428                                         return(ntype);
 429                         }
 430                 }
 431         }
 432
 433         /*
 434          * Build a new qualified type and set its qualifiers, then duplicate
 435          * appropriate sections of the old type.
 436          */
 437         if (ntype == NULL) {
 438                 ntype = AllocType(otype->ty_SQList, otype->ty_Op);
 439         } else if (ntype->ty_SQList == NULL) {
 440                 ntype->ty_SQList = otype->ty_SQList;
 441                 addTail(ntype->ty_SQList, &ntype->ty_Node);
 442         }
 443
 444         /*
 445          * Set the op and the expression.  Unlike SQFlags, if exp is passed as
 446          * NULL we inherit the old type's default.
 447          *
 448          * The DupExp() call here is special, see DupExp()'s handling of
 449          * ex_Decl.
 450          *
 451          * Normally DupExp() is called during resolution prior to ex_Decl
 452          * being set.  This is the one case where it may be called with
 453          * ex_Decl already set.
 454          */
 455         ntype->ty_Op = otype->ty_Op;
 456         if (exp)
 457                 ntype->ty_AssExp = exp;
 458         else if (otype->ty_AssExp)
 459                 ntype->ty_AssExp = SetDupExp(NULL, otype->ty_AssExp);
 460         ntype->ty_SQFlags = sqFlags;
 461         ntype->ty_Visibility = otype->ty_Visibility;
 462
 463         switch(otype->ty_Op) {
 464         case TY_CLASS:
 465                 ntype->ty_ClassType.et_SemGroup =
 466                         otype->ty_ClassType.et_SemGroup;
 467                 ntype->ty_ClassType.et_Super = otype->ty_ClassType.et_Super;
 468                 break;
 469         case TY_IMPORT:
 470                 ntype->ty_Visibility = otype->ty_Visibility;
 471                 ntype->ty_ImportType.et_SemGroup = otype->ty_ImportType.et_SemGroup;
 472                 break;
 473         case TY_CPTRTO:
 474                 ntype->ty_CPtrType.et_Type = otype->ty_CPtrType.et_Type;
 475                 ntype->ty_CPtrType.et_RefNull.rs_Type =
 476                         ntype->ty_CPtrType.et_Type;
 477                 ntype->ty_CPtrType.et_RefNull.rs_Refs = 1;
 478                 break;
 479         case TY_PTRTO:
 480                 ntype->ty_PtrType.et_Type = otype->ty_PtrType.et_Type;
 481                 ntype->ty_PtrType.et_RefNull.rs_Type =
 482                         ntype->ty_PtrType.et_Type;
 483                 ntype->ty_PtrType.et_RefNull.rs_Refs = 1;
 484                 break;
 485         case TY_REFTO:
 486                 ntype->ty_RefType.et_Type = otype->ty_RefType.et_Type;
 487                 ntype->ty_RefType.et_RefNull.rs_Type =
 488                         ntype->ty_RefType.et_Type;
 489                 ntype->ty_RefType.et_RefNull.rs_Refs = 1;
 490                 break;
 491         case TY_ARYOF:
 492                 /*
 493                  * note: multiple type structures may share the same array size
 494                  * expression in simple qualified-type cases.  YYY XXX bad bad.
 495                  */
 496                 ntype->ty_AryType.et_Type = otype->ty_AryType.et_Type;
 497                 ntype->ty_AryType.et_ArySize = otype->ty_AryType.et_ArySize;
 498                 ntype->ty_AryType.et_SemGroup = otype->ty_AryType.et_SemGroup;
 499                 break;
 500         case TY_COMPOUND:
 501                 ntype->ty_CompType.et_SemGroup = otype->ty_CompType.et_SemGroup;
 502                 break;
 503         case TY_VAR:
 504                 ntype->ty_VarType.et_Type = otype->ty_VarType.et_Type;
 505                 ntype->ty_VarType.et_SemGroup = otype->ty_VarType.et_SemGroup;
 506                 break;
 507         case TY_ARGS:
 508                 ntype->ty_ArgsType.et_SemGroup = otype->ty_ArgsType.et_SemGroup;
 509                 break;
 510         case TY_PROC:
 511                 ntype->ty_ProcType.et_ArgsType = otype->ty_ProcType.et_ArgsType;
 512                 ntype->ty_ProcType.et_RetType = otype->ty_ProcType.et_RetType;
 513                 ntype->ty_ProcType.et_ArgCount = otype->ty_ProcType.et_ArgCount;
 514                 break;
 515         case TY_STORAGE:
 516                 ntype->ty_StorType.et_Bytes = otype->ty_StorType.et_Bytes;
 517                 break;
 518         case TY_DYNAMIC:
 519                 /*
 520                  * It is not legal to qualify a dynamic type other then to
 521                  * add or remove SF_LVALUE.
 522                  */
 523                 dassert(0);
 524                 break;
 525         case TY_UNRESOLVED:
 526                 ntype->ty_UnresType.et_DottedId =
 527                         otype->ty_UnresType.et_DottedId;
 528                 ntype->ty_UnresType.et_SemGroup =
 529                         otype->ty_UnresType.et_SemGroup;
 530                 break;
 531         default:
 532                 dassert_type(otype, 0);
 533         }
 534         return(ntype);
 535 }
 536
 537 /*
 538  * XXX match the procedure type(s)
 539  */
 540 Type *
 541 TypeToProcType(Type *rtype, Type *atype)
 542 {
 543         Type *type;
 544         int count = 0;
 545         Declaration *d;
 546         SemGroup *sg;
 547
 548         dassert_type(atype, atype->ty_Op == TY_ARGS);
 549         sg = atype->ty_CompType.et_SemGroup;
 550
 551         for (
 552                 d = getHead(&sg->sg_DeclList);
 553                 d;
 554                 d = getSucc(&sg->sg_DeclList, &d->d_Node)
 555         ) {
 556                 ++count;
 557         }
 558         for (
 559                 type = getHead(&rtype->ty_QList);
 560                 type;
 561                 type = getSucc(&rtype->ty_QList, &type->ty_Node)
 562         ) {
 563                 if (type->ty_Op == TY_PROC) {
 564                         if (type->ty_ProcType.et_ArgsType == atype &&
 565                             type->ty_ProcType.et_RetType == rtype &&
 566                             type->ty_ProcType.et_ArgCount == count
 567                         ) {
 568                                 puts("SG1"); /* YYY */
 569                                 return(type);
 570                         }
 571                 }
 572         }
 573         type = AllocType(&rtype->ty_QList, TY_PROC);
 574         type->ty_ProcType.et_ArgsType = AllocArgsType(sg);
 575         type->ty_ProcType.et_RetType = rtype;
 576         type->ty_ProcType.et_ArgCount = count;
 577         return(type);
 578 }
 579
 580 /*
 581  * Convert type to pointer-to-type
 582  */
 583 Type *
 584 TypeToPtrType(Type *otype)
 585 {
 586         Type *type;
 587
 588         for (type = getHead(&otype->ty_QList);
 589              type;
 590              type = getSucc(&otype->ty_QList, &type->ty_Node)
 591         ) {
 592                 if (type->ty_Op == TY_PTRTO)
 593                         return(type);
 594         }
 595         type = AllocType(&otype->ty_QList, TY_PTRTO);
 596         type->ty_PtrType.et_Type = otype;
 597         type->ty_PtrType.et_RefNull.rs_Type = otype;
 598         type->ty_PtrType.et_RefNull.rs_Refs = 1;
 599         return(type);
 600 }
 601
 602 /*
 603  * Convert type to pointer-to-type
 604  */
 605 Type *
 606 TypeToCPtrType(Type *otype)
 607 {
 608         Type *type;
 609
 610         for (type = getHead(&otype->ty_QList);
 611              type;
 612              type = getSucc(&otype->ty_QList, &type->ty_Node)
 613         ) {
 614                 if (type->ty_Op == TY_CPTRTO)
 615                         return(type);
 616         }
 617         type = AllocType(&otype->ty_QList, TY_CPTRTO);
 618         type->ty_CPtrType.et_Type = otype;
 619         type->ty_CPtrType.et_RefNull.rs_Type = otype;
 620         type->ty_CPtrType.et_RefNull.rs_Refs = 1;
 621         return(type);
 622 }
 623
 624 /*
 625  * Convert type to ref-to-type
 626  *
 627  *      A reference type is similar to a pointer type except that the
 628  *      resolver is not able to entirely know what it is pointing to.
 629  *      The reference type is a superclass, but the actual type is
 630  *      stored in the run-time structure.
 631  */
 632 Type *
 633 TypeToRefType(Type *otype)
 634 {
 635         Type *type;
 636
 637         for (type = getHead(&otype->ty_QList);
 638              type;
 639              type = getSucc(&otype->ty_QList, &type->ty_Node)
 640         ) {
 641                 if (type->ty_Op == TY_REFTO)
 642                         return(type);
 643         }
 644         type = AllocType(&otype->ty_QList, TY_REFTO);
 645         type->ty_RefType.et_Type = otype;
 646         type->ty_RefType.et_RefNull.rs_Type = otype;
 647         type->ty_RefType.et_RefNull.rs_Refs = 1;
 648         return(type);
 649 }
 650
 651 Type *
 652 TypeToAryType(Type *otype, Exp *exp, SemGroup *sg)
 653 {
 654         Type *type;
 655
 656         /*
 657          * XXX handle constant expression optimization for QList
 658          * XXX handle qualifiers
 659          */
 660         type = AllocType(&otype->ty_QList, TY_ARYOF);
 661         type->ty_AryType.et_ArySize = exp;
 662         type->ty_AryType.et_Type = DelTypeQual(otype, SF_MASK_ARY_INHERIT);
 663         type->ty_AryType.et_SemGroup = sg;
 664         type->ty_SQFlags |= otype->ty_SQFlags & SF_MASK_ARY_INHERIT;
 665         return(type);
 666 }
 667
 668 #if 0
 669
 670 Type *
 671 TypeToRunTimeAryType(Type *otype, int count)
 672 {
 673         Type *type;
 674         Type *t2 = DelTypeQual(otype, SF_MASK_ARY_INHERIT);
 675
 676         for (type = getHead(&otype->ty_QList);
 677              type;
 678              type = getSucc(&otype->ty_QList, &type->ty_Node)
 679         ) {
 680                 if (type->ty_Op == TY_ARYOF &&
 681                         type->ty_AryType.et_Type == t2 &&
 682                         type->ty_AryType.et_Count == count &&
 683                         type->ty_SQFlags ==
 684                          (otype->ty_SQFlags & SF_MASK_ARY_INHERIT)
 685                 ) {
 686                         return(type);
 687                 }
 688         }
 689         type = AllocType(&otype->ty_QList, TY_ARYOF);
 690         type->ty_AryType.et_Count = count;
 691         type->ty_AryType.et_Type = t2;
 692         type->ty_SQFlags |= otype->ty_SQFlags & SF_MASK_ARY_INHERIT;
 693         return(type);
 694 }
 695
 696 #endif
 697
 698 Type *
 699 TypeToVarType(Type *otype, SemGroup *sg)
 700 {
 701         Type *type;
 702
 703         dassert(sg->sg_Flags & SGF_RESOLVED);
 704         dassert(otype->ty_Flags & TF_RESOLVED);
 705
 706         for (type = getHead(&otype->ty_QList);
 707              type;
 708              type = getSucc(&otype->ty_QList, &type->ty_Node)
 709         ) {
 710                 if (type->ty_Op == TY_VAR &&
 711                     type->ty_VarType.et_Type == otype &&
 712                     type->ty_VarType.et_SemGroup == sg
 713                 ) {
 714                         puts("SG2"); /* YYY */
 715                         return(type);
 716                 }
 717         }
 718         type = AllocType(&otype->ty_QList, TY_VAR);
 719         type->ty_VarType.et_Type = otype;
 720         type->ty_VarType.et_SemGroup = sg;
 721 #if 0
 722         /* XXX doesn't work for var-args */
 723         if (sg->sg_Flags & SGF_RESOLVED) {
 724                 type->ty_Flags |= TF_RESOLVED;
 725                 type->ty_Bytes = sg->sg_Bytes;
 726                 type->ty_AlignMask = sg->sg_AlignMask;
 727         }
 728 #endif
 729         return(type);
 730 }
 731
 732 /*
 733  * ChangeType() - given pointer, C pointer, or array of something,
 734  *                return 'op' of something instead.
 735  */
 736 Type *
 737 ChangeType(Type *type, int op)
 738 {
 739         switch(type->ty_Op) {
 740         case TY_PTRTO:
 741                 switch(op) {
 742                 case TY_CPTRTO:
 743                         type = TypeToCPtrType(type->ty_PtrType.et_Type);
 744                         break;
 745                 case TY_ARYOF:
 746                         type = TypeToAryType(type->ty_PtrType.et_Type,
 747                                              NULL, NULL);
 748                         break;
 749                 default:
 750                         dassert(0);
 751                 }
 752                 break;
 753         case TY_CPTRTO:
 754                 switch(op) {
 755                 case TY_PTRTO:
 756                         type = TypeToPtrType(type->ty_CPtrType.et_Type);
 757                         break;
 758                 case TY_ARYOF:
 759                         type = TypeToAryType(type->ty_CPtrType.et_Type,
 760                                              NULL, NULL);
 761                         break;
 762                 default:
 763                         dassert(0);
 764                 }
 765                 break;
 766         case TY_ARYOF:
 767                 switch(op) {
 768                 case TY_PTRTO:
 769                         type = TypeToPtrType(type->ty_AryType.et_Type);
 770                         break;
 771                 case TY_CPTRTO:
 772                         type = TypeToCPtrType(type->ty_AryType.et_Type);
 773                         break;
 774                 default:
 775                         dassert(0);
 776                 }
 777                 break;
 778         default:
 779                 dassert(0);
 780         }
 781         return(type);
 782 }
 783
 784 /*
 785  * BaseType() - return base type
 786  *
 787  *      Traverse the type to locate the base type.  Store the base type
 788  *      in *ptype and return the SemGroup, or return NULL if the base type
 789  *      does not have a SemGroup.
 790  */
 791 SemGroup *
 792 BaseType(Type **ptype)
 793 {
 794         Type *type = *ptype;
 795
 796         for (;;) {
 797                 switch(type->ty_Op) {
 798                 case TY_CPTRTO:
 799                         type = type->ty_CPtrType.et_Type;
 800                         continue;
 801                 case TY_PTRTO:
 802                         type = type->ty_PtrType.et_Type;
 803                         continue;
 804                 case TY_REFTO:
 805                         type = type->ty_RefType.et_Type;
 806                         continue;
 807                 case TY_ARYOF:
 808                         type = type->ty_AryType.et_Type;
 809                         continue;
 810                 }
 811                 break;
 812         }
 813
 814         *ptype = type;
 815
 816         switch(type->ty_Op) {
 817         case TY_CLASS:
 818                 return(type->ty_ClassType.et_SemGroup);
 819         case TY_COMPOUND:
 820                 return(type->ty_CompType.et_SemGroup);
 821         case TY_ARGS:
 822                 return(type->ty_ArgsType.et_SemGroup);
 823         case TY_PROC:
 824         case TY_VAR:
 825         case TY_DYNAMIC:
 826         case TY_STORAGE:
 827                 return(NULL);
 828         case TY_UNRESOLVED:
 829         default:
 830                 dassert_type(type, 0);
 831                 return(NULL);   /* avoid compiler complaints */
 832         }
 833 }
 834
 835 /*
 836  * MatchType() -        Match two types
 837  *
 838  *      Match two types as if we wanted to cast type to super or use
 839  *      type as super.
 840  *
 841  *      SG_COMPAT_FULL          Type is a subclass, methods and storage are
 842  *                              compatible (storage may be extended).
 843  *
 844  *      SG_COMPAT_PART          Type is a subclass, methods are compatible
 845  *                              but storage is not.
 846  *
 847  *      SG_COMPAT_SUBCLASS      Type is a subclass, but the methods are
 848  *                              not directly compatible (the methods that
 849  *                              propogate down must be regenerated).
 850  *      SG_COMPAT_FAIL          Type is not even a subclass
 851  *
 852  *      XXX we are skipping qualifiers
 853  */
 854 int
 855 MatchType(Type *super, Type *type)
 856 {
 857         int r = SG_COMPAT_FULL;
 858
 859         while (super && type) {
 860                 SemGroup *sg1 = NULL;
 861                 SemGroup *sg2 = NULL;
 862
 863                 if (type->ty_Op != super->ty_Op) {
 864                         if (super->ty_Op == TY_REFTO &&
 865                             type->ty_Op == TY_PTRTO) {
 866                                 super = super->ty_RefType.et_Type;
 867                                 type = type->ty_PtrType.et_Type;
 868                                 r = MatchType(super, type);
 869                         } else {
 870                                 r = SG_COMPAT_FAIL;
 871                         }
 872                         break;
 873                 }
 874
 875                 /*
 876                  * Relaxed storage qualifiers.  The less refined target type
 877                  * (super) can omit certain storage qualifiers and still match.
 878                  *
 879                  * NOTE: Actual casts may do more stringent tests.
 880                  */
 881                 if (super->ty_SQFlags != type->ty_SQFlags) {
 882                         if ((super->ty_SQFlags & ~(SF_LVALUE)) !=
 883                             (type->ty_SQFlags & ~SF_RELAXING_MASK)) {
 884                                 r = SG_COMPAT_FAIL;
 885                                 break;
 886                         }
 887                 }
 888
 889                 switch(super->ty_Op) {
 890                 case TY_CLASS:
 891                         /*
 892                          * type can be a subclass of super
 893                          */
 894                         if (type->ty_ClassType.et_SemGroup ==
 895                             super->ty_ClassType.et_SemGroup) {
 896                                 return(r);
 897                         }
 898                         r = type->ty_ClassType.et_SemGroup->sg_Compat;
 899 #if 0
 900                         if (r < SG_COMPAT_PART)
 901                                 r = SG_COMPAT_PART;
 902 #endif
 903                         while ((type = type->ty_ClassType.et_Super) != NULL) {
 904                                 if (type->ty_ClassType.et_SemGroup ==
 905                                     super->ty_ClassType.et_SemGroup) {
 906                                         break;
 907                                 }
 908                                 if (r < type->ty_ClassType.et_SemGroup->sg_Compat)
 909                                         r = type->ty_ClassType.et_SemGroup->sg_Compat;
 910                         }
 911                         if (type == NULL)       /* not even a subclass */
 912                                 r = SG_COMPAT_FAIL;
 913                         break;
 914                 case TY_IMPORT:
 915                         /*
 916                          * type can be a subclass of super
 917                          */
 918                         if (type != super)
 919                                 r = SG_COMPAT_FAIL;
 920                         break;
 921                 case TY_CPTRTO:
 922                         type = type->ty_CPtrType.et_Type;
 923                         super = super->ty_CPtrType.et_Type;
 924                         continue;
 925                 case TY_PTRTO:
 926                         type = type->ty_PtrType.et_Type;
 927                         super = super->ty_PtrType.et_Type;
 928                         continue;
 929                 case TY_REFTO:
 930                         type = type->ty_RefType.et_Type;
 931                         super = super->ty_RefType.et_Type;
 932                         continue;
 933                 case TY_ARYOF:
 934                         type = type->ty_AryType.et_Type;
 935                         super = super->ty_AryType.et_Type;
 936                         /* XXX */
 937                         continue;
 938                 case TY_COMPOUND:
 939                         sg1 = super->ty_CompType.et_SemGroup;
 940                         sg2 = type->ty_CompType.et_SemGroup;
 941                         break;
 942                 case TY_ARGS:
 943                         sg1 = super->ty_ArgsType.et_SemGroup;
 944                         sg2 = type->ty_ArgsType.et_SemGroup;
 945                         break;
 946                 case TY_VAR:
 947                         r = MatchType(super->ty_VarType.et_Type,
 948                                       type->ty_VarType.et_Type);
 949                         break;
 950                 case TY_PROC:
 951                         {
 952                                 int v;
 953
 954                                 r = MatchType(super->ty_ProcType.et_ArgsType,
 955                                               type->ty_ProcType.et_ArgsType);
 956                                 v = MatchType(super->ty_ProcType.et_RetType,
 957                                               type->ty_ProcType.et_RetType);
 958                                 if (r < v)
 959                                         r = v;
 960                         }
 961                         break;
 962                 case TY_DYNAMIC:
 963                         break;
 964                 case TY_STORAGE:
 965                         if (type->ty_StorType.et_Bytes !=
 966                             super->ty_StorType.et_Bytes) {
 967                                 r = SG_COMPAT_SUBCLASS;
 968                         }
 969                         break;
 970                 case TY_UNRESOLVED:
 971                 default:
 972                         dassert_type(super, 0); /* can't happen */
 973                         break;
 974                 }
 975                 if (sg1) {
 976                         Declaration *sd = getHead(&sg1->sg_DeclList);
 977                         Declaration *rd = getHead(&sg2->sg_DeclList);
 978                         while (sd && rd) {
 979                                 int v = MatchDeclTypes(sd, rd);
 980                                 if (r < v)
 981                                         r = v;
 982                                 if (r == SG_COMPAT_FAIL)
 983                                         break;
 984                                 sd = getSucc(&sg1->sg_DeclList, &sd->d_Node);
 985                                 rd = getSucc(&sg2->sg_DeclList, &rd->d_Node);
 986                         }
 987                         if (sd || rd)
 988                                 r = SG_COMPAT_FAIL;
 989                 }
 990                 break;
 991         }
 992         return(r);
 993 }
 994
 995 /*
 996  * DupType()     - create a duplicate of a type, possibly in a new SemGroup.
 997  *
 998  *      This code is used when duplicating procedures and other elements
 999  *      when merging a superclass into a subclass.
1000  *
1001  *      If sg is NULL, stype is simply returned.  The case is used when we
1002  *      try to duplciate an expression with DupExp()... in that case we
1003  *      want to dup the expression tree but use the same types.
1004  */
1005 Type *
1006 DupType(SemGroup *sg, Type *stype)
1007 {
1008         Type *type = NULL;
1009
1010         if (sg == NULL)
1011                 return(stype);
1012
1013         /*
1014          * XXX type may be resolved if it is part of a varargs dup
1015          */
1016 #if 0
1017         dassert_type(stype,
1018                      (stype->ty_Flags & (TF_RESOLVED|TF_RESOLVING)) == 0);
1019 #endif
1020
1021         switch(stype->ty_Op) {
1022         case TY_CLASS:
1023                 /*
1024                  * This only occurs because the resolver has resolved an
1025                  * unresolved type on the original SemGroup.  We duplicate
1026                  * that on the new SemGroup.
1027                  */
1028                 type = AllocClassType(&sg->sg_ClassList,
1029                                       stype->ty_ClassType.et_Super,
1030                                       stype->ty_ClassType.et_SemGroup,
1031                                       stype->ty_Visibility);
1032                 break;
1033         case TY_IMPORT:
1034         case TY_DYNAMIC:
1035                 type = stype;
1036                 break;
1037         case TY_CPTRTO:
1038                 type = TypeToCPtrType(DupType(sg, stype->ty_CPtrType.et_Type));
1039                 break;
1040         case TY_PTRTO:
1041                 type = TypeToPtrType(DupType(sg, stype->ty_PtrType.et_Type));
1042                 break;
1043         case TY_REFTO:
1044                 type = TypeToRefType(DupType(sg, stype->ty_RefType.et_Type));
1045                 break;
1046         case TY_ARYOF:
1047                 type = TypeToAryType(DupType(sg, stype->ty_AryType.et_Type),
1048                                 SetDupExp(sg, stype->ty_AryType.et_ArySize),
1049                                 stype->ty_AryType.et_SemGroup);
1050                 break;
1051         case TY_VAR:
1052                 type = TypeToVarType(DupType(sg, stype->ty_VarType.et_Type),
1053                                 DupSemGroup(sg, NULL,
1054                                             stype->ty_VarType.et_SemGroup, 1));
1055                 break;
1056         case TY_COMPOUND:
1057                 type = AllocCompoundType(
1058                                 DupSemGroup(sg, NULL,
1059                                             stype->ty_CompType.et_SemGroup, 1));
1060                 break;
1061         case TY_ARGS:
1062                 /*
1063                  * At the moment we always formally duplicate the arguments
1064                  * so we can modify them for methods below.
1065                  */
1066                 type = AllocArgsType(
1067                                 DupSemGroup(sg, NULL,
1068                                             stype->ty_CompType.et_SemGroup, 1));
1069                 break;
1070         case TY_PROC:
1071                 type = DupType(sg, stype->ty_ProcType.et_RetType);
1072                 type = TypeToProcType(type,
1073                                       DupType(sg,
1074                                               stype->ty_ProcType.et_ArgsType));
1075
1076                 /*
1077                  * If this is a method procedure, we have to change the
1078                  * first argument to point at our new subclass.  It was
1079                  * previously pointing at our superclass.   XXX the
1080                  * programmer can override the argument.  If it isn't a
1081                  * reference we have to assert.
1082                  */
1083                 if (stype->ty_SQFlags & SF_METHOD) {
1084                         SemGroup *asg = type->ty_ProcType.et_ArgsType->ty_ArgsType.et_SemGroup;
1085                         Declaration *d = getHead(&asg->sg_DeclList);
1086                         Type *thisType = d->d_StorDecl.ed_Type;
1087
1088                         dassert_decl(d, d->d_Id == String_This &&
1089                                         d->d_Op == DOP_ARGS_STORAGE);
1090                         dassert_decl(d, sg->sg_Stmt->st_Op == ST_Class);
1091                         if (thisType->ty_Op == TY_CLASS) {
1092                                 /* XXX sg_ClassList? right sg? */
1093                                 /* XXX correct visibility? */
1094                                 if (d->d_Search == NULL) {
1095                                         d->d_Search = d->d_StorDecl.ed_Type->
1096                                                       ty_ClassType.et_SemGroup;
1097                                 }
1098                                 d->d_StorDecl.ed_Type =
1099                                         AllocClassType(&sg->sg_ClassList,
1100                                                        sg->sg_Stmt->st_ClassStmt.es_Super,
1101                                                        sg->sg_Stmt->st_MyGroup,
1102                                                        SCOPE_ALL_VISIBLE);
1103                         } else {
1104                                 dassert_decl(d, thisType->ty_Op == TY_REFTO);
1105                         }
1106                 } else if (stype->ty_SQFlags & SF_GMETHOD) {
1107                         SemGroup *asg;
1108                         Declaration *d;
1109
1110                         asg = type->ty_ProcType.et_ArgsType->
1111                                 ty_ArgsType.et_SemGroup;
1112                         d = getHead(&asg->sg_DeclList);
1113
1114                         dassert_decl(d, d->d_Id == String_This &&
1115                                      d->d_Op == DOP_TYPEDEF);
1116                         dassert_decl(d, sg->sg_Stmt->st_Op == ST_Class);
1117                         dassert_decl(d, d->d_TypedefDecl.ed_Type->ty_Op ==
1118                                         TY_CLASS);
1119                         /* XXX sg_ClassList? right sg? */
1120                         /* XXX correct visibility? */
1121                         if (d->d_Search == NULL) {
1122                                 d->d_Search = d->d_TypedefDecl.ed_Type->
1123                                                ty_ClassType.et_SemGroup;
1124                         }
1125                         d->d_TypedefDecl.ed_Type =
1126                                 AllocClassType(&sg->sg_ClassList,
1127                                                sg->sg_Stmt->st_ClassStmt.es_Super,
1128                                                sg->sg_Stmt->st_MyGroup,
1129                                                SCOPE_ALL_VISIBLE);
1130                 }
1131                 break;
1132         case TY_STORAGE:
1133                 type = stype;
1134                 break;
1135         case TY_UNRESOLVED:
1136                 /*
1137                  * e.g. so elements in a superclass will see refined elements
1138                  * in the subclass.  Note that the original import semgroup
1139                  * is left intact so the semantic search mechanism uses it
1140                  * when the base sg (typically a subclass) fails.
1141                  */
1142                 type = AllocUnresolvedType(
1143                                 stype->ty_UnresType.et_ImportSemGroup,
1144                                 sg,
1145                                 stype->ty_UnresType.et_DottedId,
1146                                 0);
1147                 break;
1148         default:
1149                 dassert_type(stype, 0);
1150         }
1151
1152         if (type != stype) {
1153                 type->ty_Flags = stype->ty_Flags;
1154                 type->ty_Bytes = stype->ty_Bytes;
1155                 type->ty_AlignMask = stype->ty_AlignMask;
1156                 type->ty_Visibility = stype->ty_Visibility;
1157         }
1158         if (stype->ty_AssExp || stype->ty_SQFlags != type->ty_SQFlags) {
1159                 type = TypeToQualType(type, NULL,
1160                                       stype->ty_SQFlags,
1161                                       SetDupExp(sg, stype->ty_AssExp));
1162         }
1163
1164         return(type);
1165 }
1166
1167 /*
1168  * SameType() - return 1 if the types are equilvalent, 0 if they are not.
1169  *
1170  *      The sqFlags for t2 may be overriden.  If you do not wish to override
1171  *      the sqFlags for t2, pass t2->ty_SQFlags for sqFlags.  The override
1172  *      only applies to the top level of the type.
1173  *
1174  *      Types can be aliased - for example, two different type structures
1175  *      may point to the same class data.
1176  *
1177  *      XXX this needs a lot of work.  We really need to guarentee
1178  *      some level of uniqueness for non-qualified type elements.
1179  */
1180 int
1181 SameType(Type *t1, Type *t2, int sqFlags2)
1182 {
1183         for (;;) {
1184                 if (t1 == t2)
1185                         return(1);
1186                 if (t1->ty_Op != t2->ty_Op)
1187                         break;
1188                 if (t1->ty_SQFlags != sqFlags2)
1189                         break;
1190                 switch(t1->ty_Op) {
1191                 case TY_IMPORT:
1192                         if (t1->ty_ImportType.et_SemGroup ==
1193                             t2->ty_ImportType.et_SemGroup)
1194                         {
1195                                 return(1);
1196                         }
1197                         return(0);
1198                 case TY_CLASS:
1199                         if (t1->ty_ClassType.et_SemGroup ==
1200                              t2->ty_ClassType.et_SemGroup &&
1201                             t1->ty_ClassType.et_Super ==
1202                              t2->ty_ClassType.et_Super)
1203                         {
1204                                 return(1);
1205                         }
1206                         return(0);
1207                 case TY_CPTRTO:
1208                         t1 = t1->ty_CPtrType.et_Type;
1209                         t2 = t2->ty_CPtrType.et_Type;
1210                         break;
1211                 case TY_PTRTO:
1212                         t1 = t1->ty_PtrType.et_Type;
1213                         t2 = t2->ty_PtrType.et_Type;
1214                         break;
1215                 case TY_REFTO:
1216                         t1 = t1->ty_RefType.et_Type;
1217                         t2 = t2->ty_RefType.et_Type;
1218                         break;
1219                 case TY_ARYOF:
1220                 case TY_VAR:
1221                 case TY_COMPOUND:
1222                 case TY_PROC:
1223                         /* XXX */
1224                         return(0);
1225                 case TY_STORAGE:
1226                 case TY_ARGS:
1227                 case TY_UNRESOLVED:
1228                 case TY_DYNAMIC:
1229                         /* XXX */
1230                         return(0);
1231                 default:
1232                         dassert_type(t1, 0);
1233                         return(0);
1234                 }
1235                 sqFlags2 = t2->ty_SQFlags;
1236         }
1237         return(0);
1238 }
1239
1240 /*
1241  * SimilarType() - like SameType(), but ignores storage qualifiers and
1242  *                 if t2 is varargs, compares the original version.
1243  *
1244  *    Used when casting t2 (rhs) to t1 (lhs).
1245  */
1246 int
1247 SimilarType(Type *t1, Type *t2)
1248 {
1249         if (t2->ty_Op == TY_VAR)
1250                 t2 = t2->ty_VarType.et_Type;
1251         for (;;) {
1252                 if (t1 == t2)
1253                         return(1);
1254 #if 0
1255                 /*
1256                  * Normally we fail if the ops do not match, but it is legal to
1257                  * cast a pointer (t2) to a reference type (t1) if the ref type
1258                  * is its superclass.  It is also legal to cast an array to a
1259                  * pointer or C pointer.
1260                  */
1261                 if (t2->ty_Op != t1->ty_Op) {
1262                         /*
1263                          * pointer->ref
1264                          */
1265                         if (t2->ty_Op == TY_PTRTO && t1->ty_Op == TY_REFTO) {
1266                                 t1 = t1->ty_RefType.et_Type;
1267                                 t2 = t2->ty_PtrType.et_Type;
1268                                 if (MatchType(t1, t2) <= SG_COMPAT_PART) {
1269                                         return(1);
1270                                 }
1271                                 return(0);
1272                         }
1273                         /*
1274                          * array->pointer
1275                          */
1276                         if (t2->ty_Op == TY_ARYOF && t1->ty_Op == TY_PTRTO) {
1277                                 t1 = t1->ty_PtrType.et_Type;
1278                                 t2 = t2->ty_AryType.et_Type;
1279                                 if (MatchType(t1, t2) <= SG_COMPAT_PART) {
1280                                         return(1);
1281                                 }
1282                                 return(0);
1283                         }
1284                         /*
1285                          * array->cpointer
1286                          */
1287                         if (t2->ty_Op == TY_ARYOF && t1->ty_Op == TY_CPTRTO) {
1288                                 t1 = t1->ty_PtrType.et_Type;
1289                                 t2 = t2->ty_AryType.et_Type;
1290                                 if (MatchType(t1, t2) <= SG_COMPAT_PART) {
1291                                         return(1);
1292                                 }
1293                                 return(0);
1294                         }
1295                         break;
1296                 }
1297 #endif
1298                 if (t2->ty_Op != t1->ty_Op)
1299                         break;
1300                 switch(t1->ty_Op) {
1301                 case TY_IMPORT:
1302                         if (t1->ty_ImportType.et_SemGroup ==
1303                             t2->ty_ImportType.et_SemGroup) {
1304                                 return(1);
1305                         }
1306                         return(0);
1307                 case TY_CLASS:
1308                         if (t1->ty_ClassType.et_SemGroup ==
1309                              t2->ty_ClassType.et_SemGroup &&
1310                             t1->ty_ClassType.et_Super ==
1311                              t2->ty_ClassType.et_Super)
1312                         {
1313                                 return(1);
1314                         }
1315                         return(0);
1316                 case TY_CPTRTO:
1317                         t1 = t1->ty_CPtrType.et_Type;
1318                         t2 = t2->ty_CPtrType.et_Type;
1319                         break;
1320                 case TY_PTRTO:
1321                         t1 = t1->ty_PtrType.et_Type;
1322                         t2 = t2->ty_PtrType.et_Type;
1323                         break;
1324                 case TY_REFTO:
1325                         /*
1326                          * Reference types are similar if the lhs is a
1327                          * superclass of the rhs and partially compatible
1328                          * (only method call changes and extensions).
1329                          */
1330                         t1 = t1->ty_RefType.et_Type;
1331                         t2 = t2->ty_RefType.et_Type;
1332                         if (MatchType(t1, t2) <= SG_COMPAT_PART) {
1333                                 return(1);
1334                         }
1335                         return(0);
1336                         break;
1337                 case TY_COMPOUND:
1338                         /*
1339                          * Compare the elements making up the compound type.
1340                          * XXX
1341                          */
1342                         return(SimilarSemGroup(t1->ty_CompType.et_SemGroup,
1343                                                t2->ty_CompType.et_SemGroup));
1344                         break;
1345                 case TY_ARYOF:
1346                 case TY_VAR:
1347                 case TY_PROC:
1348                         /* XXX */
1349                         return(0);
1350                 case TY_STORAGE:
1351                 case TY_ARGS:
1352                 case TY_UNRESOLVED:
1353                 case TY_DYNAMIC:
1354                         /* XXX */
1355                         return(0);
1356                 default:
1357                         dassert_type(t1, 0);
1358                         return(0);
1359                 }
1360         }
1361         return(0);
1362 }
1363
1364 /*
1365  * SimilarSemGroup() - check to see if the storage underlying the two
1366  *                      semantic groups is compatible.
1367  */
1368 int
1369 SimilarSemGroup(SemGroup *s1, SemGroup *s2)
1370 {
1371         Declaration *d1;
1372         Declaration *d2;
1373
1374         if (s1->sg_Bytes != s2->sg_Bytes)
1375                 return(0);
1376         d1 = getHead(&s1->sg_DeclList);
1377         d2 = getHead(&s2->sg_DeclList);
1378         for (;;) {
1379                 while (d1 &&
1380                        ((d1->d_Op & DOPF_STORAGE) == 0 ||
1381                          d1->d_Op == DOP_GLOBAL_STORAGE)
1382                 ) {
1383                         d1 = getSucc(&s1->sg_DeclList, &d1->d_Node);
1384                 }
1385                 while (d2 &&
1386                        ((d2->d_Op & DOPF_STORAGE) == 0 ||
1387                          d2->d_Op == DOP_GLOBAL_STORAGE)
1388                 ) {
1389                         d2 = getSucc(&s2->sg_DeclList, &d2->d_Node);
1390                 }
1391                 if (d1 == NULL || d2 == NULL)
1392                         break;
1393                 if (SimilarType(d1->d_StorDecl.ed_Type,
1394                                 d2->d_StorDecl.ed_Type) == 0) {
1395                         break;
1396                 }
1397                 d1 = getSucc(&s1->sg_DeclList, &d1->d_Node);
1398                 d2 = getSucc(&s2->sg_DeclList, &d2->d_Node);
1399         }
1400         if (d1 || d2)
1401                 return(0);      /* compare bad */
1402         return(1);              /* compare good */
1403 }
1404
1405 char *
1406 TypeToStr(Type *type, char **pstr)
1407 {
1408         char *str = NULL;
1409         char *s1 = NULL;
1410         char *s2 = NULL;
1411         Stmt *st;
1412         SemGroup *sg;
1413         Declaration *d;
1414         int count;
1415         static char *SaveStr[8];
1416         static int SaveIndex;
1417
1418         if (type == NULL) {
1419                 safe_asprintf(&str, "(null)");
1420         } else {
1421                 switch(type->ty_Op) {
1422                 case TY_CLASS:
1423                         st = type->ty_ClassType.et_SemGroup->sg_Stmt;
1424                         dassert(st->st_Op == ST_Class);
1425 #if 0
1426                         safe_asprintf(&str, "CLASS(%s",
1427                                       st->st_ClassStmt.es_Decl->d_Id);
1428 #else
1429                         LexPrintRef(&st->st_LexRef, 0);
1430                         safe_asprintf(&str, "CLASS(%s from",
1431                                 /* type->ty_ClassType.et_SemGroup->sg_Parse, */
1432                                       st->st_ClassStmt.es_Decl->d_Id);
1433                         for (;;) {
1434                                 while (st && st->st_Op != ST_Import)
1435                                         st = st->st_Parent;
1436                                 if (st == NULL)
1437                                         break;
1438                                 safe_replacef(&str, "%s <%s%s>",
1439                                               str,
1440                                               st->st_ImportStmt.es_Path,
1441                                               st->st_ImportStmt.es_File);
1442                                 st = st->st_Parent;
1443                         }
1444 #endif
1445                         safe_replacef(&str, "%s)", str);
1446                         break;
1447                 case TY_IMPORT:
1448                         st = type->ty_ImportType.et_SemGroup->sg_Stmt;
1449                         dassert(st->st_Op == ST_Module);
1450                         safe_asprintf(&str, "IMPORT(%s)",
1451                                       st->st_LexRef.lr_Lex->l_Path);
1452                         break;
1453                 case TY_CPTRTO:
1454                         TypeToStr(type->ty_CPtrType.et_Type, &s1);
1455                         safe_replacef(&str, "(CLANG)*%s", s1);
1456                         break;
1457                 case TY_PTRTO:
1458                         TypeToStr(type->ty_PtrType.et_Type, &s1);
1459                         safe_replacef(&str, "*%s", s1);
1460                         break;
1461                 case TY_REFTO:
1462                         TypeToStr(type->ty_RefType.et_Type, &s1);
1463                         safe_replacef(&str, "@%s", s1);
1464                         break;
1465                 case TY_ARYOF:
1466                         TypeToStr(type->ty_AryType.et_Type, &s1);
1467                         safe_replacef(&str, "%s[]", s1);
1468                         break;
1469                 case TY_COMPOUND:
1470                         sg = type->ty_CompType.et_SemGroup;
1471                         safe_asprintf(&str, "COMPOUND(");
1472                         count = 0;
1473                         for (d = getHead(&sg->sg_DeclList);
1474                              d;
1475                              d = getSucc(&sg->sg_DeclList, &d->d_Node)) {
1476                                 if (d->d_Op & DOPF_STORAGE) {
1477                                         TypeToStr(d->d_StorDecl.ed_Type, &s1);
1478                                         if (count)
1479                                                 safe_replacef(&str, "%s,%s",
1480                                                               str, s1);
1481                                         else
1482                                                 safe_replacef(&str, "%s%s",
1483                                                               str, s1);
1484                                         ++count;
1485                                         safe_free(&s1);
1486                                 }
1487                         }
1488                         safe_replacef(&str, "%s)", str);
1489                         break;
1490                 case TY_VAR:
1491                         safe_replacef(&str, "VAR");
1492                         break;
1493                 case TY_ARGS:
1494                         sg = type->ty_ArgsType.et_SemGroup;
1495                         safe_asprintf(&str, "ARGS(");
1496                         count = 0;
1497                         for (d = getHead(&sg->sg_DeclList);
1498                              d;
1499                              d = getSucc(&sg->sg_DeclList, &d->d_Node)) {
1500                                 if (d->d_Op & DOPF_STORAGE) {
1501                                         TypeToStr(d->d_StorDecl.ed_Type, &s1);
1502                                         if (count)
1503                                                 safe_replacef(&str, "%s,%s",
1504                                                               str, s1);
1505                                         else
1506                                                 safe_replacef(&str, "%s%s",
1507                                                               str, s1);
1508                                         safe_free(&s1);
1509                                         ++count;
1510                                 }
1511                         }
1512                         safe_replacef(&str, "%s)", str);
1513                         break;
1514                 case TY_PROC:
1515                         {
1516                                 TypeToStr(type->ty_ProcType.et_RetType, &s1);
1517                                 TypeToStr(type->ty_ProcType.et_ArgsType, &s2);
1518                                 safe_asprintf(&str, "%s %s", s1, s2);
1519                         }
1520                         break;
1521                 case TY_STORAGE:
1522                         safe_asprintf(&str, "STORAGE(%d)",
1523                                       type->ty_StorType.et_Bytes);
1524                         break;
1525                 case TY_DYNAMIC:
1526                         safe_asprintf(&str, "DYNAMIC");
1527                         break;
1528                 case TY_UNRESOLVED:
1529                         safe_asprintf(&str, "UNRES(");
1530                         for (count = 0; type->ty_UnresType.et_DottedId[count]; ++count) {
1531                                 safe_replacef(&str, "%s%s",
1532                                               str, type->ty_UnresType.et_DottedId[count]);
1533                                 if (count) {
1534                                         safe_replacef(&str, "%s,%s",
1535                                                       str, type->ty_UnresType.et_DottedId[count]);
1536                                 }
1537                         }
1538                         safe_replacef(&str, "%s)", str);
1539                         break;
1540                 default:
1541                         safe_asprintf(&str, "?");
1542                         break;
1543                 }
1544                 if (type->ty_SQFlags) {
1545                         char *sqstr;
1546
1547                         safe_asprintf(&sqstr, "(%s%s%s%s%s%s%s)",
1548                           ((type->ty_SQFlags & SF_CONST) ? "const " : ""),
1549                           ((type->ty_SQFlags & SF_VOLATILE) ? "volatile " : ""),
1550                           ((type->ty_SQFlags & SF_VARARGS) ? "varargs " : ""),
1551                           ((type->ty_SQFlags & SF_LVALUE) ? "lvalue " : ""),
1552                           ((type->ty_SQFlags & SF_NOZERO) ? "__nozero " : ""),
1553                           ((type->ty_SQFlags & SF_METHOD) ? "method " : ""),
1554                           ((type->ty_SQFlags & SF_GMETHOD) ? "global method " : "")
1555                         );
1556                         safe_replacef(&str, "%s%s", sqstr, str);
1557                         free(sqstr);
1558                 }
1559         }
1560         safe_free(&s1);
1561         safe_free(&s2);
1562         if (pstr) {
1563                 safe_free(pstr);
1564                 *pstr = str;
1565         } else {
1566                 safe_free(&SaveStr[SaveIndex]);
1567                 SaveStr[SaveIndex] = str;
1568                 SaveIndex = (SaveIndex + 1) % arysize(SaveStr);
1569         }
1570         return(str);
1571 }
1572
1573 typedef struct TypeRegNode {
1574         Node    tr_Node;
1575         string_t        tr_Id;
1576         Type    *tr_Type;
1577 } TypeRegNode;
1578
1579 List TypeRegList = INITLIST(TypeRegList);
1580
1581 void
1582 InternalRegisterType(const char *str, Type *type)
1583 {
1584         static int Special = SPECIALF_REGISTERED|SPECIALF_INTERNAL|1;
1585         TypeRegNode *tr;
1586
1587         dassert(Special & SPECIALF_MASK);
1588         tr = zalloc(sizeof(TypeRegNode));
1589         tr->tr_Id = StrTableAlloc(str, strlen(str), Special++);
1590         tr->tr_Type = type;
1591         addTail(&TypeRegList, &tr->tr_Node);
1592 }
1593
1594 Type *
1595 InternalRegisteredTypeLookup(string_t id)
1596 {
1597         TypeRegNode *tr;
1598
1599         for (
1600                 tr = getHead(&TypeRegList);
1601                 tr;
1602                 tr = getSucc(&TypeRegList, &tr->tr_Node)
1603         ) {
1604                 if (tr->tr_Id == id)
1605                         return(tr->tr_Type);
1606         }
1607         return(NULL);
1608 }