LR parsing with line-breaks – yet again

Posted on June 24, 2019 by neilbrown

It has been some years since I last wrote about about parsing with indents and line-breaks. Some of that time I’ve been distracted by other things, some of it has involved working on other areas of language design, but some of it has seen me struggling with line breaks again.

In my last note I had made significant progress over my original design, and there is much in that note that is still valuable. But some of it I got wrong too.

Most particularly, the idea that NEWLINES should be separators rather than terminators was mostly wrong. I now believe they must be mostly thought of as terminators, though there is one area where we must blur our definitions a little.

A related area that I’ve been struggling with is handling blank lines. Since NEWLINES are parsed tokens, we need to be prepared to accept and ignore those that we don’t really care about. As blank lines are usually uninteresting (in program code at least), I need explicit support in our grammar to allow them. What this support must look like has caused a lot of head-scratching, but I seem to be happy with my current approach. Part of the reason that this was a struggle was that at the same time I was trying to make sure there weren’t any newline related conflicts in the grammar. I thought these were somehow related to the multiple newlines issue and while this was probably the case, there was a whole others side to parsing with indents and newlines that I had forgotten to think about. So I’ll need to discuss blank lines and this other issue.

But first to NEWLINES as terminators.

As I hinted in my last note, treating newlines as separators can cause expressions – when they appear at the end of a line – to look line-like, as they are followed by a NEWLINE. I suggested that care should be taken in the grammar to not put the NEWLINE immediately after an expression, only after a whole line-like thing.
e.g.

statement -> IDENTIFIER = Expression
statementline -> statement NEWLINE

However that is not sufficient. The NEWLINE is still assessed as being “after” the Expression (it is in the look-ahead set) so the Expression needs to be treated as line-like, and that is no good as we don’t want line breaks in indented expressions to be syntactically meaningful.

So I went back to using NEWLINES as terminators, but with a simpler measure for “line-like” symbols. Any symbol that can possibly derive a sentential form (i.e. a code fragment) which contains a NEWLINE is line-like. It doesn’t matter where in the fragment the NEWLINE is; start, middle, or end. If there could be a NEWLINE, then it is line-like. This is easy to think about, easy to code, and largely works.  Putting a slightly different perspective on this, if a symbol can “contain” a newline, then newlines must be important when parsing it, so they mustn’t be ignore.  So if we are in any state between starting the parse of a NEWLINE-containing symbol and ending that parse, and we haven’t seen an indent, then we need to pay attention to newlines. This is exactly the consequence of marking the “before a NEWLINE containing symbol” state as “starts line”

I’ve had one problem with this approach and it comes from a syntactic form that I mentioned previously, and is probably the one that pushed me to think of the newline as a separator.

if condition: simple statement

This line contains two statements, an “if” statement and a simple statement. I slight extension could even contain three:

if cond1: if cond2: simple statement

This form might seem unnecessary, but I want to allow it for generality’s sake.

If every statement must be terminated by a NEWLINE (or a semicolon), then this must be followed by two (or three) NEWLINEs. I hope it is obvious that requiring a blank line after this construct would never do.

I experimented with various modifications to the grammar and approaches to NEWLINE handling and most of them failed, often because they got too complicated and I couldn’t really understand the implications of what I was trying to suggest.

My solution is to add a special marking to the production, much like the marking that can be used to indicate precedence of operators. If a production ends with $$NEWLINE then it is handled a bit differently.

Block -> { Statements }
       | : Statements $$NEWLINE
       | : SimpleStatements $$NEWLINE

This means that when a code block is introduced by a ‘:’, it must be REDUCED by a NEWLINE. That is, a NEWLINE must be the look-ahead token. The NEWLINE isn’t shifted, so it can serve to reduce several of these, depending on what indents are in play.

This only works, of course, if Statements and SimpleStatements don’t have to end with a NEWLINE. SimpleStatements doesn’t. It needs a NEWLINE to be part of Statements, but not otherwise. In many cases Statements will end with NEWLINE, but not always. Particularly if the last statement ends with a Block there won’t be a newline required at the end.

Initially I found that this is the only place in the grammar that I need to have $$NEWLINE. Everything else works fine with the other rules that I had developed. However once I realised the big issue I’d been missing, I found a couple more places it was needed.

