RustPythonの紹介

## はじめに

RustPythonの紹介記事です。
ソースコードを読んでRustPythonがどのように実装されているかも調べました。

## RustPythonとは

RustPythonとはその名の通りRustで実装されたPythonインタプリタです。
以下の特徴があります。

* Rustで書いたプログラムにPythonを組み込める

* WebAssemblyにコンパイルすることでWeb上でPythonコードが実行できる

## インストール

Rustを最新版に更新します。

```
$ rustup install stable
```

以下のコマンドを実行します。

```
$ cargo install --git https://github.com/RustPython/RustPython
```

Windowsの場合は環境変数`RUSTPYTHONPATH`を追加する必要があります。
自分の環境では以下の値を設定しました。

```
%USERPROFILE%\.cargo\git\checkouts\rustpython-f8ef4d934ac33cd8\eb337e5\Lib
```

## 使い方

`rustpython`でREPLが起動します。

```
>rustpython
Welcome to the magnificent Rust Python 0.1.2 interpreter 😱 🖖
>>>>>
```

通常のPythonと同じように使えます。

```
>>>>> x = 9
>>>>> print(x)
9
>>>>> [i for i in range(20) if i % 2 == 0]
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
>>>>>
```

### 指定したファイルを実行

指定した`.py`ファイルを実行できます。

```py:fizzbuzz.py
import sys

def main():
    for i in range(1, int(sys.argv[1]) + 1):
        if i % 15 == 0:
            print("FizzBuzz")
        elif i % 5 == 0:
            print("Buzz")
        elif i % 3 == 0:
            print("Fizz")
        else:
            print(i)

if __name__ == "__main__":
    main()
```

```
$ rustpython fizzbuzz.py 15
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
```

### Rustのコードから実行
crates.ioは更新されていないのでGithub上のコードを指定します。
`Cargo.toml`に以下を追加します。

```
[dependencies]
rustpython-vm = {git="https://github.com/RustPython/RustPython", version="0.1.2"}
```

