notmuch-mutt: support for duplicate message removal

notmuch-mutt: support for duplicate message removal

[Stefano Zacchiroli]

Heya,
  here is a patchset originating from a feature contributed by Kevin
J. McCarthy: duplicate message removal for notmuch-mutt searches.

I've reviewed the main patch and gone through various iterations of it
with Kevin. I consider it suitable for application in its present
form, and I've added a subsequent patch to fix the Debian packaging
accordingly.

Can someone with commit access be so kind of applying this patchset to
the master branch?

Also, if you've further comments on the patch, do not hesitate!

[PATCH 1/2] Add duplicate message removal for notmuch-mutt.

[Stefano Zacchiroli]

From: Kevin McCarthy <kevin@8t8.us>

Add a --remove-dups flag which removes duplicate files from search and
thread results.  Uses fdupes if installed.  Otherwise it runs a size and
Digest::SHA scan on each file to detect duplicates.

Signed-off-by: Stefano Zacchiroli <zack@upsilon.cc>
---
 contrib/notmuch-mutt/notmuch-mutt    |   89 ++++++++++++++++++++++++++++------
 contrib/notmuch-mutt/notmuch-mutt.rc |    4 +-
 2 files changed, 76 insertions(+), 17 deletions(-)

diff --git a/contrib/notmuch-mutt/notmuch-mutt b/contrib/notmuch-mutt/notmuch-mutt
index 7c125e6..d14709d 100755
--- a/contrib/notmuch-mutt/notmuch-mutt
+++ b/contrib/notmuch-mutt/notmuch-mutt
@@ -18,6 +18,8 @@ use Mail::Box::Maildir;
 use Pod::Usage;
 use String::ShellQuote;
 use Term::ReadLine;
+use Digest::SHA;
+use File::Which;
 
 
 my $xdg_cache_dir = "$ENV{HOME}/.cache";
@@ -34,16 +36,65 @@ sub empty_maildir($) {
     $folder->close();
 }
 
