From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:39461) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ai8a9-000781-JE for qemu-devel@nongnu.org; Mon, 21 Mar 2016 18:45:55 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ai8a7-0006jB-QM for qemu-devel@nongnu.org; Mon, 21 Mar 2016 18:45:53 -0400 References: <1457635927-23045-1-git-send-email-berrange@redhat.com> <1457636396-24983-1-git-send-email-berrange@redhat.com> From: Eric Blake Message-ID: <56F07993.5080403@redhat.com> Date: Mon, 21 Mar 2016 16:45:39 -0600 MIME-Version: 1.0 In-Reply-To: <1457636396-24983-1-git-send-email-berrange@redhat.com> Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="bQOKi96BO4iv4t0M3On7KeoDxwNojXEer" Subject: Re: [Qemu-devel] [PATCH v3 01/10] qdict: implement a qdict_crumple method for un-flattening a dict List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: "Daniel P. Berrange" , qemu-devel@nongnu.org Cc: Paolo Bonzini , qemu-block@nongnu.org, Markus Armbruster , =?UTF-8?Q?Andreas_F=c3=a4rber?= , Max Reitz This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --bQOKi96BO4iv4t0M3On7KeoDxwNojXEer Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable On 03/10/2016 11:59 AM, 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. >=20 > 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. >=20 >=20 > will get turned into a dict with one element 'foo' whose > value is a list. The list elements will each in turn be > dicts. >=20 > { > 'foo' =3D> [ s/=3D>/:/ > { 'bar': 'one', 'wizz': '1' } s/$/,/ > { 'bar': 'two', 'wizz': '2' } > ], > } >=20 > 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 s/the nested/the nesting/ > used when the same object is defined over QMP. >=20 > Signed-off-by: Daniel P. Berrange > --- > include/qapi/qmp/qdict.h | 1 + > qobject/qdict.c | 267 +++++++++++++++++++++++++++++++++++++++= ++++++++ > tests/check-qdict.c | 143 +++++++++++++++++++++++++ > 3 files changed, 411 insertions(+) >=20 > + > +/** > + * 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=3D'foo' and suffix=3D'0.bar' > + * 'foo..0.bar' -> prefix=3D'foo.0' and suffix=3D'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. > + */ Might be worth mentioning that prefix and suffix must both be non-NULL, and that the caller must g_free() the two resulting strings. > +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 =3D NULL; > + do { > + if (separator) { > + separator +=3D 2; > + } else { > + separator =3D key; > + } > + separator =3D strchr(separator, '.'); > + } while (separator && *(separator + 1) =3D=3D '.'); I'd probably have written separator[1] =3D=3D '.', but your approach is synonymous. > + > + if (separator) { > + *prefix =3D g_strndup(key, > + separator - key); > + *suffix =3D g_strdup(separator + 1); > + } else { > + *prefix =3D g_strdup(key); > + *suffix =3D NULL; > + } > + > + /* Unescape the '..' sequence into '.' */ > + for (i =3D 0, j =3D 0; (*prefix)[i] !=3D '\0'; i++, j++) { > + if ((*prefix)[i] =3D=3D '.' && > + (*prefix)[i + 1] =3D=3D '.') { Technically, if (*prefix)[i] =3D=3D '.', we could assert((*prefix)[i + 1]= =3D=3D '.'), since the only way to get a '.' in prefix is via escaping. For that matter, you could short-circuit (part of) the loop by doing a strchr for '.' (if not found, the loop is not needed; if found, start the reduction at that point rather on the bytes leading up to that point)= =2E > + i++; > + } > + (*prefix)[j] =3D (*prefix)[i]; > + } > + (*prefix)[j] =3D '\0'; > +} > + > + > +/** > + * qdict_list_size: > + * @maybe_List: dict that may be only list elements s/List/list/ > + * > + * Determine whether all keys in @maybe_list are > + * valid list elements. They they are all valid, s/They they/If they/ > + * then this returns the number of elements. If > + * they all look like non-numeric keys, then returns > + * zero. If there is a mix of numeric and non-numeric > + * keys, then an error is set as it is both a list > + * and a dict at once. > + * > + * Returns: number of list elemets, 0 if a dict, -1 on error s/elemets/elements/ > + */ > +static ssize_t qdict_list_size(QDict *maybe_list, Error **errp) > +{ > + const QDictEntry *entry, *next; > + ssize_t len =3D 0; > + ssize_t max =3D -1; > + int is_list =3D -1; > + int64_t val; > + > + entry =3D qdict_first(maybe_list); > + while (entry !=3D NULL) { > + next =3D qdict_next(maybe_list, entry); > + > + if (qemu_strtoll(entry->key, NULL, 10, &val) =3D=3D 0) { > + if (is_list =3D=3D -1) { > + is_list =3D 1; > + } else if (!is_list) { > + error_setg(errp, > + "Key '%s' is for a list, but previous key i= s " > + "for a dict", entry->key); Keys are unsorted, so it's a bit hard to call it "previous key". Maybe a better error message would be along the lines of "cannot crumple dictionary because of a mix of list and non-list keys"? I dunno... > + return -1; > + } > + len++; > + if (val > max) { > + max =3D val; > + } > + } else { > + if (is_list =3D=3D -1) { > + is_list =3D 0; > + } else if (is_list) { > + error_setg(errp, > + "Key '%s' is for a dict, but previous key i= s " > + "for a list", entry->key); =2E..same argument. If we can wordsmith something that makes sense, it might work for both places. Otherwise, I can live with your messages. > +/** > + * qdict_crumple: > + * Worth documenting the 'recursive' parameter? > + * 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 merely one level of arrays > + * > + * { 'foo.0.bar': 'one', 'foo.0.wizz': '1', > + * 'foo.1.bar': 'two', 'foo.1.wizz': '2' } > + * > + * =3D> > + * > + * { > + * 'foo' =3D> [ s/=3D>/:/ > + * { 'bar': 'one', 'wizz': '1' } s/$/,/ > + * { 'bar': 'two', 'wizz': '2' } > + * ], > + * } > + * Worth mentioning the escaping of '.' in key names? > + */ > +QObject *qdict_crumple(QDict *src, bool recursive, Error **errp) > +{ > + const QDictEntry *entry, *next; > + QDict *two_level, *multi_level =3D NULL; > + QObject *dst =3D NULL, *child; > + ssize_t list_len; > + size_t i; > + char *prefix =3D NULL, *suffix =3D NULL; > + > + two_level =3D qdict_new(); > + entry =3D qdict_first(src); > + > + /* Step 1: split our totally flat dict into a two level dict */ > + > + /* Step 2: optionally process the two level dict recursively > + * into a multi-level dict */ > + if (recursive) { > + > + /* Step 3: detect if we need to turn our dict into list */ > + list_len =3D qdict_list_size(multi_level, errp); > + if (list_len < 0) { > + goto error; > + } > + > + if (list_len) { > + dst =3D QOBJECT(qlist_new()); > + > + for (i =3D 0; i < list_len; i++) { > + char *key =3D g_strdup_printf("%zu", i); > + > + child =3D qdict_get(multi_level, key); > + g_free(key); > + if (!child) { > + error_setg(errp, "Unexpected missing list entry %zu", = i); Couldn't we assert() this, since it is a programming bug if qdict_list_size() let us get this far but then the key disappeared? Overall looks like it does the trick. > +++ b/tests/check-qdict.c > @@ -596,6 +596,140 @@ static void qdict_join_test(void) > QDECREF(dict2); > } > =20 > + > +static void qdict_crumple_test_nonrecursive(void) > +{ This only covers a single layer of collapse, but not turning a dict into a list. Is it also worth covering a case where no list indices are involved, such as the four keys "a.b.d", "a.b.e", "a.c.d", "a.d.e" being crumpled non-recursively into a single dict "a" with keys "b.d", "b.e", "c.d", and "d.e"? > + > +static void qdict_crumple_test_recursive(void) > +{ > + This only covers a list of dict collapse, not a true multi-layer dict collapse. Is it also worth covering the same four keys as above, but this time that dict "a" has keys "b" and "c", each of which is a dict in turn with keys "d" and "e"? > +static void qdict_crumple_test_empty(void) > +{ So an empty dict is never crumpled to an empty list. I guess that shouldn't matter. > + > +static void qdict_crumple_test_bad_inputs(void) > +{ > + QDict *src; > + Error *error =3D NULL; > + > + > + src =3D 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")); I'd use "rule.a" and "rule.b" here, so that you aren't confusing this with the earlier test that you can't mix list and dict. I'd also add a negative test for "rule.1" without "rule.0" being invalid (missing a list index). I'll wait to give R-b until I get further into the series, and/or you post a v4, but it's mostly there. --=20 Eric Blake eblake redhat com +1-919-301-3266 Libvirt virtualization library http://libvirt.org --bQOKi96BO4iv4t0M3On7KeoDxwNojXEer Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 Comment: Public key at http://people.redhat.com/eblake/eblake.gpg Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQEcBAEBCAAGBQJW8HmTAAoJEKeha0olJ0NqbY4H/iJA6lvpkXMVHIOVt+NNaooc 2TUEc3o4KUq0eK27SnNO4AbunddQjPSYqzSypzA/aKrrTrNqMzTwAz1wv6q45eud UFTKAzEorrSaiAaQ8YM9DjjlljfMWQXsnue5VX+0IkQw/xw7y+y3j5w/c+kdOKTE 6rxiJHNmz0YXlUEQpKyOIK6AHGbYCXkSOJxhoh7EOEcHdEYJYksEie7+KXY36L0/ HSIWuo7TolphiICq8vY3lwP9mTQGG6aNcLYUci+m7CT32TWX1WYqJzs7ibQgv8X5 38/a11/slsKNc4gGzhcLjZjvX3i+OnnvqmxNqIX6QSotK+D7uf3+pLrKFS3ptf4= =W5+W -----END PGP SIGNATURE----- --bQOKi96BO4iv4t0M3On7KeoDxwNojXEer--