After reading a blog post about some of the quirks of the Java compiler and JVM, I thought I'd perform a magic trick for my colleagues to see how familiar they were with the same quirks.
The Trick
I have two hats and one ball. The ball looks like this:
Ball.java
public class Ball {
public static final String UNDER_HAT = "NONE";
}
The first hat looks like this:
HatOne.java
public class HatOne {
public boolean hasBall() {
return "ONE".equals(Ball.UNDER_HAT);
}
}
The second hat looks like this:
HatTwo.java
public class HatTwo {
public boolean hasBall() {
return "TWO".equals(Ball.UNDER_HAT);
}
}
The magic trick looks like this:
MagicTrick.java
public class MagicTrick {
public static void main(String... args) {
HatOne hatOne = new HatOne();
HatTwo hatTwo = new HatTwo();
if (hatOne.hasBall() && hatTwo.hasBall())
System.out.println("TADA!! The ball is under both hats!");
else if (hatOne.hasBall())
System.out.println("The ball is under hat one.");
else if (hatTwo.hasBall())
System.out.println("The ball is under hat two.");
else
System.out.println("Better luck next time.");
}
}
For this trick, I am not allowed to modify MagicTrick.java, HatOne.java or HatTwo.java, but I am allowed to change the implementation of Ball.java as much as I like. After making secret changes to Ball.java, I execute the magic trick:
$ java MagicTrick TADA!! The ball is under both hats!
How did I do it?
The Solution
If you consider yourself a seasoned Java developer, I suggest you have a go at finding a solution before reading this section, it will be fun. I expected that a number of my colleagues would work out how I did it, but what I didn't expect is that they would come up with 4 completely different ways of performing the trick.
Initially a solution was suggested that involved changing the package of some of the classes, but that meant editing the files, so that didn't count. Then a really simple solution arose that I hadn't thought of. It was suggested by Tom Davies, though with one small bug, which was fixed by Chris Mountford:
public class Ball {
static {
System.out.println("TADA!! The ball is under both hats!");
System.exit(0);
}
public static String UNDER_HAT = "NONE";
}
Well, that was too easy, so I changed the rules to say that the only class that was allowed to print any output was MagicTrick.java. Then came the solution that I was looking for, suggested by both Charles Miller and Chris Kiehl. It was:
- Compile all classes
- Modify Ball.java so UNDER_HAT="ONE"
- Compile Ball.java and HatOne.java
- Modify Ball.java so UNDER_HAT="TWO"
- Compile Ball.java and HatTwo.java
- Run MagicTrick - TADA!!
This solution exploits the way the Java compiler inlines static final fields wherever it can. The next solution, proposed by Chris Mountford, I thought someone might try. I don't think a magician would be very wise though to use this solution, it is greatly dependent on the speed of the processor, the OS scheduler, and whatever else the system happens to be doing at the same time:
public class Ball {
public static String UNDER_HAT = foo();
static String foo() {
Thread changer = new Thread() {
public void run() {
UNDER_HAT= "TWO";
}
};
changer.start();
try {
Thread.sleep(94);
}
catch (InterruptedException e) {
throw new RuntimeException(e);
}
return "ONE";
}
}
I thought that had to be all the solutions that would arise. But then, Matt Quail, a magician with a deep knowledge of the implementation of the String class and the way the JVM handles String literals, came up with this very elegant solution:
import java.lang.reflect.Field;
public class Ball {
public static Object UNDER_HAT;
static {
try {
new HatTwo().hasBall();
Field fValue = String.class.getDeclaredField("value");
fValue.setAccessible(true);
Field fOffset = String.class.getDeclaredField("offset");
fOffset.setAccessible(true);
Field fCount = String.class.getDeclaredField("count");
fCount.setAccessible(true);
String internedOne = "ONE";
String internedTwo = "TWO";
char[] none = {'N', 'O', 'N', 'E'};
UNDER_HAT = new String(none);
fValue.set(internedOne, none);
fOffset.setInt(internedOne, 0);
fCount.setInt(internedOne, 4);
fValue.set(internedTwo, none);
fOffset.setInt(internedTwo, 0);
fCount.setInt(internedTwo, 4);
} catch (Exception e) {
e.printStackTrace();
}
}
}
This solution exploits the way the JVM interns String literals, and changes the interned value of the String literals in the HatOne and HatTwo classes. Finally, I tried my hand at a solution that involved messing with class loaders:
import java.io.*;
public class Ball {
public static String UNDER_HAT = "ONE";
private static final String HAT_TWO = "cafebabe00000032000f0a0003000c07000d07000e0100063c696e69743e010003282956010004436f646501000f4c696e654e756d6265725461626c6501000768617342616c6c01000328295a01000a536f7572636546696c6501000b48617454776f2e6a6176610c0004000501000648617454776f0100106a6176612f6c616e672f4f626a656374002100020003000000000002000100040005000100060000001d00010001000000052ab70001b100000001000700000006000100000001000100080009000100060000001a000100010000000204ac000000010007000000060001000000010001000a00000002000b";
static {
try {
MagicTrickClassLoader mtcl = new MagicTrickClassLoader();
Class magicTrickClass = mtcl.loadClass("MagicTrick");
magicTrickClass.getMethod("main", new Class[] { String[].class })
.invoke(null, new Object[] { new String[] {} });
System.exit(0);
} catch (Exception e) {
}
}
private static class MagicTrickClassLoader extends ClassLoader {
public Class loadClass(String name) throws ClassNotFoundException {
if ("MagicTrick".equals(name)) {
try {
ByteArrayOutputStream os = new ByteArrayOutputStream();
FileInputStream is = new FileInputStream(new File(
getClass().getResource(name + ".class").toURI()));
int b = is.read();
while (b >= 0) {
os..write(b);
b = is.read();
}
is.close();
byte[] bytes = os.toByteArray();
return super.defineClass(name, bytes, 0, bytes.length);
} catch (Exception e) {
}
} else if (name.matches("HatTwo")) {
byte[] bytes = new byte[HAT_TWO.length() / 2];
for (int i = 0; i < HAT_TWO.length(); i += 2) {
bytes[i / 2] = (byte) Integer.parseInt(HAT_TWO.substring(i, i + 2), 16);
}
return super.defineClass(name, bytes, 0, bytes.length);
}
return super.loadClass(name);
}
}
}
Initially embedding Java byte code in a Java source file felt a bit hairy to me, so I implemented it using the javax.tools API, but that required creating temporary directories and the like, this solution ended up being simpler (if you count less lines of code as being simpler). So, have we exhausted all the ways to perform this magic trick?
9 Comment(s)
http://java.sun.com/javase/6/docs/api/java/lang/instrument/ClassFileTransformer.html
Transform java.lang.String.equals so that when invoked for a magic value, it checks the caller from stack, and responds as specified.
By Mikael Gueck at July 31, 2008 7:05 PM
I'm not sure that method will work without loading a Java agent (eg, java -javaagent:agent.jar). Doing that would give the magic trick away when executed. If you don't use a Java agent, then there is no way that I'm aware of to get a hold of an instance of an Instrumentation class, which means you can't add your ClassFileTransformer. Additionally, I thought Instrumentation.isModifiable(String.class) returned false, because the JVM won't let you modify class in the java.* package. However, you could transform the HatOne and HatTwo classes to always return true from hasBall.
By James Roper at July 31, 2008 7:25 PM
@James Roper -- you can load an instrumentation agent at runtime.. read how
By peter royal at July 31, 2008 9:31 PM
A fifth (sixth?) solution that doesn't even require modifying the Ball: http://www.papercut.com/blog/tom/2008/08/01/java-magic-trick-the-ball-is-everywhere/
By Tom Clift at August 1, 2008 2:07 AM
Great Puzzle James, but you are neglecting giving constraints.
Okay, your constraint is that the MagicTrick.java has to do the output.
If that is the only constraint I would make "java" a batch/shell on the path, which would for example put my custom classloader as a system property via "java.system.class.loader"
Then I could load custom Hat classes.
Also this could solve the javaagent command line option.
I guess you can always find a trick to make your own script/executable run instead of the original java one, doing any setup, bytecode modification you like.
Sure it misses the point of being a Java Trick, but that the kind of cheating magicians do :-)
By Fabian Lange at August 1, 2008 4:47 AM
I did consider making it so the only thing you could change was the value of UNDER_HAT, that would have eliminated a number of solutions because then a static block couldn't be placed inside Ball.java because it would never be initialised, due to the fact that UNDER_HAT is static final. But the good thing about having rules that aren't so strict is it increases the scope of creativity.
By James Roper at August 2, 2008 7:21 AM
If you changed the value of UNDER_HAT to be the return value of a static method (which could do the required meddling), would that still fall within the constraint?
By Chris Leggatt at August 5, 2008 10:35 PM
@Chris Leggatt
No, because Java inlines the result of the static method at compile time. That static method is only called once...
By Kit at August 6, 2008 8:14 PM
@Kit
Regardless of whether the static method is inlined or not, if it's used to initialise a static member it's only going to be used once to initialise that static particular static member.
What I was referring to was that while creating a static method that returns the value of "NONE" (while also changing the internal char array of the Strings "ONE" and "TWO" to be {'N', 'O', 'N', 'E'}) and assigning that to UNDER_HAT works, I was wondering whether this would violate the proposed constraint of "the only thing you could change was the value of UNDER_HAT". Technically, you still only changing the value of UNDER_HAT after all...
By Chris Leggatt at August 12, 2008 5:51 PM