《Chrome V8 源码》39. String.prototype.split 源码分析

阅读量    139435 |

分享到: QQ空间 新浪微博 微信 QQ facebook twitter

 

1 介绍

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

 

2 String.prototype.split 源码

测试用例代码如下:

var str="How9are9you9doing9today?";
var n=str.split("9");
console.log(n);

split() 采用 TF_BUILTIN 实现,replace() 在 V8 中的函数名是 StringPrototypeSplit,编号是 596,源码如下:

1.  TF_BUILTIN(StringPrototypeSplit, StringBuiltinsAssembler) {
2.    const int kSeparatorArg = 0;
3.    const int kLimitArg = 1;
4.    TNode<IntPtrT> const argc =
5.        ChangeInt32ToIntPtr(Parameter(Descriptor::kJSActualArgumentsCount));
6.    CodeStubArguments args(this, argc);
7.    TNode<Object> receiver = args.GetReceiver();
8.    TNode<Object> const separator = args.GetOptionalArgumentValue(kSeparatorArg);
9.    TNode<Object> const limit = args.GetOptionalArgumentValue(kLimitArg);
10.    TNode<NativeContext> context = CAST(Parameter(Descriptor::kContext));
11.    TNode<Smi> smi_zero = SmiConstant(0);
12.    RequireObjectCoercible(context, receiver, "String.prototype.split");
13.    MaybeCallFunctionAtSymbol(/*省略....*/);
14.    TNode<String> subject_string = ToString_Inline(context, receiver);
15.    TNode<Number> limit_number = Select<Number>(
16.        IsUndefined(limit), [=] { return NumberConstant(kMaxUInt32); },
17.        [=] { return ToUint32(context, limit); });
18.    TNode<String> const separator_string = ToString_Inline(context, separator);
19.    Label return_empty_array(this);
20.    GotoIf(TaggedEqual(limit_number, smi_zero), &return_empty_array);
21.    {
22.      Label next(this);
23.      GotoIfNot(IsUndefined(separator), &next);
24.      const ElementsKind kind = PACKED_ELEMENTS;
25.      TNode<NativeContext> const native_context = LoadNativeContext(context);
26.      TNode<Map> array_map = LoadJSArrayElementsMap(kind, native_context);
27.      TNode<Smi> length = SmiConstant(1);
28.      TNode<IntPtrT> capacity = IntPtrConstant(1);
29.      TNode<JSArray> result = AllocateJSArray(kind, array_map, capacity, length);
30.      TNode<FixedArray> fixed_array = CAST(LoadElements(result));
31.      StoreFixedArrayElement(fixed_array, 0, subject_string);
32.      args.PopAndReturn(result);
33.      BIND(&next);
34.    }
35.    {
36.      Label next(this);
37.      GotoIfNot(SmiEqual(LoadStringLengthAsSmi(separator_string), smi_zero),
38.                &next);
39.      TNode<Smi> subject_length = LoadStringLengthAsSmi(subject_string);
40.      GotoIf(SmiEqual(subject_length, smi_zero), &return_empty_array);
41.      args.PopAndReturn(
42.          StringToArray(context, subject_string, subject_length, limit_number));
43.      BIND(&next);
44.    }
45.    TNode<Object> const result =
46.        CallRuntime(Runtime::kStringSplit, context, subject_string,
47.                    separator_string, limit_number);
48.    args.PopAndReturn(result);
49.    BIND(&return_empty_array);
50.    {
51.      const ElementsKind kind = PACKED_ELEMENTS;
52.      TNode<NativeContext> const native_context = LoadNativeContext(context);
53.      TNode<Map> array_map = LoadJSArrayElementsMap(kind, native_context);
54.      TNode<Smi> length = smi_zero;
55.      TNode<IntPtrT> capacity = IntPtrConstant(0);
56.      TNode<JSArray> result = AllocateJSArray(kind, array_map, capacity, length);
57.      args.PopAndReturn(result);
58.    }
59.  }

上述代码中,第 7 行代码 receiver 代表测试用例中的字符串 str;
第 8 行代码 separator 代表测试用例中的 “9”;
第 9 行代码读取 limit;
第 13 行代码如果 separator 是正则表达式,就使用 MaybeCallFunctionAtSymbol() 完成 split 操作;
第 14 行代码把 receiver 转换为字符串,并保存到 subject_string 中;
第 15 行代码把 limit 的类型转换为 Number;
第 16 行代码把 separator 转换为字符串,并保存到 separator_string 中;
第 20 行代码判断 limit 是否等于零,等于返回空字符串,split 退出;
第 21 行代码判断 separator 是否等于 Undefined,不等于则跳转到第 33 行代码;
第 24-32 行代码实现 ECMA的规定:“if {separator} is undefined, the result should be an array of size 1 containing the entire string. ”;
第 37 行代码判断 separator的长度是否等于零,不等于则跳转到第 43 行代码;
第 39-41 行代码用于实现 separator=”” 时的 split 功能,即创建由 receiver 中的所有字符组成的数组;
第 45 行代码当 “separator 长度大于零” 和 “limit未定义或大于零” 两个条件同时满足时,该行用于实现 split 功能;
第 49-59行代码返回空数组。
下面说明 StringPrototypeSplit 中使用的重要函数:
(1) StringToArray 方法,在本文中该方法实现了 separator=”” 时的 split 功能,源码如下:

