Reading: Rust RFC 2535

2535-or-patterns - のメモ。

Summary

パターンマッチ内で任意にネストした形式で |(or pattern) を使えるようにする。 記法は Some(A(0) | B(1 | 2)) のようになる。

以前は Some(A(0)) | Some(B(1)) | Some(B(2)) のように書かなければならなかった。

Motivation

今すでにある機能をより強力に使えるようにしたかった。 人間工学的にもよいし、可読性もよくなる。

Don’t repeat yourself

Some(Enum::A) | Some(Enum::B) | Some(Enum::C) | Some(Enum::D) => ..

この書き方は Some($pat) (!$pat は変数と考える) を繰り返す必要がある。

Some(Enum::A | Enum::B | Enum::C | Enum::D) => ..

こう書けた方がパターンが増えた時に線形にスケールしていくよね。

Mental model

この RFC の目的としては、(目で)スキャンしないといけない冗長な情報を減らして可読性を向上させること。

Is your car red, white, or blue?

Is your car red, your car white, or your car blue?

を比べると後者は不必要に your car が繰り返されているし、あなたはどちらで尋ねて欲しいか?ってこと。 この RFC を research していたときに、German (2) Swedish (3), French (2), Portuguese (1), Spanish (2), Farsi (3), Finnish (1), Esperanto (1), and Japanese (1) に聞いたら、全員が前者を好んでいた。

ということで、不完全な情報ながらも、人間にとっては CNF(conjuctive normal form) と同種のものをコミュニケーションで使うのがより一般的だと結論付けた。

Reducing complexity with uniformity

プログラミング言語が複雑性を積み重ねる主な要因は、プログラマがコードを書いたり理解したりするために覚えておかなければならないルールを増やすことによる。 この結果として、たびたび注意事項(caveats)やコーナーケースがプログラミング言語の学び、理解、記述を難しくしてしまう。 そのような注意事項を避けるには、言語を uniform に保ち続けることが重要だ。

この RFC は、すでに存在していて、ユーザーもよく知っている機能を別の機能のために拡張することで言語の複雑性を減らす。

以前は match のトップレベルの pat | pat と似たような constructs のみを許容していた。 これからは pat | pat をパターンマッチのどこでも許容する。 さらに、$p | $q というマクロも許容する。

Real world use cases

**1. **: chars_indices を iterate するステートマシンの構築

match iter.next() {
    Some(_, ' ' | '\n' | '\r' | '\u{21A1}') => {
        // Change state
    }
    Some(index, ch) => {
        // Look at char
    }
    None => return Err(Eof),
}

2.: ghc-proposals/0000-or-patterns.rst at 77ee8e615aa28fbf2d0ef2be876a852c4e63c53b · osa1/ghc-proposals に挙げられているもの

WildPat: _ のこと BangPat: ! のこと(正格評価を強制する) AsPat: [..]@xs のこと ViewPat: size (view -> Unit) = 1 とかできるやつ。ViewPatterns – GHC ConPat: type constructor のパターンマッチ

isIrrefutableHsPat pat
  = go pat
  where
    go (L _ pat) = go1 pat

    go1 (WildPat {})        = True
    go1 (VarPat {})         = True
    go1 (LazyPat {})        = True
    go1 (BangPat pat)       = go pat
    go1 (CoPat _ pat _)     = go1 pat
    go1 (ParPat pat)        = go pat
    go1 (AsPat _ pat)       = go pat
    go1 (ViewPat _ pat _)   = go pat
    go1 (SigPatIn pat _)    = go pat
    go1 (SigPatOut pat _)   = go pat
    go1 (TuplePat pats _ _) = all go pats
    go1 (SumPat pat _ _  _) = go pat
    go1 (ListPat {})        = False
    go1 (PArrPat {})        = False
    go1 (ConPatIn {})       = False
    go1 (ConPatOut{ pat_con = L _ (RealDataCon con), pat_args = details }) = ...
    go1 (ConPatOut{ pat_con = L _ (PatSynCon _pat) }) = ...
    go1 (LitPat {})         = False
    go1 (NPat {})           = False
    go1 (NPlusKPat {})      = False
    go1 (SplicePat {})      = urk pat

    urk pat = pprPanic "isIrrefutableHsPat:" (ppr pat)
  1. rfcs/0000-pipe-in-patterns.md at de235887a80555427314c7eb25c6214523d50cce · rust-lang/rfcs で言及されていたもの
