由 tauri 单例模式 bug “意外修复” 发现的 dangling

TL;DR

tauri 单例插件用于区分单例实例的 productName的过长会导致单例功能失效，博主最初确信 encode_wide 实现有问题，并提交了修复。然而在和社区深入研究问题原因后，发现根本原因是使用 encode_wide 转码传参时造成了 dangling 。

PS: 为方便读者理解，博主花费一天时间重新梳理分析步骤，按照演绎法展示定位 bug 地过程，实现发生的分析过程要比博文的过程更加曲折，对分析理解问题无意义因此略过。

所以这个 bug 的现象是怎么样的？

正如博主所说，在有问题版本的插件代码中，博主最初发现，tauri.conf.json 中的 package.productName 在分别使用五个汉字与六个汉字时，单例模式功能表现出不一致的行为：五个汉字的 productName 单例功能运行正常，而六个汉字的 productName 单例功能失效，于是针对该问题初步进行了测试：

测试的 `productName`	单例插件功能是否生效
六个汉字试试	x
随便五个字	√
又来了六个字	x

因为这些汉字测试用例使用 UTF-8 编码，又因为是常用字，因此每个汉字对应 3 bytes，因此假设 productName 在超过 15 bytes、不超过 18 bytes 时会导致功能失效，进一步补充测试用例：

测试的 `productName`	单例插件功能是否生效
z12345678901234	√
z123456789012345	x

看来博主运气不错，刚好踩到了边界的测试用例。那么基本可以确定，productName 超过 15 bytes 就会导致单例功能失效。

PotatoTooLarge: 传递给 Win32 API 的字符串要用 C string 风格的 `\0` 结束

在最初的讨论过程中，因为我们没有仔细留意插件仓库使用的 encode_wide 是自行做过封装的，因此我们一开始根据以下代码进行分析：

pub fn init<R: Runtime>(f: Box<SingleInstanceCallback<R>>) -> TauriPlugin<R> {
    plugin::Builder::new("single-instance")
        .setup(|app| {
            let app_name = &app.package_info().name;
            let class_name = format!("{}-single-instance-class", app_name);
            let window_name = format!("{}-single-instance-window", app_name);

            let hmutex = unsafe {
                CreateMutexW(
                    std::ptr::null(),
                    true.into(),
                    encode_wide("tauri-plugin-single-instance-mutex").as_ptr(),
                )
            };

            if unsafe { GetLastError() } == ERROR_ALREADY_EXISTS {
                unsafe {
                    let hwnd = FindWindowW(
                        encode_wide(&class_name).as_ptr(),
                        encode_wide(&window_name).as_ptr(),
                    );

                    // omitted
                }

                // omitted
            }

            // omitted
        })
        .on_event(|app, event| {
            // omitted
        })
        .build()
}

有 Windows 编程经验的 @PotatoTooLarge 指出，encode_wide（来自 std 的 Window扩展）并不会补充 \0 结束符：

Re-encodes an OsStr as a wide character sequence, i.e., potentially ill-formed UTF-16.

This is lossless: calling OsStringExt::from_wide and then encode_wide on the result will yield the original code units. Note that the encoding does not add a final null terminator.

于是博主听取建议，把所有会传递到 encode_wide 函数的字符串都添加了 \0，形成了一版修复:

pub fn init<R: Runtime>(f: Box<SingleInstanceCallback<R>>) -> TauriPlugin<R> {
    plugin::Builder::new("single-instance")
        .setup(|app| {
            let app_name = &app.package_info().name;
            // let class_name = format!("{}-single-instance-class", app_name);
            let class_name = format!("{}-single-instance-class\0", app_name);
            // let window_name = format!("{}-single-instance-window", app_name);
            let window_name = format!("{}-single-instance-window\0", app_name);

            let hmutex = unsafe {
                CreateMutexW(
                    std::ptr::null(),
                    true.into(),
                    // encode_wide("tauri-plugin-single-instance-mutex").as_ptr(),
                    encode_wide("tauri-plugin-single-instance-mutex\0").as_ptr(),
                )
            };

            if unsafe { GetLastError() } == ERROR_ALREADY_EXISTS {
                unsafe {
                    let hwnd = FindWindowW(
                        encode_wide(&class_name).as_ptr(),
                        encode_wide(&window_name).as_ptr(),
                    );

                    // omitted
                }

                // omitted
            }

            // omitted
        })
        .on_event(|app, event| {
            // omitted
        })
        .build()
}

然后使用修复前会引起单例功能失效的 z123456789012345 作为测试用例，验证单例功能可用了，证明该修改可以修复单例功能失效的问题。

但它并不是真的修复

在博主提交了修复后，插件仓库作者提醒，前文所述的代码使用的 encode_wide 是封装拼接了 \0 后再传递参数的:

pub fn encode_wide(string: impl AsRef<std::ffi::OsStr>) -> Vec<u16> {
    std::os::windows::prelude::OsStrExt::encode_wide(string.as_ref())
        .chain(std::iter::once(0))
        .collect()
}

这意味着，并不是 \0 导致问题的失效，因为该函数在 windows 环境下执行是能够补足 \0 的：

fn encode_wide(string: impl AsRef<std::ffi::OsStr>) -> Vec<u16> {
    std::os::windows::prelude::OsStrExt::encode_wide(string.as_ref())
        .chain(std::iter::once(0))
        .collect()
}

fn main() {
    let product_name = "z123456789012345";

    // output: [122, 49, 50, 51, 52, 53, 54, 55, 56, 57, 48, 49, 50, 51, 52, 53, 0]
    //                                                                           ^
    //                              null concated here so it's null-terminated --|
    println!("{:?}", encode_wide(product_name));
}

那么失效的过程发生了什么？

为了分析问题详细过程，我将插件仓库代码切换到了问题代码版本：

git checkout 16e5e9eb59da9ceca3dcf09c81120b37fe108a03

然后添加了一些 dbg 宏：

pub fn init<R: Runtime>(f: Box<SingleInstanceCallback<R>>) -> TauriPlugin<R> {
    plugin::Builder::new("single-instance")
        .setup(|app| {
            let app_name = &app.package_info().name;
            let class_name = format!("{}-single-instance-class", app_name);
            let window_name = format!("{}-single-instance-window", app_name);

            let hmutex = unsafe {
                CreateMutexW(
                    std::ptr::null(),
                    true.into(),
                    encode_wide("tauri-plugin-single-instance-mutex").as_ptr(),
                )
            };
            dbg!(hmutex);  // windows.rs:43 debug here!

            if unsafe { GetLastError() } == ERROR_ALREADY_EXISTS {
                unsafe {
                    let hwnd = FindWindowW(
                        encode_wide(&class_name).as_ptr(),
                        encode_wide(&window_name).as_ptr(),
                    );
                    dbg!(hwnd);  // windows.rs:51 debug here!

                    // omitted
                }
            } else {
                app.manage(MutexHandle(hmutex));

                let hwnd = create_event_target_window::<R>(&class_name, &window_name);
                dbg!(hwnd);  // windows.rs:76 debug here!

                // omitted
            }

            Ok(())
        })
        .on_event(|app, event| {
            // omitted
        })
        .build()
}

然后，将代码仓库 examples\emit-event\src-tauri\tauri.conf.json 分别改成 z12345678901234 与 z123456789012345，然后执行：

# process1
> cd examples\emit-event
examples\emit-event> cargo tauri build --debug
examples\emit-event> src-tauri\target\debug\z12345678901234.exe
[tauri-plugin-single-instance\src\platform_impl\windows.rs:43] hmutex = 548
[tauri-plugin-single-instance\src\platform_impl\windows.rs:76] hwnd = 40113446

# process2
> examples\emit-event\src-tauri\target\debug\z12345678901234.exe
[tauri-plugin-single-instance\src\platform_impl\windows.rs:43] hmutex = 548
[tauri-plugin-single-instance\src\platform_impl\windows.rs:51] hwnd = 40113446

# process1
> cd examples\emit-event
examples\emit-event> cargo tauri build --debug
examples\emit-event> src-tauri\target\debug\z123456789012345.exe
[tauri-plugin-single-instance\src\platform_impl\windows.rs:43] hmutex = 552
[tauri-plugin-single-instance\src\platform_impl\windows.rs:76] hwnd = 0

# process2
> examples\emit-event\src-tauri\target\debug\z123456789012345.exe
[tauri-plugin-single-instance\src\platform_impl\windows.rs:43] hmutex = 548
[tauri-plugin-single-instance\src\platform_impl\windows.rs:51] hwnd = 0

# process3
> examples\emit-event\src-tauri\target\debug\z123456789012345.exe
[tauri-plugin-single-instance\src\platform_impl\windows.rs:43] hmutex = 548
[tauri-plugin-single-instance\src\platform_impl\windows.rs:51] hwnd = 0

由上面的结果我们可以知道：在用例 z12345678901234，我们在创建实实例时返回了有效的 hwnd 值，并且在检查 hwnd 时确认已经创建窗口；而在用例 z123456789012345，我们创建窗口的函数 create_event_target_window 返回的 hwnd 是无效的！所以导致问题的代码，应该在 create_event_target_window 的逻辑中！再次添加 dbg ，重新编译后继续 debug：

fn create_event_target_window<R: Runtime>(class_name: &str, window_name: &str) -> HWND {
    unsafe {
        let class = WNDCLASSEXW {
            cbSize: std::mem::size_of::<WNDCLASSEXW>() as u32,
            style: 0,
            lpfnWndProc: Some(single_instance_window_proc::<R>),
            cbClsExtra: 0,
            cbWndExtra: 0,
            hInstance: GetModuleHandleW(std::ptr::null()),
            hIcon: 0,
            hCursor: 0,
            hbrBackground: 0,
            lpszMenuName: std::ptr::null(),
            lpszClassName: encode_wide(&class_name).as_ptr(),
            hIconSm: 0,
        };
        dbg!(class.lpszClassName);  // windows.rs:153 debug here
        dbg!(*class.lpszClassName);  // windows.rs:154 debug here

        RegisterClassExW(&class);

        let hwnd = CreateWindowExW(
            WS_EX_NOACTIVATE
            | WS_EX_TRANSPARENT
            | WS_EX_LAYERED
            // WS_EX_TOOLWINDOW prevents this window from ever showing up in the taskbar, which
            // we want to avoid. If you remove this style, this window won't show up in the
            // taskbar *initially*, but it can show up at some later point. This can sometimes
            // happen on its own after several hours have passed, although this has proven
            // difficult to reproduce. Alternatively, it can be manually triggered by killing
            // `explorer.exe` and then starting the process back up.
            // It is unclear why the bug is triggered by waiting for several hours.
            | WS_EX_TOOLWINDOW,
            dbg!(encode_wide(&class_name).as_ptr()),  // windows.rs:170 debug here
            dbg!(encode_wide(&window_name).as_ptr()),  // windows.rs:171 debug here
            WS_OVERLAPPED,
            0,
            0,
            0,
            0,
            0,
            0,
            GetModuleHandleW(std::ptr::null()),
            std::ptr::null(),
        );
        SetWindowLongPtrW(
            hwnd,
            GWL_STYLE,
            // The window technically has to be visible to receive WM_PAINT messages (which are used
            // for delivering events during resizes), but it isn't displayed to the user because of
            // the LAYERED style.
            (WS_VISIBLE | WS_POPUP) as isize,
        );
        hwnd
    }
}

z12345678901234:

examples\emit-event> src-tauri\target\debug\z12345678901234.exe
[tauri-plugin-single-instance\src\platform_impl\windows.rs:43] hmutex = 556
[tauri-plugin-single-instance\src\platform_impl\windows.rs:153] class.lpszClassName = 0x0000021d099eddc0
[tauri-plugin-single-instance\src\platform_impl\windows.rs:154] *class.lpszClassName = 122
[tauri-plugin-single-instance\src\platform_impl\windows.rs:170] encode_wide(&class_name).as_ptr() = 0x0000021d099ee180
[tauri-plugin-single-instance\src\platform_impl\windows.rs:171] encode_wide(&window_name).as_ptr() = 0x0000021d099dfe20
[tauri-plugin-single-instance\src\platform_impl\windows.rs:76] hwnd = 28841288

z123456789012345:

examples\emit-event> src-tauri\target\debug\z123456789012345.exe
[tauri-plugin-single-instance\src\platform_impl\windows.rs:43] hmutex = 548
[tauri-plugin-single-instance\src\platform_impl\windows.rs:153] class.lpszClassName = 0x0000017259ca6be0
[tauri-plugin-single-instance\src\platform_impl\windows.rs:154] *class.lpszClassName = 43920
[tauri-plugin-single-instance\src\platform_impl\windows.rs:170] encode_wide(&class_name).as_ptr() = 0x0000017259cc6b30
[tauri-plugin-single-instance\src\platform_impl\windows.rs:171] encode_wide(&window_name).as_ptr() = 0x0000017259cc6970
[tauri-plugin-single-instance\src\platform_impl\windows.rs:76] hwnd = 0

对比我们之前 encode_wide 函数返回的结果，class_name 开头的字符应该是 ASCII 字符 z（ASCII 码 122），因此通过 encode_wide(&class_name).as_ptr() 传参的 class.lpszClassName，应当指向值为 "z123456789012345-single-instance-class" 的字符串，这在用例 z12345678901234 中行为符合预期；但在 z123456789012345 的用例中，class.lpszClassName 指向的却发生了变化（*class.lpszClassName = 43920），反推可以得知， encode_wide(&class_name).as_ptr() 并没有成功地把指针传递给 class.lpszClassName。

一语惊醒梦中人：悬垂指针（dangling）！

@Berrysoft 指出， encode_wide(&class_name).as_ptr() 这种写法由于直接对临时变量直接取指针，而临时变量 encode_wide(&class_name) 会在执行完之后被马上释放结束生命周期，因此指向该临时变量的指针也会变成悬垂指针！临时变量的这一行为在 reference 中有说明：

When using a value expression in most place expression contexts, a temporary unnamed memory location is created and initialized to that value. The expression evaluates to that location instead, except if promoted to a static. The drop scope of the temporary is usually the end of the enclosing statement.

而解决该问题，只需要把提升变量的 lifetime，把要用到的变量提取出来，使其 lifetime 可以覆盖要用到的函数而不至于在语句执行完之后马上被回收。于是有了解决问题的 PR。

那为什么在 `format` 的时候手动添加 `\0` 后，问题“修复”了呢？

这个问题依然悬而未决。有 TG 群友提出，可能是由于堆栈被破坏 “碰巧” 又指向了正确的字符串位置，而 format 后的变量又是 'static 的，因此能达到“修复”的效果，然而这依然是基于 bug/undefined behavior 的修复方案，因此仍然不可靠。后续原因排查出来后会更新博客~

教训与经验

实际上的排查过程，是分析过一次 create_event_target_window 的，然而当时由于需求紧急而找到了临时绕开的实现方案（把 productName 砍短），因此搁置了，也没有留下相关的排查记录文档，以致于后续在需求变更而变得必须排查清楚该问题时，走向了排查 encode_wide 的错误方向，虽然有了“修复”方案，但该方案仍然不可靠，因此可以视作浪费了实践。 形成记录首先方便的是以后的自己。
凡是 unsafe 多查几遍。像本文涉及到的悬垂指针问题，在 safe rust 中因为 lifetime 不够长而会阻止编译，而 unsafe 块中使用裸指针是不会被编译器检查的，因此相关操作都要相当慎重。
多借助社区的力量。比起一个人钻牛角尖，多与社区讨论才容易跳出原本的死胡同，从而理解意识到原来思路的局限性。

尝试在单 HTML 文件中嵌入 WASM 模块的错误操作

TL;DR

当项目是需要 WASM 与 JavaScript 相互交互的时候，请尽可能在统一的 JavaScript 入口中定义所有的功能；
wasm-pack 生成的胶水 JavaScript 与 WASM 可以稍作修改即可嵌入到 HTML 文件中。

项目背景

当博主兴高采烈地使用 HTML 与 JavaScript 迅速开发好 UI 界面与交互功能的时候，发现核心的功能的 JavaScript 库只支持 npm 环境而无法应用到前述 UI 界面上，博主迫于无奈只能抓起以前做过的 Rust 版本库，尝试改造成 WASM 模块以复用界面代码。因为博主的这个项目是属于不对外开放的项目，因此本文中使用的项目是简化后的 demo，但不影响博主记录以及提醒上述遇到的两个问题（这两个坑每一个都坑掉了我几个小时，但愿会有读者看到我这篇文章抢救一下自己的时间）。

demo 项目架构

demo
  |-- Cargo.toml
  |-- src
        |-- lib.rs
  |-- assets
        |-- demo.html

# Cargo.toml
[package]
name = "demo"
authors = ["huangjj27 <huangjj.27@qq.com>"]
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[lib]
crate-type = ["cdylib", "rlib"]

[dependencies]
wasm-bindgen = "0.2.63"

// lib.rs
use wasm_bindgen::prelude::*;

#[wasm_bindgen]
pub fn add(a: i32, b: i32) -> i32 {
    a + b
}

<!-- demo.html -->
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>just a demo</title>
    <script id="indexscript" type="module">
        import init, { add } from "../pkg/demo.js";
        async function run() {
            await init();
        }

        run();
    </script>
    <script>
        function js_add() {
            let a = document.getElementById("a");
            let b = document.getElementById("b");
            let sum = document.getElementById("sum");
            sum.value = add(a.value, b.value);
        }
    </script>
