Kirill Simonov avatar Kirill Simonov committed 03d2595

Reviewed binding nodes and the binding process.

Added comparison operator to domain instances.
Refactored the Bind adapter: introduced a `BindingState` object.
Separated lookup into two adapters: Lookup, and Itemize.
Moved UnaryCoerce and BinaryCoerce adapters to a separate module.
Refactored binding nodes: removed the parent attribute from most of the nodes.
Updated API documentation to list modules in alphabetical order.
Added docstrings and comments.

Comments (0)

Files changed (25)

 
     # make doc
 
-Note that this requires Sphinx 1.0, which is not yet released.
+Note that this requires Sphinx 1.0+.
 
 
 Running HTSQL
    :maxdepth: 2
 
    api/htsql
-   api/htsql_tr
-   api/htsql_ctl
+   api/htsql.ctl
+   api/htsql.tr
+   api/htsql.tr.fn
+   api/htsql_pgsql
    api/htsql_sqlite
-   api/htsql_pgsql
 

doc/api/htsql.ctl.rst

+================================
+  The :mod:`htsql.ctl` package
+================================
+
+.. automodule:: htsql.ctl
+   :members:
+.. automodule:: htsql.ctl.default
+   :members:
+.. automodule:: htsql.ctl.error
+   :members:
+.. automodule:: htsql.ctl.help
+   :members:
+.. automodule:: htsql.ctl.option
+   :members:
+.. automodule:: htsql.ctl.server
+   :members:
+.. automodule:: htsql.ctl.shell
+   :members:
+.. automodule:: htsql.ctl.regress
+   :members:
+.. automodule:: htsql.ctl.request
+   :members:
+.. automodule:: htsql.ctl.routine
+   :members:
+.. automodule:: htsql.ctl.script
+   :members:
+.. automodule:: htsql.ctl.version
+   :members:
+

doc/api/htsql.rst

 
 .. automodule:: htsql
    :members:
+.. automodule:: htsql.adapter
+   :members:
+.. automodule:: htsql.addon
+   :members:
+.. automodule:: htsql.application
+   :members:
+.. automodule:: htsql.connect
+   :members:
+.. automodule:: htsql.context
+   :members:
+.. automodule:: htsql.domain
+   :members:
+.. automodule:: htsql.entity
+   :members:
+.. automodule:: htsql.error
+   :members:
 .. automodule:: htsql.export
    :members:
+.. automodule:: htsql.introspect
+   :members:
+.. automodule:: htsql.mark
+   :members:
+.. automodule:: htsql.split_sql
+   :members:
 .. automodule:: htsql.util
    :members:
 .. automodule:: htsql.validator
    :members:
-.. automodule:: htsql.application
-   :members:
-.. automodule:: htsql.context
-   :members:
-.. automodule:: htsql.adapter
-   :members:
-.. automodule:: htsql.addon
-   :members:
-.. automodule:: htsql.entity
-   :members:
-.. automodule:: htsql.domain
-   :members:
-.. automodule:: htsql.mark
-   :members:
-.. automodule:: htsql.error
-   :members:
 .. automodule:: htsql.wsgi
    :members:
-.. automodule:: htsql.connect
-   :members:
-.. automodule:: htsql.split_sql
-   :members:
-.. automodule:: htsql.introspect
-   :members:
 

doc/api/htsql.tr.fn.rst

+==================================
+  The :mod:`htsql.tr.fn` package
+==================================
+
+.. automodule:: htsql.tr.fn
+   :members:
+.. automodule:: htsql.tr.fn.function
+   :members:
+

doc/api/htsql.tr.rst

+===============================
+  The :mod:`htsql.tr` package
+===============================
+
+.. automodule:: htsql.tr
+   :members:
+.. automodule:: htsql.tr.bind
+   :members:
+.. automodule:: htsql.tr.binding
+   :members:
+.. automodule:: htsql.tr.coerce
+   :members:
+.. automodule:: htsql.tr.error
+   :members:
+.. automodule:: htsql.tr.lookup
+   :members:
+.. automodule:: htsql.tr.parse
+   :members:
+.. automodule:: htsql.tr.scan
+   :members:
+.. automodule:: htsql.tr.syntax
+   :members:
+.. automodule:: htsql.tr.token
+   :members:
+

doc/api/htsql_ctl.rst

-================================
-  The :mod:`htsql.ctl` package
-================================
-
-.. automodule:: htsql.ctl
-   :members:
-.. automodule:: htsql.ctl.script
-   :members:
-.. automodule:: htsql.ctl.error
-   :members:
-.. automodule:: htsql.ctl.option
-   :members:
-.. automodule:: htsql.ctl.routine
-   :members:
-.. automodule:: htsql.ctl.default
-   :members:
-.. automodule:: htsql.ctl.version
-   :members:
-.. automodule:: htsql.ctl.help
-   :members:
-.. automodule:: htsql.ctl.server
-   :members:
-.. automodule:: htsql.ctl.request
-   :members:
-.. automodule:: htsql.ctl.shell
-   :members:
-.. automodule:: htsql.ctl.regress
-   :members:
-

doc/api/htsql_pgsql.rst

 
 .. automodule:: htsql_pgsql
    :members:
-.. automodule:: htsql_pgsql.export
+.. automodule:: htsql_pgsql.connect
    :members:
 .. automodule:: htsql_pgsql.domain
    :members:
-.. automodule:: htsql_pgsql.connect
+.. automodule:: htsql_pgsql.export
+   :members:
+.. automodule:: htsql_pgsql.introspect
    :members:
 .. automodule:: htsql_pgsql.split_sql
    :members:
-.. automodule:: htsql_pgsql.introspect
-   :members:
 

doc/api/htsql_sqlite.rst

 
 .. automodule:: htsql_sqlite
    :members:
-.. automodule:: htsql_sqlite.export
+.. automodule:: htsql_sqlite.connect
    :members:
 .. automodule:: htsql_sqlite.domain
    :members:
-.. automodule:: htsql_sqlite.connect
+.. automodule:: htsql_sqlite.export
+   :members:
+.. automodule:: htsql_sqlite.introspect
    :members:
 .. automodule:: htsql_sqlite.split_sql
    :members:
-.. automodule:: htsql_sqlite.introspect
-   :members:
 

doc/api/htsql_tr.rst

-===============================
-  The :mod:`htsql.tr` package
-===============================
-
-.. automodule:: htsql.tr
-   :members:
-.. automodule:: htsql.tr.error
-   :members:
-.. automodule:: htsql.tr.token
-   :members:
-.. automodule:: htsql.tr.scan
-   :members:
-.. automodule:: htsql.tr.syntax
-   :members:
-.. automodule:: htsql.tr.parse
-   :members:
-

src/htsql/domain.py

     def __repr__(self):
         return "<%s %s>" % (self.__class__.__name__, self)
 
+    def __eq__(self, other):
+        # Used when comparing some of the code objects.  The generic
+        # implementations check that the classes are identical and
+        # all attributes are equal; concrete SQL domains may override
+        # this method to provide engine-specific type equality.
+        if not isinstance(other, Domain):
+            return False
+        return (self.__class__ == other.__class__)
+
 
 class VoidDomain(Domain):
     """
         # Represent an integer value as a decimal number.
         return str(value)
 
+    def __eq__(self, other):
+        if not isinstance(other, Domain):
+            return False
+        return (self.__class__ == other.__class__ and self.size == other.size)
+
 
 class FloatDomain(NumberDomain):
     """
         Number of bits used to store a value; ``None`` if not known.
     """
 
-
     is_exact = False
     radix = 2
 
         # Use `repr` to avoid loss of precision.
         return repr(value)
 
+    def __eq__(self, other):
+        if not isinstance(other, Domain):
+            return False
+        return (self.__class__ == other.__class__ and self.size == other.size)
+
 
 class DecimalDomain(NumberDomain):
     """
         # Produce a decimal representation of the number.
         return str(value)
 
+    def __eq__(self, other):
+        if not isinstance(other, Domain):
+            return False
+        return (self.__class__ == other.__class__ and
+                self.precision == other.precision and
+                self.scale == other.scale)
+
 
 class StringDomain(Domain):
     """
         # No conversion is required for string values.
         return value
 
+    def __eq__(self, other):
+        if not isinstance(other, Domain):
+            return False
+        return (self.__class__ == other.__class__ and
+                self.length == other.length and
+                self.is_varying == other.is_varying)
+
 
 class EnumDomain(Domain):
     """
         # No conversion is required.
         return value
 
