Viewing file:  Traversal.py (19.98 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
########################################################################
#
# 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
|