<commit_before>package dm

import (
	"sort"

	"github.com/davecgh/go-spew/spew"
	"github.com/golang/glog"
)

// We assume that aFile is the base file version and that bFile is derived from
// aFile. Therefore we also assume that block copies occur in bFile, but not
// in aFile.  As a result, when processing gaps (unmatched regions), we focus
// on bFile when finding gaps, and then find corresponding regions in aFile,
// which may be processed with more than one section of bFile.

// Note that this is not intended to be efficient, just effective (hopefully).
// If it turns out to be useful, but slow, there is plenty of room for optimization.

// TODO How can we use sentinal lines here? Maybe produce a new FileRange
// that has unique sentinals at the start and end of each Full FileRange;
// or common start sentinals at the start of every Full FileRange, and
// common end sentinals at the end of every Full FileRange, so that we'd be
// guaranteed of a match at the start, and then not worry about gap filling
// before BOF or after EOF.

// TODO Introduce two ordered data structures for storing the *BlockPair's,
// one sorting by AIndex, the other by BIndex. This will eliminate all the
// SortBlockPairsBy*Index calls.
// We'll need the ability to:
// * insert elements, perhaps with a hint (e.g. when splitting a BlockPair,
//	 we might want to replace one entry with several);
// * forward iterate over the members, tolerating modifications (e.g. filling
//	 gaps while iterating, or splitting an entry);
// * get the last member, and possibly the first;
// * lookup members (e.g. when filling gaps by AIndex, we'll need to find
//	 the neighbors of the BlockPair in B).
// We might be able to start with a single BlockPair representing a mismatch
// between the entirety of the two files, then we'd try to create matches within
// that BlockPair. For easy of operations we might want to insert two other
// BlockPairs (sentinals) marking the start and end of the two files.

