Blog Without An Important Name

Here’s something a bit more computer-sciencey than usual. For something at work, I have had to implement a function parser, so you can type ‘1+2*b‘ and it’ll work it all out, with correct operator precedence and so forth. To do this, I use a three-step process:

1. Tokenise the input, and at the same time convert any variables found to their numeric values
2. Convert the input tokens to RPN using the Shunting Yard algorithm
3. Evaluate the RPN form of the equation using an RPN parser, which is really easy to write

This did the job nicely, however the time came when it had to be extended, and able to accept functions, such as ‘max(1,2,3)‘. The standard shunting yard algorithm can handle functions, but with the restriction that the number of arguments to them is known (really, this is a limitation of the RPN algorithm, but it’s at this point in the process that we need to deal with the problem). In this case, I wanted to handle functions with a variable number of arguments, so ‘max(1,2)‘ would work, and so would ‘max(1,2,3,4,5)‘. To do this, I extended the standard algorithm. Below is the algorithm from Wikipedia. My additions are in bold. This requires two more stacks, a ‘were values‘ stack, and an ‘arg count‘ stack. It also requires that you can attach the number of arguments to an instance of a function. In my case, I did it with a small class that took the function and an argument count, with one of these created during tokenisation for each function encountered.

• While there are tokens to be read:

• Read a token.
• If the token is a number, then add it to the output queue. If the were values stack has a value on it, pop it and push true.
• If the token is a function token, then push it onto the stack. Push 0 onto the arg count stack. If the were values stack has a value on it, pop it and push true. Push false onto were values.
• If the token is a function argument separator (e.g., a comma):

• Until the topmost element of the stack is a left parenthesis, pop the element onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched. Pop were values into w. If w is true, pop arg count into a, increment a and push back into arg count. Push false into were values.

• If the token is an operator, o₁, then:

• while there is an operator, o₂, at the top of the stack, and either

o₁ is associative or left-associative and its precedence is less than (lower precedence) or equal to that of o₂, or

o₁ is right-associative and its precedence is less than (lower precedence) that of o₂,

pop o₂ off the stack, onto the output queue;

• push o₁ onto the operator stack.

• If the token is a left parenthesis, then push it onto the stack.
• If the token is a right parenthesis:

• Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
• Pop the left parenthesis from the stack, but not onto the output queue.
• If the token at the top of the stack is a function token
  • Pop stack into f
  • Pop arg count into a
  • Pop were values into w
  • If w is true, increment a
  • Set the argument count of f to a
  • Push f onto output queue
• If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.

• When there are no more tokens to read:

• While there are still operator tokens in the stack:

• If the operator token on the top of the stack is a parenthesis, then there are mismatched parenthesis.
• Pop the operator onto the output queue.

• Exit.

Note that because I didn’t feel like correctly listifying most of it, consider an if to apply to the end of that sentence only. Operation order is usually important.

With this done, the part of the RPN algorithm that says:

It is known that the function takes n arguments.

can now be satisfied.

I currently am doing some spare-time work for Naxos (the music label), customising my Java-based, open-source eMusic.com downloader, eMusic/J, to work with their Classicsonline download service. This means taking what was a Linux-only application and making it work on Windows and Mac OS X also. Getting the Linux version was obviously easy, I’d already done that; making a Windows version took a little more time, but most of that was learning how to make EXE files and installers (I’m using Launch4j and NSIS for that). However, making it work on Mac OS X was quite a trial, because this platform decides to do some things totally differently to the others.

The fundamental issue was an incompatibility between SWT, the GUI toolkit I’m using, and the Apple event system. Basically, to make SWT work you need to pass a special option to the JVM: StartOnMainThread. However, as soon as you do this, you lose the ability to catch events for things like “someone double-clicked one of my documents”. So I had the option of having a broken GUI, or no events. Neither of which is a possibility, as opening a particular file is the major purpose of this program. My theorising about what the actual issue is is in this message.

However, Azureus manages to do this, so I knew it was possible. With some help from the Azureus devs on IRC, and staring at undocumented code, I finally have a solution which I’m putting here in the hope that other people don’t spend hours of fruitless searching like I did.

It is possible, with some JNI hooks into the Carbon layer of OS X, to catch the events there and have them passed through to the application. Basically, you include this JNI code, create some callbacks using SWT, sacrifice a chicken and bleed a goat, and all of a sudden your code gets called when someone opens one of your files.

