[v2,01/10] qdict: implement a qdict_crumple method for un-flattening a dict

Commit Message

Daniel P. Berrangé March 7, 2016, 3:43 p.m. UTC

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 <[e-mail]>
---
 include/qapi/qmp/qdict.h |   1 +
 qobject/qdict.c          | 237 +++++++++++++++++++++++++++++++++++++++++++++++
 tests/check-qdict.c      | 114 +++++++++++++++++++++++
 3 files changed, 352 insertions(+)

Comments

Max Reitz March 7, 2016, 5:23 p.m. UTC | #1

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 <[e-mail]>
> ---
>  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.

> diff --git a/include/qapi/qmp/qdict.h b/include/qapi/qmp/qdict.h
> index 71b8eb0..8a3ac13 100644
> --- a/include/qapi/qmp/qdict.h
> +++ b/include/qapi/qmp/qdict.h
> @@ -73,6 +73,7 @@ void qdict_flatten(QDict *qdict);
>  void qdict_extract_subqdict(QDict *src, QDict **dst, const char *start);
>  void qdict_array_split(QDict *src, QList **dst);
>  int qdict_array_entries(QDict *src, const char *subqdict);
> +QObject *qdict_crumple(QDict *src, bool recursive, Error **errp);
>  
>  void qdict_join(QDict *dest, QDict *src, bool overwrite);
>  
> diff --git a/qobject/qdict.c b/qobject/qdict.c
> index 9833bd0..b0f3447 100644
> --- a/qobject/qdict.c
> +++ b/qobject/qdict.c
> @@ -682,6 +682,243 @@ void qdict_array_split(QDict *src, QList **dst)
>      }
>  }
>  
> +
> +/**
> + * qdict_split_flat_key:
> + *
> + * 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.
> + */
> +static void qdict_split_flat_key(const char *key, char **prefix, 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);
> +        *suffix = g_strdup(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] == '.' &&
> +            (*prefix)[i + 1] == '.') {
> +            i++;
> +        }
> +        (*prefix)[j] = (*prefix)[i];
> +    }
> +    (*prefix)[j] = '\0';
> +}
> +
> +
> +/**
> + * qdict_crumple:
> + *
> + * Reverses the flattening done by qdict_flatten by
> + * crumpling the dicts into a nested structure. Similar
> + * qdict_array_split, but copes with arbitrary nesting
> + * of dicts & arrays, not meely one level of arrays

s/meely/merely/

> + *
> + * { 'foo.0.bar': 'one', 'foo.0.wizz': '1',
> + *   'foo.1.bar': 'two', 'foo.1.wizz': '2' }
> + *
> + * =>
> + *
> + * {
> + *   'foo' => [
> + *      { 'bar': 'one', 'wizz': '1' }
> + *      { 'bar': 'two', 'wizz': '2' }
> + *   ],
> + * }
> + *
> + */
> +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...

> +
> +    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()).

> +                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);
> +        }
> +
> +        g_free(suffix);
> +        g_free(prefix);
> +        suffix = prefix = NULL;
> +
> +        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);
> +
> +            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 */
> +    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.

> +        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.

> +                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).

> +                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.)

> +
> +    /* 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.

> +        }
> +    }
> +    QDECREF(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..20aa1af 100644
> --- a/tests/check-qdict.c
> +++ b/tests/check-qdict.c
> @@ -596,6 +596,113 @@ static void qdict_join_test(void)
>      QDECREF(dict2);
>  }
>  
> +
> +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);

Max

> +}
> +
> +
> +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.0", qdict_new());
> +    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);
> +}
> +
>  /*
>   * Errors test-cases
>   */
> @@ -743,6 +850,13 @@ int main(int argc, char **argv)
>      g_test_add_func("/errors/put_exists", qdict_put_exists_test);
>      g_test_add_func("/errors/get_not_exists", qdict_get_not_exists_test);
>  
> +    g_test_add_func("/public/crumple/nonrecursive",
> +                    qdict_crumple_test_nonrecursive);
> +    g_test_add_func("/public/crumple/recursive",
> +                    qdict_crumple_test_recursive);
> +    g_test_add_func("/public/crumple/bad_inputs",
> +                    qdict_crumple_test_bad_inputs);
> +
>      /* The Big one */
>      if (g_test_slow()) {
>          g_test_add_func("/stress/test", qdict_stress_test);
>

Daniel P. Berrangé March 9, 2016, 6:07 p.m. UTC | #2

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 <[e-mail]>
> > ---
> >  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

Max Reitz March 9, 2016, 6:16 p.m. UTC | #3

On 09.03.2016 19:07, Daniel P. Berrange wrote:
> On Mon, Mar 07, 2016 at 06:23:35PM +0100, Max Reitz wrote:
>> On 07.03.2016 16:43, Daniel P. Berrange wrote:

[...]

>>> +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.

Oops, right. :-)

