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