[_CD4_]<datools7.0>Lichen>LichenStructuring.Mesa!10

LichenStructuring.Mesa

Last tweaked by Mike Spreitzer on February 2, 1988 1:13:20 pm PST

DIRECTORY AbSets, LichenDataStructure, BiRels;

LichenStructuring: CEDAR DEFINITIONS

IMPORTS AbSets, BiRels

BEGIN

OPEN LichenDataStructure, Sets:AbSets;

Set: TYPE ~ LichenDataStructure.Set;

BiRel: TYPE ~ LichenDataStructure.BiRel;

Function: TYPE ~ LichenDataStructure.Function;

OneToOne: TYPE ~ LichenDataStructure.OneToOne;

Seq: TYPE ~ LichenDataStructure.Seq;

Thing: TYPE ~ REF ANY --actually UNION [Port, Wire]--;

StepTriple: TYPE ~ RECORD [parent: StepNode, step: NameStep, child: StepNode];

StepDAG: TYPE ~ REF StepDAGPrivate;

StepDAGPrivate: TYPE ~ RECORD [

down: Function--parent StepNode b Decomp--,

up: OneToOne--child stepNode é Ups--,

toThing: Function--StepNode b Thing, exclusive of root--,

cands: Set--domain of candSize--,

rootThing: Thing,

rootNode: StepNode,

prefixd, leavesCommonized: BOOL ← FALSE

];

Decomp: TYPE ~ REF Function--NameStep b child StepNode--;

Ups: TYPE ~ REF BiRel--parent StepNode NameStep--;

StepNode: TYPE ~ REF INT;

These are just placeholders. Every leaf node always has a Thing; once the prefix property is established, only leaves have Things. Once the leaves are `commonized', each Thing is had by exactly one leaf.

StepTree: TYPE ~ StepNode;

CandGrade: TYPE ~ RECORD [

good: BOOL,

size: INT

];

CreateDAG: PROC [root: REF ANY--UNION[Thing, StepNode]--, from: StepDAG] RETURNS [dag: StepDAG];

VerifyDAG: PROC [dag: StepDAG];

InsertInDAG: PROC [dag: StepDAG, parent: StepNode, steps: NameStepList, thing: Thing];

AddLink: PROC [dag: StepDAG, parent: StepNode, step: NameStep, child: StepNode];

GetDown: PROC [dag: StepDAG, parent: StepNode, step: NameStep, mayAdd: BOOL] RETURNS [child: StepNode];

GetDecomp: PROC [dag: StepDAG, parent: StepNode, mayAdd: BOOL] RETURNS [dec: Decomp];

GetUps: PROC [dag: StepDAG, child: StepNode, mayAdd: BOOL] RETURNS [ups: Ups];

RemoveLink: PROC [dag: StepDAG, parent: StepNode, step: NameStep, child: StepNode, cleanup: CleanUpOption];

CleanUpOption: TYPE ~ {ignore, wontBeNeeded, ifNotThinged, do};

ReplaceNode: PROC [dag: StepDAG, doomed, survivor: StepNode, cleanDown: CleanDownOption];

CleanDownOption: TYPE ~ {unlink, keep, none};

RemoveLeaf: PROC [dag: StepDAG, leaf: StepNode];

PruneCand: PROC [dag: StepDAG, cand: StepNode];

Sequify: PROC [oto: OneToOne] RETURNS [seq: Seq];

GradeCand: PROC [dag: StepDAG, cand: StepNode] RETURNS [grade: CandGrade];

CommonizeLeaves: PROC [dag: StepDAG];

CommonizeDecomps: PROC [dag: StepDAG];

CreateTreeSpace: PROC [dag: StepDAG] RETURNS [treeSpace: Sets.Space];

IsKidCand: PROC [dag: StepDAG, node: StepNode] RETURNS [BOOL] ~ INLINE {

IF dag.cands.HasMemA[node] THEN RETURN [TRUE];

IF dag.down.HasMapA[node] THEN RETURN [FALSE];

IF NOT dag.prefixd THEN ERROR--can't check yet--;

IF NOT dag.toThing.HasMapA[node] THEN ERROR--node not in this dag--;

RETURN [TRUE]};

END.