func (s *memorySeriesStorage) preloadChunksForRange(
	fp clientmodel.Fingerprint,
	from clientmodel.Timestamp, through clientmodel.Timestamp,
	stalenessDelta time.Duration,
) ([]*chunkDesc, error) {
	s.fpLocker.Lock(fp)
	defer s.fpLocker.Unlock(fp)

	series, ok := s.fpToSeries.get(fp)
	if !ok {
		has, first, last, err := s.persistence.hasArchivedMetric(fp)
		if err != nil {
			return nil, err
		}
		if !has {
			s.invalidPreloadRequestsCount.Inc()
			return nil, nil
		}
		if from.Add(-stalenessDelta).Before(last) && through.Add(stalenessDelta).After(first) {
			metric, err := s.persistence.getArchivedMetric(fp)
			if err != nil {
				return nil, err
			}
			series = s.getOrCreateSeries(fp, metric)
		} else {
			return nil, nil
		}
	}
	return series.preloadChunksForRange(from, through, fp, s)
}

func prepareInstantQuery(node Node, timestamp clientmodel.Timestamp, storage local.Storage, queryStats *stats.TimerGroup) (local.Preloader, error) {
	analyzeTimer := queryStats.GetTimer(stats.QueryAnalysisTime).Start()
	analyzer := NewQueryAnalyzer(storage)
	Walk(analyzer, node)
	analyzeTimer.Stop()

	// TODO: Preloading should time out after a given duration.
	preloadTimer := queryStats.GetTimer(stats.PreloadTime).Start()
	p := storage.NewPreloader()
	for fp, rangeDuration := range analyzer.FullRanges {
		if err := p.PreloadRange(fp, timestamp.Add(-rangeDuration), timestamp, *stalenessDelta); err != nil {
			p.Close()
			return nil, err
		}
	}
	for fp := range analyzer.IntervalRanges {
		if err := p.PreloadRange(fp, timestamp, timestamp, *stalenessDelta); err != nil {
			p.Close()
			return nil, err
		}
	}
	preloadTimer.Stop()

	ii := &iteratorInitializer{
		storage: storage,
	}
	Walk(ii, node)

	return p, nil
}

func viewAdapterForRangeQuery(node Node, start clientmodel.Timestamp, end clientmodel.Timestamp, interval time.Duration, storage metric.PreloadingPersistence, queryStats *stats.TimerGroup) (*viewAdapter, error) {
	analyzeTimer := queryStats.GetTimer(stats.QueryAnalysisTime).Start()
	analyzer := NewQueryAnalyzer(storage)
	analyzer.AnalyzeQueries(node)
	analyzeTimer.Stop()

	requestBuildTimer := queryStats.GetTimer(stats.ViewRequestBuildTime).Start()
	viewBuilder := storage.NewViewRequestBuilder()
	for fingerprint, rangeDuration := range analyzer.FullRanges {
		if interval < rangeDuration {
			viewBuilder.GetMetricRange(&fingerprint, start.Add(-rangeDuration), end)
		} else {
			viewBuilder.GetMetricRangeAtInterval(&fingerprint, start.Add(-rangeDuration), end, interval, rangeDuration)
		}
	}
	for fingerprint := range analyzer.IntervalRanges {
		viewBuilder.GetMetricAtInterval(&fingerprint, start, end, interval)
	}
	requestBuildTimer.Stop()

	buildTimer := queryStats.GetTimer(stats.InnerViewBuildingTime).Start()
	view, err := viewBuilder.Execute(time.Duration(60)*time.Second, queryStats)
	buildTimer.Stop()
	if err != nil {
		return nil, err
	}
	return NewViewAdapter(view, storage, queryStats), nil
}

func (t *TieredStorage) seriesTooOld(f *clientmodel.Fingerprint, i clientmodel.Timestamp) (bool, error) {
	// BUG(julius): Make this configurable by query layer.
	i = i.Add(-stalenessLimit)

	wm, cacheHit, _ := t.wmCache.Get(f)
	if !cacheHit {
		if t.memoryArena.HasFingerprint(f) {
			samples := t.memoryArena.CloneSamples(f)
			if len(samples) > 0 {
				newest := samples[len(samples)-1].Timestamp
				t.wmCache.Put(f, &watermarks{High: newest})

				return newest.Before(i), nil
			}
		}

		highTime, diskHit, err := t.DiskStorage.MetricHighWatermarks.Get(f)
		if err != nil {
			return false, err
		}

		if diskHit {
			t.wmCache.Put(f, &watermarks{High: highTime})

			return highTime.Before(i), nil
		}

		t.wmCache.Put(f, &watermarks{})
		return true, nil
	}

	return wm.High.Before(i), nil
}

