DIRECTORY Asserting, CardHashTableThreaded, Core, CoreClasses, CoreFlat, CoreOps, CoreProperties, CoreStructuralComparison, HashTable, IO, OneToOne, Rope, RopeHash, StructuralComparisonDataStructure, StructuralComparisonOps, StructureFromCore;

StructuralComparisonOuter: CEDAR PROGRAM
IMPORTS Asserting, CardHashTableThreaded, CoreClasses, CoreFlat, CoreOps, CoreProperties, HashTable, IO, OneToOne, StructuralComparisonDataStructure, StructuralComparisonOps, StructureFromCore
EXPORTS CoreStructuralComparison
SHARES StructuralComparisonDataStructure
=

BEGIN OPEN CC:CoreClasses, CO:CoreOps, CP:CoreProperties, CF:CoreFlat, CoreStructuralComparison, StructuralComparisonDataStructure, StructuralComparisonOps, StructureFromCore;

Need: TYPE = REF NeedPrivate;
NeedPrivate: TYPE = RECORD [name: ROPE, from, to: Vertex];

EltListArray: TYPE ~ ARRAY RealGraphID OF ElementList;

matchProp: ATOM = CP.RegisterProperty[$StructuralComparisonMatch];

FlattenAndCompare:
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];
}}};

ToLeaves: PUBLIC PROC [instance: CC.CellInstance, path: CF.InstancePath] RETURNS [leafType: Core.CellType] --SubtreeSpec-- = {
leafType _ CO.ToBasic[instance.type];
IF leafType.class = CC.recordCellClass THEN leafType _ NIL;
};

DontFlatten: PUBLIC PROC [instance: CC.CellInstance, path: CF.InstancePath] RETURNS [leafType: Core.CellType] --SubtreeSpec-- = {
leafType _ instance.type;
};

MergeNothing: PUBLIC PROC [original, parent: Core.CellType, path: CF.InstancePath, EnumerateInstances: PROC [Consume: PROC [ci: CC.CellInstance] RETURNS [stop: BOOL _ FALSE]], IdentifyActual: PROC [ci: CC.CellInstance, actual: Core.Wire, describe: BOOL _ FALSE] RETURNS [ActualID], Consume: MergeConsumer] --MergeSpec-- = {
NULL;
};

CreatePublicMapping: PROC [from, to: Core.CellType] RETURNS [pm: OneToOne.OneToOne] = {
Note: PROC [actualWire, publicWire: Core.Wire] RETURNS [subWires: BOOL _ TRUE, quit: BOOL _ FALSE] --CO.EachWirePairProc-- = {
wfrom: Core.Wire = actualWire;
wto: Core.Wire = publicWire;
IF wfrom.size # wto.size THEN ERROR;
IF wto.size = 0 THEN {
dfrom: DescendantWire = NEW [CF.FlatWireRec _ [wireRoot: public, wire: wfrom]];
dto: DescendantWire = NEW [CF.FlatWireRec _ [wireRoot: public, wire: wto]];
pm.Associate[dfrom, dto];
};
};
IF from = to THEN RETURN [OneToOne.id];
pm _ OneToOne.CreateVanillaOneToOne[HashDescendant, HashDescendant, DescendantEqual, DescendantEqual];
IF CO.VisitBinding[from.public, to.public, Note] THEN ERROR;
pm _ pm;
};

HashDescendant: PUBLIC PROC [ra: REF ANY] RETURNS [hash: CARDINAL] = {
org: Descendant = ra;
hash _ WITH org SELECT FROM
x: DescendantWire => x.FlatWireHash[],
x: DescendantCellInstance => x^.InstancePathHash[],
ENDCASE => ERROR;
};

DescendantEqual: PUBLIC PROC [r1, r2: REF ANY] RETURNS [equal: BOOL] = {
o1: Descendant = r1;
o2: Descendant = r2;
equal _ WITH o1 SELECT FROM
x: DescendantWire => WITH o2 SELECT FROM
y: DescendantWire => x.FlatWireEqual[y],
ENDCASE => FALSE,
x: DescendantCellInstance => WITH o2 SELECT FROM
y: DescendantCellInstance => x^.InstancePathEqual[y^],
ENDCASE => FALSE,
ENDCASE => ERROR;
};

END.
”StructuralComparisonOuter.Mesa
Mike Spreitzer March 10, 1987 10:27:53 am PST
Last tweaked by Mike Spreitzer on March 24, 1987 2:52:42 pm PST
Κθ–

