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

E1 and E2 and E3 and E4
E5 and E3 and E2 and E6

>>> 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"])

>>> from peak.rules.indexing import define_ordering
>>> define_ordering(f, ["E5","E3","E2","E6"])   # E5 and E3 and E2 and E6

>>> 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

(E1 or E5) -> (E2 or E3) -> (E4 or E6)

E5, E3, E2
E1, E2
E5, E1, E2
E1, E5, E2

>>> from peak.rules.indexing import set, frozenset  # 2.3 compatibility

>>> E2.constraints == set([frozenset(["E1"]), frozenset(["E5", "E3"])])
True

>>> E2.requires(["E5", "E3", "E4"])
>>> E2.constraints == set([frozenset(["E1"]), frozenset(["E5", "E3"])])
True

>>> E2.requires(["E5"])
>>> E2.constraints == set([frozenset(["E1"]), frozenset(["E5"])])
True

>>> 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.

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),)]
... }
True

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).items()
...         branches.sort()
...         return dict(
...             [(key, self.build(tuple(values), remaining_exprs, memo))
...                 for key,values in branches]
...         )
...
...     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'),), {}) == {
...     None: [], 1: [[('x', 1)]]
... }
building switch for x with [[('x', 1)]] and (  )
building leaf node for []
building leaf node for [[('x', 1)]]
True

>>> DemoBuilder().build((r(x=1),), (DemoExpr('x'), DemoExpr('q')), {}) == {
...     None: [], 1: [[('x', 1)]]
... }
building switch for x with [[('x', 1)]] and (  )
building leaf node for []
building leaf node for [[('x', 1)]]
True

>>> DemoBuilder().build((r(x=1),), (DemoExpr('q'), DemoExpr('x')), {}) == {
...     None: [], 1: [[('x', 1)]]
... }
building switch for x with [[('x', 1)]] and (  )
building leaf node for []
building leaf node for [[('x', 1)]]
True

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), {}) == {
...     None: [], 2: {None: [], 1: [[('y', 2), ('x', 1)]]}
... }
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)]]
True

>>> db.build((r(x=1, y=2),), (y, x), {}) == {
...     None: [], 2: {None: [], 1: [[('y', 2), ('x', 1)]]}
... }
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)]]
True

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
...     None: [],
...         3: {None: [],
...                2: {None: [],
...                       1: [[('y', 2), ('x', 1), ('z', 3)]]}},
...         4: [[('z', 4)]]
... }
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)]]
True

>>> db.build(rules, (z,y,x), {}) == { # doctest: +NORMALIZE_WHITESPACE
...     None: [],
...        3: {None: [],
...               2: {None: [],
...                      1: [[('y', 2), ('x', 1), ('z', 3)]]}},
...        4: [[('z', 4)]]
... }
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)]]
True

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
...     None: [], 3: {None: [], 1: [[('x', 1), ('z', 3)]]}, 4: [[('z', 4)]]
... } 
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)]]
True

>>> db.build(rules, (z,y,x), {}) == {
...     None: [], 3: {None: [], 1: [[('x', 1), ('z', 3)]]}, 4: [[('z', 4)]]
... } # 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)]]
True

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 == {
...     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)]]}
... }
True

>>> 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 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(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")
<DemoIndex object at ...>

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)

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()) == {id(p): [[0], [1]], None: [[1], [0]]}
True

>>> ind.selectivity([1])
(2, 1)

>>> ind.selectivity([0,1])
(2, 2)

>>> q = object()
>>> ind.add_case(2, IsObject(q))

>>> 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)

>>> dict(ind.expanded_sets()) == {
...     None: [[1], [0, 2]], id(p): [[0], [1]], id(q): [[1, 2], []],
... }
True

>>> from peak.rules.core import intersect
>>> ind.add_case(3, intersect(ppne, IsObject(q,False)))

>>> dict(ind.expanded_sets()) == {
...     None: [[1, 3], [0, 2]], id(p): [[0], [1, 3]], id(q): [[1, 2], [3]],
... }
True

