StructureFromCoreImpl:
CEDAR
PROGRAM
IMPORTS Asserting, Atom, Convert, CoreClasses, CoreFlat, CoreOps, CoreProperties, CoreStructuralComparison, HashTable, IO, Rope, RopeHash, StructuralComparisonDataStructure, StructuralComparisonOps
EXPORTS StructureFromCore
SHARES StructuralComparisonDataStructure =
BEGIN OPEN CC: CoreClasses, CF: CoreFlat, CO: CoreOps, CP: CoreProperties, StructuralComparisonOps, CoreStructuralComparison, StructuralComparisonDataStructure;
ATOMList: TYPE = LIST OF ATOM;
implKey: ATOM = $StructureFromCoreImplInstance;
implVal: REF ROPE ← NEW [ROPE ← "New for this one"];
ColorerKey: ATOM = $CoreStructureColorer;
Colorer: TYPE = REF ColorerPrivate;
ColorerPrivate:
TYPE =
RECORD [
CellTypeColor: PROC [ct: Core.CellType] RETURNS [Color],
ColorPorts:
PROC [ct: Core.CellType,
SetColor:
PROC [Core.Wire, Color]]
Must set the color of each atom of the public wire.
];
wireColorKey:
ATOM =
CP.RegisterProperty[
$LichenStructureFromCoreImplWireColor,
CP.Props[[CP.propPrint, CP.PropDontPrint]]];
ttolProps:
ARRAY TransistorDim
OF
ATOM ~ [
length:
CP.RegisterProperty[
$LichenLengthTolerance,
CP.Props[[CP.propPrint, CP.PropDontPrint]]],
width:
CP.RegisterProperty[
$LichenWidthTolerance,
CP.Props[[CP.propPrint, CP.PropDontPrint]]]
];
structureFromCorePrefix: ROPE = "StructureFromCore by SubtreeSpec ";
structureFromCorePrefixLength: INT = structureFromCorePrefix.Length[];
structureFromCoreFormat: ROPE = structureFromCorePrefix.Concat["%g(%g) and MergeSpec %g(%g)"];
SpecAndKeyList: TYPE = LIST OF SpecAndKey;
SpecAndKey: TYPE = RECORD [sts: SubtreeSpec, ms: MergeSpec, key: ATOM];
stsToKey: SpecAndKeyList ← NIL;
backHashKey: ATOM = $StructureFromCoreImplCellTypeToBackpointerHashtable;
structureToCore: ATOM = $StructureToCore;
GetKeyForSpecs:
PROC [sts: SubtreeSpec, ms: MergeSpec]
RETURNS [key:
ATOM] = {
FOR stks: SpecAndKeyList ← stsToKey, stks.rest
WHILE stks #
NIL
DO
IF stks.first.sts = sts AND stks.first.ms = ms THEN RETURN [stks.first.key];
ENDLOOP;
key ←
CP.RegisterProperty[
Atom.MakeAtom[
IO.PutFR[
structureFromCoreFormat,
[cardinal[LOOPHOLE[sts, CARDINAL]]],
[refAny[NEW [SubtreeSpec ← sts]]],
[cardinal[LOOPHOLE[ms, CARDINAL]]],
[refAny[NEW [MergeSpec ← ms]]]
]],
CP.Props[[CP.propPrint, CP.PropDontPrint]]];
stsToKey ← CONS[[sts, ms, key], stsToKey];
};
GetGraph:
PUBLIC
PROC [ttols: TransistorTolerances ←
NIL, cct: Core.CellType, internals:
BOOL, sts: SubtreeSpec, ms: MergeSpec,
SurveyPart:
PROC [v: Vertex, core:
REF
ANY
--UNION [Wire, CellInstance]--] ←
NIL]
RETURNS [sct: CellType] = {
original: Core.CellType = cct;
raw: REF ANY;
colorer: Colorer =
WITH
CP.InheritCellTypeProp[cct, ColorerKey]
SELECT
FROM
x: Colorer => x,
ENDCASE => defaultColorer;
backHash: HashTable.Table;
structureFromCoreCellType: ATOM = GetKeyForSpecs[sts, ms];
ttolsCopied: BOOL ← FALSE;
IF NOT (internals OR ms=MergeNothing) THEN ERROR--Not implemented because not needed, right?--;
IF ttols = NIL THEN ttols ← defaultTransistorTolerances;
FOR td: TransistorDim
IN TransistorDim
DO
WITH
CP.InheritCellTypeProp[cct, ttolProps[td]]
SELECT
FROM
x:
ROPE => {
y: REAL ~ Convert.RealFromRope[x];
IF
NOT ttolsCopied
THEN {
ttolsCopied ← TRUE;
ttols ← NEW [TransistorTolerancesPrivate ← ttols^]};
ttols[td] ←
SELECT y
FROM
>= 1.0 => [1.0/y, y],
<= 0.0 => ERROR,
ENDCASE => [y, 1.0/y];
};
ENDCASE => NULL;
ENDLOOP;
sct ← NIL;
DO
raw ← CP.GetCellTypeProp[cct, structureFromCoreCellType];
IF raw #
NIL
THEN
WITH raw
SELECT
FROM
x: CellType => sct ← IF Asserting.FnVal[implKey, x.otherPublic] = implVal THEN x ELSE NIL;
ENDCASE => sct ← NIL;
IF sct # NIL THEN EXIT;
IF cct.class.recast = NIL THEN EXIT;
IF TRUE THEN EXIT--because backHash (& other, less obvious, things) references original, it won't do to inherit the graph of a Recast--;
cct ← CO.Recast[cct];
ENDLOOP;
IF sct =
NIL
THEN {
sct ←
NEW [CellTypeRep ← [
name: GetCellTypeName[original],
color: FilterColor[colorer.CellTypeColor[original]],
ports: NEW [PortSeq[CO.WireBits[original.public]]],
otherPublic: Asserting.AssertFn1[structureToCore, original, Asserting.AssertFn1[implKey, implVal, Asserting.AssertFn1[transistorTolerancesKey, ttols, NIL]]]
]];
sct.ports.length ← 0;
CP.PutCellTypeProp[original, structureFromCoreCellType, sct];
colorer.ColorPorts[original, SetWireColor];
IF
NOT internals
THEN {
seen: HashTable.Table = HashTable.Create[];
pi: PortIndex ← 0;
DefinePorts:
PROC [wire: Core.Wire] = {
IF
NOT seen.Fetch[wire].found
THEN {
name: ROPE = UnionNames[CO.GetFullWireNames[original.public, wire]];
sct.ports[pi] ← [
name: name,
color: GetWireColor[wire]
];
IF NOT seen.Insert[wire, $T] THEN ERROR;
pi ← pi + 1;
};
};
CO.VisitRootAtomics[original.public, DefinePorts];
IF pi # sct.ports.size THEN ERROR;
sct.ports.length ← pi;
};
}
ELSE IF GetCellType[sct] # original THEN ERROR;
IF sct.internalsKnown OR NOT internals THEN RETURN;
sct.internalsKnown ← TRUE;
{ENABLE UNWIND => ForgetGraph[sct];
backHash ← HashTable.Create[hash: HashDescendant, equal: DescendantEqual];
sct.otherPrivate ← Asserting.AssertFn1[backHashKey, backHash, sct.otherPrivate];
{
Prefix:
PROC [path:
CF.InstancePath]
RETURNS [prefix:
ROPE] = {
IF path.length=0 THEN RETURN [NIL];
prefix ← CF.InstancePathRope[original, path].Concat["/"];
};
IntroduceWires:
PROC [flatCell:
CF.FlatCellTypeRec, wireRoot:
CF.WireRoot, root: Core.Wire, bindings:
CF.Bindings] = {
DefineInternal:
PROC [wire: Core.Wire] = {
IF bindings =
NIL
OR
NOT bindings.Fetch[wire].found
THEN {
dw: CF.FlatWire = NEW [CF.FlatWireRec ← [flatCell: flatCell, wireRoot: wireRoot, wire: wire]];
IF
NOT backHash.Fetch[dw].found
THEN {
name: ROPE ~ CF.WirePathRope[root: original, wire: dw^];
name: ROPE = Prefix[flatCell.path].Concat[UnionNames[CO.GetFullWireNames[root, wire]]];
v: Vertex =
NEW [VertexRep ← [
name: name,
class: net,
other: Asserting.AssertFn1[structureToCore, dw, NIL]
]];
IF NOT backHash.Insert[dw, v] THEN ERROR;
AddPart[sct, v];
IF SurveyPart # NIL THEN SurveyPart[v, wire];
};
};
};
CO.VisitRootAtomics[root, DefineInternal];
};
Flatten:
PROC [cell: Core.CellType, target:
CF.FlatCellTypeRec ←
CF.allFlatCells, flatCell:
CF.FlatCellTypeRec ← [], instance:
CF.CellInstance ←
NIL, index:
NAT ←
LAST[
NAT], parent: Core.CellType ←
NIL, flatParent:
CF.FlatCellTypeRec ← [], data:
REF
ANY ←
NIL, bindings:
CF.Bindings ←
NIL]
--CF.BoundFlatCellProc-- = {
path: DescendantCellInstancePrivate = flatCell.path;
childCCT: Core.CellType = IF path.length > 0 THEN sts[instance, path] ELSE NIL;
flatten: BOOL = childCCT = NIL;
IF flatten
THEN {
IF cell.class=
CC.recordCellClass
THEN {
rct: CC.RecordCellType = NARROW[cell.data];
IntroduceWires[flatCell, internal, rct.internal, bindings];
};
CF.NextBoundCellType[cell, target, flatCell, instance, index, parent, flatParent, data, bindings, Flatten];
IF cell.class=
CC.recordCellClass
THEN {
rct: CC.RecordCellType = NARROW[cell.data];
EnumerateInstances:
PROC [
Consume:
PROC [ci:
CC.CellInstance]
RETURNS [stop:
BOOL ←
FALSE]] = {
FOR i:
NAT
IN [0 .. rct.size)
DO
IF Consume[rct[i]] THEN EXIT;
ENDLOOP;
};
IdentifyActual:
PROC [ci: CoreClasses.CellInstance, actual: Core.Wire, describe:
BOOL ←
FALSE]
RETURNS [ActualID] = {
dw: DescendantWire ~ NARROW[bindings.Fetch[actual].value];
IF dw # NIL THEN RETURN [[dw, IF describe THEN CF.WirePathRope[original, dw^] ELSE NIL]];
RETURN [[actual, IF describe THEN CF.WirePathRope[original, [flatCell: flatCell, wire: actual]] ELSE NIL]];
};
ConsumeMerge:
PROC [ds: Element] = {
v: Vertex ← CanonizeAndGetStructure[sct, ds.first];
FOR ds ← ds.rest, ds.rest
WHILE ds #
NIL
DO
w: Vertex ← CanonizeAndGetStructure[sct, ds.first];
v ← MergeVertices[sct, v, w].merged;
ENDLOOP;
};
ms[original, cell, path, EnumerateInstances, IdentifyActual, ConsumeMerge];
}
}
ELSE {
ci: CC.CellInstance = instance;
di: DescendantCellInstance = NEW [DescendantCellInstancePrivate ← path];
name: ROPE = Prefix[path].Concat[CC.GetCellInstanceName[ci]];
type: CellType = GetGraph[ttols, childCCT, FALSE, sts, MergeNothing, NIL];
v: Vertex =
NEW [VertexRep ← [
name: name,
class: cell,
type: type,
other: Asserting.AssertFn1[structureToCore, di, NIL]
]];
pi: PortIndex ← 0;
seen: HashTable.Table = HashTable.Create[];
SeeBinding:
PROC [actualWire, publicWire: Core.Wire]
RETURNS [subWires:
BOOL ←
TRUE, quit:
BOOL ←
FALSE]
--CO.EachWirePairProc-- = {
pw: Core.Wire = publicWire;
IF pw.size = 0
AND pw # ci.type.public
AND
NOT seen.Fetch[pw].found
THEN {
adw: DescendantWire = NARROW[bindings.Fetch[publicWire].value];
IF adw = NIL THEN ERROR;
{nv: Vertex = GetStructure[sct, adw];
IF nv = NIL THEN ERROR;
Link[v, nv, type.ports[pi].color];
IF NOT seen.Insert[pw, $T] THEN ERROR;
pi ← pi + 1;
}};
};
IF NOT backHash.Insert[di, v] THEN ERROR;
AddPart[sct, v];
[] ← CO.VisitBinding[ci.actual, ci.type.public, SeeBinding];
IF pi # type.ports.length THEN ERROR;
IF SurveyPart # NIL THEN SurveyPart[v, ci];
};
};
IntroduceWires[[], public, original.public, NIL];
Flatten[original, CF.allFlatCells, [], NIL, LAST[NAT], NIL, [], NIL, HashTable.Create[]];
};
IF sct.ports.length # 0 THEN ERROR;
{pi: PortIndex ← 0;
seen: HashTable.Table = HashTable.Create[];
SetPortNet:
PROC [wire: Core.Wire] = {
IF
NOT seen.Fetch[wire].found
THEN {
dw: DescendantWire = NEW [DescendantWirePrivate ← [wireRoot: public, wire: wire]];
nv: Vertex = GetStructure[sct, dw];
IF nv = NIL THEN ERROR;
IF
NOT seen.Fetch[nv].found
THEN {
first: BOOL ← TRUE;
color: Color ← 0;
FOR ds: Element ← GetCore[nv], ds.rest
WHILE ds #
NIL
DO
dw: DescendantWire = NARROW[ds.first];
IF dw.path.length # 0 THEN ERROR;
IF first THEN first ← FALSE;
color ← color + GetWireColor[dw.wire];
ENDLOOP;
IF first THEN ERROR;
sct.ports[pi] ← [
name: nv.name,
net: nv,
color: FilterColor[color]
];
IF NOT seen.Insert[nv, $T] THEN ERROR;
pi ← pi + 1;
};
};
};
[] ← CO.VisitRootAtomics[original.public, SetPortNet];
sct.ports.length ← pi;
};
AddMirror[sct];
};
sct ← sct;
};
ForgetGraph:
PUBLIC
PROC [sct: CellType] = {
cct: Core.CellType = GetCellType[sct];
propsToRemove: ATOMList ← NIL;
FindPropsToRemove:
PROC [prop:
ATOM, val:
REF
ANY ←
NIL] = {
IF structureFromCorePrefix.Equal[Atom.GetPName[prop].Substr[len: structureFromCorePrefixLength]] THEN propsToRemove ← CONS[prop, propsToRemove];
};
EnumerateParts[sct, DestroyVertex, TRUE];
sct^ ← CellTypeRep[destroyed: TRUE];
CP.Enumerate[cct.properties, FindPropsToRemove];
FOR propsToRemove ← propsToRemove, propsToRemove.rest
WHILE propsToRemove #
NIL
DO
CP.PutCellTypeProp[cct, propsToRemove.first, NIL];
ENDLOOP;
};
AddPart:
PROC [sct: CellType, v: Vertex] = {
v.nextPart ← sct.firstPart;
sct.firstPart ← v;
sct.size ← sct.size + 1;
SELECT v.class
FROM
cell => sct.cellCount ← sct.cellCount + 1;
net => sct.netCount ← sct.netCount + 1;
ENDCASE => ERROR;
};
Link:
PROC [cv, nv: Vertex, edgeColor: Color] = {
e: Edge =
NEW [EdgeRep ← [
sides: [
net: [v: nv, next: NIL, prev: nv.lastEdge],
cell: [v: cv, next: NIL, prev: cv.lastEdge]],
color: edgeColor]];
IF nv.lastEdge = NIL THEN nv.firstEdge ← e ELSE nv.lastEdge.sides[net].next ← e;
IF cv.lastEdge = NIL THEN cv.firstEdge ← e ELSE cv.lastEdge.sides[cell].next ← e;
nv.lastEdge ← cv.lastEdge ← e;
};
DestroyVertex:
PROC [v: Vertex] = {
WHILE v.firstEdge #
NIL
DO
e: Edge ← v.firstEdge;
v.firstEdge ← e.sides[v.class].next;
e.sides[v.class] ← [NIL, NIL, NIL];
ENDLOOP;
v^ ← [class: v.class];
};
AddMirror:
PROC [sct: CellType] = {
v: Vertex =
NEW [VertexRep ← [
name: " The Outside World! ",
class: cell,
type: sct,
isMirror: TRUE
]];
sct.mirror ← v;
FOR pi: PortIndex
IN [0 .. sct.ports.length)
DO
Link[v, sct.ports[pi].net, sct.ports[pi].color];
ENDLOOP;
};
SetWireColor:
PROC [wire: Core.Wire, color: Color] = {
CP.PutWireProp[wire, wireColorKey, NEW [Color ← color]];
};
GetWireColor:
PROC [wire: Core.Wire]
RETURNS [color: Color] = {
rc: REF Color = NARROW[CP.GetWireProp[wire, wireColorKey]];
color ← rc^;
};
GetCellType:
PUBLIC
PROC [sct: CellType]
RETURNS [cct: Core.CellType] = {
cct ← NARROW[Asserting.FnVal[structureToCore, sct.otherPublic]];
};
CanonizeAndGetStructure:
PUBLIC
PROC [sct: CellType, core:
--not necessarily canonical--Descendant]
RETURNS [v: Vertex] = {
backHash: HashTable.Table = NARROW[Asserting.FnVal[backHashKey, sct.otherPrivate]];
cd: --Canonized--Descendant ← core;
WITH core
SELECT
FROM
di: DescendantCellInstance => NULL;
dw: DescendantWire => {
original: Core.CellType = GetCellType[sct];
cd ← NEW [CF.FlatWireRec ← CF.CanonizeWire[original, dw^]];
};
ENDCASE => ERROR;
FOR v ← NARROW[backHash.Fetch[cd].value], v.better UNTIL v.better = NIL DO NULL ENDLOOP;
};
GetStructure:
PUBLIC
PROC [sct: CellType, core:
--Canonized--Descendant]
RETURNS [v: Vertex] = {
backHash: HashTable.Table = NARROW[Asserting.FnVal[backHashKey, sct.otherPrivate]];
FOR v ← NARROW[backHash.Fetch[core].value], v.better UNTIL v.better = NIL DO NULL ENDLOOP;
};
GetCore:
PUBLIC
PROC [v: Vertex]
RETURNS [core: Element] = {
Note:
PROC [assertion: Asserting.Assertion]
--Asserting.AssertionConsumer-- = {
d: Descendant = Asserting.FnVal[structureToCore, LIST[assertion]];
core ← CONS[d, core];
};
core ← NIL;
Asserting.EnumerateAssertionsAbout[structureToCore, v.other, Note];
};
defaultColorer: Colorer ← NEW [ColorerPrivate ← [DefaultCellTypeColor, DefaultColorPorts]];
DefaultCellTypeColor:
PROC [ct: Core.CellType]
RETURNS [color: Color] = {
name: ROPE ← CO.GetCellTypeName[ct];
color ← RopeHash.FromRope[name];
color ← color * color;
};
DefaultColorPorts:
PROC [ct: Core.CellType,
SetColor:
PROC [Core.Wire, Color]] = {
ColorPort:
PROC [wire: Core.Wire] = {
name: ROPE = UnionNames[CO.GetFullWireNames[ct.public, wire]];
SetColor[wire, RopeHash.FromRope[name]];
SetColor[wire, RefHash[wire]];
};
[] ← CO.VisitRootAtomics[ct.public, ColorPort];
};
transistorColorer: Colorer ← NEW [ColorerPrivate ← [TransistorCellTypeColor, ColorTransistorPorts]];
TransistorCellTypeColor:
PROC [ct: Core.CellType]
RETURNS [color: Color] = {
td: CC.Transistor = NARROW[ct.data];
color ←
SELECT td.type
FROM
nE => 36,
pE => 24,
nD => 33,
ENDCASE => ERROR;
};
ColorTransistorPorts:
PROC [ct: Core.CellType,
SetColor:
PROC [Core.Wire, Color]] = {
ColorPort:
PROC [wire: Core.Wire] = {
name: ROPE = CO.GetShortWireName[wire];
SetColor[wire,
SELECT
TRUE
FROM
name.Substr[len: 2].Equal["ch", FALSE] => channelColor,
name.Equal["gate", FALSE] => gateColor,
ENDCASE => ERROR
];
};
[] ← CO.VisitRootAtomics[ct.public, ColorPort];
};
gateColor: Color ← 47;
channelColor: Color ← 834;
UnionNames:
PROC [names:
LIST
OF
ROPE]
RETURNS [unioned:
ROPE] = {
unioned ← NIL;
FOR names ← names, names.rest
WHILE names #
NIL
DO
unioned ← IF unioned=NIL THEN names.first ELSE Rope.Cat[unioned, "|", names.first];
ENDLOOP;
unioned ← unioned;
};
GetCellTypeName:
PROC [cct: Core.CellType]
RETURNS [name:
ROPE] = {
IF (name ← CO.GetCellTypeName[cct]).Length[] # 0 THEN RETURN;
cct ← CO.ToBasic[cct];
IF (name ← CO.GetCellTypeName[cct]).Length[] # 0 THEN RETURN;
WITH cct.data
SELECT
FROM
t:
CC.Transistor => {
name ←
IO.PutFR[
"%g(%g/%g)",
[rope[
SELECT t.type
FROM
nE => "nE",
pE => "pE",
nD => "nD",
ENDCASE => ERROR]],
[integer[t.length]],
[integer[t.width]]];
[] ← CO.SetCellTypeName[cct, name];
};
ENDCASE => name ← IO.PutFR["%xB^", [cardinal[LOOPHOLE[cct]]]];
};
Start:
PROC = {
CP.PutCellClassProp[CC.transistorCellClass, ColorerKey, transistorColorer];
};
Start[];
END.