PUBLIC
PROC [
roleNames: ARRAY Role OF ROPE,
cts: CellTypePair,
stss: ARRAY Role OF SubtreeSpec ← ALL[ToLeaves],
mss: ARRAY Role OF MergeSpec ← ALL[MergeNothing],
GiveHints: HintsGiver ← NIL,
PerPair: AssociationPairConsumer ← NIL,
PerMismatch: MismatchConsumer ← NIL,
Querier: AssociationQuerier ← NIL,
automorphismHack, mayQuitEarly: BOOL ← FALSE,
didQuitEarly, abort: REF BOOL
]
RETURNS [isomorphic: BOOL]
= {
realDescrs: RealGraphDescriptions ~ [A: roleNames[A], B: roleNames[B]];
needsFrom:
ARRAY Role
OF HashTable.Table ~ [
A: HashTable.Create[equal: HashTable.RopeEqual, hash: HashTable.HashRope],
B: HashTable.Create[equal: HashTable.RopeEqual, hash: HashTable.HashRope]];
SurveyA:
PROC [v: Vertex, core:
REF
ANY
--UNION [Wire, CellInstance]--] = {
matchName:
ROPE =
NARROW[
WITH core
SELECT
FROM
w: Core.Wire => CP.GetWireProp[w, matchProp],
ci: CC.CellInstance => CP.GetCellInstanceProp[ci, matchProp],
ENDCASE => ERROR];
IF matchName #
NIL
THEN {
need: Need = NEW [NeedPrivate ← [matchName, v, NIL]];
IF NOT needsFrom[A].Insert[matchName, need] THEN ERROR;
};
};
SurveyB:
PROC [v: Vertex, core:
REF
ANY
--UNION [Wire, CellInstance]--] = {
name, matchName: ROPE;
IF v = NIL OR core = NIL THEN ERROR;
WITH core
SELECT
FROM
w: Core.Wire => {name ← CO.GetShortWireName[w]; matchName ← NARROW[CP.GetWireProp[w, matchProp]]};
ci: CC.CellInstance => {name ← CC.GetCellInstanceName[ci]; matchName ← NARROW[CP.GetCellInstanceProp[ci, matchProp]]};
ENDCASE => ERROR;
{match: Need = NARROW[needsFrom[A].Fetch[name].value];
IF matchName #
NIL
THEN {
need: Need = NEW [NeedPrivate ← [matchName, v, NIL]];
IF NOT needsFrom[B].Insert[matchName, need] THEN ERROR;
};
IF match #
NIL
THEN {
IF match.to # NIL THEN ERROR;
match.to ← v};
}};
sctA: CellType = GetGraph[NIL, cts[A], TRUE, stss[A], mss[A], SurveyA];
IF abort^ THEN RETURN [FALSE];
{sctB: CellType = GetGraph[NIL, cts[B], TRUE, stss[B], mss[B], SurveyB];
IF abort^ THEN RETURN [FALSE];
{ccts: ARRAY RealGraphID OF Core.CellType = [A: cts[A], B: cts[B]];
scts: ARRAY RealGraphID OF CellType = [A: sctA, B: sctB];
GenerateHints:
PROC [
Consume:
PROC [vA, vB: Vertex]] = {
PassHint:
PROC [ds:
ARRAY Role
OF Descendant]
--HintConsumer-- = {
vA: Vertex = GetStructure[sctA, ds[A]];
vB: Vertex = GetStructure[sctB, ds[B]];
Consume[vA, vB];
};
IF GiveHints # NIL THEN GiveHints[PassHint];
IF needsFrom[A].GetSize[] # 0
THEN {
GiveMatch:
PROC [key, value:
REF
ANY]
RETURNS [quit:
BOOL ←
FALSE] = {
need: Need = NARROW[value];
IF need.from = NIL OR need.to = NIL THEN ERROR;
Consume[need.from, need.to];
};
IF HashTable.Pairs[needsFrom[A], GiveMatch] THEN ERROR;
};
IF needsFrom[B].GetSize[] # 0
THEN {
bs: INT ← 0;
PerPart:
PROC [vA: Vertex] = {
matched: BOOL ← FALSE;
FOR ds: Element ← GetCore[vA], ds.rest
WHILE ds #
NIL
DO
name:
ROPE =
WITH ds.first
SELECT
FROM
dw: DescendantWire => CO.GetShortWireName[dw.wire],
dci: DescendantCellInstance => CC.GetCellInstanceName[CF.ResolveFlatCellType[cts[A], [dci^, 0]].instance],
ENDCASE => ERROR;
need: Need = NARROW[needsFrom[B].Fetch[name].value];
IF need #
NIL
THEN {
IF matched THEN ERROR;
matched ← TRUE;
IF need.from = NIL OR need.to # NIL THEN ERROR;
Consume[vA, need.from];
};
ENDLOOP;
};
sctA.EnumerateParts[PerPart, FALSE];
};
};
CdToDla:
PROC [cd: ColorData]
RETURNS [dla: EltListArray] = {
dla ← ALL[NIL];
FOR v: Vertex ← cd.firstVertex, GetColorNext[v]
WHILE v #
NIL
DO
IF NOT IsMirror[v] THEN dla[v.GetGraph[]] ← CONS[GetCore[v], dla[v.GetGraph[]]];
ENDLOOP;
dla ← dla;
};
ttols:
ARRAY RealGraphID
OF TransistorTolerances ~ [
A: NARROW[Asserting.FnVal[transistorTolerancesKey, scts[A].otherPublic]],
B: NARROW[Asserting.FnVal[transistorTolerancesKey, scts[B].otherPublic]]];
ttol: TransistorTolerancesPrivate ~ [
length: [
min: MAX[ttols[A][length].min, ttols[B][length].min],
max: MIN[ttols[A][length].max, ttols[B][length].max]],
width: [
min: MAX[ttols[A][width].min, ttols[B][width].min],
max: MIN[ttols[A][width].max, ttols[B][width].max]]];
ReportColor:
PROC [key:
INT, value:
REF
ANY]
RETURNS [quit:
BOOL ←
FALSE]
--IntHashTableThreaded.EachPairAction-- = {
cd: ColorData = NARROW[value];
ds: EltListArray = CdToDla[cd];
IF cd.count =
ALL[1]
THEN {
isTransistor: ARRAY RealGraphID OF BOOL;
trs:
ARRAY RealGraphID
OF
RECORD [
type: CC.TransistorType,
shape: ARRAY TransistorDim OF REAL];
FOR g: RealGraphID
IN RealGraphID
DO
first: BOOL ← TRUE;
FOR dl: Element ← ds[g].first, dl.rest
WHILE dl #
NIL
DO
WITH dl.first
SELECT
FROM
dci: DescendantCellInstance => {
ct: Core.CellType ~ CO.ToBasic[CF.ResolveFlatCellType[ccts[g], [dci^]].cellType];
thisIs: BOOL ~ ct.class = CC.transistorCellClass;
IF first THEN isTransistor[g] ← thisIs ELSE IF isTransistor[g] # thisIs THEN ERROR;
IF thisIs
THEN {
tr: CC.Transistor ~ NARROW[ct.data];
IF first
THEN trs[g] ← [tr.type, [tr.length, tr.width]]
ELSE {
IF tr.type # trs[g].type OR tr.length # trs[g].shape[length] THEN ERROR;
trs[g].shape[width] ← trs[g].shape[width] + tr.width;
};
};
first ← FALSE;
};
dw: DescendantWire => {
thisIs: BOOL ~ FALSE;
IF first THEN {first ← FALSE; isTransistor[g] ← thisIs} ELSE IF isTransistor[g] # thisIs THEN ERROR;
};
ENDCASE => ERROR;
ENDLOOP;
IF first THEN ERROR;
ENDLOOP;
IF isTransistor[A] # isTransistor[B] THEN ERROR;
IF isTransistor[A]
THEN {
FOR td: TransistorDim
IN TransistorDim
DO
ratio: REAL ~ trs[A].shape[td] / trs[B].shape[td];
IF ratio < ttol[td].min
OR ratio > ttol[td].max
THEN PerMismatch[
msg: IO.PutFR["transistor %g mismatch (%g/%g not within a factor of %g)", [rope[TransistorDimName[td]]], [real[trs[A].shape[td]]], [real[trs[B].shape[td]]], [real[ttol[td].max]]],
kind: transistorShape,
cts: cts,
colorElts: [A: ds[A], B: ds[B]],
Ans: Answer];
ENDLOOP;
};
IF PerPair # NIL THEN PerPair[[A: ds[A].first, B: ds[B].first]];
}
ELSE IF quittedEarly AND cd.count[A]=cd.count[B] THEN NULL
ELSE {
IF PerMismatch #
NIL
THEN PerMismatch[
kind: IF cd.count[A] = cd.count[B] THEN stuck ELSE difference,
cts: cts,
colorElts: [A: ds[A], B: ds[B]],
Ans: Answer];
};
};
Answer:
PROC [r: Role, d: Descendant]
RETURNS [dlp: Pair] = {
g: RealGraphID ~ roleToGraphID[r];
v: Vertex = CanonizeAndGetStructure[scts[g], d];
IF v = NIL THEN ERROR;
{cd: ColorData = NARROW[partition.Fetch[v.CurColor[]].value];
IF cd.count # ALL[1] THEN RETURN [[NIL, NIL]];
{dla: EltListArray = CdToDla[cd];
RETURN [[A: dla[A].first, B: dla[B].first]];
}}};
partition: ColorTable;
quittedEarly: BOOL;
[isomorphic, quittedEarly, partition] ← CompareGraphs[realDescrs, sctA, sctB, GenerateHints, automorphismHack, FALSE, mayQuitEarly, abort];
IF abort^ THEN RETURN [FALSE];
didQuitEarly^ ← quittedEarly;
[] ← partition.Pairs[ReportColor];
IF Querier # NIL THEN Querier[Answer];
ForgetGraph[sctA];
ForgetGraph[sctB];
}}};