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