
    <<ProcMapImpl.mesa>>
        <<Copyright © 1984, 1985 by Xerox Corporation.  All rights reserved.>>
        <<Russ Atkinson, March 7, 1985 4:11:01 am PST>>
        <<Sweet November 21, 1985 5:01:01 pm PST>>

    DIRECTORY
        AMTypes,
        BcdDefs,
        ConvertUnsafe,
        ProcMap,
        Rope,
        RTSymbolDefs,
        RTSymbols,
        Symbols,
        SymbolSegment,
        SymbolTable;

    ProcMapImpl: CEDAR PROGRAM
        IMPORTS AMTypes, ConvertUnsafe, Rope, RTSymbols
        EXPORTS ProcMap
        = BEGIN

        Item: TYPE = ProcMap.Item;
        Object: TYPE = ProcMap.Object;
        Handle: TYPE = ProcMap.Handle;

        ROPE: TYPE = Rope.ROPE;
        SubString: TYPE = ConvertUnsafe.SubString;

        BodyInfo: TYPE = Symbols.BodyInfo;
        BTIndex: TYPE = Symbols.BTIndex;
            BTNull: BTIndex = Symbols.BTNull;
        CBTIndex: TYPE = Symbols.CBTIndex;
        FGTEntry: TYPE = SymbolSegment.FGTEntry;
        HTIndex: TYPE = Symbols.HTIndex;
            HTNull: HTIndex = Symbols.HTNull;
        ISEIndex: TYPE = Symbols.ISEIndex;
            ISENull: ISEIndex = Symbols.ISENull;
        SEIndex: TYPE = Symbols.SEIndex;
            SENull: SEIndex = Symbols.SENull;

    FromSource: PUBLIC PROC [h: Handle, src: INT] RETURNS [ROPE] =
        BEGIN
        l, u, m: INTEGER;
        IF h = NIL THEN RETURN["<anon>"];
        l _ 0; u _ h.length - 1;
        WHILE l <= u DO
            m _ (l+u)/2;
            SELECT h[m].firstSource FROM
                < src => l _ m + 1;
                > src => u _ m - 1;
                ENDCASE => RETURN [h[m].proc];
            ENDLOOP;
        -- By Knuth 6.2.1, exercise 1, source[u] < src < source[l] (if unique keys)
        RETURN [IF u = -1 THEN "<anon>" ELSE h[u].proc]
        END;

    Create: PUBLIC PROC [module: ROPE] RETURNS [h: Handle] = TRUSTED {
        sth: RTSymbolDefs.SymbolTableHandle _ RTSymbolDefs.nullHandle;
        rstb: RTSymbolDefs.SymbolTableBase;
        stb: SymbolTable.Base;
        sth _ RTSymbols.GetSTHForModule[
            stamp: BcdDefs.NullVersion,
            fileName: module,
            moduleName: NIL ! AMTypes.Error => CONTINUE];
        IF sth = RTSymbolDefs.nullHandle THEN RETURN [NIL];
        rstb _ RTSymbols.AcquireSTB[sth];
        WITH rstb SELECT FROM
            x => stb _ e;
            y => stb _ e;
            ENDCASE;
        h _ ProduceSourceMap[stb ! UNWIND => RTSymbols.ReleaseSTB[rstb]];
        RTSymbols.ReleaseSTB[rstb];
        };

    ProduceSourceMap: PUBLIC PROC[stb: SymbolTable.Base] RETURNS[h: Handle] = TRUSTED {
        DigestFGT: PROC = TRUSTED {
            bti: BTIndex;
            proc: ROPE;
            n: CARDINAL _ 0;

            AddMyEntry: PROC [source: INT] = TRUSTED {
                IF n = h.maxLength THEN {
                    oldFGT: Handle _ h;
                    myFGTSize: CARDINAL _ myFGTSize + myFGTSize/2 + 16;
                    h _ NEW[Object[myFGTSize]];
                    IF oldFGT # NIL THEN
                        FOR i: NAT IN [0..oldFGT.maxLength) DO
                            h[i] _ oldFGT[i] ENDLOOP;
                    };
                h[n] _ [firstSource: source, proc: proc];
                h.length _ n _ n + 1;
                };
            AddBodyFGT: PROC [bti: Symbols.CBTIndex] = TRUSTED {
                info: BodyInfo[External] = NARROW[stb.bb[bti].info, BodyInfo[External]];
                fgLast: CARDINAL = info.startIndex + info.indexLength - 1;
                lastSource: INT _ stb.bb[bti].sourceIndex;
                FOR i: CARDINAL IN [info.startIndex..fgLast] DO
                    f: FGTEntry = stb.fgTable[i];
                    WITH f SELECT FROM
                        normal => {
                            lastSource _ lastSource + deltaSource;
                            AddMyEntry[lastSource]};
                        step =>
                            IF which = $source THEN lastSource _ lastSource + delta;
                        ENDCASE;
                    ENDLOOP;
                };
            Sort: PROC = TRUSTED {
                i: CARDINAL;
                temp: Item;

                SiftUp: PROC [l, u: CARDINAL] = TRUSTED {
                    s: CARDINAL;
                    key: Item _ h[l-1];
                    DO
                        s _ l*2;
                        IF s > u THEN EXIT;
                        IF s < u AND h[s+1-1].firstSource > h[s-1].firstSource THEN s _ s+1;
                        IF key.firstSource > h[s-1].firstSource THEN EXIT;
                        h[l-1] _ h[s-1];
                        l _ s;
                        ENDLOOP;
                    h[l-1] _ key};

                FOR i DECREASING IN [2..n/2] DO SiftUp[i, n]; ENDLOOP;
                FOR i DECREASING IN [2..n] DO
                    SiftUp[1, i];
                    temp _ h[1-1];
                    h[1-1] _ h[i-1];
                    h[i-1] _ temp;
                    ENDLOOP;
                }; -- end of Sort procedure

            h _ NEW[Object[stb.fgTable.LENGTH + 1]]; -- probably big enough
            bti _ BTIndex.FIRST; proc _ NIL;
            IF stb.bb[bti].sourceIndex # 0 THEN 
                AddMyEntry[source: 0];
            DO
                WITH stb.bb[bti] SELECT FROM
                    Callable => IF ~inline THEN {
                        cbti: CBTIndex = LOOPHOLE[bti];
                        proc _ BodyName[cbti];
                        AddBodyFGT[cbti]};
                    ENDCASE;
                IF stb.bb[bti].firstSon # BTNull
                    THEN bti _ stb.bb[bti].firstSon
                    ELSE DO
                        prev: BTIndex _ bti;
                        bti _ stb.bb[bti].link.index;
                        IF bti = BTNull THEN GO TO Done;
                        IF stb.bb[prev].link.which # $parent THEN EXIT;
                        ENDLOOP;
                REPEAT Done => NULL;
                ENDLOOP;
            Sort[];
            };

        BodyName: PROC[bti: Symbols.CBTIndex] RETURNS[ROPE] = TRUSTED {
            sei: ISEIndex = stb.bb[bti].id;
            hti: HTIndex;
            IF sei = Symbols.SENull OR (hti _ stb.seb[sei].hash) = HTNull THEN RETURN["<anon>"]
            ELSE TRUSTED {
                ss: SubString = stb.SubStringForName[hti];
                rt: REF TEXT = NEW[TEXT[ss.length]];
                ConvertUnsafe.AppendSubStringToRefText[to: rt, from: ss];
                RETURN[Rope.FromRefText[rt]];
                };
            };
        <<Executable part of SearchForLog.>>

        IF stb.stHandle.definitionsFile THEN RETURN [NIL];
        DigestFGT[];
        };

    END.