www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Range of uncopyable elements

reply RazvanN <razvan.nitu1305 gmail.com> writes:
Hi,

I am trying to create a range with uncopyable elements. My 
thought process was the following:

1.I have created a struct :

struct S
{
     int a;

      disable this(this);
}

2. I declared an array :

S[] arr = [S(1), S(2), S(3)];

expecting that arr will be a range like, for example, an int[].
I was surprised to see that isInputRange!arr is false.

So, is there any possibility to create a range with uncopyable 
elements?
Dec 08 2016
parent reply Jerry <hurricane hereiam.com> writes:
The problem is with how isInputRange is defined, requires that 
front be copyable.

auto h = r.front; // can get the front of the range

https://github.com/dlang/phobos/blob/v2.072.1/std/range/primitives.d#L168

It doesn't take into consideration that front exists and that 
it's a reference to a struct that can't be copied. There was a 
discussion a while back to change it but it seems nothing came of 
it.
Dec 08 2016
parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Thu, Dec 08, 2016 at 04:35:02PM +0000, Jerry via Digitalmars-d-learn wrote:

 The problem is with how isInputRange is defined, requires that front
 be copyable.
 
 auto h = r.front; // can get the front of the range
 
 https://github.com/dlang/phobos/blob/v2.072.1/std/range/primitives.d#L168
 
 It doesn't take into consideration that front exists and that it's a
 reference to a struct that can't be copied. There was a discussion a
 while back to change it but it seems nothing came of it.


A possible workaround, which is somewhat ugly but should work, is to
have the range return pointers to the elements instead of the elements
themselves. For the most part, this should be mostly transparent because
the . operator automatically dereferences.


T

-- 
Designer clothes: how to cover less by paying more.
Dec 08 2016
parent reply Jerry <hurricane hereiam.com> writes:
On Thursday, 8 December 2016 at 16:48:07 UTC, H. S. Teoh wrote:

 On Thu, Dec 08, 2016 at 04:35:02PM +0000, Jerry via 
 Digitalmars-d-learn wrote:

 The problem is with how isInputRange is defined, requires that 
 front be copyable.
 
 auto h = r.front; // can get the front of the range
 
 https://github.com/dlang/phobos/blob/v2.072.1/std/range/primitives.d#L168
 
 It doesn't take into consideration that front exists and that 
 it's a reference to a struct that can't be copied. There was a 
 discussion a while back to change it but it seems nothing came 
 of it.


 A possible workaround, which is somewhat ugly but should work, 
 is to have the range return pointers to the elements instead of 
 the elements themselves. For the most part, this should be 
 mostly transparent because the . operator automatically 
 dereferences.


 T


It's not something that you should have to workaround, 
isInputRange is not defined properly and should be fixed. You end 
up complicating your code for no reason other than isInputRange 
is poorly defined.
Dec 08 2016
parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Thu, Dec 08, 2016 at 05:22:25PM +0000, Jerry via Digitalmars-d-learn wrote:

 On Thursday, 8 December 2016 at 16:48:07 UTC, H. S. Teoh wrote:

 On Thu, Dec 08, 2016 at 04:35:02PM +0000, Jerry via Digitalmars-d-learn
 wrote:

 The problem is with how isInputRange is defined, requires that
 front be copyable.
 
 auto h = r.front; // can get the front of the range
 
 https://github.com/dlang/phobos/blob/v2.072.1/std/range/primitives.d#L168
 
 It doesn't take into consideration that front exists and that it's
 a reference to a struct that can't be copied. There was a
 discussion a while back to change it but it seems nothing came of
 it.


 
 A possible workaround, which is somewhat ugly but should work, is to
 have the range return pointers to the elements instead of the
 elements themselves. For the most part, this should be mostly
 transparent because the . operator automatically dereferences.
 
 
 T


 
 It's not something that you should have to workaround, isInputRange is not
 defined properly and should be fixed. You end up complicating your code for
 no reason other than isInputRange is poorly defined.


