Re: git status --ignored hangs when a deep directory structure present in working tree

From: SZEDER Gábor <szeder.dev@gmail.com>
Date: Jan 27, 2020, 12:08 UTC
Message-ID: <20200127120837.GA10482@szeder.dev>
In-Reply-To: <CANt4O2L_DZnMqVxZzTBMvr=BTWqB6L0uyORkoN_yMHLmUX7yHw@mail.gmail.com>

On Mon, Jan 27, 2020 at 11:55:01AM +0100, Martin Melka wrote:

Show 21 quoted lines

> Hi all, I have ran across what might be a bug in git. When there is a
> deep directory structure (tried on 100+ nested dirs), then git status
> --ignored hangs indefinitely.
> Discovered this on OSX (Mojave, git 2.20.1 (Apple Git-117)), but it
> reproduces in Ubuntu (19.04, git 2.25.0) Docker container on OSX and
> also on baremetal Ubuntu server (16.04, git 2.17.1).
> 
> Steps to reproduce:
> 
> 1. Generate the deep dir structure:
> 
>     mkdir gittest; pushd gittest; git init; for i in $(seq 1 120); do
> mkdir dir; cd dir; done; touch leaf; popd
> 
> 2. Try to get git status --ignored
> 
>     cd gittest && git status --ignored
> 
> 
> If there is a dir depth limit, git should probably exit with an error
> rather than getting stuck endlessly.

This is interesting, thanks for the report.

There is no such directory depth limit, but the runtime of 'git status --ignored' grows quickly with the depth of the untracked directory. Running this shell loop produces the numbers below:

for depth in $(seq 10 30)
do
        dirs=$(for i in $(seq 1 $depth) ; do printf 'dir/' ; done)
        rm -rf dir
        mkdir -p $dirs
        >$dirs/untracked-file
        /usr/bin/time --format="$depth: %e" git status --ignored >/dev/null
done

10: 0.01 11: 0.03 12: 0.05 13: 0.11 14: 0.23 15: 0.47 16: 0.97 17: 1.97 18: 3.88 19: 7.85 20: 16.29 21: 32.92 22: 76.24

Beautifully quadratic, isn't it? :)

Unless I messed up my numbers, with a depth of 120 directories it would take over 6*10^23 years to complete... so yeah, it does qualify as indefinitely.

This slowdown was caused by commit df5bcdf83a (dir: recurse into untracked dirs for ignored files, 2017-05-18), which was part of a patch series to fix 'git clean -d' deleting untracked directories even if they contained ignored files.

Cc'ing Samuel, author of that commit, and Elijah, who had quite some fun with 'dir.c' recently.