Function ListDistinct

extensions/lists_functions.cc:132–188

}

absl::StatusOr<Value> ListDistinct(
    const ListValue& list,
    const google::protobuf::DescriptorPool* absl_nonnull descriptor_pool,
    google::protobuf::MessageFactory* absl_nonnull message_factory,
    google::protobuf::Arena* absl_nonnull arena) {
  CEL_ASSIGN_OR_RETURN(size_t size, list.Size());
  // If the list is empty or has a single element, we can return it as is.
  if (size < 2) {
    return list;
  }

  // We need a set to keep track of the seen values.
  //
  // By default, for unhashable types, this set is implemented as a vector of
  // all the seen values, which means that we will perform O(n^2) comparisons
  // between the values.
  //
  // For efficiency purposes, if the first element of the list is hashable, we
  // will use a specialized implementation that is faster for homogeneous lists
  // of hashable types.
  // If the list is not homogeneous, we will fall back to the slow
  // implementation.
  //
  // The total runtime cost is O(n) for homogeneous lists of hashable types, and
  // O(n^2) for all other cases.
  auto builder = NewListValueBuilder(arena);
  CEL_ASSIGN_OR_RETURN(Value first,
                       list.Get(0, descriptor_pool, message_factory, arena));
  switch (first.kind()) {
    case ValueKind::kInt: {
      CEL_RETURN_IF_ERROR(ListDistinctHomogeneousHashableImpl<IntValue>(
          list, descriptor_pool, message_factory, arena, builder.get()));
      break;
    }
    case ValueKind::kUint: {
      CEL_RETURN_IF_ERROR(ListDistinctHomogeneousHashableImpl<UintValue>(
          list, descriptor_pool, message_factory, arena, builder.get()));
      break;
    }
    case ValueKind::kBool: {
      CEL_RETURN_IF_ERROR(ListDistinctHomogeneousHashableImpl<BoolValue>(
          list, descriptor_pool, message_factory, arena, builder.get()));
      break;
    }
    case ValueKind::kString: {
      CEL_RETURN_IF_ERROR(ListDistinctHomogeneousHashableImpl<StringValue>(
          list, descriptor_pool, message_factory, arena, builder.get()));
      break;
    }
    default: {
      CEL_RETURN_IF_ERROR(ListDistinctHeterogeneousImpl(
          list, descriptor_pool, message_factory, arena, builder.get()));
      break;
    }
  }
  return std::move(*builder).Build();
}