CedarBackup2.util

1 # -*- coding: iso-8859-1 -*- 2 # vim: set ft=python ts=3 sw=3 expandtab: 3 # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 4 # 5 # C E D A R 6 # S O L U T I O N S "Software done right." 7 # S O F T W A R E 8 # 9 # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 10 # 11 # Copyright (c) 2004-2008,2010 Kenneth J. Pronovici. 12 # All rights reserved. 13 # 14 # Portions copyright (c) 2001, 2002 Python Software Foundation. 15 # All Rights Reserved. 16 # 17 # This program is free software; you can redistribute it and/or 18 # modify it under the terms of the GNU General Public License, 19 # Version 2, as published by the Free Software Foundation. 20 # 21 # This program is distributed in the hope that it will be useful, 22 # but WITHOUT ANY WARRANTY; without even the implied warranty of 23 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 24 # 25 # Copies of the GNU General Public License are available from 26 # the Free Software Foundation website, http://www.gnu.org/. 27 # 28 # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 29 # 30 # Author : Kenneth J. Pronovici <pronovic@ieee.org> 31 # Language : Python 2 (>= 2.7) 32 # Project : Cedar Backup, release 2 33 # Purpose : Provides general-purpose utilities. 34 # 35 # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 36 37 ######################################################################## 38 # Module documentation 39 ######################################################################## 40 41 """ 42 Provides general-purpose utilities. 43 44 @sort: AbsolutePathList, ObjectTypeList, RestrictedContentList, RegexMatchList, 45 RegexList, _Vertex, DirectedGraph, PathResolverSingleton, 46 sortDict, convertSize, getUidGid, changeOwnership, splitCommandLine, 47 resolveCommand, executeCommand, calculateFileAge, encodePath, nullDevice, 48 deriveDayOfWeek, isStartOfWeek, buildNormalizedPath, 49 ISO_SECTOR_SIZE, BYTES_PER_SECTOR, 50 BYTES_PER_KBYTE, BYTES_PER_MBYTE, BYTES_PER_GBYTE, KBYTES_PER_MBYTE, MBYTES_PER_GBYTE, 51 SECONDS_PER_MINUTE, MINUTES_PER_HOUR, HOURS_PER_DAY, SECONDS_PER_DAY, 52 UNIT_BYTES, UNIT_KBYTES, UNIT_MBYTES, UNIT_GBYTES, UNIT_SECTORS 53 54 @var ISO_SECTOR_SIZE: Size of an ISO image sector, in bytes. 55 @var BYTES_PER_SECTOR: Number of bytes (B) per ISO sector. 56 @var BYTES_PER_KBYTE: Number of bytes (B) per kilobyte (kB). 57 @var BYTES_PER_MBYTE: Number of bytes (B) per megabyte (MB). 58 @var BYTES_PER_GBYTE: Number of bytes (B) per megabyte (GB). 59 @var KBYTES_PER_MBYTE: Number of kilobytes (kB) per megabyte (MB). 60 @var MBYTES_PER_GBYTE: Number of megabytes (MB) per gigabyte (GB). 61 @var SECONDS_PER_MINUTE: Number of seconds per minute. 62 @var MINUTES_PER_HOUR: Number of minutes per hour. 63 @var HOURS_PER_DAY: Number of hours per day. 64 @var SECONDS_PER_DAY: Number of seconds per day. 65 @var UNIT_BYTES: Constant representing the byte (B) unit for conversion. 66 @var UNIT_KBYTES: Constant representing the kilobyte (kB) unit for conversion. 67 @var UNIT_MBYTES: Constant representing the megabyte (MB) unit for conversion. 68 @var UNIT_GBYTES: Constant representing the gigabyte (GB) unit for conversion. 69 @var UNIT_SECTORS: Constant representing the ISO sector unit for conversion. 70 71 @author: Kenneth J. Pronovici <pronovic@ieee.org> 72 """ 73 74 75 ######################################################################## 76 # Imported modules 77 ######################################################################## 78 79 import sys 80 import math 81 import os 82 import re 83 import time 84 import logging 85 import string # pylint: disable=W0402 86 from subprocess import Popen, STDOUT, PIPE 87 88 try: 89 import pwd 90 import grp 91 _UID_GID_AVAILABLE = True 92 except ImportError: 93 _UID_GID_AVAILABLE = False 94 95 from CedarBackup2.release import VERSION, DATE 96 97 98 ######################################################################## 99 # Module-wide constants and variables 100 ######################################################################## 101 102 logger = logging.getLogger("CedarBackup2.log.util") 103 outputLogger = logging.getLogger("CedarBackup2.output") 104 105 ISO_SECTOR_SIZE = 2048.0 # in bytes 106 BYTES_PER_SECTOR = ISO_SECTOR_SIZE 107 108 BYTES_PER_KBYTE = 1024.0 109 KBYTES_PER_MBYTE = 1024.0 110 MBYTES_PER_GBYTE = 1024.0 111 BYTES_PER_MBYTE = BYTES_PER_KBYTE * KBYTES_PER_MBYTE 112 BYTES_PER_GBYTE = BYTES_PER_MBYTE * MBYTES_PER_GBYTE 113 114 SECONDS_PER_MINUTE = 60.0 115 MINUTES_PER_HOUR = 60.0 116 HOURS_PER_DAY = 24.0 117 SECONDS_PER_DAY = SECONDS_PER_MINUTE * MINUTES_PER_HOUR * HOURS_PER_DAY 118 119 UNIT_BYTES = 0 120 UNIT_KBYTES = 1 121 UNIT_MBYTES = 2 122 UNIT_GBYTES = 4 123 UNIT_SECTORS = 3 124 125 MTAB_FILE = "/etc/mtab" 126 127 MOUNT_COMMAND = [ "mount", ] 128 UMOUNT_COMMAND = [ "umount", ] 129 130 DEFAULT_LANGUAGE = "C" 131 LANG_VAR = "LANG" 132 LOCALE_VARS = [ "LC_ADDRESS", "LC_ALL", "LC_COLLATE", 133 "LC_CTYPE", "LC_IDENTIFICATION", 134 "LC_MEASUREMENT", "LC_MESSAGES", 135 "LC_MONETARY", "LC_NAME", "LC_NUMERIC", 136 "LC_PAPER", "LC_TELEPHONE", "LC_TIME", ]

