added kdenlive
[feisty_meow.git] / nucleus / library / filesystem / directory_tree.cpp
1 /*****************************************************************************\
2 *                                                                             *
3 *  Name   : directory_tree                                                    *
4 *  Author : Chris Koeritz                                                     *
5 *                                                                             *
6 *******************************************************************************
7 * Copyright (c) 2004-$now By Author.  This program is free software; you can  *
8 * redistribute it and/or modify it under the terms of the GNU General Public  *
9 * License as published by the Free Software Foundation; either version 2 of   *
10 * the License or (at your option) any later version.  This is online at:      *
11 *     http://www.fsf.org/copyleft/gpl.html                                    *
12 * Please send any updates to: fred@gruntose.com                               *
13 \*****************************************************************************/
14
15 #include "directory.h"
16 #include "directory_tree.h"
17 #include "filename.h"
18 #include "filename_list.h"
19 #include "filename_tree.h"
20
21 #include <basis/functions.h>
22 #include <basis/contracts.h>
23 #include <loggers/program_wide_logger.h>
24 #include <structures/object_packers.h>
25 #include <structures/string_array.h>
26 #include <textual/parser_bits.h>
27 #include <textual/string_manipulation.h>
28
29 #include <stdio.h>
30
31 using namespace basis;
32 using namespace loggers;
33 using namespace nodes;
34 using namespace structures;
35 using namespace textual;
36
37 //#define DEBUG_DIRECTORY_TREE
38   // uncomment for noisier version.
39
40 #undef LOG
41 #define LOG(to_print) CLASS_EMERGENCY_LOG(program_wide_logger::get(), to_print)
42
43 //////////////
44
45 namespace filesystem {
46
47 class dir_tree_iterator : public filename_tree::iterator
48 {
49 public:
50   filename_tree *_current;
51
52   dir_tree_iterator(const filename_tree *initial,
53       tree::traversal_directions dir)
54   : filename_tree::iterator(initial, dir), _current(NULL_POINTER) {}
55 };
56
57 //////////////
58
59 directory_tree::directory_tree()
60 : _scanned_okay(false),
61   _path(new astring),
62   _pattern(new astring),
63   _real_tree(new filename_tree),
64   _ignore_files(false),
65   _creator(new fname_tree_creator)
66 {
67 }
68
69 directory_tree::directory_tree(const astring &path, const char *pattern,
70     bool ignore_files)
71 : _scanned_okay(false),
72   _path(new astring(path)),
73   _pattern(new astring(pattern)),
74   _real_tree(NULL_POINTER),
75   _ignore_files(ignore_files),
76   _creator(new fname_tree_creator)
77 {
78   reset(path, pattern);
79 }
80
81 directory_tree::~directory_tree()
82 {
83   _scanned_okay = false;
84   WHACK(_path);
85   WHACK(_pattern);
86   WHACK(_real_tree);
87   WHACK(_creator);
88 }
89
90 const astring &directory_tree::path() const { return *_path; }
91
92 int directory_tree::packed_size() const
93 {
94   return 2 * PACKED_SIZE_INT32
95       + _path->packed_size()
96       + _pattern->packed_size()
97       + _real_tree->recursive_packed_size();
98 }
99
100 void directory_tree::pack(byte_array &packed_form) const
101 {
102   attach(packed_form, int(_scanned_okay));
103   attach(packed_form, int(_ignore_files));
104   _path->pack(packed_form);
105   _pattern->pack(packed_form);
106   _real_tree->recursive_pack(packed_form);
107 }
108
109 bool directory_tree::unpack(byte_array &packed_form)
110 {
111   int temp;
112   if (!detach(packed_form, temp)) return false;
113   _scanned_okay = temp;
114   if (!detach(packed_form, temp)) return false;
115   _ignore_files = temp;
116   if (!_path->unpack(packed_form)) return false;
117   if (!_pattern->unpack(packed_form)) return false;
118   WHACK(_real_tree);
119   _real_tree = (filename_tree *)packable_tree::recursive_unpack
120       (packed_form, *_creator);
121   if (!_real_tree) {
122     _real_tree = new filename_tree;  // reset it.
123     return false;
124   }
125   return true;
126 }
127
128 void directory_tree::text_form(astring &target, bool show_files)
129 {
130   dir_tree_iterator *ted = start(directory_tree::prefix);
131     // create our iterator to do a prefix traversal.
132
133   int depth;  // current depth in tree.
134   filename curr;  // the current path the iterator is at.
135   string_array files;  // the filenames held at the iterator.
136
137   while (current(*ted, curr, files)) {
138     // we have a good directory to show.
139     directory_tree::depth(*ted, depth);
140     target += string_manipulation::indentation(depth * 2) + astring("[")
141         + curr.raw() + "]" + parser_bits::platform_eol_to_chars();
142     if (show_files) {
143       astring names;
144       for (int i = 0; i < files.length(); i++) names += files[i] + " ";
145       if (names.length()) {
146         astring split;
147         string_manipulation::split_lines(names, split, depth * 2 + 2);
148         target += split + parser_bits::platform_eol_to_chars();
149       }
150     }
151
152     // go to the next place.
153     next(*ted);
154   }
155
156   throw_out(ted);
157 }
158
159 void directory_tree::traverse(const astring &path, const char *pattern,
160     filename_tree &add_to)
161 {
162   FUNCDEF("traverse");
163   // prepare the current node.
164   add_to._dirname = filename(path, astring::empty_string());
165   add_to._files.reset();
166 #ifdef DEBUG_DIRECTORY_TREE
167   LOG(astring("working on node ") + add_to._dirname);
168 #endif
169
170   // open the directory.
171   directory curr(path, "*");
172   if (!curr.good()) return;
173
174   if (!_ignore_files) {
175     // add all the files to the current node.
176     directory curr_stringent(path, pattern);
177     add_to._files = curr_stringent.files();
178   }
179
180   // now iterate across the directories here and add a sub-node for each one,
181   // and recursively traverse that sub-node also.
182   const string_array &dirs = curr.directories();
183   for (int i = 0; i < dirs.length(); i++) {
184     filename_tree *new_branch = NULL_POINTER;
185     astring new_path = path + filename::default_separator() + dirs[i];
186 #ifdef DEBUG_DIRECTORY_TREE
187     LOG(astring("seeking path: ") + new_path);
188 #endif
189     if (!filename(new_path).is_normal()) {
190 //#ifdef DEBUG_DIRECTORY_TREE
191       LOG(astring("bailing on weird dir: ") + new_path);
192 //#endif
193       continue;  // only regular directories please.
194     }
195     for (int q = 0; q < add_to.branches(); q++) {
196       filename_tree *curr_kid = (filename_tree *)add_to.branch(q);
197 #ifdef DEBUG_DIRECTORY_TREE
198       LOG(astring("curr kid: ") + curr_kid->_dirname);
199 #endif
200       if (filename(new_path).raw().iequals(filename
201           (curr_kid->_dirname).raw())) {
202         new_branch = curr_kid;
203 #ifdef DEBUG_DIRECTORY_TREE
204         LOG(astring("using existing branch for ") + new_path);
205 #endif
206         break;
207       }
208     }
209     if (!new_branch) {
210 #ifdef DEBUG_DIRECTORY_TREE
211       LOG(astring("adding new branch for ") + new_path);
212 #endif
213       new_branch = new filename_tree;
214       add_to.attach(new_branch);
215       new_branch->_depth = add_to._depth + 1;
216     }
217 #ifdef DEBUG_DIRECTORY_TREE
218     LOG(astring("traversing sub-node ") + new_path);
219 #endif
220     traverse(new_path, pattern, *new_branch);
221   }
222 }
223
224 bool directory_tree::reset(const astring &path, const char *pattern)
225 {
226   FUNCDEF("reset");
227   _scanned_okay = false;
228   WHACK(_real_tree);
229 //  filename temp_path(path);
230 //  temp_path.canonicalize();
231   *_path = path;
232 //temp_path.raw();
233   *_pattern = pattern;
234   _real_tree = new filename_tree;
235
236 #ifdef DEBUG_DIRECTORY_TREE
237   LOG(astring("dirtree::reset to path: ") + path);
238 #endif
239
240   // check that the top-level is healthy.
241   directory curr(path, "*");
242   if (!curr.good()) return false;
243     // our only exit condition; other directories might not be accessible
244     // underneath, but the top one must be accessible for us to even start
245     // the scanning.
246
247   traverse(path, pattern, *_real_tree);
248   _scanned_okay = true;;
249   return true;
250 }
251
252 dir_tree_iterator *directory_tree::start_at(filename_tree *start,
253     traversal_types type) const
254 {
255   // translate to the lower level traversal enum.
256   tree::traversal_directions dir = tree::prefix;
257   if (type == infix) dir = tree::infix;
258   else if (type == postfix) dir = tree::postfix;
259
260   return new dir_tree_iterator(start, dir);
261 }
262
263 dir_tree_iterator *directory_tree::start(traversal_types type) const
264 {
265   // translate to the lower level traversal enum.
266   tree::traversal_directions dir = tree::prefix;
267   if (type == infix) dir = tree::infix;
268   else if (type == postfix) dir = tree::postfix;
269
270   return new dir_tree_iterator(_real_tree, dir);
271 }
272
273 bool directory_tree::jump_to(dir_tree_iterator &scanning,
274     const astring &sub_path)
275 {
276   FUNCDEF("jump_to");
277   string_array pieces;
278   bool rooted;
279   filename(sub_path).separate(rooted, pieces);
280   for (int i = 0; i < pieces.length(); i++) {
281     filename_tree *curr = dynamic_cast<filename_tree *>(scanning.current());
282 #ifdef DEBUG_DIRECTORY_TREE
283     LOG(astring("at ") + curr->_dirname.raw());
284 #endif
285     string_array sub_pieces = pieces.subarray(i, i);
286     filename curr_path;
287     curr_path.join(rooted, sub_pieces);
288     curr_path = filename(curr->_dirname.raw() + filename::default_separator()
289         + curr_path.raw());
290 #ifdef DEBUG_DIRECTORY_TREE
291     LOG(astring("made curr path ") + curr_path.raw());
292 #endif
293     if (!curr) return false;
294     bool found_it = false;
295     for (int j = 0; j < curr->branches(); j++) {
296       filename_tree *sub = dynamic_cast<filename_tree *>(curr->branch(j));
297 #ifdef DEBUG_DIRECTORY_TREE
298       LOG(astring("looking at ") + sub->_dirname.raw());
299 #endif
300       if (sub->_dirname.compare_prefix(curr_path)) {
301         // this part matches!
302         scanning.push(sub);
303 #ifdef DEBUG_DIRECTORY_TREE
304         LOG(astring("found at ") + sub->_dirname.raw());
305 #endif
306         found_it = true;
307         break;
308       }
309     }
310     if (!found_it) {
311 #ifdef DEBUG_DIRECTORY_TREE
312       LOG(astring("could not find ") + curr_path.raw());
313 #endif
314       return false;
315     }
316   }
317   return true;
318 }
319
320 filename_tree *directory_tree::goto_current(dir_tree_iterator &scanning)
321 {
322   if (!scanning._current) {
323     // this one hasn't been advanced yet, or it's already over with.
324     scanning._current = (filename_tree *)scanning.next();
325   }
326   // now check that we're healthy.
327   if (!scanning._current) return NULL_POINTER;  // all done.
328
329   // cast the tree to the right type.
330   return dynamic_cast<filename_tree *>(scanning._current);
331 }
332
333 bool directory_tree::current_dir(dir_tree_iterator &scanning,
334     filename &dir_name)
335 {
336   dir_name = astring::empty_string();
337   filename_tree *tof = goto_current(scanning);
338   if (!tof) return false;
339   dir_name = tof->_dirname;
340   return true;
341 }
342
343 bool directory_tree::current(dir_tree_iterator &scanning,
344     filename &dir_name, string_array &to_fill)
345 {
346   // clear any existing junk.
347   dir_name = astring::empty_string();
348   to_fill.reset();
349
350   filename_tree *tof = goto_current(scanning);
351   if (!tof) return false;
352
353   // fill in what they wanted.
354   dir_name = tof->_dirname;
355   tof->_files.fill(to_fill);
356
357   return true;
358 }
359
360 bool directory_tree::current(dir_tree_iterator &scanning,
361     filename &dir_name, filename_list &to_fill)
362 {
363   // clear any existing junk.
364   dir_name = astring::empty_string();
365   to_fill.reset();
366
367   filename_tree *tof = goto_current(scanning);
368   if (!tof) return false;
369
370   // fill in what they wanted.
371   dir_name = tof->_dirname;
372   to_fill = tof->_files;
373
374   return true;
375 }
376
377 filename_list *directory_tree::access(dir_tree_iterator &scanning)
378 {
379   filename_tree *tof = goto_current(scanning);
380   if (!tof) return NULL_POINTER;
381   return &tof->_files;
382 }
383
384 bool directory_tree::depth(dir_tree_iterator &scanning, int &depth)
385 {
386   depth = -1;  // invalid as default.
387   filename_tree *tof = goto_current(scanning);
388   if (!tof) return false;
389   depth = tof->_depth;
390   return true;
391 }
392
393 bool directory_tree::children(dir_tree_iterator &scanning, int &kids)
394 {
395   kids = -1;  // invalid as default.
396   filename_tree *tof = goto_current(scanning);
397   if (!tof) return false;
398   kids = tof->branches();
399   return true;
400 }
401
402 bool directory_tree::next(dir_tree_iterator &scanning)
403 {
404   scanning._current = (filename_tree *)scanning.next();
405   return !!scanning._current;
406 }
407
408 void directory_tree::throw_out(dir_tree_iterator * &to_whack)
409 {
410   WHACK(to_whack);
411 }
412
413 filename_tree *directory_tree::seek(const astring &dir_name_in,
414     bool ignore_initial) const
415 {
416   FUNCDEF("seek");
417   array<filename_tree *> examining;
418     // the list of nodes we're currently looking at.
419
420 #ifdef DEBUG_DIRECTORY_TREE
421   LOG(astring("seeking on root of: ") + *_path);
422 #endif
423
424   astring dir_name = filename(dir_name_in).raw();
425   // set the search path up to have the proper prefix.
426   if (ignore_initial)
427     dir_name = path() + filename::default_separator()
428        + filename(dir_name_in).raw();
429
430 #ifdef DEBUG_DIRECTORY_TREE
431   LOG(astring("adding root: ") + _real_tree->_dirname);
432 #endif
433   examining += _real_tree;
434
435   astring sequel;  // holds extra pieces from filename comparisons.
436
437   // chew on the list of nodes to examine until we run out.
438   while (examining.length()) {
439     int posn;
440     bool found = false;
441     // start looking at all the items in the list, even though we might have
442     // to abandon the iteration if we find a match.
443     filename_tree *check = NULL_POINTER;
444     for (posn = 0; posn < examining.length(); posn++) {
445       check = examining[posn];
446       filename current(check->_dirname);
447       if (!current.is_normal()) {
448 //#ifdef DEBUG_DIRECTORY_TREE
449         LOG(astring("seek: skipping abnormal dir: \"") + current + "\"");
450 //#endif
451         continue;
452       }
453 #ifdef DEBUG_DIRECTORY_TREE
454       LOG(astring("looking at ") + current.raw());
455 #endif
456       if (current.compare_prefix(dir_name, sequel)) {
457         // we have a match!
458 #ifdef DEBUG_DIRECTORY_TREE
459         LOG(astring("matched! at ") + current.raw());
460 #endif
461         found = true;
462         if (!sequel) {
463           // whoa!  an exact match.  we're done now.
464 #ifdef DEBUG_DIRECTORY_TREE
465           LOG(astring("exact match at ") + current.raw() + "!  done!!!");
466 #endif
467           return check;
468         } else {
469 #ifdef DEBUG_DIRECTORY_TREE
470           LOG(astring("inexact match because sequel=") + sequel);
471 #endif
472         }
473         break;
474       }
475     }
476     if (!found) return NULL_POINTER;  // we found nothing comparable.
477
478     // we found a partial match.  that means we should start looking at this
479     // node's children for the exact match.
480     if (!check) {
481       // this is a serious logical error!
482       LOG("serious logical error: tree was not located.");
483       return NULL_POINTER;
484     }
485     examining.reset();  // clear the existing nodes.
486     for (int i = 0; i < check->branches(); i++)
487       examining += (filename_tree *)check->branch(i);
488   }
489
490   return NULL_POINTER;  // we found nothing that looked like that node.
491 }
492
493 bool directory_tree::calculate(bool just_size)
494 { return calculate(_real_tree, just_size); }
495
496 bool directory_tree::calculate(filename_tree *start, bool just_size)
497 {
498   FUNCDEF("calculate");
499 #ifdef DEBUG_DIRECTORY_TREE
500   LOG(astring("calculate: got tree to start with at ") + start->_dirname.raw());
501 #endif
502   dir_tree_iterator *ted = start_at(start, directory_tree::postfix);
503     // create our iterator to do a postfix traversal.  why postfix?  well,
504     // prefix has been used elsewhere and since it doesn't really matter what
505     // order we visit the nodes here, it's good to change up.
506
507   int depth;  // current depth in tree.
508   filename curr;  // the current path the iterator is at.
509   filename_list *files;  // the filenames held at the iterator.
510
511   while (directory_tree::current_dir(*ted, curr)) {
512     if (!curr.is_normal()) {
513 //#ifdef DEBUG_DIRECTORY_TREE
514       LOG(astring("calculate: skipping abnormal dir: \"") + curr + "\"");
515 //#endif
516       directory_tree::next(*ted);
517       continue;  // scary non-simple file type.
518     }
519     // we have a good directory to show.
520 #ifdef DEBUG_DIRECTORY_TREE
521     LOG(astring("calcing node ") + curr.raw());
522 #endif
523     files = directory_tree::access(*ted);
524     directory_tree::depth(*ted, depth);
525     for (int i = 0; i < files->elements(); i++) {
526       filename curr_file = curr + "/" + *files->borrow(i);
527 #ifdef DEBUG_DIRECTORY_TREE
528       LOG(astring("got a curr file: ") + curr_file);
529 #endif
530       if (!curr_file.is_normal()) {
531 //#ifdef DEBUG_DIRECTORY_TREE
532         LOG(astring("skipping abnormal file: \"") + curr + "\"");
533 //#endif
534         continue;
535       }
536       if (!files->borrow(i)->calculate(curr.raw(), just_size)) {
537         LOG(astring("failure to calculate ") + files->get(i)->text_form());
538       }
539     }
540
541     directory_tree::next(*ted);
542   }
543
544   directory_tree::throw_out(ted);
545   return true;
546 }
547
548 bool directory_tree::compare_trees(const directory_tree &source,
549     const directory_tree &target, filename_list &differences,
550     file_info::file_similarity how_to_compare)
551 {
552   return compare_trees(source, astring::empty_string(), target,
553       astring::empty_string(), differences, how_to_compare);
554 }
555
556 bool directory_tree::compare_trees(const directory_tree &source,
557     const astring &source_start_in, const directory_tree &target,
558     const astring &target_start_in, filename_list &differences,
559     file_info::file_similarity how_compare)
560 {
561   FUNCDEF("compare_trees");
562   differences.reset();  // prepare it for storage.
563
564   // make sure we get canonical names to work with.
565   filename source_start(source_start_in);
566   filename target_start(target_start_in);
567
568   dir_tree_iterator *ted = source.start(directory_tree::prefix);
569     // create our iterator to do a prefix traversal.
570
571   astring real_source_start = source.path();
572   if (source_start.raw().t()) {
573     // move to the right place.
574     real_source_start = real_source_start + filename::default_separator()
575         + source_start.raw();
576     if (!directory_tree::jump_to(*ted, source_start.raw())) {
577       // can't even start comparing.
578       LOG(astring("failed to find source start in tree, given as ")
579           + source_start.raw());
580       return false;
581     }
582   }
583
584   filename curr;  // the current path the iterator is at.
585   filename_list files;  // the filenames held at the iterator.
586
587   // calculate where our comparison point is on the source.
588   int source_pieces = 0;
589   {
590     string_array temp;
591     bool rooted_source;
592     filename(real_source_start).separate(rooted_source, temp);
593     source_pieces = temp.length();
594   }
595
596   bool seen_zero_pieces = false;
597   while (directory_tree::current(*ted, curr, files)) {
598     // we're in a place in the source tree now.  let's compare it with the
599     // target's recollection.
600
601 #ifdef DEBUG_DIRECTORY_TREE
602     LOG(astring("curr dir in tree: ") + curr.raw());
603 #endif
604
605     string_array pieces;
606     bool curr_rooted;
607     curr.separate(curr_rooted, pieces);  // get the components of the current location.
608 #ifdef DEBUG_DIRECTORY_TREE
609     LOG(astring("name in pieces:") + pieces.text_form());
610 #endif
611     pieces.zap(0, source_pieces - 1);
612       // snap the root components out of there.
613
614     filename corresponding_name;
615 //hmmm: is that right decision?
616     corresponding_name.join(false, pieces);
617 #ifdef DEBUG_DIRECTORY_TREE
618     LOG(astring("computed target name as: ") + corresponding_name);
619 #endif
620     filename original_correspondence(corresponding_name);
621
622     if (!corresponding_name.raw().t()) {
623       if (seen_zero_pieces) {
624 #ifdef DEBUG_DIRECTORY_TREE
625         LOG(astring("breaking out now due to empty correspondence"));
626 #endif
627         break;
628       }
629       seen_zero_pieces = true;
630     }
631     if (target_start.raw().t()) {
632       corresponding_name = filename(target_start.raw()
633           + filename::default_separator() + corresponding_name.raw());
634 /*doesn't help, not right yet.    } else {
635       // if they didn't give us a place to start, we start at the top.
636       corresponding_name = filename(target.path()
637           + filename::default_separator() + corresponding_name.raw());
638 */
639     }
640 #ifdef DEBUG_DIRECTORY_TREE
641     LOG(astring("target with start is: ") + corresponding_name);
642 #endif
643
644     filename_tree *target_now = target.seek(corresponding_name.raw(), true);
645     if (!target_now) {
646       // that entire sub-tree is missing.  add all of the files here into
647       // the list.
648 //#ifdef DEBUG_DIRECTORY_TREE
649       LOG(astring("could not find dir in target for ") + curr.raw()
650           + " which we computed corresp as " + corresponding_name.raw());
651 //#endif
652     }
653
654     // now scan across all the files that are in our source list.
655     for (int i = 0; i < files.elements(); i++) {
656       if (!target_now  // there was no node, so we're adding everything...
657           || !target_now->_files.member_with_state(*files[i], how_compare) ) {
658         // ... or we need to add this file since it's missing.
659 #ifdef DEBUG_DIRECTORY_TREE
660         LOG(astring("adding record: ") + files[i]->text_form());
661 #endif
662
663         file_info *new_record = new file_info(*files[i]);
664         // record the file time for use later in saving.
665         new_record->calculate(curr, true);
666         astring original = new_record->raw();
667 #ifdef DEBUG_DIRECTORY_TREE
668         LOG(astring("current: ") + new_record->raw());
669 #endif
670
671         astring actual_name = source_start.raw();
672 #ifdef DEBUG_DIRECTORY_TREE
673         if (actual_name.t()) LOG(astring("sname=") + actual_name);
674 #endif
675         if (actual_name.length()) actual_name += filename::default_separator();
676         actual_name += original_correspondence.raw();
677         if (actual_name.length()) actual_name += filename::default_separator();
678         actual_name += new_record->raw();
679 #ifdef DEBUG_DIRECTORY_TREE
680         if (actual_name.t()) LOG(astring("sname=") + actual_name);
681 #endif
682         (filename &)(*new_record) = filename(actual_name);
683
684         astring targ_name = corresponding_name.raw();
685 #ifdef DEBUG_DIRECTORY_TREE
686         if (targ_name.t()) LOG(astring("tname=") + targ_name);
687 #endif
688         if (targ_name.length()) targ_name += filename::default_separator();
689         targ_name += original;
690 #ifdef DEBUG_DIRECTORY_TREE
691         if (targ_name.t()) LOG(astring("tname=") + targ_name);
692 #endif
693
694         new_record->secondary(targ_name);
695
696         differences += new_record;
697 #ifdef DEBUG_DIRECTORY_TREE
698         LOG(astring("came out as: ") + new_record->text_form());
699 #endif
700       }
701     }
702     
703     // go to the next place.
704     directory_tree::next(*ted);
705   }
706
707   directory_tree::throw_out(ted);
708
709   return true;
710 }
711
712 outcome directory_tree::find_common_root(const astring &finding, bool exists,
713     filename_tree * &found, astring &reassembled, string_array &pieces,
714     int &match_place)
715 {
716   FUNCDEF("find_common_root");
717   // test the path to find what it is.
718   filename adding(finding);
719   if (exists && !adding.good())
720     return common::BAD_INPUT;  // not a good path.
721   int file_subtract = 0;  // if it's a file, then we remove last component.
722   if (exists && !adding.is_directory()) file_subtract = 1;
723
724   // break up the path into pieces.
725   pieces.reset();
726   bool rooted;
727   adding.separate(rooted, pieces);
728
729   // break up our root into pieces; we must take off components that are
730   // already in the root.
731   string_array root_pieces;
732   bool root_rooted;
733   filename temp_file(path());
734   temp_file.separate(root_rooted, root_pieces);
735
736   // locate the last place where the path we were given touches our tree.
737   // it could be totally new, partially new, or already contained.
738   filename_tree *last_match = _real_tree;  // where the common root is located.
739   int list_length = pieces.length() - file_subtract;
740   reassembled = "";
741
742   // we must put all the pieces in that already come from the root.
743   for (int i = 0; i < root_pieces.length() - 1; i++) {
744     bool add_slash = false;
745     if (reassembled.length() && (reassembled[reassembled.end()] != '/') )
746       add_slash = true;
747     if (add_slash) reassembled += "/";
748     reassembled += pieces[i];
749     if (reassembled[reassembled.end()] == ':') {
750 #ifdef DEBUG_DIRECTORY_TREE
751       LOG(astring("skipping drive component ") + reassembled);
752 #endif
753       continue;
754     }
755   }
756
757 #ifdef DEBUG_DIRECTORY_TREE
758   LOG(astring("after pre-assembly, path is ") + reassembled);
759 #endif
760
761   outcome to_return = common::NOT_FOUND;
762
763   for (match_place = root_pieces.length() - 1; match_place < list_length;
764       match_place++) {
765     // add a slash if there's not one present already.
766     bool add_slash = false;
767     if (reassembled.length() && (reassembled[reassembled.end()] != '/') )
768       add_slash = true;
769     // add the next component in to our path.
770     if (add_slash) reassembled += "/";
771     reassembled += pieces[match_place];
772     // special case for dos paths.
773     if (reassembled[reassembled.end()] == ':') {
774 #ifdef DEBUG_DIRECTORY_TREE
775       LOG(astring("skipping drive component ") + reassembled);
776 #endif
777       continue;
778     }
779     reassembled = filename(reassembled).raw();  // force compliance with OS.
780 #ifdef DEBUG_DIRECTORY_TREE
781     LOG(astring("now seeking ") + reassembled);
782 #endif
783     filename_tree *sought = seek(reassembled, false);
784     if (!sought) {
785 #ifdef DEBUG_DIRECTORY_TREE
786       LOG(astring("couldn't find ") + reassembled);
787 #endif
788       if (!exists && (match_place == list_length - 1)) {
789         // see if we can get a match on a file rather than a directory, but
790         // only if we're near the end of the compare.
791         if (last_match->_files.member(pieces[match_place])) {
792           // aha!  a file match.
793           to_return = common::OKAY;
794           match_place--;
795           break;
796         }
797       }
798       match_place--;
799       break;
800     } else {
801       // record where we last had some success.
802 #ifdef DEBUG_DIRECTORY_TREE
803       LOG(astring("found subtree for ") + reassembled);
804 #endif
805       last_match = sought;
806     }
807   }
808   // this is a success, but our loop structure can put us one past the right
809   // place.
810   if (match_place >= list_length) {
811     match_place = list_length - 1;
812     to_return = common::OKAY;
813   }
814
815   found = last_match;
816   return to_return;
817 }
818
819 outcome directory_tree::add_path(const astring &new_item, bool just_size)
820 {
821   FUNCDEF("add_path");
822   // test the path to find out what it is.
823   filename adding(new_item);
824   if (!adding.good()) {
825     LOG(astring("non-existent new item!  ") + new_item);
826     return common::NOT_FOUND;  // not an existing path.
827   }
828   if (!adding.is_normal()) {
829 //#ifdef DEBUG_DIRECTORY_TREE
830     LOG(astring("abnormal new item:  ") + new_item);
831 //#endif
832     return common::BAD_INPUT;  // not a good path.
833   }
834   int file_subtract = 0;  // if it's a file, then we remove last component.
835   if (!adding.is_directory()) file_subtract = 1;
836 #ifdef DEBUG_DIRECTORY_TREE
837   if (file_subtract) { LOG(astring("adding a file ") + new_item); }
838   else { LOG(astring("adding a directory ") + new_item); }
839 #endif
840
841   // find the common root, break up the path into pieces, and tell us where
842   // we matched.
843   string_array pieces;
844   filename_tree *last_match = NULL_POINTER;
845   int comp_index;
846   astring reassembled;  // this will hold the common root.
847   outcome ret = find_common_root(new_item, true, last_match, reassembled,
848       pieces, comp_index);
849   if (!last_match) {
850     LOG(astring("serious error finding common root for ") + new_item
851         + ", got null tree.");
852     return common::FAILURE;  // something serious isn't right.
853   }
854
855   if (!file_subtract) {
856     if (ret != common::OKAY) {
857       // if it's a new directory, we add a new node for traverse to work on.
858 #ifdef DEBUG_DIRECTORY_TREE
859       LOG(astring("now adding node for ") + reassembled);
860 #endif
861       filename_tree *new_branch = new filename_tree;
862       new_branch->_depth = last_match->_depth + 1;
863       last_match->attach(new_branch);
864       last_match = new_branch;
865     } else {
866 #ifdef DEBUG_DIRECTORY_TREE
867       LOG(astring("matched properly.  reassembled set to ") + reassembled);
868 #endif
869     }
870   }
871
872   if (file_subtract) {
873     if (ret != common::OKAY) {
874 #ifdef DEBUG_DIRECTORY_TREE
875       LOG(astring("common gave us posn of: ") + reassembled);
876 #endif
877       // handle the case for files now that we have our proper node.
878       string_array partial_pieces;
879       bool partial_rooted;
880       filename(reassembled).separate(partial_rooted, partial_pieces);
881       int levels_missing = pieces.length() - partial_pieces.length();
882
883       // we loop over all the pieces that were missing in between the last
884       // common root and the file's final location.
885       for (int i = 0; i < levels_missing; i++) {
886 #ifdef DEBUG_DIRECTORY_TREE
887         LOG(astring("adding intermediate directory: ") + reassembled);
888 #endif
889         filename_tree *new_branch = new filename_tree;
890         new_branch->_depth = last_match->_depth + 1;
891         new_branch->_dirname = filename(reassembled).raw();
892         last_match->attach(new_branch);
893         last_match = new_branch;
894         reassembled += astring("/") + pieces[partial_pieces.length() + i];
895         reassembled = filename(reassembled).raw();  // canonicalize.
896       }
897     }
898
899     if (!last_match->_files.find(pieces[pieces.last()])) {
900 #ifdef DEBUG_DIRECTORY_TREE
901       LOG(astring("adding new file ") + pieces[pieces.last()]
902         + " at " + reassembled);
903 #endif
904       file_info *to_add = new file_info(pieces[pieces.last()], 0);
905       to_add->calculate(reassembled, just_size);
906       last_match->_files += to_add;
907     } else {
908 #ifdef DEBUG_DIRECTORY_TREE
909       LOG(astring("not adding existing file ") + pieces[pieces.last()]
910           + " at " + reassembled);
911 #endif
912     }
913   } else {
914     // handle the case for directories.
915 #ifdef DEBUG_DIRECTORY_TREE
916     LOG(astring("doing traverse in ") + last_match->_dirname
917         + " to add " + reassembled);
918 #endif
919     traverse(reassembled, "*", *last_match);
920 //hmmm: maybe provide pattern capability instead of assuming all files.
921     calculate(last_match, just_size);
922   }
923
924   return common::OKAY;
925 }
926
927 outcome directory_tree::remove_path(const astring &zap_item)
928 {
929   FUNCDEF("remove_path");
930   // find the common root, if one exists.  if not, we're not going to do this.
931   string_array pieces;
932   filename_tree *last_match = NULL_POINTER;
933   int comp_index;
934   astring reassembled;
935   outcome ret = find_common_root(zap_item, false, last_match, reassembled,
936       pieces, comp_index);
937   if (!last_match) return common::NOT_FOUND;
938   // if we didn't actually finish iterating to the file, then we're not
939   // whacking anything.
940   if (ret != common::OKAY) {
941 #ifdef DEBUG_DIRECTORY_TREE
942     LOG(astring("got error seeking ") + zap_item + " of "
943         + common::outcome_name(ret));
944 #endif
945     return ret;
946   }
947
948   if (comp_index == pieces.last()) {
949     // if the names match fully, then we're talking about a directory.
950 #ifdef DEBUG_DIRECTORY_TREE
951     LOG(astring("found directory match for ") + zap_item);
952 #endif
953   } else {
954 #ifdef DEBUG_DIRECTORY_TREE
955     LOG(astring("may have found file match for ") + zap_item);
956 #endif
957     filename to_seek(pieces[pieces.last()]);
958     if (!last_match->_files.member(to_seek)) {
959       // this file is not a member, so we must say it's not found.
960 #ifdef DEBUG_DIRECTORY_TREE
961       LOG(astring("couldn't find file match in common root for ") + zap_item);
962 #endif
963       return common::NOT_FOUND;
964     } else {
965       int indy = last_match->_files.locate(to_seek);
966 #ifdef DEBUG_DIRECTORY_TREE
967       LOG(astring("found match to remove for ") + zap_item);
968 #endif
969       last_match->_files.zap(indy, indy);
970       return common::OKAY;  // done!
971     }
972   }
973
974 #ifdef DEBUG_DIRECTORY_TREE
975   LOG(astring("going to whack node at: ") + last_match->_dirname.raw());
976 #endif
977
978   // we're whacking directories, so we need to take out last_match and below.
979   filename_tree *parent = (filename_tree *)last_match->parent();
980   if (!parent || (last_match == _real_tree)) {
981     // this seems to be matching the whole tree.  we disallow that.
982 #ifdef DEBUG_DIRECTORY_TREE
983     LOG("there's a problem whacking this node; it's the root.");
984 #endif
985     return common::BAD_INPUT;
986   }
987 #ifdef DEBUG_DIRECTORY_TREE
988   LOG(astring("pruning tree at ") + last_match->_dirname.raw());
989 #endif
990   parent->prune(last_match);
991   WHACK(last_match);
992
993   return common::OKAY;
994 }
995
996 basis::outcome directory_tree::make_directories(const basis::astring new_root)
997 {
998   FUNCDEF("make_directories");
999   // iterate down the tree, making all the directories requested.
1000   dir_tree_iterator *ted = start(directory_tree::prefix);
1001
1002   int depth;  // current depth in tree.
1003   filename curr;  // the current path the iterator is at.
1004   string_array files;  // the filenames held at the iterator.
1005
1006 #ifdef DEBUG_DIRECTORY_TREE
1007   LOG(astring("new root is ") + new_root);
1008 #endif
1009   filename old_root = path();
1010 #ifdef DEBUG_DIRECTORY_TREE
1011   LOG(astring("old root was ") + old_root.raw());
1012 #endif
1013
1014   while (current(*ted, curr, files)) {
1015     // we have a good directory to show.
1016     directory_tree::depth(*ted, depth);
1017     int found = curr.find(old_root);
1018     if (found < common::OKAY) {
1019       LOG(astring("failed to find prefix of path '") + old_root
1020           + "' in the current directory '" + curr + "'");
1021       return found;
1022     }
1023     curr = curr.substring(found + old_root.length(), curr.end());
1024 //LOG(astring("curr now is: ") + curr);
1025     filename dir_to_make(new_root + "/" + curr);
1026 #ifdef DEBUG_DIRECTORY_TREE
1027     LOG(astring("creating dir: ") + dir_to_make.raw());
1028 #endif
1029     directory::recursive_create(dir_to_make.raw());
1030     next(*ted);
1031   }
1032
1033   throw_out(ted);
1034   return common::OKAY;
1035 }
1036
1037 } //namespace.
1038