[Cyan]<Tioga2>Base>TiogaPathOpsImpl.mesa!1

TiogaPathOpsImpl.mesa; Written by Paxton, July 1983

Edited by Paxton, August 16, 1983 1:17 pm

DIRECTORY

TiogaPathOps,

CreateNode USING [CreateInternalRep],

NodeProps,

TiogaLooks,

TiogaNode,

TiogaItemClass,

TiogaBasicClass,

TiogaNodeOps,

Rope,

RopeEdit;

TiogaPathOpsImpl: CEDAR PROGRAM

IMPORTS CreateNode, RopeEdit, NodeProps, TiogaNodeOps

EXPORTS TiogaPathOps

SHARES TiogaNode =

BEGIN OPEN TiogaPathOps;

ROPE: TYPE = Rope.ROPE;

RefBranchNode: TYPE = TiogaNode.RefBranchNode;

RefTextNode: TYPE = TiogaNode.RefTextNode;

RefBoxNode: TYPE = TiogaNode.RefBoxNode;

RefListNode: TYPE = TiogaNode.RefListNode;

Span: TYPE = TiogaNode.Span;

Parent: PUBLIC PROC [p: Path] RETURNS [Path] = {

If p points to root of template or actual arg, Parent returns parent of corresponding application or formal arg.

node: Ref;

IF (node ← p.node)=NIL OR node.deleted THEN RETURN [nullPath];

UNTIL node.last DO node ← node.next; ENDLOOP;

IF node.next # NIL THEN RETURN [[node.next, p.path]];

IF p.path=NIL THEN RETURN [nullPath];

p ← p.path^; -- go back to the formal or the application and find parent of that

ENDLOOP };

GetTemplate: PROC [name, styleName: TiogaNode.Name] RETURNS [Ref] = {

RETURN [NIL] };

GetActualArg: PROC [formal: Path] RETURNS [Ref] = {

RETURN [NIL] };

GetStyleName: PROC [p: Path] RETURNS [styleName: TiogaNode.Name] = {

RETURN [TiogaNode.nullName] };

ConstructRefPath: PROC [p: Path] RETURNS [ref: REF Path] = {

If path is of form [node, NIL], then save ref to it away on node's property list since can reuse it.

Could consider doing this for case in which p.path # NIL if take care to avoid hanging onto ref's to nodes that have been deleted.

IF p.path # NIL THEN RETURN [NEW[Path ← p]];

IF (ref ← NARROW[NodeProps.GetProp[p.node, $RefPath]])=NIL THEN -- create one

NodeProps.PutProp[p.node, $RefPath, ref ← NEW[Path ← p]];

RETURN [ref] };

GetTemplatePath: PROC [application: Path] RETURNS [template: Path] = {

name: TiogaNode.Name = NodeProps.GetTemplateName[node];

styleName: TiogaNode.Name = GetStyleName[p];

templateNode: Ref ← GetTemplate[name, styleName];

refApplicationPath: REF Path = ConstructRefPath[application];

save back pointer with template to application

RETURN [[templateNode, refApplicationPath]] };

RETURN [nullPath] };

GetArgPath: PROC [formal: Path] RETURNS [actual: Path] = {

Must take care of case in which actual parameter is an application or a formal. Keep going until find a normal node.

RETURN [nullPath] };

Sib: PROC [p: Path] RETURNS [Path] = {

This is like Next but doesn't create internal rep for branches

If p points to root of template or actual arg, Sib returns sibling of corresponding application or formal arg.

node: Ref;

IF (node ← p.node)=NIL THEN RETURN [nullPath];

IF ~node.last THEN {

p ← [node.next, p.path];

RETURN [SELECT node.templateInfo FROM

normal => p,

application => GetTemplatePath[p],

formal => GetArgPath[p],

ENDCASE => ERROR] };

IF node.next # NIL OR p.path = NIL THEN RETURN [nullPath];

p ← p.path^; -- go back to the formal or the application and find Sib of that

ENDLOOP };

Contents: PUBLIC PROC [p: Path] RETURNS [Path] = BEGIN

node: Ref;

IF p.node=NIL THEN RETURN [nullPath];

WITH p.node SELECT FROM

br: RefBranchNode => { CheckInternalRep[br]; node ← br.contents };

bx: RefBoxNode => node ← bx.contents;

ls: RefListNode => node ← ls.contents;

ENDCASE => RETURN [nullPath];

IF node=NIL THEN RETURN [nullPath];

