Re: [Qemu-devel] [PATCH v8 07/17] qapi: Rework collision assertions

[Eric Blake]

On 11/02/2015 08:37 AM, Markus Armbruster wrote:
> Eric Blake <address@hidden> writes:
> 
>> Now that we have separate namespaces for QMP vs. tag values,
> 
> What's the "QMP namespace"?

I guess I need to be more explicit :)

In the generated C struct for a qapi object, we now have two separate
namespaces:

struct Foo {
    Type1 name1; /* namespace for QMP (aka non-variant) members */
    Type2 name2;
    union {
        Type1 name1; /* namespace for tag values */
        Type2 name2;
    } u;
};


> 
>> we can simplify how the QAPISchema*.check() methods check for
>> collisions.
> 
> I *guess* the point of this patch is dropping checks that are obsolete
> now tag values no longer collide with non-variant member names in
> generated C, with simplifications on top.  Correct?
> 

Almost. This is not actually dropping any of the old ad hoc checks in
the parser, but you are correct that it IS fixing the check() methods to
quit asserting things that are no longer forbidden now that tag values
no longer collide with non-variant member names.

>>              Each QAPISchemaObjectTypeMember check() call is
>> given a single set of names it must not collide with; this set
>> is either the QMP names (when this member is used by an
>> ObjectType) or the case names (when this member is used by an
>> ObjectTypeVariants).  We no longer need an all_members
>> parameter, as it can be computed by seen.values().

This is point [1] mentioned below.

>>  When used
>> by a union, QAPISchemaObjectTypeVariant must also perform a
>> QMP collision check for each member of its corresponding type.
> 
> I'm afraid this explanation is next to impossible to understand unless
> you know how the checking works.  I should know, because I wrote it, but
> actually don't, at least not by heart.  So let me relearn how checking
> works before your patch.

I guess I get to pick and choose from your wording, to try and make my
commit body more comprehensible.

> 
> We're talking about a single invocation of QAPISchemaObjectType.check().
> Its job is to compute self.members and self.base, and do sanity
> checking, which includes checking for collisions.  It has two variables
> of interest:
> 
> * members is where we accumulate the list of members that'll become
>   self.members.  It's initialized to the inherited members (empty if no
>   base, obviously).

True pre-patch; eliminated by point [1] mentioned above, by observing
that seen.values() is identical to members after processing
local_members, and that we don't further modify seen when processing
variants.

> 
> * seen is a dictionary mapping names to members.  This is merely for
>   collision checking.  It's initialized to contain the inherited members
>   (whose names must be distinct, by induction, because we make sure the
>   base type's check() completes first).
> 
> For each local member m of self, we call m.check(schema, members, seen).
> This is actually QAPISchemaObjectTypeMember.check(), and it uses members
> and seen as follows:
> 
> * Assert m.name doesn't collide with another member's name, i.e. not in
>   seen.
> 
> * Append m to members.
> 
> * Insert m.name: m into seen.
> 
> Straightforward so far.  Coming up next: variants.
> 
> Each variant's members are represented as a single member with the tag
> value as name.  Its type is an object type that has the variant's
> members.
> 
> For each variant v:
> 
> * Copy seen to vseen.  It holds the non-variant members.
> 
> * Call QAPISchemaObjectTypeMember.check(schema, [], vseen), which boils
>   down to assert v.name doesn't collide with a non-variant member's
>   name.  This check is obsolete.
> 
> * Assert v.name is a member of tag_type.
> 
> Not checked: variant's name doesn't collide with another variant's name.
> That's because we copy seen inside the loop instead of before the loop.
> 
> Not checked: variant's members don't collide with non-variant members.
> I think this check got lost when we simplified
> QAPISchemaObjectTypeVariants to hold a single member.

Perhaps so; our testsuite wasn't as complete at that time.  Or maybe
it's because our ad hoc checks in the parsing portion were preventing us
from realizing that we needed to repeat things in check() methods.

> 
> Note that the real checking happens in check_union(), and the checks
> here are just sanity checks.  As long as that's the case, holes here are
> harmless.  However, we need them plugged them when we move the real
> checking from check_union() to the .check().

Yep, and that's what this patch is trying to do.

> 
> Looks like variant checking should be thrown out and redone.
> 
> I still don't get your description.  Guess I have to read the patch
> after all ;)
> 
>> The new ObjectType.check_qmp() is an idempotent subset of
>> check(), and can be called multiple times over different seen
>> sets (useful, since the members of one type can be applied
>> into more than one other location via inheritance or flat
>> union variants).
> 
> I think I get this argument.  Except I don't get why the method's named
> check_qmp().

