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.

Answer 1

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 -- "$@" "$pathname"
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+=("$pathname")
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.

Answer 2

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.)

Answer 3

A short awk solution:

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

Answer 4

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("\n", sort keys %paths) }' <(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.

Answer 5

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
'

Answer 6

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.