Agent-System/internal/traceimpact/walk.go

package traceimpact

// WalkHit is one node reached by a reverse walk.
type WalkHit struct {
	ItemID int64
	EdgeID int64
	Depth  int
	Via    string
}

// WalkReverse follows confirmed edges from changed items to their dependents.
// An edge From --depends_on/refines--> To means From depends on To.
// Changing To therefore impacts From. Candidate edges are not followed.
func WalkReverse(edges []Edge, start []int64, maxDepth, maxNodes int) (hits []WalkHit, truncated bool) {
	if maxDepth <= 0 {
		maxDepth = MaxWalkDepth
	}
	if maxNodes <= 0 {
		maxNodes = MaxWalkNodes
	}
	startSet := map[int64]bool{}
	for _, id := range start {
		startSet[id] = true
	}
	type node struct {
		id    int64
		depth int
	}
	queue := make([]node, 0, len(start))
	for _, id := range start {
		queue = append(queue, node{id: id, depth: 0})
	}
	seen := map[int64]bool{}
	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		if seen[cur.id] {
			continue
		}
		seen[cur.id] = true
		if len(seen) > maxNodes {
			return hits, true
		}
		if cur.depth >= maxDepth {
			continue
		}
		for _, e := range edges {
			if e.ReviewState != ReviewConfirmed || e.ToItemID != cur.id {
				continue
			}
			if startSet[e.FromItemID] || seen[e.FromItemID] {
				continue
			}
			hits = append(hits, WalkHit{ItemID: e.FromItemID, EdgeID: e.ID, Depth: cur.depth + 1, Via: e.RelationType})
			queue = append(queue, node{id: e.FromItemID, depth: cur.depth + 1})
		}
	}
	return hits, false
}