Merge branch 'mb/fetch' into develop

4 files changed, 1747 insertions, 7 deletions

diff --git a/test/query/ast_test/test_fetch.py b/test/query/ast_test/test_fetch.py
new file mode 100644
index 0000000..0c48a1f
--- /dev/null
+++ b/test/query/ast_test/test_fetch.py
@@ -0,0 +1,239 @@
+"""
+
+Part of the tagit test suite.
+A copy of the license is provided with the project.
+Author: Matthias Baumgartner, 2022
+"""
+# imports
+import unittest
+
+# bsfs imports
+from bsfs.namespace import ns
+from bsfs.utils import URI
+
+# objects to test
+from bsfs.query.ast.fetch import FetchExpression
+from bsfs.query.ast.fetch import All, This
+from bsfs.query.ast.fetch import _Branch, Fetch
+from bsfs.query.ast.fetch import _Named, Node, Value
+
+
+## code ##
+
+class TestExpression(unittest.TestCase): # FetchExpression
+    def test_essentials(self):
+        class Foo(FetchExpression): pass
+        # comparison
+        self.assertEqual(FetchExpression(), FetchExpression())
+        self.assertEqual(hash(FetchExpression()), hash(FetchExpression()))
+        # comparison respects type
+        self.assertNotEqual(FetchExpression(), Foo())
+        self.assertNotEqual(hash(FetchExpression()), hash(Foo()))
+        # string conversion
+        self.assertEqual(str(FetchExpression()), 'FetchExpression()')
+        self.assertEqual(repr(FetchExpression()), 'FetchExpression()')
+        self.assertEqual(str(Foo()), 'Foo()')
+        self.assertEqual(repr(Foo()), 'Foo()')
+
+
+class TestAll(unittest.TestCase): # All
+    def test_essentials(self):
+        class Foo(All): pass
+        expr0 = This('hello')
+        expr1 = This('world')
+        # comparison
+        self.assertEqual(All(expr0), All(expr0))
+        self.assertEqual(hash(All(expr0)), hash(All(expr0)))
+        # comparison respects type
+        self.assertNotEqual(All(expr0), Foo(expr0))
+        self.assertNotEqual(hash(All(expr0)), hash(Foo(expr0)))
+        # comparison respects expressions
+        self.assertEqual(All(expr0, expr1), All(expr0, expr1))
+        self.assertEqual(hash(All(expr0, expr1)), hash(All(expr0, expr1)))
+        self.assertNotEqual(All(expr0), All(expr1))
+        self.assertNotEqual(hash(All(expr0)), hash(All(expr1)))
+        # expressions are unordered
+        self.assertEqual(All(expr0, expr1), All(expr1, expr0))
+        self.assertEqual(hash(All(expr0, expr1)), hash(All(expr1, expr0)))
+        # string conversion
+        self.assertIn(str(All(expr0, expr1)), {
+            'All({This(world), This(hello)})',
+            'All({This(hello), This(world)})'})
+        self.assertIn(repr(All(expr0, expr1)), {
+            'All({This(world), This(hello)})',
+            'All({This(hello), This(world)})'})
+
+    def test_members(self):
+        class Foo(): pass
+        expr0 = This('hello')
+        expr1 = This('world')
+        # requires at least one child expression
+        self.assertRaises(AttributeError, All)
+        # expr returns child expressions
+        self.assertEqual(All(expr0, expr1).expr, {expr0, expr1})
+        # can pass expressions as arguments
+        self.assertEqual(All(expr0, expr1).expr, {expr0, expr1})
+        # can pass a single expression as argument
+        self.assertEqual(All(expr0).expr, {expr0})
+        # can pass expressions as list-like
+        self.assertEqual(All([expr0, expr1]).expr, {expr0, expr1})
+        self.assertEqual(All((expr0, expr1)).expr, {expr0, expr1})
+        self.assertEqual(All({expr0, expr1}).expr, {expr0, expr1})
+        # can pass a single expression as list-like
+        self.assertEqual(All([expr0]).expr, {expr0})
+        # must pass a FilterExpression
+        self.assertRaises(TypeError, All, Foo())
+        self.assertRaises(TypeError, All, 1234)
+        self.assertRaises(TypeError, All, 'hello world')
+        # len returns the number of child expressions
+        self.assertEqual(len(All(expr0)), 1)
+        self.assertEqual(len(All(expr0, expr1)), 2)
+        # iter iterates over child expressions
+        self.assertSetEqual(set(All(expr0, expr1)), {expr0, expr1})
+
+
+class TestThis(unittest.TestCase): # This
+    def test_essentials(self):
+        class Foo(This): pass
+        # comparison
+        self.assertEqual(This('hello'), This('hello'))
+        self.assertEqual(hash(This('hello')), hash(This('hello')))
+        # comparison respects type
+        self.assertNotEqual(This('hello'), Foo('hello'))
+        self.assertNotEqual(hash(This('hello')), hash(Foo('hello')))
+        # comparison respects name
+        self.assertNotEqual(This('hello'), This('world'))
+        self.assertNotEqual(hash(This('hello')), hash(This('world')))
+        # string conversion
+        self.assertEqual(str(This('hello')), 'This(hello)')
+        self.assertEqual(repr(This('hello')), 'This(hello)')
+
+    def test_members(self):
+        class Foo(): pass
+        # name returns member
+        self.assertEqual(This('hello').name, 'hello')
+        self.assertEqual(This('world').name, 'world')
+        # name is converted to a string
+        self.assertEqual(This(1234).name, '1234')
+        foo = Foo()
+        self.assertEqual(This(foo).name, str(foo))
+
+
+class TestBranch(unittest.TestCase): # _Branch, Fetch
+    def test_essentials(self):
+        pred = ns.bse.tag
+        expr = FetchExpression()
+        # comparison
+        self.assertEqual(_Branch(pred), _Branch(pred))
+        self.assertEqual(hash(_Branch(pred)), hash(_Branch(pred)))
+        self.assertEqual(Fetch(pred, expr), Fetch(pred, expr))
+        self.assertEqual(hash(Fetch(pred, expr)), hash(Fetch(pred, expr)))
+        # comparison respects type
+        self.assertNotEqual(_Branch(pred), Fetch(pred, expr))
+        self.assertNotEqual(hash(_Branch(pred)), hash(Fetch(pred, expr)))
+        self.assertNotEqual(Fetch(pred, expr), _Branch(pred))
+        self.assertNotEqual(hash(Fetch(pred, expr)), hash(_Branch(pred)))
+        # comparison respects predicate
+        self.assertNotEqual(_Branch(pred), _Branch(ns.bse.filesize))
+        self.assertNotEqual(hash(_Branch(pred)), hash(_Branch(ns.bse.filesize)))
+        self.assertNotEqual(Fetch(pred, expr), Fetch(ns.bse.filesize, expr))
+        self.assertNotEqual(hash(Fetch(pred, expr)), hash(Fetch(ns.bse.filesize, expr)))
+        # comparison respects expression
+        self.assertNotEqual(Fetch(pred, expr), Fetch(pred, This('foo')))
+        self.assertNotEqual(hash(Fetch(pred, expr)), hash(Fetch(pred, This('foo'))))
+        # string conversion
+        self.assertEqual(str(_Branch(pred)), f'_Branch({pred})')
+        self.assertEqual(repr(_Branch(pred)), f'_Branch({pred})')
+        self.assertEqual(str(Fetch(pred, expr)), f'Fetch({pred}, {expr})')
+        self.assertEqual(repr(Fetch(pred, expr)), f'Fetch({pred}, {expr})')
+
+    def test_members(self):
+        class Foo(): pass
+        pred = ns.bse.tag
+        expr = FetchExpression()
+
+        # predicate returns member
+        self.assertEqual(_Branch(pred).predicate, pred)
+        self.assertEqual(Fetch(pred, expr).predicate, pred)
+        # can pass an URI
+        self.assertEqual(_Branch(ns.bse.filename).predicate, ns.bse.filename)
+        self.assertEqual(Fetch(ns.bse.filename, expr).predicate, ns.bse.filename)
+        # must pass an URI
+        self.assertRaises(TypeError, _Branch, Foo())
+        self.assertRaises(TypeError, Fetch, Foo(), expr)
+        # expression returns member
+        self.assertEqual(Fetch(pred, expr).expr, expr)
+        # expression must be a FilterExpression
+        self.assertRaises(TypeError, Fetch, ns.bse.filename, 'hello')
+        self.assertRaises(TypeError, Fetch, ns.bse.filename, 1234)
+        self.assertRaises(TypeError, Fetch, ns.bse.filename, Foo())
+
+
+class TestNamed(unittest.TestCase): # _Named, Node, Value
+    def test_essentials(self):
+        pred = ns.bse.tag
+        name = 'foobar'
+        # comparison
+        self.assertEqual(_Named(pred, name), _Named(pred, name))
+        self.assertEqual(hash(_Named(pred, name)), hash(_Named(pred, name)))
+        # comparison respects type
+        self.assertNotEqual(_Named(pred, name), Node(pred, name))
+        self.assertNotEqual(Node(pred, name), Value(pred, name))
+        self.assertNotEqual(Value(pred, name), _Named(pred, name))
+        self.assertNotEqual(hash(_Named(pred, name)), hash(Node(pred, name)))
+        self.assertNotEqual(hash(Node(pred, name)), hash(Value(pred, name)))
+        self.assertNotEqual(hash(Value(pred, name)), hash(_Named(pred, name)))
+        # comparison respects predicate
+        self.assertNotEqual(_Named(pred, name), _Named(ns.bse.filesize, name))
+        self.assertNotEqual(hash(_Named(pred, name)), hash(_Named(ns.bse.filesize, name)))
+        self.assertNotEqual(Node(pred, name), Node(ns.bse.filesize, name))
+        self.assertNotEqual(hash(Node(pred, name)), hash(Node(ns.bse.filesize, name)))
+        self.assertNotEqual(Value(pred, name), Value(ns.bse.filesize, name))
+        self.assertNotEqual(hash(Value(pred, name)), hash(Value(ns.bse.filesize, name)))
+        # comparison respects name
+        self.assertNotEqual(_Named(pred, name), _Named(pred, 'foo'))
+        self.assertNotEqual(hash(_Named(pred, name)), hash(_Named(pred, 'foo')))
+        self.assertNotEqual(Node(pred, name), Node(pred, 'foo'))
+        self.assertNotEqual(hash(Node(pred, name)), hash(Node(pred, 'foo')))
+        self.assertNotEqual(Value(pred, name), Value(pred, 'foo'))
+        self.assertNotEqual(hash(Value(pred, name)), hash(Value(pred, 'foo')))
+        # string conversion
+        self.assertEqual(str(_Named(pred, name)), f'_Named({pred}, {name})')
+        self.assertEqual(repr(_Named(pred, name)), f'_Named({pred}, {name})')
+        self.assertEqual(str(Node(pred, name)), f'Node({pred}, {name})')
+        self.assertEqual(repr(Node(pred, name)), f'Node({pred}, {name})')
+        self.assertEqual(str(Value(pred, name)), f'Value({pred}, {name})')
+        self.assertEqual(repr(Value(pred, name)), f'Value({pred}, {name})')
+
+    def test_members(self):
+        class Foo(): pass
+        pred = ns.bse.tag
+        name = 'foobar'
+        # predicate returns member
+        self.assertEqual(_Named(pred, name).predicate, pred)
+        self.assertEqual(Node(pred, name).predicate, pred)
+        self.assertEqual(Value(pred, name).predicate, pred)
+        # can pass an URI as predicate
+        self.assertEqual(_Named(ns.bse.filename, name).predicate, ns.bse.filename)
+        self.assertEqual(Node(ns.bse.filename, name).predicate, ns.bse.filename)
+        self.assertEqual(Value(ns.bse.filename, name).predicate, ns.bse.filename)
+        # must pass an URI
+        self.assertRaises(TypeError, _Named, Foo(), name)
+        self.assertRaises(TypeError, Node, Foo(), name)
+        self.assertRaises(TypeError, Value, Foo(), name)
+        # name returns member
+        self.assertEqual(_Named(pred, name).name, name)
+        self.assertEqual(Node(pred, name).name, name)
+        self.assertEqual(Value(pred, name).name, name)
+        # name is converted to a string
+        self.assertEqual(_Named(pred, 1234).name, '1234')
+        self.assertEqual(Node(pred, 1234).name, '1234')
+        self.assertEqual(Value(pred, 1234).name, '1234')
+
+
+## main ##
+
+if __name__ == '__main__':
+    unittest.main()
+
+## EOF ##
diff --git a/test/query/ast_test/test_filter_.py b/test/query/ast_test/test_filter_.py
index 9eb92e2..39b98f8 100644
--- a/test/query/ast_test/test_filter_.py
+++ b/test/query/ast_test/test_filter_.py
@@ -20,6 +20,7 @@ from bsfs.query.ast.filter_ import _Value, Is, Equals, Substring, StartsWith, En
 from bsfs.query.ast.filter_ import _Bounded, LessThan, GreaterThan
 from bsfs.query.ast.filter_ import Predicate, OneOf
 from bsfs.query.ast.filter_ import IsIn, IsNotIn
