
""" sql semantics 
"""

### trim unused methods.
### make assns use equivalence classes.

### maybe eventually implement disj-conj-eq optimizations

### note: for multithreading x.relbind(...) should ALWAYs return
###   a fresh copy of structure (sometimes in-place now).

### note: binding of order by is dubious with archiving,
###    should not bind IN PLACE, leave unbound elts alone!

### need to fix serialization/deserialization of btand and btor
###

# use kjbuckets builtin if available
try:
    import kjbuckets
except ImportError:
    import kjbuckets0
    kjbuckets = kjbuckets0
    
Tuple = kjbuckets.kjDict
Graph = kjbuckets.kjGraph
Set = kjbuckets.kjSet

import sys, traceback
### debug
#sys.stderr = sys.stdin
    
# operations on simple tuples, mostly from kjbuckets
#def maketuple(thing):
#    """try to make a tuple from thing.
#       thing should be a dictionary or sequence of (name, value)
#       or other tuple."""
#    from types import DictType
#    if type(thing)==DictType:
#       return Tuple(thing.items() )
#    else: return Tuple(thing)
    
def no_ints_nulls(list):
    """in place remove all ints, Nones from a list (for null handling)"""
    tt = type
    nn = None
    from types import IntType
    count = 0
    for x in list:
        if tt(x) is not IntType and x is not nn:
           list[count] = x
           count = count+1
    del list[count:]
    return list

# stuff for bound tuples.

class HashJoiner:

    def __init__(self, bt, relname, attributes, relation, witness):
        self.relname = relname
        self.attributes = attributes
        self.relation = relation
        self.witness = witness 
        self.bt = bt
        eqs = bt.eqs
        #print "relname", relname
        #print "attributes", attributes
        #print "relation", relation
        #print "witness", witness
        #print "bt", bt
        transform = self.transform = kjbuckets.kjDict()
        rbindings = self.rbindings = kjbuckets.kjSet()
        for a in attributes:
            b = (relname, a)
            transform[b] = a
            rbindings[b] = b
        self.eqs = eqs = eqs + kjbuckets.kjGraph(rbindings)
        witness = witness.remap(eqs)
        known = kjbuckets.kjSet(witness.keys()) & rbindings
        batts = tuple(known.items())
        if not batts:
           atts = ()
        elif len(batts)==1:
           atts = ( transform[batts[0]], )
        else:
           atts = transform.dump(batts)
        self.atts = atts
        self.batts = batts
        self.transform = transform
        eqs = bt.eqs
        #eqs = (rbindings * eqs)
        self.eqs = eqs = eqs + kjbuckets.kjGraph(rbindings)
        self.transformG = transformG = eqs * transform
        assns = self.assns = bt.assns
        self.rassns = assns.remap( ~transformG )
        
    def relbind(self, db, atts):
        rel = self.relation
        #print "rel is ", rel, type(rel)
        #print dir(rel)
        if rel.is_view:
            self.relation = rel.relbind(db, atts)
        return self
        
    def uncache(self):
        rel = self.relation
        if rel.is_view:
           self.relation.uncache()
        
    def join(self, subseq):
        relname = self.relname
        result = []
        assns = self.assns
        if not subseq: return result
        # apply equalities to unitary subseq (embedded subq)
        if len(subseq)==1:
           subseq0 = subseq[0]
           subseq0r = subseq0.remap(self.eqs)
           if subseq0r is None:
              return [] # inconsistent
           subseq0 = subseq0 + subseq0r + assns
           if subseq0.Clean() is None:
              return [] # inconsistent
           subseq = [subseq0]
        rassns = self.rassns
        #print "rassns", rassns
        #print "subseq", subseq
        if rassns is None:
           #print "inconsistent btup"
           return []
        relation = self.relation
        #print "assns", assns
        transformG = self.transformG
        #print "transformG", transformG
        transform = self.transform
        atts = self.atts
        batts = self.batts
        #print "batts, atts", batts, atts
        if not batts:
           #print "cross product", relname
           tuples = relation.rows()
           for t in tuples:
               #print "t is", t
               if rassns:
                  t = (t + rassns).Clean()
               if t is None:
                  #print "preselect fails"
                  continue
               new = t.remap(transformG)
               #print "new is", new
               if new is None:
                  #print "transform fails"
                  continue
               for subst in subseq:
                   #print "subst", subst
                   if subst:
                      add = (subst + new).Clean()
                   else:
                      add = new
                   #print "add is", add
                   if add is not None:
                      result.append(add)
        else:
           # hash join
           #print "hash join"
           # first try to use an index
           index = relation.choose_index(atts)
           #print transform
           if index is not None:
              #print "index join", index.name, relname
              #print index.index.keys()
              #print "rassns", rassns
              atts = index.attributes()
              invtransform = ~transform
              if len(atts)==1:
                 batts = (invtransform[atts[0]],)
              else:
                 batts = invtransform.dump(atts)
              hash_tups = 1
              tindex = index.index
              # memoize converted tuples
              tindex0 = {}
              test = tindex.has_key
              test0 = tindex0.has_key
              for i in xrange(len(subseq)):
                  subst = subseq[i]
                  #print "substs is", subst
                  its = subst.dump(batts)
                  #print "its", its
                  othersubsts = []
                  if test0(its):
                     othersubsts = tindex0[its]
                  elif test(its):
                     tups = tindex[its]
                     for t in tups:
                         #print "t before", t
                         t = (t+rassns).Clean()
                         #print "t after", t
                         if t is None: continue
                         new = t.remap(transformG)
                         #print "new", new
                         if new is None: continue
                         othersubsts.append(new)
                  tindex0[its] = othersubsts
                  for other in othersubsts:
                      #print "adding", other, subst
                      add = (other + subst).Clean()
                      if add is not None:
                         result.append(add)
           # hash join
           #print "hash join"
           else:
               tuples = relation.rows()
               if len(subseq)<len(tuples):
                  #print "hash subseq", relname
                  subseqindex = {}
                  test = subseqindex.has_key
                  for i in xrange(len(subseq)):
                      subst = subseq[i]
                      its = subst.dump(batts)
                      #print "items1", subseq, batts, its
                      if test(its):
                         subseqindex[its].append(subst)
                      else:
                         subseqindex[its] = [ subst ]
                  for t in tuples:
                      #print "on", t
                      if rassns:
                         t = (t+rassns).Clean()
                      if t is None:
                         #print "preselect fails"
                         continue
                      its = t.dump(atts)
                      #print "items2", its
                      if test(its):
                         new = t.remap(transformG)
                         #print "...new", new
                         if new is None:
                            #print "transform fails"
                            continue
                         l = subseqindex[its]
                         for subst in l:
                             add = (subst + new).Clean()
                             #print "adding", add
                             if add is not None:
                                result.append(add)
               else:
                  #print "hash tuples", relname
                  tindex = {}
                  test = tindex.has_key
                  for i in xrange(len(tuples)):
                      t = tuples[i]
                      if rassns:
                         t = (t + rassns).Clean()
                      if t is None:
                         #print "preselect fails"
                         continue
                      new = t.remap(transformG)
                      #print "new is", new
                      if new is None:
                         #print "transform fails"
                         continue
                      its = t.dump(atts)
                      #print "items3", its
                      if test(its):
                         tindex[its].append(new)
                      else:
                         tindex[its] = [ new ]
                  for subst in subseq:
                      its = subst.dump(batts)
                      #print "items4", its
                      if test(its):
                         n = tindex[its]
                         for new in n:
                             add = (subst + new).Clean()
                             if add is not None:
                                result.append(add)
        #print "hashjoin result"
        #for x in result:
            #print x
            #break
        return result
        
### essentially, specialized pickle for this app:
        
def deserialize(description):
    """simple protocol for generating a marshallable ob"""
    #print "deserialize", description
    from types import TupleType
    if type(description) is not TupleType:
        return description # base type
    try:
        (name, desc) = description
    except:
        return description # base type
    if name == "tuple":
        # tuple case
        return desc
    ### other special cases here...
    if name == "list":
        # list case: map deserialize across desc
        return map(deserialize, desc)
    # all other cases are classes of sqlsem
    import sqlsem
    klass = getattr(sqlsem, name)
    (args1, args2) = desc
    args1 = tuple(map(deserialize, args1))
    ob = apply(klass, args1)
    ob.demarshal(args2)
    return ob
    
def serialize(ob):
    """dual of deserialize."""
    from types import ListType
    tt = type(ob)
    # for lists map serialize across members
    #if tt is ListType:
    #    return ("list", map(serialize, ob))
    try:
        #print ob.__class__, ob
        args1 = ob.initargs()
        #print "args1 before", args1
        args1 = tuple(map(serialize, args1))
        #print "args1 after", args1
        args2 = ob.marshaldata()
        return (ob.__class__.__name__, (args1, args2))
    except:
        from types import InstanceType
        #tt = type(ob)
        if tt is InstanceType:
           #ext = traceback.extract_tb(sys.exc_traceback)
           #for x in ext: 
               #print x
           #print
           #print sys.exc_type, sys.exc_value
           #print ob.__class__
           raise ValueError, "couldn't serialize %s %s" % (
             tt, ob.__class__)
        # assume base type otherwise
        return ob
        
# invariant:
#   deserialize(serialize(ob)) returns semantic copy of ob
#   serialize(ob) is marshallable
# ie,
#   args1 = ob.initargs() # init args
#   args1d = map(serialize, args1) # serialized
#   args2 = ob.marshaldata() # marshalable addl info
#   # assert args1d, args2 are marshallable
#   args1copy = map(deserialize, args1)
#   ob2 = ob.__class__(args1copy)
#   ob2 = ob2.demarshal(args2)
#   # assert ob2 is semantic copy of ob

class SimpleRecursive:
    """Simple Recursive structure, only requires initargs"""
    def demarshal(self, args):
        pass
    def marshaldata(self):
        return ()

