v2: index forwards (via `git log --reverse')

Since we'll need to expose THREADID to JMAP and IMAP users,
index all messages in the order they were committed to ensure
our `tid' (thread ID) column ascends in mirrors the same way
they do in the source inbox.

This drastically simplifies our code but increases memory
usage of `git-log'.  The next commit will bring memory use
back down at the expense of $TMPDIR usage.

2 files changed, 81 insertions, 260 deletions

diff --git a/lib/PublicInbox/MultiMidQueue.pm b/lib/PublicInbox/MultiMidQueue.pm
deleted file mode 100644
index eb2ecf2f..00000000
--- a/lib/PublicInbox/MultiMidQueue.pm
+++ /dev/null
@@ -1,62 +0,0 @@
-# Copyright (C) 2020 all contributors <meta@public-inbox.org>
-# License: AGPL-3.0+ <https://www.gnu.org/licenses/agpl-3.0.txt>
-
-# temporary queue for public-inbox-index to support multi-Message-ID
-# messages on mirrors of v2 inboxes
-package PublicInbox::MultiMidQueue;
-use strict;
-use SDBM_File; # part of Perl standard library
-use Fcntl qw(O_RDWR O_CREAT);
-use File::Temp 0.19 (); # 0.19 for ->newdir
-my %e = (
-        freebsd => 0x100000,
-        linux => 0x80000,
-        netbsd => 0x400000,
-        openbsd => 0x10000,
-);
-my $O_CLOEXEC = $e{$^O} // 0;
-
-sub new {
-        my ($class) = @_;
-        my $tmpdir = File::Temp->newdir('multi-mid-q-XXXXXX', TMPDIR => 1);
-        my $base = $tmpdir->dirname . '/q';
-        my %sdbm;
-        my $flags = O_RDWR|O_CREAT;
-        if (!tie(%sdbm, 'SDBM_File', $base, $flags|$O_CLOEXEC, 0600)) {
-                if (!tie(%sdbm, 'SDBM_File', $base, $flags, 0600)) {
-                        die "could not tie ($base): $!";
-                }
-                $O_CLOEXEC = 0;
-        }
-
-        bless {
-                cur => 1,
-                min => 1,
-                max => 0,
-                sdbm => \%sdbm,
-                tmpdir => $tmpdir,
-        }, $class;
-}
-
-sub set_oid {
-        my ($self, $i, $oid, $v2w) = @_;
-        $self->{max} = $i if $i > $self->{max};
-        $self->{min} = $i if $i < $self->{min};
-        $self->{sdbm}->{$i} = "$oid\t$v2w->{autime}\t$v2w->{cotime}";
-}
-
-sub get_oid {
-        my ($self, $i, $v2w) = @_;
-        my $rec = $self->{sdbm}->{$i} or return;
-        my ($oid, $autime, $cotime) = split(/\t/, $rec);
-        $v2w->{autime} = $autime;
-        $v2w->{cotime} = $cotime;
-        $oid
-}
-
-sub push_oid {
-        my ($self, $oid, $v2w) = @_;
-        set_oid($self, $self->{cur}++, $oid, $v2w);
-}
-
-1;
diff --git a/lib/PublicInbox/V2Writable.pm b/lib/PublicInbox/V2Writable.pm
index 16556ddc..c04ea5d7 100644
--- a/lib/PublicInbox/V2Writable.pm
+++ b/lib/PublicInbox/V2Writable.pm
@@ -18,10 +18,10 @@ use PublicInbox::OverIdx;
 use PublicInbox::Msgmap;
 use PublicInbox::Spawn qw(spawn popen_rd);
 use PublicInbox::SearchIdx;
-use PublicInbox::MultiMidQueue;
 use IO::Handle; # ->autoflush
 use File::Temp qw(tempfile);
 
+my $x40 = qr/[a-f0-9]{40}/;
 # an estimate of the post-packed size to the raw uncompressed size
 my $PACKING_FACTOR = 0.4;
 
@@ -862,18 +862,6 @@ sub atfork_child {
         $self->{bnote}->[1];
 }
 
-sub mark_deleted ($$$$) {
-        my ($self, $sync, $git, $oid) = @_;
-        return if PublicInbox::SearchIdx::too_big($self, $git, $oid);
-        my $msgref = $git->cat_file($oid);
-        my $mime = PublicInbox::Eml->new($$msgref);
-        my $mids = mids($mime->header_obj);
-        my $chash = content_hash($mime);
-        foreach my $mid (@$mids) {
-                $sync->{D}->{"$mid\0$chash"} = $oid;
-        }
-}
-
 sub reindex_checkpoint ($$$) {
         my ($self, $sync, $git) = @_;
 
@@ -891,107 +879,11 @@ sub reindex_checkpoint ($$$) {
         $sync->{mm_tmp}->atfork_parent;
 }
 
-# only for a few odd messages with multiple Message-IDs
-sub reindex_oid_m ($$$$;$) {
-        my ($self, $sync, $git, $oid, $regen_num) = @_;
-        $self->{current_info} = "multi_mid $oid";
-        my ($num, $mid0, $len);
-        my $msgref = $git->cat_file($oid, \$len);
-        my $mime = PublicInbox::Eml->new($$msgref);
-        my $mids = mids($mime->header_obj);
-        my $chash = content_hash($mime);
-        die "BUG: reindex_oid_m called for <=1 mids" if scalar(@$mids) <= 1;
-
-        for my $mid (reverse @$mids) {
-                delete($sync->{D}->{"$mid\0$chash"}) and
-                        die "BUG: reindex_oid should handle <$mid> delete";
-        }
-        my $over = $self->{over};
-        for my $mid (reverse @$mids) {
-                ($num, $mid0) = $over->num_mid0_for_oid($oid, $mid);
-                next unless defined $num;
-                if (defined($regen_num) && $regen_num != $num) {
-                        die "BUG: regen(#$regen_num) != over(#$num)";
-                }
-        }
-        unless (defined($num)) {
-                for my $mid (reverse @$mids) {
-                        # is this a number we got before?
-                        my $n = $sync->{mm_tmp}->num_for($mid);
-                        next unless defined $n;
-                        next if defined($regen_num) && $regen_num != $n;
-                        ($num, $mid0) = ($n, $mid);
-                        last;
-                }
-        }
-        if (defined($num)) {
-                $sync->{mm_tmp}->num_delete($num);
-        } elsif (defined $regen_num) {
-                $num = $regen_num;
-                for my $mid (reverse @$mids) {
-                        $self->{mm}->mid_set($num, $mid) == 1 or next;
-                        $mid0 = $mid;
-                        last;
-                }
-                unless (defined $mid0) {
-                        warn "E: cannot regen #$num\n";
-                        return;
-                }
-        } else { # fixup bugs in old mirrors on reindex
-                for my $mid (reverse @$mids) {
-                        $num = $self->{mm}->mid_insert($mid);
-                        next unless defined $num;
-                        $mid0 = $mid;
-                        last;
-                }
-                if (defined $mid0) {
-                        if ($sync->{reindex}) {
-                                warn "reindex added #$num <$mid0>\n";
-                        }
-                } else {
-                        warn "E: cannot find article #\n";
-                        return;
-                }
-        }
-        $sync->{nr}++;
-        my $smsg = bless {
-                raw_bytes => $len,
-                num => $num,
-                blob => $oid,
-                mid => $mid0,
-        }, 'PublicInbox::Smsg';
-        $smsg->populate($mime, $self);
-        if (do_idx($self, $msgref, $mime, $smsg)) {
-                reindex_checkpoint($self, $sync, $git);
-        }
-}
-
-sub check_unindexed ($$$) {
-        my ($self, $num, $mid0) = @_;
-        my $unindexed = $self->{unindexed} // {};
-        my $n = delete($unindexed->{$mid0});
-        defined $n or return;
-        if ($n != $num) {
-                die "BUG: unindexed $n != $num <$mid0>\n";
-        } else {
-                $self->{mm}->mid_set($num, $mid0);
-        }
-}
-
-sub multi_mid_q_push ($$$) {
-        my ($self, $sync, $oid) = @_;
-        my $multi_mid = $sync->{multi_mid} //= PublicInbox::MultiMidQueue->new;
-        if ($sync->{reindex}) { # no regen on reindex
-                $multi_mid->push_oid($oid, $self);
-        } else {
-                my $num = $sync->{regen}--;
-                die "BUG: ran out of article numbers" if $num <= 0;
-                $multi_mid->set_oid($num, $oid, $self);
-        }
-}
-
 sub reindex_oid ($$$$) {
         my ($self, $sync, $git, $oid) = @_;
+        if (my $D = $sync->{D}) { # don't waste I/O on deletes
+                return if $D->{pack('H*', $oid)};
+        }
         return if PublicInbox::SearchIdx::too_big($self, $git, $oid);
         my ($num, $mid0, $len);
         my $msgref = $git->cat_file($oid, \$len);
@@ -1003,48 +895,57 @@ sub reindex_oid ($$$$) {
         if (scalar(@$mids) == 0) {
                 warn "E: $oid has no Message-ID, skipping\n";
                 return;
-        } elsif (scalar(@$mids) == 1) {
-                my $mid = $mids->[0];
-
-                # was the file previously marked as deleted?, skip if so
-                if (delete($sync->{D}->{"$mid\0$chash"})) {
-                        if (!$sync->{reindex}) {
-                                $num = $sync->{regen}--;
-                                $self->{mm}->num_highwater($num);
-                        }
-                        return;
-                }
+        }
 
-                # is this a number we got before?
-                $num = $sync->{mm_tmp}->num_for($mid);
+        # {unindexed} is unlikely
+        if ((my $unindexed = $self->{unindexed}) && scalar(@$mids) == 1) {
+                $num = delete($unindexed->{$mids->[0]});
                 if (defined $num) {
-                        $mid0 = $mid;
-                        check_unindexed($self, $num, $mid0);
-                } else {
-                        $num = $sync->{regen}--;
-                        die "BUG: ran out of article numbers" if $num <= 0;
-                        if ($self->{mm}->mid_set($num, $mid) != 1) {
-                                warn "E: unable to assign $num => <$mid>\n";
-                                return;
-                        }
-                        $mid0 = $mid;
+                        $mid0 = $mids->[0];
+                        $self->{mm}->mid_set($num, $mid0);
+                        delete($self->{unindexed}) if !keys(%$unindexed);
+                }
+        }
+        if (!defined($num)) { # reuse if reindexing (or duplicates)
+                my $over = $self->{over};
+                for my $mid (@$mids) {
+                        ($num, $mid0) = $over->num_mid0_for_oid($oid, $mid);
+                        last if defined $num;
                 }
-        } else { # multiple MIDs are a weird case:
-                my $del = 0;
-                for (@$mids) {
-                        $del += delete($sync->{D}->{"$_\0$chash"}) // 0;
+        }
+        $mid0 //= do { # is this a number we got before?
+                $num = $sync->{mm_tmp}->num_for($mids->[0]);
+                defined($num) ? $mids->[0] : undef;
+        };
+        if (!defined($num)) {
+                for (my $i = $#$mids; $i >= 1; $i--) {
+                        $num = $sync->{mm_tmp}->num_for($mids->[$i]);
+                        if (defined($num)) {
+                                $mid0 = $mids->[$i];
+                                last;
+                        }
                 }
-                if ($del) {
-                        unindex_oid_remote($self, $oid, $_) for @$mids;
-                        # do not delete from {mm_tmp}, since another
-                        # single-MID message may use it.
-                } else { # handle them at the end:
-                        multi_mid_q_push($self, $sync, $oid);
+        }
+        if (defined($num)) {
+                $sync->{mm_tmp}->num_delete($num);
+        } else { # never seen
+                $num = $self->{mm}->mid_insert($mids->[0]);
+                if (defined($num)) {
+                        $mid0 = $mids->[0];
+                } else { # rare, try the rest of them, backwards
+                        for (my $i = $#$mids; $i >= 1; $i--) {
+                                $num = $self->{mm}->mid_insert($mids->[$i]);
+                                if (defined($num)) {
+                                        $mid0 = $mids->[$i];
+                                        last;
+                                }
+                        }
                 }
+        }
+        if (!defined($num)) {
+                warn "E: $oid <", join('> <', @$mids), "> is a duplicate\n";
                 return;
         }
-        $sync->{mm_tmp}->mid_delete($mid0) or
-                die "failed to delete <$mid0> for article #$num\n";
         $sync->{nr}++;
         my $smsg = bless {
                 raw_bytes => $len,
@@ -1134,6 +1035,22 @@ $range
         $range;
 }
 
+# don't bump num_highwater on --reindex
+sub mark_deleted ($$$) {
+        my ($git, $sync, $range) = @_;
+        my $D = $sync->{D} //= {}; # pack("H*", $oid) => NR
+        my $fh = $git->popen(qw(log --raw --no-abbrev
+                        --pretty=tformat:%H
+                        --no-notes --no-color --no-renames
+                        --diff-filter=AM), $range, '--', 'd');
+        while (<$fh>) {
+                if (/\A:\d{6} 100644 $x40 ($x40) [AM]\td$/o) {
+                        $D->{pack('H*', $1)}++;
+                }
+        }
+        close $fh or die "git log failed: \$?=$?";
+}
+
 sub sync_prepare ($$$) {
         my ($self, $sync, $epoch_max) = @_;
         my $pr = $sync->{-opt}->{-progress};
@@ -1144,7 +1061,7 @@ sub sync_prepare ($$$) {
         # without {reindex}
         my $reindex_heads = last_commits($self, $epoch_max) if $sync->{reindex};
 
-        for (my $i = $epoch_max; $i >= 0; $i--) {
+        for my $i (0..$epoch_max) {
                 die 'BUG: already indexing!' if $self->{reindex_pipe};
                 my $git_dir = git_dir_n($self, $i);
                 -d $git_dir or next; # missing epochs are fine
@@ -1168,8 +1085,8 @@ sub sync_prepare ($$$) {
                 close $fh or die "git log failed: \$?=$?";
                 $pr->("$n\n") if $pr;
                 $regen_max += $n;
+                mark_deleted($git, $sync, $range) if $sync->{reindex};
         }
-
         return 0 if (!$regen_max && !keys(%{$self->{unindex_range}}));
 
         # reindex should NOT see new commits anymore, if we do,
@@ -1203,10 +1120,8 @@ sub unindex_oid ($$$;$) {
                 my ($id, $prev);
                 while (my $smsg = $over->next_by_mid($mid, \$id, \$prev)) {
                         $gone{$smsg->{num}} = 1 if $oid eq $smsg->{blob};
-                        1; # continue
                 }
-                my $n = scalar keys %gone;
-                next unless $n;
+                my $n = scalar(keys(%gone)) or next;
                 if ($n > 1) {
                         warn "BUG: multiple articles linked to $oid\n",
                                 join(',',sort keys %gone), "\n";
@@ -1222,7 +1137,6 @@ sub unindex_oid ($$$;$) {
         }
 }
 
-my $x40 = qr/[a-f0-9]{40}/;
 sub unindex ($$$$) {
         my ($self, $sync, $git, $unindex_range) = @_;
         my $unindexed = $self->{unindexed} ||= {}; # $mid0 => $num
@@ -1276,22 +1190,29 @@ sub index_epoch ($$$) {
         if (my $pr = $sync->{-opt}->{-progress}) {
                 $pr->("$i.git indexing $range\n");
         }
-
-        my @cmd = qw(log --raw -r --pretty=tformat:%H.%at.%ct
+        my @cmd = qw(log --reverse --raw -r --pretty=tformat:%H.%at.%ct
                         --no-notes --no-color --no-abbrev --no-renames);
         my $fh = $self->{reindex_pipe} = $git->popen(@cmd, $range);
         my $cmt;
+        my $D = $sync->{D};
         while (<$fh>) {
                 chomp;
                 $self->{current_info} = "$i.git $_";
                 if (/\A($x40)\.([0-9]+)\.([0-9]+)$/o) {
-                        $cmt //= $1;
+                        $cmt = $1;
                         $self->{autime} = $2;
                         $self->{cotime} = $3;
                 } elsif (/\A:\d{6} 100644 $x40 ($x40) [AM]\tm$/o) {
                         reindex_oid($self, $sync, $git, $1);
                 } elsif (/\A:\d{6} 100644 $x40 ($x40) [AM]\td$/o) {
-                        mark_deleted($self, $sync, $git, $1);
+                        # allow re-add if there was user error
+                        my $oid = $1;
+                        if ($D) {
+                                my $oid_bin = pack('H*', $oid);
+                                my $nr = --$D->{$oid_bin};
+                                delete($D->{$oid_bin}) if $nr <= 0;
+                        }
+                        unindex_oid($self, $git, $oid);
                 }
         }
         close $fh or die "git log failed: \$?=$?";
@@ -1310,15 +1231,12 @@ sub index_sync {
         $self->idx_init($opt); # acquire lock
         $self->{over}->rethread_prepare($opt);
         my $sync = {
-                D => {}, # "$mid\0$chash" => $oid
                 unindex_range => {}, # EPOCH => oid_old..oid_new
                 reindex => $opt->{reindex},
                 -opt => $opt
         };
         $sync->{ranges} = sync_ranges($self, $sync, $epoch_max);
-        $sync->{regen} = sync_prepare($self, $sync, $epoch_max);
-
-        if ($sync->{regen}) {
+        if (sync_prepare($self, $sync, $epoch_max)) {
                 # tmp_clone seems to fail if inside a transaction, so
                 # we rollback here (because we opened {mm} for reading)
                 # Note: we do NOT rely on DBI transactions for atomicity;
@@ -1328,43 +1246,8 @@ sub index_sync {
                 $sync->{mm_tmp} = $self->{mm}->tmp_clone;
         }
 
-        # work backwards through history
-        for (my $i = $epoch_max; $i >= 0; $i--) {
-                index_epoch($self, $sync, $i);
-        }
-
-        # unindex is required for leftovers if "deletes" affect messages
-        # in a previous fetch+index window:
-        my $git;
-        if (my @leftovers = values %{delete $sync->{D}}) {
-                $git = $self->{-inbox}->git;
-                for my $oid (@leftovers) {
-                        $self->{current_info} = "leftover $oid";
-                        unindex_oid($self, $git, $oid);
-                }
-        }
-        if (my $multi_mid = delete $sync->{multi_mid}) {
-                $git //= $self->{-inbox}->git;
-                my $min = $multi_mid->{min};
-                my $max = $multi_mid->{max};
-                if ($sync->{reindex}) {
-                        # we may need to create new Message-IDs if mirrors
-                        # were initially indexed with old versions
-                        for (my $i = $max; $i >= $min; $i--) {
-                                my $oid;
-                                $oid = $multi_mid->get_oid($i, $self) or next;
-                                next unless defined $oid;
-                                reindex_oid_m($self, $sync, $git, $oid);
-                        }
-                } else { # regen on initial index
-                        for my $num ($min..$max) {
-                                my $oid;
-                                $oid = $multi_mid->get_oid($num, $self) or next;
-                                reindex_oid_m($self, $sync, $git, $oid, $num);
-                        }
-                }
-        }
-        $git->cleanup if $git;
+        # work forwards through history
+        index_epoch($self, $sync, $_) for (0..$epoch_max);
         $self->done;
 
         if (my $nr = $sync->{nr}) {