########################################################################
#
# File Name:            Traversal
#
#
"""
the classes that perform traversal in Versa
WWW: http://4suite.org        e-mail: support@4suite.org

Copyright 2002 Fourthought Inc, USA.
See  http://4suite.org/COPYRIGHT  for license and copyright information
"""

import DataTypes
import types
from Ft.Rdf import Model, OBJECT_TYPE_RESOURCE
from Ft.Lib import boolean
import ResourceExpressions, NamedExpressions, Literals, Optimizer


class Traversal:
    """
    Base class for all Traversals


    http://www.w3.org/TR/rdf-mt/#RDFRules (7.3 RDFS Entailment Rules)
    OWL usage of rdfs:domain, rdfs:range, and Extensional Entailment Rules *could* provide some optimizations via
    inference, when evaluating traversal expressions, they could also implement *some* RDFS entailment rules
    by providing additional checks when evaluating traversals.       
    """
    def evaluate(self,con):
        raise "Not Implemented in %s" % repr(self)


class ForwardTraversal(Traversal):
    """
    Shift the context along an arc.
    Shift from the set of resources, alongs each predicates, filter the results with the filter
    The predicates get evaluated with the shifted context
    The filter is applied to each result set with the resource that created it as context
    """
    def __init__(self, resources, predicates, filter, isFilter=0):
        self.isFilter = isFilter
        self.resources = resources
        self.predicates = predicates
        self.filterExpr = filter
        self.evaluate = self.evaluateOptNone
        self._optAllSubjFlag = 0
        self._optAllPredFlag = 0
        self._containsFlags = Model.REGEX

        if Optimizer.IsCoreFunction(self.resources, "all"):
            self._optAllSubjFlag = 1
        if Optimizer.IsCoreFunction(self.predicates, "properties") and \
           ( not self.predicates._args or isinstance(self.predicates._args[0], ResourceExpressions.CurrentExpression) ):
            self._optAllPredFlag = 1
        if self._optAllPredFlag or Optimizer.IsFixedResourceCollection(self.predicates):
            if Optimizer.IsCoreFunction(self.filterExpr, "eq"):
                if len(self.filterExpr._args) == 1 and \
                   (isinstance(self.filterExpr._args[0], Literals.StringLiteral) \
                    or isinstance(self.filterExpr._args[0], Literals.ResourceLiteral) \
                    or isinstance(self.filterExpr._args[0], ResourceExpressions.PureQNameExpression)):
                    self.evaluate = self.evaluateOptEq
            elif Optimizer.IsCoreFunction(self.filterExpr, "contains"):
                if len(self.filterExpr._args) == 1 and \
                   isinstance(self.filterExpr._args[0], Literals.StringLiteral):
                    self.evaluate = self.evaluateOptContains
            elif Optimizer.IsCoreFunction(self.filterExpr, "contains-ci"):
                if len(self.filterExpr._args) == 1 and \
                   isinstance(self.filterExpr._args[0], Literals.StringLiteral):
                    self._containsFlags = Model.REGEX | Model.IGNORE_CASE
                    self.evaluate = self.evaluateOptContains
            elif isinstance(self.filterExpr, ResourceExpressions.LiteralExpression):
                if self.filterExpr.value == boolean.true:
                    self.evaluate = self.evaluateOptWildcard
            elif not self._optAllPredFlag:
                self.evaluate = self.evaluateOptFixedPred
        return

    def evaluateOptNone(self, con):
        #print "OPTIMIZER: using ForwardTraversal.evaluateOptNone"
        curReses = DataTypes.ToList(self.resources.evaluate(con))
        res = []
        orig = con.current
        for r in curReses:
            if not r:
                #This is a kludge until we can easily not treat a null value as a wildcard
                continue
            con.current = r
            preds = [ str(p) for p in DataTypes.ToList(self.predicates.evaluate(con)) ]
            if not preds:
                continue
            objects = con.driver.objectsFromSubAndPreds(str(r), preds, con.scope)
            for o, otype in objects:
                o = otype == OBJECT_TYPE_RESOURCE and DataTypes.ToResource(o) or o
                con.current = o
                if self.filterExpr.evaluate(con):
                    if self.isFilter:
                        res.append(DataTypes.ToResource(r))
                    else:
                        res.append(o)
        #print "Traversed from %s to %s" % (str(curReses),str(res.keys()))
        con.current = orig
        return res

    def evaluateOptFixedPred(self, con):
        """
        Optimization for traversals where the predicate does not change
        in any of the possibilities
        """
        #print "OPTIMIZER: using ForwardTraversal.evaluateOptFixedPred"
        orig = con.current
        
        if self._optAllSubjFlag:
            #print "OPTIMIZER: with subject = all() variation"
            preds = DataTypes.ToList(self.predicates.evaluate(con))
            results = []
            for p in preds:
                stmts = con.driver.complete(None, unicode(str(p), 'utf-8'),
                                            None, None, con.scope,{})
                for s in stmts:
                    o = s[5] == OBJECT_TYPE_RESOURCE and DataTypes.ToResource(s[2]) or s[2]
                    con.current = o
                    if self.filterExpr.evaluate(con):
                        if self.isFilter:
                            results.append(DataTypes.ToResource(s[0]))
                        else:
                            results.append(o)
            return results
                    
        
        cur_reses = DataTypes.ToList(self.resources.evaluate(con))
        if not cur_reses: return []
        preds = DataTypes.ToList(self.predicates.evaluate(con))
        if self.isFilter:
            objects = []
            result = []
            for p in preds:
                rel = ResourceExpressions.GetRelations(cur_reses, p, con, 0)
                for k in rel.keys():
                    for o in rel[k]:
                        con.current = o
                        if self.filterExpr.evaluate(con):
                            result.append(DataTypes.ToResource(k))
                            break
        else:
            objects = []
            for p in preds:
                rel = ResourceExpressions.GetRelations(cur_reses, p, con, 0)
                for k in rel.keys():
                    objects.extend(rel[k])
            result = []
            for o in objects:
                con.current = o
                if self.filterExpr.evaluate(con):
                    result.append(o)
        con.current = orig
        return result

    def evaluateOptEq(self, con):
        #print "OPTIMIZER: using ForwardTraversal.evaluateOptEq"
        obj = self.filterExpr._args[0].evaluate(con)
        if self._optAllSubjFlag:
            #print "OPTIMIZER: with subject = all() variation"
            result = []
            obj = DataTypes.ToString(obj)
            if self._optAllPredFlag:
                if self.isFilter:
                    result.extend([ DataTypes.ToResource(s[0]) for s in con.driver.complete(None, None, obj, None, con.scope, {}) ] )
                else:
                    result.extend([ s[5] == OBJECT_TYPE_RESOURCE and DataTypes.ToResource(s[2]) or s[2] for s in con.driver.complete(None, None, obj, None, con.scope, {}) ] )
                return result
            preds = DataTypes.ToList(self.predicates.evaluate(con))
            for p in preds:
                p = unicode(str(p), 'utf-8')
                if self.isFilter:
                    result.extend([ DataTypes.ToResource(s[0]) for s in con.driver.complete(None, p, obj, None, con.scope, {}) ] )
                else:
                    result.extend([ s[5] == OBJECT_TYPE_RESOURCE and DataTypes.ToResource(s[2]) or s[2] for s in con.driver.complete(None, p, obj, None, con.scope, {}) ] )
            return result
        preds = DataTypes.ToList(self.predicates.evaluate(con))
        curReses = DataTypes.ToList(self.resources.evaluate(con))
        result = []
        orig = con.current
        for r in curReses:
            if not r:
                #This is a kludge until we can easily not treat a null value as a wildcard
                continue
            con.current = r
            for p in preds:
                p = unicode(str(p), 'utf-8')
                obj = DataTypes.ToString(obj)
                r = DataTypes.ToString(r)
                if self.isFilter:
                    result.extend([ DataTypes.ToResource(s[0]) for s in con.driver.complete(r, p, obj, None, con.scope, {}) ] )
                else:
                    result.extend([ s[5] == OBJECT_TYPE_RESOURCE and DataTypes.ToResource(s[2]) or s[2] for s in con.driver.complete(r, p, obj, None, con.scope, {}) ] )
        #print "Traversed from %s to %s" % (str(curReses),str(objects.keys()))
        con.current = orig
        return result

    def evaluateOptContains(self, con):
        #print "OPTIMIZER: using ForwardTraversal.evaluateOptContains"
        obj = self.filterExpr._args[0].evaluate(con)
        if self._optAllSubjFlag:
            #print "OPTIMIZER: with subject = all() variation"
            result = []
            obj = DataTypes.ToString(obj)
            if self._optAllPredFlag:
                #print "OPTIMIZER: with predicate = all properties variation"
                if self.isFilter:
                    result.extend([ DataTypes.ToResource(s[0]) for s in con.driver.complete(None, None, '.*'+obj+'.*', None, con.scope, flags={"objectFlags": self._containsFlags}) ] )
                else:
                    result.extend([ s[5] == OBJECT_TYPE_RESOURCE and DataTypes.ToResource(s[2]) or s[2] for s in con.driver.complete(None, None, '.*'+obj+'.*', None, con.scope, flags={"objectFlags": self._containsFlags}) ] )
                return result
            preds = DataTypes.ToList(self.predicates.evaluate(con))
            for p in preds:
                p = unicode(str(p), 'utf-8')
                if self.isFilter:
                    result.extend([ DataTypes.ToResource(s[0]) for s in con.driver.complete(None, p, '.*'+obj+'.*', None, con.scope, flags={"objectFlags": self._containsFlags}) ] )
                else:
                    result.extend([ s[5] == OBJECT_TYPE_RESOURCE and DataTypes.ToResource(s[2]) or s[2] for s in con.driver.complete(None, p, '.*'+obj+'.*', None, con.scope, flags={"objectFlags": self._containsFlags}) ] )
            return result
        preds = DataTypes.ToList(self.predicates.evaluate(con))
        curReses = DataTypes.ToList(self.resources.evaluate(con))
        result = []
        orig = con.current
        for r in curReses:
            if not r:
                #This is a kludge until we can easily not treat a null value as a wildcard
                continue
            con.current = r
            for p in preds:
                p = unicode(str(p), 'utf-8')
                obj = DataTypes.ToString(obj)
                if self.isFilter:
                    result.extend([ DataTypes.ToResource(s[0]) for s in con.driver.complete(r, p, '.*'+obj+'.*', None, con.scope, flags={"objectFlags": self._containsFlags}) ] )
                else:
                    result.extend([ s[5] == OBJECT_TYPE_RESOURCE and DataTypes.ToResource(s[2]) or s[2] for s in con.driver.complete(r, p, '.*'+obj+'.*', None, con.scope, flags={"objectFlags": self._containsFlags}) ] )
        #print "Traversed from %s to %s" % (str(curReses),str(result.keys()))
        con.current = orig
        return result

    def evaluateOptWildcard(self, con):
        #print "OPTIMIZER: using ForwardTraversal.evaluateOptWildcard"
        if self._optAllSubjFlag:
            #print "OPTIMIZER: with subject = all() variation"
            result = []
            if self._optAllPredFlag:
                #print "OPTIMIZER: with predicate = all properties variation"
                if self.isFilter:
                    result.extend([ DataTypes.ToResource(s[0]) for s in con.driver.complete(None, None, None, None, con.scope, {}) ] )
                else:
                    result.extend([ (s[2], s[5]) for s in con.driver.complete(None, None, None, None, con.scope, {}) ] )
                    result = [ o[1] == OBJECT_TYPE_RESOURCE and DataTypes.ToResource(o[0]) or o[0] for o in result ]
                return result
            preds = DataTypes.ToList(self.predicates.evaluate(con))
            for p in preds:
                p = unicode(str(p), 'utf-8')
                if self.isFilter:
                    result.extend([ DataTypes.ToResource(s[0]) for s in con.driver.complete(None, p, None, None, con.scope, {}) ] )
                else:
                    result.extend([ s[5] == OBJECT_TYPE_RESOURCE and DataTypes.ToResource(s[2]) or s[2] for s in con.driver.complete(None, p, None, None, con.scope, {}) ] )
            return result
        if self._optAllPredFlag:
            #print "OPTIMIZER: with predicate = all properties variation"
            preds = [None]
        else:
            preds = DataTypes.ToList(self.predicates.evaluate(con))
        curReses = DataTypes.ToList(self.resources.evaluate(con))
        result = []
        orig = con.current
        for r in curReses:
            if not r:
                #This is a kludge until we can easily not treat a null value as a wildcard
                continue
            con.current = r
            for p in preds:
                if p: p = unicode(str(p), 'utf-8')
                r = DataTypes.ToString(r)
                if self.isFilter:
                    result.extend([ DataTypes.ToResource(s[0]) for s in con.driver.complete(r, p, None, None, con.scope, {}) ] )
                else:
                    result.extend([ s[5] == OBJECT_TYPE_RESOURCE and DataTypes.ToResource(s[2]) or s[2] for s in con.driver.complete(r, p, None, None, con.scope, {}) ] )
        #print "Traversed from %s to %s" % (str(curReses),str(result.keys()))
        con.current = orig
        return result


