Fewer NULL dereferences in edlib

My recent efforts with edlib have been to get rid of some potential NULL pointer dereference issues.  When I first started writing “commands” I assumed that the correct value would always be passed.  Of course that isn’t very safe unless it is enforced, and is particularly unsafe if I’m going to let users write their own commends in extension languages like python.  So more safety is required.

Auditing the code to ensure I’m always being careful enough is fairly boring and error prone, so I wrote a tool to help me.  More accurately I extended some existing tools.  You can read lots more details in my LWN.net article. At the time I wrote that I still had some unresolved issues.  I’ve resolved enough of those now that I no longer have warnings.  Sometimes that it because I used casts to hide things, but a lot of real issues have been address.  The versions of “sparse” and “smatch” that I am using are in the “safe” branch of the copies of these trees on github.com.  So this for smatch and this for sparse.

Doing this involved adding a lot of ‘safe’ annotations throughout edlib.  Hopefully these aren’t too confusing.  It is nice to have the documentation of intent, and nice to know that a whole class of errors is now impossible.

I had to fix a few bugs in smatch/sparse as well as add new functionality to smatch.  I really should post those bug fixes upstream…

Posted in edlib | Comments Off

A notmuch based email reader

I’ve been very slack.  Sorry.  I keep thinking “I should write a blog post about that” when I make some progress with edlib.  But I also think “or I could write some more code instead”.  I do enjoy writing blog posts.  But I seem to enjoy the code more.

Consequently, I’ve lost track of what has happened since my last post.  Git tells me that I have made 379 commits since then.  I’ve added “Alt-!” to run a shell command, with a history of recent commands stored in a buffer.  I’ve provided a way for attributes on text to trigger call-backs to display panes, to enabling highlighting of text; and used this to better display matches for the current search.  I’ve broken the “Refresh” event into three separate events, one that updates the sizes of panes,  one that can update the position of a document in a pane, and one that redraws the content.  And I’ve fixed lots of bugs and cleaned up lots of code.  But the big thing that I’ve been working on is a notmuch email client.

Notmuch Email

Notmuch is an email handling tool that maintains an index into a database of email messages, can add and remove tags on messages, and can perform various searches.  This makes it quite easy to present a list of email messages which match some criteria, and to extract the individual messages for display.  Notmuch comes with an emacs mode which is usable, but far from perfect.  So I’m building a notmuch interface in edlib.  You can try it by typing “M-x nm enter” providing that you already have notmuch configured to access your email.

The appearance of the notmuch mode that I envision is based largely on claws-mail, though several other email readers have similar appearance.  There is a narrow column on the left with the names of folders (saved searches with notmuch).  The remainder is divided into a list of message summaries at the top and the body of a message below that.  This means having a small number of panes in a fixed relationship with each other.  Were an application to try this in emacs it would be easy to setup but hard to maintain.  It is too easy for the user to split and close panes which would mess up the arrangement.

In edlib, my approach is to stack a tile-set inside a pane provided by the main tile-set.  Each tile set can have a name and split/resize/close commands from the keyboard only go to the primary unnamed tile-set.  So if the cursor is in the email-body-view pane and I type “C-x-2″ to split the pane, it doesn’t split the body view, but instead splits the whole email application pane. The pane containing my three-part view of email remains as three parts in the same relationship, but the pane as a whole might change size.  Currently it only responds by resizing the sub-panes, though I might teach it to hide some sub-panes when the over-all pane gets too small.  This shows what the app looks like after splitting the pane.

notmuchThe arrangement of panes and documents took a little effort to get right, and raises some interesting issues.  The primary document represents the whole notmuch database and presents a list of saved-searches.  So when you view that with the default viewing pane you get the appearance in the bottom half of the above.  When you then select a search, a subordinate document is created which stores just the results of that search.  This is stacked on top of a new tile and an appropriate viewer is placed on top of it.

In this arrangement there is now a document with another document as an ancestor in the pane tree.  The ‘search’ document is stacked over the tiles.  The primary data-base document is stacked under all of these 3 tiles.  This leaves room for confusion about the meaning of marks which are passed up or down the stack.  I had previously assumed there could only be one document beneath a leaf pane.  Now there can be two and so a mark passed down the stack might be mistakenly processed by the wrong document.  This should be easy enough to fix as their is already a field in the mark which can be set by the document which own the mark.  But it is something I hadn’t foreseen.

There is a lot more work to do on this application.  In particular it does not yet allow tags to be set or any other changes to be made, such as creating new saved searches.  Also, it only displays email messages as raw text.  notmuch can dissect a mime message into the various parts to make them easier to present, but I currently want edlib to do that natively.  I imagine a number of different display panes for displaying different types of data, and an RFC-2822 pane which parses the message and attaches display panes over different parts as needed.

So: good progress, but still so much to do…


Posted in edlib | Comments Off

edlib is back on track…

In the weeks leading up toe linux.conf.au 2016 I approached edlib development as a sprint.   I wanted to put together sufficient functionality so that I could present my LCA2016 talk using slides displayed by edlib.  I achieve this goal but at some cost.  A lot of the development that went into that sprint was fairly hackish and not well thought out.  It achieved the immediate goal but wasn’t good long term development.

With that cost came benefits.  Not just working code but a clearer perspective on what I needed to do and what problems would be faced by creating a slide-presentation mode.  I don’t regret the sprint at all but it certainly didn’t result in completed work.  I had to go over all of that development and turn the prototype into well designed code.  This naturally took quite a bit longer but resulted in much more coherent designs and a stronger overall structure.  This is done now and my LCA2016 presentation is now in my mainline of edlib development and works well.

There were a number of structural changes that I made while revising all this functionality, I’ll just address a few of them here.

