source: tests/collections/string-overwrite.cfa@ 1abcec9b

Last change on this file since 1abcec9b was 1abcec9b, checked in by Michael Brooks <mlbrooks@…>, 3 weeks ago

Add overlaid means to list perf histograms. Add 2nd-order graph to the paper and its discussion.
  • Property mode set to 100644
File size: 12.1 KB
Line 
1#include <string.hfa>
2#include <string_sharectx.hfa>
3#include <fstream.hfa>
4
5/*
6
7Modify a subrange of a string, while a witness is watching another subrange of the same string.
8
9Cases are the relative positions and overlaps of the modifier vs the witness.
10MS = modifier start
11ME = modifier end
12ML = modifier length
13WS = witness start
14WE = witness end
15WL = witness length
16
17The test does:
18 starts with the entire string being, initially, the alphabet; prints this entire alphabet
19 sets up modifier and witness as ranges within it, and prints a visualization of those ranges
20 does the main modification
21 prints the result of the main modification, which is always an unsurprising consequence of the modifier range, but shows little about what happened to the witness, particularly if the witness is/became empty
22 modifies the witness to be "?"
23 prints the result of this second modification, which implies what the witness included after the main modification
24
25Deriving the concrete list of cases....
26
27By definition of a string, MS <= ME and WS <= WE.
28This API's convention has Start positions being inclusive and end positions being exclusive.
29
30 v Case number in output
31With 1 equivalence class:
32MS = ME = WS = WE 1
33
34With 2 equivalence classes:
35 < = =
36MS rest 2
37WS rest 3
38
39 = < =
40MS ME WS WE 4
41WS WE MS ME 5
42MS WS ME WE 6
43
44 = = <
45 rest ME 7
46 rest WE 8
47
48With 3 equivalence classes
49 < < =
50MS ME WS WE 9
51 WS ME WE 10
52+2 11, 12
53
54 < = <
55MS WS ME WE 13
56 WE ME 14
57+2 15, 16
58
59 = < <
60MS WS WE ME 17
61 ME WS WE 18
62+2 19, 20
63
64With 4 equivalence classes
65 < < <
66MS ME WS WE 21
67 WS ME WE 22
68 WE ME 23
69+3 24, 25, 26
70
71
72
73*/
74
75const char * OUT_DELIM = "------------------------------------------------------------------------";
76
77void showOneReplacement(string & s, int ms, int ml, int ws, int wl, const char* replaceWith) {
78
79 int me = ms + ml;
80 int we = ws + wl;
81
82 assert( ms >= 0 && ms <= me && me <= len(s) );
83 assert( ws >= 0 && ws <= we && we <= len(s) );
84
85 string mod = s(ms, ml)`share;
86 string wit = s(ws, wl)`share;
87
88 string modOld = mod;
89 string witOld = wit;
90
91 // s, before the mode
92 sout | s;
93
94 // visualize the pair of ranges
95 sout | nlOff;
96 for ( i; len(s) ) {
97 if( i < ms || i > me ) {
98 sout | ' ';
99 } else if ( i < me ) {
100 sout | '-';
101 } else {
102 assert ( i == me );
103 sout | '!';
104 }
105 } sout | nl;
106 for ( i; len(s) ) {
107 if( i < ws || i > we ) {
108 sout | ' ';
109 } else if ( i < we ) {
110 sout | '-';
111 } else {
112 assert ( i == we );
113 sout | '?';
114 }
115 }
116 sout | nl;
117 sout | nlOn;
118
119 mod = replaceWith; // main replacement
120 sout | s | "( wit = " | wit | "witlen = " | len(wit) | " )";
121 wit = "?"; // witness-revelaing replacement
122 sout | s;
123}
124
125void runReplaceCases() {
126 char * alphabetTemplate = "abcdefghijklmnopqrstuvwxyz";
127 struct { int ms; int ml; int ws; int wl; char *replaceWith; char *label; } cases[] = {
128 { 12, 2, 10, 10, "xxxxx", "warmup" },
129 { 10, 0, 10, 0, "=====", "1" },
130 { 10, 0, 10, 0, "==" , "" },
131 { 10, 0, 10, 0, "=" , "" },
132 { 10, 0, 10, 0, "" , "" },
133 { 10, 2, 12, 0, "=====", "2" },
134 { 10, 2, 12, 0, "==" , "" },
135 { 10, 2, 12, 0, "=" , "" },
136 { 10, 2, 12, 0, "" , "" },
137 { 12, 0, 10, 2, "=====", "3" },
138 { 12, 0, 10, 2, "==" , "" },
139 { 12, 0, 10, 2, "=" , "" },
140 { 12, 0, 10, 2, "" , "" },
141 { 10, 0, 12, 0, "=====", "4" },
142 { 10, 0, 12, 0, "==" , "" },
143 { 10, 0, 12, 0, "=" , "" },
144 { 10, 0, 12, 0, "" , "" },
145 { 12, 0, 10, 0, "=====", "5" },
146 { 12, 0, 10, 0, "==" , "" },
147 { 12, 0, 10, 0, "=" , "" },
148 { 12, 0, 10, 0, "" , "" },
149 { 10, 2, 10, 2, "=====", "6" },
150 { 10, 2, 10, 2, "==" , "" },
151 { 10, 2, 10, 2, "=" , "" },
152 { 10, 2, 10, 2, "" , "" },
153 { 10, 2, 10, 0, "=====", "7" },
154 { 10, 2, 10, 0, "==" , "" },
155 { 10, 2, 10, 0, "=" , "" },
156 { 10, 2, 10, 0, "" , "" },
157 { 10, 0, 10, 2, "=====", "8" },
158 { 10, 0, 10, 2, "==" , "" },
159 { 10, 0, 10, 2, "=" , "" },
160 { 10, 0, 10, 2, "" , "" },
161 { 10, 2, 14, 0, "=====", "9" },
162 { 10, 2, 14, 0, "==" , "" },
163 { 10, 2, 14, 0, "=" , "" },
164 { 10, 2, 14, 0, "" , "" },
165 { 10, 4, 12, 2, "=====", "10" },
166 { 10, 4, 12, 2, "==" , "" },
167 { 10, 4, 12, 2, "=" , "" }, // FORMERLY unrunnable bug: tries to print seemingly infinite string
168 { 10, 4, 12, 2, "" , "" }, // ditto
169 { 14, 0, 10, 2, "=====", "11" },
170 { 14, 0, 10, 2, "==" , "" },
171 { 14, 0, 10, 2, "=" , "" },
172 { 14, 0, 10, 2, "" , "" },
173 { 12, 2, 10, 4, "=====", "12" }, // correctness observation: watching klmn while mn |-> xxx gives klxxx because the mn is inside what I'm watching
174 { 12, 2, 10, 4, "==" , "" },
175 { 12, 2, 10, 4, "=" , "" },
176 { 12, 2, 10, 4, "" , "" },
177 { 10, 2, 12, 2, "=====", "13" },
178 { 10, 2, 12, 2, "==" , "" },
179 { 10, 2, 12, 2, "=" , "" },
180 { 10, 2, 12, 2, "" , "" },
181 { 10, 4, 12, 0, "=====", "14" },
182 { 10, 4, 12, 0, "==" , "" },
183 { 10, 4, 12, 0, "=" , "" },
184 { 10, 4, 12, 0, "" , "" },
185 { 12, 2, 10, 2, "=====", "15" },
186 { 12, 2, 10, 2, "==" , "" },
187 { 12, 2, 10, 2, "=" , "" },
188 { 12, 2, 10, 2, "" , "" },
189 { 12, 0, 10, 4, "=====", "16" },
190 { 12, 0, 10, 4, "==" , "" },
191 { 12, 0, 10, 4, "=" , "" },
192 { 12, 0, 10, 4, "" , "" },
193 { 10, 4, 10, 2, "=====", "17" },
194 { 10, 4, 10, 2, "==" , "" },
195 { 10, 4, 10, 2, "=" , "" },
196 { 10, 4, 10, 2, "" , "" },
197 { 10, 0, 12, 2, "=====", "18" },
198 { 10, 0, 12, 2, "==" , "" },
199 { 10, 0, 12, 2, "=" , "" },
200 { 10, 0, 12, 2, "" , "" },
201 { 10, 2, 10, 4, "=====", "19" },
202 { 10, 2, 10, 4, "==" , "" },
203 { 10, 2, 10, 4, "=" , "" },
204 { 10, 2, 10, 4, "" , "" },
205 { 12, 2, 10, 0, "=====", "20" },
206 { 12, 2, 10, 0, "==" , "" },
207 { 12, 2, 10, 0, "=" , "" },
208 { 12, 2, 10, 0, "" , "" },
209 { 10, 2, 14, 2, "=====", "21" },
210 { 10, 2, 14, 2, "==" , "" },
211 { 10, 2, 14, 2, "=" , "" },
212 { 10, 2, 14, 2, "" , "" },
213 { 10, 4, 12, 4, "=====", "22" },
214 { 10, 4, 12, 4, "==" , "" },
215 { 10, 4, 12, 4, "=" , "" },
216 { 10, 4, 12, 4, "" , "" },
217 { 10, 6, 12, 2, "=====", "23" },
218 { 10, 6, 12, 2, "==" , "" },
219 { 10, 6, 12, 2, "=" , "" },
220 { 10, 6, 12, 2, "" , "" },
221 { 14, 2, 10, 2, "=====", "24" },
222 { 14, 2, 10, 2, "==" , "" },
223 { 14, 2, 10, 2, "=" , "" },
224 { 14, 2, 10, 2, "" , "" },
225 { 12, 4, 10, 4, "=====", "25" },
226 { 12, 4, 10, 4, "==" , "" },
227 { 12, 4, 10, 4, "=" , "" },
228 { 12, 4, 10, 4, "" , "" },
229 { 12, 2, 10, 6, "=====", "26" },
230 { 12, 2, 10, 6, "==" , "" },
231 { 12, 2, 10, 6, "=" , "" },
232 { 12, 2, 10, 6, "" , "" },
233 };
234 for ( i; sizeof(cases)/sizeof(cases[0]) ) {
235 sout | OUT_DELIM | cases[i].label;
236 string replaceIn = alphabetTemplate;
237 showOneReplacement( replaceIn, cases[i].ms, cases[i].ml, cases[i].ws, cases[i].wl, cases[i].replaceWith );
238 }
239}
240
241
242int main() {
243
244 #ifdef STRING_SHARING_OFF
245 string_sharectx c = { NO_SHARING };
246 #endif
247
248
249 runReplaceCases();
250
251
252 // in `s(i, k) = sr`:
253 // - whlln, whole-string length = len(s)
254 // - sctln, selection length = k
255 // - rplln, replacement length = len(sr)
256
257 // Extra cases via syntax that appears more direct.
258 // Indirect, as drives the table:
259 // string replace = src(strt, len)`share;
260 // replace = "xyz";
261 // Direct, following:
262 // src(strt, len) = "xyz";
263 sout | OUT_DELIM | "syn-direct";
264
265 // 0 1 2
266 // 01234567890123456789012345
267 string s = "abcdefghijklmnopqrstuvwxyz";
268
269 s(5,5) = "qqqqq"; // start=5, end=10, len=5
270 sout | s;
271
272 s(5,0) = "-----"; // start=5, end=5, len=0
273 sout | s;
274
275
276 // Extra cases for at-/out-of-bound access
277 // Every selection starts and ends at a position between characters, inclusive of before-first and after-last
278 // Intended behaviour is
279 // - negative start means "back from whlln;" i.e., -1 is before-last
280 // - negative sctln menas "back from start;" i.e., -1 from middle selects 1 character before start
281 // - squish inward at subject string's first/last character
282 // - start > whlln means same as start == whlln: after last character, with sctln >= 0 selecting zero characters
283 // - start < -whlln means same as start == -whlln: before first character, with sctln <= 0 selecting zero characters
284 // - (let xstart be the position in [0,whlln] equivalent to start, by the above, in the following...)
285 // - xstart + sctln > whlln means same as sctln = whlln - xstart (significant when sctln is positive)
286 // - xstart + sctln < 0 means same as sctln = -xstart (significant when sctln is negative)
287 // - start = 0 means
288 // - before first, when sctln is zero or positive
289 // - after last, when sctln is negative
290 // - start "outside the string" cases are:
291 // - start = 0 can select forward from first or backward from last (as just stated); note the asymmetric "sctln = 0" handling
292 // - (so, the following cases are available to specify front-v-back explicitly...)
293 // - start >= whlln can select only backward from last, i.e. selects final epsilon when sctln >= 0
294 // - start <= -whln can select only forward from first, i.e. selects initial epsilon when sctln <= 0
295 // most selections have two equivalent representations
296 sout | OUT_DELIM | "boundary";
297/*
298The test
299
300base = 01234
301
302
303(Start|Step) is (just over|right on|just under) the (min|mid|max) value
304|
305whlln (>|=|<) rplln
306|
3070 (=|<) (whlln|rplln)
308
309Every case needs concrete & independent
310whlln
311rpln
312start
313step, aka sctln
314
315Constraint space is
316sel[Start]
317*
318sel[Step]
319*
320lens1
321*
322lens2
323,
324excluding when the lens pair contradicts
325=
326972 concrete test cases (all combinations)
327
328Toward all pairs
329Each case achieves up to 6 further pairings.
330Best-case, achieved with 81 cases. (162 permutations / 2 orderings of a pair)
331
332
333
334Start
335just over the min value
336just over the mid value
337just over the max value
338just over the min value
339just over the mid value
340just over the max value
341just over the min value
342just over the mid value
343just over the max value
344
345
346*/
347
348
349 // Extra cases for modifying substring of substring.
350 sout | OUT_DELIM | "compound";
351
352 s = "abcdefghijklmnopqrstuvwxyz";
353 string sx = s(5,5)`share;
354
355}
Note: See TracBrowser for help on using the repository browser.