Import trimmed svn-1.8.0-rc3

1 files changed, 529 insertions, 0 deletions

diff --git a/subversion/libsvn_diff/diff3.c b/subversion/libsvn_diff/diff3.c
new file mode 100644
index 0000000..8b7c9b3
--- /dev/null
+++ b/subversion/libsvn_diff/diff3.c
@@ -0,0 +1,529 @@
+/*
+ * 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_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 = modified_length < latest_length
+                        ? modified_length : latest_length;
+
+        (*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;
+}