HuaHuaY commented on code in PR #50252: URL: https://github.com/apache/arrow/pull/50252#discussion_r4397699103
########## cpp/src/parquet/variant/decoding.cc: ########## @@ -0,0 +1,526 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +#include "parquet/variant/decoding.h" + +#include <algorithm> +#include <cstring> +#include <limits> +#include <utility> + +#include "arrow/util/endian.h" +#include "arrow/util/logging_internal.h" +#include "parquet/exception.h" +#include "parquet/variant/format_internal.h" + +namespace parquet::variant { + +namespace bit_util = ::arrow::bit_util; + +namespace internal { + +class ViewAccess { + public: + template <typename View, typename... Args> + static View Make(Args&&... args) { + return View(std::forward<Args>(args)...); + } +}; + +} // namespace internal + +namespace { + +using internal::ViewAccess; + +uint32_t ReadLittleEndian(std::string_view data, size_t offset, size_t width) { + DCHECK_LE(width, sizeof(uint32_t)); + uint32_t value = 0; + std::memcpy(&value, data.data() + offset, width); + return bit_util::FromLittleEndian(value); +} + +void CheckAvailable(std::string_view data, size_t offset, size_t size, + std::string_view context) { + if (offset > data.size() || data.size() - offset < size) { + throw ParquetInvalidOrCorruptedFileException("Invalid Variant encoding: truncated ", + context); + } +} + +size_t OffsetCount(uint32_t count) { + const auto converted_count = static_cast<size_t>(count); + if (converted_count == std::numeric_limits<size_t>::max()) { + throw ParquetInvalidOrCorruptedFileException( + "Invalid Variant encoding: offset count overflow"); + } + return converted_count + 1; +} + +size_t OffsetBytes(size_t offset_count, uint8_t offset_size) { + if (offset_count > + std::numeric_limits<size_t>::max() / static_cast<size_t>(offset_size)) { + throw ParquetInvalidOrCorruptedFileException( + "Invalid Variant encoding: offset table size overflow"); + } + return offset_count * static_cast<size_t>(offset_size); +} + +size_t PrimitivePayloadSize(std::string_view value, size_t offset, + VariantPrimitiveType primitive) { + switch (primitive) { + case VariantPrimitiveType::kNull: + case VariantPrimitiveType::kBooleanTrue: + case VariantPrimitiveType::kBooleanFalse: + return 0; + case VariantPrimitiveType::kInt8: + return 1; + case VariantPrimitiveType::kInt16: + return 2; + case VariantPrimitiveType::kInt32: + case VariantPrimitiveType::kDate: + case VariantPrimitiveType::kFloat: + return 4; + case VariantPrimitiveType::kInt64: + case VariantPrimitiveType::kDouble: + case VariantPrimitiveType::kTimestampMicros: + case VariantPrimitiveType::kTimestampNTZMicros: + case VariantPrimitiveType::kTimeNTZMicros: + case VariantPrimitiveType::kTimestampNanos: + case VariantPrimitiveType::kTimestampNTZNanos: + return 8; + case VariantPrimitiveType::kDecimal4: + return 5; + case VariantPrimitiveType::kDecimal8: + return 9; + case VariantPrimitiveType::kDecimal16: + return 17; + case VariantPrimitiveType::kUuid: + return 16; + case VariantPrimitiveType::kBinary: + case VariantPrimitiveType::kString: { + CheckAvailable(value, offset, 4, "variable-length size"); + const uint32_t length = ReadLittleEndian(value, offset, 4); + return 4 + static_cast<size_t>(length); + } + } + throw ParquetInvalidOrCorruptedFileException( + "Invalid Variant encoding: unknown primitive type"); +} + +size_t ParsePrimitive(std::string_view value, size_t offset, + VariantPrimitiveType primitive) { + if (!internal::IsKnownVariantPrimitive(primitive)) { + throw ParquetInvalidOrCorruptedFileException( + "Invalid Variant encoding: unknown primitive type ", static_cast<int>(primitive)); + } + + const size_t payload_size = PrimitivePayloadSize(value, offset, primitive); + CheckAvailable(value, offset, payload_size, "primitive value"); + + if (internal::IsDecimalVariantPrimitive(primitive)) { + const auto scale = static_cast<uint8_t>(value[offset]); + internal::ValidateDecimalScale(scale); + } + + if (primitive == VariantPrimitiveType::kString) { + const uint32_t length = ReadLittleEndian(value, offset, 4); + internal::ValidateUtf8(value.substr(offset + 4, length), "primitive string value"); + } + + return payload_size; +} + +template <bool validate_children> +size_t ParseValue(std::string_view value, const VariantMetadataView& metadata, + VariantValueView* out); + +template <bool validate_children> +size_t ParseArray(std::string_view value, const VariantMetadataView& metadata, + uint8_t header, VariantValueView* out) { + const auto offset_size = static_cast<uint8_t>((header & 0x03) + 1); + const bool is_large = (header & 0x04) != 0; + const size_t count_size = is_large ? 4 : 1; + + size_t offset = 1; + CheckAvailable(value, offset, count_size, "array size"); + const uint32_t num_elements = ReadLittleEndian(value, offset, count_size); + offset += count_size; + const size_t offset_count = OffsetCount(num_elements); + + CheckAvailable(value, offset, OffsetBytes(offset_count, offset_size), "array offsets"); + + std::vector<uint32_t> offsets(offset_count); + for (size_t i = 0; i < offset_count; ++i) { + offsets[i] = ReadLittleEndian(value, offset, offset_size); + offset += offset_size; + } + + if (offsets[0] != 0) { + throw ParquetInvalidOrCorruptedFileException( + "Invalid Variant encoding: first array offset must be 0"); + } + for (uint32_t i = 0; i < num_elements; ++i) { + if (offsets[i] > offsets[i + 1]) { + throw ParquetInvalidOrCorruptedFileException( + "Invalid Variant encoding: array offsets must be monotonic"); + } + } + + const size_t values_start = offset; + const size_t total_value_size = offsets[num_elements]; + CheckAvailable(value, values_start, total_value_size, "array values"); + + if constexpr (validate_children) { + for (uint32_t i = 0; i < num_elements; ++i) { + const size_t child_consumed = ParseValue<true>( + value.substr(values_start + offsets[i]), metadata, /*out=*/nullptr); + if (child_consumed != offsets[i + 1] - offsets[i]) { + throw ParquetInvalidOrCorruptedFileException( + "Invalid Variant encoding: array value does not end at next offset"); + } + } + } + + const size_t consumed = values_start + total_value_size; + if (out != nullptr) { + std::vector<std::string_view> array_elements; + array_elements.reserve(num_elements); + for (uint32_t i = 0; i < num_elements; ++i) { + array_elements.push_back( + value.substr(values_start + offsets[i], offsets[i + 1] - offsets[i])); + } + *out = ViewAccess::Make<VariantValueView>( + value.substr(0, consumed), + ViewAccess::Make<VariantArrayView>(std::move(array_elements), metadata)); + } + return consumed; +} + +template <bool validate_children> +size_t ParseObject(std::string_view value, const VariantMetadataView& metadata, + uint8_t header, VariantValueView* out) { + const auto offset_size = static_cast<uint8_t>((header & 0x03) + 1); + const auto id_size = static_cast<uint8_t>(((header >> 2) & 0x03) + 1); + const bool is_large = (header & 0x10) != 0; + const size_t count_size = is_large ? 4 : 1; + + size_t offset = 1; + CheckAvailable(value, offset, count_size, "object size"); + const uint32_t num_elements = ReadLittleEndian(value, offset, count_size); + offset += count_size; + + CheckAvailable(value, offset, static_cast<size_t>(num_elements) * id_size, + "object field ids"); + std::vector<uint32_t> field_ids(num_elements); + for (uint32_t i = 0; i < num_elements; ++i) { + field_ids[i] = ReadLittleEndian(value, offset, id_size); + offset += id_size; + } + + const size_t offset_count = OffsetCount(num_elements); + CheckAvailable(value, offset, OffsetBytes(offset_count, offset_size), + "object field offsets"); + std::vector<uint32_t> field_offsets(offset_count); + for (size_t i = 0; i < offset_count; ++i) { + field_offsets[i] = ReadLittleEndian(value, offset, offset_size); + offset += offset_size; + } + + const size_t values_start = offset; + const size_t total_value_size = field_offsets[num_elements]; + if (num_elements == 0 && total_value_size != 0) { + throw ParquetInvalidOrCorruptedFileException( + "Invalid Variant encoding: empty object must have zero value size"); + } + CheckAvailable(value, values_start, total_value_size, "object values"); + + std::vector<VariantObjectField> object_fields; + if (out != nullptr) { + object_fields.reserve(num_elements); + } + + for (uint32_t i = 0; i < num_elements; ++i) { + if (field_ids[i] >= metadata.dictionary_size()) { + throw ParquetInvalidOrCorruptedFileException( + "Invalid Variant encoding: object field id ", field_ids[i], + " is outside metadata dictionary of size ", metadata.dictionary_size()); + } + if constexpr (validate_children) { + if (i > 0 && !(metadata.string(field_ids[i - 1]) < metadata.string(field_ids[i]))) { + throw ParquetInvalidOrCorruptedFileException( + "Invalid Variant encoding: object field names must be sorted and unique"); + } + } + + const auto field_offset = field_offsets[i]; + if (field_offset >= total_value_size) { + throw ParquetInvalidOrCorruptedFileException( + "Invalid Variant encoding: object field offset is outside values"); + } + } + + std::vector<uint32_t> value_offsets = field_offsets; + std::ranges::sort(value_offsets); + if (std::ranges::adjacent_find(value_offsets) != value_offsets.end()) { Review Comment: This sorted array will be used for subsequent binary searches, so I don’t think it can be easily eliminated without compromising the time complexity. Perhaps we could achieve some optimization by using `arrow::internal::SmallVector`. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
