tr ouwens

by the way: things I want to say

Generics in EqualsVerifier, part 1: Overcoming type erasure

This is part 1 of a two-part series. This part deals with overcoming type erasure. In Part 2, we will see what EqualsVerifier can do with this generic type information.

Introduction

Since version 2.0, EqualsVerifier is aware of generics. For instance, it can determine, at runtime, whether a class’s field is a List<String> or a List<Integer>. However, type erasure says this is impossible! If we call getClass() on a list instance, we’ll get a List.class object, which is unaware of the generic paramter. How does EqualsVerifier do this?

Some background

EqualsVerifier works by creating instances of objects, filling their fields with carefully chosen values, and repeatedly calling equals on them to see if something unexpected comes up. However, type erasure causes problems. Say we have the following class:

class ListContainer {
    private final List<String> list;
}

EqualsVerifier can see that this class has a field list of type List. Versions below 2.0 don’t know anything more than that: they can’t determine that it’s really a List<String>, because the generics get erased by the JVM. To work around this, EqualsVerifier simply instantiates a raw List, puts in a few values of type Object, and hopes nobody notices.

In most cases this works perfectly fine, because in most cases, an equals method will just call list.equals(other.list). List’s equals method then simply calls equals on each of its values and it doesn’t matter what the type of these values is. After all, every Java class has an equals method that you can call.

In a small number of cases, this doesn’t work. For example, Android has a type called SparseArray. It’s a generic type that contains a sequence of values, like an array or a list. However, unlike arrays and lists, it doesn’t implement its own equals method. Calling equals on a SparseArray is like calling == on it: it doesn’t matter if two SparseArrays contain exactly the same elements; if they’re not the same instance, they’re not equal. This means that a class with a SparseArray field, has to ‘unwrap’ it in equals:

public class SparseArrayContainer {
    private final SparseArray<String> sparseArray;
    
    // ...
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof SparseArrayContainer)) {
            return false;
        }
        SparseArrayContainer other = (SparseArrayContainer)obj;
        for (int i = 0; i < sparseArray.size(); i++) {
            String a = sparseArray.get(i);
            String b = other.sparseArray.get(i);
            if (!a.equals(b)) {
                return false;
            }
        }
        return true;
    }
}

Now, we get a ClassCastException in the line that assigns an element of sparseArray to a: a expects a String, but it gets an Object. Oops.

Because the generic type is erased at runtime, there’s no way around this issue. Or is there?

There is!

While it’s true for objects at runtime that their generic type gets erased, there is something we can use. In EqualsVerifier, we’re always inspecting a class and its fields, and it turns out that Java does retain the fully generic type of all fields in a class. You can use reflection to access this information. So, for our SparseArrayContainer, we can do this:

Field f = SparseArrayContainer.class.getDeclaredField("sparseArray");
Type type = f.getGenericType();
if (type instanceof ParameterizedType) {
    ParameterizedType pt = (ParameterizedType)type;
    Type[] genericTypes = pt.getActualTypeArguments();
} 

The type variable has type java.lang.reflect.Type, which is an interface with several impementations. The most important implementation, and also the easiest, is good old java.lang.Class. However, our sparseArray field is parameterized, so we’ll get an instance of ParameterizedType.

On a ParameterizedType (don’t forget to cast first; java.lang.reflect.Type doesn’t declare a lot of useful methods by itself), we can call a getActualTypeArguments() method, which gives us an array of Type. The elements of this array are instances of java.lang.Class. (As said before, java.lang.Class implements the java.lang.reflect.Type interface). In other words, genericTypes[0].equals(String.class). Yay! We have the generic type we want. The rest is just an exercise of filling in the blanks.

It turns out, there’s a lot of blanks to fill in.

TypeTag

First, we need to be able to pass around our new generic type information, where EqualsVerifier used to just pass around a java.lang.Class. java.lang.reflect.Type has all the information we need, but it’s very unwieldy. Time then to build our own container: TypeTag. It looks something like this:

public final class TypeTag {
    private final Class<?> type;
    private final List<TypeTag> genericTypes;

    public TypeTag(Field field) { ... }
    
    // Getters, equals, hashCode left out for brevity.
}

In order to construct an instance, we’ll need a java.lang.reflect.Field, because as we said before, we need that to access the generic types. (There are other ways to get them; for example, if we can make a subclass of a type and instantiate that, we can use that to instance to find the generic types. However, sometimes types are final and in those cases, making a subclass is impossible. Using a field is much more reliable.)

