pkg/bufman/bufpkg/bufimage/bufimageutil/source_paths_remap.go

// Licensed to the Apache Software Foundation (ASF) under one or more
// contributor license agreements.  See the NOTICE file distributed with
// this work for additional information regarding copyright ownership.
// The ASF licenses this file to You 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 bufimageutil

import (
	"sort"
)

// sourcePathsRemapTrieNode is a node in a trie. Each node represents the
// path of a source code location.
type sourcePathsRemapTrieNode struct {
	oldIndex int32
	// If == -1, the item at this path is being deleted. Otherwise,
	// if != oldIndex, the item at this path is being moved, as well as
	// all its descendents in the trie.
	newIndex int32
	// If true, the item at this point has its comments omitted. This is
	// used to omit comments for messages that, after filtering, are only
	// present as a namespace (so the comments likely no longer apply).
	noComment bool
	// This node's children. These represent paths for which the current
	// node is a path prefix (aka ancestor).
	children sourcePathsRemapTrie
}

// sourcePathsRemapTrie is a trie (aka prefix tree) whose children are a
// sorted slice (more efficient than a map, mainly due to not having to
// sort it with every addition, in practice, since source code info is
// mostly sorted).
//
// Each node in the trie represents some path of a source code location.
// This is used to track renumbering and deletions of paths.
type sourcePathsRemapTrie []*sourcePathsRemapTrieNode

// markMoved inserts the given path into the trie and marks the last element
// of oldPath to be replaced with newIndex.
func (t *sourcePathsRemapTrie) markMoved(oldPath []int32, newIndex int32) {
	t.doTrieInsert(oldPath, newIndex, false)
}

// markDeleted marks the given path for deletion.
func (t *sourcePathsRemapTrie) markDeleted(oldPath []int32) {
	t.doTrieInsert(oldPath, -1, false)
}

// markNoComment inserts the given path into the trie and marks the element so
// its comments will be dropped.
func (t *sourcePathsRemapTrie) markNoComment(oldPath []int32) {
	t.doTrieInsert(oldPath, oldPath[len(oldPath)-1], true)
}

func (t *sourcePathsRemapTrie) doTrieInsert(oldPath []int32, newIndex int32, noComment bool) {
	if t == nil {
		return
	}
	items := *t
	searchIndex := oldPath[0]
	idx, found := sort.Find(len(items), func(i int) int {
		return int(searchIndex - items[i].oldIndex)
	})
	if !found {
		// shouldn't usually need to sort because incoming items are often in order
		needSort := len(items) > 0 && searchIndex < items[len(items)-1].oldIndex
		idx = len(items)
		items = append(items, &sourcePathsRemapTrieNode{
			oldIndex: searchIndex,
			newIndex: searchIndex,
		})
		if needSort {
			sort.Slice(items, func(i, j int) bool {
				return items[i].oldIndex < items[j].oldIndex
			})
			// find the index of the thing we just added
			idx, _ = sort.Find(len(items), func(i int) int {
				return int(searchIndex - items[i].oldIndex)
			})
		}
		*t = items
	}
	if len(oldPath) > 1 {
		items[idx].children.doTrieInsert(oldPath[1:], newIndex, noComment)
		return
	}
	if noComment {
		items[idx].noComment = noComment
	} else {
		items[idx].newIndex = newIndex
	}
}

// newPath returns the corrected path of oldPath, given any moves and
// deletions inserted into t. If the item at the given oldPath was deleted
// then nil is returned. Otherwise, the corrected path is returned. If the
// item at oldPath was not moved or deleted, the returned path has the
// same values as oldPath.
func (t *sourcePathsRemapTrie) newPath(oldPath []int32) (path []int32, noComment bool) {
	if len(oldPath) == 0 {
		// make sure return value is non-nil, so response doesn't
		// get confused for "delete this entry"
		return []int32{}, false
	}
	if t == nil {
		return oldPath, false
	}
	newPath := make([]int32, len(oldPath))
	keep, noComment := t.fix(oldPath, newPath)
	if !keep {
		return nil, false
	}
	return newPath, noComment
}

func (t *sourcePathsRemapTrie) fix(oldPath, newPath []int32) (keep, noComment bool) {
	items := *t
	searchIndex := oldPath[0]
	idx, found := sort.Find(len(items), func(i int) int {
		return int(searchIndex - items[i].oldIndex)
	})
	if !found {
		copy(newPath, oldPath)
		return true, false
	}
	item := items[idx]
	if item.newIndex == -1 {
		return false, false
	}
	newPath[0] = item.newIndex
	if len(oldPath) > 1 {
		if item.newIndex == -1 {
			newPath[0] = item.oldIndex
		}
		return item.children.fix(oldPath[1:], newPath[1:])
	}
	return true, item.noComment
}