***** 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] = {
before[0]=root; before[i]=Parent[before[i+1]]; before[before.length-1]=node
after[i]=Next[before[i]]
if node.child # NIL then after[before.length]=node.child
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] = {
new[i]=first[i] for i in [0..firstLen)
new[i+firstLen]=last[i] for i in [0..last.length)
new.length=last.length+firstLen
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] = {
join slices
make after[afterStart+i] be successor of before[beforeStart+i]
if more after's than before's, adopt as children of last before
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�ter[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] = {
do Splices to insert (top-bottom) between (before-after)
nesting tells how to offset last of before vs. last of top
before[before.length-1+nesting] will be predecessor of top[top.length-1]
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] = {
top[top.length-1] = first
before[before.length-1+nesting] = predecessor of first
bottom[bottom.length-1] = last
raises BadBand error if last doesn't follow first in tree structure
or if first or last is root node
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
check assertions
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] = {
remove entries from start of slice
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] = {
where = after means insert starting as sibling after dest
where = child means insert starting as child of dest
where = before means insert starting as sibling before dest
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] = {
create tree of parents
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]]]
};
go to next node
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] = {
determines relative order in tree of last nodes in the slices
returns "same" if slices are identical
returns "before" if last node of s1 comes before last node of s2
returns "after" if last node of s1 comes after last node of s2
returns "disjoint" if slices are not from the same tree
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<i
SELECT i
FROM
s1Len => {
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] = {
result is same as MakeSlices[node].before
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] = {
split off head or tail sections of text
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;
};