src/google/protobuf/generated_enum_util.cc

// Protocol Buffers - Google's data interchange format
// Copyright 2008 Google Inc.  All rights reserved.
//
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file or at
// https://developers.google.com/open-source/licenses/bsd

#include "google/protobuf/generated_enum_util.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <utility>
#include <vector>

#include "absl/log/absl_check.h"
#include "absl/types/optional.h"
#include "absl/types/span.h"
#include "google/protobuf/generated_message_util.h"

// Must be included last.
#include "google/protobuf/port_def.inc"

namespace google {
namespace protobuf {
namespace internal {
namespace {

bool EnumCompareByName(const EnumEntry& a, const EnumEntry& b) {
  return absl::string_view(a.name) < absl::string_view(b.name);
}

// Gets the numeric value of the EnumEntry at the given index, but returns a
// special value for the index -1. This gives a way to use std::lower_bound on a
// sorted array of indices while searching for value that we associate with -1.
int GetValue(const EnumEntry* enums, int i, int target) {
  if (i == -1) {
    return target;
  } else {
    return enums[i].value;
  }
}

}  // namespace

bool LookUpEnumValue(const EnumEntry* enums, size_t size,
                     absl::string_view name, int* value) {
  EnumEntry target{name, 0};
  auto it = std::lower_bound(enums, enums + size, target, EnumCompareByName);
  if (it != enums + size && it->name == name) {
    *value = it->value;
    return true;
  }
  return false;
}

int LookUpEnumName(const EnumEntry* enums, const int* sorted_indices,
                   size_t size, int value) {
  auto comparator = [enums, value](int a, int b) {
    return GetValue(enums, a, value) < GetValue(enums, b, value);
  };
  auto it =
      std::lower_bound(sorted_indices, sorted_indices + size, -1, comparator);
  if (it != sorted_indices + size && enums[*it].value == value) {
    return it - sorted_indices;
  }
  return -1;
}

bool InitializeEnumStrings(
    const EnumEntry* enums, const int* sorted_indices, size_t size,
    internal::ExplicitlyConstructed<std::string>* enum_strings) {
  for (size_t i = 0; i < size; ++i) {
    enum_strings[i].Construct(enums[sorted_indices[i]].name);
    internal::OnShutdownDestroyString(enum_strings[i].get_mutable());
  }
  return true;
}

bool ValidateEnum(int value, const uint32_t* data) {
  return ValidateEnumInlined(value, data);
}

struct EytzingerLayoutSorter {
  absl::Span<const int32_t> input;
  absl::Span<uint32_t> output;
  size_t i;

