836816 - WebIDL parser should enforce spec restrictions on dictionary member types

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, defect)

Description

[Boris Zbarsky [:bzbarsky]]

dictionary Foo {
  Foo foo;
};

is invalid per spec, but our parser lets it through; codegen then catches the problem.  It would be better to have the parser detect this, I think.

Comment 1

[Pranav Ravichandran [:pranavrc]]

Hi! I'm willing to work on this bug. I went through the spec and I've started to look at dom/bindings/parser/WebIDL.py (hopefully the right place), but I haven't quite zeroed in on the relevant code yet. Should this check be implemented under the IDLDictionary class constructor? Also, I work with Linux, but the platform specifies Mac OS X. Is that a problem?

Comment 2

[Boris Zbarsky [:bzbarsky]]

Pranav, thanks!

That file is the right place.  The right place for the check is probably the "finish" member of the IDLDictionary class, though you could presumably also do it in "validate".

It shouldn't matter which OS you're on for this bug, as long as it has Python.  ;)

Comment 3

[Pranav Ravichandran [:pranavrc]]

Attachment: patch v1

Here's a rudimentary patch; returns TEST-UNEXPECTED-FAIL with an unhandled exception for the corresponding test written.

Comment 4

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 711903 [details] [diff] [review]
patch v1

That's a reasonable start.  You probably want to use a WebIDLError and add in the other checks the spec calls for.  And change the test to expect an exception.

Comment 5

[Pranav Ravichandran [:pranavrc]]

I changed the code to raise a WebIDLError and to expect an exception, but I'm not quite sure about the additional specifications required. There were a few things I checked, such as, the default value being an enum value in case of enum type, the lexicographical order of members et al, and they seem to be implemented already. What am I missing?

Comment 6

[Boris Zbarsky [:bzbarsky]]

Oh, sorry.  The part of the spec this bug is about is this part at http://dev.w3.org/2006/webapi/WebIDL/#idl-dictionaries :

  The type of a dictionary member MUST NOT include the dictionary it appears on. A type
  includes a dictionary D if at least one of the following is true:

    the type is D
    the type is a dictionary that inherits from D
    the type is a nullable type whose inner type includes D
    the type is a sequence type or array type whose element type includes D
    the type is a union type, one of whose member types includes D
    the type is a dictionary, one of whose members or inherited members has a type that
      includes D

Comment 7

[Pranav Ravichandran [:pranavrc]]

Ah, right, thanks! Looks like I was going through an older version of the spec. Will attach the new patch.

Comment 8

[Pranav Ravichandran [:pranavrc]]

Attachment: Patch v2

Comment 9

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 713344 [details] [diff] [review]
Patch v2

You probably want to undo the random whitespace changes.

As far as the code itself, a few comments.

First, "memberType.name == self.identifier.name" is probably better written as "memberType.inner = self".  Similar for "memberType.inner.parent == self" for the second branch of that if.

Second, I believe this code will fail to error out in the following case:

  dictionary Foo {
    sequence<sequence<Foo>> member;
  };

It would be clearer to align the algorithm more closely with the spec by defining a callback function inside validate like so:

  def containsDictionary(type, dictionary):
      # Do what the spec says here, calling containsDictionary recursively as
      # needed.  The return value should probably be a tuple whose first
      # element is a boolean and whose second element is either None if the
      # boolean is False or the location of the type that triggered a True
      # return value.  Or the second element could be a list of locations if 
      # we want really good error reporting.

and then you'd just do (assuming a tuple with list of locations):

  for member in self.members:
    (contains, locations) = containsDictionary(member.type, self)
    if contains:
      raise WebIDLError("Dictionary %s has member containing itself" %
                        self.identifier.name,
                        [member.location]+locations) 


or something along those lines.

Comment 10

[Pranav Ravichandran [:pranavrc]]

Attachment: Patch v3

Comment 11

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 713465 [details] [diff] [review]
Patch v3

