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
  18  *   key          = key-fragment { '.' key-fragment }
  19  *   key-fragment = / [^=,.]+ /
  20  *   val          = { / [^,]+ / | ',,' }
  21  *
  22  * Semantics defined by reduction to JSON:
  23  *
  24  *   key-vals specifies a JSON object, i.e. a tree whose root is an
  25  *   object, inner nodes other than the root are objects or arrays,
  26  *   and leaves are strings.
  27  *
  28  *   Each key-val = key-fragment '.' ... '=' val specifies a path from
  29  *   root to a leaf (left of '='), and the leaf's value (right of
  30  *   '=').
  31  *
  32  *   A path from the root is defined recursively:
  33  *       L '.' key-fragment is a child of the node denoted by path L
  34  *       key-fragment is a child of the tree root
  35  *   If key-fragment is numeric, the parent is an array and the child
  36  *   is its key-fragment-th member, counting from zero.
  37  *   Else, the parent is an object, and the child is its member named
  38  *   key-fragment.
  39  *
  40  *   This constrains inner nodes to be either array or object.  The
  41  *   constraints must be satisfiable.  Counter-example: a.b=1,a=2 is
  42  *   not, because root.a must be an object to satisfy a.b=1 and a
  43  *   string to satisfy a=2.
  44  *
  45  *   Array subscripts can occur in any order, but the set of
  46  *   subscripts must not have gaps.  For instance, a.1=v is not okay,
  47  *   because root.a[0] is missing.
  48  *
  49  *   If multiple key-val denote the same leaf, the last one determines
  50  *   the value.
  51  *
  52  * Key-fragments must be valid QAPI names or consist only of decimal
  53  * digits.
  54  *
  55  * The length of any key-fragment must be between 1 and 127.
  56  *
  57  * Design flaw: there is no way to denote an empty array or non-root
  58  * object.  While interpreting "key absent" as empty seems natural
  59  * (removing a key-val from the input string removes the member when
  60  * there are more, so why not when it's the last), it doesn't work:
  61  * "key absent" already means "optional object/array absent", which
  62  * isn't the same as "empty object/array present".
  63  *
  64  * Design flaw: scalar values can only be strings; there is no way to
  65  * denote numbers, true, false or null.  The special QObject input
  66  * visitor returned by qobject_input_visitor_new_keyval() mostly hides
  67  * this by automatically converting strings to the type the visitor
  68  * expects.  Breaks down for type 'any', where the visitor's
  69  * expectation isn't clear.  Code visiting 'any' needs to do the
  70  * conversion itself, but only when using this keyval visitor.
  71  * Awkward.  Note that we carefully restrict alternate types to avoid
  72  * similar ambiguity.
  73  *
  74  * Alternative syntax for use with an implied key:
  75  *
  76  *   key-vals     = [ key-val-1st { ',' key-val } [ ',' ] ]
  77  *   key-val-1st  = val-no-key | key-val
  78  *   val-no-key   = / [^=,]+ /
  79  *
  80  * where val-no-key is syntactic sugar for implied-key=val-no-key.
  81  *
  82  * Note that you can't use the sugared form when the value contains
  83  * '=' or ','.
  84  */
  85
  86 #include "qemu/osdep.h"
  87 #include "qapi/error.h"
  88 #include "qapi/qmp/qdict.h"
  89 #include "qapi/qmp/qlist.h"
  90 #include "qapi/qmp/qstring.h"
  91 #include "qemu/cutils.h"
  92 #include "qemu/option.h"
  93
  94 /*
  95  * Convert @key to a list index.
  96  * Convert all leading decimal digits to a (non-negative) number,
  97  * capped at INT_MAX.
  98  * If @end is non-null, assign a pointer to the first character after
  99  * the number to *@end.
 100  * Else, fail if any characters follow.
 101  * On success, return the converted number.
 102  * On failure, return a negative value.
 103  * Note: since only digits are converted, no two keys can map to the
 104  * same number, except by overflow to INT_MAX.
 105  */
 106 static int key_to_index(const char *key, const char **end)
 107 {
 108     int ret;
 109     unsigned long index;
 110
 111     if (*key < '0' || *key > '9') {
 112         return -EINVAL;
 113     }
 114     ret = qemu_strtoul(key, end, 10, &index);
 115     if (ret) {
 116         return ret == -ERANGE ? INT_MAX : ret;
 117     }
 118     return index <= INT_MAX ? index : INT_MAX;
 119 }
 120
 121 /*
 122  * Ensure @cur maps @key_in_cur the right way.
 123  * If @value is null, it needs to map to a QDict, else to this
 124  * QString.
 125  * If @cur doesn't have @key_in_cur, put an empty QDict or @value,
 126  * respectively.
 127  * Else, if it needs to map to a QDict, and already does, do nothing.
 128  * Else, if it needs to map to this QString, and already maps to a
 129  * QString, replace it by @value.
 130  * Else, fail because we have conflicting needs on how to map
 131  * @key_in_cur.
 132  * In any case, take over the reference to @value, i.e. if the caller
 133  * wants to hold on to a reference, it needs to qobject_ref().
 134  * Use @key up to @key_cursor to identify the key in error messages.
 135  * On success, return the mapped value.
 136  * On failure, store an error through @errp and return NULL.
 137  */
 138 static QObject *keyval_parse_put(QDict *cur,
 139                                  const char *key_in_cur, QString *value,
 140                                  const char *key, const char *key_cursor,
 141                                  Error **errp)
 142 {
 143     QObject *old, *new;
 144
 145     old = qdict_get(cur, key_in_cur);
 146     if (old) {
 147         if (qobject_type(old) != (value ? QTYPE_QSTRING : QTYPE_QDICT)) {
 148             error_setg(errp, "Parameters '%.*s.*' used inconsistently",
 149                        (int)(key_cursor - key), key);
 150             qobject_unref(value);
 151             return NULL;
 152         }
 153         if (!value) {
 154             return old;         /* already QDict, do nothing */
 155         }
 156         new = QOBJECT(value);   /* replacement */
 157     } else {
 158         new = value ? QOBJECT(value) : QOBJECT(qdict_new());
 159     }
 160     qdict_put_obj(cur, key_in_cur, new);
 161     return new;
 162 }
 163
 164 /*
 165  * Parse one KEY=VALUE from @params, store result in @qdict.
 166  * The first fragment of KEY applies to @qdict.  Subsequent fragments
 167  * apply to nested QDicts, which are created on demand.  @implied_key
 168  * is as in keyval_parse().
 169  * On success, return a pointer to the next KEY=VALUE, or else to '\0'.
 170  * On failure, return NULL.
 171  */
 172 static const char *keyval_parse_one(QDict *qdict, const char *params,
 173                                     const char *implied_key,
 174                                     Error **errp)
 175 {
 176     const char *key, *key_end, *s, *end;
 177     size_t len;
 178     char key_in_cur[128];
 179     QDict *cur;
 180     int ret;
 181     QObject *next;
 182     QString *val;
 183
 184     key = params;
 185     len = strcspn(params, "=,");
 186     if (implied_key && len && key[len] != '=') {
 187         /* Desugar implied key */
 188         key = implied_key;
 189         len = strlen(implied_key);
 190     }
 191     key_end = key + len;
 192
 193     /*
 194      * Loop over key fragments: @s points to current fragment, it
 195      * applies to @cur.  @key_in_cur[] holds the previous fragment.
 196      */
 197     cur = qdict;
 198     s = key;
 199     for (;;) {
 200         /* Want a key index (unless it's first) or a QAPI name */
 201         if (s != key && key_to_index(s, &end) >= 0) {
 202             len = end - s;
 203         } else {
 204             ret = parse_qapi_name(s, false);
 205             len = ret < 0 ? 0 : ret;
 206         }
 207         assert(s + len <= key_end);
 208         if (!len || (s + len < key_end && s[len] != '.')) {
 209             assert(key != implied_key);
 210             error_setg(errp, "Invalid parameter '%.*s'",
 211                        (int)(key_end - key), key);
 212             return NULL;
 213         }
 214         if (len >= sizeof(key_in_cur)) {
 215             assert(key != implied_key);
 216             error_setg(errp, "Parameter%s '%.*s' is too long",
 217                        s != key || s + len != key_end ? " fragment" : "",
 218                        (int)len, s);
 219             return NULL;
 220         }
 221
 222         if (s != key) {
 223             next = keyval_parse_put(cur, key_in_cur, NULL,
 224                                     key, s - 1, errp);
 225             if (!next) {
 226                 return NULL;
 227             }
 228             cur = qobject_to(QDict, next);
 229             assert(cur);
 230         }
 231
 232         memcpy(key_in_cur, s, len);
 233         key_in_cur[len] = 0;
 234         s += len;
 235
 236         if (*s != '.') {
 237             break;
 238         }
 239         s++;
 240     }
 241
 242     if (key == implied_key) {
 243         assert(!*s);
 244         s = params;
 245     } else {
 246         if (*s != '=') {
 247             error_setg(errp, "Expected '=' after parameter '%.*s'",
 248                        (int)(s - key), key);
 249             return NULL;
 250         }
 251         s++;
 252     }
 253
 254     val = qstring_new();
 255     for (;;) {
 256         if (!*s) {
 257             break;
 258         } else if (*s == ',') {
 259             s++;
 260             if (*s != ',') {
 261                 break;
 262             }
 263         }
 264         qstring_append_chr(val, *s++);
 265     }
 266
 267     if (!keyval_parse_put(cur, key_in_cur, val, key, key_end, errp)) {
 268         return NULL;
 269     }
 270     return s;
 271 }
 272
 273 static char *reassemble_key(GSList *key)
 274 {
 275     GString *s = g_string_new("");
 276     GSList *p;
 277
 278     for (p = key; p; p = p->next) {
 279         g_string_prepend_c(s, '.');
 280         g_string_prepend(s, (char *)p->data);
 281     }
 282
 283     return g_string_free(s, FALSE);
 284 }
 285
 286 /*
 287  * Listify @cur recursively.
 288  * Replace QDicts whose keys are all valid list indexes by QLists.
 289  * @key_of_cur is the list of key fragments leading up to @cur.
 290  * On success, return either @cur or its replacement.
 291  * On failure, store an error through @errp and return NULL.
 292  */
 293 static QObject *keyval_listify(QDict *cur, GSList *key_of_cur, Error **errp)
 294 {
 295     GSList key_node;
 296     bool has_index, has_member;
 297     const QDictEntry *ent;
 298     QDict *qdict;
 299     QObject *val;
 300     char *key;
 301     size_t nelt;
 302     QObject **elt;
 303     int index, max_index, i;
 304     QList *list;
 305
 306     key_node.next = key_of_cur;
 307
 308     /*
 309      * Recursively listify @cur's members, and figure out whether @cur
 310      * itself is to be listified.
 311      */
 312     has_index = false;
 313     has_member = false;
 314     for (ent = qdict_first(cur); ent; ent = qdict_next(cur, ent)) {
 315         if (key_to_index(ent->key, NULL) >= 0) {
 316             has_index = true;
 317         } else {
 318             has_member = true;
 319         }
 320
 321         qdict = qobject_to(QDict, ent->value);
 322         if (!qdict) {
 323             continue;
 324         }
 325
 326         key_node.data = ent->key;
 327         val = keyval_listify(qdict, &key_node, errp);
 328         if (!val) {
 329             return NULL;
 330         }
 331         if (val != ent->value) {
 332             qdict_put_obj(cur, ent->key, val);
 333         }
 334     }
 335
 336     if (has_index && has_member) {
 337         key = reassemble_key(key_of_cur);
 338         error_setg(errp, "Parameters '%s*' used inconsistently", key);
 339         g_free(key);
 340         return NULL;
 341     }
 342     if (!has_index) {
 343         return QOBJECT(cur);
 344     }
 345
 346     /* Copy @cur's values to @elt[] */
 347     nelt = qdict_size(cur) + 1; /* one extra, for use as sentinel */
 348     elt = g_new0(QObject *, nelt);
 349     max_index = -1;
 350     for (ent = qdict_first(cur); ent; ent = qdict_next(cur, ent)) {
 351         index = key_to_index(ent->key, NULL);
 352         assert(index >= 0);
 353         if (index > max_index) {
 354             max_index = index;
 355         }
 356         /*
 357          * We iterate @nelt times.  If we get one exceeding @nelt
 358          * here, we will put less than @nelt values into @elt[],
 359          * triggering the error in the next loop.
 360          */
 361         if ((size_t)index >= nelt - 1) {
 362             continue;
 363         }
 364         /* Even though dict keys are distinct, indexes need not be */
 365         elt[index] = ent->value;
 366     }
 367
 368     /*
 369      * Make a list from @elt[], reporting the first missing element,
 370      * if any.
 371      * If we dropped an index >= nelt in the previous loop, this loop
 372      * will run into the sentinel and report index @nelt missing.
 373      */
 374     list = qlist_new();
 375     assert(!elt[nelt-1]);       /* need the sentinel to be null */
 376     for (i = 0; i < MIN(nelt, max_index + 1); i++) {
 377         if (!elt[i]) {
 378             key = reassemble_key(key_of_cur);
 379             error_setg(errp, "Parameter '%s%d' missing", key, i);
 380             g_free(key);
 381             g_free(elt);
 382             qobject_unref(list);
 383             return NULL;
 384         }
 385         qobject_ref(elt[i]);
 386         qlist_append_obj(list, elt[i]);
 387     }
 388
 389     g_free(elt);
 390     return QOBJECT(list);
 391 }
 392
 393 /*
 394  * Parse @params in QEMU's traditional KEY=VALUE,... syntax.
 395  * If @implied_key, the first KEY= can be omitted.  @implied_key is
 396  * implied then, and VALUE can't be empty or contain ',' or '='.
 397  * On success, return a dictionary of the parsed keys and values.
 398  * On failure, store an error through @errp and return NULL.
 399  */
 400 QDict *keyval_parse(const char *params, const char *implied_key,
 401                     Error **errp)
 402 {
 403     QDict *qdict = qdict_new();
 404     QObject *listified;
 405     const char *s;
 406
 407     s = params;
 408     while (*s) {
 409         s = keyval_parse_one(qdict, s, implied_key, errp);
 410         if (!s) {
 411             qobject_unref(qdict);
 412             return NULL;
 413         }
 414         implied_key = NULL;
 415     }
 416
 417     listified = keyval_listify(qdict, NULL, errp);
 418     if (!listified) {
 419         qobject_unref(qdict);
 420         return NULL;
 421     }
 422     assert(listified == QOBJECT(qdict));
 423     return qdict;
 424 }