iterator_base advertises forward_iterator_tag but violates the multi-pass guarantee

[ec36339]

Summary

YAML::Node's iterator declares iterator_category = std::forward_iterator_tag but does not satisfy the semantic multi-pass guarantee required by std::forward_iterator (iterator.concept.forward). This causes silent incorrect behaviour when the iterator is used with C++20 <ranges> machinery, which trusts the declared category.

---

What the standard requires

std::forward_iterator requires the multi-pass guarantee: if a == b, then *a and *b must refer to the same object. This is a semantic requirement; there is no compile-time concept check that enforces it.

std::views::transform and other range adapters propagate the iterator category from the underlying range. If a range claims to be a forward_range, the resulting view also claims to be one. Code downstream that relies on multi-pass behaviour then has formally undefined behaviour.

---

Reproduction

#include <yaml-cpp/yaml.h>
#include <gtest/gtest.h>
#include <memory>
#include <forward_list>

// Syntactic check passes -- concepts only see iterator_category, not semantics.
static_assert(std::ranges::forward_range<YAML::Node>);

// FAILS at runtime: two copies of the same iterator dereference to distinct objects.
// std::forward_iterator requires *a and *b to refer to the same object when a == b.
// https://en.cppreference.com/w/cpp/iterator/forward_iterator
TEST(YamlCppMapIterator, DereferenceOperator_WithEqualIteratorCopies_ReturnsSameObject)
{
    YAML::Node node = YAML::Load("{key: value}");
    auto it_a = node.begin();
    auto it_b = node.begin();
    ASSERT_EQ(it_a, it_b);

    const auto& ref_a = *it_a;
    const auto& ref_b = *it_b;

    EXPECT_EQ(std::addressof(ref_a), std::addressof(ref_b)); // FAILS
}

// Control: std::forward_list::iterator is a true forward iterator.
// operator*() returns int& -- a stable reference to the stored node.
// https://en.cppreference.com/w/cpp/container/forward_list
TEST(ForwardListIterator, DereferenceOperator_WithEqualIteratorCopies_ReturnsSameObject)
{
    std::forward_list<int> list = {42};
    auto it_a = list.begin();
    auto it_b = list.begin();
    ASSERT_EQ(it_a, it_b);

    const auto& ref_a = *it_a;
    const auto& ref_b = *it_b;

    EXPECT_EQ(std::addressof(ref_a), std::addressof(ref_b)); // PASSES
}

Observed output from the yaml-cpp test:

Expected equality of these values:
  std::addressof(ref_a)  Which is: 000000D0A4B9EC50
  std::addressof(ref_b)  Which is: 000000D0A4B9ED50

The addresses differ -- each iterator copy holds its own iterator_value member, and operator*() returns it by value, materialising a new temporary per call.

---

Root cause

iterator_base<V>::operator*() (iterator.h) returns value_type by value:

value_type operator*() const
{
    // constructs and returns a new iterator_value every call
}

YAML::Node is a shallow-copying reference handle, not a value type. Each dereference constructs a new iterator_value{Node first; Node second;} wrapping the same underlying ref-counted data but at a new address. Two copies of the same iterator therefore dereference to two distinct C++ objects, violating [iterator.concept.forward]/6.

This is also related to #1326 (value_type being const-qualified), which is a separate but symptomatically similar violation of std::indirectly_readable.

---

Why this is a bug and not a design choice

Prior to C++20, iterator_category tags were advisory. In C++20, std::forward_iterator is a formal concept with normative semantic requirements. Code using std::views::transform or other range adapters on a YAML::Node will produce a forward_range view based on a false premise. Any algorithm that exploits multi-pass behaviour on that view has formally undefined behaviour, even if it happens to work in practice in a trivial single-pass use.

---

Proposed fixes

Option A (recommended): Change iterator_category to input_iterator_tag
The iterator is semantically an input iterator. Declaring it as such is honest and correct. Single-pass range-for loops and std::views::transform all work on input ranges. This is a breaking change for callers that pass the iterator to algorithms requiring ForwardIterator, but those callers already have latent UB.

