Diffの計算はそれこそ論文が書けてしまうような難しいコンピュータサイエンスなんですが、かっこよく表示するのもちょっと工夫しないと難しかったりします。多くの人が見慣れている、GitHubのような差分をQt上で表示するウィジェットを作ってみました。コードはQt依存なところもありますが、考え方は他のコードに移植できると思います。

Diff-Match-Patchを使ってみた→失敗

まず最初に使い慣れたDiff-Match-Patchを使ってみようと思いました。僕はGo版を使い慣れていて、なおかつオリジナル実装にはQtを使ったC++用のライブラリが入っている。

ですが、普通にやってみたら、以下のようにうまくいきませんでした。適当に"log"という行を足してみた結果です。

"log"という行だけの差分になってほしいのに、前の行の末尾のダブルクオートを巻き込んだdiffが取れてしまっています。前の行は実際は差分はないので、差分表示されちゃうと困ってしまいます。パッチを作って当てる用途ではなくて、見やすいdiffを出す用途なので多少冗長でも良いのですが、これができませんでした。あと、Diff-Match-PatchのWikiには行単位Diffの取り方のサンプルがあるんですがGoでやったときには問題なく動いたのですが、これがC++版だとprivateメソッドで使えないという。無理やりpublicに書き換えても動かず。別のライブラリを探し始めました。

Diff Template Libraryを使ってみる

ということで、インターネッツをさまよっていたら、cubicdaiya氏作のDiff Template Library for C++が見つかりました。Diff Match PatchはQtのQStringだけだったのですが、dtlはテンプレートでどんな型がきてもOKだったのでこれを使ってみました。

まずは行単位diff

Gitのdiffはまず行単位で行っています。DTLそのものは文字列の文字単位diffに特化してます。改行を特別に扱うようなコードも無さそう。一発で期待する結果は出ませんが、その分、いろいろミニマムな機能を組み合わせれば結構自由に差分が取れます。

ウィジェットはQLabelを継承して作ります。HTML(4.0のサブセット)が使えるので、色をつけたりして表示するにはこれが一番お手頃です。

QDiffView.h

#pragma once

#include <QLabel>

namespace qdiffview
{
class QDiffView : public QLabel
{
    Q_OBJECT
public:
    explicit QDiffView(QWidget *parent = 0);
    virtual ~QDiffView();
    void setSource(const QString &oldString, const QString &newString);
};
}

setSource()メソッドがいろいろ実装しているコードです。新旧の文字列を行単位に分けます。その後QMapを使って、行のリストを数値のリストに置換していきます。同じ内容だったら同じ数値になるようにしています。line2idというマップが行の文字列から数値へのマッピング、id2lineがその逆です。

とりあえずデバッグ出力してみます。

QDiffView.cpp

#include "qdiffview.h"
#include "pdtl/dtl.hpp"
#include <QDebug>
#include <QMap>

namespace qdiffview
{

QDiffView::QDiffView(QWidget *parent)
    : QLabel(parent)
{
    this->setTextFormat(Qt::RichText);
}

QDiffView::~QDiffView() {}

void QDiffView::setSource(const QString &oldString, const QString &newString)
{
    QMap<QString, int> line2id;
    QMap<int, QString> id2line;
    std::vector<int> oldStringIndex;
    std::vector<int> newStringIndex;

    // 古い方の文字列を行単位に分けて、idのリストに変換する。
    for (const QString &line : oldString.split(QRegExp("\n|\r\n|\r"))) {
        if (line2id.contains(line)) {
            oldStringIndex.push_back(line2id[line]);
        } else {
            int newId = line2id.size();
            oldStringIndex.push_back(newId);
            line2id[line] = newId;
            id2line[newId] = line;
        }
    }

    // 新しい方の文字列を行単位に分けて、idのリストに変換する。
    for (const QString &line : newString.split(QRegExp("\n|\r\n|\r"))) {
        if (line2id.contains(line)) {
            newStringIndex.push_back(line2id[line]);
        } else {
            int newId = line2id.size();
            newStringIndex.push_back(newId);
            line2id[line] = newId;
            id2line[newId] = line;
        }
    }

    // idのリストの差分を計算して表示してみる。
    dtl::Diff<int> linediff(oldStringIndex, newStringIndex);
    linediff.compose();

    for (auto ses : linediff.getSes().getSequence()) {
        qDebug() << ses.second.type << id2line[ses.first];
    }
}
}

ユニットテスト代わりに網羅的な状態変更の入力データを用意したサンプルを作ってみました。

sample.cpp

#include "qdiffview/qdiffview.h"
#include <QApplication>

