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