nxt.skip_ex source code

1 /** Extensions to skipOver.
2  *
3  * See_Also: https://forum.dlang.org/post/tswdobtabsjarszfkmbt@forum.dlang.org
4  * See_Also: https://forum.dlang.org/post/ybamybeakxwxwleebnwb@forum.dlang.org
5  */
6 module nxt.skip_ex;
7 
8 import std.functional : binaryFun;
9 import std.range.primitives : front, back, save, empty, popBack, hasSlicing, isBidirectionalRange, ElementType;
10 
11 version(unittest)
12 {
13     import nxt.array_help : s;
14 }
15 
16 /** Skip over the ending portion of `haystack` that matches `needle`, or nothing upon no match.
17  *
18  * See_Also: std.algorithm.searching.skipOver.
19  */
20 bool skipOverBack(Haystack, Needle)(scope ref Haystack haystack,
21                                     scope Needle needle) // non`const` because may be range with mutable range primitives
22 if (isBidirectionalRange!Haystack &&
23     isBidirectionalRange!Needle &&
24     is(typeof(haystack.back == needle.back)))
25 {
26     static if (is(typeof(haystack[] == needle) : bool) &&
27                is(typeof(needle.length > haystack.length) : bool) &&
28                is(typeof(haystack = haystack[])))
29     {
30         if (haystack.length >= needle.length &&
31             haystack[$ - needle.length .. $] == needle)
32         {
33             haystack = haystack[0 .. haystack.length - needle.length];
34             return true;
35         }
36         return false;
37     }
38     else
39     {
40         return skipOverBack!((a, b) => a == b)(haystack, needle);
41     }
42 }
43 
44 ///
45 bool skipOverBack(alias pred, Haystack, Needle)(scope ref Haystack haystack,
46                                                 scope Needle needle) // non`const` because may be range with mutable range primitives
47 if (isBidirectionalRange!Haystack &&
48     isBidirectionalRange!Needle &&
49     is(typeof(binaryFun!pred(haystack.back, needle.back)))) // TODO: Needle doesn't have to bi-directional if Haystack is RandomAccess and Needle.hasLength
50 {
51     import std.range.primitives : hasLength;
52     static if (hasLength!Haystack && hasLength!Needle)
53     {
54         if (haystack.length < needle.length) { return false; } // fast discardal
55     }
56     auto r = haystack.save;
57     while (!needle.empty &&
58            !r.empty &&
59            binaryFun!pred(r.back, needle.back))
60     {
61         r.popBack();
62         needle.popBack();
63     }
64     if (needle.empty)
65     {
66         haystack = r;
67     }
68     return needle.empty;
69 }
70 
71 ///
72 @safe pure nothrow @nogc unittest
73 {
74     auto s1_ = [1, 2, 3].s;
75     auto s1 = s1_[];
76     const s2_ = [2, 3].s;
77     const s2 = s2_[];
78     s1.skipOverBack(s2);
79     assert(s1 == [1].s);
80     s1.skipOverBack(s2);        // no effect
81     assert(s1 == [1].s);
82 }
83 
84 @safe pure nothrow @nogc unittest
85 {
86     import std.algorithm : equal;
87     auto s1 = "Hello world";
88     assert(!skipOverBack(s1, "Ha"));
89     assert(s1 == "Hello world");
90     assert(skipOverBack(s1, "world") && s1 == "Hello ");
91 }
92 
93 /** Variadic version of $(D skipOver).
94  *
95  * Returns: index + 1 into matching $(D needles), 0 otherwise.
96  *
97  * TODO: Reuse `skipOver with many needles` or write own array-version of `skipOver` that's faster.
98  */
99 size_t skipOverEither(alias pred = "a == b", Range, Ranges...)(scope ref Range haystack,
100                                                                scope Ranges needles)
101 if (Ranges.length >= 2)
102 {
103     import nxt.array_traits : isSameSlices;
104     foreach (const index, const ref needle; needles)
105     {
106         static if (pred == "a == b" &&
107                    isSameSlices!(Range, Ranges)) // fast
108         {
109             // `nothrow` char[] fast path
110             if (haystack.length >= needle.length &&
111                 haystack[0 .. needle.length] == needle) // TODO: `haystack.ptr`
112             {
113                 haystack = haystack[needle.length .. haystack.length]; // TODO: `haystack.ptr`
114                 return index + 1;
115             }
116         }
117         else
118         {
119             import std.algorithm.searching : skipOver;
120             if (haystack.skipOver(needle)) // TODO: nothrow
121                 return index + 1;
122         }
123     }
124     return 0;
125 }
126 
127 @safe pure nothrow /* TODO: nothrow @nogc */ unittest
128 {
129     import std.algorithm.searching : startsWith;
130     auto x = "beta version";
131     assert(x.startsWith("beta"));
132 }
133 
134 @safe pure /* TODO: nothrow @nogc */ unittest
135 {
136     import std.algorithm.searching : skipOver;
137     auto x = "beta version";
138     assert(x.skipOver("beta"));
139     assert(x == " version");
140 }
141 
142 @safe pure nothrow @nogc unittest
143 {
144     auto x = "beta version";
145     assert(x.skipOverEither("beta", "be") == 1);
146     assert(x == " version");
147 }
148 
149 @safe pure nothrow @nogc unittest
150 {
151     auto x = "beta version";
152     assert(x.skipOverEither("be", "_") == 1);
153 }
154 
155 @safe pure nothrow @nogc unittest
156 {
157     auto x = "beta version";
158     assert(x.skipOverEither("x", "y") == 0);
159 }
160 
161 @safe pure nothrow @nogc unittest
162 {
163 
164     auto x = "beta version";
165     assert(x.skipOverEither("x", "y") == 0);
166 }
167 
168 /** Skip Over Shortest Matching prefix in $(D needles) that prefixes $(D haystack).
169  *
170  * TODO: Make return value a specific type that has bool conversion so we can
171  * call it as
172  * if (auto hit = r.skipOverShortestOf(...)) { ... }
173  */
174 size_t skipOverShortestOf(alias pred = "a == b",
175                           Range,
176                           Ranges...)(scope ref Range haystack,
177                                      scope Ranges needles)
178 if (Ranges.length >= 2)
179 {
180     import std.algorithm.searching : startsWith;
181     const hit = startsWith!pred(haystack, needles);
182     if (hit)
183     {
184         // get needle lengths
185         size_t[needles.length] lengths;
186         foreach (const index, ref needle; needles)
187         {
188             import std.traits : isSomeString, isSomeChar;
189             import std.range.primitives : ElementType;
190             import core.internal.traits : Unqual;
191 
192             alias Needle = Unqual!(typeof(needle));
193 
194             static if (is(Unqual!Range ==
195                           Needle))
196             {
197                 lengths[index] = needle.length;
198             }
199             else static if (is(Unqual!(ElementType!Range) ==
200                                Unqual!(ElementType!Needle)))
201             {
202                 lengths[index] = needle.length;
203             }
204             else static if (isSomeString!Range &&
205                             isSomeString!Needle)
206             {
207                 lengths[index] = needle.length;
208             }
209             else static if (isSomeChar!(ElementType!Range) &&
210                             isSomeChar!Needle)
211             {
212                 lengths[index] = 1;
213             }
214             else static if (is(Unqual!(ElementType!Range) ==
215                                Needle))
216             {
217                 lengths[index] = 1;
218             }
219             else
220             {
221                 static assert(0,
222                               "Cannot handle needle of type " ~ Needle.stringof ~
223                               " when haystack has ElementType " ~ (ElementType!Range).stringof);
224             }
225         }
226 
227         import std.range: popFrontN;
228         haystack.popFrontN(lengths[hit - 1]);
229     }
230 
231     return hit;
232 
233 }
234 
235 @safe pure unittest
236 {
237     auto x = "beta version";
238     assert(x.skipOverShortestOf("beta", "be") == 2);
239     assert(x == "ta version");
240 }
241 
242 @safe pure unittest
243 {
244     auto x = "beta version";
245     assert(x.skipOverShortestOf("be", "beta") == 1);
246     assert(x == "ta version");
247 }
248 
249 @safe pure unittest
250 {
251     auto x = "beta version";
252     assert(x.skipOverShortestOf('b', "be", "beta") == 1);
253     assert(x == "eta version");
254 }
255 
256 /** Skip Over Longest Matching prefix in $(D needles) that prefixes $(D haystack).
257  */
258 SkipOverLongest skipOverLongestOf(alias pred = "a == b", Range, Ranges...)(scope ref Range haystack,
259                                                                            scope Ranges needles)
260 {
261     // TODO: figure out which needles that are prefixes of other needles by first
262     // sorting them and then use some adjacent filtering algorithm
263     static assert(0, "TODO: implement");
264 }
265 
266 /** Skip Over Back Shortest Match of `needles` in `haystack`. */
267 size_t skipOverBackShortestOf(alias pred = "a == b", Range, Ranges...)(scope ref Range haystack,
268                                                                        scope Ranges needles) @trusted
269 // TODO: We cannot prove that cast(ubyte[]) of a type that have no directions is safe
270 if (Ranges.length >= 2)
271 {
272     import std.range: retro, ElementType;
273     import std.traits: hasIndirections;
274     import core.internal.traits : Unqual;
275     import std.meta: staticMap, AliasSeq;
276     // import nxt.traits_ex: allSame;
277 
278     static if ((!hasIndirections!(ElementType!Range))/*  && */
279                /* allSame!(Unqual!Range, staticMap!(Unqual, Ranges)) */)
280     {
281         auto retroHaystack = (cast(ubyte[])haystack).retro;
282 
283         alias Retro(Range) = typeof((ubyte[]).init.retro);
284         AliasSeq!(staticMap!(Retro, Ranges)) retroNeedles;
285         foreach (const index, const ref needle; needles)
286         {
287             retroNeedles[index] = (cast(ubyte[])needle).retro;
288         }
289 
290         const retroHit = retroHaystack.skipOverShortestOf(retroNeedles);
291         haystack = haystack[0.. $ - (haystack.length - retroHaystack.length)];
292 
293         return retroHit;
294     }
295     else
296     {
297         static assert(0, "Unsupported combination of haystack type " ~ Range.stringof ~
298                       " with needle types " ~ Ranges.stringof);
299     }
300 }
301 
302 @safe pure nothrow @nogc unittest
303 {
304     auto x = "alpha_beta";
305     assert(x.skipOverBackShortestOf("x", "beta") == 2);
306     assert(x == "alpha_");
307 }
308 
309 @safe pure nothrow @nogc unittest
310 {
311     auto x = "alpha_beta";
312     assert(x.skipOverBackShortestOf("a", "beta") == 1);
313     assert(x == "alpha_bet");
314 }
315 
316 /** Drop $(D prefixes) in $(D s).
317  *
318  * TODO: Use multi-argument skipOver when it becomes available
319  * http://forum.dlang.org/thread/bug-12335-3@https.d.puremagic.com%2Fissues%2F
320 */
321 void skipOverPrefixes(R, A)(scope ref R s,
322                             const scope A prefixes)
323 {
324     import std.algorithm.searching : skipOver;
325     foreach (prefix; prefixes)
326     {
327         if (s.length > prefix.length &&
328             s.skipOver(prefix))
329         {
330             break;
331         }
332     }
333 }
334 
335 /** Drop $(D suffixes) in $(D s).
336  */
337 void skipOverSuffixes(R, A)(scope ref R s,
338                             const scope A suffixes)
339 {
340     foreach (suffix; suffixes)
341     {
342         if (s.length > suffix.length &&
343             s.endsWith(suffix))
344         {
345             s = s[0 .. $ - suffix.length]; // TODO: .ptr
346             break;
347         }
348     }
349 }
350 
351 /** Drop either both prefix `frontPrefix` and suffix `backSuffix` or do nothing.
352  *
353  * Returns: `true` upon drop, `false` otherwise.
354  */
355 bool skipOverFrontAndBack(alias pred = "a == b", R, E, F)(scope ref R r,
356                                                           scope E frontPrefix,
357                                                           scope F backSuffix)
358 if (isBidirectionalRange!R &&
359     is(typeof(binaryFun!pred(ElementType!R.init, E.init))) &&
360     is(typeof(binaryFun!pred(ElementType!R.init, F.init))))
361 {
362     import core.internal.traits : Unqual;
363     import std.traits : isArray;
364     static if (isArray!R &&
365                is(Unqual!(typeof(R.init[0])) == E)) // for instance if `R` is `string` and `E` is `char`
366     {
367         if (r.length >= 2 &&
368             r[0] == frontPrefix &&
369             r[$ - 1] == backSuffix)
370         {
371             r = r[1 .. $ - 1];
372             return true;
373         }
374     }
375     else
376     {
377         if (r.length >= 2 && // TODO: express this requirement in `r` as `hasLength`
378             binaryFun!pred(r.front, frontPrefix) &&
379             binaryFun!pred(r.back, backSuffix))
380         {
381             import std.range.primitives : popBack, popFront;
382             r.popFront();
383             r.popBack();
384             return true;
385         }
386     }
387     return false;
388 }
389 
390 @safe pure nothrow @nogc unittest
391 {
392     auto expr = `"alpha"`;
393     assert(expr.skipOverFrontAndBack('"', '"'));
394     assert(expr == `alpha`);
395 }
396 
397 @safe pure nothrow @nogc unittest
398 {
399     auto expr_ = `"alpha"`;
400     auto expr = expr_;
401     assert(!expr.skipOverFrontAndBack(',', '"'));
402     assert(expr == expr_);
403 }
404 
405 @safe pure nothrow @nogc unittest
406 {
407     auto expr_ = `"alpha`;
408     auto expr = expr_;
409     assert(!expr.skipOverFrontAndBack('"', '"'));
410     assert(expr == expr_);
411 }
412 
413 @safe pure nothrow @nogc unittest
414 {
415     auto expr_ = `alpha"`;
416     auto expr = expr_;
417     assert(!expr.skipOverFrontAndBack('"', '"'));
418     assert(expr == expr_);
419 }