137 138 139 ######################################################################## 140 # UnorderedList class definition 141 ######################################################################## 142 143 -class UnorderedList(list):

144 145 """ 146 Class representing an "unordered list". 147 148 An "unordered list" is a list in which only the contents matter, not the 149 order in which the contents appear in the list. 150 151 For instance, we might be keeping track of set of paths in a list, because 152 it's convenient to have them in that form. However, for comparison 153 purposes, we would only care that the lists contain exactly the same 154 contents, regardless of order. 155 156 I have come up with two reasonable ways of doing this, plus a couple more 157 that would work but would be a pain to implement. My first method is to 158 copy and sort each list, comparing the sorted versions. This will only work 159 if two lists with exactly the same members are guaranteed to sort in exactly 160 the same order. The second way would be to create two Sets and then compare 161 the sets. However, this would lose information about any duplicates in 162 either list. I've decided to go with option #1 for now. I'll modify this 163 code if I run into problems in the future. 164 165 We override the original C{__eq__}, C{__ne__}, C{__ge__}, C{__gt__}, 166 C{__le__} and C{__lt__} list methods to change the definition of the various 167 comparison operators. In all cases, the comparison is changed to return the 168 result of the original operation I{but instead comparing sorted lists}. 169 This is going to be quite a bit slower than a normal list, so you probably 170 only want to use it on small lists. 171 """ 172

173 - def __eq__(self, other):

