'From Cuis 2.0 of 4 January 2010 [latest update: #393] on 12 February 2010 at 9:46:16 am'!
!classDefinition: #DifferenceFinder category: #'System-Code Differ'!
Object subclass: #DifferenceFinder
	instanceVariableNames: 'base case x y map tally matrix differences'
	classVariableNames: 'D EmptyLCS L U UL'
	poolDictionaries: ''
	category: 'System-Code Differ'!

!DifferenceFinder commentStamp: '<historical>' prior: 0!
Count := 0.!

!classDefinition: #DifferenceFinderTest category: #'System-Code Differ'!
TestCase subclass: #DifferenceFinderTest
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'System-Code Differ'!
!classDefinition: #SequenceDifference category: #'System-Code Differ'!
Object subclass: #SequenceDifference
	instanceVariableNames: 'x y lcs'
	classVariableNames: ''
	poolDictionaries: ''
	category: 'System-Code Differ'!

!DifferenceFinder methodsFor: 'accessing'!
base: aCollection case: anotherCollection
	base := aCollection.
	case := anotherCollection.
	x := aCollection.
	y := anotherCollection
! !

!DifferenceFinder methodsFor: 'accessing' stamp: 'LC 1/26/2010 10:23'!
sourceCodeDifferences
	self compareLines; compute.
	self linesAreSimilar ifTrue: [self recomputeWithWords].
	^differences! !

!DifferenceFinder methodsFor: 'private' stamp: 'jmv 2/8/2010 09:48'!
initializeMap
	map := FloatMatrix newHeight: x size width: y size! !

!DifferenceFinder methodsFor: 'private' stamp: 'jmv 2/8/2010 09:46'!
initializeMatrix
	matrix := ObjectMatrix newHeight: x size width: y size! !

!DifferenceFinder methodsFor: 'private'!
keywordsAndBlanksFrom: aString
	^Array streamContents: [:strm | | read keyword tail |
		read := aString readStream.
		[read atEnd] whileFalse: [
			keyword := read nextKeyword.
			strm nextPut: keyword.
			tail := read untilAnySatisfying: [:ch | ch isAlphaNumeric].
			tail notEmpty ifTrue: [strm nextPut: tail]]]
! !

!DifferenceFinder methodsFor: 'private' stamp: 'LC 1/26/2010 10:22'!
linesAreSimilar
	^self similitudeProportion > 0.7! !

!DifferenceFinder methodsFor: 'private'!
linesIn: aString
	"
	LongestCommonSequenceFinder linesIn: 'x y'
	"
	^Array streamContents: [:strm | | cr read |
		cr := '
'.
		read := aString readStream.
		[read atEnd] whileFalse: [| line |
			line := read nextLine.
			read skip: -1.
			read peek = cr last ifTrue: [line := line , cr].
			read skip: 1.
			strm nextPut: line]]
! !

!DifferenceFinder methodsFor: 'private' stamp: 'jmv 2/8/2010 09:37'!
maxLength
"????"
"	tally isEmpty ifTrue: [^0]."
	^tally i: x size j: y size! !

!DifferenceFinder methodsFor: 'private' stamp: 'jmv 2/8/2010 09:41'!
maxLengthPoints
	| max points |
	max := self maxLength.
	max = 0 ifTrue: [^Array with: 0 @ 0].
	points := OrderedCollection new.
	tally withIndexesDo: [:i :j :t | t = max ifTrue: [points add: i @ j]].
	^points! !

!DifferenceFinder methodsFor: 'private' stamp: 'LC 1/26/2010 10:21'!
similitudeProportion
	^self maxLength / (x size + y size / 2)! !

!DifferenceFinder methodsFor: 'private'!
unfold
	| points |
	points := OrderedCollection with: x size @ y size.
	^self unfold: points
! !

!DifferenceFinder methodsFor: 'private'!
unfold: pointCollection
	| pending visited point |
	pending := OrderedCollection withAll: pointCollection.
	visited := OrderedCollection new.
	[pending notEmpty] whileTrue: [
		point := pending removeFirst.
		(visited includes: point) ifFalse: [
			self unfold: point on: pending.
			visited add: point]].
	^visited
! !