class BoundTuple:

   clean = 1  # false if inconsistent
   closed = 0 # true if equality constraints inferred

   def __init__(self, **bindings):
       """bindings are name>simpletuple associations."""
       self.eqs = Graph()
       self.assns = Tuple()
       for (name, simpletuple) in bindings.items():
           self.bind(name, simpletuple)
          
   def initargs(self):
       return ()
       
   def marshaldata(self):
       #print "btp marshaldata", self
       return (self.eqs.items(), self.assns.items(), self.clean, self.closed)
       
   def demarshal(self, args):
       (eitems, aitems, self.clean, self.closed) = args
       self.eqs = kjbuckets.kjGraph(eitems)
       self.assns = kjbuckets.kjDict(aitems)
           
   def relbind(self, dict, db):
       """return bindings of self wrt dict rel>att"""
       result = BoundTuple()
       e2 = result.eqs
       a2 = result.assns
       for ((a,b), (c,d)) in self.eqs.items():
           if a is None:
              try:
                 a = dict[b]
              except KeyError:
                 raise NameError, `b`+": ambiguous or unknown attribute"
           if c is None:
              try:
                 c = dict[d]
              except KeyError:
                 raise NameError, `d`+": ambiguous or unknown attribute"
           e2[(a,b)] = (c,d)
       for ((a,b), v) in self.assns.items():
           if a is None:
              try:
                 a = dict[b]
              except KeyError:
                 raise NameError, `b`+": ambiguous or unknown attribute"
           a2[(a,b)] = v
       result.closed = self.closed
       result.clean = self.clean
       return result
           
   #def known(self, relname):
   #    """return ([(relname, a1), ...], [a1, ...])
   #       for attributes ai of relname known in self."""
   #    atts = []
   #    batts = []
   #    for x in self.assns.keys():
   #        (r,a) = x
   #        if r==relname:
   #           batts.append(x)
   #           atts.append(a)
   #    return (batts, atts)
                 
   def relorder(self, db, allrels):
       """based on known constraints, pick an
          ordering for materializing relations.
          db is database (ignored currently)
          allrels is names of all relations to include (list)."""
       ### not very smart about indices yet!!!
       if len(allrels)<2:
          # doesn't matter
          return allrels
       order = []
       eqs = self.eqs
       assns = self.assns
       kjSet = kjbuckets.kjSet
       kjGraph = kjbuckets.kjGraph
       pinned = kjSet()
       has_index = kjSet()
       needed = kjSet(allrels)
       akeys = assns.keys()
       for (r,a) in akeys:
           pinned[r]=r # pinned if some value known
       known_map = kjGraph(akeys)
       for r in known_map.keys():
           rknown = known_map.neighbors(r)
           if db.has_key(r):
              rel = db[r]
              index = rel.choose_index(rknown)
              if index is not None:
                 has_index[r] = r # has an index!
       if pinned: pinned = pinned & needed
       if has_index: has_index = has_index & needed
       related = kjGraph()
       for ( (r1, a1), (r2, a2) ) in eqs.items():
           related[r1]=r2 # related if equated to other
           related[r2]=r1 # redundant if closed.
       if related: related = needed * related * needed
       chosen = kjSet()
       pr = kjSet(related) & pinned
       # choose first victim
       if has_index:
          choice = has_index.choose_key()
       elif pr:
          choice = pr.choose_key()
       elif pinned:
          choice = pinned.choose_key()
       elif related:
          choice = related.choose_key()
       else:
          return allrels[:] # give up!
       while pinned or related or has_index:
          order.append(choice)
          chosen[choice] = 1
          if pinned.has_key(choice):
             del pinned[choice]
          if related.has_key(choice):
             del related[choice]
          if has_index.has_key(choice):
             del has_index[choice]
          nexts = related * chosen
          if nexts:
             # prefer a relation related to chosen
             choice = nexts.choose_key()
          elif pinned:
             # otherwise one that is pinned
             choice = pinned.choose_key()
          elif related:
             # otherwise one that relates to something...
             choice = related.choose_key()
       others = kjSet(allrels) - chosen
       if others: order = order + others.items()
       return order
           
   def domain(self):
       kjSet = kjbuckets.kjSet
       return kjSet(self.eqs) + kjSet(self.assns)
       
   def __repr__(self):
       from string import join
       result = []
       for ( (name, att), value) in self.assns.items():
           result.append( "%s.%s=%s" % (name, att, `value`) )
       for ( (name, att), (name2, att2) ) in self.eqs.items():
           result.append( "%s.%s=%s.%s" % (name, att, name2, att2) )
       if self.clean:
          if not result: return "TRUE"
       else:
          result.insert(0, "FALSE")
       result.sort()
       return join(result, " & ")
           
   def equate(self, equalities):
       """add equalities to self, only if not closed.
          equalities should be seq of ( (name, att), (name, att) )
          """
       if self.closed: raise ValueError, "cannot add equalities! Closed!"
       e = self.eqs
       for (a, b) in equalities:
           e[a] = b
           
   def close(self):
       """infer equalities, if consistent.
          only recompute equality closure if not previously closed.
          return None on inconsistency.
       """
       neweqs = self.eqs
       if not self.closed:
          self.eqs = neweqs = (neweqs + ~neweqs).tclosure() # sym, trans closure
          self.closed = 1
       # add trivial equalities to self
       for x in self.assns.keys():
           if not neweqs.member(x,x):
              neweqs[x] = x
       newassns = self.assns.remap(neweqs)
       if newassns is not None and self.clean:
          self.assns = newassns
          #self.clean = 1
          return self
       else:
          self.clean = 0
          return None
          
   def share_eqs(self):
       """make clone of self that shares equalities, closure.
          note: will share future side effects to eqs too."""
       result = BoundTuple()
       result.eqs = self.eqs
       result.closed = self.closed
       return result
       
   def __add__(self, other):
       """combine self with other, return closure."""
       result = self.share_eqs()
       se = self.eqs
       oe = other.eqs
       if (se is not oe) and (se != oe):
          result.eqs = se + oe
          result.closed = 0
       ra= result.assns = self.assns + other.assns
       result.clean = result.clean and (ra.Clean() is not None)
       return result.close()
       
   def __and__(self, other):
      """return closed constraints common to self and other."""
      result = BoundTuple()
      se = self.eqs
      oe = other.eqs
      if (se is oe) or (se == oe):
         result.eqs = self.eqs
         result.closed = self.closed
      else:
         result.eqs = self.eqs & other.eqs
      result.assns = self.assns & other.assns
      result.clean = self.clean and other.clean
      return result.close()
      
   def __hash__(self):
      # note: equalities don't enter into hash computation!
      # (some may be spurious)
      self.close()
      return hash(self.assns)# ^ hash(self.eqs)
      
   def __cmp__(self, other):
       test = cmp(self.__class__, other.__class__)
       if test: return test
       sa = self.assns
       oa = other.assns
       test = cmp(sa, oa)
       if test: return test
       kjSet = kjbuckets.kjSet
       kjGraph = kjbuckets.kjSet
       se = self.eqs
       se = kjGraph(se) - kjGraph(kjSet(se))
       oe = other.eqs
       oe = kjGraph(oe) - kjGraph(kjSet(oe))
       return cmp(se, oe)
      
class BoundExpression(SimpleRecursive):
   """superclass for all bound expressions.
      except where overloaded expressions are binary
      with self.left and self.right
   """
   
   contains_aggregate = 0 # default
   
   def __init__(self, left, right):
       self.left = left
       self.right = right
       self.contains_aggregate = left.contains_aggregate or right.contains_aggregate
       
   def initargs(self):
       return (self.left, self.right)
       
   def uncache(self):
       """prepare for execution, clear cached data."""
       self.left.uncache()
       self.right.uncache()
   
   # eventually add converters...
   def equate(self,other):
       """return predicate equating self and other.
          Overload for special cases, please!"""
       return NontrivialEqPred(self, other)
       
   def attribute(self):
       return (None, `self`)
       
   def le(self, other):
       """predicate self<=other"""
       return LessEqPred(self, other)
   
   # these should be overridden for 2 const case someday...
   def lt(self, other):
       """predicate self<other"""
       return LessPred(self, other)
       
   def __coerce__(self, other):
       return (self, other)
       
   def __add__(self, other):
       return BoundAddition(self, other)
       
   def __sub__(self, other):
       return BoundSubtraction(self, other)
       
   def __mul__(self, other):
       return BoundMultiplication(self, other)
       
   def __neg__(self):
       return BoundMinus(self)
       
   def __div__(self, other):
       return BoundDivision(self, other)
       
   def relbind(self, dict, db):
       Class = self.__class__
       return Class(self.left.relbind(dict, db), self.right.relbind(dict, db))
   
   def __repr__(self):
       return "(%s)%s(%s)" % (self.left, self.op, self.right)
       
   def domain(self):
       return self.left.domain() + self.right.domain()
   # always overload value
   
class BoundMinus(BoundExpression, SimpleRecursive):
   def __init__(self, thing):
       self.thing = thing
       self.contains_aggregate = thing.contains_aggregate
   def initargs(self):
       return (self.thing,)
   def __repr__(self):
       return "-(%s)" % (self.thing,)
   def value(self, contexts):
       from types import IntType
       tt = type
       result = self.thing.value(contexts)
       for i in xrange(len(contexts)):
           if tt(contexts[i]) is not IntType:
              result[i] = -result[i]
       return result
   def relbind(self, dict, db):
       Class = self.__class__
       return Class(self.thing.relbind(dict,db))
   def uncache(self):
       self.thing.uncache()
   def domain(self):
       return self.thing.domain()
       

### stuff for aggregation
class Average(BoundMinus):
       
   contains_aggregate = 1

   def __init__(self, expr, distinct=0):
       self.distinct = distinct
       if expr.contains_aggregate:
          raise ValueError, `expr`+": aggregate in aggregate "+self.name
       self.thing = expr
       
   name = "Average"
   def __repr__(self):
       distinct = ""
       if self.distinct:
          distinct = "distinct "
       return "%s(%s%s)" % (self.name, distinct, self.thing)

   def relbind(self, dict, db):
       Class = self.__class__
       return Class(self.thing.relbind(dict,db), self.distinct)
       
   def value(self, contexts):
       if not contexts: return [] # ???
       test = contexts[0]
       if not test.has_key(None):
          return [self.all_value(contexts)]
       else:
          return self.agg_value(contexts)
          
   def dvalues(self, values):
       d = {}
       for i in xrange(len(values)):
           d[values[i]] = 1
       return d.keys()
          
   def all_value(self, contexts):
       thing = self.thing
       values = self.clean(thing.value(contexts), contexts)
       if self.distinct:
          values = self.dvalues(values)
       return self.op(values)
       
   def clean(self, values, contexts):
       D = {}
       from types import IntType
       tt = type
       for i in xrange(len(contexts)):
           if tt(contexts[i]) is not IntType:
              D[i] = values[i]
       return D.values()
       
   def agg_value(self, contexts):
       from types import IntType
       tt = type
       result = list(contexts)
       for i in xrange(len(contexts)):
           context = contexts[i]
           if tt(context) is not IntType:
              result[i] = self.all_value( context[None] )
       return result
       
   def op(self, values):
       sum = 0
       for x in values:
           sum = sum+x
       return sum/(len(values)*1.0)
       