  // This is recursive, but the maximum depth is log(N), so it should be safe.
  void Sort(size_t output_index = 0) {
    if (output_index < input.size()) {
      Sort(2 * output_index + 1);
      output[output_index] = input[i++];
      Sort(2 * output_index + 2);
    }
  }
};

std::vector<uint32_t> GenerateEnumData(absl::Span<const int32_t> values) {
  const auto sorted_and_unique = [&] {
    for (size_t i = 0; i + 1 < values.size(); ++i) {
      if (values[i] >= values[i + 1]) return false;
    }
    return true;
  };
  ABSL_DCHECK(sorted_and_unique());
  std::vector<int32_t> fallback_values_too_large, fallback_values_after_bitmap;
  std::vector<uint32_t> bitmap_values;
  constexpr size_t kBitmapBlockSize = 32;
  absl::optional<int16_t> start_sequence;
  uint32_t sequence_length = 0;
  for (int32_t v : values) {
    // If we don't yet have a sequence, start it.
    if (!start_sequence.has_value()) {
      // But only if we can fit it in the sequence.
      if (static_cast<int16_t>(v) != v) {
        fallback_values_too_large.push_back(v);
        continue;
      }

      start_sequence = v;
      sequence_length = 1;
      continue;
    }
    // If we can extend the sequence, do so.
    if (v == static_cast<int32_t>(*start_sequence) +
                 static_cast<int32_t>(sequence_length) &&
        sequence_length < 0xFFFF) {
      ++sequence_length;
      continue;
    }

    // We adjust the bitmap values to be relative to the end of the sequence.
    const auto adjust = [&](int32_t v) -> uint32_t {
      // Cast to int64_t first to avoid overflow. The result is guaranteed to be
      // positive and fit in uint32_t.
      int64_t a = static_cast<int64_t>(v) - *start_sequence - sequence_length;
      ABSL_DCHECK(a >= 0);
      ABSL_DCHECK_EQ(a, static_cast<uint32_t>(a));
      return a;
    };
    const uint32_t adjusted = adjust(v);

    const auto add_bit = [&](uint32_t bit) {
      bitmap_values[bit / kBitmapBlockSize] |= uint32_t{1}
                                               << (bit % kBitmapBlockSize);
    };

    // If we can fit it on the already allocated bitmap, do so.
    if (adjusted < kBitmapBlockSize * bitmap_values.size()) {
      // We can fit it in the existing bitmap.
      ABSL_DCHECK_EQ(fallback_values_after_bitmap.size(), 0);
      add_bit(adjusted);
      continue;
    }

    // We can't fit in the sequence and we can't fit in the current bitmap.
    // Evaluate if it is better to add to fallback, or to collapse all the
    // fallback values after the bitmap into the bitmap.
    const size_t cost_if_fallback =
        bitmap_values.size() + (1 + fallback_values_after_bitmap.size());
    const size_t rounded_bitmap_size =
        (adjusted + kBitmapBlockSize) / kBitmapBlockSize;
    const size_t cost_if_collapse = rounded_bitmap_size;

    if (cost_if_collapse <= cost_if_fallback &&
        kBitmapBlockSize * rounded_bitmap_size < 0x10000) {
      // Collapse the existing values, and add the new one.
      ABSL_DCHECK_GT(rounded_bitmap_size, bitmap_values.size());
      bitmap_values.resize(rounded_bitmap_size);
      for (int32_t to_collapse : fallback_values_after_bitmap) {
        add_bit(adjust(to_collapse));
      }
      fallback_values_after_bitmap.clear();
      add_bit(adjusted);
    } else {
      fallback_values_after_bitmap.push_back(v);
    }
  }

  std::vector<int32_t> fallback_values;
  if (fallback_values_after_bitmap.empty()) {
    fallback_values = std::move(fallback_values_too_large);
  } else if (fallback_values_too_large.empty()) {
    fallback_values = std::move(fallback_values_after_bitmap);
  } else {
    fallback_values.resize(fallback_values_too_large.size() +
                           fallback_values_after_bitmap.size());
    std::merge(fallback_values_too_large.begin(),
               fallback_values_too_large.end(),
               fallback_values_after_bitmap.begin(),
               fallback_values_after_bitmap.end(), &fallback_values[0]);
  }

  std::vector<uint32_t> output(
      2 /* seq start + seq len + bitmap len + ordered len */ +
      bitmap_values.size() + fallback_values.size());
  uint32_t* p = output.data();

  ABSL_DCHECK_EQ(sequence_length, static_cast<uint16_t>(sequence_length));
  *p++ = uint32_t{static_cast<uint16_t>(start_sequence.value_or(0))} |
         (uint32_t{sequence_length} << 16);
  ABSL_DCHECK_EQ(
      kBitmapBlockSize * bitmap_values.size(),
      static_cast<uint16_t>(kBitmapBlockSize * bitmap_values.size()));
  ABSL_DCHECK_EQ(fallback_values.size(),
                 static_cast<uint16_t>(fallback_values.size()));
  *p++ = static_cast<uint32_t>(kBitmapBlockSize * bitmap_values.size()) |
         static_cast<uint32_t>(fallback_values.size() << 16);
  p = std::copy(bitmap_values.begin(), bitmap_values.end(), p);

  EytzingerLayoutSorter{fallback_values,
                        absl::MakeSpan(p, fallback_values.size())}
      .Sort();

  return output;
}

}  // namespace internal
}  // namespace protobuf
}  // namespace google