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/help_option.h" 99 #include "qemu/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