TreeCheckImpl.Mesa; written by Pier. February, 1981
edited by Paxton, 20-May-81 13:47:47
edited by McGregor, May 9, 1983 2:20 pm
Last Edited by: Lamming, April 13, 1983 12:04 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, RefBasicNode, RefBoxNode, RefBranchNode, RefItemNode, RefListNode, RefTextNode],
TreeCheck,
CheckNode USING [CheckTextNode];
TreeCheckImpl: CEDAR PROGRAM
IMPORTS CheckNode
EXPORTS TreeCheck =
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, childN:Depth] = {
IF childN >= maxDepth THEN
ERROR; -- too many kids to believe
WITH me SELECT FROM
branch:TiogaNode.RefBranchNode =>
VerifyBranchNode[branch, parent, childN];
item:TiogaNode.RefItemNode =>
VerifyItemNode[item, parent, childN];
basic:TiogaNode.RefBasicNode =>
VerifyBasicNode[basic, parent, childN];
ENDCASE => ERROR; -- must be one of above!
};
VerifyNodeOfType: PROCEDURE [kind:TiogaNode.OfNode, me,parent:Node, childN:Depth] = {
IF me.kind#kind THEN
ERROR -- not of expected type
ELSE
VerifyNode[me, parent, childN];
};
VerifyBasicNode: PROCEDURE [me:TiogaNode.RefBasicNode, parent:Node, childN:Depth] = {
ERROR; -- dont know how to verify a basic node yet
};
VerifyBranchNode: PROCEDURE [me:TiogaNode.RefBranchNode, parent:Node, childN:Depth] = {
Check a branch - note that the sibling chain is checked by iteration to avoid stack overflow
sibN:Depth ← 0;
IF me.internalRepCreated THEN {
IF me.contents # NIL THEN
VerifyNodeOfType[item, me.contents, me, childN];   -- contents
IF me.child # NIL THEN           -- children
FOR this:TiogaNode.RefBranchNode ← me.child, NARROW[this.next] DO
IF this = NIL THEN ERROR
ELSE VerifyBranchNode[this, me, childN+1];
IF this.last THEN {
IF this.next = me THEN RETURN;
IF this.next # NIL THEN FindSmashedLink[parent, this.next];
ERROR; -- next link NIL!
};
IF (sibN ← sibN + 1) >= maxDepth THEN ERROR;   -- too many children to believe
ENDLOOP;
IF me.last THEN {
IF me.next = parent THEN
RETURN;
IF me.next # NIL THEN FindSmashedLink[parent, me.next];
ERROR; -- next link NIL!
}
}
ELSE { -- verify what you can then
ERROR;
};
};
VerifyItemNode: PROCEDURE [me:TiogaNode.RefItemNode, parent:Node, childN:Depth] = {
sibN:Depth ← 0;
VerifyItemConts: PROCEDURE [me:TiogaNode.RefItemNode, parent:Node, childN:Depth] = {
WITH me SELECT FROM
t:TiogaNode.RefTextNode => {
CheckNode.CheckTextNode[t];
};
l:TiogaNode.RefListNode => ERROR;
b:TiogaNode.RefBoxNode => ERROR;
ENDCASE => ERROR;
IF me.last THEN {
IF me.next = parent THEN
RETURN;
IF me.next # NIL THEN FindSmashedLink[parent, me.next];
ERROR; -- next link NIL!
};
};
FOR this: Node ← me, this.next DO
IF this = NIL THEN ERROR; -- should point to next sib or parent
IF this.kind = item THEN VerifyItemConts[NARROW[this], parent, childN]
ELSE ERROR;
IF this.last THEN {
IF this.next = parent THEN
RETURN;
IF this.next # NIL THEN FindSmashedLink[parent, this.next];
ERROR; -- next link NIL!
};
IF (sibN ← sibN + 1) >= maxDepth THEN
ERROR; -- too many siblings 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