exclude.cc

   1 /* Cumulus: Efficient Filesystem Backup to the Cloud
   2  * Copyright (C) 2012 The Cumulus Developers
   3  * See the AUTHORS file for a list of contributors.
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along
  16  * with this program; if not, write to the Free Software Foundation, Inc.,
  17  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18  */
  19
  20 /* Implementation of Cumulus include/exclude rules for selecting files to be
  21  * backed up. */
  22
  23 #include <regex.h>
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <sys/types.h>
  27 #include <iostream>
  28 #include <sstream>
  29 #include <string>
  30
  31 #include "exclude.h"
  32
  33 using std::make_pair;
  34 using std::pair;
  35 using std::string;
  36
  37 FilePattern::FilePattern(const string& pattern, const string& basedir)
  38     : refcount(1), orig_pattern(pattern), valid(false)
  39 {
  40     string pattern_as_regex = pattern_to_regex(pattern, basedir);
  41     int status = regcomp(&regex, pattern_as_regex.c_str(),
  42                          REG_EXTENDED|REG_NOSUB);
  43     if (status != 0) {
  44         char errbuf[256];
  45         regerror(status, &regex, errbuf, sizeof(errbuf));
  46         fprintf(stderr,
  47                 "Pattern %s: failed to compile as regular expression %s: %s\n",
  48                 pattern.c_str(), pattern_as_regex.c_str(), errbuf);
  49         regfree(&regex);
  50     } else {
  51         valid = true;
  52     }
  53 }
  54
  55 FilePattern::~FilePattern()
  56 {
  57     if (valid)
  58         regfree(&regex);
  59 }
  60
  61 bool FilePattern::matches(const std::string& path) const
  62 {
  63     if (!valid)
  64         return false;
  65     else
  66         return regexec(&regex, path.c_str(), 0, NULL, 0) == 0;
  67 }
  68
  69 string FilePattern::pattern_to_regex(const string& pattern,
  70                                      const string& basedir)
  71 {
  72     /* Matches are always anchored to cover the entire string; we insert
  73      * wildcards where needed if we only need to match a suffix of the path. */
  74     string result = "^";
  75     size_t i = 0;
  76     size_t len = pattern.size();
  77     if (len == 0) {
  78         /* Special case: an empty pattern matches all files. */
  79         return result;
  80     }
  81
  82     /* For a non-empty basedir, the match must ensure that the file actually
  83      * falls within basedir. */
  84     if (!basedir.empty() && basedir != ".") {
  85         result += regex_quote(basedir) + "/";
  86     }
  87
  88     /* A leading slash indicates a pattern that must match the entire path.  If
  89      * there is no leading slash, match any number of leading directory
  90      * components. */
  91     if (pattern[0] == '/') {
  92         i++;
  93     } else {
  94         result += "(|.*/)";
  95     }
  96
  97     while (i < len) {
  98         switch (pattern[i]) {
  99         /* Characters that must be quoted in a regular expression that are not
 100          * otherwise part of the Cumulus pattern language. */
 101         case '^':
 102         case '.':
 103         case '[':
 104         case ']':
 105         case '$':
 106         case '(':
 107         case ')':
 108         case '|':
 109         case '+':
 110         case '{':
 111         case '}':
 112         case '\\':
 113             result += '\\';
 114             result += pattern[i];
 115             break;
 116
 117         case '?':
 118             /* Any character except a directory separator. */
 119             result += "[^/]";
 120             break;
 121
 122         case '*':
 123             if (i + 1 < len && pattern[i + 1] == '*') {
 124                 /* Any number of characters, including slashes. */
 125                 i++;
 126                 result += ".*";
 127             } else {
 128                 /* Zero or more characters (but no directory separators). */
 129                 result += "[^/]*";
 130             }
 131             break;
 132
 133         default:
 134             /* A character matched literally that does not require quoting. */
 135             result += pattern[i];
 136             break;
 137         }
 138         i++;
 139     }
 140
 141     /* A trailing slash should match only a directory.  No trailing slash means
 142      * match any type of file.  Callers should include a slash at the end of a
 143      * path that is a directory; if there is no trailing slash in the pattern
 144      * match either a trailing slash or none. */
 145     if (pattern[len - 1] != '/') {
 146         result += "/?";
 147     }
 148
 149     result += "$";
 150
 151     return result;
 152 }
 153
 154 string FilePattern::regex_quote(const string& pattern)
 155 {
 156     string result = "";
 157     for (size_t i = 0; i < pattern.length(); i++) {
 158         switch (pattern[i]) {
 159         /* Characters that must be quoted in a regular expression. */
 160         case '^':
 161         case '.':
 162         case '[':
 163         case ']':
 164         case '$':
 165         case '(':
 166         case ')':
 167         case '|':
 168         case '*':
 169         case '+':
 170         case '?':
 171         case '{':
 172         case '}':
 173         case '\\':
 174             result += '\\';
 175             // fall through
 176
 177         default:
 178             result += pattern[i];
 179         }
 180     }
 181
 182     return result;
 183 }
 184
 185 PathFilterList::PathFilterList()
 186 {
 187     /* Invariant: pattern_stack is always non-empty (except when the destructor
 188      * runs).  Thus, reading pattern_stack.front() is always safe. */
 189     pattern_stack.push_back(make_pair(1, new PatternList));
 190 }
 191
 192 PathFilterList::~PathFilterList()
 193 {
 194     /* Pops all items off the saved rule stack.  As an optimization, rather
 195      * than repeatedly popping items which have a repeat count, just set the
 196      * repeat count to one. */
 197     while (!pattern_stack.empty()) {
 198         pattern_stack.front().first = 1;
 199         restore();
 200     }
 201 }
 202
 203 /* save() operates lazily: simply increment the repeat count on the rule set at
 204  * the head of the list.  If modifications are made, mutable_patterns() will
 205  * create a copy of the rules. */
 206 void PathFilterList::save()
 207 {
 208     pattern_stack.front().first++;
 209 }
 210
 211 void PathFilterList::restore()
 212 {
 213     if (--pattern_stack.front().first == 0) {
 214         PatternList *old_patterns = pattern_stack.front().second;
 215         pattern_stack.pop_front();
 216         for (PatternList::iterator i = old_patterns->begin();
 217              i != old_patterns->end(); ++i) {
 218             i->second->unref();
 219         }
 220         delete old_patterns;
 221     }
 222 }
 223
 224 void PathFilterList::add_pattern(PatternType type, const string& pattern,
 225                                  const string& basedir)
 226 {
 227     FilePattern *pat = new FilePattern(pattern, basedir);
 228     mutable_patterns()->push_back(make_pair(type, pat));
 229 }
 230
 231 bool PathFilterList::is_included(const std::string& path,
 232                                  bool is_directory) const
 233 {
 234     string full_path;
 235     if (is_directory) {
 236         full_path = path + "/";
 237     } else {
 238         full_path = path;
 239     }
 240
 241     PatternList::const_iterator i;
 242     for (i = patterns().begin(); i != patterns().end(); ++i) {
 243         if (i->second->matches(full_path)) {
 244             switch (i->first) {
 245             case INCLUDE:
 246                 return true;
 247             case EXCLUDE:
 248                 return false;
 249             case DIRMERGE:
 250                 /* Merge rules are ignored for the purposes of selecting
 251                  * whether a file is included or not. */
 252                 continue;
 253             }
 254         }
 255     }
 256
 257     /* Default is include if no rule matches. */
 258     return true;
 259 }
 260
 261 bool PathFilterList::is_mergefile(const std::string& path) const
 262 {
 263     PatternList::const_iterator i;
 264     for (i = patterns().begin(); i != patterns().end(); ++i) {
 265         if (i->first == DIRMERGE && i->second->matches(path))
 266             return true;
 267     }
 268     return false;
 269 }
 270
 271 /* Parses the specified contents of a per-directory rule merge file.  The rules
 272  * are first parsed into a temporary PatternList, which is then spliced into
 273  * the rule set just before the DIRMERGE rule.  Thus, if a dir-merge rule
 274  * matches multiple times (in successive sub-directories), deeper rules take
 275  * precedence over earlier rules. */
 276 void PathFilterList::merge_patterns(const string& path,
 277                                     const string& basedir,
 278                                     const string& contents)
 279 {
 280     PatternList *rules = mutable_patterns();
 281     PatternList::iterator i;
 282     for (PatternList::iterator i = rules->begin(); i != rules->end(); ++i) {
 283         /* Try to locate where the rules should be inserted by looking for the
 284          * DIRMERGE rule which matches the path to the rule file. */
 285         if (i->first == DIRMERGE && i->second->matches(path)) {
 286             PatternList *new_rules = parse_rules(basedir, contents);
 287             rules->splice(i, *new_rules);
 288             delete new_rules;
 289             break;
 290         }
 291     }
 292 }
 293
 294 PathFilterList::PatternList *PathFilterList::parse_rules(const string& basedir,
 295                                                          const string& data)
 296 {
 297     PatternList *patterns = new PatternList;
 298     std::stringstream rules(data, std::stringstream::in);
 299     while (!rules.eof()) {
 300         string rule;
 301         std::getline(rules, rule);
 302         /* Ignore blank lines and lines starting with "#". */
 303         if (rule.empty() || rule[0] == '#')
 304             continue;
 305         if (rule.length() > 2 && rule[1] == ' ') {
 306             if (rule[0] == '+' || rule[0] == '-' || rule[0] == ':') {
 307                 FilePattern *pat = new FilePattern(rule.substr(2), basedir);
 308                 switch (rule[0]) {
 309                 case '+':
 310                     patterns->push_back(make_pair(INCLUDE, pat));
 311                     break;
 312                 case '-':
 313                     patterns->push_back(make_pair(EXCLUDE, pat));
 314                     break;
 315                 case ':':
 316                     patterns->push_back(make_pair(DIRMERGE, pat));
 317                     break;
 318                 default:
 319                     break;
 320                 }
 321                 continue;
 322             }
 323             fprintf(stderr, "Invalid rule: %s\n", rule.c_str());
 324         }
 325     }
 326     return patterns;
 327 }
 328
 329 PathFilterList::PatternList *PathFilterList::mutable_patterns()
 330 {
 331     PatternList *old_list = pattern_stack.front().second;
 332     if (pattern_stack.front().first == 1)
 333         return old_list;
 334
 335     PatternList *new_list = new PatternList;
 336     for (PatternList::iterator i = old_list->begin();
 337          i != old_list->end(); ++i) {
 338         i->second->ref();
 339         new_list->push_back(*i);
 340     }
 341     pattern_stack.front().first--;
 342     pattern_stack.push_front(make_pair(1, new_list));
 343     return new_list;
 344 }
 345
 346
 347 /*****************************************************************************
 348  * Unit tests for pattern matching.  These are not compiled in by default, but
 349  * exclude.cc can be compiled to a standalone binary with -DRUN_TESTS to run
 350  * the unit tests.
 351  *****************************************************************************/
 352
 353 #ifdef RUN_TESTS
 354 /* Tests of pattern matching rules.  test_pattern takes a pattern, a base
 355  * directory, and a path to match, and prints out whether the rule matches.
 356  * expect_match is the expected result; if this doesn't equal the actual result
 357  * print a warning message. */
 358 static void test_pattern(const string& pattern, const string& basedir,
 359                          const string& path, bool expect_match)
 360 {
 361     FilePattern pat(pattern, basedir);
 362     bool result = pat.matches(path);
 363     printf("%3s %c %c %-30s %-30s\n",
 364            result == expect_match ? "" : "ERR",
 365            result ? '+' : '-',
 366            expect_match ? '+' : '-',
 367            pattern.c_str(),
 368            path.c_str());
 369 }
 370
 371 int main(int argc, char *argv[])
 372 {
 373     printf("Act/Exp Pattern                        Path\n");
 374     test_pattern("*.o", "", "a/b/c.txt", false);
 375     test_pattern("*.o", "", "a/b/c.o", true);
 376     test_pattern("*.git/", "", "repo/project.git/", true);
 377     test_pattern("/.cache", "", ".cache", true);
 378     test_pattern("/.cache", "", "home/user/.cache", false);
 379     test_pattern("/*/.cache", "", "home/user/.cache", false);
 380     test_pattern("/*/*/.cache", "", "home/user/.cache", true);
 381     test_pattern("/**/.cache", "", "home/user/.cache", true);
 382     test_pattern(".cache", "", "home/user/.cache", true);
 383     test_pattern("?.o", "", "home/user/a.o", true);
 384     test_pattern("?.o", "", "home/user/a/o", false);
 385     test_pattern("*.o", "", "a/b/\n.o", true);
 386     test_pattern("/**/.cache", "", "home/new\nline/.cache", true);
 387     test_pattern("/*/.cache", "home", "home/user/.cache", true);
 388     test_pattern(".cache", "home", "home/user/.cache", true);
 389     test_pattern("user/.cache", "home", "home/user/.cache", true);
 390     test_pattern("user/.cache", "home/user", "home/user/.cache", false);
 391
 392     PathFilterList pfl;
 393     pfl.add_pattern(PathFilterList::DIRMERGE, ".cumulus-filter", "");
 394     pfl.save();
 395     pfl.merge_patterns("dir/.cumulus-filter", "dir",
 396                        "# comment\n"
 397                        "\n"
 398                        "- *.o\n"
 399                        "+ /.git/\n"
 400                        "* invalid\n");
 401     pfl.restore();
 402     return 0;
 403 }
 404 #endif