174 """ 175 Definition of C{==} operator for this class. 176 @param other: Other object to compare to. 177 @return: True/false depending on whether C{self == other}. 178 """ 179 if other is None: 180 return False 181 selfSorted = self[:] 182 otherSorted = other[:] 183 selfSorted.sort() 184 otherSorted.sort() 185 return selfSorted.__eq__(otherSorted)

186

187 - def __ne__(self, other):

188 """ 189 Definition of C{!=} operator for this class. 190 @param other: Other object to compare to. 191 @return: True/false depending on whether C{self != other}. 192 """ 193 if other is None: 194 return True 195 selfSorted = self[:] 196 otherSorted = other[:] 197 selfSorted.sort() 198 otherSorted.sort() 199 return selfSorted.__ne__(otherSorted)

200

201 - def __ge__(self, other):

202 """ 203 Definition of S{>=} operator for this class. 204 @param other: Other object to compare to. 205 @return: True/false depending on whether C{self >= other}. 206 """ 207 if other is None: 208 return True 209 selfSorted = self[:] 210 otherSorted = other[:] 211 selfSorted.sort() 212 otherSorted.sort() 213 return selfSorted.__ge__(otherSorted)

214

215 - def __gt__(self, other):

216 """ 217 Definition of C{>} operator for this class. 218 @param other: Other object to compare to. 219 @return: True/false depending on whether C{self > other}. 220 """ 221 if other is None: 222 return True 223 selfSorted = self[:] 224 otherSorted = other[:] 225 selfSorted.sort() 226 otherSorted.sort() 227 return selfSorted.__gt__(otherSorted)

228

229 - def __le__(self, other):

230 """ 231 Definition of S{<=} operator for this class. 232 @param other: Other object to compare to. 233 @return: True/false depending on whether C{self <= other}. 234 """ 235 if other is None: 236 return False 237 selfSorted = self[:] 238 otherSorted = other[:] 239 selfSorted.sort() 240 otherSorted.sort() 241 return selfSorted.__le__(otherSorted)

242

243 - def __lt__(self, other):

244 """ 245 Definition of C{<} operator for this class. 246 @param other: Other object to compare to. 247 @return: True/false depending on whether C{self < other}. 248 """ 249 if other is None: 250 return False 251 selfSorted = self[:] 252 otherSorted = other[:] 253 selfSorted.sort() 254 otherSorted.sort() 255 return selfSorted.__lt__(otherSorted)

256

257 258 ######################################################################## 259 # AbsolutePathList class definition 260 ######################################################################## 261 262 -class AbsolutePathList(UnorderedList):

263 264 """ 265 Class representing a list of absolute paths. 266 267 This is an unordered list. 268 269 We override the C{append}, C{insert} and C{extend} methods to ensure that 270 any item added to the list is an absolute path. 271 272 Each item added to the list is encoded using L{encodePath}. If we don't do 273 this, we have problems trying certain operations between strings and unicode 274 objects, particularly for "odd" filenames that can't be encoded in standard 275 ASCII. 276 """ 277

278 - def append(self, item):

279 """ 280 Overrides the standard C{append} method. 281 @raise ValueError: If item is not an absolute path. 282 """ 283 if not os.path.isabs(item): 284 raise ValueError("Not an absolute path: [%s]" % item) 285 list.append(self, encodePath(item))

286

287 - def insert(self, index, item):

288 """ 289 Overrides the standard C{insert} method. 290 @raise ValueError: If item is not an absolute path. 291 """ 292 if not os.path.isabs(item): 293 raise ValueError("Not an absolute path: [%s]" % item) 294 list.insert(self, index, encodePath(item))

295

296 - def extend(self, seq):

297 """ 298 Overrides the standard C{insert} method. 299 @raise ValueError: If any item is not an absolute path. 300 """ 301 for item in seq: 302 if not os.path.isabs(item): 303 raise ValueError("Not an absolute path: [%s]" % item) 304 for item in seq: 305 list.append(self, encodePath(item))

