path: root/tools/x-repo-types/typeAnalyzer/typeAnalyzer.go

// Copyright (C) 2019-2024 Algorand, Inc.
// This file is part of go-algorand
//
// go-algorand is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// go-algorand is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with go-algorand.  If not, see <https://www.gnu.org/licenses/>.

package main

import (
	"fmt"
	"reflect"
	"regexp"
	"sort"
	"strings"
	"unicode"
)

// diffExclusions is a set of types to exclude. The string keys are assumed to be generated by
// the `TypeNode.String()` method, and these values are ignored when building up the diff.
// These exclusions represent types that are known to serialize in the same way, but
// would be evaluated as different by the diff algorithm if not for this exclusion.
var diffExclusions = map[string]bool{
	// MicroAlgos is a struct with custom marshal override in go-algorand. In other repos it is a uint64.
	`github.com/algorand/go-algorand/data/basics :: "basics.MicroAlgos" (struct)`: true,

	// crypto.PublicKey is an array [32]byte in go-algorand, but is a byte-slice elsewhere.
	`github.com/algorand/go-algorand/crypto :: "crypto.PublicKey" (array)`: true,
}

// --------------- TYPE TREE DATA STRUCTURES --------------- //

// TypeNode wraps reflect.Type and reflect.Kind to make it easier to
// build a tree of types.
type TypeNode struct {
	Depth      int
	Type       reflect.Type
	Kind       reflect.Kind
	ChildNames []ChildName
	children   *ChildTypes
}

// String returns fully qualified information about the TypeNode.
func (t *TypeNode) String() string {
	return fmt.Sprintf("%s :: %q (%s)", t.Type.PkgPath(), t.Type, t.Kind)
}

// IsStruct returns true if the TypeNode is a struct.
func (t *TypeNode) IsStruct() bool {
	return t.Kind == reflect.Struct
}

// MakeType uses reflection to build a TypeNode from a concrete value.
func MakeType(v interface{}) TypeNode {
	t := reflect.TypeOf(v)
	return TypeNode{Type: t, Kind: t.Kind()}
}

// ChildTypes represent a TypeNode's child Types.
type ChildTypes map[string]TypeNode

// ChildName represents the name a type is referred to together with
// the Tag metadata (for the case of a struct field)
type ChildName struct {
	Name, Tag string
}

// String representing the ChildName in an invertible manner.
func (e *ChildName) String() string {
	return fmt.Sprintf("[%s](%s)", e.Name, e.Tag)
}

// ChildNameFromLabel de-"serialize"s a ChildName that has been rendered via ChildName.String()
func ChildNameFromLabel(s string) (ChildName, error) {
	re := regexp.MustCompile(`^\[(.*)\]\((.*)\)$`)
	matches := re.FindStringSubmatch(s)
	if len(matches) == 3 {
		return ChildName{Name: matches[1], Tag: matches[2]}, nil
	}
	return ChildName{}, fmt.Errorf("invalid label: %s", s)
}

// Target represents a Type that is a child of another Type by
// providing the ChildName that "points" to it.
// In the case of a "root" TypeNode, it's up to the caller to provide
// the ChildName.
type Target struct {
	ChildName
	TypeNode TypeNode
}

// String is a convenience method for printing a Target.
func (tgt *Target) String() string {
	return fmt.Sprintf("%s|-->%s", &tgt.ChildName, &tgt.TypeNode)
}

// SerializationInfo provides the essential data
// for go to serialize the field or other type.
func (e *ChildName) SerializationInfo() string {
	// Probably more subtlety is called for.
	re := regexp.MustCompile(`^codec:"([^,"]+)`)

	if e.Tag == "" {
		return e.Name
	}

	matches := re.FindStringSubmatch(e.Tag)
	if len(matches) > 1 {
		return matches[1]
	}
	return e.Tag
}

// TargetPair represents a pair of Targets.
type TargetPair struct {
	X, Y Target
}

