Если я хочу посмотреть видео — разве для этого обязательно покидать vim?

Что ж, прямо в заголовке этого поста я пообещал вам продемонстрировать Bad Apple в vim, пользуясь только поисковыми запросами. Вот Bad Apple в vim: всё, что здесь меняется — только поисковый запрос:

Давайте обсудим, как всё это работает!

Позвольте, а что же такое Bad Apple?

Bad Apple — это залипательное музыкальное видео, которое разным затейникам нравится встраивать в неожиданных местах. Это мем, в том же смысле, в каком можно считать мемом запуск DOOM на экране умного холодильника.

Я хотел где-нибудь запустить Bad Apple с тех пор, как мне попалось это видео — якобы воспроизводящееся на сайте «Миллион флажков».

Получаем кадры

Первый шаг здесь был довольно прост. Мне требовались данные по каждому кадру Bad Apple. Felixoofed уже частично проделали за меня эту работу; я склонировал их репозиторий. Таким образом, я не только получил видео; ещё мне предложили команду ffmpeg, преобразующую этот ролик примерно в 6 500 файлов в формате PNG, по одному на каждый кадр.

Затем я написал немного кода на Python, чтобы превратить каждый из этих PNG в двумерный массив из нулей и единиц (где 1 соответствует чёрному пикселю). Исходный размер видео составлял 480x360 — и я сжал его до 120x90, померяв окно терминала и заключив, что больше картинка быть просто не может.

from PIL import Image
import numpy as np

def process_image(path, target_width=120, target_height=90):
    img = Image.open(path)
    img = img.resize((target_width, target_height), Image.Resampling.LANCZOS)

    if img.mode != "L": img = img.convert("L")

    pixels = np.array(img)
    binary_pixels = (pixels < 10).astype(int) # 1 для тёмного, 0 для светлого
    return binary_pixels

def text_preview(binary_pixels):
    chars = {0: ".", 1: "#"}

    return "\n".join("".join(chars[px] for px in row) for row in binary_pixels)

Я попробовал этот код с парой кадров и вывел на экран их text_preview, чтобы убедиться, что они выглядят нормально. Действительно, они получились!

Отрисовка в vim

Итак, как же нарисовать что-нибудь в vim? Что ж, для начала я собрал текстовую сетку, в которую был встроен рисунок. Вот сетка, состоящая в основном из A, но, если вы поищете B, то заметите человечка из палочек:

Итак, в принципе, что-то нарисовать можно! Но возникает ряд проблем. Во-первых, что делать с этой голубой подсветкой (кажется, в vim она активируется по умолчанию)? Не вполне ясно.

Но оказывается, что подсветка в vim очень хорошо конфигурируется! Для каждого подходящего символа можно задать подсветку переднего или заднего плана одним и тем же цветом. Для этого я вызываю hi Search cterm=NONE ctermfg=grey ctermbg=grey и в результате получаю красивые прямоугольники:

Но здесь есть ещё одна проблема — нам нужны квадратные пиксели! Но в данный момент каждый из наших символов — скорее прямоугольный, так как символы в большинстве гарнитур вытянуты в высоту, а не в ширину! Я поискал и нашёл шрифт Square, который, как вы догадываетесь… квадратный! Он спроектирован для игр-рогаликов, в которые играют в терминале. Если применить его в нашем случае, то получается очень красивая сетка:

Теперь давайте делать картинки, для этого будем подсвечивать текст. Но как нам подсветить именно тот текст, который понадобится для каждого кадра Bad Apple?

Рисуем произвольные прямоугольники

Я набросал кучу полуоформленных идей по поводу структуры файла. Может быть, найдётся способ анализировать мои кадры, выявить, какие пиксели должны получиться «яркими», а потом сгенерировать файл, специально оптимизированный для работы с регулярными выражениями, выбирающими эти пиксели?

Но прежде чем устремляться по этому пути, я решил подробно почитать в документации vim всё, что касается поиска. Я знал, что в поиске vim полно всевозможных экстравагантных фич и хотел уточнить, какие инструменты есть у меня в распоряжении. Оказалось, что в vim уже есть ровно то, что мне нужно!

Больше всего мне нравятся \zs и \ze, при помощи которых можно объявлять, где начинается или заканчивается совпадение. Они как бы позволяют сообщить: «всё, что находится за мной/передо мной можно считать перспективным/ретроспективным». Это очень эргономично!

				/\%l /\%>l /\%<l E951 E1204 E1273
\%23l	Matches in a specific line.
\%<23l	Matches above a specific line (lower line number).
\%>23l	Matches below a specific line (higher line number).
\%.l	Matches at the cursor line.
\%<.l	Matches above the cursor line.
\%>.l	Matches below the cursor line.