class BackwardTraversal(Traversal):
    """
    Shift the context against an arc.
    Shift from the set of resources, along each predicates, filter the results with the filter
    The predicates get evaluated with the shifted context
    The filter is applied to each result set with the resource that created it as context
    """
    def __init__(self, objects, predicates, filter):
        self.objects = objects
        self.predicates = predicates
        self.filterExpr = filter
        self.evaluate = self.evaluateOptNone
        self._optAllSubjFlag = 0
        if Optimizer.IsCoreFunction(self.objects, "all"):
            self._optAllSubjFlag = 1
        elif Optimizer.IsCoreFunction(self.filterExpr, "eq"):
            if len(self.filterExpr._args) == 1 and \
               (isinstance(self.filterExpr._args[0], Literals.StringLiteral) \
                or isinstance(self.filterExpr._args[0], Literals.ResourceLiteral) \
                or isinstance(self.filterExpr._args[0], ResourceExpressions.PureQNameExpression)):
                self.evaluate = self.evaluateOptEq
        elif Optimizer.IsCoreFunction(self.filterExpr, "contains"):
            if len(self.filterExpr._args) == 1 and \
               isinstance(self.filterExpr._args[0], Literals.StringLiteral):
                self.evaluate = self.evaluateOptContains
        elif isinstance(self.filterExpr, ResourceExpressions.LiteralExpression):
            if self.filterExpr.value == boolean.true:
                self.evaluate = self.evaluateOptWildcard
        return

    def evaluateOptNone(self, con):
        #print "OPTIMIZER: using BackwardTraversal.evaluateOptNone"
        objs = DataTypes.ToList(self.objects.evaluate(con))
        res = []
        orig = con.current
        for o in objs:
            if not o:
                #This is a kludge until we can easily not treat a null value as a wildcard
                continue
            con.current = o
            preds = DataTypes.ToList(self.predicates.evaluate(con))
            if not preds:
                continue
            for s in con.driver.subjectsFromPredsAndObj(preds, o, con.scope):
                s = DataTypes.ToResource(s)
                con.current = s
                if self.filterExpr.evaluate(con):
                    res.append(s)
        #print "Traversed from %s to %s" % (str(objs), str(res.keys()))
        con.current = orig
        return res

    def evaluateOptWildcard(self, con):
        #print "OPTIMIZER: using BackwardTraversal.evaluateOptWildcard"
        preds = DataTypes.ToList(self.predicates.evaluate(con))
        if self._optAllSubjFlag:
            #print "OPTIMIZER: with subject = all() variation"
            subjects = []
            for p in preds:
                p = unicode(str(p), 'utf-8')
                subjects.extend([ DataTypes.ToResource(s[0]) for s in con.driver.complete(None, p, None, None, con.scope, {}) ] )
            return subjects
        objs = DataTypes.ToList(self.objects.evaluate(con))
        subjs = []
        for object in objs:
            if object:
                # This is a kludge until we can easily not treat a null
                # value as a wildcard
                o = DataTypes.ToString(object)
                for predicate in preds:
                    p = unicode(str(predicate), 'utf-8')
                    tuples = con.driver.complete(None, p, o, None, con.scope, {})
                    subjs.extend(map(lambda t, func=DataTypes.ToResource:
                                     func(t[0]),
                                     tuples))
                #for p in preds:
                #    p = unicode(str(p), 'utf-8')
                #    o = DataTypes.ToString(object)
                #    subjs.extend([ DataTypes.ToResource(s[0]) for s in con.driver.complete(None, p, o, None, con.scope, {}) ] )
        return subjs

    def evaluateOptEq(self, con):
        #print "OPTIMIZER: using BackwardTraversal.evaluateOptEq"
        subj = self.filterExpr._args[0].evaluate(con)
        preds = DataTypes.ToList(self.predicates.evaluate(con))
        if self._optAllSubjFlag:
            #print "OPTIMIZER: with subject = all() variation"
            subjects = []
            for p in preds:
                p = unicode(str(p), 'utf-8')
                subjects.extend([ DataTypes.ToResource(s[0]) for s in con.driver.complete(subj, p, None, None, con.scope, {}) ] )
            return subjects
        objs = DataTypes.ToList(self.objects.evaluate(con))
        subjs = []
        orig = con.current
        for o in objs:
            if not o:
                #This is a kludge until we can easily not treat a null value as a wildcard
                continue
            con.current = o
            for p in preds:
                p = unicode(str(p), 'utf-8')
                o = DataTypes.ToString(o)
                subjs.extend([ DataTypes.ToResource(s[0]) for s in con.driver.complete(subj, p, o, None, con.scope, {}) ] )
        con.current = orig
        return subjs

    def evaluateOptContains(self, con):
        #print "OPTIMIZER: using BackwardTraversal.evaluateOptContains"
        subj = self.filterExpr._args[0].evaluate(con)
        preds = DataTypes.ToList(self.predicates.evaluate(con))
        if self._optAllSubjFlag:
            #print "OPTIMIZER: with subject = all() variation"
            subjects = []
            for p in preds:
                p = unicode(str(p), 'utf-8')
                subjects.extend([ DataTypes.ToResource(s[0]) for s in con.driver.complete('.*'+subj+'.*', p, None, None, con.scope, flags={"subjectFlags": Model.REGEX}) ] )
            return subjects
        objs = DataTypes.ToList(self.objects.evaluate(con))
        subjs = []
        orig = con.current
        for o in objs:
            if not o:
                #This is a kludge until we can easily not treat a null value as a wildcard
                continue
            con.current = o
            for p in preds:
                p = unicode(str(p), 'utf-8')
                o = DataTypes.ToString(o)
                subjs.extend([ DataTypes.ToResource(s[0]) for s in con.driver.complete('.*'+subj+'.*', p, o, None, con.scope, flags={"subjectFlags": Model.REGEX}) ] )
        con.current = orig
        return subjs