Documents have a clearer identity

Documents need to appear in various display hierarchies where they appear on panes for editing, and they must also exist in a list-of-all-documents.  Previously the distinction between these two locations was not very clear – the same sort of object existed in both and just behaved a little differently.

Now we have two different sorts of things: documents which are well defined panes that each access precisely one document, and document access panes which appear in the display hierarchy and contains a reference to the main document pane.  Previously these referred to the document inself, now they refer to the pane which owns the document.  This has made some implementation details cleaner and hopefully will be easier to think about and work with.

The *Documents* document is now pluggable

The “*Document*” document lists all known documents.  Previously is was implemented in core code by what can best be described as a hack:  Documents were the children of the focus of the root.

Now when documents are created they call a well known command name.  Any module can register a handler for this name and so become the document manager.  That module can collect  all new documents together, provide a document which presents a list of known documents etc.  If you don’t like the module that I have created, you can make your own and plug it in.

Events always travel up the tree towards the root

Previously there was common code for events to be sent to the “focus” pane or the pane containing a given x,y co-ordinate.  That is all simplified now and the common code just moved from a leaf towards the root.  For those few cases where it is necessary to find the focus or location-based window that must be open coded.  As there are about one each of these, this is a simplification.

There is still a bit of ugliness here.  When we have a stack of windows that together perform some task it is sometime useful to find the leaf-most window of the stack.  This is not a problem for handling keystrokes as the command ‘focus’ will be the leaf-most pane.  However in other cases, particular when handling a “Refresh” the leaf-most pane is not immediately known and it must be found.

This is not particular hard to do but the current implementation seems a bit clumsy.  I’m wondering if I need to have a specific concept of a “stack of panes” where it is always easy to find the leaf-mode end of the stack.  Maybe some idea will come to me.

Next steps

While there is always lots to do there are two particular goals that I am aiming at now that the LCA2016 presentation mode is working.

One goal is to be able to use edlib as a day-to-day editor.  This requires at least auto-save and quite a collection of fairly simple functions.  Half of the task here is identifying what functionality I really need and the other half is implementing it.

The second goal is to build an email reader based on notmuch.  I have lots of ideas for this but there are lots of details to work out and they will require improvements to core functionality.

What I really need is more “long service leave” to work on this, but I don’t get any more of that for several years.

As always, code is available at https://github.com/neilbrown/edlib

Posted in edlib | Comments Off

LCA-2016 presentation is done

I’ve been busy of the last couple of months.  A number of family and personal things meant I have less time for edlib, but I had a lot to do for edlib too.  I really wanted to use edlib to give my presentation at linux.conf.au 2016 in beautiful Geelong.

As an editor with programable-everything including display it makes perfect sense to have a display made that takes some marked-up text and presents them as slides.  Multiple windows are quite straight forward, so one full screen on the data projector, and one on my laptop screen from which I can control both seemed like a good idea and ended up working quite well.  While I did have time (just) to get this all working, the result is far from polished and has quite a few ugly hacks.  So all the work is in a ‘devel’ branch of my git tree on git://neil.brown.name/edlib and github.com/neilbrown/edlib.  I’ve tagged the commit as ‘lca2016′.

The “sprint” to get it working was, I think, quite valuable.  It forced me to think a bit differently about what I had and opened my eyes to a number of the different things that applications are going to want to do with edlib.  So I saw lots of weaknesses and several opportunity.  Hopefully I will be able to explore all of those properly over the coming weeks and get all the functionality into my mainline in a form that I am happy with.

One aspect that I thought would end up as a horrible hack turned out rather nice.  I needed some way for a command in my control window (e.g. page-down) to affect the display window.  I eventually realized that the document would act like a message bus to send a message along.  The display window could request a “Recentre” message in the same way that pane can request “Replace” messages when content replacement happens.  The control window can then send a “Recentre” message to the document, and it can forward it to any listening applications.  My current solution is very specific to “Recentering”, but it will be easy enough to generalise that so that any message can be sent among different windows on the same document.  I wonder what other uses I will find for this.

Another happy idea came about because I wanted to use a slightly different background image on each slide.  There is a common background which is a photo of the sunrise over the bay on Monday morning.  Then on most pages there is also a photo of one of the many “bollard people” who decorated the water front here.  I enhanced “render-lines” to look up the “background” attribute on the pane and if that was “colour:XXX” or “image:XXX” to draw the appropriate colour or image.  Adding extra options to draw a second picture over to the right seemed the wrong thing to do.

My “a-ha” insight was to teach “render-lines” to understand a background of “call:XXX” to mean that it should call the given command.  The “render-present” (the presentation renderer) could then catch that command and draw the background.  There is still some hard-coded knowledge specific to my presentation, but if I want to add a way to describe a background in more detail, handling that in render-present — ot at least out side of render-lines — seems like the best choice.

There were two things I wanted to add to edlib for the presentation but didn’t get time.  One is a new document type which mmaps a file – typically a block device – so that edlib’s hex mode and be used to explore a block device without reading it all in.

The other was more direct rendering of the “model-view-controler” diagrams.  Each of those was generated with a few lines of “Graphviz” code.  I used “xdot” to show them on the screen, then “gimp” to capture the image and make the background transparent.  I would much rather have plugged the python code from ‘xdot’ into edlib so that the “graphviz” code could have been in my presentation and would have been rendered on demand.  I still want to do that, but wonder when I’ll give another presentation that uses graphviz style graphs…

On the whole I am happy with the talk.  The room wasn’t crowded but it was far from empty and it seems that I managed to keep people engaged.  Hopefully the videos will be available soon( … or now).  The presentation I used can be viewed if you manage to get edlib to work.  Grab the lca2016 version at https://github.com/neilbrown/edlib/releases/tag/lca2016 and follow the instruction in the last commit: https://github.com/neilbrown/edlib/commit/956605b0969a43c0ca8461cb6f9213b13039896b

