<> <> <> <> DIRECTORY EditSpan, EditSpanSupport, TextEdit, RopeEdit, TiogaItemClass, TiogaBasicClass, TiogaNode, TiogaNodeOps, TiogaTreeOps, TreeSlice; EditSpanSupportImpl: CEDAR MONITOR IMPORTS EditSpan, TiogaNodeOps, TiogaTreeOps, TreeSlice EXPORTS EditSpanSupport SHARES TiogaNode = BEGIN OPEN EditSpanSupport, TreeSlice, EditSpan; NeedNestingChange: PUBLIC PROC [before, after, top, bottom: Slice, nesting: INTEGER, depth: NAT] RETURNS [NeededNestingChange] = { bandStart, afterOver: INTEGER; topLen, botLen: NAT; nesting _ MIN[1,nesting]; topLen _ top.length; botLen _ bottom.length; bandStart _ before.length+nesting-(topLen-depth); IF bandStart <= 0 THEN RETURN [needNest]; -- must be at least 1 afterOver _ after.length-(botLen-depth+bandStart); IF afterOver > 1 THEN RETURN [needUnNest]; RETURN [ok] }; Splice: PUBLIC PROC [before, after: Slice, beforeStart, afterStart: NAT _ 0] = { <> <> <> a, b: Ref; beforeLen, afterLen: NAT; beforeLen _ before.length - beforeStart; afterLen _ after.length - afterStart; IF before.kind # before OR after.kind # after THEN ERROR; IF afterLen > beforeLen+1 THEN ERROR; -- cannot have gaps in tree b _ TreeSlice.LastOfSlice[before]; IF afterLen = beforeLen+1 THEN { -- adopt children a _ TreeSlice.LastOfSlice[after]; IF a # NIL AND beforeLen > 0 THEN TiogaTreeOps.LastSibling[a].next _ b } ELSE a _ NIL; WITH b SELECT FROM br: RefBranchNode => { brchild: RefBranchNode = TiogaNodeOps.NarrowToBranchNode[a]; IF a # NIL AND brchild=NIL THEN ERROR; br.child _ brchild }; ls: TiogaNode.RefListNode => ls.contents _ a; bx: TiogaNode.RefBoxNode => bx.contents _ a; ENDCASE => ERROR; IF beforeLen=0 THEN RETURN; FOR i: NAT _ beforeLen-1, i-1 DO -- do successors a, b: Ref; b _ before[beforeStart+i]; IF i >= afterLen OR (a_after[afterStart+i])=NIL THEN { -- no successor IF i > 0 THEN { b.next _ before[beforeStart+i-1]; b.last _ TRUE }} ELSE { -- has successor IF a=b THEN RETURN; IF i > 0 THEN TiogaTreeOps.LastSibling[a].next _ before[beforeStart+i-1]; b.next _ a; b.last _ FALSE }; IF i=0 THEN RETURN; ENDLOOP }; ReplaceBand: PUBLIC PROC [before, after, top, bottom: Slice, nesting: INTEGER, event: Event] = { <> <> <> depth: NAT; fullBottom: Slice; nesting _ MIN[1,nesting]; IF top.length >= before.length+nesting THEN ERROR; depth _ MAX[1,before.length+nesting-top.length]; fullBottom _ TreeSlice.InsertPrefix[before,bottom,depth]; Splice[fullBottom,after]; Splice[before,top,depth]; FreeSlice[fullBottom] }; BadBand: PUBLIC ERROR = CODE; DescribeBand: PUBLIC PROC [first, last: RefBranchNode] RETURNS [before, after, top, bottom: Slice, nesting: INTEGER, depth: NAT] = { <<>> <> <> <> <> <> <<>> BadBandError: PROC = { ERROR BadBand [! UNWIND => { FreeSlice[before]; FreeSlice[after]; FreeSlice[top]; FreeSlice[bottom] } ] }; pred: RefBranchNode _ TiogaTreeOps.Backward[first].back; minDepth: NAT; IF pred=NIL THEN ERROR BadBand; -- first is root node IF pred=last THEN ERROR BadBand; -- this actually happened during testing! [before,top] _ TreeSlice.MakeSlices[pred]; nesting _ top.length-before.length; [bottom,after] _ TreeSlice.MakeSlices[last]; minDepth _ MIN[before.length,bottom.length]; FOR depth _ 0, depth+1 UNTIL depth >= minDepth DO IF before[depth] # bottom[depth] THEN { -- check for legality bot: Ref _ bottom[depth]; FOR node: Ref _ before[depth], TiogaTreeOps.Next[node] DO SELECT node FROM bot => EXIT; NIL => BadBandError[]; -- last must come before first ENDCASE; ENDLOOP; EXIT }; ENDLOOP; IF depth=0 THEN BadBandError[]; -- different root nodes for first and last <> IF TreeSlice.LastOfSlice[top] # first THEN ERROR; IF before[before.length+nesting-2] # TiogaTreeOps.Parent[first] THEN ERROR; IF TreeSlice.LastOfSlice[bottom] # last THEN ERROR }; DestSlices: PUBLIC PROC [dest: RefBranchNode, where: Place] RETURNS [before, after: Slice, nesting: INTEGER] = { <<>> <> <> <> <<>> SELECT where FROM after => { [before,after] _ TreeSlice.MakeSlices[dest]; nesting _ 0 }; child => { [before,after] _ TreeSlice.MakeSlices[dest]; nesting _ 1 }; before => { pred: RefBranchNode _ TiogaTreeOps.Backward[dest].back; [before,after] _ TreeSlice.MakeSlices[pred]; nesting _ after.length-before.length }; ENDCASE => ERROR }; CreateDest: PUBLIC PROC [depth: NAT] RETURNS [dest: BranchLoc] = { <> node: RefBranchNode; UNTIL depth = 0 DO child: RefBranchNode _ TiogaNodeOps.NewBranchNode[]; IF node # NIL THEN { node.child _ child; child.next _ node }; node _ child; depth _ depth-1; ENDLOOP; RETURN [[node,TiogaNode.NodeItself]] }; CopySpan: PUBLIC PROC [span: TreeSpan] RETURNS [result: TreeSpan] = { node, sourceFirst, sourceLast, child, new, prev, parent, first: Ref; firstLoc, lastLoc: Offset; br: RefBranchNode; sourceFirst _ span.start.node; firstLoc _ span.start.where; sourceLast _ span.end.node; lastLoc _ span.end.where; IF (node _ sourceFirst)=NIL OR sourceLast=NIL THEN RETURN [TiogaTreeOps.nullSpan]; parent _ -- parent for the copied span IF TiogaNodeOps.IsBasic[node] THEN TiogaNodeOps.NewListNode[] ELSE TiogaNodeOps.NewBranchNode[]; DO -- create new node each time through the loop WITH node SELECT FROM -- create new node of same kind as old node br: RefBranchNode => { newBr: RefBranchNode; new _ newBr _ TiogaNodeOps.NewBranchNode[] }; tx: TiogaNode.RefTextNode => { newTx: TiogaNode.RefTextNode; new _ newTx _ TiogaNodeOps.NewTextNode[tx.class]; newTx.rope _ tx.rope; newTx.runs _ tx.runs }; bx: TiogaNode.RefBoxNode => { newBx: TiogaNode.RefBoxNode; new _ newBx _ TiogaNodeOps.NewBoxNode[bx.class]; IF bx.data # NIL THEN { -- copy the data itemClass: TiogaItemClass.ItemClass _ TiogaNodeOps.FetchItemClass[bx.class]; IF itemClass.copy#NIL THEN itemClass.copy[bx, newBx] }}; ls: TiogaNode.RefListNode => { newLs: TiogaNode.RefListNode; new _ newLs _ TiogaNodeOps.NewListNode[ls.class]; IF ls.data # NIL THEN { -- copy the data itemClass: TiogaItemClass.ItemClass _ TiogaNodeOps.FetchItemClass[ls.class]; IF itemClass.copy#NIL THEN itemClass.copy[ls, newLs] }}; bs: TiogaNode.RefBasicNode => { newBs: TiogaNode.RefBasicNode; new _ newBs _ TiogaNodeOps.NewBasicNode[bs.class]; IF bs.data # NIL THEN { -- copy the data basicClass: TiogaBasicClass.BasicClass _ TiogaNodeOps.FetchBasicClass[bs.class]; IF basicClass.copy#NIL THEN basicClass.copy[bs, newBs] }}; ENDCASE => ERROR; Inherit[node,new,TRUE]; -- inherit properties from node IF prev#NIL THEN { prev.last _ FALSE; prev.next _ new } -- insert new into tree as next sibling of prev ELSE WITH parent SELECT FROM -- insert new into tree as first child/contents of parent br: RefBranchNode => WITH new SELECT FROM newItem: TiogaNode.RefItemNode => br.contents _ newItem; newBr: RefBranchNode => br.child _ newBr; ENDCASE => ERROR; bx: TiogaNode.RefBoxNode => bx.contents _ new; ls: TiogaNode.RefListNode => ls.contents _ new; ENDCASE => ERROR; new.new _ new.last _ TRUE; new.next _ parent; prev _ new; <> IF node=sourceFirst THEN first _ new; IF node=sourceLast THEN RETURN [[[first,firstLoc],[new,lastLoc]]]; <> IF (child _ TiogaTreeOps.Contents[node])=NIL AND (br _ TiogaNodeOps.NarrowToBranchNode[node])#NIL THEN child _ TiogaTreeOps.BranchChild[br]; -- use Contents and BranchChild to get internal rep's created IF child#NIL THEN { node _ child; parent _ new; prev _ NIL } -- descend in the tree ELSE DO -- move to next node, sibling or up* then sibling isBranch: BOOL; IF ~node.last THEN { node _ TiogaTreeOps.Next[node]; EXIT }; -- use Next to get internal rep created <> prev _ parent; IF (parent _ parent.next) = NIL THEN { -- need a new parent parentBr: RefBranchNode _ TiogaNodeOps.NewBranchNode[]; parent _ parentBr; WITH prev SELECT FROM br: RefBranchNode => parentBr.child _ br; it: TiogaNode.RefItemNode => parentBr.contents _ it; bs: TiogaNode.RefBasicNode => ERROR; -- cannot happen since prev comes from previous parent ENDCASE => ERROR; prev.next _ parent }; <> isBranch _ TiogaNodeOps.IsBranch[node]; IF (node _ node.next -- the parent --) = NIL THEN ERROR; -- bad arg span; failed to find sourceLast new _ new.next; -- move new to its parent also IF ~isBranch THEN WITH node SELECT FROM br: RefBranchNode => IF br.child # NIL THEN { node _ TiogaTreeOps.BranchChild[br]; -- use BranchChild to get internal rep created parent _ new; prev _ NIL; EXIT }; ENDCASE; ENDLOOP; ENDLOOP }; DoSplits: PUBLIC PROC [alpha, beta: TreeSpan, event: Event] RETURNS [newalpha, newbeta: BranchSpan] = { <> Break: PROC [root: RefBranchNode, node: Ref, before: BOOL] RETURNS [newLoc: BranchLoc] = { newLoc.node _ BreakStatement[alphaRoot, node, before, event]; <> newLoc.where _ IF newLoc.node=node THEN NodeItself ELSE 0 }; MakeTextSplit: PROC [root: RefBranchNode, node: Ref, offset: Offset] = { FixLoc: PROC [old: TreeLoc] RETURNS [newLoc: TreeLoc] = { where: Offset; IF old.node # node THEN RETURN [old]; SELECT where _ old.where FROM = NodeItself => ERROR; < offset => RETURN [[node,where]]; ENDCASE => RETURN [[new,where-offset]] }; new: Ref; IF node=NIL OR offset=NodeItself OR ~TiogaNodeOps.IsText[node] THEN RETURN; new _ BreakTextNode[root, [node, offset], event]; alpha.start _ FixLoc[alpha.start]; alpha.end _ FixLoc[alpha.end]; beta.start _ FixLoc[beta.start]; beta.end _ FixLoc[beta.end] }; alphaRoot, betaRoot: RefBranchNode; alphaRoot _ TiogaTreeOps.Root[alpha.start.node]; betaRoot _ TiogaTreeOps.Root[beta.start.node]; MakeTextSplit[alphaRoot, alpha.start.node, alpha.start.where]; MakeTextSplit[betaRoot, beta.start.node, beta.start.where]; MakeTextSplit[alphaRoot, alpha.end.node, alpha.end.where+1]; MakeTextSplit[betaRoot, beta.end.node, beta.end.where+1]; newalpha.start _ Break[alphaRoot, alpha.start.node, TRUE]; newalpha.end _ Break[alphaRoot, alpha.end.node, FALSE]; newbeta.start _ Break[betaRoot, beta.start.node, TRUE]; newbeta.end _ Break[betaRoot, beta.end.node, FALSE] }; DoSplitsForMove: PUBLIC PROC [dest: TreeLoc, source: TreeSpan, where: Place, event: Event] RETURNS [newdest: BranchLoc, newsource: BranchSpan] = { destSpan: TreeSpan; desBranchSpan: BranchSpan; SELECT where FROM before => destSpan _ [dest, TiogaTreeOps.nullLoc]; after => destSpan _ [TiogaTreeOps.nullLoc, dest]; ENDCASE => ERROR; [desBranchSpan, newsource] _ DoSplits[destSpan, source, event]; newdest _ IF where=before THEN desBranchSpan.start ELSE desBranchSpan.end }; ReMerge: PUBLIC PROC [ alpha, beta: BranchSpan, merge: RefBranchNode, event: Event, tail: BOOL _ FALSE] RETURNS [newalpha, newbeta: BranchSpan] = { FixNode: PROC [old: RefBranchNode] RETURNS [RefBranchNode] = INLINE { RETURN [IF old=merge THEN breakStatement ELSE old] }; break: Ref; breakStatement: RefBranchNode; IF tail THEN merge _ TiogaTreeOps.Forward[merge].nx; break _ JoinStatements[TiogaTreeOps.Root[merge], merge, event].node; WHILE (breakStatement _ TiogaNodeOps.NarrowToBranchNode[break])=NIL DO break _ TiogaTreeOps.Parent[break]; ENDLOOP; newalpha.start _ [FixNode[alpha.start.node], alpha.start.where]; newalpha.end _ [FixNode[alpha.end.node], alpha.end.where]; newbeta.start _ [FixNode[beta.start.node], beta.start.where]; newbeta.end _ [FixNode[beta.end.node], beta.end.where] }; UndoSplits: PUBLIC PROC [alpha, beta: BranchSpan, event: Event] = { <> IF alpha.start.where # NodeItself THEN [alpha,beta] _ ReMerge[alpha,beta,alpha.start.node,event]; IF beta.start.where # NodeItself THEN [alpha,beta] _ ReMerge[alpha,beta,beta.start.node,event]; IF alpha.end.where # NodeItself THEN [alpha,beta] _ ReMerge[alpha,beta,alpha.end.node,event,TRUE]; IF beta.end.where # NodeItself THEN [alpha,beta] _ ReMerge[alpha,beta,beta.end.node,event,TRUE]; }; UndoSplitsForMove: PUBLIC PROC [dest: BranchLoc, source: BranchSpan, where: Place, event: Event] = { destSpan: BranchSpan; SELECT where FROM before => destSpan _ [dest, TiogaTreeOps.nullBranchLoc]; after => destSpan _ [TiogaTreeOps.nullBranchLoc, dest]; ENDCASE => ERROR; UndoSplits[destSpan,source,event] }; END.