Input range -> take -> filter -> chain: Take gets applied *after* filter

[dlangBugzillaToGithub]

qigezx+dc40d6nao940k reported this on 2024-09-20T13:14:28Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=24775

Description

InputRange.take(n).filter.chain logically transforms it into InputRange.filter.take(n-1).chain and thus takes the wrong number of elements

Example:
----
import std.stdio;
import std.algorithm;
import std.range;

auto inputRangeFactory(){
	int i = 0;
	int gen(){
		return i++;
	}
	return generate!gen();
}

void main(){

	// [10, 11, 12, 13, 14, 15, 16, 17, 18, 100]
	inputRangeFactory.take(10).filter!"a>8".chain(only(100)).writeln;
	
	// Unless filter would discard all taken elements
	// [100]
	inputRangeFactory.take(10).filter!"a>9".chain(only(100)).writeln;
	
	// Adding "array" somewhere in the middle fixes it
	// [9,100]
	inputRangeFactory.take(10).array.filter!"a>8".chain(only(100)).writeln;
	inputRangeFactory.take(10).filter!"a>8".array.chain(only(100)).writeln;
}
------

$ dmd --version
DMD64 D Compiler v2.109.1

Copyright (C) 1999-2024 by The D Language Foundation, All Rights Reserved written by Walter Bright

[0xEAB]

AFAICT this is a value vs. reference semantics issue.

import std.algorithm;
import std.range;
import std.stdio;

struct Range
{
	private int i;

	enum bool empty = false;
	int front() => i;
	void popFront() { ++i; }
}

void main()
{
	writeln(     Range() .take(10).filter!"a>8".chain(only(100)));
	writeln((new Range()).take(10).filter!"a>8".chain(only(100)));
}

[9, 100]
[9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 100]

[0xEAB]

import std.algorithm;
import std.range;
import std.stdio;

struct Range
{
	private int i = 0;

	enum bool empty = false;
	int front() => i;
	void popFront() { ++i; }
}

void main()
{
	writeln(chain(
		(new Range()).take(2).filter!"a > 0",
		(new Range()).take(2).filter!"a > 0",
	));
}

[1, 2, 1]