package object

import (
	
	
	
	

	
	
	
	
)
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 (
	 Changes,
	 *DiffTreeOptions,
) (Changes, error) {
	if  == nil {
		 = DefaultDiffTreeOptions
	}

	 := &renameDetector{
		renameScore: int(.RenameScore),
		renameLimit: int(.RenameLimit),
		onlyExact:   .OnlyExactRenames,
	}

	for ,  := range  {
		,  := .Action()
		if  != nil {
			return nil, 
		}

		switch  {
		case merkletrie.Insert:
			.added = append(.added, )
		case merkletrie.Delete:
			.deleted = append(.deleted, )
		default:
			.modified = append(.modified, )
		}
	}

	return .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
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 ( *renameDetector) () {
	 := groupChangesByHash(.added)
	 := groupChangesByHash(.deleted)
	var  []*Change
	var  [][]*Change
	var  []*Change

	for ,  := range  {
		if len() == 1 {
			 = append(, [0])
		} else {
			 = append(, )
		}
	}

	for ,  := range  {
		 := changeHash()
		 := []

		if len() == 1 {
			if sameMode(, [0]) {
				.modified = append(.modified, &Change{From: [0].From, To: .To})
				delete(, )
			} else {
				 = append(, )
			}
		} else if len() > 1 {
			 := bestNameMatch(, )
			if  != nil && sameMode(, ) {
				.modified = append(.modified, &Change{From: .From, To: .To})
				delete(, )

				var  = make([]*Change, 0, len()-1)
				for ,  := range  {
					if  !=  {
						 = append(, )
					}
				}
				[] = 
			}
		} else {
			 = append(, )
		}
	}

	for ,  := range  {
		 := changeHash([0])
		 := []

		if len() == 1 {
			 := [0]
			 := bestNameMatch(, )
			if  != nil && sameMode(, ) {
				.modified = append(.modified, &Change{From: .From, To: .To})
				delete(, )

				for ,  := range  {
					if  !=  {
						 = append(, )
					}
				}
			} else {
				 = append(, ...)
			}
		} else if len() > 1 {
			 := len() * len()
			if .renameLimit > 0 && .renameLimit <  {
				 = .renameLimit
			}

			 := make(similarityMatrix, 0, )

			for ,  := range  {
				 := changeName()

				for ,  := range  {
					 := changeName()

					 := nameSimilarityScore(, )
					 = append(, similarityPair{added: , deleted: , score: })

					if len() >=  {
						break
					}
				}

				if len() >=  {
					break
				}
			}

			sort.Stable()

			 := make(map[*Change]struct{})
			 := make(map[*Change]struct{})
			for  := len() - 1;  >= 0; -- {
				 := [[].deleted]
				 := [[].added]

it was already matched
					continue
				}

				[] = struct{}{}
				[] = struct{}{}
				.modified = append(.modified, &Change{From: .From, To: .To})
				[[].added] = nil
				[[].deleted] = nil
			}

			for ,  := range  {
				if ,  := []; ! &&  != nil {
					 = append(, )
				}
			}

			var  = make([]*Change, 0, len()-len())
			for ,  := range  {
				if ,  := []; ! &&  != nil {
					 = append(, )
				}
			}
			[] = 
		} else {
			 = append(, ...)
		}
	}

	.added = 
	.deleted = nil
	for ,  := range  {
		.deleted = append(.deleted, ...)
	}
}
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 ( *renameDetector) () error {
	 := max(len(.added), len(.deleted))
	if .renameLimit > 0 &&  > .renameLimit {
		return nil
	}

	,  := .deleted, .added
	,  := buildSimilarityMatrix(, , .renameScore)
	if  != nil {
		return 
	}
	 := make([]*Change, 0, min(len(), len()))
Match rename pairs on a first come, first serve basis until we have looked at everything that is above the minimum score.
	for  := len() - 1;  >= 0; -- {
		 := []
		 := [.deleted]
		 := [.added]

It was already matched before
			continue
		}

		 = append(, &Change{From: .From, To: .To})
Claim destination and source as matched
		[.added] = nil
		[.deleted] = nil
	}

	.modified = append(.modified, ...)
	.added = compactChanges()
	.deleted = compactChanges()

	return nil
}

func ( *renameDetector) () (Changes, error) {
	if len(.added) > 0 && len(.deleted) > 0 {
		.detectExactRenames()

		if !.onlyExact {
			if  := .detectContentRenames();  != nil {
				return nil, 
			}
		}
	}

	 := make(Changes, 0, len(.added)+len(.deleted)+len(.modified))
	 = append(, .added...)
	 = append(, .deleted...)
	 = append(, .modified...)

	sort.Stable()

	return , nil
}