Option B: Return a stable reference from operator*()
Store the current iterator_value inside the iterator as a member and return iterator_value&. However, since two equal iterators are independent copies each holding their own member, they still dereference to different objects. This does not fix the multi-pass violation and adds overhead.

Option C: Shared materialised state
All copies of the same logical iterator position share ownership of a single heap-allocated iterator_value. Satisfies the multi-pass guarantee mechanically, but adds allocation overhead and complicates copy semantics.

Option D (consuming-code workaround): Wrapper that re-declares input_iterator_tag
Users can wrap YAML::Node's iterator in a thin adapter that overrides iterator_category to input_iterator_tag. This is a local fix that does not require yaml-cpp changes, at the cost of boilerplate per use site.

---

Disclaimer: this bug was found by an AI coding tool (GitHub Copilot), with the assistance and review of a real human. This report was posted at the direct request of that human. The account posting this report is owned and operated by a real person.

[ec36339]

Confirming that I am a real person, and that I posted this bug because I am personally using this library and ran into this issue. While I could have written the bug report myself, I am happy with the way the AI wrote it, and I couldn't have written it better myself. I also explicitly asked for the unit tests, because I do not trust AI reasoning. I know how C++20 ranges and iterator concepts work, which is why I care. :)

[SGSSGene]

Hi @ec36339
Thank you for your input.

I am not convinced the explanation from your AI is correct. Specifically the claim std::forward_iterator requires the multi-pass guarantee: if a == b, then *a and *b must refer to the same object.

If I read the description of std::forward_iterator I do not see this claim. It also would be surprising, since value semantics for the operator* will always created different objects and this would disallow many uses of std::views::transform.

Further, I find the explicit statement:

Unlike the LegacyForwardIterator requirements, the forward_iterator concept does not require dereference to return a reference.

Here a short demonstration of a "reproduced" case that fails but fails according to your test but is valid and multi pass:

void test3()
{
    std::forward_list<int> list = {42};
    auto view = list | std::views::transform([](auto x) { return x*2; });
    auto it_a = view.begin();
    auto it_b = view.begin();
    assert(it_a == it_b);

    static_assert(std::ranges::forward_range<decltype(view)>);

    const auto& ref_a = *it_a;
    const auto& ref_b = *it_b;

    assert(std::addressof(ref_a) == std::addressof(ref_b)); // FAILS but that is ok
    
}

So, I am assuming something else is what breaks the multi pass properties. Maybe you have a better example?
(There might be something wrong with yaml-cpp and i would like to fix it in that case)

[md5i]

Here's what the standard says:
§23.3.4.11 Concept forward_iterator

1. The forward_iterator concept adds copyability, equality comparison, and the multi-pass guarantee, specified
   below.

template<class I>
  concept forward_iterator =
    input_iterator<I> &&
    derived_from<ITER_CONCEPT(I), forward_iterator_tag> &&
    incrementable<I> &&
    sentinel_for<I, I>;

2. The domain of == for forward iterators is that of iterators over the same underlying sequence. However,
   value-initialized iterators of the same type may be compared and shall compare equal to other value-initialized
   iterators of the same type.
3. Pointers and references obtained from a forward iterator into a range [i, s) shall remain valid while [i, s)
   continues to denote a range.
4. Two dereferenceable iterators a and b of type X offer the multi-pass guarantee if:
   (4.1)— a == b implies ++a == ++b and
   (4.2)— the expression ((void)[](X x){++x;}(a), *a) is equivalent to the expression *a.
5. [Note: The requirement that a == b implies ++a == ++b and the removal of the restrictions on the number of
   assignments through a mutable iterator (which applies to output iterators) allow the use of multi-pass one-directional
   algorithms with forward iterators. — end note]

[ec36339]

I could be wrong, but ...

I think the following combination:

• Rule 4.1 of the multi-pass guarantee of std::forward_iterator
• The requirement of std::indirectly_readable that *i must be equality-preserving
• The fact that *i returns a reference (not a value)

