func exprListsMatch(a, b []string) bool {
	var visited = make([]bool, len(b))
	for _, va := range a {
		found := false
		for j, vb := range b {
			if visited[j] {
				continue
			}
			if va == vb {
				visited[j] = true
				found = true
				break
			}
		}
		if !found {
			return false
		}
	}
	return true
}
exprListsMatch returns whether any subset of a is the entirety of b.
package sql
import (
	"io"
	"strings"
	"sync"
	"github.com/src-d/go-mysql-server/internal/similartext"
	"github.com/sirupsen/logrus"
	"gopkg.in/src-d/go-errors.v1"
)
const IndexBatchSize = uint64(10000)
const ChecksumKey = "checksum"
type Checksumable interface {
	Checksum() (string, error)
}
type PartitionIndexKeyValueIter interface {
	Next() (Partition, IndexKeyValueIter, error)
	io.Closer
}
type IndexKeyValueIter interface {
	Next() ([]interface{}, []byte, error)
	io.Closer
}
type IndexValueIter interface {
	Next() ([]byte, error)
	io.Closer
}
type Index interface {
	Get(key ...interface{}) (IndexLookup, error)
	Has(partition Partition, key ...interface{}) (bool, error)
	ID() string
	Database() string
	Table() string
	Expressions() []string
	Driver() string
}
type AscendIndex interface {
	AscendGreaterOrEqual(keys ...interface{}) (IndexLookup, error)
	AscendLessThan(keys ...interface{}) (IndexLookup, error)
	AscendRange(greaterOrEqual, lessThan []interface{}) (IndexLookup, error)
}
type DescendIndex interface {
	DescendGreater(keys ...interface{}) (IndexLookup, error)
	DescendLessOrEqual(keys ...interface{}) (IndexLookup, error)
	DescendRange(lessOrEqual, greaterThan []interface{}) (IndexLookup, error)
}
type NegateIndex interface {
	Not(keys ...interface{}) (IndexLookup, error)
}
type IndexLookup interface {
	Values(Partition) (IndexValueIter, error)
	Indexes() []string
}
type SetOperations interface {
	Intersection(...IndexLookup) IndexLookup
	Union(...IndexLookup) IndexLookup
	Difference(...IndexLookup) IndexLookup
}
type Mergeable interface {
	IsMergeable(IndexLookup) bool
}
type IndexDriver interface {
	ID() string
	Create(db, table, id string, expressions []Expression, config map[string]string) (Index, error)
	LoadAll(db, table string) ([]Index, error)
	Save(*Context, Index, PartitionIndexKeyValueIter) error
	Delete(Index, PartitionIter) error
}
type indexKey struct {
	db, id string
}
type IndexRegistry struct {
	Root string
	mut        sync.RWMutex
	indexes    map[indexKey]Index
	indexOrder []indexKey
	statuses   map[indexKey]IndexStatus
	driversMut sync.RWMutex
	drivers    map[string]IndexDriver
	rcmut            sync.RWMutex
	refCounts        map[indexKey]int
	deleteIndexQueue map[indexKey]chan<- struct{}
}
func NewIndexRegistry() *IndexRegistry {
	return &IndexRegistry{
		indexes:          make(map[indexKey]Index),
		statuses:         make(map[indexKey]IndexStatus),
		drivers:          make(map[string]IndexDriver),
		refCounts:        make(map[indexKey]int),
		deleteIndexQueue: make(map[indexKey]chan<- struct{}),
	}
}
func (r *IndexRegistry) IndexDriver(id string) IndexDriver {
	r.driversMut.RLock()
	defer r.driversMut.RUnlock()
	return r.drivers[id]
}
func (r *IndexRegistry) DefaultIndexDriver() IndexDriver {
	r.driversMut.RLock()
	defer r.driversMut.RUnlock()
	if len(r.drivers) == 1 {
		for _, d := range r.drivers {
			return d
		}
	}
	return nil
}
func (r *IndexRegistry) RegisterIndexDriver(driver IndexDriver) {
	r.driversMut.Lock()
	defer r.driversMut.Unlock()
	r.drivers[driver.ID()] = driver
}
func (r *IndexRegistry) LoadIndexes(dbs Databases) error {
	r.driversMut.RLock()
	defer r.driversMut.RUnlock()
	r.mut.Lock()
	defer r.mut.Unlock()
	for _, driver := range r.drivers {
		for _, db := range dbs {
			for _, t := range db.Tables() {
				indexes, err := driver.LoadAll(db.Name(), t.Name())
				if err != nil {
					return err
				}
				var checksum string
				if c, ok := t.(Checksumable); ok && len(indexes) != 0 {
					checksum, err = c.Checksum()
					if err != nil {
						return err
					}
				}
				for _, idx := range indexes {
					k := indexKey{db.Name(), idx.ID()}
					r.indexes[k] = idx
					r.indexOrder = append(r.indexOrder, k)
					var idxChecksum string
					if c, ok := idx.(Checksumable); ok {
						idxChecksum, err = c.Checksum()
						if err != nil {
							return err
						}
					}
					if checksum == "" || checksum == idxChecksum {
						r.statuses[k] = IndexReady
					} else {
						logrus.Warnf(
							"index %q is outdated and will not be used, you can remove it using `DROP INDEX %s ON %s`",
							idx.ID(),
							idx.ID(),
							idx.Table(),
						)
						r.MarkOutdated(idx)
					}
				}
			}
		}
	}
	return nil
}
func (r *IndexRegistry) MarkOutdated(idx Index) {
	r.statuses[indexKey{idx.Database(), idx.ID()}] = IndexOutdated
}
func (r *IndexRegistry) retainIndex(db, id string) {
	r.rcmut.Lock()
	defer r.rcmut.Unlock()
	key := indexKey{db, id}
	r.refCounts[key]++
}
func (r *IndexRegistry) CanUseIndex(idx Index) bool {
	r.mut.RLock()
	defer r.mut.RUnlock()
	return r.canUseIndex(idx)
}
func (r *IndexRegistry) CanRemoveIndex(idx Index) bool {
	if idx == nil {
		return false
	}
	r.mut.RLock()
	defer r.mut.RUnlock()
	status := r.statuses[indexKey{idx.Database(), idx.ID()}]
	return status == IndexReady || status == IndexOutdated
}
func (r *IndexRegistry) canUseIndex(idx Index) bool {
	if idx == nil {
		return false
	}
	return r.statuses[indexKey{idx.Database(), idx.ID()}].IsUsable()
}
func (r *IndexRegistry) setStatus(idx Index, status IndexStatus) {
	r.statuses[indexKey{idx.Database(), idx.ID()}] = status
}
func (r *IndexRegistry) ReleaseIndex(idx Index) {
	r.rcmut.Lock()
	defer r.rcmut.Unlock()
	key := indexKey{idx.Database(), idx.ID()}
	r.refCounts[key]--
	if r.refCounts[key] > 0 {
		return
	}
	if ch, ok := r.deleteIndexQueue[key]; ok {
		close(ch)
		delete(r.deleteIndexQueue, key)
	}
}
func (r *IndexRegistry) Index(db, id string) Index {
	r.mut.RLock()
	defer r.mut.RUnlock()
	r.retainIndex(db, id)
	return r.indexes[indexKey{db, strings.ToLower(id)}]
}
func (r *IndexRegistry) IndexesByTable(db, table string) []Index {
	r.mut.RLock()
	defer r.mut.RUnlock()
	var indexes []Index
	for _, key := range r.indexOrder {
		idx := r.indexes[key]
		if idx.Database() == db && idx.Table() == table {
			indexes = append(indexes, idx)
			r.retainIndex(db, idx.ID())
		}
	}
	return indexes
}
func (r *IndexRegistry) IndexByExpression(db string, expr ...Expression) Index {
	r.mut.RLock()
	defer r.mut.RUnlock()
	expressions := make([]string, len(expr))
	for i, e := range expr {
		expressions[i] = e.String()
	}
	for _, k := range r.indexOrder {
		idx := r.indexes[k]
		if !r.canUseIndex(idx) {
			continue
		}
		if idx.Database() == db {
			if exprListsMatch(idx.Expressions(), expressions) {
				r.retainIndex(db, idx.ID())
				return idx
			}
		}
	}
	return nil
}
func (r *IndexRegistry) ExpressionsWithIndexes(
	db string,
	exprs ...Expression,
) [][]Expression {
	r.mut.RLock()
	defer r.mut.RUnlock()
	var results [][]Expression
Indexes:
	for _, idx := range r.indexes {
		if !r.canUseIndex(idx) {
			continue
		}
		if ln := len(idx.Expressions()); ln <= len(exprs) && ln > 1 {
			var used = make(map[int]struct{})
			var matched []Expression
			for _, ie := range idx.Expressions() {
				var found bool
				for i, e := range exprs {
					if _, ok := used[i]; ok {
						continue
					}
					if ie == e.String() {
						used[i] = struct{}{}
						found = true
						matched = append(matched, e)
						break
					}
				}
				if !found {
					continue Indexes
				}
			}
			results = append(results, matched)
		}
	}
	return results
}
var (
	ErrIndexIDAlreadyRegistered = errors.NewKind("an index with id %q has already been registered")
	ErrIndexExpressionAlreadyRegistered = errors.NewKind("there is already an index registered for the expressions: %s")
	ErrIndexNotFound = errors.NewKind("index %q	was not found")
	ErrIndexDeleteInvalidStatus = errors.NewKind("can't delete index %q because it's not ready for removal")
)
func (r *IndexRegistry) validateIndexToAdd(idx Index) error {
	r.mut.RLock()
	defer r.mut.RUnlock()
	for _, i := range r.indexes {
		if i.Database() != idx.Database() {
			continue
		}
		if i.ID() == idx.ID() {
			return ErrIndexIDAlreadyRegistered.New(idx.ID())
		}
		if exprListsEqual(i.Expressions(), idx.Expressions()) {
			return ErrIndexExpressionAlreadyRegistered.New(
				strings.Join(idx.Expressions(), ", "),
			)
		}
	}
	return nil
}