class Sum(Average):
   name = "Sum"
   def op(self, values):
       if not values: return 0
       sum = values[0]
       for x in values[1:]:
           sum = sum+x
       return sum
       
class Median(Average):
   name = "Median"
   def op(self, values):
       if not values:
          raise ValueError, "Median of empty set"
       values = list(values)
       values.sort()
       lvals = len(values)
       return values[lvals/2]
   
class Maximum(Average):
   name = "Maximum"
   def op(self, values):
       return max(values)
       
class Minimum(Average):
   name = "Minimum"
   def op(self, values):
       return min(values)
       
class Count(Average):
   name = "Count"
   distinct = 0
   def __init__(self, thing, distinct = 0):
       if thing=="*":
          self.thing = "*"
       else:
          Average.__init__(self, thing, distinct)
          
   def domain(self):
       thing = self.thing
       if thing=="*":
          return kjbuckets.kjSet()
       return thing.domain()
       
   def all_value(self, contexts):
       thing = self.thing
       if thing=="*" or not self.distinct:
          test = self.clean(contexts, contexts)
          #print "count len", len(test), contexts[0]
          return len(test)
       return Average.all_value(self, contexts)
   def op(self, values):
       return len(values)
   def relbind(self, dict, db):
       if self.thing=="*":
          return self
       return Average.relbind(self, dict, db)
   def uncache(self):
       if self.thing!="*": self.thing.uncache()

def aggregate(assignments, exprlist):
    """aggregates are a assignments with special
       attribute None > list of subtuple"""
    lexprs = len(exprlist)
    if lexprs<1:
       raise ValueError, "aggregate on no expressions?"
    lassns = len(assignments)
    pairs = list(exprlist)
    for i in xrange(lexprs):
        expr = exprlist[i]
        attributes = [expr.attribute()]*lassns
        values = expr.value(assignments)
        pairs[i] = map(None, attributes, values)
    #for x in pairs:
        #print "pairs", x
    if lexprs>1:
       newassnpairs = apply(map, (None,)+tuple(pairs))
    else:
       newassnpairs = pairs[0]
    #for x in newassnpairs:
        #print "newassnpairs", x
    xassns = range(lassns)
    dict = {}
    test = dict.has_key
    for i in xrange(lassns):
        thesepairs = newassnpairs[i]
        thissubassn = assignments[i]
        if test(thesepairs):
           dict[thesepairs].append(thissubassn)
        else:
           dict[thesepairs] = [thissubassn]
    items = dict.items()
    result = list(items)
    kjDict = kjbuckets.kjDict
    if lexprs>1:
       for i in xrange(len(items)):
           (pairs, subassns) = items[i]
           #print "pairs", pairs
           #print "subassns", subassns
           D = kjDict(pairs)
           D[None] = subassns
           result[i] = D
    else:
       for i in xrange(len(items)):
           (pair, subassns) = items[i]
           #print "pair", pair
           #print "subassns", subassns
           result[i] = kjDict( [pair, (None, subassns)] )
    return result

### stuff for order_by
class DescExpr(BoundMinus):
   """special wrapper used only for order by descending
      for things with no -thing operation (eg, strings)"""
      
   def __init__(self, thing):
       self.thing = thing
       self.contains_aggregate = thing.contains_aggregate

   def value(self, contexts):
       from types import IntType, StringType
       tt = type
       result = self.thing.value(contexts)
       allwrap = None
       allnowrap = None
       for i in xrange(len(contexts)):
           if tt(contexts[i]) is not IntType:
              resulti = result[i]
              # currently assume only value needing wrapping is string
              if tt(resulti) is StringType:
                 if allnowrap is not None:
                    raise ValueError, "(%s, %s) cannot order desc" % (allnowrap, resulti)
                 allwrap = resulti
                 result[i] = descOb(resulti)
              else:
                 if allwrap is not None:
                    raise ValueError, "(%s, %s) cannot order desc" % (allwrap, resulti)
                 allnowrap = resulti
                 result[i] = -resulti
       return result
   def __repr__(self):
       return "DescExpr(%s)" % (self.thing,)
   def orderbind(self, order):
       """order is list of (att, expr)."""
       Class = self.__class__
       return Class(self.thing.orderbind(order))
       
class SimpleColumn(SimpleRecursive):
   """a simple column name for application to a list of tuples"""
   contains_aggregate = 0
   def __init__(self, name):
       self.name = name
   def relbind(self, dict, db):
       # already bound!
       return self
   def orderbind(self, whatever):
       # already bound!
       return self
   def initargs(self):
       return (self.name,)
   def value(self, simpletuples):
       from types import IntType
       tt = type
       name = self.name
       result = list(simpletuples)
       for i in xrange(len(result)):
           ri = result[i]
           if tt(ri) is not IntType:
              result[i] = ri[name]
           else:
              result[i] = None # ???
       return result
   def __repr__(self):
       return "<SimpleColumn %s>" % (self.name,)
       
class NumberedColumn(BoundMinus):
   """order by column number"""
   contains_aggregate = 0
   def __init__(self, num):
       self.thing = num
   def __repr__(self):
       return "<NumberedColumn %s>" % (self.thing,)
   def relbind(self, dict, db):
       from types import IntType
       if type(self.thing)!=IntType:
          raise ValueError, `self.thing`+": not a numbered column"
       return self
   def orderbind(self, order):
       return SimpleColumn( order[self.thing-1][0] )
       
class OrderExpr(BoundMinus):
   """order by expression."""
   def orderbind(self, order):
       expratt = self.thing.attribute()
       for (att, exp) in order:
           if exp.attribute()==expratt:
              return SimpleColumn(att)
       else:
           raise NameError, `self`+": invalid ordering specification"
   def __repr__(self):
       return "<order expression %s>" % (self.thing,)
       
class descOb:

   """special wrapper only used for sorting in descending order
      should only be compared with other descOb instances.
      should only wrap items that cannot be easily "order inverted",
      (eg, strings).
   """
      
   def __init__(self, ob):
       self.ob = ob
       
   def __cmp__(self, other):
       #test = cmp(self.__class__, other.__class__)
       #if test: return test
       return -cmp(self.ob,other.ob)
       
   def __coerce__(self, other):
       return (self, other)
       
   def __hash__(self):
       return hash(self.ob)
       
   def __repr__(self):
       return "descOb(%s)" % (self.ob,)
       
def PositionedSort(num, ord):
    nc = NumberedColumn(num)
    if ord=="DESC":
       return DescExpr(nc)
    return nc
    
def NamedSort(name, ord):
    oe = OrderExpr(name)
    if ord=="DESC":
       return DescExpr(oe)
    return oe
    
def relbind_sequence(order_list, dict, db):
    result = list(order_list)
    for i in xrange(len(order_list)):
        result[i] = result[i].relbind(dict,db)
    return result
        
def orderbind_sequence(order_list, order):
    result = list(order_list)
    for i in xrange(len(order_list)):
        result[i] = result[i].orderbind(order)
    return result
    
def order_tuples(order_list, tuples):
    lorder_list = len(order_list)
    ltuples = len(tuples)
    if lorder_list<1:
       raise ValueError, "order on empty list?"
    order_map = list(order_list)
    for i in xrange(lorder_list):
        order_map[i] = order_list[i].value(tuples)
    if len(order_map)>1:
       order_vector = apply(map, (None,)+tuple(order_map) )
    else:
       order_vector = order_map[0]
    #G = kjbuckets.kjGraph()
    pairs = map(None, range(ltuples), tuples)
    ppairs = map(None, order_vector, pairs)
    G = kjbuckets.kjGraph(ppairs)
    #for i in xrange(ltuples):
    #    G[ order_vector[i] ] = (i, tuples[i])
    Gkeys = G.keys()
    Gkeys.sort()
    result = list(tuples)
    index = 0
    for x in Gkeys:
        #print x
        for (i, y) in G.neighbors(x):
            #print "   ", y
            result[index]=y
            index = index+1
    if index!=ltuples:
       raise ValueError, \
        "TUPLE LOST IN ORDERING COMPUTATION! (%s,%s)" % (ltuples, index)
    return result
   
class BoundAddition(BoundExpression):
   """promised addition."""
   op = "+"
   def value(self, contexts):
       from types import IntType
       tt = type
       lvs = self.left.value(contexts)
       rvs = self.right.value(contexts)
       for i in xrange(len(contexts)):
           if tt(contexts[i]) is not IntType:
              lvs[i] = lvs[i] + rvs[i]
       return lvs
   
class BoundSubtraction(BoundExpression):
   """promised subtraction."""
   op = "-"
   def value(self, contexts):
       from types import IntType
       tt = type
       lvs = self.left.value(contexts)
       rvs = self.right.value(contexts)
       for i in xrange(len(contexts)):
           if tt(contexts[i]) is not IntType:
              lvs[i] = lvs[i] - rvs[i]
       return lvs
   
class BoundMultiplication(BoundExpression):
   """promised multiplication."""
   op = "*"
   def value(self, contexts):
       from types import IntType
       tt = type
       lvs = self.left.value(contexts)
       rvs = self.right.value(contexts)
       #print lvs
       for i in xrange(len(contexts)):
           if tt(contexts[i]) is not IntType:
              lvs[i] = lvs[i] * rvs[i]
       return lvs
   
class BoundDivision(BoundExpression):
   """promised division."""
   op = "/"
   def value(self, contexts):
       from types import IntType
       tt = type
       lvs = self.left.value(contexts)
       rvs = self.right.value(contexts)
       for i in xrange(len(contexts)):
           if tt(contexts[i]) is not IntType:
              lvs[i] = lvs[i] / rvs[i]
       return lvs
       
