源码共读前言

为了能帮助到更多对源码感兴趣、想学会看源码、提升自己写作和前端技术能力的同学。 帮助读者夯实基础，查漏补缺，开阔眼界，拓宽视野，知其然知其所以然。

我倾力组织了每周一起学200行左右的源码共读活动。我写有《学习源码整体架构系列》20余篇，走过路过的小伙伴可以点击关注下这个目前是掘金关注数最多的专栏。

欢迎点此扫码加我微信 ruochuan02 交流，参与 源码共读 活动，每周大家一起学习200行左右的源码，共同进步。可以持续关注我@若川。

从易到难推荐学习顺序

活动介绍和顺序具体看这里从易到难推荐学习顺序

提交笔记

提交笔记方式，具体的看这里
简言之：看任务，看辅助文章、看源码，交流讨论，在掘金写笔记，写好后提交到本文评论区。

为了给大家谋福利，另外给大家的文章带来更多阅读量，便于搜索，从2022年3月27日起，笔记可以直接发布在掘金，以《标题自取》标题不限，可以取个好标题，容易被掘金推荐。

笔记文章开头加两句话：

• 本文参加了由公众号@若川视野 发起的每周源码共读活动， 点击了解详情一起参与。
• 这是源码共读的第xx期，链接：xxx。

笔记文章最后，建议写上总结、收获、感受等。

• 开头第一句作用是：方便每月统计评优，掘金赞助送小礼物。顺便帮忙宣传推广，让更多人参与进来，一起学习。
• 开头第二句作用是：加上是多少期，当前任务说明的链接，方便读者知道这是什么活动。

笔记写完后，到当前期活动的文章评论区留言自己的文章和笔记特点。方便大家查阅学习交流讨论。

任务发布时间

2023年3月6日 - 2023年3月19日(两周)。可以按照自己节奏学习，提交笔记即可（不一定要严格按照我规定的时间）。往期共读也可以及时复习，笔记未完成可以继续完成。

语雀本期任务说明链接

语雀有树形菜单，更方便查看，所以也放下语雀的这一期链接

学习任务

• 1. 学会如何用 vue3 + ts 开发一个 loading 组件
• 2. 学会使用 vue-devtools 打开组件文件，并可以学会其原理
• 3. 学会使用 @vue/babel-plugin-jsx 编写 jsx 组件
• 4. 等等

• 参考我的文章
• juejin.cn/post/716046…

参考文章

• juejin.cn/post/716046…
• 看文章，看源码，交流讨论，写笔记发布在掘金。再在掘金这篇文章下评论放上提交笔记的链接。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

作者：王舒源

本文预计阅读时长约为 20min

本文为公司内部的分享，部分内容是 live coding 现场编写，需要参考代码示例

完整的代码示例可以在这里找到

前言

对于 NAPI-RS 来说，大家一定已经不陌生了。和 Neon，WASM-Bindgen 相同，它们均是用来生成对于某种 Binding 的工具库，前者 Neon 和 NAPI-RS 基本是同类产品，用于生成和 Node 的 Binding。

Binding 是什么？

这里的 binding 等价于 Language binding，摘录一段维基百科中的描述：

In programming and software design, binding is an application programming interface (API) that provides glue code specifically made to allow a programming language to use a foreign library or operating system service (one that is not native to that language). From Wikipedia

大部分同类型的工具的架构都比较类似，对于 NAPI-RS 来说是这样的：

• NAPI-SYS：NAPI 的 SYS crate，负责和 Node 通信。社区上通常使用 *-sys 命名这些底层调用的库。
• NAPI: NAPI crate 则是对 NAPI-SYS 库的上层封装。由于 Sys crate 通常是原生的底层 API，因此基本所有原生库都会存在一个对语言友好的封装，进而降低用户的使用成本与代码的准确性。

为什么 Sys crate 通常和 Wrapper crate 分开存在？

对于 Sys crate 来说，它们的工作是和底层的 lib 相绑定，API 的变化通常不会那么频繁，而对于 wrapper 层来说它们是极易产生 breaking change 的。当 Sys 和 Wrapper 放在同一个 crate 中则非常容易产生 breaking change，如此时进行大版本升级，则可能会导致项目中单独使用 Sys crate 的 Dependency（无论是间接，还是直接）们都需要进行升级，因此这是不合理的。详情见 Semver Compatability

• NAPI Macro 与 NAPI Macro backend：通常为使用 NAPI 的 Rust API 在编译时生成相关模板代码，解放用户的双手。如 NAPI Macro 还做了一些 TS 类型生成的工作。

对于上层的 crate 我们不会在本篇中做过多的介绍，对于它们来说，更多的重心则是放在“怎么让用户降低开发成本”（例如是基于 Macro 的编译时生成模板代码、对 Promise 类型的封装使得它能够对接 Rust Future等）与“怎么让用户的代码变得更加的安全”（例如：对于某些 Opaque 类型的上层封装）上。

本篇，我们会将更多的目光聚焦于 Sys crate 和 Node 的通信上，因为这是 NAPI 的本质。

总结成一句话来说：NAPI-SYS 和 Node 的通信是建立在 C ABI 之上的 FFI 的调用。

C ABI ?

看到这里，有些人可能会对这个概念有一些歧义，我们将会在下方做进一步解释。

我们会以一个简单的 NAPI-SYS crate 的实现作为结束。同时为了让整体的衔接不至于太过僵硬，下方会使用另外一个案例进行具体分析。那么，接下来让我们详细展开。

Build Script ｜文档

从编译的角度来看，当一个 Package 被编译时，Cargo 会首先编译这个 build script，再进行后续的编译操作。你可以认为 Build Script 只是另一个 Package，并在当前的 Package 编译前先进行了编译。事实上确实如此，我们能在 Target 中找到两组产物，其中一组便是 Build script 的产物。

从事务的角度出发，Build Script 对于 Sys crate 来说，一般会做一些源码编译、lib 搜索相关的事务，而对于 Turbopack 来说，则是进行了注册、代码生成相关的事项。总之，尽管它被叫做 build script，而现实世界中，理论上你可以用来对他做任何事情，甚至是发送一个 HTTP 请求或做一些危及计算机安全的事情，Rust 的 Secure code team 还为此发起了相关是否要做 Build-time Sandbox 的*讨论* 。

默认情况下，你可以直接在 Package 的根目录中生成一个带有 fn main 的 build.rs 来作为 build script：

1
2
3
4

csharp复制代码// build.rs
fn main() {
 
}

如果在 build script 的执行过程中发生了 panic，则不会对该 Package 进行后续的编译流程。

值得注意的是，在 build script 中的一切 print 操作是不会被打印到 stdio 上的

1
2
3
4

arduino复制代码// build.rs
fn main() {
 println!("hello from build.rs"); // 没有用
}

对于 print 来说，你可以在产物文件夹下 output 文件中找到对应的输出，对于 dbg! 的相关输出则可以在产物文件夹中的 stderr 文件中找到（这个 macro 的本质是 stderr 的 output）

对于为什么不对 print 相关的内容进行控制台的输出，*官方*给出的理由是不想制造更多的噪音。因为我们在 build script 中还有一件大事可以做，那就是调用 print 生成 Cargo Instructions

Cargo Instructions | 文档

这里列举一些常用的 Instructions:

• cargo:rerun-if-changed=PATH — Tells Cargo when to re-run the script.
• cargo:rustc-link-arg=FLAG — Passes custom flags to a linker for benchmarks, binaries, cdylib crates, examples, and tests.
• cargo:rustc-link-lib=LIB — Adds a library to link.
• cargo:rustc-link-search=[KIND=]PATH — Adds to the library search path.
• cargo:rustc-cfg=KEY[="VALUE"] — Enables compile-time cfg settings.
• cargo:rustc-cdylib-link-arg=FLAG — Passes custom flags to a linker for cdylib crates.

除此之外，我们通常也会在 build script 中获取相关 env 字段，常见的有 OUT_DIR，CARGO_FEATURE_XXX 等等，这些都可以通过 std::env::var 获得，如果你希望忽略 UTF-8 的校验，则可以用性能更好的 std::env::var_os 达到几乎相同的效果。

这些都是日常开发上基本会用到的相关内容，在这之上，对于一个 Sys crate 的编译来说，我们通常会对本机的 lib 进行查找，从而引导 rustc 完成对该 lib 的 linking。

Pattern

暂时无法在飞书文档外展示此内容

通常情况下，我们会在一个版本号区间内查找系统中存在的 lib 包，如果不存在则进行基于源码的构建。

这里我们可以以 libgit2 作为参考，就不在本文中详细展开了。

Foreign Function Interface (FFI)

A foreign function interface (FFI) is a mechanism by which a program written in one programming language can call routines or make use of services written in another. From Wikepedia

FFI 可以让跨语言的程序之间完成相互的调用。就像 IPC(Inter-process communication)一样需要建立一套 protocol，FFI 同样也是一种满足了约定的规则(如：Calling conventions 等, ABI)的调用，Rust 支持的 ABI 可以在这里找到。由于 C 的 ABI 在同一个平台上是兼容的，因此大部分库都是建立在 C ABI 上的。

ABI 和 C ABI?

ABI(Application Binary Interface) 和 API(Application Programming Interface)非常相似，前者描述了 Binary 的兼容性，这其中包括了各种数据类型的 size 和 alignment、内存布局（Layout）以及系统的调用约定（用来描述例如参数是怎么被传递的等等，例如：x86 calling conventions），甚至包括了 Compiler 等等之间的一致性（Conformance） 等等。更多

在 C 的标准中，其实是没有对 C ABI 标准的定义的。但对于同一个平台，这些基本是可以被认为是一致的，因此我们基本可以认为它们是兼容的。而对于不同的平台来说，它们系统之间的调用约定可能是不一致的，因此我们认为它们是不兼容的。所以我们在描述 C ABI 的兼容性时，都包涵了一个隐式约定：同一平台

FFI

在 Rust 中我们可以这样来声明，extern “abi”：如 extern “C”

1
2
3

php复制代码extern "C" {
  fn napi_create_object(...)
}

我们不需要手动定义 unsafe，因为 FFI 的调用永远是 unsafe 的。

Reverse FFI

同样的，我们也可以定义对应的 fn 给其他支持该 ABI 的语言调用：

1
2
3
4

rust复制代码#[no_mangle]
pub extern "C" fn napi_register_module_v1(...) {
  // ...
}

需要注意的是，我们需要添加 no_mangle 的标记。否则对应的 symbol name 会被 mangle，而导致调用方无法寻址。你可以使用 nm 命令验证这一点：

1

shell复制代码$ nm <path/to/generated-binary> | grep napi

macOS 下 symbol 会带有一个下划线，可以看到_napi_register_module_v1 被包含在 Symbol table 中：

1

r复制代码0000000000001650 T _napi_register_module_v1

FFI Safety

有了 ABI 的限制，我们可以得到：只有有限的值类型才可以完成跨 FFI 边界的值传递（通信），就像 IPC protocol 也有特定的数据结构的要求，那么，常用的 C ABI 也是一样，简单来说，C 里面无法表达的数据结构，你就不能通过 FFI 这条 Boundary，同样的对于 Rust 的 Error 也是无法通过 FFI 边界的，etc。

要标记一个值为 C ABI Compatible，可以使用 #[repr(C)]，这会让 rustc 开启对应的编译时检查，确保这个类型是 FFI Safe 的：

1
2
3
4
5

rust复制代码#[repr(C)]
struct some_data_type {
  foo: [u8;0],
  bar: usize
}

C的范式还限制了 enum 的传递，但可以用 #[repr(u32, i8, etc..)] and #[repr(C)] 来强制将非 C 范式的 enum 拥有特定的 Memory Layout，因此下面两种类型是可以互相 Interop 的：

1
2
3
4
5
6

scss复制代码#[repr(u8)]
pub enum LineStyle {
    Solid,
    Dotted,
    Dashed,
}

1
2
3
4
5

kotlin复制代码enum class LineStyle: uint8_t {
    Solid,
    Dotted,
    Dashed,
}

更多的信息可以在这里找到

Opaque Type

在 FFI 的交互过程中，有很多值是不希望被访问到其实际内容的。对于熟悉 NAPI 可能了解过 External 类型，它是一个 Opaque Type，这个 Opaque Type 将会通过 FFI 调用获取到，再通过 FFI 作为参数进行传递：

1
2
3
4
5
6
7
8
9

arduino复制代码napi_status napi_create_external(napi_env env,
                                 void* data, // 需要包裹的值
                                 napi_finalize finalize_cb,
                                 void* finalize_hint,
                                 napi_value* result) // 生成的 JS 类型 External Type
                                 
napi_status napi_get_value_external(napi_env env,
                                    napi_value value, // 这个 JS ExternalType
                                    void** result) // 获取到这个值之前被包裹的 Data

得到这两组定义后，我们可以将 data 包裹成一个值做为标志存储在 JS 侧，而 JS 侧是无法感知到内部的数据结构的，一个实际的例子可以参考 NAPI-RS External Type

同样的，我们在 Rust 中也可以定义相关的 Opaque Type：

1
2
3
4
5
6
7
8
9

rust复制代码#[repr(C)]
struct foo_opaque {
 _data: [u8;0],
 _marker: PhantomData<*mut ()> // 标记这个 struct 为 !Send 和 !Sync 的
}

#[no_mangle]
extern "C" fn some_init_function(foo: *const foo_opaque) {
}

这样一来，上述的例子中，在其他语言调用它的时候，你仅能拿到 foo 的指针。

另一个 Opaque Type 的好处在于可以完成类型的区分，我们知道在 C 中，一切任意 Type 的 pointer 都可以用 void 来定义，这在 Rust 中的表示是这样的：

1
2
3
4

php复制代码extern "C" fn some_init_function(foo: *const ::std::os::raw::c_void, 
                                 bar: *const ::std::os::raw::c_void) {
  do_something_with_bar(foo); // 可以编译！                                 
}

但当两个 pointer 均为 c_void 时，则无法区分，也就丢失了 rustc 编译时的类型检查，这是我们希望能够避免的。

写一个 *-sys crate

在这一章节，我们将用 libsodium 作为案例编写一个 libsodium-sys，使其能够完成简单的 hasher 的功能。这个 Demo 中将直接使用 rust-bindgen **完成 binding 的生成。 **由于篇幅的关系，我们将不涉及 vendor 时的“从源码构建”。

准备工作

首先需要安装 libsodium

1
2
3
4

shell复制代码# 通过 brew 安装
$ brew install libsodium

# 通过其他方式进行安装 https://libsodium.gitbook.io/doc/installation

安装完成后可以通过命令验证是否成功：

1

lua复制代码$ pkg-config --libs libsodium

新建一个 libsodium-sys

Cargo.toml:

1
2
3
4
5
6
7
8

ini复制代码[package]
edition = "2021"
name = "libsodium-sys"
version = "0.1.0"

[build-dependencies]
pkg-config = "0.3.1"
bindgen = "0.63.0"

1. 我们通过 pkg-config 查找系统依赖，它可以自动设置 rustc 依赖的参数
2. bindgen 用于基于 libsodium 的 header 生成 FFI Binding

定义 wrapper.h

1

arduino复制代码#include "sodium.h"

我们将需要的 header 文件 sodium.h 添加到 wrapper.h，rust-bindgen 将会编译生成 FFI 声明

编写 build script

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

rust复制代码fn main() {
  // 通过 pkg_config 查找 syslib
  let lib = pkg_config::Config::new()
        .atleast_version("1.0.18")
        .probe("libsodium")
        .unwrap();
        
  println!("cargo:rerun-if-changed=wrapper.h");
  
  // The bindgen::Builder is the main entry point
  // to bindgen, and lets you build up options for
  // the resulting bindings.
  let bindings = bindgen::Builder::default()
    // The input header we would like to generate
    // bindings for.
    .header("wrapper.h")
    .clang_args(
        lib.include_paths
            .iter()
            .map(|p| format!("-I{}", p.display())),
     )
    .allowlist_function("crypto_generichash")
    .allowlist_function("sodium_init")
    .allowlist_var("crypto_generichash_.*")
    // Tell cargo to invalidate the built crate whenever any of the
    // included header files changed.
    .parse_callbacks(Box::new(bindgen::CargoCallbacks))
    // Finish the builder and generate the bindings.
    .generate()
    // Unwrap the Result and panic on failure.
    .expect("Unable to generate bindings");

  // Write the bindings to the $OUT_DIR/bindings.rs file.
  let out_path = PathBuf::from(env::var("OUT_DIR").unwrap());
  bindings
    .write_to_file(out_path.join("bindings.rs"))
    .expect("Couldn't write bindings!");
}

1. 我们通过 pkg-config 查找并 set rustc flags，将 include_paths 添加到 bindgen 的 clang_args 参数
2. 同时当 wrapper.h 变化时，我们需要重新执行 build script
3. allow_list 中添加本次 DEMO 需要用到的 fn, const
4. 最终的 bindings.rs 我们可以在 OUT_DIR 中找到，它是这样的：

编写 binding 并测试

我们可以通过 libsodium 官网的 FFI 定义了解各个字段的作用：Generic hashing

1
2
3
4
5
6
7
8
9
10
11

