Merge lines in print-changed by showing simple changes in place in the line

[jamieschmeiser]

Summary

Relative simple changes result in a line being flagged as changed, showing the entire line in both red and green in the cdiff and dot-cfg outputs.
For example, an unnamed variable being removed results in all the subsequent variables being renamed, showing all lines containing these variables
in red or green and much time can be spent just verifying that the only change is the variable. Similar things happen when attributes change.
Where possible, merge these changes into a single line, showing the colourized change in line with the common part shown in black rather
than showing the entire line twice, once in red and once in green. Also flag such lines with a (red) asterisk in print-changed=(c)diff to aid identifying such lines.

[aeubanks]

do you have an example that I can try this on to see the difference?

[jamieschmeiser]

This will show some of the differences:

int f() {
  unsigned total = 0;
  for (unsigned i = 0; i < 5; ++i)
    total += i;
  return total;
}

int main() {
  return f();
}

clang -mllvm -print-changed=cdiff-quiet -emit-llvm -O2 test.C -c

Look for lines that have a * at the front. It shows better in colour. I originally had it limited to cdiff and dot-cfg, but then added the * to make it easier to spot in diff and cdiff (also helps if using grep -e "^\*" -e "^+"-e "^-")

*** IR Dump After SimplifyCFGPass on _Z1fv ***
...
*for.cond:                                         ; preds = -%for.inc+%for.body, %entry
...
 for.body:                                         ; preds = %for.cond
*  -%1+%2 = load i32, ptr %i, align 4, !tbaa !5
*  -%2+%3 = load i32, ptr %total, align 4, !tbaa !5
*  %add = add i32 -%2+%3, -%1+%2

Normally, for.body would have 3 red (delete) lines, followed by 3 green (add) lines and the first thing I would do is compare all of the text in the lines, trying to identify that everything other the unnamed variables was unchanged.
The example shows that when an unnamed variable is added or deleted, it has a ripple effect and such changes are easier to spot. Also, changes to just the attributes will also be displayed in a similar manner (eg: -!6+!7). I find it means I don't have to compare lines token by token to recognize simple changes. It also makes it a little more compact.

llvm/lib/Passes/StandardInstrumentations.cpp

 #include "llvm/Support/Error.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/GraphWriter.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Program.h"
 #include "llvm/Support/Regex.h"
 #include "llvm/Support/Signals.h"
 #include "llvm/Support/raw_ostream.h"