would require that for any two iterators i == j, it must be true that addressof(*i) == addressof(*j), but the article on "equality-preservation" is so convoluted, you have to be a lawyer and mathematician to understand it, and I don't trust AI on things I don't understand well enough (yes, I'm walking back on claiming that I understand this).

In reality, this would probably almost never matter for a YAML iterator.

Also, the transform_view I was trying to build was a range of data structures read from YAML objects in a YAML array. The address of whatever *i returns for a YAML node iterator shouldn't matter at all. This whole thing started with an AI agent cowardly refusing to use std::views::transform with YAML iterators.

I have had issues with "false forward iterators" in the past. a classic case of shooting myself in the foot was the "iota generator":

std::views::iota(0, 10)
| std::views::transform([](auto&&) { return some_generator_function(); })

This produces a range of 10 results of some_generator_function() (which could be a stateful generator). The way this breaks is that iota is a bidirectional range, and transform preserves that, but the stateful generator violates the semantic guarantees of forward_iterator, which then causes algorithms and other range adapters to do stuff which causes the generator to be called more often than expected, UNLESS you somehow force the iterator category to input_iterator.

This is why I got trigger happy and trusted the AI too much. It could still be right, but I'm not 100% convinced any more.

[afonsojanu]

I tried implementing option A (downgrading iterator_category to input_iterator_tag) to see it through, and it does compile and does make the multi-pass violation honest, but it has a real side effect that I don't think either of the two options above accounts for: std::prev and std::advance called with a negative distance silently stop working the way callers expect.

libc++'s own __advance.h spells this out directly:

template <class _InputIter, ...>
void advance(_InputIter& __i, _Distance __orig_n) {
  ...
  // Calling `advance` with a negative value on a non-bidirectional iterator is a no-op in the current implementation.
  _LIBCPP_ASSERT_PEDANTIC(__n >= 0 || __has_bidirectional_iterator_category<_InputIter>::value, ...);
  std::__advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category());
}

and the input_iterator_tag overload of __advance is just for (; __n > 0; --__n) ++__i;, which does nothing at all for a negative n. The assert is pedantic-only, so in a normal build this fails silently rather than refusing to compile.

I confirmed this isn't theoretical: yaml-cpp's own test suite already relies on this. NodeTest.InteratorOnSequenceBackward in test/node_test.cpp iterates with for (iterator it = node.end(); it != node.begin(); --it) and calls prev(it)->IsNull() inside the loop. After downgrading the tag to input_iterator_tag, that test starts failing, because prev(it) (which resolves through std::advance) simply returns it unchanged instead of stepping back one element. The direct --it in the loop condition still works fine since that's a plain member function call, not something tag-dispatched, so the loop itself doesn't break, but any code path that calls std::prev/std::advance/std::distance with a negative amount against a YAML::Node::iterator silently stops moving instead of raising a compile error.

So this isn't just a formal correctness nuance that "happens to work in practice" like the C++20 range case, it's an existing, working code path (both inside this repo and plausibly in consumer code) that goes from correct to silently wrong. Given that, I don't think option A is a drop-in fix, at least not without also auditing/replacing every internal std::prev/std::advance call against this iterator and documenting the same trap for downstream users. Might be worth flagging this in the issue itself so nobody picks "just retag it" as an easy first PR without hitting this.

I don't have a clean answer for the right fix here; making operator*() return a genuinely stable reference would need a real internal storage change (caching the constructed Node somewhere with iterator-copy-independent lifetime), which is a bigger redesign than a tag change, so I'm not attempting that myself. Just wanted to flag the concrete breakage I found while looking at this.

[SGSSGene]

@afonsojanu thank you for also looking into this. If we use --it and prev(it) wouldn't that mean we are assuming that it is modeling bidirectional_iterator ?

I am still not convinced that there is a bug with the category (beside it should be bidirectional_iterator.)

There is another issue, that is maybe related. That is that YAML::Node only produces 'shallow copies' and behaves more like a 'reference type`. This currently produces unexpected memory usage. Additionally, yaml-cpp does implement correct move-semantics possibly causing all types of unexpected behavior.