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 | */ |
102 | static 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 | */ |
134 | static 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 | */ |
168 | static 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 | |
269 | static 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 | */ |
289 | static 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 | */ |
396 | QDict *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 | |