第 19 章：字符串（Strings）

原文：Robert Nystrom, Crafting Interpreters, Chapter 19。原书以 CC BY-NC-SA 4.0 协议发布；本译文用于学习与研究。

啊？对琐碎劳动有一点厌恶？医生扬起了眉毛。可以理解，却放错了位置。人应珍视那些让身体忙碌、却让心灵和情感不受拘束的单调工作。

Tad Williams，《龙骨椅》

VM 目前能表示数字、布尔值和 nil。它们都不可变且很小，最大的数字也能装进两个 64 位字。字符串却没有长度上限；即便人为限制在 255 个字符，仍不能让每一个 Value 都预留如此大空间。早期 UCSD Pascal 的字符串在开头用一个字节保存长度，因此正有 255 字符上限：

以长度字节 5 开头的 Pascal 字符串 hello。

可变大小值适合在堆上动态分配，VM 只在 Value 中保存指向该内存的指针。

19.1 值与对象（Values and Objects）

小而固定大小的值直接存入 Value；更大的可变对象存于堆，Value 负载则是指针。将来字符串、实例、函数等都会如此。每类对象有不同负载，却也有供垃圾收集器使用的共同状态。所有堆分配值统称 Obj，只需一个新的 ValueType：

// value.h
typedef struct Obj Obj;

typedef enum {
  VAL_BOOL,
  VAL_NIL,
  VAL_NUMBER,
  VAL_OBJ,
} ValueType;

typedef struct {
  ValueType type;
  union {
    bool boolean;
    double number;
    Obj* obj;
  } as;
} Value;

数值和对象 Value 的字段布局。

和其他值类型一样，提供断言、解包与包装宏：

#define IS_OBJ(value)     ((value).type == VAL_OBJ)
#define AS_OBJ(value)     ((value).as.obj)
#define OBJ_VAL(object)   ((Value){VAL_OBJ, {.obj = (Obj*)object}})

19.2 结构体继承（Struct Inheritance）

每个堆对象都是 Obj，但不同对象类型的大小和字段不同：字符串有字符数组，实例有字段，函数有字节码 chunk。不能为所有负载再建一个巨大 union；改用一种 C 支持的类型重解释技巧，本书称之为结构体继承。

Obj 类似对象的基类，因与 Value 相互依赖，先在 value.h 前置声明，真正定义位于新模块：

// object.h
typedef enum {
  OBJ_STRING,
} ObjType;

struct Obj {
  ObjType type;
};

#define OBJ_TYPE(value) (AS_OBJ(value)->type)

字符串对象把 Obj 作为第一个字段，再放自身负载：

typedef struct ObjString ObjString;

struct ObjString {
  Obj obj;
  int length;
  char* chars;
};

字符数组也在堆上单独分配，只占实际所需空间；显式 length 让我们无需扫描 NUL 终止符来得知分配大小。

Obj 与 ObjString 字段的内存布局。

C 保证结构体字段按声明顺序排列，嵌套结构体会就地展开，因此 ObjString 开头的字节与 Obj 完全对齐。故可安全将 ObjString* 转成 Obj*，以统一访问类型标签；反向向下转换前，则必须确认 Obj 确实指向某个 ObjString。

static inline bool isObjType(Value value, ObjType type) {
  return IS_OBJ(value) && AS_OBJ(value)->type == type;
}

#define IS_STRING(value)  isObjType(value, OBJ_STRING)
#define AS_STRING(value)  ((ObjString*)AS_OBJ(value))
#define AS_CSTRING(value) (((ObjString*)AS_OBJ(value))->chars)

这里 IS_STRING 不直接用宏展开函数体，因为 value 会在宏体中出现两次。若调用 IS_STRING(pop())，展开后会弹两次栈；内联函数保证实参只求值一次。

19.3 字符串（Strings）

扫描器已经产生 TOKEN_STRING，在 Pratt 表中注册前缀函数：

[TOKEN_STRING] = {string, NULL, PREC_NONE},

字符串 token 的词素包含引号。编译时剔除两端引号，复制内部字符，包装为对象 Value 并写入常量表：

static void string() {
  emitConstant(OBJ_VAL(copyString(parser.previous.start + 1,
                                  parser.previous.length - 2)));
}

Lox 没有转义序列；若存在，应在这里翻译。copyString() 分配并拥有字符数组：

// memory.h
#define ALLOCATE(type, count) \
    (type*)reallocate(NULL, 0, sizeof(type) * (count))