!DifferenceFinder methodsFor: 'private' stamp: 'jmv 2/8/2010 09:27'!
unfold: aPoint on: pending
	| i j mij |
	i := aPoint x.
	j := aPoint y.
	(i = 0 or: [j = 0]) ifTrue: [^self].
	mij := map i: i j: j.
	mij = D ifTrue: [
		pending add: i - 1 @ (j - 1).
		^self].
	mij = U ifTrue: [
		pending add: i - 1 @ j.
		^self].
	mij = L ifTrue: [
		pending add: i @ (j - 1).
		^self].
	mij = UL ifTrue: [
		pending add: i - 1 @ j; add: i @ (j - 1).
		^self].
	self ASSERT: false
! !

!DifferenceFinder methodsFor: 'configuration'!
compareCharacters
	x := base.
	y := case
! !

!DifferenceFinder methodsFor: 'configuration'!
compareLines
	x := self linesIn: base.
	y := self linesIn: case
! !

!DifferenceFinder methodsFor: 'configuration'!
compareWords
	x := self keywordsAndBlanksFrom: base.
	y := self keywordsAndBlanksFrom: case
! !

!DifferenceFinder methodsFor: 'computing' stamp: 'LC 1/26/2010 10:21'!
compute
	self initializeMap; initializeMatrix; computeMap.
	differences := self longestSequences asArray
		collect: [:lcs | SequenceDifference x: x y: y lcs: lcs].
	^differences sort! !

!DifferenceFinder methodsFor: 'computing' stamp: 'jmv 2/8/2010 09:26'!
computeLcsAt: i at: j
	| mij cij pair left up |
	mij := map i: i j: j.
	mij = D ifTrue: [
		cij := self lcsAt: i - 1 at: j - 1.
		pair := Array with: i with: j.
		^cij collect: [:s | s copyWith: pair]].
	mij = U ifTrue: [^self lcsAt: i - 1 at: j].
	mij = L ifTrue: [^self lcsAt: i at: j - 1].
	mij = UL ifTrue: [
		left := self lcsAt: i at: j - 1.
		up := self lcsAt: i - 1 at: j.
		^left copy addAll: up; yourself].
	self ASSERT: false
! !

!DifferenceFinder methodsFor: 'computing' stamp: 'jmv 2/8/2010 09:51'!
computeMap
	| m |
	tally := FloatMatrix newHeight: x size width: y size.
	1 to: x size do: [:i | 
		1 to: y size do: [:j | 
			m := self computeMapAt: i at: j.
			map i: i j: j put: m]]
! !

!DifferenceFinder methodsFor: 'computing' stamp: 'jmv 2/8/2010 09:27'!
computeMapAt: i at: j
	| xi yj left up t |
	xi := x at: i.
	yj := y at: j.
	xi = yj ifTrue: [
		t := ((j = 1 or: [i = 1])
			ifTrue: [0]
			ifFalse: [tally i: i - 1 j: j - 1])
			+ 1.
		tally i: i j: j put: t.
		^D].
	left := j = 1 ifTrue: [0] ifFalse: [tally i: i j: j - 1].
	up := i = 1 ifTrue: [0] ifFalse: [tally i: i - 1 j: j].
	left < up ifTrue: [
		tally i: i j: j put: up.
		^U].
	tally i: i j: j put: left.
	^up < left ifTrue: [L] ifFalse: [UL]
! !

!DifferenceFinder methodsFor: 'computing' stamp: 'jmv 2/8/2010 09:26'!
lcsAt: i at: j
	| lcs |
	(i = 0 or: [j = 0]) ifTrue: [^EmptyLCS].
	lcs := matrix i: i j: j.
	lcs isNil ifTrue: [
		lcs := self computeLcsAt: i at: j.
		matrix i: i j: j put: lcs].
	^lcs
! !

!DifferenceFinder methodsFor: 'computing' stamp: 'LC 1/26/2010 10:20'!
longestSequences
	| maxs points |
	maxs := self maxLengthPoints.
	points := self unfold: maxs.
	points
		sortBy: [:p :q | p x < q x or: [p x = q x and: [p y <= q y]]];
		do: [:p | self lcsAt: p x at: p y].
	^(Array streamContents: [:strm | 
		maxs do: [:p | | lcs |
			lcs := self lcsAt: p x at: p y.
			lcs do: [:s | strm nextPut: s]]]) asSet! !

