In side-by-side diff, add support for marking individual characters.

[ps-cgit] / ui-ssdiff.c

diff --git a/ui-ssdiff.c b/ui-ssdiff.c
index 56736427a6bdd641278ff877aa3979d880e9fba7..408e620533ac0dd3f61d1f868ec3aeede246f9d7 100644 (file)
--- a/ui-ssdiff.c
+++ b/ui-ssdiff.c
@@ -15,6 +15,52 @@ struct deferred_lines {
 static struct deferred_lines *deferred_old, *deferred_old_last;
 static struct deferred_lines *deferred_new, *deferred_new_last;
 
 static struct deferred_lines *deferred_old, *deferred_old_last;
 static struct deferred_lines *deferred_new, *deferred_new_last;
 

+static char *longest_common_subsequence(char *A, char *B)
+{
+       int i, j, ri;
+       int m = strlen(A);
+       int n = strlen(B);
+       int L[m + 1][n + 1];
+       int tmp1, tmp2;
+       int lcs_length;
+       char *result;
+
+       for (i = m; i >= 0; i--) {
+               for (j = n; j >= 0; j--) {
+                       if (A[i] == '\0' || B[j] == '\0') {
+                               L[i][j] = 0;
+                       } else if (A[i] == B[j]) {
+                               L[i][j] = 1 + L[i + 1][j + 1];
+                       } else {
+                               tmp1 = L[i + 1][j];
+                               tmp2 = L[i][j + 1];
+                               L[i][j] = (tmp1 > tmp2 ? tmp1 : tmp2);
+                       }
+               }
+       }
+
+       lcs_length = L[0][0];
+       result = xmalloc(lcs_length + 2);
+       memset(result, 0, sizeof(*result) * (lcs_length + 2));
+
+       ri = 0;
+       i = 0;
+       j = 0;
+       while (i < m && j < n) {
+               if (A[i] == B[j]) {
+                       result[ri] = A[i];
+                       ri += 1;
+                       i += 1;
+                       j += 1;
+               } else if (L[i + 1][j] >= L[i][j + 1]) {
+                       i += 1;
+               } else {
+                       j += 1;
+               }
+       }
+       return result;
+}
+

 static int line_from_hunk(char *line, char type)
 {
        char *buf1, *buf2;
 static int line_from_hunk(char *line, char type)
 {
        char *buf1, *buf2;


@@ -73,6 +119,17 @@ static char *replace_tabs(char *line)
        return result;
 }
 
        return result;
 }
 

+static int calc_deferred_lines(struct deferred_lines *start)
+{
+       struct deferred_lines *item = start;
+       int result = 0;
+       while (item) {
+               result += 1;
+               item = item->next;
+       }
+       return result;
+}
+

 static void deferred_old_add(char *line, int line_no)
 {
        struct deferred_lines *item = xmalloc(sizeof(struct deferred_lines));
 static void deferred_old_add(char *line, int line_no)
 {
        struct deferred_lines *item = xmalloc(sizeof(struct deferred_lines));


@@ -101,9 +158,45 @@ static void deferred_new_add(char *line, int line_no)
        }
 }
 
        }
 }
 

