gcc/java/verify-impl.c

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