index.go

Documentation: go/types

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