infinite loop in git-send-email with alias files

infinite loop in git-send-email with alias files

[Mike Frysinger]

i was setting up an aliasesfile for git-send-email, but in doing so, i
inadvertently made a typo creating an infinite loop.  i didnt notice
right away, but i did notice when `git-send-email` hung using 100% of
a cpu.

simple way to reproduce:
$ $ git config sendemail.aliasesfile
.git/mail
$ git config sendemail.aliasfiletype
mutt
$ cat .git/mail
alias a b
alias b a
$ git send-email HEAD^ --to a
<hit enter a few times and watch it hang>

noticed with 1.6.3.3, but seems to be in 1.6.4-rc1 too
-mike

Re: infinite loop in git-send-email with alias files

[Jeff King]

On Thu, Jul 16, 2009 at 09:10:00PM -0400, Mike Frysinger wrote:

> i was setting up an aliasesfile for git-send-email, but in doing so, i
> inadvertently made a typo creating an infinite loop.  i didnt notice
> right away, but i did notice when `git-send-email` hung using 100% of
> a cpu.

Yep, we don't do cycle detection on alias expansion. It is easy enough
to do, though:

-- >8 --
Subject: [PATCH] send-email: detect cycles in alias expansion

With the previous code, an alias cycle like:

  $ echo 'alias a b' >aliases
  $ echo 'alias b a' >aliases
  $ git config sendemail.aliasesfile aliases
  $ git config sendemail.aliasfiletype mutt

would put send-email into an infinite loop. This patch
detects the situation and complains to the user.

Signed-off-by: Jeff King <peff@peff.net>
---
Two notes on this patch:

  1. I ended up rewriting the iterative expansion as a recursive
     function, because it makes the code simpler (doing proper detection
     in the iterative loop means you have to check where each expansion
     came from. That is, expanding "a" to "b" and "c" to "b" is OK, but
     expanding "a" to "b" to "c" is not. So you end up having to
     implement a stack, anyway. Much easier to let perl do it for us).

     But this also raises the likelihood that I screwed something up, so
     I would appreciate an extra set of eyes.

  2. It just barfs. I figure such a situation is a sign of a problem
     that the user should address. But we could also just stop expansion
     (so "a" => "b" => "a" simply expands to "a"); this is more like how
     bash aliases work, but I don't know if there is any benefit to that
     here.

     We could also print out the cycle, but I doubt it is worth the
     trouble.

 git-send-email.perl |   18 +++++++++++-------
 1 files changed, 11 insertions(+), 7 deletions(-)

diff --git a/git-send-email.perl b/git-send-email.perl
index 8ce6f1f..d508f83 100755
--- a/git-send-email.perl
+++ b/git-send-email.perl
@@ -654,13 +654,17 @@ if (!@to) {
 }
 
 sub expand_aliases {
-	my @cur = @_;
-	my @last;
-	do {
-		@last = @cur;
-		@cur = map { $aliases{$_} ? @{$aliases{$_}} : $_ } @last;
-	} while (join(',',@cur) ne join(',',@last));
-	return @cur;
+	return map { expand_one_alias($_) } @_;
+}
+
+my %EXPANDED_ALIASES;
+sub expand_one_alias {
+	my $alias = shift;
+	if ($EXPANDED_ALIASES{$alias}) {
+		die "fatal: alias '$alias' expands to itself\n";
+	}
+	local $EXPANDED_ALIASES{$alias} = 1;
+	return $aliases{$alias} ? expand_aliases(@{$aliases{$alias}}) : $alias;
 }
 
 @to = expand_aliases(@to);
-- 
1.6.4.rc1.190.g0a8d.dirty

Re: infinite loop in git-send-email with alias files

[Johannes Sixt]

Jeff King schrieb:
> +my %EXPANDED_ALIASES;
> +sub expand_one_alias {
> +	my $alias = shift;
> +	if ($EXPANDED_ALIASES{$alias}) {
> +		die "fatal: alias '$alias' expands to itself\n";
> +	}
> +	local $EXPANDED_ALIASES{$alias} = 1;
> +	return $aliases{$alias} ? expand_aliases(@{$aliases{$alias}}) : $alias;

What does 'local' make local here? Only the assignment of the slot
$EXPANDED_ALIASES{$alias}? Or the whole %EXPANDED_ALIASES? If the latter,
does this copy the existing %EXPANDED_ALIASES before the assignment is
made; otherwise, how can this work if only ever a single slot of
%EXPANDED_ALIASES is filled in?

(Disclaimer: I'm not a perl expert, obviously, and I didn't test your patch.)

-- Hannes

Re: infinite loop in git-send-email with alias files

[Jeff King]

On Thu, Jul 23, 2009 at 02:30:55PM +0200, Johannes Sixt wrote:

> Jeff King schrieb:
> > +my %EXPANDED_ALIASES;
> > +sub expand_one_alias {
> > +	my $alias = shift;
> > +	if ($EXPANDED_ALIASES{$alias}) {
> > +		die "fatal: alias '$alias' expands to itself\n";
> > +	}
> > +	local $EXPANDED_ALIASES{$alias} = 1;
> > +	return $aliases{$alias} ? expand_aliases(@{$aliases{$alias}}) : $alias;
> 
> What does 'local' make local here? Only the assignment of the slot
> $EXPANDED_ALIASES{$alias}? Or the whole %EXPANDED_ALIASES? If the latter,
> does this copy the existing %EXPANDED_ALIASES before the assignment is
> made; otherwise, how can this work if only ever a single slot of
> %EXPANDED_ALIASES is filled in?

It localizes just that slot. But remember that 'local' is about
_dynamic_ scoping, not _lexical_ scoping. So that slot is now set for
the duration of the expand_one_alias call, and is visible to its
subroutines (i.e., the recursive calls). So each level of recursion sets
one more field in $EXPANDED_ALIASES, and when we leave the function,
perl automatically restores it to its previous value.

-Peff