]>
Commit | Line | Data |
---|---|---|
107c1cdb ND |
1 | // Copyright 2017, 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 | ||
5 | package cmp | |
6 | ||
7 | import ( | |
8 | "fmt" | |
9 | "reflect" | |
10 | "strings" | |
11 | "unicode" | |
12 | "unicode/utf8" | |
13 | ) | |
14 | ||
863486a6 AG |
15 | // Path is a list of PathSteps describing the sequence of operations to get |
16 | // from some root type to the current position in the value tree. | |
17 | // The first Path element is always an operation-less PathStep that exists | |
18 | // simply to identify the initial type. | |
19 | // | |
20 | // When traversing structs with embedded structs, the embedded struct will | |
21 | // always be accessed as a field before traversing the fields of the | |
22 | // embedded struct themselves. That is, an exported field from the | |
23 | // embedded struct will never be accessed directly from the parent struct. | |
24 | type Path []PathStep | |
107c1cdb | 25 | |
863486a6 AG |
26 | // PathStep is a union-type for specific operations to traverse |
27 | // a value's tree structure. Users of this package never need to implement | |
28 | // these types as values of this type will be returned by this package. | |
29 | // | |
30 | // Implementations of this interface are | |
31 | // StructField, SliceIndex, MapIndex, Indirect, TypeAssertion, and Transform. | |
32 | type PathStep interface { | |
33 | String() string | |
107c1cdb | 34 | |
863486a6 AG |
35 | // Type is the resulting type after performing the path step. |
36 | Type() reflect.Type | |
107c1cdb | 37 | |
863486a6 AG |
38 | // Values is the resulting values after performing the path step. |
39 | // The type of each valid value is guaranteed to be identical to Type. | |
40 | // | |
41 | // In some cases, one or both may be invalid or have restrictions: | |
42 | // • For StructField, both are not interface-able if the current field | |
43 | // is unexported and the struct type is not explicitly permitted by | |
44 | // AllowUnexported to traverse unexported fields. | |
45 | // • For SliceIndex, one may be invalid if an element is missing from | |
46 | // either the x or y slice. | |
47 | // • For MapIndex, one may be invalid if an entry is missing from | |
48 | // either the x or y map. | |
49 | // | |
50 | // The provided values must not be mutated. | |
51 | Values() (vx, vy reflect.Value) | |
52 | } | |
53 | ||
54 | var ( | |
55 | _ PathStep = StructField{} | |
56 | _ PathStep = SliceIndex{} | |
57 | _ PathStep = MapIndex{} | |
58 | _ PathStep = Indirect{} | |
59 | _ PathStep = TypeAssertion{} | |
60 | _ PathStep = Transform{} | |
107c1cdb ND |
61 | ) |
62 | ||
63 | func (pa *Path) push(s PathStep) { | |
64 | *pa = append(*pa, s) | |
65 | } | |
66 | ||
67 | func (pa *Path) pop() { | |
68 | *pa = (*pa)[:len(*pa)-1] | |
69 | } | |
70 | ||
71 | // Last returns the last PathStep in the Path. | |
72 | // If the path is empty, this returns a non-nil PathStep that reports a nil Type. | |
73 | func (pa Path) Last() PathStep { | |
74 | return pa.Index(-1) | |
75 | } | |
76 | ||
77 | // Index returns the ith step in the Path and supports negative indexing. | |
78 | // A negative index starts counting from the tail of the Path such that -1 | |
79 | // refers to the last step, -2 refers to the second-to-last step, and so on. | |
80 | // If index is invalid, this returns a non-nil PathStep that reports a nil Type. | |
81 | func (pa Path) Index(i int) PathStep { | |
82 | if i < 0 { | |
83 | i = len(pa) + i | |
84 | } | |
85 | if i < 0 || i >= len(pa) { | |
86 | return pathStep{} | |
87 | } | |
88 | return pa[i] | |
89 | } | |
90 | ||
91 | // String returns the simplified path to a node. | |
92 | // The simplified path only contains struct field accesses. | |
93 | // | |
94 | // For example: | |
95 | // MyMap.MySlices.MyField | |
96 | func (pa Path) String() string { | |
97 | var ss []string | |
98 | for _, s := range pa { | |
863486a6 | 99 | if _, ok := s.(StructField); ok { |
107c1cdb ND |
100 | ss = append(ss, s.String()) |
101 | } | |
102 | } | |
103 | return strings.TrimPrefix(strings.Join(ss, ""), ".") | |
104 | } | |
105 | ||
106 | // GoString returns the path to a specific node using Go syntax. | |
107 | // | |
108 | // For example: | |
109 | // (*root.MyMap["key"].(*mypkg.MyStruct).MySlices)[2][3].MyField | |
110 | func (pa Path) GoString() string { | |
111 | var ssPre, ssPost []string | |
112 | var numIndirect int | |
113 | for i, s := range pa { | |
114 | var nextStep PathStep | |
115 | if i+1 < len(pa) { | |
116 | nextStep = pa[i+1] | |
117 | } | |
118 | switch s := s.(type) { | |
863486a6 | 119 | case Indirect: |
107c1cdb ND |
120 | numIndirect++ |
121 | pPre, pPost := "(", ")" | |
122 | switch nextStep.(type) { | |
863486a6 | 123 | case Indirect: |
107c1cdb | 124 | continue // Next step is indirection, so let them batch up |
863486a6 | 125 | case StructField: |
107c1cdb ND |
126 | numIndirect-- // Automatic indirection on struct fields |
127 | case nil: | |
128 | pPre, pPost = "", "" // Last step; no need for parenthesis | |
129 | } | |
130 | if numIndirect > 0 { | |
131 | ssPre = append(ssPre, pPre+strings.Repeat("*", numIndirect)) | |
132 | ssPost = append(ssPost, pPost) | |
133 | } | |
134 | numIndirect = 0 | |
135 | continue | |
863486a6 | 136 | case Transform: |
107c1cdb ND |
137 | ssPre = append(ssPre, s.trans.name+"(") |
138 | ssPost = append(ssPost, ")") | |
139 | continue | |
107c1cdb ND |
140 | } |
141 | ssPost = append(ssPost, s.String()) | |
142 | } | |
143 | for i, j := 0, len(ssPre)-1; i < j; i, j = i+1, j-1 { | |
144 | ssPre[i], ssPre[j] = ssPre[j], ssPre[i] | |
145 | } | |
146 | return strings.Join(ssPre, "") + strings.Join(ssPost, "") | |
147 | } | |
148 | ||
863486a6 AG |
149 | type pathStep struct { |
150 | typ reflect.Type | |
151 | vx, vy reflect.Value | |
152 | } | |
107c1cdb | 153 | |
863486a6 AG |
154 | func (ps pathStep) Type() reflect.Type { return ps.typ } |
155 | func (ps pathStep) Values() (vx, vy reflect.Value) { return ps.vx, ps.vy } | |
107c1cdb ND |
156 | func (ps pathStep) String() string { |
157 | if ps.typ == nil { | |
158 | return "<nil>" | |
159 | } | |
160 | s := ps.typ.String() | |
161 | if s == "" || strings.ContainsAny(s, "{}\n") { | |
162 | return "root" // Type too simple or complex to print | |
163 | } | |
164 | return fmt.Sprintf("{%s}", s) | |
165 | } | |
166 | ||
863486a6 AG |
167 | // StructField represents a struct field access on a field called Name. |
168 | type StructField struct{ *structField } | |
169 | type structField struct { | |
170 | pathStep | |
171 | name string | |
172 | idx int | |
173 | ||
174 | // These fields are used for forcibly accessing an unexported field. | |
175 | // pvx, pvy, and field are only valid if unexported is true. | |
176 | unexported bool | |
177 | mayForce bool // Forcibly allow visibility | |
178 | pvx, pvy reflect.Value // Parent values | |
179 | field reflect.StructField // Field information | |
180 | } | |
181 | ||
182 | func (sf StructField) Type() reflect.Type { return sf.typ } | |
183 | func (sf StructField) Values() (vx, vy reflect.Value) { | |
184 | if !sf.unexported { | |
185 | return sf.vx, sf.vy // CanInterface reports true | |
186 | } | |
187 | ||
188 | // Forcibly obtain read-write access to an unexported struct field. | |
189 | if sf.mayForce { | |
190 | vx = retrieveUnexportedField(sf.pvx, sf.field) | |
191 | vy = retrieveUnexportedField(sf.pvy, sf.field) | |
192 | return vx, vy // CanInterface reports true | |
193 | } | |
194 | return sf.vx, sf.vy // CanInterface reports false | |
195 | } | |
196 | func (sf StructField) String() string { return fmt.Sprintf(".%s", sf.name) } | |
197 | ||
198 | // Name is the field name. | |
199 | func (sf StructField) Name() string { return sf.name } | |
200 | ||
201 | // Index is the index of the field in the parent struct type. | |
202 | // See reflect.Type.Field. | |
203 | func (sf StructField) Index() int { return sf.idx } | |
204 | ||
205 | // SliceIndex is an index operation on a slice or array at some index Key. | |
206 | type SliceIndex struct{ *sliceIndex } | |
207 | type sliceIndex struct { | |
208 | pathStep | |
209 | xkey, ykey int | |
210 | } | |
211 | ||
212 | func (si SliceIndex) Type() reflect.Type { return si.typ } | |
213 | func (si SliceIndex) Values() (vx, vy reflect.Value) { return si.vx, si.vy } | |
214 | func (si SliceIndex) String() string { | |
107c1cdb ND |
215 | switch { |
216 | case si.xkey == si.ykey: | |
217 | return fmt.Sprintf("[%d]", si.xkey) | |
218 | case si.ykey == -1: | |
219 | // [5->?] means "I don't know where X[5] went" | |
220 | return fmt.Sprintf("[%d->?]", si.xkey) | |
221 | case si.xkey == -1: | |
222 | // [?->3] means "I don't know where Y[3] came from" | |
223 | return fmt.Sprintf("[?->%d]", si.ykey) | |
224 | default: | |
225 | // [5->3] means "X[5] moved to Y[3]" | |
226 | return fmt.Sprintf("[%d->%d]", si.xkey, si.ykey) | |
227 | } | |
228 | } | |
107c1cdb | 229 | |
863486a6 AG |
230 | // Key is the index key; it may return -1 if in a split state |
231 | func (si SliceIndex) Key() int { | |
107c1cdb ND |
232 | if si.xkey != si.ykey { |
233 | return -1 | |
234 | } | |
235 | return si.xkey | |
236 | } | |
107c1cdb | 237 | |
863486a6 AG |
238 | // SplitKeys are the indexes for indexing into slices in the |
239 | // x and y values, respectively. These indexes may differ due to the | |
240 | // insertion or removal of an element in one of the slices, causing | |
241 | // all of the indexes to be shifted. If an index is -1, then that | |
242 | // indicates that the element does not exist in the associated slice. | |
243 | // | |
244 | // Key is guaranteed to return -1 if and only if the indexes returned | |
245 | // by SplitKeys are not the same. SplitKeys will never return -1 for | |
246 | // both indexes. | |
247 | func (si SliceIndex) SplitKeys() (ix, iy int) { return si.xkey, si.ykey } | |
248 | ||
249 | // MapIndex is an index operation on a map at some index Key. | |
250 | type MapIndex struct{ *mapIndex } | |
251 | type mapIndex struct { | |
252 | pathStep | |
253 | key reflect.Value | |
254 | } | |
255 | ||
256 | func (mi MapIndex) Type() reflect.Type { return mi.typ } | |
257 | func (mi MapIndex) Values() (vx, vy reflect.Value) { return mi.vx, mi.vy } | |
258 | func (mi MapIndex) String() string { return fmt.Sprintf("[%#v]", mi.key) } | |
259 | ||
260 | // Key is the value of the map key. | |
261 | func (mi MapIndex) Key() reflect.Value { return mi.key } | |
262 | ||
263 | // Indirect represents pointer indirection on the parent type. | |
264 | type Indirect struct{ *indirect } | |
265 | type indirect struct { | |
266 | pathStep | |
267 | } | |
268 | ||
269 | func (in Indirect) Type() reflect.Type { return in.typ } | |
270 | func (in Indirect) Values() (vx, vy reflect.Value) { return in.vx, in.vy } | |
271 | func (in Indirect) String() string { return "*" } | |
272 | ||
273 | // TypeAssertion represents a type assertion on an interface. | |
274 | type TypeAssertion struct{ *typeAssertion } | |
275 | type typeAssertion struct { | |
276 | pathStep | |
277 | } | |
278 | ||
279 | func (ta TypeAssertion) Type() reflect.Type { return ta.typ } | |
280 | func (ta TypeAssertion) Values() (vx, vy reflect.Value) { return ta.vx, ta.vy } | |
281 | func (ta TypeAssertion) String() string { return fmt.Sprintf(".(%v)", ta.typ) } | |
282 | ||
283 | // Transform is a transformation from the parent type to the current type. | |
284 | type Transform struct{ *transform } | |
285 | type transform struct { | |
286 | pathStep | |
287 | trans *transformer | |
288 | } | |
289 | ||
290 | func (tf Transform) Type() reflect.Type { return tf.typ } | |
291 | func (tf Transform) Values() (vx, vy reflect.Value) { return tf.vx, tf.vy } | |
292 | func (tf Transform) String() string { return fmt.Sprintf("%s()", tf.trans.name) } | |
293 | ||
294 | // Name is the name of the Transformer. | |
295 | func (tf Transform) Name() string { return tf.trans.name } | |
296 | ||
297 | // Func is the function pointer to the transformer function. | |
298 | func (tf Transform) Func() reflect.Value { return tf.trans.fnc } | |
299 | ||
300 | // Option returns the originally constructed Transformer option. | |
301 | // The == operator can be used to detect the exact option used. | |
302 | func (tf Transform) Option() Option { return tf.trans } | |
107c1cdb ND |
303 | |
304 | // isExported reports whether the identifier is exported. | |
305 | func isExported(id string) bool { | |
306 | r, _ := utf8.DecodeRuneInString(id) | |
307 | return unicode.IsUpper(r) | |
308 | } |