Commits

Kirill Simonov committed 66b7838

Added the first draft of the SQL translator.

Added entity and domain objects.
Implemented introspectors for PostgreSQL and SQLite.
Implemented the SQL translation process.
Added a trivial renderer.

  • Participants
  • Parent commits 94b177e

Comments (0)

Files changed (40)

doc/api/htsql.rst

    :members:
 .. automodule:: htsql.split_sql
    :members:
+.. automodule:: htsql.introspect
+   :members:
 

doc/api/htsql_pgsql.rst

    :members:
 .. automodule:: htsql_pgsql.split_sql
    :members:
+.. automodule:: htsql_pgsql.introspect
+   :members:
 

doc/api/htsql_sqlite.rst

    :members:
 .. automodule:: htsql_sqlite.split_sql
    :members:
+.. automodule:: htsql_sqlite.introspect
+   :members:
 

src/htsql/adapter.py

         """
         # Bypass realizations.
         if cls.is_realized:
-            return super(Adapter, cls).__new__(cls, *args, **kwds)
+            return super(Adapter, cls).__new__(cls)
         # Extract polymorphic parameters.
         assert cls.signature is not None and len(args) >= len(cls.signature)
         objects = args[:len(cls.signature)]
         # Specialize the interface for the given parameters.
         realization = cls.realize(*objects)
         # Create an instance of the realization.
-        return super(Adapter, realization).__new__(realization, *args, **kwds)
+        return super(Adapter, realization).__new__(realization)
 
     @classmethod
     def realize(cls, *objects):

src/htsql/connect.py

 """
 
 
-from .adapter import Utility, weights, find_adapters
+from .adapter import Adapter, Utility, adapts, find_adapters
+from .domain import Domain
 
 
 class DBError(Exception):
             exception = exc_type(exc_value)
 
         # Ask the connection adapter to convert the exception.
-        error = self.connect.translate_error(exception)
+        error = self.connect.normalize_error(exception)
 
         # If we got a new exception, raise it.
         if error is not None:
         # Override when subclassing.
         raise NotImplementedError()
 
