blob: 7957f5b203ff08ae6c64ce850ce3b0176d3eade9 [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 <cstring>
#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, kMaxValue = kOther };
// // In .cc file:
// template <>
// constexpr EnumTable<MyEnum> EnumTable<MyEnum>::instance({
// {MyEnum::kFoo, "FOO"},
// {MyEnum::kBar, "BAR"},
// ...
// {MyEnum::kOther}, // Not all values need strings.
// },
// MyEnum::kMaxValue); // Needed to detect missing table entries.
// 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.
// Consecutive Enum Tables
// -----------------------
// When using an EnumTable, it's generally best for the following conditions
// to be true:
// - The enum is defined with "enum class" syntax.
// - The members have the default values assigned by the compiler.
// - There is an extra member named kMaxValue which is set equal to the highest
// ordinary value. (The Chromium style checker will verify that kMaxValue
// really is the maximum value.)
// - The values in the EnumTable constructor appear in sorted order.
// - Every member of the enum (other than kMaxValue) is included in the table.
// When these conditions are met, the enum's |kMaxValue| member should be passed
// as the second argument of the EnumTable. This will create a table where enum
// values can be converted to strings in constant time. It will also reliably
// detect an incomplete enum table during startup of a debug build.
// Non-Consecutive Enum Tables
// ---------------------------
// When the conditions in the previous section cannot be satisfied, the second
// argument of the EnumTable constructor should be the special constant
// |NonConsecutiveEnumTable|. Doing so has some unfortunate side-effects: there
// is no automatic way to detect when an enum value is missing from the table,
// and looking up a non-constant enum value requires a linear search.
// 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);
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};
constexpr bool has_str() const { return chars != nullptr; }
// 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, these constructors really needs to be inlined. Even though they look
// "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)
: chars(nullptr), length(UINT32_MAX), value(value) {}
inline constexpr GenericEnumTableEntry::GenericEnumTableEntry(
int32_t value,
base::StringPiece str)
: chars(,
value(value) {}
struct NonConsecutiveEnumTable_t {};
constexpr NonConsecutiveEnumTable_t NonConsecutiveEnumTable;
// 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 data members to this class, or it will break the
// reinterpret_casts below. If necessary, add new members to
// GenericEnumTableEntry instead.
class Entry : public GenericEnumTableEntry {
// Constructor for placeholder entries with no string value.
constexpr Entry(E value)
: GenericEnumTableEntry(static_cast<int32_t>(value)) {}
// Constructor for regular entries.
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.
// If |max_value| is specified, all enum values in |data| must be less than or
// equal to |max_value|. This feature is intended to help catch errors cause
// by a new value being added to an enum without the new value being added to
// the corresponding table. For best results, use an enum class and create a
// constant named kMaxValue. For more details, see
constexpr EnumTable(std::initializer_list<Entry> data, E max_value)
: 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 = FindNonConsecutiveEntry(data);
DCHECK(!found) << "Entries' numerical values must be consecutive "
<< "integers starting from 0; found problem at index "
<< *found;
const auto int_max_value = static_cast<int32_t>(max_value);
DCHECK(data.end()[-1].value == int_max_value)
<< "Missing entry for enum value " << int_max_value;
#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,
: 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];
if (ANALYZER_ASSUME_TRUE(entry.has_str()))
return entry.str();
return base::nullopt;
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) && entry.has_str())
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.has_str() && ej.has_str() && 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> FindNonConsecutiveEntry(
std::initializer_list<Entry> data) {
int32_t counter = 0;
for (const auto& entry : data) {
if (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