При поиске в vim можно задать сопоставление с конкретными номерами строк (и столбцов). Причём можно сочетать несколько таких поисковых заданий. Например, \%>5c\%<15c\%>4l\%<9l соответствует прямоугольнику, стороны которого пролегают между столбцами 5 и 15 и строками 4 и 9.

Более того, к этим паттернам применим оператор OR (ИЛИ), точно как при любой другой операции поиска в  vim. Например, выражение  \%>5c\%<15c\%>4l\%<9l\|\%>12c\%<25c\%>10l\%<15l находит и наш предыдущий прямоугольник, и тот, что заключён между столбцами 12 и 25 и строками 10 и 15. Поэтому не составляет труда отрисовать на экране одним поисковым запросом множество прямоугольников.

В результате задача переформулируется: теперь мы должны разложить каждый кадр на последовательность прямоугольников, по которым можно было бы вести поиск!

Переделываем кадры в прямоугольники

Наша сетка имела размеры 90x120, в ней у нас было примерно 10 000 пикселей. Таким образом, при крайне упрощённом подходе нам потребовалось бы найти тысячи разных прямоугольников и для этого сгенерировать поисковую строку длиной в десятки тысяч символов. Проведя простейшие тесты, я обнаружил, что, пусть поиск в vim и очень быстр, с такими поисковыми строками не удаётся справиться ни при какой кадровой частоте.

Казалось, что идея «декомпозировать эту сетку на минимальное количество прямоугольников, необходимое для её заполнения» однозначно приведёт нас к имеющемуся решению, поэтому я взялся такие решения искать. Но почти ничего не нашёл! Есть вопрос 14-летней давности на stack overflow, на который поступил ответ «это сложно».

Поэтому я придумал наивное решение. Решил действовать так:

• Обнаруживаем все единицы в первом ряду.

• Смотрим следующий ряд и находим серии, перекрывающиеся с сериями из предыдущего ряда.

• «Объединяем» эти серии в прямоугольник при условии, что площадь такого совокупного прямоугольника больше, чем площадь любого ряда в отдельности (напомню, что серии могут перекрываться не полностью).

• Продолжаем в том же духе, при этом обязательно добавляем новые серии в имеющиеся прямоугольники, когда это только возможно.

Код для этой операции довольно длинный, и я не уверен, что вам стоит его читать, но, если вам любопытно — вот он:

class Rect:
    def __init__(self, col_start, col_end, row_start, row_end):
        self.row_start = row_start
        self.row_end = row_end
        self.col_start = col_start
        self.col_end = col_end

    def height(self):
        return self.row_end - self.row_start

    def width(self):
        return self.col_end - self.col_start

    def area(self):
        return self.height() * self.width()

    def to_vim_pattern(self):
        # vim индексируется, начиная с 1 (не включительно) в обоих направлениях 
        row_start = self.row_start
        row_end = self.row_end + 1
        col_start = self.col_start
        col_end = self.col_end + 1
        return fr"\%>{col_start}c\%<{col_end}c\%>{row_start}l\%<{row_end}l"

    def __repr__(self):
        width = self.width()
        height = self.height()
        return f"R: ({width}x{height}) {self.row_start}:{self.row_end}, {self.col_start}:{self.col_end}"

    def test_merge_horizontal(self, run_start, run_end, run_row):
        if run_end <= self.col_start: return [False, None, None, None]
        if run_start >= self.col_end: return [False, None, None, None]

        overlap_start = max(run_start, self.col_start)
        overlap_end = min(run_end, self.col_end)
        overlap_rect = Rect(overlap_start, overlap_end, self.row_start, run_row+1)

        # прямоугольники, которые больше не подпадают под слияние
        top_rects = []
        if overlap_start > self.col_start:
            top_rects.append(Rect(self.col_start, overlap_start, self.row_start, self.row_end))
        if overlap_end < self.col_end:
            top_rects.append(Rect(overlap_end, self.col_end, self.row_start, self.row_end))

        # прямоугольники, отсечённые от текущей серии, но поддающиеся слиянию с 
        # пикселями, расположенными ниже 
        bot_rects = []
        if overlap_start > run_start:
            bot_rects.append(Rect(run_start, overlap_start, run_row, run_row+1))
        if overlap_end < run_end:
            bot_rects.append(Rect(overlap_end, run_end, run_row, run_row+1))

        return [True, overlap_rect, top_rects, bot_rects]
    
def find_runs(row):
    runs = []
    start = None

    for i, val in enumerate(row):
        if val == 1 and start is None:
            start = i
        elif val == 0 and start is not None:
            runs.append((start, i))
            start = None

    if start is not None:
        runs.append((start, len(row)))
    return runs

