Keyboard Navigation

Keeping with the Uniscribe theme brings us to the next area of Neatpad’s development that hasn’t been touched on yet, which is keyboard-input. I’ve deliberately left this stage until now because I knew that without Uniscribe keyboard-navigation would be very difficult indeed. The problem with keyboard-handling is not how to process keyboard input (which is easy), but rather how to navigate through a Unicode file - taking into account combining sequences, surrogates, graphaeme clusters etc.

Up until this point the Uniscribe API has been used extensively provide text-rendering support. Fortunately Uniscribe can be used for more than just text output, and we will be looking in detail at the ScriptBreak API and how it can help us manage keyboard navigation.

Keyboard messages in Win32

All Windows programs receive keyboard input in the form of WM_KEYDOWN and WM_KEYUP messages. When a key is pressed, a series of WM_KEYDOWN messages are sent to an application’s message-queue, and when the key is released a single WM_KEYUP message is sent. These two messages are relatively ’low level’ but together still form the foundation of keyboard-input in Windows.

The table above summarises the two basic keyboard-input messages, and also their ‘system’ counterparts - WM_SYSKEYDOWN and WM_SYSKEYUP. These last two messages are seldom used by Windows programs and have no relevance to Neatpad’s development so I won’t bother describing them here.

The WM_KEYDOWN message is most commonly used by applications to detect when specific keys on the keyboard have been pressed. This is a good way to detect keys such as <control>, <shift> and arrow keys. However when it comes to text-entry, processing specific key presses is not actually the best way to go about things.

For example, when processing specific key presses, there is no easy way to determine the case of a letter. The user could have hit the ‘A’ key, but is this in lowercase or uppercase? All we know is the virtual-keystroke ‘A’ was entered, but we don’t know anything about the state of the CAPSLOCK button or whether the user is holding the SHIFT key down. Obviously the actual character entered would be different depending on these factors - in this simple case it could be either ‘a’ or ‘A’. Things get even more complicated when you move beyond English keyboards into the realm of Unicode, Input Method Editors and system locales, where multiple key-strokes can result in wildly different characters.

Fortunately there is another mechanism for handling character input in Windows - the WM_CHAR and WM_UNICHAR messages. These messages are specifically intended to represent characters rather keystrokes. Interestingly, WM_CHAR is not automatically sent to an application when a key is pressed on the keyboard. It is not until the TranslateMessage function is called inside an application’s message-loop that the WM_CHAR message is dispatched.

while(GetMessage(&msg, 0, 0, 0) > 0)
{
    TranslateMessage(&msg);
    DispatchMessage(&msg);
}

Above is the standard message-loop of many Win32 programs. Most programmers probably copy+paste this loop straight into their code without giving it much thought, but the TranslateMessage function in particular has a very specific purpose. It translates certain messages (such as WM_KEYDOWN) into a series of corresponding WM_CHAR messages. TranslateMessage takes into account certain things such as the state of the SHIFT or CAPSLOCK keys, and also the current locale. Note that the WM_KEYDOWN message being translated is not modified in any way - instead a new WM_CHAR message is constructed by TranslateMessage and posted back into the current thread’s message-queue for subsequent processing.

The table above this time summarises the various character-input messages available to Windows programs. We don’t be performing actual data-entry into Neatpad until much later on in this series so there is no point in looking at these messages now.

Keyboard Navigation with WM_KEYDOWN

The purpose of this tutorial is to cover the implementation of Keyboard Navigation - so we are only interested in physical keys such as the arrow-keys, page-up, page-down, home & end, etc. Therefore will only need to handle the WM_KEYDOWN message at this time - actual character-input (and the WM_CHAR /WM_UNICHAR messages) will wait until later in this series until we actually have a mechanism to modify the TextDocument.

In general, keyboard navigation in Windows text-editors is fairly consistent. The arrow keys (left, right, up, down) are used to move the text-caret in these four basic directions, and page-up, page-down, home and end are all well established in what they should achieve. In addition holding the control or shift keys should modify the behaviour of whatever navigation key is being pressed at the time - the shift key being used to alter the text-selection as the cursor is being moved.

