Welcome to oosquare’s personal blog

std::any::Any 是 Rust 在运行时进行类型擦除和转换的工具，所有 'static 类型都实现了 Any，因此装箱为 Box<dyn Any> 后可以借助 Any::type_id() 获取 TypeId，还可以通过 dyn Any 的 downcast_*() 等方法再转换回具体类型。 然而问题也出在 dyn Any 的 downcast_*() 方法。这些方法是 dyn Any 的方法，而不是 Any trait 中的方法，所以其他任何 dyn Trait 都不会拥有这些方法，即使有 Trait: Any。另一方面，由于 trait upcasting 直到最近才成为稳定特性，且还没进入 stable 版本，所以依赖语言支持的 trait upcasting 来转换为 dyn Any 对于较早版本的项目并不合适。 因此，本文则通过纯 Rust 语法来扩展 trait object，以实现 Any 的所有功能。这些实现都可以在 better-as-any 找到。 现有解决方案 downcast downcast crate 通过宏来生成代码，直接为指定的 dyn Trait 添加 is()、downcast_*() 方法。这种做法在最终效果上与 dyn Any 完全一样，但是需要使用 impl_downcast!() 宏来实现。我个人则偏好能使用语言特性实现就不使用宏。...

在对 Rust 错误处理的思考和 anyerr一文中，我介绍了 anyerr 这一个错误处理库，其可以携带上下文信息，且储存上下文的数据结构是可定制的。本文则聚焦 anyerr 是如何实现这样的特性的。 上下文的核心特性 基本结构和表示 在设计之前，首先我们要明确需求。什么样的上下文数据结构是我们所需要的？携带上下文是为了能够记录某些变量所保存的值，我们需要记录变量的名称和其中的值。上下文可以有很多种类，但所有的上下文都可以表示为一个键值映射表。 所以以下是我们对一个上下文储存的基本特性的定义： pub trait AbstractContext: Default + Debug + Send + Sync + 'static { type Key; type Value; type Entry: Entry<Key = Self::Key, Value = Self::Value>; type Iter<'a>: Iter<'a, Entry = Self::Entry> where Self: 'a; fn iter(&self) -> Self::Iter<'_>; } 这样的一个 trait 定义仅仅规定了一个上下文的键值对类型和迭代其中元素的方法，却没有插入或者其他查询的方法。这是因为一个上下文不一定需要真的携带有信息，如果不需要上下文，那么一个不带有任何信息的上下文就可以非常好地适用于这种场景，这也是为什么这个 trait 叫做 AbstractContext。anyerr 针对这样的情况有特殊的优化，这些后面再说。 上下文的元素 AbstractContext::Entry 规定了上下文中每一个元素的类型，其应当实现 Entry trait。以下则是 Entry 的定义： pub trait Entry: Debug + Send + Sync + 'static { type Key: Borrow<Self::KeyBorrowed> + Debug + Send + Sync + 'static; type KeyBorrowed: Debug + Display + Eq + Hash + ?...

错误处理是 Rust 中核心的一部分，从标准库中的 Result<T, E> 和 Error 到社区的 anyhow、thiserror、color-eyre、snafu 等 crates，可见其重要地位。但是在我看来，这些仅仅是错误处理机制的基础，而不是一个十分完备的框架，同时某些 crate 的设计，要么不能符合实际需要，要么使用起来很麻烦。本文将阐述我对 Rust 错误处理的理解和自己的实践 anyerr。 std 中的基础设施 在讨论我对错误处理的理解之前，有必要先回顾标准库中与错误处理相关的基础设施。 截至本文写作时间，Rust 的最新版本为 1.84.1，接下来将以此版本为基础进行讨论。 错误与结果 标准库中最广为人知的一个类型就是 Result<T, E>，用来表示一个可能成功或失败的结果。这是一个非常精妙的设计，主要体现其可以编码成功或失败中的一者，而不是将失败结果糅合进成功结果的值中。C 广泛采用后一种处理方式，导致 API 的混乱，当然这很大一部分是历史原因。在 Java 等以异常为主要错误处理机制的语言中，这一问题有了很大改善，但这又引入了隐式控制流的问题，Result<T, E> 则又避开了这个问题。所以，Result<T, E> 应该是一个很不错的机制。 尽管 Result<T, E> 中的 E 代表错误，但标准库对其具体应是什么类型没有什么限制。一般情况下，E 是一个实现了 Error trait 的类型，或者是其他可以间接地访问到内部的错误的类型，如 Box<dyn Error>。 错误类型的统一契约 若某类型实现了 Error，那么其就可以以一种标准的形式来被集成的错误处理的框架中。Error 规定了如何显示错误信息（通过 Display trait）和如何溯源错误（通过 <Self as Error>::source()）。 在 Rust 早期，并没有 Error，错误处理是处于一种野蛮生长的状态。直到 Error 的引入，Rust 才可以算是有了一套标准的错误处理机制。 错误的传播 Result<T, E> 虽好，但在深层函数调用中，一次次手动向上传播错误却很麻烦。? 运算符则有效解决了这个问题，实现了把错误方便的提前返回，传播给调用方。 ? 的使用不要求被传播错误类型和接受的错误类型完全相同，只需要有 From 的联系，即如果 E1: From<E2>，那么对 Result<U, E2> 使用 ?...

在 Linux 下，GUI 外观配置一直是一个复杂的话题。本文试图梳理 Qt 和 GTK 两种 GUI 框架的相关概念，并给出不同情况下的配置方案，实现外观的统一。 本文讨论的 Qt 包括 Qt 5 和 Qt 6，GTK 包括 GTK 2、GTK 3、GTK 4，并且将以 Qt 6 和 GTK 4 为重点。测试的 DE 和 WM 包括 GNOME 4.46、KDE Plamsa 6.1、Hyprland 0.41。 配置组成 基本概念 外观配置一般包括以下几个方面： 主题/Theme：这是一个比较广泛的概念，一般包括了样式、图标和鼠标指针等各配置项在内。 样式/Style：一般指程序窗口、面板、组件的外观。 图标/Icon 指针/Cursor 字体/Font 配色方案/Color Scheme：较细粒度的配置项，诸如主要颜色、强调颜色的配置都属于配置方案。 声音/Sound …… 这是一个比较广泛的定义，具体到各框架，又会产生一定的变化。 GTK GTK 中可直接配置的部分相对较少，主要是： 主题/Theme：主要与一般定义中的样式/Style 对应。 图标/Icon Theme：与一般定义中的图标/Icon 相同。 指针/Cursor Theme：与一般定义中的指针/Cursor 相同。 字体/Font：与一般定义中的字体/Font 相同。 包括 GNOME 在内的基于 GTK 开发的 DE 基本上直接使用上述概念，利用这些 DE 的工具配置外观，基本上就是对 GTK 的配置直接修改。...

紧张的考试周过后，终于有时间和朋友玩 Minecraft 了。为了方便进行多人游戏，我和 @whitepaperdog 决定购买一台云主机作为服务器。鉴于 NixOS 强大的 reproducibility 以及我这半年使用 NixOS 的优秀体验，我决定将服务器的系统更换为 NixOS，并在其之上部署 Minecraft 服务。 准备工作 NixOS 安装 这台服务器并不是用我的账号买的，所以我没有办法直接在控制台上传 NixOS 的镜像进行安装。等我拿到 root 密码后，系统就已经是 Ubuntu 了。在此情况下，我选择了使用 NixOS-infect。NixOS-infect 是一个 shell 脚本，其在服务器上安装 Nix，再用 Nix 构建出 NixOS，最后修改 bootloader 配置，添加 NixOS 的启动项并删除其他东西。 使用 NixOS-infect 前需要配置好访问 root 的 SSH 公钥，这是因为 NixOS-infect 并没有提供设置 root 密码的步骤，并且 NixOS 默认情况下将禁用 SSH 通过密码登录 root。NixOS-infect 脚本会将原有的 root 的公钥重新导入到新的 NixOS 里。 由于服务器在国内，所以访问 nixpkgs 的 cache 将会非常慢，在安装 NixOS 之前需要配置好 cache 镜像。编辑脚本，在完成 Nix 的安装后，配置镜像源： infect() { # ....

最近发现了一个用 Rust 写的 Vim-like 编辑器 Helix，用有强大的性能和各种开箱即用的功能。经过短暂时间的体验，我认为 Helix 已经可以在大部分领域替代 Vim/Neovim/VS Code。 性能 作为一款用 Rust 写的编辑器，Helix 自然拥有优异的性能。得益于其丰富的内置功能，Helix 无需插件就可以完成许多 Vim 只能用插件做到的事，并且还通过 Rust 获得了性能上的优势。现在我的 Neovim 安装有 coc.nvim、vim-visual-multi 等插件，共十个，启动需要延迟近 0.5 秒，虽然已经显著快于 VS Code，但相比 Helix 的小于 0.1 秒，还是稍显逊色。（当然这可能与我现在用的是 Windows 有关） 虽然现在（2023年4月8日）Helix 还没有插件系统，但未来的插件系统大概率会用 WASM 实现，相比 Vim Script 以及 Neovim 用的 Lua 等脚本语言会更快。 编辑体验 整体思路 首先 Helix 和 Vim 一样都是模态编辑器，具有多种模式，最基本的操作思路是一样的，比如都使用 hjkl 进行移动，都使用 i、a 等进行插入，都使用 y，d、p 进行复制删除粘贴。但是 Helix 采用了 selection -> action 模式，比如向右删除 3 个字符需要按 3ld 而不是 d3l，先选择在操作，就我个人而言，这种方式确实更舒适。 另外，Helix 的命令有丰富的提示，而且还可以通过 <space> ?...

项目地址：https://github.com/oosquare/brainfuck-interpreter Brainfuck 是什么就不具体介绍了，可以看这里。以下简称 bf。 这个解释器实现总体上是比较简单的，但是相比其他的大多数解释器还是有比较多的不同之处，具体如下： 更多的配置选项 内存的长度与地址范围：可配置为负数 单个内存单元的数据类型 数据溢出处理机制：wrap 或错误 读到 EOF 的处理机制：返回 0、EOF 本身或不改变 优化指令 采用类似编译为字节码的机制 这个项目可以算是学习 Rust 的练手项目，尝试着用了如 clap 这样的 crate。接下来就介绍一些技术细节。 使用方法 具体说明在项目 README. 编译、安装、执行全过程： $ git clone https://github.com/oosquare/brainfuck-interpreter.git $ cd brainfuck-interpreter $ cargo install --path ./crates/bf-exec # The program will be installed to ~/.cargo/bin $ bf-exec ./examples/helloworld.bf Hello World! ./examples/helloworld.bf： ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>. 实现原理 目前，项目分为两个 crate：common 与 bf-exec，其中 common 实现了解释器的所有逻辑，而 bf-exec 是 common 的前端，负责处理输入和配置。 common 的模块树如下： complier：解析代码并转换为 IR (Intermediate Representation，中间表示) lexer：词法分析 parser：语法分析并优化，生成 AST SyntaxTree syntax：AST 生成 optimizer：AST 优化 instruction：根据 AST 生成 IR，同时也是最终执行的指令 execution：IR 的执行与相关环境 memory：按照 bf 的内存模型实现的可配置内存 strategy：基于策略模式实现的可配置组件 config：构建 Memory 的配置 stream：bf 的 IO 实现 config：构建 InStream、OutStream 的配置 context：Memory 与 InStream、OutStream 的组合 processor：运行指令，并调用 Context 实现细节 代码优化 同质代码合并 首先最简单的就是这个优化，它是指把相邻的 + 与 -、< 与 > 合并到一起并加上一个重复次数。...

写本文之前，我共有两百多道题目在校内 OJ 上通过，由于某些原因，想要保存这些代码，于是想到使用 Python 实现自动爬取代码。同时考虑到效率问题，决定使用 aiohttp 编写一个高性能异步爬虫。 实现目标分析 这个爬虫需要能够爬取所有的已通过题目的列表，并继续爬取这些已通过题目的代码，随后保存到文件中。 校内 OJ 基于 SYZOJ 搭建，该 OJ 的项目地址为 https://github.com/syzoj/syzoj，故接下来的代码都是基于其实现的。 由于这个 OJ 的外网域名的带宽很小，一个网页最坏情况下需要花费 2～3 秒的时间，所以必须采用异步实现。这里就使用 aiohttp 了。 获取 Cookie 由于直接从浏览器里获取的 Cookie 无法正常使用，传给服务器无法识别，猜测是编码问题，所以使用在爬虫运行时即时获取 Cookie 的办法。 分析 SYZOJ 的登陆页面源码，找到如下代码片段： function login() { password = md5($("#password").val() + "syzoj2_xxx"); $("#login").addClass("loading"); $.ajax({ url: "/api/login", type: 'POST', data: { "username": $("#username").val(), "password": password }, async: true, success: function(data) { error_code = data.error_code; switch (error_code) { case 1001: show_error("用户不存在"); break; case 1002: show_error("密码错误"); break; case 1003: show_error("您尚未设置密码，请通过下方「找回密码」来设置您的密码。"); break; case 1: success(data....

概述 MultiGenerator 作为早年我的试验项目，已不再适合于实际使用。如果想要生成数据，请使用性能更高且更简单的 Rust 实现：data-gen-rs。 MultiGenerator 是一个为 OI 而生的多线程并行数据生成库，基于 C++ 17，使用面向对象和泛型等 Morden C++ 高级特性，只需要添加最少的额外代码，就可以获得最高的性能。以下是一个能够指定数据范围的 A + B Problem 数据生成器的示例代码： #include <random> #include <MultiGenerator.hpp> using MultiGenerator::DataConfig; using MultiGenerator::GeneratingTask; using MultiGenerator::SolutionTask; using MultiGenerator::NormalTemplate; using MultiGenerator::entry; using MultiGenerator::testcase; /** 指定数据生成器，仅需继承一个抽象类和实现一个成员函数 */ class AddGenerator : public GeneratingTask { private: void generate(std::ostream &data, const DataConfig &config) override { /** DataConfig 为配置信息，可以用于储存数据范围等元信息 */ auto minValue = std::stoi(config.get("minValue").value()); auto maxValue = std::stoi(config.get("maxValue").value()); std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution<> dist(minValue, maxValue); /** 像 cout 一样输出生成结果 */ data << dist(gen) << " " << dist(gen) << std::endl; } }; /** 指定数据求解器，也仅需继承一个抽象类和实现一个成员函数 */ class AddSolution : public SolutionTask { private: /** 假如你有标程，仅需要把程序用这个类包装起来，再把 main() 改为这个成员函数即可 */ void solve(std::istream &dataIn, std::ostream &dataOut, const DataConfig &) override { int a, b; /** 像 cin 一样读入数据 */ dataIn >> a >> b; /** 像 cout 一样输出答案 */ dataOut << a + b << std::endl; } }; int main() { constexpr int MAX_THREAD_COUNT = 8; constexpr int MAX_TESTCASE_COUNT = 20; constexpr char PROBLEM_NAME[] = "add"; /** 创建一个题目生成模板，指定数据文件名为 add#....

二分图 定义 如果一个图 $G=(V,E)$ 中的结点可以被分为两个部分，且两个部分之内的点互相没有连边，则称这种图为二分图。如果每个结点的度数相等且都为 $k$，则称这种二分图为 $k$ - 正则二分图。 判断 对图的结点进行黑白染色，相连的结点染不同的颜色，若最后满足每条边的两个端点颜色不相同，则这个图是二分图。树也是二分图。 染色 这里的染色不同于判断的染色，它指的是对边进行染色。若染 $k$ 种颜色，则称其为二分图的 $k$ 染色。 对于一个 $k$ - 正则二分图来说，它一定可以被 $k$ 染色，而对于一般的二分图，若其最大度数为 $k$，则它也可以被 $k$ 染色。 匹配 在二分图的边集中选出一个非空子集，且这个非空子集内没有两条边连接了一个相同的端点，则这个非空子集被称为二分图的一个匹配，同样对于一般图也有类似的概念。 若一个匹配的所含的边数最大，则称这个匹配为最大匹配。 若二分图两边的结点个数相同，且存在一个匹配满足其中的边连接了所有的点，则这个匹配被称为这个二分图的完美匹配或者完备匹配。 若每条边有边权，且一个匹配的所含的边的权值和最大，则这个匹配被称为这个二分图的最大权匹配。 匈牙利算法 交替路 假设在二分图最大匹配的过程中，已经找到了一些边作为一个匹配，则一条交替路就是一个匹配边和非匹配边交替连接组成的简单路径。 根据二分图的定义，假设一条交替路的起点在左边，且第一条边是匹配边，则这条交替路中的匹配边一定都是从左边到右边，而非匹配边一定是从右边到左边。 交替路上的结点最多连接一条匹配边和一条非匹配边，所以如果把交替路上的匹配边变为非匹配边，非匹配边变为匹配边，则仍然满足条件，也就是交替路边集的匹配边集的补集也可以是匹配。 增广路 匈牙利算法的核心就是找增广路，这条增广路是一条交替路。每次增广从左边开始，第一条边是非匹配边，最后一条边也是非匹配边，根据上文的描述，这样的路径的边数为奇数，非匹配边个数比匹配边个数多 $1$，若把匹配边与非匹配边反转，则反转后的边集仍然是一个合法的匹配，且比原来的匹配的边数多了 $1$。如果能找到一条这样的增广路，则此次增广成功。 具体来说，比如一个左边的结点 $x$ 找到了一个右边的结点 $y$，它没有与其他左边的结点匹配过，则 $e(x,y)$ 可以作为一个匹配边，反转边集前，有 $1$ 条匹配边，$0$ 条非匹配边，增广成功。 如果右边的结点 $y$ 已经有匹配了，那么就可以让原来 $y$ 的匹配 $x'$ 新找一个点 $y'$，如果能够找到这个 $y'$，那么 $e(x',y')$ 成为一个匹配边，$y$ 就无需和 $x'$ 匹配了，也就是说 $y$ 已经变为了一个没有匹配的点，$x$ 就可以与 $y$ 匹配了。如果 $x'$ 找不到 $y'$，那么 $x'$ 就要保持原样，和 $y$ 匹配，那么 $x$ 就不可以和 $y$ 匹配，只能继续寻找下一个可能的结点。...