Skip to content

Commit 7bc03cc

Browse files
safesparrowsafesparrow
committed
WIP
1 parent 8229cf6 commit 7bc03cc

5 files changed

Lines changed: 225 additions & 42 deletions

File tree

‎tests/FSharp.Compiler.Service.Tests2/Big.fs‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
module FSharp.Compiler.Service.Tests.Big
2+
3+
module A1 = let a = 3
4+
module A2 = let a = 3
5+
module A3 = let a = 3
6+
module A4 =
7+
8+
type AAttribute(name : string) =
9+
inherit System.Attribute()
10+
11+
let a = 3
12+
module A1 =
13+
let a = 3
14+
type X = int * int
15+
type Y = Y of int
16+
17+
module B =
18+
open A2
19+
let b = [|
20+
A1.a
21+
A2.a
22+
A3.a
23+
|]
24+
let c : A4.X = 2,2
25+
[<A4.A("name")>]
26+
let d : A4.Y = A4.Y 2
27+
type Z =
28+
{
29+
X : A4.X
30+
Y : A4.Y
31+
}
32+
33+
let c = A4.a
34+
let d = A4.A1.a
35+
open A4
36+
let e = A1.a
37+
open A1
38+
let f = a
39+
40+
//module X = B

‎tests/FSharp.Compiler.Service.Tests2/DepResolving.fs‎

Lines changed: 175 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,175 @@
1+
module FSharp.Compiler.Service.Tests.DepResolving
2+
3+
open FSharp.Compiler.Service.Tests2.SyntaxTreeTests.TypeTests
4+
open FSharp.Compiler.Syntax
5+
open NUnit.Framework
6+
7+
/// File * AST
8+
type FileAST = string * ParsedInput
9+
10+
type List<'a> = System.Collections.Generic.List<'a>
11+
12+
type Node =
13+
{
14+
Name : string
15+
AST : ParsedInput
16+
Top : LongIdent
17+
ModuleRefs : LongIdent[]
18+
}
19+
20+
/// Filenames with dependencies
21+
type Graph = (Node * List<Node>)[]
22+
23+
let extractModuleSegments (stuff : Stuff) : LongIdent[] =
24+
stuff
25+
|> Seq.choose (fun x ->
26+
match x.Kind with
27+
| ModuleOrNamespace -> x.Ident |> Some
28+
| Type ->
29+
match x.Ident.Length with
30+
| 0
31+
| 1 -> None
32+
| n -> x.Ident.GetSlice(Some 0, n - 1 |> Some) |> Some
33+
)
34+
|> Seq.toArray
35+
36+
type ModuleSegment = string
37+
38+
type TrieNode =
39+
{
40+
// parent?
41+
// TODO Use ValueTuples if not already
42+
Children : System.Collections.Generic.IDictionary<ModuleSegment, TrieNode>
43+
mutable Reachable : bool
44+
/// Files/graph nodes represented by this TrieNode
45+
/// All files whose top-level module/namespace are same as this TrieNode's 'path'
46+
GraphNodes : System.Collections.Generic.List<Node>
47+
}
48+
49+
let emptyList<'a> () =
50+
System.Collections.Generic.List<'a>()
51+
52+
let cloneTrie (trie : TrieNode) : TrieNode =
53+
failwith unsupported // TODO
54+
55+
let emptyTrie () : TrieNode =
56+
{
57+
TrieNode.Children = dict([])
58+
Reachable = false
59+
GraphNodes = emptyList()
60+
}
61+
62+
/// Build initial Trie from files
63+
let buildTrie (nodes : Node[]) : TrieNode =
64+
let root = emptyTrie()
65+
66+
// Add every file
67+
let addItem (node : Node) =
68+
let ident = node.Top
69+
70+
let mutable trieNode = root
71+
// Go through module segments, possibly extending the Trie with new nodes
72+
for segment in ident do
73+
let child =
74+
match trieNode.Children.TryGetValue segment.idText with
75+
// Child exists
76+
| true, child ->
77+
child
78+
// Child doesn't exist
79+
| false, _ ->
80+
let child = emptyTrie()
81+
trieNode.Children[segment.idText] <- child
82+
child
83+
trieNode <- child
84+
85+
// Add the node to the found leaf's list
86+
trieNode.GraphNodes.Add(node)
87+
88+
// Add all files to the Trie
89+
nodes
90+
|> Array.iter addItem
91+
92+
root
93+
94+
let search (trie : TrieNode) (path : LongIdent) =
95+
trie
96+
97+
let algorithm (nodes : FileAST list) : Graph =
98+
// Create ASTs, extract module refs
99+
let nodes =
100+
nodes
101+
|> List.map (fun (name, ast) ->
102+
let typeAndModuleRefs = visit ast
103+
let top = topModuleOrNamespace ast
104+
let moduleRefs = extractModuleSegments typeAndModuleRefs
105+
{
106+
Name = name
107+
AST = ast
108+
Top = top
109+
ModuleRefs = moduleRefs
110+
}
111+
)
112+
|> List.toArray
113+
114+
let trie = buildTrie nodes
115+
116+
// Find dependencies for all files (can be in parallel)
117+
nodes
118+
|> Array.map (fun node ->
119+
let trie = cloneTrie trie
120+
121+
// Keep a list of reachable nodes
122+
let reachable = emptyList<TrieNode>()
123+
124+
let markReachable (node : TrieNode) =
125+
if not node.Reachable then
126+
printfn $"New node reachable"
127+
node.Reachable <- true
128+
reachable.Add(node)
129+
130+
// Mark two nodes as reachable:
131+
// - root (no prefix)
132+
// - top-level module/namespace
133+
markReachable trie
134+
let topNode = search trie node.Top
135+
markReachable topNode
136+
137+
// Process module refs in order, marking more and more TrieNodes as reachable
138+
let processRef (id : LongIdent) =
139+
()
140+
node.ModuleRefs
141+
|> Array.iter processRef
142+
143+
// Collect files from all reachable TrieNodes
144+
let reachableItems =
145+
reachable
146+
|> Seq.collect (fun node -> node.GraphNodes)
147+
node, List<Node>(reachableItems)
148+
)
149+
150+
[<Test>]
151+
let Foo() =
152+
153+
let A =
154+
"""
155+
module A
156+
open B
157+
let x = B.x
158+
"""
159+
let B =
160+
"""
161+
module B
162+
let x = 3
163+
"""
164+
165+
let files = [
166+
"A", A
167+
"B", B
168+
]
169+
let nodes =
170+
files
171+
|> List.map (fun (name, code) -> name, getParseResults code)
172+
173+
let graph = algorithm nodes
174+
175+
printfn $"%+A{graph}"