+    def __eq__(self, other):
+        if not isinstance(other, Domain):
+            return False
+        # Here we check equality by comparing the labels.  Concrete SQL enum
+        # types should probably override this method to provide engine-specific
+        # comparison.
+        return (self.__class__ == other.__class__ and
+                self.labels == other.labels)
+
 
 class DateDomain(Domain):
     """

src/htsql/request.py

 from .connect import DBError, Connect, Normalize
 from .error import EngineError
 from .tr.parse import parse
-from .tr.binder import Binder
+from .tr.bind import bind
 from .tr.encoder import Encoder
 from .tr.assembler import Assembler
 from .tr.outliner import Outliner
 
     def translate(self):
         syntax = parse(self.uri)
-        binder = Binder()
-        binding = binder.bind_one(syntax)
+        binding = bind(syntax)
         encoder = Encoder()
         code = encoder.encode(binding)
         assembler = Assembler()

src/htsql/tr/bind.py

+#
+# Copyright (c) 2006-2010, Prometheus Research, LLC
+# Authors: Clark C. Evans <cce@clarkevans.com>,
+#          Kirill Simonov <xi@resolvent.net>
+#
+
+
+"""
+:mod:`htsql.tr.bind`
+====================
+
+This module implements the binding process.
+"""
+
+
+from ..adapter import Adapter, adapts
+from ..context import context
+from ..domain import (BooleanDomain, IntegerDomain, DecimalDomain,
+                      FloatDomain, UntypedDomain)
+from .error import BindError
+from .syntax import (Syntax, QuerySyntax, SegmentSyntax, SelectorSyntax,
+                     SieveSyntax, OperatorSyntax, FunctionOperatorSyntax,
+                     FunctionCallSyntax, GroupSyntax, SpecifierSyntax,
+                     IdentifierSyntax, WildcardSyntax, StringSyntax,
+                     NumberSyntax)
+from .binding import (Binding, RootBinding, QueryBinding, SegmentBinding,
+                      LiteralBinding, SieveBinding, CastBinding,
+                      WrapperBinding)
+from .lookup import lookup, itemize
+from .coerce import coerce
+from .fn.function import call
+import decimal
+
+
+class BindingState(object):
+    """
+    Encapsulates the (mutable) state of the binding process.
+
+    State attributes:
+
+    `base` (:class:`htsql.tr.binding.Binding`)
+        The current lookup context.
+    """
+
+    def __init__(self):
+        # The current lookup context.
+        self.base = None
+        # The stack of previous lookup contexts.
+        self.base_stack = []
+
+    def push_base(self, base):
+        """
+        Sets the new lookup context.
+
+        This function stores the current context in the stack and makes
+        the given binding `base` the new lookup context.  Use the
+        :attr:`base` attribute to get the current context; :meth:`pop_base`
+        to restore the previous context.
+
+        `base` (:class:`htsql.tr.binding.Binding`)
+            The new lookup context.
+        """
+        # Sanity check on the argument.
+        assert isinstance(base, Binding)
+        # Save the current lookup context.
+        self.base_stack.append(self.base)
+        # Assign the new lookup context.
+        self.base = base
+
+    def pop_base(self):
+        """
+        Restores the previous lookup context.
+
+        This functions restores the previous lookup context from the stack.
+        Use the :attr:`base` attribute to get the current context;
+        :meth:`push_base` to change the current context.
+        """
+        # Restore the prevous lookup context from the stack.
+        self.base = self.base_stack.pop()
+
+    def bind_all(self, syntax, base=None):
+        """
+        Binds the given syntax node using the current binding state.
+
+        Returns a list of generated binding nodes.
+
+        `syntax` (:class:`htsql.tr.syntax.Syntax`)
+            The syntax node to bind.
+
+        `base` (:class:`htsql.tr.binding.Binding` or ``None``)
+            If set, the lookup context is set to `base` when
+            binding the syntax node.
+        """
+        return bind_all(syntax, self, base)
+
+    def bind(self, syntax, base=None):
+        """
+        Binds the given syntax node using the current binding state.
+
+        Returns a binding node.  This function raises an error if none
+        or more than one node are produced.
+
+        `syntax` (:class:`htsql.tr.syntax.Syntax`)
+            The syntax node to bind.
+
+        `base` (:class:`htsql.tr.binding.Binding` or ``None``)
+            If set, the lookup context is set to `base` when
+            binding the syntax node.
+        """
+        return bind(syntax, self, base)
+
+    def call(self, syntax, base=None):
+        """
+        Binds the given function call node using the current binding state.
+
+        Returns a list of binding nodes.
+
+        `syntax` (:class:`htsql.tr.syntax.CallSyntax`)
+            The syntax node to bind.
+
+        `base` (:class:`htsql.tr.binding.Binding` or ``None``)
+            If set, the lookup context is set to `base` when
+            binding the syntax node.
+        """
+        return call(syntax, self, base)
+
+
+class Bind(Adapter):
+    """
+    Translates a syntax node to a sequence of binding nodes.
+
+    This is an interface adapter; see subclasses for implementations.
+
+    The binding process translates a syntax tree to a binding tree.  The
+    primary purpose of binding is to resolve identifiers against database
+    objects, resolve an validate function and operator calls and determine
+    types of all expressions.
+
+    The :class:`Bind` adapter has the following signature::
+
+        Bind: (Syntax, State) -> (Binding ...)
+
+    The adapter is polymorphic on the `Syntax` argument.
+
+    `syntax` (:class:`htsql.tr.syntax.Syntax`)
+        The syntax node to bind.
+
+    `state` (:class:`BindingState`)
+        The current state of the binding process.
+    """
+
+    adapts(Syntax)
+
+    def __init__(self, syntax, state):
+        assert isinstance(syntax, Syntax)
+        assert isinstance(state, BindingState)
+        self.syntax = syntax
+        self.state = state
+
+    def __call__(self):
+        # The default implementation raises an error.  It is actually
+        # unreachable since we provide an implementation for all syntax nodes.
+        raise BindError("unable to bind a node", self.syntax.mark)
+
+
+class BindQuery(Bind):
+    """
+    Binds the top-level syntax node :class:`htsql.tr.syntax.QuerySyntax`.
+
+    Produces a :class:`htsql.tr.binding.QueryBinding` node.
+    """
+
+    adapts(QuerySyntax)
+
+    def __call__(self):
+        # Set the root lookup context: `RootBinding` represents a scalar
+        # context with `lookup` implemented as table lookup.
+        root = RootBinding(self.syntax)
+        self.state.push_base(root)
+        # Bind the segment node if it is available.
+        segment = None
+        if self.syntax.segment is not None:
+            segment = self.state.bind(self.syntax.segment)
+        # Restore the original lookup context.
+        self.state.pop_base()
+        # Construct and return the top-level binding node.
+        yield QueryBinding(root, segment, self.syntax)
+
+
+class BindSegment(Bind):
+    """
+    Binds a :class:`htsql.tr.syntax.SegmentSyntax` node.
+
+    Produces a :class:`htsql.tr.binding.SegmentBinding` node.
+    """
+
+    adapts(SegmentSyntax)
+
+    def __call__(self):
+        # To construct a segment binding, we determine its base and its
+        # elements.  Note that the selector node has the form:
+        #   /base{selector}?filter
+        # (where the selector and the filter nodes are optional) or
+        #   /{selector}
+        # Typically the base and the filter nodes are bound to construct
+        # the segment base and the selector is bound to construct the segment
+        # elements.
+
+        # If the syntax node has the form:
+        #   /{selector}
+        # we take the current lookup context as the segment base.
+        base = self.state.base
+        # Othewise, for queries `/base{selector}?filter` and `/base{selector}`
+        # we bind the nodes `(base?filter)` and `base` respectively
+        # to get the segment base.
+        if self.syntax.base is not None:
+            if self.syntax.filter is not None:
+                base_syntax = SieveSyntax(self.syntax.base, None,
+                                          self.syntax.filter, self.syntax.mark)
+                base_syntax = GroupSyntax(base_syntax, self.syntax.mark)
+                base = self.state.bind(base_syntax)
+            else:
+                base = self.state.bind(self.syntax.base)
+        # Bind the selector against the base to get the segment elements.
+        if self.syntax.selector is not None:
+            bare_elements = self.state.bind_all(self.syntax.selector, base)
+        else:
+            # No selector means that the segment has the form:
+            #   / base   or   / base ?filter
+            # This is a special case: depending on whether the base is
+            # enumerable, it is interpreted either as
+            #   / base {*}
+            # or as
+            #   / {base}
+            bare_elements = itemize(base, base.syntax)
+            if bare_elements is None:
+                bare_elements = [base]
+                base = self.state.base
+        # Validate and specialize the domains of the elements.
+        elements = []
+        for element in bare_elements:
+            domain = coerce(element.domain)
+            if domain is None:
+                raise BindError("invalid element type", element.mark)
+            element = CastBinding(element, domain, element.syntax)
+            elements.append(element)
+        # Generate a segment binding.
+        yield SegmentBinding(base, elements, self.syntax)
+
+
+class BindSelector(Bind):
+    """
+    Binds a :class:`htsql.tr.syntax.SelectorSyntax` node.
+
+    Produces a sequence (possibly empty) of binding nodes.
+    """
+
+    adapts(SelectorSyntax)
+
+    def __call__(self):
+        # The selector node has the form:
+        #   {element,...}
+        # We iterate over the elements to bind them.
+        for element in self.syntax.elements:
+            for binding in self.state.bind_all(element):
+                yield binding
+
+
+class BindSieve(Bind):
+    """
+    Bind a :class:`htsql.tr.syntax.SieveSyntax` node.
+
+    Produces a sequence (possibly empty) of binding nodes.
+    """
+
+    adapts(SieveSyntax)
+
+    def __call__(self):
+        # A sieve node admits one of two forms.  The first form
+        #   /base?filer
+        # produces a sieve binding node.  The second form
+        #   /base{selector}?filter
+        # generates a sieve binding node and uses it as a lookup
+        # context when binding the selector.  The binding nodes
+        # produced by the selector are returned.
+
+        if self.syntax.selector is None:
+            # Handle the case `/base?filter`: generate and return
+            # a sieve binding.
+            base = self.state.bind(self.syntax.base)
+            # Note: this condition is always satisfied.
+            if self.syntax.filter is not None:
+                filter = self.state.bind(self.syntax.filter, base)
+                filter = CastBinding(filter, coerce(BooleanDomain()),
+                                     filter.syntax)
+                base = SieveBinding(base, filter, self.syntax)
+            yield base
+
+        else:
+            # Handle the cases `/base{selector}` and `/base{selector}?filter`:
+            # bind and return the selector using `base` or `base?filter` as
+            # the lookup context.
+
+            # Generate the new lookup context.
+            if self.syntax.filter is not None:
+                # Generate a new syntax node `(base?filter)` and bind it.
+                base_syntax = SieveSyntax(self.syntax.base, None,
+                                          self.syntax.filter, self.syntax.mark)
+                base_syntax = GroupSyntax(base_syntax, self.syntax.mark)
+                base = self.state.bind(base_syntax)
+            else:
+                base = self.state.bind(self.syntax.base)
+
+            # Bind and return the selector.
+            for binding in self.state.bind_all(self.syntax.selector, base):
+                # Wrap the binding nodes to change the associated syntax node.
+                # We replace `element` with `base{element}`.
+                selector_syntax = SelectorSyntax([binding.syntax],
+                                                 binding.mark)
+                binding_syntax = SieveSyntax(self.syntax.base,
+                                             selector_syntax,
+                                             self.syntax.filter,
+                                             binding.mark)
+                binding = WrapperBinding(binding, binding_syntax)
+                yield binding
+
+
+class BindOperator(Bind):
+    """
+    Binds an :class:`htsql.tr.syntax.OperatorSyntax` node.
+    """
+
+    adapts(OperatorSyntax)
+
+    def __call__(self):
+        # The operator node has one of the forms:
+        #   <lop><symbol><rop>, <lop><symbol>, <symbol><rop>.
+
+        # Find and bind the operator.
+        return self.state.call(self.syntax)
+
+
+class BindFunctionOperator(Bind):
+    """
+    Binds a :class:`htsql.tr.syntax.FunctionOperatorSyntax` node.
+    """
+
+    adapts(FunctionOperatorSyntax)
+
+    def __call__(self):
+        # A function operator node has the form:
+        #   <lop> <identifier> <rop>
+
+        # Find and bind the function.
+        return self.state.call(self.syntax)
+
+
+class BindFunctionCall(Bind):
+    """
+    Binds a :class:`htsql.tr.syntax.FunctionCallSyntax` node.
+    """
+
+    adapts(FunctionCallSyntax)
+
+    def __call__(self):
+        # A function call has one of the forms:
+        #   `identifier(argument,...)` or `base.identifier(argument,...)`.
+        # When `base` is set, it is used as the lookup context when binding
+        # the function and its arguments.
+
+        # Get the lookup context of the function.
+        base = self.state.base
+        if self.syntax.base is not None:
+            base = self.state.bind(self.syntax.base)
+        # Find and bind the function.
+        return self.state.call(self.syntax, base)
+
+
+class BindGroup(Bind):
+    """
+    Binds a :class:`htsql.tr.syntax.GroupSyntax` node.
+    """
+
+    adapts(GroupSyntax)
+
+    def __call__(self):
+        # A group node has the form:
+        #   ( expression )
+
+        # Bind the expression and wrap the result to add parentheses
+        # around the syntax node.
+        for binding in self.state.bind_all(self.syntax.expression):
+            binding_syntax = GroupSyntax(binding.syntax, binding.mark)
+            binding = WrapperBinding(binding, binding_syntax)
+            yield binding
+
+
+class BindSpecifier(Bind):
+    """
+    Binds a :class:`htsql.tr.syntax.SpecifierSyntax` node.
+    """
+
+    adapts(SpecifierSyntax)
+
+    def __call__(self):
+        # A specifier node has the form:
+        #   `base.identifier` or `base.*`
+
+        # Bind `base` and use it as the lookup context when binding
+        # the identifier.
+        base = self.state.bind(self.syntax.base)
+        for binding in self.state.bind_all(self.syntax.identifier, base):
+            # Wrap the binding node to update the associated syntax node.
+            # Note `identifier` is replaced with `base.identifier`.
+            # FIXME: Will fail if `binding.syntax` is not an identifier
+            # or a wildcard node.  Currently, `binding.syntax` is always
+            # an identifier node, but that might change in the future.
+            binding_syntax = SpecifierSyntax(base.syntax, binding.syntax,
+                                             binding.mark)
+            binding = WrapperBinding(binding, binding_syntax)
+            yield binding
+
+
+class BindIdentifier(Bind):
+    """
+    Binds an :class:`htsql.tr.syntax.IdentifierSyntax` node.
+    """
+
+    adapts(IdentifierSyntax)
+
+    def __call__(self):
+        # Look for the identifier in the current lookup context.
+        binding = lookup(self.state.base, self.syntax)
+        if binding is None:
+            raise BindError("unable to resolve an identifier",
+                            self.syntax.mark)
+        yield binding
+
+
+class BindWildcard(Bind):
+    """
+    Binds a :class:`htsql.tr.syntax.WildcardSyntax` node.
+    """
+
+    adapts(WildcardSyntax)
+
+    def __call__(self):
+        # Get all public descendants in the current lookup context.
+        bindings = itemize(self.state.base, self.syntax)
+        if bindings is None:
+            raise BindError("unable to resolve a wildcard",
+                            self.syntax.mark)
+        for binding in bindings:
+            yield binding
+
+
+class BindString(Bind):
+    """
+    Binds a :class:`htsql.tr.syntax.StringSyntax` node.
+    """
+
+    adapts(StringSyntax)
+
+    def __call__(self):
+        # Bind a quoted literal.  Note that a quoted literal not necessarily
+        # represents a string value; its initial domain is untyped.
+        binding = LiteralBinding(self.syntax.value,
+                                 UntypedDomain(),
+                                 self.syntax)
+        yield binding
+
+
+class BindNumber(Bind):
+    """
+    Binds a :class:`htsql.tr.syntax.NumberSyntax` node.
+    """
+
+    adapts(NumberSyntax)
+
+    def __call__(self):
+        # Bind an unquoted (numeric) literal.
+
+        # Create an untyped literal binding.
+        binding = LiteralBinding(self.syntax.value,
+                                 UntypedDomain(),
+                                 self.syntax)
+
+        # Cast the binding to an appropriate numeric type.
+        value = self.syntax.value
+        # If the literal uses the exponential notation, assume it's
+        # a float number.
+        if 'e' in value or 'E' in value:
+            domain = coerce(FloatDomain())
+        # If the literal uses the decimal notation, assume it's
+        # a decimal number.
+        elif '.' in value:
+            domain = coerce(DecimalDomain())
+        # Otherwise, it's an integer.
+        else:
+            domain = coerce(IntegerDomain())
+        binding = CastBinding(binding, domain, self.syntax)
+        yield binding
+
+
+def bind_all(syntax, state=None, base=None):
+    """
+    Binds the given syntax node.
+
+    Returns a list of generated binding nodes.
+
+    `syntax` (:class:`htsql.tr.syntax.Syntax`)
+        The syntax node to bind.
+
+    `state` (:class:`BindingState` or ``None``).
+        The binding state to use.  If not set, a new binding state
+        is created.
+
+    `base` (:class:`htsql.tr.binding.Binding` or ``None``)
+        If set, the lookup context is set to `base` when
+        binding the node.
+    """
+    # Create a new binding state if necessary.
+    if state is None:
+        state = BindingState()
+    # If passed, set the new lookup context.
+    if base is not None:
+        state.push_base(base)
+    # Realize and apply the `Bind` adapter.
+    bind = Bind(syntax, state)
+    bindings = list(bind())
+    # Restore the old lookup context.
+    if base is not None:
+        state.pop_base()
+    # Return the binding nodes.
+    return bindings
+
+
+def bind(syntax, state=None, base=None):
+    """
+    Binds the given syntax node.
+
+    Returns a binding node.  This function raises an error if no nodes
+    or more than one node are produced.
+
+    `syntax` (:class:`htsql.tr.syntax.Syntax`)
+        The syntax node to bind.
+
+    `state` (:class:`BindingState` or ``None``).
+        The binding state to use.  If not set, a new binding state
+        is created.
+
+    `base` (:class:`htsql.tr.binding.Binding` or ``None``)
+        If set, the lookup context is set to `base` when binding
+        the node.
+    """
+    # Bind the syntax node.
+    bindings = bind_all(syntax, state, base)
+    # Ensure we got exactly one binding node back.
+    if len(bindings) != 1:
+        raise BindError("unexpected selector or wildcard expression",
+                        syntax.mark)
+    return bindings[0]
+
+

src/htsql/tr/binder.py

-#
-# Copyright (c) 2006-2010, Prometheus Research, LLC
-# Authors: Clark C. Evans <cce@clarkevans.com>,
-#          Kirill Simonov <xi@resolvent.net>
-#
-
-
-"""
-:mod:`htsql.tr.binder`
-======================
-
-This module implements binding adapters.
-"""
-
-
-from ..adapter import Adapter, adapts
-from .syntax import (Syntax, QuerySyntax, SegmentSyntax, SelectorSyntax,
-                     SieveSyntax, OperatorSyntax, FunctionOperatorSyntax,
-                     FunctionCallSyntax, GroupSyntax, SpecifierSyntax,
-                     IdentifierSyntax, WildcardSyntax, StringSyntax,
-                     NumberSyntax)
-from .binding import (Binding, RootBinding, QueryBinding, SegmentBinding,
-                      TableBinding, FreeTableBinding, JoinedTableBinding,
-                      ColumnBinding, LiteralBinding, SieveBinding,
-                      CastBinding, TupleBinding)
-from .lookup import Lookup
-from .fn.function import FindFunction
-from ..introspect import Introspect
-from ..domain import (Domain, BooleanDomain, IntegerDomain, DecimalDomain,
-                      FloatDomain, StringDomain, DateDomain,
-                      TupleDomain, UntypedDomain, VoidDomain)
-from ..error import InvalidArgumentError
-from ..context import context
-import decimal
-
-
-class Binder(object):
-
-    def bind(self, syntax, parent=None):
-        if parent is None:
-            app = context.app
-            if app.cached_catalog is None:
-                introspect = Introspect()
-                catalog = introspect()
-                app.cached_catalog = catalog
-            catalog = app.cached_catalog
-            parent = RootBinding(catalog, syntax)
-        bind = Bind(syntax, self)
-        return bind.bind(parent)
-
-    def bind_one(self, syntax, parent=None):
-        if parent is None:
-            app = context.app
-            if app.cached_catalog is None:
-                introspect = Introspect()
-                catalog = introspect()
-                app.cached_catalog = catalog
-            catalog = app.cached_catalog
-            parent = RootBinding(catalog, syntax)
-        bind = Bind(syntax, self)
-        return bind.bind_one(parent)
-
-    def find_function(self, name):
-        find_function = FindFunction()
-        return find_function(name, self)
-
-    def cast(self, binding, domain, syntax=None, parent=None):
-        if syntax is None:
-            syntax = binding.syntax
-        if parent is None:
-            parent = binding.parent
-        cast = Cast(binding, binding.domain, domain, self)
-        return cast.cast(syntax, parent)
-
-    def coerce(self, left_domain, right_domain=None):
-        if right_domain is not None:
-            coerce = BinaryCoerce(left_domain, right_domain)
-            domain = coerce()
-            if domain is None:
-                coerce = BinaryCoerce(right_domain, left_domain)
-                domain = coerce()
-            return domain
-        else:
-            coerce = UnaryCoerce(left_domain)
-            return coerce()
-
-
-class UnaryCoerce(Adapter):
-
-    adapts(Domain)
-
-    def __init__(self, domain):
-        self.domain = domain
-
-    def __call__(self):
-        return self.domain
-
-
-class CoerceVoid(UnaryCoerce):
-
-    adapts(VoidDomain)
-
-    def __call__(self):
-        return None
-
-
-class CoerceTuple(UnaryCoerce):
-
-    adapts(TupleDomain)
-
-    def __call__(self):
-        return None
-
-
-class CoerceUntyped(UnaryCoerce):
-
-    adapts(UntypedDomain)
-
-    def __call__(self):
-        return StringDomain()
-
-
-class BinaryCoerce(Adapter):
-
-    adapts(Domain, Domain)
-
-    def __init__(self, left_domain, right_domain):
-        self.left_domain = left_domain
-        self.right_domain = right_domain
-
-    def __call__(self):
-        return None
-
-
-class BinaryCoerceUntyped(BinaryCoerce):
-
-    adapts(Domain, UntypedDomain)
-
-    def __call__(self):
-        return self.left_domain
-
-
-class BinaryCoerceBoolean(BinaryCoerce):
-
-    adapts(BooleanDomain, BooleanDomain)
-
-    def __call__(self):
-        return BooleanDomain()
-
-
-class BinaryCoerceInteger(BinaryCoerce):
-
-    adapts(IntegerDomain, IntegerDomain)
-
-    def __call__(self):
-        return IntegerDomain()
-
-
-class BinaryCoerceFloat(BinaryCoerce):
-
-    adapts(FloatDomain, FloatDomain)
-
-    def __call__(self):
-        return FloatDomain()
-
-
-class BinaryCoerceDecimal(BinaryCoerce):
-
-    adapts(DecimalDomain, DecimalDomain)
-
-    def __call__(self):
-        return DecimalDomain()
-
-
-class BinaryCoerceString(BinaryCoerce):
-
-    adapts(StringDomain, StringDomain)
-
-    def __call__(self):
-        return StringDomain()
-
-
-class BinaryCoerceDate(BinaryCoerce):
-
-    adapts(DateDomain, DateDomain)
-
-    def __call__(self):
-        return DateDomain()
-
-
-class CoerceIntegerToDecimal(BinaryCoerce):
-
-    adapts(IntegerDomain, DecimalDomain)
-
-    def __call__(self):
-        return DecimalDomain()
-
-
-class CoerceIntegerToFloat(BinaryCoerce):
-
-    adapts(IntegerDomain, FloatDomain)
-
-    def __call__(self):
-        return FloatDomain()
-
-
-class CoerceDecimalToFloat(BinaryCoerce):
-
-    adapts(DecimalDomain, FloatDomain)
-
-    def __call__(self):
-        return FloatDomain()
-
-
-class Cast(Adapter):
-
-    adapts(Binding, Domain, Domain, Binder)
-
-    def __init__(self, binding, from_domain, to_domain, binder):
-        self.binding = binding
-        self.from_domain = from_domain
-        self.to_domain = to_domain
-        self.binder = binder
-
-    def cast(self, syntax, parent):
-        return CastBinding(parent, self.binding, self.to_domain, syntax)
-
-
-class CastBooleanToBoolean(Cast):
-
-    adapts(Binding, BooleanDomain, BooleanDomain, Binder)
-
-    def cast(self, syntax, parent):
-        return self.binding
-
-
-class CastTupleToBoolean(Cast):
-
-    adapts(Binding, TupleDomain, BooleanDomain, Binder)
-
-    def cast(self, syntax, parent):
-        return TupleBinding(self.binding)
-
-
-class CastStringToString(Cast):
-
-    adapts(Binding, StringDomain, StringDomain, Binder)
-
-    def cast(self, syntax, parent):
-        return self.binding
-
-
-class CastIntegerToInteger(Cast):
-
-    adapts(Binding, IntegerDomain, IntegerDomain, Binder)
-
-    def cast(self, syntax, parent):
-        return self.binding
-
-
-class CastDecimalToDecimal(Cast):
-
-    adapts(Binding, DecimalDomain, DecimalDomain, Binder)
-
-    def cast(self, syntax, parent):
-        return self.binding
-
-
-class CastFloatToFloat(Cast):
-
-    adapts(Binding, FloatDomain, FloatDomain, Binder)
-
-    def cast(self, syntax, parent):
-        return self.binding
-
-
-class CastDateToDate(Cast):
-
-    adapts(Binding, DateDomain, DateDomain, Binder)
-
-    def cast(self, syntax, parent):
-        return self.binding
-
-
-class CastLiteral(Cast):
-
-    adapts(LiteralBinding, UntypedDomain, Domain, Binder)
-
-    def cast(self, syntax, parent):
-        try:
-            value = self.to_domain.parse(self.binding.value)
-        except ValueError, exc:
-            raise InvalidArgumentError("cannot cast a value: %s" % exc,
-                                       syntax.mark)
-        return LiteralBinding(parent, value, self.to_domain, syntax)
-
-
-class Bind(Adapter):
-
-    adapts(Syntax, Binder)
-
-    def __init__(self, syntax, binder):
-        self.syntax = syntax
-        self.binder = binder
-
-    def bind(self, parent):
-        raise InvalidArgumentError("unable to bind a node", self.syntax.mark)
-
-    def bind_one(self, parent):
-        bindings = list(self.bind(parent))
-        if len(bindings) == 1:
-            return bindings[0]
-        if len(bindings) < 1:
-            raise InvalidArgumentError("expected one node; got none",
-                                       self.syntax.mark)
-        if len(bindings) > 1:
-            raise InvalidArgumentError("expected one node; got more",
-                                       self.syntax.mark)
-
-
-class BindQuery(Bind):
-
-    adapts(QuerySyntax, Binder)
-
-    def bind(self, parent):
-        segment = None
-        if self.syntax.segment is not None:
-            segment = self.binder.bind_one(self.syntax.segment, parent)
-        yield QueryBinding(parent, segment, self.syntax)
-
-
-class BindSegment(Bind):
-
-    adapts(SegmentSyntax, Binder)
-
-    def bind(self, parent):
-        base = parent
-        if self.syntax.base is not None:
-            base = self.binder.bind_one(self.syntax.base, base)
-        if self.syntax.filter is not None:
-            filter = self.binder.bind_one(self.syntax.filter, base)
-            base_syntax = SieveSyntax(base.syntax, None, filter.syntax,
-                                      base.mark)
-            base_syntax = GroupSyntax(base_syntax, base.mark)
-            base = SieveBinding(base, filter, base_syntax)
-        if self.syntax.selector is not None:
-            bare_elements = list(self.binder.bind(self.syntax.selector, base))
-        else:
-            lookup = Lookup(base)
-            bare_elements = list(lookup.enumerate(base.syntax))
-        elements = []
-        for element in bare_elements:
-            domain = self.binder.coerce(element.domain)
-            if domain is None:
-                raise InvalidArgumentError("invalid type", element.mark)
-            if domain is not element.domain:
-                element = self.binder.cast(element, domain)
-            elements.append(element)
-        yield SegmentBinding(parent, base, elements, self.syntax)
-
-
-class BindSelector(Bind):
-
-    adapts(SelectorSyntax, Binder)
-
-    def bind(self, parent):
-        for element in self.syntax.elements:
-            for binding in self.binder.bind(element, parent):
-                yield binding
-
-
-class BindSieve(Bind):
-
-    adapts(SieveSyntax, Binder)
-
-    def bind(self, parent):
-        base = self.binder.bind_one(self.syntax.base, parent)
-        if self.syntax.filter is not None:
-            filter = self.binder.bind_one(self.syntax.filter, base)
-            base_syntax = SieveSyntax(base.syntax, None, filter.syntax,
-                                      base.mark)
-            if self.syntax.selector is not None:
-                base_syntax = GroupSyntax(base_syntax, base.mark)
-            base = SieveBinding(base, filter, base_syntax)
-        if self.syntax.selector is not None:
-            for binding in self.binder.bind(self.syntax.selector, base):
-                selector = SelectorSyntax([binding.syntax], binding.mark)
-                binding_syntax = SieveSyntax(self.syntax.base,
-                                             selector,
-                                             self.syntax.filter,
-                                             binding.mark)
-                binding = binding.clone(syntax=binding_syntax)
-                yield binding
-        else:
-            yield base
-
-
-class BindOperator(Bind):
-
-    adapts(OperatorSyntax, Binder)
-
-    def bind(self, parent):
-        name = self.syntax.symbol
-        if self.syntax.left is None:
-            name = name+'_'
-        if self.syntax.right is None:
-            name = '_'+name
-        function = self.binder.find_function(name)
-        return function.bind_operator(self.syntax, parent)
-
-
-class BindFunctionOperator(Bind):
-
-    adapts(FunctionOperatorSyntax, Binder)
-
-    def bind(self, parent):
-        name = self.syntax.identifier.value
-        function = self.binder.find_function(name)
-        return function.bind_function_operator(self.syntax, parent)
-
-
-class BindFunctionCall(Bind):
-
-    adapts(FunctionCallSyntax, Binder)
-
-    def bind(self, parent):
-        if self.syntax.base is not None:
-            parent = self.binder.bind_one(self.syntax.base, parent)
-        name = self.syntax.identifier.value
-        function = self.binder.find_function(name)
-        return function.bind_function_call(self.syntax, parent)
-
-
-class BindGroup(Bind):
-
-    adapts(GroupSyntax, Binder)
-
-    def bind(self, parent):
-        for binding in self.binder.bind(self.syntax.expression, parent):
-            binding_syntax = GroupSyntax(binding.syntax, binding.mark)
-            binding = binding.clone(syntax=binding_syntax)
-            yield binding
-
-
-class BindSpecifier(Bind):
-
-    adapts(SpecifierSyntax, Binder)
-
-    def bind(self, parent):
-        base = self.binder.bind_one(self.syntax.base, parent)
-        for binding in self.binder.bind(self.syntax.identifier, base):
-            binding_syntax = SpecifierSyntax(base.syntax, binding.syntax,
-                                             binding.mark)
-            binding = binding.clone(syntax=binding_syntax)
-            yield binding
-
-
-class BindIdentifier(Bind):
-
-    adapts(IdentifierSyntax, Binder)
-
-    def bind(self, parent):
-        lookup = Lookup(parent)
-        binding = lookup(self.syntax)
-        yield binding
-
-
-class BindWildcard(Bind):
-
-    adapts(WildcardSyntax, Binder)
-
-    def bind(self, parent):
-        lookup = Lookup(parent)
-        for binding in lookup.enumerate(self.syntax):
-            yield binding
-
-
-class BindString(Bind):
-
-    adapts(StringSyntax, Binder)
-
-    def bind(self, parent):
-        binding = LiteralBinding(parent, self.syntax.value,
-                                 UntypedDomain(),
-                                 self.syntax)
-        yield binding
-
-
-class BindNumber(Bind):
-
-    adapts(NumberSyntax, Binder)
-
-    def bind(self, parent):
-        value = self.syntax.value
-        if 'e' in value or 'E' in value:
-            domain = FloatDomain()
-            value = float(value)
-            if str(value) in ['inf', '-inf', 'nan']:
-                raise InvalidArgumentError("invalid float value",
-                                           self.syntax.mark)
-        elif '.' in value:
-            domain = DecimalDomain()
-            value = decimal.Decimal(value)
-        else:
-            domain = IntegerDomain()
-            value = int(value)
-            if not (-2**63 <= value < 2**63):
-                raise InvalidArgumentError("invalid integer value",
-                                           self.syntax.mark)
-        binding = LiteralBinding(parent, value, domain, self.syntax)
-        yield binding
-
-

src/htsql/tr/binding.py

 """
 
 
