data/LineDiff.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "LineDiff.h" | ||
| 2 | |||
| 3 | #include <algorithm> | ||
| 4 | #include <vector> | ||
| 5 | |||
| 6 | namespace LineDiff { | ||
| 7 | |||
| 8 | namespace { | ||
| 9 | |||
| 10 | // Longest common subsequence of two line lists; the kept index pairs. | ||
| 11 | 1507 | QList<QPair<int, int>> lcsPairs(const QStringList &a, const QStringList &b) { | |
| 12 | 1507 | const int n = int(a.size()); | |
| 13 | 1507 | const int m = int(b.size()); | |
| 14 |
2/2✓ Branch 8 → 9 taken 1507 times.
✓ Branch 9 → 10 taken 1507 times.
|
1507 | std::vector<std::vector<int>> table(size_t(n) + 1, std::vector<int>(size_t(m) + 1, 0)); |
| 15 |
2/2✓ Branch 33 → 14 taken 16903 times.
✓ Branch 33 → 34 taken 1507 times.
|
18410 | for (int i = n - 1; i >= 0; --i) |
| 16 |
2/2✓ Branch 31 → 15 taken 11201139 times.
✓ Branch 31 → 32 taken 16903 times.
|
11218042 | for (int j = m - 1; j >= 0; --j) |
| 17 |
2/2✓ Branch 18 → 19 taken 16335 times.
✓ Branch 18 → 22 taken 11184804 times.
|
22385943 | table[size_t(i)][size_t(j)] = a.at(i) == b.at(j) ? table[size_t(i) + 1][size_t(j) + 1] + 1 |
| 18 | 11184804 | : std::max(table[size_t(i) + 1][size_t(j)], table[size_t(i)][size_t(j) + 1]); | |
| 19 | 1507 | QList<QPair<int, int>> kept; | |
| 20 | 1507 | int i = 0, j = 0; | |
| 21 |
4/4✓ Branch 49 → 50 taken 17155 times.
✓ Branch 49 → 51 taken 1347 times.
✓ Branch 50 → 35 taken 16995 times.
✓ Branch 50 → 51 taken 160 times.
|
18502 | while (i < n && j < m) { |
| 22 |
2/2✓ Branch 38 → 39 taken 15704 times.
✓ Branch 38 → 42 taken 1291 times.
|
16995 | if (a.at(i) == b.at(j)) { |
| 23 |
1/1✓ Branch 40 → 41 taken 15704 times.
|
15704 | kept.append({i, j}); |
| 24 | 15704 | ++i; | |
| 25 | 15704 | ++j; | |
| 26 |
2/2✓ Branch 46 → 47 taken 993 times.
✓ Branch 46 → 48 taken 298 times.
|
1291 | } else if (table[size_t(i) + 1][size_t(j)] >= table[size_t(i)][size_t(j) + 1]) { |
| 27 | 993 | ++i; | |
| 28 | } else { | ||
| 29 | 298 | ++j; | |
| 30 | } | ||
| 31 | } | ||
| 32 | 1507 | return kept; | |
| 33 | 1507 | } | |
| 34 | |||
| 35 | } // namespace | ||
| 36 | |||
| 37 | 20041 | QStringList splitLines(const QByteArray &bytes) { | |
| 38 |
1/1✓ Branch 2 → 3 taken 20041 times.
|
20041 | QString text = QString::fromUtf8(bytes); |
| 39 |
1/1✓ Branch 9 → 10 taken 20041 times.
|
40082 | text.replace(QStringLiteral("\r\n"), QStringLiteral("\n")); |
| 40 |
3/3✓ Branch 16 → 17 taken 20041 times.
✓ Branch 17 → 18 taken 20026 times.
✓ Branch 17 → 19 taken 15 times.
|
20041 | if (text.endsWith(QLatin1Char('\n'))) |
| 41 |
1/1✓ Branch 18 → 19 taken 20026 times.
|
20026 | text.chop(1); |
| 42 |
3/3✓ Branch 20 → 21 taken 9 times.
✓ Branch 20 → 22 taken 20032 times.
✓ Branch 25 → 26 taken 20032 times.
|
60114 | return text.isEmpty() ? QStringList{} : text.split(QLatin1Char('\n')); |
| 43 | 20041 | } | |
| 44 | |||
| 45 | 1509 | QList<int> match(const QStringList &a, const QStringList &b) { | |
| 46 |
1/1✓ Branch 3 → 4 taken 1509 times.
|
1509 | QList<int> result(a.size(), -1); |
| 47 | 1509 | int prefix = 0; | |
| 48 |
8/8✓ Branch 8 → 9 taken 12745 times.
✓ Branch 8 → 16 taken 518 times.
✓ Branch 10 → 11 taken 12716 times.
✓ Branch 10 → 16 taken 29 times.
✓ Branch 14 → 15 taken 11754 times.
✓ Branch 14 → 16 taken 962 times.
✓ Branch 17 → 5 taken 11754 times.
✓ Branch 17 → 18 taken 1509 times.
|
13263 | while (prefix < a.size() && prefix < b.size() && a.at(prefix) == b.at(prefix)) { |
| 49 |
1/1✓ Branch 5 → 6 taken 11754 times.
|
11754 | result[prefix] = prefix; |
| 50 | 11754 | ++prefix; | |
| 51 | } | ||
| 52 | 1509 | int suffix = 0; | |
| 53 |
8/8✓ Branch 24 → 25 taken 20487 times.
✓ Branch 24 → 34 taken 654 times.
✓ Branch 26 → 27 taken 20391 times.
✓ Branch 26 → 34 taken 96 times.
✓ Branch 32 → 33 taken 19632 times.
✓ Branch 32 → 34 taken 759 times.
✓ Branch 35 → 19 taken 19632 times.
✓ Branch 35 → 36 taken 1509 times.
|
41532 | while (suffix < a.size() - prefix && suffix < b.size() - prefix && |
| 54 | 20391 | a.at(a.size() - 1 - suffix) == b.at(b.size() - 1 - suffix)) { | |
| 55 |
1/1✓ Branch 21 → 22 taken 19632 times.
|
19632 | result[a.size() - 1 - suffix] = int(b.size() - 1 - suffix); |
| 56 | 19632 | ++suffix; | |
| 57 | } | ||
| 58 |
1/1✓ Branch 37 → 38 taken 1509 times.
|
1509 | const QStringList middleA = a.mid(prefix, a.size() - prefix - suffix); |
| 59 |
1/1✓ Branch 39 → 40 taken 1509 times.
|
1509 | const QStringList middleB = b.mid(prefix, b.size() - prefix - suffix); |
| 60 |
5/6✓ Branch 41 → 42 taken 1507 times.
✓ Branch 41 → 44 taken 2 times.
✗ Branch 43 → 44 not taken.
✓ Branch 43 → 45 taken 1507 times.
✓ Branch 46 → 47 taken 2 times.
✓ Branch 46 → 48 taken 1507 times.
|
1509 | if (middleA.size() > kExactLineLimit || middleB.size() > kExactLineLimit) |
| 61 | 2 | return result; | |
| 62 | // The kept lines of `before` pair with the earliest equal line of | ||
| 63 | // `after` (the pairing SieveBlockDiff always used; any common | ||
| 64 | // subsequence embeds greedily). | ||
| 65 | 1507 | int j = 0; | |
| 66 |
5/5✓ Branch 48 → 49 taken 1507 times.
✓ Branch 49 → 50 taken 1507 times.
✓ Branch 50 → 51 taken 1507 times.
✓ Branch 62 → 52 taken 15704 times.
✓ Branch 62 → 63 taken 1507 times.
|
17211 | for (const auto &pair : lcsPairs(middleA, middleB)) { |
| 67 |
2/2✓ Branch 58 → 54 taken 298 times.
✓ Branch 58 → 59 taken 15704 times.
|
16002 | while (middleB.at(j) != middleA.at(pair.first)) |
| 68 | 298 | ++j; | |
| 69 |
1/1✓ Branch 59 → 60 taken 15704 times.
|
15704 | result[prefix + pair.first] = prefix + j; |
| 70 | 15704 | ++j; | |
| 71 | 1507 | } | |
| 72 | 1507 | return result; | |
| 73 | 1509 | } | |
| 74 | |||
| 75 | 18 | QList<Line> diff(const QStringList &a, const QStringList &b) { | |
| 76 |
1/1✓ Branch 2 → 3 taken 18 times.
|
18 | const QList<int> matched = match(a, b); |
| 77 | 18 | QList<Line> result; | |
| 78 | 18 | int j = 0; | |
| 79 |
2/2✓ Branch 26 → 4 taken 138 times.
✓ Branch 26 → 27 taken 18 times.
|
156 | for (int i = 0; i < a.size(); ++i) { |
| 80 |
2/2✓ Branch 5 → 6 taken 27 times.
✓ Branch 5 → 11 taken 111 times.
|
138 | if (matched.at(i) < 0) { |
| 81 |
1/1✓ Branch 8 → 9 taken 27 times.
|
27 | result.append({Line::Op::Removed, a.at(i)}); |
| 82 | 27 | continue; | |
| 83 | } | ||
| 84 |
2/2✓ Branch 18 → 12 taken 6 times.
✓ Branch 18 → 19 taken 111 times.
|
117 | while (j < matched.at(i)) |
| 85 |
1/1✓ Branch 14 → 15 taken 6 times.
|
6 | result.append({Line::Op::Added, b.at(j++)}); |
| 86 |
1/1✓ Branch 21 → 22 taken 111 times.
|
111 | result.append({Line::Op::Same, a.at(i)}); |
| 87 | 111 | ++j; | |
| 88 | } | ||
| 89 |
2/2✓ Branch 34 → 28 taken 18 times.
✓ Branch 34 → 35 taken 18 times.
|
36 | while (j < b.size()) |
| 90 |
1/1✓ Branch 30 → 31 taken 18 times.
|
18 | result.append({Line::Op::Added, b.at(j++)}); |
| 91 | 18 | return result; | |
| 92 | 180 | } | |
| 93 | |||
| 94 | } // namespace LineDiff | ||
| 95 |