From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 8981 invoked from network); 1 Jul 1999 14:17:18 -0000 Received: from sunsite.auc.dk (130.225.51.30) by ns1.primenet.com.au with SMTP; 1 Jul 1999 14:17:18 -0000 Received: (qmail 29102 invoked by alias); 1 Jul 1999 14:16:58 -0000 Mailing-List: contact zsh-workers-help@sunsite.auc.dk; run by ezmlm Precedence: bulk X-No-Archive: yes X-Seq: 6938 Received: (qmail 29095 invoked from network); 1 Jul 1999 14:16:58 -0000 X-Lotus-FromDomain: JPMORGAN@SMTP From: "Anthony J Heading" To: zsh-workers@sunsite.auc.dk Message-ID: <482567A1.004530C0.00@nyc-ntgw-n01.ny.jpmorgan.com> Date: Thu, 1 Jul 1999 22:14:56 +0800 Subject: Alternative design for keymap code Mime-Version: 1.0 Content-type: text/plain; charset=us-ascii Content-Disposition: inline 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.