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

[SR-6820] Literal 0 triggers spurious compile-time error, breaks source compatibility with Swift 4.0 #49369

Closed
xwu opened this issue Jan 24, 2018 · 30 comments
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. regression standard library Area: Standard library umbrella swift 4.1

Comments

@xwu
Copy link
Collaborator

xwu commented Jan 24, 2018

Previous ID SR-6820
Radar rdar://problem/36826847
Original Reporter @xwu
Type Bug
Status Closed
Resolution Done
Additional Detail from JIRA
Votes 0
Component/s Standard Library
Labels Bug, 4.1Regression
Assignee None
Priority Medium

md5: a9726c96f9cb0d194a1df694ad41f0ba

Issue Description:

This bug is related to SR-6602, or it is the same bug with a different manifestation.

In that report, it was thought that the bug would affect essentially no one in the wild because people won't be writing `0.magnitude`.

However, I have just discovered that my own, in-the-wild test cases for NumericAnnex break terribly with the latest builds of Swift. For example:

XCTAssertTrue((pi * 0).isNaN)

or

XCTAssertEqual(Int8.lcmFullWidth(0, 42).high, 0)

both fail to compile with the warning "arithmetic operation 'x + 1' (on T) results in an overflow" (where x == T.max).

I had to disable the statements that failed to compile, of which there were many. See: xwu/NumericAnnex@c5816a9

@xwu
Copy link
Collaborator Author

xwu commented Jan 24, 2018

/cc @stephentyrone

@belkadan
Copy link
Contributor

cc @moiseev

@belkadan
Copy link
Contributor

@swift-ci create

@moiseev
Copy link
Mannequin

moiseev mannequin commented Jan 24, 2018

I wonder is that's related to the CS changes by @xedin

I am having hard times remembering any stdlib changes around integers since 4.0, apart from those that support the CS work.

@xedin
Copy link
Member

xedin commented Jan 24, 2018

It looks like it might be related to removal of _Strideable, most likely in -swift-version 3 there is conflicting overload which we don't have in >= 4.1 mode...

@xwu
Copy link
Collaborator Author

xwu commented Jan 24, 2018

Out of curiosity, how is _Strideable related to compiler diagnostics for literals?

@xedin
Copy link
Member

xedin commented Jan 24, 2018

@xwu `0` literal is ExpressibleByIntegerLiteral which means that it can be any integral of floating-point type, and since you have operators involved in here because of the _Strideable conformance we might have been picking a different overload. "arithmetic operation 'x + 1' (on T) results in an overflow" error happens down the line from type-checker (in think on the SIL optimizer stage).

@xwu
Copy link
Collaborator Author

xwu commented Jan 24, 2018

There aren't any operators involved in the second example, nor in the case of 0.magnitude cited in the other bug report. I'm struggling to see the connection here as there should be nothing attempting to add 1 (of any type).

Moreover, the same bug is triggered without literals, as Int(),magnitude will apparently cause the same error, so it appears not to be a type inference issue.

It seems the compiler is trying to compute the value 0 by performing (in the case of UInt8) 255 + 1, which would work if instead it were 255 &+ 1, but this is in either case a curious thing to do behind the scenes for the value 0.

@xedin
Copy link
Member

xedin commented Jan 24, 2018

Sorry I only looked at the NumericAnnex examples you have in the description. `0.magnitude` is interesting but I don't think it has anything to do with type inference because 0 is inferred to be Int and 0.magnitude result is inferred as UInt and I can see that the whole expression type-checks effectively into `Int(0).magnitude` which then fails down the line in optimizer.

@moiseev
Copy link
Mannequin

moiseev mannequin commented Jan 24, 2018

/cc @eeckstein aschwaighofer@apple.com (JIRA User) shajrawi (JIRA User)

@stephentyrone
Copy link
Member

Xiaodi, are you still seeing these issues with 4.2?

@xwu
Copy link
Collaborator Author

xwu commented Oct 5, 2018

I'll test again this weekend. I've been delinquent in maintaining my projects lately.

@xwu
Copy link
Collaborator Author

xwu commented Oct 7, 2018

@stephentyrone Yes, these issues are still manifesting with 4.2.

@stephentyrone
Copy link
Member

@xwu can you provide a self-contained example of the failures that you're seeing? The code snippets provided in the bug description here are not sufficient to see what's going wrong.

@xwu
Copy link
Collaborator Author

xwu commented Oct 8, 2018

OK, here's a self-contained example. Apologies that it's not reduced further. Interestingly, my not-at-all kosher use of '@_transparent' here is required to expose the problem.

import XCTest

extension UnsignedInteger {
  public static func gcd(_ a: Self, _ b: Self) -> Self {
    // An iterative version of Stein's algorithm.
    if a == 0 { return b }
    if b == 0 { return a }
    var a = a, b = b, shift = 0 as Self
    while ((a | b) & 1) == 0 {
      a >>= 1
      b >>= 1
      shift += 1
    }
    while (a & 1) == 0 { a >>= 1 }
    repeat {
      while (b & 1) == 0 { b >>= 1 }
      if a > b { swap(&a, &b) }
      b -= a
    } while b != 0
    return a << shift
  }
}

