diff options
author | Robert Griesemer <gri@golang.org> | 2021-04-07 17:47:14 -0700 |
---|---|---|
committer | Robert Griesemer <gri@golang.org> | 2021-04-10 19:02:05 +0000 |
commit | 36c5f902f9049b82da50ac66049371830e6de031 (patch) | |
tree | bbd636934391e7783ddbf32121c3c9da9c039b67 /src/cmd/compile/internal/types2/index.go | |
parent | 4638545d85d7e10e49132ee94ff9a6778db1c893 (diff) | |
download | go-36c5f902f9049b82da50ac66049371830e6de031.tar.gz go-36c5f902f9049b82da50ac66049371830e6de031.zip |
cmd/compile/internal/types2: factor out index/slice expr handling
First step towards lightening the load of Checker.exprInternal by
factoring out the code for index and slice expressions; incl. moving
a couple of related methods (Checker.index, Checker.indexedElts).
The code for handling index/slice expressions is copied 1:1 but
occurrences of "goto Error" are replaced by "x.mode = invalid"
followed by a "return".
Change-Id: I44048dcc4851dc5e24f5f169c17f536a37a6a676
Reviewed-on: https://go-review.googlesource.com/c/go/+/308370
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
Diffstat (limited to 'src/cmd/compile/internal/types2/index.go')
-rw-r--r-- | src/cmd/compile/internal/types2/index.go | 405 |
1 files changed, 405 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/types2/index.go b/src/cmd/compile/internal/types2/index.go new file mode 100644 index 0000000000..0f4adab237 --- /dev/null +++ b/src/cmd/compile/internal/types2/index.go @@ -0,0 +1,405 @@ +// Copyright 2021 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// This file implements typechecking of index/slice expressions. + +package types2 + +import ( + "cmd/compile/internal/syntax" + "go/constant" +) + +func (check *Checker) indexExpr(x *operand, e *syntax.IndexExpr) { + check.exprOrType(x, e.X) + if x.mode == invalid { + check.use(e.Index) + return + } + + if x.mode == typexpr { + // type instantiation + x.mode = invalid + x.typ = check.varType(e) + if x.typ != Typ[Invalid] { + x.mode = typexpr + } + return + } + + if x.mode == value { + if sig := asSignature(x.typ); sig != nil && len(sig.tparams) > 0 { + // function instantiation + check.funcInst(x, e) + return + } + } + + // ordinary index expression + valid := false + length := int64(-1) // valid if >= 0 + switch typ := optype(x.typ).(type) { + case *Basic: + if isString(typ) { + valid = true + if x.mode == constant_ { + length = int64(len(constant.StringVal(x.val))) + } + // an indexed string always yields a byte value + // (not a constant) even if the string and the + // index are constant + x.mode = value + x.typ = universeByte // use 'byte' name + } + + case *Array: + valid = true + length = typ.len + if x.mode != variable { + x.mode = value + } + x.typ = typ.elem + + case *Pointer: + if typ := asArray(typ.base); typ != nil { + valid = true + length = typ.len + x.mode = variable + x.typ = typ.elem + } + + case *Slice: + valid = true + x.mode = variable + x.typ = typ.elem + + case *Map: + var key operand + check.expr(&key, e.Index) + check.assignment(&key, typ.key, "map index") + // ok to continue even if indexing failed - map element type is known + x.mode = mapindex + x.typ = typ.elem + x.expr = e + return + + case *Sum: + // A sum type can be indexed if all of the sum's types + // support indexing and have the same index and element + // type. Special rules apply for maps in the sum type. + var tkey, telem Type // key is for map types only + nmaps := 0 // number of map types in sum type + if typ.is(func(t Type) bool { + var e Type + switch t := under(t).(type) { + case *Basic: + if isString(t) { + e = universeByte + } + case *Array: + e = t.elem + case *Pointer: + if t := asArray(t.base); t != nil { + e = t.elem + } + case *Slice: + e = t.elem + case *Map: + // If there are multiple maps in the sum type, + // they must have identical key types. + // TODO(gri) We may be able to relax this rule + // but it becomes complicated very quickly. + if tkey != nil && !Identical(t.key, tkey) { + return false + } + tkey = t.key + e = t.elem + nmaps++ + case *TypeParam: + check.errorf(x, "type of %s contains a type parameter - cannot index (implementation restriction)", x) + case *instance: + panic("unimplemented") + } + if e == nil || telem != nil && !Identical(e, telem) { + return false + } + telem = e + return true + }) { + // If there are maps, the index expression must be assignable + // to the map key type (as for simple map index expressions). + if nmaps > 0 { + var key operand + check.expr(&key, e.Index) + check.assignment(&key, tkey, "map index") + // ok to continue even if indexing failed - map element type is known + + // If there are only maps, we are done. + if nmaps == len(typ.types) { + x.mode = mapindex + x.typ = telem + x.expr = e + return + } + + // Otherwise we have mix of maps and other types. For + // now we require that the map key be an integer type. + // TODO(gri) This is probably not good enough. + valid = isInteger(tkey) + // avoid 2nd indexing error if indexing failed above + if !valid && key.mode == invalid { + x.mode = invalid + return + } + x.mode = value // map index expressions are not addressable + } else { + // no maps + valid = true + x.mode = variable + } + x.typ = telem + } + } + + if !valid { + check.errorf(x, invalidOp+"cannot index %s", x) + x.mode = invalid + return + } + + if e.Index == nil { + check.errorf(e, invalidAST+"missing index for %s", x) + x.mode = invalid + return + } + + index := e.Index + if l, _ := index.(*syntax.ListExpr); l != nil { + if n := len(l.ElemList); n <= 1 { + check.errorf(e, invalidAST+"invalid use of ListExpr for index expression %v with %d indices", e, n) + x.mode = invalid + return + } + // len(l.ElemList) > 1 + check.error(l.ElemList[1], invalidOp+"more than one index") + index = l.ElemList[0] // continue with first index + } + + // In pathological (invalid) cases (e.g.: type T1 [][[]T1{}[0][0]]T0) + // the element type may be accessed before it's set. Make sure we have + // a valid type. + if x.typ == nil { + x.typ = Typ[Invalid] + } + + check.index(index, length) +} + +func (check *Checker) sliceExpr(x *operand, e *syntax.SliceExpr) { + check.expr(x, e.X) + if x.mode == invalid { + check.use(e.Index[:]...) + return + } + + valid := false + length := int64(-1) // valid if >= 0 + switch typ := optype(x.typ).(type) { + case *Basic: + if isString(typ) { + if e.Full { + check.error(x, invalidOp+"3-index slice of string") + x.mode = invalid + return + } + valid = true + if x.mode == constant_ { + length = int64(len(constant.StringVal(x.val))) + } + // spec: "For untyped string operands the result + // is a non-constant value of type string." + if typ.kind == UntypedString { + x.typ = Typ[String] + } + } + + case *Array: + valid = true + length = typ.len + if x.mode != variable { + check.errorf(x, invalidOp+"%s (slice of unaddressable value)", x) + x.mode = invalid + return + } + x.typ = &Slice{elem: typ.elem} + + case *Pointer: + if typ := asArray(typ.base); typ != nil { + valid = true + length = typ.len + x.typ = &Slice{elem: typ.elem} + } + + case *Slice: + valid = true + // x.typ doesn't change + + case *Sum, *TypeParam: + check.error(x, "generic slice expressions not yet implemented") + x.mode = invalid + return + } + + if !valid { + check.errorf(x, invalidOp+"cannot slice %s", x) + x.mode = invalid + return + } + + x.mode = value + + // spec: "Only the first index may be omitted; it defaults to 0." + if e.Full && (e.Index[1] == nil || e.Index[2] == nil) { + check.error(e, invalidAST+"2nd and 3rd index required in 3-index slice") + x.mode = invalid + return + } + + // check indices + var ind [3]int64 + for i, expr := range e.Index { + x := int64(-1) + switch { + case expr != nil: + // The "capacity" is only known statically for strings, arrays, + // and pointers to arrays, and it is the same as the length for + // those types. + max := int64(-1) + if length >= 0 { + max = length + 1 + } + if _, v := check.index(expr, max); v >= 0 { + x = v + } + case i == 0: + // default is 0 for the first index + x = 0 + case length >= 0: + // default is length (== capacity) otherwise + x = length + } + ind[i] = x + } + + // constant indices must be in range + // (check.index already checks that existing indices >= 0) +L: + for i, x := range ind[:len(ind)-1] { + if x > 0 { + for _, y := range ind[i+1:] { + if y >= 0 && x > y { + check.errorf(e, "invalid slice indices: %d > %d", x, y) + break L // only report one error, ok to continue + } + } + } + } +} + +// index checks an index expression for validity. +// If max >= 0, it is the upper bound for index. +// If the result typ is != Typ[Invalid], index is valid and typ is its (possibly named) integer type. +// If the result val >= 0, index is valid and val is its constant int value. +func (check *Checker) index(index syntax.Expr, max int64) (typ Type, val int64) { + typ = Typ[Invalid] + val = -1 + + var x operand + check.expr(&x, index) + if x.mode == invalid { + return + } + + // an untyped constant must be representable as Int + check.convertUntyped(&x, Typ[Int]) + if x.mode == invalid { + return + } + + // the index must be of integer type + if !isInteger(x.typ) { + check.errorf(&x, invalidArg+"index %s must be integer", &x) + return + } + + if x.mode != constant_ { + return x.typ, -1 + } + + // a constant index i must be in bounds + if constant.Sign(x.val) < 0 { + check.errorf(&x, invalidArg+"index %s must not be negative", &x) + return + } + + v, valid := constant.Int64Val(constant.ToInt(x.val)) + if !valid || max >= 0 && v >= max { + if check.conf.CompilerErrorMessages { + check.errorf(&x, "array index %s out of bounds [0:%d]", x.val.String(), max) + } else { + check.errorf(&x, "index %s is out of bounds", &x) + } + return + } + + // 0 <= v [ && v < max ] + return Typ[Int], v +} + +// indexElts checks the elements (elts) of an array or slice composite literal +// against the literal's element type (typ), and the element indices against +// the literal length if known (length >= 0). It returns the length of the +// literal (maximum index value + 1). +func (check *Checker) indexedElts(elts []syntax.Expr, typ Type, length int64) int64 { + visited := make(map[int64]bool, len(elts)) + var index, max int64 + for _, e := range elts { + // determine and check index + validIndex := false + eval := e + if kv, _ := e.(*syntax.KeyValueExpr); kv != nil { + if typ, i := check.index(kv.Key, length); typ != Typ[Invalid] { + if i >= 0 { + index = i + validIndex = true + } else { + check.errorf(e, "index %s must be integer constant", kv.Key) + } + } + eval = kv.Value + } else if length >= 0 && index >= length { + check.errorf(e, "index %d is out of bounds (>= %d)", index, length) + } else { + validIndex = true + } + + // if we have a valid index, check for duplicate entries + if validIndex { + if visited[index] { + check.errorf(e, "duplicate index %d in array or slice literal", index) + } + visited[index] = true + } + index++ + if index > max { + max = index + } + + // check element against composite literal element type + var x operand + check.exprWithHint(&x, eval, typ) + check.assignment(&x, typ, "array or slice literal") + } + return max +} |