/* id.c : operations on node and node revision ID's
 *
 * ====================================================================
 * Copyright (c) 2000-2002 CollabNet.  All rights reserved.
 *
 * This software is licensed as described in the file COPYING, which
 * you should have received as part of this distribution.  The terms
 * are also available at http://subversion.tigris.org/license-1.html.
 * If newer versions of this license are posted there, you may use a
 * newer version instead, at your option.
 *
 * This software consists of voluntary contributions made by many
 * individuals.  For exact contribution history, see the revision
 * history and logs, available at http://subversion.tigris.org/.
 * ====================================================================
 */

#include <string.h>
#include <stdlib.h>

#include "svn_fs.h"
#include "id.h"
#include "key-gen.h"
#include "validate.h"


/* Finding the length of an ID.  */


int
svn_fs__id_length (const svn_fs_id_t *id)
{
  int len;

  for (len = 0; id[len] != -1; len++)
    continue;

  return len;
}


/* Comparing node ID's.  */

int
svn_fs__id_eq (const svn_fs_id_t *a, const svn_fs_id_t *b)
{
  int i;

  for (i = 0; a[i] == b[i]; i++)
    if (a[i] == -1)
      return 1;

  return 0;
}


int
svn_fs__id_is_ancestor (const svn_fs_id_t *a, const svn_fs_id_t *b)
{
  int i = 0;

  for (;;)
    {
      /* Invariant: i is even, and for all j < i, a[j] == b[j].
         Keep in mind: every even-numbered entry in A or B is a
         node/branch number; every odd-numbered entry is a revision
         number.  So i is pointing at a node/branch number.  */

      /* If we've reached the end of A, then either A and B are equal,
         or A is a prefix of B, so A is an ancestor of B.  Examples:
         100.20 vs. 100.20; 100.20 vs. 100.20.3.2  */
      if (a[i] == -1)
        return 1;

      /* If the node/branch numbers differ, then they're unrelated.
         Examples: 100.20 vs. 101.20; 100.20.2.3 vs. 100.20.3.1;

         This also catches the case where B has ended before A ---
         they're related, but A isn't B's ancestor.
         Example: 100.20.3.2 vs 100.20.  */
      if (a[i] != b[i])
        return 0;

      /* If A's revision number is greater than B's, then A is not B's
         ancestor.  Examples: 100.30 vs 100.20; 2.3.4.5 vs 2.3.4.4.  */
      if (a[i+1] > b[i+1])
        return 0;

      /* If A's revision number is less than B's, then A is an ancestor
         iff its ID ends now.  Examples: 100.30 vs 100.31; 100.30 vs
         100.32.2.4.  */
      if (a[i+1] < b[i+1])
        return (a[i+2] == -1);

      /* Otherwise, we've established that the node/branch numbers and
         revision numbers are equal, so go around again.  */
      i += 2;
    }
}


/* Compute the distance from the node revision A to the node revision
   identified by the first PREFIX elements of A.  In other words, this
   is the distance from a node revision to some branch of the node
   revision.  */
static int
distance_from_prefix (const svn_fs_id_t *a, int prefix)
{
  int i;
  int d = 0;

  for (i = 0; a[prefix + i] != -1; i += 2)
    d += a[prefix + i + 1];

  return d;
}


int
svn_fs_id_distance (const svn_fs_id_t *a, const svn_fs_id_t *b)
{
  int i;

  /* Are they completely unrelated?  */
  if (a[0] != b[0])
    return -1;

  /* Skip any common prefix.  */
  for (i = 0; a[i] == b[i] && a[i] != -1 && a[i+1] == b[i+1]; i += 2)
    continue;

  /* If they're completely identical, then the distance is zero.  */
  if (a[i] == -1 && b[i] == -1)
    return 0;

  /* Are they (branches off) different revisions of the same node?
     Account for the distance between the two revisions.  */
  if (a[i] == b[i])
    return (distance_from_prefix (a, i+2)
            + distance_from_prefix (b, i+2)
            + abs (a[i+1] - b[i+1]));
  else
    /* Or two branches off the same node revision?  */
    return (distance_from_prefix (a, i)
            + distance_from_prefix (b, i));
}


int
svn_fs__id_is_parent (const svn_fs_id_t *parent,
                      const svn_fs_id_t *child)
{
  int i;

  for (i = 0; parent[i] == child[i]; i++)
    {
      /* If they're completely identical, then CHILD isn't a direct
         child of PARENT.  */
      if (parent[i] == -1)
        return 0;
    }

  /* Is CHILD the next revision of PARENT?  */
  if ((i & 1) == 1
      && child[i] == parent[i] + 1
      && child[i + 1] == -1
      && parent[i + 1] == -1)
    return 1;

  /* Is CHILD the first revision of any branch from PARENT?  */
  if ((i & 1) == 0
      && parent[i] == -1
      && child[i + 1] != -1
      && child[i + 2] == 1
      && child[i + 3] == -1)
    return 1;

  /* Anything else is no good.  */
  return 0;
}


/* Parsing and unparsing node ID's.  */

