func (m *memcacheImpl) GetMulti(items []Item) error {
	lme := errors.NewLazyMultiError(len(items))
	realItems, idxMap := filterItems(lme, items, ErrCacheMiss)
	if len(realItems) == 0 {
		return lme.Get()
	}

	keys := make([]string, len(realItems))
	for i, itm := range realItems {
		keys[i] = itm.Key()
	}

	j := 0
	err := m.RawInterface.GetMulti(keys, func(item Item, err error) {
		i := idxMap[j]
		if !lme.Assign(i, err) {
			items[i].SetAll(item)
		}
		j++
	})
	if err == nil {
		err = lme.Get()
	}
	return err
}

func (d *datastoreImpl) PutMulti(src interface{}) error {
	slice := reflect.ValueOf(src)
	mat := parseMultiArg(slice.Type())
	if !mat.valid {
		return fmt.Errorf("invalid PutMulti input type: %T", src)
	}

	keys, vals, err := mat.GetKeysPMs(d.NewKey, slice)
	if err != nil {
		return err
	}

	lme := errors.NewLazyMultiError(len(keys))
	i := 0
	err = d.RawInterface.PutMulti(keys, vals, func(key Key, err error) {
		if key != keys[i] {
			mat.setKey(slice.Index(i), key)
		}
		lme.Assign(i, err)
		i++
	})

	if err == nil {
		err = lme.Get()
	}
	return err
}

func (tcf *checkFilter) PutMulti(keys []Key, vals []PropertyMap, cb PutMultiCB) error {
	if len(keys) != len(vals) {
		return fmt.Errorf("datastore: PutMulti with mismatched keys/vals lengths (%d/%d)", len(keys), len(vals))
	}
	if len(keys) == 0 {
		return nil
	}
	if cb == nil {
		return fmt.Errorf("datastore: PutMulti callback is nil")
	}
	lme := errors.NewLazyMultiError(len(keys))
	for i, k := range keys {
		if !k.PartialValid(tcf.aid, tcf.ns) {
			lme.Assign(i, ErrInvalidKey)
			continue
		}
		v := vals[i]
		if v == nil {
			lme.Assign(i, errors.New("datastore: PutMulti got nil vals entry"))
		}
	}
	if me := lme.Get(); me != nil {
		for _, err := range me.(errors.MultiError) {
			cb(nil, err)
		}
		return nil
	}

	return tcf.RawInterface.PutMulti(keys, vals, cb)
}

func (d *datastoreImpl) GetMulti(dst interface{}) error {
	slice := reflect.ValueOf(dst)
	mat := parseMultiArg(slice.Type())

	keys, pms, err := mat.GetKeysPMs(d.aid, d.ns, slice, true)
	if err != nil {
		return err
	}

	lme := errors.NewLazyMultiError(len(keys))
	i := 0
	meta := NewMultiMetaGetter(pms)
	err = d.RawInterface.GetMulti(keys, meta, func(pm PropertyMap, err error) error {
		if !lme.Assign(i, err) {
			lme.Assign(i, mat.setPM(slice.Index(i), pm))
		}
		i++
		return nil
	})

	if err == nil {
		err = lme.Get()
	}
	return err
}

func (t *txnBufState) fixKeys(keys []*datastore.Key) ([]*datastore.Key, error) {
	lme := errors.NewLazyMultiError(len(keys))
	realKeys := []*datastore.Key(nil)
	for i, key := range keys {
		if key.Incomplete() {
			// intentionally call AllocateIDs without lock.
			start, err := t.parentDS.AllocateIDs(key, 1)
			if !lme.Assign(i, err) {
				if realKeys == nil {
					realKeys = make([]*datastore.Key, len(keys))
					copy(realKeys, keys)
				}

				aid, ns, toks := key.Split()
				toks[len(toks)-1].IntID = start
				realKeys[i] = datastore.NewKeyToks(aid, ns, toks)
			}
		}
	}
	err := lme.Get()

	if realKeys != nil {
		return realKeys, err
	}
	return keys, err
}

func (d *datastoreImpl) GetMulti(dst interface{}) error {
	slice := reflect.ValueOf(dst)
	mat := parseMultiArg(slice.Type())
	if !mat.valid {
		return fmt.Errorf("invalid GetMulti input type: %T", dst)
	}

	keys, pms, err := mat.GetKeysPMs(d.NewKey, slice)
	if err != nil {
		return err
	}

	lme := errors.NewLazyMultiError(len(keys))
	i := 0
	meta := NewMultiMetaGetter(pms)
	err = d.RawInterface.GetMulti(keys, meta, func(pm PropertyMap, err error) {
		if !lme.Assign(i, err) {
			lme.Assign(i, mat.setPM(slice.Index(i), pm))
		}
		i++
	})

	if err == nil {
		err = lme.Get()
	}
	return err
}

