Log of /PEAK-Rules/peak/rules/indexing.py

Parent Directory

No default branch
Bookmark a link to HEAD: (view) (download) (as text)

Fix 3.x frozenset repr for tests

Python 3 compatibility: map and iteritems

Remove unnecessary import

Fix broken indexing for "is not" conditions (especially "and"-ed ones)

Simplified class indexing strategy so that ABCs and other 2.6+ classes 
using __subclasscheck__/__subclasshook__ should work correctly without
any special treatment.  (The tradeoff is worse worst-case performance
when not-yet-indexed classes are added to rules or seen during
dispatching.)

Fix for Python 2.6 DeprecationWarning

Refactor condition negation by adding negate() GF, dropping
truth mode from builders, and adding an OrElse sequential-or
operator.  This also changed how Truth tests are coded, to use
Value(True, T/F) objects in place of bools (to get rid of the
ambiguity that previously existed).  Value(x, False) objects
no longer have disjuncts, since that was another ambiguity.
These ambiguities meant that you couldn't cleanly take the
disjuncts() of a Test(), which meant you also couldn't negate
a test safely.  We also no longer force Signature() objects
to expand Test disjunctions, as this isn't necessary for
DNF handling.  (Because we're going to grab the disjuncts()
at rule-add time anyway -- eager expansion was an unnecessary
holdover from the way RuleDispatch did things.)  See also:

 http://www.eby-sarna.com/pipermail/peak/2008-July/003000.html

for more background on the reasoning behind these changes.

Fix "not isinstance" criteria, broken by last refactoring due to
inadequate test coverage.  :(

Add some tests of mixed istype/class indexing.  (Also,
a slight refactoring of TypeIndex.add_class.)

Massive overhaul of the indexing system, to simplify custom
indexing and fully support istype() criteria in instance/subclass
nodes.

Preliminary istype() support for predicate dispatch.
This is just the necessary compiler support for translating expressions
of the form ``type(x) is y`` and ``x in istype(y)``, some support for
istype() implication/intersection with Class criteria, and a bit of 
cleanup/refactoring of the indexing code.

NOT supported: mixing istype() and Classes...  or actually indexing 
istype() criteria.  The entire BitmapIndex system is going to have to be 
refactored in order to fully fix this.  :(  On the bright side, that 
will let me clean up a bunch of other index-related cruft, too.

Drop unnecessary attributes from BitmapIndex

Oops - during testing I commented out part of the fix for
an indexing bug.

Fix not getting disjuncts of 'not x' rules (bug reported
by R.D. Murray)

Fix range indexes not handling > cases correctly if there
are no other conditions in the index for the same value.
(Reported by Alberto Valverde.)

Fix selectivity problems with Truth and ==
comparisons that were ending up with branches==1,
leading to incorrect dispatch trees.  (The number
of branches should never be 1 in a correct index.)

String parsing and auto-upgrade of existing GFs!
Two major caveats, though: subexpression ordering
is not enforced, and subexpression calculation
caching is temporarily disabled, due to problems
with the stack trickery used in dispatching.  But
the basic engine is now working correctly.

Centralize the 2.3-compatibility code, fixup some missing
__all__ entries.

Separate memoization from builder state, drop build_root
method and go back to using Ordering(builder,expr) directly
for detecting ordering.  This lets us reuse the same builder
for different trees, as long as all the build state is kept
in the memo.

Index reseeding, classic MROs, enhanced "abstract", and 
smart engine recreation (w/unsubscribe).

Index refactoring: allow TreeBuilder subclasses to define how
expression-ordering is done, adjust ``BitmapIndex.seed_bits()``
and ``split_ranges`` to work better together and be a basis
for more complex dispatch node building.

Thread-safety and re-entrant code generation, such that calling a
function that is being regenerated will execute the previous code
for that function.  Simplified Engine protocols for code generation,
etc.

Switch to using peak.util.extremes

Changed to use AddOns instead of Aspects.

Improve the robustness of the core bootstrapping process, and flesh out
the ``Engine`` abstract base class a bit.  RuleSets now generate actions
using ``disjunct()``, so they should work with the predicate system now.
``overrides()`` for methods is now distinct from ``implies()``, as that
lowers the self-referentiality complexity just a bit.  :)  Also, it
paves the way to creating a less error-prone way of haing inter-
methodtype priorities (e.g. Around vs. Before/After, etc.).

PEAK-Rules is now as "smart" as RuleDispatch, in that it now
"knows" as much as RuleDispatch does about logical conditions
regarding Python objects, and how to index them efficiently.
The machinery is also better documented (and probably better
tested) than the equivalent bits of RuleDispatch.

Alas, this does not mean that you can actually use Python
expressions for generic function criteria yet, as the actual
tree builder/interpreter hasn't been written.  So we can
evaluate and index expressions, but not build them from an AST
or build/run a dispatch tree from the indexes.  Still, it's
getting *really* close now!

Move actual criterion types to peak.rules.criteria, which is also where
predicate/signature logic and criteria implication/intersection will
live.

Refactor ``seeds_for()`` to make its methods simpler to implement.

Implement indexing for is/not and </>/==/!= conditions, and general
bitmap-based index facility.  (Still needs class indexing to achieve
parity with the comparable parts of RuleDispatch, but it's getting
close.)

Added Aspects (ala PEP 3124) and refactor to use them in place of special
methods.  Refactor indexes to be aspects of an engine.  Improved handling
for the self-referential bootstrapping of the implies() generic function.

Added a generic version of the Chambers & Chen algorithm, with tests.  
Unlike the RuleDispatch implementation, this one doesn't care how 
indexes or criteria or expressions actually work, and it has a much 
simpler way of dealing with inter-expression constraints.  The tree 
building algorithm can also be easily revised to produce any kind of 
dispatch tree, either eagerly or lazily, and whether in the form of 
bytecode, source code, or an actual object tree.  (RuleDispatch only 
supports lazy creation of an object tree; it can't do anything else.)

Of course, this core algorithm is useless without some concrete types to 
represent expressions, criteria, and indexes -- not to mention some 
actual tree-generating code to go along with it.  But this algorithm for
generating decision trees will be at the heart of the main rule engine 
for predicate dispatching.

At this point, about 2/3rds of the code in the ``dispatch.functions``
module of RuleDispatch has been mapped to ``peak.rules.core`` and 
``peak.rules.indexing``.  About 1/6th of ``dispatch.strategy`` has also
been translated.  ``dispatch.ast_builder`` will not require any code
changes, but it will probably get some new tests.  The remaining modules,
however, (including ``strategy``, ``combiners``, and  ``predicates``)
will be changed substantially.

The good news is that these changes should mostly be simplifications, 
since most of the ``predicates`` module will become calls to 
BytecodeAssembler APIs.  But the remaining parts of ``strategy`` and 
``functions`` will likely become more complex, because they will need 
to know how to generate decision-making bytecode, deal with rule 
removals, and a few other odds and ends.  Some additional code will also 
be needed to ensure that the core implementation is sufficiently 
extensible to allow new features (like predicate abstractions and 
classifiers) to be implemented.