averello/swift-mirror
1
0
Fork 0
mirror of https://github.com/apple/swift.git synced 2025-12-14 20:36:38 +01:00
Code Issues Packages Projects Releases Wiki Activity
179,023 Commits 622 Branches 2,942 Tags
weird-codegen
Commit Graph

174 Commits

Author SHA1 Message Date
Slava Pestov
bed95dd1a4 Sema: Simplify PotentialBindings updates a little 2025-01-15 22:30:34 -05:00
Slava Pestov
1aff26eaa6 Sema: Store BindingSet inside the ConstraintGraphNode 
Building the DenseMap in determineBestBindings() is extremely
expensive.

Also rename getCurrentBindings() to getPotentialBindings().
 2025-01-15 22:30:32 -05:00
Slava Pestov
25ad700fb0 Sema: Simplify depthFirstSearch() a bit now that it only has one caller 2024-12-21 00:42:13 -08:00
Slava Pestov
9fb6d9251e Sema: Remove DependentComponentSplitterStep 2024-12-21 00:42:13 -08:00
Slava Pestov
dd3e49c3ac Sema: Remove one-way constraint handling from computeConnectedComponents() 2024-12-21 00:42:13 -08:00
Slava Pestov
0c128e5db7 Sema: Optimize ConstraintGraph::computeConnectedComponents() 
Instead of starting a depth-first search from each type variable
and marking all type variables that haven't been marked yet,
we can implement this as a union-find.

We can also store the temporary state directly inside the
TypeVariableType::Implementation, instead of creating large
DenseMaps whose keys range over all type variables.
 2024-12-18 17:30:43 -05:00
Slava Pestov
45346c8389 Sema: Remove ConstraintGraph::TypeVariables 2024-12-18 17:30:34 -05:00
Slava Pestov
60d34a4162 Sema: Micro-optimize PotentialBindings 
PotentialBindings is part of ConstraintGraphNode and there's no need
to store the ConstraintSystem and TypeVariableType twice.

Also it doesn't need to be optional either, because we no longer need
to reset and recompute bindings.
 2024-11-20 13:35:22 -05:00
Slava Pestov
1bdf7f0192 Sema: Assert that the constraint graph node is empty before recycling 2024-11-20 13:35:22 -05:00
Slava Pestov
1a18d70f90 Sema: Remove ConstraintSystem::SolverState::isRecordingChanges() 
All but two remaining call sites can be changed to just check for a
non-null solverState, because we want to assert if we're inside
of an active undo.

The two places inside binding inference can check isUndoActive()
directly.
 2024-11-20 13:35:22 -05:00
Slava Pestov
24de22a078 Sema: Split off ConstraintGraph::addTypeVariable() from ::operator[] 
Also, since we add a vertex immediately after introducing a new type
variable, the code path to handle the case where the type variable
had a parent or fixed type was actually dead.
 2024-11-20 13:35:21 -05:00
Slava Pestov
b760cfd03d Sema: Fold ConstraintGraph::lookupNode() into ::operator[] 
lookupNode() returned a pair but both callers only looked at the
first element of the pair.
 2024-11-20 08:23:58 -05:00
Slava Pestov
a19c92a4e0 Sema: Extract duplication from ConstraintGraph::introduceTo/retractFromInference(Type) overloads 2024-11-19 21:24:13 -05:00
Slava Pestov
1a60685292 Sema: Address the FIXME in ConstraintGraph::mergeNodes() 2024-11-19 21:24:12 -05:00
Slava Pestov
5690addb4e Sema: Fix ordering of constraint graph updates vs fixed type assignment 2024-11-19 21:24:12 -05:00
Slava Pestov
0d3d31599f Sema: Remove ConstraintGraph::reintroduceToInference() 2024-11-19 21:24:12 -05:00
Slava Pestov
338ad3062d Sema: Tighten an invariant in ConstraintGraph 
These functions are never called while undoing a change; so
we want to assert if we have an active undo instead of
silently not recording the change.
 2024-10-22 20:14:43 -04:00
Slava Pestov
3a4de0b953 Sema: Optimize computeConnectedComponents() 
If there is only one connected component, we don't actually have
to form the array of components at all. Re-organize the code so
that we can short-circuit this decision as soon as possible.
 2024-10-10 17:05:30 -04:00
