xref: /openbmc/qemu/util/keyval.c (revision ed75658a)
1 /*
2  * Parsing KEY=VALUE,... strings
3  *
4  * Copyright (C) 2017 Red Hat Inc.
5  *
6  * Authors:
7  *  Markus Armbruster <armbru@redhat.com>,
8  *
9  * This work is licensed under the terms of the GNU GPL, version 2 or later.
10  * See the COPYING file in the top-level directory.
11  */
12 
13 /*
14  * KEY=VALUE,... syntax:
15  *
16  *   key-vals     = [ key-val { ',' key-val } [ ',' ] ]
17  *   key-val      = key '=' val | help
18  *   key          = key-fragment { '.' key-fragment }
19  *   key-fragment = qapi-name | index
20  *   qapi-name    = '__' / [a-z0-9.-]+ / '_' / [A-Za-z][A-Za-z0-9_-]* /
21  *   index        = / [0-9]+ /
22  *   val          = { / [^,]+ / | ',,' }
23  *   help         = 'help' | '?'
24  *
25  * Semantics defined by reduction to JSON:
26  *
27  *   key-vals specifies a JSON object, i.e. a tree whose root is an
28  *   object, inner nodes other than the root are objects or arrays,
29  *   and leaves are strings.
30  *
31  *   Each key-val = key-fragment '.' ... '=' val specifies a path from
32  *   root to a leaf (left of '='), and the leaf's value (right of
33  *   '=').
34  *
35  *   A path from the root is defined recursively:
36  *       L '.' key-fragment is a child of the node denoted by path L
37  *       key-fragment is a child of the tree root
38  *   If key-fragment is numeric, the parent is an array and the child
39  *   is its key-fragment-th member, counting from zero.
40  *   Else, the parent is an object, and the child is its member named
41  *   key-fragment.
42  *
43  *   This constrains inner nodes to be either array or object.  The
44  *   constraints must be satisfiable.  Counter-example: a.b=1,a=2 is
45  *   not, because root.a must be an object to satisfy a.b=1 and a
46  *   string to satisfy a=2.
47  *
48  *   Array subscripts can occur in any order, but the set of
49  *   subscripts must not have gaps.  For instance, a.1=v is not okay,
50  *   because root.a[0] is missing.
51  *
52  *   If multiple key-val denote the same leaf, the last one determines
53  *   the value.
54  *
55  * Key-fragments must be valid QAPI names or consist only of decimal
56  * digits.
57  *
58  * The length of any key-fragment must be between 1 and 127.
59  *
60  * If any key-val is help, the object is to be treated as a help
61  * request.
62  *
63  * Design flaw: there is no way to denote an empty array or non-root
64  * object.  While interpreting "key absent" as empty seems natural
65  * (removing a key-val from the input string removes the member when
66  * there are more, so why not when it's the last), it doesn't work:
67  * "key absent" already means "optional object/array absent", which
68  * isn't the same as "empty object/array present".
69  *
70  * Design flaw: scalar values can only be strings; there is no way to
71  * denote numbers, true, false or null.  The special QObject input
72  * visitor returned by qobject_input_visitor_new_keyval() mostly hides
73  * this by automatically converting strings to the type the visitor
74  * expects.  Breaks down for type 'any', where the visitor's
75  * expectation isn't clear.  Code visiting 'any' needs to do the
76  * conversion itself, but only when using this keyval visitor.
77  * Awkward.  Note that we carefully restrict alternate types to avoid
78  * similar ambiguity.
79  *
80  * Alternative syntax for use with an implied key:
81  *
82  *   key-vals     = [ key-val-1st { ',' key-val } [ ',' ] ]
83  *   key-val-1st  = val-no-key | key-val
84  *   val-no-key   = / [^=,]+ / - help
85  *
86  * where val-no-key is syntactic sugar for implied-key=val-no-key.
87  *
88  * Note that you can't use the sugared form when the value contains
89  * '=' or ','.
90  */
91 
92 #include "qemu/osdep.h"
93 #include "qapi/error.h"
94 #include "qapi/qmp/qdict.h"
95 #include "qapi/qmp/qlist.h"
96 #include "qapi/qmp/qstring.h"
97 #include "qemu/cutils.h"
98 #include "qemu/keyval.h"
99 #include "qemu/help_option.h"
100 
101 /*
102  * Convert @key to a list index.
103  * Convert all leading decimal digits to a (non-negative) number,
104  * capped at INT_MAX.
105  * If @end is non-null, assign a pointer to the first character after
106  * the number to *@end.
107  * Else, fail if any characters follow.
108  * On success, return the converted number.
109  * On failure, return a negative value.
110  * Note: since only digits are converted, no two keys can map to the
111  * same number, except by overflow to INT_MAX.
112  */
113 static int key_to_index(const char *key, const char **end)
114 {
115     int ret;
116     unsigned long index;
117 
118     if (*key < '0' || *key > '9') {
119         return -EINVAL;
120     }
121     ret = qemu_strtoul(key, end, 10, &index);
122     if (ret) {
123         return ret == -ERANGE ? INT_MAX : ret;
124     }
125     return index <= INT_MAX ? index : INT_MAX;
126 }
127 
128 /*
129  * Ensure @cur maps @key_in_cur the right way.
130  * If @value is null, it needs to map to a QDict, else to this
131  * QString.
132  * If @cur doesn't have @key_in_cur, put an empty QDict or @value,
133  * respectively.
134  * Else, if it needs to map to a QDict, and already does, do nothing.
135  * Else, if it needs to map to this QString, and already maps to a
136  * QString, replace it by @value.
137  * Else, fail because we have conflicting needs on how to map
138  * @key_in_cur.
139  * In any case, take over the reference to @value, i.e. if the caller
140  * wants to hold on to a reference, it needs to qobject_ref().
141  * Use @key up to @key_cursor to identify the key in error messages.
142  * On success, return the mapped value.
143  * On failure, store an error through @errp and return NULL.
144  */
145 static QObject *keyval_parse_put(QDict *cur,
146                                  const char *key_in_cur, QString *value,
147                                  const char *key, const char *key_cursor,
148                                  Error **errp)
149 {
150     QObject *old, *new;
151 
152     old = qdict_get(cur, key_in_cur);
153     if (old) {
154         if (qobject_type(old) != (value ? QTYPE_QSTRING : QTYPE_QDICT)) {
155             error_setg(errp, "Parameters '%.*s.*' used inconsistently",
156                        (int)(key_cursor - key), key);
157             qobject_unref(value);
158             return NULL;
159         }
160         if (!value) {
161             return old;         /* already QDict, do nothing */
162         }
163         new = QOBJECT(value);   /* replacement */
164     } else {
165         new = value ? QOBJECT(value) : QOBJECT(qdict_new());
166     }
167     qdict_put_obj(cur, key_in_cur, new);
168     return new;
169 }
170 
171 /*
172  * Parse one parameter from @params.
173  *
174  * If we're looking at KEY=VALUE, store result in @qdict.
175  * The first fragment of KEY applies to @qdict.  Subsequent fragments
176  * apply to nested QDicts, which are created on demand.  @implied_key
177  * is as in keyval_parse().
178  *
179  * If we're looking at "help" or "?", set *help to true.
180  *
181  * On success, return a pointer to the next parameter, or else to '\0'.
182  * On failure, return NULL.
183  */
184 static const char *keyval_parse_one(QDict *qdict, const char *params,
185                                     const char *implied_key, bool *help,
186                                     Error **errp)
187 {
188     const char *key, *key_end, *val_end, *s, *end;
189     size_t len;
190     char key_in_cur[128];
191     QDict *cur;
192     int ret;
193     QObject *next;
194     GString *val;
195 
196     key = params;
197     val_end = NULL;
198     len = strcspn(params, "=,");
199     if (len && key[len] != '=') {
200         if (starts_with_help_option(key) == len) {
201             *help = true;
202             s = key + len;
203             if (*s == ',') {
204                 s++;
205             }
206             return s;
207         }
208         if (implied_key) {
209             /* Desugar implied key */
210             key = implied_key;
211             val_end = params + len;
212             len = strlen(implied_key);
213         }
214     }
215     key_end = key + len;
216 
217     /*
218      * Loop over key fragments: @s points to current fragment, it
219      * applies to @cur.  @key_in_cur[] holds the previous fragment.
220      */
221     cur = qdict;
222     s = key;
223     for (;;) {
224         /* Want a key index (unless it's first) or a QAPI name */
225         if (s != key && key_to_index(s, &end) >= 0) {
226             len = end - s;
227         } else {
228             ret = parse_qapi_name(s, false);
229             len = ret < 0 ? 0 : ret;
230         }
231         assert(s + len <= key_end);
232         if (!len || (s + len < key_end && s[len] != '.')) {
233             assert(key != implied_key);
234             error_setg(errp, "Invalid parameter '%.*s'",
235                        (int)(key_end - key), key);
236             return NULL;
237         }
238         if (len >= sizeof(key_in_cur)) {
239             assert(key != implied_key);
240             error_setg(errp, "Parameter%s '%.*s' is too long",
241                        s != key || s + len != key_end ? " fragment" : "",
242                        (int)len, s);
243             return NULL;
244         }
245 
246         if (s != key) {
247             next = keyval_parse_put(cur, key_in_cur, NULL,
248                                     key, s - 1, errp);
249             if (!next) {
250                 return NULL;
251             }
252             cur = qobject_to(QDict, next);
253             assert(cur);
254         }
255 
256         memcpy(key_in_cur, s, len);
257         key_in_cur[len] = 0;
258         s += len;
259 
260         if (*s != '.') {
261             break;
262         }
263         s++;
264     }
265 
266     if (key == implied_key) {
267         assert(!*s);
268         val = g_string_new_len(params, val_end - params);
269         s = val_end;
270         if (*s == ',') {
271             s++;
272         }
273     } else {
274         if (*s != '=') {
275             error_setg(errp, "Expected '=' after parameter '%.*s'",
276                        (int)(s - key), key);
277             return NULL;
278         }
279         s++;
280 
281         val = g_string_new(NULL);
282         for (;;) {
283             if (!*s) {
284                 break;
285             } else if (*s == ',') {
286                 s++;
287                 if (*s != ',') {
288                     break;
289                 }
290             }
291             g_string_append_c(val, *s++);
292         }
293     }
294 
295     if (!keyval_parse_put(cur, key_in_cur, qstring_from_gstring(val),
296                           key, key_end, errp)) {
297         return NULL;
298     }
299     return s;
300 }
301 
302 static char *reassemble_key(GSList *key)
303 {
304     GString *s = g_string_new("");
305     GSList *p;
306 
307     for (p = key; p; p = p->next) {
308         g_string_prepend_c(s, '.');
309         g_string_prepend(s, (char *)p->data);
310     }
311 
312     return g_string_free(s, FALSE);
313 }
314 
315 /*
316  * Recursive worker for keyval_merge.
317  *
318  * @str is the path that led to the * current dictionary (to be used for
319  * error messages).  It is modified internally but restored before the
320  * function returns.
321  */
322 static void keyval_do_merge(QDict *dest, const QDict *merged, GString *str, Error **errp)
323 {
324     size_t save_len = str->len;
325     const QDictEntry *ent;
326     QObject *old_value;
327 
328     for (ent = qdict_first(merged); ent; ent = qdict_next(merged, ent)) {
329         old_value = qdict_get(dest, ent->key);
330         if (old_value) {
331             if (qobject_type(old_value) != qobject_type(ent->value)) {
332                 error_setg(errp, "Parameter '%s%s' used inconsistently",
333                            str->str, ent->key);
334                 return;
335             } else if (qobject_type(ent->value) == QTYPE_QDICT) {
336                 /* Merge sub-dictionaries.  */
337                 g_string_append(str, ent->key);
338                 g_string_append_c(str, '.');
339                 keyval_do_merge(qobject_to(QDict, old_value),
340                                 qobject_to(QDict, ent->value),
341                                 str, errp);
342                 g_string_truncate(str, save_len);
343                 continue;
344             } else if (qobject_type(ent->value) == QTYPE_QLIST) {
345                 /* Append to old list.  */
346                 QList *old = qobject_to(QList, old_value);
347                 QList *new = qobject_to(QList, ent->value);
348                 const QListEntry *item;
349                 QLIST_FOREACH_ENTRY(new, item) {
350                     qobject_ref(item->value);
351                     qlist_append_obj(old, item->value);
352                 }
353                 continue;
354             } else {
355                 assert(qobject_type(ent->value) == QTYPE_QSTRING);
356             }
357         }
358 
359         qobject_ref(ent->value);
360         qdict_put_obj(dest, ent->key, ent->value);
361     }
362 }
363 
364 /* Merge the @merged dictionary into @dest.
365  *
366  * The dictionaries are expected to be returned by the keyval parser, and
367  * therefore the only expected scalar type is the string.  In case the same
368  * path is present in both @dest and @merged, the semantics are as follows:
369  *
370  * - lists are concatenated
371  *
372  * - dictionaries are merged recursively
373  *
374  * - for scalar values, @merged wins
375  *
376  * In case an error is reported, @dest may already have been modified.
377  *
378  * This function can be used to implement semantics analogous to QemuOpts's
379  * .merge_lists = true case, or to implement -set for options backed by QDicts.
380  *
381  * Note: while QemuOpts is commonly used so that repeated keys overwrite
382  * ("last one wins"), it can also be used so that repeated keys build up
383  * a list. keyval_merge() can only be used when the options' semantics are
384  * the former, not the latter.
385  */
386 void keyval_merge(QDict *dest, const QDict *merged, Error **errp)
387 {
388     GString *str;
389 
390     str = g_string_new("");
391     keyval_do_merge(dest, merged, str, errp);
392     g_string_free(str, TRUE);
393 }
394 
395 /*
396  * Listify @cur recursively.
397  * Replace QDicts whose keys are all valid list indexes by QLists.
398  * @key_of_cur is the list of key fragments leading up to @cur.
399  * On success, return either @cur or its replacement.
400  * On failure, store an error through @errp and return NULL.
401  */
402 static QObject *keyval_listify(QDict *cur, GSList *key_of_cur, Error **errp)
403 {
404     GSList key_node;
405     bool has_index, has_member;
406     const QDictEntry *ent;
407     QDict *qdict;
408     QObject *val;
409     char *key;
410     size_t nelt;
411     QObject **elt;
412     int index, max_index, i;
413     QList *list;
414 
415     key_node.next = key_of_cur;
416 
417     /*
418      * Recursively listify @cur's members, and figure out whether @cur
419      * itself is to be listified.
420      */
421     has_index = false;
422     has_member = false;
423     for (ent = qdict_first(cur); ent; ent = qdict_next(cur, ent)) {
424         if (key_to_index(ent->key, NULL) >= 0) {
425             has_index = true;
426         } else {
427             has_member = true;
428         }
429 
430         qdict = qobject_to(QDict, ent->value);
431         if (!qdict) {
432             continue;
433         }
434 
435         key_node.data = ent->key;
436         val = keyval_listify(qdict, &key_node, errp);
437         if (!val) {
438             return NULL;
439         }
440         if (val != ent->value) {
441             qdict_put_obj(cur, ent->key, val);
442         }
443     }
444 
445     if (has_index && has_member) {
446         key = reassemble_key(key_of_cur);
447         error_setg(errp, "Parameters '%s*' used inconsistently", key);
448         g_free(key);
449         return NULL;
450     }
451     if (!has_index) {
452         return QOBJECT(cur);
453     }
454 
455     /* Copy @cur's values to @elt[] */
456     nelt = qdict_size(cur) + 1; /* one extra, for use as sentinel */
457     elt = g_new0(QObject *, nelt);
458     max_index = -1;
459     for (ent = qdict_first(cur); ent; ent = qdict_next(cur, ent)) {
460         index = key_to_index(ent->key, NULL);
461         assert(index >= 0);
462         if (index > max_index) {
463             max_index = index;
464         }
465         /*
466          * We iterate @nelt times.  If we get one exceeding @nelt
467          * here, we will put less than @nelt values into @elt[],
468          * triggering the error in the next loop.
469          */
470         if ((size_t)index >= nelt - 1) {
471             continue;
472         }
473         /* Even though dict keys are distinct, indexes need not be */
474         elt[index] = ent->value;
475     }
476 
477     /*
478      * Make a list from @elt[], reporting the first missing element,
479      * if any.
480      * If we dropped an index >= nelt in the previous loop, this loop
481      * will run into the sentinel and report index @nelt missing.
482      */
483     list = qlist_new();
484     assert(!elt[nelt-1]);       /* need the sentinel to be null */
485     for (i = 0; i < MIN(nelt, max_index + 1); i++) {
486         if (!elt[i]) {
487             key = reassemble_key(key_of_cur);
488             error_setg(errp, "Parameter '%s%d' missing", key, i);
489             g_free(key);
490             g_free(elt);
491             qobject_unref(list);
492             return NULL;
493         }
494         qobject_ref(elt[i]);
495         qlist_append_obj(list, elt[i]);
496     }
497 
498     g_free(elt);
499     return QOBJECT(list);
500 }
501 
502 /*
503  * Parse @params in QEMU's traditional KEY=VALUE,... syntax.
504  *
505  * If @implied_key, the first KEY= can be omitted.  @implied_key is
506  * implied then, and VALUE can't be empty or contain ',' or '='.
507  *
508  * A parameter "help" or "?" without a value isn't added to the
509  * resulting dictionary, but instead is interpreted as help request.
510  * All other options are parsed and returned normally so that context
511  * specific help can be printed.
512  *
513  * If @p_help is not NULL, store whether help is requested there.
514  * If @p_help is NULL and help is requested, fail.
515  *
516  * On success, return @dict, now filled with the parsed keys and values.
517  *
518  * On failure, store an error through @errp and return NULL.  Any keys
519  * and values parsed so far will be in @dict nevertheless.
520  */
521 QDict *keyval_parse_into(QDict *qdict, const char *params, const char *implied_key,
522                          bool *p_help, Error **errp)
523 {
524     QObject *listified;
525     const char *s;
526     bool help = false;
527 
528     s = params;
529     while (*s) {
530         s = keyval_parse_one(qdict, s, implied_key, &help, errp);
531         if (!s) {
532             return NULL;
533         }
534         implied_key = NULL;
535     }
536 
537     if (p_help) {
538         *p_help = help;
539     } else if (help) {
540         error_setg(errp, "Help is not available for this option");
541         return NULL;
542     }
543 
544     listified = keyval_listify(qdict, NULL, errp);
545     if (!listified) {
546         return NULL;
547     }
548     assert(listified == QOBJECT(qdict));
549     return qdict;
550 }
551 
552 /*
553  * Parse @params in QEMU's traditional KEY=VALUE,... syntax.
554  *
555  * If @implied_key, the first KEY= can be omitted.  @implied_key is
556  * implied then, and VALUE can't be empty or contain ',' or '='.
557  *
558  * A parameter "help" or "?" without a value isn't added to the
559  * resulting dictionary, but instead is interpreted as help request.
560  * All other options are parsed and returned normally so that context
561  * specific help can be printed.
562  *
563  * If @p_help is not NULL, store whether help is requested there.
564  * If @p_help is NULL and help is requested, fail.
565  *
566  * On success, return a dictionary of the parsed keys and values.
567  * On failure, store an error through @errp and return NULL.
568  */
569 QDict *keyval_parse(const char *params, const char *implied_key,
570                     bool *p_help, Error **errp)
571 {
572     QDict *qdict = qdict_new();
573     QDict *ret = keyval_parse_into(qdict, params, implied_key, p_help, errp);
574 
575     if (!ret) {
576         qobject_unref(qdict);
577     }
578     return ret;
579 }
580