util/keyval.c

   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  * Listify @cur recursively.
 315  * Replace QDicts whose keys are all valid list indexes by QLists.
 316  * @key_of_cur is the list of key fragments leading up to @cur.
 317  * On success, return either @cur or its replacement.
 318  * On failure, store an error through @errp and return NULL.
 319  */
 320 static QObject *keyval_listify(QDict *cur, GSList *key_of_cur, Error **errp)
 321 {
 322     GSList key_node;
 323     bool has_index, has_member;
 324     const QDictEntry *ent;
 325     QDict *qdict;
 326     QObject *val;
 327     char *key;
 328     size_t nelt;
 329     QObject **elt;
 330     int index, max_index, i;
 331     QList *list;
 332
 333     key_node.next = key_of_cur;
 334
 335     /*
 336      * Recursively listify @cur's members, and figure out whether @cur
 337      * itself is to be listified.
 338      */
 339     has_index = false;
 340     has_member = false;
 341     for (ent = qdict_first(cur); ent; ent = qdict_next(cur, ent)) {
 342         if (key_to_index(ent->key, NULL) >= 0) {
 343             has_index = true;
 344         } else {
 345             has_member = true;
 346         }
 347
 348         qdict = qobject_to(QDict, ent->value);
 349         if (!qdict) {
 350             continue;
 351         }
 352
 353         key_node.data = ent->key;
 354         val = keyval_listify(qdict, &key_node, errp);
 355         if (!val) {
 356             return NULL;
 357         }
 358         if (val != ent->value) {
 359             qdict_put_obj(cur, ent->key, val);
 360         }
 361     }
 362
 363     if (has_index && has_member) {
 364         key = reassemble_key(key_of_cur);
 365         error_setg(errp, "Parameters '%s*' used inconsistently", key);
 366         g_free(key);
 367         return NULL;
 368     }
 369     if (!has_index) {
 370         return QOBJECT(cur);
 371     }
 372
 373     /* Copy @cur's values to @elt[] */
 374     nelt = qdict_size(cur) + 1; /* one extra, for use as sentinel */
 375     elt = g_new0(QObject *, nelt);
 376     max_index = -1;
 377     for (ent = qdict_first(cur); ent; ent = qdict_next(cur, ent)) {
 378         index = key_to_index(ent->key, NULL);
 379         assert(index >= 0);
 380         if (index > max_index) {
 381             max_index = index;
 382         }
 383         /*
 384          * We iterate @nelt times.  If we get one exceeding @nelt
 385          * here, we will put less than @nelt values into @elt[],
 386          * triggering the error in the next loop.
 387          */
 388         if ((size_t)index >= nelt - 1) {
 389             continue;
 390         }
 391         /* Even though dict keys are distinct, indexes need not be */
 392         elt[index] = ent->value;
 393     }
 394
 395     /*
 396      * Make a list from @elt[], reporting the first missing element,
 397      * if any.
 398      * If we dropped an index >= nelt in the previous loop, this loop
 399      * will run into the sentinel and report index @nelt missing.
 400      */
 401     list = qlist_new();
 402     assert(!elt[nelt-1]);       /* need the sentinel to be null */
 403     for (i = 0; i < MIN(nelt, max_index + 1); i++) {
 404         if (!elt[i]) {
 405             key = reassemble_key(key_of_cur);
 406             error_setg(errp, "Parameter '%s%d' missing", key, i);
 407             g_free(key);
 408             g_free(elt);
 409             qobject_unref(list);
 410             return NULL;
 411         }
 412         qobject_ref(elt[i]);
 413         qlist_append_obj(list, elt[i]);
 414     }
 415
 416     g_free(elt);
 417     return QOBJECT(list);
 418 }
 419
 420 /*
 421  * Parse @params in QEMU's traditional KEY=VALUE,... syntax.
 422  *
 423  * If @implied_key, the first KEY= can be omitted.  @implied_key is
 424  * implied then, and VALUE can't be empty or contain ',' or '='.
 425  *
 426  * A parameter "help" or "?" without a value isn't added to the
 427  * resulting dictionary, but instead is interpreted as help request.
 428  * All other options are parsed and returned normally so that context
 429  * specific help can be printed.
 430  *
 431  * If @p_help is not NULL, store whether help is requested there.
 432  * If @p_help is NULL and help is requested, fail.
 433  *
 434  * On success, return a dictionary of the parsed keys and values.
 435  * On failure, store an error through @errp and return NULL.
 436  */
 437 QDict *keyval_parse(const char *params, const char *implied_key,
 438                     bool *p_help, Error **errp)
 439 {
 440     QDict *qdict = qdict_new();
 441     QObject *listified;
 442     const char *s;
 443     bool help = false;
 444
 445     s = params;
 446     while (*s) {
 447         s = keyval_parse_one(qdict, s, implied_key, &help, errp);
 448         if (!s) {
 449             qobject_unref(qdict);
 450             return NULL;
 451         }
 452         implied_key = NULL;
 453     }
 454
 455     if (p_help) {
 456         *p_help = help;
 457     } else if (help) {
 458         error_setg(errp, "Help is not available for this option");
 459         qobject_unref(qdict);
 460         return NULL;
 461     }
 462
 463     listified = keyval_listify(qdict, NULL, errp);
 464     if (!listified) {
 465         qobject_unref(qdict);
 466         return NULL;
 467     }
 468     assert(listified == QOBJECT(qdict));
 469     return qdict;
 470 }