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
21 namespace spvtools {
22 namespace diff {
23 namespace {
24
25 using Sequence = std::vector<int>;
26 using LCS = LongestCommonSubsequence<Sequence>;
27
VerifyMatch(const Sequence & src,const Sequence & dst,size_t expected_match_count)28 void 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
TEST(LCSTest,EmptySequences)62 TEST(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
TEST(LCSTest,EmptySrc)76 TEST(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
TEST(LCSTest,EmptyDst)90 TEST(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
TEST(LCSTest,Identical)104 TEST(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
TEST(LCSTest,SrcPrefix)118 TEST(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
TEST(LCSTest,DstPrefix)135 TEST(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
TEST(LCSTest,SrcSuffix)152 TEST(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
TEST(LCSTest,DstSuffix)169 TEST(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
TEST(LCSTest,None)186 TEST(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
TEST(LCSTest,NonContiguous)200 TEST(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
TEST(LCSTest,WithDuplicates)217 TEST(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
TEST(LCSTest,Large)223 TEST(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