It does mean that we can’t get the generic types at the top of the chain, though. Say we have the following class:

public final class Entity<I extends Comparable> {
    private final I id;
    
    // Constructor, getters, equals, hashCode left out for brevity.
}

There is no way to figure out that Entity has a generic type parameter I extends Comparable<I> if we only have an instance of Entity. Fortunately, this problem is not as big as it seems, because in all cases, we only need to know the type parameter when it’s used. And when the type parameter is used, it’s used in a field. And we can get at the type parameters of fields!

However, we’re not done yet. Apart from java.lang.Class and java.lang.reflect.ParameterizedType, our java.lang.reflect.Type interface has a bunch more implementations, and we need to consider each one.

TypeVariable

Consider once again the Entity class above. When we have a java.lang.reflect.Field instance of its id field, we will get an instance of java.lang.reflect.TypeVariable, which is another implementation of the java.lang.reflect.Type interface. This gives us the name (in this case a String "I") and its bounds (Comparable<I>, wrapped in some other instance of java.lang.reflect.Type). The bounds are important, because we can’t assign a java.lang.Object to id, because that’s not Comparable. Note that type variables can be bound to concrete classes (T extends Object), but also to other type variables (T extends U), which complicates matters. To make things even worse, bounds are often even recursive: T extends Comparable<T>!

And it gets more complicated. Consider the following (not even very contrived) example:

public interface Period { }
public final class Per<T extends Comparable<T>, P extends Period> {
    private final P period;
    private final T value;
    
    // Constructor, getters, equals, hashCode left out for brevity.
}

When we evaluate the types of period and value, we’ll have to match them up with Per’s generic parameters. Note that I switched the order around, to emphasize that we can’t simply say that the first field we encounter in the class will match with the first generic parameter, and the second field with the second generic parameter. No, we’ll have to match the field’s type’s name with the generic parameter’s name.

Fortunately, there is one thing we can get from a raw java.lang.Class object: the java.lang.reflect.TypeVariables it was declared with. Per.class.getTypeParameters() returns an array of TypeVariable.

So, if we want to determine the precise type of Per’s value field, we need value’s corresponding java.lang.reflect.Field, and Per’s TypeVariable. We’ll call the Per class value’s enclosing class. We’ll put Per’s TypeVariables in a hash map, keyed on the names of the type variables, so we can more easily match them with the types of the fields.

Other implementations of the Type interface

The next java.lang.reflect.Type implementation we have to consider is the wildcard, which can also have bounds. Fortunately, the wildcard only occurs on fields, not on classes, so it’s a bit easier:

private final List<? extends Point> points;

We can safely substitute a boundless wildcard with java.lang.Object, and a bounded wildcard with the bound itself. In the case of the List<? extends Point> above, we can simply pretend it’s a List<Point>. Note that wildcards, as opposed to TypeVariables, can have upper (? extends SomeType) and lower (? super SomeType) bounds. Fortunately, we can treat them the same in this case.

Finally, there’s the GenericArrayType. Fortunately, that one is pretty straightforward compared to the rest. We’ll not look at it in detail.

What do we have now?

All this effort allows us to determine the complete type of any field, and take from that the information that is relevant to EqualsVerifier. For example, take this class:

public class Container<T extends Comparable<T>> {
    private final List<String> a;
    private final Map<String, List<Integer>> b;
    private final List<T> c;
    private final List<?> d;
    private final List<? super Class> e;
    private final T[] f;
}

This gives us the following TypeTags for its fields:

TypeTag(List, TypeTag(String))
TypeTag(Map, TypeTag(String), TypeTag(List, TypeTag(Integer)))
TypeTag(List, TypeTag(Comparable))
TypeTag(List, TypeTag(Object))
TypeTag(List, TypeTag(Class))
TypeTag(Comparable[])

TypeTag has a factory method that takes a java.lang.reflect.Field and another TypeTag that represents the enclosing type, which we need to resolve TypeVariables like T. Then it determines what kind of java.lang.reflect.Type the field is, and recursively resolves it. You can look at the implementation here.

A caveat

You might have noticed that I haven’t discussed multiple bounds, like T extends Interface1 & Interface2, which are also allowed in Java generics. In all honesty, I only thought of them while researching this article. EqualsVerifier 2.0 has been out for several months by now, so I suppose these multiple bounds aren’t used often enough for people to have run into this. Nevertheless, it’s obviously quite high on my list of future improvements.

Summary

We have seen how we can determine the full, generic type of a class’s field. In Part 2, we will see how we can put this information to good use.

Get to grips with your build, with Gradle

Last month, the Dutch Java Magazine published an article written by Hanno Embregts and myself. In it, we describe how we used Gradle in our project at the Dutch Railways.

It’s a big, monolithic project with ± 25.000 lines of Ant scripts, which we wanted to break up into separate components that can be built and released separately. Doing this with Ant would add more complexity to an already much too complex system of scripts. Maven wasn’t a good fit either, because being built with Ant since its inception, our project didn’t follow Maven’s conventions, and shoe-horning it into these conventions would be impractical. Gradle provided the right mix of structure and flexibility.

We started our migration on a small subcomponent with no dependencies to other parts of our codebase, to work our way up. That way we wouldn’t have to deal with deploying the moving target of our project, which was actively in development during the migration, into Nexus so our Gradle scripts could consume it. We tried it; it didn’t work. It’s much easier to go the other way round, to consume artifacts from Nexus that were already migrated to Gradle and put under a strict regimen of Semantic Versioning.

Still, our existing Ant scripts needed to deal with our new Gradle-built artifacts. We decided it would treat these like any other 3rd party dependency, which worked fine for the most part. However, we found we had to be careful that the content of artifacts was identical to the ones built by the original Ant scripts, especially in the case of MANIFEST.MF files and various kinds of XML files embedded in the JARs. We had tools to test this, and we even went so far as to change Gradle’s unit test output layout to match that of Ant, so we could compare those easily using a diff viewer.

In the end, we were very happy with the result, even if it took more effort than we expected initially. If you want to know more about the reasoning behind some of the choices we made, or how we solved some of the other issues we ran into, you can read the full article in the physical magazine, or you can read it online. Note: it’s in Dutch.

Foobal, Moneyball

Ever since Moneyball came out, winning at sports using statistics has become more and more mainstream. As I’ve blogged before, I have also been getting in on some of that action: I’ve been competing in my family’s soccer match betting game, where we guess the results of NAC Breda, our favourite team. But instead of predicting the outcomes myself, I’m using Foobal, a little Scala program that I’ve written for this very purpose.

And, like the Oakland A’s, FC Midtjylland and Brentford FC, this has not been without success: I won this year’s pool! And by quite some margin, too. Here’s the trophy:

Trophy

On the last few lines, it says J10 anO15 which really should have been 2015 JanO. I guess the thick black line got in the way :). I’ll keep it until next year, when I pass it on to the next winner.

Anyway, Foobal probably did so well because NAC has been playing very, err… consistently this season. Sadly, due to this consistency, NAC were also relegated from the Honor Division to the First Division. I must say, it’s sad to win the pool under such sad circumstances. To Foobal’s moral credit, though, it did predict a win for the final and deciding match, which was lost during extra time.

The relegation also means that next year, NAC will have to face many teams that Foobal does not have data on. This will be quite a challenge, but it gives me a good opportunity to tweak the algorithm a bit and see if I can come up with something even more successful. I’m only getting started!

Hacking Java enums

The other day, I was debugging some enum related code in EqualsVerifier. I had this enum:

enum CallMe { YES, NO, MAYBE }

And two variables, original and clone, containing a value of said enum. Here’s what the bug looked like in Eclipse’s debugger:

Call Me Maybe

So, what do we see here? We see two variables of type EnumHack$CallMe (the enum was an inner class, so that makes sense). Both enums have the same name and ordinal, so they are equal. They also have different ids (33 and 34, respectively), so they’re not the same object.

Wait, what!?

That’s right: two different instances of the same enum constant. In other words, original.equals(clone) returns false, even though both variables are set to CallMe.MAYBE. How is that even possible? I thought it wasn’t. In the words of Joshua Bloch:

This approach [of using a one-element enum to implement a singleton, JO] provides an ironclad guarantee against multiple instantiation, even in the face of sophisticated serialization or reflection attacks.

The Java Language Specification, section 8.9 says this:

An enum type has no instances other than those defined by its enum constants. It is a compile-time error to attempt to explicitly instantiate an enum type (§15.9.1).

The final clone method in Enum ensures that enum constants can never be cloned, and the special treatment by the serialization mechanism ensures that duplicate instances are never created as a result of deserialization. Reflective instantiation of enum types is prohibited. Together, these four things ensure that no instances of an enum type exist beyond those defined by the enum constants.

Clearly, despite the fact that an enum constant can never be cloned, I had a clone on my hands.

So what happened? I traced the problem back to this:

@Test
public void hackAnEnum() throws Exception {
    CallMe original = CallMe.MAYBE;
    CallMe clone = ObjectAccessor.of(original).copy();
    
    assertEquals(original.name(), clone.name());
    assertEquals(original.ordinal(), clone.ordinal());
    assertFalse(original.equals(clone));
    assertFalse(original == clone);
}

I added the asserts so you can see for yourself what’s going on: if you copy/paste this to your IDE and put EqualsVerifier on the classpath, you’ll be able to run it. This test passes, which means that both original.equals(clone) and original == clone are, indeed, false.

So what does this ObjectAccessor do? It’s part of EqualsVerifier’s reflection library, and as you probably guessed, it makes a copy of the given object. If I factor out all EqualsVerifier code, I end up with this:

CallMe clone = new ObjenesisStd().newInstance(CallMe.class);
for (Field f : Enum.class.getDeclaredFields()) {
    f.setAccessible(true);
    f.set(clone, f.get(original));
}

Apart from the reference to ObjenesisStd, this is all standard Java reflection code. So, what is this Objenesis thing, then? From their website:

Objenesis is a small Java library that serves one purpose: To instantiate a new object of a particular class.

In other words, it can instantiate any object, without calling its constructor. So how does Objenesis work, exactly? Well, that depends. It uses the Strategy pattern to choose from several different ways of instantiating objects, depending on what kind of JVM you’re running, and probably some other factors, too. In my case, it expanded to this:

Constructor<Object> objectConstructor =
    Object.class.getConstructor((Class[]) null);
Class<?> reflectionFactoryClass =
    Class.forName("sun.reflect.ReflectionFactory");
Method method = reflectionFactoryClass.getDeclaredMethod("getReflectionFactory");
Object reflectionFactory = method.invoke(null);
Method newConstructorForSerializationMethod =
    reflectionFactoryClass.getDeclaredMethod("newConstructorForSerialization", Class.class, Constructor.class);
Constructor<CallMe> ctr = (Constructor<CallMe>)
    newConstructorForSerializationMethod.invoke(reflectionFactory, CallMe.class, objectConstructor);
CallMe clone = ctr.newInstance((Object[]) null);

That’s some incredibly hairy scary code. Let’s pretend we never saw this. The only thing we need to remember is that all this can be done without resorting to actually changing the bytecode at runtime; it’s all reflection.

While Objenesis maybe a relatively unknown library, it is actually pretty widely used. The most famous libraries that use it are Mockito (and basically all mocking frameworks), and Spring Framework. But there are more. Many more. EqualsVerifier uses it to instantiate values for the fields of the class it’s testing.

OK, now we that know this, can we go one further? It turns out we can:

Call Me Sometime

We can add our own enum constants. Here’s how:

CallMe sometime = new ObjenesisStd().newInstance(CallMe.class);
Field ordinal = Enum.class.getDeclaredField("ordinal");
ordinal.setAccessible(true);
ordinal.set(sometime, 4);
Field name = Enum.class.getDeclaredField("name");
name.setAccessible(true);
name.set(sometime, "SOMETIME");

It’s actually pretty simple. I guess the JVM’s guarantees aren’t ironclad enough for this particular sophisticated reflection attack. And to think I actually found it by accident! I fixed the bug in EqualsVerifier before it ever got released into production, so all’s well that ends well, I guess.

P.S. Oh and don’t try this at home kids! …or at least, not in production.

Configuring my NAS

The other day, I had to re-install my NAS, and of course, I’d forgotten exactly how I had configured it. That meant finding back lots of websites, some of which apparently didn’t exist anymore. This time, I’ve written down all the steps I’ve taken, just in case, for some sad, unforeseen reason, I ever have to do it again.

What do I want from my NAS? Not much, actually:

  • I want it to store my files (duh)
  • I want to use an rsync script to copy my photos to my NAS
  • I want filenames with special characters (éüå) to be treated sanely by said rsync script
  • I want it to run CrashPlan so all my data is automatically backed up to the cloud

I don’t need it to be a media server; I have Spotify and Netflix for that.

My NAS is a Synology DS213j running DSM 5.1.

Starting out