306

307 308 ######################################################################## 309 # ObjectTypeList class definition 310 ######################################################################## 311 312 -class ObjectTypeList(UnorderedList):

313 314 """ 315 Class representing a list containing only objects with a certain type. 316 317 This is an unordered list. 318 319 We override the C{append}, C{insert} and C{extend} methods to ensure that 320 any item added to the list matches the type that is requested. The 321 comparison uses the built-in C{isinstance}, which should allow subclasses of 322 of the requested type to be added to the list as well. 323 324 The C{objectName} value will be used in exceptions, i.e. C{"Item must be a 325 CollectDir object."} if C{objectName} is C{"CollectDir"}. 326 """ 327

328 - def __init__(self, objectType, objectName):

329 """ 330 Initializes a typed list for a particular type. 331 @param objectType: Type that the list elements must match. 332 @param objectName: Short string containing the "name" of the type. 333 """ 334 super(ObjectTypeList, self).__init__() 335 self.objectType = objectType 336 self.objectName = objectName

337

338 - def append(self, item):

339 """ 340 Overrides the standard C{append} method. 341 @raise ValueError: If item does not match requested type. 342 """ 343 if not isinstance(item, self.objectType): 344 raise ValueError("Item must be a %s object." % self.objectName) 345 list.append(self, item)

346

347 - def insert(self, index, item):

348 """ 349 Overrides the standard C{insert} method. 350 @raise ValueError: If item does not match requested type. 351 """ 352 if not isinstance(item, self.objectType): 353 raise ValueError("Item must be a %s object." % self.objectName) 354 list.insert(self, index, item)

355

356 - def extend(self, seq):

357 """ 358 Overrides the standard C{insert} method. 359 @raise ValueError: If item does not match requested type. 360 """ 361 for item in seq: 362 if not isinstance(item, self.objectType): 363 raise ValueError("All items must be %s objects." % self.objectName) 364 list.extend(self, seq)

365

366 367 ######################################################################## 368 # RestrictedContentList class definition 369 ######################################################################## 370 371 -class RestrictedContentList(UnorderedList):

372 373 """ 374 Class representing a list containing only object with certain values. 375 376 This is an unordered list. 377 378 We override the C{append}, C{insert} and C{extend} methods to ensure that 379 any item added to the list is among the valid values. We use a standard 380 comparison, so pretty much anything can be in the list of valid values. 381 382 The C{valuesDescr} value will be used in exceptions, i.e. C{"Item must be 383 one of values in VALID_ACTIONS"} if C{valuesDescr} is C{"VALID_ACTIONS"}. 384 385 @note: This class doesn't make any attempt to trap for nonsensical 386 arguments. All of the values in the values list should be of the same type 387 (i.e. strings). Then, all list operations also need to be of that type 388 (i.e. you should always insert or append just strings). If you mix types -- 389 for instance lists and strings -- you will likely see AttributeError 390 exceptions or other problems. 391 """ 392

393 - def __init__(self, valuesList, valuesDescr, prefix=None):

394 """ 395 Initializes a list restricted to containing certain values. 396 @param valuesList: List of valid values. 397 @param valuesDescr: Short string describing list of values. 398 @param prefix: Prefix to use in error messages (None results in prefix "Item") 399 """ 400 super(RestrictedContentList, self).__init__() 401 self.prefix = "Item" 402 if prefix is not None: self.prefix = prefix 403 self.valuesList = valuesList 404 self.valuesDescr = valuesDescr

405

406 - def append(self, item):

407 """ 408 Overrides the standard C{append} method. 409 @raise ValueError: If item is not in the values list. 410 """ 411 if item not in self.valuesList: 412 raise ValueError("%s must be one of the values in %s." % (self.prefix, self.valuesDescr)) 413 list.append(self, item)

414

415 - def insert(self, index, item):

