#20: Выживает сильнейший: генетические алгоритмы

[00:20] Здарова! Меня зовут Саша Пахомов, и я инженер, который любит своё дело. Это юбилейный, двадцатый выпуск подкаста «Тысяча фичей». Сегодня я расскажу вам про то, как работают генетические алгоритмы и как я пытался применить их в тестировании Java-кода. Этот выпуск я хотел сделать самым первым в подкасте, но решил отложить до момента, когда прокачаюсь и смогу интереснее рассказать про свой мертворождённый продукт. А в конце — олдскульная полезняшка. Поехали!

[00:55] Генетические алгоритмы, Java-код, тестирование — как это вообще всё можно связать, как подружить ежа с ужом? В этом выпуске я как раз расскажу, как это можно было сделать и как это сделал я. Для начала — про свой дипломный проект в магистратуре, который я делал в Воронежском государственном университете. Дам небольшую предысторию, как я пришёл к этому набору технологий — генетическим алгоритмам и Java — и как вообще мыслил. Затем немного погружу вас в теорию тестирования, которую я довольно плотно изучил, чтобы начать что-то делать. А потом расскажу про сам проект — и объясню, почему он был мертворождённым.

[01:36] Итак, идея для диплома витала в воздухе ещё на первом курсе магистратуры. Я уже сильно увлекался тестированием — читал книжку Кента Бека «TDD», которой делился в подкасте. Я в целом уже понимал, что тесты люблю писать, писал их в стиле TDD, и был таким нормальным крепким мидлом, который решал задачи, писал тесты, закрывал тикеты — в общем, бодро себя чувствовал на работе. Это я к чему? Я хорошо видел и чувствовал индустрию, потому что был в неё погружён. Несмотря на то, что это всего лишь первый курс магистратуры, опыта работы у меня было уже года три-четыре. Так что я в принципе понимал, как индустрия устроена, какие в ней проблемы и какие продукты туда можно принести.

[02:22] Свой диплом я воспринимал как потенциальное решение — open-source-библиотеку, фреймворк или даже компанию: типа того, как сейчас Atomic Jar делает с контейнерами. Давайте честно скажем: на тот момент зарплаты у хороших, крепких, бодрых мидлов были уже достаточно большие, и я расценивал своё время дорого. Я не собирался полгода-год делать осознанную тяжёлую работу в университете только для того, чтобы она осталась где-то в бумажках, и из неё ничего не выросло. То есть диплом я рассматривал как почву для ресёрча, как MVP или proof-of-concept библиотеки, которую потом, если пойму, что она работает, начну развивать сам и сделаю из неё свой продукт. Почему это не получилось — расскажу в конце; думаю, вы и сами по ходу поймёте почему.

[03:20] Что за идея? У меня, да и, думаю, у вас у всех, на работе есть такие участки кода — legacy, которые нормально не протестированы или на которые написаны настолько кривые тесты, что они сразу падают, и вы боитесь рефакторить. Каждый боится трогать эту часть кода: если что-то тронешь, тесты тебе об этом не скажут, потому что их, возможно, нет, — а продукт начнёт вести себя как-то не так. В каких-то edge-кейсах, на каких-то стендах что-то начнёт падать, и ты думаешь: «Да ну нафиг, не буду это менять», — а менять-то хочется. Мы же все инженеры, мы хотим сделать рефакторинг, хотим, чтобы кодовая база стала лучше.

[04:07] И что я тогда придумал? Было бы прикольно скормить какому-то инструменту вот этот исходный legacy-код и получить хорошие тесты, написанные на него. То есть я хотел покрыть тестами legacy-код, но не руками — руками писать тесты на такой старый код сложно: непонятно, как он вообще должен работать, и это может занять очень много времени. А вот если попросить фреймворк или библиотечку: «сгенерируй мне, пожалуйста, юнит-тесты для этого класса»… После того как тесты есть, как каркас зафиксирован, — в чём вообще состоит основа рефакторинга? В том, что мы меняем внутреннюю работу кода без изменения внешнего поведения. А как гарантировать неизменность внешнего поведения? Написать на него тесты. Вот я и хотел первым этапом написать тесты — для последующего комфортного рефакторинга. Такая была идея.

