compose/parser: resolve keysyms in parser instead of scanner
[platform/upstream/libxkbcommon.git] / src / compose / parser.c
1 /*
2  * Copyright © 2013 Ran Benita <ran234@gmail.com>
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a
5  * copy of this software and associated documentation files (the "Software"),
6  * to deal in the Software without restriction, including without limitation
7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8  * and/or sell copies of the Software, and to permit persons to whom the
9  * Software is furnished to do so, subject to the following conditions:
10  *
11  * The above copyright notice and this permission notice (including the next
12  * paragraph) shall be included in all copies or substantial portions of the
13  * Software.
14  *
15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21  * DEALINGS IN THE SOFTWARE.
22  */
23
24 /******************************************************************
25
26               Copyright 1992 by Oki Technosystems Laboratory, Inc.
27               Copyright 1992 by Fuji Xerox Co., Ltd.
28
29 Permission to use, copy, modify, distribute, and sell this software
30 and its documentation for any purpose is hereby granted without fee,
31 provided that the above copyright notice appear in all copies and
32 that both that copyright notice and this permission notice appear
33 in supporting documentation, and that the name of Oki Technosystems
34 Laboratory and Fuji Xerox not be used in advertising or publicity
35 pertaining to distribution of the software without specific, written
36 prior permission.
37 Oki Technosystems Laboratory and Fuji Xerox make no representations
38 about the suitability of this software for any purpose.  It is provided
39 "as is" without express or implied warranty.
40
41 OKI TECHNOSYSTEMS LABORATORY AND FUJI XEROX DISCLAIM ALL WARRANTIES
42 WITH REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
43 MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL OKI TECHNOSYSTEMS
44 LABORATORY AND FUJI XEROX BE LIABLE FOR ANY SPECIAL, INDIRECT OR
45 CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
46 OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
47 OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
48 OR PERFORMANCE OF THIS SOFTWARE.
49
50   Author: Yasuhiro Kawai        Oki Technosystems Laboratory
51   Author: Kazunori Nishihara    Fuji Xerox
52
53 ******************************************************************/
54
55 #include <errno.h>
56
57 #include "utils.h"
58 #include "scanner-utils.h"
59 #include "table.h"
60 #include "paths.h"
61 #include "utf8.h"
62 #include "parser.h"
63
64 #define MAX_LHS_LEN 10
65 #define MAX_INCLUDE_DEPTH 5
66
67 #define KEYSYM_FROM_NAME_CACHE_SIZE 8
68
69 /*
70  * xkb_keysym_from_name() is fairly slow, because for internal reasons
71  * it must use strcasecmp().
72  * A small cache reduces about 20% from the compilation time of
73  * en_US.UTF-8/Compose.
74  */
75 struct keysym_from_name_cache {
76     struct {
77         char name[64];
78         xkb_keysym_t keysym;
79     } cache[KEYSYM_FROM_NAME_CACHE_SIZE];
80     unsigned next;
81 };
82
83 static xkb_keysym_t
84 cached_keysym_from_name(struct keysym_from_name_cache *cache,
85                         const char *name, size_t len)
86 {
87     xkb_keysym_t keysym;
88
89     if (len >= sizeof(cache->cache[0].name))
90         return XKB_KEY_NoSymbol;
91
92     for (unsigned i = 0; i < KEYSYM_FROM_NAME_CACHE_SIZE; i++)
93         if (streq(cache->cache[i].name, name))
94             return cache->cache[i].keysym;
95
96     keysym = xkb_keysym_from_name(name, XKB_KEYSYM_NO_FLAGS);
97     strcpy(cache->cache[cache->next].name, name);
98     cache->cache[cache->next].keysym = keysym;
99     cache->next = (cache->next + 1) % KEYSYM_FROM_NAME_CACHE_SIZE;
100     return keysym;
101 }
102
103 /*
104  * Grammar adapted from libX11/modules/im/ximcp/imLcPrs.c.
105  * See also the XCompose(5) manpage.
106  *
107  * We don't support the MODIFIER rules, which are commented out.
108  *
109  * FILE          ::= { [PRODUCTION] [COMMENT] "\n" | INCLUDE }
110  * INCLUDE       ::= "include" '"' INCLUDE_STRING '"'
111  * PRODUCTION    ::= LHS ":" RHS [ COMMENT ]
112  * COMMENT       ::= "#" {<any character except null or newline>}
113  * LHS           ::= EVENT { EVENT }
114  * EVENT         ::= "<" keysym ">"
115  * # EVENT         ::= [MODIFIER_LIST] "<" keysym ">"
116  * # MODIFIER_LIST ::= ("!" {MODIFIER} ) | "None"
117  * # MODIFIER      ::= ["~"] modifier_name
118  * RHS           ::= ( STRING | keysym | STRING keysym )
119  * STRING        ::= '"' { CHAR } '"'
120  * CHAR          ::= GRAPHIC_CHAR | ESCAPED_CHAR
121  * GRAPHIC_CHAR  ::= locale (codeset) dependent code
122  * ESCAPED_CHAR  ::= ('\\' | '\"' | OCTAL | HEX )
123  * OCTAL         ::= '\' OCTAL_CHAR [OCTAL_CHAR [OCTAL_CHAR]]
124  * OCTAL_CHAR    ::= (0|1|2|3|4|5|6|7)
125  * HEX           ::= '\' (x|X) HEX_CHAR [HEX_CHAR]]
126  * HEX_CHAR      ::= (0|1|2|3|4|5|6|7|8|9|A|B|C|D|E|F|a|b|c|d|e|f)
127  *
128  * INCLUDE_STRING is a filesystem path, with the following %-expansions:
129  *     %% - '%'.
130  *     %H - The user's home directory (the $HOME environment variable).
131  *     %L - The name of the locale specific Compose file (e.g.,
132  *          "/usr/share/X11/locale/<localename>/Compose").
133  *     %S - The name of the system directory for Compose files (e.g.,
134  *          "/usr/share/X11/locale").
135  */
136
137 enum rules_token {
138     TOK_END_OF_FILE = 0,
139     TOK_END_OF_LINE,
140     TOK_INCLUDE,
141     TOK_INCLUDE_STRING,
142     TOK_LHS_KEYSYM,
143     TOK_COLON,
144     TOK_STRING,
145     TOK_RHS_KEYSYM,
146     TOK_ERROR
147 };
148
149 /* Values returned with some tokens, like yylval. */
150 union lvalue {
151     struct {
152         /* Still \0-terminated. */
153         const char *str;
154         size_t len;
155     } string;
156 };
157
158 static enum rules_token
159 lex(struct scanner *s, union lvalue *val)
160 {
161 skip_more_whitespace_and_comments:
162     /* Skip spaces. */
163     while (is_space(peek(s)))
164         if (next(s) == '\n')
165             return TOK_END_OF_LINE;
166
167     /* Skip comments. */
168     if (chr(s, '#')) {
169         skip_to_eol(s);
170         goto skip_more_whitespace_and_comments;
171     }
172
173     /* See if we're done. */
174     if (eof(s)) return TOK_END_OF_FILE;
175
176     /* New token. */
177     s->token_line = s->line;
178     s->token_column = s->column;
179     s->buf_pos = 0;
180
181     /* LHS Keysym. */
182     if (chr(s, '<')) {
183         while (peek(s) != '>' && !eol(s))
184             buf_append(s, next(s));
185         if (!chr(s, '>')) {
186             scanner_err(s, "unterminated keysym literal");
187             return TOK_ERROR;
188         }
189         if (!buf_append(s, '\0')) {
190             scanner_err(s, "keysym literal is too long");
191             return TOK_ERROR;
192         }
193         val->string.str = s->buf;
194         val->string.len = s->buf_pos;
195         return TOK_LHS_KEYSYM;
196     }
197
198     /* Colon. */
199     if (chr(s, ':'))
200         return TOK_COLON;
201
202     /* String literal. */
203     if (chr(s, '\"')) {
204         while (!eof(s) && !eol(s) && peek(s) != '\"') {
205             if (chr(s, '\\')) {
206                 uint8_t o;
207                 if (chr(s, '\\')) {
208                     buf_append(s, '\\');
209                 }
210                 else if (chr(s, '"')) {
211                     buf_append(s, '"');
212                 }
213                 else if (chr(s, 'x') || chr(s, 'X')) {
214                     if (hex(s, &o))
215                         buf_append(s, (char) o);
216                     else
217                         scanner_warn(s, "illegal hexadecimal escape sequence in string literal");
218                 }
219                 else if (oct(s, &o)) {
220                     buf_append(s, (char) o);
221                 }
222                 else {
223                     scanner_warn(s, "unknown escape sequence (%c) in string literal", peek(s));
224                     /* Ignore. */
225                 }
226             } else {
227                 buf_append(s, next(s));
228             }
229         }
230         if (!chr(s, '\"')) {
231             scanner_err(s, "unterminated string literal");
232             return TOK_ERROR;
233         }
234         if (!buf_append(s, '\0')) {
235             scanner_err(s, "string literal is too long");
236             return TOK_ERROR;
237         }
238         if (!is_valid_utf8(s->buf, s->buf_pos - 1)) {
239             scanner_err(s, "string literal is not a valid UTF-8 string");
240             return TOK_ERROR;
241         }
242         val->string.str = s->buf;
243         val->string.len = s->buf_pos;
244         return TOK_STRING;
245     }
246
247     /* RHS keysym or include. */
248     if (is_alpha(peek(s)) || peek(s) == '_') {
249         s->buf_pos = 0;
250         while (is_alnum(peek(s)) || peek(s) == '_')
251             buf_append(s, next(s));
252         if (!buf_append(s, '\0')) {
253             scanner_err(s, "identifier is too long");
254             return TOK_ERROR;
255         }
256
257         if (streq(s->buf, "include"))
258             return TOK_INCLUDE;
259
260         val->string.str = s->buf;
261         val->string.len = s->buf_pos;
262         return TOK_RHS_KEYSYM;
263     }
264
265     /* Discard rest of line. */
266     skip_to_eol(s);
267
268     scanner_err(s, "unrecognized token");
269     return TOK_ERROR;
270 }
271
272 static enum rules_token
273 lex_include_string(struct scanner *s, struct xkb_compose_table *table,
274                    union lvalue *val_out)
275 {
276     while (is_space(peek(s)))
277         if (next(s) == '\n')
278             return TOK_END_OF_LINE;
279
280     s->token_line = s->line;
281     s->token_column = s->column;
282     s->buf_pos = 0;
283
284     if (!chr(s, '\"')) {
285         scanner_err(s, "include statement must be followed by a path");
286         return TOK_ERROR;
287     }
288
289     while (!eof(s) && !eol(s) && peek(s) != '\"') {
290         if (chr(s, '%')) {
291             if (chr(s, '%')) {
292                 buf_append(s, '%');
293             }
294             else if (chr(s, 'H')) {
295                 const char *home = secure_getenv("HOME");
296                 if (!home) {
297                     scanner_err(s, "%%H was used in an include statement, but the HOME environment variable is not set");
298                     return TOK_ERROR;
299                 }
300                 if (!buf_appends(s, home)) {
301                     scanner_err(s, "include path after expanding %%H is too long");
302                     return TOK_ERROR;
303                 }
304             }
305             else if (chr(s, 'L')) {
306                 char *path = get_locale_compose_file_path(table->locale);
307                 if (!path) {
308                     scanner_err(s, "failed to expand %%L to the locale Compose file");
309                     return TOK_ERROR;
310                 }
311                 if (!buf_appends(s, path)) {
312                     free(path);
313                     scanner_err(s, "include path after expanding %%L is too long");
314                     return TOK_ERROR;
315                 }
316                 free(path);
317             }
318             else if (chr(s, 'S')) {
319                 const char *xlocaledir = get_xlocaledir_path();
320                 if (!buf_appends(s, xlocaledir)) {
321                     scanner_err(s, "include path after expanding %%S is too long");
322                     return TOK_ERROR;
323                 }
324             }
325             else {
326                 scanner_err(s, "unknown %% format (%c) in include statement", peek(s));
327                 return TOK_ERROR;
328             }
329         } else {
330             buf_append(s, next(s));
331         }
332     }
333     if (!chr(s, '\"')) {
334         scanner_err(s, "unterminated include statement");
335         return TOK_ERROR;
336     }
337     if (!buf_append(s, '\0')) {
338         scanner_err(s, "include path is too long");
339         return TOK_ERROR;
340     }
341     val_out->string.str = s->buf;
342     val_out->string.len = s->buf_pos;
343     return TOK_INCLUDE_STRING;
344 }
345
346 struct production {
347     xkb_keysym_t lhs[MAX_LHS_LEN];
348     unsigned int len;
349     xkb_keysym_t keysym;
350     char string[256];
351     bool has_keysym;
352     bool has_string;
353 };
354
355 static uint32_t
356 add_node(struct xkb_compose_table *table, xkb_keysym_t keysym)
357 {
358     struct compose_node new = {
359         .keysym = keysym,
360         .next = 0,
361         .is_leaf = true,
362     };
363     darray_append(table->nodes, new);
364     return darray_size(table->nodes) - 1;
365 }
366
367 static void
368 add_production(struct xkb_compose_table *table, struct scanner *s,
369                const struct production *production)
370 {
371     unsigned lhs_pos;
372     uint32_t curr;
373     struct compose_node *node;
374
375     curr = 0;
376     node = &darray_item(table->nodes, curr);
377
378     /*
379      * Insert the sequence to the trie, creating new nodes as needed.
380      *
381      * TODO: This can be sped up a bit by first trying the path that the
382      * previous production took, and only then doing the linear search
383      * through the trie levels.  This will work because sequences in the
384      * Compose files are often clustered by a common prefix; especially
385      * in the 1st and 2nd keysyms, which is where the largest variation
386      * (thus, longest search) is.
387      */
388     for (lhs_pos = 0; lhs_pos < production->len; lhs_pos++) {
389         while (production->lhs[lhs_pos] != node->keysym) {
390             if (node->next == 0) {
391                 uint32_t next = add_node(table, production->lhs[lhs_pos]);
392                 /* Refetch since add_node could have realloc()ed. */
393                 node = &darray_item(table->nodes, curr);
394                 node->next = next;
395             }
396
397             curr = node->next;
398             node = &darray_item(table->nodes, curr);
399         }
400
401         if (lhs_pos + 1 == production->len)
402             break;
403
404         if (node->is_leaf) {
405             if (node->u.leaf.utf8 != 0 ||
406                 node->u.leaf.keysym != XKB_KEY_NoSymbol) {
407                 scanner_warn(s, "a sequence already exists which is a prefix of this sequence; overriding");
408                 node->u.leaf.utf8 = 0;
409                 node->u.leaf.keysym = XKB_KEY_NoSymbol;
410             }
411
412             {
413                 uint32_t successor = add_node(table, production->lhs[lhs_pos + 1]);
414                 /* Refetch since add_node could have realloc()ed. */
415                 node = &darray_item(table->nodes, curr);
416                 node->is_leaf = false;
417                 node->u.successor = successor;
418             }
419         }
420
421         curr = node->u.successor;
422         node = &darray_item(table->nodes, curr);
423     }
424
425     if (!node->is_leaf) {
426         scanner_warn(s, "this compose sequence is a prefix of another; skipping line");
427         return;
428     }
429
430     if (node->u.leaf.utf8 != 0 || node->u.leaf.keysym != XKB_KEY_NoSymbol) {
431         if (streq(&darray_item(table->utf8, node->u.leaf.utf8),
432                   production->string) &&
433             node->u.leaf.keysym == production->keysym) {
434             scanner_warn(s, "this compose sequence is a duplicate of another; skipping line");
435             return;
436         }
437         scanner_warn(s, "this compose sequence already exists; overriding");
438     }
439
440     if (production->has_string) {
441         node->u.leaf.utf8 = darray_size(table->utf8);
442         darray_append_items(table->utf8, production->string,
443                             strlen(production->string) + 1);
444     }
445     if (production->has_keysym) {
446         node->u.leaf.keysym = production->keysym;
447     }
448 }
449
450 static bool
451 parse(struct xkb_compose_table *table, struct scanner *s,
452       unsigned include_depth);
453
454 static bool
455 do_include(struct xkb_compose_table *table, struct scanner *s,
456            const char *path, unsigned include_depth)
457 {
458     FILE *file;
459     bool ok;
460     const char *string;
461     size_t size;
462     struct scanner new_s;
463
464     if (include_depth >= MAX_INCLUDE_DEPTH) {
465         scanner_err(s, "maximum include depth (%d) exceeded; maybe there is an include loop?",
466                     MAX_INCLUDE_DEPTH);
467         return false;
468     }
469
470     file = fopen(path, "r");
471     if (!file) {
472         scanner_err(s, "failed to open included Compose file \"%s\": %s",
473                     path, strerror(errno));
474         return false;
475     }
476
477     ok = map_file(file, &string, &size);
478     if (!ok) {
479         scanner_err(s, "failed to read included Compose file \"%s\": %s",
480                     path, strerror(errno));
481         goto err_file;
482     }
483
484     scanner_init(&new_s, table->ctx, string, size, path, s->priv);
485
486     ok = parse(table, &new_s, include_depth + 1);
487     if (!ok)
488         goto err_unmap;
489
490 err_unmap:
491     unmap_file(string, size);
492 err_file:
493     fclose(file);
494     return ok;
495 }
496
497 static bool
498 parse(struct xkb_compose_table *table, struct scanner *s,
499       unsigned include_depth)
500 {
501     enum rules_token tok;
502     union lvalue val;
503     struct keysym_from_name_cache *cache = s->priv;
504     xkb_keysym_t keysym;
505     struct production production;
506     enum { MAX_ERRORS = 10 };
507     int num_errors = 0;
508
509 initial:
510     production.len = 0;
511     production.has_keysym = false;
512     production.has_string = false;
513
514     /* fallthrough */
515
516 initial_eol:
517     switch (tok = lex(s, &val)) {
518     case TOK_END_OF_LINE:
519         goto initial_eol;
520     case TOK_END_OF_FILE:
521         goto finished;
522     case TOK_INCLUDE:
523         goto include;
524     default:
525         goto lhs_tok;
526     }
527
528 include:
529     switch (tok = lex_include_string(s, table, &val)) {
530     case TOK_INCLUDE_STRING:
531         goto include_eol;
532     default:
533         goto unexpected;
534     }
535
536 include_eol:
537     switch (tok = lex(s, &val)) {
538     case TOK_END_OF_LINE:
539         if (!do_include(table, s, val.string.str, include_depth))
540             goto fail;
541         goto initial;
542     default:
543         goto unexpected;
544     }
545
546 lhs:
547     tok = lex(s, &val);
548 lhs_tok:
549     switch (tok) {
550     case TOK_LHS_KEYSYM:
551         keysym = cached_keysym_from_name(cache, val.string.str, val.string.len);
552         if (keysym == XKB_KEY_NoSymbol) {
553             scanner_err(s, "unrecognized keysym \"%s\" on left-hand side",
554                         val.string.str);
555             goto error;
556         }
557         if (production.len + 1 > MAX_LHS_LEN) {
558             scanner_warn(s, "too many keysyms (%d) on left-hand side; skipping line",
559                          MAX_LHS_LEN + 1);
560             goto skip;
561         }
562         production.lhs[production.len++] = keysym;
563         goto lhs;
564     case TOK_COLON:
565         if (production.len <= 0) {
566             scanner_warn(s, "expected at least one keysym on left-hand side; skipping line");
567             goto skip;
568         }
569         goto rhs;
570     default:
571         goto unexpected;
572     }
573
574 rhs:
575     switch (tok = lex(s, &val)) {
576     case TOK_STRING:
577         if (production.has_string) {
578             scanner_warn(s, "right-hand side can have at most one string; skipping line");
579             goto skip;
580         }
581         if (val.string.len <= 0) {
582             scanner_warn(s, "right-hand side string must not be empty; skipping line");
583             goto skip;
584         }
585         if (val.string.len >= sizeof(production.string)) {
586             scanner_warn(s, "right-hand side string is too long; skipping line");
587             goto skip;
588         }
589         strcpy(production.string, val.string.str);
590         production.has_string = true;
591         goto rhs;
592     case TOK_RHS_KEYSYM:
593         keysym = cached_keysym_from_name(cache, val.string.str, val.string.len);
594         if (keysym == XKB_KEY_NoSymbol) {
595             scanner_err(s, "unrecognized keysym \"%s\" on right-hand side",
596                         val.string.str);
597             goto error;
598         }
599         if (production.has_keysym) {
600             scanner_warn(s, "right-hand side can have at most one keysym; skipping line");
601             goto skip;
602         }
603         production.keysym = keysym;
604         production.has_keysym = true;
605     case TOK_END_OF_LINE:
606         if (!production.has_string && !production.has_keysym) {
607             scanner_warn(s, "right-hand side must have at least one of string or keysym; skipping line");
608             goto skip;
609         }
610         add_production(table, s, &production);
611         goto initial;
612     default:
613         goto unexpected;
614     }
615
616 unexpected:
617     if (tok != TOK_ERROR)
618         scanner_err(s, "unexpected token");
619 error:
620     num_errors++;
621     if (num_errors <= MAX_ERRORS)
622         goto skip;
623
624     scanner_err(s, "too many errors");
625     goto fail;
626
627 fail:
628     scanner_err(s, "failed to parse file");
629     return false;
630
631 skip:
632     while (tok != TOK_END_OF_LINE && tok != TOK_END_OF_FILE)
633         tok = lex(s, &val);
634     goto initial;
635
636 finished:
637     return true;
638 }
639
640 bool
641 parse_string(struct xkb_compose_table *table, const char *string, size_t len,
642              const char *file_name)
643 {
644     struct scanner s;
645     struct keysym_from_name_cache cache;
646     memset(&cache, 0, sizeof(cache));
647     scanner_init(&s, table->ctx, string, len, file_name, &cache);
648     if (!parse(table, &s, 0))
649         return false;
650     /* Maybe the allocator can use the excess space. */
651     darray_shrink(table->nodes);
652     darray_shrink(table->utf8);
653     return true;
654 }
655
656 bool
657 parse_file(struct xkb_compose_table *table, FILE *file, const char *file_name)
658 {
659     bool ok;
660     const char *string;
661     size_t size;
662
663     ok = map_file(file, &string, &size);
664     if (!ok) {
665         log_err(table->ctx, "Couldn't read Compose file %s: %s\n",
666                 file_name, strerror(errno));
667         return false;
668     }
669
670     ok = parse_string(table, string, size, file_name);
671     unmap_file(string, size);
672     return ok;
673 }