7

Given any two absolute Unix path specs1, one could decompose each spec as the concatenation of a longest common prefix and a specific suffix. E.g.,

/abc/bcd/cdf     -> /abc/bcd + cdf
/abc/bcd/chi/hij -> /abc/bcd + chi/hij

Is there a Unix utility (or utilities) to compute such decomposition? (I added "or utilities" in case there are separate utilities for computing the longest common prefix and for computing relative paths.)

(I realize that it would not be extremely difficult to code such utilities, but I try to give priority to tools that are more or less standard over custom-made ones, whenever possible.)

1I write "path spec" rather than "path" to sidestep issues like existence (of the paths) in a given filesystem, links, etc.

2

5 Answers 5

14

You can compute the longest common leading substring of a list of lines with this:

sed -e '1{h;d;}' -e 'G;s,\(.*\).*\n\1.*,\1,;h;$!d'

Which for instance for:

/abc/bcd/cdf
/abc/bcd/cdf/foo
/abc/bcd/chi/hij
/abc/bcd/cdd

returns:

/abc/bcd/c

To restrict it to path components:

sed -e 's,$,/,;1{h;d;}' -e 'G;s,\(.*/\).*\n\1.*,\1,;h;$!d;s,/$,,'

(returns /abc/bcd on the sample above).

4
  • 7
    You win the prize for shortest solution. But good lord, I do not understand it. Feb 3, 2015 at 23:50
  • 1
    Just what I came here for. An unintelligible one-liner that gets the job done. Nov 26, 2018 at 21:35
  • I had no idea that sed is so powerful.
    – Jasha
    May 23, 2022 at 0:23
  • Also the second one-liner above (i.e. the one restricted to path components) gives an incorrect answer in some edge cases involving relative paths with no common prefix (e.g. for the pair of paths a/b and c/d).
    – Jasha
    Jun 11, 2022 at 22:08
2

You can do that in a shell loop. The code below should work with all kinds of strange paths with extra slashes; if all your paths are of the form /foo/bar, you can get away with something simpler.