[05:04] Потом, когда начал про неё думать, я, конечно, начал разгонять. Было бы вообще прикольно написать какого-нибудь GitHub-бота, который приходит в open-source-проекты и просто предлагает сгенерированные им тесты. Ты расширяешь продукт и говоришь уже: «протестируй мне, пожалуйста, не конкретный класс, а вот этот репозиторий целиком». Бот уходит на день генерации этих тестов — тут скорость работы не так важна — и приходит с pull request’ом. Идея богатая: это можно интегрировать и продавать в компаниях как CI/CD-инструмент, где в процессе CI/CD на твой pull request какой-то процесс сверху дописывает ещё тестов, а ты их смотришь и, если они нормальные, принимаешь. Такой автоматизированный тестировщик. И напомню, что тогда этого ещё не было — на секундочку. Не было ни Copilot, ни ChatGPT; генеративные модели тогда не были так распространены. Поэтому идея казалась вообще супер.

[06:05] Это про саму идею. Дальше — про то, как я мыслил и подходил к написанию диплома. Ещё в бакалавриате, на четвёртом курсе, у меня был отличный ментор на работе — живой инженер из индустрии, который мне подсказывал, что нужно делать. Не преподаватель в университете, который варится в своей тарелке и не понимает, что происходит снаружи, а человек снаружи, который в целом может понять, что университету нужно. И вот этот коллега — спасибо ему огромное, он мне очень помог — говорит: «Слушай, пиши в LaTeX». У нас в университете LaTeX есть, но, хотя это инженерная специальность, программисты, — культуры писать дипломы в LaTeX нет. Из-за чего я, кстати, потом сильно расстроился. Все писали в Word — что, как мне кажется, очень странно и убого: на инженерном, математическом факультете писать дипломы в Word, блин, алло? В общем, инженер посоветовал LaTeX, я его изучил, посмотрел — реально понравилось, и бакалаврскую я писал в LaTeX.

[07:06] Так вот, когда я писал уже магистерскую диссертацию, выбора, в чём писать, у меня уже не было. Как строить процесс разработки диплома? Я подошёл к нему как к итеративной разработке — так, как мы это делаем в инжиниринге. Поэтому у меня есть GitHub-репозиторий с дипломом, там, естественно, LaTeX, всё это я делал в Git — итеративно, каждый день, каждую неделю что-то дописывал, добавлял какой-то ресёрч, коммитил, пушил. Нормальный такой процесс, и за это он мне очень понравился. То есть я использовал GitHub, LaTeX, ну и собственно свою голову и интернет — чтобы сначала ресёрчить, а потом уже и разрабатывать.

[07:43] Ещё пара слов про процесс. Я принципиально, осознанно не выбирал себе научного руководителя. В российских университетах есть такая тема: ты выбираешь научрука, чтобы он тебя в процессе ресёрча направлял, давал ревью, вёл по ходу работы. Но по опыту бакалаврского диплома я понял, что в магистерской работе этот человек мне совершенно не нужен. Какие-то редакторские правки, орфографические ошибки помочь исправить он бы мог, но по факту — по качеству ресёрча, по разрабатываемому инструменту — компетенции оценить то, что я делаю, у них не хватало. Поэтому я решил вообще не брать дипломного руководителя. Благо мои софт-скиллы и положение на кафедре позволяли так сделать: я был на хорошем счету, уже преподавал и в целом сам мог кому-то быть научным руководителем. Вот и решил, что мне это не нужно — буду делать сам.

[08:58] О чём я вообще не жалею. У меня была творческая свобода: я мог распоряжаться своим временем, ни от кого не зависел, никто не присылал мне ревью. Как я сам видел диплом, так я его и писал — и от этого сильно кайфанул. Мне реально понравился процесс самостоятельного ресёрча, работы и рефлексии над тем, что делаешь. Тебе не нужен кто-то, кто будет тебе что-то говорить, и ты будешь от него зависеть — делать так, чтобы ревьюер сказал «ок», а не так, чтобы тебе самому было ок. А иногда бывает: тебе внутри ок, а ревьюер говорит, что не ок, — и что делать? Порой ревьюер просто лажает и даёт не ту обратную связь, которую ты ожидаешь. Поэтому ревьюеров в дипломе у меня не было.

[09:40] Единственное, что я в порядке подготовки изучил, — прочитал книгу «Пиши, сокращай» Ильяхова. Сейчас перечитываю диплом — там прямо Ильяховщина, чистый информационный стиль. В целом для диплома он подходит, так что ничего страшного, но сейчас я так уже, конечно, не пишу. Забавно. Редакторские скиллы я себе подкачал, чтобы диплом можно было читать. Орфографию, естественно, проверял автоматизированно — по-моему, куда-то в LanguageTool засылал текст, чтобы не делать ошибок. Ну и жена мне помогала смотреть, потому что с этим у меня, честно говоря, есть небольшие проблемы. А в остальном мне никто ничего не говорил, я всё делал сам: просто пришёл на предзащиту, предзащитился, получил какие-то правки от преподавательского состава, поправил их и выступил с дипломом на отлично.