-static void print_ssdiff_line(char *class, int old_line_no, char *old_line,
-                             int new_line_no, char *new_line)
+static void print_part_with_lcs(char *class, char *line, char *lcs)
+{
+       int line_len = strlen(line);
+       int i, j;
+       char c[2] = " ";
+       int same = 1;
+
+       j = 0;
+       for (i = 0; i < line_len; i++) {
+               c[0] = line[i];
+               if (same) {
+                       if (line[i] == lcs[j])
+                               j += 1;
+                       else {
+                               same = 0;
+                               htmlf("<span class='%s'>", class);
+                       }
+               } else if (line[i] == lcs[j]) {
+                       same = 1;
+                       htmlf("</span>");
+                       j += 1;
+               }
+               html_txt(c);
+       }
+}
+
+static void print_ssdiff_line(char *class,
+                             int old_line_no,
+                             char *old_line,
+                             int new_line_no,
+                             char *new_line, int individual_chars)

 {
 {

+       char *lcs = NULL;
+       if (old_line)
+               old_line = replace_tabs(old_line + 1);
+       if (new_line)
+               new_line = replace_tabs(new_line + 1);
+       if (individual_chars && old_line && new_line)
+               lcs = longest_common_subsequence(old_line, new_line);

        html("<tr>");
        if (old_line_no > 0)
                htmlf("<td class='lineno'>%d</td><td class='%s'>",
        html("<tr>");
        if (old_line_no > 0)
                htmlf("<td class='lineno'>%d</td><td class='%s'>",


@@ -112,15 +205,14 @@ static void print_ssdiff_line(char *class, int old_line_no, char *old_line,
                htmlf("<td class='lineno'></td><td class='%s'>", class);
        else
                htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
                htmlf("<td class='lineno'></td><td class='%s'>", class);
        else
                htmlf("<td class='lineno'></td><td class='%s_dark'>", class);

-

        if (old_line) {
        if (old_line) {

-               old_line = replace_tabs(old_line + 1);
-               html_txt(old_line);
-               free(old_line);
+               if (lcs)
+                       print_part_with_lcs("del", old_line, lcs);
+               else
+                       html_txt(old_line);

        }
 
        html("</td>");
        }
 
        html("</td>");

-

        if (new_line_no > 0)
                htmlf("<td class='lineno'>%d</td><td class='%s'>",
                      new_line_no, class);
        if (new_line_no > 0)
                htmlf("<td class='lineno'>%d</td><td class='%s'>",
                      new_line_no, class);


@@ -128,24 +220,29 @@ static void print_ssdiff_line(char *class, int old_line_no, char *old_line,
                htmlf("<td class='lineno'></td><td class='%s'>", class);
        else
                htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
                htmlf("<td class='lineno'></td><td class='%s'>", class);
        else
                htmlf("<td class='lineno'></td><td class='%s_dark'>", class);

-

        if (new_line) {
        if (new_line) {

-               new_line = replace_tabs(new_line + 1);
-               html_txt(new_line);
-               free(new_line);
+               if (lcs)
+                       print_part_with_lcs("add", new_line, lcs);
+               else
+                       html_txt(new_line);

        }
 
        html("</td></tr>");
        }
 
        html("</td></tr>");

+       if (lcs)
+               free(lcs);
+       if (new_line)
+               free(new_line);
+       if (old_line)
+               free(old_line);

 }
 
 static void print_deferred_old_lines()
 {
        struct deferred_lines *iter_old, *tmp;
 }
 
 static void print_deferred_old_lines()
 {
        struct deferred_lines *iter_old, *tmp;

-

        iter_old = deferred_old;
        while (iter_old) {
                print_ssdiff_line("del", iter_old->line_no,
        iter_old = deferred_old;
        while (iter_old) {
                print_ssdiff_line("del", iter_old->line_no,

-                                 iter_old->line, -1, NULL);
+                                 iter_old->line, -1, NULL, 0);

                tmp = iter_old->next;
                free(iter_old);
                iter_old = tmp;
                tmp = iter_old->next;
                free(iter_old);
                iter_old = tmp;


@@ -155,11 +252,10 @@ static void print_deferred_old_lines()
 static void print_deferred_new_lines()
 {
        struct deferred_lines *iter_new, *tmp;
 static void print_deferred_new_lines()
 {
        struct deferred_lines *iter_new, *tmp;

-

        iter_new = deferred_new;
        while (iter_new) {
        iter_new = deferred_new;
        while (iter_new) {

-               print_ssdiff_line("add", -1, NULL, iter_new->line_no,
-                                 iter_new->line);
+               print_ssdiff_line("add", -1, NULL,
+                                 iter_new->line_no, iter_new->line, 0);

                tmp = iter_new->next;
                free(iter_new);
                iter_new = tmp;
                tmp = iter_new->next;
                free(iter_new);
                iter_new = tmp;


@@ -169,6 +265,9 @@ static void print_deferred_new_lines()
 static void print_deferred_changed_lines()
 {
        struct deferred_lines *iter_old, *iter_new, *tmp;
 static void print_deferred_changed_lines()
 {
        struct deferred_lines *iter_old, *iter_new, *tmp;

+       int n_old_lines = calc_deferred_lines(deferred_old);
+       int n_new_lines = calc_deferred_lines(deferred_new);
+       int individual_chars = (n_old_lines == n_new_lines ? 1 : 0);

 
        iter_old = deferred_old;
        iter_new = deferred_new;
 
        iter_old = deferred_old;
        iter_new = deferred_new;


@@ -176,14 +275,14 @@ static void print_deferred_changed_lines()
                if (iter_old && iter_new)
                        print_ssdiff_line("changed", iter_old->line_no,
                                          iter_old->line,
                if (iter_old && iter_new)
                        print_ssdiff_line("changed", iter_old->line_no,
                                          iter_old->line,

-                                         iter_new->line_no, iter_new->line);
+                                         iter_new->line_no, iter_new->line,
+                                         individual_chars);

                else if (iter_old)
                        print_ssdiff_line("changed", iter_old->line_no,
                else if (iter_old)
                        print_ssdiff_line("changed", iter_old->line_no,

-                                         iter_old->line, -1, NULL);
+                                         iter_old->line, -1, NULL, 0);

                else if (iter_new)
                        print_ssdiff_line("changed", -1, NULL,
                else if (iter_new)
                        print_ssdiff_line("changed", -1, NULL,

-                                         iter_new->line_no, iter_new->line);
-
+                                         iter_new->line_no, iter_new->line, 0);

                if (iter_old) {
                        tmp = iter_old->next;
                        free(iter_old);
                if (iter_old) {
                        tmp = iter_old->next;
                        free(iter_old);


@@ -202,14 +301,12 @@ void cgit_ssdiff_print_deferred_lines()
 {
        if (!deferred_old && !deferred_new)
                return;
 {
        if (!deferred_old && !deferred_new)
                return;

-

        if (deferred_old && !deferred_new)
                print_deferred_old_lines();
        else if (!deferred_old && deferred_new)
                print_deferred_new_lines();
        else
                print_deferred_changed_lines();
        if (deferred_old && !deferred_new)
                print_deferred_old_lines();
        else if (!deferred_old && deferred_new)
                print_deferred_new_lines();
        else
                print_deferred_changed_lines();

-

        deferred_old = deferred_old_last = NULL;
        deferred_new = deferred_new_last = NULL;
 }
        deferred_old = deferred_old_last = NULL;
        deferred_new = deferred_new_last = NULL;
 }


@@ -220,9 +317,7 @@ void cgit_ssdiff_print_deferred_lines()
 void cgit_ssdiff_line_cb(char *line, int len)
 {
        char c = line[len - 1];
 void cgit_ssdiff_line_cb(char *line, int len)
 {
        char c = line[len - 1];

-

        line[len - 1] = '\0';
        line[len - 1] = '\0';

-

        if (line[0] == '@') {
                current_old_line = line_from_hunk(line, '-');
                current_new_line = line_from_hunk(line, '+');
        if (line[0] == '@') {
                current_old_line = line_from_hunk(line, '-');
                current_new_line = line_from_hunk(line, '+');


@@ -232,7 +327,7 @@ void cgit_ssdiff_line_cb(char *line, int len)
                if (deferred_old || deferred_new)
                        cgit_ssdiff_print_deferred_lines();
                print_ssdiff_line("ctx", current_old_line, line,
                if (deferred_old || deferred_new)
                        cgit_ssdiff_print_deferred_lines();
                print_ssdiff_line("ctx", current_old_line, line,

-                                 current_new_line, line);
+                                 current_new_line, line, 0);

                current_old_line += 1;
                current_new_line += 1;
        } else if (line[0] == '+') {
                current_old_line += 1;
                current_new_line += 1;
        } else if (line[0] == '+') {