1// Copyright 2017 The Wuffs Authors. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// https://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package check 16 17import ( 18 "fmt" 19 "math/big" 20 21 a "github.com/google/wuffs/lang/ast" 22 t "github.com/google/wuffs/lang/token" 23) 24 25func (q *checker) tcheckVars(block []*a.Node) error { 26 for _, o := range block { 27 if o.Kind() != a.KVar { 28 break 29 } 30 31 q.errFilename, q.errLine = o.AsRaw().FilenameLine() 32 33 o := o.AsVar() 34 name := o.Name() 35 if _, ok := q.localVars[name]; ok { 36 return fmt.Errorf("check: duplicate var %q", name.Str(q.tm)) 37 } 38 if err := q.tcheckTypeExpr(o.XType(), 0); err != nil { 39 return err 40 } 41 q.localVars[name] = o.XType() 42 } 43 return nil 44} 45 46func (q *checker) tcheckStatement(n *a.Node) error { 47 q.errFilename, q.errLine = n.AsRaw().FilenameLine() 48 49 switch n.Kind() { 50 case a.KAssert: 51 if err := q.tcheckAssert(n.AsAssert()); err != nil { 52 return err 53 } 54 55 case a.KAssign: 56 if err := q.tcheckAssign(n.AsAssign()); err != nil { 57 return err 58 } 59 60 case a.KIf: 61 for n := n.AsIf(); n != nil; n = n.ElseIf() { 62 cond := n.Condition() 63 if cond.Effect() != 0 { 64 return fmt.Errorf("check: internal error: if-condition is not effect-free") 65 } 66 if err := q.tcheckExpr(cond, 0); err != nil { 67 return err 68 } 69 if !cond.MType().IsBool() { 70 return fmt.Errorf("check: if condition %q, of type %q, does not have a boolean type", 71 cond.Str(q.tm), cond.MType().Str(q.tm)) 72 } 73 for _, o := range n.BodyIfTrue() { 74 if err := q.tcheckStatement(o); err != nil { 75 return err 76 } 77 } 78 for _, o := range n.BodyIfFalse() { 79 if err := q.tcheckStatement(o); err != nil { 80 return err 81 } 82 } 83 } 84 for n := n.AsIf(); n != nil; n = n.ElseIf() { 85 setPlaceholderMBoundsMType(n.AsNode()) 86 } 87 return nil 88 89 case a.KIOBind: 90 n := n.AsIOBind() 91 if err := q.tcheckExpr(n.IO(), 0); err != nil { 92 return err 93 } 94 if typ := n.IO().MType(); !typ.IsIOType() { 95 return fmt.Errorf("check: %s expression %q, of type %q, does not have an I/O type", 96 n.Keyword().Str(q.tm), n.IO().Str(q.tm), typ.Str(q.tm)) 97 } 98 99 arg1Typ := typeExprSliceU8 100 if n.Keyword() == t.IDIOLimit { 101 arg1Typ = typeExprU64 102 } 103 if err := q.tcheckExpr(n.Arg1(), 0); err != nil { 104 return err 105 } 106 if typ := n.Arg1().MType(); !typ.EqIgnoringRefinements(arg1Typ) { 107 return fmt.Errorf("check: %s expression %q, of type %q, does not have type %q", 108 n.Keyword().Str(q.tm), n.Arg1().Str(q.tm), typ.Str(q.tm), arg1Typ.Str(q.tm)) 109 } 110 111 for _, o := range n.Body() { 112 // TODO: prohibit jumps (breaks, continues), rets (returns, yields) 113 // and retry-calling ? methods while inside an io_bind body. 114 if err := q.tcheckStatement(o); err != nil { 115 return err 116 } 117 } 118 119 case a.KIterate: 120 for n := n.AsIterate(); n != nil; n = n.ElseIterate() { 121 for _, o := range n.Assigns() { 122 if err := q.tcheckStatement(o); err != nil { 123 return err 124 } 125 o := o.AsAssign() 126 if typ := o.LHS().MType(); !typ.IsSliceType() { 127 return fmt.Errorf("check: iterate assignment to %q, of type %q, does not have slice type", 128 o.LHS().Str(q.tm), typ.Str(q.tm)) 129 } 130 } 131 // TODO: prohibit jumps (breaks, continues), rets (returns, yields) and 132 // retry-calling ? methods while inside an iterate body. 133 if err := q.tcheckLoop(n); err != nil { 134 return err 135 } 136 } 137 for n := n.AsIterate(); n != nil; n = n.ElseIterate() { 138 setPlaceholderMBoundsMType(n.AsNode()) 139 } 140 return nil 141 142 case a.KJump: 143 n := n.AsJump() 144 jumpTarget := (a.Loop)(nil) 145 if id := n.Label(); id != 0 { 146 for i := len(q.jumpTargets) - 1; i >= 0; i-- { 147 if w := q.jumpTargets[i]; w.Label() == id { 148 jumpTarget = w 149 break 150 } 151 } 152 } else if nj := len(q.jumpTargets); nj > 0 { 153 jumpTarget = q.jumpTargets[nj-1] 154 } 155 if jumpTarget == nil { 156 sepStr, labelStr := "", "" 157 if id := n.Label(); id != 0 { 158 sepStr, labelStr = ":", id.Str(q.tm) 159 } 160 return fmt.Errorf("no matching while/iterate statement for %s%s%s", 161 n.Keyword().Str(q.tm), sepStr, labelStr) 162 } 163 if n.Keyword() == t.IDBreak { 164 jumpTarget.SetHasBreak() 165 } else { 166 jumpTarget.SetHasContinue() 167 } 168 n.SetJumpTarget(jumpTarget) 169 170 case a.KRet: 171 n := n.AsRet() 172 lTyp := q.astFunc.Out() 173 if q.astFunc.Effect().Coroutine() { 174 lTyp = typeExprStatus 175 } else if lTyp == nil { 176 lTyp = typeExprEmptyStruct 177 } 178 value := n.Value() 179 if err := q.tcheckExpr(value, 0); err != nil { 180 return err 181 } 182 rTyp := value.MType() 183 if !(rTyp.IsIdeal() && lTyp.IsNumType()) && !lTyp.EqIgnoringRefinements(rTyp) { 184 return fmt.Errorf("check: cannot return %q (of type %q) as type %q", 185 value.Str(q.tm), rTyp.Str(q.tm), lTyp.Str(q.tm)) 186 } 187 188 case a.KVar: 189 n := n.AsVar() 190 if n.XType().AsNode().MType() == nil { 191 return fmt.Errorf("check: internal error: unchecked type expression %q", n.XType().Str(q.tm)) 192 } 193 // TODO: check that the default zero value is assignable to n.XType(). 194 195 case a.KWhile: 196 n := n.AsWhile() 197 cond := n.Condition() 198 if cond.Effect() != 0 { 199 return fmt.Errorf("check: internal error: while-condition is not effect-free") 200 } 201 if err := q.tcheckExpr(cond, 0); err != nil { 202 return err 203 } 204 if !cond.MType().IsBool() { 205 return fmt.Errorf("check: for-loop condition %q, of type %q, does not have a boolean type", 206 cond.Str(q.tm), cond.MType().Str(q.tm)) 207 } 208 if err := q.tcheckLoop(n); err != nil { 209 return err 210 } 211 212 default: 213 return fmt.Errorf("check: unrecognized ast.Kind (%s) for tcheckStatement", n.Kind()) 214 } 215 216 setPlaceholderMBoundsMType(n) 217 return nil 218} 219 220func (q *checker) tcheckAssert(n *a.Assert) error { 221 cond := n.Condition() 222 if err := q.tcheckExpr(cond, 0); err != nil { 223 return err 224 } 225 if !cond.MType().IsBool() { 226 return fmt.Errorf("check: assert condition %q, of type %q, does not have a boolean type", 227 cond.Str(q.tm), cond.MType().Str(q.tm)) 228 } 229 for _, o := range n.Args() { 230 if err := q.tcheckExpr(o.AsArg().Value(), 0); err != nil { 231 return err 232 } 233 setPlaceholderMBoundsMType(o) 234 } 235 // TODO: check that there are no side effects. 236 return nil 237} 238 239func (q *checker) tcheckEq(lID t.ID, lhs *a.Expr, lTyp *a.TypeExpr, rhs *a.Expr, rTyp *a.TypeExpr) error { 240 if (rTyp.IsIdeal() && lTyp.IsNumType()) || 241 (rTyp.EqIgnoringRefinements(lTyp)) || 242 (rTyp.IsNullptr() && lTyp.Decorator() == t.IDNptr) { 243 return nil 244 } 245 lStr := "???" 246 if lID != 0 { 247 lStr = lID.Str(q.tm) 248 } else if lhs != nil { 249 lStr = lhs.Str(q.tm) 250 } 251 return fmt.Errorf("check: cannot assign %q of type %q to %q of type %q", 252 rhs.Str(q.tm), rTyp.Str(q.tm), lStr, lTyp.Str(q.tm)) 253} 254 255func (q *checker) tcheckAssign(n *a.Assign) error { 256 rhs := n.RHS() 257 if err := q.tcheckExpr(rhs, 0); err != nil { 258 return err 259 } 260 lhs := n.LHS() 261 if lhs == nil { 262 return nil 263 } 264 if err := q.tcheckExpr(lhs, 0); err != nil { 265 return err 266 } 267 lTyp := lhs.MType() 268 rTyp := rhs.MType() 269 270 if op := n.Operator(); op == t.IDEq || op == t.IDEqQuestion { 271 return q.tcheckEq(0, lhs, lTyp, rhs, rTyp) 272 } 273 274 if !lTyp.IsNumType() { 275 return fmt.Errorf("check: assignment %q: assignee %q, of type %q, does not have numeric type", 276 n.Operator().Str(q.tm), lhs.Str(q.tm), lTyp.Str(q.tm)) 277 } 278 279 switch n.Operator() { 280 case t.IDShiftLEq, t.IDShiftREq, t.IDTildeModShiftLEq: 281 if !rTyp.IsNumTypeOrIdeal() { 282 return fmt.Errorf("check: assignment %q: shift %q, of type %q, does not have numeric type", 283 n.Operator().Str(q.tm), rhs.Str(q.tm), rTyp.Str(q.tm)) 284 } 285 return nil 286 case t.IDTildeModPlusEq, t.IDTildeModMinusEq, t.IDTildeSatPlusEq, t.IDTildeSatMinusEq: 287 if !lTyp.IsUnsignedInteger() { 288 return fmt.Errorf("check: assignment %q: %q, of type %q, does not have unsigned integer type", 289 n.Operator().Str(q.tm), lhs.Str(q.tm), lTyp.Str(q.tm)) 290 } 291 } 292 293 if !(rTyp.IsIdeal() && lTyp.IsNumType()) && !lTyp.EqIgnoringRefinements(rTyp) { 294 return fmt.Errorf("check: assignment %q: %q and %q, of types %q and %q, do not have compatible types", 295 n.Operator().Str(q.tm), 296 lhs.Str(q.tm), rhs.Str(q.tm), 297 lTyp.Str(q.tm), rTyp.Str(q.tm), 298 ) 299 } 300 return nil 301} 302 303func (q *checker) tcheckLoop(n a.Loop) error { 304 for _, o := range n.Asserts() { 305 if err := q.tcheckAssert(o.AsAssert()); err != nil { 306 return err 307 } 308 setPlaceholderMBoundsMType(o) 309 } 310 q.jumpTargets = append(q.jumpTargets, n) 311 defer func() { 312 q.jumpTargets = q.jumpTargets[:len(q.jumpTargets)-1] 313 }() 314 for _, o := range n.Body() { 315 if err := q.tcheckStatement(o); err != nil { 316 return err 317 } 318 } 319 return nil 320} 321 322func (q *checker) tcheckExpr(n *a.Expr, depth uint32) error { 323 if depth > a.MaxExprDepth { 324 return fmt.Errorf("check: expression recursion depth too large") 325 } 326 depth++ 327 328 if n.MType() != nil { 329 return nil 330 } 331 332 switch op := n.Operator(); { 333 case op.IsXUnaryOp(): 334 return q.tcheckExprUnaryOp(n, depth) 335 case op.IsXBinaryOp(): 336 return q.tcheckExprBinaryOp(n, depth) 337 case op.IsXAssociativeOp(): 338 return q.tcheckExprAssociativeOp(n, depth) 339 } 340 return q.tcheckExprOther(n, depth) 341} 342 343func (q *checker) tcheckExprOther(n *a.Expr, depth uint32) error { 344 switch n.Operator() { 345 case 0: 346 id1 := n.Ident() 347 if id1.IsNumLiteral(q.tm) { 348 z := big.NewInt(0) 349 s := id1.Str(q.tm) 350 if _, ok := z.SetString(s, 0); !ok { 351 return fmt.Errorf("check: invalid numeric literal %q", s) 352 } 353 n.SetConstValue(z) 354 n.SetMType(typeExprIdeal) 355 return nil 356 357 } else if id1.IsStrLiteral(q.tm) { 358 if _, ok := q.c.statuses[n.StatusQID()]; !ok { 359 return fmt.Errorf("check: unrecognized status %s", n.StatusQID().Str(q.tm)) 360 } 361 n.SetMType(typeExprStatus) 362 return nil 363 364 } else if id1.IsIdent(q.tm) { 365 if q.localVars != nil { 366 if typ, ok := q.localVars[id1]; ok { 367 n.SetMType(typ) 368 return nil 369 } 370 } 371 if c, ok := q.c.consts[t.QID{0, id1}]; ok { 372 // TODO: check somewhere that a global ident (i.e. a const) is 373 // not directly in the LHS of an assignment. 374 n.SetGlobalIdent() 375 n.SetMType(c.XType()) 376 return nil 377 } 378 // TODO: look for other (global) names: consts, funcs, statuses, 379 // structs from used packages. 380 return fmt.Errorf("check: unrecognized identifier %q", id1.Str(q.tm)) 381 } 382 383 switch id1 { 384 case t.IDFalse: 385 n.SetConstValue(zero) 386 n.SetMType(typeExprBool) 387 return nil 388 389 case t.IDTrue: 390 n.SetConstValue(one) 391 n.SetMType(typeExprBool) 392 return nil 393 394 case t.IDNothing: 395 n.SetConstValue(zero) 396 n.SetMType(typeExprEmptyStruct) 397 return nil 398 399 case t.IDNullptr: 400 n.SetConstValue(zero) 401 n.SetMType(typeExprNullptr) 402 return nil 403 404 case t.IDOk: 405 n.SetConstValue(zero) 406 n.SetMType(typeExprStatus) 407 return nil 408 } 409 410 case t.IDOpenParen: 411 // n is a function call. 412 return q.tcheckExprCall(n, depth) 413 414 case t.IDOpenBracket: 415 // n is an index. 416 lhs := n.LHS().AsExpr() 417 if err := q.tcheckExpr(lhs, depth); err != nil { 418 return err 419 } 420 rhs := n.RHS().AsExpr() 421 if err := q.tcheckExpr(rhs, depth); err != nil { 422 return err 423 } 424 lTyp := lhs.MType() 425 if key := lTyp.Decorator(); key != t.IDArray && key != t.IDSlice { 426 return fmt.Errorf("check: %s is an index expression but %s has type %s, not an array or slice type", 427 n.Str(q.tm), lhs.Str(q.tm), lTyp.Str(q.tm)) 428 } 429 rTyp := rhs.MType() 430 if !rTyp.IsNumTypeOrIdeal() { 431 return fmt.Errorf("check: %s is an index expression but %s has type %s, not a numeric type", 432 n.Str(q.tm), rhs.Str(q.tm), rTyp.Str(q.tm)) 433 } 434 n.SetMType(lTyp.Inner()) 435 return nil 436 437 case t.IDColon: 438 // n is a slice. 439 // TODO: require that the i and j in a[i:j] are *unsigned* (or 440 // non-negative constants)? 441 if mhs := n.MHS().AsExpr(); mhs != nil { 442 if err := q.tcheckExpr(mhs, depth); err != nil { 443 return err 444 } 445 mTyp := mhs.MType() 446 if !mTyp.IsNumTypeOrIdeal() { 447 return fmt.Errorf("check: %s is a slice expression but %s has type %s, not a numeric type", 448 n.Str(q.tm), mhs.Str(q.tm), mTyp.Str(q.tm)) 449 } 450 } 451 if rhs := n.RHS().AsExpr(); rhs != nil { 452 if err := q.tcheckExpr(rhs, depth); err != nil { 453 return err 454 } 455 rTyp := rhs.MType() 456 if !rTyp.IsNumTypeOrIdeal() { 457 return fmt.Errorf("check: %s is a slice expression but %s has type %s, not a numeric type", 458 n.Str(q.tm), rhs.Str(q.tm), rTyp.Str(q.tm)) 459 } 460 } 461 lhs := n.LHS().AsExpr() 462 if err := q.tcheckExpr(lhs, depth); err != nil { 463 return err 464 } 465 lTyp := lhs.MType() 466 switch lTyp.Decorator() { 467 default: 468 return fmt.Errorf("check: %s is a slice expression but %s has type %s, not an array or slice type", 469 n.Str(q.tm), lhs.Str(q.tm), lTyp.Str(q.tm)) 470 case t.IDArray: 471 n.SetMType(a.NewTypeExpr(t.IDSlice, 0, 0, nil, nil, lTyp.Inner())) 472 case t.IDSlice: 473 n.SetMType(lTyp) 474 } 475 return nil 476 477 case t.IDDot: 478 return q.tcheckDot(n, depth) 479 480 case t.IDComma: 481 for _, o := range n.Args() { 482 o := o.AsExpr() 483 if err := q.tcheckExpr(o, depth); err != nil { 484 return err 485 } 486 } 487 n.SetMType(typeExprList) 488 return nil 489 } 490 491 return fmt.Errorf("check: unrecognized token (0x%X) in expression %q for tcheckExprOther", 492 n.Operator(), n.Str(q.tm)) 493} 494 495func (q *checker) tcheckExprCall(n *a.Expr, depth uint32) error { 496 lhs := n.LHS().AsExpr() 497 if err := q.tcheckExpr(lhs, depth); err != nil { 498 return err 499 } 500 f, err := q.c.resolveFunc(lhs.MType()) 501 if err != nil { 502 return err 503 } 504 if ne, fe := n.Effect(), f.Effect(); ne != fe { 505 return fmt.Errorf("check: %q has effect %q but %q has effect %q", 506 n.Str(q.tm), ne, f.QQID().Str(q.tm), fe) 507 } 508 509 genericType1 := (*a.TypeExpr)(nil) 510 genericType2 := (*a.TypeExpr)(nil) 511 switch f.Receiver() { 512 case t.QID{t.IDBase, t.IDDagger1}: 513 genericType1 = lhs.MType().Receiver() 514 case t.QID{t.IDBase, t.IDDagger2}: 515 genericType2 = lhs.MType().Receiver() 516 if genericType2.Decorator() != t.IDTable { 517 return fmt.Errorf("check: internal error: %q is not a generic table", genericType2.Str(q.tm)) 518 } 519 genericType1 = a.NewTypeExpr(t.IDSlice, 0, 0, nil, nil, genericType2.Inner()) 520 } 521 522 // Check that the func's in type matches the arguments. 523 inFields := f.In().Fields() 524 if len(inFields) != len(n.Args()) { 525 return fmt.Errorf("check: %q has %d arguments but %d were given", 526 lhs.MType().Str(q.tm), len(inFields), len(n.Args())) 527 } 528 for i, o := range n.Args() { 529 o := o.AsArg() 530 if err := q.tcheckExpr(o.Value(), depth); err != nil { 531 return err 532 } 533 534 inField := inFields[i].AsField() 535 if o.Name() != inField.Name() { 536 return fmt.Errorf("check: argument name: got %q, want %q", o.Name().Str(q.tm), inField.Name().Str(q.tm)) 537 } 538 539 inFieldTyp := inField.XType() 540 if genericType1 != nil && inFieldTyp.Eq(typeExprGeneric1) { 541 inFieldTyp = genericType1 542 } else if genericType2 != nil && inFieldTyp.Eq(typeExprGeneric2) { 543 inFieldTyp = genericType2 544 } 545 if err := q.tcheckEq(inField.Name(), nil, inFieldTyp, o.Value(), o.Value().MType()); err != nil { 546 return err 547 } 548 setPlaceholderMBoundsMType(o.AsNode()) 549 } 550 551 oTyp := f.Out() 552 if oTyp == nil { 553 if n.Effect().Coroutine() { 554 n.SetMType(typeExprStatus) 555 } else { 556 n.SetMType(typeExprEmptyStruct) 557 } 558 } else if genericType1 != nil && oTyp.Eq(typeExprGeneric1) { 559 n.SetMType(genericType1) 560 } else if genericType2 != nil && oTyp.Eq(typeExprGeneric2) { 561 n.SetMType(genericType2) 562 } else { 563 n.SetMType(oTyp) 564 } 565 return nil 566} 567 568func (q *checker) tcheckDot(n *a.Expr, depth uint32) error { 569 lhs := n.LHS().AsExpr() 570 if err := q.tcheckExpr(lhs, depth); err != nil { 571 return err 572 } 573 lTyp := lhs.MType().Pointee() 574 lQID := lTyp.QID() 575 qqid := t.QQID{lQID[0], lQID[1], n.Ident()} 576 577 if lTyp.IsSliceType() { 578 qqid[0] = t.IDBase 579 qqid[1] = t.IDDagger1 580 if q.c.builtInSliceFuncs[qqid] == nil { 581 return fmt.Errorf("check: no slice method %q", n.Ident().Str(q.tm)) 582 } 583 n.SetMType(a.NewTypeExpr(t.IDFunc, 0, n.Ident(), lTyp.AsNode(), nil, nil)) 584 return nil 585 586 } else if lTyp.IsTableType() { 587 qqid[0] = t.IDBase 588 qqid[1] = t.IDDagger2 589 if q.c.builtInTableFuncs[qqid] == nil { 590 return fmt.Errorf("check: no table method %q", n.Ident().Str(q.tm)) 591 } 592 n.SetMType(a.NewTypeExpr(t.IDFunc, 0, n.Ident(), lTyp.AsNode(), nil, nil)) 593 return nil 594 595 } else if lTyp.Decorator() != 0 { 596 return fmt.Errorf("check: invalid type %q for dot-expression LHS %q", lTyp.Str(q.tm), lhs.Str(q.tm)) 597 } 598 599 if f := q.c.funcs[qqid]; f != nil { 600 n.SetMType(a.NewTypeExpr(t.IDFunc, 0, n.Ident(), lTyp.AsNode(), nil, nil)) 601 return nil 602 } 603 604 s := (*a.Struct)(nil) 605 if q.astFunc != nil && lQID[0] == 0 && lQID[1] == t.IDArgs { 606 s = q.astFunc.In() 607 } 608 if s == nil { 609 s = q.c.structs[lQID] 610 if s == nil { 611 if lQID[0] == t.IDBase { 612 return fmt.Errorf("check: no built-in function %q found", qqid.Str(q.tm)) 613 } 614 return fmt.Errorf("check: no struct type %q found for expression %q", lTyp.Str(q.tm), lhs.Str(q.tm)) 615 } 616 } 617 618 for _, field := range s.Fields() { 619 f := field.AsField() 620 if f.Name() == n.Ident() { 621 n.SetMType(f.XType()) 622 return nil 623 } 624 } 625 626 return fmt.Errorf("check: no field or method named %q found in type %q for expression %q", 627 n.Ident().Str(q.tm), lTyp.Str(q.tm), n.Str(q.tm)) 628} 629 630func (q *checker) tcheckExprUnaryOp(n *a.Expr, depth uint32) error { 631 rhs := n.RHS().AsExpr() 632 if err := q.tcheckExpr(rhs, depth); err != nil { 633 return err 634 } 635 rTyp := rhs.MType() 636 637 switch n.Operator() { 638 case t.IDXUnaryPlus, t.IDXUnaryMinus: 639 if !rTyp.IsNumTypeOrIdeal() { 640 return fmt.Errorf("check: unary %q: %q, of type %q, does not have a numeric type", 641 n.Operator().AmbiguousForm().Str(q.tm), rhs.Str(q.tm), rTyp.Str(q.tm)) 642 } 643 if cv := rhs.ConstValue(); cv != nil { 644 if n.Operator() == t.IDXUnaryMinus { 645 cv = neg(cv) 646 } 647 n.SetConstValue(cv) 648 } 649 n.SetMType(rTyp.Unrefined()) 650 return nil 651 652 case t.IDXUnaryNot: 653 if !rTyp.IsBool() { 654 return fmt.Errorf("check: unary %q: %q, of type %q, does not have a boolean type", 655 n.Operator().AmbiguousForm().Str(q.tm), rhs.Str(q.tm), rTyp.Str(q.tm)) 656 } 657 if cv := rhs.ConstValue(); cv != nil { 658 n.SetConstValue(btoi(cv.Sign() == 0)) 659 } 660 n.SetMType(typeExprBool) 661 return nil 662 663 case t.IDXUnaryRef: 664 // TODO. 665 666 case t.IDXUnaryDeref: 667 if rTyp.Decorator() != t.IDPtr { // TODO: t.IDNptr? 668 return fmt.Errorf("check: %q is a dereference of a non-pointer type %q", 669 n.Str(q.tm), rTyp.Str(q.tm)) 670 } 671 n.SetMType(rTyp.Inner()) 672 return nil 673 } 674 return fmt.Errorf("check: unrecognized token (0x%X) for tcheckExprUnaryOp", n.Operator()) 675} 676 677func (q *checker) tcheckExprBinaryOp(n *a.Expr, depth uint32) error { 678 lhs := n.LHS().AsExpr() 679 if err := q.tcheckExpr(lhs, depth); err != nil { 680 return err 681 } 682 lTyp := lhs.MType() 683 op := n.Operator() 684 if op == t.IDXBinaryAs { 685 rhs := n.RHS().AsTypeExpr() 686 if err := q.tcheckTypeExpr(rhs, 0); err != nil { 687 return err 688 } 689 if lTyp.IsNumTypeOrIdeal() && rhs.IsNumType() { 690 n.SetMType(rhs) 691 return nil 692 } 693 return fmt.Errorf("check: cannot convert expression %q, of type %q, as type %q", 694 lhs.Str(q.tm), lTyp.Str(q.tm), rhs.Str(q.tm)) 695 } 696 rhs := n.RHS().AsExpr() 697 if err := q.tcheckExpr(rhs, depth); err != nil { 698 return err 699 } 700 rTyp := rhs.MType() 701 702 pointerComparison := false 703 switch op { 704 case t.IDXBinaryAnd, t.IDXBinaryOr: 705 if !lTyp.IsBool() { 706 return fmt.Errorf("check: binary %q: %q, of type %q, does not have a boolean type", 707 op.AmbiguousForm().Str(q.tm), lhs.Str(q.tm), lTyp.Str(q.tm)) 708 } 709 if !rTyp.IsBool() { 710 return fmt.Errorf("check: binary %q: %q, of type %q, does not have a boolean type", 711 op.AmbiguousForm().Str(q.tm), rhs.Str(q.tm), rTyp.Str(q.tm)) 712 } 713 default: 714 bad := (*a.Expr)(nil) 715 if !lTyp.IsNumTypeOrIdeal() { 716 bad = lhs 717 } else if !rTyp.IsNumTypeOrIdeal() { 718 bad = rhs 719 } 720 if op == t.IDXBinaryNotEq || op == t.IDXBinaryEqEq { 721 if lTyp.Eq(typeExprStatus) && rTyp.Eq(typeExprStatus) { 722 break 723 } 724 lNullptr := lTyp.Eq(typeExprNullptr) 725 rNullptr := rTyp.Eq(typeExprNullptr) 726 if (lNullptr && rNullptr) || 727 (lNullptr && rTyp.IsPointerType()) || 728 (rNullptr && lTyp.IsPointerType()) { 729 pointerComparison = true 730 break 731 } 732 } 733 if bad != nil { 734 return fmt.Errorf("check: binary %q: %q, of type %q, does not have a numeric type", 735 op.AmbiguousForm().Str(q.tm), bad.Str(q.tm), bad.MType().Str(q.tm)) 736 } 737 } 738 739 switch op { 740 default: 741 if pointerComparison { 742 break 743 } 744 if !lTyp.EqIgnoringRefinements(rTyp) && !lTyp.IsIdeal() && !rTyp.IsIdeal() { 745 return fmt.Errorf("check: binary %q: %q and %q, of types %q and %q, do not have compatible types", 746 op.AmbiguousForm().Str(q.tm), 747 lhs.Str(q.tm), rhs.Str(q.tm), 748 lTyp.Str(q.tm), rTyp.Str(q.tm), 749 ) 750 } 751 case t.IDXBinaryShiftL, t.IDXBinaryShiftR, t.IDXBinaryTildeModShiftL: 752 if lTyp.IsIdeal() && !rTyp.IsIdeal() { 753 return fmt.Errorf("check: binary %q: %q and %q, of types %q and %q; "+ 754 "cannot shift an ideal number by a non-ideal number", 755 op.AmbiguousForm().Str(q.tm), 756 lhs.Str(q.tm), rhs.Str(q.tm), 757 lTyp.Str(q.tm), rTyp.Str(q.tm), 758 ) 759 } 760 } 761 762 switch op { 763 case t.IDXBinaryTildeModPlus, t.IDXBinaryTildeModMinus, 764 t.IDXBinaryTildeSatPlus, t.IDXBinaryTildeSatMinus: 765 typ := lTyp 766 if typ.IsIdeal() { 767 typ = rTyp 768 if typ.IsIdeal() { 769 return fmt.Errorf("check: binary %q: %q and %q, of types %q and %q, do not have non-ideal types", 770 op.AmbiguousForm().Str(q.tm), 771 lhs.Str(q.tm), rhs.Str(q.tm), 772 lTyp.Str(q.tm), rTyp.Str(q.tm), 773 ) 774 } 775 } 776 if !typ.IsUnsignedInteger() { 777 return fmt.Errorf("check: binary %q: %q and %q, of types %q and %q, do not have unsigned integer types", 778 op.AmbiguousForm().Str(q.tm), 779 lhs.Str(q.tm), rhs.Str(q.tm), 780 lTyp.Str(q.tm), rTyp.Str(q.tm), 781 ) 782 } 783 } 784 785 if lcv, rcv := lhs.ConstValue(), rhs.ConstValue(); lcv != nil && rcv != nil { 786 ncv, err := evalConstValueBinaryOp(q.tm, n, lcv, rcv) 787 if err != nil { 788 return err 789 } 790 n.SetConstValue(ncv) 791 } 792 793 if (op < t.ID(len(comparisonOps))) && comparisonOps[op] { 794 n.SetMType(typeExprBool) 795 } else if !lTyp.IsIdeal() { 796 n.SetMType(lTyp.Unrefined()) 797 } else { 798 n.SetMType(rTyp.Unrefined()) 799 } 800 801 return nil 802} 803 804func evalConstValueBinaryOp(tm *t.Map, n *a.Expr, l *big.Int, r *big.Int) (*big.Int, error) { 805 switch n.Operator() { 806 case t.IDXBinaryPlus: 807 return big.NewInt(0).Add(l, r), nil 808 case t.IDXBinaryMinus: 809 return big.NewInt(0).Sub(l, r), nil 810 case t.IDXBinaryStar: 811 return big.NewInt(0).Mul(l, r), nil 812 case t.IDXBinarySlash: 813 if r.Sign() == 0 { 814 return nil, fmt.Errorf("check: division by zero in const expression %q", n.Str(tm)) 815 } 816 // TODO: decide on Euclidean division vs other definitions. See "go doc 817 // math/big int.divmod" for details. 818 return big.NewInt(0).Div(l, r), nil 819 case t.IDXBinaryShiftL: 820 if r.Sign() < 0 || r.Cmp(ffff) > 0 { 821 return nil, fmt.Errorf("check: shift %q out of range in const expression %q", 822 n.RHS().AsExpr().Str(tm), n.Str(tm)) 823 } 824 return big.NewInt(0).Lsh(l, uint(r.Uint64())), nil 825 case t.IDXBinaryShiftR: 826 if r.Sign() < 0 || r.Cmp(ffff) > 0 { 827 return nil, fmt.Errorf("check: shift %q out of range in const expression %q", 828 n.RHS().AsExpr().Str(tm), n.Str(tm)) 829 } 830 return big.NewInt(0).Rsh(l, uint(r.Uint64())), nil 831 case t.IDXBinaryAmp: 832 return big.NewInt(0).And(l, r), nil 833 case t.IDXBinaryPipe: 834 return big.NewInt(0).Or(l, r), nil 835 case t.IDXBinaryHat: 836 return big.NewInt(0).Xor(l, r), nil 837 case t.IDXBinaryPercent: 838 if r.Sign() == 0 { 839 return nil, fmt.Errorf("check: division by zero in const expression %q", n.Str(tm)) 840 } 841 return big.NewInt(0).Mod(l, r), nil 842 case t.IDXBinaryNotEq: 843 return btoi(l.Cmp(r) != 0), nil 844 case t.IDXBinaryLessThan: 845 return btoi(l.Cmp(r) < 0), nil 846 case t.IDXBinaryLessEq: 847 return btoi(l.Cmp(r) <= 0), nil 848 case t.IDXBinaryEqEq: 849 return btoi(l.Cmp(r) == 0), nil 850 case t.IDXBinaryGreaterEq: 851 return btoi(l.Cmp(r) >= 0), nil 852 case t.IDXBinaryGreaterThan: 853 return btoi(l.Cmp(r) > 0), nil 854 case t.IDXBinaryAnd: 855 return btoi((l.Sign() != 0) && (r.Sign() != 0)), nil 856 case t.IDXBinaryOr: 857 return btoi((l.Sign() != 0) || (r.Sign() != 0)), nil 858 case t.IDXBinaryTildeModShiftL, 859 t.IDXBinaryTildeModPlus, t.IDXBinaryTildeModMinus, 860 t.IDXBinaryTildeSatPlus, t.IDXBinaryTildeSatMinus: 861 return nil, fmt.Errorf("check: cannot apply tilde-operators to ideal numbers") 862 } 863 return nil, fmt.Errorf("check: unrecognized token (0x%02X) for evalConstValueBinaryOp", n.Operator()) 864} 865 866func (q *checker) tcheckExprAssociativeOp(n *a.Expr, depth uint32) error { 867 switch n.Operator() { 868 case t.IDXAssociativePlus, t.IDXAssociativeStar, 869 t.IDXAssociativeAmp, t.IDXAssociativePipe, t.IDXAssociativeHat: 870 871 expr, typ := (*a.Expr)(nil), (*a.TypeExpr)(nil) 872 for _, o := range n.Args() { 873 o := o.AsExpr() 874 if err := q.tcheckExpr(o, depth); err != nil { 875 return err 876 } 877 oTyp := o.MType() 878 if oTyp.IsIdeal() { 879 continue 880 } 881 if !oTyp.IsNumType() { 882 return fmt.Errorf("check: associative %q: %q, of type %q, does not have a numeric type", 883 n.Operator().AmbiguousForm().Str(q.tm), o.Str(q.tm), oTyp.Str(q.tm)) 884 } 885 if typ == nil { 886 expr, typ = o, oTyp.Unrefined() 887 continue 888 } 889 if !typ.EqIgnoringRefinements(oTyp) { 890 return fmt.Errorf("check: associative %q: %q and %q, of types %q and %q, "+ 891 "do not have compatible types", 892 n.Operator().AmbiguousForm().Str(q.tm), 893 expr.Str(q.tm), o.Str(q.tm), 894 expr.MType().Str(q.tm), o.MType().Str(q.tm)) 895 } 896 } 897 if typ == nil { 898 typ = typeExprIdeal 899 } 900 n.SetMType(typ) 901 return nil 902 903 case t.IDXAssociativeAnd, t.IDXAssociativeOr: 904 for _, o := range n.Args() { 905 o := o.AsExpr() 906 if err := q.tcheckExpr(o, depth); err != nil { 907 return err 908 } 909 if !o.MType().IsBool() { 910 return fmt.Errorf("check: associative %q: %q, of type %q, does not have a boolean type", 911 n.Operator().AmbiguousForm().Str(q.tm), o.Str(q.tm), o.MType().Str(q.tm)) 912 } 913 } 914 n.SetMType(typeExprBool) 915 return nil 916 } 917 918 return fmt.Errorf("check: unrecognized token (0x%X) for tcheckExprAssociativeOp", n.Operator()) 919} 920 921func (q *checker) tcheckTypeExpr(typ *a.TypeExpr, depth uint32) error { 922 if depth > a.MaxTypeExprDepth { 923 return fmt.Errorf("check: type expression recursion depth too large") 924 } 925 depth++ 926 927swtch: 928 switch typ.Decorator() { 929 // TODO: also check t.IDFunc. 930 case 0: 931 qid := typ.QID() 932 if qid[0] == t.IDBase && qid[1].IsNumType() { 933 for _, b := range typ.Bounds() { 934 if b == nil { 935 continue 936 } 937 if err := q.tcheckExpr(b, 0); err != nil { 938 return err 939 } 940 if q.exprConstValue(b) == nil { 941 return fmt.Errorf("check: %q is not constant", b.Str(q.tm)) 942 } 943 } 944 break 945 } 946 if typ.Min() != nil || typ.Max() != nil { 947 // TODO: reject. You can only refine numeric types. 948 } 949 if qid[0] == t.IDBase { 950 if _, ok := builtInTypeMap[qid[1]]; ok || qid[1] == t.IDDagger1 || qid[1] == t.IDDagger2 { 951 break swtch 952 } 953 } 954 for _, s := range q.c.structs { 955 if s.QID() == qid { 956 break swtch 957 } 958 } 959 return fmt.Errorf("check: %q is not a type", typ.Str(q.tm)) 960 961 case t.IDArray: 962 aLen := typ.ArrayLength() 963 if err := q.tcheckExpr(aLen, 0); err != nil { 964 return err 965 } 966 if q.exprConstValue(aLen) == nil { 967 return fmt.Errorf("check: %q is not constant", aLen.Str(q.tm)) 968 } 969 fallthrough 970 971 case t.IDNptr, t.IDPtr, t.IDSlice, t.IDTable: 972 if err := q.tcheckTypeExpr(typ.Inner(), depth); err != nil { 973 return err 974 } 975 976 default: 977 return fmt.Errorf("check: %q is not a type", typ.Str(q.tm)) 978 } 979 typ.AsNode().SetMType(typeExprTypeExpr) 980 return nil 981} 982 983func (q *checker) exprConstValue(n *a.Expr) *big.Int { 984 if cv := n.ConstValue(); cv != nil { 985 return cv 986 } 987 if n.Operator() == 0 { 988 if c, ok := q.c.consts[t.QID{0, n.Ident()}]; ok { 989 if cv := c.Value().ConstValue(); cv != nil { 990 n.SetConstValue(cv) 991 return cv 992 } 993 } 994 } 995 return nil 996} 997 998var comparisonOps = [...]bool{ 999 t.IDXBinaryNotEq: true, 1000 t.IDXBinaryLessThan: true, 1001 t.IDXBinaryLessEq: true, 1002 t.IDXBinaryEqEq: true, 1003 t.IDXBinaryGreaterEq: true, 1004 t.IDXBinaryGreaterThan: true, 1005} 1006