Я реализовал алгоритм Майерса в 130 строках, а затем потерял полдня из-за ошибки на единицу I Implemented Myers Diff in 130 Lines, Then Lost Half a Day to an Off-by-One Bug

Разработчик отказался от внешней библиотеки и самостоятельно реализовал алгоритм Майерса для сравнения текстов в рамках своего инструмента PureMark, уложившись в 130 строк TypeScript. Алгоритм, используемый в git diff, был переосмыслен как задача поиска кратчайшего пути на графе. После успешного тестирования на коротких текстах в продакшене обнаружилась коварная ошибка на единицу в логике обратного хода, которая проявлялась только на длинных данных, что подчеркивает важность тестирования на реалистичных объемах. Статья демонстрирует ценность глубокого понимания базовых алгоритмов и опасность скрытых багов.

A developer, adhering to a strict zero-dependency policy for their tool PureMark, implemented the Myers diff algorithm from scratch in about 130 lines of TypeScript, reframing the diff problem as a shortest-path search on a grid. The implementation initially worked for small test cases, but a subtle off-by-one bug in the backtracking logic—caused by misinterpreting the save timing of a state trace array—only manifested with longer texts, costing half a day to debug. The article highlights the educational value of implementing core algorithms, the perils of insufficient testing with production-scale data, and includes a practical solution for key-order-independent JSON diffing.