p ← [node, p.path];

RETURN [SELECT node.templateInfo FROM

normal => p,

application => GetTemplatePath[p],

formal => GetArgPath[p],

ENDCASE => ERROR];

END;

BranchChild: PUBLIC PROC [p: Path] RETURNS [Path] = BEGIN

n: RefBranchNode = TiogaNodeOps.NarrowToBranchNode[p.node];

node: RefBranchNode;

IF n=NIL THEN RETURN [nullPath];

CheckInternalRep[n];

IF (node ← n.child)=NIL THEN RETURN [nullPath];

CheckInternalRep[node];

p ← [node, p.path];

RETURN [SELECT node.templateInfo FROM

normal => p,

application => GetTemplatePath[p],

formal => GetArgPath[p],

ENDCASE => ERROR];

END;

Root: PUBLIC PROC [p: Path] RETURNS [Path] = {

parent: Path;

IF (parent←Parent[p]).node=NIL THEN RETURN [p];

p ← parent;

ENDLOOP };

Next: PUBLIC PROC [p: Path] RETURNS [nxt: Path] = {

nxt ← Sib[p];

WITH nxt.node SELECT FROM

br: RefBranchNode => CheckInternalRep[br];

ENDCASE };

FirstSibling: PUBLIC PROC [p: Path, parent: Path ← nullPath] RETURNS [sib: Path] = {

Returns p if p is the first sibling

IF p.node=NIL THEN RETURN [nullPath];

IF parent.node=NIL THEN parent ← Parent[p];

IF parent.node=NIL THEN RETURN [nullPath];

RETURN [

IF TiogaNodeOps.IsBranch[p.node] AND TiogaNodeOps.IsBranch[parent.node] THEN BranchChild[parent]

ELSE Contents[parent]] };

LastSibling: PUBLIC PROC [p: Path] RETURNS [sib: Path] = {

Returns p if p is the last sibling

IF p.node=NIL THEN RETURN [nullPath];

UNTIL (sib ← Sib[p]).node = NIL DO p ← sib; ENDLOOP;

WITH sib.node SELECT FROM

br: RefBranchNode => CheckInternalRep[br];

ENDCASE };

Previous: PUBLIC PROC [p: Path, parent: Path ← nullPath] RETURNS [sib: Path] = {

Returns NIL if p=FirstSibling[p]

IF p.node=NIL THEN RETURN [nullPath];

IF (sib ← FirstSibling[p, parent])=p OR sib.node=NIL THEN RETURN [nullPath];

UNTIL InlineEqual[sib ← Sib[p], p] DO p ← sib; ENDLOOP;

WITH sib.node SELECT FROM

br: RefBranchNode => CheckInternalRep[br];

ENDCASE };

LastWithin: PUBLIC PROC [p: Path] RETURNS [Path] = {

nxt: Path;

IF p.node=NIL THEN RETURN [nullPath];

IF ~TiogaNodeOps.IsBranch[p.node] OR (nxt ← BranchChild[p]).node=NIL THEN nxt ← Contents[p];

IF nxt.node=NIL THEN RETURN [p];

p ← LastSibling[nxt];

ENDLOOP };

Forward: PUBLIC PROC [p: Path] RETURNS [nx: Path, levelDelta: INTEGER] = {

returns next branch in standard tree walk order

fakeLevel: INTEGER = 100;

nxLevel: INTEGER;

[nx, nxLevel] ← ForwardClipped[p, LAST[INTEGER], fakeLevel];

RETURN [nx, nxLevel-fakeLevel] };

ForwardClipped: PUBLIC PROC [p: Path, maxLevel: INTEGER, nodeLevel: INTEGER ← 0]

RETURNS [nx: Path, nxLevel: INTEGER] = {

like Forward, but limits how deep will go in tree

if pass nodeLevel=0, correct value will be computed

nxLevel = Level[nx] <= MAX[maxLevel,Level[node]]

IF nodeLevel <= 0 THEN nodeLevel ← Level[p];

IF nodeLevel < maxLevel AND (nx ← BranchChild[p]).node # NIL THEN

RETURN [nx, nodeLevel+1]; -- return the child

IF ~TiogaNodeOps.IsBranch[p.node] THEN RETURN [nullPath, 0];

DO -- move to next node, sibling or up* then sibling

IF (nx ← Next[p]).node # NIL THEN RETURN;

IF (p ← Parent[p]).node = NIL THEN RETURN [nullPath, 0]; -- move to the parent

nodeLevel ← nodeLevel-1;

ENDLOOP };

