[SR-11841] Lazy filter runs in unexpected order

[swift-ci]

Previous ID	SR-11841
Radar	rdar://problem/57549147
Original Reporter	dtorres (JIRA User)
Type	Bug
Status	Resolved
Resolution	Done

Environment

Xcode 11.2.1

Additional Detail from JIRA

Votes	0
Component/s	Standard Library
Labels	Bug
Assignee	None
Priority	Medium

md5: 281a0f54ddfb46f82336abd5abaa9562

Issue Description:

For the following code:

var array = ["1", "2", "3"]


let filtered = array.lazy
    .filter({ _ in
        print("A")
        return true
    }).filter { _ in
        print("B")
        return true
}

_ = Array(filtered)

Actual Results:

B
A
B
A
B
A

Expected Results:

A
B
A
B
A
B

I would expect a cascade behaviour of A filtering before B*. However, this prints:

*Not to confuse with non lazy behaviour of AAABBB which is indeed correct

[swift-ci]

Comment by Diego Torres (JIRA)

It is indeed wrong.
https://github.com/apple/swift/blob/master/stdlib/public/core/Filter.swift#L341

Thanks @natecook1000

[swift-ci]

Comment by Diego Torres (JIRA)

And a PR to fix it #28462

[pcantrell]

An interesting example that came up discussing this bug, just to demonstrate how insidious it can be:

var valuesEncountered = Set<String>()

var result = ["bangle", "bannister", "banjo"]
    .filter({ valuesEncountered.insert($0).inserted })
    .filter({ valuesEncountered.insert(String($0.prefix(3))).inserted })

print(valuesEncountered)  // ["bangle", "bannister", "banjo", "ban”]

…as expected. But make it lazy, which should give the same results:

var valuesEncountered = Set<String>()

var result = ["bangle", "bannister", "banjo"]
    .lazy  // go lazy
    .filter({ valuesEncountered.insert($0).inserted })
    .filter({ valuesEncountered.insert(String($0.prefix(3))).inserted })

Array(result)  // force evaluation
print(valuesEncountered)  // ["ban", "bangle”] ← oops!

But then if we trigger lazy evaluation with a contextual type instead of an explicit Array(…) call:

var valuesEncountered = Set<String>()

// Now [String] type forces evaluation instead
var result: [String] = ["bangle", "bannister", "banjo"]
    .lazy  // go lazy
    .filter({ valuesEncountered.insert($0).inserted })
    .filter({ valuesEncountered.insert(String($0.prefix(3))).inserted })

print(valuesEncountered)  // ["bangle", "ban", "banjo", "bannister”]

[beccadax]

@swift-ci create

[natecook1000]

Just as a note, that last example isn't using lazy evaluation — providing the type of the result as [String] selects the filter method from the Sequence protocol rather than the one implemented directly on the LazySequence type.

[natecook1000]

Fixed in #28462