Levente Uzonyi uploaded a new version of System to project The Trunk:
http://source.squeak.org/trunk/System-ul.590.mcz

==================== Summary ====================

Name: System-ul.590
Author: ul
Time: 11 September 2013, 5:31:05.947 pm
UUID: c51e4adf-c500-4c70-a3e3-6363fdcb50d7
Ancestors: System-cmm.589

TextDiffBuilder changes:
- #split: returns an Array of DiffElements instead of Strings
- introduced #from:to:ignoreLineEndings:, so one doesn't have to change the global preference to get the preferred behavior
- unrolled and optimized some parts of #lcsFor:and: 
- fixed some comments

=============== Diff against System-cmm.589 ===============

Item was changed:
  ----- Method: ClassDiffBuilder>>split: (in category 'private') -----
  split: aString
+ 	"I return an Array or DiffElements containing aString splitted by whitespace ' and ""."
- 	"I return an array with aString splitted by whitespace ' and ""."
  
  	^Array streamContents: [ :stream |
  		| input separators |
  		input := aString readStream.
  		separators := CharacterSet separators
  			add: $'; "for variables"
  			add: $"; "for comments in mc"
  			yourself.
  		[ input atEnd ] whileFalse: [
  			| word separator |
  			word := input
  				upToAnyOf: separators
  				do: [ :matchingSeparator |
  					separator := matchingSeparator ].
+ 			stream nextPut: (DiffElement string: word).
- 			stream nextPut: word.
  			separator ifNotNil: [
+ 				stream nextPut: (DiffElement string: separator asString) ] ] ]!
- 				stream nextPut: separator asString ] ] ]!

Item was changed:
  Object subclass: #DiffElement
  	instanceVariableNames: 'string hash match'
  	classVariableNames: ''
  	poolDictionaries: ''
  	category: 'System-FilePackage'!
  
+ !DiffElement commentStamp: 'ul 9/11/2013 01:01' prior: 0!
- !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 match anything from the other sequence
- 	- 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
  !

Item was changed:
  Object subclass: #TextDiffBuilder
+ 	instanceVariableNames: 'xLines yLines ignoreLineEndings'
- 	instanceVariableNames: 'xLines yLines'
  	classVariableNames: 'IgnoreLineEndings InsertTextAttributes NormalTextAttributes RemoveTextAttributes'
  	poolDictionaries: ''
  	category: 'System-FilePackage'!
  
+ !TextDiffBuilder commentStamp: 'ul 9/11/2013 01:05' prior: 0!
- !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>
+ 	ignoreLineEndings:	<Boolean>
- 	xLines:		<Array>
- 	yLines:		<Array>
  
  xLines
+ 	- an Array of DiffElements which is created from the first input text
- 	- an Array of DiffElement which is created from the first input text
  
  yLines
+ 	- an Array of DiffElements which is created from the second input text
+ 	
+ ignoreLineEndings
+ 	- a Boolean describing wether lines only differing in the line endings should be reported as a difference, or not!
- 	- an Array of DiffElement which is created from the second input text!

Item was changed:
  ----- Method: TextDiffBuilder class>>from:to: (in category 'instance creation') -----
  from: sourceText to: destinationText
  
+ 	^self from: sourceText to: destinationText ignoreLineEndings: self ignoreLineEndings!
- 	^self new
- 		from: sourceText to: destinationText;
- 		yourself!

Item was added:
+ ----- Method: TextDiffBuilder class>>from:to:ignoreLineEndings: (in category 'instance creation') -----
+ from: sourceText to: destinationText ignoreLineEndings: ignoreLineEndings
+ 
+ 	^self new
+ 		from: sourceText to: destinationText ignoreLineEndings: ignoreLineEndings;
+ 		yourself!

Item was changed:
  ----- Method: TextDiffBuilder>>from:to: (in category 'initialize') -----
  from: xString to: yString
  
+ 	self from: xString to: yString ignoreLineEndings: self class ignoreLineEndings!
- 	xLines := (self split: xString asString) replace: [ :each | DiffElement string: each ].
- 	yLines := (self split: yString asString) replace: [ :each | DiffElement string: each ].
- 	self findMatches!

