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