Live set at a disagreeing merge: three throwaway-repo cases

Answer to the cycle-46 direction. The live set at a merge is keys added in any ancestor minus keys revoked in any ancestor (git log X, every commit, not --first-parent). The no-empty-revoke check must run again at the merge: case A has two parents that each pass alone and a merge whose own live set is empty. The per-parent rule (cycle 45) is still needed beside it: in case C the merged set is {k2}, non-empty, and only the per-parent check rejects it.

A first-parent fold gets every merge wrong: {k2} at A (accepts an empty set), {k1 k2 k3} at B (k1 revived), {k1 k2} at C (k1 revived, rejected parent not seen).

live.sh

g() { git -c commit.gpgsign=false -c user.name=t -c user.email=t@t "$@"; }
c() { g commit -q --allow-empty -m "$1"; }
# live set at X: keys added in any ancestor minus keys revoked in any ancestor (all of rev-list X, not --first-parent)
live() { git log --format=%s "$1" | awk '/^add /{a[$2]=1} /^revoke /{r[$2]=1} END{for(k in a) if(!(k in r)) print k}' | sort | tr '\n' ' '; }
# own check: a revoke or a merge must leave its live set non-empty (no-empty-revoke, rerun at merges)
own() { s=$(git log -1 --format=%s "$1"); n=$(git log -1 --format=%P "$1" | wc -w); l=$(live "$1")
  if { [ "${s#revoke}" != "$s" ] || [ "$n" -gt 1 ]; } && [ -z "${l// }" ]; then echo "no-empty-revoke: own live set empty"; else echo ok; fi; }
verdict() { for p in $(git log -1 --format=%P "$1"); do [ "$(verdict "$p")" = ok ] || { echo "REJECT by per-parent: parent '$(git log -1 --format=%s "$p")' rejected"; return; }; done
  o=$(own "$1"); [ "$o" = ok ] && echo ok || echo "REJECT by $o"; }
show() { printf '%-12s live={%s} %s\n' "$(git log -1 --format=%s "$1")" "$(live "$1")" "$(verdict "$1")"; }

run.sh

#!/usr/bin/env bash
# Throwaway repo: each commit's subject is "add kN" or "revoke kN".
set -e
rm -rf r && git init -q r && cd r
. ../live.sh
run() { git checkout -q --orphan "$1"; for m in $2; do c "${m/_/ }"; done; b=$(git rev-parse HEAD)
  git checkout -q -b "$1-L" "$b"; for m in $3; do c "${m/_/ }"; done; L=$(git rev-parse HEAD)
  git checkout -q -b "$1-R" "$b"; for m in $4; do c "${m/_/ }"; done; R=$(git rev-parse HEAD)
  git checkout -q "$1-L"; g merge -q --no-ff -m "merge $1" "$1-R"
  echo "== $1: base [$2] | L [$3] | R [$4]"; show "$b"; show "$L"; show "$R"; show HEAD
  echo "   first-parent fold: {$(git log --first-parent --format=%s HEAD | awk '/^add /{a[$2]=1} /^revoke /{r[$2]=1} END{for(k in a) if(!(k in r)) print k}' | sort | tr '\n' ' ')}"; }
run A "add_k1 add_k2" "revoke_k1" "revoke_k2"
run B "add_k1 add_k3" "add_k2" "revoke_k1"
run C "add_k1" "add_k2" "revoke_k1"

Output of bash run.sh 2>/dev/null

== A: base [add_k1 add_k2] | L [revoke_k1] | R [revoke_k2]
add k2       live={k1 k2 } ok
revoke k1    live={k2 } ok
revoke k2    live={k1 } ok
merge A      live={} REJECT by no-empty-revoke: own live set empty
   first-parent fold: {k2 }
== B: base [add_k1 add_k3] | L [add_k2] | R [revoke_k1]
add k3       live={k1 k3 } ok
add k2       live={k1 k2 k3 } ok
revoke k1    live={k3 } ok
merge B      live={k2 k3 } ok
   first-parent fold: {k1 k2 k3 }
== C: base [add_k1] | L [add_k2] | R [revoke_k1]
add k1       live={k1 } ok
add k2       live={k1 k2 } ok
revoke k1    live={} REJECT by no-empty-revoke: own live set empty
merge C      live={k2 } REJECT by per-parent: parent 'revoke k1' rejected
   first-parent fold: {k1 k2 }

Opposite edits to one key: only rule 1 gives one answer

Case E, the one merge-readd-is-a-no-op.md left open. Base adds k1 and k2. Left revokes k1. Right revokes k2, then adds k1. Both parents touch k1, in opposite directions. The same history is built twice; only the timestamps of the two k1 commits are swapped.

Commands (throwaway repo, empty commits, subject = event)

g(){ git -c commit.gpgsign=false -c core.hooksPath=/dev/null "$@"; }
d(){ echo "2026-01-01T00:0$1:00Z"; }   # minute $1
c(){ GIT_AUTHOR_DATE="$(d "$2")" GIT_COMMITTER_DATE="$(d "$2")" g commit -q --allow-empty -m "$1"; }
live(){ comm -23 <(git log --format=%s "$1" | awk '$1=="add"{print $2}' | sort -u) \
                 <(git log --format=%s "$1" | awk '$1=="revoke"{print $2}' | sort -u) | xargs; }
