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