StructuralComparisonOuter.Mesa
Last tweaked by Mike Spreitzer on March 4, 1989 1:52:12 pm PST
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;
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: BOOLFALSE,
didQuitEarly, abort: REF BOOL,
ttols: TransistorTolerances,
vsp: ViewStatsPair ← [NIL, NIL],
data: REF ANYNIL
]
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: BOOLFALSE] = {
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: BOOLFALSE;
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: BOOLFALSE] --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: BOOLTRUE;
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];
} 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: BOOLTRUE, quit: BOOLFALSE] --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: BOOLFALSE]], IdentifyActual: PROC [ci: CC.CellInstance, actual: Core.Wire, describe: BOOLFALSE] 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: BOOLTRUE, quit: BOOLFALSE] --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 [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: BOOLFALSE];
timers: RefTab.Ref ~ RefTab.Create[];
timerStack: TimerStack ← NIL;
timedProcess: UNSAFE PROCESSNIL;
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: BOOLFALSE, info: SimpleMailer.SendMessageInfo ← ok] ~ {
ComposeBody: ENTRY PROC RETURNS [ROPE] ~ {
ENABLE UNWIND => NULL;
to: IO.STREAM ~ IO.ROS[];
PerTimer: PROC [key, val: REF ANY] RETURNS [quit: BOOLFALSE]--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;
[sent, info] ← SimpleMailer.SendMessage[
from: "StructuralComparison",
to: LIST["Spreitzer.pa"],
subject: "Timers",
body: body];
RETURN};
Start: PROC ~ TRUSTED {
Process.InitializeCondition[@sendTimers, Process.SecondsToTicks[600]];
Process.Detach[FORK Sender[]];
Process.Yield[];
RETURN};
Start[];
END.