Commits

Kirill Simonov committed c5a939e

Refactoring the term tree and the assembler.

Simplified the term tree structure: added the `id` attribute, use `id`
for routing, generate `baseline` from the routing table, other minor
changes and renames.
Spaces: added `is_scalar` class attribute, renamed `ConvergedSpace`
to `MaskedSpace`.
Added auxiliary expression nodes `GroupExpression` and
`AggregateGroupExpression` to represent collections of code nodes.
Renamed module `htsql.tr.assembler` to `assemble`.
Introduced assembling state and adapters `Assemble` and `Inject`.
Rewritten the assembling process from scratch.

Comments (0)

Files changed (8)

src/htsql/request.py

 from .tr.parse import parse
 from .tr.bind import bind
 from .tr.encode import encode
-from .tr.assembler import Assembler
+from .tr.assemble import assemble
 from .tr.outliner import Outliner
 from .tr.compiler import Compiler
 from .tr.serializer import Serializer
     def translate(self):
         syntax = parse(self.uri)
         binding = bind(syntax)
-        code = encode(binding)
-        assembler = Assembler()
-        term = assembler.assemble(code)
+        expression = encode(binding)
+        term = assemble(expression)
         outliner = Outliner()
         sketch = outliner.outline(term)
         compiler = Compiler()

src/htsql/tr/assemble.py

