Re: [Qemu-devel] [PATCH v14 02/21] qdict: implement a qdict_crumple method for un-flattening a dict

[Markus Armbruster <armbru@redhat.com>]

Max Reitz <mreitz@redhat.com> writes:

> On 21.10.2016 11:58, Markus Armbruster wrote:
>> "Daniel P. Berrange" <berrange@redhat.com> writes:
>> 
>>> On Tue, Oct 18, 2016 at 04:32:13PM +0200, Markus Armbruster wrote:
>>>> "Daniel P. Berrange" <berrange@redhat.com> 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.
>>>>>
>>>>> Reviewed-by: Eric Blake <eblake@redhat.com>
>>>>> Reviewed-by: Kevin Wolf <kwolf@redhat.com>
>>>>> Reviewed-by: Marc-André Lureau <marcandre.lureau@redhat.com>
>>>>> Signed-off-by: Daniel P. Berrange <berrange@redhat.com>
>>>>> ---
>>>>>  include/qapi/qmp/qdict.h |   1 +
>>>>>  qobject/qdict.c          | 289 +++++++++++++++++++++++++++++++++++++++++++++++
>>>>>  tests/check-qdict.c      | 261 ++++++++++++++++++++++++++++++++++++++++++
>>>>>  3 files changed, 551 insertions(+)
>>>>>
>>>>> diff --git a/include/qapi/qmp/qdict.h b/include/qapi/qmp/qdict.h
>>>>> index 71b8eb0..e0d24e1 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(const 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 60f158c..c38e90e 100644
>>>>> --- a/qobject/qdict.c
>>>>> +++ b/qobject/qdict.c
>>>> [...]
>>>>> +/**
>>>>> + * qdict_crumple:
>>>>> + * @src: the original flat dictionary (only scalar values) to crumple
>>>>> + * @recursive: true to recursively crumple nested dictionaries
>>>>
>>>> Is recursive=false used outside tests in this series?
>>>
>>> No, its not used.
>>>
>>> It was suggested in a way earlier version by Max, but not sure if his
>>> code uses it or not.
>> 
>> In general, I prefer features to be added right before they're used, and
>> I really dislike adding features "just in case".  YAGNI.
>> 
>> Max, do you actually need this one?  If yes, please explain your use
>> case.
>
> As far as I can tell from a quick glance, I made the point for v1 that
> qdict_crumple() could be simplified by using qdict_array_split() and
> qdict_array_entries().
>
> Dan then (correctly) said that using these functions would worsen
> runtime performance of qdict_crumple() and that instead we can replace
> qdict_array_split() by qdict_crumple(). However, for that to work, we
> need to be able to make qdict_crumple() non-recursive (because
> qdict_array_split() is non-recursive).
>
> Dan also said that in the long run we want to keep the tree structure in
> the block layer instead of flattening everything down which would rid us
> of several other QDict functions (and would make non-recursive behavior
> obsolete again). I believe that this is an idea for the (far?) future,
> as can be seen from the discussion you and others had on this very topic
> in this version here.
>
> However, clearly there are no patches out yet that replace
> qdict_array_split() by qdict_crumple(recursive=false), and I certainly
> won't write any until qdict_crumple() is merged.

I prefer not to maintain code that isn't actually used.  Since Dan is
enjoying a few days off, and the soft freeze is closing in, I'm
proposing to squash in the following:

* Drop @recursive, in the most straightforward way possible.

* Drop all tests that pass false to @recursive.  This might reduce
  coverage, but we can fix that on top.

* While there, collapse some vertical whitespace, for consistency with
  spacing elsewhere in the same files.

Resulting fixup patch appended.  I'd appreciate a quick look-over before
I do a pull request.  Current state at
http://repo.or.cz/w/qemu/armbru.git branch qapi-not-next.



>From df87de10a12bd65d2ddc47514e951712de7c06f0 Mon Sep 17 00:00:00 2001
From: Markus Armbruster <armbru@redhat.com>
Date: Tue, 25 Oct 2016 10:09:46 +0200
Subject: [PATCH] fixup! qdict: implement a qdict_crumple method for
 un-flattening a dict

---
 include/qapi/qmp/qdict.h |   2 +-
 qobject/qdict.c          |  42 ++++++---------
 tests/check-qdict.c      | 133 +++--------------------------------------------
 3 files changed, 23 insertions(+), 154 deletions(-)

diff --git a/include/qapi/qmp/qdict.h b/include/qapi/qmp/qdict.h
index e0d24e1..fe9a4c5 100644
--- a/include/qapi/qmp/qdict.h
+++ b/include/qapi/qmp/qdict.h
@@ -73,7 +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(const QDict *src, bool recursive, Error **errp);
+QObject *qdict_crumple(const QDict *src, Error **errp);
 
 void qdict_join(QDict *dest, QDict *src, bool overwrite);
 
diff --git a/qobject/qdict.c b/qobject/qdict.c
index c38e90e..197b0fb 100644
--- a/qobject/qdict.c
+++ b/qobject/qdict.c
@@ -684,7 +684,6 @@ void qdict_array_split(QDict *src, QList **dst)
     }
 }
 
-
 /**
  * qdict_split_flat_key:
  * @key: the key string to split
@@ -744,7 +743,6 @@ static void qdict_split_flat_key(const char *key, char **prefix,
     (*prefix)[j] = '\0';
 }
 
-
 /**
  * qdict_is_list:
  * @maybe_list: dict to check if keys represent list elements.
@@ -815,14 +813,10 @@ static int qdict_is_list(QDict *maybe_list, Error **errp)
 /**
  * qdict_crumple:
  * @src: the original flat dictionary (only scalar values) to crumple
- * @recursive: true to recursively crumple nested dictionaries
  *
  * Takes a flat dictionary whose keys use '.' separator to indicate
  * nesting, and values are scalars, and crumples it 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.
+ * structure.
  *
  * To include a literal '.' in a key name, it must be escaped as '..'
  *
@@ -855,7 +849,7 @@ static int qdict_is_list(QDict *maybe_list, Error **errp)
  * Returns: either a QDict or QList for the nested data structure, or NULL
  * on error
  */
-QObject *qdict_crumple(const QDict *src, bool recursive, Error **errp)
+QObject *qdict_crumple(const QDict *src, Error **errp)
 {
     const QDictEntry *ent;
     QDict *two_level, *multi_level = NULL;
@@ -908,28 +902,23 @@ QObject *qdict_crumple(const QDict *src, bool recursive, Error **errp)
 
     /* Step 2: optionally process the two level dict recursively
      * into a multi-level dict */
-    if (recursive) {
-        multi_level = qdict_new();
-        for (ent = qdict_first(two_level); ent != NULL;
-             ent = qdict_next(two_level, ent)) {
+    multi_level = qdict_new();
+    for (ent = qdict_first(two_level); ent != NULL;
+         ent = qdict_next(two_level, ent)) {
 
-            if (qobject_type(ent->value) == QTYPE_QDICT) {
-                child = qdict_crumple(qobject_to_qdict(ent->value),
-                                      recursive, errp);
-                if (!child) {
-                    goto error;
-                }
-
-                qdict_put_obj(multi_level, ent->key, child);
-            } else {
-                qobject_incref(ent->value);
-                qdict_put_obj(multi_level, ent->key, ent->value);
+        if (qobject_type(ent->value) == QTYPE_QDICT) {
+            child = qdict_crumple(qobject_to_qdict(ent->value), errp);
+            if (!child) {
+                goto error;
             }
+
+            qdict_put_obj(multi_level, ent->key, child);
+        } else {
+            qobject_incref(ent->value);
+            qdict_put_obj(multi_level, ent->key, ent->value);
         }
-        QDECREF(two_level);
-    } else {
-        multi_level = two_level;
     }
+    QDECREF(two_level);
     two_level = NULL;
 
     /* Step 3: detect if we need to turn our dict into list */
@@ -971,7 +960,6 @@ QObject *qdict_crumple(const QDict *src, bool recursive, Error **errp)
     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 64c33ab..07b1c79 100644
--- a/tests/check-qdict.c
+++ b/tests/check-qdict.c
@@ -413,7 +413,6 @@ static void qdict_array_split_test(void)
 
     QDECREF(test_dict);
 
-
     /*
      * Test the split of
      *
@@ -519,7 +518,6 @@ static void qdict_join_test(void)
     dict1 = qdict_new();
     dict2 = qdict_new();
 
-
     /* Test everything once without overwrite and once with */
     do
     {
@@ -529,7 +527,6 @@ static void qdict_join_test(void)
         g_assert(qdict_size(dict1) == 0);
         g_assert(qdict_size(dict2) == 0);
 
-
         /* First iteration: Test movement */
         /* Second iteration: Test empty source and non-empty destination */
         qdict_put(dict2, "foo", qint_from_int(42));
@@ -543,7 +540,6 @@ static void qdict_join_test(void)
             g_assert(qdict_get_int(dict1, "foo") == 42);
         }
 
-
         /* Test non-empty source and destination without conflict */
         qdict_put(dict2, "bar", qint_from_int(23));
 
@@ -555,7 +551,6 @@ static void qdict_join_test(void)
         g_assert(qdict_get_int(dict1, "foo") == 42);
         g_assert(qdict_get_int(dict1, "bar") == 23);
 
-
         /* Test conflict */
         qdict_put(dict2, "foo", qint_from_int(84));
 
@@ -571,7 +566,6 @@ static void qdict_join_test(void)
             g_assert(qdict_get_int(dict2, "foo") == 84);
         }
 
-
         /* Check the references */
         g_assert(qdict_get(dict1, "foo")->refcnt == 1);
         g_assert(qdict_get(dict1, "bar")->refcnt == 1);
@@ -580,7 +574,6 @@ static void qdict_join_test(void)
             g_assert(qdict_get(dict2, "foo")->refcnt == 1);
         }
 
-
         /* Clean up */
         qdict_del(dict1, "foo");
         qdict_del(dict1, "bar");
@@ -591,113 +584,10 @@ static void qdict_join_test(void)
     }
     while (overwrite ^= true);
 
-
     QDECREF(dict1);
     QDECREF(dict2);
 }
 
-
-static void qdict_crumple_test_nonrecursive(void)
-{
-    QDict *src, *dst, *rules, *vnc, *acl;
-    QObject *child, *res;
-
-    src = qdict_new();
-    qdict_put(src, "vnc.listen.addr", qstring_from_str("127.0.0.1"));
-    qdict_put(src, "vnc.listen.port", qstring_from_str("5901"));
-    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, "acl..name", qstring_from_str("acl0"));
-    qdict_put(src, "acl.rule..name", qstring_from_str("acl0"));
-
-    res = qdict_crumple(src, false, &error_abort);
-
-    g_assert_cmpint(qobject_type(res), ==, QTYPE_QDICT);
-
-    dst = qobject_to_qdict(res);
-
-    g_assert_cmpint(qdict_size(dst), ==, 4);
-
-    child = qdict_get(dst, "vnc");
-    g_assert_cmpint(qobject_type(child), ==, QTYPE_QDICT);
-    vnc = qdict_get_qdict(dst, "vnc");
-
-    g_assert_cmpint(qdict_size(vnc), ==, 2);
-
-    g_assert_cmpstr("127.0.0.1", ==, qdict_get_str(vnc, "listen.addr"));
-    g_assert_cmpstr("5901", ==, qdict_get_str(vnc, "listen.port"));
-
-    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"));
-
-    /* With non-recursive crumpling, we should only see the first
-     * level names unescaped */
-    g_assert_cmpstr("acl0", ==, qdict_get_str(dst, "acl.name"));
-    child = qdict_get(dst, "acl");
-    g_assert_cmpint(qobject_type(child), ==, QTYPE_QDICT);
-    acl = qdict_get_qdict(dst, "acl");
-    g_assert_cmpstr("acl0", ==, qdict_get_str(acl, "rule..name"));
-
-    QDECREF(src);
-    QDECREF(dst);
-}
-
-
-static void qdict_crumple_test_listtop(void)
-{
-    QDict *src, *rule;
-    QList *rules;
-    QObject *res;
-
-    src = qdict_new();
-    qdict_put(src, "0.match.name", qstring_from_str("Fred"));
-    qdict_put(src, "0.match.email", qstring_from_str("fred@example.com"));
-    qdict_put(src, "0.policy", qstring_from_str("allow"));
-    qdict_put(src, "1.match.name", qstring_from_str("Bob"));
-    qdict_put(src, "1.match.email", qstring_from_str("bob@example.com"));
-    qdict_put(src, "1.policy", qstring_from_str("deny"));
-
-    res = qdict_crumple(src, false, &error_abort);
-
-    g_assert_cmpint(qobject_type(res), ==, QTYPE_QLIST);
-
-    rules = qobject_to_qlist(res);
-
-    g_assert_cmpint(qlist_size(rules), ==, 2);
-
-    g_assert_cmpint(qobject_type(qlist_peek(rules)), ==, QTYPE_QDICT);
-    rule = qobject_to_qdict(qlist_pop(rules));
-    g_assert_cmpint(qdict_size(rule), ==, 3);
-
-    g_assert_cmpstr("Fred", ==, qdict_get_str(rule, "match.name"));
-    g_assert_cmpstr("fred@example.com", ==, qdict_get_str(rule, "match.email"));
-    g_assert_cmpstr("allow", ==, qdict_get_str(rule, "policy"));
-    QDECREF(rule);
-
-    g_assert_cmpint(qobject_type(qlist_peek(rules)), ==, QTYPE_QDICT);
-    rule = qobject_to_qdict(qlist_pop(rules));
-    g_assert_cmpint(qdict_size(rule), ==, 3);
-
-    g_assert_cmpstr("Bob", ==, qdict_get_str(rule, "match.name"));
-    g_assert_cmpstr("bob@example.com", ==, qdict_get_str(rule, "match.email"));
-    g_assert_cmpstr("deny", ==, qdict_get_str(rule, "policy"));
-    QDECREF(rule);
-
-    QDECREF(src);
-    qobject_decref(res);
-}
-
-
 static void qdict_crumple_test_recursive(void)
 {
     QDict *src, *dst, *rule, *vnc, *acl, *listen;
@@ -715,7 +605,7 @@ static void qdict_crumple_test_recursive(void)
     qdict_put(src, "vnc.acl..name", qstring_from_str("acl0"));
     qdict_put(src, "vnc.acl.rule..name", qstring_from_str("acl0"));
 
-    res = qdict_crumple(src, true, &error_abort);
+    res = qdict_crumple(src, &error_abort);
 
     g_assert_cmpint(qobject_type(res), ==, QTYPE_QDICT);
 
@@ -765,14 +655,13 @@ static void qdict_crumple_test_recursive(void)
     QDECREF(dst);
 }
 
