common/web_package/web_package_request_matcher.cc

// Copyright 2019 The Chromium Authors. All rights reserved.
// 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 <utility>

#include "base/containers/span.h"
#include "base/numerics/checked_math.h"
#include "base/optional.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,
      base::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 base::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->begin(),
                                         request_header_value->end(), ',');
    while (values.GetNext()) {
      net::HttpUtil::NameValuePairsIterator name_value_pairs(
          values.value_begin(), values.value_end(), ';',
          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::LowerCaseEqualsASCII(name_value_pairs.name_piece(), "q")) {
          if (auto value = GetQValue(name_value_pairs.value()))
            item.weight = *value;
        } else {
          // Parameters except for "q" are included in the output.
          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:
  base::Optional<double> GetQValue(const std::string& 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 base::nullopt;
    if (val < 0.0 || val > 1.0)
      return base::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,
      base::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,
      base::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 (!std::any_of(
            preferred_codings.begin(), preferred_codings.end(),
            [](const WeightedValue& p) { return p.value == kIdentity; })) {
      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,
      base::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::copy(available_values.begin(), available_values.end(),
                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
base::Optional<std::vector<std::pair<std::string, std::vector<std::string>>>>
ParseVariants(const base::StringPiece& 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.
  base::Optional<net::structured_headers::ListOfLists> parsed =
      net::structured_headers::ParseListOfLists(str);
  if (!parsed)
    return base::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 base::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 base::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
base::Optional<std::vector<std::vector<std::string>>> ParseVariantKey(
    const base::StringPiece& 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.
  base::Optional<net::structured_headers::ListOfLists> parsed =
      net::structured_headers::ParseListOfLists(str);
  if (!parsed)
    return base::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 base::nullopt;
    for (const net::structured_headers::Item& item : inner_list) {
      if (!item.is_string() && !item.is_token())
        return base::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
base::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::find(sorted_variants[i].begin(), sorted_variants[i].end(),
                           variant_key[i]);
    if (found == sorted_variants[i].end())
      return base::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);
}

base::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]
      base::Optional<std::string> request_value;
      std::string header_value;
      if (request_headers.GetHeader(field_name, &header_value))
        request_value = header_value;
      // 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) {
      auto found = std::find(sorted_variants[i].begin(),
                             sorted_variants[i].end(), vk[i]);
      if (found == sorted_variants[i].end())
        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
base::Optional<size_t> WebPackageRequestMatcher::FindBestMatchingIndex(
    const net::HttpRequestHeaders& request_headers,
    const std::string& variants) {
  auto parsed_variants = ParseVariants(variants);
  if (!parsed_variants)
    return base::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 base::nullopt;
    base::Optional<std::string> request_value;
    std::string header_value;
    if (request_headers.GetHeader(field_name, &header_value))
      request_value = header_value;

    std::vector<std::string> sorted_values =
        negotiation_algorithm->run(variant_axis.second, request_value);
    if (sorted_values.empty())
      return base::nullopt;
    auto it = std::find(variant_axis.second.begin(), variant_axis.second.end(),
                        sorted_values.front());
    if (it == variant_axis.second.end())
      return base::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 base::nullopt;
    }
    if (!base::CheckAdd(best_match_index, best_value_index)
             .AssignIfValid(&best_match_index)) {
      return base::nullopt;
    }
  }
  return best_match_index;
}

}  // namespace blink