fold(){ git log "$@" --reverse --format=%s | awk '$1=="add"||$1=="revoke"{s[$2]=$1} END{for(k in s) if(s[k]=="add") printf "%s ", k; print ""}' | xargs; }
build(){ # $1 = minute of left's "revoke k1", $2 = minute of right's "add k1"
  g init -q -b main; c "add k1" 1; c "add k2" 2; g branch base
  g checkout -q -b left base;  c "revoke k1" "$1"
  g checkout -q -b right base; c "revoke k2" 3; c "add k1" "$2"
  g checkout -q left; GIT_AUTHOR_DATE="$(d 9)" GIT_COMMITTER_DATE="$(d 9)" g merge -q --no-ff right -m "merge right"
  echo "left  (HEAD^1): {$(live HEAD^1)}"; echo "right (HEAD^2): {$(live HEAD^2)}"; echo "merge: {$(live HEAD)}"
  echo "fold --date-order: {$(fold --date-order HEAD)}"
  echo "fold --topo-order: {$(fold --topo-order HEAD)}"
}
mkdir r1 && (cd r1 && build 4 5)   # left's revoke older than right's add
mkdir r2 && (cd r2 && build 5 4)   # left's revoke newer than right's add

Output

## r1: left revoke k1 at 00:04, right add k1 at 00:05
left  (HEAD^1): {k2}
right (HEAD^2): {k1}
merge: {}
fold --date-order: {k1}
fold --topo-order: {k1}
## r2: left revoke k1 at 00:05, right add k1 at 00:04
left  (HEAD^1): {k2}
right (HEAD^2): {k1}
merge: {}
fold --date-order: {}
fold --topo-order: {k1}

(HEAD^1/HEAD^2, not left/right: after the merge left points at the merge commit. An earlier run used the branch names and reported left as {}.)

Both parents pass alone in both repos, so the cycle-45 per-parent check lets each merge through. Only the rerun on the merged set rejects it.

What this adds

1. The last-event fold answers differently for the same graph. In r2, --date-order gives {} (reject) and --topo-order gives {k1} (accept). Swapping two commit timestamps (r1 against r2) flips the --date-order verdict. Commit dates are set by whoever commits, so under that fold an author decides whether a revoke survives a merge.
2. Rule 1 gives {} in all four runs. It reads no order and no dates, only the sets of add and revoke events in the ancestry.
3. Right's add k1 is a no-op under rule 1 even on its own side: k1 was never revoked there, so right is {k1} with or without it. A merge-time conflict between "add" and "revoke" of one key resolves to revoke because a revoke anywhere in the ancestry is final.
4. Answer to this cycle's direction across cases A-E: the merge's live set is (adds in the whole ancestry) minus (revokes in the whole ancestry), and no-empty-revoke must run again at the merge. Cases A, D and E each have two passing parents and an empty merge.

A re-add on one parent cannot save the merge

Case D, beside A-C in merge-live-set-three-cases.md. Base adds k1 and k2. Left revokes k2. Right revokes k1 and then adds k1 again.

Rule 1 says the live set is the keys added in any ancestor minus the keys revoked in any ancestor. Under that rule a revoke is permanent, so a re-add does nothing, on a single line of history or at a merge.

Commands (throwaway repo, empty commits, subject = event)

c(){ git commit -q --allow-empty -m "$1"; }
live(){ comm -23 <(git log --format=%s "$1" | awk '$1=="add"{print $2}' | sort -u) \
                 <(git log --format=%s "$1" | awk '$1=="revoke"{print $2}' | sort -u); }
c "add k1"; c "add k2"; git branch base
git checkout -b left base;  c "revoke k2"
git checkout -b right base; c "revoke k1"; c "add k1"
echo "left:  {$(live left)}"; echo "right: {$(live right)}"
# last-event fold, for comparison: the newest add/revoke of each key wins
fold(){ git log "$@" --reverse --format=%s | awk '{s[$2]=$1} END{for(k in s) if(s[k]=="add") printf "%s ", k; print ""}'; }
fold right
git checkout left; git merge --no-ff right -m "merge right"
echo "merge: {$(live HEAD)}"
fold --topo-order HEAD; fold --date-order HEAD

Output

left:  {k1}
right: {k2}
right ordered fold (last event per key wins): {k1 k2}
merge: {}
merge ordered fold --topo-order: {k1}
merge ordered fold --date-order: {k1}

*   d166b3c merge right
|\
| * ae5ce59 add k1
| * ace7de1 revoke k1
* | a1df110 revoke k2
|/
* e9c0aea add k2
* 3f35a82 add k1

Both parents pass on their own, so the cycle-45 per-parent check does not reject the merge. The rerun on the merged set does.

What this adds

1. With a "last event wins" fold, the right side keeps k1, and so does the merge ({k1}, passes). Rule 1 rejects the same merge. The two folds disagree about whether the merge is valid, and the only difference is whether a re-add counts.
2. "Last event wins" needs an order of events across both parents, and a merge has no such order. Here both git orders agree because only the right side touches k1. If both parents had touched the same key in opposite directions, the answer would depend on which parent git log lists last (not run here; the next stuff item could test it). Rule 1 needs no ordering. That is a reason to keep it.
3. The cost of rule 1 is that a revoked key cannot come back. Bringing it back means adding a new key id (k1b), not adding k1 again. The tool has to reject add k1 after a revoke of k1, or at least warn about it. Otherwise the author believes k1 is live when it is not.