Slava Pestov
7244102b4d
RequirementMachine: Wire up protocol requirement signature minimization
2021-10-09 19:11:14 -04:00
Slava Pestov
a4c2ad43ab
RequirementMachine: Use ProtocolDecl::getProtocolDependencies()
...
When using the requirement machine to build protocol signatures,
we can't get the protocol's dependencies by looking at the
conformance requirements in it's requirement signature, because
we haven't computed the requirement signature yet.
Instead, get the dependencies via the recently-added
getStructuralRequirements() request.
2021-10-08 19:38:48 -04:00
Slava Pestov
a5e680015a
Merge pull request #39646 from slavapestov/fix-rqm-reference-invalidation
...
RequirementMachine: Fix reference invalidation bug
2021-10-08 18:30:35 -04:00
Slava Pestov
94e9ab6713
RequirementMachine: Track parent paths when computing generating conformances
2021-10-08 14:28:27 -04:00
Slava Pestov
b47b2d3b03
RequirementMachine: Fix generating conformances
2021-10-08 14:28:27 -04:00
Slava Pestov
70233aceb7
RequirementMachine: Teach generating conformances to understand protocol refinement
...
For implementation reasons we want the requirement signature of a
protocol to directly include all protocol refinement relationships,
even if they can be derived via same-type requirements between Self
and some nested type.
Therefore, a protocol refinement rule [P].[Q] => [P] can only be
replaced with a generating conformance equation that consists
entirely of other conformance rules.
This exactly simulates the existing behavior of the GSB's redundant
requirements algorithm.
2021-10-08 14:28:27 -04:00
Slava Pestov
371366eb4b
RequirementMachine: Assert that non-redundant rules are fully resolved
2021-10-08 14:28:27 -04:00
Slava Pestov
14708adf5c
RequirementMachine: Move implementation of RequirementSignatureRequest out of Sema
...
For now, this still uses the GSB.
2021-10-08 14:28:27 -04:00
Slava Pestov
b8177995df
RequirementMachine: Sort requirements and canonicalize same-type requirements
2021-10-08 14:28:27 -04:00
Slava Pestov
566971dbc2
RequirementMachine: Add some comments and assertions around state transitions
2021-10-08 14:28:27 -04:00
Slava Pestov
526feebb8d
RequirementMachine: Fix reference invalidation bug
...
After forming a reference to an entry in a DenseMap, we have to be
careful not touch the reference after calling any code which might
re-entrantly invalidate the reference by mutating the DenseMap.
Fixes rdar://problem/83891298.
2021-10-07 22:38:01 -04:00
Slava Pestov
2335116aee
Merge pull request #39606 from slavapestov/rqm-requirement-signature-minimization
...
RequirementMachine: More progress toward computing protocol requirement signatures
2021-10-06 13:19:08 -04:00
Slava Pestov
62de909801
RequirementMachine: Some comments
2021-10-06 00:20:18 -04:00
Slava Pestov
03dfa60edd
RequirementMachine: Initial implementation of requirement minimization
2021-10-06 00:11:21 -04:00
Slava Pestov
760efcafd8
RequirementMachine: When building a requirement signature system, remember the protocols
2021-10-06 00:11:21 -04:00
Slava Pestov
acb12fa750
RequirementMachine: More complete implementation of findProtocolConformanceRules()
2021-10-06 00:11:21 -04:00
Slava Pestov
c3270742dc
RequirementMachine: Compute strongly connected components from the protocol dependency graph
2021-10-05 21:30:57 -04:00
Slava Pestov
17e2d6a290
RequirementMachine: Avoid term->type->term round-trip in getConformanceAccessPath()
...
We would skip recording a conformance access path if the subject
type canonicalized to a concrete type, but this was incorrect.
The correct formulation is to use the _canonical anchor_ and not
the canonical type as the caching key; that is, we always want it
to be a type parameter, even if it is fixed to a concrete type,
because type parameters fixed to concrete types can appear in
the middle of conformance access paths, as the example in the
radar demonstrates.
Fixes rdar://problem/83687967.
2021-10-05 15:06:42 -04:00
Slava Pestov
9fb2897953
RequirementMachine: Make Terms work as DenseMap keys
2021-10-05 15:06:42 -04:00
Slava Pestov
e7b0b1b35d
RequirementMachine: Right-hand side simplification produces more aesthetically-pleasing 3-cells
2021-10-01 00:57:44 -04:00
Slava Pestov
62c9347d3b
RequirementMachine: Overhaul generating conformances algorithm
2021-10-01 00:57:44 -04:00
Slava Pestov
2db676d41a
RequirementMachine: Homotopy reduction deletes rules with unresolved name symbols first
2021-10-01 00:57:44 -04:00
Slava Pestov
871b4d143a
RequirementMachine: Cosmetic fix for conformance path assert output
2021-10-01 00:57:35 -04:00
Slava Pestov
86ee6c2f55
RequirementMachine: Add some comments
2021-10-01 00:56:50 -04:00
Slava Pestov
916249ef73
RequirementMachine: Fix -debug-requirement-machine=simplify output
2021-10-01 00:56:50 -04:00
Slava Pestov
a46a7b893f
RequirementMachine: Check that homotopy reduction was able to eliminate all redundant conformances
2021-10-01 00:56:50 -04:00
Slava Pestov
34592cb2fa
RequirementMachine: Fix generating conformances algorithm for rules of the form [P].[P] => [P]
2021-10-01 00:56:50 -04:00
Slava Pestov
3f8ef30185
RequirementMachine: Preserve sugared generic params in getSuperclassBound() and getConcreteType()
...
This was manifesting as module interfaces printing generic parameters
as `τ_0_0` in some cases.
Note that the GSB has the same bug, so this test case will fail with
-requirement-machine=off. I don't plan on fixing the bug in the GSB
unless we need to.
Fixes rdar://problem/78977127.
2021-09-29 14:39:38 -04:00
Slava Pestov
a0f4484127
RequirementMachine: Don't forget to delete requirement machines when freeing the RewriteContext
2021-09-28 13:52:33 -04:00
Slava Pestov
46063d3925
Merge pull request #39476 from slavapestov/rqm-avoid-hashtable-lookup
...
AST: GenericSignatures point directly to their RequirementMachine
2021-09-28 00:18:03 -04:00
Slava Pestov
47ab4a9f28
AST: GenericSignatures point directly to their RequirementMachine
...
This avoids a hashtable lookup when performing queries.
2021-09-27 21:36:45 -04:00
Slava Pestov
64d1931e15
RequirementMachine: Sketch out "generating conformances" algorithm
2021-09-27 19:04:16 -04:00
Slava Pestov
5f3d781ed3
RequirementMachine: Homotopy reduction tweaks
...
- Skip permanent rules (there's no point, we'll add them back next time)
- Skip conformance rules (these will be handled separately)
- Delete 3-cells that are entirely "in-context" (but don't quote me on
this one, I'm not quite yet convinced it's correct, but it feels right)
2021-09-27 19:03:34 -04:00
Slava Pestov
2923a334f5
RequirementMachine: Remove unused method
2021-09-27 19:03:30 -04:00
Slava Pestov
7ad0c3cc79
RequirementMachine: Add a mode allowing unresolved name symbols in rewrite rules
2021-09-27 19:03:26 -04:00
Slava Pestov
2b068b3c48
RequirementMachine: Encapsulate 3-cells in a new HomotopyGenerator data type
2021-09-24 08:59:51 -04:00
Slava Pestov
5210e5d475
RequirementMachine: Remove some debugging code
2021-09-24 08:59:51 -04:00
Slava Pestov
99dab70840
RequirementMachine: Mark associated type introduction rules permanent
2021-09-24 08:59:51 -04:00
Slava Pestov
8fbe93c469
RequirementMachine: Rename Rule::isDeleted() => isSimplified(), and add isPermanent(), isRedundant() bits
2021-09-24 08:59:51 -04:00
Slava Pestov
1fa36c70c6
RequirementMachine: Factor out Rule::isPropertyRule() from the property map
2021-09-24 08:59:51 -04:00
Slava Pestov
67fad897ab
RequirementMachine: Compute left canonical forms of paths
2021-09-24 08:59:51 -04:00
Slava Pestov
5f03c737d2
RequirementMachine: Preliminary implementation of homotopy reduction
2021-09-24 08:59:50 -04:00
Slava Pestov
c6403e65e1
RequirementMachine: RewriteStep stores both whiskers
2021-09-24 08:59:50 -04:00
Slava Pestov
5cbfbae536
RequirementMachine: Represent concrete type adjustment in a rewrite path
2021-09-24 08:59:50 -04:00
Slava Pestov
b317a5c5ee
RequirementMachine: Verify homotopy generators
2021-09-24 08:59:50 -04:00
Slava Pestov
a75327e6b1
RequirementMachine: Record homotopy generators when adding new rules during completion
2021-09-24 08:59:50 -04:00
Slava Pestov
65e9dd1161
RequirementMachine: Trie.insert() updates existing entry
2021-09-24 08:59:50 -04:00
Slava Pestov
866a04905b
RequirementMachine: When simplifying right hand sides, add new rules instead of mutating
...
We need to keep the original rules around for homotopy generators.
2021-09-24 08:59:50 -04:00
Slava Pestov
b2a21b3117
RequirementMachine: Preliminary plumbing for computing homotopy generators
2021-09-24 08:59:50 -04:00
Slava Pestov
e4f6128990
RequirementMachine: Don't simplify terms inside concrete substitutions when adding a rule
...
The effect of doing this is difficult to represent with homotopy generators,
so let's just not bother.
2021-09-24 08:59:50 -04:00
