Bug 763724. Detect cycles in the interface inheritance and implementation graph. r=jlebar
authorBoris Zbarsky <bzbarsky@mit.edu>
Thu, 21 Jun 2012 12:29:11 -0400
changeset 102093 5de10f87c56e971dda9b0718d90f9a4febfa1e4f
parent 102092 da942dd41b43a3fa6c72725d766edbab06717569
child 102094 6f0cb242f0e623dba6fc79d92fa6832bcdac336f
push idunknown
push userunknown
push dateunknown
reviewersjlebar
bugs763724
milestone16.0a1
Bug 763724. Detect cycles in the interface inheritance and implementation graph. r=jlebar
dom/bindings/parser/WebIDL.py
dom/bindings/parser/tests/test_dictionary.py
dom/bindings/parser/tests/test_interface.py
--- a/dom/bindings/parser/WebIDL.py
+++ b/dom/bindings/parser/WebIDL.py
@@ -421,16 +421,23 @@ class IDLInterface(IDLObjectWithScope):
             # anything that has consequential interfaces.
             if self.isCallback():
                 assert(self.parent.isCallback())
                 assert(len(self.parent.getConsequentialInterfaces()) == 0)
 
         for iface in self.implementedInterfaces:
             iface.finish(scope)
 
+        cycleInGraph = self.findInterfaceLoopPoint(self)
+        if cycleInGraph:
+            raise WebIDLError("Interface %s has itself as ancestor or "
+                              "implemented interface" % self.identifier.name,
+                              self.location,
+                              extraLocation=cycleInGraph.location)
+
         # Now resolve() and finish() our members before importing the
         # ones from our implemented interfaces.
 
         # resolve() will modify self.members, so we need to iterate
         # over a copy of the member list here.
         for member in list(self.members):
             member.resolve(self)
 
@@ -589,16 +596,36 @@ class IDLInterface(IDLObjectWithScope):
 
         # And now collect up the consequential interfaces of all of those
         temp = set()
         for iface in consequentialInterfaces:
             temp |= iface.getConsequentialInterfaces()
 
         return consequentialInterfaces | temp
 
+    def findInterfaceLoopPoint(self, otherInterface):
+        """
+        Finds an interface, amongst our ancestors and consequential interfaces,
+        that inherits from otherInterface or implements otherInterface
+        directly.  If there is no such interface, returns None.
+        """
+        if self.parent:
+            if self.parent == otherInterface:
+                return self
+            loopPoint = self.parent.findInterfaceLoopPoint(otherInterface)
+            if loopPoint:
+                return loopPoint
+        if otherInterface in self.implementedInterfaces:
+            return self
+        for iface in self.implementedInterfaces:
+            loopPoint = iface.findInterfaceLoopPoint(otherInterface)
+            if loopPoint:
+                return loopPoint
+        return None
+
 class IDLDictionary(IDLObjectWithScope):
     def __init__(self, location, parentScope, name, parent, members):
         assert isinstance(parentScope, IDLScope)
         assert isinstance(name, IDLUnresolvedIdentifier)
         assert not parent or isinstance(parent, IDLIdentifierPlaceholder)
 
         self.parent = parent
         self._finished = False
