Bug 564086: Frontend support for IPDL process graphs and Bridge()ing processes. r=benjamn
authorChris Jones <jones.chris.g@gmail.com>
Sat, 22 May 2010 14:35:31 -0500
changeset 42560 0f37ae194f8f4f409174cd7014ab19ed43d22475
parent 42559 7c27cdcee4762a86063b7b69e569dd208d5d9eaa
child 42561 4254363b9c635df43e2fff78392cdff960a35785
push id13404
push usercjones@mozilla.com
push dateSat, 22 May 2010 19:33:57 +0000
treeherdermozilla-central@721817fd5753 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbenjamn
bugs564086
milestone1.9.3a5pre
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
Bug 564086: Frontend support for IPDL process graphs and Bridge()ing processes. r=benjamn
ipc/ipdl/ipdl/ast.py
ipc/ipdl/ipdl/parser.py
ipc/ipdl/ipdl/type.py
ipc/ipdl/test/ipdl/error/bridgesNonexistent.ipdl
ipc/ipdl/test/ipdl/error/bridgesSubprotocol.ipdl
ipc/ipdl/test/ipdl/error/spawnsNonexistent.ipdl
ipc/ipdl/test/ipdl/error/spawnsSubprotocol.ipdl
ipc/ipdl/test/ipdl/error/subprotocolBridges.ipdl
ipc/ipdl/test/ipdl/error/subprotocolSpawns.ipdl
ipc/ipdl/test/ipdl/ok/compositor.ipdl
ipc/ipdl/test/ipdl/ok/content.ipdl
ipc/ipdl/test/ipdl/ok/jetpack.ipdl
ipc/ipdl/test/ipdl/ok/jetpackContent.ipdl
ipc/ipdl/test/ipdl/ok/plugin.ipdl
--- a/ipc/ipdl/ipdl/ast.py
+++ b/ipc/ipdl/ipdl/ast.py
@@ -61,28 +61,38 @@ class Visitor:
             t.accept(self)
 
     def visitUsingStmt(self, using):
         pass
 
     def visitProtocol(self, p):
         for namespace in p.namespaces:
             namespace.accept(self)
+        for spawns in p.spawnsStmts:
+            spawns.accept(self)
+        for bridges in p.bridgesStmts:
+            bridges.accept(self)
         for mgr in p.managers:
             mgr.accept(self)
         for managed in p.managesStmts:
             managed.accept(self)
         for msgDecl in p.messageDecls:
             msgDecl.accept(self)
         for transitionStmt in p.transitionStmts:
             transitionStmt.accept(self)
 
     def visitNamespace(self, ns):
         pass
 
+    def visitSpawnsStmt(self, spawns):
+        pass
+
+    def visitBridgesStmt(self, bridges):
+        pass
+
     def visitManager(self, mgr):
         pass
 
     def visitManagesStmt(self, mgs):
         pass
 
     def visitMessageDecl(self, md):
         for inParam in md.inParams:
@@ -244,36 +254,42 @@ class Namespace(Node):
     def __init__(self, loc, namespace):
         Node.__init__(self, loc)
         self.name = namespace
 
 class Protocol(NamespacedNode):
     def __init__(self, loc):
         NamespacedNode.__init__(self, loc)
         self.sendSemantics = ASYNC
+        self.spawnsStmts = [ ]
+        self.bridgesStmts = [ ]
         self.managers = [ ]
         self.managesStmts = [ ]
         self.messageDecls = [ ]
         self.transitionStmts = [ ]
         self.startStates = [ ]
 
-    def addManagesStmts(self, managesStmts):
-        self.managesStmts += managesStmts
-
-    def addMessageDecls(self, messageDecls):
-        self.messageDecls += messageDecls
-
-    def addTransitionStmts(self, transStmts):
-        self.transitionStmts += transStmts
-
 class UnionDecl(NamespacedNode):
     def __init__(self, loc, name, components):
         NamespacedNode.__init__(self, loc, name)
         self.components = components
 
+class SpawnsStmt(Node):
+    def __init__(self, loc, side, proto, spawnedAs):
+        Node.__init__(self, loc)
+        self.side = side
+        self.proto = proto
+        self.spawnedAs = spawnedAs
+
+class BridgesStmt(Node):
+    def __init__(self, loc, parentSide, childSide):
+        Node.__init__(self, loc)
+        self.parentSide = parentSide
+        self.childSide = childSide
+
 class Manager(Node):
     def __init__(self, loc, managerName):
         Node.__init__(self, loc)
         self.name = managerName
 
 class ManagesStmt(Node):
     def __init__(self, loc, managedName):
         Node.__init__(self, loc)
