| // Copyright 2017 The Wuffs Authors. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| package check |
| |
| import ( |
| "fmt" |
| "math/big" |
| |
| a "github.com/google/wuffs/lang/ast" |
| t "github.com/google/wuffs/lang/token" |
| ) |
| |
| type cpuArchBits uint32 |
| |
| const ( |
| cpuArchBitsARMCRC32 = cpuArchBits(0x00000001) |
| cpuArchBitsARMNeon = cpuArchBits(0x00000002) |
| cpuArchBitsX86SSE42 = cpuArchBits(0x00000004) |
| cpuArchBitsX86AVX2 = cpuArchBits(0x00000008) |
| ) |
| |
| func calcCPUArchBits(n *a.Func) (ret cpuArchBits) { |
| for _, o := range n.Asserts() { |
| o := o.AsAssert() |
| if !o.IsChooseCPUArch() { |
| continue |
| } |
| switch o.Condition().RHS().AsExpr().Ident() { |
| case t.IDARMCRC32: |
| ret |= cpuArchBitsARMCRC32 |
| case t.IDARMNeon: |
| ret |= cpuArchBitsARMNeon |
| case t.IDX86SSE42: |
| ret |= cpuArchBitsX86SSE42 |
| case t.IDX86AVX2: |
| ret |= cpuArchBitsX86SSE42 | cpuArchBitsX86AVX2 |
| } |
| } |
| return ret |
| } |
| |
| func (q *checker) tcheckCPUArchBits(cab cpuArchBits, typ *a.TypeExpr) error { |
| if qid := typ.Innermost().QID(); (qid[0] == t.IDBase) && qid[1].IsBuiltInCPUArch() { |
| need := cpuArchBits(0) |
| switch qid[1] { |
| case t.IDARMCRC32Utility, t.IDARMCRC32U32: |
| need = cpuArchBitsARMCRC32 |
| case t.IDARMNeonUtility, |
| t.IDARMNeonU8x8, t.IDARMNeonU16x4, t.IDARMNeonU32x2, t.IDARMNeonU64x1, |
| t.IDARMNeonU8x16, t.IDARMNeonU16x8, t.IDARMNeonU32x4, t.IDARMNeonU64x2: |
| need = cpuArchBitsARMNeon |
| case t.IDX86SSE42Utility, t.IDX86M128I: |
| need = cpuArchBitsX86SSE42 |
| } |
| if (cab & need) != need { |
| return fmt.Errorf("check: missing cpu_arch for %q", typ.Innermost().Str(q.tm)) |
| } |
| } |
| return nil |
| } |
| |
| func (q *checker) tcheckVars(cab cpuArchBits, block []*a.Node) error { |
| for _, o := range block { |
| if o.Kind() != a.KVar { |
| break |
| } |
| |
| q.errFilename, q.errLine = o.AsRaw().FilenameLine() |
| |
| o := o.AsVar() |
| name := o.Name() |
| if _, ok := q.localVars[name]; ok { |
| return fmt.Errorf("check: duplicate var %q", name.Str(q.tm)) |
| } else if q.c.topLevelNames[name] != 0 { |
| return &Error{ |
| Err: fmt.Errorf("check: var %q shadows top level name", name.Str(q.tm)), |
| Filename: o.Filename(), |
| Line: o.Line(), |
| } |
| } |
| if err := q.tcheckTypeExpr(o.XType(), 0); err != nil { |
| return err |
| } |
| if err := q.tcheckCPUArchBits(cab, o.XType()); err != nil { |
| return err |
| } |
| q.localVars[name] = o.XType() |
| } |
| return nil |
| } |
| |
| func (q *checker) tcheckStatement(n *a.Node) error { |
| q.errFilename, q.errLine = n.AsRaw().FilenameLine() |
| |
| switch n.Kind() { |
| case a.KAssert: |
| if err := q.tcheckAssert(n.AsAssert()); err != nil { |
| return err |
| } |
| |
| case a.KAssign: |
| if err := q.tcheckAssign(n.AsAssign()); err != nil { |
| return err |
| } |
| |
| case a.KChoose: |
| if err := q.tcheckChoose(n.AsChoose()); err != nil { |
| return err |
| } |
| |
| case a.KIf: |
| for n := n.AsIf(); n != nil; n = n.ElseIf() { |
| cond := n.Condition() |
| if cond.Effect() != 0 { |
| return fmt.Errorf("check: internal error: if-condition is not effect-free") |
| } |
| if err := q.tcheckExpr(cond, 0); err != nil { |
| return err |
| } |
| if !cond.MType().IsBool() { |
| return fmt.Errorf("check: if condition %q, of type %q, does not have a boolean type", |
| cond.Str(q.tm), cond.MType().Str(q.tm)) |
| } |
| for _, o := range n.BodyIfTrue() { |
| if err := q.tcheckStatement(o); err != nil { |
| return err |
| } |
| } |
| for _, o := range n.BodyIfFalse() { |
| if err := q.tcheckStatement(o); err != nil { |
| return err |
| } |
| } |
| } |
| for n := n.AsIf(); n != nil; n = n.ElseIf() { |
| setPlaceholderMBoundsMType(n.AsNode()) |
| } |
| return nil |
| |
| case a.KIOBind: |
| n := n.AsIOBind() |
| if err := q.tcheckExpr(n.IO(), 0); err != nil { |
| return err |
| } |
| if typ := n.IO().MType(); !typ.IsIOType() { |
| return fmt.Errorf("check: %s expression %q, of type %q, does not have an I/O type", |
| n.Keyword().Str(q.tm), n.IO().Str(q.tm), typ.Str(q.tm)) |
| } |
| |
| arg1Typ := typeExprSliceU8 |
| if n.Keyword() == t.IDIOLimit { |
| arg1Typ = typeExprU64 |
| } |
| if err := q.tcheckExpr(n.Arg1(), 0); err != nil { |
| return err |
| } |
| if typ := n.Arg1().MType(); !typ.EqIgnoringRefinements(arg1Typ) { |
| return fmt.Errorf("check: %s expression %q, of type %q, does not have type %q", |
| n.Keyword().Str(q.tm), n.Arg1().Str(q.tm), typ.Str(q.tm), arg1Typ.Str(q.tm)) |
| } |
| |
| for _, o := range n.Body() { |
| // TODO: prohibit jumps (breaks, continues), rets (returns, yields) |
| // and retry-calling ? methods while inside an io_bind body. |
| if err := q.tcheckStatement(o); err != nil { |
| return err |
| } |
| } |
| |
| case a.KIterate: |
| for n := n.AsIterate(); n != nil; n = n.ElseIterate() { |
| if err := q.tcheckExpr(n.UnrollAsExpr(), 0); err != nil { |
| return err |
| } |
| for _, o := range n.Assigns() { |
| if err := q.tcheckStatement(o); err != nil { |
| return err |
| } |
| o := o.AsAssign() |
| if typ := o.LHS().MType(); !typ.IsSliceType() { |
| return fmt.Errorf("check: iterate assignment to %q, of type %q, does not have slice type", |
| o.LHS().Str(q.tm), typ.Str(q.tm)) |
| } |
| } |
| // TODO: prohibit jumps (breaks, continues), rets (returns, yields) and |
| // retry-calling ? methods while inside an iterate body. |
| if err := q.tcheckLoop(n); err != nil { |
| return err |
| } |
| } |
| for n := n.AsIterate(); n != nil; n = n.ElseIterate() { |
| setPlaceholderMBoundsMType(n.AsNode()) |
| } |
| return nil |
| |
| case a.KJump: |
| // No-op. |
| |
| case a.KRet: |
| n := n.AsRet() |
| lTyp := q.astFunc.Out() |
| if q.astFunc.Effect().Coroutine() { |
| lTyp = typeExprStatus |
| } else if lTyp == nil { |
| lTyp = typeExprEmptyStruct |
| } |
| value := n.Value() |
| if err := q.tcheckExpr(value, 0); err != nil { |
| return err |
| } |
| rTyp := value.MType() |
| if !(rTyp.IsIdeal() && lTyp.IsNumType()) && !lTyp.EqIgnoringRefinements(rTyp) { |
| return fmt.Errorf("check: cannot return %q (of type %q) as type %q", |
| value.Str(q.tm), rTyp.Str(q.tm), lTyp.Str(q.tm)) |
| } |
| |
| case a.KVar: |
| n := n.AsVar() |
| if n.XType().AsNode().MType() == nil { |
| return fmt.Errorf("check: internal error: unchecked type expression %q", n.XType().Str(q.tm)) |
| } |
| // TODO: check that the default zero value is assignable to n.XType(). |
| |
| case a.KWhile: |
| n := n.AsWhile() |
| cond := n.Condition() |
| if cond.Effect() != 0 { |
| return fmt.Errorf("check: internal error: while-condition is not effect-free") |
| } |
| if err := q.tcheckExpr(cond, 0); err != nil { |
| return err |
| } |
| if !cond.MType().IsBool() { |
| return fmt.Errorf("check: for-loop condition %q, of type %q, does not have a boolean type", |
| cond.Str(q.tm), cond.MType().Str(q.tm)) |
| } |
| if err := q.tcheckLoop(n); err != nil { |
| return err |
| } |
| |
| default: |
| return fmt.Errorf("check: unrecognized ast.Kind (%s) for tcheckStatement", n.Kind()) |
| } |
| |
| setPlaceholderMBoundsMType(n) |
| return nil |
| } |
| |
| func (q *checker) tcheckFuncAssert(n *a.Assert) error { |
| if n.IsChooseCPUArch() { |
| cond := n.Condition() |
| cond.SetMType(typeExprBool) |
| cond.LHS().AsExpr().SetMType(typeExprU32) |
| cond.RHS().AsExpr().SetMType(typeExprU32) |
| return nil |
| } |
| return fmt.Errorf("check: function assertions are not supported yet") |
| } |
| |
| func (q *checker) tcheckAssert(n *a.Assert) error { |
| cond := n.Condition() |
| if err := q.tcheckExpr(cond, 0); err != nil { |
| return err |
| } |
| if !cond.MType().IsBool() { |
| return fmt.Errorf("check: assert condition %q, of type %q, does not have a boolean type", |
| cond.Str(q.tm), cond.MType().Str(q.tm)) |
| } |
| for _, o := range n.Args() { |
| if err := q.tcheckExpr(o.AsArg().Value(), 0); err != nil { |
| return err |
| } |
| setPlaceholderMBoundsMType(o) |
| } |
| // TODO: check that there are no side effects. |
| return nil |
| } |
| |
| func (q *checker) tcheckEq(lID t.ID, lhs *a.Expr, lTyp *a.TypeExpr, rhs *a.Expr, rTyp *a.TypeExpr) error { |
| if (rTyp.IsIdeal() && lTyp.IsNumType()) || |
| (rTyp.EqIgnoringRefinements(lTyp)) || |
| (rTyp.IsNullptr() && lTyp.Decorator() == t.IDNptr) { |
| return nil |
| } |
| lStr := "???" |
| if lID != 0 { |
| lStr = lID.Str(q.tm) |
| } else if lhs != nil { |
| lStr = lhs.Str(q.tm) |
| } |
| return fmt.Errorf("check: cannot assign %q of type %q to %q of type %q", |
| rhs.Str(q.tm), rTyp.Str(q.tm), lStr, lTyp.Str(q.tm)) |
| } |
| |
| func (q *checker) tcheckAssign(n *a.Assign) error { |
| rhs := n.RHS() |
| if err := q.tcheckExpr(rhs, 0); err != nil { |
| return err |
| } |
| lhs := n.LHS() |
| if lhs == nil { |
| return nil |
| } |
| if err := q.tcheckExpr(lhs, 0); err != nil { |
| return err |
| } |
| lTyp := lhs.MType() |
| rTyp := rhs.MType() |
| |
| if op := n.Operator(); op == t.IDEq || op == t.IDEqQuestion { |
| if (op == t.IDEqQuestion) && !rTyp.Eq(typeExprStatus) { |
| return fmt.Errorf("check: =? only works with the base.status type") |
| } |
| return q.tcheckEq(0, lhs, lTyp, rhs, rTyp) |
| } |
| |
| if !lTyp.IsNumType() { |
| return fmt.Errorf("check: assignment %q: assignee %q, of type %q, does not have numeric type", |
| n.Operator().Str(q.tm), lhs.Str(q.tm), lTyp.Str(q.tm)) |
| } |
| |
| switch n.Operator() { |
| case t.IDShiftLEq, t.IDShiftREq, t.IDTildeModShiftLEq: |
| if !rTyp.IsNumTypeOrIdeal() { |
| return fmt.Errorf("check: assignment %q: shift %q, of type %q, does not have numeric type", |
| n.Operator().Str(q.tm), rhs.Str(q.tm), rTyp.Str(q.tm)) |
| } |
| return nil |
| |
| case t.IDTildeModPlusEq, t.IDTildeModMinusEq, t.IDTildeModStarEq, |
| t.IDTildeSatPlusEq, t.IDTildeSatMinusEq: |
| |
| if !lTyp.IsUnsignedInteger() { |
| return fmt.Errorf("check: assignment %q: %q, of type %q, does not have unsigned integer type", |
| n.Operator().Str(q.tm), lhs.Str(q.tm), lTyp.Str(q.tm)) |
| } |
| } |
| |
| if !(rTyp.IsIdeal() && lTyp.IsNumType()) && !lTyp.EqIgnoringRefinements(rTyp) { |
| return fmt.Errorf("check: assignment %q: %q and %q, of types %q and %q, do not have compatible types", |
| n.Operator().Str(q.tm), |
| lhs.Str(q.tm), rhs.Str(q.tm), |
| lTyp.Str(q.tm), rTyp.Str(q.tm), |
| ) |
| } |
| return nil |
| } |
| |
| func (q *checker) tcheckLoop(n a.Loop) error { |
| for _, o := range n.Asserts() { |
| if err := q.tcheckAssert(o.AsAssert()); err != nil { |
| return err |
| } |
| setPlaceholderMBoundsMType(o) |
| } |
| for _, o := range n.Body() { |
| if err := q.tcheckStatement(o); err != nil { |
| return err |
| } |
| } |
| return nil |
| } |
| |
| func (q *checker) tcheckExpr(n *a.Expr, depth uint32) error { |
| if depth > a.MaxExprDepth { |
| return fmt.Errorf("check: expression recursion depth too large") |
| } |
| depth++ |
| |
| if n.MType() != nil { |
| return nil |
| } |
| |
| switch op := n.Operator(); { |
| case op.IsXUnaryOp(): |
| return q.tcheckExprUnaryOp(n, depth) |
| case op.IsXBinaryOp(): |
| return q.tcheckExprBinaryOp(n, depth) |
| case op.IsXAssociativeOp(): |
| return q.tcheckExprAssociativeOp(n, depth) |
| } |
| return q.tcheckExprOther(n, depth) |
| } |
| |
| func (q *checker) tcheckExprOther(n *a.Expr, depth uint32) error { |
| switch n.Operator() { |
| case 0: |
| id1 := n.Ident() |
| if id1.IsNumLiteral(q.tm) { |
| z := big.NewInt(0) |
| s := id1.Str(q.tm) |
| if _, ok := z.SetString(s, 0); !ok { |
| return fmt.Errorf("check: invalid numeric literal %q", s) |
| } |
| n.SetConstValue(z) |
| n.SetMType(typeExprIdeal) |
| return nil |
| |
| } else if id1.IsSQStrLiteral(q.tm) { |
| s := id1.Str(q.tm) |
| unescaped, ok := t.Unescape(id1.Str(q.tm)) |
| if !ok { |
| return fmt.Errorf("check: invalid '-string literal %q", s) |
| } |
| |
| z := big.NewInt(0) |
| i, iEnd, iDelta := 0, len(unescaped), +1 // Big-endian. |
| if (len(s) > 2) && (s[len(s)-2] == 'l') { |
| i, iEnd, iDelta = len(unescaped)-1, -1, -1 // Little-endian. |
| } |
| for ; i != iEnd; i += iDelta { |
| z.Lsh(z, 8) |
| z.Or(z, big.NewInt(int64(unescaped[i]))) |
| } |
| |
| n.SetConstValue(z) |
| n.SetMType(typeExprIdeal) |
| return nil |
| |
| } else if id1.IsDQStrLiteral(q.tm) { |
| if _, ok := q.c.statuses[t.QID{0, n.Ident()}]; !ok { |
| return fmt.Errorf("check: unrecognized status %s", n.Ident().Str(q.tm)) |
| } |
| n.SetMType(typeExprStatus) |
| return nil |
| |
| } else if id1.IsIdent(q.tm) { |
| if q.localVars != nil { |
| if typ, ok := q.localVars[id1]; ok { |
| n.SetMType(typ) |
| return nil |
| } |
| } |
| if q.c.topLevelNames[id1] == a.KUse { |
| n.SetConstValue(zero) |
| n.SetMType(typeExprPackage) |
| return nil |
| } |
| return q.tcheckExprXDotY(n, 0, id1) |
| } |
| |
| switch id1 { |
| case t.IDFalse: |
| n.SetConstValue(zero) |
| n.SetMType(typeExprBool) |
| return nil |
| |
| case t.IDTrue: |
| n.SetConstValue(one) |
| n.SetMType(typeExprBool) |
| return nil |
| |
| case t.IDNothing: |
| n.SetConstValue(zero) |
| n.SetMType(typeExprEmptyStruct) |
| return nil |
| |
| case t.IDNullptr: |
| n.SetConstValue(zero) |
| n.SetMType(typeExprNullptr) |
| return nil |
| |
| case t.IDOk: |
| n.SetConstValue(zero) |
| n.SetMType(typeExprStatus) |
| return nil |
| } |
| |
| case t.IDOpenParen: |
| // n is a function call. |
| return q.tcheckExprCall(n, depth) |
| |
| case t.IDOpenBracket: |
| // n is an index. |
| lhs := n.LHS().AsExpr() |
| if err := q.tcheckExpr(lhs, depth); err != nil { |
| return err |
| } |
| rhs := n.RHS().AsExpr() |
| if err := q.tcheckExpr(rhs, depth); err != nil { |
| return err |
| } |
| lTyp := lhs.MType() |
| if key := lTyp.Decorator(); key != t.IDArray && key != t.IDSlice { |
| return fmt.Errorf("check: %s is an index expression but %s has type %s, not an array or slice type", |
| n.Str(q.tm), lhs.Str(q.tm), lTyp.Str(q.tm)) |
| } |
| rTyp := rhs.MType() |
| if !rTyp.IsNumTypeOrIdeal() { |
| return fmt.Errorf("check: %s is an index expression but %s has type %s, not a numeric type", |
| n.Str(q.tm), rhs.Str(q.tm), rTyp.Str(q.tm)) |
| } |
| n.SetMType(lTyp.Inner()) |
| return nil |
| |
| case t.IDDotDot: |
| // n is a slice. |
| // TODO: require that the i and j in a[i .. j] are *unsigned* (or |
| // non-negative constants)? |
| if mhs := n.MHS().AsExpr(); mhs != nil { |
| if err := q.tcheckExpr(mhs, depth); err != nil { |
| return err |
| } |
| mTyp := mhs.MType() |
| if !mTyp.IsNumTypeOrIdeal() { |
| return fmt.Errorf("check: %s is a slice expression but %s has type %s, not a numeric type", |
| n.Str(q.tm), mhs.Str(q.tm), mTyp.Str(q.tm)) |
| } |
| } |
| if rhs := n.RHS().AsExpr(); rhs != nil { |
| if err := q.tcheckExpr(rhs, depth); err != nil { |
| return err |
| } |
| rTyp := rhs.MType() |
| if !rTyp.IsNumTypeOrIdeal() { |
| return fmt.Errorf("check: %s is a slice expression but %s has type %s, not a numeric type", |
| n.Str(q.tm), rhs.Str(q.tm), rTyp.Str(q.tm)) |
| } |
| } |
| lhs := n.LHS().AsExpr() |
| if err := q.tcheckExpr(lhs, depth); err != nil { |
| return err |
| } |
| lTyp := lhs.MType() |
| switch lTyp.Decorator() { |
| default: |
| return fmt.Errorf("check: %s is a slice expression but %s has type %s, not an array or slice type", |
| n.Str(q.tm), lhs.Str(q.tm), lTyp.Str(q.tm)) |
| case t.IDArray: |
| n.SetMType(a.NewTypeExpr(t.IDSlice, 0, 0, nil, nil, lTyp.Inner())) |
| case t.IDSlice: |
| n.SetMType(lTyp) |
| } |
| return nil |
| |
| case t.IDDot: |
| return q.tcheckDot(n, depth) |
| |
| case t.IDComma: |
| for _, o := range n.Args() { |
| o := o.AsExpr() |
| if err := q.tcheckExpr(o, depth); err != nil { |
| return err |
| } |
| } |
| n.SetMType(typeExprList) |
| return nil |
| } |
| |
| return fmt.Errorf("check: unrecognized token (0x%X) in expression %q for tcheckExprOther", |
| n.Operator(), n.Str(q.tm)) |
| } |
| |
| func (q *checker) tcheckExprXDotY(n *a.Expr, x t.ID, y t.ID) error { |
| qid := t.QID{x, y} |
| if c, ok := q.c.consts[qid]; ok { |
| // TODO: check somewhere that a global ident (i.e. a const) is |
| // not directly in the LHS of an assignment. |
| n.SetGlobalIdent() |
| n.SetConstValue(c.Value().ConstValue()) |
| n.SetMType(c.XType()) |
| return nil |
| } |
| if _, ok := q.c.statuses[t.QID{x, y}]; ok { |
| n.SetMType(typeExprStatus) |
| return nil |
| } |
| // TODO: look in q.c.structs. |
| return fmt.Errorf("check: unrecognized name %q", qid.Str(q.tm)) |
| } |
| |
| func (q *checker) tcheckExprCall(n *a.Expr, depth uint32) error { |
| lhs := n.LHS().AsExpr() |
| if err := q.tcheckExpr(lhs, depth); err != nil { |
| return err |
| } |
| f, err := q.c.resolveFunc(lhs.MType()) |
| if err != nil { |
| return err |
| } |
| if ne, fe := n.Effect(), f.Effect(); ne != fe { |
| return fmt.Errorf("check: %q has effect %q but %q has effect %q", |
| n.Str(q.tm), ne, f.QQID().Str(q.tm), fe) |
| } |
| if f.HasChooseCPUArch() { |
| return fmt.Errorf(`check: cannot call cpu_arch function %q directly, only via "choose"`, |
| f.QQID().Str(q.tm)) |
| } |
| |
| genericType1 := (*a.TypeExpr)(nil) |
| genericType2 := (*a.TypeExpr)(nil) |
| if recv := f.Receiver(); recv[0] == t.IDBase { |
| switch recv[1] { |
| case t.IDDagger1: |
| genericType1 = lhs.MType().Receiver() |
| case t.IDDagger2: |
| genericType2 = lhs.MType().Receiver() |
| if genericType2.Decorator() != t.IDTable { |
| return fmt.Errorf("check: internal error: %q is not a generic table", genericType2.Str(q.tm)) |
| } |
| genericType1 = a.NewTypeExpr(t.IDSlice, 0, 0, nil, nil, genericType2.Inner()) |
| } |
| } |
| |
| // Check that the func's in type matches the arguments. |
| inFields := f.In().Fields() |
| if len(inFields) != len(n.Args()) { |
| return fmt.Errorf("check: %q has %d arguments but %d were given", |
| lhs.MType().Str(q.tm), len(inFields), len(n.Args())) |
| } |
| for i, o := range n.Args() { |
| o := o.AsArg() |
| if err := q.tcheckExpr(o.Value(), depth); err != nil { |
| return err |
| } |
| |
| inField := inFields[i].AsField() |
| if o.Name() != inField.Name() { |
| return fmt.Errorf("check: argument name: got %q, want %q", o.Name().Str(q.tm), inField.Name().Str(q.tm)) |
| } |
| |
| inFieldTyp := inField.XType() |
| if genericType1 != nil && inFieldTyp.Eq(typeExprGeneric1) { |
| inFieldTyp = genericType1 |
| } else if genericType2 != nil && inFieldTyp.Eq(typeExprGeneric2) { |
| inFieldTyp = genericType2 |
| } |
| if err := q.tcheckEq(inField.Name(), nil, inFieldTyp, o.Value(), o.Value().MType()); err != nil { |
| return err |
| } |
| setPlaceholderMBoundsMType(o.AsNode()) |
| } |
| |
| oTyp := f.Out() |
| if oTyp == nil { |
| if n.Effect().Coroutine() { |
| n.SetMType(typeExprStatus) |
| } else { |
| n.SetMType(typeExprEmptyStruct) |
| } |
| } else if genericType1 != nil && oTyp.Eq(typeExprGeneric1) { |
| n.SetMType(genericType1) |
| } else if genericType2 != nil && oTyp.Eq(typeExprGeneric2) { |
| n.SetMType(genericType2) |
| } else { |
| n.SetMType(oTyp) |
| } |
| return nil |
| } |
| |
| func (q *checker) tcheckDot(n *a.Expr, depth uint32) error { |
| lhs := n.LHS().AsExpr() |
| if err := q.tcheckExpr(lhs, depth); err != nil { |
| return err |
| } |
| if lhs.MType() == typeExprPackage { |
| return q.tcheckExprXDotY(n, lhs.Ident(), n.Ident()) |
| } |
| lTyp := lhs.MType().Pointee() |
| lQID := lTyp.QID() |
| qqid := t.QQID{lQID[0], lQID[1], n.Ident()} |
| |
| if lTyp.IsSliceType() { |
| qqid[0] = t.IDBase |
| qqid[1] = t.IDDagger1 |
| if (q.c.builtInSliceFuncs[qqid] != nil) || |
| ((q.c.builtInSliceU8Funcs[qqid] != nil) && lTyp.Eq(typeExprSliceU8)) { |
| n.SetMType(a.NewTypeExpr(t.IDFunc, 0, n.Ident(), lTyp.AsNode(), nil, nil)) |
| return nil |
| } |
| return fmt.Errorf("check: no slice method %q", n.Ident().Str(q.tm)) |
| |
| } else if lTyp.IsTableType() { |
| qqid[0] = t.IDBase |
| qqid[1] = t.IDDagger2 |
| if q.c.builtInTableFuncs[qqid] != nil { |
| n.SetMType(a.NewTypeExpr(t.IDFunc, 0, n.Ident(), lTyp.AsNode(), nil, nil)) |
| return nil |
| } |
| return fmt.Errorf("check: no table method %q", n.Ident().Str(q.tm)) |
| |
| } else if lTyp.Decorator() != 0 { |
| return fmt.Errorf("check: invalid type %q for dot-expression LHS %q", lTyp.Str(q.tm), lhs.Str(q.tm)) |
| } |
| |
| if f := q.c.funcs[qqid]; f != nil { |
| n.SetMType(a.NewTypeExpr(t.IDFunc, 0, n.Ident(), lTyp.AsNode(), nil, nil)) |
| return nil |
| } |
| |
| s := (*a.Struct)(nil) |
| if q.astFunc != nil && lQID[0] == 0 && lQID[1] == t.IDArgs { |
| s = q.astFunc.In() |
| } |
| if s == nil { |
| s = q.c.structs[lQID] |
| if s == nil { |
| if lQID[0] == t.IDBase { |
| return fmt.Errorf("check: no built-in function %q found", qqid.Str(q.tm)) |
| } |
| return fmt.Errorf("check: no struct type %q found for expression %q", lTyp.Str(q.tm), lhs.Str(q.tm)) |
| } |
| } |
| |
| for _, field := range s.Fields() { |
| f := field.AsField() |
| if f.Name() == n.Ident() { |
| n.SetMType(f.XType()) |
| return nil |
| } |
| } |
| |
| return fmt.Errorf("check: no field or method named %q found in type %q for expression %q", |
| n.Ident().Str(q.tm), lTyp.Str(q.tm), n.Str(q.tm)) |
| } |
| |
| func (q *checker) tcheckExprUnaryOp(n *a.Expr, depth uint32) error { |
| rhs := n.RHS().AsExpr() |
| if err := q.tcheckExpr(rhs, depth); err != nil { |
| return err |
| } |
| rTyp := rhs.MType() |
| |
| switch n.Operator() { |
| case t.IDXUnaryPlus, t.IDXUnaryMinus: |
| if !rTyp.IsNumTypeOrIdeal() { |
| return fmt.Errorf("check: unary %q: %q, of type %q, does not have a numeric type", |
| n.Operator().AmbiguousForm().Str(q.tm), rhs.Str(q.tm), rTyp.Str(q.tm)) |
| } |
| if cv := rhs.ConstValue(); cv != nil { |
| if n.Operator() == t.IDXUnaryMinus { |
| cv = neg(cv) |
| } |
| n.SetConstValue(cv) |
| } |
| n.SetMType(rTyp.Unrefined()) |
| return nil |
| |
| case t.IDXUnaryNot: |
| if !rTyp.IsBool() { |
| return fmt.Errorf("check: unary %q: %q, of type %q, does not have a boolean type", |
| n.Operator().AmbiguousForm().Str(q.tm), rhs.Str(q.tm), rTyp.Str(q.tm)) |
| } |
| if cv := rhs.ConstValue(); cv != nil { |
| n.SetConstValue(btoi(cv.Sign() == 0)) |
| } |
| n.SetMType(typeExprBool) |
| return nil |
| } |
| return fmt.Errorf("check: unrecognized token (0x%X) for tcheckExprUnaryOp", n.Operator()) |
| } |
| |
| func (q *checker) tcheckExprBinaryOp(n *a.Expr, depth uint32) error { |
| lhs := n.LHS().AsExpr() |
| if err := q.tcheckExpr(lhs, depth); err != nil { |
| return err |
| } |
| lTyp := lhs.MType() |
| op := n.Operator() |
| if op == t.IDXBinaryAs { |
| rhs := n.RHS().AsTypeExpr() |
| if err := q.tcheckTypeExpr(rhs, 0); err != nil { |
| return err |
| } |
| if lTyp.IsNumTypeOrIdeal() && rhs.IsNumType() { |
| n.SetMType(rhs) |
| return nil |
| } |
| return fmt.Errorf("check: cannot convert expression %q, of type %q, as type %q", |
| lhs.Str(q.tm), lTyp.Str(q.tm), rhs.Str(q.tm)) |
| } |
| rhs := n.RHS().AsExpr() |
| if err := q.tcheckExpr(rhs, depth); err != nil { |
| return err |
| } |
| rTyp := rhs.MType() |
| |
| pointerComparison := false |
| switch op { |
| case t.IDXBinaryAnd, t.IDXBinaryOr: |
| if !lTyp.IsBool() { |
| return fmt.Errorf("check: binary %q: %q, of type %q, does not have a boolean type", |
| op.AmbiguousForm().Str(q.tm), lhs.Str(q.tm), lTyp.Str(q.tm)) |
| } |
| if !rTyp.IsBool() { |
| return fmt.Errorf("check: binary %q: %q, of type %q, does not have a boolean type", |
| op.AmbiguousForm().Str(q.tm), rhs.Str(q.tm), rTyp.Str(q.tm)) |
| } |
| default: |
| bad := (*a.Expr)(nil) |
| if !lTyp.IsNumTypeOrIdeal() { |
| bad = lhs |
| } else if !rTyp.IsNumTypeOrIdeal() { |
| bad = rhs |
| } |
| if op == t.IDXBinaryNotEq || op == t.IDXBinaryEqEq { |
| if lTyp.Eq(typeExprStatus) && rTyp.Eq(typeExprStatus) { |
| break |
| } |
| lNullptr := lTyp.Eq(typeExprNullptr) |
| rNullptr := rTyp.Eq(typeExprNullptr) |
| if (lNullptr && rNullptr) || |
| (lNullptr && rTyp.IsPointerType()) || |
| (rNullptr && lTyp.IsPointerType()) { |
| pointerComparison = true |
| break |
| } |
| } |
| if bad != nil { |
| return fmt.Errorf("check: binary %q: %q, of type %q, does not have a numeric type", |
| op.AmbiguousForm().Str(q.tm), bad.Str(q.tm), bad.MType().Str(q.tm)) |
| } |
| } |
| |
| switch op { |
| default: |
| if pointerComparison { |
| break |
| } |
| if !lTyp.EqIgnoringRefinements(rTyp) && !lTyp.IsIdeal() && !rTyp.IsIdeal() { |
| return fmt.Errorf("check: binary %q: %q and %q, of types %q and %q, do not have compatible types", |
| op.AmbiguousForm().Str(q.tm), |
| lhs.Str(q.tm), rhs.Str(q.tm), |
| lTyp.Str(q.tm), rTyp.Str(q.tm), |
| ) |
| } |
| case t.IDXBinaryShiftL, t.IDXBinaryShiftR, t.IDXBinaryTildeModShiftL: |
| if lTyp.IsIdeal() && !rTyp.IsIdeal() { |
| return fmt.Errorf("check: binary %q: %q and %q, of types %q and %q; "+ |
| "cannot shift an ideal number by a non-ideal number", |
| op.AmbiguousForm().Str(q.tm), |
| lhs.Str(q.tm), rhs.Str(q.tm), |
| lTyp.Str(q.tm), rTyp.Str(q.tm), |
| ) |
| } |
| } |
| |
| switch op { |
| case t.IDXBinaryTildeModPlus, t.IDXBinaryTildeModMinus, t.IDXBinaryTildeModStar, |
| t.IDXBinaryTildeSatPlus, t.IDXBinaryTildeSatMinus: |
| |
| typ := lTyp |
| if typ.IsIdeal() { |
| typ = rTyp |
| if typ.IsIdeal() { |
| return fmt.Errorf("check: binary %q: %q and %q, of types %q and %q, do not have non-ideal types", |
| op.AmbiguousForm().Str(q.tm), |
| lhs.Str(q.tm), rhs.Str(q.tm), |
| lTyp.Str(q.tm), rTyp.Str(q.tm), |
| ) |
| } |
| } |
| if !typ.IsUnsignedInteger() { |
| return fmt.Errorf("check: binary %q: %q and %q, of types %q and %q, do not have unsigned integer types", |
| op.AmbiguousForm().Str(q.tm), |
| lhs.Str(q.tm), rhs.Str(q.tm), |
| lTyp.Str(q.tm), rTyp.Str(q.tm), |
| ) |
| } |
| } |
| |
| if lcv, rcv := lhs.ConstValue(), rhs.ConstValue(); lcv != nil && rcv != nil { |
| ncv, err := evalConstValueBinaryOp(q.tm, n, lcv, rcv) |
| if err != nil { |
| return err |
| } |
| n.SetConstValue(ncv) |
| } |
| |
| if (op < t.ID(len(comparisonOps))) && comparisonOps[op] { |
| n.SetMType(typeExprBool) |
| } else if !lTyp.IsIdeal() { |
| n.SetMType(lTyp.Unrefined()) |
| } else { |
| n.SetMType(rTyp.Unrefined()) |
| } |
| |
| return nil |
| } |
| |
| func evalConstValueBinaryOp(tm *t.Map, n *a.Expr, l *big.Int, r *big.Int) (*big.Int, error) { |
| switch n.Operator() { |
| case t.IDXBinaryPlus: |
| return big.NewInt(0).Add(l, r), nil |
| case t.IDXBinaryMinus: |
| return big.NewInt(0).Sub(l, r), nil |
| case t.IDXBinaryStar: |
| return big.NewInt(0).Mul(l, r), nil |
| case t.IDXBinarySlash: |
| if r.Sign() == 0 { |
| return nil, fmt.Errorf("check: division by zero in const expression %q", n.Str(tm)) |
| } |
| // TODO: decide on Euclidean division vs other definitions. See "go doc |
| // math/big int.divmod" for details. |
| return big.NewInt(0).Div(l, r), nil |
| case t.IDXBinaryShiftL: |
| if r.Sign() < 0 || r.Cmp(ffff) > 0 { |
| return nil, fmt.Errorf("check: shift %q out of range in const expression %q", |
| n.RHS().AsExpr().Str(tm), n.Str(tm)) |
| } |
| return big.NewInt(0).Lsh(l, uint(r.Uint64())), nil |
| case t.IDXBinaryShiftR: |
| if r.Sign() < 0 || r.Cmp(ffff) > 0 { |
| return nil, fmt.Errorf("check: shift %q out of range in const expression %q", |
| n.RHS().AsExpr().Str(tm), n.Str(tm)) |
| } |
| return big.NewInt(0).Rsh(l, uint(r.Uint64())), nil |
| case t.IDXBinaryAmp: |
| return big.NewInt(0).And(l, r), nil |
| case t.IDXBinaryPipe: |
| return big.NewInt(0).Or(l, r), nil |
| case t.IDXBinaryHat: |
| return big.NewInt(0).Xor(l, r), nil |
| case t.IDXBinaryPercent: |
| if r.Sign() == 0 { |
| return nil, fmt.Errorf("check: division by zero in const expression %q", n.Str(tm)) |
| } |
| return big.NewInt(0).Mod(l, r), nil |
| case t.IDXBinaryNotEq: |
| return btoi(l.Cmp(r) != 0), nil |
| case t.IDXBinaryLessThan: |
| return btoi(l.Cmp(r) < 0), nil |
| case t.IDXBinaryLessEq: |
| return btoi(l.Cmp(r) <= 0), nil |
| case t.IDXBinaryEqEq: |
| return btoi(l.Cmp(r) == 0), nil |
| case t.IDXBinaryGreaterEq: |
| return btoi(l.Cmp(r) >= 0), nil |
| case t.IDXBinaryGreaterThan: |
| return btoi(l.Cmp(r) > 0), nil |
| case t.IDXBinaryAnd: |
| return btoi((l.Sign() != 0) && (r.Sign() != 0)), nil |
| case t.IDXBinaryOr: |
| return btoi((l.Sign() != 0) || (r.Sign() != 0)), nil |
| |
| case t.IDXBinaryTildeModPlus, t.IDXBinaryTildeModMinus, |
| t.IDXBinaryTildeModStar, t.IDXBinaryTildeModShiftL, |
| t.IDXBinaryTildeSatPlus, t.IDXBinaryTildeSatMinus: |
| |
| return nil, fmt.Errorf("check: cannot apply tilde-operators to ideal numbers") |
| } |
| return nil, fmt.Errorf("check: unrecognized token (0x%X) for evalConstValueBinaryOp", n.Operator()) |
| } |
| |
| func (q *checker) tcheckExprAssociativeOp(n *a.Expr, depth uint32) error { |
| switch n.Operator() { |
| case t.IDXAssociativePlus, t.IDXAssociativeStar, |
| t.IDXAssociativeAmp, t.IDXAssociativePipe, t.IDXAssociativeHat: |
| |
| expr, typ := (*a.Expr)(nil), (*a.TypeExpr)(nil) |
| for _, o := range n.Args() { |
| o := o.AsExpr() |
| if err := q.tcheckExpr(o, depth); err != nil { |
| return err |
| } |
| oTyp := o.MType() |
| if oTyp.IsIdeal() { |
| continue |
| } |
| if !oTyp.IsNumType() { |
| return fmt.Errorf("check: associative %q: %q, of type %q, does not have a numeric type", |
| n.Operator().AmbiguousForm().Str(q.tm), o.Str(q.tm), oTyp.Str(q.tm)) |
| } |
| if typ == nil { |
| expr, typ = o, oTyp.Unrefined() |
| continue |
| } |
| if !typ.EqIgnoringRefinements(oTyp) { |
| return fmt.Errorf("check: associative %q: %q and %q, of types %q and %q, "+ |
| "do not have compatible types", |
| n.Operator().AmbiguousForm().Str(q.tm), |
| expr.Str(q.tm), o.Str(q.tm), |
| expr.MType().Str(q.tm), o.MType().Str(q.tm)) |
| } |
| } |
| if typ == nil { |
| typ = typeExprIdeal |
| } |
| n.SetMType(typ) |
| |
| case t.IDXAssociativeAnd, t.IDXAssociativeOr: |
| for _, o := range n.Args() { |
| o := o.AsExpr() |
| if err := q.tcheckExpr(o, depth); err != nil { |
| return err |
| } |
| if !o.MType().IsBool() { |
| return fmt.Errorf("check: associative %q: %q, of type %q, does not have a boolean type", |
| n.Operator().AmbiguousForm().Str(q.tm), o.Str(q.tm), o.MType().Str(q.tm)) |
| } |
| } |
| n.SetMType(typeExprBool) |
| |
| default: |
| return fmt.Errorf("check: unrecognized token (0x%X) for tcheckExprAssociativeOp", n.Operator()) |
| } |
| |
| ncv, err := evalConstValueAssociativeOp(q.tm, n) |
| n.SetConstValue(ncv) |
| return err |
| } |
| |
| func evalConstValueAssociativeOp(tm *t.Map, n *a.Expr) (*big.Int, error) { |
| args := n.Args() |
| if len(args) == 0 { |
| return nil, fmt.Errorf("check: no operands for associative operator") |
| } |
| cv0 := args[0].AsExpr().ConstValue() |
| if cv0 == nil { |
| return nil, nil |
| } |
| args = args[1:] |
| ncv := big.NewInt(0).Set(cv0) |
| |
| switch n.Operator() { |
| case t.IDXAssociativePlus: |
| for _, o := range args { |
| if cv := o.AsExpr().ConstValue(); cv == nil { |
| return nil, nil |
| } else { |
| ncv.Add(ncv, cv) |
| } |
| } |
| |
| case t.IDXAssociativeStar: |
| for _, o := range args { |
| if cv := o.AsExpr().ConstValue(); cv == nil { |
| return nil, nil |
| } else { |
| ncv.Mul(ncv, cv) |
| } |
| } |
| |
| case t.IDXAssociativeAmp, t.IDXAssociativeAnd: |
| for _, o := range args { |
| if cv := o.AsExpr().ConstValue(); cv == nil { |
| return nil, nil |
| } else { |
| ncv.And(ncv, cv) |
| } |
| } |
| |
| case t.IDXAssociativePipe, t.IDXAssociativeOr: |
| for _, o := range args { |
| if cv := o.AsExpr().ConstValue(); cv == nil { |
| return nil, nil |
| } else { |
| ncv.Or(ncv, cv) |
| } |
| } |
| |
| case t.IDXAssociativeHat: |
| for _, o := range args { |
| if cv := o.AsExpr().ConstValue(); cv == nil { |
| return nil, nil |
| } else { |
| ncv.Xor(ncv, cv) |
| } |
| } |
| |
| default: |
| return nil, fmt.Errorf("check: unrecognized token (0x%X) for evalConstValueAssociativeOp", n.Operator()) |
| } |
| |
| return ncv, nil |
| } |
| |
| func (q *checker) tcheckTypeExpr(typ *a.TypeExpr, depth uint32) error { |
| if depth > a.MaxTypeExprDepth { |
| return fmt.Errorf("check: type expression recursion depth too large") |
| } |
| depth++ |
| |
| swtch: |
| switch typ.Decorator() { |
| // TODO: also check t.IDFunc. |
| case 0: |
| qid := typ.QID() |
| if qid[0] == t.IDBase && qid[1].IsNumType() { |
| for _, b := range typ.Bounds() { |
| if b == nil { |
| continue |
| } |
| if err := q.tcheckExpr(b, 0); err != nil { |
| return err |
| } |
| if b.ConstValue() == nil { |
| return fmt.Errorf("check: %q is not constant", b.Str(q.tm)) |
| } |
| } |
| break |
| } |
| if typ.Min() != nil || typ.Max() != nil { |
| // TODO: reject. You can only refine numeric types. |
| } |
| if qid[0] == t.IDBase { |
| if _, ok := builtInTypeMap[qid[1]]; ok || qid[1] == t.IDDagger1 || qid[1] == t.IDDagger2 { |
| break swtch |
| } |
| } |
| for _, s := range q.c.structs { |
| if s.QID() == qid { |
| break swtch |
| } |
| } |
| return fmt.Errorf("check: %q is not a type", typ.Str(q.tm)) |
| |
| case t.IDArray: |
| aLen := typ.ArrayLength() |
| if err := q.tcheckExpr(aLen, 0); err != nil { |
| return err |
| } |
| if aLen.ConstValue() == nil { |
| return fmt.Errorf("check: %q is not constant", aLen.Str(q.tm)) |
| } |
| fallthrough |
| |
| case t.IDNptr, t.IDPtr, t.IDSlice, t.IDTable: |
| if err := q.tcheckTypeExpr(typ.Inner(), depth); err != nil { |
| return err |
| } |
| |
| default: |
| return fmt.Errorf("check: %q is not a type", typ.Str(q.tm)) |
| } |
| typ.AsNode().SetMType(typeExprTypeExpr) |
| return nil |
| } |
| |
| func (q *checker) tcheckChoose(n *a.Choose) error { |
| qqid := q.astFunc.QQID() |
| fQQID := t.QQID{qqid[0], qqid[1], n.Name()} |
| f := q.c.funcs[fQQID] |
| if f == nil { |
| return fmt.Errorf("check: no function named %q", fQQID.Str(q.tm)) |
| } else if !f.Choosy() { |
| return fmt.Errorf("check: choose assignee %q is not choosy", fQQID[2].Str(q.tm)) |
| } |
| for _, o := range n.Args() { |
| o := o.AsExpr() |
| gQQID := t.QQID{qqid[0], qqid[1], o.Ident()} |
| g := q.c.funcs[gQQID] |
| if g == nil { |
| return fmt.Errorf("check: no function named %q", gQQID.Str(q.tm)) |
| } else if err := f.CheckChooseCompatible(g); err != nil { |
| return fmt.Errorf("check: incompatible choose functions %q and %q: %v", |
| fQQID.Str(q.tm), gQQID.Str(q.tm), err) |
| } |
| o.SetMBounds(bounds{one, one}) |
| o.SetMType(typeExprNonNullptr) |
| } |
| return nil |
| } |
| |
| var comparisonOps = [...]bool{ |
| t.IDXBinaryNotEq: true, |
| t.IDXBinaryLessThan: true, |
| t.IDXBinaryLessEq: true, |
| t.IDXBinaryEqEq: true, |
| t.IDXBinaryGreaterEq: true, |
| t.IDXBinaryGreaterThan: true, |
| } |