Slava Pestov
cdc2145ad5 Sema: Use existing utility function 2024-10-09 11:48:08 -04:00
Slava Pestov
892e79cd70 Sema: Use an xmacro to clean up some duplication in CSTrail.cpp 2024-10-07 16:50:46 -04:00
Slava Pestov
31edb86da9 Sema: Remove ConstraintGraphNode::resetBindingSet() 2024-09-30 22:14:09 -04:00
Slava Pestov
186589bd25 Sema: Remove SolverTrail::Change::introducedToInference() 2024-09-30 22:05:41 -04:00
Slava Pestov
c46ee87408 Sema: Simplify ConstraintGraph::addConstraint() and ::removeConstraint() 2024-09-30 22:00:14 -04:00
Slava Pestov
2caf2e001f Sema: Simplify ConstraintGraphNode::truncateEquivalenceClass() 2024-09-30 21:31:43 -04:00
Slava Pestov
6652e34f55 Sema: Add SolverTrail::Change::InferredBindings and ::RetractedBindings 2024-09-30 21:29:59 -04:00
Slava Pestov
b885c29f71 Sema: Split up SolverTrail::Change::AddedConstraint and ::RemovedConstraint 2024-09-30 21:29:59 -04:00
Slava Pestov
ae53c8e7ff Sema: Split up SolverTrail::Change::BoundTypeVariable 2024-09-30 15:09:38 -04:00
Slava Pestov
148033930c Sema: Split off introduceToInference() into its own Change 
Previously, retractFromInference() was the last step in
unbindTypeVariable(). This doesn't really make sense,
because bindTypeVariable() doesn't call introduceToInference();
its two callers do it later.

Start untangling this by splitting off introduceToInference()
into its own Change, but for now, record this change at the
incorrect place to maintain the same behavior as before.
 2024-09-29 21:46:41 -04:00
Slava Pestov
c0afe3fce1 Sema: Don't create new ConstraintGraphNode during active undo 
This messes up the bookkeeping for the trail.
 2024-09-27 10:51:47 -04:00
Slava Pestov
4ef30a4b47 Sema: Recycle ConstraintGraphNode 2024-09-27 01:30:13 -04:00
Slava Pestov
cab698216f Sema: Fancier assertions in ConstraintGraph 2024-09-26 23:15:27 -04:00
Slava Pestov
105b6b39a9 Sema: Remove ConstraintGraphScope 2024-09-26 23:15:27 -04:00
Slava Pestov
4cc27c9b20 Sema: Factor out SolverTrail from ConstraintGraph 2024-09-26 23:15:26 -04:00
Tim Kientzle
1d961ba22d Add #include "swift/Basic/Assertions.h" to a lot of source files 
Although I don't plan to bring over new assertions wholesale
into the current qualification branch, it's entirely possible
that various minor changes in main will use the new assertions;
having this basic support in the release branch will simplify that.
(This is why I'm adding the includes as a separate pass from
rewriting the individual assertions)
 2024-06-05 19:37:30 -07:00