QString oldSource = "abc\n" // same
                    "def\n" // removed
                    "ghi\n"
                    "jkl\n"
                    "mno\n" // remove one char insert one char
                    "pqr\n"
                    "stu\n" // remove one char
                    "vwx\n"
                    "yz\n"; // insert one char

QString newSource = "abc\n"
                    "ghi\n"
                    "123\n" // inserted
                    "jkl\n"
                    "no!\n" // remove one char insert one char
                    "pqr\n"
                    "su\n" // remove one char
                    "vwx\n"
                    "yz!\n"; // insert one char

int main(int argc, char **argv)
{
    QApplication app(argc, argv);
    qdiffview::QDiffView *view = new qdiffview::QDiffView();
    view->setSource(oldSource, newSource);
    view->show();
    return app.exec();
}

実行結果はこんな感じです。先頭の数値はdtl::edit_t型の定数で、0が新旧で同じ、-1が削除された、1が挿入されたという意味です。いい感じに出ましたね。

0 "abc"
-1 "def"
0 "ghi"
1 "123"
0 "jkl"
-1 "mno"
1 "no!"
0 "pqr"
-1 "stu"
1 "su"
0 "vwx"
-1 "yz"
1 "yz!"

HTML化して表示してみる

行番号込みで差分をきれいに表示したいので、HTML化してみます。一部CSSも使えますがなつかしのtableレイアウトです。テンプレートをQStringの文字列で用意しました。

QDiffView.cpp

QString bodyTemplate1 = "<html>\n"
                        "<head>\n"
                        "<style>\n"
                        ".text {font-weight:600;}\n"
                        "body {background-color: blue;width: 100%;}\n"
                        "table {width: 100%; }\n"
                        ".rl {background-color: #ffecec;}\n"
                        ".cl {background-color: #ffffff;}\n"
                        ".al {background-color: #eaffea;}\n"
                        "</style>\n"
                        "</head>\n"
                        "<body>\n"
                        "<table width=\"100%\" cellspacing=\"1\" cellpadding=\"3\">\n";
QString bodyTemplate2 = "</table>\n"
                        "</body></html>\n";
QString addedTemplate = "<tr class=\"al\"><th width=\"40\"></th><th "
                        "align=\"right\" width=\"40\">%1</th><td width=\"100%\">%2</td></tr>\n";
QString removedTemplate = "<tr class=\"rl\"><th align=\"right\" "
                          "width=\"40\">%1</th><th width=\"40\"></th><td "
                          "width=\"100%\">%2</td></tr>\n";
QString commonTemplate
    = "<tr class=\"cl\"><th align=\"right\" width=\"40\">%1</th><th align=\"right\" "
      "width=\"40\">%2</th><td width=\"100%\">%3</td></tr>\n";

表示する前に、削除が続いているブロック、挿入が続いているブロックでまとめようと思います。DTLは通常の使い方ならUnified Formatにしてくれる機能を提供してくれているのですが、今回は共通部分を間引かないで使用するので、自分でがんばります。

ブロックを表現する構造体を作っておきます。旧データ、新データのそれぞれのブロックの開始オフセット行数(ずれることがありえるので)、種類、行のコンテンツの文字列のリストが入ります。

diff.h

#pragma once

#include "dtl/variables.hpp"
#include <QStringList>

namespace qdiffview
{
struct Diff {
    int oldOffset;
    int newOffset;
    dtl::edit_t type;
    QStringList lines;

    Diff(int oo, int no, dtl::edit_t t)
        : oldOffset(oo), newOffset(no), type(t) {}
};
}

ヘッダーにメンバー変数でこのブロックのリストを取っておきます。

QDiffView.h

struct Diff;

class QDiffView : public QLabel
{
    // 省略
private:
    QList<Diff*> _diffs;
    void _update();
};

setSourceに追加していきます。_update()は最後にHTMLを完成させて表示を更新するメソッドです。

QDiffView.cpp

QDiffView::~QDiffView() { qDeleteAll(this->_diffs); }

void QDiffView::setSource(const QString &oldString, const QString &newString)
    // 省略
    qDeleteAll(this->_diffs);
    this->_diffs.clear();

    dtl::edit_t last = -2;
    int oldLineNumber = 1;
    int newLineNumber = 1;

    for (auto ses : linediff.getSes().getSequence()) {
        Diff *diff;
        // 最後のタイプと同じじゃなかったら新しいDiffオブジェクトを作る。
        if (ses.second.type != last) {
            diff = new Diff(oldLineNumber, newLineNumber, ses.second.type);
            last = ses.second.type;
            this->_diffs.append(diff);
        } else {
            // 同じなら最後のDiffオブジェクトを取ってくる
            diff = this->_diffs.last();
        }
        // Diffオブジェクトの行配列に追記
        diff->lines.append(id2line[ses.first]);
        // 行番号をインクリメントする
        switch (ses.second.type) {
        case dtl::SES_COMMON:
            oldLineNumber++;
            newLineNumber++;
            break;
        case dtl::SES_ADD:
            newLineNumber++;
            break;
        case dtl::SES_DELETE:
            oldLineNumber++;
            break;
        }
    }
    this->_update();
}

