diff3: Add support for -A

Diff3 in -A mode generates an ed script to show how the 3 files and
brackets changes that conflict. The ed script generated should when
applied leave familiar merge conflict markers in a patched file.

Diff3 output is not documented, this feature has been arrived at by
comparing bsd diff3 output to gnu diff3 output until they were made to
agree. There are likely to still be differences between these formats.

The gnu diff3 guide is actually quite good at explaining how diff3
output should appear, but it doesn't cover every form of output from
diff3.

https://www.gnu.org/software/diffutils/manual/diffutils.html#Comparing-Three-Files

Discussed with:	pstef, kevans
Sponsored by:	Klara, Inc.

5 files changed, 157 insertions, 8 deletions

diff --git a/usr.bin/diff3/diff3.1 b/usr.bin/diff3/diff3.1
index 2cf1e57cb74e..f0fd481c75f1 100644
--- a/usr.bin/diff3/diff3.1
+++ b/usr.bin/diff3/diff3.1
@@ -30,7 +30,7 @@
 .\"     @(#)diff3.1	8.2 (Berkeley) 4/18/94
 .\" $FreeBSD$
 .\"
-.Dd August 23, 2021
+.Dd April 19, 2022
 .Dt DIFF3 1
 .Os
 .Sh NAME
@@ -38,7 +38,7 @@
 .Nd 3-way differential file comparison
 .Sh SYNOPSIS
 .Nm diff3
-.Op Fl 3aEeiTXx
+.Op Fl 3AaEeiTXx
 .Op Fl Fl diff-program Ar program
 .Op Fl Fl strip-trailing-cr
 .Op Fl L | Fl Fl label Ar label1
@@ -71,6 +71,8 @@ Produces an output script suitable for
 with changes
 specific only to
 .Ar file3 .
+.It Fl A Fl Fl show-all
+Output all changes, bracketing conflicts.
 .It Fl a , Fl Fl text
 Treat all files as ASCII.
 .It Fl E , Fl Fl show-overlap
diff --git a/usr.bin/diff3/diff3.c b/usr.bin/diff3/diff3.c
index 97fccc739ebe..5df6357065fc 100644
--- a/usr.bin/diff3/diff3.c
+++ b/usr.bin/diff3/diff3.c
@@ -100,6 +100,14 @@ struct range {
 };
 
 struct diff {
+#define DIFF_TYPE2 2
+#define DIFF_TYPE3 3
+	int type;
+#if DEBUG
+	char *line;
+#endif	/* DEBUG */
+
+	/* Ranges as lines */
 	struct range old;
 	struct range new;
 };
@@ -129,10 +137,11 @@ static int oflag;		/* indicates whether to mark overlaps (-E or -X) */
 static int strip_cr;
 static char *f1mark, *f2mark, *f3mark;
 static const char *oldmark = "<<<<<<<";
+static const char *orgmark = "|||||||";
 static const char *newmark = ">>>>>>>";
 
 static bool duplicate(struct range *, struct range *);
-static int edit(struct diff *, bool, int);
+static int edit(struct diff *, bool, int, int);
 static char *getchange(FILE *);
 static char *get_line(FILE *, size_t *);
 static int readin(int fd, struct diff **);
@@ -143,6 +152,7 @@ static void merge(int, int);
 static void prange(struct range *, bool);
 static void repos(int);
 static void edscript(int) __dead2;
+static void Ascript(int) __dead2;
 static void increase(void);
 static void usage(void) __dead2;
 static void printrange(FILE *, struct range *);
@@ -189,6 +199,10 @@ readin(int fd, struct diff **dd)
 	if (f == NULL)
 		err(2, "fdopen");
 	for (i = 0; (p = getchange(f)); i++) {
+#if DEBUG
+		(*dd)[i].line = strdup(p);
+#endif	/* DEBUG */
+
 		if (i >= szchanges - 1)
 			increase();
 		a = b = (int)strtoimax(p, &p, 10);
@@ -309,6 +323,9 @@ merge(int m1, int m2)
 				keep(1, &d2->new);
 				change(3, &d2->new, false);
 				change(2, &d2->old, false);
+			} else if (Aflag || mflag) {
+				// XXX-THJ: What does it mean for the second file to differ?
+				j = edit(d2, dup, j, DIFF_TYPE2);
 			}
 			d2++;
 			continue;
@@ -344,8 +361,10 @@ merge(int m1, int m2)
 				change(2, &d2->old, false);
 				d3 = d1->old.to > d1->old.from ? d1 : d2;
 				change(3, &d3->new, false);
-			} else
-				j = edit(d1, dup, j);
+			} else {
+				j = edit(d1, dup, j, DIFF_TYPE3);
+			}
+			dup = false;
 			d1++;
 			d2++;
 			continue;
@@ -369,7 +388,10 @@ merge(int m1, int m2)
 			d1->new.to = d2->new.to;
 		}
 	}
-	if (eflag)
+
+	if (Aflag)
+		Ascript(j);
+	else if (eflag)
 		edscript(j);
 }
 
@@ -498,7 +520,7 @@ repos(int nchar)
  * collect an editing script for later regurgitation
  */
 static int
-edit(struct diff *diff, bool dup, int j)
+edit(struct diff *diff, bool dup, int j, int difftype)
 {
 
 	if (((dup + 1) & eflag) == 0)
@@ -507,6 +529,12 @@ edit(struct diff *diff, bool dup, int j)
 	overlap[j] = !dup;
 	if (!dup)
 		overlapcnt++;
+
+	de[j].type = difftype;
+#if DEBUG
+	de[j].line = diff->line;
+#endif	/* DEBUG */
+
 	de[j].old.from = diff->old.from;
 	de[j].old.to = diff->old.to;
 	de[j].new.from = diff->new.from;
@@ -574,6 +602,91 @@ edscript(int n)
 	exit(eflag == 0 ? overlapcnt : 0);
 }
 
