utils.go 4.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163
  1. package config
  2. import (
  3. "fmt"
  4. "net"
  5. "net/netip"
  6. "strings"
  7. "github.com/metacubex/mihomo/adapter/outboundgroup"
  8. "github.com/metacubex/mihomo/common/structure"
  9. )
  10. func trimArr(arr []string) (r []string) {
  11. for _, e := range arr {
  12. r = append(r, strings.Trim(e, " "))
  13. }
  14. return
  15. }
  16. // Check if ProxyGroups form DAG(Directed Acyclic Graph), and sort all ProxyGroups by dependency order.
  17. // Meanwhile, record the original index in the config file.
  18. // If loop is detected, return an error with location of loop.
  19. func proxyGroupsDagSort(groupsConfig []map[string]any) error {
  20. type graphNode struct {
  21. indegree int
  22. // topological order
  23. topo int
  24. // the original data in `groupsConfig`
  25. data map[string]any
  26. // `outdegree` and `from` are used in loop locating
  27. outdegree int
  28. option *outboundgroup.GroupCommonOption
  29. from []string
  30. }
  31. decoder := structure.NewDecoder(structure.Option{TagName: "group", WeaklyTypedInput: true})
  32. graph := make(map[string]*graphNode)
  33. // Step 1.1 build dependency graph
  34. for _, mapping := range groupsConfig {
  35. option := &outboundgroup.GroupCommonOption{}
  36. if err := decoder.Decode(mapping, option); err != nil {
  37. return fmt.Errorf("ProxyGroup %s: %s", option.Name, err.Error())
  38. }
  39. groupName := option.Name
  40. if node, ok := graph[groupName]; ok {
  41. if node.data != nil {
  42. return fmt.Errorf("ProxyGroup %s: duplicate group name", groupName)
  43. }
  44. node.data = mapping
  45. node.option = option
  46. } else {
  47. graph[groupName] = &graphNode{0, -1, mapping, 0, option, nil}
  48. }
  49. for _, proxy := range option.Proxies {
  50. if node, ex := graph[proxy]; ex {
  51. node.indegree++
  52. } else {
  53. graph[proxy] = &graphNode{1, -1, nil, 0, nil, nil}
  54. }
  55. }
  56. }
  57. // Step 1.2 Topological Sort
  58. // topological index of **ProxyGroup**
  59. index := 0
  60. queue := make([]string, 0)
  61. for name, node := range graph {
  62. // in the beginning, put nodes that have `node.indegree == 0` into queue.
  63. if node.indegree == 0 {
  64. queue = append(queue, name)
  65. }
  66. }
  67. // every element in queue have indegree == 0
  68. for ; len(queue) > 0; queue = queue[1:] {
  69. name := queue[0]
  70. node := graph[name]
  71. if node.option != nil {
  72. index++
  73. groupsConfig[len(groupsConfig)-index] = node.data
  74. if len(node.option.Proxies) == 0 {
  75. delete(graph, name)
  76. continue
  77. }
  78. for _, proxy := range node.option.Proxies {
  79. child := graph[proxy]
  80. child.indegree--
  81. if child.indegree == 0 {
  82. queue = append(queue, proxy)
  83. }
  84. }
  85. }
  86. delete(graph, name)
  87. }
  88. // no loop is detected, return sorted ProxyGroup
  89. if len(graph) == 0 {
  90. return nil
  91. }
  92. // if loop is detected, locate the loop and throw an error
  93. // Step 2.1 rebuild the graph, fill `outdegree` and `from` filed
  94. for name, node := range graph {
  95. if node.option == nil {
  96. continue
  97. }
  98. if len(node.option.Proxies) == 0 {
  99. continue
  100. }
  101. for _, proxy := range node.option.Proxies {
  102. node.outdegree++
  103. child := graph[proxy]
  104. if child.from == nil {
  105. child.from = make([]string, 0, child.indegree)
  106. }
  107. child.from = append(child.from, name)
  108. }
  109. }
  110. // Step 2.2 remove nodes outside the loop. so that we have only the loops remain in `graph`
  111. queue = make([]string, 0)
  112. // initialize queue with node have outdegree == 0
  113. for name, node := range graph {
  114. if node.outdegree == 0 {
  115. queue = append(queue, name)
  116. }
  117. }
  118. // every element in queue have outdegree == 0
  119. for ; len(queue) > 0; queue = queue[1:] {
  120. name := queue[0]
  121. node := graph[name]
  122. for _, f := range node.from {
  123. graph[f].outdegree--
  124. if graph[f].outdegree == 0 {
  125. queue = append(queue, f)
  126. }
  127. }
  128. delete(graph, name)
  129. }
  130. // Step 2.3 report the elements in loop
  131. loopElements := make([]string, 0, len(graph))
  132. for name := range graph {
  133. loopElements = append(loopElements, name)
  134. delete(graph, name)
  135. }
  136. return fmt.Errorf("loop is detected in ProxyGroup, please check following ProxyGroups: %v", loopElements)
  137. }
  138. func verifyIP6() bool {
  139. if iAddrs, err := net.InterfaceAddrs(); err == nil {
  140. for _, addr := range iAddrs {
  141. if prefix, err := netip.ParsePrefix(addr.String()); err == nil {
  142. if addr := prefix.Addr().Unmap(); addr.Is6() && addr.IsGlobalUnicast() {
  143. return true
  144. }
  145. }
  146. }
  147. }
  148. return false
  149. }