…and stay tuned.  I certainly plan to continue making progress with this.


Posted in edlib | Comments Off

edlib – render-lines, what a good idea.

I had a brain-wave last week.  I thought it would take me about a day to implement but it took 3 to get it working almost reasonably and the rest of the week to polish it and create some proper use-cases to exercise it properly.  But that is done now and I am quite happy with the result.  It related to the rendering side of edlib.

Commonality among renderers

My original idea for the rendering side of an editor was they there would be a number of quite different renderers, each took a document and a pane and drew the contents of the one onto the other.  I even implemented several of there: render-text to handle a standard text document with line-wrap, render-dir to render either a directory or a document-list in an “ls -l” format – with the format being configurable based on attributes.  And render-hex which takes the same text document, but displays the contents as hex, 16 bytes per line.

Having done this I noticed that was quite a lot of commonality.  Detail were different but each render need to keep track of which part of the document was currently displayed and to be able to move that part around whenever the ‘point’ moved outside of the document.  It also needed to handle movement commands which were display-based, like ‘end of line’ or ‘down one page’.  All this duplication was rather boring and I didn’t relish writing it for the next renderer I needed which would help with file-name completion.

Rendering Components: line at a time.

My brain wave was that I could avoid this duplication by abstracting out the rendering of “lines”.  Every display I was working with was essentially line oriented.  If I could get the underlying document to provide lines: lines of text, lines of hex characters, lines of directory contents, then a single renderer could draw them all, wrapping or truncating long lines, scrolling up or down to display the point, counting lines that fit so that ‘page down’ could mean something.

One stumbling block that probably consumed half the time is that lines don’t always exist in a “text” file.  For a “hex” file, a line is exactly 16 bytes, for a directory listing it is a single entry, but for a text file it is from one newline character to the next.  If a file has a million characters and no newlines, then the it would appear to be just one line and handling that line entirely in the renderer would be clumsy.   I first explored having the renderer tell the document “it is OK to give me just some of the line if it is long” but the indeterminism there caused lots of problems.

So my current solution is to leave it to the document to manage.  When asked for a line it must always provide a line, but the definition of a “line” is somewhat flexible as long as it is well defined and stable. For example the document should decide that a line cannot have 2 characters that are on a 1KB boundary.  If that threatens, then the second becomes the start of a new line.  This might lead to some strange rendering, particularly if line-wrapping is disabled.  But it should at least be repeatable.

Rendering Components: stacking

The way I implemented the “give me a line” functionality was to send a command up the pane stack from the display pane until it reached a pane with a document.  The document would return a line.  It quickly became clear that I could insert a different pane in the stack which did something different.

So if a text document is asked for a line, it returns something between newline characters.  However if a “hex” pane is asked for a line, it asks the document for characters and returns 16 of  them formatted as hex.  More complex pipelines should be possible.

My plan for filename completion is to have a directory document with an “format attributes” pane which just presents the “name” attribute in each line.  Then on top of that I stack a “completion” pane which knows that the current prefix is and hides any line that don’t start with it.  It also allows easy movement and selection of an entry.  On top of this pane is the render-lines pane which actually draws those lines (the one which match the prefix) onto the pane (probably in a drop-down menu).

Having this sort of flexibility makes the task of writing a new renderer much less daunting so I’ll probably do more of it.  I suspect I’ll eventually need something other than “lines”.  I have in mind a “Column” renderer which expects short lines and stacks them into columns of a fixed height, and then scrolls left or right if there are too many lines for all the columns.  This is how some UIs allow selection from a large number of files.  And of course some displays might not be line-based at all – maybe a renderer that interprets SVG and draws pictures?

Details of render-lines

There is a little more sophistication needed in the document or underlying pane than just providing lines of text.  It also needs to be able to find the lines of text and map cursor position to position in that text.  It would also be nice to support attributes: bold, underline, text color etc.

So there are actually two commands that can be sent.  “render-line-prev” is given a mark and must move it to the beginning of the line, or the beginning of the previous line, depending on the repeat-count that is part of the command.  “render-line” has three modes.  In the standard mode (no repeat count given) it provides a text version of the line starting at the given mark, and moves the mark to the start of the next line.  In the ‘find-point’ mode (negative repeat count) it only renders until the mark reaches point.  Then it returns a partial line.  That allows render-lines to work out where in the pane the cursor should be.  Finally a non-negative repeat count means to render until that many characters have been produced in the line, and then stop returning with the mark only moved far enough to produce those characters.  That allows render-lines to convert a pane-position into a document position so that when you click somewhere the point moves accordingly.

To support attributes, render-lines allows the reported line to contain attributes enclosed in angle brackets: <bold,fg:red>sometext</> will display sometext in bold red characters.  This is probably a preliminary design and could well change.  To include a “<” in the displayed text, use two “<<“.

There is room for more information flow from the text generator to the line renderer.  In hex mode it is nice to have the address at the start of the line and it would be nice if that didn’t shift to the left when the content moves because of a narrow pane.  It would also be nice to allow a line to be rendered differently when ‘point’ is on it: currently lines are cached and not re-rendered until the document changes.  Treating the point-line specially would allow extra highlighting of the cursor and a “reveal-codes” like approach to WYSIWYG editing where you only see the markup codes when the cursor is on them.

So there is a little way to go still before this brain-wave if fully realized, but I’m really quite happy with how it has progressed so far – if only it hadn’t taken so long.

Posted in edlib | Comments Off

edlib – commands

It been over 3 months – maybe you thought I had given up – but no.  I had some holidays and other distractions, but I’m back and will be working fairly consistently for a while.

