Wednesday, June 27, 2012

Properties and relationships - it won't get easier

Okay, now to show you the peak of what I've done using ASM: Look at these classes:

@PropertyFactory("p")
public class Test {
    protected final PropertyChangeSupport s = new PropertyChangeSupport(this);
    protected final Properties p = new BoundProperties(s);
   
    @Property
    private String s;
    
    public void setS(String s) {this.s = s;}
    public String getS() {return s;}
    //add/remove PropertyChangeListener methods
}

//test code
Test t = new Test();
t.addPropertyChangeListener(...); //prints to System.out
t.setS("hello"); //listener fires!

With the right setup (and with setup I don't mean things you have to do every time; it's just either configuring a ClassLoader or transforming the bytecode directly after compilation), it's as simple as that to add property change support, and other things; in fact everything that can be done with a Properties object. (in case you never heard of that creation, look at the code) And there is another thing I have done using properties: bidirectional 1:1, 1:n and m:n relationships, which is pretty nice if it's as simple as this:

@PropertyFactory("p")
public class A {
    protected final Properties p = new BasicProperties();
   
    @OneToOne("a")
    private B b;
    //getters and setters
}

@PropertyFactory("p")
public class B {
    protected final Properties p = new BasicProperties();
   
    @OneToOne("b")
    private A a;
    //getters and setters
}

//test code
A a = new A(); B b = new B();
a.setB(b);
System.out.println(b.getA() == a); //true!

I'm skipping the other cardinalities, and the two examples here were a little modified, but they are functional! It's not simplified beyond what's necessary for the code to actually work as advertised. If you want to take a look at the complete test cases, look here. It also includes a ClassLoader that can do the job, as well as the setup for junit that invokes the test code on the modified class.

Okay, the advertising is over; one or two sentences about the internals:
  • The class loader that is used prints all classes it loads (that is, the test classes) to a directory structure analogous to java's package structure. The printed text is the disassembled bytecode that is actually loaded - so not the same code as the compiled class files, and even some classes that are not present in the sources. If you can read bytecode, that's perfect to see every detail on how a simple this.b = b; comes to setting the private A a; in the newly referenced B instance.
  • The relation annotations create a new attribute, for example OneToOne<A> a$o2o; (with default access). This is essentially the field you would name a if not making your life easier with ASM.
  • That field is accessed by a class like B$$a$o2o_EntityFunction (For the OneToOne field named a in class B). It implements a simple interface and implements only one method, taking the B instance and returning the OneToOne object. Since the class is in the same package as B, the access is allowed, and any classes can be related without exposing any normal-java accessible fields for other classes.
I hope you can get your benefits out of this little gem!

Saturday, June 9, 2012

Under the Hood: Transforming Bytecode

This will be more or less a "what I've already done", although without much Java code. It got pretty verbose last time, as I explained how to use the visitors to create a new class. I'll focus on the bytecode transformations this time; the Java code is pretty straightforward then.

So, my goal was to make coding easier when working with properties. Basically, I want to have this:

public class Test {
    private int a;
   
    public void setA(int a) {
        this.a = a;
    }
   
    public int getA() {
        return a;
    }
}

transformed into this:

public class Test {
    private Properties properties = new BasicProperties();
   
    private final Property<Integer> a = properties.cfg(Properties.NAME, "a").property(0);
   
    public void setA(int a) {
        this.a.setValue(a);
    }
   
    public int getA() {
        return a.getValue();
    }
}

Of course, we need to add a few little modifications to control our transformation, but it would still simplify reading the code:

public class Test {
    private Properties properties = new TestProperties();
   
    @Property
    private int a;
   
    public void setA(int a) {
        this.a = a;
    }
   
    public int getA() {
        return a;
    }
}

That's enough for my simplistic version. I'll skip the field changing type and instead concentrate on how code accesses the fields. Now let's look at the source and target bytecodes; original at the top and goal at the bottom:


public void setA(int);
  Signature: (I)V
  Code:
   0:    aload_0
   1:    iload_1
   2:    putfield    #5; //Field a:I
   5:    return

 public void setA(int);
  Signature: (I)V
  Code:
   0:    aload_0
   1:    getfield    #10; //Field a:Lnet/slightlymagic/beans/properties/Property;
   4:    iload_1
   5:    invokestatic    #8; //Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
   8:    invokeinterface    #11,  2; //InterfaceMethod net/slightlymagic/beans/properties/Property.setValue:(Ljava/lang/Object;)V
   13:    return


So in the original, we have a simple putfield, whereas our goal is to do a getfield, fetching our wrapper object, and then doing a setValue(Object) with our value. That we have to wrap the int into an Integer ourselves at the bytecode level is a complication, but not so hard.
What really poses a problem is where we realize that we're doing the important stuff: basically, at 2: putfield, we know that setting the attribute is happening. However, the target bytecode differs before that: to fetch the wrapper! Don't be temptated to buffer some instructions and then insert the getfield one entry ahead; imagine we're doing this.a = 2*a instead. It simply wouldn't line up. Instead, we use the swap opcode the JVM provides to bring the stack into order, even though the bytecode will be different than that from javac.
First, look at the stack in the original:

