internal/telemetry: replace TagSet with TagMap and TagPointer

This separates the concerns of tag collections that have to be iterated
and tag collections that need lookup by key.
Also make it so that events just carry a plain slice of tags.
We pass a TagMap down through the exporters and allow it to be
extended on the way.
We no longer need the event.Query method (or the event type)
We now exclusivley use Key as the identity, and no longer have a
common core implementation but just implement it directly in each
type.
This removes some confusion that was causing the same key through
different paths to end up with a different identity.

Change-Id: I61e47adcb397f4ca83dd90342b021dd8e9571ed3
Reviewed-on: https://go-review.googlesource.com/c/tools/+/224278
Run-TryBot: Ian Cottrell <iancottrell@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Emmanuel Odeke <emm.odeke@gmail.com>
diff --git a/internal/lsp/debug/metrics.go b/internal/lsp/debug/metrics.go
index 62e533c..796639f 100644
--- a/internal/lsp/debug/metrics.go
+++ b/internal/lsp/debug/metrics.go
@@ -49,7 +49,7 @@
 	}
 )
 
-func registerMetrics(m *metric.Exporter) {
+func registerMetrics(m *metric.Config) {
 	receivedBytes.Record(m, tag.ReceivedBytes)
 	sentBytes.Record(m, tag.SentBytes)
 	latency.Record(m, tag.Latency)
diff --git a/internal/lsp/debug/rpc.go b/internal/lsp/debug/rpc.go
index 71d0503..0f39c7c 100644
--- a/internal/lsp/debug/rpc.go
+++ b/internal/lsp/debug/rpc.go
@@ -91,20 +91,21 @@
 	Count int64
 }
 
-func (r *rpcs) ProcessEvent(ctx context.Context, ev event.Event) (context.Context, event.Event) {
+func (r *rpcs) ProcessEvent(ctx context.Context, ev event.Event, tagMap event.TagMap) context.Context {
 	if !ev.IsRecord() {
-		return ctx, ev
+		return ctx
 	}
 	r.mu.Lock()
 	defer r.mu.Unlock()
-	metrics := metric.Entries.Get(ev.Tags).([]metric.Data)
+	metrics := metric.Entries.Get(tagMap).([]metric.Data)
 	for _, data := range metrics {
 		for i, group := range data.Groups() {
 			set := &r.Inbound
-			if tag.RPCDirection.Get(group) == tag.Outbound {
+			groupTags := event.NewTagMap(group...)
+			if tag.RPCDirection.Get(groupTags) == tag.Outbound {
 				set = &r.Outbound
 			}
-			method := tag.Method.Get(group)
+			method := tag.Method.Get(groupTags)
 			index := sort.Search(len(*set), func(i int) bool {
 				return (*set)[i].Method >= method
 			})
@@ -120,7 +121,7 @@
 			case started.Name:
 				stats.Started = data.(*metric.Int64Data).Rows[i]
 			case completed.Name:
-				status := tag.StatusCode.Get(group)
+				status := tag.StatusCode.Get(groupTags)
 				var b *rpcCodeBucket
 				for c, entry := range stats.Codes {
 					if entry.Key == status {
@@ -180,7 +181,7 @@
 			stats.InProgress = stats.Started - stats.Completed
 		}
 	}
-	return ctx, ev
+	return ctx
 }
 
 func (r *rpcs) getData(req *http.Request) interface{} {
diff --git a/internal/lsp/debug/serve.go b/internal/lsp/debug/serve.go
index 11b731a..a4cafbc 100644
--- a/internal/lsp/debug/serve.go
+++ b/internal/lsp/debug/serve.go
@@ -52,7 +52,8 @@
 
 	LogWriter io.Writer
 
-	metrics    metric.Exporter
+	exporter event.Exporter
+
 	ocagent    *ocagent.Exporter
 	prometheus *prometheus.Exporter
 	rpcs       *rpcs
@@ -383,7 +384,7 @@
 }
 
 func init() {
-	event.SetExporter(makeExporter(os.Stderr))
+	event.SetExporter(makeGlobalExporter(os.Stderr))
 }
 
 func GetInstance(ctx context.Context) *Instance {
@@ -406,7 +407,6 @@
 		OCAgentConfig: agent,
 	}
 	i.LogWriter = os.Stderr
-	registerMetrics(&i.metrics)
 	ocConfig := ocagent.Discover()
 	//TODO: we should not need to adjust the discovered configuration
 	ocConfig.Address = i.OCAgentConfig
@@ -415,6 +415,7 @@
 	i.rpcs = &rpcs{}
 	i.traces = &traces{}
 	i.State = &State{}
+	i.exporter = makeInstanceExporter(i)
 	return context.WithValue(ctx, instanceKey, i)
 }
 
@@ -539,33 +540,42 @@
 	return nil
 }
 
-func makeExporter(stderr io.Writer) event.Exporter {
-	return func(ctx context.Context, ev event.Event) (context.Context, event.Event) {
-		ctx, ev = export.ContextSpan(ctx, ev)
+func makeGlobalExporter(stderr io.Writer) event.Exporter {
+	return func(ctx context.Context, ev event.Event, tags event.TagMap) context.Context {
 		i := GetInstance(ctx)
 		if ev.IsLog() && (ev.Error != nil || i == nil) {
 			fmt.Fprintf(stderr, "%v\n", ev)
 		}
-		ctx, ev = protocol.LogEvent(ctx, ev)
+		ctx = protocol.LogEvent(ctx, ev, tags)
 		if i == nil {
-			return ctx, ev
+			return ctx
 		}
-		ctx, ev = export.Tag(ctx, ev)
-		ctx, ev = i.metrics.ProcessEvent(ctx, ev)
+		return i.exporter(ctx, ev, tags)
+	}
+}
+
+func makeInstanceExporter(i *Instance) event.Exporter {
+	exporter := func(ctx context.Context, ev event.Event, tags event.TagMap) context.Context {
 		if i.ocagent != nil {
-			ctx, ev = i.ocagent.ProcessEvent(ctx, ev)
+			ctx = i.ocagent.ProcessEvent(ctx, ev, tags)
 		}
 		if i.prometheus != nil {
-			ctx, ev = i.prometheus.ProcessEvent(ctx, ev)
+			ctx = i.prometheus.ProcessEvent(ctx, ev, tags)
 		}
 		if i.rpcs != nil {
-			ctx, ev = i.rpcs.ProcessEvent(ctx, ev)
+			ctx = i.rpcs.ProcessEvent(ctx, ev, tags)
 		}
 		if i.traces != nil {
-			ctx, ev = i.traces.ProcessEvent(ctx, ev)
+			ctx = i.traces.ProcessEvent(ctx, ev, tags)
 		}
-		return ctx, ev
+		return ctx
 	}
+	metrics := metric.Config{}
+	registerMetrics(&metrics)
+	exporter = metrics.Exporter(exporter)
+	exporter = export.Spans(exporter)
+	exporter = export.Labels(exporter)
+	return exporter
 }
 
 type dataFunc func(*http.Request) interface{}
diff --git a/internal/lsp/debug/trace.go b/internal/lsp/debug/trace.go
index db75caf..52a6986 100644
--- a/internal/lsp/debug/trace.go
+++ b/internal/lsp/debug/trace.go
@@ -73,12 +73,12 @@
 	Tags   string
 }
 
-func (t *traces) ProcessEvent(ctx context.Context, ev event.Event) (context.Context, event.Event) {
+func (t *traces) ProcessEvent(ctx context.Context, ev event.Event, tags event.TagMap) context.Context {
 	t.mu.Lock()
 	defer t.mu.Unlock()
 	span := export.GetSpan(ctx)
 	if span == nil {
-		return ctx, ev
+		return ctx
 	}
 
 	switch {
@@ -93,19 +93,19 @@
 			SpanID:   span.ID.SpanID,
 			ParentID: span.ParentID,
 			Name:     span.Name,
-			Start:    span.Start,
-			Tags:     renderTags(span.Tags),
+			Start:    span.Start.At,
+			Tags:     renderTags(span.Start.Tags()),
 		}
 		t.unfinished[span.ID] = td
 		// and wire up parents if we have them
 		if !span.ParentID.IsValid() {
-			return ctx, ev
+			return ctx
 		}
 		parentID := export.SpanContext{TraceID: span.ID.TraceID, SpanID: span.ParentID}
 		parent, found := t.unfinished[parentID]
 		if !found {
 			// trace had an invalid parent, so it cannot itself be valid
-			return ctx, ev
+			return ctx
 		}
 		parent.Children = append(parent.Children, td)
 
@@ -113,17 +113,17 @@
 		// finishing, must be already in the map
 		td, found := t.unfinished[span.ID]
 		if !found {
-			return ctx, ev // if this happens we are in a bad place
+			return ctx // if this happens we are in a bad place
 		}
 		delete(t.unfinished, span.ID)
 
-		td.Finish = span.Finish
-		td.Duration = span.Finish.Sub(span.Start)
+		td.Finish = span.Finish.At
+		td.Duration = span.Finish.At.Sub(span.Start.At)
 		td.Events = make([]traceEvent, len(span.Events))
 		for i, event := range span.Events {
 			td.Events[i] = traceEvent{
 				Time: event.At,
-				Tags: renderTags(event.Tags),
+				Tags: renderTags(event.Tags()),
 			}
 		}
 
@@ -140,7 +140,7 @@
 			fillOffsets(td, td.Start)
 		}
 	}
-	return ctx, ev
+	return ctx
 }
 
 func (t *traces) getData(req *http.Request) interface{} {
@@ -169,11 +169,11 @@
 	}
 }
 
-func renderTags(tags event.TagSet) string {
+func renderTags(tags event.TagIterator) string {
 	buf := &bytes.Buffer{}
-	for i := tags.Iterator(); i.Next(); {
-		tag := i.Value()
-		fmt.Fprintf(buf, "%s=%q ", tag.Key().Name(), tag.Value())
+	for ; tags.Valid(); tags.Advance() {
+		tag := tags.Tag()
+		fmt.Fprintf(buf, "%s=%q ", tag.Key.Name(), tag.Value)
 	}
 	return buf.String()
 }
diff --git a/internal/lsp/protocol/context.go b/internal/lsp/protocol/context.go
index 4d55a22..a1b8822 100644
--- a/internal/lsp/protocol/context.go
+++ b/internal/lsp/protocol/context.go
@@ -18,18 +18,18 @@
 	return context.WithValue(ctx, clientKey, client)
 }
 
-func LogEvent(ctx context.Context, ev event.Event) (context.Context, event.Event) {
+func LogEvent(ctx context.Context, ev event.Event, tags event.TagMap) context.Context {
 	if !ev.IsLog() {
-		return ctx, ev
+		return ctx
 	}
 	client, ok := ctx.Value(clientKey).(Client)
 	if !ok {
-		return ctx, ev
+		return ctx
 	}
 	msg := &LogMessageParams{Type: Info, Message: fmt.Sprint(ev)}
 	if ev.Error != nil {
 		msg.Type = Error
 	}
 	go client.LogMessage(xcontext.Detach(ctx), msg)
-	return ctx, ev
+	return ctx
 }
diff --git a/internal/telemetry/bench_test.go b/internal/telemetry/bench_test.go
index 2568304..905aee0 100644
--- a/internal/telemetry/bench_test.go
+++ b/internal/telemetry/bench_test.go
@@ -142,9 +142,4 @@
 	return len(b), nil
 }
 
-var noopLogger = export.LogWriter(new(noopWriter), false)
-
-func noopExporter(ctx context.Context, ev event.Event) (context.Context, event.Event) {
-	ctx, ev = export.ContextSpan(ctx, ev)
-	return noopLogger(ctx, ev)
-}
+var noopExporter = export.Spans(export.LogWriter(new(noopWriter), false))
diff --git a/internal/telemetry/event/event.go b/internal/telemetry/event/event.go
index adf5f51..5c5e165 100644
--- a/internal/telemetry/event/event.go
+++ b/internal/telemetry/event/event.go
@@ -17,7 +17,6 @@
 	StartSpanType
 	EndSpanType
 	LabelType
-	QueryType
 	DetachType
 	RecordType
 )
@@ -27,14 +26,14 @@
 	At      time.Time
 	Message string
 	Error   error
-	Tags    TagSet
+
+	tags []Tag
 }
 
 func (e Event) IsLog() bool       { return e.Type == LogType }
 func (e Event) IsEndSpan() bool   { return e.Type == EndSpanType }
 func (e Event) IsStartSpan() bool { return e.Type == StartSpanType }
 func (e Event) IsLabel() bool     { return e.Type == LabelType }
-func (e Event) IsQuery() bool     { return e.Type == QueryType }
 func (e Event) IsDetach() bool    { return e.Type == DetachType }
 func (e Event) IsRecord() bool    { return e.Type == RecordType }
 
@@ -50,8 +49,19 @@
 			fmt.Fprintf(f, ": %v", e.Error)
 		}
 	}