The topic for today is “Commands”.  Commands are a standard interface for code in one module of the editor to call code in some other module.   Various objects in the editor have  commands attaches to perform various tasks specific to that object.  To some extent you can think of commands like object methods in an object-orient system, but that is only part of the story.

In many case, commands are associated with names in a key-map.  The key maps were hinted at in my previous note about managing input, but they are broader than that and details have changed since last I wrote. So maybe that is a good place to start.

Key Maps

A key map maps arbitrary strings to commands.  They are currently implemented as a sorted array allowing easy binary searching.

All input keystrokes and mouse actions are translated to strings, such as “Chr-g” for the character “g” or “S-Backspace” for the backspace key being pressed while Shift is down, or CLick-1 for a click on mouse-button-1.  The commands associated with some of these keys perform the action directly, others resubmit the input as an action, so “C-Chr-F” (control-F) might cause “Move-Char” to be be submitted.  A different module will pick this up and handle it.

Key maps are associated with panes, so when an event happens, each pane from the leaf to the root is tried in order until one has a map which supports the event.  Documents can also have key maps.  Some panes are directly connected to a document and when that pane is being processed, the keymap for the document will also be tried.

This last possibility, keymaps on document, is a fairly recent invention so I have not explored all the implication of it yet.  I might end up finding lots of uses for this so that most actions that a document can perform are performed through commands attached to a key map.

Commands more generally

Currently there are a few places where commands are attached directly to objects rather than through a keymap, though this might change.

Specifically each pane has a separate command which is called for specific actions on that pane.  It is called when the pane is “Damaged” and needs to be redrawn.  It is called when the pane is being destroyed. And it is called if the pane needs to be cloned (to create a new pane viewing the same point in the same document).  Having one command for all of this is quite possible, but a little ugly.  So this might be combined into the per-pane keymap.  Or maybe a pane will end up with a list of keymaps.

Each document has a list of “views”.  These are often panes but can be anything else.  The word-count module creates a view on any document it wants to count.

When any change happens in the document, each view is told about the change.  A pane can note that the pane is damaged so a refresh will happen.  The word-count module can clear its cached counts so they are recalculated on need.  This telling about change also happens via a command.  It is less obvious that a keymap should be provided here rather than a single command, but further experience may suggest otherwise.

Ins and Outs of a Command

So I’ve talked about how a command is used, but what is it?  It is a function pointer with a specific interface.  It is passed a “struct cmd_info” and returns an integer.  The integer can mean slightly different things in different cases. For event handling commands, if the integer is zero, then the command didn’t handle the event and something else should be tried.  For “refresh” commands, non-zero means that children need to be refreshed even if they weren’t already damaged.

The “struct cmd_info” contains various details which can have slightly different meanings in different contexts, though much of it is fairly fixed.

  • key : the name of the event or action.  This allows a single command to handle multiple actions.
  • two panes: home and focus.  The “focus” pane is where the event should happen.  For a keystroke, it is the leaf-most pane that contains the cursor.  For a “Clone” command, it is the parent to attach a clone to.
    The “home” pane is the pane where the command as found.  Each pane contain module-specific data and the commands associated with a pane may want to access that data. It may not be in the “focus”, but it will be in the “home” pane.
  • two numbers: “numeric” and “extra”.  “numeric” is a count that suggests how many times the command should be repeated.  “extra” is arbitrary extra information that can be used as needed.  The “refresh” commands use it to communicate what sort of damage happened.  Some event commands use it to connect consecutive “change” commands that can then be grouped into a single “undo”.
  • two co-ordinates: x and y.  These are used for mouse events and any event that needs a position on the screen. They are relative to the “focus” pane.
  • An arbitrary string “str”.  This is a bit like “extra”, but for text.  The “Replace” function expects a string value to be stored into the document.
  • Finally a mark and a point.  The point is usually the location of the cursor in the event window.  The “mark” is somewhere else, if it is used. It mus be in the same document as “point”.  Together that can identify a range for a document for some action to happen.  Once I work out how select and copy/paste works, the mark might get a more defined meaning.

Some of these fields may be used as outputs as well as input.  When a “refresh” function reports that children should be treated as damaged, “extra” reports the specific damage bits.  I suspect that a “choose other pane” function (use for C-x-4-?? emacs functions) will probably return the chosen pane in “focus”.

As you can see, this is a fairly restricted set of value, but has some flexibility. I really hope that I won’t find the need to extent it too much.

One way it can be extended is to attach attributes to the mark or point.  This is how the word-count module works.  It doesn’t exactly work as a command yet, but that is the plan.  It can be passed a “mark”, and it determines word and line counts and stores them in attributes attached to the mark. They can then be examined by the caller.


I suspect there will turn out to be more opportunities to use commands.  One obvious place is to handle user-typed commands, with “M-x” in emacs or “:” in vi.  The arguments to the command could be passed via the “str”.

One place where I will need some sort of call-out functionality is for customizing renderers.  I want to encourage purpose-build renders for specific needs, but there is a place for have a fairly generic renderer that is easily customizable for simple customizations.  I imagine that if a location in a document has a “render” attribute attached, then that might lead to a command which takes some roles in part of the rendering.  So far this is just a vague idea, no details.

It seems likely that there will be real changes to the nature of a command before I am done, because it is still early days.  But I’m quite sure that the idea of a “command” as a ubiquitous tool for passing control between modules is a a good one.

The Code

I’ve decided that the code has advanced enough that I have published it – partly to ensure an off-site backup.  git://neil.brown.name/edlib holds the code and http://git.neil.brown.name/?p=edlib.git lets you browse it.


Posted in edlib | Comments Off

edlib – managing input

