#prog #article

Системы типов #java и #scala являются unsound. Подробности в статье.

TL;DR:
Программа определяет тип class Constrain<A, B extends A> {} и метод upcast:

static class Bind<A> {
<B extends A>
A upcast(Constrain<A,B> constrain, B b) {
return b;
}
}

Этот метод просто апкастит значение типа B в значение типа A, используя значение типа Constrain<A, B> как материальное свидетельство того, что B действительно является подтипом A. К сожалению, ничто не мешает в качестве значения этого типа использовать null, что ломает логику системы типов, которая полагается на этот факт, а использования wildcard capture позволяет при помощи Constrain установить отношение субтипизации между двумя произвольным типами. Результат? Комбинация null-гого Constrain и upcast позволяет перевести значение любого типа в значение любого типа. Фактически — аналог std::mem::transmute, но без каких либо небезопасных фич и с корректно типизированным кодом.

И эта ошибка оставалась незамеченной 12 лет. А кто-то ещё говорит, что null — хорошая идея.

Коллега, находясь в отпуске, помогает в рабочем чате.

xxx: Имярек, выйди и зайди в отпуск нормально

#трудовыебудни

Чёртов Proton

Скачивание веб-страниц в один HTML файл. #решения

Нашёл такое расширение для браузера. Стили, скрипты, шрифты, картинки, видео тупо инлайнятся в html через data:image + base64 или напрямую через <style>, <script>. Теперь можно перестать делать скриншоты всей страницы или скачивать её в pdf. Так же это расширение позволяет скачивать только выделенную часть страницы.

Расширение: https://github.com/gildas-lormeau/SingleFile (там нормальное описание и ссылка на версию для каждого браузера).

Оригинальные настройки удаляют со страницы JS, скрытые элементы, неиспользуемые стили, не скачивают видео итд. Так что покопайтесь в настройках чтобы получать нужный вам результат.

Я проверил на своей последней статье, работает отлично, в комментах приложу html файл, он работает даже на телефоне.

Вдохновлено https://t.iss.one/bpblog/1219

Наконец-то дошли руки пройти Serena, которую я запускал в последний раз... 6 лет назад.

И знаете что?

Я обескуражен. Весьма.

Ворую чужие #prog #meme-ы

#prog #rust #моё

Тут Даня рассказывает о том, как можно уменьшить время на критические секции с мапой в многопоточном контексте, расчитывая хэш для поиска ключа заранее. Бенчмарк, который он сделал, показывает, что CPU time от подобных манипуляций остаётся практически то же, а вот wall time становится меньше, что в итоге уменьшает задержку (в смысле latency). Советую почитать, пост неплохой.

Но я несколько отвлёкся. В том же посте Даниил сокрушается, что подобная операция (поиск при помощи хэша) есть в коллекциях Abseil, но не в различных стандартных библиотеках языков, в том числе C++ и Rust. И вот тут Даня не совсем прав.

У HashMap из стандартной библиотеки Rust есть методы raw_entry{, mut}, которые предоставляют API для низкоуровневого манипулирования мапой, в том числе и поиск при помощи предвычисленного хэша. Единственная проблема заключаются в том, что эти методы... Ещё не стабилизированы. И, насколько я могу понять по обсуждениям в tracking issue, сейчас там обсуждается вопрос, должно ли это API вообще существовать в том виде, в котором оно есть сейчас. С другой стороны, HashMap из стандартной библиотеки сейчас не более, чем обёртка над hashbrown::HashMap, у которой эти методы есть, так что мы можем построить поверх неё аналог LockedHashMap из оригинального поста, а заодно осветить парочку моментов из стандартной библиотеки Rust, которые незаслуженно обделяют вниманием.

Для начала запишем определение:

use hashbrown::HashMap;

use std::{borrow::Borrow, hash::{BuildHasher, Hash, Hasher}, sync::{Mutex, MutexGuard, PoisonError}};

struct LockedHashMap<K, V, S> {
inner: Mutex<HashMap<K, V, S>>,
}

Расписывать конструкторы я не буду, они тривиальны. Методы LockedHashMap будут начинать свою работу со взятия блокировки на inner, но... Метод .lock() возвращает Result. Что с этим делать? И почему мы импортируем PoisonError?

