# 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/>.

"""plan execution of rql queries on multiple sources

the best way to understand what are we trying to acheive here is to read the

unit-tests in unittest_msplanner.py

What you need to know

~~~~~~~~~~~~~~~~~~~~~

1. The system source is expected  to support every entity and relation types

2. Given "X relation Y":

   * if relation, X and Y types are supported by the external source, we suppose

     by default that X and Y should both come from the same source as the

     relation. You can specify otherwise by adding relation into the

     "cross_relations" set in the source's mapping file and it that case, we'll

     consider that we can also find in the system source some relation between

     X and Y coming from different sources.

   * if "relation" isn't supported by the external source but X or Y

     types (or both) are, we suppose by default that can find in the system

     source some relation where X and/or Y come from the external source. You

     can specify otherwise by adding relation into the "dont_cross_relations"

     set in the source's mapping file and it that case, we'll consider that we

     can only find in the system source some relation between X and Y coming

     the system source.

Implementation

~~~~~~~~~~~~~~

XXX explain algorithm

Exemples of multi-sources query execution

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

For a system source and a ldap user source (only CWUser and its attributes

is supported, no group or such):

:CWUser X:

1. fetch CWUser X from both sources and return concatenation of results

:CWUser X WHERE X in_group G, G name 'users':

* catch 1

  1. fetch CWUser X from both sources, store concatenation of results into a

     temporary table

  2. return the result of TMP X WHERE X in_group G, G name 'users' from the

     system source

* catch 2

  1. return the result of CWUser X WHERE X in_group G, G name 'users' from system

     source, that's enough (optimization of the sql querier will avoid join on

     CWUser, so we will directly get local eids)

:CWUser X,L WHERE X in_group G, X login L, G name 'users':

1. fetch Any X,L WHERE X is CWUser, X login L from both sources, store

   concatenation of results into a temporary table

2. return the result of Any X, L WHERE X is TMP, X login LX in_group G,

   G name 'users' from the system source

:Any X WHERE X owned_by Y:

* catch 1

  1. fetch CWUser X from both sources, store concatenation of results into a

     temporary table

  2. return the result of Any X WHERE X owned_by Y, Y is TMP from the system

     source

* catch 2

  1. return the result of Any X WHERE X owned_by Y from system source, that's

     enough (optimization of the sql querier will avoid join on CWUser, so we

     will directly get local eids)

"""

__docformat__ = "restructuredtext en"

from itertools import imap, ifilterfalse

from logilab.common.compat import any

from logilab.common.decorators import cached

from rql import BadRQLQuery

from rql.stmts import Union, Select

from rql.nodes import (VariableRef, Comparison, Relation, Constant, Variable,

                       Not, Exists, SortTerm, Function)

from cubicweb import server

from cubicweb.utils import make_uid

from cubicweb.rqlrewrite import add_types_restriction, cleanup_solutions

from cubicweb.server.ssplanner import SSPlanner, OneFetchStep

from cubicweb.server.mssteps import *

Variable._ms_table_key = lambda x: x.name

Relation._ms_table_key = lambda x: x.r_type

# str() Constant.value to ensure generated table name won't be unicode

Constant._ms_table_key = lambda x: str(x.value)

Variable._ms_may_be_processed = lambda x, terms, linkedterms: any(

    t for t in terms if t in linkedterms.get(x, ()))

Relation._ms_may_be_processed = lambda x, terms, linkedterms: all(

    getattr(hs, 'variable', hs) in terms for hs in x.get_variable_parts())

def ms_scope(term):

    rel = None

    scope = term.scope

    if isinstance(term, Variable) and len(term.stinfo['relations']) == 1:

        rel = iter(term.stinfo['relations']).next().relation()

    elif isinstance(term, Constant):

        rel = term.relation()

    elif isinstance(term, Relation):

        rel = term

    if rel is not None and (

        rel.r_type != 'identity' and rel.scope is scope

        and isinstance(rel.parent, Exists) and rel.parent.neged(strict=True)):

        return scope.parent.scope

    return scope

def need_intersect(select, getrschema):

    for rel in select.iget_nodes(Relation):

        if isinstance(rel.parent, Exists) and rel.parent.neged(strict=True) and not rel.is_types_restriction():

            rschema = getrschema(rel.r_type)

            if not rschema.final:

                # if one of the relation's variable is ambiguous but not

                # invariant, an intersection will be necessary

                for vref in rel.get_nodes(VariableRef):

                    var = vref.variable

                    if (var.valuable_references() == 1

                        and len(var.stinfo['possibletypes']) > 1):

                        return True

    return False

