[Qemu-block] [PATCH v2 02/16] qdict: Add qdict_unflatten()

[Max Reitz]

The QMP input visitor is rather unhappy with flattened QDicts, which is
how they are generally used in the block layer. This function allows
unflattening a QDict so we can use an input visitor on it.

Signed-off-by: Max Reitz <address@hidden>
---
 include/qapi/qmp/qdict.h |   1 +
 qobject/qdict.c          | 189 +++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 190 insertions(+)

diff --git a/include/qapi/qmp/qdict.h b/include/qapi/qmp/qdict.h
index 223f746..0ec7477 100644
--- a/include/qapi/qmp/qdict.h
+++ b/include/qapi/qmp/qdict.h
@@ -70,6 +70,7 @@ void qdict_set_default_str(QDict *dst, const char *key, const 
char *val);
 
 QDict *qdict_clone_shallow(const QDict *src);
 void qdict_flatten(QDict *qdict);
+bool qdict_unflatten(QDict *qdict, Error **errp);
 
 void qdict_extract_subqdict(QDict *src, QDict **dst, const char *start);
 void qdict_array_split(QDict *src, QList **dst);
diff --git a/qobject/qdict.c b/qobject/qdict.c
index bbfe39f..800af38 100644
--- a/qobject/qdict.c
+++ b/qobject/qdict.c
@@ -771,6 +771,195 @@ int qdict_array_entries(QDict *src, const char *subqdict)
 }
 
 /**
+ * qlist_unflatten(): Recursive helper function for qdict_unflatten(). Invokes
+ * qdict_unflatten() and qlist_unflatten() on all its QDict and QList members,
+ * respectively.
+ */
+static bool qlist_unflatten(QList *qlist, Error **errp)
+{
+    const QListEntry *entry;
+
+    for (entry = qlist_first(qlist); entry; entry = qlist_next(entry)) {
+        switch (qobject_type(entry->value)) {
+        case QTYPE_QDICT:
+            if (!qdict_unflatten(qobject_to_qdict(entry->value), errp)) {
+                return false;
+            }
+            break;
+
+        case QTYPE_QLIST:
+            if (!qlist_unflatten(qobject_to_qlist(entry->value), errp)) {
+                return false;
+            }
+            break;
+
+        default:
+            break;
+        }
+    }
+
+    return true;
+}
+
+/**
+ * qdict_unflatten(): The opposite of qdict_flatten().
+ *
+ * Every entry whose key is of the form "${prefix}.${index}" is moved to index
+ * "${index}" in a QList whose key in @qdict is "${prefix}", if
+ * qdict_array_entries(qdict, "${prefix}.") yields a positive value.
+ *
+ * Every entry whose key is of the form "${prefix}.${index}.${trailing}" is
+ * moved into a QDict at index "${index}" in a QList whose key in @qdict is
+ * "${prefix}". The moved object's key in the nested QDict is "${trailing}".
+ * This is only done if qdict_array_entries(qdict, "${prefix}.") yields a
+ * positive value.
+ *
+ * Every remaining entry whose key is of the form "${prefix}.${trailing}" is
+ * moved into a QDict whose key in @qdict is "${prefix}". The moved object's 
key
+ * in the nested QDict is "${trailing}".
+ *
+ * This algorithm then recurses on all QDict members (including indirect ones
+ * in QLists) of this QDict.
+ *
+ * This function will never overwrite existing members. For instance:
+ *   qdict_unflatten({ "x": 42, "x.y": 23 })
+ * is an error because there already is an "x" element which is not a QDict.
+ * However,
+ *   qdict_unflatten({ "x": { "a": 0 }, "x.y": 23 })
+ *   => { "x": { "a": 0, "y": 23 } }
+ * because the flattened "x.y" can be merged into the existing "x" QDict 
without
+ * overwriting any of its members. In contrast to that,
+ *   qdict_unflatten({ "x": { "y": 0 }, "x.y": 23 })
+ * is an error because "y" nested in "x" would need to be overwritten.
+ *
+ * This function returns true on success and false on error (in which case 
*errp
+ * is set). On error, the contents of @qdict are undefined.
+ */
+bool qdict_unflatten(QDict *qdict, Error **errp)
+{
+    const QDictEntry *entry;
+
+    /* First pass: Unflatten this level */
+    entry = qdict_first(qdict);
+    while (entry) {
+        const char *prefix_end = strchr(entry->key, '.');
+
+        if (prefix_end) {
+            size_t prefix_length = prefix_end - entry->key;
+            char *prefix, *prefix_dot;
+
+            prefix = g_malloc(prefix_length + 1);
+            strncpy(prefix, entry->key, prefix_length);
+            prefix[prefix_length] = 0;
+
+            prefix_dot = g_strdup_printf("%s.", prefix);
+
+            if (qdict_array_entries(qdict, prefix_dot) > 0) {
+                /* Move all entries with this prefix into a nested QList */
+                QDict *array_qdict;
+                QList *target_qlist;
+
+                /* We cannot merge two non-empty lists without one overwriting
+                 * members of the other */
+                if (qdict_haskey(qdict, prefix)) {
+                    if (qobject_type(qdict_get(qdict, prefix)) != QTYPE_QLIST 
||
+                        !qlist_empty(qdict_get_qlist(qdict, prefix)))
+                    {
+                        error_setg(errp, "Cannot unflatten list '%s': Overlaps 
"
+                                   "with existing member", prefix);
+                        g_free(prefix);
+                        g_free(prefix_dot);
+                        return false;
+                    }
+
+                    /* Remove the existing empty list so we can replace it */
+                    qdict_del(qdict, prefix);
+                }
+
+                qdict_extract_subqdict(qdict, &array_qdict, prefix_dot);
+                qdict_array_split(array_qdict, &target_qlist);
+                assert(!qdict_size(array_qdict));
+                QDECREF(array_qdict);
+                qdict_put(qdict, prefix, target_qlist);
+            } else {
+                /* Move all entries with this prefix into a nested QDict */
+                QDict *target_qdict, *tmp_qdict;
+
+                if (qdict_haskey(qdict, prefix)) {
+                    if (qobject_type(qdict_get(qdict, prefix)) != QTYPE_QDICT) 
{
+                        error_setg(errp, "Cannot unflatten dict '%s': Overlaps 
"
+                                   "with non-dict member", prefix);
+                        g_free(prefix);
+                        g_free(prefix_dot);
+                        return false;
+                    }
+
+                    /* If there already is a QDict with this prefix, try to
+                     * merge the unflattened members into it */
+                    target_qdict = qdict_get_qdict(qdict, prefix);
+                } else {
+                    /* Otherwise created a new one */
+                    target_qdict = qdict_new();
+                    qdict_put(qdict, prefix, target_qdict);
+                }
+
+                qdict_extract_subqdict(qdict, &tmp_qdict, prefix_dot);
+                qdict_join(target_qdict, tmp_qdict, false);
+
+                if (qdict_size(tmp_qdict)) {
+                    error_setg(errp, "Flattened member '%s.%s' exists in "
+                               "previously existing unflattened dict",
+                               prefix, qdict_first(tmp_qdict)->key);
+                    QDECREF(tmp_qdict);
+                    g_free(prefix);
+                    g_free(prefix_dot);
+                    return false;
+                }
+
+                QDECREF(tmp_qdict);
+            }
+
+            g_free(prefix);
+            g_free(prefix_dot);
+
+            /* The QDict has changed, so we need to reiterate. This will not
+             * result in an infinite loop because every time we get here, one
+             * entry whose key contains a '.' has been removed, and in its 
place
+             * at most one entry whose key does not contain a '.' has been
+             * inserted. Therefore, the number of entries with '.' in their key
+             * decreases and will eventually reach 0, at which point we cannot
+             * get here anymore. */
+            entry = qdict_first(qdict);
+            continue;
+        }
+
+        entry = qdict_next(qdict, entry);
+    }
+
+    /* Second pass: Recurse to nested QDicts and QLists */
+    for (entry = qdict_first(qdict); entry; entry = qdict_next(qdict, entry)) {
+        switch (qobject_type(entry->value)) {
+        case QTYPE_QDICT:
+            if (!qdict_unflatten(qobject_to_qdict(entry->value), errp)) {
+                return false;
+            }
+            break;
+
+        case QTYPE_QLIST:
+            if (!qlist_unflatten(qobject_to_qlist(entry->value), errp)) {
+                return false;
+            }
+            break;
+
+        default:
+            break;
+        }
+    }
+
+    return true;
+}
+
+/**
  * qdict_join(): Absorb the src QDict into the dest QDict, that is, move all
  * elements from src to dest.
  *
-- 
2.7.1