[10:37] Ну а теперь давайте к самому делу — хватит разговаривать. Как я начал ресёрчить и изучать тему? Итак, у меня была идея сделать тулу, которая сама пишет тесты на исходный код. На старте я вообще не понимал, как это можно сделать. У меня не было даже мысли писать нейронную сеть — я же не data scientist. Написать простенькую модель, сделать пайплайн, обучить, что-то подкрутить, запустить, посмотреть — это я мог. Но писать нейронную сеть уровня хотя бы GPT-2 или GPT-3 мне, студенту-не-датасайентисту, было невозможно. Поэтому я принципиально отложил от себя нейронные сети. Не искусственный интеллект в широком смысле, а именно нейронные сети. С инженерной точки зрения я хорошо умею делать одно — писать код. Вот какой я могу написать код, чтобы он генерировал сносные JUnit-тесты для Java-кода?

[11:45] Начал я, конечно, с того, что поглубже изучил сам фреймворк JUnit — всякие экстеншены, параметризацию тестов (про неё я в целом знал, но описал заодно). Параллельно с изучением я писал теоретическую часть диплома, чтобы читающим было понятно, откуда у работы растут ноги. И наткнулся на неплохой ресёрческий проект — ребята изучают fuzzing testing. В дипломе я приложу ссылку на свой репозиторий, а там, в конце, будут все материалы, так что при желании можно найти. Суть в том, что они делают интерактивный Python-ноутбук, в котором можно даже исполнять код: читаешь его как книжку, а они изучают фазинг. И рядом с фазингом была такая тема, как Search-Based Software Testing, то есть тестирование на основе анализа исходного кода. Но прежде чем объяснить, что это, давайте вообще поговорим про тестирование, про тесты, про предметную область, в которой мы сейчас находимся.

[12:50] Мы все знаем, что тесты писать можно и нужно. Тестирование глобально делится на два типа: когда мы тесты пишем и когда мы их исполняем. Исполнение тестов априори автоматизированное — мы не запускаем руками каждый метод, это понятно. А вот написание тестов у большинства всё ещё процесс не автоматизированный. Что мы делаем руками? Во-первых, можем писать спецификации. Даже если явно их не пишем, то в голове подразумеваем: специфицируем, при каких входных данных какие результаты ожидаем от нашего модуля — если говорить конкретно про юнит-тесты.

[13:30] Есть интересный приём, который используется в дизайне спецификаций и самих тест-кейсов, — разбиение входных данных на классы эквивалентности (я про это, кажется, уже говорил в каком-то выпуске). Что такое класс эквивалентности? Это подмножество входных параметров метода такое, что, если исполнить код на любом наборе данных из этого класса, мы получим один и тот же результат — тот же путь исполнения кода. Значит, все входные данные, приводящие к одному результату, принадлежат одному классу эквивалентности. Нам нужно найти все возможные классы эквивалентности, взять по одному набору данных из каждого и на их основе сделать тестовые кейсы. Вот она, наша интеллектуальная работа, которая ценится и которую мы, инженеры и тестировщики, выполняем, когда пишем тесты, — найти эти тест-кейсы.

[14:31] Ещё мы можем применить технику тестирования границ: когда понятно, где граничат классы эквивалентности, берём максимально близкие с двух сторон тестовые данные. Условно, есть метод isEmpty для строки: у нас есть пустая строка и минимально непустая — один символ. Поэтому мы берём границу «пустая строка / один символ» и пишем два тест-кейса на этой границе. Это такие, на первый взгляд наивные, мыслительные техники, которыми мы можем задизайнить тестовые сценарии.

[15:08] Затем можно использовать техники, которые уже не blackbox. До этого мы тестировали со стороны, не заглядывая в исходный код: знаем только, какой результат он отдаёт. А если мы можем посмотреть внутрь кода, то применяем другие техники генерации тестов — например, структурное тестирование. Оно учитывает исходный код, а учитывает с помощью покрытия — test coverage. Берём тест, запускаем, получили покрытие 10; генерируем ещё набор данных, проверяем — получили 20; и так до тех пор, пока не достигнем 100% покрытия. Когда достигли ста — всё, больше тестов не надо, их достаточно.