Commands to an editor – at least the sort of editor that edlib is designed for – usually involve single keystrokes or key combinations.  Translating those keystrokes, as well as mouse actions, into commands is the topic of this note.  Many editors also support commands that are written out with words.  Such commands are often introduced with Meta-X in emacs or “colon” in vi.  For the purposes of edlib, such interactions can be managed by creating a simple document in a small window somewhere and accepting key-stroke commands to edit that document.  Some keystrokes will “complete” the command which will make the window disappear and will perform the required action.  So word-based commands are certainly possible, but they happen at a different level.

The complex part of managing keystrokes is in tracking how they can mean different things in different contexts.  There are a number of different sorts of context that all need to be managed.

  • In today’s world it makes sense to support both “vi” and “emacs” styles of key bindings.  These are global modes which potentially affect everything – at least everything on the one display.  They determine not only how keys are interpreted but also what subsidiary modes are available.  These modes stay in effect until they are explicitly changed to something else.
  • With these there are long-lasting subsidiary modes.  “vi” has insert mode and vim adds visual mode to that.  emacs has a variety of major modes, some of which only redefine a few keys, others redefine almost all of them. These modes also stay in effect until canceled or explicitly changed, but they can be seen as subordinate to the global modes, not just other different global modes.
  • Then there are short-term modes which only last for one to two more keystrokes before the prior major mode is reverted to.  The vi commands “c” and “d” (change and delete) introduce such temporary modes.  In these modes a movement command is expected and then text which would have been passed over by that movement is deleted. In emacs C-x (control-X) enters a temporary mode were most keystrokes have an alternate meaning.
  • Numeric prefixes can be seen as introducing new modes too.  Typing ‘2’ in vi will switch to a mode where the next command will be executed twice where that is meaningful.

Search commands fit into the category of “word-based” commands though they might seem quite different.  A keystroke that initiates a search, such as ‘/’ in vi or ‘contr0l-S’ in emacs, will create or enable a small window somewhere that becomes the focus for keystrokes.  As the search string is built up incremental searching or possible-match hightlighting might update the display of the target document.  When “enter” is pressed the window will close and the originating window will receive some synthetic event describing the search.  In vi you can type “d/string” and everything up to the start of “string” will be deleted.  So exactly what happens with that synthetic event from the search box will depend on the state of the originating window.

Finding an abstraction that encompasses all of the above (and probably more) requires finding effective answers to a few questions:

  • It is clear that some state needs to be stored to guide how each keystroke is handled.  How much state exactly?
  • State can be stored explicitly, such as a number to represent the repeat-count, or implicitly by selecting a different key-to-command mapping. To what extent should each of these be used?
  • How is state changed? Should all changes between explicitly requested by a command, or should some be automatic such as a prefix being cleared once it has been used?
  • Assuming that key-to-command mapping are used, should there be separate mapping for different states, or should the mappings be from state-plus-key-to-command and some part of the state be included in each lookup?
  • If there are multiple windows on multiple documents, all in the one display, then some elements of state will affect all keystrokes, and some will only affect key strokes in a particular window.  How is this distinction managed?

The choices that edlib makes are:

  • There are 4 element of state: a ‘current’ mode, a ‘next’ mode, a numeric prefix, and 32 bits available for extra information.  The ‘mode’ is a small number which can represent both long-term and short-term modes. Some modes might be vi-command, vi-insert, vi-change/delete, emacs-normal, emacs-C-x, emacs-escape.  To enter a long-term mode, both ‘current’ and ‘next’ mode are set.  To enter a transient mode, only ‘current’ mode need be set.
  • Each pane (which can be nested arbitrarily deeply) can identify a single mode+key-to-command mapping.  When a keystroke is received it is combined with the current mode and this serves as a lookup-key for those mapping.  Look up starts in the current focus window, which is often a leaf, and continues toward the root until a command is found for the mode+key, and the command accepts it (a command can return a status to say “keep looking”).
  • The current mode, numeric prefix, and extra information are provided to the command and those values are reset (current mode being set to ‘next’ mode) before running the command.  The command can make arbitrary changes, such as restoring any of the state with arbitrary modifications.
  • Command can synthesize new requests which can then be re-submitted at the current focus pane.  These requests do not affect the current state, though the caller can modify the state before and after initiating the request.  This allows responsibility for some commands to be shared.  For example the keystroke to “move forward one word” might be translated in to a virtual keystroke which always means “move forward one word”.  Different panes which might contain different sorts of document might then interpret “word” differently.  The emacs command alt-D (delete word forward) might record current location, submit that “move forward one word” virtual keystroke, and then submit a “replace” virtual keystroke which tell the underlying document to replace everything from one mark to another with the empty string.
    When a search command, as discussed earlier, opens a search window, it might store the context that came with the search command, particularly the current mode.  When the search completes and a virtual ‘search’ keystroke is synthesize, it can include the saved search context so that, for example, vi-like editor know whether to move to, delete to, or change to the search destination.

Mouse events are handled much the same as keystroke events, except that they are directory to the leaf-most pane which covers the location of the mouse event.  State is passed in an changed in much the same way as for key strokes.

Key-up events are not tracked or supported.  mouse-button-up events will be but the details are not yet clear.  Some sort of ‘grab’ will be required so that the mouse-up goes to the same pane as mouse-down.  When an even is synthesized, it can be directed to a specific location so that, for example, drag-and-drop functionality could be implemented by the mouse-up handler sending a ‘drop’ virtual keystroke to the appropriate co-ordinates.

So far, this model seems sufficient for all of my needs.  If it turns out to be insufficient in some way, it will doubtlessly be revised.


Posted in edlib | Comments Off

edlib – displays and panes

Displaying the document being edited is, of course, very important for any editor.