Timofey Solonin
3f366947e4 Improve indentation in debugging output 2022-11-17 23:25:31 +08:00
Amritpan Kaur
a4a72075fd [ConstraintGraph] Correct dis/conjunction indents. 2022-09-13 10:45:15 -07:00
Amritpan Kaur
01ea11b34a [ConstraintGraph] Collect and print changes in current Active Scope. 2022-08-21 09:27:25 -07:00
Amritpan Kaur
fd41a39294 [ConstraintSystem] Refactor solver state depth to its own function for easier indent editing in future. 2022-08-10 13:29:02 -07:00
Josh Soref
4c77c59269 Spelling sema (#42474) 
* spelling: accessibility

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: accessories

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: adjustments

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: all

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: ambiguous

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: arguments

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: assignment

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: associated

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: assumes

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: auxiliary

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: availability

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: available

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: belongs

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: checking

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: clazz

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: compatibility

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: completely

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: completion

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: complicated

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: conformance

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: constrained

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: constraint

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: contextual

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: conversion

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: convertible

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: couldn't

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: declaration

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: defaultable

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: dependent

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: depending

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: describe

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: diagnostic

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: diagnostics

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: existential

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: expects

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: explicit

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: explicitly

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: expression

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: first

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: font

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: forward

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: generation

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: generic

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: given

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: global

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: guarantee

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: happened

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: hierarchy

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: identical

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: immediately

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: implicit

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: indicates

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: inferred

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: initialization

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: initialize

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: initializer

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: integrity

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: interpolation

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: introducing

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: involved

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: just

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: like

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: likewise

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: mismatch

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: missing

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: more

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: necessarily

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: noescape

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: nonetheless

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: occurrences

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: operators

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: optional

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: otherwise

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: outside

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: overload

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: overridden

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: override

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: parameter

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: parameters

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: penalize

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: platforms

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: precedence

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: preemptively

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: preliminary

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: preserve

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: propagate

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: propagated

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: qualifier

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: question

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: really

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: received

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: references

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: replaceable

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: replacement

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: representable

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: representative

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: requirement

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: requires

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: resolved

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: retrieve

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: rewriting

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: satisfied

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: semantics

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: signature

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: similar

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: simplest

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: simplification

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: solver

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: struct

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: structurally

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: success

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: sure

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: symmetric

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: syntactically

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: target

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: that

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: the

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: themselves

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: these

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: this

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: transform

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: transparent

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: tread

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: truncation

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: type

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: unconstructable

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: universally

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: unknown

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: unwrapped

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: versioned

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: visible

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

* spelling: where

Signed-off-by: Josh Soref <jsoref@users.noreply.github.com>

Co-authored-by: Josh Soref <jsoref@users.noreply.github.com>
 2022-04-20 15:12:46 -07:00
Pavel Yaskevich
6a85650573 [ConstraintSystem] Don't attempt to rollback state and scope from incorrect state 2021-08-06 12:32:17 -07:00
Pavel Yaskevich
7e022b27c1 [ConstraintGraph] Don't notify referenced var if constraint is not useful 
Performance optimization that skips notifying referenced variables
if it's clear that the constraint is not going to be useful for them.
 2021-06-09 15:59:21 -07:00
Pavel Yaskevich
5fd722ced9 [ConstraintGraph] NFC: Remove commented code from {introduceTo, retractFrom}Inference 2021-06-08 17:43:05 -07:00
Pavel Yaskevich
12e9686765 [ConstraintGraph] Remove flags from inference methods 
Use newly added `notifyReferencedVars` in `{add, remove}Constraint`.
 2021-06-07 14:35:15 -07:00
Pavel Yaskevich
d4cb7564a3 [ConstraintGraph] Extract logic to notify referenced variable into a dedicated method 2021-06-07 14:18:51 -07:00
Ikko Ashimine
2d702b86ca [ConstraintGraph] Fix typo 
absense -> absence
 2021-04-24 09:59:35 +09:00
Pavel Yaskevich
109a33cf2b Merge pull request #36220 from xedin/optimize-edge-contraction 
[ConstraintGraph] Optimize edge contraction
 2021-03-03 10:26:47 -08:00
Pavel Yaskevich
c5695c2c03 [ConstraintGraph] NFC: Convert shouldContractEdge into a closure since it's only used by contractEdges 2021-03-01 17:33:33 -08:00
Pavel Yaskevich
0cc0a3a5f1 [ConstraintGraph] Optimize edge contraction 
Previously on every step solver would iterate over all
constraints in attempt to find `BindParam` which could
be contracted. Instead of doing that, let's take advantage
of the fact that all (participating) closures are recorded
in the constraint system during constraint generation, so
it should be possible to check either outer parameter types
are contractable with their inner uses.
 2021-03-01 17:23:14 -08:00
Pavel Yaskevich
ca16c3796e [ConstraintGraph] Don't propagate to referenced vars 
Just like regular `Bind` constraint `BindOverload` contains no
useful information for referenced type variables.
 2021-03-01 10:52:29 -08:00
Pavel Yaskevich
b487b6956b [ConstraintSystem] Delay inference until let's clear that type variable attempt is successful 
Currently bindings where inferred on every `bindTypeVariable` call,
but that's wasteful because not all binds are always correct. To
avoid unnecessary inference traffic let's wait until re-activated
constraints are simplified and notify binding inference about new
fixed type only if all of them are successful.
 2021-03-01 10:52:29 -08:00