subversion/libsvn_diff/diff3.c

/*
 * diff3.c :  routines for doing diffs
 *
 * ====================================================================
 *    Licensed to the Apache Software Foundation (ASF) under one
 *    or more contributor license agreements.  See the NOTICE file
 *    distributed with this work for additional information
 *    regarding copyright ownership.  The ASF licenses this file
 *    to you under the Apache License, Version 2.0 (the
 *    "License"); you may not use this file except in compliance
 *    with the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *    Unless required by applicable law or agreed to in writing,
 *    software distributed under the License is distributed on an
 *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 *    KIND, either express or implied.  See the License for the
 *    specific language governing permissions and limitations
 *    under the License.
 * ====================================================================
 */


#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_sorts.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,
                           svn_diff__token_index_t num_tokens,
                           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__token_index_t *token_counts[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]->token_index == position[1]->token_index)
    {
      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];
    }

  token_counts[0] = svn_diff__get_token_counts(position[0], num_tokens,
                                               subpool);
  token_counts[1] = svn_diff__get_token_counts(position[1], num_tokens,
                                               subpool);

  *lcs_ref = svn_diff__lcs(position[0], position[1], token_counts[0],
                           token_counts[1], num_tokens, 0, 0, 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;

  /* 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_2(svn_diff_t **diff,
                 void *diff_baton,
                 const svn_diff_fns2_t *vtable,
                 apr_pool_t *pool)
{
  svn_diff__tree_t *tree;
  svn_diff__position_t *position_list[3];
  svn_diff__token_index_t num_tokens;
  svn_diff__token_index_t *token_counts[3];
  svn_diff_datasource_e datasource[] = {svn_diff_datasource_original,
                                        svn_diff_datasource_modified,
                                        svn_diff_datasource_latest};
  svn_diff__lcs_t *lcs_om;
  svn_diff__lcs_t *lcs_ol;
  apr_pool_t *subpool;
  apr_pool_t *treepool;
  apr_off_t prefix_lines = 0;
  apr_off_t suffix_lines = 0;

  *diff = NULL;

  subpool = svn_pool_create(pool);
  treepool = svn_pool_create(pool);

  svn_diff__tree_create(&tree, treepool);

  SVN_ERR(vtable->datasources_open(diff_baton, &prefix_lines, &suffix_lines,
                                   datasource, 3));

  SVN_ERR(svn_diff__get_tokens(&position_list[0],
                               tree,
                               diff_baton, vtable,
                               svn_diff_datasource_original,
                               prefix_lines,
                               subpool));

  SVN_ERR(svn_diff__get_tokens(&position_list[1],
                               tree,
                               diff_baton, vtable,
                               svn_diff_datasource_modified,
                               prefix_lines,
                               subpool));

  SVN_ERR(svn_diff__get_tokens(&position_list[2],
                               tree,
                               diff_baton, vtable,
                               svn_diff_datasource_latest,
                               prefix_lines,
                               subpool));

  num_tokens = svn_diff__get_node_count(tree);

  /* Get rid of the tokens, we don't need them to calc the diff */
  if (vtable->token_discard_all != NULL)
    vtable->token_discard_all(diff_baton);

  /* We don't need the nodes in the tree either anymore, nor the tree itself */
  svn_pool_destroy(treepool);

  token_counts[0] = svn_diff__get_token_counts(position_list[0], num_tokens,
                                               subpool);
  token_counts[1] = svn_diff__get_token_counts(position_list[1], num_tokens,
                                               subpool);
  token_counts[2] = svn_diff__get_token_counts(position_list[2], num_tokens,
                                               subpool);

  /* Get the lcs for original-modified and original-latest */
  lcs_om = svn_diff__lcs(position_list[0], position_list[1], token_counts[0],
                         token_counts[1], num_tokens, prefix_lines,
                         suffix_lines, subpool);
  lcs_ol = svn_diff__lcs(position_list[0], position_list[2], token_counts[0],
                         token_counts[2], num_tokens, prefix_lines,
                         suffix_lines, subpool);

  /* Produce a merged diff */
  {
    svn_diff_t **diff_ref = diff;

    apr_off_t original_start = 1;
    apr_off_t modified_start = 1;
    apr_off_t latest_start = 1;
    apr_off_t original_sync;
    apr_off_t modified_sync;
    apr_off_t latest_sync;
    apr_off_t common_length;
    apr_off_t modified_length;
    apr_off_t latest_length;
    svn_boolean_t is_modified;
    svn_boolean_t is_latest;
    svn_diff__position_t sentinel_position[2];

    /* Point the position lists to the start of the list
     * so that common_diff/conflict detection actually is
     * able to work.
     */
    if (position_list[1])
      {
        sentinel_position[0].next = position_list[1]->next;
        sentinel_position[0].offset = position_list[1]->offset + 1;
        position_list[1]->next = &sentinel_position[0];
        position_list[1] = sentinel_position[0].next;
      }
    else
      {
        sentinel_position[0].offset = prefix_lines + 1;
        sentinel_position[0].next = NULL;
        position_list[1] = &sentinel_position[0];
      }

    if (position_list[2])
      {
        sentinel_position[1].next = position_list[2]->next;
        sentinel_position[1].offset = position_list[2]->offset + 1;
        position_list[2]->next = &sentinel_position[1];
        position_list[2] = sentinel_position[1].next;
      }
    else
      {
        sentinel_position[1].offset = prefix_lines + 1;
        sentinel_position[1].next = NULL;
        position_list[2] = &sentinel_position[1];
      }

    while (1)
      {
        /* Find the sync points */
        while (1)
          {
            if (lcs_om->position[0]->offset > lcs_ol->position[0]->offset)
              {
                original_sync = lcs_om->position[0]->offset;

                while (lcs_ol->position[0]->offset + lcs_ol->length
                       < original_sync)
                  lcs_ol = lcs_ol->next;

                /* If the sync point is the EOF, and our current lcs segment
                 * doesn't reach as far as EOF, we need to skip this segment.
                 */
                if (lcs_om->length == 0 && lcs_ol->length > 0
                    && lcs_ol->position[0]->offset + lcs_ol->length
                       == original_sync
                    && lcs_ol->position[1]->offset + lcs_ol->length
                       != lcs_ol->next->position[1]->offset)
                  lcs_ol = lcs_ol->next;

                if (lcs_ol->position[0]->offset <= original_sync)
                    break;
              }
            else
              {
                original_sync = lcs_ol->position[0]->offset;

                while (lcs_om->position[0]->offset + lcs_om->length
                       < original_sync)
                  lcs_om = lcs_om->next;

                /* If the sync point is the EOF, and our current lcs segment
                 * doesn't reach as far as EOF, we need to skip this segment.
                 */
                if (lcs_ol->length == 0 && lcs_om->length > 0
                    && lcs_om->position[0]->offset + lcs_om->length
                       == original_sync
                    && lcs_om->position[1]->offset + lcs_om->length
                       != lcs_om->next->position[1]->offset)
                  lcs_om = lcs_om->next;

                if (lcs_om->position[0]->offset <= original_sync)
                    break;
              }
          }

        modified_sync = lcs_om->position[1]->offset
                      + (original_sync - lcs_om->position[0]->offset);
        latest_sync = lcs_ol->position[1]->offset
                    + (original_sync - lcs_ol->position[0]->offset);

        /* Determine what is modified, if anything */
        is_modified = lcs_om->position[0]->offset - original_start > 0
                      || lcs_om->position[1]->offset - modified_start > 0;

        is_latest = lcs_ol->position[0]->offset - original_start > 0
                    || lcs_ol->position[1]->offset - latest_start > 0;

        if (is_modified || is_latest)
          {
            modified_length = modified_sync - modified_start;
            latest_length = latest_sync - latest_start;

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

            (*diff_ref)->original_start = original_start - 1;
            (*diff_ref)->original_length = original_sync - original_start;
            (*diff_ref)->modified_start = modified_start - 1;
            (*diff_ref)->modified_length = modified_length;
            (*diff_ref)->latest_start = latest_start - 1;
            (*diff_ref)->latest_length = latest_length;
            (*diff_ref)->resolved_diff = NULL;

            if (is_modified && is_latest)
              {
                svn_diff__resolve_conflict(*diff_ref,
                                           &position_list[1],
                                           &position_list[2],
                                           num_tokens,
                                           pool);
              }
            else if (is_modified)
              {
                (*diff_ref)->type = svn_diff__type_diff_modified;
              }
            else
              {
                (*diff_ref)->type = svn_diff__type_diff_latest;
              }

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

        /* Detect EOF */
        if (lcs_om->length == 0 || lcs_ol->length == 0)
            break;

        modified_length = lcs_om->length
                          - (original_sync - lcs_om->position[0]->offset);
        latest_length = lcs_ol->length
                        - (original_sync - lcs_ol->position[0]->offset);
        common_length = MIN(modified_length, latest_length);

        if (common_length > 0)
          {
            (*diff_ref) = apr_palloc(pool, sizeof(**diff_ref));

            (*diff_ref)->type = svn_diff__type_common;
            (*diff_ref)->original_start = original_sync - 1;
            (*diff_ref)->original_length = common_length;
            (*diff_ref)->modified_start = modified_sync - 1;
            (*diff_ref)->modified_length = common_length;
            (*diff_ref)->latest_start = latest_sync - 1;
            (*diff_ref)->latest_length = common_length;
            (*diff_ref)->resolved_diff = NULL;

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

        /* Set the new offsets */
        original_start = original_sync + common_length;
        modified_start = modified_sync + common_length;
        latest_start = latest_sync + common_length;

        /* Make it easier for diff_common/conflict detection
           by recording last lcs start positions
         */
        if (position_list[1]->offset < lcs_om->position[1]->offset)
          position_list[1] = lcs_om->position[1];

        if (position_list[2]->offset < lcs_ol->position[1]->offset)
          position_list[2] = lcs_ol->position[1];

        /* Make sure we are pointing to lcs entries beyond
         * the range we just processed
         */
        while (original_start >= lcs_om->position[0]->offset + lcs_om->length
               && lcs_om->length > 0)
          {
            lcs_om = lcs_om->next;
          }

        while (original_start >= lcs_ol->position[0]->offset + lcs_ol->length
               && lcs_ol->length > 0)
          {
            lcs_ol = lcs_ol->next;
          }
      }

    *diff_ref = NULL;
  }

  svn_pool_destroy(subpool);

  return SVN_NO_ERROR;
}