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