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    USizeType;
  35 Type    SSizeType;
  36
  37 Type    FloatType;              /* generic float placeholder */
  38 Type    Float32Type;
  39 Type    Float64Type;
  40 Type    Float128Type;
  41
  42 Type    PointerType;            /* generic pointer placeholder */
  43 Type    CCharType;              /* const uchar          */
  44 Type    StrType;                /* const uchar *        */
  45 Type    UCharPtrType;           /* uchar *              */
  46 Type    UCharPtrPtrType;        /* uchar **             */
  47 Type    CUCharPtrPtrType;       /* const uchar **       */
  48 Type    VoidPtrType;            /* void *               */
  49 Type    VoidRefType;            /* void @               */
  50 Type    CVoidPtrType;           /* const void *         */
  51 Type    LVoidPtrType;           /* lvalue void *        */
  52
  53 Type    LexRefType;             /* run-time access class tie-ins */
  54 Type    ScopeType;
  55 Type    DeclarationType;
  56 Type    SemGroupType;
  57 Type    PointerInfoType;
  58 Type    TypeType;
  59 Type    FILLERTypeType;
  60 Type    FILLERDeclType;
  61
  62 typelist_t DynamicTypeList = RUNE_HEAD_INITIALIZER(DynamicTypeList);
  63 typelist_t CompoundTypeList = RUNE_HEAD_INITIALIZER(CompoundTypeList);
  64 typelist_t ArgsTypeList = RUNE_HEAD_INITIALIZER(ArgsTypeList);
  65 typelist_t StorageTypeList = RUNE_HEAD_INITIALIZER(StorageTypeList);
  66
  67 static void initInternalClassType(Type *type, Declaration *d);
  68
  69 Type   *BaseTypeAry[] = {
  70     &DynamicLValueType, &DynamicRValueType, &NumericType,
  71     &IntegralType, &SIntegerType, &UIntegerType,
  72     &VoidType, &BoolType, &Int8Type, &UInt8Type,
  73     &Int16Type, &UInt16Type, &Int32Type, &UInt32Type,
  74     &Int64Type, &UInt64Type, &Int128Type, &UInt128Type,
  75
  76     &IntPtrType, &UIntPtrType, &OffType, &USizeType, &SSizeType,
  77
  78     &FloatType, &Float32Type, &Float64Type, &Float128Type,
  79
  80     &PointerType, &CCharType, &StrType, &UCharPtrType,
  81     &UCharPtrPtrType, &CUCharPtrPtrType,
  82     &VoidPtrType, &VoidRefType, &CVoidPtrType,
  83     &LVoidPtrType,
  84
  85     &LexRefType, &ScopeType, &DeclarationType, &SemGroupType,
  86     &PointerInfoType, &TypeType,
  87     &FILLERTypeType, &FILLERDeclType,
  88     NULL
  89 };
  90
  91 void
  92 initType(Type *type, typelist_t *list, int op)
  93 {
  94     type->ty_Op = op;
  95     RUNE_INIT(&type->ty_QList);
  96     if (list)
  97         RUNE_INSERT_TAIL(list, type, ty_Node);
  98     type->ty_SQList = list;
  99     type->ty_Info.in_Type = type;
 100     type->ty_Info.in_Refs = PINFO_STATIC;
 101 }
 102
 103 void
 104 initQualType(Type *type, typelist_t *list, int op, int sqflags)
 105 {
 106     initType(type, list, op);
 107     type->ty_SQFlags = sqflags;
 108 }
 109
 110 void
 111 initPtrType(Type *type, Type *ptrto, int sqflags)
 112 {
 113     initQualType(type, &ptrto->ty_QList, TY_PTRTO, sqflags);
 114     type->ty_PtrType.et_Type = ptrto;
 115     /* type->ty_Bytes = sizeof(PointerStor); */
 116     type->ty_AlignMask = POINTERSTOR_ALIGN;
 117 }
 118
 119 void
 120 initCPtrType(Type *type, Type *ptrto, int sqflags)
 121 {
 122     initQualType(type, &ptrto->ty_QList, TY_CPTRTO, sqflags);
 123     type->ty_PtrType.et_Type = ptrto;
 124     /* type->ty_Bytes = sizeof(void *); */
 125     type->ty_AlignMask = sizeof(void *) - 1;
 126 }
 127
 128 static void
 129 initRefType(Type *type, Type *refto, int sqflags)
 130 {
 131     initQualType(type, &refto->ty_QList, TY_REFTO, sqflags);
 132     type->ty_RefType.et_Type = refto;
 133     /* type->ty_Bytes = sizeof(PointerStor); */
 134     type->ty_AlignMask = POINTERSTOR_ALIGN;
 135 }
 136
 137 void
 138 TypeInit(void)
 139 {
 140     int     i;
 141
 142     initQualType(&DynamicLValueType, &DynamicTypeList,
 143                  TY_DYNAMIC, SF_LVALUE);
 144     initType(&DynamicRValueType, &DynamicTypeList, TY_DYNAMIC);
 145     initType(&NumericType, NULL, TY_UNRESOLVED);
 146     initType(&IntegralType, NULL, TY_UNRESOLVED);
 147     initType(&SIntegerType, NULL, TY_UNRESOLVED);
 148     initType(&UIntegerType, NULL, TY_UNRESOLVED);
 149     initType(&FloatType, NULL, TY_UNRESOLVED);
 150     initType(&PointerType, NULL, TY_UNRESOLVED);
 151     PointerType.ty_AlignMask = POINTERSTOR_ALIGN;
 152
 153     initType(&VoidType, NULL, TY_UNRESOLVED);
 154     initType(&BoolType, NULL, TY_UNRESOLVED);
 155     initType(&Int8Type, NULL, TY_UNRESOLVED);
 156     initType(&UInt8Type, NULL, TY_UNRESOLVED);
 157     initType(&Int16Type, NULL, TY_UNRESOLVED);
 158     initType(&UInt16Type, NULL, TY_UNRESOLVED);
 159     initType(&Int32Type, NULL, TY_UNRESOLVED);
 160     initType(&UInt32Type, NULL, TY_UNRESOLVED);
 161     initType(&Int64Type, NULL, TY_UNRESOLVED);
 162     initType(&UInt64Type, NULL, TY_UNRESOLVED);
 163
 164     initType(&IntPtrType, NULL, TY_UNRESOLVED);
 165     initType(&UIntPtrType, NULL, TY_UNRESOLVED);
 166     initType(&OffType, NULL, TY_UNRESOLVED);
 167     initType(&USizeType, NULL, TY_UNRESOLVED);
 168     initType(&SSizeType, NULL, TY_UNRESOLVED);
 169
 170     initType(&Float32Type, NULL, TY_UNRESOLVED);
 171     initType(&Float64Type, NULL, TY_UNRESOLVED);
 172     initType(&Float128Type, NULL, TY_UNRESOLVED);
 173
 174     initQualType(&CCharType, NULL, TY_UNRESOLVED, SF_CONST);
 175     initPtrType(&StrType, &CCharType, 0);
 176     initPtrType(&UCharPtrType, &UInt8Type, 0);
 177     initPtrType(&UCharPtrPtrType, &UCharPtrType, 0);
 178     initPtrType(&CUCharPtrPtrType, &StrType, 0);
 179     initPtrType(&VoidPtrType, &VoidType, 0);
 180     initRefType(&VoidRefType, &VoidType, 0);
 181     initCPtrType(&CVoidPtrType, &VoidType, SF_CONST);
 182     initPtrType(&LVoidPtrType, &VoidType, SF_LVALUE);
 183
 184     /*
 185      * Mark internal types (not all are bound to classes so it is easiest to
 186      * just do it here).  This will prevent the collapse code from trying to
 187      * collapse our base types.
 188      */
 189     for (i = 0; BaseTypeAry[i]; ++i)
 190         BaseTypeAry[i]->ty_Flags |= TF_ISINTERNAL;
 191 }
 192
 193 /*
 194  * Attach an internal class, creating a global summary type for it that
 195  * allows our interpreter and code generator to make various assumptions.
 196  */
 197 int
 198 InternalClassAttach(Parse *p __unused, int t, Declaration *d)
 199 {
 200     Type   *itype;
 201
 202     dassert_decl(d, d->d_Op == DOP_CLASS);
 203
 204     switch(d->d_Id) {
 205     case RUNEID_VOID:
 206         itype = &VoidType;
 207         break;
 208     case RUNEID_BOOL:
 209         /*
 210          * Special flag helper (resolver sets TF_ISBOOL in in the type)
 211          */
 212         itype = &BoolType;
 213         d->d_ClassDecl.ed_SemGroup->sg_Flags |= SGF_ISBOOL;
 214         break;
 215     case RUNEID_INT8:
 216         itype = &Int8Type;
 217         break;
 218     case RUNEID_UINT8:
 219         itype = &UInt8Type;
 220         break;
 221     case RUNEID_INT16:
 222         itype = &Int16Type;
 223         break;
 224     case RUNEID_UINT16:
 225         itype = &UInt16Type;
 226         break;
 227     case RUNEID_INT32:
 228         itype = &Int32Type;
 229         break;
 230     case RUNEID_UINT32:
 231         itype = &UInt32Type;
 232         break;
 233     case RUNEID_INT64:
 234         itype = &Int64Type;
 235         break;
 236     case RUNEID_UINT64:
 237         itype = &UInt64Type;
 238         break;
 239     case RUNEID_INT128:
 240         itype = &Int128Type;
 241         break;
 242     case RUNEID_UINT128:
 243         itype = &UInt128Type;
 244         break;
 245
 246     case RUNEID_FLOAT:
 247         /*
 248          * Special flag helper (resolver sets TF_ISFLOATING in in the
 249          * type)
 250          */
 251         itype = &FloatType;
 252         d->d_ClassDecl.ed_SemGroup->sg_Flags |= SGF_ISFLOATING;
 253         break;
 254     case RUNEID_FLOAT32:
 255         itype = &Float32Type;
 256         break;
 257     case RUNEID_FLOAT64:
 258         itype = &Float64Type;
 259         break;
 260     case RUNEID_FLOAT128:
 261         itype = &Float128Type;
 262         break;
 263
 264     case RUNEID_INTPTR:
 265         itype = &IntPtrType;
 266         break;
 267     case RUNEID_UINTPTR:
 268         itype = &UIntPtrType;
 269         break;
 270     case RUNEID_OFF:
 271         itype = &OffType;
 272         break;
 273     case RUNEID_USIZE:
 274         itype = &USizeType;
 275         break;
 276     case RUNEID_SSIZE:
 277         itype = &SSizeType;
 278         break;
 279     case RUNEID_POINTER:
 280         itype = &PointerType;
 281         break;
 282     case RUNEID_NUMERIC:
 283         itype = &NumericType;
 284         break;
 285     case RUNEID_INTEGRAL:
 286         itype = &IntegralType;
 287         break;
 288     case RUNEID_SINTEGER:
 289         /*
 290          * Special flag helper (resolver sets TF_ISINTEGER in in the
 291          * type)
 292          */
 293         itype = &SIntegerType;
 294         d->d_ClassDecl.ed_SemGroup->sg_Flags |= SGF_ISINTEGER;
 295         break;
 296     case RUNEID_UINTEGER:
 297         /*
 298          * Special flag helper (resolver sets TF_ISINTEGER and
 299          * TF_ISUNSIGNED in the type)
 300          */
 301         itype = &UIntegerType;
 302         d->d_ClassDecl.ed_SemGroup->sg_Flags |= SGF_ISUNSIGNED;
 303         d->d_ClassDecl.ed_SemGroup->sg_Flags |= SGF_ISINTEGER;
 304         break;
 305     case RUNEID_LEXREF:
 306         itype = &LexRefType;
 307         break;
 308     case RUNEID_SCOPE:
 309         itype = &ScopeType;
 310         break;
 311     case RUNEID_DECLARATION:
 312         itype = &DeclarationType;
 313         break;
 314     case RUNEID_SEMGROUP:
 315         itype = &SemGroupType;
 316         break;
 317     case RUNEID_POINTERINFO:
 318         itype = &PointerInfoType;
 319         break;
 320     case RUNEID_TYPE:
 321         itype = &TypeType;
 322         break;
 323     case RUNEID_FILLERTYPE:
 324         itype = &FILLERTypeType;
 325         break;
 326     case RUNEID_FILLERDECL:
 327         itype = &FILLERDeclType;
 328         break;
 329     default:
 330         {
 331             char buf[RUNE_IDTOSTR_LEN];
 332
 333             dpanic("Unknown internal class: %s", runeid_text(d->d_Id, buf));
 334         }
 335         itype = NULL;
 336         break;
 337     }
 338     initInternalClassType(itype, d);
 339
 340     /*
 341      * Fixup for const int8 pointers... we did not have a QList to put
 342      * CCharType on until now.  It will wind up on the SemGroup's
 343      * sg_ClassList.
 344      */
 345     if (itype == &UInt8Type) {
 346         TypeToQualType(itype, &CCharType,
 347                        itype->ty_SQFlags | SF_CONST, NULL);
 348     }
 349
 350     return (t);
 351 }
 352
 353 /*
 354  * This is mostly deprecated except for official type aliases such as
 355  * intptr_t.
 356  */
 357 int
 358 InternalTypeAttach(Parse *p, int t, Declaration *d)
 359 {
 360     Type   *itype;
 361
 362     dassert_decl(d, d->d_Op == DOP_TYPEDEF);
 363
 364     switch(d->d_Id) {
 365     case RUNEID_VOID:
 366         itype = &VoidType;
 367         break;
 368     case RUNEID_BOOL:
 369         itype = &BoolType;
 370         break;
 371     case RUNEID_INT8:
 372         itype = &Int8Type;
 373         break;
 374     case RUNEID_UINT8:
 375         itype = &UInt8Type;
 376         break;
 377     case RUNEID_INT16:
 378         itype = &Int16Type;
 379         break;
 380     case RUNEID_UINT16:
 381         itype = &UInt16Type;
 382         break;
 383     case RUNEID_INT32:
 384         itype = &Int32Type;
 385         break;
 386     case RUNEID_UINT32:
 387         itype = &UInt32Type;
 388         break;
 389     case RUNEID_INT64:
 390         itype = &Int64Type;
 391         break;
 392     case RUNEID_UINT64:
 393         itype = &UInt64Type;
 394         break;
 395
 396     case RUNEID_FLOAT32:
 397         itype = &Float32Type;
 398         break;
 399     case RUNEID_FLOAT64:
 400         itype = &Float64Type;
 401         break;
 402     case RUNEID_FLOAT128:
 403         itype = &Float128Type;
 404         break;
 405
 406     case RUNEID_INTPTR:
 407         itype = &IntPtrType;
 408         break;
 409     case RUNEID_UINTPTR:
 410         itype = &UIntPtrType;
 411         break;
 412     case RUNEID_OFF:
 413         itype = &OffType;
 414         break;
 415     case RUNEID_USIZE:
 416         itype = &USizeType;
 417         break;
 418     case RUNEID_SSIZE:
 419         itype = &SSizeType;
 420         break;
 421     case RUNEID_POINTER:
 422         itype = &PointerType;
 423         break;
 424     case RUNEID_NUMERIC:
 425         itype = &NumericType;
 426         break;
 427     case RUNEID_INTEGRAL:
 428         itype = &IntegralType;
 429         break;
 430     case RUNEID_SINTEGER:
 431         itype = &SIntegerType;
 432         break;
 433     case RUNEID_UINTEGER:
 434         itype = &UIntegerType;
 435         break;
 436     default:
 437         itype = InternalRegisteredTypeLookup(d->d_Id);
 438         if (itype == NULL)
 439             dpanic("Unknown internal type: %s", d->d_Id);
 440         break;
 441     }
 442
 443     if (itype) {
 444         if (itype->ty_Op != TY_UNRESOLVED) {
 445             t = LexError(&p->p_Token, TOK_ERR_DUPLICATE_ATTACH);
 446         } else {
 447             Type   *ntype = d->d_TypedefDecl.ed_Type;
 448
 449             TypeToQualType(ntype, itype, ntype->ty_SQFlags, NULL);
 450         }
 451     } else {
 452         t = LexError(&p->p_Token, TOK_ERR_UNRECOGNIZED_ATTACH);
 453     }
 454     return (t);
 455 }
 456
 457 Type *
 458 AllocType(typelist_t *list, int op)
 459 {
 460     Type   *type = zalloc(sizeof(Type));
 461
 462     initType(type, list, op);
 463     return (type);
 464 }
 465
 466 /*
 467  * May be used to generate a varargs compound type, in which case the
 468  * semgroup may already be resolved.
 469  *
 470  * We do no matching/caching at this time and callers assume that (for making
 471  * adjustments) to the underlying sg at parse-time via TypeToProcType()
 472  */
 473 Type *
 474 AllocCompoundType(SemGroup *sg)
 475 {
 476     Type   *type;
 477
 478     type = AllocType(&CompoundTypeList, TY_COMPOUND);
 479     type->ty_CompType.et_SemGroup = sg;
 480     dassert((sg->sg_Flags & SGF_RESOLVED) == 0);
 481     return (type);
 482 }
 483
 484 /*
 485  * XXX match the compound type(s)
 486  */
 487 Type *
 488 AllocArgsType(SemGroup *sg)
 489 {
 490     Type   *type;
 491
 492     type = AllocType(&ArgsTypeList, TY_ARGS);
 493     type->ty_ArgsType.et_SemGroup = sg;
 494     return (type);
 495 }
 496
 497 Type *
 498 AllocStorageType(urunesize_t bytes)
 499 {
 500     Type   *type;
 501
 502     RUNE_FOREACH(type, &StorageTypeList, ty_Node) {
 503         if (type->ty_Op == TY_STORAGE &&
 504             type->ty_StorType.et_Bytes == bytes
 505             ) {
 506             return (type);
 507         }
 508     }
 509     type = AllocType(&StorageTypeList, TY_STORAGE);
 510     type->ty_StorType.et_Bytes = bytes;
 511     return (type);
 512 }
 513
 514 Type *
 515 AllocUnresolvedType(SemGroup *isg, SemGroup *sg, runeid_t *ary, int eatAry)
 516 {
 517     Type   *type = NULL;
 518
 519     dassert_semgrp(sg, ary != NULL);
 520
 521     RUNE_FOREACH(type, &sg->sg_ClassList, ty_Node) {
 522         int     i;
 523
 524         if (type->ty_Op != TY_UNRESOLVED)
 525             continue;
 526         if (type->ty_UnresType.et_ImportSemGroup != isg)
 527             continue;
 528
 529         for (i = 0; ary[i]; ++i) {
 530             if (ary[i] != type->ty_UnresType.et_DottedId[i])
 531                 break;
 532         }
 533         if (ary[i] == 0 && type->ty_UnresType.et_DottedId[i] == 0) {
 534             if (eatAry)
 535                 FreeDotIdAry(ary);
 536             return (type);
 537         }
 538     }
 539     type = AllocType((sg ? &sg->sg_ClassList : NULL), TY_UNRESOLVED);
 540     type->ty_UnresType.et_DottedId = ary;
 541     type->ty_UnresType.et_SemGroup = sg;        /* may be NULL */
 542     type->ty_UnresType.et_ImportSemGroup = isg; /* may be NULL */
 543     return (type);
 544 }
 545
 546 /*
 547  * AllocClassType() - allocate a type representing a the semgroup which in
 548  * turn represents (typically) a class.
 549  */
 550 Type *
 551 AllocClassType(typelist_t *list, Type *super, SemGroup *sg, int visibility)
 552 {
 553     Type   *type;
 554
 555     dassert(sg != NULL);
 556     list = &sg->sg_ClassList;
 557
 558     RUNE_FOREACH(type, list, ty_Node) {
 559         if (type->ty_Op == TY_CLASS &&
 560             type->ty_ClassType.et_SemGroup == sg &&
 561             type->ty_ClassType.et_Super == super &&
 562             type->ty_Visibility == visibility
 563             ) {
 564             return (type);
 565         }
 566     }
 567     if (sg)
 568         dassert(&sg->sg_ClassList == list);
 569     type = AllocType(list, TY_CLASS);
 570     type->ty_ClassType.et_SemGroup = sg;
 571     type->ty_ClassType.et_Super = super;
 572     type->ty_Visibility = visibility;
 573     return (type);
 574 }
 575
 576 static
 577 void
 578 initInternalClassType(Type *type, Declaration *d)
 579 {
 580     SemGroup *sg = d->d_ClassDecl.ed_SemGroup;
 581
 582     initType(type, &sg->sg_ClassList, TY_CLASS);
 583     RUNE_REMOVE(&sg->sg_ClassList, type, ty_Node);
 584     RUNE_INSERT_HEAD(&sg->sg_ClassList, type, ty_Node);
 585     type->ty_ClassType.et_SemGroup = d->d_ClassDecl.ed_SemGroup;
 586     type->ty_ClassType.et_Super = d->d_ClassDecl.ed_Super;
 587     type->ty_Visibility = d->d_ScopeFlags & SCOPE_ALL_VISIBLE;
 588     type->ty_Flags |= TF_ISINTERNAL;
 589 }
 590
 591 Type *
 592 AllocImportType(typelist_t *list, SemGroup *sg, int visibility)
 593 {
 594     Type   *type = AllocType(list, TY_IMPORT);
 595
 596     type->ty_ImportType.et_SemGroup = sg;
 597     type->ty_Visibility = visibility;
 598     return (type);
 599 }
 600
 601 /*
 602  * adjtype must be moved to type's QList because type is being modified such
 603  * that that is where it is expected to be.
 604  */
 605 Type *
 606 TypeAdjustQList(Type *type, Type *adjtype)
 607 {
 608     if (adjtype) {
 609         if (adjtype->ty_SQList)
 610             RUNE_REMOVE(adjtype->ty_SQList, adjtype, ty_Node);
 611         adjtype->ty_SQList = &type->ty_QList;
 612         RUNE_INSERT_TAIL(adjtype->ty_SQList, adjtype, ty_Node);
 613     }
 614     return type;
 615 }
 616
 617 /*
 618  * Compound types inherit locking modes if not specifically overridden.
 619  */
 620 Type *
 621 TypeFixupInheritedFlags(Type *type, int rqflags)
 622 {
 623     SemGroup *sg;
 624     Declaration *d;
 625
 626     if (type->ty_Op != TY_COMPOUND)
 627         return type;
 628
 629     /*
 630      * Assume no matching collapse yet
 631      */
 632     sg = type->ty_CompType.et_SemGroup;
 633     RUNE_FOREACH(d, &sg->sg_DeclList, d_Node) {
 634         if (d->d_Op != DOP_GROUP_STORAGE)
 635             continue;
 636         if ((d->d_ScopeFlags & SCOPE_LOCKING_MASK) == 0) {
 637             if (rqflags & SF_UNTRACKED)
 638                 d->d_ScopeFlags |= SCOPE_UNTRACKED;
 639             if (rqflags & SF_UNLOCKED)
 640                 d->d_ScopeFlags |= SCOPE_UNLOCKED;
 641             if (rqflags & SF_SOFT)
 642                 d->d_ScopeFlags |= SCOPE_SOFT;
 643             if (rqflags & SF_HARD)
 644                 d->d_ScopeFlags |= SCOPE_HARD;
 645         }
 646     }
 647     return type;
 648 }
 649
 650 Type *
 651 TypeToQualType(Type *otype, Type *ntype, int sqFlags, Exp *exp)
 652 {
 653     SemGroup *sg;
 654
 655     /*
 656      * Combine with existing qualifiers, Shortcut if no changes made.
 657      */
 658     if (ntype == NULL &&
 659         sqFlags == otype->ty_SQFlags &&
 660         (exp == NULL || exp == otype->ty_AssExp)
 661         ) {
 662         return (otype);
 663     }
 664
 665     /*
 666      * See if we already have a matching qualified type (only if storage for
 667      * the new type is not being provided).  Note: the provided storage has
 668      * already been initType()d
 669      */
 670     if (ntype == NULL) {
 671         RUNE_FOREACH(ntype, otype->ty_SQList, ty_Node) {
 672             if (ntype->ty_Op == otype->ty_Op &&
 673                 ntype->ty_SQFlags == sqFlags &&
 674                 (exp == NULL || ntype->ty_AssExp == exp)
 675                 ) {
 676                 if (SameType(ntype, otype, sqFlags))
 677                     return (ntype);
 678             }
 679         }
 680     }
 681
 682     /*
 683      * Build a new qualified type and set its qualifiers, then duplicate
 684      * appropriate sections of the old type.
 685      *
 686      * Default to the same SQList as otype.
 687      */
 688     if (ntype == NULL) {
 689         ntype = AllocType(otype->ty_SQList, otype->ty_Op);
 690     } else {
 691         if (ntype->ty_SQList)
 692             RUNE_REMOVE(ntype->ty_SQList, ntype, ty_Node);
 693         ntype->ty_SQList = otype->ty_SQList;
 694         RUNE_INSERT_TAIL(ntype->ty_SQList, ntype, ty_Node);
 695     }
 696
 697     /*
 698      * Set the op and the expression.  Unlike SQFlags, if exp is passed as
 699      * NULL we inherit the old type's default.
 700      *
 701      * The DupExp() call here is special, see DupExp()'s handling of ex_Decl.
 702      *
 703      * Normally DupExp() is called during resolution prior to ex_Decl being
 704      * set.  This is the one case where it may be called with ex_Decl already
 705      * set.
 706      *
 707      * WARNING! We do not try to resolve the type here.  Various resolve
 708      * related flags in ty_Flags will be resolved later.  This includes
 709      * TF_ISUNSIGNED and other TF_* flags.
 710      */
 711     ntype->ty_Op = otype->ty_Op;
 712     if (exp)
 713         ntype->ty_AssExp = exp;
 714     else if (otype->ty_AssExp)
 715         ntype->ty_AssExp = SetDupExp(NULL, otype->ty_AssExp);
 716     ntype->ty_SQFlags = sqFlags;
 717     ntype->ty_Visibility = otype->ty_Visibility;
 718
 719     switch (otype->ty_Op) {
 720     case TY_CLASS:
 721         /*
 722          * When updating the class, alternative forms are collapsed into it's
 723          * SemGroup->sg_ClassList and not into some potentially long
 724          * recursive chain based on ty_QList.
 725          */
 726         sg = otype->ty_ClassType.et_SemGroup;
 727
 728         dassert(ntype->ty_SQList == &sg->sg_ClassList);
 729         if (ntype->ty_ClassType.et_SemGroup != sg) {
 730             ntype->ty_ClassType.et_SemGroup = sg;
 731         }
 732         ntype->ty_ClassType.et_Super = otype->ty_ClassType.et_Super;
 733         break;
 734     case TY_IMPORT:
 735         ntype->ty_Visibility = otype->ty_Visibility;
 736         ntype->ty_ImportType.et_SemGroup = otype->ty_ImportType.et_SemGroup;
 737         break;
 738     case TY_CPTRTO:
 739         ntype->ty_CPtrType.et_Type = otype->ty_CPtrType.et_Type;
 740         break;
 741     case TY_PTRTO:
 742         ntype->ty_PtrType.et_Type = otype->ty_PtrType.et_Type;
 743         break;
 744     case TY_REFTO:
 745         ntype->ty_RefType.et_Type = otype->ty_RefType.et_Type;
 746         break;
 747     case TY_ARYOF:
 748         /*
 749          * note: multiple type structures may share the same array size
 750          * expression in simple qualified-type cases.  YYY XXX bad bad.
 751          */
 752         ntype->ty_AryType.et_Type = otype->ty_AryType.et_Type;
 753         ntype->ty_AryType.et_ArySize = otype->ty_AryType.et_ArySize;
 754         ntype->ty_AryType.et_SemGroup = otype->ty_AryType.et_SemGroup;
 755         ntype->ty_AryType.et_Count = otype->ty_AryType.et_Count;
 756         break;
 757     case TY_COMPOUND:
 758         ntype->ty_CompType.et_SemGroup = otype->ty_CompType.et_SemGroup;
 759         break;
 760     case TY_VAR:
 761         ntype->ty_VarType.et_Type = otype->ty_VarType.et_Type;
 762         ntype->ty_VarType.et_SemGroup = otype->ty_VarType.et_SemGroup;
 763         break;
 764     case TY_ARGS:
 765         ntype->ty_ArgsType.et_SemGroup = otype->ty_ArgsType.et_SemGroup;
 766         break;
 767     case TY_PROC:
 768         ntype->ty_ProcType.et_ArgsType = otype->ty_ProcType.et_ArgsType;
 769         ntype->ty_ProcType.et_RetType = otype->ty_ProcType.et_RetType;
 770         ntype->ty_ProcType.et_ArgCount = otype->ty_ProcType.et_ArgCount;
 771         dassert(ntype->ty_SQList ==
 772                 &otype->ty_ProcType.et_RetType->ty_QList);
 773         break;
 774     case TY_STORAGE:
 775         ntype->ty_StorType.et_Bytes = otype->ty_StorType.et_Bytes;
 776         break;
 777     case TY_DYNAMIC:
 778         /*
 779          * It is not legal to qualify a dynamic type other then to add or
 780          * remove SF_LVALUE.
 781          */
 782         dpanic("Dynamic type cannot be qualified");
 783         break;
 784     case TY_UNRESOLVED:
 785         ntype->ty_UnresType.et_DottedId =
 786             otype->ty_UnresType.et_DottedId;
 787         ntype->ty_UnresType.et_SemGroup =
 788             otype->ty_UnresType.et_SemGroup;
 789         ntype->ty_UnresType.et_ImportSemGroup =
 790             otype->ty_UnresType.et_ImportSemGroup;
 791         break;
 792     default:
 793         dassert_type(otype, 0);
 794     }
 795     return (ntype);
 796 }
 797
 798 /*
 799  * Convert a return-type + argument-type into a procedure type.  If adjret is
 800  * non-zero the return-type is converted to locked storage (which is
 801  * generally what we want).
 802  *
 803  * Match the procedure type(s) (after adjustment?)
 804  */
 805 Type *
 806 TypeToProcType(Type *rtype, Type *atype, int adjret)
 807 {
 808     urunesize_t count = 0;
 809     Declaration *d;
 810     SemGroup *sg;
 811     Type   *type;
 812
 813     dassert_type(atype, atype->ty_Op == TY_ARGS);
 814
 815     if (adjret)
 816         rtype = TypeFixupInheritedFlags(rtype, rtype->ty_SQFlags);
 817
 818     sg = atype->ty_CompType.et_SemGroup;
 819
 820     RUNE_FOREACH(d, &sg->sg_DeclList, d_Node) {
 821         ++count;
 822     }
 823     RUNE_FOREACH(type, &rtype->ty_QList, ty_Node) {
 824         if (type->ty_Op == TY_PROC) {
 825             if (type->ty_ProcType.et_ArgsType == atype &&
 826                 type->ty_ProcType.et_RetType == rtype &&
 827                 type->ty_ProcType.et_ArgCount == count
 828                 ) {
 829                 return (type);
 830             }
 831         }
 832     }
 833     type = AllocType(&rtype->ty_QList, TY_PROC);
 834     type->ty_ProcType.et_ArgsType = AllocArgsType(sg);
 835     type->ty_ProcType.et_RetType = rtype;
 836     type->ty_ProcType.et_ArgCount = count;
 837     return (type);
 838 }
 839
 840 /*
 841  * Convert type to pointer-to-type
 842  */
 843 Type *
 844 TypeToPtrType(Type *otype)
 845 {
 846     Type   *type;
 847
 848     RUNE_FOREACH(type, &otype->ty_QList, ty_Node) {
 849         if (type->ty_Op == TY_PTRTO)
 850             return (type);
 851     }
 852     type = AllocType(&otype->ty_QList, TY_PTRTO);
 853     type->ty_PtrType.et_Type = otype;
 854     return (type);
 855 }
 856
 857 /*
 858  * Convert type to pointer-to-type
 859  */
 860 Type *
 861 TypeToCPtrType(Type *otype)
 862 {
 863     Type   *type;
 864
 865     RUNE_FOREACH(type, &otype->ty_QList, ty_Node) {
 866         if (type->ty_Op == TY_CPTRTO)
 867             return (type);
 868     }
 869     type = AllocType(&otype->ty_QList, TY_CPTRTO);
 870     type->ty_CPtrType.et_Type = otype;
 871     return (type);
 872 }
 873
 874 /*
 875  * Convert type to ref-to-type
 876  *
 877  * A reference type is similar to a pointer type except that the resolver is
 878  * not able to entirely know what it is pointing to. The reference type is a
 879  * superclass, but the actual type is stored in the run-time structure.
 880  */
 881 Type *
 882 TypeToRefType(Type *otype)
 883 {
 884     Type   *type;
 885
 886     RUNE_FOREACH(type, &otype->ty_QList, ty_Node) {
 887         if (type->ty_Op == TY_REFTO)
 888             return (type);
 889     }
 890     type = AllocType(&otype->ty_QList, TY_REFTO);
 891     type->ty_RefType.et_Type = otype;
 892     return (type);
 893 }
 894
 895 Type *
 896 TypeToAryType(Type *otype, Exp *exp, SemGroup *sg)
 897 {
 898     Type   *type;
 899
 900     /*
 901      * XXX handle constant expression optimization for QList XXX handle
 902      * qualifiers
 903      */
 904     type = AllocType(&otype->ty_QList, TY_ARYOF);
 905     type->ty_AryType.et_ArySize = exp;
 906     type->ty_AryType.et_Type = DelTypeQual(otype, SF_MASK_ARY_INHERIT);
 907     type->ty_AryType.et_SemGroup = sg;
 908     type->ty_SQFlags |= otype->ty_SQFlags & SF_MASK_ARY_INHERIT;
 909     return (type);
 910 }
 911
 912 #if 0
 913
 914 Type *
 915 TypeToRunTimeAryType(Type *otype, int count)
 916 {
 917     Type   *type;
 918     Type   *t2 = DelTypeQual(otype, SF_MASK_ARY_INHERIT);
 919
 920     RUNE_FOREACH(type, &otype->ty_QList, ty_Node) {
 921         if (type->ty_Op == TY_ARYOF &&
 922             type->ty_AryType.et_Type == t2 &&
 923             type->ty_AryType.et_Count == count &&
 924             type->ty_SQFlags ==
 925             (otype->ty_SQFlags & SF_MASK_ARY_INHERIT)
 926             ) {
 927             return (type);
 928         }
 929     }
 930     type = AllocType(&otype->ty_QList, TY_ARYOF);
 931     type->ty_AryType.et_Count = count;
 932     type->ty_AryType.et_Type = t2;
 933     type->ty_SQFlags |= otype->ty_SQFlags & SF_MASK_ARY_INHERIT;
 934     return (type);
 935 }
 936
 937 #endif
 938
 939 Type *
 940 TypeToVarType(Type *otype, SemGroup *sg)
 941 {
 942     Type   *type;
 943
 944     /* dassert(sg->sg_Flags & SGF_RESOLVED); */
 945     /* dassert(otype->ty_Flags & TF_RESOLVED); */
 946
 947     RUNE_FOREACH(type, &otype->ty_QList, ty_Node) {
 948         if (type->ty_Op == TY_VAR &&
 949             type->ty_VarType.et_Type == otype &&
 950             type->ty_VarType.et_SemGroup == sg
 951             ) {
 952             puts("SG2");        /* YYY */
 953             return (type);
 954         }
 955     }
 956     type = AllocType(&otype->ty_QList, TY_VAR);
 957     type->ty_VarType.et_Type = otype;
 958     type->ty_VarType.et_SemGroup = sg;
 959 #if 0
 960     /* XXX doesn't work for var-args */
 961     if (sg->sg_Flags & SGF_RESOLVED) {
 962         type->ty_Flags |= TF_RESOLVED;
 963         type->ty_Bytes = sg->sg_Bytes;
 964         type->ty_AlignMask = sg->sg_AlignMask;
 965     }
 966 #endif
 967     return (type);
 968 }
 969
 970 /*
 971  * ChangeType() - given pointer, C pointer, or array of something, return
 972  * 'op' of something instead.
 973  */
 974 Type *
 975 ChangeType(Type *type, int op)
 976 {
 977     switch (type->ty_Op) {
 978     case TY_PTRTO:
 979         switch (op) {
 980         case TY_CPTRTO:
 981             type = TypeToCPtrType(type->ty_PtrType.et_Type);
 982             break;
 983         case TY_ARYOF:
 984             type = TypeToAryType(type->ty_PtrType.et_Type,
 985                                  NULL, NULL);
 986             break;
 987         default:
 988             dpanic("Illegal type convesion (A)");
 989         }
 990         break;
 991     case TY_CPTRTO:
 992         switch (op) {
 993         case TY_PTRTO:
 994             type = TypeToPtrType(type->ty_CPtrType.et_Type);
 995             break;
 996         case TY_ARYOF:
 997             type = TypeToAryType(type->ty_CPtrType.et_Type,
 998                                  NULL, NULL);
 999             break;
1000         default:
1001             dpanic("Illegal type convesion (B)");
1002         }
1003         break;
1004     case TY_ARYOF:
1005         switch (op) {
1006         case TY_PTRTO:
1007             type = TypeToPtrType(type->ty_AryType.et_Type);
1008             break;
1009         case TY_CPTRTO:
1010             type = TypeToCPtrType(type->ty_AryType.et_Type);
1011             break;
1012         default:
1013             dpanic("Illegal type convesion (C)");
1014         }
1015         break;
1016     default:
1017         dpanic("Illegal type convesion (D)");
1018     }
1019     return (type);
1020 }
1021
1022 /*
1023  * BaseType() - return base type
1024  *
1025  * Traverse the type to locate the base type.  Store the base type in *ptype
1026  * and return the SemGroup, or return NULL if the base type does not have a
1027  * SemGroup.
1028  */
1029 SemGroup *
1030 BaseType(Type **ptype)
1031 {
1032     Type   *type = *ptype;
1033
1034     for (;;) {
1035         switch (type->ty_Op) {
1036         case TY_CPTRTO:
1037             type = type->ty_CPtrType.et_Type;
1038             continue;
1039         case TY_PTRTO:
1040             type = type->ty_PtrType.et_Type;
1041             continue;
1042         case TY_REFTO:
1043             type = type->ty_RefType.et_Type;
1044             continue;
1045         case TY_ARYOF:
1046             type = type->ty_AryType.et_Type;
1047             continue;
1048         }
1049         break;
1050     }
1051
1052     *ptype = type;
1053
1054     switch (type->ty_Op) {
1055     case TY_CLASS:
1056         return (type->ty_ClassType.et_SemGroup);
1057     case TY_COMPOUND:
1058         return (type->ty_CompType.et_SemGroup);
1059     case TY_ARGS:
1060         return (type->ty_ArgsType.et_SemGroup);
1061     case TY_PROC:
1062     case TY_VAR:
1063     case TY_DYNAMIC:
1064     case TY_STORAGE:
1065         return (NULL);
1066     case TY_UNRESOLVED:
1067     default:
1068         dassert_type(type, 0);
1069         return (NULL);          /* avoid compiler complaints */
1070     }
1071 }
1072
1073 /*
1074  * DupType()     - create a duplicate of a type, possibly in a new SemGroup.
1075  *
1076  * This code is used when duplicating procedures and other elements when
1077  * merging a superclass into a subclass.
1078  *
1079  * If sg is NULL, stype is simply returned.  The case is used when we try to
1080  * duplciate an expression with DupExp()... in that case we want to dup the
1081  * expression tree but use the same types.
1082  */
1083 Type *
1084 DupType(SemGroup *sg, Type *stype)
1085 {
1086     Type   *type = NULL;
1087
1088     if (sg == NULL)
1089         return (stype);
1090
1091     /*
1092      * XXX type may be resolved if it is part of a varargs dup
1093      */
1094 #if 0
1095     dassert_type(stype,
1096                  (stype->ty_Flags & (TF_RESOLVED | TF_RESOLVING)) == 0);
1097 #endif
1098
1099     switch (stype->ty_Op) {
1100     case TY_CLASS:
1101         /*
1102          * This only occurs because the resolver has resolved an unresolved
1103          * type on the original SemGroup.  We duplicate that on the new
1104          * SemGroup.
1105          */
1106         type = AllocClassType(&sg->sg_ClassList,
1107                               stype->ty_ClassType.et_Super,
1108                               stype->ty_ClassType.et_SemGroup,
1109                               stype->ty_Visibility);
1110         break;
1111     case TY_IMPORT:
1112     case TY_DYNAMIC:
1113         type = stype;
1114         break;
1115     case TY_CPTRTO:
1116         type = TypeToCPtrType(DupType(sg, stype->ty_CPtrType.et_Type));
1117         break;
1118     case TY_PTRTO:
1119         type = TypeToPtrType(DupType(sg, stype->ty_PtrType.et_Type));
1120         break;
1121     case TY_REFTO:
1122         type = TypeToRefType(DupType(sg, stype->ty_RefType.et_Type));
1123         break;
1124     case TY_ARYOF:
1125         type = TypeToAryType(DupType(sg, stype->ty_AryType.et_Type),
1126                              SetDupExp(sg, stype->ty_AryType.et_ArySize),
1127                              stype->ty_AryType.et_SemGroup);
1128         type->ty_AryType.et_Count = stype->ty_AryType.et_Count;
1129         break;
1130     case TY_VAR:
1131         type = TypeToVarType(DupType(sg, stype->ty_VarType.et_Type),
1132                              DupSemGroup(sg, NULL,
1133                                          stype->ty_VarType.et_SemGroup, 1));
1134         break;
1135     case TY_COMPOUND:
1136         type = AllocCompoundType(
1137                                  DupSemGroup(sg, NULL,
1138                                         stype->ty_CompType.et_SemGroup, 1));
1139         break;
1140     case TY_ARGS:
1141         /*
1142          * At the moment we always formally duplicate the arguments so we can
1143          * modify them for methods below.
1144          */
1145         type = AllocArgsType(
1146                              DupSemGroup(sg, NULL,
1147                                          stype->ty_CompType.et_SemGroup, 1));
1148         break;
1149     case TY_PROC:
1150         type = DupType(sg, stype->ty_ProcType.et_RetType);
1151         type = TypeToProcType(type,
1152                               DupType(sg, stype->ty_ProcType.et_ArgsType),
1153                               1);
1154
1155         /*
1156          * If this is a method procedure, we have to change the first
1157          * argument to point at our new subclass.  It was previously pointing
1158          * at our superclass.   XXX the programmer can override the argument.
1159          * If it isn't a reference we have to assert.
1160          */
1161         if (sg->sg_Stmt->st_Op != ST_Class) {
1162             /*
1163              * XXX probably an inlined procedure, the type is already
1164              * correct.  Need an assertrion here.
1165              */
1166         } else if (stype->ty_SQFlags & SF_METHOD) {
1167             SemGroup *asg = type->ty_ProcType.et_ArgsType->ty_ArgsType.et_SemGroup;
1168             Declaration *d = RUNE_FIRST(&asg->sg_DeclList);
1169             Type   *thisType = d->d_StorDecl.ed_Type;
1170
1171             dassert_decl(d, d->d_Id == RUNEID_THIS &&
1172                             d->d_Op == DOP_ARGS_STORAGE);
1173             dassert_decl(d, sg->sg_Stmt->st_Op == ST_Class);
1174             if (thisType->ty_Op == TY_CLASS) {
1175                 /* XXX sg_ClassList? right sg? */
1176                 /* XXX correct visibility? */
1177                 if (d->d_Search == NULL) {
1178                     d->d_Search = d->d_StorDecl.ed_Type->
1179                         ty_ClassType.et_SemGroup;
1180                 }
1181                 d->d_StorDecl.ed_Type =
1182                     AllocClassType(&sg->sg_ClassList,
1183                                    sg->sg_Stmt->st_ClassStmt.es_Super,
1184                                    sg->sg_Stmt->st_MyGroup,
1185                                    SCOPE_ALL_VISIBLE);
1186             } else {
1187                 dassert_decl(d, thisType->ty_Op == TY_REFTO);
1188             }
1189         } else if (stype->ty_SQFlags & SF_GMETHOD) {
1190             SemGroup *asg;
1191             Declaration *d;
1192
1193             asg = type->ty_ProcType.et_ArgsType->
1194                 ty_ArgsType.et_SemGroup;
1195             d = RUNE_FIRST(&asg->sg_DeclList);
1196
1197             dassert_decl(d, d->d_Id == RUNEID_THIS && d->d_Op == DOP_TYPEDEF);
1198             dassert_decl(d, sg->sg_Stmt->st_Op == ST_Class);
1199             dassert_decl(d, d->d_TypedefDecl.ed_Type->ty_Op == TY_CLASS);
1200             /* XXX sg_ClassList? right sg? */
1201             /* XXX correct visibility? */
1202             if (d->d_Search == NULL) {
1203                 d->d_Search = d->d_TypedefDecl.ed_Type->
1204                                 ty_ClassType.et_SemGroup;
1205             }
1206             d->d_TypedefDecl.ed_Type =
1207                 AllocClassType(&sg->sg_ClassList,
1208                                sg->sg_Stmt->st_ClassStmt.es_Super,
1209                                sg->sg_Stmt->st_MyGroup,
1210                                SCOPE_ALL_VISIBLE);
1211         }
1212         break;
1213     case TY_STORAGE:
1214         type = stype;
1215         break;
1216     case TY_UNRESOLVED:
1217         /*
1218          * e.g. so elements in a superclass will see refined elements in the
1219          * subclass.  Note that the original import semgroup is left intact
1220          * so the semantic search mechanism uses it when the base sg
1221          * (typically a subclass) fails.
1222          */
1223         type = AllocUnresolvedType(
1224                                    stype->ty_UnresType.et_ImportSemGroup,
1225                                    sg,
1226                                    stype->ty_UnresType.et_DottedId,
1227                                    0);
1228         break;
1229     default:
1230         dassert_type(stype, 0);
1231     }
1232
1233     if (type != stype) {
1234         type->ty_Flags = stype->ty_Flags &
1235             ~(TF_ISINTERNAL | TF_RESOLVING | TF_RESOLVED |
1236               TF_ALIGNRESOLVED | TF_TMPRESOLVED);
1237         type->ty_Bytes = stype->ty_Bytes;
1238         type->ty_AlignMask = stype->ty_AlignMask;
1239         type->ty_Visibility = stype->ty_Visibility;
1240         type->ty_DynamicVector = stype->ty_DynamicVector;
1241     }
1242     if (stype->ty_AssExp || stype->ty_SQFlags != type->ty_SQFlags) {
1243         type = TypeToQualType(type, NULL,
1244                               stype->ty_SQFlags,
1245                               SetDupExp(sg, stype->ty_AssExp));
1246     }
1247
1248     return (type);
1249 }
1250
1251 typereglist_t TypeRegList = RUNE_HEAD_INITIALIZER(TypeRegList);
1252
1253 void
1254 InternalRegisterType(const char *str, const char *linkname, Type *type)
1255 {
1256     TypeRegNode *tr;
1257
1258     tr = zalloc(sizeof(TypeRegNode));
1259     tr->tr_Id = runeid_hash(str, strlen(str));
1260     tr->tr_Type = type;
1261     tr->tr_LinkName = linkname;
1262     RUNE_INSERT_TAIL(&TypeRegList, tr, tr_Node);
1263 }
1264
1265 Type *
1266 InternalRegisteredTypeLookup(runeid_t id)
1267 {
1268     TypeRegNode *tr;
1269
1270     RUNE_FOREACH(tr, &TypeRegList, tr_Node) {
1271         if (tr->tr_Id == id)
1272             return (tr->tr_Type);
1273     }
1274     return (NULL);
1275 }