components/cbor/reader.cc

// Copyright 2017 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// Crubit C++ FFI integration notes:
// TODO(crbug.com/262737383): Update `ConvertRustMapKeyToCpp` and
// `ConvertRustValueToCpp` to use Crubit's auto-generated C++ pattern matching
// and accessor methods for non-repr(C) ADT enums (like `Value` and `MapKey`)
// once available, completely replacing the manual `.tag` inspection switch
// statements.
// TODO(crbug.com/259749095): Call `cbor::rust::parse_with_config` directly
// and remove `ParseResult` once Crubit supports returning generic `Result`
// tuples (`Result<(Value, usize), Error>`) directly across FFI.
// TODO(crbug.com/535682335): Remove `#if BUILDFLAG(USE_CBOR_RUST)` macros
// throughout this file and unconditionally include rust headers/helpers once
// Cronet supports Crubit dependencies.
#include "components/cbor/reader.h"

#include <math.h>

#include <iterator>
#include <limits>
#include <map>
#include <utility>

#include "base/bit_cast.h"
#include "base/check_deref.h"
#include "base/check_op.h"
#include "base/containers/to_vector.h"
#include "base/notreached.h"
#include "base/numerics/checked_math.h"
#include "base/numerics/safe_conversions.h"
#include "base/strings/string_util.h"
#include "base/strings/string_view_util.h"
#include "components/cbor/cbor_buildflags.h"
#include "components/cbor/constants.h"

#if BUILDFLAG(USE_CBOR_RUST)
#include "components/cbor/rust/cbor_rust.h"
#endif

