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

[Daniel P. Berrange]

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
-- 
|: http://berrange.com      -o-    http://www.flickr.com/photos/dberrange/ :|
|: http://libvirt.org              -o-             http://virt-manager.org :|
|: http://autobuild.org       -o-         http://search.cpan.org/~danberr/ :|
|: http://entangle-photo.org       -o-       http://live.gnome.org/gtk-vnc :|