From 388c6c7dc0f2945a2d551a49886d0e2f1a2bacd2 Mon Sep 17 00:00:00 2001 From: smerten Date: Sun, 18 Apr 2010 10:45:20 +0000 Subject: [PATCH] Continued studies. git-svn-id: https://docutils.svn.sourceforge.net/svnroot/docutils/trunk@6309 929543f6-e4f2-0310-98a6-ba3bd3dd1d04 --- sandbox/rstdiff/global.log | 45 ++++++++++++++ sandbox/rstdiff/studies/diff.py | 111 +++++++++++++++-------------------- sandbox/rstdiff/studies/hashable.py | 113 ++++++++++++++++++++++++++++++++++-- sandbox/rstdiff/tag.log | 2 +- 4 files changed, 201 insertions(+), 70 deletions(-) diff --git a/sandbox/rstdiff/global.log b/sandbox/rstdiff/global.log index 31fed234b..051f1d3c7 100644 --- a/sandbox/rstdiff/global.log +++ b/sandbox/rstdiff/global.log @@ -1,4 +1,49 @@ ************************************** +Date: Sun Apr 18 12:45:06 CEST 2010 +Author: stefan +Tag: rstdiff_1_14 + +-------------------------------------- +Update of /home/stefan/vault/sm/rstdiff/studies +In directory rosalu:/home/stefan/free/rstdiff/studies + +Modified Files: + diff.py hashable.py + +-------------------------------------- +Log Message: +Refactoring. +************************************** +Date: Sat Apr 17 13:47:23 CEST 2010 +Author: stefan +Tag: rstdiff_1_13 + +-------------------------------------- +Update of /home/stefan/vault/sm/rstdiff/studies +In directory rosalu:/home/stefan/free/rstdiff/studies + +Modified Files: + diff.py + +-------------------------------------- +Log Message: +Continued studies. +************************************** +Date: Sat Apr 17 13:10:51 CEST 2010 +Author: stefan +Tag: rstdiff_1_12 + +-------------------------------------- +Update of /home/stefan/vault/sm/rstdiff/studies +In directory rosalu:/home/stefan/free/rstdiff/studies + +Modified Files: + diff.py + +-------------------------------------- +Log Message: +Continued studies. +************************************** Date: Sun Apr 11 15:27:42 CEST 2010 Author: stefan Tag: rstdiff_1_11 diff --git a/sandbox/rstdiff/studies/diff.py b/sandbox/rstdiff/studies/diff.py index 8dea6c1db..4ff8a2f41 100644 --- a/sandbox/rstdiff/studies/diff.py +++ b/sandbox/rstdiff/studies/diff.py @@ -2,7 +2,13 @@ from difflib import SequenceMatcher -from hashable import HashableImpl +from hashable import HashableNodeImpl + +from pprint import pprint + +import sys + +__docformat__ = 'reStructuredText' aI = ( 1, 2, 3, 5, 6, 7, ) bI = ( 2, 3, 4, 8, 6 ) @@ -23,55 +29,27 @@ class TreeNode(object): self.tag = tag self.children = children -class HashableTreeNodeImpl(HashableImpl): - - """Consider only the root node (or include the children).""" - # TODO Needs a push/pop methods - rootOnly = False +class HashableTreeNodeImpl(HashableNodeImpl): def __init__(self): super(self.__class__, self).__init__(TreeNode) - def impl__hash__(self, this): - rootHash = self.rootHash(this) - if self.rootOnly: - return rootHash - else: - return rootHash + self.childrenHash(this) - - def impl__eq__(self, this, other): - if not self.rootEq(this, other): - return False - if self.rootOnly: - return True - return self.childrenEq(this, other) - - def rootHash(self, this): - """Return a hash for the root only.""" - return hash(this.tag) - - def childrenHash(self, this): - """Return a hash for the children only.""" - return reduce(lambda x, y: x + y, - [ hash(child) - for child in this.children ], 0) - - def rootEq(self, this, other): - """True if the two nodes as roots are equal without considering their - children. This should be true if one node can be replaced by - the other and all changes can be represented without changing - the node itself.""" - return type(this) == type(other) and this.tag == other.tag - - def childrenEq(self, this, other): - """True if the children of the two nodes are equal without considering - the root features.""" - if len(this.children) != len(other.children): - return False - for i in xrange(len(this.children)): - if not (this.children[i] == other.children[i]): - return False - return hashableImpl + def rootHash(self, node): + return hash(node.tag) + + def childHash(self, node): + """Return a hash for the children only. Subclasses should override + this.""" + return hash(node) + + def rootEq(self, node, other): + return type(node) == type(other) and node.tag == other.tag + + def childEq(self, node, other): + return node == other + + def getChildren(self, node): + return node.children # To generate a diff tree: # @@ -82,10 +60,10 @@ class HashableTreeNodeImpl(HashableImpl): # * ``replace`` opcodes need to be analyzed recursively to find a # minimal set of changes -def resolveDeepReplace(hashableImpl, opcodes, a, b): +def resolveDeepReplace(hashableNodeImpl, opcodes, a, b): """Resolves ``replace`` elements in `opcodes` pertaining to `a` and `b`. Returns opcodes including nested elements for these cases. - `hashableImpl` is the `HashableImpl` used to control the hashable + `hashableNodeImpl` is the `HashableNodeImpl` used to control the hashable feature.""" result = [ ] for i in xrange(len(opcodes)): @@ -94,8 +72,7 @@ def resolveDeepReplace(hashableImpl, opcodes, a, b): result.append(opcodes[i]) continue try: - savedRootOnly = hashableImpl.rootOnly - hashableImpl.rootOnly = True + hashableNodeImpl.pushRootOnly(True) sm = SequenceMatcher(None, a[aBeg:aEnd], b[bBeg:bEnd]) rootOpcodes = sm.get_opcodes() for j in xrange(len(rootOpcodes)): @@ -109,36 +86,37 @@ def resolveDeepReplace(hashableImpl, opcodes, a, b): bIdx = bBeg + bSubBeg + k result.append(('descend', aIdx, aIdx + 1, bIdx, bIdx + 1, - resolveRootEqual(hashableImpl, + resolveRootEqual(hashableNodeImpl, a[aIdx], b[bIdx]), )) finally: - hashableImpl.rootOnly = savedRootOnly + hashableNodeImpl.popRootOnly() return result -def resolveRootEqual(hashableImpl, aElem, bElem): +def resolveRootEqual(hashableNodeImpl, aElem, bElem): """Considers children of `aElem` and `bElem` which have equal roots. - Returns opcodes for the children. `hashableImpl` is the - `HashableImpl` used to control the hashable feature.""" - a = aElem.children - b = bElem.children + Returns opcodes for the children. `hashableNodeImpl` is the + `HashableNodeImpl` used to control the hashable feature.""" + a = hashableNodeImpl.getChildren(aElem) + b = hashableNodeImpl.getChildren(bElem) try: - savedRootOnly = hashableImpl.rootOnly - hashableImpl.rootOnly = False + hashableNodeImpl.pushRootOnly(False) sm = SequenceMatcher(None, a, b) nestedOpcodes = sm.get_opcodes() - return resolveDeepReplace(hashableImpl, nestedOpcodes, a, b) + return resolveDeepReplace(hashableNodeImpl, nestedOpcodes, a, b) finally: - hashableImpl.rootOnly = savedRootOnly + hashableNodeImpl.popRootOnly() -hashableImpl = HashableTreeNodeImpl() +hashableNodeImpl = HashableTreeNodeImpl() aT = ( TreeNode('first'), TreeNode('second', ( TreeNode('second.first'), + TreeNode('second.second'), )), TreeNode('third', ( TreeNode(2), )), + TreeNode('fourth'), ) bT = ( TreeNode('first'), @@ -146,6 +124,7 @@ bT = ( TreeNode('first'), TreeNode('second.first', ( TreeNode('second.first.first'), )), + TreeNode('second.second1'), TreeNode('second.second'), )), TreeNode('second1', ( @@ -154,12 +133,14 @@ bT = ( TreeNode('first'), TreeNode('third', ( TreeNode(2), )), - TreeNode('fourth'), + TreeNode('fourth1'), ) sm = SequenceMatcher(None, aT, bT) top = sm.get_opcodes() -print(top) +pprint(top) print('---') # Use a pseudo root -print(resolveRootEqual(hashableImpl, TreeNode(None, aT), TreeNode(None, bT))) +pprint(resolveRootEqual(hashableNodeImpl, + TreeNode(None, aT), TreeNode(None, bT)), + sys.stdout, 2, 40, None) diff --git a/sandbox/rstdiff/studies/hashable.py b/sandbox/rstdiff/studies/hashable.py index a686bebc2..c3e2da060 100644 --- a/sandbox/rstdiff/studies/hashable.py +++ b/sandbox/rstdiff/studies/hashable.py @@ -2,20 +2,28 @@ from docutils.nodes import Node +__docformat__ = 'reStructuredText' + class HashableDescriptor(object): """A descriptor to plug into a class to be made hashable.""" + """Name of function to override.""" override = None + """Arity of function to override.""" arity = None hashableImpl = None debug = False def __init__(self, override, arity, hashableImpl): + """Initialize a descriptor for function `override` with `arity` using + `hashableImpl`.""" self.override = override self.arity = arity self.hashableImpl = hashableImpl def __get__(self, instance, owner): + """Implements the descriptor protocol. Returns a function to use on + `instance`.""" if self.debug: print('__get__ called on ' + owner.__name__ + ' by ' + self.override) @@ -24,11 +32,15 @@ class HashableDescriptor(object): except: if self.debug: print('***Exception***') - raise AttributeError('Can not access method ' + repr(self.override)) + raise AttributeError('Can not access method %r' + % ( self.override, )) if self.arity == 0: return lambda: fct(instance) - else: + elif self.arity == 1: return lambda other: fct(instance, other) + else: + raise AttributeError('Can not create function for %r with arity %d' + % ( self.override, self.arity, )) class HashableImpl(object): """Implements hashability and reflexive equality for a class.""" @@ -65,13 +77,106 @@ class HashableImpl(object): return not self.impl__eq__(this, other) class HashableNodeImpl(HashableImpl): - """Implements equality for a `Node`.""" + """An abstract implementation of `HashableImpl` for nodes in a tree. + Allows switching between of root only comparison and deep + comparison.""" + + """Consider only the root node (or include the children).""" + _rootOnly = False + """Stack for `_rootOnly`""" + __rootOnlies = [ ] + + def __init__(self, cls): + HashableImpl.__init__(self, cls) + + def pushRootOnly(self, newRootOnly): + """Set `newRootOnly` as new `rootOnly` value. If ``True`` then only + information in the root is considered.""" + self.__rootOnlies.append(self._rootOnly) + self._rootOnly = newRootOnly + + def popRootOnly(self): + """Pop and return last `rootOnly` value.""" + self._rootOnly = self.__rootOnlies.pop() + + def impl__hash__(self, node): + """Returns the hash for node `node`. Subclasses may override this but + overriding `rootHash` and `childrenHash` may make more sense.""" + rootHash = self.rootHash(node) + if self._rootOnly: + return rootHash + else: + return rootHash + self.childrenHash(node) + + def impl__eq__(self, node, other): + """Returns equality between `node` and an `other` node. Subclasses may + override this but overriding `rootEq` and `childrenEq` may + make more sense.""" + if not self.rootEq(node, other): + return False + if self._rootOnly: + return True + return self.childrenEq(node, other) + + def childrenHash(self, node): + """Return a hash for the children only. Subclasses may override + this but overriding `childHash` may make more sense.""" + return reduce(lambda x, y: x + y, + [ self.childHash(child) + for child in self.getChildren(node) ], 0) + + def childrenEq(self, node, other): + """Returns children equality of `node` and an `other` node. ``True`` + if the children of the two nodes are equal without considering + the root. Subclasses may override this but overriding + `childEq` may make more sense.""" + nodeChildren = self.getChildren(node) + otherChildren = self.getChildren(other) + if len(nodeChildren) != len(otherChildren): + return False + for i in xrange(len(nodeChildren)): + if not self.childEq(nodeChildren[i], otherChildren[i]): + return False + return True + + def rootHash(self, node): + """Return a hash for the root only. Subclasses must override + this.""" + raise NotImplementedError() + + def childHash(self, node): + """Return a hash for the node as a child. Subclasses must override + this.""" + raise NotImplementedError() + + def rootEq(self, node, other): + """Returns root equality of `node` and an `other` node. ``True`` if + the two nodes as roots are equal without considering their + children. This should be true if one node can be replaced by + the other and all changes can be represented without changing + the node itself. Subclasses must override this.""" + raise NotImplementedError() + + def childEq(self, node, other): + """Returns equality of `node` and an `other` node as children. + ``True`` if the child features of the two nodes are equal + without considering the root. Subclasses must override + this.""" + raise NotImplementedError() + + def getChildren(self, node): + """Return the children of `node` as a list. Subclasses must override + this.""" + raise NotImplementedError() + +class HashableDocutilsNodeImpl(HashableImpl): + """Implements equality for a docutils `Node`.""" def __init__(self): super(self.__class__, self).__init__(Node) if __name__ == '__main__': - hashableImpl = HashableNodeImpl() + hashableImpl = HashableDocutilsNodeImpl() hashableImpl.debug = True n1 = Node() diff --git a/sandbox/rstdiff/tag.log b/sandbox/rstdiff/tag.log index 24bea2e47..95d6761c9 100644 --- a/sandbox/rstdiff/tag.log +++ b/sandbox/rstdiff/tag.log @@ -1 +1 @@ -rstdiff_1_11 +rstdiff_1_14 -- 2.11.4.GIT