2 * Runnable tests for the edit_distance module using custom costs/weights.
4 * @copyright 2016 Kevin Locke <kevin@kevinlocke.name>
5 * MIT license - see LICENSE file for details
10 #include <ccan/build_assert/build_assert.h>
11 #include <ccan/tap/tap.h>
13 #define ED_DEL_COST(e) (e == 'a' ? 2 : 1)
14 #define ED_INS_COST(e) (e == 'b' ? 2 : 1)
15 #define ED_SUB_COST(e, f) (f == 'c' && e == 'd' ? 3 : 1)
16 #define ED_TRA_COST(e, f) (e == 'e' && f == 'f' ? 3 : 1)
18 #include <ccan/edit_distance/edit_distance.c>
19 #include <ccan/edit_distance/edit_distance_dl.c>
20 #include <ccan/edit_distance/edit_distance_lcs.c>
21 #include <ccan/edit_distance/edit_distance_lev.c>
22 #include <ccan/edit_distance/edit_distance_rdl.c>
24 #define edit_distance_lcs_static(arr1, arr2) \
25 edit_distance(arr1, sizeof arr1 - 1, arr2, sizeof arr2 - 1, \
27 #define edit_distance_lev_static(arr1, arr2) \
28 edit_distance(arr1, sizeof arr1 - 1, arr2, sizeof arr2 - 1, \
30 #define edit_distance_rdl_static(arr1, arr2) \
31 edit_distance(arr1, sizeof arr1 - 1, arr2, sizeof arr2 - 1, \
33 #define edit_distance_dl_static(arr1, arr2) \
34 edit_distance(arr1, sizeof arr1 - 1, arr2, sizeof arr2 - 1, \
37 static void test_lcs(void)
40 ok1(edit_distance_lcs_static("", "") == 0);
41 ok1(edit_distance_lcs_static("a", "") == 2);
42 ok1(edit_distance_lcs_static("", "a") == 1);
43 ok1(edit_distance_lcs_static("a", "a") == 0);
44 ok1(edit_distance_lcs_static("a", "b") == 4);
45 ok1(edit_distance_lcs_static("b", "a") == 2);
47 /* Trivial search cases */
48 ok1(edit_distance_lcs_static("a", "bcdef") == 8);
49 ok1(edit_distance_lcs_static("a", "bcadef") == 6);
50 ok1(edit_distance_lcs_static("acdef", "b") == 8);
51 ok1(edit_distance_lcs_static("abcdef", "b") == 6);
53 /* Common prefix with single-char distance */
54 ok1(edit_distance_lcs_static("aa", "ab") == 4);
55 ok1(edit_distance_lcs_static("ab", "aa") == 2);
57 /* Common suffix with single-char distance */
58 ok1(edit_distance_lcs_static("aa", "ba") == 4);
59 ok1(edit_distance_lcs_static("ba", "aa") == 2);
61 /* Non-optimized cases (require Wagner-Fischer matrix) */
62 ok1(edit_distance_lcs_static("ab", "ba") == 3);
63 ok1(edit_distance_lcs_static("abc", "de") == 6);
64 ok1(edit_distance_lcs_static("abc", "def") == 7);
65 ok1(edit_distance_lcs_static("de", "bdef") == 3);
67 /* Transposition + Insert */
68 ok1(edit_distance_lcs_static("ca", "abc") == 4);
70 /* Insert + Delete + Sub */
71 ok1(edit_distance_lcs_static("abcde", "xcdef") == 5);
73 /* Distance depends on multiple deletions in final row. */
74 ok1(edit_distance_lcs_static("aabcc", "bccdd") == 6);
76 /* Distance depends on multiple insertions in final column. */
77 ok1(edit_distance_lcs_static("bccdd", "aabcc") == 4);
80 static void test_lev(void)
83 ok1(edit_distance_lev_static("", "") == 0);
84 ok1(edit_distance_lev_static("a", "") == 2);
85 ok1(edit_distance_lev_static("", "a") == 1);
86 ok1(edit_distance_lev_static("a", "a") == 0);
87 ok1(edit_distance_lev_static("a", "b") == 1);
88 ok1(edit_distance_lev_static("b", "a") == 1);
90 /* Trivial search cases */
91 ok1(edit_distance_lev_static("a", "bcdef") == 5);
92 ok1(edit_distance_lev_static("a", "bcadef") == 6);
93 ok1(edit_distance_lev_static("acdef", "b") == 5);
94 ok1(edit_distance_lev_static("abcdef", "b") == 6);
96 /* Common prefix with single-char distance */
97 ok1(edit_distance_lev_static("aa", "ab") == 1);
98 ok1(edit_distance_lev_static("ab", "aa") == 1);
100 /* Common suffix with single-char distance */
101 ok1(edit_distance_lev_static("aa", "ba") == 1);
102 ok1(edit_distance_lev_static("ba", "aa") == 1);
104 /* Non-optimized cases (require Wagner-Fischer matrix) */
105 ok1(edit_distance_lev_static("ab", "ba") == 2);
106 ok1(edit_distance_lev_static("abc", "de") == 3);
107 ok1(edit_distance_lev_static("abc", "def") == 3);
108 ok1(edit_distance_lev_static("de", "bdef") == 3);
110 /* Transposition + Insert */
111 ok1(edit_distance_lev_static("ca", "abc") == 3);
113 /* Insert + Delete + Sub */
114 ok1(edit_distance_lev_static("abcde", "xcdef") == 3);
116 /* Distance depends on multiple deletions in final row. */
117 ok1(edit_distance_lev_static("aabcc", "bccdd") == 5);
119 /* Distance depends on multiple insertions in final column. */
120 ok1(edit_distance_lev_static("bccdd", "aabcc") == 4);
123 static void test_rdl(void)
126 ok1(edit_distance_rdl_static("", "") == 0);
127 ok1(edit_distance_rdl_static("a", "") == 2);
128 ok1(edit_distance_rdl_static("", "a") == 1);
129 ok1(edit_distance_rdl_static("a", "a") == 0);
130 ok1(edit_distance_rdl_static("a", "b") == 1);
131 ok1(edit_distance_rdl_static("b", "a") == 1);
133 /* Trivial search cases */
134 ok1(edit_distance_rdl_static("a", "bcdef") == 5);
135 ok1(edit_distance_rdl_static("a", "bcadef") == 6);
136 ok1(edit_distance_rdl_static("acdef", "b") == 5);
137 ok1(edit_distance_rdl_static("abcdef", "b") == 6);
139 /* Common prefix with single-char distance */
140 ok1(edit_distance_rdl_static("aa", "ab") == 1);
141 ok1(edit_distance_rdl_static("ab", "aa") == 1);
143 /* Common suffix with single-char distance */
144 ok1(edit_distance_rdl_static("aa", "ba") == 1);
145 ok1(edit_distance_rdl_static("ba", "aa") == 1);
147 /* Non-optimized cases (require Wagner-Fischer matrix) */
148 ok1(edit_distance_rdl_static("ab", "ba") == 1);
149 ok1(edit_distance_rdl_static("abc", "de") == 3);
150 ok1(edit_distance_rdl_static("abc", "def") == 3);
151 ok1(edit_distance_rdl_static("de", "bdef") == 3);
153 /* Transposition + Insert */
154 ok1(edit_distance_rdl_static("ca", "abc") == 3);
156 /* Transpose Weight */
157 ok1(edit_distance_rdl_static("ef", "fe") == 2);
158 ok1(edit_distance_rdl_static("fe", "ef") == 1);
160 /* Insert + Delete + Sub */
161 ok1(edit_distance_rdl_static("abcde", "xcdef") == 3);
163 /* Distance depends on multiple deletions in final row. */
164 ok1(edit_distance_rdl_static("aabcc", "bccdd") == 5);
166 /* Distance depends on multiple insertions in final column. */
167 ok1(edit_distance_rdl_static("bccdd", "aabcc") == 4);
170 static void test_dl(void)
173 ok1(edit_distance_dl_static("", "") == 0);
174 ok1(edit_distance_dl_static("a", "") == 2);
175 ok1(edit_distance_dl_static("", "a") == 1);
176 ok1(edit_distance_dl_static("a", "a") == 0);
177 ok1(edit_distance_dl_static("a", "b") == 1);
178 ok1(edit_distance_dl_static("b", "a") == 1);
180 /* Trivial search cases */
181 ok1(edit_distance_dl_static("a", "bcdef") == 5);
182 ok1(edit_distance_dl_static("a", "bcadef") == 6);
183 ok1(edit_distance_dl_static("acdef", "b") == 5);
184 ok1(edit_distance_dl_static("abcdef", "b") == 6);
186 /* Common prefix with single-char distance */
187 ok1(edit_distance_dl_static("aa", "ab") == 1);
188 ok1(edit_distance_dl_static("ab", "aa") == 1);
190 /* Common suffix with single-char distance */
191 ok1(edit_distance_dl_static("aa", "ba") == 1);
192 ok1(edit_distance_dl_static("ba", "aa") == 1);
194 /* Non-optimized cases (require Wagner-Fischer matrix) */
195 ok1(edit_distance_dl_static("ab", "ba") == 1);
196 ok1(edit_distance_dl_static("abc", "de") == 3);
197 ok1(edit_distance_dl_static("abc", "def") == 3);
198 ok1(edit_distance_dl_static("de", "bdef") == 3);
200 /* Transposition + Insert */
201 ok1(edit_distance_dl_static("ca", "abc") == 3);
203 /* Transpose Weight */
204 ok1(edit_distance_dl_static("ef", "fe") == 2);
205 ok1(edit_distance_dl_static("fe", "ef") == 1);
207 /* Insert + Delete + Sub */
208 ok1(edit_distance_dl_static("abcde", "xcdef") == 3);
210 /* Distance depends on multiple deletions in final row. */
211 ok1(edit_distance_dl_static("aabcc", "bccdd") == 5);
213 /* Distance depends on multiple insertions in final column. */
214 ok1(edit_distance_dl_static("bccdd", "aabcc") == 4);
217 /* Test edit_distance calculation around the stack threshold to ensure memory
218 * is allocated and freed correctly and stack overflow does not occur.
220 * Note: This test is done when ED_COST_IS_SYMMETRIC is not defined so that
221 * tgt can be small to make the test run quickly (with ED_COST_IS_SYMMETRIC the
222 * min length would need to be above the threshold).
224 static void test_mem_use(void)
227 char src[ED_STACK_DIST_VALS + 1];
228 for (size_t i = 0; i < ED_STACK_DIST_VALS; ++i) {
229 src[i] = (char)('A' + (i % 26));
231 src[ED_STACK_DIST_VALS] = '\0';
233 for (ed_size tlen = 1; tlen < 3; ++tlen) {
234 ed_size slen = ED_STACK_DIST_VALS;
235 /* Above threshold, causes allocation */
236 ok(edit_distance_lcs(src, slen, tgt, tlen) == slen - tlen,
237 "edit_distance_lcs(\"%.3s..., %u, \"%.*s\", %u) == %u",
238 src, slen, (int)tlen, tgt, tlen, slen - tlen);
239 ok(edit_distance_lev(src, slen, tgt, tlen) == slen - tlen,
240 "edit_distance_lev(\"%.3s..., %u, \"%.*s\", %u) == %u",
241 src, slen, (int)tlen, tgt, tlen, slen - tlen);
242 ok(edit_distance_rdl(src, slen, tgt, tlen) == slen - tlen,
243 "edit_distance_rdl(\"%.3s..., %u, \"%.*s\", %u) == %u",
244 src, slen, (int)tlen, tgt, tlen, slen - tlen);
245 ok(edit_distance_dl(src, slen, tgt, tlen) == slen - tlen,
246 "edit_distance_dl(\"%.3s..., %u, \"%.*s\", %u) == %u",
247 src, slen, (int)tlen, tgt, tlen, slen - tlen);
249 /* Below threshold, no allocation */
251 ok(edit_distance_lcs(src, slen, tgt, tlen) == slen - tlen,
252 "edit_distance_lcs(\"%.3s..., %u, \"%.*s\", %u) == %u",
253 src, slen, (int)tlen, tgt, tlen, slen - tlen);
254 ok(edit_distance_lev(src, slen, tgt, tlen) == slen - tlen,
255 "edit_distance_lev(\"%.3s..., %u, \"%.*s\", %u) == %u",
256 src, slen, (int)tlen, tgt, tlen, slen - tlen);
257 ok(edit_distance_rdl(src, slen, tgt, tlen) == slen - tlen,
258 "edit_distance_rdl(\"%.3s..., %u, \"%.*s\", %u) == %u",
259 src, slen, (int)tlen, tgt, tlen, slen - tlen);
260 ok(edit_distance_dl(src, slen, tgt, tlen) == slen - tlen,
261 "edit_distance_dl(\"%.3s..., %u, \"%.*s\", %u) == %u",
262 src, slen, (int)tlen, tgt, tlen, slen - tlen);
277 /* Unsupported edit distance measure */
278 enum ed_measure badmeasure = (enum ed_measure)-1;
279 ok1(edit_distance("ab", 2, "ba", 2, badmeasure) == (ed_dist)-1);
281 return exit_status();