</head>
<body>
    <textarea id="a" autofocus oninput="js_add()">40</textarea>
    <textarea id="b" oninput="js_add()">2</textarea>
    <textarea id="sum" readonly></textarea>
</body>
</html>

项目在编译的时候还需要 wasm-pack，用来生成胶水 JavaScript demo/pkg/demo.js 和 wasm 文件 demo/pkg/demo_bg.wasm：

wasm-pack build --target=web

薛定谔的 JavaScript 函数

当我们打开 demo.html 并且尝试修改 a 和 b 的值时，我们会从控制台遇到了如下报错：

13:33:19.672 Uncaught ReferenceError: add is not defined
    js_add file:///demo/assets/demo.html:23
    oninput file:///demo/assets/demo.html:1
2 demo.html:22:13

这里的 add 函数就是我们从 WASM 模块中加载的，来自 rust 实现的 add 函数。此时，如果我们在 run 下属下方，直接调用 add 则是可以执行成功的：

    <script id="indexscript" type="module">
        import init, { add } from "../pkg/demo.js";
        async function run() {
            await init();
            console.log(`add函数已加载，add(1, 2) = ${add(1, 2)}`);
        }

        run();
    </script>

执行结果:

14:02:58.360 add函数已加载，add(1, 2) = 3 demo.html:13:21
14:03:11.895 Uncaught ReferenceError: add is not defined
    js_add file:///demo/assets/demo.html:23
    oninput file:///demo/assets/demo.html:1
2 demo.html:23:13

出现以上现象的原因是，type="module" 限制了 indexscript 内部项目的作用域只能在该 <script> 代码块中有效。解决方法有两种：

将需要导出的给其他 <script> 块使用的功能，挂载在页面全局的 window 对象上，模拟 export 的效果，缺点是很可能无意中覆盖了挂载对象。
将所有js 功能都集中在 indexscript 代码块中，将所有的功能统一管理。此时，要注意将DOM 元素的事件通过监听事件的方式来管理：

<!-- demo.html -->
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>just a demo</title>
    <script id="indexscript" type="module">
        import init, { add } from "../pkg/demo.js";
        function js_add() {
            let a = document.getElementById("a");
            let b = document.getElementById("b");
            let sum = document.getElementById("sum");
            sum.value = add(a.value, b.value);
        }

        async function run() {
            await init();

            document.getElementById("a").addEventListener("input", js_add);
            document.getElementById("b").addEventListener("input", js_add);
        }

        run();
    </script>
</head>
<body>
    <textarea id="a" autofocus>40</textarea>
    <textarea id="b">2</textarea>
    <textarea id="sum" readonly></textarea>
</body>
</html>

然而我还是想包容你的，我的 WASM

我们来分析一下 wasm-pack 生成的 demo.js：

// demo.js

let wasm;

/**
* @param {number} a
* @param {number} b
* @returns {number}
*/
export function add(a, b) {
    const ret = wasm.add(a, b);
    return ret;
}

async function load(module, imports) {
    if (typeof Response === 'function' && module instanceof Response) {
        if (typeof WebAssembly.instantiateStreaming === 'function') {
            try {
                return await WebAssembly.instantiateStreaming(module, imports);

            } catch (e) {
                if (module.headers.get('Content-Type') != 'application/wasm') {
                    console.warn("`WebAssembly.instantiateStreaming` failed because your server does not serve wasm with `application/wasm` MIME type. Falling back to `WebAssembly.instantiate` which is slower. Original error:\n", e);

                } else {
                    throw e;
                }
            }
        }

        const bytes = await module.arrayBuffer();
        return await WebAssembly.instantiate(bytes, imports);

    } else {
        const instance = await WebAssembly.instantiate(module, imports);

        if (instance instanceof WebAssembly.Instance) {
            return { instance, module };

        } else {
            return instance;
        }
    }
}

async function init(input) {
    if (typeof input === 'undefined') {
        input = new URL('demo_bg.wasm', import.meta.url);
    }
    const imports = {};


    if (typeof input === 'string' || (typeof Request === 'function' && input instanceof Request) || (typeof URL === 'function' && input instanceof URL)) {
        input = fetch(input);
    }



    const { instance, module } = await load(await input, imports);

    wasm = instance.exports;
    init.__wbindgen_wasm_module = module;

    return wasm;
}

export default init;

我们看到，demo.js:175 对来待加载的 module 做了判断：如果不是从响应获取的数据，则直接视作 wasm bytes 来进行加载。于是我们可以对生成的 demo_bg.wasm 文件通过 base64 转码，嵌入到 HTML 文件中，然后转换成 Uint8Array 传递给 demo.js:init 函数进行加载:

    <script id="indexscript" type="module">
// demo.js 完全嵌入到 html 文件中，并且不需要 export 语句
let wasm;

/**
* @param {number} a
* @param {number} b
* @returns {number}
*/
function add(a, b) {
    const ret = wasm.add(a, b);
    return ret;
}

async function load(module, imports) {
    if (typeof Response === 'function' && module instanceof Response) {
        if (typeof WebAssembly.instantiateStreaming === 'function') {
            try {
                return await WebAssembly.instantiateStreaming(module, imports);

            } catch (e) {
                if (module.headers.get('Content-Type') != 'application/wasm') {
                    console.warn("`WebAssembly.instantiateStreaming` failed because your server does not serve wasm with `application/wasm` MIME type. Falling back to `WebAssembly.instantiate` which is slower. Original error:\n", e);

                } else {
                    throw e;
                }
            }
        }

        const bytes = await module.arrayBuffer();
        return await WebAssembly.instantiate(bytes, imports);

    } else {
        const instance = await WebAssembly.instantiate(module, imports);

        if (instance instanceof WebAssembly.Instance) {
            return { instance, module };

        } else {
            return instance;
        }
    }
}

async function init(input) {
    if (typeof input === 'undefined') {
        input = new URL('demo_bg.wasm', import.meta.url);
    }
    const imports = {};


    if (typeof input === 'string' || (typeof Request === 'function' && input instanceof Request) || (typeof URL === 'function' && input instanceof URL)) {
        input = fetch(input);
    }



    const { instance, module } = await load(await input, imports);

    wasm = instance.exports;
    init.__wbindgen_wasm_module = module;

    return wasm;
}

// demo.js 嵌入结束

        // wasm 二进制，base64编码：
        const WASM_B64 = "AGFzbQEAAAABBwFgAn9/AX8DAgEABQMBABEHEAIGbWVtb3J5AgADYWRkAAAKCQEHACAAIAFqCwB7CXByb2R1Y2VycwIIbGFuZ3VhZ2UBBFJ1c3QADHByb2Nlc3NlZC1ieQMFcnVzdGMdMS42MS4wIChmZTViMTNkNjggMjAyMi0wNS0xOCkGd2FscnVzBjAuMTkuMAx3YXNtLWJpbmRnZW4SMC4yLjgwICg0Y2FhOTgxNjUp";

        function b64toBytes(b64) {
            let binary = atob(b64);
            let bytes = new Uint8Array(binary.length);
            for (let i = 0; i < bytes.length; i++) {
                bytes[i] = binary.charCodeAt(i);
            }
            return bytes;
        }

        function js_add() {
            let a = document.getElementById("a");
            let b = document.getElementById("b");
            let sum = document.getElementById("sum");
            sum.value = add(a.value, b.value);
        }

        async function run() {
            await init(b64toBytes(WASM_B64));  // 直接通过页面加载编码

            document.getElementById("a").addEventListener("input", js_add);
            document.getElementById("b").addEventListener("input", js_add);
        }

        run();
    </script>

完成以上步骤，我们就得到了一个带有 WASM 功能的 standalone html 文件啦~。

蓄水池算法改进 - 面向抽奖场景保证等概率性

免责声明：禁止任何个人或团体使用本文研究成果用于实施任何违反中华人民共和国法律法规的活动如有违反，均与本文作者无关

在我们通常遇到的抽奖场景，于年会时将所有人的编号都放到箱子里面抽奖，然后每次抽出中奖者决定奖项。而在这过程中，因为先抽中者已经确定了奖项，然后不能够参与后续的奖项的抽奖；而后续参与抽奖的人员则其实会以越来越低的概率参与抽奖:

例：在上述场景中共有 $ n $ 人参与抽取 $ m ( \lt n) $ 个奖项，

抽取第一个奖项概率为： $ { m \over n } $

那么如果第一个奖项被抽走并 揭露了，剩下 $ n - 1 $ 人参与 $ m - 1 $ 个奖项，抽中的概率为 $ m - 1 \over n - 1 $。那么 $ m \lt n \Rightarrow -m \gt -n \Rightarrow mn - m \gt nm - n \Rightarrow m(n-1) \gt n(m - 1) \Rightarrow { m \over n } \gt { m - 1 \over n - 1 }$，即如果是后续参与抽奖 并且前面的奖项被拿走了，后面抽到奖项的概率会更低，同时也会失去参与部分奖项的机会。

因此，在人数 $ n $ 大于奖项数 $ m $ 的时候，我们通过以越来越低的概率干涉前面已经“取得”奖项的结果，来保证先参与抽奖的人中奖的概率随着人数的增多中奖的概率也变低，最后保证每个人中奖的概率为 $ m \over n $。但是在实际场景中，$ m $ 个奖项可能不仅相同（如划分了一二三等奖），因此对于蓄水池算法的改进提出了新的要求：

将所有的奖项视为各不相同的位置，不论人数多少（当还是要保证有人来参与抽奖 $ n \gt 1$ )所有人占有特定位置的概率相同
~~每当新来一人参与抽奖时，如果他没有中奖，可以即场告知未中~~¹

算法描述与等概率性证明

我们分两种情况讨论：

一种是当人数不足以覆盖所有的奖项的场景（ $n \lt m $ )，
另外一种是当抽奖人数远大于所有奖项加起来的数目。（ $ n \gt m $）。

然后我们再回来看看能不能找到一种很方便的方法桥接两种情况。

同时，我们假设 $ m $ 个奖项两两互不相同。

抽奖人数不足时（ $n \lt m $ )

因为当人数不足时，所有参与者都能抽奖，因此我们要保证每个人获得特定奖项的概率为 $ 1 \over m $。算法描述：

记 $ Choosen $ 为容量为 $ m $ 的数组， $ Choosen[k] (1 \le k \le m) $ 表示第 k 个奖项的当前占有情况，初始值为 $ None $,

$ Players $ 为参与参与抽奖的人的序列

令 $ i := 1 $，当 $ i \le n $ 时，做如下操作：

产生随机数 $ r_1 (1 \le r_1 \le i) $

如果 $ r_1 \lt i $，$ Choosen[i] := Choosen[r_1] $

$ Choosen[r_1] := Players[i] $

$ i := i + 1 $

当 $ i \le m $ 时，做如下操作：

产生随机数 $ r_2 (1 \le r_2 \le i) $

如果 $ r_2 \lt i $:

$ Choosen[i] := Choosen[r_2] $

$ Choosen[r_2] := None $

$ i := i + 1 $

等概率性证明

我们先证明，在填入中奖者的第 $ k (1 \le k \le m) $ 轮过程中，能够保证对于前 $ k $ 个奖项中的每一个奖项，每一位中奖者抽中其中第 $ i (1 \le i \le k) $ 个奖项的概率为 $1 \over k $，证明如下：

我们采用数学归纳法来证明：

奠基：当 $ k = 1 $ 时，易知该中奖者一定会抽中第一个奖项，前一个奖项中只有第一个选项，所以此时每一位中奖者抽中第 $ k = 1 $ 的概率为 $ 1 = { 1 \over 1 } = { 1 \over k } $;
归纳:
- 假设当 $k = j (1 \le j \lt m) $时，每一位抽奖者抽中第 $ i (1 \le i \le j) $的概率为 $ 1 \over j $
- 当 $ k = j + 1 $, 有：
  - 第 $ j + 1 $ 位抽奖着抽中任意第 $ i' (1 \le i' \le j + 1) $ 个奖项的概率为 $ 1 \over { j + 1 } $ （假设产生的随机数 $ r_1、r_2 $ 足够的均匀）;
  - 对于前 $ j $ 位抽奖者，每一位都有 $ 1 \over { j + 1 } $，的概率将自己的奖项更换位第 $ j + 1 $个奖项；
  - 对于前 $ j $ 位抽奖者，每一位依然占有原有第 $ i' $ 个奖项的概率为：