// Diff represents a difference (if any) between two Types.
// CommonPath is the path in the trees of the types from their roots
// that arrives at the difference.
// Xdiff and Ydiff are the differences at the end of the common path
// between children. Set theoretically:
// * Xdiff = X - Y
// * Ydiff = Y - X.
type Diff struct {
	CommonPath   []TargetPair
	Xdiff, Ydiff []Target
}

// Empty reports whether there was any difference at all.
func (d *Diff) Empty() bool {
	return d == nil || (len(d.Xdiff) == 0 && len(d.Ydiff) == 0)
}

// --------------- BUILD THE TYPE TREE --------------- //

// Targets returns a slice of Targets, one for each child of the TypeNode.
// In the case of structs, the order is the same as the order of the fields in the struct.
// In the case of maps, the key Target precedes the value Target.
func (t *TypeNode) Targets() []Target {
	targets := make([]Target, 0, len(t.ChildNames))
	for _, edge := range t.ChildNames {
		targets = append(targets, Target{edge, (*t.children)[edge.String()]})
	}
	return targets
}

// TypePath encapsulates a path in a TypeNode tree.
type TypePath []TypeNode

// String is a convenience method for printing a TypePath
// in a go-literal-friendly format.
func (t TypePath) String() string {
	parts := make([]string, len(t))
	for i, node := range t {
		parts[i] = fmt.Sprintf("%q", node.String())
	}
	return fmt.Sprintf("[]string{%s}", strings.Join(parts, ", "))
}

// IsLeaf returns true if the TypeNode has no children.
func (t *TypeNode) IsLeaf() bool {
	return t.children == nil || len(*t.children) == 0
}

// Build the TypeNode tree by finding all child types that belong to a kind and recursively
// building their TypeNode trees. Stop traversing when a cycle is detected.
func (t *TypeNode) Build() TypePath {
	return t.build(TypePath{})
}

func (t *TypeNode) appendChild(typeName, typeTag string, child TypeNode) {
	cname := ChildName{typeName, typeTag}
	t.ChildNames = append(t.ChildNames, cname)
	if t.children == nil {
		children := make(ChildTypes)
		t.children = &children
	}
	(*t.children)[cname.String()] = child
}

// build the TypeNode tree by finding all child types that belong to a kind and recursively
// building their TypeNode trees.
// Return a path that will be non-trivial only in a case that a cycle is detected.
func (t *TypeNode) build(path TypePath) TypePath {
	if t.IsStruct() {
		me := t.String()
		foundCycle := false
		for _, node := range path {
			if node.String() == me {
				foundCycle = true
				break
			}
		}
		path = append(path, *t)
		if foundCycle {
			return path
		}
	}

	var cyclePath TypePath
	switch t.Kind {
	case reflect.Struct:
		cyclePath = t.buildStructChildren(path)
	case reflect.Slice, reflect.Array:
		cyclePath = t.buildListChild(path)
	case reflect.Map:
		cyclePath = t.buildMapChildren(path)
	case reflect.Ptr:
		cyclePath = t.buildPtrChild(path)
	}

	return cyclePath
}

// buildStructChildren builds the children of a struct type.
func (t *TypeNode) buildStructChildren(path TypePath) TypePath {
	var cyclePath TypePath
	for i := 0; i < t.Type.NumField(); i++ {
		typeField := t.Type.Field(i)
		typeName := typeField.Name

		// probably we need to skip typeField.Tag == `codec:"-"` as well
		if typeName == "" || (!unicode.IsUpper(rune(typeName[0])) && typeName != "_struct") {
			continue
		}

		if typeField.Anonymous {
			// embedded struct case
			actualKind := typeField.Type.Kind()
			if actualKind != reflect.Struct {
				panic(fmt.Sprintf("expected [%s] but got unexpected embedded type: %s", reflect.Struct, typeField.Type))
			}

			embedded := TypeNode{t.Depth, typeField.Type, reflect.Struct, nil, nil}
			embeddedCyclePath := embedded.build(path)
			if len(embeddedCyclePath) > 0 {
				cyclePath = embeddedCyclePath
			}
			for _, edge := range embedded.ChildNames {
				child := (*embedded.children)[edge.String()]
				t.appendChild(edge.Name, edge.Tag, child)
			}
			continue
		}

		typeTag := string(typeField.Tag)
		child := TypeNode{t.Depth + 1, typeField.Type, typeField.Type.Kind(), nil, nil}
		childCyclePath := child.build(path)
		if len(childCyclePath) > 0 {
			cyclePath = childCyclePath
		}
		t.appendChild(typeName, typeTag, child)
	}
	return cyclePath
}

