The inactive list may contain other disjunctions associated with bound
type variables. For now, make sure we recover the orphan directly to
fix the crash in SR-4056 / rdar://problem/30686926. Later, we can
treat these as orphans, too.
The constraint graph models type variables (as the nodes) and
constraints (as the multi-edges connecting nodes). The connected
components within this (multi-)graph are independent subproblems that
are solved separately; the results from each subproblem are then
combined. The approach helps curtail exponential behavior, because
(e.g.) the disjunctions/type variables in one component won't ever be
explored while solving for another component
This approach assumes that all of the constraints that cannot be
immediately solved are associated with one or more type
variables. This is almost entirely true---constraints that don't
involve type variables are immediately simplified.
Except for disjunctions. A disjunction involving no type variables
would not appear *at all* in the constraint graph. Worse, it's
independence from other constraints could not be established, so the
constraint solver would go exponential for every one of these
constraints. This has always been an issue, but it got worse with the
separation of type checking of "as" into the "coercion" case and the
"bridging" case, which introduced more of these disjunctions. This led
to counterintuitive behavior where adding "as Foo" would cause the
type checking to take *more* time than leaving it off, if both sides
of the "as" were known to be concrete. rdar://problem/30545483
captures a case (now in the new test case) where we saw such
exponential blow-ups.
Teach the constraint graph to keep track of "orphaned" constraints
that don't reference any type variables, and treat each "orphaned"
constraint as a separate connected component. That way, they're solved
independently.
Fixes rdar://problem/30545483 and will likely curtain other
exponential behavior we're seeing in the solver.
When trying to solve for the test case we attempt to simplify a value
member constraint and it fails because we've bound the LHS type
variable to an optional as a result of other constraints involving
other type variables in the equivalence class of this type
variable.
We don't have enough information to directly deduce the non-optional
type directly from other constraints involving this type variable.
This change results in one interesting type checking anomoly. In Swift
3 mode, we now successfully typecheck an expression that we previously
did not. Although the type checking technically makes sense given the
type checking rules we have in place, it can be a bit surprising to
users. Fortunately we emit a warning that calls out the surprising
behavior of considering an expression unused.
Fixes rdar://problem/30271695.
Shrinking such expressions will immediately restrict the solution set
to the default literal types (Int or Double), causing later solutions
to fail. Fixes rdar://problem/30220565.
While shrinking constraint system, avoid candidates which contain
closures inside, because closure expressions require special handling
and allow no rollback.
Since `ConstraintSystem::shrink` is going to attempt to type-check
sub-expressions separately it's essential to clean-up AST if constraint
generation or solving of the such expressions fails, otherwise if
such solving resulted in creation of implicit expression type variables
might leak to the outside.
Since `ConstraintSystem::shrink` is going to attempt to type-check
sub-expressions separately it's essential to clean-up AST if constraint
generation or solving of the such expressions fails, otherwise if
such solving resulted in creation of implicit expression type variables
might leak to the outside.
This commit introduces new kind of requirements: layout requirements.
This kind of requirements allows to expose that a type should satisfy certain layout properties, e.g. it should be a trivial type, have a given size and alignment, etc.
Rather than waiting until we've used a huge amount of memory, attempt to
make the choice to bail out based on the number of type bindings /
disjunction choices we visit.
I expect this will generally fail faster than the Swift 3 metric, but
will still only fail when we've got clearly exponential type checking
behvior.
Since we have multiple sources of exponential behavior today, I don't
want to make the bounds too tight. Once we fix some/most of that
behavior we can look at further tightening up the metric.
We were only reporting it in cases where we found no solutions before
deciding the expression was too complex. Had we found some solution, we
would go ahead and use that solution before bailing out due to
complexity, which means e.g. we might have been allowing otherwise
ambiguous expression to type check.
Checked casts are dependent on run-time queries; we should not attempt
to infer type variable bindings from them, because doing so produces
unreasonable bindings. Fixes rdar://problem/29894174.
This gives us much better diagnostics around things like
escaping-mismatched function parameters which would previously skip
this and produce bogus invalid conversion errors between “identical”
types.
withoutActuallyEscaping has a signature like `<T..., U, V, W> (@nonescaping (T...) throws<U> -> V, (@escaping (T...) throws<U> -> V) -> W) -> W, but our type system for functions unfortunately isn't quite that expressive yet, so we need to special-case it. Set up the necessary type system when resolving an overload set to reference withoutActuallyEscaping, and if a type check succeeds, build a MakeTemporarilyEscapableExpr to represent it in the type-checked AST.
Previously, bridging conversions were handled as a form of "explicit
conversion" that was treated along the same path as normal
conversions in matchTypes(). Historically, this made some
sense---bridging was just another form of conversion---however, Swift
now separates out bridging into a different kind of conversion that is
available only via an explicit "as". This change accomplishes a few
things:
* Improves type inference around "as" coercions. We were incorrectly
inferring type variables of the "x" in "x as T" in cases where a
bridging conversion was expected, which cause some type inference
failures (e.g., the SR-3319 regression).
* Detangles checking for bridging conversions from other conversions,
so it's easier to isolate when we're applying a bridging
conversion.
* Explicitly handle optionals when dealing with bridging conversions,
addressing a number of problems with incorrect diagnostics, e.g.,
complains about "unrelated type" cast failures that would succeed at
runtime.
Addresses rdar://problem/29496775 / SR-3319 / SR-2365.
Changes:
* Terminate all namespaces with the correct closing comment.
* Make sure argument names in comments match the corresponding parameter name.
* Remove redundant get() calls on smart pointers.
* Prefer using "override" or "final" instead of "virtual". Remove "virtual" where appropriate.
Once we've bound a type variable, we find those inactive constraints
that mention the type variable and make them active, so they'll be
simplified again. However, we weren't finding *all* constraints that
could be affected---in particular, we weren't searching everything
related to the type variables in the equivalence class, which meant
that some constraints would not get visited... and we would to
type-check simply because we didn't look at a constraint again when we
should have.
Fixes rdar://problem/29633747.
Instead of relying on the SolverScope to rollback all of the changes
done to constraints in the system at the end of its life time, move
all of the logic handling that into SolverState where retired/generated
constraints live.
Since retired constraints are re-added back to the circulation in LIFO
order, make sure that all of the constraints are added to the front of
SolverScope::retiredConstraints list.
Update CSGen/CSApply/CSSolver to primarily use getType() from
ConstraintSystem.
Currently getType() just returns the type on the expression. As with
setType(), which continues to set the type on the expression, this
will be updated once all the other changes are in place.
This change also moves coerceToRValue from TypeChecker to
CosntraintSystem so that it can access the expression type map in the
constraint system.
Make SolverState manage whether the ConstraintSystem it belongs to has a
current SolverState.
Also a couple minor formatting fixes for ternary expressions involving
solverState.
Simplify some control-flow to reduce indentation and eliminate an
unneeded flag variable.
Also update a comment to match the code that went in with
b5500b8600.
The constraint solver tries not to solve for type variables that
"involve other type variables", which handles the case where we have
seen a constraint that mentions the type variable under consideration
as well as a different type variable, but in a constraint that we
cannot capture in a binding. Solving for such type variables too early
can lead to missed solutions, so we avoid it.
Tweak the logic for this computation to not consider type variables
mentioned within dependent member types (e.g., $T0.Iterator.Element),
because such types do not affect type inference at all, and therefore
shouldn't prevent solving for the type variable in question.
In the constraint solver, we've traditionally modeled nested type via
a "type member" constraint of the form
$T1 = $T0.NameOfTypeMember
and treated $T1 as a type variable. While the solver did generally try
to avoid attempting bindings for $T1 (it would wait until $T0 was
bound, which solves the constraint), on occasion we would get weird
behavior because the solver did try to bind the type
variable.
With this commit, model nested types via DependentMemberType, the same
way we handle (e.g.) the nested type of a generic type parameter. This
solution maintains more information (e.g., we know specifically which
associated type we're referring to), fits in better with the type
system (we know how to deal with dependent members throughout the type
checker, AST, and so on), and is easier to reason able.
This change is a performance optimization for the type checker for a
few reasons. First, it reduces the number of type variables we need to
deal with significantly (we create half as many type variables while
type checking the standard library), and the solver scales poorly with
the number of type variables because it visits all of the
as-yet-unbound type variables at each solving step. Second, it
eliminates a number of redundant by-name lookups in cases where we
already know which associated type we want.
Overall, this change provides a 25% speedup when type-checking the
standard library.
