protocol for using InputRanges

[Rainer Schuetze]

On 27.03.2014 03:48, Walter Bright wrote:
> On 3/26/2014 7:19 PM, Steven Schveighoffer wrote:
>> if(!r.empty)
>> {
>>     auto r2 = map!(x => x * 2)(r);
>>     do
>>     {
>>        auto x = r2.front;
>>        ...
>>     } while(!r2.empty);
>> }
>>
>> Should we be required to re-verify that r2 is not empty before using
>> it? It
>> clearly is not, and would be an artificial requirement (one that map
>> likely
>> would not enforce!).
>>
>> This sounds so much like a convention that simply won't be followed,
>> and the
>> result will be perfectly valid code.
>
> The idea is that there are three functions: empty, front, and popFront.
> The functionality of the range will be distributed between these 3
> functions. Different things being ranged over will naturally split their
> operations into the 3 functions in different ways.
>
> If the 3 functions can be called in any order, then extra logic has to
> be added to them to signal to each other. This slows things down.
>
> To write generic code calling ranges, it's necessary to stop assuming
> what is happening under the hood of empty, front, and popFront, and
> stick to the protocol.
>

IIUC what you are proposing would be covered better by removing front 
and return the value by popFront.

Instead of forcing strong, breaking and sometimes unintuitive semantics 
we could also improve dmd's optimizer. This caching range example:

///////////////////////////////////
T getc(T)();

struct irange(T)
{
   bool _cached;
   T _cache;

   this(T[] arr) { _cached = false; }
   bool empty() {
     if(_cached) return false;
     _cache = getc!T();
     return (_cache < 0);
   }
   T front() { empty(); return _cache; }
   void popFront() { _cached = false; }
}

int foo(irange!int rg)
{
   int sum = 0;
   while(!rg.empty)
   {
     sum += rg.front;
   	rg.popFront;
   }
   return sum;
}
///////////////////////////////////

generates this code with "dmd2.065 -O -inline -release -noboundscheck -m64":

_D7irange23fooFS7irange213__T6irangeTiZ6irangeZi:
   0000: push        rbp
   0001: mov         rbp,rsp
   0004: push        rax
   0005: push        rsi
   0006: mov         qword ptr [rbp+10h],rcx
   000A: xor         esi,esi
   000C: lea         rcx,[rbp+10h]
   0010: sub         rsp,20h
   0014: call        _D7irange213__T6irangeTiZ6irange5emptyMFZb
   0019: add         rsp,20h
   001D: xor         al,1
   001F: je          0050
   0021: lea         rcx,[rbp+10h]
   0025: sub         rsp,20h
   0029: call        _D7irange213__T6irangeTiZ6irange5emptyMFZb
   002E: add         rsp,20h
   0032: mov         eax,dword ptr [rbp+14h]
   0035: add         esi,eax
   0037: mov         byte ptr [rbp+10h],0
   003B: lea         rcx,[rbp+10h]
   003F: sub         rsp,20h
   0043: call        _D7irange213__T6irangeTiZ6irange5emptyMFZb
   0048: add         rsp,20h
   004C: xor         al,1
   004E: jne         0021
   0050: mov         eax,esi
   0052: pop         rsi
   0053: lea         rsp,[rbp]
   0057: pop         rbp
   0058: ret

_D7irange213__T6irangeTiZ6irange5emptyMFZb:
   0000: push        rbp
   0001: mov         rbp,rsp
   0004: mov         qword ptr [rbp+10h],rcx
   0008: cmp         byte ptr [rcx],0
   000B: je          0011
   000D: xor         eax,eax
   000F: pop         rbp
   0010: ret
   0011: sub         rsp,20h
   0015: call        _D7irange211__T4getcTiZ4getcFZi
   001A: add         rsp,20h
   001E: mov         rcx,qword ptr [rbp+10h]
   0022: mov         dword ptr [rcx+4],eax
   0025: shr         eax,1Fh
   0028: mov         byte ptr [rcx],al
   002A: xor         al,1
   002C: pop         rbp
   002D: ret

and this with gdc (-O2 on godbolt.org):

int example.foo(example.irange!(int).irange):
	mov	rax, rdi
	push	rbx
	xor	ebx, ebx
	shr	rax, 32
	test	dil, dil
	je	.L5
.L2:
	add	ebx, eax
.L5:
	call	int example.getc!(int).getc()
	test	eax, eax
	js	.L2
	mov	eax, ebx
	pop	rbx
	ret

All traces of the caching but the initial state check have been removed, 
no extra calls.