Re: [Qemu-devel] [PATCH v9 09/27] qapi-introspect: Document lack of sorting

[Markus Armbruster]

Eric Blake <address@hidden> 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 <address@hidden>
>
> ---
> 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.
>  #