gcc/java/verify-impl.c

   1 /* Copyright (C) 2001, 2002, 2003, 2004, 2005  Free Software Foundation
   2
   3    This file is part of libgcj.
   4
   5 This software is copyrighted work licensed under the terms of the
   6 Libgcj License.  Please consult the file "LIBGCJ_LICENSE" for
   7 details.  */
   8
   9 /* Written by Tom Tromey <tromey@redhat.com>  */
  10
  11 /* Uncomment this to enable debugging output.  */
  12 /* #define VERIFY_DEBUG */
  13
  14 #include "config.h"
  15
  16 #include "verify.h"
  17
  18 /* Hack to work around namespace pollution from java-tree.h.  */
  19 #undef current_class
  20
  21 #ifdef VERIFY_DEBUG
  22 #include <stdio.h>
  23 #endif /* VERIFY_DEBUG */
  24
  25 /* This is used to mark states which are not scheduled for
  26    verification. */
  27 #define INVALID_STATE ((state *) -1)
  28
  29 #ifdef VERIFY_DEBUG
  30 static void
  31 debug_print (const char *fmt, ...)
  32 {
  33   va_list ap;
  34   va_start (ap, fmt);
  35   vfprintf (stderr, fmt, ap);
  36   va_end (ap);
  37 }
  38 #else
  39 static void
  40 debug_print (const char *fmt ATTRIBUTE_UNUSED, ...)
  41 {
  42 }
  43 #endif /* VERIFY_DEBUG */
  44
  45 /* This started as a fairly ordinary verifier, and for the most part
  46    it remains so.  It works in the obvious way, by modeling the effect
  47    of each opcode as it is encountered.  For most opcodes, this is a
  48    straightforward operation.
  49
  50    This verifier does not do type merging.  It used to, but this
  51    results in difficulty verifying some relatively simple code
  52    involving interfaces, and it pushed some verification work into the
  53    interpreter.
  54
  55    Instead of merging reference types, when we reach a point where two
  56    flows of control merge, we simply keep the union of reference types
  57    from each branch.  Then, when we need to verify a fact about a
  58    reference on the stack (e.g., that it is compatible with the
  59    argument type of a method), we check to ensure that all possible
  60    types satisfy the requirement.
  61
  62    Another area this verifier differs from the norm is in its handling
  63    of subroutines.  The JVM specification has some confusing things to
  64    say about subroutines.  For instance, it makes claims about not
  65    allowing subroutines to merge and it rejects recursive subroutines.
  66    For the most part these are red herrings; we used to try to follow
  67    these things but they lead to problems.  For example, the notion of
  68    "being in a subroutine" is not well-defined: is an exception
  69    handler in a subroutine?  If you never execute the `ret' but
  70    instead `goto 1' do you remain in the subroutine?
  71
  72    For clarity on what is really required for type safety, read
  73    "Simple Verification Technique for Complex Java Bytecode
  74    Subroutines" by Alessandro Coglio.  Among other things this paper
  75    shows that recursive subroutines are not harmful to type safety.
  76    We implement something similar to what he proposes.  Note that this
  77    means that this verifier will accept code that is rejected by some
  78    other verifiers.
  79
  80    For those not wanting to read the paper, the basic observation is
  81    that we can maintain split states in subroutines.  We maintain one
  82    state for each calling `jsr'.  In other words, we re-verify a
  83    subroutine once for each caller, using the exact types held by the
  84    callers (as opposed to the old approach of merging types and
  85    keeping a bitmap registering what did or did not change).  This
  86    approach lets us continue to verify correctly even when a
  87    subroutine is exited via `goto' or `athrow' and not `ret'.
  88
  89    In some other areas the JVM specification is (mildly) incorrect,
  90    so we diverge.  For instance, you cannot
  91    violate type safety by allocating an object with `new' and then
  92    failing to initialize it, no matter how one branches or where one
  93    stores the uninitialized reference.  See "Improving the official
  94    specification of Java bytecode verification" by Alessandro Coglio.
  95
  96    Note that there's no real point in enforcing that padding bytes or
  97    the mystery byte of invokeinterface must be 0, but we do that
  98    regardless.
  99
 100    The verifier is currently neither completely lazy nor eager when it
 101    comes to loading classes.  It tries to represent types by name when
 102    possible, and then loads them when it needs to verify a fact about
 103    the type.  Checking types by name is valid because we only use
 104    names which come from the current class' constant pool.  Since all
 105    such names are looked up using the same class loader, there is no
 106    danger that we might be fooled into comparing different types with
 107    the same name.
 108
 109    In the future we plan to allow for a completely lazy mode of
 110    operation, where the verifier will construct a list of type
 111    assertions to be checked later.
 112
 113    Some test cases for the verifier live in the "verify" module of the
 114    Mauve test suite.  However, some of these are presently
 115    (2004-01-20) believed to be incorrect.  (More precisely the notion
 116    of "correct" is not well-defined, and this verifier differs from
 117    others while remaining type-safe.)  Some other tests live in the
 118    libgcj test suite.
 119
 120    This verifier is also written to be pluggable.  This means that it
 121    is intended for use in a variety of environments, not just libgcj.
 122    As a result the verifier expects a number of type and method
 123    declarations to be declared in "verify.h".  The intent is that you
 124    recompile the verifier for your particular environment.  This
 125    approach was chosen so that operations could be inlined in verify.h
 126    as much as possible.
 127
 128    See the verify.h that accompanies this copy of the verifier to see
 129    what types, preprocessor defines, and functions must be declared.
 130    The interface is ad hoc, but was defined so that it could be
 131    implemented to connect to a pure C program.
 132 */
 133
 134 #define FLAG_INSN_START 1
 135 #define FLAG_BRANCH_TARGET 2
 136 #define FLAG_INSN_SEEN 4
 137
 138 struct state;
 139 struct type;
 140 struct ref_intersection;
 141
 142 typedef struct state state;
 143 typedef struct type type;
 144 typedef struct ref_intersection ref_intersection;
 145
 146 /*typedef struct state_list state_list;*/
 147
 148 typedef struct state_list
 149 {
 150   state *val;
 151   struct state_list *next;
 152 } state_list;
 153
 154 typedef struct vfy_string_list
 155 {
 156   vfy_string val;
 157   struct vfy_string_list *next;
 158 } vfy_string_list;
 159
 160 typedef struct verifier_context
 161 {
 162   /* The current PC.  */
 163   int PC;
 164   /* The PC corresponding to the start of the current instruction.  */
 165   int start_PC;
 166
 167   /* The current state of the stack, locals, etc.  */
 168   state *current_state;
 169
 170   /* At each branch target we keep a linked list of all the states we
 171      can process at that point.  We'll only have multiple states at a
 172      given PC if they both have different return-address types in the
 173      same stack or local slot.  This array is indexed by PC and holds
 174      the list of all such states.  */
 175   state_list **states;
 176
 177   /* We keep a linked list of all the states which we must reverify.
 178      This is the head of the list.  */
 179   state *next_verify_state;
 180
 181   /* We keep some flags for each instruction.  The values are the
 182      FLAG_* constants defined above.  This is an array indexed by PC.  */
 183   char *flags;
 184
 185   /* The bytecode itself.  */
 186   const unsigned char *bytecode;
 187   /* The exceptions.  */
 188   vfy_exception *exception;
 189
 190   /* Defining class.  */
 191   vfy_jclass current_class;
 192   /* This method.  */
 193   vfy_method *current_method;
 194
 195   /* A linked list of utf8 objects we allocate.  */
 196   vfy_string_list *utf8_list;
 197
 198   /* A linked list of all ref_intersection objects we allocate.  */
 199   ref_intersection *isect_list;
 200 } verifier_context;
 201
 202 /* The current verifier's state data. This is maintained by
 203    {push/pop}_verifier_context to provide a shorthand form to access
 204    the verification state. */
 205 static GTY(()) verifier_context *vfr;
 206
 207 /* Local function declarations.  */
 208 bool type_initialized (type *t);
 209 int ref_count_dimensions (ref_intersection *ref);
 210
 211 static void
 212 verify_fail_pc (const char *s, int pc)
 213 {
 214   vfy_fail (s, pc, vfr->current_class, vfr->current_method);
 215 }
 216
 217 static void
 218 verify_fail (const char *s)
 219 {
 220   verify_fail_pc (s, vfr->PC);
 221 }
 222
 223 /* This enum holds a list of tags for all the different types we
 224    need to handle.  Reference types are treated specially by the
 225    type class.  */
 226 typedef enum type_val
 227 {
 228   void_type,
 229
 230   /* The values for primitive types are chosen to correspond to values
 231      specified to newarray. */
 232   boolean_type = 4,
 233   char_type = 5,
 234   float_type = 6,
 235   double_type = 7,
 236   byte_type = 8,
 237   short_type = 9,
 238   int_type = 10,
 239   long_type = 11,
 240
 241   /* Used when overwriting second word of a double or long in the
 242      local variables.  Also used after merging local variable states
 243      to indicate an unusable value.  */
 244   unsuitable_type,
 245   return_address_type,
 246   /* This is the second word of a two-word value, i.e., a double or
 247      a long.  */
 248   continuation_type,
 249
 250   /* Everything after `reference_type' must be a reference type.  */
 251   reference_type,
 252   null_type,
 253   uninitialized_reference_type
 254 } type_val;
 255
 256 /* This represents a merged class type.  Some verifiers (including
 257    earlier versions of this one) will compute the intersection of
 258    two class types when merging states.  However, this loses
 259    critical information about interfaces implemented by the various
 260    classes.  So instead we keep track of all the actual classes that
 261    have been merged.  */
 262 struct ref_intersection
 263 {
 264   /* Whether or not this type has been resolved.  */
 265   bool is_resolved;
 266
 267   /* Actual type data.  */
 268   union
 269   {
 270     /* For a resolved reference type, this is a pointer to the class.  */
 271     vfy_jclass klass;
 272     /* For other reference types, this it the name of the class.  */
 273     vfy_string name;
 274   } data;
 275
 276   /* Link to the next reference in the intersection.  */
 277   ref_intersection *ref_next;
 278
 279   /* This is used to keep track of all the allocated
 280      ref_intersection objects, so we can free them.
 281      FIXME: we should allocate these in chunks.  */
 282   ref_intersection *alloc_next;
 283 };
 284
 285 static ref_intersection *
 286 make_ref (void)
 287 {
 288   ref_intersection *new_ref =
 289     (ref_intersection *) vfy_alloc (sizeof (ref_intersection));
 290
 291   new_ref->alloc_next = vfr->isect_list;
 292   vfr->isect_list = new_ref;
 293   return new_ref;
 294 }
 295
 296 static ref_intersection *
 297 clone_ref (ref_intersection *dup)
 298 {
 299   ref_intersection *new_ref = make_ref ();
 300
 301   new_ref->is_resolved = dup->is_resolved;
 302   new_ref->data = dup->data;
 303   return new_ref;
 304 }
 305
 306 static void
 307 resolve_ref (ref_intersection *ref)
 308 {
 309   if (ref->is_resolved)
 310     return;
 311   ref->data.klass = vfy_find_class (vfr->current_class, ref->data.name);
 312   ref->is_resolved = true;
 313 }
 314
 315 static bool
 316 refs_equal (ref_intersection *ref1, ref_intersection *ref2)
 317 {
 318   if (! ref1->is_resolved && ! ref2->is_resolved
 319       && vfy_strings_equal (ref1->data.name, ref2->data.name))
 320     return true;
 321   if (! ref1->is_resolved)
 322     resolve_ref (ref1);
 323   if (! ref2->is_resolved)
 324     resolve_ref (ref2);
 325   return ref1->data.klass == ref2->data.klass;
 326 }
 327
 328 /* Merge REF1 type into REF2, returning the result.  This will
 329    return REF2 if all the classes in THIS already appear in
 330    REF2.  */
 331 static ref_intersection *
 332 merge_refs (ref_intersection *ref1, ref_intersection *ref2)
 333 {
 334   ref_intersection *tail = ref2;
 335   for (; ref1 != NULL; ref1 = ref1->ref_next)
 336     {
 337       bool add = true;
 338       ref_intersection *iter;
 339       for (iter = ref2; iter != NULL; iter = iter->ref_next)
 340         {
 341           if (refs_equal (ref1, iter))
 342             {
 343               add = false;
 344               break;
 345             }
 346         }
 347
 348       if (add)
 349         {
 350           ref_intersection *new_tail = clone_ref (ref1);
 351           new_tail->ref_next = tail;
 352           tail = new_tail;
 353         }
 354     }
 355   return tail;
 356 }
 357
 358 /* See if an object of type SOURCE can be assigned to an object of
 359    type TARGET.  This might resolve classes in one chain or the other.  */
 360 static bool
 361 ref_compatible (ref_intersection *target, ref_intersection *source)
 362 {
 363   for (; target != NULL; target = target->ref_next)
 364     {
 365       ref_intersection *source_iter = source;
 366
 367       for (; source_iter != NULL; source_iter = source_iter->ref_next)
 368         {
 369           /* Avoid resolving if possible.  */
 370           if (! target->is_resolved
 371               && ! source_iter->is_resolved
 372               && vfy_strings_equal (target->data.name,
 373                                     source_iter->data.name))
 374             continue;
 375
 376           if (! target->is_resolved)
 377             resolve_ref (target);
 378           if (! source_iter->is_resolved)
 379             resolve_ref (source_iter);
 380
 381           if (! vfy_is_assignable_from (target->data.klass,
 382                                         source_iter->data.klass))
 383             return false;
 384         }
 385     }
 386
 387   return true;
 388 }
 389
 390 static bool
 391 ref_isarray (ref_intersection *ref)
 392 {
 393   /* assert (ref_next == NULL);  */
 394   if (ref->is_resolved)
 395     return vfy_is_array (ref->data.klass);
 396   else
 397     return vfy_string_bytes (ref->data.name)[0] == '[';
 398 }
 399
 400 static bool
 401 ref_isinterface (ref_intersection *ref)
 402 {
 403   /* assert (ref_next == NULL);  */
 404   if (! ref->is_resolved)
 405     resolve_ref (ref);
 406   return vfy_is_interface (ref->data.klass);
 407 }
 408
 409 static bool
 410 ref_isabstract (ref_intersection *ref)
 411 {
 412   /* assert (ref_next == NULL); */
 413   if (! ref->is_resolved)
 414     resolve_ref (ref);
 415   return vfy_is_abstract (ref->data.klass);
 416 }
 417
 418 static vfy_jclass
 419 ref_getclass (ref_intersection *ref)
 420 {
 421   if (! ref->is_resolved)
 422     resolve_ref (ref);
 423   return ref->data.klass;
 424 }
 425
 426 int
 427 ref_count_dimensions (ref_intersection *ref)
 428 {
 429   int ndims = 0;
 430   if (ref->is_resolved)
 431     {
 432       vfy_jclass k = ref->data.klass;
 433       while (vfy_is_array (k))
 434         {
 435           k = vfy_get_component_type (k);
 436           ++ndims;
 437         }
 438     }
 439   else
 440     {
 441       const char *p = vfy_string_bytes (ref->data.name);
 442       while (*p++ == '[')
 443         ++ndims;
 444     }
 445   return ndims;
 446 }
 447
 448 /* Return the type_val corresponding to a primitive signature
 449    character.  For instance `I' returns `int.class'.  */
 450 static type_val
 451 get_type_val_for_signature (char sig)
 452 {
 453   type_val rt;
 454   switch (sig)
 455     {
 456     case 'Z':
 457       rt = boolean_type;
 458       break;
 459     case 'B':
 460       rt = byte_type;
 461       break;
 462     case 'C':
 463       rt = char_type;
 464       break;
 465     case 'S':
 466       rt = short_type;
 467       break;
 468     case 'I':
 469       rt = int_type;
 470       break;
 471     case 'J':
 472       rt = long_type;
 473       break;
 474     case 'F':
 475       rt = float_type;
 476       break;
 477     case 'D':
 478       rt = double_type;
 479       break;
 480     case 'V':
 481       rt = void_type;
 482       break;
 483     default:
 484       verify_fail ("invalid signature");
 485       return null_type;
 486     }
 487   return rt;
 488 }
 489
 490 /* Return the type_val corresponding to a primitive class.  */
 491 static type_val
 492 get_type_val_for_primtype (vfy_jclass k)
 493 {
 494   return get_type_val_for_signature (vfy_get_primitive_char (k));
 495 }
 496
 497 /* The `type' class is used to represent a single type in the verifier.  */
 498 struct type
 499 {
 500   /* The type key.  */
 501   type_val key;
 502
 503   /* For reference types, the representation of the type.  */
 504   ref_intersection *klass;
 505
 506   /* This is used in two situations.
 507
 508      First, when constructing a new object, it is the PC of the
 509      `new' instruction which created the object.  We use the special
 510      value UNINIT to mean that this is uninitialized.  The special
 511      value SELF is used for the case where the current method is
 512      itself the <init> method.  the special value EITHER is used
 513      when we may optionally allow either an uninitialized or
 514      initialized reference to match.
 515
 516      Second, when the key is return_address_type, this holds the PC
 517      of the instruction following the `jsr'.  */
 518   int pc;
 519
 520 #define UNINIT -2
 521 #define SELF -1
 522 #define EITHER -3
 523 };
 524
 525 /* Make a new instance given the type tag.  We assume a generic
 526    `reference_type' means Object.  */
 527 static void
 528 init_type_from_tag (type *t, type_val k)
 529 {
 530   t->key = k;
 531   /* For reference_type, if KLASS==NULL then that means we are
 532      looking for a generic object of any kind, including an
 533      uninitialized reference.  */
 534   t->klass = NULL;
 535   t->pc = UNINIT;
 536 }
 537
 538 /* Make a type for the given type_val tag K.  */
 539 static type
 540 make_type (type_val k)
 541 {
 542   type t;
 543   init_type_from_tag (&t, k);
 544   return t;
 545 }
 546
 547 /* Make a new instance given a class.  */
 548 static void
 549 init_type_from_class (type *t, vfy_jclass k)
 550 {
 551   t->key = reference_type;
 552   t->klass = make_ref ();
 553   t->klass->is_resolved = true;
 554   t->klass->data.klass = k;
 555   t->klass->ref_next = NULL;
 556   t->pc = UNINIT;
 557 }
 558
 559 static type
 560 make_type_from_class (vfy_jclass k)
 561 {
 562   type t;
 563   init_type_from_class (&t, k);
 564   return t;
 565 }
 566
 567 static void
 568 init_type_from_string (type *t, vfy_string n)
 569 {
 570   t->key = reference_type;
 571   t->klass = make_ref ();
 572   t->klass->is_resolved = false;
 573   t->klass->data.name = n;
 574   t->klass->ref_next = NULL;
 575   t->pc = UNINIT;
 576 }
 577
 578 static type
 579 make_type_from_string (vfy_string n)
 580 {
 581   type t;
 582   init_type_from_string (&t, n);
 583   return t;
 584 }
 585
 586 /* Promote a numeric type.  */
 587 static void
 588 vfy_promote_type (type *t)
 589 {
 590   if (t->key == boolean_type || t->key == char_type
 591       || t->key == byte_type || t->key == short_type)
 592     t->key = int_type;
 593 }
 594 #define promote_type vfy_promote_type
 595
 596 /* Mark this type as the uninitialized result of `new'.  */
 597 static void
 598 type_set_uninitialized (type *t, int npc)
 599 {
 600   if (t->key == reference_type)
 601     t->key = uninitialized_reference_type;
 602   else
 603     verify_fail ("internal error in type::uninitialized");
 604   t->pc = npc;
 605 }
 606
 607 /* Mark this type as now initialized.  */
 608 static void
 609 type_set_initialized (type *t, int npc)
 610 {
 611   if (npc != UNINIT && t->pc == npc && t->key == uninitialized_reference_type)
 612     {
 613       t->key = reference_type;
 614       t->pc = UNINIT;
 615     }
 616 }
 617
 618 /* Mark this type as a particular return address.  */
 619 static void type_set_return_address (type *t, int npc)
 620 {
 621   t->pc = npc;
 622 }
 623
 624 /* Return true if this type and type OTHER are considered
 625    mergeable for the purposes of state merging.  This is related
 626    to subroutine handling.  For this purpose two types are
 627    considered unmergeable if they are both return-addresses but
 628    have different PCs.  */
 629 static bool
 630 type_state_mergeable_p (type *t1, type *t2)
 631 {
 632   return (t1->key != return_address_type
 633           || t2->key != return_address_type
 634           || t1->pc == t2->pc);
 635 }
 636
 637 /* Return true if an object of type K can be assigned to a variable
 638    of type T.  Handle various special cases too.  Might modify
 639    T or K.  Note however that this does not perform numeric
 640    promotion.  */
 641 static bool
 642 types_compatible (type *t, type *k)
 643 {
 644   /* Any type is compatible with the unsuitable type.  */
 645   if (k->key == unsuitable_type)
 646     return true;
 647
 648   if (t->key < reference_type || k->key < reference_type)
 649     return t->key == k->key;
 650
 651   /* The `null' type is convertible to any initialized reference
 652      type.  */
 653   if (t->key == null_type)
 654     return k->key != uninitialized_reference_type;
 655   if (k->key == null_type)
 656     return t->key != uninitialized_reference_type;
 657
 658   /* A special case for a generic reference.  */
 659   if (t->klass == NULL)
 660     return true;
 661   if (k->klass == NULL)
 662     verify_fail ("programmer error in type::compatible");
 663
 664   /* Handle the special 'EITHER' case, which is only used in a
 665      special case of 'putfield'.  Note that we only need to handle
 666      this on the LHS of a check.  */
 667   if (! type_initialized (t) && t->pc == EITHER)
 668     {
 669       /* If the RHS is uninitialized, it must be an uninitialized
 670          'this'.  */
 671       if (! type_initialized (k) && k->pc != SELF)
 672         return false;
 673     }
 674   else if (type_initialized (t) != type_initialized (k))
 675     {
 676       /* An initialized type and an uninitialized type are not
 677          otherwise compatible.  */
 678       return false;
 679     }
 680   else
 681     {
 682       /* Two uninitialized objects are compatible if either:
 683        * The PCs are identical, or
 684        * One PC is UNINIT.  */
 685       if (type_initialized (t))
 686         {
 687           if (t->pc != k->pc && t->pc != UNINIT && k->pc != UNINIT)
 688             return false;
 689         }
 690     }
 691
 692   return ref_compatible (t->klass, k->klass);
 693 }
 694
 695 /* Return true if two types are equal.  Only valid for reference
 696    types.  */
 697 static bool
 698 types_equal (type *t1, type *t2)
 699 {
 700   if ((t1->key != reference_type && t1->key != uninitialized_reference_type)
 701       || (t2->key != reference_type
 702           && t2->key != uninitialized_reference_type))
 703     return false;
 704   /* Only single-ref types are allowed.  */
 705   if (t1->klass->ref_next || t2->klass->ref_next)
 706     return false;
 707   return refs_equal (t1->klass, t2->klass);
 708 }
 709
 710 static bool
 711 type_isvoid (type *t)
 712 {
 713   return t->key == void_type;
 714 }
 715
 716 static bool
 717 type_iswide (type *t)
 718 {
 719   return t->key == long_type || t->key == double_type;
 720 }
 721
 722 /* Return number of stack or local variable slots taken by this type.  */
 723 static int
 724 type_depth (type *t)
 725 {
 726   return type_iswide (t) ? 2 : 1;
 727 }
 728
 729 static bool
 730 type_isarray (type *t)
 731 {
 732   /* We treat null_type as not an array.  This is ok based on the
 733      current uses of this method.  */
 734   if (t->key == reference_type)
 735     return ref_isarray (t->klass);
 736   return false;
 737 }
 738
 739 static bool
 740 type_isnull (type *t)
 741 {
 742   return t->key == null_type;
 743 }
 744
 745 static bool
 746 type_isinterface (type *t)
 747 {
 748   if (t->key != reference_type)
 749     return false;
 750   return ref_isinterface (t->klass);
 751 }
 752
 753 static bool
 754 type_isabstract (type *t)
 755 {
 756   if (t->key != reference_type)
 757     return false;
 758   return ref_isabstract (t->klass);
 759 }
 760
 761 /* Return the element type of an array.  */
 762 static type
 763 type_array_element (type *t)
 764 {
 765   type et;
 766   vfy_jclass k;
 767
 768   if (t->key != reference_type)
 769     verify_fail ("programmer error in type::element_type()");
 770
 771   k = vfy_get_component_type (ref_getclass (t->klass));
 772   if (vfy_is_primitive (k))
 773     init_type_from_tag (&et, get_type_val_for_primtype (k));
 774   else
 775     init_type_from_class (&et, k);
 776   return et;
 777 }
 778
 779 /* Return the array type corresponding to an initialized
 780    reference.  We could expand this to work for other kinds of
 781    types, but currently we don't need to.  */
 782 static type
 783 type_to_array (type *t)
 784 {
 785   type at;
 786   vfy_jclass k;
 787
 788   if (t->key != reference_type)
 789     verify_fail ("internal error in type::to_array()");
 790
 791   k = ref_getclass (t->klass);
 792   init_type_from_class (&at, vfy_get_array_class (k));
 793   return at;
 794 }
 795
 796 static bool
 797 type_isreference (type *t)
 798 {
 799   return t->key >= reference_type;
 800 }
 801
 802 static int
 803 type_get_pc (type *t)
 804 {
 805   return t->pc;
 806 }
 807
 808 bool
 809 type_initialized (type *t)
 810 {
 811   return t->key == reference_type || t->key == null_type;
 812 }
 813
 814 static void
 815 type_verify_dimensions (type *t, int ndims)
 816 {
 817   /* The way this is written, we don't need to check isarray().  */
 818   if (t->key != reference_type)
 819     verify_fail ("internal error in verify_dimensions:"
 820                            " not a reference type");
 821
 822   if (ref_count_dimensions (t->klass) < ndims)
 823     verify_fail ("array type has fewer dimensions"
 824                            " than required");
 825 }
 826
 827 /* Merge OLD_TYPE into this.  On error throw exception.  Return
 828    true if the merge caused a type change.  */
 829 static bool
 830 merge_types (type *t, type *old_type, bool local_semantics)
 831 {
 832   bool changed = false;
 833   bool refo = type_isreference (old_type);
 834   bool refn = type_isreference (t);
 835   if (refo && refn)
 836     {
 837       if (old_type->key == null_type)
 838         ;
 839       else if (t->key == null_type)
 840         {
 841           *t = *old_type;
 842           changed = true;
 843         }
 844       else if (type_initialized (t) != type_initialized (old_type))
 845         verify_fail ("merging initialized and uninitialized types");
 846       else
 847         {
 848           ref_intersection *merged;
 849           if (! type_initialized (t))
 850             {
 851               if (t->pc == UNINIT)
 852                 t->pc = old_type->pc;
 853               else if (old_type->pc == UNINIT)
 854                 ;
 855               else if (t->pc != old_type->pc)
 856                 verify_fail ("merging different uninitialized types");
 857             }
 858
 859           merged = merge_refs (old_type->klass, t->klass);
 860           if (merged != t->klass)
 861             {
 862               t->klass = merged;
 863               changed = true;
 864             }
 865         }
 866     }
 867   else if (refo || refn || t->key != old_type->key)
 868     {
 869       if (local_semantics)
 870         {
 871           /* If we already have an `unsuitable' type, then we
 872              don't need to change again.  */
 873           if (t->key != unsuitable_type)
 874             {
 875               t->key = unsuitable_type;
 876               changed = true;
 877             }
 878         }
 879       else
 880         verify_fail ("unmergeable type");
 881     }
 882   return changed;
 883 }
 884
 885 #ifdef VERIFY_DEBUG
 886 static void
 887 type_print (type *t)
 888 {
 889   char c = '?';
 890   switch (t->key)
 891     {
 892     case boolean_type: c = 'Z'; break;
 893     case byte_type: c = 'B'; break;
 894     case char_type: c = 'C'; break;
 895     case short_type: c = 'S'; break;
 896     case int_type: c = 'I'; break;
 897     case long_type: c = 'J'; break;
 898     case float_type: c = 'F'; break;
 899     case double_type: c = 'D'; break;
 900     case void_type: c = 'V'; break;
 901     case unsuitable_type: c = '-'; break;
 902     case return_address_type: c = 'r'; break;
 903     case continuation_type: c = '+'; break;
 904     case reference_type: c = 'L'; break;
 905     case null_type: c = '@'; break;
 906     case uninitialized_reference_type: c = 'U'; break;
 907     }
 908   debug_print ("%c", c);
 909 }
 910 #endif /* VERIFY_DEBUG */
 911
 912 /* This class holds all the state information we need for a given
 913    location. */
 914 struct state
 915 {
 916   /* The current top of the stack, in terms of slots.  */
 917   int stacktop;
 918   /* The current depth of the stack.  This will be larger than
 919      STACKTOP when wide types are on the stack.  */
 920   int stackdepth;
 921   /* The stack.  */
 922   type *stack;
 923   /* The local variables.  */
 924   type *locals;
 925   /* We keep track of the type of `this' specially.  This is used to
 926      ensure that an instance initializer invokes another initializer
 927      on `this' before returning.  We must keep track of this
 928      specially because otherwise we might be confused by code which
 929      assigns to locals[0] (overwriting `this') and then returns
 930      without really initializing.  */
 931   type this_type;
 932
 933   /* The PC for this state.  This is only valid on states which are
 934      permanently attached to a given PC.  For an object like
 935      `current_state', which is used transiently, this has no
 936      meaning.  */
 937   int pc;
 938   /* We keep a linked list of all states requiring reverification.
 939      If this is the special value INVALID_STATE then this state is
 940      not on the list.  NULL marks the end of the linked list.  */
 941   state *next;
 942 };
 943
 944 /* NO_NEXT is the PC value meaning that a new state must be
 945    acquired from the verification list.  */
 946 #define NO_NEXT -1
 947
 948 static void
 949 init_state_with_stack (state *s, int max_stack, int max_locals)
 950 {
 951   int i;
 952   s->stacktop = 0;
 953   s->stackdepth = 0;
 954   s->stack = (type *) vfy_alloc (max_stack * sizeof (type));
 955   for (i = 0; i < max_stack; ++i)
 956     init_type_from_tag (&s->stack[i], unsuitable_type);
 957   s->locals = (type *) vfy_alloc (max_locals * sizeof (type));
 958   for (i = 0; i < max_locals; ++i)
 959     init_type_from_tag (&s->locals[i], unsuitable_type);
 960   init_type_from_tag (&s->this_type, unsuitable_type);
 961   s->pc = NO_NEXT;
 962   s->next = INVALID_STATE;
 963 }
 964
 965 static void
 966 copy_state (state *s, state *copy, int max_stack, int max_locals)
 967 {
 968   int i;
 969   s->stacktop = copy->stacktop;
 970   s->stackdepth = copy->stackdepth;
 971   for (i = 0; i < max_stack; ++i)
 972     s->stack[i] = copy->stack[i];
 973   for (i = 0; i < max_locals; ++i)
 974     s->locals[i] = copy->locals[i];
 975
 976   s->this_type = copy->this_type;
 977   /* Don't modify `next' or `pc'. */
 978 }
 979
 980 static void
 981 copy_state_with_stack (state *s, state *orig, int max_stack, int max_locals)
 982 {
 983   init_state_with_stack (s, max_stack, max_locals);
 984   copy_state (s, orig, max_stack, max_locals);
 985 }
 986
 987 /* Allocate a new state, copying ORIG. */
 988 static state *
 989 make_state_copy (state *orig, int max_stack, int max_locals)
 990 {
 991   state *s = vfy_alloc (sizeof (state));
 992   copy_state_with_stack (s, orig, max_stack, max_locals);
 993   return s;
 994 }
 995
 996 static state *
 997 make_state (int max_stack, int max_locals)
 998 {
 999   state *s = vfy_alloc (sizeof (state));
1000   init_state_with_stack (s, max_stack, max_locals);
1001   return s;
1002 }
1003
1004 static void
1005 free_state (state *s)
1006 {
1007   if (s->stack != NULL)
1008     vfy_free (s->stack);
1009   if (s->locals != NULL)
1010     vfy_free (s->locals);
1011 }
1012
1013 /* Modify this state to reflect entry to an exception handler.  */
1014 static void
1015 state_set_exception (state *s, type *t, int max_stack)
1016 {
1017   int i;
1018   s->stackdepth = 1;
1019   s->stacktop = 1;
1020   s->stack[0] = *t;
1021   for (i = s->stacktop; i < max_stack; ++i)
1022     init_type_from_tag (&s->stack[i], unsuitable_type);
1023 }
1024
1025 /* Merge STATE_OLD into this state.  Destructively modifies this
1026    state.  Returns true if the new state was in fact changed.
1027    Will throw an exception if the states are not mergeable.  */
1028 static bool
1029 merge_states (state *s, state *state_old, int max_locals)
1030 {
1031   int i;
1032   bool changed = false;
1033
1034   /* Special handling for `this'.  If one or the other is
1035      uninitialized, then the merge is uninitialized.  */
1036   if (type_initialized (&s->this_type))
1037     s->this_type = state_old->this_type;
1038
1039   /* Merge stacks.  */
1040   if (state_old->stacktop != s->stacktop)  /* FIXME stackdepth instead?  */
1041     verify_fail ("stack sizes differ");
1042   for (i = 0; i < state_old->stacktop; ++i)
1043     {
1044       if (merge_types (&s->stack[i], &state_old->stack[i], false))
1045         changed = true;
1046     }
1047
1048   /* Merge local variables.  */
1049   for (i = 0; i < max_locals; ++i)
1050     {
1051       if (merge_types (&s->locals[i], &state_old->locals[i], true))
1052         changed = true;
1053     }
1054
1055   return changed;
1056 }
1057
1058 /* Ensure that `this' has been initialized.  */
1059 static void
1060 state_check_this_initialized (state *s)
1061 {
1062   if (type_isreference (&s->this_type) && ! type_initialized (&s->this_type))
1063     verify_fail ("`this' is uninitialized");
1064 }
1065
1066 /* Set type of `this'.  */
1067 static void
1068 state_set_this_type (state *s, type *k)
1069 {
1070   s->this_type = *k;
1071 }
1072
1073 /* Mark each `new'd object we know of that was allocated at PC as
1074    initialized.  */
1075 static void
1076 state_set_initialized (state *s, int pc, int max_locals)
1077 {
1078   int i;
1079   for (i = 0; i < s->stacktop; ++i)
1080     type_set_initialized (&s->stack[i], pc);
1081   for (i = 0; i < max_locals; ++i)
1082     type_set_initialized (&s->locals[i], pc);
1083   type_set_initialized (&s->this_type, pc);
1084 }
1085
1086 /* This tests to see whether two states can be considered "merge
1087    compatible".  If both states have a return-address in the same
1088    slot, and the return addresses are different, then they are not
1089    compatible and we must not try to merge them.  */
1090 static bool
1091 state_mergeable_p (state *s, state *other, int max_locals)
1092
1093 {
1094   int i;
1095
1096   /* This is tricky: if the stack sizes differ, then not only are
1097      these not mergeable, but in fact we should give an error, as
1098      we've found two execution paths that reach a branch target
1099      with different stack depths.  FIXME stackdepth instead?  */
1100   if (s->stacktop != other->stacktop)
1101     verify_fail ("stack sizes differ");
1102
1103   for (i = 0; i < s->stacktop; ++i)
1104     if (! type_state_mergeable_p (&s->stack[i], &other->stack[i]))
1105       return false;
1106   for (i = 0; i < max_locals; ++i)
1107     if (! type_state_mergeable_p (&s->locals[i], &other->locals[i]))
1108       return false;
1109   return true;
1110 }
1111
1112 static void
1113 state_reverify (state *s)
1114 {
1115   if (s->next == INVALID_STATE)
1116     {
1117       s->next = vfr->next_verify_state;
1118       vfr->next_verify_state = s;
1119     }
1120 }
1121
1122 #ifdef VERIFY_DEBUG
1123 static void
1124 debug_print_state (state *s, const char *leader, int pc, int max_stack,
1125                    int max_locals)
1126 {
1127   int i;
1128   debug_print ("%s [%4d]:   [stack] ", leader, pc);
1129   for (i = 0; i < s->stacktop; ++i)
1130     type_print (&s->stack[i]);
1131   for (; i < max_stack; ++i)
1132     debug_print (".");
1133   debug_print ("    [local] ");
1134   for (i = 0; i < max_locals; ++i)
1135     type_print (&s->locals[i]);
1136   debug_print (" | %p\n", s);
1137 }
1138 #else
1139 static void
1140 debug_print_state (state *s ATTRIBUTE_UNUSED,
1141                    const char *leader ATTRIBUTE_UNUSED,
1142                    int pc ATTRIBUTE_UNUSED, int max_stack ATTRIBUTE_UNUSED,
1143                    int max_locals ATTRIBUTE_UNUSED)
1144 {
1145 }
1146 #endif /* VERIFY_DEBUG */
1147
1148 static type
1149 pop_raw (void)
1150 {
1151   type r;
1152   state *s = vfr->current_state;
1153   if (s->stacktop <= 0)
1154     verify_fail ("stack empty");
1155   r = s->stack[--s->stacktop];
1156   s->stackdepth -= type_depth (&r);
1157   if (s->stackdepth < 0)
1158     verify_fail_pc ("stack empty", vfr->start_PC);
1159   return r;
1160 }
1161
1162 static type
1163 pop32 (void)
1164 {
1165   type r = pop_raw ();
1166   if (type_iswide (&r))
1167     verify_fail ("narrow pop of wide type");
1168   return r;
1169 }
1170
1171 static type
1172 vfy_pop_type_t (type match)
1173 {
1174   type t;
1175   vfy_promote_type (&match);
1176   t = pop_raw ();
1177   if (! types_compatible (&match, &t))
1178     verify_fail ("incompatible type on stack");
1179   return t;
1180 }
1181
1182 static type
1183 vfy_pop_type (type_val match)
1184 {
1185   type t = make_type (match);
1186   return vfy_pop_type_t (t);
1187 }
1188
1189 #define pop_type vfy_pop_type
1190 #define pop_type_t vfy_pop_type_t
1191
1192 /* Pop a reference which is guaranteed to be initialized.  MATCH
1193    doesn't have to be a reference type; in this case this acts like
1194    pop_type.  */
1195 static type
1196 pop_init_ref_t (type match)
1197 {
1198   type t = pop_raw ();
1199   if (type_isreference (&t) && ! type_initialized (&t))
1200     verify_fail ("initialized reference required");
1201   else if (! types_compatible (&match, &t))
1202     verify_fail ("incompatible type on stack");
1203   return t;
1204 }
1205
1206 static type
1207 pop_init_ref (type_val match)
1208 {
1209   type t = make_type (match);
1210   return pop_init_ref_t (t);
1211 }
1212
1213 /* Pop a reference type or a return address.  */
1214 static type
1215 pop_ref_or_return (void)
1216 {
1217   type t = pop_raw ();
1218   if (! type_isreference (&t) && t.key != return_address_type)
1219     verify_fail ("expected reference or return address on stack");
1220   return t;
1221 }
1222
1223 static void
1224 vfy_push_type_t (type t)
1225 {
1226   int depth;
1227   state *s = vfr->current_state;
1228   /* If T is a numeric type like short, promote it to int.  */
1229   promote_type (&t);
1230
1231   depth = type_depth (&t);
1232
1233   if (s->stackdepth + depth > vfr->current_method->max_stack)
1234     verify_fail ("stack overflow");
1235   s->stack[s->stacktop++] = t;
1236   s->stackdepth += depth;
1237 }
1238
1239 static void
1240 vfy_push_type (type_val tval)
1241 {
1242   type t = make_type (tval);
1243   vfy_push_type_t (t);
1244 }
1245
1246 #define push_type vfy_push_type
1247 #define push_type_t vfy_push_type_t
1248
1249 static void
1250 set_variable (int index, type t)
1251 {
1252   int depth;
1253   state *s = vfr->current_state;
1254   /* If T is a numeric type like short, promote it to int.  */
1255   promote_type (&t);
1256
1257   depth = type_depth (&t);
1258   if (index > vfr->current_method->max_locals - depth)
1259     verify_fail ("invalid local variable");
1260   s->locals[index] = t;
1261
1262   if (depth == 2)
1263     init_type_from_tag (&s->locals[index + 1], continuation_type);
1264   if (index > 0 && type_iswide (&s->locals[index - 1]))
1265     init_type_from_tag (&s->locals[index - 1], unsuitable_type);
1266 }
1267
1268 static type
1269 get_variable_t (int index, type *t)
1270 {
1271   state *s = vfr->current_state;
1272   int depth = type_depth (t);
1273   if (index > vfr->current_method->max_locals - depth)
1274     verify_fail ("invalid local variable");
1275   if (! types_compatible (t, &s->locals[index]))
1276     verify_fail ("incompatible type in local variable");
1277   if (depth == 2)
1278     {
1279       type cont = make_type (continuation_type);
1280       if (! types_compatible (&s->locals[index + 1], &cont))
1281         verify_fail ("invalid local variable");
1282     }
1283   return s->locals[index];
1284 }
1285
1286 static type
1287 get_variable (int index, type_val v)
1288 {
1289   type t = make_type (v);
1290   return get_variable_t (index, &t);
1291 }
1292
1293 /* Make sure ARRAY is an array type and that its elements are
1294    compatible with type ELEMENT.  Returns the actual element type.  */
1295 static type
1296 require_array_type_t (type array, type element)
1297 {
1298   type t;
1299   /* An odd case.  Here we just pretend that everything went ok.  If
1300      the requested element type is some kind of reference, return
1301      the null type instead.  */
1302   if (type_isnull (&array))
1303     return type_isreference (&element) ? make_type (null_type) : element;
1304
1305   if (! type_isarray (&array))
1306     verify_fail ("array required");
1307
1308   t = type_array_element (&array);
1309   if (! types_compatible (&element, &t))
1310     {
1311       /* Special case for byte arrays, which must also be boolean
1312          arrays.  */
1313       bool ok = true;
1314       if (element.key == byte_type)
1315         {
1316           type e2 = make_type (boolean_type);
1317           ok = types_compatible (&e2, &t);
1318         }
1319       if (! ok)
1320         verify_fail ("incompatible array element type");
1321     }
1322
1323   /* Return T and not ELEMENT, because T might be specialized.  */
1324   return t;
1325 }
1326
1327 static type
1328 require_array_type (type array, type_val element)
1329 {
1330   type t = make_type (element);
1331   return require_array_type_t (array, t);
1332 }
1333
1334 static jint
1335 get_byte (void)
1336 {
1337   if (vfr->PC >= vfr->current_method->code_length)
1338     verify_fail ("premature end of bytecode");
1339   return (jint) vfr->bytecode[vfr->PC++] & 0xff;
1340 }
1341
1342 static jint
1343 get_ushort (void)
1344 {
1345   jint b1 = get_byte ();
1346   jint b2 = get_byte ();
1347   return (jint) ((b1 << 8) | b2) & 0xffff;
1348 }
1349
1350 static jint
1351 get_short (void)
1352 {
1353   signed char b1 = (signed char) get_byte ();
1354   jint b2 = get_byte ();
1355   jshort s = (b1 << 8) | b2;
1356   return (jint) s;
1357 }
1358
1359 static jint
1360 get_int (void)
1361 {
1362   jint b1 = get_byte ();
1363   jint b2 = get_byte ();
1364   jint b3 = get_byte ();
1365   jint b4 = get_byte ();
1366   jword result = (b1 << 24) | (b2 << 16) | (b3 << 8) | b4;
1367   /* In the compiler, 'jint' might have more than 32 bits, so we must
1368      sign extend.  */
1369   return WORD_TO_INT (result);
1370 }
1371
1372 static int
1373 compute_jump (int offset)
1374 {
1375   int npc = vfr->start_PC + offset;
1376   if (npc < 0 || npc >= vfr->current_method->code_length)
1377     verify_fail_pc ("branch out of range", vfr->start_PC);
1378   return npc;
1379 }
1380
1381 /* Add a new state to the state list at NPC.  */
1382 static state *
1383 add_new_state (int npc, state *old_state)
1384 {
1385   state_list *nlink;
1386   vfy_method *current_method = vfr->current_method;
1387   state *new_state = make_state_copy (old_state, current_method->max_stack,
1388                                       current_method->max_locals);
1389   debug_print ("== New state in add_new_state\n");
1390   debug_print_state (new_state, "New", npc, current_method->max_stack,
1391                     current_method->max_locals);
1392
1393   nlink = vfy_alloc (sizeof (state_list));
1394   nlink->val = new_state;
1395   nlink->next = vfr->states[npc];
1396   vfr->states[npc] = nlink;
1397   new_state->pc = npc;
1398   return new_state;
1399 }
1400
1401 /* Merge the indicated state into the state at the branch target and
1402    schedule a new PC if there is a change.  NPC is the PC of the
1403    branch target, and FROM_STATE is the state at the source of the
1404    branch.  This method returns true if the destination state
1405    changed and requires reverification, false otherwise.  */
1406 static void
1407 merge_into (int npc, state *from_state)
1408 {
1409   /* Iterate over all target states and merge our state into each,
1410      if applicable.  FIXME one improvement we could make here is
1411      "state destruction".  Merging a new state into an existing one
1412      might cause a return_address_type to be merged to
1413      unsuitable_type.  In this case the resulting state may now be
1414      mergeable with other states currently held in parallel at this
1415      location.  So in this situation we could pairwise compare and
1416      reduce the number of parallel states.  */
1417   state_list *iter;
1418   bool applicable = false;
1419   for (iter = vfr->states[npc]; iter != NULL; iter = iter->next)
1420     {
1421       state *new_state = iter->val;
1422       vfy_method *current_method = vfr->current_method;
1423
1424       if (state_mergeable_p (new_state, from_state,
1425                                         current_method->max_locals))
1426         {
1427           bool changed;
1428           applicable = true;
1429
1430           debug_print ("== Merge states in merge_into\n");
1431           debug_print_state (from_state, "Frm", vfr->start_PC, current_method->max_stack,
1432                              current_method->max_locals);
1433           debug_print_state (new_state, " To", npc, current_method->max_stack,
1434                             current_method->max_locals);
1435           changed = merge_states (new_state, from_state,
1436                                   current_method->max_locals);
1437           debug_print_state (new_state, "New", npc, current_method->max_stack,
1438                             current_method->max_locals);
1439
1440           if (changed)
1441             state_reverify (new_state);
1442         }
1443     }
1444
1445   if (! applicable)
1446     {
1447       /* Either we don't yet have a state at NPC, or we have a
1448          return-address type that is in conflict with all existing
1449          state.  So, we need to create a new entry.  */
1450       state *new_state = add_new_state (npc, from_state);
1451       /* A new state added in this way must always be reverified.  */
1452       state_reverify (new_state);
1453     }
1454 }
1455
1456 static void
1457 push_jump (int offset)
1458 {
1459   int npc = compute_jump (offset);
1460   /* According to the JVM Spec, we need to check for uninitialized
1461      objects here.  However, this does not actually affect type
1462      safety, and the Eclipse java compiler generates code that
1463      violates this constraint.  */
1464   merge_into (npc, vfr->current_state);
1465 }
1466
1467 static void
1468 push_exception_jump (type t, int pc)
1469 {
1470   state s;
1471   /* According to the JVM Spec, we need to check for uninitialized
1472      objects here.  However, this does not actually affect type
1473      safety, and the Eclipse java compiler generates code that
1474      violates this constraint.  */
1475   copy_state_with_stack (&s, vfr->current_state,
1476                          vfr->current_method->max_stack,
1477                          vfr->current_method->max_locals);
1478   if (vfr->current_method->max_stack < 1)
1479     verify_fail ("stack overflow at exception handler");
1480   state_set_exception (&s, &t, vfr->current_method->max_stack);
1481   merge_into (pc, &s);
1482   /* FIXME: leak.. need free_state or GC */
1483 }
1484
1485 static state *
1486 pop_jump (void)
1487 {
1488   state *new_state = vfr->next_verify_state;
1489   if (new_state == INVALID_STATE)
1490     verify_fail ("programmer error in pop_jump");
1491   if (new_state != NULL)
1492     {
1493       vfr->next_verify_state = new_state->next;
1494       new_state->next = INVALID_STATE;
1495     }
1496   return new_state;
1497 }
1498
1499 static void
1500 invalidate_pc (void)
1501 {
1502   vfr->PC = NO_NEXT;
1503 }
1504
1505 static void
1506 note_branch_target (int pc)
1507 {
1508   /* Don't check `pc <= PC', because we've advanced PC after
1509      fetching the target and we haven't yet checked the next
1510      instruction.  */
1511   if (pc < vfr->PC && ! (vfr->flags[pc] & FLAG_INSN_START))
1512     verify_fail_pc ("branch not to instruction start", vfr->start_PC);
1513   vfr->flags[pc] |= FLAG_BRANCH_TARGET;
1514 }
1515
1516 static void
1517 skip_padding (void)
1518 {
1519   while ((vfr->PC % 4) > 0)
1520     if (get_byte () != 0)
1521       verify_fail ("found nonzero padding byte");
1522 }
1523
1524 /* Do the work for a `ret' instruction.  INDEX is the index into the
1525    local variables.  */
1526 static void
1527 handle_ret_insn (int index)
1528 {
1529   type ret = make_type (return_address_type);
1530   type ret_addr = get_variable_t (index, &ret);
1531   /* It would be nice if we could do this.  However, the JVM Spec
1532      doesn't say that this is what happens.  It is implied that
1533      reusing a return address is invalid, but there's no actual
1534      prohibition against it.  */
1535   /* set_variable (index, unsuitable_type); */
1536
1537   int npc = type_get_pc (&ret_addr);
1538   /* We might be returning to a `jsr' that is at the end of the
1539      bytecode.  This is ok if we never return from the called
1540      subroutine, but if we see this here it is an error.  */
1541   if (npc >= vfr->current_method->code_length)
1542     verify_fail ("fell off end");
1543
1544   /* According to the JVM Spec, we need to check for uninitialized
1545      objects here.  However, this does not actually affect type
1546      safety, and the Eclipse java compiler generates code that
1547      violates this constraint.  */
1548   merge_into (npc, vfr->current_state);
1549   invalidate_pc ();
1550 }
1551
1552 static void handle_jsr_insn (int offset)
1553 {
1554   type ret_addr;
1555   int npc = compute_jump (offset);
1556
1557   /* According to the JVM Spec, we need to check for uninitialized
1558      objects here.  However, this does not actually affect type
1559      safety, and the Eclipse java compiler generates code that
1560      violates this constraint.  */
1561
1562   /* Modify our state as appropriate for entry into a subroutine.  */
1563   ret_addr = make_type (return_address_type);
1564   type_set_return_address (&ret_addr, vfr->PC);
1565   vfy_push_type_t (ret_addr);
1566   merge_into (npc, vfr->current_state);
1567   invalidate_pc ();
1568 }
1569
1570 static vfy_jclass
1571 construct_primitive_array_type (type_val prim)
1572 {
1573   vfy_jclass k = NULL;
1574   switch (prim)
1575     {
1576     case boolean_type:
1577     case char_type:
1578     case float_type:
1579     case double_type:
1580     case byte_type:
1581     case short_type:
1582     case int_type:
1583     case long_type:
1584       k = vfy_get_primitive_type ((int) prim);
1585       break;
1586
1587     /* These aren't used here but we call them out to avoid
1588        warnings.  */
1589     case void_type:
1590     case unsuitable_type:
1591     case return_address_type:
1592     case continuation_type:
1593     case reference_type:
1594     case null_type:
1595     case uninitialized_reference_type:
1596     default:
1597       verify_fail ("unknown type in construct_primitive_array_type");
1598     }
1599   k = vfy_get_array_class (k);
1600   return k;
1601 }
1602
1603 /* This pass computes the location of branch targets and also
1604    instruction starts.  */
1605 static void
1606 branch_prepass (void)
1607 {
1608   int i, pc;
1609   vfr->flags = (char *) vfy_alloc (vfr->current_method->code_length);
1610
1611   for (i = 0; i < vfr->current_method->code_length; ++i)
1612     vfr->flags[i] = 0;
1613
1614   vfr->PC = 0;
1615   while (vfr->PC < vfr->current_method->code_length)
1616     {
1617       java_opcode opcode;
1618       /* Set `start_PC' early so that error checking can have the
1619          correct value.  */
1620       vfr->start_PC = vfr->PC;
1621       vfr->flags[vfr->PC] |= FLAG_INSN_START;
1622
1623       opcode = (java_opcode) vfr->bytecode[vfr->PC++];
1624       switch (opcode)
1625         {
1626         case op_nop:
1627         case op_aconst_null:
1628         case op_iconst_m1:
1629         case op_iconst_0:
1630         case op_iconst_1:
1631         case op_iconst_2:
1632         case op_iconst_3:
1633         case op_iconst_4:
1634         case op_iconst_5:
1635         case op_lconst_0:
1636         case op_lconst_1:
1637         case op_fconst_0:
1638         case op_fconst_1:
1639         case op_fconst_2:
1640         case op_dconst_0:
1641         case op_dconst_1:
1642         case op_iload_0:
1643         case op_iload_1:
1644         case op_iload_2:
1645         case op_iload_3:
1646         case op_lload_0:
1647         case op_lload_1:
1648         case op_lload_2:
1649         case op_lload_3:
1650         case op_fload_0:
1651         case op_fload_1:
1652         case op_fload_2:
1653         case op_fload_3:
1654         case op_dload_0:
1655         case op_dload_1:
1656         case op_dload_2:
1657         case op_dload_3:
1658         case op_aload_0:
1659         case op_aload_1:
1660         case op_aload_2:
1661         case op_aload_3:
1662         case op_iaload:
1663         case op_laload:
1664         case op_faload:
1665         case op_daload:
1666         case op_aaload:
1667         case op_baload:
1668         case op_caload:
1669         case op_saload:
1670         case op_istore_0:
1671         case op_istore_1:
1672         case op_istore_2:
1673         case op_istore_3:
1674         case op_lstore_0:
1675         case op_lstore_1:
1676         case op_lstore_2:
1677         case op_lstore_3:
1678         case op_fstore_0:
1679         case op_fstore_1:
1680         case op_fstore_2:
1681         case op_fstore_3:
1682         case op_dstore_0:
1683         case op_dstore_1:
1684         case op_dstore_2:
1685         case op_dstore_3:
1686         case op_astore_0:
1687         case op_astore_1:
1688         case op_astore_2:
1689         case op_astore_3:
1690         case op_iastore:
1691         case op_lastore:
1692         case op_fastore:
1693         case op_dastore:
1694         case op_aastore:
1695         case op_bastore:
1696         case op_castore:
1697         case op_sastore:
1698         case op_pop:
1699         case op_pop2:
1700         case op_dup:
1701         case op_dup_x1:
1702         case op_dup_x2:
1703         case op_dup2:
1704         case op_dup2_x1:
1705         case op_dup2_x2:
1706         case op_swap:
1707         case op_iadd:
1708         case op_isub:
1709         case op_imul:
1710         case op_idiv:
1711         case op_irem:
1712         case op_ishl:
1713         case op_ishr:
1714         case op_iushr:
1715         case op_iand:
1716         case op_ior:
1717         case op_ixor:
1718         case op_ladd:
1719         case op_lsub:
1720         case op_lmul:
1721         case op_ldiv:
1722         case op_lrem:
1723         case op_lshl:
1724         case op_lshr:
1725         case op_lushr:
1726         case op_land:
1727         case op_lor:
1728         case op_lxor:
1729         case op_fadd:
1730         case op_fsub:
1731         case op_fmul:
1732         case op_fdiv:
1733         case op_frem:
1734         case op_dadd:
1735         case op_dsub:
1736         case op_dmul:
1737         case op_ddiv:
1738         case op_drem:
1739         case op_ineg:
1740         case op_i2b:
1741         case op_i2c:
1742         case op_i2s:
1743         case op_lneg:
1744         case op_fneg:
1745         case op_dneg:
1746         case op_i2l:
1747         case op_i2f:
1748         case op_i2d:
1749         case op_l2i:
1750         case op_l2f:
1751         case op_l2d:
1752         case op_f2i:
1753         case op_f2l:
1754         case op_f2d:
1755         case op_d2i:
1756         case op_d2l:
1757         case op_d2f:
1758         case op_lcmp:
1759         case op_fcmpl:
1760         case op_fcmpg:
1761         case op_dcmpl:
1762         case op_dcmpg:
1763         case op_monitorenter:
1764         case op_monitorexit:
1765         case op_ireturn:
1766         case op_lreturn:
1767         case op_freturn:
1768         case op_dreturn:
1769         case op_areturn:
1770         case op_return:
1771         case op_athrow:
1772         case op_arraylength:
1773           break;
1774
1775         case op_bipush:
1776         case op_ldc:
1777         case op_iload:
1778         case op_lload:
1779         case op_fload:
1780         case op_dload:
1781         case op_aload:
1782         case op_istore:
1783         case op_lstore:
1784         case op_fstore:
1785         case op_dstore:
1786         case op_astore:
1787         case op_ret:
1788         case op_newarray:
1789           get_byte ();
1790           break;
1791
1792         case op_iinc:
1793         case op_sipush:
1794         case op_ldc_w:
1795         case op_ldc2_w:
1796         case op_getstatic:
1797         case op_getfield:
1798         case op_putfield:
1799         case op_putstatic:
1800         case op_new:
1801         case op_anewarray:
1802         case op_instanceof:
1803         case op_checkcast:
1804         case op_invokespecial:
1805         case op_invokestatic:
1806         case op_invokevirtual:
1807           get_short ();
1808           break;
1809
1810         case op_multianewarray:
1811           get_short ();
1812           get_byte ();
1813           break;
1814
1815         case op_jsr:
1816         case op_ifeq:
1817         case op_ifne:
1818         case op_iflt:
1819         case op_ifge:
1820         case op_ifgt:
1821         case op_ifle:
1822         case op_if_icmpeq:
1823         case op_if_icmpne:
1824         case op_if_icmplt:
1825         case op_if_icmpge:
1826         case op_if_icmpgt:
1827         case op_if_icmple:
1828         case op_if_acmpeq:
1829         case op_if_acmpne:
1830         case op_ifnull:
1831         case op_ifnonnull:
1832         case op_goto:
1833           note_branch_target (compute_jump (get_short ()));
1834           break;
1835
1836         case op_tableswitch:
1837           {
1838             jint low, hi;
1839             skip_padding ();
1840             note_branch_target (compute_jump (get_int ()));
1841             low = get_int ();
1842             hi = get_int ();
1843             if (low > hi)
1844               verify_fail_pc ("invalid tableswitch", vfr->start_PC);
1845             for (i = low; i <= hi; ++i)
1846               note_branch_target (compute_jump (get_int ()));
1847           }
1848           break;
1849
1850         case op_lookupswitch:
1851           {
1852             int npairs;
1853             skip_padding ();
1854             note_branch_target (compute_jump (get_int ()));
1855             npairs = get_int ();
1856             if (npairs < 0)
1857               verify_fail_pc ("too few pairs in lookupswitch", vfr->start_PC);
1858             while (npairs-- > 0)
1859               {
1860                 get_int ();
1861                 note_branch_target (compute_jump (get_int ()));
1862               }
1863           }
1864           break;
1865
1866         case op_invokeinterface:
1867           get_short ();
1868           get_byte ();
1869           get_byte ();
1870           break;
1871
1872         case op_wide:
1873           {
1874             opcode = (java_opcode) get_byte ();
1875             get_short ();
1876             if (opcode == op_iinc)
1877               get_short ();
1878           }
1879           break;
1880
1881         case op_jsr_w:
1882         case op_goto_w:
1883           note_branch_target (compute_jump (get_int ()));
1884           break;
1885
1886 #if 0
1887         /* These are unused here, but we call them out explicitly
1888            so that -Wswitch-enum doesn't complain.  */
1889         case op_putfield_1:
1890         case op_putfield_2:
1891         case op_putfield_4:
1892         case op_putfield_8:
1893         case op_putfield_a:
1894         case op_putstatic_1:
1895         case op_putstatic_2:
1896         case op_putstatic_4:
1897         case op_putstatic_8:
1898         case op_putstatic_a:
1899         case op_getfield_1:
1900         case op_getfield_2s:
1901         case op_getfield_2u:
1902         case op_getfield_4:
1903         case op_getfield_8:
1904         case op_getfield_a:
1905         case op_getstatic_1:
1906         case op_getstatic_2s:
1907         case op_getstatic_2u:
1908         case op_getstatic_4:
1909         case op_getstatic_8:
1910         case op_getstatic_a:
1911 #endif /* VFY_FAST_OPCODES  */
1912         default:
1913           verify_fail_pc ("unrecognized instruction in branch_prepass",
1914                           vfr->start_PC);
1915         }
1916
1917       /* See if any previous branch tried to branch to the middle of
1918          this instruction.  */
1919       for (pc = vfr->start_PC + 1; pc < vfr->PC; ++pc)
1920         {
1921           if ((vfr->flags[pc] & FLAG_BRANCH_TARGET))
1922             verify_fail_pc ("branch to middle of instruction", pc);
1923         }
1924     }
1925
1926   /* Verify exception handlers.  */
1927   for (i = 0; i < vfr->current_method->exc_count; ++i)
1928     {
1929       int handler, start, end, htype;
1930       vfy_get_exception (vfr->exception, i, &handler, &start, &end, &htype);
1931       if (! (vfr->flags[handler] & FLAG_INSN_START))
1932         verify_fail_pc ("exception handler not at instruction start",
1933                         handler);
1934       if (! (vfr->flags[start] & FLAG_INSN_START))
1935         verify_fail_pc ("exception start not at instruction start", start);
1936       if (end != vfr->current_method->code_length
1937           && ! (vfr->flags[end] & FLAG_INSN_START))
1938         verify_fail_pc ("exception end not at instruction start", end);
1939
1940       vfr->flags[handler] |= FLAG_BRANCH_TARGET;
1941     }
1942 }
1943
1944 static void
1945 check_pool_index (int index)
1946 {
1947   if (index < 0 || index >= vfy_get_constants_size (vfr->current_class))
1948     verify_fail_pc ("constant pool index out of range", vfr->start_PC);
1949 }
1950
1951 static type
1952 check_class_constant (int index)
1953 {
1954   type t;
1955   vfy_constants *pool;
1956
1957   check_pool_index (index);
1958   pool = vfy_get_constants (vfr->current_class);
1959   if (vfy_tag (pool, index) == JV_CONSTANT_ResolvedClass)
1960     init_type_from_class (&t, vfy_get_pool_class (pool, index));
1961   else if (vfy_tag (pool, index) == JV_CONSTANT_Class)
1962     init_type_from_string (&t, vfy_get_pool_string (pool, index));
1963   else
1964     verify_fail_pc ("expected class constant", vfr->start_PC);
1965   return t;
1966 }
1967
1968 static type
1969 check_constant (int index)
1970 {
1971   type t;
1972   vfy_constants *pool;
1973
1974   check_pool_index (index);
1975   pool = vfy_get_constants (vfr->current_class);
1976   if (vfy_tag (pool, index) == JV_CONSTANT_ResolvedString
1977       || vfy_tag (pool, index) == JV_CONSTANT_String)
1978     init_type_from_class (&t, vfy_string_type ());
1979   else if (vfy_tag (pool, index) == JV_CONSTANT_Integer)
1980     init_type_from_tag (&t, int_type);
1981   else if (vfy_tag (pool, index) == JV_CONSTANT_Float)
1982     init_type_from_tag (&t, float_type);
1983   else
1984     verify_fail_pc ("String, int, or float constant expected", vfr->start_PC);
1985   return t;
1986 }
1987
1988 static type
1989 check_wide_constant (int index)
1990 {
1991   type t;
1992   vfy_constants *pool;
1993
1994   check_pool_index (index);
1995   pool = vfy_get_constants (vfr->current_class);
1996   if (vfy_tag (pool, index) == JV_CONSTANT_Long)
1997     init_type_from_tag (&t, long_type);
1998   else if (vfy_tag (pool, index) == JV_CONSTANT_Double)
1999     init_type_from_tag (&t, double_type);
2000   else
2001     verify_fail_pc ("long or double constant expected", vfr->start_PC);
2002   return t;
2003 }
2004
2005 /* Helper for both field and method.  These are laid out the same in
2006    the constant pool.  */
2007 static type
2008 handle_field_or_method (int index, int expected,
2009                         vfy_string *name, vfy_string *fmtype)
2010 {
2011   vfy_uint_16 class_index, name_and_type_index;
2012   vfy_uint_16 name_index, desc_index;
2013   vfy_constants *pool;
2014
2015   check_pool_index (index);
2016   pool = vfy_get_constants (vfr->current_class);
2017   if (vfy_tag (pool, index) != expected)
2018     verify_fail_pc ("didn't see expected constant", vfr->start_PC);
2019   /* Once we know we have a Fieldref or Methodref we assume that it
2020      is correctly laid out in the constant pool.  I think the code
2021      in defineclass.cc guarantees this.  */
2022   vfy_load_indexes (pool, index, &class_index, &name_and_type_index);
2023   vfy_load_indexes (pool, name_and_type_index, &name_index, &desc_index);
2024
2025   *name = vfy_get_pool_string (pool, name_index);
2026   *fmtype = vfy_get_pool_string (pool, desc_index);
2027
2028   return check_class_constant (class_index);
2029 }
2030
2031 /* Return field's type, compute class' type if requested.  If
2032    PUTFIELD is true, use the special 'putfield' semantics.  */
2033 static type
2034 check_field_constant (int index, type *class_type, bool putfield)
2035 {
2036   vfy_string name, field_type;
2037   const char *typec;
2038   int len;
2039   type t;
2040
2041   type ct = handle_field_or_method (index,
2042                                     JV_CONSTANT_Fieldref,
2043                                     &name, &field_type);
2044   if (class_type)
2045     *class_type = ct;
2046   typec = vfy_string_bytes (field_type);
2047   len = vfy_string_length (field_type);
2048   if (typec[0] == '[' || typec[0] == 'L')
2049     init_type_from_string (&t, field_type);
2050   else
2051     init_type_from_tag (&t, get_type_val_for_signature (typec[0]));
2052
2053   /* We have an obscure special case here: we can use `putfield' on a
2054      field declared in this class, even if `this' has not yet been
2055      initialized.  */
2056   if (putfield
2057       && ! type_initialized (&vfr->current_state->this_type)
2058       && vfr->current_state->this_type.pc == SELF
2059       && types_equal (&vfr->current_state->this_type, &ct)
2060       && vfy_class_has_field (vfr->current_class, name, field_type))
2061     /* Note that we don't actually know whether we're going to match
2062        against 'this' or some other object of the same type.  So,
2063        here we set things up so that it doesn't matter.  This relies
2064        on knowing what our caller is up to.  */
2065     type_set_uninitialized (class_type, EITHER);
2066
2067   return t;
2068 }
2069
2070 static type
2071 check_method_constant (int index, bool is_interface,
2072                             vfy_string *method_name,
2073                             vfy_string *method_signature)
2074 {
2075   return handle_field_or_method (index,
2076                                  (is_interface
2077                                   ? JV_CONSTANT_InterfaceMethodref
2078                                   : JV_CONSTANT_Methodref),
2079                                  method_name, method_signature);
2080 }
2081
2082 static char *
2083 get_one_type (char *p, type *t)
2084 {
2085   const char *start = p;
2086   vfy_jclass k;
2087   type_val rt;
2088   char v;
2089
2090   int arraycount = 0;
2091   while (*p == '[')
2092     {
2093       ++arraycount;
2094       ++p;
2095     }
2096
2097   v = *p++;
2098
2099   if (v == 'L')
2100     {
2101       vfy_string name;
2102       while (*p != ';')
2103         ++p;
2104       ++p;
2105       name = vfy_get_string (start, p - start);
2106       *t = make_type_from_string (name);
2107       return p;
2108     }
2109
2110   /* Casting to jchar here is ok since we are looking at an ASCII
2111      character.  */
2112   rt = get_type_val_for_signature (v);
2113
2114   if (arraycount == 0)
2115     {
2116       /* Callers of this function eventually push their arguments on
2117          the stack.  So, promote them here.  */
2118       type new_t = make_type (rt);
2119       vfy_promote_type (&new_t);
2120       *t = new_t;
2121       return p;
2122     }
2123
2124   k = construct_primitive_array_type (rt);
2125   while (--arraycount > 0)
2126     k = vfy_get_array_class (k);
2127   *t = make_type_from_class (k);
2128   return p;
2129 }
2130
2131 static void
2132 compute_argument_types (vfy_string signature, type *types)
2133 {
2134   int i;
2135   char *p = (char *) vfy_string_bytes (signature);
2136
2137   /* Skip `('.  */
2138   ++p;
2139
2140   i = 0;
2141   while (*p != ')')
2142     p = get_one_type (p, &types[i++]);
2143 }
2144
2145 static type
2146 compute_return_type (vfy_string signature)
2147 {
2148   char *p = (char *) vfy_string_bytes (signature);
2149   type t;
2150   while (*p != ')')
2151     ++p;
2152   ++p;
2153   get_one_type (p, &t);
2154   return t;
2155 }
2156
2157 static void
2158 check_return_type (type onstack)
2159 {
2160   type rt = compute_return_type (vfy_get_signature (vfr->current_method));
2161   if (! types_compatible (&rt, &onstack))
2162     verify_fail ("incompatible return type");
2163 }
2164
2165 /* Initialize the stack for the new method.  Returns true if this
2166    method is an instance initializer.  */
2167 static bool
2168 initialize_stack (void)
2169 {
2170   int arg_count, i;
2171   int var = 0;
2172   bool is_init = vfy_strings_equal (vfy_get_method_name (vfr->current_method),
2173                                     vfy_init_name());
2174   bool is_clinit = vfy_strings_equal (vfy_get_method_name (vfr->current_method),
2175                                       vfy_clinit_name());
2176
2177   if (! vfy_is_static (vfr->current_method))
2178     {
2179       type kurr = make_type_from_class (vfr->current_class);
2180       if (is_init)
2181         {
2182           type_set_uninitialized (&kurr, SELF);
2183           is_init = true;
2184         }
2185       else if (is_clinit)
2186         verify_fail ("<clinit> method must be static");
2187       set_variable (0, kurr);
2188       state_set_this_type (vfr->current_state, &kurr);
2189       ++var;
2190     }
2191   else
2192     {
2193       if (is_init)
2194         verify_fail ("<init> method must be non-static");
2195     }
2196
2197   /* We have to handle wide arguments specially here.  */
2198   arg_count = vfy_count_arguments (vfy_get_signature (vfr->current_method));
2199   {
2200     type *arg_types = (type *) vfy_alloc (arg_count * sizeof (type));
2201     compute_argument_types (vfy_get_signature (vfr->current_method), arg_types);
2202     for (i = 0; i < arg_count; ++i)
2203       {
2204         set_variable (var, arg_types[i]);
2205         ++var;
2206         if (type_iswide (&arg_types[i]))
2207           ++var;
2208       }
2209     vfy_free (arg_types);
2210   }
2211
2212   return is_init;
2213 }
2214
2215 static void
2216 verify_instructions_0 (void)
2217 {
2218   int i;
2219   bool this_is_init;
2220
2221   vfr->current_state = make_state (vfr->current_method->max_stack,
2222                                    vfr->current_method->max_locals);
2223
2224   vfr->PC = 0;
2225   vfr->start_PC = 0;
2226
2227   /*  True if we are verifying an instance initializer.  */
2228   this_is_init = initialize_stack ();
2229
2230   vfr->states = (state_list **) vfy_alloc (sizeof (state_list *)
2231                                       * vfr->current_method->code_length);
2232
2233   for (i = 0; i < vfr->current_method->code_length; ++i)
2234     vfr->states[i] = NULL;
2235
2236   vfr->next_verify_state = NULL;
2237
2238   while (true)
2239     {
2240       java_opcode opcode;
2241
2242       /* If the PC was invalidated, get a new one from the work list.  */
2243       if (vfr->PC == NO_NEXT)
2244         {
2245           state *new_state = pop_jump ();
2246           /* If it is null, we're done.  */
2247           if (new_state == NULL)
2248             break;
2249
2250           vfr->PC = new_state->pc;
2251           debug_print ("== State pop from pending list\n");
2252           /* Set up the current state.  */
2253           copy_state (vfr->current_state, new_state,
2254             vfr->current_method->max_stack, vfr->current_method->max_locals);
2255         }
2256       else
2257         {
2258           /* We only have to do this checking in the situation where
2259              control flow falls through from the previous
2260              instruction.  Otherwise merging is done at the time we
2261              push the branch.  */
2262           if (vfr->states[vfr->PC] != NULL)
2263             {
2264               /* We've already visited this instruction.  So merge
2265                  the states together.  It is simplest, but not most
2266                  efficient, to just always invalidate the PC here.  */
2267               merge_into (vfr->PC, vfr->current_state);
2268               invalidate_pc ();
2269               continue;
2270             }
2271         }
2272
2273       /* Control can't fall off the end of the bytecode.  We need to
2274          check this in both cases, not just the fall-through case,
2275          because we don't check to see whether a `jsr' appears at
2276          the end of the bytecode until we process a `ret'.  */
2277       if (vfr->PC >= vfr->current_method->code_length)
2278         verify_fail ("fell off end");
2279       vfr->flags[vfr->PC] |= FLAG_INSN_SEEN;
2280
2281       /* We only have to keep saved state at branch targets.  If
2282          we're at a branch target and the state here hasn't been set
2283          yet, we set it now.  You might notice that `ret' targets
2284          won't necessarily have FLAG_BRANCH_TARGET set.  This
2285          doesn't matter, since those states will be filled in by
2286          merge_into.  */
2287       /* Note that other parts of the compiler assume that there is a
2288          label with a type map at PC=0.  */
2289       if (vfr->states[vfr->PC] == NULL
2290           && (vfr->PC == 0 || (vfr->flags[vfr->PC] & FLAG_BRANCH_TARGET) != 0))
2291         add_new_state (vfr->PC, vfr->current_state);
2292
2293       /* Set this before handling exceptions so that debug output is
2294          sane.  */
2295       vfr->start_PC = vfr->PC;
2296
2297       /* Update states for all active exception handlers.  Ordinarily
2298          there are not many exception handlers.  So we simply run
2299          through them all.  */
2300       for (i = 0; i < vfr->current_method->exc_count; ++i)
2301         {
2302           int hpc, start, end, htype;
2303           vfy_get_exception (vfr->exception, i, &hpc, &start, &end, &htype);
2304           if (vfr->PC >= start && vfr->PC < end)
2305             {
2306               type handler = make_type_from_class (vfy_throwable_type ());
2307               if (htype != 0)
2308                 handler = check_class_constant (htype);
2309               push_exception_jump (handler, hpc);
2310             }
2311         }
2312
2313
2314       debug_print_state (vfr->current_state, "   ", vfr->PC,
2315                          vfr->current_method->max_stack,
2316                          vfr->current_method->max_locals);
2317       opcode = (java_opcode) vfr->bytecode[vfr->PC++];
2318       switch (opcode)
2319         {
2320         case op_nop:
2321           break;
2322
2323         case op_aconst_null:
2324           push_type (null_type);
2325           break;
2326
2327         case op_iconst_m1:
2328         case op_iconst_0:
2329         case op_iconst_1:
2330         case op_iconst_2:
2331         case op_iconst_3:
2332         case op_iconst_4:
2333         case op_iconst_5:
2334           push_type (int_type);
2335           break;
2336
2337         case op_lconst_0:
2338         case op_lconst_1:
2339           push_type (long_type);
2340           break;
2341
2342         case op_fconst_0:
2343         case op_fconst_1:
2344         case op_fconst_2:
2345           push_type (float_type);
2346           break;
2347
2348         case op_dconst_0:
2349         case op_dconst_1:
2350           push_type (double_type);
2351           break;
2352
2353         case op_bipush:
2354           get_byte ();
2355           push_type (int_type);
2356           break;
2357
2358         case op_sipush:
2359           get_short ();
2360           push_type (int_type);
2361           break;
2362
2363         case op_ldc:
2364           push_type_t (check_constant (get_byte ()));
2365           break;
2366         case op_ldc_w:
2367           push_type_t (check_constant (get_ushort ()));
2368           break;
2369         case op_ldc2_w:
2370           push_type_t (check_wide_constant (get_ushort ()));
2371           break;
2372
2373         case op_iload:
2374           push_type_t (get_variable (get_byte (), int_type));
2375           break;
2376         case op_lload:
2377           push_type_t (get_variable (get_byte (), long_type));
2378           break;
2379         case op_fload:
2380           push_type_t (get_variable (get_byte (), float_type));
2381           break;
2382         case op_dload:
2383           push_type_t (get_variable (get_byte (), double_type));
2384           break;
2385         case op_aload:
2386           push_type_t (get_variable (get_byte (), reference_type));
2387           break;
2388
2389         case op_iload_0:
2390         case op_iload_1:
2391         case op_iload_2:
2392         case op_iload_3:
2393           push_type_t (get_variable (opcode - op_iload_0, int_type));
2394           break;
2395         case op_lload_0:
2396         case op_lload_1:
2397         case op_lload_2:
2398         case op_lload_3:
2399           push_type_t (get_variable (opcode - op_lload_0, long_type));
2400           break;
2401         case op_fload_0:
2402         case op_fload_1:
2403         case op_fload_2:
2404         case op_fload_3:
2405           push_type_t (get_variable (opcode - op_fload_0, float_type));
2406           break;
2407         case op_dload_0:
2408         case op_dload_1:
2409         case op_dload_2:
2410         case op_dload_3:
2411           push_type_t (get_variable (opcode - op_dload_0, double_type));
2412           break;
2413         case op_aload_0:
2414         case op_aload_1:
2415         case op_aload_2:
2416         case op_aload_3:
2417           push_type_t (get_variable (opcode - op_aload_0, reference_type));
2418           break;
2419         case op_iaload:
2420           pop_type (int_type);
2421           push_type_t (require_array_type (pop_init_ref (reference_type),
2422                                          int_type));
2423           break;
2424         case op_laload:
2425           pop_type (int_type);
2426           push_type_t (require_array_type (pop_init_ref (reference_type),
2427                                          long_type));
2428           break;
2429         case op_faload:
2430           pop_type (int_type);
2431           push_type_t (require_array_type (pop_init_ref (reference_type),
2432                                          float_type));
2433           break;
2434         case op_daload:
2435           pop_type (int_type);
2436           push_type_t (require_array_type (pop_init_ref (reference_type),
2437                                          double_type));
2438           break;
2439         case op_aaload:
2440           pop_type (int_type);
2441           push_type_t (require_array_type (pop_init_ref (reference_type),
2442                                          reference_type));
2443           break;
2444         case op_baload:
2445           pop_type (int_type);
2446           require_array_type (pop_init_ref (reference_type), byte_type);
2447           push_type (int_type);
2448           break;
2449         case op_caload:
2450           pop_type (int_type);
2451           require_array_type (pop_init_ref (reference_type), char_type);
2452           push_type (int_type);
2453           break;
2454         case op_saload:
2455           pop_type (int_type);
2456           require_array_type (pop_init_ref (reference_type), short_type);
2457           push_type (int_type);
2458           break;
2459         case op_istore:
2460           set_variable (get_byte (), pop_type (int_type));
2461           break;
2462         case op_lstore:
2463           set_variable (get_byte (), pop_type (long_type));
2464           break;
2465         case op_fstore:
2466           set_variable (get_byte (), pop_type (float_type));
2467           break;
2468         case op_dstore:
2469           set_variable (get_byte (), pop_type (double_type));
2470           break;
2471         case op_astore:
2472           set_variable (get_byte (), pop_ref_or_return ());
2473           break;
2474         case op_istore_0:
2475         case op_istore_1:
2476         case op_istore_2:
2477         case op_istore_3:
2478           set_variable (opcode - op_istore_0, pop_type (int_type));
2479           break;
2480         case op_lstore_0:
2481         case op_lstore_1:
2482         case op_lstore_2:
2483         case op_lstore_3:
2484           set_variable (opcode - op_lstore_0, pop_type (long_type));
2485           break;
2486         case op_fstore_0:
2487         case op_fstore_1:
2488         case op_fstore_2:
2489         case op_fstore_3:
2490           set_variable (opcode - op_fstore_0, pop_type (float_type));
2491           break;
2492         case op_dstore_0:
2493         case op_dstore_1:
2494         case op_dstore_2:
2495         case op_dstore_3:
2496           set_variable (opcode - op_dstore_0, pop_type (double_type));
2497           break;
2498         case op_astore_0:
2499         case op_astore_1:
2500         case op_astore_2:
2501         case op_astore_3:
2502           set_variable (opcode - op_astore_0, pop_ref_or_return ());
2503           break;
2504         case op_iastore:
2505           pop_type (int_type);
2506           pop_type (int_type);
2507           require_array_type (pop_init_ref (reference_type), int_type);
2508           break;
2509         case op_lastore:
2510           pop_type (long_type);
2511           pop_type (int_type);
2512           require_array_type (pop_init_ref (reference_type), long_type);
2513           break;
2514         case op_fastore:
2515           pop_type (float_type);
2516           pop_type (int_type);
2517           require_array_type (pop_init_ref (reference_type), float_type);
2518           break;
2519         case op_dastore:
2520           pop_type (double_type);
2521           pop_type (int_type);
2522           require_array_type (pop_init_ref (reference_type), double_type);
2523           break;
2524         case op_aastore:
2525           pop_type (reference_type);
2526           pop_type (int_type);
2527           require_array_type (pop_init_ref (reference_type), reference_type);
2528           break;
2529         case op_bastore:
2530           pop_type (int_type);
2531           pop_type (int_type);
2532           require_array_type (pop_init_ref (reference_type), byte_type);
2533           break;
2534         case op_castore:
2535           pop_type (int_type);
2536           pop_type (int_type);
2537           require_array_type (pop_init_ref (reference_type), char_type);
2538           break;
2539         case op_sastore:
2540           pop_type (int_type);
2541           pop_type (int_type);
2542           require_array_type (pop_init_ref (reference_type), short_type);
2543           break;
2544         case op_pop:
2545           pop32 ();
2546           break;
2547         case op_pop2:
2548           {
2549             type t = pop_raw ();
2550             if (! type_iswide (&t))
2551               pop32 ();
2552           }
2553           break;
2554         case op_dup:
2555           {
2556             type t = pop32 ();
2557             push_type_t (t);
2558             push_type_t (t);
2559           }
2560           break;
2561         case op_dup_x1:
2562           {
2563             type t1 = pop32 ();
2564             type t2 = pop32 ();
2565             push_type_t (t1);
2566             push_type_t (t2);
2567             push_type_t (t1);
2568           }
2569           break;
2570         case op_dup_x2:
2571           {
2572             type t1 = pop32 ();
2573             type t2 = pop_raw ();
2574             if (! type_iswide (&t2))
2575               {
2576                 type t3 = pop32 ();
2577                 push_type_t (t1);
2578                 push_type_t (t3);
2579               }
2580             else
2581               push_type_t (t1);
2582             push_type_t (t2);
2583             push_type_t (t1);
2584           }
2585           break;
2586         case op_dup2:
2587           {
2588             type t = pop_raw ();
2589             if (! type_iswide (&t))
2590               {
2591                 type t2 = pop32 ();
2592                 push_type_t (t2);
2593                 push_type_t (t);
2594                 push_type_t (t2);
2595               }
2596             else
2597               push_type_t (t);
2598             push_type_t (t);
2599           }
2600           break;
2601         case op_dup2_x1:
2602           {
2603             type t1 = pop_raw ();
2604             type t2 = pop32 ();
2605             if (! type_iswide (&t1))
2606               {
2607                 type t3 = pop32 ();
2608                 push_type_t (t2);
2609                 push_type_t (t1);
2610                 push_type_t (t3);
2611               }
2612             else
2613               push_type_t (t1);
2614             push_type_t (t2);
2615             push_type_t (t1);
2616           }
2617           break;
2618         case op_dup2_x2:
2619           {
2620             type t1 = pop_raw ();
2621             if (type_iswide (&t1))
2622               {
2623                 type t2 = pop_raw ();
2624                 if (type_iswide (&t2))
2625                   {
2626                     push_type_t (t1);
2627                     push_type_t (t2);
2628                   }
2629                 else
2630                   {
2631                     type t3 = pop32 ();
2632                     push_type_t (t1);
2633                     push_type_t (t3);
2634                     push_type_t (t2);
2635                   }
2636                 push_type_t (t1);
2637               }
2638             else
2639               {
2640                 type t2 = pop32 ();
2641                 type t3 = pop_raw ();
2642                 if (type_iswide (&t3))
2643                   {
2644                     push_type_t (t2);
2645                     push_type_t (t1);
2646                   }
2647                 else
2648                   {
2649                     type t4 = pop32 ();
2650                     push_type_t (t2);
2651                     push_type_t (t1);
2652                     push_type_t (t4);
2653                   }
2654                 push_type_t (t3);
2655                 push_type_t (t2);
2656                 push_type_t (t1);
2657               }
2658           }
2659           break;
2660         case op_swap:
2661           {
2662             type t1 = pop32 ();
2663             type t2 = pop32 ();
2664             push_type_t (t1);
2665             push_type_t (t2);
2666           }
2667           break;
2668         case op_iadd:
2669         case op_isub:
2670         case op_imul:
2671         case op_idiv:
2672         case op_irem:
2673         case op_ishl:
2674         case op_ishr:
2675         case op_iushr:
2676         case op_iand:
2677         case op_ior:
2678         case op_ixor:
2679           pop_type (int_type);
2680           push_type_t (pop_type (int_type));
2681           break;
2682         case op_ladd:
2683         case op_lsub:
2684         case op_lmul:
2685         case op_ldiv:
2686         case op_lrem:
2687         case op_land:
2688         case op_lor:
2689         case op_lxor:
2690           pop_type (long_type);
2691           push_type_t (pop_type (long_type));
2692           break;
2693         case op_lshl:
2694         case op_lshr:
2695         case op_lushr:
2696           pop_type (int_type);
2697           push_type_t (pop_type (long_type));
2698           break;
2699         case op_fadd:
2700         case op_fsub:
2701         case op_fmul:
2702         case op_fdiv:
2703         case op_frem:
2704           pop_type (float_type);
2705           push_type_t (pop_type (float_type));
2706           break;
2707         case op_dadd:
2708         case op_dsub:
2709         case op_dmul:
2710         case op_ddiv:
2711         case op_drem:
2712           pop_type (double_type);
2713           push_type_t (pop_type (double_type));
2714           break;
2715         case op_ineg:
2716         case op_i2b:
2717         case op_i2c:
2718         case op_i2s:
2719           push_type_t (pop_type (int_type));
2720           break;
2721         case op_lneg:
2722           push_type_t (pop_type (long_type));
2723           break;
2724         case op_fneg:
2725           push_type_t (pop_type (float_type));
2726           break;
2727         case op_dneg:
2728           push_type_t (pop_type (double_type));
2729           break;
2730         case op_iinc:
2731           get_variable (get_byte (), int_type);
2732           get_byte ();
2733           break;
2734         case op_i2l:
2735           pop_type (int_type);
2736           push_type (long_type);
2737           break;
2738         case op_i2f:
2739           pop_type (int_type);
2740           push_type (float_type);
2741           break;
2742         case op_i2d:
2743           pop_type (int_type);
2744           push_type (double_type);
2745           break;
2746         case op_l2i:
2747           pop_type (long_type);
2748           push_type (int_type);
2749           break;
2750         case op_l2f:
2751           pop_type (long_type);
2752           push_type (float_type);
2753           break;
2754         case op_l2d:
2755           pop_type (long_type);
2756           push_type (double_type);
2757           break;
2758         case op_f2i:
2759           pop_type (float_type);
2760           push_type (int_type);
2761           break;
2762         case op_f2l:
2763           pop_type (float_type);
2764           push_type (long_type);
2765           break;
2766         case op_f2d:
2767           pop_type (float_type);
2768           push_type (double_type);
2769           break;
2770         case op_d2i:
2771           pop_type (double_type);
2772           push_type (int_type);
2773           break;
2774         case op_d2l:
2775           pop_type (double_type);
2776           push_type (long_type);
2777           break;
2778         case op_d2f:
2779           pop_type (double_type);
2780           push_type (float_type);
2781           break;
2782         case op_lcmp:
2783           pop_type (long_type);
2784           pop_type (long_type);
2785           push_type (int_type);
2786           break;
2787         case op_fcmpl:
2788         case op_fcmpg:
2789           pop_type (float_type);
2790           pop_type (float_type);
2791           push_type (int_type);
2792           break;
2793         case op_dcmpl:
2794         case op_dcmpg:
2795           pop_type (double_type);
2796           pop_type (double_type);
2797           push_type (int_type);
2798           break;
2799         case op_ifeq:
2800         case op_ifne:
2801         case op_iflt:
2802         case op_ifge:
2803         case op_ifgt:
2804         case op_ifle:
2805           pop_type (int_type);
2806           push_jump (get_short ());
2807           break;
2808         case op_if_icmpeq:
2809         case op_if_icmpne:
2810         case op_if_icmplt:
2811         case op_if_icmpge:
2812         case op_if_icmpgt:
2813         case op_if_icmple:
2814           pop_type (int_type);
2815           pop_type (int_type);
2816           push_jump (get_short ());
2817           break;
2818         case op_if_acmpeq:
2819         case op_if_acmpne:
2820           pop_type (reference_type);
2821           pop_type (reference_type);
2822           push_jump (get_short ());
2823           break;
2824         case op_goto:
2825           push_jump (get_short ());
2826           invalidate_pc ();
2827           break;
2828         case op_jsr:
2829           handle_jsr_insn (get_short ());
2830           break;
2831         case op_ret:
2832           handle_ret_insn (get_byte ());
2833           break;
2834         case op_tableswitch:
2835           {
2836             int i;
2837             jint low, high;
2838             pop_type (int_type);
2839             skip_padding ();
2840             push_jump (get_int ());
2841             low = get_int ();
2842             high = get_int ();
2843             /* Already checked LOW -vs- HIGH.  */
2844             for (i = low; i <= high; ++i)
2845               push_jump (get_int ());
2846             invalidate_pc ();
2847           }
2848           break;
2849
2850         case op_lookupswitch:
2851           {
2852             int i;
2853             jint npairs, lastkey;
2854
2855             pop_type (int_type);
2856             skip_padding ();
2857             push_jump (get_int ());
2858             npairs = get_int ();
2859             /* Already checked NPAIRS >= 0.  */
2860             lastkey = 0;
2861             for (i = 0; i < npairs; ++i)
2862               {
2863                 jint key = get_int ();
2864                 if (i > 0 && key <= lastkey)
2865                   verify_fail_pc ("lookupswitch pairs unsorted", vfr->start_PC);
2866                 lastkey = key;
2867                 push_jump (get_int ());
2868               }
2869             invalidate_pc ();
2870           }
2871           break;
2872         case op_ireturn:
2873           check_return_type (pop_type (int_type));
2874           invalidate_pc ();
2875           break;
2876         case op_lreturn:
2877           check_return_type (pop_type (long_type));
2878           invalidate_pc ();
2879           break;
2880         case op_freturn:
2881           check_return_type (pop_type (float_type));
2882           invalidate_pc ();
2883           break;
2884         case op_dreturn:
2885           check_return_type (pop_type (double_type));
2886           invalidate_pc ();
2887           break;
2888         case op_areturn:
2889           check_return_type (pop_init_ref (reference_type));
2890           invalidate_pc ();
2891           break;
2892         case op_return:
2893           /* We only need to check this when the return type is
2894              void, because all instance initializers return void.  */
2895           if (this_is_init)
2896             state_check_this_initialized (vfr->current_state);
2897           check_return_type (make_type (void_type));
2898           invalidate_pc ();
2899           break;
2900         case op_getstatic:
2901           push_type_t (check_field_constant (get_ushort (), NULL, false));
2902           break;
2903         case op_putstatic:
2904           pop_type_t (check_field_constant (get_ushort (), NULL, false));
2905           break;
2906         case op_getfield:
2907           {
2908             type klass;
2909             type field = check_field_constant (get_ushort (), &klass, false);
2910             pop_type_t (klass);
2911             push_type_t (field);
2912           }
2913           break;
2914         case op_putfield:
2915           {
2916             type klass;
2917             type field = check_field_constant (get_ushort (), &klass, true);
2918             pop_type_t (field);
2919             pop_type_t (klass);
2920           }
2921           break;
2922
2923         case op_invokevirtual:
2924         case op_invokespecial:
2925         case op_invokestatic:
2926         case op_invokeinterface:
2927           {
2928             vfy_string method_name, method_signature;
2929             const char *namec;
2930             int i, arg_count;
2931             type rt;
2932             bool is_init = false;
2933
2934             type class_type
2935               = check_method_constant (get_ushort (),
2936                                        opcode == op_invokeinterface,
2937                                        &method_name,
2938                                        &method_signature);
2939             /* NARGS is only used when we're processing
2940                invokeinterface.  It is simplest for us to compute it
2941                here and then verify it later.  */
2942             int nargs = 0;
2943             if (opcode == op_invokeinterface)
2944               {
2945                 nargs = get_byte ();
2946                 if (get_byte () != 0)
2947                   verify_fail ("invokeinterface dummy byte is wrong");
2948               }
2949
2950             namec = vfy_string_bytes (method_name);
2951
2952             if (vfy_strings_equal (method_name, vfy_init_name()))
2953               {
2954                 is_init = true;
2955                 if (opcode != op_invokespecial)
2956                   verify_fail ("can't invoke <init>");
2957               }
2958             else if (namec[0] == '<')
2959               verify_fail ("can't invoke method starting with `<'");
2960
2961             arg_count = vfy_count_arguments (method_signature);
2962             {
2963               /* Pop arguments and check types.  */
2964               type *arg_types = (type *) vfy_alloc (arg_count * sizeof (type));
2965
2966               compute_argument_types (method_signature, arg_types);
2967               for (i = arg_count - 1; i >= 0; --i)
2968                 {
2969                   /* This is only used for verifying the byte for
2970                      invokeinterface.  */
2971                   nargs -= type_depth (&arg_types[i]);
2972                   pop_init_ref_t (arg_types[i]);
2973                 }
2974
2975               vfy_free (arg_types);
2976             }
2977
2978             if (opcode == op_invokeinterface
2979                 && nargs != 1)
2980               verify_fail ("wrong argument count for invokeinterface");
2981
2982             if (opcode != op_invokestatic)
2983               {
2984                 type raw;
2985                 type t = class_type;
2986                 if (is_init)
2987                   {
2988                     /* In this case the PC doesn't matter.  */
2989                     type_set_uninitialized (&t, UNINIT);
2990                     /* FIXME: check to make sure that the <init>
2991                        call is to the right class.
2992                        It must either be super or an exact class
2993                        match.  */
2994                   }
2995                 raw = pop_raw ();
2996                 if (! types_compatible (&t, &raw))
2997                   verify_fail ("incompatible type on stack");
2998
2999                 if (is_init)
3000                   state_set_initialized (vfr->current_state,
3001                     type_get_pc (&raw), vfr->current_method->max_locals);
3002               }
3003
3004             rt = compute_return_type (method_signature);
3005             if (! type_isvoid (&rt))
3006               push_type_t (rt);
3007           }
3008           break;
3009
3010         case op_new:
3011           {
3012             type t = check_class_constant (get_ushort ());
3013             if (type_isarray (&t) || type_isinterface (&t)
3014                 || type_isabstract (&t))
3015               verify_fail ("type is array, interface, or abstract");
3016             type_set_uninitialized (&t, vfr->start_PC);
3017             push_type_t (t);
3018           }
3019           break;
3020
3021         case op_newarray:
3022           {
3023             int atype = get_byte ();
3024             type t;
3025             /* We intentionally have chosen constants to make this
3026                valid.  */
3027             if (atype < boolean_type || atype > long_type)
3028               verify_fail_pc ("type not primitive", vfr->start_PC);
3029             pop_type (int_type);
3030             init_type_from_class (&t, construct_primitive_array_type (atype));
3031             push_type_t (t);
3032           }
3033           break;
3034         case op_anewarray:
3035           {
3036             type t;
3037             pop_type (int_type);
3038             t = check_class_constant (get_ushort ());
3039             push_type_t (type_to_array (&t));
3040           }
3041           break;
3042         case op_arraylength:
3043           {
3044             type t = pop_init_ref (reference_type);
3045             if (! type_isarray (&t) && ! type_isnull (&t))
3046               verify_fail ("array type expected");
3047             push_type (int_type);
3048           }
3049           break;
3050         case op_athrow:
3051           pop_type_t (make_type_from_class (vfy_throwable_type ()));
3052           invalidate_pc ();
3053           break;
3054         case op_checkcast:
3055           pop_init_ref (reference_type);
3056           push_type_t (check_class_constant (get_ushort ()));
3057           break;
3058         case op_instanceof:
3059           pop_init_ref (reference_type);
3060           check_class_constant (get_ushort ());
3061           push_type (int_type);
3062           break;
3063         case op_monitorenter:
3064           pop_init_ref (reference_type);
3065           break;
3066         case op_monitorexit:
3067           pop_init_ref (reference_type);
3068           break;
3069         case op_wide:
3070           {
3071             switch (get_byte ())
3072               {
3073               case op_iload:
3074                 push_type_t (get_variable (get_ushort (), int_type));
3075                 break;
3076               case op_lload:
3077                 push_type_t (get_variable (get_ushort (), long_type));
3078                 break;
3079               case op_fload:
3080                 push_type_t (get_variable (get_ushort (), float_type));
3081                 break;
3082               case op_dload:
3083                 push_type_t (get_variable (get_ushort (), double_type));
3084                 break;
3085               case op_aload:
3086                 push_type_t (get_variable (get_ushort (), reference_type));
3087                 break;
3088               case op_istore:
3089                 set_variable (get_ushort (), pop_type (int_type));
3090                 break;
3091               case op_lstore:
3092                 set_variable (get_ushort (), pop_type (long_type));
3093                 break;
3094               case op_fstore:
3095                 set_variable (get_ushort (), pop_type (float_type));
3096                 break;
3097               case op_dstore:
3098                 set_variable (get_ushort (), pop_type (double_type));
3099                 break;
3100               case op_astore:
3101                 set_variable (get_ushort (), pop_init_ref (reference_type));
3102                 break;
3103               case op_ret:
3104                 handle_ret_insn (get_short ());
3105                 break;
3106               case op_iinc:
3107                 get_variable (get_ushort (), int_type);
3108                 get_short ();
3109                 break;
3110               default:
3111                 verify_fail_pc ("unrecognized wide instruction", vfr->start_PC);
3112               }
3113           }
3114           break;
3115         case op_multianewarray:
3116           {
3117             int i;
3118             type atype = check_class_constant (get_ushort ());
3119             int dim = get_byte ();
3120             if (dim < 1)
3121               verify_fail_pc ("too few dimensions to multianewarray", vfr->start_PC);
3122             type_verify_dimensions (&atype, dim);
3123             for (i = 0; i < dim; ++i)
3124               pop_type (int_type);
3125             push_type_t (atype);
3126           }
3127           break;
3128         case op_ifnull:
3129         case op_ifnonnull:
3130           pop_type (reference_type);
3131           push_jump (get_short ());
3132           break;
3133         case op_goto_w:
3134           push_jump (get_int ());
3135           invalidate_pc ();
3136           break;
3137         case op_jsr_w:
3138           handle_jsr_insn (get_int ());
3139           break;
3140
3141         default:
3142           /* Unrecognized opcode.  */
3143           verify_fail_pc ("unrecognized instruction in verify_instructions_0",
3144                        vfr->start_PC);
3145         }
3146     }
3147 }
3148
3149 /* This turns a `type' into something suitable for use by the type map
3150    in the other parts of the compiler.  In particular, reference types
3151    are mapped to Object, primitive types are unchanged, and other
3152    types are mapped using special functions declared in verify.h.  */
3153 static vfy_jclass
3154 collapse_type (type *t)
3155 {
3156   switch (t->key)
3157     {
3158     case void_type:
3159     case boolean_type:
3160     case char_type:
3161     case float_type:
3162     case double_type:
3163     case byte_type:
3164     case short_type:
3165     case int_type:
3166     case long_type:
3167       return vfy_get_primitive_type (t->key);
3168
3169     case unsuitable_type:
3170     case continuation_type:
3171       return vfy_unsuitable_type ();
3172
3173     case return_address_type:
3174       return vfy_return_address_type ();
3175
3176     case null_type:
3177       return vfy_null_type ();
3178
3179     case reference_type:
3180     case uninitialized_reference_type:
3181       return vfy_object_type ();
3182     }
3183
3184   abort ();
3185 }
3186
3187 static void
3188 verify_instructions (void)
3189 {
3190   int i;
3191
3192   branch_prepass ();
3193   verify_instructions_0 ();
3194
3195   /* Now tell the rest of the compiler about the types we've found.  */
3196   for (i = 0; i < vfr->current_method->code_length; ++i)
3197     {
3198       int j, slot;
3199       struct state *curr;
3200
3201       if ((vfr->flags[i] & FLAG_INSN_SEEN) != 0)
3202         vfy_note_instruction_seen (i);
3203
3204       if (! vfr->states[i])
3205         continue;
3206
3207       curr = vfr->states[i]->val;
3208       vfy_note_stack_depth (vfr->current_method, i, curr->stackdepth);
3209
3210       /* Tell the compiler about each local variable.  */
3211       for (j = 0; j < vfr->current_method->max_locals; ++j)
3212         vfy_note_local_type (vfr->current_method, i, j,
3213                              collapse_type (&curr->locals[j]));
3214       /* Tell the compiler about each stack slot.  */
3215       for (slot = j = 0; j < curr->stacktop; ++j, ++slot)
3216         {
3217           vfy_note_stack_type (vfr->current_method, i, slot,
3218                                collapse_type (&curr->stack[j]));
3219           if (type_iswide (&curr->stack[j]))
3220             {
3221               ++slot;
3222               vfy_note_stack_type (vfr->current_method, i, slot,
3223                                    vfy_unsuitable_type ());
3224             }
3225         }
3226       if (slot != curr->stackdepth)
3227         abort ();
3228     }
3229 }
3230
3231 static void
3232 make_verifier_context (vfy_method *m)
3233 {
3234   vfr = (verifier_context *) vfy_alloc (sizeof (struct verifier_context));
3235
3236   vfr->current_method = m;
3237   vfr->bytecode = vfy_get_bytecode (m);
3238   vfr->exception = vfy_get_exceptions (m);
3239   vfr->current_class = m->defining_class;
3240
3241   vfr->states = NULL;
3242   vfr->flags = NULL;
3243   vfr->utf8_list = NULL;
3244   vfr->isect_list = NULL;
3245 }
3246
3247 static void
3248 free_verifier_context (void)
3249 {
3250   vfy_string_list *utf8_list;
3251   ref_intersection *isect_list;
3252
3253   if (vfr->flags)
3254     vfy_free (vfr->flags);
3255
3256   utf8_list = vfr->utf8_list;
3257   while (utf8_list != NULL)
3258     {
3259       vfy_string_list *n = utf8_list->next;
3260       vfy_free (utf8_list);
3261       utf8_list = n;
3262     }
3263
3264   isect_list = vfr->isect_list;
3265   while (isect_list != NULL)
3266     {
3267       ref_intersection *next = isect_list->alloc_next;
3268       vfy_free (isect_list);
3269       isect_list = next;
3270     }
3271
3272   if (vfr->states != NULL)
3273     {
3274       int i;
3275       for (i = 0; i < vfr->current_method->code_length; ++i)
3276         {
3277           state_list *iter = vfr->states[i];
3278           while (iter != NULL)
3279             {
3280               state_list *next = iter->next;
3281               free_state (iter->val);
3282               vfy_free (iter->val);
3283               vfy_free (iter);
3284               iter = next;
3285             }
3286         }
3287       vfy_free (vfr->states);
3288     }
3289
3290   vfy_free (vfr);
3291 }
3292
3293 int
3294 verify_method (vfy_method *meth)
3295 {
3296   debug_print ("verify_method (%s) %i\n", vfy_string_bytes (meth->name),
3297                meth->code_length);
3298
3299   if (vfr != NULL)
3300     verify_fail ("verifier re-entered");
3301
3302   make_verifier_context (meth);
3303   verify_instructions ();
3304   free_verifier_context ();
3305   vfr = NULL;
3306
3307   return 1;
3308 }