- The "primaryjoin" model has been stretched a bit further to allow

a join condition that is strictly from a single column to itself,
translated through some kind of SQL function or expression.  This
is kind of experimental, but the first proof of concept is a
"materialized path" join condition where a path string is compared
to itself using "like".   The :meth:`.Operators.like` operator has
also been added to the list of valid operators to use in a primaryjoin
condition.  fixes #3029

6 files changed, 301 insertions, 29 deletions

diff --git a/doc/build/changelog/changelog_09.rst b/doc/build/changelog/changelog_09.rst
index 0aae51810..054e41efb 100644
--- a/doc/build/changelog/changelog_09.rst
+++ b/doc/build/changelog/changelog_09.rst
@@ -15,6 +15,19 @@
     :version: 0.9.5
 
     .. change::
+        :tags: feature, orm
+        :tickets: 3029
+
+        The "primaryjoin" model has been stretched a bit further to allow
+        a join condition that is strictly from a single column to itself,
+        translated through some kind of SQL function or expression.  This
+        is kind of experimental, but the first proof of concept is a
+        "materialized path" join condition where a path string is compared
+        to itself using "like".   The :meth:`.Operators.like` operator has
+        also been added to the list of valid operators to use in a primaryjoin
+        condition.
+
+    .. change::
         :tags: feature, sql
         :tickets: 3028
 
diff --git a/doc/build/orm/relationships.rst b/doc/build/orm/relationships.rst
index afe5b4e79..32f056456 100644
--- a/doc/build/orm/relationships.rst
+++ b/doc/build/orm/relationships.rst
@@ -1157,6 +1157,48 @@ Will render as::
    flag to assist in the creation of :func:`.relationship` constructs using
    custom operators.
 
+Non-relational Comparisons / Materialized Path
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+.. warning::  this section details an experimental feature.
+
+Using custom expressions means we can produce unorthodox join conditions that
+don't obey the usual primary/foreign key model.  One such example is the
+materialized path pattern, where we compare strings for overlapping path tokens
+in order to produce a tree structure.
+
+Through careful use of :func:`.foreign` and :func:`.remote`, we can build
+a relationship that effectively produces a rudimentary materialized path
+system.   Essentially, when :func:`.foreign` and :func:`.remote` are
+on the *same* side of the comparison expression, the relationship is considered
+to be "one to many"; when they are on *different* sides, the relationship
+is considered to be "many to one".   For the comparison we'll use here,
+we'll be dealing with collections so we keep things configured as "one to many"::
+
+    class Element(Base):
+        __tablename__ = 'element'
+
+        path = Column(String, primary_key=True)
+
+        descendants = relationship('Element',
+                               primaryjoin=
+                                    remote(foreign(path)).like(
+                                            path.concat('/%')),
+                               viewonly=True,
+                               order_by=path)
+
+Above, if given an ``Element`` object with a path attribute of ``"/foo/bar2"``,
+we seek for a load of ``Element.descendants`` to look like::
+
+    SELECT element.path AS element_path
+    FROM element
+    WHERE element.path LIKE ('/foo/bar2' || '/%') ORDER BY element.path
+
+.. versionadded:: 0.9.5 Support has been added to allow a single-column
+   comparison to itself within a primaryjoin condition, as well as for
+   primaryjoin conditions that use :meth:`.Operators.like` as the comparison
+   operator.
+
 .. _self_referential_many_to_many:
 
 Self-Referential Many-to-Many Relationship
diff --git a/lib/sqlalchemy/orm/relationships.py b/lib/sqlalchemy/orm/relationships.py
index 311fba478..0d9ee87b3 100644
--- a/lib/sqlalchemy/orm/relationships.py
+++ b/lib/sqlalchemy/orm/relationships.py
@@ -12,7 +12,7 @@ SQL annotation and aliasing behavior focused on the `primaryjoin`
 and `secondaryjoin` aspects of :func:`.relationship`.
 
 """
-
+from __future__ import absolute_import
 from .. import sql, util, exc as sa_exc, schema, log
 
 from .util import CascadeOptions, _orm_annotate, _orm_deannotate
@@ -27,6 +27,7 @@ from ..sql import operators, expression, visitors
 from .interfaces import MANYTOMANY, MANYTOONE, ONETOMANY, StrategizedProperty, PropComparator
 from ..inspection import inspect
 from . import mapper as mapperlib
+import collections
 
 def remote(expr):
     """Annotate a portion of a primaryjoin expression
@@ -2391,16 +2392,38 @@ class JoinCondition(object):
 
             if onetomany_fk and manytoone_fk:
                 # fks on both sides.  test for overlap of local/remote