>+++ b/dom/bindings/parser/WebIDL.py
>+        def containsDictionary(memberType, dictionary):
>+            if memberType.isDictionary():
>+                if memberType.inner == dictionary or \
>+                   (memberType.inner.parent and \
>+                   memberType.inner.parent == dictionary):

  if (memberType.inner == dictionary or
      memberType.inner.parent == dictionary):

please, if you want the test to be as above.  But I think you actually want to walk the entire ancestor chain, not just the parent.  Please add a test for the case when the member is a dictionary whose grandparent is the original dictionary.

>+                    return (True, memberType.location)

That second tuple member should be [memberType.location], no?  Did you check that the exception that's thrown in this case is actually the right now, not an exception from trying to add lists and location objects, as I suspect it is?

>+                else:

No need for else after return.

>+                    if memberType.inner.parent:
>+                        inheritedMembers = memberType.inner.parent.members
>+                    for member in memberType.inner.members + inheritedMembers:
>+                        if containsDictionary(member.type, dictionary)[0]:
>+                            return (True, member.type.location)

I'm not sure what this is aiming to do, but it's also not dealing with grandparents....

>+            if memberType.isUnion() and \
>+               memberType.hasDictionaryType:
>+                return (True, memberType.location)

This seems wrong: the dictionary type could be some other dictionary.  Here you need to call the function recursively on the flat member types of memberType.

And again, you will want to return a list as your second tuple element.

>+            if memberType.nullable() or \
>+               memberType.isSequence() or \
>+               memberType.isArray():
>+                return containsDictionary(memberType.inner, dictionary)

The nullable() check should be first.  Otherwise this:

  dictionary D {};
  dictionary E {
    D? member;
  };

will end up throwing parse-time exceptions, I believe.  Check that it does with your patch, then add a test?

Also, the idea of returning a list, if that's what you're trying to do, is that this way we end up with the full path through the typegraph to the offending point in the locations list.  If you're not going to try to do that, just return a single location, not a list...

As far as tests go, a test like this:

+        parser.parse("""
+            dictionary Foo {
+              sequence<sequence<Foo>> c;
+              (Foo or DOMString)[] d;
+            };
+        """)

doesn't tell you anything about whether "sequence<sequence<Foo>>" is allowed inside Foo, right?  You want to put the array bit in a separate test.

Comment 12

[Pranav Ravichandran [:pranavrc]]

Attachment: Patch v4

Comment 13

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 714773 [details] [diff] [review]
Patch v4

Can you please document what the contract is for the locations list passed to these functions?  I can't tell whether they're dealing with it correctly or not, because I'm not sure what exactly they're _trying_ to do.

Comment 14

[Pranav Ravichandran [:pranavrc]]

Attachment: Patch v5

New to Contracts, so I'm not sure if that's valid Contract Documentation, but I gave it a try :)

When I try to print the locations, this is the kind of output I get: 

