#! /usr/bin/python """ Find differences between two RDF graphs, using functional and inverse functional properties to identify bnodes in the patch file. --from=uri -f uri from-file --to=uri -t uri file against which to check for differences --meta=uri -m uri file with metadata to be assumed (in addition to schemas) --help -h print this help message --verbose= -v 1 verbose mode (can be 0 to 10, 0 is default) --granularity= -g 0 g=0 - lots of little diffs. g=1, fewer diffs (default) If from-file but not to-file is given, from-file is smushed and output Uris are relative to present working directory. For motivation and explanation, see $Id: delta.py,v 1.11 2007/06/26 02:36:15 syosi Exp $ http://www.w3.org/2000/10/swap/diff.py """ import string, getopt try: Set = set # Python2.4 and on except NameError: from sets import Set # Python2.3 and on import string import sys # http://www.w3.org/2000/10/swap/ try: from swap import llyn, diag from swap.myStore import loadMany from swap.diag import verbosity, setVerbosity, progress from swap import notation3 # N3 parsers and generators from swap.RDFSink import FORMULA, LITERAL, ANONYMOUS, Logic_NS from swap import uripath from swap.uripath import base from swap.myStore import Namespace from swap import myStore from swap.notation3 import RDF_NS_URI from swap.llyn import Formula, CONTEXT, PRED, SUBJ, OBJ except ImportError: import llyn, diag from myStore import loadMany from diag import verbosity, setVerbosity, progress import notation3 # N3 parsers and generators from RDFSink import FORMULA, LITERAL, ANONYMOUS, Logic_NS import uripath from uripath import base from myStore import Namespace import myStore from notation3 import RDF_NS_URI from llyn import Formula, CONTEXT, PRED, SUBJ, OBJ #daml = Namespace("http://www.daml.org/2001/03/daml+oil#") OWL = Namespace("http://www.w3.org/2002/07/owl#") RDF = Namespace("http://www.w3.org/1999/02/22-rdf-syntax-ns#") LOG = Namespace("http://www.w3.org/2000/10/swap/log#") DELTA = Namespace("http://www.w3.org/2004/delta#") def debugBnode(n, f): progress("For node %s" % `n`) for s in f.statementsMatching(subj=n): progress(" %s %s; # could be ifp?" %(`s.predicate()`, `s.object()`)) for s in f.statementsMatching(obj=n): progress(" is %s of %s; # could be fp?" %(`s.predicate()`, `s.subject()`)) def lookUp(predicates, assumptions=Set()): """Look up all the schemas for the predicates given""" global verbose schemas = assumptions for pred in predicates: if verbose > 3: progress("Predicate: %s" % `pred`) u = pred.uriref() hash = u.find("#") if hash <0: if verbose > 1: progress("Warning: Predicate <%s> looks like web resource not Property" % u) else: schemas.add(u[:hash]) if verbose > 2: for r in schemas: progress("Metadata to be loaded: ", r) if schemas: return loadMany([(x) for x in schemas]) return myStore.store.newFormula() # Empty formula def nailFormula(f, assumptions=Set()): """Smush the formula. Build a dictionary of nodes which are indirectly identified by [inverse] functonal properties.""" global verbose cc, predicates, ss, oo = getParts(f) nodes = ss | oo sofar = {} bnodes = Set() for node in nodes: if node.generated() or node in f.existentials(): bnodes.add(node) if verbose >=5: progress("Blank node: %s" % `node`) else: if verbose >=5: progress("Fixed node: %s" % `node`) sofar[node] = [] meta = lookUp(predicates, assumptions) ifps = predicates & Set(meta.each(pred=RDF.type, obj=OWL.InverseFunctionalProperty)) fps = predicates & Set(meta.each(pred=RDF.type, obj=OWL.FunctionalProperty)) if verbose > 1: for p in fps: progress("Functional Property:", p) for p in ifps: progress("Inverse Functional: ", p) definitions = [] if len(bnodes) == 0: if verbose > 0: progress("No bnodes in graph") return bnodes, definitions a = float(len(bnodes))/len(nodes) if verbose > 1: progress("Proportion of bodes which are blank: %f" % a) # if a == 0: return bnodes, definitions loose = bnodes.copy() equivs = Set() # Note possible optmization: First pass only like this, # future passes work from newNodes. while loose: newNailed = Set() for preds, inverse, char in ((fps, 0, "!"), (ifps, 1, "^")): for pred in preds: if verbose > 3: progress("Predicate", pred) ss = f.statementsMatching(pred=pred) for s in ss: if inverse: y, x = s.object(), s.subject() else: x, y = s.object(), s.subject() if not x.generated(): continue # Only anchor bnodes if y not in loose: # y is the possible anchor defi = (x, inverse, pred, y) if x in loose: # this node if verbose > 4: progress(" Nailed %s as %s%s%s" % (`x`, `y`, `char`, `pred`)) loose.discard(x) newNailed.add(x) else: if verbose >=6 : progress( " (ignored %s as %s%s%s)" % (`x`, `y`, `char`, `pred`)) definitions.append(defi) # if verbose > 9: progress(" Definition[x] is now", definition[x]) if inverse: equivalentSet = Set(f.each(obj=y, pred=pred)) else: equivalentSet = Set(f.each(subj=y, pred=pred)) if len(equivalentSet) > 1: equivs.add(equivalentSet) if not newNailed: if verbose > 1: progress("Failed to nail nodes:", loose) if verbose > 3: for n in loose: debugBnode(n, f) break # At this point if we still have loose nodes, we have failed with ifps and fps. # Diff may not be strong. (It might still be: the diffs might not involve weak definitions) weak = loose.copy() # Remember if verbose > 0: progress("\nFailed to directly nail everything, looking for weak nailings.") # sys.exit(-1) #@@@ while loose: newNailed = Set() if verbose>2: progress() progress("Pass: loose = %s" % loose) for x in loose.copy(): if verbose>3: progress("Checking weakly node %s" % x) for s in f.statementsMatching(obj=x): pred, y = s.predicate(), s.subject() if y in loose: if verbose > 4: progress("Can't nail to loose %s" % y) continue # Can't nail to something loose others = f.each(subj=y, pred=pred) # @@ Should ignore redirected equivalent nodes in others if len(others) != 1: if verbose>4: progress("Can't nail: %s all are %s of %s." % (others, pred, y)) continue # Defn would be ambiguous in this graph defi = (x, 0, pred, y) if verbose >4: progress(" Weakly-nailed %s as %s%s%s" % (x, y, "!", pred)) loose.discard(x) newNailed.add(x) definitions.append(defi) break # progress else: for s in f.statementsMatching(subj=x): pred, obj = s.predicate(), s.object() if obj in loose: if verbose >4: progress("Can't nail to loose %s" % obj) continue # Can't nail to something loose others = f.each(obj=obj, pred=pred) # @@ Should ignore redirected equivalent nodes in others if len(others) != 1: if verbose >4: progress( "Can't nail: %s all have %s of %s." % (others, pred, obj)) continue # Defn would be ambiguous in this graph defi = (x, 1, pred, obj) if verbose>2: progress(" Weakly-nailed %s as %s%s%s" % (`x`, `obj`, "^", `pred`)) loose.discard(x) newNailed.add(x) definitions.append(defi) break # progress if not newNailed: if verbose>0: progress("Failed to even weakly nail nodes:", loose) for n in loose: progress("For node %s" % n) for s in f.statementsMatching(subj=n): progress(" %s %s; # could be ifp?" %(`s.predicate()`, `s.object()`)) for s in f.statementsMatching(obj=n): progress(" is %s of %s; # could be fp?" %(s.predicate(), s.subject())) raise ValueError("Graph insufficiently labelled for nodes: %s" % loose) if verbose>0 and not weak: progress("Graph is solid.") if verbose>0 and weak: progress("Graph is NOT solid.") f.reopen() for es in equivs: if verbose>3: progress("Equivalent: ", es) prev = None for x in es: if prev: f.add(x, OWL.sameAs, prev) prev = x return bnodes, definitions def removeCommon(f, g, match): """Find common statements from f and g match gives the dictionary mapping bnodes in f to bnodes in g""" only_f, common_g = Set(), Set() for st in f.statements[:]: s, p, o = st.spo() assert s not in f._redirections assert o not in f._redirections if s.generated(): sg = match.get(s, None) else: sg = s if o.generated(): og = match.get(o, None) else: og = o if og != None and sg != None: gsts = g.statementsMatching(subj=sg, pred=p, obj=og) if len(gsts) == 1: if verbose>4: progress("Statement in both", st) common_g.add(gsts[0]) continue only_f.add(st) return only_f, Set(g.statements)-common_g def patches(delta, f, only_f, originalBnodes, definitions, deleting=0): """Generate patches in patch formula, for the remaining statements in f given the bnodes and definitions for f.""" todo = only_f.copy() if deleting: patchVerb = DELTA.deletion else: patchVerb = DELTA.insertion if verbose>2: progress("*********** PATCHES: %s, with %i to do" %(patchVerb, len(todo))) while todo: # find a contiguous subgraph defined in the given graph bnodesToDo = Set() bnodes = Set() rhs = delta.newFormula() lhs = delta.newFormula() # left hand side of patch newStatements = Set() for seed in todo: break # pick one #@2 fn? statementsToDo = Set([seed]) if verbose>3: progress("Seed:", seed) subgraph = statementsToDo while statementsToDo or bnodesToDo: for st in statementsToDo: s, p, o = st.spo() for x in s, p, o: if x.generated() and x not in bnodes: # and x not in commonBnodes: if verbose>4: progress(" Bnode ", x) bnodesToDo.add(x) bnodes.add(x) rhs.add(s, p, o) statementsToDo = Set() for x in bnodesToDo: bnodes.add(x) ss = (f.statementsMatching(subj=x) + f.statementsMatching(pred=x) + f.statementsMatching(obj=x)) for z in ss: if z in only_f: newStatements.add(z) if verbose>3: progress(" New statements from %s: %s" % (x, newStatements)) statementsToDo = statementsToDo | newStatements subgraph = subgraph |newStatements bnodesToDo = Set() if verbose>3: progress("Subgraph of %i statements (%i left):\n\t%s\n" %(len(subgraph), len(todo), subgraph)) todo = todo - subgraph undefined = bnodes.copy() for x, inverse, pred, y in definitions: if x in undefined: if inverse: s, p, o = x, pred, y else: s, p, o = y, pred, x if verbose > 4: progress("Declaring variable %s" % x.uriref()) if deleting: delta.declareUniversal(x) lhs.add(subj=s, pred=p, obj=o) else: # inserting if x in originalBnodes: delta.declareUniversal(x) lhs.add(subj=s, pred=p, obj=o) else: rhs.declareExistential(x) if y.generated(): undefined.add(y) undefined.discard(x) if undefined: progress("Still haven't defined bnodes %s" % undefined) for n in undefined: debugBnode(n, f) raise RuntimeError("BNodes still undefined", undefined) lhs = lhs.close() rhs = rhs.close() delta.add(subj=lhs, pred=patchVerb, obj=rhs) if verbose >1: progress("PATCH: %s %s %s\n" %(lhs.n3String(), `patchVerb`, rhs.n3String())) return def consolidate(delta, patchVerb): """Consolidate patches Where the same left hand side applies to more than 1 RHS formula, roll those RHS formulae into one, to make the dif file more readable and faster to execute in some implementations """ agenda = {} if verbose >3: progress("Consolidating %s" % patchVerb) for s in delta.statementsMatching(pred=patchVerb): list = agenda.get(s.subject(), None) if list == None: list = [] agenda[s.subject()] = list list.append(s) for lhs, list in agenda.items(): if verbose >3: progress("Patches lhs= %s: %s" %(lhs, list)) if len(list) > 1: rhs = delta.newFormula() for s in list: delta.store.copyFormula(s.object(), rhs) delta.removeStatement(s) delta.add(subj=lhs, pred=patchVerb, obj=rhs.close()) def differences(f, g, assumptions): """Smush the formulae. Compare them, generating patch instructions.""" global lumped # Cross-map nodes: g_bnodes, g_definitions = nailFormula(g, assumptions) bnodes, definitions = nailFormula(f, assumptions) if verbose > 1: progress("\n Done nailing") definitions.reverse() # go back down list @@@ reverse the g list too? @@@ g_definitions.reverse() # @@ needed for the patch generation unmatched = bnodes.copy() match = {} # Mapping of nodes in f to nodes in g for x, inverse, pred, y in definitions: if x in match: continue # done already if x in f._redirections: if verbose > 3: progress("Redirected %s to %s. Ignoring" % (`x`, `f._redirections[x]`)) unmatched.discard(x) continue if verbose > 3: progress("Definition of %s = %s%s%s"% (`x`, `y` , ".!^"[inverse], `pred`)) if y.generated(): while y in f._redirections: y = f._redirections[y] if verbose>4: progress(" redirected to %s = %s%s%s"% (`x`, `y`, "!^"[inverse], `pred`)) yg = match.get(y, None) if yg == None: if verbose>4: progress(" Had definition for %s in terms of %s which is not matched"%(`x`,`y`)) continue else: yg = y if inverse: # Inverse functional property like ssn matches = Set(g.each(obj=yg, pred=pred)) else: matches = Set(g.each(subj=yg, pred=pred)) if len(matches) == 0: continue # This is normal - the node does not exist in the other graph # raise RuntimeError("Can't match %s" % x) if len(matches) > 1: raise RuntimeError("""Rats. Wheras in the first graph %s%s%s uniquely selects %s, in the other graph there are more than 1 matches: %s""" % (`y`, "!^"[inverse], `pred`, `x`, `matches`)) for q in matches: # pick only one @@ python function? z = q break if verbose > 2: progress("Found match for %s in %s " % (`x`,`z`)) match[x] = z unmatched.discard(x) if len(unmatched) > 0: if verbose >1: progress("Failed to match all nodes:", unmatched) for n in unmatched: debugBnode(n, f) # Find common parts only_f, only_g = removeCommon(f,g, match) delta = f.newFormula() if len(only_f) == 0 and len(only_g) == 0: return delta f = f.close() # We are not going to mess with them any more g = g.close() common = Set([match[x] for x in match]) if verbose>2: progress("Common bnodes (as named in g)", common) patches(delta, f, only_f, Set(), definitions, deleting=1) patches(delta, g, only_g, common, g_definitions, deleting=0) if lumped: consolidate(delta, delta.store.insertion) consolidate(delta, delta.store.deletion) return delta def getParts(f, meta=None): """Make lists of all node IDs and arc types """ values = [Set([]),Set([]),Set([]),Set([])] for s in f.statements: for p in SUBJ, PRED, OBJ: x = s[p] values[p].add(x) return values def loadFiles(files): graph = myStore.formula() graph.setClosureMode("e") # Implement sameAs by smushing if verbose>0: progress("Loading %s..." % files) graph = myStore.loadMany(files, openFormula=graph) if verbose>0: progress("Loaded", graph) return graph def usage(): sys.stderr.write(__doc__) def main(): testFiles = [] diffFiles = [] assumptions = Set() global ploughOn # even if error ploughOn = 0 global verbose global lumped verbose = 0 lumped = 1 try: opts, args = getopt.getopt(sys.argv[1:], "hf:t:m:v:g:", ["help", "from=", "to=", "meta=", "verbose=", "granularity="]) except getopt.GetoptError: # print help information and exit: usage() sys.exit(2) output = None for o, a in opts: if o in ("-h", "--help"): usage() sys.exit(2) if o in ("-v", "--verbose"): try: verbose = int(a) except ValueError: verbose = 10 if o in ("-g", "--granularity"): try: lumped = int(a) except ValueError: lumped = 0 if o in ("-f", "--from"): testFiles.append(a) if o in ("-t", "--to"): diffFiles.append(a) if o in ("-m", "--meta"): assumptions.add(a) # if testFiles == []: testFiles = [ "/dev/stdin" ] if testFiles == []: usage() sys.exit(2) graph = loadFiles(testFiles) version = "$Id: delta.py,v 1.11 2007/06/26 02:36:15 syosi Exp $"[1:-1] if diffFiles == []: nailFormula(graph, assumptions) if verbose > 1: print "# Smush generated by " + version print graph.close().n3String(base=base(), flags="a") sys.exit(0) graph2 = loadFiles(diffFiles) delta = differences(graph, graph2, assumptions) if verbose >1: print "# Differences by " + version print delta.close().n3String(base=base()) # sys.exit(len(delta)) # sys.exit(0) # didn't crash if delta.contains(): # Any statements in delta at all? sys.exit(1) else: sys.exit(0) if __name__ == "__main__": main()