path.c

linux subdivision ying gai ke yi le ba

int
svn_path_compare_paths (const char *path1,
                        const char *path2)
{
  apr_size_t path1_len = strlen (path1);
  apr_size_t path2_len = strlen (path2);
  apr_size_t min_len = ((path1_len < path2_len) ? path1_len : path2_len);
  apr_size_t i = 0;

  assert (is_canonical (path1, path1_len));
  assert (is_canonical (path2, path2_len));

  /* Skip past common prefix. */
  while (i < min_len && path1[i] == path2[i])
    ++i;

  /* Are the paths exactly the same? */
  if ((path1_len == path2_len) && (i >= min_len))
    return 0;    

  /* Children of paths are greater than their parents, but less than
     greater siblings of their parents. */
  if ((path1[i] == '/') && (path2[i] == 0))
    return 1;
  if ((path2[i] == '/') && (path1[i] == 0))
    return -1;
  if (path1[i] == '/')
    return -1;
  if (path2[i] == '/')
    return 1;

  /* Common prefix was skipped above, next character is compared to
     determine order */
  return path1[i] < path2[i] ? -1 : 1;
}


/* Return the string length of the longest common ancestor of PATH1 and PATH2.  
 *
 * This function handles everything except the URL-handling logic 
 * of svn_path_get_longest_ancestor, and assumes that PATH1 and 
 * PATH2 are *not* URLs.  
 *
 * If the two paths do not share a common ancestor, return 0. 
 *
 * New strings are allocated in POOL.
 */
static apr_size_t
get_path_ancestor_length (const char *path1,
                          const char *path2,
                          apr_pool_t *pool)
{
  apr_size_t path1_len, path2_len;
  apr_size_t i = 0;
  apr_size_t last_dirsep = 0;
  
  path1_len = strlen (path1);
  path2_len = strlen (path2);

  if (SVN_PATH_IS_EMPTY (path1) || SVN_PATH_IS_EMPTY (path2))
    return 0;

  while (path1[i] == path2[i])
    {
      /* Keep track of the last directory separator we hit. */
      if (path1[i] == '/')
        last_dirsep = i;

      i++;

      /* If we get to the end of either path, break out. */
      if ((i == path1_len) || (i == path2_len))
        break;
    }

  /* last_dirsep is now the offset of the last directory separator we
     crossed before reaching a non-matching byte.  i is the offset of
     that non-matching byte. */
  if (((i == path1_len) && (path2[i] == '/'))
           || ((i == path2_len) && (path1[i] == '/'))
           || ((i == path1_len) && (i == path2_len)))
    return i;
  else
    return last_dirsep;
}


char *
svn_path_get_longest_ancestor (const char *path1,
                               const char *path2,
                               apr_pool_t *pool)
{
  svn_boolean_t path1_is_url, path2_is_url;
  path1_is_url = svn_path_is_url (path1);
  path2_is_url = svn_path_is_url (path2);

  if (path1_is_url && path2_is_url) 
    {
      apr_size_t path_ancestor_len; 
      apr_size_t i = 0;

      /* Find ':' */
      while (1)
        {
          /* No shared protocol => no common prefix */
          if (path1[i] != path2[i])
            return apr_pmemdup (pool, SVN_EMPTY_PATH, 
                                sizeof (SVN_EMPTY_PATH));

          if (path1[i] == ':') 
            break;

          /* They're both URLs, so EOS can't come before ':' */
          assert ((path1[i] != '\0') && (path2[i] != '\0'));

          i++;
        }

      i += 3;  /* Advance past '://' */

      path_ancestor_len = get_path_ancestor_length (path1 + i, path2 + i, 
                                                    pool);

      if (path_ancestor_len == 0)
        return apr_pmemdup (pool, SVN_EMPTY_PATH, sizeof (SVN_EMPTY_PATH));
      else
        return apr_pstrndup (pool, path1, path_ancestor_len + i); 
    }

  else if ((! path1_is_url) && (! path2_is_url))
    { 
      return apr_pstrndup (pool, path1, 
                           get_path_ancestor_length (path1, path2, pool));
    }

  else
    {
      /* A URL and a non-URL => no common prefix */
      return apr_pmemdup (pool, SVN_EMPTY_PATH, sizeof (SVN_EMPTY_PATH));
    }
}