-
 static void qdict_crumple_test_empty(void)
 {
     QDict *src, *dst;
 
     src = qdict_new();
 
-    dst = (QDict *)qdict_crumple(src, true, &error_abort);
+    dst = (QDict *)qdict_crumple(src, &error_abort);
 
     g_assert_cmpint(qdict_size(dst), ==, 0);
 
@@ -780,7 +669,6 @@ static void qdict_crumple_test_empty(void)
     QDECREF(dst);
 }
 
-
 static void qdict_crumple_test_bad_inputs(void)
 {
     QDict *src;
@@ -791,7 +679,7 @@ static void qdict_crumple_test_bad_inputs(void)
     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(qdict_crumple(src, &error) == NULL);
     g_assert(error != NULL);
     error_free(error);
     error = NULL;
@@ -802,7 +690,7 @@ static void qdict_crumple_test_bad_inputs(void)
     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(qdict_crumple(src, &error) == NULL);
     g_assert(error != NULL);
     error_free(error);
     error = NULL;
@@ -813,38 +701,35 @@ static void qdict_crumple_test_bad_inputs(void)
     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(qdict_crumple(src, &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", qstring_from_str("deny"));
     qdict_put(src, "rule.3", qstring_from_str("allow"));
 
-    g_assert(qdict_crumple(src, true, &error) == NULL);
+    g_assert(qdict_crumple(src, &error) == NULL);
     g_assert(error != NULL);
     error_free(error);
     error = NULL;
     QDECREF(src);
 
-
     src = qdict_new();
     /* List indexes must be in %zu format */
     qdict_put(src, "rule.0", qstring_from_str("deny"));
     qdict_put(src, "rule.+1", qstring_from_str("allow"));
 
-    g_assert(qdict_crumple(src, true, &error) == NULL);
+    g_assert(qdict_crumple(src, &error) == NULL);
     g_assert(error != NULL);
     error_free(error);
     error = NULL;
     QDECREF(src);
 }
 
-
 /*
  * Errors test-cases
  */
@@ -992,12 +877,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/nonrecursive",
-                    qdict_crumple_test_nonrecursive);
     g_test_add_func("/public/crumple/recursive",
                     qdict_crumple_test_recursive);
-    g_test_add_func("/public/crumple/listtop",
-                    qdict_crumple_test_listtop);
     g_test_add_func("/public/crumple/empty",
                     qdict_crumple_test_empty);
     g_test_add_func("/public/crumple/bad_inputs",
-- 
2.5.5