Complex documents in edlib

One of my core goals in developing edlib is to allow the display to be programmatically controlled: the content of a document is formatted dynamically as it is displayed, and so can respond to context (e.g. location of “point” can modify appearance more than just by displaying a cursor) and also so that the entire document doesn’t need to be rendered into a buffer, just the parts being displayed.

A natural (for me) extension to this idea was the possibility that the source of the display wasn’t just one single document – multiple documents could be blended. Various examples have occurred to me, though few have been implemented.

I have a “hex-view” mode which displays a document by showing each byte as hex. To edit such a document conveniently I would like to transparently replace a particular hex field, in the view, with a tiny text document which contains the individual hex characters.  I could then edit that and the hex value I entered would be decoded into a byte (or bytes) that would be stored in the main document.  Thus the display is partly the main document, and partly the little entry document.

I imaging a “diff” mode which shows the difference between two documents. The part of the view which contain lines from either document could be a reference to that document.  This way, editing the lines in the diff would directly edit the original.  The display, in this case, would contain parts of one document interleaved with parts of another.

I have an email reader that can display multi-part email messages. This effectively divides the email document into multiple sub-documents, decodes them as appropriate (e.g. BASE64, quoted-printable) and then displays a combination of these individual parts, with buttons to act on the parts, and some headers at the top.

Finally, this same email reader can display a list of summaries of messages.  This is a complex document in a different way (and I’m wondering if I’m confusing different sorts of documents together – which is why I writing this note).  The list of messages is actually a list of threads where each thread is a list of messages.  I sometimes want to display one line for each thread, sometimes I want one of the threads to instead display as a list of (non-archived) messages, and sometimes I want to only see the messages from a single thread, but I want to see all of them (including archived).  I currently implement this as complexity in the document, but maybe it should all be in the display.

Reality hits.

Most of these thought came about in early design.  I thought that I could easily have a display which showed parts of multiple documents and could easily move about on the virtual document simply by being in control of the view.  It turned out that I was wrong, or at least overly simplifying.

Key to understanding the link between documents and views is understand how the “marks” work, particularly the cursor or “point” that each view holds in a document.  Each document has a set of marks which are kept in an ordered list.  Each mark has a (non-contiguous) sequence number so ordering between marks is easy to check.  The current cursor in each view is one of these marks.  Marks are also used for lots of other purposes to keep track of locations in documents.  This storage of marks has two particular implications for managing complex documents.

Firstly, a view can only display a single document – the document which owns the cursor mark.  It would be a substantial extra complexity for the cursor in a view to be allowed to move from one document to another.  Secondly, the view of a document cannot change the order of  elements in the document.  Doing that would confused the ordering of marks – marks could have a different order in the view than in the document.

In some cases these limitation can be hidden by using a temporary auxiliary view.  In the hex-editor case, a viewing pane that is just a few characters wide could be displayed over-laying the view on the main document.  This secondary view would display a different document – one which contains the individual hex characters.  Some deliberate action would be needed to place the view, and then to discard it again.  This could be conceptually like a pop-up window, but would not have a border and so would appear to be part of the main document.  A similar approach could be used for the ‘diff’ example.  A particular prerequisite for this approach is that the main document and the secondary document have the same appearance for some range of characters, so rather than mixing two documents together in one view, we display two different views but place one over the other so it looks like just one view.

In other cases the limitation can be removed by creating a virtual document.  This document has its own set of marks, and maps them to marks in the underlying document as appropriate.  The view just displays the virtual document, which returns content from one or more subordinate documents.  I have implemented a “multi-part” document which does exactly this.  It maintains a list of documents and concatenates them. This is how email messages are displayed.  Once I realized the necessity of this it was fairly easy to implement and it made the display of multi-path documents manageable at last.