-from ..entity import CatalogEntity, TableEntity, ColumnEntity, Join
+from ..util import maybe, listof, Node
+from ..entity import TableEntity, ColumnEntity, Join
 from ..domain import Domain, VoidDomain, BooleanDomain, TupleDomain
 from .syntax import Syntax
-from ..util import maybe, listof, tupleof, Node
+from .coerce import coerce
 
 
 class Binding(Node):
+    """
+    Represents a binding node.
 
-    def __init__(self, parent, domain, syntax):
-        assert isinstance(parent, Binding)
+    This is an abstract class; see subclasses for concrete binding nodes.
+
+    A binding tree (technically, a DAG) is an intermediate stage of the HTSQL
+    translator.  A binding tree is translated from the syntax tree by the
+    *binding* process.  A binding tree is translated to a code tree by the
+    *encoding* process.
+
+    The following adapters are associated with the binding process and generate
+    new binding nodes::
+
+        Bind: (Syntax, BindState) -> Binding, ...
+        Lookup: (Binding, IdentifierSyntax) -> Binding
+
+    See :class:`htsql.tr.bind.Bind` and :class:`htsql.tr.lookup.Lookup` for
+    more details.
+
+    The following adapters are associated with the encoding process and
+    convert binding nodes to code and space nodes::
+
+        Encode: (Binding, EncodeState) -> Code
+        Relate: (Binding, EncodeState) -> Space
+
+    See :class:`htsql.tr.encode.Encode` and :class:`htsql.tr.encode.Relate`
+    for more details.
+
+    The constructor arguments:
+
+    `domain` (:class:`htsql.domain.Domain`)
+        The type of the binding node; use :class:`htsql.domain.VoidDomain`
+        instance when not applicable.
+
+    `syntax` (:class:`htsql.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.
+
+    Other attributes:
+
+    `mark` (:class:`htsql.mark.Mark`)
+        The location of the node in the original query (for error reporting).
+    """
+
+    def __init__(self, domain, syntax):
         assert isinstance(domain, Domain)
         assert isinstance(syntax, Syntax)
 