416 """ 417 Overrides the standard C{insert} method. 418 @raise ValueError: If item is not in the values list. 419 """ 420 if item not in self.valuesList: 421 raise ValueError("%s must be one of the values in %s." % (self.prefix, self.valuesDescr)) 422 list.insert(self, index, item)

423

424 - def extend(self, seq):

425 """ 426 Overrides the standard C{insert} method. 427 @raise ValueError: If item is not in the values list. 428 """ 429 for item in seq: 430 if item not in self.valuesList: 431 raise ValueError("%s must be one of the values in %s." % (self.prefix, self.valuesDescr)) 432 list.extend(self, seq)

433

434 435 ######################################################################## 436 # RegexMatchList class definition 437 ######################################################################## 438 439 -class RegexMatchList(UnorderedList):

440 441 """ 442 Class representing a list containing only strings that match a regular expression. 443 444 If C{emptyAllowed} is passed in as C{False}, then empty strings are 445 explicitly disallowed, even if they happen to match the regular expression. 446 (C{None} values are always disallowed, since string operations are not 447 permitted on C{None}.) 448 449 This is an unordered list. 450 451 We override the C{append}, C{insert} and C{extend} methods to ensure that 452 any item added to the list matches the indicated regular expression. 453 454 @note: If you try to put values that are not strings into the list, you will 455 likely get either TypeError or AttributeError exceptions as a result. 456 """ 457

458 - def __init__(self, valuesRegex, emptyAllowed=True, prefix=None):

459 """ 460 Initializes a list restricted to containing certain values. 461 @param valuesRegex: Regular expression that must be matched, as a string 462 @param emptyAllowed: Indicates whether empty or None values are allowed. 463 @param prefix: Prefix to use in error messages (None results in prefix "Item") 464 """ 465 super(RegexMatchList, self).__init__() 466 self.prefix = "Item" 467 if prefix is not None: self.prefix = prefix 468 self.valuesRegex = valuesRegex 469 self.emptyAllowed = emptyAllowed 470 self.pattern = re.compile(self.valuesRegex)

471

472 - def append(self, item):

473 """ 474 Overrides the standard C{append} method. 475 @raise ValueError: If item is None 476 @raise ValueError: If item is empty and empty values are not allowed 477 @raise ValueError: If item does not match the configured regular expression 478 """ 479 if item is None or (not self.emptyAllowed and item == ""): 480 raise ValueError("%s cannot be empty." % self.prefix) 481 if not self.pattern.search(item): 482 raise ValueError("%s is not valid: [%s]" % (self.prefix, item)) 483 list.append(self, item)

484

485 - def insert(self, index, item):

486 """ 487 Overrides the standard C{insert} method. 488 @raise ValueError: If item is None 489 @raise ValueError: If item is empty and empty values are not allowed 490 @raise ValueError: If item does not match the configured regular expression 491 """ 492 if item is None or (not self.emptyAllowed and item == ""): 493 raise ValueError("%s cannot be empty." % self.prefix) 494 if not self.pattern.search(item): 495 raise ValueError("%s is not valid [%s]" % (self.prefix, item)) 496 list.insert(self, index, item)

497

498 - def extend(self, seq):

499 """ 500 Overrides the standard C{insert} method. 501 @raise ValueError: If any item is None 502 @raise ValueError: If any item is empty and empty values are not allowed 503 @raise ValueError: If any item does not match the configured regular expression 504 """ 505 for item in seq: 506 if item is None or (not self.emptyAllowed and item == ""): 507 raise ValueError("%s cannot be empty." % self.prefix) 508 if not self.pattern.search(item): 509 raise ValueError("%s is not valid: [%s]" % (self.prefix, item)) 510 list.extend(self, seq)

511

512 513 ######################################################################## 514 # RegexList class definition 515 ######################################################################## 516 517 -class RegexList(UnorderedList):

518 519 """ 520 Class representing a list of valid regular expression strings. 521 522 This is an unordered list. 523 524 We override the C{append}, C{insert} and C{extend} methods to ensure that 525 any item added to the list is a valid regular expression. 526 """ 527

528 - def append(self, item):

529 """ 530 Overrides the standard C{append} method. 531 @raise ValueError: If item is not an absolute path. 532 """ 533 try: 534 re.compile(item) 535 except re.error: 536 raise ValueError("Not a valid regular expression: [%s]" % item) 537 list.append(self, item)

538

539 - def insert(self, index, item):

540 """ 541 Overrides the standard C{insert} method. 542 @raise ValueError: If item is not an absolute path. 543 """ 544 try: 545 re.compile(item) 546 except re.error: 547 raise ValueError("Not a valid regular expression: [%s]" % item) 548 list.insert(self, index, item)

549

550 - def extend(self, seq):

551 """ 552 Overrides the standard C{insert} method. 553 @raise ValueError: If any item is not an absolute path. 554 """ 555 for item in seq: 556 try: 557 re.compile(item) 558 except re.error: 559 raise ValueError("Not a valid regular expression: [%s]" % item) 560 for item in seq: 561 list.append(self, item)

562

563 564 ######################################################################## 565 # Directed graph implementation 566 ######################################################################## 567 568 -class _Vertex(object):

569 570 """ 571 Represents a vertex (or node) in a directed graph. 572 """ 573

574 - def __init__(self, name):

575 """ 576 Constructor. 577 @param name: Name of this graph vertex. 578 @type name: String value. 579 """ 580 self.name = name 581 self.endpoints = [] 582 self.state = None

583

584 -class DirectedGraph(object):

585 586 """ 587 Represents a directed graph. 588 589 A graph B{G=(V,E)} consists of a set of vertices B{V} together with a set 590 B{E} of vertex pairs or edges. In a directed graph, each edge also has an 591 associated direction (from vertext B{v1} to vertex B{v2}). A C{DirectedGraph} 592 object provides a way to construct a directed graph and execute a depth- 593 first search. 594 595 This data structure was designed based on the graphing chapter in 596 U{The Algorithm Design Manual<http://www2.toki.or.id/book/AlgDesignManual/>}, 597 by Steven S. Skiena. 598 599 This class is intended to be used by Cedar Backup for dependency ordering. 600 Because of this, it's not quite general-purpose. Unlike a "general" graph, 601 every vertex in this graph has at least one edge pointing to it, from a 602 special "start" vertex. This is so no vertices get "lost" either because 603 they have no dependencies or because nothing depends on them. 604 """ 605 606 _UNDISCOVERED = 0 607 _DISCOVERED = 1 608 _EXPLORED = 2 609

610 - def __init__(self, name):

611 """ 612 Directed graph constructor. 613 614 @param name: Name of this graph. 615 @type name: String value. 616 """ 617 if name is None or name == "": 618 raise ValueError("Graph name must be non-empty.") 619 self._name = name 620 self._vertices = {} 621 self._startVertex = _Vertex(None) # start vertex is only vertex with no name

622

623 - def __repr__(self):

624 """ 625 Official string representation for class instance. 626 """ 627 return "DirectedGraph(%s)" % self.name

628

629 - def __str__(self):

630 """ 631 Informal string representation for class instance. 632 """ 633 return self.__repr__()

634

635 - def __cmp__(self, other):

636 """ 637 Definition of equals operator for this class. 638 @param other: Other object to compare to. 639 @return: -1/0/1 depending on whether self is C{<}, C{=} or C{>} other. 640 """ 641 # pylint: disable=W0212 642 if other is None: 643 return 1 644 if self.name != other.name: 645 if self.name < other.name: 646 return -1 647 else: 648 return 1 649 if self._vertices != other._vertices: 650 if self._vertices < other._vertices: 651 return -1 652 else: 653 return 1 654 return 0

655

