diff options
author | Android Build Coastguard Worker <android-build-coastguard-worker@google.com> | 2023-04-13 01:06:03 +0000 |
---|---|---|
committer | Android Build Coastguard Worker <android-build-coastguard-worker@google.com> | 2023-04-13 01:06:03 +0000 |
commit | 58e389be699fdcebb823ae78520fe453a13c41e4 (patch) | |
tree | a76404902892cd8b0a206c0d78fed0563f25d968 | |
parent | 880b9b479e99f0110396851ceb1609e20df9c46b (diff) | |
parent | 85934ee06375f86300beb453e8fe41f11f69c0c8 (diff) | |
download | blueprint-android14-s2-release.tar.gz |
Snap for 9930594 from 85934ee06375f86300beb453e8fe41f11f69c0c8 to udc-releaseandroid-vts-14.0_r4android-vts-14.0_r3android-vts-14.0_r2android-vts-14.0_r1android-security-14.0.0_r9android-security-14.0.0_r8android-security-14.0.0_r7android-security-14.0.0_r6android-security-14.0.0_r5android-security-14.0.0_r4android-security-14.0.0_r3android-security-14.0.0_r2android-security-14.0.0_r1android-platform-14.0.0_r7android-platform-14.0.0_r6android-platform-14.0.0_r5android-platform-14.0.0_r4android-platform-14.0.0_r3android-platform-14.0.0_r2android-platform-14.0.0_r1android-cts-14.0_r4android-cts-14.0_r3android-cts-14.0_r2android-cts-14.0_r1android-14.0.0_r28android-14.0.0_r2android-14.0.0_r15android-14.0.0_r14android-14.0.0_r13android-14.0.0_r1android14-tests-releaseandroid14-security-releaseandroid14-s2-releaseandroid14-s1-releaseandroid14-releaseandroid14-platform-release
Change-Id: I5c560e310e43658ea2001df144fbf1d21957a449
-rw-r--r-- | Android.bp | 2 | ||||
-rw-r--r-- | context.go | 3 | ||||
-rw-r--r-- | levenshtein.go | 117 | ||||
-rw-r--r-- | levenshtein_test.go | 54 | ||||
-rw-r--r-- | name_interface.go | 11 |
5 files changed, 183 insertions, 4 deletions
@@ -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", @@ -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 { |