The table below summarises the behaviours that we wil be implementing in Neatpad.

Each action will be represented by a TextView member-function that will perform the associated operation. As you can see there are actually quite a number of different actions that we must implement. This is due in part to the effect of the control-key which almost doubles the number of methods we must implement.

The WM_KEYDOWN handler in Neatpad’s TextView is shown below. A switch-statement is used to process each keystroke that we are interested in:

LONG TextView::OnKeyDown(UINT nKeyCode, UINT nFlags)
{
    bool fCtrlDown = IsKeyPressed(VK_CONTROL);

    switch(nKeyCode)
    {
    case VK_LEFT:

        if(fCtrlDown) MoveWordPrev();
        else MoveCharPrev();

        break;

    case VK_RIGHT:
    ...
    } 

    << extend selection if <shift> is held down >> 

    << update text-caret position >>
}

The purpose of the MoveXxxx functions is to update the m_nCursorOffset variable to reference a new position within the current file. Each MoveXxxx function adjusts m_nCursorOffset in a different way depending on what keyboard action should be processed. I won’t include the entire function here because hopefully you can get the general idea from the snippet above.

Once a keypress has resulted in m_nCursorOffset being updated, the next step is to handle text-selections:

// Extend selection if <shift> is down
if(IsKeyPressed(VK_SHIFT))
{		
    InvalidateRange(m_nSelectionEnd, m_nCursorOffset);
    m_nSelectionEnd = m_nCursorOffset;
}
// Otherwise clear the selection
else
{
    if(m_nSelectionStart != m_nSelectionEnd)
        InvalidateRange(m_nSelectionStart, m_nSelectionEnd);

    m_nSelectionEnd = m_nCursorOffset;
    m_nSelectionStart = m_nCursorOffset;
}

Extending the text-selection is simply a matter of checking the state of the shift key (up/down), and then modifying the m_nSelectionStart and m_nSelectionEnd TextView variables appropriately. When the selection should be extended (shift key is down) then only the m_nSelectionEnd variable is modified. Otherwise both variables are updated to the same value, effectively ‘zeroing’ the selection.

The final step is to update the physical caret-position from the cursor-offset. This is an important concept because at no time during the keyboard navigation does the caret’s physical on-screen position need to be taken into account. All keyboard navigation is based soley on a single logical character-offset and it is only after the cursor-offset has been updated (due to a keypress) is the caret repositioned:

// update text-caret location (xpos, line#) from the offset
UpdateCaretOffset(m_nCursorOffset, &m_nCaretPosX, &m_nCurrentLine);

UpdateCaretOffset is already being used to position the caret from a previous tutorial (using the UspOffsetToX and SetCaretPos APIs), so this function is simply reused for our keyboard handling.

All keyboard navigation in Uniscribe is based around logical offsets. In other words, the cursor advances through the backing store (the file) in WCHAR units. When it comes to navigating through bidirectional strings the caret still advances logically through the file. We rely on Uniscribe converting the logical cursor-offset to a physical location on screen (using the ScriptCPtoX function). This may mean that the cursor appears to move both ’left’ and ‘right’ within the same string even if a single arrow-key is being used. Don’t worry about displaying the caret in bidirectional strings - because we are using Uniscribe it handles all these details for us automatically.

Lastly note the use of the IsKeyPressed function, which is a simple wrapper around the GetKeyState API. It’s purpose is to simplify the test for whether a key is pressed or not and returns a boolean value indicating this fact.

bool IsKeyPressed(UINT nVirtKey)
{
    return GetKeyState(nVirtKey) < 0 ? true : false;
}

ScriptBreak

ScriptBreak works alongside ScriptItemize to identify the logical attributes of each character in a string. ScriptBreak must be called once for each individual item-run in the string (as identified by ScriptItemize) and returns an array of SCRIPT_LOGATTR structures. Each entry in the array represents a single WCHAR in the Unicode string, and must be allocated by the caller to have the same number of elements as there are WCHARs in the run.