+from bsfs.query.ast.filter_ import Includes, Excludes, Between
 
 
 ## code ##
@@ -456,13 +457,15 @@ class TestOneOf(unittest.TestCase):
         self.assertEqual(len(OneOf(Predicate(ns.bse.filesize), Predicate(ns.bse.filename), Predicate(ns.bse.tag))), 3)
 
 
-    def testIsIn(self):
+    def test_IsIn(self):
+        # cannot pass zero arguments
+        self.assertRaises(AttributeError, IsIn)
         # can pass expressions as arguments
         self.assertEqual(IsIn('http://example.com/entity#1234', 'http://example.com/entity#4321'),
             Or(Is('http://example.com/entity#1234'), Is('http://example.com/entity#4321')))
         # can pass one expression as argument
         self.assertEqual(IsIn('http://example.com/entity#1234'),
-            Or(Is('http://example.com/entity#1234')))
+            Is('http://example.com/entity#1234'))
         # can pass expressions as iterator
         self.assertEqual(IsIn(iter(('http://example.com/entity#1234', 'http://example.com/entity#4321'))),
             Or(Is('http://example.com/entity#1234'), Is('http://example.com/entity#4321')))
@@ -477,16 +480,18 @@ class TestOneOf(unittest.TestCase):
             Or(Is('http://example.com/entity#1234'), Is('http://example.com/entity#4321')))
         # can pass one expression as list-like
         self.assertEqual(IsIn(['http://example.com/entity#1234']),
-            Or(Is('http://example.com/entity#1234')))
+            Is('http://example.com/entity#1234'))
 
 
-    def testIsNotIn(self):
+    def test_IsNotIn(self):
+        # cannot pass zero arguments
+        self.assertRaises(AttributeError, IsNotIn)
         # can pass expressions as arguments
         self.assertEqual(IsNotIn('http://example.com/entity#1234', 'http://example.com/entity#4321'),
             Not(Or(Is('http://example.com/entity#1234'), Is('http://example.com/entity#4321'))))
         # can pass one expression as argument
         self.assertEqual(IsNotIn('http://example.com/entity#1234'),
-            Not(Or(Is('http://example.com/entity#1234'))))
+            Not(Is('http://example.com/entity#1234')))
         # can pass expressions as iterator
         self.assertEqual(IsNotIn(iter(('http://example.com/entity#1234', 'http://example.com/entity#4321'))),
             Not(Or(Is('http://example.com/entity#1234'), Is('http://example.com/entity#4321'))))
@@ -501,9 +506,110 @@ class TestOneOf(unittest.TestCase):
             Not(Or(Is('http://example.com/entity#1234'), Is('http://example.com/entity#4321'))))
         # can pass one expression as list-like
         self.assertEqual(IsNotIn(['http://example.com/entity#1234']),
-            Not(Or(Is('http://example.com/entity#1234'))))
+            Not(Is('http://example.com/entity#1234')))
 
 
+    def test_Includes(self):
+        # cannot pass zero arguments
+        self.assertRaises(AttributeError, Includes)
+        # can pass expressions as arguments
+        self.assertEqual(Includes('hello', 'world'),
+            Or(Equals('hello'), Equals('world')))
+        self.assertEqual(Includes('hello', 'world', approx=True),
+            Or(Substring('hello'), Substring('world')))
+        # can pass one expression as argument
+        self.assertEqual(Includes('hello'),
+            Equals('hello'))
+        self.assertEqual(Includes('hello', approx=True),
+            Substring('hello'))
+        # can pass expressions as iterator
+        self.assertEqual(Includes(iter(('hello', 'world'))),
+            Or(Equals('hello'), Equals('world')))
+        self.assertEqual(Includes(iter(('hello', 'world')), approx=True),
+            Or(Substring('hello'), Substring('world')))
+        # can pass expressions as generator
+        def gen():
+            yield 'hello'
+            yield 'world'
+        self.assertEqual(Includes(gen()),
+            Or(Equals('hello'), Equals('world')))
+        self.assertEqual(Includes(gen(), approx=True),
+            Or(Substring('hello'), Substring('world')))
+        # can pass expressions as list-like
+        self.assertEqual(Includes(['hello', 'world']),
+            Or(Equals('hello'), Equals('world')))
+        self.assertEqual(Includes(['hello', 'world'], approx=True),
+            Or(Substring('hello'), Substring('world')))
+        # can pass one expression as list-like
+        self.assertEqual(Includes(['hello']),
+            Equals('hello'))
+        self.assertEqual(Includes(['hello'], approx=True),
+            Substring('hello'))
+
+
+    def test_Excludes(self):
+        # cannot pass zero arguments
+        self.assertRaises(AttributeError, Excludes)
+        # can pass expressions as arguments
+        self.assertEqual(Excludes('hello', 'world'),
+            Not(Or(Equals('hello'), Equals('world'))))
+        self.assertEqual(Excludes('hello', 'world', approx=True),
+            Not(Or(Substring('hello'), Substring('world'))))
+        # can pass one expression as argument
+        self.assertEqual(Excludes('hello'),
+            Not(Equals('hello')))
+        self.assertEqual(Excludes('hello', approx=True),
+            Not(Substring('hello')))
+        # can pass expressions as iterator
+        self.assertEqual(Excludes(iter(('hello', 'world'))),
+            Not(Or(Equals('hello'), Equals('world'))))
+        self.assertEqual(Excludes(iter(('hello', 'world')), approx=True),
+            Not(Or(Substring('hello'), Substring('world'))))
+        # can pass expressions as generator
+        def gen():
+            yield 'hello'
+            yield 'world'
+        self.assertEqual(Excludes(gen()),
+            Not(Or(Equals('hello'), Equals('world'))))
+        self.assertEqual(Excludes(gen(), approx=True),
+            Not(Or(Substring('hello'), Substring('world'))))
+        # can pass expressions as list-like
+        self.assertEqual(Excludes(['hello', 'world']),
+            Not(Or(Equals('hello'), Equals('world'))))
+        self.assertEqual(Excludes(['hello', 'world'], approx=True),
+            Not(Or(Substring('hello'), Substring('world'))))
+        # can pass one expression as list-like
+        self.assertEqual(Excludes(['hello']),
+            Not(Equals('hello')))
+        self.assertEqual(Excludes(['hello'], approx=True),
+            Not(Substring('hello')))
+
+
+    def test_Between(self):
+        # must specify at least one bound
+        self.assertRaises(ValueError, Between, float('inf'), float('inf'))
+        # lower bound must be less than the upper bound
+        self.assertRaises(ValueError, Between, 321, 123)
+        # can set a lower bound only
+        self.assertEqual(Between(123),
+            GreaterThan(123, strict=True))
+        self.assertEqual(Between(123, lo_strict=False),
+            GreaterThan(123, strict=False))
+        # can set an upper bound only
+        self.assertEqual(Between(hi=123),
+            LessThan(123, strict=True))
+        self.assertEqual(Between(hi=123, hi_strict=False),
+            LessThan(123, strict=False))
+        # can set both bounds
+        self.assertEqual(Between(123, 321),
+            And(GreaterThan(123, strict=True), LessThan(321, strict=True)))
+        self.assertEqual(Between(123, 321, False, False),
+            And(GreaterThan(123, strict=False), LessThan(321, strict=False)))
+        # can set identical bounds
+        self.assertRaises(ValueError, Between, 123, 123)
+        self.assertEqual(Between(123, 123, False, False),
+            Equals(123))
+
 
 ## main ##
 