Check that the QMP field names introduced by this type into an overall
object do not cause any collisions with QMP field names already present
from other sources.  I'm open to suggestions for a better name.

> 
>> The code needs a temporary hack of passing a 'union' flag
>> through Variants.check(), since we do not inline the branches
>> of an alternate type into a parent QMP object.
> 
> What a "QMP object"?  Sounds like a JSON object on the QMP wire, but
> that makes no sense :)

Let's try again:

The code needs a temporary hack of passing a 'union' flag through
Variants.check(), in order to decide whether to check the various fields
of the branch object type against the earlier QMP names in seen.  The
check is conditional on being a union, because the QMP field names of
each union branch share the same QMP namespace as the non-variant fields
in the overall JSON object (even though they are in a different C
namespace due to boxing behind the branch type), while an alternate does
not inline any QMP fields (because it is not part of a larger JSON
object).  Note that we do not need to distinguish between simple and
flat unions, because simple unions have a generated wrapper type whose
lone QMP field ('data') will be checked against the lone 'type'
non-variant field.

> 
>>                                                 A later patch
>> will rework how alternates are laid out, by adding a new
>> subclass, and that will allow us to drop the extra parameter.
>>
>> There are no changes to generated code.
>>
>> Future patches will enhance testsuite coverage, improve error
>> message quality on actual collisions, and move collision
>> checks out of ad hoc parse code into the check() methods.
>>
>> Signed-off-by: Eric Blake <address@hidden>
>>
>> ---
>> v8: rebase to earlier patches, defer positive test additions to
>> later in series
>> v7: new patch, although it is a much cleaner implementation of
>> what was attempted by subset B v8 15/18
>> https://lists.gnu.org/archive/html/qemu-devel/2015-10/msg03042.html
>> ---
>>  scripts/qapi.py | 55 +++++++++++++++++++++++++++++++++----------------------
>>  1 file changed, 33 insertions(+), 22 deletions(-)

Okay, let's see what you think of the actual patch, or if you have any
better suggestions for how I should have worded the commit body.

>>
>> diff --git a/scripts/qapi.py b/scripts/qapi.py
>> index 84ac151..c571709 100644
>> --- a/scripts/qapi.py
>> +++ b/scripts/qapi.py
>> @@ -972,28 +972,28 @@ class QAPISchemaObjectType(QAPISchemaType):
>>          self.variants = variants
>>          self.members = None
>>
>> +    # Finish construction, and validate that all members are usable
>>      def check(self, schema):
>>          assert self.members is not False        # not running in cycles
>>          if self.members:
>>              return
>>          self.members = False                    # mark as being checked
>> +        seen = OrderedDict()
> 
> Why do you need to switch from {} to OrderedDict()?

Because I'm dropping the all_members argument, and I need seen.values()
to maintain the same order in which members are seen, for it to be a
replacement for all_members.

Maybe I need to split this patch into a few more pieces, each tackling a
smaller cleanup, rather than trying to do it all in one?

> 
>>          if self._base_name:
>>              self.base = schema.lookup_type(self._base_name)
>> -            assert isinstance(self.base, QAPISchemaObjectType)
>> -            assert not self.base.variants       # not implemented
>> -            self.base.check(schema)

[2] The old code calls base.check()...

>> -            members = list(self.base.members)
x>> -        else:
>> -            members = []
>> -        seen = {}
>> -        for m in members:
>> -            assert c_name(m.name) not in seen
>> -            seen[m.name] = m