-                # with foreign key
-                self_equated = self.remote_columns.intersection(
-                                        self.local_columns
-                                    )
-                onetomany_local = self.remote_columns.\
-                                    intersection(self.foreign_key_columns).\
-                                    difference(self_equated)
-                manytoone_local = self.local_columns.\
-                                    intersection(self.foreign_key_columns).\
-                                    difference(self_equated)
+                # with foreign key.
+                # we will gather columns directly from their annotations
+                # without deannotating, so that we can distinguish on a column
+                # that refers to itself.
+
+                # 1. columns that are both remote and FK suggest
+                # onetomany.
+                onetomany_local = self._gather_columns_with_annotation(
+                                        self.primaryjoin, "remote", "foreign")
+
+                # 2. columns that are FK but are not remote (e.g. local)
+                # suggest manytoone.
+                manytoone_local = set([c for c in
+                                        self._gather_columns_with_annotation(
+                                                    self.primaryjoin,
+                                                    "foreign")
+                                        if "remote" not in c._annotations])
+
+                # 3. if both collections are present, remove columns that
+                # refer to themselves.  This is for the case of
+                # and_(Me.id == Me.remote_id, Me.version == Me.version)
+                if onetomany_local and manytoone_local:
+                    self_equated = self.remote_columns.intersection(
+                                            self.local_columns
+                                        )
+                    onetomany_local = onetomany_local.difference(self_equated)
+                    manytoone_local = manytoone_local.difference(self_equated)
+
+                # at this point, if only one or the other collection is
+                # present, we know the direction, otherwise it's still
+                # ambiguous.
+
                 if onetomany_local and not manytoone_local:
                     self.direction = ONETOMANY
                 elif manytoone_local and not onetomany_local:
@@ -2585,46 +2608,40 @@ class JoinCondition(object):
 
     def create_lazy_clause(self, reverse_direction=False):
         binds = util.column_dict()
-        lookup = util.column_dict()
+        lookup = collections.defaultdict(list)
         equated_columns = util.column_dict()
-        being_replaced = set()
 
         if reverse_direction and self.secondaryjoin is None:
             for l, r in self.local_remote_pairs:
-                _list = lookup.setdefault(r, [])
-                _list.append((r, l))
+                lookup[r].append((r, l))
                 equated_columns[l] = r
         else:
             # replace all "local side" columns, which is
             # anything that isn't marked "remote"
-            being_replaced.update(self.local_columns)
             for l, r in self.local_remote_pairs:
-                _list = lookup.setdefault(l, [])
-                _list.append((l, r))
+                lookup[l].append((l, r))
                 equated_columns[r] = l
 
         def col_to_bind(col):
-            if col in being_replaced or col in lookup:
+            if (reverse_direction and col in lookup) or \
+                (not reverse_direction and "local" in col._annotations):
                 if col in lookup:
                     for tobind, equated in lookup[col]:
                         if equated in binds:
                             return None
-                else:
-                    assert not reverse_direction
                 if col not in binds:
                     binds[col] = sql.bindparam(
                         None, None, type_=col.type, unique=True)
                 return binds[col]
             return None
 
-        lazywhere = self.deannotated_primaryjoin
-
-        if self.deannotated_secondaryjoin is None or not reverse_direction:
+        lazywhere = self.primaryjoin
+        if self.secondaryjoin is None or not reverse_direction:
             lazywhere = visitors.replacement_traverse(
                                             lazywhere, {}, col_to_bind)
 
-        if self.deannotated_secondaryjoin is not None:
-            secondaryjoin = self.deannotated_secondaryjoin
+        if self.secondaryjoin is not None:
+            secondaryjoin = self.secondaryjoin
             if reverse_direction:
                 secondaryjoin = visitors.replacement_traverse(
                                             secondaryjoin, {}, col_to_bind)
@@ -2632,6 +2649,9 @@ class JoinCondition(object):
 
         bind_to_col = dict((binds[col].key, col) for col in binds)
 
+        # this is probably not necessary
+        lazywhere = _deep_deannotate(lazywhere)
+
         return lazywhere, bind_to_col, equated_columns
 
 class _ColInAnnotations(object):
diff --git a/lib/sqlalchemy/sql/operators.py b/lib/sqlalchemy/sql/operators.py
index bafe00979..402610fa5 100644
--- a/lib/sqlalchemy/sql/operators.py
+++ b/lib/sqlalchemy/sql/operators.py
@@ -782,7 +782,7 @@ def nullslast_op(a):
 
 _commutative = set([eq, ne, add, mul])
 
-_comparison = set([eq, ne, lt, gt, ge, le, between_op])
+_comparison = set([eq, ne, lt, gt, ge, le, between_op, like_op])
 
 
 def is_comparison(op):
