StructuralComparisonOuter.Mesa
Last tweaked by Mike Spreitzer on October 26, 1990 1:08:57 pm PDT
Barth, April 16, 1987 10:44:04 pm PDT
DIRECTORY BasicTime, CardHashTableThreaded, Core, CoreClasses, CoreFlat, CoreOps, CoreProperties, CoreStructuralComparison, IO, OneToOne, Process, Real, RefTab, Rope, RopeHash, SimpleMailer, StructuralComparisonDataStructure, StructuralComparisonOps, StructureFromCore, SymTab;
StructuralComparisonOuter:
CEDAR
MONITOR
IMPORTS BasicTime, CardHashTableThreaded, CoreClasses, CoreFlat, CoreOps, CoreProperties, CoreStructuralComparison, IO, OneToOne, Process, RefTab, Rope, SimpleMailer, StructuralComparisonDataStructure, StructuralComparisonOps, StructureFromCore, SymTab
EXPORTS CoreStructuralComparison
SHARES StructuralComparisonDataStructure
=
BEGIN OPEN CC:CoreClasses, CO:CoreOps, CP:CoreProperties, CF:CoreFlat, CoreStructuralComparison, StructuralComparisonDataStructure, StructuralComparisonOps, StructureFromCore;
ViewStats: TYPE ~ REF ViewStatsPrivate;
ViewStatsPrivate: PUBLIC TYPE ~ StructuralComparisonDataStructure.ViewStatsPrivate;
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,
PerDroppedConnection: DroppedConnectionConsumer ← NIL,
PerBogusMerge: BogusMergeConsumer ← NIL,
Querier: AssociationQuerier ← NIL,
trace: Trace ← NIL,
automorphismHack, mayQuitEarly: BOOL ← FALSE,
didQuitEarly, abort: REF BOOL,
ttols: TransistorTolerances,
vsp: ViewStatsPair ← [NIL, NIL],
data: REF ANY ← NIL
]
RETURNS [isomorphic: BOOL]
= {
realDescrs: RealGraphDescriptions ~ [A: roleNames[A], B: roleNames[B]];
needsFrom:
ARRAY Role
OF SymTab.Ref ~ [
A: SymTab.Create[case: TRUE],
B: SymTab.Create[case: TRUE]];
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].val];
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[ttols, cts[A],
TRUE, data, stss[A], mss[A], SurveyA, vsp[A]!
DroppedConnection => {IF PerDroppedConnection#NIL THEN PerDroppedConnection[A, subroot, public, actual]; RESUME};
BogusMerge => {IF PerBogusMerge#NIL THEN PerBogusMerge[A, subroot, w1, w2, from]; RESUME}
];
IF abort^ THEN RETURN [FALSE];
{sctB: CellType = GetGraph[ttols,cts[B],
TRUE, data, stss[B], mss[B], SurveyB, vsp[B]!
DroppedConnection => {IF PerDroppedConnection#NIL THEN PerDroppedConnection[B, subroot, public, actual]; RESUME};
BogusMerge => {IF PerBogusMerge#NIL THEN PerBogusMerge[B, subroot, w1, w2, from]; RESUME}
];
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, val:
REF
ANY]
RETURNS [quit:
BOOL ←
FALSE] = {
need: Need = NARROW[val];
IF need.from = NIL OR need.to = NIL THEN ERROR;
Consume[need.from, need.to];
};
IF SymTab.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].val];
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;
};
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];
rl: REF INT ~ NARROW[CoreProperties.GetCellTypeProp[ct, CC.lengthProp]];
rw: REF INT ~ NARROW[CoreProperties.GetCellTypeProp[ct, CC.widthProp]];
queer: BOOL ~ rl=NIL OR rw=NIL;
shape: ARRAY TransistorDim OF REAL ~ IF queer THEN ALL[Real.LargestNumber] ELSE [rl^, rw^];
IF first
THEN trs[g] ← [tr.type, shape]
ELSE {
IF tr.type # trs[g].type OR shape[length] # trs[g].shape[length] THEN ERROR;
IF NOT queer THEN trs[g].shape[width] ← trs[g].shape[width] + shape[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]
AND trs[A].shape#trs[B].shape
THEN {
IF trs[A].shape#
ALL[Real.LargestNumber]
AND trs[B].shape#
ALL[Real.LargestNumber]
THEN {
FOR td: TransistorDim
IN TransistorDim
DO
ratio: REAL ~ trs[A].shape[td] / trs[B].shape[td];
IF ratio < ttols[td].min
OR ratio > ttols[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[ttols[td].max]]],
kind: transistorShape,
cts: cts,
colorElts: [A: ds[A], B: ds[B]],
Ans: Answer];
ENDLOOP;
}
ELSE PerMismatch[
msg: IF trs[A].shape=ALL[Real.LargestNumber] THEN Rope.Cat["transistor queerness mismatch: ", realDescrs[A], " is queer, ", realDescrs[B], " isn't"] ELSE Rope.Cat["transistor queerness mismatch: ", realDescrs[B], " is queer, ", realDescrs[A], " isn't"],
kind: transistorShape,
cts: cts,
colorElts: [A: ds[A], B: ds[B]],
Ans: Answer];
};
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 RETURN [[NIL, NIL]];
{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;
FOR r: Role
IN Role
DO
IF vsp[r] #
NIL
THEN {
id: RealGraphID ~ roleToGraphID[r];
vsp[r].maxFlatTransistors[Original] ← MAX[vsp[r].maxFlatTransistors[Original], scts[id].transCounts.flatTransistors];
vsp[r].maxFlatTransistors[Reconciled] ← MAX[vsp[r].maxFlatTransistors[Reconciled], scts[id].transCounts.flatTransistors - scts[id].transCounts.flatTransMerges];
vsp[r].maxFlatWires[Original] ← MAX[vsp[r].maxFlatWires[Original], scts[id].transCounts.flatWires + scts[id].transCounts.flatWireDels];
vsp[r].maxFlatWires[Reconciled] ← MAX[vsp[r].maxFlatWires[Reconciled], scts[id].transCounts.flatWires];
} ENDLOOP;
PushTimer[$base];
{ENABLE UNWIND => PopTimer[$base];
[isomorphic, quittedEarly, partition] ← CompareGraphs[realDescrs, sctA, sctB, trace, GenerateHints, automorphismHack, FALSE, mayQuitEarly, abort];
IF abort^ THEN {PopTimer[$base]; RETURN [FALSE]};
didQuitEarly^ ← quittedEarly;
[] ← partition.Pairs[ReportColor];
IF Querier # NIL THEN Querier[Answer];
ForgetGraph[sctA];
ForgetGraph[sctB]};
PopTimer[$base]}}};
ToLeaves:
PUBLIC
PROC [data:
REF
ANY, instance:
CC.CellInstance, path:
CF.InstancePath, ttols: TransistorTolerances]
RETURNS [SubtreeAns]
--SubtreeSpec-- = {
basic: Core.CellType ~ CO.ToBasic[instance.type];
IF basic.class =
CC.recordCellClass
THEN RETURN [[NIL, [NIL]]]
ELSE RETURN [[basic, CreateParallelMapper[basic, instance.type]]];
};
DontFlatten:
PUBLIC
PROC [data:
REF
ANY, instance:
CC.CellInstance, path:
CF.InstancePath, ttols: TransistorTolerances]
RETURNS [SubtreeAns]
--SubtreeSpec-- = {
RETURN [[instance.type, CreateIdentityMapper[instance.type]]]};
CreateParallelMapper:
PUBLIC
PROC [from, to: Core.CellType]
RETURNS [MapEnumerator] ~ {
RETURN [[EnumerateParallel, NEW [FromTo ← [from, to]]]]};
FromTo: TYPE ~ RECORD [from, to: Core.CellType];
EnumerateParallel:
PROC [data:
REF
ANY,
Consume: MapConsumer] ~ {
ft: REF FromTo ~ NARROW[data];
seen: RefTab.Ref ~ RefTab.Create[];
PerPair:
PROC [actualWire, publicWire: Core.Wire]
RETURNS [subWires:
BOOL ←
TRUE, quit:
BOOL ←
FALSE]
--CO.EachWirePairProc-- ~ {
ProduceTos: PROC [Consume: ToConsumer] ~ {Consume[actualWire]};
IF seen.Fetch[publicWire].found THEN RETURN;
IF NOT seen.Insert[publicWire, $T] THEN ERROR;
Consume[publicWire, ProduceTos];
RETURN};
[] ← CO.VisitBindingSeq[ft.to.public, ft.from.public, PerPair];
RETURN};
MergeNothing:
PUBLIC
PROC [data:
REF
ANY, parent: Core.CellType, recastOfSubroot:
BOOL,
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,
Depublicize: Depublicizer]
--MergeSpec-- = {
RETURN};
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 w
to.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 [
CARDINAL] = {
org: Descendant = ra;
RETURN [
WITH org
SELECT
FROM
x: DescendantWire => x.FlatWireHash[],
x: DescendantCellInstance => x^.InstancePathHash[],
ENDCASE => ERROR]};
DescendantEqual:
PUBLIC
PROC [key1, key2:
REF
ANY]
RETURNS [
BOOL] = {
o1: Descendant = key1;
o2: Descendant = key2;
RETURN [
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]};
DisplayStats: PUBLIC PROC ~ {StructuralComparisonOps.DisplayStats[]};
GetConstraints: PUBLIC PROC [subroot: Core.CellType] RETURNS [RefTab.Ref] ~ {RETURN GetCommonalityConstraints[subroot]};
TimerStack: TYPE ~ LIST OF Timer;
Timer: TYPE ~ REF TimerPrivate;
TimerPrivate:
TYPE ~
RECORD [
activity: ATOM,
secs, msecs: INT ← 0,
startGMT: BasicTime.GMT ← BasicTime.Now[],
startPulses: BasicTime.Pulses ← BasicTime.GetClockPulses[],
on: BOOL ← FALSE];
timers: RefTab.Ref ~ RefTab.Create[];
timerStack: TimerStack ← NIL;
timedProcess: UNSAFE PROCESS ← NIL;
countedSeconds: INT ← 0;
sendTimers: CONDITION;
PushTimer:
PUBLIC
ENTRY
PROC [activity:
ATOM] ~ {
me: UNSAFE PROCESS ~ Process.GetCurrent[];
nowGmt: BasicTime.GMT ~ BasicTime.Now[];
nowPulses: BasicTime.Pulses ~ BasicTime.GetClockPulses[];
IF timerStack=NIL THEN timedProcess ← me
ELSE {
IF timedProcess#me THEN ERROR--don't use PWCoreLichen in multiple processes (while I'm gathering these statistics)--;
StopTop[nowGmt, nowPulses]};
{timer: Timer ← NARROW[timers.Fetch[activity].val];
IF timer=NIL THEN IF NOT timers.Store[activity, timer ← NEW [TimerPrivate ← [activity]]] THEN ERROR;
timerStack ← CONS[timer, timerStack];
StartTop[nowGmt, nowPulses];
RETURN}};
PopTimer:
PUBLIC
ENTRY
PROC [activity:
ATOM] ~ {
me: UNSAFE PROCESS ~ Process.GetCurrent[];
nowGmt: BasicTime.GMT ~ BasicTime.Now[];
nowPulses: BasicTime.Pulses ~ BasicTime.GetClockPulses[];
IF timerStack.first.activity # activity THEN ERROR--caller blew it--;
StopTop[nowGmt, nowPulses];
timerStack ← timerStack.rest;
IF timerStack#NIL THEN StartTop[nowGmt, nowPulses];
RETURN};
StartTop:
INTERNAL
PROC [nowGmt: BasicTime.
GMT, nowPulses: BasicTime.Pulses] ~ {
timer: Timer ~ timerStack.first;
timer.startGMT ← nowGmt;
timer.startPulses ← nowPulses;
IF timer.on THEN ERROR;
timer.on ← TRUE;
RETURN};
StopTop:
INTERNAL
PROC [nowGmt: BasicTime.
GMT, nowPulses: BasicTime.Pulses] ~ {
timer: Timer ~ timerStack.first;
IF NOT timer.on THEN ERROR;
timer.on ← FALSE;
{ds: INT ~ BasicTime.Period[timer.startGMT, nowGmt];
IF
ds < 1000
THEN {
dp: BasicTime.Pulses ~ nowPulses-timer.startPulses;
dss: CARD ~ BasicTime.PulsesToMicroseconds[dp];
IF dss > 1D9+1D6 THEN ERROR;
{dsi: CARD ~ dss/1D6;
dsm: CARD ~ dss - dsi*1D6;
timer.secs ← timer.secs + dsi;
countedSeconds ← countedSeconds + dsi;
IF (timer.
msecs ← timer.
msecs +
dsm) > 1D6
THEN {
timer.secs ← timer.secs + 1;
timer.msecs ← timer.msecs - 1D6;
countedSeconds ← countedSeconds + 1};
}}
ELSE {
timer.secs ← timer.secs + ds;
countedSeconds ← countedSeconds + ds};
IF countedSeconds>500 THEN BROADCAST sendTimers;
timer.on ← FALSE;
RETURN}};
Sender:
PROC ~ {
Wait: ENTRY PROC ~ {ENABLE UNWIND => NULL; WAIT sendTimers; RETURN};
Process.SetPriority[Process.priorityForeground];
DO Wait[]; [] ← SendTimers[2]; ENDLOOP;
};
SendTimers:
PROC [threshold:
NAT ← 0]
RETURNS [aboveThreshold, sent:
BOOL ←
FALSE, failureReason:
ROPE ←
NIL] ~ {
ComposeBody:
ENTRY
PROC
RETURNS [
ROPE] ~ {
ENABLE UNWIND => NULL;
to: IO.STREAM ~ IO.ROS[];
PerTimer:
PROC [key, val:
REF
ANY]
RETURNS [quit:
BOOL ←
FALSE]
--RefTab.EachPairAction-- ~ {
activity: ATOM ~ NARROW[key];
timer: Timer ~ NARROW[val];
IF timer.activity # activity THEN ERROR;
to.PutF["%g: %g.%06d\n", [atom[activity]], [integer[timer.secs]], [integer[timer.msecs]] ];
timer.secs ← timer.msecs ← 0;
RETURN [FALSE]};
IF NOT (aboveThreshold ← countedSeconds >= threshold) THEN RETURN [NIL];
IF timers.Pairs[PerTimer] THEN ERROR;
countedSeconds ← 0;
RETURN [to.RopeFromROS[]]};
body: ROPE ~ ComposeBody[];
IF NOT aboveThreshold THEN RETURN;
IF NOT reallySend THEN RETURN;
[sent, failureReason] ← SimpleMailer.SendMessage[
from: "StructuralComparison",
to: LIST[[$chs, "Mike Spreitzer:PARC:Xerox"]],
subject: "Timers",
body: body];
RETURN};
reallySend: BOOL ← FALSE;
Start:
PROC ~
TRUSTED {
Process.InitializeCondition[@sendTimers, Process.SecondsToTicks[600]];
Process.Detach[FORK Sender[]];
Process.Yield[];
RETURN};
Start[];
END.