const char *
svn_path_is_child (const char *path1,
                   const char *path2,
                   apr_pool_t *pool)
{
  apr_size_t i;

  /* assert (is_canonical (path1, strlen (path1)));  ### Expensive strlen */
  /* assert (is_canonical (path2, strlen (path2)));  ### Expensive strlen */

  /* Allow "" and "foo" to be parent/child */
  if (SVN_PATH_IS_EMPTY (path1))               /* "" is the parent  */
    {
      if (SVN_PATH_IS_EMPTY (path2)            /* "" not a child    */
          || path2[0] == '/')                  /* "/foo" not a child */
        return NULL;
      else
        return apr_pstrdup (pool, path2);      /* everything else is child */
    }

  /* Reach the end of at least one of the paths.  How should we handle
     things like path1:"foo///bar" and path2:"foo/bar/baz"?  It doesn't
     appear to arise in the current Subversion code, it's not clear to me
     if they should be parent/child or not. */
  for (i = 0; path1[i] && path2[i]; i++)
    if (path1[i] != path2[i])
      return NULL;

  /* There are two cases that are parent/child
          ...      path1[i] == '\0'
          .../foo  path2[i] == '/'
      or
          /        path1[i] == '\0'
          /foo     path2[i] != '/'
  */
  if (path1[i] == '\0' && path2[i])
    {
      if (path2[i] == '/')
        return apr_pstrdup (pool, path2 + i + 1);
      else if (i == 1 && path1[0] == '/')
        return apr_pstrdup (pool, path2 + 1);
    }

  /* Otherwise, path2 isn't a child. */
  return NULL;
}


apr_array_header_t *
svn_path_decompose (const char *path,
                    apr_pool_t *pool)
{
  apr_size_t i, oldi;

  apr_array_header_t *components = 
    apr_array_make (pool, 1, sizeof(const char *));

  /* assert (is_canonical (path, strlen (path)));  ### Expensive strlen */

  if (SVN_PATH_IS_EMPTY (path))
    return components;  /* ### Should we return a "" component? */

  /* If PATH is absolute, store the '/' as the first component. */
  i = oldi = 0;
  if (path[i] == '/')
    {
      char dirsep = '/';

      *((const char **) apr_array_push (components))
        = apr_pstrmemdup (pool, &dirsep, sizeof (dirsep));

      i++;
      oldi++;
      if (path[i] == '\0') /* path is a single '/' */
        return components;
    }

  do
    {
      if ((path[i] == '/') || (path[i] == '\0'))
        {
          if (SVN_PATH_IS_PLATFORM_EMPTY (path + oldi, i - oldi))
            /* ### Should canonicalization strip "//" and "/./" substrings? */
            *((const char **) apr_array_push (components)) = SVN_EMPTY_PATH;
          else
            *((const char **) apr_array_push (components))
              = apr_pstrmemdup (pool, path + oldi, i - oldi);

          i++;
          oldi = i;  /* skipping past the dirsep */
          continue;
        }
      i++;
    }
  while (path[i-1]);

  return components;
}


svn_boolean_t
svn_path_is_single_path_component (const char *name)
{
  /* assert (is_canonical (name, strlen (name)));  ### Expensive strlen */

  /* Can't be empty or `..'  */
  if (SVN_PATH_IS_EMPTY (name)
      || (name[0] == '.' && name[1] == '.' && name[2] == '\0'))
    return FALSE;

  /* Slashes are bad, m'kay... */
  if (strchr (name, '/') != NULL)
    return FALSE;

  /* It is valid.  */
  return TRUE;
}