...then adds each of base's members into seen.

>> +            self.base.check_qmp(schema, seen)

The new code combines all of those actions under the helper
base.check_qmp().

>>          for m in self.local_members:
>> -            m.check(schema, members, seen)
>> +            m.check(schema, seen)
>>          if self.variants:
>> -            self.variants.check(schema, members, seen)
>> -        self.members = members
>> +            self.variants.check(schema, seen)
>> +        self.members = seen.values()

Nothing else in child calls check_qmp().

>> +
>> +    # Check that this type does not introduce QMP collisions into seen
>> +    def check_qmp(self, schema, seen):
>> +        self.check(schema)
>> +        assert not self.variants       # not implemented
>> +        for m in self.members:
>> +            m.check(schema, seen)
> 
> You said "ObjectType.check_qmp() is an idempotent subset of check()",
> but it's obviously a superset: it calls check(), then does some more
> work.

See [2] above. I need to reword that then, or split it into a separate
patch for easier reasoning.  base.check_qmp() is a subset of the work
done by child.check().  You are correct that it is NOT a subset of the
work done by base.check() (because it calls base.check() and then does
additional work).

> 
> I think I'm now too confused to make further progress on this patch,
> probably because I've thought myself into a corner.
> 
> Before I give up, a remark on design.  The QAPISchemaFOO classes all
> implement the same protocol:
> 
> * __init__() type-checks arguments and initializes instance variables,
>   generally either to an argument or to None.  This is basically AST
>   construction.
> 
> * check() computes the remaining instance variables.  This is semantic
>   analysis, except it's stubbed out.
> 
>   QAPISchema.__init__() calls its own check(), which calls all the
>   others, directly (for entities), or indirect (for members and such).
>   Each check() runs *once*.

And I'm intentionally reworking things to run a _subset_ of check()
multiple times - namely, calling member.check(seen) to see if member
collides with any names already present in seen, where seen can be
either the set of inherited non-variant fields (for both local members
and for the fields of a variant type from a qapi union), or where seen
can be the set of tag names (for the use of QAPISchemaObjectTypeVariant,
which is a subclass of QAPISchemaObjectTypeMember).

> 
>   Except for QAPISchemaType.check().  Why?  Unlike other entities, the
>   types need to be checked in a certain order: contained types (base and
>   variant) before the containing type.  For simplicity, we simply call
>   their check(), and detect cycles.  This is basically a topological
>   sort and the real checking squashed together.  The real checking still
>   runs once.
> 
>   It follows that you must not call check() except:
> 
>   - An entity is responsible for calling check() for the non-entities it
>     owns (e.g. an object type's check() calls its members' check()).
> 
>   - A type may call check() for a type it contains (e.g. its base type).
>     That's safe, because no type may contain itself.  This kind of call
>     drives the top-sort.
> 
> * Obviously, the instance variables computed by check() have valid
>   values only after check().  Likewise, certain methods should be called
>   only after check(), e.g. visit().
> 
> Of course, if we find a more suitable protocol, we're free to adopt it.
> 
>>
>>      def is_implicit(self):
>>          # See QAPISchema._make_implicit_object_type()
>> @@ -1027,11 +1027,13 @@ class QAPISchemaObjectTypeMember(object):
>>          self.type = None
>>          self.optional = optional
>>
>> -    def check(self, schema, all_members, seen):
>> +    def check(self, schema, seen):
>> +        # seen is a map of names we must not collide with (either QMP
>> +        # names, when called by ObjectType, or case names, when called
>> +        # by Variant). This method is safe to call over multiple 'seen'.
> 
> What are "QMP names"?  Member names, perhaps?

Yes, the member names that result from JSON object keys at the same
level of nesting, whether or not those names are attributed to the same
C namespace.

I still like my patch, but I can see it caused some confusion. So I'll
try to break it into smaller pieces for v9.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

signature.asc
Description: OpenPGP digital signature