1 /************************************************************
2  * Copyright (c) 1996 by Silicon Graphics Computer Systems, Inc.
3  *
4  * Permission to use, copy, modify, and distribute this
5  * software and its documentation for any purpose and without
6  * fee is hereby granted, provided that the above copyright
7  * notice appear in all copies and that both that copyright
8  * notice and this permission notice appear in supporting
9  * documentation, and that the name of Silicon Graphics not be
10  * used in advertising or publicity pertaining to distribution
11  * of the software without specific prior written permission.
12  * Silicon Graphics makes no representation about the suitability
13  * of this software for any purpose. It is provided "as is"
14  * without any express or implied warranty.
15  *
16  * SILICON GRAPHICS DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
17  * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
18  * AND FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT SHALL SILICON
19  * GRAPHICS BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
20  * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
21  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
22  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION  WITH
23  * THE USE OR PERFORMANCE OF THIS SOFTWARE.
24  *
25  ********************************************************/
26 
27 /*
28  * Copyright © 2012 Ran Benita <ran234@gmail.com>
29  *
30  * Permission is hereby granted, free of charge, to any person obtaining a
31  * copy of this software and associated documentation files (the "Software"),
32  * to deal in the Software without restriction, including without limitation
33  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
34  * and/or sell copies of the Software, and to permit persons to whom the
35  * Software is furnished to do so, subject to the following conditions:
36  *
37  * The above copyright notice and this permission notice (including the next
38  * paragraph) shall be included in all copies or substantial portions of the
39  * Software.
40  *
41  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
42  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
43  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
44  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
45  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
46  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
47  * DEALINGS IN THE SOFTWARE.
48  */
49 
50 #include "config.h"
51 
52 #include "xkbcomp-priv.h"
53 #include "rules.h"
54 #include "include.h"
55 #include "scanner-utils.h"
56 
57 #define MAX_INCLUDE_DEPTH 5
58 
59 /* Scanner / Lexer */
60 
61 /* Values returned with some tokens, like yylval. */
62 union lvalue {
63     struct sval string;
64 };
65 
66 enum rules_token {
67     TOK_END_OF_FILE = 0,
68     TOK_END_OF_LINE,
69     TOK_IDENTIFIER,
70     TOK_GROUP_NAME,
71     TOK_BANG,
72     TOK_EQUALS,
73     TOK_STAR,
74     TOK_INCLUDE,
75     TOK_ERROR
76 };
77 
78 static inline bool
is_ident(char ch)79 is_ident(char ch)
80 {
81     return is_graph(ch) && ch != '\\';
82 }
83 
84 static enum rules_token
lex(struct scanner * s,union lvalue * val)85 lex(struct scanner *s, union lvalue *val)
86 {
87 skip_more_whitespace_and_comments:
88     /* Skip spaces. */
89     while (chr(s, ' ') || chr(s, '\t') || chr(s, '\r'));
90 
91     /* Skip comments. */
92     if (lit(s, "//")) {
93         skip_to_eol(s);
94     }
95 
96     /* New line. */
97     if (eol(s)) {
98         while (eol(s)) next(s);
99         return TOK_END_OF_LINE;
100     }
101 
102     /* Escaped line continuation. */
103     if (chr(s, '\\')) {
104         /* Optional \r. */
105         chr(s, '\r');
106         if (!eol(s)) {
107             scanner_err(s, "illegal new line escape; must appear at end of line");
108             return TOK_ERROR;
109         }
110         next(s);
111         goto skip_more_whitespace_and_comments;
112     }
113 
114     /* See if we're done. */
115     if (eof(s)) return TOK_END_OF_FILE;
116 
117     /* New token. */
118     s->token_line = s->line;
119     s->token_column = s->column;
120 
121     /* Operators and punctuation. */
122     if (chr(s, '!')) return TOK_BANG;
123     if (chr(s, '=')) return TOK_EQUALS;
124     if (chr(s, '*')) return TOK_STAR;
125 
126     /* Group name. */
127     if (chr(s, '$')) {
128         val->string.start = s->s + s->pos;
129         val->string.len = 0;
130         while (is_ident(peek(s))) {
131             next(s);
132             val->string.len++;
133         }
134         if (val->string.len == 0) {
135             scanner_err(s, "unexpected character after \'$\'; expected name");
136             return TOK_ERROR;
137         }
138         return TOK_GROUP_NAME;
139     }
140 
141     /* Include statement. */
142     if (lit(s, "include"))
143         return TOK_INCLUDE;
144 
145     /* Identifier. */
146     if (is_ident(peek(s))) {
147         val->string.start = s->s + s->pos;
148         val->string.len = 0;
149         while (is_ident(peek(s))) {
150             next(s);
151             val->string.len++;
152         }
153         return TOK_IDENTIFIER;
154     }
155 
156     scanner_err(s, "unrecognized token");
157     return TOK_ERROR;
158 }
159 
160 /***====================================================================***/
161 
162 enum rules_mlvo {
163     MLVO_MODEL,
164     MLVO_LAYOUT,
165     MLVO_VARIANT,
166     MLVO_OPTION,
167     _MLVO_NUM_ENTRIES
168 };
169 
170 #define SVAL_LIT(literal) { literal, sizeof(literal) - 1 }
171 
172 static const struct sval rules_mlvo_svals[_MLVO_NUM_ENTRIES] = {
173     [MLVO_MODEL] = SVAL_LIT("model"),
174     [MLVO_LAYOUT] = SVAL_LIT("layout"),
175     [MLVO_VARIANT] = SVAL_LIT("variant"),
176     [MLVO_OPTION] = SVAL_LIT("option"),
177 };
178 
179 enum rules_kccgst {
180     KCCGST_KEYCODES,
181     KCCGST_TYPES,
182     KCCGST_COMPAT,
183     KCCGST_SYMBOLS,
184     KCCGST_GEOMETRY,
185     _KCCGST_NUM_ENTRIES
186 };
187 
188 static const struct sval rules_kccgst_svals[_KCCGST_NUM_ENTRIES] = {
189     [KCCGST_KEYCODES] = SVAL_LIT("keycodes"),
190     [KCCGST_TYPES] = SVAL_LIT("types"),
191     [KCCGST_COMPAT] = SVAL_LIT("compat"),
192     [KCCGST_SYMBOLS] = SVAL_LIT("symbols"),
193     [KCCGST_GEOMETRY] = SVAL_LIT("geometry"),
194 };
195 
196 /* We use this to keep score whether an mlvo was matched or not; if not,
197  * we warn the user that his preference was ignored. */
198 struct matched_sval {
199     struct sval sval;
200     bool matched;
201 };
202 typedef darray(struct matched_sval) darray_matched_sval;
203 
204 /*
205  * A broken-down version of xkb_rule_names (without the rules,
206  * obviously).
207  */
208 struct rule_names {
209     struct matched_sval model;
210     darray_matched_sval layouts;
211     darray_matched_sval variants;
212     darray_matched_sval options;
213 };
214 
215 struct group {
216     struct sval name;
217     darray_sval elements;
218 };
219 
220 struct mapping {
221     int mlvo_at_pos[_MLVO_NUM_ENTRIES];
222     unsigned int num_mlvo;
223     unsigned int defined_mlvo_mask;
224     xkb_layout_index_t layout_idx, variant_idx;
225     int kccgst_at_pos[_KCCGST_NUM_ENTRIES];
226     unsigned int num_kccgst;
227     unsigned int defined_kccgst_mask;
228     bool skip;
229 };
230 
231 enum mlvo_match_type {
232     MLVO_MATCH_NORMAL = 0,
233     MLVO_MATCH_WILDCARD,
234     MLVO_MATCH_GROUP,
235 };
236 
237 struct rule {
238     struct sval mlvo_value_at_pos[_MLVO_NUM_ENTRIES];
239     enum mlvo_match_type match_type_at_pos[_MLVO_NUM_ENTRIES];
240     unsigned int num_mlvo_values;
241     struct sval kccgst_value_at_pos[_KCCGST_NUM_ENTRIES];
242     unsigned int num_kccgst_values;
243     bool skip;
244 };
245 
246 /*
247  * This is the main object used to match a given RMLVO against a rules
248  * file and aggragate the results in a KcCGST. It goes through a simple
249  * matching state machine, with tokens as transitions (see
250  * matcher_match()).
251  */
252 struct matcher {
253     struct xkb_context *ctx;
254     /* Input.*/
255     struct rule_names rmlvo;
256     union lvalue val;
257     darray(struct group) groups;
258     /* Current mapping. */
259     struct mapping mapping;
260     /* Current rule. */
261     struct rule rule;
262     /* Output. */
263     darray_char kccgst[_KCCGST_NUM_ENTRIES];
264 };
265 
266 static struct sval
strip_spaces(struct sval v)267 strip_spaces(struct sval v)
268 {
269     while (v.len > 0 && is_space(v.start[0])) { v.len--; v.start++; }
270     while (v.len > 0 && is_space(v.start[v.len - 1])) v.len--;
271     return v;
272 }
273 
274 static darray_matched_sval
split_comma_separated_mlvo(const char * s)275 split_comma_separated_mlvo(const char *s)
276 {
277     darray_matched_sval arr = darray_new();
278 
279     /*
280      * Make sure the array returned by this function always includes at
281      * least one value, e.g. "" -> { "" } and "," -> { "", "" }.
282      */
283 
284     if (!s) {
285         struct matched_sval val = { .sval = { NULL, 0 } };
286         darray_append(arr, val);
287         return arr;
288     }
289 
290     while (true) {
291         struct matched_sval val = { .sval = { s, 0 } };
292         while (*s != '\0' && *s != ',') { s++; val.sval.len++; }
293         val.sval = strip_spaces(val.sval);
294         darray_append(arr, val);
295         if (*s == '\0') break;
296         if (*s == ',') s++;
297     }
298 
299     return arr;
300 }
301 
302 static struct matcher *
matcher_new(struct xkb_context * ctx,const struct xkb_rule_names * rmlvo)303 matcher_new(struct xkb_context *ctx,
304             const struct xkb_rule_names *rmlvo)
305 {
306     struct matcher *m = calloc(1, sizeof(*m));
307     if (!m)
308         return NULL;
309 
310     m->ctx = ctx;
311     m->rmlvo.model.sval.start = rmlvo->model;
312     m->rmlvo.model.sval.len = strlen_safe(rmlvo->model);
313     m->rmlvo.layouts = split_comma_separated_mlvo(rmlvo->layout);
314     m->rmlvo.variants = split_comma_separated_mlvo(rmlvo->variant);
315     m->rmlvo.options = split_comma_separated_mlvo(rmlvo->options);
316 
317     return m;
318 }
319 
320 static void
matcher_free(struct matcher * m)321 matcher_free(struct matcher *m)
322 {
323     struct group *group;
324     if (!m)
325         return;
326     darray_free(m->rmlvo.layouts);
327     darray_free(m->rmlvo.variants);
328     darray_free(m->rmlvo.options);
329     darray_foreach(group, m->groups)
330         darray_free(group->elements);
331     for (int i = 0; i < _KCCGST_NUM_ENTRIES; i++)
332         darray_free(m->kccgst[i]);
333     darray_free(m->groups);
334     free(m);
335 }
336 
337 static void
matcher_group_start_new(struct matcher * m,struct sval name)338 matcher_group_start_new(struct matcher *m, struct sval name)
339 {
340     struct group group = { .name = name, .elements = darray_new() };
341     darray_append(m->groups, group);
342 }
343 
344 static void
matcher_group_add_element(struct matcher * m,struct scanner * s,struct sval element)345 matcher_group_add_element(struct matcher *m, struct scanner *s,
346                           struct sval element)
347 {
348     darray_append(darray_item(m->groups, darray_size(m->groups) - 1).elements,
349                   element);
350 }
351 
352 static bool
353 read_rules_file(struct xkb_context *ctx,
354                 struct matcher *matcher,
355                 unsigned include_depth,
356                 FILE *file,
357                 const char *path);
358 
359 static void
matcher_include(struct matcher * m,struct scanner * parent_scanner,unsigned include_depth,struct sval inc)360 matcher_include(struct matcher *m, struct scanner *parent_scanner,
361                 unsigned include_depth,
362                 struct sval inc)
363 {
364     struct scanner s; /* parses the !include value */
365     FILE *file;
366 
367     scanner_init(&s, m->ctx, inc.start, inc.len,
368                  parent_scanner->file_name, NULL);
369     s.token_line = parent_scanner->token_line;
370     s.token_column = parent_scanner->token_column;
371     s.buf_pos = 0;
372 
373     if (include_depth >= MAX_INCLUDE_DEPTH) {
374         scanner_err(&s, "maximum include depth (%d) exceeded; maybe there is an include loop?",
375                     MAX_INCLUDE_DEPTH);
376         return;
377     }
378 
379     while (!eof(&s) && !eol(&s)) {
380         if (chr(&s, '%')) {
381             if (chr(&s, '%')) {
382                 buf_append(&s, '%');
383             }
384             else if (chr(&s, 'H')) {
385                 const char *home = secure_getenv("HOME");
386                 if (!home) {
387                     scanner_err(&s, "%%H was used in an include statement, but the HOME environment variable is not set");
388                     return;
389                 }
390                 if (!buf_appends(&s, home)) {
391                     scanner_err(&s, "include path after expanding %%H is too long");
392                     return;
393                 }
394             }
395             else if (chr(&s, 'S')) {
396                 const char *default_root = xkb_context_include_path_get_system_path(m->ctx);
397                 if (!buf_appends(&s, default_root) || !buf_appends(&s, "/rules")) {
398                     scanner_err(&s, "include path after expanding %%S is too long");
399                     return;
400                 }
401             }
402             else if (chr(&s, 'E')) {
403                 const char *default_root = xkb_context_include_path_get_extra_path(m->ctx);
404                 if (!buf_appends(&s, default_root) || !buf_appends(&s, "/rules")) {
405                     scanner_err(&s, "include path after expanding %%E is too long");
406                     return;
407                 }
408             }
409             else {
410                 scanner_err(&s, "unknown %% format (%c) in include statement", peek(&s));
411                 return;
412             }
413         }
414         else {
415             buf_append(&s, next(&s));
416         }
417     }
418     if (!buf_append(&s, '\0')) {
419         scanner_err(&s, "include path is too long");
420         return;
421     }
422 
423     file = fopen(s.buf, "rb");
424     if (file) {
425         bool ret = read_rules_file(m->ctx, m, include_depth + 1, file, s.buf);
426         if (!ret)
427             log_err(m->ctx, "No components returned from included XKB rules \"%s\"\n", s.buf);
428         fclose(file);
429     } else {
430         log_err(m->ctx, "Failed to open included XKB rules \"%s\"\n", s.buf);
431     }
432 }
433 
434 static void
matcher_mapping_start_new(struct matcher * m)435 matcher_mapping_start_new(struct matcher *m)
436 {
437     for (unsigned i = 0; i < _MLVO_NUM_ENTRIES; i++)
438         m->mapping.mlvo_at_pos[i] = -1;
439     for (unsigned i = 0; i < _KCCGST_NUM_ENTRIES; i++)
440         m->mapping.kccgst_at_pos[i] = -1;
441     m->mapping.layout_idx = m->mapping.variant_idx = XKB_LAYOUT_INVALID;
442     m->mapping.num_mlvo = m->mapping.num_kccgst = 0;
443     m->mapping.defined_mlvo_mask = 0;
444     m->mapping.defined_kccgst_mask = 0;
445     m->mapping.skip = false;
446 }
447 
448 static int
extract_layout_index(const char * s,size_t max_len,xkb_layout_index_t * out)449 extract_layout_index(const char *s, size_t max_len, xkb_layout_index_t *out)
450 {
451     /* This function is pretty stupid, but works for now. */
452     *out = XKB_LAYOUT_INVALID;
453     if (max_len < 3)
454         return -1;
455     if (s[0] != '[' || !is_digit(s[1]) || s[2] != ']')
456         return -1;
457     if (s[1] - '0' < 1 || s[1] - '0' > XKB_MAX_GROUPS)
458         return -1;
459     /* To zero-based index. */
460     *out = s[1] - '0' - 1;
461     return 3;
462 }
463 
464 static void
matcher_mapping_set_mlvo(struct matcher * m,struct scanner * s,struct sval ident)465 matcher_mapping_set_mlvo(struct matcher *m, struct scanner *s,
466                          struct sval ident)
467 {
468     enum rules_mlvo mlvo;
469     struct sval mlvo_sval;
470 
471     for (mlvo = 0; mlvo < _MLVO_NUM_ENTRIES; mlvo++) {
472         mlvo_sval = rules_mlvo_svals[mlvo];
473 
474         if (svaleq_prefix(mlvo_sval, ident))
475             break;
476     }
477 
478     /* Not found. */
479     if (mlvo >= _MLVO_NUM_ENTRIES) {
480         scanner_err(s, "invalid mapping: %.*s is not a valid value here; ignoring rule set",
481                     ident.len, ident.start);
482         m->mapping.skip = true;
483         return;
484     }
485 
486     if (m->mapping.defined_mlvo_mask & (1u << mlvo)) {
487         scanner_err(s, "invalid mapping: %.*s appears twice on the same line; ignoring rule set",
488                     mlvo_sval.len, mlvo_sval.start);
489         m->mapping.skip = true;
490         return;
491     }
492 
493     /* If there are leftovers still, it must be an index. */
494     if (mlvo_sval.len < ident.len) {
495         xkb_layout_index_t idx;
496         int consumed = extract_layout_index(ident.start + mlvo_sval.len,
497                                             ident.len - mlvo_sval.len, &idx);
498         if ((int) (ident.len - mlvo_sval.len) != consumed) {
499             scanner_err(s, "invalid mapping: \"%.*s\" may only be followed by a valid group index; ignoring rule set",
500                         mlvo_sval.len, mlvo_sval.start);
501             m->mapping.skip = true;
502             return;
503         }
504 
505         if (mlvo == MLVO_LAYOUT) {
506             m->mapping.layout_idx = idx;
507         }
508         else if (mlvo == MLVO_VARIANT) {
509             m->mapping.variant_idx = idx;
510         }
511         else {
512             scanner_err(s, "invalid mapping: \"%.*s\" cannot be followed by a group index; ignoring rule set",
513                         mlvo_sval.len, mlvo_sval.start);
514             m->mapping.skip = true;
515             return;
516         }
517     }
518 
519     m->mapping.mlvo_at_pos[m->mapping.num_mlvo] = mlvo;
520     m->mapping.defined_mlvo_mask |= 1u << mlvo;
521     m->mapping.num_mlvo++;
522 }
523 
524 static void
matcher_mapping_set_kccgst(struct matcher * m,struct scanner * s,struct sval ident)525 matcher_mapping_set_kccgst(struct matcher *m, struct scanner *s, struct sval ident)
526 {
527     enum rules_kccgst kccgst;
528     struct sval kccgst_sval;
529 
530     for (kccgst = 0; kccgst < _KCCGST_NUM_ENTRIES; kccgst++) {
531         kccgst_sval = rules_kccgst_svals[kccgst];
532 
533         if (svaleq(rules_kccgst_svals[kccgst], ident))
534             break;
535     }
536 
537     /* Not found. */
538     if (kccgst >= _KCCGST_NUM_ENTRIES) {
539         scanner_err(s, "invalid mapping: %.*s is not a valid value here; ignoring rule set",
540                     ident.len, ident.start);
541         m->mapping.skip = true;
542         return;
543     }
544 
545     if (m->mapping.defined_kccgst_mask & (1u << kccgst)) {
546         scanner_err(s, "invalid mapping: %.*s appears twice on the same line; ignoring rule set",
547                     kccgst_sval.len, kccgst_sval.start);
548         m->mapping.skip = true;
549         return;
550     }
551 
552     m->mapping.kccgst_at_pos[m->mapping.num_kccgst] = kccgst;
553     m->mapping.defined_kccgst_mask |= 1u << kccgst;
554     m->mapping.num_kccgst++;
555 }
556 
557 static void
matcher_mapping_verify(struct matcher * m,struct scanner * s)558 matcher_mapping_verify(struct matcher *m, struct scanner *s)
559 {
560     if (m->mapping.num_mlvo == 0) {
561         scanner_err(s, "invalid mapping: must have at least one value on the left hand side; ignoring rule set");
562         goto skip;
563     }
564 
565     if (m->mapping.num_kccgst == 0) {
566         scanner_err(s, "invalid mapping: must have at least one value on the right hand side; ignoring rule set");
567         goto skip;
568     }
569 
570     /*
571      * This following is very stupid, but this is how it works.
572      * See the "Notes" section in the overview above.
573      */
574 
575     if (m->mapping.defined_mlvo_mask & (1u << MLVO_LAYOUT)) {
576         if (m->mapping.layout_idx == XKB_LAYOUT_INVALID) {
577             if (darray_size(m->rmlvo.layouts) > 1)
578                 goto skip;
579         }
580         else {
581             if (darray_size(m->rmlvo.layouts) == 1 ||
582                 m->mapping.layout_idx >= darray_size(m->rmlvo.layouts))
583                 goto skip;
584         }
585     }
586 
587     if (m->mapping.defined_mlvo_mask & (1u << MLVO_VARIANT)) {
588         if (m->mapping.variant_idx == XKB_LAYOUT_INVALID) {
589             if (darray_size(m->rmlvo.variants) > 1)
590                 goto skip;
591         }
592         else {
593             if (darray_size(m->rmlvo.variants) == 1 ||
594                 m->mapping.variant_idx >= darray_size(m->rmlvo.variants))
595                 goto skip;
596         }
597     }
598 
599     return;
600 
601 skip:
602     m->mapping.skip = true;
603 }
604 
605 static void
matcher_rule_start_new(struct matcher * m)606 matcher_rule_start_new(struct matcher *m)
607 {
608     memset(&m->rule, 0, sizeof(m->rule));
609     m->rule.skip = m->mapping.skip;
610 }
611 
612 static void
matcher_rule_set_mlvo_common(struct matcher * m,struct scanner * s,struct sval ident,enum mlvo_match_type match_type)613 matcher_rule_set_mlvo_common(struct matcher *m, struct scanner *s,
614                              struct sval ident,
615                              enum mlvo_match_type match_type)
616 {
617     if (m->rule.num_mlvo_values + 1 > m->mapping.num_mlvo) {
618         scanner_err(s, "invalid rule: has more values than the mapping line; ignoring rule");
619         m->rule.skip = true;
620         return;
621     }
622     m->rule.match_type_at_pos[m->rule.num_mlvo_values] = match_type;
623     m->rule.mlvo_value_at_pos[m->rule.num_mlvo_values] = ident;
624     m->rule.num_mlvo_values++;
625 }
626 
627 static void
matcher_rule_set_mlvo_wildcard(struct matcher * m,struct scanner * s)628 matcher_rule_set_mlvo_wildcard(struct matcher *m, struct scanner *s)
629 {
630     struct sval dummy = { NULL, 0 };
631     matcher_rule_set_mlvo_common(m, s, dummy, MLVO_MATCH_WILDCARD);
632 }
633 
634 static void
matcher_rule_set_mlvo_group(struct matcher * m,struct scanner * s,struct sval ident)635 matcher_rule_set_mlvo_group(struct matcher *m, struct scanner *s,
636                             struct sval ident)
637 {
638     matcher_rule_set_mlvo_common(m, s, ident, MLVO_MATCH_GROUP);
639 }
640 
641 static void
matcher_rule_set_mlvo(struct matcher * m,struct scanner * s,struct sval ident)642 matcher_rule_set_mlvo(struct matcher *m, struct scanner *s,
643                       struct sval ident)
644 {
645     matcher_rule_set_mlvo_common(m, s, ident, MLVO_MATCH_NORMAL);
646 }
647 
648 static void
matcher_rule_set_kccgst(struct matcher * m,struct scanner * s,struct sval ident)649 matcher_rule_set_kccgst(struct matcher *m, struct scanner *s,
650                         struct sval ident)
651 {
652     if (m->rule.num_kccgst_values + 1 > m->mapping.num_kccgst) {
653         scanner_err(s, "invalid rule: has more values than the mapping line; ignoring rule");
654         m->rule.skip = true;
655         return;
656     }
657     m->rule.kccgst_value_at_pos[m->rule.num_kccgst_values] = ident;
658     m->rule.num_kccgst_values++;
659 }
660 
661 static bool
match_group(struct matcher * m,struct sval group_name,struct sval to)662 match_group(struct matcher *m, struct sval group_name, struct sval to)
663 {
664     struct group *group;
665     struct sval *element;
666     bool found = false;
667 
668     darray_foreach(group, m->groups) {
669         if (svaleq(group->name, group_name)) {
670             found = true;
671             break;
672         }
673     }
674 
675     if (!found) {
676         /*
677          * rules/evdev intentionally uses some undeclared group names
678          * in rules (e.g. commented group definitions which may be
679          * uncommented if needed). So we continue silently.
680          */
681         return false;
682     }
683 
684     darray_foreach(element, group->elements)
685         if (svaleq(to, *element))
686             return true;
687 
688     return false;
689 }
690 
691 static bool
match_value(struct matcher * m,struct sval val,struct sval to,enum mlvo_match_type match_type)692 match_value(struct matcher *m, struct sval val, struct sval to,
693             enum mlvo_match_type match_type)
694 {
695     if (match_type == MLVO_MATCH_WILDCARD)
696         return true;
697     if (match_type == MLVO_MATCH_GROUP)
698         return match_group(m, val, to);
699     return svaleq(val, to);
700 }
701 
702 static bool
match_value_and_mark(struct matcher * m,struct sval val,struct matched_sval * to,enum mlvo_match_type match_type)703 match_value_and_mark(struct matcher *m, struct sval val,
704                      struct matched_sval *to, enum mlvo_match_type match_type)
705 {
706     bool matched = match_value(m, val, to->sval, match_type);
707     if (matched)
708         to->matched = true;
709     return matched;
710 }
711 
712 /*
713  * This function performs %-expansion on @value (see overview above),
714  * and appends the result to @to.
715  */
716 static bool
append_expanded_kccgst_value(struct matcher * m,struct scanner * s,darray_char * to,struct sval value)717 append_expanded_kccgst_value(struct matcher *m, struct scanner *s,
718                              darray_char *to, struct sval value)
719 {
720     const char *str = value.start;
721     darray_char expanded = darray_new();
722     char ch;
723     bool expanded_plus, to_plus;
724 
725     /*
726      * Some ugly hand-lexing here, but going through the scanner is more
727      * trouble than it's worth, and the format is ugly on its own merit.
728      */
729     for (unsigned i = 0; i < value.len; ) {
730         enum rules_mlvo mlv;
731         xkb_layout_index_t idx;
732         char pfx, sfx;
733         struct matched_sval *expanded_value;
734 
735         /* Check if that's a start of an expansion. */
736         if (str[i] != '%') {
737             /* Just a normal character. */
738             darray_appends_nullterminate(expanded, &str[i++], 1);
739             continue;
740         }
741         if (++i >= value.len) goto error;
742 
743         pfx = sfx = 0;
744 
745         /* Check for prefix. */
746         if (str[i] == '(' || str[i] == '+' || str[i] == '|' ||
747             str[i] == '_' || str[i] == '-') {
748             pfx = str[i];
749             if (str[i] == '(') sfx = ')';
750             if (++i >= value.len) goto error;
751         }
752 
753         /* Mandatory model/layout/variant specifier. */
754         switch (str[i++]) {
755         case 'm': mlv = MLVO_MODEL; break;
756         case 'l': mlv = MLVO_LAYOUT; break;
757         case 'v': mlv = MLVO_VARIANT; break;
758         default: goto error;
759         }
760 
761         /* Check for index. */
762         idx = XKB_LAYOUT_INVALID;
763         if (i < value.len && str[i] == '[') {
764             int consumed;
765 
766             if (mlv != MLVO_LAYOUT && mlv != MLVO_VARIANT) {
767                 scanner_err(s, "invalid index in %%-expansion; may only index layout or variant");
768                 goto error;
769             }
770 
771             consumed = extract_layout_index(str + i, value.len - i, &idx);
772             if (consumed == -1) goto error;
773             i += consumed;
774         }
775 
776         /* Check for suffix, if there supposed to be one. */
777         if (sfx != 0) {
778             if (i >= value.len) goto error;
779             if (str[i++] != sfx) goto error;
780         }
781 
782         /* Get the expanded value. */
783         expanded_value = NULL;
784 
785         if (mlv == MLVO_LAYOUT) {
786             if (idx != XKB_LAYOUT_INVALID &&
787                 idx < darray_size(m->rmlvo.layouts) &&
788                 darray_size(m->rmlvo.layouts) > 1)
789                 expanded_value = &darray_item(m->rmlvo.layouts, idx);
790             else if (idx == XKB_LAYOUT_INVALID &&
791                      darray_size(m->rmlvo.layouts) == 1)
792                 expanded_value = &darray_item(m->rmlvo.layouts, 0);
793         }
794         else if (mlv == MLVO_VARIANT) {
795             if (idx != XKB_LAYOUT_INVALID &&
796                 idx < darray_size(m->rmlvo.variants) &&
797                 darray_size(m->rmlvo.variants) > 1)
798                 expanded_value = &darray_item(m->rmlvo.variants, idx);
799             else if (idx == XKB_LAYOUT_INVALID &&
800                      darray_size(m->rmlvo.variants) == 1)
801                 expanded_value = &darray_item(m->rmlvo.variants, 0);
802         }
803         else if (mlv == MLVO_MODEL) {
804             expanded_value = &m->rmlvo.model;
805         }
806 
807         /* If we didn't get one, skip silently. */
808         if (!expanded_value || expanded_value->sval.len == 0)
809             continue;
810 
811         if (pfx != 0)
812             darray_appends_nullterminate(expanded, &pfx, 1);
813         darray_appends_nullterminate(expanded,
814                                      expanded_value->sval.start,
815                                      expanded_value->sval.len);
816         if (sfx != 0)
817             darray_appends_nullterminate(expanded, &sfx, 1);
818         expanded_value->matched = true;
819     }
820 
821     /*
822      * Appending  bar to  foo ->  foo (not an error if this happens)
823      * Appending +bar to  foo ->  foo+bar
824      * Appending  bar to +foo ->  bar+foo
825      * Appending +bar to +foo -> +foo+bar
826      */
827 
828     ch = (darray_empty(expanded) ? '\0' : darray_item(expanded, 0));
829     expanded_plus = (ch == '+' || ch == '|');
830     ch = (darray_empty(*to) ? '\0' : darray_item(*to, 0));
831     to_plus = (ch == '+' || ch == '|');
832 
833     if (expanded_plus || darray_empty(*to))
834         darray_appends_nullterminate(*to, expanded.item, expanded.size);
835     else if (to_plus)
836         darray_prepends_nullterminate(*to, expanded.item, expanded.size);
837 
838     darray_free(expanded);
839     return true;
840 
841 error:
842     darray_free(expanded);
843     scanner_err(s, "invalid %%-expansion in value; not used");
844     return false;
845 }
846 
847 static void
matcher_rule_verify(struct matcher * m,struct scanner * s)848 matcher_rule_verify(struct matcher *m, struct scanner *s)
849 {
850     if (m->rule.num_mlvo_values != m->mapping.num_mlvo ||
851         m->rule.num_kccgst_values != m->mapping.num_kccgst) {
852         scanner_err(s, "invalid rule: must have same number of values as mapping line; ignoring rule");
853         m->rule.skip = true;
854     }
855 }
856 
857 static void
matcher_rule_apply_if_matches(struct matcher * m,struct scanner * s)858 matcher_rule_apply_if_matches(struct matcher *m, struct scanner *s)
859 {
860     for (unsigned i = 0; i < m->mapping.num_mlvo; i++) {
861         enum rules_mlvo mlvo = m->mapping.mlvo_at_pos[i];
862         struct sval value = m->rule.mlvo_value_at_pos[i];
863         enum mlvo_match_type match_type = m->rule.match_type_at_pos[i];
864         struct matched_sval *to;
865         bool matched = false;
866 
867         if (mlvo == MLVO_MODEL) {
868             to = &m->rmlvo.model;
869             matched = match_value_and_mark(m, value, to, match_type);
870         }
871         else if (mlvo == MLVO_LAYOUT) {
872             xkb_layout_index_t idx = m->mapping.layout_idx;
873             idx = (idx == XKB_LAYOUT_INVALID ? 0 : idx);
874             to = &darray_item(m->rmlvo.layouts, idx);
875             matched = match_value_and_mark(m, value, to, match_type);
876         }
877         else if (mlvo == MLVO_VARIANT) {
878             xkb_layout_index_t idx = m->mapping.layout_idx;
879             idx = (idx == XKB_LAYOUT_INVALID ? 0 : idx);
880             to = &darray_item(m->rmlvo.variants, idx);
881             matched = match_value_and_mark(m, value, to, match_type);
882         }
883         else if (mlvo == MLVO_OPTION) {
884             darray_foreach(to, m->rmlvo.options) {
885                 matched = match_value_and_mark(m, value, to, match_type);
886                 if (matched)
887                     break;
888             }
889         }
890 
891         if (!matched)
892             return;
893     }
894 
895     for (unsigned i = 0; i < m->mapping.num_kccgst; i++) {
896         enum rules_kccgst kccgst = m->mapping.kccgst_at_pos[i];
897         struct sval value = m->rule.kccgst_value_at_pos[i];
898         append_expanded_kccgst_value(m, s, &m->kccgst[kccgst], value);
899     }
900 
901     /*
902      * If a rule matches in a rule set, the rest of the set should be
903      * skipped. However, rule sets matching against options may contain
904      * several legitimate rules, so they are processed entirely.
905      */
906     if (!(m->mapping.defined_mlvo_mask & (1 << MLVO_OPTION)))
907         m->mapping.skip = true;
908 }
909 
910 static enum rules_token
gettok(struct matcher * m,struct scanner * s)911 gettok(struct matcher *m, struct scanner *s)
912 {
913     return lex(s, &m->val);
914 }
915 
916 static bool
matcher_match(struct matcher * m,struct scanner * s,unsigned include_depth,const char * string,size_t len,const char * file_name)917 matcher_match(struct matcher *m, struct scanner *s,
918               unsigned include_depth,
919               const char *string, size_t len,
920               const char *file_name)
921 {
922     enum rules_token tok;
923 
924     if (!m)
925         return false;
926 
927 initial:
928     switch (tok = gettok(m, s)) {
929     case TOK_BANG:
930         goto bang;
931     case TOK_END_OF_LINE:
932         goto initial;
933     case TOK_END_OF_FILE:
934         goto finish;
935     default:
936         goto unexpected;
937     }
938 
939 bang:
940     switch (tok = gettok(m, s)) {
941     case TOK_GROUP_NAME:
942         matcher_group_start_new(m, m->val.string);
943         goto group_name;
944     case TOK_INCLUDE:
945         goto include_statement;
946     case TOK_IDENTIFIER:
947         matcher_mapping_start_new(m);
948         matcher_mapping_set_mlvo(m, s, m->val.string);
949         goto mapping_mlvo;
950     default:
951         goto unexpected;
952     }
953 
954 group_name:
955     switch (tok = gettok(m, s)) {
956     case TOK_EQUALS:
957         goto group_element;
958     default:
959         goto unexpected;
960     }
961 
962 group_element:
963     switch (tok = gettok(m, s)) {
964     case TOK_IDENTIFIER:
965         matcher_group_add_element(m, s, m->val.string);
966         goto group_element;
967     case TOK_END_OF_LINE:
968         goto initial;
969     default:
970         goto unexpected;
971     }
972 
973 include_statement:
974     switch (tok = gettok(m, s)) {
975     case TOK_IDENTIFIER:
976         matcher_include(m, s, include_depth, m->val.string);
977         goto initial;
978     default:
979         goto unexpected;
980     }
981 
982 mapping_mlvo:
983     switch (tok = gettok(m, s)) {
984     case TOK_IDENTIFIER:
985         if (!m->mapping.skip)
986             matcher_mapping_set_mlvo(m, s, m->val.string);
987         goto mapping_mlvo;
988     case TOK_EQUALS:
989         goto mapping_kccgst;
990     default:
991         goto unexpected;
992     }
993 
994 mapping_kccgst:
995     switch (tok = gettok(m, s)) {
996     case TOK_IDENTIFIER:
997         if (!m->mapping.skip)
998             matcher_mapping_set_kccgst(m, s, m->val.string);
999         goto mapping_kccgst;
1000     case TOK_END_OF_LINE:
1001         if (!m->mapping.skip)
1002             matcher_mapping_verify(m, s);
1003         goto rule_mlvo_first;
1004     default:
1005         goto unexpected;
1006     }
1007 
1008 rule_mlvo_first:
1009     switch (tok = gettok(m, s)) {
1010     case TOK_BANG:
1011         goto bang;
1012     case TOK_END_OF_LINE:
1013         goto rule_mlvo_first;
1014     case TOK_END_OF_FILE:
1015         goto finish;
1016     default:
1017         matcher_rule_start_new(m);
1018         goto rule_mlvo_no_tok;
1019     }
1020 
1021 rule_mlvo:
1022     tok = gettok(m, s);
1023 rule_mlvo_no_tok:
1024     switch (tok) {
1025     case TOK_IDENTIFIER:
1026         if (!m->rule.skip)
1027             matcher_rule_set_mlvo(m, s, m->val.string);
1028         goto rule_mlvo;
1029     case TOK_STAR:
1030         if (!m->rule.skip)
1031             matcher_rule_set_mlvo_wildcard(m, s);
1032         goto rule_mlvo;
1033     case TOK_GROUP_NAME:
1034         if (!m->rule.skip)
1035             matcher_rule_set_mlvo_group(m, s, m->val.string);
1036         goto rule_mlvo;
1037     case TOK_EQUALS:
1038         goto rule_kccgst;
1039     default:
1040         goto unexpected;
1041     }
1042 
1043 rule_kccgst:
1044     switch (tok = gettok(m, s)) {
1045     case TOK_IDENTIFIER:
1046         if (!m->rule.skip)
1047             matcher_rule_set_kccgst(m, s, m->val.string);
1048         goto rule_kccgst;
1049     case TOK_END_OF_LINE:
1050         if (!m->rule.skip)
1051             matcher_rule_verify(m, s);
1052         if (!m->rule.skip)
1053             matcher_rule_apply_if_matches(m, s);
1054         goto rule_mlvo_first;
1055     default:
1056         goto unexpected;
1057     }
1058 
1059 unexpected:
1060     switch (tok) {
1061     case TOK_ERROR:
1062         goto error;
1063     default:
1064         goto state_error;
1065     }
1066 
1067 finish:
1068     return true;
1069 
1070 state_error:
1071     scanner_err(s, "unexpected token");
1072 error:
1073     return false;
1074 }
1075 
1076 static bool
read_rules_file(struct xkb_context * ctx,struct matcher * matcher,unsigned include_depth,FILE * file,const char * path)1077 read_rules_file(struct xkb_context *ctx,
1078                 struct matcher *matcher,
1079                 unsigned include_depth,
1080                 FILE *file,
1081                 const char *path)
1082 {
1083     bool ret = false;
1084     char *string;
1085     size_t size;
1086     struct scanner scanner;
1087 
1088     ret = map_file(file, &string, &size);
1089     if (!ret) {
1090         log_err(ctx, "Couldn't read rules file \"%s\": %s\n",
1091                 path, strerror(errno));
1092         goto out;
1093     }
1094 
1095     scanner_init(&scanner, matcher->ctx, string, size, path, NULL);
1096 
1097     ret = matcher_match(matcher, &scanner, include_depth, string, size, path);
1098 
1099     unmap_file(string, size);
1100 out:
1101     return ret;
1102 }
1103 
1104 bool
xkb_components_from_rules(struct xkb_context * ctx,const struct xkb_rule_names * rmlvo,struct xkb_component_names * out)1105 xkb_components_from_rules(struct xkb_context *ctx,
1106                           const struct xkb_rule_names *rmlvo,
1107                           struct xkb_component_names *out)
1108 {
1109     bool ret = false;
1110     FILE *file;
1111     char *path = NULL;
1112     struct matcher *matcher = NULL;
1113     struct matched_sval *mval;
1114     unsigned int offset = 0;
1115 
1116     file = FindFileInXkbPath(ctx, rmlvo->rules, FILE_TYPE_RULES, &path, &offset);
1117     if (!file)
1118         goto err_out;
1119 
1120     matcher = matcher_new(ctx, rmlvo);
1121 
1122     ret = read_rules_file(ctx, matcher, 0, file, path);
1123     if (!ret ||
1124         darray_empty(matcher->kccgst[KCCGST_KEYCODES]) ||
1125         darray_empty(matcher->kccgst[KCCGST_TYPES]) ||
1126         darray_empty(matcher->kccgst[KCCGST_COMPAT]) ||
1127         /* darray_empty(matcher->kccgst[KCCGST_GEOMETRY]) || */
1128         darray_empty(matcher->kccgst[KCCGST_SYMBOLS])) {
1129         log_err(ctx, "No components returned from XKB rules \"%s\"\n", path);
1130         ret = false;
1131         goto err_out;
1132     }
1133 
1134     darray_steal(matcher->kccgst[KCCGST_KEYCODES], &out->keycodes, NULL);
1135     darray_steal(matcher->kccgst[KCCGST_TYPES], &out->types, NULL);
1136     darray_steal(matcher->kccgst[KCCGST_COMPAT], &out->compat, NULL);
1137     darray_steal(matcher->kccgst[KCCGST_SYMBOLS], &out->symbols, NULL);
1138     darray_free(matcher->kccgst[KCCGST_GEOMETRY]);
1139 
1140     mval = &matcher->rmlvo.model;
1141     if (!mval->matched && mval->sval.len > 0)
1142         log_err(matcher->ctx, "Unrecognized RMLVO model \"%.*s\" was ignored\n",
1143                 mval->sval.len, mval->sval.start);
1144     darray_foreach(mval, matcher->rmlvo.layouts)
1145         if (!mval->matched && mval->sval.len > 0)
1146             log_err(matcher->ctx, "Unrecognized RMLVO layout \"%.*s\" was ignored\n",
1147                     mval->sval.len, mval->sval.start);
1148     darray_foreach(mval, matcher->rmlvo.variants)
1149         if (!mval->matched && mval->sval.len > 0)
1150             log_err(matcher->ctx, "Unrecognized RMLVO variant \"%.*s\" was ignored\n",
1151                     mval->sval.len, mval->sval.start);
1152     darray_foreach(mval, matcher->rmlvo.options)
1153         if (!mval->matched && mval->sval.len > 0)
1154             log_err(matcher->ctx, "Unrecognized RMLVO option \"%.*s\" was ignored\n",
1155                     mval->sval.len, mval->sval.start);
1156 
1157 err_out:
1158     if (file)
1159         fclose(file);
1160     matcher_free(matcher);
1161     free(path);
1162     return ret;
1163 }
1164