-# search($maildir, $query)
+# Match files by size and SHA-256; then delete duplicates
+sub builtin_remove_dups($) {
+    my ($maildir) = @_;
+    my (%size_to_files, %sha_to_files);
+
+    # Group files by matching sizes
+    foreach my $file (glob("$maildir/cur/*")) {
+        my $size = -s $file;
+        push(@{$size_to_files{$size}}, $file) if $size;
+    }
+
+    foreach my $same_size_files (values %size_to_files) {
+        # Don't run sha unless there is another file of the same size
+        next if scalar(@$same_size_files) < 2;
+        %sha_to_files = ();
+
+        # Group files with matching sizes by SHA-256
+        foreach my $file (@$same_size_files) {
+            open(my $fh, '<', $file) or next;
+            binmode($fh);
+            my $sha256hash = Digest::SHA->new(256)->addfile($fh)->hexdigest;
+            close($fh);
+
+            push(@{$sha_to_files{$sha256hash}}, $file);
+        }
+
+        # Remove duplicates
+        foreach my $same_sha_files (values %sha_to_files) {
+            next if scalar(@$same_sha_files) < 2;
+            unlink(@{$same_sha_files}[1..$#$same_sha_files]);
+        }
+    }
+}
+
+# Use either fdupes or the built-in scanner to detect and remove duplicate
+# search results in the maildir
+sub remove_duplicates($) {
+    my ($maildir) = @_;
+
+    my $fdupes = which("fdupes");
+    if ($fdupes) {
+      system("$fdupes --hardlinks --symlinks --delete --noprompt"
+             . " --quiet $maildir/cur/ > /dev/null");
+    } else {
+        builtin_remove_dups($maildir);
+    }
+}
+
+# search($maildir, $remove_dups, $query)
 # search mails according to $query with notmuch; store results in $maildir
-sub search($$) {
-    my ($maildir, $query) = @_;
+sub search($$$) {
+    my ($maildir, $remove_dups, $query) = @_;
     $query = shell_quote($query);
 
     empty_maildir($maildir);
     system("notmuch search --output=files $query"
 	   . " | sed -e 's: :\\\\ :g'"
 	   . " | xargs --no-run-if-empty ln -s -t $maildir/cur/");
+    remove_duplicates($maildir) if ($remove_dups);
 }
 
 sub prompt($$) {
@@ -74,28 +125,28 @@ sub get_message_id() {
     return $1;
 }
 
-sub search_action($$@) {
-    my ($interactive, $results_dir, @params) = @_;
+sub search_action($$$@) {
+    my ($interactive, $results_dir, $remove_dups, @params) = @_;
 
     if (! $interactive) {
-	search($results_dir, join(' ', @params));
+	search($results_dir, $remove_dups, join(' ', @params));
     } else {
 	my $query = prompt("search ('?' for man): ", join(' ', @params));
 	if ($query ne "") {
-	    search($results_dir,$query);
+	    search($results_dir, $remove_dups, $query);
 	}
     }
 }
 
-sub thread_action(@) {
-    my ($results_dir, @params) = @_;
+sub thread_action($$@) {
+    my ($results_dir, $remove_dups, @params) = @_;
 
     my $mid = get_message_id();
     my $search_cmd = 'notmuch search --output=threads ' . shell_quote("id:$mid");
     my $tid = `$search_cmd`;	# get thread id
     chomp($tid);
 
-    search($results_dir, $tid);
+    search($results_dir, $remove_dups, $tid);
 }
 
 sub tag_action(@) {
@@ -118,11 +169,13 @@ sub main() {
     my $results_dir = "$cache_dir/results";
     my $interactive = 0;
     my $help_needed = 0;
+    my $remove_dups = 0;
 
     my $getopt = GetOptions(
 	"h|help" => \$help_needed,
 	"o|output-dir=s" => \$results_dir,
-	"p|prompt" => \$interactive);
+	"p|prompt" => \$interactive,
+	"r|remove-dups" => \$remove_dups);
     if (! $getopt || $#ARGV < 0) { die_usage() };
     my ($action, @params) = ($ARGV[0], @ARGV[1..$#ARGV]);
 
@@ -136,9 +189,9 @@ sub main() {
 	print STDERR "Error: no search term provided\n\n";
 	die_usage();
     } elsif ($action eq "search") {
-	search_action($interactive, $results_dir, @params);
+	search_action($interactive, $results_dir, $remove_dups, @params);
     } elsif ($action eq "thread") {
-	thread_action($results_dir, @params);
+	thread_action($results_dir, $remove_dups, @params);
     } elsif ($action eq "tag") {
 	tag_action(@params);
     } else {
@@ -189,6 +242,12 @@ be overwritten. (Default: F<~/.cache/notmuch/mutt/results/>)
 Instead of using command line search terms, prompt the user for them (only for
 "search").
 
+=item -r
+
+=item --remove-dups
+
+Remove duplicates from search results.
+
 =item -h
 
 =item --help
@@ -205,10 +264,10 @@ the following in your Mutt configuration (usually one of: F<~/.muttrc>,
 F</etc/Muttrc>, or a configuration snippet under F</etc/Muttrc.d/>):
 
     macro index <F8> \
-          "<enter-command>unset wait_key<enter><shell-escape>notmuch-mutt --prompt search<enter><change-folder-readonly>~/.cache/notmuch/mutt/results<enter>" \
+          "<enter-command>unset wait_key<enter><shell-escape>notmuch-mutt -r --prompt search<enter><change-folder-readonly>~/.cache/notmuch/mutt/results<enter>" \
           "notmuch: search mail"
     macro index <F9> \
-          "<enter-command>unset wait_key<enter><pipe-message>notmuch-mutt thread<enter><change-folder-readonly>~/.cache/notmuch/mutt/results<enter><enter-command>set wait_key<enter>" \
+          "<enter-command>unset wait_key<enter><pipe-message>notmuch-mutt -r thread<enter><change-folder-readonly>~/.cache/notmuch/mutt/results<enter><enter-command>set wait_key<enter>" \
           "notmuch: reconstruct thread"
     macro index <F6> \
           "<enter-command>unset wait_key<enter><pipe-message>notmuch-mutt tag -- -inbox<enter>" \
diff --git a/contrib/notmuch-mutt/notmuch-mutt.rc b/contrib/notmuch-mutt/notmuch-mutt.rc
index b0a38d1..ddc4b48 100644
--- a/contrib/notmuch-mutt/notmuch-mutt.rc
+++ b/contrib/notmuch-mutt/notmuch-mutt.rc
@@ -1,8 +1,8 @@
 macro index <F8> \
-      "<enter-command>unset wait_key<enter><shell-escape>notmuch-mutt --prompt search<enter><change-folder-readonly>`echo ${XDG_CACHE_HOME:-$HOME/.cache}/notmuch/mutt/results`<enter>" \
+      "<enter-command>unset wait_key<enter><shell-escape>notmuch-mutt -r --prompt search<enter><change-folder-readonly>`echo ${XDG_CACHE_HOME:-$HOME/.cache}/notmuch/mutt/results`<enter>" \
       "notmuch: search mail"
 macro index <F9> \
-      "<enter-command>unset wait_key<enter><pipe-message>notmuch-mutt thread<enter><change-folder-readonly>`echo ${XDG_CACHE_HOME:-$HOME/.cache}/notmuch/mutt/results`<enter><enter-command>set wait_key<enter>" \
+      "<enter-command>unset wait_key<enter><pipe-message>notmuch-mutt -r thread<enter><change-folder-readonly>`echo ${XDG_CACHE_HOME:-$HOME/.cache}/notmuch/mutt/results`<enter><enter-command>set wait_key<enter>" \
       "notmuch: reconstruct thread"
 macro index <F6> \
       "<enter-command>unset wait_key<enter><pipe-message>notmuch-mutt tag -- -inbox<enter>" \
-- 
1.7.10.4

[PATCH 2/2] debian packaging: new depends for duplicate removals in mutt contrib

[Stefano Zacchiroli]

both new hard dependency for File::Which and soft dependency on fdupes
---
 debian/control |    3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/debian/control b/debian/control
index 812430f..e24fd94 100644
--- a/debian/control
+++ b/debian/control
@@ -109,8 +109,9 @@ Package: notmuch-mutt
 Architecture: all
 Depends: notmuch, libmail-box-perl, libmailtools-perl,
  libstring-shellquote-perl, libterm-readline-gnu-perl,
+ libfile-which-perl,
  ${misc:Depends}
-Recommends: mutt
+Recommends: mutt, fdupes
 Enhances: notmuch, mutt
 Description: thread-based email index, search and tagging (Mutt interface)
  notmuch-mutt provides integration among the Mutt mail user agent and
-- 
1.7.10.4

Re: notmuch-mutt: support for duplicate message removal

[Jani Nikula]

On Wed, 01 Aug 2012, Stefano Zacchiroli <zack@upsilon.cc> wrote:
> Heya,
>   here is a patchset originating from a feature contributed by Kevin
> J. McCarthy: duplicate message removal for notmuch-mutt searches.
>
> I've reviewed the main patch and gone through various iterations of it
> with Kevin. I consider it suitable for application in its present
> form, and I've added a subsequent patch to fix the Debian packaging
> accordingly.
>
> Can someone with commit access be so kind of applying this patchset to
> the master branch?
>
> Also, if you've further comments on the patch, do not hesitate!

I'm guessing you get the duplicates because you have dupes in the mail
store, and 'notmuch search --output=files' prints all the filenames
associated with each matching message, rather than any other reason. The
presented approach will only remove identical files, and will leave
behind files that are basically the same message, but have differing
headers, e.g. due to being received through different channels. Is this
what you want?

Perhaps an option to 'notmuch search --output=files' to print only one
filename (even if there are many) per message would be interesting. IIRC
the first filename is used by 'notmuch show' to display the message
anyway. At a glance, this should be trivial to implement, but would it
cover your needs?


BR,
Jani.

Re: notmuch-mutt: support for duplicate message removal

[Andrei POPESCU]

[-- Attachment #1: Type: text/plain, Size: 1032 bytes --]

On Mi, 01 aug 12, 13:24:24, Jani Nikula wrote:
> On Wed, 01 Aug 2012, Stefano Zacchiroli <zack@upsilon.cc> wrote:
> >
> > Also, if you've further comments on the patch, do not hesitate!
> 
> I'm guessing you get the duplicates because you have dupes in the mail
> store, and 'notmuch search --output=files' prints all the filenames
> associated with each matching message, rather than any other reason. The
> presented approach will only remove identical files, and will leave
> behind files that are basically the same message, but have differing
> headers, e.g. due to being received through different channels. Is this
> what you want?

I'm at least one user that cares enough about the distinction to have 
all list mails received via a different address, just to avoid Gmail's 
"feature" of silently dropping my own messages received via a list. 
IMVHO it should at least be configurable...

Kind regards,
Andrei
-- 
If you can't explain it simply, you don't understand it well enough.
(Albert Einstein)

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: notmuch-mutt: support for duplicate message removal

[Daniel Kahn Gillmor]

[-- Attachment #1: Type: text/plain, Size: 564 bytes --]

On 08/01/2012 12:26 PM, Andrei POPESCU wrote:
> I'm at least one user that cares enough about the distinction to have 
> all list mails received via a different address, just to avoid Gmail's 
> "feature" of silently dropping my own messages received via a list. 
> IMVHO it should at least be configurable...

The proposed feature could also exacerbate the previously-discussed
attack vector [0] whereby a malicious Message-ID collision can be used
to hide messages from the victim's mailstore.

	--dkg

[0] id:87k42vrqve.fsf@pip.fifthhorseman.net


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 1030 bytes --]

Re: notmuch-mutt: support for duplicate message removal

[Kevin J. McCarthy]

Jani Nikula wrote:
> I'm guessing you get the duplicates because you have dupes in the mail
> store, and 'notmuch search --output=files' prints all the filenames
> associated with each matching message, rather than any other reason. The
> presented approach will only remove identical files, and will leave
> behind files that are basically the same message, but have differing
> headers, e.g. due to being received through different channels. Is this
> what you want?

This method was something we felt comfortable enabling by default.

Stefano and I discussed adding a (by default off) option to remove
duplicates by message-id, but wanted to get this patch merged first and
then think about it.

> Perhaps an option to 'notmuch search --output=files' to print only one
> filename (even if there are many) per message would be interesting.

This would be useful for the second approach.  If it's easy to do, that
would be great.

-Kevin

Re: notmuch-mutt: support for duplicate message removal

[Jani Nikula]

On Wed, 01 Aug 2012, Daniel Kahn Gillmor <dkg@fifthhorseman.net> wrote:
> On 08/01/2012 12:26 PM, Andrei POPESCU wrote:
>> I'm at least one user that cares enough about the distinction to have 
>> all list mails received via a different address, just to avoid Gmail's 
>> "feature" of silently dropping my own messages received via a list. 
>> IMVHO it should at least be configurable...
>
> The proposed feature could also exacerbate the previously-discussed
> attack vector [0] whereby a malicious Message-ID collision can be used
> to hide messages from the victim's mailstore.

Just to clarify, the feature proposed in this patch series does not make
the problem worse (as it would hide only fully identical messages, which
is not useful for the malicious purpose).

What I suggested [1] could indeed make notmuch-mutt as vulnerable to the
attack vector as notmuch show, and the emacs ui, currently are (but not
worse than that).

BR,
Jani.

[1] id:"87pq7aam8n.fsf@nikula.org"

>
> 	--dkg
>
> [0] id:87k42vrqve.fsf@pip.fifthhorseman.net

Re: notmuch-mutt: support for duplicate message removal

[Jani Nikula]

On Wed, 01 Aug 2012, "Kevin J. McCarthy" <kevin@8t8.us> wrote:
> Jani Nikula wrote:
>> I'm guessing you get the duplicates because you have dupes in the mail
>> store, and 'notmuch search --output=files' prints all the filenames
>> associated with each matching message, rather than any other reason. The
>> presented approach will only remove identical files, and will leave
>> behind files that are basically the same message, but have differing
>> headers, e.g. due to being received through different channels. Is this
>> what you want?
>
> This method was something we felt comfortable enabling by default.
>
> Stefano and I discussed adding a (by default off) option to remove
> duplicates by message-id, but wanted to get this patch merged first and
> then think about it.

Sounds reasonable, especially considering [1]. I have no comments on the
patches; I'm not a notmuch-mutt (or perl) user.

>> Perhaps an option to 'notmuch search --output=files' to print only one
>> filename (even if there are many) per message would be interesting.
>
> This would be useful for the second approach.  If it's easy to do, that
> would be great.

Apart from [1], the hardest part will be bikeshedding about the option
name. ;)

BR,
Jani.

[1] id:"87d33av2sg.fsf@nikula.org"

Re: notmuch-mutt: support for duplicate message removal

[Stefano Zacchiroli]

On Wed, Aug 01, 2012 at 01:20:08PM -0400, Daniel Kahn Gillmor wrote:
> The proposed feature could also exacerbate the previously-discussed
> attack vector [0] whereby a malicious Message-ID collision can be used
> to hide messages from the victim's mailstore.
> 
> [0] id:87k42vrqve.fsf@pip.fifthhorseman.net

I didn't find the reference above but, if you're speaking about the
proposed patch only, I don't think it's the case. The proposed patch
only deduplicate file-identical (up to checksums, that is) messages in
maildirs: a Message-ID collision is not enough to hide a message.

But your comment is very interesting anyhow, as deduplicating on the
basis of Message-ID is indeed something I've discussed with Kevin as
future work. You just provided an extra argument not to enable that by
default.

Cheers.
-- 
Stefano Zacchiroli     zack@{upsilon.cc,pps.jussieu.fr,debian.org} . o .
Maître de conférences   ......   http://upsilon.cc/zack   ......   . . o
Debian Project Leader    .......   @zack on identi.ca   .......    o o o
« the first rule of tautology club is the first rule of tautology club »

Re: notmuch-mutt: support for duplicate message removal

[Jameson Graef Rollins]

[-- Attachment #1: Type: text/plain, Size: 504 bytes --]

On Thu, Aug 02 2012, Stefano Zacchiroli <zack@upsilon.cc> wrote:
> On Wed, Aug 01, 2012 at 01:20:08PM -0400, Daniel Kahn Gillmor wrote:
>> The proposed feature could also exacerbate the previously-discussed
>> attack vector [0] whereby a malicious Message-ID collision can be used
>> to hide messages from the victim's mailstore.
>> 
>> [0] id:87k42vrqve.fsf@pip.fifthhorseman.net
>
> I didn't find the reference above but,

http://mid.gmane.org/87k42vrqve.fsf@pip.fifthhorseman.net

jamie.

[-- Attachment #2: Type: application/pgp-signature, Size: 835 bytes --]

Re: notmuch-mutt: support for duplicate message removal

[Stefano Zacchiroli]

On Thu, Aug 02, 2012 at 11:03:44AM -0700, Jameson Graef Rollins wrote:
> > I didn't find the reference above but,
> http://mid.gmane.org/87k42vrqve.fsf@pip.fifthhorseman.net

Thanks. I confirm my previous comments after "but," then :-)

-- 
Stefano Zacchiroli     zack@{upsilon.cc,pps.jussieu.fr,debian.org} . o .
Maître de conférences   ......   http://upsilon.cc/zack   ......   . . o
Debian Project Leader    .......   @zack on identi.ca   .......    o o o
« the first rule of tautology club is the first rule of tautology club »

Re: [PATCH 1/2] Add duplicate message removal for notmuch-mutt.

[David Bremner]

Stefano Zacchiroli <zack@upsilon.cc> writes:

> From: Kevin McCarthy <kevin@8t8.us>
>
> Add a --remove-dups flag which removes duplicate files from search and
> thread results.  Uses fdupes if installed.  Otherwise it runs a size and
> Digest::SHA scan on each file to detect duplicates.

Pushed,

d