src/vm/jit/verify/typeinfo.c

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