rust复制代码#![allow(unused)]
#![allow(non_upper_case_globals)]
#![allow(non_camel_case_types)]
#![allow(non_snake_case)]

mod ffi {
  // 内联 bindings.rs 的 codegen 的结果到 mod ffi
  include!(concat!(env!("OUT_DIR"), "/bindings.rs"));
}

pub use ffi::*;

测试部分可以参考

Tips

• 可以使用 pkg-config crate 进行 libs 的查找，查询成功后会自动添加相应的 cargo instructions，省去了手动添加
• 使用 Bindgen 生成的代码是一个“大杂烩”，可以限制导出的内容，如：使用 allowlist 等
• 不建议在 sys crate 中编写除 ffi 声明以外的逻辑，避免 breaking change
• 可以通过 cargo instructions 暴露相关的 metadata 给依赖方，以保持如全局的 lib 版本统一

写一个简单的 napi-sys

在这一章节，我们将创建一个 dynamic library 并调用 napi 完成简单的注册，添加模块导出等功能，并在 Node 中进行测试。

准备工作

我们将会新建两个 crate，第一个 crate 为 napi-sys 用于声明一些 Node 给我们提供的 FFI，完整的 FFI 列表可以参考 N-API 文档。其次，我们将会创建第二个 crate NAPI 用于编写 binding 的测试。

用到的 FFI :

• napi_create_string_utf8

1
2
3
4

arduino复制代码napi_status napi_create_string_utf8(napi_env env,
                                    const char* str,
                                    size_t length,
                                    napi_value* result)

• napi_set_named_property

1
2
3
4

csharp复制代码napi_status napi_set_named_property(napi_env env,
                                    napi_value object,
                                    const char* utf8Name,
                                    napi_value value);

用到的 Reverse FFI :

由于当前插件为 dynamic library，我们需要在 crate NAPI 中导出注册的钩子，用于在运行时完成 Module 的注册：

• napi_register_module_v1：现在 Register 的版本号为 1，可以参考这里

1
2

java复制代码napi_value napi_register_module_v1(napi_env env,
                                   napi_value exports)

用到的返回值：

• napi_status: NAPI 调用成功与否，0 为成功

我们需要在 Rust 侧创建一个 named export，它的 key 为 foo，值为 bar，最终的效果是这样的：

1
2

javascript复制代码const foo = require("./binding.node").foo;
console.log(foo) // bar

[live-coding]

完整的代码示例：github.com/h-a-n-a/bui…

可能遇到的问题

• 在 Clang(macOS 默认) 中你需要使用 -undefined, dynamic_lookup 来标记 linker symbol 查找的行为（在 Runtime 中查找，-C 表示 codegen flags），否则会产生找不到 Symbol 的编译报错：

1
2
3
4
5
6
7
8
9
10
11

ini复制代码[target.x86_64-apple-darwin]
rustflags = [
  "-C", "link-arg=-undefined",
  "-C", "link-arg=dynamic_lookup",
]

[target.aarch64-apple-darwin]
rustflags = [
  "-C", "link-arg=-undefined",
  "-C", "link-arg=dynamic_lookup",
]

图 1.1： LLVM 架构图 blog.gopheracademy.com/advent-2018…

图 1.2: Linker **en.wikipedia.org/wiki/Linker…

Linker 有什么用?

编译器的架构：Frontend(C -> Clang) -> LLVM Optimizer -> LLVM Backend（图1.1）

Linker 的作用(图 1.2)

• 由于我们希望生成的是一个基于 C ABI 的 dynamic library，因此需要在 cargo.toml 中标记：

1
2

ini复制代码[lib]
crate-type = ["cdylib"]

Tips

• 可以用 nm 查看 binary 中的 Symbol，如：

1
2
3

markdown复制代码                 U _napi_create_string_utf8
00000000000015b0 T _napi_register_module_v1
                 U _napi_set_named_property

T 代表 Global text symbol

U 代表 Undefined symbol，这正是我们期望的，它将会在宿主环境中提供，例如我们可以简单验证 node 中是否定义了 napi_create_string_utf8：

1

ruby复制代码$ nm $(which node) | grep napi_create_string_utf8

我们便能得到对应的 FFI 定义

1

r复制代码0000000100087c00 T _napi_create_string_utf8

FFI 的定义和声明的区别是什么？

在上述例子中，我们的 napi-sys crate 仅仅完成了 FFI 的声明，就好比你直接引用了 napi 的 header file，而只有在对应 Node binary 中定义了这些 FFI 后你才能使用。这也是为什么 FFI 永远是 unsafe 的原因之一

• 可以用 file 查看文件的类型，如：

1

复制代码file binding.node

我们可以得到这是一个 x86_64-apple-darwin（通过 Apple iMac 3.8 GHz 8-Core Intel Core i7 编译） 的 shared library：

1

arduino复制代码binding.node: Mach-O 64-bit dynamically linked shared library x86_64

交叉编译

通常情况而言，一个平台只能编译出当前平台支持的可执行代码，而交叉编译则是想解决跨平台编译的问题。如在 M1(aarch64-apple-darwin) 上编译出 x86_64-linux-gnu 的代码（每一种 compiler 的 triple 写法都不太一样，这里列举了 Rust 的）。Rust 提供了开箱即用的 cross-compilation 支持，你只需要安装 target 对应的 toolchain 即可：

1

sql复制代码$ rustup target add x86_64-unknown-linux-gnu

然后使用 Cargo build –target 进行编译：

1

css复制代码$ cargo build --target x86_64-unknown-linux-gnu

对于编译一个项目来说，仅仅支持不同 target 的标准库是大概率不够用的，对于不同的 target 你也许需要使用不同的 Linker 等，这些都可以在 .cargo/config.toml 文件中定义，详细内容可以参考 The Cargo Book。大致的设置是这样的：

1
2

ini复制代码[target.x86_64-unknown-linux-gnu]
linker = "x86_64-unknown-linux-gnu-gcc"

Linux 的一些 C 标准库

• GNU (glibc)
• Musl

对于 gnu 输出的一般是动态链接的 binary，需要在使用方的电脑上安装 glibc。而 musl 则是静态链接（你可以认为就是一个 Tree-shaked 过的 Bundle）的，Bundle 的体积会变大一些，但优势在于它不需要任何的 Dependency。

你会发现，如果我们需要 cross-compile 多个平台，则需要完成多个平台的参数的调优（不同的 Compiler 的参数还不太一样），这让人非常头疼。这个时候，Zig cc 可以非常好地帮助我们解决这一系列问题。

Zig

从语言的角度看，Zig 是一个非常轻量级的静态语言，它没有Macro 等等。除此之外，它提供了非常好的 C Interoperability，你甚至可以直接 include 一个 C 的 header。除此之外它还是一个 C/C++ Compiler，底层调用的是 Clang，令人吃惊的是它竟然兼容了 Clang 和 gcc 的编译参数！从原理上来说，它承担了和 Clang 沟通的角色，截获部分需要的指令，如 --target 等，加以处理后交给 Clang 进行后续的编译流程，如：

1
2
3

ruby复制代码$ zig cc -target x86_64-linux-gnu ...
⬇️
$ clang xxx

那么如何将 Zig 应用到我们的工作流上呢？首先在任意位置创建一个 zcc 的文件（Zig cc），如：

1
2

bash复制代码#!/bin/sh
zig cc -target x86_64-linux-gnu $@

在对应的 .cargo/config.toml 中完成对 linker 的设置：

1
2

ini复制代码[target.x86_64-unknown-linux-gnu]
linker = "path/to/zcc"

调用 Cargo build 即可：

1

css复制代码$ cargo build --target x86_64-unknown-linux-gnu

测试

如果需要对 binding 进行测试，建议还是 follow docker。推荐所有大型项目，能不用交叉编译就不用，因为最后它们均要完成在各个平台上的测试，以验证编译后的产物的正确性。

Reference

Build Script

doc.rust-lang.org/cargo/refer…

FFI

www.youtube.com/watch?v=peP…

doc.rust-lang.org/nightly/nom…

doc.rust-lang.org/nightly/nom…

nickdesaulniers.github.io/blog/2016/0…

交叉编译

actually.fyi/posts/zig-m…

doc.rust-lang.org/cargo/refer…

rustc-dev-guide.rust-lang.org/backend/cod…

andrewkelley.me/post/zig-cc…

www.aosabook.org/en/llvm.htm…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

一、前言

为什么有这篇文章？当时有人问我下面这个点击button，网页应该变成什么样？
注意他们的key是相同的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

js复制代码import React, { useState } from "react";

function Demo2() {
  const [count, setCount] = useState(0);

  return (
    <div>
      <button onClick={() => setCount((i) => i + 1)}>点击Count+1</button>
      <h3 key={count}>大{count}</h3>
      <h2 key={count}>舌{count}</h2>
      <h1 key={count}>头{count}</h1>
    </div>
  );
}

export default Demo2;

我去看了7km老师的博客
收集到了答案

答案和你想象的一样吗？？不一样就继续往下看看呗！！！结尾有答案滴

二、前置概念

react框架可以用来表示，输入状态 —> 吐出ui。

1

php复制代码const ui = fn(state)

react架构是什么？

可以分为如下三层：

1. scheduler（调度器）：用来分发优先级更高的任务。
2. render阶段（协调器）：找出哪些节点发生了变化，并且给相应的fiber打上标签。
3. commit阶段（渲染器）：将打好标签的节点渲染到视图上。遍历effectList执行对应的dom操作或部分生命周期

1. 输入: 将每一次更新(如: 新增, 删除, 修改节点之后)视为一次更新需求(目的是要更新DOM节点).
2. 注册调度任务: react-reconciler收到更新需求之后, 并不会立即构造fiber树, 而是去调度中心scheduler注册一个新任务task, 即把更新需求转换成一个task.
3. 执行调度任务(输出): 调度中心scheduler通过任务调度循环来执行task

1. fiber构造循环是task的实现环节之一, 循环完成之后会构造出最新的 fiber 树.
2. commitRoot是task的实现环节之二, 把最新的 fiber 树最终渲染到页面上, task完成.

主干逻辑就是输入到输出这一条链路, 为了更好的性能(如批量更新, 可中断渲染等功能), react在输入到输出的链路上做了很多优化策略, 任务调度循环和fiber构造循环相互配合就可以实现可中断渲染.

ReactElement, Fiber, DOM 三者的关系

上面我们大概提及了一下react的架构和更新的粗略流程，考虑到本文的重点是Render阶段发生了啥，接下来上重量级嘉宾JSX,ReactElement, Fiber, DOM。以下面这个jsx代码为例，讲解三者的关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

javascript复制代码function Test() {
  const [showName, setShowName] = useState(true);
  return (
    <div>
      <div>今天肯德基疯狂星期八，和我一起玩彩虹六？</div>
      <ul>
        <li>抱枕一号</li>
        {showName && <li>抱枕二号</li>}
      </ul>
      <div
        onClick={() => {
          setShowName(false);
        }}
      >
        点击让高启强少一个小弟
      </div>
    </div>
  );
}

createElement源码

所有采用JSX语法书写的节点, 都会被编译器转换, 最终会以React.createElement(...)的方式, 创建出来一个与之对应的ReactElement对象.