On case for which there isn’t an easy solution is when there is a need to re-order content, such as when displaying the headers of an email message.  It is good to present headers in stable order, such as From, To, Subject, Cc.  The headers in the email document could be in any order.  A virtual document could split the headers into individual documents and recombine them, but I’m not sure it is worth the effort.  My current solution is to just copy the headers that I want into a fresh text document, and display that.  As I have no desire to edit the original, I don’t lose any functionality by doing this.  If I wanted to edit a document that was stored in the “wrong” order, I might need a more complex intermediate virtual document.

Problems

Now, at last, I get to the issue that I wanted to think through.  Several documents have selective visibility.  The multi-part document used for email will normally hide parts that probably aren’t interesting (e.g. HTML versions of messages), but it must be possible to display them if they are wanted.  I’ve already discussed the slightly more complex selective-visibility needed for the email summary list.  I also need selective visibility of the document which contains a list of all documents.  When performing “save-all”, I display this document in a view where documents that don’t need saving are not visible.  I currently have three different ways to implement selective visibility, and I think that it is more than I really want.

For the “modified only” view of the document list I have a view pane which captures the low-level commands for moving a mark (particularly “doc:step”) and cause it to step over any document that is not “modified”.  So if it finds the document pointed to cannot be saved, it transparently moves to the next document.  This makes cursor movement, display, and everything else “just work”.  This is probably the best approach.

For the multi-part document I currently store the “is it visible” state in the document.  This makes is a little awkward to get information about the invisible bits, but I found a reasonable way around that.  The main problem is the two views on the one email message will have to show the same parts, and that isn’t a good idea.

For mail messages I have an in-between sort of approach.  The document manages all the movement of marks, but the view tells is what how to choose.  When a movement comment (such as “doc:step”) arrives at the view, the view adds a couple of values that are not normally used for that command.  “str2″ is set to the thread-id of the thread of interest, and “xy.x” is set to 0 or 1 depending on whether that thread should be expanded in context, or should be the only thing displayed.  This works well and has a good division of labor, but feels like a hack.  Overloading fields isn’t really a problem – that fact that I have a limited set of fields in commands effectively requires that.  But this puts a limit on the sorts of views that are available – a limit imposed by the document.  That puts the decision in the wrong place.

Solution?

Ideally the document would know nothing about visibility.  That means the view needs to be able to efficiently skip over invisible content itself.  For “modified” documents it simply gets some attributes and checks them.  This isn’t very efficient, but there aren’t enough documents that you would notice.  For multi-part the view could keep a list of marks for each part-start, and could attach visibility info to those – finding nearby marks given a point is designed to be fast.  For the email summary list, it would be necessary to be able to skip to a particular thread (rather than individually step over each message in each thread).  That could probably be done once, and a mark left behind.  Leaving marks at significant places certainly seems like part of the solution.

Another part might be to pass a predicate function to the “move” command so it can more quickly step over unwanted locations.  Having a pane call “step-forward” over and over again is not very efficient as the step command has to search down the pane stack to find the document.  If we pass a function the step-forward command, it could call that at each location and keep moving until it succeeds.  This would have an added benefit of making “search” a lot faster.  Currently it is slow because the “step-forward” command to get the next character is slow as it hunts for the right command.  If that can be short-circuited with a callback, it might run much more smoothly.

Summary!

  1. complex documents where there is a base document and others which provide the same content from a different perspective should be easy enough, though they need some sort of deliberate action to activate the alternate document
  2. complex documents which each provide different content must use an intermediate virtual document.  I could even re-order things, but only be dividing the original up into separate pieces, then re-assembling them.
  3. views that control visibility must put all the decision making in the viewer, but might used special movement commands provided by the document (such as ‘move to next part of a multipart’ or ‘move to next thread’).  They can expedite things by leaving suitable marks around, and by passing a predicate function to the “move” command.

I think I now need to review all my movement commands, and how I get characters and attributes from a document.  There is probably room for unifying things there.

Posted in edlib | Comments Off

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.

Futures

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