Package ClusterShell :: Module NodeSet
[hide private]
[frames] | no frames]

Source Code for Module ClusterShell.NodeSet

   1  # 
   2  # Copyright CEA/DAM/DIF (2007, 2008, 2009, 2010) 
   3  #  Contributor: Stephane THIELL <stephane.thiell@cea.fr> 
   4  # 
   5  # This file is part of the ClusterShell library. 
   6  # 
   7  # This software is governed by the CeCILL-C license under French law and 
   8  # abiding by the rules of distribution of free software.  You can  use, 
   9  # modify and/ or redistribute the software under the terms of the CeCILL-C 
  10  # license as circulated by CEA, CNRS and INRIA at the following URL 
  11  # "http://www.cecill.info". 
  12  # 
  13  # As a counterpart to the access to the source code and  rights to copy, 
  14  # modify and redistribute granted by the license, users are provided only 
  15  # with a limited warranty  and the software's author,  the holder of the 
  16  # economic rights,  and the successive licensors  have only  limited 
  17  # liability. 
  18  # 
  19  # In this respect, the user's attention is drawn to the risks associated 
  20  # with loading,  using,  modifying and/or developing or reproducing the 
  21  # software by the user in light of its specific status of free software, 
  22  # that may mean  that it is complicated to manipulate,  and  that  also 
  23  # therefore means  that it is reserved for developers  and  experienced 
  24  # professionals having in-depth computer knowledge. Users are therefore 
  25  # encouraged to load and test the software's suitability as regards their 
  26  # requirements in conditions enabling the security of their systems and/or 
  27  # data to be ensured and,  more generally, to use and operate it in the 
  28  # same conditions as regards security. 
  29  # 
  30  # The fact that you are presently reading this means that you have had 
  31  # knowledge of the CeCILL-C license and that you accept its terms. 
  32  # 
  33  # $Id: NodeSet.py 233 2010-02-25 16:51:55Z st-cea $ 
  34   
  35  """ 
  36  Cluster node set. 
  37   
  38  A module to deal efficiently with 1D rangesets and nodesets (pdsh-like). 
  39  Instances of RangeSet and NodeSet both provide similar operations than 
  40  the builtin set() type and Set object. 
  41     [ See http://www.python.org/doc/lib/set-objects.html ] 
  42   
  43  Usage example: 
  44   
  45      # Import NodeSet class 
  46      from ClusterShell.NodeSet import NodeSet 
  47   
  48      # Create a new nodeset from pdsh-like pattern 
  49      nodeset = NodeSet("cluster[1-30]") 
  50   
  51      # Add cluster32 to nodeset 
  52      nodeset.update("cluster32") 
  53   
  54      # Remove from nodeset 
  55      nodeset.difference_update("cluster[2-5]") 
  56   
  57      # Print nodeset as a pdsh-like pattern 
  58      print nodeset 
  59   
  60      # Iterate over node names in nodeset 
  61      for node in nodeset: 
  62          print node 
  63  """ 
  64   
  65  import copy 
  66  import re 