I have memories of the first editor I used on Unix which was em, rather than the well known “ed”.  It actually allowed a single line to be edited “directly” rather than by using pattern substitution (s/pattern/replace/)  commands or rewriting whole lines.  It also had a ‘v’ command to view lines of context around the current line.  That ability to see what has happening helped a lot.

We’ve come a long way of course and today we expect to be able to easily see and move around the context of the place we are editing … though that “context” is usually the very simple “nearby lines of text”.

edlib needs to make it easy to provide a display of context, without mandating what that context might look like. To achieve this it provides “displays” and “panes”.  These are used for directing input from the user to the documents as well as for displaying content from the document to the user, but for now just the latter will be discussed.

A “display” is simply a rectangle that the user can see which can contain text and probably other things.  So a text window provided by the likes of “xterm”, a full graphic window in X11 or wayland, or maybe even a canvas in an HTML browser could server as a display.  A particular instance of an edlib editor can potentially have several displays of different sorts, each showing the same documents or different documents.

Each display provides a top-level “pane” which can have arbitrary children and more remote descendents.  Drawing performed in any pane is clipped to that pane and its ancestors.  Panes can be given a ‘z depth’ in which case they obscure any parts of other panes with a lower ‘z’ and which overlap in x,y space.  This allows for panes to provide pop-up dialog boxes, drop-down menus, or various other facilities.

A pane has no appearance by itself.  Something must render into it, whether that is to draw boarders, a background, or content. A typical arrangement might be that children of the root form tiles.  Each tile draws enough border to separate it from others (maybe just left-and-bottom) and then displays some document in the remainder of the pane.

A pane used to display a document might contain further child panes, maybe one per line of text, maybe two for parallel renderings of the same content in different styles.  The choice is up to the rendering code.

Each pane has a set of ‘damage’  flags which record if the pane might need to be redrawn at all.  It is expected that refresh will involve redrawing whole panes.  Which nesting level of pane needs to be redrawn will depend on the level of damage.  If just one pane is damaged and it can be redrawn without changing its size, then maybe only that pane needs to change.  Damage is normally detected when a document signals a viewer that the document has changed, and the viewer determines that this could affect some particular panes.

Implementation status

As yet the only display driver that I have implemented in an ncurses based driver to run in a terminal window. A tiling pane manager is available to divide a pane up horizontally or vertically, and a document can be viewed within any pane, complete with (very simple) scroll bar.

Working with a pixel display will clearly provide challenges that are not met when working on a simple character based display.  I suspect that I will make it possible to treat a pane in a pixel display just line a character based display, and will allow panes displaying different parts of a document to use different font sizes but still be simply character based.  This could make it fairly easy to use large fonts for headings in mark-down, or smaller fonts for text that is further away from the cursor and so probably less interesting. Lots of experimentation is needed. Support for images and general curves is important too.

I imagine that it will be useful to be able to display HTML and I don’t want to write an HTML renderer.  The idea of allowing webkit to display in one edlib pane is very appealing.  It probably wouldn’t be very useful for editing a document, but for simple display (an important role of an editor) it could provide just what is needed.

Posted in edlib | Comments Off

edlib – because one more editor is never enough.

I’ve decided to write an editor.  Silly idea I know – there are already two out there: both vim and emacs are quite good.  I’ve heard rumors that there might be others, but investigation always shows they are just toys, not real editors. They don’t support reading email, unless that is all that they do.

And I know that I’m supposed to be designing a new language: ocean.  And I will… maybe.  But how can one write code for a new language without a new editor (though one could equally wonder what language a new editor might be coded in if not a new language…).  Ocean will have to wait.

So why a new editor?  Well I really love emacs.  Really.  But I also hate it.  I’ve tried programming in emacs and I just can’t manage it.  It isn’t just the LISP (though that doesn’t thrill me), it is the  low-level hacking at the attributes in the buffer to create the image that I want to display.  It feels like assembly programming.  It is probably a personal weakness on my part – other people seem to manage.  But isn’t it always out of personal weakness that great genius emerges?  I’m sure it is.

I’ve tried writing an editor before, as recently as last year and as long ago as my honours year at University (1986).  Each time I failed to produce anything even vaguely useful.  A big part of my problem is that I tend to let the perfect become the enemy of the good.  Whether that is the real reason I’m not sure, but I know that fact is true, and I know that I consciously tried to fight it this time.  And I’ve made a lot more progress in the last few weeks than I ever did before.  So maybe I’ve overcome my personality flaw, or maybe I just stumbled onto a good idea.  Which part of the design that good idea might be I’m not sure.  So I’ll have to just write about all of it.

Let’s start with the name: edlib.  This very deliberately pays homage to emacs.  emacs is short for “editing macros” or something similar.  It describes the technology used to build the editor.  “edlib” is short for “editing library” – again it is the technology.  edlib will (hopefully) become a library of sensible interfaces and useful implementations which can be combined to build an editor.  Any editor.  But “edlib” is also the name for a specific editor that I will build with this library.  The interfaces are important.  Creating clean abstractions that are combined through good interfaces will what will make (or break) edlib.

The general structure of the library follows the Model-View-Controller (MVC) pattern.  This highlights what I really don’t like about emacs: the model is not well separated from the view.  In edlib it will be.  Today I will write mostly about the model.

Documents: the model of editable data.

