1 /* plan.c - Checking renames and resolving rename order.
2 *
3 * Copyright (C) 2001, 2002, 2004, 2005, 2007, 2008 Oskar Liljeblad
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU Library General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18 */
19
20 #include <config.h>
21 #include <stdlib.h> /* C89 */
22 #include <string.h> /* gnulib (C89) */
23 #include <stdbool.h> /* gnulib (POSIX) */
24 #include <gettext.h> /* gnulib (gettext) */
25 #define _(s) gettext(s)
26 #define N_(s) (s)
27 #include "xalloc.h" /* gnulib */
28 #include "xvasprintf.h" /* gnulib */
29 #include "common/io-utils.h"
30 #include "common/string-utils.h"
31 #include "common/common.h"
32 #include "common/error.h"
33 #include "common/llist.h"
34 #include "common/hmap.h"
35 #include "qcmd.h"
36
37 /* Find renames that have the same destination filename.
38 * Mark these as STATUS_DUPLICATE.
39 */
40 static void
duplicate_scan(LList * renames,ApplyPlan * plan)41 duplicate_scan(LList *renames, ApplyPlan *plan)
42 {
43 HMap *map = hmap_new();
44 LListIterator it;
45
46 for (llist_iterator(renames, &it); it.has_next(&it); ) {
47 FileSpec *spec = it.next(&it);
48
49 if (spec->status == STATUS_UNCHECKED) {
50 FileSpec *spec2;
51
52 spec2 = hmap_put(map, spec->new_name, spec);
53 if (spec2 != NULL) {
54 if (spec2->status == STATUS_UNCHECKED) {
55 spec2->status = STATUS_DUPLICATE;
56 llist_add(plan->error, spec2);
57 }
58 spec->status = STATUS_DUPLICATE;
59 llist_add(plan->error, spec);
60 }
61 }
62 }
63
64 hmap_free(map);
65 }
66
67 /* Sort renames topologically, so that their destination name
68 * won't exist when they are to be renamed.
69 */
70 static void
topologic_sort(LList * renames,ApplyPlan * plan)71 topologic_sort(LList *renames, ApplyPlan *plan)
72 {
73 LList *pending = llist_new();
74 HMap *available = hmap_new();
75 LListIterator it;
76 bool changed;
77
78 /* Find all renames where destination file does not exist. */
79 for (llist_iterator(renames, &it); it.has_next(&it); ) {
80 FileSpec *spec = it.next(&it);
81 if (spec->status == STATUS_UNCHECKED) {
82 char *fullname = cat_files(work_directory, spec->new_name);
83 if (!file_exists(fullname)) {
84 hmap_put(available, spec->old_name, spec);
85 spec->status = STATUS_APPLY;
86 llist_add(plan->ok, spec);
87 } else {
88 llist_add(pending, spec);
89 }
90 free(fullname);
91 }
92 }
93
94 /* Topologic sorting */
95 do {
96 changed = false;
97 for (llist_iterator(pending, &it); it.has_next(&it); ) {
98 FileSpec *spec = it.next(&it);
99 FileSpec *depend = hmap_get(available, spec->new_name);
100 if (depend != NULL) {
101 it.remove(&it);
102 spec->prev_spec = depend;
103 depend->next_spec = spec;
104 hmap_put(available, spec->old_name, spec);
105 hmap_remove(available, spec->new_name);
106 spec->status = STATUS_APPLY;
107 llist_add(plan->ok, spec);
108 changed = true;
109 }
110 }
111 } while (changed);
112
113 llist_free(pending);
114 hmap_free(available);
115 }
116
117 /* Find all renames where the old file is missing.
118 * There is no guarantee that the old file will go
119 * missing later (say, a microsecond after we
120 * did the file_exists check), but it is probably
121 * of some guidance to the user.
122 *
123 * XXX: Technically, there are other checks similar
124 * to this one. For example, maybe the new file
125 * is on a different filesystem? Or the new file
126 * is a subdirectory of the old file (assuming the
127 * old file is a directory)?
128 */
129 static void
old_missing_scan(LList * renames,ApplyPlan * plan)130 old_missing_scan(LList *renames, ApplyPlan *plan)
131 {
132 LListIterator it;
133
134 for (llist_iterator(renames, &it); it.has_next(&it); ) {
135 FileSpec *spec = it.next(&it);
136 if (spec->status == STATUS_UNCHECKED) {
137 char *fullname = cat_files(work_directory, spec->old_name);
138 if (!file_exists(fullname)) {
139 spec->status = STATUS_OLD_MISSING;
140 llist_add(plan->error, spec);
141 }
142 free(fullname);
143 }
144 }
145 }
146
147 /* For each spec, if destination is found among sources
148 * then that spec is an error.
149 * This is only useful in qcp mode.
150 */
151 static void
new_exists_scan(LList * renames,ApplyPlan * plan)152 new_exists_scan(LList *renames, ApplyPlan *plan)
153 {
154 HMap *map;
155 LListIterator it;
156
157 map = hmap_new();
158
159 for (llist_iterator(renames, &it); it.has_next(&it); ) {
160 FileSpec *spec = it.next(&it);
161 if (spec->status == STATUS_UNCHECKED)
162 hmap_put(map, spec->old_name, spec);
163 }
164
165 for (llist_iterator(renames, &it); it.has_next(&it); ) {
166 FileSpec *spec = it.next(&it);
167 if (spec->status == STATUS_UNCHECKED) {
168 FileSpec *s2;
169 s2 = hmap_get(map, spec->new_name);
170 if (s2 != NULL) {
171 spec->status = STATUS_NEW_EXISTS;
172 llist_add(plan->error, spec);
173 }
174 }
175 }
176
177 for (llist_iterator(renames, &it); it.has_next(&it); ) {
178 FileSpec *spec = it.next(&it);
179 if (spec->status == STATUS_UNCHECKED) {
180 char *fullname = cat_files(work_directory, spec->new_name);
181 if (file_exists(fullname)) {
182 spec->status = STATUS_NEW_EXISTS;
183 llist_add(plan->error, spec);
184 }
185 free(fullname);
186 }
187 }
188
189 hmap_free(map);
190 }
191
192 /* Remaining pending files are either cross-referenced
193 * (e.g. x->y, y->x), or can't be renamed because the
194 * destination file exists.
195 */
196 static void
cross_reference_resolve(LList * renames,ApplyPlan * plan)197 cross_reference_resolve(LList *renames, ApplyPlan *plan)
198 {
199 HMap *map_old = hmap_new();
200 HMap *map_new = hmap_new();
201 LListIterator it;
202
203 /* Put old names for all remaining files into the table. */
204 for (llist_iterator(renames, &it); it.has_next(&it); ) {
205 FileSpec *spec = it.next(&it);
206 if (spec->status == STATUS_UNCHECKED) {
207 hmap_put(map_old, spec->old_name, spec);
208 hmap_put(map_new, spec->new_name, spec);
209 } else if (spec->status == STATUS_APPLY) {
210 hmap_put(map_new, spec->new_name, spec);
211 }
212 }
213
214 /* Follow the renamings from new to old. */
215 for (llist_iterator(renames, &it); it.has_next(&it); ) {
216 FileSpec *s1 = it.next(&it);
217 FileSpec *s2 = s1;
218 FileSpec *prev_circular = s1;
219 LListIterator it2;
220 int tmp_count = 1;
221 char *tmp_name;
222 char *fullname = NULL;
223
224 /* Rename has already been processed. Ignore it. */
225 if (s1->status != STATUS_UNCHECKED)
226 continue;
227
228 /* Follow the renamings from new to old, until we reach the rename
229 * we started from, or a dead end (i.e. destination exists). We can
230 * be sure this is not going to loop forever, because no two
231 * renames can have the same destination name. */
232 for (;;) {
233 s2 = hmap_get(map_old, s2->new_name);
234
235 /* Destination file already exists. */
236 if (s2 == NULL || s2->status != STATUS_UNCHECKED) {
237 s1->next_spec = NULL;
238 break;
239 }
240 /* We have found a circular rename-set. */
241 if (s2 == s1) {
242 prev_circular->next_spec = NULL;
243 break;
244 }
245 prev_circular->next_spec = s2;
246 prev_circular = s2;
247 }
248
249 /* This was not a cross-reference. The destination already
250 * existed. */
251 if (s1->next_spec == NULL) {
252 s1->status = STATUS_NEW_EXISTS;
253 llist_add(plan->error, s1);
254 continue;
255 }
256
257 /* Find a temporary name for the new rename */
258 do {
259 if (fullname != NULL)
260 free(fullname);
261 tmp_name = xasprintf("%s-%d", s1->old_name, tmp_count++);
262 fullname = cat_files(work_directory, tmp_name);
263 } while (file_exists(fullname) || hmap_contains_key(map_new, tmp_name));
264 free(fullname);
265
266 /* Add and update status of selected files (reverse order). */
267 s2 = new_file_spec();
268 /*llist_add(plan->free_spec, s2);*/
269 llist_add_first(plan->ok, s2);
270 s2->status = STATUS_CIRCULAR;
271 s2->old_name = xstrdup(s1->old_name);
272 s2->new_name = xstrdup(s1->new_name);
273 s2->next_spec = s1->next_spec;
274 s2->prev_spec = s1->prev_spec;
275 s1->status = STATUS_APPLY;
276 s1->next_spec = NULL;
277 s1->prev_spec = NULL;
278 s1 = s2;
279
280 for (s2 = s1->next_spec; s2 != NULL; s2 = s2->next_spec) {
281 s2->status = STATUS_CIRCULAR;
282 llist_add_first(plan->ok, s2);
283 }
284
285 /* Add the extra required rename. */
286 s2 = new_file_spec();
287 /*llist_add(plan->free_spec, s2);*/
288 llist_add_first(plan->ok, s2);
289 s2->status = STATUS_CIRCULAR;
290 s2->old_name = s1->old_name;
291 s2->new_name = xstrdup(tmp_name);
292 s1->old_name = xstrdup(tmp_name);
293
294 /* Update the next_spec field of these circular renames */
295 llist_iterator(plan->ok, &it2);
296 it2.next(&it2); /* skip first - that's s2 */
297 while (it.has_next(&it2)) {
298 FileSpec *spec = it.next(&it2);
299 s2->next_spec = spec;
300 spec->prev_spec = s2;
301 if (spec == s1)
302 break;
303 s2 = spec;
304 }
305 s1->next_spec = NULL;
306 }
307
308 hmap_free(map_new);
309 hmap_free(map_old);
310 }
311
312 /* Find all renames that have no changes.
313 */
314 static void
no_change_scan(LList * renames,ApplyPlan * plan)315 no_change_scan(LList *renames, ApplyPlan *plan)
316 {
317 LListIterator it;
318
319 for (llist_iterator(renames, &it); it.has_next(&it); ) {
320 FileSpec *spec = it.next(&it);
321 if (spec->status == STATUS_UNCHECKED) {
322 if (strcmp(spec->old_name, spec->new_name) == 0) {
323 spec->status = STATUS_NO_CHANGE;
324 llist_add(plan->no_change, spec);
325 }
326 }
327 }
328 }
329
330 /* Mark all with status UNCHECKED as APPLY, and
331 * add them to ok list in plan. This is the last thing
332 * done. Some may already be in the ok list.
333 */
334 static void
apply_unchecked(LList * renames,ApplyPlan * plan)335 apply_unchecked(LList *renames, ApplyPlan *plan)
336 {
337 LListIterator it;
338
339 for (llist_iterator(renames, &it); it.has_next(&it); ) {
340 FileSpec *spec = it.next(&it);
341 if (spec->status == STATUS_UNCHECKED) {
342 spec->status = STATUS_APPLY;
343 llist_add(plan->ok, spec);
344 }
345 }
346 }
347
348 static void
previous_scan(LList * renames,ApplyPlan * plan)349 previous_scan(LList *renames, ApplyPlan *plan)
350 {
351 LListIterator it;
352
353 for (llist_iterator(renames, &it); it.has_next(&it); ) {
354 FileSpec *spec = it.next(&it);
355 if (spec->status == STATUS_APPLY || spec->status == STATUS_CIRCULAR)
356 llist_add(plan->ok, spec);
357 else if (spec->status == STATUS_NO_CHANGE)
358 llist_add(plan->no_change, spec);
359 else if (spec->status != STATUS_UNCHECKED)
360 llist_add(plan->error, spec);
361
362 }
363 }
364
365 ApplyPlan *
make_plan(LList * renames)366 make_plan(LList *renames)
367 {
368 ApplyPlan *plan;
369
370 plan = xmalloc(sizeof(ApplyPlan));
371 plan->ok = llist_new();
372 plan->error = llist_new();
373 plan->no_change = llist_new();
374 /*plan->free_spec = llist_new();*/
375
376 previous_scan(renames, plan);
377 duplicate_scan(renames, plan);
378 old_missing_scan(renames, plan);
379 no_change_scan(renames, plan);
380 if (strcmp(program, "qmv") == 0) {
381 topologic_sort(renames, plan);
382 cross_reference_resolve(renames, plan);
383 } else if (strcmp(program, "qcp") == 0) {
384 new_exists_scan(renames, plan);
385 }
386 apply_unchecked(renames, plan);
387
388 return plan;
389 }
390
391 void
free_plan(ApplyPlan * plan)392 free_plan(ApplyPlan *plan)
393 {
394 llist_free(plan->ok);
395 llist_free(plan->error);
396 llist_free(plan->no_change);
397 /*llist_iterate(plan->free_spec, free_file_spec);
398 llist_free(plan->free_spec);*/
399 free(plan);
400 }
401