felipecrv commented on code in PR #51647:
URL: https://github.com/apache/arrow/pull/51647#discussion_r4592372525


##########
cpp/src/arrow/array/array_nested.cc:
##########
@@ -415,37 +415,8 @@ Result<std::shared_ptr<ArrayData>> ListFromListViewImpl(
       std::is_same<typename SrcListViewType::offset_type,
                    typename DestListType::offset_type>::value,
       "Offset types between list type and list-view type are expected to 
match");
-  using offset_type = typename DestListType::offset_type;
-  using ListBuilderType = typename TypeTraits<DestListType>::BuilderType;
-
-  const auto& list_view_type =
-      checked_cast<const SrcListViewType&>(*list_view_data->type);
-  const auto& value_type = list_view_type.value_type();
-  const auto list_type = std::make_shared<DestListType>(value_type);
-
-  ARROW_ASSIGN_OR_RAISE(auto sum_of_list_view_sizes,
-                        
list_util::internal::SumOfLogicalListSizes(*list_view_data));
-  ARROW_ASSIGN_OR_RAISE(std::shared_ptr<ArrayBuilder> value_builder,
-                        MakeBuilder(value_type, pool));
-  RETURN_NOT_OK(value_builder->Reserve(sum_of_list_view_sizes));
-  auto list_builder = std::make_shared<ListBuilderType>(pool, value_builder, 
list_type);
-  RETURN_NOT_OK(list_builder->Reserve(list_view_data->length));
-
-  ArraySpan values{*list_view_data->child_data[0]};
-  const auto* in_validity_bitmap = list_view_data->GetValues<uint8_t>(0);
-  const auto* in_offsets = list_view_data->GetValues<offset_type>(1);
-  const auto* in_sizes = list_view_data->GetValues<offset_type>(2);
-  for (int64_t i = 0; i < list_view_data->length; ++i) {
-    const bool is_valid =
-        !in_validity_bitmap ||
-        bit_util::GetBit(in_validity_bitmap, list_view_data->offset + i);
-    const int64_t size = is_valid ? in_sizes[i] : 0;
-    RETURN_NOT_OK(list_builder->Append(is_valid, size));
-    RETURN_NOT_OK(value_builder->AppendArraySlice(values, in_offsets[i], 
size));
-  }
-  std::shared_ptr<ArrayData> list_array_data;
-  RETURN_NOT_OK(list_builder->FinishInternal(&list_array_data));
-  return list_array_data;
+  return list_util::internal::ListFromListView(ArraySpan{*list_view_data},
+                                               DestListType::type_id, pool);

Review Comment:
   The more common order is a function that takes dynamically typed values to 
delegate to the statically typed (templated/specialized). Here the opposite is 
happening.
   
   This template has the types already worked out, but then it delegates to a 
function that is going to switch on the type ids again.



##########
cpp/src/arrow/compute/kernels/scalar_cast_nested.cc:
##########
@@ -105,7 +106,37 @@ struct CastList {
     return Status::OK();
   }
 
+  /// \brief Cast a list-view array to a (large)list array
+  ///
+  /// The values referenced by a list-view have to be gathered according to the
+  /// views' offsets and sizes, so the views' offsets buffer cannot be reused 
as
+  /// a list-offsets buffer (GH-51612).
+  static Status ExecListView(KernelContext* ctx, const ExecSpan& batch, 
ExecResult* out) {
+    const CastOptions& options = CastState::Get(ctx);
+    auto child_type = checked_cast<const DestType&>(*out->type()).value_type();
+
+    ARROW_ASSIGN_OR_RAISE(std::shared_ptr<ArrayData> list_data,
+                          list_util::internal::ListFromListView(
+                              batch[0].array, DestType::type_id, 
ctx->memory_pool()));
+
+    ARROW_ASSIGN_OR_RAISE(Datum cast_values, Cast(list_data->child_data[0], 
child_type,
+                                                  options, 
ctx->exec_context()));
+    DCHECK(cast_values.is_array());
+
+    ArrayData* out_array = out->array_data().get();
+    out_array->buffers[0] = std::move(list_data->buffers[0]);
+    out_array->buffers[1] = std::move(list_data->buffers[1]);
+    out_array->null_count.store(list_data->null_count.load());
+    out_array->offset = list_data->offset;
+    out_array->child_data.push_back(cast_values.array());
+    return Status::OK();
+  }
+
   static Status Exec(KernelContext* ctx, const ExecSpan& batch, ExecResult* 
out) {
+    if constexpr (is_list_view(SrcType::type_id)) {
+      return ExecListView(ctx, batch, out);
+    }
+

Review Comment:
   This is a weird short-circuit for this logic that is meant to be generic for 
nested arrays. It would make more sense to have a branch around `HandleOffsets` 
and the handling of values. And what you want is not always a cast of the 
entire array to list-view. You want to make the cast values packed in sequence 
according to the slices created by the offset-size pairs.
   
   From those values you can decide to output a list-view or a *list. Always 
returning list is going to be weird (i.e. list-view in, list out).



##########
cpp/src/arrow/util/list_util.cc:
##########
@@ -190,8 +199,346 @@ int64_t SumOfListViewSizes(const ArraySpan& input) {
   return sum;
 }
 
+std::shared_ptr<DataType> StorageType(const std::shared_ptr<DataType>& type);
+
+std::shared_ptr<Field> StorageField(const std::shared_ptr<Field>& field) {
+  return field->WithType(StorageType(field->type()));
+}
+
+FieldVector StorageFields(const FieldVector& fields) {
+  FieldVector storage_fields;
+  storage_fields.reserve(fields.size());
+  for (const auto& field : fields) {
+    storage_fields.push_back(StorageField(field));
+  }
+  return storage_fields;
+}
+
+/// \brief Replace every extension type by its storage type, recursively
+///
+/// `MakeBuilder` does not support extension types, so the values gathered from
+/// a list-view are built using their storage types. The original types are 
then
+/// restored by `RestoreType`.
+std::shared_ptr<DataType> StorageType(const std::shared_ptr<DataType>& type) {
+  switch (type->id()) {
+    case Type::EXTENSION:
+      return StorageType(checked_cast<const 
ExtensionType&>(*type).storage_type());
+    case Type::LIST:
+      return std::make_shared<ListType>(
+          StorageField(checked_cast<const ListType&>(*type).value_field()));
+    case Type::LARGE_LIST:
+      return std::make_shared<LargeListType>(
+          StorageField(checked_cast<const 
LargeListType&>(*type).value_field()));
+    case Type::LIST_VIEW:
+      return std::make_shared<ListViewType>(
+          StorageField(checked_cast<const 
ListViewType&>(*type).value_field()));
+    case Type::LARGE_LIST_VIEW:
+      return std::make_shared<LargeListViewType>(
+          StorageField(checked_cast<const 
LargeListViewType&>(*type).value_field()));
+    case Type::MAP: {
+      const auto& map_type = checked_cast<const MapType&>(*type);
+      return std::make_shared<MapType>(StorageField(map_type.key_field()),
+                                       StorageField(map_type.item_field()),
+                                       map_type.keys_sorted());
+    }
+    case Type::FIXED_SIZE_LIST: {
+      const auto& list_type = checked_cast<const FixedSizeListType&>(*type);
+      return 
std::make_shared<FixedSizeListType>(StorageField(list_type.value_field()),
+                                                 list_type.list_size());
+    }
+    case Type::STRUCT:
+      return std::make_shared<StructType>(StorageFields(type->fields()));
+    case Type::SPARSE_UNION: {
+      const auto& union_type = checked_cast<const SparseUnionType&>(*type);
+      return 
std::make_shared<SparseUnionType>(StorageFields(union_type.fields()),
+                                               union_type.type_codes());
+    }
+    case Type::DENSE_UNION: {
+      const auto& union_type = checked_cast<const DenseUnionType&>(*type);
+      return 
std::make_shared<DenseUnionType>(StorageFields(union_type.fields()),
+                                              union_type.type_codes());
+    }
+    case Type::RUN_END_ENCODED: {
+      const auto& ree_type = checked_cast<const RunEndEncodedType&>(*type);
+      return std::make_shared<RunEndEncodedType>(ree_type.run_end_type(),
+                                                 
StorageType(ree_type.value_type()));
+    }
+    case Type::DICTIONARY: {
+      const auto& dict_type = checked_cast<const DictionaryType&>(*type);
+      return std::make_shared<DictionaryType>(dict_type.index_type(),
+                                              
StorageType(dict_type.value_type()),
+                                              dict_type.ordered());
+    }
+    default:
+      return type;
+  }
+}
+
+/// \brief Restore the original (possibly nested) types on gathered array data
+void RestoreType(const std::shared_ptr<DataType>& type, ArrayData* data,
+                 bool update_type = true) {
+  if (update_type) {
+    data->type = type;
+  }
+  switch (type->id()) {
+    case Type::EXTENSION:
+      RestoreType(checked_cast<const ExtensionType&>(*type).storage_type(), 
data,
+                  /*update_type=*/false);
+      break;
+    case Type::LIST:
+    case Type::LARGE_LIST:
+    case Type::LIST_VIEW:
+    case Type::LARGE_LIST_VIEW:
+    case Type::MAP:
+    case Type::FIXED_SIZE_LIST:
+      RestoreType(type->field(0)->type(), data->child_data[0].get());
+      break;
+    case Type::STRUCT:
+    case Type::SPARSE_UNION:
+    case Type::DENSE_UNION:
+    case Type::RUN_END_ENCODED:
+      for (int i = 0; i < type->num_fields(); ++i) {
+        RestoreType(type->field(i)->type(), data->child_data[i].get());
+      }
+      break;
+    case Type::DICTIONARY:
+      if (data->dictionary) {
+        RestoreType(checked_cast<const DictionaryType&>(*type).value_type(),
+                    data->dictionary.get());
+      }
+      break;
+    default:
+      break;
+  }
+}
+
+/// \brief Rewrite the type of a span and of all its children to a storage type
+///
+/// The gathered values are appended to storage-typed builders (see
+/// `StorageType`), so the appended slices have to be seen through those same
+/// storage types: a builder may check or inspect the type of the array it is
+/// given (e.g. `RunEndEncodedBuilder` or `DictionaryBuilder`).
+///
+/// \pre `span` has the layout of `storage_type`, i.e. the two only differ by
+///      extension types
+void ApplyStorageType(ArraySpan* span, const std::shared_ptr<DataType>& 
storage_type) {
+  span->type = storage_type.get();
+  if (storage_type->id() == Type::DICTIONARY) {
+    // An ArraySpan holds the dictionary of a dictionary array in its first 
child
+    const auto& dict_type = checked_cast<const DictionaryType&>(*storage_type);
+    ApplyStorageType(&span->child_data[0], dict_type.value_type());
+    return;
+  }
+  for (int i = 0; i < static_cast<int>(span->child_data.size()); ++i) {
+    ApplyStorageType(&span->child_data[i], storage_type->field(i)->type());
+  }
+}
+
+/// \brief The range of values a list-view references, when its views are 
contiguous
+///
+/// A list-view describes a list without moving any value when its valid views
+/// are in order and contiguous, i.e. when every valid view with values starts
+/// where the previous valid view with values ended. Empty views reference no
+/// value, so their offsets are ignored. Such a view is a list in disguise: the
+/// values it references are a slice of its child array, and the values that
+/// only null views reference (before the first and after the last valid view)
+/// are not part of that slice.
+///
+/// \return The range of the child array to keep, or `std::nullopt` when the
+///         views are out of order, overlapping or have gaps in between
+template <typename SrcListViewType>
+std::optional<std::pair<int64_t, int64_t>> ContiguousValuesRange(
+    const ArraySpan& list_view) {
+  using offset_type = typename SrcListViewType::offset_type;
+  const uint8_t* validity = list_view.buffers[0].data;
+  const auto* offsets = list_view.GetValues<offset_type>(1);
+  const auto* sizes = list_view.GetValues<offset_type>(2);
+  const int64_t values_length = list_view.child_data[0].length;
+
+  int64_t range_start = 0;
+  int64_t range_end = 0;
+  bool has_valid_view = false;
+  for (int64_t i = 0; i < list_view.length; ++i) {
+    // A null view contributes no values, whatever size it declares.
+    if (validity != nullptr && !bit_util::GetBit(validity, list_view.offset + 
i)) {
+      continue;
+    }
+    const int64_t offset = offsets[i];
+    const int64_t size = sizes[i];
+    if (offset < 0 || size < 0 || offset > values_length ||
+        size > values_length - offset) {
+      return std::nullopt;
+    }
+    // An empty view references no value, so neither its offset nor its
+    // position can break the contiguity of the other views.
+    if (size == 0) {
+      continue;
+    }
+    if (!has_valid_view) {
+      range_start = offset;
+      has_valid_view = true;
+    } else if (offset != range_end) {
+      // Values are missing, shared or referenced out of order: they have to be
+      // gathered instead of sliced.
+      return std::nullopt;
+    }
+    range_end = offset + size;
+  }
+  if (!has_valid_view) {
+    // Every view is null: no value is referenced at all.
+    return std::make_pair<int64_t, int64_t>(0, 0);
+  }
+  return std::make_pair(range_start, range_end - range_start);
+}
+
+/// \brief Convert a list-view whose views are contiguous, keeping its values
+///
+/// \param list_view A LIST_VIEW or LARGE_LIST_VIEW array whose views are
+/// contiguous, as checked by `ContiguousValuesRange`
+/// \param values_range The range of the values to keep, as returned by
+/// `ContiguousValuesRange`
+template <typename DestListType, typename SrcListViewType>
+Result<std::shared_ptr<ArrayData>> ContiguousViewToList(
+    const ArraySpan& list_view, const std::pair<int64_t, int64_t>& 
values_range,
+    MemoryPool* pool) {
+  using src_offset_type = typename SrcListViewType::offset_type;
+  using dest_offset_type = typename DestListType::offset_type;
+
+  const auto& list_view_type = checked_cast<const 
SrcListViewType&>(*list_view.type);
+  const auto list_type = 
std::make_shared<DestListType>(list_view_type.value_type());
+  const int64_t range_length = values_range.second;
+  if (range_length > std::numeric_limits<dest_offset_type>::max()) {
+    return Status::Invalid("Array of type ", list_view.type->ToString(),
+                           " too large to convert to ", list_type->ToString());
+  }
+
+  // The views' offsets cannot be reused as list offsets: they are relative to
+  // the child array, not to the range of values that is kept, and the views'
+  // declared sizes are dropped for the null ones.
+  ARROW_ASSIGN_OR_RAISE(
+      std::shared_ptr<Buffer> offsets_buffer,
+      AllocateBuffer(sizeof(dest_offset_type) * (list_view.length + 1), pool));
+  auto* offsets = offsets_buffer->mutable_data_as<dest_offset_type>();
+  const uint8_t* validity = list_view.buffers[0].data;
+  const auto* sizes = list_view.GetValues<src_offset_type>(2);
+  dest_offset_type offset = 0;
+  for (int64_t i = 0; i < list_view.length; ++i) {
+    offsets[i] = offset;
+    const bool is_valid = !validity || bit_util::GetBit(validity, 
list_view.offset + i);
+    offset += static_cast<dest_offset_type>(is_valid ? sizes[i] : 0);
+  }
+  offsets[list_view.length] = offset;
+  DCHECK_EQ(offset, range_length);
+
+  // The bitmap is bit-packed, so it can only be shared when the views start at
+  // the first bit; otherwise the range has to be copied out of the way.
+  std::shared_ptr<Buffer> null_bitmap = list_view.GetBuffer(0);
+  if (validity != nullptr && list_view.offset != 0) {
+    ARROW_ASSIGN_OR_RAISE(null_bitmap,
+                          CopyBitmap(pool, validity, list_view.offset, 
list_view.length));
+  }
+
+  // The values are kept as they are, only narrowed down to the values that the
+  // valid views reference (GH-51612).
+  std::shared_ptr<ArrayData> values = list_view.child_data[0].ToArrayData();
+  if (values_range.first != 0 || range_length != values->length) {
+    values = values->Slice(values_range.first, range_length);
+  }
+
+  return ArrayData::Make(list_type, list_view.length,
+                         {std::move(null_bitmap), std::move(offsets_buffer)},
+                         {std::move(values)}, list_view.GetNullCount());
+}
+
+/// \param list_view A LIST_VIEW or LARGE_LIST_VIEW array
+template <typename DestListType, typename SrcListViewType>
+Result<std::shared_ptr<ArrayData>> ListFromListViewImpl(const ArraySpan& 
list_view,
+                                                        MemoryPool* pool) {
+  using src_offset_type = typename SrcListViewType::offset_type;
+  using ListBuilderType = typename TypeTraits<DestListType>::BuilderType;
+
+  const auto& list_view_type = checked_cast<const 
SrcListViewType&>(*list_view.type);
+  const auto& value_type = list_view_type.value_type();
+
+  // The views may already describe a list, in which case its values are kept
+  // instead of being gathered (GH-51612).
+  if (auto values_range = ContiguousValuesRange<SrcListViewType>(list_view)) {
+    return ContiguousViewToList<DestListType, SrcListViewType>(list_view, 
*values_range,
+                                                               pool);
+  }
+  // MakeBuilder does not support extension types, so the values are gathered
+  // through their storage types.
+  const auto storage_value_type = StorageType(value_type);
+  // The value type is carried over, so that callers may cast the child.
+  auto list_type = std::make_shared<DestListType>(value_type);
+
+  ARROW_ASSIGN_OR_RAISE(auto sum_of_sizes, SumOfLogicalListSizes(list_view));
+  ARROW_ASSIGN_OR_RAISE(std::shared_ptr<ArrayBuilder> value_builder,
+                        MakeBuilder(storage_value_type, pool));
+  RETURN_NOT_OK(value_builder->Reserve(sum_of_sizes));
+  auto list_builder = std::make_shared<ListBuilderType>(pool, value_builder, 
list_type);
+  RETURN_NOT_OK(list_builder->Reserve(list_view.length));
+
+  // The bitmap is bit-packed, so it must be read with the element offset
+  // applied as a bit offset, not as the byte offset GetValues() would apply.
+  const uint8_t* validity = list_view.buffers[0].data;
+  const auto* offsets = list_view.GetValues<src_offset_type>(1);
+  const auto* sizes = list_view.GetValues<src_offset_type>(2);
+  // The value builder is storage-typed, so the appended slices must be seen
+  // through the storage types as well (GH-51612).
+  ArraySpan values{list_view.child_data[0]};
+  ApplyStorageType(&values, storage_value_type);
+  for (int64_t i = 0; i < list_view.length; ++i) {
+    const bool is_valid = !validity || bit_util::GetBit(validity, 
list_view.offset + i);
+    // A null view contributes no values, whatever size it declares.
+    const int64_t size = is_valid ? sizes[i] : 0;
+    RETURN_NOT_OK(list_builder->Append(is_valid, size));
+    RETURN_NOT_OK(value_builder->AppendArraySlice(values, offsets[i], size));
+  }
+
+  std::shared_ptr<ArrayData> list_data;
+  RETURN_NOT_OK(list_builder->FinishInternal(&list_data));
+  // The builders produced storage-typed data; restore the original types,
+  // including extension types nested anywhere in the value type.
+  list_data->type = list_type;
+  RestoreType(value_type, list_data->child_data[0].get());
+  return list_data;
+}
+
 }  // namespace
 
+Result<std::shared_ptr<ArrayData>> ListFromListView(const ArraySpan& input,
+                                                    Type::type dest_type_id,
+                                                    MemoryPool* pool) {
+  switch (input.type->id()) {
+    case Type::LIST_VIEW:
+      switch (dest_type_id) {
+        case Type::LIST:
+          return ListFromListViewImpl<ListType, ListViewType>(input, pool);
+        case Type::LARGE_LIST:
+          return ListFromListViewImpl<LargeListType, ListViewType>(input, 
pool);
+        default:
+          break;
+      }
+      break;
+    case Type::LARGE_LIST_VIEW:
+      switch (dest_type_id) {
+        case Type::LIST:
+          return ListFromListViewImpl<ListType, LargeListViewType>(input, 
pool);
+        case Type::LARGE_LIST:
+          return ListFromListViewImpl<LargeListType, LargeListViewType>(input, 
pool);
+        default:
+          break;
+      }
+      break;
+    default:
+      break;
+  }
+  return Status::TypeError("ListFromListView: expected a list-view array and a 
",
+                           arrow::internal::ToString(dest_type_id),
+                           " destination type, got ", input.type->ToString());
+}
+

Review Comment:
   This change is large because you are re-doing a big chunk of what 
`array_nested.cc` is trying to achieve recursively. See how you can adapter 
`array_nested.cc` to cast list-views naturally.



-- 
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]

Reply via email to