Item was added:
+ ----- Method: TextDiffBuilder>>from:to:ignoreLineEndings: (in category 'initialize') -----
+ from: xString to: yString ignoreLineEndings: aBoolean
+ 
+ 	ignoreLineEndings := aBoolean.
+ 	xLines := self split: xString asString.
+ 	yLines := self split: yString asString.
+ 	self findMatches!

Item was added:
+ ----- Method: TextDiffBuilder>>ignoreLineEndings: (in category 'creating patches') -----
+ ignoreLineEndings: aBoolean
+ 
+ 	ignoreLineEndings := aBoolean!

Item was changed:
  ----- Method: TextDiffBuilder>>lcsFor:and: (in category 'private') -----
  lcsFor: xFilteredLines and: yFilteredLines
+ 	"I find one of the longest common subsequences of my 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 third (and 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/SES Algorithm from the 6th page of 'An O(ND) Difference Algorithm and Its Variations (1986)' by Eugene W. Myers"
- 	"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 index lcs x y |
- 	| 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.
+ 	"Unrolled first iteration (d = 0, k = 0)"
+ 	index := max + 2.
+ 	y := x := v at: index put: 0.	
+ 	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 ifTrue: [ y >= m ifTrue: [ ^lcs ] ].
+ 	v at: max + 1 put: x.
+ 	lcss at: max + 1 put: lcs.
+ 	1 to: max do: [ :d |
+ 		"Unrolled lowest diagonal checks (k = -d)."
+ 		index := max - d + 2.
+ 		x := v at: index.
+ 		y := x + d.
+ 		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 ifTrue: [ y >= m ifTrue: [ ^lcs ] ].
+ 		v at: max - d + 1 put: x.
+ 		lcss at: max - d + 1 put: lcs.
+ 		"Inner diagonals. (k in [2-d..d-2])"
+ 		2 - d to: d - 2 by: 2 do: [ :k |
- 	0 to: max do: [ :d |
- 		d negated to: d by: 2 do: [ :k |
- 			| index lcs x y |
  			index := max + k.
+ 			(v at: index) < (v at: index + 2)
- 			(k + d = 0 or: [ k ~= d and: [ (v at: index) < (v at: index + 2) ] ])
  				ifTrue: [ x := v at: (index := index + 2) ]
  				ifFalse: [ 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 ifTrue: [ y >= m ifTrue: [ ^lcs ] ].
- 				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 ].
+ 		"Unrolled highest diagonal checks (k = d)."
+ 		index := max + d.
+ 		x := (v at: index) + 1.
+ 		y := x - d.
+ 		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 ifTrue: [ y >= m ifTrue: [ ^lcs ] ].
+ 		v at: max + d + 1 put: x.
+ 		lcss at: max + d + 1 put: lcs ].
+ 	self error "We should never reach this point."!
- 			lcss at: max + k + 1 put: lcs ] ].
- 	self error!

Item was changed:
  ----- Method: TextDiffBuilder>>split: (in category 'private') -----
  split: aString
+ 	"I return an Array of DiffElements containing the strings which are the lines extracted from aString. All lines contain the line separator characters, or not depending on preference."
- 	"I return an Array of strings which are the lines extracted from aString. All lines contain the line separator characters, or not depending on preference."
  
  	^Array streamContents: [ :stream |
+ 		ignoreLineEndings
+ 			ifTrue: [
+ 				aString lineIndicesDo: [ :start :endWithoutSeparators :end |
+ 					stream nextPut: (DiffElement string: (aString copyFrom: start to: endWithoutSeparators)) ] ]
+ 			ifFalse: [
+ 				aString lineIndicesDo: [ :start :endWithoutSeparators :end |
+ 					stream nextPut: (DiffElement string: (aString copyFrom: start to: end)) ] ] ]!
- 		self class ignoreLineEndings
- 			ifTrue: [aString lineIndicesDo: [ :start :endWithoutSeparators :end |
- 				stream nextPut: (aString copyFrom: start to: endWithoutSeparators) ] ]
- 			ifFalse: [aString lineIndicesDo: [ :start :endWithoutSeparators :end |
- 				stream nextPut: (aString copyFrom: start to: end) ] ] ]!