Skip to content

Commit 8e85538

Browse files
nojafnojaf
committed
Return a graph of int in mkGraph.
1 parent 18657b1 commit 8e85538

2 files changed

Lines changed: 58 additions & 70 deletions

File tree

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

Lines changed: 51 additions & 56 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22

33
open System.Linq
44
open FSharp.Compiler.Syntax
5+
open ParallelTypeCheckingTests
56

67
// This is pseudo code of how we could restructure the trie code
78
// My main benefit is that you can easily visually inspect if an identifier will match something in the trie
@@ -177,68 +178,60 @@ let collectGhostDependencies (fileIndex: int) (trie: TrieNode) (queryTrie: Query
177178
// The partial open did eventually lead to a link in a file
178179
Array.empty)
179180

180-
let mkGraph (files: FileWithAST array) =
181+
let mkGraph (files: FileWithAST array) : Graph<int> =
181182
// Implementation files backed by signatures should be excluded to construct the trie.
182183
let trieInput =
183-
time
184-
"trieInput"
185-
Array.filter
184+
Array.filter
186185
(fun f ->
187186
match f.AST with
188187
| ParsedInput.SigFile _ -> true
189188
| ParsedInput.ImplFile _ -> Array.forall (fun (sigFile: FileWithAST) -> sigFile.File <> $"{f.File}i") files)
190189
files
191190

192-
let trie = time "TrieMapping.mkTrie" TrieMapping.mkTrie trieInput
193-
191+
let trie = TrieMapping.mkTrie trieInput
194192
let queryTrie: QueryTrie = queryTrieMemoized trie
195193

196-
let fileContents =
197-
time "FileContentMapping.mkFileContent" Array.Parallel.map FileContentMapping.mkFileContent files
194+
let fileContents = Array.Parallel.map FileContentMapping.mkFileContent files
198195

199196
let filesWithAutoOpen =
200-
time
201-
"filesWithAutoOpen"
202-
(Array.choose (fun f ->
197+
Array.choose
198+
(fun f ->
203199
if AlwaysLinkDetection.doesFileHasAutoOpenBehavior f.AST then
204200
Some f.Idx
205201
else
206-
None))
202+
None)
207203
trieInput
208204

209-
time
210-
"link deps"
211-
// Array.Parallel.map
212-
Array.map
213-
(fun (file: FileWithAST) ->
214-
let fileContent = fileContents.[file.Idx]
215-
let knownFiles = getFileNameBefore files file.Idx
216-
217-
// Process all entries of a file and query the trie when required to find the dependent files.
218-
let result =
219-
// Seq is faster than List in this case.
220-
Seq.fold (processStateEntry queryTrie) (FileContentQueryState.Create file.Idx knownFiles) fileContent
221-
222-
// after processing the file we should verify if any of the open statements are found in the trie but do not yield any file link.
223-
let ghostDependencies = collectGhostDependencies file.Idx trie queryTrie result
224-
225-
// Automatically add all files that came before the current file that use the [<AutoOpen>] attribute.
226-
let topLevelAutoOpenFiles =
227-
if Array.isEmpty filesWithAutoOpen then
228-
Array.empty
229-
else
230-
[| 0 .. (file.Idx - 1) |].Intersect(filesWithAutoOpen).ToArray()
205+
let findDependencies (file: FileWithAST) : int * int array =
206+
let fileContent = fileContents.[file.Idx]
207+
let knownFiles = getFileNameBefore files file.Idx
231208

232-
let allDependencies =
233-
set
234-
[|
235-
yield! result.FoundDependencies
236-
yield! ghostDependencies
237-
yield! topLevelAutoOpenFiles
238-
|]
209+
// Process all entries of a file and query the trie when required to find the dependent files.
210+
let result =
211+
// Seq is faster than List in this case.
212+
Seq.fold (processStateEntry queryTrie) (FileContentQueryState.Create file.Idx knownFiles) fileContent
239213

240-
file, Set.toArray allDependencies)
241-
files
214+
// after processing the file we should verify if any of the open statements are found in the trie but do not yield any file link.
215+
let ghostDependencies = collectGhostDependencies file.Idx trie queryTrie result
216+
217+
// Automatically add all files that came before the current file that use the [<AutoOpen>] attribute.
218+
let topLevelAutoOpenFiles =
219+
if Array.isEmpty filesWithAutoOpen then
220+
Array.empty
221+
else
222+
[| 0 .. (file.Idx - 1) |].Intersect(filesWithAutoOpen).ToArray()
223+
224+
let allDependencies =
225+
[|
226+
yield! result.FoundDependencies
227+
yield! ghostDependencies
228+
yield! topLevelAutoOpenFiles
229+
|]
230+
|> Array.distinct
231+
232+
file.Idx, allDependencies
233+
234+
Array.Parallel.map findDependencies files |> readOnlyDict
242235

