From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:60825) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bkUrt-0006sT-2H for qemu-devel@nongnu.org; Thu, 15 Sep 2016 07:30:15 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bkUrn-0008Op-2a for qemu-devel@nongnu.org; Thu, 15 Sep 2016 07:30:12 -0400 Received: from mx1.redhat.com ([209.132.183.28]:33438) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bkUrm-0008OF-On for qemu-devel@nongnu.org; Thu, 15 Sep 2016 07:30:07 -0400 Date: Thu, 15 Sep 2016 12:30:01 +0100 From: "Daniel P. Berrange" Message-ID: <20160915113001.GH26068@redhat.com> Reply-To: "Daniel P. Berrange" References: <1473088600-17930-1-git-send-email-berrange@redhat.com> <1473088600-17930-2-git-send-email-berrange@redhat.com> <20160914141842.GD4649@noname.redhat.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <20160914141842.GD4649@noname.redhat.com> Subject: Re: [Qemu-devel] [PATCH v11 1/6] qdict: implement a qdict_crumple method for un-flattening a dict List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Kevin Wolf Cc: qemu-devel@nongnu.org, Markus Armbruster , Max Reitz , =?utf-8?Q?Marc-Andr=C3=A9?= Lureau , Paolo Bonzini , Andreas =?utf-8?Q?F=C3=A4rber?= On Wed, Sep 14, 2016 at 04:18:42PM +0200, Kevin Wolf wrote: > Am 05.09.2016 um 17:16 hat Daniel P. Berrange geschrieben: > > 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. > > [...] > > > +static void qdict_split_flat_key(const char *key, char **prefix, > > + const 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 = NULL; > > + do { > > + if (separator) { > > + separator += 2; > > + } else { > > + separator = key; > > + } > > + separator = strchr(separator, '.'); > > + } while (separator && separator[1] == '.'); > > + > > + if (separator) { > > + *prefix = g_strndup(key, > > + separator - key); > > This fits in a single line. > > > + *suffix = separator + 1; > > + } else { > > + *prefix = g_strdup(key); > > + *suffix = NULL; > > + } > > + > > + /* Unescape the '..' sequence into '.' */ > > + for (i = 0, j = 0; (*prefix)[i] != '\0'; i++, j++) { > > + if ((*prefix)[i] == '.') { > > + assert((*prefix)[i + 1] == '.'); > > + i++; > > + } > > + (*prefix)[j] = (*prefix)[i]; > > + } > > + (*prefix)[j] = '\0'; > > +} > > + > > + > > +/** > > + * qdict_is_list: > > + * @maybe_list: dict to check if keys represent list elements. > > + * > > + * Determine whether all keys in @maybe_list are valid list elements. > > + * If @maybe_list is non-zero in length and all the keys look like > > + * valid list indexes, this will return 1. If @maybe_list is zero > > + * length or all keys are non-numeric then it will return 0 to indicate > > + * it is a normal qdict. If there is a mix of numeric and non-numeric > > + * keys, or the list indexes are non-contiguous, an error is reported. > > + * > > + * Returns: 1 if a valid list, 0 if a dict, -1 on error > > + */ > > +static int qdict_is_list(QDict *maybe_list, Error **errp) > > +{ > > + const QDictEntry *ent; > > + ssize_t len = 0; > > + ssize_t max = -1; > > + int is_list = -1; > > + int64_t val; > > + > > + for (ent = qdict_first(maybe_list); ent != NULL; > > + ent = qdict_next(maybe_list, ent)) { > > + > > + if (qemu_strtoll(ent->key, NULL, 10, &val) == 0) { > > + if (is_list == -1) { > > + is_list = 1; > > + } else if (!is_list) { > > + error_setg(errp, > > + "Cannot crumple a dictionary with a mix of list " > > + "and non-list keys"); > > This is a message that users will see if they pass a bad command line > option. I don't think they will understand what it means to "crumple a > dictionary" or that they tried to do this. > > Maybe simply "Cannot mix list and non-list keys"? Oh yes, good point. > > + if (is_list == -1) { > > + assert(!qdict_size(maybe_list)); > > + is_list = 0; > > + } > > + > > + if (len != (max + 1)) { > > + error_setg(errp, "List indexes are not contiguous, " > > + "saw %zd elements but %zd largest index", > > + len, max); > > + return -1; > > + } > > I don't think this is catching everything that isn't contiguous, but I'm > not sure whether we care. > > One reason is that you accept negative indexes above, the other one is > that the keys are strings, so I could pass "1", "+1", "01" and "3" and it > would be accepted. > > It's probably reasonable enough to say that in such cases you get what > you get, and if future versions behave differently, that's your problem. In the context of this 'qdict_is_list()' method I think that's ok - even if they use "1", "+1", "01" and "3", from the POV of this method it is a list. The qdict_crumple method could however then detect if there are keys that are duplicated and/or missing, which will handle the case you illustrate. I'll add a checks and a test for this. > > +/** > > + * 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. > > + * > > + * To include a literal '.' in a key name, it must be escaped as '..' > > + * > > + * For example, an input of: > > + * > > + * { 'foo.0.bar': 'one', 'foo.0.wizz': '1', > > + * 'foo.1.bar': 'two', 'foo.1.wizz': '2' } > > + * > > + * will result in any output of: > > + * > > + * { > > + * 'foo': [ > > + * { 'bar': 'one', 'wizz': '1' }, > > + * { 'bar': 'two', 'wizz': '2' } > > + * ], > > + * } > > + * > > + * The following scenarios in the input dict will result in an > > + * error being returned: > > + * > > + * - Any values in @src are non-scalar types > > + * - If keys in @src imply that a particular level is both a > > + * list and a dict. eg, "foo.0.bar" and "foo.eek.bar". > > + * - If keys in @src imply that a particular level is a list, > > + * but the indexes are non-contigous. eg "foo.0.bar" and > > + * "foo.2.bar" without any "foo.1.bar" present. > > + * - If keys in @src represent list indexes, but are not in > > + * the "%zu" format. eg "foo.+0.bar" > > Hm, so you thought of the case I mentioned above, but I don't see it > handled properly in the code. Yeah, I've not handled it well enough. > > + /* Step 3: detect if we need to turn our dict into list */ > > + is_list = qdict_is_list(multi_level, errp); > > + if (is_list < 0) { > > + goto error; > > + } > > + > > + if (is_list) { > > + dst = QOBJECT(qlist_new()); > > + > > + for (i = 0; i < qdict_size(multi_level); i++) { > > + char *key = g_strdup_printf("%zu", i); > > + > > + child = qdict_get(multi_level, key); > > + g_free(key); > > + assert(child); > > So this is the place where the %zu requirement for key names is > enforced. But where do we check this before to return an error instead > of running into an assertion failure? > > If you turn this into another non-contiguous error, we should be fine. Yes, I should turn the assert into an reported error. > > + > > + qobject_incref(child); > > + qlist_append_obj(qobject_to_qlist(dst), child); > > + } > > + QDECREF(multi_level); > > + multi_level = NULL; > > + } else { > > + dst = QOBJECT(multi_level); > > +static void qdict_crumple_test_nonrecursive(void) > > +{ > > + QDict *src, *dst, *rules, *vnc; > > + 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")); > > Worth testing an escaped . as well? Possibly both in the prefix (where > it should get unescaped) and in the suffix (where the doubling is still > expected. Yes, we should validate escaping. > > + > > +static void qdict_crumple_test_bad_inputs(void) > > +{ > > + QDict *src; > > + Error *error = NULL; > > + > > + src = qdict_new(); > > + /* rule.0 can't be both a string and a dict */ > > + 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(error != NULL); > > + error_free(error); > > + error = NULL; > > + QDECREF(src); > > + > > + src = qdict_new(); > > + /* rule can't be both a list and a dict */ > > + 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(error != NULL); > > + error_free(error); > > + error = NULL; > > + QDECREF(src); > > + > > + src = qdict_new(); > > + /* The input should be flat, ie no dicts or lists */ > > + 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(error != NULL); > > + error_free(error); > > + error = NULL; > > + QDECREF(src); > > + > > + > > + src = qdict_new(); > > + /* List indexes must not have gaps */ > > + qdict_put(src, "rule.0", qdict_new()); > > You want to use something valid here (i.e. a scalar) > > > + qdict_put(src, "rule.3", qstring_from_str("allow")); > > + > > + g_assert(qdict_crumple(src, true, &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", qdict_new()); > > And here too. This invalid entry is the reason why you error out early > instead of running into the assertion failure I mentioned above. OK Regards, Daniel -- |: http://berrange.com -o- http://www.flickr.com/photos/dberrange/ :| |: http://libvirt.org -o- http://virt-manager.org :| |: http://autobuild.org -o- http://search.cpan.org/~danberr/ :| |: http://entangle-photo.org -o- http://live.gnome.org/gtk-vnc :|