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