EditSpanSupportImpl.mesa; written by Bill Paxton, June 1981
edited by McGregor, February 14, 1983 1:59 pm
edited by Bill Paxton, August 10, 1983 4:25 pm
edited by Maxwell, January 5, 1983 12:47 pm
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] = {
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 ← 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�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 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] = {
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 ← 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] = {
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: 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
check assertions
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] = {
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] ← 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] = {
create tree of parents
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[TiogaNode.invalidItemClassID]
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;
check if done
IF node=sourceFirst THEN first ← new;
IF node=sourceLast THEN RETURN [[[first,firstLoc],[new,lastLoc]]];
go to next node
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
take care of parent
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 };
check if have just finished the contents of a branch and now need to do children
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] = {
split off head or tail sections of spans so have spans of complete branches 
Break: PROC [root: RefBranchNode, node: Ref, before: BOOL] RETURNS [newLoc: BranchLoc] = {
newLoc.node ← BreakStatement[alphaRoot, node, before, event];
Use newLoc.where to encode whether or not broke the statement.
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: BOOLFALSE]
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] = {
This should really be changed so that it will use the info saved on the undo log. This doesn't currently take care of break from way down in the contents.
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.