================================== Decision Trees and Index Selection ================================== One of the most efficient representations for executing a collection of rules is a decision tree expressed as code. This document describes the design (and tests the implementation) of a decision tree building subsystem and its indexing machinery. You do not need to read this unless you are extending these subsystems, e.g. to support outputting something other than bytecode, or to add specialized indexes, an alternate expression language, etc. This document does not describe in detail how indexes are used to build executable decision trees (e.g. in bytecode or source code form), but focuses instead on the overall process of decision tree building, how indexes are selected to build individual nodes, and how these processes can be customized. The algorithms presented here are based in part on the ones described by Craig Chambers and Weimin Chen in their 1999 paper on `Efficient Multiple and Predicate Dispatching `_. We do, however, introduce an improved appraoch to managing inter-expression constraints. The new approach is simpler to explain and implement, while being more precise in what it constrains, as it more directly represents the actual constraints supplied by the input rules. -------------------- Expression Selection -------------------- An "expression" is an object that is used to build individual decision tree nodes, using statistics about which rules accept what values for a particular argument expression. Different expression types are used to apply different kinds of criteria, such as ``isinstance()`` or ``issubclass()`` tests versus equality or other comparison tests. You can create new expression types to support new kinds of criteria. For example, given rules with these criteria:: isinstance(x,Foo) and y==BAR isinstance(x,Baz) and y>0 and z/y<27 Three expressions would be required: one to handle ``isinstance()`` tests on ``x``, one to handle comparison tests on ``y``, and a third to handle comparison tests on ``z/y``. We would want the resulting decision tree to look something like this (ignoring inheritance and various other issues, of course):: switch type(x): case Foo: if y==BAR: ... case Baz: if y>0: if z/y<27: ... The decision tree must meet two requirements: it must be correct, and it must be as efficient as possible. To be efficient, it must test highly selective expressions first. For example, it would be unwise to first test conditions that apply to only a small number of rules. In the above example, testing ``z/y<27`` first would have been wasteful because only one of the two rules cares about the value of ``z/y``. To be correct, however, the tree must avoid reordering tests that are guarded by preconditions -- like ``y>0 and z/y<27``, where the ``y>0`` guards against division by zero. Even if it was highly selective, we can't use the ``z/y`` equality index for the root of the decision tree. These two requirements of correctness and efficiency are met by managing `inter-expression constraints`_ and `selectivity statistics`_, as described in the sections below. Ordering Constraints ==================== Inter-expression ordering constraints ensure that evaluation is not reordered in such a way as to test expressions before their guards. Support for tracking these guards is provided by the ``Ordering`` add-on of an engine:: >>> from peak.rules.indexing import Ordering >>> def f(): """An object to attach some orderings to""" ``Ordering`` add-ons have two methods for managing inter-expression constraints: ``requires()`` and ``can_precede()``. The ``requires()`` method adds a "constraint": a set of expressions that must all have been computed *before* the constrained expression can be used. Let's define a constraint for function ``f`` that says ``z/y`` can only be computed after ``x`` and ``y`` have been examined:: >>> Ordering(f, "z/y").requires(["x", "y"]) We won't add constraints for tests on plain arguments like ``x`` and ``y`` themselves, because argument-only tests can be evaluated in any order. (Note, by the way, that although the examples here use strings, the actual keys or expression objects used can be any hashable object.) An expression can't be used in a decision tree node unless at least one of its constraints is met. As a decision tree is built, the tree builder tracks what expressions haven't yet been used -- and if a required expression hasn't been used yet, any constraints that contain it are not met. Initially, all of our indexes will be unused, but only ``x`` and ``y`` will be usable:: >>> unused = ["x", "y", "z/y"] >>> Ordering(f, "x").can_precede(unused) True >>> Ordering(f, "y").can_precede(unused) True >>> Ordering(f, "z/y").can_precede(unused) False Let's say that the tree builder decides to evaluate ``y``, and then removes it from the unused set:: >>> unused.remove("y") >>> Ordering(f, "x").can_precede(unused) True >>> Ordering(f, "z/y").can_precede(unused) False Since ``x`` is still in the unused set, ``z/y`` still can't be used. We have to remove it also:: >>> unused.remove("x") >>> Ordering(f, "z/y").can_precede(unused) True Multiple Constraints -------------------- You can add more than one ordering constraint for an expression, since the same expression may be used in different positions in different rules. For example, suppose we have the following criteria:: E1 and E2 and E3 and E4 E5 and E3 and E2 and E6 E2 and E3 appear in two different places, resulting in the following ordering constraints for the first expression:: >>> Ordering(f, "E2").requires(["E1"]) # E1 and E2 and E3 and E4 >>> Ordering(f, "E3").requires(["E1", "E2"]) >>> Ordering(f, "E4").requires(["E1", "E2", "E3"]) However, we can shortcut this repetitious process by using the ``define_ordering`` function, which automatically adds all the constraints implied by a given expression sequence:: >>> from peak.rules.indexing import define_ordering >>> define_ordering(f, ["E5","E3","E2","E6"]) # E5 and E3 and E2 and E6 All in all, E3 can be computed as long as either E1 and E2 *or* E5 have been computed. E2 can be computed as long as either E1 *or* E5 and E3 have been computed:: >>> E2 = Ordering(f, "E2") >>> E2.can_precede(["E1", "E2", "E3", "E4", "E5", "E6"]) False >>> E2.can_precede(["E1", "E5"]) False >>> E2.can_precede(["E5"]) True >>> E2.can_precede(["E1"]) True This is somewhat different from the Chambers & Chen approach, in that their approach reduces the above example to a constraint graph of the form:: (E1 or E5) -> (E2 or E3) -> (E4 or E6) Their approach is a little over-optimistic here, in that it assumes that "E5, E2" is a valid calculation sequence, even though this sequence appears nowhere in the input rules! The approach we use (which tracks the *actual* constraints provided by the rules) will allow any of these sequences to compute E2:: E5, E3, E2 E1, E2 E5, E1, E2 E1, E5, E2 It does not overgeneralize from this to assume that "E5, E2" is valid, the way the Chambers & Chen approach does. Constraint Simplification ------------------------- The active constraints of an index are maintained as a set of frozen sets:: >>> from peak.rules.indexing import set, frozenset # 2.3 compatibility >>> E2.constraints == set([frozenset(["E1"]), frozenset(["E5", "E3"])]) True Because constraints are effectively "or"ed together, adding a more restrictive constraint than an existing constraint is ignored:: >>> E2.requires(["E5", "E3", "E4"]) >>> E2.constraints == set([frozenset(["E1"]), frozenset(["E5", "E3"])]) True And if a less-restrictive constraint is added, it replaces any constraints that it's a subset of:: >>> E2.requires(["E5"]) >>> E2.constraints == set([frozenset(["E1"]), frozenset(["E5"])]) True And of course adding the same constraint more than once has no effect:: >>> E4 = Ordering(f, "E4") >>> E4.requires(["E1", "E2", "E3"]) >>> E4.requires(["E1", "E2", "E3"]) >>> E4.constraints == set([frozenset(["E1", "E2", "E3"])]) True Selectivity Statistics ====================== To maximize efficiency, decision tree nodes should always be built using the "most selective" expression that is currently legal to evaluate. Selectivity isn't an absolute measurement, however. It's based on the cases remaining to be distinguished at the current node. If none of the cases at a node care about a particular expression, that expression shouldn't be used. Likewise, if *all* of the rules care about an expression, but they are all expecting the same class or value, there may be better choices that would narrow down the applicable rules faster. All of these conditions can be determined using two statistics: the number of branches that the expression would produce for the current node, and the average number of cases remaining on each of the branches. If none of the cases care about the expression, then each branch will still have the same number of rules as the current node does. Thus the average is N (the number of cases at the current node.) If all of the cases care about the expression, but they all expect the same class or value, then there would be two branches: one empty, and one with N rules. Thus, its average is N/2: better than the case where none of the rules care, but it could be better still. If each rule expects a different value for the expression, then there will be N branches, each of length 1, resulting in an average of about 1 -- an optimal choice. Decision tree builders must therefore be able to compute an expression's selectivity, as we will see in the next section. ---------------------- Decision Tree Building ---------------------- The ``TreeBuilder`` class implements the basic algorithm for transforming rules into a decision tree:: >>> from peak.rules.indexing import TreeBuilder A decision tree is built by taking a set of cases (action definitions), and a set of indexes that cover all expressions tested by those cases, using the ``build()`` method: build(`cases`, `exprs`, `memo`) Builds a decision tree to distinguish `cases`, using `exprs`. The "best" expression (based on legality of use and selectivity) is chosen and used to build a dispach node, with subnodes recursively constructed by calls to ``build()`` with the remaining `cases` and `exprs`. Leaf nodes are constructed whenever either the cases or expressions are exhausted along a particular path. `memo` must be a dictionary. This method is memoized via `memo`, meaning that if it is called more than once with the same cases and indexes, it will return the same result each time. That is, the first invocation's return value is cached in `memo`, and returned by future calls using the same `memo`. This helps cut down on the total decision tree size by eliminating the redundancy that would otherwise occur when more than one path leads to the same remaining options. Because of this, however, the input `cases` and `indexes` must be hashable, because the ``TreeBuilder`` will be using them as dictionary keys. Our examples here will use tuples of cases and indexes (so as to maintain their order when we display them), but immutable sets could also be used, as could integer "bit sets" or strings or anything else that's hashable. The ``build()`` method doesn't care about what the cases or indexes "mean"; it just passes them off to other methods for handling. Subclassing TreeBuilder ======================= The ``TreeBuilder`` base class requires the following methods to be defined in a subclass, in order for the ``build()`` template method to work: build_node(`expr`, `cases`, `remaining_exprs`, `memo`) Build a decision node, using `expr` as the expression to dispatch on. `cases` are the actions to be distinguished, and `remaining_exprs` are the expressions that still need dispatch nodes. This method should call back to the ``build()`` method to obtain subnodes as needed, via e.g. ``self.build(subnode_cases, remaining_indexes, memo)``. This method should then return the switch node it has constructed. build_leaf(`cases`, `memo`) Build a leaf node for `cases`. Usually this means something like picking the most specific case, or producing a method combination for the cases. The return value should be the leaf node it has constructed. For improved efficiency, most ``TreeBuilder`` subclasses may wish to cache these leaf nodes by their value in `memo`, to allow equivalent leaves to be shared even if they were produced by different sets of `cases`. Such caching should be done by this method, if applicable. selectivity(`expr`, `cases`) Estimate the selectivity of a decision tree node that subdivides `cases` using `expr`. The return value must be a tuple of the form (`branches`, `total`), where `branches` is the number of branches that the node would have, and `total` is the total number of rules applying on each branch. (In other words, the average number of rules on each branch is ``total/branches``.) If `expr` is not used by any of the `cases`, the returned ``total`` *must* be equal to ``branches * len(cases)``. If `expr` *is* used, however, the return statistics can be estimated rather than precisely computed, if it improves performance. (Selectivity estimation is done a *lot* during tree building, since each node must choose the "best" expression from all the currently-applicable expressions.) cost(`expr`, `remaining_exprs`) Estimate the cost of computing `expr`, given that `remaining_exprs` have not been computed yet. Lower costs are better than higher ones. The default implementation of this method just returns 1. Expression cost is only used as a tiebreaker when the selectivity of two candidate expressions is the same, however. For our examples, we'll define some of these methods to build interior nodes as dictionaries, and leaf nodes as lists. We'll also print out what we're doing, to show that redundant nodes are cached. And, we'll compute selectivity in a slow but easy way: by building a branch table for the expressions. But first, we'll need an expression class. For simplicity's sake, we'll use a string subclass that uses sequences of name-value pairs as rules, and creates branches for each value whose name equals the expression string:: >>> class DemoExpr(str): ... def branch_table(self, cases): ... branches = {None: []} # "none of the above" branch ... for case in cases: ... care = False ... for name, value in case: ... if name==self: ... branches.setdefault(value, []).append(case) ... care = True ... if not care: ... # "don't care" rules must be added to *every* branch ... for b in branches: ... branches[b].append(case) ... return branches >>> def r(**kw): ... return tuple(kw.items()) >>> x = DemoExpr('x') >>> x.branch_table([r(x=1), r(x=2)]) {None: [], 1: [(('x', 1),)], 2: [(('x', 2),)]} Notice, by the way, that branch tables produced by this expression type contain a ``None`` key, to handle the case where the expression value doesn't match any of the rules. It isn't necessary that this key actually be ``None``, and for many types of expression in PEAK-Rules, it *can't* be ``None``. But the general idea of a "none-of-the-above" branch in tree nodes is nonetheless important. (Note also that expression objects aren't required to have a ``branch_table()`` method; that's just an implementation detail of the demos in this document. Computing Selectivity and Building Nodes ======================================== Now that we have our expression type and the ability to build simple branch tables, we can define our tree builder, which assumes that each "case" is a tuple of name-value pairs, and that each "expr" is a ``DemoExpr`` instance:: >>> class DemoBuilder(TreeBuilder): ... ... def build_node(self, expr, cases, remaining_exprs, memo): ... enames = list(remaining_exprs) ... enames.sort() ... enames = ", ".join(enames) ... ... print "building switch for", expr, ... print "with", map(list,cases), "and (", enames, ")" ... ... branches = expr.branch_table(cases) ... return dict( ... [(key, self.build(tuple(values), remaining_exprs, memo)) ... for key,values in branches.items()] ... ) ... ... def build_leaf(self, cases, memo): ... print "building leaf node for", map(list,cases) ... return map(list,cases) ... ... def selectivity(engine, expr, cases): ... branches = expr.branch_table(cases) ... total = 0 ... for value, rules in branches.items(): ... total += len(rules) ... return len(branches), total Note, by the way, that this demo builder is *very* inefficient. A real builder would have other methods to allow cases to be added to it in advance for indexing purposes, and the selectivity and branch table calculations would be done by extracting a subset of precomputed index information. However, for this demo index, clarity and simplicity are more important than performance. In later sections, we'll look at more efficient ways to compute selectivity and build dispatch tables. Here's a quick example to show how selectivity should be calculated for a few simple cases:: >>> db = DemoBuilder() >>> db.selectivity(x, [r(x=1), r(x=2)]) # 3 branches: 1, 2, None (3, 2) >>> db.selectivity(x, [r(x=1), r(x=1)]) # 2 branches: 1, None (2, 2) >>> db.selectivity(x, []) # 1 branch: "None of the above" (1, 0) >>> db.selectivity(x, [r(y=42)]) # 1 branch: "None of the above" (1, 1) >>> db.selectivity(x, [r(x=1), r(y=1)]) # 2 branches: 1, None (2, 3) >>> db.selectivity(x, [r(y=2), r(z=1)]) # 1 branch: "None of the above" (1, 2) Basic Tree-Building =================== Building nothing produces an empty leaf node:: >>> DemoBuilder().build((), (), {}) building leaf node for [] [] In fact, building anything with no remaining indexes produces a leaf node:: >>> DemoBuilder().build((r(x=1),), (), {}) building leaf node for [[('x', 1)]] [[('x', 1)]] Any inapplicable indexes are ignored:: >>> DemoBuilder().build((r(x=1),), (DemoExpr('q'),), {}) building leaf node for [[('x', 1)]] [[('x', 1)]] But applicable indexes are used:: >>> DemoBuilder().build((r(x=1),), (DemoExpr('x'),), {}) building switch for x with [[('x', 1)]] and ( ) building leaf node for [] building leaf node for [[('x', 1)]] {None: [], 1: [[('x', 1)]]} >>> DemoBuilder().build((r(x=1),), (DemoExpr('x'), DemoExpr('q')), {}) building switch for x with [[('x', 1)]] and ( ) building leaf node for [] building leaf node for [[('x', 1)]] {None: [], 1: [[('x', 1)]]} >>> DemoBuilder().build((r(x=1),), (DemoExpr('q'), DemoExpr('x')), {}) building switch for x with [[('x', 1)]] and ( ) building leaf node for [] building leaf node for [[('x', 1)]] {None: [], 1: [[('x', 1)]]} As long as they have no constraints preventing them from being used:: >>> def f(): pass >>> x = DemoExpr('x') >>> y = DemoExpr('y') >>> db = DemoBuilder() >>> Ordering(db, x).requires([y]) >>> db.build((r(x=1, y=2),), (x, y), {}) building switch for y with [[('y', 2), ('x', 1)]] and ( x ) building leaf node for [] building switch for x with [[('y', 2), ('x', 1)]] and ( ) building leaf node for [[('y', 2), ('x', 1)]] {None: [], 2: {None: [], 1: [[('y', 2), ('x', 1)]]}} >>> db.build((r(x=1, y=2),), (y, x), {}) building switch for y with [[('y', 2), ('x', 1)]] and ( x ) building leaf node for [] building switch for x with [[('y', 2), ('x', 1)]] and ( ) building leaf node for [[('y', 2), ('x', 1)]] {None: [], 2: {None: [], 1: [[('y', 2), ('x', 1)]]}} Optimizations ============= If more than one index is applicable, the one with the best selectivity is chosen:: >>> z = DemoExpr('z') >>> rules = r(x=1,y=2,z=3), r(z=4) >>> db.build(rules, (x,y,z), {}) # doctest: +NORMALIZE_WHITESPACE building switch for z with [[('y', 2), ('x', 1), ('z', 3)], [('z', 4)]] and ( x, y ) building leaf node for [] building switch for y with [[('y', 2), ('x', 1), ('z', 3)]] and ( x ) building switch for x with [[('y', 2), ('x', 1), ('z', 3)]] and ( ) building leaf node for [[('y', 2), ('x', 1), ('z', 3)]] building leaf node for [[('z', 4)]] {None: [], 3: {None: [], 2: {None: [], 1: [[('y', 2), ('x', 1), ('z', 3)]]}}, 4: [[('z', 4)]]} >>> db.build(rules, (z,y,x), {}) # doctest: +NORMALIZE_WHITESPACE building switch for z with [[('y', 2), ('x', 1), ('z', 3)], [('z', 4)]] and ( x, y ) building leaf node for [] building switch for y with [[('y', 2), ('x', 1), ('z', 3)]] and ( x ) building switch for x with [[('y', 2), ('x', 1), ('z', 3)]] and ( ) building leaf node for [[('y', 2), ('x', 1), ('z', 3)]] building leaf node for [[('z', 4)]] {None: [], 3: {None: [], 2: {None: [], 1: [[('y', 2), ('x', 1), ('z', 3)]]}}, 4: [[('z', 4)]]} If an index is skipped due to a constraint, its selectivity should still be checked if its constraints go away (due to the blocking index being found inapplicable):: >>> Ordering(db, z).requires([y]) # z now must have y checked first >>> rules = r(x=1,z=3), r(z=4) # but y isn't used by the rules >>> db.build(rules, (x,y,z), {}) # so z is the most-selective index building switch for z with [[('x', 1), ('z', 3)], [('z', 4)]] and ( x ) building leaf node for [] building switch for x with [[('x', 1), ('z', 3)]] and ( ) building leaf node for [[('x', 1), ('z', 3)]] building leaf node for [[('z', 4)]] {None: [], 3: {None: [], 1: [[('x', 1), ('z', 3)]]}, 4: [[('z', 4)]]} >>> db.build(rules, (z,y,x), {}) # try them in another order building switch for z with [[('x', 1), ('z', 3)], [('z', 4)]] and ( x ) building leaf node for [] building switch for x with [[('x', 1), ('z', 3)]] and ( ) building leaf node for [[('x', 1), ('z', 3)]] building leaf node for [[('z', 4)]] {None: [], 3: {None: [], 1: [[('x', 1), ('z', 3)]]}, 4: [[('z', 4)]]} The above examples whose results contain more than one ``[]`` leaf node show that leaf nodes for the same cases are being cached, but let's also show that non-leaf nodes are similarly shared and cached:: >>> rules = (('x',1),('x',2),('y',1),('y',2)), >>> tree = db.build(rules, (x,y,), {}) building switch for y with [[('x', 1), ('x', 2), ('y', 1), ('y', 2)]] and ( x ) building leaf node for [] building switch for x with [[('x', 1), ('x', 2), ('y', 1), ('y', 2)]] and ( ) building leaf node for [[('x', 1), ('x', 2), ('y', 1), ('y', 2)]] >>> tree # doctest: +NORMALIZE_WHITESPACE {None: [], 1: {None: [], 1: [[('x', 1), ('x', 2), ('y', 1), ('y', 2)]], 2: [[('x', 1), ('x', 2), ('y', 1), ('y', 2)]]}, 2: {None: [], 1: [[('x', 1), ('x', 2), ('y', 1), ('y', 2)]], 2: [[('x', 1), ('x', 2), ('y', 1), ('y', 2)]]}} >>> tree[1] is tree[2] True >>> tree[1][1] is tree[1][2] True >>> tree[None] is tree[1][None] True As you can see, the redundant leaf nodes and intermediate nodes are shared due to the caching, and the log shows that only two intermediate nodes and two leaf nodes were even created in the first place. ------------------ Bitmap/Set Indexes ------------------ The basic indexes used by PEAK-Rules use a combination of bitmaps and sets to represent criteria as ranges or regions in a (1-dimensional) logical space. Points that represent region edges are known as "seeds". In the simplest possible indexes, a bitmap of applicable rules (cases, actually) is kept for each seed. (For equality or identity testing, this is all that's required, but more complex criteria things get a bit more involved.) For simple generic functions with 31 or fewer cases, a single integer is sufficient to represent any set of cases. For more complex generic functions, Python's long integer arithmetic performance scales reasonably well, even up to many hundreds of bits (cases). Plus, both integers and longs can be used as dictionary keys, and thus work well with the ``TreeBuilder`` class (which needs to cache dispatch nodes for sets of applicable cases). Bitmap Operations ================= To work with bitsets, we need to be able to convert an integer sequence to a bitmap (integer or long integer), and vice versa:: >>> from peak.rules.indexing import to_bits, from_bits >>> odds = to_bits([9,11,13,1,3,5,7,15]) >>> print hex(odds) 0xaaaa >>> list(from_bits(odds)) [1, 3, 5, 7, 9, 11, 13, 15] And to handle sets with more than 31 bits, we need these operations to handle long integers:: >>> seven_long = to_bits([32,33,34]) >>> print hex(long(seven_long)) 0x700000000L >>> list(from_bits(seven_long)) [32, 33, 34] The ``BitmapIndex`` Add-on ========================== The ``BitmapIndex`` add-on base class provides basic support for indexing cases identified by sequential integers. Indexes are keyed by expression and attach to an "engine", which can be any object that supports add-ons. The ``BitmapIndex`` add-on provides these methods and attributes: add_case(case_id, criterion) Given an integer `case_id`, update the index by calling the ``.add_criterion()`` method on `criterion` and caching the result (so that multiple cases using the same criterion share the same seeds). add_criterion(criterion) (**abstract method: must be defined in a subclass**) The ``.add_criterion()`` method must return a set or sequence of the "applicable seeds" for which the criterion holds true. It must also ensure that the ``.all_seeds`` index is up to date, usually by calling the ``.include()`` and ``.exclude()`` or ``.add_seed()`` methods. The set or sequence returned by this method is only used for its ``len()`` as a basis for computing selectivity; its contents aren't actually used by the ``BitmapIndex`` base class. Thus, this method can return a specialized dynamic object that simply computes an appropriate length, and optionally updates the ``all_seeds`` sets when it notice new seeds there (e.g. due to ``reseed()`` or the addition of new cases and criteria). include(seed, criterion) Add `criterion` to the "inclusions" for `seed`. You should call this method in ``.add_criterion()`` for each seed that the criterion applies to. Note that there is no requirement that the `criterion` used here must be limited to criteria that were passed to ``.add_criterion()`` -- that method is allowed to pre-calculate inclusions for related criteria that haven't been seen yet. For example, ``TypeIndex`` precalculates many inclusions and exclusions for the base classes of criteria it encounters. exclude(seed, criterion) Add `criterion` to the "exclusions" for `seed`. Like ``.include()``, this is usually called from within ``.add_criterion()``, and may be called on any criterion, whether or not it was passed to ``.add_criterion()``. Simple indexes will probably have no use for this method, as "exclusions" are typically only useful for negated criteria. For example, an ``is not`` condition is false for all seeds but one, so it's not efficient to try to update the inclusions for every seed to list every ``is not`` criterion. Instead, it's better to record an exclusion for the ``is not`` criterion's seed, and an inclusion for the criterion to a "default" seed, so that by default, the criterion will apply. selectivity(case_id_list) Given a **sorted** sequence of integer case ids, return the `selectivity statistics`_ of the index for those cases. The default implementation simply sums the ``len()`` of the values returned by the appropriate ``.add_criterion()`` calls. It can be overridden in a subclass to implement more sophisticated calculation strategies. seed_bits(cases) Given a bitmap of cases, return a tuple ``(dontcares, seedmap)``, where ``dontcares`` is a bitset of "don't care" cases (i.e., cases that must be included in *every* child node), and ``seedmap`` is a dictionary mapping seeds to ``(include, exclude)`` bitset pairs. reseed(criterion) Handle a reseed request. By default, this is a synonym for ``.add_criterion(criterion)``, but if necessary it can be overridden in a subclass to handle reseeds differently. expanded_sets() Return a list of ``(seed, (inc, exc)`` tuples, where ``inc`` and ``exc`` are integer case lists. This method is for debugging and testing only. all_seeds A dictionary containing information about all seeds seen by the index. The keys are the seeds, and the values are ``(include,exclude)`` tuples of sets of criteria, indicating which criteria include or exclude that key, respectively. Dynamic criteria should update this dictionary when new seeds are discovered (e.g. via ``reseed()`` or new cases being added). criteria_bits A dictionary mapping each known criterion to a bitset representing the cases that use that criterion. criteria_seeds A dictionary that caches the result of the index's calls to the ``.add_criterion()`` method. case_seeds A list mapping case ids to the values returned by ``.add_criterion()`` for the corresponding criterion. Entries for case ids that were not assigned criteria via ``.add_case()`` are filled with ``self.null``. null The value used to pad skipped entries in the ``.case_seeds`` list. By default, this is the same object as ``self.all_seeds``, so that for selectivity-calculation purposes, the case is treated as applying for all seeds. (You may change this in a subclass if you are also overriding the ``selectivity()`` method.) known_cases A bitset representing the case ids of all cases added to the index using the ``add_case()`` method. extra An empty dictionary, made available for the use of ``.add_criterion()`` algorithms that may require additional storage for dependencies or intermediate indexes. match A single-element sequence that can be used as a default return value from ``.add_criterion()``. If your ``.add_criterion()`` method is going to return a set or sequence containing only one element (and it won't be changed later), you should return ``self.match`` instead of making a new sequence. This can save a lot of memory. For our first demo, we'll assume we're indexing a simple equality condition, so every criterion will seed only to itself. We'll create a simple criterion type, and a suitable ``BitmapIndex`` subclass:: >>> from peak.rules.indexing import BitmapIndex >>> from peak.util.decorators import struct >>> from peak.rules import when >>> class DemoEngine: pass >>> def find(val): ... """A structure type used as a criterion""" ... return val, >>> find = struct()(find) >>> class DemoIndex(BitmapIndex): ... def add_criterion(self, criterion): ... print "computing seeds for", criterion ... self.include(criterion.val, criterion) ... return [criterion.val] By the way, the ``BitmapIndex`` constructor is an abstract factory: it can automatically create a subclass of the appropriate type, for the given engine and expression:: >>> eng = DemoEngine() >>> ind = BitmapIndex(eng, "some expression") Traceback (most recent call last): ... NoApplicableMethods: ((<...DemoEngine ...>, 'some expression'), {}) Well, it will as long as you register an appropriate method for the ``bitmap_index_type`` generic function:: >>> from peak.rules.indexing import bitmap_index_type >>> f = when(bitmap_index_type, (DemoEngine, str))( ... lambda engine, expr: DemoIndex ... ) Now we should be able to get the right kind of index, just by calling ``BitmapIndex()``:: >>> BitmapIndex(eng, "some expression") We also could have explicitly used ``DemoIndex``, of course. Once created, the same instance will be reused for each call to either the specific constructor or ``BitmapIndex``. To begin with, our index's selectivity is 0/0 because there are no seeds (and therefore no branches):: >>> ind = DemoIndex(eng, "some expression") >>> ind.selectivity([]) (0, 0) >>> ind.all_seeds {} >>> ind.criteria_seeds {} >>> list(from_bits(ind.known_cases)) [] By adding a case, we'll add a criterion (and therefore a seed), which gets cached:: >>> ind.add_case(0, find("x")) computing seeds for find('x',) >>> ind.criteria_seeds {find('x',): ['x']} >>> ind.criteria_bits {find('x',): 1} Now, selectivity will always be at least 1/0, because there's one possible branch:: >>> ind.selectivity([]) (1, 0) >>> ind.selectivity([1]) (1, 1) >>> ind.selectivity([2]) (1, 1) >>> ind.selectivity([1,2]) (1, 2) And the seed bitmaps reflect this:: >>> list(from_bits(ind.known_cases)) [0] >>> ind.seed_bits(ind.known_cases) (0, {'x': (1, 0)}) >>> dict(ind.expanded_sets()) # expanded form of seed_bits(known_cases) {'x': [[0], []]} If we add another case with the same criterion, the number of branches will stay the same. Notice also, that the seeds for a previously-seen criterion are not recalculated:: >>> ind.add_case(1, find("x")) >>> ind.criteria_bits # criterion 'x' was used for cases 0 and 1 {find('x',): 3} >>> dict(ind.expanded_sets()) {'x': [[0, 1], []]} >>> list(from_bits(ind.known_cases)) [0, 1] >>> ind.selectivity([]) (1, 0) >>> ind.selectivity([1]) (1, 1) >>> ind.selectivity([2]) (1, 1) >>> ind.selectivity([1,2]) (1, 2) However, if we add a new case with a *new* criterion, its seeds are computed, and the number of branches increases:: >>> ind.add_case(2, find("y")) computing seeds for find('y',) >>> dict(ind.expanded_sets()) {'y': [[2], []], 'x': [[0, 1], []]} >>> list(from_bits(ind.known_cases)) [0, 1, 2] >>> ind.selectivity([]) (2, 0) >>> ind.selectivity([1]) (2, 1) >>> ind.selectivity([2]) (2, 1) >>> ind.selectivity([1,2]) (2, 2) ----------------- Indexing Criteria ----------------- All of the criterion objects provided by ``peak.rules.criteria`` have ``BitmapIndex`` subclasses suitable for indexing them:: >>> from peak.rules.criteria import Value, Range, IsObject, Class, Classes To demonstrate them, we'll use a dummy engine object:: >>> class Engine: pass >>> eng = Engine() Object Identity =============== The ``IsObject`` criterion type implements indexing for the ``is`` and ``is not`` operators. ``IsObject(x)`` represents ``is x``, and ``IsObject(x, False)`` represents ``is not x``. The bitmap index seeds for ``IsObject`` objects are the ``id()`` values of the target objects, or ``None`` to represent the "none of the above" cases:: >>> from peak.rules.indexing import PointerIndex >>> p = object() >>> ppeq = IsObject(p) >>> ppne = IsObject(p, False) >>> ind = PointerIndex(eng, "x") >>> ind.add_case(0, ppeq) >>> dict(ind.expanded_sets()) {...: [[0], []], None: [[], [0]]} The selectivity of an ``is`` criterion is 1:: >>> ind.selectivity([0]) (2, 1) And for an ``is not`` criterion, it's always one less than the total number of seeds currently in the index (because an ``is not`` criterion is true for every possible branch *except* its target):: >>> ind.add_case(1, ppne) >>> dict(ind.expanded_sets()) {...: [[0], [1]], None: [[1], [0]]} >>> ind.selectivity([1]) (2, 1) >>> ind.selectivity([0,1]) (2, 2) >>> ind.add_case(2, IsObject(object())) >>> ind.selectivity([1]) # now it's (3,2) instead of (2,1) or (3,1) (3, 2) >>> ind.selectivity([0]) # 'is' pointers are always 1 (3, 1) Ranges and Value Comparisons ============================ ``Range`` Objects ----------------- The ``Range()`` criterion type represents an inequality such as ``lo < x < hi`` or ``x >= lo``. (For more details on their semantics, see Criteria.txt). The bitmap index seeds for ``Range`` objects are edge tuples, and the selectivity of a ``Range`` is the distance between the low and high edges in a sorted list of all the index's seeds:: >>> from peak.rules.indexing import RangeIndex >>> ind = RangeIndex(eng, "y") >>> r = Range((1,-1), (23,1)) >>> ind.add_case(0, r) >>> ind.selectivity([0]) (2, 1) >>> from peak.rules.criteria import sorted >>> sorted(ind.expanded_sets()) [((1, -1), [[0], []]), ((23, 1), [[], [0]])] >>> ind.add_case(1, Range((5,-1), (20,1))) >>> ind.selectivity([1]) (4, 1) >>> sorted(ind.expanded_sets()) [((1, -1), [[0], []]), ((5, -1), [[1], []]), ((20, 1), [[], [1]]), ((23, 1), [[], [0]])] >>> ind.add_case(2, Range((7,-1), (24,1))) >>> ind.selectivity([2]) (6, 3) >>> sorted(ind.expanded_sets()) [((1, -1), [[0], []]), ((5, -1), [[1], []]), ((7, -1), [[2], []]), ((20, 1), [[], [1]]), ((23, 1), [[], [0]]), ((24, 1), [[], [2]])] >>> ind.add_case(3, Range((7,-1), (7,1))) >>> sorted(ind.expanded_sets()) [((1, -1), [[0], []]), ((5, -1), [[1], []]), ((7, -1), [[2, 3], []]), ((7, 1), [[], [3]]), ((20, 1), [[], [1]]), ((23, 1), [[], [0]]), ((24, 1), [[], [2]])] >>> ind.selectivity([0]) (7, 5) >>> ind.selectivity([1]) (7, 3) >>> ind.selectivity([2]) (7, 4) >>> ind.selectivity([3]) (7, 1) ``Value`` Objects ----------------- ``Value`` objects are used to represent ``==`` and ``!=`` comparisons. ``Value(x)`` represents ``==x`` and ``Value(x, False)`` represents ``!=x``. The bitmap index seeds for ``Value`` objects are ``(value, 0)`` tuples, which fall between the "below" and "above" tuples of any ``Range`` objects in the same index. And the selectivity of a ``Value`` is either 1 or the number of seeds in the index, minus one:: >>> ind.add_case(4, Value(7, False)) >>> ind.selectivity([4]) (9, 8) >>> sorted(ind.expanded_sets()) [((Min, -1), [[4], []]), ((1, -1), [[0], []]), ((5, -1), [[1], []]), ((7, -1), [[2, 3], []]), ((7, 0), [[], [4]]), ((7, 1), [[], [3]]), ((20, 1), [[], [1]]), ((23, 1), [[], [0]]), ((24, 1), [[], [2]])] >>> ind.add_case(5, Value(7)) >>> ind.selectivity([5]) (9, 1) >>> sorted(ind.expanded_sets()) [((Min, -1), [[4], [5]]), ((1, -1), [[0], []]), ((5, -1), [[1], []]), ((7, -1), [[2, 3], []]), ((7, 0), [[5], [4]]), ((7, 1), [[], [3]]), ((20, 1), [[], [1]]), ((23, 1), [[], [0]]), ((24, 1), [[], [2]])] Notice that the seeds for a ``Value`` always include either an inclusion or exclusion for ``(Min, -1)``, as this Value Map Generation -------------------- >>> from peak.rules.indexing import split_ranges >>> from peak.util.extremes import Min, Max >>> def dump_ranges(ind, cases): ... exact, ranges = split_ranges(*ind.seed_bits(cases)) ... for k in exact.keys(): ... exact[k] = list(from_bits(exact[k])) ... for n, (k, v) in enumerate(ranges): ... ranges[n] = k, list(from_bits(v)) ... return exact, ranges >>> dump_ranges(ind, ind.known_cases) ({1: [0, 4], 5: [0, 1, 4], 7: [0, 1, 2, 3, 5], 20: [0, 1, 2, 4], 23: [0, 2, 4], 24: [2, 4]}, [((Min, 1), [4]), ((1, 5), [0, 4]), ((5, 7), [0, 1, 4]), ((7, 20), [0, 1, 2, 4]), ((20, 23), [0, 2, 4]), ((23, 24), [2, 4]), ((24, Max), [4])]) >>> ind = RangeIndex(eng, 'q') >>> dump_ranges(ind, ind.known_cases) ({}, [((Min, Max), [])]) >>> ind.add_case(0, Value(19)) >>> result = dump_ranges(ind, ind.known_cases) >>> result == ({Min: [], 19: [0]}, [((Min, Max), [])]) True >>> ind.add_case(1, Value(23)) >>> result = dump_ranges(ind, ind.known_cases) >>> result == ({Min: [], 19: [0], 23: [1]}, [((Min, Max), [])]) True >>> ind.add_case(2, Value(23, False)) >>> dump_ranges(ind, ind.known_cases) ({19: [0, 2], 23: [1]}, [((Min, Max), [2])]) >>> ind.add_case(3, Range(lo=(57,1))) >>> dump_ranges(ind, ind.known_cases) ({57: [2], 19: [0, 2], 23: [1]}, [((Min, 57), [2]), ((57, Max), [2, 3])]) >>> ind.add_case(4, Range(lo=(57,-1))) >>> dump_ranges(ind, ind.known_cases) ({57: [2, 4], 19: [0, 2], 23: [1]}, [((Min, 57), [2]), ((57, Max), [2, 3, 4])]) Single Classes ============== ``Class`` objects represent ``issubclass()`` or ``isinstance()`` tests. ``Class(x)`` is a instance/subclass match, while ``Class(x, False)`` is a non-match:: >>> from peak.rules.indexing import TypeIndex >>> ind = TypeIndex(eng, 'by class') >>> ind.add_case(0, Class(int)) >>> ind.selectivity([0]) (2, 1) >>> dict(ind.expanded_sets()) {: [[0], []], : [[], []]} >>> class myint(int): pass >>> ind.add_case(1, Class(myint)) >>> ind.selectivity([1]) (3, 1) >>> dict(ind.expanded_sets()) {: [[0], []], : [[], []], : [[0, 1], []]} >>> ind.selectivity([0]) (3, 2) >>> ind.add_case(2, Class(int, False)) >>> ind.selectivity([2]) (3, 1) >>> dict(ind.expanded_sets()) {: [[0], [2]], : [[2], []], : [[0, 1], [2]]} >>> class other(object): pass >>> ind.add_case(3, Class(other)) >>> ind.selectivity([3]) (4, 1) >>> ind.selectivity([2]) (4, 2) >>> dict(ind.expanded_sets()) == { ... int: [[0], [2]], object: [[2], []], other: [[3], []], ... myint: [[0, 1], [2]] ... } True # the default cases should include all of the "not isinstance" criteria >>> list(from_bits(ind.seed_bits(to_bits(range(4)))[0])) [2] Multiple Classes ================ ``Classes`` objects hold sets of 2 or more ``Class`` criteria, and represent the "and" of those criteria. This is the most complex type of criteria to index, because there's no easy way to incrementally update a set intersection:: >>> class a(object): pass >>> class b(object): pass >>> class c(a,b): pass >>> class d(b): pass >>> class e(a,d): pass >>> class f(e, c): pass >>> class g(c): pass >>> ind = TypeIndex(eng, 'classes') >>> ind.add_case(0, Classes([Class(a), Class(b)])) >>> ind.selectivity([0]) (3, 0) >>> dict(ind.expanded_sets()) == { ... a: [[], []], b: [[], []], object: [[], []] ... } True >>> ind.add_case(1, Class(c)) >>> ind.selectivity([0]) # c (4, 1) >>> ind.selectivity([1]) (4, 1) >>> dict(ind.expanded_sets()) == { ... a: [[], []], b: [[], []], c: [[0, 1], []], object: [[], []] ... } True >>> ind.add_case(2, Classes([Class(a), Class(b), Class(c, False)])) >>> ind.selectivity([2]) (4, 0) >>> dict(ind.expanded_sets()) == { ... a: [[], []], b: [[], []], c: [[0, 1], []], object: [[], []] ... } True >>> ind.add_case(3, Class(e)) >>> ind.selectivity([0]) # c, e (6, 2) >>> ind.selectivity([2]) (6, 1) >>> ind.selectivity([3]) (6, 1) >>> dict(ind.expanded_sets()) == { ... a: [[], []], b: [[], []], c: [[0, 1], []], object: [[], []], ... d: [[], []], e: [[0, 2, 3], []] ... } True >>> ind.add_case(4, Class(f)) >>> ind.selectivity([0]) # c, e, f (7, 3) >>> ind.selectivity([2]) (7, 1) >>> dict(ind.expanded_sets()) == { ... a: [[], []], b: [[], []], c: [[0, 1], []], object: [[], []], ... d: [[], []], e: [[0, 2, 3], []], f: [[0, 1, 3, 4], []] ... } True >>> ind.add_case(5, Class(g)) >>> ind.selectivity([0]) # c, e, f, g (8, 4) >>> ind.selectivity([2]) # still just 'e' (8, 1) >>> Classes([Class(d, False), Class(e, False)]) Class(, False) >>> ind.add_case(6, Classes([Class(d, False), Class(e, False)])) >>> ind.selectivity([6]) # all but d, e, f (8, 5) >>> dict(ind.expanded_sets()) == { ... a: [[], []], b: [[], []], c: [[0, 1], []], object: [[6], []], ... d: [[], [6]], e: [[0, 2, 3], [6]], f: [[0, 1, 3, 4], [6]], g: [[0, 1, 5], []] ... } True # the default cases should include all of the "not isinstance" criteria >>> list(from_bits(ind.seed_bits(to_bits(range(7)))[0])) [6] Reseeding ========= Due to the nature of multiple inheritance, it's sometimes necessary to re-seed an index by adding a new criterion, recomputing selectivity, and then getting new seed bits. Let's test an example by making a new class that inherits from ``a`` and ``b``:: >>> class x(a,b): pass This class isn't in the index, because we just created it. If it were only inheriting from one class, we could safely assume that a lookup of the base class would work just as well as looking up the actual class. However, since it inherits from more than one class, we don't know if there are multi-class criteria that might apply to it. (And in fact there are: cases 0 and 2 in our index apply to classes that inherit from both ``a`` and ``b``.) So, to update the index, we use the ``reseed()`` method:: >>> ind.reseed(Class(x)) It takes a criterion and an optional bitset representing the cases for which a new ``seed_bits`` map should be generated. It updates the index by checking the ``len()`` of every "applicable seeds" set, after adding the criterion to the appropriate caches. The result is that the index now includes correct information for the new ``x`` class:: >>> dict(ind.expanded_sets()) == { ... a: [[], []], b: [[], []], c: [[0, 1], []], object: [[6], []], ... d: [[], [6]], e: [[0, 2, 3], [6]], f: [[0, 1, 3, 4], [6]], g: [[0, 1, 5], []], ... x: [[0, 2], []] ... } True Exact Types =========== Finally, let's try out some ``istype()`` and mixed class/classes/istype criteria, to make sure they interoperate:: >>> from peak.rules import istype >>> ind = TypeIndex(eng, 'types') >>> ind.add_case(0, istype(a)) >>> ind.selectivity([0]) (2, 1) >>> ind.add_case(1, istype(b, False)) >>> ind.selectivity([1]) (3, 2) >>> ind.selectivity([0,1]) (3, 3) >>> ind.add_case(2, Class(a)) >>> ind.selectivity([2]) (3, 1) >>> ind.selectivity([0,1,2]) (3, 4) >>> dict(ind.expanded_sets()) == { ... a:[[0, 2], []], ... b:[[], [1]], ... object:[[1], []] ... } True >>> ind.add_case(3, Class(a, False)) >>> ind.selectivity([3]) (3, 2) >>> ind.selectivity([0,1,2,3]) (3, 6) >>> dict(ind.expanded_sets()) == { ... a:[[0, 2], [3]], ... b:[[], [1]], ... object:[[1, 3], []] ... } True >>> ind.add_case(4, Classes([Class(a), istype(c, False)])) >>> ind.selectivity([4]) (4, 1) >>> dict(ind.expanded_sets()) == { ... a:[[0, 2, 4], [3]], ... b:[[], [1]], ... c:[[2], [3]], ... object:[[1, 3], []] ... } True >>> ind.reseed(Class(e)) >>> dict(ind.expanded_sets()) == { ... a:[[0, 2, 4], [3]], ... b:[[], [1]], ... c:[[2], [3]], ... d:[[], []], ... e:[[2, 4], [3]], ... object:[[1, 3], []] ... } True >>> ind.add_case(5, istype(object)) # the default cases should include all of the "not isinst/type" criteria >>> list(from_bits(ind.seed_bits(to_bits(range(6)))[0])) [1, 3] Truth ===== ``TruthIndex`` treats boolean criteria as logical truth:: >>> from peak.rules.indexing import TruthIndex >>> ind = TruthIndex(eng, "z") >>> ind.add_case(0, Value(True)) >>> ind.selectivity([0]) (2, 1) >>> ind.add_case(1, Value(True, False)) >>> ind.selectivity([0,1]) (2, 2) >>> dict(ind.expanded_sets()) {False: [[1], []], True: [[0], []]}