Программируемый Дифф

Время от времени я глубоко погружаюсь в компилятор NuoSQL и делаю это с трудом. Как правило, это хорошо для компилятора, но это может сделать сравнение нового компилятора с результатами старого компилятора упражнением в изучении множества небольших различий, некоторые из которых имеют значение, а некоторые нет. Компьютеры гораздо лучше, чем я, поэтому я хотел бы использовать инструмент diff, который чрезвычайно настраивается. У PHP есть array-udiff, а у Python есть difflib, но я хотел инструмент, написанный на Java, и я также хотел узнать больше о том, как работает diff. Я разрабатываю компиляторы алгоритмов динамического программирования, и я знаю, что многие алгоритмы сравнения основаны на динамическом программировании. Должно быть весело!

Быстрый Тур

Код DiffEngine <T extends Comparable> в нашем репозитории github является основой этого инструмента. DiffEngine <T> сравнивает два экземпляра List <T>; его метод getDifferences () возвращает List <Difference> элемента поэлементных операций редактирования, которые преобразуют первый список во второй список. DiffEngine.coalesceRegions () преобразует поэлементный список в вывод, который больше похож на традиционный diff.

Инструмент FilterByRegex берет пути к двум файлам для сравнения и путь к файлу шаблона:

java -cp classes com.nuodb.diff.FilterByRegex testResults.expected testResults.actual -p patternFile

Файл шаблона представляет собой список регулярных выражений с группами захвата, такими как:

