src/vm/jit/verify/typeinfo.cpp

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