You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by ak...@apache.org on 2004/06/10 06:42:16 UTC
svn commit: rev 20975 - in incubator/directory/snickers/trunk: ber-codec/src/java/org/apache/snickers/ber/digester ber-codec/src/test/org/apache/snickers/ber/digester ber-codec/src/test/org/apache/snickers/ber/digester/testutils ldap-ber-provider/src/test/org/apache/snickers/ldap xdocs/ber-codec xdocs/images
Author: akarasulu
Date: Wed Jun 9 21:42:16 2004
New Revision: 20975
Added:
incubator/directory/snickers/trunk/ber-codec/src/java/org/apache/snickers/ber/digester/RuleRegistration.java (contents, props changed)
incubator/directory/snickers/trunk/ber-codec/src/test/org/apache/snickers/ber/digester/testutils/
incubator/directory/snickers/trunk/ber-codec/src/test/org/apache/snickers/ber/digester/testutils/PrivateTestCase.java (contents, props changed)
incubator/directory/snickers/trunk/xdocs/images/TagTree.png (contents, props changed)
incubator/directory/snickers/trunk/xdocs/images/WildTagTree.png (contents, props changed)
Modified:
incubator/directory/snickers/trunk/ber-codec/src/java/org/apache/snickers/ber/digester/TagNode.java
incubator/directory/snickers/trunk/ber-codec/src/java/org/apache/snickers/ber/digester/TagTree.java
incubator/directory/snickers/trunk/ber-codec/src/test/org/apache/snickers/ber/digester/TagTreeTest.java
incubator/directory/snickers/trunk/ldap-ber-provider/src/test/org/apache/snickers/ldap/SearchRequestTest.java
incubator/directory/snickers/trunk/xdocs/ber-codec/BERDigesterDesign.xml
Log:
Commit changes ...
o added ability to match in constant time regardless of rule base size using
a wild card at the start of a pattern
o added unit tests to verify correct operation
o added more docs to describe the changes to TagTree
Added: incubator/directory/snickers/trunk/ber-codec/src/java/org/apache/snickers/ber/digester/RuleRegistration.java
==============================================================================
--- (empty file)
+++ incubator/directory/snickers/trunk/ber-codec/src/java/org/apache/snickers/ber/digester/RuleRegistration.java Wed Jun 9 21:42:16 2004
@@ -0,0 +1,69 @@
+/*
+ * Copyright 2004 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ */
+package org.apache.snickers.ber.digester;
+
+
+/**
+ * Document this class.
+ *
+ * @author <a href="mailto:directory-dev@incubator.apache.org">Apache Directory
+ * Project</a>
+ * @version $Rev$
+ */
+public class RuleRegistration
+{
+ /** the pattern that is used to register a rule with */
+ private final int[] pattern;
+ /** the rule registered with the pattern */
+ private final Rule rule;
+
+
+ /**
+ * Create a new rule registration used to track the rules and patterns that
+ * are registered with the digester.
+ *
+ * @param pattern the pattern used to register a rule with
+ * @param rule the rule registered with the pattern
+ */
+ public RuleRegistration( int[] pattern, Rule rule )
+ {
+ this.rule = rule;
+ this.pattern = pattern;
+ }
+
+
+ /**
+ * Gets the pattern used to register a rule.
+ *
+ * @return the pattern that is used to register a rule
+ */
+ public int[] getPattern()
+ {
+ return pattern;
+ }
+
+
+ /**
+ * Gets the rule registered with the pattern.
+ *
+ * @return the rule registered with the pattern
+ */
+ public Rule getRule()
+ {
+ return rule;
+ }
+}
Modified: incubator/directory/snickers/trunk/ber-codec/src/java/org/apache/snickers/ber/digester/TagNode.java
==============================================================================
--- incubator/directory/snickers/trunk/ber-codec/src/java/org/apache/snickers/ber/digester/TagNode.java (original)
+++ incubator/directory/snickers/trunk/ber-codec/src/java/org/apache/snickers/ber/digester/TagNode.java Wed Jun 9 21:42:16 2004
@@ -17,9 +17,7 @@
package org.apache.snickers.ber.digester ;
-import java.util.HashMap ;
-import java.util.ArrayList ;
-import java.util.List;
+import java.util.*;
/**
@@ -90,8 +88,20 @@
{
return children.containsKey( tag ) ;
}
-
-
+
+
+ public boolean isLeaf()
+ {
+ return children.isEmpty() ;
+ }
+
+
+ public Iterator getChildren()
+ {
+ return children.values().iterator() ;
+ }
+
+
public TagNode getChild( Integer tag )
{
return ( TagNode ) children.get( tag ) ;
Modified: incubator/directory/snickers/trunk/ber-codec/src/java/org/apache/snickers/ber/digester/TagTree.java
==============================================================================
--- incubator/directory/snickers/trunk/ber-codec/src/java/org/apache/snickers/ber/digester/TagTree.java (original)
+++ incubator/directory/snickers/trunk/ber-codec/src/java/org/apache/snickers/ber/digester/TagTree.java Wed Jun 9 21:42:16 2004
@@ -17,16 +17,14 @@
package org.apache.snickers.ber.digester ;
-import java.util.List ;
-import java.util.HashMap ;
-import java.util.Collections ;
+import java.util.*;
import org.apache.commons.lang.Validate ;
-import org.apache.commons.collections.primitives.IntStack;
+import org.apache.commons.collections.primitives.IntStack ;
/**
- * A tree of tags.
+ * A disjointed tree of tag patterns with and without wild cards.
*
* @todo find and start using a hash table keyed by primitive int instead of
* an Integer
@@ -37,20 +35,57 @@
*/
public class TagTree
{
- /** a set of tag nodes */
- private HashMap nodes = new HashMap( 3 ) ;
+ /** the wild card tag value as an integer = UNIVERSAL 2,097,151 (2^21-1) */
+ public static final int WILDCARD = 0x1FFFFFFF ;
+
+ /** a map of tag nodes for normal patterns */
+ private HashMap normNodes = new HashMap( 3 ) ;
+ /** a map of tag nodes for wild carded patterns */
+ private HashMap wildNodes = new HashMap( 3 ) ;
+ /** the list of normal rule regs with rule and pattern in order */
+ private ArrayList normRegistrations = new ArrayList() ;
+ /** the list of wild carded rule regs with rule and pattern in order */
+ private ArrayList wildRegistrations = new ArrayList() ;
+
+
+ // ------------------------------------------------------------------------
+ // Methods used to add rules to trees
+ // ------------------------------------------------------------------------
+
+
+ /**
+ * Adds a Rule to this TagTree in a manner based on whether the pattern
+ * contains a wild card in front or not.
+ *
+ * @param pattern the pattern of nested tags
+ * @param rule the rule to add for the pattern
+ */
+ public void addRule( int[] pattern, Rule rule )
+ {
+ if ( pattern[0] == WILDCARD )
+ {
+ wildRegistrations.add( new RuleRegistration( pattern, rule ) ) ;
+ addWildRule( pattern, rule ) ;
+ }
+ else
+ {
+ normRegistrations.add( new RuleRegistration( pattern, rule ) ) ;
+ addNormalRule( pattern, rule ) ;
+ }
+ }
+
-
/**
* Adds a Rule to this TagTree.
*
* @param pattern the pattern of nested tags
* @param rule the rule to add for the pattern
*/
- public void addRule( int[] pattern, Rule rule )
+ private void addNormalRule( int[] pattern, Rule rule )
{
Integer tag = null ;
TagNode node = null ;
+ Stack stack = new Stack() ;
Validate.notNull( rule, "cannot add null rule" ) ;
Validate.notNull( pattern, "cannot add rule with null pattern" ) ;
@@ -58,14 +93,17 @@
"cannot add rule with empty pattern" ) ;
tag = new Integer( pattern[0] ) ;
- if ( nodes.containsKey( tag ) )
+ if ( normNodes.containsKey( tag ) )
{
- node = ( TagNode ) nodes.get( tag ) ;
+ node = ( TagNode ) normNodes.get( tag ) ;
+ stack.push( node.getTag() ) ;
}
else
{
node = new TagNode( tag ) ;
- nodes.put( tag, node ) ;
+ normNodes.put( tag, node ) ;
+ stack.push( node.getTag() ) ;
+ addWildRulesToNewNormalNode( node, stack ) ;
}
for ( int ii = 1; ii < pattern.length; ii++ )
@@ -77,16 +115,277 @@
{
childNode = new TagNode( childTag ) ;
node.addNode( childNode ) ;
+ stack.push( childNode.getTag() ) ;
+ addWildRulesToNewNormalNode( childNode, stack ) ;
}
-
+ else
+ {
+ stack.push( childNode.getTag() ) ;
+ }
+
node = childNode ;
tag = childTag ;
}
node.addRule( rule ) ;
}
-
-
+
+
+ /**
+ * Adds a Rule using a pattern with a wild card in front to this TagTree.
+ *
+ * @param pattern the pattern of nested tags with starting wild card
+ * @param rule the rule to add for the pattern
+ */
+ private void addWildRule( int[] pattern, Rule rule )
+ {
+ Validate.notNull( pattern,
+ "Attempting to register rule " + rule
+ + " with null pattern" ) ;
+ Validate.isTrue( pattern.length > 0,
+ "Attempting to register rule " + rule
+ + " with zero length pattern" ) ;
+ Validate.isTrue( pattern[0] == WILDCARD,
+ "Expected rule " + rule
+ + " pattern to have front wild card but it did not" ) ;
+ Validate.isTrue( pattern.length > 1,
+ "Cannot register only wild card \"*\" pattern for rule "
+ + rule ) ;
+
+ /*
+ * Adds the rule associated with the registration to the normal tag
+ * tree which involves a recursive descent on the normal tree.
+ */
+ TagNode node = null ;
+ Iterator list = normNodes.values().iterator() ;
+ while ( list.hasNext() )
+ {
+ node = ( TagNode ) list.next() ;
+ addWildRuleToNormalTree( pattern, rule, new Stack(), node ) ;
+ }
+
+ /*
+ * first just lay down the new branch without adding the rule
+ * next do a recursive drilldown testing for rule addition to all nodes
+ */
+ Integer tag = new Integer( pattern[pattern.length-1] ) ;
+ if ( wildNodes.containsKey( tag ) )
+ {
+ node = ( TagNode ) wildNodes.get( tag ) ;
+ }
+ else
+ {
+ node = new TagNode( tag ) ;
+ wildNodes.put( tag, node ) ;
+ }
+
+ for( int ii = pattern.length - 2; ii >= 1; ii-- )
+ {
+ Integer childTag = new Integer( pattern[ii] ) ;
+ TagNode childNode = node.getChild( childTag ) ;
+
+ if ( childNode == null )
+ {
+ childNode = new TagNode( childTag ) ;
+ node.addNode( childNode ) ;
+ }
+
+ node = childNode ;
+ tag = childTag ;
+ }
+
+ /*
+ * Recusively drill down each branch of the wild tree checking at each
+ * node to see if we need to add the new rule based on the pattern
+ */
+ list = wildNodes.values().iterator() ;
+ while( list.hasNext() )
+ {
+ node = ( TagNode ) list.next() ;
+ addWildRuleToWildTree( pattern, rule, new Stack(), node ) ;
+ }
+ }
+
+
+ /**
+ * Adds wild carded rules to new nodes being added to the tag tree with
+ * normal patterns without wild cards.
+ *
+ * @param node the new node added to the tree of normal tags
+ * @param stack a stack of nodes encountered while walking the tree
+ */
+ private void addWildRulesToNewNormalNode( TagNode node, Stack stack )
+ {
+ for ( int jj = 0; jj < wildRegistrations.size(); jj++ )
+ {
+ RuleRegistration reg = ( RuleRegistration )
+ wildRegistrations.get( jj ) ;
+
+ if ( isTailMatch( reg.getPattern(), stack ) )
+ {
+ node.addRule( reg.getRule() ) ;
+ }
+ }
+ }
+
+
+ /**
+ * Adds rules registered via wild cards to the wild TagTree to all
+ * nodes matching the pattern. This method performs depth first recursion
+ * building a stack of TagNodes as dives into the TagTree. At each point
+ * the pattern with the wild card is tested against the contents of the
+ * stack to see if it matches the nesting pattern, if it does then the
+ * rule is added to the current node.
+ *
+ * @param pattern the matching pattern with front wild card
+ * @param rule the rule registered with the pattern
+ * @param stack the stack storing the depth first nesting pattern
+ * @param node the current node scrutinized for a match by the pattern, and
+ * the current position of the depth first search
+ */
+ private void addWildRuleToWildTree( int[] pattern, Rule rule,
+ Stack stack, TagNode node )
+ {
+ stack.push( node.getTag() ) ;
+
+ if ( isReverseTailMatch( pattern, stack ) )
+ {
+ if ( ! node.getRules().contains( rule ) )
+ {
+ node.addRule( rule ) ;
+ }
+ }
+
+ if ( ! node.isLeaf() )
+ {
+ Iterator children = node.getChildren() ;
+ while( children.hasNext() )
+ {
+ addWildRuleToWildTree( pattern, rule, stack,
+ ( TagNode ) children.next() ) ;
+ }
+ }
+
+ stack.pop() ;
+ }
+
+
+ /**
+ * Called by depth first search used to add rules of wild card patterns to
+ * the wild TagTree. This method compares a stack of Integers to a
+ * pattern. The stack must have as many or more than pattern.length - 1
+ * elements to match. Elements from the second element of the pattern to
+ * the last element are compared with the bottom stack element up to the
+ * top. This is the reverse order because of the inverse paths in the
+ * pattern tree with wild cards.
+ *
+ * @param pattern the pattern with a wild card at position 0
+ * @param stack the nesting stack representing the depth first search path
+ * @return true if the elements [n-1] in the pattern match the bottom most
+ * elements in the stack where n+1 is length of the pattern array.
+ */
+ private boolean isReverseTailMatch( int[] pattern, Stack stack )
+ {
+ if ( stack.size() < pattern.length - 1 )
+ {
+ return false ;
+ }
+
+ for( int ii = pattern.length - 1, jj = 0 ; ii >= 1; ii--, jj++ )
+ {
+ if ( pattern[ii] != ( ( Integer ) stack.get( jj ) ).intValue() )
+ {
+ return false ;
+ }
+ }
+
+ return true ;
+ }
+
+
+ /**
+ * Adds rules registered via wild cards to the nodes within a branch of the
+ * normal TagTree. All nodes matching the pattern with wild cards has the
+ * rule added to it. This method performs depth first recursion building
+ * a stack of TagNodes as it dives into the TagTree. At each point the
+ * pattern with the wild card is tested against the contents of the
+ * stack to see if it matches the nesting pattern, if it does then the
+ * rule is added to the current node.
+ *
+ * @param pattern the matching pattern with front wild card
+ * @param rule the rule registered with the pattern
+ * @param stack the stack storing the depth first nesting pattern
+ * @param node the current node scrutinized for a match by the pattern, and
+ * the current position of the depth first search
+ */
+ private void addWildRuleToNormalTree( int[] pattern, Rule rule,
+ Stack stack, TagNode node )
+ {
+ stack.push( node.getTag() ) ;
+
+ if ( isTailMatch( pattern, stack ) && node.isLeaf() )
+ {
+ if ( ! node.getRules().contains( rule ) )
+ {
+ node.addRule( rule ) ;
+ }
+
+ System.out.println( rule + " already contained in node "
+ + node + " found at path " + stack
+ + " so we're not adding it again" ) ;
+ }
+
+ if ( ! node.isLeaf() )
+ {
+ Iterator children = node.getChildren() ;
+ while( children.hasNext() )
+ {
+ addWildRuleToNormalTree( pattern, rule, stack,
+ ( TagNode ) children.next() ) ;
+ }
+ }
+
+ stack.pop() ;
+ }
+
+
+ /**
+ * Called by depth first search used to add rules of wild card patterns to
+ * the normal TagTree. This method compares a stack of Integers to a
+ * pattern. The stack must have as many or more than pattern.length - 1
+ * elements to match. From the tail of the pattern to the second element
+ * is compared with the topmost stack element down.
+ *
+ * @param pattern the pattern with a wild card at position 0
+ * @param stack the nesting stack representing the depth first search path
+ * @return true if the elements [n-1] in the pattern match the topmost
+ * elements in the stack where n+1 is length of the pattern array.
+ */
+ private boolean isTailMatch( int[] pattern, Stack stack )
+ {
+ if ( stack.size() < pattern.length - 1 )
+ {
+ return false ;
+ }
+
+ for( int ii = pattern.length - 1, jj = stack.size() - 1; ii >= 1;
+ ii--, jj-- )
+ {
+ if ( pattern[ii] != ( ( Integer ) stack.get( jj ) ).intValue() )
+ {
+ return false ;
+ }
+ }
+
+ return true ;
+ }
+
+
+ // ------------------------------------------------------------------------
+ // Methods used for matching a stack or a int[]
+ // ------------------------------------------------------------------------
+
+
public List match( IntStack stack )
{
TagNode node = getNode( stack ) ;
@@ -100,7 +399,46 @@
}
- public TagNode getNode( IntStack stack )
+ public TagNode getNode( IntStack stack )
+ {
+ TagNode node = getNormalNode( stack ) ;
+
+ if ( node == null )
+ {
+ node = getWildNode( stack ) ;
+ }
+
+ return node ;
+ }
+
+
+ public List match( int[] pattern )
+ {
+ TagNode node = getNode( pattern ) ;
+
+ if ( node == null )
+ {
+ return Collections.EMPTY_LIST ;
+ }
+
+ return node.getRules() ;
+ }
+
+
+ public TagNode getNode( int[] pattern )
+ {
+ TagNode node = getNormalNode( pattern ) ;
+
+ if ( node == null )
+ {
+ node = getWildNode( pattern ) ;
+ }
+
+ return node ;
+ }
+
+
+ private TagNode getNormalNode( IntStack stack )
{
Integer tag = null ;
TagNode node = null ;
@@ -109,9 +447,9 @@
Validate.isTrue( !stack.empty(), "cannot match with empty pattern" ) ;
tag = new Integer( stack.get( 0 ) ) ;
- if ( nodes.containsKey( tag ) )
+ if ( normNodes.containsKey( tag ) )
{
- node = ( TagNode ) nodes.get( tag ) ;
+ node = ( TagNode ) normNodes.get( tag ) ;
}
else
{
@@ -136,20 +474,7 @@
}
- public List match( int[] pattern )
- {
- TagNode node = getNode( pattern ) ;
-
- if ( node == null )
- {
- return Collections.EMPTY_LIST ;
- }
-
- return node.getRules() ;
- }
-
-
- public TagNode getNode( int[] pattern )
+ private TagNode getNormalNode( int[] pattern )
{
Integer tag = null ;
TagNode node = null ;
@@ -159,9 +484,9 @@
"cannot match with empty pattern" ) ;
tag = new Integer( pattern[0] ) ;
- if ( nodes.containsKey( tag ) )
+ if ( normNodes.containsKey( tag ) )
{
- node = ( TagNode ) nodes.get( tag ) ;
+ node = ( TagNode ) normNodes.get( tag ) ;
}
else
{
@@ -186,8 +511,118 @@
}
- public TagNode getNode( int tag )
+ /**
+ * Gets a node matching a pattern with a wild card from this TagTree.
+ *
+ * @param pattern the wild card pattern as an int array
+ * @return the matching wild card node if any
+ */
+ private TagNode getWildNode( int[] pattern )
+ {
+ Integer tag = null ;
+ TagNode node = null ;
+
+ /*
+ * Restrict empty pattern, and zero length patterns.
+ */
+ Validate.notNull( pattern,
+ "cannot match using null pattern" ) ;
+ Validate.isTrue( pattern.length > 0,
+ "cannot match with empty pattern" ) ;
+
+ /*
+ * Begin reverse walk by looking up the node corresponding
+ * to the last pattern element. Return null if it does not exit.
+ */
+ tag = new Integer( pattern[pattern.length - 1] ) ;
+ if ( wildNodes.containsKey( tag ) )
+ {
+ node = ( TagNode ) wildNodes.get( tag ) ;
+ }
+ else
+ {
+ return null ;
+ }
+
+ /*
+ * Walk using the second to last [pattern.length-2] element down to
+ * the first element at index 0 in the pattern.
+ */
+ for ( int ii = pattern.length-2; ii >= 0; ii-- )
+ {
+ Integer childTag = new Integer( pattern[ii] ) ;
+ TagNode childNode = node.getChild( childTag ) ;
+
+ /*
+ * If no more children are present and we're about to walk off of
+ * the tree then we return the last node we have seen here.
+ */
+ if ( childNode == null )
+ {
+ return node ;
+ }
+
+ node = childNode ;
+ tag = childTag ;
+ }
+
+ return node ;
+ }
+
+
+ /**
+ * Gets a node matching a pattern with a wild card from this TagTree.
+ *
+ * @param stack the wild card pattern as a stack
+ * @return the matching wild card node if any
+ */
+ private TagNode getWildNode( IntStack stack )
{
- return ( TagNode ) nodes.get( new Integer( tag ) ) ;
+ Integer tag = null ;
+ TagNode node = null ;
+
+ /*
+ * Restrict empty pattern, and zero length patterns.
+ */
+ Validate.notNull( stack, "cannot match using null pattern" ) ;
+ Validate.isTrue( !stack.empty(), "cannot match with empty pattern" ) ;
+
+ /*
+ * Begin reverse walk by looking up the node corresponding
+ * to the bottom stack element. Return null if it does not exit.
+ */
+ tag = new Integer( stack.get( stack.size() - 1 ) ) ;
+ if ( normNodes.containsKey( tag ) )
+ {
+ node = ( TagNode ) normNodes.get( tag ) ;
+ }
+ else
+ {
+ return null ;
+ }
+
+ /*
+ * Walk using the element above the bottom [stack.size()-2] up to
+ * the top element at index 0 in the stack.
+ */
+ for ( int ii = stack.size() - 2; ii >= 0; ii-- )
+ {
+ Integer childTag = new Integer( stack.get( ii ) ) ;
+ TagNode childNode = node.getChild( childTag ) ;
+
+ /*
+ * If no more children are present and we're about to walk off of
+ * the tree then we return the last node we have seen here.
+ */
+ if ( childNode == null )
+ {
+ return node ;
+ }
+
+ node = childNode ;
+ tag = childTag ;
+ }
+
+ return node ;
}
}
Modified: incubator/directory/snickers/trunk/ber-codec/src/test/org/apache/snickers/ber/digester/TagTreeTest.java
==============================================================================
--- incubator/directory/snickers/trunk/ber-codec/src/test/org/apache/snickers/ber/digester/TagTreeTest.java (original)
+++ incubator/directory/snickers/trunk/ber-codec/src/test/org/apache/snickers/ber/digester/TagTreeTest.java Wed Jun 9 21:42:16 2004
@@ -18,9 +18,11 @@
import java.util.List ;
+import java.util.Stack ;
+import java.util.HashMap ;
-import junit.framework.TestCase ;
-import org.apache.commons.collections.primitives.IntStack;
+import org.apache.commons.collections.primitives.IntStack ;
+import org.apache.snickers.ber.digester.testutils.PrivateTestCase ;
/**
@@ -30,7 +32,7 @@
* Apache Directory Project</a>
* @version $Rev$
*/
-public class TagTreeTest extends TestCase
+public class TagTreeTest extends PrivateTestCase
{
/**
* Constructor for TagTreeTest.
@@ -41,19 +43,400 @@
super( name ) ;
}
-
+
+ /**
+ * Accesses the private wildNodes member to extract the TagNode
+ * with the int tag argument as a value.
+ *
+ * @param tree the tree to access
+ * @param tag the tag value to get the TagNode for
+ * @return the tag node accessed or null
+ */
+ private TagNode getWildNode( TagTree tree, int tag )
+ {
+ HashMap nodes = ( HashMap ) super.getMember( "wildNodes", tree ) ;
+ return ( TagNode ) nodes.get( new Integer( tag ) ) ;
+ }
+
+
+ /**
+ * Accesses the private normNodes member to extract the TagNode
+ * with the int tag argument as a value.
+ *
+ * @param tree the tree to access
+ * @param tag the tag value to get the TagNode for
+ * @return the tag node accessed or null
+ */
+ private TagNode getNormalNode( TagTree tree, int tag )
+ {
+ HashMap nodes = ( HashMap ) super.getMember( "normNodes", tree ) ;
+ return ( TagNode ) nodes.get( new Integer( tag ) ) ;
+ }
+
+
+ /**
+ * Used to white box test the private isTailMatch() method of the TagTree.
+ *
+ * @param tree the tree instance to test
+ * @param pattern the pattern arg
+ * @param stack the stack arg
+ * @return the resultant true or false return value
+ */
+ private boolean isTailMatch( TagTree tree, int[] pattern, Stack stack )
+ {
+ Class[] argClasses = { pattern.getClass(), Stack.class } ;
+ Object[] args = { pattern, stack } ;
+ Object result = super.invokeMemberMethod( tree, TagTree.class,
+ "isTailMatch", argClasses, args ) ;
+ return ( ( Boolean ) result ).booleanValue() ;
+ }
+
+
+ /**
+ * Used to white box test the private isReverseTailMatch() method of the
+ * TagTree.
+ *
+ * @param tree the tree instance to test
+ * @param pattern the pattern arg
+ * @param stack the stack arg
+ * @return the resultant true or false return value
+ */
+ private boolean isReverseTailMatch( TagTree tree, int[] pattern,
+ Stack stack )
+ {
+ Class[] argClasses = { pattern.getClass(), Stack.class } ;
+ Object[] args = { pattern, stack } ;
+ Object result = super.invokeMemberMethod( tree, TagTree.class,
+ "isReverseTailMatch", argClasses, args ) ;
+ return ( ( Boolean ) result ).booleanValue() ;
+ }
+
+
+ /**
+ * Tests the private isTailMatch() method.
+ */
+ public void testIsTailMatch()
+ {
+ TagTree tree = new TagTree() ;
+ int[] pattern = {TagTree.WILDCARD,1,2,3} ;
+ Stack stack = new Stack() ;
+ assertFalse( isTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 5 ) ) ;
+ assertFalse( isTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 6 ) ) ;
+ assertFalse( isTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 1 ) ) ;
+ assertFalse( isTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 2 ) ) ;
+ assertFalse( isTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 3 ) ) ;
+ assertTrue( isTailMatch( tree, pattern, stack ) ) ;
+
+ tree = new TagTree() ;
+ pattern = new int[]{TagTree.WILDCARD} ;
+ stack = new Stack() ;
+ assertTrue( isTailMatch( tree, pattern, stack ) ) ;
+
+ tree = new TagTree() ;
+ pattern = new int[]{} ;
+ stack = new Stack() ;
+ assertTrue( isTailMatch( tree, pattern, stack ) ) ;
+
+ tree = new TagTree() ;
+ pattern = new int[]{TagTree.WILDCARD, 1} ;
+ stack = new Stack() ;
+ assertFalse( isTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 2 ) ) ;
+ assertFalse( isTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 1 ) ) ;
+ assertTrue( isTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 1 ) ) ;
+ assertTrue( isTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 2 ) ) ;
+ assertFalse( isTailMatch( tree, pattern, stack ) ) ;
+ }
+
+
+ /**
+ * Tests the private isTailMatch() method.
+ */
+ public void testIsReverseTailMatch()
+ {
+ TagTree tree = new TagTree() ;
+ int[] pattern = {TagTree.WILDCARD,1,2,3} ;
+ Stack stack = new Stack() ;
+ stack.push( new Integer( 3 ) ) ;
+ assertFalse( isReverseTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 2 ) ) ;
+ assertFalse( isReverseTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 1 ) ) ;
+ assertTrue( isReverseTailMatch( tree, pattern, stack ) ) ;
+
+ tree = new TagTree() ;
+ pattern = new int[]{TagTree.WILDCARD} ;
+ stack = new Stack() ;
+ assertTrue( isReverseTailMatch( tree, pattern, stack ) ) ;
+
+ tree = new TagTree() ;
+ pattern = new int[]{} ;
+ stack = new Stack() ;
+ assertTrue( isReverseTailMatch( tree, pattern, stack ) ) ;
+
+ tree = new TagTree() ;
+ pattern = new int[]{TagTree.WILDCARD, 1, 1} ;
+ stack = new Stack() ;
+ assertFalse( isReverseTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 1 ) ) ;
+ assertFalse( isReverseTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 1 ) ) ;
+ assertTrue( isReverseTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 2 ) ) ;
+ assertTrue( isReverseTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 3 ) ) ;
+ assertTrue( isReverseTailMatch( tree, pattern, stack ) ) ;
+
+ tree = new TagTree() ;
+ pattern = new int[]{TagTree.WILDCARD, 1, 2} ;
+ stack = new Stack() ;
+ assertFalse( isReverseTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 1 ) ) ;
+ assertFalse( isReverseTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 1 ) ) ;
+ assertFalse( isReverseTailMatch( tree, pattern, stack ) ) ;
+ stack.push( new Integer( 2 ) ) ;
+ assertFalse( isReverseTailMatch( tree, pattern, stack ) ) ;
+ }
+
+
+ /**
+ * Used to white box test the private addWildRuleToNormalTree() method of
+ * the TagTree class.
+ *
+ * @param tree the tree instance to test
+ * @param pattern the 1st int[] pattern arg
+ * @param rule the 2nd Rule arg
+ * @param stack the 3rd Stack arg
+ * @param node the last TagNode arg
+ */
+ public void addWildRuleToNormalTree( TagTree tree, int[] pattern,
+ Rule rule, Stack stack, TagNode node )
+ {
+ Class[] argClasses = {
+ pattern.getClass(), Rule.class, Stack.class, TagNode.class
+ } ;
+
+ Object[] args = { pattern, rule, stack, node } ;
+ super.invokeMemberMethod( tree, TagTree.class,
+ "addWildRuleToNormalTree", argClasses, args ) ;
+ }
+
+
+ /**
+ * Tests various combinations of wild card patterns and trees to make sure
+ * all is working with addWildRuleToNormalTree().
+ */
+ public void testAddWildRuleToNormalTree2()
+ {
+ TagTree tree = new TagTree() ;
+ int[] pattern = {1,2,3} ;
+ Rule r0 = new MockRule() ;
+ tree.addRule( pattern, r0 ) ;
+
+ // Walk the branch of tag nodes and validate contents along the way
+ TagNode node = getNormalNode( tree, 1 ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 2 ) ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 3 ) ) ;
+ assertEquals( 1, node.getRules().size() ) ;
+ assertEquals( r0, node.getRules().get( 0 ) ) ;
+
+ // setup the first wild card addition but it should not match
+ int[] wildpat = { TagTree.WILDCARD,1,2} ;
+ Rule r1 = new MockRule() ;
+ addWildRuleToNormalTree( tree, wildpat, r1, new Stack(), node ) ;
+
+ // the pattern *,1,2 should NOT match 1,2,3
+ // walk of the branch of tag nodes and validate contents along the way
+ node = getNormalNode( tree, 1 ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 2 ) ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 3 ) ) ;
+ assertEquals( 1, node.getRules().size() ) ;
+ assertEquals( r0, node.getRules().get( 0 ) ) ;
+
+ // now try a matching the pattern with *,1,2,3 so r1 should be present
+ wildpat = new int[]{TagTree.WILDCARD, 1, 2, 3} ;
+ r1 = new MockRule() ;
+ node = getNormalNode( tree, 1 ) ;
+ addWildRuleToNormalTree( tree, wildpat, r1, new Stack(), node ) ;
+
+ // the pattern *,1,2,3 should match 1,2,3 now
+ // walk of the branch of tag nodes and validate contents along the way
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 2 ) ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 3 ) ) ;
+ assertEquals( 2, node.getRules().size() ) ;
+ assertEquals( r0, node.getRules().get( 0 ) ) ;
+ assertEquals( r1, node.getRules().get( 1 ) ) ;
+
+ // now try a less specific matching the pattern *,2,3
+ wildpat = new int[]{TagTree.WILDCARD, 2, 3} ;
+ Rule r2 = new MockRule() ;
+ node = getNormalNode( tree, 1 ) ;
+ addWildRuleToNormalTree( tree, wildpat, r2, new Stack(), node ) ;
+
+ // the pattern *,2,3 should match 1,2,3 now
+ // walk of the branch of tag nodes and validate contents along the way
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 2 ) ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 3 ) ) ;
+ assertEquals( 3, node.getRules().size() ) ;
+ assertEquals( r0, node.getRules().get( 0 ) ) ;
+ assertEquals( r1, node.getRules().get( 1 ) ) ;
+ assertEquals( r2, node.getRules().get( 2 ) ) ;
+
+ // now try least specific matching using pattern *,3
+ wildpat = new int[]{TagTree.WILDCARD, 3} ;
+ Rule r3 = new MockRule() ;
+ node = getNormalNode( tree, 1 ) ;
+ addWildRuleToNormalTree( tree, wildpat, r3, new Stack(), node ) ;
+
+ // the pattern *,3 should match 1,2,3 now
+ // walk of the branch of tag nodes and validate contents along the way
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 2 ) ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 3 ) ) ;
+ assertEquals( 4, node.getRules().size() ) ;
+ assertEquals( r0, node.getRules().get( 0 ) ) ;
+ assertEquals( r1, node.getRules().get( 1 ) ) ;
+ assertEquals( r2, node.getRules().get( 2 ) ) ;
+ assertEquals( r3, node.getRules().get( 3 ) ) ;
+ }
+
+
+ /**
+ * Tests to see that we do not add the rule with wild card pattern more
+ * than once to a node in the normal tree by first checking if it already
+ * contains that rule before a rule add operation to the node.
+ */
+ public void testAddWildRuleToNormalTree1()
+ {
+ TagTree tree = new TagTree() ;
+ int[] pattern = {1,2,3} ;
+ Rule r0 = new MockRule() ;
+ tree.addRule( pattern, r0 ) ;
+
+ int[] wildpat = { TagTree.WILDCARD,1,2,3} ;
+ TagNode node = getNormalNode( tree, 1 ) ;
+
+ // see if the rule r0 is added - should not be!
+ addWildRuleToNormalTree( tree, wildpat, r0, new Stack(), node ) ;
+ node = node.getChild( new Integer( 2 ) ).getChild( new Integer( 3 ) ) ;
+ List rules = node.getRules() ;
+
+ // only one copy of r0 should exist
+ assertEquals( 1, rules.size() ) ;
+ assertEquals( r0, rules.get( 0 ) ) ;
+ }
+
+
+ /**
+ * Used to white box test the private addWildRuleToNormalTree() method of
+ * the TagTree class.
+ *
+ * @param tree the tree instance to test
+ * @param pattern the 1st int[] pattern arg
+ * @param rule the 2nd Rule arg
+ * @param stack the 3rd Stack arg
+ * @param node the last TagNode arg
+ */
+ public void addWildRuleToWildTree( TagTree tree, int[] pattern,
+ Rule rule, Stack stack, TagNode node )
+ {
+ Class[] argClasses = {
+ pattern.getClass(), Rule.class, Stack.class, TagNode.class
+ } ;
+
+ Object[] args = { pattern, rule, stack, node } ;
+ super.invokeMemberMethod( tree, TagTree.class,
+ "addWildRuleToWildTree", argClasses, args ) ;
+ }
+
+
+
+ /**
+ * Tests various combinations of wild card patterns and trees to make sure
+ * all is working with addWildRuleToWildTree().
+ */
+ public void testAddWildRuleToWildTree2()
+ {
+ TagTree tree = new TagTree() ;
+ TagNode n0 = new TagNode( new Integer( 2 ) ) ;
+ TagNode n1 = new TagNode( new Integer( 1 ) ) ;
+ TagNode n2 = new TagNode( new Integer( 3 ) ) ;
+ n0.addNode( n1 ) ;
+ n1.addNode( n2 ) ;
+ HashMap wildNodes = ( HashMap ) getMember( "wildNodes", tree ) ;
+ wildNodes.put( new Integer( 2 ), n0 ) ;
+
+ int[] pattern = {TagTree.WILDCARD,1,2} ;
+ Rule r0 = new MockRule() ;
+ addWildRuleToWildTree( tree, pattern, r0, new Stack(), n0 ) ;
+
+ // the pattern *,1,2 should match at nodes 2-1 and 2-1-3
+ assertEquals( 0, n0.getRules().size() ) ;
+ assertEquals( 1, n1.getRules().size() ) ;
+ assertEquals( r0, n1.getRules().get( 0 ) ) ;
+ assertEquals( 1, n2.getRules().size() ) ;
+ assertEquals( r0, n2.getRules().get( 0 ) ) ;
+ }
+
+ /**
+ * Tests various combinations of wild card patterns and trees to make sure
+ * all is working with addWildRuleToWildTree().
+ */
+ public void testAddWildRuleToWildTree1()
+ {
+ TagTree tree = new TagTree() ;
+ TagNode n0 = new TagNode( new Integer( 2 ) ) ;
+ TagNode n1 = new TagNode( new Integer( 1 ) ) ;
+ TagNode n2 = new TagNode( new Integer( 3 ) ) ;
+ n0.addNode( n1 ) ;
+ n1.addNode( n2 ) ;
+ HashMap wildNodes = ( HashMap ) getMember( "wildNodes", tree ) ;
+ wildNodes.put( new Integer( 2 ), n0 ) ;
+
+ int[] pattern = {TagTree.WILDCARD,1,2} ;
+ Rule r0 = new MockRule() ;
+ n1.addRule( r0 );
+ n2.addRule( r0 );
+ addWildRuleToWildTree( tree, pattern, r0, new Stack(), n0 ) ;
+
+ // the pattern *,1,2 should match at nodes 2-1 and 2-1-3
+ assertEquals( 0, n0.getRules().size() ) ;
+ assertEquals( 1, n1.getRules().size() ) ;
+ assertEquals( r0, n1.getRules().get( 0 ) ) ;
+ assertEquals( 1, n2.getRules().size() ) ;
+ assertEquals( r0, n2.getRules().get( 0 ) ) ;
+ }
+
+
/**
* Tests the addRule method of the tree.
*/
- public void testAddRule()
+ public void testAddRuleNormal()
{
TagTree tree = new TagTree() ;
int[] pattern = {1,2,3} ;
tree.addRule( pattern, new MockRule() ) ;
-
- assertNull( tree.getNode(4) ) ;
-
- TagNode node = tree.getNode( 1 ) ;
+ assertNull( getNormalNode( tree, 4 ) ) ;
+
+ TagNode node = getNormalNode( tree, 1 ) ;
assertNotNull( node ) ;
node = node.getChild( new Integer(2) ) ;
assertNotNull( node ) ;
@@ -62,12 +445,250 @@
node = node.getChild( new Integer(4) ) ;
assertNull( node ) ;
- int[] pat1 = {1,2,3} ;
tree.addRule( pattern, new MockRule() ) ;
}
/**
+ * Used to white box test the private addWildRule() method of the
+ * TagTree.
+ *
+ * @param tree the tree instance to test
+ * @param pattern the pattern arg
+ * @param rule the Rule arg
+ */
+ private void addWildRule( TagTree tree, int[] pattern, Rule rule )
+ {
+ Class[] argClasses = { pattern.getClass(), Rule.class } ;
+ Object[] args = { pattern, rule } ;
+ super.invokeMemberMethod( tree, TagTree.class, "addWildRule",
+ argClasses, args ) ;
+ }
+
+
+ /**
+ * Used to white box test the private addNormalRule() method of the
+ * TagTree.
+ *
+ * @param tree the tree instance to test
+ * @param pattern the pattern arg
+ * @param rule the Rule arg
+ */
+ private void addNormalRule( TagTree tree, int[] pattern, Rule rule )
+ {
+ Class[] argClasses = { pattern.getClass(), Rule.class } ;
+ Object[] args = { pattern, rule } ;
+ super.invokeMemberMethod( tree, TagTree.class, "addNormalRule",
+ argClasses, args ) ;
+ }
+
+
+ /**
+ * Tests the addRule method of the tree.
+ */
+ public void testAddWildRule1()
+ {
+ TagTree tree = new TagTree() ;
+ int[] pattern = {TagTree.WILDCARD,1,2,3} ;
+ Rule r0 = new MockRule() ;
+ addWildRule( tree, pattern, r0 );
+ assertNull( getWildNode( tree, 4 ) ) ;
+
+ TagNode node = getWildNode( tree, 3 ) ;
+ assertNotNull( node ) ;
+ node = node.getChild( new Integer(2) ) ;
+ assertNotNull( node ) ;
+ node = node.getChild( new Integer(1) ) ;
+ assertNotNull( node ) ;
+ assertEquals( 1, node.getRules().size() ) ;
+ assertEquals( r0, node.getRules().get( 0 ) ) ;
+ node = node.getChild( new Integer(4) ) ;
+ assertNull( node ) ;
+ }
+
+
+ /**
+ * Tests the addRule method of the tree.
+ */
+ public void testAddWildRule2()
+ {
+ TagTree tree = new TagTree() ;
+ int[] pattern0 = {TagTree.WILDCARD,1,2} ;
+ int[] pattern1 = {3,1,2} ;
+ int[] pattern2 = {TagTree.WILDCARD,2} ;
+ Rule r0 = new MockRule() ;
+ Rule r1 = new MockRule() ;
+ Rule r2 = new MockRule() ;
+ addNormalRule( tree, pattern1, r1 ) ;
+ addWildRule( tree, pattern0, r0 );
+ assertNull( getWildNode( tree, 4 ) ) ;
+
+ // now test that we have made the addition to the wild tree
+ TagNode node = getWildNode( tree, 2 ) ;
+ assertNotNull( node ) ;
+ node = node.getChild( new Integer(1) ) ;
+ assertNotNull( node ) ;
+ assertEquals( 1, node.getRules().size() ) ;
+ assertEquals( r0, node.getRules().get( 0 ) ) ;
+
+ node = node.getChild( new Integer(4) ) ;
+ assertNull( node ) ;
+
+ // now test the normal tree
+ HashMap normNodes = ( HashMap ) getMember( "normNodes", tree ) ;
+ assertEquals( 1, normNodes.size() ) ;
+ node = getNormalNode( tree, 3 ) ;
+ assertNotNull( node ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 1 ) ) ;
+ assertNotNull( node ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 2 ) ) ;
+ assertNotNull( node ) ;
+ assertEquals( 2, node.getRules().size() ) ;
+ assertEquals( r1, node.getRules().get( 0 ) ) ;
+ assertEquals( r0, node.getRules().get( 1 ) ) ;
+
+ // now we'll add the other wild card and see if it adds correctly
+ addWildRule( tree, pattern2, r2 ) ;
+
+ // test that we have made the r2 addition to the places in wild tree
+ node = getWildNode( tree, 2 ) ;
+ assertNotNull( node ) ;
+ assertEquals( 1, node.getRules().size() ) ;
+ assertEquals( r2, node.getRules().get( 0 ) ) ;
+ node = node.getChild( new Integer(1) ) ;
+ assertNotNull( node ) ;
+ assertEquals( 2, node.getRules().size() ) ;
+ assertEquals( r0, node.getRules().get( 0 ) ) ;
+ assertEquals( r2, node.getRules().get( 1 ) ) ;
+ assertTrue( node.isLeaf() ) ;
+
+ // test that we have added r2 to the normal tree
+ assertEquals( 1, normNodes.size() ) ;
+ node = getNormalNode( tree, 3 ) ;
+ assertNotNull( node ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 1 ) ) ;
+ assertNotNull( node ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 2 ) ) ;
+ assertNotNull( node ) ;
+ assertEquals( 3, node.getRules().size() ) ;
+ assertEquals( r1, node.getRules().get( 0 ) ) ;
+ assertEquals( r0, node.getRules().get( 1 ) ) ;
+ assertEquals( r2, node.getRules().get( 2 ) ) ;
+
+ // control
+ node = node.getChild( new Integer(4) ) ;
+ assertNull( node ) ;
+ }
+
+
+ /**
+ * Tests the addNormalRule method of the tree after registering
+ * rule patterns using wild cards.
+ */
+ public void testAddNormalRule1()
+ {
+ TagTree tree = new TagTree() ;
+ int[] pattern0 = {TagTree.WILDCARD,1,2} ;
+ int[] pattern1 = {3,1,2} ;
+ int[] pattern2 = {TagTree.WILDCARD,2} ;
+ Rule r0 = new MockRule() ;
+ Rule r1 = new MockRule() ;
+ Rule r2 = new MockRule() ;
+ addNormalRule( tree, pattern1, r1 ) ;
+ addWildRule( tree, pattern0, r0 );
+ assertNull( getWildNode( tree, 4 ) ) ;
+
+ // now test that we have made the addition to the wild tree
+ TagNode node = getWildNode( tree, 2 ) ;
+ assertNotNull( node ) ;
+ node = node.getChild( new Integer(1) ) ;
+ assertNotNull( node ) ;
+ assertEquals( 1, node.getRules().size() ) ;
+ assertEquals( r0, node.getRules().get( 0 ) ) ;
+
+ node = node.getChild( new Integer(4) ) ;
+ assertNull( node ) ;
+
+ // now test the normal tree
+ HashMap normNodes = ( HashMap ) getMember( "normNodes", tree ) ;
+ assertEquals( 1, normNodes.size() ) ;
+ node = getNormalNode( tree, 3 ) ;
+ assertNotNull( node ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 1 ) ) ;
+ assertNotNull( node ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 2 ) ) ;
+ assertNotNull( node ) ;
+ assertEquals( 2, node.getRules().size() ) ;
+ assertEquals( r1, node.getRules().get( 0 ) ) ;
+ assertEquals( r0, node.getRules().get( 1 ) ) ;
+
+ // now we'll add the other wild card and see if it adds correctly
+ addWildRule( tree, pattern2, r2 ) ;
+
+ // test that we have made the r2 addition to the places in wild tree
+ node = getWildNode( tree, 2 ) ;
+ assertNotNull( node ) ;
+ assertEquals( 1, node.getRules().size() ) ;
+ assertEquals( r2, node.getRules().get( 0 ) ) ;
+ node = node.getChild( new Integer(1) ) ;
+ assertNotNull( node ) ;
+ assertEquals( 2, node.getRules().size() ) ;
+ assertEquals( r0, node.getRules().get( 0 ) ) ;
+ assertEquals( r2, node.getRules().get( 1 ) ) ;
+ assertTrue( node.isLeaf() ) ;
+
+ // test that we have added r2 to the normal tree
+ assertEquals( 1, normNodes.size() ) ;
+ node = getNormalNode( tree, 3 ) ;
+ assertNotNull( node ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 1 ) ) ;
+ assertNotNull( node ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 2 ) ) ;
+ assertNotNull( node ) ;
+ assertEquals( 3, node.getRules().size() ) ;
+ assertEquals( r1, node.getRules().get( 0 ) ) ;
+ assertEquals( r0, node.getRules().get( 1 ) ) ;
+ assertEquals( r2, node.getRules().get( 2 ) ) ;
+
+ // control
+ node = node.getChild( new Integer(4) ) ;
+ assertNull( node ) ;
+
+ // lets add a normal node to the normal tree matching these patterns
+ int[] pattern3 = {8,1,2} ;
+ Rule r3 = new MockRule() ;
+ List wildRegistrations = ( List )
+ getMember( "wildRegistrations", tree ) ;
+ wildRegistrations.add( new RuleRegistration( pattern0, r0 ) ) ;
+ wildRegistrations.add( new RuleRegistration( pattern2, r2 ) ) ;
+ addNormalRule( tree, pattern3, r3 ) ;
+
+ // test if we have added the rules and nodes correctly
+ assertEquals( 2, normNodes.size() ) ;
+ node = getNormalNode( tree, 8 ) ;
+ assertNotNull( node ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 1 ) ) ;
+ assertNotNull( node ) ;
+ assertEquals( 0, node.getRules().size() ) ;
+ node = node.getChild( new Integer( 2 ) ) ;
+ assertNotNull( node ) ;
+ assertEquals( 3, node.getRules().size() ) ;
+ assertEquals( r0, node.getRules().get( 0 ) ) ;
+ assertEquals( r2, node.getRules().get( 1 ) ) ;
+ assertEquals( r3, node.getRules().get( 2 ) ) ;
+ }
+
+
+ /**
* Tests the TagTree.match(int[]) method.
*/
public void testMatchintArray()
@@ -127,7 +748,7 @@
/**
- * Tests the TagTree.getNode(int[]) method.
+ * Tests the TagTree.getNormalNode(int[]) method.
*/
public void testGetNodeintArray()
{
Added: incubator/directory/snickers/trunk/ber-codec/src/test/org/apache/snickers/ber/digester/testutils/PrivateTestCase.java
==============================================================================
--- (empty file)
+++ incubator/directory/snickers/trunk/ber-codec/src/test/org/apache/snickers/ber/digester/testutils/PrivateTestCase.java Wed Jun 9 21:42:16 2004
@@ -0,0 +1,174 @@
+/*
+ * Copyright 2004 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ */
+package org.apache.snickers.ber.digester.testutils;
+
+
+import java.lang.reflect.Method;
+import java.lang.reflect.InvocationTargetException;
+import java.lang.reflect.Field;
+
+import junit.framework.TestCase;
+import org.apache.commons.lang.exception.NestableRuntimeException;
+
+
+/**
+ * A utility base class used to test private methods in classes using
+ * reflection workarounds for accessing private member and static methods.
+ *
+ * @author <a href="mailto:directory-dev@incubator.apache.org">Apache Directory
+ * Project</a>
+ * @version $Rev$
+ */
+public class PrivateTestCase extends TestCase
+{
+ public PrivateTestCase()
+ {
+ super();
+ }
+
+
+ public PrivateTestCase( String s )
+ {
+ super( s );
+ }
+
+
+ protected Object getMember( String name, Object obj )
+ {
+ try
+ {
+ Field field = obj.getClass().getDeclaredField( name ) ;
+ field.setAccessible( true ) ;
+ return field.get( obj ) ;
+ }
+ catch ( NoSuchFieldException e )
+ {
+ throw new TestFailedException( e ) ;
+ }
+ catch ( IllegalAccessException e )
+ {
+ throw new TestFailedException( e ) ;
+ }
+ }
+
+
+ protected Object invokeMemberMethod( Object obj, Class targetClass,
+ String methodName, Class[] argClasses, Object[] argObjects )
+ {
+ try
+ {
+ Method method = targetClass.getDeclaredMethod( methodName,
+ argClasses );
+ method.setAccessible( true );
+ return method.invoke( obj, argObjects );
+
+ }
+ catch ( NoSuchMethodException e )
+ {
+ // Should happen only rarely, because most times the
+ // specified method should exist. If it does happen, just let
+ // the test fail so the programmer can fix the problem.
+ throw new TestFailedException( e );
+ }
+ catch ( SecurityException e )
+ {
+ // Should happen only rarely, because the setAccessible(true)
+ // should be allowed in when running unit tests. If it does
+ // happen, just let the test fail so the programmer can fix
+ // the problem.
+ throw new TestFailedException( e );
+ }
+ catch ( IllegalAccessException e )
+ {
+ // Should never happen, because setting accessible flag to
+ // true. If setting accessible fails, should throw a security
+ // exception at that point and never get to the invoke. But
+ // just in case, wrap it in a TestFailedException and let a
+ // human figure it out.
+ throw new TestFailedException( e );
+ }
+ catch ( IllegalArgumentException e )
+ {
+ // Should happen only rarely, because usually the right
+ // number and types of arguments will be passed. If it does
+ // happen, just let the test fail so the programmer can fix
+ // the problem.
+ throw new TestFailedException( e );
+ }
+ catch ( InvocationTargetException e )
+ {
+ throw new TestFailedException( e.getTargetException() );
+ }
+ }
+
+
+ protected Object invokeStaticMethod( Class targetClass,
+ String methodName, Class[] argClasses, Object[] argObjects )
+ throws InvocationTargetException
+ {
+
+ try
+ {
+ Method method = targetClass.getDeclaredMethod( methodName,
+ argClasses );
+ method.setAccessible( true );
+ return method.invoke( null, argObjects );
+
+ }
+ catch ( NoSuchMethodException e )
+ {
+ // Should happen only rarely, because most times the
+ // specified method should exist. If it does happen, just let
+ // the test fail so the programmer can fix the problem.
+ throw new TestFailedException( e );
+ }
+ catch ( SecurityException e )
+ {
+ // Should happen only rarely, because the setAccessible(true)
+ // should be allowed in when running unit tests. If it does
+ // happen, just let the test fail so the programmer can fix
+ // the problem.
+ throw new TestFailedException( e );
+ }
+ catch ( IllegalAccessException e )
+ {
+ // Should never happen, because setting accessible flag to
+ // true. If setting accessible fails, should throw a security
+ // exception at that point and never get to the invoke. But
+ // just in case, wrap it in a TestFailedException and let a
+ // human figure it out.
+ throw new TestFailedException( e );
+ }
+ catch ( IllegalArgumentException e )
+ {
+ // Should happen only rarely, because usually the right
+ // number and types of arguments will be passed. If it does
+ // happen, just let the test fail so the programmer can fix
+ // the problem.
+ throw new TestFailedException( e );
+ }
+ }
+
+
+ class TestFailedException extends NestableRuntimeException
+ {
+ TestFailedException( Throwable t )
+ {
+ super( t ) ;
+ }
+ }
+}
Modified: incubator/directory/snickers/trunk/ldap-ber-provider/src/test/org/apache/snickers/ldap/SearchRequestTest.java
==============================================================================
--- incubator/directory/snickers/trunk/ldap-ber-provider/src/test/org/apache/snickers/ldap/SearchRequestTest.java (original)
+++ incubator/directory/snickers/trunk/ldap-ber-provider/src/test/org/apache/snickers/ldap/SearchRequestTest.java Wed Jun 9 21:42:16 2004
@@ -60,8 +60,8 @@
FilterParserImpl parser = new FilterParserImpl() ;
ExprNode node = null ;
- node = parser.parse( "(& (ou=Human Resources) (l=SunnyVale) " +
- " (| (uid=akarasulu) (! (uid=jbean ) ) ) )" ) ;
+ node = parser.parse( "( & ( ou = Human Resources ) ( l = SunnyVale ) "
+ + " ( | ( uid = akarasulu ) ( ! ( uid = jbean ) ) ) )" ) ;
req.setFilter( node ) ;
System.out.println( "Generated SearchRequest for test:" ) ;
Modified: incubator/directory/snickers/trunk/xdocs/ber-codec/BERDigesterDesign.xml
==============================================================================
--- incubator/directory/snickers/trunk/xdocs/ber-codec/BERDigesterDesign.xml (original)
+++ incubator/directory/snickers/trunk/xdocs/ber-codec/BERDigesterDesign.xml Wed Jun 9 21:42:16 2004
@@ -9,11 +9,13 @@
<subsection name="What is it?">
<p>
- The BERDigester is a high level decoder that builds object
- containment trees from a train of TLV Tuple objects it receives via
- BERDecoder callback events. It builds these containment trees
- through the action of rules that are triggered by TLV Tag nesting
- patterns.
+ The digester is a high level decoder that builds object
+ containment trees from a stream of events it receives via callback
+ events. These callbacks notify of the start and end of BER tuples
+ composed of a Tag, a Length and a Value within the underlying stream.
+ Rules, registered with Tag nesting patterns are used to build
+ containment trees using an object stack. Rules are triggered when
+ Tag nesting patterns match the patterns registered with the rule.
</p>
</subsection>
@@ -26,7 +28,7 @@
The Commons Digester consumed these events. While processing these
events it tracked the nesting of XML elements and fired registered
rules when nesting patterns were matched. These rules performed
- operation on the Digester's stack. Objects were instantiated and
+ operations on the Digester's stack: objects were instantiated and
pushed, or populated and then popped to build the containment tree.
</p>
@@ -37,7 +39,7 @@
event streams BER TLV event streams signal the nesting pattern of
underlying constructs within the stream. This hence reviels the
structure of an ASN.1 data type or in the case of SAX the structure
- of an XML document. Both digesters consume events emmination from
+ of an XML document. Both digesters consume events emminating from
some event source to build object containment trees based on the
nesting pattern revieled by those events. The containment trees are
built through the action of rules triggered by matching nesting
@@ -156,61 +158,107 @@
<subsection name="Pattern Matching">
<p>
- Without going into too much detail, matching a rule pattern to the
- nesting of tag ints within the tagStack seems pretty simple.
- Compare each int value at a position within both int sequences and
- see if at any point there are differences. If there are differences
- the pattern does not match the tag nesting pattern. If there are no
- differences then its a match. The issues with this algorithm start
- popping up when we consider performance and the number of rules that
- must be compared within the digester's rule base (set of registered
- rules). To calculate the matching rules for a nesting pattern we
- would have to perform N comparisons where N is the number of
- registered rules. These calculations would have to occur every time
- a tag int is pushed onto the stack. If you ask me this brute force
- approach is unacceptable.
- </p>
- <p>
- To reduce the need to compute N comparisons we have built a special
- data structure used to store, and rapidly search for all matching
- rules. The data structure is a tree of TagNodes. Every TagNode
- in the tree stores the canonical representation of a tag int and a
- set of rules. TagNodes may have child TagNodes keyed by their tag
- int value. A depth first tree walk is conducted to search for the
- set of rules that are matched by the current nesting pattern. The
- tree walk starts at the root of the tree using the Tag int value to
- determine the child to lookup. The walk then continues with the
- child and the next Tag int used to lookup the next child and so on.
- If the walk consumes all tag ints within the stack and lands on a
- TagNode then all the rules at that node have matched the nesting
- pattern.
- </p>
- <p>
- This tree data structure is built as rules are registered with the
- digester. Each rule registered either adds a new path of TagNodes
- to the tree, of adds itself to an existing node within the tree.
- Once built the structure can be searched to determine the rules
- matched by a nesting pattern. The data structure is small, cheap
- and turns an order O(nm) search operation where n is the number of
- rules an m is the current tag nesting depth into a O(m) search
- operation which is much better.
- </p>
- <p>
- The only problem I have at this point is how to implement matching
- pattern wildcards used to register rules with. I have some ideas
- on how this can be done though. First of all a special reserved tag
- int value must be selected so it does not conflict with any valid
- tags we might encounter. I think any of the UNIVERSAL tags above
- 32 can be used for this but I would have to check. Presuming this
- were known already there are four kinds of wildcard use cases which
- I have outlined below:
+ To trigger rules the digester checks every new tag nesting pattern
+ to see if it matches any of the patterns registered with a rule.
+ Multiple patterns may be registered with a rule to allow it to fire
+ under different contexts. With every in coming event which changes
+ the tag nesting pattern, the digester must see if the tag nesting
+ pattern matches any of the patterns for every registered rule. This
+ could be an expensive operation to have to perform with every event
+ if the rule and pattern base is large. Every registered rule pattern
+ would have to be tested for equality with the tag nesting pattern to
+ determine if the corresponding rule needs to fire.
+ </p>
+
+ <p>
+ To keep pattern matching overheads constant regardless of the number
+ of rules registered, a special data structure, a search tree called
+ the TagTree is used. The tree is composed of TagNodes and is built
+ as rules and their patterns are registered. The tree's tag nodes
+ simply correspond to a tag value, and have a list of rules. Tag
+ nodes maintain a hash of children keyed by their tag value. Here's
+ an example of a TagTree for the following rule pattern registrations:
+ </p>
+
+ <table>
+ <tr>
+ <th>Rule</th>
+ <th>Pattern</th>
+ </tr>
+
+ <tr>
+ <td>R0</td>
+ <td>[1,2,3,4,5]</td>
+ </tr>
+
+ <tr>
+ <td>R1</td>
+ <td>[1,2,5]</td>
+ </tr>
+
+ <tr>
+ <td>R2</td>
+ <td>[1,2,3]</td>
+ </tr>
+
+ <tr>
+ <td>R3</td>
+ <td>[4,4,5]</td>
+ </tr>
+
+ <tr>
+ <td>R0</td>
+ <td>[4,1,2,4]</td>
+ </tr>
+ </table>
+
+ <br></br>
+
+ <center>
+ <img src="../images/TagTree.png"/>
+ </center>
+
+ <p>
+ Whenever possible nodes in the tree are reused while adding new
+ patterns and rules to the tree. Each new pattern added to the tree
+ corresponds to a new unique path within the tree. Rule registration
+ is where the true cost of the tree's construction is incurred. In
+ the solid state the tree is only used to rapidly search for the set
+ of rules to fire based on the current nesting pattern. The search
+ occurs by walking the tree with the current nesting pattern. For
+ example a walk using the [1,2,3] nesting pattern takes us from the
+ root to tag node 1, then 2 and finally tag node 3. Once the pattern
+ is exhausted, meaning all tag values are consumed in the walk, the
+ rules at the final node are returned as the matching set that need to
+ be fired. If there are no rules at that node, then the set is empty.
+ If the pattern "walks off the tree", where no child with a tag value
+ is available to continue the walk on the tree, the search ends
+ returning the empty set.
+ </p>
+
+ <p>
+ Without the tag tree every pattern registered with a rule would have
+ to be compared. This is an O(nm) operation where n is the number of
+ pattern registrations and m is the size of the pattern. With the tag
+ tree the search time is only O(m) where only the size of the pattern
+ determine the search time. This is much more acceptable.
+ </p>
+
+ <p>
+ The only remaining problem at this point is how to implement wild
+ cards with pattern matching. First of all a special reserved tag
+ int value must be selected as the wild card ("*") value so it does
+ not conflict with any valid tags we might encounter. I think any of
+ the UNIVERSAL tags above 32 can be used for this but I would have to
+ check. Plus there are four kinds of wildcard use cases which are
+ possible:
</p>
<ol>
<li>wildcard at the front of the pattern</li>
<li>wildcard at the end of the pattern</li>
<li>wildcard in the middle of the pattern</li>
- <li>two or more wildcards in the middle of the pattern</li>
+ <li>two or more wildcards in a pattern</li>
</ol>
<p>
@@ -220,21 +268,146 @@
implement for the return in expressivity. At this point I plan to
implement any of these use cases on an as needed basis. However
the two noteworthy use cases that stick out are use case #1 and #2.
- When handling fragmented strings encoded using constructed tuples
- #2 will come in handy if we want a rule to fire off for each
- fragment. Likewise #1 will be useful as well. Sometimes a pattern
- may occur multiple times in different places and you want to detect
- them all using a single rule. In this case, a pattern with a
- wildcard at the front (case #1) does the job. Use cases #3 and #4
- are very difficult to implement not to mention expensive in terms
- of processing. They just don't seem worth it.
+ #2 is useful for rule used to build ASN.1 strings that are broken
+ apart using the constructed BER encoding. #1 will be useful as well.
+ Sometimes a pattern may occur multiple times in different contexts
+ and you want to detect them all using a single rule. In this case,
+ a pattern with a wildcard at the front (case #1) does the job.
+ Furthermore recursive ASN.1 definitions as those found with the
+ LDAP SearchRequest, will require wildcard use case #1.
+ Use cases #3 and #4 are very difficult to implement not to mention
+ expensive in terms of processing. They just don't seem worth it.
</p>
+ </subsection>
+ <subsection name="Pattern Matching with Wild Cards">
<p>
- Now the question is how do we search with a wildcard in the front or
- at the tail end of the pattern.
+ The LDAP SearchRequest requires the use case where the wild card is
+ in the middle of the rule matching pattern because of a recursive
+ ASN.1 definition for Filter expressions. This means the nesting could
+ be arbitrarily deep so long as the end sequence of tag nesting
+ matches the tail of the pattern and the start sequences matches the
+ front. The use of a wild card at the front of the pattern would
+ also satisfy this use case although with less specificity. However
+ it would be easier to implement so we're going to shoot for wild
+ cards in the front of a pattern first which corresponds to use case
+ #1 above.
+ </p>
+
+ <p>
+ Matching for patterns with wild cards in front requires the use of
+ another searchable TagTree similar to the one used for patterns
+ without wild cards. This new TagTree is built using the reverse
+ sequence of the wild card pattern's tail. So if a rule is added using
+ the wild card pattern, [*,6,3,9], a branch is created in an empty
+ TagTree in the order 9-3-6. Besides just adding the reverse
+ branch the tree must be searched for any existing branches that
+ end with 9, 3 and 6. So if there was a branch 9-3-6-4 based on the
+ pattern [*,4,6,3,9] we would add the rule to node 4 in this branch
+ as well as to node 6 in branch 9-3-6 created by pattern [6,3,9].
+ The fact that node 9-3-6-4 contains the rule can be inferred from
+ it being a child of 9-3-6 while conducting a search to return both
+ rules. The addition of the rule to both nodes 6 and 4 is a bit
+ redundant, however this is done during rule addition, so we do not
+ have to compute this and collect extra rules while walking the tree
+ to find all matching rules. We want to follow a strategy where the
+ amount of object creation, and computation is minimal while search.
+ What ever needs to be calculated to avoid the penalty during a search
+ we do during rule pattern registration. This strategy is followed
+ to conduct searches for matching rules as fast as possible requiring
+ the minimum amount of work. Here's an example of what a tree with
+ wild cards might look like when registrations with the following
+ patterns and rules are applied:
+ </p>
+
+ <table>
+ <tr>
+ <th>Rule</th>
+ <th>Wild Carded Pattern</th>
+ </tr>
+
+ <tr>
+ <td>R0</td>
+ <td>[*,6,3,9]</td>
+ </tr>
+
+ <tr>
+ <td>R1</td>
+ <td>[*,4,3,9]</td>
+ </tr>
+
+ <tr>
+ <td>R2</td>
+ <td>[*,1,2,5]</td>
+ </tr>
+
+ <tr>
+ <td>R3</td>
+ <td>[*,1,2]</td>
+ </tr>
+
+ <tr>
+ <td>R4</td>
+ <td>[*,3,1,2]</td>
+ </tr>
+
+ </table>
+
+ <br></br>
+
+ <center>
+ <img src="../images/WildTagTree.png"/>
+ </center>
+
+ <p>
+ Furthermore rules added via wild cards are also added to all nodes
+ satisfying the pattern in the primary tag tree used for patterns
+ without wild card patterns. This is done again to avoid having to
+ gather rules while conducting the search. It also avoids having to
+ instantiate a List for every event if we are not gathering rules but
+ just returning an existing list from one of the trees. By adding the
+ rule with the wild card to the tree of patterns without wild cards
+ any node that is selected already accounts for firing rules
+ registered using patterns with wild cards. Hence the other tree with
+ wild cards does not need to be searched. Again this is somewhat
+ redundant to do but it allows the return of the List at a single node
+ without having to gather rules into a newly instantiated List. This
+ all makes more sense when we look at the modified matching algorithm
+ used:
+ </p>
+
+ <ol>
+ <li>walk TagTree without wild cards with nesting pattern</li>
+ <li>if we find a TagNode for the pattern return rules and be done</li>
+ <li>if no match, take the reverse pattern and walk wild tag tree</li>
+ <li>last node before falling off of tree is the matching node</li>
+ <li>if no node matched before walking off then return empty set</li>
+ <li>otherwise return the rules in this last node</li>
+ </ol>
- THIS STUFF NEEDS TO BE FIGURED OUT!
+ <p>
+ The way we match is different for both TagTrees. In the first we're
+ walking the tree using the pattern and if we fall off then we return
+ the empty set. In the second tree with the wild cards, called the
+ WildTagTree, we walk the tree using the reversed pattern tail without
+ the wild card. We also consider our selves matching if we can start
+ a walk at all into some node. Walking off of the WildTagTree selects
+ the last node we were on as the matching node. This nodes rules need
+ to be fired. Furthermore in the WildTagTree search we return the
+ empty set only if we cannot even begin a search.
+ </p>
+
+ <p>
+ Also note that since rules for wild card patterns are added to
+ the matching nodes of the regular TagTree, a match in the first
+ TagTree shorts the search into the second WildTagTree. Another walk
+ in the WildTagTree is not necessary. However, if the walk on the
+ first TagTree falls off, then a search on the WildTagTree is
+ required. By taking this approach we're either returning the list of
+ rules for a TagTree node or returning the list of rules for a
+ WildTagTree node. We never need to create a new list to collect
+ rules in it this way. The final result set equals the list of rules
+ for some node in any of the two trees.
</p>
</subsection>
Added: incubator/directory/snickers/trunk/xdocs/images/TagTree.png
==============================================================================
Binary file. No diff available.
Added: incubator/directory/snickers/trunk/xdocs/images/WildTagTree.png
==============================================================================
Binary file. No diff available.