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