--- a/dom/bindings/parser/tests/test_dictionary.py
+++ b/dom/bindings/parser/tests/test_dictionary.py
@@ -1,10 +1,8 @@
-import WebIDL
-
 def WebIDLTest(parser, harness):
     parser.parse("""
       dictionary Dict2 : Dict1 {
         long child = 5;
         Dict1 aaandAnother;
       };
       dictionary Dict1 {
         long parent;
@@ -24,33 +22,33 @@ def WebIDLTest(parser, harness):
     harness.check(dict1.members[1].identifier.name, "parent",
                   "'o' really comes before 'p'")
     harness.check(dict2.members[0].identifier.name, "aaandAnother",
                   "'a' comes before 'c'")
     harness.check(dict2.members[1].identifier.name, "child",
                   "'a' really comes before 'c'")
 
     # Now reset our parser
-    parser = WebIDL.Parser()
+    parser = parser.reset()
     threw = False
     try:
         parser.parse("""
           dictionary Dict {
             long prop = 5;
             long prop;
           };
         """)
         results = parser.finish()
     except:
         threw = True
 
     harness.ok(threw, "Should not allow name duplication in a dictionary")
 
     # Now reset our parser again
-    parser = WebIDL.Parser()
+    parser = parser.reset()
     threw = False
     try:
         parser.parse("""
           dictionary Dict1 : Dict2 {
             long prop = 5;
           };
           dictionary Dict2 : Dict3 {
             long prop2;
@@ -62,33 +60,33 @@ def WebIDLTest(parser, harness):
         results = parser.finish()
     except:
         threw = True
 
     harness.ok(threw, "Should not allow name duplication in a dictionary and "
                "its ancestor")
 
     # More reset
-    parser = WebIDL.Parser()
+    parser = parser.reset()
     threw = False
     try:
         parser.parse("""
           interface Iface {};
           dictionary Dict : Iface {
             long prop;
           };
         """)
         results = parser.finish()
     except:
         threw = True
 
     harness.ok(threw, "Should not allow non-dictionary parents for dictionaries")
 
     # Even more reset
-    parser = WebIDL.Parser()
+    parser = parser.reset()
     threw = False
     try:
         parser.parse("""
             dictionary A : B {};
             dictionary B : A {};
         """)
         results = parser.finish()
     except:
--- a/dom/bindings/parser/tests/test_interface.py
+++ b/dom/bindings/parser/tests/test_interface.py
@@ -47,8 +47,129 @@ def WebIDLTest(parser, harness):
     base = results[0]
     derived = results[1]
     harness.check(base.members[0].identifier.QName(), "::QNameBase::foo",
                   "Member has the right QName")
     harness.check(derived.members[0].identifier.QName(), "::QNameDerived::foo",
                   "Member has the right QName")
     harness.check(derived.members[1].identifier.QName(), "::QNameDerived::bar",
                   "Member has the right QName")
+
+    parser = parser.reset()
+    threw = False
+    try:
+        parser.parse("""
+            interface A : B {};
+            interface B : A {};
+        """)
+        results = parser.finish()
+    except:
+        threw = True
+
+    harness.ok(threw, "Should not allow cycles in interface inheritance chains")
+
+    parser = parser.reset()
+    threw = False
+    try:
+        parser.parse("""
+            interface A : C {};
+            interface C : B {};
+            interface B : A {};
+        """)
+        results = parser.finish()
+    except:
+        threw = True
+
+    harness.ok(threw, "Should not allow indirect cycles in interface inheritance chains")
+
+    parser = parser.reset()
+    threw = False
+    try:
+        parser.parse("""
+            interface A {};
+            interface B {};
+            A implements B;
+            B implements A;
+        """)
+        results = parser.finish()
+    except:
+        threw = True
+
+    harness.ok(threw, "Should not allow cycles via implements")
+
+    parser = parser.reset()
+    threw = False
+    try:
+        parser.parse("""
+            interface A {};
+            interface C {};
+            interface B {};
+            A implements C;
+            C implements B;
+            B implements A;
+        """)
+        results = parser.finish()
+    except:
+        threw = True
+
+    harness.ok(threw, "Should not allow indirect cycles via implements")
+
+    parser = parser.reset()
+    threw = False
+    try:
+        parser.parse("""
+            interface A : B {};
+            interface B {};
+            B implements A;
+        """)
+        results = parser.finish()
+    except:
+        threw = True
+
+    harness.ok(threw, "Should not allow inheriting from an interface that implements us")
+
+    parser = parser.reset()
+    threw = False
+    try:
+        parser.parse("""
+            interface A : B {};
+            interface B {};
+            interface C {};
+            B implements C;
+            C implements A;
+        """)
+        results = parser.finish()
+    except:
+        threw = True
+
+    harness.ok(threw, "Should not allow inheriting from an interface that indirectly implements us")
+
+    parser = parser.reset()
+    threw = False
+    try:
+        parser.parse("""
+            interface A : B {};
+            interface B : C {};
+            interface C {};
+            C implements A;
+        """)
+        results = parser.finish()
+    except:
+        threw = True
+
+    harness.ok(threw, "Should not allow indirectly inheriting from an interface that implements us")
+
+    parser = parser.reset()
+    threw = False
+    try:
+        parser.parse("""
+            interface A : B {};
+            interface B : C {};
+            interface C {};
+            interface D {};
+            C implements D;
+            D implements A;
+        """)
+        results = parser.finish()
+    except:
+        threw = True
+
+    harness.ok(threw, "Should not allow indirectly inheriting from an interface that indirectly implements us")