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