-- ParserGraphsImpl.mesa
-- last edit     November 2, 1984 2:04:39 pm PST
-- Sturgis, April 1, 1986 2:16:10 pm PST

DIRECTORY
GrammarBasic USING[Grammar, Symbol],
ParserGraphs USING[GraphClass];


ParserGraphsImpl: CEDAR PROGRAM EXPORTS ParserGraphs  =

BEGIN OPEN GrammarBasic, ParserGraphs;

Graph: TYPE = REF GraphBody;
GraphBody: PUBLIC TYPE = RECORD[
class: GraphClass,
grammar: Grammar,
start: Node _ NIL,
first: Node _ NIL,
firstStage1: Node _ NIL,
firstDirty: Node _ NIL,
indexed: BOOLEAN _ FALSE];

Node: TYPE = REF NodeBody;
NodeBody: PUBLIC TYPE = RECORD[
graph: Graph,
s: REF ANY,
index: CARDINAL _ 0, --used by print code
upper: Node _ NIL,
base: Node, 
ring: CARDINAL _ LAST[CARDINAL],
split: BOOLEAN _ FALSE,
dirty: BOOLEAN _ FALSE,
arcs: Arc _ NIL,
recentArc: Arc _ NIL,
next: Node _ NIL,
stage: Stage _ stage1,
installed: BOOLEAN _ FALSE,
prevStage1, nextStage1: Node _ NIL,
nextDirty: Node _ NIL];

Stage: TYPE = {stage1, stage2};

Arc: TYPE = REF ArcBody;
ArcBody: TYPE = RECORD[
s: Symbol,
target: Node,
next: Arc];


-- interface procedures

CreateEmptyGraph: PUBLIC PROC[grammar: Grammar, class: GraphClass] RETURNS[Graph] =
BEGIN
graph: Graph _ NEW[GraphBody _ [class, grammar]];
RETURN[graph];
END;

GetGraphStats: PUBLIC PROC[g: Graph] RETURNS[nNodes, nArcs, nNodesMarkedToSplit: INT] =
BEGIN
SeeOneNode: PROC[n: Node] RETURNS[BOOLEAN] =
BEGIN
nNodes _ nNodes + 1;
IF n.split THEN nNodesMarkedToSplit _ nNodesMarkedToSplit + 1;
GenerateArcs[n, SeeOneArc];
RETURN[TRUE]
END;

SeeOneArc: PROC[s: Symbol, t: Node] RETURNS[BOOLEAN] =
{nArcs _ nArcs + 1; RETURN[TRUE]};

nNodes _ nArcs _ nNodesMarkedToSplit _ 0;
GenerateAllNodes[g, SeeOneNode];
END; 

GetClass: PUBLIC PROC[graph: Graph] RETURNS[GraphClass] =
{RETURN[graph.class]};

GetGrammar: PUBLIC PROC[graph: Graph] RETURNS[Grammar] =
{RETURN[graph.grammar]};

GetStartNode: PUBLIC PROC[graph: Graph] RETURNS[Node] =
{RETURN[graph.start]};

GetAnyStage1Node: PUBLIC PROC[graph: Graph] RETURNS[Node] =
{RETURN[graph.firstStage1]};

GetAnyDirtyNode: PUBLIC PROC[graph: Graph] RETURNS[Node] =
BEGIN
dirty: Node _ graph.firstDirty;
IF dirty # NIL THEN
BEGIN
graph.firstDirty _ dirty.nextDirty;
dirty.nextDirty _ NIL;
dirty.dirty _ FALSE;
END;
RETURN[dirty];
END;

GenerateAllNodes: PUBLIC PROC[graph: Graph, viewNode: PROC[Node] RETURNS[--continue--BOOLEAN]] =
BEGIN -- nodes added during iteration will not be generated.
FOR node: Node _ graph.first, node.next WHILE node # NIL DO
IF NOT viewNode[node] THEN EXIT;
ENDLOOP;
END;

ClearAllUpperNodePointers: PUBLIC PROC[graph: Graph] =
BEGIN
FOR node: Node _ graph.first, node.next WHILE node # NIL DO
node.upper _ NIL;
ENDLOOP;
END;

IndexTheNodes: PUBLIC PROC[graph: Graph] =
BEGIN
nextIndex: CARDINAL _ 0;
IF graph.indexed THEN ERROR;
graph.indexed _ TRUE;
FOR node: Node _ graph.first, node.next WHILE node # NIL DO
node.index _ nextIndex;
nextIndex _ nextIndex+1;
ENDLOOP;
END;


CleanTheGraph: PUBLIC PROCEDURE[graph: Graph] RETURNS[Graph] =
BEGIN
nextNode: Node;
nextArc: Arc;
IF graph = NIL THEN RETURN[NIL];
FOR node: Node _ graph.first, nextNode WHILE node # NIL DO
nextNode _ node.next;
FOR arc: Arc _ node.arcs, nextArc WHILE arc # NIL DO
nextArc _ arc.next;
arc.target _ NIL;
arc.next _ NIL;
ENDLOOP;
node.graph _ NIL;
node.upper _ node.base _ node.next _ node.prevStage1 _ node.nextStage1 _ node.nextDirty _ NIL;
node.arcs _ node.recentArc _ NIL;
ENDLOOP;
RETURN[NIL];
END;