The other issue I struggled with is parsing blank lines.  I don’t recall all the things I tried and why they didn’t work, but I do know that pattern that ended up working well.  Importantly, this works well for optional NEWLINEs.  It is easy to end up with places in the grammar which could be preceded by something that ends with a NEWLINE, or something that was marked $$NEWLINE.  In the latter case there must be a newline following, in the former there may be.  The pattern that I use works well for both of these cases.  When you have any non-terminal that can, and possibly should, appear one a line by itself, you provide an extra production for that non-terminal which is left-recursive and adds a NEWLINE at the end. So

Line -> Type1line
      | Type2line
      | Line NEWLINE

This approach ensures that each type of line can be followed by arbitrary NEWLINEs, and that if some type of line is only marked as $$NEWLINE – meaning it must be followed by a NEWLINE – then the parser will expect and accept a NEWLINE after it.

This covers all eventualities except for NEWLINEs at the start of a sequence of lines.  For that case, we can use a right-recursive rule to put NEWLINEs at the start.

LineBlock -> Lines
           | NEWLINE LineBlock
Lines -> Line
           | Lines Line

Keeping LineBlock separate from Lines is not essential for handling blank lines, but as mentioned in a previous post, left-recursive productions cannot be closed fully by the end of an indent, unless they can be reduced into some other non-terminal.  Here LineBlock provides that other non-terminal.

One problem with this pattern is that if there are a large number of blank lines at the start of a block, they will use up a lost of that parser stack – that is a property of any right-recursive form in a shift/reduce parser.  If this is at all a concern, it can easily be alleviated by introducing a left-recursive rule for consuming the blank lines:

Newlines -> NEWLINE
          | Newlines NEWLINE

LineBlock -> Lines
          | Newlines Lines

This will recognise the blank lines at the start of a LineBlock equally well, but will use only a fixed amount of the parser stack.

I have started using these two patterns consistently, and my problems with blank lines have gone away.

So now I’m just left with one remaining issue to discuss and I think I’ll be done with parsing newlines.  I need to explain and resolve my blind spot.  This blind spot relates to error detection.

When I started thinking about parsing with indents and line breaks, I was focused on correct programs and finding a way to parse such programs correctly – in part this meant understanding what “correct” means in this context.  So I identified the various rules for when an “OUT” token or “NEWLINE” token should force a a reduction – so that everything in the two-dimension space closed by that token would be fully parsed before we moved on.  There is a flip-side to this that I didn’t consider.  The flip-side of allowing these special tokens to reduce production, is requiring them too.  i.e. in some cases, any other token must be an error.

As an example case where this is important, imagine a language where the word “function” introduces the declaration of a function, and there is no specific terminal to mark the end of the function, it depends on indentation information.  So

function foo(args):
       statements
function bar(args):
       other statements

could be two functions.  In this language, nested functions are not allowed, so the word “function” can only appear at the outer level.  If the parser for such a language is given

function foo(args):
        statements
        function

it needs to see this as an error.  With the initial rules I formed for parsing, that wouldn’t happen.  When the parser sees “function”, that would reduce the statements, and then the function, and then start parsing a new function.

The solution to this is very nearly the solution I discussed at the start of this note, marking some productions as “$$NEWLINE”.  There are three different things that I’ve found that such a marking might need to mean:

  • This production must be reduced by a NEWLINE
  • This production must be reduced by an OUT (end of indent)
  • When reducing this production, we must be at the start of a line, with no pending indents since the start of the line.

It is possible that each of these mean close enough to the same thing.  In my current implementation I have two marks, “$$NEWLINE” and “$$OUT” which both have the same effect, that being to require any one of those three conditions to be true when the production is reduced.

The important part of this last part of the discussion is how I now think about these markings.  They are explicit statements on how as two-dimensional region of text must be closed.  Thinking about it this way lead me to realize that I had placed the markers at the wrong place before.  To support a syntax like

if condition:
      statements

I had defined a Block as

Block -> : statementlist $$NEWLINE

I now think this is wrong.  It requires the “: statementlist” to be terminated, but it is really just the statementlist that needs to be terminated.  So now I want

Block -> : statementblock
statementblock -> statementlist $$OUT

One practical consequence of the difference is that in the new grammar I can indent a following else:

if condition:
       statements
   else:
       statements

In this, the “: statements” is not yet terminated, either by an OUT or a NEWLINE, when the “else” is seen.  But the “statementblock” is fully terminated, which is what I want.

The other place that I found to put “$$NEWLINE” is at the end of any “complex” statement such as if/then/else or while/do.  It is likely that such statements will end with a “Block” (as defined above) and so they don’t have an explicit NEWLINE at the end, though they may still end with a NEWLINE in practice.  By marking it as “$$NEWLINE” I can be sure that it there is no way that another statement can appear in the same 2-dimensional space.  The next thing, whatever it is, must at least be on a new line.