I suppose it looked so tempting to me because of the QDECREF(rule) for
the pop'ed rules.

Max

Patch

diff --git a/include/qapi/qmp/qdict.h b/include/qapi/qmp/qdict.h
index 71b8eb0..8a3ac13 100644
--- a/include/qapi/qmp/qdict.h
+++ b/include/qapi/qmp/qdict.h
@@ -73,6 +73,7 @@  void qdict_flatten(QDict *qdict);
 void qdict_extract_subqdict(QDict *src, QDict **dst, const char *start);
 void qdict_array_split(QDict *src, QList **dst);
 int qdict_array_entries(QDict *src, const char *subqdict);
+QObject *qdict_crumple(QDict *src, bool recursive, Error **errp);
 
 void qdict_join(QDict *dest, QDict *src, bool overwrite);
 
diff --git a/qobject/qdict.c b/qobject/qdict.c
index 9833bd0..b0f3447 100644
--- a/qobject/qdict.c
+++ b/qobject/qdict.c
@@ -682,6 +682,243 @@  void qdict_array_split(QDict *src, QList **dst)
     }
 }
 
+
+/**
+ * qdict_split_flat_key:
+ *
+ * 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.
+ */
+static void qdict_split_flat_key(const char *key, char **prefix, 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);
+        *suffix = g_strdup(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] == '.' &&
+            (*prefix)[i + 1] == '.') {
+            i++;
+        }
+        (*prefix)[j] = (*prefix)[i];
+    }
+    (*prefix)[j] = '\0';
+}
+
+
+/**
+ * qdict_crumple:
+ *
+ * Reverses the flattening done by qdict_flatten by
+ * crumpling the dicts into a nested structure. Similar
+ * qdict_array_split, but copes with arbitrary nesting
+ * of dicts & arrays, not meely one level of arrays
+ *
+ * { 'foo.0.bar': 'one', 'foo.0.wizz': '1',
+ *   'foo.1.bar': 'two', 'foo.1.wizz': '2' }
+ *
+ * =>
+ *
+ * {
+ *   'foo' => [
+ *      { 'bar': 'one', 'wizz': '1' }
+ *      { 'bar': 'two', 'wizz': '2' }
+ *   ],
+ * }
+ *
+ */
+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;
+    ssize_t list_max = -1;
+    size_t list_len = 0;
+    size_t i;
+    int64_t val;
+    char *prefix, *suffix;
+
+    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;
+        }
+
+        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);
+        }
+
+        g_free(suffix);
+        g_free(prefix);
+        suffix = prefix = NULL;
+
+        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);
+
+            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 */
+    entry = qdict_first(multi_level);
+    while (entry != NULL) {
+        next = qdict_next(multi_level, 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;
+            }
+            list_len++;
+            if (val > list_max) {
+                list_max = val;
+            }
+        } else {
+            if (!dst) {
+                dst = (QObject *)multi_level;
+                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 */
+    if (isList) {
+        if (list_len != (list_max + 1)) {
+            error_setg(errp, "List indexes are not continuous, "
+                       "saw %zu elements but %zu largest index",
+                       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;
+            }
+
+            qobject_incref(child);
+            qlist_append_obj((QList *)dst, child);
+        }
+    }
+    QDECREF(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..20aa1af 100644
--- a/tests/check-qdict.c
+++ b/tests/check-qdict.c
@@ -596,6 +596,113 @@  static void qdict_join_test(void)
     QDECREF(dict2);
 }
 
+
+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);
+
+    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_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_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_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_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.0", qdict_new());
+    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);
+}
+
 /*
  * Errors test-cases
  */
@@ -743,6 +850,13 @@  int main(int argc, char **argv)
     g_test_add_func("/errors/put_exists", qdict_put_exists_test);
     g_test_add_func("/errors/get_not_exists", qdict_get_not_exists_test);
 
+    g_test_add_func("/public/crumple/nonrecursive",
+                    qdict_crumple_test_nonrecursive);
+    g_test_add_func("/public/crumple/recursive",
+                    qdict_crumple_test_recursive);
+    g_test_add_func("/public/crumple/bad_inputs",
+                    qdict_crumple_test_bad_inputs);
+
     /* The Big one */
     if (g_test_slow()) {
         g_test_add_func("/stress/test", qdict_stress_test);