class BoundAttribute(BoundExpression):
   """bound attribute: initialize with relname=None if
      implicit."""
      
   contains_aggregate = 0
      
   def __init__(self, rel, name):
       self.rel = rel
       self.name = name
       
   def initargs(self):
       return (self.rel, self.name)
       
   def relbind(self, dict, db):
       if self.rel is not None: return self
       name = self.name
       try:
           rel = dict[name]
       except KeyError:
           raise NameError, `name` + ": unknown or ambiguous"
       return BoundAttribute(rel, name)
       
   def uncache(self):
       pass
       
   def __repr__(self):
       return "%s.%s" % (self.rel, self.name)
       
   def attribute(self):
       """return (rename, attribute) for self."""
       return (self.rel, self.name)
       
   def domain(self):
       return kjbuckets.kjSet([ (self.rel, self.name) ])
       
   def value(self, contexts):
       """return value of self in context (bound tuple)."""
       #print "value of ", self, "in", contexts
       from types import IntType
       tt = type
       result = list(contexts)
       ra = (self.rel, self.name)
       for i in xrange(len(result)):
           if tt(result[i]) is not IntType:
              result[i] = contexts[i][ra]
       return result
       
   def equate(self, other):
       oc = other.__class__
       if oc==BoundAttribute:
          result = BoundTuple()
          result.equate([(self.attribute(), other.attribute())])
          return BTPredicate(result)
       elif oc==Constant:
          result = BoundTuple()
          result.assns[ self.attribute() ] = other.value([1])[0]
          return BTPredicate(result)
       else:
          return NontrivialEqPred(self, other)
          
class Constant(BoundExpression):
   contains_aggregate = 0
   
   def __init__(self, value):
       self.value0 = value
       
   def __hash__(self):
       return hash(self.value0)
       
   def initargs(self):
       return (self.value0,)
       
   def domain(self):
       return kjbuckets.kjSet()
       
   def __add__(self, other):
       if other.__class__==Constant:
          return Constant(self.value0 + other.value0)
       return BoundAddition(self, other)
       
   def __sub__(self, other):
       if other.__class__==Constant:
          return Constant(self.value0 - other.value0)
       return BoundSubtraction(self, other)
       
   def __mul__(self, other):
       if other.__class__==Constant:
          return Constant(self.value0 * other.value0)
       return BoundMultiplication(self, other)
       
   def __neg__(self):
       return Constant(-self.value0)
       
   def __div__(self, other):
       if other.__class__==Constant:
          return Constant(self.value0 / other.value0)
       return BoundDivision(self, other)

   def relbind(self, dict, db):
       return self
       
   def uncache(self):
       pass
       
   def value(self, contexts):
       """return the constant value associated with self."""
       return [self.value0] * len(contexts)
       
   def equate(self,other):
       if other.__class__==Constant:
          if other.value0 == self.value0:
             return BTPredicate() #true
          else:
             return ~BTPredicate() #false
       else:
          return other.equate(self)
          
   def attribute(self):
       """invent a pair to identify a constant"""
       return ('unbound', `self`)
       
   def __repr__(self):
       return "<const %s at %s>" % (`self.value0`, id(self))
          
class TupleCollector:
   """Translate a sequence of assignments to simple tuples.
      (for implementing the select list of a SELECT).
   """
   contains_aggregate = 0
   contains_nonaggregate = 0
   
   def __init__(self):
       self.final = None
       self.order = []
       self.attorder = []
       self.exporder = []
       
   def initargs(self):
       return ()
       
   def marshaldata(self):
       exps = map(serialize, self.exporder)
       return (self.attorder, exps, 
               self.contains_aggregate, self.contains_nonaggregate)
       
   def demarshal(self, args):
       (self.attorder, exps, self.contains_aggregate,
        self.contains_nonaggregate) = args
       exporder = self.exporder = map(deserialize, exps)
       self.order = map(None, self.attorder, exporder)
       
   def uncache(self):
       for exp in self.exporder:
           exp.uncache()
       
   def domain(self):
       all=[]
       for e in self.exporder:
           all = all+e.domain().items()
       return kjbuckets.kjSet(all)
       
   def __repr__(self):
       l = []
       for (att, exp) in self.order:
           l.append( "%s as %s" % (exp, att) )
       from string import join
       return join(l, ", ")
       
   def addbinding(self, attribute, expression):
       """bind att>expression."""
       self.order.append((attribute, expression) )
       self.attorder.append(attribute )
       self.exporder.append(expression)
       if expression.contains_aggregate:
          self.contains_aggregate = 1
       else:
          self.contains_nonaggregate = 1
       
   def map(self, assnlist):
       """remap btlist by self. return (tuplelist, attorder)"""
       # DON'T eliminate nulls
       from types import IntType
       tt = type
       values = []
       for exp in self.exporder:
           values.append(exp.value(assnlist))
       if len(values)>1:
          valtups = apply(map, (None,) + tuple(values) )
       else:
          valtups = values[0]
       kjUndump = kjbuckets.kjUndump
       undumper = tuple(self.attorder)
       for i in xrange(len(valtups)):
           test = assnlist[i]
           if tt(test) is IntType or test is None:
              valtups[i] = 0 # null/false
           else:
              tup = valtups[i]
              valtups[i] = kjUndump(undumper, tup)
       return (valtups, self.attorder)
       
   def relbind(self, dict, db):
       """disambiguate missing rel names if possible.
          also choose output names appropriately."""
       # CURRENTLY THIS IS AN "IN PLACE" OPERATION
       order = self.order
       attorder = self.attorder
       exporder = self.exporder
       known = {}
       for i in xrange(len(order)):
           (att, exp) = order[i]
           #print exp
           exp = exp.relbind(dict, db)
           if att is None:
              # choose a name for this column
              #print exp
              (rname, aname) = exp.attribute()
              if known.has_key(aname):
                 both = rname+"."+aname
                 att = both
                 count = 0
                 while known.has_key(att):
                    # crank away!
                    count = count+1
                    att = both+"."+`count`
              else:
                 att = aname
           else:
              if known.has_key(att):
                 raise NameError, `att`+" ambiguous in select list"
           order[i] = (att, exp)
           exporder[i] = exp
           attorder[i] = att
           known[att] = att
       return self

class BTPredicate(SimpleRecursive):
   """superclass for bound tuple predicates.
      Eventually should be modified to use "compile" for speed
      to generate an "inlined" evaluation function.
      self(bt) returns bt with additional equality constraints
      (possible) or None if predicate fails."""
      
   false = 0
   constraints = None
   contains_aggregate = 0
      
   def __init__(self, constraints=None):
       """default interpretation: True."""
       if constraints is not None:
          self.constraints = constraints.close()
          
   def initargs(self):
       return (self.constraints,)
          
   def relbind(self, dict, db):
       c = self.constraints
       if c is None: return self
       return BTPredicate( self.constraints.relbind(dict, db) )
       
   def uncache(self):
       pass
          
   #def evaluate(self, db, relnames):
       #"""evaluate the predicate over database bindings."""
       # pretty simple strategy right now...
       ### need to do something about all/distinct...
       #c = self.constraints
       #if c is None:
       #  c = BoundTuple()
       #order = c.relorder(db, relnames)
       #if not order:
       #   raise ValueError, "attempt to evaluate over no relations: "+`relnames`
       #result = [c]
       #for r in order:
       #    result = hashjoin(result, r, db[r])
       #if self.__class__==BTPredicate:
       #   # if it's just equality conjunction, we're done
       #   return result
       #else:
       #   # apply additional constraints
       #   return self(result)
          
   def domain(self):
       c = self.constraints
       kjSet = kjbuckets.kjSet
       if c is None: return kjSet()
       return c.domain()
       
   def __repr__(self):
       if self.false: return "FALSE"
       c = self.constraints
       if c is None: c = "true"
       return "[pred](%s)" % c
          
   def detrivialize(self):
       """hook added to allow elimination of trivialities
          return None if completely true, or simpler form
          or self, if no simplification is possible."""
       if self.false: return self
       if not self.constraints: return None
       return self
          
   def negated_constraints(self):
       """equality constraints always false of satisfactory tuple."""
       return BoundTuple() # there aren't any
       
   def __call__(self, assignments, toplevel=0):
       """apply self to sequence of assignments
          return copy of asssignments with false results
          replaced by 0!  Input may have 0's!"""
       # optimization
       #   if toplevel, the btpred has been evaluated during join.
       if toplevel:
          return list(assignments)
       from types import IntType
       tt = type
       lbt = len(assignments)
       if self.false: return [0] * lbt
       c = self.constraints
       if c is None or not c:
          result = assignments[:] # no constraints
       else:
          assns = c.assns
          eqs = c.eqs
          eqsinteresting = 0
          for (a,b) in eqs.items():
              if a!=b:
                 eqsinteresting = 1
          result = assignments[:]
          for i in xrange(lbt):
              this = assignments[i]
              #print "comparing", self, "to", this
              if type(this) is IntType: continue
              this = (this + assns).Clean()
              if this is None:
                 result[i] = 0
              elif eqsinteresting:
                 this = this.remap(eqs)
                 if this is None:
                    result[i] = 0
       return result
          
   def __and__(self, other):
       """NOTE: all subclasses must define an __and__!!!"""
       #print "BTPredicate.__and__", (self, other)
       if self.__class__==BTPredicate and other.__class__==BTPredicate:
          c = self.constraints
          o = other.constraints
          if c is None: return other
          if o is None: return self
          if self.false: return self
          if other.false: return other
          # optimization for simple constraints
          all = (c+o)
          result = BTPredicate( all ) # all constraints
          if all is None: result.false = 1
       else:
          result = other & self
       return result
       
   def __or__(self, other):
       if self.__class__==BTPredicate and other.__class__==BTPredicate:
          c = self.constraints
          o = other.constraints
          if c is None: return self # true dominates
          if o is None: return other
          if other.false: return self
          if self.false: return other
          if self == other: return self
       result = BTor_pred([self, other])
       return result
       
   def __invert__(self):
       if self.false:
          return BTPredicate()
       if not self.constraints:
          result = BTPredicate()
          result.false = 1
          return result
       return BTnot_pred(self)
       
   def __cmp__(self, other):
       test = cmp(other.__class__, self.__class__)
       if test: return test
       if self.false and other.false: return 0
       return cmp(self.constraints, other.constraints)
       
   def __hash__(self):
       if self.false: return 11111
       return hash(self.constraints)
       
