EditSpanSupportImpl.mesa
Copyright Ó 1985, 1986, 1988 by Xerox Corporation. All rights reserved.
written by Bill Paxton, June 1981
last edit by Bill Paxton, November 9, 1982 10:30 am
Last Edited by: Maxwell, January 5, 1983 12:47 pm
Michael Plass, March 29, 1985 4:01:21 pm PST
Doug Wyatt, February 17, 1988 5:42:43 pm PST
DIRECTORY
EditSpan USING [Inherit, Merge, NodeOrder, Place, Split],
EditSpanSupport USING [ApplyProc, Event, LastOfSlice, MaxLen, NeededNestingChange, NodeItself, Slice, SliceArray],
TextEdit USING [Size],
TextNode USING [LastSibling, Location, NewTextNode, Next, Node, NodeRep, nullLocation, nullSpan, Parent, Root, Span, StepBackward, StepForward];
EditSpanSupportImpl: CEDAR MONITOR
IMPORTS EditSpan, EditSpanSupport, TextEdit, TextNode
EXPORTS EditSpanSupport, EditSpan
= BEGIN OPEN EditSpanSupport;
Node: TYPE ~ TextNode.Node;
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: Node] 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: Node, 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: Node;
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: Node]
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: Node ← 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: Node ← bottom[depth];
FOR node: Node ← 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: Node, 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: Node ← 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: Node;
UNTIL depth = 0 DO
child: Node ← 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: Node;
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.NodeRep];
new.rope ← node.rope;
new.charSets ← node.charSets;
new.charLooks ← node.charLooks;
new.charProps ← node.charProps;
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: Node ← s2[i];
FOR n:Node ← 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: Node] 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: Node] RETURNS [slice: Slice] = {
result is same as MakeSlices[node].before
Slicer: PROC [node: Node, 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: Node, 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: Node;
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: Node, event: Event, tail: BOOLFALSE]
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: Node;
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.