commandkit/internal/alias/termination.go

package alias

import (
	"fmt"
	"sort"
	"strings"
)

type head struct {
	control int
	symbol  symbol
}

type popKey struct {
	from head
	to   int
}

type popSummary struct {
	rules map[int]struct{}
}

type popWork struct {
	key     popKey
	summary popSummary
}

type transitionUse struct {
	key        transitionKey
	transition transition
}

type graphEdge struct {
	to    head
	rules map[int]struct{}
}

// NonTerminationError identifies mappings that participate in an alias loop.
type NonTerminationError struct {
	Mappings []Mapping
}

func (err *NonTerminationError) Error() string {
	if err == nil || len(err.Mappings) == 0 {
		return "command alias rewriting does not terminate"
	}
	parts := make([]string, 0, len(err.Mappings))
	for _, mapping := range err.Mappings {
		parts = append(parts, fmt.Sprintf("%q → %q", mapping.Source.String(), mapping.Target.String()))
	}
	return "command aliases do not terminate: " + strings.Join(parts, "; ")
}

// ValidateTermination rejects mapping sets whose deterministic prefix
// rewriting can repeat forever for some finite command path.
func ValidateTermination(mappings []Mapping) error {
	_, machine, err := Compile(mappings)
	if err != nil {
		return err
	}
	if cycle := findHeadCycle(machine); cycle != nil {
		return &NonTerminationError{Mappings: cycle}
	}
	return nil
}

func findHeadCycle(machine *Machine) []Mapping {
	// Pop summaries exactly describe finite paths that remove one top symbol
	// without inspecting below it. The head graph then represents nonempty
	// paths that never pop below their starting level. Its cycle witnesses a
	// repeatable computation even when the complete command path keeps growing.
	pop := saturatePopSummaries(machine)
	graph := buildHeadGraph(machine, pop)
	colors := make(map[head]uint8, len(graph))
	path := make([]head, 0)
	pathEdges := make([]graphEdge, 0)
	pathIndex := make(map[head]int)
	var cycleRules map[int]struct{}

	var visit func(head) bool
	visit = func(current head) bool {
		colors[current] = 1
		pathIndex[current] = len(path)
		path = append(path, current)
		for _, edge := range graph[current] {
			switch colors[edge.to] {
			case 0:
				pathEdges = append(pathEdges, edge)
				if visit(edge.to) {
					return true
				}
				pathEdges = pathEdges[:len(pathEdges)-1]
			case 1:
				start := pathIndex[edge.to]
				cycleRules = make(map[int]struct{})
				for _, cycleEdge := range pathEdges[start:] {
					mergeRules(cycleRules, cycleEdge.rules)
				}
				mergeRules(cycleRules, edge.rules)
				return true
			}
		}
		path = path[:len(path)-1]
		delete(pathIndex, current)
		colors[current] = 2
		return false
	}

	for current := range graph {
		if colors[current] == 0 && visit(current) {
			indices := make([]int, 0, len(cycleRules))
			for index := range cycleRules {
				if index >= 0 {
					indices = append(indices, index)
				}
			}
			sort.Ints(indices)
			mappings := make([]Mapping, 0, len(indices))
			for _, index := range indices {
				if index < len(machine.mappings) {
					mapping := machine.mappings[index]
					mappings = append(mappings, Mapping{Source: mapping.Source.Clone(), Target: mapping.Target.Clone()})
				}
			}
			return mappings
		}
	}
	return nil
}

