| Message ID | 1465920443-22804-2-git-send-email-berrange@redhat.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
Hi On Tue, Jun 14, 2016 at 6:07 PM, Daniel P. Berrange <berrange@redhat.com> wrote: > 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. > > 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(+) > > 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..514d7b6 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 strin returned in @prefix s/strin/string > + * 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 missing : > + * @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 contigous, " > + "saw %zd elements but %zd largest index", > + len, max); > + return -1; > + } > + > + return is_list ? 1 : 0; > +} > + > +/** > + * 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 crumpls it into a nested crumples > + * 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); > -- > 2.5.5 > > Reviewed-by: Marc-André Lureau <marcandre.lureau@redhat.com>
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..514d7b6 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 strin 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 contigous, " + "saw %zd elements but %zd largest index", + len, max); + return -1; + } + + return is_list ? 1 : 0; +} + +/** + * 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 crumpls 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. 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(+)