<<>>
    <<MakeDoImpl.Mesa>>
    <<Last Edited by: Spreitzer, May 20, 1985 11:44:42 am PDT>>
        <<Carl Hauser, April 11, 1985 3:43:34 pm PST>>

    <<IF A is needed & C makes A from B THEN B is needed.>>
    <<>>
    <<IF A is needed & A doesn't exist & C makes A THEN C needs to be done>>
    <<>>
    <<IF A is needed & A is out-of-date & C makes A THEN C needs to be done>>
    <<>>
    <<IF C needs to be done & (ForAll B used by C: B exists) THEN C can be done>>
    <<>>
    <<IF C needs to be done & C can't be done THEN C fails>>
    <<>>
    <<IF C succeeded & C makes A THEN A may have changed>>
    <<>>
    <<IF C failed & C makes A THEN A doesn't exist>>
    <<>>
    <<IF C derived from D & D changed THEN {B| C uses B} may have changed>>
    <<>>
    <<IF A is needed & A is certainly modifiable & C makes A from B & B doesn't exist THEN Complain (actually, don't complain if 
    complaint was already given for a recursive ingredient)>>
    <<>>
    DIRECTORY Basics, BasicTime, Commander, CommandTool, FileNames, FileViewerOps, FS, IO, MakeDo, RedBlackTree, Process, Rope, 
    TimeStamp, ViewerIO;

    MakeDoSimpleImpl: CEDAR MONITOR
        IMPORTS CommandTool, FileNames, FileViewerOps, FS, IO, RedBlackTree, Process, Rope, ViewerIO
        EXPORTS MakeDo =

    BEGIN OPEN MakeDo;

    Warning: PUBLIC SIGNAL [message: ROPE] = CODE;

    Error: PUBLIC ERROR [message: ROPE] = CODE;

    NodeList: TYPE = LIST OF Node;
    Node: TYPE = REF NodeRep;
    NodeRep: PUBLIC TYPE = RECORD [
        name: ROPE,
        producer: Command _ NIL,
        derivedCmds, consumers: CommandList _ NIL,
        props: PropList _ NIL,
        missed: BOOL _ FALSE,
        explained: BOOLEAN _ FALSE,
        timeValid: BOOLEAN _ FALSE,
        needed: BOOL _ FALSE,
        modifiable: BOOL _ FALSE,
        rooted: BOOL _ FALSE,
        inStack: BOOL _ FALSE,
        latest: BasicTime.GMT _ BasicTime.nullGMT
            <<BasicTime.nullGMT means does not exist.>>
        ];

    Command: TYPE = REF CommandRep;
    CommandRep: PUBLIC TYPE = RECORD [
        cmd: ROPE,
        makes, from, missedSources, missedResults: NodeList,
        outdated, needsToBeDone: BOOLEAN _ FALSE,
        class: CommandClass,
        foundData: REF ANY,
        initialized: BOOLEAN _ FALSE,
        canBeDone: BOOLEAN _ TRUE,
        failed: BOOLEAN _ FALSE,
        makesACertainlyModifiable: BOOL _ FALSE
        ];

    nodes: RedBlackTree.Table _ RedBlackTree.Create[GetKey, CompareNodes];

    depth: INT _ 0;
    debugging: BOOLEAN _ FALSE;
    log, in: IO.STREAM _ NIL;
    boundaryKnown: BOOL _ FALSE;

    Log: PUBLIC PROC [fmt: ROPE, v1, v2, v3, v4, v5: IO.Value _ [null[]]] =
        BEGIN
        FOR i: INT IN [0 .. depth) DO log.PutChar['\t] ENDLOOP;
        log.PutF[fmt, v1, v2, v3, v4, v5];
        log.PutChar['\n];
        END;

    Confirm: PROC [action: ROPE] =
        BEGIN
        FOR i: INT IN [0 .. depth) DO log.PutChar['\t] ENDLOOP;
        log.PutF["Ready to %g ? ", IO.rope[action]];
        WHILE in.GetChar[] # '\n DO NULL ENDLOOP;
        END;

    PublicPartsOfNode: PUBLIC PROC [n: Node] RETURNS [name: ROPE, producer: Command, derivedCmds, consumers: CommandList, props: 
    PropList] = {
        RETURN [
            name: n.name,
            producer: n.producer,
            derivedCmds: n.derivedCmds,
            consumers: n.consumers,
            props: n.props
            ];
        };

    SetProps: PUBLIC PROC [node: Node, props: PropList] = {node.props _ props};

    SetLatest: PUBLIC PROC [node: Node, latest: BasicTime.GMT] = {
        IF node.timeValid THEN ERROR;
        node.timeValid _ TRUE; node.latest _ latest};

    Needed: PUBLIC PROC [node: Node] RETURNS [needed: BOOL] =
        {needed _ node.needed};

    PublicPartsOfCommand: PUBLIC PROC [c: Command] RETURNS [cmd: ROPE, makes, from: NodeList, foundData: REF ANY, needsToBeDone, 
    failed: BOOL] = {
        RETURN [
            cmd: c.cmd,
            makes: c.makes,
            from: c.from,
            foundData: c.foundData,
            needsToBeDone: c.needsToBeDone,
            failed: c.failed
            ];
        };

    GetNode: PUBLIC PROC [name: ROPE] RETURNS [node: Node] = {
        IF (node _ NARROW[nodes.Lookup[name]]) = NIL
            THEN nodes.Insert[node _ NEW [NodeRep _ [name: name]], node]};

    GetKey: PROC [data: REF ANY] RETURNS [REF ANY] --RedBlackTree.GetKey--  =
        {RETURN[data]};

    CompareNodes: PROC [k, data: REF ANY] RETURNS [Basics.Comparison]  --RedBlackTree.Compare-- =
        BEGIN
        GetKey: PROC [ra: REF] RETURNS[r: ROPE] = {
            r _ WITH ra SELECT FROM
                n: Node => n.name,
                x: ROPE => x,
                ENDCASE => ERROR};
        k1: ROPE _ GetKey[k];
        k2: ROPE _ GetKey[data];
        RETURN [k1.Compare[s2: k2, case: FALSE]];
        END;


    FileTime: PUBLIC PROC [n: Node] --UpdateTimeProc-- =
        BEGIN
        FileViewerOps.WaitUntilSaved[fileName: n.name, feedBack: currentCommanderHandle.err];
        [created: n.latest] _ FS.FileInfo[n.name !FS.Error =>
            {n.latest _ BasicTime.nullGMT; CONTINUE}];
        n.timeValid _ TRUE;
        END;

    finders: LIST OF Finder _ NIL;

    AddFinder: PUBLIC PROC [finder: Finder, end: End] =
        BEGIN
        SELECT end FROM
            front => finders _ CONS[finder, finders];
            back => {fl: LIST OF Finder;
                IF finders = NIL THEN {finders _ LIST[finder]; RETURN};
                FOR fl _ finders, fl.rest WHILE fl.rest # NIL DO NULL ENDLOOP;
                fl.rest _ LIST[finder]};
            ENDCASE => ERROR;
        END;

    GetLeaf: PROC [name: ROPE] RETURNS [node: Node] = {
        node _ GetNode[name];
        IF node.producer # NIL THEN ERROR;
        node.producer _ leaf};

    EnsureNodeProduced: PROC [node: Node] =
        BEGIN
        n: Node;
        IF node.producer # NIL THEN RETURN;
        n _ EnsureProduced[node.name, FALSE];
        IF node # n THEN ERROR Error[IO.PutFR["Disagreement on cannonical name for %g or %g", IO.rope[node.name], IO.rope[n.name]]];
        END;

    EnsureProduced: PROC [resultName: ROPE, makeModifiable: BOOL] RETURNS [sought: Node] =
        BEGIN
        FOR fl: LIST OF Finder _ finders, fl.rest WHILE fl # NIL DO
            found: BOOLEAN;
            makes, from, why: NodeList;
            cmd: ROPE;
        class: CommandClass;
            foundData: REF ANY;
            Process.CheckForAbort[];
            [found, sought, makes, from, why, cmd, class, foundData] _ fl.first.finderProc[resultName: resultName, finderData: 
            fl.first.finderData];
            IF found THEN {
                c: Command;
                first: BOOLEAN _ TRUE;
                soughtIn: BOOL _ FALSE;
                already: Command _ NIL;
                sought.modifiable _ sought.modifiable OR makeModifiable;
                IF (NOT sought.modifiable) AND boundaryKnown THEN RETURN [GetLeaf[resultName]];
                FOR ml: NodeList _ makes, ml.rest WHILE ml # NIL DO
                    soughtIn _ soughtIn OR (sought = ml.first);
                    IF first
                        THEN {already _ ml.first.producer; first _ FALSE}
                        ELSE {IF ml.first.producer # already
                            THEN ERROR Error[IO.PutFR[
                                "Command %g doesn't precisely cover command %g (e.g., at %g)",
                                IO.refAny[cmd],
                                IO.refAny[IF already # NIL THEN already.cmd ELSE NIL],
                                IO.rope[ml.first.name]]]};
                    ENDLOOP;
                IF NOT soughtIn THEN ERROR Error["Finder blew it"];
                IF already # NIL THEN RETURN [sought];
                c _ NEW [CommandRep _
                    [cmd: cmd, makes: makes, from: from, missedResults: NIL, class: class, foundData: foundData]];
                FOR ml: NodeList _ c.makes, ml.rest WHILE ml # NIL DO
                    IF ml.first.producer # NIL THEN ERROR;
                    ml.first.producer _ c;
                    ENDLOOP;
                FOR wl: NodeList _ why, wl.rest WHILE wl # NIL DO
                    wl.first.derivedCmds _ CONS[c, wl.first.derivedCmds];
                    ENDLOOP;
                RETURN};
            ENDLOOP;
        sought _ GetLeaf[resultName];
        END;

    leafClass: CommandClass _ NEW [CommandClassRep _ [UpdateTime: FileTime, Explain: ExplainLeaf]];

    root: Command _ NEW [CommandRep _ [cmd: "-- root"]];
    leaf: Command _ NEW [CommandRep _ [cmd: "-- leaf", class: leafClass]];

    ExplainLeaf: ExplainProc = {to.PutRope[" OOPS! Internal inconsistency (#3)\n"]};

    Explain: PUBLIC PROC [ch: Commander.Handle, what: RopeList] =
        BEGIN
        to: IO.STREAM _ ch.out;
        cwd: ROPE _ ConvertFromSlashFormat[FileNames.CurrentWorkingDirectory[]];
        currentCommanderHandle _ ch;
        FOR wl: RopeList _ what, wl.rest WHILE wl # NIL DO
            node: Node _ NIL;
            Try: PROC [name: ROPE] RETURNS [found: BOOL] = {
                IF node # NIL THEN ERROR;
                node _ NARROW[nodes.Lookup[name]];
                IF found _ (node # NIL) THEN wl.first _ name};
            IF
                Try[wl.first] OR
                Try[cwd.Cat[wl.first]] OR
                Try[wl.first.Cat[".BCD"]] OR
                Try[cwd.Cat[wl.first, ".BCD"]]
                THEN node.explained _ FALSE;
            ENDLOOP;
        FOR wl: RopeList _ what, wl.rest WHILE wl # NIL DO
            node: Node _ NARROW[nodes.Lookup[wl.first]];
            IF node = NIL THEN to.PutF["There was no %g\n\n", IO.rope[wl.first]]
            ELSE BEGIN
                to.PutF["%g needed by: {", IO.rope[node.name]];
                IF node.rooted THEN to.PutRope["\n\troot"];
                FOR cl: CommandList _ node.consumers, cl.rest WHILE cl # NIL DO
                    cc: Command _ NARROW[cl.first];
                    to.PutF["\n\t%g", IO.rope[cc.cmd]];
                    ENDLOOP;
                to.PutRope["}\n"];
                IF NOT node.explained THEN {
                    c: Command _ node.producer;
                    IF c = NIL THEN to.PutF["Nothing knew how to make %g\n\n", IO.rope[wl.first]]
                    ELSE IF c = leaf THEN to.PutF["%g was a source\n\n", IO.rope[wl.first]]
                    ELSE BEGIN
                        to.PutF["%g:\n\tMakes:\n", IO.rope[c.cmd]];
                        FOR ml: NodeList _ c.makes, ml.rest WHILE ml # NIL DO
                            to.PutF["\t\t%g\n", IO.rope[ml.first.name]];
                            ml.first.explained _ TRUE;
                            ENDLOOP;
                        to.PutRope["\tFrom:\n"];
                        FOR ml: NodeList _ c.from, ml.rest WHILE ml # NIL DO
                            to.PutF["\t\t%g\n", IO.rope[ml.first.name]];
                            ENDLOOP;
                        IF c.needsToBeDone # (c.outdated OR (c.missedResults # NIL)) THEN ERROR;
                        IF c.outdated THEN {
                            to.PutRope["\tneeded to be done because of inconsistency:\n"];
                            c.class.Explain[c, to];
                            };
                        IF c.missedResults # NIL THEN to.PutF["\tneeded to be done because result(s) %g missing\n", 
                        IO.rope[EnglishList[c.missedResults].el]];
                        IF NOT c.needsToBeDone THEN {
                            to.PutRope["\tdid not need to be done\n"];
                            c.class.Explain[c, to];
                            };
                        IF (c.needsToBeDone OR c.makesACertainlyModifiable) AND NOT c.canBeDone THEN
                            BEGIN
                            misses: ROPE;
                            missCount: CARDINAL _ 0;
                            [misses, missCount] _ EnglishList[c.missedSources, TRUE];
                            SELECT missCount FROM
                                = 0 => to.PutRope[" OOPS! Internal inconsistency (#1)!\n"];
                                > 0 => to.PutF["\tcouldn't be done because %g couldn't be made.\n", IO.rope[misses]];
                                ENDCASE => ERROR;
                            END;
                        to.PutRope["\n"];
                        END;
                    };
                END;
            ENDLOOP;
        currentCommanderHandle _ NIL;
        END;

    ConvertFromSlashFormat: PROC [slashy: ROPE] RETURNS [squigly: ROPE] =
        BEGIN
        cp: FS.ComponentPositions;
        full: ROPE;
        [fullFName: full, cp: cp] _ FS.ExpandName[slashy.Concat["foo"]];
        squigly _ full.Substr[start: 0, len: cp.base.start];
        END;

    EnglishList: PROC [nl: NodeList, all: BOOLEAN _ TRUE] RETURNS [el: ROPE, ec: CARDINAL] =
        BEGIN
        twoOfMany: ROPE;
        ec _ 0;
        FOR nl _ nl, nl.rest WHILE nl # NIL DO
            IF (NOT all) AND Exists[nl.first] THEN LOOP;
            SELECT ec FROM
                =0 => el _ nl.first.name;
                =1 => {
                    twoOfMany _ nl.first.name.Cat[", and ", el];
                    el _ nl.first.name.Cat[" and ", el];
                    };
                =2 => el _ nl.first.name.Cat[", ", twoOfMany];
                >2 => el _ nl.first.name.Cat[", ", el];
                ENDCASE => ERROR;
            ec _ ec + 1;
            ENDLOOP;
        END;

    DestroyNode: PROC [a: REF ANY] RETURNS [stop: BOOLEAN] = {
        n: Node _ NARROW[a];
        stop _ FALSE;
        n.props _ NIL;
        n.derivedCmds _ NIL;
        n.producer _ NIL};

    Ensure: PUBLIC ENTRY PROC [ch: Commander.Handle, what, otherModifiable: RopeList, guessBoundary, dontDo, assumeAllInconsistent: 
    BOOL] RETURNS [nFailed, nSucceeded, nSteps: NAT, failedSteps: CommandList, cmds: ROPE] =
        BEGIN ENABLE UNWIND => {};
        goals: NodeList _ NIL;
        nFailed _ nSucceeded _ 0;
        IF debugging AND log = NIL THEN [in: in, out: log] _ ViewerIO.CreateViewerStreams["MakeDo Log"];
        nodes.EnumerateIncreasing[DestroyNode];
        nodes.DestroyTable[];
        currentCommanderHandle _ ch;
        boundaryKnown _ NOT guessBoundary;
        depth _ 0;
        stepCount _ 0;
        failedCmds _ NIL;
        cmds _ NIL;
        FOR rl: RopeList _ otherModifiable, rl.rest WHILE rl # NIL DO
            n: Node _ EnsureProduced[rl.first, TRUE];
            n _ n;
            ENDLOOP;
        FOR rl: RopeList _ what, rl.rest WHILE rl # NIL DO
            n: Node _ EnsureProduced[rl.first, TRUE];
            n.rooted _ TRUE;
            goals _ CONS[n, goals];
            ENDLOOP;
        FOR goals _ goals, goals.rest WHILE goals # NIL DO
            p: Command _ goals.first.producer;
            cmds _ EnsureWork[p, goals.first, dontDo, assumeAllInconsistent, cmds];
            IF p.failed OR NOT p.canBeDone THEN nFailed _ nFailed + 1 ELSE nSucceeded _ nSucceeded + 1;
            ENDLOOP;
        currentCommanderHandle _ NIL;
        IF debugging THEN Log["\n"];
        nSteps _ stepCount;
        failedSteps _ failedCmds;
        END;

    failedCmds: CommandList;
    stepCount: INT;
    currentCommanderHandle: PUBLIC Commander.Handle;

    EnsureWork: PROC [c: Command, goal: Node, dontDo, assumeAllInconsistent: BOOL, prevCmds: ROPE] RETURNS [allCmds: ROPE] =
        BEGIN
        already: BOOL _ c.initialized;
        PostAmble: PROC = {
            goal.inStack _ FALSE;
            IF debugging THEN Log["EW <- %g", IO.rope[c.cmd]];
            depth _ depth - 1};
        allCmds _ prevCmds;
        IF c # goal.producer THEN ERROR;
        IF goal.inStack THEN {
            SIGNAL Warning[IO.PutFR["Found dependency cycle containing %g", IO.rope[goal.name]]];
            RETURN;
            };
        depth _ depth + 1;
        IF debugging THEN Log["EW -> %g ", IO.rope[c.cmd]];
        goal.inStack _ TRUE;
        {ENABLE UNWIND => PostAmble[];
        goal.needed _ TRUE;
        IF (c = leaf) OR (c.initialized AND c.needsToBeDone) THEN {PostAmble[]; RETURN};
        WHILE NOT c.initialized DO
            c.initialized _ TRUE;
            c.outdated _ FALSE;
            c.makesACertainlyModifiable _ FALSE;
            FOR ml: NodeList _ c.makes, ml.rest WHILE ml # NIL DO
                IF ml.first.modifiable THEN {c.makesACertainlyModifiable _ TRUE; EXIT};
                ENDLOOP;
            FOR mrl: NodeList _ c.missedResults, mrl.rest WHILE mrl # NIL DO
                mrl.first.missed _ FALSE;
                ENDLOOP;
            c.missedResults _ NIL;
            FOR sl: NodeList _ c.from, sl.rest WHILE sl # NIL DO
                Process.CheckForAbort[];
                sl.first.consumers _ CONS[c, sl.first.consumers];
                EnsureNodeProduced[sl.first];
                allCmds _ EnsureWork[sl.first.producer, sl.first, dontDo, assumeAllInconsistent, allCmds];
                ENDLOOP;
            ENDLOOP;
        Process.CheckForAbort[];
        IF (NOT goal.missed) AND (NOT Exists[goal]) THEN {
            c.missedResults _ CONS[goal, c.missedResults];
            goal.missed _ TRUE};
        c.needsToBeDone _ c.outdated OR (c.missedResults # NIL);
        IF (NOT c.needsToBeDone) AND (NOT already) AND (assumeAllInconsistent OR c.class.NotCurrent[c]) THEN c.outdated _ c.needsToBeDone _ 
        TRUE;
        IF c.needsToBeDone OR (c.makesACertainlyModifiable AND NOT already) THEN {
            <<c.missedSources that are likely to be the source of the problem:>>
                missedBitches: NodeList _ NIL;
            c.missedSources _ NIL;
            FOR sl: NodeList _ c.from, sl.rest WHILE sl # NIL DO
                p: Command _ sl.first.producer;
                SELECT p FROM
                    leaf => IF NOT Exists[sl.first] THEN {
                        c.missedSources _ CONS[sl.first, c.missedSources];
                        missedBitches _ CONS[sl.first, missedBitches]};
                    ENDCASE => IF p.needsToBeDone AND (p.failed OR NOT p.canBeDone) THEN {
                        c.missedSources _ CONS[sl.first, c.missedSources];
                        IF NOT sl.first.modifiable THEN missedBitches _ CONS[sl.first, missedBitches];
                        };
                ENDLOOP;
            c.canBeDone _ c.missedSources = NIL;
            IF c.needsToBeDone AND c.canBeDone THEN {
                IF dontDo THEN {
                    allCmds _ allCmds.Cat[c.cmd, "\n"];
                    }
                ELSE {
                    IF debugging THEN Confirm[c.cmd];
                    stepCount _ stepCount + 1;
                    c.failed _ (doans _ CommandTool.DoCommand[commandLine: c.cmd, parent: currentCommanderHandle]) = $Failure;
                    IF c.failed THEN failedCmds _ CONS[c, failedCmds];
                    FOR ml: NodeList _ c.makes, ml.rest WHILE ml # NIL DO
                        ml.first.timeValid _ FALSE;
                        ENDLOOP;
                    FOR ml: NodeList _ c.makes, ml.rest WHILE ml # NIL DO
                        FOR cl: CommandList _ ml.first.derivedCmds, cl.rest WHILE cl # NIL DO
                            RederiveCommand[cl.first];
                            ENDLOOP;
                        ENDLOOP;
                    };
                };
            IF missedBitches # NIL AND c.makesACertainlyModifiable THEN {
                SIGNAL Warning[IO.PutFR[
                    "Couldn't %g%g because %g missing or unmakeable.\n",
                    IO.rope[IF NOT c.needsToBeDone THEN "check consistency of " ELSE ""],
                    IO.rope[c.cmd],
                    IO.rope[EnglishList[c.missedSources].el]]];
                };
            };
        };
        PostAmble[];
        END;

    doans: REF ANY;

    RederiveCommand: PROC [c: Command] =
        BEGIN
        [c.from, c.cmd] _ c.class.Rederive[c];
        c.initialized _ FALSE;
        END;

    Exists: PUBLIC PROC [n: Node, u: UpdateTimeProc _ NIL] RETURNS [exists: BOOL] =
        {exists _ Latest[n, u] # BasicTime.nullGMT};

    Latest: PUBLIC PROC [n: Node, u: UpdateTimeProc _ NIL] RETURNS [t: BasicTime.GMT] = {
        IF n.timeValid THEN RETURN [n.latest];
        (IF u = NIL THEN n.producer.class.UpdateTime ELSE u)[n];
        IF NOT n.timeValid THEN ERROR;
        t _ n.latest};

    END.