SystemOrganization addCategory: #'DiffMerge-Diffing'! SystemOrganization addCategory: #'DiffMerge-Tests'! SystemOrganization addCategory: #'DiffMerge-Merging'! Object subclass: #Diff3 instanceVariableNames: 'file1 file0 file2 diffClass' classVariableNames: '' poolDictionaries: '' category: 'DiffMerge-Merging'! !Diff3 commentStamp: 'tonyg 6/17/2008 01:00' prior: 0! Diff3 provides a three-way-merge algorithm suitable for performing textual merges, such as are often required as part of source-code version control systems. Instance Variables diffClass: Should be a subclass of GenericDiff. Used to resolve changes. file0: The ancestral file. file1: The left branch. file2: The right branch. -- Copyright (c) 2008 Tony Garnock-Jones Copyright (c) 2008 LShift Ltd. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction,including without limitation the rights to use, copy, modify, merge,publish, distribute, sublicense, and/or sell copies of the Software,and to permit persons to whom the Software is furnished to do so,subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. ! !Diff3 methodsFor: 'private' stamp: 'tonyg 6/16/2008 23:30'! addCommonChunkTo: result between: commonOffset and: targetOffset targetOffset > commonOffset ifTrue: [ result add: (Diff3Chunk new side: #original; offset: commonOffset; length: targetOffset - commonOffset)]. ^ targetOffset ! ! !Diff3 methodsFor: 'private' stamp: 'tonyg 6/17/2008 00:11'! computeConflictFrom: i1 to: i2 hunks: hunks | hunk conflict l o r chunk | conflict := Diff3Conflict new. conflict left: (l := DiffChunk new). conflict original: (o := DiffChunk new). conflict right: (r := DiffChunk new). o offset: (hunks at: i1) oldChunk offset. o length: (hunks at: i2) oldChunk lastIndex - o offset + 1. l offset: file1 size; length: -1. r offset: file2 size; length: -1. i1 to: i2 do: [:index | hunk := hunks at: index. chunk := (hunk side = #left) ifTrue: [l] ifFalse: [r]. chunk offset: (chunk offset min: hunk newChunk offset). chunk length: (chunk length max: (hunk newChunk lastIndex - chunk offset + 1))]. ^ conflict! ! !Diff3 methodsFor: 'private' stamp: 'tonyg 6/16/2008 23:14'! computeHunks | diff2 diff1 hunks | diff1 := diffClass new file1: file0; file2: file1; diffIndices. diff2 := diffClass new file1: file0; file2: file2; diffIndices. hunks := OrderedCollection new. diff1 do: [ :entry | hunks add: (Diff3Hunk side: #left entry: entry) ]. diff2 do: [ :entry | hunks add: (Diff3Hunk side: #right entry: entry) ]. ^ hunks asSortedCollection! ! !Diff3 methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 22:28'! diffClass ^ diffClass! ! !Diff3 methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 22:28'! diffClass: anObject diffClass := anObject! ! !Diff3 methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 22:28'! file0 ^ file0! ! !Diff3 methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 22:28'! file0: anObject file0 := anObject! ! !Diff3 methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 22:28'! file1 ^ file1! ! !Diff3 methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 22:28'! file1: anObject file1 := anObject! ! !Diff3 methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 22:28'! file2 ^ file2! ! !Diff3 methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 22:28'! file2: anObject file2 := anObject! ! !Diff3 methodsFor: 'private' stamp: 'tonyg 6/16/2008 23:59'! fileMap | files | files := Dictionary new. files at: #left put: file1. files at: #original put: file0. files at: #right put: file2. ^ files! ! !Diff3 methodsFor: 'private' stamp: 'tonyg 6/16/2008 23:20'! findOverlapStartingAt: startIndex in: hunks | regionRhs hunk | regionRhs := (hunks at: startIndex) oldChunk lastIndex. startIndex + 1 to: hunks size do: [:index | hunk := hunks at: index. hunk oldChunk offset > regionRhs ifTrue: [^ index - 1]. regionRhs := hunk oldChunk lastIndex]. ^ hunks size.! ! !Diff3 methodsFor: 'merging' stamp: 'tonyg 6/17/2008 01:22'! merge "Returns an Array of (#ok -> {...}) or (#conflict -> Diff3Conflict of collections) instances representing the results of a three-way merge between file1/file0/file2. Does not optimistically treat 'false conflicts' as clean merges (see the class comment for Diff3InclusiveVisitor)." ^ self merge: false! ! !Diff3 methodsFor: 'private' stamp: 'tonyg 6/17/2008 00:44'! merge: excludeFalseConflicts | visitor | visitor := excludeFalseConflicts ifTrue: [Diff3ExclusiveVisitor new] ifFalse: [Diff3InclusiveVisitor new]. visitor files: self fileMap. self mergeIndices do: [:each | each accept: visitor]. ^ visitor result ! ! !Diff3 methodsFor: 'merging' stamp: 'tonyg 6/17/2008 01:22'! mergeClean "Returns an Array of (#ok -> {...}) or (#conflict -> Diff3Conflict of collections) instances representing the results of a three-way merge between file1/file0/file2. Optimistically treats 'false conflicts' as clean merges (see the class comment for Diff3ExclusiveVisitor)." ^ self merge: true! ! !Diff3 methodsFor: 'merging' stamp: 'tonyg 6/17/2008 01:24'! mergeIndices "Returns an Array of Diff3Chunks (representing clean merges) or Diff3Conflicts (containing DiffChunks, representing conflicts), together representing the results of a three-way merge between file1/file0/file2. Does not detect 'false conflicts', and can return two Diff3Chunks next to each other in the result." | result commonOffset hunks lastOverlapHunkIndex hunk firstHunkIndex | hunks := self computeHunks. result := OrderedCollection new. commonOffset := 1. firstHunkIndex := 1. [firstHunkIndex <= hunks size] whileTrue: [ hunk := hunks at: firstHunkIndex. self addCommonChunkTo: result between: commonOffset and: hunk oldChunk offset. lastOverlapHunkIndex := self findOverlapStartingAt: firstHunkIndex in: hunks. (firstHunkIndex = lastOverlapHunkIndex) ifTrue: [(hunk newChunk length > 0) ifTrue: [result add: (Diff3Chunk side: hunk side chunk: hunk newChunk)]] ifFalse: [result add: (self computeConflictFrom: firstHunkIndex to: lastOverlapHunkIndex hunks: hunks)]. commonOffset := (hunks at: lastOverlapHunkIndex) oldChunk lastIndex + 1. firstHunkIndex := lastOverlapHunkIndex + 1]. self addCommonChunkTo: result between: commonOffset and: file0 size + 1. ^ result asArray! ! Object subclass: #Diff3Conflict instanceVariableNames: 'left original right' classVariableNames: '' poolDictionaries: '' category: 'DiffMerge-Merging'! !Diff3Conflict commentStamp: 'tonyg 6/17/2008 01:03' prior: 0! A Diff3Conflict represents a merge conflict. Instance Variables left: Either a SequenceableCollection or a Diff3Chunk representing the left variant. original: Either a SequenceableCollection or a Diff3Chunk representing the original variant. right: Either a SequenceableCollection or a Diff3Chunk representing the right variant. ! !Diff3Conflict methodsFor: 'as yet unclassified' stamp: 'tonyg 6/17/2008 00:33'! = otherConflict ^ (otherConflict isKindOf: Diff3Conflict) and: [(left = otherConflict left) and: [(original = otherConflict original) and: [(right = otherConflict right)]]]! ! !Diff3Conflict methodsFor: 'as yet unclassified' stamp: 'tonyg 6/16/2008 23:35'! accept: aVisitor ^ aVisitor left: left original: original right: right.! ! !Diff3Conflict methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 23:32'! left ^ left! ! !Diff3Conflict methodsFor: 'accessing' stamp: 'tonyg 6/17/2008 00:10'! left: anObject left := anObject! ! !Diff3Conflict methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 23:32'! original ^ original! ! !Diff3Conflict methodsFor: 'accessing' stamp: 'tonyg 6/17/2008 00:10'! original: anObject original := anObject! ! !Diff3Conflict methodsFor: 'as yet unclassified' stamp: 'tonyg 6/17/2008 00:29'! printOn: aStream aStream nextPut: $(; nextPutAll: self class name; nextPutAll: ' new left: '. left printOn: aStream. aStream nextPutAll: '; original: '. original printOn: aStream. aStream nextPutAll: '; right: '. right printOn: aStream. aStream nextPut: $).! ! !Diff3Conflict methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 23:32'! right ^ right! ! !Diff3Conflict methodsFor: 'accessing' stamp: 'tonyg 6/17/2008 00:10'! right: anObject right := anObject! ! Object subclass: #Diff3Hunk instanceVariableNames: 'side oldChunk newChunk' classVariableNames: '' poolDictionaries: '' category: 'DiffMerge-Merging'! !Diff3Hunk commentStamp: 'tonyg 6/17/2008 01:04' prior: 0! A Diff3Hunk represents a change from the ancestor to either the left or the right branch as part of a three-way merge. Instance Variables newChunk: The new content chunk oldChunk: The old (ancestral) content chunk side: Either #left or #right ! !Diff3Hunk class methodsFor: 'as yet unclassified' stamp: 'tonyg 6/16/2008 23:14'! side: aSelector entry: anAssociation ^ self new side: aSelector; oldChunk: anAssociation key; newChunk: anAssociation value! ! !Diff3Hunk methodsFor: 'comparing' stamp: 'tonyg 6/16/2008 23:15'! <= otherHunk ^ (oldChunk < otherHunk oldChunk) or: [(otherHunk oldChunk = oldChunk) and: [side = #left]]! ! !Diff3Hunk methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 23:11'! newChunk ^ newChunk! ! !Diff3Hunk methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 23:11'! newChunk: anObject newChunk := anObject! ! !Diff3Hunk methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 23:11'! oldChunk ^ oldChunk! ! !Diff3Hunk methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 23:11'! oldChunk: anObject oldChunk := anObject! ! !Diff3Hunk methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 23:11'! side ^ side! ! !Diff3Hunk methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 23:11'! side: anObject side := anObject! ! Object subclass: #Diff3InclusiveVisitor instanceVariableNames: 'result okLines files' classVariableNames: '' poolDictionaries: '' category: 'DiffMerge-Merging'! !Diff3InclusiveVisitor commentStamp: 'tonyg 6/17/2008 01:06' prior: 0! A Diff3InclusiveVisitor is used by Diff3 to construct a three-way SequenceableCollection merge that treats "false conflicts" (a.k.a "accidental clean merges") as true conflicts. Instance Variables files: Used to extract the elements for each part of the result okLines: Used to buffer up lists of non-conflicting elements result: Accumulator -- Copyright (c) 2008 Tony Garnock-Jones Copyright (c) 2008 LShift Ltd. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction,including without limitation the rights to use, copy, modify, merge,publish, distribute, sublicense, and/or sell copies of the Software,and to permit persons to whom the Software is furnished to do so,subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. ! Diff3InclusiveVisitor subclass: #Diff3ExclusiveVisitor instanceVariableNames: '' classVariableNames: '' poolDictionaries: '' category: 'DiffMerge-Merging'! !Diff3ExclusiveVisitor commentStamp: 'tonyg 6/17/2008 01:07' prior: 0! A Diff3ExclusiveVisitor is used by Diff3 to construct a three-way SequenceableCollection merge that resolves "false conflicts" (a.k.a "accidental clean merges") by accepting the changed text as a non-conflict in the merge result. -- Copyright (c) 2008 Tony Garnock-Jones Copyright (c) 2008 LShift Ltd. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction,including without limitation the rights to use, copy, modify, merge,publish, distribute, sublicense, and/or sell copies of the Software,and to permit persons to whom the Software is furnished to do so,subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. ! !Diff3ExclusiveVisitor methodsFor: 'as yet unclassified' stamp: 'tonyg 6/17/2008 01:26'! isTrueConflictBetween: left and: right "A conflict is 'false' when, from a particular ancestral snippet, both the left and right branches have changed to have the same contents. In some circumstances this can be treated as a clean merge; in others, it's actually an exception that needs to be dealt with. See http://revctrl.org/AccidentalCleanMerge." left length = right length ifFalse: [^true]. (left extractFrom: (files at: #left)) = (right extractFrom: (files at: #right)) ifFalse: [^true]. ^false! ! !Diff3ExclusiveVisitor methodsFor: 'as yet unclassified' stamp: 'tonyg 6/17/2008 00:41'! left: left original: original right: right (self isTrueConflictBetween: left and: right) ifTrue: [super left: left original: original right: right] ifFalse: [self side: #left chunk: left] ! ! !Diff3InclusiveVisitor methodsFor: 'as yet unclassified' stamp: 'tonyg 6/17/2008 00:04'! files: aDictionary files := aDictionary! ! !Diff3InclusiveVisitor methodsFor: 'as yet unclassified' stamp: 'tonyg 6/17/2008 00:14'! flushOk okLines isEmpty ifFalse: [ result add: #ok -> okLines asArray. okLines := OrderedCollection new].! ! !Diff3InclusiveVisitor methodsFor: 'as yet unclassified' stamp: 'tonyg 6/17/2008 00:12'! initialize result := OrderedCollection new. okLines := OrderedCollection new.! ! !Diff3InclusiveVisitor methodsFor: 'as yet unclassified' stamp: 'tonyg 6/17/2008 00:16'! left: left original: original right: right | c | self flushOk. c := Diff3Conflict new. c left: (left extractFrom: (files at: #left)). c original: (original extractFrom: (files at: #original)). c right: (right extractFrom: (files at: #right)). result add: #conflict -> c.! ! !Diff3InclusiveVisitor methodsFor: 'as yet unclassified' stamp: 'tonyg 6/17/2008 00:15'! result self flushOk. ^ result asArray! ! !Diff3InclusiveVisitor methodsFor: 'as yet unclassified' stamp: 'tonyg 6/17/2008 00:14'! side: aSelector chunk: aChunk okLines addAll: (aChunk extractFrom: (files at: aSelector)).! ! Object subclass: #DiffChunk instanceVariableNames: 'offset length' classVariableNames: '' poolDictionaries: '' category: 'DiffMerge-Diffing'! !DiffChunk commentStamp: 'tonyg 6/17/2008 00:51' prior: 0! A DiffChunk represents a span of items within a collection (e.g. a collection of lines representing a text file). Instance Variables length: Count of lines within the chunk; 0 is permitted offset: Index of first line within the chunk; 1-based ! DiffChunk subclass: #Diff3Chunk instanceVariableNames: 'side' classVariableNames: '' poolDictionaries: '' category: 'DiffMerge-Merging'! !Diff3Chunk commentStamp: 'tonyg 6/17/2008 01:02' prior: 0! A Diff3Chunk is a subclass of DiffChunk that also knows which side of a three-way merge it represents. Instance Variables side: One of #left, #original or #right ! !Diff3Chunk class methodsFor: 'as yet unclassified' stamp: 'tonyg 6/16/2008 23:30'! side: aSelector chunk: aChunk ^ self new side: aSelector; offset: aChunk offset; length: aChunk length! ! !Diff3Chunk methodsFor: 'as yet unclassified' stamp: 'tonyg 6/17/2008 00:32'! = otherChunk ^ (otherChunk isKindOf: Diff3Chunk) and: [(super = otherChunk) and: [side = otherChunk side]]! ! !Diff3Chunk methodsFor: 'as yet unclassified' stamp: 'tonyg 6/16/2008 23:34'! accept: aVisitor ^ aVisitor side: side chunk: self! ! !Diff3Chunk methodsFor: 'as yet unclassified' stamp: 'tonyg 6/16/2008 23:52'! printOn: aStream aStream nextPut: $(. super printOn: aStream. aStream nextPutAll: ' side: '; nextPutAll: side printString; nextPut: $).! ! !Diff3Chunk methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 23:21'! side ^ side! ! !Diff3Chunk methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 23:21'! side: anObject side := anObject! ! !DiffChunk class methodsFor: 'as yet unclassified' stamp: 'tonyg 6/16/2008 23:48'! offset: o length: l ^ self new offset: o; length: l! ! !DiffChunk methodsFor: 'comparing' stamp: 'tonyg 6/17/2008 01:09'! < aDiffChunk "Used to sort changed chunks during three-way merge; see Diff3" ^ self offset < aDiffChunk offset! ! !DiffChunk methodsFor: 'comparing' stamp: 'tonyg 6/16/2008 22:11'! = otherChunk ^ (otherChunk isKindOf: DiffChunk) and: [(self offset = otherChunk offset) and: [(self length = otherChunk length)]]! ! !DiffChunk methodsFor: 'as yet unclassified' stamp: 'tonyg 6/17/2008 01:09'! extractFrom: aCollection "Extracts a subcollection from aCollection corresponding to my offset and length." ^ aCollection copyFrom: offset to: offset + length - 1.! ! !DiffChunk methodsFor: 'accessing' stamp: 'tonyg 6/17/2008 01:10'! lastIndex "Returns the rightmost index contained in my range. (Offset is the leftmost index.) If my length is zero, will return an index lower than my offset." ^ offset + length - 1! ! !DiffChunk methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 21:15'! length ^ length! ! !DiffChunk methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 23:48'! length: anObject length := anObject! ! !DiffChunk methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 21:15'! offset ^ offset! ! !DiffChunk methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 23:48'! offset: anObject offset := anObject! ! !DiffChunk methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 21:39'! printOn: aStream aStream nextPut: $(; nextPutAll: self class name; nextPutAll: ' offset: '; nextPutAll: self offset asString; nextPutAll: ' length: '; nextPutAll: self length asString; nextPut: $).! ! Object subclass: #DiffPatch instanceVariableNames: 'chunks snippets' classVariableNames: '' poolDictionaries: '' category: 'DiffMerge-Diffing'! !DiffPatch commentStamp: 'tonyg 6/17/2008 00:54' prior: 0! A DiffPatch has a collection of DiffChunks, and a collection of corresponding SequenceableCollection snippets. It can be used to patch a file (= SequenceableCollection) forwards or backwards. Instance Variables chunks: DiffChunk> snippets: SequenceableCollection> ! !DiffPatch methodsFor: 'accessing' stamp: 'tonyg 6/17/2008 01:12'! applyTo: file "Applies this patch to the given collection. Makes no sanity checks on the contents of the collection - simply blindly applies the chunks and snippets to its argument." | result commonOffset | result := OrderedCollection new. commonOffset := 1. chunks with: snippets do: [:chunk :snippet | result addAll: (file copyFrom: commonOffset to: chunk key offset - 1). result addAll: (snippet value). commonOffset := chunk key offset + chunk key length]. result addAll: (file copyFrom: commonOffset to: file size). ^ result as: file species.! ! !DiffPatch methodsFor: 'as yet unclassified' stamp: 'tonyg 6/16/2008 22:16'! initChunks: c file1: f1 file2: f2 chunks := c. snippets := c collect: [:entry | (entry key extractFrom: f1) -> (entry value extractFrom: f2)].! ! !DiffPatch methodsFor: 'selecting' stamp: 'tonyg 6/17/2008 01:14'! invert "Causes this patch to invert itself; if previously it represented the changes from file1 to file2, after being sent #invert, it will represent the changes from file2 to file1. After inversion, calling #applyTo: on file2 will yield file1, rather than the other way around." chunks do: [:entry | entry key: entry value value: entry key]. snippets do: [:entry | entry key: entry value value: entry key]. ! ! Object subclass: #GenericDiff instanceVariableNames: 'file1 file2' classVariableNames: '' poolDictionaries: '' category: 'DiffMerge-Diffing'! !GenericDiff commentStamp: 'tonyg 6/17/2008 00:55' prior: 0! Generic diff/comm utilities. Agnostic as to the longestCommonSubsequence algorithm used. Instance Variables file1: One of the two files to compare. file2: The other of the files to compare. -- Copyright (c) 2008 Tony Garnock-Jones Copyright (c) 2008 LShift Ltd. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction,including without limitation the rights to use, copy, modify, merge,publish, distribute, sublicense, and/or sell copies of the Software,and to permit persons to whom the Software is furnished to do so,subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. ! !GenericDiff methodsFor: 'private' stamp: 'tonyg 6/16/2008 21:57'! addCommonBlock: aSubCollection ifNonEmptyTo: aCollection ^ aSubCollection isEmpty ifFalse: [aCollection add: #common -> aSubCollection asArray. OrderedCollection new] ifTrue: [aSubCollection]! ! !GenericDiff methodsFor: 'diffing' stamp: 'tonyg 6/17/2008 01:17'! comm "Returns a collection of similarities and differences between the two files. Each entry in the resulting collection is either (#common -> {...}) or (#different -> ({...} -> {...}))." | result common p1 p2 | result := OrderedCollection new. p1 := 0. p2 := 0. common := OrderedCollection new. self longestCommonSubsequence do: [:entry | ((p1 + 1 ~= entry key) or: [p2 + 1 ~= entry value]) ifTrue: [common := self addCommonBlock: common ifNonEmptyTo: result. result add: #different -> ((file1 copyFrom: p1 + 1 to: entry key - 1) -> (file2 copyFrom: p2 + 1 to: entry value - 1))]. common add: (self file1 at: entry key). p1 := entry key. p2 := entry value.]. self addCommonBlock: common ifNonEmptyTo: result. ^ result asArray! ! !GenericDiff methodsFor: 'diffing' stamp: 'tonyg 6/17/2008 01:15'! diff "Returns a DiffPatch instance that can be used in future to transform file1 into file2." | p | p := DiffPatch new. p initChunks: self diffIndices file1: file1 file2: file2. ^ p! ! !GenericDiff methodsFor: 'diffing' stamp: 'tonyg 6/17/2008 01:16'! diffIndices "Returns a collection of (DiffChunk -> DiffChunk) associations mapping differing regions of file1 and file2 onto each other." | result p1 p2 | result := OrderedCollection new. p1 := 0. p2 := 0. self longestCommonSubsequence do: [:entry | ((p1 + 1 ~= entry key) or: [p2 + 1 ~= entry value]) ifTrue: [result add: ((DiffChunk offset: p1 + 1 length: entry key - p1 - 1) -> (DiffChunk offset: p2 + 1 length: entry value - p2 - 1))]. p1 := entry key. p2 := entry value.]. ^ result asArray! ! !GenericDiff methodsFor: 'private' stamp: 'tonyg 6/17/2008 01:16'! emptyCaches "Subclasses should implement this to clear any cached state they may have built up."! ! !GenericDiff methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 21:29'! file1 ^ file1! ! !GenericDiff methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 21:30'! file1: anObject file1 := anObject. self emptyCaches. ! ! !GenericDiff methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 21:30'! file2 ^ file2! ! !GenericDiff methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 21:30'! file2: anObject file2 := anObject. self emptyCaches.! ! !GenericDiff methodsFor: 'diffing' stamp: 'tonyg 6/17/2008 01:18'! longestCommonSubsequence "The longestCommonSubsequence (LCS) algorithm is at the heart of a diff/comm algorithm." self subclassResponsibility.! ! GenericDiff subclass: #HuntMcilroyDiff instanceVariableNames: 'lcs' classVariableNames: '' poolDictionaries: '' category: 'DiffMerge-Diffing'! !HuntMcilroyDiff commentStamp: 'tonyg 6/17/2008 00:58' prior: 0! A HuntMcilroyDiff provides a longestCommonSubsequence algorithm following Hunt and McIlroy 1976 for use by the methods on GenericDiff. J. W. Hunt and M. D. McIlroy, An algorithm for differential file comparison, Bell Telephone Laboratories CSTR #41 (1976). http://www.cs.dartmouth.edu/~doug/ Instance Variables lcs: cached longest common subsequence -- Copyright (c) 2008 Tony Garnock-Jones Copyright (c) 2008 LShift Ltd. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction,including without limitation the rights to use, copy, modify, merge,publish, distribute, sublicense, and/or sell copies of the Software,and to permit persons to whom the Software is furnished to do so,subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. ! !HuntMcilroyDiff methodsFor: 'private' stamp: 'tonyg 6/16/2008 20:50'! computeEquivalenceClasses | result | result := Dictionary new. file2 withIndexDo: [ :line :index | (result at: line ifAbsentPut: [ OrderedCollection new ]) add: index ]. ^ result! ! !HuntMcilroyDiff methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 21:29'! emptyCaches lcs := nil.! ! !HuntMcilroyDiff methodsFor: 'private' stamp: 'tonyg 6/16/2008 20:57'! findCandidateFrom: candidates forLine: file2index ^ (1 to: candidates size) findFirst: [ :k | (candidates at: k) file2index < file2index and: [ k = candidates size or: [ (candidates at: k + 1) file2index > file2index ] ] ]! ! !HuntMcilroyDiff methodsFor: 'diffing' stamp: 'tonyg 6/16/2008 21:00'! longestCommonSubsequence | equivalenceClasses candidates | lcs ifNotNil: [ ^ lcs ]. equivalenceClasses := self computeEquivalenceClasses. candidates := OrderedCollection with: (HuntMcilroyDiffCandidate new file1index: 0 file2index: 0 chain: nil). file1 withIndexDo: [ :line :file1index | self mergeCandidates: candidates file1index: file1index file2indices: (equivalenceClasses at: line ifAbsent: #()) ]. lcs := self postprocessCandidateChain: candidates. ^ lcs! ! !HuntMcilroyDiff methodsFor: 'private' stamp: 'tonyg 6/16/2008 20:55'! mergeCandidates: candidates file1index: file1index file2indices: file2indices | r s c | r := 1. c := candidates at: r. file2indices do: [ :file2index | s := self findCandidateFrom: candidates forLine: file2index. s > 0 ifTrue: [ self storeCandidate: c at: r in: candidates. c := HuntMcilroyDiffCandidate new file1index: file1index file2index: file2index chain: (candidates at: s). r := s + 1. s = candidates size ifTrue: [ self storeCandidate: c at: r in: candidates. ^ self ] ] ]. self storeCandidate: c at: r in: candidates.! ! !HuntMcilroyDiff methodsFor: 'private' stamp: 'tonyg 6/16/2008 20:59'! postprocessCandidateChain: candidates | result c | result := OrderedCollection new. c := candidates at: candidates size. [ c chain notNil ] whileTrue: [ result add: c file1index -> c file2index. c := c chain ]. ^ result reversed. ! ! !HuntMcilroyDiff methodsFor: 'private' stamp: 'tonyg 6/16/2008 20:43'! storeCandidate: c at: r in: candidates r > candidates size ifTrue: [candidates add: c] ifFalse: [candidates at: r put: c].! ! Object subclass: #HuntMcilroyDiffCandidate instanceVariableNames: 'file1index file2index chain' classVariableNames: '' poolDictionaries: '' category: 'DiffMerge-Diffing'! !HuntMcilroyDiffCandidate commentStamp: 'tonyg 6/17/2008 00:59' prior: 0! HuntMcilroyDiffCandidate is used internally by HuntMcilroyDiff. Instance Variables chain: Link to next candidate in chain. file1index: Position in file1. file2index: Position in file2. ! !HuntMcilroyDiffCandidate methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 19:41'! chain ^ chain! ! !HuntMcilroyDiffCandidate methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 19:41'! file1index ^ file1index! ! !HuntMcilroyDiffCandidate methodsFor: 'as yet unclassified' stamp: 'tonyg 6/16/2008 19:38'! file1index: f1 file2index: f2 chain: c file1index := f1. file2index := f2. chain := c.! ! !HuntMcilroyDiffCandidate methodsFor: 'accessing' stamp: 'tonyg 6/16/2008 19:41'! file2index ^ file2index! ! TestCase subclass: #Diff3Tests instanceVariableNames: '' classVariableNames: '' poolDictionaries: '' category: 'DiffMerge-Tests'! !Diff3Tests methodsFor: 'as yet unclassified' stamp: 'tonyg 6/16/2008 22:44'! instance ^ Diff3 new file1: #(the quick fox jumps over some lazy dog); file0: #(the quick brown fox jumped over a dog); file2: #(the quick brown fox jumps over some record dog); diffClass: HuntMcilroyDiff.! ! !Diff3Tests methodsFor: 'as yet unclassified' stamp: 'tonyg 6/17/2008 00:45'! testMergeExcludingFalseConflicts | m | m := self instance mergeClean. self assert: [m = { #ok->#(#the #quick #fox #jumps #over) . #conflict->(Diff3Conflict new left: #(#some #lazy); original: #(#a); right: #(#some #record)) . #ok->#(#dog) }].! ! !Diff3Tests methodsFor: 'as yet unclassified' stamp: 'tonyg 6/17/2008 00:45'! testMergeIncludingFalseConflicts | m | m := self instance merge. self assert: [m = { #ok->#(#the #quick #fox) . #conflict->(Diff3Conflict new left: #(#jumps); original: #(#jumped); right: #(#jumps)) . #ok->#(#over) . #conflict->(Diff3Conflict new left: #(#some #lazy); original: #(#a); right: #(#some #record)) . #ok->#(#dog) }].! ! !Diff3Tests methodsFor: 'as yet unclassified' stamp: 'tonyg 6/17/2008 00:30'! testMergeIndices | m | m := self instance mergeIndices. self assert: [m = { ((Diff3Chunk offset: 1 length: 2) side: #original). ((Diff3Chunk offset: 4 length: 1) side: #original). (Diff3Conflict new left: (DiffChunk offset: 4 length: 1); original: (DiffChunk offset: 5 length: 1); right: (DiffChunk offset: 5 length: 1)). ((Diff3Chunk offset: 6 length: 1) side: #original). (Diff3Conflict new left: (DiffChunk offset: 6 length: 2); original: (DiffChunk offset: 7 length: 1); right: (DiffChunk offset: 7 length: 2)). ((Diff3Chunk offset: 8 length: 1) side: #original) }].! ! TestCase subclass: #HuntMcilroyDiffTests instanceVariableNames: '' classVariableNames: '' poolDictionaries: '' category: 'DiffMerge-Tests'! !HuntMcilroyDiffTests methodsFor: 'as yet unclassified' stamp: 'tonyg 6/16/2008 21:21'! sampleDiff: diffClass ^ diffClass new file1: #(The red brown fox jumped over the rolling log); file2: #(The brown spotted fox leaped over the rolling log). ! ! !HuntMcilroyDiffTests methodsFor: 'as yet unclassified' stamp: 'tonyg 6/16/2008 21:59'! testComm | c | c := (self sampleDiff: HuntMcilroyDiff) comm. self assert: [c = {#common->#(#The) . #different->(#(#red)->#()) . #common->#(#brown) . #different->(#()->#(#spotted)) . #common->#(#fox) . #different->(#(#jumped)->#(#leaped)) . #common->#(#over #the #rolling #log)}].! ! !HuntMcilroyDiffTests methodsFor: 'as yet unclassified' stamp: 'tonyg 6/16/2008 22:24'! testDiffIndices | p | p := (self sampleDiff: HuntMcilroyDiff) diffIndices. self assert: [p = {(DiffChunk offset: 2 length: 1)->(DiffChunk offset: 2 length: 0) . (DiffChunk offset: 4 length: 0)->(DiffChunk offset: 3 length: 1) . (DiffChunk offset: 5 length: 1)->(DiffChunk offset: 5 length: 1)}].! ! !HuntMcilroyDiffTests methodsFor: 'as yet unclassified' stamp: 'tonyg 6/16/2008 22:25'! testDiffPatch | d p f2 | d := self sampleDiff: HuntMcilroyDiff. p := d diff. f2 := p applyTo: d file1. self assert: [f2 = d file2].! ! !HuntMcilroyDiffTests methodsFor: 'as yet unclassified' stamp: 'tonyg 6/16/2008 21:21'! testLcs | lcs | lcs := (self sampleDiff: HuntMcilroyDiff) longestCommonSubsequence asArray. self assert: [lcs = {1->1. 3->2. 4->4. 6->6. 7->7. 8->8. 9->9}]. "({file1index:7, file2index:7, chain:{file1index:6, file2index:6, chain:{file1index:5, file2index:5, chain:{file1index:3, file2index:3, chain:{file1index:2, file2index:1, chain:{file1index:0, file2index:0, chain:{file1index:-1, file2index:-1, chain:null}}}}}}})"! !