正文

《Chrome V8 源码》36. String.prototype.concat 源码分析

admin
admin V管理员 /0 评论 /16 阅读
0321
此篇文章发布距今已超过1141天，您需要注意文章的内容或图片是否可用！

 

1 介绍

字符串是 JavaScript 中的重要数据类型，其重要性不仅体现在字符串是应用最多最广泛的数据类型，更体现在V8中使用了大量的技术手段来修饰和优化字符串的操作。接下来的几篇文章将集中讲解字符串的相关操作。本文先讲解 String.prototype.concat 的源码以及相关数据结构，再通过测试用例演示 String.prototype.concat 的调用、加载和执行过程。
注意 （1）Sea of Nodes 是本文的先导知识，请参考 Cliff 1993年发表的论文 From Quads to Graphs。（2）本文所用环境为：V8 7.9、win10 x64、VS2019。

 

2 String.prototype.concat 源码

测试用例代码如下：

var txt1 = "he ", txt2="is ", txt3="HuiDou ", txt4=".";
var bio = txt1.concat(txt2,txt3,txt4);
console.log(bio);

concet() 是用 TF_BUILTIN 实现的，concet() 在 V8 中的函数名是 StringPrototypeConcat，编号是 888，源码如下：

1.  TF_BUILTIN(StringPrototypeConcat, CodeStubAssembler) {
2.  ca_.Goto(&block0, torque_arguments.frame, torque_arguments.base, torque_arguments.length, parameter0, parameter1);
3.    if (block0.is_used()) {//省略..............
4.      ca_.Bind(&block0, &tmp0, &tmp1, &tmp2, &tmp3, &tmp4);
5.      ca_.SetSourcePosition("../../../src/builtins/string.tq", 128);
6.      compiler::TNode<String> tmp5;
7.      USE(tmp5);
8.      tmp5 = FromConstexpr6String18ATconstexpr_string_156(state_, "String.prototype.concat");
9.      compiler::TNode<String> tmp6;
10.      USE(tmp6);
11.      tmp6 = CodeStubAssembler(state_).ToThisString(compiler::TNode<Context>{tmp3}, compiler::TNode<Object>{tmp4}, compiler::TNode<String>{tmp5});
12.      ca_.SetSourcePosition("../../../src/builtins/string.tq", 131);
13.      compiler::TNode<IntPtrT> tmp7;
14.      USE(tmp7);
15.      tmp7 = Convert8ATintptr8ATintptr_1494(state_, compiler::TNode<IntPtrT>{tmp2});
16.      ca_.SetSourcePosition("../../../src/builtins/string.tq", 132);
17.      compiler::TNode<IntPtrT> tmp8;
18.      USE(tmp8);
19.      tmp8 = FromConstexpr8ATintptr17ATconstexpr_int31_150(state_, 0);
20.      ca_.Goto(&block3, tmp0, tmp1, tmp2, tmp3, tmp4, tmp6, tmp7, tmp8);
21.    }
22.    if (block3.is_used()) {//省略..............
23.      ca_.Bind(&block3, &tmp9, &tmp10, &tmp11, &tmp12, &tmp13, &tmp14, &tmp15, &tmp16);
24.      compiler::TNode<BoolT> tmp17;
25.      USE(tmp17);
26.      tmp17 = CodeStubAssembler(state_).IntPtrLessThan(compiler::TNode<IntPtrT>{tmp16}, compiler::TNode<IntPtrT>{tmp15});
27.      ca_.Branch(tmp17, &block1, &block2, tmp9, tmp10, tmp11, tmp12, tmp13, tmp14, tmp15, tmp16);
28.    }
29.    if (block1.is_used()) {//省略..............
30.      ca_.Bind(&block1, &tmp18, &tmp19, &tmp20, &tmp21, &tmp22, &tmp23, &tmp24, &tmp25);
31.      ca_.SetSourcePosition("../../../src/builtins/string.tq", 133);
32.      compiler::TNode<Object> tmp26;
33.      USE(tmp26);
34.      tmp26 = CodeStubAssembler(state_).GetArgumentValue(TorqueStructArguments{compiler::TNode<RawPtrT>{tmp18}, compiler::TNode<RawPtrT>{tmp19}, compiler::TNode<IntPtrT>{tmp20}}, compiler::TNode<IntPtrT>{tmp25});
35.      compiler::TNode<String> tmp27;
36.      USE(tmp27);
37.      tmp27 = CodeStubAssembler(state_).ToString_Inline(compiler::TNode<Context>{tmp21}, compiler::TNode<Object>{tmp26});
38.      ca_.SetSourcePosition("../../../src/builtins/string.tq", 134);
39.      compiler::TNode<String> tmp28;
40.      USE(tmp28);
41.      tmp28 = StringAdd_82(state_, compiler::TNode<Context>{tmp21}, compiler::TNode<String>{tmp23}, compiler::TNode<String>{tmp27});
42.      ca_.SetSourcePosition("../../../src/builtins/string.tq", 132);
43.      ca_.Goto(&block4, tmp18, tmp19, tmp20, tmp21, tmp22, tmp28, tmp24, tmp25);
44.    }
45.    if (block4.is_used()) {//省略..............
46.      ca_.Bind(&block4, &tmp29, &tmp30, &tmp31, &tmp32, &tmp33, &tmp34, &tmp35, &tmp36);
47.      compiler::TNode<IntPtrT> tmp37;
48.      USE(tmp37);
49.      tmp37 = FromConstexpr8ATintptr17ATconstexpr_int31_150(state_, 1);
50.      compiler::TNode<IntPtrT> tmp38;
51.      USE(tmp38);
52.      tmp38 = CodeStubAssembler(state_).IntPtrAdd(compiler::TNode<IntPtrT>{tmp36}, compiler::TNode<IntPtrT>{tmp37});
53.      ca_.Goto(&block3, tmp29, tmp30, tmp31, tmp32, tmp33, tmp34, tmp35, tmp38);
54.    }
55.    if (block2.is_used()) {//省略..............
56.      ca_.Bind(&block2, &tmp39, &tmp40, &tmp41, &tmp42, &tmp43, &tmp44, &tmp45, &tmp46);
57.      ca_.SetSourcePosition("../../../src/builtins/string.tq", 136);
58.      arguments.PopAndReturn(tmp44);
59.    }
60.  }

