Eric Blake <ebl...@redhat.com> writes:
> qapi-code-gen.txt already claims that types, commands, and
> events share a common namespace; set this in stone by further
> documenting that our introspection output will never have
> collisions with the same name tied to more than one meta-type.
>
> Our largest QMP enum currently has 125 values, our largest
> object type has 27 members, and the mean for each is less than
> 10. These sizes are small enough that the per-element overhead
> of O(log n) binary searching probably outweighs the speed
> possible with direct O(n) linear searching (a better algorithm
> with more overhead will only beat a leaner naive algorithm only
> as you scale to larger input sizes).
>
> Arguably, the overall SchemaInfo array could be sorted by name;
> there, we currently have 531 entities, large enough for a binary
> search to be faster than linear. However, remember that we have
> mutually-recursive types, which means there is no topological
> ordering that will allow clients to learn all information about
> that type in a single linear pass; thus clients will want to do
> random access over the data, and they will probably read the
> introspection output into a hashtable for O(1) lookup rather
> than O(log n) binary searching, at which point, pre-sorting our
> introspection output doesn't help the client.
>
> Finally, I am not sure how to guarantee that python sorts strings
> for the C locale even if the generator is run under a different
> locale.
Python's "Sorting HOW TO" advises:
For locale aware sorting, use locale.strxfrm() for a key function or
locale.strcoll() for a comparison function.
https://docs.python.org/2.7/howto/sorting.html#odd-and-ends
Explicit, opt-in locale-dependence sure feels a lot cleaner and safer
than the historical mess we have in C.
> Our current output order is deterministic (based on the
> order present in .json files, even if that order has no inherent
> bearing on how a client will present their QMP commands),
Actually no longer the case:
def visit(self, visitor):
visitor.visit_begin(self)
for (name, entity) in sorted(self._entity_dict.items()):
if visitor.visit_needed(entity):
entity.visit(visitor)
visitor.visit_end()
Dates back to commit 3f7dc21 "qapi: New QAPISchemaVisitor". Without
sorting, we'd some unpredictable order. I could've used OrderedDict
instead, preserving insertion order.
> while
> sorting data risks non-determinism if the generator is subject to
> any locale differences.
>
> For these reasons, we simply document that clients should not
> rely on any particular order of items in introspection output.
> Additionally, this gives us the freedom to later change our mind,
> so that we could rearrange output in a different order than the
> way it was listed in the .json file, without breaking any client
> that was already aware it had to do a linear search.
>
> Document these conventions, so that clients will know what can
> and cannot be relied on.
>
> Signed-off-by: Eric Blake <ebl...@redhat.com>
>
> ---
> v9: retitle; and swing in the opposite direction: give the user
> no guarantee about order
> v8: no change
> v7: tweak commit wording
> v6: no change from v5
> ---
> docs/qapi-code-gen.txt | 19 +++++++++++++++----
> qapi/introspect.json | 21 ++++++++++++++++-----
> 2 files changed, 31 insertions(+), 9 deletions(-)
>
> diff --git a/docs/qapi-code-gen.txt b/docs/qapi-code-gen.txt
> index ba29bc6..20e6907 100644
> --- a/docs/qapi-code-gen.txt
> +++ b/docs/qapi-code-gen.txt
> @@ -516,6 +516,10 @@ query-qmp-schema. QGA currently doesn't support
> introspection.
>
> query-qmp-schema returns a JSON array of SchemaInfo objects. These
> objects together describe the wire ABI, as defined in the QAPI schema.
> +There is no specified order to the SchemaInfo objects returned; a
> +client must search for a particular name throughout the entire array
> +to learn more about that name, but is at least guaranteed that there
> +will be no collisions between type, command, and event names.
I would've omitted the "client must search" clause, but I habitually
write subtle contracts that need to be read slowly and carefully. Feel
free to keep it.
> However, the SchemaInfo can't reflect all the rules and restrictions
> that apply to QMP. It's interface introspection (figuring out what's
> @@ -596,7 +600,9 @@ any. Each element is a JSON object with members "name"
> (the member's
> name), "type" (the name of its type), and optionally "default". The
> member is optional if "default" is present. Currently, "default" can
> only have value null. Other values are reserved for future
> -extensions.
> +extensions. The "members" array is in no particular order; clients
> +must search every member when learning whether a particular member is
> +supported.
Nitpick: clients must search the object, not every member.
> Example: the SchemaInfo for MyType from section Struct types
>
> @@ -610,7 +616,9 @@ Example: the SchemaInfo for MyType from section Struct
> types
> "variants" is a JSON array describing the object's variant members.
> Each element is a JSON object with members "case" (the value of type
> tag this element applies to) and "type" (the name of an object type
> -that provides the variant members for this type tag value).
> +that provides the variant members for this type tag value). The
> +"variants" array is in no particular order, and is not guaranteed to
> +list cases in the same order as the corresponding "tag" enum type.
>
> Example: the SchemaInfo for flat union BlockdevOptions from section
> Union types
> @@ -651,7 +659,8 @@ Union types
> The SchemaInfo for an alternate type has meta-type "alternate", and
> variant member "members". "members" is a JSON array. Each element is
> a JSON object with member "type", which names a type. Values of the
> -alternate type conform to exactly one of its member types.
> +alternate type conform to exactly one of its member types. There is
> +no guarantee on the order in which "members" will be listed.
>
> Example: the SchemaInfo for BlockRef from section Alternate types
>
> @@ -673,7 +682,9 @@ Example: the SchemaInfo for ['str']
> "element-type": "str" }
>
> The SchemaInfo for an enumeration type has meta-type "enum" and
> -variant member "values".
> +variant member "values". The values are listed in no particular
> +order; clients must search every value when learning whether a
> +particular value is supported.
Similar nitpick.
> Example: the SchemaInfo for MyEnum from section Enumeration types
>
> diff --git a/qapi/introspect.json b/qapi/introspect.json
> index cc50dc6..f86d552 100644
> --- a/qapi/introspect.json
> +++ b/qapi/introspect.json
> @@ -25,6 +25,10 @@
> # Returns: array of @SchemaInfo, where each element describes an
> # entity in the ABI: command, event, type, ...
> #
> +# The order of the various SchemaInfo is unspecified; however, all
> +# names are guaranteed to be unique (no name will be duplicated with
> +# different meta-types).
> +#
> # Note: the QAPI schema is also used to help define *internal*
> # interfaces, by defining QAPI types. These are not part of the QMP
> # wire ABI, and therefore not returned by this command.
> @@ -78,7 +82,8 @@
> # Commands and events have the name defined in the QAPI schema.
> # Unlike command and event names, type names are not part of
> # the wire ABI. Consequently, type names are meaningless
> -# strings here.
> +# strings here, although they are still guaranteed unique
> +# regardless of @meta-type.
> #
> # All references to other SchemaInfo are by name.
> #
> @@ -130,7 +135,9 @@
> #
> # Additional SchemaInfo members for meta-type 'enum'.
> #
> -# @values: the enumeration type's values.
> +# @values: the enumeration type's values. The values are in no particular
> +# order, so clients must search every value when learning if a
> +# particular value is present.
I'd drop the ", so clients must search" part as obvious.
> #
> # Values of this type are JSON string on the wire.
> #
> @@ -158,14 +165,18 @@
> #
> # Additional SchemaInfo members for meta-type 'object'.
> #
> -# @members: the object type's (non-variant) members.
> +# @members: the object type's (non-variant) members. The members are
> +# in no particular order, so clients must search every member
> +# when learning if a particular member is present.
Likewise.
> #
> # @tag: #optional the name of the member serving as type tag.
> # An element of @members with this name must exist.
> #
> # @variants: #optional variant members, i.e. additional members that
> # depend on the type tag's value. Present exactly when
> -# @tag is present.
> +# @tag is present. The variants are in no particular order,
> +# and may even differ from the order of the values of the
> +# enum type of the @tag.
> #
> # Values of this type are JSON object on the wire.
> #
> @@ -219,7 +230,7 @@
> #
> # Additional SchemaInfo members for meta-type 'alternate'.
> #
> -# @members: the alternate type's members.
> +# @members: the alternate type's members, in no particular order.
> # The members' wire encoding is distinct, see
> # docs/qapi-code-gen.txt section Alternate types.
> #
