Skip to content

Commit e5e769a

Browse files
nojafnojaf
committed
Dependency resolution with new trie approach.
1 parent b574074 commit e5e769a

6 files changed

Lines changed: 1298 additions & 250 deletions

File tree

‎tests/ParallelTypeCheckingTests/Code/TrieApproach/DependencyResolution.fs‎

Lines changed: 188 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,188 @@
1+
module ParallelTypeCheckingTests.Code.TrieApproach.DependencyResolution
2+
3+
open FSharp.Compiler.Syntax
4+
5+
// This is pseudo code of how we could restructure the trie code
6+
// My main benefit is that you can easily visually inspect if an identifier will match something in the trie
7+
8+
// This code just looks for a path in the trie
9+
// It could be cached and is easy to reason about.
10+
let queryTrie (trie: TrieNode) (path: ModuleSegment list) : QueryTrieNodeResult =
11+
let rec visit (currentNode: TrieNode) (path: ModuleSegment list) =
12+
match path with
13+
| [] -> failwith "path should not be empty"
14+
| [ lastNodeFromPath ] ->
15+
let childResults =
16+
currentNode.Children
17+
|> Seq.tryFind (fun (KeyValue (segment, _childNode)) -> segment = lastNodeFromPath)
18+
19+
match childResults with
20+
| None -> QueryTrieNodeResult.NodeDoesNotExist
21+
| Some (KeyValue (_, childNode)) ->
22+
if Set.isEmpty childNode.Files then
23+
QueryTrieNodeResult.NodeDoesNotExposeData
24+
else
25+
QueryTrieNodeResult.NodeExposesData(childNode.Files)
26+
| currentPath :: restPath ->
27+
let childResults =
28+
currentNode.Children
29+
|> Seq.tryFind (fun (KeyValue (segment, _childNode)) -> segment = currentPath)
30+
31+
match childResults with
32+
| None -> QueryTrieNodeResult.NodeDoesNotExist
33+
| Some (KeyValue (_, childNode)) -> visit childNode restPath
34+
35+
visit trie path
36+
37+
// Now how to detect the deps between files?
38+
// Process the content of each file using some state
39+
40+
// Helper function to process a open statement
41+
// The statement could link to files and/or should be tracked as an open namespace
42+
let processOpenPath (trie: TrieNode) (path: ModuleSegment list) (state: FileContentQueryState) : FileContentQueryState =
43+
let queryResult = queryTrie trie path
44+
45+
match queryResult with
46+
| QueryTrieNodeResult.NodeDoesNotExist -> state
47+
| QueryTrieNodeResult.NodeDoesNotExposeData -> state.AddOpenNamespace path
48+
| QueryTrieNodeResult.NodeExposesData files -> state.AddDependenciesAndOpenNamespace(files, path)
49+
50+
// Helper function to process an identifier
51+
let processIdentifier (trie: TrieNode) (path: ModuleSegment list) (state: FileContentQueryState) : FileContentQueryState =
52+
let queryResult = queryTrie trie path
53+
54+
match queryResult with
55+
| QueryTrieNodeResult.NodeDoesNotExist -> state
56+
| QueryTrieNodeResult.NodeDoesNotExposeData ->
57+
// This can occur when you are have a file that uses a known namespace (for example namespace System).
58+
// When any other code uses that System namespace it won't find anything in the user code.
59+
state
60+
| QueryTrieNodeResult.NodeExposesData files -> state.AddDependencies files
61+
62+
// Typically used to folder FileContentEntry items over a FileContentQueryState
63+
let rec processStateEntry (trie: TrieNode) (state: FileContentQueryState) (entry: FileContentEntry) : FileContentQueryState =
64+
match entry with
65+
| FileContentEntry.TopLevelNamespace (topLevelPath, content) ->
66+
let state =
67+
match topLevelPath with
68+
| [] -> state
69+
| _ -> processOpenPath trie topLevelPath state
70+
71+
List.fold (processStateEntry trie) state content
72+
73+
| FileContentEntry.OpenStatement path ->
74+
// An open statement can directly reference file or be a partial open statement
75+
// Both cases need to be processed.
76+
let stateAfterFullOpenPath = processOpenPath trie path state
77+
78+
// Any existing open statement could be extended with the current path (if that node where to exists in the trie)
79+
// The extended path could add a new link (in case of a module or namespace with types)
80+
// It might also not add anything at all (in case it the extended path is still a partial one)
81+
(stateAfterFullOpenPath, state.OpenNamespaces)
82+
||> Seq.fold (fun acc openNS -> processOpenPath trie [ yield! openNS; yield! path ] acc)
83+
84+
| FileContentEntry.PrefixedIdentifier path ->
85+
// process the name was if it were a FQN
86+
let stateAfterFullIdentifier = processIdentifier trie path state
87+
88+
// Process the name in combination with the existing open namespaces
89+
(stateAfterFullIdentifier, state.OpenNamespaces)
90+
||> Seq.fold (fun acc openNS -> processIdentifier trie [ yield! openNS; yield! path ] acc)
91+
92+
| FileContentEntry.NestedModule (nestedContent = nestedContent) ->
93+
// We don't want our current state to be affect by any open statements in the nested module
94+
let nestedState = List.fold (processStateEntry trie) state nestedContent
95+
// Afterward we are only interested in the found dependencies in the nested module
96+
let foundDependencies =
97+
Set.union state.FoundDependencies nestedState.FoundDependencies
98+
99+
{ state with
100+
FoundDependencies = foundDependencies
101+
}
102+
103+
let getFileNameBefore (files: FileWithAST array) idx =
104+
files.[0 .. (idx - 1)] |> Array.map (fun f -> f.File) |> Set.ofArray
105+
106+
let mkGraph (files: FileWithAST array) =
107+
let trie =
108+
let input =
109+
files
110+
|> Array.filter (fun f ->
111+
match f.AST with
112+
| ParsedInput.SigFile _ -> true
113+
| ParsedInput.ImplFile _ -> Array.forall (fun (sigFile: FileWithAST) -> sigFile.File <> $"{f.File}i") files)
114+
115+
TrieMapping.mkTrie input
116+
117+
let fileContents = Array.Parallel.map FileContentMapping.mkFileContent files
118+
119+
files
120+
|> Array.map (fun (file: FileWithAST) ->
121+
let fileContent = fileContents.[file.Idx]
122+
let knownFiles = getFileNameBefore files file.Idx
123+
124+
let result =
125+
Seq.fold (processStateEntry trie) (FileContentQueryState.Create file.File knownFiles) fileContent
126+
127+
file.File, Set.toArray result.FoundDependencies)
128+
129+
// =============================================================================================================
130+
// =============================================================================================================
131+
132+
open NUnit.Framework
133+
open FSharp.Compiler.Service.Tests.Common
134+
135+
[<Test>]
136+
let ``Fantomas.Core for realzies`` () =
137+
let files =
138+
[|
139+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\obj\Debug\netstandard2.0\.NETStandard,Version=v2.0.AssemblyAttributes.fs"
140+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\obj\Debug\netstandard2.0\Fantomas.Core.AssemblyInfo.fs"
141+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\AssemblyInfo.fs"
142+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\ISourceTextExtensions.fs"
143+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\RangeHelpers.fs"
144+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\AstExtensions.fsi"
145+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\AstExtensions.fs"
146+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\TriviaTypes.fs"
147+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\Utils.fs"
148+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\SourceParser.fs"
149+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\AstTransformer.fsi"
150+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\AstTransformer.fs"
151+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\Version.fs"
152+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\Queue.fs"
153+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\FormatConfig.fs"
154+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\Defines.fsi"
155+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\Defines.fs"
156+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\Trivia.fsi"
157+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\Trivia.fs"
158+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\SourceTransformer.fs"
159+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\Context.fs"
160+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\CodePrinter.fsi"
161+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\CodePrinter.fs"
162+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\CodeFormatterImpl.fsi"
163+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\CodeFormatterImpl.fs"
164+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\Validation.fs"
165+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\Selection.fsi"
166+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\Selection.fs"
167+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\CodeFormatter.fsi"
168+
@"C:\Users\nojaf\Projects\main-fantomas\src\Fantomas.Core\CodeFormatter.fs"
169+
|]
170+
171+
let filesWithAST =
172+
files
173+
|> Array.mapi (fun idx file ->
174+
{
175+
Idx = idx
176+
AST = parseSourceCode (file, System.IO.File.ReadAllText(file))
177+
File = file
178+
})
179+
180+
let graph = mkGraph filesWithAST
181+
182+
for fileName, deps in graph do
183+
let depString = String.concat "\n " deps
184+
185+
if deps.Length = 0 then
186+
printfn $"%s{fileName}: []"
187+
else
188+
printfn $"%s{fileName}:\n {depString}"

0 commit comments

Comments
 (0)