for event in event_pump.poll_iter() {
    use sdl2::event::Event;
    use sdl2::keyboard::Keycode::{Escape, Q};
    match event {
        Event::KeyDown { keycode: Some(Escape | Q), ... } => break 'game,
        _ => {},
    }
    ...
}
  1. issue で要望されていたもの
  1. @alercah によるユースケース
pub fn is_green(self) -> bool {
    match self {
        | Tile::Suited(Suit::Souzu, 2 | 3 | 4 | 6 | 8)
        | Tile::Dragon(Dragon::Green) => true,
        _ => false,
    }
}
  1. sourcegraph 内で見られるもの
  1. 他のユースケース

from git2-rs:

match obj.kind() {
    Some(Commit | Tag | Tree) => ...
    Some(Blob) => ...
    None => ...
}

from src/debian/dependency.rs · 4355097810264644cb08ddaa8f7464d5887275f1 · Rust compiler tools and packages / debcargo · GitLab:

match (op, &mmp.clone()) {
    (&Lt, &(M(0) | MM(0, 0) | MMP(0, 0, 0))) => debcargo_bail!(
                    "Unrepresentable dependency version predicate: {} {:?}",
                            dep.name(),
                                    p
                                        ),
    (&Tilde, &(M(_) | MM(_, _))) => {
            vr.constrain_lt(mmp.inclast());
            vr.constrain_ge(mmp);
        }
    (&Compatible, &(MMP(0, minor, _) | MM(0, minor))) => {
            vr.constrain_lt(MM(0, minor + 1));
            vr.constrain_ge(mmp);
        }
    (&Compatible, &(MMP(major, _, _) | MM(major, _) | M(major))) => {
            vr.constrain_lt(M(major + 1));
            vr.constrain_ge(mmp);
        }
    ...,
}
  1. rustc によるもの

In src/librustc_mir/interpret/eval_context.rs:

   Some(Def::Static(..) | Def::Const(..) | Def::AssociatedConst(..)) => {},

In src/librustc_mir/util/borrowck_errors.rs:

   (&ty::TyArray(_, _), Some(true) | None) => "array",

In src/librustc/middle/reachable.rs:

   Some(Def::Local(node_id) | Def::Upvar(node_id, ..)) => { .. }

In src/librustc/infer/error_reporting/mod.rs:

   Some(hir_map::NodeBlock(_) | hir_map::NodeExpr(_)) => "body",

In src/libfmt_macros/lib.rs:

   Some((_, '>' | '<' | '^')) => { .. }

In src/librustc/traits/select.rs:

   ty::TyInfer(ty::IntVar(_) | ty::FloatVar(_)) | .. => { .. }

In src/librustc_typeck/check/mod.rs:

   ty::TyInt(ast::IntTy::I8 | ast::IntTy::I16) | ty::TyBool => { .. }

   ...

   ty::TyUint(ast::UintTy::U8 | ast::UintTy::U16) => { .. }

In src/tools/cargo/src/cargo/sources/path.rs:

   Some("Cargo.lock" | "target") => continue,

In src/libsyntax_ext/format_foreign.rs:

   ('h' | 'l' | 'L' | 'z' | 'j' | 't' | 'q', _) => {
       state = Type;
       length = Some(at.slice_between(next).unwrap());
       move_to!(next);
   },

   ...

   let width = match self.width {
       Some(Num::Next) => {
           // NOTE: Rust doesn't support this.
           return None;
       }
       w @ Some(Num::Arg(_) | Num::Num(_)) => w,
       None => None,
   };

