/* path.c - Don Yang (uguu.org)

   Note that Windows absolute paths (those that start with drive
   letter) are not recognized as absolute paths, and all '\\'
   separators are replaced with '/'.

   12/27/05
                                                                           */
/*@ -mayaliasunique @*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "path.h"

/* Same as strdup, but never returns NULL */
static /*@only@*//*@notnull@*/char *CopyString(/*@observer@*/char *s)
{
   char *r;
   if( (r = (char*)malloc(strlen(s) + 1)) == NULL )
      abort();
   return strcpy(r, s);
}

/* Canonicalize path in-place */
/*@dependent@*/char *CanonicalizePath(/*@dependent@*/char *path)
{
   char *r, *w, *p, *root;
   int dot_count;

   #ifdef _WIN32
      for(p = path; (p = strchr(p, '\\')) != NULL; *p++ = '/');
   #endif

   dot_count = 0;
   for(r = w = root = path; *r != '\0';)
   {
      if( *r == '.' )
      {
         /* Only count dots specially if they follow a path separator */
         if( dot_count >= 0 )
            dot_count++;
         *(w++) = *(r++);
         continue;
      }
      if( *r == '/' )
      {
         /* Path separator */
         if( dot_count == 1 )
         {
            /* Remove . reference */
            r++;
            w--;
         }
         else if( dot_count == 2 )
         {
            /* Remove .. reference */

            /* Move up one directory, set p to point at "/.." */
            for(p = w - 1; p != root && *p != '/'; p--);
            if( *p == '/' )
            {
               /* Move up one more directory, set p to point at "/parent" */
               for(p--; p != root && *p != '/'; p--);
               w = p;
               if( *p == '/' )
                  *(w++) = *(r++);
               else
                  r++;
            }
            else
            {
               /* Can not back up more directories, set this to be new root */
               *(w++) = *(r++);
               root = w;
            }
         }
         else
         {
            /* Too many dots */
            *(w++) = *(r++);
         }
         dot_count = 0;
      }
      else
      {
         /* Not a path separator, stop counting dots */
         *(w++) = *(r++);
         dot_count = -1;
      }
   }

   /* Copy terminating NUL */
   *w = '\0';
   return path;
}

/* Get relative path from source to target */
/*@only@*/char *RelativePath(/*@observer@*/char *source,
                             /*@observer@*/char *target)
{
   char *x, *y, *z, *r;
   size_t d;

   /* Return full path if source or target is not relative */
   if( *source == '/' || *target == '/' )
      return CopyString(target);

   /* Find common root */
   x = source;
   y = target;
   while( *x == *y && *x != '\0' && *y != '\0' )
   {
      x++;
      y++;
   }
   if( *x == '\0' && *y == '\0' )
      return CopyString(target);

   /* Move back to nearest path separator */
   if( x != source )
   {
      for(x--; x != source && *x != '/'; x--);
   }
   if( y != target )
   {
      for(y--; y != target && *y != '/'; y--);
   }

   /* Count source directory depth */
   if( *x == '/' && *y == '/' )
   {
      x++;
      y++;
   }
   d = 0;
   for(z = x; *z != '\0'; z++)
   {
      if( *z == '/' )
         d++;
   }

   /* Prepend .. references and return */
   if( (r = (char*)malloc(d * 3 + strlen(y) + 1)) == NULL )
      abort();
   for(z = r; d > 0; d--)
   {
      *(z++) = '.';
      *(z++) = '.';
      *(z++) = '/';
   }
   if( *y == '/' )
      y++;
   strcpy(z, y);
   return r;
}