def neged_relation(rel):

    parent = rel.parent

    return isinstance(parent, Not) or (isinstance(parent, Exists) and

                                       isinstance(parent.parent, Not))

def need_source_access_relation(vargraph):

    if not vargraph:

        return False

    # check vargraph contains some other relation than the identity relation

    # test of key nature since it may be a variable name (don't care about that)

    # or a 2-uple (var1, var2) associated to the relation to traverse to go from

    # var1 to var2

    return any(key for key, val in vargraph.iteritems()

               if isinstance(key, tuple) and val != 'identity')

def need_aggr_step(select, sources, stepdefs=None):

    """return True if a temporary table is necessary to store some partial

    results to execute the given query

    """

    if len(sources) == 1:

        # can do everything at once with a single source

        return False

    if select.orderby or select.groupby or select.has_aggregat:

        # if more than one source, we need a temp table to deal with sort /

        # groups / aggregat if :

        # * the rqlst won't be splitted (in the other case the last query

        #   using partial temporary table can do sort/groups/aggregat without

        #   the need for a later AggrStep)

        # * the rqlst is splitted in multiple steps and there are more than one

        #   final step

        if stepdefs is None:

            return True

        has_one_final = False

        fstepsolindices = set()

        for stepdef in stepdefs:

            if stepdef[-1]:

                if has_one_final or frozenset(stepdef[2]) != fstepsolindices:

                    return True

                has_one_final = True

            else:

                fstepsolindices.update(stepdef[2])

    return False

def select_group_sort(select): # XXX something similar done in rql2sql

    # add variables used in groups and sort terms to the selection

    # if necessary

    if select.groupby:

        for vref in select.groupby:

            if not vref in select.selection:

                select.append_selected(vref.copy(select))

    for sortterm in select.orderby:

        for vref in sortterm.iget_nodes(VariableRef):

            if not vref in select.get_selected_variables():

                # we can't directly insert sortterm.term because it references

                # a variable of the select before the copy.

                # XXX if constant term are used to define sort, their value

                # may necessite a decay

                select.append_selected(vref.copy(select))

                if select.groupby and not vref in select.groupby:

                    select.add_group_var(vref.copy(select))

def allequals(solutions):

    """return true if all solutions are identical"""

    sol = solutions.next()

    noconstsol = None

    for sol_ in solutions:

        if sol_ != sol:

            return False

    return True

# XXX move functions below to rql ##############################################

def is_ancestor(n1, n2):

    """return True if n2 is a parent scope of n1"""

    p = n1.parent

    while p is not None:

        if p is n2:

            return True

        p = p.parent

    return False

def copy_node(newroot, node, subparts=()):

    newnode = node.__class__(*node.initargs(newroot))

    for part in subparts:

        newnode.append(part)

    return newnode

def used_in_outer_scope(var, scope):

    """return true if the variable is used in an outer scope of the given scope

    """

    for rel in var.stinfo['relations']:

        rscope = ms_scope(rel)

        if not rscope is scope and is_ancestor(scope, rscope):

            return True

    return False

################################################################################

