// expect adds a new metric with a sequence of values to the set of expected
// results for the query.
func (ev *evalCmd) expect(pos int, m clientmodel.Metric, vals ...sequenceValue) {
	if m == nil {
		ev.expected[0] = entry{pos: pos, vals: vals}
		return
	}
	fp := m.Fingerprint()
	ev.metrics[fp] = m
	ev.expected[fp] = entry{pos: pos, vals: vals}
}

// mapFP takes a raw fingerprint (as returned by Metrics.FastFingerprint) and
// returns a truly unique fingerprint. The caller must have locked the raw
// fingerprint.
//
// If an error is encountered, it is returned together with the unchanged raw
// fingerprint.
func (m *fpMapper) mapFP(fp clientmodel.Fingerprint, metric clientmodel.Metric) (clientmodel.Fingerprint, error) {
	// First check if we are in the reserved FP space, in which case this is
	// automatically a collision that has to be mapped.
	if fp <= maxMappedFP {
		return m.maybeAddMapping(fp, metric)
	}

	// Then check the most likely case: This fp belongs to a series that is
	// already in memory.
	s, ok := m.fpToSeries.get(fp)
	if ok {
		// FP exists in memory, but is it for the same metric?
		if metric.Equal(s.metric) {
			// Yupp. We are done.
			return fp, nil
		}
		// Collision detected!
		return m.maybeAddMapping(fp, metric)
	}
	// Metric is not in memory. Before doing the expensive archive lookup,
	// check if we have a mapping for this metric in place already.
	m.mtx.RLock()
	mappedFPs, fpAlreadyMapped := m.mappings[fp]
	m.mtx.RUnlock()
	if fpAlreadyMapped {
		// We indeed have mapped fp historically.
		ms := metricToUniqueString(metric)
		// fp is locked by the caller, so no further locking of
		// 'collisions' required (it is specific to fp).
		mappedFP, ok := mappedFPs[ms]
		if ok {
			// Historical mapping found, return the mapped FP.
			return mappedFP, nil
		}
	}
	// If we are here, FP does not exist in memory and is either not mapped
	// at all, or existing mappings for FP are not for m. Check if we have
	// something for FP in the archive.
	archivedMetric, err := m.p.archivedMetric(fp)
	if err != nil {
		return fp, err
	}
	if archivedMetric != nil {
		// FP exists in archive, but is it for the same metric?
		if metric.Equal(archivedMetric) {
			// Yupp. We are done.
			return fp, nil
		}
		// Collision detected!
		return m.maybeAddMapping(fp, metric)
	}
	// As fp does not exist, neither in memory nor in archive, we can safely
	// keep it unmapped.
	return fp, nil
}

func (rule *AlertingRule) HTMLSnippet() template.HTML {
	alertMetric := clientmodel.Metric{
		clientmodel.MetricNameLabel: AlertMetricName,
		AlertNameLabel:              clientmodel.LabelValue(rule.name),
	}
	return template.HTML(fmt.Sprintf(
		`ALERT <a href="%s">%s</a> IF <a href="%s">%s</a> FOR %s WITH %s`,
		ConsoleLinkForExpression(alertMetric.String()),
		rule.name,
		ConsoleLinkForExpression(rule.vector.String()),
		rule.vector,
		utility.DurationToString(rule.holdDuration),
		rule.Labels))
}

// HTMLSnippet returns an HTML snippet representing this alerting rule.
func (rule *AlertingRule) HTMLSnippet(pathPrefix string) template.HTML {
	alertMetric := clientmodel.Metric{
		clientmodel.MetricNameLabel: alertMetricName,
		alertNameLabel:              clientmodel.LabelValue(rule.name),
	}
	return template.HTML(fmt.Sprintf(
		`ALERT <a href="%s">%s</a> IF <a href="%s">%s</a> FOR %s WITH %s`,
		pathPrefix+strutil.GraphLinkForExpression(alertMetric.String()),
		rule.name,
		pathPrefix+strutil.GraphLinkForExpression(rule.vector.String()),
		rule.vector,
		strutil.DurationToString(rule.holdDuration),
		rule.labels))
}

