Вы пишете match десятки раз в день. Разбираете Option, матчите варианты enum, ловите диапазоны. Выглядит как switch из Си, только мощнее!

Но задумывались ли вы, что происходит, когда компилятор берёт ваш match с вложенными паттернами, гардами и привязками — и превращает его в машинный код? Там, внутри, лежит целый мир: деревья решений, таблицы переходов, niche-оптимизации, и иногда — один-единственный mov, где вы ожидали десяток сравнений.

Пройдем весь путь от паттерна до ассемблера.

match — это не switch

Первое заблуждение, от которого стоит избавиться сразу. match в Rust — это не синтаксический сахар над цепочкой if-else и не аналог switch из Си. Это другая конструкция с другой семантикой, и компилятор обрабатывает её принципиально иначе.

switch в Си работает с целыми числами. Один уровень вложенности, никаких деструктурирующих паттернов, никаких привязок. Компилятор либо строит таблицу переходов (jump table), либо генерирует цепочку сравнений.

match в Rust — это сопоставление с образцом. Паттерн может деструктурировать вложенные структуры, привязывать поля к переменным, проверять диапазоны, комбинировать несколько вариантов через |, и дополнительно фильтровать через гард (if condition). Один match может одновременно проверять дискриминант enum, значение вложенного поля, и привязывать результат к имени.

match event {
    Event::Click { x: 0..=100, y, button: Button::Left } => handle_left(y),
    Event::Click { button: Button::Right, .. } => show_menu(),
    Event::Key { code, modifiers } if modifiers.ctrl => shortcut(code),
    _ => {}
}

Одно выражение, а внутри: проверка дискриминанта (Click или Key), проверка диапазона (0..=100), проверка вложенного поля (Button::Left), привязка (y, code, modifiers), и гард (if modifiers.ctrl). Попробуйте развернуть это в if-else вручную, получится каша.

Шаг первый

Когда rustc видит match, первое, что он делает — разбирает синтаксис и строит HIR (High-level Intermediate Representation). На этом этапе match ещё выглядит узнаваемо: набор рукавов, каждый с паттерном, необязательным гардом и телом.

Но уже здесь начинается работа. if let и while let — это тоже match, просто с сахаром:

// это:
if let Some(x) = value {
    process(x);
}

// превращается в:
match value {
    Some(x) => { process(x); }
    _ => {}
}

let-else — аналогично:

// это:
let Some(x) = value else { return; };

// становится match-ем с двумя рукавами

Компилятор десахаризует всё это до единой конструкции. К моменту, когда код добирается до следующего этапа, никаких if let уже нет,только match.

Шаг второй

Перед тем как компилировать match, rustc проверяет, что все возможные значения покрыты. Это та самая ошибка «non-exhaustive patterns», которую вы видите, когда забыли обработать вариант enum.

Компилятор разбивает пространство всех возможных значений на «конструкторы». Для enum — это варианты. Для числа — диапазоны. Для кортежа — конструктор кортежа с полями.

Дальше он рекурсивно проверяет: для каждого конструктора, покрыты ли все возможные комбинации вложенных полей.

enum Color { Red, Green, Blue }

match color {
    Color::Red => {},
    Color::Green => {},
    // ошибка: Color::Blue не покрыт
}

Алгоритм знает, что Color имеет три конструктора, видит два и сообщает, какого не хватает. Для вложенных паттернов он работает рекурсивно: если вы матчите (Color, bool), он проверяет все комбинации 3 × 2 = 6 вариантов.

Отдельно стоит проверка недостижимости. Если паттерн перекрывается предыдущим, rustc выдаёт предупреждение «unreachable pattern». Это тот же алгоритм, просто в обратную сторону: «может ли новый паттерн сматчить что-то, чего не поймали предыдущие?»

Вся эта проверка происходит на этапе компиляции.

Шаг третий: MIR — здесь match умирает

На этапе понижения до MIR (Mid-level Intermediate Representation) выражение match перестаёт существовать. Буквально, ведь в MIR нет конструкции «match», зато есть базовые блоки, связанные условными и безусловными переходами.

