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-14937] Compiler hangs when applying a deeply nested typealias #57279

Open
swift-ci opened this issue Jul 17, 2021 · 1 comment
Open

[SR-14937] Compiler hangs when applying a deeply nested typealias #57279

swift-ci opened this issue Jul 17, 2021 · 1 comment
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself

Comments

@swift-ci
Copy link
Collaborator

Previous ID SR-14937
Radar rdar://problem/80820405
Original Reporter mossprescott (JIRA User)
Type Bug
Environment

macOS 11.4

Mac mini (M1), 16 GB

Xcode 12.5.1

Swift 5.4.2

Building in Xcode vs. terminal or ARM vs. x86 seems to make no difference.

Additional Detail from JIRA
Votes 0
Component/s Compiler
Labels Bug
Assignee None
Priority Medium

md5: fc2863e2d1f0bc92b5a9ae41690dff09

Issue Description:

A series of type aliases, each with a single parameter, is used to construct a deeply recursive type. As the size of the nested type increases, the compiler takes slightly longer to run. At a certain size (about 16 levels deep), the compiler hangs indefinitely.

According to Activity monitor, `swift-frontend` is pegging a single core, with memory stable at about 35 MB.

This issue seems to make it pretty hard to use this approach to define compile-time natural numbers. I ended up using a different encoding instead for what I needed (which was actually just the numbers 0 to 63.)

A Swift package exhibiting the problem can be found at https://github.com/mossprescott/swift-bug-recursive-types.

The offending code is:

protocol Nat {}
enum Zero: Nat {}
enum Succ<Pred: Nat>: Nat {}

typealias One = Succ<Zero>
typealias Plus1<T: Nat> = Succ<T>
typealias Plus2<T: Nat> = Plus1<Plus1<T>>
typealias Plus4<T: Nat> = Plus2<Plus2<T>>
typealias Plus8<T: Nat> = Plus4<Plus4<T>>

/// The compiler hangs if this type alias is **used**, but not if this declaration appears but is never applied:
typealias Plus16<T: Nat> = Plus8<Plus8<T>>

/// However, this seems to be fine:
typealias _64 = Succ<Succ<...<Zero>...>>

The package will build, but the compiler hangs when a test tries to apply that alias:

$ swift --version 
Apple Swift version 5.4.2 (swiftlang-1205.0.28.2 clang-1205.0.19.57)
Target: arm64-apple-darwin20.5.0
 
$ time swift build  # declares, but does not apply, the Plus16 alias
[2/2] Build complete!
 real    0m0.192s
 user    0m0.119s
 sys    0m0.041s
 
$ swift test -v   # tries to apply the alias to construct the compile-time value 16
...
/usr/bin/xcrun --sdk macosx --find xctest
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/swiftc -print-target-info
...
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/swift-frontend -frontend -c -primary-file /Users/moss/git/RecursiveTypes/Tests/RecursiveTypesTests/RecursiveTypesTests.swift -emit-module-path /Users/moss/git/RecursiveTypes/.build/arm64-apple-macosx/debug/RecursiveTypesTests.build/RecursiveTypesTests~partial.swiftmodule -emit-module-doc-path /Users/moss/git/RecursiveTypes/.build/arm64-apple-macosx/debug/RecursiveTypesTests.build/RecursiveTypesTests~partial.swiftdoc -emit-module-source-info-path /Users/moss/git/RecursiveTypes/.build/arm64-apple-macosx/debug/RecursiveTypesTests.build/RecursiveTypesTests~partial.swiftsourceinfo -emit-dependencies-path /Users/moss/git/RecursiveTypes/.build/arm64-apple-macosx/debug/RecursiveTypesTests.build/RecursiveTypesTests.d -emit-reference-dependencies-path /Users/moss/git/RecursiveTypes/.build/arm64-apple-macosx/debug/RecursiveTypesTests.build/RecursiveTypesTests.swiftdeps -target arm64-apple-macosx10.15 -Xllvm -aarch64-use-tbi -enable-objc-interop -stack-check -sdk /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX11.3.sdk -I /Users/moss/git/RecursiveTypes/.build/arm64-apple-macosx/debug -I /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/usr/lib -F /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/Library/Frameworks -color-diagnostics -enable-testing -g -module-cache-path /Users/moss/git/RecursiveTypes/.build/arm64-apple-macosx/debug/ModuleCache -swift-version 5 -Onone -D SWIFT_PACKAGE -D DEBUG -enable-anonymous-context-mangled-names -target-sdk-version 11.3 -parse-as-library -module-name RecursiveTypesTests -o /Users/moss/git/RecursiveTypes/.build/arm64-apple-macosx/debug/RecursiveTypesTests.build/RecursiveTypesTests.swift.o -index-store-path /Users/moss/git/RecursiveTypes/.build/arm64-apple-macosx/debug/index/store -index-system-modules
^C
$
@typesanitizer
Copy link

@swift-ci create

At first, this reminded me of https://bugs.swift.org/browse/SR-1312 but that is actually different as we end up with high memory consumption there but not here.

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@typesanitizer @swift-ci