Kirill Simonov avatar Kirill Simonov committed ae6fe3d

Refactoring binding nodes.
Added support for attachment operator.

Comments (0)

Files changed (18)

src/htsql/core/syn/parse.py

 from .syntax import (Syntax, SkipSyntax, AssignSyntax, SpecifySyntax,
         FunctionSyntax, PipeSyntax, OperatorSyntax, PrefixSyntax, FilterSyntax,
         ProjectSyntax, LinkSyntax, AttachSyntax, DetachSyntax, CollectSyntax,
-        DirectSyntax, ComposeSyntax, UnpackSyntax, ComplementSyntax,
-        GroupSyntax, SelectSyntax, LocateSyntax, RecordSyntax, ListSyntax,
-        IdentitySyntax, ReferenceSyntax, IdentifierSyntax, StringSyntax,
-        LabelSyntax, IntegerSyntax, DecimalSyntax, FloatSyntax)
+        DirectSyntax, ComposeSyntax, UnpackSyntax, LiftSyntax, GroupSyntax,
+        SelectSyntax, LocateSyntax, RecordSyntax, ListSyntax, IdentitySyntax,
+        ReferenceSyntax, IdentifierSyntax, StringSyntax, LabelSyntax,
+        IntegerSyntax, DecimalSyntax, FloatSyntax)
 from .grammar import SyntaxGrammar
 from .scan import scan
 
     # Atomic expressions.
     atom = grammar.add_rule('''
         atom:   collection  | detachment    | unpacking     |
-                reference   | function      | complement    |
+                reference   | function      | lift          |
                 record      | list          | identity      | literal
     ''')
 
         stream.mark(syntax)
         yield syntax
 
