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