HRESULT WINAPI ScriptBreak ( 
  WCHAR * pwcChars, 
  int cChars, 
  SCRIPT_ANALYSIS * psa, 
  SCRIPT_LOGATTR * psla 
);

The individual attributes for each character are held within the SCRIPT_LOGATTR structure, shown below:

struct SCRIPT_LOGATTR 
{ 
  BYTE fSoftBreak : 1; 
  BYTE fWhiteSpace : 1; 
  BYTE fCharStop : 1; 
  BYTE fWordStop : 1; 
  BYTE fInvalid : 1; 
  BYTE fReserved : 3; 
};

Although each field of the SCRIPT_LOGATTR structure has a specific purpose, this information as returned by ScriptBreak is generally useful for two purposes: word-wrapping and keyboard navigation:

• fSoftBreak indicates the positions within a string where word-wrapping can take place - in other words, the positions where the string can be broken into smaller units suitable for display over multiple lines.
• fWhiteSpace indicates that the corresponding character should be treated as white-space. This could potentially be set for many more characters than just tabs and spaces.
• fCharStop and fWordStop identify valid caret positions within the string. These positions can be used to support single character- based navigation and ‘word’ navigation.

Don’t under-estimate just how much work ScriptBreak is doing on our behalf. The identification of character and word positions alone saves us a tremendous amount of effort. Added to this is the fact that ScriptBreak supports all of the various Unicode scripts, so for languages such as Thai (which require dictionary support to identify ‘soft breaks’), all of the hard work is already done.

The task of calling ScriptBreak for each item-run is handled by the UspAnalyze function, which we looked at in previous tutorials. The SCRIPT_LOGATTR buffer is allocated and stored inside the USPDATA object’s breakList * member. A simple loop is then used to iterate over each item-run, and the results of ScriptBreak stored inside the USPDATA::breakList array. The array holds the results for all item-runs, concatenated together:

<< UspLib.c - UspAnalyze(...) >>

 // allocate memory for SCRIPT_LOGATTR structures
 uspData->breakList = malloc(wlen * sizeof(SCRIPT_LOGATTR));

 // Generate the word-break information for each item-run
 for(i = 0; i < uspData->itemRunCount; i++)
 {
     ITEM_RUN *itemRun = &uspData->itemRunList[i];

     ScriptBreak(
          wstr + itemRun->charPos, 
          itemRun->len, 
         &itemRun->analysis, 
          uspData->breakList + itemRun->charPos
     );
 }

Any string (or paragraph) of text analyzed with UspAnalyze will therefore automatically have it’s SCRIPT_LOGATTR information stored inside the USPDATA object. Because the information for each run has been concatenated into the same buffer in effect individual item-runs do not need to be taken into account when inspecting the logical-attributes for each character in the string.

Let’s look at a quick example and see how the string “Hello يُساوِي World” would be treated by ScriptBreak. Note that there are two spaces in the string, one either side of the Arabic phrase:

Tabs and Whitespace

ScriptBreak does not identify tab-characters as whitespace by default. This poses a problem because every text-editor under the sun understands that tabs are basically the same as spaces and should therefore be treated the same. The solution is to parse the Unicode string looking for tab-characters and modify the corresponding entries in the breakList :

for(i = 0; i < wlen; i++)
{
    if(wstr[i] == '\t')
        uspData->breakList[i].fWhiteSpace = TRUE;
}

The loop above can be found inside UspAnalyze and is executed after the ScriptBreak information has been obtained.

UspGetLogAttr

I have introduced a new UspLib function called UspGetLogAttr, which is similar in concept to the Script_pLogAttr function. It returns a pointer to the breakList buffer inside each USPDATA object. The difference is however, that a non-constSCRIPT_LOGATTR array is returned which can be modified by the caller of the function.

SCRIPT_LOGATTR * UspGetLogAttr( USPDATA * uspData )
{
    return uspData->breakList;
}

