Remove paths from list if parent directory is also in the list

Question

My title may be a bit oddly worded, so here's my situation: I have a bunch of directory paths, e.g.

/a/b
/a/b/c
/a/b/c/d
/a/e/f/g/h
/a/e/f/g/h/i/j/k/l
/a/e/f/g/m/n/o
/a/e/f/g/m/n/p

and I want to filter out all lines that are child paths of an entry that already exists in the list, e.g.

/a/b
/a/e/f/g/h
/a/e/f/g/m/n/o
/a/e/f/g/m/n/p

The directory paths are obtained from find, ~~so they should reliably be in top-down order.~~ Solutions for parsing as an array or multi-line string are both welcome.

@cas Editted to strike out the bit about assumed order. The first codeblock is the example input, the second codeblock is the example desired output. — Sam, Apr 20 '21 at 16:01
@cas The criteria is that they are to be removed if they are "child paths of an entry that already exists in the list," /a/b is in the list and is the parent directory of /a/b/c and /a/b/c/d, so /a/b/c and /a/b/c/d are to be removed. Already have an accepted answer, though, so feel free to move on to another post. Thanks for trying to help, though, and sorry if my question wasn't sufficiently clear. — Sam, Apr 20 '21 at 16:18
Can you use find's -prune arg to not have this problem in the first place? (It can be a bit tricky to put it in the right place to trigger on the conditions you want.) — Peter Cordes, Apr 21 '21 at 07:09
Are you just trying to find files, then, find has -type f for that.... (it's not clear from the question). — djsmiley2kStaysInside, Apr 21 '21 at 10:36
@PeterCordes wow, I was not aware of that option. That does seem to do what I was looking for. — Sam, Apr 21 '21 at 14:29

Kusalananda · Answer 1 · 2021-04-21T07:13:54.943

I'm assuming that the list of pathnames may possibly not be sorted, and that the resulting list of pathnames should be in the same order as in the input. I also assume that no pathname contains embedded newline characters.

Using /bin/sh:

#!/bin/sh
set --
while IFS= read -r pathname; do
        for p do
                case $pathname in ("$p"/*) continue 2 ;; esac
        done
    set -- &quot;$@&quot; &quot;$pathname&quot;

done <list
printf '%s\n' "$@"

This reads the pathnames from the file list, one line at a time. The accepted pathnames (initially an empty list) are tested against each read pathname, one at a time in the inner loop. If an accepted pathname is a directory path prefix to the current pathname, the current pathname is discarded (the inner loop skips to the next iteration of the outer loop using continue 2). If no accepted pathname is found to be a directory path prefix to the current pathname, the current pathname is accepted.

The list of accepted pathnames is kept in the positional parameters.

The bash shell would obviously be able to run the above script, but if you want something written specifically for that shell, you could say

#!/bin/bash
accepted=()
while IFS= read -r pathname; do
        for p in "${accepted[@]}"; do
                [[ $pathname == "$p"/* ]] && continue 2
        done
    accepted+=(&quot;$pathname&quot;)

done <list
printf '%s\n' "${accepted[@]}"

Using awk with the identical approach as above:

$ awk '{ for (i=1; i<=n; ++i) if (index($0, accepted[i] "/") == 1) next; accepted[++n]=$0 } END { for (i=1; i<=n; ++i) print accepted[i] }' list
/a/b
/a/e/f/g/h
/a/e/f/g/m/n/o
/a/e/f/g/m/n/p

The awk code, nicified:

{
        for (i = 1; i <= n; ++i)
                if (index($0, accepted[i] "/") == 1)
                        next
    accepted[++n] = $0

}
END {
        for (i = 1; i <= n; ++i)
                print accepted[i]
}

You should be able to see the obvious similarities between this awk program and the shell code variations at the start.

This uses index() to test whether an accepted pathname is the prefix to the current pathname. You could have used if ($0 ~ "^" acceped[i] "/") instead, but a shortcoming of this is that the pathnames themselves are used as part of the regular expression. This starts to matter once you have pathnames containing characters like . and * etc.

+1 for the awk version. i'll hold my nose and ignore the shell while read loops. — cas, Apr 20 '21 at 16:56

ilkkachu · Answer 2 · 2021-04-21T11:11:56.407

If I'm not mistaken, a list of normalized(*), or at least consistently presented paths, sorted with the usual lexicographic sort, has subdirectories of a directory appear immediately after that directory (recursively). Hence, it should be enough to look only at the previous (non-dropped) line.

_{(* By normalized, I mean /foo/bar or /foo/bar/, and not e.g.
/foo/asdf/../bar or /foo///bar//. The output from find would not be a problem since while it does give non-normalized output if given a non-normalized starting directory, the output is at least consistent.)}

A path can still be a prefix of another while being only a sibling but not a parent, e.g. /foo and /foobar. To deal with such cases, we can add a trailing slash to each line that doesn't already have one.

Hence (with /foo and /foobar added to the test, and no attempt at golfing the code):

$ sort paths.txt | awk '! /\/$/ { $0 = $0 "/" } 
                        last && last == substr($0, 1, length(last)) { next; } 
                        { last = $0; sub(/\/$/, "", $0); print }' 
/a/b
/a/e/f/g/h
/a/e/f/g/m/n/o
/a/e/f/g/m/n/p
/foo
/foobar

The first line adds the slash to the current line $0 if needed; the second compares the line to the last stored one (in last) if there is one, and drops matching lines; the third stores and prints any undropped lines, with the trailing slash removed. (Remove the sub(...) to keep them.)

+1. Normalising the paths is interesting and good practice, but it's not going to be an issue in output from find. Matching only the previous line on sorted input is a clever optimisation - much faster and uses much less memory. — cas, Apr 21 '21 at 03:11

score 6 · Accepted Answer · edited Apr 21 '21 at 14:23

6

A short awk solution:

<infile sort -u |awk 'NR==1 || index($0, pre"/")!=1{print; pre=$0}'

edited Apr 21 '21 at 14:23

Ed Morton

31,617

answered Apr 20 '21 at 20:37

αғsнιη

41,407

cas · Answer 4 · 2021-04-21T03:03:51.800

5

With perl (and sort process substitution to guarantee the input is sorted):

$ perl -lne '
    unless (defined($paths) && m:^($paths)/:) {
      $paths{$_}++;
      $paths=join("|", map +( "\Q$_\E" ), keys %paths);
    };
END { print join(&quot;\n&quot;, sort keys %paths) }' &lt;(sort input.txt)

/a/b
/a/e/f/g/h
/a/e/f/g/m/n/o
/a/e/f/g/m/n/p

It progressively builds a regular expression matching paths it has already seen. If a path hasn't been seen before, it adds it to the %paths hash, which is used both to build the regular expression and to contain the list of paths that need to be printed at the end of the script.

Each path is surrounded by \Q and \E when added to the regular expression, to make sure that any perlre meta-characters (like ., ?, *, etc) are disabled.

edited Apr 21 '21 at 03:03

answered Apr 20 '21 at 16:33

cas

78,579

There's an issue with using the pathnames as part of the regular expression. Try with a modified input where the first line is /a/.* (a hidden file named .* in the directory /a), or /a/[eb]. You can fix this by using index() instead. See my awk code. – Kusalananda Apr 20 '21 at 16:36
the list contains directories only...although i guess a directory could be called '/a/.*'. Easily fixed with \Q and \E to escape all meta-characters. – cas Apr 20 '21 at 16:39
Ah, yes. That works too. – Kusalananda Apr 20 '21 at 16:47
1

@cas, note that there's the corner case of e.g. /foo and /foobar, where one is a prefix of another, but not a parent. I think that could be dealt with by adding trailing slashes or so, but you may want to check. – ilkkachu Apr 20 '21 at 19:09
1

@ilkkachu i thought about adding a trailing slash to the RE when i wrote the answer, but wasn't sure if it would introduce problems in a larger input data set. i'll do some testing. – cas Apr 21 '21 at 03:00

score 2 · Answer 5 · answered Apr 21 '21 at 09:50

GNU sed with extended regex mode -E. The previous line with no subsets is stored in hold space.

< file sort \
| sed -En '
    G
    /^([^\n]+)\/.*\n\1$/d
    s/\n.*//p;h
'

< file sort \
| perl -lne '
    $prev //= $_;
    print($prev = $_)
       if index($_, "$prev/");
'

POSIX sed does not allow [^\n] so we rewrite in POSIX compliant constructs

< file sort \
| sed -e '
    H;x
    \|^\(..*\)\n\1/|{
      s/\n.*//;h;d
    }
    g
'

score 2 · Answer 6 · answered Apr 21 '21 at 16:53

For a list of files from find, you may be able to use find ... -prune to avoid the problem in the first place: exclude descending into children of the current path, if it's a directory itself. This Q&A shows an example, and see the man page. If trying to combine it with -o on the OR of some other conditions, you may want find ... $ -name 'foo*' -o -name 'bar*' $ -prune.

There are other cases where it's not going to do what you need, so you will need one of the other answers that process the output of find.

e.g. if you're using find -name marker.txt -printf '%h\n' to find directories that happen to contain a marker.txt, you can't -prune on that because -name only matches a file within the directory, not the directory itself.

Or for other future readers whose list of files isn't straight from find in the first place.

Remove paths from list if parent directory is also in the list

6 Answers6

Linked