From: Junio C Hamano <gitster@pobox•com>
To: Samuel Lijin <sxlijin@gmail•com>
Cc: git@vger•kernel.org
Subject: Re: [PATCH v3 4/8] dir: hide untracked contents of untracked dirs
Date: Wed, 17 May 2017 15:47:49 +0900 [thread overview]
Message-ID: <xmqqo9usvv1m.fsf@gitster.mtv.corp.google.com> (raw)
In-Reply-To: <20170516073423.25762-5-sxlijin@gmail.com> (Samuel Lijin's message of "Tue, 16 May 2017 03:34:19 -0400")
Samuel Lijin <sxlijin@gmail•com> writes:
> When we taught read_directory_recursive() to recurse into untracked
> directories in search of ignored files given DIR_SHOW_IGNORED_TOO, that
> had the side effect of teaching it to collect the untracked contents of
> untracked directories. It doesn't always make sense to return these,
> though (we do need them for `clean -d`), so we introduce a flag
> (DIR_KEEP_UNTRACKED_CONTENTS) to control whether or not read_directory()
> strips dir->entries of the untracked contents of untracked dirs.
>
> We also introduce check_contains() to check if one dir_entry corresponds
> to a path which contains the path corresponding to another dir_entry.
>
> Signed-off-by: Samuel Lijin <sxlijin@gmail•com>
> ---
> dir.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
> dir.h | 3 ++-
> 2 files changed, 56 insertions(+), 1 deletion(-)
>
> diff --git a/dir.c b/dir.c
> index 6bd0350e9..214a148ee 100644
> --- a/dir.c
> +++ b/dir.c
> @@ -1852,6 +1852,14 @@ static int cmp_name(const void *p1, const void *p2)
> return name_compare(e1->name, e1->len, e2->name, e2->len);
> }
>
> +/* check if *out lexically contains *in */
> +static int check_contains(const struct dir_entry *out, const struct dir_entry *in)
> +{
> + return (out->len < in->len) &&
> + (out->name[out->len - 1] == '/') &&
> + !memcmp(out->name, in->name, out->len);
> +}
OK, treat_one_path() and treat_pah_fast() both ensure that a path to
a directory is terminated with '/' before calling dir_add_name() and
dir_add_ignored(), so we know a dir_entry "out" that is a directory
must end with '/'. Good.
The second and third line being overly indented is a bit
distracting, though.
> static int treat_leading_path(struct dir_struct *dir,
> const char *path, int len,
> const struct pathspec *pathspec)
> @@ -2067,6 +2075,52 @@ int read_directory(struct dir_struct *dir, const char *path,
> read_directory_recursive(dir, path, len, untracked, 0, pathspec);
> QSORT(dir->entries, dir->nr, cmp_name);
> QSORT(dir->ignored, dir->ignored_nr, cmp_name);
> +
> + // if DIR_SHOW_IGNORED_TOO, read_directory_recursive() will also pick
> + // up untracked contents of untracked dirs; by default we discard these,
> + // but given DIR_KEEP_UNTRACKED_CONTENTS we do not
/*
* Our multi-line comments are formatted like this
* example. No C++/C99 // comments, outside of
* borrowed code and platform specific compat/ code,
* please.
*/
> + if ((dir->flags & DIR_SHOW_IGNORED_TOO)
> + && !(dir->flags & DIR_KEEP_UNTRACKED_CONTENTS)) {
Both having && at the end and && at the beginning are valid C, but
please stick to one style in a single file.
> + int i, j, nr_removed = 0;
> +
> + // remove from dir->entries untracked contents of untracked dirs
/* And our single-liner comments look like this */
> + for (i = 0; i < dir->nr; i++) {
> + if (!dir->entries[i])
> + continue;
> +
> + for (j = i + 1; j < dir->nr; j++) {
> + if (!dir->entries[j])
> + continue;
> + if (check_contains(dir->entries[i], dir->entries[j])) {
> + nr_removed++;
> + free(dir->entries[j]);
> + dir->entries[j] = NULL;
> + }
> + else {
> + break;
> + }
> + }
> + }
This loop is O(n^2). I wonder if we can do better, especially we
know dir->entries[] is sorted already.
Well, because it is sorted, if A/, A/B, and A/B/C are all untracked,
the first round that scans for A/ will nuke both A/B and A/B/C, so
we won't have to scan looking for entries inside A/B, which is a bit
of consolation ;-)
> + for (i = 0;;) {
> + while (i < dir->nr && dir->entries[i])
> + i++;
> + if (i == dir->nr)
> + break;
> + j = i;
> + while (j < dir->nr && !dir->entries[j])
> + j++;
> + if (j == dir->nr)
> + break;
> + dir->entries[i] = dir->entries[j];
> + dir->entries[j] = NULL;
> + }
> + dir->nr -= nr_removed;
This looks like an overly complicated way to scan an array and skip
NULLs. Are you doing an equivalent of this loop, or am I missing
something subtle?
for (src = dst = 0; src < nr; src++)
if (array[src])
array[dst++] = src;
nr = dst;
next prev parent reply other threads:[~2017-05-17 6:47 UTC|newest]
Thread overview: 89+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-04-28 22:56 Bug Report: .gitignore behavior is not matching in git clean and git status Chris Johnson
2017-05-01 1:41 ` Junio C Hamano
2017-05-01 1:56 ` Chris Johnson
2017-05-01 3:15 ` Junio C Hamano
2017-05-01 13:51 ` Samuel Lijin
2017-05-01 15:34 ` Samuel Lijin
2017-05-02 0:26 ` Junio C Hamano
2017-05-03 3:29 ` [PATCH 0/7] Keep git clean -d from inadvertently removing ignored files Samuel Lijin
2017-05-03 3:29 ` [PATCH 1/7] t7300: skip untracked dirs containing " Samuel Lijin
2017-05-03 18:19 ` Stefan Beller
2017-05-03 18:26 ` Samuel Lijin
2017-05-03 18:34 ` Stefan Beller
2017-05-03 3:29 ` [PATCH 2/7] dir: recurse into untracked dirs for " Samuel Lijin
2017-05-03 3:29 ` [PATCH 3/7] dir: add method to check if a dir_entry lexically contains another Samuel Lijin
2017-05-03 18:09 ` Stefan Beller
2017-05-03 3:29 ` [PATCH 4/7] dir: hide untracked contents of untracked dirs Samuel Lijin
2017-05-03 3:29 ` [PATCH 5/7] dir: change linkage of cmp_name() and check_contains() Samuel Lijin
2017-05-03 3:29 ` [PATCH 6/7] builtin/clean: teach clean -d to skip dirs containing ignored files Samuel Lijin
2017-05-03 3:29 ` [PATCH 7/7] t7061: check for ignored file in untracked dir Samuel Lijin
2017-05-05 10:46 ` [PATCH v2 0/9] Keep git clean -d from inadvertently removing ignored files Samuel Lijin
2017-05-08 4:26 ` Junio C Hamano
2017-05-08 21:37 ` Samuel Lijin
2017-05-09 0:31 ` Junio C Hamano
2017-05-16 7:34 ` [PATCH v3 0/8] Fix clean -d and status --ignored Samuel Lijin
2017-05-18 8:21 ` [PATCH v4 0/6] " Samuel Lijin
2017-05-23 9:18 ` [PATCH v5 " Samuel Lijin
2017-05-23 10:09 ` [PATCH v6 " Samuel Lijin
2017-05-23 10:09 ` [PATCH v6 1/6] t7300: clean -d should skip dirs with ignored files Samuel Lijin
2017-05-23 10:09 ` [PATCH v6 2/6] t7061: status --ignored should search untracked dirs Samuel Lijin
2017-05-23 10:09 ` [PATCH v6 3/6] dir: recurse into untracked dirs for ignored files Samuel Lijin
2017-05-23 10:09 ` [PATCH v6 4/6] dir: hide untracked contents of untracked dirs Samuel Lijin
2017-05-23 10:09 ` [PATCH v6 5/6] dir: expose cmp_name() and check_contains() Samuel Lijin
2017-05-23 10:09 ` [PATCH v6 6/6] clean: teach clean -d to preserve ignored paths Samuel Lijin
2017-05-23 22:35 ` Junio C Hamano
2017-05-24 4:14 ` Torsten Bögershausen
2017-05-25 15:36 ` Samuel Lijin
2017-05-26 1:05 ` Junio C Hamano
2017-05-23 9:18 ` [PATCH v5 1/6] t7300: clean -d should skip dirs with ignored files Samuel Lijin
2017-05-23 9:18 ` [PATCH v5 2/6] t7061: status --ignored should search untracked dirs Samuel Lijin
2017-05-23 9:18 ` [PATCH v5 3/6] dir: recurse into untracked dirs for ignored files Samuel Lijin
2017-05-23 9:18 ` [PATCH v5 4/6] dir: hide untracked contents of untracked dirs Samuel Lijin
2017-05-23 9:18 ` [PATCH v5 5/6] dir: expose cmp_name() and check_contains() Samuel Lijin
2017-05-23 9:18 ` [PATCH v5 6/6] clean: teach clean -d to preserve ignored paths Samuel Lijin
2017-05-23 12:52 ` Junio C Hamano
2017-05-23 19:16 ` Samuel Lijin
2017-05-18 8:21 ` [PATCH v4 1/6] t7300: clean -d should skip dirs with ignored files Samuel Lijin
2017-05-18 8:21 ` [PATCH v4 2/6] t7061: status --ignored should search untracked dirs Samuel Lijin
2017-05-18 8:21 ` [PATCH v4 3/6] dir: recurse into untracked dirs for ignored files Samuel Lijin
2017-05-18 8:21 ` [PATCH v4 4/6] dir: hide untracked contents of untracked dirs Samuel Lijin
2017-05-22 3:13 ` Junio C Hamano
2017-05-18 8:21 ` [PATCH v4 5/6] dir: expose cmp_name() and check_contains() Samuel Lijin
2017-05-22 0:38 ` Junio C Hamano
2017-05-18 8:21 ` [PATCH v4 6/6] clean: teach clean -d to skip dirs containing ignored files Samuel Lijin
2017-05-22 4:48 ` Junio C Hamano
2017-05-22 5:58 ` Samuel Lijin
2017-05-22 6:17 ` Junio C Hamano
2017-05-23 2:43 ` Samuel Lijin
2017-05-23 7:50 ` Junio C Hamano
2017-05-16 7:34 ` [PATCH v3 1/8] t7300: clean -d should skip dirs with " Samuel Lijin
2017-05-16 7:34 ` [PATCH v3 2/8] t7061: status --ignored should search untracked dirs Samuel Lijin
2017-05-16 7:34 ` [PATCH v3 3/8] dir: recurse into untracked dirs for ignored files Samuel Lijin
2017-05-17 6:23 ` Junio C Hamano
2017-05-17 7:02 ` Samuel Lijin
2017-05-16 7:34 ` [PATCH v3 4/8] dir: hide untracked contents of untracked dirs Samuel Lijin
2017-05-17 6:47 ` Junio C Hamano [this message]
2017-05-17 7:32 ` Samuel Lijin
2017-05-17 10:14 ` Junio C Hamano
2017-05-16 7:34 ` [PATCH v3 5/8] dir: expose cmp_name() and check_contains() Samuel Lijin
2017-05-16 7:34 ` [PATCH v3 6/8] clean: teach clean -d to skip dirs containing ignored files Samuel Lijin
2017-05-18 2:34 ` Junio C Hamano
2017-05-18 6:32 ` Samuel Lijin
2017-05-16 7:34 ` [PATCH v3 7/8] t7300: clean -d now skips untracked " Samuel Lijin
2017-05-18 2:38 ` Junio C Hamano
2017-05-16 7:34 ` [PATCH v3 8/8] t7061: status --ignored now searches untracked dirs Samuel Lijin
2017-05-18 2:46 ` Junio C Hamano
2017-05-05 10:46 ` [PATCH v2 1/9] t7300: skip untracked dirs containing ignored files Samuel Lijin
2017-05-07 19:12 ` Torsten Bögershausen
2017-05-08 21:24 ` Samuel Lijin
2017-05-05 10:46 ` [PATCH v2 2/9] t7061: expect failure where expected behavior will change Samuel Lijin
2017-05-08 4:34 ` Junio C Hamano
2017-05-05 10:46 ` [PATCH v2 3/9] dir: recurse into untracked dirs for ignored files Samuel Lijin
2017-05-05 10:46 ` [PATCH v2 4/9] dir: add method to check if a dir_entry lexically contains another Samuel Lijin
2017-05-05 10:46 ` [PATCH v2 5/9] dir: hide untracked contents of untracked dirs Samuel Lijin
2017-05-05 10:46 ` [PATCH v2 6/9] dir: change linkage of cmp_name() and check_contains() Samuel Lijin
2017-05-08 4:37 ` Junio C Hamano
2017-05-05 10:46 ` [PATCH v2 7/9] builtin/clean: teach clean -d to skip dirs containing ignored files Samuel Lijin
2017-05-05 10:46 ` [PATCH v2 8/9] t7300: clean -d now skips untracked " Samuel Lijin
2017-05-05 10:46 ` [PATCH v2 9/9] t7061: expect ignored files in untracked dirs Samuel Lijin
2017-05-08 6:35 ` Junio C Hamano
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=xmqqo9usvv1m.fsf@gitster.mtv.corp.google.com \
--to=gitster@pobox$(echo .)com \
--cc=git@vger$(echo .)kernel.org \
--cc=sxlijin@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox