Posted on

Implementing Spring-like Classpath Scanning in Android

One of the things that Spring 2.5 introduced back in 2007 was component scanning, a feature which removed the need for XML bean configuration and instead allowed developers to declare their beans using Java annotations. Rather than this:

We can do this:

It’s a pretty simple idea since Java makes it very easy to introspectively check a class’s annotations at runtime through its reflection API. Spring’s component scan feature also allows you to specify the base package(s) to scan for beans.

The big question is how do we get access to the classes in the classpath, specifically, those in the desired package? Java SE doesn’t provide an API for doing it, but there are ways to accomplish this. The most common (if not the only) approach is to load classes by relying on the file system. We know that we can use the ClassLoader to load a class by its package-qualified name, so it becomes a matter of retrieving the file names.

Getting the classpath itself in Java SE is easy:

This will yield something that looks like “/Users/Tyler/Workspace/Test/bin:/Users/Tyler/Workspace/Test/lib/gson-2.1.jar”. Loading the files from here is pretty straightforward, as is filtering on the package name since it maps to a directory one-to-one.

Another similar approach is to use the ClassLoader to load the resources directly:

Transition to Android

Unfortunately, these solutions don’t lend themselves to Android, which made implementing classpath scanning a little more difficult for Infinitum. The reason for this is, more or less, because of the way Android’s Dalvik VM is designed. When an Android application is compiled, the Dalvik bytecode is packaged into a file called “classes.dex” inside the APK. The good news is that the Android SDK provides an API for interacting with DEX files through the DexFile class.

In order to access classes.dex, we need a handle on the APK itself, which is actually quite easy to do:

The above code opens a DexFile for the running APK. Of course, this can have some performance implications. Opening the DexFile will potentially cause the VM to pass classes.dex through a process known as “dexopt”, which is a program that performs bytecode verification and optimization. This is an expensive process, but since we’re opening a DexFile for the APK itself, classes.dex should have already undergone this process, meaning dexopt won’t be run again.

The DexFile gives us access to the classes contained in classes.dex as an enumeration of strings representing the package-qualified class names. With this, we can iterate over the class names and load any which match the desired package.

This gets the job done, and it’s essentially how Infinitum accomplishes component scanning. However, it’s a very expensive operation. DexFile.entries() yields every class in the classpath — that is, every class in classes.dex — which includes not just application binaries, but also those of any libraries included.

It’s great that we can introspect every class in the classpath, but if we’re only interested in classes of a particular package, we’re out of luck. Every class is compiled into classes.dex and, short of decompiling it ((Tools for decompiling DEX files exist, such as Baksmali, but doing such a thing at runtime — if it’s even possible — would arguably not gain you any performance benefits. Still, this is something worth exploring.)),  there’s no way to pull out the classes we want without iterating over the entire classpath.

So, for now we settle with this somewhat inefficient solution. Nonetheless, it accomplishes what it needs to at the cost of maybe a few hundred milliseconds ((On the emulator running on my MacBook Pro, the classpath scanning takes about 600 milliseconds, while on my Galaxy Nexus, it takes about 200 milliseconds.)), so maybe it’s not such a bad approach in the grand scheme of things.

Posted on

Introducing InfinitumFramework.com

rendering

Here’s a dose of shameless self-promotion. It’s coming up on a year since I started development on Infinitum, and I’m targeting its first full release on its birthday, February 11. Shortly before I moved the project to GitHub, they deprecated the downloads service, so I needed to fine a home for distributing the binaries as well as the Javadoc.

GitHub offers its pages service, but I figured I’d just host it myself. I threw together a website in a couple days and the result is www.infinitumframework.com. This website will be used to host the latest (and previous) releases of the framework, its documentation, and, in the future, announcements and updates for it.

Stay tuned as Infinitum approaches its first official release!

Posted on

Modularizing Infinitum: A Postmortem

In addition to getting the code migrated from Google Code to GitHub, one of my projects over the holidays was to modularize the Infinitum Android framework I’ve been working on for the past year.

Infinitum began as a SQLite ORM and quickly grew to include a REST ORM implementation,  REST client, logging wrapper, DI framework, AOP module, and, of course, all of the framework tools needed to support these various functionalities. It evolved as I added more and more features in a semi-haphazard way. In my defense, the code was organized. It was logical. It made sense. There was no method, but there also was no madness. Everything was in an appropriately named package. Everything was coded to an interface. There was no duplicated code. However, modularity — in terms of minimizing framework dependencies — wasn’t really in mind at the time, and the code was all in a single project.

The Wild, Wild West

The issue wasn’t how the code was organized, it was how the code was integrated. The project was cowboy coding at its finest. I was the only stakeholder, the only tester, the only developer — judge, jury, and executioner. I was building it for my own personal use after all. Consequently, there was no planning involved, unit testing was somewhere between minimal and non-existent, and what got done was at my complete discretion. Ultimately, what was completed any given day, more or less, came down to what I felt like working on.

What started as an ORM framework became a REST framework, which became a logging framework, which became an IOC framework, which became an AOP framework. All of these features, built from the ground up, were tied together through a context, which provided framework configuration data. More important, the Infinitum context stored the bean factory used for storing and retrieving bean definitions used by both the framework and the client. The different modules themselves were not tightly coupled, but they were connected to the context like feathers on a bird.

infinitum-arch

The framework began to grow large. It was only about 300KB of actual code (JARed without ProGuard compression), but it had a number of library dependencies, namely Dexmaker, Simple XML, and GSON, which is over 1MB combined in size. Since it’s an Android framework, I wanted to keep the footprint as small as possible. Additionally, it’s likely that someone wouldn’t be using all of the features in the framework. Maybe they just need the SQLite ORM, or just the REST client, or just dependency injection. The way the framework was structured, they had to take it all or none.

A Painter Looking for a Brush

I began to investigate ways to modularize it. As I illustrated, the central problem lay in the fact that the Infinitum context had knowledge of all of the different modules and was responsible for calling and configuring their APIs. If the ORM is an optional dependency, the context should not need to have knowledge of it. How can the modules be decoupled from the context?

Obviously, there is a core dependency, Infinitum Core, which consists of the framework essentials. These are things used throughout the framework in all of the modules — logging, DI ((I was originally hoping to pull out dependency injection as a separate module, but the framework relies heavily on it to wire up components.)), exceptions, and miscellaneous utilities. The goal was to pull off ORM, REST, and AOP modules.

My initial approach was to try and use the decorator pattern to “decorate” the Infinitum context with additional functionality. The OrmContextDecorator would implement the ORM-specific methods, the AopContextDecorator would implement the AOP-specific methods, and so on. The problem with this was that it would still require the module-specific methods to be declared in the Infinitum context interface. Not only would they need to be stubbed out in the context implementation, a lot of module interfaces would need to be shuffled and placed in Infinitum Core  in order to satisfy the compiler. The problem remained; the context still had knowledge of all the modules.

I had another idea in mind. Maybe I could turn the Infinitum context from a single point of configuration to a hierarchical structure where each module has its own context as a “child” of the root context. The OrmContext interface could extend the InfinitumContext interface, providing ORM-specific functionality while still inheriting the core context methods. The implementation would then contain a reference to the parent context, so if it was unable to perform a certain piece of functionality, it could delegate to the parent. This could work. The Infinitum context has no notion of module X, Y, or Z, and, in effect, the control has been inverted. You could call it the Hollywood Principle — “Don’t call us, we’ll call you.”

infinitum-context-hierarchy

There’s still one remaining question: how do we identify the “child” contexts and subsequently initialize them? The solution is to maintain a module registry. This registry will keep track of the optional framework dependencies and is responsible for initializing them if they are available. We use a marker class from each module, a class we know exists if the dependency is included in the classpath, to check its availability.

Lastly, we use reflection to instantiate an instance of the module context. I used an enum to maintain a registry of Infinitum modules. I then extended the enum to add an initialize method which loads a context instance.

The modules get picked up during a post-processing step in the ContextFactory. It’s this step that also adds them as child contexts to the parent.

New modules can be added to the registry without any changes elsewhere. As long as the context has been implemented, they will be picked up and processed automatically.

Once this architecture was in place, separating the framework into different projects was simple. Now Infinitum Core can be used by itself if only dependency injection is needed, the ORM can be included if needed for SQLite, AOP included for aspect-oriented programming, and Web for the RESTful web service client and various HTTP utilities.

We Shape Our Buildings, and Afterwards, Our Buildings Shape Us

I think this solution has helped to minimize some of the complexity a bit. As with any modular design, not only is it more extensible, it’s more maintainable. Each module context is responsible for its own configuration, so this certainly helped to reduce complexity in the InfinitumContext implementation as before it was handling the initialization for the ORM, AOP, and REST pieces. It also worked out in that I made the switch to GitHub ((Now that the code’s pushed to GitHub, I begin the laborious task of migrating the documentation over from Google Code.)) by setting up four discrete repositories, one for each module.

In retrospect, I would have made things a lot easier on myself if I had taken a more modular approach from the beginning. I ended up having to reengineer quite a bit, although once I had a viable solution, it actually wasn’t all that much work. I was fortunate in that I had things fairly well designed (perhaps not at a very high level, but in general) and extremely organized. It’s difficult to anticipate change, but chances are you’ll be kicking yourself if you don’t. I started the framework almost a year ago, and I never imagined it would grow to what it is today.

Posted on

Dalvik Bytecode Generation

Earlier, I discussed the use of dynamic proxies and how they can be implemented in Java. As we saw, a necessary part of proxying classes is bytecode generation. From its onset, something I wanted to include in Infinitum was lazy loading. I also wanted to provide support for AOP down the road. Consequently, it was essential to include some way to generate bytecode at runtime.

The obvious choice would be to use a library like Cglib or Javassist, but sadly neither of those would work. That’s because Android does not use a Java VM, it uses its own virtual machine called Dalvik. As a result, Java source code isn’t compiled into Java bytecode (.class files), but rather Dalvik bytecode (.dex files). Since Cglib and Javassist are designed for Java bytecode manipulation, they do not work on the Android platform. ((ASMDEX, a Dalvik-compatible bytecode-manipulation library was released in March 2012, meaning Cglib could, in theory, be ported to Android since it relies on ASM.))

What’s a programmer to do? Fortunately, some Googlers developed a new library for runtime code generation targeting the Dalvik VM called Dexmaker.

It has a small, close-to-the-metal API. This API mirrors the Dalvik bytecode specification giving you tight control over the bytecode emitted. Code is generated instruction-by-instruction; you bring your own abstract syntax tree if you need one. And since it uses Dalvik’s dx tool as a backend, you get efficient register allocation and regular/wide instruction selection for free.

Even better, Dexmaker provides an API for directly creating proxies called ProxyBuilder. If you followed my previous post on generating proxies, then using ProxyBuilder is a piece of cake. Similar to Java’s Proxy class, ProxyBuilder relies on an InvocationHandler to specify a proxy’s behavior.

Dexmaker enabled me to implement lazy loading and AOP within the Infinitum framework. It also opens up the possibility of using Mockito for unit testing in an Android environment because Mockito relies on proxies for generating mocks. ((Infinitum is actually unit tested using Robolectric, which allows for testing Android code in a standard JVM.))

Posted on

Solving the Referential Integrity Problem

“A man with a watch knows what time it is. A man with two watches is never sure.”

I’ve been developing my open source Android framework, Infinitum, for the better part of 10 months now. It has brought about some really interesting problems that I’ve had to tackle, which is one of the many reasons I enjoy working on it so much.

Chicken or the Egg

Although it’s much more now, Infinitum began as an object-relational mapper which was loosely modeled after Hibernate. One of the first major issues I faced while developing the ORM component was loading object graphs. To illustrate what I mean by this, suppose we’re developing some software for a department store. The domain model for this software might look something like this:

As you can see, an Employee works in one Department, and, conversely, a Department has one or more Employees working in it, forming a many-to-one relationship and resulting in the class below.

Pretty straightforward, right? Now, let’s say we want to retrieve the Employee with, say, the ID 4028 from the database. Thinking about it at a high level and ignoring any notion of lazy loading, this appears to be rather simple.

1. Perform a query on the Employee table.

2. Instantiate a new Employee object.
3. Populate the Employee object’s fields from the query result.

But there’s some handwaving going on in those three steps, specifically the last one. One of the Employee fields is an entity, namely department. Okay, this shouldn’t be a problem. We just need to perform a second query to retrieve the Department associated with the Employee (the result of the first query is going to include the Department foreign key — let’s assume its 14).

Then we just create the Department object, populate it and assign it to the respective field in the Employee.

Once again, there’s a problem. To understand why, it’s helpful to see what the Department class actually looks like.

Do you see what the issue is? In order to construct our Employee, we need to construct his Department. In order to construct his Department, we need to construct the Employee. Our object graph has a cycle that’s throwing us for a (infinite) loop.

Breaking the Cycle

Fortunately, there’s a pretty easy solution for this chicken-or-the-egg problem. We’ll make use of a HashMap to keep tabs on our object graph as we incrementally build it. This will make more sense in just a bit.

We’re going to use a HashMap keyed off of an integer hash where the map values will be the entities in the object graph.

The integer hash will be a unique value computed for each entity we need to load to fulfill the object graph. The idea is that we will store the partially populated entity in the HashMap to have its remaining fields populated later. Loading an entity will take the following steps:

  1. Perform query on the entity table.
  2. Instantiate a new entity object.
  3. Populate the entity object fields which do not belong to a relationship from the query result.
  4. Compute the hash for the partial entity object.
  5. Check if the HashMap contains the computed hash.
  6. If the HashMap contains the hash, return the associated entity object (this breaks any potential cycle).
  7. Otherwise, store the entity object in the HashMap using the hash as its key.
  8. Load related entities by recursively calling this sequence.

Going back to our Employee problem, retrieving an Employee from the database will take these steps:

  1. Perform query on the Employee table.
  2. Instantiate a new Employee object.
  3. Populate the Employee object fields which do not belong to a relationship from the query result.
  4. Compute the hash for the partial Employee object.
  5. Check if the HashMap contains the computed hash (it won’t).
  6. Store the Employee object in the HashMap using the hash as its key.
  7. Perform query on the Department table.
  8. Instantiate a new Department object.
  9. Populate the Department object fields which do not belong to a relationship from the query results.
  10. Compute the hash for the partial Department object.
  11. Check if the HashMap contains the computed hash (again, it won’t).
  12. Store the Department object in the HashMap using the hash as its key.
  13. The cycle will terminate and the two objects in the HashMap, the Employee and the Department, will be fully populated and referencing each other.

Considering the HashMap is not specific to any entity type (i.e. it will hold Employees, Departments, and any other domain types we come up with), how do we compute a unique hash for objects of various types? Moreover, we’re computing hashes for incomplete objects, so what gives?

Obviously, we can’t make use of hashCode() since not every field is guaranteed to be populated. Fortunately, we can take advantage of the fact that every entity must have a primary key, but, unless we’re using a policy where every primary key is unique across every table, this won’t get us very far. We will include the entity type as a factor in our hash code. Here’s the code Infinitum currently uses to compute this hash:

This hash allows us to uniquely identify entities even if they have not been fully populated. Our cycle problem is solved!

Maintaining Referential Integrity

The term “referential integrity” is typically used to refer to a property of relational databases. However, when I say referential integrity, I’m referring to the notion of object references in an object graph. This referential integrity is something ORMs must keep track of or otherwise you run into some big problems.

To illustrate this, say our department store only has one department and two employees who work in said department (this might defeat the purpose of a department store, but just roll with it). Now, let’s say we retrieve one Employee, Bill, from the database. Once again ignoring lazy loading, this should implicitly load an object graph consisting of the Employee, the Department, and the Employees assigned to that Department. Next, let’s subsequently retrieve the second Employee, Frank, from the database. Again, this will load the object graph.

Bill and Frank both work in the same Department, but if referential integrity is not enforced, objects can become out of sync.

The underlying problem is that there are two different copies of the Department object, but we must abide by the Highlander Principle in that “there can be only one.” Bill and Frank should reference the same instance so that, regardless of how the Department is dereferenced, it stays synced between every object in the graph.

In plain terms, when we’re retrieving objects from the database, we must be cautious not to load the same one twice. Otherwise, we’ll have two objects corresponding to a single database row and things will get out of sync.

Enter Identity Map

This presents an interesting problem. Knowing what we learned earlier with regard to the chicken-or-the-egg problem, can we apply a similar solution? The answer is yes! In fact, the solution we discussed earlier was actually masquerading as a fairly common design pattern known as the Identity Map, originally cataloged by Martin Fowler in his book Patterns of Enterprise Application Architecture.

The idea behind the Identity Map pattern is that, every time we read a record from the database, we first check the Identity Map to see if the record has already been retrieved. This allows us to simply return a new reference to the in-memory record rather than creating a new object, maintaining referential integrity.

A secondary benefit to the Identity Map is that, since it acts as a cache, it reduces the number of database calls needed to retrieve objects, which yields a performance enhancement.

An Identity Map is normally tied to some sort of transactional context such as a session. This works exceedingly well for Infinitum because its ORM is built around the notion of a Session object, which  can be configured as a scoped unit of work. The Infinitum Session contains a cache which functions as an Identity Map, solving both the cycle and the referential integrity issues.

It’s worth pointing out, however, that while an Identity Map maintains referential integrity within the context of a session, it doesn’t do anything to prevent incongruities between different sessions. This is a complex problem that usually requires a locking strategy, which is beyond the scope of this blog post.

Under the Hood

It may be helpful to see how Infinitum uses an Identity Map to solve the cycle problem. The method createFromCursor takes a database result cursor and transforms it into an instance of the given type. It makes use of a recursive method that goes through the process I outlined earlier. The call to loadRelationships will result in this recursion.

Entities are stored in the Session cache as they are retrieved, allowing us to enforce referential integrity while also preventing any infinite loops that might occur while building up the object graph.

So that’s it! We’ve learned to make use of the Identity Map pattern to solve some pretty interesting problems. We looked at how we can design an ORM to load object graphs that contain cycles as well as maintain this critical notion of referential integrity. We also saw how the Identity Map helps to give us some performance gain through caching. Infinitum’s ORM module makes use of this pattern in its session caching and many other frameworks use it as well. In a future blog entry, I will talk about lazy loading and how it can be used to avoid loading large object graphs.