
    <<LichenStructuring.Mesa>>
        <<Last tweaked by Mike Spreitzer on September 18, 1987 11:25:38 am PDT>>

    DIRECTORY Collections, LichenDataStructure, PairCollections, IntFunctions;

    LichenStructuring: CEDAR DEFINITIONS
        IMPORTS Collections
        =
    BEGIN

    OPEN LichenDataStructure, Colls:Collections, PairColls:PairCollections, IntFns:IntFunctions;

    Set: TYPE ~ LichenDataStructure.Set;
    Relation: TYPE ~ LichenDataStructure.Relation;
    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 
        up: OneToOne--child stepNode 
        cands: Set--of StepNode--,
        root: Thing
        ];

    Decomp: TYPE ~ REF OneToOne--NameStep 
    Ups: TYPE ~ REF Relation--parent StepNode 

    StepNode: TYPE ~ REF ANY --actually UNION [Thing, Fake]--;
    Fake: TYPE ~ REF ANY;
        <<Doesn't matter what it is, only the identity is used (and the fact that it's runtime-distinguishable from a Thing).  Let's use 
        its Decomp (actually, that choice is depended on now).>>

    CreateDAG: PROC [root: StepNode, ups: BOOL] RETURNS [dag: StepDAG];
    VerifyDAG: PROC [dag: StepDAG, mayBeLone: StepNode, midThings: BOOL];

    InsertInDAG: PROC [dag: StepDAG, parent: StepNode, parts: SteppyName, thing: Thing];
    AddLink: PROC [dag: StepDAG, parent: StepNode, step: NameStep, child: StepNode, downRed: BOOL];
    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: CleanOption];
        CleanOption: TYPE ~ {ignore, wontBeNeeded, ifFake, do};
    ReplaceNode: PROC [dag: StepDAG, doomed, survivor: StepNode];
    RemoveLeaf: PROC [dag: StepDAG, leaf: StepNode];

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

    IsThing: PROC [node: StepNode] RETURNS [BOOL] ~ INLINE {
        RETURN [WITH node SELECT FROM
            x: Port => TRUE,
            x: Wire => TRUE,
            x: Fake => FALSE,
            ENDCASE => ERROR]};

    RawLeaf: PROC [dag: StepDAG, node: StepNode] RETURNS [BOOL] ~ INLINE {
        RETURN [node#dag.root AND (WITH node SELECT FROM
            x: Port => TRUE,
            x: Wire => TRUE,
            x: Fake => FALSE,
            ENDCASE => ERROR)]};

    IsKidCand: PROC [dag: StepDAG, node: StepNode] RETURNS [BOOL] ~ INLINE {
        RETURN [node#dag.root AND (WITH node SELECT FROM
            x: Port => TRUE,
            x: Wire => TRUE,
            x: Fake => dag.cands.HasMember[x],
            ENDCASE => ERROR)]};

    END.