Компилятор берёт match и превращает его в дерево решений (decision tree). Идея в том, что вместо того чтобы проверять каждый рукав целиком (линейный поиск), компилятор строит дерево проверок, где каждый узел — одна простенькая проверка.

Вот простой пример:

enum Shape {
    Circle(f64),
    Rect(f64, f64),
    Triangle(f64, f64, f64),
}

match shape {
    Shape::Circle(r) if r > 0.0 => area_circle(r),
    Shape::Rect(w, h) => area_rect(w, h),
    Shape::Circle(r) => zero(),  // r <= 0.0 (гард не прошёл выше)
    Shape::Triangle(a, b, c) => area_triangle(a, b, c),
}

Наивный подход — проверять рукава сверху вниз: «это Circle? Нет. Это Rect? Нет. Это Circle ещё раз? Нет. Это Triangle? Да!». Для каждого элемента полная проверка. Если у вас десять вариантов и десять рукавов, в худшем случае — сто проверок.

Компилятор делает круче. Он строит дерево:

Проверить дискриминант shape:
├── Circle → проверить гард (r > 0.0):
│   ├── true  → area_circle(r)
│   └── false → zero()
├── Rect → area_rect(w, h)
└── Triangle → area_triangle(a, b, c)

Дискриминант проверяется один раз. Для Circle — одна дополнительная проверка гарда. Никаких повторных проверок дискриминанта.

В MIR это превращается в набор базовых блоков:

bb0: switchInt(discriminant(shape)) -> [0: bb1, 1: bb2, 2: bb3]
bb1: // Circle
     _r = (shape as Circle).0
     switchInt(_r > 0.0) -> [true: bb4, false: bb5]
bb2: // Rect
     _w = (shape as Rect).0
     _h = (shape as Rect).1
     area_rect(_w, _h) -> bb6
bb3: // Triangle
     ...
bb4: area_circle(_r) -> bb6
bb5: zero() -> bb6
bb6: // продолжение

switchInt — ключевая инструкция MIR. Она берёт целое число (дискриминант, значение, результат сравнения) и переходит к нужному блоку. Паттерн-матчинг превращается в граф потока управления.

Посмотреть MIR можно так:

cargo rustc -- --emit=mir
# или на playground: Tools → MIR

Рекомендую.

LLVM и рождение машинного кода

Из MIR код спускается в LLVM-IR, а оттуда в машинный код. Тут начинается самое прикольное, потому что LLVM принимает собственные решения о том, как реализовать switchInt.

У LLVM три основные стратегии для конструкции switch:

1. Таблица переходов (jump table). Классика. Компилятор создаёт массив адресов — по одному на каждый вариант — и прыгает по индексу. Один mov для загрузки адреса, один непрямой jmp. Работает, когда значения дискриминантов плотные (0, 1, 2, 3, …) и их достаточно много.

; match на enum с вариантами 0..5
mov   eax, [rdi]            ; загрузить дискриминант
lea   rcx, [rip + .LJTI0_0] ; адрес таблицы переходов
movsxd rax, [rcx + 4*rax]   ; смещение из таблицы
add   rax, rcx               ; абсолютный адрес
jmp   rax                    ; прыжок

.LJTI0_0:
  .long .LBB0_1 - .LJTI0_0  ; Circle
  .long .LBB0_2 - .LJTI0_0  ; Rect
  .long .LBB0_3 - .LJTI0_0  ; Triangle
  .long .LBB0_4 - .LJTI0_0  ; Point
  .long .LBB0_5 - .LJTI0_0  ; Line

Быстро: O(1) по количеству вариантов. Но есть нюансик (куда без них), непрямой jmp хуже предсказывается процессором, чем прямой условный переход. Для enum с тремя вариантами таблица переходов может быть медленнее, чем пара cmp + je.

2. Цепочка сравнений (linear sequence). Для малого числа вариантов LLVM генерирует обычные cmp + je:

; match на enum с двумя вариантами
cmp   eax, 0
je    .LBB_some
jmp   .LBB_none

Быстро для двух-трёх вариантов. Предсказатель переходов справляется отлично, но линейно растёт с числом вариантов.

