1 """RQL to SQL generator for native sources.

     2 

     3 

     4 SQL queries optimization

     5 ~~~~~~~~~~~~~~~~~~~~~~~~

     6 1. EUser X WHERE X in_group G, G name 'users':

     7 

     8    EUser is the only subject entity type for the in_group relation,

     9    which allow us to do ::

    10 

    11      SELECT eid_from FROM in_group, EGroup

    12      WHERE in_group.eid_to = EGroup.eid_from

    13      AND EGroup.name = 'users'

    14 

    15 

    16 2. Any X WHERE X nonfinal1 Y, Y nonfinal2 Z

    17 

    18    -> direct join between nonfinal1 and nonfinal2, whatever X,Y, Z (unless

    19       inlined...)

    20       

    21       NOT IMPLEMENTED (and quite hard to implement)

    22 

    23 Potential optimization information is collected by the querier, sql generation

    24 is done according to this information

    25 

    26 

    27 :organization: Logilab

    28 :copyright: 2001-2008 LOGILAB S.A. (Paris, FRANCE), all rights reserved.

    29 :contact: http://www.logilab.fr/ -- mailto:contact@logilab.fr

    30 """

    31 __docformat__ = "restructuredtext en"

    32 

    33 import threading

    34 

    35 from rql import BadRQLQuery, CoercionError

    36 from rql.stmts import Union, Select

    37 from rql.nodes import (SortTerm, VariableRef, Constant, Function, Not,

    38                        Variable, ColumnAlias, Relation, SubQuery, Exists)

    39 

    40 from cubicweb import server

    41 from cubicweb.server.utils import cleanup_solutions

    42 

    43 def _new_var(select, varname): 

    44     newvar = select.get_variable(varname)

    45     if not 'relations' in newvar.stinfo:

    46         # not yet initialized

    47         newvar.prepare_annotation()

    48         newvar.stinfo['scope'] = select

    49         newvar._q_invariant = False

    50     return newvar

    51 

    52 def _fill_to_wrap_rel(var, newselect, towrap, schema):

    53     for rel in var.stinfo['relations'] - var.stinfo['rhsrelations']:

    54         rschema = schema.rschema(rel.r_type)

    55         if rschema.inlined:

    56             towrap.add( (var, rel) )

    57             for vref in rel.children[1].iget_nodes(VariableRef):

    58                 newivar = _new_var(newselect, vref.name)

    59                 newselect.selection.append(VariableRef(newivar))

    60                 _fill_to_wrap_rel(vref.variable, newselect, towrap, schema)

    61         elif rschema.is_final():

    62             towrap.add( (var, rel) )

    63    

    64 def rewrite_unstable_outer_join(select, solutions, unstable, schema):

    65     """if some optional variables are unstable, they should be selected in a

    66     subquery. This function check this and rewrite the rql syntax tree if

    67     necessary (in place). Return a boolean telling if the tree has been modified

    68     """

    69     torewrite = set()

    70     modified = False

    71     for varname in tuple(unstable):

    72         var = select.defined_vars[varname]

    73         if not var.stinfo['optrelations']:

    74             continue

    75         modified = True

    76         unstable.remove(varname)

    77         torewrite.add(var)

    78         newselect = Select()

    79         newselect.need_distinct = False

    80         myunion = Union()

    81         myunion.append(newselect)

    82         # extract aliases / selection

    83         newvar = _new_var(newselect, var.name)

    84         newselect.selection = [VariableRef(newvar)]

    85         for avar in select.defined_vars.itervalues():

    86             if avar.stinfo['attrvar'] is var:

    87                 newavar = _new_var(newselect, avar.name)

    88                 newavar.stinfo['attrvar'] = newvar

    89                 newselect.selection.append(VariableRef(newavar))

    90         towrap_rels = set()

    91         _fill_to_wrap_rel(var, newselect, towrap_rels, schema)

    92         # extract relations

    93         for var, rel in towrap_rels:

    94             newrel = rel.copy(newselect)

    95             newselect.add_restriction(newrel)

    96             select.remove_node(rel)

    97             var.stinfo['relations'].remove(rel)

    98             newvar.stinfo['relations'].add(newrel)

    99             if rel.optional in ('left', 'both'):

   100                 newvar.stinfo['optrelations'].add(newrel)

   101             for vref in newrel.children[1].iget_nodes(VariableRef):

   102                 var = vref.variable

   103                 var.stinfo['relations'].add(newrel)

   104                 var.stinfo['rhsrelations'].add(newrel)

   105                 if rel.optional in ('right', 'both'):

   106                     var.stinfo['optrelations'].add(newrel)                

   107         # extract subquery solutions

   108         solutions = [sol.copy() for sol in solutions]

   109         cleanup_solutions(newselect, solutions)

   110         newselect.set_possible_types(solutions)

   111         # full sub-query

   112         aliases = [VariableRef(select.get_variable(avar.name, i))

   113                    for i, avar in enumerate(newselect.selection)]

   114         select.add_subquery(SubQuery(aliases, myunion), check=False)

   115     return modified

   116 

   117 def _new_solutions(rqlst, solutions):

   118     """first filter out subqueries variables from solutions"""

   119     newsolutions = []

   120     for origsol in solutions:

   121         asol = {}

   122         for vname in rqlst.defined_vars:

   123             asol[vname] = origsol[vname]

   124         if not asol in newsolutions:

   125             newsolutions.append(asol)

   126     return newsolutions

   127 

   128 def remove_unused_solutions(rqlst, solutions, varmap, schema):

   129     """cleanup solutions: remove solutions where invariant variables are taking

   130     different types

   131     """

   132     newsolutions = _new_solutions(rqlst, solutions)

   133     existssols = {}

   134     unstable = set()

   135     for vname, var in rqlst.defined_vars.iteritems():

   136         vtype = newsolutions[0][vname]

   137         if var._q_invariant or vname in varmap:

   138             for i in xrange(len(newsolutions)-1, 0, -1):

   139                 if vtype != newsolutions[i][vname]:

   140                     newsolutions.pop(i)

   141         elif not var.scope is rqlst:

   142             # move appart variables which are in a EXISTS scope and are variating

   143             try:

   144                 thisexistssols, thisexistsvars = existssols[var.scope]

   145             except KeyError:

   146                 thisexistssols = [newsolutions[0]]

   147                 thisexistsvars = set()

   148                 existssols[var.scope] = thisexistssols, thisexistsvars

   149             for i in xrange(len(newsolutions)-1, 0, -1):

   150                 if vtype != newsolutions[i][vname]:

   151                     thisexistssols.append(newsolutions.pop(i))

   152                     thisexistsvars.add(vname)

   153         else:

   154             # remember unstable variables

   155             for i in xrange(1, len(newsolutions)):

   156                 if vtype != newsolutions[i][vname]:

   157                     unstable.add(vname)

   158     if len(newsolutions) > 1:

   159         if rewrite_unstable_outer_join(rqlst, newsolutions, unstable, schema):

   160             # remove variables extracted to subqueries from solutions

   161             newsolutions = _new_solutions(rqlst, newsolutions)

   162     return newsolutions, existssols, unstable

   163 

   164 def relation_info(relation):

   165     lhs, rhs = relation.get_variable_parts()

   166     try:

   167         lhs = lhs.variable

   168         lhsconst = lhs.stinfo['constnode']

   169     except AttributeError:

   170         lhsconst = lhs

   171         lhs = None

   172     except KeyError:

   173         lhsconst = None # ColumnAlias

   174     try:

   175         rhs = rhs.variable

   176         rhsconst = rhs.stinfo['constnode']

   177     except AttributeError:

   178         rhsconst = rhs

   179         rhs = None

   180     except KeyError:

   181         rhsconst = None # ColumnAlias

   182     return lhs, lhsconst, rhs, rhsconst

   183 

   184 def switch_relation_field(sql, table=''):

   185     switchedsql = sql.replace(table + '.eid_from', '__eid_from__')

   186     switchedsql = switchedsql.replace(table + '.eid_to',

   187                                       table + '.eid_from')

   188     return switchedsql.replace('__eid_from__', table + '.eid_to')

   189 

   190 def sort_term_selection(sorts, selectedidx, rqlst, groups):

   191     # XXX beurk

   192     if isinstance(rqlst, list):

   193         def append(term):

   194             rqlst.append(term)

   195     else:

   196         def append(term):

   197             rqlst.selection.append(term.copy(rqlst))

   198     for sortterm in sorts:

   199         term = sortterm.term

   200         if not isinstance(term, Constant) and not str(term) in selectedidx:

   201             selectedidx.append(str(term))

   202             append(term)

   203             if groups:

   204                 for vref in term.iget_nodes(VariableRef):

   205                     if not vref in groups:

   206                         groups.append(vref)

   207         

   208 def fix_selection(rqlst, selectedidx, needwrap, sorts, groups, having):

   209     if sorts:

   210         sort_term_selection(sorts, selectedidx, rqlst, not needwrap and groups)

   211     if needwrap:

   212         if groups:

   213             for vref in groups:

   214                 if not vref.name in selectedidx:

   215                     selectedidx.append(vref.name)

   216                     rqlst.selection.append(vref)

   217         if having:

   218             for term in having:

   219                 for vref in term.iget_nodes(VariableRef):

   220                     if not vref.name in selectedidx:

   221                         selectedidx.append(vref.name)

   222                         rqlst.selection.append(vref)

   223 

   224 # IGenerator implementation for RQL->SQL ######################################

   225 

   226 

   227 class StateInfo(object):

   228     def __init__(self, existssols, unstablevars):

   229         self.existssols = existssols

   230         self.unstablevars = unstablevars

   231         self.subtables = {}

   232         

   233     def reset(self, solution):

   234         """reset some visit variables"""

   235         self.solution = solution

   236         self.count = 0

   237         self.done = set()

   238         self.tables = self.subtables.copy()

   239         self.actual_tables = [[]]

   240         for _, tsql in self.tables.itervalues():

   241             self.actual_tables[-1].append(tsql)

   242         self.outer_tables = {}

   243         self.duplicate_switches = []

   244         self.attr_vars = {}

   245         self.aliases = {}

   246         self.restrictions = []

   247         self._restr_stack = []

   248         

   249     def add_restriction(self, restr):

   250         if restr:

   251             self.restrictions.append(restr)

   252             

   253     def iter_exists_sols(self, exists):

   254         if not exists in self.existssols:

   255             yield 1

   256             return

   257         thisexistssols, thisexistsvars = self.existssols[exists]

   258         origsol = self.solution

   259         origtables = self.tables

   260         done = self.done

   261         for thisexistssol in thisexistssols:

   262             for vname in self.unstablevars:

   263                 if thisexistssol[vname] != origsol[vname] and vname in thisexistsvars:

   264                     break

   265             else:

   266                 self.tables = origtables.copy()

   267                 self.solution = thisexistssol

   268                 yield 1

   269                 # cleanup self.done from stuff specific to exists

   270                 for var in thisexistsvars:

   271                     if var in done:

   272                         done.remove(var)

   273                 for rel in exists.iget_nodes(Relation):

   274                     if rel in done:

   275                         done.remove(rel)

   276         self.solution = origsol

   277         self.tables = origtables

   278 

   279     def push_scope(self):

   280         self.actual_tables.append([])

   281         self._restr_stack.append(self.restrictions)

   282         self.restrictions = []

   283 

   284     def pop_scope(self):

   285         restrictions = self.restrictions

   286         self.restrictions = self._restr_stack.pop()

   287         return restrictions, self.actual_tables.pop()

   288     

   289     

   290 class SQLGenerator(object):

   291     """

   292     generation of SQL from the fully expanded RQL syntax tree

   293     SQL is designed to be used with a CubicWeb SQL schema

   294 

   295     Groups and sort are not handled here since they should not be handled at

   296     this level (see cubicweb.server.querier)

   297     

   298     we should not have errors here !

   299 

   300     WARNING: a CubicWebSQLGenerator instance is not thread safe, but generate is

   301     protected by a lock

   302     """

   303     

   304     def __init__(self, schema, dbms_helper, dbencoding='UTF-8'):

   305         self.schema = schema

   306         self.dbms_helper = dbms_helper

   307         self.dbencoding = dbencoding

   308         self.keyword_map = {'NOW' : self.dbms_helper.sql_current_timestamp,

   309                             'TODAY': self.dbms_helper.sql_current_date,

   310                             }

   311         if not self.dbms_helper.union_parentheses_support:

   312             self.union_sql = self.noparen_union_sql

   313         self._lock = threading.Lock()

   314         

   315     def generate(self, union, args=None, varmap=None):

   316         """return SQL queries and a variable dictionnary from a RQL syntax tree

   317 

   318         :partrqls: a list of couple (rqlst, solutions)

   319         :args: optional dictionary with values of substitutions used in the query

   320         :varmap: optional dictionary mapping variable name to a special table

   321           name, in case the query as to fetch data from temporary tables

   322 

   323         return an sql string and a dictionary with substitutions values

   324         """

   325         if args is None:

   326             args = {}

   327         if varmap is None:

   328             varmap =  {}

   329         self._lock.acquire()

   330         self._args = args

   331         self._varmap = varmap

   332         self._query_attrs = {}

   333         self._state = None

   334         try:

   335             # union query for each rqlst / solution

   336             sql = self.union_sql(union)

   337             # we are done

   338             return sql, self._query_attrs

   339         finally:

   340             self._lock.release()

   341 

   342     def union_sql(self, union, needalias=False): # pylint: disable-msg=E0202

   343         if len(union.children) == 1:

   344             return self.select_sql(union.children[0], needalias)

   345         sqls = ('(%s)' % self.select_sql(select, needalias)

   346                 for select in union.children)

   347         return '\nUNION ALL\n'.join(sqls)

   348 

   349     def noparen_union_sql(self, union, needalias=False):

   350         # needed for sqlite backend which doesn't like parentheses around

   351         # union query. This may cause bug in some condition (sort in one of

   352         # the subquery) but will work in most case

   353         # see http://www.sqlite.org/cvstrac/tktview?tn=3074

   354         sqls = (self.select_sql(select, needalias)

   355                 for i, select in enumerate(union.children))

   356         return '\nUNION ALL\n'.join(sqls)

   357     

   358     def select_sql(self, select, needalias=False):

   359         """return SQL queries and a variable dictionnary from a RQL syntax tree

   360 

   361         :select: a selection statement of the syntax tree (`rql.stmts.Select`)

   362         :solution: a dictionnary containing variables binding.

   363           A solution's dictionnary has variable's names as key and variable's

   364           types as values

   365         :needwrap: boolean telling if the query will be wrapped in an outer

   366           query (to deal with aggregat and/or grouping)

   367         """

   368         distinct = selectsortterms = select.need_distinct

   369         sorts = select.orderby

   370         groups = select.groupby

   371         having = select.having

   372         # remember selection, it may be changed and have to be restored

   373         origselection = select.selection[:]

   374         # check if the query will have union subquery, if it need sort term

   375         # selection (union or distinct query) and wrapping (union with groups)

   376         needwrap = False

   377         sols = select.solutions

   378         if len(sols) > 1:

   379             # remove invariant from solutions

   380             sols, existssols, unstable = remove_unused_solutions(

   381                 select, sols, self._varmap, self.schema)

   382             if len(sols) > 1:

   383                 # if there is still more than one solution, a UNION will be

   384                 # generated and so sort terms have to be selected

   385                 selectsortterms = True

   386                 # and if select is using group by or aggregat, a wrapping

   387                 # query will be necessary

   388                 if groups or select.has_aggregat:

   389                     select.select_only_variables()

   390                     needwrap = True                        

   391         else:

   392             existssols, unstable = {}, ()

   393         state = StateInfo(existssols, unstable)

   394         # treat subqueries

   395         self._subqueries_sql(select, state)

   396         # generate sql for this select node

   397         selectidx = [str(term) for term in select.selection]

   398         if needwrap:

   399             outerselection = origselection[:]

   400             if sorts and selectsortterms:

   401                 outerselectidx = [str(term) for term in outerselection]

   402                 if distinct:

   403                     sort_term_selection(sorts, outerselectidx,

   404                                         outerselection, groups)

   405             else:

   406                 outerselectidx = selectidx[:]

   407         fix_selection(select, selectidx, needwrap,

   408                       selectsortterms and sorts, groups, having)

   409         if needwrap:

   410             fselectidx = outerselectidx

   411             fneedwrap = len(outerselection) != len(origselection)

   412         else:

   413             fselectidx = selectidx

   414             fneedwrap = len(select.selection) != len(origselection)

   415         if fneedwrap:

   416             needalias = True

   417         self._in_wrapping_query = False

   418         self._state = state

   419         try:

   420             sql = self._solutions_sql(select, sols, distinct, needalias or needwrap)

   421             # generate groups / having before wrapping query selection to

   422             # get correct column aliases

   423             self._in_wrapping_query = needwrap

   424             if groups:

   425                 # no constant should be inserted in GROUP BY else the backend will

   426                 # interpret it as a positional index in the selection

   427                 groups = ','.join(vref.accept(self) for vref in groups

   428                                   if not isinstance(vref, Constant))

   429             if having:

   430                 # filter out constants as for GROUP BY

   431                 having = ','.join(vref.accept(self) for vref in having

   432                                   if not isinstance(vref, Constant))

   433             if needwrap:

   434                 sql = '%s FROM (%s) AS T1' % (self._selection_sql(outerselection, distinct,

   435                                                                   needalias),

   436                                               sql)

   437             if groups:

   438                 sql += '\nGROUP BY %s' % groups

   439             if having:

   440                 sql += '\nHAVING %s' % having

   441             # sort

   442             if sorts:

   443                 sql += '\nORDER BY %s' % ','.join(self._sortterm_sql(sortterm, 

   444                                                                      fselectidx)

   445                                                   for sortterm in sorts)

   446                 if fneedwrap:

   447                     selection = ['T1.C%s' % i for i in xrange(len(origselection))]

   448                     sql = 'SELECT %s FROM (%s) AS T1' % (','.join(selection), sql)

   449         finally:

   450             select.selection = origselection

   451         # limit / offset

   452         limit = select.limit

   453         if limit:

   454             sql += '\nLIMIT %s' % limit

   455         offset = select.offset

   456         if offset:

   457             sql += '\nOFFSET %s' % offset

   458         return sql

   459 

   460     def _subqueries_sql(self, select, state):

   461         for i, subquery in enumerate(select.with_):

   462             sql = self.union_sql(subquery.query, needalias=True)

   463             tablealias = '_T%s' % i

   464             sql = '(%s) AS %s' % (sql, tablealias)

   465             state.subtables[tablealias] = (0, sql)

   466             for vref in subquery.aliases:

   467                 alias = vref.variable

   468                 alias._q_sqltable = tablealias

   469                 alias._q_sql = '%s.C%s' % (tablealias, alias.colnum)

   470 

   471     def _solutions_sql(self, select, solutions, distinct, needalias):

   472         sqls = []

   473         for solution in solutions:

   474             self._state.reset(solution)

   475             # visit restriction subtree

   476             if select.where is not None:

   477                 self._state.add_restriction(select.where.accept(self))

   478             sql = [self._selection_sql(select.selection, distinct, needalias)]

   479             if self._state.restrictions:

   480                 sql.append('WHERE %s' % ' AND '.join(self._state.restrictions))

   481             # add required tables

   482             assert len(self._state.actual_tables) == 1, self._state.actual_tables

   483             tables = self._state.actual_tables[-1]

   484             if tables:

   485                 # sort for test predictability

   486                 sql.insert(1, 'FROM %s' % ', '.join(sorted(tables)))

   487             elif self._state.restrictions and self.dbms_helper.needs_from_clause:

   488                 sql.insert(1, 'FROM (SELECT 1) AS _T')

   489             sqls.append('\n'.join(sql))

   490         if distinct:

   491             return '\nUNION\n'.join(sqls)

   492         else:

   493             return '\nUNION ALL\n'.join(sqls)

   494         

   495     def _selection_sql(self, selected, distinct, needaliasing=False):

   496         clause = []

   497         for term in selected:

   498             sql = term.accept(self)

   499             if needaliasing:

   500                 colalias = 'C%s' % len(clause)

   501                 clause.append('%s AS %s' % (sql, colalias))

   502                 if isinstance(term, VariableRef):

   503                     self._state.aliases[term.name] = colalias

   504             else:

   505                 clause.append(sql)

   506         if distinct:

   507             return 'SELECT DISTINCT %s' % ', '.join(clause)

   508         return 'SELECT %s' % ', '.join(clause)

   509 

   510     def _sortterm_sql(self, sortterm, selectidx):

   511         term = sortterm.term

   512         try:

   513             sqlterm = str(selectidx.index(str(term)) + 1)

   514         except ValueError:

   515             # Constant node or non selected term

   516             sqlterm = str(term.accept(self))

   517         if sortterm.asc:

   518             return sqlterm

   519         else:

   520             return '%s DESC' % sqlterm

   521 

   522     def visit_and(self, et):

   523         """generate SQL for a AND subtree"""

   524         res = []

   525         for c in et.children:

   526             part = c.accept(self)

   527             if part:

   528                 res.append(part)

   529         return ' AND '.join(res)

   530 

   531     def visit_or(self, ou):

   532         """generate SQL for a OR subtree"""

   533         res = []

   534         for c in ou.children:

   535             part = c.accept(self)

   536             if part:

   537                 res.append('(%s)' % part)

   538         if res:

   539             if len(res) > 1:

   540                 return '(%s)' % ' OR '.join(res)

   541             return res[0]

   542         return ''

   543     

   544     def visit_not(self, node):

   545         self._state.push_scope()

   546         csql = node.children[0].accept(self)

   547         sqls, tables = self._state.pop_scope()

   548         if node in self._state.done or not csql:

   549             # already processed or no sql generated by children

   550             self._state.actual_tables[-1] += tables

   551             self._state.restrictions += sqls

   552             return csql

   553         if isinstance(node.children[0], Exists):

   554             assert not sqls, (sqls, str(node.stmt))

   555             assert not tables, (tables, str(node.stmt))

   556             return 'NOT %s' % csql

   557         sqls.append(csql)

   558         if tables:

   559             select = 'SELECT 1 FROM %s' % ','.join(tables)

   560         else:

   561             select = 'SELECT 1'

   562         if sqls:

   563             sql = 'NOT EXISTS(%s WHERE %s)' % (select, ' AND '.join(sqls))

   564         else:

   565             sql = 'NOT EXISTS(%s)' % select

   566         return sql

   567 

   568     def visit_exists(self, exists):

   569         """generate SQL name for a exists subquery"""

   570         sqls = []

   571         for dummy in self._state.iter_exists_sols(exists):

   572             sql = self._visit_exists(exists)

   573             if sql:

   574                 sqls.append(sql)

   575         if not sqls:

   576             return ''

   577         return 'EXISTS(%s)' % ' UNION '.join(sqls)

   578             

   579     def _visit_exists(self, exists):

   580         self._state.push_scope()

   581         restriction = exists.children[0].accept(self)

   582         restrictions, tables = self._state.pop_scope()

   583         if restriction:

   584             restrictions.append(restriction)

   585         restriction = ' AND '.join(restrictions)

   586         if not restriction:

   587             return ''

   588         if not tables:

   589             # XXX could leave surrounding EXISTS() in this case no?

   590             sql = 'SELECT 1 WHERE %s' % restriction 

   591         else:

   592             sql = 'SELECT 1 FROM %s WHERE %s' % (', '.join(tables), restriction)

   593         return sql

   594 

   595     

   596     def visit_relation(self, relation):

   597         """generate SQL for a relation"""

   598         rtype = relation.r_type

   599         # don't care of type constraint statement (i.e. relation_type = 'is')

   600         if relation.is_types_restriction():

   601             return ''

   602         lhs, rhs = relation.get_parts()

   603         rschema = self.schema.rschema(rtype)

   604         if rschema.is_final():

   605             if rtype == 'eid' and lhs.variable._q_invariant and \

   606                    lhs.variable.stinfo['constnode']:

   607                 # special case where this restriction is already generated by

   608                 # some other relation

   609                 return ''

   610             # attribute relation

   611             if rtype == 'has_text':

   612                 sql = self._visit_has_text_relation(relation)

   613             else:

   614                 rhs_vars = rhs.get_nodes(VariableRef)

   615                 if rhs_vars:

   616                     # if variable(s) in the RHS

   617                     sql = self._visit_var_attr_relation(relation, rhs_vars)

   618                 else:

   619                     # no variables in the RHS

   620                     sql = self._visit_attribute_relation(relation)

   621                 if relation.neged(strict=True):

   622                     self._state.done.add(relation.parent)

   623                     sql = 'NOT (%s)' % sql

   624         else:

   625             if rtype == 'is' and rhs.operator == 'IS':

   626                 # special case "C is NULL"

   627                 if lhs.name in self._varmap:

   628                     lhssql = self._varmap[lhs.name]

   629                 else:

   630                     lhssql = lhs.accept(self)

   631                 return '%s%s' % (lhssql, rhs.accept(self))

   632             if '%s.%s' % (lhs, relation.r_type) in self._varmap:

   633                 # relation has already been processed by a previous step

   634                 return

   635             if relation.optional:

   636                 # check it has not already been treaten (to get necessary

   637                 # information to add an outer join condition)

   638                 if relation in self._state.done:

   639                     return

   640                 # OPTIONAL relation, generate a left|right outer join

   641                 sql = self._visit_outer_join_relation(relation, rschema)

   642             elif rschema.inlined:

   643                 sql = self._visit_inlined_relation(relation)

   644 #             elif isinstance(relation.parent, Not):

   645 #                 self._state.done.add(relation.parent)

   646 #                 # NOT relation

   647 #                 sql = self._visit_not_relation(relation, rschema)

   648             else:

   649                 # regular (non final) relation

   650                 sql = self._visit_relation(relation, rschema)

   651         return sql

   652 

   653     def _visit_inlined_relation(self, relation):

   654         lhsvar, _, rhsvar, rhsconst = relation_info(relation)

   655         # we are sure here to have a lhsvar

   656         assert lhsvar is not None

   657         lhssql = self._inlined_var_sql(lhsvar, relation.r_type)

   658         if isinstance(relation.parent, Not):

   659             self._state.done.add(relation.parent)

   660             sql = "%s IS NULL" % lhssql

   661             if rhsvar is not None and not rhsvar._q_invariant:

   662                 sql = '(%s OR %s!=%s)' % (sql, lhssql, rhsvar.accept(self))

   663             return sql

   664         if rhsconst is not None:

   665             return '%s=%s' % (lhssql, rhsconst.accept(self))

   666         if isinstance(rhsvar, Variable) and not rhsvar.name in self._varmap:

   667             # if the rhs variable is only linked to this relation, this mean we

   668             # only want the relation to exists, eg NOT NULL in case of inlined

   669             # relation

   670             if len(rhsvar.stinfo['relations']) == 1 and rhsvar._q_invariant:

   671                 return '%s IS NOT NULL' % lhssql

   672             if rhsvar._q_invariant:

   673                 return self._extra_join_sql(relation, lhssql, rhsvar)

   674         return '%s=%s' % (lhssql, rhsvar.accept(self))

   675 

   676     def _process_relation_term(self, relation, rid, termvar, termconst, relfield):

   677         if termconst or isinstance(termvar, ColumnAlias) or not termvar._q_invariant:

   678             termsql = termconst and termconst.accept(self) or termvar.accept(self)

   679             yield '%s.%s=%s' % (rid, relfield, termsql)

   680         elif termvar._q_invariant:

   681             # if the variable is mapped, generate restriction anyway

   682             if termvar.name in self._varmap:

   683                 termsql = termvar.accept(self)

   684                 yield '%s.%s=%s' % (rid, relfield, termsql)

   685             extrajoin = self._extra_join_sql(relation, '%s.%s' % (rid, relfield), termvar)

   686             if extrajoin:

   687                 yield extrajoin

   688         

   689     def _visit_relation(self, relation, rschema):

   690         """generate SQL for a relation

   691 

   692         implements optimization 1.

   693         """

   694         if relation.r_type == 'identity':

   695             # special case "X identity Y"

   696             lhs, rhs = relation.get_parts()

   697             if isinstance(relation.parent, Not):

   698                 self._state.done.add(relation.parent)

   699                 return 'NOT %s%s' % (lhs.accept(self), rhs.accept(self))

   700             return '%s%s' % (lhs.accept(self), rhs.accept(self))

   701         lhsvar, lhsconst, rhsvar, rhsconst = relation_info(relation)

   702         rid = self._relation_table(relation)

   703         sqls = []

   704         sqls += self._process_relation_term(relation, rid, lhsvar, lhsconst, 'eid_from')

   705         sqls += self._process_relation_term(relation, rid, rhsvar, rhsconst, 'eid_to')

   706         sql = ' AND '.join(sqls)

   707         if rschema.symetric:

   708             sql = '(%s OR %s)' % (sql, switch_relation_field(sql))

   709         return sql

   710 

   711     def _visit_outer_join_relation(self, relation, rschema):

   712         """

   713         left outer join syntax (optional=='right'):

   714           X relation Y?

   715           

   716         right outer join syntax (optional=='left'):

   717           X? relation Y

   718           

   719         full outer join syntaxes (optional=='both'):

   720           X? relation Y?

   721 

   722         if relation is inlined:

   723            if it's a left outer join:

   724            -> X LEFT OUTER JOIN Y ON (X.relation=Y.eid)

   725            elif it's a right outer join:

   726            -> Y LEFT OUTER JOIN X ON (X.relation=Y.eid)

   727            elif it's a full outer join:

   728            -> X FULL OUTER JOIN Y ON (X.relation=Y.eid)

   729         else:

   730            if it's a left outer join:

   731            -> X LEFT OUTER JOIN relation ON (relation.eid_from=X.eid)

   732               LEFT OUTER JOIN Y ON (relation.eid_to=Y.eid)

   733            elif it's a right outer join:

   734            -> Y LEFT OUTER JOIN relation ON (relation.eid_to=Y.eid)

   735               LEFT OUTER JOIN X ON (relation.eid_from=X.eid)

   736            elif it's a full outer join:

   737            -> X FULL OUTER JOIN Y ON (X.relation=Y.eid)

   738         """

   739         lhsvar, lhsconst, rhsvar, rhsconst = relation_info(relation)

   740         if relation.optional == 'right':

   741             joinattr, restrattr = 'eid_from', 'eid_to'

   742         else:

   743             lhsvar, rhsvar = rhsvar, lhsvar

   744             lhsconst, rhsconst = rhsconst, lhsconst

   745             joinattr, restrattr = 'eid_to', 'eid_from'

   746         if relation.optional == 'both':

   747             outertype = 'FULL'

   748         else:

   749             outertype = 'LEFT'

   750         if rschema.inlined or relation.r_type == 'identity':

   751             self._state.done.add(relation)

   752             t1 = self._var_table(lhsvar)

   753             if relation.r_type == 'identity':

   754                 attr = 'eid'

   755             else:

   756                 attr = relation.r_type

   757             # reset lhs/rhs, we need the initial order now

   758             lhs, rhs = relation.get_variable_parts()

   759             if '%s.%s' % (lhs.name, attr) in self._varmap:

   760                 lhssql = self._varmap['%s.%s' % (lhs.name, attr)]

   761             else:

   762                 lhssql = '%s.%s' % (self._var_table(lhs.variable), attr)

   763             if not rhsvar is None:

   764                 t2 = self._var_table(rhsvar)

   765                 if t2 is None:

   766                     if rhsconst is not None:

   767                         # inlined relation with invariant as rhs

   768                         condition = '%s=%s' % (lhssql, rhsconst.accept(self))

   769                         if relation.r_type != 'identity':

   770                             condition = '(%s OR %s IS NULL)' % (condition, lhssql)

   771                         if not lhsvar.stinfo['optrelations']:

   772                             return condition

   773                         self.add_outer_join_condition(lhsvar, t1, condition)

   774                     return

   775             else:

   776                 condition = '%s=%s' % (lhssql, rhsconst.accept(self))

   777                 self.add_outer_join_condition(lhsvar, t1, condition)

   778             join = '%s OUTER JOIN %s ON (%s=%s)' % (

   779                 outertype, self._state.tables[t2][1], lhssql, rhs.accept(self))

   780             self.replace_tables_by_outer_join(join, t1, t2)

   781             return ''

   782         lhssql = lhsconst and lhsconst.accept(self) or lhsvar.accept(self)

   783         rhssql = rhsconst and rhsconst.accept(self) or rhsvar.accept(self)

   784         rid = self._relation_table(relation)

   785         if not lhsvar:

   786             join = ''

   787             toreplace = []

   788             maintable = rid

   789         else:

   790             join = '%s OUTER JOIN %s ON (%s.%s=%s' % (

   791                 outertype, self._state.tables[rid][1], rid, joinattr, lhssql)

   792             toreplace = [rid]

   793             maintable = self._var_table(lhsvar)

   794             if rhsconst:

   795                 join += ' AND %s.%s=%s)' % (rid, restrattr, rhssql)

   796             else:

   797                 join += ')'

   798         if not rhsconst:

   799             rhstable = self._var_table(rhsvar)

   800             if rhstable:

   801                 assert rhstable is not None, rhsvar

   802                 join += ' %s OUTER JOIN %s ON (%s.%s=%s)' % (

   803                     outertype, self._state.tables[rhstable][1], rid, restrattr, rhssql)

   804                 toreplace.append(rhstable)

   805         self.replace_tables_by_outer_join(join, maintable, *toreplace)

   806         return ''

   807 

   808     def _visit_var_attr_relation(self, relation, rhs_vars):

   809         """visit an attribute relation with variable(s) in the RHS

   810 

   811         attribute variables are used either in the selection or for

   812         unification (eg X attr1 A, Y attr2 A). In case of selection,

   813         nothing to do here.

   814         """

   815         contextrels = {}

   816         attrvars = self._state.attr_vars

   817         for var in rhs_vars:

   818             try:

   819                 contextrels[var.name] = attrvars[var.name]

   820             except KeyError:

   821                 attrvars[var.name] = relation

   822         if not contextrels:

   823             relation.children[1].accept(self, contextrels)

   824             return ''

   825         # at least one variable is already in attr_vars, this means we have to

   826         # generate unification expression

   827         lhssql = self._inlined_var_sql(relation.children[0].variable,

   828                                        relation.r_type)

   829         return '%s%s' % (lhssql, relation.children[1].accept(self, contextrels))

   830     

   831     def _visit_attribute_relation(self, relation):

   832         """generate SQL for an attribute relation"""

   833         lhs, rhs = relation.get_parts()

   834         rhssql = rhs.accept(self)

   835         table = self._var_table(lhs.variable)

   836         if table is None:

   837             assert relation.r_type == 'eid'

   838             lhssql = lhs.accept(self)

   839         else:

   840             try:

   841                 lhssql = self._varmap['%s.%s' % (lhs.name, relation.r_type)]

   842             except KeyError:

   843                 lhssql = '%s.%s' % (table, relation.r_type)

   844         try:

   845             if relation._q_needcast == 'TODAY':

   846                 sql = 'DATE(%s)%s' % (lhssql, rhssql)

   847             # XXX which cast function should be used

   848             #elif relation._q_needcast == 'NOW':

   849             #    sql = 'TIMESTAMP(%s)%s' % (lhssql, rhssql)

   850             else:

   851                 sql = '%s%s' % (lhssql, rhssql)

   852         except AttributeError:

   853             sql = '%s%s' % (lhssql, rhssql)

   854         if lhs.variable.stinfo['optrelations']:

   855             self.add_outer_join_condition(lhs.variable, table, sql)

   856         else:

   857             return sql

   858 

   859     def _visit_has_text_relation(self, relation):

   860         """generate SQL for a has_text relation"""

   861         lhs, rhs = relation.get_parts()

   862         const = rhs.children[0]

   863         alias = self._fti_table(relation)

   864         jointo = lhs.accept(self)

   865         restriction = ''

   866         lhsvar = lhs.variable

   867         me_is_principal = lhsvar.stinfo.get('principal') is relation

   868         if me_is_principal:

   869             if not lhsvar.stinfo['typerels']:

   870                 # the variable is using the fti table, no join needed

   871                 jointo = None

   872             elif not lhsvar.name in self._varmap:

   873                 # join on entities instead of etype's table to get result for

   874                 # external entities on multisources configurations

   875                 ealias = lhsvar._q_sqltable = lhsvar.name

   876                 jointo = lhsvar._q_sql = '%s.eid' % ealias

   877                 self.add_table('entities AS %s' % ealias, ealias)

   878                 if not lhsvar._q_invariant or len(lhsvar.stinfo['possibletypes']) == 1:

   879                     restriction = " AND %s.type='%s'" % (ealias, self._state.solution[lhs.name])

   880                 else:

   881                     etypes = ','.join("'%s'" % etype for etype in lhsvar.stinfo['possibletypes'])

   882                     restriction = " AND %s.type IN (%s)" % (ealias, etypes)

   883         if isinstance(relation.parent, Not):

   884             self._state.done.add(relation.parent)

   885             not_ = True

   886         else:

   887             not_ = False

   888         return self.dbms_helper.fti_restriction_sql(alias, const.eval(self._args),

   889                                                     jointo, not_) + restriction

   890         

   891     def visit_comparison(self, cmp, contextrels=None):

   892         """generate SQL for a comparaison"""

   893         if len(cmp.children) == 2:

   894             lhs, rhs = cmp.children

   895         else:

   896             lhs = None

   897             rhs = cmp.children[0]

   898         operator = cmp.operator

   899         if operator in ('IS', 'LIKE', 'ILIKE'):

   900             if operator == 'ILIKE' and not self.dbms_helper.ilike_support:

   901                 operator = ' LIKE '

   902             else:

   903                 operator = ' %s ' % operator

   904         elif isinstance(rhs, Function) and rhs.name == 'IN':

   905             assert operator == '='

   906             operator = ' '

   907         if lhs is None:

   908             return '%s%s'% (operator, rhs.accept(self, contextrels))

   909         return '%s%s%s'% (lhs.accept(self, contextrels), operator,

   910                           rhs.accept(self, contextrels))

   911             

   912     def visit_mathexpression(self, mexpr, contextrels=None):

   913         """generate SQL for a mathematic expression"""

   914         lhs, rhs = mexpr.get_parts()

   915         # check for string concatenation

   916         operator = mexpr.operator

   917         try:

   918             if mexpr.operator == '+' and mexpr.get_type(self._state.solution, self._args) == 'String':

   919                 operator = '||'

   920         except CoercionError:

   921             pass

   922         return '(%s %s %s)'% (lhs.accept(self, contextrels), operator,

   923                               rhs.accept(self, contextrels))

   924         

   925     def visit_function(self, func, contextrels=None):

   926         """generate SQL name for a function"""

   927         # function_description will check function is supported by the backend

   928         self.dbms_helper.function_description(func.name) 

   929         return '%s(%s)' % (func.name, ', '.join(c.accept(self, contextrels)

   930                                                 for c in func.children))

   931 

   932     def visit_constant(self, constant, contextrels=None):

   933         """generate SQL name for a constant"""

   934         value = constant.value

   935         if constant.type is None:

   936             return 'NULL'

   937         if constant.type == 'Int' and  isinstance(constant.parent, SortTerm):

   938             return constant.value

   939         if constant.type in ('Date', 'Datetime'):

   940             rel = constant.relation()

   941             if rel is not None:

   942                 rel._q_needcast = value

   943             return self.keyword_map[value]()

   944         if constant.type == 'Substitute':

   945             _id = constant.value

   946             if isinstance(_id, unicode):

   947                 _id = _id.encode()

   948         else:

   949             _id = str(id(constant)).replace('-', '', 1)

   950             if isinstance(value, unicode):

   951                 value = value.encode(self.dbencoding)

   952             self._query_attrs[_id] = value

   953         return '%%(%s)s' % _id

   954         

   955     def visit_variableref(self, variableref, contextrels=None):

   956         """get the sql name for a variable reference"""

   957         # use accept, .variable may be a variable or a columnalias

   958         return variableref.variable.accept(self, contextrels)

   959 

   960     def visit_columnalias(self, colalias, contextrels=None):

   961         """get the sql name for a subquery column alias"""

   962         if colalias.name in self._varmap:

   963             sql = self._varmap[colalias.name]

   964             self.add_table(sql.split('.', 1)[0])

   965             return sql

   966         return colalias._q_sql

   967     

   968     def visit_variable(self, variable, contextrels=None):

   969         """get the table name and sql string for a variable"""

   970         if contextrels is None and variable.name in self._state.done:

   971             if self._in_wrapping_query:

   972                 return 'T1.%s' % self._state.aliases[variable.name]

   973             return variable._q_sql

   974         self._state.done.add(variable.name)

   975         vtablename = None

   976         if contextrels is None and variable.name in self._varmap:

   977             sql, vtablename = self._var_info(variable)            

   978         elif variable.stinfo['attrvar']:

   979             # attribute variable (systematically used in rhs of final

   980             # relation(s)), get table name and sql from any rhs relation

   981             sql = self._linked_var_sql(variable, contextrels)

   982         elif variable._q_invariant:

   983             # since variable is invariant, we know we won't found final relation

   984             principal = variable.stinfo['principal']

   985             if principal is None:

   986                 vtablename = variable.name

   987                 self.add_table('entities AS %s' % variable.name, vtablename)

   988                 sql = '%s.eid' % vtablename

   989                 if variable.stinfo['typerels']:

   990                     # add additional restriction on entities.type column

   991                     pts = variable.stinfo['possibletypes']

   992                     if len(pts) == 1:

   993                         etype = iter(variable.stinfo['possibletypes']).next()

   994                         restr = "%s.type='%s'" % (vtablename, etype)

   995                     else:

   996                         etypes = ','.join("'%s'" % et for et in pts)

   997                         restr = '%s.type IN (%s)' % (vtablename, etypes)

   998                     self._state.add_restriction(restr)

   999             elif principal.r_type == 'has_text':

  1000                 sql = '%s.%s' % (self._fti_table(principal),

  1001                                  self.dbms_helper.fti_uid_attr)

  1002             elif principal in variable.stinfo['rhsrelations']:

  1003                 if self.schema.rschema(principal.r_type).inlined:

  1004                     sql = self._linked_var_sql(variable, contextrels)

  1005                 else:

  1006                     sql = '%s.eid_to' % self._relation_table(principal)

  1007             else:

  1008                 sql = '%s.eid_from' % self._relation_table(principal)

  1009         else:

  1010             # standard variable: get table name according to etype and use .eid

  1011             # attribute

  1012             sql, vtablename = self._var_info(variable)

  1013         variable._q_sqltable = vtablename

  1014         variable._q_sql = sql

  1015         return sql

  1016 

  1017     # various utilities #######################################################

  1018 

  1019     def _extra_join_sql(self, relation, sql, var):

  1020         # if rhs var is invariant, and this relation is not its principal,

  1021         # generate extra join

  1022         try:

  1023             if not var.stinfo['principal'] is relation:

  1024                 # need a predicable result for tests

  1025                 return '%s=%s' % tuple(sorted((sql, var.accept(self))))

  1026         except KeyError:

  1027             # no principal defined, relation is necessarily the principal and

  1028             # so nothing to return here

  1029             pass

  1030         return ''

  1031     

  1032     def _var_info(self, var):

  1033         # if current var or one of its attribute is selected , it *must*

  1034         # appear in the toplevel's FROM even if we're currently visiting

  1035         # a EXISTS node

  1036         if var.sqlscope is var.stmt:

  1037             scope = 0

  1038         else:

  1039             scope = -1

  1040         try:

  1041             sql = self._varmap[var.name]

  1042             table = sql.split('.', 1)[0]

  1043             if scope == -1:

  1044                 scope = self._varmap_table_scope(var.stmt, table)

  1045             self.add_table(table, scope=scope)

  1046         except KeyError:

  1047             etype = self._state.solution[var.name]

  1048             # XXX this check should be moved in rql.stcheck

  1049             if self.schema.eschema(etype).is_final():

  1050                 raise BadRQLQuery(var.stmt.root)

  1051             table = var.name

  1052             sql = '%s.eid' % table

  1053             self.add_table('%s AS %s' % (etype, table), table, scope=scope)

  1054         return sql, table

  1055     

  1056     def _inlined_var_sql(self, var, rtype):

  1057         try:

  1058             sql = self._varmap['%s.%s' % (var.name, rtype)]

  1059             scope = var.sqlscope is var.stmt and 0 or -1

  1060             self.add_table(sql.split('.', 1)[0], scope=scope)

  1061         except KeyError:

  1062             sql = '%s.%s' % (self._var_table(var), rtype)

  1063             #self._state.done.add(var.name)

  1064         return sql

  1065         

  1066     def _linked_var_sql(self, variable, contextrels=None):

  1067         if contextrels is None:

  1068             try:

  1069                 return self._varmap[variable.name]            

  1070             except KeyError:

  1071                 pass

  1072         rel = (contextrels and contextrels.get(variable.name) or 

  1073                variable.stinfo.get('principal') or

  1074                iter(variable.stinfo['rhsrelations']).next())

  1075         linkedvar = rel.children[0].variable

  1076         if rel.r_type == 'eid':

  1077             return linkedvar.accept(self)

  1078         if isinstance(linkedvar, ColumnAlias):

  1079             raise BadRQLQuery('variable %s should be selected by the subquery'

  1080                               % variable.name)

  1081         try:

  1082             sql = self._varmap['%s.%s' % (linkedvar.name, rel.r_type)]

  1083         except KeyError:

  1084             linkedvar.accept(self)            

  1085             sql = '%s.%s' % (linkedvar._q_sqltable, rel.r_type)

  1086         return sql

  1087 

  1088     # tables handling #########################################################

  1089 

  1090     def alias_and_add_table(self, tablename):

  1091         alias = '%s%s' % (tablename, self._state.count)

  1092         self._state.count += 1

  1093         self.add_table('%s AS %s' % (tablename, alias), alias)

  1094         return alias

  1095         

  1096     def add_table(self, table, key=None, scope=-1):

  1097         if key is None:

  1098             key = table

  1099         if key in self._state.tables:

  1100             return

  1101         self._state.tables[key] = (len(self._state.actual_tables) - 1, table)

  1102         self._state.actual_tables[scope].append(table)

  1103     

  1104     def replace_tables_by_outer_join(self, substitute, lefttable, *tables):

  1105         for table in tables:

  1106             try:

  1107                 scope, alias = self._state.tables[table]

  1108                 self._state.actual_tables[scope].remove(alias)

  1109             except ValueError: # huum, not sure about what should be done here

  1110                 msg = "%s already used in an outer join, don't know what to do!"

  1111                 raise Exception(msg % table)

  1112         try:

  1113             tablealias = self._state.outer_tables[lefttable]

  1114             actualtables = self._state.actual_tables[-1]

  1115         except KeyError:

  1116             tablescope, tablealias = self._state.tables[lefttable]

  1117             actualtables = self._state.actual_tables[tablescope]

  1118         outerjoin = '%s %s' % (tablealias, substitute)

  1119         self._update_outer_tables(lefttable, actualtables, tablealias, outerjoin)

  1120         for table in tables:

  1121             self._state.outer_tables[table] = outerjoin

  1122 

  1123     def add_outer_join_condition(self, var, table, condition):

  1124         try:

  1125             tablealias = self._state.outer_tables[table]

  1126             actualtables = self._state.actual_tables[-1]

  1127         except KeyError:

  1128             for rel in var.stinfo['optrelations']:

  1129                 self.visit_relation(rel)

  1130             assert self._state.outer_tables

  1131             self.add_outer_join_condition(var, table, condition)

  1132             return

  1133         before, after = tablealias.split(' AS %s ' % table, 1)

  1134         beforep, afterp = after.split(')', 1)

  1135         outerjoin = '%s AS %s %s AND %s) %s' % (before, table, beforep,