CreateTentativeStage1Node: PUBLIC PROC[g: Graph, s: REF ANY, base: Node] RETURNS[Node] =
BEGIN
newNode: Node _ NEW[NodeBody _ [graph: g, s: s, base: base, next: NIL, nextStage1: NIL]];
RETURN[newNode];
END;

InstallStage1Node: PUBLIC PROC[n: Node, startNode: BOOLEAN] =
BEGIN
g: Graph _ n.graph;
IF n.installed THEN RETURN;
n.installed _ TRUE;
n.nextStage1 _ g.firstStage1;
IF g.firstStage1 # NIL THEN g.firstStage1.prevStage1 _ n;
g.firstStage1 _ n;
n.next _ g.first;
g.first _ n;
IF startNode THEN
BEGIN
IF g.start # NIL THEN ERROR;
g.start _ n;
END;
END;

SetUpperNode: PUBLIC PROC[n: Node, upper: Node] =
BEGIN
IF n.upper # NIL THEN ERROR;
n.upper _ upper;
END;

SetRingNumber: PUBLIC PROC[n: Node, ring: CARDINAL] =
{n.ring _ ring};

AppendAnArc: PUBLIC PROC[source: Node, s: Symbol, target: Node] =
BEGIN
newArc: Arc;
IF source.recentArc # NIL AND source.recentArc.s = s THEN ERROR;
FOR a: Arc _ source.arcs, a.next WHILE a # NIL DO
IF a.s = s THEN ERROR;
ENDLOOP;
newArc _ NEW[ArcBody _ [s: s, target: target, next: source.arcs]];
source.arcs _ newArc;
END;

ResetArcTarget: PUBLIC PROC[source: Node, s: Symbol, newTarget: Node] =
BEGIN
IF source.recentArc = NIL OR source.recentArc.s # s THEN
FOR a: Arc _ source.arcs, a.next WHILE a # NIL DO
IF a.s = s THEN {source.recentArc _ a; EXIT};
ENDLOOP;
IF source.recentArc = NIL THEN ERROR;
source.recentArc.target _ newTarget;
END;

SetAssociatedSet: PUBLIC PROC[node: Node, s: REF ANY, oldValue: REF ANY] =
BEGIN
IF node.s # oldValue THEN ERROR;
node.s _ s;
END;

MarkAsStage2: PUBLIC PROC[node: Node] =
BEGIN
IF NOT node.stage = stage1 THEN ERROR;
node.stage _ stage2;
IF node.prevStage1 # NIL THEN node.prevStage1.nextStage1 _ node.nextStage1 ELSE node.graph.firstStage1 _ node.nextStage1;
IF node.nextStage1 # NIL THEN node.nextStage1.prevStage1 _ node.prevStage1;
node.prevStage1 _ node.nextStage1 _ NIL;
END;

MarkNodeDirty: PUBLIC PROC[node: Node] =
BEGIN
IF node.dirty THEN RETURN;
node.dirty _ TRUE;
node.nextDirty _ node.graph.firstDirty;
node.graph.firstDirty _ node;
END;


MarkNodeToSplit: PUBLIC PROC[node: Node] =
{node.split _ TRUE};

SetNodeIndex: PUBLIC PROC[node: Node, x: CARDINAL] =
{node.index _ x};

GetGraph: PUBLIC PROC[node: Node] RETURNS[Graph] =
{RETURN[node.graph]};

GenerateArcs: PUBLIC PROC[node: Node, p: PROC[Symbol, Node] RETURNS[--continue-- BOOLEAN]] =
BEGIN
FOR a: Arc _ node.arcs, a.next WHILE a # NIL DO
IF NOT p[a.s, a.target] THEN EXIT;
ENDLOOP;
END;

FollowSymbol: PUBLIC PROC[node: Node, s: Symbol] RETURNS[Node] =
BEGIN
IF node.recentArc # NIL AND node.recentArc.s = s THEN RETURN[node.recentArc.target];
FOR a: Arc _ node.arcs, a.next WHILE a # NIL DO
IF a.s = s THEN
BEGIN
node.recentArc _ a;
RETURN[a.target];
END;
ENDLOOP;
RETURN[NIL];
END;

GetAssociatedSet: PUBLIC PROC[node: Node] RETURNS[REF ANY] =
{RETURN[node.s]};

GetBaseNode: PUBLIC PROC[node: Node] RETURNS[Node] =
{RETURN[node.base]};

GetUpperNode: PUBLIC PROC[node: Node] RETURNS[Node] =
{RETURN[node.upper]};

GetRingNumber: PUBLIC PROC[node: Node] RETURNS[CARDINAL] =
{RETURN[node.ring]};

GetSplittingMark: PUBLIC PROC[node: Node] RETURNS[BOOLEAN] =
{RETURN[node.split]};

NarrowNode: PUBLIC PROC[ref: REF ANY] RETURNS[Node] =
{RETURN[NARROW[ref]]};

GetNodeIndex: PUBLIC PROC[node: Node] RETURNS[CARDINAL] =
{RETURN[node.index]};



END..