qemu

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