-    # Complement indicator (`^`).
-    complement = grammar.add_rule('''
-        complement:
-                `^`
+    # Lift indicator (`^`).
+    lift = grammar.add_rule('''
+        lift:   `^`
     ''')
 
-    @complement.set_match
-    def match_complement(stream):
+    @lift.set_match
+    def match_lift(stream):
         stream.pull()               # `^`
-        syntax = ComplementSyntax()
+        syntax = LiftSyntax()
         stream.mark(syntax)
         yield syntax
 

src/htsql/core/syn/syntax.py

         return u"".join(chunks)
 
 
-class ComplementSyntax(Syntax):
+class LiftSyntax(Syntax):
     """
-    The complement symbol.
+    The lift symbol.
 
     ::
 

src/htsql/core/tr/bind.py

 from ..error import Error, translate_guard, choices_guard, point
 from ..syn.syntax import (Syntax, CollectSyntax, SelectSyntax, ApplySyntax,
         FunctionSyntax, PipeSyntax, OperatorSyntax, PrefixSyntax,
-        ProjectSyntax, FilterSyntax, LinkSyntax, DetachSyntax, AssignSyntax,
-        ComposeSyntax, LocateSyntax, IdentitySyntax, GroupSyntax,
-        IdentifierSyntax, UnpackSyntax, ReferenceSyntax, ComplementSyntax,
+        ProjectSyntax, FilterSyntax, LinkSyntax, DetachSyntax, AttachSyntax,
+        AssignSyntax, ComposeSyntax, LocateSyntax, IdentitySyntax, GroupSyntax,
+        IdentifierSyntax, UnpackSyntax, ReferenceSyntax, LiftSyntax,
         StringSyntax, LabelSyntax, NumberSyntax, RecordSyntax, DirectSyntax)
 from .binding import (Binding, WrappingBinding, QueryBinding, SegmentBinding,
-        WeakSegmentBinding, RootBinding, HomeBinding, FreeTableBinding,
-        AttachedTableBinding, ColumnBinding, QuotientBinding, KernelBinding,
-        ComplementBinding, LinkBinding, LocatorBinding, SieveBinding,
+        WeakSegmentBinding, RootBinding, HomeBinding, TableBinding,
+        ChainBinding, ColumnBinding, QuotientBinding, KernelBinding,
+        ComplementBinding, LocateBinding, SieveBinding, AttachBinding,
         SortBinding, CastBinding, IdentityBinding, ImplicitCastBinding,
-        RescopingBinding, AssignmentBinding, DefinitionBinding,
-        SelectionBinding, WildSelectionBinding, DirectionBinding, TitleBinding,
-        RerouteBinding, ReferenceRerouteBinding, AliasBinding, LiteralBinding,
+        RescopingBinding, AssignmentBinding, DefineBinding,
+        DefineReferenceBinding, DefineLiftBinding, SelectionBinding,
+        WildSelectionBinding, DirectionBinding, TitleBinding, RerouteBinding,
+        ReferenceRerouteBinding, AliasBinding, LiteralBinding, FormulaBinding,
         VoidBinding, Recipe, LiteralRecipe, SelectionRecipe, FreeTableRecipe,
         AttachedTableRecipe, ColumnRecipe, KernelRecipe, ComplementRecipe,
         IdentityRecipe, ChainRecipe, SubstitutionRecipe, BindingRecipe,
         ClosedRecipe, PinnedRecipe, AmbiguousRecipe)
 from .lookup import (lookup_attribute, lookup_reference, lookup_complement,
         lookup_attribute_set, lookup_reference_set, expand, direct, guess_tag,
-        lookup_command, identify, unwrap)
+        identify, unwrap)
+from .signature import IsEqualSig, AndSig
 from .coerce import coerce
 from .decorate import decorate
 
         if self.environment is not None:
             for name, recipe in self.environment:
                 name = normalize(name)
-                self.scope = DefinitionBinding(self.scope, name, True, None,
-                                               recipe, self.scope.syntax)
+                self.scope = DefineReferenceBinding(self.scope, name,
+                                                    recipe, self.scope.syntax)
 
     def flush(self):
         """
                 seed = self.state.use(recipe, syntax)
         else:
             seed = self.state.scope
-        if lookup_command(seed) is not None:
-            return seed
         seed = Select.__invoke__(seed, self.state)
         domain = ListDomain(seed.domain)
         return SegmentBinding(self.state.scope, seed, domain,
                 if isinstance(syntax, AssignSyntax):
                     syntax = syntax.larm.larms[0]
                 binding = self.state.use(recipe, syntax)
-                scope = DefinitionBinding(scope, name, is_reference,
-                                          None, recipe, scope.syntax)
+                if is_reference:
+                    scope = DefineReferenceBinding(scope, name,
+                                                   recipe, scope.syntax)
+                else:
+                    scope = DefineBinding(scope, name, None,
+                                          recipe, scope.syntax)
                 self.state.pop_scope()
                 self.state.push_scope(scope)
             # Extract nested selectors, if any.
         if name is not None:
             recipe = ComplementRecipe(quotient)
             recipe = ClosedRecipe(recipe)
-            binding = DefinitionBinding(binding, name, False, None, recipe,
-                                        self.syntax)
+            binding = DefineBinding(binding, name, None, recipe, self.syntax)
         for index, kernel in enumerate(kernels):
             name = guess_tag(kernel)
             if name is not None:
                 recipe = KernelRecipe(quotient, index)
                 recipe = ClosedRecipe(recipe)
-                binding = DefinitionBinding(binding, name, False, None, recipe,
-                                            self.syntax)
+                binding = DefineBinding(binding, name, None, recipe,
+                                        self.syntax)
         return binding
 
 
                                                target_image.syntax)
             images.append((origin_image, target_image))
         # Generate a link scope.
-        return LinkBinding(self.state.scope, seed, images, self.syntax)
+        return AttachBinding(self.state.scope, seed, images, None, self.syntax)
+
+
+class BindAttach(Bind):
+
+    adapt(AttachSyntax)
+
+    def __call__(self):
+        home = HomeBinding(self.state.scope, self.syntax)
+        seed = self.state.bind(self.syntax.rarm, scope=home)
+        recipe = BindingRecipe(seed)
+        scope = self.state.scope
+        scope = DefineLiftBinding(scope, recipe, self.syntax)
+        name = guess_tag(seed)
+        if name is not None:
+            scope = DefineBinding(scope, name, None, recipe, self.syntax)
+        condition = self.state.bind(self.syntax.larm, scope=scope)
+        return AttachBinding(self.state.scope, seed, [], condition, self.syntax)
 
 
 class BindDetach(Bind):
             if identity.domain.width != location.width:
                 raise Error("Found ill-formed locator")
         def convert(identity, elements):
-            value = []
-            for field in identity.labels:
-                if isinstance(field, IdentityDomain):
+            assert isinstance(identity, IdentityBinding)
+            images = []
+            for field in identity.elements:
+                if isinstance(field.domain, IdentityDomain):
                     total_width = 0
                     items = []
-                    while total_width < field.width:
+                    while total_width < field.domain.width:
                         assert elements
                         element = elements.pop(0)
                         if (total_width == 0 and
                                 isinstance(element, IdentityBinding) and
-                                element.width == field.width):
+                                element.width == field.domain.width):
                             items = element.elements[:]
                             total_width = element.width
                         elif isinstance(element, IdentityBinding):
                             items.append(element)
                             total_width += 1
                     with translate_guard(self.syntax.rarm):
-                        if total_width > field.width:
+                        if total_width > field.domain.width:
                             raise Error("Found ill-formed locator")
-                    item = convert(field, items)
-                    value.append(item)
+                    images.extend(convert(field, items))
                 else:
                     assert elements
                     element = elements.pop(0)
                     with translate_guard(self.syntax.larm):
                         if isinstance(element, IdentityBinding):
                             raise Error("Found ill-formed locator")
-                    item = ImplicitCastBinding(element, field, element.syntax)
-                    value.append(item)
-            return tuple(value)
+                    item = ImplicitCastBinding(element, field.domain,
+                                               element.syntax)
+                    images.append((item, field))
+            return images
         elements = location.elements[:]
         while len(elements) == 1 and isinstance(elements[0], IdentityBinding):
             elements = elements[0].elements[:]
-        value = convert(identity.domain, elements)
-        return LocatorBinding(self.state.scope, seed, identity, value,
-                              self.syntax)
+        images = convert(identity, elements)
+        return LocateBinding(self.state.scope, seed, images, None, self.syntax)
 
 
 class BindIdentity(Bind):
         return self.state.use(recipe, self.syntax)
 
 
-class BindComplement(Bind):
+class BindLift(Bind):
 
-    adapt(ComplementSyntax)
+    adapt(LiftSyntax)
 
     def __call__(self):
         # Look for a complement, complain if not found.
 
     def __call__(self):
         # Produce a free table scope.
-        return FreeTableBinding(self.state.scope,
-                                self.recipe.table,
-                                self.syntax)
+        return TableBinding(self.state.scope,
+                            self.recipe.table,
+                            self.syntax)
 
 
 class BindByAttachedTable(BindByRecipe):
     adapt(AttachedTableRecipe)
 
     def __call__(self):
-        # Produce a sequence of joined tables.
-        binding = self.state.scope
-        for join in self.recipe.joins:
-            binding = AttachedTableBinding(binding, join, self.syntax)
-        return binding
+        return ChainBinding(self.state.scope, self.recipe.joins, self.syntax)
 
 
 class BindByColumn(BindByRecipe):
                                             self.recipe.parameters,
                                             self.recipe.body)
             recipe = ClosedRecipe(recipe)
-            binding = DefinitionBinding(binding, name, is_reference, arity,
+            if is_reference:
+                binding = DefineReferenceBinding(binding, name,
+                                                 recipe, self.syntax)
+            else:
+                binding = DefineBinding(binding, name, arity,
                                         recipe, self.syntax)
             return binding
 
                 binding = self.state.bind(syntax)
                 recipe = BindingRecipe(binding)
                 recipe = ClosedRecipe(recipe)
-                scope = DefinitionBinding(scope, name, is_reference, None,
+                if is_reference:
+                    scope = DefineReferenceBinding(scope, name,
+                                                   recipe, scope.syntax)
+                else:
+                    scope = DefineBinding(scope, name, None,
                                           recipe, scope.syntax)
         # Bind the syntax node associated with the recipe.
         binding = self.state.bind(self.recipe.body, scope=scope)

src/htsql/core/tr/binding.py

 #
 
 
-"""
-:mod:`htsql.core.tr.binding`
-============================
-
-This module declares binding nodes and recipe objects.
-"""
-
-
 from ..util import maybe, listof, tupleof, Clonable, Printable, Hashable
 from ..entity import TableEntity, ColumnEntity, Join
 from ..domain import (Domain, VoidDomain, BooleanDomain, ListDomain,
 from ..error import point
 from ..syn.syntax import Syntax, VoidSyntax, IdentifierSyntax, StringSyntax
 from .signature import Signature, Bag, Formula
-from ..cmd.command import Command
 
 
 class Binding(Clonable, Printable):
     """
-    Represents a binding node.
+    A binding node.
 
-    This is an abstract class; see subclasses for concrete binding nodes.
+    A binding graph is an intermediate representation of an HTSQL query.
+    It is constructed from the syntax tree by the *binding* process and
+    further translated to the flow graph by the *encoding* process.
 
-    A binding graph is an intermediate phase of the HTSQL translator between
-    the syntax tree and the flow graph.  It is converted from the syntax tree
-    by the *binding* process and further translated to the flow graph by the
-    *encoding* process.
+    A binding node represents an HTSQL expression or a naming scope (or both).
+    Each binding node keeps a reference to the scope in which it was created;
+    this scope chain forms a lookup context.
 
-    The structure of the binding graph reflects the form of naming *scopes*
-    in the query; each binding node keeps a reference to the scope where
-    it was instantiated.
+    `base`: :class:`Binding` or ``None``
+        The scope in which the node was created; used for chaining lookup
+        requests.
 
-    The constructor arguments:
+    `domain`: :class:`.Domain`
+        The data type of the expression.
 
-    `base` (:class:`Binding` or ``None``)
-        The scope in which the node is created.
-
-        The value of ``None`` is only valid for an instance of
-        :class:`RootBinding`, which represents the origin node in the graph.
-
-    `domain` (:class:`htsql.core.domain.Domain`)
-        The type of the binding node; use :class:`htsql.core.domain.VoidDomain`
-        instance when not applicable.
-
-    `syntax` (:class:`htsql.core.tr.syntax.Syntax`)
-        The syntax node that generated the binding node; should be used
-        for presentation or error reporting only, there is no guarantee
-        that that the syntax node is semantically, or even syntaxically
-        valid.
+    `syntax`: :class:`.Syntax`
+        The syntax node from which the binding node was generated; use
+        only for presentation and error reporting.
     """
 
     def __init__(self, base, domain, syntax):
         assert isinstance(base, maybe(Binding))
-        assert base is None or not isinstance(self, RootBinding)
+        assert base is not None or isinstance(self, (RootBinding, VoidBinding))
         assert isinstance(domain, Domain)
         assert isinstance(syntax, Syntax)
 
         self.base = base
         self.domain = domain
         self.syntax = syntax
+        # Inherit the error context from the syntax node.
         point(self, syntax)
 
-    def __str__(self):
-        # Display an HTSQL fragment that (approximately) corresponds
-        # to the binding node.
-        return str(self.syntax)
+    def __unicode__(self):
+        return unicode(self.syntax)
 
 
-class Recipe(Hashable, Printable):
+class Recipe(Hashable):
     """
-    Represents a recipe object.
+    A recipe object.
 
     A recipe is a generator of binding nodes.  Recipes are produced by lookup
     requests and used to construct the binding graph.
 
 
 class VoidBinding(Binding):
+    """
+    A dummy binding node.
+    """
 
     def __init__(self):
-        base = RootBinding(VoidSyntax())
-        super(VoidBinding, self).__init__(base, VoidDomain(), VoidSyntax())
+        super(VoidBinding, self).__init__(None, VoidDomain(), VoidSyntax())
+
+
+class ScopeBinding(Binding):
+    """
+    Represents a binding node that introduces a new naming scope.
+    """
+
+
+class HomeBinding(ScopeBinding):
+    """
+    The *home* scope.
+
+    The home scope contains all database tables.
+    """
+
+    def __init__(self, base, syntax):
+        super(HomeBinding, self).__init__(base, EntityDomain(), syntax)
+
+
+class RootBinding(HomeBinding):
+    """
+    The root scope.
+
+    The root scope is the origin of the binding graph.
+    """
+
+    def __init__(self, syntax):
+        super(RootBinding, self).__init__(None, syntax)
+
+
+class TableBinding(ScopeBinding):
+    """
+    A table scope.
+
+    A table scope contains all table attributes and the links to other tables
+    related via foreign key constraints.
+
+    `table`: :class:`.TableEntity`
+        The database table.
+    """
+
+    def __init__(self, base, table, syntax):
+        assert isinstance(table, TableEntity)
+        super(TableBinding, self).__init__(base, EntityDomain(), syntax)
+        self.table = table
+
+
+class ChainBinding(TableBinding):
+    """
+    An attached table scope.
+
+    An attached table is produced by a link from another table via
+    a chain of foreign key constraints.
+
+    `joins`: [:class:`.Join`]
+        Constraints attaching the table to its base.
+    """
+
+    def __init__(self, base, joins, syntax):
+        assert isinstance(joins, listof(Join)) and len(joins) > 0
+        super(ChainBinding, self).__init__(base, joins[-1].target, syntax)
+        self.joins = joins
+
+
+class ColumnBinding(ScopeBinding):
+    """
+    A table column scope.
+
+    `column`: :class:`.ColumnEntity`
+        The column.
+
+    `link`: :class:`Binding` or ``None``
+        If set, intercepts all lookup requests to the column scope.  Used
+        when the same name represents both a column and a link to another
+        table.
+    """
+
+    def __init__(self, base, column, link, syntax):
+        assert isinstance(column, ColumnEntity)
+        assert isinstance(link, maybe(Binding))
+        super(ColumnBinding, self).__init__(base, column.domain, syntax)
+        self.column = column
+        self.link = link
+
+
+class QuotientBinding(ScopeBinding):
+    """
+    A quotient scope.
+
+    A quotient of the `seed` flow by the given `kernels` is a flow of
+    all unique values of ``kernels`` as it ranges over ``seed``.
+
+    `seed`: :class:`Binding`
+        The seed of the quotient.
+
+    `kernels`: [:class:`Binding`]
+        The kernel expressions.
+    """
+
+    def __init__(self, base, seed, kernels, syntax):
+        assert isinstance(seed, Binding)
+        assert isinstance(kernels, listof(Binding))
+        super(QuotientBinding, self).__init__(base, EntityDomain(), syntax)
+        self.seed = seed
+        self.kernels = kernels
+
+
+class CoverBinding(ScopeBinding):
+    """
+    Represents a scope that borrows its content from another scope.
+
+    `seed`: :class:`Binding`
+        The wrapped scope.
+    """
+
+    def __init__(self, base, seed, syntax):
+        assert isinstance(seed, Binding)
+        super(ScopeBinding, self).__init__(base, seed.domain, syntax)
+        self.seed = seed
+
+
+class KernelBinding(CoverBinding):
+    """
+    A kernel expression in a quotient scope.
+
+    `quotient`: :class:`QuotientBinding`
+        The quotient scope.
+
+    `index`: ``int``
+        The position of the selected kernel expression.
+    """
+
+    def __init__(self, base, quotient, index, syntax):
+        assert isinstance(quotient, QuotientBinding)
+        assert isinstance(index, int)
+        assert 0 <= index < len(quotient.kernels)
+        seed = quotient.kernels[index]
+        super(KernelBinding, self).__init__(base, seed, syntax)
+        self.quotient = quotient
+        self.index = index
+
+
+class ComplementBinding(CoverBinding):
+    """
+    A complement link in a quotient scope.
+
+    `quotient`: :class:`QuotientBinding`
+        The quotient scope.
+    """
+
+    def __init__(self, base, quotient, syntax):
+        assert isinstance(quotient, QuotientBinding)
+        super(ComplementBinding, self).__init__(base, quotient.seed, syntax)
+        self.quotient = quotient
+
+
+class ForkBinding(CoverBinding):
+    """
+    A fork of the current scope.
+
+    `kernels` [:class:`Binding`]
+        The kernel expressions attaching the fork to its base.
+    """
+
+    def __init__(self, base, kernels, syntax):
+        assert isinstance(kernels, listof(Binding))
+        super(ForkBinding, self).__init__(base, base, syntax)
+        self.kernels = kernels
+
+
+class AttachBinding(CoverBinding):
+    """
+    An attachment expression.
+
+    `images`: [(:class:`Binding`, :class:`Binding`)]
+        Pairs of expressions attaching the binding to its base.
+
+    `condition`: :class:`Binding`
+        A condition attaching the binding to its base.
+    """
+
+    def __init__(self, base, seed, images, condition, syntax):
+        assert isinstance(images, listof(tupleof(Binding, Binding)))
+        assert isinstance(condition, maybe(Binding))
+        if condition is not None:
+            assert isinstance(condition.domain, BooleanDomain)
+        super(AttachBinding, self).__init__(base, seed, syntax)
+        self.images = images
+        self.condition = condition
+
+
+class LocateBinding(AttachBinding):
+    """
+    A locator expression.
+
+    A locator is an attachment expression for which we know that
+    it produces a singular value.
+    """
+
+
+class ClipBinding(CoverBinding):
+    """
+    A slice of a flow.
+
+    `order`: [(:class:`Binding`, ``+1`` or ``-1``)]
+        Expressions to sort by.
+
+    `limit`: ``int`` or ``None``
+        If set, indicates to take the top ``limit`` rows.
+        (``None`` means ``1``).
+
+    `offset`: ``int`` or ``None``
+        If set, indicates to drop the top ``offset`` rows.
+        (``None`` means ``0``).
+    """
+
+    def __init__(self, base, seed, order, limit, offset, syntax):
+        assert isinstance(seed, Binding)
+        assert isinstance(order, listof(tupleof(Binding, int)))
+        assert isinstance(limit, maybe(int))
+        assert isinstance(offset, maybe(int))
+        super(ClipBinding, self).__init__(base, seed, syntax)
+        self.order = order
+        self.limit = limit
+        self.offset = offset
+
+
+class ValueBinding(Binding):
+    """
+    A literal value.
+
+    `data`
+        The data value.
+    """
+
+    def __init__(self, base, data, domain, syntax):
+        super(ValueBinding, self).__init__(base, domain, syntax)
+        self.data = data
+
+
+class WrapBinding(Binding):
+    """
+    Represents a binding node that augments a naming scope.
+    """
+
+
+class DecorateBinding(WrapBinding):
+    """
+    Represents a binding node ignored by the encoder.
+    """
+
+    def __init__(self, base, syntax):
+        super(DecorateBinding, self).__init__(base, base.domain, syntax)
+
+
+class DefineBinding(DecorateBinding):
+    """
+    Defines a calculated attribute.
+
+    `name`: ``unicode``
+        The name of the attribute.
+
+    `arity`: ``int`` or ``None``
+        The number of arguments for an parameterized attribute;
+        ``None`` for an attribute without parameters.
+
+    `recipe`: :class:`Recipe`
+        The value generator.
+    """
+
+    def __init__(self, base, name, arity, recipe, syntax):
+        assert isinstance(name, unicode)
+        assert isinstance(arity, maybe(int))
+        assert isinstance(recipe, Recipe)
+        super(DefineBinding, self).__init__(base, syntax)
+        self.name = name
+        self.arity = arity
+        self.recipe = recipe
+
+
+class DefineReferenceBinding(DecorateBinding):
+    """
+    Defines a reference.
+
+    `name`: ``unicode``
+        The reference name.
+
+    `recipe`: :class:`Recipe`
+        The value generator.
+    """
+
+    def __init__(self, base, name, recipe, syntax):
+        assert isinstance(name, unicode)
+        assert isinstance(recipe, Recipe)
+        super(DefineReferenceBinding, self).__init__(base, syntax)
+        self.name = name
+        self.recipe = recipe
+
+
+class DefineLiftBinding(DecorateBinding):
+    """
+    Defines the value of the lift symbol.
+
+    `recipe`: :class:`Recipe`
+        The value generator.
+    """
+
+    def __init__(self, base, recipe, syntax):
+        assert isinstance(recipe, Recipe)
+        super(DefineLiftBinding, self).__init__(base, syntax)
+        self.recipe = recipe
 
 
 class QueryBinding(Binding):
     pass
 
 
-class CommandBinding(Binding):
-
-    def __init__(self, base, command, syntax):
-        assert isinstance(command, Command)
-        super(CommandBinding, self).__init__(base, VoidDomain(), syntax)
-        self.command = command
-
-
 class ScopingBinding(Binding):
     """
     Represents a binding node that introduces a new naming scope.
         super(WrappingBinding, self).__init__(base, base.domain, syntax)
 
 
-class HomeBinding(ScopingBinding):
-    """
-    Represents the *home* naming scope.
-
-    The home scope contains links to all tables in the database.
-    """
-
-    def __init__(self, base, syntax):
-        super(HomeBinding, self).__init__(base, EntityDomain(), syntax)
-
-
-class RootBinding(HomeBinding):
-    """
-    Represents the root scope.
-
-    The root scope is the origin of the binding graph.
-    """
-
-    def __init__(self, syntax):
-        super(RootBinding, self).__init__(None, syntax)
-
-
-class TableBinding(ScopingBinding):
-    """
-    Represents a table scope.
-
-    This is an abstract class; see :class:`FreeTableBinding` and
-    :class:`AttachedTableBinding` for concrete subclasses.
-
-    A table scope contains all attributes of the tables as well
-    as the links to other tables related via foreign key constraints.
-
-    `table` (:class:`htsql.core.entity.TableEntity`)
-        The table with which the binding is associated.
-    """
-
-    def __init__(self, base, table, syntax):
-        assert isinstance(table, TableEntity)
-        super(TableBinding, self).__init__(base, EntityDomain(), syntax)
-        self.table = table
-
-
-class FreeTableBinding(TableBinding):
-    """
-    Represents a free table scope.
-
-    A free table binding is generated by a link from the home class.
-    """
-
-
-class AttachedTableBinding(TableBinding):
-    """
-    Represents an attached table scope.
-
-    An attached table binding is generated by a link from another table.
-
-    `join` (:class:`htsql.core.entity.Join`)
-        The join attaching the table to its base.
-    """
-
-    def __init__(self, base, join, syntax):
-        assert isinstance(join, Join)
-        super(AttachedTableBinding, self).__init__(base, join.target, syntax)
-        self.join = join
-
-
-class ColumnBinding(ScopingBinding):
-    """
-    Represents a table column scope.
-
-    `column` (:class:`htsql.core.entity.ColumnEntity`)
-        The column entity.
-
-    `link` (:class:`Binding` or ``None``)
-        If set, indicates that the binding also represents a link
-        to another table.  Any lookup requests applied to the column
-        binding are delegated to `link`.
-    """
-
-    def __init__(self, base, column, link, syntax):
-        assert isinstance(column, ColumnEntity)
-        assert isinstance(link, maybe(Binding))
-        super(ColumnBinding, self).__init__(base, column.domain, syntax)
-        self.column = column
-        self.link = link
-
-
-class QuotientBinding(ScopingBinding):
-    """
-    Represents a quotient scope.
-
-    A quotient expression generates a flow of all unique values of
-    the given kernel as it ranges over the `seed` flow.
-
-    `seed` (:class:`Binding`)
-        The seed of the quotient.
-
-    `kernels` (a list of :class:`Binding`)
-        The kernel expressions of the quotient.
-    """
-
-    def __init__(self, base, seed, kernels, syntax):
-        assert isinstance(seed, Binding)
-        assert isinstance(kernels, listof(Binding))
-        super(QuotientBinding, self).__init__(base, EntityDomain(), syntax)
-        self.seed = seed
-        self.kernels = kernels
-
-
-class KernelBinding(ScopingBinding):
-    """
-    Represents a kernel in a quotient scope.
-
-    `quotient` (:class:`QuotientBinding`)
-        The quotient binding (typically coincides with `base`).
-
-    `index` (an integer)
-        The position of the selected kernel expression.
-    """
-
-    def __init__(self, base, quotient, index, syntax):
-        assert isinstance(quotient, QuotientBinding)
-        assert isinstance(index, int)
-        assert 0 <= index < len(quotient.kernels)
-        domain = quotient.kernels[index].domain
-        super(KernelBinding, self).__init__(base, domain, syntax)
-        self.quotient = quotient
-        self.index = index
-
-
-class ComplementBinding(ScopingBinding):
-    """
-    Represents a complement link in a quotient scope.
-
-    `quotient` (:class:`QuotientBinding`)
-        The quotient binding (typically coincides with `base`)
-    """
-
-    def __init__(self, base, quotient, syntax):
-        assert isinstance(quotient, QuotientBinding)
-        domain = quotient.seed.domain
-        super(ComplementBinding, self).__init__(base, domain, syntax)
-        self.quotient = quotient
-
-
-class CoverBinding(ScopingBinding):
-    """
-    Represents an opaque alias for a scope expression.
-
-    `seed` (:class:`Binding`)
-        The covered expression.
-    """
-
-    def __init__(self, base, seed, syntax):
-        assert isinstance(seed, Binding)
-        super(CoverBinding, self).__init__(base, seed.domain, syntax)
-        self.seed = seed
-
-
-class ForkBinding(ScopingBinding):
-    """
-    Represents a forking expression.
-
-    `kernels` (a list of :class:`Binding`)
-        The kernel expressions of the fork.
-    """
-
-    def __init__(self, base, kernels, syntax):
-        assert isinstance(kernels, listof(Binding))
-        super(ForkBinding, self).__init__(base, base.domain, syntax)
-        self.kernels = kernels
-
-
-class LinkBinding(ScopingBinding):
-    """
-    Represents a linking expression.
-
-    `seed` (:class:`Binding`)
-        The target of the link.
-
-    `images` (a list of pairs of :class:`Binding`)
-        Pairs of expressions connecting `seed` to `base`.
-    """
-
-    def __init__(self, base, seed, images, syntax):
-        assert isinstance(seed, Binding)
-        assert isinstance(images, listof(tupleof(Binding, Binding)))
-        super(LinkBinding, self).__init__(base, EntityDomain(), syntax)
-        self.seed = seed
-        self.images = images
-
-
-class ClipBinding(ScopingBinding):
-
-    def __init__(self, base, seed, limit, offset, syntax):
-        assert isinstance(seed, Binding)
-        assert isinstance(limit, maybe(int))
-        assert isinstance(offset, maybe(int))
-        super(ClipBinding, self).__init__(base, seed.domain, syntax)
-        self.seed = seed
-        self.limit = limit
-        self.offset = offset
-
-
-class LocatorBinding(ScopingBinding):
-
-    def __init__(self, base, seed, identity, value, syntax):
-        assert isinstance(seed, Binding)
-        assert isinstance(identity, IdentityBinding)
-        assert (isinstance(value, tuple) and
-                len(value) == len(identity.elements))
-        super(LocatorBinding, self).__init__(base, seed.domain, syntax)
-        self.seed = seed
-        self.identity = identity
-        self.value = value
-
-
 class SieveBinding(ChainingBinding):
     """
     Represents a sieve expression.
         self.body = body
 
 
-class DefinitionBinding(WrappingBinding):
-    """
-    Represents a definition of a calculated attribute or a reference.
-
-    `name` (a Unicode string)
-        The name of the attribute.
-
-    `is_reference` (Boolean)
-        If set, indicates a definition of a reference.
-
-    `arity` (an integer or ``None``)
-        The number of arguments for an parameterized attribute;
-        ``None`` for an attribute without parameters.
-
-    `recipe` (:class:`Recipe`)
-        The value of the attribute.
-    """
-
-    def __init__(self, base, name, is_reference, arity, recipe, syntax):
-        assert isinstance(name, unicode)
-        assert isinstance(is_reference, bool)
-        assert isinstance(arity, maybe(int))
-        # A reference cannot have parameters.
-        assert arity is None or not is_reference
-        assert isinstance(recipe, Recipe)
-        super(DefinitionBinding, self).__init__(base, syntax)
-        self.name = name
-        self.is_reference = is_reference
-        self.arity = arity
-        self.recipe = recipe
-
-
 class DirectionBinding(WrappingBinding):
     """
     Represents a direction decorator (postfix ``+`` and ``-`` operators).

src/htsql/core/tr/compile.py

                         SortDirectionSig, RowNumberSig)
 from .flow import (Expression, QueryExpr, SegmentCode, Code, LiteralCode,
         FormulaCode, Flow, RootFlow, ScalarFlow, TableFlow, QuotientFlow,
-        ComplementFlow, MonikerFlow, LocatorFlow, ForkedFlow, LinkedFlow,
+        ComplementFlow, MonikerFlow, LocatorFlow, ForkedFlow, AttachFlow,
         ClippedFlow, FilteredFlow, OrderedFlow, Unit, ScalarUnit, ColumnUnit,
         AggregateUnit, CorrelatedUnit, KernelUnit, CoveringUnit,
         CorrelationCode)
     # The implementation is shared by these three covering flows.
     adapt_many(MonikerFlow,
                ForkedFlow,
-               LinkedFlow,
-               ClippedFlow,
-               LocatorFlow)
+               AttachFlow,
+               ClippedFlow)
 
     def __call__(self):
         # Moniker, forked and linked flows are represented as a seed term
         if isinstance(self.flow, ForkedFlow):
             codes += self.flow.kernels
         # For the linked flow, it must export the linking expressions.
-        if isinstance(self.flow, LinkedFlow):
+        if isinstance(self.flow, AttachFlow):
             codes += [rop for lop, rop in self.flow.images]
         # A clipped flow must order itself (but only up to the base).
         if isinstance(self.flow, ClippedFlow):
                     continue
                 codes.append(code)
                 order.append((code, direction))
-        if isinstance(self.flow, LocatorFlow):
+        if (isinstance(self.flow, AttachFlow) and
+                self.flow.filter is not None):
             codes.append(self.flow.filter)
         # Any companion expressions must also be included.
         codes += self.flow.companions
         seed_term = self.state.inject(seed_term, codes)
 
-        if isinstance(self.flow, LocatorFlow):
+        if (isinstance(self.flow, AttachFlow) and
+                self.flow.filter is not None):
             seed_term = FilterTerm(self.state.tag(), seed_term,
                                    self.flow.filter,
                                    seed_term.flow,

src/htsql/core/tr/encode.py

 from ..error import Error, translate_guard
 from .coerce import coerce
 from .binding import (Binding, QueryBinding, SegmentBinding,
-        WeakSegmentBinding, WrappingBinding, SelectionBinding, HomeBinding,
-        RootBinding, FreeTableBinding, AttachedTableBinding, ColumnBinding,
+        WeakSegmentBinding, WrappingBinding, DecorateBinding, SelectionBinding,
+        HomeBinding, RootBinding, TableBinding, ChainBinding, ColumnBinding,
         QuotientBinding, KernelBinding, ComplementBinding, IdentityBinding,
-        LocatorBinding, CoverBinding, ForkBinding, LinkBinding, ClipBinding,
+        LocateBinding, CoverBinding, ForkBinding, AttachBinding, ClipBinding,
         SieveBinding, SortBinding, CastBinding, RescopingBinding,
         LiteralBinding, FormulaBinding)
 from .lookup import direct
 from .flow import (RootFlow, ScalarFlow, DirectTableFlow, FiberTableFlow,
         QuotientFlow, ComplementFlow, MonikerFlow, LocatorFlow, ForkedFlow,
-        LinkedFlow, ClippedFlow, FilteredFlow, OrderedFlow, QueryExpr,
+        AttachFlow, ClippedFlow, FilteredFlow, OrderedFlow, QueryExpr,
         SegmentCode, LiteralCode, FormulaCode, CastCode, RecordCode,
         AnnihilatorCode, IdentityCode, ColumnUnit, ScalarUnit, KernelUnit)
 from .signature import Signature, IsNullSig, NullIfSig, IsEqualSig, AndSig
         return ScalarFlow(base, self.binding)
 
 
-class RelateFreeTable(Relate):
+class RelateTable(Relate):
 
-    adapt(FreeTableBinding)
+    adapt(TableBinding)
 
     def __call__(self):
         # Generate the parent flow.
         return DirectTableFlow(base, self.binding.table, self.binding)
 
 
-class RelateAttachedTable(Relate):
+class RelateChain(Relate):
 
-    adapt(AttachedTableBinding)
+    adapt(ChainBinding)
 
     def __call__(self):
         # Generate the parent flow.
-        base = self.state.relate(self.binding.base)
+        flow = self.state.relate(self.binding.base)
         # Produce a link between table classes.
-        return FiberTableFlow(base, self.binding.join, self.binding)
+        for join in self.binding.joins:
+            flow = FiberTableFlow(flow, join, self.binding)
+        return flow
 
 
 class RelateSieve(Relate):
         return ForkedFlow(base, seed, kernels, self.binding)
 
 
-class RelateLink(Relate):
+class RelateAttach(Relate):
 
-    adapt(LinkBinding)
+    adapt(AttachBinding)
 
     def __call__(self):
         # Generate the parent and the seed flows.
         #    if not all(seed.spans(unit.flow) for unit in rcode.units):
         #        raise Error("a singular expression is expected",
         #                    rcode.mark)
-        return LinkedFlow(base, seed, images, self.binding)
+        filter = None
+        if self.binding.condition is not None:
+            filter = self.state.encode(self.binding.condition)
+        return AttachFlow(base, seed, images, filter, self.binding)
 
 
 class RelateClip(Relate):
 
 class RelateLocator(Relate):
 
-    adapt(LocatorBinding)
+    adapt(LocateBinding)
 
     def __call__(self):
         base = self.state.relate(self.binding.base)
         seed = self.state.relate(self.binding.seed)
-        def convert(identity, items):
-            filters = []
-            for element, item in zip(identity.elements, items):
-                if isinstance(element, IdentityBinding):
-                    filter = convert(element, item)
-                else:
-                    element = self.state.encode(element)
-                    item = self.state.encode(item)
-                    filter = FormulaCode(IsEqualSig(+1),
-                                         coerce(BooleanDomain()),
-                                         self.binding,
-                                         lop=element, rop=item)
-                filters.append(filter)
-            if len(filters) == 1:
-                return filters[0]
-            else:
-                return FormulaCode(AndSig(), coerce(BooleanDomain()),
-                                   self.binding, ops=filters)
-        filter = convert(self.binding.identity, self.binding.value)
-        return LocatorFlow(base, seed, filter, self.binding)
+        images = [(self.state.encode(lop), self.state.encode(rop))
+                  for lop, rop in self.binding.images]
+        filter = None
+        if self.binding.condition is not None:
+            filter = self.state.encode(self.binding.condition)
+        return LocatorFlow(base, seed, images, filter, self.binding)
 
 
 class EncodeColumn(Encode):
 
 class EncodeWrapping(Encode):
 
-    adapt(WrappingBinding)
+    adapt_many(WrappingBinding,
+               DecorateBinding)
 
     def __call__(self):
         # Delegate the adapter to the wrapped binding.
     Translates a wrapper binding to a flow node.
     """
 
-    adapt(WrappingBinding)
+    adapt_many(WrappingBinding,
+               DecorateBinding)
 
     def __call__(self):
         # Delegate the adapter to the wrapped binding.

src/htsql/core/tr/flow.py

                 % (self.base, ", ".join(str(code) for code in self.kernels))
 
 
-class LinkedFlow(Flow):
+class AttachFlow(Flow):
     """
     Represents a linking operation.
 
 
     is_axis = True
 
-    def __init__(self, base, seed, images, binding, companions=[]):
+    def __init__(self, base, seed, images, filter, binding, companions=[]):
         assert isinstance(base, Flow)
         assert isinstance(seed, Flow)
         assert seed.spans(base)
         assert not base.spans(seed)
         assert isinstance(images, listof(tupleof(Code, Code)))
-        # FIXME: the constraint may be violated after rewriting.
-        #assert all(base.spans(unit.flow) for lop, rop in images
-        #                                 for unit in lop.units)
-        #assert all(seed.spans(unit.flow) for lop, rop in images
-        #                                 for unit in rop.units)
+        assert isinstance(filter, maybe(Code))
+        if filter is not None:
+            assert isinstance(filter.domain, BooleanDomain)
         assert isinstance(companions, listof(Code))
         ground = seed
         while not base.spans(ground.base):
             ground = ground.base
-        super(LinkedFlow, self).__init__(
+        super(AttachFlow, self).__init__(
                     base=base,
                     family=seed.family,
                     is_contracting=False,
         self.seed = seed
         self.ground = ground
         self.images = images
+        self.filter = filter
         self.companions = companions
 
     def __basis__(self):
-        return (self.base, self.seed, tuple(self.images))
+        return (self.base, self.seed, tuple(self.images), self.filter)
 
     def __str__(self):
         # Display:
                    self.limit if self.limit is not None else 1)
 
 
-class LocatorFlow(Flow):
+class LocatorFlow(AttachFlow):
 
     is_axis = True
 
-    def __init__(self, base, seed, filter, binding, companions=[]):
+    def __init__(self, base, seed, images, filter, binding, companions=[]):
         assert isinstance(base, Flow)
         assert isinstance(seed, Flow)
-        assert (isinstance(filter, Code) and
-                isinstance(filter.domain, BooleanDomain))
+        assert isinstance(images, listof(tupleof(Code, Code)))
+        assert isinstance(filter, maybe(Code))
+        if filter is not None:
+            assert isinstance(filter.domain, BooleanDomain)
         assert seed.spans(base)
         # We don't need `seed` to be plural or even axial against `base`.
         #assert not base.spans(seed)
         while not axis.is_axis:
             axis = axis.base
         is_contracting = (axis.base is None or base.spans(axis.base))
-        super(LocatorFlow, self).__init__(
+        # Note: skip Attach constructor.
+        super(AttachFlow, self).__init__(
                     base=base,
                     family=seed.family,
                     is_contracting=is_contracting,
                     is_expanding=False,
                     binding=binding)
         self.seed = seed
+        self.images = images
         self.filter = filter
         self.ground = ground
         self.companions = companions
 
     def __basis__(self):
-        return (self.base, self.seed, self.filter)
+        return (self.base, self.seed, tuple(self.images), self.filter)
 
 
 class FilteredFlow(Flow):
         assert isinstance(flow, (ComplementFlow,
                                  MonikerFlow,
                                  ForkedFlow,
-                                 LinkedFlow,
+                                 AttachFlow,
                                  ClippedFlow,
                                  LocatorFlow))
         super(CoveringUnit, self).__init__(

src/htsql/core/tr/fn/bind.py

 from ..binding import (LiteralBinding, SortBinding, SieveBinding,
         FormulaBinding, CastBinding, ImplicitCastBinding, WrappingBinding,
         TitleBinding, DirectionBinding, QuotientBinding, AssignmentBinding,
-        DefinitionBinding, SelectionBinding, HomeBinding, RescopingBinding,
-        CoverBinding, ForkBinding, ClipBinding, CommandBinding, SegmentBinding,
-        QueryBinding, Binding, BindingRecipe, ComplementRecipe, KernelRecipe,
-        SubstitutionRecipe, ClosedRecipe)
+        DefineBinding, DefineReferenceBinding, SelectionBinding, HomeBinding,
+        RescopingBinding, CoverBinding, ForkBinding, ClipBinding,
+        SegmentBinding, QueryBinding, Binding, BindingRecipe, ComplementRecipe,
+        KernelRecipe, SubstitutionRecipe, ClosedRecipe)
 from ..bind import BindByName, BindingState
 from ...error import Error, translate_guard
 from ..coerce import coerce
 from ..decorate import decorate
-from ..lookup import direct, expand, identify, guess_tag, lookup_command
+from ..lookup import direct, expand, identify, guess_tag
 from ..signature import (Signature, NullarySig, UnarySig, BinarySig,
         CompareSig, IsEqualSig, IsTotallyEqualSig, IsInSig, IsNullSig,
         IfNullSig, NullIfSig, AndSig, OrSig, NotSig, SortDirectionSig)
         if name is not None:
             recipe = ComplementRecipe(quotient)
             recipe = ClosedRecipe(recipe)
-            binding = DefinitionBinding(binding, name, False, None, recipe,
-                                        self.syntax)
+            binding = DefineBinding(binding, name, None, recipe, self.syntax)
         for index, kernel in enumerate(kernels):
             name = guess_tag(kernel)
             if name is not None:
                 recipe = KernelRecipe(quotient, index)
                 recipe = ClosedRecipe(recipe)
-                binding = DefinitionBinding(binding, name, False, None, recipe,
-                                            self.syntax)
+                binding = DefineBinding(binding, name, None, recipe,
+                                        self.syntax)
         return binding
 
 
             limit = self.parse(limit)
         if offset is not None:
             offset = self.parse(offset)
-        return ClipBinding(self.state.scope, seed, limit, offset, self.syntax)
+        return ClipBinding(self.state.scope, seed, [], limit, offset,
+                           self.syntax)
 
 
 class BindDirectionBase(BindMacro):
                                             assignment.parameters,
                                             assignment.body)
             recipe = ClosedRecipe(recipe)
-            binding = DefinitionBinding(binding, name, is_reference, arity,
+            if is_reference:
+                binding = DefineReferenceBinding(binding, name,
+                                                 recipe, self.syntax)
+            else:
+                binding = DefineBinding(binding, name, arity,
                                         recipe, self.syntax)
         return binding
 
                                             assignment.parameters,
                                             assignment.body)
             recipe = ClosedRecipe(recipe)
-            binding = DefinitionBinding(binding, name, is_reference, arity,
+            if is_reference:
+                binding = DefineReferenceBinding(binding, name,
+                                                 recipe, self.syntax)
+            else:
+                binding = DefineBinding(binding, name, arity,
                                         recipe, self.syntax)
         return self.state.bind(lop, scope=binding)
 

src/htsql/core/tr/lookup.py

 from ..classify import classify, relabel, localize, normalize
 from ..syn.syntax import IdentifierSyntax
 from ..error import point
-from .binding import (Binding, ScopingBinding, ChainingBinding,
-        WrappingBinding, SegmentBinding, HomeBinding, RootBinding,
-        TableBinding, FreeTableBinding, AttachedTableBinding, ColumnBinding,
-        QuotientBinding, ComplementBinding, CoverBinding, ForkBinding,
-        LinkBinding, ClipBinding, LocatorBinding, RescopingBinding,
-        DefinitionBinding, SelectionBinding, WildSelectionBinding,
-        DirectionBinding, RerouteBinding, ReferenceRerouteBinding,
-        TitleBinding, AliasBinding, CommandBinding, ImplicitCastBinding,
-        FreeTableRecipe, AttachedTableRecipe, ColumnRecipe, ComplementRecipe,
-        KernelRecipe, BindingRecipe, IdentityRecipe, ChainRecipe,
-        SubstitutionRecipe, ClosedRecipe, InvalidRecipe, AmbiguousRecipe)
+from .binding import (Binding, ScopeBinding, ChainingBinding, WrappingBinding,
+        DecorateBinding, SegmentBinding, HomeBinding, RootBinding,
+        TableBinding, ChainBinding, ColumnBinding, QuotientBinding,
+        ComplementBinding, CoverBinding, ForkBinding, AttachBinding,
+        ClipBinding, LocateBinding, RescopingBinding, DefineBinding,
+        DefineReferenceBinding, DefineLiftBinding, SelectionBinding,
+        WildSelectionBinding, DirectionBinding, RerouteBinding,
+        ReferenceRerouteBinding, TitleBinding, AliasBinding,
+        ImplicitCastBinding, FreeTableRecipe, AttachedTableRecipe,
+        ColumnRecipe, ComplementRecipe, KernelRecipe, BindingRecipe,
+        IdentityRecipe, ChainRecipe, SubstitutionRecipe, ClosedRecipe,
+        InvalidRecipe, AmbiguousRecipe)
 
 
 class Probe(Clonable, Printable):
     pass
 
 
-class GuessNameProbe(Probe):
-    """
-    Represents a request for an attribute name.
-
-    The result of the probe is a string value -- an appropriate
-    name of a binding.
-    """
-
-    def __str__(self):
-        return "?<:=>"
-
-
-class GuessTitleProbe(Probe):
-    """
-    Represents a request for a title.
-
-    The result of this probe is a list of headings.
-    """
-
-    def __str__(self):
-        return "?<:as>"
-
-
 class GuessTagProbe(Probe):
     pass
 
         return "?<+|->"
 
 
-class CommandProbe(Probe):
-    pass
-
-
 class UnwrapProbe(Probe):
 
     def __init__(self, binding_class, is_deep=True):
         return set()
 
 
-class GuessName(Lookup):
-    # Generate an attribute name from a binging node.
-
-    adapt(Binding, GuessNameProbe)
-
-    def __call__(self):
-        # If the binding was induced by an identifier node,
-        # use the identifier name.
-        if isinstance(self.binding.syntax, IdentifierSyntax):
-            return self.binding.syntax.name
-        # Otherwise, fail to produce a name.
-        return None
-
-
-class GuessTitle(Lookup):
-    # Generate a sequence of headings for a binding node.
-
-    adapt(Binding, GuessTitleProbe)
-
-    def __call__(self):
-        # Generate a header from the associated syntax node.
-        return [unicode(self.binding.syntax)]
-
-
 class GuessTag(Lookup):
 
     adapt(Binding, GuessTagProbe)
 class LookupReferenceInScoping(Lookup):
     # Find a reference in a scoping node.
 
-    adapt(ScopingBinding, ReferenceProbe)
+    adapt(ScopeBinding, ReferenceProbe)
 
     def __call__(self):
         # Delegate reference lookups to the parent binding.
 class LookupReferenceSetInScoping(Lookup):
     # Find all available references in a scoping node.
 
-    adapt(ScopingBinding, ReferenceSetProbe)
+    adapt(ScopeBinding, ReferenceSetProbe)
 
     def __call__(self):
         # Delegate reference lookups to the parent binding.
                (ChainingBinding, ComplementProbe),
                (ChainingBinding, ExpansionProbe),
                (ChainingBinding, IdentityProbe),
-               (ChainingBinding, GuessTitleProbe),
-               (ChainingBinding, DirectionProbe))
+               (ChainingBinding, DirectionProbe),
+               (DecorateBinding, AttributeProbe),
+               (DecorateBinding, AttributeSetProbe),
+               (DecorateBinding, ReferenceProbe),
+               (DecorateBinding, ReferenceSetProbe),
+               (DecorateBinding, ComplementProbe),
+               (DecorateBinding, ExpansionProbe),
+               (DecorateBinding, IdentityProbe),
+               (DecorateBinding, DirectionProbe))
 
     def __call__(self):
         # Delegate all lookup requests to the parent binding.
         return lookup(self.binding.base, self.probe)
 
 
-class GuessNameFromChaining(Lookup):
-    # Generate an attribute name from a chaining binding.
-
-    adapt(ChainingBinding, GuessNameProbe)
-
-    def __call__(self):
-        # If the binding was induced by an identifier node,
-        # use the identifier name.
-        if isinstance(self.binding.syntax, IdentifierSyntax):
-            return self.binding.syntax.name
-        # Otherwise, pass the probe to the parent binding.
-        return lookup(self.binding.base, self.probe)
-
-
 class GuessTagFromChaining(Lookup):
 
-    adapt(ChainingBinding, GuessTagProbe)
+    adapt_many((ChainingBinding, GuessTagProbe),
+               (DecorateBinding, GuessTagProbe))
 
     def __call__(self):
         if isinstance(self.binding.syntax, IdentifierSyntax):
 
 class GuessHeaderInChaining(Lookup):
 
-    adapt(ChainingBinding, GuessHeaderProbe)
+    adapt_many((ChainingBinding, GuessHeaderProbe),
+               (DecorateBinding, GuessHeaderProbe))
 
     def __call__(self):
         return lookup(self.binding.base, self.probe)
 
 class GuessPathFromChaining(Lookup):
 
-    adapt(ChainingBinding, GuessPathProbe)
+    adapt_many((ChainingBinding, GuessPathProbe),
+               (DecorateBinding, GuessPathProbe))
 
     def __call__(self):
         return lookup(self.binding.base, self.probe)
 
 class LookupInImplicitCast(Lookup):
 
-    adapt_many((ImplicitCastBinding, GuessNameProbe),
-               (ImplicitCastBinding, GuessTitleProbe),
-               (ImplicitCastBinding, GuessTagProbe),
+    adapt_many((ImplicitCastBinding, GuessTagProbe),
                (ImplicitCastBinding, GuessHeaderProbe),
                (ImplicitCastBinding, GuessPathProbe),
                (ImplicitCastBinding, DirectionProbe))
         return None
 
 
-class LookupCommandInWrapping(Lookup):
-
-    adapt(WrappingBinding, CommandProbe)
-
-    def __call__(self):
-        return lookup(self.binding.base, self.probe)
-
-
 class UnwrapWrapping(Lookup):
 
-    adapt(WrappingBinding, UnwrapProbe)
+    adapt_many((WrappingBinding, UnwrapProbe),
+               (DecorateBinding, UnwrapProbe))
 
     def __call__(self):
         if isinstance(self.binding, self.probe.binding_class):
         return lookup(self.binding.base, self.probe)
 
 
-class GuessNameFromSegment(Lookup):
-    # Generate an attribute name from a segment binding.
-
-    adapt(SegmentBinding, GuessNameProbe)
-
-    def __call__(self):
-        # If available, use the name of the segment seed.
-        if self.binding.seed is not None:
-            return lookup(self.binding.seed, self.probe)
-        # Otherwise, fail to generate a name.
-        return None
-
-
-class GuessTitleFromSegment(Lookup):
-    # Generate a heading from a segment binding.
-
-    adapt(SegmentBinding, GuessTitleProbe)
-
-    def __call__(self):
-        # If available, use the heading of the segment seed.
-        if self.binding.seed is not None:
-            return lookup(self.binding.seed, self.probe)
-        # Otherwise, produce an empty heading.
-        return []
-
-
 class GuessFromSegment(Lookup):
 
     adapt_many((SegmentBinding, GuessTagProbe),
         return None
 
 
-class LookupCommandInCommand(Lookup):
-
-    adapt(CommandBinding, CommandProbe)
-
-    def __call__(self):
-        return self.binding.command
-
-
 class LookupAttributeInHome(Lookup):
     # Attributes of the *home* scope represent database tables.
 
         return None
 
 
-class GuessTitleFromHome(Lookup):
-    # Generate a title for a home scope.
-
-    adapt(HomeBinding, GuessTitleProbe)
-
-    def __call__(self):
-        # Produce no headers.
-        return []
-
-
 class GuessHeaderFromHome(Lookup):
 
     adapt(HomeBinding, GuessHeaderProbe)
         return chain(TableNode(self.binding.table))
 
 
-class GuessPathForFreeTable(Lookup):
+class GuessPathForTable(Lookup):
 
-    adapt(FreeTableBinding, GuessPathProbe)
+    adapt(TableBinding, GuessPathProbe)
 
     def __call__(self):
         path = lookup(self.binding.base, self.probe)
         return path+[arc]
 
 
-class GuessPathForAttachedTable(Lookup):
+class GuessPathForChain(Lookup):
 
-    adapt(AttachedTableBinding, GuessPathProbe)
+    adapt(ChainBinding, GuessPathProbe)
 
     def __call__(self):
         path = lookup(self.binding.base, self.probe)
         if not path:
             return None
         arc = None
-        # FIXME: fails for multi-join links.
         for label in classify(path[-1].target):
             if (isinstance(label.arc, ChainArc) and
-                    (label.arc.joins == [self.binding.join])):
+                    (label.arc.joins == self.binding.joins)):
                 arc = label.arc
                 break
         if arc is None:
                (ClipBinding, AttributeSetProbe),
                (ClipBinding, ComplementProbe),
                (ClipBinding, IdentityProbe),
-               (LocatorBinding, AttributeProbe),
-               (LocatorBinding, AttributeSetProbe),
-               (LocatorBinding, ComplementProbe),
-               (LocatorBinding, IdentityProbe))
+               (AttachBinding, AttributeProbe),
+               (AttachBinding, AttributeSetProbe),
+               (AttachBinding, ComplementProbe),
+               (AttachBinding, IdentityProbe),
+               (LocateBinding, AttributeProbe),
+               (LocateBinding, AttributeSetProbe),
+               (LocateBinding, ComplementProbe),
+               (LocateBinding, IdentityProbe))
 
     def __call__(self):
         # Delegate all lookup requests to the seed flow.
 
     adapt_many((CoverBinding, ExpansionProbe),
                (ClipBinding, ExpansionProbe),
-               (LocatorBinding, ExpansionProbe))
+               (LocateBinding, ExpansionProbe))
 
     def __call__(self):
         # Ignore pure selector expansion probes.
 
 class GuessTagHeaderFromLocatorClipPath(Lookup):
 
-    adapt_many((LocatorBinding, GuessTagProbe),
-               (LocatorBinding, GuessHeaderProbe),
-               (LocatorBinding, GuessPathProbe),
+    adapt_many((LocateBinding, GuessTagProbe),
+               (LocateBinding, GuessHeaderProbe),
+               (LocateBinding, GuessPathProbe),
                (ClipBinding, GuessTagProbe),
                (ClipBinding, GuessHeaderProbe),
                (ClipBinding, GuessPathProbe))
         return lookup(self.binding.base, probe)
 
 
-class LookupAttributeInLink(Lookup):
-    # Find an attribute in a link scope.
-
-    adapt_many((LinkBinding, AttributeProbe),
-               (LinkBinding, AttributeSetProbe),
-               (LinkBinding, ComplementProbe),
-               (LinkBinding, IdentityProbe))
-
-    def __call__(self):
-        # Delegate all lookup probes to the seed scope.
-        return lookup(self.binding.seed, self.probe)
-
-
-class ExpandLink(Lookup):
-    # Expand public columns in a link scope.
-
-    adapt(LinkBinding, ExpansionProbe)
-
-    def __call__(self):
-        # Ignore selection expand probes.
-        if not self.probe.with_class:
-            return super(ExpandLink, self).__call__()
-        # Delegate class expansion probe to the seed flow;
-        # turn off selection expansion to avoid expanding the
-        # selector in `image -> table{image}`.
-        probe = self.probe.clone(with_syntax=False, with_wild=False)
-        return lookup(self.binding.seed, probe)
-
-
-class GuessTitleFromLink(Lookup):
-    # Extract a heading from a link scope.
-
-    adapt(LinkBinding, GuessTitleProbe)
-
-    def __call__(self):
-        # Generate a heading from the link target.
-        return lookup(self.binding.seed, self.probe)
-
-
 class GuessHeaderFromLink(Lookup):
 
-    adapt(LinkBinding, GuessHeaderProbe)
+    adapt(AttachBinding, GuessHeaderProbe)
 
     def __call__(self):
         return lookup(self.binding.seed, self.probe)
 
 
-class GuessTitleFromRescoping(Lookup):
-    # Generate a title for a rescoping binding.
-
-    adapt(RescopingBinding, GuessTitleProbe)
-
-    def __call__(self):
-        # For a fragment:
-        #   scope{expression}
-        # generate a combined heading from `scope` and `expression`.
-        child_titles = lookup(self.binding.base, self.probe)
-        parent_titles = lookup(self.binding.scope, self.probe)
-        # Collapse repeating headers.
-        if parent_titles and child_titles:
-            if parent_titles[-1] == child_titles[0]:
-                parent_titles = parent_titles[:-1]
-        return parent_titles + child_titles
-
-
 class DirectRescoping(Lookup):
     # Extract a direction decorator from a rescoping binding.
 
         return base_direction * scope_direction
 
 
-class LookupAttributeInDefinition(Lookup):
+class LookupAttributeInDefine(Lookup):
     # Find an attribute in a definition binding.
 
-    adapt(DefinitionBinding, AttributeProbe)
+    adapt(DefineBinding, AttributeProbe)
 
     def __call__(self):
         # Check if the definition matches the probe.
-        if not self.binding.is_reference:
-            if self.binding.arity == self.probe.arity:
-                binding_key = normalize(self.binding.name)
-                if binding_key == self.probe.key:
-                    # If it matches, produce the associated recipe.
-                    return self.binding.recipe
-        # Otherwise, delegate the probe to the parent binding.
-        return super(LookupAttributeInDefinition, self).__call__()
-
-
-class LookupAttributeSetInDefinition(Lookup):
-    # Find all attributes in a definition binding.
-
-    adapt(DefinitionBinding, AttributeSetProbe)
-
-    def __call__(self):
-        attributes = super(LookupAttributeSetInDefinition, self).__call__()
-        if not self.binding.is_reference:
-            attributes.add((normalize(self.binding.name), self.binding.arity))
-        return attributes
-
-
-class LookupReferenceInDefinition(Lookup):
-    # Find a reference in a definition binding.
-
-    adapt(DefinitionBinding, ReferenceProbe)
-
-    def __call__(self):
-        # Check if the definition matches the probe.
-        if self.binding.is_reference:
+        if self.binding.arity == self.probe.arity:
             binding_key = normalize(self.binding.name)
             if binding_key == self.probe.key:
                 # If it matches, produce the associated recipe.
                 return self.binding.recipe
         # Otherwise, delegate the probe to the parent binding.
-        return super(LookupReferenceInDefinition, self).__call__()
+        return super(LookupAttributeInDefine, self).__call__()
 
 
-class LookupReferenceSetInDefinition(Lookup):
+class LookupAttributeSetInDefine(Lookup):
+    # Find all attributes in a definition binding.
+
+    adapt(DefineBinding, AttributeSetProbe)
+
+    def __call__(self):
+        attributes = super(LookupAttributeSetInDefine, self).__call__()
+        attributes.add((normalize(self.binding.name), self.binding.arity))
+        return attributes
+
+
+class LookupReferenceInDefineReference(Lookup):
+    # Find a reference in a definition binding.
+
+    adapt(DefineReferenceBinding, ReferenceProbe)
+
+    def __call__(self):
+        # Check if the definition matches the probe.
+        binding_key = normalize(self.binding.name)
+        if binding_key == self.probe.key:
+            # If it matches, produce the associated recipe.
+            return self.binding.recipe
+        # Otherwise, delegate the probe to the parent binding.
+        return super(LookupReferenceInDefineReference, self).__call__()
+
+
+class LookupReferenceSetInDefineReference(Lookup):
     # Find all references in a definition binding.
 
-    adapt(DefinitionBinding, ReferenceSetProbe)
+    adapt(DefineReferenceBinding, ReferenceSetProbe)
 
     def __call__(self):
-        references = super(LookupReferenceSetInDefinition, self).__call__()
-        if self.binding.is_reference:
-            references.add(normalize(self.binding.name))
+        references = super(LookupReferenceSetInDefineReference, self).__call__()
+        references.add(normalize(self.binding.name))
         return references
 
 
+class LookupComplementInDefineLift(Lookup):
+
+    adapt(DefineLiftBinding, ComplementProbe)
+
+    def __call__(self):
+        return self.binding.recipe
+
+
 class ExpandSelection(Lookup):
     # Expand a selector operation.
 
         return lookup(self.binding.target, self.probe)
 
 
-class GuessTitleFromTitle(Lookup):
-    # Extract the title from a title decorator.
-
-    adapt(TitleBinding, GuessTitleProbe)
-
-    def __call__(self):
-        return [self.binding.title]
-
-
 class GuessHeaderFromTitle(Lookup):
 
     adapt(TitleBinding, GuessHeaderProbe)
         return super(GuessTagFromTitle, self).__call__()
 
 
-class GuessNameFromAlias(Lookup):
-    # Extract an attribute name from a syntax decorator.
-
-    adapt(AliasBinding, GuessNameProbe)
-
-    def __call__(self):
-        # If the binding is associated with an identifier node,
-        # use the identifier name.
-        if isinstance(self.binding.syntax, IdentifierSyntax):
-            return self.binding.syntax.name
-        # Otherwise, fail to produce a name.
-        return None
-
-
-class GuessTitleFromAlias(Lookup):
-    # Extract a title from a syntax decorator.
-
-    adapt(AliasBinding, GuessTitleProbe)
-
-    def __call__(self):
-        return [str(self.binding.syntax)]
-
-
 class GuessTagFromAlias(Lookup):
 
     adapt(AliasBinding, GuessTagProbe)
     return lookup(binding, probe)
 
 
-#def guess_name(binding):
-#    """
-#    Extracts an attribute name from the given binding.
-#
-#    Returns a string value; ``None`` if the node is not associated
-#    with any attribute.
-#    """
-#    probe = GuessNameProbe()
-#    return lookup(binding, probe)
-
-
-#def guess_title(binding):
-#    """
-#    Extracts a heading from the given binding.
-#
-#    Returns a list of string values: the header associated with
-#    the binding node.
-#    """
-#    probe = GuessTitleProbe()
-#    return lookup(binding, probe)
-
-
 def guess_tag(binding):
     probe = GuessTagProbe()
     return lookup(binding, probe)
     return lookup(binding, probe)
 
 
-def lookup_command(binding):
-    probe = CommandProbe()
-    return lookup(binding, probe)
-
-
 def unwrap(binding, binding_class, is_deep=True):
     probe = UnwrapProbe(binding_class, is_deep)
     return lookup(binding, probe)

src/htsql/core/tr/rewrite.py

 from .coerce import coerce
 from .flow import (Expression, QueryExpr, SegmentCode, Flow, RootFlow,
         FiberTableFlow, QuotientFlow, ComplementFlow, MonikerFlow, ForkedFlow,
-        LinkedFlow, ClippedFlow, LocatorFlow, FilteredFlow, OrderedFlow, Code,
+        AttachFlow, ClippedFlow, LocatorFlow, FilteredFlow, OrderedFlow, Code,
         LiteralCode, CastCode, RecordCode, IdentityCode, AnnihilatorCode,
         FormulaCode, Unit, ColumnUnit, CompoundUnit, ScalarUnit,
         AggregateUnitBase, AggregateUnit, KernelUnit, CoveringUnit)
-from .signature import Signature, OrSig, AndSig
+from .signature import Signature, OrSig, AndSig, IsEqualSig, isformula
 # FIXME: move `IfSig` and `SwitchSig` to `htsql.core.tr.signature`.
 from .fn.signature import IfSig
 
         return self.flow.clone(base=base, seed=seed)
 
 
-class RewriteLocator(RewriteFlow):
-
-    adapt(LocatorFlow)
-
-    def __call__(self):
-        #if self.flow.base.dominates(self.flow.seed):
-        #    flow = FilteredFlow(self.flow.seed, self.flow.filter,
-        #                        self.flow.binding)
-        #    return self.state.rewrite(flow)
-        base = self.state.rewrite(self.flow.base)
-        seed = self.state.rewrite(self.flow.seed)
-        filter = self.state.rewrite(self.flow.filter)
-        return self.flow.clone(base=base, seed=seed, filter=filter)
-
-
-class UnmaskLocator(UnmaskFlow):
-
-    adapt(LocatorFlow)
-
-    def __call__(self):
-        # Unmask the seed flow against the parent flow.
-        seed = self.state.unmask(self.flow.seed, mask=self.flow.base)
-        # Unmask the parent flow against the current mask.
-        base = self.state.unmask(self.flow.base)
-        filter = self.state.unmask(self.flow.filter, mask=self.flow.seed)
-        return self.flow.clone(base=base, seed=seed, filter=filter)
-
-
-class ReplaceLocator(Replace):
-
-    adapt(LocatorFlow)
-
-    def __call__(self):
-        base = self.state.replace(self.flow.base)
-        substate = self.state.spawn()
-        substate.collect(self.flow.seed)
-        substate.collect(self.flow.filter)
-        substate.recombine()
-        seed = substate.replace(self.flow.seed)
-        filter = substate.replace(self.flow.filter)
-        return self.flow.clone(base=base, seed=seed, filter=filter)
-
-
 class RewriteForked(RewriteFlow):
 
     adapt(ForkedFlow)
         return self.flow.clone(base=base, seed=seed, kernels=kernels)
 
 
-class RewriteLinked(RewriteFlow):
+class RewriteAttach(RewriteFlow):
 
-    adapt(LinkedFlow)
+    adapt(AttachFlow)
 
     def __call__(self):
         # Rewrite the child nodes.
         seed = self.state.rewrite(self.flow.seed)
         images = [(self.state.rewrite(lcode), self.state.rewrite(rcode))
                   for lcode, rcode in self.flow.images]
-        return self.flow.clone(base=base, seed=seed, images=images)
+        filter = self.flow.filter
+        if filter is not None:
+            filter = self.state.rewrite(filter)
+            if (isinstance(filter, LiteralCode) and
+                isinstance(filter.domain, BooleanDomain) and
+                filter.value is True):
+                filter = None
+        predicates = []
+        all_images = images
+        images = []
+        for lcode, rcode in all_images:
+            if not lcode.units:
+                code = FormulaCode(IsEqualSig(+1), BooleanDomain(),
+                                   self.flow.binding, lop=rcode, rop=lcode)
+                predicates.append(code)
+            else:
+                images.append((lcode, rcode))
+        if filter is not None:
+            if isformula(filter, AndSig):
+                ops = filter.ops
+            else:
+                ops = [filter]
+            for op in ops:
+                if (isformula(op, IsEqualSig) and
+                        op.signature.polarity == +1):
+                    if (op.lop.units and
+                            all(self.flow.base.spans(unit.flow)
+                                for unit in op.lop.units) and
+                            any(not self.flow.base.spans(unit.flow)
+                                for unit in op.rop.units)):
+                        images.append((op.lop, op.rop))
+                        continue
+                    if (op.rop.units and
+                            all(self.flow.base.spans(unit.flow)
+                                for unit in op.rop.units) and
+                            any(not self.flow.base.spans(unit.flow)
+                                for unit in op.lop.units)):
+                        images.append((op.rop, op.lop))
+                        continue
+                predicates.append(op)
+        if len(predicates) == 0:
+            filter = None
+        elif len(predicates) == 1:
+            [filter] = predicates
+        else:
+            filter = FormulaCode(AndSig(), BooleanDomain(),
+                                 self.flow.binding, ops=predicates)
+        return self.flow.clone(base=base, seed=seed, images=images,
+                               filter=filter)
 
 
-class UnmaskLinked(UnmaskFlow):
+class UnmaskAttach(UnmaskFlow):
 
-    adapt(LinkedFlow)
+    adapt(AttachFlow)
 
     def __call__(self):
         # Unmask the parent flow.
         images = [(self.state.unmask(lcode, mask=self.flow.base),
                    self.state.unmask(rcode, mask=self.flow.seed))
                   for lcode, rcode in self.flow.images]
-        return self.flow.clone(base=base, seed=seed, images=images)
+        filter = None
+        if self.flow.filter is not None:
+            filter = self.state.unmask(self.flow.filter, mask=self.flow.seed)
+        return self.flow.clone(base=base, seed=seed, images=images,
+                               filter=filter)
 
 
-class CollectLinked(Collect):
+class CollectAttach(Collect):
 
-    adapt(LinkedFlow)
+    adapt(AttachFlow)
 
     def __call__(self):
         # Gather units in the parent flow and the parent images.
             self.state.collect(lcode)