src/vm/jit/verify/typeinfo.cpp

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