android/depset_generic.go

// Copyright 2020 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 android

import (
	"fmt"
	"reflect"
)

// depSet is designed to be conceptually compatible with Bazel's depsets:
// https://docs.bazel.build/versions/master/skylark/depsets.html

type DepSetOrder int

const (
	PREORDER DepSetOrder = iota
	POSTORDER
	TOPOLOGICAL
)

func (o DepSetOrder) String() string {
	switch o {
	case PREORDER:
		return "PREORDER"
	case POSTORDER:
		return "POSTORDER"
	case TOPOLOGICAL:
		return "TOPOLOGICAL"
	default:
		panic(fmt.Errorf("Invalid DepSetOrder %d", o))
	}
}

// A depSet efficiently stores a slice of an arbitrary type from transitive dependencies without
// copying. It is stored as a DAG of depSet nodes, each of which has some direct contents and a list
// of dependency depSet nodes.
//
// A depSet has an order that will be used to walk the DAG when ToList() is called.  The order
// can be POSTORDER, PREORDER, or TOPOLOGICAL.  POSTORDER and PREORDER orders return a postordered
// or preordered left to right flattened list.  TOPOLOGICAL returns a list that guarantees that
// elements of children are listed after all of their parents (unless there are duplicate direct
// elements in the depSet or any of its transitive dependencies, in which case the ordering of the
// duplicated element is not guaranteed).
//
// A depSet is created by newDepSet or newDepSetBuilder.Build from the slice for direct contents
// and the *depSets of dependencies. A depSet is immutable once created.
//
// This object uses reflection to remain agnostic to the type it contains.  It should be replaced
// with generics once those exist in Go.  Callers should generally use a thin wrapper around depSet
// that provides type-safe methods like DepSet for Paths.
type depSet struct {
	preorder   bool
	reverse    bool
	order      DepSetOrder
	direct     interface{}
	transitive []*depSet
}

type depSetInterface interface {
	embeddedDepSet() *depSet
}

func (d *depSet) embeddedDepSet() *depSet {
	return d
}

var _ depSetInterface = (*depSet)(nil)

// newDepSet returns an immutable depSet with the given order, direct and transitive contents.
// direct must be a slice, but is not type-safe due to the lack of generics in Go.  It can be a
// nil slice, but not a nil interface{}, i.e. []string(nil) but not nil.
func newDepSet(order DepSetOrder, direct interface{}, transitive interface{}) *depSet {
	var directCopy interface{}
	transitiveDepSet := sliceToDepSets(transitive, order)

	if order == TOPOLOGICAL {
		directCopy = reverseSlice(direct)
		reverseSliceInPlace(transitiveDepSet)
	} else {
		directCopy = copySlice(direct)
	}

	return &depSet{
		preorder:   order == PREORDER,
		reverse:    order == TOPOLOGICAL,
		order:      order,
		direct:     directCopy,
		transitive: transitiveDepSet,
	}
}

// depSetBuilder is used to create an immutable depSet.
type depSetBuilder struct {
	order      DepSetOrder
	direct     reflect.Value
	transitive []*depSet
}

// newDepSetBuilder returns a depSetBuilder to create an immutable depSet with the given order and
// type, represented by a slice of type that will be in the depSet.
func newDepSetBuilder(order DepSetOrder, typ interface{}) *depSetBuilder {
	empty := reflect.Zero(reflect.TypeOf(typ))
	return &depSetBuilder{
		order:  order,
		direct: empty,
	}
}

// sliceToDepSets converts a slice of any type that implements depSetInterface (by having a depSet
// embedded in it) into a []*depSet.
func sliceToDepSets(in interface{}, order DepSetOrder) []*depSet {
	slice := reflect.ValueOf(in)
	length := slice.Len()
	out := make([]*depSet, length)
	for i := 0; i < length; i++ {
		vi := slice.Index(i)
		depSetIntf, ok := vi.Interface().(depSetInterface)
		if !ok {
			panic(fmt.Errorf("element %d is a %s, not a depSetInterface", i, vi.Type()))
		}
		depSet := depSetIntf.embeddedDepSet()
		if depSet.order != order {
			panic(fmt.Errorf("incompatible order, new depSet is %s but transitive depSet is %s",
				order, depSet.order))
		}
		out[i] = depSet
	}
	return out
}

