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