| 353 | */ |
| 354 | private: |
| 355 | static void diff_compute(string_t text1, string_t text2, bool checklines, clock_t deadline, Diffs& diffs) { |
| 356 | if (text1.empty()) { |
| 357 | // Just add some text (speedup). |
| 358 | diffs.push_back(Diff(INSERT, text2)); |
| 359 | return; |
| 360 | } |
| 361 | |
| 362 | if (text2.empty()) { |
| 363 | // Just delete some text (speedup). |
| 364 | diffs.push_back(Diff(DELETE, text1)); |
| 365 | return; |
| 366 | } |
| 367 | |
| 368 | { |
| 369 | const string_t& longtext = text1.length() > text2.length() ? text1 : text2; |
| 370 | const string_t& shorttext = text1.length() > text2.length() ? text2 : text1; |
| 371 | const size_t i = longtext.find(shorttext); |
| 372 | if (i != string_t::npos) { |
| 373 | // Shorter text is inside the longer text (speedup). |
| 374 | const Operation op = (text1.length() > text2.length()) ? DELETE : INSERT; |
| 375 | diffs.push_back(Diff(op, longtext.substr(0, i))); |
| 376 | diffs.push_back(Diff(EQUAL, shorttext)); |
| 377 | diffs.push_back(Diff(op, safeMid(longtext, i + shorttext.length()))); |
| 378 | return; |
| 379 | } |
| 380 | |
| 381 | if (shorttext.length() == 1) { |
| 382 | // Single character string. |
| 383 | // After the previous speedup, the character can't be an equality. |
| 384 | diffs.push_back(Diff(DELETE, text1)); |
| 385 | diffs.push_back(Diff(INSERT, text2)); |
| 386 | return; |
| 387 | } |
| 388 | // Garbage collect longtext and shorttext by scoping out. |
| 389 | } |
| 390 | |
| 391 | // Don't risk returning a non-optimal diff if we have unlimited time. |
| 392 | if (deadline != std::numeric_limits<clock_t>::max()) { |
| 393 | // Check to see if the problem can be split in two. |
| 394 | HalfMatchResult hm; |
| 395 | if (diff_halfMatch(text1, text2, hm)) { |
| 396 | // A half-match was found, sort out the return data. |
| 397 | // Send both pairs off for separate processing. |
| 398 | diff_main(hm.text1_a, hm.text2_a, checklines, deadline, diffs); |
| 399 | diffs.push_back(Diff(EQUAL, hm.mid_common)); |
| 400 | Diffs diffs_b; |
| 401 | diff_main(hm.text1_b, hm.text2_b, checklines, deadline, diffs_b); |
| 402 | diffs.splice(diffs.end(), diffs_b); |
| 403 | return; |
| 404 | } |
| 405 | } |
| 406 | |
| 407 | // Perform a real diff. |
| 408 | if (checklines && text1.length() > 100 && text2.length() > 100) { |
| 409 | diff_lineMode(text1, text2, deadline, diffs); |
| 410 | return; |
| 411 | } |
| 412 | |