[16:00] Но штука в том, что покрытие можно считать по-разному. Самое банальное — покрытие строк кода: если на строке было исполнение, значит, она покрыта. Какой минус у этого подхода? Строчки кода могут меняться, они подвержены рефакторингу. Например, в первой версии был тернарный оператор if, где и основная, и else-ветка умещались в одной строке. Тогда, покрыв эту строчку, мы считаем её покрытой. Но если отрефакторить тернарник в полноценный if/else на три-четыре строки, а наш тест-кейс исполнялся только по else-ветке, то основная ветка покрыта не будет, и покрытие уменьшится. Поэтому покрытие по строкам — не самый оптимальный и не самый качественный вариант. Зато самый быстрый: его посчитать легче всего.

[17:02] Как решить эту проблему с рефакторингом? Можно представить код в виде дерева — не совсем до абстрактного синтаксического дерева, до AST, а просто как блоки кода, которые исполняются. Условно, if — это ветвление, else-ветка — один блок, основная ветка — другой блок. Представляем всё такими блоками, соединяем рёбрами и говорим: если блок исполнился, считаем его исполненным, — и покрытие считаем относительно блоков. Но покрытие блоков не учитывает все возможные пути, которыми мы можем в этот блок прийти. Поэтому есть ещё покрытие ветвлений, и оно уже более-менее адекватное: мы смотрим все ветвления — все пути, которые могут привести к конкретному блоку, и все пути, которые из него выходят. Стопроцентное покрытие ветвлений говорит, что мы прошли все пути.

[17:56] Но и тут есть шероховатости. Например, if держит в себе не одно условие вроде a < 10, а составное — a < 10 || b > 30. Это комплексное условие, которое может стать true или false разными способами: можно подложить a, которое меньше 10, а можно b, которое больше 30. То есть классов эквивалентности, влияющих на принятие решения, больше двух. Поэтому есть ещё покрытие условий: эти составные условия декомпозируются на односложные — ветвления раскладываются на более простые. И когда мы дошли до примитивов (одно условие — a < 10, второе — b > 30), и каждое стало отдельным блоком, мы после этого расширения внутренней структуры снова считаем покрытие по блокам и ветвям — и получаем более-менее адекватное, точнее, стопроцентное покрытие: лучше уже не придумаешь.

[19:03] Проблема этого подхода в том, что его очень сложно имплементировать: появляется слишком много тестовых входных данных. Чтобы покрыть все возможные пути исполнения, нужно очень много данных — там, по-моему, экспоненциальная зависимость числа тест-кейсов от количества входных параметров. Короче, это неоптимально, и никто в здравом уме такое количество тестов из головы не нагенерит для более-менее нормального продукта. Представьте свой код — все возможные if, все else, все пути: сколько будет тестов и сколько они будут работать?

[19:51] Поэтому есть более оптимальная техника, которая для меня стала открытием, когда я прочитал про неё впервые. Это так называемые condition/decision-критерии покрытия — «принятые решения», по сути вероятность; есть ещё modified-версия. В чём суть? Мы генерируем все возможные пути исполнения — пусть их будет восемь. Но тех, что влияют на изменение результата, всего четыре. То есть важных, значимых тестов реально меньше, чем всех возможных. Как определить значимый тест? Берём первый набор входных данных — скажем, 1, 2 — получаем true. Дальше наша задача — изменить ровно один параметр из набора (единичку или двойку) так, чтобы поменялся выходной результат: true превратился в false.

[20:43] Вот это одно изменение и есть значимый шаг. Первый кейс — 1, 2 = true. Потом подбираем набор 1, 30 = false. Следующий ход — снова меняем ровно один параметр, чтобы снова поменять результат: меняем единицу на минус единицу и получаем что-то другое. Так продолжаем, пока не можем придумать нового единственного изменения одного входного параметра, которое поменяло бы результат. Как только такого изменения нет — останавливаемся, перестаём генерировать тест-кейсы. И этот набор тестов адекватен с точки зрения и количества, и покрытия. Это такое эмпирическое понимание важности теста — на этом моменте можно остановиться.

