Function FlattenListViewArray

cpp/src/arrow/array/array_nested.cc:268–353

template <typename ListViewArrayT, bool HasNulls>
Result<std::shared_ptr<Array>> FlattenListViewArray(const ListViewArrayT& list_view_array,
                                                    MemoryPool* memory_pool) {
  using offset_type = typename ListViewArrayT::offset_type;
  const int64_t list_view_array_offset = list_view_array.offset();
  const int64_t list_view_array_length = list_view_array.length();
  std::shared_ptr<arrow::Array> value_array = list_view_array.values();

  if (list_view_array_length == 0) {
    return SliceArrayWithOffsets(*value_array, 0, 0);
  }

  // If the list array is *all* nulls, then just return an empty array.
  if constexpr (HasNulls) {
    if (list_view_array.null_count() == list_view_array.length()) {
      return MakeEmptyArray(value_array->type(), memory_pool);
    }
  }

  const auto* validity = list_view_array.data()->template GetValues<uint8_t>(0, 0);
  const auto* offsets = list_view_array.data()->template GetValues<offset_type>(1);
  const auto* sizes = list_view_array.data()->template GetValues<offset_type>(2);

  auto is_null_or_empty = [&](int64_t i) {
    if (HasNulls && !bit_util::GetBit(validity, list_view_array_offset + i)) {
      return true;
    }
    return sizes[i] == 0;
  };

  // Index of the first valid, non-empty list-view.
  int64_t first_i = 0;
  for (; first_i < list_view_array_length; first_i++) {
    if (!is_null_or_empty(first_i)) {
      break;
    }
  }
  // If all list-views are empty, return an empty array.
  if (first_i == list_view_array_length) {
    return MakeEmptyArray(value_array->type(), memory_pool);
  }

  std::vector<std::shared_ptr<Array>> slices;
  {
    int64_t i = first_i;
    auto begin_offset = offsets[i];
    auto end_offset = offsets[i] + sizes[i];
    i += 1;
    // Inductive invariant: slices and the always non-empty values slice
    // [begin_offset, end_offset) contains all the maximally contiguous slices of the
    // values array that are covered by all the list-views before list-view i.
    for (; i < list_view_array_length; i++) {
      if (is_null_or_empty(i)) {
        // The invariant is preserved by simply preserving the current set of slices.
      } else {
        if (offsets[i] == end_offset) {
          end_offset += sizes[i];
          // The invariant is preserved because since the non-empty list-view i
          // starts at end_offset, the current range can be extended to end at