diff --git a/test/query/test_matcher.py b/test/query/test_matcher.py
new file mode 100644
index 0000000..e830cf8
--- /dev/null
+++ b/test/query/test_matcher.py
@@ -0,0 +1,1182 @@
+"""
+
+Part of the tagit test suite.
+A copy of the license is provided with the project.
+Author: Matthias Baumgartner, 2022
+"""
+# imports
+import operator
+import unittest
+
+# bsfs imports
+from bsfs.namespace import ns
+from bsfs.query import ast
+from bsfs.utils import errors
+
+# objects to test
+from bsfs.query.matcher import Any, Filter, Partial, Rest, _set_matcher
+
+
+## code ##
+
+class TestAny(unittest.TestCase):
+    def test_essentials(self):
+        # comparison
+        a = Any()
+        b = Any()
+        self.assertNotEqual(Any(), Any())
+        self.assertNotEqual(hash(Any()), hash(Any()))
+        self.assertNotEqual(a, Any())
+        self.assertNotEqual(hash(a), hash(Any()))
+        self.assertNotEqual(a, b)
+        self.assertNotEqual(hash(a), hash(b))
+        # comparison within sets
+        self.assertEqual(len({Any(), Any(), Any(), Any()}), 4)
+        self.assertEqual(len({Any() for _ in range(1000)}), 1000)
+        # string representation
+        self.assertEqual(str(Any()), 'Any()')
+        self.assertEqual(repr(Any()), 'Any()')
+
+
+class TestRest(unittest.TestCase):
+    def test_essentials(self):
+        expr = ast.filter.Equals('hello')
+        # comparison
+        self.assertEqual(Rest(expr), Rest(expr))
+        self.assertEqual(hash(Rest(expr)), hash(Rest(expr)))
+        # comparison respects type
+        class Foo(): pass
+        self.assertNotEqual(Rest(expr), 1234)
+        self.assertNotEqual(hash(Rest(expr)), hash(1234))
+        self.assertNotEqual(Rest(expr), Foo())
+        self.assertNotEqual(hash(Rest(expr)), hash(Foo()))
+        # comparison respects expr
+        self.assertNotEqual(Rest(expr), Rest(ast.filter.Equals('world')))
+        self.assertNotEqual(hash(Rest(expr)), hash(Rest(ast.filter.Equals('world'))))
+        # default constructor -> Any -> Not equal
+        self.assertNotEqual(Rest(), Rest())
+        self.assertNotEqual(hash(Rest()), hash(Rest()))
+        # string representation
+        self.assertEqual(str(Rest()), 'Rest(Any())')
+        self.assertEqual(str(Rest(expr)), 'Rest(Equals(hello))')
+        self.assertEqual(repr(Rest()), 'Rest(Any())')
+        self.assertEqual(repr(Rest(expr)), 'Rest(Equals(hello))')
+
+
+
+class TestPartial(unittest.TestCase):
+    def test_match(self):
+        p0 = Partial(ast.filter.LessThan)
+        p1 = Partial(ast.filter.LessThan, threshold=3)
+        p2 = Partial(ast.filter.LessThan, strict=False)
+        p3 = Partial(ast.filter.LessThan, threshold=3, strict=False)
+        # match respects name
+        self.assertTrue(p0.match('foo', None))
+        self.assertTrue(p1.match('foo', None))
+        self.assertTrue(p2.match('foo', None))
+        self.assertTrue(p3.match('foo', None))
+        # match respects correct value
+        self.assertTrue(p0.match('threshold', 3))
+        self.assertTrue(p1.match('threshold', 3))
+        self.assertTrue(p2.match('threshold', 3))
+        self.assertTrue(p3.match('threshold', 3))
+        self.assertTrue(p0.match('strict', False))
+        self.assertTrue(p1.match('strict', False))
+        self.assertTrue(p2.match('strict', False))
+        self.assertTrue(p3.match('strict', False))
+        # match respects incorrect value
+        self.assertTrue(p0.match('threshold', 5))
+        self.assertFalse(p1.match('threshold', 5))
+        self.assertTrue(p2.match('threshold', 5))
+        self.assertFalse(p3.match('threshold', 5))
+        self.assertTrue(p0.match('strict', True))
+        self.assertTrue(p1.match('strict', True))
+        self.assertFalse(p2.match('strict', True))
+        self.assertFalse(p3.match('strict', True))
+
+    def test_members(self):
+        # node returns expression
+        self.assertEqual(Partial(ast.filter.Equals).node, ast.filter.Equals)
+        self.assertEqual(Partial(ast.filter.LessThan).node, ast.filter.LessThan)
+        # kwargs returns arguments
+        self.assertDictEqual(Partial(ast.filter.Equals, value='hello').kwargs,
+            {'value': 'hello'})
+        self.assertDictEqual(Partial(ast.filter.LessThan, threshold=3, strict=False).kwargs,
+            {'threshold': 3, 'strict': False})
+        # Partial does not check about kwargs
+        self.assertDictEqual(Partial(ast.filter.LessThan, value='hello').kwargs,
+            {'value': 'hello'})
+        self.assertDictEqual(Partial(ast.filter.Equals, threshold=3, strict=False).kwargs,
+            {'threshold': 3, 'strict': False})
+
+    def test_essentials(self):
+        # comparison respects type
+        class Foo(): pass
+        self.assertNotEqual(Partial(ast.filter.Equals), 1234)
+        self.assertNotEqual(hash(Partial(ast.filter.Equals)), hash(1234))
+        self.assertNotEqual(Partial(ast.filter.Equals), Foo())
+        self.assertNotEqual(hash(Partial(ast.filter.Equals)), hash(Foo()))
+        self.assertNotEqual(Partial(ast.filter.Equals), ast.filter.Equals)
+        self.assertNotEqual(hash(Partial(ast.filter.Equals)), hash(ast.filter.Equals))
+        self.assertNotEqual(Partial(ast.filter.Equals), ast.filter.Equals('hello'))
+        self.assertNotEqual(hash(Partial(ast.filter.Equals)), hash(ast.filter.Equals('hello')))
+        # comparison respects node
+        self.assertEqual(Partial(ast.filter.Equals), Partial(ast.filter.Equals))
+        self.assertEqual(hash(Partial(ast.filter.Equals)), hash(Partial(ast.filter.Equals)))
+        self.assertEqual(Partial(ast.filter.LessThan), Partial(ast.filter.LessThan))
+        self.assertEqual(hash(Partial(ast.filter.LessThan)), hash(Partial(ast.filter.LessThan)))
+        self.assertNotEqual(Partial(ast.filter.Equals), Partial(ast.filter.LessThan))
+        self.assertNotEqual(hash(Partial(ast.filter.Equals)), hash(Partial(ast.filter.LessThan)))
+        # comparison respects kwargs
+        self.assertEqual(
+            Partial(ast.filter.Equals, value='hello'),
+            Partial(ast.filter.Equals, value='hello'))
+        self.assertEqual(
+            hash(Partial(ast.filter.Equals, value='hello')),
+            hash(Partial(ast.filter.Equals, value='hello')))
+        self.assertEqual(
+            Partial(ast.filter.LessThan, threshold=3, strict=False),
+            Partial(ast.filter.LessThan, threshold=3, strict=False))
+        self.assertEqual(
+            hash(Partial(ast.filter.LessThan, threshold=3, strict=False)),
+            hash(Partial(ast.filter.LessThan, threshold=3, strict=False)))
+        self.assertNotEqual(
+            Partial(ast.filter.Equals, value='hello'),
+            Partial(ast.filter.Equals))
+        self.assertNotEqual(
+            hash(Partial(ast.filter.Equals, value='hello')),
+            hash(Partial(ast.filter.Equals)))
+        self.assertNotEqual(
+            Partial(ast.filter.Equals, value='hello'),
+            Partial(ast.filter.Equals, value='world'))
+        self.assertNotEqual(
+            hash(Partial(ast.filter.Equals, value='hello')),
+            hash(Partial(ast.filter.Equals, value='world')))
+        self.assertNotEqual(
+            Partial(ast.filter.LessThan, threshold=3, strict=False),
+            Partial(ast.filter.LessThan))
+        self.assertNotEqual(
+            hash(Partial(ast.filter.LessThan, threshold=3, strict=False)),
+            hash(Partial(ast.filter.LessThan)))
+        self.assertNotEqual(
+            Partial(ast.filter.LessThan, threshold=3, strict=False),
+            Partial(ast.filter.LessThan, threshold=5))
+        self.assertNotEqual(
+            hash(Partial(ast.filter.LessThan, threshold=3, strict=False)),
+            hash(Partial(ast.filter.LessThan, threshold=5)))
+        self.assertNotEqual(
+            Partial(ast.filter.LessThan, threshold=3, strict=False),
+            Partial(ast.filter.LessThan, strict=False))
+        self.assertNotEqual(
+            hash(Partial(ast.filter.LessThan, threshold=3, strict=False)),
+            hash(Partial(ast.filter.LessThan, strict=False)))
+        self.assertNotEqual(
+            Partial(ast.filter.LessThan, threshold=3, strict=False),
+            Partial(ast.filter.LessThan, threshold=3, strict=True))
+        self.assertNotEqual(
+            hash(Partial(ast.filter.LessThan, threshold=3, strict=False)),
+            hash(Partial(ast.filter.LessThan, threshold=3, strict=True)))
+        self.assertNotEqual(
+            Partial(ast.filter.LessThan, threshold=3, strict=False),
+            Partial(ast.filter.LessThan, threshold=5, strict=False))
+        self.assertNotEqual(
+            hash(Partial(ast.filter.LessThan, threshold=3, strict=False)),
+            hash(Partial(ast.filter.LessThan, threshold=5, strict=False)))
+        # string representation
+        self.assertEqual(str(Partial(ast.filter.Equals)), 'Partial(Equals, {})')
+        self.assertEqual(repr(Partial(ast.filter.Equals)), 'Partial(Equals, {})')
+        self.assertEqual(str(Partial(ast.filter.LessThan)), 'Partial(LessThan, {})')
+        self.assertEqual(repr(Partial(ast.filter.LessThan)), 'Partial(LessThan, {})')
+        self.assertEqual(str(Partial(ast.filter.Equals, value='hello')), "Partial(Equals, {'value': 'hello'})")
+        self.assertEqual(repr(Partial(ast.filter.Equals, value='hello')), "Partial(Equals, {'value': 'hello'})")
+        self.assertEqual(str(Partial(ast.filter.LessThan, threshold=3)), "Partial(LessThan, {'threshold': 3})")
+        self.assertEqual(repr(Partial(ast.filter.LessThan, threshold=3)), "Partial(LessThan, {'threshold': 3})")
+        self.assertEqual(str(Partial(ast.filter.LessThan, strict=False)), "Partial(LessThan, {'strict': False})")
+        self.assertEqual(repr(Partial(ast.filter.LessThan, strict=False)), "Partial(LessThan, {'strict': False})")
+        self.assertEqual(str(Partial(ast.filter.LessThan, threshold=3, strict=False)), "Partial(LessThan, {'threshold': 3, 'strict': False})")
+        self.assertEqual(repr(Partial(ast.filter.LessThan, threshold=3, strict=False)), "Partial(LessThan, {'threshold': 3, 'strict': False})")
+
+
+class TestSetMatcher(unittest.TestCase):
+    def test_set_matcher(self):
+        # setup
+        A = ast.filter.Equals('A')
+        B = ast.filter.Equals('B')
+        C = ast.filter.Equals('C')
+        D = ast.filter.Equals('D')
+        matcher = Filter()
+
+        # identical sets match
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, B, C),
+            matcher._parse_filter_expression,
+            ))
+
+        # order is irrelevant
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(B, C, A),
+            matcher._parse_filter_expression,
+            ))
+
+        # all reference items must be present
+        self.assertFalse(_set_matcher(
+            ast.filter.And(A, B),
+            ast.filter.And(A, B, C),
+            matcher._parse_filter_expression,
+            ))
+
+        # all reference items must have a match
+        self.assertFalse(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(D, B, C),
+            matcher._parse_filter_expression,
+            ))
+        self.assertFalse(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, D, C),
+            matcher._parse_filter_expression,
+            ))
+        self.assertFalse(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, B, D),
+            matcher._parse_filter_expression,
+            ))
+
+        # Any matches every item
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(Any(), B, C),
+            matcher._parse_filter_expression,
+            ))
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, Any(), C),
+            matcher._parse_filter_expression,
+            ))
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, B, Any()),
+            matcher._parse_filter_expression,
+            ))
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, D),
+            ast.filter.And(A, B, Any()),
+            matcher._parse_filter_expression,
+            ))
+
+        # there can be multiple Any's
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, Any(), Any()),
+            matcher._parse_filter_expression,
+            ))
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(Any(), B, Any()),
+            matcher._parse_filter_expression,
+            ))
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(Any(), Any(), C),
+            matcher._parse_filter_expression,
+            ))
+
+        # Any covers exactly one element
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, B, Any()),
+            matcher._parse_filter_expression,
+            ))
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, D),
+            ast.filter.And(A, B, Any()),
+            matcher._parse_filter_expression,
+            ))
+        self.assertFalse(_set_matcher(
+            ast.filter.And(A, B),
+            ast.filter.And(A, B, Any()),
+            matcher._parse_filter_expression,
+            ))
+        self.assertFalse(_set_matcher(
+            ast.filter.And(A, B, C, D),
+            ast.filter.And(A, B, Any()),
+            matcher._parse_filter_expression,
+            ))
+
+        # each Any covers exactly one element
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(Any(), Any(), Any()),
+            matcher._parse_filter_expression,
+            ))
+        self.assertFalse(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(Any(), Any()),
+            matcher._parse_filter_expression,
+            ))
+        self.assertFalse(_set_matcher(
+            ast.filter.And(A, B),
+            ast.filter.And(Any(), Any(), Any()),
+            matcher._parse_filter_expression,
+            ))
+
+        # Rest captures remainder
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, B, Rest()),
+            matcher._parse_filter_expression,
+            ))
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C, D),
+            ast.filter.And(A, B, Rest()),
+            matcher._parse_filter_expression,
+            ))
+        # remainder matches the empty set
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B),
+            ast.filter.And(A, B, Rest()),
+            matcher._parse_filter_expression,
+            ))
+        # Rest does not absolve other refernce items from having a match
+        self.assertFalse(_set_matcher(
+            ast.filter.And(A, C, D),
+            ast.filter.And(A, B, Rest()),
+            matcher._parse_filter_expression,
+            ))
+        # Rest can be combined with Any ...
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, C, D),
+            ast.filter.And(A, Any(), Rest()),
+            matcher._parse_filter_expression,
+            ))
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, C, D),
+            ast.filter.And(A, Any(), Rest()),
+            matcher._parse_filter_expression,
+            ))
+        # ... explicit items still need to match
+        self.assertFalse(_set_matcher(
+            ast.filter.And(A, C, D),
+            ast.filter.And(B, Any(), Rest()),
+            matcher._parse_filter_expression,
+            ))
+        # ... Any still determines minimum element count
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B),
+            ast.filter.And(A, Any(), Rest()),
+            matcher._parse_filter_expression,
+            ))
+        self.assertFalse(_set_matcher(
+            ast.filter.And(A, B),
+            ast.filter.And(A, Any(), Any(), Rest()),
+            matcher._parse_filter_expression,
+            ))
+        # Rest cannot be repeated ...
+        self.assertRaises(errors.BackendError, _set_matcher,
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, Rest(), Rest(ast.filter.Equals('hello'))),
+            matcher._parse_filter_expression,
+            )
+        # ... unless they are identical
+        self.assertRaises(errors.BackendError, _set_matcher,
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, Rest(), Rest()), # Any instances are different!
+            matcher._parse_filter_expression,
+            )
+        # ... unless they are identical
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, B, Rest(C), Rest(C)),
+            matcher._parse_filter_expression,
+            ))
+        # Rest can mandate a specific expression
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, B, Rest(C)),
+            matcher._parse_filter_expression,
+            ))
+        self.assertFalse(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, B, Rest(D)),
+            matcher._parse_filter_expression,
+            ))
+        # Rest can mandate a partial expression
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, B, Rest(Partial(ast.filter.Equals))),
+            matcher._parse_filter_expression,
+            ))
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, Rest(Partial(ast.filter.Equals))),
+            matcher._parse_filter_expression,
+            ))
+        self.assertFalse(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, B, Rest(Partial(ast.filter.Substring))),
+            matcher._parse_filter_expression,
+            ))
+        self.assertFalse(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(A, B, Rest(Partial(ast.filter.Equals, value='D'))),
+            matcher._parse_filter_expression,
+            ))
+        # Rest can be the only expression
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(Rest(Partial(ast.filter.Equals))),
+            matcher._parse_filter_expression,
+            ))
+        # Rest's expression defaults to Any
+        self.assertTrue(_set_matcher(
+            ast.filter.And(A, B, C),
+            ast.filter.And(Rest()),
+            matcher._parse_filter_expression,
+            ))
+
+
+class TestFilter(unittest.TestCase):
+    def setUp(self):
+        self.match = Filter()
+
+    def test_call(self):
+        # query must be a filter expression
+        self.assertRaises(errors.BackendError, self.match, 1234, Any())
+        self.assertRaises(errors.BackendError, self.match, ast.filter.Predicate(ns.bse.filename), Any())
+        # reference must be a filter expression
+        self.assertRaises(errors.BackendError, self.match, ast.filter.Equals('hello'), 1234)
+        self.assertRaises(errors.BackendError, self.match, ast.filter.Equals('hello'), ast.filter.Predicate(ns.bse.filename))
+        # reference can be Any or Partial
+        self.assertTrue(self.match(
+            ast.filter.Equals('hello'),
+            Any(),
+            ))
+        self.assertTrue(self.match(
+            ast.filter.Equals('hello'),
+            Partial(ast.filter.Equals),
+            ))
+        # call parses expression
+        self.assertTrue(self.match(
+            # query
+            ast.filter.And(
+                ast.filter.Any(ns.bse.tag,
+                    ast.filter.All(ns.bse.label,
+                        ast.filter.Or(
+                            ast.filter.Equals('hello'),
+                            ast.filter.Equals('world'),
+                            ast.filter.StartsWith('foo'),
+                            ast.filter.EndsWith('bar'),
+                            )
+                        )
+                    ),
+                ast.filter.Any(ns.bse.iso,
+                    ast.filter.And(
+                        ast.filter.GreaterThan(100, strict=True),
+                        ast.filter.LessThan(200, strict=False),
+                        )
+                    ),
+                ast.filter.Any(ast.filter.OneOf(ns.bse.featureA, ns.bse.featureB),
+                    ast.filter.Distance([1,2,3], 1)
+                    ),
+                ),
+            # reference
+            ast.filter.And(
+                ast.filter.Any(Any(),
+                    ast.filter.All(Partial(ast.filter.Predicate, reverse=False),
+                        ast.filter.Or(
+                            Partial(ast.filter.StartsWith),
+                            ast.filter.EndsWith('bar'),
+                            Rest(Partial(ast.filter.Equals)),
+                            )
+                        )
+                    ),
+                ast.filter.Any(ns.bse.iso,
+                    ast.filter.And(
+                        Partial(ast.filter.GreaterThan, strict=True),
+                        Any(),
+                        Rest(),
+                        )
+                    ),
+                ast.filter.Any(ast.filter.OneOf(Rest()),
+                    Partial(ast.filter.Distance)
+                    ),
+                ),
+            ))
+        self.assertFalse(self.match(
+            # query
+            ast.filter.Any(ns.bse.tag,
+                ast.filter.And(
+                    ast.filter.Any(ns.bse.label, ast.filter.Equals('hello')),
+                    ast.filter.Any(ns.bse.collection, ast.filter.Is('http://example.com/col#123')),
+                    ast.filter.Not(ast.filter.Has(ns.bse.label)),
+                    )
+                ),
+            # reference
+            ast.filter.Any(ns.bse.tag,
+                ast.filter.And(
+                    Any(),
+                    ast.filter.Any(Partial(ast.filter.Predicate, reverse=True), # reverse mismatch
+                        Partial(ast.filter.Is)),
+                    ast.filter.Not(ast.filter.Has(Any(), Any())),
+                    )
+                )
+            ))
+
+    def test_parse_filter_expression(self):
+        # Any matches every filter expression
+        self.assertTrue(self.match._parse_filter_expression(
+            ast.filter.Not(ast.filter.FilterExpression()), Any()))
+        self.assertTrue(self.match._parse_filter_expression(
+            ast.filter.Has(ns.bse.filename), Any()))
+        self.assertTrue(self.match._parse_filter_expression(
+            ast.filter.Distance([1,2,3], 1.0), Any()))
+        self.assertTrue(self.match._parse_filter_expression(
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')), Any()))
+        self.assertTrue(self.match._parse_filter_expression(
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')), Any()))
+        self.assertTrue(self.match._parse_filter_expression(
+            ast.filter.And(ast.filter.Equals('hello')), Any()))
+        self.assertTrue(self.match._parse_filter_expression(
+            ast.filter.Or(ast.filter.Equals('hello')), Any()))
+        self.assertTrue(self.match._parse_filter_expression(
+            ast.filter.Equals('hello'), Any()))
+        self.assertTrue(self.match._parse_filter_expression(
+            ast.filter.Substring('hello'), Any()))
+        self.assertTrue(self.match._parse_filter_expression(
+            ast.filter.StartsWith('hello'), Any()))
+        self.assertTrue(self.match._parse_filter_expression(
+            ast.filter.EndsWith('hello'), Any()))
+        self.assertTrue(self.match._parse_filter_expression(
+            ast.filter.Is('hello'), Any()))
+        self.assertTrue(self.match._parse_filter_expression(
+            ast.filter.LessThan(3), Any()))
+        self.assertTrue(self.match._parse_filter_expression(
+            ast.filter.GreaterThan(3), Any()))
+        # Any matches invalid filter expressions
+        self.assertTrue(self.match._parse_filter_expression(
+            ast.filter.FilterExpression(), Any()))
+        # node must be an appropriate filter expression
+        self.assertRaises(errors.BackendError, self.match._parse_filter_expression,
+            ast.filter.FilterExpression(), ast.filter.FilterExpression())
+        self.assertRaises(errors.BackendError, self.match._parse_filter_expression,
+            1234, ast.filter.FilterExpression())
+
+    def test_parse_predicate_expression(self):
+        # Any matches every predicate expression
+        self.assertTrue(self.match._parse_predicate_expression(
+            ast.filter.Predicate(ns.bse.filename), Any()))
+        self.assertTrue(self.match._parse_predicate_expression(
+            ast.filter.OneOf(ns.bse.filename), Any()))
+        # Any matches invalid predicate expression
+        self.assertTrue(self.match._parse_predicate_expression(
+            ast.filter.FilterExpression(), Any()))
+        # node must be an appropriate predicate expression
+        self.assertRaises(errors.BackendError, self.match._parse_predicate_expression,
+            ast.filter.PredicateExpression(), ast.filter.PredicateExpression())
+        self.assertRaises(errors.BackendError, self.match._parse_predicate_expression,
+            1234, ast.filter.PredicateExpression())
+
+    def test_predicate(self):
+        # identical expressions match
+        self.assertTrue(self.match._predicate(
+            ast.filter.Predicate(ns.bse.filename, reverse=False),
+            ast.filter.Predicate(ns.bse.filename, reverse=False),
+            ))
+        # _predicate respects type
+        self.assertFalse(self.match._predicate(
+            ast.filter.Predicate(ns.bse.filename, reverse=False),
+            ast.filter.FilterExpression(),
+            ))
+        # _predicate respects predicate
+        self.assertFalse(self.match._predicate(
+            ast.filter.Predicate(ns.bse.filename, reverse=False),
+            ast.filter.Predicate(ns.bse.filesize, reverse=False),
+            ))
+        # _predicate respects reverse
+        self.assertFalse(self.match._predicate(
+            ast.filter.Predicate(ns.bse.filename, reverse=False),
+            ast.filter.Predicate(ns.bse.filename, reverse=True),
+            ))
+        # Partial requires ast.filter.Predicate
+        self.assertFalse(self.match._predicate(
+            ast.filter.Predicate(ns.bse.filename, reverse=False),
+            Partial(ast.filter.Equals),
+            ))
+        # predicate and reverse can be specified
+        self.assertTrue(self.match._predicate(
+            ast.filter.Predicate(ns.bse.filename, reverse=False),
+            Partial(ast.filter.Predicate, predicate=ns.bse.filename, reverse=False),
+            ))
+        self.assertFalse(self.match._predicate(
+            ast.filter.Predicate(ns.bse.filename, reverse=False),
+            Partial(ast.filter.Predicate, predicate=ns.bse.filesize, reverse=False),
+            ))
+        self.assertFalse(self.match._predicate(
+            ast.filter.Predicate(ns.bse.filename, reverse=False),
+            Partial(ast.filter.Predicate, predicate=ns.bse.filename, reverse=True),
+            ))
+        # predicate can remain unspecified
+        self.assertTrue(self.match._predicate(
+            ast.filter.Predicate(ns.bse.filename, reverse=False),
+            Partial(ast.filter.Predicate, reverse=False),
+            ))
+        self.assertTrue(self.match._predicate(
+            ast.filter.Predicate(ns.bse.filesize, reverse=False),
+            Partial(ast.filter.Predicate, reverse=False),
+            ))
+        self.assertFalse(self.match._predicate(
+            ast.filter.Predicate(ns.bse.filesize, reverse=False),
+            Partial(ast.filter.Predicate, reverse=True),
+            ))
+        # reverse can remain unspecified
+        self.assertTrue(self.match._predicate(
+            ast.filter.Predicate(ns.bse.filename, reverse=False),
+            Partial(ast.filter.Predicate, predicate=ns.bse.filename),
+            ))
+        self.assertTrue(self.match._predicate(
+            ast.filter.Predicate(ns.bse.filename, reverse=True),
+            Partial(ast.filter.Predicate, predicate=ns.bse.filename),
+            ))
+        self.assertFalse(self.match._predicate(
+            ast.filter.Predicate(ns.bse.filename, reverse=False),
+            Partial(ast.filter.Predicate, predicate=ns.bse.filesize),
+            ))
+
+    def test_one_of(self):
+        A = ast.filter.Predicate(ns.bse.filename)
+        B = ast.filter.Predicate(ns.bse.filesize)
+        C = ast.filter.Predicate(ns.bse.filename, reverse=True)
+        # identical expressions match
+        self.assertTrue(self.match._one_of(
+            ast.filter.OneOf(A, B),
+            ast.filter.OneOf(A, B),
+            ))
+        # _one_of respects type
+        self.assertFalse(self.match._one_of(
+            ast.filter.OneOf(A, B),
+            ast.filter.Predicate(ns.bse.filesize, reverse=True),
+            ))
+        # _one_of respects child expressions
+        self.assertFalse(self.match._one_of(
+            ast.filter.OneOf(A, B),
+            ast.filter.OneOf(A, C),
+            ))
+        self.assertFalse(self.match._one_of(
+            ast.filter.OneOf(A, B),
+            ast.filter.OneOf(A),
+            ))
+        self.assertFalse(self.match._one_of(
+            ast.filter.OneOf(A, B),
+            ast.filter.OneOf(A, B, C),
+            ))
+        self.assertTrue(self.match._one_of(
+            ast.filter.OneOf(A, B),
+            ast.filter.OneOf(B, A),
+            ))
+        self.assertTrue(self.match._one_of(
+            ast.filter.OneOf(A, B),
+            ast.filter.OneOf(A, Any()),
+            ))
+        self.assertTrue(self.match._one_of(
+            ast.filter.OneOf(A, B),
+            ast.filter.OneOf(B, Rest()),
+            ))
+
+    def test_branch(self):
+        # identical expressions match
+        self.assertTrue(self.match._branch(
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')),
+            ))
+        self.assertTrue(self.match._branch(
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')),
+            ))
+        # _agg respects type
+        self.assertFalse(self.match._branch(
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')),
+            ))
+        self.assertFalse(self.match._branch(
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')),
+            ))
+        self.assertFalse(self.match._branch(
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.Equals('hello'),
+            ))
+        self.assertFalse(self.match._branch(
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.Equals('hello'),
+            ))
+        # _agg respects predicate expression
+        self.assertTrue(self.match._branch(
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.Any(ast.filter.Predicate(ns.bse.filename), ast.filter.Equals('hello')),
+            ))
+        self.assertTrue(self.match._branch(
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.All(ast.filter.Predicate(ns.bse.filename), ast.filter.Equals('hello')),
+            ))
+        self.assertFalse(self.match._branch(
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.Any(ns.bse.filesize, ast.filter.Equals('hello')),
+            ))
+        self.assertFalse(self.match._branch(
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.All(ns.bse.filesize, ast.filter.Equals('hello')),
+            ))
+        self.assertFalse(self.match._branch(
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.Any(ast.filter.OneOf(ns.bse.filename), ast.filter.Equals('hello')),
+            ))
+        self.assertFalse(self.match._branch(
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.All(ast.filter.OneOf(ns.bse.filename), ast.filter.Equals('hello')),
+            ))
+        self.assertFalse(self.match._branch(
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.Any(ast.filter.Predicate(ns.bse.filename, reverse=True), ast.filter.Equals('hello')),
+            ))
+        self.assertFalse(self.match._branch(
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.All(ast.filter.Predicate(ns.bse.filename, reverse=True), ast.filter.Equals('hello')),
+            ))
+        self.assertTrue(self.match._branch(
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.Any(Any(), ast.filter.Equals('hello')),
+            ))
+        self.assertTrue(self.match._branch(
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.All(Any(), ast.filter.Equals('hello')),
+            ))
+        self.assertTrue(self.match._branch(
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.Any(Partial(ast.filter.Predicate), ast.filter.Equals('hello')),
+            ))
+        self.assertTrue(self.match._branch(
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.All(Partial(ast.filter.Predicate), ast.filter.Equals('hello')),
+            ))
+        # _agg respects filter expression
+        self.assertFalse(self.match._branch(
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.Any(ns.bse.filename, ast.filter.Substring('hello')),
+            ))
+        self.assertFalse(self.match._branch(
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.All(ns.bse.filename, ast.filter.Substring('hello')),
+            ))
+        self.assertFalse(self.match._branch(
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.Any(ns.bse.filename, ast.filter.Any(Any(), Any())),
+            ))
+        self.assertFalse(self.match._branch(
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.All(ns.bse.filename, ast.filter.All(Any(), Any())),
+            ))
+        self.assertTrue(self.match._branch(
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.Any(ns.bse.filename, Any()),
+            ))
+        self.assertTrue(self.match._branch(
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.All(ns.bse.filename, Any()),
+            ))
+        self.assertTrue(self.match._branch(
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.Any(ns.bse.filename, Partial(ast.filter.Equals)),
+            ))
+        self.assertTrue(self.match._branch(
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.All(ns.bse.filename, Partial(ast.filter.Equals)),
+            ))
+        self.assertFalse(self.match._branch(
+            ast.filter.Any(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.Any(ns.bse.filename, Partial(ast.filter.Equals, value='world')),
+            ))
+        self.assertFalse(self.match._branch(
+            ast.filter.All(ns.bse.filename, ast.filter.Equals('hello')),
+            ast.filter.All(ns.bse.filename, Partial(ast.filter.Equals, value='world')),
+            ))
+
+    def test_agg(self):
+        A = ast.filter.Equals('hello')
+        B = ast.filter.Equals('world')
+        C = ast.filter.Equals('foobar')
+        # identical expressions match
+        self.assertTrue(self.match._agg(
+            ast.filter.And(A, B),
+            ast.filter.And(A, B),
+            ))
+        self.assertTrue(self.match._agg(
+            ast.filter.Or(A, B),
+            ast.filter.Or(A, B),
+            ))
+        # _agg respects type
+        self.assertFalse(self.match._agg(
+            ast.filter.And(A, B),
+            ast.filter.Or(A, B),
+            ))
+        self.assertFalse(self.match._agg(
+            ast.filter.Or(A, B),
+            ast.filter.And(A, B),
+            ))
+        self.assertFalse(self.match._agg(
+            ast.filter.And(A, B),
+            ast.filter.Equals('hello'),
+            ))
+        self.assertFalse(self.match._agg(
+            ast.filter.Or(A, B),
+            ast.filter.Equals('hello'),
+            ))
+        # _agg respects child expressions
+        self.assertFalse(self.match._agg(
+            ast.filter.And(A, B),
+            ast.filter.And(A, ast.filter.Equals('bar')),
+            ))
+        self.assertFalse(self.match._agg(
+            ast.filter.Or(A, B),
+            ast.filter.Or(A, ast.filter.Equals('bar')),
+            ))
+        self.assertFalse(self.match._agg(
+            ast.filter.And(A, B),
+            ast.filter.And(A),
+            ))
+        self.assertFalse(self.match._agg(
+            ast.filter.Or(A, B),
+            ast.filter.Or(A),
+            ))
+        self.assertFalse(self.match._agg(
+            ast.filter.And(A, B),
+            ast.filter.And(A, B, C),
+            ))
+        self.assertFalse(self.match._agg(
+            ast.filter.Or(A, B),
+            ast.filter.Or(A, B, C),
+            ))
+        self.assertTrue(self.match._agg(
+            ast.filter.And(A, B),
+            ast.filter.And(B, A),
+            ))
+        self.assertTrue(self.match._agg(
+            ast.filter.Or(A, B),
+            ast.filter.Or(B, A),
+            ))
+        self.assertTrue(self.match._agg(
+            ast.filter.And(A, B),
+            ast.filter.And(A, Any()),
+            ))
+        self.assertTrue(self.match._agg(
+            ast.filter.Or(A, B),
+            ast.filter.Or(A, Any()),
+            ))
+        self.assertTrue(self.match._agg(
+            ast.filter.And(A, B),
+            ast.filter.And(B, Rest()),
+            ))
+        self.assertTrue(self.match._agg(
+            ast.filter.Or(A, B),
+            ast.filter.Or(B, Rest()),
+            ))
+
+    def test_not(self):
+        # identical expressions match
+        self.assertTrue(self.match._not(
+            ast.filter.Not(ast.filter.Equals('hello')),
+            ast.filter.Not(ast.filter.Equals('hello')),
+            ))
+        # _not respects type
+        self.assertFalse(self.match._not(
+            ast.filter.Not(ast.filter.Equals('hello')),
+            ast.filter.Equals('hello'),
+            ))
+        # _not respects child expression
+        self.assertFalse(self.match._not(
+            ast.filter.Not(ast.filter.Equals('hello')),
+            ast.filter.Not(ast.filter.Equals('world')),
+            ))
+        self.assertFalse(self.match._not(
+            ast.filter.Not(ast.filter.Equals('hello')),
+            ast.filter.Not(ast.filter.Substring('hello')),
+            ))
+        self.assertTrue(self.match._not(
+            ast.filter.Not(ast.filter.Equals('hello')),
+            ast.filter.Not(Any()),
+            ))
+
+    def test_has(self):
+        # identical expressions match
+        self.assertTrue(self.match._has(
+            ast.filter.Has(ns.bse.filesize),
+            ast.filter.Has(ns.bse.filesize),
+            ))
+        self.assertTrue(self.match._has(
+            ast.filter.Has(ns.bse.filesize, ast.filter.LessThan(3)),
+            ast.filter.Has(ns.bse.filesize, ast.filter.LessThan(3)),
+            ))
+        # _has respects type
+        self.assertFalse(self.match._has(
+            ast.filter.Has(ns.bse.filesize),
+            ast.filter.Equals('hello'),
+            ))
+        self.assertFalse(self.match._has(
+            ast.filter.Has(ns.bse.filesize),
+            ast.filter.Equals('hello'),
+            ))
+        # _has respects predicate
+        self.assertFalse(self.match._has(
+            ast.filter.Has(ns.bse.filesize, ast.filter.LessThan(3)),
+            ast.filter.Has(ns.bse.iso, ast.filter.LessThan(3)),
+            ))
+        self.assertTrue(self.match._has(
+            ast.filter.Has(ns.bse.filesize, ast.filter.LessThan(3)),
+            ast.filter.Has(Any(), ast.filter.LessThan(3)),
+            ))
+        self.assertTrue(self.match._has(
+            ast.filter.Has(ns.bse.filesize, ast.filter.LessThan(3)),
+            ast.filter.Has(Partial(ast.filter.Predicate), ast.filter.LessThan(3)),
+            ))
+        # _has respects count
+        self.assertFalse(self.match._has(
+            ast.filter.Has(ns.bse.filesize, ast.filter.LessThan(3)),
+            ast.filter.Has(ns.bse.filesize, ast.filter.GreaterThan(3)),
+            ))
+        self.assertFalse(self.match._has(
+            ast.filter.Has(ns.bse.filesize, ast.filter.LessThan(3)),
+            ast.filter.Has(ns.bse.filesize, ast.filter.LessThan(5)),
+            ))
+        self.assertTrue(self.match._has(
+            ast.filter.Has(ns.bse.filesize, ast.filter.LessThan(3)),
+            ast.filter.Has(ns.bse.filesize, Any()),
+            ))
+        self.assertTrue(self.match._has(
+            ast.filter.Has(ns.bse.filesize, ast.filter.LessThan(3)),
+            ast.filter.Has(ns.bse.filesize, Partial(ast.filter.LessThan)),
+            ))
+
+    def test_distance(self):
+        # identical expressions match
+        self.assertTrue(self.match._distance(
+            ast.filter.Distance([1,2,3], 5, True),
+            ast.filter.Distance([1,2,3], 5, True),
+            ))
+        # _distance respects type
+        self.assertFalse(self.match._distance(
+            ast.filter.Distance([1,2,3], 5, True),
+            ast.filter.Equals('hello'),
+            ))
+        self.assertFalse(self.match._distance(
+            ast.filter.Distance([1,2,3], 5, True),
+            Partial(ast.filter.Equals),
+            ))
+        # _distance respects reference value
+        self.assertFalse(self.match._distance(
+            ast.filter.Distance([1,2,3], 5, True),
+            ast.filter.Distance([3,2,1], 5, True),
+            ))
+        self.assertTrue(self.match._distance(
+            ast.filter.Distance([1,2,3], 5, True),
+            Partial(ast.filter.Distance, threshold=5, strict=True),
+            ))
+        self.assertTrue(self.match._distance(
+            ast.filter.Distance([1,2,3], 5, True),
+            Partial(ast.filter.Distance, reference=[1,2,3], threshold=5, strict=True),
+            ))
+        self.assertFalse(self.match._distance(
+            ast.filter.Distance([1,2,3], 5, True),
+            Partial(ast.filter.Distance, reference=[3,2,1], threshold=5, strict=True),
+            ))
+        # _distance respects threshold
+        self.assertFalse(self.match._distance(
+            ast.filter.Distance([1,2,3], 5, True),
+            ast.filter.Distance([1,2,3], 8, True),
+            ))
+        self.assertTrue(self.match._distance(
+            ast.filter.Distance([1,2,3], 5, True),
+            Partial(ast.filter.Distance, reference=[1,2,3], strict=True),
+            ))
+        self.assertTrue(self.match._distance(
+            ast.filter.Distance([1,2,3], 5, True),
+            Partial(ast.filter.Distance, reference=[1,2,3], threshold=5, strict=True),
+            ))
+        self.assertFalse(self.match._distance(
+            ast.filter.Distance([1,2,3], 5, True),
+            Partial(ast.filter.Distance, reference=[1,2,3], threshold=8, strict=True),
+            ))
+        # _distance respects strict
+        self.assertFalse(self.match._distance(
+            ast.filter.Distance([1,2,3], 5, True),
+            ast.filter.Distance([1,2,3], 5, False),
+            ))
+        self.assertTrue(self.match._distance(
+            ast.filter.Distance([1,2,3], 5, True),
+            Partial(ast.filter.Distance, reference=[1,2,3], threshold=5),
+            ))
+        self.assertTrue(self.match._distance(
+            ast.filter.Distance([1,2,3], 5, True),
+            Partial(ast.filter.Distance, reference=[1,2,3], threshold=5, strict=True),
+            ))
+        self.assertFalse(self.match._distance(
+            ast.filter.Distance([1,2,3], 5, True),
+            Partial(ast.filter.Distance, reference=[1,2,3], threshold=5, strict=False),
+            ))
+
+    def test_value(self):
+        # identical expressions match
+        self.assertTrue(self.match._value(ast.filter.Equals('hello'), ast.filter.Equals('hello')))
+        self.assertTrue(self.match._value(ast.filter.Substring('hello'), ast.filter.Substring('hello')))
+        self.assertTrue(self.match._value(ast.filter.StartsWith('hello'), ast.filter.StartsWith('hello')))
+        self.assertTrue(self.match._value(ast.filter.EndsWith('hello'), ast.filter.EndsWith('hello')))
+        self.assertTrue(self.match._value(ast.filter.Is('hello'), ast.filter.Is('hello')))
+        # _value respects type
+        self.assertFalse(self.match._value(ast.filter.Equals('hello'), ast.filter.Is('hello')))
+        self.assertFalse(self.match._value(ast.filter.Substring('hello'), ast.filter.Is('hello')))
+        self.assertFalse(self.match._value(ast.filter.StartsWith('hello'), ast.filter.Is('hello')))
+        self.assertFalse(self.match._value(ast.filter.EndsWith('hello'), ast.filter.Is('hello')))
+        self.assertFalse(self.match._value(ast.filter.Is('hello'), ast.filter.Equals('hello')))
+        # _value respects value
+        self.assertFalse(self.match._value(ast.filter.Equals('hello'), ast.filter.Equals('world')))
+        self.assertFalse(self.match._value(ast.filter.Substring('hello'), ast.filter.Substring('world')))
+        self.assertFalse(self.match._value(ast.filter.StartsWith('hello'), ast.filter.StartsWith('world')))
+        self.assertFalse(self.match._value(ast.filter.EndsWith('hello'), ast.filter.EndsWith('world')))
+        self.assertFalse(self.match._value(ast.filter.Is('hello'), ast.filter.Is('world')))
+        # Partial requires correct type
+        self.assertFalse(self.match._value(ast.filter.Equals('hello'), Partial(ast.filter.Is)))
+        self.assertFalse(self.match._value(ast.filter.Substring('hello'), Partial(ast.filter.Is)))
+        self.assertFalse(self.match._value(ast.filter.StartsWith('hello'), Partial(ast.filter.Is)))
+        self.assertFalse(self.match._value(ast.filter.EndsWith('hello'), Partial(ast.filter.Is)))
+        self.assertFalse(self.match._value(ast.filter.Is('hello'), Partial(ast.filter.Equals)))
+        # value can be specified
+        self.assertTrue(self.match._value(ast.filter.Equals('hello'), Partial(ast.filter.Equals, value='hello')))
+        self.assertFalse(self.match._value(ast.filter.Equals('hello'), Partial(ast.filter.Equals, value='world')))
+        self.assertTrue(self.match._value(ast.filter.Substring('hello'), Partial(ast.filter.Substring, value='hello')))
+        self.assertFalse(self.match._value(ast.filter.Substring('hello'), Partial(ast.filter.Substring, value='world')))
+        self.assertTrue(self.match._value(ast.filter.StartsWith('hello'), Partial(ast.filter.StartsWith, value='hello')))
+        self.assertFalse(self.match._value(ast.filter.StartsWith('hello'), Partial(ast.filter.StartsWith, value='world')))
+        self.assertTrue(self.match._value(ast.filter.EndsWith('hello'), Partial(ast.filter.EndsWith, value='hello')))
+        self.assertFalse(self.match._value(ast.filter.EndsWith('hello'), Partial(ast.filter.EndsWith, value='world')))
+        self.assertTrue(self.match._value(ast.filter.Is('hello'), Partial(ast.filter.Is, value='hello')))
+        self.assertFalse(self.match._value(ast.filter.Is('hello'), Partial(ast.filter.Is, value='world')))
+        # value can remain unspecified
+        self.assertTrue(self.match._value(ast.filter.Equals('hello'), Partial(ast.filter.Equals)))
+        self.assertTrue(self.match._value(ast.filter.Substring('hello'), Partial(ast.filter.Substring)))
+        self.assertTrue(self.match._value(ast.filter.StartsWith('hello'), Partial(ast.filter.StartsWith)))
+        self.assertTrue(self.match._value(ast.filter.EndsWith('hello'), Partial(ast.filter.EndsWith)))
+        self.assertTrue(self.match._value(ast.filter.Is('hello'), Partial(ast.filter.Is)))
+
+    def test_bounded(self):
+        # identical expressions match
+        self.assertTrue(self.match._bounded(
+            ast.filter.LessThan(threshold=3, strict=False),
+            ast.filter.LessThan(threshold=3, strict=False),
+            ))
+        self.assertTrue(self.match._bounded(
+            ast.filter.GreaterThan(threshold=3, strict=False),
+            ast.filter.GreaterThan(threshold=3, strict=False),
+            ))
+        # _bounded respects type
+        self.assertFalse(self.match._bounded(
+            ast.filter.LessThan(threshold=3, strict=False),
+            ast.filter.GreaterThan(threshold=3, strict=False),
+            ))
+        self.assertFalse(self.match._bounded(
+            ast.filter.GreaterThan(threshold=3, strict=False),
+            ast.filter.LessThan(threshold=3, strict=False),
+            ))
+        # _bounded respects threshold
+        self.assertFalse(self.match._bounded(
+            ast.filter.LessThan(threshold=3, strict=False),
+            ast.filter.LessThan(threshold=4, strict=False),
+            ))
+        self.assertFalse(self.match._bounded(
+            ast.filter.GreaterThan(threshold=3, strict=False),
+            ast.filter.GreaterThan(threshold=4, strict=False),
+            ))
+        # _bounded respects strict
+        self.assertFalse(self.match._bounded(
+            ast.filter.LessThan(threshold=3, strict=False),
+            ast.filter.LessThan(threshold=3, strict=True),
+            ))
+        self.assertFalse(self.match._bounded(
+            ast.filter.GreaterThan(threshold=3, strict=False),
+            ast.filter.GreaterThan(threshold=3, strict=True),
+            ))
+        # Partial requires correct type
+        self.assertFalse(self.match._bounded(
+            ast.filter.LessThan(threshold=3, strict=False),
+            Partial(ast.filter.GreaterThan),
+            ))
+        self.assertFalse(self.match._bounded(
+            ast.filter.GreaterThan(threshold=3, strict=False),
+            Partial(ast.filter.LessThan),
+            ))
+        # threshold and strict can be specified
+        self.assertTrue(self.match._bounded(
+            ast.filter.LessThan(threshold=3, strict=False),
+            Partial(ast.filter.LessThan, threshold=3, strict=False),
+            ))
+        self.assertTrue(self.match._bounded(
+            ast.filter.GreaterThan(threshold=3, strict=False),
+            Partial(ast.filter.GreaterThan, threshold=3, strict=False),
+            ))
+        self.assertFalse(self.match._bounded(
+            ast.filter.LessThan(threshold=3, strict=False),
+            Partial(ast.filter.LessThan, threshold=4, strict=False),
+            ))
+        self.assertFalse(self.match._bounded(
+            ast.filter.GreaterThan(threshold=3, strict=False),
+            Partial(ast.filter.GreaterThan, threshold=4, strict=False),
+            ))
+        self.assertFalse(self.match._bounded(
+            ast.filter.LessThan(threshold=3, strict=False),
+            Partial(ast.filter.LessThan, threshold=3, strict=True),
+            ))
+        self.assertFalse(self.match._bounded(
+            ast.filter.GreaterThan(threshold=3, strict=False),
+            Partial(ast.filter.GreaterThan, threshold=3, strict=True),
+            ))
+        # threshold can remain unspecified
+        self.assertTrue(self.match._bounded(
+            ast.filter.LessThan(threshold=3, strict=False),
+            Partial(ast.filter.LessThan, strict=False),
+            ))
+        self.assertTrue(self.match._bounded(
+            ast.filter.GreaterThan(threshold=3, strict=False),
+            Partial(ast.filter.GreaterThan, strict=False),
+            ))
+        self.assertFalse(self.match._bounded(
+            ast.filter.LessThan(threshold=3, strict=False),
+            Partial(ast.filter.LessThan, strict=True),
+            ))
+        self.assertFalse(self.match._bounded(
+            ast.filter.GreaterThan(threshold=3, strict=False),
+            Partial(ast.filter.GreaterThan, strict=True),
+            ))
+        # strict can remain unspecified
+        self.assertTrue(self.match._bounded(
+            ast.filter.LessThan(threshold=3, strict=False),
+            Partial(ast.filter.LessThan, threshold=3),
+            ))
+        self.assertTrue(self.match._bounded(
+            ast.filter.GreaterThan(threshold=3, strict=False),
+            Partial(ast.filter.GreaterThan, threshold=3),
+            ))
+        self.assertFalse(self.match._bounded(
+            ast.filter.LessThan(threshold=3, strict=False),
+            Partial(ast.filter.LessThan, threshold=4),
+            ))
+        self.assertFalse(self.match._bounded(
+            ast.filter.GreaterThan(threshold=3, strict=False),
+            Partial(ast.filter.GreaterThan, threshold=4),
+            ))
+
+
+## main ##
+
+if __name__ == '__main__':
+    unittest.main()
+
+## EOF ##
diff --git a/test/query/test_validator.py b/test/query/test_validator.py
index dc9d913..fec3d23 100644
--- a/test/query/test_validator.py
+++ b/test/query/test_validator.py
@@ -14,7 +14,7 @@ from bsfs.query import ast
 from bsfs.utils import errors
 
 # objects to test
-from bsfs.query.validator import Filter
+from bsfs.query.validator import Filter, Fetch
 
 
 ## code ##
@@ -286,6 +286,219 @@ class TestFilter(unittest.TestCase):
         self.assertIsNone(self.validate._distance(self.schema.literal(ns.bsfs.Colors), ast.filter.Distance([1,2,3,4,5], 1, False)))
 
 
+class TestFetch(unittest.TestCase):
+    def setUp(self):
+        self.schema = _schema.from_string('''
+            prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#>
+            prefix xsd: <http://www.w3.org/2001/XMLSchema#>
+
+            prefix bsfs: <http://bsfs.ai/schema/>
+            prefix bse: <http://bsfs.ai/schema/Entity#>
+
+            bsfs:Entity rdfs:subClassOf bsfs:Node .
+            bsfs:Tag rdfs:subClassOf bsfs:Node .
+            xsd:string rdfs:subClassOf bsfs:Literal .
+
+            bse:filename rdfs:subClassOf bsfs:Predicate ;
+                rdfs:domain bsfs:Node ;
+                rdfs:range xsd:string .
+
+            bse:tag rdfs:subClassOf bsfs:Predicate ;
+                rdfs:domain bsfs:Entity ;
+                rdfs:range bsfs:Tag .
+
+            bse:label rdfs:subClassOf bsfs:Predicate ;
+                rdfs:domain bsfs:Tag ;
+                rdfs:range xsd:string .
+
+            ''')
+        self.validate = Fetch(self.schema)
+
+    def test_call(self):
+        # call accepts correct expressions
+        self.assertTrue(self.validate(self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Fetch(ns.bse.tag, ast.fetch.Value(ns.bse.label, 'value'))))
+        self.assertTrue(self.validate(self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Fetch(ns.bse.tag, ast.fetch.This('this'))))
+        self.assertTrue(self.validate(self.schema.node(ns.bsfs.Entity),
+            ast.fetch.This('this')))
+        self.assertTrue(self.validate(self.schema.node(ns.bsfs.Entity),
+            ast.fetch.All(ast.fetch.This('this'), ast.fetch.Node(ns.bse.tag, 'node'), ast.fetch.Value(ns.bse.filename, 'value'))))
+        # type must be a Node
+        self.assertRaises(TypeError, self.validate, 1234, ast.fetch.This('this'))
+        self.assertRaises(TypeError, self.validate, 'foobar', ast.fetch.This('this'))
+        self.assertRaises(TypeError, self.validate, self.schema.literal(ns.bsfs.Literal), ast.fetch.This('this'))
+        # type must be in the schema
+        self.assertRaises(errors.ConsistencyError, self.validate, self.schema.node(ns.bsfs.Node).child(ns.bsfs.Invalid),
+            ast.fetch.FetchExpression())
+        # expression must be a fetch expression
+        self.assertRaises(TypeError, self.validate, self.schema.node(ns.bsfs.Entity), 1234)
+        self.assertRaises(TypeError, self.validate, self.schema.node(ns.bsfs.Entity), 'hello')
+        self.assertRaises(TypeError, self.validate, self.schema.node(ns.bsfs.Entity), ast.filter.FilterExpression())
+        # expression must be valid
+        self.assertRaises(errors.ConsistencyError, self.validate, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Fetch(ns.bse.tag, ast.fetch.Node(ns.bse.label, 'node')))
+        self.assertRaises(errors.ConsistencyError, self.validate, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Value(ns.bse.tag, 'value'))
+
+    def test_routing(self):
+        # Node passes _branch, _named, and _node checks
+        self.assertRaises(errors.ConsistencyError, self.validate._parse_fetch_expression, self.schema.node(ns.bsfs.Node),
+            ast.fetch.Node(ns.bse.tag, 'node')) # fails in _branch
+        self.assertRaises(errors.BackendError, self.validate._parse_fetch_expression, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Node(ns.bse.tag, '')) # fails in _named
+        self.assertRaises(errors.ConsistencyError, self.validate._parse_fetch_expression, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Node(ns.bse.label, 'node')) # fails in _node
+        # Value passes _branch, _named, and _value checks
+        self.assertRaises(errors.ConsistencyError, self.validate._parse_fetch_expression, self.schema.node(ns.bsfs.Node),
+            ast.fetch.Value(ns.bse.label, 'value')) # fails in _branch
+        self.assertRaises(errors.BackendError, self.validate._parse_fetch_expression, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Value(ns.bse.filename, '')) # fails in _named
+        self.assertRaises(errors.ConsistencyError, self.validate._parse_fetch_expression, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Value(ns.bse.tag, 'value')) # fails in _value
+        # Fetch passes _branch and _fetch checks
+        self.assertRaises(errors.ConsistencyError, self.validate._parse_fetch_expression, self.schema.node(ns.bsfs.Node),
+            ast.fetch.Fetch(ns.bse.tag, ast.fetch.This('this'))) # fails in _branch
+        self.assertRaises(errors.ConsistencyError, self.validate._parse_fetch_expression, self.schema.node(ns.bsfs.Node),
+            ast.fetch.Fetch(ns.bse.filename, ast.fetch.This('this'))) # fails in _fetch
+        # invalid expressions cannot be parsed
+        type_ = self.schema.node(ns.bsfs.Node)
+        self.assertRaises(errors.BackendError, self.validate._parse_fetch_expression, type_,
+            ast.filter.FilterExpression())
+        self.assertRaises(errors.BackendError, self.validate._parse_fetch_expression, type_,
+            1234)
+        self.assertRaises(errors.BackendError, self.validate._parse_fetch_expression, type_,
+            'hello world')
+
+    def test_all(self):
+        # all accepts correct expressions
+        self.assertIsNone(self.validate._all(self.schema.node(ns.bsfs.Entity),
+            ast.fetch.All(ast.fetch.Value(ns.bse.filename, 'value'), ast.fetch.Node(ns.bse.tag, 'node'))))
+        # child expressions must be valid
+        self.assertRaises(errors.ConsistencyError, self.validate._all, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.All(ast.fetch.Value(ns.bse.tag, 'value')))
+        self.assertRaises(errors.ConsistencyError, self.validate._all, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.All(ast.fetch.Value(ns.bse.filename, 'value'), ast.fetch.Node(ns.bse.filename, 'node')))
+        self.assertRaises(errors.ConsistencyError, self.validate._all, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.All(ast.fetch.Value(ns.bse.tag, 'value'), ast.fetch.Node(ns.bse.tag, 'node')))
+        self.assertRaises(errors.ConsistencyError, self.validate._all, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.All(ast.fetch.Value(ns.bse.tag, 'value'), ast.fetch.Node(ns.bse.filename, 'node')))
+
+    def test_branch(self):
+        # branch accepts correct expressions
+        self.assertIsNone(self.validate._branch(self.schema.node(ns.bsfs.Entity),
+            ast.fetch._Branch(ns.bse.filename)))
+        self.assertIsNone(self.validate._branch(self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Fetch(ns.bse.tag, ast.fetch.This('this'))))
+        self.assertIsNone(self.validate._branch(self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Value(ns.bse.filename, 'value')))
+        self.assertIsNone(self.validate._branch(self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Node(ns.bse.tag, 'node')))
+        # type must be a node
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.literal(ns.bsfs.Literal),
+            ast.fetch._Branch(ns.bse.filename))
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.literal(ns.bsfs.Literal),
+            ast.fetch.Fetch(ns.bse.tag, ast.fetch.This('this')))
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.literal(ns.bsfs.Literal),
+            ast.fetch.Value(ns.bse.filename, 'value'))
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.literal(ns.bsfs.Literal),
+            ast.fetch.Node(ns.bse.tag, 'node'))
+        # type must be in the schema
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.node(ns.bsfs.Node).child(ns.bsfs.Invalid),
+            ast.fetch._Branch(ns.bse.filename))
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.node(ns.bsfs.Node).child(ns.bsfs.Invalid),
+            ast.fetch.Fetch(ns.bse.tag, ast.fetch.This('this')))
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.node(ns.bsfs.Node).child(ns.bsfs.Invalid),
+            ast.fetch.Value(ns.bse.filename, 'value'))
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.node(ns.bsfs.Node).child(ns.bsfs.Invalid),
+            ast.fetch.Node(ns.bse.tag, 'node'))
+        # predicate must be in the schema
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.node(ns.bsfs.Entity),
+            ast.fetch._Branch(ns.bse.invalid))
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Fetch(ns.bse.invalid, ast.fetch.This('this')))
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Value(ns.bse.invalid, 'value'))
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Node(ns.bse.invalid, 'node'))
+        # predicate's domain must be related to the type
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.node(ns.bsfs.Entity),
+            ast.fetch._Branch(ns.bse.label))
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Fetch(ns.bse.label, ast.fetch.This('this')))
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Node(ns.bse.label, 'node'))
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Value(ns.bse.label, 'value'))
+        # predicate's domain cannot be a supertype
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.node(ns.bsfs.Node),
+            ast.fetch._Branch(ns.bse.tag))
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.node(ns.bsfs.Node),
+            ast.fetch.Fetch(ns.bse.tag, ast.fetch.This('this')))
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.node(ns.bsfs.Node),
+            ast.fetch.Node(ns.bse.tag, 'node'))
+        self.assertRaises(errors.ConsistencyError, self.validate._branch, self.schema.node(ns.bsfs.Node),
+            ast.fetch.Value(ns.bse.tag, 'value'))
+        # predicate's domain can be a subtype
+        self.assertIsNone(self.validate._branch(self.schema.node(ns.bsfs.Entity),
+            ast.fetch._Branch(ns.bse.filename)))
+        self.assertIsNone(self.validate._branch(self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Value(ns.bse.filename, 'value')))
+
+    def test_fetch(self):
+        # fetch accepts correct expressions
+        self.assertIsNone(self.validate._fetch(self.schema.node(ns.bsfs.Node),
+            ast.fetch.Fetch(ns.bse.tag, ast.fetch.Value(ns.bse.label, 'value'))))
+        # range must be a node
+        self.assertRaises(errors.ConsistencyError, self.validate._fetch, self.schema.node(ns.bsfs.Node),
+            ast.fetch.Fetch(ns.bse.filename, ast.fetch.This('this')))
+        # child expression must be valid
+        self.assertRaises(errors.ConsistencyError, self.validate._fetch, self.schema.node(ns.bsfs.Node),
+            ast.fetch.Fetch(ns.bse.tag, ast.fetch.Node(ns.bse.label, 'node')))
+
+    def test_named(self):
+        # named accepts correct expressions
+        self.assertIsNone(self.validate._named(self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Node(ns.bse.tag, 'node')))
+        self.assertIsNone(self.validate._named(self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Value(ns.bse.filename, 'value')))
+        # name must be non-empty
+        self.assertRaises(errors.BackendError, self.validate._named, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Node(ns.bse.tag, ''))
+        self.assertRaises(errors.BackendError, self.validate._named, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Value(ns.bse.filename, ''))
+
+    def test_node(self):
+        # node accepts correct expressions
+        self.assertIsNone(self.validate._node(self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Node(ns.bse.tag, 'node')))
+        # range must be a node
+        self.assertRaises(errors.ConsistencyError, self.validate._node, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Node(ns.bse.filename, 'node'))
+
+    def test_value(self):
+        # value accepts correct expressions
+        self.assertIsNone(self.validate._value(self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Value(ns.bse.filename, 'value')))
+        # range must be a literal
+        self.assertRaises(errors.ConsistencyError, self.validate._value, self.schema.node(ns.bsfs.Entity),
+            ast.fetch.Value(ns.bse.tag, 'value'))
+
+    def test_this(self):
+        # this accepts correct expressions
+        self.assertIsNone(self.validate._this(self.schema.node(ns.bsfs.Entity), ast.fetch.This('this')))
+        # type must be a node
+        self.assertRaises(errors.ConsistencyError, self.validate._this, self.schema.literal(ns.bsfs.Literal),
+            ast.fetch.This('this'))
+        self.assertRaises(errors.ConsistencyError, self.validate._this, self.schema.predicate(ns.bsfs.Predicate),
+            ast.fetch.This('this'))
+        # type must be in the schema
+        self.assertRaises(errors.ConsistencyError, self.validate._this, self.schema.node(ns.bsfs.Node).child(ns.bsfs.Invalid),
+            ast.fetch.This('this'))
+        # name must be non-empty
+        self.assertRaises(errors.BackendError, self.validate._this, self.schema.node(ns.bsfs.Entity), ast.fetch.This(''))
+
+
 ## main ##
 
 if __name__ == '__main__':