QueryTextNodeImpl.mesa
Copyright Ó 1985, 1986 by Xerox Corporation. All rights reserved.
written by Bill Paxton, March 1981
last edit by Bill Paxton, August 11, 1982 9:51 am
Doug Wyatt, March 3, 1985 3:01:39 pm PST
Michael Plass, March 27, 1985 3:50:32 pm PST
Rick Beach, March 27, 1985 10:13:12 am PST
Doug Terry, May 12, 1987 10:09:10 am PDT
This is a modified version of TextNodeImpl.mesa that retrieves nodes from a LoganBerry database as they are requested. Nodes with format="Query" are dynamically replaced with the results obtained from running the query specified by the node's contents. The query need not always be run in its entirety; in many cases the query node can be replaced by two nodes: the first being the first database entry returned by the query and the second being a new query (specifcally a database cursor) to generate the remaining entries.
Note: All of the procedures in this module assume that any nodes passed as inputs are regular text nodes (format#$query) and ensure that any nodes returned as results are regular text nodes.
DIRECTORY
IO USING [atom, BreakProc, EndOfStream, GetTokenRope, IDProc, PutFR, RIS, rope, STREAM],
LoganBerry USING [Entry, Open],
LoganQuery USING [AttributePatterns, ComplexCursor, NextEntry, QueryEntries, ReadAttributePatterns, SyntaxError],
NodeProps USING [GetProp, PutProp],
Rope USING [Concat, ROPE, Size],
TextLooks USING [Runs],
TextNode USING [Body, Location, MaxLen, NodeItself, NodeProps, Ref, RefTextNode, Span];
QueryTextNodeImpl: CEDAR PROGRAM
IMPORTS IO, LoganBerry, LoganQuery, NP: NodeProps, Rope
EXPORTS TextNode
= BEGIN OPEN TextNode;
ROPE: TYPE ~ Rope.ROPE;
MakeNodeLoc: PUBLIC PROC [n: Ref] RETURNS [Location]
= { RETURN [[node: n, where: NodeItself]] };
MakeNodeSpan: PUBLIC PROC [first, last: Ref] RETURNS [Span]
= { RETURN [[MakeNodeLoc[first], MakeNodeLoc[last]]] };
NarrowToTextNode: PUBLIC PROC [n: Ref] RETURNS [txt: RefTextNode] ~ {RETURN [n]};
For backwards compatability.
NewTextNode: PUBLIC PROC RETURNS [txt: RefTextNode] = {
txt ← NEW[Body]; txt.last ← TRUE
};
Parent: PUBLIC PROC [n: Ref] RETURNS [Ref] = { RETURN [InlineParent[n]] };
InlineParent: PROC [n: Ref] RETURNS [Ref] = INLINE {
DO IF n=NIL OR n.deleted THEN RETURN [NIL];
IF n.last THEN RETURN [QueryToText[n.next]];
n ← n.next;
ENDLOOP;
};
Root: PUBLIC PROC [n: Ref] RETURNS [Ref] = {
applies Parent repeatedly until reaches root
p: Ref;
DO IF (p ← InlineParent[n])=NIL THEN RETURN [IF n=NIL OR n.deleted THEN NIL ELSE n];
n ← p;
ENDLOOP;
};
Next: PUBLIC PROC [n: Ref] RETURNS [Ref] = {
RETURN[IF n=NIL OR n.last OR n.deleted THEN NIL ELSE QueryToText[n.next]];
};
Previous: PUBLIC PROC [n: Ref, parent: Ref ← NIL] RETURNS [nx: Ref] = {
nx2: Ref;
IF parent=NIL THEN parent ← InlineParent[n];
IF n=NIL OR parent=NIL OR (nx ← parent.child)=n THEN RETURN [NIL];
DO IF (nx2←nx.next)=n THEN RETURN [QueryToLastText[nx]]; nx ← nx2; ENDLOOP;
};
Forward: PUBLIC PROC [node: Ref] RETURNS [nx: Ref, levelDelta: INTEGER] = {
[nx, levelDelta] ← InlineForward[node];
};
InlineForward: PROC [node: Ref] RETURNS [nx: Ref, levelDelta: INTEGER] = INLINE {
returns next node in standard tree walk order
child: Ref;
IF node=NIL THEN RETURN [NIL, 0];
IF (child ← node.child) # NIL THEN RETURN [QueryToText[child, node], 1]; -- descend in the tree
levelDelta ← 0;
DO -- move to next node, sibling or up* then sibling
IF NOT node.last THEN RETURN [QueryToText[node.next], levelDelta]; -- the sibling
IF (node ← node.next) = NIL THEN RETURN [NIL, levelDelta]; -- the parent
levelDelta ← levelDelta-1;
ENDLOOP;
};
RawInlineForward: PROC [node: Ref] RETURNS [nx: Ref, levelDelta: INTEGER] = INLINE {
returns next node in standard tree walk order
child: Ref;
IF node=NIL THEN RETURN [NIL, 0];
IF (child ← node.child) # NIL THEN RETURN [child, 1]; -- descend in the tree
levelDelta ← 0;
DO -- move to next node, sibling or up* then sibling
IF NOT node.last THEN RETURN [node.next, levelDelta]; -- the sibling
IF (node ← node.next) = NIL THEN RETURN [NIL, levelDelta]; -- the parent
levelDelta ← levelDelta-1;
ENDLOOP;
};
Backward: PUBLIC PROC [node: Ref, parent: Ref ← NIL]
RETURNS [back, backparent: Ref, levelDelta: INTEGER] = {
returns preceeding node in standard tree walk order
child, child2: Ref;
IF parent = NIL THEN parent ← InlineParent[node];
IF parent = NIL OR node = NIL THEN RETURN [NIL, NIL, 0];
IF (child ← parent.child) = node THEN RETURN [parent, Parent[parent], -1];
DO IF child.last THEN ERROR; -- incorrect value supplied for parent
IF (child2 ← child.next)=node THEN EXIT;
child ← child2;
ENDLOOP;
levelDelta ← 0;
DO IF (child2 ← LastChild[child]) = NIL THEN RETURN [QueryToLastText[child], parent, levelDelta];
levelDelta ← levelDelta+1;
parent ← child; child ← child2;
ENDLOOP;
};
StepForward: PUBLIC PROC [node: Ref] RETURNS [Ref]
= { RETURN[Forward[node].nx] };
returns next node in standard tree walk order
StepBackward: PUBLIC PROC [node: Ref, parent: Ref ← NIL] RETURNS [Ref]
= { RETURN[Backward[node, parent].back] };
returns preceding node in standard tree walk order
Level: PUBLIC PROC [node: Ref] RETURNS [level: INTEGER] = {
Level[Root[x]] == 0; Level[FirstChild[n]]=Level[n]+1
level ← 0;
UNTIL (node ← InlineParent[node])=NIL DO level ← level+1 ENDLOOP;
};
ForwardClipped: PUBLIC PROC [
node: Ref, maxLevel: INTEGER, nodeLevel: INTEGER ← 0]
RETURNS [nx: Ref, 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]]
child: Ref;
IF node=NIL THEN RETURN [NIL, 0];
IF nodeLevel <= 0 THEN nodeLevel ← Level[node];
IF nodeLevel < maxLevel AND (child ← node.child) # NIL THEN
RETURN [QueryToText[child, node], nodeLevel+1]; -- return the child
DO -- move to next node, sibling or up* then sibling
IF NOT node.last THEN RETURN [QueryToText[node.next], nodeLevel]; -- return the sibling
IF (node ← node.next) = NIL THEN RETURN [NIL, 0]; -- go to the parent
nodeLevel ← nodeLevel-1;
ENDLOOP;
};
BackwardClipped: PUBLIC PROC [
node: Ref, maxLevel: INTEGER, parent: Ref ← NIL, nodeLevel: INTEGER ← 0]
RETURNS [back, backparent: Ref, backLevel: INTEGER] = {
like Backward, but limits how deep will go in tree
backLevel = Level[back] <= MAX[maxLevel, Level[node]]
child, child2: Ref;
IF parent = NIL THEN parent ← InlineParent[node];
IF parent = NIL OR node = NIL THEN RETURN [NIL, NIL, 0];
IF nodeLevel <= 0 THEN nodeLevel ← Level[node];
IF (child ← parent.child) = node THEN RETURN [parent, InlineParent[parent], nodeLevel-1];
DO -- search for sibling just before node
IF child.last THEN ERROR; -- incorrect value supplied for parent
IF (child2 ← child.next)=node THEN EXIT;
child ← child2;
ENDLOOP;
DO -- go deeper in tree until reach maxLevel
IF nodeLevel >= maxLevel OR (child2 ← LastChild[child]) = NIL THEN
RETURN [QueryToLastText[child], parent, nodeLevel];
nodeLevel ← nodeLevel+1;
parent ← child;
child ← child2;
ENDLOOP;
};
LocRelative: PUBLIC PROC [location: Location, count: INT ← 0,
break: NAT ← 1, skipCommentNodes: BOOL ← FALSE] RETURNS [Location] = {
n: Ref ← location.node;
size, lastSize, where: INT ← 0;
init: Ref ← n;
lastTxt: RefTextNode;
IF count=0 AND InlineParent[n]=NIL THEN
RETURN [[FirstChild[n], 0]]; -- avoid returning root node
where ← MAX[location.where, 0]; -- where we are in the current node
WHILE n # NIL DO
IF n # NIL AND (NOT skipCommentNodes OR NOT n.comment) THEN {
lastSize ← size ← Rope.Size[n.rope];
IF (count ← count-(size-where)) <= 0 THEN RETURN [[n, MAX[0, count+size]]];
lastTxt ← n;
count ← count-break;
};
[n, ] ← InlineForward[n];
where ← 0;
ENDLOOP;
IF lastTxt # NIL THEN RETURN [[lastTxt, lastSize]]; -- end of last text node
RETURN [[init, 0]];
};
LocWithin: PUBLIC PROC [n: Ref, count: INT, break: NAT ← 1, skipCommentNodes: BOOL ← FALSE] RETURNS [Location]
= { RETURN[LocRelative[[n, 0], count, break, skipCommentNodes]] };
BadArgs: PUBLIC ERROR = CODE;
LocOffset: PUBLIC PROC [loc1, loc2: Location, break: NAT ← 1, skipCommentNodes: BOOL ← FALSE] RETURNS [count: INT ← 0] = {
returns character offset of location2 relative to location1
node: Ref ← loc2.node;
n: Ref ← loc1.node;
count ← IF loc2.where # NodeItself THEN loc2.where ELSE 0;
count ← count - MAX[loc1.where, 0];
DO -- add in counts for text nodes before location
SELECT n FROM
node => RETURN;
NIL => ERROR BadArgs;
ENDCASE;
IF n # NIL AND (NOT skipCommentNodes OR NOT n.comment) THEN {
size: INT ← IF n.formatName#$query THEN Rope.Size[n.rope] ELSE 300;
count ← count+size+break;
};
[n, ] ← RawInlineForward[n];
ENDLOOP;
};
LocNumber: PUBLIC PROC [at: Location, break: NAT ← 1, skipCommentNodes: BOOL ← FALSE] RETURNS [count: INT]
= { RETURN[LocOffset[[Root[at.node], 0], at, break, skipCommentNodes]] };
returns character offset of location relative to root
FirstSibling: PUBLIC PROC [n: Ref] RETURNS [Ref] = {
RETURN[FirstChild[Parent[n]]];
};
LastSibling: PUBLIC PROC [n: Ref] RETURNS [Ref] = {
IF n=NIL THEN RETURN [NIL];
UNTIL n.last DO n ← n.next ENDLOOP;
RETURN[QueryToLastText[n]];
};
FirstChild: PUBLIC PROC [n: Ref] RETURNS [Ref] = {
RETURN[IF n=NIL THEN NIL ELSE QueryToText[n.child, n]];
};
LastChild: PUBLIC PROC [n: Ref] RETURNS [Ref] = {
RETURN[LastSibling[FirstChild[n]]];
};
LastWithin: PUBLIC PROC [n: Ref] RETURNS [Ref] = {
nxt: Ref;
IF n=NIL THEN RETURN [NIL];
IF (nxt ← n.child)=NIL THEN RETURN [n];
n ← nxt;
DO -- keep going to child of last sibling
IF n.last THEN {
IF (nxt ← n.child)=NIL THEN RETURN [QueryToLastText[n]];
n ← nxt
}
ELSE n ← n.next;
ENDLOOP;
};
LastLocWithin: PUBLIC PROC [n: Ref] RETURNS [Location] = {
last: Ref ← LastWithin[n];
where: INT ← IF last # NIL THEN Rope.Size[last.rope] ELSE NodeItself;
RETURN [[last, where]];
};
NthChild: PUBLIC PROC [n: Ref, location: INT ← 0] RETURNS [child: Ref] = {
note: NthChild[n, 0]==FirstChild[n]; NthChild[n, k+1]==Next[NthChild[n, k]]
IF n=NIL OR (child ← n.child)=NIL THEN RETURN;
DO IF location=0 THEN RETURN [QueryToText[child]];
child ← QueryToText[child];
IF child.last THEN RETURN [NIL];
child ← child.next;
location ← location-1;
ENDLOOP;
};
NthSibling: PUBLIC PROC [n: Ref, cnt: INT ← 0] RETURNS [Ref] = {
note: NthSibling[n, 0]==n; NthSibling[n, k+1]==Next[NthSibling[n, k]]
IF n=NIL THEN RETURN [NIL];
DO IF cnt=0 THEN RETURN [QueryToText[n]];
n ← QueryToText[n];
IF n.last THEN RETURN [NIL];
n ← n.next;
cnt ← cnt-1;
ENDLOOP;
};
CountChildren: PUBLIC PROC [n: Ref] RETURNS [count: INT ← 0] = {
child: Ref;
IF (child ← FirstChild[n])=NIL THEN RETURN;
DO count ← count+1;
child ← QueryToText[child];
IF child.last THEN RETURN;
child ← child.next;
ENDLOOP;
};
CountFollowing: PUBLIC PROC [n: Ref] RETURNS [count: INT ← 0] = {
IF n=NIL THEN RETURN;
UNTIL n.last DO
n ← n.next;
count ← count+1;
n ← QueryToText[n];
ENDLOOP;
};
CountToParent: PUBLIC PROC [n: Ref] RETURNS [count: INT ← 0, parent: Ref] = {
IF n=NIL THEN RETURN;
UNTIL n.last DO
n ← n.next;
count ← count+1;
n ← QueryToText[n];
ENDLOOP;
parent ← n.next;
parent ← QueryToText[parent];
};
CountToChild: PUBLIC PROC [parent, child: Ref] RETURNS [count: INT ← 0] = {
note: CountToChild[parent, FirstChild[parent]]==0
n: Ref;
IF parent=NIL OR child=NIL THEN RETURN;
n ← parent.child;
DO SELECT n FROM
child => RETURN [count];
NIL => RETURN [MaxLen];
ENDCASE;
n ← Next[n];
count ← count+1;
ENDLOOP;
};
NodeRope: PUBLIC PROC [n: RefTextNode] RETURNS [ROPE] = {
RETURN[IF n=NIL THEN NIL ELSE n.rope];
};
NodeRuns: PUBLIC PROC [n: RefTextNode] RETURNS [TextLooks.Runs] = {
RETURN[IF n=NIL THEN NIL ELSE n.runs];
};
Props: PUBLIC PROC [n: Ref] RETURNS [NodeProps] = {
RETURN[IF n=NIL THEN NIL ELSE n.props];
};
NodeFormat: PUBLIC PROC [n: Ref] RETURNS [ATOM] = {
RETURN[IF n=NIL THEN NIL ELSE n.formatName];
};
IsLastSibling: PUBLIC PROC [n: Ref] RETURNS [BOOL] = {
RETURN[IF n=NIL THEN FALSE ELSE n.last];
};
EndPos: PUBLIC PROC [n: Ref] RETURNS [INT] = {
IF n=NIL THEN RETURN [0];
RETURN [MAX[Rope.Size[n.rope], 1]-1];
};
New routines for operating on $query nodes
-- remember last query and its cursor to improve performance
lastq: Ref ← NIL;
cursor: REF LoganQuery.ComplexCursor ← NIL;
QueryToText: PROC [q, p: Ref ← NIL] RETURNS [t: Ref] ~ {
On input:
q should be a node with format $query,
p (if not NIL) should be the q's parent (if q is a first child) or q's preceeding sibling,
Note that p can be determined given q so its input is only for performance improvement.
Upon completion:
t is a text node containing the first database entry obtained by running the query specified in q (t=q if q is not a $query node),
t.next is a $query node representing the rest of the query that remains to be run.
entry: LoganBerry.Entry;
IF q=NIL OR q.formatName # $query THEN RETURN[t: q];
Get next entry returned by query
IF q # lastq THEN { -- get new cursor
lastq ← q;
cursor ← NARROW[NP.GetProp[q, $LBCursor]];
IF cursor = NIL THEN {
cursor ← InitiateQuery[q.rope];
IF cursor = NIL THEN { -- bad query specification
q.formatName ← $block;
q.rope ← Rope.Concat["Bad Query: ", q.rope];
RETURN[q];
};
NP.PutProp[q, $LBCursor, cursor];
};
};
entry ← LoganQuery.NextEntry[cursor: cursor^];
IF entry = NIL THEN { -- query completed
q.formatName ← $block;
q.rope ← NIL;
RETURN[q];
};
Create new node t for returned entry
t ← NEW[Body ← q^]; -- t inherits q's properties
t.child ← NIL;
t.formatName ← $block;
t.last ← FALSE;
t.rope ← EntryToRope[entry];
Link t before q in tree
IF p=NIL THEN {
p ← q;
WHILE NOT p.last DO p ← p.next; ENDLOOP;
p ← p.next; -- p is now q's parent
IF p.child#q THEN {
p ← p.child; -- get to first sibling
WHILE p.next # q DO p ← p.next; ENDLOOP;
};
};
t.next ← q;
IF p.child=q THEN p.child ← t;
IF p.next=q THEN p.next ← t;
};
QueryToLastText: PROC [q: Ref] RETURNS [t: Ref] ~ {
On input:
q should be a node with format $query.
Upon completion:
the query specified in q has been completely processed and t is the last node in the list of retrieved database entries (t=q if q is not a $query node).
IF q=NIL OR q.formatName # $query THEN RETURN[t: q];
t ← QueryToText[q];
WHILE t.rope # NIL DO
t ← QueryToText[t.next, t];
ENDLOOP;
};
InitiateQuery: PROC [rope: Rope.ROPE] RETURNS [c: REF LoganQuery.ComplexCursor] ~ {
dbname: Rope.ROPE;
ap: LoganQuery.AttributePatterns;
s: IO.STREAM ← IO.RIS[rope];
dbname ← IO.GetTokenRope[s, IO.IDProc ! IO.EndOfStream => GOTO End].token;
ap ← LoganQuery.ReadAttributePatterns[s ! LoganQuery.SyntaxError => GOTO End];
c ← NEW[LoganQuery.ComplexCursor ← LoganQuery.QueryEntries[db: LoganBerry.Open[dbName: dbname], patterns: ap].cursor];
EXITS
End => RETURN[NIL];
};
EntryToRope: PROC [e: LoganBerry.Entry] RETURNS [r: Rope.ROPE] ~ {
r ← NIL;
FOR l: LoganBerry.Entry ← e, l.rest WHILE l # NIL DO
r ← IO.PutFR["%g%g: %g\n", IO.rope[r], IO.atom[l.first.type], IO.rope[l.first.value]];
ENDLOOP;
};
END.