func (t *TypeNode) buildListChild(path TypePath) TypePath {
	tt := t.Type.Elem()
	child := TypeNode{t.Depth + 1, tt, tt.Kind(), nil, nil}
	path = child.build(path)
	t.appendChild("<list elt>", "", child)
	return path
}

// buildMapChildren builds the children of a map type.
// To distinguish between the key and value children as well as children of lists and structs,
// the key child is given the name "<map key>" while the value child is given the name "<map val>".
func (t *TypeNode) buildMapChildren(path TypePath) TypePath {
	keyType, valueType := t.Type.Key(), t.Type.Elem()

	keyChild := TypeNode{t.Depth + 1, keyType, keyType.Kind(), nil, nil}
	// don't worry about path because struct keys must be hashable:
	keyChild.build(path)
	t.appendChild("<map key>", "", keyChild)

	valChild := TypeNode{t.Depth + 1, valueType, valueType.Kind(), nil, nil}
	path = valChild.build(path)
	t.appendChild("<map val>", "", valChild)
	return path
}

// buildPtrChild builds the child of a pointer type. To distinguish between a child
// that is a pointer and other children, the child is given the name "<pointer>".
func (t *TypeNode) buildPtrChild(path TypePath) TypePath {
	tt := t.Type.Elem()
	child := TypeNode{t.Depth + 1, tt, tt.Kind(), nil, nil}
	path = child.build(path)
	t.appendChild("<pointer>", "", child)
	return path
}

// Visit traverses the Target tree and applies any actions provided at each node.
func (tgt *Target) Visit(actions ...func(Target)) {
	if len(actions) > 0 {
		for _, action := range actions {
			action(*tgt)
		}
		for _, target := range tgt.TypeNode.Targets() {
			target.Visit(actions...)
		}
	}
}

// StructDiff compares two structs by building their type tree and then
// calling targetTreeDiff on the trees.
func StructDiff(x, y interface{}, exclusions map[string]bool) (TypeNode, TypeNode, *Diff, error) {
	xRoot, yRoot := MakeType(x), MakeType(y)
	xRoot.Build()
	yRoot.Build()

	diff, err := targetTreeDiff(Target{TypeNode: xRoot}, Target{TypeNode: yRoot}, exclusions)
	return xRoot, yRoot, diff, err
}

// targetTreeDiff recursively computes a diff between two Target's x and y considering only data
// that impacts serialization, but ignoring any assumption on key ordering.
func targetTreeDiff(x, y Target, exclusions map[string]bool) (*Diff, error) {
	xtype, ytype := x.TypeNode, y.TypeNode
	if xtype.Depth != ytype.Depth {
		return nil, fmt.Errorf("cannot compare types at different depth")
	}
	// if we got here it must be the case that either depth == 0 or
	// the edges of x and y serialize the same way.

	// First check that the native type for x and y are the same.
	if xtype.Kind != ytype.Kind {
		return &Diff{
			Xdiff: []Target{x},
			Ydiff: []Target{y},
		}, nil
	}

	// So look at the children.
	// If any children differ report back the diff.
	xTgts, yTgts := xtype.Targets(), ytype.Targets()
	xSerials, ySerials := make(map[string]Target), make(map[string]Target)
	for _, tgt := range xTgts {
		xSerials[tgt.ChildName.SerializationInfo()] = tgt
	}
	for _, tgt := range yTgts {
		ySerials[tgt.ChildName.SerializationInfo()] = tgt
	}
	xDiff, yDiff := []Target{}, []Target{}
	for k, v := range xSerials {
		if _, ok := ySerials[k]; !ok {
			xDiff = append(xDiff, v)
		}
	}
	for k, v := range ySerials {
		if _, ok := xSerials[k]; !ok {
			yDiff = append(yDiff, v)
		}
	}
	if len(xDiff) != 0 || len(yDiff) != 0 {
		return &Diff{
			Xdiff: xDiff,
			Ydiff: yDiff,
		}, nil
	}

	// Otherwise, call the children recursively. If any of them report
	// a diff, modify the diff's CommonPath to include the current edge and return it.
	for k, xChild := range xSerials {
		if exclusions[xChild.TypeNode.String()] {
			continue
		}
		yChild := ySerials[k]
		diff, err := targetTreeDiff(xChild, yChild, exclusions)
		if err != nil {
			return nil, err

		}
		if diff != nil {
			diff.CommonPath = append([]TargetPair{
				{
					X: xChild,
					Y: yChild,
				},
			}, diff.CommonPath...)
			return diff, nil
		}
	}
	// No diffs detected up the tree:
	return nil, nil
}