-        self.parent = parent
-        if parent is self:
-            self.root = self
-        else:
-            self.root = parent.root
         self.domain = domain
         self.syntax = syntax
         self.mark = syntax.mark
 
 
-class RootBinding(Binding):
+class ChainBinding(Binding):
+    """
+    Represents a link binding node.
 
-    def __init__(self, catalog, syntax):
-        assert isinstance(catalog, CatalogEntity)
+    Each link binding has an associated `base` parent node.  The base node
+    specifies the context of the node; the meaning of the context depends
+    on the concrete binding type.
+    
+    Chain bindings together with their bases form a subtree (or a forest)
+    in the binding graph.
+
+    Chain bindings are typically (but not always) generated by the lookup
+    adapter; that is, `Lookup` applied to a base node generates a link
+    binding with the given base.
+
+    Chaing bindings are often expected to correspond to some space nodes;
+    therefore they should have a non-trivial implementation of the `Relate`
+    adapter.
+
+    Constructor arguments:
+
+    `base` (:class:`Binding`)
+        The link context.
+    """
+
+    def __init__(self, base, domain, syntax):
+        assert isinstance(base, Binding)
+        super(ChainBinding, self).__init__(domain, syntax)
+        self.base = base
+
+
+class RootBinding(ChainBinding):
+    """
+    Represents a root link binding.
+
+    The root binding represents a scalar context in the binding tree.
+    `Lookup` over a root binding is a table lookup; `Relate` over
+    a root binding produces the scalar space.
+
+    For a root link binding, the `base` refers to the binding itself.
+    """
+
+    def __init__(self, syntax):
+        # Note: `self.base is self` for the root binding.
         super(RootBinding, self).__init__(self, VoidDomain(), syntax)