上述代码中定义了四个 block（block0-block4），它们的作用是：
block0 创建三个变量：初始字符串 tmp6（即测试用例中的“he”）、拼接总数 tmp7（测试用例中的数量为 3）和完成拼接的数量 tmp8（初始值为 0）；
block1 把两个字符串拼接在一起生成一个新字符串；
block2 返回最终结果；
block3 判断完成拼接的数量是否小于拼接总数，如果小于跳转到 block1，如果不小于跳转到 blcok2；
block4 把完成拼接的数量加 1。
从这些 block 在代码中的分布位置可以看出，他们使用 while 循环方式实现了字符串的拼接。图 1 给出了 StringPrototypeConcat 源码的位置。

下面说明 StringPrototypeConcat 用到的重要函数：
（1） ToThisString（第 11 行代码）的作用是把对象转换成字符串，源码如下：

1.  TNode<String> CodeStubAssembler::ToThisString(/*省略*/) {
2.  BIND(&if_valueisnotsmi);//省略....
3.  { TNode<Uint16T> value_instance_type = LoadInstanceType(CAST(value));
4.    Label if_valueisnotstring(this, Label::kDeferred);
5.    Branch(IsStringInstanceType(value_instance_type), &if_valueisstring,
6.            &if_valueisnotstring);
7.     BIND(&if_valueisnotstring);
8.     { Label if_valueisnullorundefined(this, Label::kDeferred);
9.       GotoIf(IsNullOrUndefined(value), &if_valueisnullorundefined);
10.       var_value.Bind(CallBuiltin(Builtins::kToString, context, value));
11.       Goto(&if_valueisstring);
12.       BIND(&if_valueisnullorundefined);
13.       {ThrowTypeError(context, MessageTemplate::kCalledOnNullOrUndefined,
14.                        method_name);}
15.     }
16.   }
17.   BIND(&if_valueissmi);
18.   {var_value.Bind(CallBuiltin(Builtins::kNumberToString, context, value));
19.     Goto(&if_valueisstring);  }
20.   BIND(&if_valueisstring);
21.   return CAST(var_value.value());

上述代码中第 2-16 行用于把非 small integer 数据转换成字符串，非 small integer 可以是数组、浮点数等。其中转换操作的具体功能由第 10 行的 kToString 实现；第 17-19 行用于把 small integer 数据转换成字符串，转换操作的具体功能由第 18 行的 kNumberToString 实现。后续文章会单独讲解 kToString 和 kNumberToString 方法。
（2） IntPtrAdd（第 52 行）实现整型数据的加法，源码如下：

1.  TNode<WordT> CodeAssembler::IntPtrAdd(SloppyTNode<WordT> left,
2.                                      SloppyTNode<WordT> right) {
3.  intptr_t left_constant;
4.  bool is_left_constant = ToIntPtrConstant(left, &left_constant);
5.  intptr_t right_constant;
6.  bool is_right_constant = ToIntPtrConstant(right, &right_constant);
7.  if (is_left_constant) {
8.    if (is_right_constant) {
9.      return IntPtrConstant(left_constant + right_constant);}
10.     if (left_constant == 0) { return right;}
11.   } else if (is_right_constant) {
12.     if (right_constant == 0) {return left;}
13.      }
14.   return UncheckedCast<WordT>(raw_assembler()->IntPtrAdd(left, right));}

上述代码中第 7-13 行用于常量的加法运算，其中第 7-8 行判断加法的左右值，如果都为常量则直接计算结果（第 9 行）；第 10 行代码判断左值，如果为零则直接返回右值；第 14 行代码表示当左、右值均为变量时，则需要添加计算节点。
（3） StringAdd_82（第 41 行）中调用 Builtins::kStringAdd_CheckNone 方法，该方法使用 CodeStubAssembler::StringAdd 完成字符串的加法运算，StringAdd 的源码如下：

1.  TNode<String> CodeStubAssembler::StringAdd(Node* context, TNode<String> left,
2.                                           TNode<String> right) {
3.  TNode<Uint32T> left_length = LoadStringLengthAsWord32(left);
4.  GotoIfNot(Word32Equal(left_length, Uint32Constant(0)), &check_right);
5.  result = right;
6.  Goto(&done_native);
7.  BIND(&check_right);
8.  TNode<Uint32T> right_length = LoadStringLengthAsWord32(right);
9.  GotoIfNot(Word32Equal(right_length, Uint32Constant(0)), &cons);
10.   result = left;
11.   Goto(&done_native);
12.   BIND(&cons);
13.   {
14.     TNode<Uint32T> new_length = Uint32Add(left_length, right_length);
15.     GotoIf(Uint32GreaterThan(new_length, Uint32Constant(String::kMaxLength)),
16.            &runtime);
17.     TVARIABLE(String, var_left, left);
18.     TVARIABLE(String, var_right, right);
19.     Variable* input_vars[2] = {&var_left, &var_right};
20.     Label non_cons(this, 2, input_vars);
21.     Label slow(this, Label::kDeferred);
22.     GotoIf(Uint32LessThan(new_length, Uint32Constant(ConsString::kMinLength)),
23.            &non_cons);
24.     result =AllocateConsString(new_length, var_left.value(), var_right.value());
25.     Goto(&done_native);
26.     BIND(&non_cons);
27.     TNode<Int32T> left_instance_type = LoadInstanceType(var_left.value());
28.     TNode<Int32T> right_instance_type = LoadInstanceType(var_right.value());
29.     TNode<Int32T> ored_instance_types =
30.         Word32Or(left_instance_type, right_instance_type);
31.     TNode<Word32T> xored_instance_types =
32.         Word32Xor(left_instance_type, right_instance_type);
33.     GotoIf(IsSetWord32(xored_instance_types, kStringEncodingMask), &runtime);
34.     GotoIf(IsSetWord32(ored_instance_types, kStringRepresentationMask), &slow);
35.     TNode<IntPtrT> word_left_length = Signed(ChangeUint32ToWord(left_length));
36.     TNode<IntPtrT> word_right_length = Signed(ChangeUint32ToWord(right_length));
37.     Label two_byte(this);
38.     GotoIf(Word32Equal(Word32And(ored_instance_types,
39.                                  Int32Constant(kStringEncodingMask)),
40.                        Int32Constant(kTwoByteStringTag)),&two_byte);
41.     result = AllocateSeqOneByteString(new_length);
42.     CopyStringCharacters(/*拷贝左字符串*/);
43.     CopyStringCharacters(/*拷贝右字符串*/);
44.     Goto(&done_native);
45.     BIND(&two_byte);
46.     {
47.       result = AllocateSeqTwoByteString(new_length);
48.       CopyStringCharacters(/*拷贝左字符串*/);
49.       CopyStringCharacters(/*拷贝右字符串*/);
50.       Goto(&done_native); }
51.     BIND(&slow);
52.     {
53.       MaybeDerefIndirectStrings(&var_left, left_instance_type, &var_right,
54.                                 right_instance_type, &non_cons);
55.       Goto(&runtime);}}
56.   BIND(&runtime);
57.   {//省略.....
58.     Goto(&done); }
59.   BIND(&done_native);
60.   {    Goto(&done);  }
61.   BIND(&done);
62.    return result.value();}

上述代码中，第 3-6 行代码判断左值长度是否为零，如果为零则直接返回右值；
第 7-11 行代码判断右值长度是否为零，如果为零则直接返回左值；
第 14-15 行代码判断新字符串的长度是否大于 V8 规定的字符串的最大长度，如果大于则使用 runtime 方式处理；
第 22 行代码判断新字符串的长度是否小于 V8 规定的字符串的最小长度，如果小于则使用 slow 或 runtime 方式处理；
第 27-34 行代码判断左、右值的编码是否一致且是否都为 sequential string，如是结果为真则执行第 35-50 行代码；
第 35-50 行代码根据单、双字节的不同，采用不同的方式创建并返回新的字符串，函数执行完毕；
第 51-58 行代码采用 slow 和 runtime 方式处理字符串。
图 2 给出了 StringAdd() 的调用堆栈。

 

3.String.prototype.concat 测试

测试用例的字节码如下：

1.  //省略........
2.     11 S> 000001332DAC2C86 @   16 : 12 01             LdaConstant [1]
3.     11 E> 000001332DAC2C88 @   18 : 15 02 0a          StaGlobal [2], [10]
4.  //省略........
5.     64 S> 000001332DAC2C9A @   36 : 13 02 00          LdaGlobal [2], [0]
6.           000001332DAC2C9D @   39 : 26 f9             Star r2
7.     69 E> 000001332DAC2C9F @   41 : 29 f9 09          LdaNamedPropertyNoFeedback r2, [9]
8.  //省略........
9.     69 E> 000001332DAC2CB3 @   61 : 5f fa f9 04       CallNoFeedback r1, r2-r5
10.  //省略........
11.  Constant pool (size = 13)
12.  000001332DAC2BC9: [FixedArray] in OldSpace
13.   - map: 0x00df20ec0169 <Map>
14.   - length: 13
15.             0: 0x01332dac2b09 <FixedArray[20]>
16.             1: 0x01332dac29d9 <String[#3]: he >
17.             2: 0x01332dac29c1 <String[#4]: txt1>
18.             3: 0x01332dac2a09 <String[#3]: is >
19.             4: 0x01332dac29f1 <String[#4]: txt2>
20.             5: 0x01332dac2a39 <String[#7]: HuiDou >
21.             6: 0x01332dac2a21 <String[#4]: txt3>
22.             7: 0x00df20ec4369 <String[#1]: .>
23.             8: 0x01332dac2a51 <String[#4]: txt4>
24.             9: 0x037ebea28b49 <String[#6]: concat>
25.            10: 0x01332dac2a69 <String[#3]: bio>
26.            11: 0x037ebea336f1 <String[#7]: console>
27.            12: 0x037ebea32d31 <String[#3]: log>

上述代码中，第 2-3 行加载并存储字符串 “he”；第 5-6 行把字符串 “he” 保存到 r2 寄存器中； 第 7 行加载 concat 方法；第 9 行调用 concat 方法，r1 寄存器的值是 concat 的地址，r2-r5 依次是 “he ”、“is ”、“HuiDou ” 和 “.”。debug测试方法：从 CallNoFeedback 开始进行汇编跟踪，如图 3 所示。

技术总结
（1） 拼接前要判断左、右字符串的类型、编码以及单双字节是否一致；
（2） 拼接采用循环方式对字符串两两拼接；
（3） 字符串的最大长度是 String::kMaxLength（1073741799）。

好了，今天到这里，下次见。
个人能力有限，有不足与纰漏，欢迎批评指正
微信：qq9123013 备注：v8交流 邮箱：[email protected]