656 - def _getName(self):

657 """ 658 Property target used to get the graph name. 659 """ 660 return self._name

661 662 name = property(_getName, None, None, "Name of the graph.") 663

664 - def createVertex(self, name):

665 """ 666 Creates a named vertex. 667 @param name: vertex name 668 @raise ValueError: If the vertex name is C{None} or empty. 669 """ 670 if name is None or name == "": 671 raise ValueError("Vertex name must be non-empty.") 672 vertex = _Vertex(name) 673 self._startVertex.endpoints.append(vertex) # so every vertex is connected at least once 674 self._vertices[name] = vertex

675

676 - def createEdge(self, start, finish):

677 """ 678 Adds an edge with an associated direction, from C{start} vertex to C{finish} vertex. 679 @param start: Name of start vertex. 680 @param finish: Name of finish vertex. 681 @raise ValueError: If one of the named vertices is unknown. 682 """ 683 try: 684 startVertex = self._vertices[start] 685 finishVertex = self._vertices[finish] 686 startVertex.endpoints.append(finishVertex) 687 except KeyError, e: 688 raise ValueError("Vertex [%s] could not be found." % e)

689

690 - def topologicalSort(self):

691 """ 692 Implements a topological sort of the graph. 693 694 This method also enforces that the graph is a directed acyclic graph, 695 which is a requirement of a topological sort. 696 697 A directed acyclic graph (or "DAG") is a directed graph with no directed 698 cycles. A topological sort of a DAG is an ordering on the vertices such 699 that all edges go from left to right. Only an acyclic graph can have a 700 topological sort, but any DAG has at least one topological sort. 701 702 Since a topological sort only makes sense for an acyclic graph, this 703 method throws an exception if a cycle is found. 704 705 A depth-first search only makes sense if the graph is acyclic. If the 706 graph contains any cycles, it is not possible to determine a consistent 707 ordering for the vertices. 708 709 @note: If a particular vertex has no edges, then its position in the 710 final list depends on the order in which the vertices were created in the 711 graph. If you're using this method to determine a dependency order, this 712 makes sense: a vertex with no dependencies can go anywhere (and will). 713 714 @return: Ordering on the vertices so that all edges go from left to right. 715 716 @raise ValueError: If a cycle is found in the graph. 717 """ 718 ordering = [] 719 for key in self._vertices: 720 vertex = self._vertices[key] 721 vertex.state = self._UNDISCOVERED 722 for key in self._vertices: 723 vertex = self._vertices[key] 724 if vertex.state == self._UNDISCOVERED: 725 self._topologicalSort(self._startVertex, ordering) 726 return ordering

727

728 - def _topologicalSort(self, vertex, ordering):

729 """ 730 Recursive depth first search function implementing topological sort. 731 @param vertex: Vertex to search 732 @param ordering: List of vertices in proper order 733 """ 734 vertex.state = self._DISCOVERED 735 for endpoint in vertex.endpoints: 736 if endpoint.state == self._UNDISCOVERED: 737 self._topologicalSort(endpoint, ordering) 738 elif endpoint.state != self._EXPLORED: 739 raise ValueError("Cycle found in graph (found '%s' while searching '%s')." % (vertex.name, endpoint.name)) 740 if vertex.name is not None: 741 ordering.insert(0, vertex.name) 742 vertex.state = self._EXPLORED

743

744 745 ######################################################################## 746 # PathResolverSingleton class definition 747 ######################################################################## 748 749 -class PathResolverSingleton(object):

