qapi-introspect: Document lack of sorting

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.

It doesn't help that sorting can be subjective if you introduce
locales into the mix (I'm not experienced enough with Python
to know for sure, but at least it looks like it defaults to
sorting in the C locale even when run under a different locale).
And while our current introspection output is deterministic
(because we visit entities in a sorted order), we may want
to change that order in the future (such as using OrderedDict
to stick to .json declaration order).

For these reasons, we simply document that clients should not
rely on any particular order of items in introspection output.
And since it is now a documented part of the contract, we have
the freedom to later rearrange output if needed, without
worrying about breaking well-written clients.

Signed-off-by: Eric Blake <eblake@redhat.com>
Message-Id: <1446791754-23823-13-git-send-email-eblake@redhat.com>
[Commit message tweaked]
Signed-off-by: Markus Armbruster <armbru@redhat.com>

1 files changed, 15 insertions, 4 deletions

diff --git a/docs/qapi-code-gen.txt b/docs/qapi-code-gen.txt
index ba29bc634a..f9fa6f3d96 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.
 
 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 the entire object when learning whether a particular
+member is supported.
 
 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 the entire enum when learning whether a
+particular value is supported.
 
 Example: the SchemaInfo for MyEnum from section Enumeration types