1 // Copyright 2019 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "quiche/common/structured_headers.h"
6
7 #include <cmath>
8 #include <cstddef>
9 #include <cstdint>
10 #include <optional>
11 #include <sstream>
12 #include <string>
13 #include <utility>
14 #include <vector>
15
16 #include "absl/algorithm/container.h"
17 #include "absl/container/flat_hash_set.h"
18 #include "absl/strings/ascii.h"
19 #include "absl/strings/escaping.h"
20 #include "absl/strings/numbers.h"
21 #include "absl/strings/str_format.h"
22 #include "absl/strings/string_view.h"
23 #include "absl/types/span.h"
24 #include "quiche/common/platform/api/quiche_logging.h"
25
26 namespace quiche {
27 namespace structured_headers {
28
29 namespace {
30
31 #define DIGIT "0123456789"
32 #define LCALPHA "abcdefghijklmnopqrstuvwxyz"
33 #define UCALPHA "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
34 #define TCHAR DIGIT LCALPHA UCALPHA "!#$%&'*+-.^_`|~"
35 // https://tools.ietf.org/html/draft-ietf-httpbis-header-structure-09#section-3.9
36 constexpr char kTokenChars09[] = DIGIT UCALPHA LCALPHA "_-.:%*/";
37 // https://www.rfc-editor.org/rfc/rfc8941.html#section-3.3.4
38 constexpr char kTokenChars[] = TCHAR ":/";
39 // https://tools.ietf.org/html/draft-ietf-httpbis-header-structure-09#section-3.1
40 constexpr char kKeyChars09[] = DIGIT LCALPHA "_-";
41 // https://www.rfc-editor.org/rfc/rfc8941.html#section-3.1.2
42 constexpr char kKeyChars[] = DIGIT LCALPHA "_-.*";
43 constexpr char kSP[] = " ";
44 constexpr char kOWS[] = " \t";
45 #undef DIGIT
46 #undef LCALPHA
47 #undef UCALPHA
48
49 // https://www.rfc-editor.org/rfc/rfc8941.html#section-3.3.1
50 constexpr int64_t kMaxInteger = 999'999'999'999'999L;
51 constexpr int64_t kMinInteger = -999'999'999'999'999L;
52
53 // Smallest value which is too large for an sh-decimal. This is the smallest
54 // double which will round up to 1e12 when serialized, which exceeds the range
55 // for sh-decimal. Any float less than this should round down. This behaviour is
56 // verified by unit tests.
57 constexpr double kTooLargeDecimal = 1e12 - 0.0005;
58
59 // Removes characters in remove from the beginning of s.
StripLeft(absl::string_view & s,absl::string_view remove)60 void StripLeft(absl::string_view& s, absl::string_view remove) {
61 size_t i = s.find_first_not_of(remove);
62 if (i == absl::string_view::npos) {
63 i = s.size();
64 }
65 s.remove_prefix(i);
66 }
67
68 // Parser for (a subset of) Structured Headers for HTTP defined in [SH09] and
69 // [RFC8941]. [SH09] compatibility is retained for use by Web Packaging, and can
70 // be removed once that spec is updated, and users have migrated to new headers.
71 // [SH09] https://tools.ietf.org/html/draft-ietf-httpbis-header-structure-09
72 // [RFC8941] https://www.rfc-editor.org/rfc/rfc8941.html
73 class StructuredHeaderParser {
74 public:
75 enum DraftVersion {
76 kDraft09,
77 kFinal,
78 };
StructuredHeaderParser(absl::string_view str,DraftVersion version)79 explicit StructuredHeaderParser(absl::string_view str, DraftVersion version)
80 : input_(str), version_(version) {
81 // [SH09] 4.2 Step 1.
82 // Discard any leading OWS from input_string.
83 // [RFC8941] 4.2 Step 2.
84 // Discard any leading SP characters from input_string.
85 SkipWhitespaces();
86 }
87 StructuredHeaderParser(const StructuredHeaderParser&) = delete;
88 StructuredHeaderParser& operator=(const StructuredHeaderParser&) = delete;
89
90 // Callers should call this after ReadSomething(), to check if parser has
91 // consumed all the input successfully.
FinishParsing()92 bool FinishParsing() {
93 // [SH09] 4.2 Step 7.
94 // Discard any leading OWS from input_string.
95 // [RFC8941] 4.2 Step 6.
96 // Discard any leading SP characters from input_string.
97 SkipWhitespaces();
98 // [SH09] 4.2 Step 8. [RFC8941] 4.2 Step 7.
99 // If input_string is not empty, fail parsing.
100 return input_.empty();
101 }
102
103 // Parses a List of Lists ([SH09] 4.2.4).
ReadListOfLists()104 std::optional<ListOfLists> ReadListOfLists() {
105 QUICHE_CHECK_EQ(version_, kDraft09);
106 ListOfLists result;
107 while (true) {
108 std::vector<Item> inner_list;
109 while (true) {
110 std::optional<Item> item(ReadBareItem());
111 if (!item) return std::nullopt;
112 inner_list.push_back(std::move(*item));
113 SkipWhitespaces();
114 if (!ConsumeChar(';')) break;
115 SkipWhitespaces();
116 }
117 result.push_back(std::move(inner_list));
118 SkipWhitespaces();
119 if (!ConsumeChar(',')) break;
120 SkipWhitespaces();
121 }
122 return result;
123 }
124
125 // Parses a List ([RFC8941] 4.2.1).
ReadList()126 std::optional<List> ReadList() {
127 QUICHE_CHECK_EQ(version_, kFinal);
128 List members;
129 while (!input_.empty()) {
130 std::optional<ParameterizedMember> member(ReadItemOrInnerList());
131 if (!member) return std::nullopt;
132 members.push_back(std::move(*member));
133 SkipOWS();
134 if (input_.empty()) break;
135 if (!ConsumeChar(',')) return std::nullopt;
136 SkipOWS();
137 if (input_.empty()) return std::nullopt;
138 }
139 return members;
140 }
141
142 // Parses an Item ([RFC8941] 4.2.3).
ReadItem()143 std::optional<ParameterizedItem> ReadItem() {
144 std::optional<Item> item = ReadBareItem();
145 if (!item) return std::nullopt;
146 std::optional<Parameters> parameters = ReadParameters();
147 if (!parameters) return std::nullopt;
148 return ParameterizedItem(std::move(*item), std::move(*parameters));
149 }
150
151 // Parses a bare Item ([RFC8941] 4.2.3.1, though this is also the algorithm
152 // for parsing an Item from [SH09] 4.2.7).
ReadBareItem()153 std::optional<Item> ReadBareItem() {
154 if (input_.empty()) {
155 QUICHE_DVLOG(1) << "ReadBareItem: unexpected EOF";
156 return std::nullopt;
157 }
158 switch (input_.front()) {
159 case '"':
160 return ReadString();
161 case '*':
162 if (version_ == kDraft09) return ReadByteSequence();
163 return ReadToken();
164 case ':':
165 if (version_ == kFinal) return ReadByteSequence();
166 return std::nullopt;
167 case '?':
168 return ReadBoolean();
169 default:
170 if (input_.front() == '-' || absl::ascii_isdigit(input_.front()))
171 return ReadNumber();
172 if (absl::ascii_isalpha(input_.front())) return ReadToken();
173 return std::nullopt;
174 }
175 }
176
177 // Parses a Dictionary ([RFC8941] 4.2.2).
ReadDictionary()178 std::optional<Dictionary> ReadDictionary() {
179 QUICHE_CHECK_EQ(version_, kFinal);
180 Dictionary members;
181 while (!input_.empty()) {
182 std::optional<std::string> key(ReadKey());
183 if (!key) return std::nullopt;
184 std::optional<ParameterizedMember> member;
185 if (ConsumeChar('=')) {
186 member = ReadItemOrInnerList();
187 if (!member) return std::nullopt;
188 } else {
189 std::optional<Parameters> parameters = ReadParameters();
190 if (!parameters) return std::nullopt;
191 member = ParameterizedMember{Item(true), std::move(*parameters)};
192 }
193 members[*key] = std::move(*member);
194 SkipOWS();
195 if (input_.empty()) break;
196 if (!ConsumeChar(',')) return std::nullopt;
197 SkipOWS();
198 if (input_.empty()) return std::nullopt;
199 }
200 return members;
201 }
202
203 // Parses a Parameterised List ([SH09] 4.2.5).
ReadParameterisedList()204 std::optional<ParameterisedList> ReadParameterisedList() {
205 QUICHE_CHECK_EQ(version_, kDraft09);
206 ParameterisedList items;
207 while (true) {
208 std::optional<ParameterisedIdentifier> item =
209 ReadParameterisedIdentifier();
210 if (!item) return std::nullopt;
211 items.push_back(std::move(*item));
212 SkipWhitespaces();
213 if (!ConsumeChar(',')) return items;
214 SkipWhitespaces();
215 }
216 }
217
218 private:
219 // Parses a Parameterised Identifier ([SH09] 4.2.6).
ReadParameterisedIdentifier()220 std::optional<ParameterisedIdentifier> ReadParameterisedIdentifier() {
221 QUICHE_CHECK_EQ(version_, kDraft09);
222 std::optional<Item> primary_identifier = ReadToken();
223 if (!primary_identifier) return std::nullopt;
224
225 ParameterisedIdentifier::Parameters parameters;
226
227 SkipWhitespaces();
228 while (ConsumeChar(';')) {
229 SkipWhitespaces();
230
231 std::optional<std::string> name = ReadKey();
232 if (!name) return std::nullopt;
233
234 Item value;
235 if (ConsumeChar('=')) {
236 auto item = ReadBareItem();
237 if (!item) return std::nullopt;
238 value = std::move(*item);
239 }
240 if (!parameters.emplace(*name, std::move(value)).second) {
241 QUICHE_DVLOG(1) << "ReadParameterisedIdentifier: duplicated parameter: "
242 << *name;
243 return std::nullopt;
244 }
245 SkipWhitespaces();
246 }
247 return ParameterisedIdentifier(std::move(*primary_identifier),
248 std::move(parameters));
249 }
250
251 // Parses an Item or Inner List ([RFC8941] 4.2.1.1).
ReadItemOrInnerList()252 std::optional<ParameterizedMember> ReadItemOrInnerList() {
253 QUICHE_CHECK_EQ(version_, kFinal);
254 bool member_is_inner_list = (!input_.empty() && input_.front() == '(');
255 if (member_is_inner_list) {
256 return ReadInnerList();
257 } else {
258 auto item = ReadItem();
259 if (!item) return std::nullopt;
260 return ParameterizedMember(std::move(item->item),
261 std::move(item->params));
262 }
263 }
264
265 // Parses Parameters ([RFC8941] 4.2.3.2)
ReadParameters()266 std::optional<Parameters> ReadParameters() {
267 Parameters parameters;
268 absl::flat_hash_set<std::string> keys;
269
270 while (ConsumeChar(';')) {
271 SkipWhitespaces();
272
273 std::optional<std::string> name = ReadKey();
274 if (!name) return std::nullopt;
275 bool is_duplicate_key = !keys.insert(*name).second;
276
277 Item value{true};
278 if (ConsumeChar('=')) {
279 auto item = ReadBareItem();
280 if (!item) return std::nullopt;
281 value = std::move(*item);
282 }
283 if (is_duplicate_key) {
284 for (auto& param : parameters) {
285 if (param.first == name) {
286 param.second = std::move(value);
287 break;
288 }
289 }
290 } else {
291 parameters.emplace_back(std::move(*name), std::move(value));
292 }
293 }
294 return parameters;
295 }
296
297 // Parses an Inner List ([RFC8941] 4.2.1.2).
ReadInnerList()298 std::optional<ParameterizedMember> ReadInnerList() {
299 QUICHE_CHECK_EQ(version_, kFinal);
300 if (!ConsumeChar('(')) return std::nullopt;
301 std::vector<ParameterizedItem> inner_list;
302 while (true) {
303 SkipWhitespaces();
304 if (ConsumeChar(')')) {
305 std::optional<Parameters> parameters = ReadParameters();
306 if (!parameters) return std::nullopt;
307 return ParameterizedMember(std::move(inner_list), true,
308 std::move(*parameters));
309 }
310 auto item = ReadItem();
311 if (!item) return std::nullopt;
312 inner_list.push_back(std::move(*item));
313 if (input_.empty() || (input_.front() != ' ' && input_.front() != ')'))
314 return std::nullopt;
315 }
316 QUICHE_NOTREACHED();
317 return std::nullopt;
318 }
319
320 // Parses a Key ([SH09] 4.2.2, [RFC8941] 4.2.3.3).
ReadKey()321 std::optional<std::string> ReadKey() {
322 if (version_ == kDraft09) {
323 if (input_.empty() || !absl::ascii_islower(input_.front())) {
324 LogParseError("ReadKey", "lcalpha");
325 return std::nullopt;
326 }
327 } else {
328 if (input_.empty() ||
329 (!absl::ascii_islower(input_.front()) && input_.front() != '*')) {
330 LogParseError("ReadKey", "lcalpha | *");
331 return std::nullopt;
332 }
333 }
334 const char* allowed_chars =
335 (version_ == kDraft09 ? kKeyChars09 : kKeyChars);
336 size_t len = input_.find_first_not_of(allowed_chars);
337 if (len == absl::string_view::npos) len = input_.size();
338 std::string key(input_.substr(0, len));
339 input_.remove_prefix(len);
340 return key;
341 }
342
343 // Parses a Token ([SH09] 4.2.10, [RFC8941] 4.2.6).
ReadToken()344 std::optional<Item> ReadToken() {
345 if (input_.empty() ||
346 !(absl::ascii_isalpha(input_.front()) || input_.front() == '*')) {
347 LogParseError("ReadToken", "ALPHA");
348 return std::nullopt;
349 }
350 size_t len = input_.find_first_not_of(version_ == kDraft09 ? kTokenChars09
351 : kTokenChars);
352 if (len == absl::string_view::npos) len = input_.size();
353 std::string token(input_.substr(0, len));
354 input_.remove_prefix(len);
355 return Item(std::move(token), Item::kTokenType);
356 }
357
358 // Parses a Number ([SH09] 4.2.8, [RFC8941] 4.2.4).
ReadNumber()359 std::optional<Item> ReadNumber() {
360 bool is_negative = ConsumeChar('-');
361 bool is_decimal = false;
362 size_t decimal_position = 0;
363 size_t i = 0;
364 for (; i < input_.size(); ++i) {
365 if (i > 0 && input_[i] == '.' && !is_decimal) {
366 is_decimal = true;
367 decimal_position = i;
368 continue;
369 }
370 if (!absl::ascii_isdigit(input_[i])) break;
371 }
372 if (i == 0) {
373 LogParseError("ReadNumber", "DIGIT");
374 return std::nullopt;
375 }
376 if (!is_decimal) {
377 // [RFC8941] restricts the range of integers further.
378 if (version_ == kFinal && i > 15) {
379 LogParseError("ReadNumber", "integer too long");
380 return std::nullopt;
381 }
382 } else {
383 if (version_ != kFinal && i > 16) {
384 LogParseError("ReadNumber", "float too long");
385 return std::nullopt;
386 }
387 if (version_ == kFinal && decimal_position > 12) {
388 LogParseError("ReadNumber", "decimal too long");
389 return std::nullopt;
390 }
391 if (i - decimal_position > (version_ == kFinal ? 4 : 7)) {
392 LogParseError("ReadNumber", "too many digits after decimal");
393 return std::nullopt;
394 }
395 if (i == decimal_position) {
396 LogParseError("ReadNumber", "no digits after decimal");
397 return std::nullopt;
398 }
399 }
400 std::string output_number_string(input_.substr(0, i));
401 input_.remove_prefix(i);
402
403 if (is_decimal) {
404 // Convert to a 64-bit double, and return if the conversion is
405 // successful.
406 double f;
407 if (!absl::SimpleAtod(output_number_string, &f)) return std::nullopt;
408 return Item(is_negative ? -f : f);
409 } else {
410 // Convert to a 64-bit signed integer, and return if the conversion is
411 // successful.
412 int64_t n;
413 if (!absl::SimpleAtoi(output_number_string, &n)) return std::nullopt;
414 QUICHE_CHECK(version_ != kFinal ||
415 (n <= kMaxInteger && n >= kMinInteger));
416 return Item(is_negative ? -n : n);
417 }
418 }
419
420 // Parses a String ([SH09] 4.2.9, [RFC8941] 4.2.5).
ReadString()421 std::optional<Item> ReadString() {
422 std::string s;
423 if (!ConsumeChar('"')) {
424 LogParseError("ReadString", "'\"'");
425 return std::nullopt;
426 }
427 while (!ConsumeChar('"')) {
428 size_t i = 0;
429 for (; i < input_.size(); ++i) {
430 if (!absl::ascii_isprint(input_[i])) {
431 QUICHE_DVLOG(1) << "ReadString: non printable-ASCII character";
432 return std::nullopt;
433 }
434 if (input_[i] == '"' || input_[i] == '\\') break;
435 }
436 if (i == input_.size()) {
437 QUICHE_DVLOG(1) << "ReadString: missing closing '\"'";
438 return std::nullopt;
439 }
440 s.append(std::string(input_.substr(0, i)));
441 input_.remove_prefix(i);
442 if (ConsumeChar('\\')) {
443 if (input_.empty()) {
444 QUICHE_DVLOG(1) << "ReadString: backslash at string end";
445 return std::nullopt;
446 }
447 if (input_[0] != '"' && input_[0] != '\\') {
448 QUICHE_DVLOG(1) << "ReadString: invalid escape";
449 return std::nullopt;
450 }
451 s.push_back(input_.front());
452 input_.remove_prefix(1);
453 }
454 }
455 return s;
456 }
457
458 // Parses a Byte Sequence ([SH09] 4.2.11, [RFC8941] 4.2.7).
ReadByteSequence()459 std::optional<Item> ReadByteSequence() {
460 char delimiter = (version_ == kDraft09 ? '*' : ':');
461 if (!ConsumeChar(delimiter)) {
462 LogParseError("ReadByteSequence", "delimiter");
463 return std::nullopt;
464 }
465 size_t len = input_.find(delimiter);
466 if (len == absl::string_view::npos) {
467 QUICHE_DVLOG(1) << "ReadByteSequence: missing closing delimiter";
468 return std::nullopt;
469 }
470 std::string base64(input_.substr(0, len));
471 // Append the necessary padding characters.
472 base64.resize((base64.size() + 3) / 4 * 4, '=');
473
474 std::string binary;
475 if (!absl::Base64Unescape(base64, &binary)) {
476 QUICHE_DVLOG(1) << "ReadByteSequence: failed to decode base64: "
477 << base64;
478 return std::nullopt;
479 }
480 input_.remove_prefix(len);
481 ConsumeChar(delimiter);
482 return Item(std::move(binary), Item::kByteSequenceType);
483 }
484
485 // Parses a Boolean ([RFC8941] 4.2.8).
486 // Note that this only parses ?0 and ?1 forms from SH version 10+, not the
487 // previous ?F and ?T, which were not needed by any consumers of SH version 9.
ReadBoolean()488 std::optional<Item> ReadBoolean() {
489 if (!ConsumeChar('?')) {
490 LogParseError("ReadBoolean", "'?'");
491 return std::nullopt;
492 }
493 if (ConsumeChar('1')) {
494 return Item(true);
495 }
496 if (ConsumeChar('0')) {
497 return Item(false);
498 }
499 return std::nullopt;
500 }
501
502 // There are several points in the specs where the handling of whitespace
503 // differs between Draft 9 and the final RFC. In those cases, Draft 9 allows
504 // any OWS character, while the RFC allows only a U+0020 SPACE.
SkipWhitespaces()505 void SkipWhitespaces() {
506 if (version_ == kDraft09) {
507 StripLeft(input_, kOWS);
508 } else {
509 StripLeft(input_, kSP);
510 }
511 }
512
SkipOWS()513 void SkipOWS() { StripLeft(input_, kOWS); }
514
ConsumeChar(char expected)515 bool ConsumeChar(char expected) {
516 if (!input_.empty() && input_.front() == expected) {
517 input_.remove_prefix(1);
518 return true;
519 }
520 return false;
521 }
522
LogParseError(const char * func,const char * expected)523 void LogParseError(const char* func, const char* expected) {
524 QUICHE_DVLOG(1) << func << ": " << expected << " expected, got "
525 << (input_.empty()
526 ? "EOS"
527 : "'" + std::string(input_.substr(0, 1)) + "'");
528 }
529
530 absl::string_view input_;
531 DraftVersion version_;
532 };
533
534 // Serializer for (a subset of) Structured Field Values for HTTP defined in
535 // [RFC8941]. Note that this serializer does not attempt to support [SH09].
536 class StructuredHeaderSerializer {
537 public:
538 StructuredHeaderSerializer() = default;
539 ~StructuredHeaderSerializer() = default;
540 StructuredHeaderSerializer(const StructuredHeaderSerializer&) = delete;
541 StructuredHeaderSerializer& operator=(const StructuredHeaderSerializer&) =
542 delete;
543
Output()544 std::string Output() { return output_.str(); }
545
546 // Serializes a List ([RFC8941] 4.1.1).
WriteList(const List & value)547 bool WriteList(const List& value) {
548 bool first = true;
549 for (const auto& member : value) {
550 if (!first) output_ << ", ";
551 if (!WriteParameterizedMember(member)) return false;
552 first = false;
553 }
554 return true;
555 }
556
557 // Serializes an Item ([RFC8941] 4.1.3).
WriteItem(const ParameterizedItem & value)558 bool WriteItem(const ParameterizedItem& value) {
559 if (!WriteBareItem(value.item)) return false;
560 return WriteParameters(value.params);
561 }
562
563 // Serializes an Item ([RFC8941] 4.1.3).
WriteBareItem(const Item & value)564 bool WriteBareItem(const Item& value) {
565 if (value.is_string()) {
566 // Serializes a String ([RFC8941] 4.1.6).
567 output_ << "\"";
568 for (const char& c : value.GetString()) {
569 if (!absl::ascii_isprint(c)) return false;
570 if (c == '\\' || c == '\"') output_ << "\\";
571 output_ << c;
572 }
573 output_ << "\"";
574 return true;
575 }
576 if (value.is_token()) {
577 // Serializes a Token ([RFC8941] 4.1.7).
578 if (!IsValidToken(value.GetString())) {
579 return false;
580 }
581 output_ << value.GetString();
582 return true;
583 }
584 if (value.is_byte_sequence()) {
585 // Serializes a Byte Sequence ([RFC8941] 4.1.8).
586 output_ << ":";
587 output_ << absl::Base64Escape(value.GetString());
588 output_ << ":";
589 return true;
590 }
591 if (value.is_integer()) {
592 // Serializes an Integer ([RFC8941] 4.1.4).
593 if (value.GetInteger() > kMaxInteger || value.GetInteger() < kMinInteger)
594 return false;
595 output_ << value.GetInteger();
596 return true;
597 }
598 if (value.is_decimal()) {
599 // Serializes a Decimal ([RFC8941] 4.1.5).
600 double decimal_value = value.GetDecimal();
601 if (!std::isfinite(decimal_value) ||
602 fabs(decimal_value) >= kTooLargeDecimal)
603 return false;
604
605 // Handle sign separately to simplify the rest of the formatting.
606 if (decimal_value < 0) output_ << "-";
607 // Unconditionally take absolute value to ensure that -0 is serialized as
608 // "0.0", with no negative sign, as required by spec. (4.1.5, step 2).
609 decimal_value = fabs(decimal_value);
610 double remainder = fmod(decimal_value, 0.002);
611 if (remainder == 0.0005) {
612 // Value ended in exactly 0.0005, 0.0025, 0.0045, etc. Round down.
613 decimal_value -= 0.0005;
614 } else if (remainder == 0.0015) {
615 // Value ended in exactly 0.0015, 0.0035, 0,0055, etc. Round up.
616 decimal_value += 0.0005;
617 } else {
618 // Standard rounding will work in all other cases.
619 decimal_value = round(decimal_value * 1000.0) / 1000.0;
620 }
621
622 // Use standard library functions to write the decimal, and then truncate
623 // if necessary to conform to spec.
624
625 // Maximum is 12 integer digits, one decimal point, three fractional
626 // digits, and a null terminator.
627 char buffer[17];
628 absl::SNPrintF(buffer, std::size(buffer), "%#.3f", decimal_value);
629
630 // Strip any trailing 0s after the decimal point, but leave at least one
631 // digit after it in all cases. (So 1.230 becomes 1.23, but 1.000 becomes
632 // 1.0.)
633 absl::string_view formatted_number(buffer);
634 auto truncate_index = formatted_number.find_last_not_of('0');
635 if (formatted_number[truncate_index] == '.') truncate_index++;
636 output_ << formatted_number.substr(0, truncate_index + 1);
637 return true;
638 }
639 if (value.is_boolean()) {
640 // Serializes a Boolean ([RFC8941] 4.1.9).
641 output_ << (value.GetBoolean() ? "?1" : "?0");
642 return true;
643 }
644 return false;
645 }
646
647 // Serializes a Dictionary ([RFC8941] 4.1.2).
WriteDictionary(const Dictionary & value)648 bool WriteDictionary(const Dictionary& value) {
649 bool first = true;
650 for (const auto& [dict_key, dict_value] : value) {
651 if (!first) output_ << ", ";
652 if (!WriteKey(dict_key)) return false;
653 first = false;
654 if (!dict_value.member_is_inner_list && !dict_value.member.empty() &&
655 dict_value.member.front().item.is_boolean() &&
656 dict_value.member.front().item.GetBoolean()) {
657 if (!WriteParameters(dict_value.params)) return false;
658 } else {
659 output_ << "=";
660 if (!WriteParameterizedMember(dict_value)) return false;
661 }
662 }
663 return true;
664 }
665
666 private:
WriteParameterizedMember(const ParameterizedMember & value)667 bool WriteParameterizedMember(const ParameterizedMember& value) {
668 // Serializes a parameterized member ([RFC8941] 4.1.1).
669 if (value.member_is_inner_list) {
670 if (!WriteInnerList(value.member)) return false;
671 } else {
672 QUICHE_CHECK_EQ(value.member.size(), 1UL);
673 if (!WriteItem(value.member[0])) return false;
674 }
675 return WriteParameters(value.params);
676 }
677
WriteInnerList(const std::vector<ParameterizedItem> & value)678 bool WriteInnerList(const std::vector<ParameterizedItem>& value) {
679 // Serializes an inner list ([RFC8941] 4.1.1.1).
680 output_ << "(";
681 bool first = true;
682 for (const ParameterizedItem& member : value) {
683 if (!first) output_ << " ";
684 if (!WriteItem(member)) return false;
685 first = false;
686 }
687 output_ << ")";
688 return true;
689 }
690
WriteParameters(const Parameters & value)691 bool WriteParameters(const Parameters& value) {
692 // Serializes a parameter list ([RFC8941] 4.1.1.2).
693 for (const auto& param_name_and_value : value) {
694 const std::string& param_name = param_name_and_value.first;
695 const Item& param_value = param_name_and_value.second;
696 output_ << ";";
697 if (!WriteKey(param_name)) return false;
698 if (!param_value.is_null()) {
699 if (param_value.is_boolean() && param_value.GetBoolean()) continue;
700 output_ << "=";
701 if (!WriteBareItem(param_value)) return false;
702 }
703 }
704 return true;
705 }
706
WriteKey(const std::string & value)707 bool WriteKey(const std::string& value) {
708 // Serializes a Key ([RFC8941] 4.1.1.3).
709 if (value.empty()) return false;
710 if (value.find_first_not_of(kKeyChars) != std::string::npos) return false;
711 if (!absl::ascii_islower(value[0]) && value[0] != '*') return false;
712 output_ << value;
713 return true;
714 }
715
716 std::ostringstream output_;
717 };
718
719 } // namespace
720
ItemTypeToString(Item::ItemType type)721 absl::string_view ItemTypeToString(Item::ItemType type) {
722 switch (type) {
723 case Item::kNullType:
724 return "null";
725 case Item::kIntegerType:
726 return "integer";
727 case Item::kDecimalType:
728 return "decimal";
729 case Item::kStringType:
730 return "string";
731 case Item::kTokenType:
732 return "token";
733 case Item::kByteSequenceType:
734 return "byte sequence";
735 case Item::kBooleanType:
736 return "boolean";
737 }
738 return "[invalid type]";
739 }
740
IsValidToken(absl::string_view str)741 bool IsValidToken(absl::string_view str) {
742 // Validate Token value per [RFC8941] 4.1.7.
743 if (str.empty() ||
744 !(absl::ascii_isalpha(str.front()) || str.front() == '*')) {
745 return false;
746 }
747 if (str.find_first_not_of(kTokenChars) != std::string::npos) {
748 return false;
749 }
750 return true;
751 }
752
Item()753 Item::Item() {}
Item(std::string value,Item::ItemType type)754 Item::Item(std::string value, Item::ItemType type) {
755 switch (type) {
756 case kStringType:
757 value_.emplace<kStringType>(std::move(value));
758 break;
759 case kTokenType:
760 value_.emplace<kTokenType>(std::move(value));
761 break;
762 case kByteSequenceType:
763 value_.emplace<kByteSequenceType>(std::move(value));
764 break;
765 default:
766 QUICHE_CHECK(false);
767 break;
768 }
769 }
Item(const char * value,Item::ItemType type)770 Item::Item(const char* value, Item::ItemType type)
771 : Item(std::string(value), type) {}
Item(int64_t value)772 Item::Item(int64_t value) : value_(value) {}
Item(double value)773 Item::Item(double value) : value_(value) {}
Item(bool value)774 Item::Item(bool value) : value_(value) {}
775
operator ==(const Item & lhs,const Item & rhs)776 bool operator==(const Item& lhs, const Item& rhs) {
777 return lhs.value_ == rhs.value_;
778 }
779
780 ParameterizedItem::ParameterizedItem() = default;
781 ParameterizedItem::ParameterizedItem(const ParameterizedItem&) = default;
782 ParameterizedItem& ParameterizedItem::operator=(const ParameterizedItem&) =
783 default;
ParameterizedItem(Item id,Parameters ps)784 ParameterizedItem::ParameterizedItem(Item id, Parameters ps)
785 : item(std::move(id)), params(std::move(ps)) {}
786 ParameterizedItem::~ParameterizedItem() = default;
787
788 ParameterizedMember::ParameterizedMember() = default;
789 ParameterizedMember::ParameterizedMember(const ParameterizedMember&) = default;
790 ParameterizedMember& ParameterizedMember::operator=(
791 const ParameterizedMember&) = default;
ParameterizedMember(std::vector<ParameterizedItem> id,bool member_is_inner_list,Parameters ps)792 ParameterizedMember::ParameterizedMember(std::vector<ParameterizedItem> id,
793 bool member_is_inner_list,
794 Parameters ps)
795 : member(std::move(id)),
796 member_is_inner_list(member_is_inner_list),
797 params(std::move(ps)) {}
ParameterizedMember(std::vector<ParameterizedItem> id,Parameters ps)798 ParameterizedMember::ParameterizedMember(std::vector<ParameterizedItem> id,
799 Parameters ps)
800 : member(std::move(id)),
801 member_is_inner_list(true),
802 params(std::move(ps)) {}
ParameterizedMember(Item id,Parameters ps)803 ParameterizedMember::ParameterizedMember(Item id, Parameters ps)
804 : member({{std::move(id), {}}}),
805 member_is_inner_list(false),
806 params(std::move(ps)) {}
807 ParameterizedMember::~ParameterizedMember() = default;
808
809 ParameterisedIdentifier::ParameterisedIdentifier() = default;
810 ParameterisedIdentifier::ParameterisedIdentifier(
811 const ParameterisedIdentifier&) = default;
812 ParameterisedIdentifier& ParameterisedIdentifier::operator=(
813 const ParameterisedIdentifier&) = default;
ParameterisedIdentifier(Item id,Parameters ps)814 ParameterisedIdentifier::ParameterisedIdentifier(Item id, Parameters ps)
815 : identifier(std::move(id)), params(std::move(ps)) {}
816 ParameterisedIdentifier::~ParameterisedIdentifier() = default;
817
818 Dictionary::Dictionary() = default;
819 Dictionary::Dictionary(const Dictionary&) = default;
820 Dictionary::Dictionary(Dictionary&&) = default;
Dictionary(std::vector<DictionaryMember> members)821 Dictionary::Dictionary(std::vector<DictionaryMember> members)
822 : members_(std::move(members)) {}
823 Dictionary::~Dictionary() = default;
begin()824 Dictionary::iterator Dictionary::begin() { return members_.begin(); }
begin() const825 Dictionary::const_iterator Dictionary::begin() const {
826 return members_.begin();
827 }
end()828 Dictionary::iterator Dictionary::end() { return members_.end(); }
end() const829 Dictionary::const_iterator Dictionary::end() const { return members_.end(); }
operator [](std::size_t idx)830 ParameterizedMember& Dictionary::operator[](std::size_t idx) {
831 return members_[idx].second;
832 }
operator [](std::size_t idx) const833 const ParameterizedMember& Dictionary::operator[](std::size_t idx) const {
834 return members_[idx].second;
835 }
at(std::size_t idx)836 ParameterizedMember& Dictionary::at(std::size_t idx) { return (*this)[idx]; }
at(std::size_t idx) const837 const ParameterizedMember& Dictionary::at(std::size_t idx) const {
838 return (*this)[idx];
839 }
operator [](absl::string_view key)840 ParameterizedMember& Dictionary::operator[](absl::string_view key) {
841 auto it = find(key);
842 if (it != end()) return it->second;
843 return members_.emplace_back(key, ParameterizedMember()).second;
844 }
at(absl::string_view key)845 ParameterizedMember& Dictionary::at(absl::string_view key) {
846 auto it = find(key);
847 QUICHE_CHECK(it != end()) << "Provided key not found in dictionary";
848 return it->second;
849 }
at(absl::string_view key) const850 const ParameterizedMember& Dictionary::at(absl::string_view key) const {
851 auto it = find(key);
852 QUICHE_CHECK(it != end()) << "Provided key not found in dictionary";
853 return it->second;
854 }
find(absl::string_view key) const855 Dictionary::const_iterator Dictionary::find(absl::string_view key) const {
856 return absl::c_find_if(
857 members_, [key](const auto& member) { return member.first == key; });
858 }
find(absl::string_view key)859 Dictionary::iterator Dictionary::find(absl::string_view key) {
860 return absl::c_find_if(
861 members_, [key](const auto& member) { return member.first == key; });
862 }
empty() const863 bool Dictionary::empty() const { return members_.empty(); }
size() const864 std::size_t Dictionary::size() const { return members_.size(); }
contains(absl::string_view key) const865 bool Dictionary::contains(absl::string_view key) const {
866 return find(key) != end();
867 }
clear()868 void Dictionary::clear() { members_.clear(); }
869
ParseItem(absl::string_view str)870 std::optional<ParameterizedItem> ParseItem(absl::string_view str) {
871 StructuredHeaderParser parser(str, StructuredHeaderParser::kFinal);
872 std::optional<ParameterizedItem> item = parser.ReadItem();
873 if (item && parser.FinishParsing()) return item;
874 return std::nullopt;
875 }
876
ParseBareItem(absl::string_view str)877 std::optional<Item> ParseBareItem(absl::string_view str) {
878 StructuredHeaderParser parser(str, StructuredHeaderParser::kFinal);
879 std::optional<Item> item = parser.ReadBareItem();
880 if (item && parser.FinishParsing()) return item;
881 return std::nullopt;
882 }
883
ParseParameterisedList(absl::string_view str)884 std::optional<ParameterisedList> ParseParameterisedList(absl::string_view str) {
885 StructuredHeaderParser parser(str, StructuredHeaderParser::kDraft09);
886 std::optional<ParameterisedList> param_list = parser.ReadParameterisedList();
887 if (param_list && parser.FinishParsing()) return param_list;
888 return std::nullopt;
889 }
890
ParseListOfLists(absl::string_view str)891 std::optional<ListOfLists> ParseListOfLists(absl::string_view str) {
892 StructuredHeaderParser parser(str, StructuredHeaderParser::kDraft09);
893 std::optional<ListOfLists> list_of_lists = parser.ReadListOfLists();
894 if (list_of_lists && parser.FinishParsing()) return list_of_lists;
895 return std::nullopt;
896 }
897
ParseList(absl::string_view str)898 std::optional<List> ParseList(absl::string_view str) {
899 StructuredHeaderParser parser(str, StructuredHeaderParser::kFinal);
900 std::optional<List> list = parser.ReadList();
901 if (list && parser.FinishParsing()) return list;
902 return std::nullopt;
903 }
904
ParseDictionary(absl::string_view str)905 std::optional<Dictionary> ParseDictionary(absl::string_view str) {
906 StructuredHeaderParser parser(str, StructuredHeaderParser::kFinal);
907 std::optional<Dictionary> dictionary = parser.ReadDictionary();
908 if (dictionary && parser.FinishParsing()) return dictionary;
909 return std::nullopt;
910 }
911
SerializeItem(const Item & value)912 std::optional<std::string> SerializeItem(const Item& value) {
913 StructuredHeaderSerializer s;
914 if (s.WriteItem(ParameterizedItem(value, {}))) return s.Output();
915 return std::nullopt;
916 }
917
SerializeItem(const ParameterizedItem & value)918 std::optional<std::string> SerializeItem(const ParameterizedItem& value) {
919 StructuredHeaderSerializer s;
920 if (s.WriteItem(value)) return s.Output();
921 return std::nullopt;
922 }
923
SerializeList(const List & value)924 std::optional<std::string> SerializeList(const List& value) {
925 StructuredHeaderSerializer s;
926 if (s.WriteList(value)) return s.Output();
927 return std::nullopt;
928 }
929
SerializeDictionary(const Dictionary & value)930 std::optional<std::string> SerializeDictionary(const Dictionary& value) {
931 StructuredHeaderSerializer s;
932 if (s.WriteDictionary(value)) return s.Output();
933 return std::nullopt;
934 }
935
936 } // namespace structured_headers
937 } // namespace quiche
938