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 3435 2005-10-13 16:25:56Z 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 (SET) 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 /* typeinfo_is_array ***********************************************************
 683
 684    Check whether a typeinfo describes an array type.
 685
 686    IN:
 687            info.............the typeinfo, must be != NULL
 688
 689    RETURN VALUE:
 690        true if INFO describes an array type.
 691
 692 *******************************************************************************/
 693
 694 bool
 695 typeinfo_is_array(typeinfo *info)
 696 {
 697         TYPEINFO_ASSERT(info);
 698     return TYPEINFO_IS_ARRAY(*info);
 699 }
 700
 701 /* typeinfo_is_primitive_array *************************************************
 702
 703    Check whether a typeinfo describes a primitive array type.
 704
 705    IN:
 706            info.............the typeinfo, must be != NULL
 707
 708    RETURN VALUE:
 709        true if INFO describes an array of a primitive type.
 710
 711 *******************************************************************************/
 712
 713 bool
 714 typeinfo_is_primitive_array(typeinfo *info,int arraytype)
 715 {
 716         TYPEINFO_ASSERT(info);
 717     return TYPEINFO_IS_PRIMITIVE_ARRAY(*info,arraytype);
 718 }
 719
 720 /* typeinfo_is_array_of_refs ***************************************************
 721
 722    Check whether a typeinfo describes an array of references type.
 723
 724    IN:
 725            info.............the typeinfo, must be != NULL
 726
 727    RETURN VALUE:
 728        true if INFO describes an array of a refrence type.
 729
 730 *******************************************************************************/
 731
 732 bool
 733 typeinfo_is_array_of_refs(typeinfo *info)
 734 {
 735         TYPEINFO_ASSERT(info);
 736     return TYPEINFO_IS_ARRAY_OF_REFS(*info);
 737 }
 738
 739 /* interface_extends_interface *************************************************
 740
 741    Check if a resolved interface extends a given resolved interface.
 742
 743    IN:
 744            cls..............the interface, must be linked
 745            interf...........the interface to check against
 746
 747    RETURN VALUE:
 748        true.............CLS extends INTERF
 749            false............CLS does not extend INTERF
 750
 751 *******************************************************************************/
 752
 753 static bool
 754 interface_extends_interface(classinfo *cls,classinfo *interf)
 755 {
 756     int i;
 757
 758         TYPEINFO_ASSERT(cls);
 759         TYPEINFO_ASSERT(interf);
 760         TYPEINFO_ASSERT((interf->flags & ACC_INTERFACE) != 0);
 761         TYPEINFO_ASSERT((cls->flags & ACC_INTERFACE) != 0);
 762         TYPEINFO_ASSERT(cls->linked);
 763
 764     /* first check direct superinterfaces */
 765     for (i=0; i<cls->interfacescount; ++i) {
 766         if (cls->interfaces[i].cls == interf)
 767             return true;
 768     }
 769
 770     /* check indirect superinterfaces */
 771     for (i=0; i<cls->interfacescount; ++i) {
 772         if (interface_extends_interface(cls->interfaces[i].cls,interf))
 773             return true;
 774     }
 775
 776     return false;
 777 }
 778
 779 /* classinfo_implements_interface **********************************************
 780
 781    Check if a resolved class implements a given resolved interface.
 782
 783    IN:
 784            cls..............the class
 785            interf...........the interface
 786
 787    RETURN VALUE:
 788        typecheck_TRUE...CLS implements INTERF
 789            typecheck_FALSE..CLS does not implement INTERF
 790            typecheck_FAIL...an exception has been thrown
 791
 792 *******************************************************************************/
 793
 794 static typecheck_result
 795 classinfo_implements_interface(classinfo *cls,classinfo *interf)
 796 {
 797         TYPEINFO_ASSERT(cls);
 798         TYPEINFO_ASSERT(interf);
 799         TYPEINFO_ASSERT((interf->flags & ACC_INTERFACE) != 0);
 800
 801         if (!cls->linked)
 802                 if (!link_class(cls))
 803                         return typecheck_FAIL;
 804
 805     if (cls->flags & ACC_INTERFACE) {
 806         /* cls is an interface */
 807         if (cls == interf)
 808             return typecheck_TRUE;
 809
 810         /* check superinterfaces */
 811         return interface_extends_interface(cls,interf);
 812     }
 813
 814         TYPEINFO_ASSERT(cls->linked);
 815     return CLASSINFO_IMPLEMENTS_INTERFACE(cls,interf->index);
 816 }
 817
 818 /* mergedlist_implements_interface *********************************************
 819
 820    Check if all the classes in a given merged list implement a given resolved
 821    interface.
 822
 823    IN:
 824            merged...........the list of merged class types
 825            interf...........the interface to check against
 826
 827    RETURN VALUE:
 828        typecheck_TRUE...all classes implement INTERF
 829            typecheck_FALSE..there is at least one class that does not implement
 830                             INTERF
 831            typecheck_MAYBE..check cannot be performed now because of unresolved
 832                             classes
 833            typecheck_FAIL...an exception has been thrown
 834
 835 *******************************************************************************/
 836
 837 static typecheck_result
 838 mergedlist_implements_interface(typeinfo_mergedlist *merged,
 839                                 classinfo *interf)
 840 {
 841     int i;
 842     classref_or_classinfo *mlist;
 843         typecheck_result r;
 844
 845         TYPEINFO_ASSERT(interf);
 846         TYPEINFO_ASSERT((interf->flags & ACC_INTERFACE) != 0);
 847
 848     /* Check if there is an non-empty mergedlist. */
 849     if (!merged)
 850         return typecheck_FALSE;
 851
 852     /* If all classinfos in the (non-empty) merged array implement the
 853      * interface return true, otherwise false.
 854      */
 855     mlist = merged->list;
 856     i = merged->count;
 857     while (i--) {
 858                 if (IS_CLASSREF(*mlist)) {
 859                         return typecheck_MAYBE;
 860                 }
 861         r = classinfo_implements_interface((mlist++)->cls,interf);
 862         if (r != typecheck_TRUE)
 863                         return r;
 864     }
 865     return typecheck_TRUE;
 866 }
 867
 868 /* merged_implements_interface *************************************************
 869
 870    Check if a possible merged type implements a given resolved interface
 871    interface.
 872
 873    IN:
 874        typeclass........(common) class of the (merged) type
 875            merged...........the list of merged class types
 876            interf...........the interface to check against
 877
 878    RETURN VALUE:
 879        typecheck_TRUE...the type implement INTERF
 880            typecheck_FALSE..the type does not implement INTERF
 881            typecheck_MAYBE..check cannot be performed now because of unresolved
 882                             classes
 883            typecheck_FAIL...an exception has been thrown
 884
 885 *******************************************************************************/
 886
 887 static typecheck_result
 888 merged_implements_interface(classinfo *typeclass,typeinfo_mergedlist *merged,
 889                             classinfo *interf)
 890 {
 891         typecheck_result r;
 892
 893     /* primitive types don't support interfaces. */
 894     if (!typeclass)
 895         return typecheck_FALSE;
 896
 897     /* the null type can be cast to any interface type. */
 898     if (typeclass == pseudo_class_Null)
 899         return typecheck_TRUE;
 900
 901     /* check if typeclass implements the interface. */
 902     r = classinfo_implements_interface(typeclass,interf);
 903         if (r != typecheck_FALSE)
 904         return r;
 905
 906     /* check the mergedlist */
 907         if (!merged)
 908                 return typecheck_FALSE;
 909     return mergedlist_implements_interface(merged,interf);
 910 }
 911
 912 /* merged_is_subclass **********************************************************
 913
 914    Check if a possible merged type is a subclass of a given class.
 915    A merged type is a subclass of a class C if all types in the merged list
 916    are subclasses of C. A sufficient condition for this is that the
 917    common type of the merged type is a subclass of C.
 918
 919    IN:
 920        typeclass........(common) class of the (merged) type
 921                             MUST be a loaded and linked class
 922            merged...........the list of merged class types
 923            cls..............the class to theck against
 924
 925    RETURN VALUE:
 926        typecheck_TRUE...the type is a subclass of CLS
 927            typecheck_FALSE..the type is not a subclass of CLS
 928            typecheck_MAYBE..check cannot be performed now because of unresolved
 929                             classes
 930            typecheck_FAIL...an exception has been thrown
 931
 932 *******************************************************************************/
 933
 934 static typecheck_result
 935 merged_is_subclass(classinfo *typeclass,typeinfo_mergedlist *merged,
 936                 classinfo *cls)
 937 {
 938     int i;
 939     classref_or_classinfo *mlist;
 940
 941         TYPEINFO_ASSERT(cls);
 942
 943     /* primitive types aren't subclasses of anything. */
 944     if (!typeclass)
 945         return typecheck_FALSE;
 946
 947     /* the null type can be cast to any reference type. */
 948     if (typeclass == pseudo_class_Null)
 949         return typecheck_TRUE;
 950
 951         TYPEINFO_ASSERT(typeclass->loaded);
 952         TYPEINFO_ASSERT(typeclass->linked);
 953
 954     /* check if the common typeclass is a subclass of CLS. */
 955         if (class_issubclass(typeclass,cls))
 956                 return typecheck_TRUE;
 957
 958     /* check the mergedlist */
 959         if (!merged)
 960                 return typecheck_FALSE;
 961     /* If all classinfos in the (non-empty) merged list are subclasses
 962          * of CLS, return true, otherwise false.
 963          * If there is at least one unresolved type in the list,
 964          * return typecheck_MAYBE.
 965      */
 966     mlist = merged->list;
 967     i = merged->count;
 968     while (i--) {
 969                 if (IS_CLASSREF(*mlist)) {
 970                         return typecheck_MAYBE;
 971                 }
 972                 if (!mlist->cls->linked)
 973                         if (!link_class(mlist->cls))
 974                                 return typecheck_FAIL;
 975                 if (!class_issubclass(mlist->cls,cls))
 976                         return typecheck_FALSE;
 977                 mlist++;
 978     }
 979     return typecheck_TRUE;
 980 }
 981
 982 /* typeinfo_is_assignable_to_class *********************************************
 983
 984    Check if a type is assignable to a given class type.
 985
 986    IN:
 987        value............the type of the value
 988            dest.............the type of the destination
 989
 990    RETURN VALUE:
 991        typecheck_TRUE...the type is assignable
 992            typecheck_FALSE..the type is not assignable
 993            typecheck_MAYBE..check cannot be performed now because of unresolved
 994                             classes
 995            typecheck_FAIL...an exception has been thrown
 996
 997 *******************************************************************************/
 998
 999 typecheck_result
