Rustの&strや&[T]はどこを参照しているのか

# Rustその3 Advent Calendar 2019

この記事は、Rustその3 Advent Calendar 2019 5日目の記事です。

4日目 -> [cargo publishできないRustプロジェクト](https://qiita.com/dalance/items/12c56e07971cfc3ac06c)
6日目 -> [[Rust] IntegerとFloatの両方でmaxが必要なとき](https://qiita.com/matt76k/items/c0c16693d2a5e85c0e05)

# はじめに

C/C++/Fortranなどのプログラミング言語の経験がある人がRustに触れたときに、次のような疑問は誰しも感じると思います。

- Rustの文字列はなぜstrではなく&strなの？
- Rustのスライスが何を指しているのかよく分からない

実際、C++における部分文字列の参照は[std::basic_string_view](https://ja.cppreference.com/w/cpp/string/basic_string_view)という普通のクラスで表現されていますし、配列に関しても[vector_view](https://github.com/r-lyeh-archived/vector_view/blob/master/vector_view)という外部のライブラリまで存在しています。

そもそも参照型とは何らかの変数への参照を表すものなので、`&str`という型が存在するということは、その参照源となる`str`型の変数がどこかに存在するはずなのですが、我々はそれを見たことがありません。

では一体、`&str`型や`&[T]`型の変数はどこを参照しているのでしょうか？

それを知るためには、Rustにおけるポインタの概念からきちんと理解し直さなければなりません。

# Rustにおけるポインタ型

64bitアーキテクチャ上では、メモリアドレスは64bitで表現されます。
これは、システムプログラミングの経験がある方にとってはもはや常識だと思います。


ところで、CやC++, Rustにはポインタという概念があります。
このポインタを用いると、次のように変数への参照を取得することができます。

```c
int a = 1;
int* pa = &a;
*pa = 2;
printf("%d\n", a);  // => 2
```

これは、ポインタ変数の実体がデータのメモリアドレスを表しているからです。
なので、C/C++においては、すべてのポインタ変数は64bitで表されます。

ここで「C/C++」とだけ書いてRustを除外したのには理由があります。

**Rustのポインタは64bitとは限らない**からです。

# Rustのポインタ型の中身を見る

まず、Rustの変数のバイト列を取得するために、`AsRawBytes`トレイトを定義・実装します。

```rust
trait AsRawBytes {
    fn as_raw_bytes<'a>(&'a self) -> &'a [u8];
}

impl<T: ?Sized> AsRawBytes for T {
    fn as_raw_bytes<'a>(&'a self) -> &'a [u8] {
        unsafe {
            std::slice::from_raw_parts(
                self as *const T as *const u8,
                std::mem::size_of_val(self))
        }
    }
}
```

`as_raw_bytes`関数は、変数をバイト列で表したときの中身を`&[u8]`型で返します。

これにより、変数のバイト列の中身を見ることができます。

```rust
let val = 0x1fc4;
println!("{:x?}", val.as_raw_bytes()); // => [c4, 1f, 0, 0]
```

リトルエンディアンなのでバイト順が逆になっていることに注意します。

### ※追記（2019/12/6）

`AsRawBytes`トレイトはUndefined Bahaviourを起こす危険があります！`AsRawBytes`の使用上の注意点について@qnighy さんからコメントを頂いたので、是非そちらもご覧ください。

## 普通のポインタ型

まずはi32のポインタ型について見てみます。

```rust
let pval = &0x1fc4 as *const i32;
println!("{:x?}", pval.as_raw_bytes());
// => [b8, f1, a3, d2, ae, 55, 0, 0]
```

きちんと8バイト（ = 64bit）で表されていますね。

当然ながらメモリアドレス（絶対アドレス）は実行するたびに変わるので、上記のプログラムの出力結果も毎回異なります。

## `*[T]`型

では、スライスへのポインタはどうなるのでしょうか。実験してみます。

```rust
let s = [3, 1, 4];
let ps = &s as *const [i32];
println!("{:x?}", ps.as_raw_bytes());
// => [10, 2, 59, b5, 7f, 55, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0]
```

なんと、ただのポインタ変数なのに16バイトで表現されています。

### スライスの先頭のアドレスと比較する

どういうことでしょうか？もう少し理解を深めるために、スライスの先頭のメモリアドレスを取得して比較してみます。

```rust
let s = [3, 1, 4];
let ps = &s as *const [i32];
println!("{:x?}", ps.as_raw_bytes());
// => [10, 92, c6, cf, 5b, 55, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0]

let pval = &s[0] as *const i32;
println!("{:x?}", pval.as_raw_bytes());
// => [10, 92, c6, cf, 5b, 55, 0, 0]
```

これらのポインタ変数の最初の8バイトが一致していることが分かります。つまりこの部分が配列の最初の要素のメモリアドレスを指していると予想できます。

残る8バイトの部分は、整数で表すと`3`になるので、スライスの長さを表していると予想できます。

## `*str`型

正解を見る前に、今度は`*str`の中身を見てみます。

```rust
let apple = "apple" as *const str;
println!("{:x?}", apple.as_raw_bytes());
// => [8, 32, 46, d1, 26, 56, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0]

let apple = apple as *const ();
println!("{:x?}", apple.as_raw_bytes());
// => [8, 32, 46, d1, 26, 56, 0, 0]
```

こちらも、先頭8バイトが文字列の先頭のメモリアドレスで、残り8バイトが部分文字列の長さを表していると予想できます。

# `*str`や`*[T]`の正体

結論から言うと、`*str`や`*[T]`は、fat pointerと呼ばれる特殊なポインタ型に分類されます。

Jim Blandy and Jason Orendorffによる"Programming Rust: Fast, Safe Systems Development"という素晴らしい書籍があったのでそこから定義を拝借すると、fat pointerとは

> two-word values carrying the address of some value, along with some further information necessary to put the value to use.

(訳)

> 何らかの値のアドレスと、その値を利用するために必要な情報を格納した2ワードの値

つまり、単にメモリアドレスだけでなく、その値に関する情報を付け加えた2つの値のセットと読み替えることができます。

「その値に関する情報」とは、`*[T]`の場合は部分配列の長さを、`*str`の場合は部分文字列の長さを表します。

これらの他にも、例えばトレイトオブジェクトへのポインタ`*SomeTrait`もfat pointerに分類されます。この場合は、オブジェクトへのポインタの他にvtableのアドレスが格納されます。

## fat pointerの特性

fat pointerは通常のポインタとはいくつかことなる性質を持つので注意する必要があります。

### 1. fat pointerから通常のpointerへはキャスト可能。逆は不可能。

ポインタの構造を考えれば当たり前なのですが、これらのキャストは不可逆変換です。
通常のポインタからfat pointerへキャストしようとするとコンパイルエラーになります。

```rust
let ps = &[3, 1, 4] as *const [i32] as *const ();

let pa = &314 as *const i32 as *const [u8];
// => cannot cast thin pointer `*const i32` to fat pointer `*const [u8]`
```

ただし、trait objectへのポインタのみ例外があります。

あるポインタ型`*T`から、Tが実装するトレイト`SomeTrait`のポインタ型`*SomeTrait`へのキャストは有効です（アップキャスト）。

```rust
let mut stdout = std::io::stdout();
let writer = &mut stdout as *mut std::io::Stdout as *mut std::io::Write;
```

### 2. 一部のポインタ演算が禁止

fat pointerの参照先の型は通常Sized traitを実装していないので、[pointer型のメソッド](https://doc.rust-lang.org/std/primitive.pointer.html#method.write_bytes)はほとんど使用することはできません（トレイト境界ではじかれるため）。

fat pointerでアドレス演算を行いたい場合は、一度通常のポインタにキャストすることで可能になります。

```rust
let ps = &[3, 1, 4] as *const [i32] as *const i32;
let ps = ps.add(1);
```

# 参照型の場合

ここまでは分かりやすくするために敢えてポインタ型について解説してきましたが、実際にプログラムを記述する際は参照を扱う場面のほうが圧倒的に多いと思われます。

しかし参照型であっても上記のルールは成立します。
つまり、（「参照先の変数」ではなく）「参照変数それ自体」が、変数のアドレスと付加情報を持っているということになります。

## `&str`や`&[T]`はどこを参照しているのか

この問題に対する答えは、

- `&str`は文字列の一部分を参照している
- `&[T]`は配列の一部分を参照している

となります。

しかし他の参照変数と異なり、`&str`型や`&[T]`型の変数それ自体が、部分配列の長さの情報も持っています。

言うなれば、`&str`はC++の`std::basic_string_view`、`&[T]`は`vector_view`と等価な構造体と捉えることができます。

# 具体例

## `&[T]`

```rust
let s = [1, 7, 3, 2, 0, 5];

// "1"の位置のメモリアドレスと部分配列の長さ(6)を保持
let ps1 = &s;

// "3"の位置のメモリアドレスと部分配列の長さ(4)を保持
let ps2 = &s[2..];

// "7"の位置のメモリアドレスと部分配列の長さ(2)を保持
let ps3 = &s[1..3];
```

## `&str`

```rust
let s = "melon";

// "m"の位置のメモリアドレスと部分配列の長さ(5)を保持
let ps1 = &s;

// "l"の位置のメモリアドレスと部分配列の長さ(2)を保持
let ps2 = &s[2..4];

let mut segments = s.split("o");

// "m"の位置のメモリアドレスと部分配列の長さ(3)を保持
let ps3 = segments.next().unwrap();
```

# 参考文献

- Blandy Jim and Orendorff Jason. (2017) Programming Rust : fast, safe systems development. O'Reilly
- [Rust 初心者が自動型変換や型変換関係のトレイトを自信を持って扱えるようになるための型変換まとめ 8 パターン](https://qiita.com/nirasan/items/e9c621240a7aae914cb8)
- [メモリをダンプしてRustのsliceとVecを理解する - 逆さまにした](https://cipepser.hatenablog.com/entry/rust-memory)