[example/hello_embed.rs](https://github.com/RustPython/RustPython/blob/main/examples/hello_embed.rs)をそのまま実行します。

```rust:main.rs
use rustpython_vm as vm;

fn main() -> vm::PyResult<()> {
    vm::Interpreter::without_stdlib(Default::default()).enter(|vm| {
        let scope = vm.new_scope_with_builtins();

        let code_obj = vm
            .compile(
                r#"print("Hello World!")"#,
                vm::compiler::Mode::Exec,
                "<embedded>".to_owned(),
            )
            .map_err(|err| vm.new_syntax_error(&err))?;

        vm.run_code_obj(code_obj, scope)?;

        Ok(())
    })
}
```

```
> cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.34s
     Running `target\debug\rp_test.exe`
Hello World!
```

### 絵文字が使える

RustPythonでは絵文字を識別子として使うことが可能です。

```
>>>>> 🦀 = "Rust"
>>>>> 🐍 = "Python"
>>>>> 🦀 + 🐍
'RustPython'
```

ただし記号、テメーはダメだ。

```
>>>>> ★ = 255
SyntaxError: Got unexpected token 笘・at line 1 column 1
笘・= "Star"
^
```

この機能についてissue上で議論がされていました。
どうやらイースターエッグとして実装されているようです。
https://github.com/RustPython/RustPython/issues/3511

## ソースコードを読む

せっかくなのでRustPythonのソースコードを少し読んでみましょう。
※コミットID[b9c62ed](https://github.com/RustPython/RustPython/tree/b9c62ed8916c720e98026a40fce5c73a2de04ac6)の時点でのソースコードを読みます。

[Development Guide](https://github.com/RustPython/RustPython/blob/main/DEVELOPMENT.md)によるとRustPythonは以下の様に動作しているようです。

1. Pythonコードをトークン列に変換（字句解析)

2. トークン列が正しい並びかチェック

3. トークン列をAST(抽象構文木)に変換 (構文解析)

4. ASTからバイトコードを生成

5. バイトコードを仮想マシン上で実行

一度に全てを読むのは大変なので、今回は字句解析の処理を読みます。

### 字句解析

字句解析とはPythonコードの文字列を1文字ずつ読み進めながら
**トークン**という意味を持つ最小単位の並びに変換する処理のことです。
トークンは列挙型で定義されています。

```rust:compiler/parser/src/token.rs
pub enum Tok {
    Name { name: String },
    Int { value: BigInt },
    Float { value: f64 },
    Complex { real: f64, imag: f64 },
    String { value: String, kind: StringKind },
    Bytes { value: Vec<u8> },
    Newline,
    Indent,
    Dedent,
    ...
```

例えば`x = 10`という文字列を字句解析すると以下のようなトークンの並びになります。

```
Name{ name: "x" }, Equal, Int{ value: 10 }, NewLine
```

#### Lexer

字句解析を行っているのが`Lexer`です。
`Lexer`はトークンを返すイテレータです。

```rust:compiler/parser/src/lexer.rs
pub struct Lexer<T: Iterator<Item = char>> {
    window: CharWindow<T, 3>,

    at_begin_of_line: bool,
    nesting: usize, // Amount of parenthesis
    indentations: Indentations,

    pending: Vec<Spanned>,
    location: Location,
}
```

`window`は`char`を1文字ずつ読み進める`CharWindow`が代入されます。
`at_begin_of_line`は行頭であるか表します。
`nesting`は現在のネストの深さを表します。
括弧(`()`,`[]`,`{}`)に入ると加算され、括弧を抜けると減算されます。
`pending`には生成されたトークンが追加されます。
`location`には現在の文字の位置(行番号、列番号)が格納されています。

#### CharWindow

次に`CharWindow`の定義を見ていきます。

```rust:compiler/parser/src/lexer.rs
struct CharWindow<T: Iterator<Item = char>, const N: usize> {
    source: T,
    window: [Option<char>; N],
}
```

`source`には`char`を返すイテレータが代入されます。
`Lexer.window`の場合は`NewLineHandler`が代入されます
`window`は現在の位置からN-1文字先の文字が格納される配列です。
この配列のおかげで読み進めずに文字の先読みが可能です。

#### NewLineHandler

実際に1文字ずつ読み進める処理を行っているのが`NewLineHandler`です。
定義は以下の通りです。

```rust:compiler/parser/src/lexer.rs
// The newline handler is an iterator which collapses different newline
// types into \n always.
pub struct NewlineHandler<T: Iterator<Item = char>> {
    window: CharWindow<T, 2>,
}
```

内部にまた`CharWindow`が出てきました。。。。
ですが`NewLineHandler`の生成コードを見るとここには文字列の`chars`を渡しています。
なので相互参照は発生していませんが、少しややこしいです。

```rust:compiler/parser/src/lexer.rs
pub fn make_tokenizer_located(
    source: &str,
    start_location: Location,
) -> impl Iterator<Item = LexResult> + '_ {
    let nlh = NewlineHandler::new(source.chars());
    Lexer::new(nlh, start_location)
}
```

また`NewLineHandler`のイテレータ実装は以下の様になっています。
`shift`は1文字読み進める関数です。

```rust:compiler/parser/src/lexer.rs
    fn next(&mut self) -> Option<Self::Item> {
        // Collapse \r\n into \n
        loop {
            match (self.window[0], self.window[1]) {
                (Some('\r'), Some('\n')) => {
                    // Windows EOL into \n
                    self.shift();
                }
                (Some('\r'), _) => {
                    // MAC EOL into \n
                    self.window.change_first('\n');
                }
                _ => break,
            }
        }

        self.shift()
    }
```

改行コードが`\r\n`や`\r`の場合は`\n`を返すように調整しています。
1文字先読みをすることで改行コードが`\r\n`であるかの判定を行っています。

改行コードによる面倒な分岐処理は`NewLineHandler`が行っています。
なので`Lexer`は改行コードの違いを意識する必要がありません。
上手く責任範囲を切り分けています。

#### inner_next

`Lexer`のイテレータ実装は以下の通りです。

```rust:compiler/parser/src/lexer.rs
    fn next(&mut self) -> Option<Self::Item> {
        // Idea: create some sort of hash map for single char tokens:
        // let mut X = HashMap::new();
        // X.insert('=', Tok::Equal);
        let token = self.inner_next();
        trace!(
            "Lex token {:?}, nesting={:?}, indent stack: {:?}",
            token,
            self.nesting,
            self.indentations,
        );

        match token {
            Ok((_, Tok::EndOfFile, _)) => None,
            r => Some(r),
        }
    }
```

`inner_next`は以下の通りです。
現在の位置が行頭ならば`handle_indentations`でインデントを解析します。
その後、`consume_normal`で各種トークンを解析します。

生成されたトークンは`pending`に追加されます。
`pending`にトークンが追加されたらループを抜けて先頭のトークンを返します。

```rust:compiler/parser/src/lexer.rs
    /// This is the main entry point. Call this function to retrieve the next token.
    /// This function is used by the iterator implementation.
    fn inner_next(&mut self) -> LexResult {
        // top loop, keep on processing, until we have something pending.
        while self.pending.is_empty() {
            // Detect indentation levels
            if self.at_begin_of_line {
                self.handle_indentations()?;
            }

            self.consume_normal()?;
        }

        Ok(self.pending.remove(0))
    }
```

`Lexer`が返す`LexResult`型の定義は以下の通りです。

```rust:compiler/parser/src/lexer.rs
pub type Spanned = (Location, Tok, Location);
pub type LexResult = Result<Spanned, LexicalError>;
```

トークンの生成に成功した場合は`(トークンの開始位置、トークン、トークンの終了位置)`のタプルを、失敗した場合は`LexicalError`を返します。

#### consume_normal

`consume_normal`を読んでいきます。
現在の文字が識別子の先頭に使える文字(アルファベットまたは`_`)ならば`lex_identifier`でトークンを解析します。
絵文字の場合は識別子トークンとして認識します。
数字や記号の場合は`consume_character`を呼び出します。

```rust:compiler/parser/src/lexer.rs
    /// Take a look at the next character, if any, and decide upon the next steps.
    fn consume_normal(&mut self) -> Result<(), LexicalError> {
        // Check if we have some character:
        if let Some(c) = self.window[0] {
            // First check identifier:
            if self.is_identifier_start(c) {
                let identifier = self.lex_identifier()?;
                self.emit(identifier);
            } else if is_emoji_presentation(c) {
                let tok_start = self.get_pos();
                self.next_char();
                let tok_end = self.get_pos();
                self.emit((
                    tok_start,
                    Tok::Name {
                        name: c.to_string(),
                    },
                    tok_end,
                ));
            } else {
                self.consume_character(c)?;
            }
        ...
```

#### lex_identifier

`lex_identifier`ではまず文字列トークンであるかを判定します。
`b""`, `r""`, `u""`, `f""`等の形式を見つけたら`lex_string`で文字列トークンを生成します。

文字列でなかったら各種識別子に対応したトークンを生成します。
`KEYWORDS`は識別子名をキーにトークンを返す辞書です。
例えば`"for"`ならForトークンが、`"if"`ならIfトークンを返します。
`KEYWORDS`に存在しない場合は、ユーザー定義の識別子です。

```rust:compiler/parser/src/lexer.rs
    // Lexer helper functions:
    fn lex_identifier(&mut self) -> LexResult {
        let mut name = String::new();
        let start_pos = self.get_pos();

        // Detect potential string like rb'' b'' f'' u'' r''
        let mut saw_b = false;
        let mut saw_r = false;
        let mut saw_u = false;
        let mut saw_f = false;
        loop {
            // Detect r"", f"", b"" and u""
            if !(saw_b || saw_u || saw_f) && matches!(self.window[0], Some('b' | 'B')) {
                saw_b = true;
            } else if !(saw_b || saw_r || saw_u || saw_f)
                && matches!(self.window[0], Some('u' | 'U'))
            {
                saw_u = true;
            } else if !(saw_r || saw_u) && matches!(self.window[0], Some('r' | 'R')) {
                saw_r = true;
            } else if !(saw_b || saw_u || saw_f) && matches!(self.window[0], Some('f' | 'F')) {
                saw_f = true;
            } else {
                break;
            }

            // Take up char into name:
            name.push(self.next_char().unwrap());

            // Check if we have a string:
            if matches!(self.window[0], Some('"' | '\'')) {
                return self
                    .lex_string(saw_b, saw_r, saw_u, saw_f)
                    .map(|(_, tok, end_pos)| (start_pos, tok, end_pos));
            }
        }

        while self.is_identifier_continuation() {
            name.push(self.next_char().unwrap());
        }
        let end_pos = self.get_pos();

        if let Some(tok) = KEYWORDS.get(name.as_str()) {
            Ok((start_pos, tok.clone(), end_pos))
        } else {
            Ok((start_pos, Tok::Name { name }, end_pos))
        }
    }
```

#### consume_character

`consume_character`では数値や記号で始まるトークンの解析を行います。
この関数内でも文字列トークンの判定をしていますが、ここではプレフィックスの付かない文字列を想定しています。

```rust:compiler/parser/src/lexer.rs
    /// Okay, we are facing a weird character, what is it? Determine that.
    fn consume_character(&mut self, c: char) -> Result<(), LexicalError> {
        match c {
            '0'..='9' => {
                let number = self.lex_number()?;
                self.emit(number);
            }
            '#' => {
                let comment = self.lex_comment()?;
                self.emit(comment);
            }
            '"' | '\'' => {
                let string = self.lex_string(false, false, false, false)?;
                self.emit(string);
            }
            '=' => {
                let tok_start = self.get_pos();
                self.next_char();
                match self.window[0] {
                    Some('=') => {
                        self.next_char();
                        let tok_end = self.get_pos();
                        self.emit((tok_start, Tok::EqEqual, tok_end));
                    }
                    _ => {
                        let tok_end = self.get_pos();
                        self.emit((tok_start, Tok::Equal, tok_end));
                    }
                }
            }
        ...
```

今回はここまでにします。
興味を持った方は`lex_number`や`lex_comment`等もぜひ読んでみてください。

## 終わりに

内部のソースコードを読みましたが、関数呼び出しの階層が深いため処理を追うのが結構大変でした。
ですが、1つ1つの処理はそこまで難しくはないのでしっかり読めば理解できました。
RustとPython両方の勉強になるので、構文解析やバイトコード生成も読もうと思います。

## 参考文献

https://rustpython.github.io/

https://github.com/RustPython/RustPython/

https://github.com/RustPython/RustPython/blob/main/DEVELOPMENT.md

https://ja.wikipedia.org/wiki/%E5%AD%97%E5%8F%A5%E8%A7%A3%E6%9E%90