(Here's the one for the test "Member type must not be a Dictionary that inherits from its Dictionary.")

<unknown> line 6:12
            dictionary Foo2 : Foo3 {
            ^
<unknown> line 6:12
            dictionary Foo2 : Foo3 {
            ^
<unknown> line 2:12
            dictionary Foo3 : Foo {
            ^
<unknown> line 14:12
            dictionary Foo {
            ^

I'm not sure what the '<unknown>' signifies here, there's this line in the Location class constructor:

self._file = filename if filename else "<unknown>"

but I haven't found out where it's being instantiated without the 'filename' parameter.

Comment 15

[Boris Zbarsky [:bzbarsky]]

I wasn't using "contract" in any sort of formal sense; just a description of what's supposed to happen.

The general description for containsDictionary would perhaps be best as:

  errorLocations: a list of locations that leads from the dictionary currently being
                  validated to the type that was passed in the memberType argument.

I should note that there is no need to pass in this list, if that's what you want it to be.  You can just build as you return back out the nested function invocations if the "contains" boolean is true.  Something like this:

  (contains, locations) = containsDictionary(member, dictionary)
  if contains:
    return (True, [ member.location ] + locations)

or some such.  In any case, it's worth carefully thinking about the locations you want to be adding.  For example, the output in comment 14 is missing a key piece of information: the actual member of type Foo2.

The <unknown> is the filename as you noted; for the tests it's always unknown, but for actual WebIDL files it'll be the WebIDL file.

Comment 16

[Pranav Ravichandran [:pranavrc]]

Attachment: Patch v6

Here's the output when I print the locations:

http://pastebin.mozilla.org/2169123

Comment 17

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 717461 [details] [diff] [review]
Patch v6

This is much much better!

>+            Returns a list of locations that leads from the dictionary currently being
>+            validated to the type that was passed in the memberType argument, if
>+            validation passes. If validation fails, returns None.

The return value is actually a tuple.  The second member is the list or None, and it's a list if the first member is True, None if the first member is False.  The first member is what determines whether memberType contains the dictionary.

>+        def checkAncestors(dictMember, dictionary):

This is where we do the check for dictMember.members containing "dictionary", right?  But this code is only called if dictMember.parent is not None?  How does that handle this case:

  dictionary Foo {
    dictionary Bar;
  };

  dictionary Bar {
    dictionary Foo;
  }

?

Given that this also checks the dictionary members, maybe it makes sense to rename "containsDictionary" to "typeContainsDictionary" and rename "checkAncestors" to "dictionaryContainsDictionary"?

Apart from those nits, this is looking great!  Some nits on the test:


>+    harness.ok(threw, "Member type must not be a Nullable type that "
>+              "whose inner type includes its Dictionary.")

Fix the indent to line up the strings, and drop the "that" before "whose".

>+    harness.ok(threw, "Nullable type check must be before Dictionary check, "
>+               "as Nullable types contain isDictionary() too.")

There is nothing nullable in that test.  What is it trying to test?

Sorry for the lag here; weekend plus being sick.  :(

Comment 18

[Pranav Ravichandran [:pranavrc]]

> There is nothing nullable in that test.  What is it trying to test?

I initially added it when the nullable() test was after the isDictionary() test. This threw exceptions because a nullable type contains the isDictionary() check too. So I moved the nullable, array and sequence checks above the isDictionary() check, and now the test isn't required, I guess, because there's no exception thrown. Didn't realize that array types don't support dictionaries as inner elements. I'll remove the test.

> Sorry for the lag here; weekend plus being sick.  :(

No problem!

Here's the new patch.

Comment 19

[Pranav Ravichandran [:pranavrc]]

Attachment: Patch v7

Comment 20

[Boris Zbarsky [:bzbarsky]]

Array types do support dictionaries as inner elements....

Comment 21

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 718842 [details] [diff] [review]
Patch v7

>+                    A list of locations that leads from the dictionary currently being
>+                    validated

It actually leads from the memberType to the dictionary, no?  I guess it depends on which order you think of them in....

r=me.  We're way out of the feedback stage here.  ;)

Comment 22

[Pranav Ravichandran [:pranavrc]]

Attachment: Patch v8

Comment 23

[Pranav Ravichandran [:pranavrc]]

(In reply to Boris Zbarsky (:bz) from comment #20)
> Array types do support dictionaries as inner elements....

I read about the array inner-type restrictions in http://dev.w3.org/2006/webapi/WebIDL/#idl-array but I think I might be missing something obvious :/

Comment 24

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 718856 [details] [diff] [review]
Patch v8

r=me.

Good catch about the element types of an array not being allowed to be sequences or dictionaries.  We should add validation for that in the parser!  Want to do it?  ;)

Comment 25

[Pranav Ravichandran [:pranavrc]]

Thanks for the check-in! And yep, I'll start working on that ;)

Comment 26

[Boris Zbarsky [:bzbarsky]]

Thanks for sticking with this through so many iterations.  ;)

https://hg.mozilla.org/integration/mozilla-inbound/rev/95d500777957

Comment 27

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/95d500777957