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.
In these cases, we should just go ahead and remove the redundant constraints:
- They don't help us derive a solution for the system
- Not doing so might leave "dangling" constraints that will make the system unsolvable
This eliminates the duplication of type variables that represent the member types of existing type variables. I'm unable to trigger this with a test case at the moment, but it becomes important when we begin to substitute type variables through protocol conformances.
Swift SVN r12971
Provides a 4% speedup type-checking the standard library. This
optimization brings the global constraint graph within 2% of the prior
solution, and prevents us from creating multiple constraint graphs per
constraint system, so flip the switch to always use the global
constraint graph.
Swift SVN r11003
Whenever we bind a type variable or merge two type variables, add
those constraints that could be affected to a worklist. Simplification
continues processing constraints in the worklist until the worklist is
empty.
This change reduces the number of constraints that we visit but can't
simplify by ~13x in the standard library, but this doesn't translate
into a performance win. More investigation is needed here.
Note that the worklist is only in use when we have a global constraint
graph, which isn't enabled by default yet.
Swift SVN r10936
Make the constraint graph into a scoped data structure that tracks the
changes that occur within a given scope, undoing those changes when
the scope is popped off the scope stack. The constraint graph's scopes
align with the constraint solver's scopes. Synchronize the solver's
constraint addition/removal operations with the constraint graph, and
improve our verification to make sure these stay in sync.
This is still a work in progress. Type checking the standard library
is about 5% slower with the per-constraint-system constraint graph
rather than building a new constraint graph each iteration *after*
simplification, and there are two intruiging test failures that appear
to be the constraint solver breaking its own invariants. Therefore,
this feature is off by default. See the ConstraintSystem constructor
for the one-line change to turn it back on.
Swift SVN r10927
Rather than building the constraint graph after simplification and
then never modifying it, build the constraint graph before
simplification and update it as simplification adds/removes
constraints. This is a step toward two separable performance goals:
(1) having a single constraint graph that evolves over the lifetime of
the constraint system, rather than building a new constraint graph at
each solver step, and (2) using the constraint graph to implement a
worklist traversal during simplification, so we only re-simplify those
constraints that might be affected by a choice the solver makes.
This behavior is currently optional with an ugly in-source flag
because while it works, it's a rather painful performance regression
that I don't want to subject everyone to. I'll turn it on for everyone
once it's a win, which should be after either (1) or (2) above is
implemented.
Swift SVN r10924
Previously, the constraint graph only represented type variables that
were both unbound and were the representatives within their respective
equivalence classes. To achieve this, each constraint was fully
simplified when it was added to the graph, which is a fairly expensive
process. This representation made certain operations---merging two type
variables, replacing a type variable with a fixed type, etc---both
hard to implement and hard to reverse, forcing us to rebuild the
constraint graph each time.
Now, add all type variables to the graph (including those with fixed
type bindings and non-representatives) and add constraints without
simplification. Separately track the equivalence classes of each type
variable (in the representative's node) and adjacencies due to type
variables showing up in the fixed type bindings of other type
variables. Although not yet implemented, the merging and type variable
replacement operations are far easier to implement (and more
efficient) with this representation, and are also easier to undo,
making this a step toward creating and updating a single consistent,
global constraint graph rather than re-creating a constraint graph
during each solver step.
Performance-wise, this is a 4% regression when type-checking the
standard library. I expect to make that up easily once we switch to a
single constraint graph.
Swift SVN r10897
Using "T" as the contextual type, either for an implicit conversion
(in the coercion case) or as a downcast (for the checked-cast case),
opens up more type-inference opportunities. Most importantly, it
allows coercions such as "1 as UInt32" (important for
<rdar://problem/15283100>). Additionally, it allows one to omit
generic arguments within the type we're casting to.
Some additional cleanup to follow.
Swift SVN r10799
This currently-untestable code allows updates to the constraint graph
when a same-type constraint causes two type variables to be
unified. Additionally, it handles the removal of a constraint from the
constraint system, e.g., if it is solved.
Swift SVN r10716
At each solution phase, construct a constraint graph and identify the
smallest connected component. Only solve for the variables in that
connected component, and restrict simplification to the constraints
within that connected component. This reduces the number of
visited-but-not-simplified constraints by ~2x when type-checking the
standard library.
Performance-wise, this is actually a regression (0.25s/8% when parsing
the standard library), because the time spent building the constraint
graph exceeds the time saved by the optimization above.
The hackaround in the standard library is due to
<rdar://problem/15168483>. Essentially, this commit changes the order
in which we visit type variables, causing the type checker to make
some very poor deduction choices.
The point of actually committing this is that it validates the
constraint graph construction and sets the stage for an actual
optimization based on isolating the solving work for the different
components.
Swift SVN r10672
This implements an offline algorithm for connected components. We
could use an online algorithm, which would be slightly more efficient
in the case where we always require the connected components, but such
algorithms don't cope with edge removals very well.
Still just a debugging tool!
Swift SVN r10663