[21:37] Также можно писать тесты на основе контрактов — design by contract; про это я говорил в десятом выпуске «Тысячи фичей», так что переходите, слушайте, — здесь я на этом останавливаться не буду. Можно использовать property-based testing: для него даже есть специальные фреймворки — на Java это, по-моему, jqwik, если не ошибаюсь. Как это работает? Мы определяем какой-то инвариант — типа «корень из числа всегда больше нуля» — и просто пихаем в нашу функцию всевозможные числа, а генерацией этих чисел занимается специальная аннотация. Мы помечаем ею входные параметры — по сути, такой же параметризованный юнит-тест, просто через другой фреймворк, который генерирует кучу входных данных. В целом довольно полезный инструмент.

[22:30] Дальше, если копать в тестирование глубже и продвинутее, набредаешь на такой термин, как тестирование с помощью искусственного интеллекта. Напоминаю: это было три года назад, Copilot тогда не было, поэтому под искусственным интеллектом понимались всякие эвристики, генетические алгоритмы, search-based-штуки — то есть не обязательно нейронные сети, а в том числе и они, но не только. Что под этим термином может пониматься? Во-первых, наш обычный статический анализ — Checkstyle, разные check-rules, FindBugs. На самом деле очень полезная автоматизированная штука, которая так или иначе что-то тестирует, проверяет, находит баги — тот же NPE может найти. Инструмент полезный и давно используется в индустрии. Это статическое тестирование.

[23:22] Помимо статического есть ещё мутационное тестирование. Как оно работает, я рассказывал в предыдущем выпуске — можно послушать. Но если коротко: мы берём наши тесты и говорим, что сейчас будем тестировать качество самих тестов. Генерируем новый исходный код путём некоторых мутаций. Набор мутаций может быть огромным, но по сути мы просто меняем if‘чики — если уж совсем коротко: знак сравнения с большего на меньший, с меньшего на «меньше либо равно» и так далее. Потом компилируем этот код и проверяем, что тесты ловят его неправильно. Тем самым мы говорим: на этом наборе данных тесты не отработали. Если тест не поймал какое-то изменение — значит, тест плохой, нужно добавить сценариев. Мы об этом кричим, и программист приходит и дорабатывает тест.

[24:14] Также существует подход под названием фазинг. Это уже генерация почти случайных или псевдослучайных входных данных в ваш сервис, продукт, функцию или класс — как сконфигурируете. Туда генерируется вообще всё возможное: если есть URL, то и пустая строка, и просто китайские символы. Всё это летит на вход, и мы смотрим на корректность работы программы. Она может падать — но пусть падает корректно: возвращает какую-то ошибку, валидацию и так далее. Фазинг — вообще тема интересная, про него, возможно, запишу отдельный выпуск, потому что там прямо сейчас происходит ресёрч-ресёрч. И с появлением больших языковых моделей, думаю, мы увидим второй рассвет фазинга. Так что давайте подождём — а когда он начнёт стрелять, я обязательно про это выпущу подкаст.

[25:14] И теперь мы приближаемся к той технике, которую я решил освоить и которая мне больше всего импонировала, — Search-Based Software Testing, то есть поиск тестов на основе исходного кода. Как это работает? Мы генерируем какой-то тест — как именно, пока не знаем. Сгенерировали юнит-тест, запустили, померили покрытие по одному из критериев, увидели его — и теперь нужно сгенерировать другой набор тестов, который улучшит этот показатель, то есть критерий покрытия. И делать так до тех пор, пока не получим 100% или пока не выйдет тайм-аут. Одно из двух. Это классическая задача оптимизации — вообще говоря, нерешённая. Но есть разные практические инженерные подходы — эвристики и прочее, — которые в целом позволяют генерировать тесты, достигающие достаточно хорошего покрытия исходного кода. То есть это сделать можно. И вот как это делал я.

[26:18] Давайте для начала разберёмся, как вообще работает генетический алгоритм, чтобы у всех сложилось представление, а потом я на примере своей задачи — генерации Java-тестов — объясню, как его применить. Итак, абстрактный генетический алгоритм называется генетическим потому, что вдохновлён эволюцией, тем, как работают гены. Сейчас скажу своими словами. Мы берём или генерируем начальную популяцию — она либо дана, либо генерируется по каким-то правилам, вообще пофиг; главное, что у нас есть какая-то начальная популяция, скажем, из ста особей. Потом для каждой особи мы вычисляем функцию приспособленности — считаем её выживаемость. Как в природе: выживаемость особи — это способность прокормить себя, не умереть в холод. У каждой особи свой критерий выживаемости; мы его как-то считаем, получаем число и спрашиваем: достигло ли это число максимума? Это лучшая особь по данному критерию?

