[repo, ms] fix planning of some queries where variable 'non-invarianess' should be considered, leading for instance to junk in entities table on source deletion
# copyright 2003-2011 LOGILAB S.A. (Paris, FRANCE), all rights reserved.
# contact http://www.logilab.fr/ -- mailto:contact@logilab.fr
#
# This file is part of CubicWeb.
#
# CubicWeb is free software: you can redistribute it and/or modify it under the
# terms of the GNU Lesser General Public License as published by the Free
# Software Foundation, either version 2.1 of the License, or (at your option)
# any later version.
#
# CubicWeb is distributed in the hope that it will be useful, but WITHOUT
# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
# FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
# details.
#
# You should have received a copy of the GNU Lesser General Public License along
# with CubicWeb. If not, see <http://www.gnu.org/licenses/>.
"""Functions to add additional annotations on a rql syntax tree to ease later
code generation.
"""
__docformat__ = "restructuredtext en"
from logilab.common.compat import any
from rql import BadRQLQuery
from rql.nodes import Relation, VariableRef, Constant, Variable, Or, Exists
from rql.utils import common_parent
def _annotate_select(annotator, rqlst):
for subquery in rqlst.with_:
annotator._annotate_union(subquery.query)
#if server.DEBUG:
# print '-------- sql annotate', repr(rqlst)
getrschema = annotator.schema.rschema
has_text_query = False
need_distinct = rqlst.distinct
for rel in rqlst.iget_nodes(Relation):
if getrschema(rel.r_type).symmetric and not isinstance(rel.parent, Exists):
for vref in rel.iget_nodes(VariableRef):
stinfo = vref.variable.stinfo
if not stinfo['constnode'] and stinfo['selected']:
need_distinct = True
# XXX could mark as not invariant
break
for var in rqlst.defined_vars.itervalues():
stinfo = var.stinfo
if stinfo.get('ftirels'):
has_text_query = True
if stinfo['attrvar']:
stinfo['invariant'] = False
stinfo['principal'] = _select_main_var(stinfo['rhsrelations'])
continue
if not stinfo['relations'] and stinfo['typerel'] is None:
# Any X, Any MAX(X)...
# those particular queries should be executed using the system
# entities table unless there is some type restriction
stinfo['invariant'] = True
stinfo['principal'] = None
continue
if any(rel for rel in stinfo['relations'] if rel.r_type == 'eid' and rel.operator() != '=') and \
not any(r for r in var.stinfo['relations'] - var.stinfo['rhsrelations']
if r.r_type != 'eid' and (getrschema(r.r_type).inlined or getrschema(r.r_type).final)):
# Any X WHERE X eid > 2
# those particular queries should be executed using the system entities table
stinfo['invariant'] = True
stinfo['principal'] = None
continue
if stinfo['selected'] and var.valuable_references() == 1+bool(stinfo['constnode']):
# "Any X", "Any X, Y WHERE X attr Y"
stinfo['invariant'] = False
continue
joins = set()
invariant = False
for ref in var.references():
rel = ref.relation()
if rel is None or rel.is_types_restriction():
continue
lhs, rhs = rel.get_parts()
onlhs = ref is lhs
role = 'subject' if onlhs else 'object'
if rel.r_type == 'eid':
if not (onlhs and len(stinfo['relations']) > 1):
break
if not stinfo['constnode']:
joins.add( (rel, role) )
continue
elif rel.r_type == 'identity':
# identity can't be used as principal, so check other relation are used
# XXX explain rhs.operator == '='
if rhs.operator != '=' or len(stinfo['relations']) <= 1: #(stinfo['constnode'] and rhs.operator == '='):
break
joins.add( (rel, role) )
continue
rschema = getrschema(rel.r_type)
if rel.optional:
if rel in stinfo.get('optrelations', ()):
# optional variable can't be invariant if this is the lhs
# variable of an inlined relation
if not rel in stinfo['rhsrelations'] and rschema.inlined:
break
# variable used as main variable of an optional relation can't
# be invariant, unless we can use some other relation as
# reference for the outer join
elif not stinfo['constnode']:
break
elif len(stinfo['relations']) == 2:
if onlhs:
ostinfo = rhs.children[0].variable.stinfo
else:
ostinfo = lhs.variable.stinfo
if not any(orel for orel in ostinfo['relations']
if orel.optional and orel is not rel):
break
if rschema.final or (onlhs and rschema.inlined):
if rschema.type != 'has_text':
# need join anyway if the variable appears in a final or
# inlined relation
break
joins.add( (rel, role) )
continue
if not stinfo['constnode']:
if rschema.inlined and rel.neged(strict=True):
# if relation is inlined, can't be invariant if that
# variable is used anywhere else.
# see 'Any P WHERE NOT N ecrit_par P, N eid 512':
# sql for 'NOT N ecrit_par P' is 'N.ecrit_par is NULL' so P
# can use N.ecrit_par as principal
if (stinfo['selected'] or len(stinfo['relations']) > 1):
break
elif rschema.symmetric and stinfo['selected']:
break
joins.add( (rel, role) )
else:
# if there is at least one ambigous relation and no other to
# restrict types, can't be invariant since we need to filter out
# other types
if not annotator.is_ambiguous(var):
invariant = True
stinfo['invariant'] = invariant
if invariant and joins:
# remember rqlst/solutions analyze information
# we have to select a kindof "main" relation which will "extrajoins"
# the other
# priority should be given to relation which are not in inner queries
# (eg exists)
try:
stinfo['principal'] = principal = _select_principal(var.scope, joins)
if getrschema(principal.r_type).inlined:
# the scope of the lhs variable must be equal or outer to the
# rhs variable's scope (since it's retrieved from lhs's table)
sstinfo = principal.children[0].variable.stinfo
sstinfo['scope'] = common_parent(sstinfo['scope'], stinfo['scope']).scope
except CantSelectPrincipal:
stinfo['invariant'] = False
rqlst.need_distinct = need_distinct
return has_text_query
class CantSelectPrincipal(Exception):
"""raised when no 'principal' variable can be found"""
def _select_principal(scope, relations, _sort=lambda x:x):
"""given a list of rqlst relations, select one which will be used to
represent an invariant variable (e.g. using on extremity of the relation
instead of the variable's type table
"""
# _sort argument is there for test
diffscope_rels = {}
ored_rels = set()
diffscope_rels = set()
for rel, role in _sort(relations):
# note: only eid and has_text among all final relations may be there
if rel.r_type in ('eid', 'identity'):
continue
if rel.optional is not None and len(relations) > 1:
if role == 'subject' and rel.optional == 'right':
continue
if role == 'object' and rel.optional == 'left':
continue
if rel.ored(traverse_scope=True):
ored_rels.add(rel)
elif rel.scope is scope:
return rel
elif not rel.neged(traverse_scope=True):
diffscope_rels.add(rel)
if len(ored_rels) > 1:
ored_rels_copy = tuple(ored_rels)
for rel1 in ored_rels_copy:
for rel2 in ored_rels_copy:
if rel1 is rel2:
continue
if isinstance(common_parent(rel1, rel2), Or):
ored_rels.discard(rel1)
ored_rels.discard(rel2)
for rel in _sort(ored_rels):
if rel.scope is scope:
return rel
diffscope_rels.add(rel)
# if DISTINCT query, can use variable from a different scope as principal
# since introduced duplicates will be removed
if scope.stmt.distinct and diffscope_rels:
return iter(_sort(diffscope_rels)).next()
# XXX could use a relation from a different scope if it can't generate
# duplicates, so we should have to check cardinality
raise CantSelectPrincipal()
def _select_main_var(relations):
"""given a list of rqlst relations, select one which will be used as main
relation for the rhs variable
"""
principal = None
# sort for test predictability
for rel in sorted(relations, key=lambda x: (x.children[0].name, x.r_type)):
# only equality relation with a variable as rhs may be principal
if rel.operator() not in ('=', 'IS') \
or not isinstance(rel.children[1].children[0], VariableRef) or rel.neged(strict=True):
continue
if rel.scope is rel.stmt:
return rel
principal = rel
if principal is None:
raise BadRQLQuery('unable to find principal in %s' % ', '.join(
r.as_string() for r in relations))
return principal
def set_qdata(getrschema, union, noinvariant):
"""recursive function to set querier data on variables in the syntax tree
"""
for select in union.children:
for subquery in select.with_:
set_qdata(getrschema, subquery.query, noinvariant)
for var in select.defined_vars.itervalues():
if var.stinfo['invariant']:
if var in noinvariant and not var.stinfo['principal'].r_type == 'has_text':
var._q_invariant = False
else:
var._q_invariant = True
else:
var._q_invariant = False
class SQLGenAnnotator(object):
def __init__(self, schema):
self.schema = schema
self.nfdomain = frozenset(eschema.type for eschema in schema.entities()
if not eschema.final)
def annotate(self, rqlst):
"""add information to the rql syntax tree to help sources to do their
job (read sql generation)
a variable is tagged as invariant if:
* it's a non final variable
* it's not used as lhs in any final or inlined relation
* there is no type restriction on this variable (either explicit in the
syntax tree or because a solution for this variable has been removed
due to security filtering)
"""
#assert rqlst.TYPE == 'select', rqlst
rqlst.has_text_query = self._annotate_union(rqlst)
def _annotate_union(self, union):
has_text_query = False
for select in union.children:
htq = _annotate_select(self, select)
if htq:
has_text_query = True
return has_text_query
def is_ambiguous(self, var):
# ignore has_text relation when we know it will be used as principal.
# This is expected by the rql2sql generator which will use the `entities`
# table to filter out by type if necessary, This optimisation is very
# interesting in multi-sources cases, as it may avoid a costly query
# on sources to get all entities of a given type to achieve this, while
# we have all the necessary information.
root = var.stmt.root # Union node
# rel.scope -> Select or Exists node, so add .parent to get Union from
# Select node
rels = [rel for rel in var.stinfo['relations'] if rel.scope.parent is root]
if len(rels) == 1 and rels[0].r_type == 'has_text':
return False
try:
data = var.stmt._deamb_data
except AttributeError:
data = var.stmt._deamb_data = IsAmbData(self.schema, self.nfdomain)
data.compute(var.stmt)
return data.is_ambiguous(var)
class IsAmbData(object):
def __init__(self, schema, nfdomain):
self.schema = schema
# shortcuts
self.rschema = schema.rschema
self.eschema = schema.eschema
# domain for non final variables
self.nfdomain = nfdomain
# {var: possible solutions set}
self.varsols = {}
# set of ambiguous variables
self.ambiguousvars = set()
# remember if a variable has been deambiguified by another to avoid
# doing the opposite
self.deambification_map = {}
# not invariant variables (access to final.inlined relation)
self.not_invariants = set()
def is_ambiguous(self, var):
return var in self.ambiguousvars
def restrict(self, var, restricted_domain):
self.varsols[var] &= restricted_domain
if var in self.ambiguousvars and self.varsols[var] == var.stinfo['possibletypes']:
self.ambiguousvars.remove(var)
def compute(self, rqlst):
# set domains for each variable
for varname, var in rqlst.defined_vars.iteritems():
if var.stinfo['uidrel'] is not None or \
self.eschema(rqlst.solutions[0][varname]).final:
ptypes = var.stinfo['possibletypes']
else:
ptypes = set(self.nfdomain)
self.ambiguousvars.add(var)
self.varsols[var] = ptypes
if not self.ambiguousvars:
return
# apply relation restriction
self.maydeambrels = maydeambrels = {}
for rel in rqlst.iget_nodes(Relation):
if rel.r_type == 'eid' or rel.is_types_restriction():
continue
lhs, rhs = rel.get_variable_parts()
if isinstance(lhs, VariableRef) or isinstance(rhs, VariableRef):
rschema = self.rschema(rel.r_type)
if rschema.inlined or rschema.final:
self.not_invariants.add(lhs.variable)
self.set_rel_constraint(lhs, rel, rschema.subjects)
self.set_rel_constraint(rhs, rel, rschema.objects)
# try to deambiguify more variables by considering other variables'type
modified = True
while modified and self.ambiguousvars:
modified = False
for var in self.ambiguousvars.copy():
try:
for rel in (var.stinfo['relations'] & maydeambrels[var]):
if self.deambiguifying_relation(var, rel):
modified = True
break
except KeyError:
# no relation to deambiguify
continue
def _debug_print(self):
print 'varsols', dict((x, sorted(str(v) for v in values))
for x, values in self.varsols.iteritems())
print 'ambiguous vars', sorted(self.ambiguousvars)
def set_rel_constraint(self, term, rel, etypes_func):
if isinstance(term, VariableRef) and self.is_ambiguous(term.variable):
var = term.variable
if len(var.stinfo['relations']) == 1 \
or rel.scope is var.scope or rel.r_type == 'identity':
self.restrict(var, frozenset(etypes_func()))
try:
self.maydeambrels[var].add(rel)
except KeyError:
self.maydeambrels[var] = set((rel,))
def deambiguifying_relation(self, var, rel):
lhs, rhs = rel.get_variable_parts()
onlhs = var is getattr(lhs, 'variable', None)
other = onlhs and rhs or lhs
otheretypes = None
# XXX isinstance(other.variable, Variable) to skip column alias
if isinstance(other, VariableRef) and isinstance(other.variable, Variable):
deambiguifier = other.variable
if not var is self.deambification_map.get(deambiguifier):
if var.stinfo['typerel'] is None:
otheretypes = deambiguifier.stinfo['possibletypes']
elif not self.is_ambiguous(deambiguifier):
otheretypes = self.varsols[deambiguifier]
elif deambiguifier in self.not_invariants:
# we know variable won't be invariant, try to use
# it to deambguify the current variable
otheretypes = self.varsols[deambiguifier]
if deambiguifier.stinfo['typerel'] is None:
# if deambiguifier has no type restriction using 'is',
# don't record it
deambiguifier = None
elif isinstance(other, Constant) and other.uidtype:
otheretypes = (other.uidtype,)
deambiguifier = None
if otheretypes is not None:
# to restrict, we must check that for all type in othertypes,
# possible types on the other end of the relation are matching
# variable's possible types
rschema = self.rschema(rel.r_type)
if onlhs:
rtypefunc = rschema.subjects
else:
rtypefunc = rschema.objects
for otheretype in otheretypes:
reltypes = frozenset(rtypefunc(otheretype))
if var.stinfo['possibletypes'] != reltypes:
return False
self.restrict(var, var.stinfo['possibletypes'])
self.deambification_map[var] = deambiguifier
return True
return False