Makepatch doesn't always include quite the right changes

Bugs
1

Connor Smith suggests there might be a fencepost error that could be remedied with:

diff --git a/src/cset.c b/src/cset.c
index 27ba3d9ae..4841b2e56 100644
--- a/src/cset.c
+++ b/src/cset.c
@@ -755,7 +755,7 @@ doDiff(sccs *sc)
                printf("\n");
                return;
        }
-       e = PARENT(sc, e);
+       e--;
        if (e == d) return;
        sccs_diffs(sc, REV(sc, e), REV(sc, d), &dop, stdout);
 }

… and offers this test case from bk’s own source:

cosmith@hilbert:~/tmp/work/bk-7.3.1ce$ bk changes -v -d'$if(:REPOTYPE:=product){$if(:CHANGESET:){${1=:REV:}}$else{$if(:MERGE:){ChangeSet@$1\t:GFILE:@:REV:\n}}}' | head
ChangeSet@1.2869        src/Makefile@1.552
ChangeSet@1.2869        src/utils/Makefile@1.67
ChangeSet@1.2859        src/slib.c@1.1073
ChangeSet@1.2858        src/csetprune.c@1.122
ChangeSet@1.2858        src/fast-export.c@1.17
ChangeSet@1.2858        src/ndiff.c@1.35
ChangeSet@1.2858        src/sccs.h@1.867
ChangeSet@1.2858        src/slib.c@1.1072
ChangeSet@1.2831.1.2    src/ndiff.c@1.31.1.1
ChangeSet@1.2831.1.2    src/slib.c@1.1068.1.1
cosmith@hilbert:~/tmp/work/bk-7.3.1ce$ bk changes -v -d'$if(:GFILE:=src/utils/Makefile){:GFILE:@:REV:\n}' -r1.2868..1.2869
src/utils/Makefile@1.67
src/utils/Makefile@1.66
cosmith@hilbert:~/tmp/work/bk-7.3.1ce$ bk-graph -r1.64..1.67 src/utils/Makefile
* src/utils/Makefile@1.67, 2016-07-05 13:07:32-04:00, wscott@x99.wscott.bitkeeper.com +0 -0
|\
| * src/utils/Makefile@1.65.1.1, 2016-07-05 13:07:22-04:00, wscott@x99.wscott.bitkeeper.com +1 -0
* | src/utils/Makefile@1.66, 2016-07-01 17:02:39-04:00, wscott@x99.wscott.bitkeeper.com +1 -0
|/
* src/utils/Makefile@1.65, 2016-04-21 14:29:35-07:00, ob@dirac.bitkeeper.com +6 -6
cosmith@hilbert:~/tmp/work/bk-7.3.1ce$ bkargs='bk makepatch -d -r1.2868..1.2869'; diff -u <($bkargs) <(~/tmp/work/bitkeeper/src/$bkargs)
--- /dev/fd/63  2024-01-24 16:20:18.870258417 +0000
+++ /dev/fd/62  2024-01-24 16:20:18.870258417 +0000
@@ -5,6 +5,14 @@
 # Host:        hilbert.dev.bluearc.com
 # Root:        /home/cosmith/tmp/work/bk-7.3.1ce

+#--- 1.392.1.2/BitKeeper/etc/attr      2016-07-05 15:09:19 +01:00
+#+++ 1.394/BitKeeper/etc/attr  2016-07-05 18:07:32 +01:00
+#@@ -5,4 +5,4 @@
+# @ID
+# lm@lm.bitmover.com|ChangeSet|19990319224848|02682|B:1000:6a5ce40345b2dee1
+# @VERSION
+#-20160701210239
+#+20160630190712
 #--- 1.23/BitKeeper/etc/ignore 2016-06-06 18:16:53 +01:00
 #+++ 1.24/BitKeeper/etc/ignore 2016-07-01 22:02:39 +01:00
 #@@ -128,3 +128,4 @@
@@ -590,16 +598,16 @@
 #      out("\r\n");
 #      out("Cache-Control: no-cache\r\n");     /* for http 1.1 */
 #      out("Pragma: no-cache\r\n");            /* for http 1.0 */
-#--- 1.66/src/utils/Makefile   2016-07-01 22:02:39 +01:00
+#--- 1.65.1.1/src/utils/Makefile       2016-07-05 18:07:22 +01:00
 #+++ 1.67/src/utils/Makefile   2016-07-05 18:07:32 +01:00
-#@@ -42,6 +42,7 @@
-#         SYS=unix
-#      EXE=
-#      EXT=.bin
-#+     LIBS=-lz
-#      H=../unix.h
-#      CFLAGS=-Os
-#      LD=$(CC)
+#@@ -12,6 +12,7 @@
+# # See the License for the specific language governing permissions and
+# # limitations under the License.
+#
+#+BK=../bk
+#
+#
+# # Override Solaris make.rules
 #--- 1.59/src/bkd_version.c    2016-03-09 13:22:25 +00:00
 #+++ 1.60/src/bkd_version.c    2016-07-01 22:02:39 +01:00
 #@@ -71,7 +71,7 @@
