.gitignore added

[dotfiles/.git] / .config / coc / extensions / coc-go-data / tools / pkg / mod / github.com / google / go-cmp@v0.5.4 / cmp / path.go

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

package cmp

import (
        "fmt"
        "reflect"
        "strings"
        "unicode"
        "unicode/utf8"

        "github.com/google/go-cmp/cmp/internal/value"
)

// Path is a list of PathSteps describing the sequence of operations to get
// from some root type to the current position in the value tree.
// The first Path element is always an operation-less PathStep that exists
// simply to identify the initial type.
//
// When traversing structs with embedded structs, the embedded struct will
// always be accessed as a field before traversing the fields of the
// embedded struct themselves. That is, an exported field from the
// embedded struct will never be accessed directly from the parent struct.
type Path []PathStep

// PathStep is a union-type for specific operations to traverse
// a value's tree structure. Users of this package never need to implement
// these types as values of this type will be returned by this package.
//
// Implementations of this interface are
// StructField, SliceIndex, MapIndex, Indirect, TypeAssertion, and Transform.
type PathStep interface {
        String() string

        // Type is the resulting type after performing the path step.
        Type() reflect.Type

        // Values is the resulting values after performing the path step.
        // The type of each valid value is guaranteed to be identical to Type.
        //
        // In some cases, one or both may be invalid or have restrictions:
        //      • For StructField, both are not interface-able if the current field
        //      is unexported and the struct type is not explicitly permitted by
        //      an Exporter to traverse unexported fields.
        //      • For SliceIndex, one may be invalid if an element is missing from
        //      either the x or y slice.
        //      • For MapIndex, one may be invalid if an entry is missing from
        //      either the x or y map.
        //
        // The provided values must not be mutated.
        Values() (vx, vy reflect.Value)
}

var (
        _ PathStep = StructField{}
        _ PathStep = SliceIndex{}
        _ PathStep = MapIndex{}
        _ PathStep = Indirect{}
        _ PathStep = TypeAssertion{}
        _ PathStep = Transform{}
)

func (pa *Path) push(s PathStep) {
        *pa = append(*pa, s)
}

func (pa *Path) pop() {
        *pa = (*pa)[:len(*pa)-1]
}

// Last returns the last PathStep in the Path.
// If the path is empty, this returns a non-nil PathStep that reports a nil Type.
func (pa Path) Last() PathStep {
        return pa.Index(-1)
}

// Index returns the ith step in the Path and supports negative indexing.
// A negative index starts counting from the tail of the Path such that -1
// refers to the last step, -2 refers to the second-to-last step, and so on.
// If index is invalid, this returns a non-nil PathStep that reports a nil Type.
func (pa Path) Index(i int) PathStep {
        if i < 0 {
                i = len(pa) + i
        }
        if i < 0 || i >= len(pa) {
                return pathStep{}
        }
        return pa[i]
}

// String returns the simplified path to a node.
// The simplified path only contains struct field accesses.
//
// For example:
//      MyMap.MySlices.MyField
func (pa Path) String() string {
        var ss []string
        for _, s := range pa {
                if _, ok := s.(StructField); ok {
                        ss = append(ss, s.String())
                }
        }
        return strings.TrimPrefix(strings.Join(ss, ""), ".")
}

// GoString returns the path to a specific node using Go syntax.
//
// For example:
//      (*root.MyMap["key"].(*mypkg.MyStruct).MySlices)[2][3].MyField
func (pa Path) GoString() string {
        var ssPre, ssPost []string
        var numIndirect int
        for i, s := range pa {
                var nextStep PathStep
                if i+1 < len(pa) {
                        nextStep = pa[i+1]
                }
                switch s := s.(type) {
                case Indirect:
                        numIndirect++
                        pPre, pPost := "(", ")"
                        switch nextStep.(type) {
                        case Indirect:
                                continue // Next step is indirection, so let them batch up
                        case StructField:
                                numIndirect-- // Automatic indirection on struct fields
                        case nil:
                                pPre, pPost = "", "" // Last step; no need for parenthesis
                        }
                        if numIndirect > 0 {
                                ssPre = append(ssPre, pPre+strings.Repeat("*", numIndirect))
                                ssPost = append(ssPost, pPost)
                        }
                        numIndirect = 0
                        continue
                case Transform:
                        ssPre = append(ssPre, s.trans.name+"(")
                        ssPost = append(ssPost, ")")
                        continue
                }
                ssPost = append(ssPost, s.String())
        }
        for i, j := 0, len(ssPre)-1; i < j; i, j = i+1, j-1 {
                ssPre[i], ssPre[j] = ssPre[j], ssPre[i]
        }
        return strings.Join(ssPre, "") + strings.Join(ssPost, "")
}

