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 15//go:generate go run gen.go 16 17package check 18 19import ( 20 "errors" 21 "fmt" 22 "path" 23 24 "github.com/google/wuffs/lang/builtin" 25 "github.com/google/wuffs/lang/parse" 26 27 a "github.com/google/wuffs/lang/ast" 28 t "github.com/google/wuffs/lang/token" 29) 30 31type Error struct { 32 Err error 33 Filename string 34 Line uint32 35 OtherFilename string 36 OtherLine uint32 37 38 TMap *t.Map 39 Facts []*a.Expr 40} 41 42func (e *Error) Error() string { 43 s := "" 44 if e.OtherFilename != "" || e.OtherLine != 0 { 45 s = fmt.Sprintf("%s at %s:%d and %s:%d", 46 e.Err, e.Filename, e.Line, e.OtherFilename, e.OtherLine) 47 } else { 48 s = fmt.Sprintf("%s at %s:%d", e.Err, e.Filename, e.Line) 49 } 50 if e.TMap == nil { 51 return s 52 } 53 b := append([]byte(s), ". Facts:\n"...) 54 for _, f := range e.Facts { 55 b = append(b, '\t') 56 b = append(b, f.Str(e.TMap)...) 57 b = append(b, '\n') 58 } 59 return string(b) 60} 61 62func Check(tm *t.Map, files []*a.File, resolveUse func(usePath string) ([]byte, error)) (*Checker, error) { 63 for _, f := range files { 64 if f == nil { 65 return nil, errors.New("check: Check given a nil *ast.File") 66 } 67 } 68 69 if len(files) > 1 { 70 m := map[string]bool{} 71 for _, f := range files { 72 if m[f.Filename()] { 73 return nil, fmt.Errorf("check: Check given duplicate filename %q", f.Filename()) 74 } 75 m[f.Filename()] = true 76 } 77 } 78 79 rMap := reasonMap{} 80 for _, r := range reasons { 81 if id := tm.ByName(r.s); id != 0 { 82 rMap[id] = r.r 83 } 84 } 85 c := &Checker{ 86 tm: tm, 87 resolveUse: resolveUse, 88 reasonMap: rMap, 89 consts: map[t.QID]*a.Const{}, 90 funcs: map[t.QQID]*a.Func{}, 91 localVars: map[t.QQID]typeMap{}, 92 statuses: map[t.QID]*a.Status{}, 93 structs: map[t.QID]*a.Struct{}, 94 useBaseNames: map[t.ID]struct{}{}, 95 } 96 97 _, err := c.parseBuiltInFuncs(builtin.Funcs, false) 98 if err != nil { 99 return nil, err 100 } 101 c.builtInSliceFuncs, err = c.parseBuiltInFuncs(builtin.SliceFuncs, true) 102 if err != nil { 103 return nil, err 104 } 105 c.builtInTableFuncs, err = c.parseBuiltInFuncs(builtin.TableFuncs, true) 106 if err != nil { 107 return nil, err 108 } 109 110 for _, z := range builtin.Statuses { 111 id, err := tm.Insert(z) 112 if err != nil { 113 return nil, err 114 } 115 c.statuses[t.QID{t.IDBase, id}] = nil 116 } 117 118 for _, phase := range phases { 119 for _, f := range files { 120 if phase.kind == a.KInvalid { 121 if err := phase.check(c, nil); err != nil { 122 return nil, err 123 } 124 continue 125 } 126 for _, n := range f.TopLevelDecls() { 127 if n.Kind() != phase.kind { 128 continue 129 } 130 if err := phase.check(c, n); err != nil { 131 return nil, err 132 } 133 } 134 setPlaceholderMBoundsMType(f.AsNode()) 135 } 136 } 137 138 return c, nil 139} 140 141var phases = [...]struct { 142 kind a.Kind 143 check func(*Checker, *a.Node) error 144}{ 145 {a.KUse, (*Checker).checkUse}, 146 {a.KStatus, (*Checker).checkStatus}, 147 {a.KConst, (*Checker).checkConst}, 148 {a.KStruct, (*Checker).checkStructDecl}, 149 {a.KInvalid, (*Checker).checkStructCycles}, 150 {a.KStruct, (*Checker).checkStructFields}, 151 {a.KFunc, (*Checker).checkFuncSignature}, 152 {a.KFunc, (*Checker).checkFuncContract}, 153 {a.KFunc, (*Checker).checkFuncBody}, 154 {a.KStruct, (*Checker).checkFieldMethodCollisions}, 155 {a.KInvalid, (*Checker).checkAllTypeChecked}, 156 // TODO: check consts, funcs, structs and uses for name collisions. 157} 158 159type reason func(q *checker, n *a.Assert) error 160 161type reasonMap map[t.ID]reason 162 163type Checker struct { 164 tm *t.Map 165 resolveUse func(usePath string) ([]byte, error) 166 reasonMap reasonMap 167 168 consts map[t.QID]*a.Const 169 funcs map[t.QQID]*a.Func 170 localVars map[t.QQID]typeMap 171 statuses map[t.QID]*a.Status 172 structs map[t.QID]*a.Struct 173 174 // useBaseNames are the base names of packages referred to by `use 175 // "foo/bar"` lines. The keys are `bar`, not `"foo/bar"`. 176 useBaseNames map[t.ID]struct{} 177 178 builtInSliceFuncs map[t.QQID]*a.Func 179 builtInTableFuncs map[t.QQID]*a.Func 180 unsortedStructs []*a.Struct 181} 182 183func (c *Checker) checkUse(node *a.Node) error { 184 usePath := node.AsUse().Path() 185 filename, ok := t.Unescape(usePath.Str(c.tm)) 186 if !ok { 187 return fmt.Errorf("check: cannot resolve `use %s`", usePath.Str(c.tm)) 188 } 189 baseName, err := c.tm.Insert(path.Base(filename)) 190 if err != nil { 191 return fmt.Errorf("check: cannot resolve `use %s`: %v", usePath.Str(c.tm), err) 192 } 193 filename += ".wuffs" 194 if _, ok := c.useBaseNames[baseName]; ok { 195 return fmt.Errorf("check: duplicate `use \"etc\"` base name %q", baseName.Str(c.tm)) 196 } 197 198 if c.resolveUse == nil { 199 return fmt.Errorf("check: cannot resolve a use declaration") 200 } 201 src, err := c.resolveUse(filename) 202 if err != nil { 203 return err 204 } 205 tokens, _, err := t.Tokenize(c.tm, filename, src) 206 if err != nil { 207 return err 208 } 209 f, err := parse.Parse(c.tm, filename, tokens, &parse.Options{ 210 AllowDoubleUnderscoreNames: true, 211 }) 212 if err != nil { 213 return err 214 } 215 216 for _, n := range f.TopLevelDecls() { 217 if err := n.AsRaw().SetPackage(c.tm, baseName); err != nil { 218 return err 219 } 220 221 switch n.Kind() { 222 case a.KConst: 223 if err := c.checkConst(n); err != nil { 224 return err 225 } 226 case a.KFunc: 227 if err := c.checkFuncSignature(n); err != nil { 228 return err 229 } 230 case a.KStatus: 231 if err := c.checkStatus(n); err != nil { 232 return err 233 } 234 case a.KStruct: 235 if err := c.checkStructDecl(n); err != nil { 236 return err 237 } 238 } 239 } 240 c.useBaseNames[baseName] = struct{}{} 241 setPlaceholderMBoundsMType(node) 242 return nil 243} 244 245func (c *Checker) checkStatus(node *a.Node) error { 246 n := node.AsStatus() 247 qid := n.QID() 248 if other, ok := c.statuses[qid]; ok { 249 return &Error{ 250 Err: fmt.Errorf("check: duplicate status %s", qid.Str(c.tm)), 251 Filename: n.Filename(), 252 Line: n.Line(), 253 OtherFilename: other.Filename(), 254 OtherLine: other.Line(), 255 } 256 } 257 c.statuses[qid] = n 258 259 setPlaceholderMBoundsMType(n.AsNode()) 260 return nil 261} 262 263func (c *Checker) checkConst(node *a.Node) error { 264 n := node.AsConst() 265 qid := n.QID() 266 if other, ok := c.consts[qid]; ok { 267 return &Error{ 268 Err: fmt.Errorf("check: duplicate const %s", qid.Str(c.tm)), 269 Filename: n.Filename(), 270 Line: n.Line(), 271 OtherFilename: other.Filename(), 272 OtherLine: other.Line(), 273 } 274 } 275 c.consts[qid] = n 276 277 q := &checker{ 278 c: c, 279 tm: c.tm, 280 } 281 typ := n.XType() 282 if err := q.tcheckTypeExpr(typ, 0); err != nil { 283 return fmt.Errorf("%v in const %s", err, qid.Str(c.tm)) 284 } 285 if _, err := q.bcheckTypeExpr(typ); err != nil { 286 return fmt.Errorf("%v in const %s", err, qid.Str(c.tm)) 287 } 288 289 if err := q.tcheckExpr(n.Value(), 0); err != nil { 290 return fmt.Errorf("%v in const %s", err, qid.Str(c.tm)) 291 } 292 if _, err := q.bcheckExpr(n.Value(), 0); err != nil { 293 return fmt.Errorf("%v in const %s", err, qid.Str(c.tm)) 294 } 295 296 nLists := 0 297 for typ.IsArrayType() { 298 if nLists == a.MaxTypeExprDepth { 299 return fmt.Errorf("check: type expression recursion depth too large") 300 } 301 nLists++ 302 typ = typ.Inner() 303 } 304 if typ.Decorator() != 0 { 305 return fmt.Errorf("check: invalid const type %q for %s", n.XType().Str(c.tm), qid.Str(c.tm)) 306 } 307 308 nb := typ.Innermost().AsNode().MBounds() 309 if err := c.checkConstElement(n.Value(), nb, nLists); err != nil { 310 return fmt.Errorf("check: %v for %s", err, qid.Str(c.tm)) 311 } 312 setPlaceholderMBoundsMType(n.AsNode()) 313 return nil 314} 315 316func (c *Checker) checkConstElement(n *a.Expr, nb bounds, nLists int) error { 317 if nLists > 0 { 318 nLists-- 319 if n.Operator() != t.IDComma { 320 return fmt.Errorf("invalid const value %q", n.Str(c.tm)) 321 } 322 for _, o := range n.Args() { 323 if err := c.checkConstElement(o.AsExpr(), nb, nLists); err != nil { 324 return err 325 } 326 } 327 return nil 328 } 329 if cv := n.ConstValue(); cv == nil || cv.Cmp(nb[0]) < 0 || cv.Cmp(nb[1]) > 0 { 330 return fmt.Errorf("invalid const value %q not within %v", n.Str(c.tm), nb) 331 } 332 return nil 333} 334 335func (c *Checker) checkStructDecl(node *a.Node) error { 336 n := node.AsStruct() 337 qid := n.QID() 338 if other, ok := c.structs[qid]; ok { 339 return &Error{ 340 Err: fmt.Errorf("check: duplicate struct %s", qid.Str(c.tm)), 341 Filename: n.Filename(), 342 Line: n.Line(), 343 OtherFilename: other.Filename(), 344 OtherLine: other.Line(), 345 } 346 } 347 c.structs[qid] = n 348 c.unsortedStructs = append(c.unsortedStructs, n) 349 setPlaceholderMBoundsMType(n.AsNode()) 350 351 // A struct declaration implies a reset method. 352 in := a.NewStruct(0, n.Filename(), n.Line(), t.IDArgs, nil) 353 f := a.NewFunc(a.EffectImpure.AsFlags(), n.Filename(), n.Line(), qid[1], t.IDReset, in, nil, nil, nil) 354 if qid[0] != 0 { 355 f.AsNode().AsRaw().SetPackage(c.tm, qid[0]) 356 } 357 return c.checkFuncSignature(f.AsNode()) 358} 359 360func (c *Checker) checkStructCycles(_ *a.Node) error { 361 if _, ok := a.TopologicalSortStructs(c.unsortedStructs); !ok { 362 return fmt.Errorf("check: cyclical struct definitions") 363 } 364 return nil 365} 366 367func (c *Checker) checkStructFields(node *a.Node) error { 368 n := node.AsStruct() 369 if err := c.checkFields(n.Fields(), true, true); err != nil { 370 return &Error{ 371 Err: fmt.Errorf("%v in struct %s", err, n.QID().Str(c.tm)), 372 Filename: n.Filename(), 373 Line: n.Line(), 374 } 375 } 376 return nil 377} 378 379func (c *Checker) checkFields(fields []*a.Node, banPtrTypes bool, checkDefaultZeroValue bool) error { 380 if len(fields) == 0 { 381 return nil 382 } 383 384 q := &checker{ 385 c: c, 386 tm: c.tm, 387 } 388 fieldNames := map[t.ID]bool{} 389 for _, n := range fields { 390 f := n.AsField() 391 if _, ok := fieldNames[f.Name()]; ok { 392 return fmt.Errorf("check: duplicate field %q", f.Name().Str(c.tm)) 393 } 394 if err := checkTypeExpr(q, f.XType()); err != nil { 395 return fmt.Errorf("%v for field %q", err, f.Name().Str(c.tm)) 396 } 397 if banPtrTypes && f.XType().HasPointers() { 398 return fmt.Errorf("check: pointer-containing type %q not allowed for field %q", 399 f.XType().Str(c.tm), f.Name().Str(c.tm)) 400 } 401 402 if checkDefaultZeroValue { 403 fb := f.XType().Innermost().AsNode().MBounds() 404 if (zero.Cmp(fb[0]) < 0) || (zero.Cmp(fb[1]) > 0) { 405 return fmt.Errorf("check: default zero value is not within bounds %v for field %q", 406 fb, f.Name().Str(c.tm)) 407 } 408 } 409 410 fieldNames[f.Name()] = true 411 setPlaceholderMBoundsMType(f.AsNode()) 412 } 413 414 return nil 415} 416 417func checkTypeExpr(q *checker, n *a.TypeExpr) error { 418 if err := q.tcheckTypeExpr(n, 0); err != nil { 419 return err 420 } 421 if _, err := q.bcheckTypeExpr(n); err != nil { 422 return err 423 } 424 return nil 425} 426 427func (c *Checker) checkFuncSignature(node *a.Node) error { 428 n := node.AsFunc() 429 if err := c.checkFields(n.In().Fields(), false, false); err != nil { 430 return &Error{ 431 Err: fmt.Errorf("%v in in-params for func %s", err, n.QQID().Str(c.tm)), 432 Filename: n.Filename(), 433 Line: n.Line(), 434 } 435 } 436 setPlaceholderMBoundsMType(n.In().AsNode()) 437 if out := n.Out(); out != nil { 438 if n.Effect().Coroutine() && n.Receiver()[0] != t.IDBase { 439 return &Error{ 440 Err: fmt.Errorf("func %s has ? effect but non-empty return type", n.QQID().Str(c.tm)), 441 Filename: n.Filename(), 442 Line: n.Line(), 443 } 444 } 445 // TODO: does checking a TypeExpr need a q? 446 q := &checker{ 447 c: c, 448 tm: c.tm, 449 } 450 if err := checkTypeExpr(q, out); err != nil { 451 return &Error{ 452 Err: fmt.Errorf("%v in out-param for func %s", err, n.QQID().Str(c.tm)), 453 Filename: n.Filename(), 454 Line: n.Line(), 455 } 456 } 457 } 458 setPlaceholderMBoundsMType(n.AsNode()) 459 460 // TODO: check somewhere that, if n.Out() is non-nil (or we are 461 // suspendible), that we end with a return statement? Or is that an 462 // implicit "return out"? 463 464 qqid := n.QQID() 465 if other, ok := c.funcs[qqid]; ok { 466 return &Error{ 467 Err: fmt.Errorf("check: duplicate function %s", qqid.Str(c.tm)), 468 Filename: n.Filename(), 469 Line: n.Line(), 470 OtherFilename: other.Filename(), 471 OtherLine: other.Line(), 472 } 473 } 474 c.funcs[qqid] = n 475 476 if qqid[0] != 0 { 477 // No need to populate c.localVars for built-in or used-package funcs. 478 // In any case, the remaining type checking code in this function 479 // doesn't handle the base.† dagger type. 480 return nil 481 } 482 483 iQID := n.In().QID() 484 inTyp := a.NewTypeExpr(0, iQID[0], iQID[1], nil, nil, nil) 485 inTyp.AsNode().SetMBounds(bounds{zero, zero}) 486 inTyp.AsNode().SetMType(typeExprTypeExpr) 487 488 localVars := typeMap{ 489 t.IDArgs: inTyp, 490 t.IDCoroutineResumed: typeExprBool, 491 } 492 if qqid[1] != 0 { 493 if _, ok := c.structs[t.QID{qqid[0], qqid[1]}]; !ok { 494 return &Error{ 495 Err: fmt.Errorf("check: no receiver struct defined for function %s", qqid.Str(c.tm)), 496 Filename: n.Filename(), 497 Line: n.Line(), 498 } 499 } 500 501 sTyp := a.NewTypeExpr(0, qqid[0], qqid[1], nil, nil, nil) 502 sTyp.AsNode().SetMBounds(bounds{zero, zero}) 503 sTyp.AsNode().SetMType(typeExprTypeExpr) 504 505 pTyp := a.NewTypeExpr(t.IDPtr, 0, 0, nil, nil, sTyp) 506 pTyp.AsNode().SetMBounds(bounds{one, one}) 507 pTyp.AsNode().SetMType(typeExprTypeExpr) 508 509 localVars[t.IDThis] = pTyp 510 } 511 c.localVars[qqid] = localVars 512 return nil 513} 514 515func (c *Checker) checkFuncContract(node *a.Node) error { 516 n := node.AsFunc() 517 if len(n.Asserts()) == 0 { 518 return nil 519 } 520 q := &checker{ 521 c: c, 522 tm: c.tm, 523 } 524 for _, o := range n.Asserts() { 525 if err := q.tcheckAssert(o.AsAssert()); err != nil { 526 return err 527 } 528 } 529 return nil 530} 531 532func (c *Checker) checkFuncBody(node *a.Node) error { 533 n := node.AsFunc() 534 if len(n.Body()) == 0 { 535 return nil 536 } 537 538 q := &checker{ 539 c: c, 540 tm: c.tm, 541 reasonMap: c.reasonMap, 542 astFunc: c.funcs[n.QQID()], 543 localVars: c.localVars[n.QQID()], 544 } 545 546 // Fill in the TypeMap with all local variables. 547 if err := q.tcheckVars(n.Body()); err != nil { 548 return &Error{ 549 Err: err, 550 Filename: q.errFilename, 551 Line: q.errLine, 552 } 553 } 554 555 // TODO: check that variables are never used before they're initialized. 556 557 for _, o := range n.Body() { 558 if err := q.tcheckStatement(o); err != nil { 559 return &Error{ 560 Err: err, 561 Filename: q.errFilename, 562 Line: q.errLine, 563 } 564 } 565 } 566 567 if err := q.bcheckBlock(n.Body()); err != nil { 568 return &Error{ 569 Err: err, 570 Filename: q.errFilename, 571 Line: q.errLine, 572 TMap: c.tm, 573 Facts: q.facts, 574 } 575 } 576 577 return nil 578} 579 580func (c *Checker) checkFieldMethodCollisions(node *a.Node) error { 581 n := node.AsStruct() 582 for _, o := range n.Fields() { 583 nQID := n.QID() 584 qqid := t.QQID{nQID[0], nQID[1], o.AsField().Name()} 585 if _, ok := c.funcs[qqid]; ok { 586 return fmt.Errorf("check: struct %q has both a field and method named %q", 587 nQID.Str(c.tm), qqid[2].Str(c.tm)) 588 } 589 } 590 return nil 591} 592 593func (c *Checker) checkAllTypeChecked(node *a.Node) error { 594 for _, v := range c.consts { 595 if err := allTypeChecked(c.tm, v.AsNode()); err != nil { 596 return err 597 } 598 } 599 for _, v := range c.funcs { 600 if err := allTypeChecked(c.tm, v.AsNode()); err != nil { 601 return err 602 } 603 } 604 for _, v := range c.statuses { 605 if v == nil { 606 // Built-in statuses have a nil v node. 607 continue 608 } 609 if err := allTypeChecked(c.tm, v.AsNode()); err != nil { 610 return err 611 } 612 } 613 for _, v := range c.structs { 614 if err := allTypeChecked(c.tm, v.AsNode()); err != nil { 615 return err 616 } 617 } 618 return nil 619} 620 621func nodeDebugString(tm *t.Map, n *a.Node) string { 622 switch n.Kind() { 623 case a.KConst: 624 return fmt.Sprintf("%s node %q", n.Kind(), n.AsConst().QID().Str(tm)) 625 case a.KExpr: 626 return fmt.Sprintf("%s node %q", n.Kind(), n.AsExpr().Str(tm)) 627 case a.KFunc: 628 return fmt.Sprintf("%s node %q", n.Kind(), n.AsFunc().QQID().Str(tm)) 629 case a.KTypeExpr: 630 return fmt.Sprintf("%s node %q", n.Kind(), n.AsTypeExpr().Str(tm)) 631 case a.KStatus: 632 return fmt.Sprintf("%s node %q", n.Kind(), n.AsStatus().QID().Str(tm)) 633 case a.KStruct: 634 return fmt.Sprintf("%s node %q", n.Kind(), n.AsStruct().QID().Str(tm)) 635 } 636 return fmt.Sprintf("%s node", n.Kind()) 637} 638 639func allTypeChecked(tm *t.Map, n *a.Node) error { 640 return n.Walk(func(o *a.Node) error { 641 b := o.MBounds() 642 typ := o.MType() 643 if b[0] == nil || b[1] == nil || typ == nil { 644 return fmt.Errorf("check: internal error: unchecked %s", nodeDebugString(tm, o)) 645 } 646 647 typOK := false 648 switch o.Kind() { 649 case a.KExpr: 650 typOK = typ != typeExprPlaceholder && typ != typeExprTypeExpr 651 case a.KTypeExpr: 652 typOK = typ == typeExprTypeExpr 653 default: 654 typOK = typ == typeExprPlaceholder 655 } 656 if !typOK { 657 return fmt.Errorf("check: internal error: %s has incorrect type, %s", 658 nodeDebugString(tm, o), typ.Str(tm)) 659 } 660 661 if o.Kind() == a.KExpr { 662 o := o.AsExpr() 663 if typ.IsIdeal() && o.ConstValue() == nil { 664 return fmt.Errorf("check: internal error: expression %q has ideal number type "+ 665 "but no const value", o.Str(tm)) 666 } 667 } 668 return nil 669 }) 670} 671 672type checker struct { 673 c *Checker 674 tm *t.Map 675 reasonMap reasonMap 676 astFunc *a.Func 677 localVars typeMap 678 679 errFilename string 680 errLine uint32 681 682 jumpTargets []a.Loop 683 684 facts facts 685} 686