diff --git a/test/orm/test_rel_fn.py b/test/orm/test_rel_fn.py
index c4d811d53..f0aa538f4 100644
--- a/test/orm/test_rel_fn.py
+++ b/test/orm/test_rel_fn.py
@@ -3,7 +3,7 @@ from sqlalchemy.testing import assert_raises_message, eq_, \
 from sqlalchemy.testing import fixtures
 from sqlalchemy.orm import relationships, foreign, remote
 from sqlalchemy import MetaData, Table, Column, ForeignKey, Integer, \
-    select, ForeignKeyConstraint, exc, func, and_
+    select, ForeignKeyConstraint, exc, func, and_, String
 from sqlalchemy.orm.interfaces import ONETOMANY, MANYTOONE, MANYTOMANY
 
 
@@ -119,6 +119,10 @@ class _JoinFixtures(object):
                         ("composite_target.uid", "composite_target.oid")),
             )
 
+        cls.purely_single_col = Table('purely_single_col', m,
+            Column('path', String)
+            )
+
     def _join_fixture_overlapping_three_tables(self, **kw):
         def _can_sync(*cols):
             for c in cols:
@@ -440,6 +444,37 @@ class _JoinFixtures(object):
                     **kw
                     )
 
+    def _join_fixture_purely_single_o2m(self, **kw):
+        return relationships.JoinCondition(
+                    self.purely_single_col,
+                    self.purely_single_col,
+                    self.purely_single_col,
+                    self.purely_single_col,
+                    support_sync=False,
+                    primaryjoin=
+                        self.purely_single_col.c.path.like(
+                            remote(
+                                foreign(
+                                    self.purely_single_col.c.path.concat('%')
+                                )
+                            )
+                        )
+                )
+
+    def _join_fixture_purely_single_m2o(self, **kw):
+        return relationships.JoinCondition(
+                    self.purely_single_col,
+                    self.purely_single_col,
+                    self.purely_single_col,
+                    self.purely_single_col,
+                    support_sync=False,
+                    primaryjoin=
+                        remote(self.purely_single_col.c.path).like(
+                            foreign(self.purely_single_col.c.path.concat('%'))
+                        )
+                )
+
+
     def _assert_non_simple_warning(self, fn):
         assert_raises_message(
             exc.SAWarning,
@@ -829,6 +864,13 @@ class ColumnCollectionsTest(_JoinFixtures, fixtures.TestBase,
             ]
         )
 
