From patchwork Wed Nov 4 06:20:31 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Blake X-Patchwork-Id: 539714 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 19FE414090A for ; Wed, 4 Nov 2015 17:23:29 +1100 (AEDT) Received: from localhost ([::1]:52816 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZtrTi-0000Bs-V4 for incoming@patchwork.ozlabs.org; Wed, 04 Nov 2015 01:23:26 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:34080) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZtrRL-00042j-Sj for qemu-devel@nongnu.org; Wed, 04 Nov 2015 01:21:02 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZtrRJ-000696-VQ for qemu-devel@nongnu.org; Wed, 04 Nov 2015 01:20:59 -0500 Received: from mx1.redhat.com ([209.132.183.28]:34755) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZtrRJ-000692-Lg for qemu-devel@nongnu.org; Wed, 04 Nov 2015 01:20:57 -0500 Received: from int-mx10.intmail.prod.int.phx2.redhat.com (int-mx10.intmail.prod.int.phx2.redhat.com [10.5.11.23]) by mx1.redhat.com (Postfix) with ESMTPS id 3E92CC0D61A3; Wed, 4 Nov 2015 06:20:57 +0000 (UTC) Received: from red.redhat.com (ovpn-113-189.phx2.redhat.com [10.3.113.189]) by int-mx10.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id tA46KqVW022634; Wed, 4 Nov 2015 01:20:56 -0500 From: Eric Blake To: qemu-devel@nongnu.org Date: Tue, 3 Nov 2015 23:20:31 -0700 Message-Id: <1446618049-13596-10-git-send-email-eblake@redhat.com> In-Reply-To: <1446618049-13596-1-git-send-email-eblake@redhat.com> References: <1446618049-13596-1-git-send-email-eblake@redhat.com> X-Scanned-By: MIMEDefang 2.68 on 10.5.11.23 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 209.132.183.28 Cc: armbru@redhat.com, Michael Roth Subject: [Qemu-devel] [PATCH v9 09/27] qapi-introspect: Document lack of sorting X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org 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. 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), 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 --- 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. 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. 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. 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. # # 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. # # @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. #