<<>>
    <<EditSpanImpl.mesa>>
        <<Copyright Ó 1985, 1986, 1987, 1988, 1991, 1992 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>>
        <<Bier, January 6, 1989 2:23:06 pm PST>>
        <<Michael Plass, October 15, 1987 3:41:49 pm PDT>>
        <<Doug Wyatt, February 26, 1992 12:48 pm PST>>
        <<>>
    DIRECTORY
        EditNotify USING [Change, Notify], 
        EditSpan USING [Nest, UnNest], 
        EditSpanSupport USING [AdoptChildren, Apply, BadBand, CompareSliceOrder, CopySpan, CreateDest, DeletePrefix, DescribeBand, 
        DestSlices, DoSplits, DoSplits2, FreeSlice, LastOfSlice, NeedNestingChange, NodeLoc, NodeSpan, ReMerge, ReplaceBand, Slice, 
        SliceLength, SliceOrder, Splice, UndoSplits, UndoSplits2],
        NodeProps USING [CopyInfo, Is, MapProps, PutProp], 
        TextEdit USING [ChangeCaps, ChangeLooks, CopyText, DeleteText, DestSpanProc, MoveText, MoveTextOnto, ReplaceText, TransposeProc, 
        TransposeText, TwoSpanProc], 
        TextNode USING [LastWithin, Level, MakeNodeLoc, MakeNodeSpan, NewTextNode, Parent, Previous, Root, StepBackward, StepForward], 
        Tioga USING [CapChange, Location, Looks, Node, NodeItself, nullLocation, nullSpan, Order, Place, Span],
        UndoEvent USING [Event, EventRep, Note];

    EditSpanImpl: CEDAR PROGRAM 
        IMPORTS EditSpan, EditSpanSupport, EditNotify, NodeProps, TextEdit, TextNode, UndoEvent
        EXPORTS EditSpan, Tioga
        = BEGIN OPEN EditSpan, Tioga;

        Event: TYPE ~ UndoEvent.Event;
        EventRep: PUBLIC TYPE ~ UndoEvent.EventRep;
        Change: TYPE ~ EditNotify.Change;

        CannotDoEdit: PUBLIC ERROR = CODE;
        afterMoved1: PUBLIC Location;
        afterMoved2: PUBLIC Location;
        <<>>
