title: Portable recursive regex substitution within a string to resolve .. in path
body: <p>In Bash, what is the most elegant and portable way to resolve all occurrences of <code>..</code> within a string representing a path?</p>
  
  <p>Example: path <code>/aa/bb/cc/../dd/ee/../../ff/gg/hh/ii/jj/../../../kk</code> becomes <code>/aa/bb/ff/gg/kk</code></p>
  
  <p>I wrote two functions that mostly accomplish this goal. (It was actually one, and it was longer, but I had a few ideas while writing this question…)</p>
  
  <p>One uses repetition:</p>
  
  <pre class="lang-sh prettyprint-override"><code>resolve_parents () {
    local previous result=$1
    local re="\/$re|$re\/" re='[^\/]{1,}\/\.\.'
    while [[ $result != $previous ]]; do
      previous=$result
      result=$(echo "$result" | awk '{sub(/\/'$re'/,"")} 1')
    done
    echo "$result"
  }
  
  resolve_parents '/aa/bb/cc/../dd/ee/../../ff/gg/hh/ii/jj/../../../kk'
  </code></pre>
  
  <p>And one uses recursion:</p>
  
  <pre class="lang-sh prettyprint-override"><code>resolve_parents_r () {
    local re="\/$re|$re\/" re='[^\/]{1,}\/\.\.'
    local result=$(echo "$1" | awk '{sub(/\/'$re'/,"")} 1')
    [[ $1 = $result ]] &amp;&amp; echo "$1" || resolve_parents_r "$result"
  }
  </code></pre>
  
  <p>They do not remove a leading <code>..</code>, which would necessitate determining the base directory to get its parent. I am OK with that limitation. Also, it does not fully reduce <code>aa/..</code> to an empty string. I suppose I would either need to separately apply a regex at the end without a leading or trailing slash, or add a slash to the string at the start and remove it at the end.</p>
  
  <p><strong>Background</strong></p>
  
  <p>I have a function that runs <code>ln -s "$source" "$target"</code>. It needs to throw an error if <code>$source</code> does not exist. Confirming <code>$source</code> exists is straightforward if it is an absolute path, but relative paths must be normalized. I accomplish this by:</p>
  
  <pre class="lang-sh prettyprint-override"><code>[[ -d $target ]] &amp;&amp; target=$target/$(basename "$source")
  local abs_source=$source
  [[ $source = /* ]] || abs_source=$( cd "$target/../$source" &amp;&amp; pwd -P )
  </code></pre>
  
  <p>The first line is necessary to ensure <code>$target</code> ends with the target name. Otherwise the <code>../</code> would need to be omitted if <code>$target</code> is a directory, but would be required if <code>$target</code> already ends with intended link name. <code>cd</code> works fine for resolving paths containing double dot parent references only if the directory exists. Since the test occurs before the link is created, <code>$target</code> unfortunately but necessarily does not exist.</p>
  
  <p>Thus, I am left to determine whether <code>$source</code> exists by deleting matches of the regular expression <code>[^/]+/\.\.</code> either preceded or followed by a slash, but not both. (I considered deleting the matches and then deleting sequences of <code>//</code>, but that can result in a path that was relative becoming absolute or a path that ended in a target name becoming a directory, which would get another target name appended. Yikes!) I cannot use a global regex replace with that pattern, as that could delete sequences like <code>../..</code>. I am not aware of a command that does global replace by resetting the search cursor to the beginning of the string upon each match, so I wrote this into a <code>while</code> loop.</p>
  
  <p>I hoped to use a pattern stored in <code>$re</code> for the sake of simplicity, but that soon became rather complicated when I tried to do the replace with <code>sed</code> and found the <code>+</code> requires extended regular expressions are sometimes turned on with <code>sed -E</code> (on OSX) and sometimes with <code>sed -r</code>. Upon replacing <code>+</code> with <code>{1,}</code>, I found the braces needed escaping for <code>sed</code>, but escaping them caused the Bash regex match to fail. I migrated to using <code>awk</code> and its <code>sub</code> command, which apparently requires the delimiter to be <code>/</code>, so I needed to escape those in my pattern as well.</p>
  
  <p>To prevent infinite loops due to an interpretation mismatch between the regex in Bash and <code>awk</code>, I first added a counter variable with an arbitrary limit. I improved that to a difference test, so <code>while [[ $result =~ $re ]] &amp;&amp; (( count &lt; 1000 ))</code> became <code>while [[ $result =~ $re &amp;&amp; $result != $previous ]]</code>. Then after experimenting with making an actually recursive function, I realized the <code>$result =~ $re &amp;&amp;</code> was not necessary.</p>
  
  <p>At this point I start to wonder whether I really care if my <code>$source</code>s are nonexistent!</p>