vendor: remove vendored golang.org/x/tools, as it's not needed
This dependency was added in 6cdbf07be9d0ad08776df0b65fb1b3e4e617c42a,
but looks like the code was vendored manually, or vendored, then removeed
from vendor.conf.
This commit removes the vendored files, as they are not needed to build
our binaries.
Signed-off-by: Sebastiaan van Stijn <github@gone.nl>
diff --git a/vendor/golang.org/x/tools/LICENSE b/vendor/golang.org/x/tools/LICENSE
deleted file mode 100644
index 6a66aea..0000000
--- a/vendor/golang.org/x/tools/LICENSE
+++ /dev/null
@@ -1,27 +0,0 @@
-Copyright (c) 2009 The Go Authors. All rights reserved.
-
-Redistribution and use in source and binary forms, with or without
-modification, are permitted provided that the following conditions are
-met:
-
- * Redistributions of source code must retain the above copyright
-notice, this list of conditions and the following disclaimer.
- * Redistributions in binary form must reproduce the above
-copyright notice, this list of conditions and the following disclaimer
-in the documentation and/or other materials provided with the
-distribution.
- * Neither the name of Google Inc. nor the names of its
-contributors may be used to endorse or promote products derived from
-this software without specific prior written permission.
-
-THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
-LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
-A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
-OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
-SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
-LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
-DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
-THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
diff --git a/vendor/golang.org/x/tools/PATENTS b/vendor/golang.org/x/tools/PATENTS
deleted file mode 100644
index 7330990..0000000
--- a/vendor/golang.org/x/tools/PATENTS
+++ /dev/null
@@ -1,22 +0,0 @@
-Additional IP Rights Grant (Patents)
-
-"This implementation" means the copyrightable works distributed by
-Google as part of the Go project.
-
-Google hereby grants to You a perpetual, worldwide, non-exclusive,
-no-charge, royalty-free, irrevocable (except as stated in this section)
-patent license to make, have made, use, offer to sell, sell, import,
-transfer and otherwise run, modify and propagate the contents of this
-implementation of Go, where such license applies only to those patent
-claims, both currently owned or controlled by Google and acquired in
-the future, licensable by Google that are necessarily infringed by this
-implementation of Go. This grant does not include claims that would be
-infringed only as a consequence of further modification of this
-implementation. If you or your agent or exclusive licensee institute or
-order or agree to the institution of patent litigation against any
-entity (including a cross-claim or counterclaim in a lawsuit) alleging
-that this implementation of Go or any code incorporated within this
-implementation of Go constitutes direct or contributory patent
-infringement, or inducement of patent infringement, then any patent
-rights granted to you under this License for this implementation of Go
-shall terminate as of the date such litigation is filed.
diff --git a/vendor/golang.org/x/tools/README.md b/vendor/golang.org/x/tools/README.md
deleted file mode 100644
index 20be9e1..0000000
--- a/vendor/golang.org/x/tools/README.md
+++ /dev/null
@@ -1,27 +0,0 @@
-# Go Tools
-
-This subrepository holds the source for various packages and tools that support
-the Go programming language.
-
-Some of the tools, `godoc` and `vet` for example, are included in binary Go
-distributions.
-
-Others, including the Go `guru` and the test coverage tool, can be fetched with
-`go get`.
-
-Packages include a type-checker for Go and an implementation of the
-Static Single Assignment form (SSA) representation for Go programs.
-
-## Download/Install
-
-The easiest way to install is to run `go get -u golang.org/x/tools/...`. You can
-also manually git clone the repository to `$GOPATH/src/golang.org/x/tools`.
-
-## Report Issues / Send Patches
-
-This repository uses Gerrit for code changes. To learn how to submit changes to
-this repository, see https://golang.org/doc/contribute.html.
-
-The main issue tracker for the tools repository is located at
-https://github.com/golang/go/issues. Prefix your issue with "x/tools/(your
-subdir):" in the subject line, so it is easy to find.
diff --git a/vendor/golang.org/x/tools/container/intsets/popcnt_amd64.go b/vendor/golang.org/x/tools/container/intsets/popcnt_amd64.go
deleted file mode 100644
index 99ea813..0000000
--- a/vendor/golang.org/x/tools/container/intsets/popcnt_amd64.go
+++ /dev/null
@@ -1,20 +0,0 @@
-// Copyright 2015 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// +build amd64,!appengine,!gccgo
-
-package intsets
-
-func popcnt(x word) int
-func havePOPCNT() bool
-
-var hasPOPCNT = havePOPCNT()
-
-// popcount returns the population count (number of set bits) of x.
-func popcount(x word) int {
- if hasPOPCNT {
- return popcnt(x)
- }
- return popcountTable(x) // faster than Hacker's Delight
-}
diff --git a/vendor/golang.org/x/tools/container/intsets/popcnt_amd64.s b/vendor/golang.org/x/tools/container/intsets/popcnt_amd64.s
deleted file mode 100644
index 05c3d6f..0000000
--- a/vendor/golang.org/x/tools/container/intsets/popcnt_amd64.s
+++ /dev/null
@@ -1,30 +0,0 @@
-// Copyright 2015 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// +build amd64,!appengine,!gccgo
-
-#include "textflag.h"
-
-// func havePOPCNT() bool
-TEXT ·havePOPCNT(SB),4,$0
- MOVQ $1, AX
- CPUID
- SHRQ $23, CX
- ANDQ $1, CX
- MOVB CX, ret+0(FP)
- RET
-
-// func popcnt(word) int
-TEXT ·popcnt(SB),NOSPLIT,$0-8
- XORQ AX, AX
- MOVQ x+0(FP), SI
- // POPCNT (SI), AX is not recognized by Go assembler,
- // so we assemble it ourselves.
- BYTE $0xf3
- BYTE $0x48
- BYTE $0x0f
- BYTE $0xb8
- BYTE $0xc6
- MOVQ AX, ret+8(FP)
- RET
diff --git a/vendor/golang.org/x/tools/container/intsets/popcnt_gccgo.go b/vendor/golang.org/x/tools/container/intsets/popcnt_gccgo.go
deleted file mode 100644
index 82a8875..0000000
--- a/vendor/golang.org/x/tools/container/intsets/popcnt_gccgo.go
+++ /dev/null
@@ -1,9 +0,0 @@
-// Copyright 2015 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// +build gccgo
-
-package intsets
-
-func popcount(x word) int
diff --git a/vendor/golang.org/x/tools/container/intsets/popcnt_gccgo_c.c b/vendor/golang.org/x/tools/container/intsets/popcnt_gccgo_c.c
deleted file mode 100644
index 08abb32..0000000
--- a/vendor/golang.org/x/tools/container/intsets/popcnt_gccgo_c.c
+++ /dev/null
@@ -1,19 +0,0 @@
-// Copyright 2015 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// +build gccgo
-
-#include <errno.h>
-#include <stdint.h>
-#include <unistd.h>
-
-#define _STRINGIFY2_(x) #x
-#define _STRINGIFY_(x) _STRINGIFY2_(x)
-#define GOSYM_PREFIX _STRINGIFY_(__USER_LABEL_PREFIX__)
-
-extern intptr_t popcount(uintptr_t x) __asm__(GOSYM_PREFIX GOPKGPATH ".popcount");
-
-intptr_t popcount(uintptr_t x) {
- return __builtin_popcountl((unsigned long)(x));
-}
diff --git a/vendor/golang.org/x/tools/container/intsets/popcnt_generic.go b/vendor/golang.org/x/tools/container/intsets/popcnt_generic.go
deleted file mode 100644
index 3985a1d..0000000
--- a/vendor/golang.org/x/tools/container/intsets/popcnt_generic.go
+++ /dev/null
@@ -1,33 +0,0 @@
-// Copyright 2015 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// +build !amd64 appengine
-// +build !gccgo
-
-package intsets
-
-import "runtime"
-
-// We compared three algorithms---Hacker's Delight, table lookup,
-// and AMD64's SSE4.1 hardware POPCNT---on a 2.67GHz Xeon X5550.
-//
-// % GOARCH=amd64 go test -run=NONE -bench=Popcount
-// POPCNT 5.12 ns/op
-// Table 8.53 ns/op
-// HackersDelight 9.96 ns/op
-//
-// % GOARCH=386 go test -run=NONE -bench=Popcount
-// Table 10.4 ns/op
-// HackersDelight 5.23 ns/op
-//
-// (AMD64's ABM1 hardware supports ntz and nlz too,
-// but they aren't critical.)
-
-// popcount returns the population count (number of set bits) of x.
-func popcount(x word) int {
- if runtime.GOARCH == "386" {
- return popcountHD(uint32(x))
- }
- return popcountTable(x)
-}
diff --git a/vendor/golang.org/x/tools/container/intsets/sparse.go b/vendor/golang.org/x/tools/container/intsets/sparse.go
deleted file mode 100644
index 5db01c1..0000000
--- a/vendor/golang.org/x/tools/container/intsets/sparse.go
+++ /dev/null
@@ -1,1091 +0,0 @@
-// Copyright 2014 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// Package intsets provides Sparse, a compact and fast representation
-// for sparse sets of int values.
-//
-// The time complexity of the operations Len, Insert, Remove and Has
-// is in O(n) but in practice those methods are faster and more
-// space-efficient than equivalent operations on sets based on the Go
-// map type. The IsEmpty, Min, Max, Clear and TakeMin operations
-// require constant time.
-//
-package intsets // import "golang.org/x/tools/container/intsets"
-
-// TODO(adonovan):
-// - Add InsertAll(...int), RemoveAll(...int)
-// - Add 'bool changed' results for {Intersection,Difference}With too.
-//
-// TODO(adonovan): implement Dense, a dense bit vector with a similar API.
-// The space usage would be proportional to Max(), not Len(), and the
-// implementation would be based upon big.Int.
-//
-// TODO(adonovan): opt: make UnionWith and Difference faster.
-// These are the hot-spots for go/pointer.
-
-import (
- "bytes"
- "fmt"
-)
-
-// A Sparse is a set of int values.
-// Sparse operations (even queries) are not concurrency-safe.
-//
-// The zero value for Sparse is a valid empty set.
-//
-// Sparse sets must be copied using the Copy method, not by assigning
-// a Sparse value.
-//
-type Sparse struct {
- // An uninitialized Sparse represents an empty set.
- // An empty set may also be represented by
- // root.next == root.prev == &root.
- //
- // The root is always the block with the smallest offset.
- // It can be empty, but only if it is the only block; in that case, offset is
- // MaxInt (which is not a valid offset).
- root block
-}
-
-type word uintptr
-
-const (
- _m = ^word(0)
- bitsPerWord = 8 << (_m>>8&1 + _m>>16&1 + _m>>32&1)
- bitsPerBlock = 256 // optimal value for go/pointer solver performance
- wordsPerBlock = bitsPerBlock / bitsPerWord
-)
-
-// Limit values of implementation-specific int type.
-const (
- MaxInt = int(^uint(0) >> 1)
- MinInt = -MaxInt - 1
-)
-
-// -- block ------------------------------------------------------------
-
-// A set is represented as a circular doubly-linked list of blocks,
-// each containing an offset and a bit array of fixed size
-// bitsPerBlock; the blocks are ordered by increasing offset.
-//
-// The set contains an element x iff the block whose offset is x - (x
-// mod bitsPerBlock) has the bit (x mod bitsPerBlock) set, where mod
-// is the Euclidean remainder.
-//
-// A block may only be empty transiently.
-//
-type block struct {
- offset int // offset mod bitsPerBlock == 0
- bits [wordsPerBlock]word // contains at least one set bit
- next, prev *block // doubly-linked list of blocks
-}
-
-// wordMask returns the word index (in block.bits)
-// and single-bit mask for the block's ith bit.
-func wordMask(i uint) (w uint, mask word) {
- w = i / bitsPerWord
- mask = 1 << (i % bitsPerWord)
- return
-}
-
-// insert sets the block b's ith bit and
-// returns true if it was not already set.
-//
-func (b *block) insert(i uint) bool {
- w, mask := wordMask(i)
- if b.bits[w]&mask == 0 {
- b.bits[w] |= mask
- return true
- }
- return false
-}
-
-// remove clears the block's ith bit and
-// returns true if the bit was previously set.
-// NB: may leave the block empty.
-//
-func (b *block) remove(i uint) bool {
- w, mask := wordMask(i)
- if b.bits[w]&mask != 0 {
- b.bits[w] &^= mask
- return true
- }
- return false
-}
-
-// has reports whether the block's ith bit is set.
-func (b *block) has(i uint) bool {
- w, mask := wordMask(i)
- return b.bits[w]&mask != 0
-}
-
-// empty reports whether b.len()==0, but more efficiently.
-func (b *block) empty() bool {
- for _, w := range b.bits {
- if w != 0 {
- return false
- }
- }
- return true
-}
-
-// len returns the number of set bits in block b.
-func (b *block) len() int {
- var l int
- for _, w := range b.bits {
- l += popcount(w)
- }
- return l
-}
-
-// max returns the maximum element of the block.
-// The block must not be empty.
-func (b *block) max() int {
- bi := b.offset + bitsPerBlock
- // Decrement bi by number of high zeros in last.bits.
- for i := len(b.bits) - 1; i >= 0; i-- {
- if w := b.bits[i]; w != 0 {
- return bi - nlz(w) - 1
- }
- bi -= bitsPerWord
- }
- panic("BUG: empty block")
-}
-
-// min returns the minimum element of the block,
-// and also removes it if take is set.
-// The block must not be initially empty.
-// NB: may leave the block empty.
-func (b *block) min(take bool) int {
- for i, w := range b.bits {
- if w != 0 {
- tz := ntz(w)
- if take {
- b.bits[i] = w &^ (1 << uint(tz))
- }
- return b.offset + int(i*bitsPerWord) + tz
- }
- }
- panic("BUG: empty block")
-}
-
-// lowerBound returns the smallest element of the block that is greater than or
-// equal to the element corresponding to the ith bit. If there is no such
-// element, the second return value is false.
-func (b *block) lowerBound(i uint) (int, bool) {
- w := i / bitsPerWord
- bit := i % bitsPerWord
-
- if val := b.bits[w] >> bit; val != 0 {
- return b.offset + int(i) + ntz(val), true
- }
-
- for w++; w < wordsPerBlock; w++ {
- if val := b.bits[w]; val != 0 {
- return b.offset + int(w*bitsPerWord) + ntz(val), true
- }
- }
-
- return 0, false
-}
-
-// forEach calls f for each element of block b.
-// f must not mutate b's enclosing Sparse.
-func (b *block) forEach(f func(int)) {
- for i, w := range b.bits {
- offset := b.offset + i*bitsPerWord
- for bi := 0; w != 0 && bi < bitsPerWord; bi++ {
- if w&1 != 0 {
- f(offset)
- }
- offset++
- w >>= 1
- }
- }
-}
-
-// offsetAndBitIndex returns the offset of the block that would
-// contain x and the bit index of x within that block.
-//
-func offsetAndBitIndex(x int) (int, uint) {
- mod := x % bitsPerBlock
- if mod < 0 {
- // Euclidean (non-negative) remainder
- mod += bitsPerBlock
- }
- return x - mod, uint(mod)
-}
-
-// -- Sparse --------------------------------------------------------------
-
-// none is a shared, empty, sentinel block that indicates the end of a block
-// list.
-var none block
-
-// Dummy type used to generate an implicit panic. This must be defined at the
-// package level; if it is defined inside a function, it prevents the inlining
-// of that function.
-type to_copy_a_sparse_you_must_call_its_Copy_method struct{}
-
-// init ensures s is properly initialized.
-func (s *Sparse) init() {
- root := &s.root
- if root.next == nil {
- root.offset = MaxInt
- root.next = root
- root.prev = root
- } else if root.next.prev != root {
- // Copying a Sparse x leads to pernicious corruption: the
- // new Sparse y shares the old linked list, but iteration
- // on y will never encounter &y.root so it goes into a
- // loop. Fail fast before this occurs.
- // We don't want to call panic here because it prevents the
- // inlining of this function.
- _ = (interface{}(nil)).(to_copy_a_sparse_you_must_call_its_Copy_method)
- }
-}
-
-func (s *Sparse) first() *block {
- s.init()
- if s.root.offset == MaxInt {
- return &none
- }
- return &s.root
-}
-
-// next returns the next block in the list, or end if b is the last block.
-func (s *Sparse) next(b *block) *block {
- if b.next == &s.root {
- return &none
- }
- return b.next
-}
-
-// prev returns the previous block in the list, or end if b is the first block.
-func (s *Sparse) prev(b *block) *block {
- if b.prev == &s.root {
- return &none
- }
- return b.prev
-}
-
-// IsEmpty reports whether the set s is empty.
-func (s *Sparse) IsEmpty() bool {
- return s.root.next == nil || s.root.offset == MaxInt
-}
-
-// Len returns the number of elements in the set s.
-func (s *Sparse) Len() int {
- var l int
- for b := s.first(); b != &none; b = s.next(b) {
- l += b.len()
- }
- return l
-}
-
-// Max returns the maximum element of the set s, or MinInt if s is empty.
-func (s *Sparse) Max() int {
- if s.IsEmpty() {
- return MinInt
- }
- return s.root.prev.max()
-}
-
-// Min returns the minimum element of the set s, or MaxInt if s is empty.
-func (s *Sparse) Min() int {
- if s.IsEmpty() {
- return MaxInt
- }
- return s.root.min(false)
-}
-
-// LowerBound returns the smallest element >= x, or MaxInt if there is no such
-// element.
-func (s *Sparse) LowerBound(x int) int {
- offset, i := offsetAndBitIndex(x)
- for b := s.first(); b != &none; b = s.next(b) {
- if b.offset > offset {
- return b.min(false)
- }
- if b.offset == offset {
- if y, ok := b.lowerBound(i); ok {
- return y
- }
- }
- }
- return MaxInt
-}
-
-// block returns the block that would contain offset,
-// or nil if s contains no such block.
-// Precondition: offset is a multiple of bitsPerBlock.
-func (s *Sparse) block(offset int) *block {
- for b := s.first(); b != &none && b.offset <= offset; b = s.next(b) {
- if b.offset == offset {
- return b
- }
- }
- return nil
-}
-
-// Insert adds x to the set s, and reports whether the set grew.
-func (s *Sparse) Insert(x int) bool {
- offset, i := offsetAndBitIndex(x)
-
- b := s.first()
- for ; b != &none && b.offset <= offset; b = s.next(b) {
- if b.offset == offset {
- return b.insert(i)
- }
- }
-
- // Insert new block before b.
- new := s.insertBlockBefore(b)
- new.offset = offset
- return new.insert(i)
-}
-
-// removeBlock removes a block and returns the block that followed it (or end if
-// it was the last block).
-func (s *Sparse) removeBlock(b *block) *block {
- if b != &s.root {
- b.prev.next = b.next
- b.next.prev = b.prev
- if b.next == &s.root {
- return &none
- }
- return b.next
- }
-
- first := s.root.next
- if first == &s.root {
- // This was the only block.
- s.Clear()
- return &none
- }
- s.root.offset = first.offset
- s.root.bits = first.bits
- if first.next == &s.root {
- // Single block remaining.
- s.root.next = &s.root
- s.root.prev = &s.root
- } else {
- s.root.next = first.next
- first.next.prev = &s.root
- }
- return &s.root
-}
-
-// Remove removes x from the set s, and reports whether the set shrank.
-func (s *Sparse) Remove(x int) bool {
- offset, i := offsetAndBitIndex(x)
- if b := s.block(offset); b != nil {
- if !b.remove(i) {
- return false
- }
- if b.empty() {
- s.removeBlock(b)
- }
- return true
- }
- return false
-}
-
-// Clear removes all elements from the set s.
-func (s *Sparse) Clear() {
- s.root = block{
- offset: MaxInt,
- next: &s.root,
- prev: &s.root,
- }
-}
-
-// If set s is non-empty, TakeMin sets *p to the minimum element of
-// the set s, removes that element from the set and returns true.
-// Otherwise, it returns false and *p is undefined.
-//
-// This method may be used for iteration over a worklist like so:
-//
-// var x int
-// for worklist.TakeMin(&x) { use(x) }
-//
-func (s *Sparse) TakeMin(p *int) bool {
- if s.IsEmpty() {
- return false
- }
- *p = s.root.min(true)
- if s.root.empty() {
- s.removeBlock(&s.root)
- }
- return true
-}
-
-// Has reports whether x is an element of the set s.
-func (s *Sparse) Has(x int) bool {
- offset, i := offsetAndBitIndex(x)
- if b := s.block(offset); b != nil {
- return b.has(i)
- }
- return false
-}
-
-// forEach applies function f to each element of the set s in order.
-//
-// f must not mutate s. Consequently, forEach is not safe to expose
-// to clients. In any case, using "range s.AppendTo()" allows more
-// natural control flow with continue/break/return.
-//
-func (s *Sparse) forEach(f func(int)) {
- for b := s.first(); b != &none; b = s.next(b) {
- b.forEach(f)
- }
-}
-
-// Copy sets s to the value of x.
-func (s *Sparse) Copy(x *Sparse) {
- if s == x {
- return
- }
-
- xb := x.first()
- sb := s.first()
- for xb != &none {
- if sb == &none {
- sb = s.insertBlockBefore(sb)
- }
- sb.offset = xb.offset
- sb.bits = xb.bits
- xb = x.next(xb)
- sb = s.next(sb)
- }
- s.discardTail(sb)
-}
-
-// insertBlockBefore returns a new block, inserting it before next.
-// If next is the root, the root is replaced. If next is end, the block is
-// inserted at the end.
-func (s *Sparse) insertBlockBefore(next *block) *block {
- if s.IsEmpty() {
- if next != &none {
- panic("BUG: passed block with empty set")
- }
- return &s.root
- }
-
- if next == &s.root {
- // Special case: we need to create a new block that will become the root
- // block.The old root block becomes the second block.
- second := s.root
- s.root = block{
- next: &second,
- }
- if second.next == &s.root {
- s.root.prev = &second
- } else {
- s.root.prev = second.prev
- second.next.prev = &second
- second.prev = &s.root
- }
- return &s.root
- }
- if next == &none {
- // Insert before root.
- next = &s.root
- }
- b := new(block)
- b.next = next
- b.prev = next.prev
- b.prev.next = b
- next.prev = b
- return b
-}
-
-// discardTail removes block b and all its successors from s.
-func (s *Sparse) discardTail(b *block) {
- if b != &none {
- if b == &s.root {
- s.Clear()
- } else {
- b.prev.next = &s.root
- s.root.prev = b.prev
- }
- }
-}
-
-// IntersectionWith sets s to the intersection s ∩ x.
-func (s *Sparse) IntersectionWith(x *Sparse) {
- if s == x {
- return
- }
-
- xb := x.first()
- sb := s.first()
- for xb != &none && sb != &none {
- switch {
- case xb.offset < sb.offset:
- xb = x.next(xb)
-
- case xb.offset > sb.offset:
- sb = s.removeBlock(sb)
-
- default:
- var sum word
- for i := range sb.bits {
- r := xb.bits[i] & sb.bits[i]
- sb.bits[i] = r
- sum |= r
- }
- if sum != 0 {
- sb = s.next(sb)
- } else {
- // sb will be overwritten or removed
- }
-
- xb = x.next(xb)
- }
- }
-
- s.discardTail(sb)
-}
-
-// Intersection sets s to the intersection x ∩ y.
-func (s *Sparse) Intersection(x, y *Sparse) {
- switch {
- case s == x:
- s.IntersectionWith(y)
- return
- case s == y:
- s.IntersectionWith(x)
- return
- case x == y:
- s.Copy(x)
- return
- }
-
- xb := x.first()
- yb := y.first()
- sb := s.first()
- for xb != &none && yb != &none {
- switch {
- case xb.offset < yb.offset:
- xb = x.next(xb)
- continue
- case xb.offset > yb.offset:
- yb = y.next(yb)
- continue
- }
-
- if sb == &none {
- sb = s.insertBlockBefore(sb)
- }
- sb.offset = xb.offset
-
- var sum word
- for i := range sb.bits {
- r := xb.bits[i] & yb.bits[i]
- sb.bits[i] = r
- sum |= r
- }
- if sum != 0 {
- sb = s.next(sb)
- } else {
- // sb will be overwritten or removed
- }
-
- xb = x.next(xb)
- yb = y.next(yb)
- }
-
- s.discardTail(sb)
-}
-
-// Intersects reports whether s ∩ x ≠ ∅.
-func (s *Sparse) Intersects(x *Sparse) bool {
- sb := s.first()
- xb := x.first()
- for sb != &none && xb != &none {
- switch {
- case xb.offset < sb.offset:
- xb = x.next(xb)
- case xb.offset > sb.offset:
- sb = s.next(sb)
- default:
- for i := range sb.bits {
- if sb.bits[i]&xb.bits[i] != 0 {
- return true
- }
- }
- sb = s.next(sb)
- xb = x.next(xb)
- }
- }
- return false
-}
-
-// UnionWith sets s to the union s ∪ x, and reports whether s grew.
-func (s *Sparse) UnionWith(x *Sparse) bool {
- if s == x {
- return false
- }
-
- var changed bool
- xb := x.first()
- sb := s.first()
- for xb != &none {
- if sb != &none && sb.offset == xb.offset {
- for i := range xb.bits {
- if sb.bits[i] != xb.bits[i] {
- sb.bits[i] |= xb.bits[i]
- changed = true
- }
- }
- xb = x.next(xb)
- } else if sb == &none || sb.offset > xb.offset {
- sb = s.insertBlockBefore(sb)
- sb.offset = xb.offset
- sb.bits = xb.bits
- changed = true
-
- xb = x.next(xb)
- }
- sb = s.next(sb)
- }
- return changed
-}
-
-// Union sets s to the union x ∪ y.
-func (s *Sparse) Union(x, y *Sparse) {
- switch {
- case x == y:
- s.Copy(x)
- return
- case s == x:
- s.UnionWith(y)
- return
- case s == y:
- s.UnionWith(x)
- return
- }
-
- xb := x.first()
- yb := y.first()
- sb := s.first()
- for xb != &none || yb != &none {
- if sb == &none {
- sb = s.insertBlockBefore(sb)
- }
- switch {
- case yb == &none || (xb != &none && xb.offset < yb.offset):
- sb.offset = xb.offset
- sb.bits = xb.bits
- xb = x.next(xb)
-
- case xb == &none || (yb != &none && yb.offset < xb.offset):
- sb.offset = yb.offset
- sb.bits = yb.bits
- yb = y.next(yb)
-
- default:
- sb.offset = xb.offset
- for i := range xb.bits {
- sb.bits[i] = xb.bits[i] | yb.bits[i]
- }
- xb = x.next(xb)
- yb = y.next(yb)
- }
- sb = s.next(sb)
- }
-
- s.discardTail(sb)
-}
-
-// DifferenceWith sets s to the difference s ∖ x.
-func (s *Sparse) DifferenceWith(x *Sparse) {
- if s == x {
- s.Clear()
- return
- }
-
- xb := x.first()
- sb := s.first()
- for xb != &none && sb != &none {
- switch {
- case xb.offset > sb.offset:
- sb = s.next(sb)
-
- case xb.offset < sb.offset:
- xb = x.next(xb)
-
- default:
- var sum word
- for i := range sb.bits {
- r := sb.bits[i] & ^xb.bits[i]
- sb.bits[i] = r
- sum |= r
- }
- if sum == 0 {
- sb = s.removeBlock(sb)
- } else {
- sb = s.next(sb)
- }
- xb = x.next(xb)
- }
- }
-}
-
-// Difference sets s to the difference x ∖ y.
-func (s *Sparse) Difference(x, y *Sparse) {
- switch {
- case x == y:
- s.Clear()
- return
- case s == x:
- s.DifferenceWith(y)
- return
- case s == y:
- var y2 Sparse
- y2.Copy(y)
- s.Difference(x, &y2)
- return
- }
-
- xb := x.first()
- yb := y.first()
- sb := s.first()
- for xb != &none && yb != &none {
- if xb.offset > yb.offset {
- // y has block, x has &none
- yb = y.next(yb)
- continue
- }
-
- if sb == &none {
- sb = s.insertBlockBefore(sb)
- }
- sb.offset = xb.offset
-
- switch {
- case xb.offset < yb.offset:
- // x has block, y has &none
- sb.bits = xb.bits
-
- sb = s.next(sb)
-
- default:
- // x and y have corresponding blocks
- var sum word
- for i := range sb.bits {
- r := xb.bits[i] & ^yb.bits[i]
- sb.bits[i] = r
- sum |= r
- }
- if sum != 0 {
- sb = s.next(sb)
- } else {
- // sb will be overwritten or removed
- }
-
- yb = y.next(yb)
- }
- xb = x.next(xb)
- }
-
- for xb != &none {
- if sb == &none {
- sb = s.insertBlockBefore(sb)
- }
- sb.offset = xb.offset
- sb.bits = xb.bits
- sb = s.next(sb)
-
- xb = x.next(xb)
- }
-
- s.discardTail(sb)
-}
-
-// SymmetricDifferenceWith sets s to the symmetric difference s ∆ x.
-func (s *Sparse) SymmetricDifferenceWith(x *Sparse) {
- if s == x {
- s.Clear()
- return
- }
-
- sb := s.first()
- xb := x.first()
- for xb != &none && sb != &none {
- switch {
- case sb.offset < xb.offset:
- sb = s.next(sb)
- case xb.offset < sb.offset:
- nb := s.insertBlockBefore(sb)
- nb.offset = xb.offset
- nb.bits = xb.bits
- xb = x.next(xb)
- default:
- var sum word
- for i := range sb.bits {
- r := sb.bits[i] ^ xb.bits[i]
- sb.bits[i] = r
- sum |= r
- }
- if sum == 0 {
- sb = s.removeBlock(sb)
- } else {
- sb = s.next(sb)
- }
- xb = x.next(xb)
- }
- }
-
- for xb != &none { // append the tail of x to s
- sb = s.insertBlockBefore(sb)
- sb.offset = xb.offset
- sb.bits = xb.bits
- sb = s.next(sb)
- xb = x.next(xb)
- }
-}
-
-// SymmetricDifference sets s to the symmetric difference x ∆ y.
-func (s *Sparse) SymmetricDifference(x, y *Sparse) {
- switch {
- case x == y:
- s.Clear()
- return
- case s == x:
- s.SymmetricDifferenceWith(y)
- return
- case s == y:
- s.SymmetricDifferenceWith(x)
- return
- }
-
- sb := s.first()
- xb := x.first()
- yb := y.first()
- for xb != &none && yb != &none {
- if sb == &none {
- sb = s.insertBlockBefore(sb)
- }
- switch {
- case yb.offset < xb.offset:
- sb.offset = yb.offset
- sb.bits = yb.bits
- sb = s.next(sb)
- yb = y.next(yb)
- case xb.offset < yb.offset:
- sb.offset = xb.offset
- sb.bits = xb.bits
- sb = s.next(sb)
- xb = x.next(xb)
- default:
- var sum word
- for i := range sb.bits {
- r := xb.bits[i] ^ yb.bits[i]
- sb.bits[i] = r
- sum |= r
- }
- if sum != 0 {
- sb.offset = xb.offset
- sb = s.next(sb)
- }
- xb = x.next(xb)
- yb = y.next(yb)
- }
- }
-
- for xb != &none { // append the tail of x to s
- if sb == &none {
- sb = s.insertBlockBefore(sb)
- }
- sb.offset = xb.offset
- sb.bits = xb.bits
- sb = s.next(sb)
- xb = x.next(xb)
- }
-
- for yb != &none { // append the tail of y to s
- if sb == &none {
- sb = s.insertBlockBefore(sb)
- }
- sb.offset = yb.offset
- sb.bits = yb.bits
- sb = s.next(sb)
- yb = y.next(yb)
- }
-
- s.discardTail(sb)
-}
-
-// SubsetOf reports whether s ∖ x = ∅.
-func (s *Sparse) SubsetOf(x *Sparse) bool {
- if s == x {
- return true
- }
-
- sb := s.first()
- xb := x.first()
- for sb != &none {
- switch {
- case xb == &none || xb.offset > sb.offset:
- return false
- case xb.offset < sb.offset:
- xb = x.next(xb)
- default:
- for i := range sb.bits {
- if sb.bits[i]&^xb.bits[i] != 0 {
- return false
- }
- }
- sb = s.next(sb)
- xb = x.next(xb)
- }
- }
- return true
-}
-
-// Equals reports whether the sets s and t have the same elements.
-func (s *Sparse) Equals(t *Sparse) bool {
- if s == t {
- return true
- }
- sb := s.first()
- tb := t.first()
- for {
- switch {
- case sb == &none && tb == &none:
- return true
- case sb == &none || tb == &none:
- return false
- case sb.offset != tb.offset:
- return false
- case sb.bits != tb.bits:
- return false
- }
-
- sb = s.next(sb)
- tb = t.next(tb)
- }
-}
-
-// String returns a human-readable description of the set s.
-func (s *Sparse) String() string {
- var buf bytes.Buffer
- buf.WriteByte('{')
- s.forEach(func(x int) {
- if buf.Len() > 1 {
- buf.WriteByte(' ')
- }
- fmt.Fprintf(&buf, "%d", x)
- })
- buf.WriteByte('}')
- return buf.String()
-}
-
-// BitString returns the set as a string of 1s and 0s denoting the sum
-// of the i'th powers of 2, for each i in s. A radix point, always
-// preceded by a digit, appears if the sum is non-integral.
-//
-// Examples:
-// {}.BitString() = "0"
-// {4,5}.BitString() = "110000"
-// {-3}.BitString() = "0.001"
-// {-3,0,4,5}.BitString() = "110001.001"
-//
-func (s *Sparse) BitString() string {
- if s.IsEmpty() {
- return "0"
- }
-
- min, max := s.Min(), s.Max()
- var nbytes int
- if max > 0 {
- nbytes = max
- }
- nbytes++ // zero bit
- radix := nbytes
- if min < 0 {
- nbytes += len(".") - min
- }
-
- b := make([]byte, nbytes)
- for i := range b {
- b[i] = '0'
- }
- if radix < nbytes {
- b[radix] = '.'
- }
- s.forEach(func(x int) {
- if x >= 0 {
- x += len(".")
- }
- b[radix-x] = '1'
- })
- return string(b)
-}
-
-// GoString returns a string showing the internal representation of
-// the set s.
-//
-func (s *Sparse) GoString() string {
- var buf bytes.Buffer
- for b := s.first(); b != &none; b = s.next(b) {
- fmt.Fprintf(&buf, "block %p {offset=%d next=%p prev=%p",
- b, b.offset, b.next, b.prev)
- for _, w := range b.bits {
- fmt.Fprintf(&buf, " 0%016x", w)
- }
- fmt.Fprintf(&buf, "}\n")
- }
- return buf.String()
-}
-
-// AppendTo returns the result of appending the elements of s to slice
-// in order.
-func (s *Sparse) AppendTo(slice []int) []int {
- s.forEach(func(x int) {
- slice = append(slice, x)
- })
- return slice
-}
-
-// -- Testing/debugging ------------------------------------------------
-
-// check returns an error if the representation invariants of s are violated.
-func (s *Sparse) check() error {
- s.init()
- if s.root.empty() {
- // An empty set must have only the root block with offset MaxInt.
- if s.root.next != &s.root {
- return fmt.Errorf("multiple blocks with empty root block")
- }
- if s.root.offset != MaxInt {
- return fmt.Errorf("empty set has offset %d, should be MaxInt", s.root.offset)
- }
- return nil
- }
- for b := s.first(); ; b = s.next(b) {
- if b.offset%bitsPerBlock != 0 {
- return fmt.Errorf("bad offset modulo: %d", b.offset)
- }
- if b.empty() {
- return fmt.Errorf("empty block")
- }
- if b.prev.next != b {
- return fmt.Errorf("bad prev.next link")
- }
- if b.next.prev != b {
- return fmt.Errorf("bad next.prev link")
- }
- if b.next == &s.root {
- break
- }
- if b.offset >= b.next.offset {
- return fmt.Errorf("bad offset order: b.offset=%d, b.next.offset=%d",
- b.offset, b.next.offset)
- }
- }
- return nil
-}
diff --git a/vendor/golang.org/x/tools/container/intsets/util.go b/vendor/golang.org/x/tools/container/intsets/util.go
deleted file mode 100644
index dd1db86..0000000
--- a/vendor/golang.org/x/tools/container/intsets/util.go
+++ /dev/null
@@ -1,84 +0,0 @@
-// Copyright 2013 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package intsets
-
-// From Hacker's Delight, fig 5.2.
-func popcountHD(x uint32) int {
- x -= (x >> 1) & 0x55555555
- x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
- x = (x + (x >> 4)) & 0x0f0f0f0f
- x = x + (x >> 8)
- x = x + (x >> 16)
- return int(x & 0x0000003f)
-}
-
-var a [1 << 8]byte
-
-func init() {
- for i := range a {
- var n byte
- for x := i; x != 0; x >>= 1 {
- if x&1 != 0 {
- n++
- }
- }
- a[i] = n
- }
-}
-
-func popcountTable(x word) int {
- return int(a[byte(x>>(0*8))] +
- a[byte(x>>(1*8))] +
- a[byte(x>>(2*8))] +
- a[byte(x>>(3*8))] +
- a[byte(x>>(4*8))] +
- a[byte(x>>(5*8))] +
- a[byte(x>>(6*8))] +
- a[byte(x>>(7*8))])
-}
-
-// nlz returns the number of leading zeros of x.
-// From Hacker's Delight, fig 5.11.
-func nlz(x word) int {
- x |= (x >> 1)
- x |= (x >> 2)
- x |= (x >> 4)
- x |= (x >> 8)
- x |= (x >> 16)
- x |= (x >> 32)
- return popcount(^x)
-}
-
-// ntz returns the number of trailing zeros of x.
-// From Hacker's Delight, fig 5.13.
-func ntz(x word) int {
- if x == 0 {
- return bitsPerWord
- }
- n := 1
- if bitsPerWord == 64 {
- if (x & 0xffffffff) == 0 {
- n = n + 32
- x = x >> 32
- }
- }
- if (x & 0x0000ffff) == 0 {
- n = n + 16
- x = x >> 16
- }
- if (x & 0x000000ff) == 0 {
- n = n + 8
- x = x >> 8
- }
- if (x & 0x0000000f) == 0 {
- n = n + 4
- x = x >> 4
- }
- if (x & 0x00000003) == 0 {
- n = n + 2
- x = x >> 2
- }
- return n - int(x&1)
-}
diff --git a/vendor/golang.org/x/tools/go.mod b/vendor/golang.org/x/tools/go.mod
deleted file mode 100644
index 0984a83..0000000
--- a/vendor/golang.org/x/tools/go.mod
+++ /dev/null
@@ -1,8 +0,0 @@
-module golang.org/x/tools
-
-go 1.11
-
-require (
- golang.org/x/net v0.0.0-20190311183353-d8887717615a
- golang.org/x/sync v0.0.0-20190423024810-112230192c58
-)
