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   int len;
2039   type t;
2040
2041   type ct = handle_field_or_method (index,
2042                                     JV_CONSTANT_Fieldref,
2043                                     &name, &field_type);
2044   if (class_type)
2045     *class_type = ct;
2046   typec = vfy_string_bytes (field_type);
2047   len = vfy_string_length (field_type);
2048   if (typec[0] == '[' || typec[0] == 'L')
2049     init_type_from_string (&t, field_type);
2050   else
2051     init_type_from_tag (&t, get_type_val_for_signature (typec[0]));
2052
2053   /* We have an obscure special case here: we can use `putfield' on a
2054      field declared in this class, even if `this' has not yet been
2055      initialized.  */
2056   if (putfield
2057       && ! type_initialized (&vfr->current_state->this_type)
2058       && vfr->current_state->this_type.pc == SELF
2059       && types_equal (&vfr->current_state->this_type, &ct)
2060       && vfy_class_has_field (vfr->current_class, name, field_type))
2061     /* Note that we don't actually know whether we're going to match
2062        against 'this' or some other object of the same type.  So,
2063        here we set things up so that it doesn't matter.  This relies
2064        on knowing what our caller is up to.  */
2065     type_set_uninitialized (class_type, EITHER);
2066
2067   return t;
2068 }
2069
2070 static type
2071 check_method_constant (int index, bool is_interface,
2072                             vfy_string *method_name,
2073                             vfy_string *method_signature)
2074 {
2075   return handle_field_or_method (index,
2076                                  (is_interface
2077                                   ? JV_CONSTANT_InterfaceMethodref
2078                                   : JV_CONSTANT_Methodref),
2079                                  method_name, method_signature);
2080 }
2081
2082 static const char *
2083 get_one_type (const char *p, type *t)
2084 {
2085   const char *start = p;
2086   vfy_jclass k;
2087   type_val rt;
2088   char v;
2089
2090   int arraycount = 0;
2091   while (*p == '[')
2092     {
2093       ++arraycount;
2094       ++p;
2095     }
2096
2097   v = *p++;
2098
2099   if (v == 'L')
2100     {
2101       vfy_string name;
2102       while (*p != ';')
2103         ++p;
2104       ++p;
2105       name = vfy_get_string (start, p - start);
2106       *t = make_type_from_string (name);
2107       return p;
2108     }
2109
2110   /* Casting to jchar here is ok since we are looking at an ASCII
2111      character.  */
2112   rt = get_type_val_for_signature (v);
2113
2114   if (arraycount == 0)
2115     {
2116       /* Callers of this function eventually push their arguments on
2117          the stack.  So, promote them here.  */
2118       type new_t = make_type (rt);
2119       vfy_promote_type (&new_t);
2120       *t = new_t;
2121       return p;
2122     }
2123
2124   k = construct_primitive_array_type (rt);
2125   while (--arraycount > 0)
2126     k = vfy_get_array_class (k);
2127   *t = make_type_from_class (k);
2128   return p;
2129 }
2130
2131 static void
2132 compute_argument_types (vfy_string signature, type *types)
2133 {
2134   int i;
2135   const char *p = vfy_string_bytes (signature);
2136
2137   /* Skip `('.  */
2138   ++p;
2139
2140   i = 0;
2141   while (*p != ')')
2142     p = get_one_type (p, &types[i++]);
2143 }
2144
2145 static type
2146 compute_return_type (vfy_string signature)
2147 {
2148   const char *p = vfy_string_bytes (signature);
2149   type t;
2150   while (*p != ')')
2151     ++p;
2152   ++p;
2153   get_one_type (p, &t);
2154   return t;
2155 }
2156
2157 static void
2158 check_return_type (type onstack)
2159 {
2160   type rt = compute_return_type (vfy_get_signature (vfr->current_method));
2161   if (! types_compatible (&rt, &onstack))
2162     verify_fail ("incompatible return type");
2163 }
2164
2165 /* Initialize the stack for the new method.  Returns true if this
2166    method is an instance initializer.  */
2167 static bool
2168 initialize_stack (void)
2169 {
2170   int arg_count, i;
2171   int var = 0;
2172   bool is_init = vfy_strings_equal (vfy_get_method_name (vfr->current_method),
2173                                     vfy_init_name());
2174   bool is_clinit = vfy_strings_equal (vfy_get_method_name (vfr->current_method),
2175                                       vfy_clinit_name());
2176
2177   if (! vfy_is_static (vfr->current_method))
2178     {
2179       type kurr = make_type_from_class (vfr->current_class);
2180       if (is_init)
2181         {
2182           type_set_uninitialized (&kurr, SELF);
2183           is_init = true;
2184         }
2185       else if (is_clinit)
2186         verify_fail ("<clinit> method must be static");
2187       set_variable (0, kurr);
2188       state_set_this_type (vfr->current_state, &kurr);
2189       ++var;
2190     }
2191   else
2192     {
2193       if (is_init)
2194         verify_fail ("<init> method must be non-static");
2195     }
2196
2197   /* We have to handle wide arguments specially here.  */
2198   arg_count = vfy_count_arguments (vfy_get_signature (vfr->current_method));
2199   {
2200     type *arg_types = (type *) vfy_alloc (arg_count * sizeof (type));
2201     compute_argument_types (vfy_get_signature (vfr->current_method), arg_types);
2202     for (i = 0; i < arg_count; ++i)
2203       {
2204         set_variable (var, arg_types[i]);
2205         ++var;
2206         if (type_iswide (&arg_types[i]))
2207           ++var;
2208       }
2209     vfy_free (arg_types);
2210   }
2211
2212   return is_init;
2213 }
2214
2215 static void
2216 verify_instructions_0 (void)
2217 {
2218   int i;
2219   bool this_is_init;
2220
2221   vfr->current_state = make_state (vfr->current_method->max_stack,
2222                                    vfr->current_method->max_locals);
2223
2224   vfr->PC = 0;
2225   vfr->start_PC = 0;
2226
2227   /*  True if we are verifying an instance initializer.  */
2228   this_is_init = initialize_stack ();
2229
2230   vfr->states = (state_list **) vfy_alloc (sizeof (state_list *)
2231                                       * vfr->current_method->code_length);
2232
2233   for (i = 0; i < vfr->current_method->code_length; ++i)
2234     vfr->states[i] = NULL;
2235
2236   vfr->next_verify_state = NULL;
2237
2238   while (true)
2239     {
2240       java_opcode opcode;
2241
2242       /* If the PC was invalidated, get a new one from the work list.  */
2243       if (vfr->PC == NO_NEXT)
2244         {
2245           state *new_state = pop_jump ();
2246           /* If it is null, we're done.  */
2247           if (new_state == NULL)
2248             break;
2249
2250           vfr->PC = new_state->pc;
2251           debug_print ("== State pop from pending list\n");
2252           /* Set up the current state.  */
2253           copy_state (vfr->current_state, new_state,
2254             vfr->current_method->max_stack, vfr->current_method->max_locals);
2255         }
2256       else
2257         {
2258           /* We only have to do this checking in the situation where
2259              control flow falls through from the previous instruction.
2260              Otherwise merging is done at the time we push the branch.
2261              Note that we'll catch the off-the-end problem just
2262              below.  */
2263           if (vfr->PC < vfr->current_method->code_length
2264               && vfr->states[vfr->PC] != NULL)
2265             {
2266               /* We've already visited this instruction.  So merge
2267                  the states together.  It is simplest, but not most
2268                  efficient, to just always invalidate the PC here.  */
2269               merge_into (vfr->PC, vfr->current_state);
2270               invalidate_pc ();
2271               continue;
2272             }
2273         }
2274
2275       /* Control can't fall off the end of the bytecode.  We need to
2276          check this in both cases, not just the fall-through case,
2277          because we don't check to see whether a `jsr' appears at
2278          the end of the bytecode until we process a `ret'.  */
2279       if (vfr->PC >= vfr->current_method->code_length)
2280         verify_fail ("fell off end");
2281       vfr->flags[vfr->PC] |= FLAG_INSN_SEEN;
2282
2283       /* We only have to keep saved state at branch targets.  If
2284          we're at a branch target and the state here hasn't been set
2285          yet, we set it now.  You might notice that `ret' targets
2286          won't necessarily have FLAG_BRANCH_TARGET set.  This
2287          doesn't matter, since those states will be filled in by
2288          merge_into.  */
2289       /* Note that other parts of the compiler assume that there is a
2290          label with a type map at PC=0.  */
2291       if (vfr->states[vfr->PC] == NULL
2292           && (vfr->PC == 0 || (vfr->flags[vfr->PC] & FLAG_BRANCH_TARGET) != 0))
2293         add_new_state (vfr->PC, vfr->current_state);
2294
2295       /* Set this before handling exceptions so that debug output is
2296          sane.  */
2297       vfr->start_PC = vfr->PC;
2298
2299       /* Update states for all active exception handlers.  Ordinarily
2300          there are not many exception handlers.  So we simply run
2301          through them all.  */
2302       for (i = 0; i < vfr->current_method->exc_count; ++i)
2303         {
2304           int hpc, start, end, htype;
2305           vfy_get_exception (vfr->exception, i, &hpc, &start, &end, &htype);
2306           if (vfr->PC >= start && vfr->PC < end)
2307             {
2308               type handler = make_type_from_class (vfy_throwable_type ());
2309               if (htype != 0)
2310                 handler = check_class_constant (htype);
2311               push_exception_jump (handler, hpc);
2312             }
2313         }
2314
2315
2316       debug_print_state (vfr->current_state, "   ", vfr->PC,
2317                          vfr->current_method->max_stack,
2318                          vfr->current_method->max_locals);
2319       opcode = (java_opcode) vfr->bytecode[vfr->PC++];
2320       switch (opcode)
2321         {
2322         case op_nop:
2323           break;
2324
2325         case op_aconst_null:
2326           push_type (null_type);
2327           break;
2328
2329         case op_iconst_m1:
2330         case op_iconst_0:
2331         case op_iconst_1:
2332         case op_iconst_2:
2333         case op_iconst_3:
2334         case op_iconst_4:
2335         case op_iconst_5:
2336           push_type (int_type);
2337           break;
2338
2339         case op_lconst_0:
2340         case op_lconst_1:
2341           push_type (long_type);
2342           break;
2343
2344         case op_fconst_0:
2345         case op_fconst_1:
2346         case op_fconst_2:
2347           push_type (float_type);
2348           break;
2349
2350         case op_dconst_0:
2351         case op_dconst_1:
2352           push_type (double_type);
2353           break;
2354
2355         case op_bipush:
2356           get_byte ();
2357           push_type (int_type);
2358           break;
2359
2360         case op_sipush:
2361           get_short ();
2362           push_type (int_type);
2363           break;
2364
2365         case op_ldc:
2366           push_type_t (check_constant (get_byte ()));
2367           break;
2368         case op_ldc_w:
2369           push_type_t (check_constant (get_ushort ()));
2370           break;
2371         case op_ldc2_w:
2372           push_type_t (check_wide_constant (get_ushort ()));
2373           break;
2374
2375         case op_iload:
2376           push_type_t (get_variable (get_byte (), int_type));
2377           break;
2378         case op_lload:
2379           push_type_t (get_variable (get_byte (), long_type));
2380           break;
2381         case op_fload:
2382           push_type_t (get_variable (get_byte (), float_type));
2383           break;
2384         case op_dload:
2385           push_type_t (get_variable (get_byte (), double_type));
2386           break;
2387         case op_aload:
2388           push_type_t (get_variable (get_byte (), reference_type));
2389           break;
2390
2391         case op_iload_0:
2392         case op_iload_1:
2393         case op_iload_2:
2394         case op_iload_3:
2395           push_type_t (get_variable (opcode - op_iload_0, int_type));
2396           break;
2397         case op_lload_0:
2398         case op_lload_1:
2399         case op_lload_2:
2400         case op_lload_3:
2401           push_type_t (get_variable (opcode - op_lload_0, long_type));
2402           break;
2403         case op_fload_0:
2404         case op_fload_1:
2405         case op_fload_2:
2406         case op_fload_3:
2407           push_type_t (get_variable (opcode - op_fload_0, float_type));
2408           break;
2409         case op_dload_0:
2410         case op_dload_1:
2411         case op_dload_2:
2412         case op_dload_3:
2413           push_type_t (get_variable (opcode - op_dload_0, double_type));
2414           break;
2415         case op_aload_0:
2416         case op_aload_1:
2417         case op_aload_2:
2418         case op_aload_3:
2419           push_type_t (get_variable (opcode - op_aload_0, reference_type));
2420           break;
2421         case op_iaload:
2422           pop_type (int_type);
2423           push_type_t (require_array_type (pop_init_ref (reference_type),
2424                                          int_type));
2425           break;
2426         case op_laload:
2427           pop_type (int_type);
2428           push_type_t (require_array_type (pop_init_ref (reference_type),
2429                                          long_type));
2430           break;
2431         case op_faload:
2432           pop_type (int_type);
2433           push_type_t (require_array_type (pop_init_ref (reference_type),
2434                                          float_type));
2435           break;
2436         case op_daload:
2437           pop_type (int_type);
2438           push_type_t (require_array_type (pop_init_ref (reference_type),
2439                                          double_type));
2440           break;
2441         case op_aaload:
2442           pop_type (int_type);
2443           push_type_t (require_array_type (pop_init_ref (reference_type),
2444                                          reference_type));
2445           break;
2446         case op_baload:
2447           pop_type (int_type);
2448           require_array_type (pop_init_ref (reference_type), byte_type);
2449           push_type (int_type);
2450           break;
2451         case op_caload:
2452           pop_type (int_type);
2453           require_array_type (pop_init_ref (reference_type), char_type);
2454           push_type (int_type);
2455           break;
2456         case op_saload:
2457           pop_type (int_type);
2458           require_array_type (pop_init_ref (reference_type), short_type);
2459           push_type (int_type);
2460           break;
2461         case op_istore:
2462           set_variable (get_byte (), pop_type (int_type));
2463           break;
2464         case op_lstore:
2465           set_variable (get_byte (), pop_type (long_type));
2466           break;
2467         case op_fstore:
2468           set_variable (get_byte (), pop_type (float_type));
2469           break;
2470         case op_dstore:
2471           set_variable (get_byte (), pop_type (double_type));
2472           break;
2473         case op_astore:
2474           set_variable (get_byte (), pop_ref_or_return ());
2475           break;
2476         case op_istore_0:
2477         case op_istore_1:
2478         case op_istore_2:
2479         case op_istore_3:
2480           set_variable (opcode - op_istore_0, pop_type (int_type));
2481           break;
2482         case op_lstore_0:
2483         case op_lstore_1:
2484         case op_lstore_2:
2485         case op_lstore_3:
2486           set_variable (opcode - op_lstore_0, pop_type (long_type));
2487           break;
2488         case op_fstore_0:
2489         case op_fstore_1:
2490         case op_fstore_2:
2491         case op_fstore_3:
2492           set_variable (opcode - op_fstore_0, pop_type (float_type));
2493           break;
2494         case op_dstore_0:
2495         case op_dstore_1:
2496         case op_dstore_2:
2497         case op_dstore_3:
2498           set_variable (opcode - op_dstore_0, pop_type (double_type));
2499           break;
2500         case op_astore_0:
2501         case op_astore_1:
2502         case op_astore_2:
2503         case op_astore_3:
2504           set_variable (opcode - op_astore_0, pop_ref_or_return ());
2505           break;
2506         case op_iastore:
2507           pop_type (int_type);
2508           pop_type (int_type);
2509           require_array_type (pop_init_ref (reference_type), int_type);
2510           break;
2511         case op_lastore:
2512           pop_type (long_type);
2513           pop_type (int_type);
2514           require_array_type (pop_init_ref (reference_type), long_type);
2515           break;
2516         case op_fastore:
2517           pop_type (float_type);
2518           pop_type (int_type);
2519           require_array_type (pop_init_ref (reference_type), float_type);
2520           break;
2521         case op_dastore:
2522           pop_type (double_type);
2523           pop_type (int_type);
2524           require_array_type (pop_init_ref (reference_type), double_type);
2525           break;
2526         case op_aastore:
2527           pop_type (reference_type);
2528           pop_type (int_type);
2529           require_array_type (pop_init_ref (reference_type), reference_type);
2530           break;
2531         case op_bastore:
2532           pop_type (int_type);
2533           pop_type (int_type);
2534           require_array_type (pop_init_ref (reference_type), byte_type);
2535           break;
2536         case op_castore:
2537           pop_type (int_type);
2538           pop_type (int_type);
2539           require_array_type (pop_init_ref (reference_type), char_type);
2540           break;
2541         case op_sastore:
2542           pop_type (int_type);
2543           pop_type (int_type);
2544           require_array_type (pop_init_ref (reference_type), short_type);
2545           break;
2546         case op_pop:
2547           pop32 ();
2548           break;
2549         case op_pop2:
2550           {
2551             type t = pop_raw ();
2552             if (! type_iswide (&t))
2553               pop32 ();
2554           }
2555           break;
2556         case op_dup:
2557           {
2558             type t = pop32 ();
2559             push_type_t (t);
2560             push_type_t (t);
2561           }
2562           break;
2563         case op_dup_x1:
2564           {
2565             type t1 = pop32 ();
2566             type t2 = pop32 ();
2567             push_type_t (t1);
2568             push_type_t (t2);
2569             push_type_t (t1);
2570           }
2571           break;
2572         case op_dup_x2:
2573           {
2574             type t1 = pop32 ();
2575             type t2 = pop_raw ();
2576             if (! type_iswide (&t2))
2577               {
2578                 type t3 = pop32 ();
2579                 push_type_t (t1);
2580                 push_type_t (t3);
2581               }
2582             else
2583               push_type_t (t1);
2584             push_type_t (t2);
2585             push_type_t (t1);
2586           }
2587           break;
2588         case op_dup2:
2589           {
2590             type t = pop_raw ();
2591             if (! type_iswide (&t))
2592               {
2593                 type t2 = pop32 ();
2594                 push_type_t (t2);
2595                 push_type_t (t);
2596                 push_type_t (t2);
2597               }
2598             else
2599               push_type_t (t);
2600             push_type_t (t);
2601           }
2602           break;
2603         case op_dup2_x1:
2604           {
2605             type t1 = pop_raw ();
2606             type t2 = pop32 ();
2607             if (! type_iswide (&t1))
2608               {
2609                 type t3 = pop32 ();
2610                 push_type_t (t2);
2611                 push_type_t (t1);
2612                 push_type_t (t3);
2613               }
2614             else
2615               push_type_t (t1);
2616             push_type_t (t2);
2617             push_type_t (t1);
2618           }
2619           break;
2620         case op_dup2_x2:
2621           {
2622             type t1 = pop_raw ();
2623             if (type_iswide (&t1))
2624               {
2625                 type t2 = pop_raw ();
2626                 if (type_iswide (&t2))
2627                   {
2628                     push_type_t (t1);
2629                     push_type_t (t2);
2630                   }
2631                 else
2632                   {
2633                     type t3 = pop32 ();
2634                     push_type_t (t1);
2635                     push_type_t (t3);
2636                     push_type_t (t2);
2637                   }
2638                 push_type_t (t1);
2639               }
2640             else
2641               {
2642                 type t2 = pop32 ();
2643                 type t3 = pop_raw ();
2644                 if (type_iswide (&t3))
2645                   {
2646                     push_type_t (t2);
2647                     push_type_t (t1);
2648                   }
2649                 else
2650                   {
2651                     type t4 = pop32 ();
2652                     push_type_t (t2);
2653                     push_type_t (t1);
2654                     push_type_t (t4);
2655                   }
2656                 push_type_t (t3);
2657                 push_type_t (t2);
2658                 push_type_t (t1);
2659               }
2660           }
2661           break;
2662         case op_swap:
2663           {
2664             type t1 = pop32 ();
2665             type t2 = pop32 ();
2666             push_type_t (t1);
2667             push_type_t (t2);
2668           }
2669           break;
2670         case op_iadd:
2671         case op_isub:
2672         case op_imul:
2673         case op_idiv:
2674         case op_irem:
2675         case op_ishl:
2676         case op_ishr:
2677         case op_iushr:
2678         case op_iand:
2679         case op_ior:
2680         case op_ixor:
2681           pop_type (int_type);
2682           push_type_t (pop_type (int_type));
2683           break;
2684         case op_ladd:
2685         case op_lsub:
2686         case op_lmul:
2687         case op_ldiv:
2688         case op_lrem:
2689         case op_land:
2690         case op_lor:
2691         case op_lxor:
2692           pop_type (long_type);
2693           push_type_t (pop_type (long_type));
2694           break;
2695         case op_lshl:
2696         case op_lshr:
2697         case op_lushr:
2698           pop_type (int_type);
2699           push_type_t (pop_type (long_type));
2700           break;
2701         case op_fadd:
2702         case op_fsub:
2703         case op_fmul:
2704         case op_fdiv:
2705         case op_frem:
2706           pop_type (float_type);
2707           push_type_t (pop_type (float_type));
2708           break;
2709         case op_dadd:
2710         case op_dsub:
2711         case op_dmul:
2712         case op_ddiv:
2713         case op_drem:
2714           pop_type (double_type);
2715           push_type_t (pop_type (double_type));
2716           break;
2717         case op_ineg:
2718         case op_i2b:
2719         case op_i2c:
2720         case op_i2s:
2721           push_type_t (pop_type (int_type));
2722           break;
2723         case op_lneg:
2724           push_type_t (pop_type (long_type));
2725           break;
2726         case op_fneg:
2727           push_type_t (pop_type (float_type));
2728           break;
2729         case op_dneg:
2730           push_type_t (pop_type (double_type));
2731           break;
2732         case op_iinc:
2733           get_variable (get_byte (), int_type);
2734           get_byte ();
2735           break;
2736         case op_i2l:
2737           pop_type (int_type);
2738           push_type (long_type);
2739           break;
2740         case op_i2f:
2741           pop_type (int_type);
2742           push_type (float_type);
2743           break;
2744         case op_i2d:
2745           pop_type (int_type);
2746           push_type (double_type);
2747           break;
2748         case op_l2i:
2749           pop_type (long_type);
2750           push_type (int_type);
2751           break;
2752         case op_l2f:
2753           pop_type (long_type);
2754           push_type (float_type);
2755           break;
2756         case op_l2d:
2757           pop_type (long_type);
2758           push_type (double_type);
2759           break;
2760         case op_f2i:
2761           pop_type (float_type);
2762           push_type (int_type);
2763           break;
2764         case op_f2l:
2765           pop_type (float_type);
2766           push_type (long_type);
2767           break;
2768         case op_f2d:
2769           pop_type (float_type);
2770           push_type (double_type);
2771           break;
2772         case op_d2i:
2773           pop_type (double_type);
2774           push_type (int_type);
2775           break;
2776         case op_d2l:
2777           pop_type (double_type);
2778           push_type (long_type);
2779           break;
2780         case op_d2f:
2781           pop_type (double_type);
2782           push_type (float_type);
2783           break;
2784         case op_lcmp:
2785           pop_type (long_type);
2786           pop_type (long_type);
2787           push_type (int_type);
2788           break;
2789         case op_fcmpl:
2790         case op_fcmpg:
2791           pop_type (float_type);
2792           pop_type (float_type);
2793           push_type (int_type);
2794           break;
2795         case op_dcmpl:
2796         case op_dcmpg:
2797           pop_type (double_type);
2798           pop_type (double_type);
2799           push_type (int_type);
2800           break;
2801         case op_ifeq:
2802         case op_ifne:
2803         case op_iflt:
2804         case op_ifge:
2805         case op_ifgt:
2806         case op_ifle:
2807           pop_type (int_type);
2808           push_jump (get_short ());
2809           break;
2810         case op_if_icmpeq:
2811         case op_if_icmpne:
2812         case op_if_icmplt:
2813         case op_if_icmpge:
2814         case op_if_icmpgt:
2815         case op_if_icmple:
2816           pop_type (int_type);
2817           pop_type (int_type);
2818           push_jump (get_short ());
2819           break;
2820         case op_if_acmpeq:
2821         case op_if_acmpne:
2822           pop_type (reference_type);
2823           pop_type (reference_type);
2824           push_jump (get_short ());
2825           break;
2826         case op_goto:
2827           push_jump (get_short ());
2828           invalidate_pc ();
2829           break;
2830         case op_jsr:
2831           handle_jsr_insn (get_short ());
2832           break;
2833         case op_ret:
2834           handle_ret_insn (get_byte ());
2835           break;
2836         case op_tableswitch:
2837           {
2838             int i;
2839             jint low, high;
2840             pop_type (int_type);
2841             skip_padding ();
2842             push_jump (get_int ());
2843             low = get_int ();
2844             high = get_int ();
2845             /* Already checked LOW -vs- HIGH.  */
2846             for (i = low; i <= high; ++i)
2847               push_jump (get_int ());
2848             invalidate_pc ();
2849           }
2850           break;
2851
2852         case op_lookupswitch:
2853           {
2854             int i;
2855             jint npairs, lastkey;
2856
2857             pop_type (int_type);
2858             skip_padding ();
2859             push_jump (get_int ());
2860             npairs = get_int ();
2861             /* Already checked NPAIRS >= 0.  */
2862             lastkey = 0;
2863             for (i = 0; i < npairs; ++i)
2864               {
2865                 jint key = get_int ();
2866                 if (i > 0 && key <= lastkey)
2867                   verify_fail_pc ("lookupswitch pairs unsorted", vfr->start_PC);
2868                 lastkey = key;
2869                 push_jump (get_int ());
2870               }
2871             invalidate_pc ();
2872           }
2873           break;
2874         case op_ireturn:
2875           check_return_type (pop_type (int_type));
2876           invalidate_pc ();
2877           break;
2878         case op_lreturn:
2879           check_return_type (pop_type (long_type));
2880           invalidate_pc ();
2881           break;
2882         case op_freturn:
2883           check_return_type (pop_type (float_type));
2884           invalidate_pc ();
2885           break;
2886         case op_dreturn:
2887           check_return_type (pop_type (double_type));
2888           invalidate_pc ();
2889           break;
2890         case op_areturn:
2891           check_return_type (pop_init_ref (reference_type));
2892           invalidate_pc ();
2893           break;
2894         case op_return:
2895           /* We only need to check this when the return type is void,
2896              because all instance initializers return void.  We also
2897              need to special-case Object constructors, as they can't
2898              call a superclass <init>.  */
2899           if (this_is_init && vfr->current_class != vfy_object_type ())
2900             state_check_this_initialized (vfr->current_state);
2901           check_return_type (make_type (void_type));
2902           invalidate_pc ();
2903           break;
2904         case op_getstatic:
2905           push_type_t (check_field_constant (get_ushort (), NULL, false));
2906           break;
2907         case op_putstatic:
2908           pop_type_t (check_field_constant (get_ushort (), NULL, false));
2909           break;
2910         case op_getfield:
2911           {
2912             type klass;
2913             type field = check_field_constant (get_ushort (), &klass, false);
2914             pop_type_t (klass);
2915             push_type_t (field);
2916           }
2917           break;
2918         case op_putfield:
2919           {
2920             type klass;
2921             type field = check_field_constant (get_ushort (), &klass, true);
2922             pop_type_t (field);
2923             pop_type_t (klass);
2924           }
2925           break;
2926
2927         case op_invokevirtual:
2928         case op_invokespecial:
2929         case op_invokestatic:
2930         case op_invokeinterface:
2931           {
2932             vfy_string method_name, method_signature;
2933             const char *namec;
2934             int i, arg_count;
2935             type rt;
2936             bool is_init = false;
2937
2938             type class_type
2939               = check_method_constant (get_ushort (),
2940                                        opcode == op_invokeinterface,
2941                                        &method_name,
2942                                        &method_signature);
2943             /* NARGS is only used when we're processing
2944                invokeinterface.  It is simplest for us to compute it
2945                here and then verify it later.  */
2946             int nargs = 0;
2947             if (opcode == op_invokeinterface)
2948               {
2949                 nargs = get_byte ();
2950                 if (get_byte () != 0)
2951                   verify_fail ("invokeinterface dummy byte is wrong");
2952               }
2953
2954             namec = vfy_string_bytes (method_name);
2955
2956             if (vfy_strings_equal (method_name, vfy_init_name()))
2957               {
2958                 is_init = true;
2959                 if (opcode != op_invokespecial)
2960                   verify_fail ("can't invoke <init>");
2961               }
2962             else if (namec[0] == '<')
2963               verify_fail ("can't invoke method starting with `<'");
2964
2965             arg_count = vfy_count_arguments (method_signature);
2966             {
2967               /* Pop arguments and check types.  */
2968               type *arg_types = (type *) vfy_alloc (arg_count * sizeof (type));
2969
2970               compute_argument_types (method_signature, arg_types);
2971               for (i = arg_count - 1; i >= 0; --i)
2972                 {
2973                   /* This is only used for verifying the byte for
2974                      invokeinterface.  */
2975                   nargs -= type_depth (&arg_types[i]);
2976                   pop_init_ref_t (arg_types[i]);
2977                 }
2978
2979               vfy_free (arg_types);
2980             }
2981
2982             if (opcode == op_invokeinterface
2983                 && nargs != 1)
2984               verify_fail ("wrong argument count for invokeinterface");
2985
2986             if (opcode != op_invokestatic)
2987               {
2988                 type raw;
2989                 type t = class_type;
2990                 if (is_init)
2991                   {
2992                     /* In this case the PC doesn't matter.  */
2993                     type_set_uninitialized (&t, UNINIT);
2994                     /* FIXME: check to make sure that the <init>
2995                        call is to the right class.
2996                        It must either be super or an exact class
2997                        match.  */
2998                   }
2999                 raw = pop_raw ();
3000                 if (! types_compatible (&t, &raw))
3001                   verify_fail ("incompatible type on stack");
3002
3003                 if (is_init)
3004                   state_set_initialized (vfr->current_state,
3005                     type_get_pc (&raw), vfr->current_method->max_locals);
3006               }
3007
3008             rt = compute_return_type (method_signature);
3009             if (! type_isvoid (&rt))
3010               push_type_t (rt);
3011           }
3012           break;
3013
3014         case op_new:
3015           {
3016             type t = check_class_constant (get_ushort ());
3017             if (type_isarray (&t) || type_isinterface (&t)
3018                 || type_isabstract (&t))
3019               verify_fail ("type is array, interface, or abstract");
3020             type_set_uninitialized (&t, vfr->start_PC);
3021             push_type_t (t);
3022           }
3023           break;
3024
3025         case op_newarray:
3026           {
3027             int atype = get_byte ();
3028             vfy_jclass k;
3029             type t;
3030             /* We intentionally have chosen constants to make this
3031                valid.  */
3032             if (atype < boolean_type || atype > long_type)
3033               verify_fail_pc ("type not primitive", vfr->start_PC);
3034             pop_type (int_type);
3035             k = construct_primitive_array_type ((type_val) atype);
3036             init_type_from_class (&t, k);
3037             push_type_t (t);
3038           }
3039           break;
3040         case op_anewarray:
3041           {
3042             type t;
3043             pop_type (int_type);
3044             t = check_class_constant (get_ushort ());
3045             push_type_t (type_to_array (&t));
3046           }
3047           break;
3048         case op_arraylength:
3049           {
3050             type t = pop_init_ref (reference_type);
3051             if (! type_isarray (&t) && ! type_isnull (&t))
3052               verify_fail ("array type expected");
3053             push_type (int_type);
3054           }
3055           break;
3056         case op_athrow:
3057           pop_type_t (make_type_from_class (vfy_throwable_type ()));
3058           invalidate_pc ();
3059           break;
3060         case op_checkcast:
3061           pop_init_ref (reference_type);
3062           push_type_t (check_class_constant (get_ushort ()));
3063           break;
3064         case op_instanceof:
3065           pop_init_ref (reference_type);
3066           check_class_constant (get_ushort ());
3067           push_type (int_type);
3068           break;
3069         case op_monitorenter:
3070           pop_init_ref (reference_type);
3071           break;
3072         case op_monitorexit:
3073           pop_init_ref (reference_type);
3074           break;
3075         case op_wide:
3076           {
3077             switch (get_byte ())
3078               {
3079               case op_iload:
3080                 push_type_t (get_variable (get_ushort (), int_type));
3081                 break;
3082               case op_lload:
3083                 push_type_t (get_variable (get_ushort (), long_type));
3084                 break;
3085               case op_fload:
3086                 push_type_t (get_variable (get_ushort (), float_type));
3087                 break;
3088               case op_dload:
3089                 push_type_t (get_variable (get_ushort (), double_type));
3090                 break;
3091               case op_aload:
3092                 push_type_t (get_variable (get_ushort (), reference_type));
3093                 break;
3094               case op_istore:
3095                 set_variable (get_ushort (), pop_type (int_type));
3096                 break;
3097               case op_lstore:
3098                 set_variable (get_ushort (), pop_type (long_type));
3099                 break;
3100               case op_fstore:
3101                 set_variable (get_ushort (), pop_type (float_type));
3102                 break;
3103               case op_dstore:
3104                 set_variable (get_ushort (), pop_type (double_type));
3105                 break;
3106               case op_astore:
3107                 set_variable (get_ushort (), pop_init_ref (reference_type));
3108                 break;
3109               case op_ret:
3110                 handle_ret_insn (get_short ());
3111                 break;
3112               case op_iinc:
3113                 get_variable (get_ushort (), int_type);
3114                 get_short ();
3115                 break;
3116               default:
3117                 verify_fail_pc ("unrecognized wide instruction", vfr->start_PC);
3118               }
3119           }
3120           break;
3121         case op_multianewarray:
3122           {
3123             int i;
3124             type atype = check_class_constant (get_ushort ());
3125             int dim = get_byte ();
3126             if (dim < 1)
3127               verify_fail_pc ("too few dimensions to multianewarray", vfr->start_PC);
3128             type_verify_dimensions (&atype, dim);
3129             for (i = 0; i < dim; ++i)
3130               pop_type (int_type);
3131             push_type_t (atype);
3132           }
3133           break;
3134         case op_ifnull:
3135         case op_ifnonnull:
3136           pop_type (reference_type);
3137           push_jump (get_short ());
3138           break;
3139         case op_goto_w:
3140           push_jump (get_int ());
3141           invalidate_pc ();
3142           break;
3143         case op_jsr_w:
3144           handle_jsr_insn (get_int ());
3145           break;
3146
3147         default:
3148           /* Unrecognized opcode.  */
3149           verify_fail_pc ("unrecognized instruction in verify_instructions_0",
3150                        vfr->start_PC);
3151         }
3152     }
3153 }
3154
3155 /* This turns a `type' into something suitable for use by the type map
3156    in the other parts of the compiler.  In particular, reference types
3157    are mapped to Object, primitive types are unchanged, and other
3158    types are mapped using special functions declared in verify.h.  */
3159 static vfy_jclass
3160 collapse_type (type *t)
3161 {
3162   switch (t->key)
3163     {
3164     case void_type:
3165     case boolean_type:
3166     case char_type:
3167     case float_type:
3168     case double_type:
3169     case byte_type:
3170     case short_type:
3171     case int_type:
3172     case long_type:
3173       return vfy_get_primitive_type (t->key);
3174
3175     case unsuitable_type:
3176     case continuation_type:
3177       return vfy_unsuitable_type ();
3178
3179     case return_address_type:
3180       return vfy_return_address_type ();
3181
3182     case null_type:
3183       return vfy_null_type ();
3184
3185     case reference_type:
3186     case uninitialized_reference_type:
3187       return vfy_object_type ();
3188     }
3189
3190   gcc_unreachable ();
3191 }
3192
3193 static void
3194 verify_instructions (void)
3195 {
3196   int i;
3197
3198   branch_prepass ();
3199   verify_instructions_0 ();
3200
3201   /* Now tell the rest of the compiler about the types we've found.  */
3202   for (i = 0; i < vfr->current_method->code_length; ++i)
3203     {
3204       int j, slot;
3205       struct state *curr;
3206
3207       if ((vfr->flags[i] & FLAG_INSN_SEEN) != 0)
3208         vfy_note_instruction_seen (i);
3209
3210       if (! vfr->states[i])
3211         continue;
3212
3213       curr = vfr->states[i]->val;
3214       vfy_note_stack_depth (vfr->current_method, i, curr->stackdepth);
3215
3216       /* Tell the compiler about each local variable.  */
3217       for (j = 0; j < vfr->current_method->max_locals; ++j)
3218         vfy_note_local_type (vfr->current_method, i, j,
3219                              collapse_type (&curr->locals[j]));
3220       /* Tell the compiler about each stack slot.  */
3221       for (slot = j = 0; j < curr->stacktop; ++j, ++slot)
3222         {
3223           vfy_note_stack_type (vfr->current_method, i, slot,
3224                                collapse_type (&curr->stack[j]));
3225           if (type_iswide (&curr->stack[j]))
3226             {
3227               ++slot;
3228               vfy_note_stack_type (vfr->current_method, i, slot,
3229                                    vfy_unsuitable_type ());
3230             }
3231         }
3232       gcc_assert (slot == curr->stackdepth);
3233     }
3234 }
3235
3236 static void
3237 make_verifier_context (vfy_method *m)
3238 {
3239   vfr = (verifier_context *) vfy_alloc (sizeof (struct verifier_context));
3240
3241   vfr->current_method = m;
3242   vfr->bytecode = vfy_get_bytecode (m);
3243   vfr->exception = vfy_get_exceptions (m);
3244   vfr->current_class = m->defining_class;
3245
3246   vfr->states = NULL;
3247   vfr->flags = NULL;
3248   vfr->utf8_list = NULL;
3249   vfr->isect_list = NULL;
3250 }
3251
3252 static void
3253 free_verifier_context (void)
3254 {
3255   vfy_string_list *utf8_list;
3256   ref_intersection *isect_list;
3257
3258   if (vfr->flags)
3259     vfy_free (vfr->flags);
3260
3261   utf8_list = vfr->utf8_list;
3262   while (utf8_list != NULL)
3263     {
3264       vfy_string_list *n = utf8_list->next;
3265       vfy_free (utf8_list);
3266       utf8_list = n;
3267     }
3268
3269   isect_list = vfr->isect_list;
3270   while (isect_list != NULL)
3271     {
3272       ref_intersection *next = isect_list->alloc_next;
3273       vfy_free (isect_list);
3274       isect_list = next;
3275     }
3276
3277   if (vfr->states != NULL)
3278     {
3279       int i;
3280       for (i = 0; i < vfr->current_method->code_length; ++i)
3281         {
3282           state_list *iter = vfr->states[i];
3283           while (iter != NULL)
3284             {
3285               state_list *next = iter->next;
3286               free_state (iter->val);
3287               vfy_free (iter->val);
3288               vfy_free (iter);
3289               iter = next;
3290             }
3291         }
3292       vfy_free (vfr->states);
3293     }
3294
3295   vfy_free (vfr);
3296 }
3297
3298 int
3299 verify_method (vfy_method *meth)
3300 {
3301   debug_print ("verify_method (%s) %i\n", vfy_string_bytes (meth->name),
3302                meth->code_length);
3303
3304   if (vfr != NULL)
3305     verify_fail ("verifier re-entered");
3306
3307   make_verifier_context (meth);
3308   verify_instructions ();
3309   free_verifier_context ();
3310   vfr = NULL;
3311
3312   return 1;
3313 }