Re: [Qemu-block] [Qemu-devel] [PATCH v5 01/11] qdict: implement a qdict_crumple method for un-flattening a dict

[Markus Armbruster]

"Daniel P. Berrange" <address@hidden> writes:

> On Thu, Jun 09, 2016 at 03:20:47PM +0200, Markus Armbruster wrote:
>> I apologize for the lateness of this review.
>> 
>> "Daniel P. Berrange" <address@hidden> writes:
>> 
>> > 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 <address@hidden>
>> 
>
>> > +/**
>> > + * qdict_split_flat_key:
>> > + * @key: the key string to split
>> > + * @prefix: non-NULL pointer to hold extracted prefix
>> > + * @suffix: non-NULL pointer to hold extracted 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.
>> 
>> Why is the suffix strdup'ed then?
>
> It doesn't need to be - i'll make it const.
>
>
>
>> > +}
>> > +
>> > +
>> > +/**
>> > + * qdict_list_size:
>> > + * @maybe_list: dict that may be only list elements
>> 
>> Huh?  How can a dictionary "be only list elements"?
>> 
>> Do you mean "the dictionary to test?"
>
> I'll say "dict to search for keys representing list elements."

Yes, that's better.

>> > + *
>> > + * Determine whether all keys in @maybe_list are
>> > + * valid list elements. If they are all valid,
>> > + * then this returns the number of elements. If
>> > + * they all look like non-numeric keys, then returns
>> > + * zero. If there is a mix of numeric and non-numeric
>> > + * keys, then an error is set as it is both a list
>> > + * and a dict at once.
>> 
>> This is well-defined only if empty @maybe_list is considered to have
>> dict nature, not list nature.  Else, return value zero could be the
>> length of the empty list or the special "has dict nature" value.
>> 
>> Please spell out behavior for empty @maybe_list.
>
> Yep, empty list will imply qdict nature and so return zero.
>
>> > + *
>> > + * Returns: number of list elements, 0 if a dict, -1 on error
>> 
>> Awkward function name.  qdict_list_size_if_list() would be clear.
>>
>> But I'd simply turn this into a predicate qdict_is_list(), and have the
>> caller use qdict_size() to get the number of elements.
>
> I thought that qdict_size() would cause another iteration, but
> I see now it just returns a cached size. So I'll switch to
> qidct_is_list().
>
>> > +static ssize_t qdict_list_size(QDict *maybe_list, Error **errp)
>> > +{
>> > +    const QDictEntry *entry, *next;
>> > +    ssize_t len = 0;
>> > +    ssize_t max = -1;
>> > +    int is_list = -1;
>> > +    int64_t val;
>> > +
>> > +    entry = qdict_first(maybe_list);
>> > +    while (entry != NULL) {
>> > +        next = qdict_next(maybe_list, entry);
>> 
>> Please keep the loop control in one place:
>> 
>>        for (entry = qdict_first(maybe_list); entry; entry = 
>> qdict_next(entry)) {
>> 
>> I'd rename some variables for less verbiage:
>> 
>>        for (ent = qdict_first(dict); ent; ent = qdict_next(ent)) {
>> 
>> Your loop control also works when the loop body deletes @entry from
>> @maybe_list.  Seeing such loop control in a function that isn't supposed
>> to change the its argument makes the reviewer go "WTF?!?" :)
>
> This pattern was left from an earlier version where all the code was in
> one method. I'll change it to a for() loop now.
>
>> 
>> > +
>> > +        if (qemu_strtoll(entry->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;
>> > +            }
>> > +        }
>> > +
>> > +        entry = next;
>> > +    }
>> > +
>> > +    if (is_list == -1) {
>> > +        is_list = 0;
>> 
>> This can happen only when @maybe_list is empty.  Okay, but perhaps you'd
>> like to assert(!qdict_size(maybe_list)).
>
> Ok
>
>> 
>> > +    }
>> > +
>> > +    if (len != (max + 1)) {
>> > +        error_setg(errp, "List indexes are not continuous, "
>> > +                   "saw %zd elements but %zd largest index",
>> > +                   len, max);
>> > +        return -1;
>> 
>> contiguous?
>> 
>> What if we saw indexes 0, 2, 2?
>
> That would imply that the dict had two entries with the same
> key, which by definition is impossible with a dict data
> structure.

I got confused :)

>> > +    }
>> > +
>> > +    return is_list ? len : 0;
>> > +}
>> > +
>> > +/**
>> > + * qdict_crumple:
>> > + * @src: the original flat dictionary to crumple
>> 
>> "Flat" means all values are scalar.  Should we spell that out?
>
> Yep, ok.
>
>> > + * @recursive: true to recursively crumple nested dictionaries
>> > + *
>> > + * Takes a flat dictionary whose keys use '.' separator to
>> > + * indicate nesting, and values are scalars, crumplings it
>> 
>> s/, crumplings/, and crumples/
>> 
>> > + * 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' }
>> > + *   ],
>> > + * }
>> > + *
>> > + * Returns: either a QDict or QList for the nested data structure
>> 
>> I think you should discuss how this can fail.
>
> Will do.
>
>> > +QObject *qdict_crumple(QDict *src, bool recursive, Error **errp)
>> > +{
>> > +    const QDictEntry *entry, *next;
>> > +    QDict *two_level, *multi_level = NULL;
>> > +    QObject *dst = NULL, *child;
>> > +    ssize_t list_len;
>> > +    size_t i;
>> > +    char *prefix = NULL, *suffix = NULL;
>> > +
>> > +    two_level = qdict_new();
>> > +    entry = qdict_first(src);
>> > +
>> > +    /* Step 1: split our totally flat dict into a two level dict */
>> > +    while (entry != NULL) {
>> > +        next = qdict_next(src, entry);
>> 
>> Again, keep the loop control in one place.
>> 
>> > +
>> > +        if (qobject_type(entry->value) == QTYPE_QDICT ||
>> > +            qobject_type(entry->value) == QTYPE_QLIST) {
>> > +            error_setg(errp, "Value %s is not a scalar",
>> > +                       entry->key);
>> > +            goto error;
>> > +        }
>> > +
>> > +        qdict_split_flat_key(entry->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(entry->value);
>> > +            qdict_put_obj(qobject_to_qdict(child), suffix, entry->value);
>> > +        } else {
>> > +            if (child) {
>> > +                error_setg(errp, "Key %s prefix is already set as a dict",
>> > +                           prefix);
>> > +                goto error;
>> > +            }
>> > +            qobject_incref(entry->value);
>> > +            qdict_put_obj(two_level, prefix, entry->value);
>> > +        }
>> 
>> Works, because we put only QDicts we've created ourselves (first
>> qdict_put_obj() above) and values we got from @src (second
>> qdict_put_obj()), and we fail when such a value isn't scalar.
>> 
>> > +
>> > +        g_free(suffix);
>> 
>> As I suspected, qdict_split_flat_key() strdup'ing the suffix is useless.
>> 
>> > +        g_free(prefix);
>> > +        suffix = prefix = NULL;
>> 
>> Dead stores.
>
> No, they're not dead. The end of this method has a 'g_free(prefix)' so
> we must be sure to clear this out to prevent a double-free if a later
> codebase jumps to the error label.
>
>> > +        entry = next;
>> > +    }
>> > +
>> > +    /* Step 2: optionally process the two level dict recursively
>> > +     * into a multi-level dict */
>> > +    if (recursive) {
>> > +        multi_level = qdict_new();
>> > +        entry = qdict_first(two_level);
>> > +        while (entry != NULL) {
>> > +            next = qdict_next(two_level, entry);
>> 
>> Again, keep the loop control in one place.
>
> OK
>
>> 
>> > +
>> > +            if (qobject_type(entry->value) == QTYPE_QDICT) {
>> > +                child = qdict_crumple(qobject_to_qdict(entry->value),
>> > +                                      recursive, errp);
>> > +                if (!child) {
>> > +                    goto error;
>> > +                }
>> > +
>> > +                qdict_put_obj(multi_level, entry->key, child);
>> > +            } else {
>> > +                qobject_incref(entry->value);
>> > +                qdict_put_obj(multi_level, entry->key, entry->value);
>> > +            }
>> > +
>> > +            entry = next;
>> > +        }
>> > +        QDECREF(two_level);
>> > +    } else {
>> > +        multi_level = two_level;
>> > +    }
>> > +    two_level = NULL;
>> > +
>> > +    /* Step 3: detect if we need to turn our dict into list */
>> > +    list_len = qdict_list_size(multi_level, errp);
>> > +    if (list_len < 0) {
>> > +        goto error;
>> > +    }
>> > +
>> > +    if (list_len) {
>> > +        dst = QOBJECT(qlist_new());
>> > +
>> > +        for (i = 0; i < list_len; i++) {
>> > +            char *key = g_strdup_printf("%zu", i);
>> > +
>> > +            child = qdict_get(multi_level, key);
>> > +            g_free(key);
>> > +            assert(child);
>> 
>> qdict_list_size() accepts as list index any (string) key qemu_strtoll()
>> accepts.  If %zu formats it back into the same string, we'll find it
>> here.  Else we die.  Please spell this out in the function contract.
>
> OK.
>
>> [*] I'm afraid we also die if qdict_list_size()'s "List indexes are not
>> continuous" check gets fooled.  Suggest to drop that check, and replace
>> this assertion by error_setg(errp, "Malformed list indexes").
>> Admittedly not the nicest error message; perhaps you can come up with a
>> better one.
>
> We can't be fooled per my note earlier
>
>> 
>> > +
>> > +            qobject_incref(child);
>> > +            qlist_append_obj(qobject_to_qlist(dst), child);
>> > +        }
>> > +        QDECREF(multi_level);
>> 
>> Do we need
>> 
>>            multi_level = NULL;
>> 
>> here?
>
> It isn't needed right now, since we're at the end of the method now
> and nothing will touch this var again. Setting it to NULL is a
> worthwhile safety net for future refactoring though.

I generally don't bother to zap pointers "just in case".  I saw the
QDECREF() after the error label, and missed the fact that we can't reach
it from here.  Your patch is fine as is.

>> > +    } else {
>> > +        dst = QOBJECT(multi_level);
>> > +    }
>> > +
>> > +    return dst;
>> > +
>> > + error:
>> > +    g_free(suffix);
>> > +    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 a43056c..0d12f40 100644
>> > --- a/tests/check-qdict.c
>> > +++ b/tests/check-qdict.c
>> > @@ -15,6 +15,7 @@
>> >  #include "qapi/qmp/qint.h"
>> >  #include "qapi/qmp/qdict.h"
>> >  #include "qapi/qmp/qstring.h"
>> > +#include "qapi/error.h"
>> >  #include "qemu-common.h"
>
>> > +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);
>> 
>> Suggest to add test case
>> 
>>        /* List indexes must not have gaps (more creative version) */
>>        qdict_put(src, "rule.0", ...);
>>        qdict_put(src, "rule.2", ...);
>>        qdict_put(src, "rule.2", ...);
>
> That's surely impossible, as dict keys have to be unique.

It's surely possible that patch review melts my brain :)

>> and
>> 
>>        /* List indexes must be in %zu format */
>>        qdict_put(src, "rule.+0", ...);