In src/libsyntax/parse/token.rs:

   BinOp(Minus | Star | Or | And) | OrOr => true,

Guide-level explanation

$p$q をパターンとして、$p | $q は合法的なパターンになる。

enum Foo<T> {
    Bar,
    Baz,
    Quux(T),
}

fn main() {
    match Some(Foo::Bar) {
        Some(Foo::Bar | Foo::Baz) => { .. },
        _ => { .. },
    }
}

$p | $q 自体もパターンだから、任意にネストできる。

fn main() {
    match Some(Foo::Bar) {
        Some(Foo::Bar | Foo::Quux(0 | 1 | 3)) => { .. },
        _ => { .. }
    }
}

| 記号の優先順位は低いことに注意。 foo @ 1 | foo @ 2 | foo @ 3 と同じ結果を得たい時は、foo @ (1 | 2 | 3) と書かなければならない。 foo @ 1 | 2 | 3 ではなく。

Reference-level explanation

Grammar

pat 文法をトップレベルで使えるようにしたので、パターンを表す文法を:

pat<allow_top_alt>
: pat<allow_top_alt> '|' pat<allow_top_alt>
| ...
;

pat<no_top_alt>
: "(" pat<allow_top_alt> ")"
| ...
;

| の優先度は最低になっていて、特に @| より結合的である。 つまり、i @ p | q(i @ p) | q として結びつく。

注意: pat<T> は Rust がコンテキストセンシティブ(! context free grammer ではないということか?)ということを必要としない。なぜなら、パラメータ化を “monomorphize” しているから。(後述)

文法規則(! yacc?):

top_pat : '|'? pat<allow_top_alt> ;

let ステートメントは以下のように変える。

let : LET top_pat maybe_ty_ascription maybe_init_expr ';' ;

if let は以下のように変える。

expr_if_let : IF LET top_pat '=' expr_nostruct block (ELSE block_or_if)? ;

while let 式も以下になる。

expr_while_let : maybe_label WHILE LET top_pat '=' expr_nostruct block ;

for ループは以下のようにする。

expr_for : maybe_label FOR top_pat IN expr_nostruct block ;

match 式は以下。

expr_match : MATCH expr_nostruct '{' match_clause* nonblock_match_clause? '}' ;
match_clause : nonblock_match_clause ',' | block_match_clause ','? ;
nonblock_match_clause : match_arm (nonblock_expr | block_expr_dot) ;
block_match_clause : match_arm (block | block_expr) ;

match_arm : maybe_outer_attrs top_pat (IF expr_nostruct)? FAT_ARROW ;

現在パターン構文が許可されているすべてのコンテキストで任意の p | q パターンは許可されるようになるということ。

fn (関数引数)の場合:

param : pat<no_top_alt> ':' ty_sum ;

closure の場合:

inferrable_param : pat<no_top_alt> maybe_ty_ascription ;

pat マクロフラグメント指定子は pat<allow_top_alt> ではなく pat<no_top_alt> にマッチする。

Error messages

以下の例のように、|@ の優先順位に起因するエラーメッセージは後述するようなものになる。

fn main() {
    match 1 {
        i @ 0 | 1 => {},
    }
}

エラーメッセージ:

error[E0408]: variable `i` is not bound in all patterns
 --> src/main.rs:3:17
  |
3 |         i @ 0 | 1 => {},
  |         -       ^ pattern doesn't bind `i`
  |         |
  |         variable not in all patterns

i @ p | q と書いちゃったユーザーはほぼ確実に i @ (p | q) を意図している。 なぜなら、それが唯一の well formed なパターンと言えるから。 この場合は、特別に、例えば以下のようなエラーメッセージを出してあげる。

error[E0408]: variable `i` is not bound in all patterns
 --> src/main.rs:3:17
  |
