path.go 13 KB

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