Page MenuHomePhabricator
Files F13958898

D9178.id.diff
No OneTemporary
Actions

D9178.id.diff
View Options

diff --git a/src/applications/differential/parser/DifferentialChangesetParser.php b/src/applications/differential/parser/DifferentialChangesetParser.php
--- a/src/applications/differential/parser/DifferentialChangesetParser.php
+++ b/src/applications/differential/parser/DifferentialChangesetParser.php
@@ -1176,6 +1176,16 @@
$added = array_map('trim', $hunk->getAddedLines());
for (reset($added); list($line, $code) = each($added); ) {
if (isset($map[$code])) { // We found a long matching line.
+
+ if (count($map[$code]) > 16) {
+ // If there are a large number of identical lines in this diff,
+ // don't try to figure out where this block came from: the
+ // analysis is O(N^2), since we need to compare every line
+ // against every other line. Even if we arrive at a result, it
+ // is unlikely to be meaningful. See T5041.
+ continue 2;
+ }
+
$best_length = 0;
foreach ($map[$code] as $val) { // Explore all candidates.
list($file, $orig_line) = $val;
diff --git a/src/applications/differential/storage/__tests__/DifferentialDiffTestCase.php b/src/applications/differential/storage/__tests__/DifferentialDiffTestCase.php
--- a/src/applications/differential/storage/__tests__/DifferentialDiffTestCase.php
+++ b/src/applications/differential/storage/__tests__/DifferentialDiffTestCase.php
@@ -15,4 +15,41 @@
ipull($copies, 1));
}
+ public function testDetectSlowCopiedCode() {
+ // This tests that the detector has a reasonable runtime when a diff
+ // contains a very large number of identical lines. See T5041.
+
+ $parser = new ArcanistDiffParser();
+
+ $line = str_repeat('x', 60);
+ $oline = '-'.$line."\n";
+ $nline = '+'.$line."\n";
+
+ $n = 1000;
+ $oblock = str_repeat($oline, $n);
+ $nblock = str_repeat($nline, $n);
+
+ $raw_diff = <<<EODIFF
+diff --git a/dst b/dst
+new file mode 100644
+index 0000000..1234567
+--- /dev/null
++++ b/dst
+@@ -0,0 +1,{$n} @@
+{$nblock}
+diff --git a/src b/src
+deleted file mode 100644
+index 123457..0000000
+--- a/src
++++ /dev/null
+@@ -1,{$n} +0,0 @@
+{$oblock}
+EODIFF;
+
+ $diff = DifferentialDiff::newFromRawChanges($parser->parseDiff($raw_diff));
+
+ $this->assertTrue(true);
+ }
+
+
}

File Metadata

Mime Type
text/plain
Expires
Oct 15 2024, 4:55 PM (5 w, 17 h ago)
Storage Engine
blob
Storage Format
Encrypted (AES-256-CBC)
Storage Handle
6713600
Default Alt Text
D9178.id.diff (2 KB)

Event Timeline

Phabricator · Built by Phacility