libjava/verify.cc

   1 // defineclass.cc - defining a class from .class format.
   2
   3 /* Copyright (C) 2001  Free Software Foundation
   4
   5    This file is part of libgcj.
   6
   7 This software is copyrighted work licensed under the terms of the
   8 Libgcj License.  Please consult the file "LIBGCJ_LICENSE" for
   9 details.  */
  10
  11 // Writte by Tom Tromey <tromey@redhat.com>
  12
  13 #include <config.h>
  14
  15 #include <jvm.h>
  16 #include <gcj/cni.h>
  17 #include <java-insns.h>
  18 #include <java-interp.h>
  19
  20 #ifdef INTERPRETER
  21
  22 #include <java/lang/Class.h>
  23 #include <java/lang/VerifyError.h>
  24 #include <java/lang/Throwable.h>
  25 #include <java/lang/reflect/Modifier.h>
  26
  27
  28 // TO DO
  29 // * read more about when classes must be loaded
  30 // * there are bugs with boolean arrays?
  31 // * class loader madness
  32 // * Lots and lots of debugging and testing
  33 // * type representation is still ugly.  look for the big switches
  34 // * at least one GC problem :-(
  35
  36
  37 // This is global because __attribute__ doesn't seem to work on static
  38 // methods.
  39 static void verify_fail (char *s) __attribute__ ((__noreturn__));
  40
  41 class _Jv_BytecodeVerifier
  42 {
  43 private:
  44
  45   static const int FLAG_INSN_START = 1;
  46   static const int FLAG_BRANCH_TARGET = 2;
  47   static const int FLAG_JSR_TARGET = 4;
  48
  49   struct state;
  50   struct type;
  51   struct subr_info;
  52
  53   // The current PC.
  54   int PC;
  55   // The PC corresponding to the start of the current instruction.
  56   int start_PC;
  57
  58   // The current state of the stack, locals, etc.
  59   state *current_state;
  60
  61   // We store the state at branch targets, for merging.  This holds
  62   // such states.
  63   state **states;
  64
  65   // We keep a linked list of all the PCs which we must reverify.
  66   // The link is done using the PC values.  This is the head of the
  67   // list.
  68   int next_verify_pc;
  69
  70   // We keep some flags for each instruction.  The values are the
  71   // FLAG_* constants defined above.
  72   char *flags;
  73
  74   // We need to keep track of which instructions can call a given
  75   // subroutine.  FIXME: this is inefficient.  We keep a linked list
  76   // of all calling `jsr's at at each jsr target.
  77   subr_info **jsr_ptrs;
  78
  79   // The current top of the stack, in terms of slots.
  80   int stacktop;
  81   // The current depth of the stack.  This will be larger than
  82   // STACKTOP when wide types are on the stack.
  83   int stackdepth;
  84
  85   // The bytecode itself.
  86   unsigned char *bytecode;
  87   // The exceptions.
  88   _Jv_InterpException *exception;
  89
  90   // Defining class.
  91   jclass current_class;
  92   // This method.
  93   _Jv_InterpMethod *current_method;
  94
  95   // This enum holds a list of tags for all the different types we
  96   // need to handle.  Reference types are treated specially by the
  97   // type class.
  98   enum type_val
  99   {
 100     void_type,
 101
 102     // The values for primitive types are chosen to correspond to values
 103     // specified to newarray.
 104     boolean_type = 4,
 105     char_type = 5,
 106     float_type = 6,
 107     double_type = 7,
 108     byte_type = 8,
 109     short_type = 9,
 110     int_type = 10,
 111     long_type = 11,
 112
 113     // Used when overwriting second word of a double or long in the
 114     // local variables.  Also used after merging local variable states
 115     // to indicate an unusable value.
 116     unsuitable_type,
 117     return_address_type,
 118     continuation_type,
 119
 120     // Everything after `reference_type' must be a reference type.
 121     reference_type,
 122     null_type,
 123     unresolved_reference_type,
 124     uninitialized_reference_type,
 125     uninitialized_unresolved_reference_type
 126   };
 127
 128   // Return the type_val corresponding to a primitive signature
 129   // character.  For instance `I' returns `int.class'.
 130   static type_val get_type_val_for_signature (jchar sig)
 131   {
 132     type_val rt;
 133     switch (sig)
 134       {
 135       case 'Z':
 136         rt = boolean_type;
 137         break;
 138       case 'C':
 139         rt = char_type;
 140         break;
 141       case 'S':
 142         rt = short_type;
 143         break;
 144       case 'I':
 145         rt = int_type;
 146         break;
 147       case 'J':
 148         rt = long_type;
 149         break;
 150       case 'F':
 151         rt = float_type;
 152         break;
 153       case 'D':
 154         rt = double_type;
 155         break;
 156       case 'V':
 157         rt = void_type;
 158         break;
 159       default:
 160         verify_fail ("invalid signature");
 161       }
 162     return rt;
 163   }
 164
 165   // Return the type_val corresponding to a primitive class.
 166   static type_val get_type_val_for_signature (jclass k)
 167   {
 168     return get_type_val_for_signature ((jchar) k->method_count);
 169   }
 170
 171   // This is used to keep track of which `jsr's correspond to a given
 172   // jsr target.
 173   struct subr_info
 174   {
 175     // PC of the instruction just after the jsr.
 176     int pc;
 177     // Link.
 178     subr_info *next;
 179   };
 180
 181   // The `type' class is used to represent a single type in the
 182   // verifier.
 183   struct type
 184   {
 185     // The type.
 186     type_val key;
 187     // Some associated data.
 188     union
 189     {
 190       // For a resolved reference type, this is a pointer to the class.
 191       jclass klass;
 192       // For other reference types, this it the name of the class.
 193       _Jv_Utf8Const *name;
 194     } data;
 195     // This is used when constructing a new object.  It is the PC of the
 196     // `new' instruction which created the object.  We use the special
 197     // value -2 to mean that this is uninitialized, and the special
 198     // value -1 for the case where the current method is itself the
 199     // <init> method.
 200     int pc;
 201
 202     static const int UNINIT = -2;
 203     static const int SELF = -1;
 204
 205     // Basic constructor.
 206     type ()
 207     {
 208       key = unsuitable_type;
 209       data.klass = NULL;
 210       pc = UNINIT;
 211     }
 212
 213     // Make a new instance given the type tag.  We assume a generic
 214     // `reference_type' means Object.
 215     type (type_val k)
 216     {
 217       key = k;
 218       data.klass = NULL;
 219       if (key == reference_type)
 220         data.klass = &java::lang::Object::class$;
 221       pc = UNINIT;
 222     }
 223
 224     // Make a new instance given a class.
 225     type (jclass klass)
 226     {
 227       key = reference_type;
 228       data.klass = klass;
 229       pc = UNINIT;
 230     }
 231
 232     // Make a new instance given the name of a class.
 233     type (_Jv_Utf8Const *n)
 234     {
 235       key = unresolved_reference_type;
 236       data.name = n;
 237       pc = UNINIT;
 238     }
 239
 240     // Copy constructor.
 241     type (const type &t)
 242     {
 243       key = t.key;
 244       data = t.data;
 245       pc = t.pc;
 246     }
 247
 248     // These operators are required because libgcj can't link in
 249     // -lstdc++.
 250     void *operator new[] (size_t bytes)
 251     {
 252       return _Jv_Malloc (bytes);
 253     }
 254
 255     void operator delete[] (void *mem)
 256     {
 257       _Jv_Free (mem);
 258     }
 259
 260     type& operator= (type_val k)
 261     {
 262       key = k;
 263       data.klass = NULL;
 264       pc = UNINIT;
 265       return *this;
 266     }
 267
 268     type& operator= (const type& t)
 269     {
 270       key = t.key;
 271       data = t.data;
 272       pc = t.pc;
 273       return *this;
 274     }
 275
 276     // Promote a numeric type.
 277     void promote ()
 278     {
 279       if (key == boolean_type || key == char_type
 280           || key == byte_type || key == short_type)
 281         key = int_type;
 282     }
 283
 284     // If *THIS is an unresolved reference type, resolve it.
 285     void resolve ()
 286     {
 287       if (key != unresolved_reference_type
 288           && key != uninitialized_unresolved_reference_type)
 289         return;
 290
 291       // FIXME: class loader
 292       using namespace java::lang;
 293       // We might see either kind of name.  Sigh.
 294       if (data.name->data[0] == 'L'
 295           && data.name->data[data.name->length - 1] == ';')
 296         data.klass = _Jv_FindClassFromSignature (data.name->data, NULL);
 297       else
 298         data.klass = Class::forName (_Jv_NewStringUtf8Const (data.name),
 299                                      false, NULL);
 300       key = (key == unresolved_reference_type
 301              ? reference_type
 302              : uninitialized_reference_type);
 303     }
 304
 305     // Mark this type as the uninitialized result of `new'.
 306     void set_uninitialized (int pc)
 307     {
 308       if (key != reference_type && key != unresolved_reference_type)
 309         verify_fail ("internal error in type::uninitialized");
 310       key = (key == reference_type
 311              ? uninitialized_reference_type
 312              : uninitialized_unresolved_reference_type);
 313       pc = pc;
 314     }
 315
 316     // Mark this type as now initialized.
 317     void set_initialized (int npc)
 318     {
 319       if (pc == npc)
 320         {
 321           key = (key == uninitialized_reference_type
 322                  ? reference_type
 323                  : unresolved_reference_type);
 324           pc = UNINIT;
 325         }
 326     }
 327
 328
 329     // Return true if an object of type K can be assigned to a variable
 330     // of type *THIS.  Handle various special cases too.  Might modify
 331     // *THIS or K.  Note however that this does not perform numeric
 332     // promotion.
 333     bool compatible (type &k)
 334     {
 335       // Any type is compatible with the unsuitable type.
 336       if (key == unsuitable_type)
 337         return true;
 338
 339       if (key < reference_type || k.key < reference_type)
 340         return key == k.key;
 341
 342       // The `null' type is convertible to any reference type.
 343       // FIXME: is this correct for THIS?
 344       if (key == null_type || k.key == null_type)
 345         return true;
 346
 347       // Any reference type is convertible to Object.  This is a special
 348       // case so we don't need to unnecessarily resolve a class.
 349       if (key == reference_type
 350           && data.klass == &java::lang::Object::class$)
 351         return true;
 352
 353       // An initialized type and an uninitialized type are not
 354       // compatible.
 355       if (isinitialized () != k.isinitialized ())
 356         return false;
 357
 358       // Two uninitialized objects are compatible if either:
 359       // * The PCs are identical, or
 360       // * One PC is UNINIT.
 361       if (! isinitialized ())
 362         {
 363           if (pc != k.pc && pc != UNINIT && k.pc != UNINIT)
 364             return false;
 365         }
 366
 367       // Two unresolved types are equal if their names are the same.
 368       if (! isresolved ()
 369           && ! k.isresolved ()
 370           && _Jv_equalUtf8Consts (data.name, k.data.name))
 371         return true;
 372
 373       // We must resolve both types and check assignability.
 374       resolve ();
 375       k.resolve ();
 376       // Use _Jv_IsAssignableFrom to avoid premature class
 377       // initialization.
 378       return _Jv_IsAssignableFrom (data.klass, k.data.klass);
 379     }
 380
 381     bool isvoid () const
 382     {
 383       return key == void_type;
 384     }
 385
 386     bool iswide () const
 387     {
 388       return key == long_type || key == double_type;
 389     }
 390
 391     // Return number of stack or local variable slots taken by this
 392     // type.
 393     int depth () const
 394     {
 395       return iswide () ? 2 : 1;
 396     }
 397
 398     bool isarray () const
 399     {
 400       // We treat null_type as not an array.  This is ok based on the
 401       // current uses of this method.
 402       if (key == reference_type)
 403         return data.klass->isArray ();
 404       else if (key == unresolved_reference_type)
 405         return data.name->data[0] == '[';
 406       return false;
 407     }
 408
 409     bool isinterface ()
 410     {
 411       resolve ();
 412       if (key != reference_type)
 413         return false;
 414       return data.klass->isInterface ();
 415     }
 416
 417     bool isabstract ()
 418     {
 419       resolve ();
 420       if (key != reference_type)
 421         return false;
 422       using namespace java::lang::reflect;
 423       return Modifier::isAbstract (data.klass->getModifiers ());
 424     }
 425
 426     // Return the element type of an array.
 427     type element_type ()
 428     {
 429       // FIXME: maybe should do string manipulation here.
 430       resolve ();
 431       if (key != reference_type)
 432         verify_fail ("programmer error in type::element_type()");
 433
 434       jclass k = data.klass->getComponentType ();
 435       if (k->isPrimitive ())
 436         return type (get_type_val_for_signature (k));
 437       return type (k);
 438     }
 439
 440     bool isreference () const
 441     {
 442       return key >= reference_type;
 443     }
 444
 445     int get_pc () const
 446     {
 447       return pc;
 448     }
 449
 450     bool isinitialized () const
 451     {
 452       return (key == reference_type
 453               || key == null_type
 454               || key == unresolved_reference_type);
 455     }
 456
 457     bool isresolved () const
 458     {
 459       return (key == reference_type
 460               || key == null_type
 461               || key == uninitialized_reference_type);
 462     }
 463
 464     void verify_dimensions (int ndims)
 465     {
 466       // The way this is written, we don't need to check isarray().
 467       if (key == reference_type)
 468         {
 469           jclass k = data.klass;
 470           while (k->isArray () && ndims > 0)
 471             {
 472               k = k->getComponentType ();
 473               --ndims;
 474             }
 475         }
 476       else
 477         {
 478           // We know KEY == unresolved_reference_type.
 479           char *p = data.name->data;
 480           while (*p++ == '[' && ndims-- > 0)
 481             ;
 482         }
 483
 484       if (ndims > 0)
 485         verify_fail ("array type has fewer dimensions than required");
 486     }
 487
 488     // Merge OLD_TYPE into this.  On error throw exception.
 489     bool merge (type& old_type, bool local_semantics = false)
 490     {
 491       bool changed = false;
 492       bool refo = old_type.isreference ();
 493       bool refn = isreference ();
 494       if (refo && refn)
 495         {
 496           if (old_type.key == null_type)
 497             ;
 498           else if (key == null_type)
 499             {
 500               *this = old_type;
 501               changed = true;
 502             }
 503           else if (isinitialized () != old_type.isinitialized ())
 504             verify_fail ("merging initialized and uninitialized types");
 505           else
 506             {
 507               if (! isinitialized ())
 508                 {
 509                   if (pc == UNINIT)
 510                     pc = old_type.pc;
 511                   else if (old_type.pc == UNINIT)
 512                     ;
 513                   else if (pc != old_type.pc)
 514                     verify_fail ("merging different uninitialized types");
 515                 }
 516
 517               if (! isresolved ()
 518                   && ! old_type.isresolved ()
 519                   && _Jv_equalUtf8Consts (data.name, old_type.data.name))
 520                 {
 521                   // Types are identical.
 522                 }
 523               else
 524                 {
 525                   resolve ();
 526                   old_type.resolve ();
 527
 528                   jclass k = data.klass;
 529                   jclass oldk = old_type.data.klass;
 530
 531                   int arraycount = 0;
 532                   while (k->isArray () && oldk->isArray ())
 533                     {
 534                       ++arraycount;
 535                       k = k->getComponentType ();
 536                       oldk = oldk->getComponentType ();
 537                     }
 538
 539                   // This loop will end when we hit Object.
 540                   while (true)
 541                     {
 542                       // Use _Jv_IsAssignableFrom to avoid premature
 543                       // class initialization.
 544                       if (_Jv_IsAssignableFrom (k, oldk))
 545                         break;
 546                       k = k->getSuperclass ();
 547                       changed = true;
 548                     }
 549
 550                   if (changed)
 551                     {
 552                       while (arraycount > 0)
 553                         {
 554                           // FIXME: Class loader.
 555                           k = _Jv_GetArrayClass (k, NULL);
 556                           --arraycount;
 557                         }
 558                       data.klass = k;
 559                     }
 560                 }
 561             }
 562         }
 563       else if (refo || refn || key != old_type.key)
 564         {
 565           if (local_semantics)
 566             {
 567               key = unsuitable_type;
 568               changed = true;
 569             }
 570           else
 571             verify_fail ("unmergeable type");
 572         }
 573       return changed;
 574     }
 575   };
 576
 577   // This class holds all the state information we need for a given
 578   // location.
 579   struct state
 580   {
 581     // Current top of stack.
 582     int stacktop;
 583     // Current stack depth.  This is like the top of stack but it
 584     // includes wide variable information.
 585     int stackdepth;
 586     // The stack.
 587     type *stack;
 588     // The local variables.
 589     type *locals;
 590     // This is used in subroutines to keep track of which local
 591     // variables have been accessed.
 592     bool *local_changed;
 593     // If not 0, then we are in a subroutine.  The value is the PC of
 594     // the subroutine's entry point.  We can use 0 as an exceptional
 595     // value because PC=0 can never be a subroutine.
 596     int subroutine;
 597     // This is used to keep a linked list of all the states which
 598     // require re-verification.  We use the PC to keep track.
 599     int next;
 600
 601     // INVALID marks a state which is not on the linked list of states
 602     // requiring reverification.
 603     static const int INVALID = -1;
 604     // NO_NEXT marks the state at the end of the reverification list.
 605     static const int NO_NEXT = -2;
 606
 607     state ()
 608     {
 609       stack = NULL;
 610       locals = NULL;
 611       local_changed = NULL;
 612     }
 613
 614     state (int max_stack, int max_locals)
 615     {
 616       stacktop = 0;
 617       stackdepth = 0;
 618       stack = new type[max_stack];
 619       for (int i = 0; i < max_stack; ++i)
 620         stack[i] = unsuitable_type;
 621       locals = new type[max_locals];
 622       local_changed = (bool *) _Jv_Malloc (sizeof (bool) * max_locals);
 623       for (int i = 0; i < max_locals; ++i)
 624         {
 625           locals[i] = unsuitable_type;
 626           local_changed[i] = false;
 627         }
 628       next = INVALID;
 629       subroutine = 0;
 630     }
 631
 632     state (const state *copy, int max_stack, int max_locals)
 633     {
 634       stack = new type[max_stack];
 635       locals = new type[max_locals];
 636       local_changed = (bool *) _Jv_Malloc (sizeof (bool) * max_locals);
 637       *this = *copy;
 638       next = INVALID;
 639     }
 640
 641     ~state ()
 642     {
 643       if (stack)
 644         delete[] stack;
 645       if (locals)
 646         delete[] locals;
 647       if (local_changed)
 648         _Jv_Free (local_changed);
 649     }
 650
 651     void *operator new[] (size_t bytes)
 652     {
 653       return _Jv_Malloc (bytes);
 654     }
 655
 656     void operator delete[] (void *mem)
 657     {
 658       _Jv_Free (mem);
 659     }
 660
 661     void *operator new (size_t bytes)
 662     {
 663       return _Jv_Malloc (bytes);
 664     }
 665
 666     void operator delete (void *mem)
 667     {
 668       _Jv_Free (mem);
 669     }
 670
 671     void copy (const state *copy, int max_stack, int max_locals)
 672     {
 673       stacktop = copy->stacktop;
 674       stackdepth = copy->stackdepth;
 675       subroutine = copy->subroutine;
 676       for (int i = 0; i < max_stack; ++i)
 677         stack[i] = copy->stack[i];
 678       for (int i = 0; i < max_locals; ++i)
 679         {
 680           locals[i] = copy->locals[i];
 681           local_changed[i] = copy->local_changed[i];
 682         }
 683       // Don't modify `next'.
 684     }
 685
 686     // Modify this state to reflect entry to an exception handler.
 687     void set_exception (type t, int max_stack)
 688     {
 689       stackdepth = 1;
 690       stacktop = 1;
 691       stack[0] = t;
 692       for (int i = stacktop; i < max_stack; ++i)
 693         stack[i] = unsuitable_type;
 694
 695       // FIXME: subroutine handling?
 696     }
 697
 698     // Merge STATE into this state.  Destructively modifies this state.
 699     // Returns true if the new state was in fact changed.  Will throw an
 700     // exception if the states are not mergeable.
 701     bool merge (state *state_old, bool ret_semantics,
 702                 int max_locals)
 703     {
 704       bool changed = false;
 705
 706       // Merge subroutine states.  *THIS and *STATE_OLD must be in the
 707       // same subroutine.  Also, recursive subroutine calls must be
 708       // avoided.
 709       if (subroutine == state_old->subroutine)
 710         {
 711           // Nothing.
 712         }
 713       else if (subroutine == 0)
 714         {
 715           subroutine = state_old->subroutine;
 716           changed = true;
 717         }
 718       else
 719         verify_fail ("subroutines merged");
 720
 721       // Merge stacks.
 722       if (state_old->stacktop != stacktop)
 723         verify_fail ("stack sizes differ");
 724       for (int i = 0; i < state_old->stacktop; ++i)
 725         {
 726           if (stack[i].merge (state_old->stack[i]))
 727             changed = true;
 728         }
 729
 730       // Merge local variables.
 731       for (int i = 0; i < max_locals; ++i)
 732         {
 733           if (! ret_semantics || local_changed[i])
 734             {
 735               if (locals[i].merge (state_old->locals[i], true))
 736                 {
 737                   changed = true;
 738                   note_variable (i);
 739                 }
 740             }
 741
 742           // If we're in a subroutine, we must compute the union of
 743           // all the changed local variables.
 744           if (state_old->local_changed[i])
 745             note_variable (i);
 746         }
 747
 748       return changed;
 749     }
 750
 751     // Throw an exception if there is an uninitialized object on the
 752     // stack or in a local variable.  EXCEPTION_SEMANTICS controls
 753     // whether we're using backwards-branch or exception-handing
 754     // semantics.
 755     void check_no_uninitialized_objects (int max_locals,
 756                                          bool exception_semantics = false)
 757     {
 758       if (! exception_semantics)
 759         {
 760           for (int i = 0; i < stacktop; ++i)
 761             if (stack[i].isreference () && ! stack[i].isinitialized ())
 762               verify_fail ("uninitialized object on stack");
 763         }
 764
 765       for (int i = 0; i < max_locals; ++i)
 766         if (locals[i].isreference () && ! locals[i].isinitialized ())
 767           verify_fail ("uninitialized object in local variable");
 768     }
 769
 770     // Note that a local variable was accessed or modified.
 771     void note_variable (int index)
 772     {
 773       if (subroutine > 0)
 774         local_changed[index] = true;
 775     }
 776
 777     // Mark each `new'd object we know of that was allocated at PC as
 778     // initialized.
 779     void set_initialized (int pc, int max_locals)
 780     {
 781       for (int i = 0; i < stacktop; ++i)
 782         stack[i].set_initialized (pc);
 783       for (int i = 0; i < max_locals; ++i)
 784         locals[i].set_initialized (pc);
 785     }
 786   };
 787
 788   type pop_raw ()
 789   {
 790     if (current_state->stacktop <= 0)
 791       verify_fail ("stack empty");
 792     type r = current_state->stack[--current_state->stacktop];
 793     current_state->stackdepth -= r.depth ();
 794     if (current_state->stackdepth < 0)
 795       verify_fail ("stack empty");
 796     return r;
 797   }
 798
 799   type pop32 ()
 800   {
 801     type r = pop_raw ();
 802     if (r.iswide ())
 803       verify_fail ("narrow pop of wide type");
 804     return r;
 805   }
 806
 807   type pop64 ()
 808   {
 809     type r = pop_raw ();
 810     if (! r.iswide ())
 811       verify_fail ("wide pop of narrow type");
 812     return r;
 813   }
 814
 815   type pop_type (type match)
 816   {
 817     type t = pop_raw ();
 818     if (! match.compatible (t))
 819       verify_fail ("incompatible type on stack");
 820     return t;
 821   }
 822
 823   void push_type (type t)
 824   {
 825     // If T is a numeric type like short, promote it to int.
 826     t.promote ();
 827
 828     int depth = t.depth ();
 829     if (current_state->stackdepth + depth > current_method->max_stack)
 830       verify_fail ("stack overflow");
 831     current_state->stack[current_state->stacktop++] = t;
 832     current_state->stackdepth += depth;
 833   }
 834
 835   void set_variable (int index, type t)
 836   {
 837     // If T is a numeric type like short, promote it to int.
 838     t.promote ();
 839
 840     int depth = t.depth ();
 841     if (index > current_method->max_locals - depth)
 842       verify_fail ("invalid local variable");
 843     current_state->locals[index] = t;
 844     current_state->note_variable (index);
 845
 846     if (depth == 2)
 847       {
 848         current_state->locals[index + 1] = continuation_type;
 849         current_state->note_variable (index + 1);
 850       }
 851     if (index > 0 && current_state->locals[index - 1].iswide ())
 852       {
 853         current_state->locals[index - 1] = unsuitable_type;
 854         // There's no need to call note_variable here.
 855       }
 856   }
 857
 858   type get_variable (int index, type t)
 859   {
 860     int depth = t.depth ();
 861     if (index > current_method->max_locals - depth)
 862       verify_fail ("invalid local variable");
 863     if (! t.compatible (current_state->locals[index]))
 864       verify_fail ("incompatible type in local variable");
 865     if (depth == 2)
 866       {
 867         type t (continuation_type);
 868         if (! current_state->locals[index + 1].compatible (t))
 869           verify_fail ("invalid local variable");
 870       }
 871     current_state->note_variable (index);
 872     return current_state->locals[index];
 873   }
 874
 875   // Make sure ARRAY is an array type and that its elements are
 876   // compatible with type ELEMENT.  Returns the actual element type.
 877   type require_array_type (type array, type element)
 878   {
 879     if (! array.isarray ())
 880       verify_fail ("array required");
 881
 882     type t = array.element_type ();
 883     if (! element.compatible (t))
 884       verify_fail ("incompatible array element type");
 885
 886     // Return T and not ELEMENT, because T might be specialized.
 887     return t;
 888   }
 889
 890   jint get_byte ()
 891   {
 892     if (PC >= current_method->code_length)
 893       verify_fail ("premature end of bytecode");
 894     return (jint) bytecode[PC++] & 0xff;
 895   }
 896
 897   jint get_ushort ()
 898   {
 899     jbyte b1 = get_byte ();
 900     jbyte b2 = get_byte ();
 901     return (jint) ((b1 << 8) | b2) & 0xffff;
 902   }
 903
 904   jint get_short ()
 905   {
 906     jbyte b1 = get_byte ();
 907     jbyte b2 = get_byte ();
 908     jshort s = (b1 << 8) | b2;
 909     return (jint) s;
 910   }
 911
 912   jint get_int ()
 913   {
 914     jbyte b1 = get_byte ();
 915     jbyte b2 = get_byte ();
 916     jbyte b3 = get_byte ();
 917     jbyte b4 = get_byte ();
 918     return (b1 << 24) | (b2 << 16) | (b3 << 8) | b4;
 919   }
 920
 921   int compute_jump (int offset)
 922   {
 923     int npc = start_PC + offset;
 924     if (npc < 0 || npc >= current_method->code_length)
 925       verify_fail ("branch out of range");
 926     return npc;
 927   }
 928
 929   // Merge the indicated state into a new state and schedule a new PC if
 930   // there is a change.  If RET_SEMANTICS is true, then we are merging
 931   // from a `ret' instruction into the instruction after a `jsr'.  This
 932   // is a special case with its own modified semantics.
 933   void push_jump_merge (int npc, state *nstate, bool ret_semantics = false)
 934   {
 935     bool changed = true;
 936     if (states[npc] == NULL)
 937       {
 938         // FIXME: what if we reach this code from a `ret'?
 939
 940         states[npc] = new state (nstate, current_method->max_stack,
 941                                  current_method->max_locals);
 942       }
 943     else
 944       changed = nstate->merge (states[npc], ret_semantics,
 945                                current_method->max_stack);
 946
 947     if (changed && states[npc]->next == state::INVALID)
 948       {
 949         // The merge changed the state, and the new PC isn't yet on our
 950         // list of PCs to re-verify.
 951         states[npc]->next = next_verify_pc;
 952         next_verify_pc = npc;
 953       }
 954   }
 955
 956   void push_jump (int offset)
 957   {
 958     int npc = compute_jump (offset);
 959     if (npc < PC)
 960       current_state->check_no_uninitialized_objects (current_method->max_stack);
 961     push_jump_merge (npc, current_state);
 962   }
 963
 964   void push_exception_jump (type t, int pc)
 965   {
 966     current_state->check_no_uninitialized_objects (current_method->max_stack,
 967                                                   true);
 968     state s (current_state, current_method->max_stack,
 969              current_method->max_locals);
 970     s.set_exception (t, current_method->max_stack);
 971     push_jump_merge (pc, &s);
 972   }
 973
 974   int pop_jump ()
 975   {
 976     int npc = next_verify_pc;
 977     if (npc != state::NO_NEXT)
 978       {
 979         next_verify_pc = states[npc]->next;
 980         states[npc]->next = state::INVALID;
 981       }
 982     return npc;
 983   }
 984
 985   void invalidate_pc ()
 986   {
 987     PC = state::NO_NEXT;
 988   }
 989
 990   void note_branch_target (int pc, bool is_jsr_target = false)
 991   {
 992     if (pc <= PC && ! (flags[pc] & FLAG_INSN_START))
 993       verify_fail ("branch not to instruction start");
 994     flags[pc] |= FLAG_BRANCH_TARGET;
 995     if (is_jsr_target)
 996       {
 997         // Record the jsr which called this instruction.
 998         subr_info *info = (subr_info *) _Jv_Malloc (sizeof (subr_info));
 999         info->pc = PC;
1000         info->next = jsr_ptrs[pc];
1001         jsr_ptrs[pc] = info;
1002         flags[pc] |= FLAG_JSR_TARGET;
1003       }
1004   }
1005
1006   void skip_padding ()
1007   {
1008     while ((PC % 4) > 0)
1009       if (get_byte () != 0)
1010         verify_fail ("found nonzero padding byte");
1011   }
1012
1013   // Return the subroutine to which the instruction at PC belongs.
1014   int get_subroutine (int pc)
1015   {
1016     if (states[pc] == NULL)
1017       return 0;
1018     return states[pc]->subroutine;
1019   }
1020
1021   // Do the work for a `ret' instruction.  INDEX is the index into the
1022   // local variables.
1023   void handle_ret_insn (int index)
1024   {
1025     get_variable (index, return_address_type);
1026
1027     int csub = current_state->subroutine;
1028     if (csub == 0)
1029       verify_fail ("no subroutine");
1030
1031     for (subr_info *subr = jsr_ptrs[csub]; subr != NULL; subr = subr->next)
1032       {
1033         // Temporarily modify the current state so it looks like we're
1034         // in the enclosing context.
1035         current_state->subroutine = get_subroutine (subr->pc);
1036         if (subr->pc < PC)
1037           current_state->check_no_uninitialized_objects (current_method->max_stack);
1038         push_jump_merge (subr->pc, current_state, true);
1039       }
1040
1041     current_state->subroutine = csub;
1042     invalidate_pc ();
1043   }
1044
1045   // We're in the subroutine SUB, calling a subroutine at DEST.  Make
1046   // sure this subroutine isn't already on the stack.
1047   void check_nonrecursive_call (int sub, int dest)
1048   {
1049     if (sub == 0)
1050       return;
1051     if (sub == dest)
1052       verify_fail ("recursive subroutine call");
1053     for (subr_info *info = jsr_ptrs[sub]; info != NULL; info = info->next)
1054       check_nonrecursive_call (get_subroutine (info->pc), dest);
1055   }
1056
1057   void handle_jsr_insn (int offset)
1058   {
1059     int npc = compute_jump (offset);
1060
1061     if (npc < PC)
1062       current_state->check_no_uninitialized_objects (current_method->max_stack);
1063     check_nonrecursive_call (current_state->subroutine, npc);
1064
1065     // Temporarily modify the current state so that it looks like we are
1066     // in the subroutine.
1067     push_type (return_address_type);
1068     int save = current_state->subroutine;
1069     current_state->subroutine = npc;
1070
1071     // Merge into the subroutine.
1072     push_jump_merge (npc, current_state);
1073
1074     // Undo our modifications.
1075     current_state->subroutine = save;
1076     pop_type (return_address_type);
1077   }
1078
1079   jclass construct_primitive_array_type (type_val prim)
1080   {
1081     jclass k = NULL;
1082     switch (prim)
1083       {
1084       case boolean_type:
1085         k = JvPrimClass (boolean);
1086         break;
1087       case char_type:
1088         k = JvPrimClass (char);
1089         break;
1090       case float_type:
1091         k = JvPrimClass (float);
1092         break;
1093       case double_type:
1094         k = JvPrimClass (double);
1095         break;
1096       case byte_type:
1097         k = JvPrimClass (byte);
1098         break;
1099       case short_type:
1100         k = JvPrimClass (short);
1101         break;
1102       case int_type:
1103         k = JvPrimClass (int);
1104         break;
1105       case long_type:
1106         k = JvPrimClass (long);
1107         break;
1108       default:
1109         verify_fail ("unknown type in construct_primitive_array_type");
1110       }
1111     k = _Jv_GetArrayClass (k, NULL);
1112     return k;
1113   }
1114
1115   // This pass computes the location of branch targets and also
1116   // instruction starts.
1117   void branch_prepass ()
1118   {
1119     flags = (char *) _Jv_Malloc (current_method->code_length);
1120     jsr_ptrs = (subr_info **) _Jv_Malloc (sizeof (subr_info *)
1121                                           * current_method->code_length);
1122
1123     for (int i = 0; i < current_method->code_length; ++i)
1124       {
1125         flags[i] = 0;
1126         jsr_ptrs[i] = NULL;
1127       }
1128
1129     bool last_was_jsr = false;
1130
1131     PC = 0;
1132     while (PC < current_method->code_length)
1133       {
1134         flags[PC] |= FLAG_INSN_START;
1135
1136         // If the previous instruction was a jsr, then the next
1137         // instruction is a branch target -- the branch being the
1138         // corresponding `ret'.
1139         if (last_was_jsr)
1140           note_branch_target (PC);
1141         last_was_jsr = false;
1142
1143         start_PC = PC;
1144         unsigned char opcode = bytecode[PC++];
1145         switch (opcode)
1146           {
1147           case op_nop:
1148           case op_aconst_null:
1149           case op_iconst_m1:
1150           case op_iconst_0:
1151           case op_iconst_1:
1152           case op_iconst_2:
1153           case op_iconst_3:
1154           case op_iconst_4:
1155           case op_iconst_5:
1156           case op_lconst_0:
1157           case op_lconst_1:
1158           case op_fconst_0:
1159           case op_fconst_1:
1160           case op_fconst_2:
1161           case op_dconst_0:
1162           case op_dconst_1:
1163           case op_iload_0:
1164           case op_iload_1:
1165           case op_iload_2:
1166           case op_iload_3:
1167           case op_lload_0:
1168           case op_lload_1:
1169           case op_lload_2:
1170           case op_lload_3:
1171           case op_fload_0:
1172           case op_fload_1:
1173           case op_fload_2:
1174           case op_fload_3:
1175           case op_dload_0:
1176           case op_dload_1:
1177           case op_dload_2:
1178           case op_dload_3:
1179           case op_aload_0:
1180           case op_aload_1:
1181           case op_aload_2:
1182           case op_aload_3:
1183           case op_iaload:
1184           case op_laload:
1185           case op_faload:
1186           case op_daload:
1187           case op_aaload:
1188           case op_baload:
1189           case op_caload:
1190           case op_saload:
1191           case op_istore_0:
1192           case op_istore_1:
1193           case op_istore_2:
1194           case op_istore_3:
1195           case op_lstore_0:
1196           case op_lstore_1:
1197           case op_lstore_2:
1198           case op_lstore_3:
1199           case op_fstore_0:
1200           case op_fstore_1:
1201           case op_fstore_2:
1202           case op_fstore_3:
1203           case op_dstore_0:
1204           case op_dstore_1:
1205           case op_dstore_2:
1206           case op_dstore_3:
1207           case op_astore_0:
1208           case op_astore_1:
1209           case op_astore_2:
1210           case op_astore_3:
1211           case op_iastore:
1212           case op_lastore:
1213           case op_fastore:
1214           case op_dastore:
1215           case op_aastore:
1216           case op_bastore:
1217           case op_castore:
1218           case op_sastore:
1219           case op_pop:
1220           case op_pop2:
1221           case op_dup:
1222           case op_dup_x1:
1223           case op_dup_x2:
1224           case op_dup2:
1225           case op_dup2_x1:
1226           case op_dup2_x2:
1227           case op_swap:
1228           case op_iadd:
1229           case op_isub:
1230           case op_imul:
1231           case op_idiv:
1232           case op_irem:
1233           case op_ishl:
1234           case op_ishr:
1235           case op_iushr:
1236           case op_iand:
1237           case op_ior:
1238           case op_ixor:
1239           case op_ladd:
1240           case op_lsub:
1241           case op_lmul:
1242           case op_ldiv:
1243           case op_lrem:
1244           case op_lshl:
1245           case op_lshr:
1246           case op_lushr:
1247           case op_land:
1248           case op_lor:
1249           case op_lxor:
1250           case op_fadd:
1251           case op_fsub:
1252           case op_fmul:
1253           case op_fdiv:
1254           case op_frem:
1255           case op_dadd:
1256           case op_dsub:
1257           case op_dmul:
1258           case op_ddiv:
1259           case op_drem:
1260           case op_ineg:
1261           case op_i2b:
1262           case op_i2c:
1263           case op_i2s:
1264           case op_lneg:
1265           case op_fneg:
1266           case op_dneg:
1267           case op_iinc:
1268           case op_i2l:
1269           case op_i2f:
1270           case op_i2d:
1271           case op_l2i:
1272           case op_l2f:
1273           case op_l2d:
1274           case op_f2i:
1275           case op_f2l:
1276           case op_f2d:
1277           case op_d2i:
1278           case op_d2l:
1279           case op_d2f:
1280           case op_lcmp:
1281           case op_fcmpl:
1282           case op_fcmpg:
1283           case op_dcmpl:
1284           case op_dcmpg:
1285           case op_monitorenter:
1286           case op_monitorexit:
1287           case op_ireturn:
1288           case op_lreturn:
1289           case op_freturn:
1290           case op_dreturn:
1291           case op_areturn:
1292           case op_return:
1293           case op_athrow:
1294             break;
1295
1296           case op_bipush:
1297           case op_sipush:
1298           case op_ldc:
1299           case op_iload:
1300           case op_lload:
1301           case op_fload:
1302           case op_dload:
1303           case op_aload:
1304           case op_istore:
1305           case op_lstore:
1306           case op_fstore:
1307           case op_dstore:
1308           case op_astore:
1309           case op_arraylength:
1310           case op_ret:
1311             get_byte ();
1312             break;
1313
1314           case op_ldc_w:
1315           case op_ldc2_w:
1316           case op_getstatic:
1317           case op_getfield:
1318           case op_putfield:
1319           case op_putstatic:
1320           case op_new:
1321           case op_newarray:
1322           case op_anewarray:
1323           case op_instanceof:
1324           case op_checkcast:
1325           case op_invokespecial:
1326           case op_invokestatic:
1327           case op_invokevirtual:
1328             get_short ();
1329             break;
1330
1331           case op_multianewarray:
1332             get_short ();
1333             get_byte ();
1334             break;
1335
1336           case op_jsr:
1337             last_was_jsr = true;
1338             // Fall through.
1339           case op_ifeq:
1340           case op_ifne:
1341           case op_iflt:
1342           case op_ifge:
1343           case op_ifgt:
1344           case op_ifle:
1345           case op_if_icmpeq:
1346           case op_if_icmpne:
1347           case op_if_icmplt:
1348           case op_if_icmpge:
1349           case op_if_icmpgt:
1350           case op_if_icmple:
1351           case op_if_acmpeq:
1352           case op_if_acmpne:
1353           case op_ifnull:
1354           case op_ifnonnull:
1355           case op_goto:
1356             note_branch_target (compute_jump (get_short ()), last_was_jsr);
1357             break;
1358
1359           case op_tableswitch:
1360             {
1361               skip_padding ();
1362               note_branch_target (compute_jump (get_int ()));
1363               jint low = get_int ();
1364               jint hi = get_int ();
1365               if (low > hi)
1366                 verify_fail ("invalid tableswitch");
1367               for (int i = low; i <= hi; ++i)
1368                 note_branch_target (compute_jump (get_int ()));
1369             }
1370             break;
1371
1372           case op_lookupswitch:
1373             {
1374               skip_padding ();
1375               note_branch_target (compute_jump (get_int ()));
1376               int npairs = get_int ();
1377               if (npairs < 0)
1378                 verify_fail ("too few pairs in lookupswitch");
1379               while (npairs-- > 0)
1380                 {
1381                   get_int ();
1382                   note_branch_target (compute_jump (get_int ()));
1383                 }
1384             }
1385             break;
1386
1387           case op_invokeinterface:
1388             get_short ();
1389             get_byte ();
1390             get_byte ();
1391             break;
1392
1393           case op_wide:
1394             {
1395               opcode = get_byte ();
1396               get_short ();
1397               if (opcode == (unsigned char) op_iinc)
1398                 get_short ();
1399             }
1400             break;
1401
1402           case op_jsr_w:
1403             last_was_jsr = true;
1404             // Fall through.
1405           case op_goto_w:
1406             note_branch_target (compute_jump (get_int ()), last_was_jsr);
1407             break;
1408
1409           default:
1410             verify_fail ("unrecognized instruction in branch_prepass");
1411           }
1412
1413         // See if any previous branch tried to branch to the middle of
1414         // this instruction.
1415         for (int pc = start_PC + 1; pc < PC; ++pc)
1416           {
1417             if ((flags[pc] & FLAG_BRANCH_TARGET))
1418               verify_fail ("branch not to instruction start");
1419           }
1420       }
1421
1422     // Verify exception handlers.
1423     for (int i = 0; i < current_method->exc_count; ++i)
1424       {
1425         if (! (flags[exception[i].handler_pc] & FLAG_INSN_START))
1426           verify_fail ("exception handler not at instruction start");
1427         if (exception[i].start_pc > exception[i].end_pc)
1428           verify_fail ("exception range inverted");
1429         if (! (flags[exception[i].start_pc] & FLAG_INSN_START)
1430             || ! (flags[exception[i].start_pc] & FLAG_INSN_START))
1431           verify_fail ("exception endpoint not at instruction start");
1432
1433         flags[exception[i].handler_pc] |= FLAG_BRANCH_TARGET;
1434       }
1435   }
1436
1437   void check_pool_index (int index)
1438   {
1439     if (index < 0 || index >= current_class->constants.size)
1440       verify_fail ("constant pool index out of range");
1441   }
1442
1443   type check_class_constant (int index)
1444   {
1445     check_pool_index (index);
1446     _Jv_Constants *pool = &current_class->constants;
1447     if (pool->tags[index] == JV_CONSTANT_ResolvedClass)
1448       return type (pool->data[index].clazz);
1449     else if (pool->tags[index] == JV_CONSTANT_Class)
1450       return type (pool->data[index].utf8);
1451     verify_fail ("expected class constant");
1452   }
1453
1454   type check_constant (int index)
1455   {
1456     check_pool_index (index);
1457     _Jv_Constants *pool = &current_class->constants;
1458     if (pool->tags[index] == JV_CONSTANT_ResolvedString
1459         || pool->tags[index] == JV_CONSTANT_String)
1460       return type (&java::lang::String::class$);
1461     else if (pool->tags[index] == JV_CONSTANT_Integer)
1462       return type (int_type);
1463     else if (pool->tags[index] == JV_CONSTANT_Float)
1464       return type (float_type);
1465     verify_fail ("String, int, or float constant expected");
1466   }
1467
1468   // Helper for both field and method.  These are laid out the same in
1469   // the constant pool.
1470   type handle_field_or_method (int index, int expected,
1471                                _Jv_Utf8Const **name,
1472                                _Jv_Utf8Const **fmtype)
1473   {
1474     check_pool_index (index);
1475     _Jv_Constants *pool = &current_class->constants;
1476     if (pool->tags[index] != expected)
1477       verify_fail ("didn't see expected constant");
1478     // Once we know we have a Fieldref or Methodref we assume that it
1479     // is correctly laid out in the constant pool.  I think the code
1480     // in defineclass.cc guarantees this.
1481     _Jv_ushort class_index, name_and_type_index;
1482     _Jv_loadIndexes (&pool->data[index],
1483                      class_index,
1484                      name_and_type_index);
1485     _Jv_ushort name_index, desc_index;
1486     _Jv_loadIndexes (&pool->data[name_and_type_index],
1487                      name_index, desc_index);
1488
1489     *name = pool->data[name_index].utf8;
1490     *fmtype = pool->data[desc_index].utf8;
1491
1492     return check_class_constant (class_index);
1493   }
1494
1495   // Return field's type, compute class' type if requested.
1496   type check_field_constant (int index, type *class_type = NULL)
1497   {
1498     _Jv_Utf8Const *name, *field_type;
1499     type ct = handle_field_or_method (index,
1500                                       JV_CONSTANT_Fieldref,
1501                                       &name, &field_type);
1502     if (class_type)
1503       *class_type = ct;
1504     return type (field_type);
1505   }
1506
1507   type check_method_constant (int index, bool is_interface,
1508                               _Jv_Utf8Const **method_name,
1509                               _Jv_Utf8Const **method_signature)
1510   {
1511     return handle_field_or_method (index,
1512                                    (is_interface
1513                                     ? JV_CONSTANT_InterfaceMethodref
1514                                     : JV_CONSTANT_Methodref),
1515                                    method_name, method_signature);
1516   }
1517
1518   type get_one_type (char *&p)
1519   {
1520     char *start = p;
1521
1522     int arraycount = 0;
1523     while (*p == '[')
1524       {
1525         ++arraycount;
1526         ++p;
1527       }
1528
1529     char v = *p++;
1530
1531     if (v == 'L')
1532       {
1533         while (*p != ';')
1534           ++p;
1535         ++p;
1536         // FIXME!  This will get collected!
1537         _Jv_Utf8Const *name = _Jv_makeUtf8Const (start, p - start);
1538         return type (name);
1539       }
1540
1541     // Casting to jchar here is ok since we are looking at an ASCII
1542     // character.
1543     type_val rt = get_type_val_for_signature (jchar (v));
1544
1545     if (arraycount == 0)
1546       return type (rt);
1547
1548     jclass k = construct_primitive_array_type (rt);
1549     while (--arraycount > 0)
1550       k = _Jv_GetArrayClass (k, NULL);
1551     return type (k);
1552   }
1553
1554   void compute_argument_types (_Jv_Utf8Const *signature,
1555                                type *types)
1556   {
1557     char *p = signature->data;
1558     // Skip `('.
1559     ++p;
1560
1561     int i = 0;
1562     while (*p != ')')
1563       types[i++] = get_one_type (p);
1564   }
1565
1566   type compute_return_type (_Jv_Utf8Const *signature)
1567   {
1568     char *p = signature->data;
1569     while (*p != ')')
1570       ++p;
1571     ++p;
1572     return get_one_type (p);
1573   }
1574
1575   void check_return_type (type expected)
1576   {
1577     type rt = compute_return_type (current_method->self->signature);
1578     if (! expected.compatible (rt))
1579       verify_fail ("incompatible return type");
1580   }
1581
1582   void verify_instructions_0 ()
1583   {
1584     current_state = new state (current_method->max_stack,
1585                                current_method->max_locals);
1586
1587     PC = 0;
1588
1589     {
1590       int var = 0;
1591
1592       using namespace java::lang::reflect;
1593       if (! Modifier::isStatic (current_method->self->accflags))
1594         {
1595           type kurr (current_class);
1596           if (_Jv_equalUtf8Consts (current_method->self->name, gcj::init_name))
1597             kurr.set_uninitialized (type::SELF);
1598           set_variable (0, kurr);
1599           ++var;
1600         }
1601
1602       if (var + _Jv_count_arguments (current_method->self->signature)
1603           > current_method->max_locals)
1604         verify_fail ("too many arguments");
1605       compute_argument_types (current_method->self->signature,
1606                               &current_state->locals[var]);
1607     }
1608
1609     states = (state **) _Jv_Malloc (sizeof (state *)
1610                                     * current_method->code_length);
1611     for (int i = 0; i < current_method->code_length; ++i)
1612       states[i] = NULL;
1613
1614     next_verify_pc = state::NO_NEXT;
1615
1616     while (true)
1617       {
1618         // If the PC was invalidated, get a new one from the work list.
1619         if (PC == state::NO_NEXT)
1620           {
1621             PC = pop_jump ();
1622             if (PC == state::INVALID)
1623               verify_fail ("saw state::INVALID");
1624             if (PC == state::NO_NEXT)
1625               break;
1626             // Set up the current state.
1627             *current_state = *states[PC];
1628           }
1629
1630         // Control can't fall off the end of the bytecode.
1631         if (PC >= current_method->code_length)
1632           verify_fail ("fell off end");
1633
1634         if (states[PC] != NULL)
1635           {
1636             // We've already visited this instruction.  So merge the
1637             // states together.  If this yields no change then we don't
1638             // have to re-verify.
1639             if (! current_state->merge (states[PC], false,
1640                                         current_method->max_stack))
1641               {
1642                 invalidate_pc ();
1643                 continue;
1644               }
1645             // Save a copy of it for later.
1646             states[PC]->copy (current_state, current_method->max_stack,
1647                               current_method->max_locals);
1648           }
1649         else if ((flags[PC] & FLAG_BRANCH_TARGET))
1650           {
1651             // We only have to keep saved state at branch targets.
1652             states[PC] = new state (current_state, current_method->max_stack,
1653                                     current_method->max_locals);
1654           }
1655
1656         // Update states for all active exception handlers.  Ordinarily
1657         // there are not many exception handlers.  So we simply run
1658         // through them all.
1659         for (int i = 0; i < current_method->exc_count; ++i)
1660           {
1661             if (PC >= exception[i].start_pc && PC < exception[i].end_pc)
1662               {
1663                 type handler = reference_type;
1664                 if (exception[i].handler_type != 0)
1665                   handler = check_class_constant (exception[i].handler_type);
1666                 push_exception_jump (handler, exception[i].handler_pc);
1667               }
1668           }
1669
1670         start_PC = PC;
1671         unsigned char opcode = bytecode[PC++];
1672         switch (opcode)
1673           {
1674           case op_nop:
1675             break;
1676
1677           case op_aconst_null:
1678             push_type (null_type);
1679             break;
1680
1681           case op_iconst_m1:
1682           case op_iconst_0:
1683           case op_iconst_1:
1684           case op_iconst_2:
1685           case op_iconst_3:
1686           case op_iconst_4:
1687           case op_iconst_5:
1688             push_type (int_type);
1689             break;
1690
1691           case op_lconst_0:
1692           case op_lconst_1:
1693             push_type (long_type);
1694             break;
1695
1696           case op_fconst_0:
1697           case op_fconst_1:
1698           case op_fconst_2:
1699             push_type (float_type);
1700             break;
1701
1702           case op_dconst_0:
1703           case op_dconst_1:
1704             push_type (double_type);
1705             break;
1706
1707           case op_bipush:
1708             get_byte ();
1709             push_type (int_type);
1710             break;
1711
1712           case op_sipush:
1713             get_short ();
1714             push_type (int_type);
1715             break;
1716
1717           case op_ldc:
1718             push_type (check_constant (get_byte ()));
1719             break;
1720           case op_ldc_w:
1721             push_type (check_constant (get_ushort ()));
1722             break;
1723           case op_ldc2_w:
1724             push_type (check_constant (get_ushort ()));
1725             break;
1726
1727           case op_iload:
1728             push_type (get_variable (get_byte (), int_type));
1729             break;
1730           case op_lload:
1731             push_type (get_variable (get_byte (), long_type));
1732             break;
1733           case op_fload:
1734             push_type (get_variable (get_byte (), float_type));
1735             break;
1736           case op_dload:
1737             push_type (get_variable (get_byte (), double_type));
1738             break;
1739           case op_aload:
1740             push_type (get_variable (get_byte (), reference_type));
1741             break;
1742
1743           case op_iload_0:
1744           case op_iload_1:
1745           case op_iload_2:
1746           case op_iload_3:
1747             push_type (get_variable (opcode - op_iload_0, int_type));
1748             break;
1749           case op_lload_0:
1750           case op_lload_1:
1751           case op_lload_2:
1752           case op_lload_3:
1753             push_type (get_variable (opcode - op_lload_0, long_type));
1754             break;
1755           case op_fload_0:
1756           case op_fload_1:
1757           case op_fload_2:
1758           case op_fload_3:
1759             push_type (get_variable (opcode - op_fload_0, float_type));
1760             break;
1761           case op_dload_0:
1762           case op_dload_1:
1763           case op_dload_2:
1764           case op_dload_3:
1765             push_type (get_variable (opcode - op_dload_0, double_type));
1766             break;
1767           case op_aload_0:
1768           case op_aload_1:
1769           case op_aload_2:
1770           case op_aload_3:
1771             push_type (get_variable (opcode - op_aload_0, reference_type));
1772             break;
1773           case op_iaload:
1774             pop_type (int_type);
1775             push_type (require_array_type (pop_type (reference_type),
1776                                            int_type));
1777             break;
1778           case op_laload:
1779             pop_type (int_type);
1780             push_type (require_array_type (pop_type (reference_type),
1781                                            long_type));
1782             break;
1783           case op_faload:
1784             pop_type (int_type);
1785             push_type (require_array_type (pop_type (reference_type),
1786                                            float_type));
1787             break;
1788           case op_daload:
1789             pop_type (int_type);
1790             push_type (require_array_type (pop_type (reference_type),
1791                                            double_type));
1792             break;
1793           case op_aaload:
1794             pop_type (int_type);
1795             push_type (require_array_type (pop_type (reference_type),
1796                                            reference_type));
1797             break;
1798           case op_baload:
1799             pop_type (int_type);
1800             require_array_type (pop_type (reference_type), byte_type);
1801             push_type (int_type);
1802             break;
1803           case op_caload:
1804             pop_type (int_type);
1805             require_array_type (pop_type (reference_type), char_type);
1806             push_type (int_type);
1807             break;
1808           case op_saload:
1809             pop_type (int_type);
1810             require_array_type (pop_type (reference_type), short_type);
1811             push_type (int_type);
1812             break;
1813           case op_istore:
1814             set_variable (get_byte (), pop_type (int_type));
1815             break;
1816           case op_lstore:
1817             set_variable (get_byte (), pop_type (long_type));
1818             break;
1819           case op_fstore:
1820             set_variable (get_byte (), pop_type (float_type));
1821             break;
1822           case op_dstore:
1823             set_variable (get_byte (), pop_type (double_type));
1824             break;
1825           case op_astore:
1826             set_variable (get_byte (), pop_type (reference_type));
1827             break;
1828           case op_istore_0:
1829           case op_istore_1:
1830           case op_istore_2:
1831           case op_istore_3:
1832             set_variable (opcode - op_istore_0, pop_type (int_type));
1833             break;
1834           case op_lstore_0:
1835           case op_lstore_1:
1836           case op_lstore_2:
1837           case op_lstore_3:
1838             set_variable (opcode - op_lstore_0, pop_type (long_type));
1839             break;
1840           case op_fstore_0:
1841           case op_fstore_1:
1842           case op_fstore_2:
1843           case op_fstore_3:
1844             set_variable (opcode - op_fstore_0, pop_type (float_type));
1845             break;
1846           case op_dstore_0:
1847           case op_dstore_1:
1848           case op_dstore_2:
1849           case op_dstore_3:
1850             set_variable (opcode - op_dstore_0, pop_type (double_type));
1851             break;
1852           case op_astore_0:
1853           case op_astore_1:
1854           case op_astore_2:
1855           case op_astore_3:
1856             set_variable (opcode - op_astore_0, pop_type (reference_type));
1857             break;
1858           case op_iastore:
1859             pop_type (int_type);
1860             pop_type (int_type);
1861             require_array_type (pop_type (reference_type), int_type);
1862             break;
1863           case op_lastore:
1864             pop_type (long_type);
1865             pop_type (int_type);
1866             require_array_type (pop_type (reference_type), long_type);
1867             break;
1868           case op_fastore:
1869             pop_type (float_type);
1870             pop_type (int_type);
1871             require_array_type (pop_type (reference_type), float_type);
1872             break;
1873           case op_dastore:
1874             pop_type (double_type);
1875             pop_type (int_type);
1876             require_array_type (pop_type (reference_type), double_type);
1877             break;
1878           case op_aastore:
1879             pop_type (reference_type);
1880             pop_type (int_type);
1881             require_array_type (pop_type (reference_type), reference_type);
1882             break;
1883           case op_bastore:
1884             pop_type (int_type);
1885             pop_type (int_type);
1886             require_array_type (pop_type (reference_type), byte_type);
1887             break;
1888           case op_castore:
1889             pop_type (int_type);
1890             pop_type (int_type);
1891             require_array_type (pop_type (reference_type), char_type);
1892             break;
1893           case op_sastore:
1894             pop_type (int_type);
1895             pop_type (int_type);
1896             require_array_type (pop_type (reference_type), short_type);
1897             break;
1898           case op_pop:
1899             pop32 ();
1900             break;
1901           case op_pop2:
1902             pop64 ();
1903             break;
1904           case op_dup:
1905             {
1906               type t = pop32 ();
1907               push_type (t);
1908               push_type (t);
1909             }
1910             break;
1911           case op_dup_x1:
1912             {
1913               type t1 = pop32 ();
1914               type t2 = pop32 ();
1915               push_type (t1);
1916               push_type (t2);
1917               push_type (t1);
1918             }
1919             break;
1920           case op_dup_x2:
1921             {
1922               type t1 = pop32 ();
1923               type t2 = pop_raw ();
1924               if (! t2.iswide ())
1925                 {
1926                   type t3 = pop32 ();
1927                   push_type (t1);
1928                   push_type (t3);
1929                 }
1930               else
1931                 push_type (t1);
1932               push_type (t2);
1933               push_type (t1);
1934             }
1935             break;
1936           case op_dup2:
1937             {
1938               type t = pop_raw ();
1939               if (! t.iswide ())
1940                 {
1941                   type t2 = pop32 ();
1942                   push_type (t2);
1943                   push_type (t);
1944                   push_type (t2);
1945                 }
1946               push_type (t);
1947             }
1948             break;
1949           case op_dup2_x1:
1950             {
1951               type t1 = pop_raw ();
1952               type t2 = pop32 ();
1953               if (! t1.iswide ())
1954                 {
1955                   type t3 = pop32 ();
1956                   push_type (t2);
1957                   push_type (t1);
1958                   push_type (t3);
1959                 }
1960               else
1961                 push_type (t1);
1962               push_type (t2);
1963               push_type (t1);
1964             }
1965             break;
1966           case op_dup2_x2:
1967             {
1968               // FIXME
1969               type t1 = pop_raw ();
1970               if (t1.iswide ())
1971                 {
1972                   type t2 = pop_raw ();
1973                   if (t2.iswide ())
1974                     {
1975                       push_type (t1);
1976                       push_type (t2);
1977                     }
1978                   else
1979                     {
1980                       type t3 = pop32 ();
1981                       push_type (t1);
1982                       push_type (t3);
1983                       push_type (t2);
1984                     }
1985                   push_type (t1);
1986                 }
1987               else
1988                 {
1989                   type t2 = pop32 ();
1990                   type t3 = pop_raw ();
1991                   if (t3.iswide ())
1992                     {
1993                       push_type (t2);
1994                       push_type (t1);
1995                     }
1996                   else
1997                     {
1998                       type t4 = pop32 ();
1999                       push_type (t2);
2000                       push_type (t1);
2001                       push_type (t4);
2002                     }
2003                   push_type (t3);
2004                   push_type (t2);
2005                   push_type (t1);
2006                 }
2007             }
2008             break;
2009           case op_swap:
2010             {
2011               type t1 = pop32 ();
2012               type t2 = pop32 ();
2013               push_type (t1);
2014               push_type (t2);
2015             }
2016             break;
2017           case op_iadd:
2018           case op_isub:
2019           case op_imul:
2020           case op_idiv:
2021           case op_irem:
2022           case op_ishl:
2023           case op_ishr:
2024           case op_iushr:
2025           case op_iand:
2026           case op_ior:
2027           case op_ixor:
2028             pop_type (int_type);
2029             push_type (pop_type (int_type));
2030             break;
2031           case op_ladd:
2032           case op_lsub:
2033           case op_lmul:
2034           case op_ldiv:
2035           case op_lrem:
2036           case op_lshl:
2037           case op_lshr:
2038           case op_lushr:
2039           case op_land:
2040           case op_lor:
2041           case op_lxor:
2042             pop_type (long_type);
2043             push_type (pop_type (long_type));
2044             break;
2045           case op_fadd:
2046           case op_fsub:
2047           case op_fmul:
2048           case op_fdiv:
2049           case op_frem:
2050             pop_type (float_type);
2051             push_type (pop_type (float_type));
2052             break;
2053           case op_dadd:
2054           case op_dsub:
2055           case op_dmul:
2056           case op_ddiv:
2057           case op_drem:
2058             pop_type (double_type);
2059             push_type (pop_type (double_type));
2060             break;
2061           case op_ineg:
2062           case op_i2b:
2063           case op_i2c:
2064           case op_i2s:
2065             push_type (pop_type (int_type));
2066             break;
2067           case op_lneg:
2068             push_type (pop_type (long_type));
2069             break;
2070           case op_fneg:
2071             push_type (pop_type (float_type));
2072             break;
2073           case op_dneg:
2074             push_type (pop_type (double_type));
2075             break;
2076           case op_iinc:
2077             get_variable (get_byte (), int_type);
2078             get_byte ();
2079             break;
2080           case op_i2l:
2081             pop_type (int_type);
2082             push_type (long_type);
2083             break;
2084           case op_i2f:
2085             pop_type (int_type);
2086             push_type (float_type);
2087             break;
2088           case op_i2d:
2089             pop_type (int_type);
2090             push_type (double_type);
2091             break;
2092           case op_l2i:
2093             pop_type (long_type);
2094             push_type (int_type);
2095             break;
2096           case op_l2f:
2097             pop_type (long_type);
2098             push_type (float_type);
2099             break;
2100           case op_l2d:
2101             pop_type (long_type);
2102             push_type (double_type);
2103             break;
2104           case op_f2i:
2105             pop_type (float_type);
2106             push_type (int_type);
2107             break;
2108           case op_f2l:
2109             pop_type (float_type);
2110             push_type (long_type);
2111             break;
2112           case op_f2d:
2113             pop_type (float_type);
2114             push_type (double_type);
2115             break;
2116           case op_d2i:
2117             pop_type (double_type);
2118             push_type (int_type);
2119             break;
2120           case op_d2l:
2121             pop_type (double_type);
2122             push_type (long_type);
2123             break;
2124           case op_d2f:
2125             pop_type (double_type);
2126             push_type (float_type);
2127             break;
2128           case op_lcmp:
2129             pop_type (long_type);
2130             pop_type (long_type);
2131             push_type (int_type);
2132             break;
2133           case op_fcmpl:
2134           case op_fcmpg:
2135             pop_type (float_type);
2136             pop_type (float_type);
2137             push_type (int_type);
2138             break;
2139           case op_dcmpl:
2140           case op_dcmpg:
2141             pop_type (double_type);
2142             pop_type (double_type);
2143             push_type (int_type);
2144             break;
2145           case op_ifeq:
2146           case op_ifne:
2147           case op_iflt:
2148           case op_ifge:
2149           case op_ifgt:
2150           case op_ifle:
2151             pop_type (int_type);
2152             push_jump (get_short ());
2153             break;
2154           case op_if_icmpeq:
2155           case op_if_icmpne:
2156           case op_if_icmplt:
2157           case op_if_icmpge:
2158           case op_if_icmpgt:
2159           case op_if_icmple:
2160             pop_type (int_type);
2161             pop_type (int_type);
2162             push_jump (get_short ());
2163             break;
2164           case op_if_acmpeq:
2165           case op_if_acmpne:
2166             pop_type (reference_type);
2167             pop_type (reference_type);
2168             push_jump (get_short ());
2169             break;
2170           case op_goto:
2171             push_jump (get_short ());
2172             invalidate_pc ();
2173             break;
2174           case op_jsr:
2175             handle_jsr_insn (get_short ());
2176             break;
2177           case op_ret:
2178             handle_ret_insn (get_byte ());
2179             break;
2180           case op_tableswitch:
2181             {
2182               pop_type (int_type);
2183               skip_padding ();
2184               push_jump (get_int ());
2185               jint low = get_int ();
2186               jint high = get_int ();
2187               // Already checked LOW -vs- HIGH.
2188               for (int i = low; i <= high; ++i)
2189                 push_jump (get_int ());
2190               invalidate_pc ();
2191             }
2192             break;
2193
2194           case op_lookupswitch:
2195             {
2196               pop_type (int_type);
2197               skip_padding ();
2198               push_jump (get_int ());
2199               jint npairs = get_int ();
2200               // Already checked NPAIRS >= 0.
2201               jint lastkey = 0;
2202               for (int i = 0; i < npairs; ++i)
2203                 {
2204                   jint key = get_int ();
2205                   if (i > 0 && key <= lastkey)
2206                     verify_fail ("lookupswitch pairs unsorted");
2207                   lastkey = key;
2208                   push_jump (get_int ());
2209                 }
2210               invalidate_pc ();
2211             }
2212             break;
2213           case op_ireturn:
2214             check_return_type (pop_type (int_type));
2215             invalidate_pc ();
2216             break;
2217           case op_lreturn:
2218             check_return_type (pop_type (long_type));
2219             invalidate_pc ();
2220             break;
2221           case op_freturn:
2222             check_return_type (pop_type (float_type));
2223             invalidate_pc ();
2224             break;
2225           case op_dreturn:
2226             check_return_type (pop_type (double_type));
2227             invalidate_pc ();
2228             break;
2229           case op_areturn:
2230             check_return_type (pop_type (reference_type));
2231             invalidate_pc ();
2232             break;
2233           case op_return:
2234             check_return_type (void_type);
2235             invalidate_pc ();
2236             break;
2237           case op_getstatic:
2238             push_type (check_field_constant (get_ushort ()));
2239             break;
2240           case op_putstatic:
2241             pop_type (check_field_constant (get_ushort ()));
2242             break;
2243           case op_getfield:
2244             {
2245               type klass;
2246               type field = check_field_constant (get_ushort (), &klass);
2247               pop_type (klass);
2248               push_type (field);
2249             }
2250             break;
2251           case op_putfield:
2252             {
2253               type klass;
2254               type field = check_field_constant (get_ushort (), &klass);
2255               pop_type (field);
2256               pop_type (klass);
2257             }
2258             break;
2259
2260           case op_invokevirtual:
2261           case op_invokespecial:
2262           case op_invokestatic:
2263           case op_invokeinterface:
2264             {
2265               _Jv_Utf8Const *method_name, *method_signature;
2266               type class_type
2267                 = check_method_constant (get_ushort (),
2268                                          opcode == (unsigned char) op_invokeinterface,
2269                                          &method_name,
2270                                          &method_signature);
2271               int arg_count = _Jv_count_arguments (method_signature);
2272               if (opcode == (unsigned char) op_invokeinterface)
2273                 {
2274                   int nargs = get_byte ();
2275                   if (nargs == 0)
2276                     verify_fail ("too few arguments to invokeinterface");
2277                   if (get_byte () != 0)
2278                     verify_fail ("invokeinterface dummy byte is wrong");
2279                   if (nargs - 1 != arg_count)
2280                     verify_fail ("wrong argument count for invokeinterface");
2281                 }
2282
2283               bool is_init = false;
2284               if (_Jv_equalUtf8Consts (method_name, gcj::init_name))
2285                 {
2286                   is_init = true;
2287                   if (opcode != (unsigned char) op_invokespecial)
2288                     verify_fail ("can't invoke <init>");
2289                 }
2290               else if (method_name->data[0] == '<')
2291                 verify_fail ("can't invoke method starting with `<'");
2292
2293               // Pop arguments and check types.
2294               type arg_types[arg_count];
2295               compute_argument_types (method_signature, arg_types);
2296               for (int i = arg_count - 1; i >= 0; --i)
2297                 pop_type (arg_types[i]);
2298
2299               if (opcode != (unsigned char) op_invokestatic)
2300                 {
2301                   type t = class_type;
2302                   if (is_init)
2303                     {
2304                       // In this case the PC doesn't matter.
2305                       t.set_uninitialized (type::UNINIT);
2306                     }
2307                   t = pop_type (t);
2308                   if (is_init)
2309                     current_state->set_initialized (t.get_pc (),
2310                                                     current_method->max_locals);
2311                 }
2312
2313               type rt = compute_return_type (method_signature);
2314               if (! rt.isvoid ())
2315                 push_type (rt);
2316             }
2317             break;
2318
2319           case op_new:
2320             {
2321               type t = check_class_constant (get_ushort ());
2322               if (t.isarray () || t.isinterface () || t.isabstract ())
2323                 verify_fail ("type is array, interface, or abstract");
2324               t.set_uninitialized (start_PC);
2325               push_type (t);
2326             }
2327             break;
2328
2329           case op_newarray:
2330             {
2331               int atype = get_byte ();
2332               // We intentionally have chosen constants to make this
2333               // valid.
2334               if (atype < boolean_type || atype > long_type)
2335                 verify_fail ("type not primitive");
2336               pop_type (int_type);
2337               push_type (construct_primitive_array_type (type_val (atype)));
2338             }
2339             break;
2340           case op_anewarray:
2341             pop_type (int_type);
2342             push_type (check_class_constant (get_ushort ()));
2343             break;
2344           case op_arraylength:
2345             {
2346               type t = pop_type (reference_type);
2347               if (! t.isarray ())
2348                 verify_fail ("array type expected");
2349               push_type (int_type);
2350             }
2351             break;
2352           case op_athrow:
2353             pop_type (type (&java::lang::Throwable::class$));
2354             invalidate_pc ();
2355             break;
2356           case op_checkcast:
2357             pop_type (reference_type);
2358             push_type (check_class_constant (get_ushort ()));
2359             break;
2360           case op_instanceof:
2361             pop_type (reference_type);
2362             check_class_constant (get_ushort ());
2363             push_type (int_type);
2364             break;
2365           case op_monitorenter:
2366             pop_type (reference_type);
2367             break;
2368           case op_monitorexit:
2369             pop_type (reference_type);
2370             break;
2371           case op_wide:
2372             {
2373               switch (get_byte ())
2374                 {
2375                 case op_iload:
2376                   push_type (get_variable (get_ushort (), int_type));
2377                   break;
2378                 case op_lload:
2379                   push_type (get_variable (get_ushort (), long_type));
2380                   break;
2381                 case op_fload:
2382                   push_type (get_variable (get_ushort (), float_type));
2383                   break;
2384                 case op_dload:
2385                   push_type (get_variable (get_ushort (), double_type));
2386                   break;
2387                 case op_aload:
2388                   push_type (get_variable (get_ushort (), reference_type));
2389                   break;
2390                 case op_istore:
2391                   set_variable (get_ushort (), pop_type (int_type));
2392                   break;
2393                 case op_lstore:
2394                   set_variable (get_ushort (), pop_type (long_type));
2395                   break;
2396                 case op_fstore:
2397                   set_variable (get_ushort (), pop_type (float_type));
2398                   break;
2399                 case op_dstore:
2400                   set_variable (get_ushort (), pop_type (double_type));
2401                   break;
2402                 case op_astore:
2403                   set_variable (get_ushort (), pop_type (reference_type));
2404                   break;
2405                 case op_ret:
2406                   handle_ret_insn (get_short ());
2407                   break;
2408                 case op_iinc:
2409                   get_variable (get_ushort (), int_type);
2410                   get_short ();
2411                   break;
2412                 default:
2413                   verify_fail ("unrecognized wide instruction");
2414                 }
2415             }
2416             break;
2417           case op_multianewarray:
2418             {
2419               type atype = check_class_constant (get_ushort ());
2420               int dim = get_byte ();
2421               if (dim < 1)
2422                 verify_fail ("too few dimensions to multianewarray");
2423               atype.verify_dimensions (dim);
2424               for (int i = 0; i < dim; ++i)
2425                 pop_type (int_type);
2426               push_type (atype);
2427             }
2428             break;
2429           case op_ifnull:
2430           case op_ifnonnull:
2431             pop_type (reference_type);
2432             push_jump (get_short ());
2433             break;
2434           case op_goto_w:
2435             push_jump (get_int ());
2436             invalidate_pc ();
2437             break;
2438           case op_jsr_w:
2439             handle_jsr_insn (get_int ());
2440             break;
2441
2442           default:
2443             // Unrecognized opcode.
2444             verify_fail ("unrecognized instruction in verify_instructions_0");
2445           }
2446       }
2447   }
2448
2449 public:
2450
2451   void verify_instructions ()
2452   {
2453     branch_prepass ();
2454     verify_instructions_0 ();
2455   }
2456
2457   _Jv_BytecodeVerifier (_Jv_InterpMethod *m)
2458   {
2459     current_method = m;
2460     bytecode = m->bytecode ();
2461     exception = m->exceptions ();
2462     current_class = m->defining_class;
2463
2464     states = NULL;
2465     flags = NULL;
2466     jsr_ptrs = NULL;
2467   }
2468
2469   ~_Jv_BytecodeVerifier ()
2470   {
2471     if (states)
2472       _Jv_Free (states);
2473     if (flags)
2474       _Jv_Free (flags);
2475     if (jsr_ptrs)
2476       _Jv_Free (jsr_ptrs);
2477   }
2478 };
2479
2480 void
2481 _Jv_VerifyMethod (_Jv_InterpMethod *meth)
2482 {
2483   _Jv_BytecodeVerifier v (meth);
2484   v.verify_instructions ();
2485 }
2486
2487 // FIXME: add more info, like PC, when required.
2488 static void
2489 verify_fail (char *s)
2490 {
2491   char buf[1024];
2492   strcpy (buf, "verification failed: ");
2493   strcat (buf, s);
2494   throw new java::lang::VerifyError (JvNewStringLatin1 (buf));
2495 }
2496
2497 #endif  /* INTERPRETER */