Atlassian, one of the biggest developers of proprietary tools for software developers, on DVCS, Mercurial, and version control.

DVCS systems in the Enterprise

Prefix Lookup

Be sure to read my new post where I explore prefix lookup algorithm efficiency in more detail.

A central principle of Abundant (stemming from b, which took the idea and code from t) is the ability to look up data by searching for a unique prefix of that data. For instance, if an issue is given the unique but unpleasant to use ID of '2fd4e1c67a2d28fced849ee1bb76e7391b93eb12', a user can refer to it simply as '2fd' and Abundant will be able to identify that this is the issue they were referring to (assuming no other issue starts with the same prefix of course).

It is not immediately clear how this lookup should work, however. t uses some custom and fairly inefficient (though good enough for it's use case) code to generate the prefix lookup. You can browse t's source code here, __getitem__ on line 141 is how items are looked up by prefix, and _prefixes on line 77 generates a table mapping items to their shortest unique prefixes. Both functions are O(n) on the number of items in the list, or more precisely, O(n*m) where m is the length of the item (or prefix).

This isn't terrible, and scales perfectly well for t and b; if I recall correctly from testing run last summer, these functions handle searching several hundred thousand records with ease. But when it came to scaling to greater demands of Abundant, adding additional features started becoming expensive. Running an O(n) lookup once isn't bad, for instance, but when you need to do it several times, and restructure the database after each step, it quickly becomes apparent that there ought to be a more robust solution.

So I ran a search on Stack Overflow for 'prefix data structure' and found a question 'most efficient data structure for a read-only list of strings (about 100,000) with fast prefix search' tagged 'Python' which in turn pointed me to a data structure called a trie that was exactly what I was looking for.

A trie (pronounced try or tree) is a tree (you guessed that I hope :P ) structure which is organized by similar prefixes of entries.  From the root, children all share a comon prefix.  So the children of the root are grouped by their first character, the grandchildren by their second character, and so on.  There are implementation details that differ from implementation to implementation, but that is the conceptual premise of all tries.

Tries operate in O(m) time, where m is the length of the prefix being looked up. This is very fast, and often faster than the "O(1)" hash table (it's actually also O(m) due to the hash function, and collisions make it more expensive) or the O(log n) binary search tree. This makes them a drastically more desirable choice than the linear search methodology of b and t.

After exploring several Python implementations described or referenced in the SO question I decided to build my own, since each of the existing implementations were not quite what I was looking for.  Most notably, the "standard" trie stores the entire key, one character at a time, down the tree.  For sparse trees (that is to say, long keys, but short unique prefixes) this seemed fairly space/time inneficient, and so my trie only goes as far as it needs to, and restructures as necessary.  In order to facilitate ease of use, my trie converts all keys and searches to lowercase, which is potentially dangerous in some use cases, but desirable for Abundant so users can look up data without regard to case sensitivity.  Imagine if, due to some platform specific issue, an ID hash was stored with uppercase hex instead of lower case.  Users would never be able to find the issue, even though as far as hex is concerned they are legitimately entering the correct number.

Furthermore, my trie implements a notion of an alias, which is stored in the trie like any other value, but when retrieved does a dictionary lookup of the alias value and returns the result.  For example, users can specify both a username and an email address in angle brackets. It would reasonable for users to be able to reference each other by either a prefix of their name or their email address. As such, Abundant adds the user string (username <email@address>) to the user trie, and then makes an alias from the email address to the user string, enabling prefix lookup on either value, transparently to the user.

It's not quite a general case trie, but I've tried to keep these specific features like lowercase and alias abstracted from the underlying data structure, so that a more traditional trie data structure could be constructed fairly trivially. All in all, I'm very pleased with this new feature.

Mutable Types as Default Parameters in Python

I just came across a little feature/bug in Python I thought worth sharing.

In Python, you can set default values for parameters, like so:

def func(param="hello"):

The result of which is a function you can call either with or without a parameter.  This seems simple enough, and works very nicely.  However what if you want to use something more complex as the default parameter?  Say, a list?

def func(param=[]):

This works just fine, exactly like the previous example.  But one thing that may or may not immediately be obvious is every call to this function without an explicit parameter will share the same list.  Python is smart enough not to re-parse the default parameters ever time the function is called, meaning that only one empty list is ever created in defining or using func().  Usually this has no effect on the programmer - if your default values are primitive or immutable types, which the vast majority of default values likely are, there is no loss to the function sharing the value between different calls - it won't be changed.  And even when mutable types are used, it's rare to gain any benefit from changing a mutable data structure the rest of the program cannot access, and as such most cases of mutable types as default parameters are used simply for accessing, not mutating, the data.

But one example where that is not the case is in a constructor.  Consider:

class BlogPost:
    def __init__(comments=[]):

When constructing a BlogPost object, I don't want to take the time to explicitly tell it there are no comments, so I would usually not even bother populating that parameter. On its own, this isn't enough to get me into trouble. Neither is creating multiple BlogPosts, nor is accessing, changing, or otherwise working with a BlogPost dangerous. And so you could go quite some time developing before you find yourself in a situation where you have constructed multiple BlogPost objects and where you update the comments array of one of them. As soon as you do that, however, all other existing BlogPost objects will also have the same comment in their comments list, because it's actually the same list!

Once you think about it this behavior is not terribly shocking - you might even go so far as to say it's intuitive. However if you aren't thinking about it, it's a very bizarre problem to debug when it happens to you.

Command Line Processing

When running programs from the command line, they are able to take a list of string arguments (the String[] args in Java's main method, for example) to control how they work.  The only way to tell these arguments apart, however, is to look at their position in the list.  This works for some programs, but breaks down quickly for complex tasks.  Easy examples can be found in any standard command line programs.  How would you use a command like grep to search through files and then display some context around the matches.  Putting "context" as an argument wouldn't work, how would it know if "context" is a special parameter or a filename?

So the notion of options were invented.  The idea being, a special flag (traditionally - on Unix, / on Windows) is placed at the begining of an argument, and the remainder of the argument has special meaning.  -C in grep is used specially to indicate context.  Importantly, whatever argument follows -C is also not considered an argument, but the parameter to the context option (in this case, a number of lines to display is expected).

This fairly simple syntax is all that the vast majority of command line programs need to function.  It's all Mercurial needs, and it's presumably all Abundant will need also.  But there is neither any one standard way to actually structure this interface (some allow + or other symbols as flags, some allow options that optionally take arguments, some use -FLAG=ARG rather than -FLAG ARG, etc.) nor any straight forward way to implement any of these designs.  Python alone has three different libraries that all do the same thing, and they don't even provide the full range of features, so some projects still wouldn't be able to use them.

And so far we haven't even addressed how these arguments and options actually hook into executing code.  The available libraries usually work fairly well for "light" programs which do exactly one task (admittedly, this is the model Unix is built on, so this isn't completely unreasonable) such as cp, grep, or ping, however they break down very quickly with larger programs like Mercurial or Abundant, where depending on which operation you wish to do different options should or should not be allowed.  This seemingly reasonable functionality is all but completely missing from most argument processing libraries, and as such, needs to be built manually.

Mercurial built it's processor on top of optget, I am using the more powerful optparse for Abundant.  Besides the underlying library, the code design is fairly similar.  A function is defined for each atomic operation that can be run in Abundant.  Then a table (dictionary, hash map, whatever you want to call it) is constructed consisting of the name of the task, like init, new or edit, which maps to a data structure containing the correlating function, a list of options the command will take, and a string describing the expected structure of the command.  The program parses the input arguments, looks up the first parameter against the table, and if it finds a match, passes the remaining arguments to a parser library given the option structure described in the table, the result of parsing the input into options and arguments is then finally passed to the function to do its work.

It's a tedious and error prone process.  Error catching occurs at three levels, before the parser, in the parser, and in the function.  Many of these error checks need to be redundant between levels, and the end result is a very unpleasant piece of spaghetti code.  Shockingly, however, it's better than most of the alternatives out there that I have seen.  It scales easily (adding new commands and editing old ones has little to no effect on other commands), allows for unique options per task, and the end result will be quite nice, as Mercurial's UI demonstrates.  Getting there is a fairly painful process sadly.

Python Documentation

I had an interesting time understanding how to use Python's json library, which is very sparsely documented and completely lacks examples.  I found a page on using json in Python which was very helpful, but I did not read the code examples quite deeply enough, and the annotations were limited.

I wanted to be able to take a "bug" object and turn it into JSON data, and then take that JSON data and reconstruct the bug.  The example is for the generic case of serializing a class, and therefore stores metadata about the class, like its name, module, and package, along with the other data.  I wanted to avoid that if possible, and so stripped out the dynamic class construction and the like, and effectively wrote a pair of functions that took a dictionary and turned it into an object, and took an object and turned it into a dictionary.

However, I tried making one of the bug's instance variables a dictionary as well, and the program crashed when converting from JSON to Python object, seeming to have dropped the surrounding dictionary, and only considering the internal dictionary.  This seemed to me like completely bizarre behavior, and took a fair bit of poking around, including multiple stack overflow questions and spending time on #python (a truly painful process) in order to understand completely.

The specific problem was the object_hook parameter of json's load function.  The description of this parameter in the documentation is:

object_hook is an optional function that will be called with the result of any object literal decoded (a dict). The return value of object_hook will be used instead of the dict. This feature can be used to implement custom decoders (e.g. JSON-RPC class hinting).

If you read this closely, you may see what I was missing.  Remember that I was coming from the perspective of needing to serialize exactly one object, who's contents would all be data structures (lists or dicts), or primitives.  It hadn't really crossed my mind that an object could contain other objects that would need to be serialized.  Silly in retrospect of course, but not immediately intuitive if you aren't thinking about it.

So what was happening when I was seeing only the internal dict was exactly what was supposed to happen - json was applying the object_hook function to each nested dict in turn.  This meant that you could not (nor would you want to) use object_hook to apply to only one type of object, it needs to at least potentially handle any possible object that could be thrown at it.  I ended up implementing a much cleaner way of (un)serializing bugs once I understood exactly what object_hook is doing - which I'll claim isn't completely clear from the language used in the Python docs.

Development Documentation

In addition to version control (which we've got) and bug tracking, which of course we're making, the third most common tool used when developing large projects is some sort of easy to maintain documentation system - usually a wiki.  Therefore I have decided to set up a wiki to maintain a high level overview of the development of Abundant.  I think this would be a very good idea for all of our projects, as maintaining documentation as we develop our code will help improve the quality of our work.

I have decided to use TiddlyWiki for Abundant.  There are several reasons:

• Easy to set up
  The entire wiki consists of one HTML file and one JAR, there is no installation or system requirements.  Furthermore, setup and configuration is a breeze, with less than half an hour's work I had customized my TiddlyWiki to a desirable structure for software development.
• Compatible with version control
  The wiki is tracked by Mercurial and located right next to the source code.  This means this documentation always goes with the code, and tracking and merging changes works just like any other file.
• Lightweight bug tracker
  Although Abundant has far loftier goals than TiddlyWiki can ultimately fulfill, it will make a perfectly suitable issue tracker until Abundant is ready for dogfooding.  Similarly, this is one of the biggest reasons I think others should look into using TiddlyWiki or some other documentation tool, as it will provide for some very nice issue tracking as they develop their project.

Additionally, since TiddlyWiki is just an HTML file, you can view and browse it straight from the source code.  If you are interested in playing with TiddlyWiki as a development documenter, you may like to download the first version of the wiki which is structured with development in mind and an issue tracker page created.

Note: Presently, the links to the Abundant repository are password protected.  Anyone reading this blog is welcome to come talk to me and I'll tell you the password, but otherwise it will be publicly accessible soon enough.