8

The javadoc of Spliterator mentions that:

A Spliterator may traverse elements individually (tryAdvance()) or sequentially in bulk (forEachRemaining()).

Then we go to the javadoc of tryAdvance() which says that:

If a remaining element exists, performs the given action on it, returning true; else returns false.

Maybe I am misreading somewhere, but to me it seems that provided there is one element, or more, remaining, the Consumer as an argument should only every .accept() one argument before returning true, and that if, say, I have two arguments immediately available, then I cannot:

action.accept(arg1);
action.accept(arg2);
return true;

In this project, I have rewritten the breadth first spliterator so that it now reads:

// deque is a Deque<Iterator<T>>

@Override
public boolean tryAdvance(final Consumer<? super T> action)
{
    Iterator<T> iterator;
    T element;

    while (!deque.isEmpty()) {
        iterator = deque.removeFirst();
        while (iterator.hasNext()) {
            element = iterator.next();
            deque.add(fn.apply(element));
            action.accept(element);
        }
    }
    return false;
}

In short, I make the action accept all arguments, and then return false... and the test, albeit quite simple, still succeeds (link).

Note that .trySplit() always returns null; and the spliterator has chacacteristics DISTINCT, ORDERED and NONNULL.

So, is there a stream usage in which the code above will not work due to the method above consuming all elements at once?

fge
  • 119,121
  • 33
  • 254
  • 329
  • 1
    Does it really matter whether the current implementation of one particular API breaks, when you violate the general contract of an `interface`? You’re not only invoking the action more than once, you are also returning `false` despite there were items. – Holger Apr 28 '16 at 17:46
  • @Holger the problem is that it's unclear to me what should happen if more than one element remains – fge Apr 28 '16 at 17:51
  • 1
    Are aiming at how to interpret the contract or what you should do, practically? – Holger Apr 28 '16 at 18:08
  • 2
    Oh god please _no_ under no circumstances should you do this. (And yes, I've written code that would break with this, e.g. `dropWhile` implementations on `Spliterator`s.) – Louis Wasserman Apr 28 '16 at 18:49
  • 3
    The spec really should be clearer about this. See [JDK-8133773](https://bugs.openjdk.java.net/browse/JDK-8133773). The requirement is that `tryAdvance` either 1) call the action ONCE and return true; or 2) call the action ZERO TIMES and return false. – Stuart Marks Apr 29 '16 at 01:47
  • 3
    @fge: note that you interpretation of `DISTINCT` is incorrect. If there’s a possibility of encountering equal objects, you *must not* report a `DISTINCT` characteristic. – Holger Apr 29 '16 at 12:27
  • @Holger we walk nodes in a tree here, so... In fact, I hesitated in adding this characteristic, but since nodes are unique by definition even if .equals() I thought it was for the best. Or maybe not. Argh – fge Apr 29 '16 at 12:43
  • 1
    @fge: well, you could consider each element of a list to be distinct by its position, still, a `List`’s `Spliterator` will not report the `DISTINCT` characteristic as there might be *equal* elements. Further, you can use the code of [this answer](http://stackoverflow.com/a/28475289/2711488) to find out that calling `unordered()` will not clear the `DISTINCT` property, so if the position is the only differentiation, that’s also wrong on the conceptional level. (And `.distinct()` being a no-op on such a stream can be considered broken). – Holger Apr 29 '16 at 12:58
  • @Holger OK, I'll revert on that... And publish 0.2.0. – fge Apr 29 '16 at 12:59
  • 1
    @fge: one last note: to me it looks like these spliterators would greatly benefit from a custom `forEachRemaining()` implementation as that method can indeed call the consumer multiple times, reducing the number of elements needing queuing (or even process all elements without queuing). – Holger Apr 29 '16 at 13:08
  • @Holger probably so in many cases, yes; my first goal here was with having something which works ;) Also, I realize that in many cases the code could be optimized to work better. Feel free to contribute, too :) – fge Apr 29 '16 at 13:26

1 Answers1

10

Your assumption that tryAdvance() should only consume one element is right. This, however, does not imply that you will notice violations of the contract immediately. When you test using operations like .collect(Collectors.toList()) it’s even unlikely to spot such a violation as most operations consuming all elements will invoke forEachRemaining() on the spliterator whose default implementation is documented as:

The default implementation repeatedly invokes tryAdvance(java.util.function.Consumer) until it returns false.

Obviously, for that method it makes no difference.

The Stream framework will invoke tryAdvance() when performing lazy operations. So when you use .peek(System.out::println).findFirst() you may notice a difference when your tryAdvance() implementation pushes more than one value. Still, given the current implementation, the result is the correct first element. Apparently, the implementation-provided consumer ignores subsequent values after encountering a value.

This might be connected to other implementation details like the one discussed in “Why filter() after flatMap() is ‘not completely’ lazy in Java streams?”. If the stream implementation itself pushes more values than necessary under certain circumstances, the receiving end in the same implementation must be prepared to handle that case.

But it must be emphasized that this is the behavior of one particular Stream API implementation. A different implementation or the next Java version might rely on a correct implementation of tryAdvance. Further, there might be use cases for Spliterators other than Streams.

Well, I finally found an example of an operation that breaks with your Spliterator:

for(Iterator<?> it=Spliterators.iterator(spliterator); it.hasNext();) {
    System.out.println(it.next());
}
Community
  • 1
  • 1
Holger
  • 285,553
  • 42
  • 434
  • 765