Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[SR-11516] Simplest MutableDataProtocol generates initializer that spins forever #53917

Closed
Lukasa opened this issue Sep 24, 2019 · 9 comments
Closed

[SR-11516] Simplest MutableDataProtocol generates initializer that spins forever #53917

Lukasa opened this issue Sep 24, 2019 · 9 comments
Assignees
@glessard
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself standard library Area: Standard library umbrella

Comments

@Lukasa
Copy link
Contributor

Lukasa commented Sep 24, 2019

Previous ID SR-11516
Radar None
Original Reporter @Lukasa
Type Bug
Status Resolved
Resolution Duplicate
Environment

Apple Swift version 5.1.1 (swiftlang-1100.0.273 clang-1100.0.33.9)
Target: x86_64-apple-darwin19.0.0

Additional Detail from JIRA
Votes 2
Component/s Compiler, Standard Library
Labels Bug
Assignee @glessard
Priority Medium

md5: e90e078aa56172fe96027339f8b054ce

duplicates:

  • SR-6501 RangeReplaceableCollection default implementations cause infinite recursion

Issue Description:

The following sample program, which is basically the simplest possible MutableDataProtocol, generates an initializer that spins forever:

import Foundation

struct ByteBucket: MutableDataProtocol, ContiguousBytes {
    init() {
        self.underlyingData = Data()
    }
    
    var startIndex: Data.Index { underlyingData.startIndex }
    var endIndex: Data.Index { underlyingData.endIndex }
    
    var underlyingData: Data
    var regions: CollectionOfOne<ByteBucket> { CollectionOfOne(self) }

    subscript(position: Data.Index) -> UInt8 {
        get {
            return underlyingData[position]
        }
        set(newValue) {
            underlyingData[position] = newValue
        }
    }

    func withUnsafeBytes<R>(_ body: (UnsafeRawBufferPointer) throws -> R) rethrows -> R {
        return try self.underlyingData.withUnsafeBytes(body)
    }

    mutating func withUnsafeMutableBytes<R>(_ body: (UnsafeMutableRawBufferPointer) throws -> R) rethrows -> R {
        return try self.underlyingData.withUnsafeMutableBytes(body)
    }
}


func test() -> Int32 {
    let data: [UInt8] = [0, 1, 2, 3, 4, 5, 6, 7, 8]
    let bucket = ByteBucket(data)
    return bucket.count == 9 ? 0 : 1
}

exit(test())

This program will never exit (release mode) or will segfault (debug mode), though it definitely should run cleanly.

This appears to be the result of the default implementations for `RangeReplaceableProtocol`. Taking a look at the debug mode call stack gives us a call stack 65k frames deep. The base is:

    frame #&#8203;65515: 0x00000001000015c0 test`protocol witness for Swift.RangeReplaceableCollection.insert(_: __owned A.Element, at: A.Index) -> () in conformance test.ByteBucket : Swift.RangeReplaceableCollection in test + 16
    frame #&#8203;65516: 0x00007fff7536f866 libswiftCore.dylib`(extension in Swift):Swift.RangeReplaceableCollection.append(__owned A.Element) -> () + 118
    frame #&#8203;65517: 0x0000000100001560 test`protocol witness for Swift.RangeReplaceableCollection.append(__owned A.Element) -> () in conformance test.ByteBucket : Swift.RangeReplaceableCollection in test + 16
    frame #&#8203;65518: 0x00007fff754815e5 libswiftCore.dylib`function signature specialization <Arg[0] = Owned To Guaranteed> of (extension in Swift):Swift.RangeReplaceableCollection.append<A where A1: Swift.Sequence, A.Element == A1.Element>(contentsOf: __owned A1) -> () + 549
    frame #&#8203;65519: 0x00007fff7536f900 libswiftCore.dylib`merged (extension in Swift):Swift._ArrayBufferProtocol._arrayAppendSequence<A where A1: Swift.Sequence, A.Element == A1.Element>(__owned A1) -> () + 16
    frame #&#8203;65520: 0x000000010000159d test`protocol witness for Swift.RangeReplaceableCollection.append<A where A1: Swift.Sequence, A.Element == A1.Element>(contentsOf: __owned A1) -> () in conformance test.ByteBucket : Swift.RangeReplaceableCollection in test + 45
    frame #&#8203;65521: 0x00007fff75251425 libswiftCore.dylib`(extension in Swift):Swift.RangeReplaceableCollection.init<A where A1: Swift.Sequence, A.Element == A1.Element>(A1) -> A + 69
    frame #&#8203;65522: 0x0000000100001fee test`test.test() -> Swift.Int32 + 254
    frame #&#8203;65523: 0x00000001000009a4 test`main + 20
    frame #&#8203;65524: 0x00007fff75db4325 libdyld.dylib`start + 1
    frame #&#8203;65525: 0x00007fff75db4325 libdyld.dylib`start + 1

