TreeCheckImpl.Mesa; written by Pier. February, 1981
edited by Paxton, August 16, 1983 1:59 pm
edited by McGregor, May 9, 1983 2:20 pm
TreeCheck: a procedure called to verify that a Tioga tree structure is valid. If a problem is discovered, an exit to the debugger with an error message and locale is taken. If no problem, returns TRUE.
DIRECTORY
TiogaNode USING [OfNode, Ref, RefBasicNode, RefBoxNode, RefBranchNode, RefItemNode, RefListNode, RefTextNode],
TiogaNodeOps,
TreeCheck,
CheckNode USING [CheckTextNode];
TreeCheckImpl:
CEDAR PROGRAM
IMPORTS CheckNode, TiogaNodeOps
EXPORTS TreeCheck
SHARES TiogaNode =
BEGIN OPEN TreeCheck;
--limits
maxDepth: CARDINAL = 2000;
Depth: TYPE = [0..maxDepth);
--globals
Verify: PUBLIC PROC [node:Node] ={ VerifyNode[node, NIL, 0] };
VerifyNode:
PROC [me, parent:Node, depth:Depth] = {
IF depth >= maxDepth THEN ERROR; -- too many kids to believe
WITH me
SELECT
FROM
branch:TiogaNode.RefBranchNode => VerifyBranchNode[branch, parent, depth];
item:TiogaNode.RefItemNode => VerifyItemNode[item, parent, depth];
basic:TiogaNode.RefBasicNode => VerifyBasicNode[basic, parent, depth];
ENDCASE => ERROR; -- must be one of above!
VerifyBasicNode:
PROCEDURE [me:TiogaNode.RefBasicNode, parent:Node, depth:Depth] = {
Check a branch - note that the sibling chain is checked by iteration to avoid stack overflow
IF depth >= maxDepth THEN ERROR;
IF me.last
AND me.next # parent
THEN {
IF me.next # NIL THEN FindSmashedLink[parent, me.next];
ERROR }};
VerifyBranchNode:
PROCEDURE [me:TiogaNode.RefBranchNode, parent:Node, depth:Depth] = {
Check a branch - note that the sibling chain is checked by iteration to avoid stack overflow
sibN:Depth ← 0;
IF depth >= maxDepth THEN ERROR;
IF me.last
AND me.next # parent
THEN {
IF me.next # NIL THEN FindSmashedLink[parent, me.next];
ERROR };
IF ~me.internalRepCreated THEN RETURN;
IF me.contents #
NIL
THEN
-- contents
FOR this: TiogaNode.RefItemNode ← me.contents,
NARROW[this.next]
DO
IF this = NIL THEN ERROR;
VerifyItemNode[this, me, depth+1];
IF this.last
THEN {
IF this.next = me THEN EXIT;
IF this.next # NIL THEN FindSmashedLink[parent, this.next];
ERROR };
IF (sibN ← sibN + 1) >= maxDepth THEN ERROR; -- too many children to believe
ENDLOOP;
IF me.child #
NIL
THEN
-- children
FOR this:TiogaNode.RefBranchNode ← me.child,
NARROW[this.next]
DO
IF this = NIL THEN ERROR;
VerifyBranchNode[this, me, depth+1];
IF this.last
THEN {
IF this.next = me THEN EXIT;
IF this.next # NIL THEN FindSmashedLink[parent, this.next];
ERROR };
IF (sibN ← sibN + 1) >= maxDepth THEN ERROR; -- too many children to believe
ENDLOOP };
VerifyItemNode:
PROCEDURE [me:TiogaNode.RefItemNode, parent:Node, depth:Depth] = {
sibN:Depth ← 0;
contents: TiogaNode.Ref;
branches: BOOL;
IF depth >= maxDepth THEN ERROR;
IF me.last
AND me.next # parent
THEN {
IF me.next # NIL THEN FindSmashedLink[parent, me.next];
ERROR };
WITH me
SELECT
FROM
tx: TiogaNode.RefTextNode => CheckNode.CheckTextNode[tx];
bx: TiogaNode.RefBoxNode => contents ← bx.contents;
ls: TiogaNode.RefListNode => contents ← ls.contents;
ENDCASE => ERROR;
IF contents=NIL THEN RETURN;
branches ← TiogaNodeOps.IsBranch[contents];
FOR this: TiogaNode.Ref ← contents, this.next
DO
IF this = NIL THEN ERROR;
IF TiogaNodeOps.IsBranch[this] # branches THEN ERROR;
VerifyNode[this, me, depth+1];
IF this.last
THEN {
IF this.next = me THEN EXIT;
IF this.next # NIL THEN FindSmashedLink[parent, this.next];
ERROR };
IF (sibN ← sibN + 1) >= maxDepth THEN ERROR; -- too many children to believe
ENDLOOP };
FindSmashedLink: PROC[startparent: Node, endparent: Node] = {
FindSmashedLink is called when the node pointed to at the end of a sibling chain is not the parent who started the chain. We assume some pointer in that chain is smashed and is pointing to some other random but wellformed section of the tree. We then traverse the startparent sibling chain, looking for the first node whose immediate sibling is a son of the endparent. That is the smashed node, called badguy.
badguy: Node ← startparent; -- this will finally be the node with a smashed pointer
FOR tnode: Node ← startparent, tnode.next
UNTIL tnode.last
DO
FOR bnode: Node ← endparent, bnode.next
UNTIL bnode.last
DO
IF tnode = bnode
THEN
ERROR;
-- tnode is a child of endparent
-- but is pointed to by badguy, a child of startparent
-- or tnode=startparent.child and startparent=badguy
badguy ← tnode;
ENDLOOP;
ENDLOOP;
ERROR; -- this can't happen!
}; --FindSmashedLink
END. --TreeCheckImpl
Log
Created February 19, 1981, by Pier.
Modified 20-May-81, by Paxton
Modified February 24, 1983 by Lamming to handle Tioga2 structures