1/*
2 * target.c:  functions which operate on a list of targets supplied to
3 *              a subversion subcommand.
4 *
5 * ====================================================================
6 *    Licensed to the Apache Software Foundation (ASF) under one
7 *    or more contributor license agreements.  See the NOTICE file
8 *    distributed with this work for additional information
9 *    regarding copyright ownership.  The ASF licenses this file
10 *    to you under the Apache License, Version 2.0 (the
11 *    "License"); you may not use this file except in compliance
12 *    with the License.  You may obtain a copy of the License at
13 *
14 *      http://www.apache.org/licenses/LICENSE-2.0
15 *
16 *    Unless required by applicable law or agreed to in writing,
17 *    software distributed under the License is distributed on an
18 *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
19 *    KIND, either express or implied.  See the License for the
20 *    specific language governing permissions and limitations
21 *    under the License.
22 * ====================================================================
23 */
24
25/* ==================================================================== */
26
27
28
29/*** Includes. ***/
30
31#include "svn_pools.h"
32#include "svn_error.h"
33#include "svn_dirent_uri.h"
34#include "svn_path.h"
35
36
37/*** Code. ***/
38
39svn_error_t *
40svn_path_condense_targets(const char **pcommon,
41                          apr_array_header_t **pcondensed_targets,
42                          const apr_array_header_t *targets,
43                          svn_boolean_t remove_redundancies,
44                          apr_pool_t *pool)
45{
46  int i, j, num_condensed = targets->nelts;
47  svn_boolean_t *removed;
48  apr_array_header_t *abs_targets;
49  size_t basedir_len;
50  const char *first_target;
51  svn_boolean_t first_target_is_url;
52
53  /* Early exit when there's no data to work on. */
54  if (targets->nelts <= 0)
55    {
56      *pcommon = NULL;
57      if (pcondensed_targets)
58        *pcondensed_targets = NULL;
59      return SVN_NO_ERROR;
60    }
61
62  /* Get the absolute path of the first target. */
63  first_target = APR_ARRAY_IDX(targets, 0, const char *);
64  first_target_is_url = svn_path_is_url(first_target);
65  if (first_target_is_url)
66    {
67      first_target = apr_pstrdup(pool, first_target);
68      *pcommon = first_target;
69    }
70  else
71    SVN_ERR(svn_dirent_get_absolute(pcommon, first_target, pool));
72
73  /* Early exit when there's only one path to work on. */
74  if (targets->nelts == 1)
75    {
76      if (pcondensed_targets)
77        *pcondensed_targets = apr_array_make(pool, 0, sizeof(const char *));
78      return SVN_NO_ERROR;
79    }
80
81  /* Copy the targets array, but with absolute paths instead of
82     relative.  Also, find the pcommon argument by finding what is
83     common in all of the absolute paths. NOTE: This is not as
84     efficient as it could be.  The calculation of the basedir could
85     be done in the loop below, which would save some calls to
86     svn_path_get_longest_ancestor.  I decided to do it this way
87     because I thought it would be simpler, since this way, we don't
88     even do the loop if we don't need to condense the targets. */
89
90  removed = apr_pcalloc(pool, (targets->nelts * sizeof(svn_boolean_t)));
91  abs_targets = apr_array_make(pool, targets->nelts, sizeof(const char *));
92
93  APR_ARRAY_PUSH(abs_targets, const char *) = *pcommon;
94
95  for (i = 1; i < targets->nelts; ++i)
96    {
97      const char *rel = APR_ARRAY_IDX(targets, i, const char *);
98      const char *absolute;
99      svn_boolean_t is_url = svn_path_is_url(rel);
100
101      if (is_url)
102        absolute = apr_pstrdup(pool, rel); /* ### TODO: avoid pool dup? */
103      else
104        SVN_ERR(svn_dirent_get_absolute(&absolute, rel, pool));
105
106      APR_ARRAY_PUSH(abs_targets, const char *) = absolute;
107
108      /* If we've not already determined that there's no common
109         parent, then continue trying to do so. */
110      if (*pcommon && **pcommon)
111        {
112          /* If the is-url-ness of this target doesn't match that of
113             the first target, our search for a common ancestor can
114             end right here.  Otherwise, use the appropriate
115             get-longest-ancestor function per the path type. */
116          if (is_url != first_target_is_url)
117            *pcommon = "";
118          else if (first_target_is_url)
119            *pcommon = svn_uri_get_longest_ancestor(*pcommon, absolute, pool);
120          else
121            *pcommon = svn_dirent_get_longest_ancestor(*pcommon, absolute,
122                                                       pool);
123        }
124    }
125
126  if (pcondensed_targets != NULL)
127    {
128      if (remove_redundancies)
129        {
130          /* Find the common part of each pair of targets.  If
131             common part is equal to one of the paths, the other
132             is a child of it, and can be removed.  If a target is
133             equal to *pcommon, it can also be removed. */
134
135          /* First pass: when one non-removed target is a child of
136             another non-removed target, remove the child. */
137          for (i = 0; i < abs_targets->nelts; ++i)
138            {
139              if (removed[i])
140                continue;
141
142              for (j = i + 1; j < abs_targets->nelts; ++j)
143                {
144                  const char *abs_targets_i;
145                  const char *abs_targets_j;
146                  svn_boolean_t i_is_url, j_is_url;
147                  const char *ancestor;
148
149                  if (removed[j])
150                    continue;
151
152                  abs_targets_i = APR_ARRAY_IDX(abs_targets, i, const char *);
153                  abs_targets_j = APR_ARRAY_IDX(abs_targets, j, const char *);
154                  i_is_url = svn_path_is_url(abs_targets_i);
155                  j_is_url = svn_path_is_url(abs_targets_j);
156
157                  if (i_is_url != j_is_url)
158                    continue;
159
160                  if (i_is_url)
161                    ancestor = svn_uri_get_longest_ancestor(abs_targets_i,
162                                                            abs_targets_j,
163                                                            pool);
164                  else
165                    ancestor = svn_dirent_get_longest_ancestor(abs_targets_i,
166                                                               abs_targets_j,
167                                                               pool);
168
169                  if (*ancestor == '\0')
170                    continue;
171
172                  if (strcmp(ancestor, abs_targets_i) == 0)
173                    {
174                      removed[j] = TRUE;
175                      num_condensed--;
176                    }
177                  else if (strcmp(ancestor, abs_targets_j) == 0)
178                    {
179                      removed[i] = TRUE;
180                      num_condensed--;
181                    }
182                }
183            }
184
185          /* Second pass: when a target is the same as *pcommon,
186             remove the target. */
187          for (i = 0; i < abs_targets->nelts; ++i)
188            {
189              const char *abs_targets_i = APR_ARRAY_IDX(abs_targets, i,
190                                                        const char *);
191
192              if ((strcmp(abs_targets_i, *pcommon) == 0) && (! removed[i]))
193                {
194                  removed[i] = TRUE;
195                  num_condensed--;
196                }
197            }
198        }
199
200      /* Now create the return array, and copy the non-removed items */
201      basedir_len = strlen(*pcommon);
202      *pcondensed_targets = apr_array_make(pool, num_condensed,
203                                           sizeof(const char *));
204
205      for (i = 0; i < abs_targets->nelts; ++i)
206        {
207          const char *rel_item = APR_ARRAY_IDX(abs_targets, i, const char *);
208
209          /* Skip this if it's been removed. */
210          if (removed[i])
211            continue;
212
213          /* If a common prefix was found, condensed_targets are given
214             relative to that prefix.  */
215          if (basedir_len > 0)
216            {
217              /* Only advance our pointer past a path separator if
218                 REL_ITEM isn't the same as *PCOMMON.
219
220                 If *PCOMMON is a root path, basedir_len will already
221                 include the closing '/', so never advance the pointer
222                 here.
223                 */
224              rel_item += basedir_len;
225              if (rel_item[0] &&
226                  ! svn_dirent_is_root(*pcommon, basedir_len))
227                rel_item++;
228            }
229
230          APR_ARRAY_PUSH(*pcondensed_targets, const char *)
231            = apr_pstrdup(pool, rel_item);
232        }
233    }
234
235  return SVN_NO_ERROR;
236}
237
238
239svn_error_t *
240svn_path_remove_redundancies(apr_array_header_t **pcondensed_targets,
241                             const apr_array_header_t *targets,
242                             apr_pool_t *pool)
243{
244  apr_pool_t *temp_pool;
245  apr_array_header_t *abs_targets;
246  apr_array_header_t *rel_targets;
247  int i;
248
249  if ((targets->nelts <= 0) || (! pcondensed_targets))
250    {
251      /* No targets or no place to store our work means this function
252         really has nothing to do. */
253      if (pcondensed_targets)
254        *pcondensed_targets = NULL;
255      return SVN_NO_ERROR;
256    }
257
258  /* Initialize our temporary pool. */
259  temp_pool = svn_pool_create(pool);
260
261  /* Create our list of absolute paths for our "keepers" */
262  abs_targets = apr_array_make(temp_pool, targets->nelts,
263                               sizeof(const char *));
264
265  /* Create our list of untainted paths for our "keepers" */
266  rel_targets = apr_array_make(pool, targets->nelts,
267                               sizeof(const char *));
268
269  /* For each target in our list we do the following:
270
271     1.  Calculate its absolute path (ABS_PATH).
272     2.  See if any of the keepers in ABS_TARGETS is a parent of, or
273         is the same path as, ABS_PATH.  If so, we ignore this
274         target.  If not, however, add this target's absolute path to
275         ABS_TARGETS and its original path to REL_TARGETS.
276  */
277  for (i = 0; i < targets->nelts; i++)
278    {
279      const char *rel_path = APR_ARRAY_IDX(targets, i, const char *);
280      const char *abs_path;
281      int j;
282      svn_boolean_t is_url, keep_me;
283
284      /* Get the absolute path for this target. */
285      is_url = svn_path_is_url(rel_path);
286      if (is_url)
287        abs_path = rel_path;
288      else
289        SVN_ERR(svn_dirent_get_absolute(&abs_path, rel_path, temp_pool));
290
291      /* For each keeper in ABS_TARGETS, see if this target is the
292         same as or a child of that keeper. */
293      keep_me = TRUE;
294      for (j = 0; j < abs_targets->nelts; j++)
295        {
296          const char *keeper = APR_ARRAY_IDX(abs_targets, j, const char *);
297          svn_boolean_t keeper_is_url = svn_path_is_url(keeper);
298          const char *child_relpath;
299
300          /* If KEEPER hasn't the same is-url-ness as ABS_PATH, we
301             know they aren't equal and that one isn't the child of
302             the other. */
303          if (is_url != keeper_is_url)
304            continue;
305
306          /* Quit here if this path is the same as or a child of one of the
307             keepers. */
308          if (is_url)
309            child_relpath = svn_uri_skip_ancestor(keeper, abs_path, temp_pool);
310          else
311            child_relpath = svn_dirent_skip_ancestor(keeper, abs_path);
312          if (child_relpath)
313            {
314              keep_me = FALSE;
315              break;
316            }
317        }
318
319      /* If this is a new keeper, add its absolute path to ABS_TARGETS
320         and its original path to REL_TARGETS. */
321      if (keep_me)
322        {
323          APR_ARRAY_PUSH(abs_targets, const char *) = abs_path;
324          APR_ARRAY_PUSH(rel_targets, const char *) = rel_path;
325        }
326    }
327
328  /* Destroy our temporary pool. */
329  svn_pool_destroy(temp_pool);
330
331  /* Make sure we return the list of untainted keeper paths. */
332  *pcondensed_targets = rel_targets;
333
334  return SVN_NO_ERROR;
335}
336