[ Test I ]
putfield
[ ]

and how we could transform the putfield into a sequence of instructions that have the same begin and end stack:

[ Test I ]
invokestatic Integer Integer.valueOf(int)
[ Test Integer ]
swap
[ Integer Test ]
getfield a Property
[ Integer Property ]
swap
[ Property Integer ]
invokeinterface void Property.setValue(Object)
[ ]

Not so hard at all. Note that I did the boxing at first, because swap can't handle 64 bit values like long and double, so I wrap these into references before doing anything else. (Don't ask me what that means in a 64 bit JVM, but since bytecode is platform independent, it's fine if we just know how it behaves in 32 bits)

public int getA();
  Signature: ()I
  Code:
   0:    aload_0
   1:    getfield    #5; //Field a:I
   4:    ireturn


public int getA();
  Signature: ()I
  Code:
   0:    aload_0
   1:    getfield    #10; //Field a:Lnet/slightlymagic/beans/properties/Property;
   4:    invokeinterface    #12,  1; //InterfaceMethod net/slightlymagic/beans/properties/Property.getValue:()Ljava/lang/Object;
   9:    checkcast    #13; //class java/lang/Integer
   12:    invokevirtual    #14; //Method java/lang/Integer.intValue:()I
   15:    ireturn


The same strategy here:

[ Test ]
getfield
[ I ]

becomes:

[ Test ]
getfield a Property

[ Property ]
invokeinterface Object Property.getValue()
[ Object ]
checkcast Integer
[ Integer ]
invokevirtual int Integer.intValue()
[ I ]
which is even more straight forward than the setter. But here comes the constructor:

public net.slightlymagic.beans.test.Test();
  Signature: ()V
  Code:
   0:    aload_0
   1:    invokespecial    #1; //Method java/lang/Object."<init>":()V
   4:    aload_0
   5:    new    #2; //class net/slightlymagic/beans/properties/basic/BasicProperties
   8:    dup
   9:    invokespecial    #3; //Method net/slightlymagic/beans/properties/basic/BasicProperties
."<init>":()V
   12:    putfield    #4; //Field properties:Lnet/slightlymagic/beans/properties/Properties;
   15:    return


public net.slightlymagic.beans.test.Test();
  Signature: ()V
  Code:
   0:    aload_0
   1:    invokespecial    #1; //Method java/lang/Object."<init>":()V
   4:    aload_0

   5:    new    #2; //class net/slightlymagic/beans/properties/basic/BasicProperties
   8:    dup
   9:    invokespecial    #3; //Method net/slightlymagic/beans/properties/basic/BasicProperties
."<init>":()V
   12:    putfield    #4; //Field properties:Lnet/slightlymagic/beans/properties/Properties;
   15:    aload_0
   16:    aload_0
   17:    getfield    #4; //Field properties:Lnet/slightlymagic/beans/properties/Properties;
   20:    ldc    #5; //String name
   22:    ldc    #6; //String a
   24:    invokeinterface    #7,  3; //InterfaceMethod net/slightlymagic/beans/properties/Properties.cfg:(Ljava/lang/Object;Ljava/lang/Object;)Lnet/slightlymagic/beans/properties/Properties;
   29:    iconst_0
   30:    invokestatic    #8; //Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
   33:    invokeinterface    #9,  2; //InterfaceMethod net/slightlymagic/beans/properties/Properties.property:(Ljava/lang/Object;)Lnet/slightlymagic/beans/properties/Property;
   38:    putfield    #10; //Field a:Lnet/slightlymagic/beans/properties/Property;
   41:    return