Anything that is edited or viewed in edlib is stored as a ‘document’.  A document combines a number of ideas:

  • A list of characters.  These are Unicode characters and a probably encoded with UTF-8, but each document can make independent implementation decisions there.
  • Attributes on the characters.  There are name=value pairs.  Attributes apply to individual characters, not ranges of characters.  The intention is that they record parse summaries or state information.  Code that interprets attributes may have to look around to find them and may have to interpret them in non-trivial ways.  For example apparent spelling mistakes might have an attribute attached to the first character in the word.  It might list some possible corrections.  A matching “view” module would notice that and highlight the whole word.  A related controller would provide a way to select from the possible corrections.
  • Marks identify locations in the document.  Each mark is between two characters, or at the start of end of the document.  Marks, like characters, can have attributes.  Marks are more heavy-weight then just attaching attributes, but marks are easy to find: they are linked together and can be stored in separate data structures.  Makes can identify temporary locations for communicating ranges between different modules.  They can identify the parts of a document being displayed in a particular view.  Or they can identify anything else.
  • Undo/redo support would be integrated into the document.  Each document keeps a list of recent changes, and can revert or re-impose them.  All changes are described as a “replace”.  Two marks (actually a point and a mark) identify a range to be deleted, and a string provides replacement.  Either the range or the string can be empty of course.
  • A “view” is a particular collection of marks together with a special mark called a “point”.  The marks in a view are in their own list (and also in a global list) so they can be found from each other easily.  When an change happens in the document, each view is notified and the preceding mark is mentioned in that notification.  This allows each view to easily determine if anything important has happened.
    To enable this, every change must happen at a “point”.  A point is a special mark which exists one per view, and which is linked into the point lists for all views.  A view which does not modify the document might not have a point.  Any view which can modify must have exactly one point.
    An obvious use of a view is to connect a document to a display window.  The marks might be the start and end of the displayed region, or they might be the start of each line that is displayed.  But there are other uses for views.
    A “word count” view might keep marks every 100 lines in the file, and record at each mark the count of lines, words, characters from there to the next mark.  Whenever there is a change, the counters at just one mark can be quickly updated.  Whenever the counts are needed, a sum over the relevant marks will accelerate the count.
    Another view might perform a spell-check on any changed text, and might set attributes to record the result.  Yet another view could parse some code and keep a symbol table reasonably up-to-date.
    Ultimately these different views could run in separate threads, particular if part of the task can be time consuming.

Together these ideas seem to form a powerful abstraction.  It is fairly obvious how this would apply to a text document read from a file, and that would be the most common document type.  Other possibilities include:

  • A file could be memory-mapped, and might only allow replacement where the deleted region matches the size of the added text.  This would allow even a block device to be mapped so that the editor could view raw data on a disk drive, and maybe even edit metadata that it has been taught the format of.  A hex-edit view would be particularly appropriate here.
  • Reading a directory into a document could involve creating a single character for each directory entry, and then attaching the name, owner, modes, type, date etc as attributes of that character.  This directory could then be displayed in various way to allow selection of a file name to load, or to allow more general directory editing.
  • A “virtual” document might itself provide a view on one or more other documents.  This could be used to view a collection of files as just one, or could present a “diff” view of two documents, with common sections only displayed once between differing sections.
    One awkwardness with the described directory document is that while it is easy for different displays to select different attributes, it is not clear how a different sort-order could be achieved.  A “virtual” document on a directory could impose a separate sort order, using a list of marks with one mark for every directory entry.
  • The editor would almost certainly contain a list of active documents.  This list itself could be stored as a document, as could other internal data structures which could usefully be viewed.

There are of course lots of other possibilities, but just those are enough to allow a very versatile editor to be built.  A key property of these documents is that they are linear lists of characters.  They have a first and a last and probably some in between.  Marks are very linear too, being linked together in text-order.  This does limit the range of documents to some extent.  For example an image doesn’t really fit this model (though a video might).  So I don’t really expect an image editor to ever be built with edlib. A mail reader, though, is an absolute must.

My implementation so far has just the one document type: a text read from a file supporting arbitrary edits and indefinite undo.  Just recently I completed the clean separation of that from the rest of the code so that a second document type (probably directories) can now be implemented.

And no: the code isn’t available yet.  It will be, but not until I want other people to look at it.

Posted in edlib | Comments Off

Structured statements and expressions in Ocean

Now that I have my general parsing worked out and understand how I want to use indents and line breaks to give a two dimensional structure to my language, I need to think about the details of some of the elements of the language.  The part of a language that we use the most is the part which does stuff: statements and expressions.  So that is where I will start, though particularly with statements.

As has previously been hinted, blocks of statements will have  two different syntaxes that the programmer can choose between, one Python-like and one C-like.

Block -> : StatementList
       | { StatementList }

This is a simplified version of the grammar, but the idea is that a StatementList can follow a colon, or be enclosed in braces.  In the first case the StatementList must be terminated by a decrease in indent.  i.e. all of the StatementList must be on the same line as the colon, or indented with respect to the line containing the colon.  When we find a line with the same indent as the line with the colon, we know the StatementList is finished.

In C, any expression can be used as a statement simply by appending a semicolon, and various thing that you might think of a statements – such as assignment – are syntactically expressions.  In GNU C (i.e. C as implemented by GCC) you can even convert arbitrary statements to expressions by enclosing them in “({” and “})“.  This synergy between statements and expressions can be very powerful, but can also become ugly and confusing.  It works well for small statements placed where  expressions are expected, but quickly breaks down as statements grow.

“Rust” takes this synergy to it’s logical conclusion and every statement is an expression – there is no difference between statements and expressions.  So you can write things like

