path.go

Documentation: github.com/google/go-cmp/cmp

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