这也是为什么在每个使用JSX的JS文件中，你必须显式的声明 import React from 'react';(17版本后不需要）否则在运行时该模块内就会报未定义变量 React的错误。

ReactElement数据结构和内存结构（结合上面jsx示例代码）

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

typescript复制代码export type ReactElement = {
  // 用于辨别ReactElement对象形式
  $$typeof: any,

  // 内部属性
  type: any, // 表明其种类
  key: any,
  ref: any,
  props: any,

  // ReactFiber 记录创建本对象的Fiber节点, 还未与Fiber树关联之前, 该属性为null
  _owner: any,

  // __DEV__ dev环境下的一些额外信息, 如文件路径, 文件名, 行列信息等
  _store: {validated: boolean, ...},
  _self: React$Element<any>,
  _shadowChildren: any,
  _source: Source,
};

内存结构

Fiber 对象数据结构

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

typescript复制代码export type Fiber = {|
  tag: WorkTag,
  key: null | string, // 和ReactElement组件的 key 一致.
  elementType: any,//一般来讲和ReactElement组件的 type 一致 比如div ul
  type: any, // 一般来讲和fiber.elementType一致. 一些特殊情形下, 比如在开发环境下为了兼容热更新
  stateNode: any, // 真实DOM是谁
  return: Fiber | null, //爹是谁
  child: Fiber | null, //孩子是谁
  sibling: Fiber | null, //兄弟是谁
  index: number, 
  ref:
    | null
    | (((handle: mixed) => void) & { _stringRef: ?string, ... })
    | RefObject, //指向在ReactElement组件上设置的 ref
  pendingProps: any, // 从`ReactElement`对象传入的 props. 用于和`fiber.memoizedProps`比较可以得出属性是否变动
  memoizedProps: any, // 上一次生成子节点时用到的属性, 生成子节点之后保持在内存中
  updateQueue: mixed, // 存储state更新的队列, 当前节点的state改动之后, 都会创建一个update对象添加到这个队列中.
  memoizedState: any, // 用于输出的state, 最终渲染所使用的state
  dependencies: Dependencies | null, // 该fiber节点所依赖的(contexts, events)等
  mode: TypeOfMode, // 二进制位Bitfield,继承至父节点,影响本fiber节点及其子树中所有节点. 与react应用的运行模式有关(有ConcurrentMode, BlockingMode, NoMode等选项).

  // 优先级相关
  lanes: Lanes, // 本fiber节点的优先级
  childLanes: Lanes, // 子节点的优先级
  alternate: Fiber | null, // 双fiber缓存 指向内存中的另一个fiber, 每个被更新过fiber节点在内存中都是成对出现(current和workInProgress)
|};

内存结构

ReactElement, Fiber, DOM 三者的关系

React的启动过程发生了啥

接下来介绍的都是当前稳定版legacy 模式

1

javascript复制代码ReactDOM.render(<App />, document.getElementById('root'), dom => {});

在没有进入render阶段（react-reconciler包）之前,reactElement(<App/>)和 DOM 对象div#root之间没有关联。

在react初始化的时候，会创建三个全局对象，在三个对象创建完毕的时候，react初始化完毕。

1. ReactDOMRoot对象

1. 属于`react-dom`包，该对象暴露有render,unmount方法, 通过调用该实例的`ReactDOM.render`方法, 可以引导 react 应用的启动.

2. fiberRoot对象

1. 属于`react-reconciler`包,在运行过程中的全局上下文, 保存 fiber 构建过程中所依赖的全局状态，
2. 其大部分实例变量用来存储`fiber构造循环`过程的各种状态，react 应用内部, 可以根据这些实例变量的值, 控制执行逻辑。

3. HostRootFiber对象

1. 属于`react-reconciler`包，这是 react 应用中的第一个 Fiber 对象, 是 Fiber 树的根节点, 节点的类型是`HostRoot`.

这 3 个对象是 react 体系得以运行的基本保障, 除非卸载整个应用，否则不会再销毁

此刻内存中各个对象的引用情况表示出来，此时reactElement(<App/>)还是独立在外的, 还没有和目前创建的 3 个全局对象关联起来

到此为止, react内部经过一系列运转, 完成了初始化。

三、render阶段发生了啥

以下所有示例按照下面的代码 请注意

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

javascript复制代码class App extends React.Component {
state = {
  list: ['A', 'B', 'C'],
};
onChange = () => {
   this.setState({ list: ['C', 'A', 'X'] });
};
componentDidMount() {
  console.log(`App Mount`);
}
render() {
  return (
    <>
      <Header key='d' />
      <button key='e'>change</button>
      <div className="content" key='f'>
      {this.state.list.map(item => (
         <p key={item}>{item}</p>
       ))}
      </div>
    </>
  );
 }
}

class Header extends React.PureComponent {
render() {
   return (
   <>
    <h1>title</h1>
    <h2>title2</h2>
   </>
  );
 }
}

双缓冲fiber技术

在上文我们梳理了ReactElement, Fiber, DOM三者的关系, fiber树的构造过程, 就是把ReactElement转换成fiber树的过程. 但是在这个过程中, 内存里会同时存在 2 棵fiber树:

• 其一: 代表当前界面的fiber树(已经被展示出来, 挂载到fiberRoot.current上). 如果是初次构造(初始化渲染), 页面还没有渲染, 此时界面对应的 fiber 树为空(fiberRoot.current = null).
• 其二: 正在构造的fiber树(即将展示出来, 挂载到HostRootFiber.alternate上, 正在构造的节点称为workInProgress). 当构造完成之后, 重新渲染页面, 最后切换fiberRoot.current = workInProgress, 使得fiberRoot.current重新指向代表当前界面的fiber树.

React入口初始化内存情况

在进入react-reconciler包之前,也就是还没render时, 内存状态图如下，和上面启动过程的图对应:

fiber 树构造方式

1. 初次创建: 在React应用首次启动时, 界面还没有渲染, 此时并不会进入对比过程, 相当于直接构造一棵全新的树.
2. 对比更新: React应用启动后, 界面已经渲染. 如果再次发生更新, 创建新fiber之前需要和旧fiber进行对比. 最后构造的 fiber 树有可能是全新的, 也可能是部分更新的.

在深度优先遍历中, 每个fiber节点都会经历 2 个阶段:

1. 探寻阶段 beginWork
2. 回溯阶段 completeWork

beginWork探寻阶段发生了什么源码地址

1. 创建节点：根据 ReactElement对象创建所有的fiber节点, 最终构造出fiber树形结构(设置return和sibling指针)
2. 给节点打标签：设置fiber.flags(二进制形式变量, 用来标记 fiber节点 的增,删,改状态, 等待completeWork阶段处理)
3. 设置真实DOM的局部状态：设置fiber.stateNode局部状态(如Class类型节点: fiber.stateNode=new Class())

completeWork回溯阶段发生了什么源码地址

1. 调用completeWork

1. 给`fiber`节点(tag=HostComponent, HostText)创建 DOM 实例, 设置`fiber.stateNode`局部状态(如`tag=HostComponent, HostText`节点: fiber.stateNode 指向这个 DOM 实例).
2. 为 DOM 节点设置属性, 绑定事件(`合成事件原理`).
3. 设置`fiber.flags`标记

2. 把当前 fiber 对象的副作用队列(firstEffect和lastEffect)添加到父节点的副作用队列之后, 更新父节点的firstEffect和lastEffect指针.
3. 识别beginWork阶段设置的fiber.flags, 判断当前 fiber 是否有副作用(增,删,改), 如果有, 需要将当前 fiber 加入到父节点的effects队列, 等待commit阶段处理.

初次创建

这有一个动画 具体如果想看流程图可以点击

下面标注了生成时期的 beginWork 和 completeWork 执行过程

1
2
3
4
5
6

js复制代码  // 将最新的fiber树挂载到root.finishedWork节点上 下面绿色粗线表示指针
  const finishedWork: Fiber = (root.current.alternate: any);
  root.finishedWork = finishedWork;
  root.finishedLanes = lanes;
  // 进入commit阶段
  commitRoot(root);

动画演示了初次创建fiber树的全部过程, 跟踪了创建过程中内存引用的变化情况. fiber树构造循环负责构造新的fiber树, 构造过程中同时标记fiber.flags, 最终把所有被标记的fiber节点收集到一个副作用队列中, 这个副作用队列被挂载到根节点上(HostRootFiber.alternate.firstEffect). 此时的fiber树和与之对应的DOM节点都还在内存当中, 等待commitRoot阶段进行渲染

对比更新的时候发生了什么

1.优化原则

1. 只对同级节点进行对比，如果DOM节点跨层级移动，则react不会复用

* 我们可以从同级的节点数量将Diff分为两类：


    + 当newChild类型为JSX对象、number、string，代表同级只有一个节点
    + 当newChild类型为Array，同级有多个节点

2. 不同类型的元素会产出不同的结构，会销毁老的结构，创建新的结构
3. 可以通过key标示移动的元素
4. 类型一致的节点才有继续diff的必要性

• 单节点对应演示,可以去浏览器的Elements->Properties查看

• 多节点对应演示

diff算法介绍

1.单节点

1. 如果是新增节点, 直接新建 fiber, 没有多余的逻辑
2. 如果是对比更新

* 如果`key`和`type`都相同，则复用
* 否则新建

单节点的逻辑比较简明, 源码

2.多节点

1. 多节点一般会存在两轮遍历，第一轮寻找公共序列，第二轮遍历剩余非公共序列
2. 第一次循环 源码
   1. let i = 0，遍历newChildren，将newChildren[i]与oldFiber比较，判断DOM节点是否可复用。
   2. 如果可复用，i++，继续比较newChildren[i]与oldFiber.sibling，可以复用则继续遍历。
   3. 如果不可复用，分两种情况：
   • key不同导致不可复用，立即跳出整个遍历，第一轮遍历结束。
   • key相同type不同导致不可复用，会将oldFiber标记为DELETION，并继续遍历
   4. 如果newChildren遍历完（即i === newChildren.length - 1）或者oldFiber遍历完（即oldFiber.sibling === null），跳出遍历，第一轮遍历结束。

1. 第二次循环: 遍历剩余非公共序列, 优先复用 oldFiber 序列中的节点。
   • 如果newChildren与oldFiber同时遍历完，diff结束
   • 如果 newChildren没遍历完，oldFiber遍历完，意味着没有可以复用的节点了，遍历剩下的newChildren为生成的workInProgress fiber依次标记Placement。
   • 如果newChildren遍历完，oldFiber没遍历完，意味着有节点被删除了，需要遍历剩下的oldFiber，依次标记Deletion。
   • 如果newChildren与oldFiber都没遍历完 (重点)源码

+ 先去`声明map数据结构`，遍历一遍老节点，把老fiber的key做映射 {元素的key：老的fiber节点}，
+ 继续遍历新`jsx`，如果`map`有`key`，会把`key`从`map`中删除，说明可以复用，把当前节点标记为`更新`。新地位高的不动，新地位低的动（中间插入链表比链表屁股插入费劲）所以地位低的动动。
+ `lastPlaceIndex`指针，指向最后一个不需要动的老节点的`key`。每次新jsx复用到节点，`lastPlaceIndex`会指向老节点的最后一个成功复用的老`fiber`节点。如果新复用的节点key小于`lastPlaceIndex`，说明老`fiber`节点的顺序在新`jsx`之前，需要挪动位置接到新`jsx`节点后面。
+ 如果`jsx`没有复用的老`fiber`，直接插入新的
+ `map`中只剩还没被复用的节点，等着新的`jsx`数组遍历完，`map`里面的`fiber`节点全部设置为删除

下面动画展示了fiber的对比更新过程 每一张流程图链接

四、检验学习成果

为什么网页会变成那个样子？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

javascript复制代码import React, { useState } from "react";

function Demo2() {
  const [count, setCount] = useState(0);

  return (
    <div>
      <button onClick={() => setCount((i) => i + 1)}>点击Count+1</button>
      <h3 key={count}>大{count}</h3>
      <h2 key={count}>舌{count}</h2>
      <h1 key={count}>头{count}</h1>
    </div>
  );
}

export default Demo2;

五、参考

7km：7kms.github.io/react-illus…

冴羽：juejin.cn/post/716098…

卡颂：react.iamkasong.com/preparation…

xiaochen1024.com/article_ite…

如果有错误的话欢迎大家帮忙指正嗷！！！强烈推荐7km的图解react！
谢谢大家～～～～

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

背景

一切的一切都要从一场惨无人道的面试开始说起。年少的小李怀揣着对职场的憧憬，悻然的来到一家高大上的互联网公司面试求职，他所面试的岗位是「前端开发工程师」。面试前小李已经熟读前端八股文、react 和 vue 的各种大法，然而他不知道的是，一个阴谋的老油条面试官「老余」将要摧残这朵即将踏上职场的小花骨朵。

初入江湖

面试官「老余」看了看小李的简历说道：『看你的项目简历，你对 react 和 vue 比较熟悉，那这样吧，你手写一个响应式，满足以下条件』

1
2
3
4
5
6
7

javascript复制代码var obj = { a: 1 };

var fn = () => {
  console.log(obj.a);
}

// 实现目标：当 obj.a 改变时 fn 函数自动执行

看到这个面试题，小李内心十分开心，这不就是网上经常可以搜到的面试题吗。核心点就是 Object.defineProperty这个 API，它能够拦截对象的 get、set操作

Object.defineProperty 可以拦截对象的 set 和 get 操作，支持三个参数

• target 源对象
• key 需要操作的 key
• config
  • get 、 set 拦截器
  • value 属性值
  • enumerable 是否可枚举
  • writeable 是否可修改属性的值
  • configurable 是否可删除、可修改属性特性

于是小李三两下就完成了以下的 coding

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

javascript复制代码let value;
const reacitve = (obj) => {
  value = obj.a;

  Object.defineProperty(obj, "a", {
    get: () => {
      return value;
    },
    set: (val) => {
      value = val;
      fn();
    }
  });

  return obj;
};

// 测试
var obj = reacitve({ a: 1 });
var fn = () => {
  console.log(obj.a);
};

fn();

obj.a = 2;

问题百出

面试官「老余」看着小李写完的代码，不经眉头一皱，十分生气的说道：『你写的什么乱七八糟的东西，为什么 set 拦截器里写死了执行 fn，而且我需要支持所有属性都能响应式。你令我有点失望，重新写吧』。小李重新审视了下题目，的确发现问题百出。针对面试官的第二个问题（支持所有属性都能响应式），直接遍历就可以了。但是第一个问题（如何何知道哪个函数依赖当前对象）该如何解决呢？
这时小李灵光一闪 JS 是单线程的，也就是说同一时间只可能有一个函数在运行，所以我只要给函数封装下就可以了，于是便有了下面的代码👇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

javascript复制代码let preObj = {};
let runner = undefined;
let deps = {};

const reacitve = (obj) => {
  preObj = { ...obj };
  Object.keys(obj).forEach((key) => {
    Object.defineProperty(obj, key, {
      get: () => {
        // 收集依赖
        if (runner) {
          if (Array.isArray(deps[key])) {
            deps[key].push(runner);
          } else {
            deps[key] = [runner];
          }
        }
        return preObj[key];
      },

      set: (newValue) => {
        preObj[key] = newValue;

        (deps[key] || []).forEach((run) => run());
      }
    });
  });
};

const run = (fn) => {
  runner = fn;
  fn();
  runner = undefined;
};

// 测试

const count = {
  value1: 1,
  value2: 2
};

reacitve(count);

function print1() {
  console.log("print1", count.value1, count.value2);
}

run(print1);

count.value1 = 2;
count.value2 = 3;

步入险境

面试官老余看完代码后说道：『的确能满足我的需求，但是还是有很多问题。首先你没有解决数组变异问题、其次你的代码不支持深度对象』

Tips: 数组变异是指，数组的某些方法调用后会修改原数组。例如 push方法

听完后，小李有些紧张，看来碰到老司机了。解决深度对象还好，用个递归就行了。但如果要解决数组变异有两种方式：

• 重写数组的所有变异方法，在变异方法内对数组再次进行响应式监听
• 使用 Proxy 这个新特性

Proxy 和 Object.definePropery 区别

• Proxy代理整个对象，Object.defineProperty只代理对象上的某个属性
• Proxy不兼容IE，Object.defineProperty不兼容IE8及以下
• Proxy 天然支持数组的操作，Object.defineProperty 需要一些骚操作
• Proxy 只是代理原对象，而 Object.defineProperty 会修改原对象

权衡之下，小李决定用 Proxy来实现响应式，见如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

javascript复制代码const isObj = (_) => _ && typeof _ === "object";
const proxyDeps = new WeakMap();
let runner = undefined;

export const makeProxy = (target) => {
  proxyDeps.set(target, []);

  return new Proxy(target, {
    get: (target, key) => {
      const deps = proxyDeps.get(target) || {};

      if (typeof runner === "function") {
        if (!deps[key]) {
          deps[key] = [];
        }

        deps[key].push(runner);
        proxyDeps.set(target, deps);
      }
      return target[key];
    },
    set: (target, key, value) => {
      const deps = proxyDeps.get(target) || {};
      const oldValue = target[key];

      target[key] = value;

      if (oldValue !== target[key]) {
        (deps[key] || []).forEach((dep) => {
          dep();
        });
      }

      return true;
    }
  });
};

export const reactive = (target) => {
  if (!isObj(target)) {
    throw Error("只支持对象、数组");
  }

  Object.entries(target).forEach(([key, value]) => {
    if (isObj(value)) {
      target[key] = reactive(value);
    }
  });

  return makeProxy(target);
};

export const reactiveRunner = (fn) => {
  runner = fn;
  fn();
  runner = undefined;
};

const count = reactive({ value: 1 });

function print1() {
  console.log("print1", count.value);
}

reactiveRunner(print1);

count.value = 2;

这里使用了 WeakMap，那么 WeakMap 和 Map 以及 对象有什么区别呢？

• Map 和对象的区别：
  • 对象：对象的 key 必须是单一类型，并且只能是整数、字符串或是Symbol类型、对象不报序
  • Map: Map 的 key可以为任意数据类型（Object, Array等）、保留所有元素的顺序
• WeakMap 和 Map 的区别：
  • Map: key 可以是任意类型、可以遍历
  • WeakMap: key 只接受对象作为键（弱引用，key 所指的对象被 gc 回收后，key 便无效）、不可遍历

适配框架

不知不觉时间已经过去 10 分钟了，小李自信的把代码交给面试官看。面试官老余仔细的审查之后说：『小伙子不做，这么快就能满足我的需求了，但是呢，我们公司主要是用 React 技术栈的，如果我想在 React Hooks 组件里使用这个响应式该如何去实现呢？』。小李木讷的看着面试官油光发亮的脑门，心里嘀咕着『我算是要栽在你手里了，没办法了只能上了』。小李思考了下：如何在 React 里使用其实不难，只需要把 React 组件当成一个函数就行了，于是便有了以下代码
注意：响应式的代码没有改动，只是新增了一个 watch 高阶组件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

javascript复制代码import React, { useEffect, useRef, useState } from "react";
import { runner } from "./reactive";

export const watch = (Component) => {
  return React.memo((props) => {
    const [, setUpdateCount] = useState(0);
    const mountedRef = useRef(false);
    const update = () => {
      setUpdateCount((pre) => pre + 1);
    };

    if (!mountedRef.current) {
      runner = update;
    }

    useEffect(() => {
      runner = undefined;
    }, []);

    return <Component {...props}/>;
  });
};

使用方式同 redux saga dva 等框架提供的高阶组件类似

精益求精

面试官老余看着小李的代码心想『这小伙子可以呀，不一会就写出来了。但是不行我必须要难倒他』，于是老余就说：『代码是可以的，但是不够完善。还是很多问题，你看看该怎么解决？』
问题：

• 1、如果是组件里面引用了子组件，你该如何正确的知道是哪个组件依赖了当前对象的，另外当对象更新时如何做到只更新对应的子组件
• 2、如何在组件或者函数销毁时取消依赖
• 3、对象同步更新后，如何将组件的批量更新转为单次更新

这几个问题如晴天霹雳打在小李的头上，为了得到工作早日迎娶白富美走上人生巅峰。小李没办法只能硬抗了。思考了几分钟之后便有了一个初步的方案：
解决方案：

• 1、通过堆栈的形式对 runner 进行改造
• 2、增加一个 WeakMap 用来计算 runner 和响应式对象的依赖，组件销毁时通过这个 map 反向删除依赖
• 3、维护一个任务队列，异步进行处理

更新后的代码如下（代码太多，这里只针对以上问题展示差异代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

javascript复制代码export const makeProxy = (proxyTarget) => {
  proxyDeps.set(proxyTarget, {});

  return new Proxy(proxyTarget, {
    get: (target, key, receiver) => {
      const current = currentRunner();
      const deps = proxyDeps.get(target) || {};
      const value = target[key];

      if (typeof current === "function") {
        // 这里用来收集依赖
        proxyDeps.set(target, cureent);
        // 这里反向收集函数和 target 的关系，函数销毁时用来销毁依赖关系
        proxyDepsKey.set(current, target);
      }

      return target[key];
    },

    set: (target, key, value, receiver) => {
      const deps = proxyDeps.get(target) || {};
      const oldValue = target[key];

      target[key] = isObj(value) ? reactive(value) : value;

      if (oldValue !== target[key]) {
        // 依赖函数加入到异步的执行队列
        queue.add(xxxx)
      }

      return true;
    }
  });
};

export const reactive = (target) => {
  if (!isObj(target)) {
    throw Error("只支持对象、数组");
  }

  // 递归
  Object.entries(target).forEach(([key, value]) => {
    if (isObj(value)) {
      target[key] = reactive(value);
    }
  });

  return makeProxy(target);
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

javascript复制代码// run.js 用来处理运行函数的模块
import { runningFN, proxyDepsKey, proxyDeps } from "./constants";

export const currentRunner = () => {
  return runningFN[runningFN.length - 1];
};

export const run = (fn) => {
  run.start(fn);
  fn();
  run.end();
};

run.start = (fn) => {
  runningFN.push(fn);
};

run.end = (fn) => {
  runningFN.pop(fn);
};

run.destory = (fn) => {
  // 1、通过 proxyDepsKey 和 proxyDeps 两个 map 找到当前 fn 依赖了哪些对象
  // 2、将对象的的 deps 里删除掉 fn
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

javascript复制代码class Queue {
  constructor() {
    this.queue = new Set();
    this.status = "stop";
  }

  add(fn) {
    this.queue.add(fn);

    if (this.status === "stop") {
      this.status = "pending";

      Promise.resolve().then(() => {
        this.status = "running";
        Array.from(this.queue).forEach((fn) => fn());
        this.status = "stop";
      });
    }
  }
}

export default new Queue();

极致性能

全部完成后，小李洋洋得意的把最终 coding 代码交给面试官，这时整体的响应式以及和 React 组件的交互都已经初步成形了。面试官老余端详后心里又开始想：『看来小伙子有把刷子，容老夫看看还有哪里可以刁难一下他的』，思考片刻后，面试官老余发话了：『虽然你完成了我交给你的 coding 任务，但是你缺乏进一步的🤔思考。对细节点的把控有所欠缺。你要学会举一反三。否则我看不到你的亮点。比如说吧，在你的代码基础上，如何解决以下问题呢？』

• 1、如何避免响应式里的重复收集依赖问题？
• 2、如何做到响应式按需收集依赖（并不是在开始时就就深度遍历）？
• 3、异步队列的渲染时机是最好的时机吗？
• 4、Proxy 性能比 Object.definePropery 性能好吗？一定要用 Proxy 吗？
• 5、你的代码里限制了只能对 object 类型进行响应式，那对普通类型如何实现呢？

『当然还有很多其他问题了，我就不一一举例了。我希望看到你对这些问题的思考』
听完这番话后小李陷入了深思 『我擦，看来遇到 PUA 之神，就这么一会儿功夫很难完成呀！得拿出看家功夫了』，小李思考后便针对以上问题一一回复了：

• 1、通过 Map 来判断当前的 key 是否已经收集过依赖，避免重复收集
• 2、开始不递归、在触发 get 时，再对 key 对应的 value 进行深一层的响应式初始化
• 3、Promise 换成 RAF
• 4、Proxy 性能差一点，但是适配性好
• 5、可以通过编译时将普通变量转为对象形式，在使用变量时自动拓展 key。（可以配合开发一个 babel 插件）

1
2
3
4
5
6
7
8
9

javascript复制代码// 源码
const num = reactive(0);

console.log(num);

// 编译后
const num = reactive({ value: 0 });

console.log(num.value)

• 这里说下 Promise 换成 RAF 的思考，我们知道 JS 是单线程的，Promise 是微任务，如何把更新队列的触发放在 Promise 里，还是会有一定概率出现重复渲染的。而 RAF 是在 UI render 发生之前微任务之后执行的，这个地方更合适些，可以参考事件循环的官方介绍 HTML5 事件循环介绍
• 关于 Proxy 和 Object.definePropery 性能比较：同样是拦截 get set，Proxy 性能稍微差点，但是差距不大。但是 Proxy 的适配性更好，这也是为什么 Vue3 里把 Object.definePropery 换成了 Proxy

用一张简单概述下 EventLoop

最后小李把思考后的所有代码都进行了更新，由于篇幅有点长，就直接贴出地址：最终版响应式

巅峰造极

上面的面试基本就结束了，但还是有很多细节点可以深入探索，比如以下几点：

• 1、React 组件如何合并渲染（当响应式触发的重新渲染和组件自身的重新渲染重叠时如何优化）？
• 2、并发渲染队列？
• 3、编译时 & 运行时？

合并渲染

结论是很难做到，除非你去调用 Scheduler Update 队列去合并渲染。用一张图阐述下 React 更新时机。

1
2
3
4
5

javascript复制代码export default App() {
  const [value, setValue] = useState(0);
  
  return <button onClick={() => setValue(pre => pre + 1)}>test{value}</button>
}

图中灰色框框里的阶段会随时被中断、重复执行（由于是在内存中的，所以不会影响真实 DOM）。这样的话我们没办法通过简单的判断 Reconciler 执行的时机，如果想要将它和响应式触发的重新执行合并的话，就得往数据层上着手了
当响应式数据发生改变时，将更新函数设置到 queue 之后，如果同样的 target key 在 queue 执行前被访问了，那么这次 target key 对应的更新函数就直接从 queue 里移除。但是这样方式也不能百分百保证渲染合并

React 渲染队列

上面的代码里没有考虑到 Hooks 里使用异步代码的情况，如果在异步操作没有返回之前，由于响应式数据的改动造成了一次 hook 的重新执行，这时多个异步的竞态可能会引发出意料之外的问题。所以一个比较好的思路是在 watch里维护一个 Hooks 的更新队列，用来存放由于响应式改变而产生的需要 Hook 重新执行的 update 函数。并且这个更新队列需要放在 Hooks 自身导致的执行之后再执行，那么问题又来了，这个任务队列执行的时机放在何时比较何时呢？

• Promise
• setTimeout
• RAF
• getSnapshotBeforeUpdate
• useLayoutEffect
• useEffect

编译时 & 运行时

上述的代码都是运行时的，是否可以将部分代码通过 babel 等插件在编译时自动注入，从而让开发更加简洁？

面试结果

面试了将近一个小时，面试官老余说道『好的，今天面试到此结束，你还有什么其他问题想问我的吗？好的没有就算了，走好不送』。小李诧异的走出了会议室，看着老余那迎风飘扬的发际线不经陷入深思。。。

附录

• 文章中提到的源码
• formily

最后的福利

关注公众号「Goodme前端团队」，获取更多干货实践，欢迎交流分享~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭与你分享每场 LeetCode 周赛的解题报告，一起体会上分之旅。

本文是 LeetCode 上分之旅系列的第 1 篇文章，往期回顾请移步到文章末尾~

大家好，我是小彭。

上周是 LeetCode 第 332 场周赛，你参加了吗？算法解题思维需要长时间锻炼，加入我们一起刷题吧~

2562. 找出数组的串联值（Easy）

题目地址

leetcode.cn/problems/fi…

题目描述

给你一个下标从 0 开始的整数数组 nums 。

现定义两个数字的 串联 是由这两个数值串联起来形成的新数字。

• 例如，15 和 49 的串联是 1549 。

nums 的 串联值 最初等于 0 。执行下述操作直到 nums 变为空：

• 如果 nums 中存在不止一个数字，分别选中 nums 中的第一个元素和最后一个元素，将二者串联得到的值加到 nums 的 串联值 上，然后从 nums 中删除第一个和最后一个元素。
• 如果仅存在一个元素，则将该元素的值加到 nums 的串联值上，然后删除这个元素。

返回执行完所有操作后 nums 的串联值。

题解

简单模拟题，使用双指针向中间逼近即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

kotlin复制代码
class Solution {
    fun findTheArrayConcVal(nums: IntArray): Long {
        var left = 0
        var right = nums.size - 1
        var result = 0L
        while (left <= right) {
            result += if (left == right) {
                 nums[left]
            } else{
                Integer.valueOf("${nums[left]}${nums[right]}")
            }
            left++
            right--
        }
        return result
    }
}

复杂度分析：

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)

2563. 统计公平数对的数目（Medium）

题目地址

leetcode.cn/problems/co…

题目描述

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

• 0 <= i < j < n，且
• lower <= nums[i] + nums[j] <= upper

题解一（排序 + 枚举组合）

题目要求寻找 2 个目标数 nums[i] 和 nums[j] 满足两数之和处于区间 [lower, upper] 。虽然题目强调了下标 i 和下标 j 满足 0 <= i < j < n，但事实上两个数的顺序并不重要，我们选择 nums[2] + nums[4] 与选择 nums[4] + nums[2] 的结果是相同的。因此，第一反应可以使用 “朴素组合模板”，时间复杂度是 O(n2)O(n^2)O(n2)，但在这道题中会超出时间限制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

kotlin复制代码// 组合模板
class Solution {
    fun countFairPairs(nums: IntArray, lower: Int, upper: Int): Long {
        val n = nums.size
        var result = 0L
        for (i in 0 until nums.size - 1) {
            for (j in i + 1 until nums.size) {
                val sum = nums[i] + nums[j]
                if (sum in lower..upper) result++
            }
        }
        return result
    }
}

以示例 1 来说，我们发现在外层循环选择 nums[i] = 4 的一趟循环中，当内层循环选择 [4+4][4 + 4][4+4] 组合不满足条件后，选择一个比 444 更大的 [4+5][4 + 5][4+5] 组合显得没有必要。从这里容易想到使用 “排序” 剪去不必要的组合方案：我们可以先对输入数据进行排序，当内层循环的 nums[j] 不再可能满足条件时提前终止内层循环：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

kotlin复制代码class Solution {
    fun countFairPairs(nums: IntArray, lower: Int, upper: Int): Long {
        // 排序 + 枚举组合
        var result = 0L
        nums.sort()
        for (i in 0 until nums.size - 1) {
            for (j in i + 1 until nums.size) {
                val sum = nums[i] + nums[j]
                if (sum < lower) continue
                if (sum > upper) break
                result++
            }
        }
        return result
    }
}

复杂度分析：

• 时间复杂度：O(nlgn+n2)O(nlgn + n^2)O(nlgn+n2) 快速排序 + 组合的时间，其中 O(n2)O(n^2)O(n2) 是一个比较松的上界。
• 空间复杂度：O(lgn)O(lgn)O(lgn) 快速排序占用的递归栈空间。

题解二（排序 + 二分查找）

使用排序优化后依然无法满足题目要求，我们发现：内层循环并不需要线性扫描，我们可以使用 O(lgn)O(lgn)O(lgn) 二分查找寻找：

• 第一个大于等于 min 的数
• 最后一个小于等于 max 的数

再使用这 2 个边界数的下标相减，即可获得内层循环中的目标组合个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

kotlin复制代码class Solution {
    fun countFairPairs(nums: IntArray, lower: Int, upper: Int): Long {
        // 排序 + 二分查找
        var result = 0L
        nums.sort()
        for (i in 0 until nums.size - 1) {
            // nums[i] + x >= lower
            // nums[i] + x <= upper
            // 目标数的范围：[lower - nums[i], upper - nums[i]]
            val min = lower - nums[i]
            val max = upper - nums[i]
            // 二分查找优化：寻找第一个大于等于 min 的数
            var left = i + 1
            var right = nums.size - 1
            while (left < right) {
                val mid = (left + right - 1) ushr 1
                if (nums[mid] < min) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            val minIndex = if (nums[left] >= min) left else continue
            // 二分查找优化：寻找最后一个小于等于 max 的数
            left = minIndex
            right = nums.size - 1
            while (left < right) {
                val mid = (left + right + 1) ushr 1
                if (nums[mid] > max) {
                    right = mid - 1
                } else {
                    left = mid
                }
            }
            val maxIndex = if (nums[left] <= max) left else continue
            result += maxIndex - minIndex + 1
        }
        return result
    }
}

复杂度分析：

• 时间复杂度：O(nlgn+nlgn)O(nlgn + nlgn)O(nlgn+nlgn) 快速排序 + 组合的时间，内层循环中每次二分查找的时间是 O(lgn)O(lgn)O(lgn)。
• 空间复杂度：O(lgn)O(lgn)O(lgn) 快速排序占用的递归栈空间。

2564. 子字符串异或查询（Medium）

题目地址

leetcode.cn/problems/su…

题目描述

给你一个 二进制字符串 s 和一个整数数组 queries ，其中 queries[i] = [firsti, secondi] 。

对于第 i 个查询，找到 s 的 最短子字符串 ，它对应的 十进制值 val 与 firsti 按位异或 得到 secondi ，换言之，val ^ firsti == secondi 。

第 i 个查询的答案是子字符串 [lefti, righti] 的两个端点（下标从 0 开始），如果不存在这样的子字符串，则答案为 [-1, -1] 。如果有多个答案，请你选择 lefti 最小的一个。

请你返回一个数组 ans ，其中 ans[i] = [lefti, righti] 是第 i 个查询的答案。

子字符串 是一个字符串中一段连续非空的字符序列。

前置知识

记 ⊕ 为异或运算，异或运算满足以下性质：

• 基本性质：x ⊕ y = 0
• 交换律：x ⊕ y = y ⊕ x
• 结合律：(x ⊕ y) ⊕ z = x ⊕ (y ⊕ z)
• 自反律：x ⊕ y ⊕ y = x

题解一（滑动窗口）

题目要求字符串 s 的最短子字符串，使其满足其对应的数值 val ⊕ first = second，根据异或的自反律性质可知（等式两边同异或 first），题目等价于求满足 val = first ⊕ second 的最短子字符串。

容易想到的思路是：我们单独处理 queries 数组中的每个查询，并计算目标异或值 target = first ⊕ second，而目标字符串的长度一定与 target 的二进制数的长度相同。所以，我们先获取 target 的有效二进制长度 len，再使用长度为 len 的滑动窗口寻找目标子字符串。由于题目要求 [left 最小的方案，所以需要在每次寻找到答案后提前中断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

kotlin复制代码class Solution {
    fun substringXorQueries(s: String, queries: Array<IntArray>): Array<IntArray> {
        // 寻找等于目标值的子字符串
        // 滑动窗口
        val n = s.length
        val result = Array(queries.size) { intArrayOf(-1, -1) }
        for ((index, query) in queries.withIndex()) {
            val target = query[0] xor query[1]
            // 计算 target 的二进制长度
            var len = 1
            var num = target
            while (num >= 2) {
                num = num ushr 1
                len++
            }
            for (left in 0..n - len) {
                val right = left + len - 1
                if (s.substring(left, right + 1).toInt(2) == target) {
                    result[index][0] = left
                    result[index][1] = right
                    break
                }
            }
        }
        return result
    }
}

复杂度分析：

• 时间复杂度：O(mn)O(mn)O(mn)，其中 m 是 queries 数组的长度，n 是字符串的长度，在这道题中会超时。
• 空间复杂度：O(1)O(1)O(1)，不考虑结果数组。

题解二（滑动窗口 + 分桶预处理）

事实上，如果每次都单独处理 queries 数组中的每个查询，那么题目将查询设置为数组就没有意义了，而且在遇到目标异或值 target 的二进制长度 len 相同时，会存在大量重复计算。因此，容易想到的思路是：我们可以预先将 queries 数组中所有二进制长度 len 相同的查询划分为一组，使相同长度的滑动窗口只会计算一次。

另一个细节是题目的测试用例中存在相同的查询，所以我们需要在映射表中使用 LinkedList 记录相同目标异或值 target 到查询下标 index 的关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

kotlin复制代码class Solution {
    fun substringXorQueries(s: String, queries: Array<IntArray>): Array<IntArray> {
        // 寻找等于目标值的子字符串
        // 根据长度分桶：len to <target,index>
        val lenMap = HashMap<Int, HashMap<Int, LinkedList<Int>>>()
        for ((index, query) in queries.withIndex()) {
            val target = query[0] xor query[1]
            // 计算 target 的二进制长度
            var len = 1
            var num = target
            while (num >= 2) {
                num = num ushr 1
                len++
            }
            lenMap.getOrPut(len) { HashMap<Int, LinkedList<Int>>() }.getOrPut(target) { LinkedList<Int>() }.add(index)
        }
        // 滑动窗口
        val n = s.length
        val result = Array(queries.size) { intArrayOf(-1, -1) }
        for ((len, map) in lenMap) {
            for (left in 0..n - len) {
                val right = left + len - 1
                val curValue = s.substring(left, right + 1).toInt(2)
                if (map.containsKey(curValue)) {
                    for (index in map[curValue]!!) {
                        result[index][0] = left
                        result[index][1] = right
                    }
                    map.remove(curValue)
                    // 该长度搜索结束
                    if (map.isEmpty()) break
                }
            }
        }
        return result
    }
}

复杂度分析：

• 时间复杂度：O(m+Ln)O(m + Ln)O(m+Ln)，其中 n 是字符串的长度， m 是 queries 数组的长度，L 是不同长度的窗口个数，O(m)O(m)O(m) 是预处理的时间。根据题目输入满足 109<23010^9 < 2^{30}109<230 可知 L 的最大值是 30。
• 空间复杂度：O(m)O(m)O(m)，散列表总共需要记录 m 个查询的映射关系。

题解三（滑动窗口 + 预处理字符串）

这道题的思路也是通过预处理过滤相同长度的滑动窗口，区别在于预处理的是输入字符串，我们直接计算字符串 s 中所有可能出现的数字以及对应的 [left,right] 下标，再利用这份数据给予 queries 数组进行 O(1)O(1)O(1) 打表查询。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

kotlin复制代码class Solution {
    fun substringXorQueries(s: String, queries: Array<IntArray>): Array<IntArray> {
        val n = s.length
        // 预处理
        val valueMap = HashMap<Int, IntArray>()
        for (len in 1..Math.min(n,31)) {
            for (left in 0..n - len) {
                val right = left + len - 1
                val num = s.substring(left, right + 1).toInt(2)
                if (!valueMap.containsKey(num)) {
                    valueMap[num] = intArrayOf(left, right)
                }
            }
        }
        val result = Array(queries.size) { intArrayOf(-1, -1) }
        for ((index, query) in queries.withIndex()) {
            val target = query[0] xor query[1]
            if (valueMap.containsKey(target)) {
                result[index] = valueMap[target]!!
            }
        }
        return result
    }
}

复杂度分析：

• 时间复杂度：O(Ln+m)O(Ln + m)O(Ln+m)，其中 n 是字符串的长度， m 是 queries 数组的长度，L 是不同长度的窗口个数。O(Ln)O(Ln)O(Ln) 是预处理的时间，根据题目输入满足 109<23010^9 < 2^{30}109<230 可知 L 的最大值是 30。
• 空间复杂度：O(nL)O(nL)O(nL)，散列表总共需要记录 nL 个数的映射关系。

2565. 最少得分子序列（Hard）

题目地址

leetcode.cn/problems/su…

题目描述

给你两个字符串 s 和 t 。

你可以从字符串 t 中删除任意数目的字符。

如果没有从字符串 t 中删除字符，那么得分为 0 ，否则：

• 令 left 为删除字符中的最小下标。
• 令 right 为删除字符中的最大下标。

字符串的得分为 right - left + 1 。

请你返回使 t 成为 s 子序列的最小得分。

一个字符串的 子序列 是从原字符串中删除一些字符后（也可以一个也不删除），剩余字符不改变顺序得到的字符串。（比方说 "ace" 是 "acde" 的子序列，但是 "aec" 不是）。

题解（前后缀分解）

这道题第一感觉是 LCS 最长公共子序列的衍生问题，我们可以使用朴素 LCS 模板求解字符串 s 和字符串 t 的最长公共子序列 ，再使用 t 字符串的长度减去公共部分长度得到需要删除的字符个数。

然而，这道题目的输出得分取决于最左边被删除的字符下标 indexleftindex_{left}indexleft 和最右边被删除字符的下标 indexrightindex_{right}indexright，常规套路显得无从下手。所以，我们尝试对原问题进行转换：

• 思考 1： 假设删除 left 和 right 两个字符后能够满足条件，那么删除 [left,right] 中间所有字符也同样能满足条件（贪心思路：删除更多字符后成为子序列的可能性更大）；
• 思考 1 结论： 原问题等价于求删除字符串 t 中的最短字符串 [i,j]，使得剩余部分 [0, i - 1] 和 [j + 1, end] 合并后成为字符串 s 的一个子序列。
• 思考 2： 如果字符串 t 删除 [i, j] 区间的字符后能够满足条件，那么一定存在剩余部分 [0, i - 1] 与字符串 s 的前缀匹配，而 [j + 1, end] 与字符串 s 的后缀匹配，而且这两段匹配的区域一定 “不存在” 交集。
• 思考 2 结论： 我们可以枚举字符串 s 中的所有分割点，分别位于分割点的 s 前缀匹配 t 的前缀，用 s 的后缀匹配 t 的后缀，计算匹配后需要减去的子串长度，将所有枚举方案的解取最小值就是原题目的解。

思路参考视频讲解：www.bilibili.com/video/BV1GY… —— 灵茶山艾府 著

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

kotlin复制代码class Solution {
    fun minimumScore(s: String, t: String): Int {
        // 前后缀分解
        val n = s.length
        val m = t.length
        // s 的后缀和 t 的后缀匹配的最长子串的起始下标
        val sub = IntArray(n + 1).apply {
            var right = m - 1
            for (index in n - 1 downTo 0) {
                if (right >= 0 && s[index] == t[right]) right--
                this[index] = right + 1
            }
            this[n] = m
        }
        // s 的前缀和 t 的前缀匹配的最长子串的终止下标
        val pre = IntArray(n).apply {
            var left = 0
            for (index in 0..n - 1) {
                if (left < m && s[index] == t[left]) left++
                this[index] = left - 1
            }
        }
        // 枚举分割点
        var result = sub[0]
        if (0 == result) return 0 // 整个 t 是 s 的子序列
        for (index in 0 until n) {
            result = Math.min(result, m - (m - sub[index + 1]) - (pre[index] + 1))
        }
        return result
    }
}

复杂度分析：

• 时间复杂度：O(n)O(n)O(n)，其中 n 是字符串 s 的长度，预处理和枚举的时间复杂度都是 O(n)O(n)O(n)。
• 空间复杂度：O(n)O(n)O(n)，前后缀数组的空间。

我们下周见，有用请点赞关注！

推荐阅读

LeetCode 上分之旅系列往期回顾：

• LeetCode 单周赛第 343 场 · 结合「下一个排列」的贪心构造问题
• LeetCode 单周赛第 342 场 · 把问题学复杂，再学简单
• LeetCode 双周赛第 102 场· 这次又是最短路。
• LeetCode 双周赛第 101 场 · 是时候做出改变了！

⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

代码 demo

[scuzoutao/

AndroidCrashProtect

](github.com/scuzoutao/A…)

App Crash对于用户来讲是一种最糟糕的体验，它会导致流程中断、app口碑变差、app卸载、用户流失、订单流失等。相关数据显示，当Android App的崩溃率超过0.4%的时候，活跃用户有明显下降态势。

目前受益于我司采取的一系列的治理、监控、防劣化体系，java crash率降低到了一个十万分级别的数字**，**今天分享的就是稳定性治理过程中的一个重要工具，下面开整。

1. 为什么抛出异常时app会退出

不细致分析了，网上随便找一下就是一堆博客，简单来说就是没有被catch的崩溃抛出时，会调用 Thread#dispatchUncaughtException(throwable) 来进行处理，而在进程初始化时，RuntimeInit#commonInit 里会注入默认杀进程的 KillApplicationHandler，如果我们没有实现自定义的 UncaughtExceptionHandler 时，dispatchUncaughtException 被调用就会走到 KillApplicationHandler 里，把当前的进程杀掉，即产生了一次用户感知的崩溃行为。

2. 有没有办法打造一个永不崩溃的app

这个问题问出来的前提是指发生的崩溃是来自于 java 层面的未捕获的异常，c 层就是另一回事了。我们来尝试回答一下这个问题：

答：可以，至少可以做到把所有的异常都吃掉。

问：那么怎么做呢？

答：当某个线程发生异常时，只要不让 KillApplicationHandler 处理这个异常就行了，即只要覆盖掉默认的 UncaughtExceptionHandler 就行了噢。

问：那当这样做的时候，比如主线程抛出一个异常被吃掉了，app还能正常运行吗？

答：不能了，因为不做任何处理的话，当前线程的 Looper.loop()就被终止了。如果是主线程的话，此时你将会获得一个 anr。

问：怎么才能在吃掉异常的同时，让主线程继续运行呢？

答：当由于异常抛出，导致线程的 Looper.loop() 终止之后，接管 Looper.loop()。代码大概长下面这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

less复制代码public class AppCrashHandler implements UncaughtExceptionHandler {
    @Override
    public void uncaughtException(@NonNull Thread thread, @NonNull Throwable ex) {
        while (true) {
            try {
                if (Looper.myLooper() == null) {
                    Looper.prepare();
                }
                Looper.loop();
            } catch (Exception e) {
            }
        }
    }
}

上面这段代码，就是我标题中被描述为 Looper 兜底框架的实现机制。但是对于一个正常的app，线上是不可能这样无脑的catch，然后 Looper.loop的，这是因为：

1. 不是所有的异常都需要被catch住，如：OOM、launcher Activity onCreate之类的。
2. 稳定性不是靠屏蔽问题，而是靠解决问题，当异常无法解决或者解决成本太高，且异常被屏蔽对用户、业务来说并没有啥实质性的影响时，可以被屏蔽，当异常抛出时已经对业务产生了破坏，但是通过保护住然后重试可以让业务恢复运作时，也可以被屏蔽，只是多了个环节，即修复异常。

问：异常被吃掉之后会有什么影响？

抛异常的那句代码之后的代码将不会被调用，即当前的调用栈将会中断。假如代码像下面这样，通过Looper兜底的方式去让app不崩溃，会导致 throw 异常之后的代码无法被执行到。可以简单的理解为，是对整个调用栈加了 try-catch，不过这个try-catch 是加在了 Looper.loop()上

1
2
3
4
5
6
7
8

csharp复制代码    private void testCrash() {
        int x = 0;
        if(x == 0){
            throw new IllegalArgumentException("xx");
        }
        int y = 1;
        Log.e("TEST", "y is : " + y);
    }

问：到底什么异常需要被吃掉呢？

上一个回答中我们大致将需要被吃掉的异常分了两类

1. 异常我们无法解决或者解决成本太高

举个例子，假如公司有使用 react native 之类的三方大框架，当业务抛出来一个如下的异常时，我们就可以认为这无法解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

php复制代码com.facebook.react.bridge.JSApplicationIllegalArgumentException: connectAnimatedNodes: Animated node with tag (child) [30843] does not exist
    at com.facebook.react.animated.NativeAnimatedNodesManager.connectAnimatedNodes(NativeAnimatedNodesManager.java:7)
    at com.facebook.react.animated.NativeAnimatedModule$16.execute
    at com.facebook.react.animated.NativeAnimatedModule$ConcurrentOperationQueue.executeBatch(NativeAnimatedModule.java:7)
    at com.facebook.react.animated.NativeAnimatedModule$3.execute
    at com.facebook.react.uimanager.UIViewOperationQueue$UIBlockOperation.execute
    at com.facebook.react.uimanager.UIViewOperationQueue$1.run(UIViewOperationQueue.java:19)
    at com.facebook.react.uimanager.UIViewOperationQueue.flushPendingBatches(UIViewOperationQueue.java:10)
    at com.facebook.react.uimanager.UIViewOperationQueue.access$2600
    at com.facebook.react.uimanager.UIViewOperationQueue$DispatchUIFrameCallback.doFrameGuarded(UIViewOperationQueue.java:6)
    at com.facebook.react.uimanager.GuardedFrameCallback.doFrame(GuardedFrameCallback.java:1)
    at com.facebook.react.modules.core.ReactChoreographer$ReactChoreographerDispatcher.doFrame(ReactChoreographer.java:7)
    at com.facebook.react.modules.core.ChoreographerCompat$FrameCallback$1.doFrame
    at android.view.Choreographer$CallbackRecord.run(Choreographer.java:1118)
    at android.view.Choreographer.doCallbacks(Choreographer.java:926)
    at android.view.Choreographer.doFrame(Choreographer.java:854)
    at android.view.Choreographer$FrameDisplayEventReceiver.run(Choreographer.java:1105)
    at android.os.Handler.handleCallback(Handler.java:938)
    at android.os.Handler.dispatchMessage(Handler.java:99)
    at android.os.Looper.loopOnce(Looper.java:238)
    at android.os.Looper.loop(Looper.java:379)
    at android.app.ActivityThread.main(ActivityThread.java:9271)
    at java.lang.reflect.Method.invoke(Method.java)
    at com.android.internal.os.RuntimeInit$MethodAndArgsCaller.run(RuntimeInit.java:567)
    at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:1018)

2. 异常被屏蔽对用户、业务来说并没有实质性影响

• 比如老生常谈的 Android 7.x toast的 BadTokenException 之类的系统崩溃，一呢发生概率非常低，二呢在Android 8上的修复方式也只是 try-catch 住。

• 一些不影响业务、用户使用的三方库崩溃，比如瞎说一个，当使用 OkHttp 在请求接口时，内部切了个线程执行了个更新缓存的任务，结果里面抛出了一个 NPE 。外面没法 try-catch ，而且这个异常抛出时，顶多下次请求不走缓存，实际上没啥太大影响。

3. 异常很严重，但是吃掉之后通过修复运行环境能够让用户所使用的业务恢复正常运行

比如我们想要保存一张图片到磁盘上，但是磁盘满了， 抛出了一个no space left，这时候我们就可以将异常吃掉，同时清空app的磁盘缓存，并且告知用户重试，就可以成功的让用户保存图片成功

3. Looper兜底框架辅助稳定性治理

上面我们说到，我们可以通过Looper兜底的机制能够做到吃掉所有的java异常，那我们自然也能想到对于一个app来说，通过Looper兜底机制来辅助稳定性的治理。我们可以先明确一下什么崩溃需要通过这种手段来治理、兜底：

1. 系统崩溃，如老生常谈的 Android 7.x toast的 BadTokenException
2. 三方库的无痛崩溃，比如公司有使用 react native 之类的三方大框架，没有能力改或者不想改一些相关的 ui 引起的 崩溃，比如做动画时莫名其妙的抛出异常
3. 一些特殊崩溃，如磁盘空间不足引发的 no space left，可以尝试通过抓住崩溃同时清理一波app的磁盘缓存，再尝试继续运行。
4. 其他…

那么，我们就可以将代码写成如下这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

typescript复制代码public class MyApplication extends Application{
    @override
    public void onCreate(){
        super.onCreate();
        CrashProtectUtil.init();
    }
}



public class CrashProtectUtil{
    public void init() {
        mOldHandler = Thread.getDefaultUncaughtExceptionHandler();
        if (mOldHandler != this) {
            Thread.setDefaultUncaughtExceptionHandler(this);
        }
    }

    @Override
    public void uncaughtException(@NonNull Thread thread, @NonNull Throwable ex) {
        //判断异常是否需要兜底
        if (needBandage(ex)) {
            bandage();
            return;
        }

        //崩吧
        if (mOldHandler != null) {
            mOldHandler.uncaughtException(thread, ex);
        }
    }

    private boolean needBandage(Throwable ex) {
        //如果是没磁盘空间了，尝试清理一波缓存
        if (isNoSpaceException(ex)) {
            CacheCleaner.cleanAppCache(mContext, true);
            return true;
        }

        //BadTokenException
        if (isBadTokenException(ex)) {
            return true;
        }

        return false;
    }

    private boolean isNoSpaceException(Throwable ex) {
        String message = ex.getMessage();
        return !TextUtils.isEmpty(message) && message.contains("No space left on device");
    }

    private boolean isBadTokenException(Throwable ex) {
        return ex instanceof WindowManager.BadTokenException;
    }

    /**
     * 让当前线程恢复运行
     */
    private void bandage() {
        try {
            //fix No Looper; Looper.prepare() wasn't called on this thread.
            if (Looper.myLooper() == null) {
                Looper.prepare();
            }
            Looper.loop();
        } catch (Exception e) {
            uncaughtException(Thread.currentThread(), e);
        }
    }
}

上面其实就是Looper兜底框架的大致代码实现了，在未捕获的异常抛出时，我们在代码中通过异常的类型来判断是否需要进行保护。

当然，如果代码真这么写，当我有新的异常要被保护时，不就得改代码，然后发版上线吗？周期太长了。于是乎，就顺理成章的可以把异常是否要保护的逻辑抽象成 需要保护的崩溃画像匹配。假如有一个配置列表，上面描述了所有的需要被保护的异常，当一个异常被抛出时，本地拿着配置的需要被保护的异常列表一个一个的去做比对，如果发现这个异常在我们的配置里，就对其进行保护，否则则让默认的handler去处理，也就是杀掉进程。

问：为什么我的标题中强调了可远程配置化呢？

答：因为可远程配置化能够为框架本身赋能更多。

问：比如？

答：可以提供一种简易的线上容灾机制，假如线上在某个页面发生了一个崩溃，这个崩溃突然发生而且崩溃发生的点本身对业务来说无关紧要（比如有个开发手贱，Integer.parse整了个汉字，抛异常了），通过热修复来修吧，流程复杂，要改代码、打补丁包、配补丁包。紧急发版吧，成本比热修高了不知多少倍，这时如果有一个可配置化的Looper兜底框架，我通过更新我的配置，保护住这个 Integer.parse 异常，就能很轻松的解决线上问题。

4. 可配置化配置的是什么东西

首先这是一个崩溃保护的框架，那么配置的肯定是能描述崩溃的内容，那么什么东西能描述一个崩溃呢？无非就是以下元素：

1. throwable class name
2. throwable message
3. throwable stacktrace
4. Android version
5. app version
6. model
7. brand
8. …

大致就是对崩溃做个标签匹配：这是个什么崩溃，发生在哪个Android版本，发生在哪个App版本，发生在哪个厂商哪个系统版本上。

5. 我们怎么做的

我们的画像标签大致长下面这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

css复制代码[  {    "class": "",    "message": "No space left on device",    "stack": [],
    "app_version": [],
    "clear_cache": 1,
    "finish_page": 0,
    "toast": "",
    "os_version": [],
    "model": []
  },
  {
    "class": "BadTokenException",
    "message": "",
    "stack": [],
    "app_version": [],
    "clear_cache": 0,
    "finish_page": 0,
    "toast": "",
    "os_version": [],
    "model": []
  }
]

配置里还加了一些额外的东西，比如：

1. 崩溃被保护住的时候，要不要清理下app的缓存
2. 崩溃被保护住的时候，要不要弹个 toast 告知用户
3. 崩溃被保护住的时候，要不要退出当前页面

就这样，我们的可配置化的Looper兜底框架的全貌就描述完了，最后再总结一下具体的工作流程吧。

Looper兜底流程：

我们会注入自己的 UncaughtExceptionHandler，当App产生了一个未捕获的异常时，我们通过对这个异常进行几个标签的匹配来判断当前的崩溃是否要进行保护，当需要保护时，接管Looper.loop，让线程继续运行。

配置更新、生效流程：

当App启动时，拉取远程的崩溃画像配置，当未捕获的异常发生时，读取本地最新的配置，进行标签匹配，如果标签匹配成功，进行Looper兜底。

你可能感兴趣

Android QUIC 实践 - 基于 OKHttp 扩展出 Cronet 拦截器 - 掘金 (juejin.cn)

Android启动优化实践 - 秒开率从17%提升至75% - 掘金 (juejin.cn)

如何科学的进行Android包体积优化 - 掘金 (juejin.cn)

Android稳定性：Looper兜底框架实现线上容灾（二） - 掘金 (juejin.cn)

基于 Booster ASM API的配置化 hook 方案封装 - 掘金 (juejin.cn)

记 AndroidStudio Tracer工具导致的编译失败 - 掘金 (juejin.cn)

Android 启动优化案例-WebView非预期初始化排查 - 掘金 (juejin.cn)

chromium-net - 跟随 Cronet 的脚步探索大致流程（1） - 掘金 (juejin.cn)

Android稳定性：可远程配置化的Looper兜底框架 - 掘金 (juejin.cn)

一类有趣的无限缓存OOM现象 - 掘金 (juejin.cn)

Android - 一种新奇的冷启动速度优化思路(Fragment极度懒加载 + Layout子线程预加载) - 掘金 (juejin.cn)

Android - 彻底消灭OOM的实战经验分享（千分之1.5 -> 万分之0.2） - 掘金 (juejin.cn)

作者：邹阿涛涛涛涛涛涛

链接：juejin.cn/post/730669…

来源：稀土掘金

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

Flutter Forward 作为一场 Flutter 的突破性发布会，事实上 Flutter 3.7 在大会前已经发布 ，所以本次大会更多是介绍未来的可能，核心集中于 come on soon 的支持，所以值得关注的内容很多，特别是一些 Feature 让人十分心动。

开始之前

按照惯例，在展望未来之前需要先总结过去，首先，到目前为止已经超过 700,000 个已发布应用使用了 Flutter，例如腾讯知名的 PUBG 再次登上了大会 PPT。

另外，如 Google Classroom 团队也分享了他们使用 Flutter 开发的经历和收获，包括了代码复用率和开发效率等。

“使用 Flutter，我们将相同功能的代码大小减少了 66%……这意味着每个平台的错误更少，未来的技术债务也更少。”（Kenechi Ufondu，Google 课堂软件工程师）

另外从 Flutter 目前的用户数据情况看，当前阶段 Flutter 还是很受欢迎的。

而关于 Flutter 3.7 部分这里就不再赘述，感兴趣可以看前面已经发布的 Flutter 3.7 的更新说明 。

本次 Flutter 还安利了两个低代码的友商平台：FlutterFlow 和 WidgetBook 。

不得不说它们的成熟度都挺高的，例如 FlutterFlow 的在线调试运行和翻译支持就相当惊艳。

另外 WidgetBook 作为开源项目，它支持 Flutter 开发者针对自己的控件进行分类归纳，同时可以在使用 Widgetbook Cloud 的情况下，将 Widget 与 Figma 同步并和团队共享，为设计和开发人员提供更灵活的协作工具。

FlutterFlow 并不是完全免费哦。

Dart 3 alpha

本次大会的另外一个重点就是 Dart 3 alpha ，其实在此之前官方就有提前预热过，在《Flutter 的下一步， Dart 3 重大变更即将在 2023 到来》 里我们就提前预览过对应更新，其中大家最关注的莫过于 Records 和 Patterns 。

Records 支持高效简洁地创建匿名复合值，不需要再声明一个类来保存，而在 Records 组合数据的地方，Patterns 可以将复合数据分解为其组成部分。

例如要将 geoLocation 上面的返回值（由一对整数组成的记录）解构为两个单独的 int 变量 lat和 long，就可以使用这样的 Patterns 声明。

Patterns 是完全类型安全的支持，并且会在开发过程中进行错误检查。

你还可以对值的类型进行 Patterns 匹配，通过 switch可以使用匹配类型的 Patterns ，以及每种类型的字段。

当然，Dart 3 还有一个重点就是 100% 空安全的要求，也就是不再支持非空安全的代码，这对于旧项目来说是很大的挑战，相信还是有相当一大部分人的 Flutter 项目一直维持在低版本。

Dart 3 还进行了很大程度的优化， 例如 Dart 3 进行了清理一些不必要的 API ，同时对编译做了很大的优化，例如下图是变异后的代码对比。

另外 Dart 3 将支持更多的平台架构，例如 RISC-V ，同时还在覆盖 Windows 上的 ARM64 支持，而 Web 上 Dart 3 也将可以脱离 Flutter 直接支持 WebAssembly (Wasm) 。

最后在新工具的支持下，Dart 可以根据 C/ObjC/Swift/Java/Kotlin 代码的头文件/接口文件，自动创建具有 Dart 接口的绑定，以及那些跨语言调用所需的自动绑定，也就是 FFIgen + JNIgen。

具体可见：github.com/flutter/sam…

Web

本次还有一个惊喜就是 add-to-web 要来了， 一个叫做 element embedding 的支持即将到来。

element embedding 允许将 Flutter 添加到任何 Web <div>中 ，当以这种方式嵌入时，Flutter 就变成了一个 Web 组件与 Web DOM 完全集成，甚至可以使用 CSS 来设置父 Flutter 对象的样式。

例如将 Flutter 嵌入到基于 HTML 的网页中，然后使用 CSS 旋转效果，并且在旋转时 Flutter 内容仍可以交互。

同时 Dart 3 还对 Pub 上的 js 包进行了一些重大更改，从而实现 JavaScript 和 Dart 之间可以直接调用，如里使用 @JSExport 属性注释 Dart 代码中的任何函数，然后从 JS 代码中调用它。

除此之外 Flutter Web 也有一系列的优化计划，其中针对体积大小的优化是最重要的指标之一。

从官方提供的数据下看，未来 Flutter Web 的加载速度将会不断提升。

最后，现在 Flutter 支持在 Web 上的使用 Pixel shaders ，从而实现各种炫酷的视觉效果。

Flutter 新闻工具包

本次还有一个有意思但是对国内比较鸡肋的介绍： Flutter News Toolkit，一个用来加速新闻应用开发的免费 Flutter 应用模板。

这是 Flutter 团队和 GNI 合作的项目，官方宣称与 iOS 和 Android 上的传统双端开发相比，在该领域使用 FNT 可以节省高达 80% 的时间。

使用 Wonderous 适应大屏幕

Wonderous 早在去年 9 月份官方就推荐过一次 ，这一次主要是介绍了 Wonderous 的下一个版本，增加了对可折叠设备、平板电脑和平板电脑横向的支持。

此次迭代同时测试了 Flutter 对不同设备格式的适配能力， 具体可见：github.com/gskinnerTea…

Impeller

随着 3.7 的发布，Impeller 现在已经可以在 iOS 上进行预览。

Impeller 针对 Flutter 进行了优化，提供了更大的灵活性和对图形管道的控制支持。

例如使用预编译着色器，减少运行时由着色器编译引起的丢帧，利用 Metal 和 Vulkan 中的原始支持等等。

除了让 UI 更流畅，Impeller 还可以在某些极端情况下显着提高性能，比如大会介绍的一个例子：

左边是默认渲染器，右边是 Impeller，可以看到滚动是左侧因为性能问题导致帧速率为 7-10 fps，而右侧 Impeller 可以稳定在 60 fps 。

3D

本次最后一个亮点就是 Flutter 未来将正式支持 3D 渲染，同时也代表着 Flutter 在游戏领域的更进一步。

其实从去年的 I/O 也好，还有本次 Flutter Forward 提前预热的相关内容，可以看到 Flutter 进军游戏领域一直没有停歇。

在本次演示中，除了支持 3D 渲染之外，还支持对 3D 文件资源进行 hotload 、添加动画支持。

可以看到，在演示中多个 3D 模型同时渲染动画的情况下，画面依然可以流畅运行，这绝对是本次 Flutter Forward 最让人期待的特性。

最后官方还演示了在低端 iPhone 上的 3d 游戏场景（有指纹解锁的老 iPhone ），可以看到画面还是相当流畅。

最后

看完之后你是不是蠢蠢欲动？但是这里面绝大多的都还只是开发中，可能会在未来可能还会有其他变动，而本次 Flutter Forward 展示它们的目的，相信也是官方想让大家更直观地了解 Flutter 未来的方向。

最后总结一下，本次 Flutter Forward 主要的核心内容有：

• Impeller
• 3D 支持
• add-to-web 支持
• Dart 3

让我们期待未来 Flutter 的更新能让这些 Feature 都能用上吧，在没有坑的情况下～

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

核心内容原文链接： medium.com/flutter/wha…

2023 年新春之际， Flutter 喜提了 3.7 的大版本更新，在 Flutter 3.7 中主要有改进框架的性能，增加一些很棒的新功能，例如：创建自定义菜单栏、级联菜单、更好地支持国际化的工具、新的调试工具等等。

另外 Flutter 3.7 还改进了 Global selection、使用 Impeller提升渲染能力、DevTools 等功能，以及一如既往的性能优化。

PS ：3.7 版本包含大量，大量，大量更新内容，感觉离 4.0 不远了。

提升 Material 3 支持

随着以下 Widget 的迁移，Material 3 支持在 3.7 中得到了极大提升：

• Badge
• BottomAppBar
• Filled 和 Filled Tonal 按键
• SegmentedButton
• Checkbox
• Divider
• Menus
• DropdownMenu
• Drawer和NavigationDrawer
• ProgressIndicator
• Radio 按键
• Slider
• SnackBar
• TabBar
• TextFields和InputDecorator
• Banner

要使用这些新功能只需打开 ThemeData 的 useMaterial3标志即可。

要充分利用 M3 的特性支持，还需要完整的 M3 配色方案，可以使用新的 theme builder 工具，或者使用构造函数的 colorSchemeSeed 参数生成一个ThemeData ：

1
2
3
4
5
6
7

dart复制代码MaterialApp ( 
  theme : ThemeData ( 
    useMaterial3 : true, 
    colorSchemeSeed : Colors.green, 
  ), 
  // …
 );

使用这些组件，可以查看展示所有新 M3 功能的 interactive demo

菜单栏和级联菜单

Flutter 现在可以创建菜单栏和级联 context 菜单。

对于 macOS 可以使用 PlatformMenuBar 创建一个菜单栏，它定义了由 macOS 而不是 Flutter 渲染的原生菜单栏支持。

而且，对于所有平台可以定义一个 Material Design menu ，它提供级联菜单栏 ( MenuBar) 或由用户界面触发的独立级联菜单( MenuAnchor) 。

这些菜单可完全自主定制，菜单项可以是自定义 Widget，或者是使用新的菜单项 Widget ( MenuItemButton, SubmenuButton)。

Impeller 预览

这里很高兴地宣布新的 Impeller 渲染引擎 已经可以在 Stable Channel 上的 iOS 进行预览。

Flutter 团队相信 Impeller 的性能将达到或超过大多数应用的 Skia 渲染器，并且在保真度方面，Impeller 实现几乎覆盖了少数极端下的使用场景。

未来在即将发布的稳定版本中可能会让 Impeller 成为 iOS 上的默认渲染器，如果有任何问题，欢迎在 GitHub 的 Impeller Feedback 上提交反馈。

虽然目前期待的结果是 iOS 上的 Impeller 可以满足几乎所有现有 Flutter 应用的渲染需求，但 API 覆盖率仍然存在一些差距：

在 Flutter wiki 上列出了少量剩余的未覆盖情况，用户可能还会注意到 Skia 和 Impeller 之间在渲染中的细微视觉上存在差异，而这些细微差别可能会导致错误，所以如果有任何问题，请不要犹豫，欢迎在 Github 提出问题。

社区的贡献大大加快了 Impeller 上的进展。特别是 GitHub 用户 ColdPaleLight、guoguo338、JsouLiang 和 magicianA 为该版本贡献了 291 个 Impeller 相关补丁中的 37 个（>12%）。

另外 Flutter 将继续在 Impeller 的 Vulkan 上继续推进支持（在旧设备上回退到 OpenGL），但 Android 上的 Impeller 目前还未准备好，Android 上的支持正在积极开发中，希望可以在未来的版本中分享更多关于它的信息——以及未来更多关于 desktop 和 web 上的支持

在 GitHub 上的 Impeller 项目板上 可以关注进展。

iOS 版本验证

当开发者发布 iOS 应用时， checklist of settings to update 可确保开发者的应用已准备好提交到 App Store。

flutter build ipa 命令现在会验证其中一些设置，并在发布前通知开发者是否需要对应用进行更改。

开发工具更新

在 3.7 版本中，有几个关于新的工具和功能方面的改进。

DevTools 内存调试工具新增了三个功能选项卡，Profile、**Trace **和 Diff，它们支持所有以前支持的内存调试功能，并添加了更多功能以方便调试。

新功能包括：

• 按 class 和 memory 类型分析应用的当前内存分配
• 调查哪些代码路径在运行时为一组 class 分配内存
• 差异内存快照以了解两个时间点之间的内存管理

所有这些新的内存功能都记录在 docs.flutter.dev 上

Performance 页面还有一些值得注意的新功能，性能页面顶部的Frame Analysis 提供了对所选 Flutter frame 的分析：

可能包括有关跟踪到的 frame 的 expensive 操作的建议，或有关在 Flutter 框架中检测到的 expensive 操作的警告。

这些只是 3.7 里 DevTools 的几个亮点， 3.7 版本还包含几个错误修复和更多功能改进，包括 Inspector、Network profiler 和 CPU profiler 的一些重要错误修复。

如需更深入的更新列表，请查看 Flutter 3.7 中 DevTools 更改的发行说明。

自定义 Context 菜单

3.7 开始可以在 Flutter 应用的任何位置创建自定义 Context 菜单，还可以使用它们来自定义内置的 Context 菜单。

例如，开发者可以将 “发送电子邮件” 按钮添加到默认文本选择工具栏，当用户选择电子邮件地址 (code) 时，该工具栏就会显示。

通过 contextMenuBuilder 参数，该参数已添加到默认情况下显示 Context 菜单的 Widget，例如 TextField。

现在开发者可以从 contextMenuBuilder 返回任何想要的 Widget，包括修改默认的平台自适应的 Context 菜单。

这个新功能也适用于文本选择之外，例如创建一个 Image，然后在右键单击或长按时显示 “Save” 按钮（code），通过 ContextMenuController 在应用的任何位置显示当前平台的默认 Context 菜单或自定义菜单。

更多可见 Flutter Demo context_menus中的全套示例。

CupertinoListSection 和 CupertinoListTile 小部件

Cupertino 新增了两个新的 Widget，CupertinoListSection 和CupertinoListTile，用于显示 iOS 风格的可滚动小部件列表。

它们是Material ListView 和 ListTile 的 Cupertino 版本。

滚动改进

3.7 版本带来了多项 滚动更新：

• 触控板交互改进
• 新的 Widget（如 Scrollbars 和DraggableScrollableSheet）
• 滚动 Context 文本选择的改进处理

值得注意的是， MacOS 应用现在将通过添加新的滚动 physics 来体验更高的保真度以匹配桌面平台。

另外还有新的 AnimatedGrid 和 SliverAnimatedGrid 动画。

最后，本次还修复了几个滚动 Widget 的构造函数中的问题，例如ListView ：

在 Flutter 框架的 NNBD 迁移过程中，原本 itemBuilder 允许用户按需提供 widgets 类型，但是在迁移到 IndexedWidgetBuilder 时不允许用户返回 null。

这意味着 itemBuilder 不能再返回 null，而本次跟新该设定已经通过 NullableIndexedWidgetBuilder 修复。

国际化工具和文档

国际化支持已经全面改进，3.7 版本通过完全重写了 gen-l10n 工具来实现支持：

• 描述性的语法错误
• 涉及嵌套/多个复数、选择和占位符的复杂消息

有关更多信息，可参阅更新的 国际化 Flutter 应用页面。

全局选择改进

SelectionArea 现在支持键盘选择，开发者可以使用键盘快捷键扩展现有选择，例如 shift+right。

后台 isolates

3.7 开始 Platform Channels 可以从任何 Isolate invoked ， 以前用户只能从 Flutter 提供的主 Isolate 调用平台通道，而现在 Plugins 或 Add-to-app 能更好地使用 Isolate 和主机平台代码进行交互。

有关更多信息，请查看在 flutter.dev 上的 platform-specific code 和 Introducing background isolate channels。

文本放大镜

3.7 开始在 Android 和 iOS 上选择文本时出现的放大镜。

对于所有带有文本选择的应用，这是开箱即用的能力，但如果你想禁用或自定义它，请参阅 magnifierConfiguration 属性。

插件的快速迁移

由于 Apple 现在专注于使用 Swift 作为他们的 APIs ，我们希望开发参考资料以帮助 Flutter 插件开发人员使用 Swift 迁移或创建新插件。

quick_actions 插件已从 Objective-C 迁移到 Swift，可用作最佳实践的演示。如果有兴趣成为帮助我们迁移插件的一员，请参阅wiki的 Swift 迁移部分。

适用于 iOS 开发人员的资源，我们为 iOS 开发者发布了一些新资源，包括：

• 面向 SwiftUI 开发者的 Flutter
• 面向 Swift 开发人员的 Dart
• Swift 开发者的 Flutter 并发
• 将 Flutter 添加到现有的 SwiftUI 应用
• 使用 Flutter 创建 flavors （适用于 Android 和 iOS）

Bitcode deprecation

从 Xcode 14 开始，watchOS 和 tvOS 应用不再需要 bitcode，App Store 也不再接受来自 Xcode 14 的 bitcode 提交。

因此，Flutter 已删除对 bitcode 的支持。

默认情况下，Flutter 应用不启用位码，我们预计这不会影响许多开发人员。

但是如果你在 Xcode 项目中手动启用了 bitcode，请在升级到 Xcode 14 后立即禁用它。

你可以通过打开 ios/Runner.xcworkspace 并将 Enable Bitcode 设置为 No 来实现，Add-to-app 的开发人员可以在宿主 Xcode 项目中禁用它。

iOS PlatformView BackdropFilter

我们添加了在有 blurred 效果的 Flutter Widget 下方呈现时使原生 iOS 视图模糊的功能，并且 UiKitView 现在可以包装在 BackdropFilter。

有关详细信息，请参考 iOS PlatformView BackdropFilter 设计文档。

内存管理

3.7 版本对内存管理进行了一些改进，具体有：

• 减少垃圾收集暂停导致的卡顿
• 由于分配速度和后台 GC 线程而降低 CPU 利用率
• 减少内存占用

作为一个例子，Flutter 扩展了现有的手动释放支持某些 dart:ui 对象。

以前，Native 资源由 Flutter 引擎持有，直到 Dart VM 垃圾回收 Dart 对象。

通过对用户应用的分析和我们自己的基准测试，我们确定该策略不足以避免不合时宜的 GC 和过度使用内存。

因此，在此版本中，Flutter 引擎添加了显式释放用于 Vertices 、Paragraph 和 ImageShader 对象持有的原生资源的 API 。

在迁移到的 Flutter 框架基准测试中，这些改进将 90% 的帧构建时间减少了 30% 以上，最终用户将体验到更流畅的动画和更少的卡顿。

此外，Flutter 引擎不再将 GPU 图像的大小注册到 Dart VM，这些图像在不再需要时会由框架手动释放。

沿着类似的思路，现在 Flutter 引擎的策略是仅向 Dart VM 报告支持 dart:ui 的 Dart 对象部分的 Native 的 shallow size 。

在基准测试中，本次更改消除了在 Widget 创建 GPU 驻留图像时构建帧的同步 GC 。

在此版本中，Flutter Engine 还更好地利用了有关 Flutter 应用状态的信息来动态更新 Dart VM。

Flutter 现在使用 Dart VM 的 RAIL Style API 在路由转换动画期间进入 低延迟模式。

在低延迟模式下，Dart VM 的内存分配器会倾向堆增长而不是垃圾收集，以避免因 GC 暂停而中断过渡动画。

虽然类似更改不会带来任何显着的性能改进，但 Flutter 团队计划在未来的版本中扩展此模型的使用，以进一步消除不合时宜的 GC 暂停。

此外，本次还 修复了 Flutter 引擎空闲时通知 Dart VM 的 逻辑错误，修复这些错误可以防止与 GC 相关的卡顿。

最后，对于 add-to-app 的 Flutter 应用，当 Flutter 视图不再显示时 Flutter 会通知 Dart VM 引擎，当没有 Flutter 视图可见时，Dart VM 为与视图关联的对象触发 GC ，此更改可以减少了 Flutter 的内存占用。

停用 macOS 10.11 到 10.13

Flutter 不再支持 macOS 10.11 和 10.12 版本，3.7 版本发布后，也取消对 10.13 的支持，这可以并将帮助团队大大简化代码库。

这也意味着在 3.7 版本及以后版本中针对稳定的 Flutter SDK 构建的应用将不再适用于这些版本，并且 Flutter 支持的最低 macOS 版本增加到 10.14 Mojave。

因此，由于 Flutter 支持的所有 iOS 和 macOS 版本都包含 Metal 支持，OpenGL 后端已从 iOS 和 macOS 嵌入器中删除，删除这些后，Flutter 引擎的压缩大小减少了大约 100KB。

toImageSync

3.7 版本在 dart:ui 里 添加了 Picture.toImageSync 和 Scene.toImageSync 方法。

类似于异步 Picture.toImage，从 Picture 转化为 Image 时会从 Scene.toImage.Picture.toImageSync 同步返回一个句柄，并在后台异步进行 Image 光栅化。

当 GPU 上下文可用时，图像将保持为 GPU 常驻状态，这意味着会比 toImage 具有更快的渲染速度（生成的图像也可以保留在 GPU 中，但这种优化尚未在该场景中实现。）

新的toImageSyncAPI 支持用例，例如：

• 快速实现光栅化成本高昂的图片，以便在多个帧中重复使用。
• 对图片应用多通道滤镜。
• 应用自定义着色器。

例如，Flutter 框架 现在使用该 API 来提高 Android 上页面转换的性能，这几乎将帧光栅化时间减半，减少卡顿，并允许动画在支持这些刷新率的设备上达到 90/120fps。

自定义 shader 改进

3.7 版本包含了对 Flutter 对自定义片段着色器支持的大量改进。

Flutter SDK 现在包含一个着色器编译器，可将 pubspec.yaml 文件中列出的 GLSL 着色器编译为目标平台的正确特定格式。

此外，自定义着色器现在可以热加载，iOS 上的 Skia 和 Impeller 后端现在也支持自定义着色器。

更多可见 docs.flutter.dev 上编写和使用自定义片段着色器文档，以及 pub.dev 上的 flutter_shaders 包。

字体热重载

以前向 pubspec.yaml 文件添加新字体需要重新运行应用才能看到它们，这个行为这与其他可以热加载的 asset 不同。

现在，对字体清单的更改（包括添加新字体）可以热加载到应用中。

减少 iOS 设备上的动画卡顿

感谢 luckysmg 的开源贡献改进减少了 iOS 上的动画卡顿，特别是手势期间在主线程上添加虚拟 CADisplayLink 对象，现在会强制以最大刷新率进行刷新。

此外，键盘动画现在将刷新率设置为 CADisplayLink ，与 Flutter 引擎动画使用的刷新率相同。

由于这些变化，用户应该注意到 120Hz iOS 设备上的动画更加一致流畅。

最后个人感想

以上就是来自 Flutter 团队关于 Flutter 3.7 的主要更新内容，可以看到本次更新内容相当丰富：

• 最显眼的莫过于 Impeller 在 iOS 可以预览，性能提升未来可期
• 关于菜单相关的更新，也极大丰富了 Flutter 在编辑和本次选择中的疲弱态势
• 全局选择的改进和文本放大镜也进一步完善了 Flutter 文本操作的生态
• 性能、内存优化老生常谈，特别是 iOS 上的优化
• 开发工具进一步提升

当然本次大版本更新设计的内容范围很广，可以预见会有各式各样的坑在等大家，特别本次更新很多涉及底层 Framework 部分，所以按照惯例，等三个小版本会更稳。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

起因与问题

上周科研时，需要计算一个CNN参数的Hessian矩阵，即二阶导数。计算Hessian矩阵的实现思路想起来很简单：

1. 对于模型参数，求两次导。第一次求导时使用loss对于参数求导
2. 使用计算出来的梯度对于参数再次求导，就可以求出Hessian矩阵/二阶导数。

也就是只需要调用两次autogard.gard()就能够完成计算。此外，pytorch也提供了直接可以用于计算Hessian矩阵的api：autograd.functional.hessian()。但在调pytorch的api去实现的时候，却发现了如下问题：

pytorch的autogard.gard只能求标量对于向量的导数

假设我们的模型参数有N维，则loss函数对于参数的一阶导数为：

∂loss⁡∂w=[∂loss⁡∂w1∂loss⁡∂w2…∂loss⁡∂wn]\frac{\partial \operatorname{loss}}{\partial w} = [\frac{\partial \operatorname{loss}}{\partial w_1}\quad \frac{\partial \operatorname{loss}}{\partial w_2} \ldots \frac{\partial \operatorname{loss}}{\partial w_n}]∂w∂loss=[∂w1∂loss∂w2∂loss…∂wn∂loss]
而二阶导数为：

H=[∂2loss∂w12∂2 loss ∂w1∂w2…∂2 loss ∂w1∂wn∂2loss∂w2∂w1∂2loss∂w22…∂2 loss ∂w2∂wn⋮⋮⋮⋮∂2loss∂wn∂w1∂2loss⁡∂wn∂w2…∂2loss⁡∂wn2]H=\left[\begin{array}{cccc}
\frac{\partial^2 l o s s}{\partial w_1^2} & \frac{\partial^2 \text { loss }}{\partial w_1 \partial w_2} & \ldots & \frac{\partial^2 \text { loss }}{\partial w_1 \partial w_n} \
\frac{\partial^2 l o s s}{\partial w_2 \partial w_1} & \frac{\partial^2 l o s s}{\partial w_2^2} & \ldots & \frac{\partial^2 \text { loss }}{\partial w_2 \partial w_n} \
\vdots & \vdots & \vdots & \vdots \
\frac{\partial^2 l o s s}{\partial w_n \partial w_1} & \frac{\partial^2 \operatorname{loss}}{\partial w_n \partial w_2} & \ldots & \frac{\partial^2 \operatorname{loss}}{\partial w_n^2}
\end{array}\right]H=⎣⎡∂w12∂2loss∂w2∂w1∂2loss⋮∂wn∂w1∂2loss∂w1∂w2∂2 loss ∂w22∂2loss⋮∂wn∂w2∂2loss……⋮…∂w1∂wn∂2 loss ∂w2∂wn∂2 loss ⋮∂wn2∂2loss⎦⎤
通过autogard.gard()可以求出loss的一阶导数，但是二阶导数的计算需要对于一阶导数求导，autogard.gard()无法直接对于向量求导。更确切的说，torch.autograd.grad()函数常用的输入参数有以下三个：

• outputs (Tensor) – 一个可微函数的输出
• inputs (Tensor) – 需要被求导的参数
• grad_outputs (Tensor) – 通常是size与outputs相同的tensor

当output为一个长度大于一的向量时，就需要输入一个grad_outputs向量，其size与outputs相同。该参数相当于和向量做一个点乘，换句话说其将outputs向量转变为一个加权和的形式，从而将向量转化为标量，再进行求导。

因此，如果调用这个函数对梯度进行求导，最终得到一个长度为N的向量，而不会得到NxN大小的矩阵，该向量中每一个元素代表Hessian矩阵的某一行的和。即如下所示：

torch.autograd.functional.hessian无法自动求参数的Hession矩阵

pytorch中提供了一个专门用于计算Hessian矩阵的API：torch.autograd.functional.hessian()，但是在我尝试使用这个API去计算参数的Hession矩阵时却发现了一个问题：这个API无法自动对于参数进行求导。

torch.autograd.functional.hessian的主要参数如下所示：

• func (function) – 一个可微函数，其输入一个tensor，输出一个标量
• inputs (tuple of Tensors or Tensor) – 一个tensor或者tensor的tuple，其作为func的输入.

这里可以与gard()的参数进行比较，gard函数输入的是一个标量和一个tensor，其会基于标量的计算过程构建出计算图，计算出与输入的tensor相关的导数，也就是说，这个api是基于计算结果计算某一个参数的导数。但是torch.autograd.functional.hessian其输入的是一个函数和一个函数的输入。而后他会计算出这个函数关于这个输入的Hession矩阵。假设我们的func代表某一个模型，那么Hessian函数计算的则是这个模型输入针对于输入数据的Hession矩阵，而不是关于模型参数的Hessian矩阵。

现有的几种计算Hessian矩阵的实现方法

使用autogard.gard对于一阶梯度循环计算

以下方代码为例：

1
2
3
4
5
6
7
8
9
10
11
12
13

js复制代码#定义函数  
x = torch.tensor([0., 0, 0], requires_grad=True)
b = torch.tensor([1., 3, 5])
A = torch.tensor([[-5, -3, -0.5], [-3, -2, 0], [-0.5, 0, -0.5]])
y = b@x + 0.5*x@A@x
 
#计算一阶导数,因为我们需要继续计算二阶导数,所以创建并保留计算图  
grad = torch.autograd.grad(y, x, retain_graph=True, create_graph=True)
#定义Print数组,为输出和进一步利用Hessian矩阵作准备  
Print = torch.tensor([])
for anygrad in grad[0]:  #torch.autograd.grad返回的是元组
    Print = torch.cat((Print, torch.autograd.grad(anygrad, x, retain_graph=True)[0]))
print(Print.view(x.size()[0], -1))

实验方案非常简单，如上所示，假设要对于一个线性模型的参数求二阶导数，首先调用gard求出y对于x的一阶导数，得到一个tensor，而后遍历tensor中的每一个元素，计算该标量对于参数x的导数，并存储结果。就可以得到一个NxN的矩阵，该矩阵即为Hessian矩阵。

调用hessian函数并对model进行封装

如下代码所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

js复制代码import torch
import numpy as np
from torch.nn import Module
import torch.nn.functional as F

class Net(Module):
    def __init__(self, h, w):
        super(Net, self).__init__()
        self.c1 = torch.nn.Conv2d(1, 32, 3, 1, 1)
        self.f2 = torch.nn.Linear(32 * h * w, 5)

    def forward(self, x):
        x = self.c1(x)
        x = x.view(x.size(0), -1)
        x = self.f2(x)
        return x

def forward_loss(a, b, c, d):
    p = [a.view(32, 1, 3, 3), b, c.view(5, 32 * 12 * 12), d]
    x = torch.randn(size=[8, 1, 12, 12], dtype=torch.float32)
    y = torch.randint(0, 5, [8])
    x = F.conv2d(x, p[0], p[1], 1, 1)
    x = x.view(x.size(0), -1)
    x = F.linear(x, p[2], p[3])
    loss = F.cross_entropy(x, y)
    return loss

if __name__ == '__main__':
    net = Net(12, 12)
    h = torch.autograd.functional.hessian(forward_loss, tuple([_.view(-1) for _ in net.parameters()]))

与调用gard函数时不同，由于hessian函数的输入必须是一个可调用函数，并且函数的输入与被求导的量一致。由于我们计算的通常是loss对于参数的导数∂loss⁡∂w\frac{\partial \operatorname{loss}}{\partial w}∂w∂loss，而不是输出值对参数的导数∂y⁡∂w\frac{\partial \operatorname{y}}{\partial w}∂w∂y因此，在使用此函数计算Hessian矩阵的时候，必须要写好一个前向传播计算loss的函数，并且该函数的输入为模型的参数。

此外，loss计算函数在调用时，其输入的参数需要reshape成一维向量并包装成tuple，而后在函数内部再reshape为数组。

参考文献

1. www.cnblogs.com/chester-cs/…
2. stackoverflow.com/questions/6…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

导语

本文介绍了Text-to-Code领域最近的一篇数据集文章，这是由Huggingface发布的一个拥有30种编程语言的3.1TB数据规模的代码预训练语料。

• 会议：Arxiv 2022
• 链接：arxiv.org/abs/2211.15…

1 简介

最近，研究者们开始探索大型语言模型（Large Language Models (LLMs)）在代码方面的应用，Code LLMs接受大量源代码集合的训练，并能够从自然语言描述和其他代码片段中合成程序。

研究Code LLM面临的挑战之一是这些系统的开发缺乏开放性和透明度。虽然已经发表了一些论文，但它们并不总是对开发过程有全面的描述。一些研究小组通过付费API服务或商业产品提供了他们的Code LLM（如CodeX）。其他小组公布了模型权重（如InCoder），但没有公布训练数据。因此，研究人员很难完全重现这些模型。LLMs的一个重要预处理步骤是训练数据的重复数据删除，因为据报道它可以提高模型性能。然而，模型的性能通常对这种预处理方法的超参数非常敏感，作者认为，与其让研究人员独立迭代预处理细节，不如从一开始就更广泛地共享由数据卡支持的高质量数据集，社区的进展会更快。

作者认为，预训练数据的开放性也很重要。一些人认为，在版权许可的代码库(例如GPL)上训练的模型是对原始程序的修改，因此得到的模型应该在版权左许可下可用。其他人认为，Code LLM开发人员可能受益于版权法的例外情况，例如根据美国版权法，可以使用代码存储库用于模型训练。在LLM输出大量(或相关)第三方受版权保护代码的逐字副本的推理场景中，也应适当考虑。但是，即使目前的法规允许使用公共源代码来训练ML模型，也值得讨论这些实践是否符合社会和更广泛的研究界的道德价值观。例如，有人可能会说，代码创建者应该有权有意地控制他们的数据是否包含在训练集中。对于在训练数据中包含个人身份信息(PII)和恶意代码，人们也可能会有道德上的担忧，因为Code LLM可能会在部署过程中输出此类敏感数据或不安全的程序。目前，如何在LLM数据集的规模上实现数据治理的过程是一个悬而未决的问题。

本文发布The Stack(一个许可源代码的大型数据集)，向对Code LLM进行开放和负责任的研究迈出了一步。本文描述了如何从GitHub收集和处理代码存储库，并展示了小规模Code LLM的有前景的结果。具体而言，本文作出以下贡献:

• 提出The Stack数据集，这是一个具有3.1TB的合法开源代码语料，拥有30种编程语言（注：最新版The Stack v1.1已经拓展到了308种语言，6TB数据）；
• 训练了一个350M参数的Decoder-only的模型，并展示了只通过这些合法数据就可以取得与CodeX、CodeGen类似的性能表现；
• 提供了一个从数据集中删除自己Repo的接口在www.bigcode-project.org/docs/about/….

2 相关工作

Code LLMs

越来越多的研究机构在源代码上训练大型Transformer模型。几个小组已经探索了具有因果语言建模目标的纯解码器模型（如CodeX、PolyCoder、InCoder、CodeGen），并且通常发现更大的模型越来越有能力从自然语言描述中合成程序。一些研究通过因果掩码（causal masking）机制使用这种仅解码器模型来完成代码填充任务。研究人员还研究了编码器掩码语言模型（如CodeBERT）和具有各种训练目标的编码器-解码器架构(如CodeT5)。

Code LLM的预训练数据集

Github一直是最常用的数据集来源。Google BigQuery提供了GitHub上许可存储库的快照，可以通过SQL查询进行过滤。AlphaCode，BLOOM，InCoder、CodeGen）都在他们的预训练数据集中包括了这部分数据。这些GitHub数据的快照也在HuggingFace hub上作为CodeParrot项目下的GitHub-Code数据集公开提供。PolyCoder通过抓取GitHub存储库收集了一个代码数据集，并发布了他们下载的存储库和文件的目录。本文将我们的工作与表1中的这些代码数据集进行比较，并在第3.2节中详细说明这些差异。

另一个常用的资源是CodeSearchNet语料库。这个语料库首先从GitHub收集了大量的公共和允许的存储库，然后用Treesitter进一步处理这些存储库，以提取函数(方法)和文档字符串对。该数据集包含了六种编程语言的配对:Go、Java、JavaScript、Python、PHP和Ruby。CodeBERT和CodeT5使用该数据集进行预训练。

一些研究报告了在非公共数据集上训练的结果。CodeX从54M个GitHub公共库中收集了179 GB的python文件，但没有发布数据，也没有披露有关许可的信息。CodeGen收集了一个私人的GitHub数据集，包含217.3GB的许可python文件。他们在Pile和BigQuery上的GitHub快照上进行预训练后，对该数据集上的模型进行了微调。虽然CodeGen开源了模型权重，但他们没有发布私有的Python数据集。

去重

最近的研究表明，训练集中的重复数据删除可以显著提高LLM的性能。Lee等人表明，语言模型的训练语料库包含许多接近重复的词，当去掉长重复的子字符串时，LLM性能会提高。Hernandez等人还发现，即使重复一小部分训练数据也会严重损害模型性能，这可能是由于数据记忆消耗了部分容量。数据复制在代码数据集中更为常见，因为重用和克隆其他代码存储库是常见的做法。事实上，Lopes等人观察到，GitHub数据中有很大一部分由克隆组成，导致精确和接近重复的比例很高。Allamanis研究了代码复制对机器学习模型的影响，并表明它会导致高度膨胀的性能指标。然而，许多现有的代码LLMs只应用精确的重复数据删除，这在训练数据中留下了大量接近重复的数据。

3 数据集

3.1 数据集创建

数据收集

本文首先从GHArchive收集了一组活跃的GitHub存储库名称，GHArchive是一个致力于归档和发布公共GitHub时间轴的开源项目。作者从2015年1月1日至2022年3月31日发布的事件档案中提取了唯一的存储库名称。这产生了一个包含22092万个唯一存储库名称的列表。接下来，运行了一个分布式计算集群花费几个月时间，克隆这个存储库列表。最终，成功下载了137.36万个存储库。所有存储库都在2021年11月至2022年6月期间下载。

许可检查

软件的开源协议有很多（可以参考www.runoob.com/w3cnote/ope… ），作者对这些Github项目的许可进行检查（如表2）。

许可允许的数据集

本文开发一个源代码数据集，只使用许可允许的数据，作者使用如下所示的许可预测列表，将单个存储库标记为许可的。最后，代码作者可以按照www.bigcodeproject.org/docs/about/… 上的说明从该数据集中删除自己的数据。

Near-deduplication

在精确重复数据删除的基础上，本文在预处理流程中实现了近乎重复的数据删除。我们首先根据非字母数字字符将文件拆分为单词/标记，并删除标记少于10个的文件。接下来，我们用所有文档的256种排列计算MinHash ，并使用局部敏感哈希（LSH）来找到重复的集群。通过确保原始集群中的每个文件与减少的集群中的至少一个文件相似，我们进一步减少了这些集群。当两个文件的Jaccard相似度超过0.85时，我们认为它们相似。我们发现，在许可数据集中，38.6%的文件只是其他文件的近似副本并被删除，它们也代表了数据集体积的53.7%。每种编程语言的细目见表3。

3.2 数据集分析

为了更深入地了解收集的数据集，我们首先分析每种编程语言的数据量，然后与其他代码数据集进行比较，最后对python子集进行更广泛的分析。

每种编程语言的数据

表3中列出了30种编程语言的可用数据量。可以看到全许可证数据集包含超过29 TB的数据。仅选择许可文件将数据集减少到3.1 TB，即仅保留大约10%的数据集。对于某些编程语言(例如SQL, Batchfile, TypeScript)，我们发现只有不到4%的数据具有许可许可。我们可以通过向许可许可列表中添加更多的许可来增加这一百分比(请参阅附录a)。如果进一步对许可许可数据集应用近似重复数据删除，最终将得到1.4 TB，减少了50%以上。例如，当不擅长这些数据时，只保留了37%的HTML。从图1中可以看出，少数几种编程语言构成了数据集的大部分。对于许可数据集，四种最大的语言——html (746 GB)、Javascript (486 GB)、Java (271 GB)和C (222 GB)——占用了数据集大小的55%以上。

与其他数据集的比较

表1展示了The Stack和CodeParrot、AlphaCode、CodeGen、PolyCoder进行比较。注意，AlphaCode和CodeGen没有公布他们的数据，但提供了每种编程语言的数据量的统计数据。值得一提的是，CodeParrot包含具有copyleft许可证(例如GPL)的文件，而我们的许可许可证数据集则没有。PolyCoder不过滤许可信息，也可能包含copyleft许可的文件。Stack和CodeParrot提供了30种编程语言的源代码，而AlphaCode、PolyCoder和CodeGen分别只提供其中12种、12种和6种语言的数据。此外，我们观察到我们的数据集是CodeParrot(第二大公开可用的代码数据集)的3倍多。我们还看到，对于每种编程语言，我们的数据集比CodeParrot更大。

Python子集分析

首先，作者研究许可数据集的Python子集中有多少配置文件和测试文件。这些配置文件在GitHub存储库中非常丰富，但没有捕获源代码的复杂功能。

接下来，对数据集中的10,000个样本使用py_compile模块来估计有效Python文件的数量。我们发现只有0.7%的文件由于语法错误而无法编译。具体来说，作者发现大约0.1%的Python文件存在标记化错误(例如，由于制表符和空格的不一致使用)。

最后，分析文件中的文档字符串和注释。这些数据对于文档生成和自然语言代码翻译等应用程序至关重要。我们分析10,000个文件中的一个子集。首先使用ast和tokenize模块来提取文档字符串和注释，作者发现它们占子集容量的18%，20%的文件只有很少(少于20个字符)或没有自然文本。

为了识别提取的文档字符串和注释的语言，作者使用fasttext库中的模型。作者发现94%的文件是英文的。在其他语言中，汉语和法语最受欢迎，有100多个样本。图2中展示了自然语言的完整分布。需要注意的是，这种语言检测并不完美，因为文档字符串通常包含带有英文关键字的代码示例。

4 实验

为了更好地理解收集的数据集的质量，本文研究了在几个版本的python子集上从头训练的transformer模型的性能。作者评估了HumanEval和MBPP上的模型，并与类似规模的CodeGen、InCoder和Codex模型进行了比较。作者在研究过程的后期发现，一些预训练集受到了来自评估基准的示例的污染。由于运行实验成本高且耗时长，本文只重新运行几个实验来调查数据污染的影响。

4.1 实验设置

数据集

作者实验了自己的python数据集的4个版本，以及CodeParrot的Python子集。对于自己的数据集，我们要么使用来自所有存储库(all-license)的python文件，要么使用来自具有许可许可(permissive-license)的存储库的python文件。对于这些数据，要么应用近重复数据删除(near-dedup)，要么不进行进一步过滤(none)。值得强调的是，接近重复数据删除的过程是在我们在数据集收集期间应用的重复数据删除之上的。对于CodeParrot，我们只试验了接近重复数据删除的版本12。

对于所有数据集，遵循Codex的过滤方法，并使用以下方法删除文件:

• 平均行长大于100个字符；
• 最大行长度超过1000个字符；
• 少于25%的字符是字母数字字符；
• 文件前几行中的关键字表明该文件可能是自动生成的。

数据包含

在训练模型之后，作者发现一些训练集包含了来自评估基准的示例。本文通过搜索HumanEval和MBPP的自然语言提示符的精确字符串匹配来检测这种污染问题。表4显示了每个子集中发现的受污染文件的数量。所有子集都包含HumanEval示例，但只有python-all-license子集包含MBPP示例。为了调查数据污染的影响，我们在几乎重复数据删除的python-all-license和python-permission-license数据集上重新运行实验。为此，我们从这些数据集中删除了受污染的文件。请注意，我们只删除了提示符的精确副本，因此不检测转述。

评估

本文在HumanEval和MBBP 基准上评估模型。HumanEval是一个包含164个编程问题的text2python基准测试。每个问题都由函数签名、文档字符串、主体和一些测试用例组成，这些测试用例允许验证生成程序的正确性。使用pass@k度量对模型进行评估:为每个问题生成k个样本，如果至少有一个样本通过测试用例，则解决了一个问题，并且测量了解决问题的总比例。在实践中，我们对每个问题取样200个程序，并按照Chen等人提出的估计pass@k。我们使用top-p = 0.95，温度T∈{0.2,0.8}T∈{0.2,0.8}T∈{0.2,0.8}的核采样，并报告pass@k为最佳温度。

作者还对MBPP进行了评估，这是一个由众包编程问题组成的text2python基准测试。每个问题由一个简短的自然语言描述和3个单元测试组成。我们在500个样本的测试集上进行评估。Austin等人在提示符中包含了所有三个单元测试，Fried等人只包含了一个单元测试，因为他们观察到较小的语言模型(即具有数十亿个参数)没有从更多的单元测试中受益。我们遵循Fried等人的做法，只将第一个单元测试添加到自然语言提示符中。除了pass@1，我们还对pass@10和pass@100进行了评估，每个问题抽样200个程序。与HumanEval类似，我们使用top-p = 0.95，温度T∈{0.2,0.8}T∈{0.2,0.8}T∈{0.2,0.8}的核采样，并报告最佳温度的分数。

训练细节

我们对通过因果语言建模目标训练的Decoder-only模型进行了实验。作者选择350M参数模型，24层，隐藏维1024,16个注意头，序列长度2048。使用Adam训练模型进行300K次迭代，Batch大小为384，β1=0.9，β2=0.95，ϵ=10−8β_1 = 0.9， β_2 = 0.95，\epsilon = 10−8β1=0.9，β2=0.95，ϵ=10−8，权值衰减为0.1。学习率设置为3×10−43 × 10^{−4}3×10−4并进行175个step的warmup，然后遵循余弦衰减。模型在训练过程中处理235.9B个token。字节对编码标记器是在The Pile和The Stack中的Python文件的50-50混合数据上训练的。我们fork了Megatron-LM的分支进行训练。

实验结果的讨论

表5和表6中报告HumanEval和MBPP结果。之后，作者给出了几点讨论。

删除近似重复的数据对性能有提升

对训练数据应用近似重复数据删除会在全许可证和许可许可证数据集上产生显著改善。在permission-license数据集上，近似重复数据删除将HumanEval性能从27.21%提高到37.00% pass@100，将MBPP性能从44.99%提高到54.69% pass@100。我们看到全许可证数据集的结果也有类似的提升，其中HumanEval性能从36.67%提高到44.00% pass@100, MBPP性能从53.59%提高到61.00% pass@100。

使用许可数据就可以复现（CodeX等）性能

我们能够复现text2python的结果，以前的工作只允许许可的源代码。在HumanEval上，我们观察到，在没有几乎重复数据删除的情况下，许可许可数据集(27.21% pass@100)的性能明显低于Codex (36.27% pass@100)和CodeGen(35.19% pass@100)。但是，在应用近似重复数据删除后，Codex和CodeGen的性能达到了一致(37.00% pass@100)。在MBPP上，我们观察到类似的结果。如果没有近似重复数据删除，python允许数据集(44.99% pass@100)的性能明显低于CodeGen (51.80% pass@100)。但是，近似重复数据删除的版本(54.69% pass@100)超过了CodeGen的结果。

与CodeParrot的比较

在Codeparrot(另一个发布的代码数据集)上的训练在HumanEval上达到30.37% pass@100，这明显低于我们发布的数据集的性能(37.00% pass@100)。在MBPP上，CodeParrot的表现也低于我们发布的数据集(45.44% vs 54.69% pass@100)。CodeParrot由从BigQuery中提取的数据组成，不足以获得HumanEval和MBPP上的竞争模型。

数据污染的影响

令人惊讶的是，我们发现删除受污染的文件对text2python结果的影响很小。在HumanEval上，许可-许可证数据集有很小的下降(37.00% vs 36.01% pass@100)，而全许可证数据集有很小的增长(44.00% vs 45.52% pass@100)。我们还看到MBPP上的全许可证数据集受到了较小的影响(61.00% vs 58.28% pass@100)。我们推测数据污染的影响是最小的，因为(1)小模型不太可能记住训练数据，(2)污染文件很少。

5 总结和未来工作

本文介绍了The Stack，这是一个拥有超过3Tb许可源代码的大型数据集。本文描述了数据集收集的细节，给出了一个简单的数据集分析，并在HumanEval基准测试上展示了有希望的结果。实验结果表明，近似重复数据删除是在text2code基准测试中获得有竞争力结果的重要预处理步骤。本文发布了30种常见编程语言的所有许可文件，以及一个近乎重复数据删除的版本。在未来的工作中，我们希望进一步改进已发布的数据集。我们对发布其他编程语言的数据持开放态度，计划研究删除PII和恶意代码的方法，并开始尝试让开发人员有可能从数据集中删除他们的数据。我们希望Stack将成为开放和负责任的Code LLM研究的有用资源。

6 局限性

数据集带来的社会影响

The Stack是BigCode项目的一个输出。BigCode的目标是在设计和默认情况下负责任。该项目是在开放科学的精神下进行的，专注于负责任的Code LLM开发。

随着The Stack的发布，我们的目标是在研究社区中增加Code LLM的可访问性、可重复性和透明度。在各个BigCode工作组中开展了降低风险和改进Code LLM道德最佳实践的工作。法律、道德和治理工作组探讨了诸如许可(包括copyleft和许可代码的预期使用)、生成的代码归属于原始代码、限制处理的权利、个人身份信息(PII)的包含以及恶意代码的风险等主题。这项工作正在进行中。

我们希望Code LLM能够让来自不同背景的人编写更高质量的代码并开发低代码应用程序。当代码生成系统指导专业开发人员如何编写更健壮和有效的代码时，关键任务软件将变得更容易维护。虽然社会影响是积极的，但代码llm的可访问性的增加也带来了一定的风险，例如过度依赖生成的代码以及对软件开发就业市场的长期影响。

我们建议读者参考Chen等人（即CodeX）的第7节，以获得对Code LLMs更广泛的影响分析，以及Khlaaf等人对这种新兴技术进行深入的风险评估和危害分析。

数据集中的偏见

从GitHub收集的代码不包含人口统计信息或关于人口统计的代理信息。然而，这并不是没有风险，因为代码中的注释可能包含有害或冒犯性的语言，这可以从模型中学习到。

与Julia和Scala等小众编程语言相比，C和Javascript等被广泛采用的编程语言过多。我们发现一些编程语言，如SQL, Batchfile, TypeScript不太可能被许可(4% vs平均10%)。这可能导致对这些语言的描述有偏见。许可文件也往往较长。

我们还发现，英语语言在文档字符串和注释中被过度表示，因为它占Python文件数据的96%。

HTML not WCAG-compliant

The Stack目前的一个限制是为网站抓取HTML可能不符合Web内容可访问性指南(WCAG)。这可能会对html生成的代码产生影响，可能会引入web可访问性问题。

个人身份信息

我们注意到数据中包含姓名和电子邮件地址等个人身份信息(Personally Identifiable Information，PII)。这个PII已经在GitHub上向公众公开，但是，我们计划在未来的工作中删除PII。

恶意代码

少数存储库被删除了，因为它们在下载阶段触发了内部安全工具。但是，我们没有完全扫描数据集的恶意软件，因此，可能仍然存在着恶意代码。

数据许可

虽然我们尽力筛选许可源代码，但是许可检测器可能错误地对许多存储库进行了分类。如果您遇到没有许可许可证的文件，请联系contact@bigcode-project.org。我们还强调，The Stack是以数据集的形式编译源文件(包括属性和许可通知)。堆栈中的每个源文件都带有自己的许可许可，数据集的用户应该尊重这些许可许可。

模型局限

我们在python数据集上展示了较小模型的text2code结果。有必要进行更多的研究，以确定是否可以为更大的模型和其他编程语言(而不是Python)获得强有力的结果。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有