// eval evaluates the rule expression and then creates pending alerts and fires
// or removes previously pending alerts accordingly.
func (rule *AlertingRule) eval(timestamp clientmodel.Timestamp, engine *promql.Engine) (promql.Vector, error) {
	query, err := engine.NewInstantQuery(rule.vector.String(), timestamp)
	if err != nil {
		return nil, err
	}
	exprResult, err := query.Exec().Vector()
	if err != nil {
		return nil, err
	}

	rule.mutex.Lock()
	defer rule.mutex.Unlock()

	// Create pending alerts for any new vector elements in the alert expression
	// or update the expression value for existing elements.
	resultFPs := map[clientmodel.Fingerprint]struct{}{}
	for _, sample := range exprResult {
		fp := sample.Metric.Metric.Fingerprint()
		resultFPs[fp] = struct{}{}

		if alert, ok := rule.activeAlerts[fp]; !ok {
			labels := clientmodel.LabelSet{}
			labels.MergeFromMetric(sample.Metric.Metric)
			labels = labels.Merge(rule.labels)
			if _, ok := labels[clientmodel.MetricNameLabel]; ok {
				delete(labels, clientmodel.MetricNameLabel)
			}
			rule.activeAlerts[fp] = &Alert{
				Name:        rule.name,
				Labels:      labels,
				State:       StatePending,
				ActiveSince: timestamp,
				Value:       sample.Value,
			}
		} else {
			alert.Value = sample.Value
		}
	}

	vector := promql.Vector{}

	// Check if any pending alerts should be removed or fire now. Write out alert timeseries.
	for fp, activeAlert := range rule.activeAlerts {
		if _, ok := resultFPs[fp]; !ok {
			vector = append(vector, activeAlert.sample(timestamp, 0))
			delete(rule.activeAlerts, fp)
			continue
		}

		if activeAlert.State == StatePending && timestamp.Sub(activeAlert.ActiveSince) >= rule.holdDuration {
			vector = append(vector, activeAlert.sample(timestamp, 0))
			activeAlert.State = StateFiring
		}

		vector = append(vector, activeAlert.sample(timestamp, 1))
	}

	return vector, nil
}

// Update implements CurationRemarker.
func (w *LevelDBCurationRemarker) Update(pair *curationKey, t clientmodel.Timestamp) error {
	k := &dto.CurationKey{}
	pair.dump(k)

	return w.LevelDBPersistence.Put(k, &dto.CurationValue{
		LastCompletionTimestamp: proto.Int64(t.Unix()),
	})
}

func (rule *AlertingRule) Eval(timestamp clientmodel.Timestamp, storage metric.PreloadingPersistence) (ast.Vector, error) {
	// Get the raw value of the rule expression.
	exprResult, err := rule.EvalRaw(timestamp, storage)
	if err != nil {
		return nil, err
	}

	rule.mutex.Lock()
	defer rule.mutex.Unlock()

	// Create pending alerts for any new vector elements in the alert expression
	// or update the expression value for existing elements.
	resultFingerprints := utility.Set{}
	for _, sample := range exprResult {
		fp := new(clientmodel.Fingerprint)
		fp.LoadFromMetric(sample.Metric)
		resultFingerprints.Add(*fp)

		if alert, ok := rule.activeAlerts[*fp]; !ok {
			labels := clientmodel.LabelSet{}
			labels.MergeFromMetric(sample.Metric)
			labels = labels.Merge(rule.Labels)
			if _, ok := labels[clientmodel.MetricNameLabel]; ok {
				delete(labels, clientmodel.MetricNameLabel)
			}
			rule.activeAlerts[*fp] = &Alert{
				Name:        rule.name,
				Labels:      labels,
				State:       PENDING,
				ActiveSince: timestamp,
				Value:       sample.Value,
			}
		} else {
			alert.Value = sample.Value
		}
	}

	vector := ast.Vector{}

	// Check if any pending alerts should be removed or fire now. Write out alert timeseries.
	for fp, activeAlert := range rule.activeAlerts {
		if !resultFingerprints.Has(fp) {
			vector = append(vector, activeAlert.sample(timestamp, 0))
			delete(rule.activeAlerts, fp)
			continue
		}

		if activeAlert.State == PENDING && timestamp.Sub(activeAlert.ActiveSince) >= rule.holdDuration {
			vector = append(vector, activeAlert.sample(timestamp, 0))
			activeAlert.State = FIRING
		}

		vector = append(vector, activeAlert.sample(timestamp, 1))
	}

	return vector, nil
}

