Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

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.

share|improve this question
    
Near-duplicate: How do I find the overlap of two strings in bash? –  Gilles Mar 7 '13 at 0:47
    
@Gilles - only near duplicate , because there are utilities available for path manipulation only that can help here, but have no equivalent for arbitrary strings, as far as I know. –  babou May 27 '13 at 14:06

4 Answers 4

up vote 1 down vote accepted

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

share|improve this answer
    
@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. –  Gilles Mar 7 '13 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 '13 at 12:37
    
@babou I get / as the common prefix of / and /, what's the problem? And what's the problem with spaces? –  Gilles May 28 '13 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 '13 at 14:02
    
@babou $ split_common_prefix / /; echo $?; echo "$common_prefix"0 / –  Gilles May 28 '13 at 17: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).

share|improve this answer

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
share|improve this answer

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 "/".

share|improve this answer
    
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. –  Gilles May 28 '13 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 '13 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. –  Gilles May 28 '13 at 19:37
    
From the man page on my machine: GNU coreutils 8.15 January 2012 REALPATH(1) –  babou May 28 '13 at 19:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.