
    <<EditSpanImpl.mesa>>
        <<Copyright © 1985, 1986 by Xerox Corporation.  All rights reserved.>>
        <<written by Bill Paxton, June 1981>>
        <<last edit by Bill Paxton, December 23, 1982 2:47 pm>>
        <<Last Edited by: Maxwell, January 5, 1983 12:46 pm>>
        <<Last Edited by: Paul Rovner, August 10, 1983 4:25 pm>>
        <<Michael Plass, May 9, 1986 12:03:23 pm PDT>>
        <<Doug Wyatt, September 16, 1986 6:36:17 pm PDT>>
    <<>>
    DIRECTORY
    Tioga,
    TiogaPrivate;

    EditSpanImpl: CEDAR PROGRAM 
    IMPORTS Tioga, TiogaPrivate
    EXPORTS Tioga
    = BEGIN OPEN TiogaPrivate, Tioga;

    World: TYPE ~ TiogaPrivate.World;
    WorldRep: PUBLIC TYPE ~ TiogaPrivate.WorldRep;
<<INLINEs>>
    TextFromSpan: PROC [span: Span] RETURNS [Text] ~ INLINE {
        RETURN[[span.start.node, span.start.where, span.end.where-span.start.where]];
        };

    SpanFromText: PROC [text: Text] RETURNS [Span] ~ INLINE {
        RETURN[[[text.node, text.start], [text.node, text.start+text.len]]];
        };

    TextLoc: PROC [loc: Location] RETURNS [BOOL] ~ INLINE {
        RETURN [loc.where#nodeItself];
        };

    TextSpan: PROC [span: Span] RETURNS [BOOL] ~ INLINE {
        RETURN [span.start.node=span.end.node AND TextLoc[span.start] AND TextLoc[span.end]];
        };

    CheckForNil: PROC [span: Span] RETURNS [BOOL] = INLINE {
        RETURN [span.start.node = NIL OR span.end.node = NIL] 
        };

    NodeLoc: PROC [node: Node] RETURNS [Location] ~ INLINE {
        RETURN[[node, nodeItself]];
        };

    NodeSpan: PROC [node1, node2: Node] RETURNS [Span] ~ INLINE {
        RETURN[[NodeLoc[node1], NodeLoc[node2]]];
        };

    WholeNodeLoc: PROC [loc: Location] RETURNS [Location] ~ INLINE {
        RETURN[NodeLoc[loc.node]];
        };

    WholeNodeSpan: PROC [span: Span] RETURNS [Span] ~ INLINE {
        RETURN[[NodeLoc[span.start.node], NodeLoc[span.end.node]]];
        };

    Nest: PROC [world: World, root: Node, span: Span] RETURNS [Span] ~ INLINE {
        RETURN ChangeNesting[world, root, span, +1];
        };

    UnNest: PROC [world: World, root: Node, span: Span] RETURNS [Span] ~ INLINE {
        RETURN ChangeNesting[world, root, span, -1];
        };

<<Paste Span>>
    SaveForPaste: PUBLIC PROC [world: World, span: Span] = {
        IF CheckForNil[span] THEN RETURN;
        IF TextSpan[span] THEN SaveTextForPaste[world, TextFromSpan[span]] 
        ELSE SaveSpanForPaste[world, CopySpan[span]] 
        };

    SaveTextForPaste: PROC [world: World, text: Text] = {
        span: Span ~ IF text.len=0 THEN nullSpan ELSE SpanFromText[text];
        SaveSpanForPaste[world, CopySpan[span]];
        };

    SaveSpanForPaste: PROC [world: World, span: Span] = {
        SaveOldPaste[world];
        world.paste _ NEW[Change.ChangingSpanForPaste _ [ChangingSpanForPaste[span]]];
        };

    SaveOldPaste: PROC [world: World] = {
        NoteEvent[world, RestorePaste, world.paste];
        world.paste _ NIL 
        };

    RestorePaste: PROC [world: World, undoRef: REF Change] = {
        SaveOldPaste[world];
        world.paste _ NARROW[undoRef] 
        };

    SavedForPaste: PUBLIC PROC [world: World] RETURNS [span: Span] = {
        savedPaste: REF Change _ world.paste;
        IF savedPaste=NIL THEN RETURN [nullSpan];
        WITH savedPaste SELECT FROM
            x: REF Change.ChangingSpanForPaste => RETURN [x.span];
            ENDCASE => ERROR;
        };

<<Editing operations on spans>>
    CannotDoEdit: PUBLIC ERROR ~ CODE;


    Replace: PUBLIC PROC [world: World, destRoot, sourceRoot: Node, dest, source: Span, saveForPaste: BOOL _ TRUE] RETURNS [Span] = {
        <<replace dest span by copy of source span>>
        <<result is the new copy of source>>
        IF TextSpan[dest] AND TextSpan[source] THEN { -- pure text replace
            destText: Text ~ TextFromSpan[dest];
            sourceText: Text ~ TextFromSpan[source];
            IF saveForPaste THEN SaveTextForPaste[world, destText];
            RETURN [SpanFromText[ReplaceText[world, destRoot, sourceRoot, destText, sourceText]]];
            }
        ELSE {
            result, newDest: Span;
            source _ CopySpan[source];
            sourceRoot _ Root[source.start.node];
            sourceRoot.deleted _ TRUE;
            [result, newDest] _ Transpose[world, sourceRoot, destRoot, source, dest];
            IF saveForPaste THEN SaveSpanForPaste[world, newDest];
            RETURN[result];
            };
        };

    Delete: PUBLIC PROC [world: World, root: Node, del: Span, saveForPaste: BOOL _ TRUE] = {
        IF CheckForNil[del] THEN RETURN;
        IF TextSpan[del] THEN { -- pure text
            delText: Text ~ TextFromSpan[del];
            IF saveForPaste THEN SaveTextForPaste[world, delText];
            DeleteText[world, root, delText];
            }
        ELSE {
            d: Span ~ MoveToLimbo[world, root, del];
            IF saveForPaste THEN SaveSpanForPaste[world, d] 
            };
        };

    MoveToLimbo: PROC [world: World, root: Node, span: Span] RETURNS [result: Span] = {
        RETURN [Move[world, NIL, root, nullLocation, span, after, 1]] 
        };

    Copy: PUBLIC PROC [world: World, destRoot, sourceRoot: Node, dest: Location, source: Span, where: Place _ after, nesting: INT _ 0] 
    RETURNS [result: Span] = {
        <<result is the new copy of source>>
        IF CheckForNil[source] OR dest.node=NIL THEN RETURN [nullSpan];
        IF TextLoc[dest] AND TextSpan[source] THEN { -- pure text copy
            sourceText: Text ~ TextFromSpan[source];
            RETURN[SpanFromText[CopyText[world, destRoot, sourceRoot, dest, sourceText]]];
            }
        ELSE {
            source _ CopySpan[source];
            sourceRoot _ Root[source.start.node];
            sourceRoot.deleted _ TRUE;
            result _ Move[world, destRoot, sourceRoot, dest, source, where, nesting];
            };
        };

    Move: PUBLIC PROC [world: World, destRoot, sourceRoot: Node, dest: Location, source: Span, where: Place _ after, nesting: INT _ 0] 
    RETURNS [result: Span] = {
        <<dest cannot be within source>>
        <<result is moved span>>
        sBefore, sAfter, sTop, sBottom, dBefore, dAfter: Slice;
        sNesting, dNesting: INT;
        sDepth: NAT;
        beforeSource, afterSource: Node; -- nodes adjacent to source after do splits
        afterLoc: Location;

        FreeSlices: PROC = {
            FreeSlice[sBefore]; FreeSlice[sAfter]; FreeSlice[sTop]; FreeSlice[sBottom]; 
            FreeSlice[dBefore]; FreeSlice[dAfter];
            sBefore _ sAfter _ sTop _ sBottom _ dBefore _ dAfter _ NIL 
            }; 

        ForcedUnNest: PROC [afterNode: Node] = {
            span: Span = NodeSpan[afterNode, LastWithin[afterNode]];
            FreeSlices[];
            [] _ UnNest[world, Root[afterNode], span] 
            };

        ForcedNest: PROC = {
            span: Span _ NodeSpan[sTop[sDepth], LastWithin[sBottom[sDepth]]];
            IF SliceLength[sTop] = sDepth+1 THEN { -- can't do it by calling Nest
                IF nesting >= 1 THEN ERROR;
                nesting _ nesting+1; -- move to a deeper position
                FreeSlices[];
                RETURN 
                };
            FreeSlices[];
            [] _ Nest[world, Root[span.start.node], span] 
            };

        IF CheckForNil[source] THEN RETURN [nullSpan];

        IF TextLoc[dest] AND TextSpan[source] THEN { -- pure text move
            sourceText: Text ~ TextFromSpan[source];
            RETURN[SpanFromText[MoveText[world, destRoot, sourceRoot, dest, sourceText]]];
            };

        IF where=child THEN { where _ after; nesting _ nesting+1 }
        ELSE IF where=sibling THEN {
            newDest: Node = LastWithin[dest.node];
            where _ after;
            nesting _ nesting + Level[dest.node] - Level[newDest];
            dest _ [newDest, nodeItself];
            };

        <<split source and dest, if necessary, so can deal with entire nodes>>
        [dest, source, where, nesting] _ DoSplits2[world, dest, source, where, nesting];
        beforeSource _ StepBackward[source.start.node];
        afterSource _ StepForward[source.end.node];
        afterLoc _ [afterSource, 0];

        { -- for exits
            <<check for dest already in correct position>>
            IF dest # nullLocation AND
            ((where = after AND (dest.node = beforeSource OR dest.node = source.end.node))
                OR (where = before AND (dest.node = afterSource OR dest.node = source.start.node)))
            THEN { -- not going anywhere, but might be changing nesting
                IF nesting > 0 THEN
                FOR i:INT IN [0..nesting) DO
                    [] _ Nest[world, sourceRoot, WholeNodeSpan[source]];
                    ENDLOOP
                ELSE IF nesting < 0 THEN
                FOR i:INT IN [nesting..0) DO
                    [] _ UnNest[world, sourceRoot, WholeNodeSpan[source]];
                    ENDLOOP 
                }
            ELSE     DO -- repeat this loop only if have forced nest or unnest or source and dest in same tree
                <<check for dest inside source>>
                [sBefore, sAfter, sTop, sBottom, sNesting, sDepth] _
                    DescribeBand[source.start.node, source.end.node ! BadBand =>
                    { source _ nullSpan; GOTO ErrorReturn } ];
                IF dest = nullLocation THEN { -- moving to limbo
                    dest _ CreateDest[SliceLength[sTop]-sDepth];
                    destRoot _ Root[dest.node];
                    destRoot.deleted _ TRUE; -- so will free this when it falls off the edit history list
                    where _ after; nesting _ 1 
                    };
                [dBefore, dAfter, dNesting] _ DestSlices[dest.node, where];
                IF CompareSliceOrder[dBefore, sBefore]=after AND 
                CompareSliceOrder[dBefore, sBottom]=before THEN GOTO ErrorReturn;
                <<dest inside source>>
                IF dBefore[0] = sBefore[0] THEN { -- source and dest in same tree
                    span: Span = NodeSpan[source.start.node, source.end.node];
                    FreeSlices[];
                    [] _ MoveToLimbo[world, sourceRoot, span];
                    LOOP 
                    };
                dNesting _ dNesting + nesting;
                SELECT NeedNestingChange[dBefore, dAfter, sTop, sBottom, dNesting, sDepth] FROM
                    needUnNest => { ForcedUnNest[LastOfSlice[dAfter]]; LOOP };
                    needNest => { ForcedNest[]; LOOP };
                    ENDCASE;
                IF SliceLength[sAfter] > SliceLength[sBefore]+1 THEN {
                    ForcedUnNest[LastOfSlice[sAfter]]; LOOP 
                    }
                ELSE { -- do it
                    notify: REF MovingNodes Change;
                    notify _ NEW[MovingNodes Change _ [MovingNodes[
                        destRoot, sourceRoot, dest.node, source.start.node, source.end.node, 
                        LastOfSlice[sBefore], sNesting, (where # before)]]];
                    EditNotify[world, notify, before];
                    DeletePrefix[sTop, sDepth]; DeletePrefix[sBottom, sDepth];
                    ReplaceBand[dBefore, dAfter, sTop, sBottom, dNesting];
                    Splice[sBefore, sAfter];
                    FreeSlices[];
                    EditNotify[world, notify, after];
                    NoteEvent[world, UndoMoveNodes, notify];
                    };
                EXIT;
                ENDLOOP;

            IF TextLoc[dest] THEN { -- undo prior splits
                start, end: BOOL _ FALSE;
                IF TextLoc[source.start] THEN { -- merge start of source with front of dest
                    start _ TRUE;
                    [source, ] _ ReMerge[world, source, nullSpan, source.start.node] 
                    };
                IF TextLoc[source.end] THEN { -- merge end of source with tail of dest
                    end _ TRUE;
                    [source, ] _ ReMerge[world, source, nullSpan, source.end.node, TRUE] 
                    };
                IF start AND end THEN { -- merge before source with after source
                    afterLoc _ Merge[world, Root[afterSource], afterSource] 
                    }
                }
            ELSE IF TextLoc[source.start] AND TextLoc[source.end] THEN {
                afterLoc _ Merge[world, Root[afterSource], afterSource] 
                };

            world.afterMoved2 _ world.afterMoved1; -- save previous hint
            world.afterMoved1 _ IF afterSource=NIL THEN [beforeSource, 0] ELSE afterLoc; -- hint for repaint

            RETURN [source];

            EXITS ErrorReturn => {
                FreeSlices[];
                [, source] _ UndoSplits2[world, dest, source];
                ERROR CannotDoEdit 
                }
            }
        };

    UndoMoveNodes: PROC [world: World, undoRef: REF Change] = {
        WITH undoRef SELECT FROM
            x: REF Change.MovingNodes => [] _ Move[world, x.sourceRoot, x.destRoot, NodeLoc[x.pred], NodeSpan[x.first, x.last], after, 
            x.nesting];
            ENDCASE => ERROR 
        };

    Transpose: PUBLIC PROC [world: World, alphaRoot, betaRoot: Node, alpha, beta: Span] RETURNS [newAlpha, newBeta: Span] = {
        <<newAlpha is new location of alpha span; ditto for newBeta>>

        aBefore, aAfter, aTop, aBottom, bBefore, bAfter, bTop, bBottom: Slice;
        aNesting, bNesting: INT;
        aDepth, bDepth: NAT;
        beforeAlpha, afterAlpha, beforeBeta, afterBeta: Node; -- nodes adjacent after do splits
        afterAlphaLoc, afterBetaLoc: Location;

        FreeSlices: PROC = {
            FreeSlice[aBefore]; FreeSlice[aAfter]; FreeSlice[aTop]; FreeSlice[aBottom]; 
            FreeSlice[bBefore]; FreeSlice[bAfter]; FreeSlice[bTop]; FreeSlice[bBottom];
            aBefore _ aAfter _ aTop _ aBottom _ bBefore _ bAfter _ bTop _ bBottom _ NIL 
            }; 

        { -- for exit

            IF CheckForNil[alpha] OR CheckForNil[beta] THEN RETURN [nullSpan, nullSpan];

            IF TextSpan[alpha] AND TextSpan[beta] THEN { -- pure text transpose
                alphaText: Text ~ TextFromSpan[alpha];
                betaText: Text ~ TextFromSpan[beta];
                alphaResultText, betaResultText: Text;
                [alphaResultText, betaResultText] _ TransposeText[world, alphaRoot, betaRoot, alphaText, betaText];
                newAlpha _ SpanFromText[alphaResultText];
                newBeta _ SpanFromText[betaResultText];
                RETURN;
                };

            [alpha, beta] _ DoSplits[world, alpha, beta]; -- so can deal with entire nodes

            beforeAlpha _ StepBackward[alpha.start.node];
            afterAlpha _ StepForward[alpha.end.node];
            afterAlphaLoc _ [afterAlpha, 0];
            beforeBeta _ StepBackward[beta.start.node];
            afterBeta _ StepForward[beta.end.node];
            afterBetaLoc _ [afterBeta, 0];


            <<now check for alpha beta adjacent or overlapping as special cases>>
            IF afterAlpha = beta.start.node THEN { -- alpha just before beta
                <<move beta nodes to before alpha nodes>>
                [] _ Move[world, alphaRoot, betaRoot, WholeNodeLoc[alpha.start], WholeNodeSpan[beta], before, 0] 
                }
            ELSE IF afterBeta = alpha.start.node THEN { -- beta just before alpha
                <<move alpha nodes to before beta nodes>>
                [] _ Move[world, betaRoot, alphaRoot, WholeNodeLoc[beta.start], WholeNodeSpan[alpha], before, 0] 
                }
            ELSE     { -- get slices describing the bands of nodes to be transposed
                overlap: BOOL;
                head, tail: Span; -- sections of alpha or beta before and after the overlap
                startOrder, endOrder: Order;
                [aBefore, aAfter, aTop, aBottom, aNesting, aDepth] _
                    DescribeBand[alpha.start.node, alpha.end.node !  BadBand =>
                    { alpha _ beta _ nullSpan; GOTO ErrorReturn }];
                [bBefore, bAfter, bTop, bBottom, bNesting, bDepth] _
                    DescribeBand[beta.start.node, beta.end.node ! BadBand =>
                    { alpha _ beta _ nullSpan; GOTO ErrorReturn }];
                <<check for overlap>>
                [overlap, head, tail, startOrder, endOrder] _
                    SliceOrder[alpha, beta, aBefore, aBottom, bBefore, bBottom];
                IF overlap THEN { -- bands overlap
                    FreeSlices[];
                    IF head = nullSpan AND tail = nullSpan THEN NULL
                    ELSE IF head = nullSpan THEN { --move tail to before alphastart
                        [] _ Move[world, alphaRoot, betaRoot, WholeNodeLoc[alpha.start], WholeNodeSpan[tail], before, 0];
                        IF endOrder=before THEN { -- alpha end before beta end
                            beta.start _ tail.start; beta.end _ alpha.end 
                            }
                        ELSE { -- beta end before alpha end
                            alpha.start _ tail.start; alpha.end _ beta.end 
                            }
                        }
                    ELSE IF tail = nullSpan THEN { --move head to after alphaend
                        [] _ Move[world, alphaRoot, betaRoot, WholeNodeLoc[alpha.end], WholeNodeSpan[head], after, 0];
                        IF startOrder=before THEN { -- alpha start before beta start
                            alpha.start _ beta.start; alpha.end _ head.end 
                            }
                        ELSE { -- beta start before alpha start
                            beta.start _ alpha.start; beta.end _ head.end 
                            }
                        }
                    ELSE IF startOrder # endOrder THEN NULL -- one contained in the other
                    ELSE {    --transpose head and tail
                        [] _ Transpose[world, alphaRoot, betaRoot, WholeNodeSpan[head], WholeNodeSpan[tail]];
                        IF startOrder=before THEN { -- alpha start before beta start
                            alpha.start _ beta.start; alpha.end _ head.end;
                            beta.start _ tail.start; beta.end _ alpha.end 
                            }
                        ELSE { -- beta start before alpha start
                            beta.start _ alpha.start; beta.end _ head.end;
                            alpha.start _ tail.start; alpha.end _ beta.end 
                            }
                        }
                    }
                ELSE { -- do transpose as two moves
                    aSpan, bSpan: Span;
                    after1, after2: Location;
                    bLoc: Location _ NodeLoc[LastOfSlice[bBefore]];
                    aLoc: Location _ NodeLoc[LastOfSlice[aBefore]];
                    FreeSlices[];
                    aSpan _ NodeSpan[alpha.start.node, alpha.end.node];
                    bSpan _ NodeSpan[beta.start.node, beta.end.node];
                    [] _ MoveToLimbo[world, alphaRoot, aSpan]; after1 _ world.afterMoved1;
                    [] _ MoveToLimbo[world, betaRoot, bSpan]; after2 _ world.afterMoved1;
                    [] _ Move[world, betaRoot, Root[aSpan.start.node], bLoc, aSpan, after, bNesting];
                    [] _ Move[world, alphaRoot, Root[bSpan.start.node], aLoc, bSpan, after, aNesting];
                    world.afterMoved1 _ after1; world.afterMoved2 _ after2 
                    }
                };

            IF TextLoc[alpha.start] AND TextLoc[beta.start] THEN { -- remerge starts
                [alpha, beta] _ ReMerge[world, alpha, beta, alpha.start.node];
                [alpha, beta] _ ReMerge[world, alpha, beta, beta.start.node] 
                };
            IF TextLoc[alpha.end] AND TextLoc[beta.end] THEN { -- remerge ends
                [alpha, beta] _ ReMerge[world, alpha, beta, alpha.end.node, TRUE];
                [alpha, beta] _ ReMerge[world, alpha, beta, beta.end.node, TRUE];
                afterAlphaLoc _ beta.end; afterBetaLoc _ alpha.end 
                };

            world.afterMoved1 _ IF afterAlphaLoc.node=NIL THEN [beforeAlpha, 0] ELSE afterAlphaLoc; -- hint for repaint
            world.afterMoved2 _ IF afterBetaLoc.node=NIL THEN [beforeBeta, 0] ELSE afterBetaLoc;

            RETURN [alpha, beta];    

            EXITS ErrorReturn => {
                FreeSlices[]; [alpha, beta] _ UndoSplits[world, alpha, beta];
                ERROR CannotDoEdit 
                }
            }
        };

    MoveOnto: PUBLIC PROC [world: World, destRoot, sourceRoot: Node, dest, source: Span, saveForPaste: BOOL _ TRUE] RETURNS [result: 
    Span] = {
        <<like Replace, but moves source instead of copying it>>
        <<result is moved span>>
        overlap: BOOL;
        head, tail, newDest: Span; -- sections of alpha or beta before and after the overlap
        startOrder, endOrder: Order;
        aBefore, aAfter, aTop, aBottom, bBefore, bAfter, bTop, bBottom: Slice;
        aNesting, bNesting: INT;
        aDepth, bDepth: NAT;

        FreeSlices: PROC = {
            FreeSlice[aBefore]; FreeSlice[aAfter]; FreeSlice[aTop]; FreeSlice[aBottom]; 
            FreeSlice[bBefore]; FreeSlice[bAfter]; FreeSlice[bTop]; FreeSlice[bBottom];
            aBefore _ aAfter _ aTop _ aBottom _ bBefore _ bAfter _ bTop _ bBottom _ NIL 
            }; 

        { -- for exit

            IF CheckForNil[source] OR CheckForNil[dest] THEN RETURN [nullSpan];

            IF TextSpan[dest] AND TextSpan[source] THEN { -- pure text move
                destText: Text ~ TextFromSpan[dest];
                sourceText: Text ~ TextFromSpan[source];
                IF saveForPaste THEN SaveTextForPaste[world, destText];
                RETURN [SpanFromText[MoveTextOnto[world, destRoot, sourceRoot, destText, sourceText]]];
                };

            [dest, source] _ DoSplits[world, dest, source];

            [aBefore, aAfter, aTop, aBottom, aNesting, aDepth] _
                DescribeBand[dest.start.node, dest.end.node !  BadBand =>
                { dest _ source _ nullSpan; GOTO ErrorReturn }];
            [bBefore, bAfter, bTop, bBottom, bNesting, bDepth] _
                DescribeBand[source.start.node, source.end.node ! BadBand =>
                { dest _ source _ nullSpan; GOTO ErrorReturn }];

            <<get slices for dest and source>>
            [overlap, head, tail, startOrder, endOrder] _
                SliceOrder[dest, source, aBefore, aBottom, bBefore, bBottom];
            FreeSlices[];

            <<check for overlap>>
            IF overlap THEN { -- bands overlap. modify dest so doesn't overlap
                IF head = nullSpan AND tail = nullSpan THEN GOTO ErrorReturn;
                IF head = nullSpan THEN { -- source start = dest start
                    IF endOrder=before THEN GOTO ErrorReturn -- dest end before source end
                    ELSE dest.start _ tail.start 
                    }
                ELSE IF tail = nullSpan THEN { --source end = dest end
                    IF startOrder=before THEN
                    dest.end _ head.end -- dest start before source start
                        ELSE GOTO ErrorReturn 
                    } -- source start before dest start
                ELSE { -- have both head and tail
                    IF startOrder=before AND endOrder=after THEN {
                        [] _ Delete[world, destRoot, tail]; dest.end _ head.end 
                        }
                    ELSE IF startOrder=before THEN dest.end _ head.end
                        ELSE IF endOrder=after THEN dest.start _ tail.start
                        ELSE GOTO ErrorReturn 
                    }
                };

            [dest, source] _ UndoSplits[world, dest, source];
            source _ MoveToLimbo[world, sourceRoot, source];
            sourceRoot _ Root[source.start.node];
            [result, newDest] _ Transpose[world, sourceRoot, destRoot, source, dest];
            IF saveForPaste THEN SaveSpanForPaste[world, newDest];
            RETURN;

            EXITS ErrorReturn => {
                [dest, source] _ UndoSplits[world, dest, source]; ERROR CannotDoEdit 
                }
            }
        };

<<Nesting>>
    ChangeNesting: PUBLIC PROC [world: World, root: Node, span: Span, change: INT] RETURNS [new: Span] = {
        <<moves span to a deeper nesting level in tree>>
        before, after, top, bottom: Slice;
        nesting: INT;
        depth: NAT;

        FreeSlices: PROC = {
            FreeSlice[before]; FreeSlice[after]; FreeSlice[top]; FreeSlice[bottom]; 
            before _ after _ top _ bottom _ NIL 
            }; 

        { -- for exit

            IF CheckForNil[span] THEN RETURN [nullSpan];

            [span, ] _ DoSplits[world, span, nullSpan]; -- so can deal with entire nodes

            DO -- only repeat this loop if have forced nest/unnest
                [before, after, top, bottom, nesting, depth] _
                    DescribeBand[span.start.node, span.end.node ! BadBand =>
                    { span _ nullSpan; GOTO ErrorReturn } ];
                IF nesting+change > 1 THEN GOTO ErrorReturn; -- cannot do it
                SELECT NeedNestingChange[before, after, top, bottom, nesting+change, depth] FROM
                    needUnNest => {
                        afterNode: Node = LastOfSlice[after];
                        span: Span = NodeSpan[afterNode, LastWithin[afterNode]];
                        FreeSlices[];
                        [] _ UnNest[world, root, span];
                        LOOP 
                        };
                    needNest => {
                        span: Span = NodeSpan[top[depth], LastWithin[bottom[depth]]];
                        IF SliceLength[top] = depth+1 THEN GOTO ErrorReturn;
                        FreeSlices[];
                        [] _ Nest[world, root, span];
                        LOOP;
                        };
                    ENDCASE => { -- do it
                        notify: REF NodeNesting Change;
                        notify _ NEW[NodeNesting Change _ [NodeNesting[
                            root, span.start.node, span.end.node, change]]];
                        EditNotify[world, notify, before];
                        DeletePrefix[top, depth];
                        DeletePrefix[bottom, depth];
                        ReplaceBand[before, after, top, bottom, nesting+change];
                        FreeSlices[];
                        EditNotify[world, notify, after];
                        NoteEvent[world, UndoChangeNesting, notify] 
                        };
                EXIT;
                ENDLOOP;

            RETURN [span];

            EXITS ErrorReturn => {
                FreeSlices[]; [span, ] _ UndoSplits[world, span, nullSpan]; ERROR CannotDoEdit 
                }
            }
        };

    UndoChangeNesting: PROC [world: World, undoRef: REF Change] = {
        WITH undoRef SELECT FROM
            x: REF Change.NodeNesting => [] _ ChangeNesting[world, x.root, NodeSpan[x.first, x.last], -x.change];
            ENDCASE => ERROR;
        };

<<New nodes; split & merge>>
    Insert: PUBLIC PROC [world: World, root, old: Node, where: Place _ after, inherit: BOOL _ TRUE] RETURNS [new: Node] = {
        <<empty copy of old node is inserted in tree in position determined by "where">>
        IF old=NIL THEN RETURN [NIL];
        new _ NewNode[];
        IF inherit THEN Inherit[old, new];
        DoInsertNode[world, root, old, new, where] 
        };

    Inherit: PUBLIC PROC [old, new: Node, allprops: BOOL _ FALSE] = {
        Copy: PROC [name: ATOM, value: REF] RETURNS [BOOL] = {
            IF allprops OR Is[name, $Inheritable] THEN {
                newvalue: REF ~ CopyProp[name, value];
                IF newvalue # NIL THEN PutProp[new, name, newvalue];
                };
            RETURN [FALSE];
            };
        new.formatName _ old.formatName;
        new.comment _ old.comment;
        IF allprops OR old.hasprefix OR old.haspostfix OR old.hasstyledef THEN
            [] _ MapProps[old, Copy, FALSE, FALSE];
        };

    DoInsertNode: PROC [world: World, root, old, new: Node, where: Place] = {
        dest, parent: Node;
        child: BOOL;
        notify: REF InsertingNode Change;
        IF new = NIL OR old = NIL THEN RETURN;
        parent _ IF where = child THEN old ELSE Parent[old];
        IF where = sibling THEN { dest _ LastWithin[old]; child _ FALSE }
        ELSE IF where = after THEN { dest _ old; child _ FALSE }
        ELSE IF where = child THEN { dest _ old; child _ TRUE }
        ELSE {
            IF parent.child = old THEN { dest _ parent; child _ TRUE }
            ELSE { dest _ LastWithin[Previous[old, parent]]; child _ FALSE }
            };
        notify _ NEW[InsertingNode Change _ [InsertingNode[root, new, dest]]];
        EditNotify[world, notify, before];
        IF child THEN { -- insert as first child of dest
            IF dest.child # NIL THEN { new.next _ dest.child; new.last _ FALSE }
            ELSE { new.next _ dest; new.last _ TRUE };
            dest.child _ new 
            }
        ELSE IF where = sibling THEN { -- insert as next sibling of old; don't adopt children
            new.next _ old.next; new.last _ old.last;
            old.last _ FALSE; old.next _ new 
            }
        ELSE { -- insert as next sibling of dest
            new.next _ dest.next; new.last _ dest.last;
            dest.last _ FALSE; dest.next _ new;
            IF where = after AND (new.child _ dest.child) # NIL THEN { -- adopt dest's children
                LastSibling[new.child].next _ new;
                dest.child _ NIL 
                }
            };
        EditNotify[world, notify, after];
        NoteEvent[world, UndoInsertNode, notify] 
        };

    UndoInsertNode: PROC [world: World, undoRef: REF Change] = {
        WITH undoRef SELECT FROM
            x: REF Change.InsertingNode => [] _ Delete[world, x.root, NodeSpan[x.new, x.new]];
            ENDCASE => ERROR 
        };

    Split: PUBLIC PROC [world: World, root: Node, loc: Location] RETURNS [new: Node] = {
        <<inserts copy of loc.node directly after loc.node (as sibling)>>
        <<new adopts children of old (if any)>>
        <<if loc.where # nodeItself and loc.node is a text node, then>>
            <<text after loc.where moves to new node>>
            <<text before loc.where stays in old node>>
        <<returns the new node>>
        IF loc.node=NIL THEN RETURN [NIL];
        new _ Insert[world, root, loc.node, after];
        IF TextLoc[loc] THEN {
            [] _ MoveText[world, root, root, [new, 0], [loc.node, loc.where, maxLen]];
            }
        };

    Merge: PUBLIC PROC [world: World, root, node: Node] RETURNS [loc: Location] = {
        <<copies text of node to end of previous node>>
        <<then deletes node>>
        <<returns location of join in the merged node>>
        <<>>
        pred: Node ~ StepBackward[node];
        IF pred=NIL OR Parent[pred]=NIL OR node=NIL THEN ERROR CannotDoEdit
        ELSE {
            result: Text ~ CopyText[world, root, root, [pred, maxLen], [node, 0, maxLen]];
            [] _ Delete[world, root, NodeSpan[node, node]];
            RETURN [[result.node, result.start]];
            };
        };

<<Change looks>>
    ChangeLooks: PUBLIC PROC [world: World, root: Node, span: Span, remove, add: Looks] = {
        DoChange: PROC [node: Node, start, len: INT] RETURNS [stop: BOOL] = {
            ChangeTextLooks[world, root, [node, start, len], remove, add]; RETURN [FALSE] 
            };
        ApplyToSpan[span, DoChange];
        };

<<Caps and Lowercase>>
    ChangeCaps: PUBLIC PROC [world: World, root: Node, span: Span, how: CapChange _ allCaps] = {
        DoChange: PROC [node: Node, start, len: INT] RETURNS [stop: BOOL] = {
            ChangeTextCaps[world, root, [node, start, len], how]; RETURN [FALSE] 
            };
        IF CheckForNil[span] THEN RETURN;
        ApplyToSpan[span, DoChange];
        };


    END.