func ( *Change,  []*Change) *Change {
	var  *Change
	var  int

	 := changeName()

	for ,  := range  {
		 := nameSimilarityScore(, changeName())
		if  >  {
			 = 
			 = 
		}
	}

	return 
}

func (,  string) int {
	 := strings.LastIndexByte(, '/') + 1
	 := strings.LastIndexByte(, '/') + 1

	 := min(, )
	 := max(, )

	var ,  int
	if  == 0 {
		 = 100
		 = 100
	} else {
		var  int

		for ;  < ; ++ {
			if [] != [] {
				break
			}
		}

		 =  * 100 / 

		if  == 100 {
			 = 100
		} else {
			for  = 0;  < ; ++ {
				if [-1-] != [-1-] {
					break
				}
			}
			 =  * 100 / 
		}
	}

	 := min(len()-, len()-)
	 := max(len()-, len()-)

	 := 0
	for ;  < ; ++ {
		if [len()-1-] != [len()-1-] {
			break
		}
	}
	 :=  * 100 / 

	return ((( + ) * 25) + ( * 50)) / 100
}

func ( *Change) string {
	if .To != empty {
		return .To.Name
	}
	return .From.Name
}

func ( *Change) plumbing.Hash {
	if .To != empty {
		return .To.TreeEntry.Hash
	}

	return .From.TreeEntry.Hash
}

func ( *Change) filemode.FileMode {
	if .To != empty {
		return .To.TreeEntry.Mode
	}

	return .From.TreeEntry.Mode
}

func (,  *Change) bool {
	return changeMode() == changeMode()
}

func ( []*Change) map[plumbing.Hash][]*Change {
	var  = make(map[plumbing.Hash][]*Change)
	for ,  := range  {
		 := changeHash()
		[] = append([], )
	}
	return 
}

type similarityMatrix []similarityPair

func ( similarityMatrix) () int      { return len() }
func ( similarityMatrix) (,  int) { [], [] = [], [] }
func ( similarityMatrix) (,  int) bool {
	if [].score == [].score {
		if [].added == [].added {
			return [].deleted < [].deleted
		}
		return [].added < [].added
	}
	return [].score < [].score
}

index of the added file
index of the deleted file
similarity score
	score int
}

func (,  int) int {
	if  >  {
		return 
	}
	return 
}

func (,  int) int {
	if  <  {
		return 
	}
	return 
}

Allocate for the worst-case scenario where every pair has a score that we need to consider. We might not need that many.
	 := make(similarityMatrix, 0, len()*len())
	 := make([]int64, len())
	 := make([]int64, len())
	 := 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.
:
	for ,  := range  {
		if changeMode() != 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  *File
		var  *similarityIndex
		var  error
		for ,  := range  {
			if changeMode() != filemode.Regular {
				continue
			}

			if [] {
				continue
			}

			var  *File
			 := []
			if  == 0 {
				, _,  = .Files()
				if  != nil {
					return nil, 
				}
				 = .Size + 1
				[] = 
			}

			 := []
			if  == 0 {
				_, ,  = .Files()
				if  != nil {
					return nil, 
				}
				 = .Size + 1
				[] = 
			}

			,  := , 
			if  <  {
				 = 
				 = 
			}

File sizes are too different to be a match
				continue
			}

			if  == nil {
				,  = fileSimilarityIndex()
				if  != nil {
					if  == errIndexFull {
						continue 
					}
					return nil, 
				}
			}

			if  == nil {
				_, ,  = .Files()
				if  != nil {
					return nil, 
				}
			}

			,  := fileSimilarityIndex()
			if  != nil {
				if  == errIndexFull {
					[] = true
				}

				return nil, 
			}

The name score returns a value between 0 and 100, so we need to convert it to the same range as the content score.
			 := nameSimilarityScore(.From.Name, .To.Name) * 100
			 := (*99 + *1) / 10000

			if  <  {
				continue
			}

			 = append(, similarityPair{added: , deleted: , score: })
		}
	}

	sort.Stable()

	return , nil
}

func ( []*Change) []*Change {
	var  []*Change
	for ,  := range  {
		if  != nil {
			 = append(, )
		}
	}
	return 
}

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 {
number of non-zero entries in hashes
	numHashes int
	growAt    int
	hashes    []keyCountPair
	hashBits  int
}