[27:23] Условно: рыба выживает на 100% и становится бессмертной, если начинает плавать со скоростью 200 км/ч. Считаем функцию приспособленности, равную скорости её передвижения под водой, и если это больше 200 — говорим: всё, достигнуто максимальное значение, функция приспособленности говорит, что это лучшая особь. Мы выходим из процесса: вот наше решение, вот та самая рыба, вот наша разработка, которую мы искали, — мы её нашли.

[27:56] Если же — а чаще всего так и есть — функция приспособленности выдаёт не единицу и не 100%, а какое-то число, мы просто связываем особь с этим числом: вот твой результат, а вот результаты у всех остальных особей. Проверяем, что не вышли за временные границы работы алгоритма, и идём дальше. Что делаем дальше? Берём всех особей и выполняем селекцию — выбираем лучших: из ста особей берём двадцать наилучших. Это число тоже всегда задаётся, подбирается экспериментально. Взяли самых быстрых, условно, рыб. Потом делаем мутации — рандомно вносим в гены этих рыб какие-то изменения, как в эволюции: когда клетки делятся, они могут мутировать.

[28:48] Вообще говоря, именно благодаря мутациям эволюция и движется. Потому что, если бы мутации не было, все эти быстрые рыбы, которые случайно оказались рыбами с одним плавником, так и остались бы рыбами с одним плавником, — и среди них мы бы в конце и пытались выбрать рыбу, которая плавает 200 км/ч, но она такой никогда не будет. Мы достигли локального максимума: рыбы с таким плавником никогда не будут плавать так быстро — они будут плавать 10 км/ч. Поэтому нужно внести мутацию: сказать, что количество плавников равно ста, бахнуть такую особь и посмотреть, что с ней будет, — то есть выйти из локального максимума случайным мутированием генов рыбы. Это популярный подход в подобных задачах и в машинном обучении, техника не новая. В общем, взяли, сделали мутации.

[29:33] И берём тех, кто выиграл и мутировал, и делаем скрещивание. Скрещивание — это когда берётся половина генов от одной рыбы и половина от другой: мы взяли двух лучших, скрестили их, сделали мутацию и ожидаем, что результат статистически когда-нибудь окажется выше текущего. И действительно, так оно и работает.

[29:54] Ещё раз проговорю генетический алгоритм — уже без всяких рыб, потому что, мне кажется, я объяснил немного запутанно. В начале у нас есть начальная популяция. Для каждой особи в ней мы вычисляем функцию приспособленности. Затем проверяем: достигли ли мы максимума для одной из особей по этой функции? Если достигли — алгоритм завершён. Если нет — входим в цикл. Проверяем, что время работы ещё доступно и мы можем генерировать новых особей; производим селекцию — выбираем лучших; производим мутацию; скрещиваем этих особей — и это становится нашей новой начальной популяцией. На ней мы снова считаем функцию приспособленности, снова проверяем максимальное значение, снова делаем селекцию, мутацию, скрещивание — и крутимся в этом цикле, пока не достигнем максимума функции приспособленности для одной из особей или не превысим время исполнения. Вот я вам и рассказал абстрактный генетический алгоритм как он есть.

[30:53] А теперь давайте подумаем, как всё это применить к генерации Java-кода — к генерации теста на Java. Вообще говоря, довольно забавная мысль и техника, которую я использовал; мне она нравится. Смотрите: что такое популяция? Популяция — это тесты, юнит-тесты, тестовые классы. Это то, кого мы взращиваем: мы хотим написать максимально классный юнит-тест, который даст 100% покрытия для нашего класса. Поэтому особью является юнит-тест. А его гены — это его внутренности. Под юнит-тестом я имею в виду тестовый класс, а он состоит из подмножества тестовых методов, помеченных аннотацией @Test. Вот эти методы, аннотированные @Test, и есть гены — свойства, которые особь может менять, добавлять, с кем-то скрещивать. Это тот геном, та единица, которой особи обмениваются между собой. Собственно, вот наша популяция — набор тестов. Как они генерируются и откуда берутся, расскажу чуть попозже; пока просто считаем, что они у нас есть.

