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