Skip to content

Commit 63539f8

Browse files
nojafnojaf
committed
queryTrieMemoized
1 parent 32dd4bf commit 63539f8

3 files changed

Lines changed: 26 additions & 17 deletions

File tree

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

Lines changed: 20 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -34,22 +34,25 @@ let queryTrie (trie: TrieNode) (path: ModuleSegment list) : QueryTrieNodeResult
3434

3535
visit trie path
3636

37+
let queryTrieMemoized (trie: TrieNode) : QueryTrie =
38+
Internal.Utilities.Library.Tables.memoize (queryTrie trie)
39+
3740
// Now how to detect the deps between files?
3841
// Process the content of each file using some state
3942

4043
// Helper function to process a open statement
4144
// 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
45+
let processOpenPath (queryTrie: QueryTrie) (path: ModuleSegment list) (state: FileContentQueryState) : FileContentQueryState =
46+
let queryResult = queryTrie path
4447

4548
match queryResult with
4649
| QueryTrieNodeResult.NodeDoesNotExist -> state
4750
| QueryTrieNodeResult.NodeDoesNotExposeData -> state.AddOpenNamespace path
4851
| QueryTrieNodeResult.NodeExposesData files -> state.AddDependenciesAndOpenNamespace(files, path)
4952

5053
// Helper function to process an identifier
51-
let processIdentifier (trie: TrieNode) (path: ModuleSegment list) (state: FileContentQueryState) : FileContentQueryState =
52-
let queryResult = queryTrie trie path
54+
let processIdentifier (queryTrie: QueryTrie) (path: ModuleSegment list) (state: FileContentQueryState) : FileContentQueryState =
55+
let queryResult = queryTrie path
5356

5457
match queryResult with
5558
| QueryTrieNodeResult.NodeDoesNotExist -> state
@@ -60,38 +63,38 @@ let processIdentifier (trie: TrieNode) (path: ModuleSegment list) (state: FileCo
6063
| QueryTrieNodeResult.NodeExposesData files -> state.AddDependencies files
6164

6265
// Typically used to folder FileContentEntry items over a FileContentQueryState
63-
let rec processStateEntry (trie: TrieNode) (state: FileContentQueryState) (entry: FileContentEntry) : FileContentQueryState =
66+
let rec processStateEntry (queryTrie: QueryTrie) (state: FileContentQueryState) (entry: FileContentEntry) : FileContentQueryState =
6467
match entry with
6568
| FileContentEntry.TopLevelNamespace (topLevelPath, content) ->
6669
let state =
6770
match topLevelPath with
6871
| [] -> state
69-
| _ -> processOpenPath trie topLevelPath state
72+
| _ -> processOpenPath queryTrie topLevelPath state
7073

71-
List.fold (processStateEntry trie) state content
74+
List.fold (processStateEntry queryTrie) state content
7275

7376
| FileContentEntry.OpenStatement path ->
7477
// An open statement can directly reference file or be a partial open statement
7578
// Both cases need to be processed.
76-
let stateAfterFullOpenPath = processOpenPath trie path state
79+
let stateAfterFullOpenPath = processOpenPath queryTrie path state
7780

7881
// Any existing open statement could be extended with the current path (if that node where to exists in the trie)
7982
// The extended path could add a new link (in case of a module or namespace with types)
8083
// It might also not add anything at all (in case it the extended path is still a partial one)
8184
(stateAfterFullOpenPath, state.OpenNamespaces)
82-
||> Seq.fold (fun acc openNS -> processOpenPath trie [ yield! openNS; yield! path ] acc)
85+
||> Seq.fold (fun acc openNS -> processOpenPath queryTrie [ yield! openNS; yield! path ] acc)
8386

8487
| FileContentEntry.PrefixedIdentifier path ->
8588
// process the name was if it were a FQN
86-
let stateAfterFullIdentifier = processIdentifier trie path state
89+
let stateAfterFullIdentifier = processIdentifier queryTrie path state
8790

8891
// Process the name in combination with the existing open namespaces
8992
(stateAfterFullIdentifier, state.OpenNamespaces)
90-
||> Seq.fold (fun acc openNS -> processIdentifier trie [ yield! openNS; yield! path ] acc)
93+
||> Seq.fold (fun acc openNS -> processIdentifier queryTrie [ yield! openNS; yield! path ] acc)
9194

9295
| FileContentEntry.NestedModule (nestedContent = nestedContent) ->
9396
// 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
97+
let nestedState = List.fold (processStateEntry queryTrie) state nestedContent
9598
// Afterward we are only interested in the found dependencies in the nested module
9699
let foundDependencies =
97100
Set.union state.FoundDependencies nestedState.FoundDependencies
@@ -121,7 +124,10 @@ let mkGraph (files: FileWithAST array) =
121124

122125
time "TrieMapping.mkTrie" TrieMapping.mkTrie input
123126

124-
let fileContents = Array.Parallel.map FileContentMapping.mkFileContent files
127+
let queryTrie: QueryTrie = queryTrieMemoized trie
128+
129+
let fileContents =
130+
time "FileContentMapping.mkFileContent" Array.Parallel.map FileContentMapping.mkFileContent files
125131

126132
time
127133
"mkGraph"
@@ -131,7 +137,7 @@ let mkGraph (files: FileWithAST array) =
131137
let knownFiles = getFileNameBefore files file.Idx
132138

133139
let result =
134-
Seq.fold (processStateEntry trie) (FileContentQueryState.Create file.File knownFiles) fileContent
140+
Seq.fold (processStateEntry queryTrie) (FileContentQueryState.Create file.File knownFiles) fileContent
135141

136142
file.File, Set.toArray result.FoundDependencies)
137143
files
@@ -521,7 +527,6 @@ let ``FCS for debugging`` () =
521527
let contents =
522528
Array.map
523529
(fun (file: FileWithAST) ->
524-
printfn "Start %s" file.File
525530
FileContentMapping.mkFileContent file)
526531
filesWithAST
527532

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

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -729,8 +729,10 @@ let ``Full project simulation`` () =
729729
let knownFiles =
730730
files.[0 .. (fileContent.Idx - 1)] |> Array.map (fun f -> f.Name) |> set
731731

732+
let queryTrie: QueryTrie = queryTrieMemoized fantomasCoreTrie
733+
732734
let result =
733-
Seq.fold (processStateEntry fantomasCoreTrie) (FileContentQueryState.Create fileContent.Name knownFiles) fileContent.Content
735+
Seq.fold (processStateEntry queryTrie) (FileContentQueryState.Create fileContent.Name knownFiles) fileContent.Content
734736

735737
fileContent.Name, Set.toArray result.FoundDependencies)
736738

@@ -785,7 +787,7 @@ let ``ProcessOpenStatement full path match`` () =
785787
|])
786788

787789
let result =
788-
processOpenPath fantomasCoreTrie [ "Fantomas"; "Core"; "AstExtensions" ] state
790+
processOpenPath (queryTrie fantomasCoreTrie) [ "Fantomas"; "Core"; "AstExtensions" ] state
789791

790792
let dep = Seq.exactlyOne result.FoundDependencies
791793
Assert.AreEqual("AstExtensions.fsi", dep)

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

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -105,3 +105,5 @@ type QueryTrieNodeResult =
105105
| NodeDoesNotExposeData
106106
/// A node was found with one or more file links
107107
| NodeExposesData of Files
108+
109+
type QueryTrie = ModuleSegment list -> QueryTrieNodeResult

0 commit comments

Comments
 (0)