// DirectSlice adds direct contents to the depSet being built by a depSetBuilder. Newly added direct
// contents are to the right of any existing direct contents.  The argument must be a slice, but
// is not type-safe due to the lack of generics in Go.
func (b *depSetBuilder) DirectSlice(direct interface{}) *depSetBuilder {
	b.direct = reflect.AppendSlice(b.direct, reflect.ValueOf(direct))
	return b
}

// Direct adds direct contents to the depSet being built by a depSetBuilder. Newly added direct
// contents are to the right of any existing direct contents.  The argument must be the same type
// as the element of the slice passed to newDepSetBuilder, but is not type-safe due to the lack of
// generics in Go.
func (b *depSetBuilder) Direct(direct interface{}) *depSetBuilder {
	b.direct = reflect.Append(b.direct, reflect.ValueOf(direct))
	return b
}

// Transitive adds transitive contents to the DepSet being built by a DepSetBuilder. Newly added
// transitive contents are to the right of any existing transitive contents.  The argument can
// be any slice of type that has depSet embedded in it.
func (b *depSetBuilder) Transitive(transitive interface{}) *depSetBuilder {
	depSets := sliceToDepSets(transitive, b.order)
	b.transitive = append(b.transitive, depSets...)
	return b
}

// Returns the depSet being built by this depSetBuilder.  The depSetBuilder retains its contents
// for creating more depSets.
func (b *depSetBuilder) Build() *depSet {
	return newDepSet(b.order, b.direct.Interface(), b.transitive)
}

// walk calls the visit method in depth-first order on a DepSet, preordered if d.preorder is set,
// otherwise postordered.
func (d *depSet) walk(visit func(interface{})) {
	visited := make(map[*depSet]bool)

	var dfs func(d *depSet)
	dfs = func(d *depSet) {
		visited[d] = true
		if d.preorder {
			visit(d.direct)
		}
		for _, dep := range d.transitive {
			if !visited[dep] {
				dfs(dep)
			}
		}

		if !d.preorder {
			visit(d.direct)
		}
	}

	dfs(d)
}

// ToList returns the depSet flattened to a list.  The order in the list is based on the order
// of the depSet.  POSTORDER and PREORDER orders return a postordered or preordered left to right
// flattened list.  TOPOLOGICAL returns a list that guarantees that elements of children are listed
// after all of their parents (unless there are duplicate direct elements in the DepSet or any of
// its transitive dependencies, in which case the ordering of the duplicated element is not
// guaranteed).
//
// This method uses a reflection-based implementation to find the unique elements in slice, which
// is around 3x slower than a concrete implementation.  Type-safe wrappers around depSet can
// provide their own implementation of ToList that calls depSet.toList with a method that
// uses a concrete implementation.
func (d *depSet) ToList() interface{} {
	return d.toList(firstUnique)
}

// toList returns the depSet flattened to a list.  The order in the list is based on the order
// of the depSet.  POSTORDER and PREORDER orders return a postordered or preordered left to right
// flattened list.  TOPOLOGICAL returns a list that guarantees that elements of children are listed
// after all of their parents (unless there are duplicate direct elements in the DepSet or any of
// its transitive dependencies, in which case the ordering of the duplicated element is not
// guaranteed).  The firstUniqueFunc is used to remove duplicates from the list.
func (d *depSet) toList(firstUniqueFunc func(interface{}) interface{}) interface{} {
	if d == nil {
		return nil
	}
	slice := reflect.Zero(reflect.TypeOf(d.direct))
	d.walk(func(paths interface{}) {
		slice = reflect.AppendSlice(slice, reflect.ValueOf(paths))
	})
	list := slice.Interface()
	list = firstUniqueFunc(list)
	if d.reverse {
		reverseSliceInPlace(list)
	}
	return list
}

