Function ListDistinctHeterogeneousImpl

extensions/lists_functions.cc:72–97

Slow distinct() implementation that uses Equal() to compare values in O(n^2).

// Slow distinct() implementation that uses Equal() to compare values in O(n^2).
absl::Status ListDistinctHeterogeneousImpl(
    const ListValue& list,
    const google::protobuf::DescriptorPool* absl_nonnull descriptor_pool,
    google::protobuf::MessageFactory* absl_nonnull message_factory,
    google::protobuf::Arena* absl_nonnull arena, ListValueBuilder* absl_nonnull builder,
    int64_t start_index = 0, std::vector<Value> seen = {}) {
  CEL_ASSIGN_OR_RETURN(size_t size, list.Size());
  for (int64_t i = start_index; i < size; ++i) {
    CEL_ASSIGN_OR_RETURN(Value value,
                         list.Get(i, descriptor_pool, message_factory, arena));
    bool is_distinct = true;
    for (const Value& seen_value : seen) {
      CEL_ASSIGN_OR_RETURN(Value equal, value.Equal(seen_value, descriptor_pool,
                                                    message_factory, arena));
      if (equal.IsTrue()) {
        is_distinct = false;
        break;
      }
    }
    if (is_distinct) {
      seen.push_back(value);
      CEL_RETURN_IF_ERROR(builder->Add(value));
    }
  }
  return absl::OkStatus();
}

// Fast distinct() implementation for homogeneous hashable types. Falls back to
// the slow implementation if the list is not actually homogeneous.