The code that I use is here. If you look at one of the ...Mac.java files, you can see the open doc handler being loaded, and inside that (OpenDocHandler.java), at the bottom of the target object, you have the bit that sends the files to the rest of the program. I don’t understand most of what it does, but it works. If I get around to it, I plan to refactor this and create a fairly stand-alone bit of code that means you can just register your own callback, and get the events without having to modify the handler. That would be pretty easy to do, I just didn’t want to touch it once I got it working. This method can probably be adapted to handle the other events, but I don’t need them so I stripped those parts out. Have a look in OSXAccess.java in the Azureus 2 code if you want to know how to do that.

Once you have this, and someone double-clicks a document type you have registered, you get told about it. Conveniently, you also get an event when your application is opened because someone opened your document.

Note: most of the code there is GPLed as I ripped it from Azureus (and eMusic/J is GPL too), but I think the actual C bit is probably something more liberal, as it was done by IBM and I expect they intend for it to be under something like the Apache licence. But I don’t know for sure, as the original file doesn’t have licence details.

So, hopefully very soon, Classicsonline will have a cross-platform, open-source download manager for its users.

I recently saw mention that Google had released Guice, their internal dependency injection framework. As an experiment, I ported a few parts of the web application I’m working on for work to use it. I’ve never used dependency injection before, and so it was a chance to learn about it too. The executive summary is that it works great. Previously I had a giant factory class handling all the instantiation of singletons (mostly which handle talking to the database), so I would do stuff like:
Configuration.getObjectRegistry().getNoticeHandler()
This worked well enough, but all the static references made testing hard, I couldn’t substitute in my own fake classes at all.

Now, for the classes that I’ve ported to use Guice, in my test case I can create a module that makes it load a bunch of fake classes to simulate what the real ones would do, so I only need to test the one class that I’m looking at. It also means I don’t have to set up database entries for everything that might get touched. I just add a line to the module like:
bind(INoticeHandler.class).to(FakeNoticeHandler.class).in(Scopes.SINGLETON);

The only gotcha I had was that I couldn't get it to inject into the servlet objects automatically. This is because you have no control over their instantiation, the application server handles that all itself. The solution to this is for the class that catches the application loading to store the Injector instance in the ServletContext, and have each servlet object load that and inject the dependencies into itself on init:

@Override
public void init(ServletConfig config) throws ServletException {
	super.init(config);
	ServletContext context = config.getServletContext();
	Injector injector = (Injector) context.getAttribute("injector");
	if (injector == null) {
		throw new UnavailableException("The Guice injector could not be " +
				"found in the ServletContext. It is expected to be named " +
				"'injector'.");
	}
	injector.injectMembers(this);
}

if every servlet extends the abstract class that contains this (and this extends HttpServlet), then it all magically just works.

Over time I plan to port the rest of the application to use this, but probably just as I’m working on those classes. In the documentation it says:

Dependency injection is viral. If you’re refactoring an existing code base with a lot of static methods, you may start to feel like you’re pulling a never-ending thread. This is a Good Thing. It means dependency injection is making your code more flexible and testable.

This is definitely the case, it would be easy to start and just keep following the thread of dependencies until the whole thing was done. However, I’m avoiding that now just due to a) being scared to refactor the whole damn thing at once, and b) I should be spending time on bug fixing and critical features right now. But, it probably won’t be too long before the whole thing is done, as a side-effect of testing.

For work stuff, I’ve been needing to set up a script to convert videos from whatever form they come in as to SWF (or, really, FLV embedded in SWF). The best thing for this that I found was FFmpeg. It does just about anything. One thing it doesn’t seem to do however is produce SWF files with the right frame count. It always writes the header with a count of 15,000, no matter the length of the incoming video. 15,000 is the maximum number of frames that the flash player can handle, and is used as a placeholder value when the file is created.

I tracked the problem down to the output not being correctly flushed, and the following patch fixes it:

Index: libavformat/swf.c
===================================================================
--- libavformat/swf.c   (revision 7093)
+++ libavformat/swf.c   (working copy)
@@ -689,7 +689,6 @@
     put_swf_tag(s, TAG_END);
     put_swf_end_tag(s);

-    put_flush_packet(&s->pb);

     /* patch file size and number of frames if not streamed */
     if (!url_is_streamed(&s->pb) && video_enc) {
@@ -699,7 +698,7 @@
         url_fseek(pb, swf->duration_pos, SEEK_SET);
         put_le16(pb, video_enc->frame_number);
     }
-
+    put_flush_packet(&s->pb);
     av_free(swf->audio_fifo);

     return 0;