67 68 -class RangeSetException(Exception):
69 """Base RangeSet exception class."""
70
71 -class RangeSetParseError(RangeSetException):
72 """Raised when RangeSet parsing cannot be done properly."""
73 - def __init__(self, part, msg):
74 if part: 75 msg = "%s : \"%s\"" % (msg, part) 76 RangeSetException.__init__(self, msg) 77 # faulty subrange; this allows you to target the error 78 self.part = part
79
80 -class RangeSetPaddingError(RangeSetParseError):
81 """Raised when a fatal padding incoherency occurs"""
82 - def __init__(self, part, msg):
83 RangeSetParseError.__init__(self, part, "padding mismatch (%s)" % msg)
84
85 86 -class NodeSetException(Exception):
87 """Base NodeSet exception class."""
88
89 -class NodeSetParseError(NodeSetException):
90 """Raised when NodeSet parsing cannot be done properly."""
91 - def __init__(self, part, msg):
92 if part: 93 msg = "%s : \"%s\"" % (msg, part) 94 NodeSetException.__init__(self, msg) 95 # faulty part; this allows you to target the error 96 self.part = part
97
98 -class NodeSetParseRangeError(NodeSetParseError):
99 """Raised when bad range is encountered during NodeSet parsing."""
100 - def __init__(self, rset_exc):
101 NodeSetParseError.__init__(self, str(rset_exc), "bad range")
102
103 104 -class RangeSet:
105 """ 106 Advanced range sets. 107 108 RangeSet creation examples: 109 rset = RangeSet() # empty RangeSet 110 rset = RangeSet("5,10-42") # contains 5, 10 to 42 111 rset = RangeSet("0-10/2") # contains 0, 2, 4, 6, 8, 10 112 113 Also, RangeSet provides methods like update(), intersection_update() 114 or difference_update(), which conform to the Python Set API. 115 """
116 - def __init__(self, pattern=None, autostep=None):
117 """ 118 Initialize RangeSet with optional pdsh-like string pattern and 119 autostep threshold. 120 """ 121 if autostep is None: 122 # disabled by default for pdsh compat (+inf is 1E400, but a bug in 123 # python 2.4 makes it impossible to be pickled, so we use less). 124 self._autostep = 1E100 125 else: 126 # - 1 because user means node count, but we means 127 # real steps. 128 self._autostep = int(autostep) - 1 129 130 self._length = 0 131 self._ranges = [] 132 133 if pattern is not None: 134 135 # Comma separated ranges 136 if pattern.find(',') < 0: 137 subranges = [pattern] 138 else: 139 subranges = pattern.split(',') 140 141 for subrange in subranges: 142 if subrange.find('/') < 0: 143 step = 1 144 baserange = subrange 145 else: 146 baserange, step = subrange.split('/', 1) 147 148 try: 149 step = int(step) 150 except ValueError: 151 raise RangeSetParseError(subrange, 152 "cannot convert string to integer") 153 154 if baserange.find('-') < 0: 155 if step != 1: 156 raise RangeSetParseError(subrange, 157 "invalid step usage") 158 begin = end = baserange 159 else: 160 begin, end = baserange.split('-', 1) 161 162 # compute padding and return node range info tuple 163 try: 164 pad = 0 165 if int(begin) != 0: 166 begins = begin.lstrip("0") 167 if len(begin) - len(begins) > 0: 168 pad = len(begin) 169 start = int(begins) 170 else: 171 if len(begin) > 1: 172 pad = len(begin) 173 start = 0 174 if int(end) != 0: 175 ends = end.lstrip("0") 176 else: 177 ends = end 178 stop = int(ends) 179 except ValueError: 180 raise RangeSetParseError(subrange, 181 "cannot convert string to integer") 182 183 # check preconditions 184 if start > stop or step < 1: 185 raise RangeSetParseError(subrange, 186 "invalid values in range") 187 188 self.add_range(start, stop, step, pad)
189 190 @classmethod
191 - def fromlist(cls, rglist, autostep=None):
192 """ 193 Class method that returns a new RangeSet with ranges from 194 provided list. 195 """ 196 inst = RangeSet(autostep=autostep) 197 for rg in rglist: 198 if isinstance(rg, RangeSet): 199 inst.update(rg) 200 else: 201 inst.update(RangeSet(rg)) 202 return inst
203
204 - def __iter__(self):
205 """ 206 Iterate over each item in RangeSet. 207 """ 208 for start, stop, step, pad in self._ranges: 209 for i in range(start, stop + 1, step): 210 yield "%*d" % (pad, i)
211
212 - def __len__(self):
213 """ 214 Get the number of items in RangeSet. 215 """ 216 return self._length
217
218 - def __str__(self):
219 """ 220 Get range-based string. 221 """ 222 cnt = 0 223 s = "" 224 for start, stop, step, pad in self._ranges: 225 assert pad != None 226 if cnt > 0: 227 s += "," 228 if start == stop: 229 s += "%0*d" % (pad, start) 230 else: 231 assert step >= 0, "Internal error: step < 0" 232 if step == 1: 233 s += "%0*d-%0*d" % (pad, start, pad, stop) 234 else: 235 s += "%0*d-%0*d/%d" % (pad, start, pad, stop, step) 236 cnt += stop - start + 1 237 return s
238 239 # __repr__ is the same as __str__ as it is a valid expression that 240 # could be used to recreate a RangeSet with the same value 241 __repr__ = __str__ 242
243 - def __contains__(self, elem):
244 """ 245 Is element contained in RangeSet? Element can be either a 246 string with optional padding (eg. "002") or an integer 247 (obviously, no padding check is performed for integer). 248 """ 249 # support str type with padding support, eg. `"003" in rangeset' 250 if type(elem) is str: 251 pad = 0 252 if int(elem) != 0: 253 selem = elem.lstrip("0") 254 if len(elem) - len(selem) > 0: 255 pad = len(elem) 256 ielem = int(selem) 257 else: 258 if len(elem) > 1: 259 pad = len(elem) 260 ielem = 0 261 return self._contains_with_padding(ielem, pad) 262 263 # the following cast raises TypeError if elem is not an integer 264 return self._contains(int(elem))
265
266 - def _contains(self, ielem):
267 """ 268 Contains subroutine that takes an integer. 269 """ 270 for rgstart, rgstop, rgstep, rgpad in self._ranges: 271 if ielem >= rgstart and ielem <= rgstop and \ 272 (ielem - rgstart) % rgstep == 0: 273 return True 274 return False
275
276 - def _contains_with_padding(self, ielem, pad):
277 """ 278 Contains subroutine that takes an integer and a padding value. 279 """ 280 for rgstart, rgstop, rgstep, rgpad in self._ranges: 281 # for each ranges, check for inclusion + padding matching 282 # + step matching 283 if ielem >= rgstart and ielem <= rgstop and \ 284 (pad == rgpad or (pad == 0 and len(str(ielem)) >= rgpad)) and \ 285 (ielem - rgstart) % rgstep == 0: 286 return True 287 return False
288
289 - def _binary_sanity_check(self, other):
290 # check that the other argument to a binary operation is also 291 # a RangeSet, raising a TypeError otherwise. 292 if not isinstance(other, RangeSet): 293 raise TypeError, "Binary operation only permitted between RangeSets"
294
295 - def issubset(self, rangeset):
296 """ 297 Report whether another rangeset contains this rangeset. 298 """ 299 self._binary_sanity_check(rangeset) 300 for start, stop, step, pad in self._ranges: 301 for i in range(start, stop + 1, step): 302 if not rangeset._contains_with_padding(i, pad): 303 return False 304 return True
305
306 - def issuperset(self, rangeset):
307 """ 308 Report whether this rangeset contains another rangeset. 309 """ 310 self._binary_sanity_check(rangeset) 311 return rangeset.issubset(self)
312
313 - def __eq__(self, other):
314 """ 315 RangeSet equality comparison. 316 """ 317 # Return NotImplemented instead of raising TypeError, to 318 # indicate that the comparison is not implemented with respect 319 # to the other type (the other comparand then gets a change to 320 # determine the result, then it falls back to object address 321 # comparison). 322 if not isinstance(other, RangeSet): 323 return NotImplemented 324 return len(self) == len(other) and self.issubset(other)
325 326 # inequality comparisons using the is-subset relation 327 __le__ = issubset 328 __ge__ = issuperset 329
330 - def __lt__(self, other):
331 """ 332 x.__lt__(y) <==> x<y 333 """ 334 self._binary_sanity_check(other) 335 return len(self) < len(other) and self.issubset(other)
336
337 - def __gt__(self, other):
338 """ 339 x.__gt__(y) <==> x>y 340 """ 341 self._binary_sanity_check(other) 342 return len(self) > len(other) and self.issuperset(other)
343
344 - def __getitem__(self, i):
345 """ 346 Return the element at index i. 347 """ 348 length = 0 349 for start, stop, step, pad in self._ranges: 350 cnt = (stop - start) / step + 1 351 if i < length + cnt: 352 return start + (i - length) * step 353 length += cnt
354
355 - def __getslice__(self, i, j):
356 """ 357 Return the slice from index i to index j-1. For convenience 358 only, not optimized as of version 1.0. 359 """ 360 return RangeSet.fromlist(list(self)[i:j])
361
362 - def split(self, nbr):
363 """ 364 Split the rangeset into nbr sub-rangeset. Each sub-rangeset will have 365 the same number of element more or less 1. Current rangeset remains 366 unmodified. Returns an iterator. 367 368 >>> RangeSet("1-5").split(3) 369 RangeSet("1-2") 370 RangeSet("3-4") 371 RangeSet("foo5") 372 """ 373 # XXX: This uses the non-optimized __getslice__ method. 374 assert(nbr > 0) 375 376 # We put the same number of element in each sub-nodeset. 377 slice_size = len(self) / nbr 378 left = len(self) % nbr 379 380 begin = 0 381 for i in range(0, nbr): 382 length = slice_size + int(i < left) 383 yield self[begin:begin + length] 384 begin += length
385 386
387 - def _expand(self):
388 """ 389 Expand all items. Internal use. 390 """ 391 items = [] 392 pad = 0 393 for rgstart, rgstop, rgstep, rgpad in self._ranges: 394 items += range(rgstart, rgstop + 1, rgstep) 395 pad = pad or rgpad 396 return items, pad
397
398 - def _fold(self, items, pad):
399 """ 400 Fold items as ranges and group them by step. 401 Return: (ranges, total_length) 402 """ 403 cnt, k, m, istart, rg = 0, -1, 0, None, [] 404 405 # iterate over items and regroup them using steps 406 for i in items: 407 if i > k: 408 cnt += 1 409 if istart is None: 410 istart = k = i 411 elif m > 0: # check step length (m) 412 if m != i - k: 413 if m == 1 or k - istart >= self._autostep * m: 414 # add one range with possible autostep 415 rg.append((istart, k, m, pad)) 416 istart = k = i 417 elif k - istart > m: 418 # stepped without autostep 419 # be careful to let the last one "pending" 420 for j in range(istart, k, m): 421 rg.append((j, j, 1, pad)) 422 istart = k 423 else: 424 rg.append((istart, istart, 1, pad)) 425 istart = k 426 m = i - k 427 k = i 428 429 # finishing 430 if istart is not None: # istart might be 0 431 if m > 0: 432 if m == 1 or k - istart >= self._autostep * m: 433 # add one range with possible autostep 434 rg.append((istart, k, m, pad)) 435 elif k - istart > m: 436 # stepped without autostep 437 for j in range(istart, k + m, m): 438 rg.append((j, j, 1, pad)) 439 else: 440 rg.append((istart, istart, 1, pad)) 441 rg.append((k, k, 1, pad)) 442 else: 443 rg.append((istart, istart, 1, pad)) 444 445 return rg, cnt
446
447 - def add_range(self, start, stop, step=1, pad=0):
448 """ 449 Add a range (start, stop, step and padding length) to RangeSet. 450 """ 451 assert start <= stop, "please provide ordered node index ranges" 452 assert step != None 453 assert step > 0 454 assert pad != None 455 assert pad >= 0 456 assert stop - start < 1e9, "range too large" 457 458 if self._length == 0: 459 # first add optimization 460 stop_adjust = stop - (stop - start) % step 461 if step == 1 or stop_adjust - start >= self._autostep * step: 462 self._ranges = [ (start, stop_adjust, step, pad) ] 463 else: 464 for j in range(start, stop_adjust + step, step): 465 self._ranges.append((j, j, step, pad)) 466 self._length = (stop_adjust - start) / step + 1 467 else: 468 self._ranges, self._length = self._add_range_exfold(start, stop, \ 469 step, pad)
470
471 - def _add_range_exfold(self, start, stop, step, pad):
472 """ 473 Add range expanding then folding all items. 474 """ 475 assert start <= stop, "please provide ordered node index ranges" 476 assert step > 0 477 assert pad != None 478 assert pad >= 0 479 480 items, rgpad = self._expand() 481 items += range(start, stop + 1, step) 482 items.sort() 483 484 return self._fold(items, pad or rgpad)
485
486 - def union(self, other):
487 """ 488 s.union(t) returns a new rangeset with elements from both s and t. 489 """ 490 self_copy = copy.deepcopy(self) 491 self_copy.update(other) 492 return self_copy
493
494 - def __or__(self, other):
495 """ 496 Implements the | operator. So s | t returns a new rangeset with 497 elements from both s and t. 498 """ 499 if not isinstance(other, RangeSet): 500 return NotImplemented 501 return self.union(other)
502
503 - def add(self, elem):
504 """ 505 Add element to RangeSet. 506 """ 507 self.add_range(elem, elem, step=1, pad=0)
508
509 - def update(self, rangeset):
510 """ 511 Update a rangeset with the union of itself and another. 512 """ 513 for start, stop, step, pad in rangeset._ranges: 514 self.add_range(start, stop, step, pad)
515
516 - def clear(self):
517 """ 518 Remove all ranges from this rangeset. 519 """ 520 self._ranges = [] 521 self._length = 0
522
523 - def __ior__(self, other):
524 """ 525 Implements the |= operator. So s |= t returns rangeset s with 526 elements added from t. (Python version 2.5+ required) 527 """ 528 self._binary_sanity_check(other) 529 return self.update(other)
530
531 - def intersection(self, rangeset):
532 """ 533 s.intersection(t) returns a new rangeset with elements common 534 to s and t. 535 """ 536 self_copy = copy.deepcopy(self) 537 self_copy.intersection_update(rangeset) 538 return self_copy
539
540 - def __and__(self, other):
541 """ 542 Implements the & operator. So s & t returns a new rangeset with 543 elements common to s and t. 544 """ 545 if not isinstance(other, RangeSet): 546 return NotImplemented 547 return self.intersection(other)
548
549 - def intersection_update(self, rangeset):
550 """ 551 Intersection with provided RangeSet. 552 """ 553 self._ranges, self._length = self._intersect_exfold(rangeset)
554
555 - def __iand__(self, other):
556 """ 557 Implements the &= operator. So s &= t returns rangeset s keeping 558 only elements also found in t. (Python version 2.5+ required) 559 """ 560 self._binary_sanity_check(other) 561 return self.intersection_update(other)
562
563 - def _intersect_exfold(self, rangeset):
564 """ 565 Calc intersection with the expand/fold method. 566 """ 567 # expand both rangesets 568 items1, pad1 = self._expand() 569 items2, pad2 = rangeset._expand() 570 571 # create a temporary dict with keys from items2 572 iset = dict.fromkeys(items2) 573 574 # fold items that are in both sets 575 return self._fold([e for e in items1 if e in iset], pad1 or pad2)
576
577 - def difference(self, rangeset):
578 """ 579 s.difference(t) returns a new rangeset with elements in s but 580 not in t. 581 in t. 582 """ 583 self_copy = copy.deepcopy(self) 584 self_copy.difference_update(rangeset) 585 return self_copy
586
587 - def __sub__(self, other):
588 """ 589 Implement the - operator. So s - t returns a new rangeset with 590 elements in s but not in t. 591 """ 592 if not isinstance(other, RangeSet): 593 return NotImplemented 594 return self.difference(other)
595
596 - def difference_update(self, rangeset, strict=False):
597 """ 598 s.difference_update(t) returns rangeset s after removing 599 elements found in t. If strict is True, raise KeyError 600 if an element cannot be removed. 601 """ 602 self._ranges, self._length = self._sub_exfold(rangeset, strict)
603
604 - def __isub__(self, other):
605 """ 606 Implement the -= operator. So s -= t returns rangeset s after 607 removing elements found in t. (Python version 2.5+ required) 608 """ 609 self._binary_sanity_check(other) 610 return self.difference_update(other)
611
612 - def remove(self, elem):
613 """ 614 Remove element elem from the RangeSet. Raise KeyError if elem 615 is not contained in the RangeSet. 616 """ 617 items1, pad1 = self._expand() 618 619 try: 620 items1.remove(elem) 621 except ValueError, e: 622 raise KeyError, elem 623 624 self._ranges, self._length = self._fold(items1, pad1)
625
626 - def _sub_exfold(self, rangeset, strict):
627 """ 628 Calc sub/exclusion with the expand/fold method. If strict is 629 True, raise KeyError if the rangeset is not included. 630 """ 631 # expand both rangesets 632 items1, pad1 = self._expand() 633 items2, pad2 = rangeset._expand() 634 635 # create a temporary dict with keys from items2 636 iset = dict.fromkeys(items2) 637 638 if strict: 639 # create a list of remaining items (lst) and update iset 640 lst = [] 641 for e in items1: 642 if e not in iset: 643 lst.append(e) 644 else: 645 del iset[e] 646 647 # if iset is not empty, some elements were not removed 648 if len(iset) > 0: 649 # give the user an indication of the range that cannot 650 # be removed 651 missing = RangeSet() 652 missing._ranges, missing._length = self._fold(iset.keys(), pad2) 653 # repr(missing) is implicit here 654 raise KeyError, missing 655 656 return self._fold(lst, pad1 or pad2) 657 else: 658 # fold items that are in set 1 and not in set 2 659 return self._fold([e for e in items1 if e not in iset], 660 pad1 or pad2)
661
662 - def symmetric_difference(self, other):
663 """ 664 s.symmetric_difference(t) returns the symmetric difference of 665 two rangesets as a new RangeSet. 666 667 (ie. all elements that are in exactly one of the rangesets.) 668 """ 669 self_copy = copy.deepcopy(self) 670 self_copy.symmetric_difference_update(other) 671 return self_copy
672
673 - def __xor__(self, other):
674 """ 675 Implement the ^ operator. So s ^ t returns a new rangeset with 676 elements that are in exactly one of the rangesets. 677 """ 678 if not isinstance(other, RangeSet): 679 return NotImplemented 680 return self.symmetric_difference(other)
681
682 - def symmetric_difference_update(self, rangeset):
683 """ 684 s.symmetric_difference_update(t) returns rangeset s keeping all 685 elements that are in exactly one of the rangesets. 686 """ 687 self._ranges, self._length = self._xor_exfold(rangeset)
688
689 - def __ixor__(self, other):
690 """ 691 Implement the ^= operator. So s ^= t returns rangeset s after 692 keeping all elements that are in exactly one of the rangesets. 693 (Python version 2.5+ required) 694 """ 695 self._binary_sanity_check(other) 696 return self.symmetric_difference_update(other)
697
698 - def _xor_exfold(self, rangeset):
699 """ 700 Calc symmetric difference (xor). 701 """ 702 # expand both rangesets 703 items1, pad1 = self._expand() 704 items2, pad2 = rangeset._expand() 705 706 if pad1 != pad2: 707 raise RangeSetPaddingError('', "%s != %s" % (pad1, pad2)) 708 # same padding, we're clean... 709 710 # create a temporary dicts 711 iset1 = dict.fromkeys(items1) 712 iset2 = dict.fromkeys(items2) 713 714 # keep items that are in one list only 715 allitems = items1 + items2 716 lst = [e for e in allitems if not e in iset1 or not e in iset2] 717 lst.sort() 718 719 return self._fold(lst, pad1)
720
721 722 -def _NodeSetParse(ns, autostep):
723 """ 724 Internal RangeSet generator for NodeSet or nodeset string pattern 725 parsing. 726 """ 727 # is ns a NodeSet instance? 728 if isinstance(ns, NodeSet): 729 for pat, rangeset in ns._patterns.iteritems(): 730 yield pat, rangeset 731 # or is ns a string? 732 elif type(ns) is str: 733 single_node_re = None 734 pat = str(ns) 735 # avoid misformatting 736 if pat.find('%') >= 0: 737 pat = pat.replace('%', '%%') 738 while pat is not None: 739 # Ignore whitespace(s) for convenience 740 pat = pat.lstrip() 741 742 # What's first: a simple node or a pattern of nodes? 743 comma_idx = pat.find(',') 744 bracket_idx = pat.find('[') 745 746 # Check if the comma is after the bracket, or if there 747 # is no comma at all but some brackets. 748 if bracket_idx >= 0 and (comma_idx > bracket_idx or comma_idx < 0): 749 750 # In this case, we have a pattern of potentially several 751 # nodes. 752 753 # Fill prefix, range and suffix from pattern 754 # eg. "forbin[3,4-10]-ilo" -> "forbin", "3,4-10", "-ilo" 755 pfx, sfx = pat.split('[', 1) 756 757 try: 758 rg, sfx = sfx.split(']', 1) 759 except ValueError: 760 raise NodeSetParseError(pat, "missing bracket") 761 762 # Check if we have a next comma-separated node or pattern 763 if sfx.find(',') < 0: 764 pat = None 765 else: 766 sfx, pat = sfx.split(',', 1) 767 768 # Ignore whitespace(s) 769 sfx = sfx.rstrip() 770 771 # pfx + sfx cannot be empty 772 if len(pfx) + len(sfx) == 0: 773 raise NodeSetParseError(pat, "empty node name") 774 775 # Process comma-separated ranges 776 try: 777 rset = RangeSet(rg, autostep) 778 except RangeSetParseError, e: 779 raise NodeSetParseRangeError(e) 780 781 yield "%s%%s%s" % (pfx, sfx), rset 782 else: 783 # In this case, either there is no comma and no bracket, 784 # or the bracket is after the comma, then just return 785 # the node. 786 if comma_idx < 0: 787 node = pat 788 pat = None # break next time 789 else: 790 node, pat = pat.split(',', 1) 791 # Ignore whitespace(s) 792 node = node.strip() 793 794 if len(node) == 0: 795 raise NodeSetParseError(pat, "empty node name") 796 797 # single node parsing 798 if single_node_re is None: 799 single_node_re = re.compile("(\D*)(\d*)(.*)") 800 801 mo = single_node_re.match(node) 802 if not mo: 803 raise NodeSetParseError(pat, "parse error") 804 pfx, idx, sfx = mo.groups() 805 pfx, sfx = pfx or "", sfx or "" 806 807 # pfx+sfx cannot be empty 808 if len(pfx) + len(sfx) == 0: 809 raise NodeSetParseError(pat, "empty node name") 810 811 if idx: 812 try: 813 rset = RangeSet(idx, autostep) 814 except RangeSetParseError, e: 815 raise NodeSetParseRangeError(e) 816 p = "%s%%s%s" % (pfx, sfx) 817 yield p, rset 818 else: 819 # undefined pad means no node index 820 yield pfx, None 821 else: 822 raise NodeSetParseError('', "unsupported input %s" % type(ns))
823
824 825 -class NodeSet(object):
826 """ 827 Iterable class of nodes with node ranges support. 828 829 NodeSet creation examples: 830 nodeset = NodeSet() # empty NodeSet 831 nodeset = NodeSet("clustername3") # contains only clustername3 832 nodeset = NodeSet("clustername[5,10-42]") 833 nodeset = NodeSet("clustername[0-10/2]") 834 nodeset = NodeSet("clustername[0-10/2],othername[7-9,120-300]") 835 836 NodeSet provides methods like update(), intersection_update() or 837 difference_update() methods, which conform to the Python Set API. 838 However, unlike RangeSet or standard Set, NodeSet is somewhat not 839 so strict for convenience, and understands NodeSet instance or 840 NodeSet string as argument. Also, there is no strict definition of 841 one element, for example, it IS allowed to do: 842 nodeset.remove("blue[36-40]"). 843 """
844 - def __init__(self, pattern=None, autostep=None):
845 """ 846 Initialize a NodeSet. If no pattern is specified, an empty 847 NodeSet is created. 848 """ 849 self._autostep = autostep 850 self._length = 0 851 self._patterns = {} 852 if pattern is not None: 853 self.update(pattern)
854 855 @classmethod
856 - def fromlist(cls, nodelist, autostep=None):
857 """ 858 Class method that returns a new NodeSet with nodes from 859 provided list. 860 """ 861 inst = NodeSet(autostep=autostep) 862 for node in nodelist: 863 inst.update(node) 864 return inst
865
866 - def __iter__(self):
867 """ 868 Iterate over concret nodes. 869 """ 870 for pat, rangeset in sorted(self._patterns.iteritems()): 871 if rangeset: 872 for start, stop, step, pad in rangeset._ranges: 873 while start <= stop: 874 yield pat % ("%0*d" % (pad, start)) 875 start += step 876 else: 877 yield pat
878
879 - def __len__(self):
880 """ 881 Get the number of nodes in NodeSet. 882 """ 883 cnt = 0 884 for rangeset in self._patterns.itervalues(): 885 if rangeset: 886 cnt += len(rangeset) 887 else: 888 cnt += 1 889 return cnt
890
891 - def __str__(self):
892 """ 893 Get pdsh-like, ranges-based pattern of node list. 894 """ 895 result = "" 896 for pat, rangeset in sorted(self._patterns.iteritems()): 897 if rangeset: 898 s = str(rangeset) 899 cnt = len(rangeset) 900 if cnt > 1: 901 s = "[" + s + "]" 902 result += pat % s 903 else: 904 result += pat 905 result += "," 906 return result[:-1]
907
908 - def __contains__(self, other):
909 """ 910 Is node contained in NodeSet ? 911 """ 912 return self.issuperset(other)
913
914 - def _binary_sanity_check(self, other):
915 # check that the other argument to a binary operation is also 916 # a NodeSet, raising a TypeError otherwise. 917 if not isinstance(other, NodeSet): 918 raise TypeError, "Binary operation only permitted between NodeSets"
919
920 - def issubset(self, other):
921 """ 922 Report whether another nodeset contains this nodeset. 923 """ 924 binary = None 925 926 # type check is needed for this case... 927 if isinstance(other, NodeSet): 928 binary = other 929 elif type(other) is str: 930 binary = NodeSet(other) 931 else: 932 raise TypeError, \ 933 "Binary operation only permitted between NodeSets or string" 934 935 return binary.issuperset(self)
936
937 - def issuperset(self, other):
938 """ 939 Report whether this nodeset contains another nodeset. 940 """ 941 status = True 942 for pat, erangeset in _NodeSetParse(other, self._autostep): 943 rangeset = self._patterns.get(pat) 944 if rangeset: 945 status = rangeset.issuperset(erangeset) 946 else: 947 # might be an unnumbered node (key in dict but no value) 948 status = self._patterns.has_key(pat) 949 if not status: 950 break 951 return status
952
953 - def __eq__(self, other):
954 """ 955 NodeSet equality comparison. 956 """ 957 # See comment for for RangeSet.__eq__() 958 if not isinstance(other, NodeSet): 959 return NotImplemented 960 return len(self) == len(other) and self.issuperset(other)
961 962 # inequality comparisons using the is-subset relation 963 __le__ = issubset 964 __ge__ = issuperset 965
966 - def __lt__(self, other):
967 """ 968 x.__lt__(y) <==> x<y 969 """ 970 self._binary_sanity_check(other) 971 return len(self) < len(other) and self.issubset(other)
972
973 - def __gt__(self, other):
974 """ 975 x.__gt__(y) <==> x>y 976 """ 977 self._binary_sanity_check(other) 978 return len(self) > len(other) and self.issuperset(other)
979
980 - def __getitem__(self, i):
981 """ 982 Return the node at index i. For convenience only, not 983 optimized as of version 1.0. 984 """ 985 return list(self)[i]
986
987 - def __getslice__(self, i, j):
988 """ 989 Return the slice from index i to index j-1. For convenience 990 only, not optimized as of version 1.0. 991 """ 992 return NodeSet.fromlist(list(self)[i:j])
993
994 - def split(self, nbr):
995 """ 996 Split the nodeset into nbr sub-nodeset. Each sub-nodeset will have the 997 same number of element more or less 1. Current nodeset remains 998 unmodified. 999 1000 >>> NodeSet("foo[1-5]").split(3) 1001 NodeSet("foo[1-2]") 1002 NodeSet("foo[3-4]") 1003 NodeSet("foo5") 1004 """ 1005 # XXX: This uses the non-optimized __getslice__ method. 1006 assert(nbr > 0) 1007 1008 # We put the same number of element in each sub-nodeset. 1009 slice_size = len(self) / nbr 1010 left = len(self) % nbr 1011 1012 begin = 0 1013 for i in range(0, nbr): 1014 length = slice_size + int(i < left) 1015 yield self[begin:begin + length] 1016 begin += length
1017
1018 - def _add_rangeset(self, pat, rangeset):
1019 """ 1020 Add a rangeset to a new or existing pattern. 1021 """ 1022 # get patterns dict entry 1023 pat_e = self._patterns.get(pat) 1024 1025 if pat_e: 1026 # don't play with prefix: if there is a value, there is a 1027 # rangeset. 1028 assert rangeset != None 1029 1030 # add rangeset in corresponding pattern rangeset 1031 pat_e.update(rangeset) 1032 else: 1033 # create new pattern (with possibly rangeset=None) 1034 self._patterns[pat] = copy.copy(rangeset)
1035
1036 - def union(self, other):
1037 """ 1038 s.union(t) returns a new set with elements from both s and t. 1039 """ 1040 self_copy = copy.deepcopy(self) 1041 self_copy.update(other) 1042 return self_copy
1043
1044 - def __or__(self, other):
1045 """ 1046 Implements the | operator. So s | t returns a new nodeset with 1047 elements from both s and t. 1048 """ 1049 if not isinstance(other, NodeSet): 1050 return NotImplemented 1051 return self.union(other)
1052
1053 - def add(self, other):
1054 """ 1055 Add node to NodeSet. 1056 """ 1057 self.update(other)
1058
1059 - def update(self, other):
1060 """ 1061 s.update(t) returns nodeset s with elements added from t. 1062 """ 1063 for pat, rangeset in _NodeSetParse(other, self._autostep): 1064 self._add_rangeset(pat, rangeset)
1065
1066 - def clear(self):
1067 """ 1068 Remove all nodes from this nodeset. 1069 """ 1070 self._patterns.clear() 1071 self._length = 0
1072
1073 - def __ior__(self, other):
1074 """ 1075 Implements the |= operator. So s |= t returns nodeset s with 1076 elements added from t. (Python version 2.5+ required) 1077 """ 1078 self._binary_sanity_check(other) 1079 return self.update(other)
1080
1081 - def intersection(self, other):
1082 """ 1083 s.intersection(t) returns a new set with elements common to s 1084 and t. 1085 """ 1086 self_copy = copy.deepcopy(self) 1087 self_copy.intersection_update(other) 1088 return self_copy
1089
1090 - def __and__(self, other):
1091 """ 1092 Implements the & operator. So s & t returns a new nodeset with 1093 elements common to s and t. 1094 """ 1095 if not isinstance(other, NodeSet): 1096 return NotImplemented 1097 return self.intersection(other)
1098
1099 - def intersection_update(self, other):
1100 """ 1101 s.intersection_update(t) returns nodeset s keeping only 1102 elements also found in t. 1103 """ 1104 if other is self: 1105 return 1106 1107 tmp_ns = NodeSet() 1108 1109 for pat, irangeset in _NodeSetParse(other, self._autostep): 1110 rangeset = self._patterns.get(pat) 1111 if rangeset: 1112 rs = copy.copy(rangeset) 1113 rs.intersection_update(irangeset) 1114 # ignore pattern if empty rangeset 1115 if len(rs) > 0: 1116 tmp_ns._add_rangeset(pat, rs) 1117 elif not irangeset and pat in self._patterns: 1118 # intersect two nodes with no rangeset 1119 tmp_ns._add_rangeset(pat, None) 1120 elif not irangeset and pat in self._patterns: 1121 # intersect two nodes with no rangeset 1122 tmp_ns._add_rangeset(pat, None) 1123 1124 # Substitute 1125 self._patterns = tmp_ns._patterns
1126
1127 - def __iand__(self, other):
1128 """ 1129 Implements the &= operator. So s &= t returns nodeset s keeping 1130 only elements also found in t. (Python version 2.5+ required) 1131 """ 1132 self._binary_sanity_check(other) 1133 return self.intersection_update(other)
1134
1135 - def difference(self, other):
1136 """ 1137 s.difference(t) returns a new NodeSet with elements in s but not 1138 in t. 1139 """ 1140 self_copy = copy.deepcopy(self) 1141 self_copy.difference_update(other) 1142 return self_copy
1143
1144 - def __sub__(self, other):
1145 """ 1146 Implement the - operator. So s - t returns a new nodeset with 1147 elements in s but not in t. 1148 """ 1149 if not isinstance(other, NodeSet): 1150 return NotImplemented 1151 return self.difference(other)
1152
1153 - def difference_update(self, other, strict=False):
1154 """ 1155 s.difference_update(t) returns nodeset s after removing 1156 elements found in t. If strict is True, raise KeyError 1157 if an element cannot be removed. 1158 """ 1159 # the purge of each empty pattern is done afterward to allow self = ns 1160 purge_patterns = [] 1161 1162 # iterate first over exclude nodeset rangesets which is usually smaller 1163 for pat, erangeset in _NodeSetParse(other, self._autostep): 1164 # if pattern is found, deal with it 1165 rangeset = self._patterns.get(pat) 1166 if rangeset: 1167 # sub rangeset, raise KeyError if not found 1168 rangeset.difference_update(erangeset, strict) 1169 1170 # check if no range left and add pattern to purge list 1171 if len(rangeset) == 0: 1172 purge_patterns.append(pat) 1173 else: 1174 # unnumbered node exclusion 1175 if self._patterns.has_key(pat): 1176 purge_patterns.append(pat) 1177 elif strict: 1178 raise KeyError, pat 1179 1180 for pat in purge_patterns: 1181 del self._patterns[pat]
1182
1183 - def __isub__(self, other):
1184 """ 1185 Implement the -= operator. So s -= t returns nodeset s after 1186 removing elements found in t. (Python version 2.5+ required) 1187 """ 1188 self._binary_sanity_check(other) 1189 return self.difference_update(other)
1190
1191 - def remove(self, elem):
1192 """ 1193 Remove element elem from the nodeset. Raise KeyError if elem 1194 is not contained in the nodeset. 1195 """ 1196 self.difference_update(elem, True)
1197
1198 - def symmetric_difference(self, other):
1199 """ 1200 s.symmetric_difference(t) returns the symmetric difference of 1201 two nodesets as a new NodeSet. 1202 1203 (ie. all nodes that are in exactly one of the nodesets.) 1204 """ 1205 self_copy = copy.deepcopy(self) 1206 self_copy.symmetric_difference_update(other) 1207 return self_copy
1208
1209 - def __xor__(self, other):
1210 """ 1211 Implement the ^ operator. So s ^ t returns a new NodeSet with 1212 nodes that are in exactly one of the nodesets. 1213 """ 1214 if not isinstance(other, NodeSet): 1215 return NotImplemented 1216 return self.symmetric_difference(other)
1217
1218 - def symmetric_difference_update(self, other):
1219 """ 1220 s.symmetric_difference_update(t) returns nodeset s keeping all 1221 nodes that are in exactly one of the nodesets. 1222 """ 1223 binary = None 1224 1225 # type check is needed for this case... 1226 if isinstance(other, NodeSet): 1227 binary = other 1228 elif type(other) is str: 1229 binary = NodeSet(other) 1230 else: 1231 raise TypeError, \ 1232 "Binary operation only permitted between NodeSets or string" 1233 1234 purge_patterns = [] 1235 1236 # iterate over our rangesets 1237 for pat, rangeset in self._patterns.iteritems(): 1238 brangeset = binary._patterns.get(pat) 1239 if brangeset: 1240 rangeset.symmetric_difference_update(brangeset) 1241 else: 1242 if binary._patterns.has_key(pat): 1243 purge_patterns.append(pat) 1244 1245 # iterate over binary's rangesets 1246 for pat, brangeset in binary._patterns.iteritems(): 1247 rangeset = self._patterns.get(pat) 1248 if not rangeset and not self._patterns.has_key(pat): 1249 self._add_rangeset(pat, brangeset) 1250 1251 # check for patterns cleanup 1252 for pat, rangeset in self._patterns.iteritems(): 1253 if rangeset is not None and len(rangeset) == 0: 1254 purge_patterns.append(pat) 1255 1256 # cleanup 1257 for pat in purge_patterns: 1258 del self._patterns[pat]
1259
1260 - def __ixor__(self, other):
1261 """ 1262 Implement the ^= operator. So s ^= t returns nodeset s after 1263 keeping all nodes that are in exactly one of the nodesets. 1264 (Python version 2.5+ required) 1265 """ 1266 self._binary_sanity_check(other) 1267 return self.symmetric_difference_update(other)
1268
1269 1270 -def expand(pat):
1271 """ 1272 Commodity function that expands a pdsh-like pattern into a list of 1273 nodes. 1274 """ 1275 return list(NodeSet(pat))
1276
1277 -def fold(pat):
1278 """ 1279 Commodity function that clean dups and fold provided pattern with 1280 ranges and "/step" support. 1281 """ 1282 return str(NodeSet(pat))
1283
1284 1285 # doctest 1286 1287 -def _test():
1288 import doctest 1289 doctest.testmod()
1290 1291 if __name__ == '__main__': 1292 _test() 1293