\[ \begin{equation} \begin{aligned} P\{前 j 位抽奖者 j + 1 轮中仍然持有 i' \} & = P\{前 j 位抽奖者j轮已经持有 i' \} \cdot P\{第 j + 1 位抽奖者没有抽中 i' \} \\ & = P\{前 j 位抽奖者j轮已经持有 i' \} \cdot (1 - P\{第 j + 1 位抽奖者抽中 i' \}) \\ & = \frac{1}{j} \cdot (1 - \frac{1}{j+1}) \\ & = \frac{1}{j} \cdot \frac{j}{j+1} \\ & = \frac{1}{j + 1} \\ & = \frac{1}{k} \\ \end{aligned} \label{1.1} \tag{1.1} \end{equation} \]

由上，可知每一轮迭代之后，前 $ k $ 个奖项对于已经参与的 $ k $中奖者来说抽中的概率均等，为 $ 1 \over k $，故到了第 $ n $ 轮操作后，我们可以通过不断填充 $ None $值来稀释概率，最后达到 $ 1 \over m $ 的等概率性。

特殊地，当 $ n == m $ 时，每个抽奖者抽到特定奖项的概率也为 $1 \over n $。

抽奖人数足够多时（ $n \gt m $ )

类似地，当 $n \gt m $时，对于每一个抽奖序号 $ k \gt m $ 的抽奖者，我们生成随机数 $ r_3(1 \le r_3 \le n) $，并且在 $ r_3 \le m $ 的时候，替换对应原本占有奖项的抽奖者；可以证明在这种情况下，能保证每个人抽到特定奖项的概率为 $1 \over n $²。

整合后的算法

记 $ Choosen $ 为容量为 $ m $ 的数组， $ Choosen[k] (1 \le k \le m) $ 表示第 $ k $ 个奖项的当前占有情况，初始值为 $ None $,

$ replaced $ 为原本已经中奖，但是被人替换的抽奖者

$ Players $ 为参与参与抽奖的人的序列，每次只能获取一个 $ player $

记 $ n := 0 $为当前参与抽奖的人数

在抽奖结束前，每次遇到一个新的 $ player $ 执行以下操作：

$ replaced := None $

$ n := n + 1 $

产生随机数 $ r (1 \le r \le n) $

如果 $ r \le m $：

$ replaced := Choosen[r] $

$ Choosen[r] := player $

如果 $ r \lt n $ 并且 $ n \le m $：

$ Choosen[n] := replaced $

在抽奖结束时，如果 $ n \lt m $, 执行以下操作：

$ i := n $

当 $ i \lt m $时，重复执行以下操作：

$ i := i + 1 $

产生随机数 $ r_2 (1 \le r_2 \le i) $

如果 $ r_2 \lt i $:

$ Choosen[i] := Choosen[r_2] $

$ Choosen[r_2] := None $

程序实现

Rust

作者偏好 Rust 编程语言，故使用 Rust 实现。

特质（trait）

Rust 中的特质（trait）是其用于复用行为抽象的特性，尽管比起 Java 或 C# 的接口（Interface）更加强大，但在此文中，熟悉 Java/C# 的读者把特质视作接口就可以了。

建模与实现

本文使用面向对象（Object-Oriented）编程范式³来进行抽象，如下所示：

use rand::random;

use std::fmt::Debug;

trait ReservoirSampler {
    // 每种抽样器只会在一种总体中抽样，而总体中所有个体都属于相同类型
    type Item;

    // 流式采样器无法知道总体数据有多少个样本，因此只逐个处理，并返回是否将样本纳入
    // 样本池的结果，以及可能被替换出来的样本
    fn sample(&mut self, it: Self::Item) -> (bool, Option<Self::Item>);

    // 任意时候应当知道当前蓄水池的状态
    fn samples(&self) -> &[Option<Self::Item>];
}

struct Lottery<P> {
    // 记录当前参与的总人数
    total: usize,

    // 奖品的名称与人数
    prices: Vec<Price>,

    // 当前的幸运儿
    lucky: Vec<Option<P>>,
}

#[derive(Clone, Debug)]
struct Price {
    name: String,
    cap: usize,
}

impl<P> ReservoirSampler for Lottery<P> {
    type Item = P;

    fn sample(&mut self, it: Self::Item) -> (bool, Option<Self::Item>) {
        let lucky_cap = self.lucky.capacity();

        self.total += 1;

        // 概率渐小的随机替换
        let r = random::<usize>() % self.total + 1;
        let mut replaced = None;
        if r <= lucky_cap {
            replaced = self.lucky[r - 1].take();
            self.lucky[r - 1] = Some(it);
        }

        if self.total <= lucky_cap && r < self.total {
            self.lucky[self.total - 1] = replaced.take();
        }

        (r <= lucky_cap, replaced)
    }

    fn samples(&self) -> &[Option<Self::Item>] {
        &self.lucky[..]
    }
}

impl<P: Debug> Lottery<P> {
    fn release(self) -> Result<Vec<(String, Vec<P>)>, &'static str> {
        let lucky_cap = self.lucky.capacity();

        if self.lucky.len() == 0 {
            return Err("No one attended to the lottery!");
        }

        let mut final_lucky = self.lucky.into_iter().collect::<Vec<Option<P>>>();
        let mut i = self.total;
        while i < lucky_cap {
            i += 1;

            // 概率渐小的随机替换
            let r = random::<usize>() % i + 1;
            if r <= lucky_cap {
                final_lucky[i - 1] = final_lucky[r - 1].take();
            }
        }
        println!("{:?}", final_lucky);

        let mut result = Vec::with_capacity(self.prices.len());
        let mut counted = 0;
        for p in self.prices {
            let mut luck = Vec::with_capacity(p.cap);

            for i in 0 .. p.cap {
                if let Some(it) = final_lucky[counted + i].take() {
                    luck.push(it);
                }
            }

            result.push((p.name, luck));
            counted += p.cap;
        }

        Ok(result)
    }
}

// 构建者模式（Builder Pattern），将所有可能的初始化行为提取到单独的构建者结构中，以保证初始化
// 后的对象(Target)的数据可靠性。此处用以保证所有奖品都确定后才能开始抽奖
struct LotteryBuilder {
    prices: Vec<Price>,
}

impl LotteryBuilder {
    fn new() -> Self {
        LotteryBuilder {
            prices: Vec::new(),
        }
    }

    fn add_price(&mut self, name: &str, cap: usize) -> &mut Self {
        self.prices.push(Price { name: name.into(), cap });
        self
    }

    fn build<P: Clone>(&self) -> Lottery<P> {
        let lucky_cap = self.prices.iter()
            .map(|p| p.cap)
            .sum::<usize>();

        Lottery {
            total: 0,
            prices: self.prices.clone(),
            lucky: std::vec::from_elem(Option::<P>::None, lucky_cap),
        }
    }
}

fn main() {
    let v = vec![8, 1, 1, 9, 2];
    let mut lottery = LotteryBuilder::new()
        .add_price("一等奖", 1)
        .add_price("二等奖", 1)
        .add_price("三等奖", 5)
        .build::<usize>();


    for it in v {
        lottery.sample(it);
        println!("{:?}", lottery.samples());
    }

    println!("{:?}", lottery.release().unwrap());
}

优点

流式处理，可以适应任意规模的参与人群
在保证每一位抽奖者都有相同的概率获得特定奖项的同时，还能保证每一个抽奖者的获得的奖项均不相同

缺点

所有参与抽奖的人都必须依次经过服务器处理，因为需要获知准确的总人数来保证等概率性。一个改进的方法是，在人数足够多的时候，将总人数用总人数的特定数量级替代（给后续参加者的一点点小福利——但是因为总人数足够多，所以总体中奖概率还是很低），在客户端完成中奖的选定
等概率性完全依赖随机数 r 生成。因为奖品初始化时不需要考虑打乱顺序，因此如果在随机这一步被技术破解，使得抽奖者可以选择自己能获取的奖项，则会破坏公平性。改进方案是，在 release 的时候再一次对奖品顺序进行随机的打乱。
这种抽奖方式还限定了每人只能抽取一次奖品，否则会出现一个人占有多个奖项的情况。

可以参考博主以前的博客

作者理解的面向对象 = 对象是交互的最基本单元 + 对象通过相互发送消息进行交互。而特质/接口以及对象其他公开的方法定义了对象可以向外发送/从外接收的消息。

该条件为用以减轻开奖时发通知的压力，并非核心需求，因为对参与抽奖的玩家负责的原因，我们还是需要储存每个玩家每次的抽奖情况信息

下一步可能展开的工作

目前所有抽奖者都按照相等的概率抽奖，而在一些场景下可能按照一些规则给与某些抽奖者优惠（例如绩效越高的员工中奖概率越大），因此下一步可能考虑如何按照权重赋予每位抽奖者各自的中奖概率。

致谢

感谢茶壶君（@ksqsf）一语惊醒梦中人，清楚明确地表达了需求；感谢张汉东老师 (@ZhangHanDong)老师提点了之后可以开展研究的方向；感谢在这次讨论中提供意见的其他 Rust 社区的朋友，谢谢你们！

总结一次面试

最值得总结的三个问题

线程同步有哪些方法？如何用这些方法实现一个 RwLock？

线程同步的目的在于解决多个线程访问关键资源时的竞争状态。一个数据竞争的简单例子如下：

use std::thread;
fn main() {
  let mut s = String::from("Hello");

  let thread1 = thread::spawn(|| {
    println!("{}", s);
  });

  let thread2 = thread::spawn(|| {
    s.push_str("World!");
    println!("{}", s);
  });

  thread1.join();
  thread2.join();
}

上文的代码中 thread1 试图打印 s, 预期得到输出 Hello, 但是 thread2 却改变了 s 的内容，那么 thread1 最终打印内容将取决于两个线程哪个先完成: 如果 thread1 先完成了，那么将打印 Hello; 如果 thread2 先完成了，那么将打印 HelloWorld!。

实际上得益于 Rust 的所有权系统与生命周期（lifetime）检查，上述示例并不能编译——子线程可能会在主程序结束后继续运行，导致子线程捕获的 s 的引用失效；另外 thread2 直接修改了 s，换言之只会允许 thread2 独占地持有 s 的可变引用（&mut s)，而不允许其他线程持有 s 的任何引用。

在 Rust 编程中，主要有以下线程同步的方法：

互斥锁(Mutex) 我们可以使用互斥锁 Mutex<T> 来控制只能有单独一个线程读取/修改对象。通常实践是在外面加上原子引用计数 Arc 变成 Arc<Mutex<T>>，来减少 Mutex 拷贝的开销。对于多读少写的场景，可以用 RwLock 提高并发。
条件变量(CondVar) 条件变量用于“阻塞”线程并使得线程在等待事件时不需要消耗 CPU 时间。通常会与放进互斥锁布尔型的预言值（状态值）关联使用，在状态值发生变化时通知条件变量。
屏障(Barrier) 屏障用于在某个需要若干线程 都完成 前置操作后再开始计算的操作之前，让所有所需线程的状态都达到能开始进行计算的状态。

有什么问题是生存期标注无法修正的？请给出一个例子

这道问题最后我也并没有理解，“生命周期标注无法修正的问题”，字面意思是，即使我们按照我们期望的程序语义来修正了生命周期标注，这个程序仍然不能通过编译，或者再运行时仍然不能得到期望结果。按此描述，一个可能的例子是，我们尝试从一个较短的引用返回一个较长的引用：

fn longhten<'a>(s_ref: &'a str) -> &'static str {
    s_ref
}

fn main() {
    let s = String::from("hello");

    let static_ref = longhten(&s);

    println!("{}", static_ref);
}

Waker 如何被唤醒？ Reactor要怎么实现？

Reactor 作为反应器，上面同时挂载了成千上万个待唤醒的事件，这里使用了mio统一封装了操作系统的多路复用API。在Linux中使用的是Epoll¹，在Mac中使用的则是Kqueue²

loop {
    // 轮询事件是否超时
    poll.poll(&events, timeout);
    for event in events.iter() {
        if (event.is_readable()) {
            for waker in event.readers.wakers {
                waker.wake();
            }
        }
        if (event.is_writeable()) {
            for waker in event.writers.wakers {
                waker.wake();
            }
        }
    }
}

一面 -- 手写代码

1. 实现一个二分查找函数