a = if some_test {
     } else {

I personally find this becomes clumsy.  Also as I wrote for lwn.net, it creates some oddities in how semicolons are handled.

“Go” deviates from C in the other direction and allows a much more limited interplay between statements and expressions.  Assignments and increments become true statements, but in a few places were you would expect an expression, a simple statement is allowed as well.  So:

while line, ok = readline(file); ok {
         do something with line;

allows a simple statement before the condition in a while. This is certainly useful, but seems a bit artificial.  It solves many cases, but isn’t really a general solution to the problem.

I like allowing general statements in the head of a while and similar places, but I don’t want to make them look like expressions – I still want a clear distinction.

So a while statement will have two forms

WhileStatement -> while Expression Block
                | while Block do Block

The first form is the one we are familiar with, though it is more like “Go” than “C” as the expression does not need to be in parentheses.  The second form allows for more complex calculation of the loop test.

Naturally the first Block in the second form must return a value somehow to guide the progress of the loop.  This is somewhat like the “return” statement in “C” which can return a value from any point in a statement block.  Using “return” in this “while” Block would be confusing as the normal expectation would suggest the meaning was to leave the containing function.  Instead I’m planning to use “use” as a keyword.  That is certainly open to change after experimentation, but it is close to what I want.  So:

     line = readline(file)
     use not line.matches("END"):
     print line

is a contrived example which shows how the “use” keyword might be used.

A noteworthy aspect of this example is that the “condition” part is larger than the “body” part.  One could go even further and imagine a body part which was simply “pass”.  This would result in a loop much like C’s “do {} while()” loop.  It may not be quite as good, as the terminating condition doesn’t syntactically stand out, but careful placing of the “use” statement can make it stand out well enough.

This generalises to having largish “condition” and “body” parts, thus allowing loops which exit in the middle and answering Dijkstra’s “n and a half loop” problem, as discussed particularly by Knuth in his Structured Programming with go to Statements.

In that article, Knuth also talks about “event indicators” which he credits to C .T Zahn. These are an attractive idea and fit quite well if we allow these expression statements in a switch construct.

      some code which can "use" multiple different values
case value1:
case value2:

Naturally the type of each of the values listed with “case” clauses must be the same as the types of values given in “use” statements.  For “event indicators” Knuth suggests that the list of allowed events might be given at the top of the statement.  This might make life easier for the compiler, but seems unnecessary.  We could allow that if all of the “use” statements give currently undefined words, and if all of those words appear after a “case” tag, then the words are taken to be values in a new anonymous enumerated type.

These enumerated values would behave a lot like “goto” labels, in that they must appear once as a target and must be used, but otherwise do not need to be declared.  Indeed, there is a lot of similarity between these “event indicators” and goto targets, and I would not consider adding a general “goto” until experimentation with the event indicators showed they weren’t enough.

In Knuth’s paper, the  event indicators can be used in loops as well as non-looping statements.  In “C”, a switch doesn’t loop,  so we clearly haven’t attained complete functionality yet.  Without detailing all the steps, all these above thoughts lead to the idea of a general structured statement with several components:

for  BLOCK or simple statement
[if | while | switch] BLOCK or condition
then BLOCK
else BLOCK
  • for” provides preliminary code which is only run once.  It may declare variables which remain for the entire statement, but it contains no “use” statements.
  • if“, “switch” and  “while” are much as you would expect and if they have BLOCKs, those BLOCKs contain “use” statements, the value of which guide the execution of the other components.
  • do” is only present with “while” and just runs code providing the condition doesn’t fail.
  • then” and “else” are run if the condition or BLOCK returns “True” or “False” respectively.  As such, they are somewhat equivalent to “case True” and “case False
  • the “case” stanzas allow the condition to return a variety of values.  If none of the “case” values match, then the else” clause is used if present.

If the values returned by the condition in a “while” are not Boolean, then it isn’t immediately clear which values cause the “do” block to run and the statement to loop.  My current thinking is that if the condition does not return a value at all, then that is equivalent to “True”, in that the “do” block is run and the statement loops.  If the condition returns any value other than “True”, then the loop aborts.

If a (“while“) loop starts with a “for” clause, then there can also be a “then” clause after the “for” and before the “while“.  Despite its positioning it is run after the “do” part if the condition didn’t fail.  This allows an effect similar to the C for loop:

for a = 0
then a += 1
while a < 10
do sum += a

There are aspects of this that feel clumsy, though I suspect they can be resolved.

  1. Requiring the ‘then’ keyword isn’t good. If the condition is a block then it makes sense, but if it is just a condition, then it isn’t wanted. So:
    if condition:
        use condition
  2. A large switch statement has no obvious end.  If a new line at the base indent level starts ‘case’ or ‘else’ then the switch statement continues, otherwise it is terminated.  This fact has some precedent in that languages with an “elseif” keyword can have a list of clauses each beginning with “elseif” which is only really terminated by a line that starts with something else.  That doesn’t seem to cause confusion, so maybe “case” with no termination won’t either.
  3. The word “then” isn’t quite perfect for the “increment” part of a “for” loop.  It isn’t too bad as one could say “while this do that and then the other” so “then” suggests something to be done a bit later.  It might just take some getting used to.
  4. I’m not even sure about “use“.  I like the concept.  I don’t much like the word.  I really don’t want a bare expression where you might expect a statement and that could be syntactically confusing.  I wonder if “select” would work, as it selects the case to exit through.

At this stage I am not planning on including “break” or “continue“.  “break” can sometimes be achieved with “use false“.  In a few contexts, “use true” will do the same as “continue“.  There might be times where these directives are still wanted in the “body” of a loop, but I hope not so I will wait until I find some convincing evidence.

This certainly isn’t the final word on loops.  At the very least I expect to add a “foreach” loop to work with some sort of “iterator” type.  However I cannot really explore that until I have a type system.

For now, I have  put together a simple interpreter which allows some experimentation with the loops and conditionals discussed here.  Now I need to think of some interesting loops and selection code that I can try it out with.

The interpreter is in my ocean git tree (git://ocean-lang.org/ocean), or you can read the literate source code.

Posted in Language Design | Comments Off