<> <> <> <> <> <> <> <<>> DIRECTORY EditSpan USING [Inherit, Merge, NodeOrder, Place, Split], EditSpanSupport USING [ApplyProc, Event, LastOfSlice, MaxLen, NeededNestingChange, NodeItself, Slice, SliceArray], TextEdit USING [Size], TextNode USING [Body, LastSibling, Location, NewTextNode, Next, nullLocation, nullSpan, Parent, Ref, Root, Span, StepBackward, StepForward]; EditSpanSupportImpl: CEDAR MONITOR IMPORTS EditSpan, EditSpanSupport, TextEdit, TextNode EXPORTS EditSpanSupport, EditSpan = BEGIN OPEN EditSpanSupport; Ref: TYPE ~ TextNode.Ref; RefTextNode: TYPE ~ TextNode.Ref; Location: TYPE ~ TextNode.Location; Place: TYPE ~ EditSpan.Place; NodeOrder: TYPE ~ EditSpan.NodeOrder; Span: TYPE ~ TextNode.Span; nullSpan: Span ~ TextNode.nullSpan; <<***** Slice support routines>> freeSlice: Slice; -- free list of slices numFreeSlices: NAT _ 0; maxFreeSlices: NAT = 15; minSliceSize: NAT = 10; GetSlice: PUBLIC ENTRY PROC [len: NAT] RETURNS [slice: Slice] = { IF freeSlice # NIL THEN { -- look on free list prev: Slice; IF freeSlice.maxLength >= len THEN { -- take the first from list slice _ freeSlice; freeSlice _ freeSlice.next; slice.next _ NIL; numFreeSlices _ numFreeSlices-1; RETURN }; prev _ freeSlice; FOR s: Slice _ freeSlice.next, s.next UNTIL s=NIL DO IF s.maxLength >= len THEN { -- take this one prev.next _ s.next; s.next _ NIL; numFreeSlices _ numFreeSlices-1; RETURN [s] }; prev _ s; ENDLOOP }; RETURN [NEW[SliceArray[MAX[len,minSliceSize]]]] }; FreeSlice: PUBLIC ENTRY PROC [slice: Slice] = { IF slice=NIL OR numFreeSlices >= maxFreeSlices OR slice.maxLength < minSliceSize THEN RETURN; FOR i:NAT IN [0..slice.length) DO slice[i] _ NIL; ENDLOOP; slice.next _ freeSlice; freeSlice _ slice; numFreeSlices _ numFreeSlices+1 }; MakeSlices: PROC [node: Ref] RETURNS [before, after: Slice] = { <<>> <> <> <> <<>> last: NAT; Slicer: PROC [node: Ref, height: NAT] RETURNS [level: NAT] = { height _ height+1; IF node=NIL THEN { -- have gone beyond root before _ GetSlice[height]; before.kind _ before; after _ GetSlice[height+1]; after.kind _ after; RETURN [0] }; level _ Slicer[TextNode.Parent[node],height]; before[level] _ node; after[level] _ TextNode.Next[node]; RETURN [level+1] }; IF node=NIL THEN RETURN; last _ Slicer[node,0]; before.length _ last; IF node.child # NIL THEN { after[last] _ node.child; after.length _ last+1 } ELSE after.length _ last; FOR i: NAT _ after.length, i-1 DO -- delete trailing NIL's from after IF i=0 THEN { after.length _ 0; EXIT }; IF after[i-1] # NIL THEN { after.length _ i; EXIT }; ENDLOOP }; InsertPrefix: PROC [first, last: Slice, firstLen: NAT] RETURNS [new: Slice] = { <<>> <> <> <> <<>> newLen: NAT; IF first = NIL OR last = NIL OR first.kind # before OR last.kind # before OR first.length < firstLen THEN ERROR; new _ GetSlice[newLen _ firstLen + last.length]; new.kind _ before; new.length _ newLen; FOR i: NAT IN [0..firstLen) DO new[i] _ first[i]; ENDLOOP; FOR i: NAT IN [0..last.length) DO new[firstLen+i] _ last[i]; ENDLOOP }; 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 _ LastOfSlice[before]; IF afterLen = beforeLen+1 THEN { -- adopt children b.child _ a _ LastOfSlice[after]; IF a # NIL AND beforeLen > 0 THEN TextNode.LastSibling[a].next _ b } ELSE b.child _ NIL; IF beforeLen=0 THEN RETURN; FOR i: NAT _ beforeLen-1, i-1 DO -- do successors 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 TextNode.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 _ InsertPrefix[before,bottom,depth]; Splice[fullBottom,after]; Splice[before,top,depth]; FreeSlice[fullBottom] }; BadBand: PUBLIC ERROR = CODE; DescribeBand: PUBLIC PROC [first, last: Ref] RETURNS [before, after, top, bottom: Slice, nesting: INTEGER, depth: NAT] = { <<>> <> <> <> <> <> <<>> BadBandError: PROC = { ERROR BadBand [! UNWIND => { FreeSlice[before]; FreeSlice[after]; FreeSlice[top]; FreeSlice[bottom] } ] }; pred: Ref _ TextNode.StepBackward[first]; 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] _ MakeSlices[pred]; nesting _ top.length-before.length; [bottom,after] _ 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], TextNode.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 LastOfSlice[top] # first THEN ERROR; IF before[before.length+nesting-2] # TextNode.Parent[first] THEN ERROR; IF LastOfSlice[bottom] # last THEN ERROR }; DeletePrefix: PUBLIC PROC [slice: Slice, depth: NAT] = { <<>> <> <<>> newLen: NAT; IF slice.length < depth THEN ERROR; newLen _ slice.length-depth; FOR i:NAT IN [0..newLen) DO slice[i] _ slice[i+depth]; ENDLOOP; FOR i:NAT IN [newLen..slice.length) DO slice[i] _ NIL; ENDLOOP; slice.length _ newLen }; DestSlices: PUBLIC PROC [dest: Ref, where: EditSpan.Place] RETURNS [before, after: Slice, nesting: INTEGER] = { <<>> <> <> <> <<>> SELECT where FROM after => { [before,after] _ MakeSlices[dest]; nesting _ 0 }; child => { [before,after] _ MakeSlices[dest]; nesting _ 1 }; before => { pred: Ref _ TextNode.StepBackward[dest]; [before,after] _ MakeSlices[pred]; nesting _ after.length-before.length }; ENDCASE => ERROR }; CreateDest: PUBLIC PROC [depth: NAT] RETURNS [dest: Location] = { <> node: Ref; UNTIL depth = 0 DO child: Ref _ TextNode.NewTextNode[]; IF node # NIL THEN { node.child _ child; child.next _ node }; node _ child; depth _ depth-1; ENDLOOP; RETURN [[node, NodeItself]] }; CopySpan: PUBLIC PROC [span: Span] RETURNS [result: Span] = { node, sourceFirst, sourceLast, child, new, prev, parent, first: Ref; firstLoc, lastLoc: INT; sourceFirst _ span.start.node; firstLoc _ span.start.where; sourceLast _ span.end.node; lastLoc _ span.end.where; IF (node _ sourceFirst)=NIL THEN RETURN [nullSpan]; parent _ TextNode.NewTextNode[]; -- parent for the span DO -- create new node each time through the loop new _ NEW[TextNode.Body]; new.rope _ node.rope; new.runs _ node.runs; IF prev#NIL THEN { prev.last _ FALSE; prev.next _ new } ELSE parent.child _ new; -- insert new new.new _ new.last _ TRUE; new.next _ parent; prev _ new; EditSpan.Inherit[node,new,TRUE]; -- inherit properties from node IF node=sourceFirst THEN first _ new; IF node=sourceLast THEN { RETURN [[[first,firstLoc], [new,lastLoc]]] }; <> IF (child _ node.child) # NIL THEN { -- descend in the tree node _ child; parent _ new; prev _ NIL } ELSE DO -- move to next node, sibling or up* then sibling IF NOT node.last THEN { node _ node.next; EXIT }; prev _ parent; IF (parent _ parent.next) = NIL THEN { -- need a new parent parent _ TextNode.NewTextNode[]; parent.child _ prev; prev.next _ parent }; IF (node _ node.next)=NIL THEN RETURN [nullSpan]; -- bad arg span ENDLOOP; ENDLOOP }; CompareSliceOrder: PUBLIC PROC [s1, s2: Slice] RETURNS [order: EditSpan.NodeOrder] = { <<>> <> <> <> <> <> <<>> s1Len, s2Len: NAT; IF s1=NIL OR s2=NIL OR (s1Len_s1.length)=0 OR (s2Len_s2.length)=0 OR s1[0] # s2[0] THEN RETURN [disjoint]; IF s1.kind # before OR s2.kind # before THEN ERROR; -- only valid for parent slices FOR i:NAT _ 1, i+1 DO -- know that s1[j]=s2[j] for j { IF i=s2Len THEN RETURN [same]; -- s1Last=s2Last RETURN [before] }; -- s1Last is a parent of s2Last s2Len => RETURN [after]; -- s2Last is a parent of s1Last ENDCASE; IF s1[i] # s2[i] THEN { -- they are siblings, so can check order by Next's s2Node: Ref _ s2[i]; FOR n:Ref _ TextNode.Next[s1[i]], TextNode.Next[n] DO -- search from s1 to s2 SELECT n FROM s2Node => RETURN [before]; NIL => RETURN [after]; ENDCASE; ENDLOOP }; ENDLOOP }; CompareNodeOrder: PUBLIC PROC [node1, node2: Ref] RETURNS [order: EditSpan.NodeOrder] = { s1, s2: Slice; IF node1=NIL OR node2=NIL THEN RETURN [disjoint]; IF node1=node2 THEN RETURN [same]; s1 _ MakeParentSlice[node1]; s2 _ MakeParentSlice[node2]; order _ CompareSliceOrder[s1,s2]; FreeSlice[s1]; FreeSlice[s2] }; MakeParentSlice: PROC [node: Ref] RETURNS [slice: Slice] = { <> Slicer: PROC [node: Ref, height: NAT] RETURNS [level: NAT] = { height _ height+1; IF node=NIL THEN { -- have gone beyond root slice _ GetSlice[height]; slice.kind _ before; RETURN [0] }; level _ Slicer[TextNode.Parent[node],height]; slice[level] _ node; RETURN [level+1] }; IF node=NIL THEN RETURN; slice.length _ Slicer[node,0] }; DoSplits: PUBLIC PROC [alpha, beta: Span, event: Event] RETURNS [Span, Span] = { <> MakeSplit: PROC [node: Ref, offset: INT] = { FixLoc: PROC [old: Location] RETURNS [newLoc: Location] = { where: INT; 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 THEN RETURN; new _ EditSpan.Split[TextNode.Root[node], [node,offset],event]; alpha.start _ FixLoc[alpha.start]; alpha.end _ FixLoc[alpha.end]; beta.start _ FixLoc[beta.start]; beta.end _ FixLoc[beta.end] }; IF alpha.start.where # NodeItself THEN MakeSplit[alpha.start.node,alpha.start.where]; IF beta.start.where # NodeItself THEN MakeSplit[beta.start.node,beta.start.where]; IF alpha.end.where # NodeItself THEN MakeSplit[alpha.end.node,alpha.end.where+1]; IF beta.end.where # NodeItself THEN MakeSplit[beta.end.node,beta.end.where+1]; RETURN [alpha,beta] }; DoSplits2: PUBLIC PROC [dest: Location, source: Span, where: EditSpan.Place, nesting: INTEGER, event: Event] RETURNS [Location, Span, EditSpan.Place, INTEGER] = { destLoc: Location; destSpan: Span _ [dest,TextNode.nullLocation]; [destSpan,source] _ DoSplits[destSpan,source,event]; destLoc _ destSpan.start; IF dest.where # NodeItself THEN { -- did a split destLoc _ BackLoc[destLoc]; where _ after; nesting _ 0 }; RETURN [destLoc, source, where, nesting] }; ReMerge: PUBLIC PROC [alpha, beta: Span, merge: Ref, event: Event, tail: BOOL _ FALSE] RETURNS [Span, Span] = { loc: Location; FixLoc: PROC [old: Location] RETURNS [Location] = { where: INT; IF old.node = merge THEN SELECT where _ old.where FROM = NodeItself => ERROR; ENDCASE => RETURN [[loc.node,loc.where+where]]; RETURN [old] }; IF tail THEN merge _ TextNode.StepForward[merge]; loc _ EditSpan.Merge[TextNode.Root[merge],merge,event]; alpha.start _ FixLoc[alpha.start]; alpha.end _ FixLoc[alpha.end]; beta.start _ FixLoc[beta.start]; beta.end _ FixLoc[beta.end]; RETURN [alpha,beta] }; UndoSplits: PUBLIC PROC [alpha, beta: Span, event: Event] RETURNS [Span, Span] = { 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]; RETURN [alpha,beta] }; UndoSplits2: PUBLIC PROC [dest: Location, source: Span, event: Event] RETURNS [Location, Span] = { destSpan: Span _ [dest,TextNode.nullLocation]; [destSpan,source] _ UndoSplits[destSpan,source,event]; RETURN [destSpan.end,source] }; SliceOrder: PUBLIC PROC [alpha, beta: Span, aBefore, aBottom, bBefore, bBottom: Slice] RETURNS [overlap: BOOL, head, tail: Span, startOrder, endOrder: EditSpan.NodeOrder] = { IF CompareSliceOrder[aBottom,bBefore]#after --alphaend before betastart OR CompareSliceOrder[aBefore,bBottom]#before --alphastart after betaend THEN { overlap _ FALSE; RETURN }; startOrder _ CompareSliceOrder[aBefore,bBefore]; endOrder _ CompareSliceOrder[aBottom,bBottom]; head _ SELECT startOrder FROM before => [alpha.start,BackLoc[beta.start]], same => nullSpan, after => [beta.start,BackLoc[alpha.start]], ENDCASE => ERROR; tail _ SELECT endOrder FROM before => [ForwardLoc[alpha.end],beta.end], same => nullSpan, after => [ForwardLoc[beta.end],alpha.end], ENDCASE => ERROR; overlap _ TRUE; }; <<***** Miscellaneous>> Apply: PUBLIC PROC [span: Span, proc: ApplyProc] = { node, last: Ref; start, lastLen: INT; IF (node _ span.start.node) = NIL THEN RETURN; IF (last _ span.end.node) = NIL THEN RETURN; IF (start _ span.start.where)=NodeItself THEN start _ 0; IF span.end.where=NodeItself THEN lastLen _ MaxLen ELSE IF span.end.where=MaxLen THEN lastLen _ MaxLen ELSE { lastLen _ span.end.where+1; IF node=last THEN lastLen _ lastLen-start }; DO IF proc[node, start, IF node=last THEN lastLen ELSE MaxLen] THEN RETURN; IF node=last OR (node _ TextNode.StepForward[node])=NIL THEN RETURN; start _ 0; ENDLOOP; }; BackLoc: PUBLIC PROC [loc: Location] RETURNS [new: Location] = { new.node _ TextNode.StepBackward[loc.node]; new.where _ IF loc.where=NodeItself THEN NodeItself ELSE TextEdit.Size[new.node] }; ForwardLoc: PUBLIC PROC [loc: Location] RETURNS [new: Location] = { new.node _ TextNode.StepForward[loc.node]; new.where _ IF loc.where=NodeItself THEN NodeItself ELSE 0 }; END.