+    def test_determine_local_remote_pairs_purely_single_col_o2m(self):
+        joincond = self._join_fixture_purely_single_o2m()
+        eq_(
+            joincond.local_remote_pairs,
+            [(self.purely_single_col.c.path, self.purely_single_col.c.path)]
+        )
+
 class DirectionTest(_JoinFixtures, fixtures.TestBase, AssertsCompiledSQL):
     def test_determine_direction_compound_2(self):
         joincond = self._join_fixture_compound_expression_2(
@@ -862,6 +904,13 @@ class DirectionTest(_JoinFixtures, fixtures.TestBase, AssertsCompiledSQL):
         joincond = self._join_fixture_m2o()
         is_(joincond.direction, MANYTOONE)
 
+    def test_determine_direction_purely_single_o2m(self):
+        joincond = self._join_fixture_purely_single_o2m()
+        is_(joincond.direction, ONETOMANY)
+
+    def test_determine_direction_purely_single_m2o(self):
+        joincond = self._join_fixture_purely_single_m2o()
+        is_(joincond.direction, MANYTOONE)
 
 class DetermineJoinTest(_JoinFixtures, fixtures.TestBase, AssertsCompiledSQL):
     __dialect__ = 'default'
diff --git a/test/orm/test_relationships.py b/test/orm/test_relationships.py
index ccd54284a..3d8287b75 100644
--- a/test/orm/test_relationships.py
+++ b/test/orm/test_relationships.py
@@ -8,7 +8,7 @@ from sqlalchemy.orm import mapper, relationship, relation, \
                     backref, create_session, configure_mappers, \
                     clear_mappers, sessionmaker, attributes,\
                     Session, composite, column_property, foreign,\
-                    remote, synonym, joinedload
+                    remote, synonym, joinedload, subqueryload
 from sqlalchemy.orm.interfaces import ONETOMANY, MANYTOONE, MANYTOMANY
 from sqlalchemy.testing import eq_, startswith_, AssertsCompiledSQL, is_
 from sqlalchemy.testing import fixtures
@@ -231,6 +231,154 @@ class DependencyTwoParentTest(fixtures.MappedTest):
         session.flush()
 
 
+class DirectSelfRefFKTest(fixtures.MappedTest, AssertsCompiledSQL):
+    """Tests the ultimate join condition, a single column
+    that points to itself, e.g. within a SQL function or similar.
+    The test is against a materialized path setup.
+
+    this is an **extremely** unusual case::
+
+    Entity
+    ------
+     path -------+
+       ^         |
+       +---------+
+
+    In this case, one-to-many and many-to-one are no longer accurate.
+    Both relationships return collections.   I'm not sure if this is a good
+    idea.
+
+    """
+
+    __dialect__ = 'default'
+
+    @classmethod
+    def define_tables(cls, metadata):
+        Table('entity', metadata,
+                Column('path', String(100), primary_key=True)
+            )
+
+    @classmethod
+    def setup_classes(cls):
+        class Entity(cls.Basic):
+            def __init__(self, path):
+                self.path = path
+
+
+    def _descendants_fixture(self, data=True):
+        Entity = self.classes.Entity
+        entity = self.tables.entity
+
+        m = mapper(Entity, entity, properties={
+                "descendants": relationship(Entity,
+                                primaryjoin=
+                                    remote(foreign(entity.c.path)).like(
+                                            entity.c.path.concat('/%')),
+                                viewonly=True,
+                                order_by=entity.c.path)
+            })
+        configure_mappers()
+        assert m.get_property("descendants").direction is ONETOMANY
+        if data:
+            return self._fixture()
+
+    def _anscestors_fixture(self, data=True):
+        Entity = self.classes.Entity
+        entity = self.tables.entity
+
+        m = mapper(Entity, entity, properties={
+                "anscestors": relationship(Entity,
+                                primaryjoin=
+                                    entity.c.path.like(
+                                            remote(foreign(entity.c.path)).concat('/%')),
+                                viewonly=True,
+                                order_by=entity.c.path)
+            })
+        configure_mappers()
+        assert m.get_property("anscestors").direction is ONETOMANY
+        if data:
+            return self._fixture()
+
+    def _fixture(self):
+        Entity = self.classes.Entity
+        sess = Session()
+        sess.add_all([
+            Entity("/foo"),
+            Entity("/foo/bar1"),
+            Entity("/foo/bar2"),
+            Entity("/foo/bar2/bat1"),
+            Entity("/foo/bar2/bat2"),
+            Entity("/foo/bar3"),
+            Entity("/bar"),
+            Entity("/bar/bat1")
+        ])
+        return sess
+
+    def test_descendants_lazyload(self):
+        sess = self._descendants_fixture()
+        Entity = self.classes.Entity
+        e1 = sess.query(Entity).filter_by(path="/foo").first()
+        eq_(
+            [e.path for e in e1.descendants],
+            ["/foo/bar1", "/foo/bar2", "/foo/bar2/bat1",
+                "/foo/bar2/bat2", "/foo/bar3"]
+        )
+
+    def test_anscestors_lazyload(self):
+        sess = self._anscestors_fixture()
+        Entity = self.classes.Entity
+        e1 = sess.query(Entity).filter_by(path="/foo/bar2/bat1").first()
+        eq_(
+            [e.path for e in e1.anscestors],
+            ["/foo", "/foo/bar2"]
+        )
+
+    def test_descendants_joinedload(self):
+        sess = self._descendants_fixture()
+        Entity = self.classes.Entity
+        e1 = sess.query(Entity).filter_by(path="/foo").\
+                options(joinedload(Entity.descendants)).first()
+
+        eq_(
+            [e.path for e in e1.descendants],
+            ["/foo/bar1", "/foo/bar2", "/foo/bar2/bat1",
+                "/foo/bar2/bat2", "/foo/bar3"]
+        )
+
+    def test_descendants_subqueryload(self):
+        sess = self._descendants_fixture()
+        Entity = self.classes.Entity
+        e1 = sess.query(Entity).filter_by(path="/foo").\
+                options(subqueryload(Entity.descendants)).first()
+
+        eq_(
+            [e.path for e in e1.descendants],
+            ["/foo/bar1", "/foo/bar2", "/foo/bar2/bat1",
+                "/foo/bar2/bat2", "/foo/bar3"]
+        )
+
+    def test_anscestors_joinedload(self):
+        sess = self._anscestors_fixture()
+        Entity = self.classes.Entity
+        e1 = sess.query(Entity).filter_by(path="/foo/bar2/bat1").\
+                options(joinedload(Entity.anscestors)).first()
+        eq_(
+            [e.path for e in e1.anscestors],
+            ["/foo", "/foo/bar2"]
+        )
+
+    def test_plain_join_descendants(self):
+        self._descendants_fixture(data=False)
+        Entity = self.classes.Entity
+        sess = Session()
+        self.assert_compile(
+            sess.query(Entity).join(Entity.descendants, aliased=True),
+            "SELECT entity.path AS entity_path FROM entity JOIN entity AS "
+            "entity_1 ON entity_1.path LIKE (entity.path || :path_1)"
+        )
+
+
+
 class CompositeSelfRefFKTest(fixtures.MappedTest):
     """Tests a composite FK where, in
     the relationship(), one col points