In case you’re working on a substantially different version of swf.c, this goes towards the end of static int swf_write_trailer(AVFormatContext *s), and is just moving the put_flush_packet call to after where the frame number is written into the file, rather than before.

Pretty simple eh? I mentioned this on the ffmpeg-users list, but noone seems interested. No matter, I don’t mind too much keeping a custom build with this change. I need to do it anyway, the Ubuntu FFmpeg version doesn’t have MP3 encoding support, and that’s a must for creating FLV.

Recently I’ve been using the Google Web Toolkit (GWT) for writing a web-based application (nothing I can talk about just yet ). It’s a very nice way of building an AJAX-type web app in pure Java. You write the client-side code in much the same way as you would a typical Java GUI application, and it compiles it to Javascript for you. (A note for the uninitiated: Java and Javascript are in no way related, except for the unfortunate confusing similarity in name).

For example, this is a segment of code that puts a text box into a grid (in this case, as part of a login form):
usernameBox = new TextBox();
table.setText(row,0,"Username:");
table.setWidget(row,1,usernameBox);

As well as GUI stuff, the other thing that it provides is a way to perform RPC, so you can initiate a request when an event occurs, such as a button press, and some time later you get the response and the user interface can be updated accordingly. It supplies all the interfaces to catch the request at the server side, process it, and return the result. All this is done by passing around Java objects, just as you would when working with a purely Java-based system. I believe that it uses something like JSON internally, although I haven’t looked into that much yet.

The point where the pure Java abstraction breaks down is that any classes that are used by the part that is getting compiled into JS must be either in the same package as the rest of the client code, or part of the libraries that are part of GWT. Fortunately, GWT includes all of java.lang and much of java.util so commonly used classes are available. However, care must be taken to convert any exceptions to something that is available to the client code, and to not do things like (as got me at one point) passing an ArrayList containing java.text.Date instances. Mysterious error messages occur if you do this. The silver lining of this is that it forces you to do proper separation between the code that produces the data and the code that displays it.

There is a fair amount of things that aren’t included that would be in a more mature GUI toolkit, however all the important stuff (that I’ve needed, anyway) was there. The trickiest part that I encountered was getting file uploads to work. It turns out that it’s not possible to do this directly from JS, as it’s not desirable to give scripts access to files, and so a regular HTML form must be used. However, the problem with forms is that clicking on the ‘Submit’ button causes a POST to go to the webserver, which requires loading new content and restarting the app. This was avoided by using a custom component to create the form, and having it target an invisible IFRAME. This, along with polling the server to get the state of the transfer makes for a nice upload interface. It’s not perfect (I’d like to avoid the polling of the server), but it works well enough.

GWT isn’t useful for building full-on websites. As all the content is dynamically created, you won’t get any sort of keywords visible to web crawlers, and your accessibility is out the window. If your needs are simply to produce a nice-to-use web-based application, it makes things quite easy.

I heard back a few days after the phone interview that I didn’t get the Google job. Pity, but not too surprising really. I suspect that it was because I lacked the knowledge/experience related with the systems reliability side of things. So for now, things are just going on the way they have. Soon, I’ll have to enact Plan B: build some cool web-base tech, and sell it for millions. I mean, it worked for Trademe!

At Linux.conf.au, which I’ve efficiently failed to finish writing about, Google had a beer bash. I didn’t think much of it at the time, but I went because - well, free drink! However, at one point I was sitting talking to some people, and one of the recruiters came by with a list for me to put our email addresses down on, so I did. Can’t hurt, right? A couple of weeks later I get an email asking if I was interested in working for them. So I said sure. So I had a pre-interview about a week after that, and then yesterday had the first phone interview. It was fairly chatty, which was nice. It was just one person, who was a programmer, so it wasn’t an HR person reading from a script or anything like that. Asked a bunch of questions about computer science stuff: stacks, sorting, etc. A note to anyone doing something similar: the stuff taught in second year computer science (at Otago, anyway) is invaluable, it turns out. That and a few thoughts about how to apply them.

I’m applying for the SRE (Systems Reliability Engineering (I think)) group, which is the one that manages the servers for search and ads. They do things like failure management, resource planning (like “we’re going to need a new datacentre in a few months”), software deployment, monitoring, and so forth. The impression I get is that it’d be a nice mix of systems and software stuff.

So anyway, if they liked me from this interview (I won’t find out for a week or so), I get another one or two phone interviews, and if I’m still in the running, I think they’d then fly me over there for something in person. That would be pretty cool.