diff_file.c

linux subdivision ying gai ke yi le ba

/*
 * diff_file.c :  routines for doing diffs on files
 *
 * ====================================================================
 * Copyright (c) 2000-2004 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 <apr.h>
#include <apr_pools.h>
#include <apr_general.h>
#include <apr_md5.h>
#include <apr_file_io.h>
#include <apr_file_info.h>
#include <apr_time.h>
#include <apr_mmap.h>

#include "svn_error.h"
#include "svn_diff.h"
#include "svn_types.h"
#include "svn_string.h"
#include "svn_io.h"
#include "svn_pools.h"
#include "diff.h"


typedef struct svn_diff__file_token_t
{
  struct svn_diff__file_token_t *next;
  svn_diff_datasource_e datasource;
  apr_off_t offset;
  apr_off_t length;
} svn_diff__file_token_t;


typedef struct svn_diff__file_baton_t
{
  const char *path[4];

  apr_file_t *file[4];
  apr_off_t size[4];

  int chunk[4];
  char *buffer[4];
  char *curp[4];
  char *endp[4];

  svn_diff__file_token_t *tokens;

  apr_pool_t *pool;
} svn_diff__file_baton_t;


static
int
svn_diff__file_datasource_to_index(svn_diff_datasource_e datasource)
{
  switch (datasource)
    {
    case svn_diff_datasource_original:
      return 0;

    case svn_diff_datasource_modified:
      return 1;

    case svn_diff_datasource_latest:
      return 2;

    case svn_diff_datasource_ancestor:
      return 3;
    }

  return -1;
}

/* Files are read in chunks of 128k.  There is no support for this number
 * whatsoever.  If there is a number someone comes up with that has some
 * argumentation, let's use that.
 */
#define CHUNK_SHIFT 17
#define CHUNK_SIZE (1 << CHUNK_SHIFT)

#define chunk_to_offset(chunk) ((chunk) << CHUNK_SHIFT)
#define offset_to_chunk(offset) ((offset) >> CHUNK_SHIFT)
#define offset_in_chunk(offset) ((offset) & (CHUNK_SIZE - 1))


/* Read a chunk from a FILE into BUFFER, starting from OFFSET, going for
 * *LENGTH.  The actual bytes read are stored in *LENGTH on return.
 */
static APR_INLINE
svn_error_t *
read_chunk(apr_file_t *file, const char *path,
           char *buffer, apr_size_t length,
           apr_off_t offset, apr_pool_t *pool)
{
  /* XXX: The final offset may not be the one we asked for.
   * XXX: Check.
   */
  SVN_ERR(svn_io_file_seek(file, APR_SET, &offset, pool));
  SVN_ERR(svn_io_file_read_full(file, buffer, length, NULL, pool));

  return SVN_NO_ERROR;
}


/* Map or read a file at PATH. *BUFFER will point to the file
 * contents; if the file was mapped, *FILE and *MM will contain the
 * mmap context; otherwise they will be NULL.  SIZE will contain the
 * file size.  Allocate from POOL.
 */
#if APR_HAS_MMAP
#define MMAP_T_PARAM(NAME) apr_mmap_t **NAME,
#define MMAP_T_ARG(NAME)   &(NAME),
#else
#define MMAP_T_PARAM(NAME)
#define MMAP_T_ARG(NAME)
#endif

static
svn_error_t *
map_or_read_file(apr_file_t **file,
                 MMAP_T_PARAM(mm)
                 char **buffer, apr_off_t *size,
                 const char *path, apr_pool_t *pool)
{
  apr_finfo_t finfo;
  apr_status_t rv;

  *buffer = NULL;

  SVN_ERR(svn_io_file_open(file, path, APR_READ, APR_OS_DEFAULT, pool));
  SVN_ERR(svn_io_file_info_get(&finfo, APR_FINFO_SIZE, *file, pool));

#if APR_HAS_MMAP
  if (finfo.size > APR_MMAP_THRESHOLD)
    {
      rv = apr_mmap_create(mm, *file, 0, finfo.size, APR_MMAP_READ, pool);
      if (rv == APR_SUCCESS)
        {
          *buffer = (*mm)->mm;
        }

      /* On failure we just fall through and try reading the file into
       * memory instead.
       */
    }
#endif /* APR_HAS_MMAP */

   if (*buffer == NULL && finfo.size > 0)
    {
      *buffer = apr_palloc(pool, finfo.size);

      SVN_ERR(svn_io_file_read_full(*file, *buffer, finfo.size, NULL, pool));

      /* Since we have the entire contents of the file we can
       * close it now.
       */
      SVN_ERR(svn_io_file_close(*file, pool));

      *file = NULL;
    }

  *size = finfo.size;

  return SVN_NO_ERROR;
}


static
svn_error_t *
svn_diff__file_datasource_open(void *baton,
                               svn_diff_datasource_e datasource)
{
  svn_diff__file_baton_t *file_baton = baton;
  int idx;
  apr_finfo_t finfo;
  apr_size_t length;
  char *curp;
  char *endp;

  idx = svn_diff__file_datasource_to_index(datasource);

  SVN_ERR(svn_io_file_open(&file_baton->file[idx], file_baton->path[idx],
                           APR_READ, APR_OS_DEFAULT, file_baton->pool));

  SVN_ERR(svn_io_file_info_get(&finfo, APR_FINFO_SIZE, 
                               file_baton->file[idx], file_baton->pool));

  file_baton->size[idx] = finfo.size;
  length = finfo.size > CHUNK_SIZE ? CHUNK_SIZE : finfo.size;

  if (length == 0)
    return SVN_NO_ERROR;

  endp = curp = apr_palloc(file_baton->pool, length);
  endp += length;

  file_baton->buffer[idx] = file_baton->curp[idx] = curp;
  file_baton->endp[idx] = endp;

  SVN_ERR(read_chunk(file_baton->file[idx], file_baton->path[idx],
                     curp, length, 0, file_baton->pool));

  return SVN_NO_ERROR;
}