def try_merge_with_prev_row(mergeable_rects, run_start, run_end, run_row):
    candidate_merges = []
    for i, rect in enumerate(mergeable_rects):
        merge_result = rect.test_merge_horizontal(run_start, run_end, run_row)
        if merge_result[0]: candidate_merges.append((merge_result, i))

    best = None
    best_idx = None
    best_merge_result = None
    run_length = run_end - run_start

    for (candidate, candidate_idx) in candidate_merges:
        _, overlap_rect, top_rects, bot_rects = candidate
        overlap_area = overlap_rect.area()
        if best is None or overlap_area > best:
            best = overlap_area
            best_idx = candidate_idx
            best_merge_result = (overlap_rect, top_rects, bot_rects)

    if best is None: return (None, None)
    elif best > run_length: return (best_idx, best_merge_result)
    else: return (None, None)

def to_horizontal_merge_rect_representation(binary_pixels):
    completed_rects = []
    mergeable_rects = []

    for row_idx, row in enumerate(binary_pixels):
        next_mergeable_rects = []
        runs = find_runs(row)

        for (run_start, run_end) in runs:
            best_merge_idx, best_merge_result = try_merge_with_prev_row(mergeable_rects, run_start, run_end, row_idx)
            if best_merge_idx is None:
                r = Rect(run_start, run_end, row_idx, row_idx+1)
                next_mergeable_rects.append(r)
            else:
                mergeable_rects.pop(best_merge_idx)
                overlap_rect, top_rects, bot_rects = best_merge_result
                mergeable_rects.extend(top_rects)
                next_mergeable_rects.append(overlap_rect)
                next_mergeable_rects.extend(bot_rects)

        completed_rects.extend(mergeable_rects)
        mergeable_rects = next_mergeable_rects

    completed_rects.extend(mergeable_rects)
    return r"\|".join(rect.to_vim_pattern() for rect in completed_rects)

Код, который я совсем не хотел вам показывать.

Можете в него не вчитываться. Суть в том, что этот код далеко не оптимален. (но писать его было реально весело). Например, этот код никогда не заглядывает более чем на ряд вперёд, поэтому отвергает такие варианты слияния, которые сейчас неуместны, но вполне могли бы привести к чему-то путному с учётом компоновки дальнейших рядов.

Но я же знал, что этот код наивен, ещё когда писал его. Я просто попробовал набросать что-нибудь отдалённо разумное и посмотреть, как этот код будет работать. Я генерировал поисковые запросы на каждый кадр и выписывал их в файл. После этого я составил простую тестовую обвязку для проверки анимации в vim — и обнаружил, что с производительностью всё нормально! Скажем так, в некоторых случаях.

Патологические случаи

В некоторых случаях мой наивный алгоритм работал по-настоящему хорошо, а в других — просто плачевно. Во многих поисковых строках было по 500-2000 символов, но вот для этого изображения он генерирует поисковую строку длиной более 10 000 символов!

Оговорюсь, что производительность не в точности бьётся с производительностью, но, думаю, соответствие здесь очень хорошее. Ведь наша поисковая строка — это просто набор паттернов (схожей длины), сцепленных оператором ИЛИ. Чем длиннее поисковая строка, тем больше в ней паттернов. Причём длительность поиска должна масштабироваться, то есть расти по мере увеличения количества паттернов, ведь vim приходится проверить каждый из них, а затем решать, выполняется ли условие поиска.

При этом тщательного профилирования я не делал, поэтому вполне могу быть в чём-то совершенно не прав!

При работе со столь длинными поисковыми строками кадровая частота драматически снижается — примерно от сорока кадров до считанных цифр в секунду.

Тогда я ударился в оптимизации. Самая увлекательная кроличья нора открылась в том случае, когда я попытался повышать производительность поиска в vim как такового, а не отдельных регулярных выражений. В конфигурации для воспроизведения видео оставил множество буферов открытыми, и на каждом из них приходилось выполнять поиск. Подумал, что, если удастся это предотвратить (или предотвратить подсвечивание в других буферах), то ситуация может улучшиться. Но так и не смог наладить такой механизм. У меня было несколько идей, что где подкрутить, но я не был уверен, что какая-либо из этих оптимизаций поможет мне в самых тяжёлых случаях. Ещё у меня не было времени, чтобы найти хороший универсальный алгоритм: я работал над этой задачей ночью перед очередной еженедельной презентацией в Recurse Center и хотел уже на следующий день представить результат!

Поэтому я провернул один из моих любимых фокусов — вместо одного отличного алгоритма написал несколько посредственных и решил, что воспользуюсь ими всеми!

Я написал ещё два наивных решения:

• Видоизменил мой алгоритм «выстраиваем прямоугольники сверху вниз» так, чтобы он работал слева направо.

• Написал простое кодирование длин серий, при котором учитывались только отдельные ряды.