The above stack shows the infinite recursion:

    frame #&#8203;65515: 0x00000001000015c0 test`protocol witness for Swift.RangeReplaceableCollection.insert(_: __owned A.Element, at: A.Index) -> () in conformance test.ByteBucket : Swift.RangeReplaceableCollection in test + 16
    frame #&#8203;65516: 0x00007fff7536f866 libswiftCore.dylib`(extension in Swift):Swift.RangeReplaceableCollection.append(__owned A.Element) -> () + 118
    frame #&#8203;65517: 0x0000000100001560 test`protocol witness for Swift.RangeReplaceableCollection.append(__owned A.Element) -> () in conformance test.ByteBucket : Swift.RangeReplaceableCollection in test + 16

There is no code in my sample that actually implements any of the requirements of RangeReplaceableCollection, which suggests that MutableDataProtocol is bringing them in somehow. This is backed up by the fact that if the above program is changed to change the words MutableDataProtocol to DataProtocol, the program fails to compile.

I don't know if this is a compiler bug or a Foundation bug, so it goes to both teams.
@weissi
Copy link
Member

weissi commented Sep 24, 2019

yeah, MutableDataProtocol is a RRC:

swift/stdlib/public/Darwin/Foundation/DataProtocol.swift

Line 73 in 6171d68

public protocol MutableDataProtocol : DataProtocol, MutableCollection, RangeReplaceableCollection {

@Lukasa
Copy link
Contributor Author

Lukasa commented Sep 24, 2019

That’s not really the relevant part. It’s fine that MutableDataProtocol must be an RRC. What’s not fine is that ByteBucket doesn’t implement any of the required API for RRC: it has no replaceSubrange method. That means MutableDataProtocol is providing the implementation, and whatever implementation it is providing is clearly leading to an infinite recursion.

@belkadan
Copy link
Contributor

I don't think we have a good answer for this. How is the compiler supposed to know which requirement you want to implement to break the cycle?

@Lukasa
Copy link
Contributor Author

Lukasa commented Sep 25, 2019

Yeah, I tagged the compiler but I don’t know if the compiler can resolve this. I do think that something (probably MutableDataProtocol) has not correctly documented its implementation requirements, because I don’t think anything is obviously implemented incorrectly here.

@swift-ci
Copy link
Collaborator

Comment by Sergo Beruashvili (JIRA)

The problem seems that RangeReplaceableCollection requires custom implementation of replaceSubrange, https://github.com/apple/swift/blob/master/stdlib/public/core/RangeReplaceableCollection.swift#L57

But... It also provides its own replaceSubrange, which just forwards it to custom implementation, but since there is no custom one, it calls itself - https://github.com/apple/swift/blob/master/stdlib/public/core/RangeReplaceableCollection.swift#L746

MutableDataProtocol just declares conformance of RRC - https://github.com/apple/swift/blob/master/stdlib/public/Darwin/Foundation/DataProtocol.swift#L73

Adding following code to the ByteBucket fixes it:

mutating func replaceSubrange<C>(_ subrange: Range<Data.Index>, with newElements: __owned C) where C: Collection, C.Element == Element {
    underlyingData.replaceSubrange(subrange, with: newElements)
}

@Lukasa
Copy link
Contributor Author

Lukasa commented Sep 29, 2019

Jordan, is it correct that the default implementation of replaceSubrange<C, R> satisfies the requirement to implement replaceSubrange<C>? That seems...unexpected to me. I feel like I’ve seen the compiler shout at me for not providing the default implementation before.

@belkadan
Copy link
Contributor

Ah, it's not desirable but it is correct. :-/ @lorentey, any ideas?

@belkadan
Copy link
Contributor

Nice analysis, ogres (JIRA User).

@lorentey
Copy link
Member

Ah, thanks Sergo – this is a new incarnation of the same issue that we have seen with `RandomNumberGenerator.next()` vs `.next<F>()`. It doesn't bode well that we got this wrong twice now.

What if we added a @_not_implements(RangeReplaceableCollection) attribute that would remove these from consideration during conformance checks?

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@glessard glessard

Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself standard library Area: Standard library umbrella
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
5 participants
@lorentey @weissi @belkadan @Lukasa @swift-ci