Goで依存関係の重みを計算する

こんにちは。

今回は自作しているGoの依存関係を分析するCLIツールにて依存関係の重みを算出して表示する機能を作成したので、紹介していこうと思います。

↓リポジトリはこちら

https://github.com/junyaU/mimi
starお待ちしております🌟

# 依存関係の重みとは
依存関係の重みというのは、
プログラムにおける、パッケージが、他のパッケージにどれだけ依存し、依存されているかを示す指標です。
大雑把にいうとそのパッケージにおいて、どれだけ依存関係が複雑かを表す指標となるものです。

依存関係の重みを算出するための要素として以下のようなものがあります。
- **直接依存関係の数** : そのパッケージが直接依存している他のパッケージの数
- **間接依存関係の数** : そのパッケージが間接的に依存している他のパッケージの数 
A→B→Cという依存関係がある時、パッケージAにおいて、Cが間接依存しているパッケージになります。
- **依存関係の深さ** : そのパッケージから最も遠い依存先までの距離
先ほどのA→B→Cの場合、パッケージAにおいてCへの深さは2になります。
この深さが最も深い部分がそのパッケージの深さです。
- **依存されているパッケージ数**　 :  そのパッケージが直接依存している他のパッケージの数

依存関係の重みが高いほど、そのパッケージが変更されたときに他のコードへの影響が大きくなり、バグの発生リスクが増えます。また、依存関係が多いとテストが難しくなったりします。
なので、依存関係の重みを算出することで、優先してリファクタリングすべきパッケージを見つけやすくすることができます。

# 依存関係の重みの算出方法
私はGoのパッケージ依存関係の「重み」を定義し、次のように算出することにしました。
※重みの値は0~1の範囲とする

```
Weight = 0.3 * D + 0.3 * I + 0.2 * De + 0.2 * Z
```

各項目の意味は以下の通りです：

- D = 直接依存関係の数
- I = 間接依存関係の数
- De = 依存されているパッケージの数
- Z = 依存関係の深さ

直接依存関係 (D) と 間接依存関係 (I) は、そのパッケージがどれだけ他のパッケージと結びついているか、すなわち、他のパッケージの変更から影響を受ける可能性がどれだけあるかを示す指標です。そのため、これらの値が大きいとパッケージの保守やリファクタリングが難しくなる可能性があります。なので、これらの項目には0.3の重みを割り当てています。

依存されているパッケージの数 (De) は、そのパッケージの変更がどれだけ他のパッケージに影響を及ぼす可能性があるかを示します。しかし、この値はパッケージ自体の複雑さにはあまり関係ないので、0.2の重みを付けています。

依存関係の深さ (Z) は、依存関係の深さが大きいほど、依存関係の理解や管理が難しくなることを示します。それでも、DやIほどの影響力はないと考えられるため、こちらにも0.2の重みを付けています。

## 具体例
パッケージAにおいて、 D=5, I=10, De=3, Z=2であった場合、これらをWeight の計算式に当てはめてみると、

```
Weight = 0.3 * 5 + 0.3 * 10 + 0.2 * 3 + 0.2 * 2
```
となり、計算結果は5.5と大幅に０~1の範囲を超えてしまいます。
そこで、0~1の範囲にマッピングするためにそれぞれの値（D, I, De, Z）に正規化を行います。

正規化の手法として、Min-Max Normalizationを使いました。この方法では、次の式に基づいて値を正規化します：

```
normalized_value = (current_value - min_value) / (max_value - min_value)
```

これにより、各パッケージの依存関係の重みを比較可能な形で計算することが可能となります。

## 妥当性と限界
この方法は、パッケージの依存関係の複雑さを評価するための一つの手法です。しかし、すべての依存関係パターンを適切に反映できるわけではありません。たとえば、大規模なパッケージが一つの小規模なパッケージに依存している場合、この方法では小規模なパッケージの重みが過大評価される可能性があります。

このため、この方法を用いる際は、あくまで一つの評価指標として使用し、他の要素や具体的なプロジェクトの状況も考慮に入れることが重要になります。

