File: Semantics\TypeInference\Graph.vb
Web Access
Project: src\src\Compilers\VisualBasic\Portable\Microsoft.CodeAnalysis.VisualBasic.vbproj (Microsoft.CodeAnalysis.VisualBasic)
' Licensed to the .NET Foundation under one or more agreements.
' The .NET Foundation licenses this file to you under the MIT license.
' See the LICENSE file in the project root for more information.
 
Imports System.Diagnostics
Imports System.Linq
Imports Microsoft.CodeAnalysis.Collections
Imports Microsoft.CodeAnalysis.PooledObjects
Imports Microsoft.CodeAnalysis.Text
Imports Microsoft.CodeAnalysis.VisualBasic.Symbols
Imports Microsoft.CodeAnalysis.VisualBasic.Syntax
 
Namespace Microsoft.CodeAnalysis.VisualBasic
 
    Partial Friend Class TypeArgumentInference
 
        Private Class GraphNode(Of TGraphNode As GraphNode(Of TGraphNode))
 
            Public ReadOnly Graph As Graph(Of TGraphNode)
            Public IsAddedToVertices As Boolean
 
            Public ReadOnly IncomingEdges As ArrayBuilder(Of TGraphNode)
            Public ReadOnly OutgoingEdges As ArrayBuilder(Of TGraphNode)
 
            Public AlgorithmData As GraphAlgorithmData(Of TGraphNode)
 
            Protected Sub New(graph As Graph(Of TGraphNode))
                Me.Graph = graph
                Me.IsAddedToVertices = False
                Me.IncomingEdges = New ArrayBuilder(Of TGraphNode)()
                Me.OutgoingEdges = New ArrayBuilder(Of TGraphNode)()
            End Sub
 
        End Class
 
        Private Enum DFSColor As Byte
            None
            Grey
            Black
        End Enum
 
        Private Structure GraphAlgorithmData(Of TGraphNode As GraphNode(Of TGraphNode))
 
            ' DFS specific fields
            Public Color As DFSColor
 
            ' Used for quick lookup of which strongly connected component this node is in.
            Public StronglyConnectedComponent As StronglyConnectedComponent(Of TGraphNode)
        End Structure
 
        Private Class StronglyConnectedComponent(Of TGraphNode As GraphNode(Of TGraphNode))
            Inherits GraphNode(Of StronglyConnectedComponent(Of TGraphNode))
 
            Public ReadOnly ChildNodes As ArrayBuilder(Of TGraphNode)
 
            Public Sub New(graph As Graph(Of StronglyConnectedComponent(Of TGraphNode)))
                MyBase.New(graph)
                ChildNodes = New ArrayBuilder(Of TGraphNode)()
            End Sub
        End Class
 
        Private Class Graph(Of TGraphNode As GraphNode(Of TGraphNode))
 
            Public ReadOnly Vertices As ArrayBuilder(Of TGraphNode)
 
            Public Sub New()
                Vertices = New ArrayBuilder(Of TGraphNode)()
            End Sub
 
            Public Sub AddEdge(
                source As TGraphNode,
                target As TGraphNode
            )
                AddNode(source)
                AddNode(target)
 
                source.OutgoingEdges.Add(target)
                target.IncomingEdges.Add(source)
            End Sub
 
            Public Sub AddNode(
                node As TGraphNode
            )
                Debug.Assert(node.Graph Is Me)
 
                If Not node.IsAddedToVertices Then
                    Vertices.Add(node)
                    node.IsAddedToVertices = True
                End If
            End Sub
 
            Public Sub RemoveEdge(
                source As TGraphNode,
                target As TGraphNode
            )
                Debug.Assert(Contains(source))
                Debug.Assert(Contains(target))
 
                Remove(source.OutgoingEdges, target)
                Remove(target.IncomingEdges, source)
            End Sub
 
            Private Shared Sub Remove(list As ArrayBuilder(Of TGraphNode), toRemove As TGraphNode)
 
                Dim lastIndex As Integer = list.Count - 1
 
                For i As Integer = 0 To lastIndex Step 1
                    If list(i) Is toRemove Then
 
                        If i < lastIndex Then
                            list(i) = list(lastIndex)
                        End If
 
                        list.Clip(lastIndex)
                        Return
                    End If
                Next
 
                Throw ExceptionUtilities.Unreachable
            End Sub
 
            Public Function BuildStronglyConnectedComponents() As Graph(Of StronglyConnectedComponent(Of TGraphNode))
 
                Dim sccGraph As New Graph(Of StronglyConnectedComponent(Of TGraphNode))()
 
                ' The first three steps are implementing Kosaraju's algorithm of finding 
                ' the strongly connected components of a directed graph.
 
                ' Step 1: Perform regular Dfs and build a list with the deepest node last.
                Dim orderedList = ArrayBuilder(Of TGraphNode).GetInstance()
                Dfs(orderedList)
 
                ' Step 2: Reset graph algorithm Data
                For Each current As TGraphNode In orderedList
                    current.AlgorithmData = New GraphAlgorithmData(Of TGraphNode)()
                Next
 
                ' Step 3: Walk the nodes and place each tree in the forest in a separate node.
                For Each current As TGraphNode In orderedList
                    If current.AlgorithmData.Color = DFSColor.None Then
                        Dim sccNode As New StronglyConnectedComponent(Of TGraphNode)(sccGraph)
                        CollectSccChildren(current, sccNode)
                        sccGraph.AddNode(sccNode)
                    End If
                Next
 
                orderedList.Free()
                orderedList = Nothing
 
                ' Step 4: Link incoming and outgoing edges.
                For Each sccNode As StronglyConnectedComponent(Of TGraphNode) In sccGraph.Vertices
                    For Each innerNodeIterCurrent As TGraphNode In sccNode.ChildNodes
                        For Each innerOutGoingInterCurrent As TGraphNode In innerNodeIterCurrent.OutgoingEdges
 
                            Dim target As StronglyConnectedComponent(Of TGraphNode) = innerOutGoingInterCurrent.AlgorithmData.StronglyConnectedComponent
 
                            ' Don't create self-edges.
                            If sccNode IsNot target Then
                                sccGraph.AddEdge(sccNode, target)
                            End If
                        Next
                    Next
                Next
 
                Return sccGraph
            End Function
 
            Private Sub CollectSccChildren(
                node As TGraphNode,
                sccNode As StronglyConnectedComponent(Of TGraphNode)
            )
                node.AlgorithmData.Color = DFSColor.Grey
 
                For Each current As TGraphNode In node.IncomingEdges
                    If current.AlgorithmData.Color = DFSColor.None Then
                        CollectSccChildren(current, sccNode)
                    End If
                Next
 
                node.AlgorithmData.Color = DFSColor.Black
 
                Debug.Assert(node.AlgorithmData.StronglyConnectedComponent Is Nothing)
                sccNode.ChildNodes.Add(node)
                node.AlgorithmData.StronglyConnectedComponent = sccNode
            End Sub
 
            Public Sub TopoSort(resultList As ArrayBuilder(Of TGraphNode))
                Dfs(resultList)
            End Sub
 
            Private Sub Dfs(resultList As ArrayBuilder(Of TGraphNode))
                For Each current In Vertices
                    current.AlgorithmData = New GraphAlgorithmData(Of TGraphNode)()
                Next
 
                Dim oldListSize = resultList.Count
                resultList.AddMany(Nothing, Vertices.Count)
                Dim newListSize = resultList.Count
 
                Dim insertAt As Integer = newListSize - 1
 
                For Each current As TGraphNode In Vertices
                    If current.AlgorithmData.Color = DFSColor.None Then
                        DfsVisit(current, resultList, insertAt)
                    End If
                Next
 
                Debug.Assert(insertAt = oldListSize - 1)
            End Sub
 
            Private Sub DfsVisit(
                node As TGraphNode,
                resultList As ArrayBuilder(Of TGraphNode),
                ByRef insertAt As Integer
            )
                node.AlgorithmData.Color = DFSColor.Grey
 
                For Each current As TGraphNode In node.OutgoingEdges
                    If current.AlgorithmData.Color = DFSColor.None Then
                        DfsVisit(current, resultList, insertAt)
                    End If
                Next
 
                node.AlgorithmData.Color = DFSColor.Black
 
                resultList(insertAt) = node
                insertAt -= 1
            End Sub
 
            Private Function Contains(node As TGraphNode) As Boolean
                Return node.Graph Is Me AndAlso node.IsAddedToVertices
            End Function
 
        End Class
 
    End Class
 
End Namespace