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

[Daniel P. Berrange]

On Wed, Mar 02, 2016 at 05:13:59PM +0100, Max Reitz wrote:
> On 19.02.2016 17:47, 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 todo 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          | 180 
> > +++++++++++++++++++++++++++++++++++++++++++++++
> >  tests/check-qdict.c      |  39 ++++++++++
> >  3 files changed, 220 insertions(+)
> > 

> > +QObject *qdict_crumple(QDict *src, Error **errp)
> > +{
> > +    const QDictEntry *entry, *next;
> > +    const char *p = NULL;
> > +    QDict *tmp1 = NULL, *tmp2 = NULL;
> > +    QObject *dst = NULL, *child;
> > +    bool isList = false;
> > +    ssize_t listMax = -1;
> > +    size_t listLen = 0;
> 
> As far as I'm aware we don't have any strict policy on names, but in
> general structs use UpperCamelCase and variables and functions use
> c_style_naming.

Yep, ok

> > +    size_t i, j;
> > +    int64_t val;
> > +    char *key;
> > +
> > +    tmp1 = qdict_new();
> 
> I guess I'd like clearer variable names.

Sure

> 
> > +    entry = qdict_first(src);
> > +
> > +    /* Step 1: extract everything as nested dicts */
> > +    while (entry != NULL) {
> > +        next = qdict_next(src, entry);
> > +        qobject_incref(entry->value);
> > +
> > +        /* Find first '.' separator, but treat '..' as
> > +         * an escape sequence */
> > +        p = NULL;
> 
> How about at least "dot" or "separator"?

Sure.

> > +        do {
> > +            if (p) {
> > +                p += 2;
> > +            } else {
> > +                p = entry->key;
> > +            }
> > +            p = strchr(p, '.');
> > +        } while (p && *(p + 1) == '.');
> > +
> > +        if (p) {
> > +            key = g_strndup(entry->key,
> > +                            p - entry->key);
> > +        } else {
> > +            key = g_strdup(entry->key);
> > +        }
> > +
> > +        for (i = 0, j = 0; key[i] != '\0'; i++, j++) {
> > +            if (key[i] == '.' &&
> > +                key[i + 1] == '.') {
> > +                i++;
> > +            }
> > +            key[j] = key[i];
> > +        }
> > +        key[j] = '\0';
> 
> I general I think it would be nice to put this escaping code into an own
> static function which returns a strdup'd key for the QDict and this
> entry's key in that QDict.

Yep, good idea.

> 
> > +
> > +        if (p) {
> > +            tmp2 = qdict_get_qdict(tmp1, key);
> > +            p++;
> > +            if (!tmp2) {
> > +                tmp2 = qdict_new();
> > +                qdict_put(tmp1, key, tmp2);
> 
> This...
> 
> > +            }
> > +            qdict_put_obj(tmp2, p, entry->value);
> > +        } else {
> > +            qdict_put_obj(tmp1, key, entry->value);
> 
> ...and this may silently overwrite entries, e.g. when crumpling
> 
> { "x": 42, "x.y": 23 }
> 
> > +        }
> 
> key is leaked.

Oh that should result in an error being raised as it is
a contradictory input.

> > +
> > +        entry = next;
> > +    }
> > +
> > +    /* Step 2: crumple the new dicts we just created */
> > +    tmp2 = qdict_new();
> 
> Please use more variables with clearer names.
> 
> > +    entry = qdict_first(tmp1);
> > +    while (entry != NULL) {
> > +        next = qdict_next(tmp1, entry);
> > +
> > +        if (qobject_type(entry->value) == QTYPE_QDICT) {
> > +            child = qdict_crumple((QDict *)entry->value, errp);
> 
> The cast works, but I'd prefer qobject_to_qdict() nonetheless.

Ok

> 
> > +            if (!child) {
> > +                goto error;
> > +            }
> > +
> > +            qdict_put_obj(tmp2, entry->key, child);
> > +        } else {
> > +            qobject_incref(entry->value);
> > +            qdict_put_obj(tmp2, entry->key, entry->value);
> > +        }
> > +
> > +        entry = next;
> > +    }
> > +    QDECREF(tmp1);
> > +
> > +    /* Step 3: detect if we need to turn our dict into list */
> 
> You could use qdict_array_entries(tmp2, "") > 0 for this.
> 
> If you do want to make { "0": 42, "2": 23 } and { "0": 42, "x": 23 }
> errors (my qdict_unflatten() just kept those QDicts), then you'd have to
> check on qdict_array_entries() error whether the QDict contained an
> integer key, but that would still be simpler than the following loop and
> the check in step 4.

If I use qdict_array_entries() then it does 2 O(N) iterations
of the input qdict, and to check the errors, I'll have todo
yet another iteration.  My inlined code here does everything
in a single O(N) iteration instead of 3. I think that's
compelling enough to reason to not use that function.



> > +    entry = qdict_first(tmp2);
> > +    while (entry != NULL) {
> > +        next = qdict_next(tmp2, entry);
> > +
> > +        errno = 0;
> > +        if (qemu_strtoll(entry->key, NULL, 10, &val) == 0) {
> > +            if (!dst) {
> > +                dst = (QObject *)qlist_new();
> > +                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;
> > +            }
> > +            listLen++;
> > +            if (val > listMax) {
> > +                listMax = val;
> > +            }
> > +        } else {
> > +            if (!dst) {
> > +                dst = (QObject *)tmp2;
> > +                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;
> > +    }
> > +
> > +    /* Step 4: Turn the dict into a list */
> 
> Why not just use qdict_array_split(tmp2, &dst);?

Again qdict_array_split() is a pretty inefficiently written
function. It does multiple nested iterations over its input
giving it O(n^2) time, compared to O(n) for my code here.


The only user of qdict_array_entries() and qdict_array_split()
is the block quorum driver. From a brief look at that code
I think it could probably be changed to just call this new
qdict_crumple() method, and those 2 inefficient functions
could be deleted, so we don't have duplication of code.

> > +    if (isList) {
> > +        if (listLen != (listMax + 1)) {
> > +            error_setg(errp, "List indexes are not continuous, "
> > +                       "saw %zu elements but %zu largest index",
> > +                       listLen, listMax);
> > +            goto error;
> > +        }
> > +
> > +        for (i = 0; i < listLen; i++) {
> > +            char *key = g_strdup_printf("%zu", i);
> > +
> > +            child = qdict_get(tmp2, key);
> > +            g_free(key);
> > +            if (!child) {
> > +                error_setg(errp, "Unexpected missing list entry %zu", i);
> > +                goto error;
> > +            }
> > +
> > +            qobject_incref(child);
> > +            qlist_append_obj((QList *)dst, child);
> > +        }
> > +    }
> > +    QDECREF(tmp2);
> > +
> > +    return dst;
> > +
> > + error:
> > +    QDECREF(tmp2);
> > +    QDECREF(tmp1);
> > +    qobject_decref(dst);
> > +    return NULL;
> > +}
> > +
> > +

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