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             {
122                 return index + 1;
123             }
124         }
125     }
126     return 0;
127 }
128 
129 @safe pure nothrow /* TODO nothrow @nogc */ unittest
130 {
131     import std.algorithm.searching : startsWith;
132     auto x = "beta version";
133     assert(x.startsWith("beta"));
134 }
135 
136 @safe pure /* TODO nothrow @nogc */ unittest
137 {
138     import std.algorithm.searching : skipOver;
139     auto x = "beta version";
140     assert(x.skipOver("beta"));
141     assert(x == " version");
142 }
143 
144 @safe pure nothrow @nogc unittest
145 {
146     auto x = "beta version";
147     assert(x.skipOverEither("beta", "be") == 1);
148     assert(x == " version");
149 }
150 
151 @safe pure nothrow @nogc unittest
152 {
153     auto x = "beta version";
154     assert(x.skipOverEither("be", "_") == 1);
155 }
156 
157 @safe pure nothrow @nogc unittest
158 {
159     auto x = "beta version";
160     assert(x.skipOverEither("x", "y") == 0);
161 }
162 
163 @safe pure nothrow @nogc unittest
164 {
165 
166     auto x = "beta version";
167     assert(x.skipOverEither("x", "y") == 0);
168 }
169 
170 /** Skip Over Shortest Matching prefix in $(D needles) that prefixes $(D haystack).
171  *
172  * TODO Make return value a specific type that has bool conversion so we can
173  * call it as
174  * if (auto hit = r.skipOverShortestOf(...)) { ... }
175  */
176 size_t skipOverShortestOf(alias pred = "a == b",
177                           Range,
178                           Ranges...)(scope ref Range haystack,
179                                      scope Ranges needles)
180 if (Ranges.length >= 2)
181 {
182     import std.algorithm.searching : startsWith;
183     const hit = startsWith!pred(haystack, needles);
184     if (hit)
185     {
186         // get needle lengths
187         size_t[needles.length] lengths;
188         foreach (const index, ref needle; needles)
189         {
190             import std.traits : isSomeString, isSomeChar;
191             import std.range.primitives : ElementType;
192             import core.internal.traits : Unqual;
193 
194             alias Needle = Unqual!(typeof(needle));
195 
196             static if (is(Unqual!Range ==
197                           Needle))
198             {
199                 lengths[index] = needle.length;
200             }
201             else static if (is(Unqual!(ElementType!Range) ==
202                                Unqual!(ElementType!Needle)))
203             {
204                 lengths[index] = needle.length;
205             }
206             else static if (isSomeString!Range &&
207                             isSomeString!Needle)
208             {
209                 lengths[index] = needle.length;
210             }
211             else static if (isSomeChar!(ElementType!Range) &&
212                             isSomeChar!Needle)
213             {
214                 lengths[index] = 1;
215             }
216             else static if (is(Unqual!(ElementType!Range) ==
217                                Needle))
218             {
219                 lengths[index] = 1;
220             }
221             else
222             {
223                 static assert(0,
224                               "Cannot handle needle of type " ~ Needle.stringof ~
225                               " when haystack has ElementType " ~ (ElementType!Range).stringof);
226             }
227         }
228 
229         import std.range: popFrontN;
230         haystack.popFrontN(lengths[hit - 1]);
231     }
232 
233     return hit;
234 
235 }
236 
237 @safe pure unittest
238 {
239     auto x = "beta version";
240     assert(x.skipOverShortestOf("beta", "be") == 2);
241     assert(x == "ta version");
242 }
243 
244 @safe pure unittest
245 {
246     auto x = "beta version";
247     assert(x.skipOverShortestOf("be", "beta") == 1);
248     assert(x == "ta version");
249 }
250 
251 @safe pure unittest
252 {
253     auto x = "beta version";
254     assert(x.skipOverShortestOf('b', "be", "beta") == 1);
255     assert(x == "eta version");
256 }
257 
258 /** Skip Over Longest Matching prefix in $(D needles) that prefixes $(D haystack).
259  */
260 SkipOverLongest skipOverLongestOf(alias pred = "a == b", Range, Ranges...)(scope ref Range haystack,
261                                                                            scope Ranges needles)
262 {
263     // TODO figure out which needles that are prefixes of other needles by first
264     // sorting them and then use some adjacent filtering algorithm
265     static assert(0, "TODO implement");
266 }
267 
268 /** Skip Over Back Shortest Match of `needles` in `haystack`. */
269 size_t skipOverBackShortestOf(alias pred = "a == b", Range, Ranges...)(scope ref Range haystack,
270                                                                        scope Ranges needles) @trusted
271 // TODO We cannot prove that cast(ubyte[]) of a type that have no directions is safe
272 if (Ranges.length >= 2)
273 {
274     import std.range: retro, ElementType;
275     import std.traits: hasIndirections;
276     import core.internal.traits : Unqual;
277     import std.meta: staticMap, AliasSeq;
278     // import nxt.traits_ex: allSame;
279 
280     static if ((!hasIndirections!(ElementType!Range))/*  && */
281                /* allSame!(Unqual!Range, staticMap!(Unqual, Ranges)) */)
282     {
283         auto retroHaystack = (cast(ubyte[])haystack).retro;
284 
285         alias Retro(Range) = typeof((ubyte[]).init.retro);
286         AliasSeq!(staticMap!(Retro, Ranges)) retroNeedles;
287         foreach (const index, const ref needle; needles)
288         {
289             retroNeedles[index] = (cast(ubyte[])needle).retro;
290         }
291 
292         const retroHit = retroHaystack.skipOverShortestOf(retroNeedles);
293         haystack = haystack[0.. $ - (haystack.length - retroHaystack.length)];
294 
295         return retroHit;
296     }
297     else
298     {
299         static assert(0, "Unsupported combination of haystack type " ~ Range.stringof ~
300                       " with needle types " ~ Ranges.stringof);
301     }
302 }
303 
304 @safe pure nothrow @nogc unittest
305 {
306     auto x = "alpha_beta";
307     assert(x.skipOverBackShortestOf("x", "beta") == 2);
308     assert(x == "alpha_");
309 }
310 
311 @safe pure nothrow @nogc unittest
312 {
313     auto x = "alpha_beta";
314     assert(x.skipOverBackShortestOf("a", "beta") == 1);
315     assert(x == "alpha_bet");
316 }
317 
318 /** Drop $(D prefixes) in $(D s).
319  *
320  * TODO Use multi-argument skipOver when it becomes available
321  * http://forum.dlang.org/thread/bug-12335-3@https.d.puremagic.com%2Fissues%2F
322 */
323 void skipOverPrefixes(R, A)(scope ref R s,
324                             const scope A prefixes)
325 {
326     import std.algorithm.searching : skipOver;
327     foreach (prefix; prefixes)
328     {
329         if (s.length > prefix.length &&
330             s.skipOver(prefix))
331         {
332             break;
333         }
334     }
335 }
336 
337 /** Drop $(D suffixes) in $(D s).
338  */
339 void skipOverSuffixes(R, A)(scope ref R s,
340                             const scope A suffixes)
341 {
342     foreach (suffix; suffixes)
343     {
344         if (s.length > suffix.length &&
345             s.endsWith(suffix))
346         {
347             s = s[0 .. $ - suffix.length]; // TODO .ptr
348             break;
349         }
350     }
351 }
352 
353 /** Drop either both prefix `frontPrefix` and suffix `backSuffix` or do nothing.
354  *
355  * Returns: `true` upon drop, `false` otherwise.
356  */
357 bool skipOverFrontAndBack(alias pred = "a == b", R, E, F)(scope ref R r,
358                                                           scope E frontPrefix,
359                                                           scope F backSuffix)
360 if (isBidirectionalRange!R &&
361     is(typeof(binaryFun!pred(ElementType!R.init, E.init))) &&
362     is(typeof(binaryFun!pred(ElementType!R.init, F.init))))
363 {
364     import core.internal.traits : Unqual;
365     import std.traits : isArray;
366     static if (isArray!R &&
367                is(Unqual!(typeof(R.init[0])) == E)) // for instance if `R` is `string` and `E` is `char`
368     {
369         if (r.length >= 2 &&
370             r[0] == frontPrefix &&
371             r[$ - 1] == backSuffix)
372         {
373             r = r[1 .. $ - 1];
374             return true;
375         }
376     }
377     else
378     {
379         if (r.length >= 2 && // TODO express this requirement in `r` as `hasLength`
380             binaryFun!pred(r.front, frontPrefix) &&
381             binaryFun!pred(r.back, backSuffix))
382         {
383             import std.range.primitives : popBack, popFront;
384             r.popFront();
385             r.popBack();
386             return true;
387         }
388     }
389     return false;
390 }
391 
392 @safe pure nothrow @nogc unittest
393 {
394     auto expr = `"alpha"`;
395     assert(expr.skipOverFrontAndBack('"', '"'));
396     assert(expr == `alpha`);
397 }
398 
399 @safe pure nothrow @nogc unittest
400 {
401     auto expr_ = `"alpha"`;
402     auto expr = expr_;
403     assert(!expr.skipOverFrontAndBack(',', '"'));
404     assert(expr == expr_);
405 }
406 
407 @safe pure nothrow @nogc unittest
408 {
409     auto expr_ = `"alpha`;
410     auto expr = expr_;
411     assert(!expr.skipOverFrontAndBack('"', '"'));
412     assert(expr == expr_);
413 }
414 
415 @safe pure nothrow @nogc unittest
416 {
417     auto expr_ = `alpha"`;
418     auto expr = expr_;
419     assert(!expr.skipOverFrontAndBack('"', '"'));
420     assert(expr == expr_);
421 }