// maybeAddMapping adds a fingerprint mapping to fpm if the FastFingerprint of m is different from fp.
func maybeAddMapping(fp clientmodel.Fingerprint, m clientmodel.Metric, fpm fpMappings) {
	if rawFP := m.FastFingerprint(); rawFP != fp {
		log.Warnf(
			"Metric %v with fingerprint %v is mapped from raw fingerprint %v.",
			m, fp, rawFP,
		)
		if mappedFPs, ok := fpm[rawFP]; ok {
			mappedFPs[metricToUniqueString(m)] = fp
		} else {
			fpm[rawFP] = map[string]clientmodel.Fingerprint{
				metricToUniqueString(m): fp,
			}
		}
	}
}

func TestAppendOutOfOrder(t *testing.T) {
	s, closer := NewTestStorage(t, 1)
	defer closer.Close()

	m := clientmodel.Metric{
		clientmodel.MetricNameLabel: "out_of_order",
	}

	for i, t := range []int{0, 2, 2, 1} {
		s.Append(&clientmodel.Sample{
			Metric:    m,
			Timestamp: clientmodel.Timestamp(t),
			Value:     clientmodel.SampleValue(i),
		})
	}

	fp, err := s.mapper.mapFP(m.FastFingerprint(), m)
	if err != nil {
		t.Fatal(err)
	}

	pl := s.NewPreloader()
	defer pl.Close()

	err = pl.PreloadRange(fp, 0, 2, 5*time.Minute)
	if err != nil {
		t.Fatalf("Error preloading chunks: %s", err)
	}

	it := s.NewIterator(fp)

	want := metric.Values{
		{
			Timestamp: 0,
			Value:     0,
		},
		{
			Timestamp: 2,
			Value:     1,
		},
	}
	got := it.RangeValues(metric.Interval{OldestInclusive: 0, NewestInclusive: 2})
	if !reflect.DeepEqual(want, got) {
		t.Fatalf("want %v, got %v", want, got)
	}
}

// set a sequence of sample values for the given metric.
func (cmd *loadCmd) set(m clientmodel.Metric, vals ...sequenceValue) {
	fp := m.Fingerprint()

	samples := make(metric.Values, 0, len(vals))
	ts := testStartTime
	for _, v := range vals {
		if !v.omitted {
			samples = append(samples, metric.SamplePair{
				Timestamp: ts,
				Value:     v.value,
			})
		}
		ts = ts.Add(cmd.gap)
	}
	cmd.defs[fp] = samples
	cmd.metrics[fp] = m
}

// HTMLSnippet returns an HTML snippet representing this alerting rule. The
// resulting snippet is expected to be presented in a <pre> element, so that
// line breaks and other returned whitespace is respected.
func (rule *AlertingRule) HTMLSnippet(pathPrefix string) template.HTML {
	alertMetric := clientmodel.Metric{
		clientmodel.MetricNameLabel: alertMetricName,
		alertNameLabel:              clientmodel.LabelValue(rule.name),
	}
	s := fmt.Sprintf("ALERT <a href=%q>%s</a>", pathPrefix+strutil.GraphLinkForExpression(alertMetric.String()), rule.name)
	s += fmt.Sprintf("\n  IF <a href=%q>%s</a>", pathPrefix+strutil.GraphLinkForExpression(rule.vector.String()), rule.vector)
	if rule.holdDuration > 0 {
		s += fmt.Sprintf("\n  FOR %s", strutil.DurationToString(rule.holdDuration))
	}
	if len(rule.labels) > 0 {
		s += fmt.Sprintf("\n  WITH %s", rule.labels)
	}
	s += fmt.Sprintf("\n  SUMMARY %q", rule.summary)
	s += fmt.Sprintf("\n  DESCRIPTION %q", rule.description)
	s += fmt.Sprintf("\n  RUNBOOK %q", rule.runbook)
	return template.HTML(s)
}