func saturatePopSummaries(machine *Machine) map[head]map[int]popSummary {
	// Zero-symbol pushes seed the relation. Each newly found summary composes
	// with transitions that push one symbol and with either side of transitions
	// that push two symbols until no new finite pop path can be derived.
	byHead := make(map[head]map[int]popSummary)
	queue := make([]popWork, 0)
	add := func(key popKey, rules map[int]struct{}) {
		if byHead[key.from] == nil {
			byHead[key.from] = make(map[int]popSummary)
		}
		if _, exists := byHead[key.from][key.to]; exists {
			return
		}
		summary := popSummary{rules: cloneRules(rules)}
		byHead[key.from][key.to] = summary
		queue = append(queue, popWork{key: key, summary: summary})
	}

	ones := make(map[head][]transitionUse)
	twosByPrefix := make(map[head][]transitionUse)
	twosBySuffix := make(map[symbol][]transitionUse)
	for key, operation := range machine.transitions {
		switch len(operation.push) {
		case 0:
			rules := make(map[int]struct{})
			addRule(rules, operation.rule)
			add(popKey{from: head{control: key.control, symbol: key.read}, to: operation.next}, rules)
		case 1:
			ones[head{control: operation.next, symbol: operation.push[0]}] = append(ones[head{control: operation.next, symbol: operation.push[0]}], transitionUse{key: key, transition: operation})
		case 2:
			prefix := head{control: operation.next, symbol: operation.push[0]}
			twosByPrefix[prefix] = append(twosByPrefix[prefix], transitionUse{key: key, transition: operation})
			twosBySuffix[operation.push[1]] = append(twosBySuffix[operation.push[1]], transitionUse{key: key, transition: operation})
		}
	}

	for cursor := 0; cursor < len(queue); cursor++ {
		work := queue[cursor]
		for _, use := range ones[work.key.from] {
			add(popKey{
				from: head{control: use.key.control, symbol: use.key.read},
				to:   work.key.to,
			}, combineRules(use.transition.rule, work.summary.rules))
		}

		for _, use := range twosByPrefix[work.key.from] {
			suffix := head{control: work.key.to, symbol: use.transition.push[1]}
			finals := make([]int, 0, len(byHead[suffix]))
			for final := range byHead[suffix] {
				finals = append(finals, final)
			}
			sort.Ints(finals)
			for _, final := range finals {
				summary := byHead[suffix][final]
				add(popKey{
					from: head{control: use.key.control, symbol: use.key.read},
					to:   final,
				}, combineRules(use.transition.rule, work.summary.rules, summary.rules))
			}
		}

		for _, use := range twosBySuffix[work.key.from.symbol] {
			if work.key.from.symbol != use.transition.push[1] {
				continue
			}
			prefix := head{control: use.transition.next, symbol: use.transition.push[0]}
			if first, exists := byHead[prefix][work.key.from.control]; exists {
				add(popKey{
					from: head{control: use.key.control, symbol: use.key.read},
					to:   work.key.to,
				}, combineRules(use.transition.rule, first.rules, work.summary.rules))
			}
		}
	}
	return byHead
}

func buildHeadGraph(machine *Machine, pop map[head]map[int]popSummary) map[head][]graphEdge {
	graph := make(map[head][]graphEdge)
	for key, operation := range machine.transitions {
		source := head{control: key.control, symbol: key.read}
		rules := make(map[int]struct{})
		addRule(rules, operation.rule)
		switch len(operation.push) {
		case 1:
			graph[source] = append(graph[source], graphEdge{
				to:    head{control: operation.next, symbol: operation.push[0]},
				rules: cloneRules(rules),
			})
		case 2:
			graph[source] = append(graph[source], graphEdge{
				to:    head{control: operation.next, symbol: operation.push[0]},
				rules: cloneRules(rules),
			})
			prefix := head{control: operation.next, symbol: operation.push[0]}
			for nextControl, summary := range pop[prefix] {
				graph[source] = append(graph[source], graphEdge{
					to:    head{control: nextControl, symbol: operation.push[1]},
					rules: combineRules(operation.rule, summary.rules),
				})
			}
		}
	}
	return graph
}

func addRule(rules map[int]struct{}, rule int) {
	if rule >= 0 {
		rules[rule] = struct{}{}
	}
}

func cloneRules(rules map[int]struct{}) map[int]struct{} {
	copy := make(map[int]struct{}, len(rules))
	mergeRules(copy, rules)
	return copy
}

func combineRules(rule int, groups ...map[int]struct{}) map[int]struct{} {
	combined := make(map[int]struct{})
	addRule(combined, rule)
	for _, group := range groups {
		mergeRules(combined, group)
	}
	return combined
}

func mergeRules(target, source map[int]struct{}) {
	for rule := range source {
		target[rule] = struct{}{}
	}
}