+#
+# Copyright (c) 2006-2010, Prometheus Research, LLC
+# Authors: Clark C. Evans <cce@clarkevans.com>,
+#          Kirill Simonov <xi@resolvent.net>
+#
+
+
+"""
+:mod:`htsql.tr.assemble`
+========================
+
+This module implements the assemble adapter.
+"""
+
+
+from ..adapter import Adapter, adapts
+from .code import (Expression, Code, Space, ScalarSpace, ProductSpace,
+                   FilteredSpace, OrderedSpace, MaskedSpace,
+                   Unit, ColumnUnit, AggregateUnit, CorrelatedUnit,
+                   QueryExpression, SegmentExpression,
+                   GroupExpression, AggregateGroupExpression)
+from .term import (RoutingTerm, ScalarTerm, TableTerm, FilterTerm, JoinTerm,
+                   CorrelationTerm, ProjectionTerm, OrderTerm, WrapperTerm,
+                   SegmentTerm, QueryTerm, ParallelTie, SeriesTie)
+
+
+class AssemblingState(object):
+
+    def __init__(self):
+        self.next_id = 1
+        self.baseline_stack = []
+        self.baseline = None
+        self.mask_stack = []
+        self.mask = None
+
+    def make_id(self):
+        id = self.next_id
+        self.next_id += 1
+        return id
+
+    def push_baseline(self, baseline):
+        assert isinstance(baseline, Space) and baseline.is_inflated
+        self.baseline_stack.append(self.baseline)
+        self.baseline = baseline
+
+    def pop_baseline(self):
+        self.baseline = self.baseline_stack.pop()
+
+    def push_mask(self, mask):
+        assert isinstance(mask, Space)
+        self.mask_stack.append(self.mask)
+        self.mask = mask
+
+    def pop_mask(self):
+        self.mask = self.mask_stack.pop()
+
+    def assemble(self, expression, baseline=None, mask=None):
+        return assemble(expression, self, baseline=baseline, mask=mask)
+
+    def inject(self, term, expressions):
+        if not expressions:
+            return term
+        if len(expressions) == 1:
+            expression = expressions[0]
+        else:
+            expression = GroupExpression(expressions, term.binding)
+        inject = Inject(expression, term, self)
+        return inject()
+
+
+class Assemble(Adapter):
+
+    adapts(Expression)
+
+    def __init__(self, expression, state):
+        assert isinstance(expression, Expression)
+        assert isinstance(state, AssemblingState)
+        self.expression = expression
+        self.state = state
+
+    def __call__(self):
+        raise NotImplementedError("the assemble adapter is not implemented"
+                                  " for a %r node" % self.expression)
+
+
+class Inject(Adapter):
+
+    adapts(Expression)
+
+    def __init__(self, expression, term, state):
+        assert isinstance(expression, Expression)
+        assert isinstance(term, RoutingTerm)
+        assert isinstance(state, AssemblingState)
+        self.expression = expression
+        self.term = term
+        self.state = state
+
+    def __call__(self):
+        raise NotImplementedError("the inject adapter is not implemented"
+                                  " for a %r node" % self.expression)
+
+
+class AssembleQuery(Assemble):
+
+    adapts(QueryExpression)
+
+    def __call__(self):
+        segment = None
+        if self.expression.segment is not None:
+            segment = self.state.assemble(self.expression.segment)
+        return QueryTerm(segment, self.expression)
+
+
+class AssembleSegment(Assemble):
+
+    adapts(SegmentExpression)
+
+    def __call__(self):
+        kid = self.state.assemble(self.expression.space,
+                                  baseline=self.expression.space.scalar,
+                                  mask=self.expression.space.scalar)
+        order = self.expression.space.ordering()
+        codes = self.expression.elements + [code for code, direction in order]
+        kid = self.state.inject(kid, codes)
+        kid = OrderTerm(self.state.make_id(), kid, order, None, None,
+                        kid.space, kid.routes.copy())
+        return SegmentTerm(self.state.make_id(), kid, self.expression.elements,
+                           kid.space, kid.routes.copy())
+
+
+class AssembleSpace(Assemble):
+
+    adapts(Space)
+
+    def __init__(self, space, state):
+        assert isinstance(space, Space)
+        assert isinstance(state.baseline, Space)
+        backbone = space.inflate()
+        assert backbone.concludes(state.baseline)
+        super(AssembleSpace, self).__init__(space, state)
+        self.space = space
+        self.state = state
+        self.baseline = state.baseline
+        self.mask = state.mask
+        self.backbone = backbone
+
+
+class InjectSpace(Inject):
+
+    adapts(Space)
+
+    def __init__(self, space, term, state):
+        assert isinstance(space, Space)
+        assert term.space.spans(space)
+        super(InjectSpace, self).__init__(space, term, state)
+        self.space = space
+        self.term = term
+        self.state = state
+
+    def __call__(self):
+        if self.space in self.term.routes:
+            return self.term
+        unmasked_space = self.space.prune(self.term.space)
+        if unmasked_space in self.term.routes:
+            routes = self.term.routes.copy()
+            routes[self.space] = routes[unmasked_space]
+            return self.term.clone(routes=routes)
+        if self.term.backbone.concludes(unmasked_space):
+            id = self.state.make_id()
+            next_axis = self.term.baseline
+            while next_axis.base != unmasked_space:
+                next_axis = next_axis.base
+            lkid = self.state.inject(self.term, [next_axis])
+            assert unmasked_space not in lkid.routes
+            rkid = self.state.assemble(unmasked_space,
+                                       baseline=unmasked_space,
+                                       mask=unmasked_space.scalar)
+            assert unmasked_space.base not in rkid.routes
+            tie = SeriesTie(next_axis, is_backward=True)
+            routes = lkid.routes.copy()
+            routes[unmasked_space] = rkid[unmasked_space]
+            routes[self.space] = rkid[unmasked_space]
+            return JoinTerm(id, lkid, rkid, [tie], True, lkid.space, routes)
+        id = self.state.make_id()
+        baseline = unmasked_space
+        while not baseline.is_inflated:
+            baseline = baseline.base
+        lkid = self.term
+        rkid = self.state.assemble(self.space,
+                                   baseline=baseline,
+                                   mask=self.term.space)
+        ties = []
+        if lkid.backbone.concludes(rkid.baseline):
+            lkid = self.state.inject(lkid, [rkid.baseline])
+            axis = lkid.backbone
+            while rkid.baseline.base != axis:
+                if axis in rkid.routes:
+                    tie = ParallelTie(axis)
+                    ties.append(tie)
+            ties.reverse()
+        else:
+            lkid = self.state.inject(lkid, [rkid.baseline.base])
+            tie = SeriesTie(rkid.baseline)
+            ties.append(tie)
+        is_inner = rkid.space.dominates(lkid.space)
+        routes = lkid.routes.copy()
+        routes[self.space] = rkid.routes[self.space]
+        routes[unmasked_space] = rkid.routes[self.space]
+        return JoinTerm(id, lkid, rkid, ties, is_inner, lkid.space, routes)
+
+
+class AssembleScalar(AssembleSpace):
+
+    adapts(ScalarSpace)
+
+    def __call__(self):
+        id = self.state.make_id()
+        routes = { self.space: id }
+        return ScalarTerm(id, self.space, routes)
+
+
+class AssembleProduct(AssembleSpace):
+
+    adapts(ProductSpace)
+
+    def __call__(self):
+        if self.backbone == self.baseline:
+            id = self.state.make_id()
+            routes = { self.space: id, self.backbone: id }
+            return TableTerm(id, self.space, routes)
+        term = self.state.assemble(self.space.base)
+        if self.backbone in term.routes and self.space.conforms(term.space):
+            routes = term.routes.copy()
+            routes[self.space] = routes[self.backbone]
+            return term.clone(routes=routes)
+        id = self.state.make_id()
+        lkid = term
+        rkid = self.state.assemble(self.space, baseline=self.backbone)
+        routes = lkid.routes.copy()
+        routes[self.space] = rkid.routes[self.space]
+        routes[self.backbone] = rkid.routes[self.backbone]
+        tie = SeriesTie(self.space)
+        return JoinTerm(id, lkid, rkid, [tie], True, self.space, routes)
+
+
+class AssembleFiltered(AssembleSpace):
+
+    adapts(FilteredSpace)
+
+    def __call__(self):
+        term = self.state.assemble(self.space.base)
+        if self.space.prune(self.mask) == term.space.prune(self.mask):
+            routes = term.routes.copy()
+            routes[self.space] = routes[self.backbone]
+            return term.clone(space=self.space, routes=routes)
+        id = self.state.make_id()
+        kid = self.state.inject(term, [self.space.filter])
+        routes = kid.routes.copy()
+        routes[self.space] = routes[self.backbone]
+        return FilterTerm(id, kid, self.space.filter, self.space, routes)
+
+
+class AssembleOrdered(AssembleSpace):
+
+    adapts(OrderedSpace)
+
+    def __call__(self):
+        if (self.space.prune(self.mask) == self.space.base.prune(self.mask)
+                or (self.space.limit is None and self.space.offset is None)):
+            term = self.state.assemble(self.space.base)
+            routes = term.routes.copy()
+            routes[self.space] = routes[self.backbone]
+            return term.clone(space=self.space, routes=routes)
+        id = self.state.make_id()
+        kid = self.state.assemble(self.space.base,
+                                  baseline=self.space.scalar,
+                                  mask=self.space.scalar)
+        order = self.space.ordering()
+        codes = [code for code, direction in order]
+        kid = self.state.inject(kid, codes)
+        routes = kid.routes.copy()
+        routes[self.space] = routes[self.backbone]
+        return OrderTerm(id, kid, order, self.space.limit, self.space.offset,
+                         self.space, routes)
+
+
+class InjectCode(Inject):
+
+    adapts(Code)
+
+    def __call__(self):
+        return self.state.inject(self.term, self.expression.units)
+
+
+class InjectUnit(Inject):
+
+    adapts(Unit)
+
+    def __init__(self, unit, term, state):
+        assert isinstance(unit, Unit)
+        super(InjectUnit, self).__init__(unit, term, state)
+        self.unit = unit
+        self.space = unit.space
+
+    def __call__(self):
+        raise NotImplementedError("the inject adapter is not implemented"
+                                  " for a %r node" % self.unit)
+
+
+class InjectColumn(Inject):
+
+    adapts(ColumnUnit)
+
+    def __call__(self):
+        if not self.unit.singular(self.term.space):
+            raise AssembleError("expected a singular expression",
+                                self.unit.mark)
+        return self.state.inject(self.term, [self.unit.space])
+
+
+class InjectAggregate(Inject):
+
+    adapts(AggregateUnit)
+
+    def __call__(self):
+        if not self.unit.singular(self.term.space):
+            raise AssembleError("expected a singular expression",
+                                self.unit.mark)
+        if self.unit in self.term.routes:
+            return self.term
+        is_native = self.space.dominates(self.term.space)
+        if is_native:
+            ground_term = self.term
+        else:
+            baseline = self.space.prune(self.term.space)
+            baseline = unmasked_space
+            while not baseline.is_inflated:
+                baseline = baseline.base
+            ground_term = self.state.assemble(self.space,
+                                              baseline=baseline,
+                                              mask=self.term.space)
+        baseline = self.unit.plural_space.prune(ground_term.space)
+        while not baseline.is_inflated:
+            baseline = baseline.base
+        if not ground_term.space.spans(baseline):
+            while not ground_term.space.spans(baseline.base):
+                baseline = baseline.base
+        plural_term = self.state.assemble(self.unit.plural_space,
+                                          baseline=baseline,
+                                          mask=ground_term.space)
+        plural_term = self.state.inject(plural_term, [self.unit.composite])
+        projected_space = None
+        ties = []
+        axes = []
+        if ground_term.backbone.concludes(plural_term.baseline):
+            ground_term = self.state.inject(ground_term,
+                                            [plural_term.baseline])
+            axis = ground_term.backbone
+            while axis not in plural_term.routes:
+                axis = axis.baseline
+            projected_space = MaskedSpace(axis, ground_term.space,
+                                          self.unit.binding)
+            while axis in plural_term.routes:
+                tie = ParallelTie(axis)
+                ties.append(tie)
+                axes.append(axis)
+                axis = axis.base
+            ties.reverse()
+            axes.reverse()
+        else:
+            axis = plural_term.baseline
+            ground_term = self.state.inject(ground_term, [axis.base])
+            projected_space = MaskedSpace(axis.base, ground_term.space,
+                                          self.unit.binding)
+            tie = SeriesTie(axis)
+            ties.append(tie)
+            axes.append(axis)
+        id = self.state.make_id()
+        routes = {}
+        for axis in axes:
+            routes[axis] = plural_term.routes[axis]
+        routes[projected_space] = routes[axes[-1]]
+        routes[projected_space.inflate()] = routes[axes[-1]]
+        projected_term = ProjectionTerm(id, plural_term, ties,
+                                        projected_space, routes)
+        id = self.state.make_id()
+        lkid = ground_term
+        rkid = projected_term
+        is_inner = projected_term.space.dominates(ground_term.space)
+        routes = lkid.routes.copy()
+        routes[self.unit] = projected_term.id
+        term = JoinTerm(id, lkid, rkid, ties, is_inner, lkid.space, routes)
+        if is_native:
+            return term
+        id = self.state.make_id()
+        lkid = self.term
+        rkid = term
+        ties = []
+        if lkid.backbone.concludes(rkid.baseline):
+            lkid = self.state.inject(lkid, [rkid.baseline])
+            axis = lkid.backbone
+            while rkid.baseline.base != axis:
+                if axis in rkid.routes:
+                    tie = ParallelTie(axis)
+                    ties.append(tie)
+            ties.reverse()
+        else:
+            lkid = self.state.inject(lkid, [rkid.baseline.base])
+            tie = SeriesTie(rkid.baseline)
+            ties.append(tie)
+        is_inner = rkid.space.dominates(lkid.space)
+        routes = lkid.routes.copy()
+        routes[self.unit] = projected_term.id
+        return JoinTerm(id, lkid, rkid, ties, is_inner, lkid.space, routes)
+
+
+class InjectCorrelated(Inject):
+
+    adapts(CorrelatedUnit)
+
+    def __call__(self):
+        if not self.unit.singular(self.term.space):
+            raise AssembleError("expected a singular expression",
+                                self.unit.mark)
+        if self.unit in self.term.routes:
+            return self.term
+        is_native = self.space.dominates(self.term.space)
+        if is_native:
+            ground_term = self.term
+        else:
+            baseline = self.space.prune(self.term.space)
+            baseline = unmasked_space
+            while not baseline.is_inflated:
+                baseline = baseline.base
+            ground_term = self.state.assemble(self.space,
+                                              baseline=baseline,
+                                              mask=self.term.space)
+        baseline = self.unit.plural_space.prune(ground_term.space)
+        while not baseline.is_inflated:
+            baseline = baseline.base
+        if not ground_term.space.spans(baseline):
+            while not ground_term.space.spans(baseline.base):
+                baseline = baseline.base
+        plural_term = self.state.assemble(self.unit.plural_space,
+                                          baseline=baseline,
+                                          mask=ground_term.space)
+        plural_term = self.state.inject(plural_term, [self.unit.composite])
+        plural_term = WrapperTerm(self.state.make_id(), plural_term,
+                                  plural_term.space, plural_term.routes.copy())
+        ties = []
+        axes = []
+        if ground_term.backbone.concludes(plural_term.baseline):
+            ground_term = self.state.inject(ground_term,
+                                            [plural_term.baseline])
+            axis = ground_term.backbone
+            while axis not in plural_term.routes:
+                axis = axis.baseline
+            while axis in plural_term.routes:
+                tie = ParallelTie(axis)
+                ties.append(tie)
+                axes.append(axis)
+                axis = axis.base
+            ties.reverse()
+        else:
+            axis = plural_term.baseline
+            ground_term = self.state.inject(ground_term, [axis.base])
+            tie = SeriesTie(axis)
+            ties.append(tie)
+            axes.append(axis)
+        id = self.state.make_id()
+        lkid = ground_term
+        rkid = plural_term
+        routes = lkid.routes.copy()
+        routes[self.unit] = plural_term.id
+        term = CorrelationTerm(id, lkid, rkid, ties, lkid.space, routes)
+        if is_native:
+            return term
+        id = self.state.make_id()
+        lkid = self.term
+        rkid = term
+        ties = []
+        if lkid.backbone.concludes(rkid.baseline):
+            lkid = self.state.inject(lkid, [rkid.baseline])
+            axis = lkid.backbone
+            while rkid.baseline.base != axis:
+                if axis in rkid.routes:
+                    tie = ParallelTie(axis)
+                    ties.append(tie)
+            ties.reverse()
+        else:
+            lkid = self.state.inject(lkid, [rkid.baseline.base])
+            tie = SeriesTie(rkid.baseline)
+            ties.append(tie)
+        is_inner = rkid.space.dominates(lkid.space)
+        routes = lkid.routes.copy()
+        routes[self.unit] = plural_term.id
+        return JoinTerm(id, lkid, rkid, ties, is_inner, lkid.space, routes)
+
+
+class InjectGroup(Inject):
+
+    adapts(GroupExpression)
+
+    def __call__(self):
+        units = []
+        for code in self.expression.codes:
+            for unit in code.units:
+                units.append(unit)
+        aggregate_forms = []
+        aggregate_form_to_units = {}
+        for unit in units:
+            if (isinstance(unit, AggregateUnit) and
+                    unit not in self.term.routes):
+                form = (unit.plural_space, unit.space)
+                if form not in aggregate_form_to_units:
+                    aggregate_forms.append(form)
+                    aggregate_form_to_units[form] = []
+                aggregate_form_to_units[form].append(unit)
+        aggregate_groups = []
+        for form in aggregate_forms:
+            plural_space, space = form
+            form_units = aggregate_form_to_units[form]
+            if len(form_units) > 1:
+                group = AggregateGroupExpression(plural_space, space,
+                                                 form_units, self.term.binding)
+                aggregate_groups.append(group)
+        term = self.term
+        for group in aggregate_groups:
+            term = self.state.inject(term, [group])
+        for unit in units:
+            term = self.state.inject(term, [unit])
+        return term
+
+
+class InjectAggregateGroup(Inject):
+
+    adapts(AggregateGroupExpression)
+
+    def __call__(self):
+        term = self.term
+        for aggregate in self.expression.aggregates:
+            term = self.state.inject(term, [aggregate])
+        return term
+
+
+def assemble(expression, state=None, baseline=None, mask=None):
+    if state is None:
+        state = AssemblingState()
+    if baseline is not None:
+        state.push_baseline(baseline)
+    if mask is not None:
+        state.push_mask(mask)
+    assemble = Assemble(expression, state)
+    term = assemble()
+    if baseline is not None:
+        state.pop_baseline()
+    if mask is not None:
+        state.pop_mask()
+    return term
+
+

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
-from .code import (Expression, Code, Space, ScalarSpace, CrossProductSpace,
-                   JoinProductSpace, FilteredSpace, OrderedSpace,
-                   ConvergedSpace, Unit, ColumnUnit, AggregateUnit,
-                   CorrelatedUnit, QueryExpression, SegmentExpression)
-from .term import (TableTerm, ScalarTerm, FilterTerm, JoinTerm,
-                   CorrelationTerm, ProjectionTerm, OrderingTerm, HangingTerm,
-                   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(Expression, 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 AssembleCode(Assemble):
-
-    adapts(Code, Assembler)
-
-    def inject(self, term):
-        for unit in self.code.units:
-            term = self.assembler.inject(unit, term)
-        return term
-
-
-class AssembleUnit(AssembleCode):
-
-    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.base != self.space:
-            axis = axis.base
-        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(CrossProductSpace, Assembler)
-
-    def assemble(self, baseline):
-        backbone = self.space.inflate()
-        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.base, 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.prune(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.inflate()
-        term_backbone = term.space.inflate()
-        assert term_backbone.concludes(backbone)
-        if self.space == backbone:
-            axis = term_backbone
-            while axis.base != self.space:
-                axis = axis.base
-            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.base, 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)
-        base_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, base_tie], False,
-                        left.space, left.baseline, routes, left.mark)
-
-
-class AssembleJoinedTable(AssembleSpace):
-
-    adapts(JoinProductSpace, Assembler)
-
-    def assemble(self, baseline):
-        backbone = self.space.inflate()
-        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.base, 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.prune(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.inflate()
-        term_backbone = term.space.inflate()
-        if term_backbone.concludes(self.space):
-            axis = term_backbone
-            while axis.base != self.space:
-                axis = axis.base
-            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.base, 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)
-        base_tie = SeriesTie(self.space)
-        ties.append(base_tie)
-        is_inner = True
-        space = self.space
-        while not term_backbone.concludes(space):
-            if not space.is_expanding:
-                is_inner = False
-                break
-            space = space.base
-        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(FilteredSpace, Assembler)
-
-    def assemble(self, baseline):
-        child = self.assembler.assemble(self.space.base, baseline)
-        child = self.assembler.inject(self.space.filter, 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.base]
-        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.prune(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.inflate()
-        baseline = self.space.inflate()
-        right = self.assembler.assemble(self.space, baseline)
-        ties = []
-        if term_backbone.concludes(baseline) or baseline.base in left.routes:
-            inflate = baseline
-            while inflate in right.routes:
-                left = self.assembler.inject(inflate, left)
-                tie = ParallelTie(inflate)
-                ties.append(tie)
-                inflate = inflate.base
-        else:
-            space = self.space
-            while not space.is_axis:
-                space = space.base
-            assert space in right.routes
-            left = self.assembler.inject(space.base, 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.base, baseline)
-        assert self.space not in child.routes
-        order = []
-        codes = set()
-        for code, dir in self.space.ordering():
-            if code not in codes:
-                order.append((code, dir))
-                codes.add(code)
-        for code, dir in order:
-            child = self.assembler.inject(code, child)
-        routes = {}
-        for key in child.routes:
-            routes[key] = [FORWARD] + child.routes[key]
-        routes[self.space] = [FORWARD] + child.routes[self.space.base]
-        return OrderingTerm(child, order, self.space.limit, self.space.offset,
-                            self.space, baseline, routes, self.space.mark)
-
-
-    def inject(self, term):
-        assert self.space in term.routes
-        return term
-
-
-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):
-        if self.code in term.routes:
-            return term
-        assert term.space.spans(self.code.space)
-        assert not term.space.spans(self.code.plural_space)
-        assert not self.code.space.spans(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.inflate()
-        plural_space = self.code.plural_space.prune(base_space)
-        baseline = plural_space
-        while not base_space.concludes(baseline.base):
-            baseline = baseline.base
-        baseline = baseline.inflate()
-        plural_term = self.assembler.assemble(plural_space, baseline)
-        plural_term = self.assembler.inject(self.code.composite, plural_term)
-        ties = []
-        inflate = []
-        if (base_backbone.concludes(baseline)
-                or baseline.base in plural_term.routes):
-            axis = baseline
-            while axis in plural_term.routes:
-                inflate.append(axis)
-                tie = ParallelTie(axis)
-                ties.append(tie)
-                axis = axis.base
-        else:
-            inflate.append(baseline)
-            tie = SeriesTie(baseline)
-            ties.append(tie)
-        relative_space = ConvergedSpace(baseline.base,
-                                       plural_space, self.code.binding)
-        routes = {}
-        for axis in inflate:
-            routes[axis] = [FORWARD] + plural_term.routes[axis]
-        routes[self.code] = []
-        projected_term = ProjectionTerm(plural_term, ties, relative_space,
-                                        baseline.base, routes,
-                                        self.code.mark)
-        if with_base_term:
-            assert False
-        if (base_backbone.concludes(baseline)
-                or baseline.base in plural_term.routes):
-            for axis in inflate:
-                term = self.assembler.inject(axis, term)
-        else:
-            for axis in inflate:
-                term = self.assembler.inject(axis.base, term)
-        left = term
-        right = projected_term
-        routes = {}
-        for key in left.routes:
-            routes[key] = [LEFT] + left.routes[key]
-        routes[self.code] = [RIGHT]
-        return JoinTerm(left, right, ties, False,
-                        left.space, left.baseline, routes, left.mark)
-
-
-class AssembleCorrelated(AssembleUnit):
-
-    adapts(CorrelatedUnit, Assembler)
-
-    def inject(self, term):
-        if self.code in term.routes:
-            return term
-        assert term.space.spans(self.code.space)
-        assert not term.space.spans(self.code.plural_space)
-        assert not self.code.space.spans(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.inflate()
-        plural_space = self.code.plural_space.prune(base_space)
-        baseline = plural_space
-        while not base_space.concludes(baseline.base):
-            baseline = baseline.base
-        baseline = baseline.inflate()
-        plural_term = self.assembler.assemble(plural_space, baseline)
-        plural_term = self.assembler.inject(self.code.composite, plural_term)
-        routes = {}
-        for key in plural_term.routes:
-            routes[key] = [FORWARD] + plural_term.routes[key]
-        plural_term = HangingTerm(plural_term,
-                                  plural_term.space, plural_term.baseline,
-                                  routes, plural_term.mark)
-        ties = []
-        inflate = []
-        if (base_backbone.concludes(baseline)
-                or baseline.base in plural_term.routes):
-            axis = baseline
-            while axis in plural_term.routes:
-                inflate.append(axis)
-                tie = ParallelTie(axis)
-                ties.append(tie)
-                axis = axis.base
-        else:
-            inflate.append(baseline)
-            tie = SeriesTie(baseline)
-            ties.append(tie)
-        if with_base_term:
-            assert False
-        if (base_backbone.concludes(baseline)
-                or baseline.base in plural_term.routes):
-            for axis in inflate:
-                term = self.assembler.inject(axis, term)
-        else:
-            for axis in inflate:
-                term = self.assembler.inject(axis.base, term)
-        left = term
-        right = plural_term
-        routes = {}
-        for key in left.routes:
-            routes[key] = [LEFT] + left.routes[key]
-        routes[self.code] = [RIGHT]
-        return CorrelationTerm(left, right, ties,
-                               left.space, left.baseline, routes, left.mark)
-
-
-class AssembleSegment(Assemble):
-
-    adapts(SegmentExpression, Assembler)
-
-    def assemble(self):
-        scalar = self.code.space
-        while scalar.base is not None:
-            scalar = scalar.base
-        child = self.assembler.assemble(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.units:
-                term = self.assembler.inject(unit, term)
-        return term
-
-
-class AssembleQuery(Assemble):
-
-    adapts(QueryExpression, 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)
-
-

src/htsql/tr/code.py

         Indicates whether the space is an axis space, that is, the shape
         of the space rows differs from the shape of its base.
 
+    `is_scalar` (Boolean)
+        Indicates if the space is the scalar space.
+
     The constructor arguments:
 
     `base` (:class:`Space` or ``None``)
     `is_inflated` (Boolean)
         Indicates if the space is an inflation, that is, the space itself
         and all its prefixes are axis spaces.
+
+    `scalar` (:class:`ScalarSpace`)
+        The root scalar space.
     """
 
     is_axis = False
+    is_scalar = False
 
     def __init__(self, base, table, is_contracting, is_expanding,
                  binding, equality_vector=None):
         # Indicates that the space itself and all its prefixes are axes.
         self.is_inflated = (base is None or
                             (base.is_inflated and self.is_axis))
+        # Extract the root scalar space from the base; if there is no base,
+        # `self` must be the root itself.
+        self.scalar = (base.scalar if base is not None else self)
 
     def ordering(self, with_strong=True, with_weak=True):
         """
                 # proceed to the next pair of prefixes.
                 my_prefixes.pop()
                 their_prefixes.pop()
-            elif their_prefix.is_contrating and not their_prefix.is_axis:
+            elif their_prefix.is_contracting and not their_prefix.is_axis:
                 # We got prefixes representing different operations; however
                 # the dominated prefix represents a non-axis operation that
                 # does not increase the cardinality of its base.  Therefore
                 # we could ignore this prefix and proceed further.
-                # operation.
                 their_prefixes.pop()
             else:
                 # The prefixes start to diverge; break from the loop.
 
     # Scalar space is an axis space.
     is_axis = True
+    is_scalar = True
 
     def __init__(self, base, binding):
         # We keep `base` among constructor arguments despite it being
         return "(%s ? %s)" % (self.base, self.filter)
 
 
-class ConvergedSpace(Space):
+class MaskedSpace(Space):
     """
-    Represents a converged space.
+    Represents a masked space.
 
-    A converged space `A ^ B`, where `A` and `B` are spaces, consists of
+    A masked space `A ^ B`, where `A` and `B` are spaces, consists of
     rows from `A` that have at least one convergent row from `B`.
+
+    This is an auxiliary space node used internally by the assembler.
     """
 
-    def __init__(self, base, filter, binding):
-        assert isinstance(filter, Space)
-        super(ConvergedSpace, self).__init__(
+    def __init__(self, base, mask, binding):
+        assert isinstance(mask, Space)
+        # FIXME: explain!
+        #is_expanding = base.is_scalar
+        is_expanding = False
+        super(MaskedSpace, self).__init__(
                     base=base,
                     table=base.table,
                     is_contracting=True,
-                    is_expanding=False,
+                    is_expanding=is_expanding,
                     binding=binding,
-                    equality_vector=(base, filter))
-        self.filter = filter
+                    equality_vector=(base, mask))
+        self.mask = mask
 
     def __str__(self):
         # Display:
-        #   (<base> ^ <filter>)
-        return "(%s ^ %s)" % (self.base, self.filter)
+        #   (<base> ^ <mask>)
+        return "(%s ^ %s)" % (self.base, self.mask)
 
 
 class OrderedSpace(Space):
     """
 
 
+class GroupExpression(Expression):
+    """
+    Represents a collection of code nodes.
+
+    This is an auxiliary expression node used internally by the assembler.
+
+    `codes` (a list of :class:`Code`)
+        A collection of code nodes.
+    """
+
+    def __init__(self, codes, binding):
+        assert isinstance(codes, listof(Code))
+        super(GroupExpression, self).__init__(binding)
+        self.codes = codes
+
+    def __str__(self):
+        # Display the collection:
+        #   <code>, <code>, ...
+        return ", ".join(str(code) for code in self.codes)
+
+
+class AggregateGroupExpression(Expression):
+    """
+    Represents a collection of aggregate units sharing the same base and
+    plural spaces.
+
+    This is an auxiliary expression node used internally by the assembler.
+
+    `plural_space` (:class:`Space`)
+        The plural space of the aggregates.
+
+    `space` (:class:`Space`)
+        The base space of the aggregates.
+
+    `aggregates` (a list of :class:`AggregateUnit`)
+        A collection of aggregate units.  All units must have the same
+        base and plural spaces.
+    """
+
+    def __init__(self, plural_space, space, aggregates, binding):
+        assert isinstance(plural_space, Space)
+        assert isinstance(space, Space)
+        assert isinstance(aggregates, listof(AggregateUnit))
+        assert all(plural_space == aggregate.plural_space and
+                   space == aggregate.space
+                   for aggregate in aggregates)
+        super(AggregateGroupExpression, self).__init__(binding)
+        self.plural_space = plural_space
+        self.space = space
+        self.aggregates = aggregates
+
+    def __str__(self):
+        # Display the collection:
+        #   <aggregate>, <aggregate>, ...: <plural_space> -> <space>
+        return ("%s: %s -> %s"
+                % (", ".join(str(aggregate) for aggregate in self.aggregates),
+                   self.plural_space, self.space))
+
+

src/htsql/tr/outliner.py

 
 
 from ..adapter import Adapter, adapts
-from .term import (Term, TableTerm, ScalarTerm, FilterTerm, JoinTerm,
-                   CorrelationTerm, ProjectionTerm, OrderingTerm, HangingTerm,
-                   SegmentTerm, QueryTerm, Tie, ParallelTie, SeriesTie)
+from .term import (Term, RoutingTerm, TableTerm, ScalarTerm, FilterTerm,
+                   JoinTerm, CorrelationTerm, ProjectionTerm, OrderTerm,
+                   WrapperTerm, SegmentTerm, QueryTerm,
+                   Tie, ParallelTie, SeriesTie)
 from .code import (Unit, ColumnUnit, AggregateUnit, CorrelatedUnit,
                    Space, ScalarSpace, CrossProductSpace, JoinProductSpace)
 from .sketch import (Sketch, LeafSketch, ScalarSketch, BranchSketch,
 
 class Outliner(object):
 
-    def outline(self, sketch, *args, **kwds):
-        outline = Outline(sketch, self)
-        return outline.outline(*args, **kwds)
+    def __init__(self):
+        self.sketch_by_term_id = {}
+        self.term_by_term_id = {}
 
-    def delegate(self, unit, sketch, term):
+    def outline(self, term, *args, **kwds):
+        if isinstance(term, RoutingTerm):
+            self.term_by_term_id[term.id] = term
+        outline = Outline(term, self)
+        sketch = outline.outline(*args, **kwds)
+        if isinstance(term, RoutingTerm):
+            self.sketch_by_term_id[term.id] = sketch
+        return sketch
+
+    def delegate(self, unit, term):
         delegate = Delegate(unit, self)
-        return delegate.delegate(sketch, term)
+        return delegate.delegate(term)
 
-    def appoint(self, expression, sketch, term):
+    def appoint(self, expression, term):
         demand_by_unit = {}
         for unit in expression.units:
-            demand = self.delegate(unit, sketch, term)
+            demand = self.delegate(unit, term)
             demand_by_unit[unit] = demand
         return BranchAppointment(expression, demand_by_unit)
 
     adapts(FilterTerm, Outliner)
 
     def outline(self, is_inner=True, is_proper=True):
-        child = self.outliner.outline(self.term.child)
+        child = self.outliner.outline(self.term.kid)
         attachment = Attachment(child)
         linkage = [attachment]
-        appointment = self.outliner.appoint(self.term.filter, child,
-                                            self.term.child)
+        appointment = self.outliner.appoint(self.term.filter,
+                                            self.term.kid)
         filter = [appointment]
         return BranchSketch(linkage=linkage,
                             filter=filter,
     adapts(JoinTerm, Outliner)
 
     def outline(self, is_inner=True, is_proper=True):
-        left_child = self.outliner.outline(self.term.left_child)
+        left_child = self.outliner.outline(self.term.lkid)
         left_attachment = Attachment(left_child)
-        right_child = self.outliner.outline(self.term.right_child,
+        right_child = self.outliner.outline(self.term.rkid,
                                             is_inner=self.term.is_inner)
         connections = []
         for tie in self.term.ties:
             for left_unit, right_unit in self.outliner.connect(tie):
                 left_appointment = self.outliner.appoint(left_unit,
-                                    left_child, self.term.left_child)
+                                                         self.term.lkid)
                 right_appointment = self.outliner.appoint(right_unit,
-                                    right_child, self.term.right_child)
+                                                          self.term.rkid)
                 connection = Connection(left_appointment, right_appointment)
                 connections.append(connection)
         right_attachment = Attachment(right_child, connections)
     adapts(CorrelationTerm, Outliner)
 
     def outline(self, is_inner=True, is_proper=True):
-        left_child = self.outliner.outline(self.term.left_child)
+        left_child = self.outliner.outline(self.term.lkid)
         left_attachment = Attachment(left_child)
-        right_child = self.outliner.outline(self.term.right_child,
+        right_child = self.outliner.outline(self.term.rkid,
                                             is_inner=False,
                                             is_proper=False)
         connections = []
         for tie in self.term.ties:
             for left_code, right_code in self.outliner.connect(tie):
                 left_appointment = self.outliner.appoint(left_code,
-                                    left_child, self.term.left_child)
+                                                         self.term.lkid)
                 right_appointment = self.outliner.appoint(right_code,
-                                    right_child, self.term.right_child)
+                                                          self.term.rkid)
                 connection = Connection(left_appointment, right_appointment)
                 connections.append(connection)
         right_attachment = Attachment(right_child, connections)
     adapts(ProjectionTerm, Outliner)
 
     def outline(self, is_inner=True, is_proper=True):
-        child = self.outliner.outline(self.term.child)
+        child = self.outliner.outline(self.term.kid)
         attachment = Attachment(child)
         linkage = [attachment]
         group = []
         for tie in self.term.ties:
             for left_code, right_code in self.outliner.connect(tie):
-                appointment = self.outliner.appoint(right_code, child,
-                                                    self.term.child)
+                appointment = self.outliner.appoint(right_code, self.term.kid)
                 group.append(appointment)
         return BranchSketch(linkage=linkage,
                             group=group,
                             mark=self.term.mark)
 
 
-class OutlineOrdering(Outline):
+class OutlineOrder(Outline):
 
-    adapts(OrderingTerm, Outliner)
+    adapts(OrderTerm, Outliner)
 
     def outline(self, is_inner=True, is_proper=True):
-        child = self.outliner.outline(self.term.child)
+        child = self.outliner.outline(self.term.kid)
         attachment = Attachment(child)
         linkage = [attachment]
         order = []
         for code, dir in self.term.order:
-            appointment = self.outliner.appoint(code, child, self.term.child)
+            appointment = self.outliner.appoint(code, self.term.kid)
             order.append((appointment, dir))
         return BranchSketch(linkage=linkage,
                             order=order,
                             mark=self.term.mark)
 
 
-class OutlineHanging(Outline):
+class OutlineWrapper(Outline):
 
-    adapts(HangingTerm, Outliner)
+    adapts(WrapperTerm, Outliner)
 
     def outline(self, is_inner=True, is_proper=True):
-        child = self.outliner.outline(self.term.child)
+        child = self.outliner.outline(self.term.kid)
         attachment = Attachment(child)
         linkage = [attachment]
         return BranchSketch(linkage=linkage,
     adapts(SegmentTerm, Outliner)
 
     def outline(self):
-        child = self.outliner.outline(self.term.child)
+        child = self.outliner.outline(self.term.kid)
         attachment = Attachment(child)
         linkage = [attachment]
         select = []
-        for code in self.term.select:
-            appointment = self.outliner.appoint(code, child, self.term.child)
+        for code in self.term.elements:
+            appointment = self.outliner.appoint(code, self.term.kid)
             select.append(appointment)
         return SegmentSketch(select=select,
                              linkage=linkage,
         self.unit = unit
         self.outliner = outliner
 
-    def delegate(self, sketch, term):
+    def delegate(self, term):
         raise NotImplementedError()
 
 
 
     adapts(ColumnUnit, Outliner)
 
-    def delegate(self, sketch, term):
-        route = term.routes[self.unit.space]
-        for idx in route:
-            sketch = sketch.linkage[idx].sketch
+    def delegate(self, term):
+        term_id = term.routes[self.unit.space]
+        sketch = self.outliner.sketch_by_term_id[term_id]
         appointment = LeafAppointment(self.unit.column,
                                       self.unit.mark)
         return Demand(sketch, appointment)
 
     adapts(AggregateUnit, Outliner)
 
-    def delegate(self, sketch, term):
-        route = term.routes[self.unit]
-        for idx in route:
-            sketch = sketch.linkage[idx].sketch
-            term = term.children[idx]
-        appointment = self.outliner.appoint(self.unit.composite,
-                                            sketch.linkage[0].sketch,
-                                            term.children[0])
+    def delegate(self, term):
+        term_id = term.routes[self.unit]
+        sketch = self.outliner.sketch_by_term_id[term_id]
+        term = self.outliner.term_by_term_id[term_id]
+        appointment = self.outliner.appoint(self.unit.composite, term.kids[0])
         return Demand(sketch, appointment)
 
 
 
     adapts(CorrelatedUnit, Outliner)
 
-    def delegate(self, sketch, term):
-        route = term.routes[self.unit]
-        for idx in route:
-            sketch = sketch.linkage[idx].sketch
-            term = term.children[idx]
-        appointment = self.outliner.appoint(self.unit.composite,
-                                            sketch, term)
+    def delegate(self, term):
+        term_id = term.routes[self.unit]
+        sketch = self.outliner.sketch_by_term_id[term_id]
+        term = self.outliner.term_by_term_id[term_id]
+        appointment = self.outliner.appoint(self.unit.composite, term)
         return Demand(sketch, appointment)
 
 

src/htsql/tr/sketch.py

         assert isinstance(segment, maybe(SegmentSketch))
         super(QuerySketch, self).__init__(mark)
         self.term = term
-        self.code = term.code
+        self.code = term.expression
         self.binding = term.binding
         self.syntax = term.syntax
         self.segment = segment

src/htsql/tr/term.py

 
 
 from ..util import Node, listof, dictof, oneof, tupleof, maybe
-from ..mark import Mark
-from ..entity import TableEntity
 from ..domain import BooleanDomain
 from .code import Expression, Space, Code, Unit, QueryExpression
 
 
-LEFT = 0
-RIGHT = 1
-FORWARD = 0
+class Term(Node):
 
+    def __init__(self, expression):
+        assert isinstance(expression, Expression)
+        self.expression = expression
+        self.binding = expression.binding
+        self.syntax = expression.syntax
+        self.mark = expression.mark
 
-class Term(Node):
+    def __str__(self):
+        return str(self.expression)
+
+
+class RoutingTerm(Term):
 
     is_nullary = False
     is_unary = False
     is_binary = False
 
-    def __init__(self, children, mark):
-        assert isinstance(children, listof(Term))
-        assert isinstance(mark, Mark)
-        self.children = children
-        self.mark = mark
+    def __init__(self, id, kids, space, routes):
+        assert isinstance(id, int)
+        assert isinstance(kids, listof(RoutingTerm))
+        assert isinstance(space, Space)
+        assert isinstance(routes, dictof(oneof(Space, Unit), int))
+        assert space in routes
+        backbone = space.inflate()
+        assert backbone in routes
+        baseline = backbone
+        while baseline.base in routes:
+            baseline = baseline.base
+        super(RoutingTerm, self).__init__(space)
+        self.id = id
+        self.kids = kids
+        self.space = space
+        self.routes = routes
+        self.backbone = backbone
+        self.baseline = baseline
 
+    def __str__(self):
+        # Display:
+        #   <baseline> -> <space>
+        return "%s -> %s" % (self.baseline, self.space)
 
-class NullaryTerm(Term):
+
+class NullaryTerm(RoutingTerm):
 
     is_nullary = True
 
-    def __init__(self, space, baseline, routes, mark):
-        assert isinstance(space, Space)
-        assert isinstance(baseline, Space) and baseline.is_inflated
-        assert isinstance(routes, dictof(oneof(Space, Unit), listof(int)))
-        super(NullaryTerm, self).__init__([], mark)
-        self.space = space
-        self.baseline = baseline
-        self.routes =  routes
+    def __init__(self, id, space, routes):
+        super(NullaryTerm, self).__init__(id, [], space, routes)
 
 
-class UnaryTerm(Term):
+class UnaryTerm(RoutingTerm):
 
     is_unary = True
 
-    def __init__(self, child, space, baseline, routes, mark):
-        assert isinstance(child, Term)
-        assert isinstance(space, Space)
-        assert isinstance(baseline, Space) and baseline.is_inflated
-        assert isinstance(routes, dictof(oneof(Space, Unit), listof(object)))
-        super(UnaryTerm, self).__init__([child], mark)
-        self.child = child
-        self.space = space
-        self.baseline = baseline
-        self.routes = routes
+    def __init__(self, id, kid, space, routes):
+        super(UnaryTerm, self).__init__(id, [kid], space, routes)
+        self.kid = kid
 
 
-class BinaryTerm(Term):
+class BinaryTerm(RoutingTerm):
 
     is_binary = True
 
-    def __init__(self, left_child, right_child,
-                 space, baseline, routes, mark):
-        assert isinstance(left_child, Term)
-        assert isinstance(right_child, Term)
-        assert isinstance(space, Space)
-        assert isinstance(baseline, Space) and baseline.is_inflated
-        assert isinstance(routes, dictof(oneof(Space, Unit), listof(object)))
-        super(BinaryTerm, self).__init__([left_child, right_child], mark)
-        self.left_child = left_child
-        self.right_child = right_child
-        self.space = space
-        self.baseline = baseline
-        self.routes = routes
+    def __init__(self, id, lkid, rkid, space, routes):
+        super(BinaryTerm, self).__init__(id, [lkid, rkid], space, routes)
+        self.lkid = lkid
+        self.rkid = rkid
+
+
+class ScalarTerm(NullaryTerm):
+
+    def __init__(self, id, space, routes):
+        assert space.table is None
+        super(ScalarTerm, self).__init__(id, space, routes)
 
 
 class TableTerm(NullaryTerm):
 
-    def __init__(self, table, space, baseline, routes, mark):
-        assert isinstance(table, TableEntity)
-        assert space.table is table
-        super(TableTerm, self).__init__(space, baseline, routes, mark)
-        self.table = table
-
-
-class ScalarTerm(NullaryTerm):
-
-    def __init__(self, space, baseline, routes, mark):
-        assert space.table is None
-        super(ScalarTerm, self).__init__(space, baseline, routes, mark)
+    def __init__(self, id, space, routes):
+        assert space.table is not None
+        super(TableTerm, self).__init__(id, space, routes)
+        self.table = space.table
 
 
 class FilterTerm(UnaryTerm):
 
-    def __init__(self, child, filter, space, baseline, routes, mark):
-        assert isinstance(filter, Expression)
-        assert isinstance(filter.domain, BooleanDomain)
-        super(FilterTerm, self).__init__(child, space, baseline,
-                                         routes, mark)
+    def __init__(self, id, kid, filter, space, routes):
+        assert (isinstance(filter, Code) and
+                isinstance(filter.domain, BooleanDomain))
+        super(FilterTerm, self).__init__(id, kid, space, routes)
         self.filter = filter
 
 
 class JoinTerm(BinaryTerm):
 
-    def __init__(self, left_child, right_child, ties, is_inner,
-                 space, baseline, routes, mark):
+    def __init__(self, id, lkid, rkid, ties, is_inner, space, routes):
         assert isinstance(ties, listof(Tie))
         assert isinstance(is_inner, bool)
-        super(JoinTerm, self).__init__(left_child, right_child,
-                                       space, baseline, routes, mark)
+        super(JoinTerm, self).__init__(id, lkid, rkid, space, routes)
         self.ties = ties
         self.is_inner = is_inner
 
 
 class CorrelationTerm(BinaryTerm):
 
-    def __init__(self, left_child, right_child, ties,
-                 space, baseline, routes, mark):
+    def __init__(self, id, lkid, rkid, ties, space, routes):
         assert isinstance(ties, listof(Tie))
-        super(CorrelationTerm, self).__init__(left_child, right_child,
-                                              space, baseline, routes, mark)
+        super(CorrelationTerm, self).__init__(id, lkid, rkid, space, routes)
         self.ties = ties
 
 
 class ProjectionTerm(UnaryTerm):
 
-    def __init__(self, child, ties, space, baseline, routes, mark):
+    def __init__(self, id, kid, ties, space, routes):
         assert isinstance(ties, listof(Tie))
-        super(ProjectionTerm, self).__init__(child, space, baseline,
-                                             routes, mark)
+        super(ProjectionTerm, self).__init__(id, kid, space, routes)
         self.ties = ties
 
 
-class OrderingTerm(UnaryTerm):
+class OrderTerm(UnaryTerm):
 
-    def __init__(self, child, order, limit, offset,
-                 space, baseline, routes, mark):
+    def __init__(self, id, kid, order, limit, offset, space, routes):
         assert isinstance(order, listof(tupleof(Code, int)))
         assert isinstance(limit, maybe(int))
         assert isinstance(offset, maybe(int))
-        super(OrderingTerm, self).__init__(child, space, baseline,
-                                           routes, mark)
+        super(OrderTerm, self).__init__(id, kid, space, routes)
         self.order = order
         self.limit = limit
         self.offset = offset
 
 
-class HangingTerm(UnaryTerm):
+class WrapperTerm(UnaryTerm):
     pass
 
 
 class SegmentTerm(UnaryTerm):
 
-    def __init__(self, child, select, space, baseline, routes, mark):
-        assert isinstance(select, listof(Code))
-        super(SegmentTerm, self).__init__(child, space, baseline, routes, mark)
-        self.select = select
+    def __init__(self, id, kid, elements, space, routes):
+        assert isinstance(elements, listof(Code))
+        super(SegmentTerm, self).__init__(id, kid, space, routes)
+        self.elements = elements
 
 
 class QueryTerm(Term):
 
-    def __init__(self, code, segment, mark):
-        assert isinstance(code, QueryExpression)
+    def __init__(self, segment, expression):
         assert isinstance(segment, maybe(SegmentTerm))
-        children = []
-        if segment is not None:
-            children.append(segment)
-        super(QueryTerm, self).__init__(children, mark)
-        self.code = code
-        self.binding = code.binding
-        self.syntax = code.syntax
+        assert isinstance(expression, QueryExpression)
+        super(QueryTerm, self).__init__(expression)
         self.segment = segment
 
 
     def __init__(self, space):
         assert isinstance(space, Space) and space.is_axis
         self.space = space
-        self.mark = space.mark
 
 
 class SeriesTie(Tie):
 
     is_series = True
 
-    def __init__(self, space, is_reverse=False):
+    def __init__(self, space, is_backward=False):
         assert isinstance(space, Space) and space.is_axis
-        assert isinstance(is_reverse, bool)
+        assert isinstance(is_backward, bool)
         self.space = space
-        self.is_reverse = is_reverse
-        self.mark = space.mark
+        self.is_reverse = is_backward
 
 

test/output/pgsql.yaml

 
          ----
          /course.sort(credits)?department='acc'
-         SELECT "course"."department", "course"."number", "course"."title", "course"."credits", "course"."description" FROM (SELECT "course"."department", "course"."number", "course"."title", "course"."credits", "course"."description" FROM "ad"."course" AS "course" WHERE ("course"."department" = 'acc') ORDER BY 4 ASC, 1 ASC, 2 ASC) AS "course" ORDER BY 4 ASC, 1 ASC, 2 ASC
+         SELECT "course"."department", "course"."number", "course"."title", "course"."credits", "course"."description" FROM "ad"."course" AS "course" WHERE ("course"."department" = 'acc') ORDER BY 4 ASC, 1 ASC, 2 ASC
     - uri: /course.sort(credits).limit(1,1)?department='acc'
       status: 200 OK
       headers:
 
          ----
          /course.sort(credits).limit(1,1)?department='acc'
-         SELECT "course"."department", "course"."number", "course"."title", "course"."credits", "course"."description" FROM (SELECT "course"."department", "course"."number", "course"."title", "course"."credits", "course"."description" FROM (SELECT "course"."department", "course"."number", "course"."title", "course"."credits", "course"."description" FROM "ad"."course" AS "course" ORDER BY 4 ASC, 1 ASC, 2 ASC) AS "course" WHERE ("course"."department" = 'acc') ORDER BY 4 ASC, 1 ASC, 2 ASC LIMIT 1 OFFSET 1) AS "course" ORDER BY 4 ASC, 1 ASC, 2 ASC
+         SELECT "course"."department", "course"."number", "course"."title", "course"."credits", "course"."description" FROM (SELECT "course"."department", "course"."number", "course"."title", "course"."credits", "course"."description" FROM "ad"."course" AS "course" WHERE ("course"."department" = 'acc') ORDER BY 4 ASC, 1 ASC, 2 ASC LIMIT 1 OFFSET 1) AS "course" ORDER BY 4 ASC, 1 ASC, 2 ASC
   - id: title-decorator
     tests:
     - uri: /{null() as Title, null() as 'Title with whitespaces'}
 
          ----
          /school{code+,name}
-         SELECT "school"."code", "school"."name" FROM "ad"."school" AS "school" ORDER BY 1 ASC
+         SELECT "school"."code", "school"."name" FROM "ad"."school" AS "school" ORDER BY 1 ASC, 1 ASC
     - uri: /school{code-,name}
       status: 200 OK
       headers:
 
          ----
          /school{code-,name}
-         SELECT "school"."code", "school"."name" FROM "ad"."school" AS "school" ORDER BY 1 DESC
+         SELECT "school"."code", "school"."name" FROM "ad"."school" AS "school" ORDER BY 1 DESC, 1 ASC
     - uri: /school{code--,name}
       status: 200 OK
       headers:
 
          ----
          /school{code--,name}
-         SELECT "school"."code", "school"."name" FROM "ad"."school" AS "school" ORDER BY 1 ASC
+         SELECT "school"."code", "school"."name" FROM "ad"."school" AS "school" ORDER BY 1 ASC, 1 ASC
     - uri: /school{name as Title+}
       status: 200 OK
       headers:
 
          ----
          /course.sort(department+,credits-){department,title,credits}?number<200
-         SELECT "course"."department", "course"."title", "course"."credits" FROM (SELECT "course"."department", "course"."title", "course"."credits", "course"."number" FROM "ad"."course" AS "course" WHERE ("course"."number" < 200) ORDER BY 1 ASC, 3 DESC, 4 ASC) AS "course" ORDER BY 1 ASC, 3 DESC, "course"."number" ASC
+         SELECT "course"."department", "course"."title", "course"."credits" FROM "ad"."course" AS "course" WHERE ("course"."number" < 200) ORDER BY 1 ASC, 3 DESC, 1 ASC, "course"."number" ASC
   - id: simple-filters
     tests:
     - uri: /school?code='ns'