[kaffe] completed bytecode verifier!

[Rob Gonzalez]

Hi all,

I just committed the bytecode verifier.  It's a huge chunk of code and
it's very likely that there are little bugs lurking around in it...I can't
even count how many off-by-one errors I had during development.

The LostTrampolineFrame regression test now fails, but I'm pretty sure
that's no fault of the verifier.  The test expects the verification of one
of the classes to fail, which it does, though it now fails during linking
where it used to fail in code analysis just prior to execution.

Section 4.8 of the JVML Spec 2 lists the static and structural constraints
the verifier must check.  The following is a list of constraints that I do
not check and the reasons for not doing so:

4.8.1: Static constraints
- The value of the count operand of each invokeinterface instruction must
  reflect the number of local variables necessary to store the arguments
  to be passed to the interface method, as implied by the descriptor of
  the CONSTANT_NameAndType_info structure referenced by the 
  CONSTANT_InterfaceMethodref constant pool entry

  I don't check this because other VM's ignore the count argument as well.

- The new instruction cannot be used to create an instance of an abstract
  class.

  This should be checked, but it cannot be checked by the verifier because
  the verifier cannot load classes unless they are necessary for type
  checking.  Thus if the type of class created by the new instruction is
  not loaded, there's no way to check if it's abstract.

  This should be checked in code-analyse.


4.8.2: Structural Constraints
- Each invokespecial instruction must name an instance initialization
  method (§3.9), a method in the current class, or a method in a
  superclass of the current class.

  Not enforced by Sun's verifier.

- Each instance initialization method (§3.9), except for the instance
  initialization method derived from the constructor of class Object, must
  call either another instance initialization method of this or an
  instance initialization method of its direct superclass super before its
  instance members are accessed.

  TODO :).  Clearly this is subject to the halting problem because of
  branches and all, so I wanted to explore Sun's behavior a little more
  before committing to a design for this.  BCEL's JustIce verifier throws
  a VerifyError if any branch occurrs before a call to another <init>()
  method, which seems pretty reasonable to me.

- The instruction following each jsr or jsr_w instruction may be returned
  to only by a single ret instruction.

  I don't see why this is a constraint, and I don't see how to check it
  without imposing unreasonable restrictions on the bytecode.  I treat the
  ret instruction basically as a goto.

- No jsr or jsr_w instruction may be used to recursively call a subroutine
  if that subroutine is already present in the subroutine call
  chain. (Subroutines can be nested when using try-finally constructs from
  within a finally clause. For more information on Java virtual machine
  subroutines, see §4.9.6.)

  TODO.  Not a big deal, I just hate messing with the subroutine stuff.


Furthermore, when merging operand stacks during pass 3b, if corresponding
types on each stack are not compatible I simply ignore the error unless it
really becomes a problem.  It doesn't take much to convince yourself that
this is OK.


TODO next: remove all the (now) unnecessary checks currently performed in
code-analyse.c.


Time to go have a beer ;)

Cheers,
Rob