Re: [Qemu-devel] [PATCH v2 01/10] qdict: implement a qdict_crumple method for un-flattening a dict

[Daniel P. Berrange]

On Mon, Mar 07, 2016 at 06:23:35PM +0100, Max Reitz wrote:
> On 07.03.2016 16:43, Daniel P. Berrange 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 nested
> > used when the same object is defined over QMP.
> > 
> > Signed-off-by: Daniel P. Berrange <address@hidden>
> > ---
> >  include/qapi/qmp/qdict.h |   1 +
> >  qobject/qdict.c          | 237 
> > +++++++++++++++++++++++++++++++++++++++++++++++
> >  tests/check-qdict.c      | 114 +++++++++++++++++++++++
> >  3 files changed, 352 insertions(+)
> 
> Under the assumption that we are going to replace qdict_array_split()
> with this function later on: Looks good overall, some comments below,
> the biggest of which regarding design is me nagging again how nice step
> 3 could be as an own function.
> 

> > +QObject *qdict_crumple(QDict *src, bool recursive, Error **errp)
> > +{
> > +    const QDictEntry *entry, *next;
> > +    QDict *two_level, *multi_level = NULL;
> > +    QObject *dst = NULL, *child;
> > +    bool isList = false;
> 
> *cough* :-)
> 
> > +    ssize_t list_max = -1;
> > +    size_t list_len = 0;
> > +    size_t i;
> > +    int64_t val;
> > +    char *prefix, *suffix;
> 
> These should be initialized to NULL...

Opps, yes.

> > +    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);
> > +
> > +        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;
> 
> ...otherwise this might result in uninitialized values being passed to
> g_free() in the error path.
> 
> > +        }
> > +
> > +        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();
> 
> Works, but I'd prefer QOBJECT(qdict_new()).

Ok.


> > +    /* Step 3: detect if we need to turn our dict into list */
> > +    entry = qdict_first(multi_level);
> > +    while (entry != NULL) {
> > +        next = qdict_next(multi_level, entry);
> > +
> > +        errno = 0;
> 
> This appears unnecessary to me, qemu_strtoll() works fine without.

Left over from when i used bare strtoll.

> > +        if (qemu_strtoll(entry->key, NULL, 10, &val) == 0) {
> > +            if (!dst) {
> > +                dst = (QObject *)qlist_new();
> 
> Again, works just fine, but QOBJECT(qlist_new()) would be nicer.

Ok

> > +                isList = true;
> > +            } else if (!isList) {
> > +                error_setg(errp,
> > +                           "Key '%s' is for a list, but previous key is "
> > +                           "for a dict", entry->key);
> > +                goto error;
> > +            }
> > +            list_len++;
> > +            if (val > list_max) {
> > +                list_max = val;
> > +            }
> > +        } else {
> > +            if (!dst) {
> > +                dst = (QObject *)multi_level;
> 
> Similarly, QOBJECT(multi_level).

Ok.

> > +                qobject_incref(dst);
> > +                isList = false;
> > +            } else if (isList) {
> > +                error_setg(errp,
> > +                           "Key '%s' is for a dict, but previous key is "
> > +                           "for a list", entry->key);
> > +                goto error;
> > +            }
> > +        }
> > +
> > +        entry = next;
> > +    }
> 
> If the QDict is empty, dst will be NULL and this function will return
> NULL. Though nothing is leaked, is this intended behavior?
> 
> If not, I think it would be a bit simpler if the loop just yielded
> is_list being true or false, and then dst is set afterwards. For this to
> work, inside the loop we'd simply need to know whether we are in the
> first iteration or not (is_list may be changed in the first iteration only).
> 
> Pulling out the setting of dst would be a nice side-effect (IMO).
> 
> (And, again, I think this decision of whether the QDict should be made a
> QList or not can be put really nicely into a dedicated function. Besides
> that boolean, it only needs to return the list_size (actually, it could
> just return the list_size and a size of 0 means it should stay a QDict).
> The test whether list_len != list_max + 1 can be done inside of that
> function, too.)

Yes, I have split the code out now and it is nicer like that. I also
added a test for the empty dict case.

> > +
> > +    /* Step 4: Turn the dict into a list */
> > +    if (isList) {
> > +        if (list_len != (list_max + 1)) {
> > +            error_setg(errp, "List indexes are not continuous, "
> > +                       "saw %zu elements but %zu largest index",
> 
> The second should be %zi or %zd (unfortunately, as I have been told,
> some systems have sizeof(size_t) != sizeof(ssize_t)).
> 
> > +                       list_len, list_max);
> > +            goto error;
> > +        }
> > +
> > +        for (i = 0; i < list_len; i++) {
> > +            char *key = g_strdup_printf("%zu", i);
> > +
> > +            child = qdict_get(multi_level, key);
> > +            g_free(key);
> > +            if (!child) {
> > +                error_setg(errp, "Unexpected missing list entry %zu", i);
> > +                goto error;
> > +            }
> 
> Could be made an assert(child);, but doesn't need to be, of course.
> 
> > +
> > +            qobject_incref(child);
> > +            qlist_append_obj((QList *)dst, child);
> 
> As with the (QObject *) casts, qobject_to_qlist(dst) would be nicer.

Ok


> > +static void qdict_crumple_test_nonrecursive(void)
> > +{
> > +    QDict *src, *dst, *rules;
> > +    QObject *child;
> > +
> > +    src = qdict_new();
> > +    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"));
> > +
> > +    dst = (QDict *)qdict_crumple(src, false, &error_abort);
> 
> It's a test, so anything is fine that works, but still... :-)
> 
> > +
> > +    g_assert_cmpint(qdict_size(dst), ==, 1);
> > +
> > +    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_recursive(void)
> > +{
> > +    QDict *src, *dst, *rule;
> > +    QObject *child;
> > +    QList *rules;
> > +
> > +    src = qdict_new();
> > +    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"));
> > +
> > +    dst = (QDict *)qdict_crumple(src, true, &error_abort);
> > +
> > +    g_assert_cmpint(qdict_size(dst), ==, 1);
> > +
> > +    child = qdict_get(dst, "rule");
> > +    g_assert_cmpint(qobject_type(child), ==, QTYPE_QLIST);
> > +
> > +    rules = qdict_get_qlist(dst, "rule");
> > +    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);
> 
> QDECREF(rules);

rules is a borrowed reference, so we can't decrement it.


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 :|