1000 typeinfo_is_assignable_to_class(typeinfo *value,classref_or_classinfo dest)
1001 {
1002         classref_or_classinfo c;
1003     classinfo *cls;
1004         utf *classname;
1005
1006         TYPEINFO_ASSERT(value);
1007
1008     c = value->typeclass;
1009
1010     /* assignments of primitive values are not checked here. */
1011     if (!c.any && !dest.any)
1012         return typecheck_TRUE;
1013
1014     /* primitive and reference types are not assignment compatible. */
1015     if (!c.any || !dest.any)
1016         return typecheck_FALSE;
1017
1018     /* the null type can be assigned to any type */
1019     if (TYPEINFO_IS_NULLTYPE(*value))
1020         return typecheck_TRUE;
1021
1022     /* uninitialized objects are not assignable */
1023     if (TYPEINFO_IS_NEWOBJECT(*value))
1024         return typecheck_FALSE;
1025
1026         if (IS_CLASSREF(c)) {
1027                 /* The value type is an unresolved class reference. */
1028                 classname = c.ref->name;
1029         }
1030         else {
1031                 classname = c.cls->name;
1032         }
1033
1034         if (IS_CLASSREF(dest)) {
1035                 /* the destination type is an unresolved class reference */
1036                 /* In this case we cannot tell a lot about assignability. */
1037
1038                 /* the common case of value and dest type having the same classname */
1039                 if (dest.ref->name == classname && !value->merged)
1040                         return typecheck_TRUE;
1041
1042                 /* we cannot tell if value is assignable to dest, so we */
1043                 /* leave it up to the resolving code to check this      */
1044                 return typecheck_MAYBE;
1045         }
1046
1047         /* { we know that dest is a loaded class } */
1048
1049         if (IS_CLASSREF(c)) {
1050                 /* the value type is an unresolved class reference */
1051
1052                 /* the common case of value and dest type having the same classname */
1053                 if (dest.cls->name == classname)
1054                         return typecheck_TRUE;
1055
1056                 /* we cannot tell if value is assignable to dest, so we */
1057                 /* leave it up to the resolving code to check this      */
1058                 return typecheck_MAYBE;
1059         }
1060
1061         /* { we know that both c and dest are loaded classes } */
1062         /* (c may still have a merged list containing unresolved classrefs!) */
1063
1064         TYPEINFO_ASSERT(!IS_CLASSREF(c));
1065         TYPEINFO_ASSERT(!IS_CLASSREF(dest));
1066
1067         cls = c.cls;
1068
1069         TYPEINFO_ASSERT(cls->loaded);
1070         TYPEINFO_ASSERT(dest.cls->loaded);
1071
1072         /* maybe we need to link the classes */
1073         if (!cls->linked)
1074                 if (!link_class(cls))
1075                         return typecheck_FAIL;
1076         if (!dest.cls->linked)
1077                 if (!link_class(dest.cls))
1078                         return typecheck_FAIL;
1079
1080         /* { we know that both c and dest are linked classes } */
1081         TYPEINFO_ASSERT(cls->linked);
1082         TYPEINFO_ASSERT(dest.cls->linked);
1083
1084     if (dest.cls->flags & ACC_INTERFACE) {
1085         /* We are assigning to an interface type. */
1086         return merged_implements_interface(cls,value->merged,dest.cls);
1087     }
1088
1089     if (CLASSINFO_IS_ARRAY(dest.cls)) {
1090                 arraydescriptor *arraydesc = dest.cls->vftbl->arraydesc;
1091                 int dimension = arraydesc->dimension;
1092                 classinfo *elementclass = (arraydesc->elementvftbl)
1093                         ? arraydesc->elementvftbl->class : NULL;
1094
1095         /* We are assigning to an array type. */
1096         if (!TYPEINFO_IS_ARRAY(*value))
1097             return typecheck_FALSE;
1098
1099         /* {Both value and dest.cls are array types.} */
1100
1101         /* value must have at least the dimension of dest.cls. */
1102         if (value->dimension < dimension)
1103             return typecheck_FALSE;
1104
1105         if (value->dimension > dimension) {
1106             /* value has higher dimension so we need to check
1107              * if its component array can be assigned to the
1108              * element type of dest.cls */
1109
1110                         if (!elementclass) return typecheck_FALSE;
1111
1112             if (elementclass->flags & ACC_INTERFACE) {
1113                 /* We are assigning to an interface type. */
1114                 return classinfo_implements_interface(pseudo_class_Arraystub,
1115                                                       elementclass);
1116             }
1117
1118             /* We are assigning to a class type. */
1119             return class_issubclass(pseudo_class_Arraystub,elementclass);
1120         }
1121
1122         /* {value and dest.cls have the same dimension} */
1123
1124         if (value->elementtype != arraydesc->elementtype)
1125             return typecheck_FALSE;
1126
1127         if (value->elementclass.any) {
1128             /* We are assigning an array of objects so we have to
1129              * check if the elements are assignable.
1130              */
1131
1132             if (elementclass->flags & ACC_INTERFACE) {
1133                 /* We are assigning to an interface type. */
1134
1135                 return merged_implements_interface(value->elementclass.cls,
1136                                                    value->merged,
1137                                                    elementclass);
1138             }
1139
1140             /* We are assigning to a class type. */
1141             return merged_is_subclass(value->elementclass.cls,value->merged,elementclass);
1142         }
1143
1144         return typecheck_TRUE;
1145     }
1146
1147     /* {dest.cls is not an array} */
1148     /* {dest.cls is a loaded class} */
1149
1150         /* If there are any unresolved references in the merged list, we cannot */
1151         /* tell if the assignment will be ok.                                   */
1152         /* This can only happen when cls is java.lang.Object                    */
1153         if (cls == class_java_lang_Object && value->merged) {
1154                 classref_or_classinfo *mlist = value->merged->list;
1155                 int i = value->merged->count;
1156                 while (i--)
1157                         if (IS_CLASSREF(*mlist++))
1158                                 return typecheck_MAYBE;
1159         }
1160
1161     /* We are assigning to a class type */
1162     if (cls->flags & ACC_INTERFACE)
1163         cls = class_java_lang_Object;
1164
1165     return merged_is_subclass(cls,value->merged,dest.cls);
1166 }
1167
1168 /* typeinfo_is_assignable ******************************************************
1169
1170    Check if a type is assignable to a given type.
1171
1172    IN:
1173        value............the type of the value
1174            dest.............the type of the destination, must not be a merged type
1175
1176    RETURN VALUE:
1177        typecheck_TRUE...the type is assignable
1178            typecheck_FALSE..the type is not assignable
1179            typecheck_MAYBE..check cannot be performed now because of unresolved
1180                             classes
1181            typecheck_FAIL...an exception has been thrown
1182
1183 *******************************************************************************/
1184
1185 typecheck_result
1186 typeinfo_is_assignable(typeinfo *value,typeinfo *dest)
1187 {
1188         TYPEINFO_ASSERT(value);
1189         TYPEINFO_ASSERT(dest);
1190         TYPEINFO_ASSERT(dest->merged == NULL);
1191
1192         return typeinfo_is_assignable_to_class(value,dest->typeclass);
1193 }
1194
1195 /**********************************************************************/
1196 /* INITIALIZATION FUNCTIONS                                           */
1197 /* The following functions fill in uninitialized typeinfo structures. */
1198 /**********************************************************************/
1199
1200 /* typeinfo_init_class *********************************************************
1201
1202    Initialize a typeinfo to a possibly unresolved class type.
1203
1204    IN:
1205            c................the class type
1206
1207    OUT:
1208        *info............is initialized
1209
1210    RETURN VALUE:
1211        true.............success
1212            false............an exception has been thrown
1213
1214 *******************************************************************************/
1215
1216 bool
1217 typeinfo_init_class(typeinfo *info,classref_or_classinfo c)
1218 {
1219         char *utf_ptr;
1220         int len;
1221         classinfo *cls;
1222
1223         TYPEINFO_ASSERT(c.any);
1224         TYPEINFO_ASSERT(info);
1225
1226         /* if necessary, try to resolve lazily */
1227         if (!resolve_classref_or_classinfo(NULL /* XXX should now method */,
1228                                 c,resolveLazy,false,true,&cls))
1229         {
1230                 return false;
1231         }
1232
1233         if (cls) {
1234                 TYPEINFO_INIT_CLASSINFO(*info,cls);
1235                 return true;
1236         }
1237
1238         /* {the type could no be resolved lazily} */
1239
1240         info->typeclass.ref = c.ref;
1241         info->elementclass.any = NULL;
1242         info->dimension = 0;
1243         info->merged = NULL;
1244
1245         /* handle array type references */
1246         utf_ptr = c.ref->name->text;
1247         len = c.ref->name->blength;
1248         if (*utf_ptr == '[') {
1249                 /* count dimensions */
1250                 while (*utf_ptr == '[') {
1251                         utf_ptr++;
1252                         info->dimension++;
1253                         len--;
1254                 }
1255                 if (*utf_ptr == 'L') {
1256                         utf_ptr++;
1257                         len -= 2;
1258                         info->elementtype = ARRAYTYPE_OBJECT;
1259                         info->elementclass.ref = class_get_classref(c.ref->referer,utf_new(utf_ptr,len));
1260                 }
1261                 else {
1262                         /* an array with primitive element type */
1263                         /* should have been resolved above */
1264                         TYPEINFO_ASSERT(false);
1265                 }
1266         }
1267         return true;
1268 }
1269
1270 /* typeinfo_init_from_typedesc *************************************************
1271
1272    Initialize a typeinfo from a typedesc.
1273
1274    IN:
1275            desc.............the typedesc
1276
1277    OUT:
1278        *type............set to the TYPE_* constant of DESC (if type != NULL)
1279        *info............receives the typeinfo (if info != NULL)
1280
1281    RETURN VALUE:
1282        true.............success
1283            false............an exception has been thrown
1284
1285 *******************************************************************************/
1286
1287 bool
1288 typeinfo_init_from_typedesc(typedesc *desc,u1 *type,typeinfo *info)
1289 {
1290         TYPEINFO_ASSERT(desc);
1291
1292 #ifdef TYPEINFO_VERBOSE
1293         fprintf(stderr,"typeinfo_init_from_typedesc(");
1294         descriptor_debug_print_typedesc(stderr,desc);
1295         fprintf(stderr,")\n");
1296 #endif
1297
1298         if (type)
1299                 *type = desc->type;
1300
1301         if (info) {
1302                 if (desc->type == TYPE_ADR) {
1303                         TYPEINFO_ASSERT(desc->classref);
1304                         if (!typeinfo_init_class(info,CLASSREF_OR_CLASSINFO(desc->classref)))
1305                                 return false;
1306                 }
1307                 else {
1308                         TYPEINFO_INIT_PRIMITIVE(*info);
1309                 }
1310         }
1311         return true;
1312 }
1313
1314 /* typeinfos_init_from_methoddesc **********************************************
1315
1316    Initialize an array of typeinfos and u1 TYPE_* values from a methoddesc.
1317
1318    IN:
1319        desc.............the methoddesc
1320        buflen...........number of parameters the buffer can hold
1321        twoword..........if true, use two parameter slots for two-word types
1322
1323    OUT:
1324        *typebuf.........receives a TYPE_* constant for each parameter
1325                         typebuf must be != NULL
1326        *infobuf.........receives a typeinfo for each parameter
1327                         infobuf must be != NULL
1328        *returntype......receives a TYPE_* constant for the return type
1329                         returntype may be NULL
1330        *returntypeinfo..receives a typeinfo for the return type
1331                         returntypeinfo may be NULL
1332
1333    RETURN VALUE:
1334        true.............success
1335        false............an exception has been thrown
1336
1337    NOTE:
1338        If (according to BUFLEN) the buffers are to small to hold the
1339            parameter types, an internal error is thrown. This must be
1340            avoided by checking the number of parameters and allocating enough
1341            space before calling this function.
1342
1343 *******************************************************************************/
1344
1345 bool
1346 typeinfos_init_from_methoddesc(methoddesc *desc,u1 *typebuf,typeinfo *infobuf,
1347                               int buflen,bool twoword,
1348                               u1 *returntype,typeinfo *returntypeinfo)
1349 {
1350         int i;
1351     int args = 0;
1352
1353         TYPEINFO_ASSERT(desc);
1354         TYPEINFO_ASSERT(typebuf);
1355         TYPEINFO_ASSERT(infobuf);
1356
1357 #ifdef TYPEINFO_VERBOSE
1358         fprintf(stderr,"typeinfos_init_from_methoddesc(");
1359         descriptor_debug_print_methoddesc(stderr,desc);
1360         fprintf(stderr,")\n");
1361 #endif
1362
1363     /* check arguments */
1364     for (i=0; i<desc->paramcount; ++i) {
1365                 if (++args > buflen) {
1366                         *exceptionptr = new_internalerror("Buffer too small for method arguments.");
1367                         return false;
1368                 }
1369
1370                 if (!typeinfo_init_from_typedesc(desc->paramtypes + i,typebuf++,infobuf++))
1371                         return false;
1372
1373                 if (twoword && (typebuf[-1] == TYPE_LONG || typebuf[-1] == TYPE_DOUBLE)) {
1374                         if (++args > buflen) {
1375                                 *exceptionptr = new_internalerror("Buffer too small for method arguments.");
1376                                 return false;
1377                         }
1378
1379                         *typebuf++ = TYPE_VOID;
1380                         TYPEINFO_INIT_PRIMITIVE(*infobuf);
1381                         infobuf++;
1382                 }
1383     }
1384
1385     /* check returntype */
1386     if (returntype) {
1387                 if (!typeinfo_init_from_typedesc(&(desc->returntype),returntype,returntypeinfo))
1388                         return false;
1389         }
1390
1391         return true;
1392 }
1393
1394 /* typedescriptor_init_from_typedesc *******************************************
1395
1396    Initialize a typedescriptor from a typedesc.
1397
1398    IN:
1399            desc.............the typedesc
1400
1401    OUT:
1402        *td..............receives the typedescriptor
1403                             td must be != NULL
1404
1405    RETURN VALUE:
1406        true.............success
1407            false............an exception has been thrown
1408
1409 *******************************************************************************/
1410
1411 bool
1412 typedescriptor_init_from_typedesc(typedescriptor *td,
1413                                                                   typedesc *desc)
1414 {
1415         TYPEINFO_ASSERT(td);
1416         TYPEINFO_ASSERT(desc);
1417
1418         td->type = desc->type;
1419         if (td->type == TYPE_ADR) {
1420                 if (!typeinfo_init_class(&(td->info),CLASSREF_OR_CLASSINFO(desc->classref)))
1421                         return false;
1422         }
1423         else {
1424                 TYPEINFO_INIT_PRIMITIVE(td->info);
1425         }
1426         return true;
1427 }
1428
1429 /* typedescriptors_init_from_methoddesc ****************************************
1430
1431    Initialize an array of typedescriptors from a methoddesc.
1432
1433    IN:
1434        desc.............the methoddesc
1435        buflen...........number of parameters the buffer can hold
1436        twoword..........if true, use two parameter slots for two-word types
1437            startindex.......the zero-based index of the first parameter to
1438                             write to the array. In other words the number of
1439                                                 parameters to skip at the beginning of the methoddesc.
1440
1441    OUT:
1442        *td..............array receiving the typedescriptors.
1443                             td[0] receives the typedescriptor of the
1444                                                 (startindex+1)th parameter of the method
1445        *returntype......receives the typedescriptor of the return type.
1446                             returntype may be NULL
1447
1448    RETURN VALUE:
1449        >= 0.............number of typedescriptors filled in TD
1450            -1...............an exception has been thrown
1451
1452    NOTE:
1453        If (according to BUFLEN) the buffer is to small to hold the
1454            parameter types, an internal error is thrown. This must be
1455            avoided by checking the number of parameters and allocating enough
1456            space before calling this function.
1457
1458 *******************************************************************************/
1459
1460 int
1461 typedescriptors_init_from_methoddesc(typedescriptor *td,
1462                                                                          methoddesc *desc,
1463                                                                          int buflen,bool twoword,int startindex,
1464                                                                          typedescriptor *returntype)
1465 {
1466         int i;
1467     int args = 0;
1468
1469     /* check arguments */
1470     for (i=startindex; i<desc->paramcount; ++i) {
1471                 if (++args > buflen) {
1472                         *exceptionptr = new_internalerror("Buffer too small for method arguments.");
1473                         return -1;
1474                 }
1475
1476                 if (!typedescriptor_init_from_typedesc(td,desc->paramtypes + i))
1477                         return -1;
1478                 td++;
1479
1480                 if (twoword && (td[-1].type == TYPE_LONG || td[-1].type == TYPE_DOUBLE)) {
1481                         if (++args > buflen) {
1482                                 *exceptionptr = new_internalerror("Buffer too small for method arguments.");
1483                                 return -1;
1484                         }
1485
1486                         td->type = TYPE_VOID;
1487                         TYPEINFO_INIT_PRIMITIVE(td->info);
1488                         td++;
1489                 }
1490     }
1491
1492     /* check returntype */
1493     if (returntype) {
1494                 if (!typedescriptor_init_from_typedesc(returntype,&(desc->returntype)))
1495                         return -1;
1496         }
1497
1498         return args;
1499 }
1500
1501 /* typeinfo_init_component *****************************************************
1502
1503    Initialize a typeinfo with the component type of a given array type.
1504
1505    IN:
1506            srcarray.........the typeinfo of the array type
1507
1508    OUT:
1509        *dst.............receives the typeinfo of the component type
1510
1511    RETURN VALUE:
1512        true.............success
1513            false............an exception has been thrown
1514
1515 *******************************************************************************/
1516
1517 bool
1518 typeinfo_init_component(typeinfo *srcarray,typeinfo *dst)
1519 {
1520         TYPEINFO_ASSERT(srcarray);
1521         TYPEINFO_ASSERT(dst);
1522
1523     if (TYPEINFO_IS_NULLTYPE(*srcarray)) {
1524         TYPEINFO_INIT_NULLTYPE(*dst);
1525         return true;
1526     }
1527
1528     if (!TYPEINFO_IS_ARRAY(*srcarray)) {
1529                 /* XXX should we make that a verify error? */
1530                 *exceptionptr = new_internalerror("Trying to access component of non-array");
1531                 return false;
1532         }
1533
1534         if (IS_CLASSREF(srcarray->typeclass)) {
1535                 constant_classref *comp;
1536                 comp = class_get_classref_component_of(srcarray->typeclass.ref);
1537
1538                 if (comp) {
1539                         if (!typeinfo_init_class(dst,CLASSREF_OR_CLASSINFO(comp)))
1540                                 return false;
1541                 }
1542                 else {
1543                         TYPEINFO_INIT_PRIMITIVE(*dst);
1544                 }
1545         }
1546         else {
1547                 vftbl_t *comp;
1548
1549                 if (!srcarray->typeclass.cls->linked) {
1550                         if (!link_class(srcarray->typeclass.cls)) {
1551                                 return false;
1552                         }
1553                 }
1554
1555                 TYPEINFO_ASSERT(srcarray->typeclass.cls->vftbl);
1556                 TYPEINFO_ASSERT(srcarray->typeclass.cls->vftbl->arraydesc);
1557
1558                 comp = srcarray->typeclass.cls->vftbl->arraydesc->componentvftbl;
1559                 if (comp)
1560                         TYPEINFO_INIT_CLASSINFO(*dst,comp->class);
1561                 else
1562                         TYPEINFO_INIT_PRIMITIVE(*dst);
1563         }
1564
1565     dst->merged = srcarray->merged; /* XXX should we do a deep copy? */
1566         return true;
1567 }
1568
1569 /* typeinfo_clone **************************************************************
1570
1571    Create a deep copy of a typeinfo struct.
1572
1573    IN:
1574            src..............the typeinfo to copy
1575
1576    OUT:
1577        *dest............receives the copy
1578
1579    NOTE:
1580        If src == dest this function is a nop.
1581
1582 *******************************************************************************/
1583
1584 void
1585 typeinfo_clone(typeinfo *src,typeinfo *dest)
1586 {
1587     int count;
1588     classref_or_classinfo *srclist,*destlist;
1589
1590     if (src == dest)
1591         return;
1592
1593     *dest = *src;
1594
1595     if (src->merged) {
1596         count = src->merged->count;
1597         TYPEINFO_ALLOCMERGED(dest->merged,count);
1598         dest->merged->count = count;
1599
1600         srclist = src->merged->list;
1601         destlist = dest->merged->list;
1602         while (count--)
1603             *destlist++ = *srclist++;
1604     }
1605 }
1606
1607 /**********************************************************************/
1608 /* MISCELLANEOUS FUNCTIONS                                            */
1609 /**********************************************************************/
1610
1611 /* typeinfo_free ***************************************************************
1612
1613    Free memory referenced by the given typeinfo. The typeinfo itself is not
1614    freed.
1615
1616    IN:
1617        info.............the typeinfo
1618
1619 *******************************************************************************/
1620
1621 void
1622 typeinfo_free(typeinfo *info)
1623 {
1624     TYPEINFO_FREEMERGED_IF_ANY(info->merged);
1625     info->merged = NULL;
1626 }
1627
1628 /**********************************************************************/
1629 /* MERGING FUNCTIONS                                                  */
1630 /* The following functions are used to merge the types represented by */
1631 /* two typeinfo structures into one typeinfo structure.               */
1632 /**********************************************************************/
1633
1634 static
1635 void
1636 typeinfo_merge_error(methodinfo *m,char *str,typeinfo *x,typeinfo *y) {
1637 #ifdef TYPEINFO_VERBOSE
1638     fprintf(stderr,"Error in typeinfo_merge: %s\n",str);
1639     fprintf(stderr,"Typeinfo x:\n");
1640     typeinfo_print(stderr,x,1);
1641     fprintf(stderr,"Typeinfo y:\n");
1642     typeinfo_print(stderr,y,1);
1643 #endif
1644
1645     log_text(str);
1646         *exceptionptr = new_verifyerror(m,str);
1647 }
1648
1649 /* Condition: clsx != clsy. */
1650 /* Returns: true if dest was changed (currently always true). */
1651 static
1652 bool
1653 typeinfo_merge_two(typeinfo *dest,classref_or_classinfo clsx,classref_or_classinfo clsy)
1654 {
1655         TYPEINFO_ASSERT(dest);
1656     TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1657     TYPEINFO_ALLOCMERGED(dest->merged,2);
1658     dest->merged->count = 2;
1659
1660         TYPEINFO_ASSERT(clsx.any != clsy.any);
1661
1662     if (clsx.any < clsy.any) {
1663         dest->merged->list[0] = clsx;
1664         dest->merged->list[1] = clsy;
1665     }
1666     else {
1667         dest->merged->list[0] = clsy;
1668         dest->merged->list[1] = clsx;
1669     }
1670
1671     return true;
1672 }
1673
1674 /* Returns: true if dest was changed. */
1675 static
1676 bool
1677 typeinfo_merge_add(typeinfo *dest,typeinfo_mergedlist *m,classref_or_classinfo cls)
1678 {
1679     int count;
1680     typeinfo_mergedlist *newmerged;
1681     classref_or_classinfo *mlist,*newlist;
1682
1683     count = m->count;
1684     mlist = m->list;
1685
1686     /* Check if cls is already in the mergedlist m. */
1687     while (count--) {
1688         if ((mlist++)->any == cls.any) { /* XXX check equal classrefs? */
1689             /* cls is in the list, so m is the resulting mergedlist */
1690             if (dest->merged == m)
1691                 return false;
1692
1693             /* We have to copy the mergedlist */
1694             TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1695             count = m->count;
1696             TYPEINFO_ALLOCMERGED(dest->merged,count);
1697             dest->merged->count = count;
1698             newlist = dest->merged->list;
1699             mlist = m->list;
1700             while (count--) {
1701                 *newlist++ = *mlist++;
1702             }
1703             return true;
1704         }
1705     }
1706
1707     /* Add cls to the mergedlist. */
1708     count = m->count;
1709     TYPEINFO_ALLOCMERGED(newmerged,count+1);
1710     newmerged->count = count+1;
1711     newlist = newmerged->list;
1712     mlist = m->list;
1713     while (count) {
1714         if (mlist->any > cls.any)
1715             break;
1716         *newlist++ = *mlist++;
1717         count--;
1718     }
1719     *newlist++ = cls;
1720     while (count--) {
1721         *newlist++ = *mlist++;
1722     }
1723
1724     /* Put the new mergedlist into dest. */
1725     TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1726     dest->merged = newmerged;
1727
1728     return true;
1729 }
1730
1731 /* Returns: true if dest was changed. */
1732 static
1733 bool
1734 typeinfo_merge_mergedlists(typeinfo *dest,typeinfo_mergedlist *x,
1735                            typeinfo_mergedlist *y)
1736 {
1737     int count = 0;
1738     int countx,county;
1739     typeinfo_mergedlist *temp,*result;
1740     classref_or_classinfo *clsx,*clsy,*newlist;
1741
1742     /* count the elements that will be in the resulting list */
1743     /* (Both lists are sorted, equal elements are counted only once.) */
1744     clsx = x->list;
1745     clsy = y->list;
1746     countx = x->count;
1747     county = y->count;
1748     while (countx && county) {
1749         if (clsx->any == clsy->any) {
1750             clsx++;
1751             clsy++;
1752             countx--;
1753             county--;
1754         }
1755         else if (clsx->any < clsy->any) {
1756             clsx++;
1757             countx--;
1758         }
1759         else {
1760             clsy++;
1761             county--;
1762         }
1763         count++;
1764     }
1765     count += countx + county;
1766
1767     /* {The new mergedlist will have count entries.} */
1768
1769     if ((x->count != count) && (y->count == count)) {
1770         temp = x; x = y; y = temp;
1771     }
1772     /* {If one of x,y is already the result it is x.} */
1773     if (x->count == count) {
1774         /* x->merged is equal to the result */
1775         if (x == dest->merged)
1776             return false;
1777
1778         if (!dest->merged || dest->merged->count != count) {
1779             TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1780             TYPEINFO_ALLOCMERGED(dest->merged,count);
1781             dest->merged->count = count;
1782         }
1783
1784         newlist = dest->merged->list;
1785         clsx = x->list;
1786         while (count--) {
1787             *newlist++ = *clsx++;
1788         }
1789         return true;
1790     }
1791
1792     /* {We have to merge two lists.} */
1793
1794     /* allocate the result list */
1795     TYPEINFO_ALLOCMERGED(result,count);
1796     result->count = count;
1797     newlist = result->list;
1798
1799     /* merge the sorted lists */
1800     clsx = x->list;
1801     clsy = y->list;
1802     countx = x->count;
1803     county = y->count;
1804     while (countx && county) {
1805         if (clsx->any == clsy->any) {
1806             *newlist++ = *clsx++;
1807             clsy++;
1808             countx--;
1809             county--;
1810         }
1811         else if (clsx->any < clsy->any) {
1812             *newlist++ = *clsx++;
1813             countx--;
1814         }
1815         else {
1816             *newlist++ = *clsy++;
1817             county--;
1818         }
1819     }
1820     while (countx--)
1821             *newlist++ = *clsx++;
1822     while (county--)
1823             *newlist++ = *clsy++;
1824
1825     /* replace the list in dest with the result list */
1826     TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1827     dest->merged = result;
1828
1829     return true;
1830 }
1831
1832 /* typeinfo_merge_nonarrays ****************************************************
1833
1834    Merge two non-array types.
1835
1836    IN:
1837        x................the first type
1838            y................the second type
1839            mergedx..........merged list of the first type, may be NULL
1840            mergedy..........merged list of the descond type, may be NULL
1841
1842    OUT:
1843        *dest............receives the resulting merged list
1844            *result..........receives the resulting type
1845
1846    RETURN VALUE:
1847        typecheck_TRUE...*dest has been modified
1848            typecheck_FALSE..*dest has not been modified
1849            typecheck_FAIL...an exception has been thrown
1850
1851    NOTE:
1852        RESULT is an extra parameter so it can point to dest->typeclass or to
1853            dest->elementclass.
1854
1855 *******************************************************************************/
1856
1857 static typecheck_result
1858 typeinfo_merge_nonarrays(typeinfo *dest,
1859                          classref_or_classinfo *result,
1860                          classref_or_classinfo x,classref_or_classinfo y,
1861                          typeinfo_mergedlist *mergedx,
1862                          typeinfo_mergedlist *mergedy)
1863 {
1864         classref_or_classinfo t;
1865     classinfo *tcls,*common;
1866     typeinfo_mergedlist *tmerged;
1867     bool changed;
1868         typecheck_result r;
1869         utf *xname;
1870         utf *yname;
1871
1872         TYPEINFO_ASSERT(dest && result && x.any && y.any);
1873         TYPEINFO_ASSERT(x.cls != pseudo_class_Null);
1874         TYPEINFO_ASSERT(y.cls != pseudo_class_Null);
1875         TYPEINFO_ASSERT(x.cls != pseudo_class_New);
1876         TYPEINFO_ASSERT(y.cls != pseudo_class_New);
1877
1878         /*--------------------------------------------------*/
1879         /* common cases                                     */
1880         /*--------------------------------------------------*/
1881
1882     /* Common case 1: x and y are the same class or class reference */
1883     /* (This case is very simple unless *both* x and y really represent
1884      *  merges of subclasses of clsx==clsy.)
1885      */
1886     if ( (x.any == y.any) && (!mergedx || !mergedy) ) {
1887   return_simple_x:
1888         /* DEBUG */ /* log_text("return simple x"); */
1889         changed = (dest->merged != NULL);
1890         TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1891         dest->merged = NULL;
1892         *result = x;
1893         /* DEBUG */ /* log_text("returning"); */
1894         return changed;
1895     }
1896
1897         xname = (IS_CLASSREF(x)) ? x.ref->name : x.cls->name;
1898         yname = (IS_CLASSREF(y)) ? y.ref->name : y.cls->name;
1899
1900         /* Common case 2: xname == yname, at least one unresolved */
1901     if ((IS_CLASSREF(x) || IS_CLASSREF(y)) && (xname == yname))
1902         {
1903                 /* use the loaded one if any */
1904                 if (!IS_CLASSREF(y))
1905                         x = y;
1906                 goto return_simple_x;
1907     }
1908
1909         /*--------------------------------------------------*/
1910         /* non-trivial cases                                */
1911         /*--------------------------------------------------*/
1912
1913 #ifdef TYPEINFO_VERBOSE
1914         {
1915                 typeinfo dbgx,dbgy;
1916                 fprintf(stderr,"merge_nonarrays:\n");
1917                 fprintf(stderr,"    ");if(IS_CLASSREF(x))fprintf(stderr,"<ref>");utf_fprint(stderr,xname);fprintf(stderr,"\n");
1918                 fprintf(stderr,"    ");if(IS_CLASSREF(y))fprintf(stderr,"<ref>");utf_fprint(stderr,yname);fprintf(stderr,"\n");
1919                 fflush(stderr);
1920                 typeinfo_init_class(&dbgx,x);
1921                 dbgx.merged = mergedx;
1922                 typeinfo_init_class(&dbgy,y);
1923                 dbgy.merged = mergedy;
1924                 typeinfo_print(stderr,&dbgx,4);
1925                 fprintf(stderr,"  with:\n");
1926                 typeinfo_print(stderr,&dbgy,4);
1927         }
1928 #endif
1929
1930         TYPEINFO_ASSERT(IS_CLASSREF(x) || x.cls->loaded);
1931         TYPEINFO_ASSERT(IS_CLASSREF(y) || y.cls->loaded);
1932
1933     /* If y is unresolved or an interface, swap x and y. */
1934     if (IS_CLASSREF(y) || (!IS_CLASSREF(x) && y.cls->flags & ACC_INTERFACE))
1935         {
1936         t = x; x = y; y = t;
1937         tmerged = mergedx; mergedx = mergedy; mergedy = tmerged;
1938     }
1939
1940     /* {We know: If only one of x,y is unresolved it is x,} */
1941     /* {         If both x,y are resolved and only one of x,y is an interface it is x.} */
1942
1943         if (IS_CLASSREF(x)) {
1944                 /* {We know: x and y have different class names} */
1945
1946         /* Check if we are merging an unresolved type with java.lang.Object */
1947         if (y.cls == class_java_lang_Object && !mergedy) {
1948             x = y;
1949             goto return_simple_x;
1950         }
1951
1952                 common = class_java_lang_Object;
1953                 goto merge_with_simple_x;
1954         }
1955
1956         /* {We know: both x and y are resolved} */
1957     /* {We know: If only one of x,y is an interface it is x.} */
1958
1959         TYPEINFO_ASSERT(!IS_CLASSREF(x) && !IS_CLASSREF(y));
1960         TYPEINFO_ASSERT(x.cls->loaded);
1961         TYPEINFO_ASSERT(y.cls->loaded);
1962
1963     /* Handle merging of interfaces: */
1964     if (x.cls->flags & ACC_INTERFACE) {
1965         /* {x.cls is an interface and mergedx == NULL.} */
1966
1967         if (y.cls->flags & ACC_INTERFACE) {
1968             /* We are merging two interfaces. */
1969             /* {mergedy == NULL} */
1970
1971             /* {We know that x.cls!=y.cls (see common case at beginning.)} */
1972             result->cls = class_java_lang_Object;
1973             return typeinfo_merge_two(dest,x,y);
1974         }
1975
1976         /* {We know: x is an interface, y is a class.} */
1977
1978         /* Check if we are merging an interface with java.lang.Object */
1979         if (y.cls == class_java_lang_Object && !mergedy) {
1980             x = y;
1981             goto return_simple_x;
1982         }
1983
1984         /* If the type y implements x then the result of the merge
1985          * is x regardless of mergedy.
1986          */
1987
1988                 /* we may have to link the classes */
1989                 if (!x.cls->linked)
1990                         if (!link_class(x.cls))
1991                                 return typecheck_FAIL;
1992                 if (!y.cls->linked)
1993                         if (!link_class(y.cls))
1994                                 return typecheck_FAIL;
1995
1996                 TYPEINFO_ASSERT(x.cls->linked);
1997                 TYPEINFO_ASSERT(y.cls->linked);
1998
1999         if (CLASSINFO_IMPLEMENTS_INTERFACE(y.cls,x.cls->index))
2000                 {
2001             /* y implements x, so the result of the merge is x. */
2002             goto return_simple_x;
2003                 }
2004
2005         r = mergedlist_implements_interface(mergedy,x.cls);
2006                 if (r == typecheck_FAIL)
2007                         return r;
2008                 if (r == typecheck_TRUE)
2009         {
2010             /* y implements x, so the result of the merge is x. */
2011             goto return_simple_x;
2012         }
2013
2014         /* {We know: x is an interface, the type y a class or a merge
2015          * of subclasses and is not guaranteed to implement x.} */
2016
2017         common = class_java_lang_Object;
2018         goto merge_with_simple_x;
2019     }
2020
2021     /* {We know: x and y are classes (not interfaces).} */
2022
2023         /* we may have to link the classes */
2024         if (!x.cls->linked)
2025                 if (!link_class(x.cls))
2026                         return typecheck_FAIL;
2027         if (!y.cls->linked)
2028                 if (!link_class(y.cls))
2029                         return typecheck_FAIL;
2030
2031         TYPEINFO_ASSERT(x.cls->linked);
2032         TYPEINFO_ASSERT(y.cls->linked);
2033
2034     /* If *x is deeper in the inheritance hierarchy swap x and y. */
2035     if (x.cls->index > y.cls->index) {
2036         t = x; x = y; y = t;
2037         tmerged = mergedx; mergedx = mergedy; mergedy = tmerged;
2038     }
2039
2040     /* {We know: y is at least as deep in the hierarchy as x.} */
2041
2042     /* Find nearest common anchestor for the classes. */
2043     common = x.cls;
2044     tcls = y.cls;
2045     while (tcls->index > common->index)
2046         tcls = tcls->super.cls;
2047     while (common != tcls) {
2048         common = common->super.cls;
2049         tcls = tcls->super.cls;
2050     }
2051
2052     /* {common == nearest common anchestor of x and y.} */
2053
2054     /* If x.cls==common and x is a whole class (not a merge of subclasses)
2055      * then the result of the merge is x.
2056      */
2057     if (x.cls == common && !mergedx) {
2058         goto return_simple_x;
2059     }
2060
2061     if (mergedx) {
2062         result->cls = common;
2063         if (mergedy)
2064             return typeinfo_merge_mergedlists(dest,mergedx,mergedy);
2065         else
2066             return typeinfo_merge_add(dest,mergedx,y);
2067     }
2068
2069 merge_with_simple_x:
2070     result->cls = common;
2071     if (mergedy)
2072         return typeinfo_merge_add(dest,mergedy,x);
2073     else
2074         return typeinfo_merge_two(dest,x,y);
2075 }
2076
2077 /* typeinfo_merge **************************************************************
2078
2079    Merge two types.
2080
2081    IN:
2082        m................method for exception messages
2083        dest.............the first type
2084        y................the second type
2085
2086    OUT:
2087        *dest............receives the result of the merge
2088
2089    RETURN VALUE:
2090        typecheck_TRUE...*dest has been modified
2091        typecheck_FALSE..*dest has not been modified
2092        typecheck_FAIL...an exception has been thrown
2093
2094    PRE-CONDITIONS:
2095        1) *dest must be a valid initialized typeinfo
2096        2) dest != y
2097
2098 *******************************************************************************/
2099
2100 typecheck_result
2101 typeinfo_merge(methodinfo *m,typeinfo *dest,typeinfo* y)
2102 {
2103     typeinfo *x;
2104     typeinfo *tmp;
2105     classref_or_classinfo common;
2106     classref_or_classinfo elementclass;
2107     int dimension;
2108     int elementtype;
2109     bool changed;
2110         typecheck_result r;
2111
2112         /*--------------------------------------------------*/
2113         /* fast checks                                      */
2114         /*--------------------------------------------------*/
2115
2116     /* Merging something with itself is a nop */
2117     if (dest == y)
2118         return typecheck_FALSE;
2119
2120     /* Merging two returnAddress types is ok. */
2121         /* Merging two different returnAddresses never happens, as the verifier */
2122         /* keeps them separate in order to check all the possible return paths  */
2123         /* from JSR subroutines.                                                */
2124     if (!dest->typeclass.any && !y->typeclass.any) {
2125                 TYPEINFO_ASSERT(TYPEINFO_RETURNADDRESS(*dest) ==  TYPEINFO_RETURNADDRESS(*y));
2126         return typecheck_FALSE;
2127         }
2128
2129     /* Primitive types cannot be merged with reference types */
2130         /* This must be checked before calls to typeinfo_merge.  */
2131     TYPEINFO_ASSERT(dest->typeclass.any && y->typeclass.any);
2132
2133     /* handle uninitialized object types */
2134     if (TYPEINFO_IS_NEWOBJECT(*dest) || TYPEINFO_IS_NEWOBJECT(*y)) {
2135         if (!TYPEINFO_IS_NEWOBJECT(*dest) || !TYPEINFO_IS_NEWOBJECT(*y)) {
2136             typeinfo_merge_error(m,"Trying to merge uninitialized object type.",dest,y);
2137                         return typecheck_FAIL;
2138                 }
2139         if (TYPEINFO_NEWOBJECT_INSTRUCTION(*dest) != TYPEINFO_NEWOBJECT_INSTRUCTION(*y)) {
2140             typeinfo_merge_error(m,"Trying to merge different uninitialized objects.",dest,y);
2141                         return typecheck_FAIL;
2142                 }
2143                 /* the same uninitialized object -- no change */
2144                 return typecheck_FALSE;
2145     }
2146
2147         /*--------------------------------------------------*/
2148         /* common cases                                     */
2149         /*--------------------------------------------------*/
2150
2151     /* Common case: dest and y are the same class or class reference */
2152     /* (This case is very simple unless *both* dest and y really represent
2153      *  merges of subclasses of class dest==class y.)
2154      */
2155     if ((dest->typeclass.any == y->typeclass.any) && (!dest->merged || !y->merged)) {
2156 return_simple:
2157         changed = (dest->merged != NULL);
2158         TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
2159         dest->merged = NULL;
2160         return changed;
2161     }
2162
2163     /* Handle null types: */
2164     if (TYPEINFO_IS_NULLTYPE(*y)) {
2165         return typecheck_FALSE;
2166     }
2167     if (TYPEINFO_IS_NULLTYPE(*dest)) {
2168         TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
2169         TYPEINFO_CLONE(*y,*dest);
2170         return typecheck_TRUE;
2171     }
2172
2173         /* Common case: two types with the same name, at least one unresolved */
2174         if (IS_CLASSREF(dest->typeclass)) {
2175                 if (IS_CLASSREF(y->typeclass)) {
2176                         if (dest->typeclass.ref->name == y->typeclass.ref->name)
2177                                 goto return_simple;
2178                 }
2179                 else {
2180                         /* XXX should we take y instead of dest here? */
2181                         if (dest->typeclass.ref->name == y->typeclass.cls->name)
2182                                 goto return_simple;
2183                 }
2184         }
2185         else {
2186                 if (IS_CLASSREF(y->typeclass)
2187                     && (dest->typeclass.cls->name == y->typeclass.ref->name))
2188                 {
2189                         goto return_simple;
2190                 }
2191         }
2192
2193         /*--------------------------------------------------*/
2194         /* non-trivial cases                                */
2195         /*--------------------------------------------------*/
2196
2197 #ifdef TYPEINFO_VERBOSE
2198         fprintf(stderr,"merge:\n");
2199     typeinfo_print(stderr,dest,4);
2200     typeinfo_print(stderr,y,4);
2201 #endif
2202
2203     /* This function uses x internally, so x and y can be swapped
2204      * without changing dest. */
2205     x = dest;
2206     changed = false;
2207
2208     /* Handle merging of arrays: */
2209     if (TYPEINFO_IS_ARRAY(*x) && TYPEINFO_IS_ARRAY(*y)) {
2210
2211         /* Make x the one with lesser dimension */
2212         if (x->dimension > y->dimension) {
2213             tmp = x; x = y; y = tmp;
2214         }
2215
2216         /* If one array (y) has higher dimension than the other,
2217          * interpret it as an array (same dim. as x) of Arraystubs. */
2218         if (x->dimension < y->dimension) {
2219             dimension = x->dimension;
2220             elementtype = ARRAYTYPE_OBJECT;
2221             elementclass.cls = pseudo_class_Arraystub;
2222         }
2223         else {
2224             dimension = y->dimension;
2225             elementtype = y->elementtype;
2226             elementclass = y->elementclass;
2227         }
2228
2229         /* {The arrays are of the same dimension.} */
2230
2231         if (x->elementtype != elementtype) {
2232             /* Different element types are merged, so the resulting array
2233              * type has one accessible dimension less. */
2234             if (--dimension == 0) {
2235                 common.cls = pseudo_class_Arraystub;
2236                 elementtype = 0;
2237                 elementclass.any = NULL;
2238             }
2239             else {
2240                 common.cls = class_multiarray_of(dimension,pseudo_class_Arraystub,true);
2241                                 if (!common.cls) {
2242                                         *exceptionptr = new_internalerror("XXX Coult not create array class");
2243                                         return typecheck_FAIL;
2244                                 }
2245
2246                 elementtype = ARRAYTYPE_OBJECT;
2247                 elementclass.cls = pseudo_class_Arraystub;
2248             }
2249         }
2250         else {
2251             /* {The arrays have the same dimension and elementtype.} */
2252
2253             if (elementtype == ARRAYTYPE_OBJECT) {
2254                 /* The elements are references, so their respective
2255                  * types must be merged.
2256                  */
2257                                 r = typeinfo_merge_nonarrays(dest,
2258                                                 &elementclass,
2259                                                 x->elementclass,
2260                                                 elementclass,
2261                                                 x->merged,y->merged);
2262                                 TYPEINFO_ASSERT(r != typecheck_MAYBE);
2263                                 if (r == typecheck_FAIL)
2264                                         return r;
2265                                 changed |= r;
2266
2267                 /* DEBUG */ /* log_text("finding resulting array class: "); */
2268                                 if (IS_CLASSREF(elementclass))
2269                                         common.ref = class_get_classref_multiarray_of(dimension,elementclass.ref);
2270                                 else {
2271                                         common.cls = class_multiarray_of(dimension,elementclass.cls,true);
2272                                         if (!common.cls) {
2273                                                 *exceptionptr = new_internalerror("XXX Coult not create array class");
2274                                                 return typecheck_FAIL;
2275                                         }
2276                                 }
2277                 /* DEBUG */ /* utf_display(common->name); printf("\n"); */
2278             }
2279                         else {
2280                                 common.any = y->typeclass.any;
2281                         }
2282         }
2283     }
2284     else {
2285         /* {We know that at least one of x or y is no array, so the
2286          *  result cannot be an array.} */
2287
2288                 r = typeinfo_merge_nonarrays(dest,
2289                                 &common,
2290                                 x->typeclass,y->typeclass,
2291                                 x->merged,y->merged);
2292                 TYPEINFO_ASSERT(r != typecheck_MAYBE);
2293                 if (r == typecheck_FAIL)
2294                         return r;
2295                 changed |= r;
2296
2297         dimension = 0;
2298         elementtype = 0;
2299         elementclass.any = NULL;
2300     }
2301
2302     /* Put the new values into dest if neccessary. */
2303
2304     if (dest->typeclass.any != common.any) {
2305         dest->typeclass.any = common.any;
2306         changed = true;
2307     }
2308     if (dest->dimension != dimension) {
2309         dest->dimension = dimension;
2310         changed = true;
2311     }
2312     if (dest->elementtype != elementtype) {
2313         dest->elementtype = elementtype;
2314         changed = true;
2315     }
2316     if (dest->elementclass.any != elementclass.any) {
2317         dest->elementclass.any = elementclass.any;
2318         changed = true;
2319     }
2320
2321     return changed;
2322 }
2323
2324
2325 /**********************************************************************/
2326 /* DEBUGGING HELPERS                                                  */
2327 /**********************************************************************/
2328
2329 #ifdef TYPEINFO_DEBUG
2330
2331 #if 0
2332 static int
2333 typeinfo_test_compare(classref_or_classinfo *a,classref_or_classinfo *b)
2334 {
2335     if (a->any == b->any) return 0;
2336     if (a->any < b->any) return -1;
2337     return +1;
2338 }
2339
2340 static void
2341 typeinfo_test_parse(typeinfo *info,char *str)
2342 {
2343     int num;
2344     int i;
2345     typeinfo *infobuf;
2346     u1 *typebuf;
2347     int returntype;
2348     utf *desc = utf_new_char(str);
2349
2350     num = typeinfo_count_method_args(desc,false);
2351     if (num) {
2352         typebuf = DMNEW(u1,num);
2353         infobuf = DMNEW(typeinfo,num);
2354
2355         typeinfo_init_from_method_args(desc,typebuf,infobuf,num,false,
2356                                        &returntype,info);
2357
2358         TYPEINFO_ALLOCMERGED(info->merged,num);
2359         info->merged->count = num;
2360
2361         for (i=0; i<num; ++i) {
2362             if (typebuf[i] != TYPE_ADDRESS) {
2363                 log_text("non-reference type in mergedlist");
2364                                 assert(0);
2365                         }
2366
2367             info->merged->list[i].any = infobuf[i].typeclass.any;
2368         }
2369         qsort(info->merged->list,num,sizeof(classref_or_classinfo),
2370               (int(*)(const void *,const void *))&typeinfo_test_compare);
2371     }
2372     else {
2373         typeinfo_init_from_method_args(desc,NULL,NULL,0,false,
2374                                        &returntype,info);
2375     }
2376 }
2377 #endif
2378
2379 #define TYPEINFO_TEST_BUFLEN  4000
2380
2381 static bool
2382 typeinfo_equal(typeinfo *x,typeinfo *y)
2383 {
2384     int i;
2385
2386     if (x->typeclass.any != y->typeclass.any) return false;
2387     if (x->dimension != y->dimension) return false;
2388     if (x->dimension) {
2389         if (x->elementclass.any != y->elementclass.any) return false;
2390         if (x->elementtype != y->elementtype) return false;
2391     }
2392
2393     if (TYPEINFO_IS_NEWOBJECT(*x))
2394         if (TYPEINFO_NEWOBJECT_INSTRUCTION(*x)
2395             != TYPEINFO_NEWOBJECT_INSTRUCTION(*y))
2396             return false;
2397
2398     if (x->merged || y->merged) {
2399         if (!(x->merged && y->merged)) return false;
2400         if (x->merged->count != y->merged->count) return false;
2401         for (i=0; i<x->merged->count; ++i)
2402             if (x->merged->list[i].any != y->merged->list[i].any)
2403                 return false;
2404     }
2405     return true;
2406 }
2407
2408 static void
2409 typeinfo_testmerge(typeinfo *a,typeinfo *b,typeinfo *result,int *failed)
2410 {
2411     typeinfo dest;
2412     bool changed,changed_should_be;
2413         typecheck_result r;
2414
2415     TYPEINFO_CLONE(*a,dest);
2416
2417     printf("\n          ");
2418     typeinfo_print_short(stdout,&dest);
2419     printf("\n          ");
2420     typeinfo_print_short(stdout,b);
2421     printf("\n");
2422
2423         r = typeinfo_merge(NULL,&dest,b);
2424         if (r == typecheck_FAIL) {
2425                 printf("EXCEPTION\n");
2426                 return;
2427         }
2428     changed = (r) ? 1 : 0;
2429     changed_should_be = (!typeinfo_equal(&dest,a)) ? 1 : 0;
2430
2431     printf("          %s\n",(changed) ? "changed" : "=");
2432
2433     if (typeinfo_equal(&dest,result)) {
2434         printf("OK        ");
2435         typeinfo_print_short(stdout,&dest);
2436         printf("\n");
2437         if (changed != changed_should_be) {
2438             printf("WRONG RETURN VALUE!\n");
2439             (*failed)++;
2440         }
2441     }
2442     else {
2443         printf("RESULT    ");
2444         typeinfo_print_short(stdout,&dest);
2445         printf("\n");
2446         printf("SHOULD BE ");
2447         typeinfo_print_short(stdout,result);
2448         printf("\n");
2449         (*failed)++;
2450     }
2451 }
2452
2453 #if 0
2454 static void
2455 typeinfo_inc_dimension(typeinfo *info)
2456 {
2457     if (info->dimension++ == 0) {
2458         info->elementtype = ARRAYTYPE_OBJECT;
2459         info->elementclass = info->typeclass;
2460     }
2461     info->typeclass = class_array_of(info->typeclass,true);
2462 }
2463 #endif
2464
2465 #define TYPEINFO_TEST_MAXDIM  10
2466
2467 static void
2468 typeinfo_testrun(char *filename)
2469 {
2470     char buf[TYPEINFO_TEST_BUFLEN];
2471     char bufa[TYPEINFO_TEST_BUFLEN];
2472     char bufb[TYPEINFO_TEST_BUFLEN];
2473     char bufc[TYPEINFO_TEST_BUFLEN];
2474     typeinfo a,b,c;
2475     int maxdim;
2476     int failed = 0;
2477     FILE *file = fopen(filename,"rt");
2478         int res;
2479
2480     if (!file) {
2481         log_text("could not open typeinfo test file");
2482                 assert(0);
2483         }
2484
2485     while (fgets(buf,TYPEINFO_TEST_BUFLEN,file)) {
2486         if (buf[0] == '#' || !strlen(buf))
2487             continue;
2488
2489         res = sscanf(buf,"%s\t%s\t%s\n",bufa,bufb,bufc);
2490         if (res != 3 || !strlen(bufa) || !strlen(bufb) || !strlen(bufc)) {
2491             log_text("Invalid line in typeinfo test file (none of empty, comment or test)");
2492                         assert(0);
2493                 }
2494
2495 #if 0
2496         typeinfo_test_parse(&a,bufa);
2497         typeinfo_test_parse(&b,bufb);
2498         typeinfo_test_parse(&c,bufc);
2499 #endif
2500 #if 0
2501         do {
2502 #endif
2503             typeinfo_testmerge(&a,&b,&c,&failed); /* check result */
2504             typeinfo_testmerge(&b,&a,&c,&failed); /* check commutativity */
2505
2506             if (TYPEINFO_IS_NULLTYPE(a)) break;
2507             if (TYPEINFO_IS_NULLTYPE(b)) break;
2508             if (TYPEINFO_IS_NULLTYPE(c)) break;
2509
2510             maxdim = a.dimension;
2511             if (b.dimension > maxdim) maxdim = b.dimension;
2512             if (c.dimension > maxdim) maxdim = c.dimension;
2513
2514 #if 0
2515             if (maxdim < TYPEINFO_TEST_MAXDIM) {
2516                 typeinfo_inc_dimension(&a);
2517                 typeinfo_inc_dimension(&b);
2518                 typeinfo_inc_dimension(&c);
2519             }
2520         } while (maxdim < TYPEINFO_TEST_MAXDIM);
2521 #endif
2522     }
2523
2524     fclose(file);
2525
2526     if (failed) {
2527         fprintf(stderr,"Failed typeinfo_merge tests: %d\n",failed);
2528         log_text("Failed test");
2529                 assert(0);
2530     }
2531 }
2532
2533 void
2534 typeinfo_test()
2535 {
2536     log_text("Running typeinfo test file...");
2537     typeinfo_testrun("typeinfo.tst");
2538     log_text("Finished typeinfo test file.");
2539 }
2540
2541 #if 0
2542 void
2543 typeinfo_init_from_fielddescriptor(typeinfo *info,char *desc)
2544 {
2545     typeinfo_init_from_descriptor(info,desc,desc+strlen(desc));
2546 }
2547 #endif
2548
2549 #define TYPEINFO_MAXINDENT  80
2550
2551 void
2552 typeinfo_print_class(FILE *file,classref_or_classinfo c)
2553 {
2554         /*fprintf(file,"<class %p>",c.any);*/
2555
2556         if (!c.any) {
2557                 fprintf(file,"<null>");
2558         }
2559         else {
2560                 if (IS_CLASSREF(c)) {
2561                         fprintf(file,"<ref>");
2562                         utf_fprint(file,c.ref->name);
2563                 }
2564                 else {
2565                         utf_fprint(file,c.cls->name);
2566                 }
2567         }
2568 }
2569
2570 void
2571 typeinfo_print(FILE *file,typeinfo *info,int indent)
2572 {
2573     int i;
2574     char ind[TYPEINFO_MAXINDENT + 1];
2575     instruction *ins;
2576         basicblock *bptr;
2577
2578     if (indent > TYPEINFO_MAXINDENT) indent = TYPEINFO_MAXINDENT;
2579
2580     for (i=0; i<indent; ++i)
2581         ind[i] = ' ';
2582     ind[i] = (char) 0;
2583
2584     if (TYPEINFO_IS_PRIMITIVE(*info)) {
2585                 bptr = (basicblock*) TYPEINFO_RETURNADDRESS(*info);
2586                 if (bptr)
2587                         fprintf(file,"%sreturnAddress (L%03d)\n",ind,bptr->debug_nr);
2588                 else
2589                         fprintf(file,"%sprimitive\n",ind);
2590         return;
2591     }
2592
2593     if (TYPEINFO_IS_NULLTYPE(*info)) {
2594         fprintf(file,"%snull\n",ind);
2595         return;
2596     }
2597
2598     if (TYPEINFO_IS_NEWOBJECT(*info)) {
2599         ins = (instruction *)TYPEINFO_NEWOBJECT_INSTRUCTION(*info);
2600         if (ins) {
2601             fprintf(file,"%sNEW(%p):",ind,(void*)ins);
2602                         typeinfo_print_class(file,CLASSREF_OR_CLASSINFO(ins[-1].val.a));
2603             fprintf(file,"\n");
2604         }
2605         else {
2606             fprintf(file,"%sNEW(this)",ind);
2607         }
2608         return;
2609     }
2610
2611     fprintf(file,"%sClass:      ",ind);
2612         typeinfo_print_class(file,info->typeclass);
2613     fprintf(file,"\n");
2614
2615     if (TYPEINFO_IS_ARRAY(*info)) {
2616         fprintf(file,"%sDimension:    %d",ind,(int)info->dimension);
2617         fprintf(file,"\n%sElements:     ",ind);
2618         switch (info->elementtype) {
2619           case ARRAYTYPE_INT     : fprintf(file,"int\n"); break;
2620           case ARRAYTYPE_LONG    : fprintf(file,"long\n"); break;
2621           case ARRAYTYPE_FLOAT   : fprintf(file,"float\n"); break;
2622           case ARRAYTYPE_DOUBLE  : fprintf(file,"double\n"); break;
2623           case ARRAYTYPE_BYTE    : fprintf(file,"byte\n"); break;
2624           case ARRAYTYPE_CHAR    : fprintf(file,"char\n"); break;
2625           case ARRAYTYPE_SHORT   : fprintf(file,"short\n"); break;
2626           case ARRAYTYPE_BOOLEAN : fprintf(file,"boolean\n"); break;
2627
2628           case ARRAYTYPE_OBJECT:
2629                           typeinfo_print_class(file,info->elementclass);
2630               fprintf(file,"\n");
2631               break;
2632
2633           default:
2634               fprintf(file,"INVALID ARRAYTYPE!\n");
2635         }
2636     }
2637
2638     if (info->merged) {
2639         fprintf(file,"%sMerged:     ",ind);
2640         for (i=0; i<info->merged->count; ++i) {
2641             if (i) fprintf(file,", ");
2642                         typeinfo_print_class(file,info->merged->list[i]);
2643         }
2644         fprintf(file,"\n");
2645     }
2646 }
2647
2648 void
2649 typeinfo_print_short(FILE *file,typeinfo *info)
2650 {
2651     int i;
2652     instruction *ins;
2653         basicblock *bptr;
2654
2655         /*fprintf(file,"<typeinfo %p>",info);*/
2656
2657         if (!info) {
2658                 fprintf(file,"(typeinfo*)NULL");
2659                 return;
2660         }
2661
2662     if (TYPEINFO_IS_PRIMITIVE(*info)) {
2663                 bptr = (basicblock*) TYPEINFO_RETURNADDRESS(*info);
2664                 if (bptr)
2665                         fprintf(file,"ret(L%03d)",bptr->debug_nr);
2666                 else
2667                         fprintf(file,"primitive");
2668         return;
2669     }
2670
2671     if (TYPEINFO_IS_NULLTYPE(*info)) {
2672         fprintf(file,"null");
2673         return;
2674     }
2675
2676     if (TYPEINFO_IS_NEWOBJECT(*info)) {
2677         ins = (instruction *)TYPEINFO_NEWOBJECT_INSTRUCTION(*info);
2678         if (ins) {
2679                         /*fprintf(file,"<ins %p>",ins);*/
2680             fprintf(file,"NEW(%p):",(void*)ins);
2681                         typeinfo_print_class(file,CLASSREF_OR_CLASSINFO(ins[-1].val.a));
2682         }
2683         else
2684             fprintf(file,"NEW(this)");
2685         return;
2686     }
2687
2688     typeinfo_print_class(file,info->typeclass);
2689
2690     if (info->merged) {
2691         fprintf(file,"{");
2692         for (i=0; i<info->merged->count; ++i) {
2693             if (i) fprintf(file,",");
2694                         typeinfo_print_class(file,info->merged->list[i]);
2695         }
2696         fprintf(file,"}");
2697     }
2698 }
2699
2700 void
2701 typeinfo_print_type(FILE *file,int type,typeinfo *info)
2702 {
2703     switch (type) {
2704       case TYPE_VOID:   fprintf(file,"V"); break;
2705       case TYPE_INT:    fprintf(file,"I"); break;
2706       case TYPE_FLOAT:  fprintf(file,"F"); break;
2707       case TYPE_DOUBLE: fprintf(file,"D"); break;
2708       case TYPE_LONG:   fprintf(file,"J"); break;
2709       case TYPE_ADDRESS:
2710                   typeinfo_print_short(file,info);
2711           break;
2712
2713       default:
2714           fprintf(file,"!");
2715     }
2716 }
2717
2718 void
2719 typeinfo_print_stacktype(FILE *file,int type,typeinfo *info)
2720 {
2721         TYPEINFO_ASSERT(file);
2722         TYPEINFO_ASSERT(type != TYPE_ADDRESS || info != NULL);
2723         if (type == TYPE_ADDRESS && TYPEINFO_IS_PRIMITIVE(*info)) {
2724                 typeinfo_retaddr_set *set = (typeinfo_retaddr_set*)
2725                         TYPEINFO_RETURNADDRESS(*info);
2726                 if (set) {
2727                         fprintf(file,"ret(L%03d",((basicblock*)(set->addr))->debug_nr);
2728                         set = set->alt;
2729                         while (set) {
2730                                 fprintf(file,"|L%03d",((basicblock*)(set->addr))->debug_nr);
2731                                 set = set->alt;
2732                         }
2733                 }
2734                 else {
2735                         fprintf(file,"ret(<NULL>");
2736                 }
2737                 fprintf(file,")");
2738         }
2739         else
2740                 typeinfo_print_type(file,type,info);
2741 }
2742
2743 void
2744 typedescriptor_print(FILE *file,typedescriptor *td)
2745 {
2746         typeinfo_print_type(file,td->type,&(td->info));
2747 }
2748
2749 void
2750 typevector_print(FILE *file,typevector *vec,int size)
2751 {
2752     int i;
2753
2754         fprintf(file,"[%d]",vec->k);
2755     for (i=0; i<size; ++i) {
2756                 fprintf(file," %d=",i);
2757         typedescriptor_print(file,vec->td + i);
2758     }
2759 }
2760
2761 void
2762 typevectorset_print(FILE *file,typevector *set,int size)
2763 {
2764     int i;
2765         typevector *vec;
2766
2767         fprintf(file,"[%d",set->k);
2768         vec = set->alt;
2769         while (vec) {
2770                 fprintf(file,"|%d",vec->k);
2771                 vec = vec->alt;
2772         }
2773         fprintf(file,"]");
2774
2775     for (i=0; i<size; ++i) {
2776                 fprintf(file," %d=",i);
2777         typedescriptor_print(file,set->td + i);
2778                 vec = set->alt;
2779                 while (vec) {
2780                         fprintf(file,"|");
2781                         typedescriptor_print(file,vec->td + i);
2782                         vec = vec->alt;
2783                 }
2784     }
2785 }
2786
2787 #endif /* TYPEINFO_DEBUG */
2788
2789
2790 /*
2791  * These are local overrides for various environment variables in Emacs.
2792  * Please do not remove this and leave it at the end of the file, where
2793  * Emacs will automagically detect them.
2794  * ---------------------------------------------------------------------
2795  * Local variables:
2796  * mode: c
2797  * indent-tabs-mode: t
2798  * c-basic-offset: 4
2799  * tab-width: 4
2800  * End:
2801  * vim:noexpandtab:sw=4:ts=4:
2802  */