diff3.c

linux subdivision ying gai ke yi le ba

/*
 * diff3.c :  routines for doing diffs
 *
 * ====================================================================
 * 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 "svn_pools.h"
#include "svn_error.h"
#include "svn_diff.h"
#include "svn_types.h"

#include "diff.h"


void
svn_diff__resolve_conflict(svn_diff_t *hunk,
                           svn_diff__position_t **position_list1,
                           svn_diff__position_t **position_list2,
                           apr_pool_t *pool)
{
    apr_off_t modified_start = hunk->modified_start + 1;
    apr_off_t latest_start = hunk->latest_start + 1;
    apr_off_t common_length;
    apr_off_t modified_length = hunk->modified_length;
    apr_off_t latest_length = hunk->latest_length;
    svn_diff__position_t *start_position[2];
    svn_diff__position_t *position[2];
    svn_diff__lcs_t *lcs = NULL;
    svn_diff__lcs_t **lcs_ref = &lcs;
    svn_diff_t **diff_ref = &hunk->resolved_diff;
    apr_pool_t *subpool;

    /* First find the starting positions for the
     * comparison
     */

    start_position[0] = *position_list1;
    start_position[1] = *position_list2;

    while (start_position[0]->offset < modified_start)
      start_position[0] = start_position[0]->next;

    while (start_position[1]->offset < latest_start)
      start_position[1] = start_position[1]->next;

    position[0] = start_position[0];
    position[1] = start_position[1];

    common_length = modified_length < latest_length
                  ? modified_length : latest_length;

    while (common_length > 0
           && position[0]->node == position[1]->node)
      {
        position[0] = position[0]->next;
        position[1] = position[1]->next;

        common_length--;
      }

    if (common_length == 0
        && modified_length == latest_length)
      {
        hunk->type = svn_diff__type_diff_common;
        hunk->resolved_diff = NULL;

        *position_list1 = position[0];
        *position_list2 = position[1];

        return;
      }

    hunk->type = svn_diff__type_conflict;

    /* ### If we have a conflict we can try to find the
     * ### common parts in it by getting an lcs between
     * ### modified (start to start + length) and
     * ### latest (start to start + length).
     * ### We use this lcs to create a simple diff.  Only
     * ### where there is a diff between the two, we have
     * ### a conflict.
     * ### This raises a problem; several common diffs and
     * ### conflicts can occur within the same original
     * ### block.  This needs some thought.
     * ###
     * ### NB: We can use the node _pointers_ to identify
     * ###     different tokens
     */

    subpool = svn_pool_create(pool);

    /* Calculate how much of the two sequences was
     * actually the same.
     */
    common_length = (modified_length < latest_length
                    ? modified_length : latest_length)
                  - common_length;

    /* If there were matching symbols at the start of
     * both sequences, record that fact.
     */
    if (common_length > 0)
      {
        lcs = apr_palloc(subpool, sizeof(*lcs));
        lcs->next = NULL;
        lcs->position[0] = start_position[0];
        lcs->position[1] = start_position[1];
        lcs->length = common_length;

        lcs_ref = &lcs->next;
      }

    modified_length -= common_length;
    latest_length -= common_length;

    modified_start = start_position[0]->offset;
    latest_start = start_position[1]->offset;

    start_position[0] = position[0];
    start_position[1] = position[1];

    /* Create a new ring for svn_diff__lcs to grok.
     * We can safely do this given we don't need the
     * positions we processed anymore.
     */
    if (modified_length == 0)
      {
        *position_list1 = position[0];
        position[0] = NULL;
      }
    else
      {
        while (--modified_length)
          position[0] = position[0]->next;

        *position_list1 = position[0]->next;
        position[0]->next = start_position[0];
      }

    if (latest_length == 0)
      {
        *position_list2 = position[1];
        position[1] = NULL;
      }
    else
      {
        while (--latest_length)
          position[1] = position[1]->next;

        *position_list2 = position[1]->next;
        position[1]->next = start_position[1];
      }

    *lcs_ref = svn_diff__lcs(position[0], position[1],
                             subpool);

    /* Fix up the EOF lcs element in case one of
     * the two sequences was NULL.
     */
    if ((*lcs_ref)->position[0]->offset == 1)
      (*lcs_ref)->position[0] = *position_list1;

    if ((*lcs_ref)->position[1]->offset == 1)
      (*lcs_ref)->position[1] = *position_list2;

    /* Restore modified_length and latest_length */
    modified_length = hunk->modified_length;
    latest_length = hunk->latest_length;

    /* Produce the resolved diff */
    while (1)
      {
        if (modified_start < lcs->position[0]->offset
            || latest_start < lcs->position[1]->offset)
          {
            (*diff_ref) = apr_palloc(pool, sizeof(**diff_ref));

            (*diff_ref)->type = svn_diff__type_conflict;
            (*diff_ref)->original_start = hunk->original_start;
            (*diff_ref)->original_length = hunk->original_length;
            (*diff_ref)->modified_start = modified_start - 1;
            (*diff_ref)->modified_length = lcs->position[0]->offset
                                           - modified_start;
            (*diff_ref)->latest_start = latest_start - 1;
            (*diff_ref)->latest_length = lcs->position[1]->offset
                                         - latest_start;
            (*diff_ref)->resolved_diff = NULL;

            diff_ref = &(*diff_ref)->next;
          }

        /* Detect the EOF */
        if (lcs->length == 0)
          break;

        modified_start = lcs->position[0]->offset;
        latest_start = lcs->position[1]->offset;

        (*diff_ref) = apr_palloc(pool, sizeof(**diff_ref));

        (*diff_ref)->type = svn_diff__type_diff_common;
        (*diff_ref)->original_start = hunk->original_start;
        (*diff_ref)->original_length = hunk->original_length;
        (*diff_ref)->modified_start = modified_start - 1;
        (*diff_ref)->modified_length = lcs->length;
        (*diff_ref)->latest_start = latest_start - 1;
        (*diff_ref)->latest_length = lcs->length;
        (*diff_ref)->resolved_diff = NULL;

        diff_ref = &(*diff_ref)->next;

        modified_start += lcs->length;
        latest_start += lcs->length;

        lcs = lcs->next;
      }

    *diff_ref = NULL;

    svn_pool_destroy(subpool);
}


svn_error_t *
svn_diff_diff3(svn_diff_t **diff,
               void *diff_baton,
               const svn_diff_fns_t *vtable,
               apr_pool_t *pool)
{
  svn_diff__tree_t *tree;
  svn_diff__position_t *position_list[3];
  svn_diff__lcs_t *lcs_om;
  svn_diff__lcs_t *lcs_ol;