typeinfo.c

   1 /********************************* typeinfo.c *********************************
   2
   3         Copyright (c) 2003 ? XXX
   4
   5         See file COPYRIGHT for information on usage and disclaimer of warranties
   6
   7         functions for the compiler's type system
   8
   9         Authors: Edwin Steiner
  10
  11         Last Change:
  12
  13 *******************************************************************************/
  14
  15 #include "typeinfo.h"
  16 #include "tables.h"
  17 #include "loader.h"
  18
  19 #define TYPEINFO_REUSE_MERGED
  20
  21 #define CLASS_IMPLEMENTS_INTERFACE(cls,index)                   \
  22     ( ((index) < (cls)->vftbl->interfacetablelength)            \
  23       && (VFTBLINTERFACETABLE((cls)->vftbl,(index)) != NULL) )
  24
  25 /**********************************************************************/
  26 /* READ-ONLY FUNCTIONS                                                */
  27 /* The following functions don't change typeinfo data.                */
  28 /**********************************************************************/
  29
  30 bool
  31 typeinfo_is_array(typeinfo *info)
  32 {
  33     return TYPEINFO_IS_ARRAY(*info);
  34 }
  35
  36 bool
  37 typeinfo_is_primitive_array(typeinfo *info,int arraytype)
  38 {
  39     return TYPEINFO_IS_PRIMITIVE_ARRAY(*info,arraytype);
  40 }
  41
  42 bool
  43 typeinfo_is_array_of_refs(typeinfo *info)
  44 {
  45     return TYPEINFO_IS_ARRAY_OF_REFS(*info);
  46 }
  47
  48 static
  49 bool
  50 interface_extends_interface(classinfo *cls,classinfo *interf)
  51 {
  52     int i;
  53
  54     /* first check direct superinterfaces */
  55     for (i=0; i<cls->interfacescount; ++i) {
  56         if (cls->interfaces[i] == interf)
  57             return true;
  58     }
  59
  60     /* check indirect superinterfaces */
  61     for (i=0; i<cls->interfacescount; ++i) {
  62         if (interface_extends_interface(cls->interfaces[i],interf))
  63             return true;
  64     }
  65
  66     return false;
  67 }
  68
  69 /* XXX If really a performance issue, this could become a macro. */
  70 static
  71 bool
  72 classinfo_implements_interface(classinfo *cls,classinfo *interf)
  73 {
  74     if (cls->flags & ACC_INTERFACE) {
  75         /* cls is an interface */
  76         if (cls == interf)
  77             return true;
  78
  79         /* check superinterfaces */
  80         return interface_extends_interface(cls,interf);
  81     }
  82
  83     return CLASS_IMPLEMENTS_INTERFACE(cls,interf->index);
  84 }
  85
  86 bool mergedlist_implements_interface(typeinfo_mergedlist *merged,
  87                                      classinfo *interf)
  88 {
  89     int i;
  90     classinfo **mlist;
  91
  92     /* Check if there is an non-empty mergedlist. */
  93     if (!merged)
  94         return false;
  95
  96     /* If all classinfos in the (non-empty) merged array implement the
  97      * interface return true, otherwise false.
  98      */
  99     mlist = merged->list;
 100     i = merged->count;
 101     while (i--) {
 102         if (!classinfo_implements_interface(*mlist++,interf))
 103             return false;
 104     }
 105     return true;
 106 }
 107
 108 bool
 109 merged_implements_interface(classinfo *typeclass,typeinfo_mergedlist *merged,
 110                             classinfo *interf)
 111 {
 112     /* primitive types don't support interfaces. */
 113     if (!typeclass)
 114         return false;
 115
 116     /* the null type can be cast to any interface type. */
 117     if (typeclass == pseudo_class_Null)
 118         return true;
 119
 120     /* check if typeclass implements the interface. */
 121     if (classinfo_implements_interface(typeclass,interf))
 122         return true;
 123
 124     /* check the mergedlist */
 125     return (merged && mergedlist_implements_interface(merged,interf));
 126 }
 127
 128 bool
 129 typeinfo_is_assignable(typeinfo *value,typeinfo *dest)
 130 {
 131     classinfo *cls;
 132
 133     cls = value->typeclass;
 134
 135     /* DEBUG CHECK: dest must not have a merged list. */
 136 #ifdef DEBUG_TYPES
 137     if (dest->merged)
 138         panic("Internal error: typeinfo_is_assignable on merged destination.");
 139 #endif
 140
 141     /* assignments of primitive values are not checked here. */
 142     if (!cls && !dest->typeclass)
 143         return true;
 144
 145     /* the null type can be assigned to any type */
 146     if (TYPEINFO_IS_NULLTYPE(*value))
 147         return true;
 148
 149     /* primitive and reference types are not assignment compatible. */
 150     if (!cls || !dest->typeclass)
 151         return false;
 152
 153     if (dest->typeclass->flags & ACC_INTERFACE) {
 154         /* We are assigning to an interface type. */
 155         return merged_implements_interface(cls,value->merged,
 156                                            dest->typeclass);
 157     }
 158
 159     if (TYPEINFO_IS_ARRAY(*dest)) {
 160         /* We are assigning to an array type. */
 161         if (!TYPEINFO_IS_ARRAY(*value))
 162             return false;
 163
 164         /* {Both value and dest are array types.} */
 165
 166         /* value must have at least the dimension of dest. */
 167         if (value->dimension < dest->dimension)
 168             return false;
 169
 170         if (value->dimension > dest->dimension) {
 171             /* value has higher dimension so we need to check
 172              * if its component array can be assigned to the
 173              * element type of dest */
 174
 175             if (dest->elementclass->flags & ACC_INTERFACE) {
 176                 /* We are assigning to an interface type. */
 177                 return classinfo_implements_interface(pseudo_class_Arraystub,
 178                                                       dest->elementclass);
 179             }
 180
 181             /* We are assigning to a class type. */
 182             return class_issubclass(pseudo_class_Arraystub,dest->elementclass);
 183         }
 184
 185         /* {value and dest have the same dimension} */
 186
 187         if (value->elementtype != dest->elementtype)
 188             return false;
 189
 190         if (value->elementclass) {
 191             /* We are assigning an array of objects so we have to
 192              * check if the elements are assignable.
 193              */
 194
 195             if (dest->elementclass->flags & ACC_INTERFACE) {
 196                 /* We are assigning to an interface type. */
 197
 198                 return merged_implements_interface(value->elementclass,
 199                                                    value->merged,
 200                                                    dest->elementclass);
 201             }
 202
 203             /* We are assigning to a class type. */
 204             return class_issubclass(value->elementclass,dest->elementclass);
 205         }
 206
 207         return true;
 208     }
 209
 210     /* {dest is not an array} */
 211
 212     /* We are assigning to a class type */
 213     if (cls->flags & ACC_INTERFACE)
 214         cls = class_java_lang_Object;
 215
 216     return class_issubclass(cls,dest->typeclass);
 217 }
 218
 219 /**********************************************************************/
 220 /* INITIALIZATION FUNCTIONS                                           */
 221 /* The following functions fill in uninitialized typeinfo structures. */
 222 /**********************************************************************/
 223
 224 /* XXX delete */
 225 #if 0
 226 void
 227 typeinfo_init_from_arraydescriptor(typeinfo *info,
 228                                    constant_arraydescriptor *desc)
 229 {
 230     int dim = 1;
 231
 232     /* Arrays are instances of the pseudo class Array. */
 233     info->typeclass = pseudo_class_Array; /* XXX */
 234     info->merged = NULL;
 235
 236     /* Handle multidimensional arrays */
 237     while (desc->arraytype == ARRAYTYPE_ARRAY) {
 238         dim++;
 239         desc = desc->elementdescriptor;
 240     }
 241
 242     info->dimension = dim;
 243
 244     if ((info->elementtype = desc->arraytype) == ARRAYTYPE_OBJECT) {
 245         info->elementclass = desc->objectclass;
 246     }
 247     else {
 248         info->elementclass = NULL;
 249     }
 250 }
 251 #endif
 252
 253 void
 254 typeinfo_init_from_descriptor(typeinfo *info,char *utf_ptr,char *end_ptr)
 255 {
 256     classinfo *cls;
 257     char *end;
 258     cls = class_from_descriptor(utf_ptr,end_ptr,&end,CLASSLOAD_NEW);
 259
 260     if (!cls)
 261         panic("Invalid descriptor.");
 262
 263     switch (*utf_ptr) {
 264       case 'L':
 265       case '[':
 266           /* a class, interface or array descriptor */
 267           TYPEINFO_INIT_CLASSINFO(*info,cls);
 268           break;
 269       default:
 270           /* a primitive type */
 271           TYPEINFO_INIT_PRIMITIVE(*info);
 272     }
 273
 274     /* exceeding characters */
 275     if (end!=end_ptr) panic ("descriptor has exceeding chars");
 276 }
 277
 278 int
 279 typeinfo_count_method_args(utf *d,bool twoword)
 280 {
 281     int args = 0;
 282     char *utf_ptr = d->text;
 283     char *end_pos = utf_end(d);
 284     char c,ch;
 285
 286     /* method descriptor must start with parenthesis */
 287     if (*utf_ptr++ != '(') panic ("Missing '(' in method descriptor");
 288
 289     /* check arguments */
 290     while ((c = *utf_ptr++) != ')') {
 291         switch (c) {
 292           case 'B':
 293           case 'C':
 294           case 'I':
 295           case 'S':
 296           case 'Z':
 297           case 'F':
 298               /* primitive one-word type */
 299               args++;
 300               break;
 301
 302           case 'J':
 303           case 'D':
 304               /* primitive two-word type */
 305               args++;
 306               if (twoword) args++;
 307               break;
 308
 309           case 'L':
 310               /* skip classname */
 311               while ( *utf_ptr++ != ';' )
 312                   if (utf_ptr>=end_pos)
 313                       panic ("Missing ';' in objecttype-descriptor");
 314
 315               args++;
 316               break;
 317
 318           case '[' :
 319               /* array type */
 320               while ((ch = *utf_ptr++)=='[')
 321                   /* skip */ ;
 322
 323               /* component type of array */
 324               switch (ch) {
 325                 case 'B':
 326                 case 'C':
 327                 case 'I':
 328                 case 'S':
 329                 case 'Z':
 330                 case 'J':
 331                 case 'F':
 332                 case 'D':
 333                     /* primitive type */
 334                     break;
 335
 336                 case 'L':
 337                     /* skip classname */
 338                     while ( *utf_ptr++ != ';' )
 339                         if (utf_ptr>=end_pos)
 340                             panic ("Missing ';' in objecttype-descriptor");
 341                     break;
 342
 343                 default:
 344                     panic ("Ill formed methodtype-descriptor");
 345               }
 346
 347               args++;
 348               break;
 349
 350           default:
 351               panic ("Ill formed methodtype-descriptor");
 352         }
 353     }
 354
 355     return args;
 356 }
 357
 358 void
 359 typeinfo_init_from_method_args(utf *desc,u1 *typebuf,typeinfo *infobuf,
 360                                int buflen,bool twoword,
 361                                int *returntype,typeinfo *returntypeinfo)
 362 {
 363     char *utf_ptr = desc->text;     /* current position in utf text   */
 364     char *end_pos = utf_end(desc);  /* points behind utf string       */
 365     char c;
 366     int args = 0;
 367     classinfo *cls;
 368
 369     /* method descriptor must start with parenthesis */
 370     if (*utf_ptr++ != '(') panic ("Missing '(' in method descriptor");
 371
 372     /* check arguments */
 373     while ((c = *utf_ptr) != ')') {
 374         cls = class_from_descriptor(utf_ptr,end_pos,&utf_ptr,CLASSLOAD_NEW);
 375         if (!cls)
 376             panic("Invalid method descriptor.");
 377
 378         switch (c) {
 379           case 'B':
 380           case 'C':
 381           case 'I':
 382           case 'S':
 383           case 'Z':
 384           case 'F':
 385               /* primitive one-word type */
 386               if (++args > buflen)
 387                   panic("Buffer too small for method arguments.");
 388               if (typebuf)
 389                   *typebuf++ = (c == 'F') ? TYPE_FLOAT : TYPE_INT; /* XXX TYPE_FLT? */
 390               TYPEINFO_INIT_PRIMITIVE(*infobuf);
 391               infobuf++;
 392               break;
 393
 394           case 'J':
 395           case 'D':
 396               /* primitive two-word type */
 397               if (++args > buflen)
 398                   panic("Buffer too small for method arguments.");
 399               if (typebuf)
 400                   *typebuf++ = (c == 'J') ? TYPE_LONG : TYPE_DOUBLE; /* XXX TYPE_DBL? */
 401               TYPEINFO_INIT_PRIMITIVE(*infobuf);
 402               infobuf++;
 403               if (twoword) {
 404                   if (++args > buflen)
 405                       panic("Buffer too small for method arguments.");
 406                   TYPEINFO_INIT_PRIMITIVE(*infobuf);
 407                   infobuf++;
 408               }
 409               break;
 410
 411           case 'L':
 412           case '[' :
 413               /* reference type */
 414
 415               if (++args > buflen)
 416                   panic("Buffer too small for method arguments.");
 417               if (typebuf)
 418                   *typebuf++ = TYPE_ADDRESS;
 419
 420               TYPEINFO_INIT_CLASSINFO(*infobuf,cls);
 421               /* XXX remove */ /* utf_display(cls->name); */
 422               infobuf++;
 423               break;
 424
 425           default:
 426               panic ("Ill formed methodtype-descriptor (type)");
 427         }
 428     }
 429     utf_ptr++; /* skip ')' */
 430
 431     /* check returntype */
 432     if (returntype) {
 433         switch (*utf_ptr) {
 434           case 'B':
 435           case 'C':
 436           case 'I':
 437           case 'S':
 438           case 'Z':
 439               *returntype = TYPE_INT;
 440               goto primitive_tail;
 441
 442           case 'J':
 443               *returntype = TYPE_LONG;
 444               goto primitive_tail;
 445
 446           case 'F':
 447               *returntype = TYPE_FLOAT;
 448               goto primitive_tail;
 449
 450           case 'D':
 451               *returntype = TYPE_DOUBLE;
 452               goto primitive_tail;
 453
 454           case 'V':
 455               *returntype = TYPE_VOID;
 456       primitive_tail:
 457               if ((utf_ptr+1) != end_pos)
 458                   panic ("Method-descriptor has exceeding chars");
 459               if (returntypeinfo) {
 460                   TYPEINFO_INIT_PRIMITIVE(*returntypeinfo);
 461               }
 462               break;
 463
 464           case 'L':
 465           case '[':
 466               *returntype = TYPE_ADDRESS;
 467               cls = class_from_descriptor(utf_ptr,end_pos,&utf_ptr,CLASSLOAD_NEW);
 468               if (!cls)
 469                   panic("Invalid return type");
 470               if (utf_ptr != end_pos)
 471                   panic ("Method-descriptor has exceeding chars");
 472               if (returntypeinfo) {
 473                   TYPEINFO_INIT_CLASSINFO(*returntypeinfo,cls);
 474               }
 475               break;
 476
 477           default:
 478               panic ("Ill formed methodtype-descriptor (returntype)");
 479         }
 480     }
 481 }
 482
 483 /* XXX could be made a macro if really performance critical */
 484 void
 485 typeinfo_init_component(typeinfo *srcarray,typeinfo *dst)
 486 {
 487     vftbl *comp = NULL;
 488
 489     /* XXX find component class */
 490     if (!TYPEINFO_IS_ARRAY(*srcarray))
 491         panic("Trying to access component of non-array");
 492
 493     comp = srcarray->typeclass->vftbl->arraydesc->componentvftbl;
 494     if (comp) {
 495         TYPEINFO_INIT_CLASSINFO(*dst,comp->class);
 496     }
 497     else {
 498         TYPEINFO_INIT_PRIMITIVE(*dst);
 499     }
 500
 501     /* XXX assign directly ? */
 502 #if 0
 503     if ((dst->dimension = srcarray->dimension - 1) == 0) {
 504         dst->typeclass = srcarray->elementclass;
 505         dst->elementtype = 0;
 506         dst->elementclass = NULL;
 507     }
 508     else {
 509         dst->typeclass = srcarray->typeclass;
 510         dst->elementtype = srcarray->elementtype;
 511         dst->elementclass = srcarray->elementclass;
 512     }
 513 #endif
 514
 515     dst->merged = srcarray->merged;
 516 }
 517
 518 /* Condition: src != dest. */
 519 void
 520 typeinfo_clone(typeinfo *src,typeinfo *dest)
 521 {
 522     int count;
 523     classinfo **srclist,**destlist;
 524
 525 #ifdef DEBUG_TYPES
 526     if (src == dest)
 527         panic("Internal error: typeinfo_clone with src==dest");
 528 #endif
 529
 530     *dest = *src;
 531
 532     if (src->merged) {
 533         count = src->merged->count;
 534         TYPEINFO_ALLOCMERGED(dest->merged,count);
 535         dest->merged->count = count;
 536
 537         /* XXX use memcpy? */
 538         srclist = src->merged->list;
 539         destlist = dest->merged->list;
 540         while (count--)
 541             *destlist++ = *srclist++;
 542     }
 543 }
 544
 545 /**********************************************************************/
 546 /* MISCELLANEOUS FUNCTIONS                                            */
 547 /**********************************************************************/
 548
 549 void
 550 typeinfo_free(typeinfo *info)
 551 {
 552     TYPEINFO_FREE(*info);
 553 }
 554
 555 /**********************************************************************/
 556 /* MERGING FUNCTIONS                                                  */
 557 /* The following functions are used to merge the types represented by */
 558 /* two typeinfo structures into one typeinfo structure.               */
 559 /**********************************************************************/
 560
 561 static
 562 void
 563 typeinfo_merge_error(char *str,typeinfo *x,typeinfo *y) {
 564 #ifdef DEBUG_TYPES
 565     fprintf(stderr,"Error in typeinfo_merge: %s\n",str);
 566     fprintf(stderr,"Typeinfo x:\n");
 567     typeinfo_print(stderr,x,1);
 568     fprintf(stderr,"Typeinfo y:\n");
 569     typeinfo_print(stderr,y,1);
 570 #endif
 571     panic(str);
 572 }
 573
 574 /* Condition: clsx != clsy. */
 575 /* Returns: true if dest was changed (always true). */
 576 static
 577 bool
 578 typeinfo_merge_two(typeinfo *dest,classinfo *clsx,classinfo *clsy)
 579 {
 580     TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
 581     TYPEINFO_ALLOCMERGED(dest->merged,2);
 582     dest->merged->count = 2;
 583
 584 #ifdef DEBUG_TYPES
 585     if (clsx == clsy)
 586         panic("Internal error: typeinfo_merge_two called with clsx==clsy.");
 587 #endif
 588
 589     if (clsx < clsy) {
 590         dest->merged->list[0] = clsx;
 591         dest->merged->list[1] = clsy;
 592     }
 593     else {
 594         dest->merged->list[0] = clsy;
 595         dest->merged->list[1] = clsx;
 596     }
 597
 598     return true;
 599 }
 600
 601 /* Returns: true if dest was changed. */
 602 static
 603 bool
 604 typeinfo_merge_add(typeinfo *dest,typeinfo_mergedlist *m,classinfo *cls)
 605 {
 606     int count;
 607     typeinfo_mergedlist *newmerged;
 608     classinfo **mlist,**newlist;
 609
 610     count = m->count;
 611     mlist = m->list;
 612
 613     /* Check if cls is already in the mergedlist m. */
 614     while (count--) {
 615         if (*mlist++ == cls) {
 616             /* cls is in the list, so m is the resulting mergedlist */
 617             if (dest->merged == m)
 618                 return false;
 619
 620             /* We have to copy the mergedlist */
 621             TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
 622             count = m->count;
 623             TYPEINFO_ALLOCMERGED(dest->merged,count);
 624             dest->merged->count = count;
 625             newlist = dest->merged->list;
 626             mlist = m->list;
 627             while (count--) {
 628                 *newlist++ = *mlist++;
 629             }
 630             return true;
 631         }
 632     }
 633
 634     /* Add cls to the mergedlist. */
 635     count = m->count;
 636     TYPEINFO_ALLOCMERGED(newmerged,count+1);
 637     newmerged->count = count+1;
 638     newlist = newmerged->list;
 639     mlist = m->list;
 640     while (count) {
 641         if (*mlist > cls)
 642             break;
 643         *newlist++ = *mlist++;
 644         count--;
 645     }
 646     *newlist++ = cls;
 647     while (count--) {
 648         *newlist++ = *mlist++;
 649     }
 650
 651     /* Put the new mergedlist into dest. */
 652     TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
 653     dest->merged = newmerged;
 654
 655     return true;
 656 }
 657
 658 /* Returns: true if dest was changed. */
 659 static
 660 bool
 661 typeinfo_merge_mergedlists(typeinfo *dest,typeinfo_mergedlist *x,
 662                            typeinfo_mergedlist *y)
 663 {
 664     int count = 0;
 665     int countx,county;
 666     typeinfo_mergedlist *temp,*result;
 667     classinfo **clsx,**clsy,**newlist;
 668
 669     /* count the elements that will be in the resulting list */
 670     /* (Both lists are sorted, equal elements are counted only once.) */
 671     clsx = x->list;
 672     clsy = y->list;
 673     countx = x->count;
 674     county = y->count;
 675     while (countx && county) {
 676         if (*clsx == *clsy) {
 677             clsx++;
 678             clsy++;
 679             countx--;
 680             county--;
 681         }
 682         else if (*clsx < *clsy) {
 683             clsx++;
 684             countx--;
 685         }
 686         else {
 687             clsy++;
 688             county--;
 689         }
 690         count++;
 691     }
 692     count += countx + county;
 693
 694     /* {The new mergedlist will have count entries.} */
 695
 696     if (y->count == count) {
 697         temp = x; x = y; y = temp;
 698     }
 699     /* {If one of x,y is already the result it is x.} */
 700     if (x->count == count) {
 701         /* x->merged is equal to the result */
 702         if (x == dest->merged)
 703             return false;
 704
 705         if (!dest->merged || dest->merged->count != count) {
 706             TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
 707             TYPEINFO_ALLOCMERGED(dest->merged,count);
 708             dest->merged->count = count;
 709         }
 710
 711         newlist = dest->merged->list;
 712         clsx = x->list;
 713         while (count--) {
 714             *newlist++ = *clsx++;
 715         }
 716         return true;
 717     }
 718
 719     /* {We have to merge two lists.} */
 720
 721     /* allocate the result list */
 722     TYPEINFO_ALLOCMERGED(result,count);
 723     result->count = count;
 724     newlist = result->list;
 725
 726     /* merge the sorted lists */
 727     clsx = x->list;
 728     clsy = y->list;
 729     countx = x->count;
 730     county = y->count;
 731     while (countx && county) {
 732         if (*clsx == *clsy) {
 733             *newlist++ = *clsx++;
 734             clsy++;
 735             countx--;
 736             county--;
 737         }
 738         else if (*clsx < *clsy) {
 739             *newlist++ = *clsx++;
 740             countx--;
 741         }
 742         else {
 743             *newlist++ = *clsy++;
 744             county--;
 745         }
 746     }
 747     while (countx--)
 748             *newlist++ = *clsx++;
 749     while (county--)
 750             *newlist++ = *clsy++;
 751
 752     /* replace the list in dest with the result list */
 753     TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
 754     dest->merged = result;
 755
 756     return true;
 757 }
 758
 759 static
 760 bool
 761 typeinfo_merge_nonarrays(typeinfo *dest,
 762                          classinfo **result,
 763                          classinfo *clsx,classinfo *clsy,
 764                          typeinfo_mergedlist *mergedx,
 765                          typeinfo_mergedlist *mergedy)
 766 {
 767     classinfo *tcls,*common;
 768     typeinfo_mergedlist *tmerged;
 769     bool changed;
 770
 771     /* XXX remove */
 772     /*
 773 #ifdef DEBUG_TYPES
 774     typeinfo dbgx,dbgy;
 775     printf("typeinfo_merge_nonarrays:\n");
 776     TYPEINFO_INIT_CLASSINFO(dbgx,clsx);
 777     dbgx.merged = mergedx;
 778     TYPEINFO_INIT_CLASSINFO(dbgy,clsy);
 779     dbgy.merged = mergedy;
 780     typeinfo_print(stdout,&dbgx,4);
 781     printf("  with:\n");
 782     typeinfo_print(stdout,&dbgy,4);
 783 #endif
 784     */
 785
 786     /* Common case: clsx == clsy */
 787     /* (This case is very simple unless *both* x and y really represent
 788      *  merges of subclasses of clsx==clsy.)
 789      */
 790     /* XXX count this case for statistics */
 791     if ((clsx == clsy) && (!mergedx || !mergedy)) {
 792   return_simple_x:
 793         /* XXX remove */ /* log_text("return simple x"); */
 794         changed = (dest->merged != NULL);
 795         TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
 796         dest->merged = NULL;
 797         *result = clsx;
 798         /* XXX remove */ /* log_text("returning"); */
 799         return changed;
 800     }
 801
 802     /* If clsy is an interface, swap x and y. */
 803     if (clsy->flags & ACC_INTERFACE) {
 804         tcls = clsx; clsx = clsy; clsy = tcls;
 805         tmerged = mergedx; mergedx = mergedy; mergedy = tmerged;
 806     }
 807     /* {We know: If only one of x,y is an interface it is x.} */
 808
 809     /* Handle merging of interfaces: */
 810     if (clsx->flags & ACC_INTERFACE) {
 811         /* {clsx is an interface and mergedx == NULL.} */
 812
 813         if (clsy->flags & ACC_INTERFACE) {
 814             /* We are merging two interfaces. */
 815             /* {mergedy == NULL} */
 816             /* XXX: should we optimize direct superinterfaces? */
 817
 818             /* {We know that clsx!=clsy (see common case at beginning.)} */
 819             *result = class_java_lang_Object;
 820             return typeinfo_merge_two(dest,clsx,clsy);
 821         }
 822
 823         /* {We know: x is an interface, clsy is a class.} */
 824
 825         /* Check if we are merging an interface with java.lang.Object */
 826         if (clsy == class_java_lang_Object && !mergedy) {
 827             clsx = clsy;
 828             goto return_simple_x;
 829         }
 830
 831
 832         /* If the type y implements clsx then the result of the merge
 833          * is clsx regardless of mergedy.
 834          */
 835
 836         if (CLASS_IMPLEMENTS_INTERFACE(clsy,clsx->index)
 837             || mergedlist_implements_interface(mergedy,clsx))
 838         {
 839             /* y implements x, so the result of the merge is x. */
 840             goto return_simple_x;
 841         }
 842
 843         /* {We know: x is an interface, the type y a class or a merge
 844          * of subclasses and does not implement x.} */
 845
 846         /* There may still be superinterfaces of x which are implemented
 847          * by y, too, so we have to add clsx to the mergedlist.
 848          */
 849
 850         /* XXX if x has no superinterfaces we could return a simple java.lang.Object */
 851
 852         common = class_java_lang_Object;
 853         goto merge_with_simple_x;
 854     }
 855
 856     /* {We know: x and y are classes (not interfaces).} */
 857
 858     /* If *x is deeper in the inheritance hierarchy swap x and y. */
 859     if (clsx->index > clsy->index) {
 860         tcls = clsx; clsx = clsy; clsy = tcls;
 861         tmerged = mergedx; mergedx = mergedy; mergedy = tmerged;
 862     }
 863
 864     /* {We know: y is at least as deep in the hierarchy as x.} */
 865
 866     /* Find nearest common anchestor for the classes. */
 867     common = clsx;
 868     tcls = clsy;
 869     while (tcls->index > common->index)
 870         tcls = tcls->super;
 871     while (common != tcls) {
 872         common = common->super;
 873         tcls = tcls->super;
 874     }
 875
 876     /* {common == nearest common anchestor of clsx and clsy.} */
 877
 878     /* XXX remove */ /* printf("common: "); utf_display(common->name); printf("\n"); */
 879
 880     /* If clsx==common and x is a whole class (not a merge of subclasses)
 881      * then the result of the merge is clsx.
 882      */
 883     if (clsx == common && !mergedx) {
 884         goto return_simple_x;
 885     }
 886
 887     if (mergedx) {
 888         *result = common;
 889         if (mergedy)
 890             return typeinfo_merge_mergedlists(dest,mergedx,mergedy);
 891         else
 892             return typeinfo_merge_add(dest,mergedx,clsy);
 893     }
 894
 895  merge_with_simple_x:
 896     *result = common;
 897     if (mergedy)
 898         return typeinfo_merge_add(dest,mergedy,clsx);
 899     else
 900         return typeinfo_merge_two(dest,clsx,clsy);
 901 }
 902
 903 /* Condition: *dest must be a valid initialized typeinfo. */
 904 /* Condition: dest != y. */
 905 /* Returns: true if dest was changed. */
 906 bool
 907 typeinfo_merge(typeinfo *dest,typeinfo* y)
 908 {
 909     typeinfo *x;
 910     typeinfo *tmp;                      /* used for swapping */
 911     classinfo *common;
 912     classinfo *elementclass;
 913     int dimension;
 914     int elementtype;
 915     bool changed;
 916
 917     /* XXX remove */
 918     /*
 919 #ifdef DEBUG_TYPES
 920     typeinfo_print(stdout,dest,4);
 921     typeinfo_print(stdout,y,4);
 922 #endif
 923     */
 924
 925     /* This function cannot be used to merge primitive types. */
 926     if (!dest->typeclass || !y->typeclass)
 927         typeinfo_merge_error("Trying to merge primitive types.",dest,y);
 928
 929 #ifdef DEBUG_TYPES
 930     if (dest == y)
 931         panic("Internal error: typeinfo_merge with dest==y");
 932
 933     /* check that no unlinked classes are merged. */
 934     if (!dest->typeclass->linked || !y->typeclass->linked)
 935         typeinfo_merge_error("Trying to merge unlinked class(es).",dest,y);
 936 #endif
 937
 938     /* XXX remove */ /* log_text("Testing common case"); */
 939
 940     /* Common case: class dest == class y */
 941     /* (This case is very simple unless *both* dest and y really represent
 942      *  merges of subclasses of class dest==class y.)
 943      */
 944     /* XXX count this case for statistics */
 945     if ((dest->typeclass == y->typeclass) && (!dest->merged || !y->merged)) {
 946         changed = (dest->merged != NULL);
 947         TYPEINFO_FREEMERGED_IF_ANY(dest->merged); /* XXX unify if */
 948         dest->merged = NULL;
 949         /* XXX remove */ /* log_text("common case handled"); */
 950         return changed;
 951     }
 952
 953     /* XXX remove */ /* log_text("Handling null types"); */
 954
 955     /* Handle null types: */
 956     if (TYPEINFO_IS_NULLTYPE(*y)) {
 957         return false;
 958     }
 959     if (TYPEINFO_IS_NULLTYPE(*dest)) {
 960         TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
 961         TYPEINFO_CLONE(*y,*dest);
 962         return true;
 963     }
 964
 965     /* This function uses x internally, so x and y can be swapped
 966      * without changing dest. */
 967     x = dest;
 968     changed = false;
 969
 970     /* Handle merging of arrays: */
 971     if (TYPEINFO_IS_ARRAY(*x) && TYPEINFO_IS_ARRAY(*y)) {
 972
 973         /* XXX remove */ /* log_text("Handling arrays"); */
 974
 975         /* Make x the one with lesser dimension */
 976         if (x->dimension > y->dimension) {
 977             tmp = x; x = y; y = tmp;
 978         }
 979
 980         /* If one array (y) has higher dimension than the other,
 981          * interpret it as an array (same dim. as x) of Arraystubs. */
 982         if (x->dimension < y->dimension) {
 983             dimension = x->dimension;
 984             elementtype = ARRAYTYPE_OBJECT;
 985             elementclass = pseudo_class_Arraystub;
 986         }
 987         else {
 988             dimension = y->dimension;
 989             elementtype = y->elementtype;
 990             elementclass = y->elementclass;
 991         }
 992
 993         /* {The arrays are of the same dimension.} */
 994
 995         if (x->elementtype != elementtype) {
 996             /* Different element types are merged, so the resulting array
 997              * type has one accessible dimension less. */
 998             if (--dimension == 0) {
 999                 common = pseudo_class_Arraystub;
1000                 elementtype = 0;
1001                 elementclass = NULL;
1002             }
1003             else {
1004                 common = class_multiarray_of(dimension,pseudo_class_Arraystub);
1005                 elementtype = ARRAYTYPE_OBJECT;
1006                 elementclass = pseudo_class_Arraystub;
1007             }
1008         }
1009         else {
1010             /* {The arrays have the same dimension and elementtype.} */
1011
1012             if (elementtype == ARRAYTYPE_OBJECT) {
1013                 /* The elements are references, so their respective
1014                  * types must be merged.
1015                  */
1016                 changed |= typeinfo_merge_nonarrays(dest,
1017                                                     &elementclass,
1018                                                     x->elementclass,
1019                                                     elementclass,
1020                                                     x->merged,y->merged);
1021
1022                 /* XXX otimize this? */
1023                 /* XXX remove */ /* log_text("finding resulting array class: "); */
1024                 common = class_multiarray_of(dimension,elementclass);
1025                 /* XXX remove */ /* utf_display(common->name); printf("\n"); */
1026             }
1027         }
1028     }
1029     else {
1030         /* {We know that at least one of x or y is no array, so the
1031          *  result cannot be an array.} */
1032
1033         changed |= typeinfo_merge_nonarrays(dest,
1034                                             &common,
1035                                             x->typeclass,y->typeclass,
1036                                             x->merged,y->merged);
1037
1038         dimension = 0;
1039         elementtype = 0;
1040         elementclass = NULL;
1041     }
1042
1043     /* Put the new values into dest if neccessary. */
1044
1045     if (dest->typeclass != common) {
1046         dest->typeclass = common;
1047         changed = true;
1048     }
1049     if (dest->dimension != dimension) {
1050         dest->dimension = dimension;
1051         changed = true;
1052     }
1053     if (dest->elementtype != elementtype) {
1054         dest->elementtype = elementtype;
1055         changed = true;
1056     }
1057     if (dest->elementclass != elementclass) {
1058         dest->elementclass = elementclass;
1059         changed = true;
1060     }
1061
1062     /* XXX remove */ /* log_text("returning from merge"); */
1063
1064     return changed;
1065 }
1066
1067
1068 /**********************************************************************/
1069 /* DEBUGGING HELPERS                                                  */
1070 /**********************************************************************/
1071
1072 #ifdef DEBUG_TYPES
1073
1074 #include "tables.h"
1075 #include "loader.h"
1076
1077 static int
1078 typeinfo_test_compare(classinfo **a,classinfo **b)
1079 {
1080     if (*a == *b) return 0;
1081     if (*a < *b) return -1;
1082     return +1;
1083 }
1084
1085 static void
1086 typeinfo_test_parse(typeinfo *info,char *str)
1087 {
1088     int num;
1089     int i;
1090     typeinfo *infobuf;
1091     u1 *typebuf;
1092     int returntype;
1093     utf *desc = utf_new_char(str);
1094
1095     num = typeinfo_count_method_args(desc,false);
1096     if (num) {
1097         typebuf = DMNEW(u1,num);
1098         infobuf = DMNEW(typeinfo,num);
1099
1100         typeinfo_init_from_method_args(desc,typebuf,infobuf,num,false,
1101                                        &returntype,info);
1102
1103         TYPEINFO_ALLOCMERGED(info->merged,num);
1104         info->merged->count = num;
1105
1106         for (i=0; i<num; ++i) {
1107             if (typebuf[i] != TYPE_ADDRESS)
1108                 panic("non-reference type in mergedlist");
1109             info->merged->list[i] = infobuf[i].typeclass;
1110         }
1111         qsort(info->merged->list,num,sizeof(classinfo*),
1112               (int(*)(const void *,const void *))&typeinfo_test_compare);
1113     }
1114     else {
1115         typeinfo_init_from_method_args(desc,NULL,NULL,0,false,
1116                                        &returntype,info);
1117     }
1118 }
1119
1120 #define TYPEINFO_TEST_BUFLEN  4000
1121
1122 static bool
1123 typeinfo_equal(typeinfo *x,typeinfo *y)
1124 {
1125     int i;
1126
1127     if (x->typeclass != y->typeclass) return false;
1128     if (x->dimension != y->dimension) return false;
1129     if (x->dimension) {
1130         if (x->elementclass != y->elementclass) return false;
1131         if (x->elementtype != y->elementtype) return false;
1132     }
1133     if (x->merged || y->merged) {
1134         if (!(x->merged && y->merged)) return false;
1135         if (x->merged->count != y->merged->count) return false;
1136         for (i=0; i<x->merged->count; ++i)
1137             if (x->merged->list[i] != y->merged->list[i])
1138                 return false;
1139     }
1140     return true;
1141 }
1142
1143 static void
1144 typeinfo_testmerge(typeinfo *a,typeinfo *b,typeinfo *result,int *failed)
1145 {
1146     typeinfo dest;
1147
1148     TYPEINFO_CLONE(*a,dest);
1149
1150     printf("\n          ");
1151     typeinfo_print_short(stdout,&dest);
1152     printf("\n          ");
1153     typeinfo_print_short(stdout,b);
1154     printf("\n");
1155
1156     typeinfo_merge(&dest,b);
1157
1158     if (typeinfo_equal(&dest,result)) {
1159         printf("OK        ");
1160         typeinfo_print_short(stdout,&dest);
1161         printf("\n");
1162     }
1163     else {
1164         printf("RESULT    ");
1165         typeinfo_print_short(stdout,&dest);
1166         printf("\n");
1167         printf("SHOULD BE ");
1168         typeinfo_print_short(stdout,result);
1169         printf("\n");
1170         (*failed)++;
1171     }
1172 }
1173
1174 static void
1175 typeinfo_inc_dimension(typeinfo *info)
1176 {
1177     if (info->dimension++ == 0) {
1178         info->elementtype = ARRAYTYPE_OBJECT;
1179         info->elementclass = info->typeclass;
1180     }
1181     info->typeclass = class_array_of(info->typeclass);
1182 }
1183
1184 #define TYPEINFO_TEST_MAXDIM  10
1185
1186 static void
1187 typeinfo_testrun(char *filename)
1188 {
1189     char buf[TYPEINFO_TEST_BUFLEN];
1190     char bufa[TYPEINFO_TEST_BUFLEN];
1191     char bufb[TYPEINFO_TEST_BUFLEN];
1192     char bufc[TYPEINFO_TEST_BUFLEN];
1193     typeinfo a,b,c,a2,b2;
1194     int maxdim;
1195     int failed = 0;
1196     FILE *file = fopen(filename,"rt");
1197
1198     if (!file)
1199         panic("could not open typeinfo test file");
1200
1201     while (fgets(buf,TYPEINFO_TEST_BUFLEN,file)) {
1202         if (buf[0] == '#' || !strlen(buf))
1203             continue;
1204
1205         int res = sscanf(buf,"%s\t%s\t%s\n",bufa,bufb,bufc);
1206         if (res != 3 || !strlen(bufa) || !strlen(bufb) || !strlen(bufc))
1207             panic("Invalid line in typeinfo test file (none of empty, comment or test)");
1208
1209         typeinfo_test_parse(&a,bufa);
1210         typeinfo_test_parse(&b,bufb);
1211         typeinfo_test_parse(&c,bufc);
1212         do {
1213             typeinfo_testmerge(&a,&b,&c,&failed); /* check result */
1214             typeinfo_testmerge(&b,&a,&c,&failed); /* check commutativity */
1215
1216             if (TYPEINFO_IS_NULLTYPE(a)) break;
1217             if (TYPEINFO_IS_NULLTYPE(b)) break;
1218             if (TYPEINFO_IS_NULLTYPE(c)) break;
1219
1220             maxdim = a.dimension;
1221             if (b.dimension > maxdim) maxdim = b.dimension;
1222             if (c.dimension > maxdim) maxdim = c.dimension;
1223
1224             if (maxdim < TYPEINFO_TEST_MAXDIM) {
1225                 typeinfo_inc_dimension(&a);
1226                 typeinfo_inc_dimension(&b);
1227                 typeinfo_inc_dimension(&c);
1228             }
1229         } while (maxdim < TYPEINFO_TEST_MAXDIM);
1230     }
1231
1232     fclose(file);
1233
1234     if (failed) {
1235         fprintf(stderr,"Failed typeinfo_merge tests: %d\n",failed);
1236         panic("Failed test");
1237     }
1238 }
1239
1240 void
1241 typeinfo_test()
1242 {
1243 /*     typeinfo i1,i2,i3,i4,i5,i6,i7,i8; */
1244
1245 /*     typeinfo_init_from_fielddescriptor(&i1,"[Ljava/lang/Integer;"); */
1246 /*     typeinfo_init_from_fielddescriptor(&i2,"[[Ljava/lang/String;"); */
1247 /*     typeinfo_init_from_fielddescriptor(&i3,"[Ljava/lang/Cloneable;"); */
1248 /*     typeinfo_init_from_fielddescriptor(&i3,"[[Ljava/lang/String;"); */
1249 /*     TYPEINFO_INIT_NULLTYPE(i1); */
1250 /*     typeinfo_print_short(stdout,&i1); printf("\n"); */
1251 /*     typeinfo_print_short(stdout,&i2); printf("\n"); */
1252 /*     typeinfo_merge(&i1,&i2); */
1253 /*     typeinfo_print_short(stdout,&i1); printf("\n"); */
1254 /*     typeinfo_print_short(stdout,&i3); printf("\n"); */
1255 /*     typeinfo_merge(&i1,&i3); */
1256 /*     typeinfo_print_short(stdout,&i1); printf("\n"); */
1257
1258     log_text("Running typeinfo test file...");
1259     typeinfo_testrun("typeinfo.tst");
1260     log_text("Finished typeinfo test file.");
1261 }
1262
1263 void
1264 typeinfo_init_from_fielddescriptor(typeinfo *info,char *desc)
1265 {
1266     typeinfo_init_from_descriptor(info,desc,desc+strlen(desc));
1267 }
1268
1269 #define TYPEINFO_MAXINDENT  80
1270
1271 void
1272 typeinfo_print(FILE *file,typeinfo *info,int indent)
1273 {
1274     int i;
1275     char ind[TYPEINFO_MAXINDENT + 1];
1276
1277     if (indent > TYPEINFO_MAXINDENT) indent = TYPEINFO_MAXINDENT;
1278
1279     for (i=0; i<indent; ++i)
1280         ind[i] = ' ';
1281     ind[i] = (char) 0;
1282
1283     if (TYPEINFO_IS_PRIMITIVE(*info)) {
1284         fprintf(file,"%sprimitive\n",ind);
1285         return;
1286     }
1287
1288     if (TYPEINFO_IS_NULLTYPE(*info)) {
1289         fprintf(file,"%snull\n",ind);
1290         return;
1291     }
1292
1293     fprintf(file,"%sClass:      ",ind);
1294     utf_fprint(file,info->typeclass->name);
1295     fprintf(file,"\n");
1296
1297     if (TYPEINFO_IS_ARRAY(*info)) {
1298         fprintf(file,"%sDimension:    %d",ind,(int)info->dimension);
1299         fprintf(file,"\n%sElements:     ",ind);
1300         switch (info->elementtype) {
1301           case ARRAYTYPE_INT     : fprintf(file,"int\n"); break;
1302           case ARRAYTYPE_LONG    : fprintf(file,"long\n"); break;
1303           case ARRAYTYPE_FLOAT   : fprintf(file,"float\n"); break;
1304           case ARRAYTYPE_DOUBLE  : fprintf(file,"double\n"); break;
1305           case ARRAYTYPE_BYTE    : fprintf(file,"byte\n"); break;
1306           case ARRAYTYPE_CHAR    : fprintf(file,"char\n"); break;
1307           case ARRAYTYPE_SHORT   : fprintf(file,"short\n"); break;
1308           case ARRAYTYPE_BOOLEAN : fprintf(file,"boolean\n"); break;
1309
1310           case ARRAYTYPE_OBJECT:
1311               fprintf(file,"reference: ");
1312               utf_fprint(file,info->elementclass->name);
1313               fprintf(file,"\n");
1314               break;
1315
1316           default:
1317               fprintf(file,"INVALID ARRAYTYPE!\n");
1318         }
1319     }
1320
1321     if (info->merged) {
1322         fprintf(file,"%sMerged: ",ind);
1323         for (i=0; i<info->merged->count; ++i) {
1324             if (i) fprintf(file,", ");
1325             utf_fprint(file,info->merged->list[i]->name);
1326         }
1327         fprintf(file,"\n");
1328     }
1329 }
1330
1331 void
1332 typeinfo_print_short(FILE *file,typeinfo *info)
1333 {
1334     int i;
1335
1336     if (TYPEINFO_IS_PRIMITIVE(*info)) {
1337         fprintf(file,"primitive");
1338         return;
1339     }
1340
1341     if (TYPEINFO_IS_NULLTYPE(*info)) {
1342         fprintf(file,"null");
1343         return;
1344     }
1345
1346     utf_fprint(file,info->typeclass->name);
1347
1348     /* XXX remove */
1349 #if 0
1350     if (TYPEINFO_IS_ARRAY(*info)) {
1351         fprintf(file,"[%d]",info->dimension);
1352         switch (info->elementtype) {
1353             case ARRAYTYPE_INT     : fprintf(file,"int"); break;
1354             case ARRAYTYPE_LONG    : fprintf(file,"long"); break;
1355             case ARRAYTYPE_FLOAT   : fprintf(file,"float"); break;
1356             case ARRAYTYPE_DOUBLE  : fprintf(file,"double"); break;
1357             case ARRAYTYPE_BYTE    : fprintf(file,"byte"); break;
1358             case ARRAYTYPE_CHAR    : fprintf(file,"char"); break;
1359             case ARRAYTYPE_SHORT   : fprintf(file,"short"); break;
1360             case ARRAYTYPE_BOOLEAN : fprintf(file,"boolean"); break;
1361
1362             case ARRAYTYPE_OBJECT:
1363                 fprintf(file,"object(");
1364                 utf_fprint(file,info->elementclass->name);
1365                 fprintf(file,")");
1366                 break;
1367
1368             default:
1369                 fprintf(file,"INVALID ARRAYTYPE!");
1370         }
1371     }
1372 #endif
1373
1374     if (info->merged) {
1375         fprintf(file,"{");
1376         for (i=0; i<info->merged->count; ++i) {
1377             if (i) fprintf(file,",");
1378             utf_fprint(file,info->merged->list[i]->name);
1379         }
1380         fprintf(file,"}");
1381     }
1382 }
1383
1384 void
1385 typeinfo_print_type(FILE *file,int type,typeinfo *info)
1386 {
1387     switch (type) {
1388       case TYPE_VOID:   fprintf(file,"V"); break;
1389       case TYPE_INT:    fprintf(file,"I"); break;
1390       case TYPE_FLOAT:  fprintf(file,"F"); break;
1391       case TYPE_DOUBLE: fprintf(file,"D"); break;
1392       case TYPE_LONG:   fprintf(file,"J"); break;
1393       case TYPE_ADDRESS:
1394           if (TYPEINFO_IS_PRIMITIVE(*info))
1395               fprintf(file,"R"); /* returnAddress */
1396           else {
1397               fprintf(file,"L");
1398               typeinfo_print_short(file,info);
1399               fprintf(file,";");
1400           }
1401           break;
1402
1403       default:
1404           fprintf(file,"!");
1405     }
1406 }
1407
1408 #endif // DEBUG_TYPES