<commit_before>/*@flow*/
/*
 * Copyright 2014 XWiki SAS
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
"use strict";

var Operation = require('./Operation');
var Common = require('./Common');

/*::
import type { Operation_t } from './Operation';
*/

var DEFAULT_BLOCKSIZE = module.exports.DEFAULT_BLOCKSIZE = 8;

var hashScan = function (str, blockSize) {
    var out = {};
    for (var i = 0; i + blockSize <= str.length; i++) {
        var slice = str.slice(i, i + blockSize);
        (out[slice] = out[slice] || []).push(i);
    }
    return out;
};

// return true if two segments do not overlap, else false
var isCompatible = function (m1, m2) {
    if (m1.oldIndex < m2.oldIndex) {
        if (m1.oldIndex + m1.length > m2.oldIndex) { return false; }
        if (m1.newIndex + m1.length > m2.newIndex) { return false; }
    } else if (m2.oldIndex < m1.oldIndex) {
        if (m2.oldIndex + m2.length > m1.oldIndex) { return false; }
        if (m2.newIndex + m2.length > m1.newIndex) { return false; }
    } else {
        return false;
    }
    return true;
};

var scoreMatch = function (m) {
    return (m.length * 2) - m.oldIndex - m.newIndex;
};

/*  iterate backwards through and array, splicing out indices to remove
    the indices to remove MUST be in ascending order
    otherwise this could remove the wrong values
    operates strictly via side-effects */
var removeAscendingIndices = function (A, toRemove) {
    if (!toRemove.length) { return; }
    for (var j = toRemove.length - 1; j > -1; j--) {
        A.splice(toRemove[j], 1);
    }
};

/*  given a candidate match and the list of pending matches
    evaluate whether the candidate conflicts with existing matches
    if the candidate is determined to be a worse match than existing matches
        return false
    otherwise return the list of candidates which should be replaced

    returns either:
    false => the candidate is incompatible, and its conflicts are more valuable
    empty array => truthy, but there is nothing to remove (no conflicts)
    array => conflicting elements to replace with the candidate
*/
var listInferiorCandidates = function (current, pending) {
    var score_m = scoreMatch(current);
    var score_rest = 0;
    var toRemove = [];

    var l = pending.length;
    for (var i = 0; i < l; i++) {
        if (isCompatible(current, pending[i])) { continue; }
        toRemove.push(i);
        score_rest += scoreMatch(pending[i]);
        if (score_rest > score_m) { return false; }
    }

    return toRemove;
};

/*  called with all the matches, including the common start and common end, if they exist...

    A: Common start (should not be replaced)
    B: potential operations
    B': satisfactory set of operations
    C: Common end (should not be replaced)

    this implementation does not do anything special to protect A and C
    it is believed that the way matches are produced, they should not be removed.
*/
var reduceMatches = function (matches) {
    // ascending sort
    matches.sort(function (a, b) { return (a.oldIndex + a.newIndex) - (b.oldIndex + b.newIndex); });
    var out = [];

    var l_m = matches.length;
    var toRemove;
    for (var i = 0; i < l_m; i++) {
        toRemove = listInferiorCandidates(matches[i], out);
        if (toRemove) {
            removeAscendingIndices(out, toRemove);
            out.push(matches[i]);
        }
    }
    return out;
};

var resolve = function (str, hash, blockSize) {
    var matches = [];
    var candidates = [];
    // do the same thing as was done in hashscan, but for the new string
    // look for commonalities between new and old data
    for (var i = 0; i + blockSize <= str.length; i++) {
        var slice = str.slice(i, i + blockSize);
        var instances = (hash[slice] || []).slice(0);
        for (var j = candidates.length - 1; j >= 0; j--) {
            var c = candidates[j];<commit_msg>make the diff function just a little bit faster<commit_after>/*@flow*/
/*
 * Copyright 2014 XWiki SAS
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
"use strict";

var Operation = require('./Operation');
var Common = require('./Common');

/*::
import type { Operation_t } from './Operation';
*/

var DEFAULT_BLOCKSIZE = module.exports.DEFAULT_BLOCKSIZE = 8;

var hashScan = function (str, blockSize) {
    var out = {};
    var l = str.length;
    for (var i = 0; i + blockSize <= l; i++) {
        var slice = str.slice(i, i + blockSize);
        (out[slice] = out[slice] || []).push(i);
    }
    return out;
};

// return true if two segments do not overlap, else false
var isCompatible = function (m1, m2) {
    if (m1.oldIndex < m2.oldIndex) {
        if (m1.oldIndex + m1.length > m2.oldIndex) { return false; }
        if (m1.newIndex + m1.length > m2.newIndex) { return false; }
    } else if (m2.oldIndex < m1.oldIndex) {
        if (m2.oldIndex + m2.length > m1.oldIndex) { return false; }
        if (m2.newIndex + m2.length > m1.newIndex) { return false; }
    } else {
        return false;
    }
    return true;
};

var scoreMatch = function (m) {
    return (m.length * 2) - m.oldIndex - m.newIndex;
};

var removeDescendingIndices = function (A, toRemove) {
    if (!toRemove.length) { return; }
    var l = toRemove.length;
    for (var j = 0; j < l; j++) {
        A.splice(toRemove[j], 1);
    }
};

/*  given a candidate match and the list of pending matches
    evaluate whether the candidate conflicts with existing matches
    if the candidate is determined to be a worse match than existing matches
        return false
    otherwise return the list of candidates which should be replaced

    returns either:
    false => the candidate is incompatible, and its conflicts are more valuable
    empty array => truthy, but there is nothing to remove (no conflicts)
    array => conflicting elements to replace with the candidate
*/
var listInferiorCandidates = function (current, pending) {
    var score_m = scoreMatch(current);
    var score_rest = 0;
    var toRemove = [];

    var l = pending.length;
    for (var i = l - 1; i >= 0; i--) {
        if (isCompatible(current, pending[i])) { continue; }
        toRemove.push(i);
        score_rest += scoreMatch(pending[i]);
        if (score_rest > score_m) { return false; }
    }

    return toRemove;
};

/*  called with all the matches, including the common start and common end, if they exist...

    A: Common start (should not be replaced)
    B: potential operations
    B': satisfactory set of operations
    C: Common end (should not be replaced)

    this implementation does not do anything special to protect A and C
    it is believed that the way matches are produced, they should not be removed.
*/
var reduceMatches = function (matches) {
    // ascending sort
    matches.sort(function (a, b) { return (a.oldIndex + a.newIndex) - (b.oldIndex + b.newIndex); });
    var out = [];

    var l_m = matches.length;
    var toRemove;
    for (var i = 0; i < l_m; i++) {
        toRemove = listInferiorCandidates(matches[i], out);
        if (toRemove) {
            removeDescendingIndices(out, toRemove);
            out.push(matches[i]);
        }
    }
    return out;
};

var resolve = function (str, hash, blockSize) {
    var matches = [];
    var candidates = [];
    // do the same thing as was done in hashscan, but for the new string
    // look for commonalities between new and old data
    for (var i = 0; i + blockSize <= str.length; i++) {
        var slice = str.slice(i, i + blockSize);
        var instances = (hash[slice] || []).slice(0);
        for (var j = candidates.length - 1; j >= 0; j--) {
            var c = candidates[j];
{'fraction_non_alphanumeric': 0.1089599279603782, 'fraction_numerical': 0.00810445745159838, 'mean_word_length': 2.7680237489397794, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, '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': '2678930', 'n_tokens_mistral': 2642, 'n_tokens_neox': 2581, 'n_words': 1043}