class BTor_pred(BTPredicate):

   def __init__(self, members, *othermembers):
       # replace any OR in members with its members
       #print "BTor_pred", members
       members = list(members) + list(othermembers)
       for m in members[:]:
           if m.__class__==BTor_pred:
              members.remove(m)
              members = members + m.members
       #print "before", members
       members = self.members = kjbuckets.kjSet(members).items()
       #print members
       for m in members[:]:
           if m.false: members.remove(m)
       self.constraints = None # common constraints
       for m in members:
          if m.contains_aggregate:
             self.contains_aggregate = 1
       if members:
          # common constraints are those in all members
          constraints = members[0].constraints
          for m in members[1:]:
              mc = m.constraints
              if not constraints or not mc:
                 constraints = None
                 break
              constraints = constraints & mc
          self.constraints = constraints
       #print members
       
   def initargs(self):
       return ((),) + tuple(self.members)
          
   def relbind(self, dict, db):
       ms = []
       for m in self.members:
           ms.append( m.relbind(dict, db) )
       return BTor_pred(ms)
       
   def uncache(self):
       for m in self.members:
           m.uncache()
          
   def domain(self):
       all = BTPredicate.domain(self).items()
       for x in self.members:
           all = all + x.domain().items()
       return kjbuckets.kjSet(all)
       
   def __repr__(self):
       c = self.constraints
       m = self.members
       mr = map(repr, m)
       from string import join
       mr.sort()
       mr = join(mr, " | ")
       if not mr: mr = "FALSE_OR"
       if c:
          mr = "[disj](%s and %s)" % (c, mr)
       return mr

   def detrivialize(self):
       """hook added to allow elimination of trivialities
          return None if completely true, or simpler form
          or self, if no simplification is possible."""
       ms = self.members
       for i in xrange(len(ms)):
           ms[i] = ms[i].detrivialize()
       # now suck out subordinate ors
       someor = None
       for m in ms:
           if m.__class__== BTor_pred:
              someor = m
              ms.remove(m)
              break
       if someor is not None:
           result = someor
           for m in ms:
               result = result + m
           return result.detrivialize()
       allfalse = 1
       for m in ms:
           if m is None: allfalse=0; break # true member
           allfalse = allfalse & m.false
       if allfalse: return ~BTPredicate() # boundary case
       ms[:] = filter(None, ms)
       if not ms: return None # all true.
       ms[:] = kjbuckets.kjSet(ms).items()
       if len(ms)==1: return ms[0] # or of 1
       return self           

   def __call__(self, boundtuples, toplevel=0):
       # apply common constraints first
       lbt = len(boundtuples)
       # boundary case for or is false
       members = self.members
       if not members:
          return [0] * lbt
       current = BTPredicate.__call__(self, boundtuples, toplevel)
       # now apply first alternative
       alt1 = members[0](current)
       # determine questionables
       questionables = current[:]
       rng = xrange(len(current))
       from types import IntType
       tt = type
       for i in rng:
           if tt(alt1[i]) is not IntType:
              questionables[i]=0
       # now test other alternatives
       #print "alt1", members[0]
       #for x in alt1: 
           #print x
       for m in self.members[1:]:
           #print "questionables", m
           #for x in questionables:
               #print x
           passm = m(questionables)
           for i in rng:
               test = passm[i]
               if tt(test) is not IntType:
                  questionables[i] = 0
                  alt1[i] = test
       return alt1

   def negated_constraints(self):
       """the negated constraints of an OR are
          the negated constraints of *all* members"""
       ms = self.members
       result = ms.negated_constraints()
       for m in ms[1:]:
           if not result: return result
           mc = m.negated_constraints()
           if not mc: return mc
           result = result & mc
       return result
       
   def __and__(self, other):
       """push "and" down"""
       newmembers = self.members[:]
       for i in xrange(len(newmembers)):
           newmembers[i] = newmembers[i] & other
       return BTor_pred(newmembers)
       
   def __or__(self, other):
       """collapse two ors, otherwise just add new member"""
       if self.__class__==BTor_pred and other.__class__==BTor_pred:
          return BTor_pred(self.members+other.members)
       return BTor_pred(self.members + [other])
       
   def __invert__(self):
       """translate to and-not"""
       ms = self.members
       if not ms: return BTPredicate() # boundary case
       result = ~ms[0]
       for m in ms[1:]:
           result = result & ~m
       return result
       
   def __cmp__(self, other):
       test = cmp(self.__class__, other.__class__)
       if test: return test
       kjSet = kjbuckets.kjSet
       test = cmp(kjSet(self.members), kjSet(other.members))
       if test: return test
       return BTPredicate.__cmp__(self, other)
       
   def __hash__(self):
       return hash(kjbuckets.kjSet(self.members))
       
class BTnot_pred(BTPredicate):

   def __init__(self, thing):
       self.negated = thing
       self.contains_aggregate = thing.contains_aggregate
       self.constraints = thing.negated_constraints()
       
   def initargs(self):
       return (self.negated,)
       
   def relbind(self, dict, db):
       return BTnot_pred( self.negated.relbind(dict, db) )
       
   def uncache(self):
       self.negated.uncache()
       
   def domain(self):
       result = BTPredicate.domain(self) + self.negated.domain()
       #print "neg domain is", `self`, result
       return result
       
   def __repr__(self):
       c = self.constraints
       n = self.negated
       r = "(NOT %s)" % n
       if c: r = "[neg](%s & %s)" % (c, r)
       return r

   def detrivialize(self):
       """hook added to allow elimination of trivialities
          return None if completely true, or simpler form
          or self, if no simplification is possible."""
       # first, fix or/and/not precedence
       thing = self.negated
       if thing.__class__ == BTnot_pred:
          return thing.negated.detrivialize()
       if thing.__class__ == BTor_pred:
          # translate to and_not
          members = thing.members[:]
          for i in xrange(len(members)):
              members[i] = ~members[i]
          result = BTand_pred(members)
          return result.detrivialize()
       if thing.__class__ == BTand_pred:
          # translate to or_not
          members = thing.members[:]
          c = thing.constraints # precondition
          if c is not None:
             members.append(BTPredicate(c))
          for i in xrange(len(members)):
              members[i] = ~members[i]
          result = BTor_pred(members)
          return result.detrivialize()
       self.negated = thing = self.negated.detrivialize()
       if thing is None: return ~BTPredicate() # uniquely false
       if thing.false: return None # uniquely true
       return self

   def __call__(self, boundtuples, toplevel=0):
       from types import IntType
       tt = type
       current = BTPredicate.__call__(self, boundtuples, toplevel)
       omit = self.negated(current)
       for i in xrange(len(current)):
           if tt(omit[i]) is not IntType:
              current[i]=0
       return current

   def negated_constraints(self):
       """the negated constraints of a NOT are the
          negated constraints of the thing negated."""
       return self.negated.constraints
       
   def __and__(self, other):
       """do the obvious thing."""
       return BTand_pred([self, other])
       
   def __or__(self, other):
       """do the obvious thing"""
       return BTor_pred([self, other])
       
   def __invert__(self):
       return self.negated
       
   def __cmp__(self, other):
       test = cmp(self.__class__, other.__class__)
       if test: return test
       test = cmp(self.negated,other.negated)
       if test: return test
       return BTPredicate.__cmp__(self,other)
       
   def __hash__(self):
       return hash(self.negated)^787876^hash(self.constraints)
       
class BTand_pred(BTPredicate):

   def __init__(self, members, precondition=None, *othermembers):
       #print "BTand_pred", (members, precondition)
       members = list(members) + list(othermembers)
       members = self.members = kjbuckets.kjSet(members).items()
       self.constraints = precondition # common constraints
       if members:
          # common constraints are those in any member
          if precondition is not None:
             constraints = precondition
          else:
             constraints = BoundTuple()
          for i in xrange(len(members)):
              m = members[i]
              mc = m.constraints
              if mc:
                 #print "constraints", constraints
                 constraints = constraints + mc
                 if constraints is None: break
              if m.__class__==BTPredicate:
                 members[i] = None # subsumed above
          members = self.members = filter(None, members)
          for m in members:
              if m.contains_aggregate:
                 self.contains_aggregate=1
          ### consider propagating constraints down?
          self.constraints = constraints
          if constraints is None: self.false = 1
          
   def initargs(self):
       #print "self.members", self.members
       #print "self.constraints", self.constraints
       #return (list(self.members), self.constraints)
       return ((), self.constraints) + tuple(self.members)
          
   def relbind(self, dict, db):
       ms = []
       for m in self.members:
           ms.append( m.relbind(dict, db) )
       c = self.constraints.relbind(dict, db)
       return BTand_pred(ms, c)
       
   def uncache(self):
       for m in self.members:
           m.uncache()
          
   def domain(self):
       all = BTPredicate.domain(self).items()
       for x in self.members:
           all = all + x.domain().items()
       return kjbuckets.kjSet(all)
       
   def __repr__(self):
       m = self.members
       c = self.constraints
       r = map(repr, m)
       if self.false: r.insert(0, "FALSE")
       from string import join
       r = join(r, " AND ")
       r = "(%s)" % r
       if c: r = "[conj](%s and %s)" % (c, r)
       return r

   def detrivialize(self):
       """hook added to allow elimination of trivialities
          return None if completely true, or simpler form
          or self, if no simplification is possible."""
       # first apply demorgan's law to push ands down
       # (exponential in worst case).
       #print "detrivialize"
       #print self
       ms = self.members
       some_or = None
       c = self.constraints
       for m in ms:
           if m.__class__==BTor_pred:
              some_or = m
              ms.remove(m)
              break
       if some_or is not None:
          result = some_or
          if c is not None:
             some_or = some_or & BTPredicate(c)
          for m in ms:
              result = result & m # preserves or/and precedence
          if result.__class__!=BTor_pred:
             raise "what the?"
          result = result.detrivialize()
          #print "or detected, returning"
          #print result
          return result
       for i in xrange(len(ms)):
           ms[i] = ms[i].detrivialize()
       ms[:] = filter(None, ms)
       if not ms:
          #print "returning boundary case of condition"
          if c is None:
             return None
          else: 
             return BTPredicate(c).detrivialize()
       ms[:] = kjbuckets.kjSet(ms).items()
       if len(ms)==1 and c is None: 
          #print "and of 1, returning"
          #print ms[0]
          return ms[0] # and of 1
       return self           

   def __call__(self, boundtuples, toplevel=0):
       # apply common constraints first
       current = BTPredicate.__call__(self, boundtuples, toplevel)
       for m in self.members:
           current = m(current)
       return current

   def negated_constraints(self):
       """the negated constraints of an AND are
          the negated constraints of *any* member"""
       ms = self.members
       result = BoundTuple()
       for m in ms:
           mc = m.negated_constraints()
           if mc: result = result + mc 
       return result
       
   def __and__(self, other):
       """push "and" down if other is an or"""
       if other.__class__==BTor_pred:
          return other & self
       c = self.constraints
       # merge in other and
       if other.__class__==BTand_pred:
          allmem = self.members+other.members
          oc = other.constraints
          if c is None:
             c = oc
          elif oc is not None:
             c = c+oc
          return BTand_pred(allmem, c)
       return BTand_pred(self.members + [other], c)
       
   def __or__(self, other):
       """do the obvious thing."""
       return BTor_pred([self, other])
       
   def __invert__(self):
       """translate to or-not"""
       ms = self.members
       if not ms: return ~BTPredicate() # boundary case
       result = ~ms[0]
       for m in ms[1:]:
           result = result | ~m
       return result
       
   def __cmp__(self, other):
       test = cmp(self.__class__, other.__class__)
       if test: return test
       kjSet = kjbuckets.kjSet
       test = cmp(kjSet(self.members), kjSet(other.members))
       if test: return test
       return BTPredicate.__cmp__(self, other)
       
   def __hash__(self):
       return hash(kjbuckets.kjSet(self.members))
       