--- a/ipc/ipdl/ipdl/parser.py
+++ b/ipc/ipdl/ipdl/parser.py
@@ -136,18 +136,20 @@ class Parser:
 def locFromTok(p, num):
     return Loc(Parser.current.filename, p.lineno(num))
 
 
 ##-----------------------------------------------------------------------------
 
 reserved = set((
         'answer',
+        'as',
         'async',
         'both',
+        'bridges',
         'call',
         'child',
         '__delete__',
         'delete',                       # reserve 'delete' to prevent its use
         'goto',
         'include',
         'manager',
         'manages',
@@ -155,16 +157,17 @@ reserved = set((
         'nullable',
         'or',
         'parent',
         'protocol',
         'recv',
         'returns',
         'rpc',
         'send',
+        'spawns',
         'start',
         'state',
         'sync',
         'union',
         'using'))
 tokens = [
     'COLONCOLON', 'ID', 'STRING'
 ] + [ r.upper() for r in reserved ]
@@ -302,72 +305,119 @@ def p_ComponentTypes(p):
                       | Type ';'"""
     if 3 == len(p):
         p[0] = [ p[1] ]
     else:
         p[1].append(p[2])
         p[0] = p[1]
 
 def p_ProtocolDefn(p):
-    """ProtocolDefn : OptionalSendSemanticsQual PROTOCOL ID '{' ManagersStmtOpt ManagesStmts OptionalMessageDecls TransitionStmts '}' ';'"""
-    protocol = Protocol(locFromTok(p, 2))
+    """ProtocolDefn : OptionalSendSemanticsQual PROTOCOL ID '{' ProtocolBody '}' ';'"""
+    protocol = p[5]
+    protocol.loc = locFromTok(p, 2)
     protocol.name = p[3]
     protocol.sendSemantics = p[1]
-    protocol.managers = p[5]   
-    protocol.addManagesStmts(p[6])
-    protocol.addMessageDecls(p[7])
-    protocol.addTransitionStmts(p[8])
     p[0] = protocol
 
-def p_ManagesStmts(p):
-    """ManagesStmts : ManagesStmts ManagesStmt
-                    | """
-    if 1 == len(p):
-        p[0] = [ ]
+def p_ProtocolBody(p):
+    """ProtocolBody : SpawnsStmtsOpt"""
+    p[0] = p[1]
+
+##--------------------
+## spawns/bridges stmts
+
+def p_SpawnsStmtsOpt(p):
+    """SpawnsStmtsOpt : SpawnsStmt SpawnsStmtsOpt
+                      | BridgesStmtsOpt"""
+    if 2 == len(p):
+        p[0] = p[1]
     else:
-        p[1].append(p[2])
+        p[2].spawnsStmts.insert(0, p[1])
+        p[0] = p[2]
+
+def p_SpawnsStmt(p):
+    """SpawnsStmt : PARENT SPAWNS ID AsOpt ';'
+                  | CHILD SPAWNS ID AsOpt ';'"""
+    p[0] = SpawnsStmt(locFromTok(p, 1), p[1], p[3], p[4])
+
+def p_AsOpt(p):
+    """AsOpt : AS PARENT
+             | AS CHILD
+             | """
+    if 3 == len(p):
+        p[0] = p[2]
+    else:
+        p[0] = 'child'
+
+def p_BridgesStmtsOpt(p):
+    """BridgesStmtsOpt : BridgesStmt BridgesStmtsOpt
+                       | ManagersStmtOpt"""
+    if 2 == len(p):
         p[0] = p[1]
+    else:
+        p[2].bridgesStmts.insert(0, p[1])
+        p[0] = p[2]
+
+def p_BridgesStmt(p):
+    """BridgesStmt : BRIDGES ID ',' ID ';'"""
+    p[0] = BridgesStmt(locFromTok(p, 1), p[2], p[4])
+
+##--------------------
+## manager/manages stmts
 
 def p_ManagersStmtOpt(p):
-    """ManagersStmtOpt : MANAGER ManagerList ';'
-                       | """
+    """ManagersStmtOpt : ManagersStmt ManagesStmtsOpt
+                       | ManagesStmtsOpt"""
+    if 2 == len(p):
+        p[0] = p[1]
+    else:
+        p[2].managers = p[1]
+        p[0] = p[2]
+
+def p_ManagersStmt(p):
+    """ManagersStmt : MANAGER ManagerList ';'"""
     if 1 == len(p):
         p[0] = [ ]
     else:
         p[0] = p[2]
 
 def p_ManagerList(p):
     """ManagerList : ID
                    | ManagerList OR ID"""
     if 2 == len(p):
         p[0] = [ Manager(locFromTok(p, 1), p[1]) ]
     else:
         p[1].append(Manager(locFromTok(p, 3), p[3]))
         p[0] = p[1]
 
+def p_ManagesStmtsOpt(p):
+    """ManagesStmtsOpt : ManagesStmt ManagesStmtsOpt
+                       | MessageDeclsOpt"""
+    if 2 == len(p):
+        p[0] = p[1]
+    else:
+        p[2].managesStmts.insert(0, p[1])
+        p[0] = p[2]
+
 def p_ManagesStmt(p):
     """ManagesStmt : MANAGES ID ';'"""
     p[0] = ManagesStmt(locFromTok(p, 1), p[2])
 
-def p_OptionalMessageDecls(p):
-    """OptionalMessageDecls : MessageDecls
-                            | """
+
+##--------------------
+## Message decls
+
+def p_MessageDeclsOpt(p):
+    """MessageDeclsOpt : MessageDeclThing MessageDeclsOpt
+                       | TransitionStmtsOpt"""
     if 2 == len(p):
         p[0] = p[1]
     else:
-        p[0] = [ ]
-
-def p_MessageDecls(p):
-    """MessageDecls : MessageDecls MessageDeclThing
-                    | MessageDeclThing"""
-    if 2 == len(p):
-        p[0] = [ p[1] ]
-    else:
-        p[1].append(p[2])
-        p[0] = p[1]
+        p[2].messageDecls.insert(0, p[1])
+        p[0] = p[2]
 
 def p_MessageDeclThing(p):
     """MessageDeclThing : MessageDirectionLabel ':' MessageDecl ';'
                         | MessageDecl ';'"""
     if 3 == len(p):
         p[0] = p[1]
     else:
         p[0] = p[3]
@@ -428,32 +478,25 @@ def p_MessageOutParams(p):
     if 1 == len(p):
         p[0] = [ ]
     else:
         p[0] = p[3]
 
 ##--------------------
 ## State machine
 
-def p_TransitionStmts(p):
-    """TransitionStmts : TransitionStmtsNonEmpty
-                       | """
-    if 2 == len(p):
-        p[0] = p[1]
+def p_TransitionStmtsOpt(p):
+    """TransitionStmtsOpt : TransitionStmt TransitionStmtsOpt
+                          |"""
+    if 1 == len(p):
+        # we fill in |loc| in the Protocol rule
+        p[0] = Protocol(None)
     else:
-        p[0] = [ ]
-
-def p_TransitionStmtsNonEmpty(p):
-    """TransitionStmtsNonEmpty : TransitionStmtsNonEmpty TransitionStmt
-                               | TransitionStmt"""
-    if 3 == len(p):
-        p[1].append(p[2])
-        p[0] = p[1]
-    elif 2 == len(p):
-        p[0] = [ p[1] ]
+        p[2].transitionStmts.insert(0, p[1])
+        p[0] = p[2]
 
 def p_TransitionStmt(p):
     """TransitionStmt : OptionalStart STATE State ':' Transitions"""
     p[3].start = p[1]
     p[0] = TransitionStmt(locFromTok(p, 2), p[3], p[5])
 
 def p_OptionalStart(p):
     """OptionalStart : START
--- a/ipc/ipdl/ipdl/type.py
+++ b/ipc/ipdl/ipdl/type.py
@@ -32,16 +32,34 @@
 
 import os, sys
 
 from ipdl.ast import CxxInclude, Decl, Loc, QualifiedId, State, TransitionStmt, TypeSpec, UsingStmt, Visitor, ASYNC, SYNC, RPC, IN, OUT, INOUT, ANSWER, CALL, RECV, SEND
 import ipdl.builtin as builtin
 
 _DELETE_MSG = '__delete__'
 
+
+def _otherside(side):
+    if side == 'parent':  return 'child'
+    elif side == 'child': return 'parent'
+    else:  assert 0 and 'unknown side "%s"'% (side)
+
+def unique_pairs(s):
+    n = len(s)
+    for i, e1 in enumerate(s):
+        for j in xrange(i+1, n):
+            yield (e1, s[j])
+
+def cartesian_product(s1, s2):
+    for e1 in s1:
+        for e2 in s2:
+            yield (e1, e2)
+
+
 class TypeVisitor:
     def defaultVisit(self, node, *args):
         raise Exception, "INTERNAL ERROR: no visitor for node type `%s'"% (
             node.__class__.__name__)
 
     def visitVoidType(self, v, *args):
         pass
 
@@ -228,34 +246,56 @@ class MessageType(IPDLType):
 
     def isIn(self): return self.direction is IN
     def isOut(self): return self.direction is OUT
     def isInout(self): return self.direction is INOUT
 
     def hasImplicitActorParam(self):
         return self.isCtor() or self.isDtor()
 
+class Bridge:
+    def __init__(self, parentPtype, childPtype):
+        assert parentPtype.isToplevel() and childPtype.isToplevel()
+        self.parent = parentPtype
+        self.child = childPtype
+
+    def __cmp__(self, o):
+        return cmp(self.parent, o.parent) or cmp(self.child, o.child)
+    def __eq__(self, o):
+        return self.parent == o.parent and self.child == o.child
+    def __hash__(self):
+        return hash(self.parent) + hash(self.child)
+
 class ProtocolType(IPDLType):
     def __init__(self, qname, sendSemantics, stateless=False):
         self.qname = qname
         self.sendSemantics = sendSemantics
+        self.spawns = set()             # ProtocolType
+        self.bridges = set()            # [ Bridge ]
         self.managers = set()           # ProtocolType
         self.manages = [ ]
         self.stateless = stateless
     def isProtocol(self): return True
 
     def name(self):
         return self.qname.baseid
     def fullname(self):
         return str(self.qname)
 
     def addManager(self, mgrtype):
         assert mgrtype.isIPDL() and mgrtype.isProtocol()
         self.managers.add(mgrtype)
 
+    def addSpawn(self, ptype):
+        assert self.isToplevel() and  ptype.isToplevel()
+        self.spawns.add(ptype)
+
+    def addBridge(self, parentPType, childPType):
+        self.bridges.add(Bridge(parentPType, childPType))
+
     def managedBy(self, mgr):
         self.managers = mgr
 
     def toplevel(self):
         if self.isToplevel():
             return self
         for mgr in self.managers:
             if mgr is not self:
@@ -457,16 +497,20 @@ With this information, it finally type c
         # and location of declaration
         if not runpass(GatherDecls(builtinUsing, self.errors)):
             return False
 
         # now that the nodes have decls, type checking is much easier.
         if not runpass(CheckTypes(self.errors)):
             return False
 
+        if not (runpass(BuildProcessGraph(self.errors))
+                and runpass(CheckProcessGraph(self.errors))):
+            return False
+
         if (len(tu.protocol.startStates)
             and not runpass(CheckStateMachine(self.errors))):
             return False
         return True
 
     def reportErrors(self, errout):
         for error in self.errors:
             print >>errout, error
@@ -604,16 +648,22 @@ class GatherDecls(TcheckVisitor):
             type=ipdltype,
             shortname=using.type.basename(),
             fullname=fullname)
 
     def visitProtocol(self, p):
         # protocol scope
         self.symtab.enterScope(p)
 
+        for spawns in p.spawnsStmts:
+            spawns.accept(self)
+
+        for bridges in p.bridgesStmts:
+            bridges.accept(self)
+
         seenmgrs = set()
         for mgr in p.managers:
             if mgr.name in seenmgrs:
                 self.error(mgr.loc, "manager `%s' appears multiple times",
                            mgr.name)
                 continue
 
             seenmgrs.add(mgr.name)
@@ -737,16 +787,35 @@ class GatherDecls(TcheckVisitor):
         # be generated.  they're not relevant to IPDL itself, but
         # those ("invisible") symbols can clash with others in the
         # IPDL spec, and we'd like to catch those before C++ compilers
         # are allowed to obfuscate the error
 
         self.symtab.exitScope(p)
 
 
+    def visitSpawnsStmt(self, spawns):
+        pname = spawns.proto
+        spawns.proto = self.symtab.lookup(pname)
+        if spawns.proto is None:
+            self.error(spawns.loc,
+                       "spawned protocol `%s' has not been declared",
+                       pname)
+
+    def visitBridgesStmt(self, bridges):
+        def lookup(p):
+            decl = self.symtab.lookup(p)
+            if decl is None:
+                self.error(bridges.loc,
+                           "bridged protocol `%s' has not been declared", p)
+            return decl
+        bridges.parentSide = lookup(bridges.parentSide)
+        bridges.childSide = lookup(bridges.childSide)
+
+
     def visitManager(self, mgr):
         mgrdecl = self.symtab.lookup(mgr.name)
         pdecl = mgr.of.decl
         assert pdecl
 
         pname, mgrname = pdecl.shortname, mgr.name
         loc = mgr.loc
 
@@ -975,27 +1044,41 @@ def formatcycles(cycles):
         r.append("`%s'" % s)
     return ", ".join(r)
 
 class CheckTypes(TcheckVisitor):
     def __init__(self, errors):
         # don't need the symbol table, we just want the error reporting
         TcheckVisitor.__init__(self, None, errors)
         self.visited = set()
+        self.ptype = None
 
     def visitProtocolInclude(self, inc):
         if inc.tu.filename in self.visited:
             return
         self.visited.add(inc.tu.filename)
         inc.tu.protocol.accept(self)
 
 
     def visitProtocol(self, p):
+        self.ptype = p.decl.type
+        
         # check that we require no more "power" than our manager protocols
         ptype, pname = p.decl.type, p.decl.shortname
+
+        if len(p.spawnsStmts) and not ptype.isToplevel():
+            self.error(p.decl.loc,
+                       "protocol `%s' is not top-level and so cannot declare |spawns|",
+                       pname)
+
+        if len(p.bridgesStmts) and not ptype.isToplevel():
+            self.error(p.decl.loc,
+                       "protocol `%s' is not top-level and so cannot declare |bridges|",
+                       pname)
+
         for mgrtype in ptype.managers:
             if mgrtype is not None and ptype.needsMoreJuiceThan(mgrtype):
                 self.error(
                     p.decl.loc,
                     "protocol `%s' requires more powerful send semantics than its manager `%s' provides",
                     pname, mgrtype.name())
 
         # XXX currently we don't require a delete() message of top-level
@@ -1018,17 +1101,53 @@ class CheckTypes(TcheckVisitor):
 
         if 1 == len(ptype.managers) and ptype is ptype.manager():
             self.error(
                 p.decl.loc,
                 "top-level protocol `%s' cannot manage itself",
                 p.name)
 
         return Visitor.visitProtocol(self, p)
-        
+
+
+    def visitSpawnsStmt(self, spawns):
+        if not self.ptype.isToplevel():
+            self.error(spawns.loc,
+                       "only top-level protocols can have |spawns| statements; `%s' cannot",
+                       self.ptype.name())
+            return
+
+        spawnedType = spawns.proto.type
+        if not (spawnedType.isIPDL() and spawnedType.isProtocol()
+                and spawnedType.isToplevel()):
+            self.error(spawns.loc,
+                       "cannot spawn non-top-level-protocol `%s'",
+                       spawnedType.name())
+        else:
+            self.ptype.addSpawn(spawnedType)
+
+
+    def visitBridgesStmt(self, bridges):
+        if not self.ptype.isToplevel():
+            self.error(bridges.loc,
+                       "only top-level protocols can have |bridges| statements; `%s' cannot",
+                       self.ptype.name())
+            return
+
+        parentType = bridges.parentSide.type
+        childType = bridges.childSide.type
+        if not (parentType.isIPDL() and parentType.isProtocol()
+                and childType.isIPDL() and childType.isProtocol()
+                and parentType.isToplevel() and childType.isToplevel()):
+            self.error(bridges.loc,
+                       "cannot bridge non-top-level-protocol(s) `%s' and `%s'",
+                       parentType.name(), childType.name())
+        else:
+            self.ptype.addBridge(parentType, childType)
+
 
     def visitManagesStmt(self, mgs):
         pdecl = mgs.manager.decl
         ptype, pname = pdecl.type, pdecl.shortname
 
         mgsdecl = mgs.decl
         mgstype, mgsname = mgsdecl.type, mgsdecl.shortname
 
@@ -1116,27 +1235,245 @@ class CheckTypes(TcheckVisitor):
             self.error(
                 loc, "%s %s message `%s' is not `%s'd",
                 mtype.sendSemantics.pretty, mtype.direction.pretty,
                 t.msg.progname,
                 t.trigger.pretty)
 
 ##-----------------------------------------------------------------------------
 
-def unique_pairs(s):
-    n = len(s)
-    for i, e1 in enumerate(s):
-        for j in xrange(i+1, n):
-            yield (e1, s[j])
+class Process:
+    def __init__(self):
+        self.actors = set()         # set(Actor)
+        self.edges = { }            # Actor -> [ SpawnsEdge ]
+        self.spawn = set()          # set(Actor)
+
+    def edge(self, spawner, spawn):
+        if spawner not in self.edges:  self.edges[spawner] = [ ]
+        self.edges[spawner].append(SpawnsEdge(spawner, spawn))
+        self.spawn.add(spawn)
+
+    def iteredges(self):
+        for edgelist in self.edges.itervalues():
+            for edge in edgelist:
+                yield edge
+
+    def merge(self, o):
+        'Merge the Process |o| into this Process'
+        if self == o:
+            return
+        for actor in o.actors:
+            ProcessGraph.actorToProcess[actor] = self
+        self.actors.update(o.actors)
+        self.edges.update(o.edges)
+        self.spawn.update(o.spawn)
+        ProcessGraph.processes.remove(o)
+
+    def spawns(self, actor):
+        return actor in self.spawn
+
+    def __cmp__(self, o):  return cmp(self.actors, o.actors)
+    def __eq__(self, o):   return self.actors == o.actors
+    def __hash__(self):    return hash(id(self))
+    def __repr__(self):
+        return reduce(lambda a, x: str(a) + str(x) +'|', self.actors, '|')
+    def __str__(self):     return repr(self)
+
+class Actor:
+    def __init__(self, ptype, side):
+        self.ptype = ptype
+        self.side = side
+
+    def other(self):
+        return Actor(self.ptype, _otherside(self.side))
+
+    def __cmp__(self, o):
+        return cmp(self.ptype, o.ptype) or cmp(self.side, o.side)
+    def __eq__(self, o):
+        return self.ptype == o.ptype and self.side == o.side
+    def __hash__(self):  return hash(repr(self))
+    def __repr__(self):  return '%s%s'% (self.ptype.name(), self.side.title())
+    def __str__(self):   return repr(self)
+
+class SpawnsEdge:
+    def __init__(self, spawner, spawn):
+        self.spawner = spawner      # Actor
+        self.spawn = spawn          # Actor
+    def __repr__(self):
+        return '(%r)--spawns-->(%r)'% (self.spawner, self.spawn)
+    def __str__(self):  return repr(self)
+
+class BridgeEdge:
+    def __init__(self, bridgeProto, parent, child):
+        self.bridgeProto = bridgeProto # ProtocolType
+        self.parent = parent           # Actor
+        self.child = child             # Actor
+    def __repr__(self):
+        return '(%r)--%s bridge-->(%r)'% (
+            self.parent, self.bridgeProto.name(), self.child)
+    def __str__(self):  return repr(self)
+
+# "singleton" class with state that persists across type checking of
+# all protocols
+class ProcessGraph:
+    processes = set()                   # set(Process)
+    bridges = { }                       # ProtocolType -> BridgeEdge
+    actorToProcess = { }                # Actor -> Process
+    visitedSpawns = set()               # set(ActorType)
+    visitedBridges = set()              # set(ActorType)
+
+    @classmethod
+    def findProcess(cls, actor):
+        return cls.actorToProcess.get(actor, None)
+
+    @classmethod
+    def getProcess(cls, actor):
+        if actor not in cls.actorToProcess:
+            p = Process()
+            p.actors.add(actor)
+            cls.processes.add(p)
+            cls.actorToProcess[actor] = p
+        return cls.actorToProcess[actor]
+
+    @classmethod
+    def spawn(cls, spawner, remoteSpawn):
+        localSpawn = remoteSpawn.other()
+        spawnerProcess = ProcessGraph.getProcess(spawner)
+        spawnerProcess.merge(ProcessGraph.getProcess(localSpawn))
+        spawnerProcess.edge(spawner, remoteSpawn)
+
+    @classmethod
+    def bridge(cls, parent, child, bridgeP):
+        cls.bridges[bridgeP] = BridgeEdge(bridgeP, parent, child)
+
+
+class BuildProcessGraph(TcheckVisitor):
+    class findSpawns(TcheckVisitor):
+        def __init__(self, errors):
+            TcheckVisitor.__init__(self, None, errors)
+
+        def visitTranslationUnit(self, tu):
+            TcheckVisitor.visitTranslationUnit(self, tu)
 
-def cartesian_product(s1, s2):
-    for e1 in s1:
-        for e2 in s2:
-            yield (e1, e2)
+        def visitProtocolInclude(self, pi):
+            pi.tu.protocol.accept(self)
+
+        def visitProtocol(self, p):
+            ptype = p.decl.type
+            # non-top-level protocols don't add any information
+            if not ptype.isToplevel() or ptype in ProcessGraph.visitedSpawns:
+                return
+
+            ProcessGraph.visitedSpawns.add(ptype)
+            self.visiting = ptype
+            ProcessGraph.getProcess(Actor(ptype, 'parent'))
+            ProcessGraph.getProcess(Actor(ptype, 'child'))
+            return TcheckVisitor.visitProtocol(self, p)
+
+        def visitSpawnsStmt(self, spawns):
+            # The picture here is:
+            #  [ spawner | localSpawn | ??? ]  (process 1)
+            #                  |
+            #                  |
+            #            [ remoteSpawn | ???]  (process 2)
+            #
+            # A spawns stmt tells us that |spawner| and |localSpawn|
+            # are in the same process.
+            spawner = Actor(self.visiting, spawns.side)
+            remoteSpawn = Actor(spawns.proto.type, spawns.spawnedAs)
+            ProcessGraph.spawn(spawner, remoteSpawn)
+
+    def __init__(self, errors):
+        TcheckVisitor.__init__(self, None, errors)
+        self.visiting = None            # ActorType
+        self.visited = set()            # set(ActorType)
+
+    def visitTranslationUnit(self, tu):
+        tu.accept(self.findSpawns(self.errors))
+        TcheckVisitor.visitTranslationUnit(self, tu)
+
+    def visitProtocolInclude(self, pi):
+        pi.tu.protocol.accept(self)
+
+    def visitProtocol(self, p):
+        ptype = p.decl.type
+        # non-top-level protocols don't add any information
+        if not ptype.isToplevel() or ptype in ProcessGraph.visitedBridges:
+            return
+
+        ProcessGraph.visitedBridges.add(ptype)
+        self.visiting = ptype
+        return TcheckVisitor.visitProtocol(self, p)
+
+    def visitBridgesStmt(self, bridges):
+        bridgeProto = self.visiting
+        parentSideProto = bridges.parentSide.type
+        childSideProto = bridges.childSide.type
 
+        # the picture here is:
+        #                                                   (process 1|
+        #  [ parentSide(Parent|Child) | childSide(Parent|Child) | ... ]
+        #         |                                       |
+        #         |                        (process 2|    |
+        #  [ parentSide(Child|Parent) | bridgeParent ]    |
+        #                                   |             |
+        #                                   |             |       (process 3|
+        #                           [ bridgeChild | childSide(Child|Parent) ]
+        #
+        # First we have to figure out which parentSide/childSide
+        # actors live in the same process.  The possibilities are {
+        # parent, child } x { parent, child }.  (Multiple matches
+        # aren't allowed yet.)  Then we make ProcessGraph aware of the
+        # new bridge.
+        parentSideActor, childSideActor = None, None
+        pc = ( 'parent', 'child' )
+        for parentSide, childSide in cartesian_product(pc, pc):
+            pactor = Actor(parentSideProto, parentSide)
+            pproc = ProcessGraph.findProcess(pactor)
+            cactor = Actor(childSideProto, childSide)
+            cproc = ProcessGraph.findProcess(cactor)
+            assert pproc and cproc
+
+            if pproc == cproc:
+                if parentSideActor is not None:
+                    self.error(bridges.loc,
+                               "ambiguous bridge `%s' between `%s' and `%s'",
+                               bridgeProto.type.name(),
+                               parentSideProto.name(),
+                               childSideProto.name())
+                else:
+                    parentSideActor, childSideActor = pactor.other(), cactor.other()
+
+        if parentSideActor is None:
+            self.error(bridges.loc,
+                       "`%s' and `%s' cannot be bridged by `%s' ",
+                       parentSideProto.name(), childSideProto.name(),
+                       bridgeProto.name())
+
+        ProcessGraph.bridge(parentSideActor, childSideActor, bridgeProto)
+
+
+class CheckProcessGraph(TcheckVisitor):
+    def __init__(self, errors):
+        TcheckVisitor.__init__(self, None, errors)
+
+    # TODO: verify spawns-per-process assumption and check that graph
+    # is a dag
+    def visitTranslationUnit(self, tu):
+        if 0:
+            print 'Processes'
+            for process in ProcessGraph.processes:
+                print '  ', process
+                for edge in process.iteredges():
+                    print '    ', edge
+            print 'Bridges'
+            for bridge in ProcessGraph.bridges.itervalues():
+                print '  ', bridge
+
+##-----------------------------------------------------------------------------
 
 class CheckStateMachine(TcheckVisitor):
     def __init__(self, errors):
         # don't need the symbol table, we just want the error reporting
         TcheckVisitor.__init__(self, None, errors)
         self.p = None
 
     def visitProtocol(self, p):
new file mode 100644
--- /dev/null
+++ b/ipc/ipdl/test/ipdl/error/bridgesNonexistent.ipdl
@@ -0,0 +1,6 @@
+protocol bridgesNonexistent {
+    bridges Leftie, Rightie;
+
+child: __delete__();
+state DEAD: send __delete__;
+};
new file mode 100644
--- /dev/null
+++ b/ipc/ipdl/test/ipdl/error/bridgesSubprotocol.ipdl
@@ -0,0 +1,13 @@
+include protocol subprotocolBridges;
+
+protocol bridgesSubprotocol {
+    bridges subprotocolBridges, subprotocolBridges;
+
+    manages subprotocolBridges;
+
+child:
+    subprotocolBridges();
+    __delete__();
+
+state DEAD: send __delete__;
+};
new file mode 100644
--- /dev/null
+++ b/ipc/ipdl/test/ipdl/error/spawnsNonexistent.ipdl
@@ -0,0 +1,6 @@
+protocol spawnsNonexistent {
+    parent spawns Nonexistent;
+
+child: __delete__();
+state DEAD: send __delete__;
+};
new file mode 100644
--- /dev/null
+++ b/ipc/ipdl/test/ipdl/error/spawnsSubprotocol.ipdl
@@ -0,0 +1,13 @@
+include protocol subprotocolSpawns;
+
+protocol spawnsSubprotocol {
+    parent spawns subprotocolSpawns;
+
+    manages subprotocolSpawns;
+
+child:
+    subprotocolSpawns();
+    __delete__();
+
+state DEAD: send __delete__;
+};
new file mode 100644
--- /dev/null
+++ b/ipc/ipdl/test/ipdl/error/subprotocolBridges.ipdl
@@ -0,0 +1,10 @@
+include protocol bridgesSubprotocol;
+
+protocol subprotocolBridges {
+    bridges bridgesSubprotocol, bridgesSubprotocol;
+
+    manager bridgesSubprotocol;
+
+child: __delete__();
+state DEAD: send __delete__;
+};
new file mode 100644
--- /dev/null
+++ b/ipc/ipdl/test/ipdl/error/subprotocolSpawns.ipdl
@@ -0,0 +1,10 @@
+include protocol spawnsSubprotocol;
+
+protocol subprotocolSpawns {
+    parent spawns spawnsSubprotocol;
+
+    manager spawnsSubprotocol;
+
+child: __delete__();
+state DEAD: send __delete__;
+};
new file mode 100644
--- /dev/null
+++ b/ipc/ipdl/test/ipdl/ok/compositor.ipdl
@@ -0,0 +1,11 @@
+include protocol content;
+
+sync protocol compositor {
+    bridges compositor, content;
+
+child:
+    __delete__();
+
+state DEAD:
+    send __delete__;
+};
new file mode 100644
--- /dev/null
+++ b/ipc/ipdl/test/ipdl/ok/content.ipdl
@@ -0,0 +1,15 @@
+include protocol compositor;
+include protocol jetpack;
+include protocol plugin;
+
+sync protocol content {
+    parent spawns compositor as parent;
+    parent spawns jetpack;
+    child spawns plugin;
+
+child:
+    __delete__();
+
+state DEAD:
+    send __delete__;
+};
new file mode 100644
--- /dev/null
+++ b/ipc/ipdl/test/ipdl/ok/jetpack.ipdl
@@ -0,0 +1,7 @@
+sync protocol jetpack {
+child:
+    __delete__();
+
+state DEAD:
+    send __delete__;
+};
new file mode 100644
--- /dev/null
+++ b/ipc/ipdl/test/ipdl/ok/jetpackContent.ipdl
@@ -0,0 +1,12 @@
+include protocol content;
+include protocol jetpack;
+
+rpc protocol jetpackContent {
+    bridges jetpack, content;
+
+child:
+    __delete__();
+
+state DEAD:
+    send __delete__;
+};
new file mode 100644
--- /dev/null
+++ b/ipc/ipdl/test/ipdl/ok/plugin.ipdl
@@ -0,0 +1,7 @@
+rpc protocol plugin {
+child:
+    __delete__();
+
+state DEAD:
+    send __delete__;
+};