// dsMF2R (DS multi-fake-to-fake) converts a slice of wrapped keys to SDK keys.
func dsMF2R(aeCtx context.Context, ks []*ds.Key) ([]*datastore.Key, error) {
	lme := errors.NewLazyMultiError(len(ks))
	ret := make([]*datastore.Key, len(ks))
	err := error(nil)
	for i, k := range ks {
		ret[i], err = dsF2R(aeCtx, k)
		lme.Assign(i, err)
	}
	return ret, lme.Get()
}

func (m *memcacheImpl) DeleteMulti(keys []string) error {
	lme := errors.NewLazyMultiError(len(keys))
	i := 0
	err := m.RawInterface.DeleteMulti(keys, func(err error) {
		lme.Assign(i, err)
		i++
	})
	if err == nil {
		err = lme.Get()
	}
	return err
}

func (t *taskqueueImpl) DeleteMulti(tasks []*Task, queueName string) error {
	lme := errors.NewLazyMultiError(len(tasks))
	i := 0
	err := t.RawInterface.DeleteMulti(tasks, queueName, func(err error) {
		lme.Assign(i, err)
		i++
	})
	if err == nil {
		err = lme.Get()
	}
	return err
}

func (d *datastoreImpl) DeleteMulti(keys []Key) (err error) {
	lme := errors.NewLazyMultiError(len(keys))
	i := 0
	extErr := d.RawInterface.DeleteMulti(keys, func(internalErr error) {
		lme.Assign(i, internalErr)
		i++
	})
	err = lme.Get()
	if err == nil {
		err = extErr
	}
	return
}

func multiCall(items []Item, nilErr error, inner func(items []Item, cb RawCB) error) error {
	lme := errors.NewLazyMultiError(len(items))
	realItems, idxMap := filterItems(lme, items, nilErr)
	j := 0
	err := inner(realItems, func(err error) {
		lme.Assign(idxMap[j], err)
		j++
	})
	if err == nil {
		err = lme.Get()
	}
	return err
}

func (t *taskqueueImpl) Stats(queueNames ...string) ([]Statistics, error) {
	ret := make([]Statistics, len(queueNames))
	lme := errors.NewLazyMultiError(len(queueNames))
	i := 0
	err := t.RawInterface.Stats(queueNames, func(s *Statistics, err error) {
		if !lme.Assign(i, err) {
			ret[i] = *s
		}
		i++
	})
	if err == nil {
		err = lme.Get()
	}
	return ret, err
}

func commitToReal(s *txnBufState) error {
	toPut, toPutKeys, toDel := s.effect()

	return parallel.FanOutIn(func(ch chan<- func() error) {
		if len(toPut) > 0 {
			ch <- func() error {
				mErr := errors.NewLazyMultiError(len(toPut))
				i := 0
				err := s.parentDS.PutMulti(toPutKeys, toPut, func(_ *datastore.Key, err error) error {
					mErr.Assign(i, err)
					i++
					return nil
				})
				if err == nil {
					err = mErr.Get()
				}
				return err
			}
		}
		if len(toDel) > 0 {
			ch <- func() error {
				mErr := errors.NewLazyMultiError(len(toDel))
				i := 0
				err := s.parentDS.DeleteMulti(toDel, func(err error) error {
					mErr.Assign(i, err)
					i++
					return nil
				})
				if err == nil {
					err = mErr.Get()
				}
				return err
			}
		}
	})
}

func (mat *multiArgType) GetKeysPMs(nk newKeyFunc, slice reflect.Value) ([]Key, []PropertyMap, error) {
	retKey := make([]Key, slice.Len())
	retPM := make([]PropertyMap, slice.Len())
	lme := errors.NewLazyMultiError(len(retKey))
	for i := range retKey {
		key, err := mat.getKey(nk, slice.Index(i))
		if !lme.Assign(i, err) {
			retKey[i] = key
			pm, err := mat.getPM(slice.Index(i))
			if !lme.Assign(i, err) {
				retPM[i] = pm
			}
		}
	}
	return retKey, retPM, lme.Get()
}

// makeFetchPlan takes the input facts and makes a plan about what to do with them.
//
// Possible scenarios:
//   * all entries we got from memcache are valid data, and so we don't need
//     to call through to the underlying datastore at all.
//   * some entries are 'lock' entries, owned by us, and so we should get them
//     from datastore and then attempt to save them back to memcache.
//   * some entries are 'lock' entries, owned by something else, so we should
//     get them from datastore and then NOT save them to memcache.
//
// Or some combination thereof. This also handles memcache enries with invalid
// data in them, cases where items have caching disabled entirely, etc.
func makeFetchPlan(c context.Context, aid, ns string, f *facts) *plan {
	p := plan{
		keepMeta: f.getMeta != nil,
		decoded:  make([]ds.PropertyMap, len(f.lockItems)),
		lme:      errors.NewLazyMultiError(len(f.lockItems)),
	}
	for i, lockItm := range f.lockItems {
		m := f.getMeta.GetSingle(i)
		getKey := f.getKeys[i]

		if lockItm == nil {
			// this item wasn't cacheable (e.g. the model had caching disabled,
			// shardsForKey returned 0, etc.)
			p.add(i, getKey, m, nil)
			continue
		}

		switch FlagValue(lockItm.Flags()) {
		case ItemHasLock:
			if bytes.Equal(f.nonce, lockItm.Value()) {
				// we have the lock
				p.add(i, getKey, m, lockItm)
			} else {
				// someone else has the lock, don't save
				p.add(i, getKey, m, nil)
			}

		case ItemHasData:
			pmap, err := decodeItemValue(lockItm.Value(), aid, ns)
			switch err {
			case nil:
				p.decoded[i] = pmap
			case ds.ErrNoSuchEntity:
				p.lme.Assign(i, ds.ErrNoSuchEntity)
			default:
				(logging.Fields{"error": err}).Warningf(c,
					"dscache: error decoding %s, %s", lockItm.Key(), getKey)
				p.add(i, getKey, m, nil)
			}

		default:
			// have some other sort of object, or our AddMulti failed to add this item.
			p.add(i, getKey, m, nil)
		}
	}
	return &p
}