\s*(?:\w)+\s+(?:\||#)\s*(.*)\s*\(\d+\)\s*

Этот кусок gobbledygook находит строки из теста, которые выглядят так:

 main |           This is the interesting part (2)

и фиксирует «Это интересная часть» в группе захвата, (. *) в шаблоне. Если строка в любом файле для сравнения совпадает с шаблоном, FilterByRegex создает реферат исходной строки, который содержит только содержимое групп захвата регулярного выражения — абстракция строки выше «Это интересная часть». (Если строка не соответствует никакому регулярному выражению, то абстрактный текст строки является исходным содержимым строки.) Затем механизм сравнения сравнивает строки на основе их абстрактного значения, поэтому все эти строки будут считаться эквивалентными:

 main |           This is the interesting part (2)
 main #           This is the interesting part (2)
 main |           This is the interesting part (12)
 zort #     This is the interesting part (943344983)

Алгоритм Диффа

Различный двигатель удивительно прост. Как и большинство алгоритмов сравнения, он основан на решении проблемы самой длинной общей подпоследовательности, известной как «LCS». LCS двух последовательностей — это самая длинная коллекция элементов, которые можно найти по порядку в обеих последовательностях. Например, для двух последовательностей:

ABCDEFG ACXDKEVG

самая длинная общая подпоследовательность — ACDEG. Как видите, элементы в LCS не обязательно являются смежными. Может быть более одной LCS: например, для двух последовательностей: ABCD ACBD ABD и ACD являются допустимыми «самыми длинными» общими подпоследовательностями. Статья Википедии на Longest Common подпоследовательности имеет обзор хороший.

Нахождение LCS двух входов дает нам разницу, потому что LCS является близким математическим родственником «расстояния редактирования», мера того, сколько дискретных изменений требуется для преобразования первой последовательности во вторую. Это начинает звучать довольно по-разному.

Вычисление LCS

Алгоритм вычисления LCS работает путем обработки последовательных префиксов входных последовательностей. Вкратце, для любых двух префиксов A (1..i) и B (1..j) исходных последовательностей A и B мы сравним последние элементы A [i] и B [j]. Если они равны, то LCS этих двух префиксов на один элемент длиннее, чем LCS префиксов A (1..i-1) и B (1..j-1); если конечные элементы не равны, то LCS является наибольшим из LCS префиксов A (1..i-1), B (1..j) или A (1..i), B (1. .j-1). Как и многие строковые алгоритмы, этот алгоритм использует индексирование на основе 1; LCS определяется как 0, когда i или j равно 0. Многие перекрывающиеся вычисления LCS префиксов могут быть записаны в массиве подрешений, что приводит к алгоритму, основанному на динамическом программировании:

    lcs = new int[sequenceA.size()+1][sequenceB.size()+1];

    for (int i = 0; i < sequenceA.size(); i++) {

        for (int j = 0; j < sequenceB.size(); j++) {

            if (sequenceA.get(i).compareTo(sequenceB.get(j)) == 0) {

                // The subsequence extends to the ith and jth 
                // positions of the respective strings.
                lcs[i+1][j+1] = lcs[i][j] + 1;

            } else {

                // The longest subsequence at the ith and jth
                // positions is the longest of the two subsequences
                // of the prefixes sequenceA[1..i-1], sequenceB[1..j-1].
                lcs[i+1][j+1] = Math.max(lcs[i][j+1], lcs[i+1][j]);
            }
        }
    }

Преобразование LCS в различие

Преобразование LCS в diff выполняется путем запуска в конце массива lcs и обратного следования через массив для построения последовательности поэлементных операций редактирования, которые преобразуют последовательность A в последовательность B. Алгоритм начинается с

    int i = sequenceA.size();   // Recall that this algorithm uses 1-based addressing
    int j = sequenceB.size();

и работает через последовательности и массив lcs. Для любых значений i и j между их начальными значениями и 0 выполняется одно из следующих условий:

A [i] = B [j].
- В этом случае элемент является общим для обеих последовательностей, и алгоритм продолжает исследовать A [1..i-1] и B [1..j-1].
j больше нуля, а i равно нулю.
- Это означает, что последовательность B имеет префикс, который не появился в общей подпоследовательности. Алгоритм добавляет операцию редактирования «вставка B [j]» в серию операций редактирования и продолжает изучение A [1..i] и B [1..j-1].
Аналогично, если i больше нуля и j равно нулю, то последовательность A имеет префикс, который не появился в общей подпоследовательности. Алгоритм добавляет операцию редактирования «delete A [i]», так как его целью является генерация операций редактирования для преобразования последовательности A в последовательность B, и продолжается анализ A [1..i-1] и B [1..j ].
Если i и j оба больше нуля, то алгоритм должен выполнить операцию редактирования и продолжить с одной из пар префиксов A [1..i], B [1..j-1] или A [1. .i-1], В [1..j]. Алгоритм выбирает свои префиксы на основе матрицы lcs; пара префиксов с самым длинным lcs — это пара префиксов, которая в конечном итоге будет производить наименьшее количество операций редактирования. Если обе пары префиксов имеют одинаковые lcs, выбор будет произвольным.
- Выполняемая операция редактирования зависит от того, какая пара префиксов была выбрана.
  - Выбор пары префиксов A [1..i], B [1..j-1] означает, что алгоритм отбросил элемент последовательности B; поскольку цель состоит в том, чтобы выдать операции редактирования для преобразования последовательности A в последовательность B, это добавляет операцию редактирования «insert B [j]».
  - Аналогично, продолжая с A [1..i-1], B [1..j] добавляет операцию редактирования «delete A [i]».

Этот алгоритм генерирует последовательность поэтапных операций редактирования, что является абсолютно корректным diff; эта последовательность обычно объединяется в более крупные блоки операций редактирования, что дает знакомый формат diff. Алгоритм объединения в DiffEngine прост и консервативен, но дает достаточно читаемые результаты. Вот поэлементные и объединенные различия из инструмента тестирования:

$td abcdefg abbbf
3d2
< c
4d2
< d
5d2
< e
5a3
> b
5a4
> b
7d5
< g

$td abcdefg abbbf -c
3,5d2
< c
< d
< e
5a3,4
> b
> b
7d5
< g

Сопоставимый вывод из GNU Diff:

$trydiff abcdefg abbbfab
3,5c3,4
< c
< d
< e
---
> b
> b
7c6,7
< g
---
> a
> b

тестирование

Самый простой способ проверить реализацию diff — это … накормить его патчем! Это то, что я сделал. Мой псевдоним «td» сверху вызывает основную оболочку Java вокруг DiffEngine, которая работает с двумя строками в виде списков объектов Character. Небольшая перестановка в sed дает скрипт для разбиения строк на односимвольные строки, а затем мы даем вывод diff из нашего DiffEngine для исправления и ожидаем, что первый файл будет преобразован во второй файл:

    <exec executable="${sed}" inputstring="${s1}" output="${f1}" failonerror="yes">
        <arg line="${sedscript}"/>
    </exec>
    <exec executable="${sed}" inputstring="${s2}" output="${f2}" failonerror="yes">
        <arg line="${sedscript}"/>
    </exec>

    <java
        classname="${test.main.class}"
        fork="yes"
        failonerror="no"
        output="${patchfile}"
        resultproperty="testdiff.result"
        >
        <arg value="${s1}"/>
        <arg value="${s2}"/>
        <arg value="-c"/>
        <jvmarg value="-ea"/>
        <jvmarg value="-Xmx2048M"/>
        <classpath>
            <pathelement path="classes"/>
        </classpath>
    </java>

    <exec executable="${patch}" failonerror="yes" input="${patchfile}">
        <arg line="--silent"/>
        <arg line="${f1}"/>
    </exec>

    <exec executable="${diff}" failonerror="yes">
        <arg line="${f1}"/>
        <arg line="${f2}"/>
    </exec>

Программа sed — это забавный маленький фрагмент. Вот как это выглядит в функции trydiff bash:

trydiff () 
{ 
    diff <(echo $1 | sed 's/./&\
/g') <(echo $2 | sed 's/./&\
/g')
}

Программируемый Дифф