blob: e0551953a39129fa3c2d171663e09ed241d47930 [file] [log] [blame]
// Copyright 2019 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include <cstdint>
#include "base/logging.h"
#include "base/optional.h"
#include "base/strings/string_piece.h"
#include "build/build_config.h"
// TODO(jrw): Move this file to a more appropriate directory.
// A bidirectional mapping between enum values and strings.
// Typical Usage
// -------------
// The typical way to use this class is to define a specializtion of
// EnumTable<E>::instance for a specific enum type, which is initialized with
// a table of enum values and their corresponding strings:
// // In .h file:
// enum class MyEnum { kFoo, kBar, ..., kOther };
// // In .cc file:
// template <>
// constexpr EnumTable<MyEnum> EnumTable<MyEnum>::instance({
// {MyEnum::kFoo, "FOO"},
// {MyEnum::kBar, "BAR"},
// ...
// // No entry for kOther because it has no string representation.
// });
// The functions EnumToString() and StringToEnum() are used to look up values
// in the table. In some cases, it may be useful to wrap these functions for
// special handling of unknown values, etc.:
// const char* MyEnumToString(MyEnum value) {
// return EnumToString(value).value_or(nullptr).data();
// }
// MyEnum StringToMyEnum(const std::string& name) {
// return StringToEnum<MyEnum>(name).value_or(MyEnum::kOther);
// }
// NOTE: Because it's a template specialization, the definition of
// EnumTable<E>::instance has to be in the cast_util namespace. Alternatively,
// you can declare your own table with any name you want and call its members
// functions directly.
// To get a the string for an enum value that is known at compile time, there is
// a special zero-argument form of EnumToString(), (and a corresponding member
// function in EnumTable):
// // Compiles to base::StringPiece("FOO").
// EnumToString<MyEnum, MyEnum::kFoo>();
// The syntax is a little awkward, but it saves you from having to duplicate
// string literals or define each enum string as a named constant.
// Why use an EnumTable?
// ---------------------
// If you're only doing one-way conversions from an enum to a string, using an
// EnumTable is almost identical to a switch statement. Typically a switch
// statement that converts an enum value to a string will compile to a simple
// constant-time lookup in a static array, and a call to an EnumTable's
// GetString() method will compile to almost exactly the same code (with one
// additional shlq instruction compared to the switch statement).
// If your enum values are non-consecutive, the GetString() method will perform
// a linear search instead of an array lookup. The search should be competitve
// in performance with a switch statement in this case. To avoid getting this
// sub-optimal behavior by accident, you must explicitly request it with an
// extra argument to EnumTable's constructor. If you don't do this, failure to
// put the values in the correct order will cause your unit tests to fail on
// startup with a decriptive error message.
// EnumTable really shines when you need to convert strings to enum values. A
// typical implementation without EnumTable looks like this:
// constexpr char kMyEnumFooString[] = "FOO";
// constexpr char kMyEnumBarString[] = "BAR";
// ...
// MyEnum StringToMyEnum(const std::string& str) {
// if (str == kMyEnumFooString) return MyEnum::kFoo;
// if (str == kMyEnumBarString) return MyEnum::kBar;
// ...
// return kOther;
// }
// If you roll your own solution, you can't do much better than this without
// jumping through some hoops. Obvious improvements, like storing the data in a
// global base::flat_map, are off-limits because Chromium requires all global
// variables to have trivial destructors. A simple chain of "if" statements
// works fine, but it has a number of drawbacks compared to an EnumTable:
// - You have to write and maintain a function separate from the one that
// converts enum values to strings. With an EnumTable, a single declaration
// lets you convert in both directions.
// - Since you will almost certainly be using the strings in more than one
// place, you have to either define a named constant for each one, or live
// with the fact that the string literals are duplicated, causing maintenance
// headaches. With an EnumTable, each string naturally appears in only one
// place, so there's no need for supplementary named constants. When you need
// to refer to the string for a particular enum value, you can get it directly
// from the table at compile time using the zero-argument EnumToString()
// function or the zero-argument EnumTable<E>::ToString() method.
// - If you want to follow best practices, you'll need to write unit tests for
// your functions that convert between strings and enums. When you use an
// EnumTable, you don't write any functions, so there's nothing to test; all
// the necessary testing is done by EnumTable's own unit tests.
// - The conversion function is essentially a fully-unrolled linear search
// through all the possible string values. This bloats your code and causes
// unnecessary churn in the instruction cache. Using an EnumTable, this
// search is compiled into a single loop shared by all enums, which the
// compiler can unroll, or not, as appropriate. On 64-bit platforms, the main
// table uses only 16 bytes per entry, so memory locality is excellent and
// impact on the data cache is minimal.
// - The hand-written function performs a function call for each candidate
// string. EnumTable's search loop compares the lengths of the strings before
// doing anything else, so most iterations don't call any functions and don't
// access any memory aside from the lookup table itself.
// - If you accidentally duplicate any lines in the function, you're on your
// own. EnumTable detects duplicate strings on startup (in debug builds), so
// you'll never accidentally try to map a string to two different enum values.
namespace cast_util {
#ifdef ARCH_CPU_64_BITS
GenericEnumTableEntry {
inline constexpr GenericEnumTableEntry(int32_t value, base::StringPiece str);
static const GenericEnumTableEntry* FindByString(
const GenericEnumTableEntry data[],
std::size_t size,
base::StringPiece str);
static base::Optional<base::StringPiece>
FindByValue(const GenericEnumTableEntry data[], std::size_t size, int value);
constexpr base::StringPiece str() const { return {chars, length}; }
// Instead of storing a base::StringPiece, it's broken apart and stored as a
// pointer and an unsigned int (rather than a std::size_t) so that table
// entries fit in 16 bytes with no padding on 64-bit platforms.
const char* chars;
uint32_t length;
int32_t value;
template <typename E>
friend class EnumTable;
// Yes, this really needs to be inlined. Even though it looks "complex" to the
// style checker, everything is executed at compile time, so an EnumTable
// instance can be fully initialized without executing any code.
inline constexpr GenericEnumTableEntry::GenericEnumTableEntry(
int32_t value,
base::StringPiece str)
: chars(,
value(value) {}
struct UnsortedEnumTable_t {};
constexpr UnsortedEnumTable_t UnsortedEnumTable;
// A table for associating enum values with string literals. This class is
// designed for use as an initialized global variable, so it has a trivial
// destructor and a simple constant-time constructor.
template <typename E>
class EnumTable {
// DO NOT add any members to this class, or it will break the
// reinterpret_casts below. If necessary, add new members to
// GenericEnumTableEntry instead.
class Entry : public GenericEnumTableEntry {
constexpr Entry(E value, base::StringPiece str)
: GenericEnumTableEntry(static_cast<int32_t>(value), str) {}
static_assert(sizeof(E) <= sizeof(int32_t),
"Enum must not use more than 32 bits of storage.");
static_assert(sizeof(Entry) == sizeof(GenericEnumTableEntry),
"EnumTable<E>::Entry must not have its own member variables.");
// Creates an EnumTable where data[i].value == i for all i. When a table is
// created with this constructor, the GetString() method is a simple array
// lookup that runs in constant time.
constexpr EnumTable(std::initializer_list<Entry> data)
: EnumTable(data, true) {
#ifndef NDEBUG
// NOTE(jrw): This is compiled out when NDEBUG is defined, even if DCHECKS
// are normally enabled because DCHECK_ALWAYS_ON is defined. The reason for
// this is that if DCHECKs are enabled, global EnumTable instances will have
// a nontrivial constructor, which is flagged as a style violation by the
// linux-rel trybot.
auto found = FindUnsortedEntry(data);
DCHECK(!found) << "Entries' numerical values must be consecutive "
<< "integers starting at 0; found problem at index "
<< *found;
#endif // NDEBUG
// Creates an EnumTable where data[i].value != i for some values of i. When
// a table is created with this constructor, the GetString() method must
// perform a linear search to find the correct string.
constexpr EnumTable(std::initializer_list<Entry> data, UnsortedEnumTable_t)
: EnumTable(data, false) {
#ifndef NDEBUG
<< "Don't use this constructor for sorted entries.";
#endif // NDEBUG
// Gets the string associated with the given enum value. When the argument
// is a constant, prefer the zero-argument form below.
inline base::Optional<base::StringPiece> GetString(E value) const {
if (is_sorted_) {
const std::size_t index = static_cast<std::size_t>(value);
if (ANALYZER_ASSUME_TRUE(index < data_.size())) {
const auto& entry = data_.begin()[index];
return entry.str();
return {};
return GenericEnumTableEntry::FindByValue(
reinterpret_cast<const GenericEnumTableEntry*>(data_.begin()),
data_.size(), static_cast<int32_t>(value));
// This overload of GetString is designed for cases where the argument is a
// literal value. It will be evaluated at compile time in non-debug builds.
// If |Value| has no string defined in the table, you'll get an error at
// runtime in debug builds, but in release builds this function will just
// return a string holding an error message. Unfortunately it doesn't seem
// possible to report an error in evaluating a constexpr function at compile
// time without using exceptions.
template <E Value>
constexpr base::StringPiece GetString() const {
for (const auto& entry : data_) {
if (entry.value == static_cast<int32_t>(Value))
return entry.str();
NOTREACHED() << "No string for enum value: " << static_cast<int32_t>(Value);
return "[invalid enum value]";
// Gets the enum value associated with the given string. Unlike
// GetString(), this method is not defined as a constexpr, because it should
// never be called with a literal string; it's simpler to just refer to the
// enum value directly.
base::Optional<E> GetEnum(base::StringPiece str) const {
auto* entry = GenericEnumTableEntry::FindByString(
reinterpret_cast<const GenericEnumTableEntry*>(data_.begin()),
data_.size(), str);
return entry ? static_cast<E>(entry->value) : base::Optional<E>();
// The default instance of this class. There should normally only be one
// instance of this class for a given enum type. Users of this class are
// responsible for providing a suitable definition for each enum type if the
// EnumToString() or StringToEnum() functions are used.
static const EnumTable<E> instance;
#ifdef ARCH_CPU_64_BITS
// Align the data on a cache line boundary.
std::initializer_list<Entry> data_;
bool is_sorted_;
constexpr EnumTable(std::initializer_list<Entry> data, bool is_sorted)
: data_(data), is_sorted_(is_sorted) {
#ifndef NDEBUG
// If the table is too large, it's probably time to update this class to do
// something smarter than a linear search.
DCHECK(data.size() <= 32) << "Table too large.";
for (std::size_t i = 0; i < data.size(); i++) {
for (std::size_t j = i + 1; j < data.size(); j++) {
const Entry& ei = data.begin()[i];
const Entry& ej = data.begin()[j];
DCHECK(ei.value != ej.value)
<< "Found duplicate enum values at indices " << i << " and " << j;
DCHECK(ei.str() != ej.str())
<< "Found duplicate strings at indices " << i << " and " << j;
#endif // NDEBUG
#ifndef NDEBUG
// Finds and returns the first i for which data[i].value != i;
constexpr static base::Optional<std::size_t> FindUnsortedEntry(
std::initializer_list<Entry> data) {
std::size_t counter = 0;
for (const auto& entry : data) {
if (static_cast<std::size_t>(entry.value) != counter) {
return counter;
return {};
#endif // NDEBUG
// Converts an enum value to a string using the default table
// (EnumTable<E>::instance) for the given enum type.
template <typename E>
inline base::Optional<base::StringPiece> EnumToString(E value) {
return EnumTable<E>::instance.GetString(value);
// Converts a literal enum value to a string at compile time using the default
// table (EnumTable<E>::instance) for the given enum type.
// TODO(jrw): Once C++17 features are allowed, change this function to have only
// one template parameter:
// template <auto Value>
// inline base::StringPiece EnumToString() {
// return EnumTable<decltype(Value)>::instance.template GetString<Value>();
// }
template <typename E, E Value>
inline base::StringPiece EnumToString() {
return EnumTable<E>::instance.template GetString<Value>();
// Converts a string to an enum value using the default table
// (EnumTable<E>::instance) for the given enum type.
template <typename E>
inline base::Optional<E> StringToEnum(base::StringPiece str) {
return EnumTable<E>::instance.GetEnum(str);
} // namespace cast_util