void QDiffView::_update()
{
    QStringList contents{bodyTemplate1};
    for (int i = 0; i < this->_diffs.length(); i++) {
        auto diff = this->_diffs[i];
        // 種類がごとにテンプレートに当てはめて出力していく。新・旧のコンテンツが存在するところだけ行番号をカラムに入れる。
        if (diff->type == dtl::SES_COMMON) {
            int oldLineNumber = diff->oldOffset;
            int newLineNumber = diff->newOffset;
            for (auto &line : diff->lines) {
                contents.append(commonTemplate.arg(oldLineNumber++).arg(newLineNumber++).arg(line));
            }
        } else if (diff->type == dtl::SES_DELETE) {
            int oldLineNumber = diff->oldOffset;
            for (auto &line : diff->lines) {
                contents.append(removedTemplate.arg(oldLineNumber++).arg(line));
            }
        } else {
            int newLineNumber = diff->newOffset;
            for (auto &line : diff->lines) {
                contents.append(addedTemplate.arg(newLineNumber++).arg(line));
            }
        }
    }
    contents.append(bodyTemplate2);
    this->setText(contents.join(""));
}

はい。いい感じに表示できていますね。

文字単位diffを追加

GitHubのdiffは同じ行内で削除された文字、追加された文字もわかりやすくなっています。同じ行内での編集ということで、隣接するdiffをうまく後処理してあげれば良さそうです。隣接しているといっても、削除5行、追記5行が斑になってしまうと見にくいので、同じ編集内容は固めておく必要があります。このために前のセクションではわざわざ同じ編集がされた行をまとめたのでした。

QDiffView.cpp

    // テンプレートのスタイルシート部に文字のdiffの色付けを追加
    ".rp {background-color: #f8cbcb;}\n"
    ".ap {background-color: #a6f3a6;}\n"

void QDiffView::setSource(const QString &oldString, const QString &newString)
{
    // 省略
    for (int i = 0; i < this->_diffs.length() - 1; i++) {
        auto oldDiff = this->_diffs[i];
        auto newDiff = this->_diffs[i + 1];
        // 旧・新と並んでいるdiff以外は相手にしない
        if (oldDiff->type != dtl::SES_DELETE || newDiff->type != dtl::SES_ADD) {
            continue;
        }
        // ブロック内の行をまとめて1つの長い文字列にする。
        auto oldString = oldDiff->lines.join('\n');
        auto newString = newDiff->lines.join('\n');
        // DTLで比較できるようにstd::vectorに変換
        std::vector<QChar> oldChars(oldString.constBegin(), oldString.constEnd());
        std::vector<QChar> newChars(newString.constBegin(), newString.constEnd());
        // diffを計算
        dtl::Diff<QChar> chardiff(oldChars, newChars);
        chardiff.compose();
        auto oldlast = dtl::SES_COMMON;
        auto newlast = dtl::SES_COMMON;
        // 新旧のフォーマット後のデータが格納される文字列
        QString oldFormatString;
        QString newFormatString;

        // ローカルな編集用関数2つ
        auto resetIfNeeded = [](dtl::edit_t &last, QString &formatString) {
            if (last != dtl::SES_COMMON) {
                formatString.append("</span>");
                last = dtl::SES_COMMON;
            }
        };
        auto append = [](QString &formatString, QChar ch) {
            if (ch == ' ') {
                formatString.append("&nbsp;");
            } else if (ch == '\t') {
                formatString.append("&nbsp;&nbsp;&nbsp;&nbsp;");
            } else {
                formatString.append(ch);
            }
        };

        // 前の文字と違う種類だったら、<span>タグでくくる、というのを新旧の文字列に対して行う
        // 新だけの文字は新に、旧だけの文字は旧だけにはいる。共通の文字は両方に入る。
        for (auto ses : chardiff.getSes().getSequence()) {
            if (ses.second.type == dtl::SES_COMMON) {
                resetIfNeeded(oldlast, oldFormatString);
                append(oldFormatString, ses.first);
                resetIfNeeded(newlast, newFormatString);
                append(newFormatString, ses.first);
            } else if (ses.second.type == dtl::SES_DELETE) {
                if (oldlast != dtl::SES_DELETE) {
                    oldFormatString.append("<span class=\"rp\">");
                    oldlast = dtl::SES_DELETE;
                }
                append(oldFormatString, ses.first);
            } else if (ses.second.type == dtl::SES_ADD) {
                if (newlast != dtl::SES_ADD) {
                    newFormatString.append("<span class=\"ap\">");
                    newlast = dtl::SES_ADD;
                }
                append(newFormatString, ses.first);
            }
        }
        // 最後は必ずタグを閉じる
        resetIfNeeded(oldlast, oldFormatString);
        resetIfNeeded(newlast, newFormatString);
        // 表示用の行のコンテンツを書き換え
        oldDiff->lines = oldFormatString.split("\n");
        newDiff->lines = newFormatString.split("\n");
    }
    this->_update();
}