<<Editing operations on spans>>
    CheckForNil: PROC [span: Span] RETURNS [BOOLEAN] = INLINE {
        RETURN [span.start.node = NIL OR span.end.node = NIL] 
        };

    Replace: PUBLIC PROC [destRoot, sourceRoot: Node, dest, source: Span, saveForPaste: BOOLEAN Ź TRUE, event: Event Ź NIL]
        RETURNS [result: Span] = {
        <<replace dest span by copy of source span>>
        <<result is the new copy of source>>
        newDest: Span;
        IF TextSpans[dest, source] THEN { -- pure text replace
            RETURN [TwoSpanText[destRoot, sourceRoot, dest, source, saveForPaste, TextEdit.ReplaceText, event]] 
            };
        source Ź EditSpanSupport.CopySpan[source];
        sourceRoot Ź TextNode.Root[source.start.node];
        sourceRoot.deleted Ź TRUE;
        [result, newDest] Ź Transpose[sourceRoot, destRoot, source, dest, event];
        IF saveForPaste THEN SaveSpanForPaste[newDest, event] 
        };

    TextSpans: PROC [dest, source: Span] RETURNS [BOOLEAN] = {
        RETURN [
            dest.start.node = dest.end.node AND
            dest.start.where # NodeItself AND
            dest.end.where # NodeItself AND
            source.start.node = source.end.node AND
            source.start.where # NodeItself AND
            source.end.where # NodeItself
            ] 
        };

    TwoSpanText: PROC [destRoot, sourceRoot: Node, dest, source: Span, saveForPaste: BOOLEAN, textProc: TextEdit.TwoSpanProc, event: 
    Event] RETURNS [result: Span] = {
        destNode: Node Ź dest.start.node;
        sourceNode: Node Ź source.start.node;
        destStart: INT Ź dest.start.where;
        destLen: INT Ź dest.end.where - destStart + 1;
        sourceStart: INT Ź source.start.where;
        sourceLen: INT Ź source.end.where - sourceStart + 1;
        resultStart, resultLen: INT;
        IF saveForPaste THEN SaveTextForPaste[destNode, destStart, destLen, event];
        [resultStart, resultLen] Ź textProc[destRoot, sourceRoot, 
            destNode, destStart, destLen, sourceNode, sourceStart, sourceLen, event];
        RETURN [[[destNode, resultStart], [destNode, resultStart+resultLen-1]]] 
        };

    SaveForPaste: PUBLIC PROC [span: Span, event: Event Ź NIL] = {
        IF CheckForNil[span] THEN RETURN;
        IF span.start.node = span.end.node AND
        span.start.where # NodeItself AND span.end.where # NodeItself THEN { -- pure text
            node: Node Ź span.start.node;
            start: INT Ź span.start.where;
            len: INT Ź span.end.where-span.start.where+1;
            SaveTextForPaste[node, start, len, event] 
            }
        ELSE SaveSpanForPaste[EditSpanSupport.CopySpan[span], event] 
        };

    Delete: PUBLIC PROC [root: Node, del: Span, event: Event Ź NIL, saveForPaste: BOOLEAN Ź TRUE] = {
        IF CheckForNil[del] THEN RETURN;
        IF del.start.node = del.end.node AND
        del.start.where # NodeItself AND del.end.where # NodeItself THEN { -- pure text
            node: Node Ź del.start.node;
            start: INT Ź del.start.where;
            len: INT Ź del.end.where-del.start.where+1;
            IF saveForPaste THEN SaveTextForPaste[node, start, len, event];
            TextEdit.DeleteText[root, node, start, len, event] 
            }
        ELSE {
            d: Span Ź MoveToLimbo[root, del, event];
            IF saveForPaste THEN SaveSpanForPaste[d, event] 
            }
        };

    paste: REF Change.ChangingSpanForPaste Ź NIL;

    SaveTextForPaste: PROC [node: Node, start, len: INT, event: Event] = {
        span: Span ~ IF len = 0 THEN nullSpan ELSE [[node, start], [node, start+len-1]];
        SaveSpanForPaste[EditSpanSupport.CopySpan[span],  event];
        };

    SaveSpanForPaste: PROC [span: Span, event: Event] = {
        SaveOldPaste[event];
        paste Ź NEW[Change.ChangingSpanForPaste Ź [ChangingSpanForPaste[span]]];
        };

    SaveOldPaste: PROC [event: Event] = {
        UndoEvent.Note[event, RestorePaste, paste]; paste Ź NIL 
        };

    RestorePaste: PROC [undoRef: REF Change, currentEvent: Event] = {
        SaveOldPaste[currentEvent]; paste Ź NARROW[undoRef] 
        };

    SavedForPaste: PUBLIC PROC RETURNS [span: Span] = {
        savedPaste: REF Change.ChangingSpanForPaste ~ paste;
        RETURN[IF savedPaste=NIL THEN nullSpan ELSE savedPaste.span];
        };

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

    Copy: PUBLIC PROC [destRoot, sourceRoot: Node, dest: Location, source: Span, where: Place Ź after, nesting: INTEGER Ź 0, event: 
    Event Ź NIL] RETURNS [result: Span] = {
        <<result is the new copy of source>>
        IF CheckForNil[source] OR dest.node=NIL THEN RETURN [nullSpan];
        IF TextLocationAndSpan[dest, source] THEN -- pure text copy
        RETURN [DestSpanText[destRoot, sourceRoot, dest, source, TextEdit.CopyText, event]];
        source Ź EditSpanSupport.CopySpan[source];
        sourceRoot Ź TextNode.Root[source.start.node];
        sourceRoot.deleted Ź TRUE;
        result Ź Move[destRoot, sourceRoot, dest, source, where, nesting, event] 
        };

    TextLocationAndSpan: PROC [dest: Location, source: Span] RETURNS [BOOLEAN] = {
        RETURN [dest.where # NodeItself AND
            source.start.node = source.end.node AND
            source.start.where # NodeItself AND source.end.where # NodeItself] 
        };

    DestSpanText: PROC [destRoot, sourceRoot: Node, dest: Location, source: Span, textProc: TextEdit.DestSpanProc, event: Event] 
    RETURNS [result: Span] = {
        destNode: Node Ź dest.node;
        sourceNode: Node Ź source.start.node;
        destLoc: INT Ź dest.where;
        sourceStart: INT Ź source.start.where;
        sourceLen: INT Ź source.end.where - sourceStart + 1;
        resultStart, resultLen: INT;
        [resultStart, resultLen] Ź textProc[destRoot, sourceRoot, destNode, destLoc, sourceNode, sourceStart, sourceLen, event];
        RETURN [[[destNode, resultStart], [destNode, resultStart+resultLen-1]]] 
        };

    Move: PUBLIC PROC [destRoot, sourceRoot: Node, dest: Location, source: Span, where: Place Ź after, nesting: INTEGER Ź 0, event: 
    Event Ź NIL] RETURNS [result: Span] = {
        <<dest cannot be within source>>
        <<result is moved span>>
        sBefore, sAfter, sTop, sBottom, dBefore, dAfter: EditSpanSupport.Slice;
        sNesting, dNesting: INTEGER;
        sDepth: NAT;
        beforeSource, afterSource: Node; -- nodes adjacent to source after do splits
        afterLoc: Location;
        FreeSlices: PROC = {
            EditSpanSupport.FreeSlice[sBefore];
            EditSpanSupport.FreeSlice[sAfter];
            EditSpanSupport.FreeSlice[sTop];
            EditSpanSupport.FreeSlice[sBottom]; 
            EditSpanSupport.FreeSlice[dBefore];
            EditSpanSupport.FreeSlice[dAfter];
            sBefore Ź sAfter Ź sTop Ź sBottom Ź dBefore Ź dAfter Ź NIL 
            }; 
        ForcedUnNest: PROC [afterNode: Node] = {
            span: Span = TextNode.MakeNodeSpan[afterNode, TextNode.LastWithin[afterNode]];
            FreeSlices[];
            [] Ź UnNest[TextNode.Root[afterNode], span, event] 
            };
        ForcedNest: PROC = {
            span: Span Ź TextNode.MakeNodeSpan[sTop[sDepth], TextNode.LastWithin[sBottom[sDepth]]];
            IF EditSpanSupport.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[TextNode.Root[span.start.node], span, event] 
            };
        IF CheckForNil[source] THEN RETURN [nullSpan];
        IF TextLocationAndSpan[dest, source] THEN {
            <<pure text move>>
            RETURN [DestSpanText[destRoot, sourceRoot, dest, source, TextEdit.MoveText, event]];
            };
        SELECT where FROM
            child => { where Ź after; nesting Ź nesting+1 };
            sibling => {
                newDest: Node = TextNode.LastWithin[dest.node];
                where Ź after;
                nesting Ź nesting + TextNode.Level[dest.node] - TextNode.Level[newDest];
                dest Ź [newDest, NodeItself];
                };
            ENDCASE => NULL;
        <<split source and dest, if necessary, so can deal with entire nodes>>
        [dest, source, where, nesting] Ź EditSpanSupport.DoSplits2[dest, source, where, nesting, event];
        beforeSource Ź TextNode.StepBackward[source.start.node];
        afterSource Ź TextNode.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
                    SELECT nesting FROM
                        > 0 => {
                            FOR i:INTEGER IN [0..nesting) DO
                                [] Ź Nest[sourceRoot, EditSpanSupport.NodeSpan[source], event];
                                ENDLOOP
                            };
                        < 0 => {
                            FOR i:INTEGER IN [nesting..0) DO
                                [] Ź UnNest[sourceRoot, EditSpanSupport.NodeSpan[source], event];
                                ENDLOOP
                            };
                        ENDCASE => NULL;
                    }
                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]
                            Ź EditSpanSupport.DescribeBand[source.start.node, source.end.node !
                                EditSpanSupport.BadBand => { source Ź nullSpan; GOTO ErrorReturn } ];
                        IF dest = nullLocation THEN { -- moving to limbo
                            dest Ź EditSpanSupport.CreateDest[EditSpanSupport.SliceLength[sTop]-sDepth];
                            destRoot Ź TextNode.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] Ź EditSpanSupport.DestSlices[dest.node, where];
                        IF EditSpanSupport.CompareSliceOrder[dBefore, sBefore]=after AND EditSpanSupport.CompareSliceOrder[dBefore, sBottom]=before THEN 
                        GOTO ErrorReturn;
                        <<dest inside source>>
                        IF dBefore[0] = sBefore[0] THEN { -- source and dest in same tree
                            span: Span = TextNode.MakeNodeSpan[source.start.node, source.end.node];
                            FreeSlices[];
                            [] Ź MoveToLimbo[sourceRoot, span, event];
                            LOOP 
                            };
                        dNesting Ź dNesting + nesting;
                        SELECT EditSpanSupport.NeedNestingChange[dBefore, dAfter, sTop, sBottom, dNesting, sDepth] FROM
                            needUnNest => { ForcedUnNest[EditSpanSupport.LastOfSlice[dAfter]]; LOOP };
                            needNest => { ForcedNest[]; LOOP };
                            ENDCASE;
                        IF EditSpanSupport.SliceLength[sAfter] > EditSpanSupport.SliceLength[sBefore]+1
                            THEN {
                                ForcedUnNest[EditSpanSupport.LastOfSlice[sAfter]]; LOOP 
                                }
                            ELSE { -- do it
                                notify: REF MovingNodes Change;
                                notify Ź NEW[MovingNodes Change Ź [MovingNodes[
                                    dest: dest.node, first: source.start.node, last: source.end.node, 
                                    pred: EditSpanSupport.LastOfSlice[sBefore], 
                                    nesting: sNesting, afterDest: (where # before)]]];
                                EditNotify.Notify[notify, before];
                                EditSpanSupport.DeletePrefix[sTop, sDepth]; EditSpanSupport.DeletePrefix[sBottom, sDepth];
                                EditSpanSupport.ReplaceBand[dBefore, dAfter, sTop, sBottom, dNesting, event];
                                EditSpanSupport.Splice[sBefore, sAfter];
                                FreeSlices[];
                                EditNotify.Notify[notify, after];
                                UndoEvent.Note[event, UndoMoveNodes, notify] 
                                };
                        EXIT;
                        ENDLOOP
                    };
            IF dest.where # NodeItself
                THEN { -- undo prior splits
                    start, end: BOOLEAN Ź FALSE;
                    IF source.start.where # NodeItself THEN { -- merge start of source with front of dest
                        start Ź TRUE;
                        [source, ] Ź EditSpanSupport.ReMerge[source, nullSpan, source.start.node, event] 
                        };
                    IF source.end.where # NodeItself THEN { -- merge end of source with tail of dest
                        end Ź TRUE;
                        [source, ] Ź EditSpanSupport.ReMerge[source, nullSpan, source.end.node, event, TRUE] 
                        };
                    IF start AND end THEN { -- merge before source with after source
                        afterLoc Ź Merge[TextNode.Root[afterSource], afterSource, event] 
                        }
                    }
                ELSE IF source.start.where # NodeItself AND source.end.where # NodeItself THEN {
                    afterLoc Ź Merge[TextNode.Root[afterSource], afterSource, event] 
                    };
            afterMoved2 Ź afterMoved1; -- save previous hint
            <<afterMoved1 _ IF afterSource=NIL THEN [beforeSource, 0] ELSE afterLoc; -- hint for repaint>>
            IF afterSource=NIL THEN afterMoved1 Ź [beforeSource, 0] ELSE afterMoved1 Ź afterLoc; -- hint for repaint
            RETURN [source];
            EXITS ErrorReturn => {
                FreeSlices[];
                [, source] Ź EditSpanSupport.UndoSplits2[dest, source, event];
                ERROR CannotDoEdit 
                }
            }
        };

    UndoMoveNodes: PROC [undoRef: REF Change, currentEvent: Event] = {
        WITH undoRef SELECT FROM
            x: REF Change.MovingNodes => {
                [] Ź Move[destRoot: TextNode.Root[x.pred], sourceRoot: TextNode.Root[x.first], 
                    dest: TextNode.MakeNodeLoc[x.pred], source: TextNode.MakeNodeSpan[x.first, x.last], 
                    where: after, nesting: x.nesting, event: currentEvent] 
                };
            ENDCASE => ERROR 
        };

    Transpose: PUBLIC PROC [alphaRoot, betaRoot: Node, 
        alpha, beta: Span, event: Event Ź NIL]
        RETURNS [newAlpha, newBeta: Span] = {
        <<newAlpha is new location of alpha span; ditto for newBeta>>
        aBefore, aAfter, aTop, aBottom, bBefore, bAfter, bTop, bBottom: EditSpanSupport.Slice;
        aNesting, bNesting: INTEGER;
        aDepth, bDepth: NAT;
        beforeAlpha, afterAlpha, beforeBeta, afterBeta: Node; -- nodes adjacent after do splits
        afterAlphaLoc, afterBetaLoc: Location;
        FreeSlices: PROC = {
            EditSpanSupport.FreeSlice[aBefore]; EditSpanSupport.FreeSlice[aAfter]; EditSpanSupport.FreeSlice[aTop]; 
            EditSpanSupport.FreeSlice[aBottom]; 
            EditSpanSupport.FreeSlice[bBefore]; EditSpanSupport.FreeSlice[bAfter]; EditSpanSupport.FreeSlice[bTop]; 
            EditSpanSupport.FreeSlice[bBottom];
            aBefore Ź aAfter Ź aTop Ź aBottom Ź bBefore Ź bAfter Ź bTop Ź bBottom Ź NIL 
            }; 
        { -- for exit
            IF CheckForNil[alpha] OR CheckForNil[beta] THEN RETURN [nullSpan, nullSpan];
            IF TextSpans[alpha, beta] THEN { -- pure text transpose
                alphaNode: Node Ź alpha.start.node;
                betaNode: Node Ź beta.start.node;
                alphaStart: INT Ź alpha.start.where;
                alphaLen: INT Ź alpha.end.where - alphaStart + 1;
                betaStart: INT Ź beta.start.where;
                betaLen: INT Ź beta.end.where - betaStart + 1;
                alphaResultStart, alphaResultLen, betaResultStart, betaResultLen: INT;
                [alphaResultStart, alphaResultLen, betaResultStart, betaResultLen] Ź TextEdit.TransposeText[
                    alphaRoot, betaRoot, alphaNode, alphaStart, alphaLen, betaNode, betaStart, betaLen, event];
                newAlpha Ź [[betaNode, alphaResultStart], [betaNode, alphaResultStart+alphaResultLen-1]];
                newBeta Ź [[alphaNode, betaResultStart], [alphaNode, betaResultStart+betaResultLen-1]];
                RETURN 
                };
            [alpha, beta] Ź EditSpanSupport.DoSplits[alpha, beta, event]; -- so can deal with entire nodes
            beforeAlpha Ź TextNode.StepBackward[alpha.start.node];
            afterAlpha Ź TextNode.StepForward[alpha.end.node];
            afterAlphaLoc Ź [afterAlpha, 0];
            beforeBeta Ź TextNode.StepBackward[beta.start.node];
            afterBeta Ź TextNode.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[alphaRoot, betaRoot, EditSpanSupport.NodeLoc[alpha.start], EditSpanSupport.NodeSpan[beta], before, 0, event] 
                }
            ELSE IF afterBeta = alpha.start.node THEN { -- beta just before alpha
                <<move alpha nodes to before beta nodes>>
                [] Ź Move[betaRoot, alphaRoot, EditSpanSupport.NodeLoc[beta.start], EditSpanSupport.NodeSpan[alpha], before, 0, event] 
                }
            ELSE     { -- get slices describing the bands of nodes to be transposed
                overlap: BOOLEAN;
                head, tail: Span; -- sections of alpha or beta before and after the overlap
                startOrder, endOrder: Order;
                [aBefore, aAfter, aTop, aBottom, aNesting, aDepth] Ź
                    EditSpanSupport.DescribeBand[alpha.start.node, alpha.end.node !  EditSpanSupport.BadBand =>
                    { alpha Ź beta Ź nullSpan; GOTO ErrorReturn }];
                [bBefore, bAfter, bTop, bBottom, bNesting, bDepth] Ź
                    EditSpanSupport.DescribeBand[beta.start.node, beta.end.node ! EditSpanSupport.BadBand =>
                    { alpha Ź beta Ź nullSpan; GOTO ErrorReturn }];
                <<check for overlap>>
                [overlap, head, tail, startOrder, endOrder] Ź
                    EditSpanSupport.SliceOrder[alpha, beta, aBefore, aBottom, bBefore, bBottom];
                IF overlap 
                    THEN { -- bands overlap
                        FreeSlices[];
                        SELECT TRUE FROM
                            head = nullSpan AND tail = nullSpan => NULL;
                            head = nullSpan => { --move tail to before alphastart
                                [] Ź Move[alphaRoot, betaRoot, 
                                    EditSpanSupport.NodeLoc[alpha.start], EditSpanSupport.NodeSpan[tail], before, 0, event];
                                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 
                                        }
                                };
                            tail = nullSpan => { --move head to after alphaend
                                [] Ź Move[alphaRoot, betaRoot, EditSpanSupport.NodeLoc[alpha.end], EditSpanSupport.NodeSpan[head], after, 0, event];
                                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 
                                        }
                                };
                            startOrder # endOrder => NULL; -- one contained in the other
                            ENDCASE => { --transpose head and tail
                                [] Ź Transpose[alphaRoot, betaRoot, 
                                    EditSpanSupport.NodeSpan[head], EditSpanSupport.NodeSpan[tail], event];
                                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 { -- no overlap, do transpose as two moves
                        aSpan, bSpan: Span;
                        after1, after2: Location;
                        bLoc: Location Ź TextNode.MakeNodeLoc[EditSpanSupport.LastOfSlice[bBefore]];
                        aLoc: Location Ź TextNode.MakeNodeLoc[EditSpanSupport.LastOfSlice[aBefore]];
                        FreeSlices[];
                        aSpan Ź TextNode.MakeNodeSpan[alpha.start.node, alpha.end.node];
                        bSpan Ź TextNode.MakeNodeSpan[beta.start.node, beta.end.node];
                        [] Ź MoveToLimbo[alphaRoot, aSpan, event]; after1 Ź afterMoved1; -- repaint hints
                        [] Ź MoveToLimbo[betaRoot, bSpan, event]; after2 Ź afterMoved1;
                        [] Ź Move[betaRoot, TextNode.Root[aSpan.start.node], bLoc, aSpan, after, bNesting, event];
                        [] Ź Move[alphaRoot, TextNode.Root[bSpan.start.node], aLoc, bSpan, after, aNesting, event];
                        afterMoved1 Ź after1; afterMoved2 Ź after2 
                        }
                };
            IF alpha.start.where # NodeItself AND beta.start.where # NodeItself THEN { -- remerge starts
                [alpha, beta] Ź EditSpanSupport.ReMerge[alpha, beta, alpha.start.node, event];
                [alpha, beta] Ź EditSpanSupport.ReMerge[alpha, beta, beta.start.node, event] 
                };
            IF alpha.end.where # NodeItself AND beta.end.where # NodeItself THEN { -- remerge ends
                [alpha, beta] Ź EditSpanSupport.ReMerge[alpha, beta, alpha.end.node, event, TRUE];
                [alpha, beta] Ź EditSpanSupport.ReMerge[alpha, beta, beta.end.node, event, TRUE];
                afterAlphaLoc Ź beta.end; afterBetaLoc Ź alpha.end 
                };
            <<afterMoved1 _ IF afterAlphaLoc.node=NIL THEN [beforeAlpha, 0] ELSE afterAlphaLoc; -- hint for repaint, comment out, Bier, January 
            6, 1989>>
            IF afterAlphaLoc.node=NIL THEN afterMoved1 Ź [beforeAlpha, 0] ELSE afterMoved1 Ź afterAlphaLoc; -- hint for repaint
            <<afterMoved2 _ IF afterBetaLoc.node=NIL THEN [beforeBeta, 0] ELSE afterBetaLoc;>>
            IF afterBetaLoc.node=NIL THEN afterMoved2 Ź [beforeBeta, 0] ELSE afterMoved2 Ź afterBetaLoc;
            RETURN [alpha, beta];    
            EXITS ErrorReturn => {
                FreeSlices[]; [alpha, beta] Ź EditSpanSupport.UndoSplits[alpha, beta, event];
                ERROR CannotDoEdit 
                }
            }
        };

    MoveOnto: PUBLIC PROC [destRoot, sourceRoot: Node, dest, source: Span, saveForPaste: BOOLEAN Ź TRUE, event: Event Ź NIL] RETURNS 
    [result: Span] = {
        <<like Replace, but moves source instead of copying it>>
        <<result is moved span>>
        overlap: BOOLEAN;
        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: EditSpanSupport.Slice;
        aNesting, bNesting: INTEGER;
        aDepth, bDepth: NAT;
        FreeSlices: PROC = {
            EditSpanSupport.FreeSlice[aBefore]; EditSpanSupport.FreeSlice[aAfter]; EditSpanSupport.FreeSlice[aTop]; 
            EditSpanSupport.FreeSlice[aBottom]; 
            EditSpanSupport.FreeSlice[bBefore]; EditSpanSupport.FreeSlice[bAfter]; EditSpanSupport.FreeSlice[bTop]; 
            EditSpanSupport.FreeSlice[bBottom];
            aBefore Ź aAfter Ź aTop Ź aBottom Ź bBefore Ź bAfter Ź bTop Ź bBottom Ź NIL 
            }; 
        { -- for exit
            IF CheckForNil[source] OR CheckForNil[dest] THEN RETURN [nullSpan];
            IF TextSpans[dest, source] THEN { -- pure text move
                RETURN [TwoSpanText[destRoot, sourceRoot, dest, source, saveForPaste, 
                    TextEdit.MoveTextOnto, event]] 
                };
            [dest, source] Ź EditSpanSupport.DoSplits[dest, source, event];
            [aBefore, aAfter, aTop, aBottom, aNesting, aDepth] Ź
                EditSpanSupport.DescribeBand[dest.start.node, dest.end.node !  EditSpanSupport.BadBand =>
                { dest Ź source Ź nullSpan; GOTO ErrorReturn }];
            [bBefore, bAfter, bTop, bBottom, bNesting, bDepth] Ź
                EditSpanSupport.DescribeBand[source.start.node, source.end.node ! EditSpanSupport.BadBand =>
                { dest Ź source Ź nullSpan; GOTO ErrorReturn }];
            <<get slices for dest and source>>
            [overlap, head, tail, startOrder, endOrder] Ź
                EditSpanSupport.SliceOrder[dest, source, aBefore, aBottom, bBefore, bBottom];
            FreeSlices[];
            <<check for overlap>>
            IF overlap THEN { -- bands overlap. modify dest so doesn't overlap
                SELECT TRUE FROM
                    head = nullSpan AND tail = nullSpan => GOTO ErrorReturn;
                    head = nullSpan => { -- source start = dest start
                        IF endOrder=before
                            THEN {GOTO ErrorReturn} -- dest end before source end
                            ELSE {dest.start Ź tail.start} 
                        };
                    tail = nullSpan => { --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 --
                        };
                    ENDCASE => { -- have both head and tail
                        SELECT TRUE FROM
                            startOrder=before AND endOrder=after => {
                                [] Ź Delete[destRoot, tail, event]; dest.end Ź head.end 
                                };
                            startOrder=before => dest.end Ź head.end;
                            endOrder=after => dest.start Ź tail.start;
                            ENDCASE => GOTO ErrorReturn;
                        };
                };
            [dest, source] Ź EditSpanSupport.UndoSplits[dest, source, event];
            source Ź MoveToLimbo[sourceRoot, source, event];
            sourceRoot Ź TextNode.Root[source.start.node];
            [result, newDest] Ź Transpose[sourceRoot, destRoot, source, dest, event];
            IF saveForPaste THEN SaveSpanForPaste[newDest, event];
            RETURN;
            EXITS ErrorReturn => {
                [dest, source] Ź EditSpanSupport.UndoSplits[dest, source, event]; ERROR CannotDoEdit 
                }
            }
        };