243236
// =============================================================================================================
244237
// =============================================================================================================
@@ -249,25 +242,26 @@ open FSharp.Compiler.Service.Tests.Common
249242
let mkGraphAndReport files =
250243
let filesWithAST =
251244
files
252-
|> Array.mapi (fun idx file ->
245+
|> Array.Parallel.mapi (fun idx file ->
253246
{
254247
Idx = idx
255248
AST = parseSourceCode (file, System.IO.File.ReadAllText(file))
256249
File = file
257250
})
258251

259-
let graph = time "mkGraph" mkGraph filesWithAST
260-
261-
for fileName, deps in graph do
262-
let depString =
263-
deps
264-
|> Array.map (fun depIdx -> filesWithAST.[depIdx].File)
265-
|> String.concat "\n "
252+
let _graph = mkGraph filesWithAST
253+
()
266254

267-
if deps.Length = 0 then
268-
printfn $"%s{fileName.File}: []"
269-
else
270-
printfn $"%s{fileName.File}:\n {depString}"
255+
// for KeyValue (fileIdx, deps) in graph do
256+
// let depString =
257+
// deps |> Array.map (fun dep -> filesWithAST.[dep].File) |> String.concat "\n "
258+
//
259+
// let fileName = filesWithAST.[fileIdx]
260+
//
261+
// if deps.Length = 0 then
262+
// printfn $"%s{fileName.File}: []"
263+
// else
264+
// printfn $"%s{fileName.File}:\n {depString}"
271265

272266
[<Test>]
273267
let ``Fantomas.Core for realzies`` () =
@@ -615,6 +609,7 @@ let fcsFiles =
615609
let ``FCS for realzies`` () = mkGraphAndReport fcsFiles
616610

617611
[<Test>]
612+
[<Explicit "To be removed">]
618613
let ``FCS for debugging`` () =
619614
let filesWithAST =
620615
fcsFiles
@@ -958,5 +953,5 @@ let ``Supported scenario`` (scenario: Scenario) =
958953
let graph = mkGraph (Array.map fst scenario.Files)
959954

960955
for file, expectedDeps in scenario.Files do
961-
let actualDeps = graph |> Array.find (fun (f, _) -> f.File = file.File) |> snd
956+
let actualDeps = graph.[file.Idx]
962957
Assert.AreEqual(expectedDeps, actualDeps, $"Dependencies don't match for {System.IO.Path.GetFileName file.File}")

‎tests/ParallelTypeCheckingTests/Tests/TypedTreeGraph.fs‎

Lines changed: 7 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -271,10 +271,7 @@ let ``Create Graph from typed tree`` (code: Codebase) =
271271
ParallelTypeCheckingTests.Code.TrieApproach.DependencyResolution.mkGraph sourceFiles
272272

273273
let alternateMap =
274-
let getDepsByIdx idx =
275-
alternativeGraphFromHeuristic
276-
|> Seq.find (fun (file, _) -> file.Idx = idx)
277-
|> snd
274+
let getDepsByIdx idx = alternativeGraphFromHeuristic.[idx]
278275

279276
(Map.empty, [ 0 .. (sourceFiles.Length - 1) ])
280277
||> List.fold (fun acc idx ->
@@ -286,22 +283,18 @@ let ``Create Graph from typed tree`` (code: Codebase) =
286283
Map.add idx allDeps acc)
287284

288285
let rec getAllDepsFromAlt idx : Set<int> =
289-
let currentDeps =
290-
alternativeGraphFromHeuristic
291-
|> Seq.find (fun (file, _) -> file.Idx = idx)
292-
|> snd
293-
286+
let currentDeps = alternativeGraphFromHeuristic.[idx]
294287
let transitiveDeps = Seq.collect getAllDepsFromAltMemoized currentDeps
295-
296288
set [| yield! currentDeps; yield! transitiveDeps |]
297289

298290
and getAllDepsFromAltMemoized =
299291
Internal.Utilities.Library.Tables.memoize getAllDepsFromAlt
300292

301-
Array.Parallel.iter
302-
(fun (file: ParallelTypeCheckingTests.Code.TrieApproach.FileWithAST, _) ->
303-
compareDeps "Alternative heuristic" file.File file.Idx (Map.find file.Idx alternateMap))
304-
alternativeGraphFromHeuristic
293+
alternativeGraphFromHeuristic.Keys
294+
|> Seq.toArray
295+
|> Array.Parallel.iter (fun (fileIdx: int) ->
296+
let file = sourceFiles.[fileIdx]
297+
compareDeps "Alternative heuristic" file.QualifiedName fileIdx (Map.find file.Idx.Idx alternateMap))
305298

306299
finally
307300
Environment.CurrentDirectory <- previousDir

0 commit comments

Comments
 (0)