学习LLVM数据结构：StringRef

在现代 C++ 程序开发中，选择合适的数据结构，对于程序性能和内存安全都至关重要。LLVM 项目中，有一大块内容便是设计用于内部开发的高效数据结构。

本文将以 cppreference 的格式，介绍这些实用的数据结构。你既可以将其作为学习参考，也可以作为学习 LLVM 的补充材料。

基本介绍

llvm::StringRef 定义在 llvm/ADT/StringRef.h 头文件中。它的声明为：

1	class StringRef;

和 ArrayRef 类似，StringRef 是一种轻量级的字符串引用类型，它用于实现高效地表示和操作字符串数据，尤其是在一些高频处理字符串，但同时不希望维护实际内存开销地场景下。它是不可变引用，主要用于向函数内传递字符串同时避免深拷贝。它只包含了指向字符串的指针和字符串的长度信息，从而使得对它的操作直接而高效。

特点

轻量级：只存储一个指向字符串的指针和字符串的长度，不存储实际的数据，所以拷贝时很高效。
简单易用：支持许多常用的字符串操作，比如比较、查找和子串提取，使用很方便。
操作一致：它的大多数操作，和标准库中 string 保持一致。

与标准库 string 对比

所有权：StringRef 是对字符串数据的引用，不拥有字符串的所有权。需要确保 StringRef 对象的生命周期，小于实际引用字符串的生命周期，否则会带来悬空引用。
大小：StringRef 只占用很小的内存，和实际字符串相比可以忽略不计。std::string 不仅包括了指针、长度，还包括了数据的内存管理信息，它在内部维护了一个动态分配的缓存区来存储字符串内容。
可变性：StringRef 是不可变的，它引用的内容不能被修改。而 std::string 则提供了完整的可操作空间。
性能：StringRef 不涉及内存分配，在传递和使用时，具有更高的性能，特别是在函数传参时，可以避免深拷贝。而 std::string 在按值传参时，会对保存字符串的内存做完整的复制。现在编译器可以通过移动语义和短字符串优化等方式来减少深拷贝的性能开销，但整体上，传递引用还是要更轻量级。

数据成员

由于 llvm::StringRef 只拥有数据的引用，而不管理实际字符串的内存，所以它的结构很简单。

class StringRef {
private:
  const char *data = nullptr;
  size_t length = 0;
};

成员方法

事实上，使用 const std::string & 基本可以取代 llvm::StringRef，然而，StringRef 的另一个优势是，它提供了更多更易用的操作方法，比如 split 函数。

构造

StringRef 可以方便地从字符串字面量、std::string 或 char * 指针来初始化。

// 从字符串字面量初始化
llvm::StringRef Str1 = "abc";

// 从字符串指针和长度来初始化
char *Cstr = "abc";
llvm::StringRef Str2{Cstr, 3};

// 从 std::string 来初始化
std::string Sstr{"abc"};
llvm::StringRef Str3{Sstr};

迭代器

提供了迭代器 begin() 和 end()，以及返回字符指针的 bytes_begin() 和 bytes_end()，这是为了处理宽字符编码的字符串。

元素访问

// 拿到字符串原始位置
const char *Data = Str.data();

// 拿到字符串的长度
bool IsEmpty = Str.empty();
size_t Length = Str.size();

// 访问首尾元素
const char FirstChar = Str.front();
const char LastChar = Str.back();

// 也支持任意的下标操作，越界用 assert 来检查
const char C = Str[1];

比较

llvm::StringRef Str1, Str2;

// 判断是否相等
bool IsEqual1 = Str1.equals(Str2);
bool IsEqual2 = Str1 == Str2;
bool IsEqual3 = Str1.equals_insensitive(Str2);  // 忽略大小写
// 其他操作也有忽略大小写的版本，不再单独列出

// 判断大小，当结果小于、等于、大于时，值是 -1、0、1
int Cmp1 = Str1.compare(Str2);
int Cmp2 = Str1.compare_insensitive(Str2);  // 忽略大小写
int Cmp3 = Str1.compare_numeric(Str2);  // 由数字字符组成的字符串，按数字来比较

编辑距离

编辑距离（edit distance）是指将一个字符串完全改为另一个字符串时，所需要的最小单字符操作的次数。这些操作可以是： - 插入一个字符 - 删除一个字符 - 替换一个字符（分为将替换看作一次操作，还是看作两次操作）

llvm::StringRef Str1, Str2;

int Distance1 = Str1.edit_distance(Str2);
int Distance2 = Str1.edit_distance_insensitive(Str2);  // 忽略大小写

// 有两个隐藏参数，第一个是替换被看作几次，默认是 1 次操作
bool AllowReplacements = true;
// 第二个是最大编辑距离，如果编辑距离超过最大编辑距离，则返回最大编辑距离+1
bool MaxEditDistance = 0;
int Distance3 = Str1.edit_distance(Str2, AllowReplacements, MaxEditDistance);

获取副本

