Завтра (технически сегодня) будет пост про Rust

#prog #abnormalprogramming

"Змейка" на клавиатуре с подсветкой.

Видеодемонстрация
Статья с разбором реализации
Перевод на Хабре

#prog #rust #моё

В Rust есть такая удобная вещь, как сопоставление с образцом (pattern matching), и она работает в том числе и для строк. К сожалению, оно позволяет сопоставлять только строки целиком, но не по частям. В частности (no pun intended), match не позволяет разделить строку на некоторый фиксированный префикс и всё остальное.

Или всё же позволяет? В конце-концов, можно написать так:

match str_value.as_bytes() {
[b'p', b'r', b'e', b'f, b'i', b'x', rest @ ..] => {}
_ => {}
}

, и тут даже будет помогать компилятор — он подскажет нам, если мы будем дважды проверять один и тот же префикс. Но тут есть и недостатки: остаток строки (rets во второй строчке) — не &str, а &[u8], ну и, конечно, это довольно неудобно писать. Первый недостаток отчасти перекрывается str::get_unchecked/std::str::from_utf8_unchecked — отчасти, поскольку в паттерн байта можно написать и часть многобайтового символа, а вот второй недостаток обойти сложнее. В идеале мы бы хотели написать матч в виде сопоставления части строки, чтобы потом он скомпилировался в примерно такой же код, как наверху — чтобы к нему могли быть применены те же оптимизации, что и к обычному матчу, и чтобы получить выгоду от проверки полноты покрытия — но это довольно существенное вмешательство в синтаксис, требующее написания процедурного макроса, написание которого отводится читателю в качестве самостоятельного упражнения.

Если же ослабить требование максимальной эффективности генерируемого кода (серьёзно, Rust и так достаточно быстрый), то можно обойтись более слабыми macro_rules!. Как можно переписать сопоставление с префиксом на обычные функции? Один из способов — это написать match, в котором значение ни с чем не сопоставляется, а условие "начинается с заданного префикса" задаётся в охранном выражении (guard clause). Сказано — сделано:

macro_rules! prefixes {
(match $value:ident {
$($prefix:literal.. => $arm:expr,)*
_ => $catch_all:expr $(,)?
}) => {
match $value {
$(x if x.starts_with($prefix) => $arm,)*
_ => $catch_all,
}
}
}

Ну и давайте сделаем какую-нибудь функцию, которая использует этот макрос:

fn use_prefixes(s: &str) -> String {
prefixes!(match s {
"foo".. => s.to_string(),
"bar".. => [s, s].concat(),
_ => String::new(),
})
}

fn main() {
let inputs = [
"foobar",
"barfoo",
"overall",
];

for input in &inputs[..] {
println!("{:?}", use_prefixes(input));
}
}

Но, погодите-ка, так потеряли одно из преимуществ компилятора: проверку полноты покрытия! Как мы можем её восстановить? Пойдём ленивым путём: сделаем свою функцию, в которой будем матчить по переданным строкам и позволим компилятору сделать работу за нас. Однако возникает вопрос, где эту функцию хранить? Простейший способ добиться этого — обернуть весь итоговый match в один блок и сделать внутри этого блока функцию. Так как функция не будет использована, она будет помечена #[allow(dead_code)], а на внутренний match повесим #[warn(unreachable_patterns)], чтобы предупреждения компилятора были даже в том случае, если они по каким-то причинам выключены на верхнем уровне:

macro_rules! prefixes {
(match $value:ident {
$($prefix:literal.. => $arm:expr,)*
_ => $catch_all:expr $(,)?
}) => {{
#[allow(dead_code)]
fn non_repeating() {
#[warn(unreachable_patterns)]
match "" {
$($prefix => (),)*
_ => (),
}
}
match $value {
$(x if x.starts_with($prefix) => $arm,)*
_ => $catch_all,
}
}}
}

Попробуем оставить в use_prefixes одинаковые префиксы:

fn use_prefixes(s: &str) -> String {
prefixes!(match s {
"foo".. => s.to_string(),
"foo".. => [s, s].concat(), // <--
_ => String::new(),
})
}

Что же скажет компилятор?

warning: unreachable pattern
--> src/main.rs:10:19
|
10 | $($prefix => (),)*
| ^^^^^^^
...
22 | / prefixes!(match s {
23 | | "foo".. => s.to_string(),
24 | | "foo".. => [s, s].concat(),
25 | | _ => String::new(),
26 | | })
| |______- in this macro invocation
|
note: the lint level is defined here
--> src/main.rs:8:20
|
8 | #[warn(unreachable_patterns)]
| ^^^^^^^^^^^^^^^^^^^^
...
22 | / prefixes!(match s {
23 | | "foo".. => s.to_string(),
24 | | "foo".. => [s, s].concat(),
25 | | _ => String::new(),
26 | | })
| |______- in this macro invocation
= note: this warning originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)

Окей, сообщение об ошибке могло бы быть и получше, но компилятор предупреждает нас о баге.

Можем ли мы улучшить результат? Безусловно: сейчас мы можем сматчить префикс, но не получаем остаток строки после него! Мы можем одновременно проверить, что строка начинается с указанного префикса, и получить остаток строки при помощи str::strip_prefix. Генерировать код при помощи такой функции несколько более хлопотно, поскольку при этом вместо match придётся писать связанные в цепочку if let, но задача решаема: для каждого префикса мы пытаемся отрезать префикс от строки, и, если это не выходит, пробуем следующий, а если не сработал ни один из префиксов, то исполняем ветку $catch_all:

macro_rules! cut_prefixes {
(match $value:ident {
$($prefix:literal ..= $rest:ident => $arm:expr,)*
_ => $catch_all:expr $(,)?
}) => {{
#[allow(dead_code)]
fn non_repeating() {
#[warn(unreachable_patterns)]
match "" {
$($prefix => (),)*
_ => (),
}
}
$(if let Some($rest) = $value.strip_prefix($prefix) {
$arm
} else)* {
$catch_all
}
}}
}

Напишем очередную малоосмысленную функцию, которая использует этот макрос:

fn use_cut_prefixes(s: &str) -> String {
    cut_prefixes!(match s {
        "foo"..=rest => rest.to_string(),
        "bar"..=tail => [tail, tail].concat(),
        _ => String::new(),
    })
}

Функция main останется той же. Программа выдаёт:

"bar"
"foofoo"
""

То есть всё как и ожидалось. Защита от повторяющихся префиксов также работает.

Есть, однако ещё один аспект match, который нельзя использовать внутри наших макросов: охранные выражения на ветках! Можем ли мы интегрировать их? В случае с prefixes — безусловно: наш макрос в итоге в конечном счёте разворачивается в те же охранные выражения, в которые несложно добавить ещё одно условие. Надо лишь учесть, что эта часть синтаксиса опциональна:

macro_rules! prefixes {
    (match $value:ident {
        $($prefix:literal .. $(if $condition:expr)? => $arm:expr,)*
        //         это новое ^^^^^^^^^^^^^^^^^^^^^^
        _ => $catch_all:expr $(,)?
    }) => {{
        /* функция для отлова одинаковых префиксов */
        match $value {
            $(x if x.starts_with($prefix) $(&& $condition)? => $arm,)*
            // вставляем условие          ^^^^^^^^^^^^^^^^^
            // из if clause, если оно есть
            _ => $catch_all,
        }
    }}
}

И да, если в use_prefixes добавить ветку с if clause, то оно будет работать — с вашего позволения, я это опущу.

А вот что делать с cut_prefixes? В идеале нам бы хотелось просто взять и добавить к if let булево условие, но соответствующий RFC даже не принят, так что придётся выкручиваться. Один из возможных путей — это использовать тот же подход, что и в use_prefixes: сделать фиктивный match и поместить всё в охранные выражения. Доставать префикс тогда придётся при помощи split_at:

macro_rules! cut_prefixes {
    (match $value:ident {
        $($prefix:literal..=$rest:ident $(if $cond:expr)? => $arm:expr,)*
        //                  новая часть ^^^^^^^^^^^^^^^^^
        _ => $catch_all:expr $(,)?
    }) => {{
        /* проверочная функция, бла-бла */
        match $value {
            $(x if x.starts_with($prefix) $(&& $cond)? => {
                let (_, $rest) = x.split_at($prefix.len());
                $arm
            },)*
            _ => $catch_all,
        }
    }}
}

И оно даже работает!

В заключение мне хотелось бы рассмотреть ограничения продемонстрированных подходов:

* в силу принципа организации генерируемого кода (цепочка условий против набора веток в ванильном матче) этот код почти наверняка хуже оптимизируется компилятором
* из-за ограничений macro_rules! значение, по которому происходит разбор, не может быть выражением (expr), а лишь идентификатором
* синтаксически макросы всегда требуют запятых в конце веток match, даже не смотря на то, что они не опциональны в match в тех случаях, когда ветки обрамлены в фигурные скобки
* паттерн для отлова всех необработанных случаев может быть только _ вместо также произвольного идентификатора в match
* в охранных выражениях в cut_prefix нельзя использовать имя, привязываемое к остатку строки
* вариант cut_prefixes, поддерживающий охранные выражения, менее эффективен — в подобном самодельном cut_prefix остаётся путь исполнения, ведущий к панике, даже на уровне оптимизации -O3. Это можно решить двумя способами:

1. str::split_at_unchecked — но это требует unsafe и потому не будет работать в кодовых базах с #![forbid(unsafe_code)];
2. Сделать функцию с атрибутом #[doc[hidden)] со str::split_at_unchecked внутри, не пометив её unsafe, и вызывать её в генерируемом коде — но это грязный хак, который нарушает гарантии safe Rust.

Как всегда, весь код в гисте.

P. S.: разумеется, ничто не мешает сделать похожие штуки для матчинга по суффиксам

#rust #gamedev

Широко известный в узких русско-расто-, расто-геймедево- и русско-расто-геймдево- кругах Андрей "@ozkriff" Лесников наконец-то завёл в Telegram свой блог: @ozkriff_games. Некоторые скажут, что для #blogrecommendation это рановато, с учётом того, что там пока лишь 3 сообщения, но как человек, знакомый с Андреем, я выдаю ему большой кредит доверия. Буду ждать крутых постов! ✊

P. S.: а ещё он работает в JetBrains

Мне аж интересно стало. Кто эти двое с возрастом 60+?

Обсуждал с Доге, что в Scala можно это сделать на кастомных экстракторах, а оказалось, это уже есть: https://t.iss.one/lilfunctor/209

Лёгким росчерком клавиатуры @poslegm (автор @lilfunctor) привлёк внимание к моему каналу, из-за чего число подписчиков наконец перевалило за шесть сотен. Спасибо!

Луковые кольца в Burger King — туфта