1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651
|
// Copyright 2019 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "third_party/blink/public/common/web_package/web_package_request_matcher.h"
#include <algorithm>
#include <limits>
#include <memory>
#include <optional>
#include <string_view>
#include <utility>
#include "base/containers/contains.h"
#include "base/containers/span.h"
#include "base/numerics/checked_math.h"
#include "base/strings/strcat.h"
#include "base/strings/string_number_conversions.h"
#include "base/strings/string_util.h"
#include "net/base/mime_util.h"
#include "net/http/http_request_headers.h"
#include "net/http/http_util.h"
#include "net/http/structured_headers.h"
#include "third_party/blink/public/common/web_package/signed_exchange_consts.h"
namespace blink {
namespace {
constexpr char kIdentity[] = "identity";
class ContentNegotiationAlgorithm {
public:
virtual ~ContentNegotiationAlgorithm() = default;
// Returns items from |available_values| that satisfy the request, in
// preference order. Each subclass should implement the algorithm defined by
// content negotiation mechanism.
virtual std::vector<std::string> run(
base::span<const std::string> available_values,
std::optional<std::string> request_header_value) = 0;
protected:
struct WeightedValue {
std::string value;
double weight;
bool operator<(const WeightedValue& other) const {
return weight > other.weight; // Descending order
}
};
// Parses an Accept (Section 5.3.2 of [RFC7231]), an Accept-Encoding (Section
// 5.3.3 of [RFC7231]), or an Accept-Language (Section 5.3.5 of [RFC7231]).
// Returns items sorted by descending order of their weight, omitting items
// with weight of 0.
std::vector<WeightedValue> ParseRequestHeaderValue(
const std::optional<std::string>& request_header_value) {
std::vector<WeightedValue> items;
if (!request_header_value)
return items;
// Value can start with '*', so it cannot be parsed by
// net::structured_headers::ParseParameterisedList.
net::HttpUtil::ValuesIterator values(*request_header_value,
/*delimiter=*/',');
while (values.GetNext()) {
net::HttpUtil::NameValuePairsIterator name_value_pairs(
values.value(), /*delimiter=*/';',
net::HttpUtil::NameValuePairsIterator::Values::NOT_REQUIRED,
net::HttpUtil::NameValuePairsIterator::Quotes::STRICT_QUOTES);
if (!name_value_pairs.GetNext())
continue;
WeightedValue item;
item.value = name_value_pairs.name();
item.weight = 1.0;
while (name_value_pairs.GetNext()) {
if (base::EqualsCaseInsensitiveASCII(name_value_pairs.name(), "q")) {
if (auto value = GetQValue(name_value_pairs.value())) {
item.weight = *value;
}
} else {
// Parameters except for "q" are included in the output.
base::StrAppend(&item.value, {";", name_value_pairs.name(), "=",
name_value_pairs.value()});
}
}
if (item.weight != 0.0)
items.push_back(std::move(item));
}
std::stable_sort(items.begin(), items.end());
return items;
}
private:
std::optional<double> GetQValue(std::string_view str) {
// TODO(ksakamoto): Validate the syntax per Section 5.3.1 of [RFC7231],
// by factoring out the logic in HttpUtil::ParseAcceptEncoding().
double val;
if (!base::StringToDouble(str, &val))
return std::nullopt;
if (val < 0.0 || val > 1.0)
return std::nullopt;
return val;
}
};
// https://httpwg.org/http-extensions/draft-ietf-httpbis-variants.html#content-type
class ContentTypeNegotiation final : public ContentNegotiationAlgorithm {
std::vector<std::string> run(
base::span<const std::string> available_values,
std::optional<std::string> request_header_value) override {
// Step 1. Let preferred-available be an empty list. [spec text]
std::vector<std::string> preferred_available;
// Step 2. Let preferred-types be a list of the types in the request-value
// (or the empty list if request-value is null), ordered by their weight,
// highest to lowest, as per Section 5.3.2 of [RFC7231] (omitting any coding
// with a weight of 0). If a type lacks an explicit weight, an
// implementation MAY assign one.
std::vector<WeightedValue> preferred_types =
ParseRequestHeaderValue(request_header_value);
// Step 3. For each preferred-type in preferred-types: [spec text]
for (const WeightedValue& preferred_type : preferred_types) {
// 3.1. If any member of available-values matches preferred-type, using
// the media-range matching mechanism specified in Section 5.3.2 of
// [RFC7231] (which is case-insensitive), append those members of
// available-values to preferred-available (preserving the precedence
// order implied by the media ranges' specificity).
for (const std::string& available : available_values) {
if (net::MatchesMimeType(preferred_type.value, available))
preferred_available.push_back(available);
}
}
// Step 4. If preferred-available is empty, append the first member of
// available-values to preferred-available. This makes the first
// available-value the default when none of the client's preferences are
// available. [spec text]
if (preferred_available.empty() && !available_values.empty())
preferred_available.push_back(available_values[0]);
// Step 5. Return preferred-available. [spec text]
return preferred_available;
}
};
// https://httpwg.org/http-extensions/draft-ietf-httpbis-variants.html#content-encoding
class AcceptEncodingNegotiation final : public ContentNegotiationAlgorithm {
std::vector<std::string> run(
base::span<const std::string> available_values,
std::optional<std::string> request_header_value) override {
// Step 1. Let preferred-available be an empty list. [spec text]
std::vector<std::string> preferred_available;
// Step 2. Let preferred-codings be a list of the codings in the
// request-value (or the empty list if request-value is null), ordered by
// their weight, highest to lowest, as per Section 5.3.1 of [RFC7231]
// (omitting any coding with a weight of 0). If a coding lacks an explicit
// weight, an implementation MAY assign one. [spec text]
std::vector<WeightedValue> preferred_codings =
ParseRequestHeaderValue(request_header_value);
// Step 3. If "identity" is not a member of preferred-codings, append
// "identity". [spec text]
if (!base::Contains(preferred_codings, kIdentity, &WeightedValue::value)) {
preferred_codings.push_back({kIdentity, 0.0});
}
// Step 4. Append "identity" to available-values. [spec text]
// Instead, we explicitly check "identity" in Step 5.1 below.
// Step 5. For each preferred-coding in preferred-codings: [spec text]
for (const WeightedValue& preferred_coding : preferred_codings) {
// Step 5.1. If there is a case-insensitive, character-for-character match
// for preferred-coding in available-values, append that member of
// available-values to preferred-available. [spec text]
if (preferred_coding.value == kIdentity) {
preferred_available.push_back(kIdentity);
continue;
}
for (const std::string& available : available_values) {
if (base::EqualsCaseInsensitiveASCII(preferred_coding.value,
available)) {
preferred_available.push_back(available);
break;
}
}
}
// Step 6. Return preferred-available. [spec text]
return preferred_available;
}
};
// https://httpwg.org/http-extensions/draft-ietf-httpbis-variants.html#content-language
class AcceptLanguageNegotiation final : public ContentNegotiationAlgorithm {
public:
std::vector<std::string> run(
base::span<const std::string> available_values,
std::optional<std::string> request_header_value) override {
// Step 1. Let preferred-available be an empty list. [spec text]
std::vector<std::string> preferred_available;
// Step 2. Let preferred-langs be a list of the language-ranges in the
// request-value (or the empty list if request-value is null), ordered by
// their weight, highest to lowest, as per Section 5.3.1 of [RFC7231]
// (omitting any language-range with a weight of 0). If a language-range
// lacks a weight, an implementation MAY assign one. [spec text]
std::vector<WeightedValue> preferred_langs =
ParseRequestHeaderValue(request_header_value);
// Step 3. For each preferred-lang in preferred-langs: [spec text]
for (const WeightedValue& preferred_lang : preferred_langs) {
// Step 3.1. If any member of available-values matches preferred-lang,
// using either the Basic or Extended Filtering scheme defined in
// Section 3.3 of [RFC4647], append those members of available-values to
// preferred-available (preserving their order). [spec text]
AppendMatchedLanguages(available_values, preferred_lang.value,
&preferred_available);
}
// Step 4. If preferred-available is empty, append the first member of
// available-values to preferred-available. This makes the first
// available-value the default when none of the client's preferences are
// available. [spec text]
if (preferred_available.empty() && !available_values.empty())
preferred_available.push_back(available_values[0]);
// Step 5. Return preferred-available. [spec text]
return preferred_available;
}
private:
// Performs the Basic Filtering (Section 3.3.1 of [RFC4647]).
void AppendMatchedLanguages(base::span<const std::string> available_values,
const std::string& preferred_lang,
std::vector<std::string>* output) {
if (preferred_lang == "*") {
std::ranges::copy(available_values, std::back_inserter(*output));
return;
}
const std::string prefix = preferred_lang + '-';
for (const std::string& available : available_values) {
if (base::EqualsCaseInsensitiveASCII(preferred_lang, available) ||
base::StartsWith(available, prefix,
base::CompareCase::INSENSITIVE_ASCII)) {
output->push_back(available);
}
}
}
};
std::unique_ptr<ContentNegotiationAlgorithm> GetContentNegotiationAlgorithm(
const std::string& field_name) {
if (field_name == "accept")
return std::make_unique<ContentTypeNegotiation>();
if (field_name == "accept-encoding")
return std::make_unique<AcceptEncodingNegotiation>();
if (field_name == "accept-language")
return std::make_unique<AcceptLanguageNegotiation>();
return nullptr;
}
// https://tools.ietf.org/id/draft-ietf-httpbis-variants-04.html#variants
std::optional<std::vector<std::pair<std::string, std::vector<std::string>>>>
ParseVariants(const std::string_view& str) {
// Compatibility note: Draft 4 of Variants
// (https://tools.ietf.org/id/draft-ietf-httpbis-variants-04.html#variants)
// uses a custom format for the Variants-04 header, which this method attempts
// to parse as a Structured Headers list-of-lists. This means that quoted
// string values as well as unquoted tokens will be accepted by this parser,
// which is strictly more lenient than the actual draft spec. Draft 5
// (https://tools.ietf.org/id/draft-ietf-httpbis-variants-05.html#variants,
// which we don't actually support yet) uses a Structured-Headers-Draft-9
// list-of-lists syntax for the Variants-05 header, and explicitly allows both
// strings and tokens.
// TODO(iclelland): As of October 2019, the latest editor's draft of Variants
// (https://httpwg.org/http-extensions/draft-ietf-httpbis-variants.html#variants)
// specifies a Structured-Headers-Draft-13 dictionary for the Variants header.
// Once the specs are updated, also parse the new Variants dictionary header
// as well. The same data structure should be returned.
std::optional<net::structured_headers::ListOfLists> parsed =
net::structured_headers::ParseListOfLists(str);
if (!parsed)
return std::nullopt;
std::vector<std::pair<std::string, std::vector<std::string>>> variants;
// Each inner-list in the Variants header field value is parsed into a
// variant-axis. The first list-member of the inner-list is interpreted as
// the field-name, and the remaining list-members are the available-values.
// [spec text]
for (const auto& inner_list : *parsed) {
auto it = inner_list.begin();
// Any list-member that is a token is interpreted as a string containing the
// same characters.
// [spec text]
if (!it->is_string() && !it->is_token())
return std::nullopt;
std::string field_name = it->GetString();
std::vector<std::string> available_values;
available_values.reserve(inner_list.size() - 1);
for (++it; it != inner_list.end(); ++it) {
// Any list-member that is a token is interpreted as a string containing
// the same characters.
// [spec text]
if (!it->is_string() && !it->is_token())
return std::nullopt;
available_values.push_back(it->GetString());
}
variants.push_back(std::make_pair(field_name, available_values));
}
return variants;
}
// https://tools.ietf.org/id/draft-ietf-httpbis-variants-04.html#variant-key
std::optional<std::vector<std::vector<std::string>>> ParseVariantKey(
const std::string_view& str,
size_t num_variant_axes) {
// Compatibility note: Draft 4 of Variants
// (https://tools.ietf.org/id/draft-ietf-httpbis-variants-04.html#variant-key)
// uses a custom format for the Variant-Key-04 header, which this method
// attempts to parse as a Structured Headers list-of-lists. This means that
// quoted string values as well as unquoted tokens will be accepted by this
// parser, which is strictly more lenient than the actual draft spec. Draft 5
// (https://tools.ietf.org/id/draft-ietf-httpbis-variants-05.html#variant-key,
// which we don't actually support yet) uses a Structured-Headers-Draft-9
// list-of-lists syntax for the Variant-Key-05 header, and explicitly allows
// both strings and tokens.
// TODO(iclelland): Once the specs are updated, also parse the new
// Variants-Key header as well. The same data structure should be returned.
std::optional<net::structured_headers::ListOfLists> parsed =
net::structured_headers::ParseListOfLists(str);
if (!parsed)
return std::nullopt;
std::vector<std::vector<std::string>> variant_keys;
variant_keys.reserve(parsed->size());
// Each inner-list MUST have the same number of list-members as there are
// variant-axes in the representation's Variants header field. Additionally,
// every element of each inner-list must be a string. If not, the client MUST
// treat the representation as having no Variant-Key header field.
// [spec text]
for (const auto& inner_list : *parsed) {
std::vector<std::string> list_members;
list_members.reserve(inner_list.size());
if (inner_list.size() != num_variant_axes)
return std::nullopt;
for (const net::structured_headers::Item& item : inner_list) {
if (!item.is_string() && !item.is_token())
return std::nullopt;
list_members.push_back(item.GetString());
}
variant_keys.push_back(list_members);
}
return variant_keys;
}
// Returns the index of matching entry in Possible Keys [1] which is the cross
// product of |sorted_variants|. If there is no matching entry returns nullopt.
// Example:
// sorted_variants: [["image/webp","image/jpg"], ["en", "fr", "ja"]]
// variant_key: ["image/jpg", "fr"]
// Possible Keys list for this sorted_variants:
// [["image/webp", "en"], ["image/webp", "fr"], ["image/webp", "ja"],
// ["image/jpg", "en"], ["image/jpg", "fr"], ["image/jpg", "ja"]]
// Result: 4
// [1] https://httpwg.org/http-extensions/draft-ietf-httpbis-variants.html#find
std::optional<size_t> GetPossibleKeysIndex(
const std::vector<std::vector<std::string>>& sorted_variants,
const std::vector<std::string>& variant_key) {
DCHECK_EQ(variant_key.size(), sorted_variants.size());
size_t index = 0;
for (size_t i = 0; i < sorted_variants.size(); ++i) {
auto found = std::ranges::find(sorted_variants[i], variant_key[i]);
if (found == sorted_variants[i].end())
return std::nullopt;
index = index * sorted_variants[i].size() +
(found - sorted_variants[i].begin());
}
return index;
}
} // namespace
WebPackageRequestMatcher::WebPackageRequestMatcher(
const net::HttpRequestHeaders& request_headers,
const std::string& accept_langs)
: request_headers_(request_headers) {
request_headers_.SetHeaderIfMissing(
net::HttpRequestHeaders::kAcceptLanguage,
net::HttpUtil::GenerateAcceptLanguageHeader(
net::HttpUtil::ExpandLanguageList(accept_langs)));
// We accept only "mi-sha256-03" as the inner content encoding.
// TODO(ksakamoto): Revisit once
// https://github.com/WICG/webpackage/issues/390 is settled.
request_headers_.SetHeader(net::HttpRequestHeaders::kAcceptEncoding,
"mi-sha256-03");
}
bool WebPackageRequestMatcher::MatchRequest(
const HeaderMap& response_headers) const {
return MatchRequest(request_headers_, response_headers);
}
std::vector<std::string>::const_iterator
WebPackageRequestMatcher::FindBestMatchingVariantKey(
const std::string& variants,
const std::vector<std::string>& variant_key_list) const {
return FindBestMatchingVariantKey(request_headers_, variants,
variant_key_list);
}
std::optional<size_t> WebPackageRequestMatcher::FindBestMatchingIndex(
const std::string& variants) const {
return FindBestMatchingIndex(request_headers_, variants);
}
// Implements "Cache Behaviour" [1] when "stored-responses" is a singleton list
// containing a response that has "Variants" header whose value is |variants|.
// [1] https://httpwg.org/http-extensions/draft-ietf-httpbis-variants.html#cache
std::vector<std::vector<std::string>> WebPackageRequestMatcher::CacheBehavior(
const std::vector<std::pair<std::string, std::vector<std::string>>>&
variants,
const net::HttpRequestHeaders& request_headers) {
// Step 1. If stored-responses is empty, return an empty list. [spec text]
// The size of stored-responses is always 1.
// Step 2. Order stored-responses by the "Date" header field, most recent to
// least recent. [spec text]
// This is no-op because stored-responses is a single-element list.
// Step 3. Let sorted-variants be an empty list. [spec text]
std::vector<std::vector<std::string>> sorted_variants;
// Step 4. If the freshest member of stored-responses (as per [RFC7234],
// Section 4.2) has one or more "Variants" header field(s) that successfully
// parse according to Section 2: [spec text]
// Step 4.1. Select one member of stored-responses with a "Variants" header
// field-value(s) that successfully parses according to Section 2 and let
// variants-header be this parsed value. This SHOULD be the most recent
// response, but MAY be from an older one as long as it is still fresh.
// [spec text]
// |variants| is the parsed "Variants" header field value.
// Step 4.2. For each variant-axis in variants-header: [spec text]
for (const auto& variant_axis : variants) {
// Step 4.2.1. If variant-axis' field-name corresponds to the request header
// field identified by a content negotiation mechanism that the
// implementation supports: [spec text]
std::string field_name = base::ToLowerASCII(variant_axis.first);
std::unique_ptr<ContentNegotiationAlgorithm> negotiation_algorithm =
GetContentNegotiationAlgorithm(field_name);
if (negotiation_algorithm) {
// Step 4.2.1.1. Let request-value be the field-value associated with
// field-name in incoming-request (after being combined as allowed by
// Section 3.2.2 of [RFC7230]), or null if field-name is not in
// incoming-request. [spec text]
std::optional<std::string> request_value =
request_headers.GetHeader(field_name);
// Step 4.2.1.2. Let sorted-values be the result of running the algorithm
// defined by the content negotiation mechanism with request-value and
// variant-axis' available-values. [spec text]
std::vector<std::string> sorted_values =
negotiation_algorithm->run(variant_axis.second, request_value);
// Step 4.2.1.3. Append sorted-values to sorted-variants. [spec text]
sorted_variants.push_back(std::move(sorted_values));
}
}
// At this point, sorted-variants will be a list of lists, each member of the
// top-level list corresponding to a variant-axis in the Variants header
// field-value, containing zero or more items indicating available-values
// that are acceptable to the client, in order of preference, greatest to
// least. [spec text]
// Step 5. Return result of running Compute Possible Keys (Section 4.1) on
// sorted-variants, an empty list and an empty list. [spec text]
// Instead of computing the cross product of sorted_variants, this
// implementation just returns sorted_variants.
return sorted_variants;
}
// Implements step 3- of
// https://wicg.github.io/webpackage/loading.html#request-matching
bool WebPackageRequestMatcher::MatchRequest(
const net::HttpRequestHeaders& request_headers,
const HeaderMap& response_headers) {
auto variants_found =
response_headers.find(blink::kSignedExchangeVariantsHeader);
auto variant_key_found =
response_headers.find(blink::kSignedExchangeVariantKeyHeader);
// Step 3. If storedExchange's response's header list contains:
// - Neither a `Variants` nor a `Variant-Key` header
// Return "match". [spec text]
if (variants_found == response_headers.end() &&
variant_key_found == response_headers.end()) {
return true;
}
// - A `Variant-Key` header but no `Variants` header
// Return "mismatch". [spec text]
if (variants_found == response_headers.end())
return false;
// - A `Variants` header but no `Variant-Key` header
// Return "mismatch". [spec text]
if (variant_key_found == response_headers.end())
return false;
// - Both a `Variants` and a `Variant-Key` header
// Proceed to the following steps. [spec text]
// Step 4. If getting `Variants` from storedExchange's response's header list
// returns a value that fails to parse according to the instructions for the
// Variants Header Field, return "mismatch". [spec text]
auto parsed_variants = ParseVariants(variants_found->second);
if (!parsed_variants)
return false;
// Step 5. Let acceptableVariantKeys be the result of running the Variants
// Cache Behavior on an incoming-request of browserRequest and
// stored-responses of a list containing storedExchange's response.
// [spec text]
std::vector<std::vector<std::string>> sorted_variants =
CacheBehavior(*parsed_variants, request_headers);
// This happens when `Variant` has unknown field names. In such cases,
// this algorithm never returns "match", so we do an early return.
if (sorted_variants.size() != parsed_variants->size())
return false;
// Step 6. Let variantKeys be the result of getting `Variant-Key` from
// storedExchange's response's header list, and parsing it into a list of
// lists as described in Variant-Key Header Field. [spec text]
auto parsed_variant_key =
ParseVariantKey(variant_key_found->second, parsed_variants->size());
// Step 7. If parsing variantKeys failed, return "mismatch". [spec text]
if (!parsed_variant_key)
return false;
// Step 8. If the intersection of acceptableVariantKeys and variantKeys is
// empty, return "mismatch". [spec text]
// Step 9. Return "match". [spec text]
// AcceptableVariantKeys is the cross product of sorted_variants. Instead of
// computing AcceptableVariantKeys and taking the intersection of it and
// variantKeys, we check its equivalent, i.e.: Return "match" if there is a vk
// in variantKeys such that for all i, vk[i] is in sorted_variants[i].
for (const std::vector<std::string>& vk : *parsed_variant_key) {
DCHECK_EQ(vk.size(), sorted_variants.size());
size_t i = 0;
for (; i < sorted_variants.size(); ++i) {
if (!base::Contains(sorted_variants[i], vk[i]))
break;
}
if (i == sorted_variants.size())
return true;
}
// Otherwise return "mismatch".
return false;
}
// static
std::vector<std::string>::const_iterator
WebPackageRequestMatcher::FindBestMatchingVariantKey(
const net::HttpRequestHeaders& request_headers,
const std::string& variants,
const std::vector<std::string>& variant_keys_list) {
auto parsed_variants = ParseVariants(variants);
if (!parsed_variants)
return variant_keys_list.end();
std::vector<std::vector<std::string>> sorted_variants =
CacheBehavior(*parsed_variants, request_headers);
// This happens when `Variant` has unknown field names. In such cases,
// this algorithm never returns "match", so we do an early return.
if (sorted_variants.size() != parsed_variants->size())
return variant_keys_list.end();
// Check that the combination count of Possible Keys doesn't overflow.
// Currently we have only three ContentNegotiationAlgorithms, so it is
// impossible to overflow. But we check to protect for future extension.
size_t possible_keys_count = 1;
for (const auto& key : sorted_variants) {
if (!base::CheckMul(possible_keys_count, key.size())
.AssignIfValid(&possible_keys_count)) {
return variant_keys_list.end();
}
}
size_t minimum_index = std::numeric_limits<size_t>::max();
auto found_variant_key = variant_keys_list.end();
for (auto variant_keys_list_it = variant_keys_list.begin();
variant_keys_list_it < variant_keys_list.end(); ++variant_keys_list_it) {
auto parsed_variant_keys =
ParseVariantKey(*variant_keys_list_it, parsed_variants->size());
if (!parsed_variant_keys)
continue;
for (const std::vector<std::string>& variant_key : *parsed_variant_keys) {
auto maching_index = GetPossibleKeysIndex(sorted_variants, variant_key);
if (maching_index.has_value() && *maching_index < minimum_index) {
minimum_index = *maching_index;
found_variant_key = variant_keys_list_it;
}
}
}
return found_variant_key;
}
// static
std::optional<size_t> WebPackageRequestMatcher::FindBestMatchingIndex(
const net::HttpRequestHeaders& request_headers,
const std::string& variants) {
auto parsed_variants = ParseVariants(variants);
if (!parsed_variants)
return std::nullopt;
size_t best_match_index = 0;
for (const auto& variant_axis : *parsed_variants) {
const std::string field_name = base::ToLowerASCII(variant_axis.first);
std::unique_ptr<ContentNegotiationAlgorithm> negotiation_algorithm =
GetContentNegotiationAlgorithm(field_name);
if (!negotiation_algorithm)
return std::nullopt;
std::optional<std::string> request_value =
request_headers.GetHeader(field_name);
std::vector<std::string> sorted_values =
negotiation_algorithm->run(variant_axis.second, request_value);
if (sorted_values.empty())
return std::nullopt;
auto it = std::ranges::find(variant_axis.second, sorted_values.front());
if (it == variant_axis.second.end())
return std::nullopt;
size_t best_value_index = it - variant_axis.second.begin();
if (!base::CheckMul(best_match_index, variant_axis.second.size())
.AssignIfValid(&best_match_index)) {
return std::nullopt;
}
if (!base::CheckAdd(best_match_index, best_value_index)
.AssignIfValid(&best_match_index)) {
return std::nullopt;
}
}
return best_match_index;
}
} // namespace blink
|