As you can see the UspGetLogAttr function is really very simple - all it does is return a pointer to the breakList buffer which is held inside each uspData object. Of course the real work in building this buffer was performed by the UspAnalyze function.

The reason this function exists is to allow the caller to modify the internal SCRIPT_LOGATTR structure inside each USPDATA object. This is important, because when it comes to syntax-highlighting I invisage that we will have to fine-tune the SCRIPT_LOGATTR buffer for each line to cater for more specific language-syntax details.

For now the UspGetLogAttr function is purely used by the keyboard navigation functions to control cursor-placement within each line of text.

Character and Word navigation

Character and Word navigation are quite closely related to each other. Both actions operate within a single line of text and both use the SCRIPT_LOGATTR information returned by ScriptBreak to position the caret at valid character/word positions:

VOID TextView::MoveCharPrev()
{
    USPCACHE * uspCache;
    CSCRIPT_LOGATTR * logAttr;
    ULONG lineOffset;
    int charPos;

    // get Uniscribe data for current line
    uspCache = GetUspCache(0, m_nCurrentLine, &lineOffset);
    logAttr = UspGetLogAttr(uspCache->uspData);

    // get character-offset relative to start of line
    charPos = m_nCursorOffset - lineOffset;

    // find the previous valid character-position
    for( --charPos; charPos >= 0; charPos--)
    {
        if(logAttr[charPos].fCharStop)
            break;
    }

    << move up to end-of-last line if necessary >>

    // update cursor position
    m_nCursorOffset = lineOffset + charPos;
}

MoveCharPrev begins by obtaining the cached UspData object for the current line, and the SCRIPT_LOGATTR structure for that line is retrieved by calling UspGetLogAttr. The SCRIPT_LOGATTR array is then parsed to detect valid character-stop positions. Because UspData objects represent individual lines, all processing is relative to the start of each line:

// find the previous valid character-position
for( --charPos; charPos >= 0; charPos--)
{
     if(logAttr[charPos].fCharStop)
         break;
}

The loop above is quite simple. All it does is continue looping until a character-stop position is found. When the loop exits the charPos variable has been modified and the text-caret can be repositioned.

Word-navigation is a little more complicated. The MoveWordNext logic can be seen below:

// if already on a word-break, go to next char
if(logAttr[charPos].fWordStop)
    charPos++;

// skip whole characters until we hit a word-break/more whitespace
for( ; charPos < uspCache->length_CRLF; charPos++)
{
    if(logAttr[charPos].fWordStop || logAttr[charPos].fWhiteSpace)
        break;
}

// skip trailing whitespace
while(charPos < uspCache->length_CRLF && logAttr[charPos].fWhiteSpace)
    charPos++;

Remember that all we are doing so far is altering the logical cursor-offset for the TextView. The actual text-caret is positioned independently and does not require any form of sophisticated processing on our part. This is the great thing about Uniscribe - as a programmer we only have to deal with logical character units - all of the complicated display-related code is handled automatically for us.

Line Wrapping

I was hoping that this stage would not be necessary due to the linear (offset-based) coordinate system that we are using for Neatpad. However because of the way Neatpad handles CR/LF sequences, specific checks must be in place to detect when the cursor moves past the beginning/end of a line. Should this occur the cursor is moved onto the previous/next line accordingly.

The difficulty occurs because the text-caret should not be allowed to move past the CR/LF at the end of each line. In effect the CR/LF sequences are ‘dead’ characters that cannot be used as character-stop positions. The image below illustrates this by showing the caret at the very last position it can reach, despite there being a line-feed character at the end.

The task of wrapping to the previous/next line is deferred to the MoveLineEnd and MoveLineStart functions. You will therefore see the following code in many of the MoveXxxxPrev functions:

if(charPos < 0)
{
    charPos = 0;

    if(m_nCurrentLine > 0)
    {
        MoveLineEnd(m_nCurrentLine-1);
        return;
    }
}

…and the following code in the corresponding MoveXxxxNext functions:

if(charPos == uspCache->length_CRLF)
{
    if(m_nCurrentLine + 1 < m_nLineCount)
        MoveLineStart(m_nCurrentLine+1);

    return;
}

I was hoping to use the SCRIPT_LOGATTR arrays somehow to ‘skip’ CR/LF sequences rather than have specific code just for this purpose. I realise that I have probably not found the neatest way to deal with line-wrapping but I’ve been working at this for so long now I’m just going to release what I’ve got. I anyone can suggest a nice way to deal with line-wrapping that doesn’t require any additional processing then please get in touch…

Line navigation and Anchoring

Conceptually line-based navigation is very simple - on the surface all that is required is for the cursor’s line-number to be adjusted - in order for the cursor to move up/down a specified number of lines. Unfortunately the implementation is slightly more complicated than that because of the necessity to support variable-width fonts.

The problem occurs when the user moves the cursor (or text-caret) up or down a line. The user’s expectation when he/she hits the up/down arrows is for the cursor to be shifted vertically to the previous/next line. For fixed-width fonts this is not an issue - the caret’s y-position can be adjusted quite freely and this is all that is usually required. However variable-width fonts require that the caret’s x-position be potentially modified to ensure that the caret always locates to a valid character position. In effect the caret must always ‘snap’ to the nearest character-stop boundary when moving up or down.

The image above illustrates this idea. As the cursor moves down through the file, you can see various numbered caret-positions being displaced horizontally around a fixed vertical line. This vertical line brings us onto the next concept to explore which is sometimes referred to as ‘anchoring’.

Quite simply, anchoring is the process where the text-cursor is kept as close as possible to a specific horizontal coordinate within each line when moving up or down through a file. Imagine that the user places the text-caret at a character-position using the mouse. This location is represented by an x-coordinate within the current line and also the line-number itself. When the user moves up or down the file using the arrow keys, they expect the cursor to follow the vertical line that they chose as closely as possible. In Neatpad’s TextView I refer to this process as anchoring.

The anchor position is represented by the m_nAnchorPosX variable. It is set whenever the user moves left/right along a line, or instead places the caret using the mouse. Importantly, the anchor position is not set when the up/down arrow keys are used as this would defeat the object of the exercise.

UspXToOffset(uspData, m_nAnchorPosX, &charPos, &trailing, 0);

Now when moving to the previous/next lines, the appropriate character-position can be identified by calling Uniscribe’s ScriptXToCP, which converts the anchoring-coordinate to a logical character offset. This function has been encapsulated by the UspXToOffset function within UspLib and can be seen above.

VOID TextView::MoveLineUp(int numLines)
{
    USPDATA * uspData;
    ULONG lineOffset;
    int charPos;
    BOOL trailing;

    // move 'up' the specified number of lines
    m_nCurrentLine -= min(m_nCurrentLine, (unsigned)numLines);

    // get Uniscribe data for that line
    uspData = GetUspData(0, m_nCurrentLine, &lineOffset);

    // move to character position nearest the anchoring x-coordinate
    UspXToOffset(uspData, m_nAnchorPosX, &charPos, &trailing, 0);

    m_nCursorOffset = lineOffset + charPos + trailing;
}

The MoveLineUp function (above) shows how the cursor is adjusted when moving up through the file. The key detail here is the call to UspXToOffset. This UspLib function takes the caret-anchoring position and finds the closest Unicode character-offset.

Coming up in Part 17

Keyboard Navigation has the potential to be incredibly complicated due to Unicode. Fortunately the Uniscribe API solves all the complexity with the ScriptBreak API. This is another huge benefit of moving to Uniscribe - the amount of code that we have been saved from writing is quite significant.

Next up will be syntax-highlighting. I have decided that regular expressions are definitely the best method in this regard, however there are many issues that must first be solved before any further work is completed. Some of the forthcoming topics will probably be regular expressions, parsing techniques and finite-state machines (FSM). If you have any comments in this regard then I’d be happy to hear them!

Downloads
neatpad16.zip