class NontrivialEqPred(BTPredicate):
   """equation of nontrivial expressions."""
   
   def __init__(self, left, right):
       #print "making pred", self.__class__, left, right
       # maybe should used reflexivity...
       self.left = left
       self.right = right
       self.contains_aggregate = left.contains_aggregate or right.contains_aggregate
       
   def initargs(self):
       return (self.left, self.right)
       
   def __cmp__(self, other):
       test = cmp(self.__class__, other.__class__)
       if test: return test
       test = cmp(self.right, other.right)
       if test: return test
       return cmp(other.left, other.left)
       
   def hash(self, other):
       return hash(self.left) ^ hash(self.right)
       
   def relbind(self, dict, db):
       Class = self.__class__
       return Class(self.left.relbind(dict,db), self.right.relbind(dict,db) )
       
   def uncache(self):
       self.left.uncache()
       self.right.uncache()
       
   def domain(self):
       return self.left.domain() + self.right.domain()
       
   op = "=="
       
   def __repr__(self):
       return "(%s)%s(%s)" % (self.left, self.op, self.right)
       
   def detrivialize(self):
       return self
       
   def __call__(self, assigns, toplevel=0):
       from types import IntType
       tt = type
       lv = self.left.value(assigns)
       rv = self.right.value(assigns)
       result = assigns[:]
       for i in xrange(len(assigns)):
           t = assigns[i]
           if type(t) is not IntType and lv[i]!=rv[i]:
              result[i] = 0
       return result
       
   def negated_constraints(self):
       return None
       
   def __and__(self, other):
       return BTand_pred( [self, other] )
       
   def __or__(self, other):
       return BTor_pred( [self, other] )
       
   def __invert__(self):
       return BTnot_pred(self)
       
class BetweenPredicate(NontrivialEqPred):
   """e1 BETWEEN e2 AND e3"""
   def __init__(self, middle, lower, upper):
       self.middle = middle
       self.lower = lower
       self.upper = upper
       
   def initargs(self):
       return (self.middle, self.lower, self.upper)
       
   def domain(self):
       return (
   self.middle.domain() + self.lower.domain() + self.upper.domain())
        
   def relbind(self, dict, db):
       self.middle = self.middle.relbind(dict, db)
       self.lower = self.lower.relbind(dict, db)
       self.upper = self.upper.relbind(dict, db)
       return self
       
   def uncache(self):
       self.middle.uncache()
       self.upper.uncache()
       self.lower.uncache()
       
   def __repr__(self):
       return "(%s BETWEEN %s AND %s)" % (
        self.middle, self.lower, self.upper)
        
   def __hash__(self):
       return hash(self.middle)^~hash(self.lower)^hash(self.upper)^55
       
   def __cmp__(self, other):
       test = cmp(self.__class__, other.__class__)
       if test: return test
       test = cmp(self.lower, other.lower)
       if test: return test
       test = cmp(self.middle, other.middle)
       if test: return test
       return cmp(self.upper, other.upper)
       
   def __call__(self, assigns, toplevel=0):
       from types import IntType
       tt = type
       lowv = self.lower.value(assigns)
       upv = self.upper.value(assigns)
       midv = self.middle.value(assigns)
       result = assigns[:]
       for i in xrange(len(assigns)):
           t = assigns[i]
           if tt(t) is not IntType:
              midvi = midv[i]
              if lowv[i]>midvi or upv[i]<midvi:
                 result[i] = 0
       return result
       
class ExistsPred(NontrivialEqPred):
   """EXISTS subquery."""
   contains_aggregate = 0
   
   def __init__(self, subq):
       self.cached_result = None
       self.cachable = None
       self.subq = subq
       
   def initargs(self):
       return (self.subq,)
       
   def domain(self):
       result = self.subq.unbound()
       # if there are no outer bindings, evaluate ONCE!
       if not result:
          self.cachable = 1
       return result
       
   def relbind(self, dict, db):
       self.subq = self.subq.relbind(db, dict)
       return self
       
   def uncache(self):
       self.cached_result = None
       self.subq.uncache()
       
   def __repr__(self):
       return "\nEXISTS\n%s\n" % (self.subq,)
       
   def __call__(self, assigns, toplevel=0):
       ### should optimize!!!
       #print "exists"
       #print self.subq
       from types import IntType
       tt = type
       eval = self.subq.eval
       result = assigns[:]
       # shortcut: if cachable, eval only once and cache
       if self.cachable:
           test = self.cached_result
           if test is None:
              self.cached_result = test = eval()
           #print "exists cached", self.cached_result
           if test:
              return result
           else:
              return [0] * len(result)
       kjDict = kjbuckets.kjDict
       for i in xrange(len(assigns)):
           #print "exists uncached"
           assignsi = assigns[i]
           if tt(assignsi) is IntType: continue
           testbtup = BoundTuple()
           testbtup.assns = kjDict(assignsi)
           test = eval(outerboundtuple=testbtup).rows()
           #for x in test:
               #print "exists for", assignsi
               #print x
               #break
           if not test:
                 result[i] = 0
       return result
       
   def __hash__(self):
       return hash(self.subq)^3333
       
   def __cmp__(self, other):
       test = cmp(self.__class__, other.__class__)
       if test: return test
       return cmp(self.subq, other.subq)
       
class QuantEQ(NontrivialEqPred):
   """Quantified equal any predicate"""
   
   def __init__(self, expr, subq):
       self.expr = expr
       self.subq = subq
       self.cachable = 0
       self.cached_column = None
       self.att = None
       
   def initargs(self):
       return (self.expr, self.subq)
       
   def uncache(self):
       self.cached_column = None
       
   def domain(self):
       first = self.subq.unbound()
       if not first:
          self.cachable = 1
       more = self.expr.domain()
       return first + more
       
   def relbind(self, dict, db):
       subq = self.subq = self.subq.relbind(db, dict)
       self.expr = self.expr.relbind(dict, db)
       # test that subquery is single column and determine att
       sl = subq.select_list
       atts = sl.attorder
       if len(atts)<>1:
          raise ValueError, \
            "Quantified predicate requires unit select list: %s" % atts
       self.att = atts[0]
       return self
       
   fmt = "(%s %s ANY %s)"
   op = "="
       
   def __repr__(self):
       return self.fmt % (self.expr, self.op, self.subq)
       
   def __call__(self, assigns, toplevel=0):
       cached_column = self.cached_column
       cachable = self.cachable
       expr = self.expr
       subq = self.subq
       att = self.att
       if cachable:
           if cached_column is None:
               subqr = subq.eval().rows()
               cc = self.cached_column = dump_single_column(subqr, att)
           #print self, "cached", self.cached_column
       exprvals = expr.value(assigns)
       kjDict = kjbuckets.kjDict
       compare = self.compare
       tt = type
       from types import IntType
       result = assigns[:]
       for i in xrange(len(assigns)):
           assignsi = assigns[i]
           if tt(assignsi) is IntType: continue
           thisval = exprvals[i]
           testbtup = BoundTuple()
           testbtup.assns = kjDict(assignsi)
           if not cachable:
               subqr = subq.eval(outerboundtuple=testbtup).rows()
               cc = dump_single_column(subqr, att)
               #print self, "uncached", cc, thisval
           if not compare(thisval, cc):
               #print "eliminated", assignsi
               result[i] = 0
       return result
       
   def compare(self, value, column):
       return value in column
       
   def __hash__(self):
       return hash(self.subq) ^ ~hash(self.expr)
       
   def __cmp__(self, other):
       test = cmp(self.__class__, other.__class__)
       if test: return test
       test = cmp(self.expr, other.expr)
       if test: return test
       return cmp(self.subq, other.subq)
       
# "expr IN (subq)" same as "expr = ANY (subq)"
InPredicate = QuantEQ

class InLits(NontrivialEqPred):
   """expr IN literals, support dynamic bindings."""   
   def __init__(self, expr, lits):
       self.expr = expr
       self.lits = lits
       self.cached_lits = None
       
   def initargs(self):
       return (self.expr, self.lits)
       
   def uncache(self):
       self.cached_lits = None
       
   def domain(self):
       d = []
       for l in self.lits:
           d0 = l.domain()
           if d0:
               d = d + d0.items()
       d0 = self.expr.domain()
       if d:
          kjSet = kjbuckets.kjSet
          return d0 + kjSet(d)
       else:
          return d0
       
   def relbind(self, dict, db):
       newlits = []
       for l in self.lits:
           newlits.append(l.relbind(dict, db))
       self.lits = newlits
       self.expr = self.expr.relbind(dict, db)
       return self
       
   fmt = "(%s IN %s)"
       
   def __repr__(self):
       return self.fmt % (self.expr, self.lits)
       
   def __call__(self, assigns, toplevel=0):
       # LITERALS ARE CONSTANT! NEED ONLY LOOK FOR ONE ASSIGN.
       tt = type
       from types import IntType
       litvals = self.cached_lits
       if litvals is None:
          assigns0 = []
          for asn in assigns:
              if tt(asn) is not IntType:
                 assigns0.append(asn)
                 break
          if not assigns0:
             # all false/unknown
             return assigns
          litvals = []
          for lit in self.lits:
              value = lit.value(assigns0)
              litvals.append(value[0])
          self.cached_lits = litvals
       expr = self.expr
       exprvals = expr.value(assigns)
       result = assigns[:]
       for i in xrange(len(assigns)):
           assignsi = assigns[i]
           if tt(assignsi) is IntType: continue
           thisval = exprvals[i]
           if thisval not in litvals:
               #print "eliminated", assignsi
               result[i] = 0
       return result
       
   def compare(self, value, column):
       return value in column
       
   def __hash__(self):
       return 10 ^ hash(self.expr)
       
   def __cmp__(self, other):
       test = cmp(self.__class__, other.__class__)
       if test: return test
       test = cmp(self.expr, other.expr)
       if test: return test
       return cmp(self.lits, other.lits)

