MODULEConstructors.; IMPORT Glob, RegEx; TYPE (* The base node type. For simplicity, all nodes have left and right child pointers even if they are not used. *) Node = T OBJECT left, right: T := NIL; END; (* Internal nodes (operators). *) TreeNode = Node OBJECT OVERRIDES test := TreeTest; END; (* The following node types are branded because they are structurally identical but we need to be able to distinguish between them with TYPECASE. *) NotNode = TreeNode BRANDED OBJECT END; AndNode = TreeNode BRANDED OBJECT END; OrNode = TreeNode BRANDED OBJECT END; (* Leaf nodes. *) MatchNode = Node OBJECT pattern: TEXT; options: Glob.MatchOptions; OVERRIDES test := MatchTest; END; RegExNode = Node OBJECT pattern: RegEx.Pattern; OVERRIDES test := RegExTest; END; TrueNode = Node OBJECT OVERRIDES test := TrueTest; END; FalseNode = Node OBJECT OVERRIDES test := FalseTest; END; GlobTree
PROCEDURELeaf evaluators.Match (pattern: TEXT; options := Glob.MatchOptions{}): T = BEGIN RETURN NEW(MatchNode, pattern := pattern, options := options); END Match; PROCEDURERegExMatch (pattern: TEXT): T RAISES {RegEx.Error} = BEGIN RETURN NEW(RegExNode, pattern := RegEx.Compile(pattern)); END RegExMatch; PROCEDUREAnd (left, right: T): T = BEGIN IF left = False OR right = False THEN RETURN False; ELSIF left = True THEN RETURN right; ELSIF right = True THEN RETURN left; ELSE RETURN NEW(AndNode, left := left, right := right); END; END And; PROCEDUREOr (left, right: T): T = BEGIN IF left = True OR right = True THEN RETURN True; ELSIF left = False THEN RETURN right; ELSIF right = False THEN RETURN left; ELSE RETURN NEW(OrNode, left := left, right := right); END; END Or; PROCEDURENot (child: T): T = BEGIN IF child = True THEN RETURN False; ELSIF child = False THEN RETURN True; ELSE RETURN NEW(NotNode, left := child); END; END Not;
PROCEDUREEvaluation of more complex trees.MatchTest (self: MatchNode; filename: TEXT): BOOLEAN = BEGIN RETURN Glob.Match(self.pattern, filename, self.options); END MatchTest; PROCEDURERegExTest (self: RegExNode; filename: TEXT): BOOLEAN = BEGIN RETURN RegEx.Execute(self.pattern, filename) >= 0; END RegExTest; PROCEDURETrueTest (<*UNUSED*> self: T; <*UNUSED*> filename: TEXT): BOOLEAN = BEGIN RETURN TRUE; END TrueTest; PROCEDUREFalseTest (<*UNUSED*> self: T; <*UNUSED*> filename: TEXT): BOOLEAN = BEGIN RETURN FALSE; END FalseTest;
TYPE State = { DoingLeft, DoingRight }; StackElem = REF RECORD next: StackElem; node: Node; state: State; END; PROCEDURETreeTest (self: TreeNode; filename: TEXT): BOOLEAN = VAR stack: StackElem := NIL; cur: Node; state: State; val: BOOLEAN; PROCEDURE Push(node: Node; state: State) = BEGIN stack := NEW(StackElem, node := node, state := state, next := stack); END Push; PROCEDURE Pop(VAR node: Node; VAR state: State) = BEGIN node := stack.node; state := stack.state; stack := stack.next; END Pop; BEGIN cur := self; LOOP (* Descend to the left until we hit bottom. *) WHILE cur.left # NIL DO Push(cur, State.DoingLeft); cur := cur.left; END; (* Now cur is a leaf node. Evaluate it. *) val := cur.test(filename); (* Ascend, propagating the value through operator nodes. *) LOOP IF stack = NIL THEN RETURN val; END; Pop(cur, state); TYPECASE cur OF | NotNode => val := NOT val; | AndNode => (* If we haven't yet evaluated the right subtree and the partial result is TRUE, descend to the right. Otherwise the result is already determined to be val. *) IF state = State.DoingLeft AND val THEN Push(cur, State.DoingRight); cur := cur.right; EXIT; END; | OrNode => (* If we haven't yet evaluated the right subtree and the partial result is FALSE, descend to the right. Otherwise the result is already determined to be val. *) IF state = State.DoingLeft AND NOT val THEN Push(cur, State.DoingRight); cur := cur.right; EXIT; END; ELSE (* We only push nodes that have children -- i.e., operator nodes. *) <*ASSERT FALSE *> END; END; END; END TreeTest; BEGIN True := NEW(TrueNode); False := NEW(FalseNode); END GlobTree.