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