1// Copyright 2021 Google Inc. All rights reserved. 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// http://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 15package blueprint 16 17import ( 18 "sort" 19) 20 21func abs(a int) int { 22 if a < 0 { 23 return -a 24 } 25 return a 26} 27 28// This implementation is written to be recursive, because 29// we know Soong names are short, so we shouldn't hit the stack 30// depth. Also, the buffer is indexed this way so that new 31// allocations aren't needed. 32func levenshtein(a, b string, ai, bi, max int, buf [][]int) int { 33 if max == 0 { 34 return 0 35 } 36 if ai >= len(a) { 37 return len(b) - bi 38 } 39 if bi >= len(b) { 40 return len(a) - ai 41 } 42 if buf[bi][ai] != 0 { 43 return buf[bi][ai] 44 } 45 if abs(len(a)-len(b)) >= max { 46 return max 47 } 48 var res = max 49 if a[ai] == b[bi] { 50 res = levenshtein(a, b, ai+1, bi+1, max, buf) 51 } else { 52 if c := levenshtein(a, b, ai+1, bi+1, max-1, buf); c < res { 53 res = c // replace 54 } 55 if c := levenshtein(a, b, ai+1, bi, max-1, buf); c < res { 56 res = c // delete from a 57 } 58 if c := levenshtein(a, b, ai, bi+1, max-1, buf); c < res { 59 res = c // delete from b 60 } 61 res += 1 62 } 63 buf[bi][ai] = res 64 return res 65} 66 67func stringIn(arr []string, str string) bool { 68 for _, a := range arr { 69 if a == str { 70 return true 71 } 72 } 73 return false 74} 75 76func namesLike(name string, unlike string, moduleGroups []*moduleGroup) []string { 77 const kAllowedDifferences = 10 78 buf := make([][]int, len(name)+kAllowedDifferences) 79 for i := range buf { 80 buf[i] = make([]int, len(name)) 81 } 82 83 var best []string 84 bestVal := kAllowedDifferences + 1 85 86 for _, group := range moduleGroups { 87 other := group.name 88 89 if other == unlike { 90 continue 91 } 92 93 l := levenshtein(name, other, 0, 0, kAllowedDifferences, buf) 94 // fmt.Printf("levenshtein %q %q %d\n", name, other, l) 95 96 // slightly better to use a min-heap 97 if l == 0 { 98 // these are the same, so it must be in a different namespace 99 // ignore... 100 } else if l < bestVal { 101 bestVal = l 102 best = []string{other} 103 } else if l == bestVal && !stringIn(best, other) { 104 best = append(best, other) 105 } 106 107 // zero buffer once used 108 for _, v := range buf { 109 for j := range v { 110 v[j] = 0 111 } 112 } 113 } 114 115 sort.Strings(best) 116 return best 117} 118