- 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. -
-- 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. -
-- 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. -
-- 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. +
+ ++ 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: +
+ +| Rule | +Pattern | +
|---|---|
| R0 | +[1,2,3,4,5] | +
| R1 | +[1,2,5] | +
| R2 | +[1,2,3] | +
| R3 | +[4,4,5] | +
| R0 | +[4,1,2,4] | +
+ +
+ + 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. +
+ ++ 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. +
+ ++ 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:
- wildcard at the front of the pattern
- wildcard at the end of the pattern
- wildcard in the middle of the pattern -
- two or more wildcards in the middle of the pattern +
- two or more wildcards in a pattern
@@ -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.
+
+