// object.c
ObjString* copyString(const char* chars, int length) {
  char* heapChars = ALLOCATE(char, length + 1);
  memcpy(heapChars, chars, length);
  heapChars[length] = '\0';
  return allocateString(heapChars, length);
}

词素只是整份源字符串中的一个范围，不以 NUL 结尾；额外的一个字节使我们可调用要求 C 字符串的标准库函数。字面量也要复制到堆，而不能仅指向源代码：运行时字符串操作也会动态分配字符，所有 ObjString 若统一拥有自己的字符数组，释放策略才可靠。

创建对象的辅助函数相当于构造器：

#define ALLOCATE_OBJ(type, objectType) \
    (type*)allocateObject(sizeof(type), objectType)

static Obj* allocateObject(size_t size, ObjType type) {
  Obj* object = (Obj*)reallocate(NULL, 0, size);
  object->type = type;
  return object;
}

static ObjString* allocateString(char* chars, int length) {
  ObjString* string = ALLOCATE_OBJ(ObjString, OBJ_STRING);
  string->length = length;
  string->chars = chars;
  return string;
}

中提琴：原书借 voila 与 viola 的拼写相近开了个玩笑。

19.4 字符串上的操作（Operations on Strings）

printValue() 遇到堆对象时交给对象模块：

// value.c
case VAL_OBJ: printObject(value); break;

// object.c
void printObject(Value value) {
  switch (OBJ_TYPE(value)) {
    case OBJ_STRING:
      printf("%s", AS_CSTRING(value));
      break;
  }
}

字符串相等应为值相等，不是指针相等。两个相同字面量会创建两个不同对象，却应使 "string" == "string" 为真：

case VAL_OBJ: {
  ObjString* aString = AS_STRING(a);
  ObjString* bString = AS_STRING(b);
  return aString->length == bString->length &&
      memcmp(aString->chars, bString->chars, aString->length) == 0;
}

这比标量比较慢，因为可能遍历整个字符串；后续会优化。当前只有 OBJ_STRING，对象分支可直接假定两个对象都是字符串，之后新增对象类型时需先比较对象类型。

19.4.1 拼接（Concatenation）

完整语言会有索引、长度、大小写、分割、查找等字符串操作；本书只让 + 拼接两个字符串。动态语言无法在编译期知道操作数类型，OP_ADD 必须运行时检查：

case OP_ADD: {
  if (IS_STRING(peek(0)) && IS_STRING(peek(1))) {
    concatenate();
  } else if (IS_NUMBER(peek(0)) && IS_NUMBER(peek(1))) {
    double b = AS_NUMBER(pop());
    double a = AS_NUMBER(pop());
    push(NUMBER_VAL(a + b));
  } else {
    runtimeError("Operands must be two numbers or two strings.");
    return INTERPRET_RUNTIME_ERROR;
  }
  break;
}

它比不少语言保守：一边是字符串、另一边是其他类型时，Lox 不会隐式转字符串。该功能本身合理，但需要每种类型的转换代码，本书选择不引入。

拼接计算长度，分配结果字符数组，依次复制两个部分并终止；takeString() 接管已分配的数组，避免再复制一次：

static void concatenate() {
  ObjString* b = AS_STRING(pop());
  ObjString* a = AS_STRING(pop());

  int length = a->length + b->length;
  char* chars = ALLOCATE(char, length + 1);
  memcpy(chars, a->chars, a->length);
  memcpy(chars + a->length, b->chars, b->length);
  chars[length] = '\0';

  ObjString* result = takeString(chars, length);
  push(OBJ_VAL(result));
}

ObjString* takeString(char* chars, int length) {
  return allocateString(chars, length);
}

copyString() 假定调用方仍拥有字符数组，所以保守地复制；字符串字面量确实如此。takeString() 则宣告对象接管调用方刚在堆上分配的数组。memcpy() 需要 string.h，而 ALLOCATE、对象操作还需要相应的 memory.h、object.h 引用。

19.5 释放对象（Freeing Objects）

观察 "st" + "ri" + "ng"：三个字面量与中间结果 "stri" 都在堆上分配。最后一次拼接后 "stri" 已从栈弹出且没有引用，却未被释放，这是内存泄漏。用户程序不应手动释放中间字符串，自动内存管理的责任落在 VM 上。

最终方案是程序运行时回收不可达对象的垃圾收集器。拖到语言实现很大后才加 GC 极其困难，因为收集器必须找到每一个仍在使用的对象引用，遗漏就会造成噩梦般的错误。本书下一章前先完成最低限度：让 VM 能追踪所有分配对象，并在程序退出时释放它们。