-        self.catalog = catalog
 
 
-class QueryBinding(Binding):
+class TableBinding(ChainBinding):
+    """
+    Represents a table link binding.
 
-    def __init__(self, parent, segment, syntax):
-        assert isinstance(segment, maybe(SegmentBinding))
-        super(QueryBinding, self).__init__(parent, VoidDomain(), syntax)
-        self.segment = segment
+    This is an abstract class; see :class:`FreeTableBinding` and
+    :class:`JoinedTableBinding` for concrete subclasses.
 
+    A table binding represents a table context; `Lookup` over a table
+    binding looks for columns and links; `Relate` over a table binding
+    produces a table space.
 
-class SegmentBinding(Binding):
+    Note that a table binding has a special domain
+    :class:`htsql.domain.TupleDomain`.
 
-    def __init__(self, parent, base, elements, syntax):
-        assert isinstance(base, Binding)
-        assert isinstance(elements, listof(Binding))
-        super(SegmentBinding, self).__init__(parent, VoidDomain(), syntax)
-        self.base = base
-        self.elements = elements
+    `table` (:class:`htsql.entity.TableEntity`)
+        The table which the binding is associated with.
+    """
 
-
-class TableBinding(Binding):
-
-    def __init__(self, parent, table, syntax):
+    def __init__(self, base, table, syntax):
         assert isinstance(table, TableEntity)
