The OpenD Programming Language

1 /**
2 This module is a submodule of $(MREF std, range).
3 
4 The main $(MREF std, range) module provides template-based tools for working with
5 ranges, but sometimes an object-based interface for ranges is needed, such as
6 when runtime polymorphism is required. For this purpose, this submodule
7 provides a number of object and `interface` definitions that can be used to
8 wrap around range objects created by the $(MREF std, range) templates.
9 
10 $(SCRIPT inhibitQuickIndex = 1;)
11 $(DIVC quickindex,
12 $(BOOKTABLE ,
13     $(TR $(TD $(LREF InputRange))
14         $(TD Wrapper for input ranges.
15     ))
16     $(TR $(TD $(LREF InputAssignable))
17         $(TD Wrapper for input ranges with assignable elements.
18     ))
19     $(TR $(TD $(LREF ForwardRange))
20         $(TD Wrapper for forward ranges.
21     ))
22     $(TR $(TD $(LREF ForwardAssignable))
23         $(TD Wrapper for forward ranges with assignable elements.
24     ))
25     $(TR $(TD $(LREF BidirectionalRange))
26         $(TD Wrapper for bidirectional ranges.
27     ))
28     $(TR $(TD $(LREF BidirectionalAssignable))
29         $(TD Wrapper for bidirectional ranges with assignable elements.
30     ))
31     $(TR $(TD $(LREF RandomAccessFinite))
32         $(TD Wrapper for finite random-access ranges.
33     ))
34     $(TR $(TD $(LREF RandomAccessAssignable))
35         $(TD Wrapper for finite random-access ranges with assignable elements.
36     ))
37     $(TR $(TD $(LREF RandomAccessInfinite))
38         $(TD Wrapper for infinite random-access ranges.
39     ))
40     $(TR $(TD $(LREF OutputRange))
41         $(TD Wrapper for output ranges.
42     ))
43     $(TR $(TD $(LREF OutputRangeObject))
44         $(TD Class that implements the `OutputRange` interface and wraps the
45         `put` methods in virtual functions.
46     ))
47     $(TR $(TD $(LREF outputRangeObject))
48         $(TD Convenience function for creating an `OutputRangeObject` with a base
49         range of type R that accepts types E.
50     ))
51     $(TR $(TD $(LREF InputRangeObject))
52         $(TD Class that implements the `InputRange` interface and wraps the
53         input range methods in virtual functions.
54     ))
55     $(TR $(TD $(LREF inputRangeObject))
56         $(TD Convenience function for creating an `InputRangeObject`
57         of the proper type.
58     ))
59     $(TR $(TD $(LREF MostDerivedInputRange))
60         $(TD Returns the interface type that best matches the range.
61     ))
62 ))
63 
64 
65 Source: $(PHOBOSSRC std/range/interfaces.d)
66 
67 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
68 
69 Authors: $(HTTP erdani.com, Andrei Alexandrescu), David Simcha, and
70          $(HTTP jmdavisprog.com, Jonathan M Davis). Credit for some of the ideas
71          in building this module goes to
72          $(HTTP fantascienza.net/leonardo/so/, Leonardo Maffi).
73 */
74 module std.range.interfaces;
75 
76 import std.meta;
77 import std.range.primitives;
78 import std.traits;
79 
80 /**These interfaces are intended to provide virtual function-based wrappers
81  * around input ranges with element type E.  This is useful where a well-defined
82  * binary interface is required, such as when a DLL function or virtual function
83  * needs to accept a generic range as a parameter. Note that
84  * $(REF_ALTTEXT isInputRange, isInputRange, std, range, primitives)
85  * and friends check for conformance to structural interfaces
86  * not for implementation of these `interface` types.
87  *
88  * Limitations:
89  *
90  * These interfaces are not capable of forwarding `ref` access to elements.
91  *
92  * Infiniteness of the wrapped range is not propagated.
93  *
94  * Length is not propagated in the case of non-random access ranges.
95  *
96  * See_Also:
97  * $(LREF inputRangeObject)
98  */
99 interface InputRange(E) {
100     ///
101     @property E front();
102 
103     /**Calls $(REF moveFront, std, range, primitives) on the wrapped range, if
104      * possible. Otherwise, throws an $(LREF UnsupportedRangeMethod) exception.
105      */
106     E moveFront();
107 
108     ///
109     void popFront();
110 
111     ///
112     @property bool empty();
113 
114     /* Measurements of the benefits of using opApply instead of range primitives
115      * for foreach, using timings for iterating over an iota(100_000_000) range
116      * with an empty loop body, using the same hardware in each case:
117      *
118      * Bare Iota struct, range primitives:  278 milliseconds
119      * InputRangeObject, opApply:           436 milliseconds  (1.57x penalty)
120      * InputRangeObject, range primitives:  877 milliseconds  (3.15x penalty)
121      */
122 
123     /**`foreach` iteration uses opApply, since one delegate call per loop
124      * iteration is faster than three virtual function calls.
125      */
126     int opApply(scope int delegate(E));
127 
128     /// Ditto
129     int opApply(scope int delegate(size_t, E));
130 
131 }
132 
133 ///
134 @safe unittest
135 {
136     import std.algorithm.iteration : map;
137     import std.range : iota;
138 
139     void useRange(InputRange!int range) {
140         // Function body.
141     }
142 
143     // Create a range type.
144     auto squares = map!"a * a"(iota(10));
145 
146     // Wrap it in an interface.
147     auto squaresWrapped = inputRangeObject(squares);
148 
149     // Use it.
150     useRange(squaresWrapped);
151 }
152 
153 /**Interface for a forward range of type `E`.*/
154 interface ForwardRange(E) : InputRange!E {
155     ///
156     @property ForwardRange!E save();
157 }
158 
159 /**Interface for a bidirectional range of type `E`.*/
160 interface BidirectionalRange(E) : ForwardRange!(E) {
161     ///
162     @property BidirectionalRange!E save();
163 
164     ///
165     @property E back();
166 
167     /**Calls $(REF moveBack, std, range, primitives) on the wrapped range, if
168      * possible. Otherwise, throws an $(LREF UnsupportedRangeMethod) exception
169      */
170     E moveBack();
171 
172     ///
173     void popBack();
174 }
175 
176 /**Interface for a finite random access range of type `E`.*/
177 interface RandomAccessFinite(E) : BidirectionalRange!(E) {
178     ///
179     @property RandomAccessFinite!E save();
180 
181     ///
182     E opIndex(size_t);
183 
184     ///
185     E moveAt(size_t);
186 
187     ///
188     @property size_t length();
189 
190     ///
191     alias opDollar = length;
192 
193     // Can't support slicing until issues with requiring slicing for all
194     // finite random access ranges are fully resolved.
195     version (none)
196     {
197         ///
198         RandomAccessFinite!E opSlice(size_t, size_t);
199     }
200 }
201 
202 /**Interface for an infinite random access range of type `E`.*/
203 interface RandomAccessInfinite(E) : ForwardRange!E {
204     ///
205     enum bool empty = false;
206 
207     /**Calls $(REF moveAt, std, range, primitives) on the wrapped range, if
208      * possible. Otherwise, throws an $(LREF UnsupportedRangeMethod) exception.
209      */
210     E moveAt(size_t);
211 
212     ///
213     @property RandomAccessInfinite!E save();
214 
215     ///
216     E opIndex(size_t);
217 }
218 
219 // https://issues.dlang.org/show_bug.cgi?id=22608
220 @safe unittest
221 {
222     static assert(isRandomAccessRange!(RandomAccessInfinite!int));
223 }
224 
225 /**Adds assignable elements to InputRange.*/
226 interface InputAssignable(E) : InputRange!E {
227     ///
228     @property void front(E newVal);
229 
230     alias front = InputRange!E.front; // overload base interface method
231 }
232 
233 @safe unittest
234 {
235     static assert(isInputRange!(InputAssignable!int));
236 }
237 
238 /**Adds assignable elements to ForwardRange.*/
239 interface ForwardAssignable(E) : InputAssignable!E, ForwardRange!E {
240     ///
241     @property ForwardAssignable!E save();
242 }
243 
244 /**Adds assignable elements to BidirectionalRange.*/
245 interface BidirectionalAssignable(E) : ForwardAssignable!E, BidirectionalRange!E {
246     ///
247     @property BidirectionalAssignable!E save();
248 
249     ///
250     @property void back(E newVal);
251 }
252 
253 /**Adds assignable elements to RandomAccessFinite.*/
254 interface RandomFiniteAssignable(E) : RandomAccessFinite!E, BidirectionalAssignable!E {
255     ///
256     @property RandomFiniteAssignable!E save();
257 
258     ///
259     void opIndexAssign(E val, size_t index);
260 }
261 
262 /**Interface for an output range of type `E`.  Usage is similar to the
263  * `InputRange` interface and descendants.*/
264 interface OutputRange(E) {
265     ///
266     void put(E);
267 }
268 
269 // https://issues.dlang.org/show_bug.cgi?id=6973
270 @safe unittest
271 {
272     static assert(isOutputRange!(OutputRange!int, int));
273 }
274 
275 
276 // CTFE function that generates mixin code for one put() method for each
277 // type E.
278 private string putMethods(E...)()
279 {
280     import std.conv : to;
281 
282     string ret;
283 
284     foreach (ti, Unused; E)
285     {
286         ret ~= "void put(E[" ~ to!string(ti) ~ "] e) { .put(_range, e); }";
287     }
288 
289     return ret;
290 }
291 
292 /**Implements the `OutputRange` interface for all types E and wraps the
293  * `put` method for each type `E` in a virtual function.
294  */
295 class OutputRangeObject(R, E...) : staticMap!(OutputRange, E) {
296     // @BUG 4689:  There should be constraints on this template class, but
297     // DMD won't let me put them in.
298     private R _range;
299 
300     ///
301     this(R range) {
302         this._range = range;
303     }
304 
305     mixin(putMethods!E());
306 }
307 
308 
309 /**Returns the interface type that best matches `R`.*/
310 template MostDerivedInputRange(R)
311 if (isInputRange!(Unqual!R))
312 {
313     private alias E = ElementType!R;
314 
315     static if (isRandomAccessRange!R)
316     {
317         static if (isInfinite!R)
318         {
319             alias MostDerivedInputRange = RandomAccessInfinite!E;
320         }
321         else static if (hasAssignableElements!R)
322         {
323             alias MostDerivedInputRange = RandomFiniteAssignable!E;
324         }
325         else
326         {
327             alias MostDerivedInputRange = RandomAccessFinite!E;
328         }
329     }
330     else static if (isBidirectionalRange!R)
331     {
332         static if (hasAssignableElements!R)
333         {
334             alias MostDerivedInputRange = BidirectionalAssignable!E;
335         }
336         else
337         {
338             alias MostDerivedInputRange = BidirectionalRange!E;
339         }
340     }
341     else static if (isForwardRange!R)
342     {
343         static if (hasAssignableElements!R)
344         {
345             alias MostDerivedInputRange = ForwardAssignable!E;
346         }
347         else
348         {
349             alias MostDerivedInputRange = ForwardRange!E;
350         }
351     }
352     else
353     {
354         static if (hasAssignableElements!R)
355         {
356             alias MostDerivedInputRange = InputAssignable!E;
357         }
358         else
359         {
360             alias MostDerivedInputRange = InputRange!E;
361         }
362     }
363 }
364 
365 /**Implements the most derived interface that `R` works with and wraps
366  * all relevant range primitives in virtual functions.  If `R` is already
367  * derived from the `InputRange` interface, aliases itself away.
368  */
369 template InputRangeObject(R)
370 if (isInputRange!(Unqual!R))
371 {
372     static if (is(R : InputRange!(ElementType!R)))
373     {
374         alias InputRangeObject = R;
375     }
376     else static if (!is(Unqual!R == R))
377     {
378         alias InputRangeObject = InputRangeObject!(Unqual!R);
379     }
380     else
381     {
382 
383         ///
384         class InputRangeObject : MostDerivedInputRange!(R) {
385             private R _range;
386             private alias E = ElementType!R;
387 
388             this(R range) {
389                 this._range = range;
390             }
391 
392             @property E front() { return _range.front; }
393 
394             E moveFront() {
395                 static if (__traits(compiles, _range.moveFront()))
396                     return _range.moveFront();
397                 else
398                     throw new UnsupportedRangeMethod(
399                         "Cannot move the front of a(n) `" ~ R.stringof ~ "`");
400             }
401 
402             void popFront() { _range.popFront(); }
403             @property bool empty() { return _range.empty; }
404 
405             static if (isForwardRange!R)
406             {
407                 @property typeof(this) save() {
408                     return new typeof(this)(_range.save);
409                 }
410             }
411 
412             static if (hasAssignableElements!R)
413             {
414                 @property void front(E newVal) {
415                     _range.front = newVal;
416                 }
417             }
418 
419             static if (isBidirectionalRange!R)
420             {
421                 @property E back() { return _range.back; }
422 
423                 E moveBack() {
424                     static if (__traits(compiles, _range.moveFront()))
425                         return _range.moveBack();
426                     else
427                         throw new UnsupportedRangeMethod(
428                             "Cannot move the back of a(n) `" ~ R.stringof ~ "`");
429                 }
430 
431                 void popBack() { return _range.popBack(); }
432 
433                 static if (hasAssignableElements!R)
434                 {
435                     @property void back(E newVal) {
436                         _range.back = newVal;
437                     }
438                 }
439             }
440 
441             static if (isRandomAccessRange!R)
442             {
443                 E opIndex(size_t index) {
444                     return _range[index];
445                 }
446 
447                 E moveAt(size_t index) {
448                     static if (__traits(compiles, _range.moveAt(index)))
449                         return _range.moveAt(index);
450                     else
451                         throw new UnsupportedRangeMethod(
452                             "Cannot move an element of a(n) `" ~ R.stringof ~ "`");
453                 }
454 
455                 static if (hasAssignableElements!R)
456                 {
457                     void opIndexAssign(E val, size_t index) {
458                         _range[index] = val;
459                     }
460                 }
461 
462                 static if (!isInfinite!R)
463                 {
464                     @property size_t length() {
465                         return _range.length;
466                     }
467 
468                     alias opDollar = length;
469 
470                     // Can't support slicing until all the issues with
471                     // requiring slicing support for finite random access
472                     // ranges are resolved.
473                     version (none)
474                     {
475                         typeof(this) opSlice(size_t lower, size_t upper) {
476                             return new typeof(this)(_range[lower .. upper]);
477                         }
478                     }
479                 }
480             }
481 
482             // Optimization:  One delegate call is faster than three virtual
483             // function calls.  Use opApply for foreach syntax.
484             int opApply(scope int delegate(E) dg) {
485                 int res;
486 
487                 for (auto r = _range; !r.empty; r.popFront())
488                 {
489                     res = dg(r.front);
490                     if (res) break;
491                 }
492 
493                 return res;
494             }
495 
496             int opApply(scope int delegate(size_t, E) dg) {
497                 int res;
498 
499                 size_t i = 0;
500                 for (auto r = _range; !r.empty; r.popFront())
501                 {
502                     res = dg(i, r.front);
503                     if (res) break;
504                     i++;
505                 }
506 
507                 return res;
508             }
509         }
510     }
511 }
512 
513 /**Convenience function for creating an `InputRangeObject` of the proper type.
514  * See $(LREF InputRange) for an example.
515  */
516 InputRangeObject!R inputRangeObject(R)(R range)
517 if (isInputRange!R)
518 {
519     static if (is(R : InputRange!(ElementType!R)))
520     {
521         return range;
522     }
523     else
524     {
525         return new InputRangeObject!R(range);
526     }
527 }
528 
529 /**Convenience function for creating an `OutputRangeObject` with a base range
530  * of type `R` that accepts types `E`.
531 */
532 template outputRangeObject(E...) {
533 
534     ///
535     OutputRangeObject!(R, E) outputRangeObject(R)(R range) {
536         return new OutputRangeObject!(R, E)(range);
537     }
538 }
539 
540 ///
541 @safe unittest
542 {
543      import std.array;
544      auto app = appender!(uint[])();
545      auto appWrapped = outputRangeObject!(uint, uint[])(app);
546      static assert(is(typeof(appWrapped) : OutputRange!(uint[])));
547      static assert(is(typeof(appWrapped) : OutputRange!(uint)));
548 }
549 
550 /// Thrown when an interface method is not supported by the wrapped range
551 class UnsupportedRangeMethod : Exception
552 {
553     import std.exception : basicExceptionCtors;
554 
555     mixin basicExceptionCtors;
556 }
557 
558 @system unittest
559 {
560     import std.algorithm.comparison : equal;
561     import std.array;
562     import std.internal.test.dummyrange;
563 
564     static void testEquality(R)(iInputRange r1, R r2) {
565         assert(equal(r1, r2));
566     }
567 
568     auto arr = [1,2,3,4];
569     RandomFiniteAssignable!int arrWrapped = inputRangeObject(arr);
570     static assert(isRandomAccessRange!(typeof(arrWrapped)));
571     //    static assert(hasSlicing!(typeof(arrWrapped)));
572     static assert(hasLength!(typeof(arrWrapped)));
573     arrWrapped[0] = 0;
574     assert(arr[0] == 0);
575     assert(arr.moveFront() == 0);
576     assert(arr.moveBack() == 4);
577     assert(arr.moveAt(1) == 2);
578 
579     foreach (elem; arrWrapped) {}
580     foreach (i, elem; arrWrapped) {}
581 
582     assert(inputRangeObject(arrWrapped) is arrWrapped);
583 
584     foreach (DummyType; AllDummyRanges)
585     {
586         auto d = DummyType.init;
587         static assert(propagatesRangeType!(DummyType,
588                         typeof(inputRangeObject(d))));
589         static assert(propagatesRangeType!(DummyType,
590                         MostDerivedInputRange!DummyType));
591         InputRange!uint wrapped = inputRangeObject(d);
592         assert(equal(wrapped, d));
593     }
594 
595     // Test output range stuff.
596     auto app = appender!(uint[])();
597     auto appWrapped = outputRangeObject!(uint, uint[])(app);
598     static assert(is(typeof(appWrapped) : OutputRange!(uint[])));
599     static assert(is(typeof(appWrapped) : OutputRange!(uint)));
600 
601     appWrapped.put(1);
602     appWrapped.put([2, 3]);
603     assert(app.data.length == 3);
604     assert(equal(app.data, [1,2,3]));
605 }
606 
607 // https://issues.dlang.org/show_bug.cgi?id=19544
608 @safe unittest
609 {
610     import std.range : repeat;
611 
612     static struct HasCC
613     {
614         inout this(ref inout typeof(this)) {}
615     }
616 
617     auto r = repeat(HasCC.init).inputRangeObject;
618 }