Revision as of 07:14, 26 September 2010

Blur: Project Summary

My Honours project, nicknamed Blur, is a program that provides a global command line interface which mirrors the functionality of the GUI in any application. It uses self-demonstration to encourage users to transition from the GUI to the command line. In other words, whenever the user invokes a command with the GUI, Blur pops up showing the command line text that will perform the equivalent action.

Examples of the auto-complete in action

An example of the self-demonstration feedback

Design Goals

• Provide a text interface to commands
• Provide intuitive typeahead and auto-complete suggestions
• Allow different types of typeahead
• Autocomplete and display typeahead on command names
• Autocomplete and display typeahead on parameters within commands
• Create a reusable autocomplete component (i.e. not coupled to Blur-specific functionality)
• Command suggestions should be unambiguous (not currently the case)

Initial Design

The following UML diagram shows my initial system design, with some details omitted (such as utility classes that wrap the Win32 functionality, and the class hierarchy containing all the different Commands). In this study I will focus mainly on the auto-complete functionality.

Tour of the design

The CommandForm class (not shown) constitutes the main GUI of Blur. It contains one control - the AutoCompleteCommandLine. This class contains most of the logic for the auto-complete functionality, and is responsible for drawing the command line prompt, user input, typeahead and other feedback on the form. Whenever the user inputs some text to the command line, it generates a new AutoCompleteResultSet. This is essentially a collection of AutoCompleteEntries, with some custom logic. It needs to be able to order AutoCompleteEntries in order of relevance, by sorting them into three categories: exact matches, where the user's input exactly matches a valid command, prefix matches, where the user's input matches the beginning of a valid command, and substring matches, where the user's input matches some inner substring of the command. Internally, it uses three separate lists to achieve these (res_exact, res_start, and res_include), and each of these lists is sorted in order of the frequency of use. The AutoCompleteSet also contains the logic to populate itself, given a search string and a list of possible command strings.

AutoCompleteEntries, which represent the command suggestions that show up beneath the command line, are internally represented as strings. An AutoCompleteEntry stores a ListText string, which is displayed in the suggestion list, an AppendText string, which is appended to the user's input, and a GetStartIndex() method that figures out where the AppendText should be appended, given a user input string. Each AutoCompleteEntry has a couple of integers to figure out where the auto-completion started, and where the typeahead should be appended.

The AutoCompleteCommandLine searches for commands from an ICommandSource, which is set externally via the CommandSource property. The ICommandSource interface has a single method called GetCommands(), which returns a dictionary of available commands, indexed by their names. The interface should enable reuse of the AutoCompleteCommandLine component, by allowing clients to define their own command sources. The AutoCompleteCommandLine takes all of the names from GetCommands() and uses them to construct an AutoCompleteResultSet.

ICommand provides a minimal interface to commands, that exposes only the functionality required by the AutoCompleteCommandLine. Implementing this interface is an abstract Command class, which provides the functionality common to all Blur specific commands. Command has a bunch of subclasses (not shown) which implement the individual command functions, such as window switching, app launching, and in-application control. (It's worth noting that this is an obvious example of the Command pattern.)

Criticisms

I found it reasonably difficult to get this design right when I was first creating it, so I just went with the first thing that worked. I couldn't Model the real world to figure out where each of the responsibilities belonged, since nothing here exists in the real world.

Below are some of my concerns with the existing design.

Coupling between the modules

Ideally, I would like the auto-completion logic (the left-hand side of the diagram) to be decoupled from the underlying command logic (the right-hand side of the design). In other words, the right-hand side of the diagram should stand alone as an API, and not know anything about the auto-completion/GUI side. This is mostly the case, but there are a couple of nasties. The worst example is shown by the dependency relationship across the top of the diagram - this is because ICommand has an AutoComplete method which returns an AutoCompleteResultSet. Also, the AutoCompleteCommandLine is hardcoded to search for a "switch" command in the ICommandSource dictionary (shown in the code snippet in the diagram), and if it exists, to autocomplete on its parameters without having to have the "switch" keyword present (an example of this kind of autocomplete entry is shown in the 3rd screenshot at the top of the page). This is a nasty piece of hardcoding that should really be more general.

It may be a good idea to implement some variant of Model view controller here in order to separate the GUI logic (including typeahead) from the underlying commands.

AutoCompleteEntry issues

There are a number of problems with the AutoCompleteEntries. First of all, they expose public data directly (violating Hide data within its class), as well as containing methods that deal with part of the autocompletion logic. Ideally, this would be either a pure data class, or the data would be private and the AutoCompleteEntry would contain all of the logic for autocompletion. The former would possess the Data class smell, but I don't think this is particularly important (the merits of each approach will be explored later, in the redesign). At this stage, the class is a nasty hybrid, with the AutoCompleteEntry finding the index in the string at which to start the autocomplete, and the client (the AutoCompleteCommandLine) performing the rest of the work.

The second problem with the AutoCompleteEntry is that it is entirely string-based. This causes ambiguities between different types of auto-completion: for example, the command line could be auto-completing on an app (e.g. "firefox") and the name of a folder (also called "firefox") at the same time. When this happens, one will override the other. These ambiguities could be solved by representing each AutoCompleteEntry as a command and a parameter list. This technique would also be a lot more flexible when improving the auto-complete in future.

Finally, the integer fields (m_BackTrack and m_AppendIndex) are just really nasty. Their purpose and relationship to each other is non-obvious, and they are extremely inflexible: they only allow typeahead at the end of the input string. Typeahead at any point in the input string is desirable (for example, so "visu" can autocomplete to "microsoft visual studio"). This needs to be fixed.

Naming

AutoCompleteEntry is a poor name. It isn't self-explanatory enough (a better name would reflect its nature as a suggestion to the user). AutoCompleteResultSet is also poor - not only does it contain AutoCompleteEntries, rather than AutoCompleteResults, but it isn't a set (it relies on ordering and functions more as a list).

Redesign

This new design addresses most of the concerns of my critique above.

Improvements

The autocomplete side has had a complete overhaul in this iteration. AutoCompleteEntries are now Suggestions, and the AutoCompleteResultSet is now a SuggestionList. The new Suggestion class is now in charge of performing the typeahead (feedforward), and the Strategy pattern has been used to make this behaviour a lot more flexible. FeedForwardStrategy has a set of concrete subclasses that perform different types of feedforward depending on the context.

Each call to Suggestion.FeedForward() returns a FeedForwardResult, which is a list of FeedForwardParts (each of which is just a string with a flag determining whether it was automatically generated). A FeedForwardResult is capable of rendering itself, meaning the FeedForwardParts can be nicely encapsulated within the FeedForwardResult (since all they're used for is drawing different-coloured text to the screen). This is a good example of Keep related data and behavior in one place, as well as Tell, don't ask, since clients of the FeedForwardResult give it a graphics context and tell it to render (rather than just asking it for its data).

The SuggestionList is now slightly more flexible and general. It no longer stores the three lists for exact, prefix and substring matches. Instead, I defined an enum of different match classes (called, unsurprisingly, MatchClass), and the SuggestionList stores a dictionary keyed by these classes. This keeps the speed advantage and simplicity of maintaining a separate list per class (since the suggestions are primarily ordered by class), but in a more general way. Operations over the suggestion lists can now iterate over the dictionary instead of using hardcoded references to each list, which means there is much less code to change when a new class of match is added (I took the opportunity while refactoring this to add another class of match which is ordered by the length of its longest common subsequence)).