split_common_prefix () {
  path1=$1
  path2=$2
  common_prefix=
  ## Handle initial // specially
  case $path1 in
    //[!/]*) case $path2 in
               //[!/]*) common_prefix=/ path1=${path1#/} path2=${path2#/};;
               *) return;;
             esac;;
    /*) case $path2 in
          /*) :;;
          *) return;;
        esac;;
    *) case $path2 in /*) return;; esac;;
  esac
  ## Normalize multiple slashes
  trailing_slash1= trailing_slash2=
  case $path1 in */) trailing_slash1=/;; esac
  case $path2 in */) trailing_slash2=/;; esac
  path1=$(printf %s/ "$path1" | tr -s / /)
  path2=$(printf %s/ "$path2" | tr -s / /)
  if [ -z "$trailing_slash1" ]; then path1=${path1%/}; fi
  if [ -z "$trailing_slash2" ]; then path2=${path2%/}; fi
  ## Handle the complete prefix case (faster, necessary for equality and
  ## for some cases with trailing slashes)
  case $path1 in
    "$path2")
      common_prefix=$path1; path1= path2=
      return;;
    "$path2"/*)
      common_prefix=$path2; path1=${path1#$common_prefix} path2=
      return;;
  esac
  case $path2 in
    "$path1"/*)
      common_prefix=$path1; path1= path2=${path2#$common_prefix}
      return;;
  esac
  ## Handle the generic case
  while prefix1=${path1%%/*} prefix2=${path2%%/*}
        [ "$prefix1" = "$prefix2" ]
  do
    common_prefix=$common_prefix$prefix1/
    path1=${path1#$prefix1/} path2=${path2#$prefix1/}
  done
}

Alternatively, determine the longest common prefix of the two strings and trim it to its last / character (except when the common prefix consists solely of slashes).

6
  • @StephaneChazelas I've now copy-pasted the latest code, in which I've also fixed the equality case (oops). I think I've also fixed cases with trailing slashes but I haven't tested it much. Mar 7, 2013 at 13:42
  • Your code still has minor problems. One case is "/" for both path, and the other concerns file names containing spaces. The latter is bad practice but happens with names generated by tools from external data. I think that you and @StephaneChazelas may be interested or amused by a simpler solution I added to the answers.
    – babou
    May 28, 2013 at 12:37
  • @babou I get / as the common prefix of / and /, what's the problem? And what's the problem with spaces? May 28, 2013 at 12:42
  • Oops ... sorry, my mistake. I do not know how you test the code you present. I encapsulated it in a bash script and I was the one to forget quotes around the arguments. But I still get no answer with / and /.
    – babou
    May 28, 2013 at 14:02
  • @babou $ split_common_prefix / /; echo $?; echo "$common_prefix"0 / May 28, 2013 at 17:14
2

There is no such tool to my knowledge. However, you can easily write such program since you have to do determine the longest group of components.

An example "one-liner":

echo /abc/bcd/cdf | awk -vpath=/abc/bcd/chi/hij -F/ '{ OFS="\n";len=0; split(path, components); for (i=1; i<=NF; i++) if($i == components[i])len+=1+length($i);else break;print substr($0, 1, len - 1), substr($0, len + 1), substr(path, len + 1);exit;}

Formatted version with comments:

$ cat longest-path.awk
#!/usr/bin/awk -f
BEGIN {
    FS="/";   # split by slash
}
{
    len=0;                      # initially the longest path has length 1
    split(path, components);    # split by directory separator (slash)
    for (i=1; i<=NF; i++) {     # loop through all path components
        if ($i == components[i]) {
            len += 1 + length($i);
        } else {
            break;              # if there is a mismatch, terminate
        }
    }
    print substr($0, 1, len - 1);  # longest prefix minus slash
    print substr($0, len + 1);     # remainder stdin
    print substr(path, len + 1);   # remainder path
    exit;                          # only the first line is compared
}
$ echo  /abc/bcd/cdf | ./longest-path.awk -vpath=/abc/bcd/chi/hij
/abc/bcd
cdf
chi/hij
1

Here is a quickie that seems to answer the question, making good use of usual (standard ?) facilities of unix/linux as requested (well ... I tried it only on my Mageia Linux).

#!/bin/sh
# Compute absolute pathnames common prefix and decompose second one
# Author Babou 2013/05/27 on http://unix.stackexchange.com/questions/67078/
first=`realpath -ms "$1"`
rel=`realpath -ms --relative-to="$1" "$2" | rev`
while [ `basename "$rel"` == '..' ]
do
   first=`dirname "$first"`
   rel=`dirname "$rel"`
done
echo $first + `echo $rel | rev`

And my test suite :

./prefix /abc/bcd/cdf /abc/bcd/chi/hij
./prefix "/abc/bcd/cdf" "/abc/bcd/chi/hij"
./prefix "/ab c/bcd/cdf" "/ab c/bcd/chi/hij"
./prefix "/abc/bcd/cdf" "/abc/bcd/chi/h ij"
./prefix "/" "/"
./prefix "/abc/bcd/" "/abc/bcd/chi/hij"
./prefix "/abc/bcd/cdf" "/abc/bcd/"
./prefix "/abc///zzz/../bcd/cdf" "///abc/bcd//chi/h i j/"
./prefix "/abèc/bcd/cdf" "/abèc/bcd/"

two examples :

$ ./prefix "/abc///zzz/../bcd/cdf" "///abc/bcd//chi/h i j/"
/abc/bcd + chi/h i j
$ ./prefix "/abèc/bcd/cdf" "/abèc/bcd/"
/abèc/bcd + .

If you desire to decompose both paths, you may either modify the script or apply it twice, changing the order or arguments.

I am not too happy with variables names ... but my first bad grade in programming was due to a failed alpha-conversion (one occurrence forgotten). So I leave it as is.

P.S. You may want to unify presentation of the relative path (second part of the decomposition) when empty : it can come as "." or as "/" in one case, when both paths are just "/".

4
  • realpath is by no means a standard utility. The Debian/Ubuntu version is only pulled in as a dependency by a few packages and doesn't have a -m option. The GNU utility to canonicalize paths is readlink, which also exists (with fewer options) on *BSD. May 28, 2013 at 12:48
  • AFAIK realpath is a GNU utility with a FSF copyright, and it does have a -m option. But your remark helped me notice I had forgotten another option, -s, to prevent symlink expansion. Without -s option, it does the same job on canonicalized paths.
    – babou
    May 28, 2013 at 19:32
  • Oh, that's a recent addition. Until recently, realpath was a third-party utility (or rather there were several utilities with that name), with fewer options. May 28, 2013 at 19:37
  • From the man page on my machine: GNU coreutils 8.15 January 2012 REALPATH(1)
    – babou
    May 28, 2013 at 19:48
0

Stéphane Chazelas has already shown a sed-based solution. I came across a slightly different sed expression by ack that I customize below to answer this question. Specifically, I restrict it to path components and handle the possibility of newlines in the path components. I then demonstrate using it to decompose path specs into longest common leading path components + remaining path components.

We'll start with ack's sed expression (I switched it to ERE syntax ):

sed -E '$!{N;s/^(.*).*\n\1.*$/\1\n\1/;D;}' <<"EOF'
/abc/bcd/cdf
/abc/bcd/cdf/foo
/abc/bcd/chi/hij
/abc/bcd/cdd
EOF

/abc/bcd/c as expected. ✔️

To restrict it to path components:

sed -E '$!{N;s|^(.*/).*\n\1.*$|\1\n\1|;D;};s|/$||' <<'EOF'
/abc/bcd/cdf
/abc/bcd/cdf/foo
/abc/bcd/chi/hij
/abc/bcd/cdd
EOF