// --------------- DIFF REPORT ----------------- //

// Report returns a human-readable listing of the differences as a string.
func Report(x, y TypeNode, d *Diff) string {
	var sb strings.Builder

	sb.WriteString(`
========================================================
			STRUCT DIFF REPORT
comparing
	<<<<<`)
	sb.WriteString(x.String())
	sb.WriteString(`>>>>>
VS
	<<<<<`)
	sb.WriteString(y.String())
	sb.WriteString(`>>>>>
========================================================`)

	if d == nil {
		sb.WriteString("\nNo differences found.")
	} else {
		if len(d.Xdiff) == 0 && len(d.Ydiff) == 0 {
			if len(d.CommonPath) != 0 {
				panic("A common paths was found with no diffs. This should NEVER happen.")
			}
			sb.WriteString("\nNo differences found.")
		} else {
			sb.WriteString(`
--------------------------------------------------------
		DIFFERENCES FOUND (partial)
--------------------------------------------------------`)
			sb.WriteString(fmt.Sprintf("\nCommon path of length %d:\n", len(d.CommonPath)))
			for depth, tgts := range d.CommonPath {
				indent := strings.Repeat(" ", depth)
				sb.WriteString(fmt.Sprintf("%s_____LEVEL %d_____\n", indent, depth+1))
				sb.WriteString(fmt.Sprintf("%sX-FIELD: %s\n%s\tX-TYPE: %s\n", indent, &tgts.X.ChildName, indent, &tgts.X.TypeNode))
				sb.WriteString(fmt.Sprintf("%sY-FIELD: %s\n%s\tY-TYPE: %s\n", indent, &tgts.Y.ChildName, indent, &tgts.Y.TypeNode))
			}
			sb.WriteString(`
X-DIFF
------
EXISTS IN:	 	`)
			sb.WriteString(fmt.Sprintf("%q", &x))
			sb.WriteString(`
MISSING FROM:		`)
			sb.WriteString(fmt.Sprintf("%q", &y))
			sb.WriteString(fmt.Sprintf("\n%d TYPES TOTAL:\n", len(d.Xdiff)))
			for i, tgt := range d.Xdiff {
				sb.WriteString(fmt.Sprintf(`
(%d)
[FIELD](+codec): 	%s
SOURCE: 		%s`, i+1, &tgt.ChildName, &tgt.TypeNode))
			}

			sb.WriteString(`



Y-DIFF
------
EXISTS IN:	 	`)
			sb.WriteString(fmt.Sprintf("%q", &y))
			sb.WriteString(`
MISSING FROM:		`)
			sb.WriteString(fmt.Sprintf("%q", &x))
			sb.WriteString(fmt.Sprintf("\n%d TYPES TOTAL:\n", len(d.Ydiff)))
			for i, tgt := range d.Ydiff {
				sb.WriteString(fmt.Sprintf(`(%d)
[FIELD](+codec): 	%s
SOURCE: 		%s
`, i+1, &tgt.ChildName, &tgt.TypeNode))
			}
		}
	}
	sb.WriteString(`
========================================================
===============  STRUCT DIFF REPORT END  ===============
========================================================`)

	return sb.String()
}

