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

Incorrect generic signature minimization causes failure in concrete equivalence class splitting #64995

Open
slavapestov opened this issue Apr 7, 2023 · 0 comments
Assignees
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself crash Bug: A crash, i.e., an abnormal termination of software generic constraints Feature → generics: generic constraints generics Feature: generic declarations and types swift 5.9 type checker Area → compiler: Semantic analysis

Comments

@slavapestov
Copy link
Member

slavapestov commented Apr 7, 2023

Reduced from https://forums.swift.org/t/requirement-machine-failure/64235/3. The problem is the generic signature of foo() below.

The second same-type requirement is bogus and should have been minimized away:

Splitting concrete equivalence classes did not reach fixed point after 2 attempts.
Last attempt produced these requirements:
conforms_to: T BidirectionalPattern
same_type: T.[Pattern]Match.[PatternMatch]Searched Data
same_type: T.[Pattern]Match.[PatternMatch]Searched.[BidirectionalPattern]Reversed.[Collection]SubSequence T.[Pattern]Match.[PatternMatch]Searched.[BidirectionalPattern]Reversed.[Pattern]SubSequencePattern
Requirement machine for <τ_0_0 where τ_0_0 : BidirectionalPattern, τ_0_0.Match.Searched == Data, τ_0_0.Match.Searched.Reversed.SubSequence == τ_0_0.Match.Searched.Reversed.SubSequencePattern>
import Foundation

protocol BidirectionalPattern: Pattern where Searchable: SearchableBidirectionalCollection {
  associatedtype Reversed: Pattern where Reversed.Searchable == ReversedCollection<Searchable>
}

protocol SearchableBidirectionalCollection: BidirectionalCollection, BidirectionalPattern, SearchableCollection where SubSequence: SearchableBidirectionalCollection {
}

protocol SearchableCollection: Collection, Pattern where Element: Equatable, Searchable == Self, SubSequence: SearchableCollection {}

protocol Pattern {
  typealias Searchable = Match.Searched

  associatedtype Match: PatternMatch

  associatedtype SubSequencePattern: Pattern where SubSequencePattern.Searchable == Searchable.SubSequence
}

protocol PatternMatch {
  associatedtype Searched: SearchableCollection
}

extension ReversedCollection: Pattern, SearchableCollection where Base: SearchableCollection {
  typealias Match = AtomicPatternMatch<ReversedCollection<Base>>
  typealias SubSequencePattern = Slice<ReversedCollection<Base>>
}

extension ReversedCollection: BidirectionalPattern, SearchableBidirectionalCollection where Base: SearchableBidirectionalCollection {
  typealias Reversed = ReversedCollection<Self>
}

struct AtomicPatternMatch<Searched>: PatternMatch where Searched: SearchableCollection {}

extension Data: SearchableBidirectionalCollection {
  typealias Reversed = ReversedCollection<Data>
  typealias Match = AtomicPatternMatch<Data>
  typealias SubSequencePattern = Data

}

extension Slice: Pattern, SearchableCollection where Base: SearchableCollection {
  typealias Match = AtomicPatternMatch<Slice<Base>>
  typealias SubSequencePattern = Slice<Base>
}

extension Slice: BidirectionalPattern, SearchableBidirectionalCollection where Base: SearchableBidirectionalCollection {
  typealias Reversed = ReversedCollection<Self>
}

func foo<T: BidirectionalPattern>(_: T) where T.Match.Searched == Data {}
@slavapestov slavapestov added bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. triage needed This issue needs more specific labels labels Apr 7, 2023
@slavapestov slavapestov self-assigned this Apr 7, 2023
@AnthonyLatsis AnthonyLatsis added compiler The Swift compiler in itself type checker Area → compiler: Semantic analysis compiler crash generics Feature: generic declarations and types crash Bug: A crash, i.e., an abnormal termination of software generic constraints Feature → generics: generic constraints swift 5.9 and removed triage needed This issue needs more specific labels labels Apr 7, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself crash Bug: A crash, i.e., an abnormal termination of software generic constraints Feature → generics: generic constraints generics Feature: generic declarations and types swift 5.9 type checker Area → compiler: Semantic analysis
Projects
None yet
Development

No branches or pull requests

2 participants