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