-	for i := e.Tags.Iterator(); i.Next(); {
-		tag := i.Value()
-		fmt.Fprintf(f, "\n\t%s = %v", tag.key.name, tag.value)
+	for it := e.Tags(); it.Valid(); it.Advance() {
+		tag := it.Tag()
+		fmt.Fprintf(f, "\n\t%s = %v", tag.Key.Name(), tag.Value)
 	}
 }
+
+func (ev Event) Tags() TagIterator {
+	if len(ev.tags) == 0 {
+		return TagIterator{}
+	}
+	return NewTagIterator(ev.tags...)
+}
+
+func (ev Event) Map() TagMap {
+	return NewTagMap(ev.tags...)
+}
diff --git a/internal/telemetry/event/export.go b/internal/telemetry/event/export.go
index 362ba29..82afb89 100644
--- a/internal/telemetry/event/export.go
+++ b/internal/telemetry/event/export.go
@@ -12,7 +12,7 @@
 
 // Exporter is a function that handles events.
 // It may return a modified context and event.
-type Exporter func(context.Context, Event) (context.Context, Event)
+type Exporter func(context.Context, Event, TagMap) context.Context
 
 var (
 	exporter unsafe.Pointer
@@ -34,11 +34,11 @@
 }
 
 // ProcessEvent is called to deliver an event to the global exporter.
-func ProcessEvent(ctx context.Context, ev Event) (context.Context, Event) {
+func ProcessEvent(ctx context.Context, ev Event) context.Context {
 	exporterPtr := (*Exporter)(atomic.LoadPointer(&exporter))
 	if exporterPtr == nil {
-		return ctx, ev
+		return ctx
 	}
 	// and now also hand the event of to the current exporter
-	return (*exporterPtr)(ctx, ev)
+	return (*exporterPtr)(ctx, ev, ev.Map())
 }
diff --git a/internal/telemetry/event/key.go b/internal/telemetry/event/key.go
index 43baea0..6a982a6 100644
--- a/internal/telemetry/event/key.go
+++ b/internal/telemetry/event/key.go
@@ -11,14 +11,10 @@
 
 // Key is the interface shared by all key implementations.
 type Key interface {
-	// Identity returns the underlying key identity.
-	Identity() interface{}
 	// Name returns the key name.
 	Name() string
 	// Description returns a string that can be used to describe the value.
 	Description() string
-	// OfValue creates a new Tag with this key and the supplied untyped value.
-	OfValue(interface{}) Tag
 }
 
 // key is used as the identity of a Tag.
@@ -29,312 +25,402 @@
 	description string
 }
 
-func newKey(name, description string) *key   { return &key{name: name, description: description} }
-func (k *key) Name() string                  { return k.name }
-func (k *key) Description() string           { return k.description }
-func (k *key) Identity() interface{}         { return k }
-func (k *key) OfValue(value interface{}) Tag { return Tag{key: k, value: value} }
-
 // ValueKey represents a key for untyped values.