"cedar" style˜
code™Kš
œ-™-K™?—K˜KšΟk	œ~œj˜σ
K˜šΡbnxœœ
˜(Kšœ^œY˜ΐ
Kšœ˜ Kšœ"˜(Kš
œ
˜
K˜Kšœ
œ
œœ
œœs˜―
K˜Kšœœœ
˜Kšœ
œœœ˜:K˜Kšœœœ
œ
˜6K˜Kšœœœ.˜BK˜š
œ˜š
˜šœ˜Kšœœœ
œ
˜Kš
œ˜Kšœœœœ˜0Kšœœœ
œ˜1KšΟn	œœ
˜KšŸœœ
˜'KšŸœœ
˜$KšŸœœ
˜"Kšœ œœ
˜-Kšœœ
˜Kš
œ
˜
—Kšœœ
˜—˜Kš
œG˜Gšœœœ˜,KšŸ
œI˜JKšŸ
œJ˜K—š
Ÿœœœ
œ
Οcœ˜Kš
œœœ
œœ
˜.Kšœœ˜-Kšœœœ$˜=Kšœœ˜—šœ
œ
œ˜Kšœ
œœ˜5Kšœ
œ&œ
œ
˜7K˜—K˜—š
Ÿœœœ
œ
 œ˜KKšœœ
˜Kšœœ
œœ
œ
œ
˜$šœœ
˜Kšœœ"œ
œ˜bKš	œœœ&œ
œ&˜vKšœœ
˜—Kšœœ!˜6šœ
œ
œ˜Kšœ
œœ˜5Kšœ
œ&œ
œ
˜7K˜—šœ	œ
œ˜Kšœœ
œ
œ
˜K˜—K˜—Kšœœ
œ˜GKšœœ
œœ˜Kšœœ
œ˜HKšœœ
œœ˜Kšœœ
œ(˜CKšœœ
œ˜9šŸ
œœŸœœ˜8š
Ÿœœœœ
 œ˜BKš
œ'˜'Kš
œ'˜'K˜K˜—Kšœ
œ
œ˜,šœœ˜$šŸ	œœœ
œœœœ˜FKšœ
œ˜Kšœ
œ
œœ
œ
œ
˜/Kš
œ˜K˜—Kšœ*œ
œ
˜7K˜—šœœ˜$Kšœœ˜šŸœœ˜Kšœ	œœ
˜šœ$œœ
˜8šœœœ
œ
˜&Kšœœ˜3Kšœœœ2˜jKšœœ
˜—Kšœ
œ!˜4šœœ
œ˜Kšœ	œ
œ
˜Kšœ
œ
˜Kšœ
œ
œœ
œ
œ
˜/Kš
œ˜K˜—Kšœ
˜—K˜—Kšœœ˜$K˜—K˜—šŸœœœ˜=Kšœœ
œ˜šœ-œœ
˜@Kšœ
œ
œœ ˜PKšœ
˜—K˜
K˜—šœœ
œ˜4KšŸ
œœ@˜IKšŸ
œœA˜J—š
œ%˜%˜	Kšœœ-˜5Kšœœ.˜6—˜Kšœœ+˜3Kšœœ-˜5——šŸœœœ	œ
œœœœ 'œ˜uKšœœ˜Kš
œ˜šœœœ˜Kšœœ
œ
œ
˜(šœœ
œ
œ˜"Kšœœ˜Kšœœœ
œ˜$—šœœ
˜$Kšœœœ
˜šœ$œœ
˜8šœ
œ
˜š
œ ˜ Kšœœ	œ0˜QKšœœœ˜1Kšœœœ
œœ
œ
˜Sšœœ˜Kšœœœ
˜$šœœ+œ˜>Kšœœ"œ
œ
˜HK˜5K˜—K˜—Kšœœ
˜K˜—š
œ˜Kšœœœ
˜Kšœœ
œœ
œœ
œ
˜dKš
œ˜—Kšœœ
˜—Kšœ
˜—Kšœœ
œ
˜Kšœ
˜—Kšœ#œ
œ
˜0šœœ˜šœœ˜)Kšœœ'˜2šœœœ
˜AKšœœ¬
˜³
Kš
œ˜K˜	K˜ KšŸœ
˜
—Kšœ
˜—K˜—Kšœœ
œ+˜@K˜
—Kš	œ
œœœ
˜:šœ˜šœœ
œ
˜&Kšœœœœ˜>K˜	K˜ KšŸœ
˜
—K˜—K˜—šŸœœœ˜=Kš
œ"˜"Kš
œ0˜0Kšœœ
œ
œ
˜Kšœœ&˜=Kšœœœ
œœœ˜.Kš
œ!˜!Kšœ&˜,K˜—Kš
œ˜Kšœœ
˜Kšœoœ˜‹
Kšœœ
œœ˜Kš
œ˜Kš
œ"˜"Kšœœ
œ˜&Kš
œ˜Kš
œ˜K˜——K˜šŸœœ
œœœœ œ˜~Kšœœ˜%Kšœœœœ
˜;K˜—K˜šŸœœ
œœœœ œ˜
Kš
œ˜K˜—K˜š(Ÿœœ
œ)œŸœœŸœœœœœœŸœœœ,œœœ
Ÿœ 
œ˜ΓKšœ
˜K˜—K˜šŸœœœ˜WšŸœœ%œœœœœ œ˜~Kšœ
Οdœ˜Kšœ
‘œ˜Kš
œ‘œ	‘œœ
œ
˜$šœ‘œ
œ˜Kš	œ
‘œœœ)‘œ˜OKš	œ
‘œœœ)‘œ˜KKšœ‘œ‘œ˜K˜—K˜—Kšœœ
œ˜'Kš
œf˜fKšœ
œ,œ
œ
˜<K˜K˜—K˜šŸœœ
œœ
œœœ˜FKš
œ˜šœœœ
˜Kš
œ&˜&Kš
œ3˜3Kšœœ
˜—K˜—K˜šŸœœ
œ
œ
œœ	œ˜HKš
œ˜Kš
œ˜šœœœ
˜šœœœ
˜(Kš
œ(˜(Kšœœ
˜—šœœœ
˜0Kš
œ6˜6Kšœœ
˜—Kšœœ
˜—K˜—K˜Kšœ
˜——…—&3Ž