src/vm/jit/verify/typeinfo.c

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