Merge "Add name hint to blueprint." am: aefc0a9b9b am: b72e38080e am: bedb263bc4 am: 85934ee063android-14.0.0_r45android-14.0.0_r44android-14.0.0_r43android-14.0.0_r42android-14.0.0_r41android-14.0.0_r40android-14.0.0_r39android-14.0.0_r38android-14.0.0_r27android-14.0.0_r26android-14.0.0_r25android-14.0.0_r24android-14.0.0_r23android-14.0.0_r22android-14.0.0_r21android-14.0.0_r20android-14.0.0_r19android-14.0.0_r18android-14.0.0_r17android-14.0.0_r16android14-qpr1-s2-releaseandroid14-qpr1-releaseandroid14-d2-s5-releaseandroid14-d2-s4-releaseandroid14-d2-s3-releaseandroid14-d2-s2-releaseandroid14-d2-s1-releaseandroid14-d2-release

Original change: https://android-review.googlesource.com/c/platform/build/blueprint/+/2518036

Change-Id: I2b87ffe635740d642071950fc5a95e2460ad716e
Signed-off-by: Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>

5 files changed, 183 insertions, 4 deletions

diff --git a/Android.bp b/Android.bp
index 547d610..20fa495 100644
--- a/Android.bp
+++ b/Android.bp
@@ -39,6 +39,7 @@ bootstrap_go_package {
     pkgPath: "github.com/google/blueprint",
     srcs: [
         "context.go",
+        "levenshtein.go",
         "glob.go",
         "live_tracker.go",
         "mangle.go",
@@ -54,6 +55,7 @@ bootstrap_go_package {
     ],
     testSrcs: [
         "context_test.go",
+        "levenshtein_test.go",
         "glob_test.go",
         "module_ctx_test.go",
         "ninja_strings_test.go",
diff --git a/context.go b/context.go
index 54f2fd8..17daa8a 100644
--- a/context.go
+++ b/context.go
@@ -3615,7 +3615,8 @@ func (c *Context) discoveredMissingDependencies(module *moduleInfo, depName stri
 }
 
 func (c *Context) missingDependencyError(module *moduleInfo, depName string) (errs error) {
-	err := c.nameInterface.MissingDependencyError(module.Name(), module.namespace(), depName)
+	guess := namesLike(depName, module.Name(), c.moduleGroups)
+	err := c.nameInterface.MissingDependencyError(module.Name(), module.namespace(), depName, guess)
 	return &BlueprintError{
 		Err: err,
 		Pos: module.pos,
diff --git a/levenshtein.go b/levenshtein.go
new file mode 100644
index 0000000..de5b75a
--- /dev/null
+++ b/levenshtein.go
@@ -0,0 +1,117 @@
+// Copyright 2021 Google Inc. All rights reserved.
+//
+// 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
+//
+//     http://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 blueprint
+
+import (
+	"sort"
+)
+
+func abs(a int) int {
+	if a < 0 {
+		return -a
+	}
+	return a
+}
+
+// This implementation is written to be recursive, because
+// we know Soong names are short, so we shouldn't hit the stack
+// depth. Also, the buffer is indexed this way so that new
+// allocations aren't needed.
+func levenshtein(a, b string, ai, bi, max int, buf [][]int) int {
+	if max == 0 {
+		return 0
+	}
+	if ai >= len(a) {
+		return len(b) - bi
+	}
+	if bi >= len(b) {
+		return len(a) - ai
+	}
+	if buf[bi][ai] != 0 {
+		return buf[bi][ai]
+	}
+	if abs(len(a)-len(b)) >= max {
+		return max
+	}
+	var res = max
+	if a[ai] == b[bi] {
+		res = levenshtein(a, b, ai+1, bi+1, max, buf)
+	} else {
+		if c := levenshtein(a, b, ai+1, bi+1, max-1, buf); c < res {
+			res = c // replace
+		}
+		if c := levenshtein(a, b, ai+1, bi, max-1, buf); c < res {
+			res = c // delete from a
+		}
+		if c := levenshtein(a, b, ai, bi+1, max-1, buf); c < res {
+			res = c // delete from b
+		}
+		res += 1
+	}
+	buf[bi][ai] = res
+	return res
+}
+
+func stringIn(arr []string, str string) bool {
+	for _, a := range arr {
+		if a == str {
+			return true
+		}
+	}
+	return false
+}
+
+func namesLike(name string, unlike string, moduleGroups []*moduleGroup) []string {
+	const kAllowedDifferences = 10
+	buf := make([][]int, len(name)+kAllowedDifferences)
+	for i := range buf {
+		buf[i] = make([]int, len(name))
+	}
+
+	var best []string
+	bestVal := kAllowedDifferences + 1
+
+	for _, group := range moduleGroups {
+		other := group.name
+
+		if other == unlike {
+			continue
+		}
+
+		l := levenshtein(name, other, 0, 0, kAllowedDifferences, buf)
+		// fmt.Printf("levenshtein %q %q %d\n", name, other, l)
+
+		// slightly better to use a min-heap
+		if l == 0 {
+			// these are the same, so it must be in a different namespace
+			// ignore...
+		} else if l < bestVal {
+			bestVal = l
+			best = []string{other}
+		} else if l == bestVal && !stringIn(best, other) {
+			best = append(best, other)
+		}
+
+		// zero buffer once used
+		for _, v := range buf {
+			for j := range v {
+				v[j] = 0
+			}
+		}
+	}
+
+	sort.Strings(best)
+	return best
+}
diff --git a/levenshtein_test.go b/levenshtein_test.go
new file mode 100644
index 0000000..60f0293
--- /dev/null
+++ b/levenshtein_test.go
@@ -0,0 +1,54 @@
+// Copyright 2014 Google Inc. All rights reserved.
+//
+// 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
+//
+//     http://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 blueprint
+
+import (
+	"reflect"
+	"testing"
+)
+
+func mods(mods []string) []*moduleGroup {
+	ret := []*moduleGroup{}
+
+	for _, v := range mods {
+		m := moduleGroup{name: v}
+		ret = append(ret, &m)
+	}
+
+	return ret
+}
+
+func assertEqual(t *testing.T, a, b []string) {
+	if len(a) == 0 && len(b) == 0 {
+		return
+	}
+
+	if !reflect.DeepEqual(a, b) {
+		t.Errorf("Expected the following to be equal:\n\t%q\n\t%q", a, b)
+	}
+}
+
+func TestLevenshteinWontGuessUnlike(t *testing.T) {
+	assertEqual(t, namesLike("a", "test", mods([]string{"test"})), []string{})
+}
+func TestLevenshteinInsert(t *testing.T) {
+	assertEqual(t, namesLike("a", "test", mods([]string{"ab", "ac", "not_this"})), []string{"ab", "ac"})
+}
+func TestLevenshteinDelete(t *testing.T) {
+	assertEqual(t, namesLike("ab", "test", mods([]string{"a", "b", "not_this"})), []string{"a", "b"})
+}
+func TestLevenshteinReplace(t *testing.T) {
+	assertEqual(t, namesLike("aa", "test", mods([]string{"ab", "ac", "not_this"})), []string{"ab", "ac"})
+}
diff --git a/name_interface.go b/name_interface.go
index d4b3383..db82453 100644
--- a/name_interface.go
+++ b/name_interface.go
@@ -66,7 +66,7 @@ type NameInterface interface {
 
 	// Returns an error indicating that the given module could not be found.
 	// The error contains some diagnostic information about where the dependency can be found.
-	MissingDependencyError(depender string, dependerNamespace Namespace, depName string) (err error)
+	MissingDependencyError(depender string, dependerNamespace Namespace, depName string, guess []string) (err error)
 
 	// Rename
 	Rename(oldName string, newName string, namespace Namespace) []error
@@ -197,7 +197,7 @@ func (s *SimpleNameInterface) AllModules() []ModuleGroup {
 	return groups
 }
 
-func (s *SimpleNameInterface) MissingDependencyError(depender string, dependerNamespace Namespace, dependency string) (err error) {
+func (s *SimpleNameInterface) MissingDependencyError(depender string, dependerNamespace Namespace, dependency string, guess []string) (err error) {
 	skipInfos, skipped := s.SkippedModuleFromName(dependency, dependerNamespace)
 	if skipped {
 		filesFound := make([]string, 0, len(skipInfos))
@@ -215,7 +215,12 @@ func (s *SimpleNameInterface) MissingDependencyError(depender string, dependerNa
 			strings.Join(reasons, "; "),
 		)
 	}
-	return fmt.Errorf("%q depends on undefined module %q", depender, dependency)
+
+	guessString := ""
+	if len(guess) > 0 {
+		guessString = fmt.Sprintf(" Did you mean %q?", guess)
+	}
+	return fmt.Errorf("%q depends on undefined module %q.%s", depender, dependency, guessString)
 }
 
 func (s *SimpleNameInterface) GetNamespace(ctx NamespaceContext) Namespace {