Function PredictReplacementSize

source/util.cpp:1296–1409

size_t PredictReplacementSize(ptrdiff_t aLengthDelta, int aReplacementCount, int aLimit, size_t aHaystackLength
	, size_t aCurrentLength, size_t aEndOffsetOfCurrMatch)
// Predict how much size the remainder of a replacement operation will consume, including its actual replacements
// and the parts of haystack that won't need replacement.
// PARAMETERS:
// - aLengthDelta: The estimated or actual difference between the length of the replacement and what it's replacing.
//   A negative number means the replacement is smaller, which will cause a shrinking of the result.
// - aReplacementCount: The number of replacements so far, including the one the caller is about to do.
// - aLimit: The *remaining* number of replacements *allowed* (not including the one the caller is about to do).
// - aHaystackLength: The total length of the original haystack/subject string.
// - aCurrentLength: The total length of the new/result string including the one the caller is about to do.
// - aEndOffsetOfCurrMatch: The offset of the char after the last char of the current match.  For example, if
//   the empty string is the current match and it's found at the beginning of haystack, this value would be 0.
{
	// Since realloc() is an expensive operation, especially for huge strings, make an extra
	// effort to get a good estimate based on how things have been going so far.
	// While this should definitely improve average-case memory-utilization and usually performance
	// (by avoiding costly realloc's), this estimate is crude because:
	// 1) The length of what is being replaced can vary due to wildcards in pattern, etc.
	// 2) The length of what is replacing it can vary due to backreferences.  Thus, the delta
	//    of each replacement is only a guess based on that of the current replacement.
	// 3) For code simplicity, the number of upcoming replacements isn't yet known; thus a guess
	//    is made based on how many there have been so far compared to percentage complete.

	INT_PTR total_delta; // The total increase/decrease in length from the number of predicted additional replacements.
	int repl_multiplier = aLengthDelta < 0 ? -1 : 1; // Negative is used to keep additional_replacements_expected conservative even when delta is negative.

	if (aLengthDelta == 0) // Avoid all the calculations because it will wind up being zero anyway.
		total_delta = 0;
	else
	{
		if (!aHaystackLength // aHaystackLength can be 0 if an empty haystack being replaced by something else. If so, avoid divide-by-zero in the prediction by doing something simpler.
			|| !aEndOffsetOfCurrMatch)  // i.e. don't the prediction if the current match is the empty string and it was found at the very beginning of Haystack because it would be difficult to be accurate (very rare anyway).
			total_delta = repl_multiplier * aLengthDelta; // Due to rarity, just allow room for one extra after the one we're about to do.
		else // So the above has ensured that the following won't divide by zero anywhere.
		{
			// The following doesn't take into account the original value of aStartingOffset passed in
			// from the caller because:
			// 1) It's pretty rare for it to be greater than 0.
			// 2) Even if it is, the prediction will just be too conservative at first, but that's
			//    pretty harmless; and anyway each successive realloc followed by a match makes the
			//    prediction more and more accurate in spite of aStartingOffset>0.
			// percent_complete must be a double because we need at least 9 digits of precision for cases where
			// 1 is divided by a big number like 1 GB.
			double percent_complete = aEndOffsetOfCurrMatch  // Don't subtract 1 (verified correct).
				/ (double)aHaystackLength; // percent_complete isn't actually a percentage, but a fraction of 1.  e.g. 0.5 rather than 50.
			int additional_replacements_expected = percent_complete >= 1.0 ? 0  // It's often 100% complete, in which case there's hardly ever another replacement after this one (the only possibility is to replace the final empty-string in haystack with something).
				: (int)(
				(aReplacementCount / percent_complete) // This is basically "replacements per percentage point, so far".
				* (1 - percent_complete) // This is the percentage of haystack remaining to be scanned (e.g. 0.5 for 50%).
				+ 1 * repl_multiplier // Add 1 or -1 to make it more conservative (i.e. go the opposite direction of ceil when repl_multiplier is negative).
				);
			// additional_replacements_expected is defined as the replacements expected *after* the one the caller
			// is about to do.

			if (aLimit >= 0 && aLimit < additional_replacements_expected)
			{	// A limit is currently in effect and it's less than expected replacements, so cap the expected.
				// This helps reduce memory utilization.