levenshtein.go

// 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
}