Alternative design for keymap code

["Anthony J Heading" <heading_anthony@xxxxxxxxxxxx>]

I posted a  couple of months back that I was fiddling with the keymap code.
I've written a reasonably substantial patch,  but at some point when I
wasn't looking my design departed from sanity.    So it needs to be
revisited.   But I think I'm now at a point that I could say what I did and
why, and find out if you think there's any mileage in it.

My original problem a couple of years back was trying to allow scripts to
read tty stdin but with command-line editing:  in practice a multi-line
vared which could be exited with EOF on a new line.    The current way
involved lots of unpleasant rebinding:  the return key and probably ^D and
signal handling to unwind the whole lot if needed.   So I figured that what
I needed was - in emacs-think - an overlay keymap.

A similar line of thought seems to be surfacing at the moment if I
understand Andrej's and others' messages correctly

The current keymap code isn't optimally structured for that, and indeed
struck me as a little simplistic -  the only relationships on keymaps are
deep copying and aliasing.   And the structure of a fixed 256 key array for
single keystrokes and a hash table for multistroke commands seemed an ugly
optimisation.

I replaced the keymap lookup code with an optimised hash table -  basically
something I learnt from perl 5.000alpha6,  but which also keeps the chains
ordered by key sequence length.   Using a hash function  h <- 33 * h +
newchar means that by setting the hash table width to 256 the single
keystrokes would be distributed one-per-bucket and always be the first
element.    Which is good for speed (if one thought that one could type
faster than a CPU could read).   So no need for the fixed array,  but also
no need for the width to be 256 if one wanted a small overlay map.

I then also implemented a distinction between unbound keys and keys bound
to undefined-key.   Finding the latter in a keymap means the key really
does nothing,  while the former case is 'transparent'  - the search simply
fall through to the next underlying keymap.     When a final definition (or
lack thereof)  is found,  it's cached in the top level map.   Again good
efficiency wise.

And I tried to simplifiy the user perspective on the viins/vicmd confusion
by assuming that vi's modal behaviour is a special case:  claim to the user
to have a single keymap  - the base one called 'vi'  -  but put a flag on
bindkey to select the command map;   implement simply by storing the
command mode defns secretly as 'vi___invisible_suffix'.    One can
therefore define one's own vi overlays on the cmd or insert maps  but
always with a single name.

At this point I lost the plot a bit.  Trying to implement the notion of an
'underlying keymap' and precedence of definitions,  I figured keymap
inheritance would a neat OO sort of thing.   And one of the most flexible
OO designs is Common Lisp's CLOS.      So I allowed each keymap a list of
parents from which it would inherit,  constructed the topological sort, and
expanded the whole thing out into the lists of effective parents and
children.    It's surprisingly concise - maybe 100 lines of code to do the
whole thing - certainly the final result is no larger than the original.

But after trying some applications,  I came to the conclusion that I was
sidetracked by the mathematical elegance of the algorithm,  and that people
really don't need full-blown multiple inheritance in order to tweak a
definition of shift-up-arrow.

After reflecting for a while,  I believe there's still value in some of the
design.    And I'm thinking instead that maybe there should be a shell
parameter  KEYMAP/keymap  pair,  which specificies the prevailing set of
keymaps.  These are searched in order.   Shell function are then able to
push their own map onto the head the list if they need.  And by allowing
the KEYMAP parameter to be function-local,  exit cleanup is automatic.

But  I'm not entirely certain what might be useful for writing widgets.
If zsh code wants to switch around its own mappings,  but not compromise
any users redefinitions,  then being able internally to treat a set of
ordered keymaps as single entity is maybe a useful thing.   So perhaps
there is some use for the inheritance code.   But perhaps not.

I've suddenly decided to spend next 3 weeks on vacation studying Russian in
St Petersburg, but might come back with enthusiasm to attack this again.
So I'd be interested in opinions about whether any of this area is
worthwhile to work on.

Rgds

Anthony



This communication is for informational purposes only.  It is not intended as
an offer or solicitation for the purchase or sale of any financial instrument
or as an official confirmation of any transaction, unless specifically agreed
otherwise. All market prices, data and other information are not warranted as
to completeness or accuracy and are subject to change without notice. Any
comments or statements made herein do not necessarily reflect those of
J.P. Morgan & Co. Incorporated, its subsidiaries and affiliates.