1 /**
2    Better versions of Phobos's template contraints that emit
3    error messages when they fail
4    Can be used with concepts.models.models
5  */
6 module concepts.range;
7 
8 import std.range.primitives: front, popFront, empty, put, save, back, popBack;
9 
10 
11 void checkInputRange(R)(inout int = 0) {
12     R r = R.init;     // can define a range object
13     if (r.empty) {}   // can test for empty
14     r.popFront;       // can invoke popFront()
15     auto h = r.front; // can get the front of the range
16 }
17 
18 /**
19 Returns $(D true) if $(D R) is an input range. An input range must
20 define the primitives $(D empty), $(D popFront), and $(D front). The
21 following code should compile for any input range.
22 
23 ----
24 R r;              // can define a range object
25 if (r.empty) {}   // can test for empty
26 r.popFront();     // can invoke popFront()
27 auto h = r.front; // can get the front of the range of non-void type
28 ----
29 
30 The following are rules of input ranges are assumed to hold true in all
31 Phobos code. These rules are not checkable at compile-time, so not conforming
32 to these rules when writing ranges or range based code will result in
33 undefined behavior.
34 
35 $(UL
36     $(LI `r.empty` returns `false` if and only if there is more data
37     available in the range.)
38     $(LI `r.empty` evaluated multiple times, without calling
39     `r.popFront`, or otherwise mutating the range object or the
40     underlying data, yields the same result for every evaluation.)
41     $(LI `r.front` returns the current element in the range.
42     It may return by value or by reference.)
43     $(LI `r.front` can be legally evaluated if and only if evaluating
44     `r.empty` has, or would have, equaled `false`.)
45     $(LI `r.front` evaluated multiple times, without calling
46     `r.popFront`, or otherwise mutating the range object or the
47     underlying data, yields the same result for every evaluation.)
48     $(LI `r.popFront` advances to the next element in the range.)
49     $(LI `r.popFront` can be called if and only if evaluating `r.empty`
50     has, or would have, equaled `false`.)
51 )
52 
53 Also, note that Phobos code assumes that the primitives `r.front` and
54 `r.empty` are $(BIGOH 1) time complexity wise or "cheap" in terms of
55 running time. $(BIGOH) statements in the documentation of range functions
56 are made with this assumption.
57 
58 Params:
59     R = type to be tested
60 
61 Returns:
62     true if R is an InputRange, false if not
63  */
64 enum isInputRange(R) = is(typeof(checkInputRange!R));
65 
66 ///
67 @safe pure unittest {
68 
69     import concepts.models: models;
70 
71     struct A {}
72     struct B
73     {
74         void popFront();
75         @property bool empty();
76         @property int front();
77     }
78     static assert(!isInputRange!A);
79     static assert( isInputRange!B);
80     static assert( isInputRange!(int[]));
81     static assert( isInputRange!(char[]));
82     static assert(!isInputRange!(char[4]));
83     static assert( isInputRange!(inout(int)[]));
84 }
85 
86 void checkOutputRange(R, E)(inout int = 0) {
87     R r = R.init;
88     E e = E.init;
89     put(r, e);
90 }
91 
92 
93 /++
94 Returns $(D true) if $(D R) is an output range for elements of type
95 $(D E). An output range is defined functionally as a range that
96 supports the operation $(D put(r, e)) as defined above.
97  +/
98 enum isOutputRange(R, E) = is(typeof(checkOutputRange!(R, E)));
99 
100 
101 ///
102 @safe pure unittest
103 {
104     void myprint(in char[] s) { }
105     static assert(isOutputRange!(typeof(&myprint), char));
106 
107     static assert(!isOutputRange!(char[], char));
108     static assert( isOutputRange!(dchar[], wchar));
109     static assert( isOutputRange!(dchar[], dchar));
110 }
111 
112 @safe pure unittest
113 {
114     import std.array;
115     import std.stdio : writeln;
116 
117     auto app = appender!string();
118     string s;
119     static assert( isOutputRange!(Appender!string, string));
120     static assert( isOutputRange!(Appender!string*, string));
121     static assert(!isOutputRange!(Appender!string, int));
122     static assert(!isOutputRange!(wchar[], wchar));
123     static assert( isOutputRange!(dchar[], char));
124     static assert( isOutputRange!(dchar[], string));
125     static assert( isOutputRange!(dchar[], wstring));
126     static assert( isOutputRange!(dchar[], dstring));
127 
128     static assert(!isOutputRange!(const(int)[], int));
129     static assert(!isOutputRange!(inout(int)[], int));
130 }
131 
132 
133 void checkForwardRange(R)(inout int = 0) {
134 
135     checkInputRange!R;
136 
137     R r1 = R.init;
138     // NOTE: we cannot check typeof(r1.save) directly
139     // because typeof may not check the right type there, and
140     // because we want to ensure the range can be copied.
141     auto s1 = r1.save;
142     static assert (is(typeof(s1) == R));
143 }
144 
145 
146 /**
147 Returns $(D true) if $(D R) is a forward range. A forward range is an
148 input range $(D r) that can save "checkpoints" by saving $(D r.save)
149 to another value of type $(D R). Notable examples of input ranges that
150 are $(I not) forward ranges are file/socket ranges; copying such a
151 range will not save the position in the stream, and they most likely
152 reuse an internal buffer as the entire stream does not sit in
153 memory. Subsequently, advancing either the original or the copy will
154 advance the stream, so the copies are not independent.
155 
156 The following code should compile for any forward range.
157 
158 ----
159 static assert(isInputRange!R);
160 R r1;
161 auto s1 = r1.save;
162 static assert (is(typeof(s1) == R));
163 ----
164 
165 Saving a range is not duplicating it; in the example above, $(D r1)
166 and $(D r2) still refer to the same underlying data. They just
167 navigate that data independently.
168 
169 The semantics of a forward range (not checkable during compilation)
170 are the same as for an input range, with the additional requirement
171 that backtracking must be possible by saving a copy of the range
172 object with $(D save) and using it later.
173  */
174 enum isForwardRange(R) = is(typeof(checkForwardRange!R));
175 
176 ///
177 @safe pure unittest
178 {
179     static assert(!isForwardRange!(int));
180     static assert( isForwardRange!(int[]));
181     static assert( isForwardRange!(inout(int)[]));
182 }
183 
184 @("BUG 14544")
185 @safe pure unittest
186 {
187     import concepts.models: models;
188 
189     @models!(R14544, isForwardRange)
190     struct R14544
191     {
192         int front() { return 0;}
193         void popFront() {}
194         bool empty() { return false; }
195         R14544 save() {return this;}
196     }
197 
198     static assert(isForwardRange!R14544);
199 }
200 
201 
202 void checkBidirectionalRange(R)(inout int = 0) {
203     R r = R.init;
204     r.popBack;
205     auto t = r.back;
206     auto w = r.front;
207     static assert(is(typeof(t) == typeof(w)));
208 }
209 
210 /**
211 Returns $(D true) if $(D R) is a bidirectional range. A bidirectional
212 range is a forward range that also offers the primitives $(D back) and
213 $(D popBack). The following code should compile for any bidirectional
214 range.
215 
216 The semantics of a bidirectional range (not checkable during
217 compilation) are assumed to be the following ($(D r) is an object of
218 type $(D R)):
219 
220 $(UL $(LI $(D r.back) returns (possibly a reference to) the last
221 element in the range. Calling $(D r.back) is allowed only if calling
222 $(D r.empty) has, or would have, returned $(D false).))
223  */
224 enum isBidirectionalRange(R) = is(typeof(checkBidirectionalRange!R));
225 
226 ///
227 @safe pure unittest
228 {
229     alias R = int[];
230     R r = [0,1];
231     static assert(isForwardRange!R);           // is forward range
232     r.popBack();                               // can invoke popBack
233     auto t = r.back;                           // can get the back of the range
234     auto w = r.front;
235     static assert(is(typeof(t) == typeof(w))); // same type for front and back
236 }
237 
238 @safe pure unittest
239 {
240     struct A {}
241     struct B
242     {
243         void popFront();
244         @property bool empty();
245         @property int front();
246     }
247     struct C
248     {
249         @property bool empty();
250         @property C save();
251         void popFront();
252         @property int front();
253         void popBack();
254         @property int back();
255     }
256     static assert(!isBidirectionalRange!(A));
257     static assert(!isBidirectionalRange!(B));
258     static assert( isBidirectionalRange!(C));
259     static assert( isBidirectionalRange!(int[]));
260     static assert( isBidirectionalRange!(char[]));
261     static assert( isBidirectionalRange!(inout(int)[]));
262 }
263 
264 void checkRandomAccessRange(R)(inout int = 0) {
265 
266     import std.traits: isNarrowString;
267     import std.range: hasLength, isInfinite;
268 
269     if(isBidirectionalRange!R) checkBidirectionalRange!R;
270     if(isForwardRange!R) checkForwardRange!R;
271 
272     static assert(isBidirectionalRange!R ||
273                   isForwardRange!R && isInfinite!R);
274     R r = R.init;
275     auto e = r[1];
276     auto f = r.front;
277     static assert(is(typeof(e) == typeof(f)));
278     static assert(!isNarrowString!R);
279     static assert(hasLength!R || isInfinite!R);
280 
281     static if (is(typeof(r[$])))
282     {
283         static assert(is(typeof(f) == typeof(r[$])));
284 
285         static if (!isInfinite!R)
286             static assert(is(typeof(f) == typeof(r[$ - 1])));
287     }
288 }
289 
290 
291 /**
292 Returns $(D true) if $(D R) is a random-access range. A random-access
293 range is a bidirectional range that also offers the primitive $(D
294 opIndex), OR an infinite forward range that offers $(D opIndex). In
295 either case, the range must either offer $(D length) or be
296 infinite. The following code should compile for any random-access
297 range.
298 
299 The semantics of a random-access range (not checkable during
300 compilation) are assumed to be the following ($(D r) is an object of
301 type $(D R)): $(UL $(LI $(D r.opIndex(n)) returns a reference to the
302 $(D n)th element in the range.))
303 
304 Although $(D char[]) and $(D wchar[]) (as well as their qualified
305 versions including $(D string) and $(D wstring)) are arrays, $(D
306 isRandomAccessRange) yields $(D false) for them because they use
307 variable-length encodings (UTF-8 and UTF-16 respectively). These types
308 are bidirectional ranges only.
309  */
310 enum isRandomAccessRange(R) = is(typeof(checkRandomAccessRange!R));
311 
312 ///
313 @safe pure unittest
314 {
315     import std.traits : isNarrowString;
316     import std.range: isInfinite, hasLength;
317 
318     alias R = int[];
319 
320     // range is finite and bidirectional or infinite and forward.
321     static assert(isBidirectionalRange!R ||
322                   isForwardRange!R && isInfinite!R);
323 
324     R r = [0,1];
325     auto e = r[1]; // can index
326     auto f = r.front;
327     static assert(is(typeof(e) == typeof(f))); // same type for indexed and front
328     static assert(!isNarrowString!R); // narrow strings cannot be indexed as ranges
329     static assert(hasLength!R || isInfinite!R); // must have length or be infinite
330 
331     // $ must work as it does with arrays if opIndex works with $
332     static if (is(typeof(r[$])))
333     {
334         static assert(is(typeof(f) == typeof(r[$])));
335 
336         // $ - 1 doesn't make sense with infinite ranges but needs to work
337         // with finite ones.
338         static if (!isInfinite!R)
339             static assert(is(typeof(f) == typeof(r[$ - 1])));
340     }
341 }
342 
343 @safe pure unittest
344 {
345     import concepts.models: models;
346 
347     struct A {}
348     struct B
349     {
350         void popFront();
351         @property bool empty();
352         @property int front();
353     }
354     struct C
355     {
356         void popFront();
357         @property bool empty();
358         @property int front();
359         void popBack();
360         @property int back();
361     }
362 
363     @models!(D, isRandomAccessRange)
364     struct D
365     {
366         @property bool empty();
367         @property D save();
368         @property int front();
369         void popFront();
370         @property int back();
371         void popBack();
372         ref int opIndex(uint);
373         @property size_t length();
374         alias opDollar = length;
375         //int opSlice(uint, uint);
376     }
377     struct E
378     {
379         bool empty();
380         E save();
381         int front();
382         void popFront();
383         int back();
384         void popBack();
385         ref int opIndex(uint);
386         size_t length();
387         alias opDollar = length;
388         //int opSlice(uint, uint);
389     }
390     static assert(!isRandomAccessRange!(A));
391     static assert(!isRandomAccessRange!(B));
392     static assert(!isRandomAccessRange!(C));
393     static assert( isRandomAccessRange!(D));
394     static assert( isRandomAccessRange!(E));
395     static assert( isRandomAccessRange!(int[]));
396     static assert( isRandomAccessRange!(inout(int)[]));
397 }
398 
399 @safe pure unittest
400 {
401     // Test fix for bug 6935.
402     struct R
403     {
404         @disable this();
405 
406         @property bool empty() const { return false; }
407         @property int front() const { return 0; }
408         void popFront() {}
409 
410         @property R save() { return this; }
411 
412         @property int back() const { return 0; }
413         void popBack(){}
414 
415         int opIndex(size_t n) const { return 0; }
416         @property size_t length() const { return 0; }
417         alias opDollar = length;
418 
419         void put(int e){  }
420     }
421     static assert(isInputRange!R);
422     static assert(isForwardRange!R);
423     static assert(isBidirectionalRange!R);
424     static assert(isRandomAccessRange!R);
425     static assert(isOutputRange!(R, int));
426 }