CoreFlatImpl.mesa
Copyright Ó 1985, 1986, 1987 by Xerox Corporation. All rights reserved.
Barth, October 5, 1987 5:37:58 pm PDT
Last Edited by: Gasbarro October 21, 1987 12:25:04 pm PDT
Last Edited by: Louis Monier January 20, 1987 10:42:41 am PST
Last tweaked by Mike Spreitzer on November 2, 1987 3:53:04 pm PST
Jean-Marc Frailong December 26, 1987 8:14:36 pm PST
Bertrand Serlet September 25, 1987 1:08:03 pm PDT
Mike Spreitzer February 27, 1987 3:45:39 pm PST
Cut Sets
cutLabelProp:
ATOM ← CoreProperties.RegisterProperty[$CoreCutLabel];
CellInstanceCutLabels:
PUBLIC
PROC [on: CellInstance, l1, l2, l3, l4, l5, l6:
ROPE ←
NIL]
RETURNS [same: CellInstance] = {
same ← CellInstanceCutLabelList[on, LabelList[l1, l2, l3, l4, l5, l6]]
};
CellInstanceCutLabelList:
PUBLIC
PROC [on: CellInstance, labels:
LIST
OF
ROPE]
RETURNS [same: CellInstance] = {
lbls: LIST OF ROPE ← NARROW[CoreProperties.GetCellInstanceProp[on, cutLabelProp]];
lbls ← CombineLabelLists[lbls, labels];
CoreProperties.PutCellInstanceProp[on, cutLabelProp, lbls];
same ← on;
};
CellTypeCutLabels:
PUBLIC
PROC [on: CellType, l1, l2, l3, l4, l5, l6:
ROPE ←
NIL]
RETURNS [same: CellType] = {
same ← CellTypeCutLabelList[on, LabelList[l1, l2, l3, l4, l5, l6]]
};
CellTypeCutLabelList:
PUBLIC
PROC [on: CellType, labels:
LIST
OF
ROPE]
RETURNS [same: CellType] = {
lbls: LIST OF ROPE ← NARROW[CoreProperties.GetCellTypeProp[on, cutLabelProp]];
lbls ← CombineLabelLists[lbls, labels];
CoreProperties.PutCellTypeProp[on, cutLabelProp, lbls];
same ← on;
};
CellClassCutLabels:
PUBLIC
PROC [on: CellClass, l1, l2, l3, l4, l5, l6:
ROPE ←
NIL]
RETURNS [same: CellClass] = {
same ← CellClassCutLabelList[on, LabelList[l1, l2, l3, l4, l5, l6]]
};
CellClassCutLabelList:
PUBLIC
PROC [on: CellClass, labels:
LIST
OF
ROPE]
RETURNS [same: CellClass] = {
lbls: LIST OF ROPE ← NARROW[CoreProperties.GetCellClassProp[on, cutLabelProp]];
lbls ← CombineLabelLists[lbls, labels];
CoreProperties.PutCellClassProp[on, cutLabelProp, lbls];
same ← on;
};
CreateCutSet:
PUBLIC
PROC [instances, cellTypes, cellClasses, labels:
LIST
OF
ROPE ←
NIL, flatCells: FlatCellTypes ←
NIL, flatten: FlatCellTypes ←
NIL, change: FlatCellTypeCutSets ←
NIL]
RETURNS [cutSet: CutSet] = {
cutSet ←
NEW[CutSetRec ← [
instances: instances,
cellTypes: cellTypes,
cellClasses: cellClasses,
labels: labels,
flatCells: flatCells,
flatten: flatten,
change: change]];
};
CutSetMember:
PUBLIC
PROC [root: CellType, flatCell: FlatCellTypeRec, cutSet: CutSet]
RETURNS [member:
BOOL ←
FALSE] = {
parent: CellType;
instance: CellInstance;
cellType: CellType;
[parent, instance, cellType] ← ResolveFlatCellType[root, flatCell];
member ← CutSetMemberResolved[flatCell, instance, cellType, cutSet]
};
CutSetMemberResolved:
PUBLIC
PROC [flatCell: FlatCellTypeRec, instance: CellInstance, cellType: CellType, cutSet: CutSet]
RETURNS [member:
BOOL ←
FALSE] = {
name: ROPE ← NIL;
IF cellType.class=CoreClasses.transistorCellClass OR cellType.class=CoreClasses.unspecifiedCellClass THEN RETURN[TRUE];
IF cutSet=NIL THEN RETURN[FALSE];
FOR cl: FlatCellTypeCutSets ← cutSet.change, cl.rest
UNTIL cl=
NIL
DO
IF flatCell.path.length >= cl.first.flatCell.path.length
THEN {
FOR i: InstancePathIndex
IN [0..cl.first.flatCell.path.length)
DO
IF flatCell.path.bits[i]#cl.first.flatCell.path.bits[i] THEN EXIT;
REPEAT FINISHED => RETURN[CutSetMemberResolved[flatCell, instance, cellType, cl.first.cutSet]];
ENDLOOP;
};
ENDLOOP;
FOR flats: FlatCellTypes ← cutSet.flatten, flats.rest
UNTIL flats=
NIL
DO
IF FlatCellTypeEqualRec[flats.first^, flatCell] THEN RETURN[FALSE];
ENDLOOP;
FOR flats: FlatCellTypes ← cutSet.flatCells, flats.rest
UNTIL flats=
NIL
DO
IF FlatCellTypeEqualRec[flats.first^, flatCell] THEN RETURN[TRUE];
ENDLOOP;
IF instance#
NIL
THEN {
name ← CoreClasses.GetCellInstanceName[instance];
IF name#NIL THEN IF OneInOther[LIST[name], cutSet.instances] THEN RETURN [TRUE];
};
name ← CoreOps.GetCellTypeName[cellType];
IF name#NIL THEN IF OneInOther[LIST[name], cutSet.cellTypes] THEN RETURN [TRUE];
IF OneInOther[LIST[cellType.class.name], cutSet.cellClasses] THEN RETURN [TRUE];
IF instance#NIL THEN IF OneInOther[NARROW[CoreProperties.GetCellInstanceProp[instance, cutLabelProp]], cutSet.labels] THEN RETURN [TRUE];
IF OneInOther[NARROW[CoreProperties.GetCellTypeProp[cellType, cutLabelProp]], cutSet.labels] THEN RETURN [TRUE];
IF OneInOther[NARROW[CoreProperties.GetCellClassProp[cellType.class, cutLabelProp]], cutSet.labels] THEN RETURN [TRUE];
};
OneInOther:
PROC [one, other:
LIST
OF
ROPE]
RETURNS [yes:
BOOL ←
FALSE] = {
FOR this:
LIST
OF
ROPE ← one, this.rest
UNTIL this=
NIL
DO
FOR that:
LIST
OF
ROPE ← other, that.rest
UNTIL that=
NIL
DO
IF Rope.Equal[CoreOps.FixStupidRef[this.first], CoreOps.FixStupidRef[that.first]] THEN RETURN[TRUE];
ENDLOOP;
ENDLOOP;
};
LabelList:
PROC [l1, l2, l3, l4, l5, l6:
ROPE ←
NIL]
RETURNS [labels:
LIST
OF
ROPE ←
NIL] = {
IF l1#NIL THEN labels ← CONS[l1, labels];
IF l2#NIL THEN labels ← CONS[l2, labels];
IF l3#NIL THEN labels ← CONS[l3, labels];
IF l4#NIL THEN labels ← CONS[l4, labels];
IF l5#NIL THEN labels ← CONS[l5, labels];
IF l6#NIL THEN labels ← CONS[l6, labels];
};
CombineLabelLists:
PROC [l1, l2:
LIST
OF
ROPE ←
NIL]
RETURNS [combined:
LIST
OF
ROPE] = {
combined ← l1;
FOR lbls:
LIST
OF
ROPE ← l2, lbls.rest
UNTIL lbls=
NIL
DO
combined ← CONS[lbls.first, combined];
ENDLOOP;
};
BelowCutSet:
PUBLIC
PROC [root: CellType, flatCell: FlatCellTypeRec, cutSet: CutSet]
RETURNS [below:
BOOL ←
FALSE] = {
SearchForCut: UnboundFlatCellProc = {
SELECT
TRUE
FROM
FlatCellTypeEqualRec[flatCell, target] => NULL;
CutSetMemberResolved[flatCell, instance, cell, cutSet] => below ← TRUE;
ENDCASE => NextUnboundCellType[cell, target, flatCell, instance, index, parent, flatParent, data, SearchForCut];
};
SearchForCut[cell: root, target: flatCell];
};
Instances
ParseInstancePath:
PUBLIC
PROC [root: CellType, pathRope:
ROPE, cutSet: CutSet]
RETURNS [path: InstancePath] = {
instance: CellInstance;
within: CellType;
token: ROPE;
ts: IO.STREAM;
firstChar: CHAR;
tokenKind: IO.TokenKind;
[path, instance, within, token, ts, firstChar, tokenKind] ← ParsePartialInstancePath[root, pathRope, cutSet];
path ← AddInstance[path, instance, within];
CheckNoMore[ts, firstChar, tokenKind];
};
InstancePathRope:
PUBLIC
PROC [root: CellType, path: InstancePath]
RETURNS [pathRope:
ROPE ←
NIL] = {
AppendName: UnboundFlatCellProc = {
IF instance#
NIL AND cell=instance.type
THEN {
name: ROPE ← CoreClasses.GetCellInstanceName[instance];
IF name=
NIL
THEN {
cellTypeName: ROPE ← CoreOps.InheritCellTypeName[instance.type];
name ← Convert.RopeFromInt[CoreClasses.InstanceIndex[parent, instance]];
IF cellTypeName#NIL THEN name ← Rope.Cat[name, "(", cellTypeName, ")"];
};
pathRope ← Rope.Cat[pathRope, "/", name];
};
NextUnboundCellType[cell, target, flatCell, instance, index, parent, flatParent, data, AppendName];
};
AppendName[root, [path, 0]];
};
InstancePathEqual:
PUBLIC
PROC [one, other: InstancePath]
RETURNS [equal:
BOOL] = {
equal ← one.length=other.length AND one.bits=other.bits;
oneBits: ARRAY [0..2) OF INT ← LOOPHOLE[one.bits];
otherBits: ARRAY [0..2) OF INT ← LOOPHOLE[other.bits];
equal ← one.length=other.length AND oneBits=otherBits;
IF equal THEN FOR bit: NAT IN [0..one.length) DO
IF one.bits[bit]#other.bits[bit] THEN {
equal ← FALSE;
EXIT;
};
ENDLOOP;
};
InstancePathHash:
PUBLIC
PROC [path: InstancePath]
RETURNS [hash:
CARDINAL ← 0] = {
bits: BitOps.BitQWord ← BitOps.QuadShift[LOOPHOLE[path.bits], path.length-64];
FOR i:
NAT
IN [0..4)
DO
hash ← Basics.BITXOR[hash, bits[i]];
ENDLOOP;
};
AddInstance:
PUBLIC
PROC [currentPath: InstancePath, instance: CoreClasses.CellInstance, parent: CellType]
RETURNS [newPath: InstancePath] = {
newPath ← currentPath;
IF instance#
NIL
THEN {
withinCT: CellType ← CoreOps.ToBasic[parent];
withinRCT: CoreClasses.RecordCellType ← NARROW[withinCT.data];
index: NAT ← CoreClasses.InstanceIndex[withinCT, instance];
IF index=-1 THEN ERROR; -- instance not found in parent CellType
newPath ← ExtendPath[currentPath, index, withinRCT];
};
};
ExtendPath:
PUBLIC
PROC [currentPath: InstancePath, index:
NAT, rct: CoreClasses.RecordCellType]
RETURNS [newPath: InstancePath] = {
pathBits: NAT ← BitOps.NBits[rct.size];
newPath ← currentPath;
FOR bit:
NAT
IN [0..pathBits)
DO
newPath.bits[newPath.length+bit] ← BitOps.EBFW[index, bit, pathBits];
ENDLOOP;
newPath.length ← newPath.length + pathBits;
};
BindInstance:
PUBLIC
PROC [parent: FlatCellTypeRec, actual, public: WireSeq, bindings: Bindings]
RETURNS [newBindings: Bindings] = {
BindPublicToActual: CoreOps.EachWirePairProc = {
bind: FlatWire ← NIL;
IF bindings#NIL THEN bind ← NARROW [RefTab.Fetch[x: bindings, key: actualWire].val];
[] ← RefTab.Store[x: newBindings, key: publicWire, val: IF bind=NIL THEN NEW[FlatWireRec ← [flatCell: parent, wire: actualWire]] ELSE bind];
};
newBindings ← RefTab.Create[public.size+1];
IF CoreOps.VisitBindingSeq[actual: actual, public: public, eachWirePair: BindPublicToActual] THEN ERROR;
};
RaiseRootOfInstancePath:
PUBLIC
PROC [by, path: InstancePath]
RETURNS [raised: InstancePath] ~ {
length: NATURAL ~ NATURAL[path.length] + by.length;
raised ← [
length: length,
bits:
LOOPHOLE[BitOps.
QOR[
LOOPHOLE[by.bits],
BitOps.QShift[LOOPHOLE[path.bits], -by.length]
]]];
RETURN};
CellTypes
ParseCellTypePath:
PUBLIC
PROC [root: CellType, pathRope:
ROPE, cutSet: CutSet]
RETURNS [flatCell: FlatCellTypeRec] = {
instance: CellInstance;
within: CellType;
token: ROPE;
ts: IO.STREAM;
firstChar: CHAR;
tokenKind: IO.TokenKind;
thisCell: CellType;
[flatCell, instance, within, token, ts, firstChar, tokenKind, thisCell] ← ParsePartialCellTypePath[root, pathRope, cutSet];
flatCell.path ← AddInstance[flatCell.path, instance, within];
CheckNoMore[ts, firstChar, tokenKind];
};
CellTypePathRope:
PUBLIC
PROC [root: CellType, flatCell: FlatCellTypeRec]
RETURNS [pathRope:
ROPE] = {
pathRope ← InstancePathRope[root, flatCell.path];
IF flatCell.recastCount>0 THEN pathRope ← Rope.Cat[pathRope, "*", Convert.RopeFromInt[flatCell.recastCount]];
};
FlatCellTypeEqual:
PUBLIC
PROC [key1, key2:
REF
ANY]
RETURNS [equal:
BOOL] = {
equal ← FlatCellTypeEqualRec[NARROW [key1, FlatCellType]^, NARROW [key2, FlatCellType]^];
};
FlatCellTypeEqualRec:
PUBLIC
PROC [one, other: FlatCellTypeRec]
RETURNS [equal:
BOOL] = {
equal ← InstancePathEqual[one.path, other.path] AND one.recastCount=other.recastCount;
};
FlatCellTypeHash:
PUBLIC
PROC [flatCell:
REF
ANY]
RETURNS [hash:
CARDINAL] = {
hash ← FlatCellTypeHashRec[NARROW[flatCell, FlatCellType]^];
};
FlatCellTypeHashRec:
PUBLIC
PROC [flatCell: FlatCellTypeRec]
RETURNS [hash:
CARDINAL] = {
hash ← InstancePathHash[flatCell.path];
hash ← Basics.BITXOR[hash, flatCell.recastCount];
};
ResolveFlatCellType:
PUBLIC
PROC [root: CellType, flatCell: FlatCellTypeRec]
RETURNS [parent: CellType, instance: CellInstance, cellType: CellType] = {
Search: UnboundFlatCellProc = {
upParent ← parent;
upInstance ← instance;
upCellType ← cell;
NextUnboundCellType[cell, target, flatCell, instance, index, parent, flatParent, data, Search]
};
upParent: CellType ← NIL;
upInstance: CellInstance ← NIL;
upCellType: CellType ← NIL;
Search[cell: root, target: flatCell];
parent ← upParent;
instance ← upInstance;
cellType ← upCellType;
};
BoundFlatCellType:
PUBLIC
PROC [root: CellType, flatCell: FlatCellTypeRec]
RETURNS [bindings: Bindings, instance: CellInstance, cellType: CellType] = {
Search: BoundFlatCellProc = {
upBindings ← bindings;
upInstance ← instance;
upCellType ← cell;
NextBoundCellType[cell, target, flatCell, instance, index, parent, flatParent, data, bindings, Search]
};
upBindings: Bindings ← NIL;
upInstance: CellInstance ← NIL;
upCellType: CellType ← NIL;
Search[cell: root, target: flatCell];
bindings ← upBindings;
instance ← upInstance;
cellType ← upCellType;
};
FindAnyFlatCell:
PUBLIC
PROC [root: CellType, cellType: CellType]
RETURNS [flatCellType: FlatCellTypeRec ← []] = {
Find:
PROC [cell: CellType, flatCell: FlatCellTypeRec ← []]
RETURNS [
BOOL] = {
IF RefTab.Fetch[cellTypeVisit, cell].found THEN RETURN [FALSE];
IF NOT RefTab.Insert[cellTypeVisit, cell, $Visited] THEN ERROR;
IF cell=cellType
THEN {
flatCellType ← flatCell;
RETURN [TRUE];
};
SELECT
TRUE
FROM
cell.class=CoreClasses.transistorCellClass => NULL;
cell.class=CoreClasses.recordCellClass => {
rct: CoreClasses.RecordCellType ← NARROW[cell.data];
FOR i:
NAT
IN [0..rct.size)
DO
IF Find[rct[i].type, [ExtendPath[flatCell.path, i, rct], 0]] THEN RETURN [TRUE];
ENDLOOP;
};
ENDCASE => {
new: CellType ← CoreOps.Recast[cell];
IF Find[new, [flatCell.path, IF cell=new THEN flatCell.recastCount ELSE flatCell.recastCount+1]] THEN RETURN [TRUE];
};
RETURN [FALSE];
};
cellTypeVisit: RefTab.Ref ← RefTab.Create[]; -- Marks visited cells
IF NOT Find[root] THEN ERROR PathError["Cell type is not reachable from root"];
};
RaiseRootOfFlatCell:
PUBLIC
PROC [by: InstancePath, flatCell: FlatCellTypeRec]
RETURNS [raised: FlatCellTypeRec] ~ {
raised ← flatCell;
raised.path ← RaiseRootOfInstancePath[by, raised.path];
RETURN};
Wires
ParseWirePath:
PUBLIC
PROC [root: CellType, pathRope:
ROPE, cutSet: CutSet]
RETURNS [flatWire: FlatWireRec] = {
AddWire:
PROC [subWire:
NAT] = {
pathBits: NAT ← BitOps.NBits[flatWire.wire.size];
instanceBits: PACKED ARRAY [0..16) OF BOOL ← LOOPHOLE[subWire];
FOR bit:
NAT
IN [0..pathBits)
DO
flatWire.path.bits[flatWire.path.length+bit] ← instanceBits[16-pathBits+bit];
ENDLOOP;
flatWire.path.length ← flatWire.path.length + pathBits;
flatWire.wire ← flatWire.wire[subWire];
IF flatWire.wireRoot=actual THEN publicWire ← publicWire[subWire];
};
InternalRoot:
PROC = {
rct: CoreClasses.RecordCellType ← NIL;
flatWire.flatCell.path ← AddInstance[flatWire.flatCell.path, instance, within];
flatWire.flatCell.recastCount ← 0;
[rct, flatWire.flatCell] ← MakeRecord[IF instance=NIL THEN root ELSE instance.type, instance, flatWire.flatCell, cutSet];
flatWire.wire ← rct.internal;
flatWire.wireRoot ← internal;
};
ParseQuotedNameWire:
PROC = {
depth: NAT ← 1;
DO
char: CHAR ← IO.GetChar[ts ! IO.EndOfStream => GOTO oops];
token ← Rope.Cat[token, Rope.FromChar[char]];
SELECT char
FROM
'{ => depth ← depth+1;
'} => {IF depth=1 THEN EXIT; depth ← depth-1};
ENDCASE;
ENDLOOP;
EXITS oops => MakeError["Missing end brace on quoted short name"];
};
AppendNameWire:
PROC = {
state ← sawWireNameOrNumber;
IF RootWire[]#none THEN MakeError["Cannot name a wire actual, internal, or public"];
FOR subWire:
CARDINAL
IN [0..flatWire.wire.size)
DO
IF Rope.Equal[token, CoreOps.GetShortWireName[
IF flatWire.wireRoot=actual
THEN publicWire[subWire]
ELSE flatWire.wire[subWire]]]
THEN {
AddWire[subWire];
EXIT;
};
REPEAT
FINISHED => {
-- This hack is for Don Curry's benefit
hackName: ROPE ← token;
DO
[token, firstChar, tokenKind] ← ParseToken[ts ! IO.EndOfStream => EXIT];
hackName ← Rope.Cat[hackName, token];
ENDLOOP;
FOR subWire:
CARDINAL
IN [0..flatWire.wire.size)
DO
IF Rope.Equal[hackName, CoreOps.GetShortWireName[
IF flatWire.wireRoot=actual
THEN publicWire[subWire]
ELSE flatWire.wire[subWire]]]
THEN {
AddWire[subWire];
EXIT;
};
REPEAT FINISHED => MakeError["Can't find wire"];
ENDLOOP;
};
ENDLOOP;
};
AppendNumberWire:
PROC = {
subWire: CARDINAL ← Convert.CardFromRope[token];
IF flatWire.wire=NIL THEN InternalRoot[];
IF subWire>=flatWire.wire.size THEN MakeError["No such wire"];
AddWire[subWire];
};
PossibleRootWire:
PROC = {
wireType: RootWireType ← RootWire[];
SELECT wireType
FROM
public => {
state ← sawWireRoot;
flatWire.flatCell.path ← AddInstance[flatWire.flatCell.path, instance, within];
flatWire.wire ← thisCell.public;
flatWire.wireRoot ← public;
};
internal => {
state ← sawWireRoot;
InternalRoot[];
};
actual => {
parentCT: CellType ← within;
IF instance=NIL THEN MakeError["Can't access actual of root"];
state ← sawWireRoot;
flatWire.wire ← instance.actual;
publicWire ← instance.type.public;
flatWire.wireRoot ← actual;
flatWire.flatCell.recastCount ← 0;
UNTIL parentCT.class=CoreClasses.recordCellClass
DO
new: CellType ← CoreOps.Recast[parentCT];
IF new#parentCT THEN flatWire.flatCell.recastCount ← flatWire.flatCell.recastCount + 1;
parentCT ← new;
ENDLOOP;
flatWire.instanceIndex ← CoreClasses.InstanceIndex[parentCT, instance];
};
none => {
InternalRoot[];
AppendNameWire[];
};
ENDCASE => ERROR;
};
RootWireType:
TYPE = {public, internal, actual, none};
RootWire:
PROC
RETURNS [RootWireType] = {
RETURN [
SELECT
TRUE
FROM
Rope.Equal[token, "PUBLIC", FALSE] => public,
Rope.Equal[token, "INTERNAL", FALSE] => internal,
Rope.Equal[token, "ACTUAL", FALSE] => actual,
ENDCASE => none];
};
WirePath ::= {start} ?((PUBLIC | INTERNAL | ACTUAL ) {sawWireRoot} . {expectWireNameOrNumber} ) (( QuotedName | Name | Number ) {sawWireNameOrNumber} ?( . {expectWireNameOrNumber})) | ( [ {sawLeft} Number {sawNumber} ] {sawRight} )
WirePathParseStates: TYPE = {start, expectMaybeRoot, sawWireRoot, expectWireNameOrNumber, sawWireNameOrNumber, sawLeft, sawNumber, sawRight};
instance: CoreClasses.CellInstance;
within: CellType;
token: ROPE;
ts: IO.STREAM;
firstChar: CHAR;
tokenKind: IO.TokenKind;
thisCell: CellType;
publicWire: Wire ← NIL;
state: WirePathParseStates ← start;
[flatWire.flatCell, instance, within, token, ts, firstChar, tokenKind, thisCell] ← ParsePartialCellTypePath[root, pathRope, cutSet];
flatWire.validPath ← TRUE;
DO
SELECT state
FROM
start =>
SELECT tokenKind
FROM
tokenSINGLE =>
SELECT firstChar
FROM
'[ => state ← sawLeft;
'. => state ← expectMaybeRoot;
'{ => {ParseQuotedNameWire[]; PossibleRootWire[]};
ENDCASE => MakeError[];
tokenID => PossibleRootWire[];
tokenDECIMAL => {AppendNumberWire[]; state ← sawWireNameOrNumber};
ENDCASE => MakeError[];
expectMaybeRoot =>
SELECT tokenKind
FROM
tokenSINGLE =>
SELECT firstChar
FROM
'[ => state ← sawLeft;
'{ => {ParseQuotedNameWire[]; PossibleRootWire[]};
ENDCASE => MakeError[];
tokenID => PossibleRootWire[];
tokenDECIMAL => {AppendNumberWire[]; state ← sawWireNameOrNumber};
ENDCASE => MakeError[];
sawWireRoot =>
SELECT tokenKind
FROM
tokenSINGLE =>
SELECT firstChar
FROM
'. => state ← expectWireNameOrNumber;
ENDCASE => MakeError[];
ENDCASE => MakeError[];
expectWireNameOrNumber =>
SELECT tokenKind
FROM
tokenSINGLE =>
SELECT firstChar
FROM
'[ => state ← sawLeft;
'{ => {ParseQuotedNameWire[]; AppendNameWire[]};
ENDCASE => MakeError[];
tokenID => AppendNameWire[];
tokenDECIMAL => {AppendNumberWire[]; state ← sawWireNameOrNumber};
ENDCASE => MakeError[];
sawWireNameOrNumber =>
SELECT tokenKind
FROM
tokenSINGLE =>
SELECT firstChar
FROM
'. => state ← expectWireNameOrNumber;
'[ => state ← sawLeft;
ENDCASE => MakeError[];
ENDCASE => MakeError[];
sawLeft =>
SELECT tokenKind
FROM
tokenDECIMAL => {AppendNumberWire[]; state ← sawNumber};
ENDCASE => MakeError[];
sawNumber =>
SELECT tokenKind
FROM
tokenSINGLE =>
SELECT firstChar
FROM
'] => state ← sawRight;
ENDCASE => MakeError[];
ENDCASE => MakeError[];
sawRight =>
SELECT tokenKind
FROM
tokenSINGLE =>
SELECT firstChar
FROM
'. => state ← expectWireNameOrNumber;
'[ => state ← sawLeft;
'{ => {ParseQuotedNameWire[]; AppendNameWire[]};
ENDCASE => MakeError[];
tokenID => AppendNameWire[];
tokenDECIMAL => {AppendNumberWire[]; state ← sawWireNameOrNumber};
ENDCASE => MakeError[];
ENDCASE => MakeError[];
[token, firstChar, tokenKind] ← ParseToken[ts ! IO.EndOfStream => {tokenKind ← tokenEOF; EXIT}];
ENDLOOP;
IF state=sawWireRoot OR state=expectWireNameOrNumber OR state=sawLeft OR state=sawNumber THEN MakeError[];
};
WirePathRope:
PUBLIC
PROC [root: CellType, wire: FlatWireRec]
RETURNS [pathRope:
ROPE] = {
cellType: CellType ← ResolveFlatCellType[root, wire.flatCell].cellType;
rootWire: Wire;
IF wire.wireRoot=actual
THEN {
wire.flatCell.path ← ExtendPath[wire.flatCell.path, wire.instanceIndex, NARROW[cellType.data, CoreClasses.RecordCellType]];
wire.flatCell.recastCount ← 0;
};
pathRope ← CellTypePathRope[root, wire.flatCell];
IF (NOT Rope.IsEmpty[pathRope]) AND wire.wireRoot#internal THEN pathRope ← Rope.Cat[pathRope, "."];
pathRope ← Rope.Cat[pathRope, SELECT wire.wireRoot FROM internal => NIL, public => "public", actual => "actual", ENDCASE => ERROR];
rootWire ←
SELECT wire.wireRoot
FROM
public => cellType.public,
internal => NARROW [cellType.data, CoreClasses.RecordCellType].internal,
actual => NARROW [cellType.data, CoreClasses.RecordCellType][wire.instanceIndex].type.public,
ENDCASE => ERROR;
IF wire.validPath
THEN {
visitWire: Wire ← rootWire;
begin: NAT ← 0;
index: NAT;
name: ROPE;
UNTIL begin=wire.path.length
DO
pathBits: NAT ← BitOps.NBits[visitWire.size];
instanceBits: PACKED ARRAY [0..16) OF BOOL ← ALL [FALSE];
FOR bit:
NAT
IN [0..pathBits)
DO
instanceBits[16-pathBits+bit] ← wire.path.bits[begin+bit];
ENDLOOP;
begin ← begin + pathBits;
index ← LOOPHOLE[instanceBits];
visitWire ← visitWire[index];
name ← CoreOps.GetShortWireName[visitWire];
IF name=NIL THEN name ← Convert.RopeFromInt[index];
IF NOT Rope.IsEmpty[pathRope] THEN pathRope ← Rope.Cat[pathRope, "."];
pathRope ← Rope.Cat[pathRope, name];
ENDLOOP;
}
ELSE {
IF NOT Rope.IsEmpty[pathRope] THEN pathRope ← Rope.Cat[pathRope, "."];
pathRope ← Rope.Cat[pathRope, CoreOps.GetFullWireName[rootWire, wire.wire]];
};
};
FlatWireEqual:
PUBLIC
PROC [key1, key2:
REF
ANY]
RETURNS [equal:
BOOL] = {
equal ← FlatWireEqualRec[NARROW [key1, FlatWire]^, NARROW [key2, FlatWire]^];
};
FlatWireEqualRec:
PUBLIC
PROC [one, other: FlatWireRec]
RETURNS [equal:
BOOL] = {
equal ← one.wire=other.wire AND FlatCellTypeEqualRec[one.flatCell, other.flatCell];
};
FlatWireHash:
PUBLIC
PROC [wire:
REF
ANY]
RETURNS [hash:
CARDINAL] = {
hash ← FlatWireHashRec[NARROW [wire, FlatWire]^];
};
FlatWireHashRec:
PUBLIC
PROC [wire: FlatWireRec]
RETURNS [hash:
CARDINAL] = {
hash ← FlatCellTypeHashRec[wire.flatCell];
hash ← Basics.BITXOR[hash, Basics.LowHalf[LOOPHOLE[wire.wire]]];
hash ← Basics.BITXOR[hash, Basics.HighHalf[LOOPHOLE[wire.wire]]];
};
CanonizeWire: PUBLIC PROC [root: CellType, child: FlatWireRec] RETURNS [parent: FlatWireRec] = { -- this is the old version. Kept if a problem arises with the new (faster) one
Search: BoundFlatCellProc = {
upBindings ← bindings;
NextBoundCellType[cell, target, flatCell, instance, index, parent, flatParent, data, bindings, Search]
};
upBindings: Bindings ← NIL;
parentRef: FlatWire ← NIL;
Search[cell: root, target: child.flatCell, bindings: InitialBindingTable[root]];
parentRef ← NARROW[RefTab.Fetch[upBindings, child.wire].val];
parent ← IF parentRef=NIL THEN child ELSE parentRef^;
};
CanonizeWire:
PUBLIC
PROC [root: CellType, child: FlatWireRec]
RETURNS [parent: FlatWireRec] = {
WindUp: UnboundFlatCellProc = {
On return of recursion, transport wire across boundaries. Stop all recursion when unable to proceed (avoids scanning the publics of cells above the canonical wire origin).
new: Wire; -- will contain recomputed value if possible
previousCells ← CONS [cell, previousCells]; -- save for recast wind up
previousInstances ← CONS [instance, previousInstances]; -- save for recast wind up
NextUnboundCellType[cell, target, flatCell, instance, index, parent, flatParent, NIL, WindUp];
previousCells ← previousCells.rest; -- restore to entry state
previousInstances ← previousInstances.rest; -- restore to entry state
IF stop OR previousCells=NIL THEN RETURN; -- at top level...
IF instance=previousInstances.first AND cell=previousCells.first THEN RETURN; -- In-place reacst
new ← CoreOps.CorrespondingActual[actual: IF instance=NIL OR instance.type#cell THEN previousCells.first.public ELSE instance.actual, public: cell.public, subPublic: canonized.wire]; -- recast or RCT
IF new=NIL THEN stop ← TRUE -- can't proceed any further
ELSE canonized ← [flatCell: flatParent, wireRoot: internal, wire: new];
};
canonized: FlatWireRec ← child; -- will be backtracked in place
previousCells: LIST OF CellType ← NIL; -- to keep track of recasts
previousInstances: LIST OF CellInstance ← NIL; -- to keep track of recasts
stop: BOOL ← FALSE;
WindUp[cell: root, target: child.flatCell];
IF CoreOps.RecursiveMember[root.public, canonized.wire] THEN canonized.wireRoot ← public; -- final upgrade: we went up to the last recursion stage succesfully
RETURN [parent: canonized]; -- too bad we must rename the result...
};
RaiseRootOfFlatWire:
PUBLIC
PROC [by: InstancePath, flatWire: FlatWireRec]
RETURNS [raised: FlatWireRec] ~ {
raised ← flatWire;
raised.flatCell ← RaiseRootOfFlatCell[by, raised.flatCell];
RETURN};
Enumeration
NextUnboundCellType:
PUBLIC
PROC [cell: CellType, target: FlatCellTypeRec, flatCell: FlatCellTypeRec, instance: CellInstance, index:
NAT, parent: CellType, flatParent: FlatCellTypeRec, data:
REF
ANY, proc: UnboundFlatCellProc] = {
IF FlatCellTypeEqualRec[target, flatCell] THEN RETURN;
IF cell.class=CoreClasses.recordCellClass
THEN {
rct: CoreClasses.RecordCellType ← NARROW[cell.data];
pathBits: NAT ← BitOps.NBits[rct.size];
childFlatCell: FlatCellTypeRec ← [flatCell.path, 0];
instance: CellInstance;
IF FlatCellTypeEqualRec[target, allFlatCells]
THEN {
FOR inst:
NAT
IN [0..rct.size)
DO
instance ← rct[inst];
childFlatCell.path ← ExtendPath[flatCell.path, inst, rct];
proc[cell: instance.type, target: target, flatCell: childFlatCell, instance: instance, index: inst, parent: cell, flatParent: flatCell, data: data];
ENDLOOP;
}
ELSE {
instanceBits: PACKED ARRAY [0..16) OF BOOL ← ALL [FALSE];
IF target.path.length<=flatCell.path.length THEN ERROR; -- illegal move
FOR bit:
NAT
IN [0..pathBits)
DO
instanceBits[16-pathBits+bit] ← target.path.bits[flatCell.path.length+bit];
childFlatCell.path.bits[flatCell.path.length+bit] ← target.path.bits[flatCell.path.length+bit];
ENDLOOP;
index ← LOOPHOLE[instanceBits];
instance ← rct[index];
childFlatCell.path.length ← childFlatCell.path.length + pathBits;
proc[cell: instance.type, target: target, flatCell: childFlatCell, instance: instance, index: index, parent: cell, flatParent: flatCell, data: data];
}
}
ELSE {
new: CellType ← NIL;
IF cell.class.recast=NIL THEN ERROR; -- illegal move
new ← CoreOps.Recast[cell];
IF new#cell THEN flatCell.recastCount ← flatCell.recastCount + 1;
proc[cell: new, target: target, flatCell: flatCell, instance: instance, index: index, parent: parent, flatParent: flatParent, data: data];
};
};
NextBoundCellType:
PUBLIC
PROC [cell: CellType, target: FlatCellTypeRec, flatCell: FlatCellTypeRec, instance: CellInstance, index:
NAT, parent: CellType, flatParent: FlatCellTypeRec, data:
REF
ANY, bindings: Bindings, proc: BoundFlatCellProc] = {
BindCellType: UnboundFlatCellProc = {
newBindings: Bindings ← IF instance=previousInstance AND cell=previousCell THEN bindings ELSE BindInstance[parent: flatParent, actual: IF instance=NIL OR instance.type#cell THEN previousCell.public ELSE instance.actual, public: cell.public, bindings: bindings];
proc[cell, target, flatCell, instance, index, parent, flatParent, data, newBindings];
};
previousCell: CellType ← cell;
previousInstance: CellInstance ← instance;
NextUnboundCellType[cell, target, flatCell, instance, index, parent, flatParent, data, BindCellType];
};
InitialBindingTable:
PUBLIC
PROC [root: CellType]
RETURNS [bindings: Bindings] = {
Bind: CoreOps.EachWireProc = {
IF subWires ← (
NOT RefTab.Fetch[bindings, wire].found)
THEN {
fw: FlatWire = NEW [FlatWireRec ← [wireRoot: public, wire: wire]];
IF NOT RefTab.Insert[bindings, wire, fw] THEN ERROR;
};
};
bindings ← RefTab.Create[];
IF CoreOps.VisitWireSeq[root.public, Bind] THEN ERROR;
bindings ← bindings;
};
Utilities
ParsePartialCellTypePath:
PROC [root: CellType, pathRope:
ROPE, cutSet: CutSet]
RETURNS [flatCell: FlatCellTypeRec, instance: CellInstance ←
NIL, within: CellType, token:
ROPE, ts:
IO.
STREAM, firstChar:
CHAR, tokenKind:
IO.TokenKind, thisCell: CellType ←
NIL] = {
RecastToClass:
PROC = {
DO
IF
NOT first
THEN {
new: CellType ← NIL;
CheckRecast[flatCell, instance, thisCell, cutSet];
new ← CoreOps.Recast[thisCell];
IF new#thisCell THEN flatCell.recastCount ← flatCell.recastCount + 1;
thisCell ← new;
};
first ← FALSE;
IF Rope.Equal[token, thisCell.class.name] THEN EXIT;
ENDLOOP;
state ← sawCellClassNameOrRecastNumber;
};
RecastByNumber:
PROC = {
recastNumber: CARDINAL ← Convert.CardFromRope[token];
FOR rn:
CARDINAL
IN [0..recastNumber)
DO
new: CellType ← NIL;
CheckRecast[flatCell, instance, thisCell, cutSet];
new ← CoreOps.Recast[thisCell];
IF new#thisCell THEN flatCell.recastCount ← flatCell.recastCount + 1;
thisCell ← new;
ENDLOOP;
state ← sawRecastNumber;
};
CheckCellClassName:
PROC = {
IF NOT Rope.Equal[token, thisCell.class.name] THEN MakeError[Rope.Cat["Incorrect cell class name ", token]];
state ← sawCellClassName;
};
CellTypePath ::= {start} * {sawAsterisk} ( Name | (Number {sawRecastNumber} ?( ( {sawLeftParan} Name {sawCellClassName} ) ) ) {sawCellClassNameOrRecastNumber} )
CellTypePathParseStates: TYPE = {start, sawAsterisk, sawRecastNumber, sawLeftParan, sawCellClassName, sawCellClassNameOrRecastNumber};
state: CellTypePathParseStates ← start;
first: BOOL ← TRUE;
[flatCell.path, instance, within, token, ts, firstChar, tokenKind] ← ParsePartialInstancePath[root, pathRope, cutSet];
thisCell ← IF instance=NIL THEN root ELSE instance.type;
flatCell.recastCount ← 0;
IF tokenKind#tokenEOF
THEN
DO
SELECT state
FROM
start =>
SELECT tokenKind
FROM
tokenSINGLE =>
SELECT firstChar
FROM
'* => state ← sawAsterisk;
'., '[, '{ => EXIT;
ENDCASE => MakeError[];
tokenID => EXIT;
tokenDECIMAL => EXIT;
ENDCASE => MakeError[];
sawAsterisk =>
SELECT tokenKind
FROM
tokenID => RecastToClass[];
tokenDECIMAL => RecastByNumber[];
ENDCASE => MakeError[];
sawRecastNumber =>
SELECT tokenKind
FROM
tokenSINGLE =>
SELECT firstChar
FROM
'( => state ← sawLeftParan;
'* => state ← sawAsterisk;
'., '[, '{ => EXIT;
ENDCASE => MakeError[];
ENDCASE => MakeError[];
sawLeftParan =>
SELECT tokenKind
FROM
tokenID => CheckCellClassName[];
ENDCASE => MakeError[];
sawCellClassName =>
SELECT tokenKind
FROM
tokenSINGLE =>
SELECT firstChar
FROM
') => state ← sawCellClassNameOrRecastNumber;
ENDCASE => MakeError[];
ENDCASE => MakeError[];
sawCellClassNameOrRecastNumber =>
SELECT tokenKind
FROM
tokenSINGLE =>
SELECT firstChar
FROM
'* => state ← sawAsterisk;
'., '[, '{ => EXIT;
ENDCASE => MakeError[];
ENDCASE => MakeError[];
ENDCASE => MakeError[];
[token, firstChar, tokenKind] ← ParseToken[ts ! IO.EndOfStream => {tokenKind ← tokenEOF; EXIT}];
ENDLOOP;
IF state=sawAsterisk OR state=sawLeftParan OR state=sawCellClassName THEN MakeError[];
};
ParsePartialInstancePath:
PROC [root: CellType, pathRope:
ROPE, cutSet: CutSet]
RETURNS [path: InstancePath ← nullInstancePath, instance: CellInstance ←
NIL, within: CellType, token:
ROPE, ts:
IO.
STREAM, firstChar:
CHAR, tokenKind:
IO.TokenKind] = {
AppendNameInstance:
PROC = {
found: BOOL ← FALSE;
rct: CoreClasses.RecordCellType;
path ← AddInstance[path, instance, within];
within ← IF instance=NIL THEN root ELSE instance.type;
rct ← MakeRecord[within, instance, [path, 0], cutSet].rct;
FOR inst:
CARDINAL
IN [0..rct.size)
DO
IF Rope.Equal[token, CoreClasses.GetCellInstanceName[rct[inst]]]
THEN {
instance ← rct[inst];
found ← TRUE;
EXIT;
};
REPEAT
FINISHED =>
FOR inst:
CARDINAL
IN [0..rct.size)
DO
IF Rope.Equal[token, CoreOps.GetCellTypeName[rct[inst].type]]
THEN {
IF found THEN MakeError["Append by cell type name is ambiguous"];
instance ← rct[inst];
found ← TRUE;
};
ENDLOOP;
ENDLOOP;
IF NOT found THEN MakeError[Rope.Cat["Can't find instance or cell type of name ", token]];
state ← sawInstanceNameOrNumber;
};
AppendNumberInstance:
PROC = {
rct: CoreClasses.RecordCellType;
inst: CARDINAL ← Convert.CardFromRope[token];
path ← AddInstance[path, instance, within];
within ← IF instance=NIL THEN root ELSE instance.type;
rct ← MakeRecord[within, instance, [path, 0], cutSet].rct;
IF inst>=rct.size THEN MakeError[Rope.Cat["No such instance ", token]];
instance ← rct[inst];
state ← sawInstanceNumber;
};
CheckCellTypeName:
PROC = {
IF NOT Rope.Equal[token, CoreOps.InheritCellTypeName[instance.type]] THEN MakeError[Rope.Cat["Incorrect cell type name ", token]];
state ← sawCellTypeName;
};
InstancePath ::= {start} / {expectInstanceNameOrNumber} ( Name | (Number {sawInstanceNumber} ?( ( {sawLeftParan} Name {sawCellTypeName} ) ) ) {sawInstanceNameOrNumber} )
InstancePathParseStates: TYPE = {start, expectInstanceNameOrNumber, sawInstanceNumber, sawLeftParan, sawCellTypeName, sawInstanceNameOrNumber};
state: InstancePathParseStates ← start;
within ← root;
ts ← IO.RIS[pathRope];
DO
[token, firstChar, tokenKind] ← ParseToken[ts ! IO.EndOfStream => {tokenKind ← tokenEOF; EXIT}];
SELECT state
FROM
start =>
SELECT tokenKind
FROM
tokenSINGLE =>
SELECT firstChar
FROM
'/ => state ← expectInstanceNameOrNumber;
'*, '[, '{ => EXIT;
ENDCASE => MakeError[];
tokenID => EXIT;
tokenDECIMAL => EXIT;
ENDCASE => MakeError[];
expectInstanceNameOrNumber =>
SELECT tokenKind
FROM
tokenID => AppendNameInstance[];
tokenDECIMAL => AppendNumberInstance[];
ENDCASE => MakeError[];
sawInstanceNumber =>
SELECT tokenKind
FROM
tokenSINGLE =>
SELECT firstChar
FROM
'( => state ← sawLeftParan;
'/ => state ← expectInstanceNameOrNumber;
'*, '., '[, '{ => EXIT;
ENDCASE => MakeError[];
ENDCASE => MakeError[];
sawLeftParan =>
SELECT tokenKind
FROM
tokenID => CheckCellTypeName[];
ENDCASE => MakeError[];
sawCellTypeName =>
SELECT tokenKind
FROM
tokenSINGLE =>
SELECT firstChar
FROM
') => state ← sawInstanceNameOrNumber;
ENDCASE => MakeError[];
ENDCASE => MakeError[];
sawInstanceNameOrNumber =>
SELECT tokenKind
FROM
tokenSINGLE =>
SELECT firstChar
FROM
'/ => state ← expectInstanceNameOrNumber;
'*, '., '[, '{ => EXIT;
ENDCASE => MakeError[];
ENDCASE => MakeError[];
ENDCASE => MakeError[];
ENDLOOP;
IF state=expectInstanceNameOrNumber OR state=sawLeftParan OR state=sawCellTypeName THEN MakeError[];
};
MakeRecord:
PROC [cellType: CellType, instance: CellInstance, flatCell: FlatCellTypeRec, cutSet: CutSet]
RETURNS [rct: CoreClasses.RecordCellType, newFlatCell: FlatCellTypeRec] = {
UNTIL cellType.class=CoreClasses.recordCellClass
DO
new: CellType ← NIL;
CheckRecast[flatCell, instance, cellType, cutSet];
new ← CoreOps.Recast[cellType];
IF new#cellType THEN flatCell.recastCount ← flatCell.recastCount + 1;
cellType ← new;
ENDLOOP;
rct ← NARROW [cellType.data];
newFlatCell ← flatCell
};
CheckRecast:
PROC [flatCell: FlatCellTypeRec, instance: CellInstance, cellType: CellType, cutSet: CutSet] = {
IF cellType.class.recast=NIL THEN MakeError["Attempting to name something inside of a primitive element"];
IF CutSetMemberResolved[flatCell, instance, cellType, cutSet] THEN MakeError["Attempting to name something below the current cutSet"];
};
CheckNoMore:
PROC [ts:
IO.
STREAM, firstChar:
CHAR, tokenKind:
IO.TokenKind] = {
token: ROPE;
IF tokenKind=tokenSINGLE AND firstChar='. THEN [token, firstChar, tokenKind] ← ParseToken[ts ! IO.EndOfStream => {tokenKind ← tokenEOF; CONTINUE}];
IF tokenKind#tokenEOF THEN MakeError[];
};
ParseToken:
PROC [ts:
IO.
STREAM]
RETURNS [token:
ROPE, firstChar:
CHAR, tokenKind:
IO.TokenKind] = {
token ← IO.GetTokenRope[ts, Breaks].token;
firstChar ← Rope.Fetch[token];
tokenKind ←
SELECT
TRUE
FROM
Rope.Length[token]=1 AND Breaks[firstChar]=break => tokenSINGLE,
firstChar IN ['0..'9] => tokenDECIMAL,
ENDCASE => tokenID;
};
Breaks:
IO.BreakProc = {
RETURN[
SELECT char
FROM
IN [IO.NUL .. IO.SP] => sepr,
'{, '}, '/, '., '(, '), '[, '], '* => break,
IN ['0..'9], IN ['a..'z], IN ['A..'Z] => other,
ENDCASE => ERROR PathError["Illegal character"]];
};