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 696 2003-12-06 20:10:05Z 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     /* the null type can be assigned to any type */
 164     if (TYPEINFO_IS_NULLTYPE(*value))
 165         return true;
 166
 167     /* primitive and reference types are not assignment compatible. */
 168     if (!cls || !dest->typeclass)
 169         return false;
 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 /* XXX could be made a macro if really performance critical */
 474 void
 475 typeinfo_init_component(typeinfo *srcarray,typeinfo *dst)
 476 {
 477     vftbl *comp = NULL;
 478
 479     if (TYPEINFO_IS_NULLTYPE(*srcarray)) {
 480         TYPEINFO_INIT_NULLTYPE(*dst);
 481         return;
 482     }
 483
 484     /* XXX find component class */
 485     if (!TYPEINFO_IS_ARRAY(*srcarray))
 486         panic("Trying to access component of non-array");
 487
 488     comp = srcarray->typeclass->vftbl->arraydesc->componentvftbl;
 489     if (comp) {
 490         TYPEINFO_INIT_CLASSINFO(*dst,comp->class);
 491     }
 492     else {
 493         TYPEINFO_INIT_PRIMITIVE(*dst);
 494     }
 495
 496     /* XXX assign directly ? */
 497 #if 0
 498     if ((dst->dimension = srcarray->dimension - 1) == 0) {
 499         dst->typeclass = srcarray->elementclass;
 500         dst->elementtype = 0;
 501         dst->elementclass = NULL;
 502     }
 503     else {
 504         dst->typeclass = srcarray->typeclass;
 505         dst->elementtype = srcarray->elementtype;
 506         dst->elementclass = srcarray->elementclass;
 507     }
 508 #endif
 509
 510     dst->merged = srcarray->merged;
 511 }
 512
 513 /* Condition: src != dest. */
 514 void
 515 typeinfo_clone(typeinfo *src,typeinfo *dest)
 516 {
 517     int count;
 518     classinfo **srclist,**destlist;
 519
 520 #ifdef TYPEINFO_DEBUG
 521     if (src == dest)
 522         panic("Internal error: typeinfo_clone with src==dest");
 523 #endif
 524
 525     *dest = *src;
 526
 527     if (src->merged) {
 528         count = src->merged->count;
 529         TYPEINFO_ALLOCMERGED(dest->merged,count);
 530         dest->merged->count = count;
 531
 532         /* XXX use memcpy? */
 533         srclist = src->merged->list;
 534         destlist = dest->merged->list;
 535         while (count--)
 536             *destlist++ = *srclist++;
 537     }
 538 }
 539
 540 /**********************************************************************/
 541 /* MISCELLANEOUS FUNCTIONS                                            */
 542 /**********************************************************************/
 543
 544 void
 545 typeinfo_free(typeinfo *info)
 546 {
 547     TYPEINFO_FREE(*info);
 548 }
 549
 550 /**********************************************************************/
 551 /* MERGING FUNCTIONS                                                  */
 552 /* The following functions are used to merge the types represented by */
 553 /* two typeinfo structures into one typeinfo structure.               */
 554 /**********************************************************************/
 555
 556 static
 557 void
 558 typeinfo_merge_error(char *str,typeinfo *x,typeinfo *y) {
 559 #ifdef TYPEINFO_DEBUG
 560     fprintf(stderr,"Error in typeinfo_merge: %s\n",str);
 561     fprintf(stderr,"Typeinfo x:\n");
 562     typeinfo_print(stderr,x,1);
 563     fprintf(stderr,"Typeinfo y:\n");
 564     typeinfo_print(stderr,y,1);
 565 #endif
 566     panic(str);
 567 }
 568
 569 /* Condition: clsx != clsy. */
 570 /* Returns: true if dest was changed (always true). */
 571 static
 572 bool
 573 typeinfo_merge_two(typeinfo *dest,classinfo *clsx,classinfo *clsy)
 574 {
 575     TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
 576     TYPEINFO_ALLOCMERGED(dest->merged,2);
 577     dest->merged->count = 2;
 578
 579 #ifdef TYPEINFO_DEBUG
 580     if (clsx == clsy)
 581         panic("Internal error: typeinfo_merge_two called with clsx==clsy.");
 582 #endif
 583
 584     if (clsx < clsy) {
 585         dest->merged->list[0] = clsx;
 586         dest->merged->list[1] = clsy;
 587     }
 588     else {
 589         dest->merged->list[0] = clsy;
 590         dest->merged->list[1] = clsx;
 591     }
 592
 593     return true;
 594 }
 595
 596 /* Returns: true if dest was changed. */
 597 static
 598 bool
 599 typeinfo_merge_add(typeinfo *dest,typeinfo_mergedlist *m,classinfo *cls)
 600 {
 601     int count;
 602     typeinfo_mergedlist *newmerged;
 603     classinfo **mlist,**newlist;
 604
 605     count = m->count;
 606     mlist = m->list;
 607
 608     /* Check if cls is already in the mergedlist m. */
 609     while (count--) {
 610         if (*mlist++ == cls) {
 611             /* cls is in the list, so m is the resulting mergedlist */
 612             if (dest->merged == m)
 613                 return false;
 614
 615             /* We have to copy the mergedlist */
 616             TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
 617             count = m->count;
 618             TYPEINFO_ALLOCMERGED(dest->merged,count);
 619             dest->merged->count = count;
 620             newlist = dest->merged->list;
 621             mlist = m->list;
 622             while (count--) {
 623                 *newlist++ = *mlist++;
 624             }
 625             return true;
 626         }
 627     }
 628
 629     /* Add cls to the mergedlist. */
 630     count = m->count;
 631     TYPEINFO_ALLOCMERGED(newmerged,count+1);
 632     newmerged->count = count+1;
 633     newlist = newmerged->list;
 634     mlist = m->list;
 635     while (count) {
 636         if (*mlist > cls)
 637             break;
 638         *newlist++ = *mlist++;
 639         count--;
 640     }
 641     *newlist++ = cls;
 642     while (count--) {
 643         *newlist++ = *mlist++;
 644     }
 645
 646     /* Put the new mergedlist into dest. */
 647     TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
 648     dest->merged = newmerged;
 649
 650     return true;
 651 }
 652
 653 /* Returns: true if dest was changed. */
 654 static
 655 bool
 656 typeinfo_merge_mergedlists(typeinfo *dest,typeinfo_mergedlist *x,
 657                            typeinfo_mergedlist *y)
 658 {
 659     int count = 0;
 660     int countx,county;
 661     typeinfo_mergedlist *temp,*result;
 662     classinfo **clsx,**clsy,**newlist;
 663
 664     /* count the elements that will be in the resulting list */
 665     /* (Both lists are sorted, equal elements are counted only once.) */
 666     clsx = x->list;
 667     clsy = y->list;
 668     countx = x->count;
 669     county = y->count;
 670     while (countx && county) {
 671         if (*clsx == *clsy) {
 672             clsx++;
 673             clsy++;
 674             countx--;
 675             county--;
 676         }
 677         else if (*clsx < *clsy) {
 678             clsx++;
 679             countx--;
 680         }
 681         else {
 682             clsy++;
 683             county--;
 684         }
 685         count++;
 686     }
 687     count += countx + county;
 688
 689     /* {The new mergedlist will have count entries.} */
 690
 691     if ((x->count != count) && (y->count == count)) {
 692         temp = x; x = y; y = temp;
 693     }
 694     /* {If one of x,y is already the result it is x.} */
 695     if (x->count == count) {
 696         /* x->merged is equal to the result */
 697         if (x == dest->merged)
 698             return false;
 699
 700         if (!dest->merged || dest->merged->count != count) {
 701             TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
 702             TYPEINFO_ALLOCMERGED(dest->merged,count);
 703             dest->merged->count = count;
 704         }
 705
 706         newlist = dest->merged->list;
 707         clsx = x->list;
 708         while (count--) {
 709             *newlist++ = *clsx++;
 710         }
 711         return true;
 712     }
 713
 714     /* {We have to merge two lists.} */
 715
 716     /* allocate the result list */
 717     TYPEINFO_ALLOCMERGED(result,count);
 718     result->count = count;
 719     newlist = result->list;
 720
 721     /* merge the sorted lists */
 722     clsx = x->list;
 723     clsy = y->list;
 724     countx = x->count;
 725     county = y->count;
 726     while (countx && county) {
 727         if (*clsx == *clsy) {
 728             *newlist++ = *clsx++;
 729             clsy++;
 730             countx--;
 731             county--;
 732         }
 733         else if (*clsx < *clsy) {
 734             *newlist++ = *clsx++;
 735             countx--;
 736         }
 737         else {
 738             *newlist++ = *clsy++;
 739             county--;
 740         }
 741     }
 742     while (countx--)
 743             *newlist++ = *clsx++;
 744     while (county--)
 745             *newlist++ = *clsy++;
 746
 747     /* replace the list in dest with the result list */
 748     TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
 749     dest->merged = result;
 750
 751     return true;
 752 }
 753
 754 static
 755 bool
 756 typeinfo_merge_nonarrays(typeinfo *dest,
 757                          classinfo **result,
 758                          classinfo *clsx,classinfo *clsy,
 759                          typeinfo_mergedlist *mergedx,
 760                          typeinfo_mergedlist *mergedy)
 761 {
 762     classinfo *tcls,*common;
 763     typeinfo_mergedlist *tmerged;
 764     bool changed;
 765
 766     /* XXX remove */
 767     /*
 768 #ifdef TYPEINFO_DEBUG
 769     typeinfo dbgx,dbgy;
 770     printf("typeinfo_merge_nonarrays:\n");
 771     TYPEINFO_INIT_CLASSINFO(dbgx,clsx);
 772     dbgx.merged = mergedx;
 773     TYPEINFO_INIT_CLASSINFO(dbgy,clsy);
 774     dbgy.merged = mergedy;
 775     typeinfo_print(stdout,&dbgx,4);
 776     printf("  with:\n");
 777     typeinfo_print(stdout,&dbgy,4);
 778 #endif
 779     */
 780
 781     /* Common case: clsx == clsy */
 782     /* (This case is very simple unless *both* x and y really represent
 783      *  merges of subclasses of clsx==clsy.)
 784      */
 785     /* XXX count this case for statistics */
 786     if ((clsx == clsy) && (!mergedx || !mergedy)) {
 787   return_simple_x:
 788         /* XXX remove */ /* log_text("return simple x"); */
 789         changed = (dest->merged != NULL);
 790         TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
 791         dest->merged = NULL;
 792         *result = clsx;
 793         /* XXX remove */ /* log_text("returning"); */
 794         return changed;
 795     }
 796
 797     /* If clsy is an interface, swap x and y. */
 798     if (clsy->flags & ACC_INTERFACE) {
 799         tcls = clsx; clsx = clsy; clsy = tcls;
 800         tmerged = mergedx; mergedx = mergedy; mergedy = tmerged;
 801     }
 802     /* {We know: If only one of x,y is an interface it is x.} */
 803
 804     /* Handle merging of interfaces: */
 805     if (clsx->flags & ACC_INTERFACE) {
 806         /* {clsx is an interface and mergedx == NULL.} */
 807
 808         if (clsy->flags & ACC_INTERFACE) {
 809             /* We are merging two interfaces. */
 810             /* {mergedy == NULL} */
 811             /* XXX: should we optimize direct superinterfaces? */
 812
 813             /* {We know that clsx!=clsy (see common case at beginning.)} */
 814             *result = class_java_lang_Object;
 815             return typeinfo_merge_two(dest,clsx,clsy);
 816         }
 817
 818         /* {We know: x is an interface, clsy is a class.} */
 819
 820         /* Check if we are merging an interface with java.lang.Object */
 821         if (clsy == class_java_lang_Object && !mergedy) {
 822             clsx = clsy;
 823             goto return_simple_x;
 824         }
 825
 826
 827         /* If the type y implements clsx then the result of the merge
 828          * is clsx regardless of mergedy.
 829          */
 830
 831         if (CLASS_IMPLEMENTS_INTERFACE(clsy,clsx->index)
 832             || mergedlist_implements_interface(mergedy,clsx))
 833         {
 834             /* y implements x, so the result of the merge is x. */
 835             goto return_simple_x;
 836         }
 837
 838         /* {We know: x is an interface, the type y a class or a merge
 839          * of subclasses and does not implement x.} */
 840
 841         /* There may still be superinterfaces of x which are implemented
 842          * by y, too, so we have to add clsx to the mergedlist.
 843          */
 844
 845         /* XXX if x has no superinterfaces we could return a simple java.lang.Object */
 846
 847         common = class_java_lang_Object;
 848         goto merge_with_simple_x;
 849     }
 850
 851     /* {We know: x and y are classes (not interfaces).} */
 852
 853     /* If *x is deeper in the inheritance hierarchy swap x and y. */
 854     if (clsx->index > clsy->index) {
 855         tcls = clsx; clsx = clsy; clsy = tcls;
 856         tmerged = mergedx; mergedx = mergedy; mergedy = tmerged;
 857     }
 858
 859     /* {We know: y is at least as deep in the hierarchy as x.} */
 860
 861     /* Find nearest common anchestor for the classes. */
 862     common = clsx;
 863     tcls = clsy;
 864     while (tcls->index > common->index)
 865         tcls = tcls->super;
 866     while (common != tcls) {
 867         common = common->super;
 868         tcls = tcls->super;
 869     }
 870
 871     /* {common == nearest common anchestor of clsx and clsy.} */
 872
 873     /* If clsx==common and x is a whole class (not a merge of subclasses)
 874      * then the result of the merge is clsx.
 875      */
 876     if (clsx == common && !mergedx) {
 877         goto return_simple_x;
 878     }
 879
 880     if (mergedx) {
 881         *result = common;
 882         if (mergedy)
 883             return typeinfo_merge_mergedlists(dest,mergedx,mergedy);
 884         else
 885             return typeinfo_merge_add(dest,mergedx,clsy);
 886     }
 887
 888  merge_with_simple_x:
 889     *result = common;
 890     if (mergedy)
 891         return typeinfo_merge_add(dest,mergedy,clsx);
 892     else
 893         return typeinfo_merge_two(dest,clsx,clsy);
 894 }
 895
 896 /* Condition: *dest must be a valid initialized typeinfo. */
 897 /* Condition: dest != y. */
 898 /* Returns: true if dest was changed. */
 899 bool
 900 typeinfo_merge(typeinfo *dest,typeinfo* y)
 901 {
 902     typeinfo *x;
 903     typeinfo *tmp;                      /* used for swapping */
 904     classinfo *common;
 905     classinfo *elementclass;
 906     int dimension;
 907     int elementtype;
 908     bool changed;
 909
 910     /* XXX remove */
 911     /*
 912 #ifdef TYPEINFO_DEBUG
 913     typeinfo_print(stdout,dest,4);
 914     typeinfo_print(stdout,y,4);
 915 #endif
 916     */
 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     if (dest == y)
 928         panic("Internal error: typeinfo_merge with dest==y");
 929
 930     /* check that no unlinked classes are merged. */
 931     if (!dest->typeclass->linked || !y->typeclass->linked)
 932         typeinfo_merge_error("Trying to merge unlinked class(es).",dest,y);
 933 #endif
 934
 935     /* XXX remove */ /* log_text("Testing common case"); */
 936
 937     /* Common case: class dest == class y */
 938     /* (This case is very simple unless *both* dest and y really represent
 939      *  merges of subclasses of class dest==class y.)
 940      */
 941     /* XXX count this case for statistics */
 942     if ((dest->typeclass == y->typeclass) && (!dest->merged || !y->merged)) {
 943         changed = (dest->merged != NULL);
 944         TYPEINFO_FREEMERGED_IF_ANY(dest->merged); /* XXX unify if */
 945         dest->merged = NULL;
 946         /* XXX remove */ /* log_text("common case handled"); */
 947         return changed;
 948     }
 949
 950     /* XXX remove */ /* log_text("Handling null types"); */
 951
 952     /* Handle null types: */
 953     if (TYPEINFO_IS_NULLTYPE(*y)) {
 954         return false;
 955     }
 956     if (TYPEINFO_IS_NULLTYPE(*dest)) {
 957         TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
 958         TYPEINFO_CLONE(*y,*dest);
 959         return true;
 960     }
 961
 962     /* This function uses x internally, so x and y can be swapped
 963      * without changing dest. */
 964     x = dest;
 965     changed = false;
 966
 967     /* Handle merging of arrays: */
 968     if (TYPEINFO_IS_ARRAY(*x) && TYPEINFO_IS_ARRAY(*y)) {
 969
 970         /* XXX remove */ /* log_text("Handling arrays"); */
 971
 972         /* Make x the one with lesser dimension */
 973         if (x->dimension > y->dimension) {
 974             tmp = x; x = y; y = tmp;
 975         }
 976
 977         /* If one array (y) has higher dimension than the other,
 978          * interpret it as an array (same dim. as x) of Arraystubs. */
 979         if (x->dimension < y->dimension) {
 980             dimension = x->dimension;
 981             elementtype = ARRAYTYPE_OBJECT;
 982             elementclass = pseudo_class_Arraystub;
 983         }
 984         else {
 985             dimension = y->dimension;
 986             elementtype = y->elementtype;
 987             elementclass = y->elementclass;
 988         }
 989
 990         /* {The arrays are of the same dimension.} */
 991
 992         if (x->elementtype != elementtype) {
 993             /* Different element types are merged, so the resulting array
 994              * type has one accessible dimension less. */
 995             if (--dimension == 0) {
 996                 common = pseudo_class_Arraystub;
 997                 elementtype = 0;
 998                 elementclass = NULL;
 999             }
1000             else {
1001                 common = class_multiarray_of(dimension,pseudo_class_Arraystub);
1002                 elementtype = ARRAYTYPE_OBJECT;
1003                 elementclass = pseudo_class_Arraystub;
1004             }
1005         }
1006         else {
1007             /* {The arrays have the same dimension and elementtype.} */
1008
1009             if (elementtype == ARRAYTYPE_OBJECT) {
1010                 /* The elements are references, so their respective
1011                  * types must be merged.
1012                  */
1013                 changed |= typeinfo_merge_nonarrays(dest,
1014                                                     &elementclass,
1015                                                     x->elementclass,
1016                                                     elementclass,
1017                                                     x->merged,y->merged);
1018
1019                 /* XXX otimize this? */
1020                 /* XXX remove */ /* log_text("finding resulting array class: "); */
1021                 common = class_multiarray_of(dimension,elementclass);
1022                 /* XXX remove */ /* utf_display(common->name); printf("\n"); */
1023             }
1024         }
1025     }
1026     else {
1027         /* {We know that at least one of x or y is no array, so the
1028          *  result cannot be an array.} */
1029
1030         changed |= typeinfo_merge_nonarrays(dest,
1031                                             &common,
1032                                             x->typeclass,y->typeclass,
1033                                             x->merged,y->merged);
1034
1035         dimension = 0;
1036         elementtype = 0;
1037         elementclass = NULL;
1038     }
1039
1040     /* Put the new values into dest if neccessary. */
1041
1042     if (dest->typeclass != common) {
1043         dest->typeclass = common;
1044         changed = true;
1045     }
1046     if (dest->dimension != dimension) {
1047         dest->dimension = dimension;
1048         changed = true;
1049     }
1050     if (dest->elementtype != elementtype) {
1051         dest->elementtype = elementtype;
1052         changed = true;
1053     }
1054     if (dest->elementclass != elementclass) {
1055         dest->elementclass = elementclass;
1056         changed = true;
1057     }
1058
1059     /* XXX remove */ /* log_text("returning from merge"); */
1060
1061     return changed;
1062 }
1063
1064
1065 /**********************************************************************/
1066 /* DEBUGGING HELPERS                                                  */
1067 /**********************************************************************/
1068
1069 #ifdef TYPEINFO_DEBUG
1070
1071 #include "tables.h"
1072 #include "loader.h"
1073
1074 static int
1075 typeinfo_test_compare(classinfo **a,classinfo **b)
1076 {
1077     if (*a == *b) return 0;
1078     if (*a < *b) return -1;
1079     return +1;
1080 }
1081
1082 static void
1083 typeinfo_test_parse(typeinfo *info,char *str)
1084 {
1085     int num;
1086     int i;
1087     typeinfo *infobuf;
1088     u1 *typebuf;
1089     int returntype;
1090     utf *desc = utf_new_char(str);
1091
1092     num = typeinfo_count_method_args(desc,false);
1093     if (num) {
1094         typebuf = DMNEW(u1,num);
1095         infobuf = DMNEW(typeinfo,num);
1096
1097         typeinfo_init_from_method_args(desc,typebuf,infobuf,num,false,
1098                                        &returntype,info);
1099
1100         TYPEINFO_ALLOCMERGED(info->merged,num);
1101         info->merged->count = num;
1102
1103         for (i=0; i<num; ++i) {
1104             if (typebuf[i] != TYPE_ADDRESS)
1105                 panic("non-reference type in mergedlist");
1106             info->merged->list[i] = infobuf[i].typeclass;
1107         }
1108         qsort(info->merged->list,num,sizeof(classinfo*),
1109               (int(*)(const void *,const void *))&typeinfo_test_compare);
1110     }
1111     else {
1112         typeinfo_init_from_method_args(desc,NULL,NULL,0,false,
1113                                        &returntype,info);
1114     }
1115 }
1116
1117 #define TYPEINFO_TEST_BUFLEN  4000
1118
1119 static bool
1120 typeinfo_equal(typeinfo *x,typeinfo *y)
1121 {
1122     int i;
1123
1124     if (x->typeclass != y->typeclass) return false;
1125     if (x->dimension != y->dimension) return false;
1126     if (x->dimension) {
1127         if (x->elementclass != y->elementclass) return false;
1128         if (x->elementtype != y->elementtype) return false;
1129     }
1130     if (x->merged || y->merged) {
1131         if (!(x->merged && y->merged)) return false;
1132         if (x->merged->count != y->merged->count) return false;
1133         for (i=0; i<x->merged->count; ++i)
1134             if (x->merged->list[i] != y->merged->list[i])
1135                 return false;
1136     }
1137     return true;
1138 }
1139
1140 static void
1141 typeinfo_testmerge(typeinfo *a,typeinfo *b,typeinfo *result,int *failed)
1142 {
1143     typeinfo dest;
1144     bool changed,changed_should_be;
1145
1146     TYPEINFO_CLONE(*a,dest);
1147
1148     printf("\n          ");
1149     typeinfo_print_short(stdout,&dest);
1150     printf("\n          ");
1151     typeinfo_print_short(stdout,b);
1152     printf("\n");
1153
1154     changed = (typeinfo_merge(&dest,b)) ? 1 : 0;
1155     changed_should_be = (!typeinfo_equal(&dest,a)) ? 1 : 0;
1156
1157     printf("          %s\n",(changed) ? "changed" : "=");
1158
1159     if (typeinfo_equal(&dest,result)) {
1160         printf("OK        ");
1161         typeinfo_print_short(stdout,&dest);
1162         printf("\n");
1163         if (changed != changed_should_be) {
1164             printf("WRONG RETURN VALUE!\n");
1165             (*failed)++;
1166         }
1167     }
1168     else {
1169         printf("RESULT    ");
1170         typeinfo_print_short(stdout,&dest);
1171         printf("\n");
1172         printf("SHOULD BE ");
1173         typeinfo_print_short(stdout,result);
1174         printf("\n");
1175         (*failed)++;
1176     }
1177 }
1178
1179 static void
1180 typeinfo_inc_dimension(typeinfo *info)
1181 {
1182     if (info->dimension++ == 0) {
1183         info->elementtype = ARRAYTYPE_OBJECT;
1184         info->elementclass = info->typeclass;
1185     }
1186     info->typeclass = class_array_of(info->typeclass);
1187 }
1188
1189 #define TYPEINFO_TEST_MAXDIM  10
1190
1191 static void
1192 typeinfo_testrun(char *filename)
1193 {
1194     char buf[TYPEINFO_TEST_BUFLEN];
1195     char bufa[TYPEINFO_TEST_BUFLEN];
1196     char bufb[TYPEINFO_TEST_BUFLEN];
1197     char bufc[TYPEINFO_TEST_BUFLEN];
1198     typeinfo a,b,c;
1199     int maxdim;
1200     int failed = 0;
1201     FILE *file = fopen(filename,"rt");
1202
1203     if (!file)
1204         panic("could not open typeinfo test file");
1205
1206     while (fgets(buf,TYPEINFO_TEST_BUFLEN,file)) {
1207         if (buf[0] == '#' || !strlen(buf))
1208             continue;
1209
1210         int res = sscanf(buf,"%s\t%s\t%s\n",bufa,bufb,bufc);
1211         if (res != 3 || !strlen(bufa) || !strlen(bufb) || !strlen(bufc))
1212             panic("Invalid line in typeinfo test file (none of empty, comment or test)");
1213
1214         typeinfo_test_parse(&a,bufa);
1215         typeinfo_test_parse(&b,bufb);
1216         typeinfo_test_parse(&c,bufc);
1217         do {
1218             typeinfo_testmerge(&a,&b,&c,&failed); /* check result */
1219             typeinfo_testmerge(&b,&a,&c,&failed); /* check commutativity */
1220
1221             if (TYPEINFO_IS_NULLTYPE(a)) break;
1222             if (TYPEINFO_IS_NULLTYPE(b)) break;
1223             if (TYPEINFO_IS_NULLTYPE(c)) break;
1224
1225             maxdim = a.dimension;
1226             if (b.dimension > maxdim) maxdim = b.dimension;
1227             if (c.dimension > maxdim) maxdim = c.dimension;
1228
1229             if (maxdim < TYPEINFO_TEST_MAXDIM) {
1230                 typeinfo_inc_dimension(&a);
1231                 typeinfo_inc_dimension(&b);
1232                 typeinfo_inc_dimension(&c);
1233             }
1234         } while (maxdim < TYPEINFO_TEST_MAXDIM);
1235     }
1236
1237     fclose(file);
1238
1239     if (failed) {
1240         fprintf(stderr,"Failed typeinfo_merge tests: %d\n",failed);
1241         panic("Failed test");
1242     }
1243 }
1244
1245 void
1246 typeinfo_test()
1247 {
1248 /*     typeinfo i1,i2,i3,i4,i5,i6,i7,i8; */
1249
1250 /*     typeinfo_init_from_fielddescriptor(&i1,"[Ljava/lang/Integer;"); */
1251 /*     typeinfo_init_from_fielddescriptor(&i2,"[[Ljava/lang/String;"); */
1252 /*     typeinfo_init_from_fielddescriptor(&i3,"[Ljava/lang/Cloneable;"); */
1253 /*     typeinfo_init_from_fielddescriptor(&i3,"[[Ljava/lang/String;"); */
1254 /*     TYPEINFO_INIT_NULLTYPE(i1); */
1255 /*     typeinfo_print_short(stdout,&i1); printf("\n"); */
1256 /*     typeinfo_print_short(stdout,&i2); printf("\n"); */
1257 /*     typeinfo_merge(&i1,&i2); */
1258 /*     typeinfo_print_short(stdout,&i1); printf("\n"); */
1259 /*     typeinfo_print_short(stdout,&i3); printf("\n"); */
1260 /*     typeinfo_merge(&i1,&i3); */
1261 /*     typeinfo_print_short(stdout,&i1); printf("\n"); */
1262
1263     log_text("Running typeinfo test file...");
1264     typeinfo_testrun("typeinfo.tst");
1265     log_text("Finished typeinfo test file.");
1266 }
1267
1268 void
1269 typeinfo_init_from_fielddescriptor(typeinfo *info,char *desc)
1270 {
1271     typeinfo_init_from_descriptor(info,desc,desc+strlen(desc));
1272 }
1273
1274 #define TYPEINFO_MAXINDENT  80
1275
1276 void
1277 typeinfo_print(FILE *file,typeinfo *info,int indent)
1278 {
1279     int i;
1280     char ind[TYPEINFO_MAXINDENT + 1];
1281
1282     if (indent > TYPEINFO_MAXINDENT) indent = TYPEINFO_MAXINDENT;
1283
1284     for (i=0; i<indent; ++i)
1285         ind[i] = ' ';
1286     ind[i] = (char) 0;
1287
1288     if (TYPEINFO_IS_PRIMITIVE(*info)) {
1289         fprintf(file,"%sprimitive\n",ind);
1290         return;
1291     }
1292
1293     if (TYPEINFO_IS_NULLTYPE(*info)) {
1294         fprintf(file,"%snull\n",ind);
1295         return;
1296     }
1297
1298     fprintf(file,"%sClass:      ",ind);
1299     utf_fprint(file,info->typeclass->name);
1300     fprintf(file,"\n");
1301
1302     if (TYPEINFO_IS_ARRAY(*info)) {
1303         fprintf(file,"%sDimension:    %d",ind,(int)info->dimension);
1304         fprintf(file,"\n%sElements:     ",ind);
1305         switch (info->elementtype) {
1306           case ARRAYTYPE_INT     : fprintf(file,"int\n"); break;
1307           case ARRAYTYPE_LONG    : fprintf(file,"long\n"); break;
1308           case ARRAYTYPE_FLOAT   : fprintf(file,"float\n"); break;
1309           case ARRAYTYPE_DOUBLE  : fprintf(file,"double\n"); break;
1310           case ARRAYTYPE_BYTE    : fprintf(file,"byte\n"); break;
1311           case ARRAYTYPE_CHAR    : fprintf(file,"char\n"); break;
1312           case ARRAYTYPE_SHORT   : fprintf(file,"short\n"); break;
1313           case ARRAYTYPE_BOOLEAN : fprintf(file,"boolean\n"); break;
1314
1315           case ARRAYTYPE_OBJECT:
1316               fprintf(file,"reference: ");
1317               utf_fprint(file,info->elementclass->name);
1318               fprintf(file,"\n");
1319               break;
1320
1321           default:
1322               fprintf(file,"INVALID ARRAYTYPE!\n");
1323         }
1324     }
1325
1326     if (info->merged) {
1327         fprintf(file,"%sMerged: ",ind);
1328         for (i=0; i<info->merged->count; ++i) {
1329             if (i) fprintf(file,", ");
1330             utf_fprint(file,info->merged->list[i]->name);
1331         }
1332         fprintf(file,"\n");
1333     }
1334 }
1335
1336 void
1337 typeinfo_print_short(FILE *file,typeinfo *info)
1338 {
1339     int i;
1340
1341     if (TYPEINFO_IS_PRIMITIVE(*info)) {
1342         fprintf(file,"primitive");
1343         return;
1344     }
1345
1346     if (TYPEINFO_IS_NULLTYPE(*info)) {
1347         fprintf(file,"null");
1348         return;
1349     }
1350
1351     utf_fprint(file,info->typeclass->name);
1352
1353     if (info->merged) {
1354         fprintf(file,"{");
1355         for (i=0; i<info->merged->count; ++i) {
1356             if (i) fprintf(file,",");
1357             utf_fprint(file,info->merged->list[i]->name);
1358         }
1359         fprintf(file,"}");
1360     }
1361 }
1362
1363 void
1364 typeinfo_print_type(FILE *file,int type,typeinfo *info)
1365 {
1366     switch (type) {
1367       case TYPE_VOID:   fprintf(file,"V"); break;
1368       case TYPE_INT:    fprintf(file,"I"); break;
1369       case TYPE_FLOAT:  fprintf(file,"F"); break;
1370       case TYPE_DOUBLE: fprintf(file,"D"); break;
1371       case TYPE_LONG:   fprintf(file,"J"); break;
1372       case TYPE_ADDRESS:
1373           if (TYPEINFO_IS_PRIMITIVE(*info))
1374               fprintf(file,"R"); /* returnAddress */
1375           else {
1376               typeinfo_print_short(file,info);
1377           }
1378           break;
1379
1380       default:
1381           fprintf(file,"!");
1382     }
1383 }
1384
1385 #endif // TYPEINFO_DEBUG