After choosing a server name, a user name and a password, make sure to first install all the updates from the Control Panel. Add the user account to the administrators group, then disable admin and guest account. Next, create a shared folder: in File Station, click Create, Create New Shared Folder. Give it a name and click OK. Give your user Read/Write permissions to the folder.

Set up SSH

Once the preliminaries are out of the way, you can set up SSH, which is needed for rsync.

  • Go to Control Panel, “Terminal & SNMP” and check “Enable SSH service”
  • Go to Control Panel, User, Advanced, and check “Enable user home service”. This is needed to be able to log in as a different user than root later.

You now have root SSH access though the Admin account. (You disabled that account earlier, but root is still active, and its password is the same as the NAS’s admin account’s password.) Let’s try it from the command-line: ssh root@diskstation. You have to type ‘yes’, then the admin password, and you’re in. Nice.

You want to be able to log in using the new user account you defined earlier. From a root SSH session:

  • Open /etc/passwd with vi.
  • Find the line for your user, and at the end of that line, replace /sbin/nologin with /bin/sh.
  • Run chmod u+s /bin/busybox, or else you won’t be able to gain root access later. (You’ll get errors like “must be suid to work properly” when you try to run su.) In fact, I’ve lost root once after an update because the permissions of this file were reset, so I invite you to add it to the crontab as well:
  • vi /etc/crontab, then add the line 0 0 * * * root chmod u+s /bin/busybox. That will restore the permission every day at midnight.
  • Restart the diskstation to make sure that the new crontab is loaded. You may want to test this to convince yourself it works, before you proceed, because if something goes wrong, you’ll be locked out of your NAS.

Now, you really should disable direct root access. Perform the following steps carefully, or you might get locked out of root forever.

  • vi /etc/ssh/sshd_config and change the line #PermitRootLogin yes to PermitRootLogin no.
  • Let’s also change #MaxAuthTries 6 to MaxAuthTries 3.

If you want to beef up security a bit more with SSH keys, read this article.

Enable special characters

Not all Synology diskstations support UTF-8 on the terminal, which is where you want to run rsync. So if you have files or folders with non-ASCII characters in them, you may want to make sure that your diskstation does support them, or else you’ll run into trouble later.

SSH into your diskstation and type locale. If it looks like this, you’re good:

LANG=en_US.utf8
LC_CTYPE="en_US.utf8"
LC_NUMERIC="en_US.utf8"
LC_TIME="en_US.utf8"
LC_COLLATE="en_US.utf8"
LC_MONETARY="en_US.utf8"
LC_MESSAGES="en_US.utf8"
LC_PAPER="en_US.utf8"
LC_NAME="en_US.utf8"
LC_ADDRESS="en_US.utf8"
LC_TELEPHONE="en_US.utf8"
LC_MEASUREMENT="en_US.utf8"
LC_IDENTIFICATION="en_US.utf8"
LC_ALL=en_US.utf8

I.e., en_US.utf8 should be everywhere. If it’s not, go to this blog post and follow the instructions to fix it. It’s a bit of work, but it’s worth it, I promise.

Enable rsync

  • Go to the diskstation’s main menu and start the app “Backup & Replication”.
  • Go to the Backup Services tab.
  • Check “Enable network backup service”.
  • Click Apply.

Now you can rsync from the pc to the NAS like this (assuming your shared folder is called documents):

rsync --delete -av --exclude ".DS_Store" --exclude ".fseventsd"
      --exclude ".Spotlight-V100" --exclude ".TemporaryItems"
      --exclude ".Trashes" --exclude "@eaDir"
      /some/directory/ user_name@diskstation:/volume1/documents

Install CrashPlan

  • Open the Package Center’s Settings, and change the Trust Level to “Any publisher”.
  • Just follow Scott Hanselman’s instructions. He explains it much better than I could. Note that, if you’re on a Mac, CrashPlan’s configuration file can be found in /Applications/CrashPlan.app/Content/Resources/Java/conf/ui.properties

The CrashPlan client prevents the diskstation from going into hibernation mode. Therefore, it may be a good idea to schedule it to run only for a few hours a day. Log in via SSH and gain root via su. Then vi /etc/crontab and add the following two lines:

0 1 * * * root /var/packages/CrashPlan/scripts/start-stop-status start
0 5 * * * root /var/packages/CrashPlan/scripts/start-stop-status stop

That starts up the service at 01:00 and shuts it back down at 05:00.

Wrapping up

Restart the diskstation one final time, to make sure all settings have taken effect.

That’s it! We’re done.