1
// Copyright 2019, The Go Authors. All rights reserved.
2
// Use of this source code is governed by a BSD-style
3
// license that can be found in the LICENSE file.
4

5
package cmp
6

7
import "reflect"
8

9
// valueNode represents a single node within a report, which is a
10
// structured representation of the value tree, containing information
11
// regarding which nodes are equal or not.
12
type valueNode struct {
13
	parent *valueNode
14

15
	Type   reflect.Type
16
	ValueX reflect.Value
17
	ValueY reflect.Value
18

19
	// NumSame is the number of leaf nodes that are equal.
20
	// All descendants are equal only if NumDiff is 0.
21
	NumSame int
22
	// NumDiff is the number of leaf nodes that are not equal.
23
	NumDiff int
24
	// NumIgnored is the number of leaf nodes that are ignored.
25
	NumIgnored int
26
	// NumCompared is the number of leaf nodes that were compared
27
	// using an Equal method or Comparer function.
28
	NumCompared int
29
	// NumTransformed is the number of non-leaf nodes that were transformed.
30
	NumTransformed int
31
	// NumChildren is the number of transitive descendants of this node.
32
	// This counts from zero; thus, leaf nodes have no descendants.
33
	NumChildren int
34
	// MaxDepth is the maximum depth of the tree. This counts from zero;
35
	// thus, leaf nodes have a depth of zero.
36
	MaxDepth int
37

38
	// Records is a list of struct fields, slice elements, or map entries.
39
	Records []reportRecord // If populated, implies Value is not populated
40

41
	// Value is the result of a transformation, pointer indirect, of
42
	// type assertion.
43
	Value *valueNode // If populated, implies Records is not populated
44

45
	// TransformerName is the name of the transformer.
46
	TransformerName string // If non-empty, implies Value is populated
47
}
48
type reportRecord struct {
49
	Key   reflect.Value // Invalid for slice element
50
	Value *valueNode
51
}
52

53
func (parent *valueNode) PushStep(ps PathStep) (child *valueNode) {
54
	vx, vy := ps.Values()
55
	child = &valueNode{parent: parent, Type: ps.Type(), ValueX: vx, ValueY: vy}
56
	switch s := ps.(type) {
57
	case StructField:
58
		assert(parent.Value == nil)
59
		parent.Records = append(parent.Records, reportRecord{Key: reflect.ValueOf(s.Name()), Value: child})
60
	case SliceIndex:
61
		assert(parent.Value == nil)
62
		parent.Records = append(parent.Records, reportRecord{Value: child})
63
	case MapIndex:
64
		assert(parent.Value == nil)
65
		parent.Records = append(parent.Records, reportRecord{Key: s.Key(), Value: child})
66
	case Indirect:
67
		assert(parent.Value == nil && parent.Records == nil)
68
		parent.Value = child
69
	case TypeAssertion:
70
		assert(parent.Value == nil && parent.Records == nil)
71
		parent.Value = child
72
	case Transform:
73
		assert(parent.Value == nil && parent.Records == nil)
74
		parent.Value = child
75
		parent.TransformerName = s.Name()
76
		parent.NumTransformed++
77
	default:
78
		assert(parent == nil) // Must be the root step
79
	}
80
	return child
81
}
82

83
func (r *valueNode) Report(rs Result) {
84
	assert(r.MaxDepth == 0) // May only be called on leaf nodes
85

86
	if rs.ByIgnore() {
87
		r.NumIgnored++
88
	} else {
89
		if rs.Equal() {
90
			r.NumSame++
91
		} else {
92
			r.NumDiff++
93
		}
94
	}
95
	assert(r.NumSame+r.NumDiff+r.NumIgnored == 1)
96

97
	if rs.ByMethod() {
98
		r.NumCompared++
99
	}
100
	if rs.ByFunc() {
101
		r.NumCompared++
102
	}
103
	assert(r.NumCompared <= 1)
104
}
105

106
func (child *valueNode) PopStep() (parent *valueNode) {
107
	if child.parent == nil {
108
		return nil
109
	}
110
	parent = child.parent
111
	parent.NumSame += child.NumSame
112
	parent.NumDiff += child.NumDiff
113
	parent.NumIgnored += child.NumIgnored
114
	parent.NumCompared += child.NumCompared
115
	parent.NumTransformed += child.NumTransformed
116
	parent.NumChildren += child.NumChildren + 1
117
	if parent.MaxDepth < child.MaxDepth+1 {
118
		parent.MaxDepth = child.MaxDepth + 1
119
	}
120
	return parent
121
}
122

123