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