!DifferenceFinder methodsFor: 'computing' stamp: 'LC 1/26/2010 10:22'!
recomputeWithWords
	x := Array new writeStream.
	y := Array new writeStream.
	differences sort first do: [:item :condition | 
		condition == #unchanged ifTrue: [
			x nextPut: item.
			y nextPut: item].
		condition == #removed
			ifTrue: [x nextPutAll: (self keywordsAndBlanksFrom: item)].
		condition == #inserted
			ifTrue: [y nextPutAll: (self keywordsAndBlanksFrom: item)]].
	x := x contents.
	y := y contents.
	self compute! !

!DifferenceFinder methodsFor: 'outputs'!
differences
	^differences
! !

!DifferenceFinder methodsFor: 'compatibility' stamp: 'LC 2/11/2010 23:59'!
buildDisplayPatch
	^self sourceCodeDifferences anyOne asText! !


!DifferenceFinder class methodsFor: 'instance creation'!
base: aCollection case: anotherCollection
	^self new base: aCollection case: anotherCollection
! !

!DifferenceFinder class methodsFor: 'instance creation'!
charactersOf: aString and: anotherString
	| finder |
	finder := self base: aString case: anotherString.
	finder compareCharacters.
	^finder
! !

!DifferenceFinder class methodsFor: 'instance creation'!
linesOf: aString and: anotherString
	| finder |
	finder := self base: aString case: anotherString.
	finder compareLines.
	^finder
! !

!DifferenceFinder class methodsFor: 'instance creation'!
wordsOf: aString and: anotherString
	| finder |
	finder := self base: aString case: anotherString.
	finder compareWords.
	^finder
! !

!DifferenceFinder class methodsFor: 'initialization'!
initialize
	"
	DifferenceFinder initialize
	"
	super initialize.
	EmptyLCS := Set with: #().
	D := 1.
	U := 2.
	L := 3.
	UL := 4
! !

!DifferenceFinder class methodsFor: 'compatibility' stamp: 'jmv 2/12/2010 09:42'!
buildDisplayPatchFrom: srcString to: dstString 

	| finder |
	finder := self base: srcString case: dstString.
	^finder buildDisplayPatch! !

!DifferenceFinder class methodsFor: 'compatibility' stamp: 'jmv 2/12/2010 09:44'!
buildDisplayPatchFrom: s1 to: s2 inClass: sourceClass prettyDiffs: aBoolean

	^(aBoolean and: [ sourceClass notNil ])
		ifFalse: [
			self buildDisplayPatchFrom: s1 to: s2 ]
		ifTrue: [
			self buildDisplayPatchFrom: s1 to: s2 prettyPrintedInClass: sourceClass ]! !

!DifferenceFinder class methodsFor: 'compatibility' stamp: 'jmv 2/12/2010 09:44'!
buildDisplayPatchFrom: srcString to: dstString prettyPrintedInClass: sourceClass
	| formattedSrcString formattedDstString |

	formattedSrcString _ [
		sourceClass compilerClass new
			format: srcString
			in: sourceClass
			notifying: nil ] 
				on: Error
				do: [ :ex | srcString ].
	formattedDstString _ [
		sourceClass compilerClass new
			format: dstString
			in: sourceClass
			notifying: nil ] 
				on: Error
				do: [ :ex | dstString ].
	^self buildDisplayPatchFrom: formattedSrcString to: formattedDstString! !

!DifferenceFinder class methodsFor: 'bibliography' stamp: 'LC 1/24/2010 16:30'!
references
	^'http://en.wikipedia.org/wiki/Longest_common_subsequence'
! !