-        super(TableBinding, self).__init__(parent, TupleDomain(), syntax)
+        super(TableBinding, self).__init__(base, TupleDomain(), syntax)
         self.table = table
 
 
 class FreeTableBinding(TableBinding):
-    pass
+    """
+    Represents a free table binding.
+
+    A free table represents a table cross joined to its base.
+    """
 
 
 class JoinedTableBinding(TableBinding):
+    """
+    Represents a joined table binding.
 
-    def __init__(self, parent, table, joins, syntax):
+    A joined table is attached to its base using a sequence of joins.
+
+    `joins` (a list of :class:`htsql.entity.Join`)
+        A sequence of joins that attach the table to its base.
+    """
+
+    def __init__(self, base, table, joins, syntax):
         assert isinstance(joins, listof(Join)) and len(joins) > 0
-        super(JoinedTableBinding, self).__init__(parent, table, syntax)
+        super(JoinedTableBinding, self).__init__(base, table, syntax)
         self.joins = joins
 
 
-class ColumnBinding(Binding):
+class SieveBinding(ChainBinding):
+    """
+    Represents a sieve binding.
 
-    def __init__(self, parent, column, syntax):
-        assert isinstance(column, ColumnEntity)
-        super(ColumnBinding, self).__init__(parent, column.domain, syntax)
-        self.column = column
+    A sieve applies a filter to the base binding.
 
+    `filter` (:class:`Binding`)
+        A Boolean expression that filters the base.
+    """
 
-class LiteralBinding(Binding):
-
-    def __init__(self, parent, value, domain, syntax):
-        super(LiteralBinding, self).__init__(parent, domain, syntax)
-        self.value = value
-
-
-class SieveBinding(Binding):
-
-    def __init__(self, parent, filter, syntax):
+    def __init__(self, base, filter, syntax):
         assert isinstance(filter, Binding)
-        super(SieveBinding, self).__init__(parent, parent.domain, syntax)
+        assert isinstance(filter.domain, BooleanDomain)
+        super(SieveBinding, self).__init__(base, TupleDomain(), syntax)
         self.filter = filter
 
 
