Revision control
++ // Copyright (C) 2025 The Qt Company Ltd.
++ // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
++ // Qt-Security score:significant reason:default
++
++ // This code is adapted from QtCreator/src/libs/utils/differ.
++
++ /*
++ The main algorithm "diffMyers()" is based on "An O(ND) Difference Algorithm
++ and Its Variations" by Eugene W. Myers: http://www.xmailserver.org/diff2.pdf
++
++ Preprocessing and postprocessing functions inspired by "Diff Strategies"
++ publication by Neil Fraser: http://neil.fraser.name/writing/diff/
++ */
++
++ #include "qqmldiffer_p.h"
++
++ #include <QStringList>
++
++ #include <algorithm>
++ #include <vector>
++
++ QT_BEGIN_NAMESPACE
++
++ using namespace Qt::StringLiterals;
++ namespace QQmlLSUtils {
++
++ static qsizetype commonPrefix(const QString &text1, const QString &text2)
++ {
++ // mismatch returns first non-equal pair
++ const auto [it1, it2] = std::mismatch(text1.cbegin(), text1.cend(),
++ text2.cbegin(), text2.cend());
++
++ return qsizetype(std::distance(text1.cbegin(), it1)); // number of matching characters
++ }
++
++ static qsizetype commonSuffix(const QString &text1, const QString &text2)
++ {
++ // mismatch returns first non-equal pair
++ const auto [it1, it2] = std::mismatch(text1.crbegin(), text1.crend(),
++ text2.crbegin(), text2.crend());
++
++ return qsizetype(std::distance(text1.crbegin(), it1)); // number of matching characters
++ }
++
++ static QList<Diff> decode(const QList<Diff> &diffList, const QStringList &lines)
++ {
++ QList<Diff> newDiffList;
++ newDiffList.reserve(diffList.size());
++ for (const Diff &diff : diffList) {
++ QString text;
++ for (QChar c : diff.text) {
++ const qsizetype idx = static_cast<ushort>(c.unicode());
++ text += lines.value(idx);
++ }
++ newDiffList.append({diff.command, text});
++ }
++ return newDiffList;
++ }
++
++ static QList<Diff> squashEqualities(const QList<Diff> &diffList)
++ {
++ if (diffList.size() < 3) // we need at least 3 items
++ return diffList;
++
++ QList<Diff> newDiffList;
++ Diff prevDiff = diffList.at(0);
++ Diff thisDiff = diffList.at(1);
++ Diff nextDiff = diffList.at(2);
++ qsizetype i = 2;
++ while (i < diffList.size()) {
++ if (prevDiff.command == Diff::Equal
++ && nextDiff.command == Diff::Equal) {
++ if (thisDiff.text.endsWith(prevDiff.text)) {
++ thisDiff.text = prevDiff.text
++ + thisDiff.text.left(thisDiff.text.size()
++ - prevDiff.text.size());
++ nextDiff.text = prevDiff.text + nextDiff.text;
++ } else if (thisDiff.text.startsWith(nextDiff.text)) {
++ prevDiff.text += nextDiff.text;
++ thisDiff.text = thisDiff.text.mid(nextDiff.text.size())
++ + nextDiff.text;
++ i++;
++ if (i < diffList.size())
++ nextDiff = diffList.at(i);
++ newDiffList.append(prevDiff);
++ } else {
++ newDiffList.append(prevDiff);
++ }
++ } else {
++ newDiffList.append(prevDiff);
++ }
++ prevDiff = thisDiff;
++ thisDiff = nextDiff;
++ i++;
++ if (i < diffList.size())
++ nextDiff = diffList.at(i);
++ }
++ newDiffList.append(prevDiff);
++ if (i == diffList.size())
++ newDiffList.append(thisDiff);
++ return newDiffList;
++ }
++
++ ///////////////
++
++ Diff::Diff(Command com, const QString &txt) :
++ command(com),
++ text(txt)
++ {
++ }
++
++ bool Diff::operator==(const Diff &other) const
++ {
++ return command == other.command && text == other.text;
++ }
++
++ bool Diff::operator!=(const Diff &other) const
++ {
++ return !(operator == (other));
++ }
++
++ ///////////////
++
++ Differ::Differ()
++ {
++ }
++
++ QList<Diff> Differ::diff(const QString &text1, const QString &text2)
++ {
++ m_currentDiffMode = m_diffMode;
++ return merge(preprocess1AndDiff(text1, text2));
++ }
++
++ void Differ::setDiffMode(Differ::DiffMode mode)
++ {
++ m_diffMode = mode;
++ }
++
++ Differ::DiffMode Differ::diffMode() const
++ {
++ return m_diffMode;
++ }
++
++ QList<Diff> Differ::preprocess1AndDiff(const QString &text1, const QString &text2)
++ {
++ if (text1.isNull() && text2.isNull())
++ return {};
++
++ if (text1 == text2) {
++ QList<Diff> diffList;
++ if (!text1.isEmpty())
++ diffList.append(Diff(Diff::Equal, text1));
++ return diffList;
++ }
++
++ QString newText1 = text1;
++ QString newText2 = text2;
++ QString prefix;
++ QString suffix;
++ const qsizetype prefixCount = commonPrefix(text1, text2);
++ if (prefixCount) {
++ prefix = text1.left(prefixCount);
++ newText1 = text1.mid(prefixCount);
++ newText2 = text2.mid(prefixCount);
++ }
++ const qsizetype suffixCount = commonSuffix(newText1, newText2);
++ if (suffixCount) {
++ suffix = newText1.right(suffixCount);
++ newText1 = newText1.left(newText1.size() - suffixCount);
++ newText2 = newText2.left(newText2.size() - suffixCount);
++ }
++ QList<Diff> diffList = preprocess2AndDiff(newText1, newText2);
++ if (prefixCount)
++ diffList.prepend(Diff(Diff::Equal, prefix));
++ if (suffixCount)
++ diffList.append(Diff(Diff::Equal, suffix));
++ return diffList;
++ }
++
++ QList<Diff> Differ::preprocess2AndDiff(const QString &text1, const QString &text2)
++ {
++ QList<Diff> diffList;
++
++ if (text1.isEmpty()) {
++ diffList.append(Diff(Diff::Insert, text2));
++ return diffList;
++ }
++
++ if (text2.isEmpty()) {
++ diffList.append(Diff(Diff::Delete, text1));
++ return diffList;
++ }
++
++ if (text1.size() != text2.size()) {
++ const QString longtext = text1.size() > text2.size() ? text1 : text2;
++ const QString shorttext = text1.size() > text2.size() ? text2 : text1;
++ const qsizetype i = longtext.indexOf(shorttext);
++ if (i != -1) {
++ const Diff::Command command = (text1.size() > text2.size())
++ ? Diff::Delete : Diff::Insert;
++ diffList.append(Diff(command, longtext.left(i)));
++ diffList.append(Diff(Diff::Equal, shorttext));
++ diffList.append(Diff(command, longtext.mid(i + shorttext.size())));
++ return diffList;
++ }
++
++ if (shorttext.size() == 1) {
++ diffList.append(Diff(Diff::Delete, text1));
++ diffList.append(Diff(Diff::Insert, text2));
++ return diffList;
++ }
++ }
++
++ if (m_currentDiffMode != Differ::CharMode && text1.size() > 80 && text2.size() > 80)
++ return diffNonCharMode(text1, text2);
++
++ return diffMyers(text1, text2);
++ }
++
++ QList<Diff> Differ::diffMyers(const QString &text1, const QString &text2)
++ {
++ const qsizetype n = text1.size();
++ const qsizetype m = text2.size();
++ const bool odd = (n + m) % 2;
++ const qsizetype D = odd ? (n + m) / 2 + 1 : (n + m) / 2;
++ const qsizetype delta = n - m;
++ const qsizetype vShift = D;
++ std::vector<qsizetype> forwardV(2 * D + 1);
++ std::vector<qsizetype> reverseV(2 * D + 1);
++ for (qsizetype i = 0; i <= 2 * D; i++) {
++ forwardV[i] = -1;
++ reverseV[i] = -1;
++ }
++ forwardV[vShift + 1] = 0;
++ reverseV[vShift + 1] = 0;
++ qsizetype kMinForward = -D;
++ qsizetype kMaxForward = D;
++ qsizetype kMinReverse = -D;
++ qsizetype kMaxReverse = D;
++ for (qsizetype d = 0; d <= D; d++) {
++ // going forward
++ for (qsizetype k = qMax(-d, kMinForward + qAbs(d + kMinForward) % 2);
++ k <= qMin(d, kMaxForward - qAbs(d + kMaxForward) % 2);
++ k = k + 2) {
++ qsizetype x;
++ if (k == -d || (k < d && forwardV[k + vShift - 1] < forwardV[k + vShift + 1]))
++ x = forwardV[k + vShift + 1]; // copy vertically from diagonal k + 1, y increases, y may exceed the graph
++ else
++ x = forwardV[k + vShift - 1] + 1; // copy horizontally from diagonal k - 1, x increases, x may exceed the graph
++ qsizetype y = x - k;
++
++ if (x > n) {
++ kMaxForward = k - 1; // we are beyond the graph (right border), don't check diagonals >= current k anymore
++ } else if (y > m) {
++ kMinForward = k + 1; // we are beyond the graph (bottom border), don't check diagonals <= current k anymore
++ } else {
++ // find snake
++ while (x < n && y < m) {
++ if (text1.at(x) != text2.at(y))
++ break;
++ x++;
++ y++;
++ }
++ forwardV[k + vShift] = x;
++ if (odd) { // check if overlap
++ if (k >= delta - (d - 1) && k <= delta + (d - 1)) {
++ if (n - reverseV[delta - k + vShift] <= x) {
++ return diffMyersSplit(text1, x, text2, y);
++ }
++ }
++ }
++ }
++ }
++ // in reverse direction
++ for (qsizetype k = qMax(-d, kMinReverse + qAbs(d + kMinReverse) % 2);
++ k <= qMin(d, kMaxReverse - qAbs(d + kMaxReverse) % 2);
++ k = k + 2) {
++ qsizetype x;
++ if (k == -d || (k < d && reverseV[k + vShift - 1] < reverseV[k + vShift + 1]))
++ x = reverseV[k + vShift + 1];
++ else
++ x = reverseV[k + vShift - 1] + 1;
++ qsizetype y = x - k;
++
++ if (x > n) {
++ kMaxReverse = k - 1; // we are beyond the graph (right border), don't check diagonals >= current k anymore
++ } else if (y > m) {
++ kMinReverse = k + 1; // we are beyond the graph (bottom border), don't check diagonals <= current k anymore
++ } else {
++ // find snake
++ while (x < n && y < m) {
++ if (text1.at(n - x - 1) != text2.at(m - y - 1))
++ break;
++ x++;
++ y++;
++ }
++ reverseV[k + vShift] = x;
++ if (!odd) { // check if overlap
++ if (k >= delta - d && k <= delta + d) {
++ if (n - forwardV[delta - k + vShift] <= x) {
++ return diffMyersSplit(text1, n - x, text2, m - x + k);
++ }
++ }
++ }
++ }
++ }
++ }
++ // Completely different
++ QList<Diff> diffList;
++ diffList.append(Diff(Diff::Delete, text1));
++ diffList.append(Diff(Diff::Insert, text2));
++ return diffList;
++ }
++
++ QList<Diff> Differ::diffMyersSplit(
++ const QString &text1, qsizetype x,
++ const QString &text2, qsizetype y)
++ {
++ const QString text11 = text1.left(x);
++ const QString text12 = text1.mid(x);
++ const QString text21 = text2.left(y);
++ const QString text22 = text2.mid(y);
++
++ const QList<Diff> &diffList1 = preprocess1AndDiff(text11, text21);
++ const QList<Diff> &diffList2 = preprocess1AndDiff(text12, text22);
++ return diffList1 + diffList2;
++ }
++
++ QList<Diff> Differ::diffNonCharMode(const QString &text1, const QString &text2)
++ {
++ QString encodedText1;
++ QString encodedText2;
++ QStringList subtexts = encode(text1, text2, &encodedText1, &encodedText2);
++
++ DiffMode diffMode = m_currentDiffMode;
++ m_currentDiffMode = CharMode;
++
++ // Each different subtext is a separate symbol
++ // process these symbols as text with bigger alphabet
++ QList<Diff> diffList = preprocess1AndDiff(encodedText1, encodedText2);
++
++ diffList = decode(diffList, subtexts);
++
++ QString lastDelete;
++ QString lastInsert;
++ QList<Diff> newDiffList;
++ for (qsizetype i = 0; i <= diffList.size(); i++) {
++ const Diff diffItem = i < diffList.size()
++ ? diffList.at(i)
++ : Diff(Diff::Equal); // dummy, ensure we process to the end
++ // even when diffList doesn't end with equality
++ if (diffItem.command == Diff::Delete) {
++ lastDelete += diffItem.text;
++ } else if (diffItem.command == Diff::Insert) {
++ lastInsert += diffItem.text;
++ } else { // Diff::Equal
++ if (!(lastDelete.isEmpty() && lastInsert.isEmpty())) {
++ // Rediff here on char basis
++ newDiffList += preprocess1AndDiff(lastDelete, lastInsert);
++
++ lastDelete.clear();
++ lastInsert.clear();
++ }
++ newDiffList.append(diffItem);
++ }
++ }
++
++ m_currentDiffMode = diffMode;
++ return newDiffList;
++ }
++
++ QStringList Differ::encode(const QString &text1,
++ const QString &text2,
++ QString *encodedText1,
++ QString *encodedText2)
++ {
++ QStringList lines{{}}; // don't use code: 0
++ QHash<QString, qsizetype> lineToCode;
++
++ *encodedText1 = encode(text1, &lines, &lineToCode);
++ *encodedText2 = encode(text2, &lines, &lineToCode);
++
++ return lines;
++ }
++
++ qsizetype Differ::findSubtextEnd(const QString &text,
++ qsizetype subtextStart)
++ {
++ if (m_currentDiffMode == Differ::LineMode) {
++ qsizetype subtextEnd = text.indexOf(u'\n', subtextStart);
++ if (subtextEnd == -1)
++ subtextEnd = text.size() - 1;
++ return ++subtextEnd;
++ } else if (m_currentDiffMode == Differ::WordMode) {
++ if (!text.at(subtextStart).isLetter())
++ return subtextStart + 1;
++ qsizetype i = subtextStart + 1;
++
++ const qsizetype count = text.size();
++ while (i < count && text.at(i).isLetter())
++ i++;
++ return i;
++ }
++ return subtextStart + 1; // CharMode
++ }
++
++ QString Differ::encode(const QString &text,
++ QStringList *lines,
++ QHash<QString, qsizetype> *lineToCode)
++ {
++ qsizetype subtextStart = 0;
++ qsizetype subtextEnd = -1;
++ QString codes;
++ while (subtextEnd < text.size()) {
++ subtextEnd = findSubtextEnd(text, subtextStart);
++ const QString line = text.mid(subtextStart, subtextEnd - subtextStart);
++ subtextStart = subtextEnd;
++
++ if (lineToCode->contains(line)) {
++ codes += QChar(static_cast<ushort>(lineToCode->value(line)));
++ } else {
++ lines->append(line);
++ lineToCode->insert(line, lines->size() - 1);
++ codes += QChar(static_cast<ushort>(lines->size() - 1));
++ }
++ }
++ return codes;
++ }
++
++ QList<Diff> Differ::merge(const QList<Diff> &diffList)
++ {
++ QString lastDelete;
++ QString lastInsert;
++ QList<Diff> newDiffList;
++ for (qsizetype i = 0; i <= diffList.size(); i++) {
++ Diff diff = i < diffList.size()
++ ? diffList.at(i)
++ : Diff(Diff::Equal); // dummy, ensure we process to the end
++ // even when diffList doesn't end with equality
++ if (diff.command == Diff::Delete) {
++ lastDelete += diff.text;
++ } else if (diff.command == Diff::Insert) {
++ lastInsert += diff.text;
++ } else { // Diff::Equal
++ if (!(lastDelete.isEmpty() && lastInsert.isEmpty())) {
++
++ // common prefix
++ const qsizetype prefixCount = commonPrefix(lastDelete, lastInsert);
++ if (prefixCount) {
++ const QString prefix = lastDelete.left(prefixCount);
++ lastDelete = lastDelete.mid(prefixCount);
++ lastInsert = lastInsert.mid(prefixCount);
++
++ if (!newDiffList.isEmpty()
++ && newDiffList.last().command == Diff::Equal) {
++ newDiffList.last().text += prefix;
++ } else {
++ newDiffList.append(Diff(Diff::Equal, prefix));
++ }
++ }
++
++ // common suffix
++ const qsizetype suffixCount = commonSuffix(lastDelete, lastInsert);
++ if (suffixCount) {
++ const QString suffix = lastDelete.right(suffixCount);
++ lastDelete = lastDelete.left(lastDelete.size() - suffixCount);
++ lastInsert = lastInsert.left(lastInsert.size() - suffixCount);
++
++ diff.text.prepend(suffix);
++ }
++
++ // append delete / insert / equal
++ if (!lastDelete.isEmpty())
++ newDiffList.append(Diff(Diff::Delete, lastDelete));
++ if (!lastInsert.isEmpty())
++ newDiffList.append(Diff(Diff::Insert, lastInsert));
++ if (!diff.text.isEmpty())
++ newDiffList.append(diff);
++ lastDelete.clear();
++ lastInsert.clear();
++ } else { // join with last equal diff
++ if (!newDiffList.isEmpty()
++ && newDiffList.last().command == Diff::Equal) {
++ newDiffList.last().text += diff.text;
++ } else {
++ if (!diff.text.isEmpty())
++ newDiffList.append(diff);
++ }
++ }
++ }
++ }
++
++ QList<Diff> squashedDiffList = squashEqualities(newDiffList);
++ if (squashedDiffList.size() != newDiffList.size())
++ return merge(squashedDiffList);
++
++ return squashedDiffList;
++ }
++
++ } // namespace QQmlLSUtils
++
++ QT_END_NAMESPACE