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