Tuesday, September 9, 2008

Yi's top-level structure

In this post I’ll give a very high-level overview of Yi’s structure. This the first part of a series that should eventually constitute a guide for Yi hacking… but let’s get going!

Yi code can be categorized into four parts:

  • Actions, which are operations having some effect on the editor state. This can be opening or saving a file, or moving the cursor in the current buffer.

  • Keymaps, governing how user input maps to actions. Yi comes with keymaps for emacs and vi emulation (and users are encouraged to write their own keymaps). Keymaps are very much like parser-combinators, but they produce a stream of actions instead of a parse-tree.

  • UIs, which are responsible for rendering the editor state, and getting the stream of input events from the user. Yi comes with console, gtk and experimental cocoa UI.

  • Glue code, to tie the knot between Keymaps and UI.

The structure described above is very flexible: there is very low coupling between components. Indeed, one can easily swap out one component for another in the same category. For example, the user can choose between the different UIs and key-bindings at runtime.

The “actions” part makes up most of the editor code. This part is structured around a stack of three monadic DSLs.

  • BufferM: A monad for all buffer-local operations, like insertion and deletion of text, and annotation of buffer contents. It can be understood as a monad that encapsulates the state of one buffer.

  • EditorM: A monad for editor-level operations, e.g., opening and closing windows and buffers. Operations involving more than one buffer are handled at this level too.

  • YiM: A monad for IO-level operations. There, one can operate on files, processes, etc. This is the only level where IO can be performed.

All these parts are easily composable, and this makes convenient to extend (and configure) the editor. In the next post we’ll see in more detail how to do so.

Tuesday, September 2, 2008

Adding Vim-like tabs to Yi

Intro


This post walks through the process and thinking behind the initial implementation of a tabbar in Yi.This was originally written about a month ago and discusses this patch. This can be followed like a tutorial but a copy of the Yi repository right before the patch is required. This command:

Will construct the required Yi checkout. The remainder of this post is written assuming that checkout is the current state of Yi.

The goal is to add a tabbed view of the editor much like that in Vim 7.0. For those unfamiliar with Vim, just think of the tabs in Firefox. Yi already has support for multiple views on the text. These views currently work much like Vim and Emacs' multiple window support: The screen can be divided into a set of rectangular views, called windows, where each view presents a region of a text buffer to the user. The tabbed view is an extension of this feature. Each tab will contain a different set of windows and only one tab will be visible at a time.

Adding Tabs to the Editor State


In Yi, the state of the editor is described by the Editor data structure in the module Yi.Editor. This contains a property that describes the set of windows currently presented by the editor.

One requirement of tab support is that each tab contains a different set of windows. In order to take advantage of the zipper properties of the window set data structure (More on that later) the same abstract data structure[1] will be used to represent a set of tabs that each contain a set of windows.

Which brings us to the first change: Replacing the "windows" property of the Editor data structure with a "tabs" property. The "tabs" property is a set, where each element of the set is a set of windows.

hunk ./Yi/Editor.hs 49
- ,windows :: WindowSet Window
+ ,tabs :: WindowSet (WindowSet Window)

This change will break a lot of code. Any code that manipulated the window set of the editor will now fail to compile. I'm going to work under the assumption that all the existing code, under the context of an editor with tabs, is only manipulating the window set of the current tab. This way I can use a property of Haskell's records to make the old code compatible with the new structure.

Haskell's records can, for the most part[2], be though of as tuples combined with auto-generated field selector equations (AKA labels). These equations have the type "[RecordType] -> [FieldType]" and have the same name as the field. Which means the "windows" field selector for the original Editor data structure had the type "Editor -> WindowSet" and the name "windows" An equation with the same signature can be manually added. For existing code that uses the "windows" selector this new function will provide compatibility with the new implementation:

hunk ./Yi/Editor.hs 63
+windows :: Editor -> WindowSet Window
+windows editor =
+ WS.current $ tabs editor
+

(The above refactoring pattern has proved useful in other projects as well. I find it is a handy
pattern to use when needing to incrementally extend a Haskell data type.)

There are three additional areas that need to be updated before Yi will once again compile: The windows accessor; Construction of an Editor instance; Update of the windows on buffer deletion.

1. The windows accessor.


The windows accessor before tabs meant "Provide an accessor for the window set." The new equation will mean "Provide an accessor for the window set of the current tab."

There are many properties in Yi's state that are presented through an accessor interface. The idea behind the accessor interface is to simplify getting and setting a specific property of the editor in a stateful way. When using a non-pure language this is something that is trivial to do: "foo.bar = 1; print foo.bar;" For a pure language, like Haskell, things are different. The Yi/Accessors.hs module provides equations to abstract away the details for users of an API.

For developers, which is the part we are playing in this post, we have to worry about the details. A property that has a Yi.Accessor interface is composed of two parts: A getter equation and a setter equation.

The getter equation is the same as the "windows" equation above. Done!

The setter equation needs to extract out the window set of the current tab. Apply a modifier to the window set and update the editor's current tab with the modified window set.