svn_boolean_t
svn_path_is_backpath_present (const char *path)
{
  int len = strlen (path);
  
  if (! strcmp (path, ".."))
    return TRUE;

  if (! strncmp (path, "../", 3))
    return TRUE;
  
  if (strstr (path, "/../") != NULL)
    return TRUE;

  if (len >= 3
      && (! strncmp (path + len - 3, "/..", 3)))
    return TRUE;

  return FALSE;
}


/*** URI Stuff ***/

/* Examine PATH as a potential URI, and return a substring of PATH
   that immediately follows the (scheme):// portion of the URI, or
   NULL if PATH doesn't appear to be a valid URI.  The returned value
   is not alloced -- it shares memory with PATH. */
static const char *
skip_uri_schema (const char *path)
{
  apr_size_t j;
  apr_size_t len = strlen (path);

  /* ### Taking strlen() initially is inefficient.  It's a holdover
     from svn_stringbuf_t days. */

  /* Make sure we have enough characters to even compare. */
  if (len < 4)
    return NULL;

  /* Look for the sequence '://' */
  for (j = 0; j < len - 3; j++)
    {
      /* We hit a '/' before finding the sequence. */
      if (path[j] == '/')
        return NULL;

      /* Skip stuff up to the first ':'. */
      if (path[j] != ':')
        continue;

      /* Current character is a ':' now.  It better not be the first
         character. */
      if (j == 0)
        return NULL;

      /* Expecting the next two chars to be '/' */

      if ((path[j + 1] == '/')
          && (path[j + 2] == '/'))
        return path + j + 3;
      
      return NULL;
    }
     
  return NULL;
}

svn_boolean_t 
svn_path_is_url (const char *path)
{
  /* ### This function is reaaaaaaaaaaaaaally stupid right now.
     We're just going to look for:
 
        (scheme)://(optional_stuff)

     Where (scheme) has no ':' or '/' characters.

     Someday it might be nice to have an actual URI parser here.
  */
  return skip_uri_schema (path) ? TRUE : FALSE;
}



/* Here is the BNF for path components in a URI. "pchar" is a
   character in a path component.

      pchar       = unreserved | escaped | 
                    ":" | "@" | "&" | "=" | "+" | "$" | ","
      unreserved  = alphanum | mark
      mark        = "-" | "_" | "." | "!" | "~" | "*" | "'" | "(" | ")"

   Note that "escaped" doesn't really apply to what users can put in
   their paths, so that really means the set of characters is:

      alphanum | mark | ":" | "@" | "&" | "=" | "+" | "$" | "," 
*/
static const int uri_char_validity[256] = {
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 1, 0, 0, 1, 0, 1, 1,   1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1,   1, 1, 1, 0, 0, 1, 0, 0,

  /* 64 */
  1, 1, 1, 1, 1, 1, 1, 1,   1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1,   1, 1, 1, 0, 0, 0, 0, 1,
  0, 1, 1, 1, 1, 1, 1, 1,   1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1,   1, 1, 1, 0, 0, 0, 1, 0,

  /* 128 */
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,

  /* 192 */
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
};

svn_boolean_t 
svn_path_is_uri_safe (const char *path)
{
  apr_size_t i;

  /* Skip the schema. */
  path = skip_uri_schema (path);

  /* No schema?  Get outta here. */
  if (! path)
    return FALSE;

  /* Skip to the first slash that's after the schema. */
  path = strchr (path, '/');

  /* If there's no first slash, then there's only a host portion;
     therefore there couldn't be any uri-unsafe characters after the
     host... so return true. */
  if (path == NULL)
    return TRUE;

  for (i = 0; path[i]; i++)
    {
      /* Allow '%XX' (where each X is a hex digit) */
      if (path[i] == '%')
        {
          if (apr_isxdigit (path[i + 1]) && apr_isxdigit (path[i + 2]))
            {
              i += 2;
              continue;
            }