!DifferenceFinderTest methodsFor: 'all' stamp: 'LC 1/24/2010 11:29'!
testCharacters
	| lcs |
	lcs := DifferenceFinder charactersOf: 'GAC' and: 'AGCAT'.
	lcs compute.
	self
		assert: (lcs lcsAt: 1 at: 1) anyOne size = 0;
		assert: (lcs lcsAt: 1 at: 2) anyOne size = 1;
		assert: (lcs lcsAt: 1 at: 3) anyOne size = 1;
		assert: (lcs lcsAt: 1 at: 4) anyOne size = 1;
		assert: (lcs lcsAt: 1 at: 5) anyOne size = 1;
		assert: (lcs lcsAt: 2 at: 1) anyOne size = 1;
		assert: (lcs lcsAt: 2 at: 2) anyOne size = 1;
		assert: (lcs lcsAt: 2 at: 3) anyOne size = 1;
		assert: (lcs lcsAt: 2 at: 4) anyOne size = 2;
		assert: (lcs lcsAt: 2 at: 5) anyOne size = 2;
		assert: (lcs lcsAt: 3 at: 1) anyOne size = 1;
		assert: (lcs lcsAt: 3 at: 2) anyOne size = 1;
		assert: (lcs lcsAt: 3 at: 3) anyOne size = 2;
		assert: (lcs lcsAt: 3 at: 4) anyOne size = 2;
		assert: (lcs lcsAt: 3 at: 5) anyOne size = 2
! !