func ( *File) (*similarityIndex, error) {
	 := newSimilarityIndex()
	if  := .hash();  != nil {
		return nil, 
	}

	sort.Stable(keyCountPairs(.hashes))

	return , nil
}

func () *similarityIndex {
	return &similarityIndex{
		hashBits: 8,
		hashes:   make([]keyCountPair, 1<<8),
		growAt:   shouldGrowAt(8),
	}
}

func ( *similarityIndex) ( *File) error {
	,  := .IsBinary()
	if  != nil {
		return 
	}

	,  := .Reader()
	if  != nil {
		return 
	}

	defer ioutil.CheckClose(, &)

	return .hashContent(, .Size, )
}

func ( *similarityIndex) ( io.Reader,  int64,  bool) error {
	var  = make([]byte, 4096)
	var ,  int
	 := 

	for 0 <  {
		 := 5381
		var  uint64
Hash one line or block, whatever happens first
		 := int64(0)
		for {
			if  ==  {
				 = 0
				var  error
				,  = io.ReadFull(, )
				if  != nil &&  != io.ErrUnexpectedEOF {
					return 
				}

				if  == 0 {
					return io.EOF
				}
			}
			++
			 := [] & 0xff
			++
Ignore CR in CRLF sequence if it's text
			if ! &&  == '\r' &&  <  && [] == '\n' {
				continue
			}
			++

			if  == '\n' {
				break
			}

			 = ( << 5) +  + int()

			if  >= 64 ||  >=  {
				break
			}
		}
		.hashed += 
		if  := .add(, );  != nil {
			return 
		}
		 -= 
	}

	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 ( *similarityIndex) ( *similarityIndex,  int) int {
	var  = .hashed
	if  < .hashed {
		 = .hashed
	}
	if  == 0 {
		return 
	}

	return int(.common() * uint64() / )
}

func ( *similarityIndex) ( *similarityIndex) uint64 {
	,  := 0, 0
	if .numHashes == 0 || .numHashes == 0 {
		return 0
	}

	var  uint64
	,  := .hashes[].key(), .hashes[].key()

	for {
		if  ==  {
			,  := .hashes[].count(), .hashes[].count()
			if  <  {
				 += 
			} else {
				 += 
			}

			++
			if  == len(.hashes) {
				break
			}
			 = .hashes[].key()

			++
			if  == len(.hashes) {
				break
			}
			 = .hashes[].key()
Region of src that is not in dst
			++
			if  == len(.hashes) {
				break
			}
			 = .hashes[].key()
Region of dst that is not in src
			++
			if  == len(.hashes) {
				break
			}
			 = .hashes[].key()
		}
	}

	return 
}

func ( *similarityIndex) ( int,  uint64) error {
	 = int(uint32()*0x9e370001 >> 1)

	 := .slot()
	for {
		 := .hashes[]
It's an empty slot, so we can store it here.
			if .growAt <= .numHashes {
				if  := .grow();  != nil {
					return 
				}
				 = .slot()
				continue
			}

			var  error
			.hashes[],  = newKeyCountPair(, )
			if  != nil {
				return 
			}
			.numHashes++
			return nil
It's the same key, so increment the counter.
			var  error
			.hashes[],  = newKeyCountPair(, .count()+)
			if  != nil {
				return 
			}
			return nil
		} else if +1 >= len(.hashes) {
			 = 0
		} else {
			++
		}
	}
}

type keyCountPair uint64

func ( int,  uint64) (keyCountPair, error) {
	if  > maxCountValue {
		return 0, errIndexFull
	}

	return keyCountPair((uint64() << keyShift) | ), nil
}

func ( keyCountPair) () int {
	return int( >> keyShift)
}

func ( keyCountPair) () uint64 {
	return uint64() & maxCountValue
}

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() >> uint(31 - .hashBits))
}

func ( int) int {
	return (1 << uint()) * ( - 3) / 
}

func ( *similarityIndex) () error {
	if .hashBits == 30 {
		return errIndexFull
	}

	 := .hashes

	.hashBits++
	.growAt = shouldGrowAt(.hashBits)
TODO(erizocosmico): find a way to check if it will OOM and return errIndexFull instead.
	.hashes = make([]keyCountPair, 1<<uint(.hashBits))

	for ,  := range  {
		if  != 0 {
			 := .slot(.key())
			for .hashes[] != 0 {
				++
				if  >= len(.hashes) {
					 = 0
				}
			}
			.hashes[] = 
		}
	}

	return nil
}

type keyCountPairs []keyCountPair

func ( keyCountPairs) () int           { return len() }
func ( keyCountPairs) (,  int)      { [], [] = [], [] }