1 # copyright 2003-2013 LOGILAB S.A. (Paris, FRANCE), all rights reserved.

     2 # contact http://www.logilab.fr/ -- mailto:contact@logilab.fr

     3 #

     4 # This file is part of CubicWeb.

     5 #

     6 # CubicWeb is free software: you can redistribute it and/or modify it under the

     7 # terms of the GNU Lesser General Public License as published by the Free

     8 # Software Foundation, either version 2.1 of the License, or (at your option)

     9 # any later version.

    10 #

    11 # CubicWeb is distributed in the hope that it will be useful, but WITHOUT

    12 # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS

    13 # FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more

    14 # details.

    15 #

    16 # You should have received a copy of the GNU Lesser General Public License along

    17 # with CubicWeb.  If not, see <http://www.gnu.org/licenses/>.

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

    19 

    20 

    21 SQL queries optimization

    22 ~~~~~~~~~~~~~~~~~~~~~~~~

    23 1. CWUser X WHERE X in_group G, G name 'users':

    24 

    25    CWUser is the only subject entity type for the in_group relation,

    26    which allow us to do ::

    27 

    28      SELECT eid_from FROM in_group, CWGroup

    29      WHERE in_group.eid_to = CWGroup.eid_from

    30      AND CWGroup.name = 'users'

    31 

    32 

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

    34 

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

    36       inlined...)

    37 

    38       NOT IMPLEMENTED (and quite hard to implement)

    39 

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

    41 is done according to this information

    42 

    43 cross RDMS note : read `Comparison of different SQL implementations`_

    44 by Troels Arvin. Features SQL ISO Standard, PG, mysql, Oracle, MS SQL, DB2

    45 and Informix.

    46 

    47 .. _Comparison of different SQL implementations: http://www.troels.arvin.dk/db/rdbms

    48 """

    49 

    50 __docformat__ = "restructuredtext en"

    51 

    52 import threading

    53 

    54 from six import PY2

    55 from six.moves import range

    56 

    57 from logilab.database import FunctionDescr, SQL_FUNCTIONS_REGISTRY

    58 

    59 from rql import BadRQLQuery, CoercionError

    60 from rql.utils import common_parent

    61 from rql.stmts import Union, Select

    62 from rql.nodes import (VariableRef, Constant, Function, Variable, Or,

    63                        Not, Comparison, ColumnAlias, Relation, SubQuery)

    64 

    65 from cubicweb import QueryError

    66 from cubicweb.rqlrewrite import cleanup_solutions

    67 from cubicweb.server.sqlutils import SQL_PREFIX

    68 

    69 ColumnAlias._q_invariant = False # avoid to check for ColumnAlias / Variable

    70 

    71 FunctionDescr.source_execute = None

    72 

    73 def default_update_cb_stack(self, stack):

    74     stack.append(self.source_execute)

    75 FunctionDescr.update_cb_stack = default_update_cb_stack

    76 

    77 get_func_descr = SQL_FUNCTIONS_REGISTRY.get_function

    78 

    79 LENGTH = get_func_descr('LENGTH')

    80 def length_source_execute(source, session, value):

    81     return len(value.getvalue())

    82 LENGTH.source_execute = length_source_execute

    83 

    84 def _new_var(select, varname):

    85     newvar = select.get_variable(varname)

    86     if not 'relations' in newvar.stinfo:

    87         # not yet initialized

    88         newvar.prepare_annotation()

    89         newvar.stinfo['scope'] = select

    90         newvar._q_invariant = False

    91         select.selection.append(VariableRef(newvar))

    92     return newvar

    93 

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

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

    96         rschema = schema.rschema(rel.r_type)

    97         if rschema.inlined:

    98             towrap.add( (var, rel) )

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

   100                 newivar = _new_var(newselect, vref.name)

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

   102         elif rschema.final:

   103             towrap.add( (var, rel) )

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

   105                 newivar = _new_var(newselect, vref.name)

   106                 newivar.stinfo['attrvar'] = (var, rel.r_type)

   107 

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

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

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

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

   112     """

   113     modified = False

   114     for varname in tuple(unstable):

   115         var = select.defined_vars[varname]

   116         if not var.stinfo.get('optrelations'):

   117             continue

   118         unstable.remove(varname)

   119         newselect = Select()

   120         myunion = Union()

   121         myunion.append(newselect)

   122         # extract aliases / selection

   123         newvar = _new_var(newselect, var.name)

   124         newselect.selection = [VariableRef(newvar)]

   125         towrap_rels = set()

   126         _fill_to_wrap_rel(var, newselect, towrap_rels, schema)

   127         # extract relations

   128         for var, rel in towrap_rels:

   129             newrel = rel.copy(newselect)

   130             newselect.add_restriction(newrel)

   131             select.remove_node(rel)

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

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

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

   135                 newvar.add_optional_relation(newrel)

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

   137                 var = vref.variable

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

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

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

   141                     var.add_optional_relation(newrel)

   142         if not select.where and not modified:

   143             # oops, generated the same thing as the original select....

   144             # restore original query, else we'll indefinitly loop

   145             for var, rel in towrap_rels:

   146                 select.add_restriction(rel)

   147             continue

   148         modified = True

   149         # extract subquery solutions

   150         mysolutions = [sol.copy() for sol in solutions]

   151         cleanup_solutions(newselect, mysolutions)

   152         newselect.set_possible_types(mysolutions)

   153         # full sub-query

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

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

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

   157     return modified

   158 

   159 def _new_solutions(rqlst, solutions):

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

   161     newsolutions = []

   162     for origsol in solutions:

   163         asol = {}

   164         for vname in rqlst.defined_vars:

   165             asol[vname] = origsol[vname]

   166         if not asol in newsolutions:

   167             newsolutions.append(asol)

   168     return newsolutions

   169 

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

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

   172     different types

   173     """

   174     newsols = _new_solutions(rqlst, solutions)

   175     existssols = {}

   176     unstable = set()

   177     invariants = {}

   178     for vname, var in rqlst.defined_vars.items():

   179         vtype = newsols[0][vname]

   180         if var._q_invariant or vname in varmap:

   181             # remove invariant variable from solutions to remove duplicates

   182             # later, then reinserting a type for the variable even later

   183             for sol in newsols:

   184                 invariants.setdefault(id(sol), {})[vname] = sol.pop(vname)

   185         elif var.scope is not rqlst:

   186             # move apart variables which are in a EXISTS scope and are variating

   187             try:

   188                 thisexistssols, thisexistsvars = existssols[var.scope]

   189             except KeyError:

   190                 thisexistssols = [newsols[0]]

   191                 thisexistsvars = set()

   192                 existssols[var.scope] = thisexistssols, thisexistsvars

   193             for i in range(len(newsols)-1, 0, -1):

   194                 if vtype != newsols[i][vname]:

   195                     thisexistssols.append(newsols.pop(i))

   196                     thisexistsvars.add(vname)

   197         else:

   198             # remember unstable variables

   199             for i in range(1, len(newsols)):

   200                 if vtype != newsols[i][vname]:

   201                     unstable.add(vname)

   202     if invariants:

   203         # filter out duplicates

   204         newsols_ = []

   205         for sol in newsols:

   206             if not sol in newsols_:

   207                 newsols_.append(sol)

   208         newsols = newsols_

   209         # reinsert solutions for invariants

   210         for sol in newsols:

   211             for invvar, vartype in invariants[id(sol)].items():

   212                 sol[invvar] = vartype

   213         for sol in existssols:

   214             try:

   215                 for invvar, vartype in invariants[id(sol)].items():

   216                     sol[invvar] = vartype

   217             except KeyError:

   218                 continue

   219     if len(newsols) > 1:

   220         if rewrite_unstable_outer_join(rqlst, newsols, unstable, schema):

   221             # remove variables extracted to subqueries from solutions

   222             newsols = _new_solutions(rqlst, newsols)

   223     return newsols, existssols, unstable

   224 

   225 def relation_info(relation):

   226     lhs, rhs = relation.get_variable_parts()

   227     try:

   228         lhs = lhs.variable

   229         lhsconst = lhs.stinfo['constnode']

   230     except AttributeError:

   231         lhsconst = lhs

   232         lhs = None

   233     except KeyError:

   234         lhsconst = None # ColumnAlias

   235     try:

   236         rhs = rhs.variable

   237         rhsconst = rhs.stinfo['constnode']

   238     except AttributeError:

   239         rhsconst = rhs

   240         rhs = None

   241     except KeyError:

   242         rhsconst = None # ColumnAlias

   243     return lhs, lhsconst, rhs, rhsconst

   244 

   245 def sort_term_selection(sorts, rqlst, groups):

   246     # XXX beurk

   247     if isinstance(rqlst, list):

   248         def append(term):

   249             rqlst.append(term)

   250         selectionidx = set(str(term) for term in rqlst)

   251     else:

   252         def append(term):

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

   254         selectionidx = set(str(term) for term in rqlst.selection)

   255 

   256     for sortterm in sorts:

   257         term = sortterm.term

   258         if not isinstance(term, Constant) and not str(term) in selectionidx:

   259             selectionidx.add(str(term))

   260             append(term)

   261             if groups:

   262                 for vref in term.iget_nodes(VariableRef):

   263                     if not any(vref.is_equivalent(g) for g in groups):

   264                         groups.append(vref)

   265 

   266 def fix_selection_and_group(rqlst, needwrap, selectsortterms,

   267                             sorts, groups, having):

   268     if selectsortterms and sorts:

   269         sort_term_selection(sorts, rqlst, not needwrap and groups)

   270     groupvrefs = [vref for term in groups for vref in term.iget_nodes(VariableRef)]

   271     if sorts and groups:

   272         # when a query is grouped, ensure sort terms are grouped as well

   273         for sortterm in sorts:

   274             term = sortterm.term

   275             if not (isinstance(term, Constant) or \

   276                     (isinstance(term, Function) and

   277                      get_func_descr(term.name).aggregat)):

   278                 for vref in term.iget_nodes(VariableRef):

   279                     if not any(vref.is_equivalent(group) for group in groupvrefs):

   280                         groups.append(vref)

   281                         groupvrefs.append(vref)

   282     if needwrap and (groups or having):

   283         selectedidx = set(vref.name for term in rqlst.selection

   284                           for vref in term.get_nodes(VariableRef))

   285         if groups:

   286             for vref in groupvrefs:

   287                 if vref.name not in selectedidx:

   288                     selectedidx.add(vref.name)

   289                     rqlst.selection.append(vref)

   290         if having:

   291             for term in having:

   292                 for vref in term.iget_nodes(VariableRef):

   293                     if vref.name not in selectedidx:

   294                         selectedidx.add(vref.name)

   295                         rqlst.selection.append(vref)

   296 

   297 def iter_mapped_var_sels(stmt, variable):

   298     # variable is a Variable or ColumnAlias node mapped to a source side

   299     # callback

   300     if not (len(variable.stinfo['rhsrelations']) <= 1 and # < 1 on column alias

   301             variable.stinfo['selected']):

   302         raise QueryError("can't use %s as a restriction variable"

   303                          % variable.name)

   304     for selectidx in variable.stinfo['selected']:

   305         vrefs = stmt.selection[selectidx].get_nodes(VariableRef)

   306         if len(vrefs) != 1:

   307             raise QueryError()

   308         yield selectidx, vrefs[0]

   309 

   310 def update_source_cb_stack(state, stmt, node, stack):

   311     while True:

   312         node = node.parent

   313         if node is stmt:

   314             break

   315         if not isinstance(node, Function):

   316             raise QueryError()

   317         funcd = get_func_descr(node.name)

   318         if funcd.source_execute is None:

   319             raise QueryError('%s can not be called on mapped attribute'

   320                              % node.name)

   321         state.source_cb_funcs.add(node)

   322         funcd.update_cb_stack(stack)

   323 

   324 

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

   326 

   327 class StateInfo(object):

   328     """this class stores data accumulated during the RQL syntax tree visit

   329     for later SQL generation.

   330 

   331     Attributes related to OUTER JOIN handling

   332     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

   333     * `outer_chains`, list of list of strings. Each list represent a tables

   334       that have to be outer joined together.

   335 

   336     * `outer_tables`, dictionary used as index of tables used in outer join ::

   337 

   338         'table alias': (outertype, [conditions], [chain])

   339 

   340       where:

   341 

   342       * `outertype` is one of None, 'LEFT', 'RIGHT', 'FULL'

   343       * `conditions` is a list of join conditions (string)

   344       * `chain` is a list of table alias (the *outer chain*) in which the key

   345         alias appears

   346 

   347     * `outer_pending` is a dictionary containing some conditions that will have

   348       to be added to the outer join when the table will be turned into an

   349       outerjoin ::

   350 

   351        'table alias': [conditions]

   352     """

   353     def __init__(self, select, existssols, unstablevars):

   354         self.existssols = existssols

   355         self.unstablevars = unstablevars

   356         self.subtables = {}

   357         self.needs_source_cb = None

   358         self.subquery_source_cb = None

   359         self.source_cb_funcs = set()

   360         self.scopes = {select: 0}

   361         self.scope_nodes = []

   362 

   363     def reset(self, solution):

   364         """reset some visit variables"""

   365         self.solution = solution

   366         self.count = 0

   367         self.done = set()

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

   369         self.actual_tables = [[]]

   370         for _, tsql in self.tables.values():

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

   372         self.outer_chains = []

   373         self.outer_tables = {}

   374         self.outer_pending = {}

   375         self.duplicate_switches = []

   376         self.aliases = {}

   377         self.restrictions = []

   378         self._restr_stack = []

   379         self.ignore_varmap = False

   380         self._needs_source_cb = {}

   381 

   382     def merge_source_cbs(self, needs_source_cb):

   383         if self.needs_source_cb is None:

   384             self.needs_source_cb = needs_source_cb

   385         elif needs_source_cb != self.needs_source_cb:

   386             raise QueryError('query fetch some source mapped attribute, some not')

   387 

   388     def finalize_source_cbs(self):

   389         if self.subquery_source_cb is not None:

   390             self.needs_source_cb.update(self.subquery_source_cb)

   391 

   392     def add_restriction(self, restr):

   393         if restr:

   394             self.restrictions.append(restr)

   395 

   396     def iter_exists_sols(self, exists):

   397         if not exists in self.existssols:

   398             yield 1

   399             return

   400         thisexistssols, thisexistsvars = self.existssols[exists]

   401         notdone_outside_vars = set()

   402         # when iterating other solutions inner to an EXISTS subquery, we should

   403         # reset variables which have this exists node as scope at each iteration

   404         for var in exists.stmt.defined_vars.values():

   405             if var.scope is exists:

   406                 thisexistsvars.add(var.name)

   407             elif var.name not in self.done:

   408                 notdone_outside_vars.add(var)

   409         origsol = self.solution

   410         origtables = self.tables

   411         done = self.done

   412         for thisexistssol in thisexistssols:

   413             for vname in self.unstablevars:

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

   415                     break

   416             else:

   417                 self.tables = origtables.copy()

   418                 self.solution = thisexistssol

   419                 yield 1

   420                 # cleanup self.done from stuff specific to exists

   421                 for var in thisexistsvars:

   422                     if var in done:

   423                         done.remove(var)

   424                 for var in list(notdone_outside_vars):

   425                     if var.name in done and var._q_sqltable in self.tables:

   426                         origtables[var._q_sqltable] = self.tables[var._q_sqltable]

   427                         notdone_outside_vars.remove(var)

   428                 for rel in exists.iget_nodes(Relation):

   429                     if rel in done:

   430                         done.remove(rel)

   431         self.solution = origsol

   432         self.tables = origtables

   433 

   434     def push_scope(self, scope_node):

   435         self.scope_nodes.append(scope_node)

   436         self.scopes[scope_node] = len(self.actual_tables)

   437         self.actual_tables.append([])

   438         self._restr_stack.append(self.restrictions)

   439         self.restrictions = []

   440 

   441     def pop_scope(self):

   442         del self.scopes[self.scope_nodes[-1]]

   443         self.scope_nodes.pop()

   444         restrictions = self.restrictions

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

   446         scope = len(self.actual_tables) - 1

   447         # check if we have some outer chain for this scope

   448         matching_chains = []

   449         for chain in self.outer_chains:

   450             for tablealias in chain:

   451                 if self.tables[tablealias][0] < scope:

   452                     # chain belongs to outer scope

   453                     break

   454             else:

   455                 # chain match current scope

   456                 matching_chains.append(chain)

   457         # call to `tables_sql` will pop actual_tables

   458         tables = self.tables_sql(matching_chains)

   459         # cleanup outer join related structure for tables in matching chains

   460         for chain in matching_chains:

   461             self.outer_chains.remove(chain)

   462             for alias in chain:

   463                 del self.outer_tables[alias]

   464         return restrictions, tables

   465 

   466     # tables handling #########################################################

   467 

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

   469         if key is None:

   470             key = table

   471         if key in self.tables:

   472             return

   473         if scope < 0:

   474             scope = len(self.actual_tables) + scope

   475         self.tables[key] = (scope, table)

   476         self.actual_tables[scope].append(table)

   477 

   478     def alias_and_add_table(self, tablename, scope=-1):

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

   480         self.count += 1

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

   482         return alias

   483 

   484     def relation_table(self, relation):

   485         """return the table alias used by the given relation"""

   486         if relation in self.done:

   487             return relation._q_sqltable

   488         rid = 'rel_%s%s' % (relation.r_type, self.count)

   489         # relation's table is belonging to the root scope if it is the principal

   490         # table of one of its variable and that variable belong's to parent

   491         # scope

   492         for varref in relation.iget_nodes(VariableRef):

   493             var = varref.variable

   494             # XXX may have a principal without being invariant for this generation,

   495             #     not sure this is a pb or not

   496             if var.stinfo.get('principal') is relation and var.scope is var.stmt:

   497                 scope = 0

   498                 break

   499         else:

   500             scope = -1

   501         self.count += 1

   502         self.add_table('%s_relation AS %s' % (relation.r_type, rid), rid, scope=scope)

   503         relation._q_sqltable = rid

   504         self.done.add(relation)

   505         return rid

   506 

   507     def fti_table(self, relation, fti_table):

   508         """return the table alias used by the given has_text relation,

   509         `fti_table` being the table name for the plain text index

   510         """

   511         if relation in self.done:

   512             try:

   513                 return relation._q_sqltable

   514             except AttributeError:

   515                 pass

   516         self.done.add(relation)

   517         scope = self.scopes[relation.scope]

   518         alias = self.alias_and_add_table(fti_table, scope=scope)

   519         relation._q_sqltable = alias

   520         return alias

   521 

   522     # outer join handling ######################################################

   523 

   524     def mark_as_used_in_outer_join(self, tablealias, addpending=True):

   525         """Mark table of given alias as used in outer join. This must be called

   526         after `outer_tables[tablealias]` has been initialized.

   527         """

   528         # remove a table from actual_table because it's used in an outer join

   529         # chain

   530         scope, tabledef = self.tables[tablealias]

   531         self.actual_tables[scope].remove(tabledef)

   532         # check if there are some pending outer join condition for this table

   533         if addpending:

   534             try:

   535                 pending_conditions = self.outer_pending.pop(tablealias)

   536             except KeyError:

   537                 pass

   538             else:

   539                 self.outer_tables[tablealias][1].extend(pending_conditions)

   540         else:

   541             assert not tablealias in self.outer_pending

   542 

   543     def add_outer_join_condition(self, tablealias, condition):

   544         try:

   545             outer, conditions, chain = self.outer_tables[tablealias]

   546             conditions.append(condition)

   547         except KeyError:

   548             self.outer_pending.setdefault(tablealias, []).append(condition)

   549 

   550     def replace_tables_by_outer_join(self, leftalias, rightalias,

   551                                      outertype, condition):

   552         """tell we need <leftalias> <outertype> JOIN <rightalias> ON <condition>

   553         """

   554         assert leftalias != rightalias, leftalias

   555         outer_tables = self.outer_tables

   556         louter, lconditions, lchain = outer_tables.get(leftalias,

   557                                                       (None, None, None))

   558         router, rconditions, rchain = outer_tables.get(rightalias,

   559                                                       (None, None, None))

   560         if lchain is None and rchain is None:

   561             # create a new outer chaine

   562             chain = [leftalias, rightalias]

   563             outer_tables[leftalias] = (None, [], chain)

   564             outer_tables[rightalias] = (outertype, [condition], chain)

   565             self.outer_chains.append(chain)

   566             self.mark_as_used_in_outer_join(leftalias, addpending=False)

   567             self.mark_as_used_in_outer_join(rightalias)

   568         elif lchain is None:

   569             # [A > B > C] + [D > A] -> [D > A > B > C]

   570             if rightalias == rchain[0]:

   571                 outer_tables[leftalias] = (None, [], rchain)

   572                 conditions = outer_tables[rightalias][1] + [condition]

   573                 outer_tables[rightalias] = (outertype, conditions, rchain)

   574                 rchain.insert(0, leftalias)

   575             else:

   576                 # [A > B > C] + [D > B] -> [A > B > C < D]

   577                 if outertype == 'LEFT':

   578                     outertype = 'RIGHT'

   579                 outer_tables[leftalias] = (outertype, [condition], rchain)

   580                 rchain.append(leftalias)

   581             self.mark_as_used_in_outer_join(leftalias)

   582         elif rchain is None:

   583             # [A > B > C] + [B > D] -> [A > B > C > D]

   584             outer_tables[rightalias] = (outertype, [condition], lchain)

   585             lchain.append(rightalias)

   586             self.mark_as_used_in_outer_join(rightalias)

   587         elif lchain is rchain:

   588             # already in the same chain, simply check compatibility and append

   589             # the condition if it's ok

   590             lidx = lchain.index(leftalias)

   591             ridx = lchain.index(rightalias)

   592             if (outertype == 'FULL' and router != 'FULL') \

   593                    or (lidx < ridx and router != 'LEFT') \

   594                    or (ridx < lidx and louter != 'RIGHT'):

   595                 raise BadRQLQuery()

   596             # merge conditions

   597             if lidx < ridx:

   598                 rconditions.append(condition)

   599             else:

   600                 lconditions.append(condition)

   601         elif louter is None:

   602             # merge chains

   603             self.outer_chains.remove(lchain)

   604             rchain += lchain

   605             self.mark_as_used_in_outer_join(leftalias)

   606             for alias, (aouter, aconditions, achain) in outer_tables.items():

   607                 if achain is lchain:

   608                     outer_tables[alias] = (aouter, aconditions, rchain)

   609         else:

   610             raise BadRQLQuery()

   611 

   612     # sql generation helpers ###################################################

   613 

   614     def tables_sql(self, outer_chains=None):

   615         """generate SQL for FROM clause"""

   616         # sort for test predictability

   617         tables = sorted(self.actual_tables.pop())

   618         # process outer joins

   619         if outer_chains is None:

   620             assert not self.actual_tables, self.actual_tables

   621             assert not self.outer_pending

   622             outer_chains = self.outer_chains

   623         for chain in sorted(outer_chains):

   624             tablealias = chain[0]

   625             outertype, conditions, _ = self.outer_tables[tablealias]

   626             assert _ is chain, (chain, _)

   627             assert outertype is None, (chain, self.outer_chains)

   628             assert not conditions, (chain, self.outer_chains)

   629             assert len(chain) > 1

   630             tabledef = self.tables[tablealias][1]

   631             outerjoin = [tabledef]

   632             for tablealias in chain[1:]:

   633                 outertype, conditions, _ = self.outer_tables[tablealias]

   634                 assert _ is chain, (chain, self.outer_chains)

   635                 assert outertype in ('LEFT', 'RIGHT', 'FULL'), (

   636                     tablealias, outertype, conditions)

   637                 assert isinstance(conditions, (list)), (

   638                     tablealias, outertype, conditions)

   639                 tabledef = self.tables[tablealias][1]

   640                 outerjoin.append('%s OUTER JOIN %s ON (%s)' % (

   641                     outertype, tabledef, ' AND '.join(conditions)))

   642             tables.append(' '.join(outerjoin))

   643         return ', '.join(tables)

   644 

   645 

   646 def extract_fake_having_terms(having):

   647     """RQL's HAVING may be used to contains stuff that should go in the WHERE

   648     clause of the SQL query, due to RQL grammar limitation. Split them...

   649 

   650     Return a list nodes that can be ANDed with query's WHERE clause. Having

   651     subtrees updated in place.

   652     """

   653     fakehaving = []

   654     for subtree in having:

   655         ors, tocheck = set(), []

   656         for compnode in subtree.get_nodes(Comparison):

   657             for fnode in compnode.get_nodes(Function):

   658                 if fnode.descr().aggregat:

   659                     p = compnode.parent

   660                     oor = None

   661                     while not isinstance(p, Select):

   662                         if isinstance(p, (Or, Not)):

   663                             oor = p

   664                         p = p.parent

   665                     if oor is not None:

   666                         ors.add(oor)

   667                     break

   668             else:

   669                 tocheck.append(compnode)

   670         # tocheck hold a set of comparison not implying an aggregat function

   671         # put them in fakehaving if they don't share an Or node as ancestor

   672         # with another comparison containing an aggregat function

   673         for compnode in tocheck:

   674             parents = set()

   675             p = compnode.parent

   676             oor = None

   677             while not isinstance(p, Select):

   678                 if p in ors or p is None: # p is None for nodes already in fakehaving

   679                     break

   680                 if isinstance(p, (Or, Not)):

   681                     oor = p

   682                 p = p.parent

   683             else:

   684                 node = oor or compnode

   685                 fakehaving.append(node)

   686                 node.parent.remove(node)

   687     return fakehaving

   688 

   689 

   690 class SQLGenerator(object):

   691     """

   692     generation of SQL from the fully expanded RQL syntax tree

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

   694 

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

   696     this level (see cubicweb.server.querier)

   697 

   698     we should not have errors here!

   699 

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

   701     protected by a lock

   702     """

   703 

   704     def __init__(self, schema, dbhelper, attrmap=None):

   705         self.schema = schema

   706         self.dbhelper = dbhelper

   707         self.dbencoding = dbhelper.dbencoding

   708         self.keyword_map = {'NOW' : self.dbhelper.sql_current_timestamp,

   709                             'TODAY': self.dbhelper.sql_current_date,

   710                             }

   711         if not self.dbhelper.union_parentheses_support:

   712             self.union_sql = self.noparen_union_sql

   713         self._lock = threading.Lock()

   714         if attrmap is None:

   715             attrmap = {}

   716         self.attr_map = attrmap

   717 

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

   719         """return SQL queries and a variable dictionary from a RQL syntax tree

   720 

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

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

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

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

   725 

   726         return an sql string and a dictionary with substitutions values

   727         """

   728         if args is None:

   729             args = {}

   730         if varmap is None:

   731             varmap =  {}

   732         self._lock.acquire()

   733         self._args = args

   734         self._varmap = varmap

   735         self._query_attrs = {}

   736         self._state = None

   737         # self._not_scope_offset = 0

   738         try:

   739             # union query for each rqlst / solution

   740             sql = self.union_sql(union)

   741             # we are done

   742             return sql, self._query_attrs, self._state.needs_source_cb

   743         finally:

   744             self._lock.release()

   745 

   746     def union_sql(self, union, needalias=False): # pylint: disable=E0202

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

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

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

   750                 for select in union.children)

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

   752 

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

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

   755         # query. This may cause bug in some condition (sort in one of the

   756         # subquery) but will work in most case

   757         #

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

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

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

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

   762 

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

   764         """return SQL queries and a variable dictionary from a RQL syntax tree

   765 

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

   767         :solution: a dictionary containing variables binding.

   768           A solution's dictionary has variable's names as key and variable's

   769           types as values

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

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

   772         """

   773         if select.distinct:

   774             distinct = True

   775         elif self.dbhelper.fti_need_distinct:

   776             distinct = getattr(select.parent, 'has_text_query', False)

   777         else:

   778             distinct = False

   779         sorts = select.orderby

   780         groups = select.groupby

   781         having = select.having

   782         for restr in extract_fake_having_terms(having):

   783             scope = None

   784             for vref in restr.get_nodes(VariableRef):

   785                 vscope = vref.variable.scope

   786                 if vscope is select:

   787                     continue # ignore select scope, so restriction is added to

   788                              # the inner most scope possible

   789                 if scope is None:

   790                     scope = vscope

   791                 elif vscope is not scope:

   792                     scope = common_parent(scope, vscope).scope

   793             if scope is None:

   794                 scope = select

   795             scope.add_restriction(restr)

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

   797         origselection = select.selection[:]

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

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

   800         needwrap = False

   801         sols = select.solutions

   802         selectsortterms = distinct

   803         if len(sols) > 1:

   804             # remove invariant from solutions

   805             sols, existssols, unstable = remove_unused_solutions(

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

   807             if len(sols) > 1:

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

   809                 # generated and so sort terms have to be selected

   810                 selectsortterms = True

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

   812                 # query will be necessary

   813                 if groups or select.has_aggregat:

   814                     select.select_only_variables()

   815                     needwrap = True

   816         else:

   817             existssols, unstable = {}, ()

   818         state = StateInfo(select, existssols, unstable)

   819         if self._state is not None:

   820             # state from a previous unioned select

   821             state.merge_source_cbs(self._state.needs_source_cb)

   822         # treat subqueries

   823         self._subqueries_sql(select, state)

   824         # generate sql for this select node

   825         if needwrap:

   826             outerselection = origselection[:]

   827             if sorts and selectsortterms:

   828                 if distinct:

   829                     sort_term_selection(sorts, outerselection, groups)

   830         fix_selection_and_group(select, needwrap, selectsortterms,

   831                                 sorts, groups, having)

   832         if needwrap:

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

   834         else:

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

   836         if fneedwrap:

   837             needalias = True

   838         self._in_wrapping_query = False

   839         self._state = state

   840         try:

   841             sql = self._solutions_sql(select, sols, distinct,

   842                                       needalias or needwrap)

   843             # generate groups / having before wrapping query selection to get

   844             # correct column aliases

   845             self._in_wrapping_query = needwrap

   846             if groups:

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

   848                 # will interpret it as a positional index in the selection

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

   850                                   if not isinstance(vref, Constant))

   851             if having:

   852                 # filter out constants as for GROUP BY

   853                 having = ' AND '.join(term.accept(self) for term in having

   854                                       if not isinstance(term, Constant))

   855             if needwrap:

   856                 sql = '%s FROM (%s) AS T1' % (

   857                     self._selection_sql(outerselection, distinct,needalias),

   858                     sql)

   859             if groups:

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

   861             if having:

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

   863             # sort

   864             if sorts:

   865                 sqlsortterms = []

   866                 if needwrap:

   867                     selectidx = [str(term) for term in outerselection]

   868                 else:

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

   870                 for sortterm in sorts:

   871                     _term = self._sortterm_sql(sortterm, selectidx)

   872                     if _term is not None:

   873                         sqlsortterms.append(_term)

   874                 if sqlsortterms:

   875                     sql = self.dbhelper.sql_add_order_by(

   876                         sql, sqlsortterms, origselection, fneedwrap,

   877                         select.limit or select.offset)

   878             else:

   879                 sqlsortterms = None

   880             state.finalize_source_cbs()

   881         finally:

   882             select.selection = origselection

   883         # limit / offset

   884         sql = self.dbhelper.sql_add_limit_offset(sql,

   885                                                  select.limit,

   886                                                  select.offset,

   887                                                  sqlsortterms)

   888         return sql

   889 

   890     def _subqueries_sql(self, select, state):

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

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

   893             tablealias = '_T%s' % i # XXX nested subqueries

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

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

   896             latest_state = self._state

   897             for vref in subquery.aliases:

   898                 alias = vref.variable

   899                 alias._q_sqltable = tablealias

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

   901                 try:

   902                     stack = latest_state.needs_source_cb[alias.colnum]

   903                     if state.subquery_source_cb is None:

   904                         state.subquery_source_cb = {}

   905                     for selectidx, vref in iter_mapped_var_sels(select, alias):

   906                         stack = stack[:]

   907                         update_source_cb_stack(state, select, vref, stack)

   908                         state.subquery_source_cb[selectidx] = stack

   909                 except KeyError:

   910                     continue

   911 

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

   913         sqls = []

   914         for solution in solutions:

   915             self._state.reset(solution)

   916             # visit restriction subtree

   917             if select.where is not None:

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

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

   920             if self._state.restrictions:

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

   922             self._state.merge_source_cbs(self._state._needs_source_cb)

   923             # add required tables

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

   925             tables = self._state.tables_sql()

   926             if tables:

   927                 sql.insert(1, 'FROM %s' % tables)

   928             elif self._state.restrictions and self.dbhelper.needs_from_clause:

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

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

   931         if distinct:

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

   933         else:

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

   935 

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

   937         clause = []

   938         for term in selected:

   939             sql = term.accept(self)

   940             if needaliasing:

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

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

   943                 if isinstance(term, VariableRef):

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

   945             else:

   946                 clause.append(sql)

   947         if distinct:

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

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

   950 

   951     def _sortterm_sql(self, sortterm, selectidx):

   952         term = sortterm.term

   953         try:

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

   955         except ValueError:

   956             # Constant node or non selected term

   957             sqlterm = term.accept(self)

   958             if sqlterm is None:

   959                 return None

   960         if sortterm.asc:

   961             return str(sqlterm)

   962         else:

   963             return '%s DESC' % sqlterm

   964 

   965     def visit_and(self, et):

   966         """generate SQL for a AND subtree"""

   967         res = []

   968         for c in et.children:

   969             part = c.accept(self)

   970             if part:

   971                 res.append(part)

   972         return ' AND '.join(res)

   973 

   974     def visit_or(self, ou):

   975         """generate SQL for a OR subtree"""

   976         res = []

   977         for c in ou.children:

   978             part = c.accept(self)

   979             if part:

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

   981         if res:

   982             if len(res) > 1:

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

   984             return res[0]

   985         return ''

   986 

   987     def visit_not(self, node):

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

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

   990             # already processed or no sql generated by children

   991             return csql

   992         return 'NOT (%s)' % csql

   993 

   994     def visit_exists(self, exists):

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

   996         sqls = []

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

   998             sql = self._visit_exists(exists)

   999             if sql:

  1000                 sqls.append(sql)

  1001         if not sqls:

  1002             return ''

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

  1004 

  1005     def _visit_exists(self, exists):

  1006         self._state.push_scope(exists)

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

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

  1009         if restriction:

  1010             restrictions.append(restriction)

  1011         restriction = ' AND '.join(restrictions)

  1012         if not restriction:

  1013             if tables:

  1014                 return 'SELECT 1 FROM %s' % tables

  1015             return ''

  1016         if not tables:

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

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

  1019         else:

  1020             sql = 'SELECT 1 FROM %s WHERE %s' % (tables, restriction)

  1021         return sql

  1022 

  1023 

  1024     def visit_relation(self, relation):

  1025         """generate SQL for a relation"""

  1026         rtype = relation.r_type

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

  1028         if relation.is_types_restriction():

  1029             return ''

  1030         lhs, rhs = relation.get_parts()

  1031         rschema = self.schema.rschema(rtype)

  1032         if rschema.final:

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

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

  1035                 # special case where this restriction is already generated by

  1036                 # some other relation

  1037                 return ''

  1038             # attribute relation

  1039             if rtype == 'has_text':

  1040                 sql = self._visit_has_text_relation(relation)

  1041             else:

  1042                 rhs_vars = rhs.get_nodes(VariableRef)

  1043                 if rhs_vars:

  1044                     # if variable(s) in the RHS

  1045                     sql = self._visit_var_attr_relation(relation, rhs_vars)

  1046                 else:

  1047                     # no variables in the RHS

  1048                     sql = self._visit_attribute_relation(relation)

  1049         elif (rtype == 'is' and isinstance(rhs.children[0], Constant)

  1050               and rhs.children[0].eval(self._args) is None):

  1051             # special case "C is NULL"

  1052             if lhs.name in self._varmap:

  1053                 lhssql = self._varmap[lhs.name]

  1054             else:

  1055                 lhssql = lhs.accept(self)

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

  1057         elif '%s.%s' % (lhs, relation.r_type) in self._varmap:

  1058             # relation has already been processed by a previous step

  1059             return ''

  1060         elif relation.optional:

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

  1062             if rtype == 'identity' or rschema.inlined:

  1063                 sql = self._visit_outer_join_inlined_relation(relation, rschema)

  1064             else:

  1065                 sql = self._visit_outer_join_relation(relation, rschema)

  1066         elif rschema.inlined:

  1067             sql = self._visit_inlined_relation(relation)

  1068         else:

  1069             # regular (non final) relation

  1070             sql = self._visit_relation(relation, rschema)

  1071         return sql

  1072 

  1073     def _visit_inlined_relation(self, relation):

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

  1075         # we are sure lhsvar is not None

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

  1077         if rhsvar is None:

  1078             moresql = None

  1079         else:

  1080             moresql = self._extra_join_sql(relation, lhssql, rhsvar)

  1081         if isinstance(relation.parent, Not):

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

  1083             if rhsvar is not None and rhsvar._q_invariant:

  1084                 sql = '%s IS NULL' % lhssql

  1085             else:

  1086                 # column != 1234 may not get back rows where column is NULL...

  1087                 sql = '(%s IS NULL OR %s!=%s)' % (

  1088                     lhssql, lhssql, (rhsvar or rhsconst).accept(self))

  1089         elif rhsconst is not None:

  1090             sql = '%s=%s' % (lhssql, rhsconst.accept(self))

  1091         elif isinstance(rhsvar, Variable) and rhsvar._q_invariant and \

  1092                  not rhsvar.name in self._varmap:

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

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

  1095             # relation

  1096             if moresql is not None:

  1097                 return moresql

  1098             return '%s IS NOT NULL' % lhssql

  1099         else:

  1100             sql = '%s=%s' % (lhssql, rhsvar.accept(self))

  1101         if moresql is None:

  1102             return sql

  1103         return '%s AND %s' % (sql, moresql)

  1104 

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

  1106         if termconst or not termvar._q_invariant:

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

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

  1109         elif termvar._q_invariant:

  1110             # if the variable is mapped, generate restriction anyway

  1111             if termvar.name in self._varmap:

  1112                 termsql = termvar.accept(self)

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

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

  1115             if extrajoin is not None:

  1116                 yield extrajoin

  1117 

  1118     def _visit_relation(self, relation, rschema):

  1119         """generate SQL for a relation

  1120 

  1121         implements optimization 1.

  1122         """

  1123         if relation.r_type == 'identity':

  1124             # special case "X identity Y"

  1125             lhs, rhs = relation.get_parts()

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

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

  1128         rid = self._state.relation_table(relation)

  1129         sqls = []

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

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

  1132         sql = ' AND '.join(sqls)

  1133         return sql

  1134 

  1135     def _visit_outer_join_relation(self, relation, rschema):