func (d *datastoreImpl) ExistsMulti(keys []*Key) ([]bool, error) {
	lme := errors.NewLazyMultiError(len(keys))
	ret := make([]bool, len(keys))
	i := 0
	err := d.RawInterface.GetMulti(keys, nil, func(_ PropertyMap, err error) error {
		if err == nil {
			ret[i] = true
		} else if err != ErrNoSuchEntity {
			lme.Assign(i, err)
		}
		i++
		return nil
	})
	if err != nil {
		return ret, err
	}
	return ret, lme.Get()
}

func (tcf *checkFilter) DeleteMulti(keys []Key, cb DeleteMultiCB) error {
	if len(keys) == 0 {
		return nil
	}
	if cb == nil {
		return fmt.Errorf("datastore: DeleteMulti callback is nil")
	}
	lme := errors.NewLazyMultiError(len(keys))
	for i, k := range keys {
		if k.Incomplete() || !k.Valid(false, tcf.aid, tcf.ns) {
			lme.Assign(i, ErrInvalidKey)
		}
	}
	if me := lme.Get(); me != nil {
		for _, err := range me.(errors.MultiError) {
			cb(err)
		}
		return nil
	}
	return tcf.RawInterface.DeleteMulti(keys, cb)
}

func (mat *multiArgType) GetKeysPMs(aid, ns string, slice reflect.Value, meta bool) ([]*Key, []PropertyMap, error) {
	retKey := make([]*Key, slice.Len())
	retPM := make([]PropertyMap, slice.Len())
	getter := mat.getPM
	if meta {
		getter = func(slot reflect.Value) (PropertyMap, error) {
			return mat.getMetaPM(slot), nil
		}
	}
	lme := errors.NewLazyMultiError(len(retKey))
	for i := range retKey {
		key, err := mat.getKey(aid, ns, slice.Index(i))
		if !lme.Assign(i, err) {
			retKey[i] = key
			pm, err := getter(slice.Index(i))
			if !lme.Assign(i, err) {
				retPM[i] = pm
			}
		}
	}
	return retKey, retPM, lme.Get()
}

func (d *datastoreImpl) GetAll(q Query, dst interface{}) error {
	v := reflect.ValueOf(dst)
	if v.Kind() != reflect.Ptr {
		return fmt.Errorf("invalid GetAll dst: must have a ptr-to-slice: %T", dst)
	}
	if !v.IsValid() || v.IsNil() {
		return errors.New("invalid GetAll dst: <nil>")
	}

	if keys, ok := dst.(*[]Key); ok {
		return d.RawInterface.Run(q.KeysOnly(), func(k Key, _ PropertyMap, _ CursorCB) bool {
			*keys = append(*keys, k)
			return true
		})
	}

	slice := v.Elem()
	mat := parseMultiArg(slice.Type())
	if !mat.valid || mat.newElem == nil {
		return fmt.Errorf("invalid GetAll input type: %T", dst)
	}

	lme := errors.NewLazyMultiError(slice.Len())
	i := 0
	err := d.RawInterface.Run(q, func(k Key, pm PropertyMap, _ CursorCB) bool {
		slice.Set(reflect.Append(slice, mat.newElem()))
		itm := slice.Index(i)
		mat.setKey(itm, k)
		lme.Assign(i, mat.setPM(itm, pm))
		i++
		return true
	})
	if err == nil {
		err = lme.Get()
	}
	return err
}

func (d *datastoreImpl) PutMulti(src interface{}) error {
	slice := reflect.ValueOf(src)
	mat := parseMultiArg(slice.Type())

	keys, vals, err := mat.GetKeysPMs(d.aid, d.ns, slice, false)
	if err != nil {
		return err
	}

	lme := errors.NewLazyMultiError(len(keys))
	i := 0
	err = d.RawInterface.PutMulti(keys, vals, func(key *Key, err error) error {
		if !lme.Assign(i, err) && key != keys[i] {
			mat.setKey(slice.Index(i), key)
		}
		i++
		return nil
	})

	if err == nil {
		err = lme.Get()
	}
	return err
}