A constructor has basically three parts: the super constructor call, initializing fields, and the explicit constructor code. If we don't initialize a explicitly in its declaration, it won't appear in the constructor, which is bad if we wait for some bytecode to tell us that it's time for action. So we have to find a place where inserting our own initialization is fine, and that place is NOT directly after the super constructor. Rather, it's after creating the Properties object, our factory for the property wrappers - a putfield instruction. (and this is actually where I stopped, so my code doesn't do this right yet)
Another thing to note is that there might be multiple putfields in the constructor, but only the first one is the initialization, needing our special treatment.
And now to the bytecode of our modification. Let's for now pretend that there is an aload_0; iconst_0; putfield; here; it might be, so we have to prepare that there is something on the stack:

[ Test I ]
invokestatic Integer Integer.valueOf(int)
[ Test Integer ]
swap
[ Integer Test ]
dup_x1
[ Test Integer Test ]
getfield properties Properties
[ Test Integer Properties ]
ldc "name"
[ Test Integer Properties String ]
ldc "a"
[ Test Integer Properties String String ]
invokeinterface Properties Properties.cfg(Object,Object)
[ Test Integer Properties ]
swap
[ Test Properties Integer ]
invokeinterface Property Properties.property(Object)
[ Test Property ]
putfield a Property
[ ]

and the last thing: look at the stack: int begins with two elements, but has up to 5 elements in the middle, so the maxStack must be increased by three (or two, if the value is long or double). It's as simple as storing a field with that value and overwriting visitMaxs() to add it to the stack.

Thanks! If you want to look at the code, you find it here.

Sunday, June 3, 2012

The Visitor pattern

A quick interruption from our Bytecode study for the Visitor pattern. A programming pattern is basically a technique which can be applied in different situations for some benefit, and at first I failed to see the benefit behind the visitor pattern. The visitor pattern has four core concepts:
  • There is a SomethingVisitor class or interface.
  • That class has many visitSomeAspect() methods that are either void or return another Visitor for that aspect.
  • A class can form an "entry point" by providing an accept(SomethingVisitor) method.
  • That accept() method calls the visit() methods in an order somehow defined in the SomethingVisitor class.
Let's take ASM as an example: There is the ClassReader class that provides an accept(ClassVisitor) method. This method calls the various visit() methods, starting with visit(), visitSource(), visitOuterClass(), followed by sequences of visitAnnotation(), visitAttribute(), visitInnerClass(), visitField(), visitMethod(), and ended with visitEnd(). In turn, visitAnnotation(), visitField() and visitMethod() return visitors on their own that get the details about the annotation, field or method. What we're actually describing is a tree structure, so why don't we simply create some ClassFile class that has some fields for name, superclass, interfaces and so on? What's the benefit of the pattern?

If you realized it straight on, you're probably smarter than me, but after working for a few days with ASM, I realized it myself. Unlike data structures, methods are inherently chainable. Let me show you some lines from ClassVisitor:

public abstract class ClassVisitor {
    protected final int api;
    protected ClassVisitor cv;

    public ClassVisitor(final int api) {
        this(api, null);
    }

    public ClassVisitor(final int api, final ClassVisitor cv) {
        this.api = api;
        this.cv = cv;
    }

    public void visit(
        int version,
        int access,
        String name,
        String signature,
        String superName,
        String[] interfaces)
    {
        if (cv != null) {
            cv.visit(version, access, name, signature, superName, interfaces);
        }
    }
}


Just ignore the api, which is for future compatibility, and look at cv and visit(). A ClassVisitor can be constructed with another delegate ClassVisitor, and the visit() methods delegate by default; if there is no delegate, the methods are no-ops. That's a really nice behavior, because you can stick ClassVisitors that do only some small thing together to get a more complex behavior. And they probably work right by doing so, because what you expect from one visitor is that it transforms one correct class into another, so each visitor gets a correct input, and you expect it to get a correct output back from it.

Now let's speak about performance. The most obvious thing is that, with the visitor pattern, you don't have to actually build your tree structure in order to process it. Basically, you can think of the visitor pattern as a stream-approach to tree processing. Think of a binary stream: you can chain different kinds of streams together, each operating on the output of the former one, yielding a result that is the composition of all the transformation. The analogue to a tree structure would be a byte array. Instead of chaining streams, each transform() method takes and returns a byte[], which is then passed to the next transform() method. This is a lot of excessive object creation, plus that each transformation processes the array from front to back. In a stream, there is only one pass that does all of the processing in a chain, and it certainly needs less memory. Of course, it's possible that the class providing accept() operates on a real tree structure, but not even that is a requirement. Thinking of binary again, there's no need to read a file into a byte[] before processing it, and then writing it back to a file again.

Let's talk Magic shortly: I repeatedly find myself thinking about the right way to represent cards. There is much you can store about a card: Name, types, abilities, power/toughness. There is also the Multiverse ID, but that is printing- and language dependent. Abilities have translated text, and the printed English text is not the same as the current oracle wording. Abilities can be present in a software-specific, machine-readable language. Images of different resolutions might be present, as well as flavor text for specific printings, artist name, copyright notice, and so on.
To make one data structure for all needs is virtually impossible. The visitor pattern is a tool that might make it possible to make all the data accessible without actually requiring all of it, and a visitor can also be used to transform one tree representation into another one with a different focus, without polluting them with explicit conversion methods featuring major duplication of code.

So the visitor pattern is, after a deeper analysis, nothing of that that you see on the surface: a method- and class name convention, combined with a specified order of method calls. It is a technique for processing complex data structures without the intermediate creation of a huge in-memory tree, and it can even boost performance. It makes you independent of the underlying tree structure, be it in memory, on disk or anywhere else. Instead, you have to conform to a single interface and be able to process the method arguments. And that's something I do call a benefit!

Saturday, June 2, 2012

Under the Hood: Creating a class with ASM

Now, let's get serious! We know how ClassLoaders are responsible for getting the binary class data to load Java classes, and we know how that binary class data actually looks. What's missing is a way to effectively modify that data, without worrying too much about the low-level details of data storage in a class file.
And that's where ASM comes into play. ASM is one library (BCEL is another) for bytecode manipulation, and it seems to be the "tool of choice" out there. That means it's relatively active in development, yet mature and usable. Let's dive straight into a code example for creating (not modifying) a class with ASM:

public class AsmBuilder implements Opcodes {
    public static final byte[] HelloWorld = HelloWorld();
  
    private static byte[] HelloWorld() {
        ClassWriter cw = new ClassWriter(0);
      
        cw.visit(V1_6, ACC_PUBLIC | ACC_SUPER, "net/slightlymagic/asm/test/HelloWorld", null, "java/lang/Object",
                null);
        cw.visitSource("<generated>", null);
      
        HelloWorld_init(cw);
        HelloWorld_main(cw);
        HelloWorld_hello(cw);
      
        return cw.toByteArray();
    }
  
    private static void HelloWorld_init(ClassWriter cw) {
        MethodVisitor mv = cw.visitMethod(ACC_PUBLIC, "<init>", "()V", null, null);
        mv.visitCode();
        mv.visitVarInsn(ALOAD, 0);
        mv.visitMethodInsn(INVOKESPECIAL, "java/lang/Object", "<init>", "()V");
        mv.visitInsn(RETURN);
        mv.visitMaxs(1, 1);
        mv.visitEnd();
    }
  
    private static void HelloWorld_main(ClassWriter cw) {
        MethodVisitor mv = cw.visitMethod(ACC_PUBLIC | ACC_STATIC, "main", "([Ljava/lang/String;)V", null, null);
        mv.visitCode();
        mv.visitTypeInsn(NEW, "net/slightlymagic/asm/test/HelloWorld");
        mv.visitInsn(DUP);
        mv.visitMethodInsn(INVOKESPECIAL, "net/slightlymagic/asm/test/HelloWorld", "<init>", "()V");
        mv.visitMethodInsn(INVOKEVIRTUAL, "net/slightlymagic/asm/test/HelloWorld", "hello", "()V");
        mv.visitInsn(RETURN);
        mv.visitMaxs(2, 1);
        mv.visitEnd();
    }
  
    private static void HelloWorld_hello(ClassWriter cw) {
        MethodVisitor mv = cw.visitMethod(ACC_PUBLIC, "hello", "()V", null, null);
        mv.visitCode();
        mv.visitFieldInsn(GETSTATIC, "java/lang/System", "out", "Ljava/io/PrintStream;");
        mv.visitLdcInsn("Hello, World");
        mv.visitMethodInsn(INVOKEVIRTUAL, "java/io/PrintStream", "println", "(Ljava/lang/String;)V");
        mv.visitInsn(RETURN);
        mv.visitMaxs(2, 1);
        mv.visitEnd();
    }
}

What you see here is a series of visitSomething() calls on a ClassWriter (which implements ClassVisitor) and the MethodVisitors created from it. The Opcodes interface impelemented just gives us easy access to some useful constants. Before elaborating on the Visitor pattern next time, let's go through the calls:

ClassVisitor.visit() gets all data that is necessary once for a class definition; that includes class version, access flags like public, class name, superclass name, signature (for generic classes like List<T>) and an array of implemented interfaces. visitSource() gets one piece of optional information; the source file name, plus a debug string that I know nothing about.

Now to the interesting method instructions: visitMethod() again takes some data that is needed once for each method: access flags, name, method descriptor, signature, and declared exceptions. visitCode() simply indicates that the actual instructions follow, as opposed to the optional annotations.
visitVarInsn(ALOAD, 0) takes an opcode that works with local variables (either LOAD or STORE) of a specific type (a reference in this case; don't ask me why the prefix is A) and takes the index of a local variable; as I said earlier, 0 is the implicit this reference for nonstatic methods. So, in plain words, this instruction pushes this onto the stack.
visitMethodInsn(INVOKESPECIAL, "java/lang/Object", "<init>", "()V") invokes a method. In this case, because it's a constructor (see the name), using the INVOKESPECIAL opcode. There are four other INVOKE opcodes, but we'll only see two others in this example. The next argument is the owner, i.e. the class containing the called method, followed by name and descriptor. If you haven't guessed it, this is a super() call, invoked on this. (Ironically, writing this.super(); in Java is illegal, yet the implicit reference is needed of course)
Last but not least, there's visitInsn(RETURN). Unlike visit*Insn(), visitInsn() takes no additional arguments, because the opcodes supported by this instruction simply don't need any. RETURN is only one of many RETURN opcodes for void methods (including constructors).
Finally, there's visitMaxs(1, 1) and visitEnd(). The maxs are stack and local. stack is 1, because there is at most one entry on the stack, namely this after ALOAD 0. And the sole local variable is, again, this, ammounting for 1 again.

A look at main([Ljava/lang/String;)V: We have a new type of instruction again! visitTypeInsn(NEW, "net/slightlymagic/asm/test/HelloWorld") takes an opcode that needs a class name. In this case, we allocate a new object (of our class) on the heap.
visitInsn(DUP) duplicates the top element on the stack, i.e. the reference.
visitMethodInsn(INVOKESPECIAL, "net/slightlymagic/asm/test/HelloWorld", "<init>", "()V") invokes the constructor on our new object. Think about it: the constructor has an implicit argument that must be on the stack prior to calling, and in the case of additional parameters, these have to come even after the new reference, so there's essentially no way to integrate the constructor call into the NEW opcode. (Well, of course you could, but why complicate the VM by introducing a different order of arguments for constructor calls if you can make it a really regular INVOKESPECIAL call simply by splitting object creating into two opcodes?) And here, you have the reason for the previous DUP: <init> is void, but we want to use the object afterwards, so we have to keep the reference on the stack some other way.
visitMethodInsn(INVOKEVIRTUAL, "net/slightlymagic/asm/test/HelloWorld", "hello", "()V") invokes hello(). INVOKEVIRTUAL is probably the most common INVOKE opcode. It's used for all nonstatic, non-constructor, non-interface methods (and now, if you wonder what the fifth variant, as hinted above, is: it's INVOKEDYNAMIC, which is a new feature targeted at dynamic JVM languages, not Java itself). The big point about virtual method invocation is overriding. The VM searches for an overridden variant of the called method, which is not necessarily that of the owner class given in the instruction.
visitInsn(RETURN); visitMaxs(2, 1); visitEnd(); there were two entries on the stack after DUP, and there is one parameter [Ljava/lang/String; in the main method.

Now hello()V: visitFieldInsn(GETSTATIC, "java/lang/System", "out", "Ljava/io/PrintStream;"), yet another type of instruction. visitFieldInsn() supports the four logically named opcodes GETFIELD, GETSTATIC, PUTFIELD and PUTSTATIC. The nonstatic variants take a reference from the stack for obvious reasons. Then there's an owner, a field name, and a field descriptor. Unlike LOAD and STORE, where there's no descriptor, but different opcodes for different types.
visitLdcInsn("Hello, World"), where LDC stands for "load constant". The argument is of type Object, but must be a primitive wrapper like Integer, or String.
visitMethodInsn(INVOKEVIRTUAL, "java/io/PrintStream", "println", "(Ljava/lang/String;)V") is our first method invocation with real arguments! I hope you can follow what's currently on the stack; there's a PrintStream (System.out) and a String ("Hello, World"), and now we're invoking a nonstatic method of PrintStream, taking a String as an argument. Knowing the order of elements on the stack is important when trying to modify bytecode; obviously, when you insert instructions, you have to leave the stack as you found it to have the following code work correctly (and don't forget to tamper with maxStack afterwards!)
visitInsn(RETURN); visitMaxs(2, 1); visitEnd(); there were two entries on the stack after LDC, and the method is not static.

Now, to make this post longer, and not make you wait on how to invoking your new class, let's look at the classloading part. we have byte[] containing the class and need a Class from it. Take a look at this simple custom ClassLoader:

public class DynamicClassLoader extends ClassLoader {
    private final HashMap<String, byte[]> bytecodes = new HashMap<String, byte[]>();
   
    public DynamicClassLoader() {
        super();
    }
   
    public DynamicClassLoader(ClassLoader parent) {
        super(parent);
    }
   
    public void putClass(String name, byte[] bytecode) {
        bytecodes.put(name, bytecode);
    }
   
    @Override
    protected Class<?> findClass(String name) throws ClassNotFoundException {
        //remove here, because the class won't be loaded another time anyway
        byte[] bytecode = bytecodes.remove(name);
        if(bytecode != null) {
            return defineClass(name, bytecode, 0, bytecode.length);
        } else {
            return super.findClass(name);
        }
    }
}


... and take a look at that simple main method:

public static void main(String[] args) throws Exception {
    DynamicClassLoader l = new DynamicClassLoader();
    l.putClass("net.slightlymagic.asm.test.HelloWorld", AsmBuilder.HelloWorld);
   
    Class<?> HelloWorld = l.loadClass("net.slightlymagic.asm.test.HelloWorld");
    HelloWorld.getMethod("main", String[].class).invoke(null, (Object) args);
}


Of course, we can't plainly reference a class that isn't present at compile time, but we can use reflection to test it. Of course, normally the generated class would implement some interface so we can store it in a variable other than an Object, and make regular method calls through the interface.

Wednesday, May 30, 2012

Under the Hood: Java Bytecode

So, now that we have cleared up how a Java application is executed, I can talk about bytecode manipulation, a technique to modify the compiled classes before execution.
There are two possible times when modification can occur: at build time, modifying the class filers after compilation, or at runtime, using a class loader that modifies the bytes of the class before passing them on and actually defining the class from it. Both have their advantages: Build time simplifies the structure at runtime; your application runs like an ordinary Java application, except that not all of its classes were ordinarily created from Java source code. Runtime gives you the possibility of applying different modifications in different executions, which could be used to, say provide compatibility to different environments. More importantly in my opinion, this allows to create completely new classes based on user input!

Let me give you an example: You make an application that draws the graph of a function the user types into a text field, so basically you take y = f(x) for each coordinate visible in the plot; that's a lot of times and you want to compute your function very quickly. So, instead of parsing the expression, building a tree from it, inserting a new value for x, and then evaluating the function, wouldn't it be nice to parse the expression into a real Java class that is executed on the tested and optimized JVM, with the possibility that your code is even JIT-compiled into machine code for an extra boost?

And guess what - that's not only possible, but even relatively easy, once you've grasped what java byte code looks like, so that's what were going to look at now. It's pretty straight forward that a class consists of fields and methods, and when you think about the fact that inner classes have separate class files, it becomes clear that there must be some information about enclosing class and inner classes, too.

The code of methods is of course where it gets interesting. The JVM is a stack based machine, which means that values are kept in a last-in-first-out data structure, and every operation pops a specific number of values from the stack and pushes its results onto the stack again. Note that this data is not related to local variables or fields; here, we're basically talking about the steps taken in evaluating an expression.
Also, type names have a special form in class files. Where a class name is needed, a string of the form java/lang/Object is used; where it could be a primitive type, too, this is wrapped into L...;, where L somehow was chosen to mean "object type", and ; denotes the end of the type name. As another example, long, which can't use the L, was given J as the identifier, and boolean uses Z; arrays prepend a [ for every dimension. A method, for example int indexOf(char ch) or String substring(int beginIndex, int endIndex) would be described as (C)I or (II)Ljava/lang/String; - note that the name is not part of the signature but stored separately.

And that's all you really need to know, except for the few less than 256 possible commands (opcodes) that the JVM knows. The details of how all the strings are stored in a classfile is hidden from you when you use ASM to generate bytecode.

Now let's look at some bytecode, as this is where it gets interesting. A simple example first:

package Example;
class Example {
    int a;
    void example(int a) {
        this.a = a;
    }
}

...and the bytecode for example():


example(I)V
ALOAD 0
ILOAD 1
PUTFIELD example/Example.a : I
RETURN


MAXSTACK = 2
MAXLOCALS = 2

ALOAD pushes a local variable onto the stack. In this example, there are - surprise - two! Not only is there parameter a, there's also the implicit this of every nonstatic method. When both are on the stack (explaining the MAXSTACK entry above), PUTFIELD can take the second value and store it into the named field of the first reference on the stack, which better be an instance of Example.

Let's take a more complex example:

package Example;
class Example {
    int a;
    Example(int a) {
        this.a = a;
    }
}

...doesn't seem so? Look at the bytecode:

(I)V
ALOAD 0
INVOKESPECIAL java/lang/Object.<init> ()V
ALOAD 0
ILOAD 1
PUTFIELD example/Example.a : I
RETURN

MAXSTACK = 2
MAXLOCALS = 2

First of all, as you see, constructors are internally void methods with special names. The special code here is ironically the one that we didn't write ourselves: the superconstructor invocation.

Okay, that's it for today! Thanks for reading!

Monday, May 28, 2012

Under the Hood: Classloading

I'm kind of a tinkerer... I like exploring new aspects of things I already know, or new things altogether, even if there is no apparent gain in it. And I bet many of you (well, if there were many readers in the first place...) share this trait with me, because it is one of the things that most engineers share.

The "thing" that I explored in the last week is Java itself, and the new aspect is the Java Bytecode, along with a few intricacies of Java that most programmers never have to worry about, namely bytecode manipulation and class loading.

Just in case you are not aware of it, I'll first describe the lifecycle of a HelloWorld program from writing it, up to its execution. It all starts, of course, with a source file. In the standard case, that's HelloWorld.java, but there are other languages, like Groovy, Scala and JRuby, that all run on the JVM.
This leads us directly to our next step, compilation. The JVM is, as the name suggests, a machine, just like any computer (except it's "virtual"), and has an instruction set it can execute. The Java compiler javac translates the more or less human readable source code into a .class file that contains code executable by the JVM, as do other compilers like gcj or scalac, except that in case of scalac, the source is written in a different language of course.

One aside about gcj: there are a few Java compiler vendors around, but by far not as many as for other languages like C. The answer is, again, the JVM: while a C compiler creates code for a specific architecture and OS, and therefore each new platform needs a new compiler (although much logic can be reused, of course), Java targets only a single platform, the JVM. Therefore, there's no inherent need for numerous compilers and Java doesn't have the problem of incompatible dialects. Still, there is some competition; for example, gcj is an open source alternative to javac. More importantly, the part of Java that is platform specific is the JVM. In Java's early days, Microsoft had its own Java implementation, which was kind of crappy compared to Sun's and was thankfully soon discontinued. Additionally, there are VMs implemented in Java, or ones that target platforms where Oracle does not provide support, or ones with smaller memory requirements, etc.

So, now we have a class file consisting of Java bytecode, independent of the language we started with. Using the java command, we can launch the main method of that class, but this involves more steps than are apparent!
Every java application has a system class loader. A ClassLoader is responsible for finding class files, reading them, and loading the classes into memory. In the most basic case, the classloader has a list of URLs (the classpath) that contains locations where classes are found. By default, this classpath contains the JRE classes (plus some more) and those found in the current directory, e.g. HelloWorld.class. Other classloaders delegate to a parent classloader, but may add new search locations or other means of getting the bytes that make up a class.
Now, the classloader loads the main class of the application, and the main thread starts, executing the main method. This method may in turn require other classes which are then loaded by the same classloader that also loaded the current class. This means by extension that normally, all classes are loaded by the same classloader that also loaded the main class. However, it's also possible to create and invoke classloaders directly, creating a class that was loaded by a different classloader than the current class. This is important because of two things. Firstly, as I said, the new classloader can add new ways of loading classes (the main reason for using a separate classloader), and secondly because it can introduce subtle problems when multiple classloaders define classes with the same name: they are not compatible, and you get a ClassCastException when you try to mix them. Don't worry, there's an easy solution: define an interface that is loaded by a common parent classloader, and only cast to the interface.

And finally, our main method can execute. And since this post was already long enough, I'll tell the story about bytecode manipulation with ASM next time ;)

Tuesday, January 10, 2012

Entities and values

As so often in programming, one big question arose when I worked on my Undo/Replication framework: What is an entity, and what is a value?

I use the word entity to make clear that I mean something different from objects. An object is something identified by an address pointer, whereas for a primitive value, its bytes in memory directly represent the value instead of an address. What I mean with entity/value is best explained by an example from databases:

Suppose you have a database table storing the data of a company's employees. There is a surname, a prename, a birth date, and so on. Besides others, there's an address. The simplest approach is to handle each of these items as a table column: Surname and prename are strings, the birthdate uses a special date column type. The address can also be simply taken as a string, but there are other ways:

An address is composed of a street name, a number, probably also an appartment number, country, state etc. It could be beneficial to store all these data in a table on its own, give it an ID (the database way of saying address), and only reference this ID in the employee table.

Don't forget the third way! You could use all those columns, but put them directly into the employee table, so there would be prename, surname, birth date, street, stree no., appartment no., etc.

What's the best? Of course, it depends! Variant one is easy to use, but lacks intrinsic validity checks: When the database doesn't know that something should be an (appartment) number, how should it check it's even a number? Variant two can handle a very specific case "better": two workers have the same address. In this case, the same ID can be referenced multiple times, so that both employees not only have equal addresses but also have the same one. In this particular case, the benefit is not too big, but there are use cases where it's important that something can be referenced. About the third, it really combines the downsides of the both above... I personally see no benefit in using it. It there are, I'm sorry I didn't see them.

Now, what should have triggered your attention was the word "ID". As soon as something has an identity, it's an entity. Note how the prename is a String, which is an Object type in Java, but only a value. On the other hand, the address in case 2 has an identifier and is an entity.

And now we're back: What I do is to assign IDs to the objects I want to replicate. The objects have values which can be changed, and I transmit changes like "property XY of object 01 changed from 'ab' to 'cd'."

And now the big question: what about collections? Should it be "element 'ab' was added to list 01" (i.e. they are entities) or "element 'ab' was added to list XY of object 01?"

Saturday, January 7, 2012

Replicating Game States - JGroups

So now I've got it. My goals in implementing Replication was to keep it out of the core functionality while still making it easy to use without worrying about replication yourself. How do you do that? By providing a general interface to other software (in my case, that's a listener) and implementing a specific one for the task at hand.

So my History class, which stores all changes to the managed objects, has a listener for two possible events: A new modification is executed; and the "current" state is moved somewhere else (e.g. undoing something.) My replication listener does not support undo right now, because I haven't figured out how to best identify a state (which is where the program is going) yet, but that should be easy. The other thing, executing modifications, does work. That means, whenever a modification is executed locally, it is sent over the network so that the partner(s) can execute it too.

The only downside is that the partners also "execute it locally", so I had to use a trick to suppress resending these received modifications. And it works pretty well:

//initialization code
final History h = createHistory(createKey("test-history"));
final JChannel channel = new JGroupsReplicationListener(h) {
    @Override
    public void receive(Message msg) {
        Modification m = (Modification) deserialize(msg.getBuffer());
        if(m instanceof Creation) id = ((Creation) m).getId();
        super.receive(msg);
    }
}.getChannel();


//executing the actions (creating an object)
h.pushHistoryForThread();
try {
    TestBean t = (TestBean) h.getObjectStore().get(Creation.create(new TestBean()));
    t.setA(1);
    t.setB(1);
} finally {
    h.popHistoryForThread();
}


//printing the results
System.out.printf("current state: %s%n", h.getObjectStore().get(id));



I made this test a GUI application so that I can control the timing on multiple virtual machines. The public void receive(Message msg)seen above is only needed for this Test, again. It's not necessary to do something like that to get the replication. The code in the middle looks exactly the same as the example last time, except I haven't hidden some of the details in a setTest() method.

Now what's probably the most interesting is how the networking works; let me tell you, I didn't write any! As hinted by me before, and in the title of course, is that I have tried JGroups to do this. In JGroups, you create Channels and let them join into a cluster; all channels in the cluster can receive and send messages, either to only only one recipient, or to all at the same time. JGroups provides a configurable protocol stack that takes care of reliability, synchronity and such things. For my tests, I have used a UDP-based protocol stack. For wide-area connections, a TCP-based approach is probably easier.

Thursday, January 5, 2012

Replicating Game States - Working code!

Before you get too excited - no, there's no multiplayer yet (well, who would have guessed that...). There is, however, working code for undoing and redoing actions (even with multiple, branching histories), and even for replicating the state on multiple virtual machines.

The key to make such a library is that it looks like ordinary Java code from the outside, so that others can use your code without wondering why it looks so weird. Let's take a look:

//Test t = new Test(); is an attribute

//replaced angle with square brackets because of HTML markup
List[StateStamp] states = new ArrayList[StateStamp]();
History h = createHistory(createKey("test"));
h.pushHistoryForThread();
try {

    states.add(h.getCurrentState()); // 0
    print();

    setTest(t);
    states.add(h.getCurrentState()); // 1
    print();

    getTest().setA(1);
    states.add(h.getCurrentState()); // 2
    print();

    getTest().setB(1);
    states.add(h.getCurrentState()); // 3
    print();

    Deletion.delete(getTest());
    states.add(h.getCurrentState()); // 4
    print();

    h.goToState(states.get(3));
    print();
    h.goToState(states.get(2));
    print();
    h.goToState(states.get(1));
    print();
    h.goToState(states.get(0));
    print();
} finally {
    h.popHistoryForThread();
}



It's probably easy to to guess that print(); prints the current state of the test object. Besides that, the only code that looks different from normal operations is marked in bold. Most of it is only necessary for this test case: storing the previous states so that you can go back. Really mandatory is only the colored code (and the actual functional code of course, but that doesn't count.)

Of course, a history for the modifications must be created. Then, the history is set for the thread: Code running in the thread (that is, everything in this method, and nothing more) can access the history without passing it as a parameter (which would make using the library awkward) or declaring it as a static variable somewhere (which is ugly from an architecture standpoint.) Everything after this is wrapped in try/finally, so that the last method is not skipped in case of an exception: this removes the association of the history with the current Thread.

Of course, implementing setTest(), setA() etc. is different from a usual simple setter. But the point here is that using the code is as simple as shown here. The result is this:

Test@732A54F9[a=0, b=0] not in store
Test@7A6D084B[a=0, b=0] in store
Test@7A6D084B[a=1, b=0] in store
Test@7A6D084B[a=1, b=1] in store
Test@7A6D084B[a=1, b=1] not in store
Test@15301ED8[a=1, b=1] in store
Test@15301ED8[a=1, b=0] in store
Test@15301ED8[a=0, b=0] in store
Test@15301ED8[a=0, b=0] not in store


You see here how the test object runs through different states up to its deletion, then goes back to its initial state. What's not shown here, but is working, is adding another branch to this history. Of course, the actual objects have only one state at a time, but the history can be switched arbitrarily between multiple histories:


This is the actual test case I ran: I went back to the state after creating the test object, changed its a value, and then switched over to the state before, and then after, deleting the test again.

I have code for replication of states going, but it's not yet as clean as for undo: a lot of handling is necessary for the network, which should be transparent to the user. I'll show it once I'm finished, but in the meantime you can look here.

Sunday, January 1, 2012

Quantum Mechanics and Magic AI

Okay, the title is kind of a stretch, but Quantum Mechanics sounds so much cooler than probability...

So what do I want to talk about? One thought that I often have is that the computer has the advantage of perfect memory. If it once views your hand, it can perfectly memorize all the cards in it. It follows that it can say that as long as a card doesn't leave your hand, you still have it in hand. But when the game progresses, things get more vague: You shuffle cards into your library without revealing them before. Here, probability comes into play.

I assume that the computer knows my deck list for simplicity. (It could even use heuristics to guess what cards might be in your deck, but that only complicates the matter.) At the beginning of the game, before even drawing your opening hand, each card in the library has an equal chance of being one of the, say, 60 cards in your deck. For example, in your mono green deck, a card has a 24 in 60 chance of being a forest. These chances don't change as you draw seven cards, at least from the computer's point of view. Even so, the computer can say that the probability of you having a Giant Growth in hand is (# Giant Growth in deck)/(# cards in deck)*(# cards in hand), and it can have "fear" that you might play that card during combat. The greater the probability, the greater the fear.

Now comes the "collapse of the wave function": the computer observes the cards in your hand. (You see, I can even use QM terminology here ;)) Suddenly, the probability of every of the cards in your hand becomes 100% for the card the AI has observed. Technically, as the hand is not a sorted zone, the AI should not remember which card is which. Let's say you have 4 different cards in hand, then the AI can assume that every of the cards has a 25% probability of being any of these cards.

When you now shuffle one card back into your library, nothing really changes, except that there's only 3 cards for a total of 75% per previously observed card.

I hope that it's clear what I'm saying. I have the feeling to make too many words about a simple concept, yet at the same time I feel that all this seems abstract and not very understandable... well, I should have made some images, but I'm too lazy...

Let me end with this: Magic is a game of uncertainty, and luckily the computer has the capabilities to process these. When an AI can make decisions based on what it sees, why not on what it doesn't see? Assigning these possibilities is pretty simple; every card in the game has a total of 100% of being some card from the deck list, and every card in the deck list is represented to 100% among all cards in the game.
The problem is to design the AI to use that information; it's often hard enough to process the known information, so even more the unknown. But in principle, there's no difference. And even if it is too hard, there are some shortcuts: If you have only one Morph card and play a Morph card, the AI knows which it is, even though it's face down. Such probability collapses can happen all the time, and it would be a waste to let them go unconsidered.