One thing I’m still not completely resolved on if whether it is sufficient to have just one marking (Current spelled either “$$NEWLINE” or “$$OUT”) or whether I need two, or even three, different markings to handle distinct cases.  It seems that just one is enough, but I need a lot more experience working with the grammar to gain any sort of confidence.  For now, I only know that this approach seems to be working more smoothly than what I had before.

Posted in Language Design | Leave a comment

Local variables and scope

Posted on February 20, 2018 by neilbrown

While I was writing test code for my first toy language I particularly noticed the lack of interesting data structures:  to write interesting loops you can do a lot more if you can build data structures while doing it.  So my second toy will begin to introduce data types. It won’t be until a later iteration before we get structures though.

The first step to this is knowing  how to declare variables, or local bindings.  Then I’ll have something to attach types of data structures too.  So this installment is about local variables and their scope.

I started writing this 3 years ago and am only publishing it now.  Sometimes life works like that.  I had to wait until the code worked and I managed to lose interest for a while and get distracted by other things.  At the recent linux.conf.au I went to a talk about the language “Pony“.  While I’m not thrilled with pony (I don’t currently think that expressions and statements are interchangeable), the talk inspired me to get back to ocean…  So what can we say about scopes?

Why we need scope

Several languages don’t bother too much with the “scope” of variables.  Such languages usually have just two scopes – local to a function, and global.  In Python and TCL, variable assignments only create a local binding unless the name is declared to be global, in others such as the “bash” shell, all assignments have global scope unless explicitly declared to be local.  In these language, accessing a binding will prefer a local binding if there is one, and otherwise will make use of a global binding.

While this makes it easy to write code (no need to pre-declare everything), it also makes it easy to write bugs and harder to read the code.  Typos in variable names can be hard to detect, and the intent is not always clear.

Some of the problems can be reduced by static analysis which requires that a variable always be set before it is used, and possibly always be used after it is set. This helps reduce the bugs that are written, but it doesn’t make the code much easier to read.

Having clearly defined, low overhead scoping rules should make it easy to write code, easy to read code, and harder to write bugs.  That is my goal.

Variable declarations

The variable declaration style of C has a certain elegance, but it does not scale well.

int anumber;
char *string;

is quite readable and easy to parse.  But once you introduce typedefs, the type name (“int” or “char” here) becomes just another identifier so you need to know whether an identifier refers to a type or something else to be able to parse correctly.

Being able  to declare a list of integer variables as:

int first, second;

is nice enough.  For more complex types it becomes much less elegant.  A list of pointers to functions returning char pointers  is

char *(*fun1)(), *(*fun2)(), *(*fun3)();

So C isn’t a good model to follow.  The other model that is familiar to me comes from Pascal

name : type-expression

In Pascal, these declarations must come in a special “var” section, but as C has shown, that isn’t really necessary.  For Ocean, I will combine this with assignment to create a simple statement that can declare bindings and give them an initial value.

name : type = value
name :: type = value

The first form declares the name to have the given type, and binds it to “value“.  The second form creates an immutable binding: the name cannot be assigned a new value or otherwise modified.

In each case the “type” can be left out in which case it will be deduced from context, possibly just from the given value, possibly also from how it is used.

found := True
pi ::= 3.14159
radius := 12

“found” is clearly Boolean, “pi” is probably float (or double), but “radius” could be an integer or floating point or even complex, depending on what else is done with it.

It is probable that I need to allow the value to be absent too, so “foo : myrecord” might be a legal declaration, as providing a complete initial value may not be practical. For the moment I will assume a value is always required but will revisit that assumption when structs/records and arrays are introduced.

Here the “:=” or “: type =” should be enough to help the reader (and the compiler) know that this is a new variable  (or binding).  If there is no such declaration near by, the name must be global (assuming we permit global names).  If there is, then the name is local.

Typos in name usage will easily be caught because there will (most likely) be no declaration for that name.  Typos in name declarations will likely be caught because a name will be used without having been defined.  There are more subtleties that need to be considered though, firstly the issue of “hole in scope”.

No hole-in-scope

A “hole-in-scope” happens when a binding is declared for a name that is already bound.  As long as the new binding is active, the original binding is hidden and so there is a hole in the scope of that outer binding.  This is quite permissible in C, where a local declaration can use the same name as the global declaration, or a local declaration in a containing statement block. So the following is perfectly legal.

int foo;
func() {
   char *foo;
   if (foo) {
       float foo = 1.0;
   }
}

Such behaviour is, I believe, unsafe.  It makes it too easy to use one binding when you meant to use another.  If you are very familiar with the code such mistakes are unlikely to happen, but if the code was written by someone else, or by yourself some time ago, then mistakes are easy.

Disallowing holes-in-scope sounds like a good idea, but it has an important implication.  It means that the set of names in the global context is never allowed to change.  If it does, a working program might break.  This would happen if the previously working program bound a name which was subsequently introduced into the global scope.  The internal binding would create a hole in the scope of the global name, which cannot be allowed.

This issue extends beyond fixed global names – which should be kept to a minimum anyway.  If we had a python-like mechanism for importing modules, such as

from MyModule import *

then it would become impossible  to add any exported  names to “MyModule”, as they would enter the global scope and could  cause conflicts.  This could be fixed by requiring explicit listing of names:

from MyModule import this, that, the_other

but that is clumsy and  verbose – it doesn’t make life easy for the programmer.

Instead, each module will have some mechanism for identifying a group of symbols to be exported.  These might reasonably reflect different versions of the module interface.  Using this, the import statement might become

from MyModule import v1.1

Which would be a well defined set of names that would never change.  If the module needed new interfaces, they would be included in other versions, but not this one.  When the client program wanted to use those interfaces it could be changed to import “v1.2”, and at the same time any binding that now caused a conflict could be resolved.

It is too early in the design process to finalise the module import mechanism, so this is just indicative.  What it indicates is that avoiding a hole-in-scope seems possible and also advisable.  So that is what my language will do.

What, then, is the scope

Removing holes from the scope of bindings means we only need to determine the start and the end of a scope to provide a complete determination.  The start should be fairly straight forward – the scope of a binding starts exactly where that variable is bound.

This isn’t quite as straight forward as it sounds, as is shown by examples like:

name := name + 42

Is the use of “name” on the right-hand-side a use of the new “name” – which would have to be illegal – or of some old “name” – which would at best be confusing.

I think it is safest to rule this out.  It is tempting to suggest that the scope of a binding extends backwards to the start of the containing block, thus preventing the name from having any other meaning in earlier in the block.  We will almost require this, but not quite as will be seen.

The other end of the scope presents a different challenge.  The most obvious and common answer is that the scope ends at the end of the statement-block which contains the start of the scope, so in

if Expression :
   name := whatever
   statements
more-statements

the scope of “name” would extend through “statements” but would have ended by “more-statements”.  This seems natural but sometimes it isn’t what I want.

if Expression :
   name := something
   other statements
else:
   name := other-thing

might be a useful construct which declares “name” as one of two different values.  I might then want to use “name” later in the code.  Using the common rules described above we would need to declare the binding for name before the “if” and not give it a value there.

name:
if Expression :
   name = something
else:
   name = other-thing

I find that I don’t really like declaring a binding without actually binding anything to the name.  There may well be times when this is best and I’m not sure I would disallow it completely.  But I like to make it as optional as possible.  In the example with two bindings, a subsequent usage of “name” would imply no ambiguity and so should be allowed.

I am as yet unsure about a construct like:

if Expression:
  name := value
some statements
if Expression:
  Some statement using "name"

If the two Expressions are identical and depend only on values that haven’t changed, then “name” in the second statement block can reasonably be the same name that was bound in the first.

I am thinking that the scope of a binding extends:

  • At least to the end of the block which declares the binding. This ensures that a name cannot be bound twice in the same block.
  • At most to the end of the function which declares the binding
  • Conditionally to the remainder of  a block which encloses a block that ends with the name still in scope. The inner block must be guaranteed to declare the name precisely once on every path through the block.  The outer block must not declare the name at all, and may not use the name before the inner block.

This conditional scope extension seems to capture what I want, but feels a little bit dangerous – having any uncertainty over semantics is best avoided.  I like it enough that I think it is worth experimenting with.  If it turns out to be clumsy, something else will have to be found.

One consequence of this rule is that a name that is bound inside a looping construct (particularly in a “do” block) can never be used outside that loop.  In part, this is what the “for” part of a loop is for – it is where you declare bindings that are used in or created by a loop.

Another consequence is that if a name is bound in one “case” clause, but not all, then it must remain local to that “case” clause.

This approach to scope seem to match what I want, but there are some thorny issues related to the type of the binding, particular when the type is inferred from usage.

