Merge "Add name hint to blueprint." am: aefc0a9b9b am: b72e38080e am: bedb263bc4 am: 85934ee063
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>
diff --git a/Android.bp b/Android.bp
index 547d610..20fa495 100644
--- a/Android.bp
+++ b/Android.bp
@@ -39,6 +39,7 @@
pkgPath: "github.com/google/blueprint",
srcs: [
"context.go",
+ "levenshtein.go",
"glob.go",
"live_tracker.go",
"mangle.go",
@@ -54,6 +55,7 @@
],
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) 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 @@
// 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 @@
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 @@
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 {