!DifferenceFinderTest methodsFor: 'all'!
testCharacters2
	| finder x y |
	finder := DifferenceFinder charactersOf: 'GAC' and: 'AGCAT'.
	finder compute.
	self assert: finder differences size = 3.
	finder differences do: [:diff | 
		x := String streamContents: [:strm | 
			diff
				do: [:char :condition | (#(#removed #unchanged) includes: condition)
					ifTrue: [strm nextPut: char]]].
		self assert: x = 'GAC'.
		y := String streamContents: [:strm | 
			diff
				do: [:char :condition | (#(#inserted #unchanged) includes: condition)
					ifTrue: [strm nextPut: char]]].
		self assert: y = 'AGCAT']
! !

!DifferenceFinderTest methodsFor: 'all'!
testCode
	| old new finder |
	old := 'differencesText
	| change sourceString current diff rtf selectedString |
	change := self selectedMethod ifNil: [self currentClass].
	current := change currentVersion.
	sourceString := current isNil
		ifTrue: ['']
		ifFalse: [current isCompiledMethod ifTrue: [(self
			formatSource: current sourceString
			inClass: current classField)
			sourceCode] ifFalse: [current sourceString]].
	selectedString := (current isNil or: [current isCompiledMethod not])
		ifTrue: [change sourceString]
		ifFalse: [((self
			formatSource: change sourceString
			inClass: current classField) ifNil: [change]) sourceCode].
	diff := TextDiffBuilder from: sourceString to: selectedString.
	rtf := RTFText new setFont: TextFont.
	rtf setTabStops: self tabStops.
	diff run; printPatchSequenceOn: rtf.
	^rtf contents contents'.
	new := 'differencesText
	| change sourceString current finder rtf selectedString |
	change := self selectedMethod ifNil: [self currentClass].
	current := change currentVersion.
	sourceString := current isNil ifTrue: [''] ifFalse: [
		current isCompiledMethod
			ifTrue: [(self
				formatSource: current sourceString
				inClass: current classField)
				sourceCode]
			ifFalse: [current sourceString]].
	selectedString := (current isNil or: [current isCompiledMethod not])
		ifTrue: [change sourceString]
		ifFalse: [((self
			formatSource: change sourceString
			inClass: current classField)
			ifNil: [change])
			sourceCode].
	finder := DifferenceFinder wordsOf: sourceString and: selectedString.
	finder compute.
	rtf := RTFText new setFont: TextFont.
	rtf setTabStops: self tabStops.
	finder differences first printTextOn: rtf.
	^rtf contents contents'.
	finder := DifferenceFinder wordsOf: old and: new.
	finder compute
! !

!DifferenceFinderTest methodsFor: 'all'!
testLines
	| finder alan ian x y |
	alan := 'The best way to
	predict
	the future is to
	invent
	it.
	A. Kay'.
	ian := 'The best way to
	invent
	the future is to
	not predicting
	it.
	Ian Piumarta'.
	finder := DifferenceFinder linesOf: alan and: ian.
	finder compute.
	finder differences do: [:diff | 
		x := String streamContents: [:strm | 
			diff
				do: [:chunk :condition | (#(#removed #unchanged) includes: condition)
					ifTrue: [strm nextPutAll: chunk]]].
		self assert: x = alan.
		y := String streamContents: [:strm | 
			diff
				do: [:chunk :condition | (#(#inserted #unchanged) includes: condition)
					ifTrue: [strm nextPutAll: chunk]]].
		self assert: y = ian]
! !

!DifferenceFinderTest methodsFor: 'all'!
testWords
	| finder alan ian x y |
	alan := 'The best way to
	predict
	the future is to
	invent
	it.
	A. Kay'.
	ian := 'The best way to
	invent 	the future is to
	not predicting
	it.
	Ian Piumarta'.
	finder := DifferenceFinder wordsOf: alan and: ian.
	finder compute.
	finder differences do: [:diff | 
		x := String streamContents: [:strm | 
			diff
				do: [:chunk :condition | (#(#removed #unchanged) includes: condition)
					ifTrue: [strm nextPutAll: chunk]]].
		self assert: x = alan.
		y := String streamContents: [:strm | 
			diff
				do: [:chunk :condition | (#(#inserted #unchanged) includes: condition)
					ifTrue: [strm nextPutAll: chunk]]].
		self assert: y = ian]
! !


!SequenceDifference methodsFor: 'accessing'!
partsSize
	| count last |
	count := 0.
	self do: [:item :condition | 
		last = condition ifFalse: [
			count := count + 1.
			last := condition]].
	^count
! !

!SequenceDifference methodsFor: 'accessing' stamp: 'LC 1/24/2010 11:28'!
x: aCollection y: anotherCollection lcs: pairCollection
	x := aCollection.
	y := anotherCollection.
	lcs := pairCollection sortBy: [:a :b | a first < b first]
! !

!SequenceDifference methodsFor: 'printing' stamp: 'LC 1/24/2010 15:18'!
asText
	^Text streamContents: [:rtf | self printTextOn: rtf]! !

!SequenceDifference methodsFor: 'printing' stamp: 'LC 1/24/2010 15:13'!
attributesFor: condition 
	condition == #unchanged
		ifTrue: [ 
			^ {TextEmphasis normal} ].
	condition == #removed
		ifTrue: [ 
			^ {TextEmphasis struckOut. TextColor blue} ].
	condition == #inserted
		ifTrue: [ 
			^ {TextColor red} ]! !

!SequenceDifference methodsFor: 'printing' stamp: 'LC 1/24/2010 15:13'!
printTextOn: rtf
	self do: [:item :condition | | attributes |
		attributes := self attributesFor: condition.
		rtf withAttributes: attributes do: [rtf nextPutAll: item asString]]! !

!SequenceDifference methodsFor: 'enumerating'!
do: aBlock
	| j i item |
	i := j := 1.
	lcs do: [:pair | 
		[i < pair first] whileTrue: [
			item := x at: i.
			aBlock value: item value: #removed.
			i := i + 1].
		[j < pair second] whileTrue: [
			item := y at: j.
			aBlock value: item value: #inserted.
			j := j + 1].
		item := x at: i.
		aBlock value: item value: #unchanged.
		i := i + 1.
		j := j + 1].
	i to: x size do: [:k | 
		item := x at: k.
		aBlock value: item value: #removed].
	j to: y size do: [:k | 
		item := y at: k.
		aBlock value: item value: #inserted]
! !

!SequenceDifference methodsFor: 'services'!
invert
	| swap |
	swap := x.
	x := y.
	y := swap.
	lcs := lcs collect: [:pair | pair copy swap: 1 with: 2]
! !

!SequenceDifference methodsFor: 'services'!
size
	^lcs sum: [:pair | (x at: pair first) size]
! !

!SequenceDifference methodsFor: 'testing'!
<= sequence
	^self partsSize <= sequence partsSize
! !


!SequenceDifference class methodsFor: 'instance creation'!
x: x y: y lcs: sequence
	^self new x: x y: y lcs: sequence
! !

DifferenceFinder class removeSelector: #buildDisplayPatchFrom:to:inClass:!
DifferenceFinder initialize!
"Postscript:
Leave the line above, and replace the rest of this comment by a useful one.
Executable statements should follow this comment, and should
be separated by periods, with no exclamation points (!!).
Be sure to put any further comments in double-quotes, like this one."
DifferenceFinder initialize!