はい。文字にも色が付きましたね。

同一内容が続いているところを省略して、クリックで開けるようにする

1000行あるファイルのうち、5行だけが変更があった場合は、それ以外の箇所は隠れて欲しいですよね？QLabelは内部のHTMLのリンクがクリックされたらシグナルが飛ぶので、それを使って実現します。

まずはDiffブロックに今表示しているかフラグを足します。

diff.h

struct Diff {
    // 省略
    bool visible;

    Diff(int oo, int no, dtl::edit_t t)
        /*省略*/, visible(false)
    {}
};

リンク付きのテンプレートも追加します。リンクがクリックされたときのスロットは、ラムダで。リンクはDiff配列のインデックスの数値を使うことにします。クリックされたらvisibleフラグをtrueにして_update()を呼んでHTMLの更新をします。HTML生成をメソッドに分けたのはこのためでした。仮想DOMっぽいでしょ？

QDiffView.cpp

QString commonLinkTemplate = "<tr class=\"cl\"><th width=\"40\"></th><th width=\"40\"></th><td  "
                             "align=\"center\" width=\"100%\"><a href=\"%1\">︙</a></td></tr>\n";

QDiffView::QDiffView(QWidget *parent)
    : QLabel(parent)
{
    // 省略
    connect(this, &QLabel::linkActivated, this, [=](const QString &link) {
        auto index = link.toInt();
        this->_diffs[index]->visible = true;
        this->_update();
    });
}

void QDiffView::_update()
{
    QStringList contents{bodyTemplate1};
    auto dumpCommon = [&](int oldLineNumber, int newLineNumber, const QStringList &commons) {
        for (auto &line : commons) {
            contents.append(commonTemplate.arg(oldLineNumber++).arg(newLineNumber++).arg(line));
        }
    };
    for (int i = 0; i < this->_diffs.length(); i++) {
        auto diff = this->_diffs[i];
        if (diff->type == dtl::SES_COMMON) {
            auto length = diff->lines.length();
            if (length > 7 && !diff->visible) {
                dumpCommon(diff->oldOffset, diff->newOffset, diff->lines.mid(0, 3));
                contents.append(commonLinkTemplate.arg(i));
                dumpCommon(diff->oldOffset + length - 3, diff->newOffset + length - 3,
                           diff->lines.mid(length - 3));
            } else {
                dumpCommon(diff->oldOffset, diff->newOffset, diff->lines);
            }

        } else if (diff->type == dtl::SES_DELETE) {
            // 変わらず
        } else {
            // 変わらず
        }
    }
    contents.append(bodyTemplate2);
    this->setText(contents.join(""));
}

リンクになりました。リンクのスタイルは後で直そう。

DiffならJSのライブラリとかでそれっぽいのはあるんですが、わざわざDiffのためだけにWebViewコンポーネント追加するのも消費メモリ上げるだけなので、ちょっとC++だけでやってみました。64bit機でQtランタイム含めて消費メモリ28MBぐらい。実際のアプリに追加した時の消費メモリの増加量はきっとMBいくかいかないかぐらいじゃないかな。

完成したライブラリ

下記のところにあります。他の人は使ってないと思いますが、自分だけ超便利に使っている自作のQt(C++)用のパッケージマネージャから使えるようにしてます。

8/30追記

// 旧・新と並んでいるdiff以外は相手にしない ってコメントしたところは実は間違いで、そこも、スペースやタブの置換は必要でした。あと、最終要素の1つ前までループしているので、最後の項目のフォーマットの修正が走らなかった時に、やっぱりスペース、タブの置換が発生しないので、そこも修正してあげる必要があります。あとは、行番号表示のスタイルをgithubに合わせたり(カラムの色や行番号の文字の色)、クリックで広がる行のスタイルも修正しています。最新版のコードを見てください。

QtでGitHubのような差分を出力する

Diff-Match-Patchを使ってみた→失敗

Diff Template Libraryを使ってみる

まずは行単位diff

HTML化して表示してみる

文字単位diffを追加

同一内容が続いているところを省略して、クリックで開けるようにする

完成したライブラリ