[31:59] Дальше нам нужна функция приспособленности. Думаю, вы уже можете догадаться — в свете всего, что я рассказывал, — что функция приспособленности для юнит-теста это покрытие тестами. Я выбрал критерий покрытия ветвлений — по-моему, именно он был реализован в той библиотеке, которую я использовал для инструментирования кода. В общем, считаем какое-то покрытие; главное — не по строкам, а адекватное. Если достигаем единицы покрытия — весь код покрыт, — значит, достигли максимума функции приспособленности, и говорим, что этот тест и есть то, что нам нужно. Логично? Логично. Если покрытие не достигнуто — уходим дальше и делаем селекцию: берём тесты, достигшие наибольшего покрытия. Это просто.

[32:56] А теперь надо сделать мутацию и скрещивание. Я сказал, что ген — это один тестовый метод, аннотированный @Test. Копнём на уровень абстракции пониже: а что представляет собой внутренность этого тестирующего метода? У него есть скелет. Условно, это метод, который дёргается: входные параметры (заглушки для них) и заглушка для ассерта. То есть входные параметры — скажем, две заглушки под два параметра, — реальный вызов метода с этими параметрами и ассерт результата против ожидаемого значения. Вот это и есть ген. Мы можем параметризовать его входными параметрами — например, единичка и двойка. И когда для такого генома мы говорим «единичка и двойка» — это и есть геном: 1, 2 — входные параметры. Это один ген. У другого теста ген — 3, 4; у ещё одного — 10, 10; у следующего — -1, 0; у другого — 0, 0. Вот набор этих генов, их может быть много.

[33:58] И теперь мы делаем мутацию: берём рандомный ген, рандомный тест, и рандомно меняем у него число — скажем, с 10 на триллион, — и смотрим, что будет. А скрещивание, думаю, уже понятно: берём половину тестовых методов у одной особи, половину у другой, склеиваем в одну — и вот наша новая особь. Вот так происходят селекция и мутация.

[34:26] А теперь немного технического — как я это всё делаю. Мне на вход приходит исходный код — просто путь к Java-классу. Я начинаю этот класс статически анализировать: первая фаза работы библиотеки — статический анализ исходного кода. Из него мы вычленяем полезную информацию. Какую? Во-первых, как этот класс инстанцировать: с конструктором он или без. Это несложно сделать статическим анализом: если конструкторы есть, смотрим на их параметры и их типы. В моей коленочной версии всё работало без параметров, поэтому я просто находил конструктор и записывал: вот есть такой объект с таким конструктором. Дальше находил публичные методы, которые, собственно, надо тестировать, анализировал их входные и выходные типы, все параметры — собирал такую метаинформацию про класс, которая потом пригодится при генерации теста. А затем использовал её, чтобы тест сгенерировать.

[35:36] Стратегия генерации тестов у меня была примитивная. Понимаю, что это довольно просто, но мне нужно было показать, что подход в принципе имеет право на жизнь. Я брал публичный метод, высчитывал количество параметров и их типы, делал для каждого типа генераторы: для int — int-генератор, для long — long-генератор, для String — string-генератор. То есть ассоциировал генераторы и делал скелет теста. Что такое скелет тестового метода? Это создать инстанс — вызвать конструктор, положить его в переменную; затем сгенерировать входные параметры для метода, который хотим вызвать; вызвать метод с этими параметрами; взять результат и сделать ассерт.

[36:16] То есть мы берём результат, который исполняется против этих входных данных — против единички и двойки, — выполнили в рантайме прямо там, лямбдой, получили десятку, положили и говорим: результат должен быть равен 10. Мы как бы зафиксировали снапшот того, как этот код исполняется с этими параметрами, — и получили стандартный тест: даны параметры, вызываем метод, получили результат, сделали ассерт. И вот из этого мы вычленяем входные параметры и результат, чтобы потом их генерировать и подкладывать. То есть генерируем такой скелетон.

[36:54] Этот скелетон мы сгенерировали — и это результат первой работы, результат анализа и подготовки. Дальше мы будем так или иначе мутировать входные параметры скелетона, подкладывать разные результаты, делать селекцию — запускать тот самый генетический алгоритм. Но каждый раз перегенерировать и переанализировать класс мы не будем, потому что это долго и неоптимально. Что нам нужно дальше? Нафигачить много-много-много таких тестов, наложить туда разные входные параметры, запустить их, посчитать у каждого критерий покрытия, посмотреть, у кого лучше, сделать мутации — и вот в таком цикле крутиться, крутиться, крутиться.

