<> <> <> <> <> <<>> 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] = { <> 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] = { <> 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