namespace cbor {

BASE_FEATURE(kUseRustCborParser, base::FEATURE_DISABLED_BY_DEFAULT);

#if BUILDFLAG(USE_CBOR_RUST)
#define ASSERT_DECODER_ERROR_EQ(cpp_err, rust_err)                   \
  static_assert(std::to_underlying(Reader::DecoderError::cpp_err) == \
                std::to_underlying(cbor::rust::Error::Tag::rust_err))
// LINT.IfChange(DecoderErrorAsserts)
ASSERT_DECODER_ERROR_EQ(UNSUPPORTED_MAJOR_TYPE, UnsupportedMajorType);
ASSERT_DECODER_ERROR_EQ(UNKNOWN_ADDITIONAL_INFO, UnknownAdditionalInfo);
ASSERT_DECODER_ERROR_EQ(INCOMPLETE_CBOR_DATA, IncompleteCborData);
ASSERT_DECODER_ERROR_EQ(INCORRECT_MAP_KEY_TYPE, IncorrectMapKeyType);
ASSERT_DECODER_ERROR_EQ(TOO_MUCH_NESTING, TooMuchNesting);
ASSERT_DECODER_ERROR_EQ(INVALID_UTF8, InvalidUtf8);
ASSERT_DECODER_ERROR_EQ(EXTRANEOUS_DATA, ExtraneousData);
ASSERT_DECODER_ERROR_EQ(OUT_OF_ORDER_KEY, OutOfOrderKey);
ASSERT_DECODER_ERROR_EQ(NON_MINIMAL_CBOR_ENCODING, NonMinimalCborEncoding);
ASSERT_DECODER_ERROR_EQ(UNSUPPORTED_SIMPLE_VALUE, UnsupportedSimpleValue);
ASSERT_DECODER_ERROR_EQ(UNSUPPORTED_FLOATING_POINT_VALUE,
                        UnsupportedFloatingPointValue);
ASSERT_DECODER_ERROR_EQ(OUT_OF_RANGE_INTEGER_VALUE, OutOfRangeIntegerValue);
ASSERT_DECODER_ERROR_EQ(DUPLICATE_KEY, DuplicateKey);
ASSERT_DECODER_ERROR_EQ(UNKNOWN_ERROR, UnknownError);
// LINT.ThenChange(//components/cbor/reader.h:DecoderError,//components/cbor/rust/reader.rs:Error)
#undef ASSERT_DECODER_ERROR_EQ
#endif

namespace constants {
const char kUnsupportedMajorType[] = "Unsupported major type.";
}

namespace {

Value::Type GetMajorType(uint8_t initial_data_byte) {
  return static_cast<Value::Type>(
      (initial_data_byte & constants::kMajorTypeMask) >>
      constants::kMajorTypeBitShift);
}

uint8_t GetAdditionalInfo(uint8_t initial_data_byte) {
  return initial_data_byte & constants::kAdditionalInformationMask;
}

// Error messages that correspond to each of the error codes. There is 1
// exception: we declare |kUnsupportedMajorType| in constants.h in the
// `constants` namespace, because we use it in several files.
const char kNoError[] = "Successfully deserialized to a CBOR value.";
const char kUnknownAdditionalInfo[] =
    "Unknown additional info format in the first byte.";
const char kIncompleteCBORData[] =
    "Prematurely terminated CBOR data byte array.";
const char kIncorrectMapKeyType[] =
    "Specified map key type is not supported by the current implementation.";
const char kTooMuchNesting[] = "Too much nesting.";
const char kInvalidUTF8[] =
    "String encodings other than UTF-8 are not allowed.";
const char kExtraneousData[] = "Trailing data bytes are not allowed.";
const char kMapKeyOutOfOrder[] =
    "Map keys must be strictly monotonically increasing based on byte length "
    "and then by byte-wise lexical order.";
const char kNonMinimalCBOREncoding[] =
    "Unsigned integers must be encoded with minimum number of bytes.";
const char kUnsupportedSimpleValue[] =
    "Unsupported or unassigned simple value.";
const char kUnsupportedFloatingPointValue[] =
    "Floating point numbers are not supported.";
const char kOutOfRangeIntegerValue[] =
    "Integer values must be between INT64_MIN and INT64_MAX.";
const char kMapKeyDuplicate[] = "Duplicate map keys are not allowed.";
const char kUnknownError[] = "An unknown error occured.";

#if BUILDFLAG(USE_CBOR_RUST)

Value ConvertRustMapKeyToCpp(const cbor::rust::MapKey& rust_key) {
  switch (rust_key.kind().tag) {
    case cbor::rust::MapKeyKind::Tag::Int:
      return Value(CHECK_DEREF(rust_key.as_int()));
    case cbor::rust::MapKeyKind::Tag::String:
      return Value(CHECK_DEREF(rust_key.as_string()).to_string_view(),
                   Value::Type::STRING);
    case cbor::rust::MapKeyKind::Tag::Bytestring:
      return Value(CHECK_DEREF(rust_key.as_bytestring()).to_span());
  }
  NOTREACHED();
}
#endif

}  // namespace

Reader::Config::Config()
    : use_rust(base::FeatureList::IsEnabled(kUseRustCborParser)) {}
Reader::Config::~Config() = default;

Reader::Reader(base::span<const uint8_t> data)
    : rest_(data), error_code_(DecoderError::CBOR_NO_ERROR) {}
Reader::~Reader() = default;

#if BUILDFLAG(USE_CBOR_RUST)
Value Reader::ConvertRustValueToCpp(const cbor::rust::Value& rust_val) {
  switch (rust_val.kind().tag) {
    case cbor::rust::ValueKind::Tag::Int:
      return Value(CHECK_DEREF(rust_val.as_int()));
    case cbor::rust::ValueKind::Tag::Boolean:
      return Value(CHECK_DEREF(rust_val.as_bool()));
    case cbor::rust::ValueKind::Tag::Null:
      return Value(Value::SimpleValue::NULL_VALUE);
    case cbor::rust::ValueKind::Tag::Undefined:
      return Value(Value::SimpleValue::UNDEFINED);
    case cbor::rust::ValueKind::Tag::Bytestring:
      return Value(CHECK_DEREF(rust_val.as_bytestring()).to_span(),
                   Value::Type::BYTE_STRING);
    case cbor::rust::ValueKind::Tag::String:
      return Value(CHECK_DEREF(rust_val.as_string()).to_string_view(),
                   Value::Type::STRING);
    case cbor::rust::ValueKind::Tag::InvalidUtf8:
      return Value(CHECK_DEREF(rust_val.as_invalid_utf8()).to_span(),
                   Value::Type::INVALID_UTF8);
    case cbor::rust::ValueKind::Tag::Array: {
      return Value(base::ToVector(CHECK_DEREF(rust_val.as_array()).to_span(),
                                  ConvertRustValueToCpp));
    }
    case cbor::rust::ValueKind::Tag::Map: {
      return Value(Value::MapValue(
          base::sorted_unique,
          base::ToVector(CHECK_DEREF(rust_val.map_entries()).to_span(),
                         [](const auto& entry) {
                           return std::pair(ConvertRustMapKeyToCpp(entry.key),
                                            ConvertRustValueToCpp(entry.value));
                         })));
    }
  }
  NOTREACHED();
}
#endif

// static
std::optional<Value> Reader::Read(base::span<uint8_t const> data,
                                  DecoderError* error_code_out,
                                  int max_nesting_level) {
  Config config;
  config.error_code_out = error_code_out;
  config.max_nesting_level = max_nesting_level;

  return Read(data, config);
}

// static
std::optional<Value> Reader::Read(base::span<uint8_t const> data,
                                  size_t* num_bytes_consumed,
                                  DecoderError* error_code_out,
                                  int max_nesting_level) {
  DCHECK(num_bytes_consumed);

  Config config;
  config.num_bytes_consumed = num_bytes_consumed;
  config.error_code_out = error_code_out;
  config.max_nesting_level = max_nesting_level;

  return Read(data, config);
}

// static
std::optional<Value> Reader::Read(base::span<uint8_t const> data,
                                  const Config& config) {
#if BUILDFLAG(USE_CBOR_RUST)
  if (config.use_rust) {
    cbor::rust::Config rust_config;
    rust_config.allow_invalid_utf8 = config.allow_invalid_utf8;
    rust_config.max_nesting_level = config.max_nesting_level;

    size_t ignored_num_bytes_consumed;
    size_t& num_bytes_consumed = config.num_bytes_consumed
                                     ? *config.num_bytes_consumed
                                     : ignored_num_bytes_consumed;
    DecoderError ignored_error_code_out;
    DecoderError& error_code_out =
        config.error_code_out ? *config.error_code_out : ignored_error_code_out;

    auto result = cbor::rust::parse_with_config(data, rust_config);

    if (!result.has_value()) {
      num_bytes_consumed = 0;
      // The static_cast is currently safe because the enum values in
      // cbor::Reader::DecoderError are initialized by the values of
      // cbor::rust::Error.
      error_code_out = static_cast<DecoderError>(result.err().tag);
      return std::nullopt;
    }

    if (!config.num_bytes_consumed && result->bytes_consumed < data.size()) {
      error_code_out = DecoderError::EXTRANEOUS_DATA;
      return std::nullopt;
    }

    num_bytes_consumed = result->bytes_consumed;
    error_code_out = DecoderError::CBOR_NO_ERROR;

    return ConvertRustValueToCpp(result->value);
  }
#else
  CHECK(!config.use_rust)
      << "CBOR Rust parser is statically disabled in this build";
#endif

  Reader reader(data);
  std::optional<Value> value =
      reader.DecodeCompleteDataItem(config, config.max_nesting_level);

  auto error = reader.GetErrorCode();
  const bool success = value.has_value();
  DCHECK_EQ(success, error == DecoderError::CBOR_NO_ERROR);

  if (config.num_bytes_consumed) {
    *config.num_bytes_consumed =
        success ? data.size() - reader.num_bytes_remaining() : 0;
  } else if (success && reader.num_bytes_remaining() > 0) {
    error = DecoderError::EXTRANEOUS_DATA;
    value.reset();
  }

  if (config.error_code_out) {
    *config.error_code_out = error;
  }

  return value;
}

std::optional<Value> Reader::DecodeCompleteDataItem(const Config& config,
                                                    int max_nesting_level) {
  if (max_nesting_level < 0 || max_nesting_level > kCBORMaxDepth) {
    error_code_ = DecoderError::TOO_MUCH_NESTING;
    return std::nullopt;
  }

  std::optional<DataItemHeader> header = DecodeDataItemHeader();
  if (!header.has_value()) {
    return std::nullopt;
  }

  switch (header->type) {
    case Value::Type::UNSIGNED:
      return DecodeValueToUnsigned(header->value);
    case Value::Type::NEGATIVE:
      return DecodeValueToNegative(header->value);
    case Value::Type::BYTE_STRING:
      return ReadByteStringContent(*header);
    case Value::Type::STRING:
      return ReadStringContent(*header, config);
    case Value::Type::ARRAY:
      return ReadArrayContent(*header, config, max_nesting_level);
    case Value::Type::MAP:
      return ReadMapContent(*header, config, max_nesting_level);
    case Value::Type::SIMPLE_VALUE:
      return DecodeToSimpleValue(*header);
    case Value::Type::NONE:
    case Value::Type::INVALID_UTF8:
      break;
  }

  error_code_ = DecoderError::UNSUPPORTED_MAJOR_TYPE;
  return std::nullopt;
}

std::optional<Reader::DataItemHeader> Reader::DecodeDataItemHeader() {
  const std::optional<uint8_t> initial_byte = ReadByte();
  if (!initial_byte) {
    return std::nullopt;
  }

  const auto major_type = GetMajorType(initial_byte.value());
  const uint8_t additional_info = GetAdditionalInfo(initial_byte.value());

  std::optional<uint64_t> value = ReadVariadicLengthInteger(additional_info);
  return value ? std::make_optional(
                     DataItemHeader{major_type, additional_info, value.value()})
               : std::nullopt;
}

std::optional<uint64_t> Reader::ReadVariadicLengthInteger(
    uint8_t additional_info) {
  uint8_t additional_bytes = 0;
  if (additional_info < 24) {
    return std::make_optional(additional_info);
  } else if (additional_info == 24) {
    additional_bytes = 1;
  } else if (additional_info == 25) {
    additional_bytes = 2;
  } else if (additional_info == 26) {
    additional_bytes = 4;
  } else if (additional_info == 27) {
    additional_bytes = 8;
  } else {
    error_code_ = DecoderError::UNKNOWN_ADDITIONAL_INFO;
    return std::nullopt;
  }

  const std::optional<base::span<const uint8_t>> bytes =
      ReadBytes(additional_bytes);
  if (!bytes) {
    return std::nullopt;
  }

  uint64_t int_data = 0;
  for (const uint8_t b : bytes.value()) {
    int_data <<= 8;
    int_data |= b;
  }

  return IsEncodingMinimal(additional_bytes, int_data)
             ? std::make_optional(int_data)
             : std::nullopt;
}

std::optional<Value> Reader::DecodeValueToNegative(uint64_t value) {
  auto negative_value = -base::CheckedNumeric<int64_t>(value) - 1;
  if (!negative_value.IsValid()) {
    error_code_ = DecoderError::OUT_OF_RANGE_INTEGER_VALUE;
    return std::nullopt;
  }
  return Value(static_cast<int64_t>(negative_value.ValueOrDie()));
}

std::optional<Value> Reader::DecodeValueToUnsigned(uint64_t value) {
  auto unsigned_value = base::CheckedNumeric<int64_t>(value);
  if (!unsigned_value.IsValid()) {
    error_code_ = DecoderError::OUT_OF_RANGE_INTEGER_VALUE;
    return std::nullopt;
  }
  return Value(static_cast<int64_t>(unsigned_value.ValueOrDie()));
}

std::optional<Value> Reader::DecodeToSimpleValue(const DataItemHeader& header) {
  // ReadVariadicLengthInteger provides this bound.
  CHECK_LE(header.additional_info, 27);
  // Floating point numbers.
  if (header.additional_info > 24) {
    error_code_ = DecoderError::UNSUPPORTED_FLOATING_POINT_VALUE;
    return std::nullopt;
  }

  // Since |header.additional_info| <= 24, ReadVariadicLengthInteger also
  // provides this bound for |header.value|.
  CHECK_LE(header.value, 255u);
  // |SimpleValue| is an enum class and so the underlying type is specified to
  // be |int|. So this cast is safe.
  Value::SimpleValue possibly_unsupported_simple_value =
      static_cast<Value::SimpleValue>(static_cast<int>(header.value));
  switch (possibly_unsupported_simple_value) {
    case Value::SimpleValue::FALSE_VALUE:
    case Value::SimpleValue::TRUE_VALUE:
    case Value::SimpleValue::NULL_VALUE:
    case Value::SimpleValue::UNDEFINED:
      return Value(possibly_unsupported_simple_value);
  }

  error_code_ = DecoderError::UNSUPPORTED_SIMPLE_VALUE;
  return std::nullopt;
}

std::optional<Value> Reader::ReadStringContent(
    const Reader::DataItemHeader& header,
    const Config& config) {
  uint64_t num_bytes = header.value;
  const std::optional<base::span<const uint8_t>> bytes = ReadBytes(num_bytes);
  if (!bytes) {
    return std::nullopt;
  }

  if (std::string_view cbor_string_view = base::as_string_view(*bytes);
      base::IsStringUTF8AllowingNoncharacters(cbor_string_view)) {
    return Value(cbor_string_view);
  }

  if (config.allow_invalid_utf8) {
    return Value(*bytes, Value::Type::INVALID_UTF8);
  }

  error_code_ = DecoderError::INVALID_UTF8;
  return std::nullopt;
}

std::optional<Value> Reader::ReadByteStringContent(
    const Reader::DataItemHeader& header) {
  uint64_t num_bytes = header.value;
  const std::optional<base::span<const uint8_t>> bytes = ReadBytes(num_bytes);
  if (!bytes) {
    return std::nullopt;
  }

  return Value(*bytes);
}

std::optional<Value> Reader::ReadArrayContent(
    const Reader::DataItemHeader& header,
    const Config& config,
    int max_nesting_level) {
  const uint64_t length = header.value;

  Value::ArrayValue cbor_array;
  for (uint64_t i = 0; i < length; ++i) {
    std::optional<Value> cbor_element =
        DecodeCompleteDataItem(config, max_nesting_level - 1);
    if (!cbor_element.has_value()) {
      return std::nullopt;
    }
    cbor_array.push_back(std::move(cbor_element.value()));
  }
  return Value(std::move(cbor_array));
}

std::optional<Value> Reader::ReadMapContent(
    const Reader::DataItemHeader& header,
    const Config& config,
    int max_nesting_level) {
  const uint64_t length = header.value;

  std::map<Value, Value, Value::Less> cbor_map;
  for (uint64_t i = 0; i < length; ++i) {
    std::optional<Value> key =
        DecodeCompleteDataItem(config, max_nesting_level - 1);
    if (!key.has_value()) {
      return std::nullopt;
    }
    std::optional<Value> value =
        DecodeCompleteDataItem(config, max_nesting_level - 1);
    if (!value.has_value()) {
      return std::nullopt;
    }

    switch (key.value().type()) {
      case Value::Type::UNSIGNED:
      case Value::Type::NEGATIVE:
      case Value::Type::STRING:
      case Value::Type::BYTE_STRING:
        break;
      case Value::Type::INVALID_UTF8:
        error_code_ = DecoderError::INVALID_UTF8;
        return std::nullopt;
      default:
        error_code_ = DecoderError::INCORRECT_MAP_KEY_TYPE;
        return std::nullopt;
    }

    auto [it, inserted] =
        cbor_map.try_emplace(std::move(key.value()), std::move(value.value()));
    if (!inserted) {
      error_code_ = DecoderError::DUPLICATE_KEY;
      return std::nullopt;
    }

    if (std::next(it) != cbor_map.end()) {
      error_code_ = DecoderError::OUT_OF_ORDER_KEY;
      return std::nullopt;
    }
  }

  std::vector<std::pair<Value, Value>> items;
  items.reserve(cbor_map.size());
  while (!cbor_map.empty()) {
    auto node = cbor_map.extract(cbor_map.begin());
    items.emplace_back(std::move(node.key()), std::move(node.mapped()));
  }
  return Value(Value::MapValue(base::sorted_unique, std::move(items)));
}

std::optional<uint8_t> Reader::ReadByte() {
  const std::optional<base::span<const uint8_t>> bytes = ReadBytes(1);
  return bytes ? std::make_optional(bytes.value()[0]) : std::nullopt;
}

std::optional<base::span<const uint8_t>> Reader::ReadBytes(uint64_t num_bytes) {
  if (base::strict_cast<uint64_t>(rest_.size()) < num_bytes) {
    error_code_ = DecoderError::INCOMPLETE_CBOR_DATA;
    return std::nullopt;
  }

  // The `uint64_t` => `size_t` conversion below will always succeed
  // because the `if` condition above implies that `num_bytes` fits into a
  // `size_t`.
  return rest_.take_first(base::checked_cast<size_t>(num_bytes));
}

bool Reader::IsEncodingMinimal(uint8_t additional_bytes, uint64_t uint_data) {
  if ((additional_bytes == 1 && uint_data < 24) ||
      uint_data <= (1ULL << 8 * (additional_bytes >> 1)) - 1) {
    error_code_ = DecoderError::NON_MINIMAL_CBOR_ENCODING;
    return false;
  }
  return true;
}

// static
const char* Reader::ErrorCodeToString(DecoderError error) {
  switch (error) {
    case DecoderError::CBOR_NO_ERROR:
      return kNoError;
    case DecoderError::UNSUPPORTED_MAJOR_TYPE:
      return constants::kUnsupportedMajorType;
    case DecoderError::UNKNOWN_ADDITIONAL_INFO:
      return kUnknownAdditionalInfo;
    case DecoderError::INCOMPLETE_CBOR_DATA:
      return kIncompleteCBORData;
    case DecoderError::INCORRECT_MAP_KEY_TYPE:
      return kIncorrectMapKeyType;
    case DecoderError::TOO_MUCH_NESTING:
      return kTooMuchNesting;
    case DecoderError::INVALID_UTF8:
      return kInvalidUTF8;
    case DecoderError::EXTRANEOUS_DATA:
      return kExtraneousData;
    case DecoderError::OUT_OF_ORDER_KEY:
      return kMapKeyOutOfOrder;
    case DecoderError::NON_MINIMAL_CBOR_ENCODING:
      return kNonMinimalCBOREncoding;
    case DecoderError::UNSUPPORTED_SIMPLE_VALUE:
      return kUnsupportedSimpleValue;
    case DecoderError::UNSUPPORTED_FLOATING_POINT_VALUE:
      return kUnsupportedFloatingPointValue;
    case DecoderError::OUT_OF_RANGE_INTEGER_VALUE:
      return kOutOfRangeIntegerValue;
    case DecoderError::DUPLICATE_KEY:
      return kMapKeyDuplicate;
    case DecoderError::UNKNOWN_ERROR:
      return kUnknownError;
    default:
      NOTREACHED();
  }
}

}  // namespace cbor