3. Двоичный поиск (binary search / decision tree). Для разреженных значений (например, match по u32 с вариантами 1, 50, 100, 9999) LLVM строит дерево сравнений:

cmp   eax, 50
jl    .check_low
jg    .check_high
jmp   .LBB_50
.check_low:
cmp   eax, 1
je    .LBB_1
jmp   .LBB_default
.check_high:
cmp   eax, 100
je    .LBB_100
cmp   eax, 9999
je    .LBB_9999
jmp   .LBB_default

Логарифмическое время. Используется, когда значения разбросаны и таблица переходов была бы слишком большой (и в основном пустой).

4. Lookup table. Если каждый рукав match возвращает значение (а не выполняет сложный код), LLVM может заменить весь match на чтение из таблицы:

fn to_score(grade: Grade) -> u32 {
    match grade {
        Grade::A => 5,
        Grade::B => 4,
        Grade::C => 3,
        Grade::D => 2,
        Grade::F => 1,
    }
}

LLVM видит: дискриминант 0-4, каждый рукав — константа. Генерирует:

mov   eax, [rip + .Lswitch.table + 4*edi]  ; одно чтение из таблицы
ret

.Lswitch.table:
  .long 5, 4, 3, 2, 1

Ни одного сравнения и и одного перехода. Один mov + ret. Тут match становится быстрее, чем любая цепочка if-else потому что LLVM умеет распознавать такие паттерны и заменять их табличным доступом.

Дискриминант: как enum хранит «кто я»

Чтобы match по enum работал, нужно откуда-то взять информацию о варианте. Эта информация — дискриминант.

Для простых enum без данных дискриминант — просто целое число:

enum Direction { North, South, East, West }

В памяти Direction занимает 1 байт (тип u8): значения 0, 1, 2, 3. match сводится к проверке одного байта.

Для enum с данными — сложнее:

enum Value {
    Int(i64),
    Float(f64),
    Text(String),
}

Value хранит дискриминант + данные самого большого варианта. На x86-64: 1 байт дискриминант + 7 байт выравнивания + 24 байта (размер String) = 32 байта. Все варианты занимают одинаковый объём — по размеру самого большого. Int(i64) платит за Text(String).

match по Value — это:

1. Загрузить байт дискриминанта (смещение 0)

2. Сравнить с вариантами

3. В зависимости от варианта — интерпретировать оставшиеся байты как i64, f64 или String

На уровне MIR третий шаг — это (value as Int).0 или (value as Text).0. На уровне LLVM — bitcast или GEP (GetElementPtr) по нужному смещению. На уровне ассемблера — обращение по адресу со смещением. Никакой рантайм-проверки типов, она уже произошла.

Niche-оптимизация: когда дискриминанта нет

осмотрите:

use std::mem::size_of;

assert_eq!(size_of::<&u32>(), 8);            // обычная ссылка: 8 байт
assert_eq!(size_of::<Option<&u32>>(), 8);     // Option ссылки: тоже 8 байт!

Option<&T> занимает ровно столько же, сколько &T. Где дискриминант? Нигде, его нет. Это niche-оптимизация (null pointer optimization, NPO — её частный случай).

Ссылка &T в Rust гарантированно ненулевая. Нулевой указатель — невалидное значение. Компилятор знает об этом и использует ноль для хранения None. Если указатель нулевой — это None. Если ненулевой — Some(&T).

match по Option<&T> на уровне ассемблера:

test  rdi, rdi    ; rdi == 0?
je    .none       ; да → None
; нет → Some, rdi содержит ссылку

Ни дискриминанта, ни смещений. test проверяет, ноль ли значение — и всё.

Это работает не только для ссылок.

NonZeroU32 гарантирует, что значение не ноль, и Option<NonZeroU32> занимает 4 байта вместо 8. bool может быть только 0 или 1 — и Option<bool> использует 2 как None, помещаясь в 1 байт.

Niche-оптимизация рекурсивна. Option<Option<&T>> — тоже 8 байт. Внутренний Option<&T> использует ноль для None. Внешний Option — какое-то другое нишевое значение. Компилятор делает это автоматически, пока есть неиспользованные битовые комбинации.

