144 lines
3.5 KiB
Go
144 lines
3.5 KiB
Go
package utils
|
|
|
|
import (
|
|
"fmt"
|
|
)
|
|
|
|
// PluginConfig 插件配置结构
|
|
type PluginConfig struct {
|
|
Tag string
|
|
Type string
|
|
Args any
|
|
}
|
|
|
|
// PluginNode 表示插件节点及其依赖关系
|
|
type PluginNode struct {
|
|
Index int // 在原始数组中的索引
|
|
Config PluginConfig // 插件配置
|
|
Deps []string // 依赖的插件标签
|
|
}
|
|
|
|
// TopologicalSort 对插件配置进行拓扑排序
|
|
// 返回排序后的插件配置列表，如果存在循环依赖则返回错误
|
|
func TopologicalSort(plugins []PluginConfig) ([]PluginConfig, error) {
|
|
// 构建依赖图
|
|
graph := buildDependencyGraph(plugins)
|
|
|
|
// 计算入度
|
|
inDegree := make(map[string]int)
|
|
for node := range graph {
|
|
if _, ok := inDegree[node]; !ok {
|
|
inDegree[node] = 0
|
|
}
|
|
for _, neighbor := range graph[node] {
|
|
inDegree[neighbor]++
|
|
}
|
|
}
|
|
|
|
// 找出所有入度为0的节点
|
|
queue := []string{}
|
|
for node, degree := range inDegree {
|
|
if degree == 0 {
|
|
queue = append(queue, node)
|
|
}
|
|
}
|
|
|
|
// BFS遍历
|
|
result := []PluginConfig{}
|
|
for len(queue) > 0 {
|
|
node := queue[0]
|
|
queue = queue[1:]
|
|
result = append(result, findPluginConfigByTag(plugins, node))
|
|
|
|
// 减少邻居节点的入度
|
|
for _, neighbor := range graph[node] {
|
|
inDegree[neighbor]--
|
|
if inDegree[neighbor] == 0 {
|
|
queue = append(queue, neighbor)
|
|
}
|
|
}
|
|
}
|
|
|
|
// 检测循环依赖
|
|
if len(result) != len(plugins) {
|
|
return nil, fmt.Errorf("检测到循环依赖，无法进行拓扑排序")
|
|
}
|
|
|
|
return result, nil
|
|
}
|
|
|
|
// buildDependencyGraph 构建插件依赖图
|
|
func buildDependencyGraph(plugins []PluginConfig) map[string][]string {
|
|
graph := make(map[string][]string)
|
|
|
|
for _, p := range plugins {
|
|
graph[p.Tag] = extractDependencies(p)
|
|
}
|
|
|
|
return graph
|
|
}
|
|
|
|
// extractDependencies 从插件配置中提取依赖关系
|
|
// 解析配置中的 $plugin_name 引用
|
|
func extractDependencies(config PluginConfig) []string {
|
|
var deps []string
|
|
|
|
// 将配置转换为字符串进行正则匹配
|
|
configStr := fmt.Sprintf("%+v", config.Args)
|
|
|
|
// 简单的字符串匹配，查找 $xxx 格式的引用
|
|
// 这是一个简化的实现，实际情况可能需要更复杂的解析
|
|
i := 0
|
|
for i < len(configStr) {
|
|
if i+1 < len(configStr) && configStr[i] == '$' {
|
|
// 找到变量名的开始
|
|
start := i + 1
|
|
// 查找变量名的结束（遇到非字母数字下划线字符）
|
|
end := start
|
|
for end < len(configStr) && (isAlphaNumeric(configStr[end]) || configStr[end] == '_') {
|
|
end++
|
|
}
|
|
|
|
if start < end {
|
|
dep := configStr[start:end]
|
|
// 排除一些常见的关键字，避免误识别
|
|
if dep != "primary" && dep != "secondary" && dep != "timeout" && dep != "china_ip" {
|
|
deps = append(deps, dep)
|
|
}
|
|
}
|
|
i = end
|
|
} else {
|
|
i++
|
|
}
|
|
}
|
|
|
|
return deps
|
|
}
|
|
|
|
// isAlphaNumeric 判断字符是否为字母、数字或下划线
|
|
func isAlphaNumeric(c byte) bool {
|
|
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || c == '_'
|
|
}
|
|
|
|
// findPluginConfigByTag 根据标签查找插件配置
|
|
func findPluginConfigByTag(plugins []PluginConfig, tag string) PluginConfig {
|
|
for _, p := range plugins {
|
|
if p.Tag == tag {
|
|
return p
|
|
}
|
|
}
|
|
// 理论上不会出现找不到的情况，因为我们是从现有标签构建的图
|
|
return PluginConfig{}
|
|
}
|
|
|
|
// ValidateConfigOrder 验证配置顺序是否正确
|
|
// 如果配置顺序有问题，返回建议的正确顺序
|
|
func ValidateConfigOrder(plugins []PluginConfig) ([]PluginConfig, error) {
|
|
sorted, err := TopologicalSort(plugins)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
|
|
return sorted, nil
|
|
}
|