使用 str() 来获取一个 std::string 类型的副本。使用 string_view() 来获取一个 std::string_view 类型的副本。同时，也提供了 copy 函数，来获取一个 StringRef 的副本，但需要提供分配器，用于分配新的空间：

#include <memory>  // 包含 std::allocator
#include "llvm/Support/BumpPtrAllocator.h"  // 包含 BumpPtrAllocator

llvm::StringRef Str;

// 使用 C++ 的内存分配器
std::allocator<char> Alloc;
llvm::StringRef NewStr1 = Str.copy(ALloc);

// 使用 LLVM 的内存分配器
llvm::BumpPtrAllocator BumpAlloc;
llvm::StringRef NewStr2 = Str.copy(BumpAlloc);

// 也可以自定义分配器，需要提供 Allocate<> 模板方法
// 使用时，需要确保分配器对象的生命周期超过 StringRef 对象，否则会带来引用失效问题

检查

llvm::StringRef Str;

// 检查字符串是否开始于一个特定前缀字符
bool Ret1 = Str.starts_with('a');
bool Ret2 = Str.startswith('a');  // 语法糖

// 检查字符串是否结束于一个特定后缀字符
bool Ret3 = Str.ends_with('z');
bool Ret4 = Str.endswith('z');  // 语法糖

查找

llvm::StringRef Str;

// 常规查找，返回下标位置，内部调用了 std::string_view::find()，当找不到时，返回 StringRef::npos，其值是 ~size_t(0)
size_t Ret1 = Str.find('m');
// 第二个隐藏参数是从什么位置开始查，默认是从 0（字符串开头）开始查

// 给定查找条件
size_t Ret2 = Str.find_if([](char c) { return c > 'r' && c < 'x'; });
// 还有取反的 find_if_not

// 反向查找
size_t Ret3 = Str.rfind('m');

// 查找是否包含特定字符
bool IsContain = Str.contains('m');
// 查找是否包含特定子串
llvm::StringRef SubStr;
bool IsContainsSubStr = Str.contains(SubStr);

辅助函数

llvm::StringRef Str;

// 计数特定字符出现的次数
size_t Cnt = Str.count('m');

// 将由数字字符组成的字符串，转换为整型，第一个参数是选择进制，置为 0 表示按 C 整形规则自动选择进制。若转换失败，会返回 true。
int Res;
Str.getAsInteger(0, Res);

// 和 getAsInteger 类似，但会剔除开头的数字部分，如果开头不是数字，返回 true 表示失败。
// 实际上，是修改了指针位置，并没有改变字符串
Str.consumeInteger(0, Res);

// 将字符串按大小写转换，并返回 std::string 类型
std::string LowerStr = Str.lower();
std::string UpperStr = Str.upper();

切片

// 截取子字符串的操作，实际上是修改指针指向位置和长度的结果
llvm::StringRef Str;

llvm::StringRef SubStr1 = Str.substr(2, 3);  // 截取从 2 下标开始，长度为 3 的子串

// 返回前 N 个字符的子串
llvm::StringRef SubStr2 = Str.take_front(3);
// 删除前 N 个字符，返回剩余字符的子串，是 drop_front

// 返回后 N 个字符的子串
llvm::StringRef SubStr3 = Str.take_back(3);
// 同理，返回剩余字符的子串，是 drop_back

// 如果以给定前缀开头，删除该前缀，返回剩余字符子串
Str.consume_front("prefix");  // 在原始引用上操作
// 同理，还有给定后缀的 consume_back()

// 截取任意子串
llvm::StringRef SubStr4 = Str.slice(1, 3);  // 截取从 1 下标到 3 下标的子串

// split 操作，即按给定字符来分割子串
std::pair<llvm::StringRef, llvm::StringRef> SubStrPair1 = Str.split(':');  // 分成两个子串
llvm::StringRef SeparatorStr = "::";
std::pair<llvm::StringRef, llvm::StringRef> SubStrPair2 = Str.split(SeparatorStr);  // 使用给定子字符串分隔子串
std::pair<llvm::StringRef, llvm::StringRef> SubStrPair3 = Str.rsplit(SeparatorStr);  // 从末尾开始搜索分隔符

// split 操作，所有都分隔
llvm::SmallVector<llvm::StringRef> SplitStrs;
Str.split(SplitStrs, "::");

// trim 操作
llvm::StringRef TrimStr1 = Str.ltrim('\0');  // 切掉左侧连续多个 '\0' 字符
llvm::StringRef TrimStr2 = Str.ltrim();  // 切掉左侧连续多个空白字符
// 对应还有右侧版 rtrim 和 两侧版 trim

// 检测是否包含 EOL 字符，EOL 字符是 end of line 标记
bool HasEOLStr = Str.detactEOL();

注意事项

引用失效

和 llvm::ArrayRef 一样，llvm::StringRef 本身是一个引用类型，所以它会存在引用失效的风险。另外，也不建议直接返回一个内部临时对象引用的 llvm::StringRef 类型，可以返回经过调整，但指向外部字符串的新的 llvm::StirngRef 类型。它的生命周期一定要短于它所引用的字符串的生命周期，从而避免悬挂引用。