[37:32] И в итоге для элементарных классов — с одним конструктором, одним методом, двумя-тремя параметрами — у меня оно работало. Для простой математики. Понятное дело, это демонстрационный проект, а не продукт, но оно реально генерировало юнит-тест, который можно было запустить, сохранить и закоммитить. Это было прикольно — но, естественно, на самом элементарном классе. Для классов со Spring, со сложными конструкторами оно не работало: если конструктор принимает объект — всё, не работает. Но я видел это как решаемую задачу; мне нужно было проверить, что оно в принципе жизнеспособно.

[38:06] Надеюсь, я не сильно загрузил вас для подкаста. Понимаю: если ты не особо знаком с терминологией и ничего такого не делал, представить себе в голове эти геномы в виде юнит-тестов реально сложно. Дальше я объясняю, понимаю, что немного сложновато. Но если вы не поняли, а вам интересно, — я оставляю ссылку на свой диплом на GitHub. Там есть файлик диплом.pdf, который можно прочитать и понять, как это работает: я там плюс-минус понятно всё объяснил в тексте, и с рисунками, конечно, всё будет яснее.

[38:41] Теперь — какие выводы я из всего этого сделал? И стоило ли оно того? С точки зрения продукта — естественно, не стоило. Почему? Потому что сейчас есть Copilot: эти тесты я генерирую одной кнопкой, и он мне их даёт. Да, это не так автоматизированно — полный набор тестов сразу ты не получаешь, — но подождать буквально год, и всё будет в порядке. И тот инструмент, каким я его видел, будет работать только с помощью генеративного Copilot — и работать лучше и быстрее, что самое важное. Потому что генетический алгоритм — это долгая фигня, она реально не особо работает. То есть как продукт это не полетело.

[39:23] Но как университетский проект, дающий почву для ресёрча, — это не какой-то очередной Java-сервис с сайтом, которые все у нас сдавали, скукотища полнейшая. На такое я вообще не хотел тратить время. Это не притащенная с работы задача, оформленная под диплом, — это моя личная инициатива. Это было то, что тогда находилось на острие изучения теории тестирования и генеративных штук, — реально cutting edge, на острие научной мысли. Я пытался провести своё изучение, свой ресёрч: применить генетический алгоритм — свою версию — к реальному Java-коду и попробовать сделать из этого инструмент. Вот такая была попытка и амбиция.

[40:16] Как интересный ресёрческий проект, как самостоятельная работа, это, мне кажется, было огромным преимуществом. Сейчас, когда я делаю ресёрчи на работе, они мне реально пригождаются: нужно изучить предметную область, задизайнить решение с оглядкой на то, как делают другие. И вот это умение, этот скилл, я там реально проработал. Так что с этой позиции диплом имеет смысл. Если ты делаешь то, что тебе интересно, если ты не страдаешь во время диплома, а реально ресёрчишь и изучаешь, — это вообще супер времяпрепровождение: когда у тебя мозги свежие, ты студент, у тебя есть время, ты можешь полностью погрузиться и изучить теорию. Это круто. И в этом плане я всем советую делать в дипломы подобные вещи. А если вы ментор или старший товарищ — драйвите своих студентов именно на такое, потому что оно потом отзовётся. Вот я сейчас перечитывал диплом — реально кайфанул: понятно изучил теорию тестирования, попробовал написать что-то своё. Реально круто. Поэтому я до сих пор горжусь этим проектом, и потраченного времени, естественно, не жаль.

[41:26] Но если вы не собираетесь тратить время на диплом и ресёрчи, а хотите как можно быстрее пройти эту систему и дальше заниматься тем, что вам интересно, — то есть у вас не совпадают взгляды на жизнь с тем, что даёт университет, — тогда, я считаю, вполне можно использовать генерацию через ChatGPT: сделать на пофиг и просто пройти систему с минимальными затраченными усилиями. Тоже вариант, я его уважаю. Но мне больше нравится погружение с головой — ресёрч и отдача себя. В целом, это моё личное мнение.

[42:05] На этом, наверное, буду завершать. Надеюсь, вы хоть что-то поняли, вам было хоть чуть-чуть интересно, и, может быть, кто-то словил мотивацию на диплом, если вы о нём думаете. Пишите в Телеграм-канале «Тысячи фичей» — пообщаемся об этом, если кому-то интересно. А в конце, как и обещал, — олдскульная полезняшка. Это доклад Лёши Шипилёва про ф— джойн-пулы, который он делал ещё лет десять назад. Если не смотрели — обязательно посмотрите, он актуален до сих пор. Не забывайте делиться подкастом с друзьями и коллегами — давайте прокачивать себя и людей вокруг. Ну а на этом всё. Услышимся!