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