‎tests/FSharp.Compiler.Service.Tests2/FSharp.Compiler.Service.Tests2.fsproj‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -27,10 +27,13 @@
2727
<Link>Common.fs</Link>
2828
</Compile>
2929
<Compile Include="TypeTests.fs" />
30-
<Compile Include="Test.fs" />
30+
<Compile Include="DepResolving.fs" />
3131
<Compile Include="..\service\Program.fs">
3232
<Link>Program.fs</Link>
3333
</Compile>
34+
<None Include="Big.fs">
35+
<CopyToOutputDirectory>PreserveNewest</CopyToOutputDirectory>
36+
</None>
3437
</ItemGroup>
3538

3639
<ItemGroup>

‎tests/FSharp.Compiler.Service.Tests2/Test.fs‎

Lines changed: 0 additions & 2 deletions
This file was deleted.

‎tests/FSharp.Compiler.Service.Tests2/TypeTests.fs‎

Lines changed: 6 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -1087,8 +1087,6 @@ let f = a
10871087
printfn $"%+A{stuff}"
10881088
()
10891089

1090-
let depends ()
1091-
10921090
[<Test>]
10931091
let ``Test two`` () =
10941092

@@ -1112,41 +1110,10 @@ let x = 3
11121110
printfn $"A refs: %+A{visitedA}"
11131111
()
11141112

1115-
module A1 = let a = 3
1116-
module A2 = let a = 3
1117-
module A3 = let a = 3
1118-
module A4 =
1119-
1120-
type AAttribute(name : string) =
1121-
inherit System.Attribute()
1122-
1123-
let a = 3
1124-
module A1 =
1125-
let a = 3
1126-
type X = int * int
1127-
type Y = Y of int
1128-
1129-
module B =
1130-
open A2
1131-
let b = [|
1132-
A1.a
1133-
A2.a
1134-
A3.a
1135-
|]
1136-
let c : A4.X = 2,2
1137-
[<A4.A("name")>]
1138-
let d : A4.Y = A4.Y 2
1139-
type Z =
1140-
{
1141-
X : A4.X
1142-
Y : A4.Y
1143-
}
1144-
1145-
let c = A4.a
1146-
let d = A4.A1.a
1147-
open A4
1148-
let e = A1.a
1149-
open A1
1150-
let f = a
11511113

1152-
module X = B
1114+
[<Test>]
1115+
let ``Test big`` () =
1116+
let code = System.IO.File.ReadAllText("Big.fs")
1117+
let parsedA = getParseResults code
1118+
let visitedA = visit parsedA
1119+
printfn $"A refs: %+A{visitedA}"

0 commit comments

Comments
 (0)