+#include <optional>
 #include <unordered_map>
 #include <unordered_set>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
 cl::opt<bool> PreservedCFGCheckerInstrumentation::VerifyPreservedCFG(

 bool isInteresting(Any IR, StringRef PassID, StringRef PassName) {
   if (isIgnored(PassID) || !isPassInPrintList(PassName))
     return false;
   if (const auto **F = any_cast<const Function *>(&IR))
     return isInterestingFunction(**F);
   return true;
 }
 
+class DiffHandler {
+public:
+  DiffHandler(std::string RColourOn, std::string RPrefix,
+              std::string RColourOff, std::string AColourOn,
+              std::string APrefix, std::string AColourOff,
+              std::string CColourOn, std::string CPrefix,
+              std::optional<std::string> NCPrefix, std::string CColourOff,
+              std::string NewLine)
+      : RColourOn(RColourOn), RPrefix(RPrefix), RColourOff(RColourOff),
+        AColourOn(AColourOn), APrefix(APrefix), AColourOff(AColourOff),
+        CColourOn(CColourOn), CPrefix(CPrefix), NCPrefix(NCPrefix),
+        CColourOff(CColourOff), NewLine(NewLine),
+        SearchRPrefix(RColourOn + RPrefix), SearchRSuffix(RColourOff + NewLine),
+        SearchAPrefix(AColourOn + APrefix), SearchASuffix(AColourOff + NewLine),
+        Removed(RColourOn + RPrefix + "%l" + RColourOff + NewLine),
+        Added(AColourOn + APrefix + "%l" + AColourOff + NewLine),
+        NoChange(CColourOn + CPrefix + "%l" + CColourOff +NewLine) {}
+
+  // Try to combine lines that only differ in an variable name or attribute.
+  // \p In is the result of the system diff so find a group of lines (possibly
+  // a single line) that are being removed.  If this is followed by a group
+  // of lines that are being added.  While the first of each group can be
+  // merged, keep trying to merge them.  A line can be merged by splitting
+  // it up on any of the following chars: "%@!#"  If the lines only differ
+  // by the id (or number) following the char, then merge the lines by
+  // replacing these sections  with the before and after parts in their
+  // appropriate (possibly colourized) formats and mark the line with NCPrefix.
+  std::string mergeLines(StringRef In) {
+    std::string Out;
+    while (true) {
+      // output everything until a removal line
+      auto SP = In.split(SearchRPrefix);
+      Out += SP.first;
+      if (SP.second == "")
+        // nothing left
+        break;
+      In = SP.second;
+      // collect series of removals
+      SmallVector<StringRef, 8> Removals;
+      do {
+        auto RS = In.split(SearchRSuffix);
+        Removals.emplace_back(RS.first);
+        In = RS.second;
+      } while (In.consume_front(SearchRPrefix));
+
+      // match against as many addition lines as possible
+      unsigned J = 0;
+      std::optional<StringRef> UnmatchedAddition;
+      while (J < Removals.size()) {
+        // Is there an addition line?
+        if (!In.consume_front(SearchAPrefix))
+          break;
+        // Get addition line
+        auto AP = In.split(SearchASuffix);
+        UnmatchedAddition = AP.first;
+        In = AP.second;
+        auto Line = merge(Removals[J], AP.first);
+        if (!Line)
+          break;
+        Out += *Line;
+        UnmatchedAddition.reset();
+        J++;
+      }
+      // Dump the remaining removal lines
+      while (J < Removals.size())
+        Out += RColourOn + RPrefix + Removals[J++].str() + RColourOff + NewLine;
+      // Is there a waiting addition line?
+      if (UnmatchedAddition)
+        Out += SearchAPrefix + UnmatchedAddition->str() + SearchASuffix;
+    }
+    return Out;
+  }
+
+  // Return the merging of lines \p S1 and \p S2 or None if they cannot
+  // be merged.
+  std::optional<std::string> merge(StringRef S1, StringRef S2) {
+    SmallVector<StringRef, 4> Rs, As;
+    SmallVector<char, 4> RPrefixChars, APrefixChars;
+    splitString(S1, Rs, RPrefixChars);
+    assert(Rs.size() == RPrefixChars.size() &&
+           "Invalid results from splitString");
+    // Does it have an id or attribute in it?
+    if (Rs.size() == 1)
+      return {};
+    splitString(S2, As, APrefixChars);
+    assert(As.size() == APrefixChars.size() &&
+           "Invalid results from splitString");
+    // Didn't split up same way so not a match
+    if (Rs.size() != As.size() || Rs[0] != As[0] ||
+        RPrefixChars[0] != APrefixChars[0])
+      return {};
+    std::string S;
+    if (NCPrefix)
+      S += RColourOn + *NCPrefix + RColourOff;
+    S += CColourOn + Rs[0].str();
+    for (size_t I = 1; I < Rs.size(); ++I) {
+      // Did they split on the same character?
+      if (RPrefixChars[I] != APrefixChars[I])
+        return {};
+
+      // Just add it if they match
+      if (Rs[I] == As[I]) {
+        S += RPrefixChars[I] + Rs[I].str();
+        continue;
+      }
+      // Pull out the id or number
+      Regex IdRx("[-a-zA-Z$._0-9]+");
+      std::string Error;
+      // Get the removed part other than the id
+      std::string Removed = IdRx.sub("", Rs[I].str(), &Error);
+      if (Error != "")
+        return {};
+      // Get the added part other than the id
+      std::string Added = IdRx.sub("", As[I].str(), &Error);
+      if (Error != "")
+        return {};
+      // Do the added and removed parts match?
+      if (Removed != Added)
+        return {};
+      // merge it
+      S += CColourOff + SearchRPrefix + RPrefixChars[I] +
+           Rs[I].drop_back(Removed.size()).str() + RColourOff + SearchAPrefix +
+           RPrefixChars[I] + As[I].drop_back(Added.size()).str() + AColourOff +
+           CColourOn + Removed;
+    }
+    return {S + NewLine + CColourOff};
+  }
+
+protected:
+  void splitString(StringRef S, SmallVectorImpl<StringRef> &A,
+                   SmallVectorImpl<char> &Prefixes) {
+    Prefixes.push_back('\0');
+    while (true) {
+      size_t Idx = S.find_first_of("%@!#");
+      if (Idx == StringRef::npos)
+        break;
+
+      // Push this split.
+      A.push_back(S.slice(0, Idx));
+      Prefixes.push_back(S[Idx]);
+
+      // Jump forward.
+      S = S.slice(Idx + 1, StringRef::npos);
+    }
+
+    // Push the tail.
+    A.push_back(S);
+  }
+
+  const std::string RColourOn;
+  const std::string RPrefix;
+  const std::string RColourOff;
+  const std::string AColourOn;
+  const std::string APrefix;
+  const std::string AColourOff;
+  const std::string CColourOn;
+  const std::string CPrefix;
+  const std::optional<std::string> NCPrefix;
+  const std::string CColourOff;
+  const std::string NewLine;
+  const std::string SearchRPrefix;
+  const std::string SearchRSuffix;
+  const std::string SearchAPrefix;
+  const std::string SearchASuffix;
+  const std::string Removed;
+  const std::string Added;
+  const std::string NoChange;
+};
+
+class InlineDiffHandler : public DiffHandler {
+public:
+  InlineDiffHandler(bool UseColour)
+      : DiffHandler(UseColour ? "\033[31m" : "", "-",
+                    UseColour ? "\033[0m" : "", UseColour ? "\033[32m" : "",
+                    "+", UseColour ? "\033[0m" : "", "", " ", {"*"}, "", "\n") {
+  }
+
+  std::string diff(StringRef Before, StringRef After) {
+    return mergeLines(doSystemDiff(Before, After, Removed, Added, NoChange));
+  }
+};
+
+class DotCfgDiffHandler : public DiffHandler {
+public:
+  DotCfgDiffHandler()
+      : DiffHandler("<FONT COLOR=\"" + BeforeColour +"\">", "", "</FONT>",
+                    "<FONT COLOR=\"" + AfterColour +"\">", "", "</FONT>",
+                    "<FONT COLOR=\"" + CommonColour +"\">", "", {},
+                    "</FONT>", "<BR align=\"left\"/>") {}
+
+  std::string diff(StringRef Before, StringRef After) {
+    std::string Diff = doSystemDiff(Before, After, Removed, Added, NoChange);
+
+    // Diff adds in some empty colour changes which are not valid HTML
+    // so remove them.  Colours are all lowercase alpha characters (as
+    // listed in https://graphviz.org/pdf/dotguide.pdf).
+    Regex R("<FONT COLOR=\"\\w+\"></FONT>");
+    while (true) {
+      std::string Error;
+      std::string S = R.sub("", Diff, &Error);
+      if (Error != "")
+        return Error;
+      if (S == Diff) {
+        return mergeLines(Diff);
+      }
+      Diff = S;
+    }
+    llvm_unreachable("should not get here");
+  }
+};
+
 } // namespace
 
 template <typename T> ChangeReporter<T>::~ChangeReporter() {
   assert(BeforeStack.empty() && "Problem with Change Printer stack.");
 }
 
 template <typename T>
 void ChangeReporter<T>::saveIRBeforePass(Any IR, StringRef PassID,
void InLineChangePrinter::handleFunctionCompare(
   if (InModule)
     Out << "\n*** IR for function " << Name << " ***\n";
 
   FuncDataT<EmptyData>::report(
       Before, After,
       [&](const BlockDataT<EmptyData> *B, const BlockDataT<EmptyData> *A) {
         StringRef BStr = B ? B->getBody() : "\n";
         StringRef AStr = A ? A->getBody() : "\n";
-        const std::string Removed =
-            UseColour ? "\033[31m-%l\033[0m\n" : "-%l\n";
-        const std::string Added = UseColour ? "\033[32m+%l\033[0m\n" : "+%l\n";
-        const std::string NoChange = " %l\n";
-        Out << doSystemDiff(BStr, AStr, Removed, Added, NoChange);
+        static InlineDiffHandler DH(UseColour);
+        Out <<  DH.diff(BStr, AStr);
       });
 }
 
 void InLineChangePrinter::registerCallbacks(PassInstrumentationCallbacks &PIC) {
   if (PrintChanged == ChangePrinter::DiffVerbose ||
       PrintChanged == ChangePrinter::DiffQuiet ||
       PrintChanged == ChangePrinter::ColourDiffVerbose ||
       PrintChanged == ChangePrinter::ColourDiffQuiet)
for (unsigned I = 0; I < 2; ++I) {
       SR[I] = Data[I]->getBody();
       // drop initial '\n' if present
       if (SR[I][0] == '\n')
         SR[I] = SR[I].drop_front();
       // drop predecessors as they can be big and are redundant
       SR[I] = SR[I].drop_until([](char C) { return C == '\n'; }).drop_front();
     }
 
-    SmallString<80> OldLineFormat = formatv(
-        "<FONT COLOR=\"{0}\">%l</FONT><BR align=\"left\"/>", BeforeColour);
-    SmallString<80> NewLineFormat = formatv(
-        "<FONT COLOR=\"{0}\">%l</FONT><BR align=\"left\"/>", AfterColour);
-    SmallString<80> UnchangedLineFormat = formatv(
-        "<FONT COLOR=\"{0}\">%l</FONT><BR align=\"left\"/>", CommonColour);
-    std::string Diff = Data[0]->getLabel().str();
-    Diff += ":\n<BR align=\"left\"/>" +
-            doSystemDiff(makeHTMLReady(SR[0]), makeHTMLReady(SR[1]),
-                         OldLineFormat, NewLineFormat, UnchangedLineFormat);
+    static DotCfgDiffHandler DH;
 
-    // Diff adds in some empty colour changes which are not valid HTML
-    // so remove them.  Colours are all lowercase alpha characters (as
-    // listed in https://graphviz.org/pdf/dotguide.pdf).
-    Regex R("<FONT COLOR=\"\\w+\"></FONT>");
-    while (true) {
-      std::string Error;
-      std::string S = R.sub("", Diff, &Error);
-      if (Error != "")
-        return Error;
-      if (S == Diff)
-        return Diff;
-      Diff = S;
-    }
-    llvm_unreachable("Should not get here");
+    return Data[0]->getLabel().str() + ":\n<BR align=\"left\"/>" +
+      DH.diff(makeHTMLReady(SR[0]), makeHTMLReady(SR[1]));
   }
 
   // Put node out in the appropriate colour.
   assert(!Data[1] && "Data[1] is set unexpectedly.");
   std::string Body = makeHTMLReady(Data[0]->getBody());
   const StringRef BS = Body;
   StringRef BS1 = BS;
   // Drop leading newline, if present.