| Message ID | 1473088600-17930-2-git-send-email-berrange@redhat.com |
|---|---|
| State | New |
| Headers | show |
Am 05.09.2016 um 17:16 hat Daniel P. Berrange geschrieben: > The qdict_flatten() method will take a dict whose elements are > further nested dicts/lists and flatten them by concatenating > keys. > > The qdict_crumple() method aims to do the reverse, taking a flat > qdict, and turning it into a set of nested dicts/lists. It will > apply nesting based on the key name, with a '.' indicating a > new level in the hierarchy. If the keys in the nested structure > are all numeric, it will create a list, otherwise it will create > a dict. > > If the keys are a mixture of numeric and non-numeric, or the > numeric keys are not in strictly ascending order, an error will > be reported. > [...] > +static void qdict_split_flat_key(const char *key, char **prefix, > + const char **suffix) > +{ > + const char *separator; > + size_t i, j; > + > + /* Find first '.' separator, but if there is a pair '..' > + * that acts as an escape, so skip over '..' */ > + separator = NULL; > + do { > + if (separator) { > + separator += 2; > + } else { > + separator = key; > + } > + separator = strchr(separator, '.'); > + } while (separator && separator[1] == '.'); > + > + if (separator) { > + *prefix = g_strndup(key, > + separator - key); This fits in a single line. > + *suffix = separator + 1; > + } else { > + *prefix = g_strdup(key); > + *suffix = NULL; > + } > + > + /* Unescape the '..' sequence into '.' */ > + for (i = 0, j = 0; (*prefix)[i] != '\0'; i++, j++) { > + if ((*prefix)[i] == '.') { > + assert((*prefix)[i + 1] == '.'); > + i++; > + } > + (*prefix)[j] = (*prefix)[i]; > + } > + (*prefix)[j] = '\0'; > +} > + > + > +/** > + * qdict_is_list: > + * @maybe_list: dict to check if keys represent list elements. > + * > + * Determine whether all keys in @maybe_list are valid list elements. > + * If @maybe_list is non-zero in length and all the keys look like > + * valid list indexes, this will return 1. If @maybe_list is zero > + * length or all keys are non-numeric then it will return 0 to indicate > + * it is a normal qdict. If there is a mix of numeric and non-numeric > + * keys, or the list indexes are non-contiguous, an error is reported. > + * > + * Returns: 1 if a valid list, 0 if a dict, -1 on error > + */ > +static int qdict_is_list(QDict *maybe_list, Error **errp) > +{ > + const QDictEntry *ent; > + ssize_t len = 0; > + ssize_t max = -1; > + int is_list = -1; > + int64_t val; > + > + for (ent = qdict_first(maybe_list); ent != NULL; > + ent = qdict_next(maybe_list, ent)) { > + > + if (qemu_strtoll(ent->key, NULL, 10, &val) == 0) { > + if (is_list == -1) { > + is_list = 1; > + } else if (!is_list) { > + error_setg(errp, > + "Cannot crumple a dictionary with a mix of list " > + "and non-list keys"); This is a message that users will see if they pass a bad command line option. I don't think they will understand what it means to "crumple a dictionary" or that they tried to do this. Maybe simply "Cannot mix list and non-list keys"? > + return -1; > + } > + len++; > + if (val > max) { > + max = val; > + } > + } else { > + if (is_list == -1) { > + is_list = 0; > + } else if (is_list) { > + error_setg(errp, > + "Cannot crumple a dictionary with a mix of list " > + "and non-list keys"); Same here. > + return -1; > + } > + } > + } > + > + if (is_list == -1) { > + assert(!qdict_size(maybe_list)); > + is_list = 0; > + } > + > + if (len != (max + 1)) { > + error_setg(errp, "List indexes are not contiguous, " > + "saw %zd elements but %zd largest index", > + len, max); > + return -1; > + } I don't think this is catching everything that isn't contiguous, but I'm not sure whether we care. One reason is that you accept negative indexes above, the other one is that the keys are strings, so I could pass "1", "+1", "01" and "3" and it would be accepted. It's probably reasonable enough to say that in such cases you get what you get, and if future versions behave differently, that's your problem. > + return is_list; > +} > + > +/** > + * qdict_crumple: > + * @src: the original flat dictionary (only scalar values) to crumple > + * @recursive: true to recursively crumple nested dictionaries > + * > + * Takes a flat dictionary whose keys use '.' separator to indicate > + * nesting, and values are scalars, and crumples it into a nested > + * structure. If the @recursive parameter is false, then only the > + * first level of structure implied by the keys will be crumpled. If > + * @recursive is true, then the input will be recursively crumpled to > + * expand all levels of structure in the keys. > + * > + * To include a literal '.' in a key name, it must be escaped as '..' > + * > + * For example, an input of: > + * > + * { 'foo.0.bar': 'one', 'foo.0.wizz': '1', > + * 'foo.1.bar': 'two', 'foo.1.wizz': '2' } > + * > + * will result in any output of: > + * > + * { > + * 'foo': [ > + * { 'bar': 'one', 'wizz': '1' }, > + * { 'bar': 'two', 'wizz': '2' } > + * ], > + * } > + * > + * The following scenarios in the input dict will result in an > + * error being returned: > + * > + * - Any values in @src are non-scalar types > + * - If keys in @src imply that a particular level is both a > + * list and a dict. eg, "foo.0.bar" and "foo.eek.bar". > + * - If keys in @src imply that a particular level is a list, > + * but the indexes are non-contigous. eg "foo.0.bar" and > + * "foo.2.bar" without any "foo.1.bar" present. > + * - If keys in @src represent list indexes, but are not in > + * the "%zu" format. eg "foo.+0.bar" Hm, so you thought of the case I mentioned above, but I don't see it handled properly in the code. > + * > + * Returns: either a QDict or QList for the nested data structure, or NULL > + * on error > + */ > +QObject *qdict_crumple(QDict *src, bool recursive, Error **errp) > +{ > + const QDictEntry *ent; > + QDict *two_level, *multi_level = NULL; > + QObject *dst = NULL, *child; > + size_t i; > + char *prefix = NULL; > + const char *suffix = NULL; > + int is_list; > + > + two_level = qdict_new(); > + > + /* Step 1: split our totally flat dict into a two level dict */ > + for (ent = qdict_first(src); ent != NULL; ent = qdict_next(src, ent)) { > + if (qobject_type(ent->value) == QTYPE_QDICT || > + qobject_type(ent->value) == QTYPE_QLIST) { > + error_setg(errp, "Value %s is not a scalar", > + ent->key); > + goto error; > + } > + > + qdict_split_flat_key(ent->key, &prefix, &suffix); > + > + child = qdict_get(two_level, prefix); > + if (suffix) { > + if (child) { > + if (qobject_type(child) != QTYPE_QDICT) { > + error_setg(errp, "Key %s prefix is already set as a scalar", > + prefix); > + goto error; > + } > + } else { > + child = QOBJECT(qdict_new()); > + qdict_put_obj(two_level, prefix, child); > + } > + qobject_incref(ent->value); > + qdict_put_obj(qobject_to_qdict(child), suffix, ent->value); > + } else { > + if (child) { > + error_setg(errp, "Key %s prefix is already set as a dict", > + prefix); > + goto error; > + } > + qobject_incref(ent->value); > + qdict_put_obj(two_level, prefix, ent->value); > + } > + > + g_free(prefix); > + prefix = NULL; > + } > + > + /* Step 2: optionally process the two level dict recursively > + * into a multi-level dict */ > + if (recursive) { > + multi_level = qdict_new(); > + for (ent = qdict_first(two_level); ent != NULL; > + ent = qdict_next(two_level, ent)) { > + > + if (qobject_type(ent->value) == QTYPE_QDICT) { > + child = qdict_crumple(qobject_to_qdict(ent->value), > + recursive, errp); > + if (!child) { > + goto error; > + } > + > + qdict_put_obj(multi_level, ent->key, child); > + } else { > + qobject_incref(ent->value); > + qdict_put_obj(multi_level, ent->key, ent->value); > + } > + } > + QDECREF(two_level); > + } else { > + multi_level = two_level; > + } > + two_level = NULL; > + > + /* Step 3: detect if we need to turn our dict into list */ > + is_list = qdict_is_list(multi_level, errp); > + if (is_list < 0) { > + goto error; > + } > + > + if (is_list) { > + dst = QOBJECT(qlist_new()); > + > + for (i = 0; i < qdict_size(multi_level); i++) { > + char *key = g_strdup_printf("%zu", i); > + > + child = qdict_get(multi_level, key); > + g_free(key); > + assert(child); So this is the place where the %zu requirement for key names is enforced. But where do we check this before to return an error instead of running into an assertion failure? If you turn this into another non-contiguous error, we should be fine. > + > + qobject_incref(child); > + qlist_append_obj(qobject_to_qlist(dst), child); > + } > + QDECREF(multi_level); > + multi_level = NULL; > + } else { > + dst = QOBJECT(multi_level); > + } > + > + return dst; > + > + error: > + g_free(prefix); > + QDECREF(multi_level); > + QDECREF(two_level); > + qobject_decref(dst); > + return NULL; > +} > + > + > /** > * qdict_array_entries(): Returns the number of direct array entries if the > * sub-QDict of src specified by the prefix in subqdict (or src itself for > diff --git a/tests/check-qdict.c b/tests/check-qdict.c > index 42da1e6..be4a132 100644 > --- a/tests/check-qdict.c > +++ b/tests/check-qdict.c > @@ -14,6 +14,7 @@ > #include "qapi/qmp/qint.h" > #include "qapi/qmp/qdict.h" > #include "qapi/qmp/qstring.h" > +#include "qapi/error.h" > #include "qemu-common.h" > > /* > @@ -595,6 +596,235 @@ static void qdict_join_test(void) > QDECREF(dict2); > } > > + > +static void qdict_crumple_test_nonrecursive(void) > +{ > + QDict *src, *dst, *rules, *vnc; > + QObject *child, *res; > + > + src = qdict_new(); > + qdict_put(src, "vnc.listen.addr", qstring_from_str("127.0.0.1")); > + qdict_put(src, "vnc.listen.port", qstring_from_str("5901")); > + qdict_put(src, "rule.0.match", qstring_from_str("fred")); > + qdict_put(src, "rule.0.policy", qstring_from_str("allow")); > + qdict_put(src, "rule.1.match", qstring_from_str("bob")); > + qdict_put(src, "rule.1.policy", qstring_from_str("deny")); Worth testing an escaped . as well? Possibly both in the prefix (where it should get unescaped) and in the suffix (where the doubling is still expected. > + res = qdict_crumple(src, false, &error_abort); > + > + g_assert_cmpint(qobject_type(res), ==, QTYPE_QDICT); > + > + dst = qobject_to_qdict(res); > + > + g_assert_cmpint(qdict_size(dst), ==, 2); > + > + child = qdict_get(dst, "vnc"); > + g_assert_cmpint(qobject_type(child), ==, QTYPE_QDICT); > + vnc = qdict_get_qdict(dst, "vnc"); > + > + g_assert_cmpint(qdict_size(vnc), ==, 2); > + > + g_assert_cmpstr("127.0.0.1", ==, qdict_get_str(vnc, "listen.addr")); > + g_assert_cmpstr("5901", ==, qdict_get_str(vnc, "listen.port")); > + > + child = qdict_get(dst, "rule"); > + g_assert_cmpint(qobject_type(child), ==, QTYPE_QDICT); > + rules = qdict_get_qdict(dst, "rule"); > + > + g_assert_cmpint(qdict_size(rules), ==, 4); > + > + g_assert_cmpstr("fred", ==, qdict_get_str(rules, "0.match")); > + g_assert_cmpstr("allow", ==, qdict_get_str(rules, "0.policy")); > + g_assert_cmpstr("bob", ==, qdict_get_str(rules, "1.match")); > + g_assert_cmpstr("deny", ==, qdict_get_str(rules, "1.policy")); > + > + QDECREF(src); > + QDECREF(dst); > +} > + > + > +static void qdict_crumple_test_listtop(void) > +{ > + QDict *src, *rule; > + QList *rules; > + QObject *res; > + > + src = qdict_new(); > + qdict_put(src, "0.match.name", qstring_from_str("Fred")); > + qdict_put(src, "0.match.email", qstring_from_str("fred@example.com")); > + qdict_put(src, "0.policy", qstring_from_str("allow")); > + qdict_put(src, "1.match.name", qstring_from_str("Bob")); > + qdict_put(src, "1.match.email", qstring_from_str("bob@example.com")); > + qdict_put(src, "1.policy", qstring_from_str("deny")); > + > + res = qdict_crumple(src, false, &error_abort); > + > + g_assert_cmpint(qobject_type(res), ==, QTYPE_QLIST); > + > + rules = qobject_to_qlist(res); > + > + g_assert_cmpint(qlist_size(rules), ==, 2); > + > + g_assert_cmpint(qobject_type(qlist_peek(rules)), ==, QTYPE_QDICT); > + rule = qobject_to_qdict(qlist_pop(rules)); > + g_assert_cmpint(qdict_size(rule), ==, 3); > + > + g_assert_cmpstr("Fred", ==, qdict_get_str(rule, "match.name")); > + g_assert_cmpstr("fred@example.com", ==, qdict_get_str(rule, "match.email")); > + g_assert_cmpstr("allow", ==, qdict_get_str(rule, "policy")); > + QDECREF(rule); > + > + g_assert_cmpint(qobject_type(qlist_peek(rules)), ==, QTYPE_QDICT); > + rule = qobject_to_qdict(qlist_pop(rules)); > + g_assert_cmpint(qdict_size(rule), ==, 3); > + > + g_assert_cmpstr("Bob", ==, qdict_get_str(rule, "match.name")); > + g_assert_cmpstr("bob@example.com", ==, qdict_get_str(rule, "match.email")); > + g_assert_cmpstr("deny", ==, qdict_get_str(rule, "policy")); > + QDECREF(rule); > + > + QDECREF(src); > + qobject_decref(res); > +} > + > + > +static void qdict_crumple_test_recursive(void) > +{ > + QDict *src, *dst, *rule, *vnc, *acl, *listen; > + QObject *child, *res; > + QList *rules; > + > + src = qdict_new(); > + qdict_put(src, "vnc.listen.addr", qstring_from_str("127.0.0.1")); > + qdict_put(src, "vnc.listen.port", qstring_from_str("5901")); > + qdict_put(src, "vnc.acl.rules.0.match", qstring_from_str("fred")); > + qdict_put(src, "vnc.acl.rules.0.policy", qstring_from_str("allow")); > + qdict_put(src, "vnc.acl.rules.1.match", qstring_from_str("bob")); > + qdict_put(src, "vnc.acl.rules.1.policy", qstring_from_str("deny")); > + qdict_put(src, "vnc.acl.default", qstring_from_str("deny")); Here some tests with escaped . would be nice, too. > + res = qdict_crumple(src, true, &error_abort); > + > + g_assert_cmpint(qobject_type(res), ==, QTYPE_QDICT); > + > + dst = qobject_to_qdict(res); > + > + g_assert_cmpint(qdict_size(dst), ==, 1); > + > + child = qdict_get(dst, "vnc"); > + g_assert_cmpint(qobject_type(child), ==, QTYPE_QDICT); > + vnc = qobject_to_qdict(child); > + > + child = qdict_get(vnc, "listen"); > + g_assert_cmpint(qobject_type(child), ==, QTYPE_QDICT); > + listen = qobject_to_qdict(child); > + g_assert_cmpstr("127.0.0.1", ==, qdict_get_str(listen, "addr")); > + g_assert_cmpstr("5901", ==, qdict_get_str(listen, "port")); > + > + child = qdict_get(vnc, "acl"); > + g_assert_cmpint(qobject_type(child), ==, QTYPE_QDICT); > + acl = qobject_to_qdict(child); > + > + child = qdict_get(acl, "rules"); > + g_assert_cmpint(qobject_type(child), ==, QTYPE_QLIST); > + rules = qobject_to_qlist(child); > + g_assert_cmpint(qlist_size(rules), ==, 2); > + > + rule = qobject_to_qdict(qlist_pop(rules)); > + g_assert_cmpint(qdict_size(rule), ==, 2); > + g_assert_cmpstr("fred", ==, qdict_get_str(rule, "match")); > + g_assert_cmpstr("allow", ==, qdict_get_str(rule, "policy")); > + QDECREF(rule); > + > + rule = qobject_to_qdict(qlist_pop(rules)); > + g_assert_cmpint(qdict_size(rule), ==, 2); > + g_assert_cmpstr("bob", ==, qdict_get_str(rule, "match")); > + g_assert_cmpstr("deny", ==, qdict_get_str(rule, "policy")); > + QDECREF(rule); > + > + QDECREF(src); > + QDECREF(dst); > +} > + > + > +static void qdict_crumple_test_empty(void) > +{ > + QDict *src, *dst; > + > + src = qdict_new(); > + > + dst = (QDict *)qdict_crumple(src, true, &error_abort); > + > + g_assert_cmpint(qdict_size(dst), ==, 0); > + > + QDECREF(src); > + QDECREF(dst); > +} > + > + > +static void qdict_crumple_test_bad_inputs(void) > +{ > + QDict *src; > + Error *error = NULL; > + > + src = qdict_new(); > + /* rule.0 can't be both a string and a dict */ > + qdict_put(src, "rule.0", qstring_from_str("fred")); > + qdict_put(src, "rule.0.policy", qstring_from_str("allow")); > + > + g_assert(qdict_crumple(src, true, &error) == NULL); > + g_assert(error != NULL); > + error_free(error); > + error = NULL; > + QDECREF(src); > + > + src = qdict_new(); > + /* rule can't be both a list and a dict */ > + qdict_put(src, "rule.0", qstring_from_str("fred")); > + qdict_put(src, "rule.a", qstring_from_str("allow")); > + > + g_assert(qdict_crumple(src, true, &error) == NULL); > + g_assert(error != NULL); > + error_free(error); > + error = NULL; > + QDECREF(src); > + > + src = qdict_new(); > + /* The input should be flat, ie no dicts or lists */ > + qdict_put(src, "rule.a", qdict_new()); > + qdict_put(src, "rule.b", qstring_from_str("allow")); > + > + g_assert(qdict_crumple(src, true, &error) == NULL); > + g_assert(error != NULL); > + error_free(error); > + error = NULL; > + QDECREF(src); > + > + > + src = qdict_new(); > + /* List indexes must not have gaps */ > + qdict_put(src, "rule.0", qdict_new()); You want to use something valid here (i.e. a scalar) > + qdict_put(src, "rule.3", qstring_from_str("allow")); > + > + g_assert(qdict_crumple(src, true, &error) == NULL); > + g_assert(error != NULL); > + error_free(error); > + error = NULL; > + QDECREF(src); > + > + > + src = qdict_new(); > + /* List indexes must be in %zu format */ > + qdict_put(src, "rule.0", qdict_new()); And here too. This invalid entry is the reason why you error out early instead of running into the assertion failure I mentioned above. > + qdict_put(src, "rule.+1", qstring_from_str("allow")); > + > + g_assert(qdict_crumple(src, true, &error) == NULL); > + g_assert(error != NULL); > + error_free(error); > + error = NULL; > + QDECREF(src); > +} Kevin
On Wed, Sep 14, 2016 at 04:18:42PM +0200, Kevin Wolf wrote: > Am 05.09.2016 um 17:16 hat Daniel P. Berrange geschrieben: > > The qdict_flatten() method will take a dict whose elements are > > further nested dicts/lists and flatten them by concatenating > > keys. > > > > The qdict_crumple() method aims to do the reverse, taking a flat > > qdict, and turning it into a set of nested dicts/lists. It will > > apply nesting based on the key name, with a '.' indicating a > > new level in the hierarchy. If the keys in the nested structure > > are all numeric, it will create a list, otherwise it will create > > a dict. > > > > If the keys are a mixture of numeric and non-numeric, or the > > numeric keys are not in strictly ascending order, an error will > > be reported. > > [...] > > > +static void qdict_split_flat_key(const char *key, char **prefix, > > + const char **suffix) > > +{ > > + const char *separator; > > + size_t i, j; > > + > > + /* Find first '.' separator, but if there is a pair '..' > > + * that acts as an escape, so skip over '..' */ > > + separator = NULL; > > + do { > > + if (separator) { > > + separator += 2; > > + } else { > > + separator = key; > > + } > > + separator = strchr(separator, '.'); > > + } while (separator && separator[1] == '.'); > > + > > + if (separator) { > > + *prefix = g_strndup(key, > > + separator - key); > > This fits in a single line. > > > + *suffix = separator + 1; > > + } else { > > + *prefix = g_strdup(key); > > + *suffix = NULL; > > + } > > + > > + /* Unescape the '..' sequence into '.' */ > > + for (i = 0, j = 0; (*prefix)[i] != '\0'; i++, j++) { > > + if ((*prefix)[i] == '.') { > > + assert((*prefix)[i + 1] == '.'); > > + i++; > > + } > > + (*prefix)[j] = (*prefix)[i]; > > + } > > + (*prefix)[j] = '\0'; > > +} > > + > > + > > +/** > > + * qdict_is_list: > > + * @maybe_list: dict to check if keys represent list elements. > > + * > > + * Determine whether all keys in @maybe_list are valid list elements. > > + * If @maybe_list is non-zero in length and all the keys look like > > + * valid list indexes, this will return 1. If @maybe_list is zero > > + * length or all keys are non-numeric then it will return 0 to indicate > > + * it is a normal qdict. If there is a mix of numeric and non-numeric > > + * keys, or the list indexes are non-contiguous, an error is reported. > > + * > > + * Returns: 1 if a valid list, 0 if a dict, -1 on error > > + */ > > +static int qdict_is_list(QDict *maybe_list, Error **errp) > > +{ > > + const QDictEntry *ent; > > + ssize_t len = 0; > > + ssize_t max = -1; > > + int is_list = -1; > > + int64_t val; > > + > > + for (ent = qdict_first(maybe_list); ent != NULL; > > + ent = qdict_next(maybe_list, ent)) { > > + > > + if (qemu_strtoll(ent->key, NULL, 10, &val) == 0) { > > + if (is_list == -1) { > > + is_list = 1; > > + } else if (!is_list) { > > + error_setg(errp, > > + "Cannot crumple a dictionary with a mix of list " > > + "and non-list keys"); > > This is a message that users will see if they pass a bad command line > option. I don't think they will understand what it means to "crumple a > dictionary" or that they tried to do this. > > Maybe simply "Cannot mix list and non-list keys"? Oh yes, good point. > > + if (is_list == -1) { > > + assert(!qdict_size(maybe_list)); > > + is_list = 0; > > + } > > + > > + if (len != (max + 1)) { > > + error_setg(errp, "List indexes are not contiguous, " > > + "saw %zd elements but %zd largest index", > > + len, max); > > + return -1; > > + } > > I don't think this is catching everything that isn't contiguous, but I'm > not sure whether we care. > > One reason is that you accept negative indexes above, the other one is > that the keys are strings, so I could pass "1", "+1", "01" and "3" and it > would be accepted. > > It's probably reasonable enough to say that in such cases you get what > you get, and if future versions behave differently, that's your problem. In the context of this 'qdict_is_list()' method I think that's ok - even if they use "1", "+1", "01" and "3", from the POV of this method it is a list. The qdict_crumple method could however then detect if there are keys that are duplicated and/or missing, which will handle the case you illustrate. I'll add a checks and a test for this. > > +/** > > + * qdict_crumple: > > + * @src: the original flat dictionary (only scalar values) to crumple > > + * @recursive: true to recursively crumple nested dictionaries > > + * > > + * Takes a flat dictionary whose keys use '.' separator to indicate > > + * nesting, and values are scalars, and crumples it into a nested > > + * structure. If the @recursive parameter is false, then only the > > + * first level of structure implied by the keys will be crumpled. If > > + * @recursive is true, then the input will be recursively crumpled to > > + * expand all levels of structure in the keys. > > + * > > + * To include a literal '.' in a key name, it must be escaped as '..' > > + * > > + * For example, an input of: > > + * > > + * { 'foo.0.bar': 'one', 'foo.0.wizz': '1', > > + * 'foo.1.bar': 'two', 'foo.1.wizz': '2' } > > + * > > + * will result in any output of: > > + * > > + * { > > + * 'foo': [ > > + * { 'bar': 'one', 'wizz': '1' }, > > + * { 'bar': 'two', 'wizz': '2' } > > + * ], > > + * } > > + * > > + * The following scenarios in the input dict will result in an > > + * error being returned: > > + * > > + * - Any values in @src are non-scalar types > > + * - If keys in @src imply that a particular level is both a > > + * list and a dict. eg, "foo.0.bar" and "foo.eek.bar". > > + * - If keys in @src imply that a particular level is a list, > > + * but the indexes are non-contigous. eg "foo.0.bar" and > > + * "foo.2.bar" without any "foo.1.bar" present. > > + * - If keys in @src represent list indexes, but are not in > > + * the "%zu" format. eg "foo.+0.bar" > > Hm, so you thought of the case I mentioned above, but I don't see it > handled properly in the code. Yeah, I've not handled it well enough. > > + /* Step 3: detect if we need to turn our dict into list */ > > + is_list = qdict_is_list(multi_level, errp); > > + if (is_list < 0) { > > + goto error; > > + } > > + > > + if (is_list) { > > + dst = QOBJECT(qlist_new()); > > + > > + for (i = 0; i < qdict_size(multi_level); i++) { > > + char *key = g_strdup_printf("%zu", i); > > + > > + child = qdict_get(multi_level, key); > > + g_free(key); > > + assert(child); > > So this is the place where the %zu requirement for key names is > enforced. But where do we check this before to return an error instead > of running into an assertion failure? > > If you turn this into another non-contiguous error, we should be fine. Yes, I should turn the assert into an reported error. > > + > > + qobject_incref(child); > > + qlist_append_obj(qobject_to_qlist(dst), child); > > + } > > + QDECREF(multi_level); > > + multi_level = NULL; > > + } else { > > + dst = QOBJECT(multi_level); > > +static void qdict_crumple_test_nonrecursive(void) > > +{ > > + QDict *src, *dst, *rules, *vnc; > > + QObject *child, *res; > > + > > + src = qdict_new(); > > + qdict_put(src, "vnc.listen.addr", qstring_from_str("127.0.0.1")); > > + qdict_put(src, "vnc.listen.port", qstring_from_str("5901")); > > + qdict_put(src, "rule.0.match", qstring_from_str("fred")); > > + qdict_put(src, "rule.0.policy", qstring_from_str("allow")); > > + qdict_put(src, "rule.1.match", qstring_from_str("bob")); > > + qdict_put(src, "rule.1.policy", qstring_from_str("deny")); > > Worth testing an escaped . as well? Possibly both in the prefix (where > it should get unescaped) and in the suffix (where the doubling is still > expected. Yes, we should validate escaping. > > + > > +static void qdict_crumple_test_bad_inputs(void) > > +{ > > + QDict *src; > > + Error *error = NULL; > > + > > + src = qdict_new(); > > + /* rule.0 can't be both a string and a dict */ > > + qdict_put(src, "rule.0", qstring_from_str("fred")); > > + qdict_put(src, "rule.0.policy", qstring_from_str("allow")); > > + > > + g_assert(qdict_crumple(src, true, &error) == NULL); > > + g_assert(error != NULL); > > + error_free(error); > > + error = NULL; > > + QDECREF(src); > > + > > + src = qdict_new(); > > + /* rule can't be both a list and a dict */ > > + qdict_put(src, "rule.0", qstring_from_str("fred")); > > + qdict_put(src, "rule.a", qstring_from_str("allow")); > > + > > + g_assert(qdict_crumple(src, true, &error) == NULL); > > + g_assert(error != NULL); > > + error_free(error); > > + error = NULL; > > + QDECREF(src); > > + > > + src = qdict_new(); > > + /* The input should be flat, ie no dicts or lists */ > > + qdict_put(src, "rule.a", qdict_new()); > > + qdict_put(src, "rule.b", qstring_from_str("allow")); > > + > > + g_assert(qdict_crumple(src, true, &error) == NULL); > > + g_assert(error != NULL); > > + error_free(error); > > + error = NULL; > > + QDECREF(src); > > + > > + > > + src = qdict_new(); > > + /* List indexes must not have gaps */ > > + qdict_put(src, "rule.0", qdict_new()); > > You want to use something valid here (i.e. a scalar) > > > + qdict_put(src, "rule.3", qstring_from_str("allow")); > > + > > + g_assert(qdict_crumple(src, true, &error) == NULL); > > + g_assert(error != NULL); > > + error_free(error); > > + error = NULL; > > + QDECREF(src); > > + > > + > > + src = qdict_new(); > > + /* List indexes must be in %zu format */ > > + qdict_put(src, "rule.0", qdict_new()); > > And here too. This invalid entry is the reason why you error out early > instead of running into the assertion failure I mentioned above. OK Regards, Daniel
diff --git a/include/qapi/qmp/qdict.h b/include/qapi/qmp/qdict.h index 71b8eb0..8a3ac13 100644 --- a/include/qapi/qmp/qdict.h +++ b/include/qapi/qmp/qdict.h @@ -73,6 +73,7 @@ void qdict_flatten(QDict *qdict); void qdict_extract_subqdict(QDict *src, QDict **dst, const char *start); void qdict_array_split(QDict *src, QList **dst); int qdict_array_entries(QDict *src, const char *subqdict); +QObject *qdict_crumple(QDict *src, bool recursive, Error **errp); void qdict_join(QDict *dest, QDict *src, bool overwrite); diff --git a/qobject/qdict.c b/qobject/qdict.c index 60f158c..a075eb1 100644 --- a/qobject/qdict.c +++ b/qobject/qdict.c @@ -17,6 +17,7 @@ #include "qapi/qmp/qbool.h" #include "qapi/qmp/qstring.h" #include "qapi/qmp/qobject.h" +#include "qapi/error.h" #include "qemu/queue.h" #include "qemu-common.h" #include "qemu/cutils.h" @@ -683,6 +684,288 @@ void qdict_array_split(QDict *src, QList **dst) } } + +/** + * qdict_split_flat_key: + * @key: the key string to split + * @prefix: non-NULL pointer to hold extracted prefix + * @suffix: non-NULL pointer to remaining suffix + * + * Given a flattened key such as 'foo.0.bar', split it into two parts + * at the first '.' separator. Allows double dot ('..') to escape the + * normal separator. + * + * eg + * 'foo.0.bar' -> prefix='foo' and suffix='0.bar' + * 'foo..0.bar' -> prefix='foo.0' and suffix='bar' + * + * The '..' sequence will be unescaped in the returned 'prefix' + * string. The 'suffix' string will be left in escaped format, so it + * can be fed back into the qdict_split_flat_key() key as the input + * later. + * + * The caller is responsible for freeing the string returned in @prefix + * using g_free(). + */ +static void qdict_split_flat_key(const char *key, char **prefix, + const char **suffix) +{ + const char *separator; + size_t i, j; + + /* Find first '.' separator, but if there is a pair '..' + * that acts as an escape, so skip over '..' */ + separator = NULL; + do { + if (separator) { + separator += 2; + } else { + separator = key; + } + separator = strchr(separator, '.'); + } while (separator && separator[1] == '.'); + + if (separator) { + *prefix = g_strndup(key, + separator - key); + *suffix = separator + 1; + } else { + *prefix = g_strdup(key); + *suffix = NULL; + } + + /* Unescape the '..' sequence into '.' */ + for (i = 0, j = 0; (*prefix)[i] != '\0'; i++, j++) { + if ((*prefix)[i] == '.') { + assert((*prefix)[i + 1] == '.'); + i++; + } + (*prefix)[j] = (*prefix)[i]; + } + (*prefix)[j] = '\0'; +} + + +/** + * qdict_is_list: + * @maybe_list: dict to check if keys represent list elements. + * + * Determine whether all keys in @maybe_list are valid list elements. + * If @maybe_list is non-zero in length and all the keys look like + * valid list indexes, this will return 1. If @maybe_list is zero + * length or all keys are non-numeric then it will return 0 to indicate + * it is a normal qdict. If there is a mix of numeric and non-numeric + * keys, or the list indexes are non-contiguous, an error is reported. + * + * Returns: 1 if a valid list, 0 if a dict, -1 on error + */ +static int qdict_is_list(QDict *maybe_list, Error **errp) +{ + const QDictEntry *ent; + ssize_t len = 0; + ssize_t max = -1; + int is_list = -1; + int64_t val; + + for (ent = qdict_first(maybe_list); ent != NULL; + ent = qdict_next(maybe_list, ent)) { + + if (qemu_strtoll(ent->key, NULL, 10, &val) == 0) { + if (is_list == -1) { + is_list = 1; + } else if (!is_list) { + error_setg(errp, + "Cannot crumple a dictionary with a mix of list " + "and non-list keys"); + return -1; + } + len++; + if (val > max) { + max = val; + } + } else { + if (is_list == -1) { + is_list = 0; + } else if (is_list) { + error_setg(errp, + "Cannot crumple a dictionary with a mix of list " + "and non-list keys"); + return -1; + } + } + } + + if (is_list == -1) { + assert(!qdict_size(maybe_list)); + is_list = 0; + } + + if (len != (max + 1)) { + error_setg(errp, "List indexes are not contiguous, " + "saw %zd elements but %zd largest index", + len, max); + return -1; + } + + return is_list; +} + +/** + * qdict_crumple: + * @src: the original flat dictionary (only scalar values) to crumple + * @recursive: true to recursively crumple nested dictionaries + * + * Takes a flat dictionary whose keys use '.' separator to indicate + * nesting, and values are scalars, and crumples it into a nested + * structure. If the @recursive parameter is false, then only the + * first level of structure implied by the keys will be crumpled. If + * @recursive is true, then the input will be recursively crumpled to + * expand all levels of structure in the keys. + * + * To include a literal '.' in a key name, it must be escaped as '..' + * + * For example, an input of: + * + * { 'foo.0.bar': 'one', 'foo.0.wizz': '1', + * 'foo.1.bar': 'two', 'foo.1.wizz': '2' } + * + * will result in any output of: + * + * { + * 'foo': [ + * { 'bar': 'one', 'wizz': '1' }, + * { 'bar': 'two', 'wizz': '2' } + * ], + * } + * + * The following scenarios in the input dict will result in an + * error being returned: + * + * - Any values in @src are non-scalar types + * - If keys in @src imply that a particular level is both a + * list and a dict. eg, "foo.0.bar" and "foo.eek.bar". + * - If keys in @src imply that a particular level is a list, + * but the indexes are non-contigous. eg "foo.0.bar" and + * "foo.2.bar" without any "foo.1.bar" present. + * - If keys in @src represent list indexes, but are not in + * the "%zu" format. eg "foo.+0.bar" + * + * Returns: either a QDict or QList for the nested data structure, or NULL + * on error + */ +QObject *qdict_crumple(QDict *src, bool recursive, Error **errp) +{ + const QDictEntry *ent; + QDict *two_level, *multi_level = NULL; + QObject *dst = NULL, *child; + size_t i; + char *prefix = NULL; + const char *suffix = NULL; + int is_list; + + two_level = qdict_new(); + + /* Step 1: split our totally flat dict into a two level dict */ + for (ent = qdict_first(src); ent != NULL; ent = qdict_next(src, ent)) { + if (qobject_type(ent->value) == QTYPE_QDICT || + qobject_type(ent->value) == QTYPE_QLIST) { + error_setg(errp, "Value %s is not a scalar", + ent->key); + goto error; + } + + qdict_split_flat_key(ent->key, &prefix, &suffix); + + child = qdict_get(two_level, prefix); + if (suffix) { + if (child) { + if (qobject_type(child) != QTYPE_QDICT) { + error_setg(errp, "Key %s prefix is already set as a scalar", + prefix); + goto error; + } + } else { + child = QOBJECT(qdict_new()); + qdict_put_obj(two_level, prefix, child); + } + qobject_incref(ent->value); + qdict_put_obj(qobject_to_qdict(child), suffix, ent->value); + } else { + if (child) { + error_setg(errp, "Key %s prefix is already set as a dict", + prefix); + goto error; + } + qobject_incref(ent->value); + qdict_put_obj(two_level, prefix, ent->value); + } + + g_free(prefix); + prefix = NULL; + } + + /* Step 2: optionally process the two level dict recursively + * into a multi-level dict */ + if (recursive) { + multi_level = qdict_new(); + for (ent = qdict_first(two_level); ent != NULL; + ent = qdict_next(two_level, ent)) { + + if (qobject_type(ent->value) == QTYPE_QDICT) { + child = qdict_crumple(qobject_to_qdict(ent->value), + recursive, errp); + if (!child) { + goto error; + } + + qdict_put_obj(multi_level, ent->key, child); + } else { + qobject_incref(ent->value); + qdict_put_obj(multi_level, ent->key, ent->value); + } + } + QDECREF(two_level); + } else { + multi_level = two_level; + } + two_level = NULL; + + /* Step 3: detect if we need to turn our dict into list */ + is_list = qdict_is_list(multi_level, errp); + if (is_list < 0) { + goto error; + } + + if (is_list) { + dst = QOBJECT(qlist_new()); + + for (i = 0; i < qdict_size(multi_level); i++) { + char *key = g_strdup_printf("%zu", i); + + child = qdict_get(multi_level, key); + g_free(key); + assert(child); + + qobject_incref(child); + qlist_append_obj(qobject_to_qlist(dst), child); + } + QDECREF(multi_level); + multi_level = NULL; + } else { + dst = QOBJECT(multi_level); + } + + return dst; + + error: + g_free(prefix); + QDECREF(multi_level); + QDECREF(two_level); + qobject_decref(dst); + return NULL; +} + + /** * qdict_array_entries(): Returns the number of direct array entries if the * sub-QDict of src specified by the prefix in subqdict (or src itself for diff --git a/tests/check-qdict.c b/tests/check-qdict.c index 42da1e6..be4a132 100644 --- a/tests/check-qdict.c +++ b/tests/check-qdict.c @@ -14,6 +14,7 @@ #include "qapi/qmp/qint.h" #include "qapi/qmp/qdict.h" #include "qapi/qmp/qstring.h" +#include "qapi/error.h" #include "qemu-common.h" /* @@ -595,6 +596,235 @@ static void qdict_join_test(void) QDECREF(dict2); } + +static void qdict_crumple_test_nonrecursive(void) +{ + QDict *src, *dst, *rules, *vnc; + QObject *child, *res; + + src = qdict_new(); + qdict_put(src, "vnc.listen.addr", qstring_from_str("127.0.0.1")); + qdict_put(src, "vnc.listen.port", qstring_from_str("5901")); + qdict_put(src, "rule.0.match", qstring_from_str("fred")); + qdict_put(src, "rule.0.policy", qstring_from_str("allow")); + qdict_put(src, "rule.1.match", qstring_from_str("bob")); + qdict_put(src, "rule.1.policy", qstring_from_str("deny")); + + res = qdict_crumple(src, false, &error_abort); + + g_assert_cmpint(qobject_type(res), ==, QTYPE_QDICT); + + dst = qobject_to_qdict(res); + + g_assert_cmpint(qdict_size(dst), ==, 2); + + child = qdict_get(dst, "vnc"); + g_assert_cmpint(qobject_type(child), ==, QTYPE_QDICT); + vnc = qdict_get_qdict(dst, "vnc"); + + g_assert_cmpint(qdict_size(vnc), ==, 2); + + g_assert_cmpstr("127.0.0.1", ==, qdict_get_str(vnc, "listen.addr")); + g_assert_cmpstr("5901", ==, qdict_get_str(vnc, "listen.port")); + + child = qdict_get(dst, "rule"); + g_assert_cmpint(qobject_type(child), ==, QTYPE_QDICT); + rules = qdict_get_qdict(dst, "rule"); + + g_assert_cmpint(qdict_size(rules), ==, 4); + + g_assert_cmpstr("fred", ==, qdict_get_str(rules, "0.match")); + g_assert_cmpstr("allow", ==, qdict_get_str(rules, "0.policy")); + g_assert_cmpstr("bob", ==, qdict_get_str(rules, "1.match")); + g_assert_cmpstr("deny", ==, qdict_get_str(rules, "1.policy")); + + QDECREF(src); + QDECREF(dst); +} + + +static void qdict_crumple_test_listtop(void) +{ + QDict *src, *rule; + QList *rules; + QObject *res; + + src = qdict_new(); + qdict_put(src, "0.match.name", qstring_from_str("Fred")); + qdict_put(src, "0.match.email", qstring_from_str("fred@example.com")); + qdict_put(src, "0.policy", qstring_from_str("allow")); + qdict_put(src, "1.match.name", qstring_from_str("Bob")); + qdict_put(src, "1.match.email", qstring_from_str("bob@example.com")); + qdict_put(src, "1.policy", qstring_from_str("deny")); + + res = qdict_crumple(src, false, &error_abort); + + g_assert_cmpint(qobject_type(res), ==, QTYPE_QLIST); + + rules = qobject_to_qlist(res); + + g_assert_cmpint(qlist_size(rules), ==, 2); + + g_assert_cmpint(qobject_type(qlist_peek(rules)), ==, QTYPE_QDICT); + rule = qobject_to_qdict(qlist_pop(rules)); + g_assert_cmpint(qdict_size(rule), ==, 3); + + g_assert_cmpstr("Fred", ==, qdict_get_str(rule, "match.name")); + g_assert_cmpstr("fred@example.com", ==, qdict_get_str(rule, "match.email")); + g_assert_cmpstr("allow", ==, qdict_get_str(rule, "policy")); + QDECREF(rule); + + g_assert_cmpint(qobject_type(qlist_peek(rules)), ==, QTYPE_QDICT); + rule = qobject_to_qdict(qlist_pop(rules)); + g_assert_cmpint(qdict_size(rule), ==, 3); + + g_assert_cmpstr("Bob", ==, qdict_get_str(rule, "match.name")); + g_assert_cmpstr("bob@example.com", ==, qdict_get_str(rule, "match.email")); + g_assert_cmpstr("deny", ==, qdict_get_str(rule, "policy")); + QDECREF(rule); + + QDECREF(src); + qobject_decref(res); +} + + +static void qdict_crumple_test_recursive(void) +{ + QDict *src, *dst, *rule, *vnc, *acl, *listen; + QObject *child, *res; + QList *rules; + + src = qdict_new(); + qdict_put(src, "vnc.listen.addr", qstring_from_str("127.0.0.1")); + qdict_put(src, "vnc.listen.port", qstring_from_str("5901")); + qdict_put(src, "vnc.acl.rules.0.match", qstring_from_str("fred")); + qdict_put(src, "vnc.acl.rules.0.policy", qstring_from_str("allow")); + qdict_put(src, "vnc.acl.rules.1.match", qstring_from_str("bob")); + qdict_put(src, "vnc.acl.rules.1.policy", qstring_from_str("deny")); + qdict_put(src, "vnc.acl.default", qstring_from_str("deny")); + + res = qdict_crumple(src, true, &error_abort); + + g_assert_cmpint(qobject_type(res), ==, QTYPE_QDICT); + + dst = qobject_to_qdict(res); + + g_assert_cmpint(qdict_size(dst), ==, 1); + + child = qdict_get(dst, "vnc"); + g_assert_cmpint(qobject_type(child), ==, QTYPE_QDICT); + vnc = qobject_to_qdict(child); + + child = qdict_get(vnc, "listen"); + g_assert_cmpint(qobject_type(child), ==, QTYPE_QDICT); + listen = qobject_to_qdict(child); + g_assert_cmpstr("127.0.0.1", ==, qdict_get_str(listen, "addr")); + g_assert_cmpstr("5901", ==, qdict_get_str(listen, "port")); + + child = qdict_get(vnc, "acl"); + g_assert_cmpint(qobject_type(child), ==, QTYPE_QDICT); + acl = qobject_to_qdict(child); + + child = qdict_get(acl, "rules"); + g_assert_cmpint(qobject_type(child), ==, QTYPE_QLIST); + rules = qobject_to_qlist(child); + g_assert_cmpint(qlist_size(rules), ==, 2); + + rule = qobject_to_qdict(qlist_pop(rules)); + g_assert_cmpint(qdict_size(rule), ==, 2); + g_assert_cmpstr("fred", ==, qdict_get_str(rule, "match")); + g_assert_cmpstr("allow", ==, qdict_get_str(rule, "policy")); + QDECREF(rule); + + rule = qobject_to_qdict(qlist_pop(rules)); + g_assert_cmpint(qdict_size(rule), ==, 2); + g_assert_cmpstr("bob", ==, qdict_get_str(rule, "match")); + g_assert_cmpstr("deny", ==, qdict_get_str(rule, "policy")); + QDECREF(rule); + + QDECREF(src); + QDECREF(dst); +} + + +static void qdict_crumple_test_empty(void) +{ + QDict *src, *dst; + + src = qdict_new(); + + dst = (QDict *)qdict_crumple(src, true, &error_abort); + + g_assert_cmpint(qdict_size(dst), ==, 0); + + QDECREF(src); + QDECREF(dst); +} + + +static void qdict_crumple_test_bad_inputs(void) +{ + QDict *src; + Error *error = NULL; + + src = qdict_new(); + /* rule.0 can't be both a string and a dict */ + qdict_put(src, "rule.0", qstring_from_str("fred")); + qdict_put(src, "rule.0.policy", qstring_from_str("allow")); + + g_assert(qdict_crumple(src, true, &error) == NULL); + g_assert(error != NULL); + error_free(error); + error = NULL; + QDECREF(src); + + src = qdict_new(); + /* rule can't be both a list and a dict */ + qdict_put(src, "rule.0", qstring_from_str("fred")); + qdict_put(src, "rule.a", qstring_from_str("allow")); + + g_assert(qdict_crumple(src, true, &error) == NULL); + g_assert(error != NULL); + error_free(error); + error = NULL; + QDECREF(src); + + src = qdict_new(); + /* The input should be flat, ie no dicts or lists */ + qdict_put(src, "rule.a", qdict_new()); + qdict_put(src, "rule.b", qstring_from_str("allow")); + + g_assert(qdict_crumple(src, true, &error) == NULL); + g_assert(error != NULL); + error_free(error); + error = NULL; + QDECREF(src); + + + src = qdict_new(); + /* List indexes must not have gaps */ + qdict_put(src, "rule.0", qdict_new()); + qdict_put(src, "rule.3", qstring_from_str("allow")); + + g_assert(qdict_crumple(src, true, &error) == NULL); + g_assert(error != NULL); + error_free(error); + error = NULL; + QDECREF(src); + + + src = qdict_new(); + /* List indexes must be in %zu format */ + qdict_put(src, "rule.0", qdict_new()); + qdict_put(src, "rule.+1", qstring_from_str("allow")); + + g_assert(qdict_crumple(src, true, &error) == NULL); + g_assert(error != NULL); + error_free(error); + error = NULL; + QDECREF(src); +} + /* * Errors test-cases */ @@ -742,6 +972,17 @@ int main(int argc, char **argv) g_test_add_func("/errors/put_exists", qdict_put_exists_test); g_test_add_func("/errors/get_not_exists", qdict_get_not_exists_test); + g_test_add_func("/public/crumple/nonrecursive", + qdict_crumple_test_nonrecursive); + g_test_add_func("/public/crumple/recursive", + qdict_crumple_test_recursive); + g_test_add_func("/public/crumple/listtop", + qdict_crumple_test_listtop); + g_test_add_func("/public/crumple/empty", + qdict_crumple_test_empty); + g_test_add_func("/public/crumple/bad_inputs", + qdict_crumple_test_bad_inputs); + /* The Big one */ if (g_test_slow()) { g_test_add_func("/stress/test", qdict_stress_test);
The qdict_flatten() method will take a dict whose elements are further nested dicts/lists and flatten them by concatenating keys. The qdict_crumple() method aims to do the reverse, taking a flat qdict, and turning it into a set of nested dicts/lists. It will apply nesting based on the key name, with a '.' indicating a new level in the hierarchy. If the keys in the nested structure are all numeric, it will create a list, otherwise it will create a dict. If the keys are a mixture of numeric and non-numeric, or the numeric keys are not in strictly ascending order, an error will be reported. As an example, a flat dict containing { 'foo.0.bar': 'one', 'foo.0.wizz': '1', 'foo.1.bar': 'two', 'foo.1.wizz': '2' } will get turned into a dict with one element 'foo' whose value is a list. The list elements will each in turn be dicts. { 'foo': [ { 'bar': 'one', 'wizz': '1' }, { 'bar': 'two', 'wizz': '2' } ], } If the key is intended to contain a literal '.', then it must be escaped as '..'. ie a flat dict { 'foo..bar': 'wizz', 'bar.foo..bar': 'eek', 'bar.hello': 'world' } Will end up as { 'foo.bar': 'wizz', 'bar': { 'foo.bar': 'eek', 'hello': 'world' } } The intent of this function is that it allows a set of QemuOpts to be turned into a nested data structure that mirrors the nesting used when the same object is defined over QMP. Reviewed-by: Marc-André Lureau <marcandre.lureau@redhat.com> Signed-off-by: Daniel P. Berrange <berrange@redhat.com> --- include/qapi/qmp/qdict.h | 1 + qobject/qdict.c | 283 +++++++++++++++++++++++++++++++++++++++++++++++ tests/check-qdict.c | 241 ++++++++++++++++++++++++++++++++++++++++ 3 files changed, 525 insertions(+)