type pathStep struct {
        typ    reflect.Type
        vx, vy reflect.Value
}

func (ps pathStep) Type() reflect.Type             { return ps.typ }
func (ps pathStep) Values() (vx, vy reflect.Value) { return ps.vx, ps.vy }
func (ps pathStep) String() string {
        if ps.typ == nil {
                return "<nil>"
        }
        s := ps.typ.String()
        if s == "" || strings.ContainsAny(s, "{}\n") {
                return "root" // Type too simple or complex to print
        }
        return fmt.Sprintf("{%s}", s)
}

// StructField represents a struct field access on a field called Name.
type StructField struct{ *structField }
type structField struct {
        pathStep
        name string
        idx  int

        // These fields are used for forcibly accessing an unexported field.
        // pvx, pvy, and field are only valid if unexported is true.
        unexported bool
        mayForce   bool                // Forcibly allow visibility
        paddr      bool                // Was parent addressable?
        pvx, pvy   reflect.Value       // Parent values (always addressible)
        field      reflect.StructField // Field information
}

func (sf StructField) Type() reflect.Type { return sf.typ }
func (sf StructField) Values() (vx, vy reflect.Value) {
        if !sf.unexported {
                return sf.vx, sf.vy // CanInterface reports true
        }

        // Forcibly obtain read-write access to an unexported struct field.
        if sf.mayForce {
                vx = retrieveUnexportedField(sf.pvx, sf.field, sf.paddr)
                vy = retrieveUnexportedField(sf.pvy, sf.field, sf.paddr)
                return vx, vy // CanInterface reports true
        }
        return sf.vx, sf.vy // CanInterface reports false
}
func (sf StructField) String() string { return fmt.Sprintf(".%s", sf.name) }

// Name is the field name.
func (sf StructField) Name() string { return sf.name }

// Index is the index of the field in the parent struct type.
// See reflect.Type.Field.
func (sf StructField) Index() int { return sf.idx }

// SliceIndex is an index operation on a slice or array at some index Key.
type SliceIndex struct{ *sliceIndex }
type sliceIndex struct {
        pathStep
        xkey, ykey int
        isSlice    bool // False for reflect.Array
}

func (si SliceIndex) Type() reflect.Type             { return si.typ }
func (si SliceIndex) Values() (vx, vy reflect.Value) { return si.vx, si.vy }
func (si SliceIndex) String() string {
        switch {
        case si.xkey == si.ykey:
                return fmt.Sprintf("[%d]", si.xkey)
        case si.ykey == -1:
                // [5->?] means "I don't know where X[5] went"
                return fmt.Sprintf("[%d->?]", si.xkey)
        case si.xkey == -1:
                // [?->3] means "I don't know where Y[3] came from"
                return fmt.Sprintf("[?->%d]", si.ykey)
        default:
                // [5->3] means "X[5] moved to Y[3]"
                return fmt.Sprintf("[%d->%d]", si.xkey, si.ykey)
        }
}

// Key is the index key; it may return -1 if in a split state
func (si SliceIndex) Key() int {
        if si.xkey != si.ykey {
                return -1
        }
        return si.xkey
}

// SplitKeys are the indexes for indexing into slices in the
// x and y values, respectively. These indexes may differ due to the
// insertion or removal of an element in one of the slices, causing
// all of the indexes to be shifted. If an index is -1, then that
// indicates that the element does not exist in the associated slice.
//
// Key is guaranteed to return -1 if and only if the indexes returned
// by SplitKeys are not the same. SplitKeys will never return -1 for
// both indexes.
func (si SliceIndex) SplitKeys() (ix, iy int) { return si.xkey, si.ykey }

// MapIndex is an index operation on a map at some index Key.
type MapIndex struct{ *mapIndex }
type mapIndex struct {
        pathStep
        key reflect.Value
}

func (mi MapIndex) Type() reflect.Type             { return mi.typ }
func (mi MapIndex) Values() (vx, vy reflect.Value) { return mi.vx, mi.vy }
func (mi MapIndex) String() string                 { return fmt.Sprintf("[%#v]", mi.key) }

// Key is the value of the map key.
func (mi MapIndex) Key() reflect.Value { return mi.key }

