1// Copyright (c) 2022 Google LLC.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#include "source/diff/lcs.h"
16
17#include <string>
18
19#include "gtest/gtest.h"
20
21namespace spvtools {
22namespace diff {
23namespace {
24
25using Sequence = std::vector<int>;
26using LCS = LongestCommonSubsequence<Sequence>;
27
28void VerifyMatch(const Sequence& src, const Sequence& dst,
29                 size_t expected_match_count) {
30  DiffMatch src_match, dst_match;
31
32  LCS lcs(src, dst);
33  size_t match_count =
34      lcs.Get<int>([](int s, int d) { return s == d; }, &src_match, &dst_match);
35
36  EXPECT_EQ(match_count, expected_match_count);
37
38  size_t src_cur = 0;
39  size_t dst_cur = 0;
40  size_t matches_seen = 0;
41
42  while (src_cur < src.size() && dst_cur < dst.size()) {
43    if (src_match[src_cur] && dst_match[dst_cur]) {
44      EXPECT_EQ(src[src_cur], dst[dst_cur])
45          << "Src: " << src_cur << " Dst: " << dst_cur;
46      ++src_cur;
47      ++dst_cur;
48      ++matches_seen;
49      continue;
50    }
51    if (!src_match[src_cur]) {
52      ++src_cur;
53    }
54    if (!dst_match[dst_cur]) {
55      ++dst_cur;
56    }
57  }
58
59  EXPECT_EQ(matches_seen, expected_match_count);
60}
61
62TEST(LCSTest, EmptySequences) {
63  Sequence src, dst;
64
65  DiffMatch src_match, dst_match;
66
67  LCS lcs(src, dst);
68  size_t match_count =
69      lcs.Get<int>([](int s, int d) { return s == d; }, &src_match, &dst_match);
70
71  EXPECT_EQ(match_count, 0u);
72  EXPECT_TRUE(src_match.empty());
73  EXPECT_TRUE(dst_match.empty());
74}
75
76TEST(LCSTest, EmptySrc) {
77  Sequence src, dst = {1, 2, 3};
78
79  DiffMatch src_match, dst_match;
80
81  LCS lcs(src, dst);
82  size_t match_count =
83      lcs.Get<int>([](int s, int d) { return s == d; }, &src_match, &dst_match);
84
85  EXPECT_EQ(match_count, 0u);
86  EXPECT_TRUE(src_match.empty());
87  EXPECT_EQ(dst_match, DiffMatch(3, false));
88}
89
90TEST(LCSTest, EmptyDst) {
91  Sequence src = {1, 2, 3}, dst;
92
93  DiffMatch src_match, dst_match;
94
95  LCS lcs(src, dst);
96  size_t match_count =
97      lcs.Get<int>([](int s, int d) { return s == d; }, &src_match, &dst_match);
98
99  EXPECT_EQ(match_count, 0u);
100  EXPECT_EQ(src_match, DiffMatch(3, false));
101  EXPECT_TRUE(dst_match.empty());
102}
103
104TEST(LCSTest, Identical) {
105  Sequence src = {1, 2, 3, 4, 5, 6}, dst = {1, 2, 3, 4, 5, 6};
106
107  DiffMatch src_match, dst_match;
108
109  LCS lcs(src, dst);
110  size_t match_count =
111      lcs.Get<int>([](int s, int d) { return s == d; }, &src_match, &dst_match);
112
113  EXPECT_EQ(match_count, 6u);
114  EXPECT_EQ(src_match, DiffMatch(6, true));
115  EXPECT_EQ(dst_match, DiffMatch(6, true));
116}
117
118TEST(LCSTest, SrcPrefix) {
119  Sequence src = {1, 2, 3, 4}, dst = {1, 2, 3, 4, 5, 6};
120
121  DiffMatch src_match, dst_match;
122
123  LCS lcs(src, dst);
124  size_t match_count =
125      lcs.Get<int>([](int s, int d) { return s == d; }, &src_match, &dst_match);
126
127  const DiffMatch src_expect = {true, true, true, true};
128  const DiffMatch dst_expect = {true, true, true, true, false, false};
129
130  EXPECT_EQ(match_count, 4u);
131  EXPECT_EQ(src_match, src_expect);
132  EXPECT_EQ(dst_match, dst_expect);
133}
134
135TEST(LCSTest, DstPrefix) {
136  Sequence src = {1, 2, 3, 4, 5, 6}, dst = {1, 2, 3, 4, 5};
137
138  DiffMatch src_match, dst_match;
139
140  LCS lcs(src, dst);
141  size_t match_count =
142      lcs.Get<int>([](int s, int d) { return s == d; }, &src_match, &dst_match);
143
144  const DiffMatch src_expect = {true, true, true, true, true, false};
145  const DiffMatch dst_expect = {true, true, true, true, true};
146
147  EXPECT_EQ(match_count, 5u);
148  EXPECT_EQ(src_match, src_expect);
149  EXPECT_EQ(dst_match, dst_expect);
150}
151
152TEST(LCSTest, SrcSuffix) {
153  Sequence src = {3, 4, 5, 6}, dst = {1, 2, 3, 4, 5, 6};
154
155  DiffMatch src_match, dst_match;
156
157  LCS lcs(src, dst);
158  size_t match_count =
159      lcs.Get<int>([](int s, int d) { return s == d; }, &src_match, &dst_match);
160
161  const DiffMatch src_expect = {true, true, true, true};
162  const DiffMatch dst_expect = {false, false, true, true, true, true};
163
164  EXPECT_EQ(match_count, 4u);
165  EXPECT_EQ(src_match, src_expect);
166  EXPECT_EQ(dst_match, dst_expect);
167}
168
169TEST(LCSTest, DstSuffix) {
170  Sequence src = {1, 2, 3, 4, 5, 6}, dst = {5, 6};
171
172  DiffMatch src_match, dst_match;
173
174  LCS lcs(src, dst);
175  size_t match_count =
176      lcs.Get<int>([](int s, int d) { return s == d; }, &src_match, &dst_match);
177
178  const DiffMatch src_expect = {false, false, false, false, true, true};
179  const DiffMatch dst_expect = {true, true};
180
181  EXPECT_EQ(match_count, 2u);
182  EXPECT_EQ(src_match, src_expect);
183  EXPECT_EQ(dst_match, dst_expect);
184}
185
186TEST(LCSTest, None) {
187  Sequence src = {1, 3, 5, 7, 9}, dst = {2, 4, 6, 8, 10, 12};
188
189  DiffMatch src_match, dst_match;
190
191  LCS lcs(src, dst);
192  size_t match_count =
193      lcs.Get<int>([](int s, int d) { return s == d; }, &src_match, &dst_match);
194
195  EXPECT_EQ(match_count, 0u);
196  EXPECT_EQ(src_match, DiffMatch(5, false));
197  EXPECT_EQ(dst_match, DiffMatch(6, false));
198}
199
200TEST(LCSTest, NonContiguous) {
201  Sequence src = {1, 2, 3, 4, 5, 6, 10}, dst = {2, 4, 5, 8, 9, 10, 12};
202
203  DiffMatch src_match, dst_match;
204
205  LCS lcs(src, dst);
206  size_t match_count =
207      lcs.Get<int>([](int s, int d) { return s == d; }, &src_match, &dst_match);
208
209  const DiffMatch src_expect = {false, true, false, true, true, false, true};
210  const DiffMatch dst_expect = {true, true, true, false, false, true, false};
211
212  EXPECT_EQ(match_count, 4u);
213  EXPECT_EQ(src_match, src_expect);
214  EXPECT_EQ(dst_match, dst_expect);
215}
216
217TEST(LCSTest, WithDuplicates) {
218  Sequence src = {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4},
219           dst = {1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4};
220  VerifyMatch(src, dst, 6);
221}
222
223TEST(LCSTest, Large) {
224  const std::string src_str =
225      "GUJwrJSlkKJXxCVIAxlVgnUyOrdyRyFtlZwWMmFhYGfkFTNnhiBmClgHyrcXMVwfrRxNUfQk"
226      "qaoGvCbPZHAzXsaZpXHPfJxOMCUtRDmIQpfiXKbHQbhTfPqhxBDWvmTQAqwsWTLajZYtMUnf"
227      "hNNCfkuAXkZsaebwEbIZOxTDZsqSMUfCMoGeKJGVSNFgLTiBMbdvchHGfFRkHKcYCDjBfIcj"
228      "todPnvDjzQYWBcvIfVvyBzHikrwpDORaGEZLhmyztIFCLJOqeLhOzERYmVqzlsoUzruTXTXq"
229      "DLTxQRakOCMRrgRzCDTXfwwfDcKMBVnxRZemjcwcEsOVxwtwdBCWJycsDcZKlvrCvZaenKlv"
230      "vyByDQeLdxAyBnPkIMQlMQwqjUfRLybeoaOanlbFkpTPPZdHelQrIvucTHzMpWWQTbuANwvN"
231      "OVhCGGoIcGNDpfIsaBexlMMdHsxMGerTngmjpdPeQQJHfvKZkdYqAzrtDohqtDsaFMxQViVQ"
232      "YszDVgyoSHZdOXAvXkJidojLvGZOzhRajVPhWDwKuGqdaympELxHsrXAJYufdCPwJdGJfWqq"
233      "yvTWpcrFHOIuCEmNLnSCDsxQGRVDwyCykBJazhApfCnrOadnafvqfVuFqEXMSrYbHTfTnzbz"
234      "MhISyOtMUITaurCXvanCbuOXBhHyCjOhVbxnMvhlPmZBMQgEHCghtAJVMXGPNRtszVZlPxVl"
235      "QIPTBnPUPejlyZGPqeICyNngdQGkvKbIoWlTLBtVhMdBeUMozNlKQTIPYBeImVcMdLafuxUf"
236      "TIXysmcTrUTcspOSKBxhdhLwiRnREGFWJTfUKsgGOAQeYojXdrqsGjMJfiKalyoiqrgLnlij"
237      "CtOapoxDGVOOBalNYGzCtBlxbvaAzxipGnJpOEbmXcpeoIsAdxspKBzBDgoPVxnuRBUwmTSr"
238      "CRpWhxikgUYQVCwalLUIeBPRyhhsECGCXJmGDZSCIUaBwROkigzdeVPOXhgCGBEprWtNdYfL"
239      "tOUYJHQXxiIJgSGmWntezJFpNQoTPbRRYAGhtYvAechvBcYWocLkYFxsDAuszvQNLXdhmAHw"
240      "DErcjbtCdQllnKcDADVNWVezljjLrAuyGHetINMgAvJZwOEYakihYVUbZGCsHEufluLNyNHy"
241      "gqtSTSFFjBHiIqQejTPWybLdpWNwZrWvIWnlzUcGNQPEYHVPCbteWknjAnWrdTBeCbHUDBoK"
242      "aHvDStmpNRGIjvlumiZTbdZNAzUeSFnFChCsSExwXeEfDJfjyOoSBofHzJqJErvHLNyUJTjX"
243      "qmtgKPpMKohUPBMhtCteQFcNEpWrUVGbibMOpvBwdiWYXNissArpSasVJFgDzrqTyGkerTMX"
244      "gcrzFUGFZRhNdekaJeKYPogsofJaRsUQmIRyYdkrxKeMgLPpwOfSKJOqzXDoeHljTzhOwEVy"
245      "krOEnACFrWhufajsMitjOWdLOHHchQDddGPzxknEgdwmZepKDvRZGCuPqzeQkjOPqUBKpKLJ"
246      "eKieSsRXkaqxSPGajfvPKmwFWdLByEcLgvrmteazgFjmMGrLYqRRxzUOfOCokenqHVYstBHf"
247      "AwsWsqPTvqsRJUfGGTaYiylZMGbQqTzINhFHvdlRQvvYKBcuAHdBeKlHSxVrSsEKbcAvnIcf"
248      "xzdVDdwQPHMCHeZZRpGHWvKzgTGzSTbYTeOPyKvvYWmQToTpsjAtKUJUjcEHWhmdBLDTBMHJ"
249      "ivBXcLGtCsumNNVFyGbVviGmqHTdyBlkneibXBesKJGOUzOtIwXCPJggqBekSzNQYkALlItk"
250      "cbEhbdXAIKVHYpInLwxXalKZrkrpxtfuagqMGmRJnJbFQaEoYMoqPsxZpocddPXXPyvxVkaF"
251      "qdKISejWDhBImnEEOPDcyWTubbfVfwUztciaFJcsPLhgYVfhqlOfoNjKbmTFptFttYuyBrUI"
252      "zzmZypOqrjQHTGFwlHStpIwxPtMvtsEDpsmWIgwzYgwmdpbMOnfElZMYpVIcvzSWejeJcdUB"
253      "QUoBRUmGQVVWvEDseuozrDjgdXFScPwwsgaUPwSzScfBNrkpmEFDSZLKfNjMqvOmUtocUkbo"
254      "VGFEKgGLbNruwLgXHTloWDrnqymPVAtzjWPutonIsMDPeeCmTjYWAFXcyTAlBeiJTIRkZxiM"
255      "kLjMnAflSNJzmZkatXkYiPEMYSmzHbLKEizHbEjQOxBDzpRHiFjhedqiyMiUMvThjaRFmwll"
256      "aMGgwKBIKepwyoEdnuhtzJzboiNEAFKiqiWxxmkRFRoTiFWXLPAWLuzSCrajgkQhDxAQDqyM"
257      "VwZlhZicQLEDYYisEalesDWZAYzcvENuHUwRutIsGgsdoYwOZiURhcgdbTGWBNqhrFjvTQCj"
258      "VlTPNlRdRLaaqzUBBwbdtyXFkCBUYYMbmRrkFxfxbCqkgZNGyHPKLkOPnezfVTRmRQgCgHbx"
259      "wcZlInVOwmFePnSIbThMJosimzkhfuiqYEpwHQiemqsSDNNdbNhBLzbsPZBJZujSHJGtYKGb"
260      "HaAYGJZxBumsKUrATwPuqXFLfwNyImLQbchBKiJAYRZhkcrKCHXBEGYyBhBGvSqvabcRUrfq"
261      "AbPiMzjHAehGYjDEmxAnYLyoSFdeWVrfJUCuYZPluhXEBuyUpKaRXDKXeiCvGidpvATwMbcz"
262      "DZpzxrhTZYyrFORFQWTbPLCBjMKMhlRMFEiarDgGPttjmkrQVlujztMSkxXffXFNqLWOLThI"
263      "KBoyMHoFTEPCdUAZjLTifAdjjUehyDLEGKlRTFoLpjalziRSUjZfRYbNzhiHgTHowMMkKTwE"
264      "ZgnqiirMtnNpaBJqhcIVrWXPpcPWZfRpsPstHleFJDZYAsxYhOREVbFtebXTZRAIjGgWeoiN"
265      "qPLCCAVadqmUrjOcqIbdCTpcDRWuDVbHrZOQRPhqbyvOWwxAWJphjLiDgoAybcjzgfVktPlj"
266      "kNBCjelpuQfnYsiTgPpCNKYtOrxGaLEEtAuLdGdDsONHNhSn";
267  const std::string dst_str =
268      "KzitfifORCbGhfNEbnbObUdFLLaAsLOpMkOeKupjCoatzqfHBkNJfSgqSMYouswfNMnoQngK"
269      "jWwyPKmEnoZWyPBUdQRmKUNudUclueKXKQefUdXWUyyqtumzsFKznrLVLwfvPZpLChNYrrHK"
270      "AtpfOuVHiUKyeRCrktJAhkyFKmPWrASEMvBLNOzuGlvinZjvZUUXazNEkyMPiOLdqXvCIroC"
271      "MeWsvjHShlLhDwLZrVlpYBnDJmILcsNFDSoaLWOKNNkNGBgNBvVjPCJXAuKfsrKZhYcdEpxK"
272      "UihiRkYvMiLyOUvaqBMklLDwEhvQBfCXHSRoqsLsSCzLZQhIYMhBapvHaPbDoRrHoJXZsNXc"
273      "rxZYCrOMIzYcVPwDCFiHBFnPNTTeAeKEMGeVUeCaAeuWZmngyPWlQBcgWumSUIfbhjVYdnpV"
274      "hRSJXrIoFZubBXfNOMhilAkVPixrhILZKgDoFTvytPFPfBLMnbhSOBmLWCbJsLQxrCrMAlOw"
275      "RmfSQyGhrjhzYVqFSBHeoQBagFwyxIjcHFZngntpVHbSwqhwHeMnWSsISPljTxSNXfCxLebW"
276      "GhMdlphtJbdvhEcjNpwPCFqhdquxCyOxkjsDUPNgjpDcpIMhMwMclNhfESTrroJaoyeGQclV"
277      "gonnhuQRmXcBwcsWeLqjNngZOlyMyfeQBwnwMVJEvGqknDyzSApniRTPgJpFoDkJJhXQFuFB"
278      "VqhuEPMRGCeTDOSEFmXeIHOnDxaJacvnmORwVpmrRhGjDpUCkuODNPdZMdupYExDEDnDLdNF"
279      "iObKBaVWpGVMKdgNLgsNxcpypBPPKKoaajeSGPZQJWSOKrkLjiFexYVmUGxJnbTNsCXXLfZp"
280      "jfxQAEVYvqKehBzMsVHVGWmTshWFAoCNDkNppzzjHBZWckrzSTANICioCJSpLwPwQvtXVxst"
281      "nTRBAboPFREEUFazibpFesCsjzUOnECwoPCOFiwGORlIZVLpUkJyhYXCENmzTBLVigOFuCWO"
282      "IiXBYmiMtsxnUdoqSTTGyEFFrQsNAjcDdOKDtHwlANWoUVwiJCMCQFILdGqzEePuSXFbOEOz"
283      "dLlEnTJbKRSTfAFToOZNtDXTfFgvQiefAKbSUWUXFcpCjRYCBNXCCcLMjjuUDXErpiNsRuIx"
284      "mgHsrObTEXcnmjdqxTGhTjTeYizNnkrJRhNQIqDXmZMwArBccnixpcuiGOOexjgkpcEyGAnz"
285      "UbgiBfflTUyJfZeFFLrZVueFkSRosebnnwAnakIrywTGByhQKWvmNQJsWQezqLhHQzXnEpeD"
286      "rFRTSQSpVxPzSeEzfWYzfpcenxsUyzOMLxhNEhfcuprDtqubsXehuqKqZlLQeSclvoGjuKJK"
287      "XoWrazsgjXXnkWHdqFESZdMGDYldyYdbpSZcgBPgEKLWZHfBirNPLUadmajYkiEzmGuWGELB"
288      "WLiSrMdaGSbptKmgYVqMGcQaaATStiZYteGAPxSEBHuAzzjlRHYsrdDkaGNXmzRGoalJMiCC"
289      "GMtWSDMhgvRSEgKnywbRgnqWXFlwrhXbbvcgLGtWSuKQBiqIlWkfPMozOTWgVoLHavDJGRYI"
290      "YerrmZnTMtuuxmZALWakfzUbksTwoetqkOiRPGqGZepcVXHoZyOaaaijjZWQLlIhYwiQNbfc"
291      "KCwhhFaMQBoaCnOecJEdKzdsMPFEYQuJNPYiiNtsYxaWBRuWjlLqGokHMNtyTQfSJKbgGdol"
292      "fWlOZdupouQMfUWXIYHzyJHefMDnqxxasDxtgArvDqtwjDBaVEMACPkLFpiDOoKCHqkWVizh"
293      "lKqbOHpsPKkhjRQRNGYRYEfxtBjYvlCvHBNUwVuIwDJYMqHxEFtwdLqYWvjdOfQmNiviDfUq"
294      "pbucbNwjNQfMYgwUuPnQWIPOlqHcbjtuDXvTzLtkdBQanJbrmLSyFqSapZCSPMDOrxWVYzyO"
295      "lwDTTJFmKxoyfPunadkHcrcSQaQsAbrQtbhqwSTXGTPURYTCbNozjAVwbmcyVxIbZudBZWYm"
296      "rnSDyelGCRRWYtrUxvOVWlTLHHdYuAmVMGnGbHscbjmjmAzmYLaCxNNwhmMYdExKvySxuYpE"
297      "rVGwfqMngBCHnZodotNaNJZiNRFWubuPDfiywXPiyVWoQMeOlSuWmpilLTIFOvfpjmJTgrWa"
298      "dgoxYeyPyOaglOvZVGdFOBSeqEcGXBwjoeUAXqkpvOxEpSXhmklKZydTvRVYVvfQdRNNDkCT"
299      "dLNfcZCFQbZORdcDOhwotoyccrSbWvlqYMoiAYeEpDzZTvkamapzZMmCpEutZFCcHBWGIIkr"
300      "urwDNHrobaErPpclyEegLJDtkfUWSNWZosWSbBGAHIvJsFNUlJXbnkSVycLkOVQVcNcUtiBy"
301      "djLDIFsycbPBEWaMvCbntNtJlOeCttvXypGnHAQFnFSiXFWWqonWuVIKmVPpKXuJtFguXCWC"
302      "rNExYYvxLGEmuZJLJDjHgjlQyOzeieCpizJxkrdqKCgomyEkvsyVYSsLeyLvOZQrrgEJgRFK"
303      "CjYtoOfluNrLdRMTRkQXmAiMRFwloYECpXCReAMxOkNiwCtutsrqWoMHsrogRqPoUCueonvW"
304      "MTwmkAkajfGJkhnQidwpwIMEttQkzIMOPvvyWZHpqkMHWlNTeSKibfRfwDyxveKENZhtlPwP"
305      "dfAjwegjRcavtFnkkTNVYdCdCrgdUvzsIcqmUjwGmVvuuQvjVrWWIDBmAzQtiZPYvCOEWjce"
306      "rWzeqVKeiYTJBOedmQCVidOgUIEjfRnbGvUbctYxfRybJkdmeAkLZQMRMGPOnsPbFswXAoCK"
307      "IxWGwohoPpEJxslbqHFKSwknxTmrDCITRZWEDkGQeucPxHBdYkduwbYhKnoxCKhgjBFiFawC"
308      "QtgTDldTQmlOsBiGLquMjuecAbrUJJvNtXbFNGjWxaZPimSRXUJWgRbydpsczOqSFIeEtuKA"
309      "ZpRhmLtPdVNKdSDQZeeImUFmUwXApRTUNHItyvFyJtNtn";
310
311  Sequence src;
312  Sequence dst;
313
314  src.reserve(src_str.length());
315  dst.reserve(dst_str.length());
316
317  for (char c : src_str) {
318    src.push_back(c);
319  }
320  for (char c : dst_str) {
321    dst.push_back(c);
322  }
323
324  VerifyMatch(src, dst, 723);
325}
326
327}  // namespace
328}  // namespace diff
329}  // namespace spvtools
330