If a name is declared in both branches of an ‘if/else’, do we allow the two declarations to be of different types?  If we don’t it might seem to be overly restrictive – surely each declaration of a name should be independent.  If we do, then the name clearly cannot be used after the ‘if/else’ as it would not have a well-defined type.

This becomes more interesting if the usage in each branch does not completely define the type.  Maybe in one branch all operations are consistent with an integer, while in the other some operations imply a floating point number.  If the name is used after the if/else then it must be the same type everywhere and  so much be floating point.  If not, it could remain as an integer in one branch, which may result in subtly different behaviour.  This ambiguity is unlikely to be a good thing.

I think the best way to resolve the ambiguity is to determine that the type of a binding must be fully determined when the block containing the declaration completes.  If two branches complete with a particular name bound with two different types, then the binding does not extend beyond the branches, and a subsequent usage is illegal.

When the type system becomes rich enough that strict type/subtype relationship become meaningful, the type beyond the branches may be the super-type of the types within the branches, but for now it must be the same or nothing.

Implementing these scopes.

While parsing, we need to know which names are currently in scope and we need to track when two or more scopes for a name from different branches can be merged.

Each time a name declaration is found a new “variable” instance is created and is possibly linked to the previous instance if there is some chance that they can be merged. Each instance tracks the minimum nesting level at which it is valid.  This starts off at the nesting level where it is declared, but can be reduced when scopes in different branches are merged.

When a variable declaration is found, the current instance with that name is located.  If its nesting level is at most the current nesting level there we have a clearly illegal redeclaration.  If it is greater then any merge of the current instance is disabled and a new instance is created at this level.  Similarly if no current instance is found a new instance is created.

When a variable name is used and the current instance has a nesting level at least the current level, that instance is used.  If there is no instance we clearly have an error.  If the current instance has a greater nesting level and can be merged, the merge is finalized and the nesting level of the combined instance is set to the current level.

Each instance for a given name is linked to the previous instance which has been merged, and also the previous which hasn’t.  When a branch statement completes the list of unmerged instances is examined to see if they might be merged.

What made it to “Stoney Creek”

Many of the above ideas were written before I had finished and implementation.  Now (February 2018) I have my “Stoney Creek” version of the pre-language and it doesn’t quite match – though mostly it does.

The “name : type = value” option has not yet been implemented, only “name := value” and “name ::= value”, so types are still implicit.  Until I have interesting types, that doesn’t lose much.  The merging after an if/else of switch/case happens precisely when a name what was declared in multiple parallel branches (e.g.  then and else) is used afterwards.  The type is only considered afterwards and if a consistent type cannot be resolved, an error occurs.  This means that a given name can easily have different types in different branches if it is no subsequently used.  I don’t currently see that as a problem, but I might change my mind.

I’ve also introduced an undeclared type – the label.  If a name is used without being declared, then it is assumed to be a label with an arbitrary, unique, constant value.  This is only permitted in a “use” statement and in a “case” expression.  I don’t currently check that every label “used” has a “case”, or vice-versa, but that is a natural step.  I think I like this, but it is early days yet.

The other key part of the implementation is error messages.  A large part of the value of scopes is that it enables common errors to be detected, so of course I don’t realize the value without error messages.  Unlike the Falls Creek language, Stoney Creek produces error messages about inconsistent types, about multiply declared variables, and even about syntax errors, though that last is very limit as yet.

My next steps are to improve the syntax errors a little, then start adding complex types.  I have lots of ideas for types.  It will important to introduce them gradually, else it will be another 3 years before I post anything.

As before, the interpreter is in my ocean git tree (git://ocean-lang.org/ocean), and can be read as literate source code.

Posted in Language Design | Leave a comment

Complex documents in edlib

Posted on November 3, 2017 by neilbrown

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 | Leave a comment

Fewer NULL dereferences in edlib

Posted on August 19, 2016 by neilbrown

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 | Leave a comment

A notmuch based email reader

Posted on August 10, 2016 by neilbrown

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 | Leave a comment

edlib is back on track…

Posted on April 4, 2016 by neilbrown

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 | Leave a comment

LCA-2016 presentation is done

Posted on February 5, 2016 by neilbrown

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 | Leave a comment

edlib – render-lines, what a good idea.

Posted on November 22, 2015 by neilbrown

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 | Leave a comment

edlib – commands

Posted on November 8, 2015 by neilbrown

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 | Leave a comment

edlib – managing input

Posted on July 30, 2015 by neilbrown

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 | Leave a comment