// MayContain indicates whether the given SampleKey could potentially contain a
// value at the provided time.  Even if true is emitted, that does not mean a
// satisfactory value, in fact, exists.
func (s *SampleKey) MayContain(t clientmodel.Timestamp) bool {
	switch {
	case t.Before(s.FirstTimestamp):
		return false
	case t.After(s.LastTimestamp):
		return false
	default:
		return true
	}
}

// EvalBoundaries implements the MatrixNode interface and returns the
// boundary values of the selector.
func (node *MatrixSelector) EvalBoundaries(timestamp clientmodel.Timestamp, view *viewAdapter) Matrix {
	interval := &metric.Interval{
		OldestInclusive: timestamp.Add(-node.interval),
		NewestInclusive: timestamp,
	}
	values, err := view.GetBoundaryValues(node.fingerprints, interval)
	if err != nil {
		glog.Error("Unable to get boundary values for vector interval: ", err)
		return Matrix{}
	}
	return values
}

// InsideInterval indicates whether a given range of sorted values could contain
// a value for a given time.
func (v Values) InsideInterval(t clientmodel.Timestamp) bool {
	switch {
	case v.Len() == 0:
		return false
	case t.Before(v[0].Timestamp):
		return false
	case !v[v.Len()-1].Timestamp.Before(t):
		return false
	default:
		return true
	}
}

// interpolateSamples interpolates a value at a target time between two
// provided sample pairs.
func interpolateSamples(first, second *metric.SamplePair, timestamp clientmodel.Timestamp) *metric.SamplePair {
	dv := second.Value - first.Value
	dt := second.Timestamp.Sub(first.Timestamp)

	dDt := dv / clientmodel.SampleValue(dt)
	offset := clientmodel.SampleValue(timestamp.Sub(first.Timestamp))

	return &metric.SamplePair{
		Value:     first.Value + (offset * dDt),
		Timestamp: timestamp,
	}
}

func buildValues(firstValue clientmodel.SampleValue, from, to clientmodel.Timestamp, interval time.Duration) (v metric.Values) {
	for from.Before(to) {
		v = append(v, metric.SamplePair{
			Value:     firstValue,
			Timestamp: from,
		})

		from = from.Add(interval)
		firstValue++
	}

	return
}

func (l *valueAtIntervalAlongRangeList) Get(fp *clientmodel.Fingerprint, from, through clientmodel.Timestamp, interval, rangeDuration time.Duration) *getValueRangeAtIntervalOp {
	var op *getValueRangeAtIntervalOp
	v, ok := l.l.Get()
	if ok {
		op = v.(*getValueRangeAtIntervalOp)
	} else {
		op = &getValueRangeAtIntervalOp{}
	}
	op.fp = *fp
	op.current = from
	op.rangeThrough = from.Add(rangeDuration)
	op.rangeDuration = rangeDuration
	op.interval = interval
	op.through = through
	return op
}

func buildSamples(from, to clientmodel.Timestamp, interval time.Duration, m clientmodel.Metric) (v clientmodel.Samples) {
	i := clientmodel.SampleValue(0)

	for from.Before(to) {
		v = append(v, &clientmodel.Sample{
			Metric:    m,
			Value:     i,
			Timestamp: from,
		})

		from = from.Add(interval)
		i++
	}

	return
}