class QuantNE(QuantEQ):
   """Quantified not equal any predicate"""
   op = "<>"
   def compare(self, value, column):
       for x in column:
           if value!=x: return 1
       return 0
       
### note: faster NOT IN using QuantNE?

class QuantLT(QuantEQ):
   """Quantified less than any predicate"""
   op = "<"
   def uncache(self):
       self.testval = self.cached = self.cached_column = None
   def compare(self, value, column):
       if self.cachable:
           if self.cached:
               testval = self.testval
           else:
               testval = self.testval = max(column)
               self.cached = 1
       else:
           testval = max(column)
       return value < testval

class QuantLE(QuantLT):
   """Quantified less equal any predicate"""
   op = "<="
   def compare(self, value, column):
       if self.cachable:
           if self.cached:
               testval = self.testval
           else:
               testval = self.testval = max(column)
               self.cached = 1
       else:
           testval = max(column)
       return value <= testval

class QuantGE(QuantLT):
   """Quantified greater equal any predicate"""
   op = ">="
   def compare(self, value, column):
       if self.cachable:
           if self.cached:
               testval = self.testval
           else:
               testval = self.testval = min(column)
               self.cached = 1
       else:
           testval = min(column)
       return value >= testval
       
class QuantGT(QuantLT):
   """Quantified greater than any predicate"""
   op = ">"
   def compare(self, value, column):
       if self.cachable:
           if self.cached:
               testval = self.testval
           else:
               self.testval = testval = min(column)
               self.cached = 1
       else:
           testval = min(column)
       return value > testval
       
def dump_single_column(assigns, att):
    """dump single column assignment"""
    result = assigns[:]
    for i in xrange(len(result)):
        result[i] = result[i][att]
    return result

class LessPred(NontrivialEqPred):
   op = "<"
   def __call__(self, assigns, toplevel=0):
       from types import IntType
       tt = type
       lv = self.left.value(assigns)
       rv = self.right.value(assigns)
       result = assigns[:]
       for i in xrange(len(assigns)):
           t = assigns[i]
           if tt(t) is not IntType and lv[i]>=rv[i]:
              result[i] = 0
       return result
       
   def __inv__(self):
       return LessEqPred(self.right, self.left)
       
   def __hash__(self):
       return hash(self.left)^hash(self.right)

       
class LessEqPred(LessPred):
   op = "<="
   def __call__(self, assigns, toplevel=0):
       from types import IntType
       tt = type
       lv = self.left.value(assigns)
       rv = self.right.value(assigns)
       result = assigns[:]
       for i in xrange(len(assigns)):
           t = assigns[i]
           if tt(t) is not IntType and lv[i]>rv[i]:
              result[i] = 0
       return result
       
   def __inv__(self):
       return LessPred(self.right, self.left)
       
class SubQueryExpression(BoundMinus, SimpleRecursive):
   """sub query expression (subq), must eval to single column, single value"""
   def __init__(self, subq):
       self.subq = subq
       self.att = self.cachable = self.cached = self.cached_value = None
       
   def initargs(self):
       return (self.subq,)
       
   def uncache(self):
       self.cached = self.cached_value = None

   def domain(self):
       result = self.subq.unbound()
       if not result:
           self.cachable = 1
       #print "expr subq domain", result
       return result
       
   def relbind(self, dict, db):
       subq = self.subq = self.subq.relbind(db, dict)
       # test that subquery is single column and determine att
       sl = subq.select_list
       atts = sl.attorder
       if len(atts)<>1:
          raise ValueError, \
            "Quantified predicate requires unit select list: %s" % atts
       self.att = atts[0]
       return self
       
   def __repr__(self):
       return "(%s)" % self.subq
       
   def value(self, contexts):
       subq = self.subq
       att = self.att
       if self.cachable:
           if self.cached:
               cached_value = self.cached_value
           else:
               self.cached = 1
               seval = subq.eval().rows()
               lse = len(seval)
               if lse<>1:
                   raise ValueError, \
          "const subquery expression must return 1 result: got %s" % lse
               self.cached_value = cached_value = seval[0][att]
           #print "const subq cached", cached_value
           return [cached_value] * len(contexts)
       from types import IntType
       tt = type
       result = contexts[:]
       kjDict = kjbuckets.kjDict
       for i in xrange(len(contexts)):
           contextsi = contexts[i]
           if tt(contextsi) is not IntType:
               testbtup = BoundTuple()
               testbtup.assns = kjDict(contextsi)
               #print "subq exp", testbtup
               seval = subq.eval(outerboundtuple=testbtup).rows()
               lse = len(seval)
               if lse<>1:
                   raise ValueError, \
          "dynamic subquery expression must return 1 result: got %s" % lse
               result[i] = seval[0][att]
               #print "nonconst subq uncached", result[i], contextsi
       return result

SELECT_TEMPLATE = """\
SELECT %s %s
FROM %s
WHERE %s
GROUP BY %s
HAVING %s %s
ORDER BY %s %s
"""

def dynamic_binding(ndynamic, dynamic):
    """create bindings from dynamic tuple for ndynamic parameters
       if a tuple is given create one
       if a list is given create many
    """
    from types import ListType, TupleType
    if not dynamic:
       if ndynamic>0:
             raise ValueError, `ndynamic`+" dynamic parameters unbound"
       return [kjbuckets.kjDict()]
    ldyn = len(dynamic)
    undumper = map(None, [0]*ndynamic, range(ndynamic))
    undumper = tuple(undumper)
    tdyn = type(dynamic)
    if tdyn is TupleType:
       ldyn = len(dynamic)
       if len(dynamic)!=ndynamic:
          raise ValueError, "%s,%s: wrong number of dynamics" % (ldyn,ndynamic)
       dynamic = [dynamic]
    elif tdyn is not ListType:
       raise TypeError, "dynamic parameters must be list or tuple"
    else:
       lens = map(len, dynamic)
       ndynamic = max(lens)
       if ndynamic!=min(lens):
          raise ValueError, "dynamic parameters of inconsistent lengths"
    undumper = map(None, [0]*ndynamic, range(ndynamic))
    undumper = tuple(undumper)
    result = list(dynamic)
    kjUndump = kjbuckets.kjUndump
    for i in xrange(len(dynamic)):
        dyn = dynamic[i]
        ldyn = len(dyn)
        #print undumper, dyn
        if ldyn==1:
           dynresult = kjUndump(undumper, dyn[0])
        else:
           dynresult = kjUndump(undumper, dyn)
        result[i] = dynresult
    return result

