Skip to content

Commit dc8904b

Browse files
safesparrowsafesparrow
committed
Update docs
1 parent 8909b7e commit dc8904b

1 file changed

Lines changed: 32 additions & 2 deletions

File tree

  • tests/FSharp.Compiler.Service.Tests2

‎tests/FSharp.Compiler.Service.Tests2/Docs.md‎

Lines changed: 32 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -146,7 +146,7 @@ This is the approach we're taking.
146146
The dependency detection algorithm can be summarised as follows:
147147
1. For each parsed file in parallel:
148148
1. Extract its top-level module or a list of top-level namespaces
149-
2. Find all partial module references in the AST by traversing it once.
149+
2. Find all partial module references in the AST by traversing it once. Consider `AutoOpens`, module abbreviations, partial opens etc.
150150
2. Build a single [Trie](https://en.wikipedia.org/wiki/Trie) by adding all top-level items extracted in 1.i. Every module/namespace _segment_ (eg. `FSharp, Compiler, Service in FSharp.Compiler.Service`) is represented by a single edge in the Trie. Note down positions of all added files in the Trie.
151151
3. For each file in parallel:
152152
1. Clone the Trie.
@@ -160,6 +160,36 @@ The dependency detection algorithm can be summarised as follows:
160160
5. Find all files that added one or more modules/namespaces to any of the nodes found in 5.
161161
6. Return those as dependencies.
162162

163+
### Graph optimisation - going deeper than just top-level module
164+
165+
In 1.i of the above algorithm we only consider the top-level module/namespace(s) for each file.
166+
As soon as some other file is able to navigate to that top-level item, we consider it a dependency.
167+
168+
A more or less straightforward optimisation of this behaviour would be to:
169+
1. In 1.i Collect a tree of modules/namespaces that contain any types/exceptions that can be used for type inference.
170+
2. In 2. add all the leaves from the tree to the Trie.
171+
172+
This should further reduce the graph.
173+
174+
### Edge-case 1. - `[<AutoOpen>]`
175+
176+
Modules with `[<AutoOpen>]` are in a way 'transparent', meaning that all the types/nested modules inside them are surfaced as if they were on a level above.
177+
178+
The algorithm needs to consider that.
179+
180+
The main problem with that is that `AutoOpenAttribute` could be aliased and hide behind a different name.
181+
Therefore it's not easy to see whether the attribute is being used based only on the AST.
182+
183+
There are ways to evaluate this, which involve scanning all module abbreviations in the project and in any referenced dlls.
184+
185+
However, for now, the algorithm simply treats every module with _any_ attributes as an `[<AutoOpen>]` module.
186+
187+
This retains correctness, but reduces efficiency of the graph reduction. Optimisation ideas here are welcome.
188+
189+
### Edge-case 2. - module abbreviations
190+
191+
At the moment the algorithm doesn't support files with module abbreviations. Adding support should be doable.
192+
163193
### Performance
164194

165195
Little to no effort has been invested in optimising the algorithm.
@@ -200,4 +230,4 @@ We believe this is doable, although no implementation exists as of yet.
200230

201231
As noted in https://github.com/dotnet/fsharp/pull/13737#issuecomment-1224124532 , disrupting the processing order makes it difficult to retain the original behaviour when it comes to the order in which diagnostics are presented and suppressed.
202232

203-
The importance of this problem and potential solutions are open questions.
233+
The importance of this problem and potential solutions are open questions.

0 commit comments

Comments
 (0)