1	/*
     2	Copyright 2013 The Perkeep Authors
     3	
     4	Licensed under the Apache License, Version 2.0 (the "License");
     5	you may not use this file except in compliance with the License.
     6	You may obtain a copy of the License at
     7	
     8	     http://www.apache.org/licenses/LICENSE-2.0
     9	
    10	Unless required by applicable law or agreed to in writing, software
    11	distributed under the License is distributed on an "AS IS" BASIS,
    12	WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13	See the License for the specific language governing permissions and
    14	limitations under the License.
    15	*/
    16	
    17	// Package sorted provides a KeyValue interface and constructor registry.
    18	package sorted // import "perkeep.org/pkg/sorted"
    19	
    20	import (
    21		"errors"
    22		"fmt"
    23	
    24		"go4.org/jsonconfig"
    25	)
    26	
    27	const (
    28		MaxKeySize   = 767   // Maximum size, in bytes, for a key in any store implementing KeyValue.
    29		MaxValueSize = 63000 // Maximum size, in bytes, for a value in any store implementing KeyValue. MaxKeySize and MaxValueSize values originate from InnoDB and MySQL limitations.
    30	)
    31	
    32	const DefaultKVFileType = "leveldb"
    33	
    34	var (
    35		ErrNotFound      = errors.New("sorted: key not found")
    36		ErrKeyTooLarge   = fmt.Errorf("sorted: key size is over %v", MaxKeySize)
    37		ErrValueTooLarge = fmt.Errorf("sorted: value size is over %v", MaxValueSize)
    38	)
    39	
    40	// KeyValue is a sorted, enumerable key-value interface supporting
    41	// batch mutations.
    42	type KeyValue interface {
    43		// Get gets the value for the given key. It returns ErrNotFound if the DB
    44		// does not contain the key.
    45		Get(key string) (string, error)
    46	
    47		Set(key, value string) error
    48	
    49		// Delete deletes keys. Deleting a non-existent key does not return an error.
    50		Delete(key string) error
    51	
    52		BeginBatch() BatchMutation
    53		CommitBatch(b BatchMutation) error
    54	
    55		// Find returns an iterator positioned before the first key/value pair
    56		// whose key is 'greater than or equal to' the given key. There may be no
    57		// such pair, in which case the iterator will return false on Next.
    58		//
    59		// The optional end value specifies the exclusive upper
    60		// bound. If the empty string, the iterator returns keys
    61		// where "key >= start".
    62		// If non-empty, the iterator returns keys where
    63		// "key >= start && key < endHint".
    64		//
    65		// Any error encountered will be implicitly returned via the iterator. An
    66		// error-iterator will yield no key/value pairs and closing that iterator
    67		// will return that error.
    68		Find(start, end string) Iterator
    69	
    70		// Close is a polite way for the server to shut down the storage.
    71		// Implementations should never lose data after a Set, Delete,
    72		// or CommmitBatch, though.
    73		Close() error
    74	}
    75	
    76	// TransactionalReader is an optional interface that may be implemented by storage
    77	// implementations. It may be implemented when a storage backend supports multiple
    78	// atomic reads.
    79	type TransactionalReader interface {
    80		KeyValue
    81	
    82		// BeginReadTx begins a read-only transaction.
    83		BeginReadTx() ReadTransaction
    84	}
    85	
    86	// Wiper is an optional interface that may be implemented by storage
    87	// implementations.
    88	type Wiper interface {
    89		KeyValue
    90	
    91		// Wipe removes all key/value pairs, and resets the storage to a blank state.
    92		// For a given storage, when NewKeyValue returns a NeedWipeError, Wipe
    93		// should be implemented so that it fixes the returned KeyValue.
    94		Wipe() error
    95	}
    96	
    97	// NeedWipeError is returned by NewKeyValue when the returned KeyValue is not
    98	// usable until Wipe has been called on it.
    99	type NeedWipeError struct {
   100		Msg string
   101	}
   102	
   103	func (e NeedWipeError) Error() string {
   104		return e.Msg
   105	}
   106	
   107	// Iterator iterates over an index KeyValue's key/value pairs in key order.
   108	//
   109	// An iterator must be closed after use, but it is not necessary to read an
   110	// iterator until exhaustion.
   111	//
   112	// An iterator is not necessarily goroutine-safe, but it is safe to use
   113	// multiple iterators concurrently, with each in a dedicated goroutine.
   114	type Iterator interface {
   115		// Next moves the iterator to the next key/value pair.
   116		// It returns false when the iterator is exhausted.
   117		Next() bool
   118	
   119		// Key returns the key of the current key/value pair.
   120		// Only valid after a call to Next returns true.
   121		Key() string
   122	
   123		// KeyBytes returns the key as bytes. The returned bytes
   124		// should not be written and are invalid after the next call
   125		// to Next or Close.
   126		// TODO(bradfitz): rename this and change it to return a
   127		// mem.RO instead?
   128		KeyBytes() []byte
   129	
   130		// Value returns the value of the current key/value pair.
   131		// Only valid after a call to Next returns true.
   132		Value() string
   133	
   134		// ValueBytes returns the value as bytes. The returned bytes
   135		// should not be written and are invalid after the next call
   136		// to Next or Close.
   137		// TODO(bradfitz): rename this and change it to return a
   138		// mem.RO instead?
   139		ValueBytes() []byte
   140	
   141		// Close closes the iterator and returns any accumulated error. Exhausting
   142		// all the key/value pairs in a table is not considered to be an error.
   143		// It is valid to call Close multiple times. Other methods should not be
   144		// called after the iterator has been closed.
   145		Close() error
   146	}
   147	
   148	// ReadTransaction is a read-only transaction on a KeyValue. It admits the same read
   149	// operations as the KeyValue itself, but writes that occur after the transaction is
   150	// created are not observed.
   151	//
   152	// Users should close the transaction as soon as it as no longer needed, as failing
   153	// to do so can tie up resources.
   154	type ReadTransaction interface {
   155		Get(key string) (string, error)
   156		Find(start, end string) Iterator
   157	
   158		// End the transaction.
   159		Close() error
   160	}
   161	
   162	type BatchMutation interface {
   163		Set(key, value string)
   164		Delete(key string)
   165	}
   166	
   167	type Mutation interface {
   168		Key() string
   169		Value() string
   170		IsDelete() bool
   171	}
   172	
   173	type mutation struct {
   174		key    string
   175		value  string // used if !delete
   176		delete bool   // if to be deleted
   177	}
   178	
   179	func (m mutation) Key() string {
   180		return m.key
   181	}
   182	
   183	func (m mutation) Value() string {
   184		return m.value
   185	}
   186	
   187	func (m mutation) IsDelete() bool {
   188		return m.delete
   189	}
   190	
   191	func NewBatchMutation() BatchMutation {
   192		return &batch{}
   193	}
   194	
   195	type batch struct {
   196		m []Mutation
   197	}
   198	
   199	func (b *batch) Mutations() []Mutation {
   200		return b.m
   201	}
   202	
   203	func (b *batch) Delete(key string) {
   204		b.m = append(b.m, mutation{key: key, delete: true})
   205	}
   206	
   207	func (b *batch) Set(key, value string) {
   208		b.m = append(b.m, mutation{key: key, value: value})
   209	}
   210	
   211	var (
   212		ctors = make(map[string]func(jsonconfig.Obj) (KeyValue, error))
   213	)
   214	
   215	func RegisterKeyValue(typ string, fn func(jsonconfig.Obj) (KeyValue, error)) {
   216		if typ == "" || fn == nil {
   217			panic("zero type or func")
   218		}
   219		if _, dup := ctors[typ]; dup {
   220			panic("duplication registration of type " + typ)
   221		}
   222		ctors[typ] = fn
   223	}
   224	
   225	// NewKeyValue returns a KeyValue as defined by cfg.
   226	// It returns an error of type NeedWipeError when the returned KeyValue should
   227	// be fixed with Wipe.
   228	func NewKeyValue(cfg jsonconfig.Obj) (KeyValue, error) {
   229		var s KeyValue
   230		var err error
   231		typ := cfg.RequiredString("type")
   232		ctor, ok := ctors[typ]
   233		if typ != "" && !ok {
   234			return nil, fmt.Errorf("Invalid sorted.KeyValue type %q", typ)
   235		}
   236		if ok {
   237			s, err = ctor(cfg)
   238			if err != nil {
   239				we, ok := err.(NeedWipeError)
   240				if !ok {
   241					return nil, fmt.Errorf("error from %q KeyValue: %v", typ, err)
   242				}
   243				if err := cfg.Validate(); err != nil {
   244					return nil, err
   245				}
   246				we.Msg = fmt.Sprintf("error from %q KeyValue: %v", typ, err)
   247				return s, we
   248			}
   249		}
   250		return s, cfg.Validate()
   251	}
   252	
   253	// NewKeyValueMaybeWipe calls NewKeyValue and wipes the KeyValue if, and only
   254	// if, NewKeyValue has returned a NeedWipeError.
   255	func NewKeyValueMaybeWipe(cfg jsonconfig.Obj) (KeyValue, error) {
   256		kv, err := NewKeyValue(cfg)
   257		if err == nil {
   258			return kv, nil
   259		}
   260		if _, ok := err.(NeedWipeError); !ok {
   261			return nil, err
   262		}
   263		wiper, ok := kv.(Wiper)
   264		if !ok {
   265			return nil, fmt.Errorf("storage type %T needs wiping because %v. But it doesn't support sorted.Wiper", err, kv)
   266		}
   267		we := err
   268		if err := wiper.Wipe(); err != nil {
   269			return nil, fmt.Errorf("sorted key/value type %T needed wiping because %v. But could not wipe: %v", kv, we, err)
   270		}
   271		return kv, nil
   272	}
   273	
   274	// Foreach runs fn for each key/value pair in kv. If fn returns an error,
   275	// that same error is returned from Foreach and iteration stops.
   276	func Foreach(kv KeyValue, fn func(key, value string) error) error {
   277		return ForeachInRange(kv, "", "", fn)
   278	}
   279	
   280	// ForeachInRange runs fn for each key/value pair in kv in the range
   281	// of start and end, which behave the same as kv.Find. If fn returns
   282	// an error, that same error is returned from Foreach and iteration
   283	// stops.
   284	func ForeachInRange(kv KeyValue, start, end string, fn func(key, value string) error) error {
   285		it := kv.Find(start, end)
   286		for it.Next() {
   287			if err := fn(it.Key(), it.Value()); err != nil {
   288				it.Close()
   289				return err
   290			}
   291		}
   292		return it.Close()
   293	}
   294	
   295	// CheckSizes returns ErrKeyTooLarge if key does not respect KeyMaxSize or
   296	// ErrValueTooLarge if value does not respect ValueMaxSize
   297	func CheckSizes(key, value string) error {
   298		if len(key) > MaxKeySize {
   299			return ErrKeyTooLarge
   300		}
   301		if len(value) > MaxValueSize {
   302			return ErrValueTooLarge
   303		}
   304		return nil
   305	}