@@ -706,7 +714,7 @@
 # W=-Wall -Wno-parentheses -Wno-strict-aliasing
 #

-# Diff checksum=2170eeaa
+# Diff checksum=076c4ebd


 # Patch vers:  1.4
cosmith@hilbert:~/tmp/work/bk-7.3.1ce$

… wherein we see that the shipping makepatch missed changes and included an extra one.

Our-ref D158146.

2

Good find. bk makepatch -d doesn’t use good graph math in a number of ways. The Newfie path uses the file tip, even if asking for an old patch like you are. The diff path would use something like librange.c:range_unrange() but that uncolors D_SET, but the idea is right: to have a diff between 2 nodes color a region, then given the colored region, get the 2 nodes back. We want the newest D_SET colored for one, and the newest PARENT of a colored node, which is uncolored for the other. In the case you show, the Makefile has a merge node with one parent colored and other other uncolored. The existing code just happens to pick the wrong one. Your fix happens to pick the right one, but isn’t the right fix as it does use the graph to find the other. This is better:

===== cset.c 1.341 vs edited =====
--- 1.341/src/cset.c    2018-11-21 06:59:43 -05:00
+++ edited/src/cset.c   2026-04-25 19:29:57 -04:00
@@ -734,29 +734,33 @@
 private void
 doDiff(sccs *sc)
 {
-       ser_t   d, e = 0;
+       ser_t   d, p, e = 0;
        df_opt  dop = {0};
+       int     j;

        dop.out_unified = 1;
        if (CSET(sc)) return;           /* no changeset diffs */
        for (d = TABLE(sc); d >= TREE(sc); d--) {
                if (FLAGS(sc, d) & D_SET) {
-                       e = d;
-               } else if (e) {
-                       break;
+                       unless (e) e = d;
+                       EACH_PARENT(sc, d, p, j) {
+                               unless (FLAGS(sc, p) & D_SET) {
+                                       d = p;
+                                       goto breakout;
+                               }
+                       }
                }
        }
-       for (d = TABLE(sc); (d >= TREE(sc)) && !(FLAGS(sc, d) & D_SET); d--);
-       if (!d) return;
-       unless (PARENT(sc, e)) {
+    breakout:
+       unless (e) return;
+       unless (d) {
                printf("--- New file ---\n+++ %s\t%s\n",
                    sc->gfile, delta_sdate(sc, sccs_ino(sc)));
-               sccs_get(sc, 0, 0, 0, 0, SILENT, 0, stdout);
+               sccs_get(sc, REV(sc, e), 0, 0, 0, SILENT, 0, stdout);
                printf("\n");
                return;
        }
-       e = PARENT(sc, e);
-       if (e == d) return;
+       if (e == d) return; /* really an assert - cannot happen */
        sccs_diffs(sc, REV(sc, e), REV(sc, d), &dop, stdout);
 }

Enough has rotted that it would take a little work to get a test environment up. I also hit some problems with gcc where it compiles but core dumps, but clang seems to work. This has been sitting here more than a year, so may not be an issue. All that said, I’ll make a local repo to at least document this part and make notes about a test case.

3

Sigh, had the diff backwards. Should be:

sccs_diffs(sc, REV(sc, d), REV(sc, e), &dop, stdout);

4

Thinking about this as I slept (just like the old days!), a one sided graph difference (in set language, A & ~B) doesn’t necessarily form a lattice, but could have multiple roots: A,B,C..D. That is, in A…B, if A is not in the history of B, then the greatest common nodes to both A and B could be a list of more than one. While parts of BK do things to activate that version in a diff, this code doesn’t. bk makepatch is seldom used manually, while being fundamental to how pull works. As such, this is the first time I’ve seen -d used. If you want it to be correct, then you need to say what you think correct is. BK can activate the set of deltas that compute when naming multiple tips, but in some ways, it can be non-sense. That’s why smerge came into being: to make sense of a merge given both the internal structure of the weave, graph and set, plus the human level of what a merge means through a set of heuristics. In non-bk terms, a multi-tip activation is really a DAG of linked tokens, not a strict sequence. All that to say, while the patch I mentioned “works” in your case, it is because the lower bound is in the history of the upper bound. In the general case, it requires more of a discussion. The range_unrange() way includes a D_INVALID response if the D_SET region can’t be expressed as a one sided difference of 2 graph nodes. Maybe that’s what you would like or maybe not.

5

Oh, there are three replies here that I hadn’t been alerted to. This is still an ongoing pain for us and I’d been thinking about deploying Connor’s patch, as we’d gotten tumbleweed here, far as I knew, and it had seemed to work in cases where the stock code didn’t. We only use this in one way: to help decide whether to accept changes, where makepatch is always given -r$(bk repogca)… as its revision range. Perhaps the problem is solvable in such cases, in which case failing out in more difficult cases would be fine by us. I hope that answers the “you need to say what you think correct is” question, but, while I felt like I understood all the words, I felt like I understood none of the sentences, so I probably haven’t answered it. I’m even boggled by the idea that this line:

    sccs_diffs(sc, REV(sc, e), REV(sc, d), &dop, stdout);

… should apparently have been:

    sccs_diffs(sc, REV(sc, d), REV(sc, e), &dop, stdout);

Surely we’d have noticed the patch being backwards.

6

@rsmith I can confirm that your patch does still pass all the existing regressions.

If you play with my Experimental bazel branch builds will work a little better.

7

I think I meant to my patch. I’ll wake up neurons later.

I felt like I understood none of the sentences

I can explain with a diagram and code example when I’m back.

8

Yay, email alerting of replies is working again, I guess thanks to Wayne’s fix site topic.

I’m afraid any graph theory explanation is likely to just make me cross-eyed as it flies over my head.

We had another previous unseen problem with makepatch -d this last week. We don’t have many binary files under source control but we do have some and makepatch -d included a diff for one. Perhaps it has to, though it was of no use for our human patch review use-case. The change was approved regardless and the output was given to bk receive for application. That calls bk unwrap under the covers and that tries to find either the start of the patch or a wrapping header. If it gets a run of 2 KiB with no newline, it fails. The only diagnostic is a mention of unwrap = 1 in cmd_log. Before I saw further activity here today, I was thinking that we should just drop the unified diffs. I get the impression that hardly anyone looks and well they might not, given that this issue makes them untrustworthy.

9

@martindorey Is this the makepatch -d spec that you would like?

If file is binary, then say either “new binary file” or “binary differs”

Otherwise, if a new file, the Newfie at the correct version.

if the graph difference has multiple roots (possible but not through your use), then output “multiple greatest common ancestor difference”.

Multi GCA example is two people do the same merge of clone repo J and pull repo K. Alice now has repo A with a-merge-cset, and Bob has repo B with b-merge-cset. Alice pulls from Bob, and does a makepatch -d a-merge-cset..b-merge-cset. This is a case where a-merge-cset is not in the history of b-merge-cset and the common history has two sets : J and K.

     A    B
     |\  /|
     | \/ |
     | /\ |
     |/  \|
     J    K

You aren’t tickling that case as you will always have one in the direct history of the other. We have to detect and not continue to give wrong answers that we do now.

My hack above does not do binary detection nor multiple GCA detection.

Also note my hack didn’t have test cases. Real work would include test cases. Also I see @wscott specified gcc 11 for the bazel work. Or the work for clang. @martindorey what are you using to build? I’ll try Wayne’s bagel repo.

10

Spec sounds good to me, though I wouldn’t like you to feel pressured to bend the design to our trifling use-case. Stepping back, I don’t immediately see why we couldn’t use bk export -tpatch -r$(bk repogca).. and maybe fake up the commentary for familiarity, sprinkle some # on each line and glom on the result of makepatch without -d. I wonder why I haven’t visibly considered doing this before. I wonder what it’d do for binaries but, if we’re processing each line, we could spot them and give up on the human readable part.

We’re currently using a binary of Wayne’s:

martind@stormy:~$ bk version
BitKeeper version is bk-7.3.3 for x86_64-glibc23-linux
Built by: wscott@debian40-64.bitkeeper.com in /build/dev-oss-wscott/src
Built on: Sat Dec 29 2018 04:23:45 PST (8 years ago)
Running on: x86_64-glibc23-linux,4.19.0-27-amd64
martind@stormy:~$

… rather than building our own. When I last tried, in connection with this issue, back in 2024, I ran into some bkbits.net issue that seemingly stopped me building the tree I’d had before. I turned to GitHub - bitkeeper-scm/bitkeeper: This is the master copy of the BitKeeper source · GitHub and noted no problem with that, except that it was demeaning to need git to build BitKeeper. I was building on Debian Buster, so with gcc-8.3. We’d need something that ran on Debian Buster, but finding something newer or older to build it on wouldn’t be a problem. We use bazel for something else already, so that’d be a non-issue. Toasted bread products also welcome, more so than autocorrect.

11

@martindorey , I’m wanting to think about a change because that graph code has many issues. Doing a quick read through repogca.c, it’s not clear that doesn’t have issues, though it might not. I didn’t see any. It doesn’t call the range code which is known to cover the corners of graph possibilities.

The repogca does have an undocumented option --only-onewhich outputs "%s: non-unique baseline revision\n", . Even though you don’t hit that condition, I would suggest adding that option as a safety net.