<<Nesting>>
    ChangeNesting: PUBLIC PROC [root: Node, span: Span, change: INTEGER, event: Event Ź NIL]
        RETURNS [new: Span] = {
        <<moves span to a deeper nesting level in tree>>
        before, after, top, bottom: EditSpanSupport.Slice;
        nesting: INTEGER;
        depth: NAT;
        FreeSlices: PROC = {
            EditSpanSupport.FreeSlice[before]; EditSpanSupport.FreeSlice[after]; EditSpanSupport.FreeSlice[top]; 
            EditSpanSupport.FreeSlice[bottom]; 
            before Ź after Ź top Ź bottom Ź NIL 
            }; 
        { -- for exit
            IF CheckForNil[span] THEN RETURN [nullSpan];
            [span, ] Ź EditSpanSupport.DoSplits[span, nullSpan, event]; -- so can deal with entire nodes
            DO -- only repeat this loop if have forced nest/unnest
                [before, after, top, bottom, nesting, depth] Ź
                    EditSpanSupport.DescribeBand[span.start.node, span.end.node ! EditSpanSupport.BadBand =>
                    { span Ź nullSpan; GOTO ErrorReturn } ];
                IF nesting+change > 1 THEN GOTO ErrorReturn; -- cannot do it
                SELECT EditSpanSupport.NeedNestingChange[before, after, top, bottom, nesting+change, depth] FROM
                    needUnNest => {
                        afterNode: Node = EditSpanSupport.LastOfSlice[after];
                        span: Span = TextNode.MakeNodeSpan[afterNode, TextNode.LastWithin[afterNode]];
                        FreeSlices[];
                        [] Ź UnNest[root, span, event];
                        LOOP 
                        };
                    needNest => {
                        span: Span = TextNode.MakeNodeSpan[top[depth], TextNode.LastWithin[bottom[depth]]];
                        IF EditSpanSupport.SliceLength[top] = depth+1 THEN GOTO ErrorReturn;
                        FreeSlices[];
                        [] Ź Nest[root, span, event];
                        LOOP 
                        };
                    ENDCASE => { -- do it
                    notify: REF NodeNesting Change;
                    notify Ź NEW[NodeNesting Change Ź [NodeNesting[
                        first: span.start.node, last: span.end.node, change: change]]];
                    EditNotify.Notify[notify, before];
                    EditSpanSupport.DeletePrefix[top, depth];
                    EditSpanSupport.DeletePrefix[bottom, depth];
                    EditSpanSupport.ReplaceBand[before, after, top, bottom, nesting+change, event];
                    FreeSlices[];
                    EditNotify.Notify[notify, after];
                    UndoEvent.Note[event, UndoChangeNesting, notify] 
                    };
                EXIT;
                ENDLOOP;
            RETURN [span];
            EXITS ErrorReturn => {
                FreeSlices[]; [span, ] Ź EditSpanSupport.UndoSplits[span, nullSpan, event]; ERROR CannotDoEdit 
                }
            }
        };

    UndoChangeNesting: PROC [undoRef: REF Change, currentEvent: Event] = {
        WITH undoRef SELECT FROM
            x: REF Change.NodeNesting => [] Ź ChangeNesting[root: TextNode.Root[x.first], span: TextNode.MakeNodeSpan[x.first, x.last], change: 
            -x.change, event: currentEvent];
            ENDCASE => ERROR 
        };

