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

[Markus Armbruster]

Eric Blake <address@hidden> writes:

> Now that we have separate namespaces for QMP vs. tag values,

What's the "QMP namespace"?

> 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?

>              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().  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.

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).

* 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.

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().

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().

> 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 :)

>                                                 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(-)
>
> 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()?

>          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)
> -            members = list(self.base.members)
> -        else:
> -            members = []
> -        seen = {}
> -        for m in members:
> -            assert c_name(m.name) not in seen
> -            seen[m.name] = m
> +            self.base.check_qmp(schema, seen)
>          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()
> +
> +    # 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.

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*.

  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?

>          assert self.name not in seen
>          self.type = schema.lookup_type(self._type_name)
>          assert self.type
> -        all_members.append(self)
>          seen[self.name] = self
>
>
> @@ -1050,26 +1052,35 @@ class QAPISchemaObjectTypeVariants(object):
>          self.tag_member = tag_member
>          self.variants = variants
>
> -    def check(self, schema, members, seen):
> +    # TODO drop union once alternates can be distinguished by tag_member
> +    def check(self, schema, seen, union=True):
>          if self.tag_name:    # flat union
>              self.tag_member = seen[self.tag_name]
> +            assert self.tag_member
>          elif seen:           # simple union
>              assert self.tag_member in seen.itervalues()
>          else:                # alternate
> -            self.tag_member.check(schema, members, seen)
> +            self.tag_member.check(schema, seen)
>          assert isinstance(self.tag_member.type, QAPISchemaEnumType)
> +        cases = OrderedDict()
>          for v in self.variants:
> -            vseen = dict(seen)
> -            v.check(schema, self.tag_member.type, vseen)
> +            # Reset seen array for each variant, since QMP names from one
> +            # branch do not affect another branch, nor add to all_members
> +            v.check(schema, self.tag_member.type, dict(seen), cases, union)
>
>
>  class QAPISchemaObjectTypeVariant(QAPISchemaObjectTypeMember):
>      def __init__(self, name, typ):
>          QAPISchemaObjectTypeMember.__init__(self, name, typ, False)
>
> -    def check(self, schema, tag_type, seen):
> -        QAPISchemaObjectTypeMember.check(self, schema, [], seen)
> +    # TODO drop union once alternates can be distinguished by tag_type
> +    def check(self, schema, tag_type, seen, cases, union):
> +        # cases is case names we must not collide with
> +        QAPISchemaObjectTypeMember.check(self, schema, cases)
>          assert self.name in tag_type.values
> +        if union:
> +            # seen is QMP names our members must not collide with
> +            self.type.check_qmp(schema, seen)
>
>      # This function exists to support ugly simple union special cases
>      # TODO get rid of them, and drop the function
> @@ -1090,7 +1101,7 @@ class QAPISchemaAlternateType(QAPISchemaType):
>          self.variants = variants
>
>      def check(self, schema):
> -        self.variants.check(schema, [], {})
> +        self.variants.check(schema, {}, False)
>
>      def json_type(self):
>          return 'value'