plumbing: detect renames by hash and similar content in diff tree

This commit implements the rename detection algorithms used in the
JGit implementation.
Given a list of changes, additions and deletions are extracted and
matched in two ways:
- By exact hash content: all additions and deletions are grouped by
  the content hash and paired with the best match based on the file
  mode and file path. All the files that cannot be paired are kept
  as regular deletions and additions.
- By similar content: a matrix of addition and deletion pairs with
  all possible combinations is created and scored by how similar the
  content is between both files as well as how similar the file path
  is. The pairs with the best score and whose score is equal or
  greater than a threshold are paired and turned into a rename.
  All the files that cannot be paired are kept as regular deletions
  and additions.

DiffTree and DiffTreeContext will not return the changes with renames
detected for compatibility reasons, although this will change in v6
so that detecting renames is the default behaviour.
A new function DiffTreeWithOptions has been added to configure the
parameters for the rename detection to control the score threshold,
the limit of renames and whether to use similar content detection in
the detection.

More information:

- https://github.com/eclipse/jgit/blob/master/org.eclipse.jgit/src/org/eclipse/jgit/diff/RenameDetector.java
- https://github.com/eclipse/jgit/blob/master/org.eclipse.jgit/src/org/eclipse/jgit/diff/SimilarityRenameDetector.java
- https://github.com/eclipse/jgit/blob/master/org.eclipse.jgit/src/org/eclipse/jgit/diff/SimilarityIndex.java

Signed-off-by: Miguel Molina <miguel@erizocosmi.co>

1 files changed, 817 insertions, 0 deletions