Гарды: статика кончается

Паттерн в match — конструкция времени компиляции. Компилятор знает все возможные формы паттернов и может построить оптимальное дерево решений. Но гарды (if condition) — другое. Они вычисляются в рантайме, и компилятор не может их оптимизировать как часть паттерна.

match value {
    Some(x) if x > 100 => big(x),
    Some(x) => small(x),
    None => nothing(),
}

Компилятор сначала проверяет паттерн (Some(x) — проверка дискриминанта), потом — гард (x > 100). Если гард не прошёл, управление не переходит к телу, а откатывается к следующему рукаву. Это называется backtracking: «я сматчил паттерн, но гард сказал нет — иду дальше».

В MIR это выглядит как дополнительное ветвление:

bb0: switchInt(discriminant(value)) -> [1: bb1, 0: bb3]  // Some или None
bb1: _x = (value as Some).0
     switchInt(_x > 100) -> [true: bb2, false: bb4]       // гард
bb2: big(_x) -> bb5                                        // гард прошёл
bb4: small(_x) -> bb5                                      // гард не прошёл, следующий рукав
bb3: nothing() -> bb5                                      // None

Гарды делают дерево решений сложнее, потому что создают точки, где после успешного матча всё равно можно вернуться назад. Компилятор должен учитывать это при построении дерева, и иногда вынужден дублировать проверки.

Если гард проверяет что-то, что можно выразить паттерном — выразите паттерном. Some(0..=100) лучше, чем Some(x) if x <= 100, потому что диапазонный паттерн встраивается в дерево решений и может быть оптимизирован.

Паттерны по вложенным структурам

Вы можете матчить произвольно вложенные структуры:

match ast {
    Expr::Binary {
        op: Op::Add,
        left: box Expr::Literal(a),
        right: box Expr::Literal(b),
    } => Expr::Literal(a + b),  // свёртка констант
    _ => ast,
}

Компилятор разворачивает это в последовательность проверок:

1. Проверить дискриминант ast — Binary?

2. Проверить поле op — Add?

3. Загрузить left, проверить дискриминант — Literal?

4. Загрузить right, проверить дискриминант — Literal?

Четыре проверки, вложенных друг в друга. Каждая — switchInt в MIR, cmp + je в ассемблере. Компилятор строит дерево в глубину, разворачивая вложенность паттерна в цепочку проверок.

Если у вас несколько рукавов, которые начинаются одинаково, компилятор объединяет общие проверки:

match ast {
    Expr::Binary { op: Op::Add, left, right } => optimize_add(left, right),
    Expr::Binary { op: Op::Mul, left, right } => optimize_mul(left, right),
    Expr::Binary { op, left, right } => default_binary(op, left, right),
    _ => ast,
}

Дискриминант Binary проверяется один раз. Потом — switchInt по op. Никаких повторных проверок «а это точно Binary?». Алгоритм построения дерева решений специально оптимизирован для этого, он находит «столбец» с наибольшей разделяющей способностью и начинает с него.

match по строкам и слайсам

Для целых чисел и enum всё красиво: дискриминанты, таблицы переходов, бинарный поиск. А что с типами, где «матчинг» — это не одно сравнение?

match s.as_str() {
    "GET" => handle_get(),
    "POST" => handle_post(),
    "PUT" => handle_put(),
    "DELETE" => handle_delete(),
    _ => not_found(),
}

Строки — это не целые числа. У них нет дискриминанта,компилятор не может построить таблицу переходов по адресу. Вместо этого match по строке превращается в цепочку вызовов PartialEq::eq:

if s == "GET" { ... }
else if s == "POST" { ... }
else if s == "PUT" { ... }
else if s == "DELETE" { ... }
else { ... }

Линейный поиск. На четырёх строках это вообще не проблема, вот уже на сотне — проблема.

Но LLVM иногда хитрит. Если строки одной длины, он может сначала проверить длину, потом сравнить содержимое. Если длины разные — может использовать длину как первичный фильтр.

Если вам нужен быстрый match по строкам в горячем пути — используйте phf или ручной HashMap.

