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

["Daniel P. Berrange" <berrange@redhat.com>]

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 <berrange@redhat.com>
---
 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;
@@ -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;
+    size_t i, j;
+    int64_t val;
+    char *key;
+
+    tmp1 = qdict_new();
+    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;
+        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';
+
+        if (p) {
+            tmp2 = qdict_get_qdict(tmp1, key);
+            p++;
+            if (!tmp2) {
+                tmp2 = qdict_new();
+                qdict_put(tmp1, key, tmp2);
+            }
+            qdict_put_obj(tmp2, p, entry->value);
+        } else {
+            qdict_put_obj(tmp1, key, entry->value);
+        }
+
+        entry = next;
+    }
+
+    /* Step 2: crumple the new dicts we just created */
+    tmp2 = qdict_new();
+    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);
+            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 */
+    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 */
+    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);
-- 
2.5.0