-class EqualityBinding(Binding):
+class SortBinding(ChainBinding):
+    """
+    Represents a sort table expression.
 
-    def __init__(self, parent, left, right, syntax):
-        assert isinstance(left, Binding)
-        assert isinstance(right, Binding)
-        domain = BooleanDomain()
-        super(EqualityBinding, self).__init__(parent, domain, syntax)
-        self.left = left
-        self.right = right
+    A sort binding specifies the order of the `base` rows.  It could also
+    extract a subset of the rows.
 
+    `order` (a list of :class:`Binding`)
+        The expressions by which the base rows are sorted.
 
-class InequalityBinding(Binding):
+    `limit` (an integer or ``None``)
+        If set, indicates that only the first `limit` rows are produced
+        (``None`` means no limit).
 
-    def __init__(self, parent, left, right, syntax):
-        assert isinstance(left, Binding)
-        assert isinstance(right, Binding)
-        domain = BooleanDomain()
-        super(InequalityBinding, self).__init__(parent, domain, syntax)
-        self.left = left
-        self.right = right
+    `offset` (an integer or ``None``)
+        If set, indicates that only the rows starting from `offset`-th
+        are produced (``None`` means ``0``).
+    """
 
-
-class TotalEqualityBinding(Binding):
-
-    def __init__(self, parent, left, right, syntax):
-        assert isinstance(left, Binding)
-        assert isinstance(right, Binding)
-        domain = BooleanDomain()
-        super(TotalEqualityBinding, self).__init__(parent, domain, syntax)
-        self.left = left
-        self.right = right
-
-
-class TotalInequalityBinding(Binding):
-
-    def __init__(self, parent, left, right, syntax):
-        assert isinstance(left, Binding)
-        assert isinstance(right, Binding)
-        domain = BooleanDomain()
-        super(TotalInequalityBinding, self).__init__(parent, domain, syntax)
-        self.left = left
-        self.right = right
-
-
-class ConjunctionBinding(Binding):
-
-    def __init__(self, parent, terms, syntax):
-        assert isinstance(terms, listof(Binding))
-        domain = BooleanDomain()
-        super(ConjunctionBinding, self).__init__(parent, domain, syntax)
-        self.terms = terms
-
-
-class DisjunctionBinding(Binding):
-
-    def __init__(self, parent, terms, syntax):
-        assert isinstance(terms, listof(Binding))
-        domain = BooleanDomain()
-        super(DisjunctionBinding, self).__init__(parent, domain, syntax)
-        self.terms = terms
-
-
-class NegationBinding(Binding):
-
-    def __init__(self, parent, term, syntax):
-        assert isinstance(term, Binding)
-        domain = BooleanDomain()
-        super(NegationBinding, self).__init__(parent, domain, syntax)
-        self.term = term
-
-
-class CastBinding(Binding):
-
-    def __init__(self, parent, binding, domain, syntax):
-        super(CastBinding, self).__init__(parent, domain, syntax)
-        self.binding = binding
-
-
-class OrderedBinding(Binding):
-
-    def __init__(self, parent, order, limit, offset, syntax):
-        assert isinstance(order, listof(tupleof(Binding, int)))
+    def __init__(self, base, order, limit, offset, syntax):
+        assert isinstance(order, listof(Binding))
         assert isinstance(limit, maybe(int))
         assert isinstance(offset, maybe(int))
-        super(OrderedBinding, self).__init__(parent, parent.domain, syntax)
+        super(SortBinding, self).__init__(base, base.domain, syntax)
         self.order = order
         self.limit = limit
         self.offset = offset
 
 
-class TupleBinding(Binding):
+class ColumnBinding(ChainBinding):
+    """
+    Represents a table column.
 
-    def __init__(self, binding):
-        super(TupleBinding, self).__init__(binding.parent, BooleanDomain(),
-                                           binding.syntax)
-        self.binding = binding
+    `column` (:class:`htsql.entity.ColumnEntity`)
+        The column entity.
+
+    `link` (:class:`JoinedTableBinding` or ``None``)
+        If set, indicates that the binding could also represent a link
+        to another table.  Any `Lookup` or `Relate` 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(JoinedTableBinding))
+        super(ColumnBinding, self).__init__(base, column.domain, syntax)
+        self.column = column
+        # FIXME: this is a hack to permit reparenting of a column binding.
+        # It is used when `Lookup` delegates the request to a base binding
+        # and then reparents the result.  Fixing this may require passing
+        # the expected base together with any `Lookup` request.
+        if link is not None and link.base is not base:
+            link = link.clone(base=base)
+        self.link = link
+
+
+class QueryBinding(Binding):
+    """
+    Represents the whole HTSQL query.
+
+    `root` (:class:`RootBinding`)
+        The root binding associated with the query.
+
+    `segment` (:class:`SegmentBinding` or ``None``)
+        The query segment.
+    """
+
+    def __init__(self, root, segment, syntax):
+        assert isinstance(root, RootBinding)
+        assert isinstance(segment, maybe(SegmentBinding))
+        super(QueryBinding, self).__init__(VoidDomain(), syntax)
+        self.root = root
+        self.segment = segment
+
+
+class SegmentBinding(Binding):
+    """
+    Represents a segment of an HTSQL query.
+
+    `base` (:class:`Binding`)
+        The base of the segment.
+
+    `elements` (a list of :class:`Binding`)
+        The segment elements.
+    """
+
+    def __init__(self, base, elements, syntax):
+        assert isinstance(base, Binding)
+        assert isinstance(elements, listof(Binding))
+        super(SegmentBinding, self).__init__(VoidDomain(), syntax)
+        self.base = base
+        self.elements = elements
+
+
+class LiteralBinding(Binding):
+    """
+    Represents a literal value.
+
+    `value` (valid type depends on the domain)
+        The value.
+
+    `domain` (:class:`htsql.domain.Domain`)
+        The value type.
+    """
+
+    def __init__(self, value, domain, syntax):
+        # FIXME: It appears `domain` is always `UntypedDomain()`.
+        # Hard-code the domain value then?
+        super(LiteralBinding, self).__init__(domain, syntax)
+        self.value = value
+
+
+class EqualityBindingBase(Binding):
+    """
+    Represents an equality operator.
+
+    This is an abstract class for the ``=``, ``==``, ``!=`` and ``!==``
+    operators.
+
+    Class attributes:
+
+    `is_negative` (Boolean)
+        If set, the class represents a "not equal" operator.
+
+    `is_total` (Boolean)
+        If set, the class represents "total equality" operator, which
+        consider ``NULL`` as a regular value.
+
+    Constructor arguments:
+
+    `lop` (:class:`Binding`)
+        The left operand.
+
+    `rop` (:class:`Binding`)
+        The right operand.
+    """
+
+    is_negative = None
+    is_total = None
+
+    def __init__(self, lop, rop, syntax):
+        assert isinstance(lop, Binding)
+        assert isinstance(rop, Binding)
+        # We want to use an engine-specific Boolean type, which, we assume,
+        # must always exist.
+        domain = coerce(BooleanDomain())
+        assert domain is not None
+        super(EqualityBindingBase, self).__init__(domain, syntax)
+        self.lop = lop
+        self.rop = rop
+
+
+class EqualityBinding(EqualityBindingBase):
+    """
+    Represents the "equality" (``=``) operator.
+    """
+
+    is_negative = False
+    is_total = False
+
+
+class InequalityBinding(EqualityBindingBase):
+    """
+    Represents the "inequality" (``!=``) operator.
+    """
+
+    is_negative = True
+    is_total = False
+
+
+class TotalEqualityBinding(EqualityBindingBase):
+    """
+    Represents the "total equality" (``==``) operator.
+    """
+
+    is_negative = False
+    is_total = True
+
+
+class TotalInequalityBinding(EqualityBindingBase):
+    """
+    Represents the "total inequality" (``!==``) operator.
+    """
+
+    is_negative = True
+    is_total = True
+
+
+class ConjunctionBinding(Binding):
+    """
+    Represents the logical "AND" (``&``) operator.
+
+    `ops` (a list of :class:`Binding`)
+        The operands.
+    """
+
+    def __init__(self, ops, syntax):
+        assert isinstance(ops, listof(Binding))
+        # Use the engine-specific Boolean type, which, we assume,
+        # must always exist.
+        domain = coerce(BooleanDomain())
+        assert domain is not None
+        super(ConjunctionBinding, self).__init__(domain, syntax)
+        self.ops = ops
+
+
+class DisjunctionBinding(Binding):
+    """
+    Represents the logical "OR" (``|``) operator.
+
+    `ops` (a list of :class:`Binding`)
+        The operands.
+    """
+
+    def __init__(self, ops, syntax):
+        assert isinstance(ops, listof(Binding))
+        # Use the engine-specific Boolean type, which, we assume,
+        # must always exist.
+        domain = coerce(BooleanDomain())
+        assert domain is not None
+        super(DisjunctionBinding, self).__init__(domain, syntax)
+        self.ops = ops
+
+
+class NegationBinding(Binding):
+    """
+    Represents the logical "NOT" (``!``) operator.
+
+    `op` (:class:`Binding`)
+        The operand.
+    """
+
+    def __init__(self, op, syntax):
+        assert isinstance(op, Binding)
+        # Use the engine-specific Boolean type, which, we assume,
+        # must always exist.
+        domain = coerce(BooleanDomain())
+        assert domain is not None
+        super(NegationBinding, self).__init__(domain, syntax)
+        self.op = op
+
+
+class CastBinding(Binding):
+    """
+    Represents a type conversion operator.
+
+    `op` (:class:`Binding`)
+        The operand to convert.
+
+    `domain` (:class:`Domain`)
+        The target domain.
+    """
+
+    def __init__(self, op, domain, syntax):
+        super(CastBinding, self).__init__(domain, syntax)
+        self.op = op
 
 
 class FunctionBinding(Binding):
+    """
+    Represents a function or an operator binding.
 
