src/vm/jit/verify/typeinfo.c

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