lib/bup/helpers.py

   1 """Helper functions and classes for bup."""
   2
   3 from ctypes import sizeof, c_void_p
   4 from os import environ
   5 import sys, os, pwd, subprocess, errno, socket, select, mmap, stat, re, struct
   6 import hashlib, heapq, operator, time, grp
   7
   8 from bup import _helpers
   9 import bup._helpers as _helpers
  10 import math
  11
  12 # This function should really be in helpers, not in bup.options.  But we
  13 # want options.py to be standalone so people can include it in other projects.
  14 from bup.options import _tty_width
  15 tty_width = _tty_width
  16
  17
  18 def atoi(s):
  19     """Convert the string 's' to an integer. Return 0 if s is not a number."""
  20     try:
  21         return int(s or '0')
  22     except ValueError:
  23         return 0
  24
  25
  26 def atof(s):
  27     """Convert the string 's' to a float. Return 0 if s is not a number."""
  28     try:
  29         return float(s or '0')
  30     except ValueError:
  31         return 0
  32
  33
  34 buglvl = atoi(os.environ.get('BUP_DEBUG', 0))
  35
  36
  37 # If the platform doesn't have fdatasync (OS X), fall back to fsync.
  38 try:
  39     fdatasync = os.fdatasync
  40 except AttributeError:
  41     fdatasync = os.fsync
  42
  43
  44 # Write (blockingly) to sockets that may or may not be in blocking mode.
  45 # We need this because our stderr is sometimes eaten by subprocesses
  46 # (probably ssh) that sometimes make it nonblocking, if only temporarily,
  47 # leading to race conditions.  Ick.  We'll do it the hard way.
  48 def _hard_write(fd, buf):
  49     while buf:
  50         (r,w,x) = select.select([], [fd], [], None)
  51         if not w:
  52             raise IOError('select(fd) returned without being writable')
  53         try:
  54             sz = os.write(fd, buf)
  55         except OSError, e:
  56             if e.errno != errno.EAGAIN:
  57                 raise
  58         assert(sz >= 0)
  59         buf = buf[sz:]
  60
  61
  62 _last_prog = 0
  63 def log(s):
  64     """Print a log message to stderr."""
  65     global _last_prog
  66     sys.stdout.flush()
  67     _hard_write(sys.stderr.fileno(), s)
  68     _last_prog = 0
  69
  70
  71 def debug1(s):
  72     if buglvl >= 1:
  73         log(s)
  74
  75
  76 def debug2(s):
  77     if buglvl >= 2:
  78         log(s)
  79
  80
  81 istty1 = os.isatty(1) or (atoi(os.environ.get('BUP_FORCE_TTY')) & 1)
  82 istty2 = os.isatty(2) or (atoi(os.environ.get('BUP_FORCE_TTY')) & 2)
  83 _last_progress = ''
  84 def progress(s):
  85     """Calls log() if stderr is a TTY.  Does nothing otherwise."""
  86     global _last_progress
  87     if istty2:
  88         log(s)
  89         _last_progress = s
  90
  91
  92 def qprogress(s):
  93     """Calls progress() only if we haven't printed progress in a while.
  94
  95     This avoids overloading the stderr buffer with excess junk.
  96     """
  97     global _last_prog
  98     now = time.time()
  99     if now - _last_prog > 0.1:
 100         progress(s)
 101         _last_prog = now
 102
 103
 104 def reprogress():
 105     """Calls progress() to redisplay the most recent progress message.
 106
 107     Useful after you've printed some other message that wipes out the
 108     progress line.
 109     """
 110     if _last_progress and _last_progress.endswith('\r'):
 111         progress(_last_progress)
 112
 113
 114 def mkdirp(d, mode=None):
 115     """Recursively create directories on path 'd'.
 116
 117     Unlike os.makedirs(), it doesn't raise an exception if the last element of
 118     the path already exists.
 119     """
 120     try:
 121         if mode:
 122             os.makedirs(d, mode)
 123         else:
 124             os.makedirs(d)
 125     except OSError, e:
 126         if e.errno == errno.EEXIST:
 127             pass
 128         else:
 129             raise
 130
 131
 132 _unspecified_next_default = object()
 133
 134 def _fallback_next(it, default=_unspecified_next_default):
 135     """Retrieve the next item from the iterator by calling its
 136     next() method. If default is given, it is returned if the
 137     iterator is exhausted, otherwise StopIteration is raised."""
 138
 139     if default is _unspecified_next_default:
 140         return it.next()
 141     else:
 142         try:
 143             return it.next()
 144         except StopIteration:
 145             return default
 146
 147 if sys.version_info < (2, 6):
 148     next =  _fallback_next
 149
 150
 151 def merge_iter(iters, pfreq, pfunc, pfinal, key=None):
 152     if key:
 153         samekey = lambda e, pe: getattr(e, key) == getattr(pe, key, None)
 154     else:
 155         samekey = operator.eq
 156     count = 0
 157     total = sum(len(it) for it in iters)
 158     iters = (iter(it) for it in iters)
 159     heap = ((next(it, None),it) for it in iters)
 160     heap = [(e,it) for e,it in heap if e]
 161
 162     heapq.heapify(heap)
 163     pe = None
 164     while heap:
 165         if not count % pfreq:
 166             pfunc(count, total)
 167         e, it = heap[0]
 168         if not samekey(e, pe):
 169             pe = e
 170             yield e
 171         count += 1
 172         try:
 173             e = it.next() # Don't use next() function, it's too expensive
 174         except StopIteration:
 175             heapq.heappop(heap) # remove current
 176         else:
 177             heapq.heapreplace(heap, (e, it)) # shift current to new location
 178     pfinal(count, total)
 179
 180
 181 def unlink(f):
 182     """Delete a file at path 'f' if it currently exists.
 183
 184     Unlike os.unlink(), does not throw an exception if the file didn't already
 185     exist.
 186     """
 187     try:
 188         os.unlink(f)
 189     except OSError, e:
 190         if e.errno == errno.ENOENT:
 191             pass  # it doesn't exist, that's what you asked for
 192
 193
 194 def readpipe(argv, preexec_fn=None):
 195     """Run a subprocess and return its output."""
 196     p = subprocess.Popen(argv, stdout=subprocess.PIPE, preexec_fn=preexec_fn)
 197     out, err = p.communicate()
 198     if p.returncode != 0:
 199         raise Exception('subprocess %r failed with status %d'
 200                         % (' '.join(argv), p.returncode))
 201     return out
 202
 203
 204 def _argmax_base(command):
 205     base_size = 2048
 206     for c in command:
 207         base_size += len(command) + 1
 208     for k, v in environ.iteritems():
 209         base_size += len(k) + len(v) + 2 + sizeof(c_void_p)
 210     return base_size
 211
 212
 213 def _argmax_args_size(args):
 214     return sum(len(x) + 1 + sizeof(c_void_p) for x in args)
 215
 216
 217 def batchpipe(command, args, preexec_fn=None, arg_max=_helpers.SC_ARG_MAX):
 218     """If args is not empty, yield the output produced by calling the
 219 command list with args as a sequence of strings (It may be necessary
 220 to return multiple strings in order to respect ARG_MAX)."""
 221     # The optional arg_max arg is a workaround for an issue with the
 222     # current wvtest behavior.
 223     base_size = _argmax_base(command)
 224     while args:
 225         room = arg_max - base_size
 226         i = 0
 227         while i < len(args):
 228             next_size = _argmax_args_size(args[i:i+1])
 229             if room - next_size < 0:
 230                 break
 231             room -= next_size
 232             i += 1
 233         sub_args = args[:i]
 234         args = args[i:]
 235         assert(len(sub_args))
 236         yield readpipe(command + sub_args, preexec_fn=preexec_fn)
 237
 238
 239 def realpath(p):
 240     """Get the absolute path of a file.
 241
 242     Behaves like os.path.realpath, but doesn't follow a symlink for the last
 243     element. (ie. if 'p' itself is a symlink, this one won't follow it, but it
 244     will follow symlinks in p's directory)
 245     """
 246     try:
 247         st = os.lstat(p)
 248     except OSError:
 249         st = None
 250     if st and stat.S_ISLNK(st.st_mode):
 251         (dir, name) = os.path.split(p)
 252         dir = os.path.realpath(dir)
 253         out = os.path.join(dir, name)
 254     else:
 255         out = os.path.realpath(p)
 256     #log('realpathing:%r,%r\n' % (p, out))
 257     return out
 258
 259
 260 def detect_fakeroot():
 261     "Return True if we appear to be running under fakeroot."
 262     return os.getenv("FAKEROOTKEY") != None
 263
 264
 265 def is_superuser():
 266     if sys.platform.startswith('cygwin'):
 267         import ctypes
 268         return ctypes.cdll.shell32.IsUserAnAdmin()
 269     else:
 270         return os.geteuid() == 0
 271
 272
 273 def _cache_key_value(get_value, key, cache):
 274     """Return (value, was_cached).  If there is a value in the cache
 275     for key, use that, otherwise, call get_value(key) which should
 276     throw a KeyError if there is no value -- in which case the cached
 277     and returned value will be None.
 278     """
 279     try: # Do we already have it (or know there wasn't one)?
 280         value = cache[key]
 281         return value, True
 282     except KeyError:
 283         pass
 284     value = None
 285     try:
 286         cache[key] = value = get_value(key)
 287     except KeyError:
 288         cache[key] = None
 289     return value, False
 290
 291
 292 _uid_to_pwd_cache = {}
 293 _name_to_pwd_cache = {}
 294
 295 def pwd_from_uid(uid):
 296     """Return password database entry for uid (may be a cached value).
 297     Return None if no entry is found.
 298     """
 299     global _uid_to_pwd_cache, _name_to_pwd_cache
 300     entry, cached = _cache_key_value(pwd.getpwuid, uid, _uid_to_pwd_cache)
 301     if entry and not cached:
 302         _name_to_pwd_cache[entry.pw_name] = entry
 303     return entry
 304
 305
 306 def pwd_from_name(name):
 307     """Return password database entry for name (may be a cached value).
 308     Return None if no entry is found.
 309     """
 310     global _uid_to_pwd_cache, _name_to_pwd_cache
 311     entry, cached = _cache_key_value(pwd.getpwnam, name, _name_to_pwd_cache)
 312     if entry and not cached:
 313         _uid_to_pwd_cache[entry.pw_uid] = entry
 314     return entry
 315
 316
 317 _gid_to_grp_cache = {}
 318 _name_to_grp_cache = {}
 319
 320 def grp_from_gid(gid):
 321     """Return password database entry for gid (may be a cached value).
 322     Return None if no entry is found.
 323     """
 324     global _gid_to_grp_cache, _name_to_grp_cache
 325     entry, cached = _cache_key_value(grp.getgrgid, gid, _gid_to_grp_cache)
 326     if entry and not cached:
 327         _name_to_grp_cache[entry.gr_name] = entry
 328     return entry
 329
 330
 331 def grp_from_name(name):
 332     """Return password database entry for name (may be a cached value).
 333     Return None if no entry is found.
 334     """
 335     global _gid_to_grp_cache, _name_to_grp_cache
 336     entry, cached = _cache_key_value(grp.getgrnam, name, _name_to_grp_cache)
 337     if entry and not cached:
 338         _gid_to_grp_cache[entry.gr_gid] = entry
 339     return entry
 340
 341
 342 _username = None
 343 def username():
 344     """Get the user's login name."""
 345     global _username
 346     if not _username:
 347         uid = os.getuid()
 348         _username = pwd_from_uid(uid)[0] or 'user%d' % uid
 349     return _username
 350
 351
 352 _userfullname = None
 353 def userfullname():
 354     """Get the user's full name."""
 355     global _userfullname
 356     if not _userfullname:
 357         uid = os.getuid()
 358         entry = pwd_from_uid(uid)
 359         if entry:
 360             _userfullname = entry[4].split(',')[0] or entry[0]
 361         if not _userfullname:
 362             _userfullname = 'user%d' % uid
 363     return _userfullname
 364
 365
 366 _hostname = None
 367 def hostname():
 368     """Get the FQDN of this machine."""
 369     global _hostname
 370     if not _hostname:
 371         _hostname = socket.getfqdn()
 372     return _hostname
 373
 374
 375 _resource_path = None
 376 def resource_path(subdir=''):
 377     global _resource_path
 378     if not _resource_path:
 379         _resource_path = os.environ.get('BUP_RESOURCE_PATH') or '.'
 380     return os.path.join(_resource_path, subdir)
 381
 382 def format_filesize(size):
 383     unit = 1024.0
 384     size = float(size)
 385     if size < unit:
 386         return "%d" % (size)
 387     exponent = int(math.log(size) / math.log(unit))
 388     size_prefix = "KMGTPE"[exponent - 1]
 389     return "%.1f%s" % (size / math.pow(unit, exponent), size_prefix)
 390
 391
 392 class NotOk(Exception):
 393     pass
 394
 395
 396 class BaseConn:
 397     def __init__(self, outp):
 398         self.outp = outp
 399
 400     def close(self):
 401         while self._read(65536): pass
 402
 403     def read(self, size):
 404         """Read 'size' bytes from input stream."""
 405         self.outp.flush()
 406         return self._read(size)
 407
 408     def readline(self):
 409         """Read from input stream until a newline is found."""
 410         self.outp.flush()
 411         return self._readline()
 412
 413     def write(self, data):
 414         """Write 'data' to output stream."""
 415         #log('%d writing: %d bytes\n' % (os.getpid(), len(data)))
 416         self.outp.write(data)
 417
 418     def has_input(self):
 419         """Return true if input stream is readable."""
 420         raise NotImplemented("Subclasses must implement has_input")
 421
 422     def ok(self):
 423         """Indicate end of output from last sent command."""
 424         self.write('\nok\n')
 425
 426     def error(self, s):
 427         """Indicate server error to the client."""
 428         s = re.sub(r'\s+', ' ', str(s))
 429         self.write('\nerror %s\n' % s)
 430
 431     def _check_ok(self, onempty):
 432         self.outp.flush()
 433         rl = ''
 434         for rl in linereader(self):
 435             #log('%d got line: %r\n' % (os.getpid(), rl))
 436             if not rl:  # empty line
 437                 continue
 438             elif rl == 'ok':
 439                 return None
 440             elif rl.startswith('error '):
 441                 #log('client: error: %s\n' % rl[6:])
 442                 return NotOk(rl[6:])
 443             else:
 444                 onempty(rl)
 445         raise Exception('server exited unexpectedly; see errors above')
 446
 447     def drain_and_check_ok(self):
 448         """Remove all data for the current command from input stream."""
 449         def onempty(rl):
 450             pass
 451         return self._check_ok(onempty)
 452
 453     def check_ok(self):
 454         """Verify that server action completed successfully."""
 455         def onempty(rl):
 456             raise Exception('expected "ok", got %r' % rl)
 457         return self._check_ok(onempty)
 458
 459
 460 class Conn(BaseConn):
 461     def __init__(self, inp, outp):
 462         BaseConn.__init__(self, outp)
 463         self.inp = inp
 464
 465     def _read(self, size):
 466         return self.inp.read(size)
 467
 468     def _readline(self):
 469         return self.inp.readline()
 470
 471     def has_input(self):
 472         [rl, wl, xl] = select.select([self.inp.fileno()], [], [], 0)
 473         if rl:
 474             assert(rl[0] == self.inp.fileno())
 475             return True
 476         else:
 477             return None
 478
 479
 480 def checked_reader(fd, n):
 481     while n > 0:
 482         rl, _, _ = select.select([fd], [], [])
 483         assert(rl[0] == fd)
 484         buf = os.read(fd, n)
 485         if not buf: raise Exception("Unexpected EOF reading %d more bytes" % n)
 486         yield buf
 487         n -= len(buf)
 488
 489
 490 MAX_PACKET = 128 * 1024
 491 def mux(p, outfd, outr, errr):
 492     try:
 493         fds = [outr, errr]
 494         while p.poll() is None:
 495             rl, _, _ = select.select(fds, [], [])
 496             for fd in rl:
 497                 if fd == outr:
 498                     buf = os.read(outr, MAX_PACKET)
 499                     if not buf: break
 500                     os.write(outfd, struct.pack('!IB', len(buf), 1) + buf)
 501                 elif fd == errr:
 502                     buf = os.read(errr, 1024)
 503                     if not buf: break
 504                     os.write(outfd, struct.pack('!IB', len(buf), 2) + buf)
 505     finally:
 506         os.write(outfd, struct.pack('!IB', 0, 3))
 507
 508
 509 class DemuxConn(BaseConn):
 510     """A helper class for bup's client-server protocol."""
 511     def __init__(self, infd, outp):
 512         BaseConn.__init__(self, outp)
 513         # Anything that comes through before the sync string was not
 514         # multiplexed and can be assumed to be debug/log before mux init.
 515         tail = ''
 516         while tail != 'BUPMUX':
 517             b = os.read(infd, (len(tail) < 6) and (6-len(tail)) or 1)
 518             if not b:
 519                 raise IOError('demux: unexpected EOF during initialization')
 520             tail += b
 521             sys.stderr.write(tail[:-6])  # pre-mux log messages
 522             tail = tail[-6:]
 523         self.infd = infd
 524         self.reader = None
 525         self.buf = None
 526         self.closed = False
 527
 528     def write(self, data):
 529         self._load_buf(0)
 530         BaseConn.write(self, data)
 531
 532     def _next_packet(self, timeout):
 533         if self.closed: return False
 534         rl, wl, xl = select.select([self.infd], [], [], timeout)
 535         if not rl: return False
 536         assert(rl[0] == self.infd)
 537         ns = ''.join(checked_reader(self.infd, 5))
 538         n, fdw = struct.unpack('!IB', ns)
 539         assert(n <= MAX_PACKET)
 540         if fdw == 1:
 541             self.reader = checked_reader(self.infd, n)
 542         elif fdw == 2:
 543             for buf in checked_reader(self.infd, n):
 544                 sys.stderr.write(buf)
 545         elif fdw == 3:
 546             self.closed = True
 547             debug2("DemuxConn: marked closed\n")
 548         return True
 549
 550     def _load_buf(self, timeout):
 551         if self.buf is not None:
 552             return True
 553         while not self.closed:
 554             while not self.reader:
 555                 if not self._next_packet(timeout):
 556                     return False
 557             try:
 558                 self.buf = self.reader.next()
 559                 return True
 560             except StopIteration:
 561                 self.reader = None
 562         return False
 563
 564     def _read_parts(self, ix_fn):
 565         while self._load_buf(None):
 566             assert(self.buf is not None)
 567             i = ix_fn(self.buf)
 568             if i is None or i == len(self.buf):
 569                 yv = self.buf
 570                 self.buf = None
 571             else:
 572                 yv = self.buf[:i]
 573                 self.buf = self.buf[i:]
 574             yield yv
 575             if i is not None:
 576                 break
 577
 578     def _readline(self):
 579         def find_eol(buf):
 580             try:
 581                 return buf.index('\n')+1
 582             except ValueError:
 583                 return None
 584         return ''.join(self._read_parts(find_eol))
 585
 586     def _read(self, size):
 587         csize = [size]
 588         def until_size(buf): # Closes on csize
 589             if len(buf) < csize[0]:
 590                 csize[0] -= len(buf)
 591                 return None
 592             else:
 593                 return csize[0]
 594         return ''.join(self._read_parts(until_size))
 595
 596     def has_input(self):
 597         return self._load_buf(0)
 598
 599
 600 def linereader(f):
 601     """Generate a list of input lines from 'f' without terminating newlines."""
 602     while 1:
 603         line = f.readline()
 604         if not line:
 605             break
 606         yield line[:-1]
 607
 608
 609 def chunkyreader(f, count = None):
 610     """Generate a list of chunks of data read from 'f'.
 611
 612     If count is None, read until EOF is reached.
 613
 614     If count is a positive integer, read 'count' bytes from 'f'. If EOF is
 615     reached while reading, raise IOError.
 616     """
 617     if count != None:
 618         while count > 0:
 619             b = f.read(min(count, 65536))
 620             if not b:
 621                 raise IOError('EOF with %d bytes remaining' % count)
 622             yield b
 623             count -= len(b)
 624     else:
 625         while 1:
 626             b = f.read(65536)
 627             if not b: break
 628             yield b
 629
 630
 631 def slashappend(s):
 632     """Append "/" to 's' if it doesn't aleady end in "/"."""
 633     if s and not s.endswith('/'):
 634         return s + '/'
 635     else:
 636         return s
 637
 638
 639 def _mmap_do(f, sz, flags, prot, close):
 640     if not sz:
 641         st = os.fstat(f.fileno())
 642         sz = st.st_size
 643     if not sz:
 644         # trying to open a zero-length map gives an error, but an empty
 645         # string has all the same behaviour of a zero-length map, ie. it has
 646         # no elements :)
 647         return ''
 648     map = mmap.mmap(f.fileno(), sz, flags, prot)
 649     if close:
 650         f.close()  # map will persist beyond file close
 651     return map
 652
 653
 654 def mmap_read(f, sz = 0, close=True):
 655     """Create a read-only memory mapped region on file 'f'.
 656     If sz is 0, the region will cover the entire file.
 657     """
 658     return _mmap_do(f, sz, mmap.MAP_PRIVATE, mmap.PROT_READ, close)
 659
 660
 661 def mmap_readwrite(f, sz = 0, close=True):
 662     """Create a read-write memory mapped region on file 'f'.
 663     If sz is 0, the region will cover the entire file.
 664     """
 665     return _mmap_do(f, sz, mmap.MAP_SHARED, mmap.PROT_READ|mmap.PROT_WRITE,
 666                     close)
 667
 668
 669 def mmap_readwrite_private(f, sz = 0, close=True):
 670     """Create a read-write memory mapped region on file 'f'.
 671     If sz is 0, the region will cover the entire file.
 672     The map is private, which means the changes are never flushed back to the
 673     file.
 674     """
 675     return _mmap_do(f, sz, mmap.MAP_PRIVATE, mmap.PROT_READ|mmap.PROT_WRITE,
 676                     close)
 677
 678
 679 def parse_timestamp(epoch_str):
 680     """Return the number of nanoseconds since the epoch that are described
 681 by epoch_str (100ms, 100ns, ...); when epoch_str cannot be parsed,
 682 throw a ValueError that may contain additional information."""
 683     ns_per = {'s' :  1000000000,
 684               'ms' : 1000000,
 685               'us' : 1000,
 686               'ns' : 1}
 687     match = re.match(r'^((?:[-+]?[0-9]+)?)(s|ms|us|ns)$', epoch_str)
 688     if not match:
 689         if re.match(r'^([-+]?[0-9]+)$', epoch_str):
 690             raise ValueError('must include units, i.e. 100ns, 100ms, ...')
 691         raise ValueError()
 692     (n, units) = match.group(1, 2)
 693     if not n:
 694         n = 1
 695     n = int(n)
 696     return n * ns_per[units]
 697
 698
 699 def parse_num(s):
 700     """Parse data size information into a float number.
 701
 702     Here are some examples of conversions:
 703         199.2k means 203981 bytes
 704         1GB means 1073741824 bytes
 705         2.1 tb means 2199023255552 bytes
 706     """
 707     g = re.match(r'([-+\d.e]+)\s*(\w*)', str(s))
 708     if not g:
 709         raise ValueError("can't parse %r as a number" % s)
 710     (val, unit) = g.groups()
 711     num = float(val)
 712     unit = unit.lower()
 713     if unit in ['t', 'tb']:
 714         mult = 1024*1024*1024*1024
 715     elif unit in ['g', 'gb']:
 716         mult = 1024*1024*1024
 717     elif unit in ['m', 'mb']:
 718         mult = 1024*1024
 719     elif unit in ['k', 'kb']:
 720         mult = 1024
 721     elif unit in ['', 'b']:
 722         mult = 1
 723     else:
 724         raise ValueError("invalid unit %r in number %r" % (unit, s))
 725     return int(num*mult)
 726
 727
 728 def count(l):
 729     """Count the number of elements in an iterator. (consumes the iterator)"""
 730     return reduce(lambda x,y: x+1, l)
 731
 732
 733 saved_errors = []
 734 def add_error(e):
 735     """Append an error message to the list of saved errors.
 736
 737     Once processing is able to stop and output the errors, the saved errors are
 738     accessible in the module variable helpers.saved_errors.
 739     """
 740     saved_errors.append(e)
 741     log('%-70s\n' % e)
 742
 743
 744 def clear_errors():
 745     global saved_errors
 746     saved_errors = []
 747
 748
 749 def handle_ctrl_c():
 750     """Replace the default exception handler for KeyboardInterrupt (Ctrl-C).
 751
 752     The new exception handler will make sure that bup will exit without an ugly
 753     stacktrace when Ctrl-C is hit.
 754     """
 755     oldhook = sys.excepthook
 756     def newhook(exctype, value, traceback):
 757         if exctype == KeyboardInterrupt:
 758             log('\nInterrupted.\n')
 759         else:
 760             return oldhook(exctype, value, traceback)
 761     sys.excepthook = newhook
 762
 763
 764 def columnate(l, prefix):
 765     """Format elements of 'l' in columns with 'prefix' leading each line.
 766
 767     The number of columns is determined automatically based on the string
 768     lengths.
 769     """
 770     if not l:
 771         return ""
 772     l = l[:]
 773     clen = max(len(s) for s in l)
 774     ncols = (tty_width() - len(prefix)) / (clen + 2)
 775     if ncols <= 1:
 776         ncols = 1
 777         clen = 0
 778     cols = []
 779     while len(l) % ncols:
 780         l.append('')
 781     rows = len(l)/ncols
 782     for s in range(0, len(l), rows):
 783         cols.append(l[s:s+rows])
 784     out = ''
 785     for row in zip(*cols):
 786         out += prefix + ''.join(('%-*s' % (clen+2, s)) for s in row) + '\n'
 787     return out
 788
 789
 790 def parse_date_or_fatal(str, fatal):
 791     """Parses the given date or calls Option.fatal().
 792     For now we expect a string that contains a float."""
 793     try:
 794         date = atof(str)
 795     except ValueError, e:
 796         raise fatal('invalid date format (should be a float): %r' % e)
 797     else:
 798         return date
 799
 800
 801 def parse_excludes(options, fatal):
 802     """Traverse the options and extract all excludes, or call Option.fatal()."""
 803     excluded_paths = []
 804
 805     for flag in options:
 806         (option, parameter) = flag
 807         if option == '--exclude':
 808             excluded_paths.append(realpath(parameter))
 809         elif option == '--exclude-from':
 810             try:
 811                 f = open(realpath(parameter))
 812             except IOError, e:
 813                 raise fatal("couldn't read %s" % parameter)
 814             for exclude_path in f.readlines():
 815                 excluded_paths.append(realpath(exclude_path.strip()))
 816     return sorted(frozenset(excluded_paths))
 817
 818
 819 def parse_rx_excludes(options, fatal):
 820     """Traverse the options and extract all rx excludes, or call
 821     Option.fatal()."""
 822     excluded_patterns = []
 823
 824     for flag in options:
 825         (option, parameter) = flag
 826         if option == '--exclude-rx':
 827             try:
 828                 excluded_patterns.append(re.compile(parameter))
 829             except re.error, ex:
 830                 fatal('invalid --exclude-rx pattern (%s): %s' % (parameter, ex))
 831         elif option == '--exclude-rx-from':
 832             try:
 833                 f = open(realpath(parameter))
 834             except IOError, e:
 835                 raise fatal("couldn't read %s" % parameter)
 836             for pattern in f.readlines():
 837                 spattern = pattern.rstrip('\n')
 838                 if not spattern:
 839                     continue
 840                 try:
 841                     excluded_patterns.append(re.compile(spattern))
 842                 except re.error, ex:
 843                     fatal('invalid --exclude-rx pattern (%s): %s' % (spattern, ex))
 844     return excluded_patterns
 845
 846
 847 def should_rx_exclude_path(path, exclude_rxs):
 848     """Return True if path matches a regular expression in exclude_rxs."""
 849     for rx in exclude_rxs:
 850         if rx.search(path):
 851             debug1('Skipping %r: excluded by rx pattern %r.\n'
 852                    % (path, rx.pattern))
 853             return True
 854     return False
 855
 856
 857 # FIXME: Carefully consider the use of functions (os.path.*, etc.)
 858 # that resolve against the current filesystem in the strip/graft
 859 # functions for example, but elsewhere as well.  I suspect bup's not
 860 # always being careful about that.  For some cases, the contents of
 861 # the current filesystem should be irrelevant, and consulting it might
 862 # produce the wrong result, perhaps via unintended symlink resolution,
 863 # for example.
 864
 865 def path_components(path):
 866     """Break path into a list of pairs of the form (name,
 867     full_path_to_name).  Path must start with '/'.
 868     Example:
 869       '/home/foo' -> [('', '/'), ('home', '/home'), ('foo', '/home/foo')]"""
 870     if not path.startswith('/'):
 871         raise Exception, 'path must start with "/": %s' % path
 872     # Since we assume path startswith('/'), we can skip the first element.
 873     result = [('', '/')]
 874     norm_path = os.path.abspath(path)
 875     if norm_path == '/':
 876         return result
 877     full_path = ''
 878     for p in norm_path.split('/')[1:]:
 879         full_path += '/' + p
 880         result.append((p, full_path))
 881     return result
 882
 883
 884 def stripped_path_components(path, strip_prefixes):
 885     """Strip any prefix in strip_prefixes from path and return a list
 886     of path components where each component is (name,
 887     none_or_full_fs_path_to_name).  Assume path startswith('/').
 888     See thelpers.py for examples."""
 889     normalized_path = os.path.abspath(path)
 890     sorted_strip_prefixes = sorted(strip_prefixes, key=len, reverse=True)
 891     for bp in sorted_strip_prefixes:
 892         normalized_bp = os.path.abspath(bp)
 893         if normalized_path.startswith(normalized_bp):
 894             prefix = normalized_path[:len(normalized_bp)]
 895             result = []
 896             for p in normalized_path[len(normalized_bp):].split('/'):
 897                 if p: # not root
 898                     prefix += '/'
 899                 prefix += p
 900                 result.append((p, prefix))
 901             return result
 902     # Nothing to strip.
 903     return path_components(path)
 904
 905
 906 def grafted_path_components(graft_points, path):
 907     # Create a result that consists of some number of faked graft
 908     # directories before the graft point, followed by all of the real
 909     # directories from path that are after the graft point.  Arrange
 910     # for the directory at the graft point in the result to correspond
 911     # to the "orig" directory in --graft orig=new.  See t/thelpers.py
 912     # for some examples.
 913
 914     # Note that given --graft orig=new, orig and new have *nothing* to
 915     # do with each other, even if some of their component names
 916     # match. i.e. --graft /foo/bar/baz=/foo/bar/bax is semantically
 917     # equivalent to --graft /foo/bar/baz=/x/y/z, or even
 918     # /foo/bar/baz=/x.
 919
 920     # FIXME: This can't be the best solution...
 921     clean_path = os.path.abspath(path)
 922     for graft_point in graft_points:
 923         old_prefix, new_prefix = graft_point
 924         # Expand prefixes iff not absolute paths.
 925         old_prefix = os.path.normpath(old_prefix)
 926         new_prefix = os.path.normpath(new_prefix)
 927         if clean_path.startswith(old_prefix):
 928             escaped_prefix = re.escape(old_prefix)
 929             grafted_path = re.sub(r'^' + escaped_prefix, new_prefix, clean_path)
 930             # Handle /foo=/ (at least) -- which produces //whatever.
 931             grafted_path = '/' + grafted_path.lstrip('/')
 932             clean_path_components = path_components(clean_path)
 933             # Count the components that were stripped.
 934             strip_count = 0 if old_prefix == '/' else old_prefix.count('/')
 935             new_prefix_parts = new_prefix.split('/')
 936             result_prefix = grafted_path.split('/')[:new_prefix.count('/')]
 937             result = [(p, None) for p in result_prefix] \
 938                 + clean_path_components[strip_count:]
 939             # Now set the graft point name to match the end of new_prefix.
 940             graft_point = len(result_prefix)
 941             result[graft_point] = \
 942                 (new_prefix_parts[-1], clean_path_components[strip_count][1])
 943             if new_prefix == '/': # --graft ...=/ is a special case.
 944                 return result[1:]
 945             return result
 946     return path_components(clean_path)
 947
 948 Sha1 = hashlib.sha1