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