class PartPlanInformation(object):

    """regroups necessary information to execute some part of a "global" rql

    query ("global" means as received by the querier, which may result in

    several internal queries, e.g. parts, due to security insertions). Actually

    a PPI is created for each subquery and for each query in a union.

    It exposes as well some methods helping in executing this part on a

    multi-sources repository, modifying its internal structure during the

    process.

    :attr plan:

      the execution plan

    :attr rqlst:

      the original rql syntax tree handled by this part

    :attr needsplit:

      bool telling if the query has to be split into multiple steps for

      execution or if it can be executed at once

    :attr temptable:

      a SQL temporary table name or None, if necessary to handle aggregate /

      sorting for this part of the query

    :attr finaltable:

      a SQL table name or None, if results for this part of the query should be

      written into a temporary table (usually shared by multiple PPI)

    :attr sourcesterms:

      a dictionary {source : {term: set([solution index, ])}} telling for each

      source which terms are supported for which solutions. A "term" may be

      either a rql Variable, Constant or Relation node.

    """

    def __init__(self, plan, rqlst, rqlhelper=None):

        self.plan = plan

        self.rqlst = rqlst

        self.needsplit = False

        self.temptable = None

        self.finaltable = None

        # shortcuts

        self._schema = plan.schema

        self._session = plan.session

        self._repo = self._session.repo

        self._solutions = rqlst.solutions

        self._solindices = range(len(self._solutions))

        self.system_source = self._repo.system_source

        # source : {term: [solution index, ]}

        self.sourcesterms = self._sourcesterms = {}

        # source : {relation: set(child variable and constant)}

        self._crossrelations = {}

        # term : set(sources)

        self._discarded_sources = {}

        # dictionary of variables and constants which are linked to each other

        # using a non final relation supported by multiple sources (crossed or

        # not).

        self._linkedterms = {}

        # processing

        termssources = self._compute_sourcesterms()

        self._remove_invalid_sources(termssources)

        self._compute_needsplit()

        # after initialisation, .sourcesterms contains the same thing as

        # ._sourcesterms though during plan construction, ._sourcesterms will

        # be modified while .sourcesterms will be kept unmodified

        self.sourcesterms = {}

        for k, v in self._sourcesterms.iteritems():

            self.sourcesterms[k] = {}

            for k2, v2 in v.iteritems():

                self.sourcesterms[k][k2] = v2.copy()

        # cleanup linked var

        for var, linkedrelsinfo in self._linkedterms.iteritems():

            self._linkedterms[var] = frozenset(x[0] for x in linkedrelsinfo)

        # map output of a step to input of a following step

        self._inputmaps = {}

        # record input map conflicts to resolve them on final step generation

        self._conflicts = []

        if rqlhelper is not None: # else test

            self._insert_identity_variable = rqlhelper._annotator.rewrite_shared_optional

        if server.DEBUG & server.DBG_MS:

            print 'sourcesterms:'

            self._debug_sourcesterms()

    def _debug_sourcesterms(self):

        for source in self._sourcesterms:

            print '-', source

            for term, sols in self._sourcesterms[source].items():

                print '  -', term, id(term), ':', sols

    def copy_solutions(self, solindices):

        return [self._solutions[solidx].copy() for solidx in solindices]

    @property

    @cached

    def part_sources(self):

        if self._sourcesterms:

            return tuple(sorted(self._sourcesterms))

        return (self.system_source,)

    @property

    @cached

    def _sys_source_set(self):

        return frozenset((self.system_source, solindex)

                         for solindex in self._solindices)

    @cached

    def _norel_support_set(self, relation):

        """return a set of (source, solindex) where source doesn't support the

        relation

        """

        return frozenset((source, solidx) for source in self._repo.sources

                         for solidx in self._solindices

                         if not ((source.support_relation(relation.r_type))

                                 or relation.r_type in source.dont_cross_relations))

    def _compute_sourcesterms(self):

        """compute for each term (variable, rewritten constant, relation) and

        for each solution in the rqlst which sources support them

        """

        repo = self._repo

        eschema = self._schema.eschema

        sourcesterms = self._sourcesterms

        # find for each source which variable/solution are supported

        for varname, varobj in self.rqlst.defined_vars.items():

            # if variable has an eid specified, we can get its source directly

            # NOTE: use uidrel and not constnode to deal with "X eid IN(1,2,3,4)"

            if varobj.stinfo['uidrel'] is not None:

                rel = varobj.stinfo['uidrel']

                hasrel = len(varobj.stinfo['relations']) > 1

                for const in rel.children[1].get_nodes(Constant):

                    eid = const.eval(self.plan.args)

                    source = self._session.source_from_eid(eid)

                    if (source is self.system_source

                        or (hasrel and varobj._q_invariant and

                            not any(source.support_relation(r.r_type)

                                    for r in varobj.stinfo['relations']

                                    if not r is rel))):

                        self._set_source_for_term(self.system_source, varobj)

                    else:

                        self._set_source_for_term(source, varobj)

                continue

            rels = varobj.stinfo['relations']

            if not rels and varobj.stinfo['typerel'] is None:

                # (rare) case where the variable has no type specified nor

                # relation accessed ex. "Any MAX(X)"

                self._set_source_for_term(self.system_source, varobj)

                continue

            for i, sol in enumerate(self._solutions):

                vartype = sol[varname]

                # skip final variable

                if eschema(vartype).final:

                    break

                for source in repo.sources:

                    if source.support_entity(vartype):

                        # the source support the entity type, though we will

                        # actually have to fetch from it only if

                        # * the variable isn't invariant