func generateTestSamples(endTime clientmodel.Timestamp, numTs int, samplesPerTs int, interval time.Duration) clientmodel.Samples {
	samples := make(clientmodel.Samples, 0, numTs*samplesPerTs)

	startTime := endTime.Add(-interval * time.Duration(samplesPerTs-1))
	for ts := 0; ts < numTs; ts++ {
		metric := clientmodel.Metric{}
		metric[clientmodel.MetricNameLabel] = clientmodel.LabelValue(fmt.Sprintf("metric_%d", ts))
		for i := 0; i < samplesPerTs; i++ {
			sample := &clientmodel.Sample{
				Metric:    metric,
				Value:     clientmodel.SampleValue(ts + 1000*i),
				Timestamp: startTime.Add(interval * time.Duration(i)),
			}
			samples = append(samples, sample)
		}
	}
	sort.Sort(samples)
	return samples
}

func prepareRangeQuery(node Node, start clientmodel.Timestamp, end clientmodel.Timestamp, interval time.Duration, storage local.Storage, queryStats *stats.TimerGroup) (local.Preloader, error) {
	analyzeTimer := queryStats.GetTimer(stats.QueryAnalysisTime).Start()
	analyzer := NewQueryAnalyzer(storage)
	Walk(analyzer, node)
	analyzeTimer.Stop()

	// TODO: Preloading should time out after a given duration.
	preloadTimer := queryStats.GetTimer(stats.PreloadTime).Start()
	p := storage.NewPreloader()
	for fp, rangeDuration := range analyzer.FullRanges {
		if err := p.PreloadRange(fp, start.Add(-rangeDuration), end, *stalenessDelta); err != nil {
			p.Close()
			return nil, err
		}
		/*
			if interval < rangeDuration {
				if err := p.GetMetricRange(fp, end, end.Sub(start)+rangeDuration); err != nil {
					p.Close()
					return nil, err
				}
			} else {
				if err := p.GetMetricRangeAtInterval(fp, start, end, interval, rangeDuration); err != nil {
					p.Close()
					return nil, err
				}
			}
		*/
	}
	for fp := range analyzer.IntervalRanges {
		if err := p.PreloadRange(fp, start, end, *stalenessDelta); err != nil {
			p.Close()
			return nil, err
		}
	}
	preloadTimer.Stop()

	ii := &iteratorInitializer{
		storage: storage,
	}
	Walk(ii, node)

	return p, nil
}

// preloadChunksForRange loads chunks for the given range from the persistence.
// The caller must have locked the fingerprint of the series.
func (s *memorySeries) preloadChunksForRange(
	from clientmodel.Timestamp, through clientmodel.Timestamp,
	fp clientmodel.Fingerprint, mss *memorySeriesStorage,
) ([]*chunkDesc, error) {
	firstChunkDescTime := clientmodel.Latest
	if len(s.chunkDescs) > 0 {
		firstChunkDescTime = s.chunkDescs[0].firstTime()
	}
	if s.chunkDescsOffset != 0 && from.Before(firstChunkDescTime) {
		cds, err := mss.loadChunkDescs(fp, firstChunkDescTime)
		if err != nil {
			return nil, err
		}
		s.chunkDescs = append(cds, s.chunkDescs...)
		s.chunkDescsOffset = 0
		s.persistWatermark += len(cds)
	}

	if len(s.chunkDescs) == 0 {
		return nil, nil
	}

	// Find first chunk with start time after "from".
	fromIdx := sort.Search(len(s.chunkDescs), func(i int) bool {
		return s.chunkDescs[i].firstTime().After(from)
	})
	// Find first chunk with start time after "through".
	throughIdx := sort.Search(len(s.chunkDescs), func(i int) bool {
		return s.chunkDescs[i].firstTime().After(through)
	})
	if fromIdx > 0 {
		fromIdx--
	}
	if throughIdx == len(s.chunkDescs) {
		throughIdx--
	}

	pinIndexes := make([]int, 0, throughIdx-fromIdx+1)
	for i := fromIdx; i <= throughIdx; i++ {
		pinIndexes = append(pinIndexes, i)
	}
	return s.preloadChunks(pinIndexes, fp, mss)
}

