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