/abc/bcd as expected. ✔️

Handle path components with newlines

For testing purposes, we will use this array of path specs:

a=(
  $'/a\n/b/\nc  d\n/\n\ne/f'
  $'/a\n/b/\nc  d\n/\ne/f'
  $'/a\n/b/\nc  d\n/\ne\n/f'
  $'/a\n/b/\nc  d\n/\nef'
)

By inspection we can see that the longest common leading path component is:

$'/a\n/b/\nc  d\n'

This can be computed and captured in a variable with the following:

longest_common_leading_path_component=$(
  printf '%s\0' "${a[@]}" \
    | sed -zE '$!{N;s|^(.*/).*\x00\1.*$|\1\x00\1|;D;};s|/$||' \
    | tr \\0 x # replace trailing NUL with a dummy character ②
)
# Remove the dummy character
longest_common_leading_path_component=${longest_common_leading_path_component%x} 
# Inspect result
echo "${longest_common_leading_path_component@Q}" # ③

Result:

$'/a\n/b/\nc  d\n'

as expected. ✔️


Continuing with our test case, we now illustrate how to decompose the path specs into longest common leading path components + remaining path components with the following:

for e in "${a[@]}"; do
  remainder=${e#"$longest_common_leading_path_component/"}
  printf '%-26s -> %s + %s\n' \
    "${e@Q}" \
    "${longest_common_leading_path_component@Q}" \
    "${remainder@Q}"
done

Result:

$'/a\n/b/\nc  d\n/\n\ne/f' -> $'/a\n/b/\nc  d\n' + $'\n\ne/f'
$'/a\n/b/\nc  d\n/\ne/f'   -> $'/a\n/b/\nc  d\n' + $'\ne/f'
$'/a\n/b/\nc  d\n/\ne\n/f' -> $'/a\n/b/\nc  d\n' + $'\ne\n/f'
$'/a\n/b/\nc  d\n/\nef'    -> $'/a\n/b/\nc  d\n' + $'\nef'

① I always add the -E option to sed and grep to switch them to ERE syntax for better consistency with other tools/languages I use, e.g., awk, bash, perl, javascript, and java.

② To preserve any trailing newlines in this command substitution, we used the usual technique of appending a dummy character that is chopped off afterwards. We combined the removal of the trailing NUL with the addition of the dummy character (we chose x) in one step using tr \\0 x.

③ The ${parameter@Q} expansion results in "a string that is the value of parameter quoted in a format that can be reused as input." – bash reference manual. Requires bash 4.4+ (discussion). Otherwise, you can inspect the result using one of the following:

printf '%q' "$longest_common_leading_path_component"
printf '%s' "$longest_common_leading_path_component" | od -An -tc
od -An -tc < <(printf %s "$longest_common_leading_path_component")
od -An -tc <<<$longest_common_leading_path_component # ④

④ Be aware that here-strings add a newline (discussion).

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .