1/*
2 * ed.xmap.c: This module contains the procedures for maintaining
3 *	      the extended-key map.
4 *
5 * 	      An extended-key (Xkey) is a sequence of keystrokes
6 *	      introduced with an sequence introducer and consisting
7 *	      of an arbitrary number of characters.  This module maintains
8 *	      a map (the Xmap) to convert these extended-key sequences
9 * 	      into input strings (XK_STR), editor functions (XK_CMD), or
10 *	      unix commands (XK_EXE). It contains the
11 *	      following externally visible functions.
12 *
13 *		int GetXkey(ch,val);
14 *		CStr *ch;
15 *		XmapVal *val;
16 *
17 *	      Looks up *ch in map and then reads characters until a
18 *	      complete match is found or a mismatch occurs. Returns the
19 *	      type of the match found (XK_STR, XK_CMD, or XK_EXE).
20 *	      Returns NULL in val.str and XK_STR for no match.
21 *	      The last character read is returned in *ch.
22 *
23 *		void AddXkey(Xkey, val, ntype);
24 *		CStr *Xkey;
25 *		XmapVal *val;
26 *		int ntype;
27 *
28 *	      Adds Xkey to the Xmap and associates the value in val with it.
29 *	      If Xkey is already is in Xmap, the new code is applied to the
30 *	      existing Xkey. Ntype specifies if code is a command, an
31 *	      out string or a unix command.
32 *
33 *	        int DeleteXkey(Xkey);
34 *	        CStr *Xkey;
35 *
36 *	      Delete the Xkey and all longer Xkeys staring with Xkey, if
37 *	      they exists.
38 *
39 *	      Warning:
40 *		If Xkey is a substring of some other Xkeys, then the longer
41 *		Xkeys are lost!!  That is, if the Xkeys "abcd" and "abcef"
42 *		are in Xmap, adding the key "abc" will cause the first two
43 *		definitions to be lost.
44 *
45 *		void ResetXmap();
46 *
47 *	      Removes all entries from Xmap and resets the defaults.
48 *
49 *		void PrintXkey(Xkey);
50 *		CStr *Xkey;
51 *
52 *	      Prints all extended keys prefixed by Xkey and their associated
53 *	      commands.
54 *
55 *	      Restrictions:
56 *	      -------------
57 *	        1) It is not possible to have one Xkey that is a
58 *		   substring of another.
59 */
60/*-
61 * Copyright (c) 1980, 1991 The Regents of the University of California.
62 * All rights reserved.
63 *
64 * Redistribution and use in source and binary forms, with or without
65 * modification, are permitted provided that the following conditions
66 * are met:
67 * 1. Redistributions of source code must retain the above copyright
68 *    notice, this list of conditions and the following disclaimer.
69 * 2. Redistributions in binary form must reproduce the above copyright
70 *    notice, this list of conditions and the following disclaimer in the
71 *    documentation and/or other materials provided with the distribution.
72 * 3. Neither the name of the University nor the names of its contributors
73 *    may be used to endorse or promote products derived from this software
74 *    without specific prior written permission.
75 *
76 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
77 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
78 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
79 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
80 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
81 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
82 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
83 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
84 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
85 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
86 * SUCH DAMAGE.
87 */
88#include "sh.h"
89#include "ed.h"
90#include "ed.defns.h"
91
92#ifndef NULL
93#define NULL 0
94#endif
95
96/* Internal Data types and declarations */
97
98/* The Nodes of the Xmap.  The Xmap is a linked list of these node
99 * elements
100 */
101typedef struct Xmapnode {
102    Char    ch;			/* single character of Xkey */
103    int     type;
104    XmapVal val; 		/* command code or pointer to string, if this
105				 * is a leaf */
106    struct Xmapnode *next;	/* ptr to next char of this Xkey */
107    struct Xmapnode *sibling;	/* ptr to another Xkey with same prefix */
108} XmapNode;
109
110static XmapNode *Xmap = NULL;	/* the current Xmap */
111
112
113/* Some declarations of procedures */
114static	int       TraverseMap	(XmapNode *, CStr *, XmapVal *);
115static	int       TryNode	(XmapNode *, CStr *, XmapVal *, int);
116static	XmapNode *GetFreeNode	(CStr *);
117static	void	  PutFreeNode	(XmapNode *);
118static	int	  TryDeleteNode	(XmapNode **, CStr *);
119static	int	  Lookup	(struct Strbuf *, const CStr *,
120				 const XmapNode *);
121static	void	  Enumerate	(struct Strbuf *, const XmapNode *);
122static	void	  unparsech	(struct Strbuf *, Char);
123
124
125XmapVal *
126XmapCmd(int cmd)
127{
128    static XmapVal xm;
129    xm.cmd = (KEYCMD) cmd;
130    return &xm;
131}
132
133XmapVal *
134XmapStr(CStr *str)
135{
136    static XmapVal xm;
137    xm.str.len = str->len;
138    xm.str.buf = str->buf;
139    return &xm;
140}
141
142/* ResetXmap():
143 *	Takes all nodes on Xmap and puts them on free list.  Then
144 *	initializes Xmap with arrow keys
145 */
146void
147ResetXmap(void)
148{
149    PutFreeNode(Xmap);
150    Xmap = NULL;
151
152    DefaultArrowKeys();
153    return;
154}
155
156
157/* GetXkey():
158 *	Calls the recursive function with entry point Xmap
159 */
160int
161GetXkey(CStr *ch, XmapVal *val)
162{
163    return (TraverseMap(Xmap, ch, val));
164}
165
166/* TraverseMap():
167 *	recursively traverses node in tree until match or mismatch is
168 * 	found.  May read in more characters.
169 */
170static int
171TraverseMap(XmapNode *ptr, CStr *ch, XmapVal *val)
172{
173    Char    tch;
174
175    if (ptr->ch == *(ch->buf)) {
176	/* match found */
177	if (ptr->next) {
178	    /* Xkey not complete so get next char */
179	    if (GetNextChar(&tch) != 1) {	/* if EOF or error */
180		val->cmd = F_SEND_EOF;
181		return XK_CMD;/* PWP: Pretend we just read an end-of-file */
182	    }
183	    *(ch->buf) = tch;
184	    return (TraverseMap(ptr->next, ch, val));
185	}
186	else {
187	    *val = ptr->val;
188	    if (ptr->type != XK_CMD)
189		*(ch->buf) = '\0';
190	    return ptr->type;
191	}
192    }
193    else {
194	/* no match found here */
195	if (ptr->sibling) {
196	    /* try next sibling */
197	    return (TraverseMap(ptr->sibling, ch, val));
198	}
199	else {
200	    /* no next sibling -- mismatch */
201	    val->str.buf = NULL;
202	    val->str.len = 0;
203	    return XK_STR;
204	}
205    }
206}
207
208void
209AddXkey(const CStr *Xkey, XmapVal *val, int ntype)
210{
211    CStr cs;
212    cs.buf = Xkey->buf;
213    cs.len = Xkey->len;
214    if (Xkey->len == 0) {
215	xprintf("%s", CGETS(9, 1, "AddXkey: Null extended-key not allowed.\n"));
216	return;
217    }
218
219    if (ntype == XK_CMD && val->cmd == F_XKEY) {
220	xprintf("%s",
221	    CGETS(9, 2, "AddXkey: sequence-lead-in command not allowed\n"));
222	return;
223    }
224
225    if (Xmap == NULL)
226	/* tree is initially empty.  Set up new node to match Xkey[0] */
227	Xmap = GetFreeNode(&cs);	/* it is properly initialized */
228
229    /* Now recurse through Xmap */
230    (void) TryNode(Xmap, &cs, val, ntype);
231    return;
232}
233
234static int
235TryNode(XmapNode *ptr, CStr *str, XmapVal *val, int ntype)
236{
237    /*
238     * Find a node that matches *string or allocate a new one
239     */
240    if (ptr->ch != *(str->buf)) {
241	XmapNode *xm;
242
243	for (xm = ptr; xm->sibling != NULL; xm = xm->sibling)
244	    if (xm->sibling->ch == *(str->buf))
245		break;
246	if (xm->sibling == NULL)
247	    xm->sibling = GetFreeNode(str);	/* setup new node */
248	ptr = xm->sibling;
249    }
250
251    str->buf++;
252    str->len--;
253    if (str->len == 0) {
254	size_t len;
255
256	/* we're there */
257	if (ptr->next != NULL) {
258	    PutFreeNode(ptr->next);	/* lose longer Xkeys with this prefix */
259	    ptr->next = NULL;
260	}
261
262	switch (ptr->type) {
263	case XK_STR:
264	case XK_EXE:
265	    xfree(ptr->val.str.buf);
266	    ptr->val.str.len = 0;
267	    break;
268	case XK_NOD:
269	case XK_CMD:
270	    break;
271	default:
272	    abort();
273	    break;
274	}
275
276	switch (ptr->type = ntype) {
277	case XK_CMD:
278	    ptr->val = *val;
279	    break;
280	case XK_STR:
281	case XK_EXE:
282	    ptr->val.str.len = val->str.len;
283	    len = (val->str.len + 1) * sizeof(*ptr->val.str.buf);
284	    ptr->val.str.buf = xmalloc(len);
285	    (void) memcpy(ptr->val.str.buf, val->str.buf, len);
286	    break;
287	default:
288	    abort();
289	    break;
290	}
291    }
292    else {
293	/* still more chars to go */
294	if (ptr->next == NULL)
295	    ptr->next = GetFreeNode(str);	/* setup new node */
296	(void) TryNode(ptr->next, str, val, ntype);
297    }
298    return (0);
299}
300
301void
302ClearXkey(KEYCMD *map, const CStr *in)
303{
304    unsigned char c = (unsigned char) *(in->buf);
305    if ((map[c] == F_XKEY) &&
306	((map == CcKeyMap && CcAltMap[c] != F_XKEY) ||
307	 (map == CcAltMap && CcKeyMap[c] != F_XKEY)))
308	(void) DeleteXkey(in);
309}
310
311int
312DeleteXkey(const CStr *Xkey)
313{
314    CStr s;
315
316    s = *Xkey;
317    if (s.len == 0) {
318	xprintf("%s",
319	        CGETS(9, 3, "DeleteXkey: Null extended-key not allowed.\n"));
320	return (-1);
321    }
322
323    if (Xmap == NULL)
324	return (0);
325
326    (void) TryDeleteNode(&Xmap, &s);
327    return (0);
328}
329
330/* Destroys str */
331static int
332TryDeleteNode(XmapNode **inptr, CStr *str)
333{
334    XmapNode *ptr;
335
336    ptr = *inptr;
337    /*
338     * Find a node that matches *string or allocate a new one
339     */
340    if (ptr->ch != *(str->buf)) {
341	XmapNode *xm;
342
343	for (xm = ptr; xm->sibling != NULL; xm = xm->sibling)
344	    if (xm->sibling->ch == *(str->buf))
345		break;
346	if (xm->sibling == NULL)
347	    return (0);
348	inptr = &xm->sibling;
349	ptr = xm->sibling;
350    }
351
352    str->buf++;
353    str->len--;
354
355    if (str->len == 0) {
356	/* we're there */
357	*inptr = ptr->sibling;
358	ptr->sibling = NULL;
359	PutFreeNode(ptr);
360	return (1);
361    }
362    else if (ptr->next != NULL && TryDeleteNode(&ptr->next, str) == 1) {
363	if (ptr->next != NULL)
364	    return (0);
365	*inptr = ptr->sibling;
366	ptr->sibling = NULL;
367	PutFreeNode(ptr);
368	return (1);
369    }
370    else {
371	return (0);
372    }
373}
374
375/* PutFreeNode():
376 *	Puts a tree of nodes onto free list using free(3).
377 */
378static void
379PutFreeNode(XmapNode *ptr)
380{
381    if (ptr == NULL)
382	return;
383
384    if (ptr->next != NULL) {
385	PutFreeNode(ptr->next);
386	ptr->next = NULL;
387    }
388
389    PutFreeNode(ptr->sibling);
390
391    switch (ptr->type) {
392    case XK_CMD:
393    case XK_NOD:
394	break;
395    case XK_EXE:
396    case XK_STR:
397	xfree(ptr->val.str.buf);
398	break;
399    default:
400	abort();
401	break;
402    }
403    xfree(ptr);
404}
405
406
407/* GetFreeNode():
408 *	Returns pointer to an XmapNode for ch.
409 */
410static XmapNode *
411GetFreeNode(CStr *ch)
412{
413    XmapNode *ptr;
414
415    ptr = xmalloc(sizeof(XmapNode));
416    ptr->ch = ch->buf[0];
417    ptr->type = XK_NOD;
418    ptr->val.str.buf = NULL;
419    ptr->val.str.len = 0;
420    ptr->next = NULL;
421    ptr->sibling = NULL;
422    return (ptr);
423}
424
425
426/* PrintXKey():
427 *	Print the binding associated with Xkey key.
428 *	Print entire Xmap if null
429 */
430void
431PrintXkey(const CStr *key)
432{
433    struct Strbuf buf = Strbuf_INIT;
434    CStr cs;
435
436    if (key) {
437	cs.buf = key->buf;
438	cs.len = key->len;
439    }
440    else {
441	cs.buf = STRNULL;
442	cs.len = 0;
443    }
444    /* do nothing if Xmap is empty and null key specified */
445    if (Xmap == NULL && cs.len == 0)
446	return;
447
448    Strbuf_append1(&buf, '"');
449    cleanup_push(&buf, Strbuf_cleanup);
450    if (Lookup(&buf, &cs, Xmap) <= -1)
451	/* key is not bound */
452	xprintf(CGETS(9, 4, "Unbound extended key \"%S\"\n"), cs.buf);
453    cleanup_until(&buf);
454}
455
456/* Lookup():
457 *	look for the string starting at node ptr.
458 *	Print if last node
459 */
460static int
461Lookup(struct Strbuf *buf, const CStr *str, const XmapNode *ptr)
462{
463    if (ptr == NULL)
464	return (-1);		/* cannot have null ptr */
465
466    if (str->len == 0) {
467	/* no more chars in string.  Enumerate from here. */
468	Enumerate(buf, ptr);
469	return (0);
470    }
471    else {
472	/* If match put this char into buf.  Recurse */
473	if (ptr->ch == *(str->buf)) {
474	    /* match found */
475	    unparsech(buf, ptr->ch);
476	    if (ptr->next != NULL) {
477		/* not yet at leaf */
478		CStr tstr;
479		tstr.buf = str->buf + 1;
480		tstr.len = str->len - 1;
481		return (Lookup(buf, &tstr, ptr->next));
482	    }
483	    else {
484		/* next node is null so key should be complete */
485		if (str->len == 1) {
486		    Strbuf_append1(buf, '"');
487		    Strbuf_terminate(buf);
488		    printOne(buf->s, &ptr->val, ptr->type);
489		    return (0);
490		}
491		else
492		    return (-1);/* mismatch -- string still has chars */
493	    }
494	}
495	else {
496	    /* no match found try sibling */
497	    if (ptr->sibling)
498		return (Lookup(buf, str, ptr->sibling));
499	    else
500		return (-1);
501	}
502    }
503}
504
505static void
506Enumerate(struct Strbuf *buf, const XmapNode *ptr)
507{
508    size_t old_len;
509
510    if (ptr == NULL) {
511#ifdef DEBUG_EDIT
512	xprintf(CGETS(9, 6, "Enumerate: BUG!! Null ptr passed\n!"));
513#endif
514	return;
515    }
516
517    old_len = buf->len;
518    unparsech(buf, ptr->ch); /* put this char at end of string */
519    if (ptr->next == NULL) {
520	/* print this Xkey and function */
521	Strbuf_append1(buf, '"');
522	Strbuf_terminate(buf);
523	printOne(buf->s, &ptr->val, ptr->type);
524    }
525    else
526	Enumerate(buf, ptr->next);
527
528    /* go to sibling if there is one */
529    if (ptr->sibling) {
530	buf->len = old_len;
531	Enumerate(buf, ptr->sibling);
532    }
533}
534
535
536/* PrintOne():
537 *	Print the specified key and its associated
538 *	function specified by val
539 */
540void
541printOne(const Char *key, const XmapVal *val, int ntype)
542{
543    struct KeyFuncs *fp;
544    static const char *fmt = "%s\n";
545
546    xprintf("%-15S-> ", key);
547    if (val != NULL)
548	switch (ntype) {
549	case XK_STR:
550	case XK_EXE: {
551	    unsigned char *p;
552
553	    p = unparsestring(&val->str, ntype == XK_STR ? STRQQ : STRBB);
554	    cleanup_push(p, xfree);
555	    xprintf(fmt, p);
556	    cleanup_until(p);
557	    break;
558	}
559	case XK_CMD:
560	    for (fp = FuncNames; fp->name; fp++)
561		if (val->cmd == fp->func)
562		    xprintf(fmt, fp->name);
563		break;
564	default:
565	    abort();
566	    break;
567	}
568    else
569	xprintf(fmt, CGETS(9, 7, "no input"));
570}
571
572static void
573unparsech(struct Strbuf *buf, Char ch)
574{
575    if (ch == 0) {
576	Strbuf_append1(buf, '^');
577	Strbuf_append1(buf, '@');
578    }
579    else if (Iscntrl(ch)) {
580	Strbuf_append1(buf, '^');
581	if (ch == CTL_ESC('\177'))
582	    Strbuf_append1(buf, '?');
583	else
584#ifdef IS_ASCII
585	    Strbuf_append1(buf, ch | 0100);
586#else
587	    Strbuf_append1(buf, _toebcdic[_toascii[ch]|0100]);
588#endif
589    }
590    else if (ch == '^') {
591	Strbuf_append1(buf, '\\');
592	Strbuf_append1(buf, '^');
593    } else if (ch == '\\') {
594	Strbuf_append1(buf, '\\');
595	Strbuf_append1(buf, '\\');
596    } else if (ch == ' ' || (Isprint(ch) && !Isspace(ch))) {
597	Strbuf_append1(buf, ch);
598    }
599    else {
600	Strbuf_append1(buf, '\\');
601	Strbuf_append1(buf, ((ch >> 6) & 7) + '0');
602	Strbuf_append1(buf, ((ch >> 3) & 7) + '0');
603	Strbuf_append1(buf, (ch & 7) + '0');
604    }
605}
606
607eChar
608parseescape(const Char **ptr)
609{
610    const Char *p;
611    Char c;
612
613    p = *ptr;
614
615    if ((p[1] & CHAR) == 0) {
616	xprintf(CGETS(9, 8, "Something must follow: %c\n"), (char)*p);
617	return CHAR_ERR;
618    }
619    if ((*p & CHAR) == '\\') {
620	p++;
621	switch (*p & CHAR) {
622	case 'a':
623	    c = CTL_ESC('\007');         /* Bell */
624	    break;
625	case 'b':
626	    c = CTL_ESC('\010');         /* Backspace */
627	    break;
628	case 'e':
629	    c = CTL_ESC('\033');         /* Escape */
630	    break;
631	case 'f':
632	    c = CTL_ESC('\014');         /* Form Feed */
633	    break;
634	case 'n':
635	    c = CTL_ESC('\012');         /* New Line */
636	    break;
637	case 'r':
638	    c = CTL_ESC('\015');         /* Carriage Return */
639	    break;
640	case 't':
641	    c = CTL_ESC('\011');         /* Horizontal Tab */
642	    break;
643	case 'v':
644	    c = CTL_ESC('\013');         /* Vertical Tab */
645	    break;
646	case '\\':
647	    c = '\\';
648	    break;
649	case '0':
650	case '1':
651	case '2':
652	case '3':
653	case '4':
654	case '5':
655	case '6':
656	case '7':
657	    {
658		int cnt, val;
659		Char ch;
660
661		for (cnt = 0, val = 0; cnt < 3; cnt++) {
662		    ch = *p++ & CHAR;
663		    if (ch < '0' || ch > '7') {
664			p--;
665			break;
666		    }
667		    val = (val << 3) | (ch - '0');
668		}
669		if ((val & ~0xff) != 0) {
670		    xprintf("%s", CGETS(9, 9,
671			    "Octal constant does not fit in a char.\n"));
672		    return 0;
673		}
674#ifndef IS_ASCII
675		if (CTL_ESC(val) != val && adrof(STRwarnebcdic))
676		    xprintf(/*CGETS(9, 9, no NLS-String yet!*/
677			    "Warning: Octal constant \\%3.3o is interpreted as EBCDIC value.\n", val/*)*/);
678#endif
679		c = (Char) val;
680		--p;
681	    }
682	    break;
683	default:
684	    c = *p;
685	    break;
686	}
687    }
688    else if ((*p & CHAR) == '^' && (Isalpha(p[1] & CHAR) ||
689				    strchr("@^_?\\|[{]}", p[1] & CHAR))) {
690	p++;
691#ifdef IS_ASCII
692	c = ((*p & CHAR) == '?') ? CTL_ESC('\177') : ((*p & CHAR) & 0237);
693#else
694	c = ((*p & CHAR) == '?') ? CTL_ESC('\177') : _toebcdic[_toascii[*p & CHAR] & 0237];
695	if (adrof(STRwarnebcdic))
696	    xprintf(/*CGETS(9, 9, no NLS-String yet!*/
697		"Warning: Control character ^%c may be interpreted differently in EBCDIC.\n", *p & CHAR /*)*/);
698#endif
699    }
700    else
701	c = *p;
702    *ptr = p;
703    return (c);
704}
705
706
707unsigned char *
708unparsestring(const CStr *str, const Char *sep)
709{
710    unsigned char *buf, *b;
711    Char   p;
712    int l;
713
714    /* Worst-case is "\uuu" or result of wctomb() for each char from str */
715    buf = xmalloc((str->len + 1) * max(4, MB_LEN_MAX));
716    b = buf;
717    if (sep[0])
718#ifndef WINNT_NATIVE
719	*b++ = sep[0];
720#else /* WINNT_NATIVE */
721	*b++ = CHAR & sep[0];
722#endif /* !WINNT_NATIVE */
723
724    for (l = 0; l < str->len; l++) {
725	p = str->buf[l];
726	if (Iscntrl(p)) {
727	    *b++ = '^';
728	    if (p == CTL_ESC('\177'))
729		*b++ = '?';
730	    else
731#ifdef IS_ASCII
732		*b++ = (unsigned char) (p | 0100);
733#else
734		*b++ = _toebcdic[_toascii[p]|0100];
735#endif
736	}
737	else if (p == '^' || p == '\\') {
738	    *b++ = '\\';
739	    *b++ = (unsigned char) p;
740	}
741	else if (p == ' ' || (Isprint(p) && !Isspace(p)))
742	    b += one_wctomb((char *)b, p);
743	else {
744	    *b++ = '\\';
745	    *b++ = ((p >> 6) & 7) + '0';
746	    *b++ = ((p >> 3) & 7) + '0';
747	    *b++ = (p & 7) + '0';
748	}
749    }
750    if (sep[0] && sep[1])
751#ifndef WINNT_NATIVE
752	*b++ = sep[1];
753#else /* WINNT_NATIVE */
754	*b++ = CHAR & sep[1];
755#endif /* !WINNT_NATIVE */
756    *b++ = 0;
757    return buf;			/* should check for overflow */
758}
759