// Indirect represents pointer indirection on the parent type.
type Indirect struct{ *indirect }
type indirect struct {
        pathStep
}

func (in Indirect) Type() reflect.Type             { return in.typ }
func (in Indirect) Values() (vx, vy reflect.Value) { return in.vx, in.vy }
func (in Indirect) String() string                 { return "*" }

// TypeAssertion represents a type assertion on an interface.
type TypeAssertion struct{ *typeAssertion }
type typeAssertion struct {
        pathStep
}

func (ta TypeAssertion) Type() reflect.Type             { return ta.typ }
func (ta TypeAssertion) Values() (vx, vy reflect.Value) { return ta.vx, ta.vy }
func (ta TypeAssertion) String() string                 { return fmt.Sprintf(".(%v)", ta.typ) }

// Transform is a transformation from the parent type to the current type.
type Transform struct{ *transform }
type transform struct {
        pathStep
        trans *transformer
}

func (tf Transform) Type() reflect.Type             { return tf.typ }
func (tf Transform) Values() (vx, vy reflect.Value) { return tf.vx, tf.vy }
func (tf Transform) String() string                 { return fmt.Sprintf("%s()", tf.trans.name) }

// Name is the name of the Transformer.
func (tf Transform) Name() string { return tf.trans.name }

// Func is the function pointer to the transformer function.
func (tf Transform) Func() reflect.Value { return tf.trans.fnc }

// Option returns the originally constructed Transformer option.
// The == operator can be used to detect the exact option used.
func (tf Transform) Option() Option { return tf.trans }

// pointerPath represents a dual-stack of pointers encountered when
// recursively traversing the x and y values. This data structure supports
// detection of cycles and determining whether the cycles are equal.
// In Go, cycles can occur via pointers, slices, and maps.
//
// The pointerPath uses a map to represent a stack; where descension into a
// pointer pushes the address onto the stack, and ascension from a pointer
// pops the address from the stack. Thus, when traversing into a pointer from
// reflect.Ptr, reflect.Slice element, or reflect.Map, we can detect cycles
// by checking whether the pointer has already been visited. The cycle detection
// uses a seperate stack for the x and y values.
//
// If a cycle is detected we need to determine whether the two pointers
// should be considered equal. The definition of equality chosen by Equal
// requires two graphs to have the same structure. To determine this, both the
// x and y values must have a cycle where the previous pointers were also
// encountered together as a pair.
//
// Semantically, this is equivalent to augmenting Indirect, SliceIndex, and
// MapIndex with pointer information for the x and y values.
// Suppose px and py are two pointers to compare, we then search the
// Path for whether px was ever encountered in the Path history of x, and
// similarly so with py. If either side has a cycle, the comparison is only
// equal if both px and py have a cycle resulting from the same PathStep.
//
// Using a map as a stack is more performant as we can perform cycle detection
// in O(1) instead of O(N) where N is len(Path).
type pointerPath struct {
        // mx is keyed by x pointers, where the value is the associated y pointer.
        mx map[value.Pointer]value.Pointer
        // my is keyed by y pointers, where the value is the associated x pointer.
        my map[value.Pointer]value.Pointer
}

func (p *pointerPath) Init() {
        p.mx = make(map[value.Pointer]value.Pointer)
        p.my = make(map[value.Pointer]value.Pointer)
}

// Push indicates intent to descend into pointers vx and vy where
// visited reports whether either has been seen before. If visited before,
// equal reports whether both pointers were encountered together.
// Pop must be called if and only if the pointers were never visited.
//
// The pointers vx and vy must be a reflect.Ptr, reflect.Slice, or reflect.Map
// and be non-nil.
func (p pointerPath) Push(vx, vy reflect.Value) (equal, visited bool) {
        px := value.PointerOf(vx)
        py := value.PointerOf(vy)
        _, ok1 := p.mx[px]
        _, ok2 := p.my[py]
        if ok1 || ok2 {
                equal = p.mx[px] == py && p.my[py] == px // Pointers paired together
                return equal, true
        }
        p.mx[px] = py
        p.my[py] = px
        return false, false
}

// Pop ascends from pointers vx and vy.
func (p pointerPath) Pop(vx, vy reflect.Value) {
        delete(p.mx, value.PointerOf(vx))
        delete(p.my, value.PointerOf(vy))
}

// isExported reports whether the identifier is exported.
func isExported(id string) bool {
        r, _ := utf8.DecodeRuneInString(id)
        return unicode.IsUpper(r)
}