#![allow(unused)]
fn main() {
use std::cmp::Ordering;

/// 给出一个从小到大排列的数组，请实现一个函数，用二分法把指定数组 x 的位置找出来。若 x
/// 不存在，则返回 -1. 若 x 存在多个，请返回 x 在数组中第一次出现的位置
fn find(arr: Vec<i32>, x: i32) -> i32 {
    let (mut left, mut right) = (0, arr.len() - 1);
    loop {
        if left > right {
            return -1;
        }

        let mut mid = (left + right) / 2;
        match arr[mid].cmp(&x) {
            // 记得要排除已经命中的元素！
            Ordering::Less => left = mid + 1,
            Ordering::Greater => right = mid - 1,
            Ordering::Equal => {
                while mid >= 1 && arr[mid - 1] == x {
                    mid -= 1;
                }

                return mid as i32;
            },
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn should_return_minus1() {
        let arr = vec![1, 3, 5];
        let x = 2;

        assert_eq!(find(arr, x), -1);
    }

    #[test]
    fn should_return_mid() {
        let arr = vec![1, 3, 5, 7, 9, 10, 10];
        let x = 7;

        assert_eq!(find(arr, x), 3);
    }

    #[test]
    fn should_return_first() {
        let arr = vec![1, 3, 5, 7, 9, 10, 10];
        let x = 10;

        assert_eq!(find(arr, x), 5);
    }
}
}

Q: 请分析该函数的算法复杂度？
- A: 时间复杂度 $ O(\log n) $，最坏情况下的事件复杂度是 $ O(n) $
Q: 请优化这个算法？
- A：一个优化方法是 插值查找法，利用如下公式自动根据查找到的元素与目标的距离来修正下一次查找的区间范围，提高查找速度：

\[ mid = left + { key - arr[left] \over arr[right] - key } (right - left) \]

2. 镜像二叉树

请反转二叉树。如给出以下二叉树：

     1
   /   \
  2     3
 / \   / \
4   5 6   7

反转为：

     1
   /   \
  3     2
 / \   / \
7   6 5   4

递归解法：

#![allow(unused)]
fn main() {
use std::convert::Into;

struct Node {
    val: i32,
    left: NodeLink,
    right: NodeLink,
}

type NodeLink = Option<Box<Node>>;

fn construct_tree() -> Box<Node> {
    let l3left1 = Node {
        val: 4,
        left: None,
        right: None,
    };

    let l3right1 = Node {
        val: 5,
        left: None,
        right: None,
    };

    let l3left2 = Node {
        val: 6,
        left: None,
        right: None,
    };

    let l3right2 = Node {
        val: 7,
        left: None,
        right: None,
    };

    let l2left = Node {
        val: 2,
        left: Some(Box::new(l3left1)),
        right: Some(Box::new(l3right1)),
    };


    let l2right = Node {
        val: 3,
        left: Some(Box::new(l3left2)),
        right: Some(Box::new(l3right2)),
    };

    Box::new(Node {
        val: 1,
        left: Some(Box::new(l2left)),
        right: Some(Box::new(l2right)),
    })
}

fn construct_mirror() -> Box<Node> {
    let l3left1 = Node {
        val: 7,
        left: None,
        right: None,
    };

    let l3right1 = Node {
        val: 6,
        left: None,
        right: None,
    };

    let l3left2 = Node {
        val: 5,
        left: None,
        right: None,
    };

    let l3right2 = Node {
        val: 4,
        left: None,
        right: None,
    };

    let l2left = Node {
        val: 3,
        left: Some(Box::new(l3left1)),
        right: Some(Box::new(l3right1)),
    };


    let l2right = Node {
        val: 2,
        left: Some(Box::new(l3left2)),
        right: Some(Box::new(l3right2)),
    };

    Box::new(Node {
        val: 1,
        left: Some(Box::new(l2left)),
        right: Some(Box::new(l2right)),
    })
}

impl Into<Vec<i32>> for Box<Node> {
    fn into(mut self) -> Vec<i32> {
        let v_left: Vec<i32>;
        let v_right: Vec<i32>;
        v_left = if let Some(node) = self.left.take() {
            node.into()
        } else {
            Vec::new()
        };

        v_right = if let Some(node) = self.right.take() {
            node.into()
        } else {
            Vec::new()
        };

       let mut v = Vec::new();
       v.push(self.val);
       v.extend(v_left.into_iter());
       v.extend(v_right.into_iter());

       v
    }
}

fn mirror(root: &mut Node) {
    let (mut tmp_left, mut tmp_right) = (NodeLink::None, NodeLink::None);

    if let Some(mut node) = root.left.take() {
        mirror(&mut node);
        tmp_left = Some(node);
    }

    if let Some(mut node) = root.right.take() {
        mirror(&mut node);
        tmp_right = Some(node);
    }

    root.left = tmp_right;
    root.right = tmp_left;
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn should_mirrored() {
        let mut tree = construct_tree();
        let expect = construct_mirror();

        let mirror = mirror(&mut tree);
        assert_eq!(<Box<Node> as Into<Vec<i32>>>::into(tree), <Box<Node> as Into<Vec<i32>>>::into(expect));
    }
}
}

Q: 请优化这个算法？
- A：如果不用递归（因为递归会加深调用栈），可以使用 广度优先搜索算法 来自根向叶逐层反转左右子节点的指针，并将子节点的指针放入到队列中待进行处理。

线程同步 -- 百度百科

Rust异步浅谈 -- leaxoy

用 `Bevy` 游戏引擎编写贪吃蛇（译）

原文：https://mbuffett.com/posts/bevy-snake-tutorial/#0.3

Bevy 最近普及开来了，但是相关学习资料还是很少。这篇文章尝试提供 Bevy 官方书（The Bevy book）的下一步学习。最后产品看起来像这样：

这大约是 300 行 Rust 代码；也需要花点时间深入。如果你想快进到成品代码，请点这里。每一个小节开头都有一份代码差异，这应该会在你不是很清晰哪里需要插入代码的时候更加清晰一点。

新的空的 Bevy 应用

点击查看差异

我们现在像 Bevy 官方书那样开始，整一个啥都不干的应用。运行 cargo new bevy-snake, 然后把以下代码放到你的 main.rs ：

use bevy::prelude::*;

fn main() {
    App::build().run();
}

我们还需要在 Cargo.toml 将 Bevy 作为依赖添加，因为我（原文作者，下同）知道这个教程之后要干嘛，我们现在也提前添加 rand库吧。

// ...

[dependencies]
bevy = "0.3.0"
rand = "0.7.3"

创建窗口

点击查看差异

我们现在要创建一个2D游戏，需要很多不同的系统；用来创建窗口的，用来做渲染循环的，用来处理输出的，用来处理精灵（sprites)的，等等。幸运的是，Bevy的默认插件给了我们以上所有选项：

fn main() {
    App::build().add_plugins(DefaultPlugins).run();
}

然而 Bevy 的默认插件不包括摄像机（camera），所以我们来插入一个 2D 摄像机，只要我们创建我们第一个系统就可以设置了：

fn setup(mut commands: Commands) {
    commands.spawn(Camera2dComponents::default());
}

Cammands 通常用来排列命令，来更改游戏世界与资源。在这里，我们创建一个带有 2D 摄像机组件的实体。为Bevy的魔法做点准备吧：

App::build()
    .add_startup_system(setup.system()) // <--
    .add_plugins(DefaultPlugins)
    .run();

我们需要做的只是在我们的函数是调用 .system()，然后 Bevy 会神奇地在启动地时候调用 commands 参数。再运行一次 app，你应该能看到一个像这样的空窗口：

开始编写一条蛇

点击查看差异

我们来写个蛇头放在窗口上吧。我们先定义几个结构体：

struct SnakeHead;
struct Materials {
    head_material: Handle<ColorMaterial>,
}

SnakeHead 仅仅是一个空结构体，我们会把它当作一个组件来使用，它就是像某种标签，我们会放到一个实体上，之后我们能通过查询带有 SnakeHead 组件的实体来找到这个实体。像这样的空结构体在 Bevy 中是一种常见的模式，组件经常不需要他们自己的任何状态。 Materials 以后会变成一种资源，用来存储我们给蛇头使用的材质，也会用来存储蛇身和食物的材质。

head_material 句柄应该在游戏设置的时候就应该创建好，所以我们接下来要做的是，修改我们的 setup 函数：

fn setup(mut commands: Commands, mut materials: ResMut<Assets<ColorMaterial>>) {
    commands.spawn(Camera2dComponents::default());
    commands.insert_resource(Materials {
        head_material: materials.add(Color::rgb(0.7, 0.7, 0.7).into()),
    });
}

注意： Bevy要求在注册系统时按照特定的顺序。命令（Commands） -> 资源（Resources） -> 组件（Components）/查询（Queries）。如果你在弄乱一个系统之后获得一个神秘的编译时错误，请检查你的顺序。

materials.add 会返回 Handle<ColorMaterial>。我们创建了使用这个新建 handle 的 Materials 结构体。之后，我们尝试访问类型为 Materials 的资源， Bevy会找到我们这个结构体。现在我们来在新的系统里创建我们的蛇头实体，然后你会看到我们如何使用前述资源的：

fn game_setup(mut commands: Commands, materials: Res<Materials>) {
    commands
        .spawn(SpriteComponents {
            material: materials.head_material.clone(),
            sprite: Sprite::new(Vec2::new(10.0, 10.0)),
            ..Default::default()
        })
        .with(SnakeHead);
}

现在我们有了新的系统，它会寻找类型为 Materials 的资源。它也会创建（spawn）一个新实体，带有 SpriteComponents 和 SnakeHead 组件。为了创建 SpriteComponents, 我们将我们之间创建的颜色的 handle 传入，并且给精灵 10x10 的大小。我们将这个系统添加到我们 app 的构建器：

.add_startup_system(setup.system())
.add_startup_stage("game_setup") // <--
.add_startup_system_to_stage("game_setup", game_setup.system()) // <--

我们需要一个新的场景而不是再一次调用 add_startup_system 的原因是，我们需要使用在 setup 函数中插入的资源。这次运行后，你应该在屏幕中央看到蛇头：

好了，可能我们叫它“蛇头”有点过了，你可以看到一个 10x10 的白色精灵。

移动小蛇

点击查看差异

如果小蛇不运动，那么游戏很无趣，所以我们先让蛇头动起来。我们之后再担心输入，现在我们的目标是让蛇头移动。所以我们来创建一个系统来移动所有的蛇头：

fn snake_movement(mut head_positions: Query<(&SnakeHead, &mut Transform)>) {
    for (_head, mut transform) in head_positions.iter_mut() {
        *transform.translation.y_mut() += 2.;
    }
}

这里有个新概念， Query 类型。我们用它来迭代所有拥有 SnakeHead 组件以及 Transform 组件的实体。我们不需要担心实际上如何创建查询类型， bevy 会帮我们创建好并用它调用我们的函数，算是 ECS 魔法的一部分。所以我们来加上这个系统，然后看看会发生些什么：

.add_startup_system_to_stage("game_setup", game_setup.system())
.add_system(snake_movement.system()) // <--
.add_plugins(DefaultPlugins)

这是我们看到的，一头蛇移出了屏幕：

你可能再思考 Transform 组件。当我们生成 SnakeHead 时，我们并没有给它 Transform，所以我们怎么就能找到一个同事拥有 SnakeHead 和 Transform 组件的实体呢？实际上 SpriteComponents 是一捆组件。就 SpriteComponents 来说，它包含了 Transform 组件，以及一堆其他组件（如 Sprite, Mesh, Draw, Rotation, Sale）。

控制小蛇

我们来修改我们小蛇的移动系统，使得我们可以控制小蛇：

fn snake_movement(
    keyboard_input: Res<Input<KeyCode>>,
    mut head_positions: Query<With<SnakeHead, &mut Transform>>,
) {
    for mut transform in head_positions.iter_mut() {
        if keyboard_input.pressed(KeyCode::Left) {
            *transform.translation.x_mut() -= 2.;
        }
        if keyboard_input.pressed(KeyCode::Right) {
            *transform.translation.x_mut() += 2.;
        }
        if keyboard_input.pressed(KeyCode::Down) {
            *transform.translation.y_mut() -= 2.;
        }
        if keyboard_input.pressed(KeyCode::Up) {
            *transform.translation.y_mut() += 2.;
        }
    }
}

留意到我们的查询 Query<(&SnakeHead, &mut Transform)> 改为了 Query<With<SnakeHead, &mut Transform>>，其实当前版本没有必要更改，旧的查询依然能很好地工作。我想，第一个系统的类型签名可能简单些，但是现在我们用正确的方式编写类型。这写法更正确是因为我们其实不需要 SnakeHead 组件。所以 With 类型允许我们说，“我们需要那些有蛇头的实体，但是我不关心蛇头组件，只给我 transform 组件就好。”每个系统访问的组件越少，bevy就能并行越多的系统。例如，如果另外一个系统正在修改 SnakeHead 组件，那这个系统旧不能在用旧写法的时候并行了。

现在，我们能控制小蛇了，尽管它动起来不那么像蛇：

码格子

点击查看差异

到现在我们一直在用窗口的坐标，但这种方法只能在 (0, 0) 坐标在窗口正中央，并且单位是像素的时候有效。贪吃蛇游戏通常用格子，所以如果我们把我们的贪吃蛇设置成 10x10，那我们的窗口会真的很小。我们让日子变得轻松些吧，我们选择用我们自己的位置和尺寸。然后，我们用系统来处理变换到窗口的坐标。

我们先定义格子为 10x10。在程序文件开头定义如下变量：

const ARENA_WIDTH: u32 = 10;
const ARENA_HEIGHT: u32 = 10;

以及我们用于处理位置/尺寸的结构体：

#[derive(Default, Copy, Clone, Eq, PartialEq, Hash)]
struct Position {
    x: i32,
    y: i32,
}

struct Size {
    width: f32,
    height: f32,
}
impl Size {
    pub fn square(x: f32) -> Self {
        Self {
            width: x,
            height: x,
        }
    }
}

相对直接地，有一个辅助方法来获取一个有相等长宽的 Size. Position 派生了一些很有用的 trait，所以我们不必不停地回顾这个结构体。 Size 可以仅仅包含一个浮点数，因为所有的对象最后都有相等的长度和宽度，但是我给它长度和宽度好像有点不对。我们现在把这些组件添加到我们生成的蛇头上：

commands
    .spawn(SpriteComponents {
        material: materials.head_material.clone(),
        sprite: Sprite::new(Vec2::new(10.0, 10.0)),
        ..Default::default()
    })
    .with(SnakeHead)
    .with(Position { x: 3, y: 3 }) // <--
    .with(Size::square(0.8)); // <--

这些组件暂时不做任何事情，我们现在就来将我们的尺寸映射到精灵的尺寸：

fn size_scaling(windows: Res<Windows>, mut q: Query<(&Size, &mut Sprite)>) {
    let window = windows.get_primary().unwrap();
    for (sprite_size, mut sprite) in q.iter_mut() {
        sprite.size = Vec2::new(
            sprite_size.width / ARENA_WIDTH as f32 * window.width() as f32,
            sprite_size.height / ARENA_HEIGHT as f32 * window.height() as f32,
        );
    }
}

这个尺寸变换逻辑是这样的：如果某个对象有一个单位格子宽度，格子宽40，然后窗口现在 400px 宽，那么它应该有10哥宽度。下面我们做位置系统：

fn position_translation(windows: Res<Windows>, mut q: Query<(&Position, &mut Transform)>) {
    fn convert(pos: f32, bound_window: f32, bound_game: f32) -> f32 {
        let tile_size = bound_window / bound_game;
        pos / bound_game * bound_window - (bound_window / 2.) + (tile_size / 2.)
    }
    let window = windows.get_primary().unwrap();
    for (pos, mut transform) in q.iter_mut() {
        transform.translation = Vec3::new(
            convert(pos.x as f32, window.width() as f32, ARENA_WIDTH as f32),
            convert(pos.y as f32, window.height() as f32, ARENA_HEIGHT as f32),
            0.0,
        );
    }
}

位置变换：如果项目的 X 坐标在我们的系统中是 5，宽度是 10，并且窗口宽度是200，那么坐标应该是 5/10 * 200 - 200 / 2。我们减去一半的窗口宽度，因为我们的做消息是从左下角开始，然后替换到正中央。然后我们再加上半个格子，因为我们想要我们精灵的左下角对齐格子的左下角，而不是精灵中心对齐。

然后我们把这些系统加到我们的应用构建器上：

.add_system(snake_movement.system())
.add_system(position_translation.system()) <--
.add_system(size_scaling.system()) <--
.add_plugins(DefaultPlugins)
.run();

注意： 现在最明显的问题是小蛇被压扁了。另外一个问题是我们破环了我们的输入处理。我们先修复输入处理，然后我们得记得回来处理我们被压扁的小蛇，把它恢复原状。

使用我们的格子

点击查看差异

我们现在配置好了格子坐标，现在我们需要更新我们的 snake_movement 系统。之前我们使用 Transform 的地方，现在替换成 Position：

fn snake_movement(
    keyboard_input: Res<Input<KeyCode>>,
    mut head_positions: Query<With<SnakeHead, &mut Position>>,
) {
    for mut pos in head_positions.iter_mut() {
        if keyboard_input.pressed(KeyCode::Left) {
            pos.x -= 1;
        }
        if keyboard_input.pressed(KeyCode::Right) {
            pos.x += 1;
        }
        if keyboard_input.pressed(KeyCode::Down) {
            pos.y -= 1;
        }
        if keyboard_input.pressed(KeyCode::Up) {
            pos.y += 1;
        }
    }
}

调整窗口大小 1

点击查看差异

我们上一步中的小蛇被压扁了，是因为默认的窗口尺寸并不是方形的，然而我们的格子是，所以我们每个格坐标会宽度长于高度。我们修复它最简单的方法，是在构建 app 的时候创建一个 WindowDescriptor 资源：

    App::build()
        .add_resource(WindowDescriptor { // <--
            title: "Snake!".to_string(), // <--
            width: 200,                 // <--
            height: 200,                // <--
            ..Default::default()         // <--
        })
        .add_startup_system(setup.system())

同时，我们改一下背景颜色，插入这个 use 语句来引入 ClearColor 结构体：

use bevy::render::pass::ClearColor;

然后在 app 构建器增加资源：

.add_resource(ClearColor(Color::rgb(0.04, 0.04, 0.04)))

原文中这里的规格是 2000，但是 2000 的规则放 10x10 显然太大了，这里改成 200

生成食物

现在我们的小蛇可以到处移动了，该喂点东西给它了。现在我们给 Materials 加一个 food_materials 字段：

struct Materials {
    head_material: Handle<ColorMaterial>,
    food_material: Handle<ColorMaterial>, // <--
}

然后把这个新材质加到我们的 setup 函数里：

commands.insert_resource(Materials {
    head_material: materials.add(Color::rgb(0.7, 0.7, 0.7).into()),
    food_material: materials.add(Color::rgb(1.0, 0.0, 1.0).into()), // <--
});

然后我们需要 Duration 给要创建的定时器使用，而且我们还需要 random 来随机分配食物的位置。先在程序里引入这些：

use rand::prelude::random;
use std::time::Duration;

然后我们因素两个新结构体： Food 组件让我们知道哪个实体是食物，以及一个定时制造食物的定时器：

struct Food;

struct FoodSpawnTimer(Timer);
impl Default for FoodSpawnTimer {
    fn default() -> Self {
        Self(Timer::new(Duration::from_millis(1000), true))
    }
}

至于实现 Default 的原因，会在我解释下面的系统的时候说明：

fn food_spawner(
    mut commands: Commands,
    materials: Res<Materials>,
    time: Res<Time>,
    mut timer: Local<FoodSpawnTimer>,
) {
    timer.0.tick(time.delta_seconds);
    if timer.0.finished {
        commands
            .spawn(SpriteComponents {
                material: materials.food_material.clone(),
                ..Default::default()
            })
            .with(Food)
            .with(Position {
                x: (random::<f32>() * ARENA_WIDTH as f32) as i32,
                y: (random::<f32>() * ARENA_HEIGHT as f32) as i32,
            })
            .with(Size::square(0.8));
    }
}

我们引入了局部资源概念，具体而言是 timer 参数。 Bevy 会看到这个参数并且实例化一个 FoodSpawnTimer 类型的值，用的是我们的 Default 实现。这会在这个系统第一次运行是发生，之后这个系统会一直重用相同的定时器。像这样使用局部资源要比手动注册资源更贴近工程化。这个定时器会一直重复，所以我们只需要调用 tick 函数，然后无论这个系统在定时器完成后什么时候跑，我们就随机创建一些食物。

你可能知道下一步是什么了，把这个系统加到应用构建器上：

.add_system(food_spawner.system())

现在我们的程序看起来像这样：

更像蛇的移动

点击查看差异

我们现在准备定时触发小蛇移动。具体说来，我们想小蛇一直在移动，无论我们是否按下按键；并且我们想要它每隔 X 秒移动一次，而不是每一帧都移动。我们会改动几个地方，所以如果你不太清楚要改动哪里，查看这一小节的差异吧。

首先，我们需要加一个方向枚举：

#[derive(PartialEq, Copy, Clone)]
enum Direction {
    Left,
    Up,
    Right,
    Down,
}

impl Direction {
    fn opposite(self) -> Self {
        match self {
            Self::Left => Self::Right,
            Self::Right => Self::Left,
            Self::Up => Self::Down,
            Self::Down => Self::Up,
        }
    }
}

然后把这个方向枚举加到我们的 SnakeHead 结构体，使得它知道应该要往哪里移动：

struct SnakeHead {
    direction: Direction,
}

我们也得在实例化 SnakeHead 组件的时候给定初始方向，例如我们让它一开始往上走：

.with(SnakeHead {
    direction: Direction::Up,
})

小蛇通常移动不是很流畅，是一种一步步来的行动。就行我们生成食物的时候，我们需要使用定时器来让系统没每隔 X秒/毫秒才跑一次。我们需要创建一个结构体来持有定时器：

struct SnakeMoveTimer(Timer);

然后我们把它当成资源加到我们的 app 构建器：

.add_resource(SnakeMoveTimer(Timer::new(
    Duration::from_millis(150. as u64),
    true,
)))

我们之所以不把这个定时器像生成食物的时候把定时器看成局部资源，是因为我们将会在几个系统里用上它，所以我帮你节约了一些重构的工作。因为我们需要在几个系统里使用它，我们需要创建一个新系统来触发这个定时器：

fn snake_timer(time: Res<Time>, mut snake_timer: ResMut<SnakeMoveTimer>) {
    snake_timer.0.tick(time.delta_seconds);
}

我们也可以把这段触发逻辑直接放到 snake_movement 系统里，但是我比较喜欢整洁地吧它放到一个单独的系统中，因为这个定时器会用在几个地方。我们把这个系统也加到 app上：

.add_system(snake_timer.system())

现在我们可以做方向逻辑的核心部分，也就是 snake_movement 系统，以下是更新后的版本：

fn snake_movement(
    keyboard_input: Res<Input<KeyCode>>,
    snake_timer: ResMut<SnakeMoveTimer>,
    mut heads: Query<(Entity, &mut SnakeHead)>,
    mut positions: Query<&mut Position>,
) {
    if let Some((head_entity, mut head)) = heads.iter_mut().next() {
        let mut head_pos = positions.get_mut(head_entity).unwrap();
        let dir: Direction = if keyboard_input.pressed(KeyCode::Left) {
            Direction::Left
        } else if keyboard_input.pressed(KeyCode::Down) {
            Direction::Down
        } else if keyboard_input.pressed(KeyCode::Up) {
            Direction::Up
        } else if keyboard_input.pressed(KeyCode::Right) {
            Direction::Right
        } else {
            head.direction
        };
        if dir != head.direction.opposite() {
            head.direction = dir;
        }
        if !snake_timer.0.finished {
            return;
        }
        match &head.direction {
            Direction::Left => {
                head_pos.x -= 1;
            }
            Direction::Right => {
                head_pos.x += 1;
            }
            Direction::Up => {
                head_pos.y += 1;
            }
            Direction::Down => {
                head_pos.y -= 1;
            }
        };
    }
}

这里没有什么新概念，仅仅是游戏逻辑。你可能在想为什么我们需要获取拥有 SankeHead 组件的 Entity，然后用另外一个独立的查询来获取位置，而不是用像 Query<Entity, &SnakeHead, &mut Position> 这样的参数。原因在于，我们之后可能需要其他实体的位置，而分开两个查询访问相同的组件是不会允许放在 Bevy app 构建器上的。这样改了之后，你会获得一个蛇头移动的稍微……像蛇一样：

加个尾巴

点击查看差异

小蛇的尾巴有点复杂。对于每蛇尾的分段，我们需要知道它下一步需要到哪里。我们准备这样实现：将这些分段放到 Vec，然后存储为资源。这样，当我们更新分段的位置时，我们能够迭代所有的分段并且设置每个分段的位置为前一个分段的位置。

我们加一个 segment_material 字段到我们趁手的 Materials 结构体：

struct Materials {
    head_material: Handle<ColorMaterial>,
    segment_material: Handle<ColorMaterial>, // <--
    food_material: Handle<ColorMaterial>,
}

老调重弹，把 segment_material 加到 setup 中：

commands.insert_resource(Materials {
    head_material: materials.add(Color::rgb(0.7, 0.7, 0.7).into()),
    segment_material: materials.add(Color::rgb(0.3, 0.3, 0.3).into()), // <--
    food_material: materials.add(Color::rgb(1.0, 0.0, 1.0).into()),
});

然后一个给蛇身分段的组件：

struct SnakeSegment;

然后我们再加上我们说到的，用来存储分段列表的资源：

#[derive(Default)]
struct SnakeSegments(Vec<Entity>);

再把它作为资源加到我们的 app 上：

.add_resource(SnakeSegments::default())

我们我们需要从几个地方生成分段（当你吃食物或者你初始化小蛇的时候），我们需要先创建一个辅助函数：

fn spawn_segment(
    commands: &mut Commands,
    material: &Handle<ColorMaterial>,
    position: Position,
) -> Entity {
    commands
        .spawn(SpriteComponents {
            material: material.clone(),
            ..SpriteComponents::default()
        })
        .with(SnakeSegment)
        .with(position)
        .with(Size::square(0.65))
        .current_entity()
        .unwrap()
}

这看上去非常像我们生成 SnakeHead 的函数，但是替换了 SnakeHead 组件，我们用的是 SnakeSegment 组件。这里要说的新知识点，就是我们最后通过 current_entity 函数，获取了生成的 Entity （其实只是个 id），然后将它返回给调用者以便使用它。现在，我们需要修改我们的游戏配置函数。并非只是生成一个蛇头，它现在要生成一个蛇身的分段：

fn spawn_snake(
    mut commands: Commands,
    materials: Res<Materials>,
    mut segments: ResMut<SnakeSegments>,
) {
    segments.0 = vec![
        commands
            .spawn(SpriteComponents {
                material: materials.head_material.clone(),
                ..Default::default()
            })
            .with(SnakeHead {
                direction: Direction::Up,
            })
            .with(SnakeSegment)
            .with(Position { x: 3, y: 3 })
            .with(Size::square(0.8))
            .current_entity()
            .unwrap(),
        spawn_segment(
            &mut commands,
            &materials.segment_material,
            Position { x: 3, y: 2 },
        ),
    ];
}

我们第一个分段是头部，现在我们多加了一个 with(SnakeSegment)。第二个分段来自我们的 spawn_segment 函数。我们现在得到了一条小小的尾巴：

让尾巴跟着小蛇活动

点击查看差异

正如我记得那样，蛇尾没有脱离蛇头，是贪吃蛇游戏中重要的一部分。我们来看看，我们可以怎么修改 snake_movement 函数，来更接近原汁原味的游戏。首先要做的事把 SnakeSegments 资源到 snake_movement 函数上：

fn snake_movement(
    keyboard_input: Res<Input<KeyCode>>,
    snake_timer: ResMut<SnakeMoveTimer>,
    segments: ResMut<SnakeSegments>, // <--
    mut heads: Query<(Entity, &mut SnakeHead)>,
    mut positions: Query<&mut Position>,

现在，直接在最前面的 if let 后面，我们加上所有分段的位置（当然，不要忘了蛇头的位置）：

let segment_positions = segments
    .0
    .iter()
    .map(|e| *positions.get_mut(*e).unwrap())
    .collect::<Vec<Position>>();

然后我们要做的是在 if let 的末尾迭代蛇身分段（跳过蛇头，因为我们已经通过用户输入更新了位置），然后让每个分段的位置都变成前一个分段的。例如，第一个蛇身分段设置为当前蛇头（更新前）的位置，第二段的设置为第一段的。

segment_positions
    .iter()
    .zip(segments.0.iter().skip(1))
    .for_each(|(pos, segment)| {
        *positions.get_mut(*segment).unwrap() = *pos;
    });

现在我们的游戏看起来应该像这样：

小蛇成长

点击查看差异

小蛇已经饿坏了。我们现在需要家一个系统来让小蛇猎食：

fn snake_eating(
    mut commands: Commands,
    snake_timer: ResMut<SnakeMoveTimer>,
    mut growth_events: ResMut<Events<GrowthEvent>>,
    food_positions: Query<With<Food, (Entity, &Position)>>,
    head_positions: Query<With<SnakeHead, &Position>>,
) {
    if !snake_timer.0.finished {
        return;
    }
    for head_pos in head_positions.iter() {
        for (ent, food_pos) in food_positions.iter() {
            if food_pos == head_pos {
                commands.despawn(ent);
                growth_events.send(GrowthEvent);
            }
        }
    }
}

只是迭代所有的食物位置，来看他们是不是和蛇头共享一个位置，如果是这样，我们就用 despawn 者趁手的函数移除食物，然后触发一个 GrowthEvent。我们来创建这个结构体：

struct GrowthEvent;

使用事件是个新概念。你可以在系统间发送或接受事件，他们可以是任意类型的结构体，使得你可以在事件里包括任何你需要发送的数据。例如，你可能有一个系统发送跳跃事件，然后一个独立的系统来处理他们。在我们的这个案例中，我们需要一个系统来发送成长事件，以及一个成长系统来处理它们。你需要注册事件，就像我们对资源和系统做的那样：

.add_event::<GrowthEvent>()

然后在这里我们也加上 snake_eating 系统：

.add_system(snake_eating.system())

现在小蛇应该能够猎食了。但是小蛇现在就像个黑洞，吃多少也不长大。在思考成长这事时，需要注意我们需要知道最后的分段移动前在哪里，因为那里是新的分段成长的位置。现在我们来创建一个新资源：

#[derive(Default)]
struct LastTailPosition(Option<Position>);

然后在 app 构建器上：

.add_resource(LastTailPosition::default())

我们也要对 snake_movement 系统做一点小修改，来更新 LastTailPosition 资源。首先先把这个资源加到参数中：

fn snake_movement(
    // ...
    mut last_tail_position: ResMut<LastTailPosition>, // <--
    // ...

然后就是给这个资源分配最后的一个分段的位置。这段代码放在我们迭代过了 segment_positions 之后：

last_tail_position.0 = Some(*segment_positions.last().unwrap()); // <--

之后，小蛇成长的函数就很清晰了：

fn snake_growth(
    mut commands: Commands,
    last_tail_position: Res<LastTailPosition>,
    growth_events: Res<Events<GrowthEvent>>,
    mut segments: ResMut<SnakeSegments>,
    mut growth_reader: Local<EventReader<GrowthEvent>>,
    materials: Res<Materials>,
) {
    if growth_reader.iter(&growth_events).next().is_some() {
        segments.0.push(spawn_segment(
            &mut commands,
            &materials.segment_material,
            last_tail_position.0.unwrap(),
        ));
    }
}

以及追加系统：

.add_system(snake_growth.system())

撞墙（或者咬尾巴）

点击查看差异

现在我们来增加撞墙和咬尾巴来触发游戏结束（game over）。我们使用一个新事件，就像我们在“小蛇成长小节”中那样：

struct GameOverEvent;

并把它注册到 app 构建器上：

.add_event::<GameOverEvent>()

在我们的 snake_movement 系统中，我们想要访问 “游戏结束” 事件，使得我们能够发送事件：

fn snake_movement(
    // ...
    mut game_over_events: ResMut<Events<GameOverEvent>>, // <--
    // ...
) {

我们先关注在撞墙事件上面。把这部分代码放到 match &head.direction { 后面：

if head_pos.x < 0
    || head_pos.y < 0
    || head_pos.x as u32 >= ARENA_WIDTH
    || head_pos.y as u32 >= ARENA_HEIGHT
{
    game_over_events.send(GameOverEvent);
}

好了，现在我们的 snake_movement 系统可以发送 “游戏结束” 事件了，我们再来创建一个系统来监听这些事件：

fn game_over(
    mut commands: Commands,
    mut reader: Local<EventReader<GameOverEvent>>,
    game_over_events: Res<Events<GameOverEvent>>,
    materials: Res<Materials>,
    segments_res: ResMut<SnakeSegments>,
    food: Query<With<Food, Entity>>,
    segments: Query<With<SnakeSegment, Entity>>,
) {
    if reader.iter(&game_over_events).next().is_some() {
        for ent in food.iter().chain(segments.iter()) {
            commands.despawn(ent);
        }
        spawn_snake(commands, materials, segments_res);
    }
}

这里有个很酷的点: 我们可以直接使用 spawn_snake 函数，现在它既是一个系统，也是一个辅助函数了。

最后一个修改点，就是我们得让小蛇咬到尾巴的时候也会触发 “游戏结束” 事件。在 snake_movement 系统中，在我们检查完边界的部分后添加：

if segment_positions.contains(&head_pos) {
    game_over_events.send(GameOverEvent);
}

最后，我们的成果：

Rust 安全应用开发51条

本文摘自法国国家网络安全局(ASSNI)的《用 Rust 开发安全应用的编程规则》（PROGRAMMING RULES TO DEVELOPSECURE APPLICATIONS WITH RUST）

要使用 stable 编译工具链
要在 cargo 配置文件中将重要变量保持为默认值
要在运行 cargo 时保持编译环境变量为默认值
要周期地使用 linter
要使用 Rust 格式器（rustfmt）
要人工检查自动修复
要检查依赖版本是否过期（cargo-outdated)
要检查依赖的安全脆弱性（vulnerabilities）（cargo-audit)
要遵循命名转换
不要使用 unsafe 块
要用合适的算术操作来处理潜在的溢出
推荐实现包含了所有可能错误的自定义错误类型
推荐使用 ? 操作符且不使用 try! 宏
不要使用能导致 panic! 的函数
要测试数组索引使用是否正确，或者使用 get 方法
要在 FFI 中正确地处理 panic!
不要使用 forget
推荐使用 clippy 检查 forget 的使用
不要泄露内存
要释放包裹在 ManaullyDrop 里的值
总是调用 into_rawed 值对应的 from_raw 函数
不要使用未初始化内存
使用完敏感数据后要将内存清零
推荐校验 Drop 实现
不要再 Drop 实现内部恐慌（panic）
不允许 Drop 的循环引用
推荐不依赖 Drop 来保证安全
推荐校验 Send 和 Sync 实现
要遵循标准库比较特质（trait）的不变之处
推荐使用标准库比较特质的默认实现
推荐尽可能派生（derive）比较特质
要在 FFI 中只使用 C 兼容类型
在 FFI 边界要使用兼容性的类型
推荐使用绑定自动生成工具
在绑定到平台依赖类型时，要使用可移植别名 c_*
推荐在 Rust 中检查外部类型
推荐指针类型而不是引用类型¹
不要使用未检查的外部引用
检查外部指针
要标记 FFI 中的函数指针类型为 extern 和 unsafe
检查外部函数指针
建议不在 FFI 边界使用不美容的 Rust enum 类型
建议为外部不透明类型使用专门的 Rust 类型
推荐使用不完整的 C/C++ struct 指针来使得类型不透明
不要在 FFI 边界使用实现了 Drop 的类型
要确保在 FFI 中清除数据所有权
推荐将外部数据包裹在可释放内存的包装类型
要在 FFI 中正确地处理 panic!
推荐为外部库提供安全的包装
推荐只暴露专门的 C 兼容 API

在天河二号上配置 Rust 运行环境

受朋友委托，需要帮忙在“天河二号”超级计算机上配置 Rust 编程语言运行环境，并配置安装 rust-overlaps。

阅读须知

本文将不涉及：

通过 Rust 独立包安装适合天河二号的 Rust 运行环境

ssh 远程登录到天河二号¹：

$ ssh -i${YOUR_CERTIFICATE_ID} -P${SSH_PORT} ${YOUR_USERNAME}@server.ip.in.vpn

获取超算的服务器平台架构：
```
[you@tainhe2-H ~]$ uname -r
```
了解平台架构后，获取对应平台的Rust 独立安装包, 并上传至超算。此处以x86_64架构为例：
```
$ scp -i${YOUR_CERTIFICATE_ID} -P${SSH_PORT} rust-1.44.0-x86_64-unknown-linux-gnu.tar.gz you@server.ip.in.vpn:~
```

解压安装压缩包：

[you@tainhe2-H ~]$ tar -zxvf rust-1.44.0-x86_64-unknown-linux-gnu.tar.gz

切换到解压缩目录，并执行安装命令:

[you@tainhe2-H ~]$ cd rust-1.44.0-x86_64-unknown-linux-gnu
[you@tainhe2-H rust-1.44.0-x86_64-unknown-linux-gnu]$ ./install.sh --prefix=~/rust --disable-ldconfig --verbose

此命令会将 Rust 安装在 ~/rust 文件夹中，rust 的可执行文件将会放在 ~/rust/bin文件夹中。

编辑~/.bashrc, 增加下面这一行配置：
```
export PATH=$HOME/rust/bin:$PATH
```
使~/.bashrc生效：
```
[you@tainhe2-H ~]$ source ~/.bashrc
```

检查 Rust 是否成功安装：

[you@tainhe2-H ~]$ cargo --version
cargo 1.44.0 (05d080faa 2020-05-06)

离线安装 `rust-overlaps`

在本地联网环境拷贝源代码：

git clone https://github.com/sirkibsirkib/rust-overlaps.git

修复源码的 Cargo.toml 的version²:
```
version = "1.1.0"
```
在代码仓库目录下执行 cargo vendor，获取依赖的源码³：
```
rust-overlaps$ cargo vendor --respect-source-config
```
下载好的依赖将会存放到 vendor文件夹中。
在 rust-overlaps 文件夹中添加 .cargo/config 文件，以便在超算的离线环境中使用本地缓存好的依赖源码进行编译：
```
[source.crates-io]
replace-with = "vendored-sources"

[source.vendored-sources]
directory = "vendor"
```

将源码文件夹打包成 .zip 包，然后上传到超算:

$ scp -i${YOUR_CERTIFICATE_ID} -P${SSH_PORT} rust-overlaps.zip you@server.ip.in.vpn:~

在超算中解压：

[you@tainhe2-H ~]$ unzip rust-overlaps.zip

离线安装³:

[you@tainhe2-H ~]$ cd rust-overlaps
[you@tainhe2-H rust-overlaps]$ cargo install --path . --offline

检查是否安装成功：

[you@tainhe2-H ~]$ rust-overlaps --version
ASPOPsolver 1.0

小结

当我看到 rust-overlaps 已经超过三年没有更新之后，我就觉得很可能不能够成功编译——但是 Rust 从来没有让我失望 —— 在本文中，我们使用的是最新稳定版的 Rust 1.44，然而编译一个三年的旧库一次就可以编译成功了。同样，得益于 Rust 以 crate 为单位的并行与增量编译，让编译命令中断后可以继续执行而不需从头编译。这个故事告诉我们，充分吸收现代学术成果的工具比起偏旧的工具对于效率提高有重要影响！

ssh登陆前还需登录VPN环境，账号密码为管理员提供的账号密码。

Rust仓库的版本号遵循语义化版本，因此必须为x.y.z的形式。更多参见sirkibsirkib/rust-overlaps#2

cargo编译中断，可以重新运行命令继续安装，直到安装完成。

设计模式在 Rust 中的实践

[设计模式] 在 Rust 中的应用与其在其他语言中的应用有很多不同之处，本系列为个人在使用 Rust 编程的时候遇到的一些设计模式，并结合自己的思考对 Rust 编写过程中设计模式有特点地优化。

特别提醒： 没有银弹！没有银弹！没有银弹！ 所有的设计都是为了解决特定场景下的问题，脱离场景扯设计模式都是耍流氓！

构建器（Builder）模式

示例

通常在 Rust 中的实现是通过不断重建 Builder 来构造最后的类型：

struct Counter {
    counted1: usize,
    counted2: usize,
    done: bool,
}

struct CounterBuilder {
    counted1: usize,
    counted2: usize,
}

impl CounterBuilder {
    // 构建器需要有默认的参数配置，然后从默认配置触发进行构建。
    // 不适用 #[derive(std::default::Default)]，因为默认配置可能不一样
    fn default() -> Self {
        CounterBuiler {
            counted1: 5,
            counted2: 0,
        }
    }

    // 属性定制方法。消耗原本的构建器，修改属性后重新生成新构建器
    fn set_counted1(self, cnt: usize) -> Self {
        self.counted1 = cnt;
        self
    }

    fn set_counted2(self, cnt: usize) -> Self {
        self.counted2 = cnt;
        self
    }

    // 最后通过 `build` 方法生成所需类型
    fn build(self) -> Counter {
        Counter {
            counted1: self.counted1,
            counted2: self.counted2,
            done: false,
        }
    }
}

个人实践

在设置属性方法的时候，通常的实现是通过消耗原本的构造器后生成新构造器，这使得如果配置构造器的过程不能连续调用属性设置方法时，必须重新捕获构造器：

let mut builder = CounterBuilder::default();

// ... 进行一些计算，获得需要配置的值
let cnt1 = operations();

builder = builder.set_counted1(cnt);

// ... 进行一些计算，获得需要配置的值
let cnt2 = operations();

builder = builder.set_counted(cnt2);

以上代码通常出现在需要流计算并及时记录参数配置的时候。并且，如果构造器被更大型的数据结构持有时，消耗并重新构建构造器可能会对性能有点影响。因此在博主个人实现时通常采取传递&mut self 引用的方法来实现属性设置方法：

    // ...
    // 属性定制方法。消耗原本的构建器，修改属性后重新生成新构建器
    fn set_counted1(&mut self, cnt: usize) -> &mut Self {
        self.counted1 = cnt;
        self
    }

    fn set_counted2(&mut self, cnt: usize) -> &mut Self {
        self.counted2 = cnt;
        self
    }

// ...

改成如上形式的函数签名，即可灵活构造目标结构:

let mut builder = CounterBuilder::default();

// ... 进行一些计算，获得需要配置的值
let cnt1 = operations();

builder.set_counted1(cnt);

// ... 进行一些计算，获得需要配置的值
let cnt2 = operations();

builder.set_counted(cnt2);

// ... 可能还要等待别的操作完成后再进行构建

let counter = builder.build();

更好用的工具

本文在微信公众号发布之后，微信粉丝 @福糙·仁波切推荐了 dtolnay/proc-macro-workshop 中的 derive_builder，能够更快地实现自定义的Builder。例如，上文中的示例使用该库可以大大减少代码:

use derive_builder::Builder;

struct Counter {
    #[builder(default = "5")]
    counted1: usize,

    #[builder(default)]
    counted2: usize,

    #[builder(default)]
    done: bool,
}

甚至可以快速自定义自己的 setter：

use derive_builder::Builder;

struct Counter {
    #[builder(default = "5")]
    counted1: usize,

    #[builder(default)]
    counted2: usize,

    #[builder(default)]
    done: bool,
}

impl CounterBuilder {
    fn set_counted2(&mut self, cnt: usize) -> &mut Self {
        // 注意生成的构造器的字段为 `Option`
        self.counted2 = Some(if cnt > 100 { 100 } else { cnt });
        self
    }
}

fn main() {
    let mut builder = CounterBuilder::default();

    builder.set_counted2(123);

    let counter = builder.build();

    println!("{:?}", counter);
}

为什么使用构造器模式

构造过程可控。通常实现构造器模式的时候，我们会将构造器所需要配置的属性设置为私有¹，并且只能通过我们提供的属性设置方法进行设置，使得构造过程可控。另外，可以通过属性设置方法提前恐慌（panic）来阻止生成无效对象。
设置方法职责专一。属性设置方法职责专一，只会负责设置一种属性，只有在该属性的设置规则改变时，相应的属性设置方法才需要进行修改；
构造灵活。多个属性设置方法可以自由的组合在一起，也可以分步组合构造。
可批量构造。我们除了使用消耗性的 build(self) 方法，也可以使用非消耗性的 fn build(&self) 方法，使得构造器可以多次复用。
符合开闭原则。当某一属性的设置方法内部实现发生变化的时候，不影响其他属性的设置方式；而新增属性及其设置方法时，可以通过链式调用很方便地增加新属性的设置。

为什么不使用构造器模式

构造器模式由于有以下缺点而在部分场景中不适用：

在构造完成前无法使用被构造对象。在构造完成之前，构造器并不生成被构造对象，因此在整个构造设置完成之前，无法使用被构造对象。
构造器与被构造对象使用相同的属性设置方法，造成代码重复并无法复用。考虑需要只通过属性设置方法来修改对象的场景，当被构造对象在使用过程中需要频繁设置属性，那么就需要编写对应的属性设置方法；而如果还使用构造器进行对象构造，那么属性设置方法就会重复，并且可能造成构造器与被构造对象的属性设置行为不一致的问题²。

Rust 语言中默认语言项(Item)的可见性都是私有的，如需公开语言项给其他模块使用，需要使用 pub 关键字放开。 ²: 一个绕开的行为不一致问题的方法是将属性设置规则抽取为静态函数，但仍然无法避免过度封装的问题。不过，可以将过度封装的事情交给过程宏等自动代码生成手段，例如文中举例的 derive_builder

抽象工厂（Abstract Factory）模式

场景需求

我们在设计游戏的时候，经常会遇到设计类似关卡的需求，例如 RPG 游戏中的副本（dungeon），每种副本都循序类似的模式、类似的行为，但是采用资源不同，行为的细节可能有所差异，为了方便我们新增新的副本，同时使得原有副本的修改尽可能少影响游戏的运行机制（所谓符合开闭原则），我们可以采用抽象工厂模式来统一管理游戏副本的生成。

场景设计

我们先设计一个简单的副本模式，包含了一个 Boss 和若干小怪，小怪数量在范围内随机波动。小怪和 Boss 都拥有血量，但是只有Boss 能攻击。我们把这个模式定义为结构：

struct Dungeon {
    boss: Box<dyn Boss>,
    monsters: Vec<Box<dyn Monster>>,
}

trait Monster {
    // 获知当前血量
    fn life(&self) -> u64;

    // 怪物血量可以因受到攻击降低，也可自行回复
    fn change_life(&mut self, diff: i32);
}

trait Boss: Monster {
    // Boss 能攻击玩家（Hero）
    fn attack(&self target: &mut Box<dyn Hero>);
}

上面在运行时已经不关心具体是什么副本（当然，副本的元数据可以添加为 Dungeon 结构的字段），我们只需要知道它有一个 Boss 和若干 Monster。

然后，我们建立抽象工厂：

use rand::random;
trait DungeonFactory {
    fn create_boss(&self) -> Box<dyn Boss>
    fn create_mosters(&self, amount: usize) -> Vec<Box<dyn Monster>>

    fn generate_dungeon(&self) -> Dungeon {
        Dungeon {
            boss: self.create_boss(),
            monsters: self.create_monsters(random::<u8>() % 2 + 2), // 2 ~ 3 只小怪
        }
    }
}

然后，我们创建新手副本的具体工厂:

struct NewbieDungeonFactory;

impl DungeonFactory for NewBieDungeonFactory {
    fn create_boss(&self) -> Box<dyn Boss> {
        NewBieBoss::new()
    }

    // 新手副本甚至没有小怪，
    fn create_mosters(&self, amount: usize) -> Vec<Box<dyn Monster>> {
        Vec::new()
    }

    // generate_dungeon 已有默认实现，不需要修改。
}

// 新手副本，boss极弱
struct NewbieBoss {
    max_life: u8,
    life: u8,
    attack: u8,
}

impl NewbieBoss {
    fn new() -> Self {
        NewBieBoss {
            max_life: 5,
            life: 5,
            attack: 1,
        }
    }
}

impl Monster for NewBieBoss {
    fn life(&self) -> u64 {
        self.life as u64
    }

    fn change_life(&mut self, diff: i32) {
        self.life = match self.life + diff {
            n if n < 0 => 0,
            n if n > self.max_life => self.max_life
            n => n
        };
    }
}

impl Boss for NewbieBoss {
    fn attack(&self, target: &mut Box<dyn Hero>) {
        target.attacked_wtih(self.attack);
    }
}

上面的工厂看上去好像很多内容，主要是因为 Boss特质需要一个新载体 NewBieBoss，同时实现 Boss 载体的 NewBieBoss 也需要实现 Monster 特质（继承关系组合化）, 这部分的代码作为示例让读者理解设定的 Dungeon 模式的行为。

接下来，我们可以新增一个新副本，新副本的小怪和 Boss 是新手副本的 NewbieBoss，但是小怪已经不能攻击玩家了（通过动态分发为 dyn Monster 对象来屏蔽 Boss 的攻击行为：

struct JuniorDungeonFactory;

impl DungeonFactory for JuniorDungeonFactory {
    fn create_boss(&self) -> Box<dyn Boss> {
        NewBieBoss::new()
    }

    // 新手副本甚至没有小怪，
    fn create_mosters(&self, amount: usize) -> Vec<Box<dyn Monster>> {
        vec![NewBieBoss::new(); amount]
    }

    // generate_dungeon 已有默认实现，不需要修改。
}

我们可以看到，抽象工厂模式很方便地为我们重用了已有资源并确保副本的行为效果。

为什么使用抽象工厂模式

模式统一。通过抽象工厂可以快速地制作符合相同模式，但是资源细节稍有差异的工厂，生成具有同样属性的产品。
职责专一。每个具体工厂只有一个原因需要被修改——该工厂对应的副本细节变化了。
符合开闭原则。因为我们统一出了抽象工厂的接口，当我们修改具体工厂的具体实现细节时，并不会影响到接口调用；而新增具体工厂时只需要提供对应的接口，也可以方便地接入副本生成系统。

Rust 镜像

由于在 Rust 群经常有新人重复提问诸如 “Rust 下载很慢，怎么办？” “Rust 怎么安装更快” 一类的提问，因此整理国内常用的用于加速的镜像和反向代理。

阅读须知

本文将不涉及：

如何获得 Rustup（Rust编程语言推荐工具链管理程序）
如何在各平台安装 Rustup （尽管下文会涉及到 Rustup 加速镜像有哪些可用）

使用国内镜像加速更新 Rustup 工具链

我们需要指定 RUSTUP_DIST_SERVER（默认指向 https://static.rust-lang.org）和 RUSTUP_UPDATE_ROOT （默认指向https://static.rust-lang.org/rustup），这两个网站均在中国大陆境外，因此在中国大陆访问会很慢，需要配置成境内的镜像。

以下 RUSTUP_DIST_SERVER 和 RUSTUP_UPDATE_ROOT 可以组合使用。

# 清华大学
RUSTUP_DIST_SERVER=https://mirrors.tuna.tsinghua.edu.cn/rustup

# 中国科学技术大学
RUSTUP_DIST_SERVER=https://mirrors.ustc.edu.cn/rust-static
RUSTUP_UPDATE_ROOT=https://mirrors.ustc.edu.cn/rust-static/rustup

# 上海交通大学
RUSTUP_DIST_SERVER=https://mirrors.sjtug.sjtu.edu.cn/rust-static/

使用国内镜像加速更新 crate 拉取

将如下配置写入 $HOME/.cargo/config 文件¹ ²：

# 放到 `$HOME/.cargo/config` 文件中
[source.crates-io]
registry = "https://github.com/rust-lang/crates.io-index"

# 替换成你偏好的镜像源
replace-with = 'sjtu'

# 清华大学
[source.tuna]
registry = "https://mirrors.tuna.tsinghua.edu.cn/git/crates.io-index.git"

# 中国科学技术大学
[source.ustc]
registry = "git://mirrors.ustc.edu.cn/crates.io-index"

# 上海交通大学
[source.sjtu]
registry = "https://mirrors.sjtug.sjtu.edu.cn/git/crates.io-index"

# rustcc社区 - 已失效！
# [source.rustcc]
# registry = "https://code.aliyun.com/rustcc/crates.io-index.git"

# rustcc 1号源
[source.rustcc]
registry="git://crates.rustcc.com/crates.io-index"

# rustcc 2号源
[source.rustcc2]
registry="git://crates.rustcc.cn/crates.io-index"

参考资料：

Rustup 镜像安装帮助 - 清华大学

Rust Toolchain 反向代理使用帮助 - 中国科学技术大学

国内Rust库文件镜像 - rustcc

在中国大陆cargo命令速度很慢怎么办?

如遇到 invalid UTF-8 的问题请去掉文中中文注释

建议不要用Windows默认的记事本编辑

在 WSL 中学习 Rust FFI

博主最近从新学习 Rust FFI 的使用，但是手头上没有可用的 Linux 环境（Windows 编译c太麻烦了），于是就尝试着使用 WSL来搭建 Rust 环境和简易的 c 编译环境，并记录下中间遇到的一些坑。感谢 Unsafe Rust 群群友 @框框对本文的首发赞助！感谢 Rust 深水群 @栗子的 gcc 指导！

阅读须知

阅读本文，你可以知道：

一些配置 WSL 全局变量的技巧
快速配置 Rust 编译运行环境
简单的 gcc 编译技巧

但是，本文不涉及：

如何安装 WSL?
如何解决 WSL 中文乱码问题? 顺带一提的是，博主通过 VS Code 使用 WSL，因为 Win 10 已经配置成 UTF-8 编码，所以并没有出现乱码问题
Rustup 国内镜像有哪些?
cargo 详细使用教程
甚至不会讲 Rust FFI 是什么

WSL Rust 环境搭建

由于 WSL 是新装的，没有 Rust 和 gcc/g++ 环境，因此需要安装：

sudo apt install gcc -y

# 官方脚本
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

但是由于在国内访问 Rust 官方网站会很慢，因此设置镜像到 Windows 环境变量中：

RUSTUP_DIST_SERVER=https://mirrors.ustc.edu.cn/rust-static
RUSTUP_UPDATE_ROOT=https://mirrors.ustc.edu.cn/rust-static/rustup

然后，使用 WSLENV环境变量将上述变量共享到 WSL 中：

WSLENV=RUSTUP_DIST_SERVER:RUSTUP_UPDATE_ROOT

然后重启 WSL 终端，重新执行 Rust 一键脚本。

以下两个项目均来自《Rust编程之道》一书，源代码仓库在这里

Rust 调用 C/C++

Rust 调用 C/C++ 代码可以使用 cc crate 配合 build.rs 预先编译好 C/C++ 的程序提供给 Rust 调用。

首先，创建一个 binary 项目：

cargo new --bin ffi_learn

项目目录结构如下：

cpp_src
    |-- sorting.h
    |-- sorting.cpp
src
    |-- main.rs
Cargo.toml
build.rs

然后编写 sorting.h 和 sorting.cpp:

// sorting.h
#ifndef __SORTING_H__
#define __SORTING_H__ "sorting.h"
#include <iostream>
#include <functional>
#include <algorithm>
#ifdef __cplusplus
extern "C" {
#endif

void interop_sort(int[], size_t);

#ifdef __cplusplus
}
#endif
#endif

// sorting.cpp
#include "sorting.h"

void interop_sort(int numbers[], size_t size) {
    int* start = &numbers[0];
    int* end = &numbers[0] + size;

    std::sort(start, end, [](int x, int y) { return x > y; });
}

然后给 Cargo.toml 的 [build-dependecies] 加上 cc crate 依赖：

# Cargo.toml
# 其他配置

[build-dependencies]
cc = "1"

接着，我们通过 cc 调用对应平台的c/c++编译器，因为我们这个项目是 WSL，所以和调用我们刚安装的 gcc:

// build.rs
// Rust 2018 不需要 extern crate 语句

fn main() {
    cc::Build::new()
        .cpp(true)
        .warnings(true)
        .flag("-Wall")
        .flag("-std=c++14")
        .flag("-c")
        .file("cpp_src/sorting.cpp")
        .compile("sorting");    // sorting.so
}

接着，我们在 Rust 主程序中，通过 extern 块引入sorting.cpp中的interop_sort函数，并调用它:

// main.rs
#[link(name = "sorting", kind = "static")]
extern "C" {
    fn interop_sort(arr: *mut i32, n: u32);
}

pub fn sort_from_cpp(arr: &mut [i32]) {
    unsafe {
        // 传入必然有效的数组引用，并通过传入数组的长度来保证不会出现越界访问，从而保证函数内存安全
        interop_sort(arr as *mut [i32] as *mut i32, arr.len() as u32);
    }
}

fn main() {
    let mut my_arr: [i32; 10] = [10, 42, -9, 12, 8, 25, 7, 13, 55, -1];
    println!("Before sorting...");
    println!("{:?}\n", my_arr);

    sort_from_cpp(&mut my_arr);

    println!("After sorting...");
    println!("{:?}\n", my_arr);
}

然后执行调用：

$ cargo run
   Compiling ffi_learning v0.1.0 (/mnt/c/Users/huangjj27/Documents/codes/ffi_learning)
warning: `extern` block uses type `[i32]`, which is not FFI-safe
 --> src/main.rs:3:26
  |
3 |     fn interop_sort(arr: &[i32], n: u32);
  |                          ^^^^^^ not FFI-safe
  |
  = note: `#[warn(improper_ctypes)]` on by default
  = help: consider using a raw pointer instead
  = note: slices have no C equivalent

    Finished dev [unoptimized + debuginfo] target(s) in 4.71s
     Running `target/debug/ffi_learn`
Before sorting...
[10, 42, -9, 12, 8, 25, 7, 13, 55, -1]

After sorting...
[55, 42, 25, 13, 12, 10, 8, 7, -1, -9]

我们看到，该函数提示我们 C 中并没有等价于 Rust slice 的类型，原因在于如果我们传递 slice，那么在 C/C++ 中就很容易访问超过数组长度的内存，造成内存不安全问题。但是，我们在 Rust 调用的时候，通过同时传入数组 arr 的长度 arr.len(), 来保证函数不会访问未经授权的内存。不过在实践中，应该划分模块，只允许确认过内存安全的 safe Rust 功能跨越模块调用。

在 C/C++ 中调用 Rust

接下来我们反过来互操作。项目结构如下：

c_src
    |-- main.c
src
    |-- lib.rs
    |-- callrust.h
Cargo.toml
makefile

然后配置 Rust 生成两种库——静态库（staticlib）和c动态库（cdylib）：

# Cargo.toml
# ...

[lib]
name = "callrust"   # 链接库名字
crate-type = ["staticlib", "cdylib"]

然后添加我们的 Rust 函数：

#![allow(unused)]
fn main() {
// lib.rs

// `#[no_mangle]` 关闭混淆功能以让 C 程序找到调用的函数
// `extern` 默认导出为 C ABI
#[no_mangle]
pub extern fn print_hello_from_rust() {
    println!("Hello from rust");
}
}

当然，为了给 C 调用我们还需要编写一个头文件：

// callrust.h
void print_hello_from_rust();

在我们的 main.c 中库并调用：

// main.c
#include "callrust.h"
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main(void) {
    print_hello_from_rust();
}

编写 makefile，先调度cargo 编译出我们需要的 Rust 库（动态或链接），然后再运行：

GCC_BIN ?= $(shell which gcc)
CARGO_BIN ?= $(shell which cargo)

# 动态链接 libcallrust.so
share: clean cargo
	mkdir cbin
	$(GCC_BIN) -o ./cbin/main ./c_src/main.c -I./src -L./target/debug -lcallrust

	# 注意动态链接再运行时也需要再次指定 `.so` 文件所在目录，否则会报错找不到！
	LD_LIBRARY_PATH=./target/debug ./cbin/main

# 静态链接 libcallrust.a
static: clean cargo
	mkdir cbin

	# libcallrust.a 缺少了一些pthread, dl类函数，需要链接进来
	$(GCC_BIN) -o ./cbin/main ./c_src/main.c -I./src ./target/debug/libcallrust.a -lpthread -ldl
	./cbin/main

clean:
	$(CARGO_BIN) clean
	rm -rf ./cbin

cargo:
	$(CARGO_BIN) build

小结

本文通过给出两个简单的示例来展示 Rust 通过 FFI 功能与 C/C++ 生态进行交互的能力, 并且指出几个在实践过程中容易浪费时间的坑：

WSL的环境变量不生效 -> 使用 WSLENV 变量从 Windows 引入使用。
make share 的时候提示 libcallrust.so 找不到 -> 需要在运行时指定 LD_LIBRARY_PATH 变量，引入我们编译的 libcallrust.so 路径。
make static的时候遇到了pthread_* dy*系列函数未定义问题 -> 通过动态链接系统库来支持运行。

WASM(Web Assembly)尽管是为了提高网页中性能敏感模块表现而提出的字节码标准, 但是WASM却不仅能用在浏览器(broswer)中, 也可以用在其他环境中. 在这些环境中, 我们则需要支持WASI(WebAssembly System Interface, WASM系统接口)的runtime来执行我们编译运行的wasm模块.

WASI探索（一） -- WASI简介与Wasmtime配置

什么是WASI?

WASI¹是一个新的API体系, 由Wasmtime项目设计, 目的是为WASM设计一套引擎无关(engine-indepent), 面向非Web系统(non-Web system-oriented)的API标准. 目前, WASI核心API(WASI Core)在做覆盖文件, 网络等等模块的API, 但这些实现都是刚刚开始实现, 离实用还是有很长路要走.

关于WASM runtime

在了解了WASI之后, 博主最后选定两个WASM运行时进行探索: WASMER 与 Wasmtime. 这两款运行时都号称开始支持了WASI标准, 但博主使用rust-wasi-tutorial对两款运行时进行试验后, 发现WASMER对于文件读取还是有些问题, 而Wasmtime则是通过了规格测试(基于specs testsuite), 因此本文接下来着重于Wasmtime的配置介绍.

Wasmtime与rust环境配置

由于目前Wasmtime与WASMER均只支持Unix-like环境, 接下来楼主将演示如何在WSL(Ubuntu 18.04)下配置Wasmtime. 而在目前比较方便生成wasm的编程语言中, 博主选择使用自带wasi目标的rust编程语言, 可以"零代价"配置wasm相关工具链.

配置rust

下载并安装rustup: curl https://sh.rustup.rs -sSf | sh, 安装时使用默认 stable-x86_64-unknown-linux-gnu工具链, 后面我们还会自行添加用于编译wasm的nightly工具链.
为cargo配置ustc反代, 提高crates(rust库)下载速度²
安装rustfmt: rustup component add rustfmt --toolchain stable-x86_64-unknown-linux-gnu. Wasmtime的test脚本需要用到该组件.
安装rust nightly工具链: rustup toolchain add nightly-x86_64-unknown-linux-gnu. 当前rust的WASI目标还在开发中, 尚未稳定³.
安装rust WASI目标: rustup target add wasm32-unknown-wasi³.

配置Wasmtime

安装cmake与clang: sudo apt install cmake clang, 用于编译Wasmtime. Wasmtime目前尚未有正式发布版本, 故需要我们自行编译.
拷贝Wasmtime源码: git clone --recursive git@github.com:CraneStation/wasmtime.git ~/wasmtime.
切换到Wasm源码目录: cd ~/wasmtime
执行测试脚本: ./scripts/test-all.sh. 当脚本执行完毕并通过测试后, 说明wasmtime已经正常编译并且能在当前WSL环境下正常工作, 可以使用生成的wasmtime可执行文件.
将生成的wasmtime拷贝到/usr/bin目录中: cp ~/wasmtime/target/release/wasmtime /usr/bin, 以便在整个WSL环境中任意目录执行wasmtime. wasmtime是个单文件(stand alone)运行时.
执行wasmtime --help命令, 确认wasmtime成功安装.

试验

GitHub上面已经有了比较简单的试验, 大家按照上面的说明去试验即可. 下一篇文章, 博主将会把猜数字编译成WASI目标并执行, 同时会尝试把一些常用的库尝试编译, 来探究当前社区对WASI支持的程度.

WASI概要

rust crates 镜像使用帮助 - 中国科学技术大学

截至2020年1月19日，WASI目标已经稳定并重命名为wasm32-wasi

WASI探索（二） -- WASI版猜数字

猜数字作为入门Rust时第一次编写并具有实际功能的程序，适合让读者快速掌握rust的基本概念。同时，为了让程序更加有趣，博主在原本的猜数字程序上添加了日志和从运行时参数传递游戏难度的功能。此外，由于博主偏好改变，本文还会涉及到另外一款WASI运行时Wasmer，以及他们为了丰富WASI生态而推出的wasm包管理器wapm。

阅读须知

学习外部资料更有助于读者了解相关生态，因此本文将不赘述：

而阅读本文，你将了解：

如何用日志debug的一些原则
一个简单的配置文件的设计
读者对Wasmer的一些浅薄看法

原版猜数字

我们从官方书拷贝了一份猜数字程序：

// main.rs
use std::io;
use std::cmp::Ordering;
use rand::Rng;

fn main() {
    println!("Guess the number!");

    let secret_number = rand::thread_rng().gen_range(1, 101);

    loop {
        println!("Please input your guess.");

        let mut guess = String::new();

        io::stdin().read_line(&mut guess)
            .expect("Failed to read line");

        let guess: u32 = match guess.trim().parse() {
            Ok(num) => num,
            Err(_) => continue,
        };

        println!("You guessed: {}", guess);

        match guess.cmp(&secret_number) {
            Ordering::Less => println!("Too small!"),
            Ordering::Greater => println!("Too big!"),
            Ordering::Equal => {
                println!("You win!");
                break;
            }
        }
    }
}

# Cargo.toml
[package]
name = "guessing_game"
version = "0.1.0"
authors = ["Your Name <you@example.com>"]
edition = "2018"

[dependencies]
rand = "0.3.14"

一次游戏只猜一个数

我们可以看到，这个程序每次运行，只能猜一个数字，如果要继续玩就只能重新启动。但是博主想让这个游戏，能在一次运行时可以生成不同难度关卡，因此首先我们将“猜一个数字”逻辑抽取成可复用函数

#![allow(unused)]
fn main() {
// main.rs
fn guess_a_number() {
    println!("Guess the number!");

    let secret_number = rand::thread_rng().gen_range(1, 101);

    loop {
        println!("Please input your guess.");

        let mut guess_str = String::new();

        io::stdin().read_line(&mut guess_str)
            .expect("Failed to read line");

        let guess: u32 = match guess_str.trim().parse() {
            Ok(num) => num,
            Err(_) => continue,
        };

        println!("You guessed: {}", guess);

        match guess.cmp(&secret_number) {
            Ordering::Less => println!("Too small!"),
            Ordering::Greater => println!("Too big!"),
            Ordering::Equal => {
                println!("You win!");
                break;
            }
        }
    }
}
}

再将配置文件修改一下：

# guess_wasi/Cargo.toml
[package]
name = "guess_wasi"
version = "0.1.0"
authors = ["huangjj27 <huangjj.27@qq.com>"]
edition = "2018"

[dependencies]
rand = "0.7"

此外，猜数字游戏的难度取决于随机生成数字的范围, 为了生成不同的难度关卡，我们需要guess_a_number接受一组控制生成数字范围的参数：

#![allow(unused)]
fn main() {
// main.rs
/// 生成熟悉范围的下界（lower bound，lb)与上界（higher bound，hb）在主函数中读取配置文件得到
fn guess_a_number((lb, hb): (u32, u32)) {
    println!("Guess the number!");

    let secret_number = rand::thread_rng().gen_range(lb, hb + 1);

    // ...
}
}

这里在传入参数时，直接解构了元组, 这样后面就可以直接使用传入的上界与下界来控制生成数范围

然后，博主发现，原版猜数字如果解析数字错误的话会直接跳过，博主觉得这里应该至少提醒一下用户输入错误了：

#![allow(unused)]
fn main() {
// main.rs
fn guess_a_number((lb, hb): (u32, u32)) {
    // ...
        let guess: u32 = match guess_str.trim().parse() {
            Ok(num) => num,
            Err(_) => {
                println!("Input not a number! please input a number");
                continue;
            },
        };
    // ...
}
}

加上log追踪生成的数据情况

使用log去追踪数据与可能产生bug的代码有以下好处：

了解运行时所关注的数据情况，方便定位bug
清晰地知道实际运行流程是否如期望那样执行
即便使用release版目标，仍然可以获得需要的分析信息
区分产生信息的层级，以便将精力集中在优先需要处理的信息中

回到猜数字游戏上，博主想要知道每一次游戏中知道生成的secret_number是多少，并且根据运行时输入的日志层级的参数决定是否显示这个数字，需求相对简单，因此使用rust生态中比较常用的log crate与env_log crate。在Cargo.toml中加入两个新依赖：

# guess_wasi/Cargo.toml

# ...

[dependencies]
rand = "0.7"

# 总是使用最新的log与env_log
log = "*"
env_logger = "*"

加入追踪日志代码：

// main.rs
use log::{trace, debug};

fn main() {
    // 别忘了初始化日志生成器， 才能获取日志！
    env_log::init();
    guess_a_number((1, 100));
}

fn guess_a_number((lb, hb): (u32, u32)) {
    println!("Guess the number!");

    let secret_number = rand::thread_rng().gen_range(lb, hb + 1);
    trace!("secret number: {}", secret);

    loop {
        println!("Please input your guess.");

        let mut guess_str = String::new();
        io::stdin().read_line(&mut guess_str)
            .expect("Failed to read line");
        debug!("scaned string: {:?}", guess_str);

        // ...
    }
}

向高难度挑战！

现在我们来到最后了一个需求：通过运行时参数来给每次游戏输入多个游戏难度，这个难度由随机数生成的范围决定-- 随机数生成的范围越大，一次猜中这个数的概率就越小。为方便地写出输入参数的命令，我们需要引入structopt库（crate）, 最后获得类似--levels=10 100 1000这样的参数输入方式, 参数中每个数字表示每次生成随机数的生成范围上界。

配置文件追加：

# guess_wasi/Cargo.toml

# ...

[dependencies]
rand = "0.7"

# 总是使用最新的log与env_log
log = "*"
env_logger = "*"

structopt = "*"

编写参数代码。

// main.rs

// ...
use structopt::StructOpt;

// 定义参数只需要把他们的名字和类型写在一个参数结构体中即可！
#[derive(StructOpt)]
#[structopt(name="guess_wasi")]
struct Opt {
    #[structopt(long="levels")]
    levels: Vec<u32>,
}

fn main() {
    env_logger::init();

    // 获取并访问levels参数, 只需要访问参数结构体的对应成员即可， 细节处理可以方便地交给库执行！
    let opt = Opt::from_args();
    for &lv in &opt.levels {
        println!("given number range 0~{}", lv);
        guess_a_number((0, lv));
    }
}

完整代码

[package]
name = "guess_wasi"
version = "0.1.0"
authors = ["huangjj27 <huangjj.27@qq.com>"]
edition = "2018"

[dependencies]
rand = "0.7"

# 总是使用最新的log与env_log
log = "*"
env_logger = "*"

structopt = "*"

// guess_wasi/main.rs
use std::io;
use std::cmp::Ordering;
use rand::Rng;
use log::{debug, trace};

use structopt::StructOpt;

// 定义参数只需要把他们的名字和类型写在一个参数结构体中即可！
#[derive(StructOpt)]
#[structopt(name="guess_wasi")]
struct Opt {
    #[structopt(long="levels")]
    levels: Vec<u32>,
}

fn main() {
    env_logger::init();

    // 获取并访问levels参数, 只需要访问参数结构体的对应成员即可， 细节处理可以方便地交给库执行！
    let opt = Opt::from_args();
    for &lv in &opt.levels {
        println!("given number range 0~{}", lv);
        guess_a_number((0, lv));
    }
}

// 一场游戏有多个难度，我们每个难度只猜一个数字，然后变难
fn guess_a_number((lb, hb): (u32, u32)) {
    let secret = rand::thread_rng().gen_range(lb, hb + 1);
    trace!("secret number: {}", secret);

    loop {
        println!("Please input your guess.");

        let mut guess_str = String::new();
        io::stdin().read_line(&mut guess_str)
            .expect("Failed to read line");
        debug!("scaned string: {:?}", guess_str);

        let guess: u32 = match guess_str.trim().parse() {
            Ok(num) => num,
            Err(_) => {
                println!("Input not a number! please input a number");
                continue;
            },
        };

        println!("You guessed: {}", guess);

        match guess.cmp(&secret) {
            Ordering::Less => println!("too small!"),
            Ordering::Greater => println!("too big!"),
            Ordering::Equal => {
                println!("You get it!");
                break;
            }
        }
    }
}

读到这里，读者可以发现前文根本没涉及到WASI，甚至没有涉及WASM。这因为WASI作为应用与运行时交互的接口，被rust编译器封装成为编译目标，读者只需要编译到对应目标即可让自己的程序在对应平台上运行. 这是Rust编程语言现代化与工程学的体现：一般应用研发工程师可以通过使用已经适配所需平台的底层库(这些底层库通常已经针对所有支持平台做了最优化适配)，就能让自己的应用支持对应的平台而无需重新编写针对某平台的特化版本源码！

是时候编译成WASI目标了

我们还需要添加对应的编译目标：

rustup target add wasm32-wasi

编译到wasm32-wasi目标上：

$ cargo build --target=wasm32-wasi --release
   Compiling proc-macro2 v1.0.18
   Compiling version_check v0.9.2
   Compiling unicode-xid v0.2.0
   Compiling syn v1.0.30
   Compiling cfg-if v0.1.10
   Compiling memchr v2.3.3
   Compiling getrandom v0.1.14
   Compiling wasi v0.9.0+wasi-snapshot-preview1
   Compiling lazy_static v1.4.0
   Compiling bitflags v1.2.1
   Compiling atty v0.2.14
   Compiling unicode-width v0.1.7
   Compiling unicode-segmentation v1.6.0
   Compiling log v0.4.8
   Compiling quick-error v1.2.3
   Compiling ansi_term v0.11.0
   Compiling ppv-lite86 v0.2.8
   Compiling regex-syntax v0.6.18
   Compiling strsim v0.8.0
   Compiling vec_map v0.8.2
   Compiling termcolor v1.1.0
   Compiling thread_local v1.0.1
   Compiling textwrap v0.11.0
   Compiling proc-macro-error-attr v1.0.2
   Compiling proc-macro-error v1.0.2
   Compiling humantime v1.3.0
   Compiling heck v0.3.1
   Compiling quote v1.0.7
   Compiling rand_core v0.5.1
   Compiling clap v2.33.1
   Compiling regex v1.3.9
   Compiling rand_chacha v0.2.2
   Compiling env_logger v0.7.1
   Compiling syn-mid v0.5.0
   Compiling rand v0.7.3
   Compiling structopt-derive v0.4.7
   Compiling structopt v0.3.14
   Compiling guess_wasi v0.1.0 (C:\Users\huangjj27\Documents\codes\huangjj27.github.io\code\guess_wasi)
    Finished release [optimized] target(s) in 4m 58s

现在，我们来运行一下程序吧：

$ wasmer --version
wasmer 0.13.1
$ wasmer run .\target\wasm32-wasi\release\guess.wasm --env RUST_LOG=trace -- --levels 10 100 1000
given number range 0~10
[2020-06-09T14:55:58Z TRACE guess] secret number: 10
Please input your guess.
5
[2020-06-09T14:56:02Z DEBUG guess] scaned string: "5\r\n"
You guessed: 5
too small!
Please input your guess.
8
[2020-06-09T14:56:04Z DEBUG guess] scaned string: "8\r\n"
You guessed: 8
too small!
Please input your guess.
9
[2020-06-09T14:56:07Z DEBUG guess] scaned string: "9\r\n"
You guessed: 9
too small!
Please input your guess.
10
[2020-06-09T14:56:09Z DEBUG guess] scaned string: "10\r\n"
You guessed: 10
You get it!
given number range 0~100
[2020-06-09T14:56:09Z TRACE guess] secret number: 60
Please input your guess.
60
[2020-06-09T14:56:25Z DEBUG guess] scaned string: "60\r\n"
You guessed: 60
You get it!
given number range 0~1000
[2020-06-09T14:56:25Z TRACE guess] secret number: 715
Please input your guess.
300
[2020-06-09T14:56:32Z DEBUG guess] scaned string: "300\r\n"
You guessed: 300
too small!
Please input your guess.
720
[2020-06-09T14:56:38Z DEBUG guess] scaned string: "720\r\n"
You guessed: 720
too big!
Please input your guess.
716
[2020-06-09T14:56:41Z DEBUG guess] scaned string: "716\r\n"
You guessed: 716
too big!
Please input your guess.
714
[2020-06-09T14:56:46Z DEBUG guess] scaned string: "714\r\n"
You guessed: 714
too small!
Please input your guess.
715
[2020-06-09T14:56:48Z DEBUG guess] scaned string: "715\r\n"
You guessed: 715
You get it!
$

调试后，确认我们的程序可以正常执行了，去掉--env RUST_LOG=trace参数，享受自己制作的这个小游戏吧！

Wasmer与Wapm

Wasmer可以是说在WASI生态中响应速度仅次于Mozilla的组织，他们号称打造了一款可以让代码“一次构建，处处运行”（Build Once, Run Anywhere.)的运行时环境，该环境可以运行ECMAScripten标准与 WASI标准的wasm栈机码。并且方便为wasm代码分发，该组织开发了类似于nodejs生态中npm的包管理工具wapm，这样用户就可以很轻松地发布自己的程序，以及利用他人的程序了--这促进了WASM生态的发展，同时作为生态底层的领导者，Wasmer也将拥有更多发言权。

作为边缘人士（稍微知道WASM生态但没很深入了解），博主看到这项目背后的布局很像上世纪Sun公司的Java和JVM（尽管WASM并不是Wasmer的发明，但这样反而不必为WASM这样可以作为主流编程语言编译目标工具投入过多精力宣传，可以集中精力去优化wasmer与wapm；同时因为wasmer是使用MIT协议授权，不会产生类似OracleJDK专利权所属的问题，相信随着生态的进一步发展，在虚拟机运行时领域会逐步替代JVM成为主流，届时将解放程序员更多生产力 -- 不必要求掌握Java而是通过自己熟悉的编程语言（c/c++/rust/python/...)通过统一的标准相互调用（进一步微型化的微服务）。

而这个在服务器/PC桌面应用占主导地位的标准，就是WASI。

初等数论自我探索

本系列文章以解决哥德巴赫猜想为目的（证明/证伪），把思路限制在初等数论（个人水平有限，理解不了更高级的工具），进行思考与尝试，本意是打发自己零散的通勤时间，走到哪算到哪。

该系列文章的最初设想是有一天突然就想到，关于一个偶数 $ 2n (n \in Z^+) $的素数相加的分拆，一定是关于整数 $ n $ 对称的，即若 $ 2n = p_1 + p_2 $，其中 $ p_1 $, $ p_2 $ 为质数（$p_1 \neq p_2 $），那么： \[ \exists d \in Z^+, \begin{cases} p_1 = n - d \\ p_2 = n + d \end{cases} \]

那么这个 $ d $ 和 $ n $ 有什么关系呢？适逢当时被科普了黎曼猜想, 得知黎曼 $ \Zeta $ 函数的非平凡零点很可能全部都位于直线 $ Re(z) = {1 \over 2} $ 上，那么会不会，最小的 $ d $ 也会在 $ n \cdot { 1 \over 2} $ 的边界内找得到呢？

于是提出了以下猜想命题： \[ \tag{0} \label{0} \forall n \in Z^+, n \gt M, \exists d \in Z^+, d \le { n \over 2 }, Prime(n - d) \land Prime(n + d) \]

其中 $ M $ 为常数，表示命题成立在某个整数以上的整数范围成立。也就是，证明有穷个整数之后的整数都满足性质$ \ref{0} $，然后再逐个验证之前的整数满足该性质，就可以得出一个比偶数哥德巴赫猜想更充分的命题，从而直接可以推导出偶数哥德巴赫定理。

若质数p不能整除偶数2n，则p不整除2n-p

命题形式化描述

\[\label{1} \tag{1} \forall p \in Primes, p \lt 2n(n \in Z^+), p \nmid 2n \Rightarrow p \nmid 2n - p \]

一般化命题与反证法 1

我们可以抽出一个更一般的命题：对任意正整数 $a, b (a \lt b)$，若 $ a \nmid b$，则 $ a \nmid b - a $: \[\label{1.0} \tag{1.0} \forall a, b \in Z^+ (a \lt b), a \nmid b \Rightarrow a \mid b - a \]

反证法

假设原结论不成立，即 $ a \mid b - a $ 成立，则：

$ \because a \mid b - a, a \mid a $

$ \therefore a \mid (b - a) + a $ （整除的线性性质），即 $ a \mid b $,

这与假设 $ a \nmid b $ 矛盾！故假设不成立，原结论成立，即 $ a\mid b - a $,

故命题 $ \ref{1.0} $ 成立。

代入条件

令 $ a := p, b = 2n $, 则显然：

\[ p \in Primes, p \lt 2n \Rightarrow p \nmid 2n \Rightarrow p \nmid 2n - p \]

即命题 $ \ref{1} $ 得证。

(以下内容为作者之前思考过的另外一个比较迂回的证明方法，为后续叙述的引理）

一整数若不同时整除互质两数，则不能整除后两数之差

形式化描述

\[ \label{1.1} \tag{1.1} \forall x \in Z^+ \land x > 1, a \in Z^+ \land a > 1, b \in Z^+ \land b > 1; \quad (a, b) = 1, x|a \lor x|b \Rightarrow x \nmid a-b \]

证明

不妨设 $ a \gt b $。易知$x|a$与$x|b$不同时成立, 否则$(a, b) \ge x$, 与 $(a, b) = 1$ 矛盾. 分类讨论:

$x|a, , x \nmid b$

$ \because x|a $

$ \therefore \exists m \in Z^+, mx=a. $

假设 $ x|a-b $, 即 $ \exists k \in Z^+, kx=a-b \Leftrightarrow b = a-kx = (m-k)x. $

若 $ m = k $, 则 $ b = 0 $, 与 $ b > 1 $ 矛盾;

若 $ m \neq k $, 则 $ \exists (m-k) \in Z, b = (m-k)x \Leftrightarrow x|b $, 与假设 $ x \nmid b $ 矛盾!

故假设 $ x|a-b $ 不成立, $ x \nmid a-b. $
$x \nmid a, , x|b$. 同理可得: 若$ x|a-b$ , 则 $ a = b + kx = (m+k)x \Leftrightarrow x|a $, 与 $x \nmid a$ 矛盾! 故 $x \nmid a-b $.

代入条件

令 $ x := p, a := 2n, b := p $，显然有$ p \mid p $。故，当 $p \nmid 2n $时， $ p \nmid 2n - p $，即命题 $ \ref{1} $ 得证。

感谢中山大学数学专业的倪秉业师弟指出这个更简洁的证明方式！

整数和它两倍（一倍半）之间的合数，可以整除整数的阶乘

形式化描述

\[ \label{2.1} \tag{2.1} \forall m \in Z^+, m \gt 8, n \in Z^+, m \lt n \lt 2m; \quad n \not \in Primes \Leftrightarrow n \mid m! \]

证明

充分性

\[ \label{2.1.1} \tag{2.1.1} n \not \in Primes \Rightarrow n \mid m! \]

因为 $ n $ 为合数，将其分为完全平方数和不完全平方数两种情况证明。

不完全平方数

不妨设 $ n = ab (a \gt b \ge 2, (a, b) = 1) $，则 $b \lt a \lt m $，证明如下：

若 $ a \ge m $，

则 $n = ab \ge 2a \ge 2m \Leftrightarrow n \ge 2m $，

这与 $ n \lt 2m $ 矛盾！

故假设不成立，故 $2 \le b \lt a \lt m \Rightarrow a \mid m!, b \mid m! $。

又 $ (a, b) = 1 \Rightarrow [a, b] = ab = n $

因此：$ a \mid m!, b \mid m \Rightarrow [a, b] \mid m! \Leftrightarrow n \mid m! $。

完全平方数

不妨设 $ n = k^2 $，则 $2 \lt k \lt 2k \lt m $，证明如下：

若 $ 2k \ge m $，则 $ k \ge { m \over 2 } $，

则 $n = k^2 \ge { m^2 \over 4 } \ge { 8 / 4 } \cdot m = 2m \Leftrightarrow n \ge 2m $，

这与 $ n \lt 2m $ 矛盾！

故假设不成立，故 $ 2 \le k \lt 2k \lt m \Rightarrow 2k^2 \mid m! $。

因此：$ 2k^2 \mid m! \Leftrightarrow 2n | m! \Rightarrow n \mid m! $。

综上，命题 $ \ref{2.1.1} $ 得证。

必要性

\[ \label{2.1.2} \tag{2.1.2} n \mid m! \Rightarrow n \not \in Primes \]

反证：假设 $n \in Primes $，则：

$ \because n > m, n \in Primes, $

$ \therefore n \nmid 2, \space n \nmid 3, \space n \nmid 4, \space \dots, \space n \mid m \Rightarrow n \nmid m!， $

这与条件 $ n \mid m! $ 矛盾！故假设不成立，命题 $ \ref{2.1.2} $ 得证。

综上，命题 $ \ref{2.1} $ 得证。

更强的结论

显然对 $ \forall n \in (m, 3/2m) \Rightarrow n \in (m, 2n) $，故： \[ \label{2.2} \tag{2.2} \forall m \in Z^+, m \gt 8, n \in Z^+, m \lt n \lt { 3m \over 2 }; \quad n \not \in Primes \Leftrightarrow n \mid m! \]

用初等数论探索哥德巴赫猜想

在探索哥德巴赫猜想在初等数论框架内证明方式, 并由此发现一些显而易见的有趣结论: 若一个偶数2n能够拆分为两个奇素数的和的形式, 并且如果两个奇素数不相等, 那么这两个素数中较小的一个p(易知$ p \lt n $)必然不能整除n.

哥德巴赫猜想

关于历史研究历程一类资料, 请参考wiki.

本文将哥德巴赫猜想简单地描述为:

给定任意整数$n(n > 1)$, 以及不超过n的所有素数¹的集合$ P = \{ p \mid Prime(p) \land p \lt n \} $. 设$p$为集合$ P $中的一个元素, 猜想$p$对应的整数$2n-p$所组成的集合$2n-P$中, 必然存在素数元素.

引理

(一) P中存在不整除n的元素

引理1: \[ \label{1.1} \tag{1.1} \exists p \in P, p \nmid n \]

证明(反证法):

假设命题$ \ref{1.1} $ 的反命题: \[\label{1.2} \tag{1.2} \forall p \in P, p \mid n \Leftrightarrow \forall p \in P, \exists m \in Z, m \neq 0 \land mp = n \] 成立, 由伯特兰-切比雪夫定理(Bertrand's postulate)可知: \[ \exists p_0, {n \over 2} \lt p_0 \lt n \]

由假设$ \ref{1.2} $ 可得: \[{mp_0 \over 2} \lt p_0 \Rightarrow m \lt 2\].

又$m \in Z$, $p_0 \gt 0, n \gt 0 \Rightarrow m = {n \over p_0} \gt 0$, 所以$m = 1$, 即$mp_0 = p_0 = n$, 这与$p_0 \lt n$ 矛盾!

所以命题$ \ref{1.2} $不成立. 故命题$ \ref{1.1} $成立.

(二) 给定正整数 $x$ 若整除互质数对$ a, b $之一，则 $x$ 不整除 $a-b$

\[ \label{2} \tag{2} (a, b) = 1, x \gt 1, a \gt 1, b \gt 1, x|a \lor x|b \Rightarrow x \nmid a-b \]

证明:

易知$x|a$与$x|b$不同时成立, 否则$(a, b) \ge x$, 与 $(a, b) = 1$ 矛盾. 分类讨论:

$x|a, , x \nmid b$

$ \because x|a $

$ \therefore \exists m \ge 1, m \in Z, mx=a. $

假设 $ x|a-b $, 即 $ \exists k \in Z, kx=a-b \Leftrightarrow b = a-kx = (m-k)x. $

若 $ m = k $, 则 $ b = 0 $, 与 $ b > 1 $ 矛盾;

若 $ m \neq k $, 则 $ \exists (m-k) \in Z, b = (m-k)x \Leftrightarrow x|b $, 与假设 $ x \nmid b $ 矛盾!

故假设 $ x|a-b $ 不成立, $ x \nmid a-b. $
$x \nmid a, , x|b$. 同理可得: 若$ x|a-b$ , 则 $ a = b + kx = (m+k)x \Leftrightarrow x|a $, 与 $x \nmid a$ 矛盾! 故 $x \nmid a-b $.

探索哥德巴赫猜想

分类讨论:

若n为素数, 显然 $ 2n-n = n $ 亦为素数, 哥德巴赫猜想成立. ¹
若n为合数, 则 $ n \ge 4 $. 由引理(一), 将集合P以能否整除n划分为以下子集: $ S = \lbrace s \mid s|n \rbrace, T = \lbrace t \mid t \nmid n \rbrace$

容易发现以下结论: $ \forall s \in S, \because s|n, s|s, \therefore s|2n-s $, 即若一个素数是n的素因子, 那么对应的整数 $ 2n-s $ 为合数. 故符合哥德巴赫猜想的数对 $ p $与 $ 2n-p $必然满足 $ p \nmid n $(封面结论)

到这里, 我们可以得到一个哥德巴赫猜想的等价命题:

对给定合数$n$, 及小于$n$且不整除$n$的素数集合$ T = \lbrace t \mid Prime(t) \land t \lt n \land t \nmid n \rbrace $, 在集合$T$对应的整数集$2n-T = \lbrace 2n - t \mid Prime(t) \land t \lt n \land t \nmid n \rbrace $中是否存在素数

进一步探究

推论一

\[ \label{3} \tag{3} \forall s \in S, t \in T, s \nmid 2n-t \] 而由引理(二)可得:

对于任意前述s, t, 有:

$ Prime(s), Prime(t) \Rightarrow s \nmid t $
$ s|n \Rightarrow s|2n $

故: $ \forall s \in S, t \in T, s \nmid 2n-t $ 也就是, 至少集合 $ 2n-T $ 的元素不会被 $ S $ 中的元素整除，命题 $ \ref{3} $ 证毕。

推论二

对于$T$的子集 $ T_{\gt {n \over 2}} = T_1 = \lbrace t| t \in T, t \gt {n \over 2} \rbrace $, 具有以下性质:

\[ \label{4} \tag{4} \forall t_1, t_2 \in T_1, t_1 \nmid 2n-t_2 \]

证明如下:

假设 $ \exists t_1, t_2, t_1 \mid 2n-t_2 $, 即 $ \exists m \in Z^+, mt_1 = 2n - t_2 $.

$ \because t_1, t_2为奇数, 2n为偶数 $ $ \therefore m为奇数. $

分类讨论:

当 $ m = 1 $ 时, t_1 + t_2 = 2n.

$ \because t_1 \neq t_2, t_1 \lt n, t_2 \lt n, \therefore t_1 + t_2 \lt 2n $, 矛盾!
当 $ m \ge 3 $时:

$ \because t_1 \gt {n \over 2}, t_2 \gt {n \over 2}, \therefore mt_1 + t_2 \gt { mn \over 2 } + { n \over 2 } \ge { 3n \over 2 } + { n \over 2 } = 2n $ , 矛盾!

故假设不成立, 命题 $ \ref{4} $ 证毕.

如无特殊说明，本文中所有集合均为正整数集的子集

在本文中暂且抛去哥德巴赫猜想中对分解出的两个素数不能相等的要求。

黄俊杰

77u/KCs4NikxODgtMTk0OC0xMjYyDQo= · huangjj.27@qq.com · 349373001 · huangjj27 · huangjj27

下载简历pdf · tech-blog: https://huangjj27.github.io · 微信技术公众号: 坏姐姐日常入门Rust

负责数字化营业厅项目下的叫号系统与数据赋能看板项目的功能测试
针对热点性能的接口与流程进行性能测试
辅助运营人员排查与定位营业员反馈的生产问题

Bonus:

编写接口自动化测试用例（Postman），并设定生产环境的每日自动巡检（企业微信 bot）
使用 goose、locus框架编写性能测试用例
制定性能测试需求评估、性能测试报告规范
review 项目代码，并通过项目代码补充对 DES、AES、HTTP设计规范的了解

银行业客户经理智能推荐与客户反馈收集项目 2020.11 - 2021.09

大数据开发工程师: 大数据 EDI 开发

负责子项目的架构优化、详细设计及部分代码实现
使得原本执行需要 40 小时的作业降至平均完成时间 6 小时
通过 GitLab 管理项目源代码，进行问题追踪、代码评审、自动化流水构建、自动化测试执行
负责子项目程序优化，进行 excel 配置自动化转化为数据库工具的开发
负责子项目部分功能的测试，利用了 Python 工具自动化执行测试用例
负责子项目中关键词词频分析相关部分程序的维护

HiveQL 静态代码扫描检查工具 2019.4

大数据开发工程师: 大数据 EDI 开发

自发地将银行客户用于 Hive QL 静态扫描规则的工具 CLI 化改造(基于 Python)
与上下游沟通，将该工具部署至 CI 平台
该工具成功阻止多次高风险代码提交
对相关员工讲演培训

客户个人金融业务管理平台 2018.8 -- 2019.4

大数据开发工程师: 大数据 EDI 开发

基于银行客户内 EDI 框架（基于 Hadoop 与 Hive）进项业务项目开发
基于 Hive 特性与调度流程优化提高已有项目代码效率
组织相关开发经验分享

（下列项目均为业余项目/开源贡献项目）

《Rust 中的异步编程》

Asynchronous Programming in Rust 一书翻译
该书详细地介绍了在 Rust 中异步编程的基础设施 Future trait、Waker类型，为了使 Future 正常工作的 Pin<T> 智能指针与 Unpin trait，以及方便开发而引用的 async/await 语法糖
该书亦给出了示例构建一个简单的执行器，以及实现一个简单的利用异步优化性能的简单 HTTP 服务器

env_logger

在 std 环境下使用比较广泛的 logger
为该库实现了基础的 wasm32-unknown-unknown 目标的支持, 让该库支持浏览器环境
因为内部结构实现的原因（formatter 格式化后记录丢失了 log::Level 信息，writter 直接使用前述记录写入日志），暂时未实现在浏览器环境中的 log 分级。

参考了 Python 程序实现
补足了单元测试用例、集成测试用例

技能

后端开发/web 开发
- 熟悉 Rust-lang，熟悉生命周期约束、所有权系统并对其进行分析
- 熟悉面向对象编程的概念以及SOLID原则
- 熟悉基本的算法与数据结构
- 了解 RESTful API设计
版本管理
- 熟练使用 git/github/gitlab进行代码版本管理
- 具有良好的版本管理意识, 熟悉语义化版本规则
软件测试 -- 有功能测试、单元测试、集成测试、接口测试经验，也熟悉使用 Rust 测试套件
外语 -- 英语（CET6）

huangjj27's Tech blog

TLSSigAPI - 使用 Rust 重写 Tencent Login Service Signature API