[Bug libstdc++/64814] New: std::copy_n advances InputIterator one *less* time than necessary.

[Bug libstdc++/64814] New: std::copy_n advances InputIterator one *less* time than necessary.

[alex-j-a at hotmail dot co.uk]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64814

            Bug ID: 64814
           Summary: std::copy_n advances InputIterator one *less* time
                    than necessary.
           Product: gcc
           Version: 4.9.2
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: alex-j-a at hotmail dot co.uk

Bug 50119 is related. The issue should be clear from the example below; I've
confirmed the output on several web-based compilers (I'm using a chromebook in
standard config) all of which claim to use GCC. 

minimal failing example:
#include <iostream>
#include <sstream>
#include <algorithm>
#include <iterator>
#include <string>

int main() {
    std::istringstream ss("123456789012");
    std::string output;

    auto readIter = std::istreambuf_iterator<char>(ss);
    for (int i = 0; i < 3; ++i) {
        output.clear();
        auto inserter = std::back_inserter(output);
        // Works - outputs 123456789012
        //for (int j = 0; j < 4; ++j)
        //    *inserter++ = *readIter++;

        // Doesn't work - outputs 123445677890
        std::copy_n(readIter, 4, inserter);

        std::cout << output;
    }
}

The following works perfectly as a drop-in replacement from my tests:
template <typename InputIt, typename SizeT, typename OutputIt>
OutputIt copy_n(InputIt first, SizeT count, OutputIt result) {
    for (; count > 0; --count)
        *result++ = *first++;
    return result;
}

[Bug libstdc++/64814] std::copy_n advances InputIterator one *less* time than necessary.

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64814

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|major                       |normal

[Bug libstdc++/64814] std::copy_n advances InputIterator one *less* time than necessary.

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64814

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I think the behaviour you're seeing is correct (and Clang gives the same
result). The problem is that increments to the input iterator happen inside the
copy_n call, to a copy of the iterator not to readIter itself. This means it is
not equivalent to your for (int j = 0; j < 4; ++j) loop which operates directly
on readIter.

Each time through the outer loop the readIter variable has not been
incremented, so has not cached the next element from the input stream.

[Bug libstdc++/64814] std::copy_n advances InputIterator one *less* time than necessary.

[alex-j-a at hotmail dot co.uk]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64814

--- Comment #2 from Anquietas <alex-j-a at hotmail dot co.uk> ---
(In reply to Jonathan Wakely from comment #1)
> The problem is that increments to the input iterator happen inside
> the copy_n call, to a copy of the iterator not to readIter itself.
The copy_n implementation I provided produces the same behaviour as the for
loop, even with copying the iterator.

[Bug libstdc++/64814] std::copy_n advances InputIterator one *less* time than necessary.

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64814

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Actually it's nothing to do with operating on a copy of the iterator, it's due
to this in the implementation of copy_n:

    if (--__n  > 0)
      ++__first;

So as you observe we don't increment the input iterator on the last step.
However, I don't see any requirement in the standard that says we're supposed
to do so. All that is required is n assignments, there is no guarantee that the
input range is also incremented past the last element written to. So I think
you are assuming something that isn't actually guaranteed by the standard.

[Bug libstdc++/64814] std::copy_n advances InputIterator one *less* time than necessary.

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64814

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The current behaviour is decades old, coming from the copy_n in the SGI STL,
and like the standard https://www.sgi.com/tech/stl/copy_n.html says nothing
about postconditions for the input iterator.

Note http://cplusplus.github.io/LWG/lwg-active.html#2242 though.

[Bug libstdc++/64814] std::copy_n advances InputIterator one *less* time than necessary.

[alex-j-a at hotmail dot co.uk]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64814

--- Comment #5 from Anquietas <alex-j-a at hotmail dot co.uk> ---
(In reply to Jonathan Wakely from comment #3)
> However, I don't see any requirement in the standard that says we're
> supposed to do so. All that is required is n assignments, there is no
> guarantee that the input range is also incremented past the last element
> written to.
The closest thing I could find to an up to date copy of the C++11 standard:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf
copy_n is on page 851

"Effects: For each non-negative integer i < n, performs *(result + i) = *(first
+ i)."
Since it's talking about input iterators where (first + n) isn't valid I think
we can interpret this as n applications each of ++first and *first. I don't
know whether the most recent version changed the description though; perhaps if
you could provide a link?

[Bug libstdc++/64814] std::copy_n advances InputIterator one *less* time than necessary.

[alex-j-a at hotmail dot co.uk]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64814

--- Comment #6 from Anquietas <alex-j-a at hotmail dot co.uk> ---
(In reply to Anquietas from comment #5)
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf
The working copy for C++14, page 902 has the same specification as the other
PDF.

[Bug libstdc++/64814] std::copy_n advances InputIterator one *less* time than necessary.

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64814

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |INVALID

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Anquietas from comment #5)
> "Effects: For each non-negative integer i < n, performs *(result + i) =
> *(first + i)."
> Since it's talking about input iterators where (first + n) isn't valid I

See 25.1 [algorithms.general] p12.

> think we can interpret this as n applications each of ++first and *first.

No, i < n so (first+n) is not needed and only n-1 applications of ++first are
required. It is unspecified whether the algorithm increments the iterator again
after the last write, but at least two implementations do not perform that
final increment.

So I'm closing this as not a bug. If
http://cplusplus.github.io/LWG/lwg-active.html#2242 becomes a defect and
changes something we will make whatever change is needed, but I don't think we
have a bug now in libstdc++.

[Bug libstdc++/64814] std::copy_n advances InputIterator one *less* time than necessary.

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64814

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
N.B. libc++ changed its copy_n with
http://lists.cs.uiuc.edu/pipermail/cfe-commits/Week-of-Mon-20110221/039404.html
and then libstdc++ did  the same in PR 50119

[Bug libstdc++/64814] std::copy_n advances InputIterator one *less* time than necessary.

[alex-j-a at hotmail dot co.uk]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64814

--- Comment #9 from Anquietas <alex-j-a at hotmail dot co.uk> ---
(In reply to Jonathan Wakely from comment #8)
> N.B. libc++ changed its copy_n with
> http://lists.cs.uiuc.edu/pipermail/cfe-commits/Week-of-Mon-20110221/039404.
> html and then libstdc++ did  the same in PR 50119
I linked that bug report in the OP, but as it happens the behaviour is quite
interesting with std::istream_iterator<int> using an adaptation of the code I
pasted in OP:
int main() {
    std::istringstream ss("1 2 3 4 5 6 7 8 9 0 1 2 ");
    std::vector<int> output;

    auto readIter = std::istream_iterator<int>(ss);
    for (int i = 0; i < 3; ++i) {
        output.clear();
        auto inserter = std::back_inserter(output);

        // Doesn't work - outputs 123415671890
        std::copy_n(readIter, 4, inserter);

        for (auto n : output)
            std::cout << n;
    }
}

However, in this case moving readIter's declaration inside the loop fixes it.
If we go back to the code in OP and do the same, it *doesn't* fix it and still
produces the same output in either case. At the very least, the current
implementation of copy_n appears to be inconsistent, depending on the type of
iterator used. The implementation I provided for copy_n in OP doesn't work for
the istream_iterator case though, and neither does the direct for loop
approach.