// firstUnique returns all unique elements of a slice, keeping the first copy of each.  It
// modifies the slice contents in place, and returns a subslice of the original slice.  The
// argument must be a slice, but is not type-safe due to the lack of reflection in Go.
//
// Performance of the reflection-based firstUnique is up to 3x slower than a concrete type
// version such as FirstUniqueStrings.
func firstUnique(slice interface{}) interface{} {
	// 4 was chosen based on Benchmark_firstUnique results.
	if reflect.ValueOf(slice).Len() > 4 {
		return firstUniqueMap(slice)
	}
	return firstUniqueList(slice)
}

// firstUniqueList is an implementation of firstUnique using an O(N^2) list comparison to look for
// duplicates.
func firstUniqueList(in interface{}) interface{} {
	writeIndex := 0
	slice := reflect.ValueOf(in)
	length := slice.Len()
outer:
	for readIndex := 0; readIndex < length; readIndex++ {
		readValue := slice.Index(readIndex)
		for compareIndex := 0; compareIndex < writeIndex; compareIndex++ {
			compareValue := slice.Index(compareIndex)
			// These two Interface() calls seem to cause an allocation and significantly
			// slow down this list-based implementation.  The map implementation below doesn't
			// have this issue because reflect.Value.MapIndex takes a Value and appears to be
			// able to do the map lookup without an allocation.
			if readValue.Interface() == compareValue.Interface() {
				// The value at readIndex already exists somewhere in the output region
				// of the slice before writeIndex, skip it.
				continue outer
			}
		}
		if readIndex != writeIndex {
			writeValue := slice.Index(writeIndex)
			writeValue.Set(readValue)
		}
		writeIndex++
	}
	return slice.Slice(0, writeIndex).Interface()
}

var trueValue = reflect.ValueOf(true)

// firstUniqueList is an implementation of firstUnique using an O(N) hash set lookup to look for
// duplicates.
func firstUniqueMap(in interface{}) interface{} {
	writeIndex := 0
	slice := reflect.ValueOf(in)
	length := slice.Len()
	seen := reflect.MakeMapWithSize(reflect.MapOf(slice.Type().Elem(), trueValue.Type()), slice.Len())
	for readIndex := 0; readIndex < length; readIndex++ {
		readValue := slice.Index(readIndex)
		if seen.MapIndex(readValue).IsValid() {
			continue
		}
		seen.SetMapIndex(readValue, trueValue)
		if readIndex != writeIndex {
			writeValue := slice.Index(writeIndex)
			writeValue.Set(readValue)
		}
		writeIndex++
	}
	return slice.Slice(0, writeIndex).Interface()
}

// reverseSliceInPlace reverses the elements of a slice in place.  The argument must be a slice, but
// is not type-safe due to the lack of reflection in Go.
func reverseSliceInPlace(in interface{}) {
	swapper := reflect.Swapper(in)
	slice := reflect.ValueOf(in)
	length := slice.Len()
	for i, j := 0, length-1; i < j; i, j = i+1, j-1 {
		swapper(i, j)
	}
}

// reverseSlice returns a copy of a slice in reverse order.  The argument must be a slice, but is
// not type-safe due to the lack of reflection in Go.
func reverseSlice(in interface{}) interface{} {
	slice := reflect.ValueOf(in)
	if !slice.IsValid() || slice.IsNil() {
		return in
	}
	if slice.Kind() != reflect.Slice {
		panic(fmt.Errorf("%t is not a slice", in))
	}
	length := slice.Len()
	if length == 0 {
		return in
	}
	out := reflect.MakeSlice(slice.Type(), length, length)
	for i := 0; i < length; i++ {
		out.Index(i).Set(slice.Index(length - 1 - i))
	}
	return out.Interface()
}

// copySlice returns a copy of a slice.  The argument must be a slice, but is not type-safe due to
// the lack of reflection in Go.
func copySlice(in interface{}) interface{} {
	slice := reflect.ValueOf(in)
	if !slice.IsValid() || slice.IsNil() {
		return in
	}
	length := slice.Len()
	if length == 0 {
		return in
	}
	out := reflect.MakeSlice(slice.Type(), length, length)
	reflect.Copy(out, slice)
	return out.Interface()
}