# 実装
一部抜粋
```go
// Node represents a node in a dependency graph.
type Node struct {
	// Package is the name of the package that this node represents.
	Package string

	// Direct is a list of packages that this node directly depends on.
	Direct []string

	// Indirect is a list of packages that this node indirectly depends on.
	Indirect []string

	// Dependents is a list of packages that depend on this node.
	Dependents []string

	// Depth is the maximum depth of this node's dependency tree.
	Depth int

	// Lines is the number of lines of code in the package that this node represents.
	Lines int

	// Weight is the weighted score of this node, based on its dependencies and dependents.
	Weight float32
}

// DepGraph represents a dependency graph of a Go project.
type DepGraph struct {
	// nodes is the list of nodes in the graph.
	nodes []Node

	// dependencyMap maps package names to their respective package info.
	dependencyMap map[string]pkginfo.Package

	// directLimits, indirectLimits, dependentLimits and depthLimits are the
	// minimum and maximum number of direct dependencies, indirect dependencies,
	// dependents, and depth across all nodes in the graph.
	directLimits    *Limits
	indirectLimits  *Limits
	dependentLimits *Limits
	depthLimits     *Limits
}

type Limits struct {
	Min int
	Max int
}

// calculateWeightsScore calculates the weight score for the node.
// The weight score is a measure of the node's importance in the dependency graph and is based on
// the number of direct dependencies, indirect dependencies, dependents, and depth of the node.
// Each of these factors is normalized with respect to the minimum and maximum values across all
// nodes in the graph, and then weighted according to predefined weights. The final weight score
// for the node is the sum of these weighted factors.
func (n *Node) calculateWeightsScore(directL, indirectL, dependentL, depthL Limits) {
	normalize := func(val int, limit Limits) float32 {
		if limit.Max == limit.Min {
			return 0
		}

		return (float32(val - limit.Min)) / (float32(limit.Max - limit.Min))
	}

	directScore := normalize(len(n.Direct), directL) * directDependencyWeights
	indirectScore := normalize(len(n.Indirect), indirectL) * indirectDependencyWeights
	dependentScore := normalize(len(n.Dependents), dependentL) * dependentWeights
	depthScore := normalize(n.Depth, depthL) * depthWeights

	score := directScore + indirectScore + dependentScore + depthScore
	if score < 0 {
		score = 0
	}

	n.Weight = score
}
```

メインは calculateWeightsScore 関数です。この関数は、各ノード（すなわち、Goパッケージ）の「重み」を計算します。これはノードが依存関係グラフ内でどれほど重要であるかを示すメトリックです。直接的な依存関係、間接的な依存関係、依存元、ノードの深さ（依存関係ツリーの最大深さ）の数に基づいています。それぞれの要素は、グラフ内の全ノードにわたる最小値と最大値に対して正規化され、その後事前定義された重みによって重み付けされます。最終的なノードの重みスコアは、これらの重み付けされた要素の合計です。

normalize 関数は、各要素をその要素の最大値と最小値に対する相対的な値に変換することで正規化を行います。しかし、最大値と最小値が同じ場合、つまりすべてのノードが同じ数の依存関係（または依存元、深さ）を持つ場合は、0除算を防ぐために0を返します。

# 実行してみる
自作ツールのmimiでは、下記のコマンドで実行することができます。

```sh
mimi table <package_path> -w
```

パッケージの依存関係を表形式で出力するものですが、-wオプションを付けることによって、重みに基づく色付けとソートが行われます。

![](https://storage.googleapis.com/zenn-user-upload/27eb5a63b8ee-20230604.png)

この実装では、重みに対して3段階の評価基準を適用しています。

**低レベル（緑色）**: 依存関係の重みが0.0~0.3までの範囲にあるパッケージ。これは、このパッケージが少ない依存関係を持ち、他のパッケージに与える影響が少ないことを表しています。

**中レベル（黄色）**: 依存関係の重みが0.3~0.7までの範囲にあるパッケージ。これは、このパッケージがある程度の依存関係を持ち、注意が必要であることを表しています。

**高レベル（赤色）**: 依存関係の重みが0.7~1.0の範囲にあるパッケージ。これは、このパッケージが多くの依存関係を持ち、他のパッケージに大きな影響を与える可能性があることを表しています。

これによってリファクタリングを率先してすべきパッケージ、依存関係が複雑になっているパッケージが一眼でわかるようになります。

# まとめ
今回は、自作したmimiを通して、依存関係の重みについて考えてみましたが、依存関係の評価はプロジェクトや規模によって最適解が変わるため、非常に面白いなと感じました。
今後は、重みの基準をカスタマイズできるようにしていきたいので、休日に実装してみようと思います。
ご興味があれば、是非使ってみてください！