Improve diff highlight (#3390)

- Try to reduce memory allocations
- Add possibility to disable diff highlight (can improve performance for large diffs)
- Tweaking with cost for prettier (cleaner) diffs
- Do not calculate diff when the number of removed lines in a block is not equal to the number of added lines (this usually resulted in ugly diffs)

4 files changed, 60 insertions, 66 deletions

diff --git a/conf/app.ini b/conf/app.ini
index 6157c08935..3c36195ff6 100644
--- a/conf/app.ini
+++ b/conf/app.ini
@@ -334,11 +334,13 @@ RUN_AT_START = true
 SCHEDULE = @every 24h
 
 [git]
-; Max number of lines allowed of a single file in diff view.
+; Disables highlight of added and removed changes
+DISABLE_DIFF_HIGHLIGHT = false
+; Max number of lines allowed of a single file in diff view
 MAX_GIT_DIFF_LINES = 1000
-; Max number of characters of a line allowed in diff view.
+; Max number of characters of a line allowed in diff view
 MAX_GIT_DIFF_LINE_CHARACTERS = 500
-; Max number of files shown in diff view.
+; Max number of files shown in diff view
 MAX_GIT_DIFF_FILES = 100
 ; Arguments for command 'git gc', e.g. "--aggressive --auto"
 ; see more on http://git-scm.com/docs/git-gc/1.7.5
diff --git a/models/git_diff.go b/models/git_diff.go
index a3040081b0..5c5954fcac 100644
--- a/models/git_diff.go
+++ b/models/git_diff.go
@@ -26,6 +26,7 @@ import (
 	"github.com/gogits/gogs/modules/base"
 	"github.com/gogits/gogs/modules/log"
 	"github.com/gogits/gogs/modules/process"
+	"github.com/gogits/gogs/modules/setting"
 	"github.com/gogits/gogs/modules/template/highlight"
 )
 
@@ -70,17 +71,18 @@ var (
 )
 
 func diffToHTML(diffs []diffmatchpatch.Diff, lineType DiffLineType) template.HTML {
-	var buf bytes.Buffer
+	buf := bytes.NewBuffer(nil)
 	for i := range diffs {
-		if diffs[i].Type == diffmatchpatch.DiffInsert && lineType == DIFF_LINE_ADD {
+		switch {
+		case diffs[i].Type == diffmatchpatch.DiffInsert && lineType == DIFF_LINE_ADD:
 			buf.Write(addedCodePrefix)
 			buf.WriteString(html.EscapeString(diffs[i].Text))
 			buf.Write(codeTagSuffix)
-		} else if diffs[i].Type == diffmatchpatch.DiffDelete && lineType == DIFF_LINE_DEL {
+		case diffs[i].Type == diffmatchpatch.DiffDelete && lineType == DIFF_LINE_DEL:
 			buf.Write(removedCodePrefix)
 			buf.WriteString(html.EscapeString(diffs[i].Text))
 			buf.Write(codeTagSuffix)
-		} else if diffs[i].Type == diffmatchpatch.DiffEqual {
+		case diffs[i].Type == diffmatchpatch.DiffEqual:
 			buf.WriteString(html.EscapeString(diffs[i].Text))
 		}
 	}
@@ -90,62 +92,86 @@ func diffToHTML(diffs []diffmatchpatch.Diff, lineType DiffLineType) template.HTM
 
 // get an specific line by type (add or del) and file line number
 func (diffSection *DiffSection) GetLine(lineType DiffLineType, idx int) *DiffLine {
-	difference := 0
+	var (
+		difference    = 0
+		addCount      = 0
+		delCount      = 0
+		matchDiffLine *DiffLine
+	)
 
+LOOP:
 	for _, diffLine := range diffSection.Lines {
-		if diffLine.Type == DIFF_LINE_PLAIN {
-			// get the difference of line numbers between ADD and DEL versions
+		switch diffLine.Type {
+		case DIFF_LINE_ADD:
+			addCount++
+		case DIFF_LINE_DEL:
+			delCount++
+		default:
+			if matchDiffLine != nil {
+				break LOOP
+			}
 			difference = diffLine.RightIdx - diffLine.LeftIdx
-			continue
+			addCount = 0
+			delCount = 0
 		}
 
-		if lineType == DIFF_LINE_DEL {
+		switch lineType {
+		case DIFF_LINE_DEL:
 			if diffLine.RightIdx == 0 && diffLine.LeftIdx == idx-difference {
-				return diffLine
+				matchDiffLine = diffLine
 			}
-		} else if lineType == DIFF_LINE_ADD {
+		case DIFF_LINE_ADD:
 			if diffLine.LeftIdx == 0 && diffLine.RightIdx == idx+difference {
-				return diffLine
+				matchDiffLine = diffLine
 			}
 		}
 	}
+
+	if addCount == delCount {
+		return matchDiffLine
+	}
 	return nil
 }
 
+var diffMatchPatch = diffmatchpatch.New()
+
+func init() {
+	diffMatchPatch.DiffEditCost = 100
+}
+
 // computes inline diff for the given line
 func (diffSection *DiffSection) GetComputedInlineDiffFor(diffLine *DiffLine) template.HTML {
-	var compareDiffLine *DiffLine
-	var diff1, diff2 string
-
-	getDefaultReturn := func() template.HTML {
+	if setting.Git.DisableDiffHighlight {
 		return template.HTML(html.EscapeString(diffLine.Content[1:]))
 	}
-
-	// just compute diff for adds and removes
-	if diffLine.Type != DIFF_LINE_ADD && diffLine.Type != DIFF_LINE_DEL {
-		return getDefaultReturn()
-	}
+	var (
+		compareDiffLine *DiffLine
+		diff1           string
+		diff2           string
+	)
 
 	// try to find equivalent diff line. ignore, otherwise
-	if diffLine.Type == DIFF_LINE_ADD {
+	switch diffLine.Type {
+	case DIFF_LINE_ADD:
 		compareDiffLine = diffSection.GetLine(DIFF_LINE_DEL, diffLine.RightIdx)
 		if compareDiffLine == nil {
-			return getDefaultReturn()
+			return template.HTML(html.EscapeString(diffLine.Content[1:]))
 		}
 		diff1 = compareDiffLine.Content
 		diff2 = diffLine.Content
-	} else {
+	case DIFF_LINE_DEL:
 		compareDiffLine = diffSection.GetLine(DIFF_LINE_ADD, diffLine.LeftIdx)
 		if compareDiffLine == nil {
-			return getDefaultReturn()
+			return template.HTML(html.EscapeString(diffLine.Content[1:]))
 		}
 		diff1 = diffLine.Content
 		diff2 = compareDiffLine.Content
+	default:
+		return template.HTML(html.EscapeString(diffLine.Content[1:]))
 	}
 
-	dmp := diffmatchpatch.New()
-	diffRecord := dmp.DiffMain(diff1[1:], diff2[1:], true)
-	diffRecord = dmp.DiffCleanupSemantic(diffRecord)
+	diffRecord := diffMatchPatch.DiffMain(diff1[1:], diff2[1:], true)
+	diffRecord = diffMatchPatch.DiffCleanupEfficiency(diffRecord)
 
 	return diffToHTML(diffRecord, diffLine.Type)
 }
diff --git a/models/git_diff_test.go b/models/git_diff_test.go
index 3a1312ca56..e673094d2e 100644
--- a/models/git_diff_test.go
+++ b/models/git_diff_test.go
@@ -33,38 +33,3 @@ func TestDiffToHTML(t *testing.T) {
 		dmp.Diff{dmp.DiffEqual, " biz"},
 	}, DIFF_LINE_DEL))
 }
-
-// test if GetLine is return the correct lines
-func TestGetLine(t *testing.T) {
-	ds := DiffSection{Lines: []*DiffLine{
-		&DiffLine{LeftIdx: 28, RightIdx: 28, Type: DIFF_LINE_PLAIN},
-		&DiffLine{LeftIdx: 29, RightIdx: 29, Type: DIFF_LINE_PLAIN},
-		&DiffLine{LeftIdx: 30, RightIdx: 30, Type: DIFF_LINE_PLAIN},
-		&DiffLine{LeftIdx: 31, RightIdx: 0, Type: DIFF_LINE_DEL},
-		&DiffLine{LeftIdx: 0, RightIdx: 31, Type: DIFF_LINE_ADD},
-		&DiffLine{LeftIdx: 0, RightIdx: 32, Type: DIFF_LINE_ADD},
-		&DiffLine{LeftIdx: 32, RightIdx: 33, Type: DIFF_LINE_PLAIN},
-		&DiffLine{LeftIdx: 33, RightIdx: 0, Type: DIFF_LINE_DEL},
-		&DiffLine{LeftIdx: 34, RightIdx: 0, Type: DIFF_LINE_DEL},
-		&DiffLine{LeftIdx: 35, RightIdx: 0, Type: DIFF_LINE_DEL},
-		&DiffLine{LeftIdx: 36, RightIdx: 0, Type: DIFF_LINE_DEL},
-		&DiffLine{LeftIdx: 0, RightIdx: 34, Type: DIFF_LINE_ADD},
-		&DiffLine{LeftIdx: 0, RightIdx: 35, Type: DIFF_LINE_ADD},
-		&DiffLine{LeftIdx: 0, RightIdx: 36, Type: DIFF_LINE_ADD},
-		&DiffLine{LeftIdx: 0, RightIdx: 37, Type: DIFF_LINE_ADD},
-		&DiffLine{LeftIdx: 37, RightIdx: 38, Type: DIFF_LINE_PLAIN},
-		&DiffLine{LeftIdx: 38, RightIdx: 39, Type: DIFF_LINE_PLAIN},
-	}}
-
-	assertLineEqual(t, ds.GetLine(DIFF_LINE_ADD, 31), ds.Lines[4])
-	assertLineEqual(t, ds.GetLine(DIFF_LINE_DEL, 31), ds.Lines[3])
-
-	assertLineEqual(t, ds.GetLine(DIFF_LINE_ADD, 33), ds.Lines[11])
-	assertLineEqual(t, ds.GetLine(DIFF_LINE_ADD, 34), ds.Lines[12])
-	assertLineEqual(t, ds.GetLine(DIFF_LINE_ADD, 35), ds.Lines[13])
-	assertLineEqual(t, ds.GetLine(DIFF_LINE_ADD, 36), ds.Lines[14])
-	assertLineEqual(t, ds.GetLine(DIFF_LINE_DEL, 34), ds.Lines[7])
-	assertLineEqual(t, ds.GetLine(DIFF_LINE_DEL, 35), ds.Lines[8])
-	assertLineEqual(t, ds.GetLine(DIFF_LINE_DEL, 36), ds.Lines[9])
-	assertLineEqual(t, ds.GetLine(DIFF_LINE_DEL, 37), ds.Lines[10])
-}
diff --git a/modules/setting/setting.go b/modules/setting/setting.go
index 0de1963c5c..6581efe4f0 100644
--- a/modules/setting/setting.go
+++ b/modules/setting/setting.go
@@ -191,6 +191,7 @@ var (
 
 	// Git settings
 	Git struct {
+		DisableDiffHighlight     bool
 		MaxGitDiffLines          int
 		MaxGitDiffLineCharacters int
 		MaxGitDiffFiles          int