'From Cuis 2.0 of 4 January 2010 [latest update: #393] on 12 January 2010 at 12:24:33 am'!
!classDefinition: #DiffElement category: #'System-SqueakTextDiffBuilder'!
Object subclass: #DiffElement
	instanceVariableNames: 'string hash match'
	classVariableNames: ''
	poolDictionaries: ''
	category: 'System-SqueakTextDiffBuilder'!

!DiffElement commentStamp: 'klub 12/28/2009 04:19' prior: 0!
My instances are container objects used by TextDiffBuilder for comparison. They hold a string and the precomputed hash of the string to speed up #=. They may reference another DiffElement object which is their pair in the diff.

Instance Variables
	hash:		<Integer>
	match:		<DiffElement>
	string:		<String>

hash
	- the hash of string, stored for fast access

match
	- another DiffElement object which has the same string and turned out to be my pair in the longest common subsequence found by a TextDiffBuilder, or nil if I don't a matching DiffElement

string
	- a part of a longer text, typically a line
!

!classDefinition: #TextDiffBuilder category: #'System-SqueakTextDiffBuilder'!
Object subclass: #TextDiffBuilder
	instanceVariableNames: 'realSrc realDst srcMap dstMap srcLines dstLines srcPos dstPos added removed shifted runs matches multipleMatches patchSequence yLines xLines '
	classVariableNames: 'NormalTextAttributes RemoveTextAttributes InsertTextAttributes '
	poolDictionaries: ''
	category: 'System-SqueakTextDiffBuilder'!

!TextDiffBuilder commentStamp: 'klub 12/28/2009 05:06' prior: 0!
I implement the diff algorithm. I can show the differences between two texts. See my method comments for further information.

Instance Variables
	xLines:		<Array>
	yLines:		<Array>

xLines
	- an Array of DiffElement which is created from the first input text

yLines
	- an Array of DiffElement which is created from the second input text!


!ClassDiffBuilder commentStamp: 'klub 12/28/2009 05:14' prior: 0!
I'm like TextDiffBuilder, but I split the input text by Character >> #separators, instead of new lines. I'm probably ment to create diffs of class definitions.!


!PrettyTextDiffBuilder commentStamp: 'klub 12/28/2009 05:12' prior: 0!
I'm like TextDiffBuilder, but I use the pretty-printed version of the source code if available.

Instance Variables
	sourceClass:		<Class>

sourceClass
	- this class provides the pretty-printer
!


!DiffElement methodsFor: 'comparing' stamp: 'ul 12/26/2009 01:47'!
= anObject

	^anObject class == self class and: [
		anObject hash = hash and: [
			anObject string = string ] ]! !

!DiffElement methodsFor: 'comparing' stamp: 'ul 12/26/2009 01:10'!
hash

	^hash! !

!DiffElement methodsFor: 'testing' stamp: 'klub 12/27/2009 01:56'!
hasMatch

	^match notNil! !

!DiffElement methodsFor: 'accessing' stamp: 'ul 12/26/2009 04:38'!
match

	^match! !

!DiffElement methodsFor: 'accessing' stamp: 'klub 12/27/2009 01:20'!
match: aDiffMatch

	match := aDiffMatch
	! !

!DiffElement methodsFor: 'accessing' stamp: 'klub 12/27/2009 01:20'!
matches: aDiffMatch

	match := aDiffMatch.
	aDiffMatch match: self! !

!DiffElement methodsFor: 'accessing' stamp: 'ul 12/26/2009 01:48'!
string

	^string! !

!DiffElement methodsFor: 'accessing' stamp: 'jmv 1/12/2010 00:00'!
string: aString

	string := aString.
	hash := string hash! !

!DiffElement methodsFor: 'printing' stamp: 'klub 12/27/2009 01:52'!
printOn: aStream

	super printOn: aStream.
	aStream
		nextPut: $(;
		print: hash;
		nextPutAll: ', ';
		print: string;
		nextPutAll: ', ';
		print: (match class == self class);
		nextPut: $)! !


!DiffElement class methodsFor: 'as yet unclassified' stamp: 'klub 12/27/2009 01:51'!
string: aString

	^self new
		string: aString;
		yourself! !


