CoreFlat.mesa
Copyright © 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
DIRECTORY Core, CoreClasses, HashTable;
CoreFlat: CEDAR DEFINITIONS = BEGIN
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.
PathError: ERROR [msg: ROPE ← NIL];
Types
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];
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.
InstancePath: TYPE = RECORD [
length: InstancePathIndex ← 0,
bits: PACKED ARRAY InstancePathIndex OF BOOL ← ALL[FALSE]];
InstancePathIndex: TYPE = [0..64);
Caution!!! Look at the implementation of InstancePathEqual and InstancePathHash before changing this type!!!
nullInstancePath: InstancePath = [];
Cell Type
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]];
Wire
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];
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.
Bindings: TYPE = HashTable.Table;
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
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];
Returns TRUE if the flatCell is a member of the cutset.
CutSetMemberResolved: PROC [flatCell: FlatCellTypeRec, instance: CellInstance, cellType: CellType, cutSet: CutSet] RETURNS [member: BOOL];
Faster version of CutSetMember for clients that already know the instance and cellType of flatCell.
Instances
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];
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.
BindInstance: PROC [parent: FlatCellTypeRec, actual, public: WireSeq, bindings: Bindings] RETURNS [newBindings: Bindings];
Creates a new binding table which contains only the public wires as keys.
CellTypes
ParseCellTypePath: PROC [root: CellType, pathRope: ROPE, cutSet: CutSet ← NIL] RETURNS [flatCell: FlatCellTypeRec];
CellTypePathRope: PROC [root: CellType, flatCell: FlatCellTypeRec] RETURNS [pathRope: ROPE];
FlatCellTypeEqual: HashTable.EqualProc;
Parameters of this function are two REFs that must be of type FlatCellType. It is supplied to help create HashTables indexed by FlatCellTypes.
FlatCellTypeEqualRec: PROC [one, other: FlatCellTypeRec] RETURNS [equal: BOOL];
FlatCellTypeHash: HashTable.HashProc;
Parameters of this function are two REFs that must be of type FlatCellType. It is supplied to help create HashTables indexed by FlatCellTypes.
FlatCellTypeHashRec: PROC [flatCell: FlatCellTypeRec] RETURNS [hash: CARDINAL];
ResolveFlatCellType: PROC [root: CellType, flatCell: FlatCellTypeRec] RETURNS [parent: CellType, instance: CellInstance, cellType: CellType];
parent and instance may be NIL if flatCell is the root or a recast of it. parent.class=CoreClasses.recordCellClass
BoundFlatCellType: PROC [root: CellType, flatCell: FlatCellTypeRec] RETURNS [bindings: Bindings, instance: CellInstance, cellType: CellType];
Creates bindings which contain only the public wires as keys.
Wires
ParseWirePath: PROC [root: CellType, pathRope: ROPE, cutSet: CutSet ← NIL] RETURNS [flatWire: FlatWireRec];
WirePathRope: PROC [root: CellType, wire: FlatWireRec] RETURNS [pathRope: ROPE];
FlatWireEqual: HashTable.EqualProc;
Parameters of this function are two REFs that must be of the type FlatWire. It is supplied to help create HashTables indexed by FlatWires.
FlatWireEqualRec: PROC [one, other: FlatWireRec] RETURNS [equal: BOOL];
FlatWireHash: HashTable.HashProc;
Parameters of this function are two REFs that must be of the type FlatWire. It is supplied to help create HashTables indexed by FlatWires.
FlatWireHashRec: PROC [wire: FlatWireRec] RETURNS [hash: CARDINAL];
CanonizeWire: PROC [root: CellType, child: FlatWireRec] RETURNS [parent: FlatWireRec];
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];
};
NextUnboundCellType: PROC [cell: CellType, target: FlatCellTypeRec, flatCell: FlatCellTypeRec, instance: CellInstance, index: NAT, parent: CellType, flatParent: FlatCellTypeRec, data: REF ANY, proc: UnboundFlatCellProc];
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.
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];
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.
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];
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.
InitialBindingTable: PROC [root: CellType] RETURNS [bindings: Bindings];
Makes entries for all the public wires of root.
END.