librune/typeq.c

   1 /*
   2  * TYPEQ.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  * WARNING: This needs to be almost standalone because it is also compiled
   8  * into libruntime.
   9  */
  10
  11 #include "defs.h"
  12
  13 /*
  14  * MatchType() -        Match two types
  15  *
  16  * Match two types as if we wanted to cast type to super or use type as
  17  * super.
  18  *
  19  * SG_COMPAT_FULL               Type is a subclass, methods and storage are
  20  *                              compatible (storage may be extended).
  21  *
  22  * SG_COMPAT_PART               Type is a subclass, methods are compatible
  23  *                              but storage is not.
  24  *
  25  * SG_COMPAT_SUBCLASS           Type is a subclass, but the methods are
  26  *                              not directly compatible (the methods that
  27  *                              propogate down must be regenerated).
  28  *
  29  * SG_COMPAT_FAIL               Type is not even a subclass
  30  *
  31  * XXX we are skipping qualifiers
  32  */
  33 int
  34 MatchType(Type *super, Type *type)
  35 {
  36     int     r = SG_COMPAT_FULL;
  37     int     loop = 0;
  38
  39     while (super && type) {
  40         SemGroup *sg1 = NULL;
  41         SemGroup *sg2 = NULL;
  42
  43         ++loop;
  44
  45         if (type->ty_Op != super->ty_Op) {
  46             r = SG_COMPAT_FAIL;
  47             break;
  48         }
  49
  50         /*
  51          * Relaxed storage qualifiers.  We are effectively casting to
  52          * 'super'.  We can remove SF_CONST from super but not from type.
  53          *
  54          * NOTE: Actual casts may do more stringent tests.
  55          */
  56         if (super->ty_SQFlags != type->ty_SQFlags) {
  57             if (loop > 1 &&
  58                 (type->ty_SQFlags & ~SF_IGNORE_MASK) !=
  59                 (super->ty_SQFlags & ~SF_RELAXING_MASK)) {
  60                 r = SG_COMPAT_FAIL;
  61                 break;
  62             }
  63         }
  64
  65         switch (super->ty_Op) {
  66         case TY_CLASS:
  67             /*
  68              * type can be a subclass of super
  69              */
  70             if (type->ty_ClassType.et_SemGroup ==
  71                 super->ty_ClassType.et_SemGroup) {
  72                 return (r);
  73             }
  74             r = type->ty_ClassType.et_SemGroup->sg_Compat;
  75 #if 0
  76             if (r < SG_COMPAT_PART)
  77                 r = SG_COMPAT_PART;
  78 #endif
  79             while ((type = type->ty_ClassType.et_Super) != NULL) {
  80                 if (type->ty_ClassType.et_SemGroup ==
  81                     super->ty_ClassType.et_SemGroup) {
  82                     break;
  83                 }
  84                 if (r < type->ty_ClassType.et_SemGroup->sg_Compat)
  85                     r = type->ty_ClassType.et_SemGroup->sg_Compat;
  86             }
  87             if (type == NULL)   /* not even a subclass */
  88                 r = SG_COMPAT_FAIL;
  89             break;
  90         case TY_IMPORT:
  91             /*
  92              * type can be a subclass of super
  93              */
  94             if (type != super)
  95                 r = SG_COMPAT_FAIL;
  96             break;
  97         case TY_PTRTO:
  98             type = type->ty_RawPtrType.et_Type;
  99             super = super->ty_RawPtrType.et_Type;
 100             continue;
 101         case TY_REFTO:
 102             type = type->ty_RefType.et_Type;
 103             super = super->ty_RefType.et_Type;
 104             continue;
 105         case TY_ARYOF:
 106             type = type->ty_AryType.et_Type;
 107             super = super->ty_AryType.et_Type;
 108             /* XXX */
 109             continue;
 110         case TY_COMPOUND:
 111             sg1 = super->ty_CompType.et_SemGroup;
 112             sg2 = type->ty_CompType.et_SemGroup;
 113             break;
 114         case TY_ARGS:
 115             sg1 = super->ty_ArgsType.et_SemGroup;
 116             sg2 = type->ty_ArgsType.et_SemGroup;
 117             break;
 118         case TY_VAR:
 119             r = MatchType(super->ty_VarType.et_Type,
 120                           type->ty_VarType.et_Type);
 121             break;
 122         case TY_PROC:
 123             {
 124                 int     v;
 125
 126                 r = MatchType(super->ty_ProcType.et_ArgsType,
 127                               type->ty_ProcType.et_ArgsType);
 128                 v = MatchType(super->ty_ProcType.et_RetType,
 129                               type->ty_ProcType.et_RetType);
 130                 if (r < v)
 131                     r = v;
 132             }
 133             break;
 134         case TY_DYNAMIC:
 135             break;
 136         case TY_STORAGE:
 137             if (type->ty_StorType.et_Bytes !=
 138                 super->ty_StorType.et_Bytes) {
 139                 r = SG_COMPAT_SUBCLASS;
 140             }
 141             break;
 142         case TY_UNRESOLVED:
 143         default:
 144             dassert_type(super, 0);     /* can't happen */
 145             break;
 146         }
 147         if (sg1) {
 148             Declaration *sd = RUNE_FIRST(&sg1->sg_DeclList);
 149             Declaration *rd = RUNE_FIRST(&sg2->sg_DeclList);
 150             while (sd && rd) {
 151                 int     v = MatchDeclTypes(sd, rd);
 152                 if (r < v)
 153                     r = v;
 154                 if (r == SG_COMPAT_FAIL)
 155                     break;
 156                 sd = RUNE_NEXT(sd, d_Node);
 157                 rd = RUNE_NEXT(rd, d_Node);
 158             }
 159             if (sd || rd)
 160                 r = SG_COMPAT_FAIL;
 161         }
 162         break;
 163     }
 164     return (r);
 165 }
 166
 167 /*
 168  * SameType() - return 1 if the types are exactly the same, 0 if they are
 169  * not.
 170  *
 171  * The sqFlags for t2 may be overriden.  If you do not wish to override the
 172  * sqFlags for t2, pass -1.  The override only applies to the top level of
 173  * the type.
 174  *
 175  * Types can be aliased - for example, two different type structures may
 176  * point to the same class data.
 177  *
 178  * XXX this needs a lot of work.  We really need to guarentee some level of
 179  * uniqueness for non-qualified type elements.
 180  */
 181 int
 182 SameType(Type *t1, Type *t2, int sqFlags2)
 183 {
 184     for (;;) {
 185         if (t1 == t2)
 186             return (1);
 187         if (t1->ty_Op != t2->ty_Op)
 188             break;
 189         if (sqFlags2 == -1)
 190             sqFlags2 = t2->ty_SQFlags;
 191         if (t1->ty_SQFlags != sqFlags2)
 192             break;
 193         switch (t1->ty_Op) {
 194         case TY_IMPORT:
 195             if (t1->ty_ImportType.et_SemGroup == t2->ty_ImportType.et_SemGroup)
 196                 return (1);
 197             return (0);
 198         case TY_CLASS:
 199             if (t1->ty_ClassType.et_SemGroup == t2->ty_ClassType.et_SemGroup &&
 200                 SameType(t1->ty_ClassType.et_Super,
 201                          t2->ty_ClassType.et_Super, -1))
 202             {
 203                 return (1);
 204             }
 205             return (0);
 206         case TY_PTRTO:
 207             t1 = t1->ty_RawPtrType.et_Type;
 208             t2 = t2->ty_RawPtrType.et_Type;
 209             break;
 210         case TY_REFTO:
 211             t1 = t1->ty_RefType.et_Type;
 212             t2 = t2->ty_RefType.et_Type;
 213             break;
 214         case TY_ARYOF:
 215         case TY_VAR:
 216         case TY_COMPOUND:
 217         case TY_PROC:
 218             /* XXX */
 219             return (0);
 220         case TY_STORAGE:
 221         case TY_ARGS:
 222         case TY_UNRESOLVED:
 223         case TY_DYNAMIC:
 224             /* XXX */
 225             return (0);
 226         default:
 227             dassert_type(t1, 0);
 228             return (0);
 229         }
 230         sqFlags2 = t2->ty_SQFlags;
 231     }
 232     return (0);
 233 }
 234
 235 /*
 236  * SimilarType() - like SameType(), but ignores storage qualifiers (except
 237  * SF_CONST) and if t2 is varargs, compares the original version.
 238  *
 239  * Used when casting t2 (rhs) to t1 (lhs).
 240  */
 241 int
 242 SimilarType(Type *t1, Type *t2)
 243 {
 244     int     check_const = 0;
 245
 246
 247     if (t2->ty_Op == TY_VAR)
 248         t2 = t2->ty_VarType.et_Type;
 249
 250     for (;;) {
 251         if (t1 == t2)
 252             return (1);
 253
 254         /*
 255          * Check for an incompatible constant conversion if we loop through a
 256          * pointer or ref.  Allow compatibility for e.g. rvalues (const int)1
 257          * == (int)1
 258          */
 259         if (check_const &&
 260             (t2->ty_SQFlags & SF_CONST) &&
 261             (t1->ty_SQFlags & SF_CONST) == 0) {
 262             return (0);
 263         }
 264         if (t2->ty_Op != t1->ty_Op)
 265             break;
 266         switch (t1->ty_Op) {
 267         case TY_IMPORT:
 268             if (t1->ty_ImportType.et_SemGroup ==
 269                 t2->ty_ImportType.et_SemGroup) {
 270                 return (1);
 271             }
 272             return (0);
 273         case TY_CLASS:
 274             if (t1->ty_ClassType.et_SemGroup ==
 275                 t2->ty_ClassType.et_SemGroup &&
 276                 SameType(t1->ty_ClassType.et_Super,
 277                          t2->ty_ClassType.et_Super, -1)) {
 278                 return (1);
 279             }
 280             return (0);
 281         case TY_PTRTO:
 282             t1 = t1->ty_RawPtrType.et_Type;
 283             t2 = t2->ty_RawPtrType.et_Type;
 284             break;
 285         case TY_REFTO:
 286             /*
 287              * Reference types are similar if the lhs is a superclass of the
 288              * rhs and partially compatible (only method call changes and
 289              * extensions).
 290              */
 291             t1 = t1->ty_RefType.et_Type;
 292             t2 = t2->ty_RefType.et_Type;
 293             if (MatchType(t1, t2) <= SG_COMPAT_PART) {
 294                 return (1);
 295             }
 296             return (0);
 297             break;
 298         case TY_COMPOUND:
 299             /*
 300              * Compare the elements making up the compound type. XXX
 301              */
 302             return (SimilarSemGroup(t1->ty_CompType.et_SemGroup,
 303                                     t2->ty_CompType.et_SemGroup));
 304             break;
 305         case TY_ARYOF:
 306         case TY_VAR:
 307         case TY_PROC:
 308             /* XXX */
 309             return (0);
 310         case TY_STORAGE:
 311         case TY_ARGS:
 312         case TY_UNRESOLVED:
 313         case TY_DYNAMIC:
 314             /* XXX */
 315             return (0);
 316         default:
 317             dassert_type(t1, 0);
 318             return (0);
 319         }
 320         check_const = 1;
 321     }
 322     return (0);
 323 }
 324
 325 /*
 326  * SimilarSemGroup() - check to see if the storage underlying the two
 327  * semantic groups is compatible.
 328  */
 329 int
 330 SimilarSemGroup(SemGroup *s1, SemGroup *s2)
 331 {
 332     Declaration *d1;
 333     Declaration *d2;
 334
 335     if (s1->sg_Bytes != s2->sg_Bytes)
 336         return (0);
 337     d1 = RUNE_FIRST(&s1->sg_DeclList);
 338     d2 = RUNE_FIRST(&s2->sg_DeclList);
 339     for (;;) {
 340         while (d1 &&
 341                ((d1->d_Op & DOPF_STORAGE) == 0 ||
 342                 d1->d_Op == DOP_GLOBAL_STORAGE)
 343             ) {
 344             d1 = RUNE_NEXT(d1, d_Node);
 345         }
 346         while (d2 &&
 347                ((d2->d_Op & DOPF_STORAGE) == 0 ||
 348                 d2->d_Op == DOP_GLOBAL_STORAGE)
 349             ) {
 350             d2 = RUNE_NEXT(d2, d_Node);
 351         }
 352         if (d1 == NULL || d2 == NULL)
 353             break;
 354         if (SimilarType(d1->d_StorDecl.ed_Type,
 355                         d2->d_StorDecl.ed_Type) == 0) {
 356             break;
 357         }
 358         d1 = RUNE_NEXT(d1, d_Node);
 359         d2 = RUNE_NEXT(d2, d_Node);
 360     }
 361     if (d1 || d2)
 362         return (0);             /* compare bad */
 363     return (1);                 /* compare good */
 364 }
 365
 366 static char *SaveStr[8];
 367 static int SaveIndex;
 368
 369 static
 370 char *
 371 typeToStr(Type *type, char **pstr, int simple)
 372 {
 373     char    buf[RUNE_IDTOSTR_LEN];
 374     char    *str = NULL;
 375     char    *s1 = NULL;
 376     char    *s2 = NULL;
 377     Stmt    *st;
 378     SemGroup *sg;
 379     Declaration *d;
 380     int     count;
 381     int     flags;
 382
 383     if (type == NULL) {
 384         safe_asprintf(&str, "(null)");
 385     } else {
 386         switch (type->ty_Op) {
 387         case TY_CLASS:
 388             st = type->ty_ClassType.et_SemGroup->sg_Stmt;
 389             if (st) {
 390                 dassert(st->st_Op == ST_Class);
 391 #if 1
 392                 safe_asprintf(&str, "%s",
 393                           runeid_text(st->st_ClassStmt.es_Decl->d_Id, buf));
 394 #else
 395                 LexPrintRef(&st->st_LexRef, 0);
 396                 safe_asprintf(&str, "%s(",
 397                           runeid_text(st->st_ClassStmt.es_Decl->d_Id, buf));
 398                 if (type->ty_Flags & (TF_ISINTEGER | TF_ISFLOAT |
 399                                       TF_ISBOOL)) {
 400                     break;
 401                 }
 402
 403                 count = 0;
 404                 for (;;) {
 405                     while (st && st->st_Op != ST_Import)
 406                         st = st->st_Parent;
 407                     if (st == NULL)
 408                         break;
 409                     safe_replacef(&str, "%s%s%s",
 410                                   str,
 411                                   (count ? "," : ""),
 412                     /* st->st_ImportStmt.es_Path, */
 413                                   st->st_ImportStmt.es_File);
 414                     st = st->st_Parent;
 415                     ++count;
 416                 }
 417                 safe_replacef(&str, "%s)", str);
 418 #endif
 419             } else {
 420                 safe_asprintf(&str, "(class_sg=%p)",
 421                               type->ty_ClassType.et_SemGroup);
 422             }
 423             break;
 424         case TY_IMPORT:
 425             st = type->ty_ImportType.et_SemGroup->sg_Stmt;
 426             if (st) {
 427                 dassert(st->st_Op == ST_Module);
 428                 safe_asprintf(&str, "IMPORT(%s)",
 429                               st->st_LexRef.lr_Lex->l_Path);
 430             } else {
 431                 safe_asprintf(&str, "IMPORT(sg=%p)",
 432                               type->ty_ImportType.et_SemGroup);
 433             }
 434             break;
 435         case TY_PTRTO:
 436             typeToStr(type->ty_RawPtrType.et_Type, &s1, simple);
 437             safe_replacef(&str, "*%s", s1);
 438             break;
 439         case TY_REFTO:
 440             typeToStr(type->ty_RefType.et_Type, &s1, simple);
 441             safe_replacef(&str, "@%s", s1);
 442             break;
 443         case TY_ARYOF:
 444             typeToStr(type->ty_AryType.et_Type, &s1, simple);
 445             safe_replacef(&str, "%s[%jd]",
 446                           s1, (intmax_t) type->ty_AryType.et_Count);
 447             break;
 448         case TY_COMPOUND:
 449             sg = type->ty_CompType.et_SemGroup;
 450             safe_asprintf(&str, "COMP(");
 451             count = 0;
 452
 453             RUNE_FOREACH(d, &sg->sg_DeclList, d_Node) {
 454                 if (d->d_Op & DOPF_STORAGE) {
 455                     Type   *dtype = d->d_StorDecl.ed_Type;
 456                     typeToStr(dtype, &s1, 1);
 457                     if (count)
 458                         safe_replacef(&str, "%s,%s",
 459                                       str, s1);
 460                     else
 461                         safe_replacef(&str, "%s%s",
 462                                       str, s1);
 463                     ++count;
 464                     safe_free(&s1);
 465                 }
 466             }
 467             safe_replacef(&str, "%s)", str);
 468             break;
 469         case TY_VAR:
 470             safe_replacef(&str, "VAR");
 471             break;
 472         case TY_ARGS:
 473             sg = type->ty_ArgsType.et_SemGroup;
 474             safe_asprintf(&str, "ARGS(");
 475             count = 0;
 476             RUNE_FOREACH(d, &sg->sg_DeclList, d_Node) {
 477                 if (d->d_Op & DOPF_STORAGE) {
 478                     Type   *dtype = d->d_StorDecl.ed_Type;
 479                     typeToStr(dtype, &s1, 1);
 480                     if (count)
 481                         safe_replacef(&str, "%s,%s",
 482                                       str, s1);
 483                     else
 484                         safe_replacef(&str, "%s%s",
 485                                       str, s1);
 486                     safe_free(&s1);
 487                     ++count;
 488                 }
 489             }
 490             safe_replacef(&str, "%s)", str);
 491             break;
 492         case TY_PROC:
 493             {
 494                 Type   *rtype = type->ty_ProcType.et_RetType;
 495                 Type   *atype = type->ty_ProcType.et_ArgsType;
 496                 typeToStr(rtype, &s1, 1);
 497                 typeToStr(atype, &s2, 1);
 498                 safe_asprintf(&str, "%s %s", s1, s2);
 499             }
 500             break;
 501         case TY_STORAGE:
 502             safe_asprintf(&str, "STORAGE(%d)",
 503                           type->ty_StorType.et_Bytes);
 504             break;
 505         case TY_DYNAMIC:
 506             safe_asprintf(&str, "DYNAMIC");
 507             break;
 508         case TY_UNRESOLVED:
 509             safe_asprintf(&str, "UNRES(");
 510             for (count = 0; type->ty_UnresType.et_DottedId[count]; ++count) {
 511                 runeid_t id;
 512
 513                 id = type->ty_UnresType.et_DottedId[count];
 514
 515                 if (count) {
 516                     safe_replacef(&str, "%s.%s", str, runeid_text(id, buf));
 517                 } else {
 518                     safe_replacef(&str, "%s%s", str, runeid_text(id, buf));
 519                 }
 520             }
 521             safe_replacef(&str, "%s)", str);
 522             break;
 523         default:
 524             safe_asprintf(&str, "?");
 525             break;
 526         }
 527         flags = type->ty_SQFlags;
 528         count = 0;
 529         while (flags) {
 530             const char *sqflag;
 531
 532             if (flags & SF_CONST) {
 533                 sqflag = "const";
 534                 flags &= ~SF_CONST;
 535             } else if (flags & SF_VOLATILE) {
 536                 sqflag = "volatile";
 537                 flags &= ~SF_VOLATILE;
 538             } else if (flags & SF_VARARGS) {
 539                 sqflag = "varargs";
 540                 flags &= ~SF_VARARGS;
 541             } else if (flags & SF_LVALUE) {
 542                 sqflag = "lvalue";
 543                 flags &= ~SF_LVALUE;
 544             } else if (flags & SF_NOZERO) {
 545                 sqflag = "__nozero";
 546                 flags &= ~SF_NOZERO;
 547             } else if (flags & SF_METHOD) {
 548                 sqflag = "method";
 549                 flags &= ~SF_METHOD;
 550             } else if (flags & SF_GMETHOD) {
 551                 sqflag = "gmethod";
 552                 flags &= ~SF_GMETHOD;
 553             } else if (flags & SF_STRUCT) {
 554                 sqflag = "structure";
 555                 flags &= ~SF_STRUCT;
 556             } else if (flags & SF_INTERNAL) {
 557                 sqflag = "internal";
 558                 flags &= ~SF_INTERNAL;
 559             } else {
 560                 sqflag = "bad";
 561                 flags = 0;
 562             }
 563             safe_replacef(&str, "%s%s%s",
 564                           sqflag, " ", str);
 565             ++count;
 566         }
 567     }
 568     safe_free(&s1);
 569     safe_free(&s2);
 570     if (pstr) {
 571         safe_free(pstr);
 572         *pstr = str;
 573     } else {
 574         safe_free(&SaveStr[SaveIndex]);
 575         SaveStr[SaveIndex] = str;
 576         SaveIndex = (SaveIndex + 1) % arysize(SaveStr);
 577     }
 578     return (str);
 579 }
 580
 581 char *
 582 TypeToStr(Type *type, char **pstr)
 583 {
 584     char   *str = NULL;
 585     char   *res;
 586
 587     res = typeToStr(type, pstr, 0);
 588     safe_asprintf(&str, "<TYPE_%p %s>", type, res);
 589     if (pstr) {
 590         safe_free(pstr);
 591         *pstr = str;
 592     } else {
 593         safe_free(&SaveStr[SaveIndex]);
 594         SaveStr[SaveIndex] = str;
 595         SaveIndex = (SaveIndex + 1) % arysize(SaveStr);
 596     }
 597     return (str);
 598 }
 599
 600 void
 601 TypePrintRef(Type *type, int t __unused)
 602 {
 603     fflush(stdout);
 604     fprintf(stderr, "for type: %s\n", TypeToStr(type, NULL));
 605     fflush(stderr);
 606 }