>>> r = object()
>>> ind.add_case(4, IsObject(r))

>>> dict(ind.expanded_sets()) == {
...     None: [[1, 3], [0, 2, 4]], id(p): [[0], [1, 3]],
...     id(q): [[1, 2], [3]], id(r): [[1, 3, 4], []]
... }
True

Ranges and Value Comparisons

>>> 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)

   >>> 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

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()) == {
...     int: [[0], []], object: [[], []]
... }
True

>>> class myint(int): pass
>>> ind.add_case(1, Class(myint))
>>> ind.selectivity([1])
(3, 1)
>>> dict(ind.expanded_sets()) == {
...     int: [[0], []], object: [[], []], myint: [[0, 1], []]
... }
True

>>> ind.selectivity([0])
(3, 2)

>>> ind.add_case(2, Class(int, False))
>>> ind.selectivity([2])
(3, 1)
>>> dict(ind.expanded_sets()) == {
...     int: [[0], []], object: [[2], []], myint: [[0, 1], []]
... }
True

>>> 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], []], object: [[2], []], other: [[2, 3], []],
...     myint: [[0, 1], []]
... }
True

Multiple Classes

Conjunction objects can 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, Conjunction([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, Conjunction([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
(5, 2)
>>> ind.selectivity([2])
(5, 1)
>>> ind.selectivity([3])
(5, 1)
>>> dict(ind.expanded_sets()) == {
...     a: [[], []], b: [[], []], c: [[0, 1], []], object: [[], []],
...     e: [[0, 2, 3], []]
... }
True


>>> ind.add_case(4, Class(f))
>>> ind.selectivity([0])    # c, e, f
(6, 3)
>>> ind.selectivity([2])
(6, 1)
>>> dict(ind.expanded_sets()) == {
...     a: [[], []], b: [[], []], c: [[0, 1], []], object: [[], []],
...     e: [[0, 2, 3], []], f: [[0, 1, 3, 4], []]
... }
True

>>> ind.add_case(5, Class(g))
>>> ind.selectivity([0])    # c, e, f, g
(7, 4)
>>> ind.selectivity([2])    # still just 'e'
(7, 1)

>>> Conjunction([Class(d, False), Class(e, False)])
Class(<class 'd'>, False)

>>> ind.add_case(6, Conjunction([Class(d, False), Class(e, False)]))
>>> ind.selectivity([6])    # all but d, e, f
(8, 5)
>>> dict(ind.expanded_sets()) == {
...     a: [[6], []], b: [[6], []], c: [[0, 1, 6], []], object: [[6], []],
...     d: [[], []], e: [[0, 2, 3], []], f: [[0, 1, 3, 4], []],
...     g: [[0, 1, 5, 6], []],
... }
True

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: [[6], []], b: [[6], []], c: [[0, 1, 6], []], object: [[6], []],
...     d: [[], []], e: [[0, 2, 3], []], f: [[0, 1, 3, 4], []],
...     g: [[0, 1, 5, 6], []], x: [[0, 2, 6], []]
... }
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, 1, 2], []],
...     b:[[], []],
...     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, 1, 2], []],
...     b:[[3], []],
...     object:[[1, 3], []]
... }
True

>>> ind.add_case(4, Conjunction([Class(a), istype(c, False)]))
>>> ind.selectivity([4])
(4, 1)

>>> dict(ind.expanded_sets()) == {    
...     a:[[0, 1, 2, 4], []],
...     b:[[3], []],
...     c:[[1, 2], []],
...     object:[[1, 3], []]
... }
True

>>> ind.reseed(Class(e))

>>> dict(ind.expanded_sets()) == {    
...     a:[[0, 1, 2, 4], []],
...     b:[[3], []],
...     c:[[1, 2], []],
...     e:[[1, 2, 4], []],
...     object:[[1, 3], []]
... }
True

>>> ind.add_case(5, istype(object))

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], []]}