Alternative design for keymap code

Alternative design for keymap code

[Anthony J Heading]

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.

Re: Alternative design for keymap code

[Peter Stephenson]

"Anthony J Heading" wrote:
> 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.

Just some thoughts while I'm waiting to go to a conference dinner: perhaps
these should be ZKEYMAP and zkeymap since we`re trying to keep the
parameter list reasonably unpolluted.  Also, if these are going to be tied,
then they should probably be normal rather than special tied arrays, since
if I remember right (I try hard never to look at this in the code since it
gives me nightmares, but it would seem I do) making special parameters
local still doesn`t work.  Maybe we should fix this, then I could sleep at
nights.  The problem is keeping them special and restoring the values, but
this has been pretty much solved for `special=value builtin' so it
shouldn't be too hard to solve it here as well.

-- 
Peter Stephenson <pws@ibmth.df.unipi.it>       Tel: +39 050 844536
WWW:  http://www.ifh.de/~pws/
Dipartimento di Fisica, Via Buonarroti 2, 56127 Pisa, Italy

Re: Alternative design for keymap code

[Sven Wischnowsky]

Anthony J Heading wrote:

> 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.

Agreed. Wholeheartedly. Btw, I just wanted to keep the code-change as
small as possible when I wrote those local keymaps we currently
have. And was planning to come back to it later... I also never
understood why we have this aliasing thing instead of a bindkey-option 
that just sets the keymap to use. If I remember correctly I wasn't
here when this (or at least parts of it) were implemented, so I missed 
the discussion. Hm, time to read the archive, I guess.

> 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.

This sounds good, too.

> 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.

Yes, I like this, too. (Making undefined-key the hole in local keymaps 
as it currently is is ugly.)

> 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.

And this sounds good to me, too.

So, I'd vote for cleaning up the keymap structure and selection
mechanism a bit and to give users a simple way to modify the keymaps
to use (either with a special array or via bindkey-option).

Bye
 Sven


--
Sven Wischnowsky                         wischnow@informatik.hu-berlin.de