Tab Completion

Home --> Programming Projects --> Miscellaneous --> Tab Completion

The Problem

Suppose you are making an application which allows the user to type some string. Furthermore, suppose this entered string must be a member of some set S which your program stores. It would be nice to allow the user to hit the tab key to complete what they have typed so far. This is done, for example, in terminals. The purpose of this page is to describe a simple algorithm to accomplish this. The tab completion algorithm will only append to the end of what is typed (as opposed to "glob completion", which completes a string containing wildcards).

Tab Completion API

The following abstract class has the method Complete which should be called to tab complete a given string. The bool is_done is set to true iff the input string has been successfully completed to a string in S. The bool is_valid is set to true iff there exists a suffix which can be appended to the input to get a string in S. 
class TabCompleter {
public:
    virtual void Complete(
        const string & input,
        string & output,
        bool & is_done,
        bool & is_valid);
};
As it stands, our description for the behavior of Complete is ambiguous. The confusion is in what happens when there exist two distinct strings in S with one an initial segment of the other. Because of this, we must be very careful how we define the behavior of the function. Here is desired behavior:
  1. Let A be the set of all elements of S that have input as an initial segment.
  2. If A is empty, then set is_done to false and is_valid to false. Otherwise, proceed to the next step.
  3. If A has exactly one element, then set output to this element, set is_done to true, and is_valid to true. Otherwise, proceed to the next step.
  4. Compute the largest common initial segment x of the elements of A.
  5. If x is in S, then set output to x, is_done to true, and is_valid to true. If not, proceed to the next step.
  6. Set output to x, is_done to false, and is_valid to true.
The strange step is #5. We might want to modify the API so that the caller knows when this case has happened. However, I don't immediately see a situation where the caller would want to know this information.

A Simple Derived Class

If we have the set of strings S at our disposal, then we can easily impliment the algorithm described above using a Radix Tree. 
class RadixTreeTabCompleter : public TabCompleter {
private:
    //The radix tree should be stored here.
    //...
    
public:
    void BuildRadixTree(
        const set<string> & all_strings)
    {
        //Build the radix tree.        
        //...
    }
    
    void Complete(
        const string & input,
        string & output,
        bool & is_done,
        bool & is_valid)
    {
        //Do the obvious thing.      
        //...
    }
};

Combining Tab Completers

Suppose we have two different tab completers T1 and T2. The tab completer T1 allows us to complete an input string to an element of some set S1, and T2 allows us to complete an input string to an element of some set S2. There is a very simple way in which we can complete an input string to an element of the union of S1 and S2. Namely, we take the largest common initial segment of the output of T1 and T2 (provided they return valid outputs).