src/vm/jit/verify/typeinfo.c

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