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-13550] Top-down type checking when the resulting type is known #55987

Open
xAlien95 opened this issue Sep 15, 2020 · 2 comments
Open

[SR-13550] Top-down type checking when the resulting type is known #55987

xAlien95 opened this issue Sep 15, 2020 · 2 comments
Labels
compiler The Swift compiler in itself improvement type checker Area → compiler: Semantic analysis

Comments

@xAlien95
Copy link
Contributor

Previous ID SR-13550
Radar rdar://problem/68927506
Original Reporter @xAlien95
Type Improvement
Additional Detail from JIRA
Votes 0
Component/s Compiler
Labels Improvement, TypeChecker
Assignee None
Priority Medium

md5: c042299b2b7abee52cec4c90dadc37ed

Issue Description:

Following a suggestion on the Swift Forums.

Consider the following code snippet to get the operation tree of an expression:

indirect enum Expression: CustomStringConvertible {
    case integer(Int)
    case real(Double)
    
    case sum(Expression, Expression)
    case difference(Expression, Expression)
    case product(Expression, Expression)
    case division(Expression, Expression)
    
    var description: String {
        switch self {
        case let .integer(a): return "\(a)"
        case let .real(a): return "\(a)"
            
        case let .sum(a, b): return "(\(a) + \(b))"
        case let .difference(a, b): return "(\(a) - \(b))"
        case let .product(a, b): return "(\(a) * \(b))"
        case let .division(a, b): return "(\(a) / \(b))"
        }
    }
}

// MARK: Literal initialization

extension Expression: ExpressibleByIntegerLiteral, ExpressibleByFloatLiteral {
    init(integerLiteral value: IntegerLiteralType) {
        self = .integer(value)
    }
    
    init(floatLiteral value: FloatLiteralType) {
        self = .real(value)
    }
}

// MARK: Operations

extension Expression {
    static func + (lhs: Self, rhs: Self) -> Self { .sum(lhs, rhs) }
    static func - (lhs: Self, rhs: Self) -> Self { .difference(lhs, rhs) }
    static func * (lhs: Self, rhs: Self) -> Self { .product(lhs, rhs) }
    static func / (lhs: Self, rhs: Self) -> Self { .division(lhs, rhs) }
}

// MARK: - Testing

let expression: Expression = 3 + 4.1 / 65 * 2 - 12

dump(expression)

With a couple more operations

let expression: Expression = 3 + 4.1 / 65 * 2 - 12 + 4.1 / 65

the compiler starts failing to infer the type of every operand and throws the following error:

The compiler is unable to type-check this expression in reasonable time; try breaking up the expression into distinct sub-expressions

The only way to make the compiler's life easier is to explicitly write that the first integer literal is an Expression

let expression = 3 as Expression + 4.1 / 65 * 2 - 12 + 4.1 / 65

and it won't raise errors even with a hundred of subsequent operations involved.

Could the explicit variable type annotation be used by the type checker to assign types in a top-down way instead of a bottom-up one?

Ideally, in an expression like

1 + 2 + 3 + 4 + 5 as Expression

given the following variants for the + operator

Float + Float -> Float
Double + Double -> Double
Float80 + Float80 -> Float80
UInt8 + UInt8 -> UInt8
Int8 + Int8 -> Int8
UInt16 + UInt16 -> UInt16
Int16 + Int16 -> Int16
UInt32 + UInt32 -> UInt32
Int32 + Int32 -> Int32
UInt64 + UInt64 -> UInt64
Int64 + Int64 -> Int64
UInt + UInt -> UInt
Int + Int -> Int
FloatingPoint + FloatingPoint -> FloatingPoint
Numeric + Numeric -> Numeric
BinaryInteger + BinaryInteger -> BinaryInteger
SIMD + SIMD -> SIMD

Expression + Expression -> Expression

... and any other ExpressibleByIntegerLiteral conforming type

I would constrain as

(1 + 2 + 3 + 4) + 5  // we know result is Expression
// compatible overloads: 1. Expression + Expression -> Expression
// rhs: 5 literal is Expression
// lhs: 1 + 2 + 3 + 4 is Expression
(1 + 2 + 3) + 4      // we know result is Expression
// compatible overloads: 1. Expression + Expression -> Expression
// rhs: 4 literal is Expression
// lhs: 1 + 2 + 3 is Expression
(1 + 2) + 3          // we know result is Expression
// compatible overloads: 1. Expression + Expression -> Expression
// rhs: 3 literal is Expression
// ...

directly obtaining the only one valid type combination, instead of 18 different ones.
@typesanitizer
Copy link

@swift-ci create

@hborla
Copy link
Member

hborla commented Mar 29, 2021

Thank you for the suggestion! You're definitely right that type annotations and other forms of contextual result types are an opportunity for optimization in the solver. I think we could effectively make the solver attempt overloads top-down if the solver knew that there was contextual information for a certain `+` in the chain and then attempt that disjunction first.

@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
compiler The Swift compiler in itself improvement type checker Area → compiler: Semantic analysis
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@xAlien95 @typesanitizer @hborla