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

[Max Reitz]

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(+)
> 
> diff --git a/include/qapi/qmp/qdict.h b/include/qapi/qmp/qdict.h
> index 6c2a0e5..baf45d5 100644
> --- a/include/qapi/qmp/qdict.h
> +++ b/include/qapi/qmp/qdict.h
> @@ -75,6 +75,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, Error **errp);
>  
>  void qdict_join(QDict *dest, QDict *src, bool overwrite);
>  
> diff --git a/qobject/qdict.c b/qobject/qdict.c
> index 9833bd0..ff4caf8 100644
> --- a/qobject/qdict.c
> +++ b/qobject/qdict.c
> @@ -608,6 +608,7 @@ void qdict_extract_subqdict(QDict *src, QDict **dst, 
> const char *start)
>      }
>  }
>  
> +
>  static int qdict_count_prefixed_entries(const QDict *src, const char *start)
>  {
>      const QDictEntry *entry;

This hunk seems unintended.

> @@ -682,6 +683,185 @@ void qdict_array_split(QDict *src, QList **dst)
>      }
>  }
>  
> +
> +/**
> + * 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, 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.

> +    size_t i, j;
> +    int64_t val;
> +    char *key;
> +
> +    tmp1 = qdict_new();

I guess I'd like clearer variable names.

> +    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"?

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

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

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

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

> +    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);?

Max

> +    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;
> +}
> +
> +
>  /**
>   * 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..fb8184c 100644
> --- a/tests/check-qdict.c
> +++ b/tests/check-qdict.c
> @@ -596,6 +596,43 @@ static void qdict_join_test(void)
>      QDECREF(dict2);
>  }
>  
> +
> +static void qdict_crumple_test(void)
> +{
> +    QDict *src, *dst, *rule, *eek;
> +    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"));
> +    qdict_put(src, "foo..bar", qstring_from_str("wibble"));
> +    qdict_put(src, "eek.foo..bar", qstring_from_str("wizz"));
> +
> +    dst = (QDict *)qdict_crumple(src, &error_abort);
> +
> +    g_assert_cmpint(qdict_size(dst), ==, 3);
> +
> +    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"));
> +
> +    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"));
> +
> +    g_assert_cmpstr("wibble", ==, qdict_get_str(dst, "foo.bar"));
> +
> +    eek = qdict_get_qdict(dst, "eek");
> +    g_assert_cmpstr("wizz", ==, qdict_get_str(eek, "foo.bar"));
> +}
> +
> +
>  /*
>   * Errors test-cases
>   */
> @@ -743,6 +780,8 @@ 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", qdict_crumple_test);
> +
>      /* The Big one */
>      if (g_test_slow()) {
>          g_test_add_func("/stress/test", qdict_stress_test);
>

signature.asc
Description: OpenPGP digital signature