Debian Codegraph @

trace/tracestate.go

raw
1 // Copyright The OpenTelemetry Authors
2 // SPDX-License-Identifier: Apache-2.0
3
4 package trace // import "go.opentelemetry.io/otel/trace"
5
6 import (
7 "encoding/json"
8 "fmt"
9 "strings"
10 )
11
12 const (
13 maxListMembers = 32
14
15 listDelimiters = ","
16 memberDelimiter = "="
17
18 errInvalidKey errorConst = "invalid tracestate key"
19 errInvalidValue errorConst = "invalid tracestate value"
20 errInvalidMember errorConst = "invalid tracestate list-member"
21 errMemberNumber errorConst = "too many list-members in tracestate"
22 errDuplicate errorConst = "duplicate list-member in tracestate"
23 )
24
25 type member struct {
26 Key string
27 Value string
28 }
29
30 // according to (chr = %x20 / (nblk-char = %x21-2B / %x2D-3C / %x3E-7E) )
31 // means (chr = %x20-2B / %x2D-3C / %x3E-7E) .
32 func checkValueChar(v byte) bool {
33 return v >= '\x20' && v <= '\x7e' && v != '\x2c' && v != '\x3d'
34 }
35
36 // according to (nblk-chr = %x21-2B / %x2D-3C / %x3E-7E) .
37 func checkValueLast(v byte) bool {
38 return v >= '\x21' && v <= '\x7e' && v != '\x2c' && v != '\x3d'
39 }
40
41 // based on the W3C Trace Context specification
42 //
43 // value = (0*255(chr)) nblk-chr
44 // nblk-chr = %x21-2B / %x2D-3C / %x3E-7E
45 // chr = %x20 / nblk-chr
46 //
47 // see https://www.w3.org/TR/trace-context-1/#value
48 func checkValue(val string) bool {
49 n := len(val)
50 if n == 0 || n > 256 {
51 return false
52 }
53 for i := 0; i < n-1; i++ {
54 if !checkValueChar(val[i]) {
55 return false
56 }
57 }
58 return checkValueLast(val[n-1])
59 }
60
61 func checkKeyRemain(key string) bool {
62 // ( lcalpha / DIGIT / "_" / "-"/ "*" / "/" )
63 for _, v := range key {
64 if v > 127 {
65 return false
66 }
67 if isAlphaNumASCII(v) {
68 continue
69 }
70 switch v {
71 case '_', '-', '*', '/':
72 continue
73 }
74 return false
75 }
76 return true
77 }
78
79 // according to
80 //
81 // simple-key = lcalpha (0*255( lcalpha / DIGIT / "_" / "-"/ "*" / "/" ))
82 // system-id = lcalpha (0*13( lcalpha / DIGIT / "_" / "-"/ "*" / "/" ))
83 //
84 // param n is remain part length, should be 255 in simple-key or 13 in system-id.
85 func checkKeyPart(key string, n int) bool {
86 if key == "" {
87 return false
88 }
89 first := key[0] // key's first char
90 ret := len(key[1:]) <= n
91 ret = ret && first >= 'a' && first <= 'z'
92 return ret && checkKeyRemain(key[1:])
93 }
94
95 func isAlphaNumASCII[T rune | byte](c T) bool {
96 if c >= 'a' && c <= 'z' {
97 return true
98 }
99 return c >= '0' && c <= '9'
100 }
101
102 // according to
103 //
104 // tenant-id = ( lcalpha / DIGIT ) 0*240( lcalpha / DIGIT / "_" / "-"/ "*" / "/" )
105 //
106 // param n is remain part length, should be 240 exactly.
107 func checkKeyTenant(key string, n int) bool {
108 if key == "" {
109 return false
110 }
111 return isAlphaNumASCII(key[0]) && len(key[1:]) <= n && checkKeyRemain(key[1:])
112 }
113
114 // based on the W3C Trace Context specification
115 //
116 // key = simple-key / multi-tenant-key
117 // simple-key = lcalpha (0*255( lcalpha / DIGIT / "_" / "-"/ "*" / "/" ))
118 // multi-tenant-key = tenant-id "@" system-id
119 // tenant-id = ( lcalpha / DIGIT ) (0*240( lcalpha / DIGIT / "_" / "-"/ "*" / "/" ))
120 // system-id = lcalpha (0*13( lcalpha / DIGIT / "_" / "-"/ "*" / "/" ))
121 // lcalpha = %x61-7A ; a-z
122 //
123 // see https://www.w3.org/TR/trace-context-1/#tracestate-header.
124 func checkKey(key string) bool {
125 tenant, system, ok := strings.Cut(key, "@")
126 if !ok {
127 return checkKeyPart(key, 255)
128 }
129 return checkKeyTenant(tenant, 240) && checkKeyPart(system, 13)
130 }
131
132 func newMember(key, value string) (member, error) {
133 if !checkKey(key) {
134 return member{}, errInvalidKey
135 }
136 if !checkValue(value) {
137 return member{}, errInvalidValue
138 }
139 return member{Key: key, Value: value}, nil
140 }
141
142 func parseMember(m string) (member, error) {
143 key, val, ok := strings.Cut(m, memberDelimiter)
144 if !ok {
145 return member{}, fmt.Errorf("%w: %s", errInvalidMember, m)
146 }
147 key = strings.TrimLeft(key, " \t")
148 val = strings.TrimRight(val, " \t")
149 result, e := newMember(key, val)
150 if e != nil {
151 return member{}, fmt.Errorf("%w: %s", errInvalidMember, m)
152 }
153 return result, nil
154 }
155
156 // String encodes member into a string compliant with the W3C Trace Context
157 // specification.
158 func (m member) String() string {
159 return m.Key + "=" + m.Value
160 }
161
162 // TraceState provides additional vendor-specific trace identification
163 // information across different distributed tracing systems. It represents an
164 // immutable list consisting of key/value pairs, each pair is referred to as a
165 // list-member.
166 //
167 // TraceState conforms to the W3C Trace Context specification
168 // (https://www.w3.org/TR/trace-context-1). All operations that create or copy
169 // a TraceState do so by validating all input and will only produce TraceState
170 // that conform to the specification. Specifically, this means that all
171 // list-member's key/value pairs are valid, no duplicate list-members exist,
172 // and the maximum number of list-members (32) is not exceeded.
173 type TraceState struct { //nolint:revive // revive complains about stutter of `trace.TraceState`
174 // list is the members in order.
175 list []member
176 }
177
178 var _ json.Marshaler = TraceState{}
179
180 // ParseTraceState attempts to decode a TraceState from the passed
181 // string. It returns an error if the input is invalid according to the W3C
182 // Trace Context specification.
183 func ParseTraceState(ts string) (TraceState, error) {
184 if ts == "" {
185 return TraceState{}, nil
186 }
187
188 wrapErr := func(err error) error {
189 return fmt.Errorf("failed to parse tracestate: %w", err)
190 }
191
192 var members []member
193 found := make(map[string]struct{})
194 for ts != "" {
195 var memberStr string
196 memberStr, ts, _ = strings.Cut(ts, listDelimiters)
197 if memberStr == "" {
198 continue
199 }
200
201 m, err := parseMember(memberStr)
202 if err != nil {
203 return TraceState{}, wrapErr(err)
204 }
205
206 if _, ok := found[m.Key]; ok {
207 return TraceState{}, wrapErr(errDuplicate)
208 }
209 found[m.Key] = struct{}{}
210
211 members = append(members, m)
212 if n := len(members); n > maxListMembers {
213 return TraceState{}, wrapErr(errMemberNumber)
214 }
215 }
216
217 return TraceState{list: members}, nil
218 }
219
220 // MarshalJSON marshals the TraceState into JSON.
221 func (ts TraceState) MarshalJSON() ([]byte, error) {
222 return json.Marshal(ts.String())
223 }
224
225 // String encodes the TraceState into a string compliant with the W3C
226 // Trace Context specification. The returned string will be invalid if the
227 // TraceState contains any invalid members.
228 func (ts TraceState) String() string {
229 if len(ts.list) == 0 {
230 return ""
231 }
232 var n int
233 n += len(ts.list) // member delimiters: '='
234 n += len(ts.list) - 1 // list delimiters: ','
235 for _, mem := range ts.list {
236 n += len(mem.Key)
237 n += len(mem.Value)
238 }
239
240 var sb strings.Builder
241 sb.Grow(n)
242 _, _ = sb.WriteString(ts.list[0].Key)
243 _ = sb.WriteByte('=')
244 _, _ = sb.WriteString(ts.list[0].Value)
245 for i := 1; i < len(ts.list); i++ {
246 _ = sb.WriteByte(listDelimiters[0])
247 _, _ = sb.WriteString(ts.list[i].Key)
248 _ = sb.WriteByte('=')
249 _, _ = sb.WriteString(ts.list[i].Value)
250 }
251 return sb.String()
252 }
253
254 // Get returns the value paired with key from the corresponding TraceState
255 // list-member if it exists, otherwise an empty string is returned.
256 func (ts TraceState) Get(key string) string {
257 for _, member := range ts.list {
258 if member.Key == key {
259 return member.Value
260 }
261 }
262
263 return ""
264 }
265
266 // Walk walks all key value pairs in the TraceState by calling f
267 // Iteration stops if f returns false.
268 func (ts TraceState) Walk(f func(key, value string) bool) {
269 for _, m := range ts.list {
270 if !f(m.Key, m.Value) {
271 break
272 }
273 }
274 }
275
276 // Insert adds a new list-member defined by the key/value pair to the
277 // TraceState. If a list-member already exists for the given key, that
278 // list-member's value is updated. The new or updated list-member is always
279 // moved to the beginning of the TraceState as specified by the W3C Trace
280 // Context specification.
281 //
282 // If key or value are invalid according to the W3C Trace Context
283 // specification an error is returned with the original TraceState.
284 //
285 // If adding a new list-member means the TraceState would have more members
286 // then is allowed, the new list-member will be inserted and the right-most
287 // list-member will be dropped in the returned TraceState.
288 func (ts TraceState) Insert(key, value string) (TraceState, error) {
289 m, err := newMember(key, value)
290 if err != nil {
291 return ts, err
292 }
293 n := len(ts.list)
294 found := n
295 for i := range ts.list {
296 if ts.list[i].Key == key {
297 found = i
298 }
299 }
300 cTS := TraceState{}
301 if found == n && n < maxListMembers {
302 cTS.list = make([]member, n+1)
303 } else {
304 cTS.list = make([]member, n)
305 }
306 cTS.list[0] = m
307 // When the number of members exceeds capacity, drop the "right-most".
308 copy(cTS.list[1:], ts.list[0:found])
309 if found < n {
310 copy(cTS.list[1+found:], ts.list[found+1:])
311 }
312 return cTS, nil
313 }
314
315 // Delete returns a copy of the TraceState with the list-member identified by
316 // key removed.
317 func (ts TraceState) Delete(key string) TraceState {
318 members := make([]member, ts.Len())
319 copy(members, ts.list)
320 for i, member := range ts.list {
321 if member.Key == key {
322 members = append(members[:i], members[i+1:]...)
323 // TraceState should contain no duplicate members.
324 break
325 }
326 }
327 return TraceState{list: members}
328 }
329
330 // Len returns the number of list-members in the TraceState.
331 func (ts TraceState) Len() int {
332 return len(ts.list)
333 }