`FreeTypeVariableBinding::GenericParameters` mode allowed to bind
all free type variables with fresh generic parameter types, which
is incorrect (at least) if there are multiple generic solutions
present, because such parameters couldn't be compared.
This mode was used for code completion, which is now switched to use
`FreeTypeVariableBinding::UnresolvedType` instead.
Add additional checking for complexity of the shrinking candidate
given the number of the expressions solved so far and total number
of disjunctions present. This allows us to bail quicker in complex
expression cases which, at the very least, produces an error instead
of being "stuck" in solver for a long time.
Resolves: rdar://problem/32034560
Consolidate some of the attributes and operations common to disjunction choice
in new `DisjunctionChoice` class, which simplifies implementation of the
`ConstraintSystem::solveSimplified` method related to overload selection.
The old TVO_MustBeMaterializable is now equivalent to
!TVO_CanBindToLValue && !TVO_CanBindToInOut.
I tried to update all usages of createTypeVariable() to
pass TVO_CanBindToInOut unless they explicitly passed
TVO_MustBeMaterializable before.
However, in reality TVO_CanBindToInOut is the rare case;
we can remove this flag gradually over time to fix
crashes and diagnostics.
The openType() function did two things:
- Replace unbound generic types like 'G' with fresh type variables
applied to bound generic types, like 'G<$T0>'.
- Replace generic parameters with type variables from the replacement
map.
The two behaviors were mutually exclusive and never used from the
same call site, so split them up into two independent functions.
Also, eliminate ConstraintSystem::openBindingType() since it was only
used in one place and could be expressed in terms of existing functions.
Add logging before solving each of the candidates considered for
shrinking with information about sub-expression and new constraint system.
At the end of the candidate solving print each of the produced solutions.
This reverts commit
ecfa406fc5, which was reinstating
3c5b393e0c.
It does not revert one test change from that commit, because
inexplicably one of the tests is still failing, probably due to some
other changes that have happened since. I'm leaving a ticket open to
investigate.
I've added one of the new cases that is failing as a result of this
change.
This is being reverted not because of bugs in this particular commit,
but because it seems to be exposing other bugs in the type checker that
are resulting in source compatibility problems. We need to shake these
other bugs out of the type checker before bringing this change back.
The "skip generic operators" heuristic within the constraint solver is
fairly awful, because it is known to miss reasonable solutions. Make
is slightly more narrow by only skipping generic operators when the
concrete operator we found was symmetric.
It is useful to set a breakpoint on ErrorType::get(ASTContext)
to see what is going wrong immediately instead of after the
fact when an ErrorType pops up where you don't expect it.
Unfortunately associated type inference, domain shrinking and
the type cleanup RAII utility would all build ErrorTypes even
with valid code.
Refactor things a bit so that this is no longer the case; at
least now the standard library and overlays build with
'assert(false)' inserted into ErrorType::get(ASTContext).
ErrorType::get(Type) is still expected to come up in associated
type inference since it is used as a signal while sorting
through potential type witness candidates.
Recent changes to the stdlib resulted in some expressions involving
literals and operators that have both generic and non-generic overloads
to become ambiguous. The ambiguity is due to an old performance hack in
the solver which unfortunately needs to remain in place at the moment to
avoid regressing expression type checker performance.
This commit changes the performance hack a bit in that instead of
stopping visiting the options in a disjunction as soon as we have a
solution involving non-generic operators and come across a constraint
involving generic operators, we instead continue visiting the elements
in the disjunction, but just skip over the generic operators.
Fixes rdar://problem/31695865 and rdar://problem/31698831.
We previously used a simple heuristic of visiting the disjunction with
the fewest number of elements in it.
Instead, this commit introduces a new way to select the best disjunction
to explore based on attempting disjunctions based on either how much
information we have about the associated type variables (e.g. how many
of the arguments of a function call in the case of bind overload
disjunctions) or by other criteria that help constraint the search or
split the connected components (e.g. coercions and calls to
initializers).
A key part of the improvement here is allowing the type checker to
attempt bindings of types to type variables when there are still
argument conversion constraints between type variables in the
system. The insight here is if there are no other constraints blocking
an attempt to bind types and we have types to try, we will be able to
test those types against active conformance constraints and potentially
fail much earlier while solving.
Visiting disjunctions in a different order exposed some other problems
with the type checker including a couple cases where map is used that
are now considered ambiguous due to problems in how we are ranking
solutions.
I measured an 11-13% reduction in type checking time for the standard
library using a release build of the compiler.
When determining whether our inference of an optional type should add
a layer of optionality, look through lvalue types.
Fixes rdar://problem/31779785.
We have various hacks in the constraint solver to improve the
compile-time performance characteristics of operators. Some of those
didn't respect availability annotations, causing us to incorrectly
choose an unavailable operator when available options exist.
Fixes rdar://problem/31592529.
There were various problems with layout constraints either
being ignored or handled incorrectly. Now that I've exercised
this support with an upcoming patch, there are some fixes
here.
Also, introduce a new ExistentialLayout::getLayoutConstriant()
which returns a value for existentials which are class-constrained
but don't have a superclass or any class-constrained protocols;
an example would be AnyObject, or AnyObject & P for some
non-class protocol P.
NFC for now, since these layout-constrained existentials cannot
be constructed yet.
This is an initial implementation of the constraint propagation pass,
disabled by default at the moment as it does not currently pass all
tests.
I have other changes that I'll hold off on for now because they are
incomplete. Without those changes, this pass doesn't really achieve
much, so this is really just a checkpoint on some progress and not
something really worth trying out at this point.
As solveRec() already does, exit immediately if we have a failed
constraint from constraint generation. Not doing so means that we can
create a SolverScope in constraint propagation, and on destruction of
that SolverScope we clear out the failedConstraint field, obscuring the
fact that we had a failure.
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.
