swiftlang / swift

The Swift Programming Language
https://swift.org
Apache License 2.0
66.76k stars 10.29k forks source link

Creating a Dictionary or Set with an element type containing a type parameter pack consisting of only a single class type crashes the compiler in release builds #73219

Open lukaskollmer opened 2 months ago

lukaskollmer commented 2 months ago

Description

Attempting to create an instance of a Set or a Dictionary where the generic parameter (Element in the case of the Set, and Key in the case of the Dictionary) is a Hashable type that uses variadic generics and is passed a single class type as its type parameter pack, crashes the compiler in a release build. (Sometimes also depending on if the Set or Dictionary is created using a literal.)

See the example program below: it defines several variables (sets and dictionaries) with different parameters for the generic parameter, and using different ways of initialising the values (using a literal and using .init()).

When compiled with a debug build, the entire program will compile without any issues. But in a release build, the compiler will crash if the program contains at least one instantiation of Set or Dictionary where the Hashable generic parameter is HashableTuple<C>. For some reason, this only happens when HashableTuple's parameter pack consists of a single class type. If a struct type is specified instead, or multiple class types, or a mix of class and struct types, everything seems to work just fine.

I also tried defining a custom type with a Hashable-constrained generic parameter that implements ExpressibleByArrayLiteral, but for some reason instantiating that instead of eg Set worked fine (ie, didn't crash the compiler).

Reproduction

func zip<each T, each U>(_ firsts: (repeat each T), _ seconds: (repeat each U)) -> (repeat (each T, each U)) {
    return (repeat (each firsts, each seconds))
}

/// Determines if two tuples of arbitrary length are equal.
func == <each T: Equatable>(_ lhs: (repeat each T), _ rhs: (repeat each T)) -> Bool {
    let zipped = zip((repeat each lhs), (repeat each rhs))
    var equal = true
    func imp<U: Equatable>(_ input: (U, U)) {
        equal = equal && input.0 == input.1
    }
    repeat imp(each zipped)
    return equal
}

struct HashableTuple<each T: Hashable>: Hashable {
    var elements: (repeat each T)

    func hash(into hasher: inout Hasher) {
        (repeat (each elements).hash(into: &hasher))
    }

    static func == (lhs: Self, rhs: Self) -> Bool {
        return (repeat each lhs.elements) == (repeat each rhs.elements)
    }
}

class C: Hashable {
    func hash(into hasher: inout Hasher) {
        hasher.combine(ObjectIdentifier(self))
    }

    static func == (lhs: C, rhs: C) -> Bool {
        return ObjectIdentifier(lhs) == ObjectIdentifier(rhs)
    }
}

struct S: Hashable {}

// all of the following will fail (replace C with S, or add additional types to make it compile...)
var set1: Set<HashableTuple<C>> = []
var dict1: [HashableTuple<C>: Void] = [:]

// all of these are fine
var set2: Set<HashableTuple<C>> = .init()
var dict2: [HashableTuple<C>: Void] = .init()
var set3: Set<HashableTuple<C, C>> = []
var dict3: [HashableTuple<C, C>: Void] = [:]

Stack dump

error: compile command failed due to signal 11 (use -v to see invocation)
Please submit a bug report (https://swift.org/contributing/#reporting-bugs) and include the crash backtrace.
Stack dump:
0.  Program arguments: /Applications/Xcode-15.3.0.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/swift-frontend -frontend -c -primary-file x.swift -target arm64-apple-macosx14.0 -Xllvm -aarch64-use-tbi -enable-objc-interop -stack-check -sdk /Applications/Xcode-15.3.0.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX14.4.sdk -color-diagnostics -O -new-driver-path /Applications/Xcode-15.3.0.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/swift-driver -empty-abi-descriptor -resource-dir /Applications/Xcode-15.3.0.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/swift -module-name x -disable-clang-spi -target-sdk-version 14.4 -target-sdk-name macosx14.4 -external-plugin-path /Applications/Xcode-15.3.0.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX14.4.sdk/usr/lib/swift/host/plugins#/Applications/Xcode-15.3.0.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX14.4.sdk/usr/bin/swift-plugin-server -external-plugin-path /Applications/Xcode-15.3.0.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX14.4.sdk/usr/local/lib/swift/host/plugins#/Applications/Xcode-15.3.0.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX14.4.sdk/usr/bin/swift-plugin-server -external-plugin-path /Applications/Xcode-15.3.0.app/Contents/Developer/Platforms/MacOSX.platform/Developer/usr/lib/swift/host/plugins#/Applications/Xcode-15.3.0.app/Contents/Developer/Platforms/MacOSX.platform/Developer/usr/bin/swift-plugin-server -external-plugin-path /Applications/Xcode-15.3.0.app/Contents/Developer/Platforms/MacOSX.platform/Developer/usr/local/lib/swift/host/plugins#/Applications/Xcode-15.3.0.app/Contents/Developer/Platforms/MacOSX.platform/Developer/usr/bin/swift-plugin-server -plugin-path /Applications/Xcode-15.3.0.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/swift/host/plugins -plugin-path /Applications/Xcode-15.3.0.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/local/lib/swift/host/plugins -enable-default-cmo -o /var/folders/72/gdk4ykgs6bdg2kds9pynlhzc0000gn/T/TemporaryDirectory.baPUSv/x-1.o
1.  Apple Swift version 5.10 (swiftlang-5.10.0.13 clang-1500.3.9.4)
2.  Compiling with the current language version
3.  While evaluating request ExecuteSILPipelineRequest(Run pipelines { PrepareOptimizationPasses, EarlyModulePasses, HighLevel,Function+EarlyLoopOpt, HighLevel,Module+StackPromote, MidLevel,Function, ClosureSpecialize, LowLevel,Function, LateLoopOpt, SIL Debug Info Generator } on SIL for x)
4.  While running pass #17655 SILFunctionTransform "DCE" on SILFunction "@$ss22__RawDictionaryStorageC4find_9hashValues10_HashTableV6BucketV6bucket_Sb5foundtx_SitSHRzlF1x13HashableTupleVyAK1CC_QPG_Tg5".
 for <<debugloc at "<compiler-generated>":0:0>>Stack dump without symbol names (ensure you have llvm-symbolizer in your PATH or set the environment var `LLVM_SYMBOLIZER_PATH` to point to it):
0  swift-frontend           0x000000010841ff3c llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) + 56
1  swift-frontend           0x000000010841f0f8 llvm::sys::RunSignalHandlers() + 112
2  swift-frontend           0x0000000108420544 SignalHandler(int) + 360
3  libsystem_platform.dylib 0x000000018cec5a24 _sigtramp + 56
4  swift-frontend           0x000000010381aacc (anonymous namespace)::DCE::markValueLive(swift::SILValue) + 424
5  swift-frontend           0x000000010381aacc (anonymous namespace)::DCE::markValueLive(swift::SILValue) + 424
6  swift-frontend           0x000000010381793c (anonymous namespace)::DCEPass::run() + 3788
7  swift-frontend           0x000000010375ba68 swift::SILPassManager::runFunctionPasses(unsigned int, unsigned int) + 3856
8  swift-frontend           0x0000000103754a0c swift::SILPassManager::executePassPipelinePlan(swift::SILPassPipelinePlan const&) + 240
9  swift-frontend           0x0000000103791354 swift::SimpleRequest<swift::ExecuteSILPipelineRequest, std::__1::tuple<> (swift::SILPipelineExecutionDescriptor), (swift::RequestFlags)1>::evaluateRequest(swift::ExecuteSILPipelineRequest const&, swift::Evaluator&) + 56
10 swift-frontend           0x0000000103775184 llvm::Expected<swift::ExecuteSILPipelineRequest::OutputType> swift::Evaluator::getResultUncached<swift::ExecuteSILPipelineRequest>(swift::ExecuteSILPipelineRequest const&) + 476
11 swift-frontend           0x0000000103777e94 swift::runSILOptimizationPasses(swift::SILModule&) + 504
12 swift-frontend           0x0000000102f2d16c swift::CompilerInstance::performSILProcessing(swift::SILModule*) + 1224
13 swift-frontend           0x0000000102d1df98 performCompileStepsPostSILGen(swift::CompilerInstance&, std::__1::unique_ptr<swift::SILModule, std::__1::default_delete<swift::SILModule>>, llvm::PointerUnion<swift::ModuleDecl*, swift::SourceFile*>, swift::PrimarySpecificPaths const&, int&, swift::FrontendObserver*) + 1128
14 swift-frontend           0x0000000102d1d444 swift::performCompileStepsPostSema(swift::CompilerInstance&, int&, swift::FrontendObserver*) + 608
15 swift-frontend           0x0000000102d21694 performCompile(swift::CompilerInstance&, int&, swift::FrontendObserver*) + 1448
16 swift-frontend           0x0000000102d1f6d0 swift::performFrontend(llvm::ArrayRef<char const*>, char const*, void*, swift::FrontendObserver*) + 4968
17 swift-frontend           0x0000000102caee8c swift::mainEntry(int, char const**) + 2612
18 dyld                     0x000000018cb150e0 start + 2360
error: fatalError

Expected behavior

IMO this should compile just fine.

Environment

swift-driver version: 1.90.11.1 Apple Swift version 5.10 (swiftlang-5.10.0.13 clang-1500.3.9.4) Target: arm64-apple-macosx14.0

Additional information

i also tried this with the nightly compiler, which also crashed.

lukaskollmer commented 2 months ago

Update:

Having looked into this a bit more (and spent some more time trying to work around this issue), it seems like this is in fact not caused by the use of set/dictionary literals, but rather is somehow directly related to the use of a single class type in the generic type parameter pack?

To provide some more context, the HashableTuple defined above is used as part of a memoize function:

func memoize<each Input: Hashable, Output>(_ fn: @escaping (repeat each Input) -> Output) -> (repeat each Input) -> Output {
    var cache: [HashableTuple<repeat each Input>: Output] = .init()
    return { (input: repeat each Input) -> Output in
        let key = HashableTuple(elements: (repeat each input))
        // rest omitted bc not relevant
    }
}

even though declaring and initializing a dict as a global variable using .init() works (as seen in the original post), it still fails when done within a function.

As with the initial issue, this seems to happen only if the type using a generic type parameter pack (HashableTuple in this case) is instantiated using only a single class type parameter.

Simply always adding an implicit trailing non-class type parameter to the pack (and thereby ensuring it never consists of only a single class type) seems to work around this issue:

private struct EmptyStruct: Hashable {}

func memoize<each Input: Hashable, Output>(_ fn: @escaping (repeat each Input) -> Output) -> (repeat each Input) -> Output {
    var cache: [HashableTuple<repeat each Input, EmptyStruct>: Output] = [:] // <--
    return { (input: repeat each Input) -> Output in
        let key = HashableTuple(elements: (repeat each input, EmptyStruct())) // <--
        // rest omitted bc not relevant
    }
}