3 |         i @ 0 | 1 => {},
  |         -       ^ pattern doesn't bind `i`
  |         |
  |         variable not in all patterns
  |
  | hint: if you wanted `i` to cover both cases, try adding parentheses around:
  |
  |         i @ 0 | 1
  |             ^^^^^

こういったエラーメッセージを具体的にどうするかは各実装に委ねられる。

Static semantics

  1. ある深さ(! lexical な意味で。)で任意の p | q パターンが与えられた時、以下の条件が満たされれればセマンティクス違反となる。
    • p の推論された型が q の推論された型へと単一化できなかった
    • pq で同一の束縛の集合が導けなかった
    • pq 内で同一名の束縛があり、その型が、型ないしは束縛の仕方の観点から単一化できなかった

前述したすべてのインスタンス(! all instances とは何のことだ?)では型の単一化は厳格(明示的)であって、暗黙的な type coercions は適用されない。

  1. match e_s { a_1 => e_1, ... a_n => e_n }, p_i | q_i を含むマッチの分岐 a_i を型検査する時、p_i | q_iのパターンは次の条件が満たされるとセマンティクス違反である。深さ de_s フラグメントが存在し、そのフラグメントの型が p_i | q_i の型へと単一化できないとき。

  2. パターンマッチの網羅性を検証に関して、p | q のパターンは p だけではなく q も含めて網羅性を検証する。あるコンストラクタについて、c(p | q, ..rest)c(p, ..rest) | c(q, ..rest) と同じ範囲を網羅性を確認する。パターンがネストしている場合も再帰的に適用される。

注意: コンストラクタという言葉で tuple struct patterns言及しているわけではない。 ここでは直積型のパターンのことを言及していて、enum variants, tuple structs, structs with named fields, arrays, tuples, そして slices が含まれる。

Dynamic semantics

  1. 深さ dc がコンストラクタであり、pq が任意のパターンで、restc の残りの要素とである時に、c(p | q, ..rest) に反する scrutinee な式(! 単語の意味が不明であるが、Google で検索した感じでは、直前の式から型が自明であるのに別の型でパターンマッチさせるような式は scrutinee と呼ばれる)に対するパターンマッチの動的なセマンティクスは c(p, ..rest) | c(q, ..rest) と同じと定義する。

  2. The dynamic semantics of pattern matching a scrutinee expression e_s against a pattern c(p | q, ..rest) at depth d where c is some constructor, p and q are arbitrary patterns, and rest is optionally any remaining potential factors in c, is defined as being the same as that of c(p, ..rest) | c(q, ..rest).

Implementation notes

静的と動的なセマンティクスに関して、CNF の c(p | q) から DNF の c(p) | c(q) へ(構文糖衣の)変換は常に valid になる。しかし、c(p | q) を単純に c(p) | c(q) として実装するのは最適ではないかもしれない。掛け算的にパターンが増えてしまうから。

match expr {
    (0 | 1, 0 | 1, 0 | 1, 0 | 1) => { ... },
}

DNF に展開すると以下のようになる。

match expr {
    | (0, 0, 0, 0)
    | (0, 0, 0, 1)
    | (0, 0, 1, 0)
    | (0, 0, 1, 1)
    | (0, 1, 0, 0)
    | (0, 1, 0, 1)
    | (0, 1, 1, 0)
    | (0, 1, 1, 1)
    | (1, 0, 0, 0)
    | (1, 0, 0, 1)
    | (1, 0, 1, 0)
    | (1, 0, 1, 1)
    | (1, 1, 0, 0)
    | (1, 1, 0, 1)
    | (1, 1, 1, 0)
    | (1, 1, 1, 1)
    => { ... },
}

解析をしたらもっと効率的になりそう。具体的な方法は rust compiler の実装にお任せ。

Drawbacks

  1. パーサーを書き直さなければならないこと。

Rationale and alternatives

RFC の motivation セクションで変更の意義は議論済み。

