[Qemu-devel] [PATCH v7 04/14] qapi-introspect: Guarantee particular sorting

[Eric Blake]

Sorting the values of an enum makes it easier to look up whether
a particular value is present, via binary rather than linear search
(probably most visible with QKeyCode, which has grown over
several releases).  Additionally, QMP clients need not know which
C value is associated with an enum name, so sorting is an
effective way to hide that non-ABI aspect of qapi.

While we are at it, it is also easy to sort the members and
variants of objects, to allow for a similar binary search (although
less compelling, as any struct with that many menbers should
arguably be broken into hierarchical substructs), and equally
valid since JSON objects have no specific order in which keys must
appear.  There is no trivial or obvious way to sort the types of
an alternate, so that is left unchanged.

However, the overall SchemaInfo array remains unsorted.  It might
make sense to sort with 'meta-type' as a primary key and 'name'
as a secondary key, but it is not obvious that this will provide
benefits to end-user clients (we allow mutually recursive types,
so there is no posible topological sorting where a single pass
over the array could resolve all types, and while binary searches
could be made possible by sorting, it would be even more efficient
for clients to read the array into a hashtable for O(1) rather
than O(log n) random-access lookups, at which point pre-sorting is
wasted effort).

Document these conventions, so that clients will know what can
and cannot be relied on.

Signed-off-by: Eric Blake <address@hidden>

---
TODO: should the documentation mention that the sorting is done
in the C locale? Is there anything required to ensure that python
sorts sanely (ie. that the choice of locale while building
doesn't cause inadvertent sorting differences such as turning on
case-insensitivity)?

v7: tweak commit wording
v6: no change from v5
---
 docs/qapi-code-gen.txt     | 21 +++++++++++++++++----
 qapi/introspect.json       | 22 +++++++++++++++++-----
 scripts/qapi-introspect.py |  9 ++++++---
 3 files changed, 40 insertions(+), 12 deletions(-)

diff --git a/docs/qapi-code-gen.txt b/docs/qapi-code-gen.txt
index 15a1c70..e970440 100644
--- a/docs/qapi-code-gen.txt
+++ b/docs/qapi-code-gen.txt
@@ -516,6 +516,13 @@ 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 and meta-type throughout the
+entire array to learn more about that name.  For now, the name for
+each SchemaInfo is unique thanks to qapi naming conventions; however
+this may be changed in the future (such as allowing a command and an
+event with the same name), so it is important that the client check
+for the desired meta-type.

 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 +603,8 @@ 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 sorted by "name", so that clients
+can use a binary search to see if a particular member is supported.

 Example: the SchemaInfo for MyType from section Struct types

@@ -610,7 +618,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 sorted by "case", so it appears in the same
+order as the enum type matching "tag".

 Example: the SchemaInfo for flat union BlockdevOptions from section
 Union types
@@ -651,7 +661,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 +684,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 sorted order,
+so clients can use a binary search to see if a particular value
+is present.

 Example: the SchemaInfo for MyEnum from section Enumeration types

diff --git a/qapi/introspect.json b/qapi/introspect.json
index cc50dc6..71632af 100644
--- a/qapi/introspect.json
+++ b/qapi/introspect.json
@@ -25,6 +25,11 @@
 # Returns: array of @SchemaInfo, where each element describes an
 # entity in the ABI: command, event, type, ...
 #
+# The order of the various SchemaInfo is unspecified.  For now, the
+# name of each SchemaInfo is unique regardless of meta-type, but to be
+# safe, clients should check that a given name has the expected
+# meta-type.
+#
 # 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 +83,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 all names are currently unique
+#        regardless of @meta-type, clients should not rely on this.
 #
 # All references to other SchemaInfo are by name.
 #
@@ -130,7 +136,9 @@
 #
 # Additional SchemaInfo members for meta-type 'enum'.
 #
-# @values: the enumeration type's values.
+# @values: the enumeration type's values.  The values are sorted, so
+#          clients can use a binary search to see if a particular value
+#          is present.
 #
 # Values of this type are JSON string on the wire.
 #
@@ -158,14 +166,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
+#           sorted by name, so clients can use a binary search to see
+#           if a given member is present.
 #
 # @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 sorted by case, which
+#            means they appear in the same order as the values of the
+#            enum type of the @tag.
 #
 # Values of this type are JSON object on the wire.
 #
@@ -219,7 +231,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.
 #
diff --git a/scripts/qapi-introspect.py b/scripts/qapi-introspect.py
index 64f2cd0..6a5a843 100644
--- a/scripts/qapi-introspect.py
+++ b/scripts/qapi-introspect.py
@@ -10,6 +10,7 @@
 # See the COPYING file in the top-level directory.

 from qapi import *
+from operator import attrgetter


 # Caveman's json.dumps() replacement (we're stuck at Python 2.4)
@@ -126,7 +127,8 @@ const char %(c_name)s[] = %(c_string)s;

     def _gen_variants(self, tag_name, variants):
         return {'tag': tag_name,
-                'variants': [self._gen_variant(v) for v in variants]}
+                'variants': [self._gen_variant(v) for v in
+                             sorted(variants, key=attrgetter('name'))]}

     def _gen_variant(self, variant):
         return {'case': variant.name, 'type': self._use_type(variant.type)}
@@ -135,14 +137,15 @@ const char %(c_name)s[] = %(c_string)s;
         self._gen_json(name, 'builtin', {'json-type': json_type})

     def visit_enum_type(self, name, info, values, prefix):
-        self._gen_json(name, 'enum', {'values': values})
+        self._gen_json(name, 'enum', {'values': sorted(values)})

     def visit_array_type(self, name, info, element_type):
         element = self._use_type(element_type)
         self._gen_json('[' + element + ']', 'array', {'element-type': element})

     def visit_object_type_flat(self, name, info, members, variants):
-        obj = {'members': [self._gen_member(m) for m in members]}
+        obj = {'members': [self._gen_member(m) for m in
+                           sorted(members, key=attrgetter('name'))]}
         if variants:
             obj.update(self._gen_variants(variants.tag_member.name,
                                           variants.variants))
-- 
2.4.3