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