Syntax

| ぐらいしか一貫性のある演算子がなくて、実質的に選択の余地がなかった。

Precedence

すでに i @ p | j @ q が構文的に合法だから、i @ p | qi @ (p | q) と解釈する訳にはいかなかった。|@ より優先順位を上げると、既存のコードに破壊的な変更を避けられない。

集合論的な観点から、@| は提案している優先順位の方がよい。 なぜなら、a * b + c(a * b) + c として、p ∧ q ∨ r(p ∧ q) ∨ r として解釈されるのと類似性があるから。

Leading |

pat : .. | pat "|" pat ; にするか pat : .. | "|"? pat "|" pat ; にするかは選択の余地があった。 以下の4つの点で前者を採用した。

  1. 前者から後者へは変更可能だが、逆はそうではない。
  2. OCaml に先例があるから。
  3. 先行する | をマクロが生成する必要ないから、マクロに対する利点が疑わしい。 (! マクロで使う場合に、式と式の間にだけ | を挟み込むのが面倒かもしれないという議論だと思われる)
  4. パターン内での先行する | は見た目が汚い。

パターンがネストしているケースで、唯一先行する | を許すアドバンテージがある。

  1. syn のようなツールやライブラリで Rust の文法をパーズするのが**ほんの少しだけ*楽。

fn arguments

fn の引数内で p | q を許す。let との一貫性の話があるが、[RFC 2175] ですでにこの話はしている。

Macros and closures

unresolved セクションを見よ。

Prior art

CSS4 selectors

In CSS4, it is possible to write a selector div > *:matches(ul, ol) which is equivalent to div > ul, div > ol. The moral equivalent of this in Rust would be: Div(Ul | Ol).

Regular expressions

Most regular expression formalisms support at least the following operations (where a, b, and c are arbitrary regexes):

Formally, the the minimal formalism we need is:

pat : terminal | pat pat | pat "|" pat | "(" pat ")" ;

Given this formalism, it is then possible to encode a regex:

a(b | c)

By the law of distributivity, we can rewrite this as:

ab | ac

OCaml

This is supported in OCaml. An example from “Real World OCaml” is:

let is_ocaml_source s =
  match String.rsplit2 s ~on:'.' with
  | Some (_, ("ml" | "mli")) -> true
  | _ -> false

While OCaml will permit the following:

let foo =
  match Some(1) with
  | Some(1 | 2) -> true
  | _ -> false

the OCaml compiler will reject:

let foo =
  match Some(1) with
  | Some(| 1 | 2) -> true (* Note in particular the leading | in Some(..). *)
  | _ -> false

We have chosen to impose the same restriction as OCaml here with respect to not allowing leading | in nested pattern alternations.

F

A language which is quite similar to OCaml is F#. With respect to pattern matching, we may write:

let detectZeroOR point =
    match point with
    | (0, 0) | (0, _) | (_, 0) -> printfn "Zero found."
    | _ -> printfn "Both nonzero."

F# calls these “OR pattern”s and includes pattern1 | pattern2 in the pattern grammar.

Haskell

The equivalent proposal is currently being discussed for inclusion in Haskell.

Lisp

There is support for or-patterns in various lisp libraries.

Unresolved questions

  1. inferrable_param 内で top_pat ないし pat<allow_top_alt> を許可すべきか?つまり、|Ok(x) | Err(x)| のように丸かっこなしを許容するか?様子見するため決定は延期する。

  2. 異なる Rust のエディションで pat マクロフラグメント指定子は top_pat にマッチすべきか? ないし、現在 RFC で指定されているように pat<no_top_alt> にマッチすべきか? これも様子見するため決定は延期。

pat<no_top_alt> を可能な限り避けるメリットは、文法の一貫性と利用者をなるべく驚かせないようにすること。 マイナス点は曖昧さが残ることや closure と macro でバックトラックが必要になるかもしれないこと。

Comments

comments powered by Disqus