func PerformDiff(aFile, bFile *File, config DifferencerConfig) (pairs []*BlockPair) {
	defer glog.Flush()

	p := diffState{
		aFile:      aFile,
		bFile:      bFile,
		aFullRange: aFile.GetFullRange(),
		bFullRange: bFile.GetFullRange(),
		aRange:     aFile.GetFullRange(),
		bRange:     bFile.GetFullRange(),
		//		aRemainingCount: aFile.GetLineCount(),
		bRemainingCount: bFile.GetLineCount(),
		config:          config,
	}

	glog.Info("PerformDiff entry, diffState:\n", p.SDumpToDepth(1))

	if !p.someRangeIsEmpty() {
		if true {
			// Experiment in an effort to better handle moves followed by edits, and
			// also copies (possibly followed by edits):
			// 1) Match common prefix and suffix, but back off until they don't end
			//    in non-rare lines.
			// 2) Align rare lines with LCS.
			// 3) Extend common prefix and suffix of the LCS entries, with no overlap
			//    (i.e. so far there can be no copies, so there can only be 1-to-1
			//    matches between A and B lines, or no match at all).  Where gaps
			//    remain, back off if the bordering BlockPairs end in non-rare lines.
			// 4) Move detection: Find all the gaps in A that contain
			//		rare lines, and and try to match those up with gaps in B. Choose
			//    the best such match for each gap in A, but at most 1 (i.e. not
			//    yet detecting copies). Within such a match, if there are multiple
			//    BlockPairs, try to fill the gaps between those BlockPairs,
			// 5) Copy detection: Find all the gaps in B that contain rare lines, and
			//    try to match those up with any lines in A.
			// 6) TODO in a future experiment: if there are changes where there are
			//    significantly more lines in B than A, we can do sub-line LCS to see
			//    if we can identify where there might be an insertion among the
			//    B lines, rather than just edits, and then attempt to match just that
			//    portion with A.

			if p.config.matchEnds {
				p.exp_phase1_ends()
			}

			if !p.someRangeIsEmpty() {<commit_msg>Added notes.<commit_after>package dm

import (
	"sort"

	"github.com/davecgh/go-spew/spew"
	"github.com/golang/glog"
)

// We assume that aFile is the base file version and that bFile is derived from
// aFile. Therefore we also assume that block copies occur in bFile, but not
// in aFile.  As a result, when processing gaps (unmatched regions), we focus
// on bFile when finding gaps, and then find corresponding regions in aFile,
// which may be processed with more than one section of bFile.

// Note that this is not intended to be efficient, just effective (hopefully).
// If it turns out to be useful, but slow, there is plenty of room for optimization.

// TODO How can we use sentinal lines here? Maybe produce a new FileRange
// that has unique sentinals at the start and end of each Full FileRange;
// or common start sentinals at the start of every Full FileRange, and
// common end sentinals at the end of every Full FileRange, so that we'd be
// guaranteed of a match at the start, and then not worry about gap filling
// before BOF or after EOF.

// TODO Introduce two ordered data structures for storing the *BlockPair's,
// one sorting by AIndex, the other by BIndex. This will eliminate all the
// SortBlockPairsBy*Index calls.
// We'll need the ability to:
// * insert elements, perhaps with a hint (e.g. when splitting a BlockPair,
//	 we might want to replace one entry with several);
// * forward iterate over the members, tolerating modifications (e.g. filling
//	 gaps while iterating, or splitting an entry);
// * get the last member, and possibly the first;
// * lookup members (e.g. when filling gaps by AIndex, we'll need to find
//	 the neighbors of the BlockPair in B).
// We might be able to start with a single BlockPair representing a mismatch
// between the entirety of the two files, then we'd try to create matches within
// that BlockPair. For easy of operations we might want to insert two other
// BlockPairs (sentinals) marking the start and end of the two files.

func PerformDiff(aFile, bFile *File, config DifferencerConfig) (pairs []*BlockPair) {
	defer glog.Flush()

	p := diffState{
		aFile:      aFile,
		bFile:      bFile,
		aFullRange: aFile.GetFullRange(),
		bFullRange: bFile.GetFullRange(),
		aRange:     aFile.GetFullRange(),
		bRange:     bFile.GetFullRange(),
		//		aRemainingCount: aFile.GetLineCount(),
		bRemainingCount: bFile.GetLineCount(),
		config:          config,
	}

	glog.Info("PerformDiff entry, diffState:\n", p.SDumpToDepth(1))

	if !p.someRangeIsEmpty() {
		if true {
			// Experiment in an effort to better handle moves followed by edits, and
			// also copies (possibly followed by edits):
			// 1) Match common prefix and suffix, but back off until they don't end
			//    in non-rare lines.
			// 2) Align rare lines with LCS.
			// 3) Extend common prefix and suffix of the LCS entries, with no overlap
			//    (i.e. so far there can be no copies, so there can only be 1-to-1
			//    matches between A and B lines, or no match at all).  Where gaps
			//    remain, back off if the bordering BlockPairs end in non-rare lines.
			
			// 3.5) TODO Before move detection, if a gap is small in both A and B,
			//      (e.g. size of gap is within 50% on both sides and/or lines is < 5)
			//		  see if the edit distance is small at the token or character level,
			//      because it may simply be that a small edit has taken place, and
			//      we don't need to go to the expense of looking for a move.
			
			// 4) Move detection: Find all the gaps in A that contain
			//		rare lines, and and try to match those up with gaps in B. Choose
			//    the best such match for each gap in A, but at most 1 (i.e. not
			//    yet detecting copies). Within such a match, if there are multiple
			//    BlockPairs, try to fill the gaps between those BlockPairs,
			// 5) Copy detection: Find all the gaps in B that contain rare lines, and
			//    try to match those up with any lines in A.
			// 6) TODO in a future experiment: if there are changes where there are
			//    significantly more lines in B than A, we can do sub-line LCS to see
			//    if we can identify where there might be an insertion among the
			//    B lines, rather than just edits, and then attempt to match just that
			//    portion with A.

			if p.config.matchEnds {
				p.exp_phase1_ends()
			}

			if !p.someRangeIsEmpty() {
{'fraction_non_alphanumeric': 0.07913927077106993, 'fraction_numerical': 0.0032277346084877466, 'mean_word_length': 2.9555555555555557, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5948113', 'n_tokens_mistral': 2608, 'n_tokens_neox': 2399, 'n_words': 1239}