DIRECTORY Core, CoreClasses, HashTable; CoreFlat: CEDAR DEFINITIONS = BEGIN PathError: ERROR [msg: ROPE _ NIL]; ROPE: TYPE = Core.ROPE; Wire: TYPE = Core.Wire; WireSeq: TYPE = Core.WireSeq; CellType: TYPE = Core.CellType; CellClass: TYPE = Core.CellClass; CellInstance: TYPE = CoreClasses.CellInstance; CutSet: TYPE = REF CutSetRec; CutSetRec: TYPE = RECORD [ instances, cellTypes, cellClasses, labels: LIST OF ROPE _ NIL, flatCells: FlatCellTypes _ NIL]; InstancePath: TYPE = RECORD [ length: InstancePathIndex _ 0, bits: PACKED ARRAY InstancePathIndex OF BOOL _ ALL[FALSE]]; InstancePathIndex: TYPE = [0..64); nullInstancePath: InstancePath = []; FlatCellTypes: TYPE = LIST OF FlatCellType; FlatCellType: TYPE = REF FlatCellTypeRec; FlatCellTypeRec: TYPE = RECORD [ path: InstancePath, recastCount: NAT _ 0]; -- do not include recasts that return the same ref rootCellType: FlatCellTypeRec = []; allFlatCells: FlatCellTypeRec = [[], LAST[NAT]]; WireRoot: TYPE = {internal, public, actual}; WirePath: TYPE = RECORD [ length: WirePathIndex _ 0, bits: PACKED ARRAY WirePathIndex OF BOOL _ ALL[FALSE]]; WirePathIndex: TYPE = [0..16); FlatWires: TYPE = LIST OF FlatWire; FlatWire: TYPE = REF FlatWireRec; FlatWireRec: TYPE = RECORD [ flatCell: FlatCellTypeRec _ rootCellType, instanceIndex: NAT _ 0, wireRoot: WireRoot _ internal, validPath: BOOL _ FALSE, path: WirePath, wire: Wire _ NIL]; Bindings: TYPE = HashTable.Table; CellInstanceCutLabels: PROC [on: CellInstance, l1, l2, l3, l4, l5, l6: ROPE _ NIL] RETURNS [same: CellInstance]; CellInstanceCutLabelList: PROC [on: CellInstance, labels: LIST OF ROPE] RETURNS [same: CellInstance]; CellTypeCutLabels: PROC [on: CellType, l1, l2, l3, l4, l5, l6: ROPE _ NIL] RETURNS [same: CellType]; CellTypeCutLabelList: PROC [on: CellType, labels: LIST OF ROPE] RETURNS [same: CellType]; CellClassCutLabels: PROC [on: CellClass, l1, l2, l3, l4, l5, l6: ROPE _ NIL] RETURNS [same: CellClass]; CellClassCutLabelList: PROC [on: CellClass, labels: LIST OF ROPE] RETURNS [same: CellClass]; CreateCutSet: PROC [instances, cellTypes, cellClasses, labels: LIST OF ROPE _ NIL, flatCells: FlatCellTypes _ NIL] RETURNS [cutSet: CutSet]; CutSetMember: PROC [root: CellType, flatCell: FlatCellTypeRec, cutSet: CutSet] RETURNS [member: BOOL]; CutSetMemberResolved: PROC [flatCell: FlatCellTypeRec, instance: CellInstance, cellType: CellType, cutSet: CutSet] RETURNS [member: BOOL]; ParseInstancePath: PROC [root: CellType, pathRope: ROPE, cutSet: CutSet _ NIL] RETURNS [path: InstancePath]; InstancePathRope: PROC [root: CellType, path: InstancePath] RETURNS [pathRope: ROPE]; InstancePathEqual: PROC [one, other: InstancePath] RETURNS [equal: BOOL]; InstancePathHash: PROC [path: InstancePath] RETURNS [hash: CARDINAL]; AddInstance: PROC [currentPath: InstancePath, instance: CoreClasses.CellInstance, parent: CellType] RETURNS [newPath: InstancePath]; ExtendPath: PROC [currentPath: InstancePath, index: NAT, rct: CoreClasses.RecordCellType] RETURNS [newPath: InstancePath]; BindInstance: PROC [parent: FlatCellTypeRec, actual, public: WireSeq, bindings: Bindings] RETURNS [newBindings: Bindings]; ParseCellTypePath: PROC [root: CellType, pathRope: ROPE, cutSet: CutSet _ NIL] RETURNS [flatCell: FlatCellTypeRec]; CellTypePathRope: PROC [root: CellType, flatCell: FlatCellTypeRec] RETURNS [pathRope: ROPE]; FlatCellTypeEqual: HashTable.EqualProc; FlatCellTypeEqualRec: PROC [one, other: FlatCellTypeRec] RETURNS [equal: BOOL]; FlatCellTypeHash: HashTable.HashProc; FlatCellTypeHashRec: PROC [flatCell: FlatCellTypeRec] RETURNS [hash: CARDINAL]; ResolveFlatCellType: PROC [root: CellType, flatCell: FlatCellTypeRec] RETURNS [parent: CellType, instance: CellInstance, cellType: CellType]; BoundFlatCellType: PROC [root: CellType, flatCell: FlatCellTypeRec] RETURNS [bindings: Bindings, instance: CellInstance, cellType: CellType]; ParseWirePath: PROC [root: CellType, pathRope: ROPE, cutSet: CutSet _ NIL] RETURNS [flatWire: FlatWireRec]; WirePathRope: PROC [root: CellType, wire: FlatWireRec] RETURNS [pathRope: ROPE]; FlatWireEqual: HashTable.EqualProc; FlatWireEqualRec: PROC [one, other: FlatWireRec] RETURNS [equal: BOOL]; FlatWireHash: HashTable.HashProc; FlatWireHashRec: PROC [wire: FlatWireRec] RETURNS [hash: CARDINAL]; CanonizeWire: PROC [root: CellType, child: FlatWireRec] RETURNS [parent: FlatWireRec]; NextUnboundCellType: PROC [cell: CellType, target: FlatCellTypeRec, flatCell: FlatCellTypeRec, instance: CellInstance, index: NAT, parent: CellType, flatParent: FlatCellTypeRec, data: REF ANY, proc: UnboundFlatCellProc]; UnboundFlatCellProc: TYPE = PROC [cell: CellType, target: FlatCellTypeRec _ allFlatCells, flatCell: FlatCellTypeRec _ [], instance: CellInstance _ NIL, index: NAT _ LAST[NAT], parent: CellType _ NIL, flatParent: FlatCellTypeRec _ [], data: REF ANY _ NIL]; NextBoundCellType: PROC [cell: CellType, target: FlatCellTypeRec, flatCell: FlatCellTypeRec, instance: CellInstance, index: NAT, parent: CellType, flatParent: FlatCellTypeRec, data: REF ANY, bindings: Bindings, proc: BoundFlatCellProc]; BoundFlatCellProc: TYPE = PROC [cell: CellType, target: FlatCellTypeRec _ allFlatCells, flatCell: FlatCellTypeRec _ [], instance: CellInstance _ NIL, index: NAT _ LAST[NAT], parent: CellType _ NIL, flatParent: FlatCellTypeRec _ [], data: REF ANY _ NIL, bindings: Bindings _ NIL]; InitialBindingTable: PROC [root: CellType] RETURNS [bindings: Bindings]; END. TCoreFlat.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Barth, February 18, 1987 6:25:55 pm PST Spreitzer, April 8, 1986 4:29:29 pm PST Bertrand Serlet October 17, 1986 2:44:31 pm PDT Mike Spreitzer November 18, 1986 2:40:01 pm PST Theory This interface supports the enumeration of cell types reachable from a root cell type and syntatic sugar for describing textually the hierarchical structure. A cut set defines a slice through the instantiation tree. It controls the boundaries of the design which can be explored by the enumeration and parsing procedures. The limitation of the search space is needed to prevent unwanted recasting which may be very expensive or impossible to compute. A cut is a place in the instantiation tree beyound which the design is not to be explored if the cut is a member of the current cut set. A cut set may contain a collection of any of a specific flat cell type, the name of a cell type, the name of a cell class, or a rope that specifies a cut label. Cut labels may be placed on cell instances, cell types, and cell classes. Cell types, instances, and wires may be named with ropes and data structures defined by this interface. Procedures are provided to convert from a rope to a data structure and back again. The following grammar gives the syntax for each type of name. Syntax Notation item | item = choose one ?item = zero or one item SMALL CAPS or puncuation other than bold ()?| = terminals ::= = keyword on left hand side is defined by expression on right hand side Grammar InstancePath ::= ?( / ( Name | (Number ?( ( Name ) )) ) ?( InstancePath ) ) CellTypePath ::= CellTypeLeftSide ?(* ( Name | (Number ?( ( Name ) ))) CellTypeLeftSide ::= CellTypePath | InstancePath WirePath ::= WireLeftSide ( ( . ( Name | Number )) | ( [Number] ) ) WireLeftSide ::= WirePath | ( CellTypePath ?( . (PUBLIC | INTERNAL | ACTUAL))) Name ::= Letter ?LetterDigitString LetterDigitString ::= (Letter | Digit) ?LetterDigitString Number ::= Digit ?Number Letter ::= one of a-z | one of A-Z Digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Grammar Notes White space may appear anywhere except inside Name or Number. Reserved words are matched ignoring case. ACTUAL causes the wire path to begin at the actual of the last instance of the instance path and then use the public names of the last cell type to index the actual. PUBLIC and INTERNAL cause the wire path to begin at the public or internal of the last cell type. If none of ACTUAL, PUBLIC, or INTERNAL appear then INTERNAL is assumed. The name in the instance path may be the instance name or, if unambiguous, the cell type name. The name in parantheses in the InstancePath rule must be the cell type name. A name in the CellTypePath rule must be the name of a cell class into which the cell type may be recasted. The number in a cell type path is the number of times the cell type is recasted to get to the named cell type. When a cell class name appears the cell type is recasted until the cell class named is found. Types Instance An InstancePath can only be interpreted given a root cell type. An InstancePath contains the same information as an InstantiationPath but in a more compact form. Clients should not need to interpret an instance path directly. They should use the procedures in this interface. Caution!!! Look at the implementation of InstancePathEqual and InstancePathHash before changing this type!!! Cell Type Wire flatCell names the CellType which contains the wire as an internal or public. IF wireRoot=actual THEN instanceIndex says of which instance of flatCell the wire is an actual. The wirePath is for clients which wish to keep track of exactly how this wire was reached from the wire root. ParseWirePath sets this field and then sets validPath to TRUE. No procedure in this interface relies on validPath being TRUE. A number of procedures in this interface have bindings as arguments or results. The bindings are hash tables which have wires for keys and FlatWires for values. The value in a binding indicates to which wire the key is bound. Cut Sets Returns TRUE if the flatCell is a member of the cutset. Faster version of CutSetMember for clients that already know the instance and cellType of flatCell. Instances Given the current path to a parent, the RecordCellType of the parent, and the index of an instance in the RecordCellType, extends the old path to include the instance. Creates a new binding table which contains only the public wires as keys. CellTypes Parameters of this function are two REFs that must be of type FlatCellType. It is supplied to help create HashTables indexed by FlatCellTypes. Parameters of this function are two REFs that must be of type FlatCellType. It is supplied to help create HashTables indexed by FlatCellTypes. parent and instance may be NIL if flatCell is the root or a recast of it. parent.class=CoreClasses.recordCellClass Creates bindings which contain only the public wires as keys. Wires Parameters of this function are two REFs that must be of the type FlatWire. It is supplied to help create HashTables indexed by FlatWires. Parameters of this function are two REFs that must be of the type FlatWire. It is supplied to help create HashTables indexed by FlatWires. Discovers the leftmost, highest wire to which the wire is bound. Enumeration This is a prototype for using the enumeration procedures. Flatten: PROC [root: CellType] = { FlattenCell: CoreFlat.BoundFlatCellProc = { IF -- cell is not a leaf cell -- THEN { -- Handle nonleaf cells here. -- Handle initialization prior to visiting children here. IF cell.class=CoreClasses.recordCellClass THEN { -- Handle special initialization for record cells here. }; CoreFlat.NextBoundCellType[cell, target, flatCell, instance, parent, flatParent, bindings, FlattenCell] -- Handle cleanup after visiting children here. } ELSE { -- Handle leaf cells here. }; }; FlattenCell[root]; }; Moves from CellType to CellType according to the Core hierarchy by Recasting and enumerating children. May be directed by target, or made to explore all by target=allFlatCells. [instance, cell] = ResolveFlatCellType[root, flatCell]. index is the number of the instance in the parent record cell type. [, parent] = ResolveFlatCellType[root, flatParent]. The flatCell is a child of flatParent, possibly recasted some. Except when the flatCell is (a Recast of) the root, in which case flatParent=rootCellType and parent=NIL. data is for client use. It is passed through unmodified to proc. Same invariants apply. Normally a procedure of this type is called with the root cell type to start the recursion. If cell=instance.type then a new recast chain is starting. If index is the default value then the index is unknown. Same as UnboundFlatCellProc but bindings are included. Only public wires of cell are in the bindings. The root call to start the recursion has bindings=NIL. Makes entries for all the public wires of root. Ê {˜codešœ ™ Kšœ Ïmœ1™Kšœžœ˜ K˜—™Mšœ–™–K™šœžœžœ˜Kšœ˜Kš œžœžœžœžœžœžœ˜;K˜—šœžœ ˜"Kšœm™m—K˜šœ$˜$K™——™ Kšœžœžœžœ˜+Kšœžœžœ˜)šœžœžœ˜ Kšœ˜Kšœ žœÏc2˜J—K˜Kšœ#˜#šœ%žœžœ˜0K˜——™šœ žœ˜,K˜—šœ žœžœ˜Kšœ˜Kš œžœžœžœžœžœžœ˜7—K˜šœžœ ˜K™—Kšœ žœžœžœ ˜#Kšœ žœžœ ˜!šœ žœžœ˜Kšœ)˜)Kšœžœ˜K˜Kšœ žœžœ˜Kšœ˜Kšœ žœ˜Kš œOžœžœòžœ<žœ™K˜—šœ žœ˜!K™ãK˜———™š Ÿœžœ,žœžœžœ˜pJ˜—š Ÿœžœžœžœžœžœ˜eJ˜—š Ÿœžœ(žœžœžœ˜dJ˜—š Ÿœžœžœžœžœžœ˜YJ˜—š Ÿœžœ)žœžœžœ˜gJ˜—š Ÿœžœžœžœžœžœ˜\J˜—šŸ œžœ-žœžœžœžœžœžœ˜ŒK˜—šŸ œžœ=žœ žœ˜fKšœžœ+™7K˜—šŸœžœYžœ žœ˜ŠKšœc™cK˜——™ š Ÿœžœžœžœžœ˜lK˜—šŸœžœ&žœ žœ˜UK˜—šŸœžœžœ žœ˜IK˜—šŸœžœžœžœ˜EK˜—šŸ œžœSžœ˜„K˜—šŸ œžœ$žœ#žœ˜zKšœ§™§K™—šŸ œžœHžœ˜zK™IK˜——™ š Ÿœžœžœžœžœ˜sK˜—šŸœžœ-žœ žœ˜\K˜—šŸœ˜'Jšœ$žœg™K˜—šŸœžœžœ žœ˜OK˜—šŸœ˜%Jšœ$žœg™K˜—šŸœžœžœžœ˜OK˜—šŸœžœ-žœ@˜KšœžœU™sK˜—šŸœžœ-žœB˜Kšœ=™=K˜——™š Ÿ œžœžœžœžœ˜kK˜—šŸ œžœ%žœ žœ˜PK˜—šŸ œ˜#Jšœ$žœ¡œ7¡œ™‹K˜—šŸœžœžœ žœ˜GK˜—šŸ œ˜!Jšœ$žœ¡œ7¡œ™‹K˜—šŸœžœžœžœ˜CK˜—šŸ œžœ&žœ˜VK™@K˜——™ ™Kšœ9™9K™šŸœžœ™"K™šŸ œ ™+šžœžœ™'K™K™9™0K™7K™—Kšœg™gK™/K™—šžœ™Kšœ™Kšœ™—Kšœ™K™—Kšœ™K™K™——š Ÿœžœežœ7žœžœ˜ÜKšœ±™±Kšœ7™7K™CKšœ3™3Kšœì™ìK˜šœžœžœsžœ žœžœžœžœ*žœžœžœ˜ÿKšœé™éK˜——š Ÿœžœežœ7žœžœ/˜ìK˜šœžœžœsžœ žœžœžœžœ*žœžœžœžœ˜—Jšœšž™žK˜——šŸœžœžœ˜HK™/K™——Kšžœ˜—…—X:'