StepForwardNode: PUBLIC PROC [p: Path] RETURNS [nx: Path] = {

returns next node in standard tree walk order; visits branch contents before branch children

IF p.node=NIL THEN RETURN [nullPath];

nx ← Contents[p];

IF nx.node=NIL AND TiogaNodeOps.IsBranch[p.node] THEN nx ← BranchChild[p];

IF nx.node # NIL THEN RETURN; -- descend in the tree

IF (nx ← Next[p]).node # NIL THEN RETURN;

IF (nx ← Parent[p]).node = NIL THEN RETURN [nullPath];

IF ~TiogaNodeOps.IsBranch[p.node] AND TiogaNodeOps.IsBranch[nx.node] AND (p ← BranchChild[nx]).node # NIL THEN

RETURN [p]; -- have visited contents of this branch; now visit children

The previous node is not a branch, but its parent is.

This implies that previous node was last of branch contents since child of branch must be a branch.

p ← nx; -- move to the parent

ENDLOOP };

Backward: PUBLIC PROC [p: Path, parent: Path ← nullPath]

RETURNS [back: Path, backparent: Path, levelDelta: INTEGER] = {

returns preceeding node in standard tree walk order

backLevel: INTEGER;

fakeLevel: INTEGER = 100;

[back, backparent, backLevel] ← BackwardClipped[p, LAST[INTEGER], parent, fakeLevel];

RETURN [back, backparent, backLevel-fakeLevel] };

BackwardClipped: PUBLIC PROC [

p: Path, maxLevel: INTEGER, parent: Path ← nullPath, nodeLevel: INTEGER ← 0]

RETURNS [back: Path, backparent: Path, backLevel: INTEGER] = {

like Backward, but limits how deep will go in tree

backLevel = Level[back] <= MAX[maxLevel,Level[node]]

child, child2: Path;

IF parent.node=NIL THEN parent ← Parent[p];

IF parent.node=NIL OR ~TiogaNodeOps.IsBranch[p.node] THEN RETURN [nullPath, nullPath, 0];

IF nodeLevel <= 0 THEN nodeLevel ← Level[p];

IF (child ← Previous[p, parent]).node=NIL THEN -- p is first following parent

IF ~TiogaNodeOps.IsBranch[parent.node] THEN RETURN [nullPath, nullPath, 0]

ELSE RETURN [parent, Parent[parent], nodeLevel-1];

DO -- go deeper in tree until reach maxLevel

IF nodeLevel >= maxLevel OR (child2 ← BranchChild[child]).node = NIL THEN

RETURN [child, parent, nodeLevel];

nodeLevel ← nodeLevel+1;

parent ← child; child ← LastSibling[child2]; ENDLOOP };

StepBackwardNode: PUBLIC PROC [p: Path, parent: Path ← nullPath]

RETURNS [back, backparent: Path] = {

child, child2: Path;

IF parent.node=NIL THEN parent ← Parent[p];

IF parent.node=NIL OR p.node=NIL THEN RETURN [nullPath, nullPath];

IF (child ← Previous[p, parent]).node=NIL THEN RETURN [parent, Parent[parent]];

DO -- find last node within predecessor

IF ~TiogaNodeOps.IsBranch[child.node] OR (child2 ← BranchChild[child]).node=NIL THEN

child2 ← Contents[child];

IF child2.node=NIL THEN RETURN [child, parent];

parent ← child; child ← LastSibling[child2]; ENDLOOP };

Equal: PUBLIC PROC [p1, p2: Path] RETURNS [yes: BOOL] = { RETURN [InlineEqual[p1, p2]] };

InlineEqual: PROC [p1, p2: Path] RETURNS [yes: BOOL] = INLINE BEGIN

IF p1.node # p2.node THEN RETURN [FALSE];

IF p1.path = p2.path THEN RETURN [TRUE];

IF p1.path = NIL OR p2.path = NIL THEN RETURN [FALSE];

p1 ← p1.path^; p2 ← p2.path^;

ENDLOOP;

END;

Level: PUBLIC PROC [p: Path] RETURNS [level: INTEGER] = {

level ← 0; UNTIL (p ← Parent[p]).node=NIL DO level ← level+1; ENDLOOP };