-    def translate_error(self, exception):
+    def normalize_error(self, exception):
         """
-        Translates a DBAPI exception.
+        Normalizes a DBAPI exception.
 
         When `exception` is a DBAPI exception, returns an instance of
         :exc:`DBError`; otherwise, returns ``None``.
         return None
 
 
+class Normalize(Adapter):
+
+    adapts(Domain)
+
+    def __init__(self, domain):
+        self.domain = domain
+
+    def __call__(self, value):
+        return value
+
+
 connect_adapters = find_adapters()
 
 

src/htsql/domain.py

+#
+# Copyright (c) 2006-2010, Prometheus Research, LLC
+# Authors: Clark C. Evans <cce@clarkevans.com>,
+#          Kirill Simonov <xi@resolvent.net>
+#
+
+
+"""
+:mod:`htsql.domain`
+===================
+
+This module defines abstract HTSQL domains.
+"""
+
+
+from .util import maybe, listof
+import re
+
+
+class Domain(object):
+
+    name = None
+
+    def parse(self, data):
+        assert isinstance(data, maybe(str))
+        if data is None:
+            return None
+        raise ValueError("invalid literal")
+
+    def dump(self, value):
+        assert value is None
+        return None
+
+    def __str__(self):
+        return self.name
+
+    def __repr__(self):
+        return "<%s %s>" % (self.__class__.__name__, self)
+
+
+class BooleanDomain(Domain):
+
+    name = 'boolean'
+
+    def parse(self, data):
+        assert isinstance(data, maybe(str))
+        if data is None:
+            return None
+        if data.lower() == 'true':
+            return True
+        if data.lower() == 'false':
+            return False
+        raise ValueError("invalid Boolean literal: expected 'true' or 'false';"
+                         " got %r" % data)
+
+    def dump(self, value):
+        assert isinstance(value, maybe(bool))
+        if value is None:
+            return None
+        if value is True:
+            return 'true'
+        if value is False:
+            return 'false'
+
+
+class NumberDomain(Domain):
+
+    is_exact = True
+    radix = 2
+
+
+class IntegerDomain(NumberDomain):
+
+    name = 'integer'
+
+    def __init__(self, size=None):
+        self.size = size
+
+    def parse(self, data):
+        assert isinstance(data, maybe(str))
+        if data is None:
+            return None
+        try:
+            value = int(data)
+        except ValueError, exc:
+            raise ValueError("invalid integer literal: %s" % exc)
+        return value
+
+    def dump(self, value):
+        assert isinstance(value, maybe(int))
+        if value is None:
+            return None
+        return str(value)
+
+
+class FloatDomain(NumberDomain):
+
+    name = 'float'
+    is_exact = False
+
+    def __init__(self, size=None):
+        self.size = size
+
+    def parse(self, data):
+        assert isinstance(data, maybe(str))
+        if data is None:
+            return None
+        try:
+            value = float(data)
+        except ValueError, exc:
+            raise ValueError("invalid float literal: %s" % exc)
+        return value
+
+    def dump(self, value):
+        assert isinstance(value, maybe(float))
+        if value is None:
+            return None
+        return str(value)
+
+
+class DecimalDomain(NumberDomain):
+
+    name = 'decimal'
+    radix = 10
+
+    def __init__(self, precision=None, scale=None):
+        assert isinstance(precision, maybe(int))
+        assert isinstance(scale, maybe(int))
+        self.precision = precision
+        self.scale = scale
+
+    def parse(self, data):
+        assert isinstance(data, maybe(str))
+        if data is None:
+            return None
+        try:
+            value = decimal.Decimal(data)
+        except decimal.InvalidOperation, exc:
+            raise ValueError("invalid decimal literal: %s" % exc)
+        return value
+
+    def dump(self, value):
+        assert isinstance(value, maybe(decimal.Decimal))
+        if value is None:
+            return None
+        return str(value)
+
+
+class StringDomain(Domain):
+
+    name = 'string'
+
+    def __init__(self, length=None, is_varying=True):
+        assert isinstance(length, maybe(int))
+        assert isinstance(is_varying, bool)
+        self.length = length
+        self.is_varying = is_varying
+
+    def parse(self, data):
+        assert isinstance(data, maybe(str))
+        if data is None:
+            return None
+        return data
+
+    def dump(self, value):
+        assert isinstance(value, maybe(str))
+        if value is None:
+            return None
+        return value
+
+
+class EnumDomain(Domain):
+
+    name = 'enum'
+
+    def __init__(self, labels=None):
+        assert isinstance(labels, maybe(listof(str)))
+        self.labels = labels
+
+
+class DateDomain(Domain):
+
+    name = 'date'
+
+    pattern = r'^(?P<year>\d{4})-(?P<month>\d{2})-(?P<day>\d{2})$'
+    regexp = re.compile(pattern)
+
+    def parse(self, data):
+        assert isinstance(data, maybe(str))
+        if data is None:
+            return None
+        match = self.regexp.match(data)
+        if match is None:
+            raise ValueError("invalid date literal: expected 'YYYY-MM-DD';"
+                             " got %r" % data)
+        year = int(match.group('year'))
+        month = int(match.group('month'))
+        day = int(match.group('day'))
+        try:
+            value = datetime.date(year, month, day)
+        except ValueError, exc:
+            raise ValueError("invalid date literal: %s" % exc)
+        return value
+
+    def dump(self, value):
+        assert isinstance(value, maybe(datetime.date))
+        if value is None:
+            return None
+        return str(value)
+
+
+class VoidDomain(Domain):
+
+    name = 'void'
+
+
+class OpaqueDomain(Domain):
+
+    name = 'opaque'
+
+
+class UntypedDomain(Domain):
+
+    name = 'untyped'
+
+
+class UntypedNumberDomain(UntypedDomain):
+    pass
+
+
+class UntypedStringDomain(UntypedDomain):
+    pass
+
+

src/htsql/entity.py

+#
+# Copyright (c) 2006-2010, Prometheus Research, LLC
+# Authors: Clark C. Evans <cce@clarkevans.com>,
+#          Kirill Simonov <xi@resolvent.net>
+#
+
+
+"""
+:mod:`htsql.entity`
+===================
+
+This module implements the HTSQL catalog and catalog entities.
+"""
+
+
+from .util import listof
+from .domain import Domain
+
+
+class Entity(object):
+
+    def __str__(self):
+        return self.__class__.__name__.lower()
+
+    def __repr__(self):
+        return "<%s %s>" % (self.__class__.__name__, self)
+
+
+class NamedEntity(Entity):
+
+    def __init__(self, name):
+        self.name = name
+
+    def __str__(self):
+        return self.name
+
+    def __repr__(self):
+        return "<%s %s>" % (self.__class__.__name__, self)
+
+
+class EntitySet(object):
+
+    def __init__(self, entities):
+        assert isinstance(entities, listof(NamedEntity))
+        self.entities = entities
+        self.entity_by_name = dict((entity.name, entity)
+                                   for entity in entities)
+
+    def __contains__(self, name):
+        return (name in self.entity_by_name)
+
+    def __getitem__(self, name):
+        return self.entity_by_name[name]
+
+    def __iter__(self):
+        return iter(self.entities)
+
+    def __len__(self):
+        return len(self.entities)
+
+    def get(self, name, default=None):
+        return self.entity_by_name.get(name, default)
+
+    def keys(self):
+        return [entity.name for entity in self.entities]
+
+    def values(self):
+        return self.entities[:]
+
+    def items(self):
+        return [(entity.name, entity) for entity in self.entities]
+
+
+class CatalogEntity(Entity):
+
+    def __init__(self, schemas):
+        assert isinstance(schemas, listof(SchemaEntity))
+        self.schemas = EntitySet(schemas)
+
+
+class SchemaEntity(NamedEntity):
+
+    def __init__(self, name, tables):
+        assert isinstance(tables, listof(TableEntity))
+        assert all(table.schema_name == name for table in tables)
+        super(SchemaEntity, self).__init__(name)
+        self.tables = EntitySet(tables)
+
+
+class TableEntity(NamedEntity):
+
+    is_view = False
+
+    def __init__(self, schema_name, name, columns, unique_keys, foreign_keys):
+        assert isinstance(columns, listof(ColumnEntity))
+        assert all((column.schema_name, column.table_name)
+                        == (schema_name, name) for column in columns)
+        assert isinstance(unique_keys, listof(UniqueKeyEntity))
+        assert all((uk.origin_schema_name, uk.origin_name)
+                        == (schema_name, name) for uk in unique_keys)
+        assert isinstance(foreign_keys, listof(ForeignKeyEntity))
+        assert all((fk.origin_schema_name, fk.origin_name)
+                        == (schema_name, name) for fk in foreign_keys)
+        super(TableEntity, self).__init__(name)
+        self.schema_name = schema_name
+        self.columns = EntitySet(columns)
+        self.unique_keys = unique_keys
+        self.primary_key = None
+        primary_keys = [uk for uk in unique_keys if uk.is_primary]
+        assert len(primary_keys) <= 1
+        if primary_keys:
+            self.primary_key = primary_keys[0]
+        self.foreign_keys = foreign_keys
+
+    def __str__(self):
+        return "%s.%s" % (self.schema_name, self.name)
+
+
+class ViewEntity(TableEntity):
+
+    is_view = True
+
+
+class ColumnEntity(NamedEntity):
+
+    def __init__(self, schema_name, table_name, name,
+                 domain, is_nullable=False, has_default=False):
+        assert isinstance(domain, Domain)
+        assert isinstance(is_nullable, bool)
+        assert isinstance(has_default, bool)
+        super(ColumnEntity, self).__init__(name)
+        self.schema_name = schema_name
+        self.table_name = table_name
+        self.domain = domain
+        self.is_nullable = is_nullable
+        self.has_default = has_default
+
+    def __str__(self):
+        return "%s.%s.%s" % (self.schema_name, self.table_name, self.name)
+
+
+class UniqueKeyEntity(Entity):
+
+    is_primary = False
+
+    def __init__(self, origin_schema_name, origin_name, origin_column_names):
+        assert isinstance(origin_schema_name, str)
+        assert isinstance(origin_name, str)
+        assert isinstance(origin_column_names, listof(str))
+
+        self.origin_schema_name = origin_schema_name
+        self.origin_name = origin_name
+        self.origin_column_names = origin_column_names
+
+    def __str__(self):
+        return "%s.%s(%s)" % (self.origin_schema_name, self.origin_name,
+                              ",".join(self.origin_column_names))
+
+
+class PrimaryKeyEntity(UniqueKeyEntity):
+
+    is_primary = True
+
+
+class ForeignKeyEntity(Entity):
+
+    def __init__(self, origin_schema_name, origin_name, origin_column_names,
+                 target_schema_name, target_name, target_column_names):
+        assert isinstance(origin_schema_name, str)
+        assert isinstance(origin_name, str)
+        assert isinstance(origin_column_names, listof(str))
+        assert isinstance(target_schema_name, str)
+        assert isinstance(target_name, str)
+        assert isinstance(target_column_names, listof(str))
+
+        self.origin_schema_name = origin_schema_name
+        self.origin_name = origin_name
+        self.origin_column_names = origin_column_names
+        self.target_schema_name = target_schema_name
+        self.target_name = target_name
+        self.target_column_names = target_column_names
+
+    def __str__(self):
+        return "%s.%s(%s) -> %s.%s(%s)" \
+                % (self.origin_schema_name, self.origin_name,
+                   ",".join(self.origin_column_names),
+                   self.target_schema_name, self.target_name,
+                   ",".join(self.target_column_names))
+
+
+class Join(object):
+
+    is_direct = False
+    is_reverse = False
+
+    def __init__(self, origin, target):
+        assert isinstance(origin, TableEntity)
+        assert isinstance(target, TableEntity)
+        self.origin = origin
+        self.target = target
+
+
+class DirectJoin(Join):
+
+    is_direct = True
+
+    def __init__(self, origin, target, foreign_key):
+        assert isinstance(foreign_key, ForeignKeyEntity)
+        super(DirectJoin, self).__init__(origin, target)
+        self.foreign_key = foreign_key
+        self.origin_columns = [origin.columns[name]
+                               for name in foreign_key.origin_column_names]
+        self.target_columns = [target.columns[name]
+                               for name in foreign_key.target_column_names]
+        self.is_expanding = all(not column.is_nullable
+                                for column in self.origin_columns)
+        self.is_contracting = True
+
+
+class ReverseJoin(Join):
+
+    is_reverse = True
+
+    def __init__(self, origin, target, foreign_key):
+        assert isinstance(foreign_key, ForeignKeyEntity)
+        super(ReverseJoin, self).__init__(origin, target)
+        self.foreign_key = foreign_key
+        self.origin_columns = [target.columns[name]
+                               for name in foreign_key.target_column_names]
+        self.target_columns = [origin.columns[name]
+                               for name in foreign_key.origin_column_names]
+        self.is_expanding = False
+        self.is_contracting = False
+        for uk in target.unique_keys:
+            if all(column.name in uk.origin_column_names
+                   for column in target.columns):
+                self.is_contracting = True
+
+
+#
+# TODO: bound entities...
+#
+
+
+class cached_property(object):
+
+    def __init__(self, getter):
+        self.getter = getter
+
+    def __get__(self, obj, objtype=None):
+        if obj is None:
+            return self
+        value = self.getter(obj)
+        obj.__dict__[self.getter.__name__] = value
+        return value
+
+
+class BoundCatalog(object):
+
+    def __init__(self, catalog):
+        self.catalog = catalog
+
+    @cached_property
+    def schemas(self):
+        return BoundEntitySet(self, self.catalog.schemas)
+
+
+class BoundSchema(object):
+
+    def __init__(self, catalog, schema):
+        self.catalog = catalog
+        self.schema = schema
+
+
+class BoundTable(object):
+
+    def __init__(self, schema, table):
+        self.schema = schema
+        self.table = table
+        self.columns = BoundEntitySet(self, self.table.columns)
+
+

src/htsql/error.py

     kind = "invalid syntax"
 
 
+class InvalidArgumentError(BadRequestError):
+
+    kind = "invalid argument"
+
+
+class EngineError(ConflictError):
+
+    kind = "engine failure"
+
+

src/htsql/export.py

 from wsgi import wsgi_adapters
 from connect import connect_adapters
 from split_sql import split_sql_adapters
+from introspect import introspect_adapters
+from translate import translate_adapters
+from produce import produce_adapters
+from render import render_adapters
+from tr.binder import bind_adapters
+from tr.lookup import lookup_adapters
+from tr.encoder import encode_adapters
+from tr.assembler import assemble_adapters
+from tr.outliner import outline_adapters
+from tr.compiler import compile_adapters
+from tr.serializer import serialize_adapters
 
 
 class HTSQL_CORE(Addon):
     # List of adapters exported by the addon.
     adapters = (wsgi_adapters +
                 connect_adapters +
-                split_sql_adapters)
+                split_sql_adapters +
+                introspect_adapters +
+                bind_adapters +
+                lookup_adapters +
+                encode_adapters +
+                assemble_adapters +
+                outline_adapters +
+                compile_adapters +
+                serialize_adapters +
+                translate_adapters +
+                produce_adapters +
+                render_adapters)
 
 

src/htsql/introspect.py

+#
+# Copyright (c) 2006-2010, Prometheus Research, LLC
+# Authors: Clark C. Evans <cce@clarkevans.com>,
+#          Kirill Simonov <xi@resolvent.net>
+#
+
+
+"""
+:mod:`htsql.introspect`
+=======================
+
+This module declares the database introspector adapter.
+
+This module exports a global variable:
+
+`introspect_adapters`
+    List of adapters declared in this module.
+"""
+
+
+from .adapter import Utility, find_adapters
+
+
+class Introspect(Utility):
+    """
+    Declares the introspection interface.
+
+    An introspector analyzes the database meta-data and generates
+    an HTSQL catalog.
+
+    Usage::
+
+        introspect = Introspect()
+        catalog = introspect()
+
+    Note that most implementations loads the meta-data information
+    when the adapter is constructed so subsequent calls of
+    :meth:`__call__` will always produce essentially the same catalog.
+    To re-load the meta-data from the database, create a new instance
+    of the :class:`Introspect` adapter.
+    """
+
+    def __call__(self):
+        """
+        Returns an HTSQL catalog.
+        """
+        # Override in implementations.
+        raise NotImplementedError()
+
+
+introspect_adapters = find_adapters()
+
+

src/htsql/produce.py

+#
+# Copyright (c) 2006-2010, Prometheus Research, LLC
+# Authors: Clark C. Evans <cce@clarkevans.com>,
+#          Kirill Simonov <xi@resolvent.net>
+#
+
+
+"""
+:mod:`htsql.produce`
+====================
+
+This module implements the produce utility.
+"""
+
+
+from .adapter import Utility, find_adapters
+from .connect import DBError, Connect, Normalize
+
+
+class Profile(object):
+
+    def __init__(self, plan):
+        self.plan = plan
+        self.frame = plan.frame
+        self.sketch = plan.sketch
+        self.term = plan.term
+        self.code = plan.code
+        self.binding = plan.binding
+        self.syntax = plan.syntax
+
+
+class Product(object):
+
+    def __init__(self, profile, records=None):
+        self.profile = profile
+        self.records = records
+
+    def __iter__(self):
+        if self.records is not None:
+            return iter(self.records)
+        else:
+            return iter([])
+
+    def __nonzero__(self):
+        return (self.records is not None)
+
+
+class Produce(Utility):
+
+    def __call__(self, plan):
+        profile = Profile(plan)
+        records = None
+        if plan.sql:
+            try:
+                connect = Connect()
+                connection = connect()
+                cursor = connection.cursor()
+                cursor.execute(plan.sql)
+                rows = cursor.fetchall()
+                connection.close()
+            except DBError, exc:
+                raise EngineError(str(exc))
+            records = []
+            select = plan.frame.segment.select
+            normalizers = []
+            for phrase in plan.frame.segment.select:
+                normalize = Normalize(phrase.domain)
+                normalizers.append(normalize)
+            for row in rows:
+                values = []
+                for item, normalize in zip(row, normalizers):
+                    value = normalize(item)
+                    values.append(value)
+                records.append((values))
+        return Product(profile, records)
+
+
+produce_adapters = find_adapters()
+
+

src/htsql/render.py

+#
+# Copyright (c) 2006-2010, Prometheus Research, LLC
+# Authors: Clark C. Evans <cce@clarkevans.com>,
+#          Kirill Simonov <xi@resolvent.net>
+#
+
+
+"""
+:mod:`htsql.render`
+===================
+
+This module implements the render utility.
+"""
+
+
+from .adapter import Utility, find_adapters
+
+
+class Output(object):
+
+    def __init__(self, status, headers, body):
+        self.status = status
+        self.headers = headers
+        self.body = body
+
+
+class Render(Utility):
+
+    def __call__(self, product, environ):
+        status = "200 OK"
+        headers = [('Content-Type', 'text/plain; charset=UTF-8')]
+        body = self.render_product(product)
+        return Output(status, headers, body)
+
+    def render_product(self, product):
+        if not product:
+            yield "(no data)\n"
+        else:
+            for row in product:
+                yield ", ".join(str(value) for value in row)+"\n"
+
+
+render_adapters = find_adapters()
+
+

src/htsql/tr/assembler.py

+#
+# Copyright (c) 2006-2010, Prometheus Research, LLC
+# Authors: Clark C. Evans <cce@clarkevans.com>,
+#          Kirill Simonov <xi@resolvent.net>
+#
+
+
+"""
+:mod:`htsql.tr.assembler`
+=========================
+
+This module implements the assemble adapter.
+"""
+
+
+from ..adapter import Adapter, adapts, find_adapters
+from .code import (Code, Space, ScalarSpace, FreeTableSpace, JoinedTableSpace,
+                   ScreenSpace, OrderedSpace, Expression, Unit,
+                   ColumnUnit, AggregateUnit, SegmentCode, QueryCode)
+from .term import (TableTerm, ScalarTerm, FilterTerm, JoinTerm,
+                   CorrelationTerm, ProjectionTerm, OrderingTerm, WrapperTerm,
+                   SegmentTerm, QueryTerm, ParallelTie, SeriesTie,
+                   LEFT, RIGHT, FORWARD)
+
+
+class Assembler(object):
+
+    def assemble(self, code, *args):
+        assemble = Assemble(code, self)
+        return assemble.assemble(*args)
+
+    def inject(self, code, term):
+        assemble = Assemble(code, self)
+        return assemble.inject(term)
+
+
+class Assemble(Adapter):
+
+    adapts(Code, Assembler)
+
+    def __init__(self, code, assembler):
+        self.code = code
+        self.assembler = assembler
+
+    def assemble(self):
+        raise NotImplementedError()
+
+    def inject(self, term):
+        raise NotImplementedError()
+
+
+class AssembleSpace(Assemble):
+
+    adapts(Space, Assembler)
+
+    def __init__(self, space, assembler):
+        self.space = space
+        self.assembler = assembler
+
+    def assemble(self, baseline):
+        raise NotImplementedError()
+
+
+class AssembleExpression(Assemble):
+
+    adapts(Expression, Assembler)
+
+    def inject(self, term):
+        for unit in self.code.get_units():
+            term = self.assembler.inject(unit, term)
+        return term
+
+
+class AssembleUnit(AssembleExpression):
+
+    adapts(Unit, Assembler)
+
+    def inject(self, term):
+        raise NotImplementedError()
+
+
+class AssembleScalar(AssembleSpace):
+
+    adapts(ScalarSpace, Assembler)
+
+    def assemble(self, baseline):
+        assert baseline == self.space
+        routes = {}
+        routes[self.space] = []
+        return ScalarTerm(self.space, baseline, routes, self.space.mark)
+
+    def inject(self, term):
+        if self.space in term.routes:
+            return term
+        axis = term.baseline
+        while axis.parent != self.space:
+            axis = axis.parent
+        term = self.assembler.inject(axis, term)
+        assert self.space not in term.routes
+        left = term
+        right_routes = {}
+        right_routes[self.space] = []
+        right = ScalarTerm(self.space, self.space,
+                           right_routes, self.space.mark)
+        tie = SeriesTie(axis, is_reverse=True)
+        routes = {}
+        for key in left.routes:
+            routes[key] = [LEFT] + left.routes[key]
+        routes[self.space] = [RIGHT]
+        return JoinTerm(left, right, [tie], True, left.space, left.baseline,
+                        routes, left.mark)
+
+
+class AssembleFreeTable(AssembleSpace):
+
+    adapts(FreeTableSpace, Assembler)
+
+    def assemble(self, baseline):
+        backbone = self.space.axes()
+        if baseline == backbone:
+            routes = {}
+            routes[self.space] = []
+            routes[backbone] = []
+            return TableTerm(self.space.table, self.space, baseline,
+                             routes, self.space.mark)
+        left = self.assembler.assemble(self.space.parent, baseline)
+        right_routes = {}
+        right_routes[self.space] = []
+        right_routes[backbone] = []
+        right = TableTerm(self.space.table, self.space, backbone,
+                          right_routes, self.space.mark)
+        routes = {}
+        for key in left.routes:
+            routes[key] = [LEFT] + left.routes[key]
+        routes[self.space] = [RIGHT]
+        routes[backbone] = [RIGHT]
+        tie = SeriesTie(self.space)
+        return JoinTerm(left, right, [tie], True, self.space, baseline,
+                        routes, self.space.mark)
+
+    def inject(self, term):
+        if self.space in term.routes:
+            return term
+        assert term.space.spans(self.space)
+        space = self.space.inflate(term.space)
+        if self.space != space:
+            term = self.assembler.inject(space, term)
+            routes = term.routes.copy()
+            routes[self.space] = routes[space]
+            return term.clone(routes=routes)
+        backbone = self.space.axes()
+        term_backbone = term.space.axes()
+        assert term_backbone.concludes(backbone)
+        if self.space == backbone:
+            axis = term_backbone
+            while axis.parent != self.space:
+                axis = axis.parent
+            left = self.assembler.inject(axis, term)
+            assert self.space not in left.routes
+            right_routes = {}
+            right_routes[self.space] = []
+            right = TableTerm(self.space.table, self.space, self.space,
+                              right_routes, self.space.mark)
+            tie = SeriesTie(axis, is_reverse=True)
+            routes = {}
+            for key in left.routes:
+                routes[key] = [LEFT] + left.routes[key]
+            routes[self.space] = [RIGHT]
+            return JoinTerm(left, right, [tie], True, left.space,
+                            left.baseline, routes, left.mark)
+        left = term
+        left = self.assembler.inject(self.space.parent, left)
+        left = self.assembler.inject(backbone, left)
+        assert self.space not in left.routes
+        right_routes = {}
+        right_routes[self.space] = []
+        right_routes[backbone] = []
+        right = TableTerm(self.space.table, self.space, backbone,
+                          right_routes, self.space.mark)
+        backbone_tie = ParallelTie(backbone)
+        parent_tie = SeriesTie(self.space)
+        routes = {}
+        for key in left.routes:
+            routes[key] = [LEFT] + left.routes[key]
+        routes[self.space] = [RIGHT]
+        return JoinTerm(left, right, [backbone_tie, parent_tie], False,
+                        left.space, left.baseline, routes, left.mark)
+
+
+class AssembleJoinedTable(AssembleSpace):
+
+    adapts(JoinedTableSpace, Assembler)
+
+    def assemble(self, baseline):
+        backbone = self.space.axes()
+        if baseline == backbone:
+            routes = {}
+            routes[self.space] = []
+            routes[backbone] = []
+            return TableTerm(self.space.table, self.space, baseline,
+                             routes, self.space.mark)
+        term = self.assembler.assemble(self.space.parent, baseline)
+        assert self.space not in term.routes
+        if backbone in term.routes:
+            if term.space.conforms(self.space):
+                routes = term.routes.copy()
+                routes[self.space] = routes[backbone]
+                term = term.clone(space=self.space, routes=routes)
+                return term
+            assert term.space.dominates(self.space)
+        left = term
+        right_routes = {}
+        right_routes[self.space] = []
+        right_routes[backbone] = []
+        right = TableTerm(self.space.table, self.space, backbone,
+                          right_routes, self.space.mark)
+        routes = {}
+        for key in left.routes:
+            routes[key] = [LEFT]+left.routes[key]
+        routes[self.space] = [RIGHT]
+        routes[backbone] = [RIGHT]
+        tie = SeriesTie(self.space)
+        return JoinTerm(left, right, tie, True, self.space, baseline,
+                        routes, self.space.mark)
+
+    def inject(self, term):
+        if self.space in term.routes:
+            return term
+        assert term.space.spans(self.space)
+        space = self.space.inflate(term.space)
+        if self.space != space:
+            term = self.assembler.inject(space, term)
+            routes = term.routes.copy()
+            routes[self.space] = routes[space]
+            return term.clone(routes=routes)
+        backbone = self.space.axes()
+        term_backbone = term.space.axes()
+        if term_backbone.conclude(self.space):
+            axis = term_backbone
+            while axis.parent != self.space:
+                axis = axis.parent
+            left = self.assembler.inject(axis, term)
+            assert self.space not in left.routes
+            right_routes = {}
+            right_routes[self.space] = []
+            right = TableTerm(self.space.table, self.space, self.space,
+                              right_routes, self.space.mark)
+            tie = SeriesTie(axis, is_reverse=True)
+            routes = {}
+            for key in left.routes:
+                routes[key] = [LEFT] + left.routes[key]
+            routes[self.space] = [RIGHT]
+            return JoinTerm(left, right, [tie], True, left.space,
+                            left.baseline, routes, left.mark)
+        left = term
+        left = self.assembler.inject(self.space.parent, left)
+        if not self.space.is_contracting:
+            left = self.assembler.inject(backbone, left)
+        assert self.space not in left.routes
+        right_routes = {}
+        right_routes[self.space] = []
+        right_routes[backbone] = []
+        right = TableTerm(self.space.table, self.space, backbone,
+                          right_routes, self.space.mark)
+        ties = []
+        if not self.space.is_contracting:
+            backbone_tie = ParallelTie(backbone)
+            ties.append(backbone_tie)
+        parent_tie = SeriesTie(self.space)
+        ties.append(parent_tie)
+        is_inner = True
+        space = self.space
+        while not term_backbone.concludes(space):
+            if not space.is_expanding:
+                is_inner = False
+                break
+            space = space.parent
+        routes = {}
+        for key in left.routes:
+            routes[key] = [LEFT] + left.routes[key]
+        routes[self.space] = [RIGHT]
+        return JoinTerm(left, right, ties, is_inner,
+                        left.space, left.baseline, routes, left.mark)
+
+
+class AssembleScreen(AssembleSpace):
+
+    adapts(ScreenSpace, Assembler)
+
+    def assemble(self, baseline):
+        child = self.assembler.assemble(self.space.parent, baseline)
+        child = self.assembler.inject(self.space.filter, child)
+        assert self.space not in term.routes
+        routes = {}
+        for key in child.routes:
+            routes[key] = [FORWARD] + child.routes[key]
+        routes[self.space] = [FORWARD] + child.routes[self.space.parent]
+        return FilterTerm(child, self.space.filter, self.space, baseline,
+                          routes, self.space.mark)
+
+    def inject(self, term):
+        if self.space in term.routes:
+            return term
+        assert term.space.spans(self.space)
+        space = self.space.inflate(term.space)
+        if self.space != space:
+            term = self.assembler.inject(space, term)
+            routes = term.routes.copy()
+            routes[self.space] = routes[space]
+            return term.clone(routes=routes)
+        left = term
+        term_backbone = term.space.axes()
+        baseline = self.space.axes()
+        right = self.assembler.assemble(self.space, baseline)
+        ties = []
+        if term_backbone.concludes(baseline) or baseline.parent in left.routes:
+            axes = baseline
+            while axes in right.routes:
+                left = self.assembler.inject(axes, left)
+                tie = ParallelTie(axes)
+                ties.append(tie)
+        else:
+            space = self.space
+            while not space.is_axis:
+                space = space.parent
+            assert space in right.routes
+            left = self.assembler.inject(space.parent, left)
+            tie = SeriesTie(space)
+        routes = {}
+        for key in left.routes:
+            routes[key] = [LEFT] + left.routes[key]
+        routes[self.space] = [RIGHT] + right.routes[self.space]
+        return JoinTerm(left, right, ties, False,
+                        left.space, left.baseline, routes, left.mark)
+
+
+class AssembleOrdered(AssembleSpace):
+
+    adapts(OrderedSpace, Assembler)
+
+    def assemble(self, baseline):
+        child = self.assembler.assemble(self.space.parent, baseline)
+        for code, dir in self.space.order:
+            child = self.assembler.inject(code, child)
+        assert self.space not in child.routes
+        routes = {}
+        for key in child.routes:
+            routes[key] = [FORWARD] + child.routes[key]
+        routes[self.space] = [FORWARD] + child.routes[self.space.parent]
+        return OrderingTerm(child, self.space.order,
+                            self.space.limit, self.space.offset,
+                            self.space, baseline, routes, self.space.mark)
+
+
+class AssembleColumn(AssembleUnit):
+
+    adapts(ColumnUnit, Assembler)
+
+    def inject(self, term):
+        return self.assembler.inject(self.code.space, term)
+
+
+class AssembleAggregate(AssembleUnit):
+
+    adapts(AggregateUnit, Assembler)
+
+    def inject(self, term):
+        assert term.space.spans(self.code.space)
+        assert not term.space.spans(self.code.plural_space)
+        assert not self.code.space.span(self.code.plural_space)
+        assert self.code.plural_space.spans(self.code.space)
+        with_base_term = (not self.code.space.dominates(term.space))
+        if with_base_term:
+            base_space = self.code.space
+        else:
+            base_space = term.space
+            left = term
+        base_backbone = base_space.axes()
+        plural_space = self.code.plural_space.inflate(base_space)
+        baseline = plural_space
+        while not base_space.concludes(baseline.parent):
+            baseline = baseline.parent
+        baseline = baseline.axes()
+        plural_term = self.assembler.assemble(plural_space, baseline)
+        ties = []
+        if (base_backbone.concludes(baseline)
+                or baseline.parent in plural_term.routes):
+            axis = baseline
+            while axis in plural_term.routes:
+                tie = ParallelTie(axis)
+                ties.append(tie)
+                axis = axis.parent
+        else:
+            tie = SeriesTie()
+
+
+
+class AssembleSegment(Assemble):
+
+    adapts(SegmentCode, Assembler)
+
+    def assemble(self):
+        child = self.assembler.assemble(self.code.space, self.code.space.scalar)
+        child = self.assembler.inject(self.code, child)
+        select = self.code.elements
+        routes = {}
+        for key in child.routes:
+            routes[key] = [FORWARD] + child.routes[key]
+        return SegmentTerm(child, select, child.space, child.baseline,
+                           routes, self.code.mark)
+
+    def inject(self, term):
+        for element in self.code.elements:
+            for unit in element.get_units():
+                term = self.assembler.inject(unit, term)
+        return term
+
+
+class AssembleQuery(Assemble):
+
+    adapts(QueryCode, Assembler)
+
+    def assemble(self):
+        segment = None
+        if self.code.segment is not None:
+            segment = self.assembler.assemble(self.code.segment)
+        return QueryTerm(self.code, segment, self.code.mark)
+
+
+assemble_adapters = find_adapters()
+
+

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, find_adapters
+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)
+from .lookup import Lookup
+from ..introspect import Introspect
+from ..domain import UntypedStringDomain, UntypedNumberDomain
+from ..error import InvalidArgumentError
+
+
+class Binder(object):
+
+    def bind(self, syntax, parent=None):
+        if parent is None:
+            introspect = Introspect()
+            catalog = introspect()
+            parent = RootBinding(catalog, syntax)
+        bind = Bind(syntax, self)
+        return bind.bind(parent)
+
+    def bind_one(self, syntax, parent=None):
+        if parent is None:
+            introspect = Introspect()
+            catalog = introspect()
+            parent = RootBinding(catalog, syntax)
+        bind = Bind(syntax, self)
+        return bind.bind_one(parent)
+
+
+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:
+            elements = list(self.binder.bind(self.syntax.selector, base))
+        else:
+            lookup = Lookup(base)
+            elements = list(lookup.enumerate(base.syntax))
+        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 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,
+                                 UntypedStringDomain(),
+                                 self.syntax)
+        yield binding
+
+
+class BindNumber(Bind):
+
+    adapts(NumberSyntax, Binder)
+
+    def bind(self, parent):
+        binding = LiteralBinding(parent, self.syntax.value,
+                                 UntypedNumberDomain(),
+                                 self.syntax)
+        yield binding
+
+
+bind_adapters = find_adapters()
+
+

src/htsql/tr/binding.py

+#
+# Copyright (c) 2006-2010, Prometheus Research, LLC
+# Authors: Clark C. Evans <cce@clarkevans.com>,
+#          Kirill Simonov <xi@resolvent.net>
+#
+
+
+"""
+:mod:`htsql.tr.binding`
+=======================
+
+This module declares binding nodes.
+"""
+
+
+from ..entity import CatalogEntity, TableEntity, ColumnEntity, Join
+from ..domain import Domain, VoidDomain
+from .syntax import Syntax
+from ..util import maybe, listof, Node
+
+
+class Binding(Node):
+
+    def __init__(self, parent, domain, syntax):
+        assert isinstance(parent, Binding)
+        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):
+
+    def __init__(self, catalog, syntax):
+        assert isinstance(catalog, CatalogEntity)
+        super(RootBinding, self).__init__(self, VoidDomain(), syntax)
+        self.catalog = catalog
+
+
+class QueryBinding(Binding):
+
+    def __init__(self, parent, segment, syntax):
+        assert isinstance(segment, maybe(SegmentBinding))
+        super(QueryBinding, self).__init__(parent, VoidDomain(), syntax)
+        self.segment = segment
+
+
+class SegmentBinding(Binding):
+
+    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
+
+
+class TableBinding(Binding):
+
+    def __init__(self, parent, table, syntax):
+        assert isinstance(table, TableEntity)
+        super(TableBinding, self).__init__(parent, VoidDomain(), syntax)
+        self.table = table
+
+
+class FreeTableBinding(TableBinding):
+    pass
+
+
+class JoinedTableBinding(TableBinding):
+
+    def __init__(self, parent, table, joins, syntax):
+        assert isinstance(joins, listof(Join)) and len(joins) > 0
+        super(JoinedTableBinding, self).__init__(parent, table, syntax)
+        self.joins = joins
+
+
+class ColumnBinding(Binding):
+
+    def __init__(self, parent, column, syntax):
+        assert isinstance(column, ColumnEntity)
+        super(ColumnBinding, self).__init__(parent, column.domain, syntax)
+        self.column = column
+
+
+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):
+        assert isinstance(filter, Binding)
+        super(SieveBinding, self).__init__(parent, parent.domain, syntax)
+        self.filter = filter
+
+

src/htsql/tr/code.py

+#
+# Copyright (c) 2006-2010, Prometheus Research, LLC
+# Authors: Clark C. Evans <cce@clarkevans.com>,
+#          Kirill Simonov <xi@resolvent.net>
+#
+
+
+"""
+:mod:`htsql.tr.code`
+====================
+
+This module declares space and code nodes.
+"""
+
+
+from ..util import maybe, listof, tupleof, Node
+from ..mark import Mark
+from ..entity import TableEntity, ColumnEntity, Join
+from ..domain import Domain, BooleanDomain, VoidDomain
+from .binding import Binding, QueryBinding
+
+
+class Code(Node):
+
+    def __init__(self, mark, hash=None):
+        assert isinstance(mark, Mark)
+        if hash is None:
+            hash = id(self)
+        self.mark = mark
+        self.hash = hash
+
+    def __hash__(self):
+        return hash(self.hash)
+
+    def __eq__(self, other):
+        return (isinstance(other, Code) and self.hash == other.hash)
+
+
+class Space(Code):
+
+    is_axis = False
+
+    def __init__(self, parent, table,
+                 is_contracting, is_expanding, mark,
+                 hash=None):
+        assert isinstance(parent, maybe(Space))
+        assert isinstance(table, maybe(TableEntity))
+        super(Space, self).__init__(mark, hash=hash)
+        self.parent = parent
+        self.table = table
+        self.is_contracting = is_contracting
+        self.is_expanding = is_expanding
+        if self.parent is not None:
+            self.scalar = self.parent.scalar
+        else:
+            self.scalar = self
+
+    def unfold(self):
+        components = []
+        component = self
+        while component is not None:
+            components.append(component)
+            component = component.parent
+        return components
+
+    def axes(self):
+        space = None
+        for component in reversed(self.unfold()):
+            if component.is_axis:
+                space = component.clone(parent=space)
+        return space
+
+
+class ScalarSpace(Space):
+
+    is_axis = True
+
+    def __init__(self, parent, mark):
+        assert parent is None
+        super(ScalarSpace, self).__init__(None, None, False, False, mark,
+                                          hash=(self.__class__))
+
+
+class FreeTableSpace(Space):
+
+    is_axis = True
+
+    def __init__(self, parent, table, mark):
+        super(FreeTableSpace, self).__init__(parent, table, True, True, mark,
+                                             hash=(self.__class__,
+                                                   parent.hash, table))
+
+
+class JoinedTableSpace(Space):
+
+    is_axis = True
+
+    def __init__(self, parent, join, mark):
+        assert isinstance(join, Join)
+        super(JoinedTableSpace, self).__init__(parent, join.target,
+                                               join.is_contracting,
+                                               join.is_expanding,
+                                               mark,
+                                               hash=(self.__class__,
+                                                     parent.hash,
+                                                     join.__class__,
+                                                     join.foreign_key))
+        self.join = join
+
+
+class ScreenSpace(Space):
+
+    def __init__(self, parent, filter, mark):
+        assert isinstance(filter, Code)
+        assert isinstance(filter.domain, BooleanDomain)
+        super(ScreenSpace, self).__init__(parent, parent.table,
+                                          True, False, mark,
+                                          hash=(self.__class__,
+                                                parent.hash,
+                                                filter.hash))
+        self.filter = filter
+
+
+class OrderedSpace(Space):
+
+    def __init__(self, parent, order, limit, offset, mark):
+        assert isinstance(order, listof(tupleof(Expression, int)))
+        assert isinstance(limit, maybe(int))
+        assert isinstance(offset, maybe(int))
+        is_expanding = (limit is None and offset is None)
+        super(OrderedSpace, self).__init__(parent, parent.table,
+                                           True, is_expanding, mark,
+                                           hash=(self.__class__,
+                                                 parent.hash,
+                                                 tuple(order),
+                                                 limit, offset))
+        self.order = order
+        self.limit = limit
+        self.offset = offset
+
+
+class Expression(Code):
+
+    def __init__(self, domain, mark, hash=None):
+        assert isinstance(domain, Domain)
+        super(Expression, self).__init__(mark, hash=hash)
+        self.domain = domain
+
+    def get_units(self):
+        return []
+
+
+class LiteralExpression(Expression):
+
+    def __init__(self, value, domain, mark):
+        super(LiteralExpression, self).__init__(domain, mark,
+                                                hash=(self.__class__,
+                                                      value, domain))
+        self.value = value
+
+
+class ElementExpression(Expression):
+
+    def __init__(self, code, order):
+        assert isinstance(code, Code)
+        assert order is None or order in [+1, -1]
+        super(ElementExpression, self).__init__(code.domain, code.mark)
+        self.code = code
+        self.order = order
+
+    def get_units(self):
+        return self.code.get_units()
+
+
+class Unit(Expression):
+
+    def __init__(self, domain, space, mark, hash=None):
+        assert isinstance(space, Space)
+        super(Unit, self).__init__(domain, mark, hash=hash)
+        self.space = space
+
+    def get_units(self):
+        return [self]
+
+
+class ColumnUnit(Unit):
+
+    def __init__(self, column, space, mark):
+        assert isinstance(column, ColumnEntity)
+        super(ColumnUnit, self).__init__(column.domain, space, mark,
+                                         hash=(self.__class__,
+                                               column, space.hash))
+        self.column = column
+
+
+class AggregateUnit(Unit):
+
+    def __init__(self, expression, plural_space, space, mark):
+        assert isinstance(expression, Expression)
+        assert isinstance(plural_space, Space)
+        super(AggregateUnit, self).__init__(expression.domain, space, mark,
+                                            hash=(self.__class__,
+                                                  expression.hash,
+                                                  plural_space.hash,
+                                                  space.hash))
+        self.expression = expression
+        self.plural_space = plural_space
+        self.space = space
+
+
+class QueryCode(Code):
+
+    def __init__(self, binding, segment, mark):
+        assert isinstance(binding, QueryBinding)
+        assert isinstance(segment, maybe(SegmentCode))
+        super(QueryCode, self).__init__(mark)
+        self.binding = binding
+        self.syntax = binding.syntax
+        self.segment = segment
+
+
+class SegmentCode(Code):
+
+    def __init__(self, space, elements, mark):
+        assert isinstance(space, Space)
+        assert isinstance(elements, listof(Expression))
+        super(SegmentCode, self).__init__(mark)
+        self.space = space
+        self.elements = elements
+
+

src/htsql/tr/compiler.py

+#
+# Copyright (c) 2006-2010, Prometheus Research, LLC
+# Authors: Clark C. Evans <cce@clarkevans.com>,
+#          Kirill Simonov <xi@resolvent.net>
+#
+
+
+"""
+:mod:`htsql.tr.compile`
+=======================
+
+This module implements the compile adapter.
+"""
+
+
+from ..util import listof
+from ..adapter import Adapter, adapts, find_adapters
+from .code import Expression, LiteralExpression, Unit
+from .sketch import (Sketch, LeafSketch, ScalarSketch, BranchSketch,
+                     SegmentSketch, QuerySketch, Demand,
+                     LeafAppointment, BranchAppointment, FrameAppointment)
+from .frame import (LeafFrame, ScalarFrame, BranchFrame, CorrelatedFrame,
+                    SegmentFrame, QueryFrame, Link, Phrase, EqualityPhrase,
+                    ConjunctionPhrase, LiteralPhrase,
+                    LeafReferencePhrase, BranchReferencePhrase)
+
+
+class Compiler(object):
+
+    def compile(self, sketch, *args, **kwds):
+        compile = Compile(sketch, self)
+        return compile.compile(*args, **kwds)
+
+    def evaluate(self, expression, references):
+        evaluate = Evaluate(expression, self)
+        return evaluate.evaluate(references)
+
+
+class Compile(Adapter):
+
+    adapts(Sketch, Compiler)
+
+    def __init__(self, sketch, compiler):
+        self.sketch = sketch
+        self.compiler = compiler
+
+    def compile(self, *args, **kwds):
+        raise NotImplementedError()
+
+
+class CompileLeaf(Compile):
+
+    adapts(LeafSketch, Compiler)
+
+    def compile(self, demands):
+        assert isinstance(demands, listof(Demand))
+        assert all(demand.sketch in self.sketch.absorbed and
+                   isinstance(demand.appointment, (LeafAppointment,
+                                                   FrameAppointment))
+                   for demand in demands)
+        frame = LeafFrame(self.sketch.table, self.sketch.mark)
+        supplies = {}
+        phrase_by_column = {}
+        for demand in demands:
+            appointment = demand.appointment
+            if appointment.is_leaf:
+                column = appointment.column
+                if column not in phrase_by_column:
+                    phrase = LeafReferencePhrase(frame,
+                            self.sketch.is_inner, column, appointment.mark)
+                    phrase_by_column[column] = phrase
+                supplies[demand] = phrase_by_column[column]
+            elif appointment.is_frame:
+                supplies[demand] = frame
+        return supplies
+
+
+class CompileScalar(Compile):
+
+    adapts(ScalarSketch, Compiler)
+
+    def compile(self, demands):
+        assert isinstance(demands, listof(Demand))
+        assert all(demand.sketch in self.sketch.absorbed and
+                   isinstance(demand.appointment, FrameAppointment)
+                   for demand in demands)
+        frame = ScalarFrame(self.sketch.mark)
+        supplies = {}
+        for demand in demands:
+            appointment = demand.appointment
+            if appointment.is_frame:
+                supplies[demand] = frame
+        return supplies
+
+
+class CompileBranch(Compile):
+
+    adapts(BranchSketch, Compiler)
+
+    def compile(self, demands, BranchFrame=BranchFrame):
+        assert isinstance(demands, listof(Demand))
+        assert all((demand.sketch in self.sketch.absorbed or
+                    demand.sketch in self.sketch.descended) and
+                   isinstance(demand.appointment, (BranchAppointment,
+                                                   FrameAppointment))
+                   for demand in demands)
+
+        child_by_sketch = {}
+        for sketch in self.sketch.absorbed:
+            child_by_sketch[sketch] = None
+        for attachment in self.sketch.linkage:
+            for sketch in attachment.sketch.absorbed:
+                child_by_sketch[sketch] = attachment.sketch
+            for sketch in attachment.sketch.descended:
+                child_by_sketch[sketch] = attachment.sketch
+
+        inner_demands = []
+        for demand in demands:
+            if demand.sketch not in self.sketch.absorbed:
+                inner_demands.append(demand)
+            inner_demands.extend(demand.appointment.get_demands())
+        for appointment in self.sketch.select:
+            inner_demands.extend(appointment.get_demands())
+        for attachment in self.sketch.linkage:
+            inner_demands.extend(attachment.get_demands())
+        for appointment in self.sketch.filter:
+            inner_demands.exend(appointment.get_demands())
+        for appointment in self.sketch.group:
+            inner_demands.extend(appointment.get_demands())
+        for appointment in self.sketch.group_filter:
+            inner_demands.extend(appointment.get_demands())
+        for appointment, dir in self.sketch.order:
+            inner_demands.extend(appointment.get_demands())
+
+        demands_by_child = {}
+        demands_by_child[None] = []
+        for attachment in self.sketch.linkage:
+            demands_by_child[attachment.sketch] = []
+        for demand in inner_demands:
+            child = child_by_sketch[demand.sketch]
+            demands_by_child[child].append(demand)
+
+        inner_supplies = {}
+        for attachment in self.sketch.linkage:
+            child = attachment.sketch
+            child_demands = demands_by_child[child]
+            child_supplies = self.compiler.compile(child, child_demands)
+            inner_supplies.update(child_supplies)
+
+        branch_demands = reversed(demands_by_child[None])
+        for demand in branch_demands:
+            phrase = self.meet(demand.appointment, inner_supplies)
+            inner_supplies[demand] = phrase
+
+        select = []
+        phrase_by_expression = {}
+        for appointment in self.sketch.select:
+            if appointment.expression not in phrase_by_expression:
+                phrase = self.meet(appointment, inner_supplies)
+                phrase_by_expression[appointment.expression] = phrase
+            phrase = phrase_by_expression[appointment.expression]
+            select.append(phrase)
+        position_by_demand = {}
+        position_by_phrase = {}
+        for demand in demands:
+            if demand.appointment.is_frame:
+                continue
+            if demand.sketch in self.sketch.absorbed:
+                appointment = demand.appointment
+                if appointment.expression in phrase_by_expression:
+                    phrase = phrase_by_expression[appointment.expression]
+                else:
+                    phrase = self.meet(appointment, inner_supplies)
+                    phrase_by_expression[appointment.expression] = phrase
+            else:
+                phrase = inner_supplies[demand]
+            if phrase not in position_by_phrase:
+                position_by_phrase[phrase] = len(select)
+                select.append(phrase)
+            position_by_demand[demand] = position_by_phrase[phrase]
+
+        linkage = []
+        for attachment in self.sketch.linkage:
+            if not attachment.sketch.is_proper:
+                continue
+            link = self.link(attachment, inner_supplies)
+            linkage.append(link)
+
+        filter = None
+        conditions = []
+        for appointment in self.sketch.filter:
+            phrase = self.meet(appointment, inner_supplies)
+            conditions.append(phrase)
+        if len(conditions) == 1:
+            filter = conditions[0]
+        elif len(conditions) > 1:
+            filter = Conjunction(conditions, self.sketch.mark)
+
+        group = []
+        for appointment in self.sketch.group:
+            if appointment.expression in phrase_by_expression:
+                phrase = phrase_by_expression[appointment.expression]
+            else:
+                phrase = self.meet(appointment, inner_supplies)
+            group.append(phrase)
+
+        group_filter = None
+        conditions = []
+        for appointment in self.sketch.group_filter:
+            phrase = self.meet(appointment, inner_supplies)
+            conditions.append(phrase)
+        if len(conditions) == 1:
+            group_filter = conditions[0]
+        elif len(conditions) > 1:
+            group_filter = Conjunction(conditions, self.sketch.mark)
+
+        order = []
+        for appointment, dir in self.sketch.order:
+            if appointment.expression in phrase_by_expression:
+                phrase = phrase_by_expression[appointment.expression]
+            else:
+                phrase = self.meet(appointment, inner_supplies)
+            order.append((phrase, dir))
+
+        limit = self.sketch.limit
+        offset = self.sketch.offset
+
+        frame = BranchFrame(select=select,
+                            linkage=linkage,
+                            filter=filter,
+                            group=group,
+                            group_filter=group_filter,
+                            order=order,
+                            limit=limit,
+                            offset=offset,
+                            mark=self.sketch.mark)
+
+        supplies = {}
+        reference_by_position = {}
+        for demand in demands:
+            if demand.appointment.is_frame:
+                supplies[demand] = frame
+            if demand.appointment.is_branch:
+                position = position_by_demand[demand]
+                if position in reference_by_position:
+                    phrase = reference_by_position
+                else:
+                    mark = select[position].mark
+                    phrase = BranchReferencePhrase(frame,
+                            self.sketch.is_inner, position, mark)
+                    reference_by_position[position] = phrase
+                supplies[demand] = phrase
+
+        return supplies