hunk ./Yi/Editor.hs 103
-windowsA = Accessor windows (\f e -> e {windows = f (windows e)})
+windowsA = Accessor windows modifyWindows $
+ where modifyWindows f e =
+ let ws = WS.current (tabs e)
+ ws' = f ws
+ tabs' = (tabs e) { WS.current = ws' }
+ in e {tabs = tabs' }

2. Construction of an Editor instance.


The Editor instance was constructed with a window set containing a single window to a scratch buffer. Now an Editor instance will be constructed with a single tab that contains a window set containing a single window to a scratch buffer.

The last two sentences were written in verbose prose to make a point: If X was the text "a window set containing a single window to a scratch buffer." Then the first sentence contained just X. While the second contained X prefixed with "a single tab that contains ". The code that implements this change will follow the same pattern:

hunk ./Yi/Editor.hs 127
- ,windows = WS.new win
+ ,tabs = WS.new $ WS.new win


The equation was "WS.new win" Which is the implementation of X in the paragraph above. The new equation is "WS.new $ WS.new win" Which is the implementation of X prefixed with the implementation of "a single tab that contains "

3. Update of the windows on buffer deletion.


Resolving this is straight forward: "pickOther" is an equation that replaces references in a Window to the buffer being deleted with references to some other buffer. The original implementation used map to apply this equation to each Window in a set of windows. The new implementation, essentially, uses map to apply the original equation the set of windows contained in each tab.

hunk ./Yi/Editor.hs 190
- windows = fmap pickOther (windows e)
+ tabs = fmap (fmap pickOther) (tabs e)


At this point Yi will once again compile and run. No features will have been gained. Which is fine. Validating the change of implementation introduced no regressions in functionality is important. This is easier to do before the new features are implemented.

Assuming no regressions are found let's move on... (Nice assumption eh?)

Adding Vim Keymap Support


The Vim keymap is going to be modified to support tabs before the functions that actually manipulate the tabs will be added. This provides a good opportunity to develop the interfaces for these functions before considering the actual implementations. Once the potential interfaces are decided then the actual implementation details will be examined.

In Vim, my usual tab workflow consists of three actions:

  1. Using ":tabnew [path | buffer]" to create a new tab.

  2. Using "gt" to move to the next tab.

  3. 3. Using "gT" to move to previous tab.


We'll examine these in turn.

Adding ":tabnew [path | buffer]"


The optional argument to :tabnew will be ignored for now. The implementation of this will be a pattern match on "tabnew" that maps to the editor action "newTabE"

hunk ./Yi/Keymap/Vim.hs 909
+ fn "tabnew" = withEditor newTabE

Adding "gt" and "gT"


The other two actions, #2 and #3, are very similar: Both are actions, next tab and previous tab respectively, applied on the recognition of a sequence of characters input in command mode.

"pString" recognizes a sequence of characters. " >>! " declares that satisfying the left hand side implies the action on the right hand side. Using these to extend the cmd_eval part of the Vim command mode keymap is pretty straight forward:

hunk ./Yi/Keymap/Vim.hs 312
- choice
- ([c ?>>! action i | (c,action) <- singleCmdFM ] ++
+ choice $
+ [c ?>>! action i | (c,action) <- singleCmdFM ] ++
hunk ./Yi/Keymap/Vim.hs 315
- [char 'r' ?>> textChar >>= write . writeN . replicate i])
+ [char 'r' ?>> textChar >>= write . writeN . replicate i
+ ,pString "gt" >>! nextTabE
+ ,pString "gT" >>! previousTabE]
+

At this point Yi will fail to compile. Good. That is what is expected for implementing code that uses an API without actual implementing the API. Otherwise something is seriously amiss! :-)

Editor Tab API


Rewind back to where the abstract data type WindowSet* was mentioned to be a zipper In this case, the WindowSet is both a list and an iterator into this list. The iterator into the list represents the "current" element being viewed. For a UI application this abstraction is very useful. Among other reasons: Persistence of the data structure is maintained; And the "current" iterator is never invalidated.

newTabE will add a new tab containing a window set of a single window to the editor. As a window in Yi needs to view a buffer, I felt it was reasonable to create a window that views the current buffer the user is editing. The implementation of newTabE looks very much like what you'd expect if the tab set was represented by a list: The new tab is added to the list. However, as the tab set is a zipper the WS.add equation has the additional effect of changing the current tab to the newly added element.

nextTabE and previousTabE change the current tab in the zipper. nextTabE goes forward in a round robin fashion while previousTabE goes backward. Both can be thought of only changing the current tab iterator in the zipper and nothing more.

hunk ./Yi/Editor.hs 448
+-- | Creates a new tab containing a window that views the current buffer.
+newTabE :: EditorM ()
+newTabE = do
+ bk <- getBuffer
+ k <- newRef
+ let win = Window False bk 0 k
+ modify $ \e -> e { tabs = WS.add (WS.new win) (tabs e) }
+
+-- | Moves to the next tab in the round robin set of tabs
+nextTabE :: EditorM ()
+nextTabE = do
+ modify $ \e -> e { tabs = WS.forward (tabs e) }
+
+-- | Moves to the previous tab in the round robin set of tabs
+previousTabE :: EditorM ()
+previousTabE = do
+ modify $ \e -> e { tabs = WS.backward (tabs e) }

Compile and run. Now Yi has a very basic tabbed UI.

Footnotes



  1. The WindowSet data structure is more general than it's name implies. The generic name is "cursor" but that's confusing in the context of an editor so the name "Round Robin Set" probably makes more sense.

  2. I'm ignoring labelled updates and data types with multiple constructors. Probably some other details too. Ah well!