BackLoc: PUBLIC PROC [loc: Location] RETURNS [new: Location] = {

text: RefTextNode;

new.path ← StepBackwardNode[loc.path].back;

new.where ← IF loc.where=TiogaNode.NodeItself OR (text ← TiogaNodeOps.NarrowToTextNode[new.path.node])=NIL

THEN TiogaNode.NodeItself ELSE RopeEdit.Size[text.rope] };

ForwardLoc: PUBLIC PROC [loc: Location] RETURNS [new: Location] = {

new.path ← StepForwardNode[loc.path];

new.where ← IF loc.where=TiogaNode.NodeItself OR TiogaNodeOps.NarrowToTextNode[new.path.node]=NIL

THEN TiogaNode.NodeItself ELSE 0 };

LastLocWithin: PUBLIC PROC [p: Path] RETURNS [Location] = {

last: Path = LastWithin[p];

lastText: RefTextNode = TiogaNodeOps.NarrowToTextNode[last.node];

where: Offset = IF lastText # NIL THEN RopeEdit.Size[lastText.rope] ELSE TiogaNode.NodeItself;

RETURN [[last,where]] };

BadArgs: PUBLIC ERROR = CODE;

LocNumber: PUBLIC PROC [at: Location, break: NAT ← 1, skipCommentNodes: BOOL ← FALSE]

RETURNS [count: Offset] = { RETURN [LocOffset[[Root[at.path],0],at,break,skipCommentNodes]] };

LocOffset: PUBLIC PROC [loc1, loc2: Location,

break: NAT ← 1, skipCommentNodes: BOOL ← FALSE] RETURNS [count: Offset] = {

returns character offset of location2 relative to location1

path: Path ← loc2.path;

p: Path ← loc1.path;

txt: RefTextNode;

count ← IF loc2.where # TiogaNode.NodeItself THEN loc2.where ELSE 0;

count ← count - MAX[loc1.where,0];

DO -- add in counts for text nodes before location

IF InlineEqual[p, path] THEN RETURN;

IF p.node=NIL THEN ERROR BadArgs;

txt ← TiogaNodeOps.NarrowToTextNode[p.node];

IF txt # NIL AND (~skipCommentNodes OR ~txt.comment) THEN

count ← count+RopeEdit.Size[txt.rope]+break;

p ← StepForwardNode[p];

ENDLOOP };

LocRelative: PUBLIC PROC [location: Location, count: Offset,

break: NAT ← 1, skipCommentNodes: BOOL ← FALSE] RETURNS [Location] = {

p: Path ← location.path;

size, lastWhere, where: Offset;

last: Path ← p;

IF count=0 AND Parent[p].node=NIL THEN -- avoid returning root node

RETURN [[BranchChild[p],0]]; -- return first child of root instead

lastWhere ← where ← MAX[location.where,0]; -- where we are in the current node

WHILE p.node # NIL DO

txt: RefTextNode ← TiogaNodeOps.NarrowToTextNode[p.node];

IF txt # NIL AND (~skipCommentNodes OR ~txt.comment) THEN {

lastWhere ← size ← RopeEdit.Size[txt.rope];

IF (count ← count-(size-where)) <= 0 THEN RETURN [[p,MAX[0,count+size]]];

count ← count-break; last ← p };

p ← StepForwardNode[p];

where ← 0;

ENDLOOP;

RETURN [[last,lastWhere]] };

CheckInternalRep: PROC [br: TiogaNode.RefBranchNode] = INLINE {

IF ~br.internalRepCreated THEN CreateNode.CreateInternalRep[br] };

Apply: PUBLIC PROC [span: Span, proc: ApplyProc] = {

path, last: Path;

start, lastLen: Offset;

IF (path ← span.start.path).node = NIL THEN RETURN;

IF (last ← span.end.path).node = NIL THEN RETURN;

IF (start ← span.start.where)=TiogaNode.NodeItself THEN start ← 0;

IF span.end.where=TiogaNode.NodeItself THEN lastLen ← LAST[Offset]

ELSE IF span.end.where=LAST[Offset] THEN lastLen ← LAST[Offset]

ELSE { lastLen ← span.end.where+1; IF Equal[path, last] THEN lastLen ← lastLen-start };

lastOne: BOOL = Equal[path, last];

IF proc[path, start, IF lastOne THEN lastLen ELSE LAST[Offset]] THEN RETURN;

IF lastOne OR (path ← StepForwardNode[path]).node=NIL THEN RETURN;

start ← 0;

ENDLOOP;

};

END.