Для начала разберёмся, почему Mutex::lock в принципе возвращает Result. Дело в том, что обычно программисты, пишущие код с блокировками, не пытаются расчитать поведение кода в том случае, если код запаникует, пока блокировка удерживается. С safe Rust это не может привести к проблемам с памятью, но прерывание обычного потока управления может оставить значение, защищаемое блокировкой, в логически неконсистентном состоянии. Если программист рассчитывает на то, что какие-то инварианты могут поддерживаться, но при этом временно их нарушает во время блокировок, то паника во время удерживания блокировки может эти логические инварианты сломать.

Дизайнеры стандартной библиотеки Rust решили, что это достаточно распространённая и при этом неочевидная ошибка, чтобы ограждать от неё в стандартной библиотеке. В итоге мьютекс из стандартной библиотеки может находиться не только в состоянии "разблокирован" или "заблокирован", но и в состоянии "отравлен". Когда MutexGuard (то, что реально возвращается в Ok-варианте из Mutex::lock) дропается, он не только разблокировывает связанный мьютекс, но и проверяет, паникует ли текущий поток. Если это так, то он помечает мьютекс как отравленный. Вызов Mutex::lock проверяет, является ли мьютекс отравленным, и если это так, то возвращает Err(PoisonError). Так как самое ленивое, что может сделать программист с результатом вызова .lock() — это вызвать .unwrap(), то в случае, если один из потоков, работающий с мьютексом, запаниковал — и, возможно, оставил защищённый мьютексом объект в логически неконсистентном состоянии — остальные потоки, использующие этот же мьютекс, также паникуют и, таким образом, не имеют возможности наблюдать состояние со сломанными инвариантами.

Такое дизайн-решение, вообще говоря, не бесспорное — и, скажем, в parking-lot метод lock не возвращает Result. Но что делать, если мы таки заботимся о соблюдении инвариантов? Так как отравление мьютекса — это защита от логических ошибок, а не от проблем с memory safety, lock на отравленном мьютексе таки захватывает его, и при помощи PoisonError::into_inner внутренний MutexGuard всё же можно достать. В общем, для упрощения остальных методов выделим LockedHashMap::lock_poisonless:

fn lock_poisonless(&self) -> MutexGuard<'_, HashMap<K, V, S>> {
self.inner.lock().unwrap_or_else(PoisonError::into_inner)
}

Теперь немного подумаем о том, что должен возвращать метод find_with_hash. Обычный HashMap::get возвращает ссылку на значение, но нам это не очень хорошо подходит, поскольку, пока ссылка жива, мы должны удерживать и блокировку, что прямо противоречит нашей цели: сокращение длительности критических секций. Я решил, что в данной ситуации будет разумно это значение клонировать. Итого метод выглядит так:

fn find_with_hash<Q>(&self, hash: u64, key: &Q) -> Option<V>
where
    Q: ?Sized + Eq,
    K: Borrow<Q> + Hash + Eq,
    V: Clone,
{
    self.lock_poisonless()
        .raw_entry()
        .from_key_hashed_nocheck(hash, key) // смотри-ка, хэш не считается!
        .map(|(_k, v)| v.clone())
}

insert пишется без проблем:

fn insert(&self, key: K, value: V) -> Option<V>
where
    K: Hash + Eq,
    S: BuildHasher,
{
    self.lock_poisonless().insert(key, value)
}

Кстати, тут также можно было бы ускорить поиск при помощи предрасчитанного хэша, но Даниил решил почему-то этого не делать. Гм... А давайте сделаем и версию с готовым хэшем:

fn insert_with_hash(&self, hash: u64, key: K, value: V) -> Option<V>
where
K: Hash + Eq,
S: BuildHasher,
{
use hashbrown::hash_map::RawEntryMut::*;

match self
.lock_poisonless()
.raw_entry_mut()
.from_key_hashed_nocheck(hash, &key)
{
Vacant(e) => {
e.insert(key, value);
None
}
Occupied(mut e) => Some(std::mem::replace(e.get_mut(), value)),
}
}

Так, требуемый функционал реализован. А теперь поговорим немного о том, как же эти самые хеши считать. В C++ задача хэширования возложена на специализации структуры std::hash. Для тех типов, которые умеют хэшироваться, соответствующая специализация имеет реализацию operator(), которая позволяет вызвать std::hash как функцию. К чему это я? В С++ хэш стандартной библиотеки имеет по одной конкретной хэш-функции на тип. В Rust же ситуация... Несколько сложнее.

