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.md file.
4
5package cmp
6
7import "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.
12type 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}
48type reportRecord struct {
49	Key   reflect.Value // Invalid for slice element
50	Value *valueNode
51}
52
53func (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
83func (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
106func (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