<<New nodes; split & merge>>
    Insert: PUBLIC PROC [root, old: Node, where: Place Ź after, event: Event Ź NIL] RETURNS [new: Node] = {
        <<empty copy of old node is inserted in tree in position determined by "where">>
        IF old=NIL THEN RETURN [NIL];
        new Ź TextNode.NewTextNode[];
        Inherit[old, new];
        DoInsertNode[root, old, new, where, event] 
        };

    InsertTextNode: PUBLIC PROC [root, old: Node, where: Place Ź after, inherit: BOOLEAN Ź FALSE, event: Event Ź NIL] RETURNS [new: 
    Node] = {
        <<empty text node is inserted in tree>>
        IF old=NIL THEN RETURN [NIL];
        new Ź TextNode.NewTextNode[];
        IF inherit THEN Inherit[old, new];
        DoInsertNode[root, old, new, where, event] 
        };

    Inherit: PUBLIC PROC [old, new: Node, allprops: BOOL Ź FALSE] = {
        CopyProp: PROC [name: ATOM, value: REF] RETURNS [BOOL] = {
            IF allprops OR NodeProps.Is[name, $Inheritable] THEN {
                newvalue: REF ~ NodeProps.CopyInfo[name, value];
                IF newvalue # NIL THEN NodeProps.PutProp[new, name, newvalue];
                };
            RETURN [FALSE];
            };
        new.format Ź old.format;
        new.comment Ź old.comment;
        IF allprops OR old.hasPrefix OR old.hasPostfix OR old.hasStyleDef THEN
            [] Ź NodeProps.MapProps[old, CopyProp, FALSE, FALSE];
        };

    DoInsertNode: PROC [root, old, new: Node, where: Place, event: Event] = {
        dest, parent: Node;
        child: BOOLEAN Ź FALSE;
        notify: REF InsertingNode Change;
        IF new = NIL OR old = NIL THEN RETURN;
        parent Ź IF where = child THEN old ELSE TextNode.Parent[old];
        SELECT where FROM
            sibling => { dest Ź TextNode.LastWithin[old]; child Ź FALSE };
            after => { dest Ź old; child Ź FALSE };
            child => { dest Ź old; child Ź TRUE };
            ENDCASE => {
                IF parent.child = old
                    THEN { dest Ź parent; child Ź TRUE }
                    ELSE { dest Ź TextNode.LastWithin[TextNode.Previous[old, parent]]; child Ź FALSE }
                };
        notify Ź NEW[InsertingNode Change Ź [InsertingNode[new: new, dest: dest]]];
        EditNotify.Notify[notify, before];
        SELECT TRUE FROM
            child => { -- insert as first child of dest
                new.next Ź dest.child;
                new.parent Ź dest;
                dest.child Ź new;
                };
            where = sibling => { -- insert as next sibling of old; don't adopt children
                new.next Ź old.next;
                new.parent Ź old.parent;
                old.next Ź new;
                };
            ENDCASE => { -- insert as next sibling of dest
                new.next Ź dest.next;
                new.parent Ź dest.parent;
                dest.next Ź new;
                IF where=after THEN {
                    EditSpanSupport.AdoptChildren[node: new, child: dest.child];
                    dest.child Ź NIL;
                    };
                };
        EditNotify.Notify[notify, after];
        UndoEvent.Note[event, UndoInsertNode, notify] 
        };

    UndoInsertNode: PROC [undoRef: REF Change, currentEvent: Event] = {
        WITH undoRef SELECT FROM
            x: REF Change.InsertingNode => [] Ź Delete[root: TextNode.Root[x.new], del: TextNode.MakeNodeSpan[x.new, x.new], event: 
            currentEvent];
            ENDCASE => ERROR;
        };

    Split: PUBLIC PROC [root: Node, loc: Location, event: Event Ź NIL] RETURNS [new: Node] = {
        <<inserts copy of loc.node is inserted 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>>
        old: Node = loc.node;
        IF old=NIL THEN RETURN [NIL];
        new Ź Insert[root, old, after, event];
        IF loc.where # NodeItself AND old # NIL THEN {
            [] Ź TextEdit.MoveText[destRoot: root, sourceRoot: root, dest: new, destLoc: 0, 
                source: old, start: loc.where, event: event] 
            }
        };

    Merge: PUBLIC PROC [root, node: Node, event: Event Ź NIL] 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 Ź TextNode.StepBackward[node];
        start: INT;
        IF pred = NIL OR TextNode.Parent[pred] = NIL OR node = NIL THEN ERROR CannotDoEdit;
        [start, ] Ź TextEdit.CopyText[root, root, pred, INT.LAST, node, 0, INT.LAST, event];
        [] Ź Delete[root, TextNode.MakeNodeSpan[node, node], event];
        RETURN [[pred, start]] 
        };


<<Change looks>>
    ChangeLooks: PUBLIC PROC [root: Node, span: Span, remove, add: Looks, event: Event Ź NIL] = {
        DoChange: PROC [node: Node, start, len: INT] RETURNS [stop: BOOL Ź FALSE] = {
            TextEdit.ChangeLooks[root, node, remove, add, start, len, event];
            };
        EditSpanSupport.Apply[span, DoChange] 
        };


<<Caps and Lowercase>>
    ChangeCaps: PUBLIC PROC [root: Node, span: Span, how: CapChange Ź allCaps, 
    event: Event Ź NIL] = {
        DoChange: PROC [node: Node, start, len: INT] RETURNS [stop: BOOL Ź FALSE] = {
            TextEdit.ChangeCaps[root, node, start, len, how, event];
            };
        IF CheckForNil[span] THEN RETURN;
        EditSpanSupport.Apply[span, DoChange] 
        };


    END.