-
Notifications
You must be signed in to change notification settings - Fork 1
/
dag.go
78 lines (72 loc) · 2.34 KB
/
dag.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package contract
import (
"github.com/Timwood0x10/sei-chain/utils/datastructures"
"github.com/Timwood0x10/sei-chain/x/dex/types"
)
type node struct {
contractAddr string
incomingNodes *datastructures.SyncSet[string]
}
// Kahn's algorithm
func TopologicalSortContractInfo(contracts []types.ContractInfoV2) ([]types.ContractInfoV2, error) {
contractAddrToContractInfo := map[string]types.ContractInfoV2{}
for _, contract := range contracts {
contractAddrToContractInfo[contract.ContractAddr] = contract
}
res := []types.ContractInfoV2{}
nodes := initNodes(contracts)
frontierNodes, nonFrontierNodes := splitNodesByFrontier(nodes)
for len(frontierNodes) > 0 {
for _, frontierNode := range frontierNodes {
if contract, ok := contractAddrToContractInfo[frontierNode.contractAddr]; ok {
res = append(res, contract)
}
for _, nonFrontierNode := range nonFrontierNodes {
nonFrontierNode.incomingNodes.Remove(frontierNode.contractAddr)
}
}
frontierNodes, nonFrontierNodes = splitNodesByFrontier(nonFrontierNodes)
}
if len(nonFrontierNodes) > 0 {
return []types.ContractInfoV2{}, types.ErrCircularContractDependency
}
return res, nil
}
func initNodes(contracts []types.ContractInfoV2) map[string]node {
res := map[string]node{}
for _, contract := range contracts {
if _, ok := res[contract.ContractAddr]; !ok {
emptyIncomingNodes := datastructures.NewSyncSet([]string{})
res[contract.ContractAddr] = node{
contractAddr: contract.ContractAddr,
incomingNodes: &emptyIncomingNodes,
}
}
if contract.Dependencies == nil {
continue
}
for _, dependentContract := range contract.Dependencies {
dependentAddr := dependentContract.Dependency
if _, ok := res[dependentAddr]; !ok {
emptyIncomingNodes := datastructures.NewSyncSet([]string{})
res[dependentAddr] = node{
contractAddr: dependentAddr,
incomingNodes: &emptyIncomingNodes,
}
}
res[dependentAddr].incomingNodes.Add(contract.ContractAddr)
}
}
return res
}
func splitNodesByFrontier(nodes map[string]node) (map[string]node, map[string]node) {
frontierNodes, nonFrontierNodes := map[string]node{}, map[string]node{}
for contractAddr, node := range nodes {
if node.incomingNodes.Size() == 0 {
frontierNodes[contractAddr] = node
} else {
nonFrontierNodes[contractAddr] = node
}
}
return frontierNodes, nonFrontierNodes
}