介绍
字符串是 JavaScript 中的重要数据类型，其重要性不仅体现在字符串是应用最多最广泛的数据类型，更体现在V8中使用了大量的技术手段来修饰和优化字符串的操作。接下来的几篇文章将集中讲解字符串的相关操作。本文先讲解 String.prototype.replace 的源码以及相关数据结构，再通过测试用例演示 String.prototype.replace 的调用、加载和执行过程。我们会看字符串的类型、长度等因素如何影响 replace 的实现方式和效率。
注意 （1）Sea of Nodes 是本文的先导知识，请参考 Cliff 1993年发表的论文 From Quads to Graphs。（2）本文所用环境为：V8 7.9、win10 x64、VS2019。
String.prototype.replace 源码
测试用例代码如下：
var str="Visit Microsoft!Visit Microsoft!";var res=str.replace("Microsoft","Runoob");console.log(res);
replace() 采用 TF_BUILTIN 实现，replace() 在 V8 中的函数名是 StringPrototypeReplace，编号是 594，源码如下：
1. TF_BUILTIN(StringPrototypeReplace, StringBuiltinsAssembler) {2. Label out(this);3. TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));4. Node* const search = Parameter(Descriptor::kSearch);5. Node* const replace = Parameter(Descriptor::kReplace);6. TNode<Context> context = CAST(Parameter(Descriptor::kContext));7. TNode<Smi> const smi_zero = SmiConstant(0);8. RequireObjectCoercible(context, receiver, "String.prototype.replace");9. MaybeCallFunctionAtSymbol(/*省略.....*/);10. TNode<String> const subject_string = ToString_Inline(context, receiver);11. TNode<String> const search_string = ToString_Inline(context, search);12. TNode<IntPtrT> const subject_length = LoadStringLengthAsWord(subject_string);13. TNode<IntPtrT> const search_length = LoadStringLengthAsWord(search_string);14. {15. Label next(this);16. GotoIfNot(WordEqual(search_length, IntPtrConstant(1)), &next);17. GotoIfNot(IntPtrGreaterThan(subject_length, IntPtrConstant(0xFF)), &next);18. GotoIf(TaggedIsSmi(replace), &next);19. GotoIfNot(IsString(replace), &next);20. TNode<Uint16T> const subject_instance_type =21. LoadInstanceType(subject_string);22. GotoIfNot(IsConsStringInstanceType(subject_instance_type), &next);23. GotoIf(TaggedIsPositiveSmi(IndexOfDollarChar(context, replace)), &next);24. Return(CallRuntime(Runtime::kStringReplaceOneCharWithString, context,25. subject_string, search_string, replace));26. BIND(&next); }27. TNode<Smi> const match_start_index =28. CAST(CallBuiltin(Builtins::kStringIndexOf, context, subject_string,29. search_string, smi_zero));30. {31. Label next(this), return_subject(this);32. GotoIfNot(SmiIsNegative(match_start_index), &next);33. GotoIf(TaggedIsSmi(replace), &return_subject);34. GotoIf(IsCallableMap(LoadMap(replace)), &return_subject);35. ToString_Inline(context, replace);36. Goto(&return_subject);37. BIND(&return_subject);38. Return(subject_string);39. BIND(&next); }40. TNode<Smi> const match_end_index = SmiAdd(match_start_index, SmiFromIntPtr(search_length));41. VARIABLE(var_result, MachineRepresentation::kTagged, EmptyStringConstant());42. {43. Label next(this);44. GotoIf(SmiEqual(match_start_index, smi_zero), &next);45. TNode<Object> const prefix =46. CallBuiltin(Builtins::kStringSubstring, context, subject_string,47. IntPtrConstant(0), SmiUntag(match_start_index));48. var_result.Bind(prefix);49. Goto(&next);50. BIND(&next); }51. Label if_iscallablereplace(this), if_notcallablereplace(this);52. GotoIf(TaggedIsSmi(replace), &if_notcallablereplace);53. Branch(IsCallableMap(LoadMap(replace)), &if_iscallablereplace,54. &if_notcallablereplace);55. BIND(&if_iscallablereplace);56. {57. Callable call_callable = CodeFactory::Call(isolate());58. Node* const replacement =59. CallJS(call_callable, context, replace, UndefinedConstant(),60. search_string, match_start_index, subject_string);61. TNode<String> const replacement_string =62. ToString_Inline(context, replacement);63. var_result.Bind(CallBuiltin(Builtins::kStringAdd_CheckNone, context,64. var_result.value(), replacement_string));65. Goto(&out); }66. BIND(&if_notcallablereplace);67. {68. TNode<String> const replace_string = ToString_Inline(context, replace);69. Node* const replacement =70. GetSubstitution(context, subject_string, match_start_index,71. match_end_index, replace_string);72. var_result.Bind(CallBuiltin(Builtins::kStringAdd_CheckNone, context,73. var_result.value(), replacement));74. Goto(&out);}75. BIND(&out);76. {77. TNode<Object> const suffix =78. CallBuiltin(Builtins::kStringSubstring, context, subject_string,79. SmiUntag(match_end_index), subject_length);80. TNode<Object> const result = CallBuiltin(81. Builtins::kStringAdd_CheckNone, context, var_result.value(), suffix);82. Return(result);83. }}
上述代码第 3 行代码 receiver 代表测试用例字符串 “Visit Microsoft!Visit Microsoft!”；
第 4 行代码 search 代表测试用例字符串 “Microsoft”；
第 5 行代码 replace 代表测试用例字符串 “Runoob”；
第 9 行代码当 search 为正则表达式时，使用 MaybeCallFunctionAtSymbol() 实现 replace 功能。
下面将 replace 源码划分为五个子功能单独说明：
（1） 功能 1：receiver 长度大于 0xFF、search 长度大于 1 以及 replace 为 ConsString，这三个条件同时成立时
第 10-13 行代码转换 search 和 replace 的数据类型，并计算他们的长度；
第 16 行代码判断 search 的长度是否等于 1，不等于则跳转到第 26 行；
第 17 行代码判断 receiver 的长度是否大于 0xFF，小于等于则跳转到第 26 行；
第 18-19 行判断 replace 是否为小整数或者 replace 不是字符串，结果为真则跳转到第 26 行；
第 20-22 行判断 replace 是否为 ConsString 类型，结果为假则跳转到第 26 行；提示 ConsString不是一个独立的字符串，它是使用指针把两个字符串拼接在一起的字符串对。在 V8 中，两个字符串相加的结果常是 ConsString 类型的字符串对。
第 23 行判断 PositiveSmi 类型；
第 24 行采用 Runtime::kStringReplaceOneCharWithString() 完成 replace。
（2） 功能 2：计算 receiver 中的前缀字符串
第 27-32 行计算 search的第一个字符在 receiver 中的位置 match_start_index，如果 match_start_index 不是负数则跳转到 39 行；
第 33-35 行判断 replace 是否为 SMI 或 函数，是则跳转到 37 行；
第 40 行计算 match_end_index；
第 44 行如果 match_start_index = 0（也就是 search[0]=receiver[0]），则跳转到 49 行；
第 45 行取出 receiver 中 match_start_index 位置之前的字符，保存为 prefix；也就是获取测试用例中的 “Visit ” 字符串；
第 50-54 行判断 replace 是否为 SMI 或 函数，根据判断结果跳转到相应的行号。
（3） 功能 3：replace 是函数类型
第 58-63 行计算 replace 的结果，将该结果拼接在 prefix 后面组成新的字符串 var_result;
（4） 功能 4：replace 是字符串类型
第 58-72 行将 replace 拼接在 prefix 后面组成新的字符串 var_result;
（5） 计算 receiver 中的后缀字符串
第 77-82 行取出 receiver 中 match_end_index 之后的字符串 suffix，将 suffix 拼接在 var_result 后面组成并返回新的字符串，replace 完毕。
下面简单说明 replace 中使用的 runtime 方法：
1. RUNTIME_FUNCTION(Runtime_StringReplaceOneCharWithString) {2. HandleScope scope(isolate);3. DCHECK_EQ(3, args.length());4. CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);5. CONVERT_ARG_HANDLE_CHECKED(String, search, 1);6. CONVERT_ARG_HANDLE_CHECKED(String, replace, 2);7. const int kRecursionLimit = 0x1000;8. bool found = false;9. Handle<String> result;10. if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,11. kRecursionLimit).ToHandle(&result)) {12. return *result;13. }14. if (isolate->has_pending_exception())15. return ReadOnlyRoots(isolate).exception();16. subject = String::Flatten(isolate, subject);17. if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,18. kRecursionLimit).ToHandle(&result)) {19. return *result;20. }21. if (isolate->has_pending_exception())22. return ReadOnlyRoots(isolate).exception();23. return isolate->StackOverflow();24. }
上述代码中第 10 执行 StringReplaceOneCharWithString 方法，该方法实现了 replace 功能;
第 14 行代码检测到异常情况时，先执行 String::Flatten，将ConsString字符处理成为单一字符串之后再次执行 StringReplaceOneCharWithString 方法。
图1给出 StringPrototypeReplace 的函数调用堆栈。
String.prototype.replace 测试
测试用例的字节码如下：
1. //省略........2. 000001A2EE982AC6 @ 16 : 12 01 LdaConstant [1]3. 000001A2EE982AC8 @ 18 : 15 02 04 StaGlobal [2], [4]4. 000001A2EE982ACB @ 21 : 13 02 00 LdaGlobal [2], [0]5. 000001A2EE982ACE @ 24 : 26 f9 Star r26. 000001A2EE982AD0 @ 26 : 29 f9 03 LdaNamedPropertyNoFeedback r2, [3]7. 000001A2EE982AD3 @ 29 : 26 fa Star r18. 000001A2EE982AD5 @ 31 : 12 04 LdaConstant [4]9. 000001A2EE982AD7 @ 33 : 26 f8 Star r310. 000001A2EE982AD9 @ 35 : 12 05 LdaConstant [5]11. 000001A2EE982ADB @ 37 : 26 f7 Star r412. 000001A2EE982ADD @ 39 : 5f fa f9 03 CallNoFeedback r1, r2-r413. 000001A2EE982AE1 @ 43 : 15 06 06 StaGlobal [6], [6]14. 000001A2EE982AE4 @ 46 : 13 07 08 LdaGlobal [7], [8]15. 000001A2EE982AE7 @ 49 : 26 f9 Star r216. 000001A2EE982AE9 @ 51 : 29 f9 08 LdaNamedPropertyNoFeedback r2, [8]17. 000001A2EE982AEC @ 54 : 26 fa Star r118. 000001A2EE982AEE @ 56 : 13 06 02 LdaGlobal [6], [2]19. 000001A2EE982AF1 @ 59 : 26 f8 Star r320. 000001A2EE982AF3 @ 61 : 5f fa f9 02 CallNoFeedback r1, r2-r321. 000001A2EE982AF7 @ 65 : 26 fb Star r022. 000001A2EE982AF9 @ 67 : ab Return23. Constant pool (size = 9)24. 000001A2EE982A29: [FixedArray] in OldSpace25. - map: 0x022d5e100169 <Map>26. - length: 927. 0: 0x01a2ee9829c9 <FixedArray[8]>28. 1: 0x01a2ee9828c1 <String[#32]: Visit Microsoft!Visit Microsoft!>29. 2: 0x01a2ee9828a9 <String[#3]: str>30. 3: 0x02749a2ab821 <String[#7]: replace>31. 4: 0x01a2ee982909 <String[#9]: Microsoft>32. 5: 0x01a2ee982929 <String[#6]: Runoob>33. 6: 0x01a2ee9828f1 <String[#3]: res>34. 7: 0x02749a2b3699 <String[#7]: console>35. 8: 0x02749a2b2cd9 <String[#3]: log>
上述代码中，第 2-5 行读取字符串 “Visit Microsoft!Visit Microsoft!” 并保存到 r2 寄存器中；
第 6-7 行获取 replace 函数地址并保存到 r1 寄存器中；
第 8-11 行读取 “Microsoft” 和 “Runoob” 并分别保存到 r3 和 r4 寄存器中；
第 12 行调用 repalce 方法；
图 2 给出了 CallNoFeedback 的调用堆栈。
技术总结
（1） receiver 长度大于 0xFF、search 长度大于 1 以及 replace为ConsString，三个条件同时成立时采用低效率的 runtime 方式处理；
（2） replace 的原理是计算前、后缀，并与 newvalue 拼接组成最终结果。
好了，今天到这里，下次见。
个人能力有限，有不足与纰漏，欢迎批评指正
X0_0X
Anna艳娜
Anna艳娜
RacentYY
RacentYY
Coremail邮件安全
Andrew
X0_0X
X0_0X
Anna艳娜
007bug
虹科网络安全
