src/vm/jit/verify/typeinfo.c

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