diff --git a/plumbing/object/rename.go b/plumbing/object/rename.go
new file mode 100644
index 0000000..48665eb
--- /dev/null
+++ b/plumbing/object/rename.go
@@ -0,0 +1,817 @@
+package object
+
+import (
+	"errors"
+	"io"
+	"sort"
+	"strings"
+
+	"github.com/go-git/go-git/v5/plumbing"
+	"github.com/go-git/go-git/v5/plumbing/filemode"
+	"github.com/go-git/go-git/v5/utils/ioutil"
+	"github.com/go-git/go-git/v5/utils/merkletrie"
+)
+
+// DetectRenames detects the renames in the given changes on two trees with
+// the given options. It will return the given changes grouping additions and
+// deletions into modifications when possible.
+// If options is nil, the default diff tree options will be used.
+func DetectRenames(
+	changes Changes,
+	opts *DiffTreeOptions,
+) (Changes, error) {
+	if opts == nil {
+		opts = DefaultDiffTreeOptions
+	}
+
+	detector := &renameDetector{
+		renameScore: int(opts.RenameScore),
+		renameLimit: int(opts.RenameLimit),
+		onlyExact:   opts.OnlyExactRenames,
+	}
+
+	for _, c := range changes {
+		action, err := c.Action()
+		if err != nil {
+			return nil, err
+		}
+
+		switch action {
+		case merkletrie.Insert:
+			detector.added = append(detector.added, c)
+		case merkletrie.Delete:
+			detector.deleted = append(detector.deleted, c)
+		default:
+			detector.modified = append(detector.modified, c)
+		}
+	}
+
+	return detector.detect()
+}
+
+// renameDetector will detect and resolve renames in a set of changes.
+// see: https://github.com/eclipse/jgit/blob/master/org.eclipse.jgit/src/org/eclipse/jgit/diff/RenameDetector.java
+type renameDetector struct {
+	added    []*Change
+	deleted  []*Change
+	modified []*Change
+
+	renameScore int
+	renameLimit int
+	onlyExact   bool
+}
+
+// detectExactRenames detects matches files that were deleted with files that
+// were added where the hash is the same on both. If there are multiple targets
+// the one with the most similar path will be chosen as the rename and the
+// rest as either deletions or additions.
+func (d *renameDetector) detectExactRenames() {
+	added := groupChangesByHash(d.added)
+	deletes := groupChangesByHash(d.deleted)
+	var uniqueAdds []*Change
+	var nonUniqueAdds [][]*Change
+	var addedLeft []*Change
+
+	for _, cs := range added {
+		if len(cs) == 1 {
+			uniqueAdds = append(uniqueAdds, cs[0])
+		} else {
+			nonUniqueAdds = append(nonUniqueAdds, cs)
+		}
+	}
+
+	for _, c := range uniqueAdds {
+		hash := changeHash(c)
+		deleted := deletes[hash]
+
+		if len(deleted) == 1 {
+			if sameMode(c, deleted[0]) {
+				d.modified = append(d.modified, &Change{From: deleted[0].From, To: c.To})
+				delete(deletes, hash)
+			} else {
+				addedLeft = append(addedLeft, c)
+			}
+		} else if len(deleted) > 1 {
+			bestMatch := bestNameMatch(c, deleted)
+			if bestMatch != nil && sameMode(c, bestMatch) {
+				d.modified = append(d.modified, &Change{From: bestMatch.From, To: c.To})
+				delete(deletes, hash)
+
+				var newDeletes = make([]*Change, 0, len(deleted)-1)
+				for _, d := range deleted {
+					if d != bestMatch {
+						newDeletes = append(newDeletes, d)
+					}
+				}
+				deletes[hash] = newDeletes
+			}
+		} else {
+			addedLeft = append(addedLeft, c)
+		}
+	}
+
+	for _, added := range nonUniqueAdds {
+		hash := changeHash(added[0])
+		deleted := deletes[hash]
+
+		if len(deleted) == 1 {
+			deleted := deleted[0]
+			bestMatch := bestNameMatch(deleted, added)
+			if bestMatch != nil && sameMode(deleted, bestMatch) {
+				d.modified = append(d.modified, &Change{From: deleted.From, To: bestMatch.To})
+				delete(deletes, hash)
+
+				for _, c := range added {
+					if c != bestMatch {
+						addedLeft = append(addedLeft, c)
+					}
+				}
+			} else {
+				addedLeft = append(addedLeft, added...)
+			}
+		} else if len(deleted) > 1 {
+			maxSize := len(deleted) * len(added)
+			if d.renameLimit > 0 && d.renameLimit < maxSize {
+				maxSize = d.renameLimit
+			}
+
+			matrix := make(similarityMatrix, 0, maxSize)
+
+			for delIdx, del := range deleted {
+				deletedName := changeName(del)
+
+				for addIdx, add := range added {
+					addedName := changeName(add)
+
+					score := nameSimilarityScore(addedName, deletedName)
+					matrix = append(matrix, similarityPair{added: addIdx, deleted: delIdx, score: score})
+
+					if len(matrix) >= maxSize {
+						break
+					}
+				}
+
+				if len(matrix) >= maxSize {
+					break
+				}
+			}
+
+			sort.Stable(matrix)
+
+			usedAdds := make(map[*Change]struct{})
+			usedDeletes := make(map[*Change]struct{})
+			for i := len(matrix) - 1; i >= 0; i-- {
+				del := deleted[matrix[i].deleted]
+				add := added[matrix[i].added]
+
+				if add == nil || del == nil {
+					// it was already matched
+					continue
+				}
+
+				usedAdds[add] = struct{}{}
+				usedDeletes[del] = struct{}{}
+				d.modified = append(d.modified, &Change{From: del.From, To: add.To})
+				added[matrix[i].added] = nil
+				deleted[matrix[i].deleted] = nil
+			}
+
+			for _, c := range added {
+				if _, ok := usedAdds[c]; !ok {
+					addedLeft = append(addedLeft, c)
+				}
+			}
+
+			var newDeletes = make([]*Change, 0, len(deleted)-len(usedDeletes))
+			for _, c := range deleted {
+				if _, ok := usedDeletes[c]; !ok {
+					newDeletes = append(newDeletes, c)
+				}
+			}
+			deletes[hash] = newDeletes
+		} else {
+			addedLeft = append(addedLeft, added...)
+		}
+	}
+
+	d.added = addedLeft
+	d.deleted = nil
+	for _, dels := range deletes {
+		for _, del := range dels {
+			if del != nil {
+				d.deleted = append(d.deleted, del)
+			}
+		}
+	}
+}
+
+// detectContentRenames detects renames based on the similarity of the content
+// in the files by building a matrix of pairs between sources and destinations
+// and matching by the highest score.
+// see: https://github.com/eclipse/jgit/blob/master/org.eclipse.jgit/src/org/eclipse/jgit/diff/SimilarityRenameDetector.java
+func (d *renameDetector) detectContentRenames() error {
+	cnt := max(len(d.added), len(d.deleted))
+	if d.renameLimit > 0 && cnt > d.renameLimit {
+		return nil
+	}
+
+	srcs, dsts := d.deleted, d.added
+	matrix, err := buildSimilarityMatrix(srcs, dsts, d.renameScore)
+	if err != nil {
+		return err
+	}
+	renames := make([]*Change, 0, min(len(matrix), len(dsts)))
+
+	// Match rename pairs on a first come, first serve basis until
+	// we have looked at everything that is above the minimum score.
+	for i := len(matrix) - 1; i >= 0; i-- {
+		pair := matrix[i]
+		src := srcs[pair.deleted]
+		dst := dsts[pair.added]
+
+		if dst == nil || src == nil {
+			// It was already matched before
+			continue
+		}
+
+		renames = append(renames, &Change{From: src.From, To: dst.To})
+
+		// Claim destination and source as matched
+		dsts[pair.added] = nil
+		srcs[pair.deleted] = nil
+	}
+
+	d.modified = append(d.modified, renames...)
+	d.added = compactChanges(dsts)
+	d.deleted = compactChanges(srcs)
+
+	return nil
+}
+
+func (d *renameDetector) detect() (Changes, error) {
+	if len(d.added) > 0 && len(d.deleted) > 0 {
+		d.detectExactRenames()
+
+		if !d.onlyExact {
+			if err := d.detectContentRenames(); err != nil {
+				return nil, err
+			}
+		}
+	}
+
+	result := make(Changes, 0, len(d.added)+len(d.deleted)+len(d.modified))
+	result = append(result, d.added...)
+	result = append(result, d.deleted...)
+	result = append(result, d.modified...)
+
+	sort.Stable(result)
+
+	return result, nil
+}
+
+func bestNameMatch(change *Change, changes []*Change) *Change {
+	var best *Change
+	var bestScore int
+
+	cname := changeName(change)
+
+	for _, c := range changes {
+		score := nameSimilarityScore(cname, changeName(c))
+		if score > bestScore {
+			bestScore = score
+			best = c
+		}
+	}
+
+	return best
+}
+
+func nameSimilarityScore(a, b string) int {
+	aDirLen := strings.LastIndexByte(a, '/') + 1
+	bDirLen := strings.LastIndexByte(b, '/') + 1
+
+	dirMin := min(aDirLen, bDirLen)
+	dirMax := max(aDirLen, bDirLen)
+
+	var dirScoreLtr, dirScoreRtl int
+	if dirMax == 0 {
+		dirScoreLtr = 100
+		dirScoreRtl = 100
+	} else {
+		var dirSim int
+
+		for ; dirSim < dirMin; dirSim++ {
+			if a[dirSim] != b[dirSim] {
+				break
+			}
+		}
+
+		dirScoreLtr = dirSim * 100 / dirMax
+
+		if dirScoreLtr == 100 {
+			dirScoreRtl = 100
+		} else {
+			for dirSim = 0; dirSim < dirMin; dirSim++ {
+				if a[aDirLen-1-dirSim] != b[bDirLen-1-dirSim] {
+					break
+				}
+			}
+			dirScoreRtl = dirSim * 100 / dirMax
+		}
+	}
+
+	fileMin := min(len(a)-aDirLen, len(b)-bDirLen)
+	fileMax := max(len(a)-aDirLen, len(b)-bDirLen)
+
+	fileSim := 0
+	for ; fileSim < fileMin; fileSim++ {
+		if a[len(a)-1-fileSim] != b[len(b)-1-fileSim] {
+			break
+		}
+	}
+	fileScore := fileSim * 100 / fileMax
+
+	return (((dirScoreLtr + dirScoreRtl) * 25) + (fileScore * 50)) / 100
+}
+
+func changeName(c *Change) string {
+	if c.To != empty {
+		return c.To.Name
+	}
+	return c.From.Name
+}
+
+func changeHash(c *Change) plumbing.Hash {
+	if c.To != empty {
+		return c.To.TreeEntry.Hash
+	}
+
+	return c.From.TreeEntry.Hash
+}
+
+func changeMode(c *Change) filemode.FileMode {
+	if c.To != empty {
+		return c.To.TreeEntry.Mode
+	}
+
+	return c.From.TreeEntry.Mode
+}
+
+func sameMode(a, b *Change) bool {
+	return changeMode(a) == changeMode(b)
+}
+
+func groupChangesByHash(changes []*Change) map[plumbing.Hash][]*Change {
+	var result = make(map[plumbing.Hash][]*Change)
+	for _, c := range changes {
+		hash := changeHash(c)
+		result[hash] = append(result[hash], c)
+	}
+	return result
+}
+
+type similarityMatrix []similarityPair
+
+func (m similarityMatrix) Len() int      { return len(m) }
+func (m similarityMatrix) Swap(i, j int) { m[i], m[j] = m[j], m[i] }
+func (m similarityMatrix) Less(i, j int) bool {
+	if m[i].score == m[j].score {
+		if m[i].added == m[j].added {
+			return m[i].deleted < m[j].deleted
+		}
+		return m[i].added < m[j].added
+	}
+	return m[i].score < m[j].score
+}
+
+type similarityPair struct {
+	// index of the added file
+	added int
+	// index of the deleted file
+	deleted int
+	// similarity score
+	score int
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}
+
+func min(a, b int) int {
+	if a < b {
+		return a
+	}
+	return b
+}
+
+func buildSimilarityMatrix(srcs, dsts []*Change, renameScore int) (similarityMatrix, error) {
+	// Allocate for the worst-case scenario where every pair has a score
+	// that we need to consider. We might not need that many.
+	matrix := make(similarityMatrix, 0, len(srcs)*len(dsts))
+	srcSizes := make([]int64, len(srcs))
+	dstSizes := make([]int64, len(dsts))
+	dstTooLarge := make(map[int]bool)
+
+	// Consider each pair of files, if the score is above the minimum
+	// threshold we need to record that scoring in the matrix so we can
+	// later find the best matches.
+outerLoop:
+	for srcIdx, src := range srcs {
+		if changeMode(src) != filemode.Regular {
+			continue
+		}
+
+		// Declare the from file and the similarity index here to be able to
+		// reuse it inside the inner loop. The reason to not initialize them
+		// here is so we can skip the initialization in case they happen to
+		// not be needed later. They will be initialized inside the inner
+		// loop if and only if they're needed and reused in subsequent passes.
+		var from *File
+		var s *similarityIndex
+		var err error
+		for dstIdx, dst := range dsts {
+			if changeMode(dst) != filemode.Regular {
+				continue
+			}
+
+			if dstTooLarge[dstIdx] {
+				continue
+			}
+
+			var to *File
+			srcSize := srcSizes[srcIdx]
+			if srcSize == 0 {
+				from, _, err = src.Files()
+				if err != nil {
+					return nil, err
+				}
+				srcSize = from.Size + 1
+				srcSizes[srcIdx] = srcSize
+			}
+
+			dstSize := dstSizes[dstIdx]
+			if dstSize == 0 {
+				_, to, err = dst.Files()
+				if err != nil {
+					return nil, err
+				}
+				dstSize = to.Size + 1
+				dstSizes[dstIdx] = dstSize
+			}
+
+			min, max := srcSize, dstSize
+			if dstSize < srcSize {
+				min = dstSize
+				max = srcSize
+			}
+
+			if int(min*100/max) < renameScore {
+				// File sizes are too different to be a match
+				continue
+			}
+
+			if s == nil {
+				s, err = fileSimilarityIndex(from)
+				if err != nil {
+					if err == errIndexFull {
+						continue outerLoop
+					}
+					return nil, err
+				}
+			}
+
+			if to == nil {
+				_, to, err = dst.Files()
+				if err != nil {
+					return nil, err
+				}
+			}
+
+			di, err := fileSimilarityIndex(to)
+			if err != nil {
+				if err == errIndexFull {
+					dstTooLarge[dstIdx] = true
+				}
+
+				return nil, err
+			}
+
+			contentScore := s.score(di, 10000)
+			// The name score returns a value between 0 and 100, so we need to
+			// convert it to the same range as the content score.
+			nameScore := nameSimilarityScore(src.From.Name, dst.To.Name) * 100
+			score := (contentScore*99 + nameScore*1) / 10000
+
+			if score < renameScore {
+				continue
+			}
+
+			matrix = append(matrix, similarityPair{added: dstIdx, deleted: srcIdx, score: score})
+		}
+	}
+
+	sort.Stable(matrix)
+
+	return matrix, nil
+}
+
+func compactChanges(changes []*Change) []*Change {
+	var result []*Change
+	for _, c := range changes {
+		if c != nil {
+			result = append(result, c)
+		}
+	}
+	return result
+}
+
+const (
+	keyShift      = 32
+	maxCountValue = (1 << keyShift) - 1
+)
+
+var errIndexFull = errors.New("index is full")
+
+// similarityIndex is an index structure of lines/blocks in one file.
+// This structure can be used to compute an approximation of the similarity
+// between two files.
+// To save space in memory, this index uses a space efficient encoding which
+// will not exceed 1MiB per instance. The index starts out at a smaller size
+// (closer to 2KiB), but may grow as more distinct blocks withing the scanned
+// file are discovered.
+// see: https://github.com/eclipse/jgit/blob/master/org.eclipse.jgit/src/org/eclipse/jgit/diff/SimilarityIndex.java
+type similarityIndex struct {
+	hashed uint64
+	// number of non-zero entries in hashes
+	numHashes int
+	growAt    int
+	hashes    []keyCountPair
+	hashBits  int
+}
+
+func fileSimilarityIndex(f *File) (*similarityIndex, error) {
+	idx := newSimilarityIndex()
+	if err := idx.hash(f); err != nil {
+		return nil, err
+	}
+
+	sort.Stable(keyCountPairs(idx.hashes))
+
+	return idx, nil
+}
+
+func newSimilarityIndex() *similarityIndex {
+	return &similarityIndex{
+		hashBits: 8,
+		hashes:   make([]keyCountPair, 1<<8),
+		growAt:   shouldGrowAt(8),
+	}
+}
+
+func (i *similarityIndex) hash(f *File) error {
+	isBin, err := f.IsBinary()
+	if err != nil {
+		return err
+	}
+
+	r, err := f.Reader()
+	if err != nil {
+		return err
+	}
+
+	defer ioutil.CheckClose(r, &err)
+
+	return i.hashContent(r, f.Size, isBin)
+}
+
+func (i *similarityIndex) hashContent(r io.Reader, size int64, isBin bool) error {
+	var buf = make([]byte, 4096)
+	var ptr, cnt int
+	remaining := size
+
+	for 0 < remaining {
+		hash := 5381
+		var blockHashedCnt uint64
+
+		// Hash one line or block, whatever happens first
+		n := int64(0)
+		for {
+			if ptr == cnt {
+				ptr = 0
+				var err error
+				cnt, err = io.ReadFull(r, buf)
+				if err != nil && err != io.ErrUnexpectedEOF {
+					return err
+				}
+
+				if cnt == 0 {
+					return io.EOF
+				}
+			}
+			n++
+			c := buf[ptr] & 0xff
+			ptr++
+
+			// Ignore CR in CRLF sequence if it's text
+			if !isBin && c == '\r' && ptr < cnt && buf[ptr] == '\n' {
+				continue
+			}
+			blockHashedCnt++
+
+			if c == '\n' {
+				break
+			}
+
+			hash = (hash << 5) + hash + int(c)
+
+			if n >= 64 || n >= remaining {
+				break
+			}
+		}
+		i.hashed += blockHashedCnt
+		if err := i.add(hash, blockHashedCnt); err != nil {
+			return err
+		}
+		remaining -= n
+	}
+
+	return nil
+}
+
+// score computes the similarity score between this index and another one.
+// A region of a file is defined as a line in a text file or a fixed-size
+// block in a binary file. To prepare an index, each region in the file is
+// hashed; the values and counts of hashes are retained in a sorted table.
+// Define the similarity fraction F as the count of matching regions between
+// the two files divided between the maximum count of regions in either file.
+// The similarity score is F multiplied by the maxScore constant, yielding a
+// range [0, maxScore]. It is defined as maxScore for the degenerate case of
+// two empty files.
+// The similarity score is symmetrical; i.e. a.score(b) == b.score(a).
+func (i *similarityIndex) score(other *similarityIndex, maxScore int) int {
+	var maxHashed = i.hashed
+	if maxHashed < other.hashed {
+		maxHashed = other.hashed
+	}
+	if maxHashed == 0 {
+		return maxScore
+	}
+
+	return int(i.common(other) * uint64(maxScore) / maxHashed)
+}
+
+func (i *similarityIndex) common(dst *similarityIndex) uint64 {
+	srcIdx, dstIdx := 0, 0
+	if i.numHashes == 0 || dst.numHashes == 0 {
+		return 0
+	}
+
+	var common uint64
+	srcKey, dstKey := i.hashes[srcIdx].key(), dst.hashes[dstIdx].key()
+
+	for {
+		if srcKey == dstKey {
+			srcCnt, dstCnt := i.hashes[srcIdx].count(), dst.hashes[dstIdx].count()
+			if srcCnt < dstCnt {
+				common += srcCnt
+			} else {
+				common += dstCnt
+			}
+
+			srcIdx++
+			if srcIdx == len(i.hashes) {
+				break
+			}
+			srcKey = i.hashes[srcIdx].key()
+
+			dstIdx++
+			if dstIdx == len(dst.hashes) {
+				break
+			}
+			dstKey = dst.hashes[dstIdx].key()
+		} else if srcKey < dstKey {
+			// Region of src that is not in dst
+			srcIdx++
+			if srcIdx == len(i.hashes) {
+				break
+			}
+			srcKey = i.hashes[srcIdx].key()
+		} else {
+			// Region of dst that is not in src
+			dstIdx++
+			if dstIdx == len(dst.hashes) {
+				break
+			}
+			dstKey = dst.hashes[dstIdx].key()
+		}
+	}
+
+	return common
+}
+
+func (i *similarityIndex) add(key int, cnt uint64) error {
+	key = int(uint32(key*0x9e370001) >> 1)
+
+	j := i.slot(key)
+	for {
+		v := i.hashes[j]
+		if v == 0 {
+			// It's an empty slot, so we can store it here.
+			if i.growAt <= i.numHashes {
+				if err := i.grow(); err != nil {
+					return err
+				}
+				j = i.slot(key)
+				continue
+			}
+
+			var err error
+			i.hashes[j], err = newKeyCountPair(key, cnt)
+			if err != nil {
+				return err
+			}
+			i.numHashes++
+			return nil
+		} else if v.key() == key {
+			// It's the same key, so increment the counter.
+			var err error
+			i.hashes[j], err = newKeyCountPair(key, v.count()+cnt)
+			if err != nil {
+				return err
+			}
+			return nil
+		} else if j+1 >= len(i.hashes) {
+			j = 0
+		} else {
+			j++
+		}
+	}
+}
+
+type keyCountPair uint64
+
+func newKeyCountPair(key int, cnt uint64) (keyCountPair, error) {
+	if cnt > maxCountValue {
+		return 0, errIndexFull
+	}
+
+	return keyCountPair((uint64(key) << keyShift) | cnt), nil
+}
+
+func (p keyCountPair) key() int {
+	return int(p >> keyShift)
+}
+
+func (p keyCountPair) count() uint64 {
+	return uint64(p) & maxCountValue
+}
+
+func (i *similarityIndex) slot(key int) int {
+	// We use 31 - hashBits because the upper bit was already forced
+	// to be 0 and we want the remaining high bits to be used as the
+	// table slot.
+	return int(uint32(key) >> (31 - i.hashBits))
+}
+
+func shouldGrowAt(hashBits int) int {
+	return (1 << hashBits) * (hashBits - 3) / hashBits
+}
+
+func (i *similarityIndex) grow() error {
+	if i.hashBits == 30 {
+		return errIndexFull
+	}
+
+	old := i.hashes
+
+	i.hashBits++
+	i.growAt = shouldGrowAt(i.hashBits)
+
+	// TODO(erizocosmico): find a way to check if it will OOM and return
+	// errIndexFull instead.
+	i.hashes = make([]keyCountPair, 1<<i.hashBits)
+
+	for _, v := range old {
+		if v != 0 {
+			j := i.slot(v.key())
+			for i.hashes[j] != 0 {
+				j++
+				if j >= len(i.hashes) {
+					j = 0
+				}
+			}
+			i.hashes[j] = v
+		}
+	}
+
+	return nil
+}
+
+type keyCountPairs []keyCountPair
+
+func (p keyCountPairs) Len() int           { return len(p) }
+func (p keyCountPairs) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
+func (p keyCountPairs) Less(i, j int) bool { return p[i] < p[j] }