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;
190 parameters = ReadParameters();
191 if (!parameters) return std::nullopt;
192 member = ParameterizedMember{Item(true), std::move(*parameters)};
193 }
194 members[*key] = std::move(*member);
195 SkipOWS();
196 if (input_.empty()) break;
197 if (!ConsumeChar(',')) return std::nullopt;
198 SkipOWS();
199 if (input_.empty()) return std::nullopt;
200 }
201 return members;
202 }
203
204 // Parses a Parameterised List ([SH09] 4.2.5).
ReadParameterisedList()205 std::optional<ParameterisedList> ReadParameterisedList() {
206 QUICHE_CHECK_EQ(version_, kDraft09);
207 ParameterisedList items;
208 while (true) {
209 std::optional<ParameterisedIdentifier> item =
210 ReadParameterisedIdentifier();
211 if (!item) return std::nullopt;
212 items.push_back(std::move(*item));
213 SkipWhitespaces();
214 if (!ConsumeChar(',')) return items;
215 SkipWhitespaces();
216 }
217 }
218
219 private:
220 // Parses a Parameterised Identifier ([SH09] 4.2.6).
ReadParameterisedIdentifier()221 std::optional<ParameterisedIdentifier> ReadParameterisedIdentifier() {
222 QUICHE_CHECK_EQ(version_, kDraft09);
223 std::optional<Item> primary_identifier = ReadToken();
224 if (!primary_identifier) return std::nullopt;
225
226 ParameterisedIdentifier::Parameters parameters;
227
228 SkipWhitespaces();
229 while (ConsumeChar(';')) {
230 SkipWhitespaces();
231
232 std::optional<std::string> name = ReadKey();
233 if (!name) return std::nullopt;
234
235 Item value;
236 if (ConsumeChar('=')) {
237 auto item = ReadBareItem();
238 if (!item) return std::nullopt;
239 value = std::move(*item);
240 }
241 if (!parameters.emplace(*name, value).second) {
242 QUICHE_DVLOG(1) << "ReadParameterisedIdentifier: duplicated parameter: "
243 << *name;
244 return std::nullopt;
245 }
246 SkipWhitespaces();
247 }
248 return ParameterisedIdentifier(std::move(*primary_identifier),
249 std::move(parameters));
250 }
251
252 // Parses an Item or Inner List ([RFC8941] 4.2.1.1).
ReadItemOrInnerList()253 std::optional<ParameterizedMember> ReadItemOrInnerList() {
254 QUICHE_CHECK_EQ(version_, kFinal);
255 std::vector<Item> member;
256 bool member_is_inner_list = (!input_.empty() && input_.front() == '(');
257 if (member_is_inner_list) {
258 return ReadInnerList();
259 } else {
260 auto item = ReadItem();
261 if (!item) return std::nullopt;
262 return ParameterizedMember(std::move(item->item),
263 std::move(item->params));
264 }
265 }
266
267 // Parses Parameters ([RFC8941] 4.2.3.2)
ReadParameters()268 std::optional<Parameters> ReadParameters() {
269 Parameters parameters;
270 absl::flat_hash_set<std::string> keys;
271
272 while (ConsumeChar(';')) {
273 SkipWhitespaces();
274
275 std::optional<std::string> name = ReadKey();
276 if (!name) return std::nullopt;
277 bool is_duplicate_key = !keys.insert(*name).second;
278
279 Item value{true};
280 if (ConsumeChar('=')) {
281 auto item = ReadBareItem();
282 if (!item) return std::nullopt;
283 value = std::move(*item);
284 }
285 if (is_duplicate_key) {
286 for (auto& param : parameters) {
287 if (param.first == name) {
288 param.second = std::move(value);
289 break;
290 }
291 }
292 } else {
293 parameters.emplace_back(std::move(*name), std::move(value));
294 }
295 }
296 return parameters;
297 }
298
299 // Parses an Inner List ([RFC8941] 4.2.1.2).
ReadInnerList()300 std::optional<ParameterizedMember> ReadInnerList() {
301 QUICHE_CHECK_EQ(version_, kFinal);
302 if (!ConsumeChar('(')) return std::nullopt;
303 std::vector<ParameterizedItem> inner_list;
304 while (true) {
305 SkipWhitespaces();
306 if (ConsumeChar(')')) {
307 std::optional<Parameters> parameters;
308 parameters = ReadParameters();
309 if (!parameters) return std::nullopt;
310 return ParameterizedMember(std::move(inner_list), true,
311 std::move(*parameters));
312 }
313 auto item = ReadItem();
314 if (!item) return std::nullopt;
315 inner_list.push_back(std::move(*item));
316 if (input_.empty() || (input_.front() != ' ' && input_.front() != ')'))
317 return std::nullopt;
318 }
319 QUICHE_NOTREACHED();
320 return std::nullopt;
321 }
322
323 // Parses a Key ([SH09] 4.2.2, [RFC8941] 4.2.3.3).
ReadKey()324 std::optional<std::string> ReadKey() {
325 if (version_ == kDraft09) {
326 if (input_.empty() || !absl::ascii_islower(input_.front())) {
327 LogParseError("ReadKey", "lcalpha");
328 return std::nullopt;
329 }
330 } else {
331 if (input_.empty() ||
332 (!absl::ascii_islower(input_.front()) && input_.front() != '*')) {
333 LogParseError("ReadKey", "lcalpha | *");
334 return std::nullopt;
335 }
336 }
337 const char* allowed_chars =
338 (version_ == kDraft09 ? kKeyChars09 : kKeyChars);
339 size_t len = input_.find_first_not_of(allowed_chars);
340 if (len == absl::string_view::npos) len = input_.size();
341 std::string key(input_.substr(0, len));
342 input_.remove_prefix(len);
343 return key;
344 }
345
346 // Parses a Token ([SH09] 4.2.10, [RFC8941] 4.2.6).
ReadToken()347 std::optional<Item> ReadToken() {
348 if (input_.empty() ||
349 !(absl::ascii_isalpha(input_.front()) || input_.front() == '*')) {
350 LogParseError("ReadToken", "ALPHA");
351 return std::nullopt;
352 }
353 size_t len = input_.find_first_not_of(version_ == kDraft09 ? kTokenChars09
354 : kTokenChars);
355 if (len == absl::string_view::npos) len = input_.size();
356 std::string token(input_.substr(0, len));
357 input_.remove_prefix(len);
358 return Item(std::move(token), Item::kTokenType);
359 }
360
361 // Parses a Number ([SH09] 4.2.8, [RFC8941] 4.2.4).
ReadNumber()362 std::optional<Item> ReadNumber() {
363 bool is_negative = ConsumeChar('-');
364 bool is_decimal = false;
365 size_t decimal_position = 0;
366 size_t i = 0;
367 for (; i < input_.size(); ++i) {
368 if (i > 0 && input_[i] == '.' && !is_decimal) {
369 is_decimal = true;
370 decimal_position = i;
371 continue;
372 }
373 if (!absl::ascii_isdigit(input_[i])) break;
374 }
375 if (i == 0) {
376 LogParseError("ReadNumber", "DIGIT");
377 return std::nullopt;
378 }
379 if (!is_decimal) {
380 // [RFC8941] restricts the range of integers further.
381 if (version_ == kFinal && i > 15) {
382 LogParseError("ReadNumber", "integer too long");
383 return std::nullopt;
384 }
385 } else {
386 if (version_ != kFinal && i > 16) {
387 LogParseError("ReadNumber", "float too long");
388 return std::nullopt;
389 }
390 if (version_ == kFinal && decimal_position > 12) {
391 LogParseError("ReadNumber", "decimal too long");
392 return std::nullopt;
393 }
394 if (i - decimal_position > (version_ == kFinal ? 4 : 7)) {
395 LogParseError("ReadNumber", "too many digits after decimal");
396 return std::nullopt;
397 }
398 if (i == decimal_position) {
399 LogParseError("ReadNumber", "no digits after decimal");
400 return std::nullopt;
401 }
402 }
403 std::string output_number_string(input_.substr(0, i));
404 input_.remove_prefix(i);
405
406 if (is_decimal) {
407 // Convert to a 64-bit double, and return if the conversion is
408 // successful.
409 double f;
410 if (!absl::SimpleAtod(output_number_string, &f)) return std::nullopt;
411 return Item(is_negative ? -f : f);
412 } else {
413 // Convert to a 64-bit signed integer, and return if the conversion is
414 // successful.
415 int64_t n;
416 if (!absl::SimpleAtoi(output_number_string, &n)) return std::nullopt;
417 QUICHE_CHECK(version_ != kFinal ||
418 (n <= kMaxInteger && n >= kMinInteger));
419 return Item(is_negative ? -n : n);
420 }
421 }
422
423 // Parses a String ([SH09] 4.2.9, [RFC8941] 4.2.5).
ReadString()424 std::optional<Item> ReadString() {
425 std::string s;
426 if (!ConsumeChar('"')) {
427 LogParseError("ReadString", "'\"'");
428 return std::nullopt;
429 }
430 while (!ConsumeChar('"')) {
431 size_t i = 0;
432 for (; i < input_.size(); ++i) {
433 if (!absl::ascii_isprint(input_[i])) {
434 QUICHE_DVLOG(1) << "ReadString: non printable-ASCII character";
435 return std::nullopt;
436 }
437 if (input_[i] == '"' || input_[i] == '\\') break;
438 }
439 if (i == input_.size()) {
440 QUICHE_DVLOG(1) << "ReadString: missing closing '\"'";
441 return std::nullopt;
442 }
443 s.append(std::string(input_.substr(0, i)));
444 input_.remove_prefix(i);
445 if (ConsumeChar('\\')) {
446 if (input_.empty()) {
447 QUICHE_DVLOG(1) << "ReadString: backslash at string end";
448 return std::nullopt;
449 }
450 if (input_[0] != '"' && input_[0] != '\\') {
451 QUICHE_DVLOG(1) << "ReadString: invalid escape";
452 return std::nullopt;
453 }
454 s.push_back(input_.front());
455 input_.remove_prefix(1);
456 }
457 }
458 return s;
459 }
460
461 // Parses a Byte Sequence ([SH09] 4.2.11, [RFC8941] 4.2.7).
ReadByteSequence()462 std::optional<Item> ReadByteSequence() {
463 char delimiter = (version_ == kDraft09 ? '*' : ':');
464 if (!ConsumeChar(delimiter)) {
465 LogParseError("ReadByteSequence", "delimiter");
466 return std::nullopt;
467 }
468 size_t len = input_.find(delimiter);
469 if (len == absl::string_view::npos) {
470 QUICHE_DVLOG(1) << "ReadByteSequence: missing closing delimiter";
471 return std::nullopt;
472 }
473 std::string base64(input_.substr(0, len));
474 // Append the necessary padding characters.
475 base64.resize((base64.size() + 3) / 4 * 4, '=');
476
477 std::string binary;
478 if (!absl::Base64Unescape(base64, &binary)) {
479 QUICHE_DVLOG(1) << "ReadByteSequence: failed to decode base64: "
480 << base64;
481 return std::nullopt;
482 }
483 input_.remove_prefix(len);
484 ConsumeChar(delimiter);
485 return Item(std::move(binary), Item::kByteSequenceType);
486 }
487
488 // Parses a Boolean ([RFC8941] 4.2.8).
489 // Note that this only parses ?0 and ?1 forms from SH version 10+, not the
490 // previous ?F and ?T, which were not needed by any consumers of SH version 9.
ReadBoolean()491 std::optional<Item> ReadBoolean() {
492 if (!ConsumeChar('?')) {
493 LogParseError("ReadBoolean", "'?'");
494 return std::nullopt;
495 }
496 if (ConsumeChar('1')) {
497 return Item(true);
498 }
499 if (ConsumeChar('0')) {
500 return Item(false);
501 }
502 return std::nullopt;
503 }
504
505 // There are several points in the specs where the handling of whitespace
506 // differs between Draft 9 and the final RFC. In those cases, Draft 9 allows
507 // any OWS character, while the RFC allows only a U+0020 SPACE.
SkipWhitespaces()508 void SkipWhitespaces() {
509 if (version_ == kDraft09) {
510 StripLeft(input_, kOWS);
511 } else {
512 StripLeft(input_, kSP);
513 }
514 }
515
SkipOWS()516 void SkipOWS() { StripLeft(input_, kOWS); }
517
ConsumeChar(char expected)518 bool ConsumeChar(char expected) {
519 if (!input_.empty() && input_.front() == expected) {
520 input_.remove_prefix(1);
521 return true;
522 }
523 return false;
524 }
525
LogParseError(const char * func,const char * expected)526 void LogParseError(const char* func, const char* expected) {
527 QUICHE_DVLOG(1) << func << ": " << expected << " expected, got "
528 << (input_.empty()
529 ? "EOS"
530 : "'" + std::string(input_.substr(0, 1)) + "'");
531 }
532
533 absl::string_view input_;
534 DraftVersion version_;
535 };
536
537 // Serializer for (a subset of) Structured Field Values for HTTP defined in
538 // [RFC8941]. Note that this serializer does not attempt to support [SH09].
539 class StructuredHeaderSerializer {
540 public:
541 StructuredHeaderSerializer() = default;
542 ~StructuredHeaderSerializer() = default;
543 StructuredHeaderSerializer(const StructuredHeaderSerializer&) = delete;
544 StructuredHeaderSerializer& operator=(const StructuredHeaderSerializer&) =
545 delete;
546
Output()547 std::string Output() { return output_.str(); }
548
549 // Serializes a List ([RFC8941] 4.1.1).
WriteList(const List & value)550 bool WriteList(const List& value) {
551 bool first = true;
552 for (const auto& member : value) {
553 if (!first) output_ << ", ";
554 if (!WriteParameterizedMember(member)) return false;
555 first = false;
556 }
557 return true;
558 }
559
560 // Serializes an Item ([RFC8941] 4.1.3).
WriteItem(const ParameterizedItem & value)561 bool WriteItem(const ParameterizedItem& value) {
562 if (!WriteBareItem(value.item)) return false;
563 return WriteParameters(value.params);
564 }
565
566 // Serializes an Item ([RFC8941] 4.1.3).
WriteBareItem(const Item & value)567 bool WriteBareItem(const Item& value) {
568 if (value.is_string()) {
569 // Serializes a String ([RFC8941] 4.1.6).
570 output_ << "\"";
571 for (const char& c : value.GetString()) {
572 if (!absl::ascii_isprint(c)) return false;
573 if (c == '\\' || c == '\"') output_ << "\\";
574 output_ << c;
575 }
576 output_ << "\"";
577 return true;
578 }
579 if (value.is_token()) {
580 // Serializes a Token ([RFC8941] 4.1.7).
581 if (!IsValidToken(value.GetString())) {
582 return false;
583 }
584 output_ << value.GetString();
585 return true;
586 }
587 if (value.is_byte_sequence()) {
588 // Serializes a Byte Sequence ([RFC8941] 4.1.8).
589 output_ << ":";
590 output_ << absl::Base64Escape(value.GetString());
591 output_ << ":";
592 return true;
593 }
594 if (value.is_integer()) {
595 // Serializes an Integer ([RFC8941] 4.1.4).
596 if (value.GetInteger() > kMaxInteger || value.GetInteger() < kMinInteger)
597 return false;
598 output_ << value.GetInteger();
599 return true;
600 }
601 if (value.is_decimal()) {
602 // Serializes a Decimal ([RFC8941] 4.1.5).
603 double decimal_value = value.GetDecimal();
604 if (!std::isfinite(decimal_value) ||
605 fabs(decimal_value) >= kTooLargeDecimal)
606 return false;
607
608 // Handle sign separately to simplify the rest of the formatting.
609 if (decimal_value < 0) output_ << "-";
610 // Unconditionally take absolute value to ensure that -0 is serialized as
611 // "0.0", with no negative sign, as required by spec. (4.1.5, step 2).
612 decimal_value = fabs(decimal_value);
613 double remainder = fmod(decimal_value, 0.002);
614 if (remainder == 0.0005) {
615 // Value ended in exactly 0.0005, 0.0025, 0.0045, etc. Round down.
616 decimal_value -= 0.0005;
617 } else if (remainder == 0.0015) {
618 // Value ended in exactly 0.0015, 0.0035, 0,0055, etc. Round up.
619 decimal_value += 0.0005;
620 } else {
621 // Standard rounding will work in all other cases.
622 decimal_value = round(decimal_value * 1000.0) / 1000.0;
623 }
624
625 // Use standard library functions to write the decimal, and then truncate
626 // if necessary to conform to spec.
627
628 // Maximum is 12 integer digits, one decimal point, three fractional
629 // digits, and a null terminator.
630 char buffer[17];
631 absl::SNPrintF(buffer, std::size(buffer), "%#.3f", decimal_value);
632
633 // Strip any trailing 0s after the decimal point, but leave at least one
634 // digit after it in all cases. (So 1.230 becomes 1.23, but 1.000 becomes
635 // 1.0.)
636 absl::string_view formatted_number(buffer);
637 auto truncate_index = formatted_number.find_last_not_of('0');
638 if (formatted_number[truncate_index] == '.') truncate_index++;
639 output_ << formatted_number.substr(0, truncate_index + 1);
640 return true;
641 }
642 if (value.is_boolean()) {
643 // Serializes a Boolean ([RFC8941] 4.1.9).
644 output_ << (value.GetBoolean() ? "?1" : "?0");
645 return true;
646 }
647 return false;
648 }
649
650 // Serializes a Dictionary ([RFC8941] 4.1.2).
WriteDictionary(const Dictionary & value)651 bool WriteDictionary(const Dictionary& value) {
652 bool first = true;
653 for (const auto& [dict_key, dict_value] : value) {
654 if (!first) output_ << ", ";
655 if (!WriteKey(dict_key)) return false;
656 first = false;
657 if (!dict_value.member_is_inner_list && !dict_value.member.empty() &&
658 dict_value.member.front().item.is_boolean() &&
659 dict_value.member.front().item.GetBoolean()) {
660 if (!WriteParameters(dict_value.params)) return false;
661 } else {
662 output_ << "=";
663 if (!WriteParameterizedMember(dict_value)) return false;
664 }
665 }
666 return true;
667 }
668
669 private:
WriteParameterizedMember(const ParameterizedMember & value)670 bool WriteParameterizedMember(const ParameterizedMember& value) {
671 // Serializes a parameterized member ([RFC8941] 4.1.1).
672 if (value.member_is_inner_list) {
673 if (!WriteInnerList(value.member)) return false;
674 } else {
675 QUICHE_CHECK_EQ(value.member.size(), 1UL);
676 if (!WriteItem(value.member[0])) return false;
677 }
678 return WriteParameters(value.params);
679 }
680
WriteInnerList(const std::vector<ParameterizedItem> & value)681 bool WriteInnerList(const std::vector<ParameterizedItem>& value) {
682 // Serializes an inner list ([RFC8941] 4.1.1.1).
683 output_ << "(";
684 bool first = true;
685 for (const ParameterizedItem& member : value) {
686 if (!first) output_ << " ";
687 if (!WriteItem(member)) return false;
688 first = false;
689 }
690 output_ << ")";
691 return true;
692 }
693
WriteParameters(const Parameters & value)694 bool WriteParameters(const Parameters& value) {
695 // Serializes a parameter list ([RFC8941] 4.1.1.2).
696 for (const auto& param_name_and_value : value) {
697 const std::string& param_name = param_name_and_value.first;
698 const Item& param_value = param_name_and_value.second;
699 output_ << ";";
700 if (!WriteKey(param_name)) return false;
701 if (!param_value.is_null()) {
702 if (param_value.is_boolean() && param_value.GetBoolean()) continue;
703 output_ << "=";
704 if (!WriteBareItem(param_value)) return false;
705 }
706 }
707 return true;
708 }
709
WriteKey(const std::string & value)710 bool WriteKey(const std::string& value) {
711 // Serializes a Key ([RFC8941] 4.1.1.3).
712 if (value.empty()) return false;
713 if (value.find_first_not_of(kKeyChars) != std::string::npos) return false;
714 if (!absl::ascii_islower(value[0]) && value[0] != '*') return false;
715 output_ << value;
716 return true;
717 }
718
719 std::ostringstream output_;
720 };
721
722 } // namespace
723
ItemTypeToString(Item::ItemType type)724 absl::string_view ItemTypeToString(Item::ItemType type) {
725 switch (type) {
726 case Item::kNullType:
727 return "null";
728 case Item::kIntegerType:
729 return "integer";
730 case Item::kDecimalType:
731 return "decimal";
732 case Item::kStringType:
733 return "string";
734 case Item::kTokenType:
735 return "token";
736 case Item::kByteSequenceType:
737 return "byte sequence";
738 case Item::kBooleanType:
739 return "boolean";
740 }
741 return "[invalid type]";
742 }
743
IsValidToken(absl::string_view str)744 bool IsValidToken(absl::string_view str) {
745 // Validate Token value per [RFC8941] 4.1.7.
746 if (str.empty() ||
747 !(absl::ascii_isalpha(str.front()) || str.front() == '*')) {
748 return false;
749 }
750 if (str.find_first_not_of(kTokenChars) != std::string::npos) {
751 return false;
752 }
753 return true;
754 }
755
Item()756 Item::Item() {}
Item(std::string value,Item::ItemType type)757 Item::Item(std::string value, Item::ItemType type) {
758 switch (type) {
759 case kStringType:
760 value_.emplace<kStringType>(std::move(value));
761 break;
762 case kTokenType:
763 value_.emplace<kTokenType>(std::move(value));
764 break;
765 case kByteSequenceType:
766 value_.emplace<kByteSequenceType>(std::move(value));
767 break;
768 default:
769 QUICHE_CHECK(false);
770 break;
771 }
772 }
Item(const char * value,Item::ItemType type)773 Item::Item(const char* value, Item::ItemType type)
774 : Item(std::string(value), type) {}
Item(int64_t value)775 Item::Item(int64_t value) : value_(value) {}
Item(double value)776 Item::Item(double value) : value_(value) {}
Item(bool value)777 Item::Item(bool value) : value_(value) {}
778
operator ==(const Item & lhs,const Item & rhs)779 bool operator==(const Item& lhs, const Item& rhs) {
780 return lhs.value_ == rhs.value_;
781 }
782
783 ParameterizedItem::ParameterizedItem() = default;
784 ParameterizedItem::ParameterizedItem(const ParameterizedItem&) = default;
785 ParameterizedItem& ParameterizedItem::operator=(const ParameterizedItem&) =
786 default;
ParameterizedItem(Item id,Parameters ps)787 ParameterizedItem::ParameterizedItem(Item id, Parameters ps)
788 : item(std::move(id)), params(std::move(ps)) {}
789 ParameterizedItem::~ParameterizedItem() = default;
790
791 ParameterizedMember::ParameterizedMember() = default;
792 ParameterizedMember::ParameterizedMember(const ParameterizedMember&) = default;
793 ParameterizedMember& ParameterizedMember::operator=(
794 const ParameterizedMember&) = default;
ParameterizedMember(std::vector<ParameterizedItem> id,bool member_is_inner_list,Parameters ps)795 ParameterizedMember::ParameterizedMember(std::vector<ParameterizedItem> id,
796 bool member_is_inner_list,
797 Parameters ps)
798 : member(std::move(id)),
799 member_is_inner_list(member_is_inner_list),
800 params(std::move(ps)) {}
ParameterizedMember(std::vector<ParameterizedItem> id,Parameters ps)801 ParameterizedMember::ParameterizedMember(std::vector<ParameterizedItem> id,
802 Parameters ps)
803 : member(std::move(id)),
804 member_is_inner_list(true),
805 params(std::move(ps)) {}
ParameterizedMember(Item id,Parameters ps)806 ParameterizedMember::ParameterizedMember(Item id, Parameters ps)
807 : member({{std::move(id), {}}}),
808 member_is_inner_list(false),
809 params(std::move(ps)) {}
810 ParameterizedMember::~ParameterizedMember() = default;
811
812 ParameterisedIdentifier::ParameterisedIdentifier() = default;
813 ParameterisedIdentifier::ParameterisedIdentifier(
814 const ParameterisedIdentifier&) = default;
815 ParameterisedIdentifier& ParameterisedIdentifier::operator=(
816 const ParameterisedIdentifier&) = default;
ParameterisedIdentifier(Item id,Parameters ps)817 ParameterisedIdentifier::ParameterisedIdentifier(Item id, Parameters ps)
818 : identifier(std::move(id)), params(std::move(ps)) {}
819 ParameterisedIdentifier::~ParameterisedIdentifier() = default;
820
821 Dictionary::Dictionary() = default;
822 Dictionary::Dictionary(const Dictionary&) = default;
Dictionary(std::vector<DictionaryMember> members)823 Dictionary::Dictionary(std::vector<DictionaryMember> members)
824 : members_(std::move(members)) {}
825 Dictionary::~Dictionary() = default;
begin()826 std::vector<DictionaryMember>::iterator Dictionary::begin() {
827 return members_.begin();
828 }
begin() const829 std::vector<DictionaryMember>::const_iterator Dictionary::begin() const {
830 return members_.begin();
831 }
end()832 std::vector<DictionaryMember>::iterator Dictionary::end() {
833 return members_.end();
834 }
end() const835 std::vector<DictionaryMember>::const_iterator Dictionary::end() const {
836 return members_.end();
837 }
operator [](std::size_t idx)838 ParameterizedMember& Dictionary::operator[](std::size_t idx) {
839 return members_[idx].second;
840 }
operator [](std::size_t idx) const841 const ParameterizedMember& Dictionary::operator[](std::size_t idx) const {
842 return members_[idx].second;
843 }
at(std::size_t idx)844 ParameterizedMember& Dictionary::at(std::size_t idx) { return (*this)[idx]; }
at(std::size_t idx) const845 const ParameterizedMember& Dictionary::at(std::size_t idx) const {
846 return (*this)[idx];
847 }
operator [](absl::string_view key)848 ParameterizedMember& Dictionary::operator[](absl::string_view key) {
849 auto it = absl::c_find_if(
850 members_, [key](const auto& member) { return member.first == key; });
851 if (it != members_.end()) return it->second;
852 members_.push_back({std::string(key), ParameterizedMember()});
853 return members_.back().second;
854 }
at(absl::string_view key)855 ParameterizedMember& Dictionary::at(absl::string_view key) {
856 auto it = absl::c_find_if(
857 members_, [key](const auto& member) { return member.first == key; });
858 QUICHE_CHECK(it != members_.end()) << "Provided key not found in dictionary";
859 return it->second;
860 }
at(absl::string_view key) const861 const ParameterizedMember& Dictionary::at(absl::string_view key) const {
862 auto it = absl::c_find_if(
863 members_, [key](const auto& member) { return member.first == key; });
864 QUICHE_CHECK(it != members_.end()) << "Provided key not found in dictionary";
865 return it->second;
866 }
empty() const867 bool Dictionary::empty() const { return members_.empty(); }
size() const868 std::size_t Dictionary::size() const { return members_.size(); }
contains(absl::string_view key) const869 bool Dictionary::contains(absl::string_view key) const {
870 for (auto& member : members_) {
871 if (member.first == key) return true;
872 }
873 return false;
874 }
875
ParseItem(absl::string_view str)876 std::optional<ParameterizedItem> ParseItem(absl::string_view str) {
877 StructuredHeaderParser parser(str, StructuredHeaderParser::kFinal);
878 std::optional<ParameterizedItem> item = parser.ReadItem();
879 if (item && parser.FinishParsing()) return item;
880 return std::nullopt;
881 }
882
ParseBareItem(absl::string_view str)883 std::optional<Item> ParseBareItem(absl::string_view str) {
884 StructuredHeaderParser parser(str, StructuredHeaderParser::kFinal);
885 std::optional<Item> item = parser.ReadBareItem();
886 if (item && parser.FinishParsing()) return item;
887 return std::nullopt;
888 }
889
ParseParameterisedList(absl::string_view str)890 std::optional<ParameterisedList> ParseParameterisedList(absl::string_view str) {
891 StructuredHeaderParser parser(str, StructuredHeaderParser::kDraft09);
892 std::optional<ParameterisedList> param_list = parser.ReadParameterisedList();
893 if (param_list && parser.FinishParsing()) return param_list;
894 return std::nullopt;
895 }
896
ParseListOfLists(absl::string_view str)897 std::optional<ListOfLists> ParseListOfLists(absl::string_view str) {
898 StructuredHeaderParser parser(str, StructuredHeaderParser::kDraft09);
899 std::optional<ListOfLists> list_of_lists = parser.ReadListOfLists();
900 if (list_of_lists && parser.FinishParsing()) return list_of_lists;
901 return std::nullopt;
902 }
903
ParseList(absl::string_view str)904 std::optional<List> ParseList(absl::string_view str) {
905 StructuredHeaderParser parser(str, StructuredHeaderParser::kFinal);
906 std::optional<List> list = parser.ReadList();
907 if (list && parser.FinishParsing()) return list;
908 return std::nullopt;
909 }
910
ParseDictionary(absl::string_view str)911 std::optional<Dictionary> ParseDictionary(absl::string_view str) {
912 StructuredHeaderParser parser(str, StructuredHeaderParser::kFinal);
913 std::optional<Dictionary> dictionary = parser.ReadDictionary();
914 if (dictionary && parser.FinishParsing()) return dictionary;
915 return std::nullopt;
916 }
917
SerializeItem(const Item & value)918 std::optional<std::string> SerializeItem(const Item& value) {
919 StructuredHeaderSerializer s;
920 if (s.WriteItem(ParameterizedItem(value, {}))) return s.Output();
921 return std::nullopt;
922 }
923
SerializeItem(const ParameterizedItem & value)924 std::optional<std::string> SerializeItem(const ParameterizedItem& value) {
925 StructuredHeaderSerializer s;
926 if (s.WriteItem(value)) return s.Output();
927 return std::nullopt;
928 }
929
SerializeList(const List & value)930 std::optional<std::string> SerializeList(const List& value) {
931 StructuredHeaderSerializer s;
932 if (s.WriteList(value)) return s.Output();
933 return std::nullopt;
934 }
935
SerializeDictionary(const Dictionary & value)936 std::optional<std::string> SerializeDictionary(const Dictionary& value) {
937 StructuredHeaderSerializer s;
938 if (s.WriteDictionary(value)) return s.Output();
939 return std::nullopt;
940 }
941
942 } // namespace structured_headers
943 } // namespace quiche
944