750 751 """ 752 Singleton used for resolving executable paths. 753 754 Various functions throughout Cedar Backup (including extensions) need a way 755 to resolve the path of executables that they use. For instance, the image 756 functionality needs to find the C{mkisofs} executable, and the Subversion 757 extension needs to find the C{svnlook} executable. Cedar Backup's original 758 behavior was to assume that the simple name (C{"svnlook"} or whatever) was 759 available on the caller's C{$PATH}, and to fail otherwise. However, this 760 turns out to be less than ideal, since for instance the root user might not 761 always have executables like C{svnlook} in its path. 762 763 One solution is to specify a path (either via an absolute path or some sort 764 of path insertion or path appending mechanism) that would apply to the 765 C{executeCommand()} function. This is not difficult to implement, but it 766 seem like kind of a "big hammer" solution. Besides that, it might also 767 represent a security flaw (for instance, I prefer not to mess with root's 768 C{$PATH} on the application level if I don't have to). 769 770 The alternative is to set up some sort of configuration for the path to 771 certain executables, i.e. "find C{svnlook} in C{/usr/local/bin/svnlook}" or 772 whatever. This PathResolverSingleton aims to provide a good solution to the 773 mapping problem. Callers of all sorts (extensions or not) can get an 774 instance of the singleton. Then, they call the C{lookup} method to try and 775 resolve the executable they are looking for. Through the C{lookup} method, 776 the caller can also specify a default to use if a mapping is not found. 777 This way, with no real effort on the part of the caller, behavior can neatly 778 degrade to something equivalent to the current behavior if there is no 779 special mapping or if the singleton was never initialized in the first 780 place. 781 782 Even better, extensions automagically get access to the same resolver 783 functionality, and they don't even need to understand how the mapping 784 happens. All extension authors need to do is document what executables 785 their code requires, and the standard resolver configuration section will 786 meet their needs. 787 788 The class should be initialized once through the constructor somewhere in 789 the main routine. Then, the main routine should call the L{fill} method to 790 fill in the resolver's internal structures. Everyone else who needs to 791 resolve a path will get an instance of the class using L{getInstance} and 792 will then just call the L{lookup} method. 793 794 @cvar _instance: Holds a reference to the singleton 795 @ivar _mapping: Internal mapping from resource name to path. 796 """ 797 798 _instance = None # Holds a reference to singleton instance 799

800 - class _Helper(object):

801 """Helper class to provide a singleton factory method."""

802 - def __init__(self):

803 pass

804 - def __call__(self, *args, **kw):

805 # pylint: disable=W0212,R0201 806 if PathResolverSingleton._instance is None: 807 obj = PathResolverSingleton() 808 PathResolverSingleton._instance = obj 809 return PathResolverSingleton._instance

810 811 getInstance = _Helper() # Method that callers will use to get an instance 812

813 - def __init__(self):

814 """Singleton constructor, which just creates the singleton instance.""" 815 if PathResolverSingleton._instance is not None: 816 raise RuntimeError("Only one instance of PathResolverSingleton is allowed!") 817 PathResolverSingleton._instance = self 818 self._mapping = { }

819

820 - def lookup(self, name, default=None):

821 """ 822 Looks up name and returns the resolved path associated with the name. 823 @param name: Name of the path resource to resolve. 824 @param default: Default to return if resource cannot be resolved. 825 @return: Resolved path associated with name, or default if name can't be resolved. 826 """ 827 value = default 828 if name in self._mapping.keys(): 829 value = self._mapping[name] 830 logger.debug("Resolved command [%s] to [%s].", name, value) 831 return value

832

833 - def fill(self, mapping):

834 """ 835 Fills in the singleton's internal mapping from name to resource. 836 @param mapping: Mapping from resource name to path. 837 @type mapping: Dictionary mapping name to path, both as strings. 838 """ 839 self._mapping = { } 840 for key in mapping.keys(): 841 self._mapping[key] = mapping[key]

842

843 844 ######################################################################## 845 # Pipe class definition 846 ######################################################################## 847 848 -class Pipe(Popen):

849 """ 850 Specialized pipe class for use by C{executeCommand}. 851 852 The L{executeCommand} function needs a specialized way of interacting 853 with a pipe. First, C{executeCommand} only reads from the pipe, and <

Source Code for Module CedarBackup2.util