表达式 "st" + "ri" + "ng" 的字节码执行过程中栈的状态。

用侵入式单链表追踪对象：链表 next 指针直接存于 Obj，避免再分配节点。

// object.h
struct Obj {
  ObjType type;
  struct Obj* next;
};

// vm.h
typedef struct {
  Chunk* chunk;
  uint8_t* ip;
  Value stack[STACK_MAX];
  Value* stackTop;
  Obj* objects;
} VM;

extern VM vm;

VM 初始化时 vm.objects = NULL。每次分配对象都插入链表头，单链表不必维护尾指针：

static Obj* allocateObject(size_t size, ObjType type) {
  Obj* object = (Obj*)reallocate(NULL, 0, size);
  object->type = type;
  object->next = vm.objects;
  vm.objects = object;
  return object;
}

结束时从头遍历，先保存 next，再执行类型特定释放：

// memory.h
#define FREE(type, pointer) reallocate(pointer, sizeof(type), 0)

void freeObjects();

// memory.c
static void freeObject(Obj* object) {
  switch (object->type) {
    case OBJ_STRING: {
      ObjString* string = (ObjString*)object;
      FREE_ARRAY(char, string->chars, string->length + 1);
      FREE(ObjString, object);
      break;
    }
  }
}

void freeObjects() {
  Obj* object = vm.objects;
  while (object != NULL) {
    Obj* next = object->next;
    freeObject(object);
    object = next;
  }
}

freeVM() 调用 freeObjects()。所有释放仍通过 reallocate() 而非直接 free()，后续即可在单一位置追踪已分配字节数。此刻 VM 只在退出时清理，长时间程序仍会持续占用内存；下一章将建立哈希表，再之后实现真正的 GC。

挑战（Challenges）

每个字符串有两次动态分配：ObjString 与字符数组。使用 flexible array members 将它们置于一次连续分配中，减少一次指针间接访问。
字面量字符串当前复制到堆，以保证所有 ObjString 都安全释放字符数组。改为区分“拥有字符数组”的字符串与指回源代码等不可释放位置的常量字符串，以节省受限设备上的内存。
若 Lox 是你的语言，字符串与非字符串使用 + 时应如何处理？说明理由，并比较其他语言的选择。

设计笔记：字符串编码（String Encoding）

本书将字符串当作 NUL 终止字节数组，避开了真实语言最棘手的问题之一。字符串编码有两面：什么算一个“字符”，以及它在内存中怎样表示。

ASCII 有 127 个字符值，适合英语却无法表示 jalapeño、naïve、Gruyère 或 Mötley Crüe。Unicode 扩展为十多万个码点（code point），但码点仍不一定等于用户看到的字符：组合字符可修饰前一个码点，例如 a 加组合变音符可组成 ä。因此访问 naïve 的第四个“字符”时，用户究竟期待 v，还是某个组合标记？前者把码点与组合字符看成一个扩展字形簇，后者则按码点计数。

内存编码也有根本权衡：

ASCII 每字符一字节、快速省内存，却排斥非拉丁文字。
UTF-32 每码点固定 32 位、全 Unicode 且随机访问快，却浪费大量内存。
UTF-8 每码点使用变长字节、与 ASCII 兼容且省内存，但定位第 N 个码点需扫描此前内容，通常是 O(n)。
UTF-16 原本为 16 位码点设计，Unicode 超出范围后引入代理对，既不如 UTF-8 省内存，又变成长编码；但浏览器、JVM、CLR 使用它，互操作时可能无法回避。

最大化方案是完整 Unicode 支持，按每个字符串内容选择 ASCII、UTF-16 等编码，并同时公开码点和扩展字形簇迭代 API；Raku、Swift 等大型新语言倾向这种方案，但实现、调试、序列化、互操作和用户理解都很复杂。

更简单的折中是统一 UTF-8，并只公开码点 API；字形簇交给第三方库。它比 ASCII 友好得多，复杂度也可控，失去的主要是按码点 O(1) 直接索引。作者若设计大型通用语言会偏向最大化方案；其嵌入式脚本语言 Wren 则选择 UTF-8 与码点。

19.1 值与对象（Values and Objects）​

19.2 结构体继承（Struct Inheritance）​

19.3 字符串（Strings）​

19.4 字符串上的操作（Operations on Strings）​

19.4.1 拼接（Concatenation）​

19.5 释放对象（Freeing Objects）​

挑战（Challenges）​

设计笔记：字符串编码（String Encoding）​