kirlich’s blog

Where is the ball?

27Dec08

Recently I’ve stumbled uppon the Magic Trick In Java article, where Atlassian developer James Roper sets up a magic trick in Java for his colleagues. So as he suggested (and I suggest you the same), I first went to find my own solution to the problem, to do my own “magic”. After I came up with one, I went to check their solutions, and as much as James was surprised with the number of different solutions, I was surprised that mine was different than others (even there is one similar solution but mine goes step further, and is simpler).

Instead of posting it as comment there, I’ve decided to write a post and back it up with some explanations. This is the very first post on this blog and I hope it will be worth reading.

The Trick

So here is 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?

First I’ll give you my “magic” solution, and then provide step by step explanation. Again I recommend you to first try to make one yourself. Maybe you’ll come up with something different than provided here, or in original Magic Trick In Java article (and its comments).

Solution

 public class Ball {
  public static String UNDER_HAT = "";
  static {
    new HatTwo().hasBall();
    try {
      Field countField = String.class.getDeclaredField("count");
      countField.setAccessible(true);
      countField.set("ONE", 0);
      countField.set("TWO", 0);
    } catch (Exception e) {
      e.printStackTrace();
    }
  }
}

Try it yourself and check the “magic” output.

Whats the magic?

So what’s going on here? How could this affect output in completely different part of code? Well here is how.

Ignore the hasBall() method invocation on HatTwo instance for now. First change is that UNDER_HAT literal is not final anymore. Reason for this is that Java compiler will inline Ball.UNDER_HAT invocations in HatOne and HatTwo hasBall method, if the field is static final. Those are the only two references to Ball class, and if they are inlined at compile time, Ball class will never be loaded. Since we are allowed only to modify Ball class, we have no chance of doing anything in it at runtime, if it is not loaded at all. Note that I said “at runtime”, since you can exploit this compile time inlining to make the trick work, but I leave that to you (or you can check solution, that James had in mind while setting up this trick).

Next change is that we added static initializer. By removing final we ensured that Ball class will be loaded, which gives us the possibility to do some work in static initializer. Let see what “magic” can we do. We need to make the condition:

hatOne.hasBall() && hatTwo.hasBall()

to be true, that is:

"ONE".equals(Ball.UNDER_HAT);
"TWO".equals(Ball.UNDER_HAT);

both to be true. So we need to somehow manipulate those two strings: “ONE” and “TWO” to make them equal to Ball.UNDER_HAT. But there are two problems:

strings are immutable
how can we refer to them from Ball class?

For (1) we can use reflection to access String private field. But first we need reference to those strings, thus we need to to solve (2) first. In order to do so we will exploit the way Java handles string literals. Here is the excerpt from Java Language Specification:

Each string literal is a reference (§4.3) to an instance (§4.3.1, §12.5) of class String (§4.3.3). String objects have a constant value. String literals-or, more generally, strings that are the values of constant expressions (§15.28)-are “interned” so as to share unique instances, using the method String.intern.

So, if we define string literal “ONE” in Ball class, that literal will refer to the same string instance as string literal “ONE” in class HatOne. Analog for string literal “TWO”. I would like to recommend you a very interesting read on this topic at Java Specialists’ Newsletter: Insane Strings which instantly came to my mind when I read setup for Magic Trick In Java.

Mutating Strings

Now that we have a way to get references to string literals “ONE” and “TWO” used in classes HatOne and HatTwo we can use reflection to modify them in order to get desired results. How should they be modified? Well, we could go by setting their underlying char array to {“N”,”O”,”N”,”E”} so that they are equal to original value of UNDER_HAT:

  public static String UNDER_HAT = "NONE";
  static {
    new HatTwo().hasBall();
    try {
      Field countField = String.class.getDeclaredField("value");
      countField.setAccessible(true);
      countField.set("ONE", UNDER_HAT.getCharArray());
      countField.set("TWO", UNDER_HAT.getCharArray());
    } catch (Exception e) {
      e.printStackTrace();
    }
  }

but in that case we also need to set their count field to 4, since obviously two strings are not equal if they “contain” (actually “represent” would be more apropriate term) different number of characters:

      Field countField = String.class.getDeclaredField("count");
      countField.setAccessible(true);
      countField.set("ONE", UNDER_HAT.length());
      countField.set("TWO", UNDER_HAT.length());

or we could avoid this by changing UNDER_HAT to “NON”. Since I wanted for solution to be as simple as possible I used different approach. I’ve only changed count field value to zero because, in that case, String.equals method will not even bother with underlying char arrays. Once String.equal method determines that both strings count field is zero it will return true. So all we need to do is set the count field for strings “ONE”, “TWO”, and UNDER_HAT to zero, and they will be equal (well at least for String.equals method). If there was additional trick constraint that forbids me to change value of UNDER_HAT literal, then I could have done this for UNDER_HAT “NONE” string, but since trick allows me to change Ball class anyway I want I decided to manually change UNDER_HAT to empty string.

public class Ball {
  public static String UNDER_HAT = "";
    .
    .
    Field countField = String.class.getDeclaredField("count");
    countField.setAccessible(true);
    countField.set("ONE", 0);
    countField.set("TWO", 0);
    .
    .
}

Mystery

Finally, we get to that mysterious line:

new HatTwo().hasBall();

Without this line, MagicTrick will print:

“The ball is under hat one.”

How can that be? In the end we changed both string literals, “ONE” and “TWO”, in a same way. We set the value of their count field to 0, but somehow HatTwo.hassBall() returns false, as opposed to HatOne.hasBall(). In order to understand why, lets get back to string literals interning from JLS:

String literals are “interned” so as to share unique instances, using the method String.intern.

And String.intern method javadoc states:

When the intern method is invoked, if the pool already contains a string equal to this String object as determined by the equals(Object) method, then the string from the pool is returned. Otherwise, this String object is added to the pool and a reference to this String object is returned

Now, having this in mind lets examine the expression that we want to satisfy in order to print magic output:

hatOne.hasBall() && hatTwo.hasBall()

So the expression:

"ONE".equals(Ball.UNDER_HAT);

will be executed first. Note that string literal “ONE” will be interned before Ball class is loaded (it is loaded when static reference to UNDER_HAT literal is made). Thus, when string literal “ONE” in Ball class static initializer is interned, it will refer to the same string as string literal in HatOne.hasBall() method. However, in case of expression:

"TWO".equals(Ball.UNDER_HAT);

when string literal “TWO” is interned there is no equal string in string pool (remember that we changed count field of string literal “TWO” in Ball class to zero). So, string literal “TWO” in HatTwo.hasBall() method refers to different string than string literal “TWO” in Ball static initializer. Thus, we need to make sure that string literals from HatOne.hasBall() and HatTwo. hasBall() are interned before we use same literals in Ball static initializer. And that is where the mysterious line

new HatTwo().hasBall();

comes from.

And that’s it. But to keep the game going, I have one for you: If you are allowed to modify MagicTrick class how can you break my solution?

Not so fast… there are some rules. MagicTrick must follow the same logic as the original one, that is:

HatOne.hasBall()	HatTwo.hasBall()	print
true	true	“TADA!! The ball is under both hats!”
true	false	“The ball is under hat one.”
false	true	“The ball is under hat two.”
false	false	“Better luck next time.”

And when you break it, how would you fix my version of Ball class to print magic output again?

Filed under: Java | Leave a Comment
Tags: Java, reflection, string, string intern

Where is the ball?

The Trick

Solution

Whats the magic?

Mutating Strings

Mystery

Recent Entries

Categories

Archives