1# vim: set ts=4 sw=4 tw=99 et: 2# This Source Code Form is subject to the terms of the Mozilla Public 3# License, v. 2.0. If a copy of the MPL was not distributed with this 4# file, You can obtain one at http://mozilla.org/MPL/2.0/. 5 6import os, sys 7 8from ipdl.ast import CxxInclude, Decl, Loc, QualifiedId, State, StructDecl, TransitionStmt 9from ipdl.ast import TypeSpec, UnionDecl, UsingStmt, Visitor 10from ipdl.ast import ASYNC, SYNC, INTR 11from ipdl.ast import IN, OUT, INOUT, ANSWER, CALL, RECV, SEND 12from ipdl.ast import NOT_NESTED, INSIDE_SYNC_NESTED, INSIDE_CPOW_NESTED 13import ipdl.builtin as builtin 14 15_DELETE_MSG = '__delete__' 16 17 18def _otherside(side): 19 if side == 'parent': return 'child' 20 elif side == 'child': return 'parent' 21 else: assert 0 and 'unknown side "%s"'% (side) 22 23def unique_pairs(s): 24 n = len(s) 25 for i, e1 in enumerate(s): 26 for j in xrange(i+1, n): 27 yield (e1, s[j]) 28 29def cartesian_product(s1, s2): 30 for e1 in s1: 31 for e2 in s2: 32 yield (e1, e2) 33 34 35class TypeVisitor: 36 def __init__(self): 37 self.visited = set() 38 39 def defaultVisit(self, node, *args): 40 raise Exception, "INTERNAL ERROR: no visitor for node type `%s'"% ( 41 node.__class__.__name__) 42 43 def visitVoidType(self, v, *args): 44 pass 45 46 def visitBuiltinCxxType(self, t, *args): 47 pass 48 49 def visitImportedCxxType(self, t, *args): 50 pass 51 52 def visitStateType(self, s, *args): 53 pass 54 55 def visitMessageType(self, m, *args): 56 for param in m.params: 57 param.accept(self, *args) 58 for ret in m.returns: 59 ret.accept(self, *args) 60 if m.cdtype is not None: 61 m.cdtype.accept(self, *args) 62 63 def visitProtocolType(self, p, *args): 64 # NB: don't visit manager and manages. a naive default impl 65 # could result in an infinite loop 66 pass 67 68 def visitActorType(self, a, *args): 69 a.protocol.accept(self, *args) 70 a.state.accept(self, *args) 71 72 def visitStructType(self, s, *args): 73 if s in self.visited: 74 return 75 76 self.visited.add(s) 77 for field in s.fields: 78 field.accept(self, *args) 79 80 def visitUnionType(self, u, *args): 81 if u in self.visited: 82 return 83 84 self.visited.add(u) 85 for component in u.components: 86 component.accept(self, *args) 87 88 def visitArrayType(self, a, *args): 89 a.basetype.accept(self, *args) 90 91 def visitShmemType(self, s, *args): 92 pass 93 94 def visitShmemChmodType(self, c, *args): 95 c.shmem.accept(self) 96 97 def visitFDType(self, s, *args): 98 pass 99 100 def visitEndpointType(self, s, *args): 101 pass 102 103class Type: 104 def __cmp__(self, o): 105 return cmp(self.fullname(), o.fullname()) 106 def __eq__(self, o): 107 return (self.__class__ == o.__class__ 108 and self.fullname() == o.fullname()) 109 def __hash__(self): 110 return hash(self.fullname()) 111 112 # Is this a C++ type? 113 def isCxx(self): 114 return False 115 # Is this an IPDL type? 116 def isIPDL(self): 117 return False 118 # Is this type neither compound nor an array? 119 def isAtom(self): 120 return False 121 # Can this type appear in IPDL programs? 122 def isVisible(self): 123 return False 124 def isVoid(self): 125 return False 126 def typename(self): 127 return self.__class__.__name__ 128 129 def name(self): raise Exception, 'NYI' 130 def fullname(self): raise Exception, 'NYI' 131 132 def accept(self, visitor, *args): 133 visit = getattr(visitor, 'visit'+ self.__class__.__name__, None) 134 if visit is None: 135 return getattr(visitor, 'defaultVisit')(self, *args) 136 return visit(self, *args) 137 138class VoidType(Type): 139 def isCxx(self): 140 return True 141 def isIPDL(self): 142 return False 143 def isAtom(self): 144 return True 145 def isVisible(self): 146 return False 147 def isVoid(self): 148 return True 149 150 def name(self): return 'void' 151 def fullname(self): return 'void' 152 153VOID = VoidType() 154 155##-------------------- 156class CxxType(Type): 157 def isCxx(self): 158 return True 159 def isAtom(self): 160 return True 161 def isBuiltin(self): 162 return False 163 def isImported(self): 164 return False 165 def isGenerated(self): 166 return False 167 def isVisible(self): 168 return True 169 170class BuiltinCxxType(CxxType): 171 def __init__(self, qname): 172 assert isinstance(qname, QualifiedId) 173 self.loc = qname.loc 174 self.qname = qname 175 def isBuiltin(self): return True 176 177 def name(self): 178 return self.qname.baseid 179 def fullname(self): 180 return str(self.qname) 181 182class ImportedCxxType(CxxType): 183 def __init__(self, qname): 184 assert isinstance(qname, QualifiedId) 185 self.loc = qname.loc 186 self.qname = qname 187 def isImported(self): return True 188 189 def name(self): 190 return self.qname.baseid 191 def fullname(self): 192 return str(self.qname) 193 194##-------------------- 195class IPDLType(Type): 196 def isIPDL(self): return True 197 def isVisible(self): return True 198 def isState(self): return False 199 def isMessage(self): return False 200 def isProtocol(self): return False 201 def isActor(self): return False 202 def isStruct(self): return False 203 def isUnion(self): return False 204 def isArray(self): return False 205 def isAtom(self): return True 206 def isCompound(self): return False 207 def isShmem(self): return False 208 def isChmod(self): return False 209 def isFD(self): return False 210 def isEndpoint(self): return False 211 212 def isAsync(self): return self.sendSemantics == ASYNC 213 def isSync(self): return self.sendSemantics == SYNC 214 def isInterrupt(self): return self.sendSemantics is INTR 215 216 def hasReply(self): return (self.isSync() or self.isInterrupt()) 217 218 @classmethod 219 def convertsTo(cls, lesser, greater): 220 if (lesser.nestedRange[0] < greater.nestedRange[0] or 221 lesser.nestedRange[1] > greater.nestedRange[1]): 222 return False 223 224 # Protocols that use intr semantics are not allowed to use 225 # message nesting. 226 if (greater.isInterrupt() and 227 lesser.nestedRange != (NOT_NESTED, NOT_NESTED)): 228 return False 229 230 if lesser.isAsync(): 231 return True 232 elif lesser.isSync() and not greater.isAsync(): 233 return True 234 elif greater.isInterrupt(): 235 return True 236 237 return False 238 239 def needsMoreJuiceThan(self, o): 240 return not IPDLType.convertsTo(self, o) 241 242class StateType(IPDLType): 243 def __init__(self, protocol, name, start=False): 244 self.protocol = protocol 245 self.name = name 246 self.start = start 247 def isState(self): return True 248 def name(self): 249 return self.name 250 def fullname(self): 251 return self.name() 252 253class MessageType(IPDLType): 254 def __init__(self, nested, prio, sendSemantics, direction, 255 ctor=False, dtor=False, cdtype=None, compress=False, 256 verify=False): 257 assert not (ctor and dtor) 258 assert not (ctor or dtor) or type is not None 259 260 self.nested = nested 261 self.prio = prio 262 self.nestedRange = (nested, nested) 263 self.sendSemantics = sendSemantics 264 self.direction = direction 265 self.params = [ ] 266 self.returns = [ ] 267 self.ctor = ctor 268 self.dtor = dtor 269 self.cdtype = cdtype 270 self.compress = compress 271 self.verify = verify 272 def isMessage(self): return True 273 274 def isCtor(self): return self.ctor 275 def isDtor(self): return self.dtor 276 def constructedType(self): return self.cdtype 277 278 def isIn(self): return self.direction is IN 279 def isOut(self): return self.direction is OUT 280 def isInout(self): return self.direction is INOUT 281 282 def hasImplicitActorParam(self): 283 return self.isCtor() or self.isDtor() 284 285class Bridge: 286 def __init__(self, parentPtype, childPtype): 287 assert parentPtype.isToplevel() and childPtype.isToplevel() 288 self.parent = parentPtype 289 self.child = childPtype 290 291 def __cmp__(self, o): 292 return cmp(self.parent, o.parent) or cmp(self.child, o.child) 293 def __eq__(self, o): 294 return self.parent == o.parent and self.child == o.child 295 def __hash__(self): 296 return hash(self.parent) + hash(self.child) 297 298class ProtocolType(IPDLType): 299 def __init__(self, qname, nestedRange, sendSemantics, stateless=False): 300 self.qname = qname 301 self.nestedRange = nestedRange 302 self.sendSemantics = sendSemantics 303 self.spawns = set() # ProtocolType 304 self.opens = set() # ProtocolType 305 self.managers = [] # ProtocolType 306 self.manages = [ ] 307 self.stateless = stateless 308 self.hasDelete = False 309 self.hasReentrantDelete = False 310 def isProtocol(self): return True 311 312 def name(self): 313 return self.qname.baseid 314 def fullname(self): 315 return str(self.qname) 316 317 def addManager(self, mgrtype): 318 assert mgrtype.isIPDL() and mgrtype.isProtocol() 319 self.managers.append(mgrtype) 320 321 def addSpawn(self, ptype): 322 assert self.isToplevel() and ptype.isToplevel() 323 self.spawns.add(ptype) 324 325 def addOpen(self, ptype): 326 assert self.isToplevel() and ptype.isToplevel() 327 self.opens.add(ptype) 328 329 def managedBy(self, mgr): 330 self.managers = list(mgr) 331 332 def toplevel(self): 333 if self.isToplevel(): 334 return self 335 for mgr in self.managers: 336 if mgr is not self: 337 return mgr.toplevel() 338 339 def toplevels(self): 340 if self.isToplevel(): 341 return [self] 342 toplevels = list() 343 for mgr in self.managers: 344 if mgr is not self: 345 toplevels.extend(mgr.toplevels()) 346 return set(toplevels) 347 348 def isManagerOf(self, pt): 349 for managed in self.manages: 350 if pt is managed: 351 return True 352 return False 353 def isManagedBy(self, pt): 354 return pt in self.managers 355 356 def isManager(self): 357 return len(self.manages) > 0 358 def isManaged(self): 359 return 0 < len(self.managers) 360 def isToplevel(self): 361 return not self.isManaged() 362 363 def manager(self): 364 assert 1 == len(self.managers) 365 for mgr in self.managers: return mgr 366 367class ActorType(IPDLType): 368 def __init__(self, protocol, state=None, nullable=0): 369 self.protocol = protocol 370 self.state = state 371 self.nullable = nullable 372 def isActor(self): return True 373 374 def name(self): 375 return self.protocol.name() 376 def fullname(self): 377 return self.protocol.fullname() 378 379class _CompoundType(IPDLType): 380 def __init__(self): 381 self.defined = False # bool 382 self.mutualRec = set() # set(_CompoundType | ArrayType) 383 def isAtom(self): 384 return False 385 def isCompound(self): 386 return True 387 def itercomponents(self): 388 raise Exception('"pure virtual" method') 389 390 def mutuallyRecursiveWith(self, t, exploring=None): 391 '''|self| is mutually recursive with |t| iff |self| and |t| 392are in a cycle in the type graph rooted at |self|. This function 393looks for such a cycle and returns True if found.''' 394 if exploring is None: 395 exploring = set() 396 397 if t.isAtom(): 398 return False 399 elif t is self or t in self.mutualRec: 400 return True 401 elif t.isArray(): 402 isrec = self.mutuallyRecursiveWith(t.basetype, exploring) 403 if isrec: self.mutualRec.add(t) 404 return isrec 405 elif t in exploring: 406 return False 407 408 exploring.add(t) 409 for c in t.itercomponents(): 410 if self.mutuallyRecursiveWith(c, exploring): 411 self.mutualRec.add(c) 412 return True 413 exploring.remove(t) 414 415 return False 416 417class StructType(_CompoundType): 418 def __init__(self, qname, fields): 419 _CompoundType.__init__(self) 420 self.qname = qname 421 self.fields = fields # [ Type ] 422 423 def isStruct(self): return True 424 def itercomponents(self): 425 for f in self.fields: 426 yield f 427 428 def name(self): return self.qname.baseid 429 def fullname(self): return str(self.qname) 430 431class UnionType(_CompoundType): 432 def __init__(self, qname, components): 433 _CompoundType.__init__(self) 434 self.qname = qname 435 self.components = components # [ Type ] 436 437 def isUnion(self): return True 438 def itercomponents(self): 439 for c in self.components: 440 yield c 441 442 def name(self): return self.qname.baseid 443 def fullname(self): return str(self.qname) 444 445class ArrayType(IPDLType): 446 def __init__(self, basetype): 447 self.basetype = basetype 448 def isAtom(self): return False 449 def isArray(self): return True 450 451 def name(self): return self.basetype.name() +'[]' 452 def fullname(self): return self.basetype.fullname() +'[]' 453 454class ShmemType(IPDLType): 455 def __init__(self, qname): 456 self.qname = qname 457 def isShmem(self): return True 458 459 def name(self): 460 return self.qname.baseid 461 def fullname(self): 462 return str(self.qname) 463 464class FDType(IPDLType): 465 def __init__(self, qname): 466 self.qname = qname 467 def isFD(self): return True 468 469 def name(self): 470 return self.qname.baseid 471 def fullname(self): 472 return str(self.qname) 473 474class EndpointType(IPDLType): 475 def __init__(self, qname): 476 self.qname = qname 477 def isEndpoint(self): return True 478 479 def name(self): 480 return self.qname.baseid 481 def fullname(self): 482 return str(self.qname) 483 484def iteractortypes(t, visited=None): 485 """Iterate over any actor(s) buried in |type|.""" 486 if visited is None: 487 visited = set() 488 489 # XXX |yield| semantics makes it hard to use TypeVisitor 490 if not t.isIPDL(): 491 return 492 elif t.isActor(): 493 yield t 494 elif t.isArray(): 495 for actor in iteractortypes(t.basetype, visited): 496 yield actor 497 elif t.isCompound() and t not in visited: 498 visited.add(t) 499 for c in t.itercomponents(): 500 for actor in iteractortypes(c, visited): 501 yield actor 502 503def hasactor(type): 504 """Return true iff |type| is an actor or has one buried within.""" 505 for _ in iteractortypes(type): return True 506 return False 507 508def hasshmem(type): 509 """Return true iff |type| is shmem or has it buried within.""" 510 class found: pass 511 class findShmem(TypeVisitor): 512 def visitShmemType(self, s): raise found() 513 try: 514 type.accept(findShmem()) 515 except found: 516 return True 517 return False 518 519def hasfd(type): 520 """Return true iff |type| is fd or has it buried within.""" 521 class found: pass 522 class findFD(TypeVisitor): 523 def visitFDType(self, s): raise found() 524 try: 525 type.accept(findFD()) 526 except found: 527 return True 528 return False 529 530##-------------------- 531_builtinloc = Loc('<builtin>', 0) 532def makeBuiltinUsing(tname): 533 quals = tname.split('::') 534 base = quals.pop() 535 quals = quals[0:] 536 return UsingStmt(_builtinloc, 537 TypeSpec(_builtinloc, 538 QualifiedId(_builtinloc, base, quals))) 539 540builtinUsing = [ makeBuiltinUsing(t) for t in builtin.Types ] 541builtinHeaderIncludes = [ CxxInclude(_builtinloc, f) for f in builtin.HeaderIncludes ] 542 543def errormsg(loc, fmt, *args): 544 while not isinstance(loc, Loc): 545 if loc is None: loc = Loc.NONE 546 else: loc = loc.loc 547 return '%s: error: %s'% (str(loc), fmt % args) 548 549##-------------------- 550class SymbolTable: 551 def __init__(self, errors): 552 self.errors = errors 553 self.scopes = [ { } ] # stack({}) 554 self.globalScope = self.scopes[0] 555 self.currentScope = self.globalScope 556 557 def enterScope(self, node): 558 assert (isinstance(self.scopes[0], dict) 559 and self.globalScope is self.scopes[0]) 560 assert (isinstance(self.currentScope, dict)) 561 562 if not hasattr(node, 'symtab'): 563 node.symtab = { } 564 565 self.scopes.append(node.symtab) 566 self.currentScope = self.scopes[-1] 567 568 def exitScope(self, node): 569 symtab = self.scopes.pop() 570 assert self.currentScope is symtab 571 572 self.currentScope = self.scopes[-1] 573 574 assert (isinstance(self.scopes[0], dict) 575 and self.globalScope is self.scopes[0]) 576 assert isinstance(self.currentScope, dict) 577 578 def lookup(self, sym): 579 # NB: since IPDL doesn't allow any aliased names of different types, 580 # it doesn't matter in which order we walk the scope chain to resolve 581 # |sym| 582 for scope in self.scopes: 583 decl = scope.get(sym, None) 584 if decl is not None: return decl 585 return None 586 587 def declare(self, decl): 588 assert decl.progname or decl.shortname or decl.fullname 589 assert decl.loc 590 assert decl.type 591 592 def tryadd(name): 593 olddecl = self.lookup(name) 594 if olddecl is not None: 595 self.errors.append(errormsg( 596 decl.loc, 597 "redeclaration of symbol `%s', first declared at %s", 598 name, olddecl.loc)) 599 return 600 self.currentScope[name] = decl 601 decl.scope = self.currentScope 602 603 if decl.progname: tryadd(decl.progname) 604 if decl.shortname: tryadd(decl.shortname) 605 if decl.fullname: tryadd(decl.fullname) 606 607 608class TypeCheck: 609 '''This pass sets the .type attribute of every AST node. For some 610nodes, the type is meaningless and it is set to "VOID." This pass 611also sets the .decl attribute of AST nodes for which that is relevant; 612a decl says where, with what type, and under what name(s) a node was 613declared. 614 615With this information, it finally type checks the AST.''' 616 617 def __init__(self): 618 # NB: no IPDL compile will EVER print a warning. A program has 619 # one of two attributes: it is either well typed, or not well typed. 620 self.errors = [ ] # [ string ] 621 622 def check(self, tu, errout=sys.stderr): 623 def runpass(tcheckpass): 624 tu.accept(tcheckpass) 625 if len(self.errors): 626 self.reportErrors(errout) 627 return False 628 return True 629 630 # tag each relevant node with "decl" information, giving type, name, 631 # and location of declaration 632 if not runpass(GatherDecls(builtinUsing, self.errors)): 633 return False 634 635 # now that the nodes have decls, type checking is much easier. 636 if not runpass(CheckTypes(self.errors)): 637 return False 638 639 if not (runpass(BuildProcessGraph(self.errors)) 640 and runpass(CheckProcessGraph(self.errors))): 641 return False 642 643 if (tu.protocol 644 and len(tu.protocol.startStates) 645 and not runpass(CheckStateMachine(self.errors))): 646 return False 647 return True 648 649 def reportErrors(self, errout): 650 for error in self.errors: 651 print >>errout, error 652 653 654class TcheckVisitor(Visitor): 655 def __init__(self, symtab, errors): 656 self.symtab = symtab 657 self.errors = errors 658 659 def error(self, loc, fmt, *args): 660 self.errors.append(errormsg(loc, fmt, *args)) 661 662 def declare(self, loc, type, shortname=None, fullname=None, progname=None): 663 d = Decl(loc) 664 d.type = type 665 d.progname = progname 666 d.shortname = shortname 667 d.fullname = fullname 668 self.symtab.declare(d) 669 return d 670 671class GatherDecls(TcheckVisitor): 672 def __init__(self, builtinUsing, errors): 673 # |self.symtab| is the symbol table for the translation unit 674 # currently being visited 675 TcheckVisitor.__init__(self, None, errors) 676 self.builtinUsing = builtinUsing 677 678 def visitTranslationUnit(self, tu): 679 # all TranslationUnits declare symbols in global scope 680 if hasattr(tu, 'symtab'): 681 return 682 tu.symtab = SymbolTable(self.errors) 683 savedSymtab = self.symtab 684 self.symtab = tu.symtab 685 686 # pretend like the translation unit "using"-ed these for the 687 # sake of type checking and C++ code generation 688 tu.builtinUsing = self.builtinUsing 689 690 # for everyone's sanity, enforce that the filename and tu name 691 # match 692 basefilename = os.path.basename(tu.filename) 693 expectedfilename = '%s.ipdl'% (tu.name) 694 if not tu.protocol: 695 # header 696 expectedfilename += 'h' 697 if basefilename != expectedfilename: 698 self.error(tu.loc, 699 "expected file for translation unit `%s' to be named `%s'; instead it's named `%s'", 700 tu.name, expectedfilename, basefilename) 701 702 if tu.protocol: 703 assert tu.name == tu.protocol.name 704 705 p = tu.protocol 706 707 # FIXME/cjones: it's a little weird and counterintuitive 708 # to put both the namespace and non-namespaced name in the 709 # global scope. try to figure out something better; maybe 710 # a type-neutral |using| that works for C++ and protocol 711 # types? 712 qname = p.qname() 713 if 0 == len(qname.quals): 714 fullname = None 715 else: 716 fullname = str(qname) 717 p.decl = self.declare( 718 loc=p.loc, 719 type=ProtocolType(qname, p.nestedRange, p.sendSemantics, 720 stateless=(0 == len(p.transitionStmts))), 721 shortname=p.name, 722 fullname=fullname) 723 724 p.parentEndpointDecl = self.declare( 725 loc=p.loc, 726 type=EndpointType(QualifiedId(p.loc, 'Endpoint<' + fullname + 'Parent>', ['mozilla', 'ipc'])), 727 shortname='Endpoint<' + p.name + 'Parent>') 728 p.childEndpointDecl = self.declare( 729 loc=p.loc, 730 type=EndpointType(QualifiedId(p.loc, 'Endpoint<' + fullname + 'Child>', ['mozilla', 'ipc'])), 731 shortname='Endpoint<' + p.name + 'Child>') 732 733 # XXX ugh, this sucks. but we need this information to compute 734 # what friend decls we need in generated C++ 735 p.decl.type._ast = p 736 737 # make sure we have decls for all dependent protocols 738 for pinc in tu.includes: 739 pinc.accept(self) 740 741 # declare imported (and builtin) C++ types 742 for using in tu.builtinUsing: 743 using.accept(self) 744 for using in tu.using: 745 using.accept(self) 746 747 # first pass to "forward-declare" all structs and unions in 748 # order to support recursive definitions 749 for su in tu.structsAndUnions: 750 self.declareStructOrUnion(su) 751 752 # second pass to check each definition 753 for su in tu.structsAndUnions: 754 su.accept(self) 755 for inc in tu.includes: 756 if inc.tu.filetype == 'header': 757 for su in inc.tu.structsAndUnions: 758 su.accept(self) 759 760 if tu.protocol: 761 # grab symbols in the protocol itself 762 p.accept(self) 763 764 765 tu.type = VOID 766 767 self.symtab = savedSymtab 768 769 def declareStructOrUnion(self, su): 770 if hasattr(su, 'decl'): 771 self.symtab.declare(su.decl) 772 return 773 774 qname = su.qname() 775 if 0 == len(qname.quals): 776 fullname = None 777 else: 778 fullname = str(qname) 779 780 if isinstance(su, StructDecl): 781 sutype = StructType(qname, [ ]) 782 elif isinstance(su, UnionDecl): 783 sutype = UnionType(qname, [ ]) 784 else: assert 0 and 'unknown type' 785 786 # XXX more suckage. this time for pickling structs/unions 787 # declared in headers. 788 sutype._ast = su 789 790 su.decl = self.declare( 791 loc=su.loc, 792 type=sutype, 793 shortname=su.name, 794 fullname=fullname) 795 796 797 def visitInclude(self, inc): 798 if inc.tu is None: 799 self.error( 800 inc.loc, 801 "(type checking here will be unreliable because of an earlier error)") 802 return 803 inc.tu.accept(self) 804 if inc.tu.protocol: 805 self.symtab.declare(inc.tu.protocol.decl) 806 self.symtab.declare(inc.tu.protocol.parentEndpointDecl) 807 self.symtab.declare(inc.tu.protocol.childEndpointDecl) 808 else: 809 # This is a header. Import its "exported" globals into 810 # our scope. 811 for using in inc.tu.using: 812 using.accept(self) 813 for su in inc.tu.structsAndUnions: 814 self.declareStructOrUnion(su) 815 816 def visitStructDecl(self, sd): 817 # If we've already processed this struct, don't do it again. 818 if hasattr(sd, 'symtab'): 819 return 820 821 stype = sd.decl.type 822 823 self.symtab.enterScope(sd) 824 825 for f in sd.fields: 826 ftypedecl = self.symtab.lookup(str(f.typespec)) 827 if ftypedecl is None: 828 self.error(f.loc, "field `%s' of struct `%s' has unknown type `%s'", 829 f.name, sd.name, str(f.typespec)) 830 continue 831 832 f.decl = self.declare( 833 loc=f.loc, 834 type=self._canonicalType(ftypedecl.type, f.typespec), 835 shortname=f.name, 836 fullname=None) 837 stype.fields.append(f.decl.type) 838 839 self.symtab.exitScope(sd) 840 841 def visitUnionDecl(self, ud): 842 utype = ud.decl.type 843 844 # If we've already processed this union, don't do it again. 845 if len(utype.components): 846 return 847 848 for c in ud.components: 849 cdecl = self.symtab.lookup(str(c)) 850 if cdecl is None: 851 self.error(c.loc, "unknown component type `%s' of union `%s'", 852 str(c), ud.name) 853 continue 854 utype.components.append(self._canonicalType(cdecl.type, c)) 855 856 def visitUsingStmt(self, using): 857 fullname = str(using.type) 858 if using.type.basename() == fullname: 859 fullname = None 860 if fullname == 'mozilla::ipc::Shmem': 861 ipdltype = ShmemType(using.type.spec) 862 elif fullname == 'mozilla::ipc::FileDescriptor': 863 ipdltype = FDType(using.type.spec) 864 else: 865 ipdltype = ImportedCxxType(using.type.spec) 866 existingType = self.symtab.lookup(ipdltype.fullname()) 867 if existingType and existingType.fullname == ipdltype.fullname(): 868 using.decl = existingType 869 return 870 using.decl = self.declare( 871 loc=using.loc, 872 type=ipdltype, 873 shortname=using.type.basename(), 874 fullname=fullname) 875 876 def visitProtocol(self, p): 877 # protocol scope 878 self.symtab.enterScope(p) 879 880 for spawns in p.spawnsStmts: 881 spawns.accept(self) 882 883 for bridges in p.bridgesStmts: 884 bridges.accept(self) 885 886 for opens in p.opensStmts: 887 opens.accept(self) 888 889 seenmgrs = set() 890 for mgr in p.managers: 891 if mgr.name in seenmgrs: 892 self.error(mgr.loc, "manager `%s' appears multiple times", 893 mgr.name) 894 continue 895 896 seenmgrs.add(mgr.name) 897 mgr.of = p 898 mgr.accept(self) 899 900 for managed in p.managesStmts: 901 managed.manager = p 902 managed.accept(self) 903 904 if 0 == len(p.managers) and 0 == len(p.messageDecls): 905 self.error(p.loc, 906 "top-level protocol `%s' cannot be empty", 907 p.name) 908 909 setattr(self, 'currentProtocolDecl', p.decl) 910 for msg in p.messageDecls: 911 msg.accept(self) 912 del self.currentProtocolDecl 913 914 p.decl.type.hasDelete = (not not self.symtab.lookup(_DELETE_MSG)) 915 if not (p.decl.type.hasDelete or p.decl.type.isToplevel()): 916 self.error( 917 p.loc, 918 "destructor declaration `%s(...)' required for managed protocol `%s'", 919 _DELETE_MSG, p.name) 920 921 p.decl.type.hasReentrantDelete = p.decl.type.hasDelete and self.symtab.lookup(_DELETE_MSG).type.isInterrupt() 922 923 for managed in p.managesStmts: 924 mgdname = managed.name 925 ctordecl = self.symtab.lookup(mgdname +'Constructor') 926 927 if not (ctordecl and ctordecl.type.isCtor()): 928 self.error( 929 managed.loc, 930 "constructor declaration required for managed protocol `%s' (managed by protocol `%s')", 931 mgdname, p.name) 932 933 p.states = { } 934 935 if len(p.transitionStmts): 936 p.startStates = [ ts for ts in p.transitionStmts 937 if ts.state.start ] 938 if 0 == len(p.startStates): 939 p.startStates = [ p.transitionStmts[0] ] 940 941 # declare implicit "any", "dead", and "dying" states 942 self.declare(loc=State.ANY.loc, 943 type=StateType(p.decl.type, State.ANY.name, start=False), 944 progname=State.ANY.name) 945 self.declare(loc=State.DEAD.loc, 946 type=StateType(p.decl.type, State.DEAD.name, start=False), 947 progname=State.DEAD.name) 948 if p.decl.type.hasReentrantDelete: 949 self.declare(loc=State.DYING.loc, 950 type=StateType(p.decl.type, State.DYING.name, start=False), 951 progname=State.DYING.name) 952 953 # declare each state before decorating their mention 954 for trans in p.transitionStmts: 955 p.states[trans.state] = trans 956 trans.state.decl = self.declare( 957 loc=trans.state.loc, 958 type=StateType(p.decl.type, trans.state, trans.state.start), 959 progname=trans.state.name) 960 961 for trans in p.transitionStmts: 962 self.seentriggers = set() 963 trans.accept(self) 964 965 if not (p.decl.type.stateless 966 or (p.decl.type.isToplevel() 967 and None is self.symtab.lookup(_DELETE_MSG))): 968 # add a special state |state DEAD: null goto DEAD;| 969 deadtrans = TransitionStmt.makeNullStmt(State.DEAD) 970 p.states[State.DEAD] = deadtrans 971 if p.decl.type.hasReentrantDelete: 972 dyingtrans = TransitionStmt.makeNullStmt(State.DYING) 973 p.states[State.DYING] = dyingtrans 974 975 # visit the message decls once more and resolve the state names 976 # attached to actor params and returns 977 def resolvestate(loc, actortype): 978 assert actortype.isIPDL() and actortype.isActor() 979 980 # already resolved this guy's state 981 if isinstance(actortype.state, Decl): 982 return 983 984 if actortype.state is None: 985 # we thought this was a C++ type until type checking, 986 # when we realized it was an IPDL actor type. But 987 # that means that the actor wasn't specified to be in 988 # any particular state 989 actortype.state = State.ANY 990 991 statename = actortype.state.name 992 # FIXME/cjones: this is just wrong. we need the symbol table 993 # of the protocol this actor refers to. low priority bug 994 # since nobody's using this feature yet 995 statedecl = self.symtab.lookup(statename) 996 if statedecl is None: 997 self.error( 998 loc, 999 "protocol `%s' does not have the state `%s'", 1000 actortype.protocol.name(), 1001 statename) 1002 elif not statedecl.type.isState(): 1003 self.error( 1004 loc, 1005 "tag `%s' is supposed to be of state type, but is instead of type `%s'", 1006 statename, 1007 statedecl.type.typename()) 1008 else: 1009 actortype.state = statedecl.type 1010 1011 for msg in p.messageDecls: 1012 for iparam in msg.inParams: 1013 loc = iparam.loc 1014 for actortype in iteractortypes(iparam.type): 1015 resolvestate(loc, actortype) 1016 for oparam in msg.outParams: 1017 loc = oparam.loc 1018 for actortype in iteractortypes(oparam.type): 1019 resolvestate(loc, actortype) 1020 1021 # FIXME/cjones declare all the little C++ thingies that will 1022 # be generated. they're not relevant to IPDL itself, but 1023 # those ("invisible") symbols can clash with others in the 1024 # IPDL spec, and we'd like to catch those before C++ compilers 1025 # are allowed to obfuscate the error 1026 1027 self.symtab.exitScope(p) 1028 1029 1030 def visitSpawnsStmt(self, spawns): 1031 pname = spawns.proto 1032 spawns.proto = self.symtab.lookup(pname) 1033 if spawns.proto is None: 1034 self.error(spawns.loc, 1035 "spawned protocol `%s' has not been declared", 1036 pname) 1037 1038 def visitBridgesStmt(self, bridges): 1039 def lookup(p): 1040 decl = self.symtab.lookup(p) 1041 if decl is None: 1042 self.error(bridges.loc, 1043 "bridged protocol `%s' has not been declared", p) 1044 return decl 1045 bridges.parentSide = lookup(bridges.parentSide) 1046 bridges.childSide = lookup(bridges.childSide) 1047 1048 def visitOpensStmt(self, opens): 1049 pname = opens.proto 1050 opens.proto = self.symtab.lookup(pname) 1051 if opens.proto is None: 1052 self.error(opens.loc, 1053 "opened protocol `%s' has not been declared", 1054 pname) 1055 1056 1057 def visitManager(self, mgr): 1058 mgrdecl = self.symtab.lookup(mgr.name) 1059 pdecl = mgr.of.decl 1060 assert pdecl 1061 1062 pname, mgrname = pdecl.shortname, mgr.name 1063 loc = mgr.loc 1064 1065 if mgrdecl is None: 1066 self.error( 1067 loc, 1068 "protocol `%s' referenced as |manager| of `%s' has not been declared", 1069 mgrname, pname) 1070 elif not isinstance(mgrdecl.type, ProtocolType): 1071 self.error( 1072 loc, 1073 "entity `%s' referenced as |manager| of `%s' is not of `protocol' type; instead it is of type `%s'", 1074 mgrname, pname, mgrdecl.type.typename()) 1075 else: 1076 mgr.decl = mgrdecl 1077 pdecl.type.addManager(mgrdecl.type) 1078 1079 1080 def visitManagesStmt(self, mgs): 1081 mgsdecl = self.symtab.lookup(mgs.name) 1082 pdecl = mgs.manager.decl 1083 assert pdecl 1084 1085 pname, mgsname = pdecl.shortname, mgs.name 1086 loc = mgs.loc 1087 1088 if mgsdecl is None: 1089 self.error(loc, 1090 "protocol `%s', managed by `%s', has not been declared", 1091 mgsname, pname) 1092 elif not isinstance(mgsdecl.type, ProtocolType): 1093 self.error( 1094 loc, 1095 "%s declares itself managing a non-`protocol' entity `%s' of type `%s'", 1096 pname, mgsname, mgsdecl.type.typename()) 1097 else: 1098 mgs.decl = mgsdecl 1099 pdecl.type.manages.append(mgsdecl.type) 1100 1101 1102 def visitMessageDecl(self, md): 1103 msgname = md.name 1104 loc = md.loc 1105 1106 isctor = False 1107 isdtor = False 1108 cdtype = None 1109 1110 decl = self.symtab.lookup(msgname) 1111 if decl is not None and decl.type.isProtocol(): 1112 # probably a ctor. we'll check validity later. 1113 msgname += 'Constructor' 1114 isctor = True 1115 cdtype = decl.type 1116 elif decl is not None: 1117 self.error(loc, "message name `%s' already declared as `%s'", 1118 msgname, decl.type.typename()) 1119 # if we error here, no big deal; move on to find more 1120 1121 if _DELETE_MSG == msgname: 1122 isdtor = True 1123 cdtype = self.currentProtocolDecl.type 1124 1125 1126 # enter message scope 1127 self.symtab.enterScope(md) 1128 1129 msgtype = MessageType(md.nested, md.prio, md.sendSemantics, md.direction, 1130 ctor=isctor, dtor=isdtor, cdtype=cdtype, 1131 compress=md.compress, verify=md.verify) 1132 1133 # replace inparam Param nodes with proper Decls 1134 def paramToDecl(param): 1135 ptname = param.typespec.basename() 1136 ploc = param.typespec.loc 1137 1138 ptdecl = self.symtab.lookup(ptname) 1139 if ptdecl is None: 1140 self.error( 1141 ploc, 1142 "argument typename `%s' of message `%s' has not been declared", 1143 ptname, msgname) 1144 ptype = VOID 1145 else: 1146 ptype = self._canonicalType(ptdecl.type, param.typespec, 1147 chmodallowed=1) 1148 return self.declare(loc=ploc, 1149 type=ptype, 1150 progname=param.name) 1151 1152 for i, inparam in enumerate(md.inParams): 1153 pdecl = paramToDecl(inparam) 1154 msgtype.params.append(pdecl.type) 1155 md.inParams[i] = pdecl 1156 for i, outparam in enumerate(md.outParams): 1157 pdecl = paramToDecl(outparam) 1158 msgtype.returns.append(pdecl.type) 1159 md.outParams[i] = pdecl 1160 1161 self.symtab.exitScope(md) 1162 1163 md.decl = self.declare( 1164 loc=loc, 1165 type=msgtype, 1166 progname=msgname) 1167 md.protocolDecl = self.currentProtocolDecl 1168 md.decl._md = md 1169 1170 1171 def visitTransitionStmt(self, ts): 1172 self.seentriggers = set() 1173 TcheckVisitor.visitTransitionStmt(self, ts) 1174 1175 def visitTransition(self, t): 1176 loc = t.loc 1177 1178 # check the trigger message 1179 mname = t.msg 1180 if t in self.seentriggers: 1181 self.error(loc, "trigger `%s' appears multiple times", t.msg) 1182 self.seentriggers.add(t) 1183 1184 mdecl = self.symtab.lookup(mname) 1185 if mdecl is not None and mdecl.type.isIPDL() and mdecl.type.isProtocol(): 1186 mdecl = self.symtab.lookup(mname +'Constructor') 1187 1188 if mdecl is None: 1189 self.error(loc, "message `%s' has not been declared", mname) 1190 elif not mdecl.type.isMessage(): 1191 self.error( 1192 loc, 1193 "`%s' should have message type, but instead has type `%s'", 1194 mname, mdecl.type.typename()) 1195 else: 1196 t.msg = mdecl 1197 1198 # check the to-states 1199 seenstates = set() 1200 for toState in t.toStates: 1201 sname = toState.name 1202 sdecl = self.symtab.lookup(sname) 1203 1204 if sname in seenstates: 1205 self.error(loc, "to-state `%s' appears multiple times", sname) 1206 seenstates.add(sname) 1207 1208 if sdecl is None: 1209 self.error(loc, "state `%s' has not been declared", sname) 1210 elif not sdecl.type.isState(): 1211 self.error( 1212 loc, "`%s' should have state type, but instead has type `%s'", 1213 sname, sdecl.type.typename()) 1214 else: 1215 toState.decl = sdecl 1216 toState.start = sdecl.type.start 1217 1218 t.toStates = set(t.toStates) 1219 1220 1221 def _canonicalType(self, itype, typespec, chmodallowed=0): 1222 loc = typespec.loc 1223 1224 if itype.isIPDL(): 1225 if itype.isProtocol(): 1226 itype = ActorType(itype, 1227 state=typespec.state, 1228 nullable=typespec.nullable) 1229 # FIXME/cjones: ShmemChmod is disabled until bug 524193 1230 if 0 and chmodallowed and itype.isShmem(): 1231 itype = ShmemChmodType( 1232 itype, 1233 myChmod=typespec.myChmod, 1234 otherChmod=typespec.otherChmod) 1235 1236 if ((typespec.myChmod or typespec.otherChmod) 1237 and not (itype.isIPDL() and (itype.isShmem() or itype.isChmod()))): 1238 self.error( 1239 loc, 1240 "fine-grained access controls make no sense for type `%s'", 1241 itype.name()) 1242 1243 if not chmodallowed and (typespec.myChmod or typespec.otherChmod): 1244 self.error(loc, "fine-grained access controls not allowed here") 1245 1246 if typespec.nullable and not (itype.isIPDL() and itype.isActor()): 1247 self.error( 1248 loc, 1249 "`nullable' qualifier for type `%s' makes no sense", 1250 itype.name()) 1251 1252 if typespec.array: 1253 itype = ArrayType(itype) 1254 1255 return itype 1256 1257 1258##----------------------------------------------------------------------------- 1259 1260def checkcycles(p, stack=None): 1261 cycles = [] 1262 1263 if stack is None: 1264 stack = [] 1265 1266 for cp in p.manages: 1267 # special case for self-managed protocols 1268 if cp is p: 1269 continue 1270 1271 if cp in stack: 1272 return [stack + [p, cp]] 1273 cycles += checkcycles(cp, stack + [p]) 1274 1275 return cycles 1276 1277def formatcycles(cycles): 1278 r = [] 1279 for cycle in cycles: 1280 s = " -> ".join([ptype.name() for ptype in cycle]) 1281 r.append("`%s'" % s) 1282 return ", ".join(r) 1283 1284 1285def fullyDefined(t, exploring=None): 1286 '''The rules for "full definition" of a type are 1287 defined(atom) := true 1288 defined(array basetype) := defined(basetype) 1289 defined(struct f1 f2...) := defined(f1) and defined(f2) and ... 1290 defined(union c1 c2 ...) := defined(c1) or defined(c2) or ... 1291''' 1292 if exploring is None: 1293 exploring = set() 1294 1295 if t.isAtom(): 1296 return True 1297 elif t.isArray(): 1298 return fullyDefined(t.basetype, exploring) 1299 elif t.defined: 1300 return True 1301 assert t.isCompound() 1302 1303 if t in exploring: 1304 return False 1305 1306 exploring.add(t) 1307 for c in t.itercomponents(): 1308 cdefined = fullyDefined(c, exploring) 1309 if t.isStruct() and not cdefined: 1310 t.defined = False 1311 break 1312 elif t.isUnion() and cdefined: 1313 t.defined = True 1314 break 1315 else: 1316 if t.isStruct(): t.defined = True 1317 elif t.isUnion(): t.defined = False 1318 exploring.remove(t) 1319 1320 return t.defined 1321 1322 1323class CheckTypes(TcheckVisitor): 1324 def __init__(self, errors): 1325 # don't need the symbol table, we just want the error reporting 1326 TcheckVisitor.__init__(self, None, errors) 1327 self.visited = set() 1328 self.ptype = None 1329 1330 def visitInclude(self, inc): 1331 if inc.tu.filename in self.visited: 1332 return 1333 self.visited.add(inc.tu.filename) 1334 if inc.tu.protocol: 1335 inc.tu.protocol.accept(self) 1336 1337 1338 def visitStructDecl(self, sd): 1339 if not fullyDefined(sd.decl.type): 1340 self.error(sd.decl.loc, 1341 "struct `%s' is only partially defined", sd.name) 1342 1343 def visitUnionDecl(self, ud): 1344 if not fullyDefined(ud.decl.type): 1345 self.error(ud.decl.loc, 1346 "union `%s' is only partially defined", ud.name) 1347 1348 1349 def visitProtocol(self, p): 1350 self.ptype = p.decl.type 1351 1352 # check that we require no more "power" than our manager protocols 1353 ptype, pname = p.decl.type, p.decl.shortname 1354 1355 if len(p.spawnsStmts) and not ptype.isToplevel(): 1356 self.error(p.decl.loc, 1357 "protocol `%s' is not top-level and so cannot declare |spawns|", 1358 pname) 1359 1360 if len(p.bridgesStmts) and not ptype.isToplevel(): 1361 self.error(p.decl.loc, 1362 "protocol `%s' is not top-level and so cannot declare |bridges|", 1363 pname) 1364 1365 if len(p.opensStmts) and not ptype.isToplevel(): 1366 self.error(p.decl.loc, 1367 "protocol `%s' is not top-level and so cannot declare |opens|", 1368 pname) 1369 1370 for mgrtype in ptype.managers: 1371 if mgrtype is not None and ptype.needsMoreJuiceThan(mgrtype): 1372 self.error( 1373 p.decl.loc, 1374 "protocol `%s' requires more powerful send semantics than its manager `%s' provides", 1375 pname, mgrtype.name()) 1376 1377 # XXX currently we don't require a delete() message of top-level 1378 # actors. need to let experience guide this decision 1379 if not ptype.isToplevel(): 1380 for md in p.messageDecls: 1381 if _DELETE_MSG == md.name: break 1382 else: 1383 self.error( 1384 p.decl.loc, 1385 "managed protocol `%s' requires a `delete()' message to be declared", 1386 p.name) 1387 else: 1388 cycles = checkcycles(p.decl.type) 1389 if cycles: 1390 self.error( 1391 p.decl.loc, 1392 "cycle(s) detected in manager/manages heirarchy: %s", 1393 formatcycles(cycles)) 1394 1395 if 1 == len(ptype.managers) and ptype is ptype.manager(): 1396 self.error( 1397 p.decl.loc, 1398 "top-level protocol `%s' cannot manage itself", 1399 p.name) 1400 1401 return Visitor.visitProtocol(self, p) 1402 1403 1404 def visitSpawnsStmt(self, spawns): 1405 if not self.ptype.isToplevel(): 1406 self.error(spawns.loc, 1407 "only top-level protocols can have |spawns| statements; `%s' cannot", 1408 self.ptype.name()) 1409 return 1410 1411 spawnedType = spawns.proto.type 1412 if not (spawnedType.isIPDL() and spawnedType.isProtocol() 1413 and spawnedType.isToplevel()): 1414 self.error(spawns.loc, 1415 "cannot spawn non-top-level-protocol `%s'", 1416 spawnedType.name()) 1417 else: 1418 self.ptype.addSpawn(spawnedType) 1419 1420 1421 def visitBridgesStmt(self, bridges): 1422 if not self.ptype.isToplevel(): 1423 self.error(bridges.loc, 1424 "only top-level protocols can have |bridges| statements; `%s' cannot", 1425 self.ptype.name()) 1426 return 1427 1428 parentType = bridges.parentSide.type 1429 childType = bridges.childSide.type 1430 if not (parentType.isIPDL() and parentType.isProtocol() 1431 and childType.isIPDL() and childType.isProtocol() 1432 and parentType.isToplevel() and childType.isToplevel()): 1433 self.error(bridges.loc, 1434 "cannot bridge non-top-level-protocol(s) `%s' and `%s'", 1435 parentType.name(), childType.name()) 1436 1437 1438 def visitOpensStmt(self, opens): 1439 if not self.ptype.isToplevel(): 1440 self.error(opens.loc, 1441 "only top-level protocols can have |opens| statements; `%s' cannot", 1442 self.ptype.name()) 1443 return 1444 1445 openedType = opens.proto.type 1446 if not (openedType.isIPDL() and openedType.isProtocol() 1447 and openedType.isToplevel()): 1448 self.error(opens.loc, 1449 "cannot open non-top-level-protocol `%s'", 1450 openedType.name()) 1451 else: 1452 self.ptype.addOpen(openedType) 1453 1454 1455 def visitManagesStmt(self, mgs): 1456 pdecl = mgs.manager.decl 1457 ptype, pname = pdecl.type, pdecl.shortname 1458 1459 mgsdecl = mgs.decl 1460 mgstype, mgsname = mgsdecl.type, mgsdecl.shortname 1461 1462 loc = mgs.loc 1463 1464 # we added this information; sanity check it 1465 assert ptype.isManagerOf(mgstype) 1466 1467 # check that the "managed" protocol agrees 1468 if not mgstype.isManagedBy(ptype): 1469 self.error( 1470 loc, 1471 "|manages| declaration in protocol `%s' does not match any |manager| declaration in protocol `%s'", 1472 pname, mgsname) 1473 1474 1475 def visitManager(self, mgr): 1476 # FIXME/bug 541126: check that the protocol graph is acyclic 1477 1478 pdecl = mgr.of.decl 1479 ptype, pname = pdecl.type, pdecl.shortname 1480 1481 mgrdecl = mgr.decl 1482 mgrtype, mgrname = mgrdecl.type, mgrdecl.shortname 1483 1484 # we added this information; sanity check it 1485 assert ptype.isManagedBy(mgrtype) 1486 1487 loc = mgr.loc 1488 1489 # check that the "manager" protocol agrees 1490 if not mgrtype.isManagerOf(ptype): 1491 self.error( 1492 loc, 1493 "|manager| declaration in protocol `%s' does not match any |manages| declaration in protocol `%s'", 1494 pname, mgrname) 1495 1496 1497 def visitMessageDecl(self, md): 1498 mtype, mname = md.decl.type, md.decl.progname 1499 ptype, pname = md.protocolDecl.type, md.protocolDecl.shortname 1500 1501 loc = md.decl.loc 1502 1503 if mtype.nested == INSIDE_SYNC_NESTED and not mtype.isSync(): 1504 self.error( 1505 loc, 1506 "inside_sync nested messages must be sync (here, message `%s' in protocol `%s')", 1507 mname, pname) 1508 1509 if mtype.nested == INSIDE_CPOW_NESTED and (mtype.isOut() or mtype.isInout()): 1510 self.error( 1511 loc, 1512 "inside_cpow nested parent-to-child messages are verboten (here, message `%s' in protocol `%s')", 1513 mname, pname) 1514 1515 # We allow inside_sync messages that are themselves sync to be sent from the 1516 # parent. Normal and inside_cpow nested messages that are sync can only come from 1517 # the child. 1518 if mtype.isSync() and mtype.nested == NOT_NESTED and (mtype.isOut() or mtype.isInout()): 1519 self.error( 1520 loc, 1521 "sync parent-to-child messages are verboten (here, message `%s' in protocol `%s')", 1522 mname, pname) 1523 1524 if mtype.needsMoreJuiceThan(ptype): 1525 self.error( 1526 loc, 1527 "message `%s' requires more powerful send semantics than its protocol `%s' provides", 1528 mname, pname) 1529 1530 if mtype.isAsync() and len(mtype.returns): 1531 # XXX/cjones could modify grammar to disallow this ... 1532 self.error(loc, 1533 "asynchronous message `%s' declares return values", 1534 mname) 1535 1536 if (mtype.compress and 1537 (not mtype.isAsync() or mtype.isCtor() or mtype.isDtor())): 1538 self.error( 1539 loc, 1540 "message `%s' in protocol `%s' requests compression but is not async or is special (ctor or dtor)", 1541 mname[:-len('constructor')], pname) 1542 1543 if mtype.isCtor() and not ptype.isManagerOf(mtype.constructedType()): 1544 self.error( 1545 loc, 1546 "ctor for protocol `%s', which is not managed by protocol `%s'", 1547 mname[:-len('constructor')], pname) 1548 1549 1550 def visitTransition(self, t): 1551 _YNC = [ ASYNC, SYNC ] 1552 1553 loc = t.loc 1554 impliedDirection, impliedSems = { 1555 SEND: [ OUT, _YNC ], RECV: [ IN, _YNC ], 1556 CALL: [ OUT, INTR ], ANSWER: [ IN, INTR ], 1557 } [t.trigger] 1558 1559 if (OUT is impliedDirection and t.msg.type.isIn() 1560 or IN is impliedDirection and t.msg.type.isOut() 1561 or _YNC is impliedSems and t.msg.type.isInterrupt() 1562 or INTR is impliedSems and (not t.msg.type.isInterrupt())): 1563 mtype = t.msg.type 1564 1565 self.error( 1566 loc, "%s %s message `%s' is not `%s'd", 1567 mtype.sendSemantics.pretty, mtype.direction.pretty, 1568 t.msg.progname, 1569 t.trigger.pretty) 1570 1571##----------------------------------------------------------------------------- 1572 1573class Process: 1574 def __init__(self): 1575 self.actors = set() # set(Actor) 1576 self.edges = { } # Actor -> [ SpawnsEdge ] 1577 self.spawn = set() # set(Actor) 1578 1579 def edge(self, spawner, spawn): 1580 if spawner not in self.edges: self.edges[spawner] = [ ] 1581 self.edges[spawner].append(SpawnsEdge(spawner, spawn)) 1582 self.spawn.add(spawn) 1583 1584 def iteredges(self): 1585 for edgelist in self.edges.itervalues(): 1586 for edge in edgelist: 1587 yield edge 1588 1589 def merge(self, o): 1590 'Merge the Process |o| into this Process' 1591 if self == o: 1592 return 1593 for actor in o.actors: 1594 ProcessGraph.actorToProcess[actor] = self 1595 self.actors.update(o.actors) 1596 self.edges.update(o.edges) 1597 self.spawn.update(o.spawn) 1598 ProcessGraph.processes.remove(o) 1599 1600 def spawns(self, actor): 1601 return actor in self.spawn 1602 1603 def __cmp__(self, o): return cmp(self.actors, o.actors) 1604 def __eq__(self, o): return self.actors == o.actors 1605 def __hash__(self): return hash(id(self)) 1606 def __repr__(self): 1607 return reduce(lambda a, x: str(a) + str(x) +'|', self.actors, '|') 1608 def __str__(self): return repr(self) 1609 1610class Actor: 1611 def __init__(self, ptype, side): 1612 self.ptype = ptype 1613 self.side = side 1614 1615 def asType(self): 1616 return ActorType(self.ptype) 1617 def other(self): 1618 return Actor(self.ptype, _otherside(self.side)) 1619 1620 def __cmp__(self, o): 1621 return cmp(self.ptype, o.ptype) or cmp(self.side, o.side) 1622 def __eq__(self, o): 1623 return self.ptype == o.ptype and self.side == o.side 1624 def __hash__(self): return hash(repr(self)) 1625 def __repr__(self): return '%s%s'% (self.ptype.name(), self.side.title()) 1626 def __str__(self): return repr(self) 1627 1628class SpawnsEdge: 1629 def __init__(self, spawner, spawn): 1630 self.spawner = spawner # Actor 1631 self.spawn = spawn # Actor 1632 def __repr__(self): 1633 return '(%r)--spawns-->(%r)'% (self.spawner, self.spawn) 1634 def __str__(self): return repr(self) 1635 1636class BridgeEdge: 1637 def __init__(self, bridgeProto, parent, child): 1638 self.bridgeProto = bridgeProto # ProtocolType 1639 self.parent = parent # Actor 1640 self.child = child # Actor 1641 def __repr__(self): 1642 return '(%r)--%s bridge-->(%r)'% ( 1643 self.parent, self.bridgeProto.name(), self.child) 1644 def __str__(self): return repr(self) 1645 1646class OpensEdge: 1647 def __init__(self, opener, openedProto): 1648 self.opener = opener # Actor 1649 self.openedProto = openedProto # ProtocolType 1650 def __repr__(self): 1651 return '(%r)--opens-->(%s)'% (self.opener, self.openedProto.name()) 1652 def __str__(self): return repr(self) 1653 1654# "singleton" class with state that persists across type checking of 1655# all protocols 1656class ProcessGraph: 1657 processes = set() # set(Process) 1658 bridges = { } # ProtocolType -> [ BridgeEdge ] 1659 opens = { } # ProtocolType -> [ OpensEdge ] 1660 actorToProcess = { } # Actor -> Process 1661 visitedSpawns = set() # set(ActorType) 1662 visitedBridges = set() # set(ActorType) 1663 1664 @classmethod 1665 def findProcess(cls, actor): 1666 return cls.actorToProcess.get(actor, None) 1667 1668 @classmethod 1669 def getProcess(cls, actor): 1670 if actor not in cls.actorToProcess: 1671 p = Process() 1672 p.actors.add(actor) 1673 cls.processes.add(p) 1674 cls.actorToProcess[actor] = p 1675 return cls.actorToProcess[actor] 1676 1677 @classmethod 1678 def bridgesOf(cls, bridgeP): 1679 return cls.bridges.get(bridgeP, []) 1680 1681 @classmethod 1682 def bridgeEndpointsOf(cls, ptype, side): 1683 actor = Actor(ptype, side) 1684 endpoints = [] 1685 for b in cls.iterbridges(): 1686 if b.parent == actor: 1687 endpoints.append(Actor(b.bridgeProto, 'parent')) 1688 if b.child == actor: 1689 endpoints.append(Actor(b.bridgeProto, 'child')) 1690 return endpoints 1691 1692 @classmethod 1693 def iterbridges(cls): 1694 for edges in cls.bridges.itervalues(): 1695 for bridge in edges: 1696 yield bridge 1697 1698 @classmethod 1699 def opensOf(cls, openedP): 1700 return cls.opens.get(openedP, []) 1701 1702 @classmethod 1703 def opensEndpointsOf(cls, ptype, side): 1704 actor = Actor(ptype, side) 1705 endpoints = [] 1706 for o in cls.iteropens(): 1707 if actor == o.opener: 1708 endpoints.append(Actor(o.openedProto, o.opener.side)) 1709 elif actor == o.opener.other(): 1710 endpoints.append(Actor(o.openedProto, o.opener.other().side)) 1711 return endpoints 1712 1713 @classmethod 1714 def iteropens(cls): 1715 for edges in cls.opens.itervalues(): 1716 for opens in edges: 1717 yield opens 1718 1719 @classmethod 1720 def spawn(cls, spawner, remoteSpawn): 1721 localSpawn = remoteSpawn.other() 1722 spawnerProcess = ProcessGraph.getProcess(spawner) 1723 spawnerProcess.merge(ProcessGraph.getProcess(localSpawn)) 1724 spawnerProcess.edge(spawner, remoteSpawn) 1725 1726 @classmethod 1727 def bridge(cls, parent, child, bridgeP): 1728 bridgeParent = Actor(bridgeP, 'parent') 1729 parentProcess = ProcessGraph.getProcess(parent) 1730 parentProcess.merge(ProcessGraph.getProcess(bridgeParent)) 1731 bridgeChild = Actor(bridgeP, 'child') 1732 childProcess = ProcessGraph.getProcess(child) 1733 childProcess.merge(ProcessGraph.getProcess(bridgeChild)) 1734 if bridgeP not in cls.bridges: 1735 cls.bridges[bridgeP] = [ ] 1736 cls.bridges[bridgeP].append(BridgeEdge(bridgeP, parent, child)) 1737 1738 @classmethod 1739 def open(cls, opener, opened, openedP): 1740 remoteOpener, remoteOpened, = opener.other(), opened.other() 1741 openerProcess = ProcessGraph.getProcess(opener) 1742 openerProcess.merge(ProcessGraph.getProcess(opened)) 1743 remoteOpenerProcess = ProcessGraph.getProcess(remoteOpener) 1744 remoteOpenerProcess.merge(ProcessGraph.getProcess(remoteOpened)) 1745 if openedP not in cls.opens: 1746 cls.opens[openedP] = [ ] 1747 cls.opens[openedP].append(OpensEdge(opener, openedP)) 1748 1749 1750class BuildProcessGraph(TcheckVisitor): 1751 class findSpawns(TcheckVisitor): 1752 def __init__(self, errors): 1753 TcheckVisitor.__init__(self, None, errors) 1754 1755 def visitTranslationUnit(self, tu): 1756 TcheckVisitor.visitTranslationUnit(self, tu) 1757 1758 def visitInclude(self, inc): 1759 if inc.tu.protocol: 1760 inc.tu.protocol.accept(self) 1761 1762 def visitProtocol(self, p): 1763 ptype = p.decl.type 1764 # non-top-level protocols don't add any information 1765 if not ptype.isToplevel() or ptype in ProcessGraph.visitedSpawns: 1766 return 1767 1768 ProcessGraph.visitedSpawns.add(ptype) 1769 self.visiting = ptype 1770 ProcessGraph.getProcess(Actor(ptype, 'parent')) 1771 ProcessGraph.getProcess(Actor(ptype, 'child')) 1772 return TcheckVisitor.visitProtocol(self, p) 1773 1774 def visitSpawnsStmt(self, spawns): 1775 # The picture here is: 1776 # [ spawner | localSpawn | ??? ] (process 1) 1777 # | 1778 # | 1779 # [ remoteSpawn | ???] (process 2) 1780 # 1781 # A spawns stmt tells us that |spawner| and |localSpawn| 1782 # are in the same process. 1783 spawner = Actor(self.visiting, spawns.side) 1784 remoteSpawn = Actor(spawns.proto.type, spawns.spawnedAs) 1785 ProcessGraph.spawn(spawner, remoteSpawn) 1786 1787 def __init__(self, errors): 1788 TcheckVisitor.__init__(self, None, errors) 1789 self.visiting = None # ActorType 1790 self.visited = set() # set(ActorType) 1791 1792 def visitTranslationUnit(self, tu): 1793 tu.accept(self.findSpawns(self.errors)) 1794 TcheckVisitor.visitTranslationUnit(self, tu) 1795 1796 def visitInclude(self, inc): 1797 if inc.tu.protocol: 1798 inc.tu.protocol.accept(self) 1799 1800 def visitProtocol(self, p): 1801 ptype = p.decl.type 1802 # non-top-level protocols don't add any information 1803 if not ptype.isToplevel() or ptype in ProcessGraph.visitedBridges: 1804 return 1805 1806 ProcessGraph.visitedBridges.add(ptype) 1807 self.visiting = ptype 1808 return TcheckVisitor.visitProtocol(self, p) 1809 1810 def visitBridgesStmt(self, bridges): 1811 bridgeProto = self.visiting 1812 parentSideProto = bridges.parentSide.type 1813 childSideProto = bridges.childSide.type 1814 1815 # the picture here is: 1816 # (process 1| 1817 # [ parentSide(Parent|Child) | childSide(Parent|Child) | ... ] 1818 # | | 1819 # | (process 2| | 1820 # [ parentSide(Child|Parent) | bridgeParent ] | 1821 # | | 1822 # | | (process 3| 1823 # [ bridgeChild | childSide(Child|Parent) ] 1824 # 1825 # First we have to figure out which parentSide/childSide 1826 # actors live in the same process. The possibilities are { 1827 # parent, child } x { parent, child }. (Multiple matches 1828 # aren't allowed yet.) Then we make ProcessGraph aware of the 1829 # new bridge. 1830 parentSideActor, childSideActor = None, None 1831 pc = ( 'parent', 'child' ) 1832 for parentSide, childSide in cartesian_product(pc, pc): 1833 pactor = Actor(parentSideProto, parentSide) 1834 pproc = ProcessGraph.findProcess(pactor) 1835 cactor = Actor(childSideProto, childSide) 1836 cproc = ProcessGraph.findProcess(cactor) 1837 assert pproc and cproc 1838 1839 if pproc == cproc: 1840 if parentSideActor is not None: 1841 if parentSideProto != childSideProto: 1842 self.error(bridges.loc, 1843 "ambiguous bridge `%s' between `%s' and `%s'", 1844 bridgeProto.name(), 1845 parentSideProto.name(), 1846 childSideProto.name()) 1847 else: 1848 parentSideActor, childSideActor = pactor.other(), cactor.other() 1849 1850 if parentSideActor is None: 1851 self.error(bridges.loc, 1852 "`%s' and `%s' cannot be bridged by `%s' ", 1853 parentSideProto.name(), childSideProto.name(), 1854 bridgeProto.name()) 1855 1856 ProcessGraph.bridge(parentSideActor, childSideActor, bridgeProto) 1857 1858 def visitOpensStmt(self, opens): 1859 openedP = opens.proto.type 1860 opener = Actor(self.visiting, opens.side) 1861 opened = Actor(openedP, opens.side) 1862 1863 # The picture here is: 1864 # [ opener | opened ] (process 1) 1865 # | | 1866 # | | 1867 # [ remoteOpener | remoteOpened ] (process 2) 1868 # 1869 # An opens stmt tells us that the pairs |opener|/|opened| 1870 # and |remoteOpener|/|remoteOpened| are each in the same 1871 # process. 1872 ProcessGraph.open(opener, opened, openedP) 1873 1874 1875class CheckProcessGraph(TcheckVisitor): 1876 def __init__(self, errors): 1877 TcheckVisitor.__init__(self, None, errors) 1878 1879 # TODO: verify spawns-per-process assumption and check that graph 1880 # is a dag 1881 def visitTranslationUnit(self, tu): 1882 if 0: 1883 print 'Processes' 1884 for process in ProcessGraph.processes: 1885 print ' ', process 1886 for edge in process.iteredges(): 1887 print ' ', edge 1888 print 'Bridges' 1889 for bridgeList in ProcessGraph.bridges.itervalues(): 1890 for bridge in bridgeList: 1891 print ' ', bridge 1892 print 'Opens' 1893 for opensList in ProcessGraph.opens.itervalues(): 1894 for opens in opensList: 1895 print ' ', opens 1896 1897##----------------------------------------------------------------------------- 1898 1899class CheckStateMachine(TcheckVisitor): 1900 def __init__(self, errors): 1901 # don't need the symbol table, we just want the error reporting 1902 TcheckVisitor.__init__(self, None, errors) 1903 self.p = None 1904 1905 def visitProtocol(self, p): 1906 self.p = p 1907 self.checkReachability(p) 1908 for ts in p.transitionStmts: 1909 ts.accept(self) 1910 1911 def visitTransitionStmt(self, ts): 1912 # We want to disallow "race conditions" in protocols. These 1913 # can occur when a protocol state machine has a state that 1914 # allows triggers of opposite direction. That declaration 1915 # allows the parent to send the child a message at the 1916 # exact instance the child sends the parent a message. One of 1917 # those messages would (probably) violate the state machine 1918 # and cause the child to be terminated. It's obviously very 1919 # nice if we can forbid this at the level of IPDL state 1920 # machines, rather than resorting to static or dynamic 1921 # checking of C++ implementation code. 1922 # 1923 # An easy way to avoid this problem in IPDL is to only allow 1924 # "unidirectional" protocol states; that is, from each state, 1925 # only send or only recv triggers are allowed. This approach 1926 # is taken by the Singularity project's "contract-based 1927 # message channels." However, this can be something of a 1928 # notational burden for stateful protocols. 1929 # 1930 # If two messages race, the effect is that the parent's and 1931 # child's states get temporarily out of sync. Informally, 1932 # IPDL allows this *only if* the state machines get out of 1933 # sync for only *one* step (state machine transition), then 1934 # sync back up. This is a design decision: the states could 1935 # be allowd to get out of sync for any constant k number of 1936 # steps. (If k is unbounded, there's no point in presenting 1937 # the abstraction of parent and child actor states being 1938 # "entangled".) The working hypothesis is that the more steps 1939 # the states are allowed to be out of sync, the harder it is 1940 # to reason about the protocol. 1941 # 1942 # Slightly less informally, two messages are allowed to race 1943 # only if processing them in either order leaves the protocol 1944 # in the same state. That is, messages A and B are allowed to 1945 # race only if processing A then B leaves the protocol in 1946 # state S, *and* processing B then A also leaves the protocol 1947 # in state S. Technically, if this holds, then messages A and 1948 # B could be called "commutative" wrt to actor state. 1949 # 1950 # "Formally", state machine definitions must adhere to two 1951 # rules. 1952 # 1953 # *Rule 1*: from a state S, all sync triggers must be of the same 1954 # "direction," i.e. only |send| or only |recv| 1955 # 1956 # (Pairs of sync messages can't commute, because otherwise 1957 # deadlock can occur from simultaneously in-flight sync 1958 # requests.) 1959 # 1960 # *Rule 2*: the "Diamond Rule". 1961 # from a state S, 1962 # for any pair of triggers t1 and t2, 1963 # where t1 and t2 have opposite direction, 1964 # and t1 transitions to state T1 and t2 to T2, 1965 # then the following must be true: 1966 # (T2 allows the trigger t1, transitioning to state U) 1967 # and 1968 # (T1 allows the trigger t2, transitioning to state U) 1969 # and 1970 # ( 1971 # ( 1972 # (all of T1's triggers have the same direction as t2) 1973 # and 1974 # (all of T2's triggers have the same direction as t1) 1975 # ) 1976 # or 1977 # (T1, T2, and U are the same "terminal state") 1978 # ) 1979 # 1980 # A "terminal state" S is one from which all triggers 1981 # transition back to S itself. 1982 # 1983 # The presence of triggers with multiple out states complicates 1984 # this check slightly, but doesn't fundamentally change it. 1985 # 1986 # from a state S, 1987 # for any pair of triggers t1 and t2, 1988 # where t1 and t2 have opposite direction, 1989 # for each pair of states (T1, T2) \in t1_out x t2_out, 1990 # where t1_out is the set of outstates from t1 1991 # t2_out is the set of outstates from t2 1992 # t1_out x t2_out is their Cartesian product 1993 # and t1 transitions to state T1 and t2 to T2, 1994 # then the following must be true: 1995 # (T2 allows the trigger t1, with out-state set { U }) 1996 # and 1997 # (T1 allows the trigger t2, with out-state set { U }) 1998 # and 1999 # ( 2000 # ( 2001 # (all of T1's triggers have the same direction as t2) 2002 # and 2003 # (all of T2's triggers have the same direction as t1) 2004 # ) 2005 # or 2006 # (T1, T2, and U are the same "terminal state") 2007 # ) 2008 2009 # check Rule 1 2010 syncdirection = None 2011 syncok = True 2012 for trans in ts.transitions: 2013 if not trans.msg.type.isSync(): continue 2014 if syncdirection is None: 2015 syncdirection = trans.trigger.direction() 2016 elif syncdirection is not trans.trigger.direction(): 2017 self.error( 2018 trans.loc, 2019 "sync trigger at state `%s' in protocol `%s' has different direction from earlier sync trigger at same state", 2020 ts.state.name, self.p.name) 2021 syncok = False 2022 # don't check the Diamond Rule if Rule 1 doesn't hold 2023 if not syncok: 2024 return 2025 2026 # helper functions 2027 def triggerTargets(S, t): 2028 '''Return the set of states transitioned to from state |S| 2029upon trigger |t|, or { } if |t| is not a trigger in |S|.''' 2030 for trans in self.p.states[S].transitions: 2031 if t.trigger is trans.trigger and t.msg is trans.msg: 2032 return trans.toStates 2033 return set() 2034 2035 def allTriggersSameDirectionAs(S, t): 2036 '''Return true iff all the triggers from state |S| have the same 2037direction as trigger |t|''' 2038 direction = t.direction() 2039 for trans in self.p.states[S].transitions: 2040 if direction != trans.trigger.direction(): 2041 return False 2042 return True 2043 2044 def terminalState(S): 2045 '''Return true iff |S| is a "terminal state".''' 2046 for trans in self.p.states[S].transitions: 2047 for S_ in trans.toStates: 2048 if S_ != S: return False 2049 return True 2050 2051 def sameTerminalState(S1, S2, S3): 2052 '''Return true iff states |S1|, |S2|, and |S3| are all the same 2053"terminal state".''' 2054 if isinstance(S3, set): 2055 assert len(S3) == 1 2056 for S3_ in S3: pass 2057 S3 = S3_ 2058 2059 return (S1 == S2 == S3) and terminalState(S1) 2060 2061 S = ts.state.name 2062 2063 # check the Diamond Rule 2064 for (t1, t2) in unique_pairs(ts.transitions): 2065 # if the triggers have the same direction, they can't race, 2066 # since only one endpoint can initiate either (and delivery 2067 # is in-order) 2068 if t1.trigger.direction() == t2.trigger.direction(): 2069 continue 2070 2071 loc = t1.loc 2072 t1_out = t1.toStates 2073 t2_out = t2.toStates 2074 2075 for (T1, T2) in cartesian_product(t1_out, t2_out): 2076 # U1 <- { u | T1 --t2--> u } 2077 U1 = triggerTargets(T1, t2) 2078 # U2 <- { u | T2 --t1--> u } 2079 U2 = triggerTargets(T2, t1) 2080 2081 # don't report more than one Diamond Rule violation 2082 # per state. there may be O(n^4) total, way too many 2083 # for a human to parse 2084 # 2085 # XXX/cjones: could set a limit on #printed and stop 2086 # after that limit ... 2087 raceError = False 2088 errT1 = None 2089 errT2 = None 2090 2091 if 0 == len(U1) or 0 == len(U2): 2092 print "******* case 1" 2093 raceError = True 2094 elif 1 < len(U1) or 1 < len(U2): 2095 raceError = True 2096 # there are potentially many unpaired states; just 2097 # pick two 2098 print "******* case 2" 2099 for u1, u2 in cartesian_product(U1, U2): 2100 if u1 != u2: 2101 errT1, errT2 = u1, u2 2102 break 2103 elif U1 != U2: 2104 print "******* case 3" 2105 raceError = True 2106 for errT1 in U1: pass 2107 for errT2 in U2: pass 2108 2109 if raceError: 2110 self.reportRaceError(loc, S, 2111 [ T1, t1, errT1 ], 2112 [ T2, t2, errT2 ]) 2113 return 2114 2115 if not ((allTriggersSameDirectionAs(T1, t2.trigger) 2116 and allTriggersSameDirectionAs(T2, t1.trigger)) 2117 or sameTerminalState(T1, T2, U1)): 2118 self.reportRunawayError(loc, S, [ T1, t1, None ], [ T2, t2, None ]) 2119 return 2120 2121 def checkReachability(self, p): 2122 def explore(ts, visited): 2123 if ts.state in visited: 2124 return 2125 visited.add(ts.state) 2126 for outedge in ts.transitions: 2127 for toState in outedge.toStates: 2128 explore(p.states[toState], visited) 2129 2130 checkfordelete = (State.DEAD in p.states) 2131 2132 allvisited = set() # set(State) 2133 for root in p.startStates: 2134 visited = set() 2135 2136 explore(root, visited) 2137 allvisited.update(visited) 2138 2139 if checkfordelete and State.DEAD not in visited: 2140 self.error( 2141 root.loc, 2142 "when starting from state `%s', actors of protocol `%s' cannot be deleted", root.state.name, p.name) 2143 2144 for ts in p.states.itervalues(): 2145 if ts.state is not State.DEAD and ts.state not in allvisited: 2146 self.error(ts.loc, 2147 "unreachable state `%s' in protocol `%s'", 2148 ts.state.name, p.name) 2149 2150 2151 def _normalizeTransitionSequences(self, t1Seq, t2Seq): 2152 T1, M1, U1 = t1Seq 2153 T2, M2, U2 = t2Seq 2154 assert M1 is not None and M2 is not None 2155 2156 # make sure that T1/M1/U1 is the parent side of the race 2157 if M1.trigger is RECV or M1.trigger is ANSWER: 2158 T1, M1, U1, T2, M2, U2 = T2, M2, U2, T1, M1, U1 2159 2160 def stateName(S): 2161 if S: return S.name 2162 return '[error]' 2163 2164 T1 = stateName(T1) 2165 T2 = stateName(T2) 2166 U1 = stateName(U1) 2167 U2 = stateName(U2) 2168 2169 return T1, M1.msg.progname, U1, T2, M2.msg.progname, U2 2170 2171 2172 def reportRaceError(self, loc, S, t1Seq, t2Seq): 2173 T1, M1, U1, T2, M2, U2 = self._normalizeTransitionSequences(t1Seq, t2Seq) 2174 self.error( 2175 loc, 2176"""in protocol `%(P)s', the sequence of events 2177 parent: +--`send %(M1)s'-->( state `%(T1)s' )--`recv %(M2)s'-->( state %(U1)s ) 2178 / 2179 ( state `%(S)s' ) 2180 \\ 2181 child: +--`send %(M2)s'-->( state `%(T2)s' )--`recv %(M1)s'-->( state %(U2)s ) 2182results in error(s) or leaves parent/child state out of sync for more than one step and is thus a race hazard; i.e., triggers `%(M1)s' and `%(M2)s' fail to commute in state `%(S)s'"""% { 2183 'P': self.p.name, 'S': S, 'M1': M1, 'M2': M2, 2184 'T1': T1, 'T2': T2, 'U1': U1, 'U2': U2 2185 }) 2186 2187 2188 def reportRunawayError(self, loc, S, t1Seq, t2Seq): 2189 T1, M1, _, T2, M2, __ = self._normalizeTransitionSequences(t1Seq, t2Seq) 2190 self.error( 2191 loc, 2192 """in protocol `%(P)s', the sequence of events 2193 parent: +--`send %(M1)s'-->( state `%(T1)s' ) 2194 / 2195 ( state `%(S)s' ) 2196 \\ 2197 child: +--`send %(M2)s'-->( state `%(T2)s' ) 2198lead to parent/child states in which parent/child state can become more than one step out of sync (though this divergence might not lead to error conditions)"""% { 2199 'P': self.p.name, 'S': S, 'M1': M1, 'M2': M2, 'T1': T1, 'T2': T2 2200 }) 2201