!PseudoClass methodsFor: 'testing' stamp: 'nice 10/20/2009 21:02'!
needsInitialize
	^self hasMetaclass and:[
		self metaClass includesSelector: #initialize]! !

!PseudoClass methodsFor: 'fileIn/fileOut' stamp: 'nice 12/26/2009 20:38'!
fileInMethods: aCollection
	"FileIn all methods with selectors taken from aCollection"
	| theClass |
	self exists ifFalse:[^self classNotDefined].
	theClass := self realClass.
	aCollection do:[:sel|
		| cat |
		cat := self organization categoryOfElement: sel.
		cat = self removedCategoryName ifFalse:[
			theClass 
				compile: (self sourceCodeAt: sel) 
				classified: cat
				withStamp: (self stampAt: sel)
				notifying: nil.
		].
	].! !

!PseudoClass methodsFor: 'fileIn/fileOut' stamp: 'nice 12/26/2009 20:40'!
fileOutMethods: aCollection on: aStream
	"FileOut all methods with selectors taken from aCollection"
	| categories |
	categories := Dictionary new.
	aCollection do:[:sel|
		| cat |
		cat := self organization categoryOfElement: sel.
		cat = self removedCategoryName ifFalse:[
			(categories includesKey: cat) 
				ifFalse:[categories at: cat put: Set new].
			(categories at: cat) add: sel].
	].
	categories associationsDo:[:assoc|
		assoc value do:[:sel|
			aStream cr.
			(self sourceCode at: sel) fileOutOn: aStream.
		].
	].! !

!PseudoClass methodsFor: 'testing method dictionary' stamp: 'jcg 1/9/2010 14:23'!
includesSelector: aSymbol 
	self exists
		ifTrue: [^self realClass includesSelector: aSymbol]
		ifFalse: [
			"Not sure what the answer should be in this case (I'm unfamiliar with this class),
			 so I want to force an error rather than answer something nonsensical.  This is
			 no worse than the old behavior, when this method didn't even exist, resulting
			 in a MessageNotUnderstood error."
			self error: 'real class does not exist'
		]! !


!SequenceableCollection methodsFor: 'enumerating' stamp: 'ul 11/11/2009 19:38'!
replace: aBlock 
	"Evaluate aBlock with each of the receiver's elements as the argument.  
	Collect the resulting values into self."

	1 to: self size do: [ :index |
		self at: index put: (aBlock value: (self at: index)) ]! !


!String methodsFor: 'accessing' stamp: 'nice 11/16/2009 20:09'!
lineIndicesDo: aBlock
	"execute aBlock with 3 arguments for each line:
	- start index of line
	- end index of line without line delimiter
	- end index of line including line delimiter(s) CR, LF or CRLF"
	
	| start end endWithoutDelimiters |
	start := 1.
	[ start <= self size ] whileTrue: [
		end := self indexOfAnyOf: CSLineEnders startingAt: start ifAbsent: [ 0 ].
		end = 0
			ifTrue: [endWithoutDelimiters := end := self size]
			ifFalse: [endWithoutDelimiters := end - 1.
				(end < self size
					and: [(self at: end + 1) = Character lf
					and: [(self at: end)	= Character cr]])
				ifTrue: [end := end + 1]].
		aBlock value: start value: endWithoutDelimiters value: end.
		start := end + 1]! !


!TextDiffBuilder methodsFor: 'initialize' stamp: 'klub 12/28/2009 04:16'!
from: xString to: yString

	xLines := (self split: xString asString) replace: [ :each | DiffElement string: each ].
	yLines := (self split: yString asString) replace: [ :each | DiffElement string: each ].
	self findMatches! !

!TextDiffBuilder methodsFor: 'creating patches' stamp: 'klub 12/28/2009 00:16'!
buildDisplayPatch

	^Text streamContents: [ :stream |
		self 
			patchSequenceDoIfMatch: [ :string |
				self print: string withAttributes: NormalTextAttributes on: stream ]
			ifInsert: [ :string |
				self print: string withAttributes: InsertTextAttributes on: stream ]
			ifRemove: [ :string |
				self print: string withAttributes: RemoveTextAttributes on: stream ] ]! !

!TextDiffBuilder methodsFor: 'creating patches' stamp: 'klub 12/29/2009 15:44'!
patchSequenceDoIfMatch: matchBlock ifInsert: insertBlock ifRemove: removeBlock
	"I'm the general purpose method to iterate through the patch sequence. See my senders to learn how to use me."

	| xLine xLineStream |
	xLineStream := xLines readStream.
	yLines do: [ :yLine | 
		yLine hasMatch 
			ifFalse: [ insertBlock value: yLine string  ]
			ifTrue: [
				[ (xLine := xLineStream next) == nil or: [ xLine == yLine match  ] ]
					whileFalse: [ removeBlock value: xLine string ].
				matchBlock value: yLine string ] ].
	[ (xLine := xLineStream next) == nil ] whileFalse: [
		removeBlock value: xLine string ]! !

!TextDiffBuilder methodsFor: 'private' stamp: 'ul 1/6/2010 05:58'!
findMatches
	"I find the matching pairs of xLines and yLines. First I filter out all lines that can't have a pair, then I find the longest common subsequence of the remaining elements. Finally I mark the matching pairs."

	| lineSet lcs xFilteredLines yFilteredLines |
	lineSet := yLines asSet.
	xFilteredLines := xLines select: [ :each |
		lineSet includes: each ].
	xFilteredLines size = 0 ifTrue: [ ^self ].
	lineSet := xLines asSet.
	yFilteredLines := yLines select: [ :each |
		(lineSet includes: each) ].
	yFilteredLines size = 0 ifTrue: [ ^self ].
	lcs := self
		lcsFor: xFilteredLines
		and: yFilteredLines.
	[ lcs == nil ] whileFalse: [
		(xFilteredLines at: (lcs at: 1)) matches: (yFilteredLines at: (lcs at: 2)).
		lcs := lcs at: 3 ]! !

!TextDiffBuilder methodsFor: 'private' stamp: 'ul 1/6/2010 06:04'!
lcsFor: xFilteredLines and: yFilteredLines

	"I find one of the longest common subsequences of my the arguments. I assume that none of my arguments are empty. I return nil or an Array which represents a list. The first two elements are the matching line numbers, the last is the next node in the list or nil if there are no more elements. The list containts the longest common subsequence. I'm a modified version of the greedy lcs algorithm from the 6th page of 'An O(ND) Difference Algorithm and Its Variations (1986)' by Eugene W. Myers"

	| n m v lcss max |
	n := xFilteredLines size.
	m := yFilteredLines size.
	max := m + n.
	v := Array new: 2 * max + 1.
	v at: max + 2 put: 0.
	lcss := Array new: 2 * max + 1.
	0 to: max do: [ :d |
		d negated to: d by: 2 do: [ :k |
			| index lcs x y |
			(k + d = 0 or: [ k ~= d and: [ (v at: max + k ) < (v at: max + k + 2) ] ])
				ifTrue: [ 
					index := max + k + 2.
					x := v at: index ]
				ifFalse: [ 
					index := max + k.
					x := (v at: index) + 1 ].
			y := x - k.
			lcs := lcss at: index.
			[ x < n and: [ y < m and: [ (xFilteredLines at: x + 1) = (yFilteredLines at: y + 1) ] ] ]
				whileTrue: [
					lcs := { x := x + 1. y := y + 1. lcs } ].
			(x >= n and: [ y >= m ]) ifTrue: [
				^lcs ].
			v at: max + k + 1 put: x.
			lcss at: max + k + 1 put: lcs ] ].
	self error! !

!TextDiffBuilder methodsFor: 'private' stamp: 'ul 1/11/2010 01:13'!
print: aString withAttributes: attributes on: stream

	stream
		withAttributes: attributes 
		do: [ 
			stream nextPutAll: aString.
			(aString notEmpty and: [ 
				aString last = Character cr or: [
					aString endsWith: String crlf ] ]) 
						ifFalse: [ stream cr ] ]! !

!TextDiffBuilder methodsFor: 'private' stamp: 'klub 12/28/2009 04:12'!
split: aString
	"I return an Array of strings which are the lines extracted from aString. All lines contain the line separator characters"

	^Array streamContents: [ :stream |
		aString lineIndicesDo: [ :start :endWithoutSeparators :end |
			stream nextPut: (aString copyFrom: start to: end) ] ]! !


!ClassDiffBuilder methodsFor: 'private' stamp: 'klub 12/28/2009 00:22'!
print: aString withAttributes: attributes on: stream

	stream
		withAttributes: attributes 
		do: [ stream nextPutAll: aString ]! !

!ClassDiffBuilder methodsFor: 'private' stamp: 'klub 12/28/2009 04:14'!
split: aString
	"I return an array with aString splitted by Character >> #separators."

	^Array streamContents: [ :stream |
		| out |
		out := aString copy writeStream.
		aString do: [ :c |
			out nextPut: c.
			c isSeparator ifTrue:[
				stream nextPut: out contents.
				out reset ] ].
		out position = 0 ifFalse: [ 
			stream nextPut: out contents ] ]! !


!PrettyTextDiffBuilder methodsFor: 'initialize' stamp: 'jmv 1/12/2010 00:07'!
split: aString 
	| formatted |
	aString ifEmpty: [ ^super split: aString ].
	formatted _ [
		sourceClass compilerClass new
			format: aString
			in: sourceClass
			notifying: nil ] 
				on: Error
				do: [ :ex | aString ].
	^super split: formatted! !


!TextDiffBuilder class methodsFor: 'instance creation' stamp: 'klub 12/27/2009 02:59'!
buildDisplayPatchFrom: sourceText to: destinationText

	^(self from: sourceText to: destinationText) buildDisplayPatch! !

!TextDiffBuilder class methodsFor: 'instance creation' stamp: 'ul 12/27/2009 17:16'!
buildDisplayPatchFrom: sourceText to: destinationText inClass: sourceClass prettyDiffs: prettyDiffs
	
	^((sourceClass notNil and: [ prettyDiffs ])
		ifFalse: [ self from: sourceText to: destinationText ]
		ifTrue: [
			PrettyTextDiffBuilder
				from: sourceText
				to: destinationText
				inClass: sourceClass ]) buildDisplayPatch! !

!TextDiffBuilder class methodsFor: 'instance creation' stamp: 'klub 12/27/2009 01:46'!
from: sourceText to: destinationText

	^self new
		from: sourceText to: destinationText;
		yourself! !

!TextDiffBuilder class methodsFor: 'class initialization' stamp: 'klub 12/27/2009 01:26'!
initialize

	self initializeTextAttributes! !

!TextDiffBuilder class methodsFor: 'class initialization' stamp: 'klub 12/27/2009 01:27'!
initializeTextAttributes

	InsertTextAttributes := { TextColor red }.
	RemoveTextAttributes := { TextEmphasis struckOut. TextColor blue }.
	NormalTextAttributes :={ TextEmphasis normal }
! !

TextDiffBuilder class removeSelector: #buildDisplayPatchFrom:to:inClass:!
TextDiffBuilder initialize!
ClassDiffBuilder removeSelector: #printPatchSequence:on:!
TextDiffBuilder removeSelector: #attributesOf:!
TextDiffBuilder removeSelector: #buildPatchSequence!
TextDiffBuilder removeSelector: #buildReferenceMap!
TextDiffBuilder removeSelector: #collectRunFrom:startingWith:into:!
TextDiffBuilder removeSelector: #destString:!
TextDiffBuilder removeSelector: #detectShiftedRuns!
TextDiffBuilder removeSelector: #formatLine:!
TextDiffBuilder removeSelector: #generatePatchSequence!
TextDiffBuilder removeSelector: #hasMultipleMatches!
TextDiffBuilder removeSelector: #incorporateAddsInto:!
TextDiffBuilder removeSelector: #incorporateMatchesInto:!
TextDiffBuilder removeSelector: #incorporateRemovalsInto:!
TextDiffBuilder removeSelector: #pointEqualBlock!
TextDiffBuilder removeSelector: #pointHashBlock!
TextDiffBuilder removeSelector: #printPatchSequence:on:!
TextDiffBuilder removeSelector: #processDiagonals!
TextDiffBuilder removeSelector: #processDiagonalsFrom:!
TextDiffBuilder removeSelector: #processShiftedRuns!
TextDiffBuilder removeSelector: #remove:from:!
TextDiffBuilder removeSelector: #sourceString:!
TextDiffBuilder removeSelector: #split:by:!
TextDiffBuilder removeSelector: #splitCharacter!
TextDiffBuilder removeSelector: #stringHashBlock!
TextDiffBuilder removeSelector: #validateRuns:!
!classDefinition: #TextDiffBuilder category: #'System-SqueakTextDiffBuilder'!
Object subclass: #TextDiffBuilder
	instanceVariableNames: 'xLines yLines'
	classVariableNames: 'InsertTextAttributes NormalTextAttributes RemoveTextAttributes'
	poolDictionaries: ''
	category: 'System-SqueakTextDiffBuilder'!
String removeSelector: #isOctetString!
Smalltalk removeClassNamed: #TwoLevelDictionary!
Smalltalk removeClassNamed: #TwoLevelSet!
"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."
TextDiffBuilder initialize!

