resolve: report likely identifier misspellings (#138)

Move spell.go to internal/spell package to enable re-use.

Unfortunately the resolver API provides no way for it to enumerate
predeclared and universe, so these candidates are missing.

Also, change var ErrNoSuchField to type NoSuchAttrError so that
HasAttrs.Attr and HasSetField.SetField implementations can return
their own message and still benefit from spell checking.

8 files changed, 140 insertions, 53 deletions

diff --git a/starlark/spell.go b/internal/spell/spell.go
index ce70c1a..7739fab 100644
--- a/starlark/spell.go
+++ b/internal/spell/spell.go
@@ -1,16 +1,16 @@
-package starlark
-
-// This file defines a simple spell checker for use in attribute errors
-// ("no such field .foo; did you mean .food?")
+// Package spell file defines a simple spelling checker for use in attribute errors
+// such as "no such field .foo; did you mean .food?".
+package spell
 
 import (
 	"strings"
 	"unicode"
 )
 
-// nearest returns the element of candidates
-// nearest to x using the Levenshtein metric.
-func nearest(x string, candidates []string) string {
+// Nearest returns the element of candidates
+// nearest to x using the Levenshtein metric,
+// or "" if none were promising.
+func Nearest(x string, candidates []string) string {
 	// Ignore underscores and case when matching.
 	fold := func(s string) string {
 		return strings.Map(func(r rune) rune {
@@ -62,6 +62,10 @@ func levenshtein(x, y string, max int) int {
 		return len(y)
 	}
 
+	if d := abs(len(x) - len(y)); d > max {
+		return d // excessive length divergence
+	}
+
 	row := make([]int, len(y)+1)
 	for i := range row {
 		row[i] = i
@@ -86,6 +90,14 @@ func levenshtein(x, y string, max int) int {
 	return row[len(y)]
 }
 
+func b2i(b bool) int {
+	if b {
+		return 1
+	} else {
+		return 0
+	}
+}
+
 func min(x, y int) int {
 	if x < y {
 		return x
@@ -93,3 +105,11 @@ func min(x, y int) int {
 		return y
 	}
 }
+
+func abs(x int) int {
+	if x >= 0 {
+		return x
+	} else {
+		return -x
+	}
+}
diff --git a/resolve/resolve.go b/resolve/resolve.go
index 60712c0..0bc9ac0 100644
--- a/resolve/resolve.go
+++ b/resolve/resolve.go
@@ -77,8 +77,10 @@ package resolve // import "go.starlark.net/resolve"
 import (
 	"fmt"
 	"log"
+	"sort"
 	"strings"
 
+	"go.starlark.net/internal/spell"
 	"go.starlark.net/syntax"
 )
 
@@ -334,6 +336,8 @@ func (r *resolver) bind(id *syntax.Ident) bool {
 }
 
 func (r *resolver) use(id *syntax.Ident) {
+	use := use{id, r.env}
+
 	// The spec says that if there is a global binding of a name
 	// then all references to that name in that block refer to the
 	// global, even if the use precedes the def---just as for locals.
@@ -365,15 +369,18 @@ func (r *resolver) use(id *syntax.Ident) {
 	// AllowGlobalReassign flag, which is loosely related and also
 	// required for Bazel.
 	if AllowGlobalReassign && r.env.isModule() {
-		r.useGlobal(id)
+		r.useGlobal(use)
 		return
 	}
 
 	b := r.container()
-	b.uses = append(b.uses, use{id, r.env})
+	b.uses = append(b.uses, use)
 }
 
-func (r *resolver) useGlobal(id *syntax.Ident) binding {
+// useGlobals resolves use.id as a reference to a global.
+// The use.env field captures the original environment for error reporting.
+func (r *resolver) useGlobal(use use) binding {
+	id := use.id
 	var scope Scope
 	if prev, ok := r.globals[id.Name]; ok {
 		scope = Global // use of global declared by module
@@ -390,14 +397,40 @@ func (r *resolver) useGlobal(id *syntax.Ident) binding {
 		}
 	} else {
 		scope = Undefined
-		// TODO(adonovan): implement spell check. Ideally we
-		// need a way to enumerate universal and predeclared.
-		r.errorf(id.NamePos, "undefined: %s", id.Name)
+		var hint string
+		if n := r.spellcheck(use); n != "" {
+			hint = fmt.Sprintf(" (did you mean %s?)", n)
+		}
+		r.errorf(id.NamePos, "undefined: %s%s", id.Name, hint)
 	}
 	id.Scope = uint8(scope)
 	return binding{scope, id.Index}
 }
 
+// spellcheck returns the most likely misspelling of
+// the name use.id in the environment use.env.
+func (r *resolver) spellcheck(use use) string {
+	var names []string
+
+	// locals
+	for b := use.env; b != nil; b = b.parent {
+		for name := range b.bindings {
+			names = append(names, name)
+		}
+	}
+
+	// globals
+	//
+	// We have no way to enumerate predeclared/universe,
+	// which includes prior names in the REPL session.
+	for _, id := range r.moduleGlobals {
+		names = append(names, id.Name)
+	}
+
+	sort.Strings(names)
+	return spell.Nearest(use.id.Name, names)
+}
+
 // resolveLocalUses is called when leaving a container (function/module)
 // block.  It resolves all uses of locals within that block.
 func (b *block) resolveLocalUses() {
@@ -804,7 +837,7 @@ func (r *resolver) resolveNonLocalUses(b *block) {
 		r.resolveNonLocalUses(child)
 	}
 	for _, use := range b.uses {
-		bind := r.lookupLexical(use.id, use.env)
+		bind := r.lookupLexical(use, use.env)
 		use.id.Scope = uint8(bind.scope)
 		use.id.Index = bind.index
 	}
@@ -827,27 +860,28 @@ func lookupLocal(use use) binding {
 	return binding{} // not found in this function
 }
 
-// lookupLexical looks up an identifier within its lexically enclosing environment.
-func (r *resolver) lookupLexical(id *syntax.Ident, env *block) (bind binding) {
+// lookupLexical looks up an identifier use.id within its lexically enclosing environment.
+// The use.env field captures the original environment for error reporting.
+func (r *resolver) lookupLexical(use use, env *block) (bind binding) {
 	if debug {
-		fmt.Printf("lookupLexical %s in %s = ...\n", id.Name, env)
+		fmt.Printf("lookupLexical %s in %s = ...\n", use.id.Name, env)
 		defer func() { fmt.Printf("= %d\n", bind) }()
 	}
 
 	// Is this the module block?
 	if env.isModule() {
-		return r.useGlobal(id) // global, predeclared, or not found
+		return r.useGlobal(use) // global, predeclared, or not found
 	}
 
 	// Defined in this block?
-	bind, ok := env.bindings[id.Name]
+	bind, ok := env.bindings[use.id.Name]
 	if !ok {
 		// Defined in parent block?
-		bind = r.lookupLexical(id, env.parent)
+		bind = r.lookupLexical(use, env.parent)
 		if env.function != nil && (bind.scope == Local || bind.scope == Free) {
 			// Found in parent block, which belongs to enclosing function.
 			id := &syntax.Ident{
-				Name:  id.Name,
+				Name:  use.id.Name,
 				Scope: uint8(bind.scope),
 				Index: bind.index,
 			}
@@ -862,7 +896,7 @@ func (r *resolver) lookupLexical(id *syntax.Ident, env *block) (bind binding) {
 
 		// Memoize, to avoid duplicate free vars
 		// and redundant global (failing) lookups.
-		env.bind(id.Name, bind)
+		env.bind(use.id.Name, bind)
 	}
 	return bind
 }
diff --git a/resolve/testdata/resolve.star b/resolve/testdata/resolve.star
index 1baad68..df96711 100644
--- a/resolve/testdata/resolve.star
+++ b/resolve/testdata/resolve.star
@@ -310,3 +310,16 @@ U = 1 # ok (legacy)
 # https://github.com/bazelbuild/starlark/starlark/issues/21
 def f(**kwargs): pass
 f(a=1, a=1) ### `keyword argument a repeated`
+
+
+---
+# spelling
+
+print = U
+
+hello = 1
+print(hollo) ### `undefined: hollo \(did you mean hello\?\)`
+
+def f(abc):
+   print(abd) ### `undefined: abd \(did you mean abc\?\)`
+   print(goodbye) ### `undefined: goodbye$`
diff --git a/starlark/eval.go b/starlark/eval.go
index 9629b16..a144052 100644
--- a/starlark/eval.go
+++ b/starlark/eval.go
@@ -18,6 +18,7 @@ import (
 	"unicode/utf8"
 
 	"go.starlark.net/internal/compile"
+	"go.starlark.net/internal/spell"
 	"go.starlark.net/resolve"
 	"go.starlark.net/syntax"
 )
@@ -450,36 +451,44 @@ func listExtend(x *List, y Iterable) {
 
 // getAttr implements x.dot.
 func getAttr(x Value, name string) (Value, error) {
-	var hint string
+	hasAttr, ok := x.(HasAttrs)
+	if !ok {
+		return nil, fmt.Errorf("%s has no .%s field or method", x.Type(), name)
+	}
 
-	// field or method?
-	if x, ok := x.(HasAttrs); ok {
-		if v, err := x.Attr(name); v != nil || err != nil {
-			return v, err
+	var errmsg string
+	v, err := hasAttr.Attr(name)
+	if err == nil {
+		if v != nil {
+			return v, nil // success
 		}
+		// (nil, nil) => generic error
+		errmsg = fmt.Sprintf("%s has no .%s field or method", x.Type(), name)
+	} else if nsa, ok := err.(NoSuchAttrError); ok {
+		errmsg = string(nsa)
+	} else {
+		return nil, err // return error as is
+	}
 
-		// check spelling
-		if n := nearest(name, x.AttrNames()); n != "" {
-			hint = fmt.Sprintf(" (did you mean .%s?)", n)
-		}
+	// add spelling hint
+	if n := spell.Nearest(name, hasAttr.AttrNames()); n != "" {
+		errmsg = fmt.Sprintf("%s (did you mean .%s?)", errmsg, n)
 	}
 
-	return nil, fmt.Errorf("%s has no .%s field or method%s", x.Type(), name, hint)
+	return nil, fmt.Errorf("%s", errmsg)
 }
 
 // setField implements x.name = y.
 func setField(x Value, name string, y Value) error {
 	if x, ok := x.(HasSetField); ok {
-		if err := x.SetField(name, y); err != ErrNoSuchField {
-			return err
-		}
-
-		// No such field: check spelling.
-		var hint string
-		if n := nearest(name, x.AttrNames()); n != "" {
-			hint = fmt.Sprintf(" (did you mean .%s?)", n)
+		err := x.SetField(name, y)
+		if _, ok := err.(NoSuchAttrError); ok {
+			// No such field: check spelling.
+			if n := spell.Nearest(name, x.AttrNames()); n != "" {
+				err = fmt.Errorf("%s (did you mean .%s?)", err, n)
+			}
 		}
-		return fmt.Errorf("%s has no .%s field%s", x.Type(), name, hint)
+		return err
 	}
 
 	return fmt.Errorf("can't assign to .%s field of %s", name, x.Type())
diff --git a/starlark/eval_test.go b/starlark/eval_test.go
index cf2b23e..abb0dd9 100644
--- a/starlark/eval_test.go
+++ b/starlark/eval_test.go
@@ -226,8 +226,8 @@ func (hf *hasfields) SetField(name string, val starlark.Value) error {
 	if hf.frozen {
 		return fmt.Errorf("cannot set field on a frozen hasfields")
 	}
-	if strings.HasPrefix(name, "no") {
-		return starlark.ErrNoSuchField // for testing
+	if strings.HasPrefix(name, "no") { // for testing
+		return starlark.NoSuchAttrError(fmt.Sprintf("no .%s field", name))
 	}
 	hf.attrs[name] = val
 	return nil
diff --git a/starlark/testdata/module.star b/starlark/testdata/module.star
index cde2bd7..8edff1f 100644
--- a/starlark/testdata/module.star
+++ b/starlark/testdata/module.star
@@ -6,3 +6,12 @@ assert.eq(type(assert), "module")
 assert.eq(str(assert), '<module "assert">')
 assert.eq(dir(assert), ["contains", "eq", "fail", "fails", "lt", "ne", "true"])
 assert.fails(lambda : {assert: None}, "unhashable: module")
+
+def assignfield():
+    assert.foo = None
+
+assert.fails(assignfield, "can't assign to .foo field of module")
+
+# no such field
+assert.fails(lambda : assert.nonesuch, "module has no .nonesuch field or method$")
+assert.fails(lambda : assert.falls, "module has no .falls field or method .did you mean .fails\?")
diff --git a/starlark/value.go b/starlark/value.go
index 229faef..b5a4aed 100644
--- a/starlark/value.go
+++ b/starlark/value.go
@@ -68,7 +68,6 @@ package starlark // import "go.starlark.net/starlark"
 
 import (
 	"bytes"
-	"errors"
 	"fmt"
 	"math"
 	"math/big"
@@ -321,19 +320,21 @@ var (
 
 // A HasSetField value has fields that may be written by a dot expression (x.f = y).
 //
-// An implementation of SetField may return ErrNoSuchField,
-// in which case the runtime will report a better error that
-// includes the field name and warns of possible misspelling.
+// An implementation of SetField may return a NoSuchAttrError,
+// in which case the runtime may augment the error message to
+// warn of possible misspelling.
 type HasSetField interface {
 	HasAttrs
 	SetField(name string, val Value) error
 }
 
-// ErrNoSuchField may be returned by an implementation of
-// HasSetField.SetField to indicate that no such field exists.
-// In that case the runtime will report a better error that
-// includes the field name and warns of possible misspelling.
-var ErrNoSuchField = errors.New("no such field")
+// A NoSuchAttrError may be returned by an implementation of
+// HasAttrs.Attr or HasSetField.SetField to indicate that no such field
+// exists. In that case the runtime may augment the error message to
+// warn of possible misspelling.
+type NoSuchAttrError string
+
+func (e NoSuchAttrError) Error() string { return string(e) }
 
 // NoneType is the type of None.  Its only legal value is None.
 // (We represent it as a number, not struct{}, so that None may be constant.)
diff --git a/starlarkstruct/struct.go b/starlarkstruct/struct.go
index 07aa84c..ac9c955 100644
--- a/starlarkstruct/struct.go
+++ b/starlarkstruct/struct.go
@@ -228,7 +228,8 @@ func (s *Struct) Attr(name string) (starlark.Value, error) {
 	if s.constructor != Default {
 		ctor = s.constructor.String() + " "
 	}
-	return nil, fmt.Errorf("%sstruct has no .%s attribute", ctor, name)
+	return nil, starlark.NoSuchAttrError(
+		fmt.Sprintf("%sstruct has no .%s attribute", ctor, name))
 }
 
 func (s *Struct) len() int { return len(s.entries) }