+/*
+ * Output an edit script to turn mine into yours, when there is a conflict
+ * between the 3 files bracket the changes. Regurgitate the diffs in reverse
+ * order to allow the ed script to track down where the lines are as changes
+ * are made.
+ */
+static void
+Ascript(int n)
+{
+	int startmark;
+	bool deletenew;
+	bool deleteold;
+
+	for (; n > 0; n--) {
+
+		deletenew = (de[n].new.from == de[n].new.to);
+		deleteold = (de[n].old.from == de[n].old.to);
+		startmark = de[n].old.from + (de[n].old.to - de[n].old.from) - 1;
+
+		if (de[n].type == DIFF_TYPE2) {
+			if (!oflag || !overlap[n]) {
+				prange(&de[n].old, deletenew);
+				printrange(fp[2], &de[n].new);
+			} else {
+				startmark = de[n].new.from +
+					(de[n].new.to - de[n].new.from);
+
+				if (!deletenew)
+					startmark--;
+
+				printf("%da\n", startmark);
+				printf("%s %s\n", newmark, f3mark);
+
+				printf(".\n");
+
+				printf("%da\n", startmark -
+					(de[n].new.to - de[n].new.from));
+				printf("%s %s\n", oldmark, f2mark);
+				if (!deleteold)
+					printrange(fp[1], &de[n].old);
+				printf("=======\n.\n");
+			}
+
+		} else if (de[n].type == DIFF_TYPE3) {
+			if (!oflag || !overlap[n]) {
+				prange(&de[n].old, deletenew);
+				printrange(fp[2], &de[n].new);
+			} else {
+				printf("%da\n", startmark);
+				printf("%s %s\n", orgmark, f2mark);
+
+				if (deleteold) {
+					struct range r;
+					r.from = de[n].old.from-1;
+					r.to = de[n].new.to;
+					printrange(fp[1], &r);
+				} else
+					printrange(fp[1], &de[n].old);
+
+				printf("=======\n");
+				printrange(fp[2], &de[n].new);
+			}
+
+			if (!oflag || !overlap[n]) {
+				if (!deletenew)
+					printf(".\n");
+			} else {
+				printf("%s %s\n.\n", newmark, f3mark);
+
+				/*
+				 * Go to the start of the conflict in original
+				 * file and append lines
+				 */
+				printf("%da\n%s %s\n.\n",
+					startmark - (de[n].old.to - de[n].old.from),
+					oldmark, f1mark);
+			}
+		}
+	}
+	if (iflag)
+		printf("w\nq\n");
+
+	exit(overlapcnt > 0);
+}
+
 static void
 increase(void)
 {
diff --git a/usr.bin/diff3/tests/Makefile b/usr.bin/diff3/tests/Makefile
index 91af4d1a6237..fc69dea260e8 100644
--- a/usr.bin/diff3/tests/Makefile
+++ b/usr.bin/diff3/tests/Makefile
@@ -21,6 +21,7 @@ ${PACKAGE}FILES+=	\
 	7.out \
 	8.out \
 	9.out \
-	long-ed.out
+	long-ed.out \
+	long-A.out
 
 .include <bsd.test.mk>
diff --git a/usr.bin/diff3/tests/diff3_test.sh b/usr.bin/diff3/tests/diff3_test.sh
index 0eb08f46a803..8df84b0d8ff2 100755
--- a/usr.bin/diff3/tests/diff3_test.sh
+++ b/usr.bin/diff3/tests/diff3_test.sh
@@ -3,6 +3,7 @@
 atf_test_case diff3
 atf_test_case diff3_lesssimple
 atf_test_case diff3_ed
+atf_test_case diff3_A
 
 diff3_body()
 {
@@ -46,9 +47,19 @@ diff3_ed_body()
 		diff3 -e $(atf_get_srcdir)/long-m.txt $(atf_get_srcdir)/long-o.txt $(atf_get_srcdir)/long-y.txt
 }
 
+diff3_A_body()
+{
+	atf_check -s exit:1 -o file:$(atf_get_srcdir)/8.out \
+		diff3 -A -L 1 -L 2 -L 3 $(atf_get_srcdir)/1.txt $(atf_get_srcdir)/2.txt $(atf_get_srcdir)/3.txt
+
+	atf_check -s exit:1 -o file:$(atf_get_srcdir)/long-A.out \
+		diff3 -A -L long-m.txt -L long-o.txt -L long-y.txt $(atf_get_srcdir)/long-m.txt $(atf_get_srcdir)/long-o.txt $(atf_get_srcdir)/long-y.txt
+}
+
 atf_init_test_cases()
 {
 	atf_add_test_case diff3
 #	atf_add_test_case diff3_lesssimple
 	atf_add_test_case diff3_ed
+	atf_add_test_case diff3_A
 }
diff --git a/usr.bin/diff3/tests/long-A.out b/usr.bin/diff3/tests/long-A.out
new file mode 100644
index 000000000000..2a2e4cbb112d
--- /dev/null
+++ b/usr.bin/diff3/tests/long-A.out
@@ -0,0 +1,22 @@
+24d
+16a
+||||||| long-o.txt
+This line is different in yours and mine, but the different in each
+=======
+This line is different in yours and mine, but the best in yours
+>>>>>>> long-y.txt
+.
+15a
+<<<<<<< long-m.txt
+.
+11a
+>>>>>>> long-y.txt
+.
+10a
+<<<<<<< long-o.txt
+This line is different in yours and mine, but the same
+=======
+.
+8c
+This line is different in yours, much butter
+.