-type ValueKey struct{ *key }
-
-// NewKey creates a new Key for untyped values.
-func NewKey(name, description string) ValueKey {
-	return ValueKey{newKey(name, description)}
+type ValueKey struct {
+	name        string
+	description string
 }
 
-// Get can be used to get a tag for the key from a TagList.
-func (k ValueKey) Get(tags TagSet) interface{} {
-	if t := tags.find(k.key); t.key != nil {
-		return t.value
+// NewKey creates a new Key for untyped values.
+func NewKey(name, description string) *ValueKey {
+	return &ValueKey{name: name, description: description}
+}
+
+func (k *ValueKey) Name() string        { return k.name }
+func (k *ValueKey) Description() string { return k.description }
+
+// Get can be used to get a tag for the key from a TagMap.
+func (k *ValueKey) Get(tags TagMap) interface{} {
+	if t := tags.Find(k); t.Valid() {
+		return t.Value
 	}
 	return nil
 }
 
 // Of creates a new Tag with this key and the supplied value.
-func (k ValueKey) Of(value interface{}) Tag { return Tag{key: k.key, value: value} }
+func (k *ValueKey) Of(value interface{}) Tag { return Tag{Key: k, Value: value} }
 
 // IntKey represents a key
-type IntKey struct{ *key }
-
-// NewIntKey creates a new Key for int values.
-func NewIntKey(name, description string) IntKey {
-	return IntKey{newKey(name, description)}
+type IntKey struct {
+	name        string
+	description string
 }
 
-// Of creates a new Tag with this key and the supplied value.
-func (k IntKey) Of(v int) Tag { return Tag{key: k.key, value: v} }
+// NewIntKey creates a new Key for int values.
+func NewIntKey(name, description string) *IntKey {
+	return &IntKey{name: name, description: description}
+}
 
-// Get can be used to get a tag for the key from a TagSet.
-func (k IntKey) Get(tags TagSet) int {
-	if t := tags.find(k.key); t.key != nil {
-		return t.value.(int)
+func (k *IntKey) Name() string        { return k.name }
+func (k *IntKey) Description() string { return k.description }
+
+// Of creates a new Tag with this key and the supplied value.
+func (k *IntKey) Of(v int) Tag { return Tag{Key: k, Value: v} }
+
+// Get can be used to get a tag for the key from a TagMap.
+func (k *IntKey) Get(tags TagMap) int {
+	if t := tags.Find(k); t.Valid() {
+		return t.Value.(int)
 	}
 	return 0
 }
 
 // Int8Key represents a key
-type Int8Key struct{ *key }
-
-// NewInt8Key creates a new Key for int8 values.
-func NewInt8Key(name, description string) Int8Key {
-	return Int8Key{newKey(name, description)}
+type Int8Key struct {
+	name        string
+	description string
 }
 
-// Of creates a new Tag with this key and the supplied value.
-func (k Int8Key) Of(v int8) Tag { return Tag{key: k.key, value: v} }
+// NewInt8Key creates a new Key for int8 values.
+func NewInt8Key(name, description string) *Int8Key {
+	return &Int8Key{name: name, description: description}
+}
 
-// Get can be used to get a tag for the key from a TagSet.
-func (k Int8Key) Get(tags TagSet) int8 {
-	if t := tags.find(k.key); t.key != nil {
-		return t.value.(int8)
+func (k *Int8Key) Name() string        { return k.name }
+func (k *Int8Key) Description() string { return k.description }
+
+// Of creates a new Tag with this key and the supplied value.
+func (k *Int8Key) Of(v int8) Tag { return Tag{Key: k, Value: v} }
+
+// Get can be used to get a tag for the key from a TagMap.
+func (k *Int8Key) Get(tags TagMap) int8 {
+	if t := tags.Find(k); t.Valid() {
+		return t.Value.(int8)
 	}
 	return 0
 }
 
 // Int16Key represents a key
-type Int16Key struct{ *key }
-
-// NewInt16Key creates a new Key for int16 values.
-func NewInt16Key(name, description string) Int16Key {
-	return Int16Key{newKey(name, description)}
+type Int16Key struct {
+	name        string
+	description string
 }
 
-// Of creates a new Tag with this key and the supplied value.
-func (k Int16Key) Of(v int16) Tag { return Tag{key: k.key, value: v} }
+// NewInt16Key creates a new Key for int16 values.
+func NewInt16Key(name, description string) *Int16Key {
+	return &Int16Key{name: name, description: description}
+}
 
-// Get can be used to get a tag for the key from a TagSet.
-func (k Int16Key) Get(tags TagSet) int16 {
-	if t := tags.find(k.key); t.key != nil {
-		return t.value.(int16)
+func (k *Int16Key) Name() string        { return k.name }
+func (k *Int16Key) Description() string { return k.description }
+
+// Of creates a new Tag with this key and the supplied value.
+func (k *Int16Key) Of(v int16) Tag { return Tag{Key: k, Value: v} }
+
+// Get can be used to get a tag for the key from a TagMap.
+func (k *Int16Key) Get(tags TagMap) int16 {
+	if t := tags.Find(k); t.Valid() {
+		return t.Value.(int16)
 	}
 	return 0
 }
 
 // Int32Key represents a key
-type Int32Key struct{ *key }
-
-// NewInt32Key creates a new Key for int32 values.
-func NewInt32Key(name, description string) Int32Key {
-	return Int32Key{newKey(name, description)}
+type Int32Key struct {
+	name        string
+	description string
 }
 
-// Of creates a new Tag with this key and the supplied value.
-func (k Int32Key) Of(v int32) Tag { return Tag{key: k.key, value: v} }
+// NewInt32Key creates a new Key for int32 values.
+func NewInt32Key(name, description string) *Int32Key {
+	return &Int32Key{name: name, description: description}
+}
 
-// Get can be used to get a tag for the key from a TagSet.
-func (k Int32Key) Get(tags TagSet) int32 {
-	if t := tags.find(k.key); t.key != nil {
-		return t.value.(int32)
+func (k *Int32Key) Name() string        { return k.name }
+func (k *Int32Key) Description() string { return k.description }
+
+// Of creates a new Tag with this key and the supplied value.
+func (k *Int32Key) Of(v int32) Tag { return Tag{Key: k, Value: v} }
+
+// Get can be used to get a tag for the key from a TagMap.
+func (k *Int32Key) Get(tags TagMap) int32 {
+	if t := tags.Find(k); t.Valid() {
+		return t.Value.(int32)
 	}
 	return 0
 }
 
 // Int64Key represents a key
-type Int64Key struct{ *key }
-
-// NewInt64Key creates a new Key for int64 values.
-func NewInt64Key(name, description string) Int64Key {
-	return Int64Key{newKey(name, description)}
+type Int64Key struct {
+	name        string
+	description string
 }
 
-// Of creates a new Tag with this key and the supplied value.
-func (k Int64Key) Of(v int64) Tag { return Tag{key: k.key, value: v} }
+// NewInt64Key creates a new Key for int64 values.
+func NewInt64Key(name, description string) *Int64Key {
+	return &Int64Key{name: name, description: description}
+}
 
-// Get can be used to get a tag for the key from a TagSet.
-func (k Int64Key) Get(tags TagSet) int64 {
-	if t := tags.find(k.key); t.key != nil {
-		return t.value.(int64)
+func (k *Int64Key) Name() string        { return k.name }
+func (k *Int64Key) Description() string { return k.description }
+
+// Of creates a new Tag with this key and the supplied value.
+func (k *Int64Key) Of(v int64) Tag { return Tag{Key: k, Value: v} }
+
+// Get can be used to get a tag for the key from a TagMap.
+func (k *Int64Key) Get(tags TagMap) int64 {
+	if t := tags.Find(k); t.Valid() {
+		return t.Value.(int64)
 	}
 	return 0
 }
 
 // UIntKey represents a key
-type UIntKey struct{ *key }
-
-// NewUIntKey creates a new Key for uint values.
-func NewUIntKey(name, description string) UIntKey {
-	return UIntKey{newKey(name, description)}
+type UIntKey struct {
+	name        string
+	description string
 }
 
-// Of creates a new Tag with this key and the supplied value.
-func (k UIntKey) Of(v uint) Tag { return Tag{key: k.key, value: v} }
+// NewUIntKey creates a new Key for uint values.
+func NewUIntKey(name, description string) *UIntKey {
+	return &UIntKey{name: name, description: description}
+}
 
-// Get can be used to get a tag for the key from a TagSet.
-func (k UIntKey) Get(tags TagSet) uint {
-	if t := tags.find(k.key); t.key != nil {
-		return t.value.(uint)
+func (k *UIntKey) Name() string        { return k.name }
+func (k *UIntKey) Description() string { return k.description }
+
+// Of creates a new Tag with this key and the supplied value.
+func (k *UIntKey) Of(v uint) Tag { return Tag{Key: k, Value: v} }
+
+// Get can be used to get a tag for the key from a TagMap.
+func (k *UIntKey) Get(tags TagMap) uint {
+	if t := tags.Find(k); t.Valid() {
+		return t.Value.(uint)
 	}
 	return 0
 }
 
 // UInt8Key represents a key
-type UInt8Key struct{ *key }
-
-// NewUInt8Key creates a new Key for uint8 values.
-func NewUInt8Key(name, description string) UInt8Key {
-	return UInt8Key{newKey(name, description)}
+type UInt8Key struct {
+	name        string
+	description string
 }
 
-// Of creates a new Tag with this key and the supplied value.
-func (k UInt8Key) Of(v uint8) Tag { return Tag{key: k.key, value: v} }
+// NewUInt8Key creates a new Key for uint8 values.
+func NewUInt8Key(name, description string) *UInt8Key {
+	return &UInt8Key{name: name, description: description}
+}
 
-// Get can be used to get a tag for the key from a TagSet.
-func (k UInt8Key) Get(tags TagSet) uint8 {
-	if t := tags.find(k.key); t.key != nil {
-		return t.value.(uint8)
+func (k *UInt8Key) Name() string        { return k.name }
+func (k *UInt8Key) Description() string { return k.description }
+
+// Of creates a new Tag with this key and the supplied value.
+func (k *UInt8Key) Of(v uint8) Tag { return Tag{Key: k, Value: v} }
+
+// Get can be used to get a tag for the key from a TagMap.
+func (k *UInt8Key) Get(tags TagMap) uint8 {
+	if t := tags.Find(k); t.Valid() {
+		return t.Value.(uint8)
 	}
 	return 0
 }
 
 // UInt16Key represents a key
-type UInt16Key struct{ *key }
-
-// NewUInt16Key creates a new Key for uint16 values.
-func NewUInt16Key(name, description string) UInt16Key {
-	return UInt16Key{newKey(name, description)}
+type UInt16Key struct {
+	name        string
+	description string
 }
 
-// Of creates a new Tag with this key and the supplied value.
-func (k UInt16Key) Of(v uint16) Tag { return Tag{key: k.key, value: v} }
+// NewUInt16Key creates a new Key for uint16 values.
+func NewUInt16Key(name, description string) *UInt16Key {
+	return &UInt16Key{name: name, description: description}
+}
 
-// Get can be used to get a tag for the key from a TagSet.
-func (k UInt16Key) Get(tags TagSet) uint16 {
-	if t := tags.find(k.key); t.key != nil {
-		return t.value.(uint16)
+func (k *UInt16Key) Name() string        { return k.name }
+func (k *UInt16Key) Description() string { return k.description }
+
+// Of creates a new Tag with this key and the supplied value.
+func (k *UInt16Key) Of(v uint16) Tag { return Tag{Key: k, Value: v} }
+
+// Get can be used to get a tag for the key from a TagMap.
+func (k *UInt16Key) Get(tags TagMap) uint16 {
+	if t := tags.Find(k); t.Valid() {
+		return t.Value.(uint16)
 	}
 	return 0
 }
 
 // UInt32Key represents a key
-type UInt32Key struct{ *key }
-
-// NewUInt32Key creates a new Key for uint32 values.
-func NewUInt32Key(name, description string) UInt32Key {
-	return UInt32Key{newKey(name, description)}
+type UInt32Key struct {
+	name        string
+	description string
 }
 
-// Of creates a new Tag with this key and the supplied value.
-func (k UInt32Key) Of(v uint32) Tag { return Tag{key: k.key, value: v} }
+// NewUInt32Key creates a new Key for uint32 values.
+func NewUInt32Key(name, description string) *UInt32Key {
+	return &UInt32Key{name: name, description: description}
+}
 
-// Get can be used to get a tag for the key from a TagSet.
-func (k UInt32Key) Get(tags TagSet) uint32 {
-	if t := tags.find(k.key); t.key != nil {
-		return t.value.(uint32)
+func (k *UInt32Key) Name() string        { return k.name }
+func (k *UInt32Key) Description() string { return k.description }
+
+// Of creates a new Tag with this key and the supplied value.
+func (k *UInt32Key) Of(v uint32) Tag { return Tag{Key: k, Value: v} }
+
+// Get can be used to get a tag for the key from a TagMap.
+func (k *UInt32Key) Get(tags TagMap) uint32 {
+	if t := tags.Find(k); t.Valid() {
+		return t.Value.(uint32)
 	}
 	return 0
 }
 
 // UInt64Key represents a key
-type UInt64Key struct{ *key }
-
-// NewUInt64Key creates a new Key for uint64 values.
-func NewUInt64Key(name, description string) UInt64Key {
-	return UInt64Key{newKey(name, description)}
+type UInt64Key struct {
+	name        string
+	description string
 }
 
-// Of creates a new Tag with this key and the supplied value.
-func (k UInt64Key) Of(v uint64) Tag { return Tag{key: k.key, value: v} }
+// NewUInt64Key creates a new Key for uint64 values.
+func NewUInt64Key(name, description string) *UInt64Key {
+	return &UInt64Key{name: name, description: description}
+}
 
-// Get can be used to get a tag for the key from a TagSet.
-func (k UInt64Key) Get(tags TagSet) uint64 {
-	if t := tags.find(k.key); t.key != nil {
-		return t.value.(uint64)
+func (k *UInt64Key) Name() string        { return k.name }
+func (k *UInt64Key) Description() string { return k.description }
+
+// Of creates a new Tag with this key and the supplied value.
+func (k *UInt64Key) Of(v uint64) Tag { return Tag{Key: k, Value: v} }
+
+// Get can be used to get a tag for the key from a TagMap.
+func (k *UInt64Key) Get(tags TagMap) uint64 {
+	if t := tags.Find(k); t.Valid() {
+		return t.Value.(uint64)
 	}
 	return 0
 }
 
 // Float32Key represents a key
-type Float32Key struct{ *key }
-
-// NewFloat32Key creates a new Key for float32 values.
-func NewFloat32Key(name, description string) Float32Key {
-	return Float32Key{newKey(name, description)}
+type Float32Key struct {
+	name        string
+	description string
 }
 
-// Of creates a new Tag with this key and the supplied value.
-func (k Float32Key) Of(v float32) Tag { return Tag{key: k.key, value: v} }
+// NewFloat32Key creates a new Key for float32 values.
+func NewFloat32Key(name, description string) *Float32Key {
+	return &Float32Key{name: name, description: description}
+}
 
-// Get can be used to get a tag for the key from a TagSet.
-func (k Float32Key) Get(tags TagSet) float32 {
-	if t := tags.find(k.key); t.key != nil {
-		return t.value.(float32)
+func (k *Float32Key) Name() string        { return k.name }
+func (k *Float32Key) Description() string { return k.description }
+
+// Of creates a new Tag with this key and the supplied value.
+func (k *Float32Key) Of(v float32) Tag { return Tag{Key: k, Value: v} }
+
+// Get can be used to get a tag for the key from a TagMap.
+func (k *Float32Key) Get(tags TagMap) float32 {
+	if t := tags.Find(k); t.Valid() {
+		return t.Value.(float32)
 	}
 	return 0
 }
 
 // Float64Key represents a key
-type Float64Key struct{ *key }
-
-// NewFloat64Key creates a new Key for int64 values.
-func NewFloat64Key(name, description string) Float64Key {
-	return Float64Key{newKey(name, description)}
+type Float64Key struct {
+	name        string
+	description string
 }
 
-// Of creates a new Tag with this key and the supplied value.
-func (k Float64Key) Of(v float64) Tag { return Tag{key: k.key, value: v} }
+// NewFloat64Key creates a new Key for int64 values.
+func NewFloat64Key(name, description string) *Float64Key {
+	return &Float64Key{name: name, description: description}
+}
 
-// Get can be used to get a tag for the key from a TagSet.
-func (k Float64Key) Get(tags TagSet) float64 {
-	if t := tags.find(k.key); t.key != nil {
-		return t.value.(float64)
+func (k *Float64Key) Name() string        { return k.name }
+func (k *Float64Key) Description() string { return k.description }
+
+// Of creates a new Tag with this key and the supplied value.
+func (k *Float64Key) Of(v float64) Tag { return Tag{Key: k, Value: v} }
+
+// Get can be used to get a tag for the key from a TagMap.
+func (k *Float64Key) Get(tags TagMap) float64 {
+	if t := tags.Find(k); t.Valid() {
+		return t.Value.(float64)
 	}
 	return 0
 }
 
 // StringKey represents a key
-type StringKey struct{ *key }
-
-// NewStringKey creates a new Key for int64 values.
-func NewStringKey(name, description string) StringKey {
-	return StringKey{newKey(name, description)}
+type StringKey struct {
+	name        string
+	description string
 }
 
-// Of creates a new Tag with this key and the supplied value.
-func (k StringKey) Of(v string) Tag { return Tag{key: k.key, value: v} }
+// NewStringKey creates a new Key for int64 values.
+func NewStringKey(name, description string) *StringKey {
+	return &StringKey{name: name, description: description}
+}
 
-// Get can be used to get a tag for the key from a TagSet.
-func (k StringKey) Get(tags TagSet) string {
-	if t := tags.find(k.key); t.key != nil {
-		return t.value.(string)
+func (k *StringKey) Name() string        { return k.name }
+func (k *StringKey) Description() string { return k.description }
+
+// Of creates a new Tag with this key and the supplied value.
+func (k *StringKey) Of(v string) Tag { return Tag{Key: k, Value: v} }
+
+// Get can be used to get a tag for the key from a TagMap.
+func (k *StringKey) Get(tags TagMap) string {
+	if t := tags.Find(k); t.Valid() {
+		return t.Value.(string)
 	}
 	return ""
 }
 
 // BooleanKey represents a key
-type BooleanKey struct{ *key }
-
-// NewBooleanKey creates a new Key for bool values.
-func NewBooleanKey(name, description string) BooleanKey {
-	return BooleanKey{newKey(name, description)}
+type BooleanKey struct {
+	name        string
+	description string
 }
 
-// Of creates a new Tag with this key and the supplied value.
-func (k BooleanKey) Of(v bool) Tag { return Tag{key: k.key, value: v} }
+// NewBooleanKey creates a new Key for bool values.
+func NewBooleanKey(name, description string) *BooleanKey {
+	return &BooleanKey{name: name, description: description}
+}
 
-// Get can be used to get a tag for the key from a TagSet.
-func (k BooleanKey) Get(tags TagSet) bool {
-	if t := tags.find(k.key); t.key != nil {
-		return t.value.(bool)
+func (k *BooleanKey) Name() string        { return k.name }
+func (k *BooleanKey) Description() string { return k.description }
+
+// Of creates a new Tag with this key and the supplied value.
+func (k *BooleanKey) Of(v bool) Tag { return Tag{Key: k, Value: v} }
+
+// Get can be used to get a tag for the key from a TagMap.
+func (k *BooleanKey) Get(tags TagMap) bool {
+	if t := tags.Find(k); t.Valid() {
+		return t.Value.(bool)
 	}
 	return false
 }
 
 // ErrorKey represents a key
-type ErrorKey struct{ *key }
-
-// NewErrorKey creates a new Key for int64 values.
-func NewErrorKey(name, description string) ErrorKey {
-	return ErrorKey{newKey(name, description)}
+type ErrorKey struct {
+	name        string
+	description string
 }
 
-// Of creates a new Tag with this key and the supplied value.
-func (k ErrorKey) Of(v error) Tag { return Tag{key: k.key, value: v} }
+// NewErrorKey creates a new Key for int64 values.
+func NewErrorKey(name, description string) *ErrorKey {
+	return &ErrorKey{name: name, description: description}
+}
 
-// Get can be used to get a tag for the key from a TagSet.
-func (k ErrorKey) Get(tags TagSet) error {
-	if t := tags.find(k.key); t.key != nil {
-		return t.value.(error)
+func (k *ErrorKey) Name() string        { return k.name }
+func (k *ErrorKey) Description() string { return k.description }
+
+// Of creates a new Tag with this key and the supplied value.
+func (k *ErrorKey) Of(v error) Tag { return Tag{Key: k, Value: v} }
+
+// Get can be used to get a tag for the key from a TagMap.
+func (k *ErrorKey) Get(tags TagMap) error {
+	if t := tags.Find(k); t.Valid() {
+		return t.Value.(error)
 	}
 	return nil
 }
diff --git a/internal/telemetry/event/label.go b/internal/telemetry/event/label.go
index bdc579a..7faec1e 100644
--- a/internal/telemetry/event/label.go
+++ b/internal/telemetry/event/label.go
@@ -11,24 +11,9 @@
 
 // Label sends a label event to the exporter with the supplied tags.
 func Label(ctx context.Context, tags ...Tag) context.Context {
-	ctx, _ = ProcessEvent(ctx, Event{
+	return ProcessEvent(ctx, Event{
 		Type: LabelType,
 		At:   time.Now(),
-		Tags: newTagSet(tags),
+		tags: tags,
 	})
-	return ctx
-}
-
-// Query sends a query event to the exporter with the supplied keys.
-// The returned tags will have up to date values if the exporter supports it.
-func Query(ctx context.Context, keys ...Key) TagSet {
-	tags := make([]Tag, len(keys))
-	for i, k := range keys {
-		tags[i] = k.OfValue(nil)
-	}
-	_, ev := ProcessEvent(ctx, Event{
-		Type: QueryType,
-		Tags: newTagSet(tags),
-	})
-	return ev.Tags
 }
diff --git a/internal/telemetry/event/log.go b/internal/telemetry/event/log.go
index 4446043..6029585 100644
--- a/internal/telemetry/event/log.go
+++ b/internal/telemetry/event/log.go
@@ -15,7 +15,7 @@
 	ProcessEvent(ctx, Event{
 		Type: LogType,
 		At:   time.Now(),
-		Tags: newTagSet(tags),
+		tags: tags,
 	})
 }
 
@@ -26,7 +26,7 @@
 		Type:    LogType,
 		At:      time.Now(),
 		Message: message,
-		Tags:    newTagSet(tags),
+		tags:    tags,
 	})
 }
 
@@ -43,6 +43,6 @@
 		At:      time.Now(),
 		Message: message,
 		Error:   err,
-		Tags:    newTagSet(tags),
+		tags:    tags,
 	})
 }
diff --git a/internal/telemetry/event/metric.go b/internal/telemetry/event/metric.go
index b5f9e95..7d4aaa5 100644
--- a/internal/telemetry/event/metric.go
+++ b/internal/telemetry/event/metric.go
@@ -13,6 +13,6 @@
 	ProcessEvent(ctx, Event{
 		Type: RecordType,
 		At:   time.Now(),
-		Tags: newTagSet(tags),
+		tags: tags,
 	})
 }
diff --git a/internal/telemetry/event/tag.go b/internal/telemetry/event/tag.go
index 96c79f1..7aa6ebb 100644
--- a/internal/telemetry/event/tag.go
+++ b/internal/telemetry/event/tag.go
@@ -11,158 +11,224 @@
 // Tag holds a key and value pair.
 // It is normally used when passing around lists of tags.
 type Tag struct {
-	key   *key
-	value interface{}
+	Key   Key
+	Value interface{}
 }
 
-// TagSet is a collection of Tags.
-// It provides a way to create new tag sets by adding new tags to an existing
-// set, and preserves the order in which tags were added when iterating.
-// Tags can also be searched for in the set by their key.
-type TagSet struct {
-	list tagList
+// TagMap is the interface to a collection of Tags indexed by key.
+type TagMap interface {
+	// IsEmpty returns true if the map holds no tags.
+	IsEmpty() bool
+	// Find returns the tag that matches the supplied key.
+	Find(key interface{}) Tag
 }
 
-type tagList struct {
-	tags []Tag
-	next *tagList
+// TagPointer is the interface to something that provides an iterable
+// list of tags.
+type TagPointer interface {
+	// Next advances to the next entry in the list and return a TagIterator for it.
+	// It will return nil if there are no more entries.
+	Next() TagPointer
+	// Tag returns the tag the pointer is for.
+	Tag() Tag
 }
 
-// TagIterator is used to iterate through all the tags in a TagSet.
+// TagIterator is used to iterate through tags using TagPointer.
+// It is a small helper that will normally fully inline to make it easier to
+// manage the fact that pointer advance returns a new pointer rather than
+// moving the existing one.
 type TagIterator struct {
-	list  tagList
-	index int
+	ptr TagPointer
+}
+
+// tagPointer implements TagPointer over a simple list of tags.
+type tagPointer struct {
+	tags []Tag
+}
+
+// tagPointer wraps a TagPointer filtering out specific tags.
+type tagFilter struct {
+	filter     []Key
+	underlying TagPointer
+}
+
+// tagPointerChain implements TagMap for a list of underlying TagMap.
+type tagPointerChain struct {
+	ptrs []TagPointer
+}
+
+// tagMap implements TagMap for a simple list of tags.
+type tagMap struct {
+	tags []Tag
+}
+
+// tagMapChain implements TagMap for a list of underlying TagMap.
+type tagMapChain struct {
+	maps []TagMap
 }
 
 // Key returns the key for this Tag.
-func (t Tag) Key() Key { return t.key }
-
-// Value returns the value for this Tag.
-func (t Tag) Value() interface{} { return t.value }
+func (t Tag) Valid() bool { return t.Key != nil }
 
 // Format is used for debug printing of tags.
 func (t Tag) Format(f fmt.State, r rune) {
-	if t.key == nil {
+	if !t.Valid() {
 		fmt.Fprintf(f, `nil`)
 		return
 	}
-	fmt.Fprintf(f, `%v="%v"`, t.key.name, t.value)
+	fmt.Fprintf(f, `%v="%v"`, t.Key.Name(), t.Value)
 }
 
-func newTagSet(tags []Tag) TagSet {
-	return TagSet{list: tagList{tags: tags}}
+func (i *TagIterator) Valid() bool {
+	return i.ptr != nil
 }
 
-// FindAll returns corresponding tags for each key in keys.
-// The resulting TagSet will have one entry for each key in the same order
-// as they were passed in, and if no tag is found for a key Tag at its
-// corresponding index will also have no value.
-func (s TagSet) FindAll(keys []Key) TagSet {
-	tags := make([]Tag, len(keys))
-	for i, key := range keys {
-		tags[i] = s.find(key.Identity())
+func (i *TagIterator) Advance() {
+	i.ptr = i.ptr.Next()
+}
+
+func (i *TagIterator) Tag() Tag {
+	return i.ptr.Tag()
+}
+
+func (i tagPointer) Next() TagPointer {
+	// loop until we are on a valid tag
+	for {
+		// move on one tag
+		i.tags = i.tags[1:]
+		// check if we have exhausted the current list
+		if len(i.tags) == 0 {
+			// no more tags, so no more iterator
+			return nil
+		}
+		// if the tag is valid, we are done
+		if i.tags[0].Valid() {
+			return i
+		}
 	}
-	return TagSet{list: tagList{tags: tags}}
 }
 
-func (s TagSet) find(key interface{}) Tag {
-	//TODO: do we want/need a faster access pattern?
-	for i := s.Iterator(); i.Next(); {
-		tag := i.Value()
-		if tag.key == key {
+func (i tagPointer) Tag() Tag {
+	return i.tags[0]
+}
+
+func (i tagFilter) Next() TagPointer {
+	// loop until we are on a valid tag
+	for {
+		i.underlying = i.underlying.Next()
+		if i.underlying == nil {
+			return nil
+		}
+		if !i.filtered() {
+			return i
+		}
+	}
+}
+
+func (i tagFilter) filtered() bool {
+	tag := i.underlying.Tag()
+	for _, f := range i.filter {
+		if tag.Key == f {
+			return true
+		}
+	}
+	return false
+}
+
+func (i tagFilter) Tag() Tag {
+	return i.underlying.Tag()
+}
+
+func (i tagPointerChain) Next() TagPointer {
+	i.ptrs[0] = i.ptrs[0].Next()
+	if i.ptrs[0] == nil {
+		i.ptrs = i.ptrs[1:]
+	}
+	if len(i.ptrs) == 0 {
+		return nil
+	}
+	return i
+}
+
+func (i tagPointerChain) Tag() Tag {
+	return i.ptrs[0].Tag()
+}
+
+func (l tagMap) Find(key interface{}) Tag {
+	for _, tag := range l.tags {
+		if tag.Key == key {
 			return tag
 		}
 	}
 	return Tag{}
 }
 
-// Format pretty prints a list.
-// It is intended only for debugging.
-func (s TagSet) Format(f fmt.State, r rune) {
-	printed := false
-	for i := s.Iterator(); i.Next(); {
-		tag := i.Value()
-		if tag.value == nil {
-			continue
+func (l tagMap) IsEmpty() bool {
+	return len(l.tags) == 0
+}
+
+func (c tagMapChain) Find(key interface{}) Tag {
+	for _, src := range c.maps {
+		tag := src.Find(key)
+		if tag.Valid() {
+			return tag
 		}
-		if printed {
-			fmt.Fprint(f, ",")
+	}
+	return Tag{}
+}
+
+func (c tagMapChain) IsEmpty() bool {
+	for _, src := range c.maps {
+		if !src.IsEmpty() {
+			return false
 		}
-		fmt.Fprint(f, tag)
-		printed = true
 	}
-}
-
-// Add returns a new TagSet where the supplied tags are included and
-// override any tags already in this TagSet.
-func (s TagSet) Add(tags ...Tag) TagSet {
-	if len(tags) <= 0 {
-		// we don't allow empty tag lists in the chain
-		return s
-	}
-	if len(s.list.tags) <= 0 {
-		// adding to an empty list, no need for a chain
-		s.list.tags = tags
-		return s
-	}
-	// we need to add a new entry to the head of the list
-	old := s.list
-	s.list.next = &old
-	s.list.tags = tags
-	return s
-}
-
-// IsEmpty returns true if the TagSet contains no tags.
-func (s TagSet) IsEmpty() bool {
-	// the only way the head can be empty is if there is no chain
-	return len(s.list.tags) <= 0
-}
-
-// Iterator returns an iterator for this TagSet.
-func (s TagSet) Iterator() TagIterator {
-	return TagIterator{list: s.list, index: -1}
-}
-
-// Next advances the iterator onto the next tag.
-// It returns true if the iterator is still valid.
-func (i *TagIterator) Next() bool {
-	// advance the iterator
-	i.index++
-	if i.index < len(i.list.tags) {
-		// within range of the tags, so next was valid
-		return true
-	}
-	if i.list.next == nil {
-		// no more lists in the chain, iterator no longer valid
-		return false
-	}
-	// need to move on to the next list in the chain
-	i.list = *i.list.next
-	i.index = 0
 	return true
 }
 
-// Value returns the tag the iterator is currently pointing to.
-// It is an error to call this on an iterator that is not valid.
-// You must have called Next and checked the return value before
-// calling this method.
-func (i *TagIterator) Value() Tag {
-	return i.list.tags[i.index]
+func NewTagIterator(tags ...Tag) TagIterator {
+	if len(tags) == 0 {
+		return TagIterator{}
+	}
+	result := TagIterator{ptr: tagPointer{tags: tags}}
+	if !result.Tag().Valid() {
+		result.Advance()
+	}
+	return result
 }
 
-// Set can be used to replace the tag currently being pointed to.
-func (i TagIterator) Set(tag Tag) {
-	i.list.tags[i.index] = tag
+func Filter(it TagIterator, keys ...Key) TagIterator {
+	if !it.Valid() || len(keys) == 0 {
+		return it
+	}
+	ptr := tagFilter{filter: keys, underlying: it.ptr}
+	result := TagIterator{ptr: ptr}
+	if ptr.filtered() {
+		result.Advance()
+	}
+	return result
 }
 
-// Equal returns true if two lists are identical.
-func (l TagSet) Equal(other TagSet) bool {
-	//TODO: make this more efficient
-	return fmt.Sprint(l) == fmt.Sprint(other)
+func ChainTagIterators(iterators ...TagIterator) TagIterator {
+	if len(iterators) == 0 {
+		return TagIterator{}
+	}
+	ptrs := make([]TagPointer, 0, len(iterators))
+	for _, it := range iterators {
+		if it.Valid() {
+			ptrs = append(ptrs, it.ptr)
+		}
+	}
+	if len(ptrs) == 0 {
+		return TagIterator{}
+	}
+	return TagIterator{ptr: tagPointerChain{ptrs: ptrs}}
 }
 
-// Less is intended only for using tag lists as a sorting key.
-func (l TagSet) Less(other TagSet) bool {
-	//TODO: make this more efficient
-	return fmt.Sprint(l) < fmt.Sprint(other)
+func NewTagMap(tags ...Tag) TagMap {
+	return tagMap{tags: tags}
+}
+
+func MergeTagMaps(srcs ...TagMap) TagMap {
+	return tagMapChain{maps: srcs}
 }
diff --git a/internal/telemetry/event/tag_test.go b/internal/telemetry/event/tag_test.go
new file mode 100644
index 0000000..6d7539f
--- /dev/null
+++ b/internal/telemetry/event/tag_test.go
@@ -0,0 +1,315 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package event_test
+
+import (
+	"bytes"
+	"fmt"
+	"testing"
+
+	"golang.org/x/tools/internal/telemetry/event"
+)
+
+var (
+	AKey = event.NewStringKey("A", "")
+	BKey = event.NewStringKey("B", "")
+	CKey = event.NewStringKey("C", "")
+	A    = AKey.Of("a")
+	B    = BKey.Of("b")
+	C    = CKey.Of("c")
+	all  = []event.Tag{A, B, C}
+)
+
+func TestTagIterator(t *testing.T) {
+	for _, test := range []struct {
+		name   string
+		tags   []event.Tag
+		expect string
+	}{{
+		name: "empty",
+	}, {
+		name:   "single",
+		tags:   []event.Tag{A},
+		expect: `A="a"`,
+	}, {
+		name:   "invalid",
+		tags:   []event.Tag{{}},
+		expect: ``,
+	}, {
+		name:   "two",
+		tags:   []event.Tag{A, B},
+		expect: `A="a", B="b"`,
+	}, {
+		name:   "three",
+		tags:   []event.Tag{A, B, C},
+		expect: `A="a", B="b", C="c"`,
+	}, {
+		name:   "missing A",
+		tags:   []event.Tag{{}, B, C},
+		expect: `B="b", C="c"`,
+	}, {
+		name:   "missing B",
+		tags:   []event.Tag{A, {}, C},
+		expect: `A="a", C="c"`,
+	}, {
+		name:   "missing C",
+		tags:   []event.Tag{A, B, {}},
+		expect: `A="a", B="b"`,
+	}, {
+		name:   "missing AB",
+		tags:   []event.Tag{{}, {}, C},
+		expect: `C="c"`,
+	}, {
+		name:   "missing AC",
+		tags:   []event.Tag{{}, B, {}},
+		expect: `B="b"`,
+	}, {
+		name:   "missing BC",
+		tags:   []event.Tag{A, {}, {}},
+		expect: `A="a"`,
+	}} {
+		t.Run(test.name, func(t *testing.T) {
+			got := printIterator(event.NewTagIterator(test.tags...))
+			if got != test.expect {
+				t.Errorf("got %q want %q", got, test.expect)
+			}
+		})
+	}
+}
+
+func TestTagFilter(t *testing.T) {
+	for _, test := range []struct {
+		name    string
+		tags    []event.Tag
+		filters []event.Key
+		expect  string
+	}{{
+		name:   "no filters",
+		tags:   all,
+		expect: `A="a", B="b", C="c"`,
+	}, {
+		name:    "no tags",
+		filters: []event.Key{AKey},
+		expect:  ``,
+	}, {
+		name:    "filter A",
+		tags:    all,
+		filters: []event.Key{AKey},
+		expect:  `B="b", C="c"`,
+	}, {
+		name:    "filter B",
+		tags:    all,
+		filters: []event.Key{BKey},
+		expect:  `A="a", C="c"`,
+	}, {
+		name:    "filter C",
+		tags:    all,
+		filters: []event.Key{CKey},
+		expect:  `A="a", B="b"`,
+	}, {
+		name:    "filter AC",
+		tags:    all,
+		filters: []event.Key{AKey, CKey},
+		expect:  `B="b"`,
+	}} {
+		t.Run(test.name, func(t *testing.T) {
+			tags := event.NewTagIterator(test.tags...)
+			got := printIterator(event.Filter(tags, test.filters...))
+			if got != test.expect {
+				t.Errorf("got %q want %q", got, test.expect)
+			}
+		})
+	}
+}
+
+func TestTagChain(t *testing.T) {
+	for _, test := range []struct {
+		name   string
+		tags   [][]event.Tag
+		expect string
+	}{{
+		name:   "no iterators",
+		expect: ``,
+	}, {
+		name:   "one iterator",
+		tags:   [][]event.Tag{all},
+		expect: `A="a", B="b", C="c"`,
+	}, {
+		name:   "invalid iterator",
+		tags:   [][]event.Tag{{}},
+		expect: ``,
+	}, {
+		name:   "two iterators",
+		tags:   [][]event.Tag{{B, C}, {A}},
+		expect: `B="b", C="c", A="a"`,
+	}, {
+		name:   "invalid start iterator",
+		tags:   [][]event.Tag{{}, {B, C}},
+		expect: `B="b", C="c"`,
+	}, {
+		name:   "invalid mid iterator",
+		tags:   [][]event.Tag{{A}, {}, {C}},
+		expect: `A="a", C="c"`,
+	}, {
+		name:   "invalid end iterator",
+		tags:   [][]event.Tag{{B, C}, {}},
+		expect: `B="b", C="c"`,
+	}} {
+		t.Run(test.name, func(t *testing.T) {
+			iterators := make([]event.TagIterator, len(test.tags))
+			for i, v := range test.tags {
+				iterators[i] = event.NewTagIterator(v...)
+			}
+			got := printIterator(event.ChainTagIterators(iterators...))
+			if got != test.expect {
+				t.Errorf("got %q want %q", got, test.expect)
+			}
+		})
+	}
+}
+
+func TestTagMap(t *testing.T) {
+	for _, test := range []struct {
+		name    string
+		tags    []event.Tag
+		keys    []event.Key
+		expect  string
+		isEmpty bool
+	}{{
+		name:    "no tags",
+		keys:    []event.Key{AKey},
+		expect:  `nil`,
+		isEmpty: true,
+	}, {
+		name:   "match A",
+		tags:   all,
+		keys:   []event.Key{AKey},
+		expect: `A="a"`,
+	}, {
+		name:   "match B",
+		tags:   all,
+		keys:   []event.Key{BKey},
+		expect: `B="b"`,
+	}, {
+		name:   "match C",
+		tags:   all,
+		keys:   []event.Key{CKey},
+		expect: `C="c"`,
+	}, {
+		name:   "match ABC",
+		tags:   all,
+		keys:   []event.Key{AKey, BKey, CKey},
+		expect: `A="a", B="b", C="c"`,
+	}, {
+		name:   "missing A",
+		tags:   []event.Tag{{}, B, C},
+		keys:   []event.Key{AKey, BKey, CKey},
+		expect: `nil, B="b", C="c"`,
+	}, {
+		name:   "missing B",
+		tags:   []event.Tag{A, {}, C},
+		keys:   []event.Key{AKey, BKey, CKey},
+		expect: `A="a", nil, C="c"`,
+	}, {
+		name:   "missing C",
+		tags:   []event.Tag{A, B, {}},
+		keys:   []event.Key{AKey, BKey, CKey},
+		expect: `A="a", B="b", nil`,
+	}} {
+		t.Run(test.name, func(t *testing.T) {
+			tagMap := event.NewTagMap(test.tags...)
+			if tagMap.IsEmpty() != test.isEmpty {
+				t.Errorf("IsEmpty gave %v want %v", tagMap.IsEmpty(), test.isEmpty)
+			}
+			got := printTagMap(tagMap, test.keys)
+			if got != test.expect {
+				t.Errorf("got %q want %q", got, test.expect)
+			}
+		})
+	}
+}
+
+func TestTagMapMerge(t *testing.T) {
+	for _, test := range []struct {
+		name    string
+		tags    [][]event.Tag
+		keys    []event.Key
+		expect  string
+		isEmpty bool
+	}{{
+		name:    "no maps",
+		keys:    []event.Key{AKey},
+		expect:  `nil`,
+		isEmpty: true,
+	}, {
+		name:   "one map",
+		tags:   [][]event.Tag{all},
+		keys:   []event.Key{AKey},
+		expect: `A="a"`,
+	}, {
+		name:    "invalid map",
+		tags:    [][]event.Tag{{}},
+		keys:    []event.Key{AKey},
+		expect:  `nil`,
+		isEmpty: true,
+	}, {
+		name:   "two maps",
+		tags:   [][]event.Tag{{B, C}, {A}},
+		keys:   []event.Key{AKey, BKey, CKey},
+		expect: `A="a", B="b", C="c"`,
+	}, {
+		name:   "invalid start map",
+		tags:   [][]event.Tag{{}, {B, C}},
+		keys:   []event.Key{AKey, BKey, CKey},
+		expect: `nil, B="b", C="c"`,
+	}, {
+		name:   "invalid mid map",
+		tags:   [][]event.Tag{{A}, {}, {C}},
+		keys:   []event.Key{AKey, BKey, CKey},
+		expect: `A="a", nil, C="c"`,
+	}, {
+		name:   "invalid end map",
+		tags:   [][]event.Tag{{A, B}, {}},
+		keys:   []event.Key{AKey, BKey, CKey},
+		expect: `A="a", B="b", nil`,
+	}} {
+		t.Run(test.name, func(t *testing.T) {
+			maps := make([]event.TagMap, len(test.tags))
+			for i, v := range test.tags {
+				maps[i] = event.NewTagMap(v...)
+			}
+			tagMap := event.MergeTagMaps(maps...)
+			if tagMap.IsEmpty() != test.isEmpty {
+				t.Errorf("IsEmpty gave %v want %v", tagMap.IsEmpty(), test.isEmpty)
+			}
+			got := printTagMap(tagMap, test.keys)
+			if got != test.expect {
+				t.Errorf("got %q want %q", got, test.expect)
+			}
+		})
+	}
+}
+
+func printIterator(it event.TagIterator) string {
+	buf := &bytes.Buffer{}
+	for ; it.Valid(); it.Advance() {
+		if buf.Len() > 0 {
+			buf.WriteString(", ")
+		}
+		fmt.Fprint(buf, it.Tag())
+	}
+	return buf.String()
+}
+
+func printTagMap(tagMap event.TagMap, keys []event.Key) string {
+	buf := &bytes.Buffer{}
+	for _, key := range keys {
+		if buf.Len() > 0 {
+			buf.WriteString(", ")
+		}
+		fmt.Fprint(buf, tagMap.Find(key))
+	}
+	return buf.String()
+}
diff --git a/internal/telemetry/event/trace.go b/internal/telemetry/event/trace.go
index fc25005..878ca4a 100644
--- a/internal/telemetry/event/trace.go
+++ b/internal/telemetry/event/trace.go
@@ -10,11 +10,11 @@
 )
 
 func StartSpan(ctx context.Context, name string, tags ...Tag) (context.Context, func()) {
-	ctx, _ = ProcessEvent(ctx, Event{
+	ctx = ProcessEvent(ctx, Event{
 		Type:    StartSpanType,
 		Message: name,
 		At:      time.Now(),
-		Tags:    newTagSet(tags),
+		tags:    tags,
 	})
 	return ctx, func() {
 		ProcessEvent(ctx, Event{
@@ -27,9 +27,8 @@
 // Detach returns a context without an associated span.
 // This allows the creation of spans that are not children of the current span.
 func Detach(ctx context.Context) context.Context {
-	ctx, _ = ProcessEvent(ctx, Event{
+	return ProcessEvent(ctx, Event{
 		Type: DetachType,
 		At:   time.Now(),
 	})
-	return ctx
 }
diff --git a/internal/telemetry/export/log.go b/internal/telemetry/export/log.go
index 1f53542..5d2bc96 100644
--- a/internal/telemetry/export/log.go
+++ b/internal/telemetry/export/log.go
@@ -26,11 +26,11 @@
 	onlyErrors bool
 }
 
-func (w *logWriter) ProcessEvent(ctx context.Context, ev event.Event) (context.Context, event.Event) {
+func (w *logWriter) ProcessEvent(ctx context.Context, ev event.Event, tagMap event.TagMap) context.Context {
 	switch {
 	case ev.IsLog():
 		if w.onlyErrors && ev.Error == nil {
-			return ctx, ev
+			return ctx
 		}
 		fmt.Fprintf(w.writer, "%v\n", ev)
 	case ev.IsStartSpan():
@@ -45,5 +45,5 @@
 			fmt.Fprintf(w.writer, "finish: %v %v", span.Name, span.ID)
 		}
 	}
-	return ctx, ev
+	return ctx
 }
diff --git a/internal/telemetry/export/metric/data.go b/internal/telemetry/export/metric/data.go
index 11eb53a..ccca71d 100644
--- a/internal/telemetry/export/metric/data.go
+++ b/internal/telemetry/export/metric/data.go
@@ -5,7 +5,7 @@
 package metric
 
 import (
-	"context"
+	"fmt"
 	"sort"
 	"time"
 
@@ -22,7 +22,7 @@
 	//TODO: rethink the concept of metric handles
 	Handle() string
 	// Groups reports the rows that currently exist for this metric.
-	Groups() []event.TagSet
+	Groups() [][]event.Tag
 }
 
 // Int64Data is a concrete implementation of Data for int64 scalar metrics.
@@ -36,7 +36,7 @@
 	// End is the last time this metric was updated.
 	EndTime time.Time
 
-	groups []event.TagSet
+	groups [][]event.Tag
 }
 
 // Float64Data is a concrete implementation of Data for float64 scalar metrics.
@@ -50,7 +50,7 @@
 	// End is the last time this metric was updated.
 	EndTime time.Time
 
-	groups []event.TagSet
+	groups [][]event.Tag
 }
 
 // HistogramInt64Data is a concrete implementation of Data for int64 histogram metrics.
@@ -62,7 +62,7 @@
 	// End is the last time this metric was updated.
 	EndTime time.Time
 
-	groups []event.TagSet
+	groups [][]event.Tag
 }
 
 // HistogramInt64Row holds the values for a single row of a HistogramInt64Data.
@@ -88,7 +88,7 @@
 	// End is the last time this metric was updated.
 	EndTime time.Time
 
-	groups []event.TagSet
+	groups [][]event.Tag
 }
 
 // HistogramFloat64Row holds the values for a single row of a HistogramFloat64Data.
@@ -105,28 +105,44 @@
 	Max float64
 }
 
-func getGroup(ctx context.Context, g *[]event.TagSet, keys []event.Key) (int, bool) {
-	group := event.Query(ctx, keys...)
+func tagListEqual(a, b []event.Tag) bool {
+	//TODO: make this more efficient
+	return fmt.Sprint(a) == fmt.Sprint(b)
+}
+
+func tagListLess(a, b []event.Tag) bool {
+	//TODO: make this more efficient
+	return fmt.Sprint(a) < fmt.Sprint(b)
+}
+
+func getGroup(tagMap event.TagMap, g *[][]event.Tag, keys []event.Key) (int, bool) {
+	group := make([]event.Tag, len(keys))
+	for i, key := range keys {
+		tag := tagMap.Find(key)
+		if tag.Valid() {
+			group[i] = tag
+		}
+	}
 	old := *g
 	index := sort.Search(len(old), func(i int) bool {
-		return !old[i].Less(group)
+		return !tagListLess(old[i], group)
 	})
-	if index < len(old) && group.Equal(old[index]) {
+	if index < len(old) && tagListEqual(group, old[index]) {
 		// not a new group
 		return index, false
 	}
-	*g = make([]event.TagSet, len(old)+1)
+	*g = make([][]event.Tag, len(old)+1)
 	copy(*g, old[:index])
 	copy((*g)[index+1:], old[index:])
 	(*g)[index] = group
 	return index, true
 }
 
-func (data *Int64Data) Handle() string         { return data.Info.Name }
-func (data *Int64Data) Groups() []event.TagSet { return data.groups }
+func (data *Int64Data) Handle() string        { return data.Info.Name }
+func (data *Int64Data) Groups() [][]event.Tag { return data.groups }
 
-func (data *Int64Data) modify(ctx context.Context, ev event.Event, tag event.Tag, f func(v int64) int64) Data {
-	index, insert := getGroup(ctx, &data.groups, data.Info.Keys)
+func (data *Int64Data) modify(at time.Time, tagMap event.TagMap, f func(v int64) int64) Data {
+	index, insert := getGroup(tagMap, &data.groups, data.Info.Keys)
 	old := data.Rows
 	if insert {
 		data.Rows = make([]int64, len(old)+1)
@@ -137,40 +153,40 @@
 		copy(data.Rows, old)
 	}
 	data.Rows[index] = f(data.Rows[index])
-	data.EndTime = ev.At
+	data.EndTime = at
 	frozen := *data
 	return &frozen
 }
 
-func (data *Int64Data) countInt64(ctx context.Context, ev event.Event, tag event.Tag) Data {
-	return data.modify(ctx, ev, tag, func(v int64) int64 {
+func (data *Int64Data) countInt64(at time.Time, tagMap event.TagMap, tag event.Tag) Data {
+	return data.modify(at, tagMap, func(v int64) int64 {
 		return v + 1
 	})
 }
 
-func (data *Int64Data) countFloat64(ctx context.Context, ev event.Event, tag event.Tag) Data {
-	return data.modify(ctx, ev, tag, func(v int64) int64 {
+func (data *Int64Data) countFloat64(at time.Time, tagMap event.TagMap, tag event.Tag) Data {
+	return data.modify(at, tagMap, func(v int64) int64 {
 		return v + 1
 	})
 }
 
-func (data *Int64Data) sum(ctx context.Context, ev event.Event, tag event.Tag) Data {
-	return data.modify(ctx, ev, tag, func(v int64) int64 {
-		return v + tag.Value().(int64)
+func (data *Int64Data) sum(at time.Time, tagMap event.TagMap, tag event.Tag) Data {
+	return data.modify(at, tagMap, func(v int64) int64 {
+		return v + tag.Value.(int64)
 	})
 }
 
-func (data *Int64Data) latest(ctx context.Context, ev event.Event, tag event.Tag) Data {
-	return data.modify(ctx, ev, tag, func(v int64) int64 {
-		return tag.Value().(int64)
+func (data *Int64Data) latest(at time.Time, tagMap event.TagMap, tag event.Tag) Data {
+	return data.modify(at, tagMap, func(v int64) int64 {
+		return tag.Value.(int64)
 	})
 }
 
-func (data *Float64Data) Handle() string         { return data.Info.Name }
-func (data *Float64Data) Groups() []event.TagSet { return data.groups }
+func (data *Float64Data) Handle() string        { return data.Info.Name }
+func (data *Float64Data) Groups() [][]event.Tag { return data.groups }
 
-func (data *Float64Data) modify(ctx context.Context, ev event.Event, tag event.Tag, f func(v float64) float64) Data {
-	index, insert := getGroup(ctx, &data.groups, data.Info.Keys)
+func (data *Float64Data) modify(at time.Time, tagMap event.TagMap, f func(v float64) float64) Data {
+	index, insert := getGroup(tagMap, &data.groups, data.Info.Keys)
 	old := data.Rows
 	if insert {
 		data.Rows = make([]float64, len(old)+1)
@@ -181,28 +197,28 @@
 		copy(data.Rows, old)
 	}
 	data.Rows[index] = f(data.Rows[index])
-	data.EndTime = ev.At
+	data.EndTime = at
 	frozen := *data
 	return &frozen
 }
 
-func (data *Float64Data) sum(ctx context.Context, ev event.Event, tag event.Tag) Data {
-	return data.modify(ctx, ev, tag, func(v float64) float64 {
-		return v + tag.Value().(float64)
+func (data *Float64Data) sum(at time.Time, tagMap event.TagMap, tag event.Tag) Data {
+	return data.modify(at, tagMap, func(v float64) float64 {
+		return v + tag.Value.(float64)
 	})
 }
 
-func (data *Float64Data) latest(ctx context.Context, ev event.Event, tag event.Tag) Data {
-	return data.modify(ctx, ev, tag, func(v float64) float64 {
-		return tag.Value().(float64)
+func (data *Float64Data) latest(at time.Time, tagMap event.TagMap, tag event.Tag) Data {
+	return data.modify(at, tagMap, func(v float64) float64 {
+		return tag.Value.(float64)
 	})
 }
 
-func (data *HistogramInt64Data) Handle() string         { return data.Info.Name }
-func (data *HistogramInt64Data) Groups() []event.TagSet { return data.groups }
+func (data *HistogramInt64Data) Handle() string        { return data.Info.Name }
+func (data *HistogramInt64Data) Groups() [][]event.Tag { return data.groups }
 
-func (data *HistogramInt64Data) modify(ctx context.Context, ev event.Event, tag event.Tag, f func(v *HistogramInt64Row)) Data {
-	index, insert := getGroup(ctx, &data.groups, data.Info.Keys)
+func (data *HistogramInt64Data) modify(at time.Time, tagMap event.TagMap, f func(v *HistogramInt64Row)) Data {
+	index, insert := getGroup(tagMap, &data.groups, data.Info.Keys)
 	old := data.Rows
 	var v HistogramInt64Row
 	if insert {
@@ -219,14 +235,14 @@
 	copy(v.Values, oldValues)
 	f(&v)
 	data.Rows[index] = &v
-	data.EndTime = ev.At
+	data.EndTime = at
 	frozen := *data
 	return &frozen
 }
 
-func (data *HistogramInt64Data) record(ctx context.Context, ev event.Event, tag event.Tag) Data {
-	return data.modify(ctx, ev, tag, func(v *HistogramInt64Row) {
-		value := tag.Value().(int64)
+func (data *HistogramInt64Data) record(at time.Time, tagMap event.TagMap, tag event.Tag) Data {
+	return data.modify(at, tagMap, func(v *HistogramInt64Row) {
+		value := tag.Value.(int64)
 		v.Sum += value
 		if v.Min > value || v.Count == 0 {
 			v.Min = value
@@ -243,11 +259,11 @@
 	})
 }
 
-func (data *HistogramFloat64Data) Handle() string         { return data.Info.Name }
-func (data *HistogramFloat64Data) Groups() []event.TagSet { return data.groups }
+func (data *HistogramFloat64Data) Handle() string        { return data.Info.Name }
+func (data *HistogramFloat64Data) Groups() [][]event.Tag { return data.groups }
 
-func (data *HistogramFloat64Data) modify(ctx context.Context, ev event.Event, tag event.Tag, f func(v *HistogramFloat64Row)) Data {
-	index, insert := getGroup(ctx, &data.groups, data.Info.Keys)
+func (data *HistogramFloat64Data) modify(at time.Time, tagMap event.TagMap, f func(v *HistogramFloat64Row)) Data {
+	index, insert := getGroup(tagMap, &data.groups, data.Info.Keys)
 	old := data.Rows
 	var v HistogramFloat64Row
 	if insert {
@@ -264,14 +280,14 @@
 	copy(v.Values, oldValues)
 	f(&v)
 	data.Rows[index] = &v
-	data.EndTime = ev.At
+	data.EndTime = at
 	frozen := *data
 	return &frozen
 }
 
-func (data *HistogramFloat64Data) record(ctx context.Context, ev event.Event, tag event.Tag) Data {
-	return data.modify(ctx, ev, tag, func(v *HistogramFloat64Row) {
-		value := tag.Value().(float64)
+func (data *HistogramFloat64Data) record(at time.Time, tagMap event.TagMap, tag event.Tag) Data {
+	return data.modify(at, tagMap, func(v *HistogramFloat64Row) {
+		value := tag.Value.(float64)
 		v.Sum += value
 		if v.Min > value || v.Count == 0 {
 			v.Min = value
diff --git a/internal/telemetry/export/metric/exporter.go b/internal/telemetry/export/metric/exporter.go
index b2dc5b2..914a7fc 100644
--- a/internal/telemetry/export/metric/exporter.go
+++ b/internal/telemetry/export/metric/exporter.go
@@ -7,40 +7,42 @@
 
 import (
 	"context"
+	"time"
 
 	"golang.org/x/tools/internal/telemetry/event"
 )
 
 var Entries = event.NewKey("metric_entries", "The set of metrics calculated for an event")
 
-type Exporter struct {
+type Config struct {
 	subscribers map[interface{}][]subscriber
 }
 
-type subscriber func(context.Context, event.Event, event.Tag) Data
+type subscriber func(time.Time, event.TagMap, event.Tag) Data
 
-func (e *Exporter) subscribe(key event.Key, s subscriber) {
+func (e *Config) subscribe(key event.Key, s subscriber) {
 	if e.subscribers == nil {
 		e.subscribers = make(map[interface{}][]subscriber)
 	}
-	ident := key.Identity()
-	e.subscribers[ident] = append(e.subscribers[ident], s)
+	e.subscribers[key] = append(e.subscribers[key], s)
 }
 
-func (e *Exporter) ProcessEvent(ctx context.Context, ev event.Event) (context.Context, event.Event) {
-	if !ev.IsRecord() {
-		return ctx, ev
-	}
-	var metrics []Data
-	for i := ev.Tags.Iterator(); i.Next(); {
-		tag := i.Value()
-		id := tag.Key().Identity()
-		if list := e.subscribers[id]; len(list) > 0 {
-			for _, s := range list {
-				metrics = append(metrics, s(ctx, ev, tag))
+func (e *Config) Exporter(output event.Exporter) event.Exporter {
+	return func(ctx context.Context, ev event.Event, tagMap event.TagMap) context.Context {
+		if !ev.IsRecord() {
+			return output(ctx, ev, tagMap)
+		}
+		var metrics []Data
+		for it := ev.Tags(); it.Valid(); it.Advance() {
+			tag := it.Tag()
+			id := tag.Key
+			if list := e.subscribers[id]; len(list) > 0 {
+				for _, s := range list {
+					metrics = append(metrics, s(ev.At, tagMap, tag))
+				}
 			}
 		}
+		tagMap = event.MergeTagMaps(event.NewTagMap(Entries.Of(metrics)), tagMap)
+		return output(ctx, ev, tagMap)
 	}
-	ev.Tags = ev.Tags.Add(Entries.Of(metrics))
-	return ctx, ev
 }
diff --git a/internal/telemetry/export/metric/info.go b/internal/telemetry/export/metric/info.go
index 28bab84..045745b 100644
--- a/internal/telemetry/export/metric/info.go
+++ b/internal/telemetry/export/metric/info.go
@@ -45,7 +45,7 @@
 // CountInt64 creates a new metric based on the Scalar information that counts
 // the number of times the supplied int64 measure is set.
 // Metrics of this type will use Int64Data.
-func (info Scalar) CountInt64(e *Exporter, key event.Key) {
+func (info Scalar) CountInt64(e *Config, key event.Key) {
 	data := &Int64Data{Info: &info}
 	e.subscribe(key, data.countInt64)
 }
@@ -53,7 +53,7 @@
 // SumInt64 creates a new metric based on the Scalar information that sums all
 // the values recorded on the int64 measure.
 // Metrics of this type will use Int64Data.
-func (info Scalar) SumInt64(e *Exporter, key event.Key) {
+func (info Scalar) SumInt64(e *Config, key event.Key) {
 	data := &Int64Data{Info: &info}
 	e.subscribe(key, data.sum)
 }
@@ -61,7 +61,7 @@
 // LatestInt64 creates a new metric based on the Scalar information that tracks
 // the most recent value recorded on the int64 measure.
 // Metrics of this type will use Int64Data.
-func (info Scalar) LatestInt64(e *Exporter, key event.Key) {
+func (info Scalar) LatestInt64(e *Config, key event.Key) {
 	data := &Int64Data{Info: &info, IsGauge: true}
 	e.subscribe(key, data.latest)
 }
@@ -69,7 +69,7 @@
 // CountFloat64 creates a new metric based on the Scalar information that counts
 // the number of times the supplied float64 measure is set.
 // Metrics of this type will use Int64Data.
-func (info Scalar) CountFloat64(e *Exporter, key event.Key) {
+func (info Scalar) CountFloat64(e *Config, key event.Key) {
 	data := &Int64Data{Info: &info}
 	e.subscribe(key, data.countFloat64)
 }
@@ -77,7 +77,7 @@
 // SumFloat64 creates a new metric based on the Scalar information that sums all
 // the values recorded on the float64 measure.
 // Metrics of this type will use Float64Data.
-func (info Scalar) SumFloat64(e *Exporter, key event.Key) {
+func (info Scalar) SumFloat64(e *Config, key event.Key) {
 	data := &Float64Data{Info: &info}
 	e.subscribe(key, data.sum)
 }
@@ -85,7 +85,7 @@
 // LatestFloat64 creates a new metric based on the Scalar information that tracks
 // the most recent value recorded on the float64 measure.
 // Metrics of this type will use Float64Data.
-func (info Scalar) LatestFloat64(e *Exporter, key event.Key) {
+func (info Scalar) LatestFloat64(e *Config, key event.Key) {
 	data := &Float64Data{Info: &info, IsGauge: true}
 	e.subscribe(key, data.latest)
 }
@@ -93,7 +93,7 @@
 // Record creates a new metric based on the HistogramInt64 information that
 // tracks the bucketized counts of values recorded on the int64 measure.
 // Metrics of this type will use HistogramInt64Data.
-func (info HistogramInt64) Record(e *Exporter, key event.Key) {
+func (info HistogramInt64) Record(e *Config, key event.Key) {
 	data := &HistogramInt64Data{Info: &info}
 	e.subscribe(key, data.record)
 }
@@ -101,7 +101,7 @@
 // Record creates a new metric based on the HistogramFloat64 information that
 // tracks the bucketized counts of values recorded on the float64 measure.
 // Metrics of this type will use HistogramFloat64Data.
-func (info HistogramFloat64) Record(e *Exporter, key event.Key) {
+func (info HistogramFloat64) Record(e *Config, key event.Key) {
 	data := &HistogramFloat64Data{Info: &info}
 	e.subscribe(key, data.record)
 }
diff --git a/internal/telemetry/export/ocagent/ocagent.go b/internal/telemetry/export/ocagent/ocagent.go
index e0907d7..96134b1 100644
--- a/internal/telemetry/export/ocagent/ocagent.go
+++ b/internal/telemetry/export/ocagent/ocagent.go
@@ -85,7 +85,7 @@
 	return exporter
 }
 
-func (e *Exporter) ProcessEvent(ctx context.Context, ev event.Event) (context.Context, event.Event) {
+func (e *Exporter) ProcessEvent(ctx context.Context, ev event.Event, tagMap event.TagMap) context.Context {
 	switch {
 	case ev.IsEndSpan():
 		e.mu.Lock()
@@ -97,10 +97,10 @@
 	case ev.IsRecord():
 		e.mu.Lock()
 		defer e.mu.Unlock()
-		data := metric.Entries.Get(ev.Tags).([]metric.Data)
+		data := metric.Entries.Get(tagMap).([]metric.Data)
 		e.metrics = append(e.metrics, data...)
 	}
-	return ctx, ev
+	return ctx
 }
 
 func (e *Exporter) Flush() {
@@ -198,9 +198,9 @@
 		ParentSpanID:            span.ParentID[:],
 		Name:                    toTruncatableString(span.Name),
 		Kind:                    wire.UnspecifiedSpanKind,
-		StartTime:               convertTimestamp(span.Start),
-		EndTime:                 convertTimestamp(span.Finish),
-		Attributes:              convertAttributes(span.Tags),
+		StartTime:               convertTimestamp(span.Start.At),
+		EndTime:                 convertTimestamp(span.Finish.At),
+		Attributes:              convertAttributes(span.Start.Tags()),
 		TimeEvents:              convertEvents(span.Events),
 		SameProcessAsParentSpan: true,
 		//TODO: StackTrace?
@@ -227,18 +227,14 @@
 	}
 }
 
-func convertAttributes(tags event.TagSet) *wire.Attributes {
-	i := tags.Iterator()
-	if !i.Next() {
+func convertAttributes(it event.TagIterator) *wire.Attributes {
+	if !it.Valid() {
 		return nil
 	}
 	attributes := make(map[string]wire.Attribute)
-	for {
-		tag := i.Value()
-		attributes[tag.Key().Name()] = convertAttribute(tag.Value())
-		if !i.Next() {
-			break
-		}
+	for ; it.Valid(); it.Advance() {
+		tag := it.Tag()
+		attributes[tag.Key.Name()] = convertAttribute(tag.Value)
 	}
 	return &wire.Attributes{AttributeMap: attributes}
 }
@@ -300,11 +296,12 @@
 		description = ev.Error.Error()
 		ev.Error = nil
 	}
-	tags := ev.Tags
+	tags := ev.Tags()
 	if ev.Error != nil {
-		tags = tags.Add(event.Err.Of(ev.Error))
+		extra := event.NewTagIterator(event.Err.Of(ev.Error))
+		tags = event.ChainTagIterators(extra, tags)
 	}
-	if description == "" && tags.IsEmpty() {
+	if description == "" && !tags.Valid() {
 		return nil
 	}
 	return &wire.Annotation{
diff --git a/internal/telemetry/export/ocagent/ocagent_test.go b/internal/telemetry/export/ocagent/ocagent_test.go
index ecd2612..36ca0e7 100644
--- a/internal/telemetry/export/ocagent/ocagent_test.go
+++ b/internal/telemetry/export/ocagent/ocagent_test.go
@@ -90,12 +90,8 @@
 )
 
 type testExporter struct {
-	metrics metric.Exporter
 	ocagent *ocagent.Exporter
 	sent    fakeSender
-	start   time.Time
-	at      time.Time
-	end     time.Time
 }
 
 func registerExporter() *testExporter {
@@ -108,36 +104,47 @@
 	}
 	cfg.Start, _ = time.Parse(time.RFC3339Nano, "1970-01-01T00:00:00Z")
 	exporter.ocagent = ocagent.Connect(&cfg)
-	exporter.start, _ = time.Parse(time.RFC3339Nano, "1970-01-01T00:00:30Z")
-	exporter.at, _ = time.Parse(time.RFC3339Nano, "1970-01-01T00:00:40Z")
-	exporter.end, _ = time.Parse(time.RFC3339Nano, "1970-01-01T00:00:50Z")
 
-	metricLatency.Record(&exporter.metrics, latencyMs)
-	metricBytesIn.Record(&exporter.metrics, bytesIn)
-	metricRecursiveCalls.SumInt64(&exporter.metrics, recursiveCalls)
+	metrics := metric.Config{}
+	metricLatency.Record(&metrics, latencyMs)
+	metricBytesIn.Record(&metrics, bytesIn)
+	metricRecursiveCalls.SumInt64(&metrics, recursiveCalls)
 
-	event.SetExporter(exporter.processEvent)
+	e := exporter.ocagent.ProcessEvent
+	e = metrics.Exporter(e)
+	e = spanFixer(e)
+	e = export.Spans(e)
+	e = export.Labels(e)
+	e = timeFixer(e)
+	event.SetExporter(e)
 	return exporter
 }
 
-func (e *testExporter) processEvent(ctx context.Context, ev event.Event) (context.Context, event.Event) {
-	switch {
-	case ev.IsStartSpan():
-		ev.At = e.start
-	case ev.IsEndSpan():
-		ev.At = e.end
-	default:
-		ev.At = e.at
+func timeFixer(output event.Exporter) event.Exporter {
+	start, _ := time.Parse(time.RFC3339Nano, "1970-01-01T00:00:30Z")
+	at, _ := time.Parse(time.RFC3339Nano, "1970-01-01T00:00:40Z")
+	end, _ := time.Parse(time.RFC3339Nano, "1970-01-01T00:00:50Z")
+	return func(ctx context.Context, ev event.Event, tagMap event.TagMap) context.Context {
+		switch {
+		case ev.IsStartSpan():
+			ev.At = start
+		case ev.IsEndSpan():
+			ev.At = end
+		default:
+			ev.At = at
+		}
+		return output(ctx, ev, tagMap)
 	}
-	ctx, ev = export.Tag(ctx, ev)
-	ctx, ev = export.ContextSpan(ctx, ev)
-	ctx, ev = e.metrics.ProcessEvent(ctx, ev)
-	ctx, ev = e.ocagent.ProcessEvent(ctx, ev)
-	if ev.IsStartSpan() {
-		span := export.GetSpan(ctx)
-		span.ID = export.SpanContext{}
+}
+
+func spanFixer(output event.Exporter) event.Exporter {
+	return func(ctx context.Context, ev event.Event, tagMap event.TagMap) context.Context {
+		if ev.IsStartSpan() {
+			span := export.GetSpan(ctx)
+			span.ID = export.SpanContext{}
+		}
+		return output(ctx, ev, tagMap)
 	}
-	return ctx, ev
 }
 
 func (e *testExporter) Output(route string) []byte {
diff --git a/internal/telemetry/export/prometheus/prometheus.go b/internal/telemetry/export/prometheus/prometheus.go
index caf35ba..eb644dd 100644
--- a/internal/telemetry/export/prometheus/prometheus.go
+++ b/internal/telemetry/export/prometheus/prometheus.go
@@ -25,13 +25,13 @@
 	metrics []metric.Data
 }
 
-func (e *Exporter) ProcessEvent(ctx context.Context, ev event.Event) (context.Context, event.Event) {
+func (e *Exporter) ProcessEvent(ctx context.Context, ev event.Event, tagMap event.TagMap) context.Context {
 	if !ev.IsRecord() {
-		return ctx, ev
+		return ctx
 	}
 	e.mu.Lock()
 	defer e.mu.Unlock()
-	metrics := metric.Entries.Get(ev.Tags).([]metric.Data)
+	metrics := metric.Entries.Get(tagMap).([]metric.Data)
 	for _, data := range metrics {
 		name := data.Handle()
 		// We keep the metrics in name sorted order so the page is stable and easy
@@ -49,7 +49,7 @@
 		}
 		e.metrics[index] = data
 	}
-	return ctx, ev
+	return ctx
 }
 
 func (e *Exporter) header(w http.ResponseWriter, name, description string, isGauge, isHistogram bool) {
@@ -64,7 +64,7 @@
 	fmt.Fprintf(w, "# TYPE %s %s\n", name, kind)
 }
 
-func (e *Exporter) row(w http.ResponseWriter, name string, group event.TagSet, extra string, value interface{}) {
+func (e *Exporter) row(w http.ResponseWriter, name string, group []event.Tag, extra string, value interface{}) {
 	fmt.Fprint(w, name)
 	buf := &bytes.Buffer{}
 	fmt.Fprint(buf, group)
diff --git a/internal/telemetry/export/tag.go b/internal/telemetry/export/tag.go
index 032a14d..6acadf0 100644
--- a/internal/telemetry/export/tag.go
+++ b/internal/telemetry/export/tag.go
@@ -10,29 +10,26 @@
 	"golang.org/x/tools/internal/telemetry/event"
 )
 
-// Tag manipulates the context using the event.
+// Labels builds an exporter that manipulates the context using the event.
 // If the event is type IsTag or IsStartSpan then it returns a context updated
 // with tag values from the event.
 // For all other event types the event tags will be updated with values from the
 // context if they are missing.
-func Tag(ctx context.Context, ev event.Event) (context.Context, event.Event) {
-	//TODO: Do we need to do something more efficient than just store tags
-	//TODO: directly on the context?
-	switch {
-	case ev.IsLabel(), ev.IsStartSpan():
-		for i := ev.Tags.Iterator(); i.Next(); {
-			tag := i.Value()
-			ctx = context.WithValue(ctx, tag.Key(), tag.Value())
-		}
-	default:
-		// all other types want the tags filled in if needed
-		for i := ev.Tags.Iterator(); i.Next(); {
-			tag := i.Value()
-			if tag.Value() == nil {
-				key := tag.Key()
-				i.Set(key.OfValue(ctx.Value(key.Identity())))
+func Labels(output event.Exporter) event.Exporter {
+	return func(ctx context.Context, ev event.Event, tagMap event.TagMap) context.Context {
+		stored, _ := ctx.Value(labelContextKey).(event.TagMap)
+		if ev.IsLabel() || ev.IsStartSpan() {
+			// update the tag source stored in the context
+			fromEvent := ev.Map()
+			if stored == nil {
+				stored = fromEvent
+			} else {
+				stored = event.MergeTagMaps(fromEvent, stored)
 			}
+			ctx = context.WithValue(ctx, labelContextKey, stored)
 		}
+		// add the stored tag context to the tag source
+		tagMap = event.MergeTagMaps(tagMap, stored)
+		return output(ctx, ev, tagMap)
 	}
-	return ctx, ev
 }
diff --git a/internal/telemetry/export/trace.go b/internal/telemetry/export/trace.go
index 010b7ef..3894b85 100644
--- a/internal/telemetry/export/trace.go
+++ b/internal/telemetry/export/trace.go
@@ -7,7 +7,6 @@
 import (
 	"context"
 	"fmt"
-	"time"
 
 	"golang.org/x/tools/internal/telemetry/event"
 )
@@ -21,9 +20,8 @@
 	Name     string
 	ID       SpanContext
 	ParentID SpanID
-	Start    time.Time
-	Finish   time.Time
-	Tags     event.TagSet
+	Start    event.Event
+	Finish   event.Event
 	Events   []event.Event
 }
 
@@ -31,6 +29,7 @@
 
 const (
 	spanContextKey = contextKeyType(iota)
+	labelContextKey
 )
 
 func GetSpan(ctx context.Context) *Span {
@@ -41,39 +40,40 @@
 	return v.(*Span)
 }
 
-// ContextSpan is an exporter that maintains hierarchical span structure in the
+// Spans creates an exporter that maintains hierarchical span structure in the
 // context.
 // It creates new spans on EventStartSpan, adds events to the current span on
 // EventLog or EventTag, and closes the span on EventEndSpan.
 // The span structure can then be used by other exporters.
-func ContextSpan(ctx context.Context, ev event.Event) (context.Context, event.Event) {
-	switch {
-	case ev.IsLog(), ev.IsLabel():
-		if span := GetSpan(ctx); span != nil {
-			span.Events = append(span.Events, ev)
+func Spans(output event.Exporter) event.Exporter {
+	return func(ctx context.Context, ev event.Event, tagMap event.TagMap) context.Context {
+		switch {
+		case ev.IsLog(), ev.IsLabel():
+			if span := GetSpan(ctx); span != nil {
+				span.Events = append(span.Events, ev)
+			}
+		case ev.IsStartSpan():
+			span := &Span{
+				Name:  ev.Message,
+				Start: ev,
+			}
+			if parent := GetSpan(ctx); parent != nil {
+				span.ID.TraceID = parent.ID.TraceID
+				span.ParentID = parent.ID.SpanID
+			} else {
+				span.ID.TraceID = newTraceID()
+			}
+			span.ID.SpanID = newSpanID()
+			ctx = context.WithValue(ctx, spanContextKey, span)
+		case ev.IsEndSpan():
+			if span := GetSpan(ctx); span != nil {
+				span.Finish = ev
+			}
+		case ev.IsDetach():
+			ctx = context.WithValue(ctx, spanContextKey, nil)
 		}
-	case ev.IsStartSpan():
-		span := &Span{
-			Name:  ev.Message,
-			Start: ev.At,
-			Tags:  ev.Tags,
-		}
-		if parent := GetSpan(ctx); parent != nil {
-			span.ID.TraceID = parent.ID.TraceID
-			span.ParentID = parent.ID.SpanID
-		} else {
-			span.ID.TraceID = newTraceID()
-		}
-		span.ID.SpanID = newSpanID()
-		ctx = context.WithValue(ctx, spanContextKey, span)
-	case ev.IsEndSpan():
-		if span := GetSpan(ctx); span != nil {
-			span.Finish = ev.At
-		}
-	case ev.IsDetach():
-		return context.WithValue(ctx, spanContextKey, nil), ev
+		return output(ctx, ev, tagMap)
 	}
-	return ctx, ev
 }
 
 func (s *SpanContext) Format(f fmt.State, r rune) {