The problem is that most range algorithms won't work if `auto h =
r.front;` doesn't compile.  Random chunks of std.algorithm won't work
for such a range.

One may argue, of course, that std.algorithm ought to be fixed... but
the root of the problem really is a conceptual one. The definition of a
range was made as an extension of a C++ iterator, which is basically a
wrapped pointer. So `auto h = r.front;` is assumed to be a cheap copy of
a *reference* to the underlying data, rather than copying the data
itself. This is why most of std.algorithm is written the way it is, and
why isInputRange is defined the way it is.  A range of non-copyable
elements in this sense is a poor fit for the range concept; a better fit
would be a range of references to an underlying container of
non-copyable elements. Hence my suggestion of using pointers.

(In any case, conflating a range with a container is usually a red flag
that there's a conceptual mismatch somewhere. Unfortunately built-in
arrays aren't helping by hiding the fact that the container is actually
GC-managed memory, which isn't directly visible to the user, thus
perpetuating the misconception that range == container.)


T

-- 
What did the alien say to Schubert? "Take me to your lieder."
Dec 08 2016
parent reply Jerry <hurricane hereiam.com> writes:
On Thursday, 8 December 2016 at 17:29:42 UTC, H. S. Teoh wrote:

 The problem is that most range algorithms won't work if `auto h 
 = r.front;` doesn't compile.  Random chunks of std.algorithm 
 won't work for such a range.

 One may argue, of course, that std.algorithm ought to be 
 fixed... but the root of the problem really is a conceptual 
 one. The definition of a range was made as an extension of a 
 C++ iterator, which is basically a wrapped pointer. So `auto h 
 = r.front;` is assumed to be a cheap copy of a *reference* to 
 the underlying data, rather than copying the data itself. This 
 is why most of std.algorithm is written the way it is, and why 
 isInputRange is defined the way it is.  A range of non-copyable 
 elements in this sense is a poor fit for the range concept; a 
 better fit would be a range of references to an underlying 
 container of non-copyable elements. Hence my suggestion of 
 using pointers.

 (In any case, conflating a range with a container is usually a 
 red flag that there's a conceptual mismatch somewhere. 
 Unfortunately built-in arrays aren't helping by hiding the fact 
 that the container is actually GC-managed memory, which isn't 
 directly visible to the user, thus perpetuating the 
 misconception that range == container.)


 T


Well it's exactly like that for C++ as well. std::copy(Iter, ...) 
won't compile if the values aren't copyable. There's no 
constraints in C++ either so you get some cryptic error message. 
The entire std library is like that.

Assuming that is wrong though, as you aren't copying an iterator 
or range you are copying the actual value. What you are confusing 
"auto h = r.front;" for is this: "auto rcopy = r;". The D code 
"auto h = r.front" is not a cheap operation and the equivalent in 
C++ is actually this: "auto h = *iterator;" and one should not 
assume it is cheap, cause it isn't. Anyways your comparison with 
C++ is off.
Dec 08 2016
parent reply Jonathan M Davis via Digitalmars-d-learn writes:
On Thursday, December 08, 2016 20:21:41 Jerry via Digitalmars-d-learn wrote:

 Assuming that is wrong though, as you aren't copying an iterator
 or range you are copying the actual value. What you are confusing
 "auto h = r.front;" for is this: "auto rcopy = r;". The D code
 "auto h = r.front" is not a cheap operation and the equivalent in
 C++ is actually this: "auto h = *iterator;" and one should not
 assume it is cheap, cause it isn't. Anyways your comparison with
 C++ is off.


His comparison with C++ is off, because front isn't analogous to an
iterator. It's analagous to dereferencing an iterator. However, at least as
of C++98, non-copyable elements in a container were not allowed IIRC, so it
would have been pretty rare to have a C++ iterator that returned a
non-copyable value when you dereferenced it. Also, it pretty much _is_
assumed that

auto h = r.front;

is cheap, and there are plenty of cases where calling front multiple times
for the same range would incur additional overhead, because front is
calculated rather than simply returning a value (e.g. this is what happens
with map). So, it could be a definite performance hit in general to start
insisting that r.front be called without the value being assigned somewhere.
Part of the problem here is that in some cases, it's more efficient to call
front multiple times, whereas in others it's more efficient to call it once.
But since most ranges do not have their front or back return by ref (and
many cannot), it's going to be more efficient to call front only once for
most ranges.

Also, consider that the way that foreach works, it _has_ to be able to copy
front unless it's used with ref - and since most ranges do not have a front
that returns by ref, most ranges will not compile with a ref foreach
variable, and generic code would fall completly flat on its face if it tried
to use foreach with a range and made the foreach variable ref, whereas
that's exactly what would be required for a range of non-copyable elements.
Even if it were allowed, a range of non-copyable elements would not play
nicely with the same code that a normal range would work with, resulting in
a lot more conditional compilation from stuff like function overloading and
static ifs in order to make the code work for both. So, allowing ranges of
non-copyable types would tend to complicate code considerably - either that
or a lot of template constraints would just do something like
hasCopyableFront!R, making it so that ranges of non-copyable elements still
really didn't work.

Yes, not allowing copyable elements for ranges is a problem. But allowing
them would also be a big problem.

What we should ultimately do about it, I don't know, but I think that it's
pretty clear that the majority of code would be better off if non-copyable
elements for ranges were not allowed. And it _is_ possible to work around
the problem by doing as H.S. Teoh suggested and using ranges of pointers.

- Jonathan M Davis
Dec 08 2016
parent reply Jerry <hurricane hereiam.com> writes:
On Thursday, 8 December 2016 at 21:46:26 UTC, Jonathan M Davis 
wrote:

 However, at least as of C++98, non-copyable elements in a
 container were not allowed IIRC, so it would have been pretty
 rare to have a C++ iterator that returned a non-copyable value
 when you dereferenced it.


Even if it was uncommon, i doubt anyone actually made a copy of 
the dereferenced iterator.
There were also no restrictions in place that every algorithm 
needed it to be copyable, only the ones that actually needed it.
In the case of C++, dereferencing an iterator was basically free.
As an iterator was essentially a pointer and there were no 
special iterators.


 Also, it pretty much _is_ assumed that

 auto h = r.front;

 is cheap, and there are plenty of cases where calling front
 multiple times for the same range would incur additional
 overhead, because front is calculated rather than simply
 returning a value (e.g. this is what happens with map).
 So, it could be a definite performance hit in general to start
 insisting that r.front be called without the value being
 assigned somewhere.


No one suggested calling front multiple times as a fix. Part of 
the problem with D is an old one and one that comes up often.
There are no rvalue references. This means it's a pain in the ass 
to write generic code. There's no easy way to write code that
will work for both references and values.

As an example you can write the following in C++:

     int  foo0() { return 10; }
     int& foo1() { static int i; return i; }

     const int& a = foo0(); // a copy is made on the stack, this 
ref points to it
     const int& b = foo1(); // this ref points to the global 
variable in foo1()

in D:

     int     foo0() { ... }
     ref int foo1() { ... }

     auto a = foo0();  // a copy is made
     auto b = foo1();  // a copy is made
     auto c = &foo1(); // need to write different code to get the 
result we want

     void callback(ref int);

     callback(a); // ok
     callback(b); // ok
     callback(c); // nope

The problem lies with D's inability to write generic code that 
works in boths instances. This means writing the same code twice
in some instances, or just not supporting one of the methods.



 Yes, not allowing copyable elements for ranges is a problem.
 But allowing them would also be a big problem.


Not if one of the biggest and most reoccurring complaints with D 
was fixed.


 What we should ultimately do about it, I don't know, but I
 think that it's pretty clear that the majority of code would be
 better off if non-copyable elements for ranges were not
 allowed. And it _is_ possible to work around the problem by
 doing as H.S. Teoh suggested and using ranges of pointers.


I don't think so. There's a lot of functions that work with 
non-copyable
elements. Without modifying any code, the only blockage is caused 
by isInputRange.
Oh well, custom build of phobos it is.
Dec 08 2016
parent reply Jonathan M Davis via Digitalmars-d-learn writes:
On Thursday, December 08, 2016 22:32:47 Jerry via Digitalmars-d-learn wrote:

 On Thursday, 8 December 2016 at 21:46:26 UTC, Jonathan M Davis

 wrote:

 However, at least as of C++98, non-copyable elements in a
 container were not allowed IIRC, so it would have been pretty
 rare to have a C++ iterator that returned a non-copyable value
 when you dereferenced it.


 Even if it was uncommon, i doubt anyone actually made a copy of
 the dereferenced iterator.


I've seen that in C++ code all the time, especially if you're dealing with
smart pointers, because otherwise you have to do stuff like (*iter)->foo()
instead of just var->foo().


 There were also no restrictions in place that every algorithm
 needed it to be copyable, only the ones that actually needed it.
 In the case of C++, dereferencing an iterator was basically free.
 As an iterator was essentially a pointer and there were no
 special iterators.


Except that C++ _does_ have special iterators. They're just not as common.


 As an example you can write the following in C++:

      int  foo0() { return 10; }
      int& foo1() { static int i; return i; }

      const int& a = foo0(); // a copy is made on the stack, this
 ref points to it
      const int& b = foo1(); // this ref points to the global
 variable in foo1()



 Yes, not allowing copyable elements for ranges is a problem.
 But allowing them would also be a big problem.


 Not if one of the biggest and most reoccurring complaints with D
 was fixed.


With the upcoming improvements to  safe and return ref, it _might_ happen
that there will be a way for a function to accept rvalues by ref. Andrei has
indicated that a really good proposal might be accepted. But that's a
separate issue from having ref on local variables, which is what would be
required for what you're suggesting, and both Walter and Andrei have been
adamant that that is not worth it - even without getting rvalue references
into the mix. I don't know that it would be impossible to convince them
otherwise, but I would be _very_ surprised if anyone managed to talk them
into it.

And for the most part, with ranges, this is pretty much a non-issue. It does
become an issue when you start worrying about ranges with a non-copyable
front, but this is literally only the second or third thread that I have
ever seen where anyone complained about it. Much as it is annoying when
someone runs int ito, it's not a big complaint that folks have. And given
how much of a pain it would be to deal with in general, I seriously question
that it's worth it - especially when simply using pointers fixes the
problem.

- Jonathan M Davis
Dec 08 2016
parent Jerry <hurricane hereiam.com> writes:
On Thursday, 8 December 2016 at 23:08:35 UTC, Jonathan M Davis 
wrote:

 I've seen that in C++ code all the time, especially if you're 
 dealing with
 smart pointers, because otherwise you have to do stuff like 
 (*iter)->foo()
 instead of just var->foo().


Smart pointers weren't introduced until C++11. I'm talking about 
std library code that would have to be generic. Not user code 
where the type in the iterator is known.



 Except that C++ _does_ have special iterators. They're just not 
 as common.


Still not as common and C++ has a way to


 With the upcoming improvements to  safe and return ref, it 
 _might_ happen that there will be a way for a function to 
 accept rvalues by ref. Andrei has indicated that a really good 
 proposal might be accepted. But that's a separate issue from 
 having ref on local variables, which is what would be required 
 for what you're suggesting, and both Walter and Andrei have 
 been adamant that that is not worth it - even without getting 
 rvalue references into the mix. I don't know that it would be 
 impossible to convince them otherwise, but I would be _very_ 
 surprised if anyone managed to talk them into it.


Exactly, the problem will continue to persist even if rvalue 
references are included into D. It's not well thought out, 
isInputRange reflects that.


 And for the most part, with ranges, this is pretty much a 
 non-issue. It does become an issue when you start worrying 
 about ranges with a non-copyable front, but this is literally 
 only the second or third thread that I have ever seen where 
 anyone complained about it. Much as it is annoying when someone 
 runs int ito, it's not a big complaint that folks have. And 
 given how much of a pain it would be to deal with in general, I 
 seriously question that it's worth it - especially when simply 
 using pointers fixes the problem.


That's not an acceptable workaround. It complicates code for no 
reason. If that's the decision that is going to be accepted. Then 
there should be helper functions included in the standard to 
reflect that.
Dec 09 2016