// ------- STATISTICS AND DEBUGGING ------------- //

// Print prints out information about the TypeNode's structure using `Visit()`.
func (t *TypeNode) Print() {
	action := func(tgt Target) {
		tabs := strings.Repeat("\t", tgt.TypeNode.Depth)
		fmt.Printf("%s[depth=%d]. Value is type %q (%s)\n", tabs, tgt.TypeNode.Depth, tgt.TypeNode.Type, tgt.TypeNode.Kind)

		if tgt.TypeNode.IsLeaf() {
			x := fmt.Sprintf("%q", tgt.TypeNode.Type)
			_ = x
			fmt.Printf("%s-------B I N G O: A LEAF---------->%q (%s)\n", tabs, tgt.TypeNode.Type, tgt.TypeNode.Kind)
			return
		}
		fmt.Printf("%s=====EDGE: %s=====>\n", tabs, tgt.ChildName)
	}
	(&Target{ChildName{}, *t}).Visit(action)
}

// PrintSerializable prints the information that determines go-codec serialization.
// cf: https://github.com/algorand/go-codec/blob/master/codec/encode.go#L1416-L1436
func (tgt Target) PrintSerializable() {
	action := func(tgt Target) {
		ttype := tgt.TypeNode
		tkind := ttype.Kind
		depth := ttype.Depth
		edge := tgt.ChildName
		if depth == 0 {
			fmt.Printf("Serialization info for type %q (%s):\n", ttype.Type, tkind)
			return
		}
		fmt.Printf("%s%s", strings.Repeat(" ", depth-1), edge.SerializationInfo())
		suffix := ""
		if ttype.IsLeaf() {
			x := ttype.String()
			_ = x
			suffix = fmt.Sprintf(":%s", tkind)
		}
		fmt.Printf("%s\n", suffix)
	}
	tgt.Visit(action)
}

// LeafStatsReport prints out a report for the leafs type count.
func LeafStatsReport(xTgt Target) {
	fmt.Printf("\n\nLeaf-type stats for type %s:\n\n", &xTgt.TypeNode)
	leaves := []TypeNode{}
	leafCollector := func(tgt Target) {
		if tgt.TypeNode.IsLeaf() {
			leaves = append(leaves, tgt.TypeNode)
		}
	}

	xTgt.Visit(leafCollector)
	fmt.Printf("Found %d leaves\n\n", len(leaves))

	stats := make(map[string]int)
	for _, leaf := range leaves {
		key := fmt.Sprintf("%s/%s", leaf.Type, leaf.Kind)
		if _, ok := stats[key]; !ok {
			stats[key] = 0
		}
		stats[key]++
	}
	printSortedStats(stats)
}

// MaxDepthReport prints out a report for the max depth of the type tree.
func MaxDepthReport(xTgt Target) int {
	fmt.Printf("\n\nMax depth stats for type %s:\n\n", &xTgt.TypeNode)
	maxDepth := 0
	maxDepthCollector := func(tgt Target) {
		if tgt.TypeNode.Depth > maxDepth {
			maxDepth = tgt.TypeNode.Depth
		}
	}
	xTgt.Visit(maxDepthCollector)
	fmt.Printf("Max depth is %d\n", maxDepth)
	return maxDepth
}

type keyValue struct {
	Key   string
	Value int
}

func printSortedStats(stats map[string]int) {
	// Create a slice of key-value pairs
	var kvSlice []keyValue
	for k, v := range stats {
		kvSlice = append(kvSlice, keyValue{k, v})
	}

	// Sort the slice by the count in descending order
	sort.Slice(kvSlice, func(i, j int) bool {
		return kvSlice[i].Value > kvSlice[j].Value
	})

	// Print the sorted slice
	for _, kv := range kvSlice {
		fmt.Printf("%s: %d\n", kv.Key, kv.Value)
	}
}