1.  TNode<JSArray> StringBuiltinsAssembler::StringToArray(
2.      TNode<NativeContext> context, TNode<String> subject_string,
3.      TNode<Smi> subject_length, TNode<Number> limit_number) {
4.    TVARIABLE(JSArray, result_array);
5.    TNode<Uint16T> instance_type = LoadInstanceType(subject_string);
6.    GotoIfNot(IsOneByteStringInstanceType(instance_type), &call_runtime);
7.    {
8.      TNode<Smi> length_smi =
9.          Select<Smi>(TaggedIsSmi(limit_number),
10.                      [=] { return SmiMin(CAST(limit_number), subject_length); },
11.                      [=] { return subject_length; });
12.      TNode<IntPtrT> length = SmiToIntPtr(length_smi);
13.      ToDirectStringAssembler to_direct(state(), subject_string);
14.      to_direct.TryToDirect(&call_runtime);
15.      TNode<FixedArray> elements = CAST(AllocateFixedArray(
16.          PACKED_ELEMENTS, length, AllocationFlag::kAllowLargeObjectAllocation));
17.      TNode<RawPtrT> string_data =
18.          to_direct.PointerToData(&fill_thehole_and_call_runtime);
19.      TNode<IntPtrT> string_data_offset = to_direct.offset();
20.      TNode<FixedArray> cache = SingleCharacterStringCacheConstant();
21.      BuildFastLoop(
22.          IntPtrConstant(0), length,
23.          [&](Node* index) {
24.            CSA_ASSERT(this, WordEqual(to_direct.PointerToData(&call_runtime),
25.                                       string_data));
26.            TNode<Int32T> char_code =
27.                UncheckedCast<Int32T>(Load(MachineType::Uint8(), string_data,
28.                                           IntPtrAdd(index, string_data_offset)));
29.            TNode<UintPtrT> code_index = ChangeUint32ToWord(char_code);
30.            TNode<Object> entry = LoadFixedArrayElement(cache, code_index);
31.            GotoIf(IsUndefined(entry), &fill_thehole_and_call_runtime);
32.            StoreFixedArrayElement(elements, index, entry);
33.          },
34.          1, ParameterMode::INTPTR_PARAMETERS, IndexAdvanceMode::kPost);
35.      TNode<Map> array_map = LoadJSArrayElementsMap(PACKED_ELEMENTS, context);
36.      result_array = AllocateJSArray(array_map, elements, length_smi);
37.      Goto(&done);
38.      BIND(&fill_thehole_and_call_runtime);
39.      {
40.        FillFixedArrayWithValue(PACKED_ELEMENTS, elements, IntPtrConstant(0),
41.                                length, RootIndex::kTheHoleValue);
42.        Goto(&call_runtime); } }
43.    BIND(&call_runtime);
44.    {
45.      result_array = CAST(CallRuntime(Runtime::kStringToArray, context,
46.                                      subject_string, limit_number));
47.      Goto(&done);}
48.    BIND(&done);
49.    return result_array.value();}

上述代码中,第 6 行代码判断 subject_string 是否为单字节字符串,如果不是则跳转到第 43 行;
第 8 行代码计算数组长度,如果定义了 limit,数组长度取 subject_string.length 和 limit 之中的最小值;如果未定义,数组长度等于 subject_string.length;
第 14 行代码将间接字符串转换为直接字符串,转换失败时调用 runtime 处理;
第 15 行代码分配数组 elements;
第 21-34 行代码使用 BuildFastLoop 方式填充 elements,填充失败时使用 runtime 处理;注意:BuildFastLoop 为 Turbofan 后端做了优化,请自行学习。
第 40-45 行代码使用 runtime 方式生成数组;
(2) Runtime_StringSplit 源码如下:

1.  RUNTIME_FUNCTION(Runtime_StringSplit) {
2.  int subject_length = subject->length();
3.  int pattern_length = pattern->length();
4.  CHECK_LT(0, pattern_length);
5.  if (limit == 0xFFFFFFFFu) {//省略............}
6.  subject = String::Flatten(isolate, subject);
7.  pattern = String::Flatten(isolate, pattern);
8.   std::vector<int>* indices = GetRewoundRegexpIndicesList(isolate);
9.   FindStringIndicesDispatch(isolate, *subject, *pattern, indices, limit);
10.   if (static_cast<uint32_t>(indices->size()) < limit) {
11.     indices->push_back(subject_length);}
12.   int part_count = static_cast<int>(indices->size());
13.   Handle<JSArray> result =
14.       isolate->factory()->NewJSArray(PACKED_ELEMENTS, part_count, part_count,
15.                                      INITIALIZE_ARRAY_ELEMENTS_WITH_HOLE);
16.   DCHECK(result->HasObjectElements());
17.   Handle<FixedArray> elements(FixedArray::cast(result->elements()), isolate);
18.   if (part_count == 1 && indices->at(0) == subject_length) {
19.     elements->set(0, *subject);
20.   } else {
21.     int part_start = 0;
22.     FOR_WITH_HANDLE_SCOPE(isolate, int, i = 0, i, i < part_count, i++, {
23.       int part_end = indices->at(i);
24.       Handle<String> substring =
25.           isolate->factory()->NewProperSubString(subject, part_start, part_end);
26.       elements->set(i, *substring);
27.       part_start = part_end + pattern_length;
28.     });}
29.   if (limit == 0xFFFFFFFFu) {//省略............}
30.   TruncateRegexpIndicesList(isolate);
31.   return *result;

上述代码中,第 2 行代码 subject 表示测试用例字符串 str;
第 3 行代码 pattern 表示 separator;
第 9 行代码使用 pattern 切分 subject,并将切分结果保存在 indices中。切分结果是切片的数量以及每个切片的开始、结尾下标。
第 13 行代码申请数组 elements,该数组长度等于切片数量;
第 19 行代码切片数量为 1时,把 subject 复制到 elements 中;
第 20-28 行代码使用循环把每个切片复制到 elements 中;
图 1 给出了初始化 StringPrototypeSplit 时的调用堆栈。

 

2 String.prototype.split 测试

测试代码的字节码如下:

1.   000000A369D42A96 @   16 : 12 01             LdaConstant [1]
2.   000000A369D42A98 @   18 : 15 02 04          StaGlobal [2], [4]
3.   000000A369D42A9B @   21 : 13 02 00          LdaGlobal [2], [0]
4.   000000A369D42A9E @   24 : 26 f9             Star r2
5.   000000A369D42AA0 @   26 : 29 f9 03          LdaNamedPropertyNoFeedback r2, [3]
6.   000000A369D42AA3 @   29 : 26 fa             Star r1
7.   000000A369D42AA5 @   31 : 12 04             LdaConstant [4]
8.   000000A369D42AA7 @   33 : 26 f8             Star r3
9.   000000A369D42AA9 @   35 : 5f fa f9 02       CallNoFeedback r1, r2-r3
10.   000000A369D42AAD @   39 : 15 05 06          StaGlobal [5], [6]
11.   000000A369D42AB0 @   42 : 13 06 08          LdaGlobal [6], [8]
12.   000000A369D42AB3 @   45 : 26 f9             Star r2
13.   000000A369D42AB5 @   47 : 29 f9 07          LdaNamedPropertyNoFeedback r2, [7]
14.   000000A369D42AB8 @   50 : 26 fa             Star r1
15.   000000A369D42ABA @   52 : 13 05 02          LdaGlobal [5], [2]
16.   000000A369D42ABD @   55 : 26 f8             Star r3
17.   000000A369D42ABF @   57 : 5f fa f9 02       CallNoFeedback r1, r2-r3
18.   000000A369D42AC3 @   61 : 26 fb             Star r0
19.   000000A369D42AC5 @   63 : ab                Return
20.  Constant pool (size = 8)
21.  000000A369D42A01: [FixedArray] in OldSpace
22.   - map: 0x03abc3a00169 <Map>
23.   - length: 8
24.   0: 0x00a369d429a1 <FixedArray[8]>
25.   1: 0x00a369d428c1 <String[#24]: How9are9you9doing9today?>
26.   2: 0x00a369d428a9 <String[#3]: str>
27.   3: 0x0233195eba31 <String[#5]: split>
28.   4: 0x00a369d42901 <String[#1]: 9>
29.   5: 0x00a369d428e9 <String[#1]: n>
30.   6: 0x0233195f3699 <String[#7]: console>
31.   7: 0x0233195f2cd9 <String[#3]: log>

上述代码中,第 1-4 行代码读取字符串 “How9are9you9doing9today?” 并保存到 r2 寄存器中;
第 5-6 行代码获取字符串方法 split 并保存到 r1 寄存器中;
第 7-8 行代码获取 separator 字符串并保存到 r3 寄存器中。测试用例的 separator 是 ‘9’。
第 9 行代码 CallNoFeedback 调用 split 方法,并传递 r2、r3 两个参数给 split 方法。

技术总结
(1) 多数情况下,split 方法由 runtime 实现;
(2) v8 中字符串分为单字节和双字节两种;
(3) 间接字符串包括:ConsString、SlicedString、ThinString以及ExternalString。

好了,今天到这里,下次见。
个人能力有限,有不足与纰漏,欢迎批评指正
微信:qq9123013 备注:v8交流 邮箱:v8blink@outlook.com

分享到: QQ空间 新浪微博 微信 QQ facebook twitter
|推荐阅读
|发表评论
|评论列表
加载更多