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