class Selector:
   """For implementing, eg the SQL SELECT statement."""
   def __init__(self, alldistinct,
                      select_list,
                      table_reference_list,
                      where_pred,
                      group_list,
                      having_cond,
                      union_select =None,
                      order_by_spec =None,
                      ndynamic=0, # number of dyn params expected
                      ):
       self.ndynamic = ndynamic
       self.alldistinct = alldistinct
       self.select_list = select_list
       self.table_list = table_reference_list
       self.where_pred = where_pred
       self.group_list = group_list
       self.having_cond = having_cond
       self.union_select = union_select
       self.order_by = order_by_spec
       #self.union_spec = "DISTINCT" # default union mode
       self.relbindings = None # binding of relations
       self.unbound_set = None # unbound attributes
       self.rel_atts = None # graph of alias>attname bound in self
       self.all_aggregate = 0
       if select_list!="*" and not group_list:
          if select_list.contains_aggregate:
             ### should restore this check somewhere else!
             #if select_list.contains_nonaggregate:
                #raise ValueError, "aggregates/nonaggregates don't mix without grouping"
             self.all_aggregate = 1
       if where_pred and where_pred.contains_aggregate:
          raise ValueError, "aggregate in WHERE"
       self.query_plan = None
          
   def initargs(self):
       #print self.alldistinct
       #print self.select_list
       #print self.table_list
       #print self.where_pred
       #print self.having_cond
       #print self.union_select
       #print self.group_list
       #print self.order_by
       #print self.ndynamic
       # note: order by requires special handling
       return (self.alldistinct, self.select_list, self.table_list, self.where_pred,
               None, self.having_cond, self.union_select, None,
               self.ndynamic)
               
   def marshaldata(self):
       order_by = self.order_by
       if order_by:
           order_by = map(serialize, order_by)
       group_list = self.group_list
       if group_list:
           group_list = map(serialize, group_list)
       #print "marshaldata"
       #print order_by
       #print group_list
       return (order_by, group_list)
       
   def demarshal(self, data):
       (order_by, group_list) = data
       if order_by:
          order_by = map(deserialize, order_by)
       if group_list:
          group_list = map(deserialize, group_list)
       #print "demarshal"
       #print order_by
       #print group_list
       self.order_by = order_by
       self.group_list = group_list
          
   def unbound(self):
       result = self.unbound_set
       if result is None:
          raise ValueError, "binding not available"
       return result
       
   def uncache(self):
       wp = self.where_pred
       hc = self.having_cond
       sl = self.select_list
       if wp is not None: wp.uncache()
       if hc is not None: hc.uncache()
       sl.uncache()
       qp = self.query_plan
       if qp:
          for joiner in qp:
              joiner.uncache()
       
   def relbind(self, db, outerbindings=None):
       ad = self.alldistinct
       sl = self.select_list
       tl = self.table_list
       wp = self.where_pred
       gl = self.group_list
       hc = self.having_cond
       us = self.union_select
       ob = self.order_by
       test = db.bindings(tl)
       #print len(test)
       #for x in test: 
            #print x
       (attbindings, relbindings, ambiguous, ambiguousatts) = test
       if outerbindings:
          # bind in outerbindings where unambiguous
          for (a,r) in outerbindings.items():
              if ((not attbindings.has_key(a))
                  and (not ambiguousatts.has_key(a)) ):
                 attbindings[a] = r
       # fix "*" select list
       if sl=="*":
          sl = TupleCollector()
          for (a,r) in attbindings.items():
              sl.addbinding(None, BoundAttribute(r,a))
          for (dotted, (r,a)) in ambiguous.items():
              sl.addbinding(dotted, BoundAttribute(r,a))
       sl = sl.relbind(attbindings, db)
       wp = wp.relbind(attbindings, db)
       if hc is not None: hc = hc.relbind(attbindings, db)
       if us is not None: us = us.relbind(db, attbindings)
       # bind grouping if present
       if gl:
          gl = relbind_sequence(gl, attbindings, db)
       # bind ordering list if present
       #print ob
       if ob:
          ob = relbind_sequence(ob, attbindings, db)
          ob = orderbind_sequence(ob, sl.order)
       result = Selector(ad, sl, tl, wp, gl, hc, us, ob)
       result.relbindings = relbindings
       result.ndynamic = self.ndynamic
       result.check_domains()
       result.plan_query()
       query_plan = result.query_plan
       for i in range(len(query_plan)):
           query_plan[i] = query_plan[i].relbind(db, attbindings)
       return result
       
   def plan_query(self):
       """generate a query plan (sequence of join operators)."""
       rel_atts = self.rel_atts # rel>attname
       where_pred = self.where_pred.detrivialize()
       #select_list = self.select_list
       # shortcut
       if where_pred is None:
          bt = BoundTuple()
       else:
          bt = self.where_pred.constraints
       if bt is None: 
          bt = BoundTuple()
       eqs = kjbuckets.kjGraph(bt.eqs)
       witness = kjbuckets.kjDict()
       # set all known and unbound atts as witnessed
       for att in bt.assns.keys():
           witness[att] = 1
       #print self, "self.unbound_set", self.unbound_set
       for att in self.unbound_set.items():
           witness[att] = 1
       relbindings = self.relbindings
       allrels = relbindings.keys()
       #print relbindings
       allrels = bt.relorder(relbindings, allrels)
       #print allrels
       rel_atts = self.rel_atts
       plan = []
       for rel in allrels:
           relation = relbindings[rel]
           ratts = rel_atts.neighbors(rel)
           h = HashJoiner(bt, rel, ratts, relation, witness)
           plan.append(h)
           for a in ratts:
               ra = (rel, a)
               witness[ra] = 1
               eqs[ra] = ra
           witness = witness.remap(eqs)
       self.query_plan = plan
       
   def check_domains(self):
       """determine set of unbound names in self.
       """
       relbindings = self.relbindings
       sl = self.select_list
       wp = self.where_pred
       gl = self.group_list
       hc = self.having_cond
       us = self.union_select
       all = sl.domain().items()
       if wp is not None:
          all = all + wp.domain().items()
       # ignore group_list ???
       if hc is not None:
          all = all + hc.domain().items()
       kjSet = kjbuckets.kjSet
       kjGraph = kjbuckets.kjGraph
       alldomain = kjSet(all)
       rel_atts = self.rel_atts = kjGraph(all)
       allnames = kjSet()
       #print "relbindings", relbindings.keys()
       for name in relbindings.keys():
           rel = relbindings[name]
           for att in rel.attributes():
               allnames[ (name, att) ] = 1
       # union compatibility check
       if us is not None:
          us.check_domains()
          myatts = self.attributes()
          thoseatts = us.attributes()
          if myatts!=thoseatts:
             if len(myatts)!=len(thoseatts):
                raise IndexError, "outer %s, inner %s: union select lists lengths differ"\
                  % (len(myatts), len(thoseatts))
          for p in map(None, myatts, thoseatts):
              (x,y)=p
              if x!=y:
                 raise NameError, "%s union names don't match" % (p,)
       self.unbound_set = alldomain - allnames
       
   def attributes(self):
       return self.select_list.attorder
       
   def eval(self, dynamic=None, outerboundtuple=None):
       """leaves a lot to be desired.
          dynamic and outerboundtuple are mutually
          exclusive.  dynamic is only pertinent to
          top levels, outerboundtuple to subqueries"""
       #print "select eval", dynamic, outerboundtuple
       from gfdb0 import Relation0
       # only uncache if outerboundtuple is None (not subquery)
       # ???
       if outerboundtuple is None:
           self.uncache()
       query_plan = self.query_plan
       where_pred = self.where_pred.detrivialize()
       select_list = self.select_list
       # shortcut
       if where_pred is not None and where_pred.false: 
          return Relation0(select_list.attorder, [])
       #print "where_pred", where_pred
       if where_pred is None or where_pred.constraints is None:
          assn0 = assn1 = kjbuckets.kjDict()
       else:
          assn1 = self.where_pred.constraints.assns
          assn0 = assn1 = kjbuckets.kjDict(assn1)
       # erase stored results from possible previous evaluation
       ndynamic = self.ndynamic
       if outerboundtuple is not None: 
          assn1 = assn1 + outerboundtuple.assns
       elif ndynamic:
          dyn = dynamic_binding(ndynamic, dynamic)
          if len(dyn)!=1:
             raise ValueError, "only one dynamic subst for selection allowed"
          dyn = dyn[0]
          assn1 = assn1 + dyn
          #print "dynamic", bt
       #print "assn1", assn1
       # check unbound names
       unbound_set = self.unbound_set
       #print "unbound", unbound_set
       #print unbound_set
       #print self.rel_atts
       for pair in unbound_set.items():
           if not assn1.has_key(pair):
              raise KeyError, `pair`+": unbound in selection"
       assn1 = (unbound_set * assn1) + assn0
       #print "assn1 now", assn1
       substseq = [assn1]
       for h in query_plan:
           #print "***"
           #for x in substseq:
               #print x
           #print "***"
           substseq = h.join(substseq)
           if not substseq: break
           #print "***"
           #for x in substseq:
               #print x
           #print "***"
       # apply the rest of the where predicate at top level
       if substseq and where_pred is not None:
          #where_pred.uncache()
          substseq = where_pred(substseq, 1)
       # eliminate zeros/nulls
       substseq = no_ints_nulls(substseq)
       # apply grouping if present
       group_list = self.group_list
       if substseq and group_list:
          substseq = aggregate(substseq, group_list)
          having_cond = self.having_cond
          #print having_cond
          if having_cond is not None:
             #having_cond.uncache()
             substseq = no_ints_nulls(having_cond(substseq))
       elif self.all_aggregate:
          # universal group
          substseq = [kjbuckets.kjDict( [(None, substseq)] ) ]
       (tups, attorder) = select_list.map(substseq)
       # do UNION if present
       union_select = self.union_select
       if union_select is not None:
          tups = union_select.eval(tups, dynamic, outerboundtuple)
       # apply DISTINCT if appropriate
       if self.alldistinct=="DISTINCT":
          tups = kjbuckets.kjSet(tups).items()
       # apply ordering if present
       ob = self.order_by
       if ob:
          tups = order_tuples(ob, tups)
       return Relation0(attorder, tups)
       
   def __repr__(self):
       ndyn = ""
       if self.ndynamic:
          ndyn = "\n[%s dynamic parameters]" % self.ndynamic
       result = SELECT_TEMPLATE % (
         self.alldistinct,
         self.select_list,
         self.table_list,
         self.where_pred,
         self.group_list,
         self.having_cond,
         #union_spec,
         self.union_select,
         self.order_by,
         ndyn
         )
       return result   
       
class Union(SimpleRecursive):
   """union clause."""

   def __init__(self, alldistinct, selection):
       self.alldistinct = alldistinct
       self.selection = selection
       
   def initargs(self):
       return (self.alldistinct, self.selection)
       
   def unbound(self):
       return self.selection.unbound()
       
   def relbind(self, db, outer=None):
       self.selection = self.selection.relbind(db, outer)
       return self
       
   def check_domains(self):
       self.selection.check_domains()
       
   def attributes(self):
       return self.selection.attributes()
       
   def eval(self, assns, dyn=None, outer=None):
       r = self.selection.eval(dyn, outer)
       rows = r.rows()
       allrows = rows + assns
       if self.alldistinct=="DISTINCT":
          allrows = kjbuckets.kjSet(allrows).items()
       return allrows
       
   def __repr__(self):
       return "\nUNION %s %s " % (self.alldistinct, self.selection)
       
class Intersect(Union):
   def eval(self, assns, dyn=None, outer=None):
       r = self.selection.eval(dyn, outer)
       rows = r.rows()
       kjSet = kjbuckets.kjSet
       allrows = (kjSet(assns) & kjSet(rows)).items()
       return allrows
   op = "INTERSECT"
   def __repr__(self):
       return "\n%s %s" % (self.op, self.selection)
       
class Except(Union):
   def eval(self, assns, dyn=None, outer=None):
       r = self.selection.eval(dyn, outer)
       rows = r.rows()
       kjSet = kjbuckets.kjSet
       allrows = (kjSet(assns) - kjSet(rows)).items()
       return allrows
   op = "EXCEPT"
       
              
class Parse_Context:
   """contextual information for parsing
        p.param() returns a new sequence number for external parameter.
   """
   # not serializable
   
   parameter_index = 0
   
   # no __init__ yet
   def param(self):
       temp = self.parameter_index
       self.parameter_index = temp+1
       return temp
       
   def ndynamic(self):
       return self.parameter_index
# update/delete/insert statements
import sqlmod
CreateTable = sqlmod.CreateTable
CreateIndex = sqlmod.CreateIndex
DropIndex = sqlmod.DropIndex
DropTable = sqlmod.DropTable
UpdateOp = sqlmod.UpdateOp
DeleteOp = sqlmod.DeleteOp
InsertOp = sqlmod.InsertOp
InsertValues = sqlmod.InsertValues
InsertSubSelect = sqlmod.InsertSubSelect
ColumnDef = sqlmod.ColumnDef
CreateView = sqlmod.CreateView
DropView = sqlmod.DropView

# update storage structures from gfdb0
import gfdb0
Add_Tuples = gfdb0.Add_Tuples
Erase_Tuples = gfdb0.Erase_Tuples
Reset_Tuples = gfdb0.Reset_Tuples
       
####### testing
# test helpers
#def tp(**kw):
#    return maketuple(kw)
    
#def st(**kw):
#    return BTPredicate(BoundTuple(r=kw))
    