-    def __init__(self, parent, domain, syntax, **arguments):
-        super(FunctionBinding, self).__init__(parent, domain, syntax)
+    This is an abstract class; see subclasses for concrete functions and
+    operators.
+
+    `domain` (:class:`Domain`)
+        The type of the result.
+
+    `arguments` (a dictionary)
+        A mapping from argument names to values.
+    """
+
+    def __init__(self, domain, syntax, **arguments):
+        super(FunctionBinding, self).__init__(domain, syntax)
         self.arguments = arguments
         for key in arguments:
             setattr(self, key, arguments[key])
 
 
+class WrapperBinding(Binding):
+    """
+    Represents a decorating binding.
+
+    This class has several subclasses, but could also be used directly
+    when the only purpose of decorating is attaching a different syntax node.
+
+    A decorating binding adds extra attributes to the base binding,
+    but does not affect the encoding or lookup operations.
+
+    `base` (:class:`Binding`)
+        The decorated binding.
+    """
+
+    def __init__(self, base, syntax):
+        super(WrapperBinding, self).__init__(base.domain, syntax)
+        self.base = base
+
+
+class OrderBinding(WrapperBinding):
+    """
+    Represents an order decorator (postfix ``+`` and ``-`` operators).
+
+    `base` (:class:`Binding`)
+        The decorated binding.
+
+    `dir` (``+1`` or ``-1``).
+        Indicates the direction; ``+1`` for ascending, ``-1`` for descending.
+    """
+
+    def __init__(self, base, dir, syntax):
+        assert dir in [-1, +1]
+        super(OrderBinding, self).__init__(base, syntax)
+        self.dir = dir
+
+
+class TitleBinding(WrapperBinding):
+    """
+    Represents a title decorator (the ``as`` operator).
+
+    The title decorator is used to specify the column title explicitly
+    (by default, a serialized syntax node is used as the title).
+
+    `base` (:class:`Binding`)
+        The decorated binding.
+
+    `title` (a string)
+        The title.
+    """
+
+    def __init__(self, base, title, syntax):
+        assert isinstance(title, str)
+        super(TitleBinding, self).__init__(base, syntax)
+        self.title = title
+
+
+class FormatBinding(WrapperBinding):
+    """
+    Represents a format decorator (the ``format`` operator).
+
+    The format decorator is used to provide hints to the renderer
+    as to how display column values.  How the format is interpreted
+    by the renderer depends on the renderer and the type of the column.
+
+    `base` (:class:`Binding`)
+        The decorated binding.
+
+    `format` (a string)
+        The formatting hint.
+    """
+
+    def __init__(self, base, format, syntax):
+        assert isinstance(format, str)
+        super(FormatBinding, self).__init__(base, syntax)
+        self.format = format
+
+

src/htsql/tr/coerce.py

+#
+# Copyright (c) 2006-2010, Prometheus Research, LLC
+# Authors: Clark C. Evans <cce@clarkevans.com>,
+#          Kirill Simonov <xi@resolvent.net>
+#
+
+
+"""
+:mod:`htsql.tr.coerce`
+======================
+
+This module implements the unary and binary coerce adapters.
+"""
+
+
+from ..util import listof
+from ..adapter import Adapter, adapts, adapts_many
+from ..domain import (Domain, VoidDomain, TupleDomain, UntypedDomain,
+                      BooleanDomain, IntegerDomain, DecimalDomain, FloatDomain,
+                      StringDomain, EnumDomain, DateDomain, OpaqueDomain)
+
+
+class UnaryCoerce(Adapter):
+    """
+    Validates and specializes a domain.
+
+    The :class:`UnaryCoerce` adapter has the following signature::
+
+        UnaryCoerce: Domain -> maybe(Domain)
+
+    The adapter checks if the given domain is valid.  If so, the domain
+    or its specialized version is returned; otherwise, ``None`` is returned.
+
+    The primary use cases are:
+
+    - disabling special domains in regular expressions;
+
+    - specializing untyped values;
+
+    - providing engine-specific versions of generic domains.
+
+    The adapter is rarely used directly, use :func:`coerce` instead.
+    """
+
+    adapts(Domain)
+
+    def __init__(self, domain):
+        self.domain = domain
+
+    def __call__(self):
+        # By default, we assume that the domain is valid and specializes
+        # into itself.
+        return self.domain
+
+
+class BinaryCoerce(Adapter):
+    """
+    Determines a common domain of two domains.
+
+    The :class:`BinaryCoerce` adapter has the following signature::
+
+        BinaryCoerce: (Domain, Domain) -> maybe(Domain)
+
+    :class:`BinaryCoerce` is polymorphic on both arguments.  
+
+    The adapter checks if two domains could be reduced to a single common
+    domains.  If the common domain cannot be determined, the adapter returns
+    ``None``.
+    
+    The primary use cases are:
+
+    - checking if two domains are compatible (that is, if values of these
+      domains are comparable without explicit cast).
+
+    - deducing the actual type of untyped values.
+
+    The adapter is rarely used directly, use :func:`coerce` instead.
+    """
+
+    adapts(Domain, Domain)
+
+    def __init__(self, ldomain, rdomain):
+        self.ldomain = ldomain
+        self.rdomain = rdomain
+
+    def __call__(self):
+        # By default, we assume that the domain is compatible with itself.
+        if self.ldomain == self.rdomain:
+            return self.ldomain
+        return None
+
+
+class UnaryCoerceSpecial(UnaryCoerce):
+    """
+    Disables special domains.
+    """
+
+    adapts_many(VoidDomain,
+                TupleDomain)
+
+    def __call__(self):
+        # `VoidDomain` and `TupleDomain` values cannot be compared.
+        return None
+
+
+class UnaryCoerceUntyped(UnaryCoerce):
+    """
+    Specializes untyped values.
+    """
+
+    adapts(UntypedDomain)
+
+    def __call__(self):
+        # Specializes untyped top-level expressions to the string type.
+        return StringDomain()
+
+
+class BinaryCoerceBoolean(BinaryCoerce):
+    """
+    Coerces untyped values to :class:`BooleanDomain`.
+    """
+
+    adapts_many((BooleanDomain, BooleanDomain),
+                (BooleanDomain, UntypedDomain),
+                (UntypedDomain, BooleanDomain))
+
+    def __call__(self):
+        return BooleanDomain()
+
+
+class BinaryCoerceInteger(BinaryCoerce):
+    """
+    Coerces untyped values to :class:`IntegerDomain`.
+    """
+
+    adapts_many((IntegerDomain, IntegerDomain),
+                (IntegerDomain, UntypedDomain),
+                (UntypedDomain, IntegerDomain))
+
+    def __call__(self):
+        # Note that we use the generic version of the domain.  Engine addons
+        # may override this implementation to provide an engine-specifi