index.go

     1  // Copyright 2021 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  // This file implements typechecking of index/slice expressions.
     6  
     7  package types
     8  
     9  import (
    10  	"go/ast"
    11  	"go/constant"
    12  	"go/token"
    13  	. "internal/types/errors"
    14  )
    15  
    16  // If e is a valid function instantiation, indexExpr returns true.
    17  // In that case x represents the uninstantiated function value and
    18  // it is the caller's responsibility to instantiate the function.
    19  func (check *Checker) indexExpr(x *operand, e *indexedExpr) (isFuncInst bool) {
    20  	check.exprOrType(x, e.x, true)
    21  	// x may be generic
    22  
    23  	switch x.mode() {
    24  	case invalid:
    25  		check.use(e.indices...)
    26  		return false
    27  
    28  	case typexpr:
    29  		// type instantiation
    30  		x.invalidate()
    31  		// TODO(gri) here we re-evaluate e.X - try to avoid this
    32  		x.typ_ = check.varType(e.orig)
    33  		if isValid(x.typ()) {
    34  			x.mode_ = typexpr
    35  		}
    36  		return false
    37  
    38  	case value:
    39  		if sig, _ := x.typ().Underlying().(*Signature); sig != nil && sig.TypeParams().Len() > 0 {
    40  			// function instantiation
    41  			return true
    42  		}
    43  	}
    44  
    45  	// x should not be generic at this point, but be safe and check
    46  	check.nonGeneric(nil, x)
    47  	if !x.isValid() {
    48  		return false
    49  	}
    50  
    51  	// We cannot index on an incomplete type; make sure it's complete.
    52  	if !check.isComplete(x.typ()) {
    53  		x.invalidate()
    54  		return false
    55  	}
    56  	switch typ := x.typ().Underlying().(type) {
    57  	case *Pointer:
    58  		// Additionally, if x.typ is a pointer to an array type, indexing implicitly dereferences the value, meaning
    59  		// its base type must also be complete.
    60  		if !check.isComplete(typ.base) {
    61  			x.invalidate()
    62  			return false
    63  		}
    64  	case *Map:
    65  		// Lastly, if x.typ is a map type, indexing must produce a value of a complete type, meaning
    66  		// its element type must also be complete.
    67  		if !check.isComplete(typ.elem) {
    68  			x.invalidate()
    69  			return false
    70  		}
    71  	}
    72  
    73  	// ordinary index expression
    74  	valid := false
    75  	length := int64(-1) // valid if >= 0
    76  	switch typ := x.typ().Underlying().(type) {
    77  	case *Basic:
    78  		if isString(typ) {
    79  			valid = true
    80  			if x.mode() == constant_ {
    81  				length = int64(len(constant.StringVal(x.val)))
    82  			}
    83  			// an indexed string always yields a byte value
    84  			// (not a constant) even if the string and the
    85  			// index are constant
    86  			x.mode_ = value
    87  			x.typ_ = universeByte // use 'byte' name
    88  		}
    89  
    90  	case *Array:
    91  		valid = true
    92  		length = typ.len
    93  		if x.mode() != variable {
    94  			x.mode_ = value
    95  		}
    96  		x.typ_ = typ.elem
    97  
    98  	case *Pointer:
    99  		if typ, _ := typ.base.Underlying().(*Array); typ != nil {
   100  			valid = true
   101  			length = typ.len
   102  			x.mode_ = variable
   103  			x.typ_ = typ.elem
   104  		}
   105  
   106  	case *Slice:
   107  		valid = true
   108  		x.mode_ = variable
   109  		x.typ_ = typ.elem
   110  
   111  	case *Map:
   112  		index := check.singleIndex(e)
   113  		if index == nil {
   114  			x.invalidate()
   115  			return false
   116  		}
   117  		var key operand
   118  		check.expr(nil, &key, index)
   119  		check.assignment(&key, typ.key, "map index")
   120  		// ok to continue even if indexing failed - map element type is known
   121  		x.mode_ = mapindex
   122  		x.typ_ = typ.elem
   123  		x.expr = e.orig
   124  		return false
   125  
   126  	case *Interface:
   127  		if !isTypeParam(x.typ()) {
   128  			break
   129  		}
   130  		// TODO(gri) report detailed failure cause for better error messages
   131  		var key, elem Type // key != nil: we must have all maps
   132  		mode := variable   // non-maps result mode
   133  		// TODO(gri) factor out closure and use it for non-typeparam cases as well
   134  		if underIs(x.typ(), func(u Type) bool {
   135  			l := int64(-1) // valid if >= 0
   136  			var k, e Type  // k is only set for maps
   137  			switch t := u.(type) {
   138  			case *Basic:
   139  				if isString(t) {
   140  					e = universeByte
   141  					mode = value
   142  				}
   143  			case *Array:
   144  				l = t.len
   145  				e = t.elem
   146  				if x.mode() != variable {
   147  					mode = value
   148  				}
   149  			case *Pointer:
   150  				if t, _ := t.base.Underlying().(*Array); t != nil {
   151  					l = t.len
   152  					e = t.elem
   153  				}
   154  			case *Slice:
   155  				e = t.elem
   156  			case *Map:
   157  				k = t.key
   158  				e = t.elem
   159  			}
   160  			if e == nil {
   161  				return false
   162  			}
   163  			if elem == nil {
   164  				// first type
   165  				length = l
   166  				key, elem = k, e
   167  				return true
   168  			}
   169  			// all map keys must be identical (incl. all nil)
   170  			// (that is, we cannot mix maps with other types)
   171  			if !Identical(key, k) {
   172  				return false
   173  			}
   174  			// all element types must be identical
   175  			if !Identical(elem, e) {
   176  				return false
   177  			}
   178  			// track the minimal length for arrays, if any
   179  			if l >= 0 && l < length {
   180  				length = l
   181  			}
   182  			return true
   183  		}) {
   184  			// For maps, the index expression must be assignable to the map key type.
   185  			if key != nil {
   186  				index := check.singleIndex(e)
   187  				if index == nil {
   188  					x.invalidate()
   189  					return false
   190  				}
   191  				var k operand
   192  				check.expr(nil, &k, index)
   193  				check.assignment(&k, key, "map index")
   194  				// ok to continue even if indexing failed - map element type is known
   195  				x.mode_ = mapindex
   196  				x.typ_ = elem
   197  				x.expr = e.orig
   198  				return false
   199  			}
   200  
   201  			// no maps
   202  			valid = true
   203  			x.mode_ = mode
   204  			x.typ_ = elem
   205  		}
   206  	}
   207  
   208  	if !valid {
   209  		// types2 uses the position of '[' for the error
   210  		check.errorf(x, NonIndexableOperand, "cannot index %s", x)
   211  		check.use(e.indices...)
   212  		x.invalidate()
   213  		return false
   214  	}
   215  
   216  	index := check.singleIndex(e)
   217  	if index == nil {
   218  		x.invalidate()
   219  		return false
   220  	}
   221  
   222  	// In pathological (invalid) cases (e.g.: type T1 [][[]T1{}[0][0]]T0)
   223  	// the element type may be accessed before it's set. Make sure we have
   224  	// a valid type.
   225  	if x.typ() == nil {
   226  		x.typ_ = Typ[Invalid]
   227  	}
   228  
   229  	check.index(index, length)
   230  	return false
   231  }
   232  
   233  func (check *Checker) sliceExpr(x *operand, e *ast.SliceExpr) {
   234  	check.expr(nil, x, e.X)
   235  	if !x.isValid() {
   236  		check.use(e.Low, e.High, e.Max)
   237  		return
   238  	}
   239  
   240  	// determine common underlying type cu
   241  	var ct, cu Type // type and respective common underlying type
   242  	var hasString bool
   243  	// TODO(adonovan): use go1.23 "range typeset()".
   244  	typeset(x.typ())(func(t, u Type) bool {
   245  		if u == nil {
   246  			check.errorf(x, NonSliceableOperand, "cannot slice %s: no specific type in %s", x, x.typ())
   247  			cu = nil
   248  			return false
   249  		}
   250  
   251  		// Treat strings like byte slices but remember that we saw a string.
   252  		if isString(u) {
   253  			u = NewSlice(universeByte)
   254  			hasString = true
   255  		}
   256  
   257  		// If this is the first type we're seeing, we're done.
   258  		if cu == nil {
   259  			ct, cu = t, u
   260  			return true
   261  		}
   262  
   263  		// Otherwise, the current type must have the same underlying type as all previous types.
   264  		if !Identical(cu, u) {
   265  			check.errorf(x, NonSliceableOperand, "cannot slice %s: %s and %s have different underlying types", x, ct, t)
   266  			cu = nil
   267  			return false
   268  		}
   269  
   270  		return true
   271  	})
   272  	if hasString {
   273  		// If we saw a string, proceed with string type,
   274  		// but don't go from untyped string to string.
   275  		cu = Typ[String]
   276  		if !isTypeParam(x.typ()) {
   277  			cu = x.typ().Underlying() // untyped string remains untyped
   278  		}
   279  	}
   280  
   281  	// Note that we don't permit slice expressions where x is a type expression, so we don't check for that here.
   282  	// However, if x.typ is a pointer to an array type, slicing implicitly dereferences the value, meaning
   283  	// its base type must also be complete.
   284  	if p, ok := x.typ().Underlying().(*Pointer); ok && !check.isComplete(p.base) {
   285  		x.invalidate()
   286  		return
   287  	}
   288  
   289  	valid := false
   290  	length := int64(-1) // valid if >= 0
   291  	switch u := cu.(type) {
   292  	case nil:
   293  		// error reported above
   294  		x.invalidate()
   295  		return
   296  
   297  	case *Basic:
   298  		if isString(u) {
   299  			if e.Slice3 {
   300  				at := e.Max
   301  				if at == nil {
   302  					at = e // e.Index[2] should be present but be careful
   303  				}
   304  				check.error(at, InvalidSliceExpr, invalidOp+"3-index slice of string")
   305  				x.invalidate()
   306  				return
   307  			}
   308  			valid = true
   309  			if x.mode() == constant_ {
   310  				length = int64(len(constant.StringVal(x.val)))
   311  			}
   312  			// spec: "For untyped string operands the result
   313  			// is a non-constant value of type string."
   314  			if isUntyped(x.typ()) {
   315  				x.typ_ = Typ[String]
   316  			}
   317  		}
   318  
   319  	case *Array:
   320  		valid = true
   321  		length = u.len
   322  		if x.mode() != variable {
   323  			check.errorf(x, NonSliceableOperand, "cannot slice unaddressable value %s", x)
   324  			x.invalidate()
   325  			return
   326  		}
   327  		x.typ_ = &Slice{elem: u.elem}
   328  
   329  	case *Pointer:
   330  		if u, _ := u.base.Underlying().(*Array); u != nil {
   331  			valid = true
   332  			length = u.len
   333  			x.typ_ = &Slice{elem: u.elem}
   334  		}
   335  
   336  	case *Slice:
   337  		valid = true
   338  		// x.typ doesn't change
   339  	}
   340  
   341  	if !valid {
   342  		check.errorf(x, NonSliceableOperand, "cannot slice %s", x)
   343  		x.invalidate()
   344  		return
   345  	}
   346  
   347  	x.mode_ = value
   348  
   349  	// spec: "Only the first index may be omitted; it defaults to 0."
   350  	if e.Slice3 && (e.High == nil || e.Max == nil) {
   351  		check.error(inNode(e, e.Rbrack), InvalidSyntaxTree, "2nd and 3rd index required in 3-index slice")
   352  		x.invalidate()
   353  		return
   354  	}
   355  
   356  	// check indices
   357  	var ind [3]int64
   358  	for i, expr := range []ast.Expr{e.Low, e.High, e.Max} {
   359  		x := int64(-1)
   360  		switch {
   361  		case expr != nil:
   362  			// The "capacity" is only known statically for strings, arrays,
   363  			// and pointers to arrays, and it is the same as the length for
   364  			// those types.
   365  			max := int64(-1)
   366  			if length >= 0 {
   367  				max = length + 1
   368  			}
   369  			if _, v := check.index(expr, max); v >= 0 {
   370  				x = v
   371  			}
   372  		case i == 0:
   373  			// default is 0 for the first index
   374  			x = 0
   375  		case length >= 0:
   376  			// default is length (== capacity) otherwise
   377  			x = length
   378  		}
   379  		ind[i] = x
   380  	}
   381  
   382  	// constant indices must be in range
   383  	// (check.index already checks that existing indices >= 0)
   384  L:
   385  	for i, x := range ind[:len(ind)-1] {
   386  		if x > 0 {
   387  			for j, y := range ind[i+1:] {
   388  				if y >= 0 && y < x {
   389  					// The value y corresponds to the expression e.Index[i+1+j].
   390  					// Because y >= 0, it must have been set from the expression
   391  					// when checking indices and thus e.Index[i+1+j] is not nil.
   392  					at := []ast.Expr{e.Low, e.High, e.Max}[i+1+j]
   393  					check.errorf(at, SwappedSliceIndices, "invalid slice indices: %d < %d", y, x)
   394  					break L // only report one error, ok to continue
   395  				}
   396  			}
   397  		}
   398  	}
   399  }
   400  
   401  // singleIndex returns the (single) index from the index expression e.
   402  // If the index is missing, or if there are multiple indices, an error
   403  // is reported and the result is nil.
   404  func (check *Checker) singleIndex(expr *indexedExpr) ast.Expr {
   405  	if len(expr.indices) == 0 {
   406  		check.errorf(expr.orig, InvalidSyntaxTree, "index expression %v with 0 indices", expr)
   407  		return nil
   408  	}
   409  	if len(expr.indices) > 1 {
   410  		// TODO(rFindley) should this get a distinct error code?
   411  		check.error(expr.indices[1], InvalidIndex, invalidOp+"more than one index")
   412  	}
   413  	return expr.indices[0]
   414  }
   415  
   416  // index checks an index expression for validity.
   417  // If max >= 0, it is the upper bound for index.
   418  // If the result typ is != Typ[Invalid], index is valid and typ is its (possibly named) integer type.
   419  // If the result val >= 0, index is valid and val is its constant int value.
   420  func (check *Checker) index(index ast.Expr, max int64) (typ Type, val int64) {
   421  	typ = Typ[Invalid]
   422  	val = -1
   423  
   424  	var x operand
   425  	check.expr(nil, &x, index)
   426  	if !check.isValidIndex(&x, InvalidIndex, "index", false) {
   427  		return
   428  	}
   429  
   430  	if x.mode() != constant_ {
   431  		return x.typ(), -1
   432  	}
   433  
   434  	if x.val.Kind() == constant.Unknown {
   435  		return
   436  	}
   437  
   438  	v, ok := constant.Int64Val(x.val)
   439  	assert(ok)
   440  	if max >= 0 && v >= max {
   441  		check.errorf(&x, InvalidIndex, invalidArg+"index %s out of bounds [0:%d]", x.val.String(), max)
   442  		return
   443  	}
   444  
   445  	// 0 <= v [ && v < max ]
   446  	return x.typ(), v
   447  }
   448  
   449  func (check *Checker) isValidIndex(x *operand, code Code, what string, allowNegative bool) bool {
   450  	if !x.isValid() {
   451  		return false
   452  	}
   453  
   454  	// spec: "a constant index that is untyped is given type int"
   455  	check.convertUntyped(x, Typ[Int])
   456  	if !x.isValid() {
   457  		return false
   458  	}
   459  
   460  	// spec: "the index x must be of integer type or an untyped constant"
   461  	if !allInteger(x.typ()) {
   462  		check.errorf(x, code, invalidArg+"%s %s must be integer", what, x)
   463  		return false
   464  	}
   465  
   466  	if x.mode() == constant_ {
   467  		// spec: "a constant index must be non-negative ..."
   468  		if !allowNegative && constant.Sign(x.val) < 0 {
   469  			check.errorf(x, code, invalidArg+"%s %s must not be negative", what, x)
   470  			return false
   471  		}
   472  
   473  		// spec: "... and representable by a value of type int"
   474  		if !representableConst(x.val, check, Typ[Int], &x.val) {
   475  			check.errorf(x, code, invalidArg+"%s %s overflows int", what, x)
   476  			return false
   477  		}
   478  	}
   479  
   480  	return true
   481  }
   482  
   483  // indexedExpr wraps an ast.IndexExpr or ast.IndexListExpr.
   484  //
   485  // Orig holds the original ast.Expr from which this indexedExpr was derived.
   486  //
   487  // Note: indexedExpr (intentionally) does not wrap ast.Expr, as that leads to
   488  // accidental misuse such as encountered in golang/go#63933.
   489  //
   490  // TODO(rfindley): remove this helper, in favor of just having a helper
   491  // function that returns indices.
   492  type indexedExpr struct {
   493  	orig    ast.Expr   // the wrapped expr, which may be distinct from the IndexListExpr below.
   494  	x       ast.Expr   // expression
   495  	lbrack  token.Pos  // position of "["
   496  	indices []ast.Expr // index expressions
   497  	rbrack  token.Pos  // position of "]"
   498  }
   499  
   500  func (x *indexedExpr) Pos() token.Pos {
   501  	return x.orig.Pos()
   502  }
   503  
   504  func unpackIndexedExpr(n ast.Node) *indexedExpr {
   505  	switch e := n.(type) {
   506  	case *ast.IndexExpr:
   507  		return &indexedExpr{
   508  			orig:    e,
   509  			x:       e.X,
   510  			lbrack:  e.Lbrack,
   511  			indices: []ast.Expr{e.Index},
   512  			rbrack:  e.Rbrack,
   513  		}
   514  	case *ast.IndexListExpr:
   515  		return &indexedExpr{
   516  			orig:    e,
   517  			x:       e.X,
   518  			lbrack:  e.Lbrack,
   519  			indices: e.Indices,
   520  			rbrack:  e.Rbrack,
   521  		}
   522  	}
   523  	return nil
   524  }
   525
View as plain text