После этого я обновил мой код так, чтобы каждый кадр прогонялся через все три алгоритма, а после этого выбирался кратчайший из сгенерированных поисковых паттернов!

Сработало отлично. Притом, что в каждом из этих алгоритмов были свои патологические случаи, между собой эти случаи очень отличались. Поэтому (почти) всегда как минимум один алгоритм генерировал достаточно хороший паттерн.

«Наилучшее» решение чаще всего генерировалось именно кодированием длин серий — но, если этот алгоритм (RLE) даёт плохое решение, то оно совсем плохое. Именно поэтому я сначала избегал пользоваться RLE. А мой исходный вариант использовался реже всего! Ой.

# Сколько раз использовался каждый подход
original approach (top to bottom merging) - 1110
left to right merging                     - 2239
single-row RLE                            - 3300

Подождите, а как именно вы всё это запускаете в vim?

Да, это хороший вопрос.

Вот как выглядит конфигурация пикселей в vim:

Слева по центру расположено окно, в котором воспроизводится видео. Это файл из 90 строк по 120 пробелов в каждой (напомню, что разрешение картинок у нас 120x90). Поскольку мы выполняем сопоставление по строкам и столбцам, никакой контент нам не требуется. Слева и справа находятся пустые буферы, отмеренные так, чтобы изображение находилось по центру.

В нижнем окне находится список наших поисковых паттернов. Все 6500.

Для воспроизведения видео используется макрос vim. Если вы не имели дела с макросами в vim, то расскажу, что макросы — это последовательности произвольных нажатий клавиш, которые впоследствии воспроизводятся. Макросы исключительно мощны, поскольку всё, что вы делаете в vim, выполняется с клавиатуры. Таким образом, вам не составляет труда записать и воспроизвести любое действие. Если же вы настроите макрос правильно (так, что в начале каждой следующей итерации курсор стоит именно в нужной точке), то можно приказать vim выполнить макрос по много раз подряд!

Макрос

Вот макрос: "ay$:let @/=@a^M+. Вот что он делает:

• "a обрабатывает регистр a

• y$ так добирается до конца файла

В Vim есть «именованные» регистры, в которых может содержаться текст. Так в ‘a’ сейчас содержится актуальная строка.

• : Переход в командный режим

• let @/=@a задаёт в качестве содержимого регистра / содержимое регистра a

• ^M выполняет команду (в данном случае ^M соответствует клавише «ввод»)

Чтобы сослаться на регистр в командном режиме, пишем @ , а после него — имя регистра. В Vim есть специальные регистры — так, регистр / соответствует текущему поиску. В данный момент vim ищет запрос, относящийся к текущей строке

• + перейти к началу следующей строки

Именно это я имею в виду, говоря, что, «если правильно настроить макрос, то его можно будет многократно воспроизводить». Мы готовы вновь использовать наш макрос, поскольку курсор уже в начале следующей строки!

Возможно, вам это кажется нонсенсом, но я с макросами на «ты», поскольку долгие годы занимался проектом Vimgolf. Но подход рабочий!

Самая интересная оптимизация — это let @/=@a. В качестве альтернативы можно было сделать что-то вроде /^Ra^M (начать поиск, вставить вывод регистра a, нажать «ввод»). Но это проблема, поскольку здесь приходится напрямую вставлять запрос, длина которого потенциально может достигать тысяч символов. В результате приходится расширять окно поиска, чтобы запрос в нём поместился. Из-за этого начинается мерцание, и кадровая частота снижается.

Но теперь мы можем выполнить 1500@q (при этом предполагается, что мы записали макрос в регистр q), чтобы макрос воспроизводился 1500 раз – то есть, мы прогоним 1500 кадров настолько быстро, насколько сможем.

И вот что у нас получится!

Заключение

Ух, это было интересно! Я написал всё это в течение суток, но, если бы я хотел потратить на этот проект больше времени, то внёс бы в него следующие доработки:

• Думаю, получилось бы ещё волшебнее, если бы я пошёл путём «создать хорошо структурированный файл, управляемый при помощи традиционных регулярных выражений, а не через встроенный в vim поиск по строкам и столбцам. Меня могут справедливо укорить, что регулярные выражения у меня ненастоящие!

• Я совершенно не старался добиться стабильной кадровой частоты, поэтому на протяжении всего видео в ней заметные явные флуктуации.

Но с учётом тех задач, что я перед собой поставил, получилось неплохо. Я думаю, это красиво, что я смог создать относительно универсальное решение, позволяющее воспроизводить видео внутри vim при помощи одних только поисковых запросов. Мне даже посоветовали записать на видео, как я играю в Bad Apple в vim, после чего воспроизвести это видео в vim. Думаю, попробую это сделать.

Наконец, признаю, что код вышел крайне запутанным, но, если хотите в нём покопаться — можете посмотреть его здесь.