// ValueAtTime implements SeriesIterator.
func (it *memorySeriesIterator) ValueAtTime(t clientmodel.Timestamp) metric.Values {
	// The most common case. We are iterating through a chunk.
	if it.chunkIt != nil && it.chunkIt.contains(t) {
		return it.chunkIt.valueAtTime(t)
	}

	if len(it.chunks) == 0 {
		return nil
	}

	// Before or exactly on the first sample of the series.
	it.chunkIt = it.chunkIterator(0)
	ts := it.chunkIt.timestampAtIndex(0)
	if !t.After(ts) {
		// return first value of first chunk
		return metric.Values{metric.SamplePair{
			Timestamp: ts,
			Value:     it.chunkIt.sampleValueAtIndex(0),
		}}
	}

	// After or exactly on the last sample of the series.
	it.chunkIt = it.chunkIterator(len(it.chunks) - 1)
	ts = it.chunkIt.lastTimestamp()
	if !t.Before(ts) {
		// return last value of last chunk
		return metric.Values{metric.SamplePair{
			Timestamp: ts,
			Value:     it.chunkIt.sampleValueAtIndex(it.chunkIt.length() - 1),
		}}
	}

	// Find last chunk where firstTime() is before or equal to t.
	l := len(it.chunks) - 1
	i := sort.Search(len(it.chunks), func(i int) bool {
		return !it.chunks[l-i].firstTime().After(t)
	})
	if i == len(it.chunks) {
		panic("out of bounds")
	}
	it.chunkIt = it.chunkIterator(l - i)
	ts = it.chunkIt.lastTimestamp()
	if t.After(ts) {
		// We ended up between two chunks.
		sp1 := metric.SamplePair{
			Timestamp: ts,
			Value:     it.chunkIt.sampleValueAtIndex(it.chunkIt.length() - 1),
		}
		it.chunkIt = it.chunkIterator(l - i + 1)
		return metric.Values{
			sp1,
			metric.SamplePair{
				Timestamp: it.chunkIt.timestampAtIndex(0),
				Value:     it.chunkIt.sampleValueAtIndex(0),
			},
		}
	}
	return it.chunkIt.valueAtTime(t)
}

// EvalBoundaries implements the MatrixNode interface and returns the
// boundary values of the selector.
func (node *MatrixSelector) EvalBoundaries(timestamp clientmodel.Timestamp) Matrix {
	interval := &metric.Interval{
		OldestInclusive: timestamp.Add(-node.interval),
		NewestInclusive: timestamp,
	}

	//// timer := v.stats.GetTimer(stats.GetBoundaryValuesTime).Start()
	sampleStreams := []SampleStream{}
	for fp, it := range node.iterators {
		samplePairs := it.GetBoundaryValues(*interval)
		if len(samplePairs) == 0 {
			continue
		}

		sampleStream := SampleStream{
			Metric: node.metrics[fp],
			Values: samplePairs,
		}
		sampleStreams = append(sampleStreams, sampleStream)
	}
	//// timer.Stop()
	return sampleStreams
}

// GetValueAtTime implements SeriesIterator.
func (it *memorySeriesIterator) GetValueAtTime(t clientmodel.Timestamp) metric.Values {
	it.lock()
	defer it.unlock()

	// The most common case. We are iterating through a chunk.
	if it.chunkIt != nil && it.chunkIt.contains(t) {
		return it.chunkIt.getValueAtTime(t)
	}

	it.chunkIt = nil

	if len(it.chunks) == 0 {
		return nil
	}

	// Before or exactly on the first sample of the series.
	if !t.After(it.chunks[0].firstTime()) {
		// return first value of first chunk
		return it.chunks[0].newIterator().getValueAtTime(t)
	}
	// After or exactly on the last sample of the series.
	if !t.Before(it.chunks[len(it.chunks)-1].lastTime()) {
		// return last value of last chunk
		return it.chunks[len(it.chunks)-1].newIterator().getValueAtTime(t)
	}

	// Find first chunk where lastTime() is after or equal to t.
	i := sort.Search(len(it.chunks), func(i int) bool {
		return !it.chunks[i].lastTime().Before(t)
	})
	if i == len(it.chunks) {
		panic("out of bounds")
	}

	if t.Before(it.chunks[i].firstTime()) {
		// We ended up between two chunks.
		return metric.Values{
			it.chunks[i-1].newIterator().getValueAtTime(t)[0],
			it.chunks[i].newIterator().getValueAtTime(t)[0],
		}
	}
	// We ended up in the middle of a chunk. We might stay there for a while,
	// so save it as the current chunk iterator.
	it.chunkIt = it.chunks[i].newIterator()
	return it.chunkIt.getValueAtTime(t)
}