svn_fs_id_t *
svn_fs_parse_id (const char *data,
                 apr_size_t data_len,
                 apr_pool_t *pool)
{
  svn_fs_id_t *id;
  int id_len;
  
  /* Count the number of components in the ID, and check its syntax.  */
  id_len = svn_fs__count_id_components (data, data_len);
  if (id_len == 0)
      return 0;

  /* Allocate the ID array.  Note that if pool is zero, apr_palloc
     just calls malloc, which meets our promised interface.  */
  if (pool)
    id = apr_palloc (pool, sizeof (*id) * (id_len + 1));
  else
    {
      id = malloc (sizeof (*id) * (id_len + 1));
      if (! id)
        abort(); /* couldn't malloc */
    }

  {
    int i = 0;
    const char *end = data + data_len;

    for (;;)
      {
        const char *next;
        id[i++] = svn_fs__getsize (data, end - data, &next, 100000000);
        if (next == end)
          break;
        if (! next
            || *next != '.')
          {
            if (! pool) free (id);
            return 0;
          }

        data = next + 1;
      }

    id[i] = -1;
  }

  return id;
}


svn_stringbuf_t *
svn_fs_unparse_id (const svn_fs_id_t *id,
                   apr_pool_t *pool)
{
  svn_stringbuf_t *unparsed = svn_stringbuf_ncreate (0, 0, pool);
  int i;

  for (i = 0; id[i] != -1; i++)
    {
      char buf[200];
      int len = svn_fs__putsize (buf, sizeof (buf), id[i]);

      if (len == 0)
        abort ();

      if (id[i + 1] != -1)
        buf[len++] = '.';

      svn_stringbuf_appendbytes (unparsed, buf, len);
    }

  return unparsed;
}


/* Copying ID's.  */

svn_fs_id_t *
svn_fs__id_copy (const svn_fs_id_t *id, apr_pool_t *pool)
{
  return apr_pmemdup (pool,
                      id,
                      (svn_fs__id_length (id) + 1) * sizeof (id[0]));
}


/* Predecessor ID's. */

/* ### kff todo: might it be a good thing to abstract out the
   successor logic from svn_fs__new_successor_id() and put it in a
   function here, svn_fs_successor_id(), to match
   svn_fs__id_predecessor()?  Investigate. */

svn_fs_id_t *
svn_fs__id_predecessor (const svn_fs_id_t *id, apr_pool_t *pool)
{
  svn_fs_id_t *predecessor_id;
  int len;

  len = svn_fs__id_length (id);
  predecessor_id = svn_fs__id_copy (id, pool);

  predecessor_id[len - 1]--;

  if (predecessor_id[len - 1] > 0)
    {
      /* Decrementing the last digit still resulted in a valid node
         revision number, so that must be the predecessor of ID.
         Return the predecessor. */
      return predecessor_id;
    }

  /* Else decrementing the last digit still resulted in a branch
     number, so the predecessor is the node revision on which the
     branch itself is based. */
  if (len > 2)
    predecessor_id[len - 2] = -1;
  else
    predecessor_id = NULL;
  
  return predecessor_id;
}

/* --------------------------------------------------------------------- */

/*** Related-ness checking */

/*  Things to remember:

    - If B is a copy of directory A, B's children are id-related to the
      corresponding children of A.
 
    - Brand new nodes (like, resulting from adds and copies) have the
      first component of their node id > older nodes. 

    Also note:  it is acceptable for this function to call back into
    public FS API interfaces because it does not itself use trails.  */
svn_error_t *
svn_fs_check_related (int *related, 
                      svn_fs_t *fs,
                      const svn_fs_id_t *id1,
                      const svn_fs_id_t *id2,
                      apr_pool_t *pool)
{
  const svn_fs_id_t *older, *younger;
  svn_fs_id_t *tmp_id;

  /* Default answer: not related, until proven otherwise. */
  *related = 0;

  /* Are the two IDs related via node id ancestry? */
  if (svn_fs_id_distance (id1, id2) != -1)
    {
      *related = 1;
      return SVN_NO_ERROR;
    }
  
  /* Figure out which id is youngest. */
  if (id1[0] > id2[0])
    {
      older = id2;
      younger = id1;
    }
  else
    {
      older = id1;
      younger = id2;
    }

  /* Copy YOUNGER so we can possible tweak it later. */
  tmp_id = svn_fs__id_copy (younger, pool);

  /* Now, we loop here from TMP_ID, through each of its predecessors,
     until no predecessors exist, trying to find some relationship to
     the OLDER id. */
  do
    {
      svn_revnum_t rev = SVN_INVALID_REVNUM;
      const char *cp_path = NULL;
      svn_fs_root_t *root;
      svn_stringbuf_t *id_str = svn_fs_unparse_id (tmp_id, pool);
      svn_fs_id_t *copy_id;
      int len = svn_fs__id_length (tmp_id);

      /* See if OLDER is a copy of another node. */
      svn_fs_id_root (&root, fs, pool);
      SVN_ERR (svn_fs_copied_from (&rev, &cp_path, root, id_str->data, pool));
      if (SVN_IS_VALID_REVNUM (rev))
        {
          SVN_ERR (svn_fs_revision_root (&root, fs, rev, pool));
          SVN_ERR (svn_fs_node_id (&copy_id, root, cp_path, pool));
          svn_fs_check_related (related, fs, older, copy_id, pool);
          if (*related)
            return SVN_NO_ERROR;
        }

      /* Hack up TMP_ID so that it represents its own predecessor. */
      tmp_id[len - 1]--;
      if (tmp_id[len - 1] == 0)
        tmp_id[len - 2] = -1;
    }
  while (tmp_id[0] != -1);

  return SVN_NO_ERROR;
}


/* 
 * local variables:
 * eval: (load-file "../../tools/dev/svn-dev.el")
 * end:
 */