Re: [Qemu-devel] [PATCH v11 1/6] qdict: implement a qdict_crumple method for un-flattening a dict

[Kevin Wolf]

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("address@hidden"));
> +    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("address@hidden"));
> +    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("address@hidden", ==, 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("address@hidden", ==, 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