public struct Rational<T : SignedInteger> where T.Magnitude : UnsignedInteger {
  public var numerator: T
  public var denominator: T

  @_transparent
  public init(numerator: T, denominator: T) {
    self.numerator = numerator
    self.denominator = denominator
  }
}

extension Rational {
  @_transparent
  public var isCanonical: Bool {
    if denominator > 0 {
      return T.Magnitude.gcd(numerator.magnitude, denominator.magnitude) == 1
    }
    return denominator == 0 && numerator.magnitude <= 1
  }
}

public typealias Ratio = Rational<Int>

XCTAssertFalse(Ratio(numerator: 2, denominator: 0).isCanonical)
// Error: Arithmetic operation '18446744073709551615 + 1' (on unsigned 64-bit integer type) results in an overflow

@stephentyrone
Copy link
Member

OK, that's really weird, and it's not totally obvious that this is even a stdlib bug; there's no explicit addition in the code, and we get this failure at compile time, not runtime. @xedin any idea what's happening here?

@stephentyrone
Copy link
Member

@xwu This continues to be really weird, but it does not reproduce on master, and 0.magnitude behaves as expected there as well (it does reproduce on 4.2). I can't point to exactly what changed or when, but I think that this is fixed. If you have the interest, adding a couple test cases to make sure this doesn't regress might be worthwhile.

@stephentyrone
Copy link
Member

@eeckstein Any idea what changed to resolve this? We see it in 4.2 but not master, and you've made some semi-recent changes to ConstantFolding.cpp.

@eeckstein
Copy link
Member

Sorry, no idea

@xedin
Copy link
Member

xedin commented Oct 9, 2018

While working on SE-0213 I've encountered a problem with magnitude as well, it's a related to constant propagation algorithm (it being too eager), I've changed magnitude to @transparent and then back to `@inline(__always)` #18039 but instead of using + I used &+ by @xwu recommendation, that's why it's fixed on master but not in 4.2 branch.

@stephentyrone
Copy link
Member

Interesting. Why is constant propagation is evaluating the unused side of a ternary? Naively I would think that it would evaluate the condition first and short-circuit if it can.

@xedin
Copy link
Member

xedin commented Oct 9, 2018

Yes, that's exactly what I have expected as well! ravikandhadai (JIRA User) has investigated it and says that it would require a lot of work to make it that way...

@moiseev
Copy link
Mannequin

moiseev mannequin commented Oct 9, 2018

@stephentyrone my recollection of discussions with Erik back when we discovered it is: constant propagation just had not been implemented to differentiate between branches, it tries to simplify all the code, even the branches-not-taken.

@stephentyrone
Copy link
Member

@xedin @moiseev ravikandhadai (JIRA User) do you know if we have a bug tracking that? I'm prepared to consider this one resolved, but we should keep a SR around for making constant propagation do the right thing with the original expression.

@moiseev
Copy link
Mannequin

moiseev mannequin commented Oct 9, 2018

FWIW I did not raise any bugs/radars for that issue. Perhaps @xedin did.

@swift-ci
Copy link
Collaborator

swift-ci commented Oct 9, 2018

Comment by Ravichandhran Kandhadai Madhavan (JIRA)

There is a radar tracking the bug: <rdar://39429767>

Yes @moiseev is right. Sadly, constant propagation does not identify infeasible branches, and @_transparent functions aggravate this problem. Hopefully, in the near future, we can make constant propagation use compile-time interpretation (#19579 and get rid of @_transparent functions.

@stephentyrone
Copy link
Member

Thanks. @xwu, I'm going to close this SR, as the issue reported here is resolved on master.

@stephentyrone
Copy link
Member

ravikandhadai (JIRA User) I put a note in the radar, but it seems like maybe we shouldn't report static overflows within conditionals unless we can prove that the path is taken. Does that seem reasonable?

@eeckstein
Copy link
Member

Some time ago I included constant folding into SimplifyCFG (commit 4f8cccf). This should solve the general problem (maybe with some more little changes in SimplifyCFG).
We just would have to run SimplifyCFG as mandatory pass. But we have to be careful to not compromise debug info.

Another option would be to implement sparse conditional constant propagation. It's on our to-do list for a while with low priority.
cc @dcci

@swift-ci
Copy link
Collaborator

Comment by Ravichandhran Kandhadai Madhavan (JIRA)

cc @stephentyrone

I wonder whether restricting to provably feasible paths would be very conservative e.g. if we have function calls along the CFG path, or if there are guards that are too complex for the constant folder to know that it is a constant etc. Perhaps, @eeckstein idea of treating every node in the Simplified CFG as feasible/reachable seems reasonable.

@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
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. regression standard library Area: Standard library umbrella swift 4.1
Projects
None yet
Development

No branches or pull requests

7 participants