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 2788 2005-06-22 16:08:51Z edwin $
  30
  31 */
  32
  33 #include <assert.h>
  34 #include <string.h>
  35
  36 #include "mm/memory.h"
  37 #include "toolbox/logging.h"
  38 #include "vm/class.h"
  39 #include "vm/loader.h"
  40 #include "vm/tables.h"
  41 #include "vm/jit/jit.h"
  42 #include "vm/jit/verify/typeinfo.h"
  43 #include "vm/descriptor.h"
  44 #include "vm/resolve.h"
  45
  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 #define CLASSINFO_IMPLEMENTS_INTERFACE(cls,index)                   \
  51     ( ((index) < (cls)->vftbl->interfacetablelength)            \
  52       && (VFTBLINTERFACETABLE((cls)->vftbl,(index)) != NULL) )
  53
  54 /******************************************************************************/
  55 /* DEBUG HELPERS                                                              */
  56 /******************************************************************************/
  57
  58 #ifdef TYPEINFO_DEBUG
  59 #define TYPEINFO_ASSERT(cond)  assert(cond)
  60 #else
  61 #define TYPEINFO_ASSERT(cond)
  62 #endif
  63
  64 /**********************************************************************/
  65 /* TYPEVECTOR FUNCTIONS                                               */
  66 /**********************************************************************/
  67
  68 typevector *
  69 typevectorset_copy(typevector *src,int k,int size)
  70 {
  71         typevector *dst = DNEW_TYPEVECTOR(size);
  72
  73         memcpy(dst,src,TYPEVECTOR_SIZE(size));
  74         dst->k = k;
  75         if (src->alt)
  76                 dst->alt = typevectorset_copy(src->alt,k+1,size);
  77         return dst;
  78 }
  79
  80 bool
  81 typevectorset_checktype(typevector *vec,int index,int type)
  82 {
  83         do {
  84                 if (vec->td[index].type != type)
  85                         return false;
  86         } while ((vec = vec->alt) != NULL);
  87         return true;
  88 }
  89
  90 bool
  91 typevectorset_checkreference(typevector *vec,int index)
  92 {
  93         do {
  94                 if (!TYPEDESC_IS_REFERENCE(vec->td[index]))
  95                         return false;
  96         } while ((vec = vec->alt) != NULL);
  97         return true;
  98 }
  99
 100 bool
 101 typevectorset_checkretaddr(typevector *vec,int index)
 102 {
 103         do {
 104                 if (!TYPEDESC_IS_RETURNADDRESS(vec->td[index]))
 105                         return false;
 106         } while ((vec = vec->alt) != NULL);
 107         return true;
 108 }
 109
 110 int
 111 typevectorset_copymergedtype(typevector *vec,int index,typeinfo *dst)
 112 {
 113         int type;
 114         typedescriptor *td;
 115
 116         td = vec->td + index;
 117         type = td->type;
 118         TYPEINFO_COPY(td->info,*dst);
 119
 120         if (vec->alt) {
 121                 int primitive;
 122
 123                 primitive = TYPEINFO_IS_PRIMITIVE(*dst) ? 1 : 0;
 124
 125                 while ((vec = vec->alt) != NULL) {
 126                         td = vec->td + index;
 127                         if (type != td->type)
 128                                 return TYPE_VOID;
 129
 130                         if (type == TYPE_ADDRESS) {
 131                                 if ((TYPEINFO_IS_PRIMITIVE(td->info) ? 1 : 0) != primitive)
 132                                         return TYPE_VOID;
 133                                 typeinfo_merge(dst,&(td->info));
 134                         }
 135                 }
 136         }
 137         return type;
 138 }
 139
 140 int
 141 typevectorset_mergedtype(typevector *vec,int index,typeinfo *temp,typeinfo **result)
 142 {
 143         if (vec->alt) {
 144                 *result = temp;
 145                 return typevectorset_copymergedtype(vec,index,temp);
 146         }
 147
 148         *result = &(vec->td[index].info);
 149         return vec->td[index].type;
 150 }
 151
 152 typeinfo *
 153 typevectorset_mergedtypeinfo(typevector *vec,int index,typeinfo *temp)
 154 {
 155         typeinfo *result;
 156         int type = typevectorset_mergedtype(vec,index,temp,&result);
 157         return (type == TYPE_ADDRESS) ? result : NULL;
 158 }
 159
 160 void
 161 typevectorset_store(typevector *vec,int index,int type,typeinfo *info)
 162 {
 163         do {
 164                 vec->td[index].type = type;
 165                 if (info)
 166                         TYPEINFO_COPY(*info,vec->td[index].info);
 167                 if (index > 0 && IS_2_WORD_TYPE(vec->td[index-1].type))
 168                         vec->td[index-1].type = TYPE_VOID;
 169         } while ((vec = vec->alt) != NULL);
 170 }
 171
 172 void
 173 typevectorset_store_retaddr(typevector *vec,int index,typeinfo *info)
 174 {
 175         typeinfo_retaddr_set *adr;
 176
 177         adr = (typeinfo_retaddr_set*) TYPEINFO_RETURNADDRESS(*info);
 178         do {
 179                 vec->td[index].type = TYPE_ADDRESS;
 180                 TYPEINFO_INIT_RETURNADDRESS(vec->td[index].info,adr->addr);
 181                 if (index > 0 && IS_2_WORD_TYPE(vec->td[index-1].type))
 182                         vec->td[index-1].type = TYPE_VOID;
 183                 adr = adr->alt;
 184         } while ((vec = vec->alt) != NULL);
 185 }
 186
 187 void
 188 typevectorset_store_twoword(typevector *vec,int index,int type)
 189 {
 190         do {
 191                 vec->td[index].type = type;
 192                 vec->td[index+1].type = TYPE_VOID;
 193                 if (index > 0 && IS_2_WORD_TYPE(vec->td[index-1].type))
 194                         vec->td[index-1].type = TYPE_VOID;
 195         } while ((vec = vec->alt) != NULL);
 196 }
 197
 198 bool
 199 typevectorset_init_object(typevector *set,void *ins,
 200                                                   classref_or_classinfo initclass,
 201                                                   int size)
 202 {
 203         int i;
 204
 205         for (;set; set=set->alt) {
 206                 for (i=0; i<size; ++i) {
 207                         if (set->td[i].type == TYPE_ADR
 208                                 && TYPEINFO_IS_NEWOBJECT(set->td[i].info)
 209                                 && TYPEINFO_NEWOBJECT_INSTRUCTION(set->td[i].info) == ins)
 210                         {
 211                                 if (!typeinfo_init_class(&(set->td[i].info),initclass))
 212                                         return false;
 213                         }
 214                 }
 215         }
 216         return true;
 217 }
 218
 219 bool
 220 typevector_merge(typevector *dst,typevector *y,int size)
 221 {
 222         bool changed = false;
 223
 224         typedescriptor *a = dst->td;
 225         typedescriptor *b = y->td;
 226         while (size--) {
 227                 if (a->type != TYPE_VOID && a->type != b->type) {
 228                         a->type = TYPE_VOID;
 229                         changed = true;
 230                 }
 231                 else if (a->type == TYPE_ADDRESS) {
 232                         if (TYPEINFO_IS_PRIMITIVE(a->info)) {
 233                                 /* 'a' is a returnAddress */
 234                                 if (!TYPEINFO_IS_PRIMITIVE(b->info)
 235                                         || (TYPEINFO_RETURNADDRESS(a->info)
 236                                                 != TYPEINFO_RETURNADDRESS(b->info)))
 237                                 {
 238                                         a->type = TYPE_VOID;
 239                                         changed = true;
 240                                 }
 241                         }
 242                         else {
 243                                 /* 'a' is a reference */
 244                                 if (TYPEINFO_IS_PRIMITIVE(b->info)) {
 245                                         a->type = TYPE_VOID;
 246                                         changed = true;
 247                                 }
 248                                 else {
 249                                         changed |= typeinfo_merge(&(a->info),&(b->info));
 250                                 }
 251                         }
 252                 }
 253                 a++;
 254                 b++;
 255         }
 256         return changed;
 257 }
 258
 259 bool
 260 typevector_separable_from(typevector *a,typevector *b,int size)
 261 {
 262         typedescriptor *tda = a->td;
 263         typedescriptor *tdb = b->td;
 264         for (;size--; tda++,tdb++) {
 265                 if (TYPEDESC_IS_RETURNADDRESS(*tda)
 266                         && TYPEDESC_IS_RETURNADDRESS(*tdb)
 267                         && TYPEINFO_RETURNADDRESS(tda->info)
 268                            != TYPEINFO_RETURNADDRESS(tdb->info))
 269                         return true;
 270         }
 271         return false;
 272 }
 273
 274 void
 275 typevectorset_add(typevector *dst,typevector *v,int size)
 276 {
 277         while (dst->alt)
 278                 dst = dst->alt;
 279         dst->alt = DNEW_TYPEVECTOR(size);
 280         memcpy(dst->alt,v,TYPEVECTOR_SIZE(size));
 281         dst->alt->alt = NULL;
 282         dst->alt->k = dst->k + 1;
 283 }
 284
 285 typevector *
 286 typevectorset_select(typevector **set,int retindex,void *retaddr)
 287 {
 288         typevector *selected;
 289
 290         if (!*set) return NULL;
 291
 292         if (TYPEINFO_RETURNADDRESS((*set)->td[retindex].info) == retaddr) {
 293                 selected = *set;
 294                 *set = selected->alt;
 295                 selected->alt = typevectorset_select(set,retindex,retaddr);
 296         }
 297         else {
 298                 selected = typevectorset_select(&((*set)->alt),retindex,retaddr);
 299         }
 300         return selected;
 301 }
 302
 303 bool
 304 typevectorset_separable_with(typevector *set,typevector *add,int size)
 305 {
 306         int i;
 307         typevector *v;
 308         void *addr;
 309         bool separable;
 310
 311         for (i=0; i<size; ++i) {
 312                 if (!TYPEDESC_IS_RETURNADDRESS(add->td[i]))
 313                         continue;
 314                 addr = TYPEINFO_RETURNADDRESS(add->td[i].info);
 315
 316                 v = set;
 317                 separable = false;
 318                 do {
 319                         if (!TYPEDESC_IS_RETURNADDRESS(v->td[i]))
 320                                 goto next_index;
 321                         if (TYPEINFO_RETURNADDRESS(v->td[i].info) != addr)
 322                                 separable = true;
 323                         v = v->alt;
 324                         if (!v && separable) return true;
 325                 } while (v);
 326         next_index:
 327                 ;
 328         }
 329         return false;
 330 }
 331
 332 bool
 333 typevectorset_collapse(typevector *dst,int size)
 334 {
 335         bool changed = false;
 336
 337         while (dst->alt) {
 338                 typevector_merge(dst,dst->alt,size);
 339                 dst->alt = dst->alt->alt;
 340                 changed = true;
 341         }
 342         return changed;
 343 }
 344
 345 /**********************************************************************/
 346 /* READ-ONLY FUNCTIONS                                                */
 347 /* The following functions don't change typeinfo data.                */
 348 /**********************************************************************/
 349
 350 bool
 351 typeinfo_is_array(typeinfo *info)
 352 {
 353         TYPEINFO_ASSERT(info);
 354     return TYPEINFO_IS_ARRAY(*info);
 355 }
 356
 357 bool
 358 typeinfo_is_primitive_array(typeinfo *info,int arraytype)
 359 {
 360         TYPEINFO_ASSERT(info);
 361     return TYPEINFO_IS_PRIMITIVE_ARRAY(*info,arraytype);
 362 }
 363
 364 bool
 365 typeinfo_is_array_of_refs(typeinfo *info)
 366 {
 367         TYPEINFO_ASSERT(info);
 368     return TYPEINFO_IS_ARRAY_OF_REFS(*info);
 369 }
 370
 371 static bool
 372 interface_extends_interface(classinfo *cls,classinfo *interf)
 373 {
 374     int i;
 375
 376         TYPEINFO_ASSERT(cls);
 377         TYPEINFO_ASSERT(interf);
 378         TYPEINFO_ASSERT((interf->flags & ACC_INTERFACE) != 0);
 379         TYPEINFO_ASSERT((cls->flags & ACC_INTERFACE) != 0);
 380         TYPEINFO_ASSERT(cls->linked);
 381
 382     /* first check direct superinterfaces */
 383     for (i=0; i<cls->interfacescount; ++i) {
 384         if (cls->interfaces[i].cls == interf)
 385             return true;
 386     }
 387
 388     /* check indirect superinterfaces */
 389     for (i=0; i<cls->interfacescount; ++i) {
 390         if (interface_extends_interface(cls->interfaces[i].cls,interf))
 391             return true;
 392     }
 393
 394     return false;
 395 }
 396
 397 static bool
 398 classinfo_implements_interface(classinfo *cls,classinfo *interf)
 399 {
 400         TYPEINFO_ASSERT(cls);
 401         TYPEINFO_ASSERT(interf);
 402         TYPEINFO_ASSERT((interf->flags & ACC_INTERFACE) != 0);
 403
 404         if (!cls->linked)
 405                 if (!link_class(cls)) /* XXX */
 406                         return false;
 407
 408     if (cls->flags & ACC_INTERFACE) {
 409         /* cls is an interface */
 410         if (cls == interf)
 411             return true;
 412
 413         /* check superinterfaces */
 414         return interface_extends_interface(cls,interf);
 415     }
 416
 417     return CLASSINFO_IMPLEMENTS_INTERFACE(cls,interf->index);
 418 }
 419
 420 tristate_t
 421 mergedlist_implements_interface(typeinfo_mergedlist *merged,
 422                                 classinfo *interf)
 423 {
 424     int i;
 425     classref_or_classinfo *mlist;
 426
 427         TYPEINFO_ASSERT(interf);
 428         TYPEINFO_ASSERT((interf->flags & ACC_INTERFACE) != 0);
 429
 430     /* Check if there is an non-empty mergedlist. */
 431     if (!merged)
 432         return false;
 433
 434     /* If all classinfos in the (non-empty) merged array implement the
 435      * interface return true, otherwise false.
 436      */
 437     mlist = merged->list;
 438     i = merged->count;
 439     while (i--) {
 440                 if (IS_CLASSREF(*mlist)) {
 441                         return MAYBE;
 442                 }
 443         if (!classinfo_implements_interface((mlist++)->cls,interf))
 444             return false;
 445     }
 446     return true;
 447 }
 448
 449 tristate_t
 450 merged_implements_interface(classinfo *typeclass,typeinfo_mergedlist *merged,
 451                             classinfo *interf)
 452 {
 453     /* primitive types don't support interfaces. */
 454     if (!typeclass)
 455         return false;
 456
 457     /* the null type can be cast to any interface type. */
 458     if (typeclass == pseudo_class_Null)
 459         return true;
 460
 461     /* check if typeclass implements the interface. */
 462     if (classinfo_implements_interface(typeclass,interf))
 463         return true;
 464
 465     /* check the mergedlist */
 466     return (merged && mergedlist_implements_interface(merged,interf));
 467 }
 468
 469 tristate_t
 470 typeinfo_is_assignable(typeinfo *value,typeinfo *dest)
 471 {
 472         TYPEINFO_ASSERT(value);
 473         TYPEINFO_ASSERT(dest);
 474         TYPEINFO_ASSERT(dest->merged == NULL);
 475
 476         return typeinfo_is_assignable_to_class(value,dest->typeclass);
 477 }
 478
 479 tristate_t
 480 typeinfo_is_assignable_to_class(typeinfo *value,classref_or_classinfo dest)
 481 {
 482         classref_or_classinfo c;
 483     classinfo *cls;
 484         utf *classname;
 485
 486         TYPEINFO_ASSERT(value);
 487
 488     c = value->typeclass;
 489
 490     /* assignments of primitive values are not checked here. */
 491     if (!c.any && !dest.any)
 492         return true;
 493
 494     /* primitive and reference types are not assignment compatible. */
 495     if (!c.any || !dest.any)
 496         return false;
 497
 498     /* the null type can be assigned to any type */
 499     if (TYPEINFO_IS_NULLTYPE(*value))
 500         return true;
 501
 502     /* uninitialized objects are not assignable */
 503     if (TYPEINFO_IS_NEWOBJECT(*value))
 504         return false;
 505
 506         if (IS_CLASSREF(c)) {
 507                 /* The value type is an unresolved class reference. */
 508                 classname = c.ref->name;
 509         }
 510         else {
 511                 classname = c.cls->name;
 512         }
 513
 514         if (IS_CLASSREF(dest)) {
 515                 /* the destination type is an unresolved class reference */
 516                 /* In this case we cannot tell a lot about assignability. */
 517
 518                 /* the common case of value and dest type having the same classname */
 519                 if (dest.ref->name == classname && !value->merged)
 520                         return true;
 521
 522                 /* we cannot tell if value is assignable to dest, so we */
 523                 /* leave it up to the resolving code to check this      */
 524                 return MAYBE;
 525         }
 526
 527         /* { we know that dest is a loaded class } */
 528
 529         if (IS_CLASSREF(c)) {
 530                 /* the value type is an unresolved class reference */
 531
 532                 /* the common case of value and dest type having the same classname */
 533                 if (dest.cls->name == classname)
 534                         return true;
 535
 536                 /* we cannot tell if value is assignable to dest, so we */
 537                 /* leave it up to the resolving code to check this      */
 538                 return MAYBE;
 539         }
 540
 541         /* { we know that both c and dest are loaded classes } */
 542
 543         TYPEINFO_ASSERT(!IS_CLASSREF(c));
 544         TYPEINFO_ASSERT(!IS_CLASSREF(dest));
 545
 546         cls = c.cls;
 547
 548         TYPEINFO_ASSERT(cls->loaded);
 549         TYPEINFO_ASSERT(dest.cls->loaded);
 550
 551         /* maybe we need to link the classes */
 552         if (!cls->linked)
 553                 link_class(cls); /* XXX */
 554         if (!dest.cls->linked)
 555                 link_class(dest.cls); /* XXX */
 556
 557         /* { we know that both c and dest are linked classes } */
 558         TYPEINFO_ASSERT(cls->linked);
 559         TYPEINFO_ASSERT(dest.cls->linked);
 560
 561     if (dest.cls->flags & ACC_INTERFACE) {
 562         /* We are assigning to an interface type. */
 563         return merged_implements_interface(cls,value->merged,dest.cls);
 564     }
 565
 566     if (CLASSINFO_IS_ARRAY(dest.cls)) {
 567                 arraydescriptor *arraydesc = dest.cls->vftbl->arraydesc;
 568                 int dimension = arraydesc->dimension;
 569                 classinfo *elementclass = (arraydesc->elementvftbl)
 570                         ? arraydesc->elementvftbl->class : NULL;
 571
 572         /* We are assigning to an array type. */
 573         if (!TYPEINFO_IS_ARRAY(*value))
 574             return false;
 575
 576         /* {Both value and dest.cls are array types.} */
 577
 578         /* value must have at least the dimension of dest.cls. */
 579         if (value->dimension < dimension)
 580             return false;
 581
 582         if (value->dimension > dimension) {
 583             /* value has higher dimension so we need to check
 584              * if its component array can be assigned to the
 585              * element type of dest.cls */
 586
 587                         if (!elementclass) return false;
 588
 589             if (elementclass->flags & ACC_INTERFACE) {
 590                 /* We are assigning to an interface type. */
 591                 return classinfo_implements_interface(pseudo_class_Arraystub,
 592                                                       elementclass);
 593             }
 594
 595             /* We are assigning to a class type. */
 596             return class_issubclass(pseudo_class_Arraystub,elementclass);
 597         }
 598
 599         /* {value and dest.cls have the same dimension} */
 600
 601         if (value->elementtype != arraydesc->elementtype)
 602             return false;
 603
 604         if (value->elementclass.any) {
 605             /* We are assigning an array of objects so we have to
 606              * check if the elements are assignable.
 607              */
 608
 609             if (elementclass->flags & ACC_INTERFACE) {
 610                 /* We are assigning to an interface type. */
 611
 612                 return merged_implements_interface(value->elementclass.cls,
 613                                                    value->merged,
 614                                                    elementclass);
 615             }
 616
 617             /* We are assigning to a class type. */
 618             return class_issubclass(value->elementclass.cls,elementclass);
 619         }
 620
 621         return true;
 622     }
 623
 624     /* {dest.cls is not an array} */
 625     /* {dest.cls is a loaded class} */
 626
 627         /* If there are any unresolved references in the merged list, we cannot */
 628         /* tell if the assignment will be ok.                                   */
 629         /* This can only happen when cls is java.lang.Object                    */
 630         if (cls == class_java_lang_Object && value->merged) {
 631                 classref_or_classinfo *mlist = value->merged->list;
 632                 int i = value->merged->count;
 633                 while (i--)
 634                         if (IS_CLASSREF(*mlist++))
 635                                 return MAYBE;
 636         }
 637
 638     /* We are assigning to a class type */
 639     if (cls->flags & ACC_INTERFACE)
 640         cls = class_java_lang_Object;
 641
 642     return class_issubclass(cls,dest.cls);
 643 }
 644
 645 /**********************************************************************/
 646 /* INITIALIZATION FUNCTIONS                                           */
 647 /* The following functions fill in uninitialized typeinfo structures. */
 648 /**********************************************************************/
 649
 650 bool
 651 typeinfo_init_class(typeinfo *info,classref_or_classinfo c)
 652 {
 653         char *utf_ptr;
 654         int len;
 655         classinfo *cls;
 656
 657         TYPEINFO_ASSERT(c.any);
 658         TYPEINFO_ASSERT(info);
 659
 660         /* if necessary, try to resolve lazily */
 661         if (!resolve_classref_or_classinfo(NULL /* XXX should now method */,
 662                                 c,resolveLazy,false,true,&cls))
 663         {
 664                 return false;
 665         }
 666
 667         if (cls) {
 668                 TYPEINFO_INIT_CLASSINFO(*info,cls);
 669                 return true;
 670         }
 671
 672         /* {the type could no be resolved lazily} */
 673
 674         info->typeclass.ref = c.ref;
 675         info->elementclass.any = NULL;
 676         info->dimension = 0;
 677         info->merged = NULL;
 678
 679         /* handle array type references */
 680         utf_ptr = c.ref->name->text;
 681         len = c.ref->name->blength;
 682         if (*utf_ptr == '[') {
 683                 /* count dimensions */
 684                 while (*utf_ptr == '[') {
 685                         utf_ptr++;
 686                         info->dimension++;
 687                         len--;
 688                 }
 689                 if (*utf_ptr == 'L') {
 690                         utf_ptr++;
 691                         len -= 2;
 692                         info->elementtype = ARRAYTYPE_OBJECT;
 693                         info->elementclass.ref = class_get_classref(c.ref->referer,utf_new(utf_ptr,len));
 694                 }
 695                 else {
 696                         /* an array with primitive element type */
 697                         /* should have been resolved above */
 698                         TYPEINFO_ASSERT(false);
 699                 }
 700         }
 701         return true;
 702 }
 703
 704 bool
 705 typeinfo_init_from_typedesc(typedesc *desc,u1 *type,typeinfo *info)
 706 {
 707         TYPEINFO_ASSERT(desc);
 708
 709 #ifdef TYPEINFO_VERBOSE
 710         fprintf(stderr,"typeinfo_init_from_typedesc(");
 711         descriptor_debug_print_typedesc(stderr,desc);
 712         fprintf(stderr,")\n");
 713 #endif
 714
 715         if (type)
 716                 *type = desc->type;
 717
 718         if (info) {
 719                 if (desc->type == TYPE_ADR) {
 720                         TYPEINFO_ASSERT(desc->classref);
 721                         if (!typeinfo_init_class(info,CLASSREF_OR_CLASSINFO(desc->classref)))
 722                                 return false;
 723                 }
 724                 else {
 725                         TYPEINFO_INIT_PRIMITIVE(*info);
 726                 }
 727         }
 728         return true;
 729 }
 730
 731 bool
 732 typeinfo_init_from_methoddesc(methoddesc *desc,u1 *typebuf,typeinfo *infobuf,
 733                               int buflen,bool twoword,
 734                               u1 *returntype,typeinfo *returntypeinfo)
 735 {
 736         int i;
 737     int args = 0;
 738
 739         TYPEINFO_ASSERT(desc);
 740         TYPEINFO_ASSERT(typebuf);
 741         TYPEINFO_ASSERT(infobuf);
 742
 743 #ifdef TYPEINFO_VERBOSE
 744         fprintf(stderr,"typeinfo_init_from_methoddesc(");
 745         descriptor_debug_print_methoddesc(stderr,desc);
 746         fprintf(stderr,")\n");
 747 #endif
 748
 749     /* check arguments */
 750     for (i=0; i<desc->paramcount; ++i) {
 751                 if (++args > buflen) {
 752                         log_text("Buffer too small for method arguments."); /* XXX */
 753                         assert(0);
 754                 }
 755
 756                 if (!typeinfo_init_from_typedesc(desc->paramtypes + i,typebuf++,infobuf++))
 757                         return false;
 758
 759                 if (twoword && (typebuf[-1] == TYPE_LONG || typebuf[-1] == TYPE_DOUBLE)) {
 760                         if (++args > buflen) {
 761                                 log_text("Buffer too small for method arguments."); /* XXX */
 762                                 assert(0);
 763                         }
 764
 765                         *typebuf++ = TYPE_VOID;
 766                         TYPEINFO_INIT_PRIMITIVE(*infobuf);
 767                         infobuf++;
 768                 }
 769     }
 770
 771     /* check returntype */
 772     if (returntype) {
 773                 if (!typeinfo_init_from_typedesc(&(desc->returntype),returntype,returntypeinfo))
 774                         return false;
 775         }
 776
 777         return true;
 778 }
 779
 780 bool
 781 typedescriptor_init_from_typedesc(typedescriptor *td,
 782                                                                   typedesc *desc)
 783 {
 784         td->type = desc->type;
 785         if (td->type == TYPE_ADR) {
 786                 if (!typeinfo_init_class(&(td->info),CLASSREF_OR_CLASSINFO(desc->classref)))
 787                         return false;
 788         }
 789         else {
 790                 TYPEINFO_INIT_PRIMITIVE(td->info);
 791         }
 792         return true;
 793 }
 794
 795 int
 796 typedescriptors_init_from_methoddesc(typedescriptor *td,
 797                                                                          methoddesc *desc,
 798                                                                          int buflen,bool twoword,int startindex,
 799                                                                          typedescriptor *returntype)
 800 {
 801         int i;
 802     int args = 0;
 803
 804     /* check arguments */
 805     for (i=startindex; i<desc->paramcount; ++i) {
 806                 if (++args > buflen) {
 807                         log_text("Buffer too small for method arguments."); /* XXX */
 808                         assert(0);
 809                 }
 810
 811                 if (!typedescriptor_init_from_typedesc(td,desc->paramtypes + i))
 812                         return -1;
 813                 td++;
 814
 815                 if (twoword && (td[-1].type == TYPE_LONG || td[-1].type == TYPE_DOUBLE)) {
 816                         if (++args > buflen) {
 817                                 log_text("Buffer too small for method arguments."); /* XXX */
 818                                 assert(0);
 819                         }
 820
 821                         td->type = TYPE_VOID;
 822                         TYPEINFO_INIT_PRIMITIVE(td->info);
 823                         td++;
 824                 }
 825     }
 826
 827     /* check returntype */
 828     if (returntype) {
 829                 if (!typedescriptor_init_from_typedesc(returntype,&(desc->returntype)))
 830                         return -1;
 831         }
 832
 833         return args;
 834 }
 835
 836 bool
 837 typeinfo_init_component(typeinfo *srcarray,typeinfo *dst)
 838 {
 839     if (TYPEINFO_IS_NULLTYPE(*srcarray)) {
 840         TYPEINFO_INIT_NULLTYPE(*dst);
 841         return true;
 842     }
 843
 844     if (!TYPEINFO_IS_ARRAY(*srcarray)) {
 845         log_text("Trying to access component of non-array"); /* XXX throw exception */
 846                 assert(0);
 847         }
 848
 849         if (IS_CLASSREF(srcarray->typeclass)) {
 850                 constant_classref *comp;
 851                 comp = class_get_classref_component_of(srcarray->typeclass.ref);
 852
 853                 if (comp) {
 854                         if (!typeinfo_init_class(dst,CLASSREF_OR_CLASSINFO(comp)))
 855                                 return false;
 856                 }
 857                 else {
 858                         TYPEINFO_INIT_PRIMITIVE(*dst);
 859                 }
 860         }
 861         else {
 862                 vftbl_t *comp;
 863
 864                 if (!srcarray->typeclass.cls->linked) {
 865                         if (!link_class(srcarray->typeclass.cls)) {
 866                                 return false;
 867                         }
 868                 }
 869
 870                 TYPEINFO_ASSERT(srcarray->typeclass.cls->vftbl);
 871                 TYPEINFO_ASSERT(srcarray->typeclass.cls->vftbl->arraydesc);
 872
 873                 comp = srcarray->typeclass.cls->vftbl->arraydesc->componentvftbl;
 874                 if (comp)
 875                         TYPEINFO_INIT_CLASSINFO(*dst,comp->class);
 876                 else
 877                         TYPEINFO_INIT_PRIMITIVE(*dst);
 878         }
 879
 880     dst->merged = srcarray->merged; /* XXX should we do a deep copy? */
 881         return true;
 882 }
 883
 884 void
 885 typeinfo_clone(typeinfo *src,typeinfo *dest)
 886 {
 887     int count;
 888     classref_or_classinfo *srclist,*destlist;
 889
 890     if (src == dest)
 891         return;
 892
 893     *dest = *src;
 894
 895     if (src->merged) {
 896         count = src->merged->count;
 897         TYPEINFO_ALLOCMERGED(dest->merged,count);
 898         dest->merged->count = count;
 899
 900         srclist = src->merged->list;
 901         destlist = dest->merged->list;
 902         while (count--)
 903             *destlist++ = *srclist++;
 904     }
 905 }
 906
 907 /**********************************************************************/
 908 /* MISCELLANEOUS FUNCTIONS                                            */
 909 /**********************************************************************/
 910
 911 void
 912 typeinfo_free(typeinfo *info)
 913 {
 914     TYPEINFO_FREEMERGED_IF_ANY(info->merged);
 915     info->merged = NULL;
 916 }
 917
 918 /**********************************************************************/
 919 /* MERGING FUNCTIONS                                                  */
 920 /* The following functions are used to merge the types represented by */
 921 /* two typeinfo structures into one typeinfo structure.               */
 922 /**********************************************************************/
 923
 924 static
 925 void
 926 typeinfo_merge_error(char *str,typeinfo *x,typeinfo *y) {
 927 #ifdef TYPEINFO_VERBOSE
 928     fprintf(stderr,"Error in typeinfo_merge: %s\n",str);
 929     fprintf(stderr,"Typeinfo x:\n");
 930     typeinfo_print(stderr,x,1);
 931     fprintf(stderr,"Typeinfo y:\n");
 932     typeinfo_print(stderr,y,1);
 933 #endif
 934
 935     log_text(str); /* XXX throw an exception */
 936         assert(0);
 937 }
 938
 939 /* Condition: clsx != clsy. */
 940 /* Returns: true if dest was changed (currently always true). */
 941 static
 942 bool
 943 typeinfo_merge_two(typeinfo *dest,classref_or_classinfo clsx,classref_or_classinfo clsy)
 944 {
 945         TYPEINFO_ASSERT(dest);
 946     TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
 947     TYPEINFO_ALLOCMERGED(dest->merged,2);
 948     dest->merged->count = 2;
 949
 950         TYPEINFO_ASSERT(clsx.any != clsy.any);
 951
 952     if (clsx.any < clsy.any) {
 953         dest->merged->list[0] = clsx;
 954         dest->merged->list[1] = clsy;
 955     }
 956     else {
 957         dest->merged->list[0] = clsy;
 958         dest->merged->list[1] = clsx;
 959     }
 960
 961     return true;
 962 }
 963
 964 /* Returns: true if dest was changed. */
 965 static
 966 bool
 967 typeinfo_merge_add(typeinfo *dest,typeinfo_mergedlist *m,classref_or_classinfo cls)
 968 {
 969     int count;
 970     typeinfo_mergedlist *newmerged;
 971     classref_or_classinfo *mlist,*newlist;
 972
 973     count = m->count;
 974     mlist = m->list;
 975
 976     /* Check if cls is already in the mergedlist m. */
 977     while (count--) {
 978         if ((mlist++)->any == cls.any) { /* XXX check equal classrefs? */
 979             /* cls is in the list, so m is the resulting mergedlist */
 980             if (dest->merged == m)
 981                 return false;
 982
 983             /* We have to copy the mergedlist */
 984             TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
 985             count = m->count;
 986             TYPEINFO_ALLOCMERGED(dest->merged,count);
 987             dest->merged->count = count;
 988             newlist = dest->merged->list;
 989             mlist = m->list;
 990             while (count--) {
 991                 *newlist++ = *mlist++;
 992             }
 993             return true;
 994         }
 995     }
 996
 997     /* Add cls to the mergedlist. */
 998     count = m->count;
 999     TYPEINFO_ALLOCMERGED(newmerged,count+1);
1000     newmerged->count = count+1;
1001     newlist = newmerged->list;
1002     mlist = m->list;
1003     while (count) {
1004         if (mlist->any > cls.any)
1005             break;
1006         *newlist++ = *mlist++;
1007         count--;
1008     }
1009     *newlist++ = cls;
1010     while (count--) {
1011         *newlist++ = *mlist++;
1012     }
1013
1014     /* Put the new mergedlist into dest. */
1015     TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1016     dest->merged = newmerged;
1017
1018     return true;
1019 }
1020
1021 /* Returns: true if dest was changed. */
1022 static
1023 bool
1024 typeinfo_merge_mergedlists(typeinfo *dest,typeinfo_mergedlist *x,
1025                            typeinfo_mergedlist *y)
1026 {
1027     int count = 0;
1028     int countx,county;
1029     typeinfo_mergedlist *temp,*result;
1030     classref_or_classinfo *clsx,*clsy,*newlist;
1031
1032     /* count the elements that will be in the resulting list */
1033     /* (Both lists are sorted, equal elements are counted only once.) */
1034     clsx = x->list;
1035     clsy = y->list;
1036     countx = x->count;
1037     county = y->count;
1038     while (countx && county) {
1039         if (clsx->any == clsy->any) {
1040             clsx++;
1041             clsy++;
1042             countx--;
1043             county--;
1044         }
1045         else if (clsx->any < clsy->any) {
1046             clsx++;
1047             countx--;
1048         }
1049         else {
1050             clsy++;
1051             county--;
1052         }
1053         count++;
1054     }
1055     count += countx + county;
1056
1057     /* {The new mergedlist will have count entries.} */
1058
1059     if ((x->count != count) && (y->count == count)) {
1060         temp = x; x = y; y = temp;
1061     }
1062     /* {If one of x,y is already the result it is x.} */
1063     if (x->count == count) {
1064         /* x->merged is equal to the result */
1065         if (x == dest->merged)
1066             return false;
1067
1068         if (!dest->merged || dest->merged->count != count) {
1069             TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1070             TYPEINFO_ALLOCMERGED(dest->merged,count);
1071             dest->merged->count = count;
1072         }
1073
1074         newlist = dest->merged->list;
1075         clsx = x->list;
1076         while (count--) {
1077             *newlist++ = *clsx++;
1078         }
1079         return true;
1080     }
1081
1082     /* {We have to merge two lists.} */
1083
1084     /* allocate the result list */
1085     TYPEINFO_ALLOCMERGED(result,count);
1086     result->count = count;
1087     newlist = result->list;
1088
1089     /* merge the sorted lists */
1090     clsx = x->list;
1091     clsy = y->list;
1092     countx = x->count;
1093     county = y->count;
1094     while (countx && county) {
1095         if (clsx->any == clsy->any) {
1096             *newlist++ = *clsx++;
1097             clsy++;
1098             countx--;
1099             county--;
1100         }
1101         else if (clsx->any < clsy->any) {
1102             *newlist++ = *clsx++;
1103             countx--;
1104         }
1105         else {
1106             *newlist++ = *clsy++;
1107             county--;
1108         }
1109     }
1110     while (countx--)
1111             *newlist++ = *clsx++;
1112     while (county--)
1113             *newlist++ = *clsy++;
1114
1115     /* replace the list in dest with the result list */
1116     TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1117     dest->merged = result;
1118
1119     return true;
1120 }
1121
1122 static
1123 bool
1124 typeinfo_merge_nonarrays(typeinfo *dest,
1125                          classref_or_classinfo *result,
1126                          classref_or_classinfo x,classref_or_classinfo y,
1127                          typeinfo_mergedlist *mergedx,
1128                          typeinfo_mergedlist *mergedy)
1129 {
1130         classref_or_classinfo t;
1131     classinfo *tcls,*common;
1132     typeinfo_mergedlist *tmerged;
1133     bool changed;
1134         utf *xname;
1135         utf *yname;
1136
1137         TYPEINFO_ASSERT(dest && result && x.any && y.any);
1138         TYPEINFO_ASSERT(x.cls != pseudo_class_Null);
1139         TYPEINFO_ASSERT(y.cls != pseudo_class_Null);
1140         TYPEINFO_ASSERT(x.cls != pseudo_class_New);
1141         TYPEINFO_ASSERT(y.cls != pseudo_class_New);
1142
1143         /*--------------------------------------------------*/
1144         /* common cases                                     */
1145         /*--------------------------------------------------*/
1146
1147     /* Common case 1: x and y are the same class or class reference */
1148     /* (This case is very simple unless *both* x and y really represent
1149      *  merges of subclasses of clsx==clsy.)
1150      */
1151     if ( (x.any == y.any) && (!mergedx || !mergedy) ) {
1152   return_simple_x:
1153         /* DEBUG */ /* log_text("return simple x"); */
1154         changed = (dest->merged != NULL);
1155         TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1156         dest->merged = NULL;
1157         *result = x;
1158         /* DEBUG */ /* log_text("returning"); */
1159         return changed;
1160     }
1161
1162         xname = (IS_CLASSREF(x)) ? x.ref->name : x.cls->name;
1163         yname = (IS_CLASSREF(y)) ? y.ref->name : y.cls->name;
1164
1165         /* Common case 2: xname == yname, at least one unresolved */
1166     if ((IS_CLASSREF(x) || IS_CLASSREF(y)) && (xname == yname))
1167         {
1168                 /* use the loaded one if any */
1169                 if (!IS_CLASSREF(y))
1170                         x = y;
1171                 goto return_simple_x;
1172     }
1173
1174         /*--------------------------------------------------*/
1175         /* non-trivial cases                                */
1176         /*--------------------------------------------------*/
1177
1178 #ifdef TYPEINFO_VERBOSE
1179         {
1180                 typeinfo dbgx,dbgy;
1181                 fprintf(stderr,"merge_nonarrays:\n");
1182                 fprintf(stderr,"    ");if(IS_CLASSREF(x))fprintf(stderr,"<ref>");utf_fprint(stderr,xname);fprintf(stderr,"\n");
1183                 fprintf(stderr,"    ");if(IS_CLASSREF(y))fprintf(stderr,"<ref>");utf_fprint(stderr,yname);fprintf(stderr,"\n");
1184                 fflush(stderr);
1185                 TYPEINFO_INIT_CLASSREF_OR_CLASSINFO(dbgx,x);
1186                 dbgx.merged = mergedx;
1187                 TYPEINFO_INIT_CLASSREF_OR_CLASSINFO(dbgy,y);
1188                 dbgy.merged = mergedy;
1189                 typeinfo_print(stderr,&dbgx,4);
1190                 fprintf(stderr,"  with:\n");
1191                 typeinfo_print(stderr,&dbgy,4);
1192         }
1193 #endif
1194
1195         TYPEINFO_ASSERT(IS_CLASSREF(x) || x.cls->loaded);
1196         TYPEINFO_ASSERT(IS_CLASSREF(y) || y.cls->loaded);
1197
1198     /* If y is unresolved or an interface, swap x and y. */
1199     if (IS_CLASSREF(y) || (!IS_CLASSREF(x) && y.cls->flags & ACC_INTERFACE))
1200         {
1201         t = x; x = y; y = t;
1202         tmerged = mergedx; mergedx = mergedy; mergedy = tmerged;
1203     }
1204
1205     /* {We know: If only one of x,y is unresolved it is x,} */
1206     /* {         If both x,y are resolved and only one of x,y is an interface it is x.} */
1207
1208         if (IS_CLASSREF(x)) {
1209                 /* {We know: x and y have different class names} */
1210
1211         /* Check if we are merging an unresolved type with java.lang.Object */
1212         if (y.cls == class_java_lang_Object && !mergedy) {
1213             x = y;
1214             goto return_simple_x;
1215         }
1216
1217                 common = class_java_lang_Object;
1218                 goto merge_with_simple_x;
1219         }
1220
1221         /* {We know: both x and y are resolved} */
1222     /* {We know: If only one of x,y is an interface it is x.} */
1223
1224         TYPEINFO_ASSERT(!IS_CLASSREF(x) && !IS_CLASSREF(y));
1225         TYPEINFO_ASSERT(x.cls->loaded);
1226         TYPEINFO_ASSERT(y.cls->loaded);
1227
1228     /* Handle merging of interfaces: */
1229     if (x.cls->flags & ACC_INTERFACE) {
1230         /* {x.cls is an interface and mergedx == NULL.} */
1231
1232         if (y.cls->flags & ACC_INTERFACE) {
1233             /* We are merging two interfaces. */
1234             /* {mergedy == NULL} */
1235
1236             /* {We know that x.cls!=y.cls (see common case at beginning.)} */
1237             result->cls = class_java_lang_Object;
1238             return typeinfo_merge_two(dest,x,y);
1239         }
1240
1241         /* {We know: x is an interface, y is a class.} */
1242
1243         /* Check if we are merging an interface with java.lang.Object */
1244         if (y.cls == class_java_lang_Object && !mergedy) {
1245             x = y;
1246             goto return_simple_x;
1247         }
1248
1249         /* If the type y implements x then the result of the merge
1250          * is x regardless of mergedy.
1251          */
1252
1253                 /* we may have to link the classes */
1254                 if (!x.cls->linked)
1255                         link_class(x.cls); /* XXX */
1256                 if (!y.cls->linked)
1257                         link_class(y.cls); /* XXX */
1258
1259                 TYPEINFO_ASSERT(x.cls->linked);
1260                 TYPEINFO_ASSERT(y.cls->linked);
1261
1262         if (CLASSINFO_IMPLEMENTS_INTERFACE(y.cls,x.cls->index)
1263             || mergedlist_implements_interface(mergedy,x.cls))
1264         {
1265             /* y implements x, so the result of the merge is x. */
1266             goto return_simple_x;
1267         }
1268
1269         /* {We know: x is an interface, the type y a class or a merge
1270          * of subclasses and does not implement x.} */
1271
1272         /* There may still be superinterfaces of x which are implemented
1273          * by y, too, so we have to add x.cls to the mergedlist.
1274          */
1275
1276         /* if x has no superinterfaces we could return a simple java.lang.Object */
1277
1278         common = class_java_lang_Object;
1279         goto merge_with_simple_x;
1280     }
1281
1282     /* {We know: x and y are classes (not interfaces).} */
1283
1284         /* we may have to link the classes */
1285         if (!x.cls->linked)
1286                 link_class(x.cls); /* XXX */
1287         if (!y.cls->linked)
1288                 link_class(y.cls); /* XXX */
1289
1290         TYPEINFO_ASSERT(x.cls->linked);
1291         TYPEINFO_ASSERT(y.cls->linked);
1292
1293     /* If *x is deeper in the inheritance hierarchy swap x and y. */
1294     if (x.cls->index > y.cls->index) {
1295         t = x; x = y; y = t;
1296         tmerged = mergedx; mergedx = mergedy; mergedy = tmerged;
1297     }
1298
1299     /* {We know: y is at least as deep in the hierarchy as x.} */
1300
1301     /* Find nearest common anchestor for the classes. */
1302     common = x.cls;
1303     tcls = y.cls;
1304     while (tcls->index > common->index)
1305         tcls = tcls->super.cls;
1306     while (common != tcls) {
1307         common = common->super.cls;
1308         tcls = tcls->super.cls;
1309     }
1310
1311     /* {common == nearest common anchestor of x and y.} */
1312
1313     /* If x.cls==common and x is a whole class (not a merge of subclasses)
1314      * then the result of the merge is x.
1315      */
1316     if (x.cls == common && !mergedx) {
1317         goto return_simple_x;
1318     }
1319
1320     if (mergedx) {
1321         result->cls = common;
1322         if (mergedy)
1323             return typeinfo_merge_mergedlists(dest,mergedx,mergedy);
1324         else
1325             return typeinfo_merge_add(dest,mergedx,y);
1326     }
1327
1328 merge_with_simple_x:
1329     result->cls = common;
1330     if (mergedy)
1331         return typeinfo_merge_add(dest,mergedy,x);
1332     else
1333         return typeinfo_merge_two(dest,x,y);
1334 }
1335
1336 /* Condition: *dest must be a valid initialized typeinfo. */
1337 /* Condition: dest != y. */
1338 /* Returns: true if dest was changed. */
1339 bool
1340 typeinfo_merge(typeinfo *dest,typeinfo* y)
1341 {
1342     typeinfo *x;
1343     typeinfo *tmp;
1344     classref_or_classinfo common;
1345     classref_or_classinfo elementclass;
1346     int dimension;
1347     int elementtype;
1348     bool changed;
1349
1350         /*--------------------------------------------------*/
1351         /* fast checks                                      */
1352         /*--------------------------------------------------*/
1353
1354     /* Merging something with itself is a nop */
1355     if (dest == y)
1356         return false;
1357
1358     /* Merging two returnAddress types is ok. */
1359         /* Merging two different returnAddresses never happens, as the verifier */
1360         /* keeps them separate in order to check all the possible return paths  */
1361         /* from JSR subroutines.                                                */
1362     if (!dest->typeclass.any && !y->typeclass.any) {
1363                 TYPEINFO_ASSERT(TYPEINFO_RETURNADDRESS(*dest) ==  TYPEINFO_RETURNADDRESS(*y));
1364         return false;
1365         }
1366
1367     /* Primitive types cannot be merged with reference types */
1368         /* XXX only check this in debug mode? */
1369     if (!dest->typeclass.any || !y->typeclass.any)
1370         typeinfo_merge_error("Trying to merge primitive types.",dest,y);
1371
1372     /* handle uninitialized object types */
1373     if (TYPEINFO_IS_NEWOBJECT(*dest) || TYPEINFO_IS_NEWOBJECT(*y)) {
1374         if (!TYPEINFO_IS_NEWOBJECT(*dest) || !TYPEINFO_IS_NEWOBJECT(*y))
1375             typeinfo_merge_error("Trying to merge uninitialized object type.",dest,y);
1376         if (TYPEINFO_NEWOBJECT_INSTRUCTION(*dest)
1377             != TYPEINFO_NEWOBJECT_INSTRUCTION(*y))
1378             typeinfo_merge_error("Trying to merge different uninitialized objects.",dest,y);
1379         return false;
1380     }
1381
1382         /*--------------------------------------------------*/
1383         /* common cases                                     */
1384         /*--------------------------------------------------*/
1385
1386     /* Common case: dest and y are the same class or class reference */
1387     /* (This case is very simple unless *both* dest and y really represent
1388      *  merges of subclasses of class dest==class y.)
1389      */
1390     if ((dest->typeclass.any == y->typeclass.any) && (!dest->merged || !y->merged)) {
1391 return_simple:
1392         changed = (dest->merged != NULL);
1393         TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1394         dest->merged = NULL;
1395         return changed;
1396     }
1397
1398     /* Handle null types: */
1399     if (TYPEINFO_IS_NULLTYPE(*y)) {
1400         return false;
1401     }
1402     if (TYPEINFO_IS_NULLTYPE(*dest)) {
1403         TYPEINFO_FREEMERGED_IF_ANY(dest->merged);
1404         TYPEINFO_CLONE(*y,*dest);
1405         return true;
1406     }
1407
1408         /* Common case: two types with the same name, at least one unresolved */
1409         if (IS_CLASSREF(dest->typeclass)) {
1410                 if (IS_CLASSREF(y->typeclass)) {
1411                         if (dest->typeclass.ref->name == y->typeclass.ref->name)
1412                                 goto return_simple;
1413                 }
1414                 else {
1415                         /* XXX should we take y instead of dest here? */
1416                         if (dest->typeclass.ref->name == y->typeclass.cls->name)
1417                                 goto return_simple;
1418                 }
1419         }
1420         else {
1421                 if (IS_CLASSREF(y->typeclass)
1422                     && (dest->typeclass.cls->name == y->typeclass.ref->name))
1423                 {
1424                         goto return_simple;
1425                 }
1426         }
1427
1428         /*--------------------------------------------------*/
1429         /* non-trivial cases                                */
1430         /*--------------------------------------------------*/
1431
1432 #ifdef TYPEINFO_VERBOSE
1433         fprintf(stderr,"merge:\n");
1434     typeinfo_print(stderr,dest,4);
1435     typeinfo_print(stderr,y,4);
1436 #endif
1437
1438     /* This function uses x internally, so x and y can be swapped
1439      * without changing dest. */
1440     x = dest;
1441     changed = false;
1442
1443     /* Handle merging of arrays: */
1444     if (TYPEINFO_IS_ARRAY(*x) && TYPEINFO_IS_ARRAY(*y)) {
1445
1446         /* Make x the one with lesser dimension */
1447         if (x->dimension > y->dimension) {
1448             tmp = x; x = y; y = tmp;
1449         }
1450
1451         /* If one array (y) has higher dimension than the other,
1452          * interpret it as an array (same dim. as x) of Arraystubs. */
1453         if (x->dimension < y->dimension) {
1454             dimension = x->dimension;
1455             elementtype = ARRAYTYPE_OBJECT;
1456             elementclass.cls = pseudo_class_Arraystub;
1457         }
1458         else {
1459             dimension = y->dimension;
1460             elementtype = y->elementtype;
1461             elementclass = y->elementclass;
1462         }
1463
1464         /* {The arrays are of the same dimension.} */
1465
1466         if (x->elementtype != elementtype) {
1467             /* Different element types are merged, so the resulting array
1468              * type has one accessible dimension less. */
1469             if (--dimension == 0) {
1470                 common.cls = pseudo_class_Arraystub;
1471                 elementtype = 0;
1472                 elementclass.any = NULL;
1473             }
1474             else {
1475                 common.cls = class_multiarray_of(dimension,pseudo_class_Arraystub,true);
1476                                 if (!common.cls) {
1477                                         log_text("XXX Coult not create array class");
1478                                         assert(0);
1479                                 }
1480
1481                 elementtype = ARRAYTYPE_OBJECT;
1482                 elementclass.cls = pseudo_class_Arraystub;
1483             }
1484         }
1485         else {
1486             /* {The arrays have the same dimension and elementtype.} */
1487
1488             if (elementtype == ARRAYTYPE_OBJECT) {
1489                 /* The elements are references, so their respective
1490                  * types must be merged.
1491                  */
1492                 changed |= typeinfo_merge_nonarrays(dest,
1493                                                     &elementclass,
1494                                                     x->elementclass,
1495                                                     elementclass,
1496                                                     x->merged,y->merged);
1497
1498                 /* DEBUG */ /* log_text("finding resulting array class: "); */
1499                                 if (IS_CLASSREF(elementclass))
1500                                         common.ref = class_get_classref_multiarray_of(dimension,elementclass.ref);
1501                                 else {
1502                                         common.cls = class_multiarray_of(dimension,elementclass.cls,true);
1503                                         if (!common.cls) {
1504                                                 log_text("XXX Coult not create array class");
1505                                                 assert(0);
1506                                         }
1507                                 }
1508                 /* DEBUG */ /* utf_display(common->name); printf("\n"); */
1509             }
1510                         else {
1511                                 common.any = y->typeclass.any;
1512                         }
1513         }
1514     }
1515     else {
1516         /* {We know that at least one of x or y is no array, so the
1517          *  result cannot be an array.} */
1518
1519         changed |= typeinfo_merge_nonarrays(dest,
1520                                             &common,
1521                                             x->typeclass,y->typeclass,
1522                                             x->merged,y->merged);
1523
1524         dimension = 0;
1525         elementtype = 0;
1526         elementclass.any = NULL;
1527     }
1528
1529     /* Put the new values into dest if neccessary. */
1530
1531     if (dest->typeclass.any != common.any) {
1532         dest->typeclass.any = common.any;
1533         changed = true;
1534     }
1535     if (dest->dimension != dimension) {
1536         dest->dimension = dimension;
1537         changed = true;
1538     }
1539     if (dest->elementtype != elementtype) {
1540         dest->elementtype = elementtype;
1541         changed = true;
1542     }
1543     if (dest->elementclass.any != elementclass.any) {
1544         dest->elementclass.any = elementclass.any;
1545         changed = true;
1546     }
1547
1548     return changed;
1549 }
1550
1551
1552 /**********************************************************************/
1553 /* DEBUGGING HELPERS                                                  */
1554 /**********************************************************************/
1555
1556 #ifdef TYPEINFO_DEBUG
1557
1558 #if 0
1559 static int
1560 typeinfo_test_compare(classref_or_classinfo *a,classref_or_classinfo *b)
1561 {
1562     if (a->any == b->any) return 0;
1563     if (a->any < b->any) return -1;
1564     return +1;
1565 }
1566
1567 static void
1568 typeinfo_test_parse(typeinfo *info,char *str)
1569 {
1570     int num;
1571     int i;
1572     typeinfo *infobuf;
1573     u1 *typebuf;
1574     int returntype;
1575     utf *desc = utf_new_char(str);
1576
1577     num = typeinfo_count_method_args(desc,false);
1578     if (num) {
1579         typebuf = DMNEW(u1,num);
1580         infobuf = DMNEW(typeinfo,num);
1581
1582         typeinfo_init_from_method_args(desc,typebuf,infobuf,num,false,
1583                                        &returntype,info);
1584
1585         TYPEINFO_ALLOCMERGED(info->merged,num);
1586         info->merged->count = num;
1587
1588         for (i=0; i<num; ++i) {
1589             if (typebuf[i] != TYPE_ADDRESS) {
1590                 log_text("non-reference type in mergedlist");
1591                                 assert(0);
1592                         }
1593
1594             info->merged->list[i].any = infobuf[i].typeclass.any;
1595         }
1596         qsort(info->merged->list,num,sizeof(classref_or_classinfo),
1597               (int(*)(const void *,const void *))&typeinfo_test_compare);
1598     }
1599     else {
1600         typeinfo_init_from_method_args(desc,NULL,NULL,0,false,
1601                                        &returntype,info);
1602     }
1603 }
1604 #endif
1605
1606 #define TYPEINFO_TEST_BUFLEN  4000
1607
1608 static bool
1609 typeinfo_equal(typeinfo *x,typeinfo *y)
1610 {
1611     int i;
1612
1613     if (x->typeclass.any != y->typeclass.any) return false;
1614     if (x->dimension != y->dimension) return false;
1615     if (x->dimension) {
1616         if (x->elementclass.any != y->elementclass.any) return false;
1617         if (x->elementtype != y->elementtype) return false;
1618     }
1619
1620     if (TYPEINFO_IS_NEWOBJECT(*x))
1621         if (TYPEINFO_NEWOBJECT_INSTRUCTION(*x)
1622             != TYPEINFO_NEWOBJECT_INSTRUCTION(*y))
1623             return false;
1624
1625     if (x->merged || y->merged) {
1626         if (!(x->merged && y->merged)) return false;
1627         if (x->merged->count != y->merged->count) return false;
1628         for (i=0; i<x->merged->count; ++i)
1629             if (x->merged->list[i].any != y->merged->list[i].any)
1630                 return false;
1631     }
1632     return true;
1633 }
1634
1635 static void
1636 typeinfo_testmerge(typeinfo *a,typeinfo *b,typeinfo *result,int *failed)
1637 {
1638     typeinfo dest;
1639     bool changed,changed_should_be;
1640
1641     TYPEINFO_CLONE(*a,dest);
1642
1643     printf("\n          ");
1644     typeinfo_print_short(stdout,&dest);
1645     printf("\n          ");
1646     typeinfo_print_short(stdout,b);
1647     printf("\n");
1648
1649     changed = (typeinfo_merge(&dest,b)) ? 1 : 0;
1650     changed_should_be = (!typeinfo_equal(&dest,a)) ? 1 : 0;
1651
1652     printf("          %s\n",(changed) ? "changed" : "=");
1653
1654     if (typeinfo_equal(&dest,result)) {
1655         printf("OK        ");
1656         typeinfo_print_short(stdout,&dest);
1657         printf("\n");
1658         if (changed != changed_should_be) {
1659             printf("WRONG RETURN VALUE!\n");
1660             (*failed)++;
1661         }
1662     }
1663     else {
1664         printf("RESULT    ");
1665         typeinfo_print_short(stdout,&dest);
1666         printf("\n");
1667         printf("SHOULD BE ");
1668         typeinfo_print_short(stdout,result);
1669         printf("\n");
1670         (*failed)++;
1671     }
1672 }
1673
1674 #if 0
1675 static void
1676 typeinfo_inc_dimension(typeinfo *info)
1677 {
1678     if (info->dimension++ == 0) {
1679         info->elementtype = ARRAYTYPE_OBJECT;
1680         info->elementclass = info->typeclass;
1681     }
1682     info->typeclass = class_array_of(info->typeclass,true);
1683 }
1684 #endif
1685
1686 #define TYPEINFO_TEST_MAXDIM  10
1687
1688 static void
1689 typeinfo_testrun(char *filename)
1690 {
1691     char buf[TYPEINFO_TEST_BUFLEN];
1692     char bufa[TYPEINFO_TEST_BUFLEN];
1693     char bufb[TYPEINFO_TEST_BUFLEN];
1694     char bufc[TYPEINFO_TEST_BUFLEN];
1695     typeinfo a,b,c;
1696     int maxdim;
1697     int failed = 0;
1698     FILE *file = fopen(filename,"rt");
1699         int res;
1700
1701     if (!file) {
1702         log_text("could not open typeinfo test file");
1703                 assert(0);
1704         }
1705
1706     while (fgets(buf,TYPEINFO_TEST_BUFLEN,file)) {
1707         if (buf[0] == '#' || !strlen(buf))
1708             continue;
1709
1710         res = sscanf(buf,"%s\t%s\t%s\n",bufa,bufb,bufc);
1711         if (res != 3 || !strlen(bufa) || !strlen(bufb) || !strlen(bufc)) {
1712             log_text("Invalid line in typeinfo test file (none of empty, comment or test)");
1713                         assert(0);
1714                 }
1715
1716 #if 0
1717         typeinfo_test_parse(&a,bufa);
1718         typeinfo_test_parse(&b,bufb);
1719         typeinfo_test_parse(&c,bufc);
1720 #endif
1721 #if 0
1722         do {
1723 #endif
1724             typeinfo_testmerge(&a,&b,&c,&failed); /* check result */
1725             typeinfo_testmerge(&b,&a,&c,&failed); /* check commutativity */
1726
1727             if (TYPEINFO_IS_NULLTYPE(a)) break;
1728             if (TYPEINFO_IS_NULLTYPE(b)) break;
1729             if (TYPEINFO_IS_NULLTYPE(c)) break;
1730
1731             maxdim = a.dimension;
1732             if (b.dimension > maxdim) maxdim = b.dimension;
1733             if (c.dimension > maxdim) maxdim = c.dimension;
1734
1735 #if 0
1736             if (maxdim < TYPEINFO_TEST_MAXDIM) {
1737                 typeinfo_inc_dimension(&a);
1738                 typeinfo_inc_dimension(&b);
1739                 typeinfo_inc_dimension(&c);
1740             }
1741         } while (maxdim < TYPEINFO_TEST_MAXDIM);
1742 #endif
1743     }
1744
1745     fclose(file);
1746
1747     if (failed) {
1748         fprintf(stderr,"Failed typeinfo_merge tests: %d\n",failed);
1749         log_text("Failed test");
1750                 assert(0);
1751     }
1752 }
1753
1754 void
1755 typeinfo_test()
1756 {
1757     log_text("Running typeinfo test file...");
1758     typeinfo_testrun("typeinfo.tst");
1759     log_text("Finished typeinfo test file.");
1760 }
1761
1762 #if 0
1763 void
1764 typeinfo_init_from_fielddescriptor(typeinfo *info,char *desc)
1765 {
1766     typeinfo_init_from_descriptor(info,desc,desc+strlen(desc));
1767 }
1768 #endif
1769
1770 #define TYPEINFO_MAXINDENT  80
1771
1772 void
1773 typeinfo_print_class(FILE *file,classref_or_classinfo c)
1774 {
1775         /*fprintf(file,"<class %p>",c.any);*/
1776
1777         if (!c.any) {
1778                 fprintf(file,"<null>");
1779         }
1780         else {
1781                 if (IS_CLASSREF(c)) {
1782                         fprintf(file,"<ref>");
1783                         utf_fprint(file,c.ref->name);
1784                 }
1785                 else {
1786                         utf_fprint(file,c.cls->name);
1787                 }
1788         }
1789 }
1790
1791 void
1792 typeinfo_print(FILE *file,typeinfo *info,int indent)
1793 {
1794     int i;
1795     char ind[TYPEINFO_MAXINDENT + 1];
1796     instruction *ins;
1797         basicblock *bptr;
1798
1799     if (indent > TYPEINFO_MAXINDENT) indent = TYPEINFO_MAXINDENT;
1800
1801     for (i=0; i<indent; ++i)
1802         ind[i] = ' ';
1803     ind[i] = (char) 0;
1804
1805     if (TYPEINFO_IS_PRIMITIVE(*info)) {
1806                 bptr = (basicblock*) TYPEINFO_RETURNADDRESS(*info);
1807                 if (bptr)
1808                         fprintf(file,"%sreturnAddress (L%03d)\n",ind,bptr->debug_nr);
1809                 else
1810                         fprintf(file,"%sprimitive\n",ind);
1811         return;
1812     }
1813
1814     if (TYPEINFO_IS_NULLTYPE(*info)) {
1815         fprintf(file,"%snull\n",ind);
1816         return;
1817     }
1818
1819     if (TYPEINFO_IS_NEWOBJECT(*info)) {
1820         ins = (instruction *)TYPEINFO_NEWOBJECT_INSTRUCTION(*info);
1821         if (ins) {
1822             fprintf(file,"%sNEW(%p):",ind,(void*)ins);
1823                         typeinfo_print_class(file,CLASSREF_OR_CLASSINFO(ins[-1].val.a));
1824             fprintf(file,"\n");
1825         }
1826         else {
1827             fprintf(file,"%sNEW(this)",ind);
1828         }
1829         return;
1830     }
1831
1832     fprintf(file,"%sClass:      ",ind);
1833         typeinfo_print_class(file,info->typeclass);
1834     fprintf(file,"\n");
1835
1836     if (TYPEINFO_IS_ARRAY(*info)) {
1837         fprintf(file,"%sDimension:    %d",ind,(int)info->dimension);
1838         fprintf(file,"\n%sElements:     ",ind);
1839         switch (info->elementtype) {
1840           case ARRAYTYPE_INT     : fprintf(file,"int\n"); break;
1841           case ARRAYTYPE_LONG    : fprintf(file,"long\n"); break;
1842           case ARRAYTYPE_FLOAT   : fprintf(file,"float\n"); break;
1843           case ARRAYTYPE_DOUBLE  : fprintf(file,"double\n"); break;
1844           case ARRAYTYPE_BYTE    : fprintf(file,"byte\n"); break;
1845           case ARRAYTYPE_CHAR    : fprintf(file,"char\n"); break;
1846           case ARRAYTYPE_SHORT   : fprintf(file,"short\n"); break;
1847           case ARRAYTYPE_BOOLEAN : fprintf(file,"boolean\n"); break;
1848
1849           case ARRAYTYPE_OBJECT:
1850                           typeinfo_print_class(file,info->elementclass);
1851               fprintf(file,"\n");
1852               break;
1853
1854           default:
1855               fprintf(file,"INVALID ARRAYTYPE!\n");
1856         }
1857     }
1858
1859     if (info->merged) {
1860         fprintf(file,"%sMerged:     ",ind);
1861         for (i=0; i<info->merged->count; ++i) {
1862             if (i) fprintf(file,", ");
1863                         typeinfo_print_class(file,info->merged->list[i]);
1864         }
1865         fprintf(file,"\n");
1866     }
1867 }
1868
1869 void
1870 typeinfo_print_short(FILE *file,typeinfo *info)
1871 {
1872     int i;
1873     instruction *ins;
1874         basicblock *bptr;
1875
1876         /*fprintf(file,"<typeinfo %p>",info);*/
1877
1878         if (!info) {
1879                 fprintf(file,"(typeinfo*)NULL");
1880                 return;
1881         }
1882
1883     if (TYPEINFO_IS_PRIMITIVE(*info)) {
1884                 bptr = (basicblock*) TYPEINFO_RETURNADDRESS(*info);
1885                 if (bptr)
1886                         fprintf(file,"ret(L%03d)",bptr->debug_nr);
1887                 else
1888                         fprintf(file,"primitive");
1889         return;
1890     }
1891
1892     if (TYPEINFO_IS_NULLTYPE(*info)) {
1893         fprintf(file,"null");
1894         return;
1895     }
1896
1897     if (TYPEINFO_IS_NEWOBJECT(*info)) {
1898         ins = (instruction *)TYPEINFO_NEWOBJECT_INSTRUCTION(*info);
1899         if (ins) {
1900                         /*fprintf(file,"<ins %p>",ins);*/
1901             fprintf(file,"NEW(%p):",(void*)ins);
1902                         typeinfo_print_class(file,CLASSREF_OR_CLASSINFO(ins[-1].val.a));
1903         }
1904         else
1905             fprintf(file,"NEW(this)");
1906         return;
1907     }
1908
1909     typeinfo_print_class(file,info->typeclass);
1910
1911     if (info->merged) {
1912         fprintf(file,"{");
1913         for (i=0; i<info->merged->count; ++i) {
1914             if (i) fprintf(file,",");
1915                         typeinfo_print_class(file,info->merged->list[i]);
1916         }
1917         fprintf(file,"}");
1918     }
1919 }
1920
1921 void
1922 typeinfo_print_type(FILE *file,int type,typeinfo *info)
1923 {
1924     switch (type) {
1925       case TYPE_VOID:   fprintf(file,"V"); break;
1926       case TYPE_INT:    fprintf(file,"I"); break;
1927       case TYPE_FLOAT:  fprintf(file,"F"); break;
1928       case TYPE_DOUBLE: fprintf(file,"D"); break;
1929       case TYPE_LONG:   fprintf(file,"J"); break;
1930       case TYPE_ADDRESS:
1931                   typeinfo_print_short(file,info);
1932           break;
1933
1934       default:
1935           fprintf(file,"!");
1936     }
1937 }
1938
1939 void
1940 typeinfo_print_stacktype(FILE *file,int type,typeinfo *info)
1941 {
1942         TYPEINFO_ASSERT(file);
1943         TYPEINFO_ASSERT(type != TYPE_ADDRESS || info != NULL);
1944         if (type == TYPE_ADDRESS && TYPEINFO_IS_PRIMITIVE(*info)) {
1945                 typeinfo_retaddr_set *set = (typeinfo_retaddr_set*)
1946                         TYPEINFO_RETURNADDRESS(*info);
1947                 if (set) {
1948                         fprintf(file,"ret(L%03d",((basicblock*)(set->addr))->debug_nr);
1949                         set = set->alt;
1950                         while (set) {
1951                                 fprintf(file,"|L%03d",((basicblock*)(set->addr))->debug_nr);
1952                                 set = set->alt;
1953                         }
1954                 }
1955                 else {
1956                         fprintf(file,"ret(<NULL>");
1957                 }
1958                 fprintf(file,")");
1959         }
1960         else
1961                 typeinfo_print_type(file,type,info);
1962 }
1963
1964 void
1965 typedescriptor_print(FILE *file,typedescriptor *td)
1966 {
1967         typeinfo_print_type(file,td->type,&(td->info));
1968 }
1969
1970 void
1971 typevector_print(FILE *file,typevector *vec,int size)
1972 {
1973     int i;
1974
1975         fprintf(file,"[%d]",vec->k);
1976     for (i=0; i<size; ++i) {
1977                 fprintf(file," %d=",i);
1978         typedescriptor_print(file,vec->td + i);
1979     }
1980 }
1981
1982 void
1983 typevectorset_print(FILE *file,typevector *set,int size)
1984 {
1985     int i;
1986         typevector *vec;
1987
1988         fprintf(file,"[%d",set->k);
1989         vec = set->alt;
1990         while (vec) {
1991                 fprintf(file,"|%d",vec->k);
1992                 vec = vec->alt;
1993         }
1994         fprintf(file,"]");
1995
1996     for (i=0; i<size; ++i) {
1997                 fprintf(file," %d=",i);
1998         typedescriptor_print(file,set->td + i);
1999                 vec = set->alt;
2000                 while (vec) {
2001                         fprintf(file,"|");
2002                         typedescriptor_print(file,vec->td + i);
2003                         vec = vec->alt;
2004                 }
2005     }
2006 }
2007
2008 #endif /* TYPEINFO_DEBUG */
2009
2010
2011 /*
2012  * These are local overrides for various environment variables in Emacs.
2013  * Please do not remove this and leave it at the end of the file, where
2014  * Emacs will automagically detect them.
2015  * ---------------------------------------------------------------------
2016  * Local variables:
2017  * mode: c
2018  * indent-tabs-mode: t
2019  * c-basic-offset: 4
2020  * tab-width: 4
2021  * End:
2022  */