src/vm/jit/verify/typeinfo.c

   1 /* src/vm/jit/verify/typeinfo.c - type system used by the type checker
   2
   3    Copyright (C) 1996-2005, 2006, 2007 R. Grafl, A. Krall, C. Kruegel,
   4    C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
   5    E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
   6    J. Wenninger, Institut f. Computersprachen - TU Wien
   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., 51 Franklin Street, Fifth Floor, Boston, MA
  23    02110-1301, USA.
  24
  25    $Id: typeinfo.c 7246 2007-01-29 18:49:05Z twisti $
  26
  27 */
  28
  29
  30 #include "config.h"
  31
  32 #include <assert.h>
  33 #include <string.h>
  34
  35 #include "mm/memory.h"
  36 #include "toolbox/logging.h"
  37
  38 #include "vm/exceptions.h"
  39
  40 #include "vm/jit/jit.h"
  41 #include "vm/jit/verify/typeinfo.h"
  42
  43 #include "vmcore/class.h"
  44 #include "vmcore/descriptor.h"
  45 #include "vmcore/loader.h"
  46 #include "vmcore/resolve.h"
  47
  48
  49 /* check if a linked class is an array class. Only use for linked classes! */
  50 #define CLASSINFO_IS_ARRAY(clsinfo)  ((clsinfo)->vftbl->arraydesc != NULL)
  51
  52 /* check if a linked class implements the interface with the given index */
  53 #define CLASSINFO_IMPLEMENTS_INTERFACE(cls,index)                   \
  54     ( ((index) < (cls)->vftbl->interfacetablelength)            \
  55       && ( (cls)->vftbl->interfacetable[-(index)] != NULL ) )
  56
  57 /******************************************************************************/
  58 /* DEBUG HELPERS                                                              */
  59 /******************************************************************************/
  60
  61 #ifdef TYPEINFO_DEBUG
  62 #define TYPEINFO_ASSERT(cond)  assert(cond)
  63 #else
  64 #define TYPEINFO_ASSERT(cond)
  65 #endif
  66
  67 /**********************************************************************/
  68 /* TYPEVECTOR FUNCTIONS                                               */
  69 /**********************************************************************/
  70
  71 #if defined(ENABLE_VERIFIER)
  72
  73 /* typevector_copy *************************************************************
  74
  75    Return a copy of the given typevector.
  76
  77    IN:
  78            src..............typevector set to copy, must be != NULL
  79            size.............number of elements per typevector
  80
  81    RETURN VALUE:
  82        a pointer to the new typevector set
  83
  84 *******************************************************************************/
  85
  86 varinfo *
  87 typevector_copy(varinfo *src, int size)
  88 {
  89         varinfo *dst;
  90
  91         TYPEINFO_ASSERT(src);
  92
  93         dst = DNEW_TYPEVECTOR(size);
  94         memcpy(dst,src,TYPEVECTOR_SIZE(size));
  95
  96         return dst;
  97 }
  98
  99 /* typevector_copy_inplace *****************************************************
 100
 101    Copy a typevector to a given destination.
 102
 103    IN:
 104            src..............typevector to copy, must be != NULL
 105            dst..............destination to write the copy to
 106            size.............number of elements per typevector
 107
 108 *******************************************************************************/
 109
 110 void
 111 typevector_copy_inplace(varinfo *src,varinfo *dst,int size)
 112 {
 113         memcpy(dst,src,TYPEVECTOR_SIZE(size));
 114 }
 115
 116 /* typevector_checktype ********************************************************
 117
 118    Check if the typevector contains a given type at a given index.
 119
 120    IN:
 121            vec..............typevector set, must be != NULL
 122            index............index of component to check
 123            type.............TYPE_* constant to check against
 124
 125    RETURN VALUE:
 126        true if the typevector contains TYPE at INDEX,
 127            false otherwise
 128
 129 *******************************************************************************/
 130
 131 bool
 132 typevector_checktype(varinfo *vec,int index,int type)
 133 {
 134         TYPEINFO_ASSERT(vec);
 135
 136         return vec[index].type == type;
 137 }
 138
 139 /* typevector_checkreference ***************************************************
 140
 141    Check if the typevector contains a reference at a given index.
 142
 143    IN:
 144            vec..............typevector, must be != NULL
 145            index............index of component to check
 146
 147    RETURN VALUE:
 148        true if the typevector contains a reference at INDEX,
 149            false otherwise
 150
 151 *******************************************************************************/
 152
 153 bool
 154 typevector_checkreference(varinfo *vec, int index)
 155 {
 156         TYPEINFO_ASSERT(vec);
 157         return TYPEDESC_IS_REFERENCE(vec[index]);
 158 }
 159
 160 /* typevectorset_checkretaddr **************************************************
 161
 162    Check if the typevectors contains a returnAddress at a given index.
 163
 164    IN:
 165            vec..............typevector, must be != NULL
 166            index............index of component to check
 167
 168    RETURN VALUE:
 169        true if the typevector contains a returnAddress at INDEX,
 170            false otherwise
 171
 172 *******************************************************************************/
 173
 174 bool
 175 typevector_checkretaddr(varinfo *vec,int index)
 176 {
 177         TYPEINFO_ASSERT(vec);
 178         return TYPEDESC_IS_RETURNADDRESS(vec[index]);
 179 }
 180
 181 /* typevector_store ************************************************************
 182
 183    Store a type at a given index in the typevector.
 184
 185    IN:
 186            vec..............typevector set, must be != NULL
 187            index............index of component to set
 188            type.............TYPE_* constant of type to set
 189            info.............typeinfo of type to set, may be NULL,
 190                             if TYPE != TYPE_ADR
 191
 192 *******************************************************************************/
 193
 194 void
 195 typevector_store(varinfo *vec,int index,int type,typeinfo *info)
 196 {
 197         TYPEINFO_ASSERT(vec);
 198
 199         vec[index].type = type;
 200         if (info)
 201                 TYPEINFO_COPY(*info,vec[index].typeinfo);
 202 }
 203
 204 /* typevector_store_retaddr ****************************************************
 205
 206    Store a returnAddress type at a given index in the typevector.
 207
 208    IN:
 209            vec..............typevector set, must be != NULL
 210            index............index of component to set
 211            info.............typeinfo of the returnAddress.
 212
 213 *******************************************************************************/
 214
 215 void
 216 typevector_store_retaddr(varinfo *vec,int index,typeinfo *info)
 217 {
 218         TYPEINFO_ASSERT(vec);
 219         TYPEINFO_ASSERT(TYPEINFO_IS_PRIMITIVE(*info));
 220
 221         vec[index].type = TYPE_ADR;
 222         TYPEINFO_INIT_RETURNADDRESS(vec[index].typeinfo,
 223                         TYPEINFO_RETURNADDRESS(*info));
 224 }
 225
 226 /* typevector_init_object ******************************************************
 227
 228    Replace all uninitialized object types in the typevector set which were
 229    created by the given instruction by initialized object types.
 230
 231    IN:
 232            set..............typevector set
 233            ins..............instruction which created the uninitialized object type
 234            initclass........class of the initialized object type to set
 235            size.............number of elements per typevector
 236
 237    RETURN VALUE:
 238        true.............success
 239            false............an exception has been thrown
 240
 241    XXX maybe we should do the lazy resolving before calling this function
 242
 243 *******************************************************************************/
 244
 245 bool
 246 typevector_init_object(varinfo *set,void *ins,
 247                                            classref_or_classinfo initclass,
 248                                            int size)
 249 {
 250         int i;
 251
 252         for (i=0; i<size; ++i) {
 253                 if (set[i].type == TYPE_ADR
 254                         && TYPEINFO_IS_NEWOBJECT(set[i].typeinfo)
 255                         && TYPEINFO_NEWOBJECT_INSTRUCTION(set[i].typeinfo) == ins)
 256                 {
 257                         if (!typeinfo_init_class(&(set[i].typeinfo),initclass))
 258                                 return false;
 259                 }
 260         }
 261         return true;
 262 }
 263
 264 /* typevector_merge ************************************************************
 265
 266    Merge a typevector with another one.
 267    The given typevectors must have the same number of components.
 268
 269    IN:
 270        m................method for exception messages
 271            dst..............the first typevector
 272            y................the second typevector
 273            size.............number of elements per typevector
 274
 275    OUT:
 276        *dst.............the resulting typevector
 277
 278    RETURN VALUE:
 279        typecheck_TRUE...dst has been modified
 280            typecheck_FALSE..dst has not been modified
 281            typecheck_FAIL...an exception has been thrown
 282
 283 *******************************************************************************/
 284
 285 typecheck_result
 286 typevector_merge(methodinfo *m,varinfo *dst,varinfo *y,int size)
 287 {
 288         bool changed = false;
 289         typecheck_result r;
 290
 291         varinfo *a = dst;
 292         varinfo *b = y;
 293         while (size--) {
 294                 if (a->type != TYPE_VOID && a->type != b->type) {
 295                         a->type = TYPE_VOID;
 296                         changed = true;
 297                 }
 298                 else if (a->type == TYPE_ADR) {
 299                         if (TYPEINFO_IS_PRIMITIVE(a->typeinfo)) {
 300                                 /* 'a' is a returnAddress */
 301                                 if (!TYPEINFO_IS_PRIMITIVE(b->typeinfo)
 302                                         || (TYPEINFO_RETURNADDRESS(a->typeinfo)
 303                                                 != TYPEINFO_RETURNADDRESS(b->typeinfo)))
 304                                 {
 305                                         a->type = TYPE_VOID;
 306                                         changed = true;
 307                                 }
 308                         }
 309                         else {
 310                                 /* 'a' is a reference */
 311                                 if (TYPEINFO_IS_PRIMITIVE(b->typeinfo)) {
 312                                         a->type = TYPE_VOID;
 313                                         changed = true;
 314                                 }
 315                                 else {
 316                                         /* two reference types are merged. There cannot be */
 317                                         /* a merge error. In the worst case we get j.l.O.  */
 318                                         r = typeinfo_merge(m,&(a->typeinfo),&(b->typeinfo));
 319                                         if (r == typecheck_FAIL)
 320                                                 return r;
 321                                         changed |= r;
 322                                 }
 323                         }
 324                 }
 325                 a++;
 326                 b++;
 327         }
 328         return changed;
 329 }
 330
 331 /**********************************************************************/
 332 /* READ-ONLY FUNCTIONS                                                */
 333 /* The following functions don't change typeinfo data.                */
 334 /**********************************************************************/
 335
 336 /* typeinfo_is_array ***********************************************************
 337
 338    Check whether a typeinfo describes an array type.
 339
 340    IN:
 341            info.............the typeinfo, must be != NULL
 342
 343    RETURN VALUE:
 344        true if INFO describes an array type.
 345
 346 *******************************************************************************/
 347
 348 bool
 349 typeinfo_is_array(typeinfo *info)
 350 {
 351         TYPEINFO_ASSERT(info);
 352     return TYPEINFO_IS_ARRAY(*info);
 353 }
 354
 355 /* typeinfo_is_primitive_array *************************************************
 356
 357    Check whether a typeinfo describes a primitive array type.
 358
 359    IN:
 360            info.............the typeinfo, must be != NULL
 361
 362    RETURN VALUE:
 363        true if INFO describes an array of a primitive type.
 364
 365 *******************************************************************************/
 366
 367 bool
 368 typeinfo_is_primitive_array(typeinfo *info,int arraytype)
 369 {
 370         TYPEINFO_ASSERT(info);
 371     return TYPEINFO_IS_PRIMITIVE_ARRAY(*info,arraytype);
 372 }
 373
 374 /* typeinfo_is_array_of_refs ***************************************************
 375
 376    Check whether a typeinfo describes an array of references type.
 377
 378    IN:
 379            info.............the typeinfo, must be != NULL
 380
 381    RETURN VALUE:
 382        true if INFO describes an array of a refrence type.
 383
 384 *******************************************************************************/
 385
 386 bool
 387 typeinfo_is_array_of_refs(typeinfo *info)
 388 {
 389         TYPEINFO_ASSERT(info);
 390     return TYPEINFO_IS_ARRAY_OF_REFS(*info);
 391 }
 392
 393 /* interface_extends_interface *************************************************
 394
 395    Check if a resolved interface extends a given resolved interface.
 396
 397    IN:
 398            cls..............the interface, must be linked
 399            interf...........the interface to check against
 400
 401    RETURN VALUE:
 402        true.............CLS extends INTERF
 403            false............CLS does not extend INTERF
 404
 405 *******************************************************************************/
 406
 407 static bool
 408 interface_extends_interface(classinfo *cls,classinfo *interf)
 409 {
 410     int i;
 411
 412         TYPEINFO_ASSERT(cls);
 413         TYPEINFO_ASSERT(interf);
 414         TYPEINFO_ASSERT((interf->flags & ACC_INTERFACE) != 0);
 415         TYPEINFO_ASSERT((cls->flags & ACC_INTERFACE) != 0);
 416         TYPEINFO_ASSERT(cls->state & CLASS_LINKED);
 417
 418     /* first check direct superinterfaces */
 419     for (i=0; i<cls->interfacescount; ++i) {
 420         if (cls->interfaces[i].cls == interf)
 421             return true;
 422     }
 423
 424     /* check indirect superinterfaces */
 425     for (i=0; i<cls->interfacescount; ++i) {
 426         if (interface_extends_interface(cls->interfaces[i].cls,interf))
 427             return true;
 428     }
 429
 430     return false;
 431 }
 432
 433 /* classinfo_implements_interface **********************************************
 434
 435    Check if a resolved class implements a given resolved interface.
 436
 437    IN:
 438            cls..............the class
 439            interf...........the interface
 440
 441    RETURN VALUE:
 442        typecheck_TRUE...CLS implements INTERF
 443            typecheck_FALSE..CLS does not implement INTERF
 444            typecheck_FAIL...an exception has been thrown
 445
 446 *******************************************************************************/
 447
 448 static typecheck_result
 449 classinfo_implements_interface(classinfo *cls,classinfo *interf)
 450 {
 451         TYPEINFO_ASSERT(cls);
 452         TYPEINFO_ASSERT(interf);
 453         TYPEINFO_ASSERT((interf->flags & ACC_INTERFACE) != 0);
 454
 455         if (!(cls->state & CLASS_LINKED))
 456                 if (!link_class(cls))
 457                         return typecheck_FAIL;
 458
 459     if (cls->flags & ACC_INTERFACE) {
 460         /* cls is an interface */
 461         if (cls == interf)
 462             return typecheck_TRUE;
 463
 464         /* check superinterfaces */
 465         return interface_extends_interface(cls,interf);
 466     }
 467
 468         TYPEINFO_ASSERT(cls->state & CLASS_LINKED);
 469     return CLASSINFO_IMPLEMENTS_INTERFACE(cls,interf->index);
 470 }
 471
 472 /* mergedlist_implements_interface *********************************************
 473
 474    Check if all the classes in a given merged list implement a given resolved
 475    interface.
 476
 477    IN:
 478            merged...........the list of merged class types
 479            interf...........the interface to check against
 480
 481    RETURN VALUE:
 482        typecheck_TRUE...all classes implement INTERF
 483            typecheck_FALSE..there is at least one class that does not implement
 484                             INTERF
 485            typecheck_MAYBE..check cannot be performed now because of unresolved
 486                             classes
 487            typecheck_FAIL...an exception has been thrown
 488
 489 *******************************************************************************/
 490
 491 static typecheck_result
 492 mergedlist_implements_interface(typeinfo_mergedlist *merged,
 493                                 classinfo *interf)
 494 {
 495     int i;
 496     classref_or_classinfo *mlist;
 497         typecheck_result r;
 498
 499         TYPEINFO_ASSERT(interf);
 500         TYPEINFO_ASSERT((interf->flags & ACC_INTERFACE) != 0);
 501
 502     /* Check if there is an non-empty mergedlist. */
 503     if (!merged)
 504         return typecheck_FALSE;
 505
 506     /* If all classinfos in the (non-empty) merged array implement the
 507      * interface return true, otherwise false.
 508      */
 509     mlist = merged->list;
 510     i = merged->count;
 511     while (i--) {
 512                 if (IS_CLASSREF(*mlist)) {
 513                         return typecheck_MAYBE;
 514                 }
 515         r = classinfo_implements_interface((mlist++)->cls,interf);
 516         if (r != typecheck_TRUE)
 517                         return r;
 518     }
 519     return typecheck_TRUE;
 520 }
 521
 522 /* merged_implements_interface *************************************************
 523
 524    Check if a possible merged type implements a given resolved interface
 525    interface.
 526
 527    IN:
 528        typeclass........(common) class of the (merged) type
 529            merged...........the list of merged class types
 530            interf...........the interface to check against
 531
 532    RETURN VALUE:
 533        typecheck_TRUE...the type implement INTERF
 534            typecheck_FALSE..the type does not implement INTERF
 535            typecheck_MAYBE..check cannot be performed now because of unresolved
 536                             classes
 537            typecheck_FAIL...an exception has been thrown
 538
 539 *******************************************************************************/
 540
 541 static typecheck_result
 542 merged_implements_interface(classinfo *typeclass,typeinfo_mergedlist *merged,
 543                             classinfo *interf)
 544 {
 545         typecheck_result r;
 546
 547     /* primitive types don't support interfaces. */
 548     if (!typeclass)
 549         return typecheck_FALSE;
 550
 551     /* the null type can be cast to any interface type. */
 552     if (typeclass == pseudo_class_Null)
 553         return typecheck_TRUE;
 554
 555     /* check if typeclass implements the interface. */
 556     r = classinfo_implements_interface(typeclass,interf);
 557         if (r != typecheck_FALSE)
 558         return r;
 559
 560     /* check the mergedlist */
 561         if (!merged)
 562                 return typecheck_FALSE;
 563     return mergedlist_implements_interface(merged,interf);
 564 }
 565
 566 /* merged_is_subclass **********************************************************
 567
 568    Check if a possible merged type is a subclass of a given class.
 569    A merged type is a subclass of a class C if all types in the merged list
 570    are subclasses of C. A sufficient condition for this is that the
 571    common type of the merged type is a subclass of C.
 572
 573    IN:
 574        typeclass........(common) class of the (merged) type
 575                             MUST be a loaded and linked class
 576            merged...........the list of merged class types
 577            cls..............the class to theck against
 578
 579    RETURN VALUE:
 580        typecheck_TRUE...the type is a subclass of CLS
 581            typecheck_FALSE..the type is not a subclass of CLS
 582            typecheck_MAYBE..check cannot be performed now because of unresolved
 583                             classes
 584            typecheck_FAIL...an exception has been thrown
 585
 586 *******************************************************************************/
 587
 588 static typecheck_result
 589 merged_is_subclass(classinfo *typeclass,typeinfo_mergedlist *merged,
 590                 classinfo *cls)
 591 {
 592     int i;
 593     classref_or_classinfo *mlist;
 594
 595         TYPEINFO_ASSERT(cls);
 596
 597     /* primitive types aren't subclasses of anything. */
 598     if (!typeclass)
 599         return typecheck_FALSE;
 600
 601     /* the null type can be cast to any reference type. */
 602     if (typeclass == pseudo_class_Null)
 603         return typecheck_TRUE;
 604
 605         TYPEINFO_ASSERT(typeclass->state & CLASS_LOADED);
 606         TYPEINFO_ASSERT(typeclass->state & CLASS_LINKED);
 607
 608     /* check if the common typeclass is a subclass of CLS. */
 609         if (class_issubclass(typeclass,cls))
 610                 return typecheck_TRUE;
 611
 612     /* check the mergedlist */
 613         if (!merged)
 614                 return typecheck_FALSE;
 615     /* If all classinfos in the (non-empty) merged list are subclasses
 616          * of CLS, return true, otherwise false.
 617          * If there is at least one unresolved type in the list,
 618          * return typecheck_MAYBE.
 619      */
 620     mlist = merged->list;
 621     i = merged->count;
 622     while (i--) {
 623                 if (IS_CLASSREF(*mlist)) {
 624                         return typecheck_MAYBE;
 625                 }
 626                 if (!(mlist->cls->state & CLASS_LINKED))
 627                         if (!link_class(mlist->cls))
 628                                 return typecheck_FAIL;
 629                 if (!class_issubclass(mlist->cls,cls))
 630                         return typecheck_FALSE;
 631                 mlist++;
 632     }
 633     return typecheck_TRUE;
 634 }
 635
 636 /* typeinfo_is_assignable_to_class *********************************************
 637
 638    Check if a type is assignable to a given class type.
 639
 640    IN:
 641        value............the type of the value
 642            dest.............the type of the destination
 643
 644    RETURN VALUE:
 645        typecheck_TRUE...the type is assignable
 646            typecheck_FALSE..the type is not assignable
 647            typecheck_MAYBE..check cannot be performed now because of unresolved
 648                             classes
 649            typecheck_FAIL...an exception has been thrown
 650
 651 *******************************************************************************/
 652
 653 typecheck_result
 654 typeinfo_is_assignable_to_class(typeinfo *value,classref_or_classinfo dest)
 655 {
 656         classref_or_classinfo c;
 657     classinfo *cls;
 658         utf *classname;
 659
 660         TYPEINFO_ASSERT(value);
 661
 662     c = value->typeclass;
 663
 664     /* assignments of primitive values are not checked here. */
 665     if (!c.any && !dest.any)
 666         return typecheck_TRUE;
 667
 668     /* primitive and reference types are not assignment compatible. */
 669     if (!c.any || !dest.any)
 670         return typecheck_FALSE;
 671
 672     /* the null type can be assigned to any type */
 673     if (TYPEINFO_IS_NULLTYPE(*value))
 674         return typecheck_TRUE;
 675
 676     /* uninitialized objects are not assignable */
 677     if (TYPEINFO_IS_NEWOBJECT(*value))
 678         return typecheck_FALSE;
 679
 680         if (IS_CLASSREF(c)) {
 681                 /* The value type is an unresolved class reference. */
 682                 classname = c.ref->name;
 683         }
 684         else {
 685                 classname = c.cls->name;
 686         }
 687
 688         if (IS_CLASSREF(dest)) {
 689                 /* the destination type is an unresolved class reference */
 690                 /* In this case we cannot tell a lot about assignability. */
 691
 692                 /* the common case of value and dest type having the same classname */
 693                 if (dest.ref->name == classname && !value->merged)
 694                         return typecheck_TRUE;
 695
 696                 /* we cannot tell if value is assignable to dest, so we */
 697                 /* leave it up to the resolving code to check this      */
 698                 return typecheck_MAYBE;
 699         }
 700
 701         /* { we know that dest is a loaded class } */
 702
 703         if (IS_CLASSREF(c)) {
 704                 /* the value type is an unresolved class reference */
 705
 706                 /* the common case of value and dest type having the same classname */
 707                 if (dest.cls->name == classname)
 708                         return typecheck_TRUE;
 709
 710                 /* we cannot tell if value is assignable to dest, so we */
 711                 /* leave it up to the resolving code to check this      */
 712                 return typecheck_MAYBE;
 713         }
 714
 715         /* { we know that both c and dest are loaded classes } */
 716         /* (c may still have a merged list containing unresolved classrefs!) */
 717
 718         TYPEINFO_ASSERT(!IS_CLASSREF(c));
 719         TYPEINFO_ASSERT(!IS_CLASSREF(dest));
 720
 721         cls = c.cls;
 722
 723         TYPEINFO_ASSERT(cls->state & CLASS_LOADED);
 724         TYPEINFO_ASSERT(dest.cls->state & CLASS_LOADED);
 725
 726         /* maybe we need to link the classes */
 727         if (!(cls->state & CLASS_LINKED))
 728                 if (!link_class(cls))
 729                         return typecheck_FAIL;
 730         if (!(dest.cls->state & CLASS_LINKED))
 731                 if (!link_class(dest.cls))
 732                         return typecheck_FAIL;
 733
 734         /* { we know that both c and dest are linked classes } */
 735         TYPEINFO_ASSERT(cls->state & CLASS_LINKED);
 736         TYPEINFO_ASSERT(dest.cls->state & CLASS_LINKED);
 737
 738     if (dest.cls->flags & ACC_INTERFACE) {
 739         /* We are assigning to an interface type. */
 740         return merged_implements_interface(cls,value->merged,dest.cls);
 741     }
 742
 743     if (CLASSINFO_IS_ARRAY(dest.cls)) {
 744                 arraydescriptor *arraydesc = dest.cls->vftbl->arraydesc;
 745                 int dimension = arraydesc->dimension;
 746                 classinfo *elementclass = (arraydesc->elementvftbl)
 747                         ? arraydesc->elementvftbl->class : NULL;
 748
 749         /* We are assigning to an array type. */
 750         if (!TYPEINFO_IS_ARRAY(*value))
 751             return typecheck_FALSE;
 752
 753         /* {Both value and dest.cls are array types.} */
 754
 755         /* value must have at least the dimension of dest.cls. */
 756         if (value->dimension < dimension)
 757             return typecheck_FALSE;
 758
 759         if (value->dimension > dimension) {
 760             /* value has higher dimension so we need to check
 761              * if its component array can be assigned to the
 762              * element type of dest.cls */
 763
 764                         if (!elementclass) return typecheck_FALSE;
 765
 766             if (elementclass->flags & ACC_INTERFACE) {
 767                 /* We are assigning to an interface type. */
 768                 return classinfo_implements_interface(pseudo_class_Arraystub,
 769                                                       elementclass);
 770             }
 771
 772             /* We are assigning to a class type. */
 773             return class_issubclass(pseudo_class_Arraystub,elementclass);
 774         }
 775
 776         /* {value and dest.cls have the same dimension} */
 777
 778         if (value->elementtype != arraydesc->elementtype)
 779             return typecheck_FALSE;
 780
 781         if (value->elementclass.any) {
 782             /* We are assigning an array of objects so we have to
 783              * check if the elements are assignable.
 784              */
 785
 786             if (elementclass->flags & ACC_INTERFACE) {
 787                 /* We are assigning to an interface type. */
 788
 789                 return merged_implements_interface(value->elementclass.cls,
 790                                                    value->merged,
 791                                                    elementclass);
 792             }
 793
 794             /* We are assigning to a class type. */
 795             return merged_is_subclass(value->elementclass.cls,value->merged,elementclass);
 796         }
 797
 798         return typecheck_TRUE;
 799     }
 800
 801     /* {dest.cls is not an array} */
 802     /* {dest.cls is a loaded class} */
 803
 804         /* If there are any unresolved references in the merged list, we cannot */
 805         /* tell if the assignment will be ok.                                   */
 806         /* This can only happen when cls is java.lang.Object                    */
 807         if (cls == class_java_lang_Object && value->merged) {
 808                 classref_or_classinfo *mlist = value->merged->list;
 809                 int i = value->merged->count;
 810                 while (i--)
 811                         if (IS_CLASSREF(*mlist++))
 812                                 return typecheck_MAYBE;
 813         }
 814
 815     /* We are assigning to a class type */
 816     if (cls->flags & ACC_INTERFACE)
 817         cls = class_java_lang_Object;
 818
 819     return merged_is_subclass(cls,value->merged,dest.cls);
 820 }
 821
 822 /* typeinfo_is_assignable ******************************************************
 823
 824    Check if a type is assignable to a given type.
 825
 826    IN:
 827        value............the type of the value
 828            dest.............the type of the destination, must not be a merged type
 829
 830    RETURN VALUE:
 831        typecheck_TRUE...the type is assignable
 832            typecheck_FALSE..the type is not assignable
 833            typecheck_MAYBE..check cannot be performed now because of unresolved
 834                             classes
 835            typecheck_FAIL...an exception has been thrown
 836
 837 *******************************************************************************/
 838
 839 typecheck_result
 840 typeinfo_is_assignable(typeinfo *value,typeinfo *dest)
 841 {
 842         TYPEINFO_ASSERT(value);
 843         TYPEINFO_ASSERT(dest);
 844         TYPEINFO_ASSERT(dest->merged == NULL);
 845
 846         return typeinfo_is_assignable_to_class(value,dest->typeclass);
 847 }
 848
 849 /**********************************************************************/
 850 /* INITIALIZATION FUNCTIONS                                           */
 851 /* The following functions fill in uninitialized typeinfo structures. */
 852 /**********************************************************************/
 853
 854 /* typeinfo_init_classinfo *****************************************************
 855
 856    Initialize a typeinfo to a resolved class.
 857
 858    IN:
 859            c................the class
 860
 861    OUT:
 862        *info............is initialized
 863
 864    RETURN VALUE:
 865        true.............success
 866            false............an exception has been thrown
 867
 868 *******************************************************************************/
 869
 870 void
 871 typeinfo_init_classinfo(typeinfo *info, classinfo *c)
 872 {
 873         if ((info->typeclass.cls = c)->vftbl->arraydesc) {
 874                 if (c->vftbl->arraydesc->elementvftbl)
 875                         info->elementclass.cls = c->vftbl->arraydesc->elementvftbl->class;
 876                 else
 877                         info->elementclass.any = NULL;
 878                 info->dimension = c->vftbl->arraydesc->dimension;
 879                 info->elementtype = c->vftbl->arraydesc->elementtype;
 880         }
 881         else {
 882                 info->elementclass.any = NULL;
 883                 info->dimension = 0;
 884                 info->elementtype = 0;
 885         }
 886         info->merged = NULL;
 887 }
 888
 889 /* typeinfo_init_class *********************************************************
 890
 891    Initialize a typeinfo to a possibly unresolved class type.
 892
 893    IN:
 894            c................the class type
 895
 896    OUT:
 897        *info............is initialized
 898
 899    RETURN VALUE:
 900        true.............success
 901            false............an exception has been thrown
 902
 903 *******************************************************************************/
 904
 905 bool
 906 typeinfo_init_class(typeinfo *info,classref_or_classinfo c)
 907 {
 908         char *utf_ptr;
 909         int len;
 910         classinfo *cls;
 911
 912         TYPEINFO_ASSERT(c.any);
 913         TYPEINFO_ASSERT(info);
 914
 915         /* if necessary, try to resolve lazily */
 916         if (!resolve_classref_or_classinfo(NULL /* XXX should know method */,
 917                                 c,resolveLazy,false,true,&cls))
 918         {
 919                 return false;
 920         }
 921
 922         if (cls) {
 923                 typeinfo_init_classinfo(info,cls);
 924                 return true;
 925         }
 926
 927         /* {the type could no be resolved lazily} */
 928
 929         info->typeclass.ref = c.ref;
 930         info->elementclass.any = NULL;
 931         info->dimension = 0;
 932         info->merged = NULL;
 933
 934         /* handle array type references */
 935         utf_ptr = c.ref->name->text;
 936         len = c.ref->name->blength;
 937         if (*utf_ptr == '[') {
 938                 /* count dimensions */
 939                 while (*utf_ptr == '[') {
 940                         utf_ptr++;
 941                         info->dimension++;
 942                         len--;
 943                 }
 944                 if (*utf_ptr == 'L') {
 945                         utf_ptr++;
 946                         len -= 2;
 947                         info->elementtype = ARRAYTYPE_OBJECT;
 948                         info->elementclass.ref = class_get_classref(c.ref->referer,utf_new(utf_ptr,len));
 949                 }
 950                 else {
 951                         /* an array with primitive element type */
 952                         /* should have been resolved above */
 953                         TYPEINFO_ASSERT(false);
 954                 }
 955         }
 956         return true;
 957 }
 958
 959 /* typeinfo_init_from_typedesc *************************************************
 960
 961    Initialize a typeinfo from a typedesc.
 962
 963    IN:
 964            desc.............the typedesc
 965
 966    OUT:
 967        *type............set to the TYPE_* constant of DESC (if type != NULL)
 968        *info............receives the typeinfo (if info != NULL)
 969
 970    RETURN VALUE:
 971        true.............success
 972            false............an exception has been thrown
 973
 974 *******************************************************************************/
 975
 976 bool
 977 typeinfo_init_from_typedesc(typedesc *desc,u1 *type,typeinfo *info)
 978 {
 979         TYPEINFO_ASSERT(desc);
 980
 981 #ifdef TYPEINFO_VERBOSE
 982         fprintf(stderr,"typeinfo_init_from_typedesc(");
 983         descriptor_debug_print_typedesc(stderr,desc);
 984         fprintf(stderr,")\n");
 985 #endif
 986
 987         if (type)
 988                 *type = desc->type;
 989
 990         if (info) {
 991                 if (desc->type == TYPE_ADR) {
 992                         TYPEINFO_ASSERT(desc->classref);
 993                         if (!typeinfo_init_class(info,CLASSREF_OR_CLASSINFO(desc->classref)))
 994                                 return false;
 995                 }
 996                 else {
 997                         TYPEINFO_INIT_PRIMITIVE(*info);
 998                 }
 999         }
1000         return true;
1001 }
1002
1003 /* typeinfos_init_from_methoddesc **********************************************
1004
1005    Initialize an array of typeinfos and u1 TYPE_* values from a methoddesc.
1006
1007    IN:
1008        desc.............the methoddesc
1009        buflen...........number of parameters the buffer can hold
1010        twoword..........if true, use two parameter slots for two-word types
1011
1012    OUT:
1013        *typebuf.........receives a TYPE_* constant for each parameter
1014                         typebuf must be != NULL
1015        *infobuf.........receives a typeinfo for each parameter
1016                         infobuf must be != NULL
1017        *returntype......receives a TYPE_* constant for the return type
1018                         returntype may be NULL
1019        *returntypeinfo..receives a typeinfo for the return type
1020                         returntypeinfo may be NULL
1021
1022    RETURN VALUE:
1023        true.............success
1024        false............an exception has been thrown
1025
1026    NOTE:
1027        If (according to BUFLEN) the buffers are to small to hold the
1028            parameter types, an internal error is thrown. This must be
1029            avoided by checking the number of parameters and allocating enough
1030            space before calling this function.
1031
1032 *******************************************************************************/
1033
1034 bool
1035 typeinfos_init_from_methoddesc(methoddesc *desc,u1 *typebuf,typeinfo *infobuf,
1036                               int buflen,bool twoword,
1037                               u1 *returntype,typeinfo *returntypeinfo)
1038 {
1039         int i;
1040     int args = 0;
1041
1042         TYPEINFO_ASSERT(desc);
1043         TYPEINFO_ASSERT(typebuf);
1044         TYPEINFO_ASSERT(infobuf);
1045
1046 #ifdef TYPEINFO_VERBOSE
1047         fprintf(stderr,"typeinfos_init_from_methoddesc(");
1048         descriptor_debug_print_methoddesc(stderr,desc);
1049         fprintf(stderr,")\n");
1050 #endif
1051
1052     /* check arguments */
1053     for (i=0; i<desc->paramcount; ++i) {
1054                 if (++args > buflen) {
1055                         exceptions_throw_internalerror("Buffer too small for method arguments.");
1056                         return false;
1057                 }
1058
1059                 if (!typeinfo_init_from_typedesc(desc->paramtypes + i,typebuf++,infobuf++))
1060                         return false;
1061
1062                 if (twoword && (typebuf[-1] == TYPE_LNG || typebuf[-1] == TYPE_DBL)) {
1063                         if (++args > buflen) {
1064                                 exceptions_throw_internalerror("Buffer too small for method arguments.");
1065                                 return false;
1066                         }
1067
1068                         *typebuf++ = TYPE_VOID;
1069                         TYPEINFO_INIT_PRIMITIVE(*infobuf);
1070                         infobuf++;
1071                 }
1072     }
1073
1074     /* check returntype */
1075     if (returntype) {
1076                 if (!typeinfo_init_from_typedesc(&(desc->returntype),returntype,returntypeinfo))
1077                         return false;
1078         }
1079
1080         return true;
1081 }
1082
1083 /* typedescriptor_init_from_typedesc *******************************************
1084
1085    Initialize a typedescriptor from a typedesc.
1086
1087    IN:
1088            desc.............the typedesc
1089
1090    OUT:
1091        *td..............receives the typedescriptor
1092                             td must be != NULL
1093
1094    RETURN VALUE:
1095        true.............success
1096            false............an exception has been thrown
1097
1098 *******************************************************************************/
1099
1100 bool
1101 typedescriptor_init_from_typedesc(typedescriptor *td,
1102                                                                   typedesc *desc)
1103 {
1104         TYPEINFO_ASSERT(td);
1105         TYPEINFO_ASSERT(desc);
1106
1107         td->type = desc->type;
1108         if (td->type == TYPE_ADR) {
1109                 if (!typeinfo_init_class(&(td->typeinfo),CLASSREF_OR_CLASSINFO(desc->classref)))
1110                         return false;
1111         }
1112         else {
1113                 TYPEINFO_INIT_PRIMITIVE(td->typeinfo);
1114         }
1115         return true;
1116 }
1117
1118 /* typeinfo_init_varinfo_from_typedesc *****************************************
1119
1120    Initialize a varinfo from a typedesc.
1121
1122    IN:
1123            desc.............the typedesc
1124
1125    OUT:
1126        *var.............receives the type
1127                             var must be != NULL
1128
1129    RETURN VALUE:
1130        true.............success
1131            false............an exception has been thrown
1132
1133 *******************************************************************************/
1134
1135 bool
1136 typeinfo_init_varinfo_from_typedesc(varinfo *var,
1137                                                                   typedesc *desc)
1138 {
1139         TYPEINFO_ASSERT(var);
1140         TYPEINFO_ASSERT(desc);
1141
1142         var->type = desc->type;
1143         if (var->type == TYPE_ADR) {
1144                 if (!typeinfo_init_class(&(var->typeinfo),CLASSREF_OR_CLASSINFO(desc->classref)))
1145                         return false;
1146         }
1147         else {
1148                 TYPEINFO_INIT_PRIMITIVE(var->typeinfo);
1149         }
1150         return true;
1151 }
1152
1153 /* typeinfo_init_varinfos_from_methoddesc **************************************
1154
1155    Initialize an array of varinfos from a methoddesc.
1156
1157    IN:
1158        desc.............the methoddesc
1159        buflen...........number of parameters the buffer can hold
1160            startindex.......the zero-based index of the first parameter to
1161                             write to the array. In other words the number of
1162                                                 parameters to skip at the beginning of the methoddesc.
1163            map..............map from parameter indices to varinfo indices
1164                             (indexed like jitdata.local_map)
1165
1166    OUT:
1167        *vars............array receiving the varinfos
1168                             td[0] receives the type of the
1169                                                 (startindex+1)th parameter of the method
1170        *returntype......receives the typedescriptor of the return type.
1171                             returntype may be NULL
1172
1173    RETURN VALUE:
1174        true.............everything ok
1175            false............an exception has been thrown
1176
1177    NOTE:
1178        If (according to BUFLEN) the buffer is to small to hold the
1179            parameter types, an internal error is thrown. This must be
1180            avoided by checking the number of parameters and allocating enough
1181            space before calling this function.
1182
1183 *******************************************************************************/
1184
1185 bool
1186 typeinfo_init_varinfos_from_methoddesc(varinfo *vars,
1187                                                                          methoddesc *desc,
1188                                                                          int buflen, int startindex,
1189                                                                          s4 *map,
1190                                                                          typedescriptor *returntype)
1191 {
1192         s4 i;
1193     s4 index;
1194         s4 type;
1195         s4 slot = 0;
1196
1197         /* skip arguments */
1198         for (i=0; i<startindex; ++i) {
1199                 slot++;
1200                 if (IS_2_WORD_TYPE(desc->paramtypes[i].type))
1201                         slot++;
1202         }
1203
1204     /* check arguments */
1205     for (i=startindex; i<desc->paramcount; ++i) {
1206                 type = desc->paramtypes[i].type;
1207                 index = map[5*slot + type];
1208
1209                 slot++;
1210                 if (IS_2_WORD_TYPE(type))
1211                         slot++;
1212
1213                 if (index == UNUSED)
1214                         continue;
1215
1216                 if (index >= buflen) {
1217                         exceptions_throw_internalerror("Buffer too small for method arguments.");
1218                         return false;
1219                 }
1220
1221                 if (!typeinfo_init_varinfo_from_typedesc(vars + index, desc->paramtypes + i))
1222                         return false;
1223     }
1224
1225     /* check returntype */
1226     if (returntype) {
1227                 if (!typedescriptor_init_from_typedesc(returntype,&(desc->returntype)))
1228                         return false;
1229         }
1230
1231         return true;
1232 }
1233
1234 /* typedescriptors_init_from_methoddesc ****************************************
1235
1236    Initialize an array of typedescriptors from a methoddesc.
1237
1238    IN:
1239        desc.............the methoddesc
1240        buflen...........number of parameters the buffer can hold
1241        twoword..........if true, use two parameter slots for two-word types
1242            startindex.......the zero-based index of the first parameter to
1243                             write to the array. In other words the number of
1244                                                 parameters to skip at the beginning of the methoddesc.
1245
1246    OUT:
1247        *td..............array receiving the typedescriptors.
1248                             td[0] receives the typedescriptor of the
1249                                                 (startindex+1)th parameter of the method
1250        *returntype......receives the typedescriptor of the return type.
1251                             returntype may be NULL
1252
1253    RETURN VALUE:
1254        >= 0.............number of typedescriptors filled in TD
1255            -1...............an exception has been thrown
1256
1257    NOTE:
1258        If (according to BUFLEN) the buffer is to small to hold the
1259            parameter types, an internal error is thrown. This must be
1260            avoided by checking the number of parameters and allocating enough
1261            space before calling this function.
1262
1263 *******************************************************************************/
1264
1265 int
1266 typedescriptors_init_from_methoddesc(typedescriptor *td,
1267                                                                          methoddesc *desc,
1268                                                                          int buflen,bool twoword,int startindex,
1269                                                                          typedescriptor *returntype)
1270 {
1271         int i;
1272     int args = 0;
1273
1274     /* check arguments */
1275     for (i=startindex; i<desc->paramcount; ++i) {
1276                 if (++args > buflen) {
1277                         exceptions_throw_internalerror("Buffer too small for method arguments.");
1278                         return -1;
1279                 }
1280
1281                 if (!typedescriptor_init_from_typedesc(td,desc->paramtypes + i))
1282                         return -1;
1283                 td++;
1284
1285                 if (twoword && (td[-1].type == TYPE_LNG || td[-1].type == TYPE_DBL)) {
1286                         if (++args > buflen) {
1287                                 exceptions_throw_internalerror("Buffer too small for method arguments.");
1288                                 return -1;
1289                         }
1290
1291                         td->type = TYPE_VOID;
1292                         TYPEINFO_INIT_PRIMITIVE(td->typeinfo);
1293                         td++;
1294                 }
1295     }
1296
1297     /* check returntype */
1298     if (returntype) {
1299                 if (!typedescriptor_init_from_typedesc(returntype,&(desc->returntype)))
1300                         return -1;
1301         }
1302
1303         return args;
1304 }
1305
1306 /* typeinfo_init_component *****************************************************
1307
1308    Initialize a typeinfo with the component type of a given array type.
1309
1310    IN:
1311            srcarray.........the typeinfo of the array type
1312
1313    OUT:
1314        *dst.............receives the typeinfo of the component type
1315
1316    RETURN VALUE:
1317        true.............success
1318            false............an exception has been thrown
1319
1320 *******************************************************************************/
1321
1322 bool
1323 typeinfo_init_component(typeinfo *srcarray,typeinfo *dst)
1324 {
1325         typeinfo_mergedlist *merged;
1326
1327         TYPEINFO_ASSERT(srcarray);
1328         TYPEINFO_ASSERT(dst);
1329
1330     if (TYPEINFO_IS_NULLTYPE(*srcarray)) {
1331         TYPEINFO_INIT_NULLTYPE(*dst);
1332         return true;
1333     }
1334
1335     if (!TYPEINFO_IS_ARRAY(*srcarray)) {
1336                 /* XXX should we make that a verify error? */
1337                 exceptions_throw_internalerror("Trying to access component of non-array");
1338                 return false;
1339         }
1340
1341         /* save the mergedlist (maybe dst == srcarray) */
1342
1343         merged = srcarray->merged;
1344
1345         if (IS_CLASSREF(srcarray->typeclass)) {
1346                 constant_classref *comp;
1347                 comp = class_get_classref_component_of(srcarray->typeclass.ref);
1348
1349                 if (comp) {
1350                         if (!typeinfo_init_class(dst,CLASSREF_OR_CLASSINFO(comp)))
1351                                 return false;
1352                 }
1353                 else {
1354                         TYPEINFO_INIT_PRIMITIVE(*dst);
1355                 }
1356         }
1357         else {
1358                 vftbl_t *comp;
1359
1360                 if (!(srcarray->typeclass.cls->state & CLASS_LINKED)) {
1361                         if (!link_class(srcarray->typeclass.cls)) {
1362                                 return false;
1363                         }
1364                 }
1365
1366                 TYPEINFO_ASSERT(srcarray->typeclass.cls->vftbl);
1367                 TYPEINFO_ASSERT(srcarray->typeclass.cls->vftbl->arraydesc);
1368
1369                 comp = srcarray->typeclass.cls->vftbl->arraydesc->componentvftbl;
1370                 if (comp)
1371                         typeinfo_init_classinfo(dst,comp->class);
1372                 else
1373                         TYPEINFO_INIT_PRIMITIVE(*dst);
1374         }
1375
1376     dst->merged = merged; /* XXX should we do a deep copy? */
1377         return true;
1378 }
1379
1380 /* typeinfo_clone **************************************************************
1381
1382    Create a deep copy of a typeinfo struct.
1383
1384    IN:
1385            src..............the typeinfo to copy
1386
1387    OUT:
1388        *dest............receives the copy
1389
1390    NOTE:
1391        If src == dest this function is a nop.
1392
1393 *******************************************************************************/
1394
1395 void
1396 typeinfo_clone(typeinfo *src,typeinfo *dest)
1397 {
1398     int count;
1399     classref_or_classinfo *srclist,*destlist;
1400
1401     if (src == dest)
1402         return;
1403
1404     *dest = *src;
1405
1406     if (src->merged) {
1407         count = src->merged->count;
1408         TYPEINFO_ALLOCMERGED(dest->merged,count);
1409         dest->merged->count = count;
1410
1411         srclist = src->merged->list;
1412         destlist = dest->merged->list;
1413         while (count--)
1414             *destlist++ = *srclist++;
1415     }
1416 }
1417
1418 /**********************************************************************/
1419 /* MISCELLANEOUS FUNCTIONS                                            */
1420 /**********************************************************************/
1421
1422 /* typeinfo_free ***************************************************************
1423
1424    Free memory referenced by the given typeinfo. The typeinfo itself is not
1425    freed.
1426
1427    IN:
1428        info.............the typeinfo
1429
1430 *******************************************************************************/
1431
1432 void
1433 typeinfo_free(typeinfo *info)
1434 {
1435     TYPEINFO_FREEMERGED_IF_ANY(info->merged);
1436     info->merged = NULL;
1437 }
1438
1439 /**********************************************************************/
1440 /* MERGING FUNCTIONS                                                  */
1441 /* The following functions are used to merge the types represented by */
1442 /* two typeinfo structures into one typeinfo structure.               */
1443 /**********************************************************************/
1444
1445 static
1446 void
1447 typeinfo_merge_error(methodinfo *m,char *str,typeinfo *x,typeinfo *y) {
1448 #ifdef TYPEINFO_VERBOSE
1449     fprintf(stderr,"Error in typeinfo_merge: %s\n",str);
1450     fprintf(stderr,"Typeinfo x:\n");
1451     typeinfo_print(stderr,x,1);
1452     fprintf(stderr,"Typeinfo y:\n");
1453     typeinfo_print(stderr,y,1);
1454     log_text(str);
1455 #endif
1456
1457         exceptions_throw_verifyerror(m, str);
1458 }
1459
1460 /* Condition: clsx != clsy. */
1461 /* Returns: true if dest was changed (currently always true). */
1462 static
1463 bool
1464 typeinfo_merge_two(typeinfo *dest,classref_or_classinfo clsx,classref_or_classinfo clsy)
1465 {
1466         TYPEINFO_ASSERT(dest);
1467     TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1468     TYPEINFO_ALLOCMERGED(dest->merged,2);
1469     dest->merged->count = 2;
1470
1471         TYPEINFO_ASSERT(clsx.any != clsy.any);
1472
1473     if (clsx.any < clsy.any) {
1474         dest->merged->list[0] = clsx;
1475         dest->merged->list[1] = clsy;
1476     }
1477     else {
1478         dest->merged->list[0] = clsy;
1479         dest->merged->list[1] = clsx;
1480     }
1481
1482     return true;
1483 }
1484
1485 /* Returns: true if dest was changed. */
1486 static
1487 bool
1488 typeinfo_merge_add(typeinfo *dest,typeinfo_mergedlist *m,classref_or_classinfo cls)
1489 {
1490     int count;
1491     typeinfo_mergedlist *newmerged;
1492     classref_or_classinfo *mlist,*newlist;
1493
1494     count = m->count;
1495     mlist = m->list;
1496
1497     /* Check if cls is already in the mergedlist m. */
1498     while (count--) {
1499         if ((mlist++)->any == cls.any) { /* XXX check equal classrefs? */
1500             /* cls is in the list, so m is the resulting mergedlist */
1501             if (dest->merged == m)
1502                 return false;
1503
1504             /* We have to copy the mergedlist */
1505             TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1506             count = m->count;
1507             TYPEINFO_ALLOCMERGED(dest->merged,count);
1508             dest->merged->count = count;
1509             newlist = dest->merged->list;
1510             mlist = m->list;
1511             while (count--) {
1512                 *newlist++ = *mlist++;
1513             }
1514             return true;
1515         }
1516     }
1517
1518     /* Add cls to the mergedlist. */
1519     count = m->count;
1520     TYPEINFO_ALLOCMERGED(newmerged,count+1);
1521     newmerged->count = count+1;
1522     newlist = newmerged->list;
1523     mlist = m->list;
1524     while (count) {
1525         if (mlist->any > cls.any)
1526             break;
1527         *newlist++ = *mlist++;
1528         count--;
1529     }
1530     *newlist++ = cls;
1531     while (count--) {
1532         *newlist++ = *mlist++;
1533     }
1534
1535     /* Put the new mergedlist into dest. */
1536     TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1537     dest->merged = newmerged;
1538
1539     return true;
1540 }
1541
1542 /* Returns: true if dest was changed. */
1543 static
1544 bool
1545 typeinfo_merge_mergedlists(typeinfo *dest,typeinfo_mergedlist *x,
1546                            typeinfo_mergedlist *y)
1547 {
1548     int count = 0;
1549     int countx,county;
1550     typeinfo_mergedlist *temp,*result;
1551     classref_or_classinfo *clsx,*clsy,*newlist;
1552
1553     /* count the elements that will be in the resulting list */
1554     /* (Both lists are sorted, equal elements are counted only once.) */
1555     clsx = x->list;
1556     clsy = y->list;
1557     countx = x->count;
1558     county = y->count;
1559     while (countx && county) {
1560         if (clsx->any == clsy->any) {
1561             clsx++;
1562             clsy++;
1563             countx--;
1564             county--;
1565         }
1566         else if (clsx->any < clsy->any) {
1567             clsx++;
1568             countx--;
1569         }
1570         else {
1571             clsy++;
1572             county--;
1573         }
1574         count++;
1575     }
1576     count += countx + county;
1577
1578     /* {The new mergedlist will have count entries.} */
1579
1580     if ((x->count != count) && (y->count == count)) {
1581         temp = x; x = y; y = temp;
1582     }
1583     /* {If one of x,y is already the result it is x.} */
1584     if (x->count == count) {
1585         /* x->merged is equal to the result */
1586         if (x == dest->merged)
1587             return false;
1588
1589         if (!dest->merged || dest->merged->count != count) {
1590             TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1591             TYPEINFO_ALLOCMERGED(dest->merged,count);
1592             dest->merged->count = count;
1593         }
1594
1595         newlist = dest->merged->list;
1596         clsx = x->list;
1597         while (count--) {
1598             *newlist++ = *clsx++;
1599         }
1600         return true;
1601     }
1602
1603     /* {We have to merge two lists.} */
1604
1605     /* allocate the result list */
1606     TYPEINFO_ALLOCMERGED(result,count);
1607     result->count = count;
1608     newlist = result->list;
1609
1610     /* merge the sorted lists */
1611     clsx = x->list;
1612     clsy = y->list;
1613     countx = x->count;
1614     county = y->count;
1615     while (countx && county) {
1616         if (clsx->any == clsy->any) {
1617             *newlist++ = *clsx++;
1618             clsy++;
1619             countx--;
1620             county--;
1621         }
1622         else if (clsx->any < clsy->any) {
1623             *newlist++ = *clsx++;
1624             countx--;
1625         }
1626         else {
1627             *newlist++ = *clsy++;
1628             county--;
1629         }
1630     }
1631     while (countx--)
1632             *newlist++ = *clsx++;
1633     while (county--)
1634             *newlist++ = *clsy++;
1635
1636     /* replace the list in dest with the result list */
1637     TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1638     dest->merged = result;
1639
1640     return true;
1641 }
1642
1643 /* typeinfo_merge_nonarrays ****************************************************
1644
1645    Merge two non-array types.
1646
1647    IN:
1648        x................the first type
1649            y................the second type
1650            mergedx..........merged list of the first type, may be NULL
1651            mergedy..........merged list of the descond type, may be NULL
1652
1653    OUT:
1654        *dest............receives the resulting merged list
1655            *result..........receives the resulting type
1656
1657    RETURN VALUE:
1658        typecheck_TRUE...*dest has been modified
1659            typecheck_FALSE..*dest has not been modified
1660            typecheck_FAIL...an exception has been thrown
1661
1662    NOTE:
1663        RESULT is an extra parameter so it can point to dest->typeclass or to
1664            dest->elementclass.
1665
1666 *******************************************************************************/
1667
1668 static typecheck_result
1669 typeinfo_merge_nonarrays(typeinfo *dest,
1670                          classref_or_classinfo *result,
1671                          classref_or_classinfo x,classref_or_classinfo y,
1672                          typeinfo_mergedlist *mergedx,
1673                          typeinfo_mergedlist *mergedy)
1674 {
1675         classref_or_classinfo t;
1676     classinfo *tcls,*common;
1677     typeinfo_mergedlist *tmerged;
1678     bool changed;
1679         typecheck_result r;
1680         utf *xname;
1681         utf *yname;
1682
1683         TYPEINFO_ASSERT(dest && result && x.any && y.any);
1684         TYPEINFO_ASSERT(x.cls != pseudo_class_Null);
1685         TYPEINFO_ASSERT(y.cls != pseudo_class_Null);
1686         TYPEINFO_ASSERT(x.cls != pseudo_class_New);
1687         TYPEINFO_ASSERT(y.cls != pseudo_class_New);
1688
1689         /*--------------------------------------------------*/
1690         /* common cases                                     */
1691         /*--------------------------------------------------*/
1692
1693     /* Common case 1: x and y are the same class or class reference */
1694     /* (This case is very simple unless *both* x and y really represent
1695      *  merges of subclasses of clsx==clsy.)
1696      */
1697     if ( (x.any == y.any) && (!mergedx || !mergedy) ) {
1698   return_simple_x:
1699         /* DEBUG */ /* log_text("return simple x"); */
1700         changed = (dest->merged != NULL);
1701         TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1702         dest->merged = NULL;
1703         *result = x;
1704         /* DEBUG */ /* log_text("returning"); */
1705         return changed;
1706     }
1707
1708         xname = (IS_CLASSREF(x)) ? x.ref->name : x.cls->name;
1709         yname = (IS_CLASSREF(y)) ? y.ref->name : y.cls->name;
1710
1711         /* Common case 2: xname == yname, at least one unresolved */
1712     if ((IS_CLASSREF(x) || IS_CLASSREF(y)) && (xname == yname))
1713         {
1714                 /* use the loaded one if any */
1715                 if (!IS_CLASSREF(y))
1716                         x = y;
1717                 goto return_simple_x;
1718     }
1719
1720         /*--------------------------------------------------*/
1721         /* non-trivial cases                                */
1722         /*--------------------------------------------------*/
1723
1724 #ifdef TYPEINFO_VERBOSE
1725         {
1726                 typeinfo dbgx,dbgy;
1727                 fprintf(stderr,"merge_nonarrays:\n");
1728                 fprintf(stderr,"    ");if(IS_CLASSREF(x))fprintf(stderr,"<ref>");utf_fprint_printable_ascii(stderr,xname);fprintf(stderr,"\n");
1729                 fprintf(stderr,"    ");if(IS_CLASSREF(y))fprintf(stderr,"<ref>");utf_fprint_printable_ascii(stderr,yname);fprintf(stderr,"\n");
1730                 fflush(stderr);
1731                 typeinfo_init_class(&dbgx,x);
1732                 dbgx.merged = mergedx;
1733                 typeinfo_init_class(&dbgy,y);
1734                 dbgy.merged = mergedy;
1735                 typeinfo_print(stderr,&dbgx,4);
1736                 fprintf(stderr,"  with:\n");
1737                 typeinfo_print(stderr,&dbgy,4);
1738         }
1739 #endif
1740
1741         TYPEINFO_ASSERT(IS_CLASSREF(x) || (x.cls->state & CLASS_LOADED));
1742         TYPEINFO_ASSERT(IS_CLASSREF(y) || (y.cls->state & CLASS_LOADED));
1743
1744     /* If y is unresolved or an interface, swap x and y. */
1745     if (IS_CLASSREF(y) || (!IS_CLASSREF(x) && y.cls->flags & ACC_INTERFACE))
1746         {
1747         t = x; x = y; y = t;
1748         tmerged = mergedx; mergedx = mergedy; mergedy = tmerged;
1749     }
1750
1751     /* {We know: If only one of x,y is unresolved it is x,} */
1752     /* {         If both x,y are resolved and only one of x,y is an interface it is x.} */
1753
1754         if (IS_CLASSREF(x)) {
1755                 /* {We know: x and y have different class names} */
1756
1757         /* Check if we are merging an unresolved type with java.lang.Object */
1758         if (y.cls == class_java_lang_Object && !mergedy) {
1759             x = y;
1760             goto return_simple_x;
1761         }
1762
1763                 common = class_java_lang_Object;
1764                 goto merge_with_simple_x;
1765         }
1766
1767         /* {We know: both x and y are resolved} */
1768     /* {We know: If only one of x,y is an interface it is x.} */
1769
1770         TYPEINFO_ASSERT(!IS_CLASSREF(x) && !IS_CLASSREF(y));
1771         TYPEINFO_ASSERT(x.cls->state & CLASS_LOADED);
1772         TYPEINFO_ASSERT(y.cls->state & CLASS_LOADED);
1773
1774     /* Handle merging of interfaces: */
1775     if (x.cls->flags & ACC_INTERFACE) {
1776         /* {x.cls is an interface and mergedx == NULL.} */
1777
1778         if (y.cls->flags & ACC_INTERFACE) {
1779             /* We are merging two interfaces. */
1780             /* {mergedy == NULL} */
1781
1782             /* {We know that x.cls!=y.cls (see common case at beginning.)} */
1783             result->cls = class_java_lang_Object;
1784             return typeinfo_merge_two(dest,x,y);
1785         }
1786
1787         /* {We know: x is an interface, y is a class.} */
1788
1789         /* Check if we are merging an interface with java.lang.Object */
1790         if (y.cls == class_java_lang_Object && !mergedy) {
1791             x = y;
1792             goto return_simple_x;
1793         }
1794
1795         /* If the type y implements x then the result of the merge
1796          * is x regardless of mergedy.
1797          */
1798
1799                 /* we may have to link the classes */
1800                 if (!(x.cls->state & CLASS_LINKED))
1801                         if (!link_class(x.cls))
1802                                 return typecheck_FAIL;
1803                 if (!(y.cls->state & CLASS_LINKED))
1804                         if (!link_class(y.cls))
1805                                 return typecheck_FAIL;
1806
1807                 TYPEINFO_ASSERT(x.cls->state & CLASS_LINKED);
1808                 TYPEINFO_ASSERT(y.cls->state & CLASS_LINKED);
1809
1810         if (CLASSINFO_IMPLEMENTS_INTERFACE(y.cls,x.cls->index))
1811                 {
1812             /* y implements x, so the result of the merge is x. */
1813             goto return_simple_x;
1814                 }
1815
1816         r = mergedlist_implements_interface(mergedy,x.cls);
1817                 if (r == typecheck_FAIL)
1818                         return r;
1819                 if (r == typecheck_TRUE)
1820         {
1821             /* y implements x, so the result of the merge is x. */
1822             goto return_simple_x;
1823         }
1824
1825         /* {We know: x is an interface, the type y a class or a merge
1826          * of subclasses and is not guaranteed to implement x.} */
1827
1828         common = class_java_lang_Object;
1829         goto merge_with_simple_x;
1830     }
1831
1832     /* {We know: x and y are classes (not interfaces).} */
1833
1834         /* we may have to link the classes */
1835         if (!(x.cls->state & CLASS_LINKED))
1836                 if (!link_class(x.cls))
1837                         return typecheck_FAIL;
1838         if (!(y.cls->state & CLASS_LINKED))
1839                 if (!link_class(y.cls))
1840                         return typecheck_FAIL;
1841
1842         TYPEINFO_ASSERT(x.cls->state & CLASS_LINKED);
1843         TYPEINFO_ASSERT(y.cls->state & CLASS_LINKED);
1844
1845     /* If *x is deeper in the inheritance hierarchy swap x and y. */
1846     if (x.cls->index > y.cls->index) {
1847         t = x; x = y; y = t;
1848         tmerged = mergedx; mergedx = mergedy; mergedy = tmerged;
1849     }
1850
1851     /* {We know: y is at least as deep in the hierarchy as x.} */
1852
1853     /* Find nearest common anchestor for the classes. */
1854     common = x.cls;
1855     tcls = y.cls;
1856     while (tcls->index > common->index)
1857         tcls = tcls->super.cls;
1858     while (common != tcls) {
1859         common = common->super.cls;
1860         tcls = tcls->super.cls;
1861     }
1862
1863     /* {common == nearest common anchestor of x and y.} */
1864
1865     /* If x.cls==common and x is a whole class (not a merge of subclasses)
1866      * then the result of the merge is x.
1867      */
1868     if (x.cls == common && !mergedx) {
1869         goto return_simple_x;
1870     }
1871
1872     if (mergedx) {
1873         result->cls = common;
1874         if (mergedy)
1875             return typeinfo_merge_mergedlists(dest,mergedx,mergedy);
1876         else
1877             return typeinfo_merge_add(dest,mergedx,y);
1878     }
1879
1880 merge_with_simple_x:
1881     result->cls = common;
1882     if (mergedy)
1883         return typeinfo_merge_add(dest,mergedy,x);
1884     else
1885         return typeinfo_merge_two(dest,x,y);
1886 }
1887
1888 /* typeinfo_merge **************************************************************
1889
1890    Merge two types.
1891
1892    IN:
1893        m................method for exception messages
1894        dest.............the first type
1895        y................the second type
1896
1897    OUT:
1898        *dest............receives the result of the merge
1899
1900    RETURN VALUE:
1901        typecheck_TRUE...*dest has been modified
1902        typecheck_FALSE..*dest has not been modified
1903        typecheck_FAIL...an exception has been thrown
1904
1905    PRE-CONDITIONS:
1906        1) *dest must be a valid initialized typeinfo
1907        2) dest != y
1908
1909 *******************************************************************************/
1910
1911 typecheck_result
1912 typeinfo_merge(methodinfo *m,typeinfo *dest,typeinfo* y)
1913 {
1914     typeinfo *x;
1915     typeinfo *tmp;
1916     classref_or_classinfo common;
1917     classref_or_classinfo elementclass;
1918     int dimension;
1919     int elementtype;
1920     bool changed;
1921         typecheck_result r;
1922
1923         /*--------------------------------------------------*/
1924         /* fast checks                                      */
1925         /*--------------------------------------------------*/
1926
1927     /* Merging something with itself is a nop */
1928     if (dest == y)
1929         return typecheck_FALSE;
1930
1931     /* Merging two returnAddress types is ok. */
1932         /* Merging two different returnAddresses never happens, as the verifier */
1933         /* keeps them separate in order to check all the possible return paths  */
1934         /* from JSR subroutines.                                                */
1935     if (!dest->typeclass.any && !y->typeclass.any) {
1936                 TYPEINFO_ASSERT(TYPEINFO_RETURNADDRESS(*dest) ==  TYPEINFO_RETURNADDRESS(*y));
1937         return typecheck_FALSE;
1938         }
1939
1940     /* Primitive types cannot be merged with reference types */
1941         /* This must be checked before calls to typeinfo_merge.  */
1942     TYPEINFO_ASSERT(dest->typeclass.any && y->typeclass.any);
1943
1944     /* handle uninitialized object types */
1945     if (TYPEINFO_IS_NEWOBJECT(*dest) || TYPEINFO_IS_NEWOBJECT(*y)) {
1946         if (!TYPEINFO_IS_NEWOBJECT(*dest) || !TYPEINFO_IS_NEWOBJECT(*y)) {
1947             typeinfo_merge_error(m,"Trying to merge uninitialized object type.",dest,y);
1948                         return typecheck_FAIL;
1949                 }
1950         if (TYPEINFO_NEWOBJECT_INSTRUCTION(*dest) != TYPEINFO_NEWOBJECT_INSTRUCTION(*y)) {
1951             typeinfo_merge_error(m,"Trying to merge different uninitialized objects.",dest,y);
1952                         return typecheck_FAIL;
1953                 }
1954                 /* the same uninitialized object -- no change */
1955                 return typecheck_FALSE;
1956     }
1957
1958         /*--------------------------------------------------*/
1959         /* common cases                                     */
1960         /*--------------------------------------------------*/
1961
1962     /* Common case: dest and y are the same class or class reference */
1963     /* (This case is very simple unless *both* dest and y really represent
1964      *  merges of subclasses of class dest==class y.)
1965      */
1966     if ((dest->typeclass.any == y->typeclass.any) && (!dest->merged || !y->merged)) {
1967 return_simple:
1968         changed = (dest->merged != NULL);
1969         TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1970         dest->merged = NULL;
1971         return changed;
1972     }
1973
1974     /* Handle null types: */
1975     if (TYPEINFO_IS_NULLTYPE(*y)) {
1976         return typecheck_FALSE;
1977     }
1978     if (TYPEINFO_IS_NULLTYPE(*dest)) {
1979         TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1980         TYPEINFO_CLONE(*y,*dest);
1981         return typecheck_TRUE;
1982     }
1983
1984         /* Common case: two types with the same name, at least one unresolved */
1985         if (IS_CLASSREF(dest->typeclass)) {
1986                 if (IS_CLASSREF(y->typeclass)) {
1987                         if (dest->typeclass.ref->name == y->typeclass.ref->name)
1988                                 goto return_simple;
1989                 }
1990                 else {
1991                         /* XXX should we take y instead of dest here? */
1992                         if (dest->typeclass.ref->name == y->typeclass.cls->name)
1993                                 goto return_simple;
1994                 }
1995         }
1996         else {
1997                 if (IS_CLASSREF(y->typeclass)
1998                     && (dest->typeclass.cls->name == y->typeclass.ref->name))
1999                 {
2000                         goto return_simple;
2001                 }
2002         }
2003
2004         /*--------------------------------------------------*/
2005         /* non-trivial cases                                */
2006         /*--------------------------------------------------*/
2007
2008 #ifdef TYPEINFO_VERBOSE
2009         fprintf(stderr,"merge:\n");
2010     typeinfo_print(stderr,dest,4);
2011     typeinfo_print(stderr,y,4);
2012 #endif
2013
2014     /* This function uses x internally, so x and y can be swapped
2015      * without changing dest. */
2016     x = dest;
2017     changed = false;
2018
2019     /* Handle merging of arrays: */
2020     if (TYPEINFO_IS_ARRAY(*x) && TYPEINFO_IS_ARRAY(*y)) {
2021
2022         /* Make x the one with lesser dimension */
2023         if (x->dimension > y->dimension) {
2024             tmp = x; x = y; y = tmp;
2025         }
2026
2027         /* If one array (y) has higher dimension than the other,
2028          * interpret it as an array (same dim. as x) of Arraystubs. */
2029         if (x->dimension < y->dimension) {
2030             dimension = x->dimension;
2031             elementtype = ARRAYTYPE_OBJECT;
2032             elementclass.cls = pseudo_class_Arraystub;
2033         }
2034         else {
2035             dimension = y->dimension;
2036             elementtype = y->elementtype;
2037             elementclass = y->elementclass;
2038         }
2039
2040         /* {The arrays are of the same dimension.} */
2041
2042         if (x->elementtype != elementtype) {
2043             /* Different element types are merged, so the resulting array
2044              * type has one accessible dimension less. */
2045             if (--dimension == 0) {
2046                 common.cls = pseudo_class_Arraystub;
2047                 elementtype = 0;
2048                 elementclass.any = NULL;
2049             }
2050             else {
2051                 common.cls = class_multiarray_of(dimension,pseudo_class_Arraystub,true);
2052                                 if (!common.cls) {
2053                                         exceptions_throw_internalerror("XXX Coult not create array class");
2054                                         return typecheck_FAIL;
2055                                 }
2056
2057                 elementtype = ARRAYTYPE_OBJECT;
2058                 elementclass.cls = pseudo_class_Arraystub;
2059             }
2060         }
2061         else {
2062             /* {The arrays have the same dimension and elementtype.} */
2063
2064             if (elementtype == ARRAYTYPE_OBJECT) {
2065                 /* The elements are references, so their respective
2066                  * types must be merged.
2067                  */
2068                                 r = typeinfo_merge_nonarrays(dest,
2069                                                 &elementclass,
2070                                                 x->elementclass,
2071                                                 elementclass,
2072                                                 x->merged,y->merged);
2073                                 TYPEINFO_ASSERT(r != typecheck_MAYBE);
2074                                 if (r == typecheck_FAIL)
2075                                         return r;
2076                                 changed |= r;
2077
2078                 /* DEBUG */ /* log_text("finding resulting array class: "); */
2079                                 if (IS_CLASSREF(elementclass))
2080                                         common.ref = class_get_classref_multiarray_of(dimension,elementclass.ref);
2081                                 else {
2082                                         common.cls = class_multiarray_of(dimension,elementclass.cls,true);
2083                                         if (!common.cls) {
2084                                                 exceptions_throw_internalerror("XXX Coult not create array class");
2085                                                 return typecheck_FAIL;
2086                                         }
2087                                 }
2088                 /* DEBUG */ /* utf_display_printable_ascii(common->name); printf("\n"); */
2089             }
2090                         else {
2091                                 common.any = y->typeclass.any;
2092                         }
2093         }
2094     }
2095     else {
2096         /* {We know that at least one of x or y is no array, so the
2097          *  result cannot be an array.} */
2098
2099                 r = typeinfo_merge_nonarrays(dest,
2100                                 &common,
2101                                 x->typeclass,y->typeclass,
2102                                 x->merged,y->merged);
2103                 TYPEINFO_ASSERT(r != typecheck_MAYBE);
2104                 if (r == typecheck_FAIL)
2105                         return r;
2106                 changed |= r;
2107
2108         dimension = 0;
2109         elementtype = 0;
2110         elementclass.any = NULL;
2111     }
2112
2113     /* Put the new values into dest if neccessary. */
2114
2115     if (dest->typeclass.any != common.any) {
2116         dest->typeclass.any = common.any;
2117         changed = true;
2118     }
2119     if (dest->dimension != dimension) {
2120         dest->dimension = dimension;
2121         changed = true;
2122     }
2123     if (dest->elementtype != elementtype) {
2124         dest->elementtype = elementtype;
2125         changed = true;
2126     }
2127     if (dest->elementclass.any != elementclass.any) {
2128         dest->elementclass.any = elementclass.any;
2129         changed = true;
2130     }
2131
2132     return changed;
2133 }
2134 #endif /* ENABLE_VERIFER */
2135
2136
2137 /**********************************************************************/
2138 /* DEBUGGING HELPERS                                                  */
2139 /**********************************************************************/
2140
2141 #ifdef TYPEINFO_DEBUG
2142
2143 #if 0
2144 static int
2145 typeinfo_test_compare(classref_or_classinfo *a,classref_or_classinfo *b)
2146 {
2147     if (a->any == b->any) return 0;
2148     if (a->any < b->any) return -1;
2149     return +1;
2150 }
2151
2152 static void
2153 typeinfo_test_parse(typeinfo *info,char *str)
2154 {
2155     int num;
2156     int i;
2157     typeinfo *infobuf;
2158     u1 *typebuf;
2159     int returntype;
2160     utf *desc = utf_new_char(str);
2161
2162     num = typeinfo_count_method_args(desc,false);
2163     if (num) {
2164         typebuf = DMNEW(u1,num);
2165         infobuf = DMNEW(typeinfo,num);
2166
2167         typeinfo_init_from_method_args(desc,typebuf,infobuf,num,false,
2168                                        &returntype,info);
2169
2170         TYPEINFO_ALLOCMERGED(info->merged,num);
2171         info->merged->count = num;
2172
2173         for (i=0; i<num; ++i) {
2174             if (typebuf[i] != TYPE_ADR) {
2175                 log_text("non-reference type in mergedlist");
2176                                 assert(0);
2177                         }
2178
2179             info->merged->list[i].any = infobuf[i].typeclass.any;
2180         }
2181         qsort(info->merged->list,num,sizeof(classref_or_classinfo),
2182               (int(*)(const void *,const void *))&typeinfo_test_compare);
2183     }
2184     else {
2185         typeinfo_init_from_method_args(desc,NULL,NULL,0,false,
2186                                        &returntype,info);
2187     }
2188 }
2189 #endif
2190
2191 #define TYPEINFO_TEST_BUFLEN  4000
2192
2193 static bool
2194 typeinfo_equal(typeinfo *x,typeinfo *y)
2195 {
2196     int i;
2197
2198     if (x->typeclass.any != y->typeclass.any) return false;
2199     if (x->dimension != y->dimension) return false;
2200     if (x->dimension) {
2201         if (x->elementclass.any != y->elementclass.any) return false;
2202         if (x->elementtype != y->elementtype) return false;
2203     }
2204
2205     if (TYPEINFO_IS_NEWOBJECT(*x))
2206         if (TYPEINFO_NEWOBJECT_INSTRUCTION(*x)
2207             != TYPEINFO_NEWOBJECT_INSTRUCTION(*y))
2208             return false;
2209
2210     if (x->merged || y->merged) {
2211         if (!(x->merged && y->merged)) return false;
2212         if (x->merged->count != y->merged->count) return false;
2213         for (i=0; i<x->merged->count; ++i)
2214             if (x->merged->list[i].any != y->merged->list[i].any)
2215                 return false;
2216     }
2217     return true;
2218 }
2219
2220 static void
2221 typeinfo_testmerge(typeinfo *a,typeinfo *b,typeinfo *result,int *failed)
2222 {
2223     typeinfo dest;
2224     bool changed,changed_should_be;
2225         typecheck_result r;
2226
2227     TYPEINFO_CLONE(*a,dest);
2228
2229     printf("\n          ");
2230     typeinfo_print_short(stdout,&dest);
2231     printf("\n          ");
2232     typeinfo_print_short(stdout,b);
2233     printf("\n");
2234
2235         r = typeinfo_merge(NULL,&dest,b);
2236         if (r == typecheck_FAIL) {
2237                 printf("EXCEPTION\n");
2238                 return;
2239         }
2240     changed = (r) ? 1 : 0;
2241     changed_should_be = (!typeinfo_equal(&dest,a)) ? 1 : 0;
2242
2243     printf("          %s\n",(changed) ? "changed" : "=");
2244
2245     if (typeinfo_equal(&dest,result)) {
2246         printf("OK        ");
2247         typeinfo_print_short(stdout,&dest);
2248         printf("\n");
2249         if (changed != changed_should_be) {
2250             printf("WRONG RETURN VALUE!\n");
2251             (*failed)++;
2252         }
2253     }
2254     else {
2255         printf("RESULT    ");
2256         typeinfo_print_short(stdout,&dest);
2257         printf("\n");
2258         printf("SHOULD BE ");
2259         typeinfo_print_short(stdout,result);
2260         printf("\n");
2261         (*failed)++;
2262     }
2263 }
2264
2265 #if 0
2266 static void
2267 typeinfo_inc_dimension(typeinfo *info)
2268 {
2269     if (info->dimension++ == 0) {
2270         info->elementtype = ARRAYTYPE_OBJECT;
2271         info->elementclass = info->typeclass;
2272     }
2273     info->typeclass = class_array_of(info->typeclass,true);
2274 }
2275 #endif
2276
2277 #define TYPEINFO_TEST_MAXDIM  10
2278
2279 static void
2280 typeinfo_testrun(char *filename)
2281 {
2282     char buf[TYPEINFO_TEST_BUFLEN];
2283     char bufa[TYPEINFO_TEST_BUFLEN];
2284     char bufb[TYPEINFO_TEST_BUFLEN];
2285     char bufc[TYPEINFO_TEST_BUFLEN];
2286     typeinfo a,b,c;
2287     int maxdim;
2288     int failed = 0;
2289     FILE *file = fopen(filename,"rt");
2290         int res;
2291
2292     if (!file) {
2293         log_text("could not open typeinfo test file");
2294                 assert(0);
2295         }
2296
2297     while (fgets(buf,TYPEINFO_TEST_BUFLEN,file)) {
2298         if (buf[0] == '#' || !strlen(buf))
2299             continue;
2300
2301         res = sscanf(buf,"%s\t%s\t%s\n",bufa,bufb,bufc);
2302         if (res != 3 || !strlen(bufa) || !strlen(bufb) || !strlen(bufc)) {
2303             log_text("Invalid line in typeinfo test file (none of empty, comment or test)");
2304                         assert(0);
2305                 }
2306
2307 #if 0
2308         typeinfo_test_parse(&a,bufa);
2309         typeinfo_test_parse(&b,bufb);
2310         typeinfo_test_parse(&c,bufc);
2311 #endif
2312 #if 0
2313         do {
2314 #endif
2315             typeinfo_testmerge(&a,&b,&c,&failed); /* check result */
2316             typeinfo_testmerge(&b,&a,&c,&failed); /* check commutativity */
2317
2318             if (TYPEINFO_IS_NULLTYPE(a)) break;
2319             if (TYPEINFO_IS_NULLTYPE(b)) break;
2320             if (TYPEINFO_IS_NULLTYPE(c)) break;
2321
2322             maxdim = a.dimension;
2323             if (b.dimension > maxdim) maxdim = b.dimension;
2324             if (c.dimension > maxdim) maxdim = c.dimension;
2325
2326 #if 0
2327             if (maxdim < TYPEINFO_TEST_MAXDIM) {
2328                 typeinfo_inc_dimension(&a);
2329                 typeinfo_inc_dimension(&b);
2330                 typeinfo_inc_dimension(&c);
2331             }
2332         } while (maxdim < TYPEINFO_TEST_MAXDIM);
2333 #endif
2334     }
2335
2336     fclose(file);
2337
2338     if (failed) {
2339         fprintf(stderr,"Failed typeinfo_merge tests: %d\n",failed);
2340         log_text("Failed test");
2341                 assert(0);
2342     }
2343 }
2344
2345 void
2346 typeinfo_test()
2347 {
2348     log_text("Running typeinfo test file...");
2349     typeinfo_testrun("typeinfo.tst");
2350     log_text("Finished typeinfo test file.");
2351 }
2352
2353 #if 0
2354 void
2355 typeinfo_init_from_fielddescriptor(typeinfo *info,char *desc)
2356 {
2357     typeinfo_init_from_descriptor(info,desc,desc+strlen(desc));
2358 }
2359 #endif
2360
2361 #define TYPEINFO_MAXINDENT  80
2362
2363 void
2364 typeinfo_print_class(FILE *file,classref_or_classinfo c)
2365 {
2366         /*fprintf(file,"<class %p>",c.any);*/
2367
2368         if (!c.any) {
2369                 fprintf(file,"<null>");
2370         }
2371         else {
2372                 if (IS_CLASSREF(c)) {
2373                         fprintf(file,"<ref>");
2374                         utf_fprint_printable_ascii(file,c.ref->name);
2375                 }
2376                 else {
2377                         utf_fprint_printable_ascii(file,c.cls->name);
2378                 }
2379         }
2380 }
2381
2382 void
2383 typeinfo_print(FILE *file,typeinfo *info,int indent)
2384 {
2385     int i;
2386     char ind[TYPEINFO_MAXINDENT + 1];
2387     instruction *ins;
2388         basicblock *bptr;
2389
2390     if (indent > TYPEINFO_MAXINDENT) indent = TYPEINFO_MAXINDENT;
2391
2392     for (i=0; i<indent; ++i)
2393         ind[i] = ' ';
2394     ind[i] = (char) 0;
2395
2396     if (TYPEINFO_IS_PRIMITIVE(*info)) {
2397                 bptr = (basicblock*) TYPEINFO_RETURNADDRESS(*info);
2398                 if (bptr)
2399                         fprintf(file,"%sreturnAddress (L%03d)\n",ind,bptr->nr);
2400                 else
2401                         fprintf(file,"%sprimitive\n",ind);
2402         return;
2403     }
2404
2405     if (TYPEINFO_IS_NULLTYPE(*info)) {
2406         fprintf(file,"%snull\n",ind);
2407         return;
2408     }
2409
2410     if (TYPEINFO_IS_NEWOBJECT(*info)) {
2411         ins = (instruction *) TYPEINFO_NEWOBJECT_INSTRUCTION(*info);
2412         if (ins) {
2413             fprintf(file,"%sNEW(%p):",ind,(void*)ins);
2414                         typeinfo_print_class(file,ins[-1].sx.val.c);
2415             fprintf(file,"\n");
2416         }
2417         else {
2418             fprintf(file,"%sNEW(this)",ind);
2419         }
2420         return;
2421     }
2422
2423     fprintf(file,"%sClass:      ",ind);
2424         typeinfo_print_class(file,info->typeclass);
2425     fprintf(file,"\n");
2426
2427     if (TYPEINFO_IS_ARRAY(*info)) {
2428         fprintf(file,"%sDimension:    %d",ind,(int)info->dimension);
2429         fprintf(file,"\n%sElements:     ",ind);
2430         switch (info->elementtype) {
2431           case ARRAYTYPE_INT     : fprintf(file,"int\n"); break;
2432           case ARRAYTYPE_LONG    : fprintf(file,"long\n"); break;
2433           case ARRAYTYPE_FLOAT   : fprintf(file,"float\n"); break;
2434           case ARRAYTYPE_DOUBLE  : fprintf(file,"double\n"); break;
2435           case ARRAYTYPE_BYTE    : fprintf(file,"byte\n"); break;
2436           case ARRAYTYPE_CHAR    : fprintf(file,"char\n"); break;
2437           case ARRAYTYPE_SHORT   : fprintf(file,"short\n"); break;
2438           case ARRAYTYPE_BOOLEAN : fprintf(file,"boolean\n"); break;
2439
2440           case ARRAYTYPE_OBJECT:
2441                           typeinfo_print_class(file,info->elementclass);
2442               fprintf(file,"\n");
2443               break;
2444
2445           default:
2446               fprintf(file,"INVALID ARRAYTYPE!\n");
2447         }
2448     }
2449
2450     if (info->merged) {
2451         fprintf(file,"%sMerged:     ",ind);
2452         for (i=0; i<info->merged->count; ++i) {
2453             if (i) fprintf(file,", ");
2454                         typeinfo_print_class(file,info->merged->list[i]);
2455         }
2456         fprintf(file,"\n");
2457     }
2458 }
2459
2460 void
2461 typeinfo_print_short(FILE *file,typeinfo *info)
2462 {
2463     int i;
2464     instruction *ins;
2465         basicblock *bptr;
2466
2467         /*fprintf(file,"<typeinfo %p>",info);*/
2468
2469         if (!info) {
2470                 fprintf(file,"(typeinfo*)NULL");
2471                 return;
2472         }
2473
2474     if (TYPEINFO_IS_PRIMITIVE(*info)) {
2475                 bptr = (basicblock*) TYPEINFO_RETURNADDRESS(*info);
2476                 if (bptr)
2477                         fprintf(file,"ret(L%03d)",bptr->nr);
2478                 else
2479                         fprintf(file,"primitive");
2480         return;
2481     }
2482
2483     if (TYPEINFO_IS_NULLTYPE(*info)) {
2484         fprintf(file,"null");
2485         return;
2486     }
2487
2488     if (TYPEINFO_IS_NEWOBJECT(*info)) {
2489         ins = (instruction *) TYPEINFO_NEWOBJECT_INSTRUCTION(*info);
2490         if (ins) {
2491                         /*fprintf(file,"<ins %p>",ins);*/
2492             fprintf(file,"NEW(%p):",(void*)ins);
2493                         typeinfo_print_class(file,ins[-1].sx.val.c);
2494         }
2495         else
2496             fprintf(file,"NEW(this)");
2497         return;
2498     }
2499
2500     typeinfo_print_class(file,info->typeclass);
2501
2502     if (info->merged) {
2503         fprintf(file,"{");
2504         for (i=0; i<info->merged->count; ++i) {
2505             if (i) fprintf(file,",");
2506                         typeinfo_print_class(file,info->merged->list[i]);
2507         }
2508         fprintf(file,"}");
2509     }
2510 }
2511
2512 void
2513 typeinfo_print_type(FILE *file,int type,typeinfo *info)
2514 {
2515     switch (type) {
2516       case TYPE_VOID: fprintf(file,"V"); break;
2517       case TYPE_INT:  fprintf(file,"I"); break;
2518       case TYPE_FLT:  fprintf(file,"F"); break;
2519       case TYPE_DBL:  fprintf(file,"D"); break;
2520       case TYPE_LNG:  fprintf(file,"J"); break;
2521           case TYPE_RET:  fprintf(file,"R:"); /* FALLTHROUGH! */
2522       case TYPE_ADR:
2523                   typeinfo_print_short(file,info);
2524           break;
2525
2526       default:
2527           fprintf(file,"!");
2528     }
2529 }
2530
2531 void
2532 typedescriptor_print(FILE *file,typedescriptor *td)
2533 {
2534         typeinfo_print_type(file,td->type,&(td->typeinfo));
2535 }
2536
2537 void
2538 typevector_print(FILE *file,varinfo *vec,int size)
2539 {
2540     int i;
2541
2542     for (i=0; i<size; ++i) {
2543                 fprintf(file," %d=",i);
2544         typeinfo_print_type(file, vec[i].type, &(vec[i].typeinfo));
2545     }
2546 }
2547
2548 #endif /* TYPEINFO_DEBUG */
2549
2550
2551 /*
2552  * These are local overrides for various environment variables in Emacs.
2553  * Please do not remove this and leave it at the end of the file, where
2554  * Emacs will automagically detect them.
2555  * ---------------------------------------------------------------------
2556  * Local variables:
2557  * mode: c
2558  * indent-tabs-mode: t
2559  * c-basic-offset: 4
2560  * tab-width: 4
2561  * End:
2562  * vim:noexpandtab:sw=4:ts=4:
2563  */