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šœœ,œœ˜