static
svn_error_t *
svn_diff__file_datasource_close(void *baton,
                                svn_diff_datasource_e datasource)
{
  /* Do nothing.  The compare_token function needs previous datasources
   * to stay available until all datasources are processed.
   */

  return SVN_NO_ERROR;
}


static
svn_error_t *
svn_diff__file_datasource_get_next_token(apr_uint32_t *hash, void **token,
                                         void *baton,
                                         svn_diff_datasource_e datasource)
{
  svn_diff__file_baton_t *file_baton = baton;
  svn_diff__file_token_t *file_token;
  int idx;
  char *endp;
  char *curp;
  char *eol;
  int last_chunk;
  apr_size_t length;
  apr_uint32_t h = 0;

  *token = NULL;

  idx = svn_diff__file_datasource_to_index(datasource);

  curp = file_baton->curp[idx];
  endp = file_baton->endp[idx];

  last_chunk = offset_to_chunk(file_baton->size[idx]);

  if (curp == endp
      && last_chunk == file_baton->chunk[idx])
    {
      return SVN_NO_ERROR;
    }

  /* Get a new token */
  file_token = file_baton->tokens;
  if (file_token)
    {
      file_baton->tokens = file_token->next;
    }
  else
    {
      file_token = apr_palloc(file_baton->pool, sizeof(*file_token));
    }

  file_token->datasource = datasource;
  file_token->offset = chunk_to_offset(file_baton->chunk[idx])
                       + (curp - file_baton->buffer[idx]);
  file_token->length = 0;

  while (1)
    {
      /* XXX: '\n' doesn't really cut it.  We need to be able to detect
       * XXX: '\n', '\r' and '\r\n'.
       */
      eol = memchr(curp, '\n', endp - curp);
      if (eol)
        {
          eol++;
          break;
        }

      if (file_baton->chunk[idx] == last_chunk)
        {
          eol = endp;
          break;
        }

      length = endp - curp;
      file_token->length += length;
      h = svn_diff__adler32(h, curp, length);

      curp = endp = file_baton->buffer[idx];
      file_baton->chunk[idx]++;
      length = file_baton->chunk[idx] == last_chunk ? 
        offset_in_chunk(file_baton->size[idx]) : CHUNK_SIZE;
      endp += length;
      file_baton->endp[idx] = endp;

      SVN_ERR(read_chunk(file_baton->file[idx], file_baton->path[idx],
                         curp, length, 
                         chunk_to_offset(file_baton->chunk[idx]),
                         file_baton->pool));
    }

  length = eol - curp;
  file_token->length += length;
  *hash = svn_diff__adler32(h, curp, length);

  file_baton->curp[idx] = eol;
  *token = file_token;

  return SVN_NO_ERROR;
}

#define COMPARE_CHUNK_SIZE 4096

static
svn_error_t *
svn_diff__file_token_compare(void *baton,
                             void *token1,
                             void *token2,
                             int *compare)
{
  svn_diff__file_baton_t *file_baton = baton;
  svn_diff__file_token_t *file_token1 = token1;
  svn_diff__file_token_t *file_token2 = token2;
  char buffer[2][COMPARE_CHUNK_SIZE];
  char *bufp[2];
  apr_off_t offset[2];
  int idx[2];
  apr_off_t length[2];
  apr_off_t total_length;
  apr_off_t len;
  int i;
  int chunk[2];

  if (file_token1->length < file_token2->length)
    {
      *compare = -1;
      return SVN_NO_ERROR;
    }

  if (file_token1->length > file_token2->length)
    {
      *compare = 1;
      return SVN_NO_ERROR;
    }

  total_length = file_token1->length;
  if (total_length == 0)
    {
      *compare = 0;
      return SVN_NO_ERROR;
    }

  idx[0] = svn_diff__file_datasource_to_index(file_token1->datasource);
  idx[1] = svn_diff__file_datasource_to_index(file_token2->datasource);
  offset[0] = file_token1->offset;
  offset[1] = file_token2->offset;
  chunk[0] = file_baton->chunk[idx[0]];
  chunk[1] = file_baton->chunk[idx[1]];

  do
    {
      for (i = 0; i < 2; i++)
        {
          if (offset_to_chunk(offset[i]) == chunk[i])
            {
              /* If the start of the token is in memory, the entire token is
               * in memory.
               */
              bufp[i] = file_baton->buffer[idx[i]];
              bufp[i] += offset_in_chunk(offset[i]);

              length[i] = total_length;
            }
          else
            {
              /* Read a chunk from disk into a buffer */
              bufp[i] = buffer[i];
              length[i] = total_length > COMPARE_CHUNK_SIZE ? 
                COMPARE_CHUNK_SIZE : total_length;

              SVN_ERR(read_chunk(file_baton->file[idx[i]],