Аналогично с паттернами по слайсам:

match slice {
    [first, .., last] => println!("{first} ... {last}"),
    [single] => println!("{single}"),
    [] => println!("empty"),
}

Компилятор генерирует проверку длины слайса, потом обращения по индексам. Это последовательные cmp + загрузки из памяти.

Or-паттерны и привязки

Or-паттерны (|) выглядят невинно:

match color {
    Color::Red | Color::Blue => cool_colors(),
    Color::Green => warm_color(),
}

Для простых случаев компилятор просто добавляет несколько меток к одному блоку. Но когда внутри есть привязки — начинается подобное:

match event {
    Event::Click(x, y) | Event::Tap(x, y) => handle(x, y),
    _ => {}
}

Rust требует, чтобы каждый подпаттерн в | привязывал одни и те же имена одних и тех же типов. Компилятор должен убедиться, что x и y одинаково доступны из обоих вариантов, и сгенерировать код, который присваивает им значения независимо от того, какой подпаттерн сработал.

В MIR это обычно выглядит как два пути, которые сходятся в одну точку, где привязки уже присвоены:

bb0: switchInt(discriminant(event)) -> [0: bb1, 1: bb2, ...]
bb1: _x = (event as Click).0; _y = (event as Click).1 -> bb3
bb2: _x = (event as Tap).0; _y = (event as Tap).1 -> bb3
bb3: handle(_x, _y)

Два пути входа, один выход.

Что LLVM делает после MIR

Всё, что компилятор Rust нагенерировал в MIR, после понижения до LLVM-IR проходит через десятки оптимизационных проходов. И некоторые из них влияют на код, порождённый match.

SimplifyCFG — объединяет избыточные базовые блоки, убирает переходы на переходы, схлопывает тривиальные ветвления. Если два рукава match ведут к одному и тому же коду, они сольются.

InstCombine — упрощает отдельные инструкции. Может заменить switch с двумя ветками на один select (условный выбор без перехода):

match flag {
    true => 1,
    false => 0,
}

Превращается не в cmp + je, а в:

movzx eax, dil   ; просто расширить bool до i32
ret

Или даже:

; match x { 0 => 10, 1 => 20, 2 => 30 } →
lea eax, [10 + 10*rdi]  ; одна арифметическая инструкция

LLVM умеет распознавать арифметические зависимости между вариантами и заменять весь switch одной формулой.

Vectorization. Если match внутри цикла и паттерны достаточно простые, LLVM может векторизировать цикл, обрабатывая несколько значений одновременно.

Dead branch elimination. Если LLVM может доказать, что конкретный рукав недостижим (например, через анализ диапазонов), он удалит соответствующий код.

Как писать match, чтобы компилятор вас любил

Всё, что я рассказал выше, сводится к простам вещам.

Ставьте самые частые варианты первыми. Для цепочек сравнений (малое число вариантов) порядок рукавов может влиять на производительность. Первый рукав проверяется первым. Если он срабатывает в 90% случаев — остальные проверки не выполняются.

Предпочитайте паттерны гардам. Some(0..=100) лучше, чем Some(x) if x <= 100. Паттерн встраивается в дерево решений и может быть объединён с другими проверками. Гард — отдельный рантайм-вызов с backtracking.

Если match возвращает значение — пусть возвращает. LLVM отлично умеет превращать match по enum, где каждый рукав — константа или простое выражение, в lookup table. Не засоряйте рукава побочными эффектами без необходимости.

Для горячих путей по строкам — не используйте match. Используйте phf, хеш-таблицу или хотя бы предварительную проверку длины. match по строке — линейный поиск.

Niche-оптимизация работает автоматически. Используйте NonZero* типы, ссылки, Box — и Option вокруг них будет бесплатным. Не нужно городить свои флаги «есть значение / нет значения».

Самое ценное, что можно унести — привычку смотреть, что получилось на выходе.

Размещайте облачную инфраструктуру и масштабируйте сервисы с надежным облачным провайдером Beget.

Эксклюзивно для читателей Хабра мы даем бонус 10% при первом пополнении.