В стандартной библиотеке есть трейт std::hash::Hash (и derive-макрос для него), который определяет единственный (необходимый) метод hash. Так что же, хэш однозначно определяется типом? Не совсем. Метод hash — обобщённый, и принимает аргументами &self и мутабельную ссылку на значение, реализующее трейт std::hash::Hasher. Этот трейт, в свою очередь, предоставляет набор методов навроде write_u32 для хэширования примитивов и write для хэширования слайса байт, а также метод finish, который возвращает значение типа u64 — вычисленный хэш. Таким образом, хэширование типа выражено в терминах методов Hasher — и в этом смысле хэш-функция зависит от типа, ибо это внутри реализации Hash решается, в каком порядке поля будут хэшированы — но конкретная реализация хэш-функции зависит от типа, реализующего Hasher. На практике это означает, что вместо того, чтобы довольствоваться некоторой стандартной хэш-функцией по умолчанию (которой для примитивных численных типов, согласно стандарту C++, вполне может быть функция идентичности), программист может выбрать хэш-функцию, которая наилучшим образом подходит для имеющихся данных — и при этом избежать выписывания этой хэш-функции для всех необходимых типов вручную (привет, 0xd34df00d).

Однако в случае хэш-мапы возникает новая задача: для подсчёта хэша нового элемента нам нужен новый, свежий хэшер. Но откуда его взять? Эта задача в стандартной библиотеке Rust делегирована третьему трейту: std::hash::BuildHasher. Его единственный метод build_hasher должен возвращать значение типа BuildHasher::Hasher, причём эти значения должны вести себя одинаково. Фактически, это фабрика хэшеров. Как и HashMap из стандартной библиотеки, так и hashbrown::HashMap параметризованы тремя типами, и этот третий тип — тот самый тип, реализующий BuildHasher. Так как значение этого типа у каждого экземпляра хэш-мапы может быть своим — и его даже можно предоставить явно при помощи with_hasher/with_capacity_and_hasher — это означает, что фактически конкретный экземпляр каждой хэш-мапы потенциально использует свою хэш-функцию (и, кстати, стандартная библиотека для фабрики хэшеров по умолчанию — std::collections::hash_map::RandomState — именно так в конструкторе и делает, что весьма огорчает некоторых пёселей). Таким образом, чтобы подсчитать хэш ключа так же, как это делает сама мапа, нам нужно получить доступ к build hasher внутри самой мапы — и, к счастью, такой геттер есть. Его можно написать и для LockedHashMap, имея при этом в виду те же соображения, что и для типа значения для find_with_hash:

fn hasher(&self) -> S
where
S: Clone,
{
self.lock_poisonless().hasher().clone()
}

Имея на руках значение типа, реализующего BuildHasher, уже несложно подсчитать хэш произвольного значения:

fn hash_single<T: Hash, S: BuildHasher>(build_hasher: &S, val: &T) -> u64 {
let mut hasher = build_hasher.build_hasher();
val.hash(&mut hasher);
hasher.finish()
}

(или же использовать BuildHasher::hash_one, когда его, чёрт побери стабилизируют) и скормить его мапе. В итоге код выглядит как-то так:

let hasher = locked_map.hasher();
// ...
let hash = hash_single(&hasher, &key);
let value = locked_map.find_with_hash(hash, &key);
if let Some(value) = value {
    // ...
}

Вот, собственно, и всё. Кода на этот раз совсем немного, но если вдруг кому-то понадобится — вот гист.

#wafflecontext #трудовыебудни

#prog #meme

Внезапно, годнота на Профункторе

#rust

Статья с впечатлениями от использования Rust в проде в течение больше, чем двух лет.

"All things considered, Rust is very mature and most of its pain points would exist in one shape or another in other mainstream languages. Rust makes reuse trivial and lets us deal safely with large code bases under active development without sacrificing performance.

Using Rust is for us no longer an experiment or a bet. It is the proven technology we are building on, <...>"

В СМЫСЛЕ УЖЕ ОКТЯБРЬ

#game

У вас нету причины не пройти Pyre.

И нет, не пытайтесь о ней что-то прочитать, к этой игре лучше подходить, ничего о ней не зная.