func TestMatches(t *testing.T) {
	storage, closer := NewTestStorage(t, 1)
	defer closer.Close()

	samples := make([]*clientmodel.Sample, 100)
	fingerprints := make(clientmodel.Fingerprints, 100)

	for i := range samples {
		metric := clientmodel.Metric{
			clientmodel.MetricNameLabel: clientmodel.LabelValue(fmt.Sprintf("test_metric_%d", i)),
			"label1":                    clientmodel.LabelValue(fmt.Sprintf("test_%d", i/10)),
			"label2":                    clientmodel.LabelValue(fmt.Sprintf("test_%d", (i+5)/10)),
			"all":                       "const",
		}
		samples[i] = &clientmodel.Sample{
			Metric:    metric,
			Timestamp: clientmodel.Timestamp(i),
			Value:     clientmodel.SampleValue(i),
		}
		fingerprints[i] = metric.FastFingerprint()
	}
	for _, s := range samples {
		storage.Append(s)
	}
	storage.WaitForIndexing()

	newMatcher := func(matchType metric.MatchType, name clientmodel.LabelName, value clientmodel.LabelValue) *metric.LabelMatcher {
		lm, err := metric.NewLabelMatcher(matchType, name, value)
		if err != nil {
			t.Fatalf("error creating label matcher: %s", err)
		}
		return lm
	}

	var matcherTests = []struct {
		matchers metric.LabelMatchers
		expected clientmodel.Fingerprints
	}{
		{
			matchers: metric.LabelMatchers{newMatcher(metric.Equal, "label1", "x")},
			expected: clientmodel.Fingerprints{},
		},
		{
			matchers: metric.LabelMatchers{newMatcher(metric.Equal, "label1", "test_0")},
			expected: fingerprints[:10],
		},
		{
			matchers: metric.LabelMatchers{
				newMatcher(metric.Equal, "label1", "test_0"),
				newMatcher(metric.Equal, "label2", "test_1"),
			},
			expected: fingerprints[5:10],
		},
		{
			matchers: metric.LabelMatchers{
				newMatcher(metric.Equal, "all", "const"),
				newMatcher(metric.NotEqual, "label1", "x"),
			},
			expected: fingerprints,
		},
		{
			matchers: metric.LabelMatchers{
				newMatcher(metric.Equal, "all", "const"),
				newMatcher(metric.NotEqual, "label1", "test_0"),
			},
			expected: fingerprints[10:],
		},
		{
			matchers: metric.LabelMatchers{
				newMatcher(metric.Equal, "all", "const"),
				newMatcher(metric.NotEqual, "label1", "test_0"),
				newMatcher(metric.NotEqual, "label1", "test_1"),
				newMatcher(metric.NotEqual, "label1", "test_2"),
			},
			expected: fingerprints[30:],
		},
		{
			matchers: metric.LabelMatchers{
				newMatcher(metric.Equal, "label1", ""),
			},
			expected: fingerprints[:0],
		},
		{
			matchers: metric.LabelMatchers{
				newMatcher(metric.NotEqual, "label1", "test_0"),
				newMatcher(metric.Equal, "label1", ""),
			},
			expected: fingerprints[:0],
		},
		{
			matchers: metric.LabelMatchers{
				newMatcher(metric.NotEqual, "label1", "test_0"),
				newMatcher(metric.Equal, "label2", ""),
			},
			expected: fingerprints[:0],
		},
		{
			matchers: metric.LabelMatchers{
				newMatcher(metric.Equal, "all", "const"),
				newMatcher(metric.NotEqual, "label1", "test_0"),
//.........这里部分代码省略.........

func BenchmarkLabelMatching(b *testing.B) {
	s, closer := NewTestStorage(b, 1)
	defer closer.Close()

	h := fnv.New64a()
	lbl := func(x int) clientmodel.LabelValue {
		h.Reset()
		h.Write([]byte(fmt.Sprintf("%d", x)))
		return clientmodel.LabelValue(fmt.Sprintf("%d", h.Sum64()))
	}

	M := 32
	met := clientmodel.Metric{}
	for i := 0; i < M; i++ {
		met["label_a"] = lbl(i)
		for j := 0; j < M; j++ {
			met["label_b"] = lbl(j)
			for k := 0; k < M; k++ {
				met["label_c"] = lbl(k)
				for l := 0; l < M; l++ {
					met["label_d"] = lbl(l)
					s.Append(&clientmodel.Sample{
						Metric:    met.Clone(),
						Timestamp: 0,
						Value:     1,
					})
				}
			}
		}
	}
	s.WaitForIndexing()

	newMatcher := func(matchType metric.MatchType, name clientmodel.LabelName, value clientmodel.LabelValue) *metric.LabelMatcher {
		lm, err := metric.NewLabelMatcher(matchType, name, value)
		if err != nil {
			b.Fatalf("error creating label matcher: %s", err)
		}
		return lm
	}

	var matcherTests = []metric.LabelMatchers{
		{
			newMatcher(metric.Equal, "label_a", lbl(1)),
		},
		{
			newMatcher(metric.Equal, "label_a", lbl(3)),
			newMatcher(metric.Equal, "label_c", lbl(3)),
		},
		{
			newMatcher(metric.Equal, "label_a", lbl(3)),
			newMatcher(metric.Equal, "label_c", lbl(3)),
			newMatcher(metric.NotEqual, "label_d", lbl(3)),
		},
		{
			newMatcher(metric.Equal, "label_a", lbl(3)),
			newMatcher(metric.Equal, "label_b", lbl(3)),
			newMatcher(metric.Equal, "label_c", lbl(3)),
			newMatcher(metric.NotEqual, "label_d", lbl(3)),
		},
		{
			newMatcher(metric.RegexMatch, "label_a", ".+"),
		},
		{
			newMatcher(metric.Equal, "label_a", lbl(3)),
			newMatcher(metric.RegexMatch, "label_a", ".+"),
		},
		{
			newMatcher(metric.Equal, "label_a", lbl(1)),
			newMatcher(metric.RegexMatch, "label_c", "("+lbl(3)+"|"+lbl(10)+")"),
		},
		{
			newMatcher(metric.Equal, "label_a", lbl(3)),
			newMatcher(metric.Equal, "label_a", lbl(4)),
			newMatcher(metric.RegexMatch, "label_c", "("+lbl(3)+"|"+lbl(10)+")"),
		},
	}

	b.ReportAllocs()
	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		benchLabelMatchingRes = map[clientmodel.Fingerprint]clientmodel.COWMetric{}
		for _, mt := range matcherTests {
			benchLabelMatchingRes = s.MetricsForLabelMatchers(mt...)
		}
	}
	// Stop timer to not count the storage closing.
	b.StopTimer()
}

func TestFingerprintsForLabels(t *testing.T) {
	storage, closer := NewTestStorage(t, 1)
	defer closer.Close()

	samples := make([]*clientmodel.Sample, 100)
	fingerprints := make(clientmodel.Fingerprints, 100)

	for i := range samples {
		metric := clientmodel.Metric{
			clientmodel.MetricNameLabel: clientmodel.LabelValue(fmt.Sprintf("test_metric_%d", i)),
			"label1":                    clientmodel.LabelValue(fmt.Sprintf("test_%d", i/10)),
			"label2":                    clientmodel.LabelValue(fmt.Sprintf("test_%d", (i+5)/10)),
		}
		samples[i] = &clientmodel.Sample{
			Metric:    metric,
			Timestamp: clientmodel.Timestamp(i),
			Value:     clientmodel.SampleValue(i),
		}
		fingerprints[i] = metric.FastFingerprint()
	}
	for _, s := range samples {
		storage.Append(s)
	}
	storage.WaitForIndexing()

	var matcherTests = []struct {
		pairs    []metric.LabelPair
		expected clientmodel.Fingerprints
	}{
		{
			pairs:    []metric.LabelPair{{"label1", "x"}},
			expected: fingerprints[:0],
		},
		{
			pairs:    []metric.LabelPair{{"label1", "test_0"}},
			expected: fingerprints[:10],
		},
		{
			pairs: []metric.LabelPair{
				{"label1", "test_0"},
				{"label1", "test_1"},
			},
			expected: fingerprints[:0],
		},
		{
			pairs: []metric.LabelPair{
				{"label1", "test_0"},
				{"label2", "test_1"},
			},
			expected: fingerprints[5:10],
		},
		{
			pairs: []metric.LabelPair{
				{"label1", "test_1"},
				{"label2", "test_2"},
			},
			expected: fingerprints[15:20],
		},
	}

	for _, mt := range matcherTests {
		resfps := storage.fingerprintsForLabelPairs(mt.pairs...)
		if len(mt.expected) != len(resfps) {
			t.Fatalf("expected %d matches for %q, found %d", len(mt.expected), mt.pairs, len(resfps))
		}
		for fp1 := range resfps {
			found := false
			for _, fp2 := range mt.expected {
				if fp1 == fp2 {
					found = true
					break
				}
			}
			if !found {
				t.Errorf("expected fingerprint %s for %q not in result", fp1, mt.pairs)
			}
		}
	}
}