Source Code for Module ClusterShell.MsgTree

  1  # 
  2  # Copyright CEA/DAM/DIF (2007, 2008, 2009) 
  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: MsgTree.py 271 2010-06-08 14:29:04Z st-cea $ 
 34   
 35  """ 
 36  MsgTree 
 37   
 38  ClusterShell message tree module. The purpose of MsgTree is to 
 39  provide a shared message tree for storing message lines received 
 40  from ClusterShell Workers (for example, from remote cluster 
 41  commands). It should be efficient, in term of compute power and memory 
 42  consumption, especially when remote messages are the same. 
 43  """ 
 44   
 45  from itertools import ifilterfalse, imap 
 46  from operator import itemgetter 
 47   
 48   
 49 -class MsgTreeElem(object): 
 50      """ 
 51      Class representing an element of the MsgTree and its associated 
 52      message. Object of this class are returned by the various MsgTree 
 53      methods like messages() or walk(). The object can then be used as 
 54      an iterator over the message lines or casted into a string. 
 55      """ 
 56 -    def __init__(self, msgline=None, parent=None): 
 57          """ 
 58          Initialize message tree element. 
 59          """ 
 60          # structure 
 61          self.parent = parent 
 62          self.children = {} 
 63          # content 
 64          self.msgline = msgline 
 65          self.keys = None 
 66      
 67 -    def __len__(self): 
 68          """Length of whole message string.""" 
 69          return len(str(self)) 
 70   
 71 -    def __eq__(self, other): 
 72          """Comparison method compares whole message strings.""" 
 73          return str(self) == str(other) 
 74   
 75 -    def _shift(self, key, target_elem): 
 76          """Shift one of our key to specified target element.""" 
 77          if self.keys and len(self.keys) == 1: 
 78              shifting = self.keys 
 79              self.keys = None 
 80          else: 
 81              shifting = set([ key ]) 
 82              if self.keys: 
 83                  self.keys.difference_update(shifting) 
 84   
 85          if not target_elem.keys: 
 86              target_elem.keys = shifting 
 87          else: 
 88              target_elem.keys.update(shifting) 
 89   
 90          return target_elem 
 91   
 92 -    def __getitem__(self, i): 
 93          return list(self.lines())[i] 
 94   
 95 -    def __iter__(self): 
 96          """Iterate over message lines starting from this tree element.""" 
 97          # no msgline in root element 
 98          if self.msgline is None: 
 99              return 
100          # trace the message path 
101          path = [self.msgline] 
102          parent = self.parent 
103          while parent.msgline is not None: 
104              path.append(parent.msgline) 
105              parent = parent.parent 
106          # rewind path 
107          while path: 
108              yield path.pop() 
109   
110 -    def lines(self): 
111          """ 
112          Get the whole message lines iterator from this tree element. 
113          """ 
114          return iter(self) 
115   
116      splitlines = lines 
117   
118 -    def message(self): 
119          """ 
120          Get the whole message buffer from this tree element. 
121          """ 
122          # concat buffers 
123          return '\n'.join(self.lines()) 
124   
125      __str__ = message 
126   
127 -    def append(self, key, msgline): 
128          """ 
129          A new message line is coming, append it to the tree element 
130          with associated source key. Called by MsgTree.add(). 
131          Return corresponding newly created MsgTreeElem. 
132          """ 
133          # create new child element and shift down the key 
134          return self._shift(key, self.children.setdefault(msgline, \ 
135                                          self.__class__(msgline, self))) 
136   
137   
138 -class MsgTree(object): 
139      """ 
140      A MsgTree object maps key objects to multi-lines messages. 
141      MsgTree's are mutable objects. Keys are almost arbitrary values 
142      (must be hashable). Message lines are organized as a tree 
143      internally. MsgTree provides low memory consumption especially 
144      on a cluster when all nodes return similar messages. Also, 
145      the gathering of messages is done automatically. 
146      """ 
147   
148 -    def __init__(self): 
149          # root element of MsgTree 
150          self._root = MsgTreeElem() 
151          # dict of keys to MsgTreeElem 
152          self._keys = {} 
153   
154 -    def clear(self): 
155          """Remove all items from the MsgTree.""" 
156          self._root = MsgTreeElem() 
157          self._keys.clear() 
158   
159 -    def __len__(self): 
160          """Return the number of keys contained in the MsgTree.""" 
161          return len(self._keys) 
162   
163 -    def __getitem__(self, key): 
164          """Return the message of MsgTree with specified key. Raises a 
165          KeyError if key is not in the MsgTree.""" 
166          return self._keys[key] 
167   
168 -    def get(self, key, default=None): 
169          """ 
170          Return the message for key if key is in the MsgTree, else default. 
171          If default is not given, it defaults to None, so that this method 
172          never raises a KeyError. 
173          """ 
174          return self._keys.get(key, default) 
175   
176 -    def add(self, key, msgline): 
177          """ 
178          Add a message line associated with the given key to the MsgTree. 
179          """ 
180          # try to get current element in MsgTree for the given key, 
181          # defaulting to the root element 
182          e_msg = self._keys.get(key, self._root) 
183   
184          # add child msg and update keys dict 
185          self._keys[key] = e_msg.append(key, msgline) 
186   
187 -    def keys(self): 
188          """Return an iterator over MsgTree's keys.""" 
189          return self._keys.iterkeys() 
190   
191      __iter__ = keys 
192       
193 -    def messages(self, match=None): 
194          """Return an iterator over MsgTree's messages.""" 
195          return imap(itemgetter(0), self.walk(match)) 
196       
197 -    def items(self, match=None, mapper=None): 
198          """ 
199          Return (key, message) for each key of the MsgTree. 
200          """ 
201          if mapper is None: 
202              mapper = lambda k: k 
203          for key, elem in self._keys.iteritems(): 
204              if match is None or match(key): 
205                  yield mapper(key), elem 
206   
207 -    def _depth(self): 
208          """ 
209          Return the depth of the MsgTree, ie. the max number of lines 
210          per message. Added for debugging. 
211          """ 
212          depth = 0 
213          # stack of (element, depth) tuples used to walk the tree 
214          estack = [ (self._root, depth) ] 
215   
216          while estack: 
217              elem, edepth = estack.pop() 
218              if len(elem.children) > 0: 
219                  estack += [(v, edepth + 1) for v in elem.children.values()] 
220              depth = max(depth, edepth) 
221           
222          return depth 
223   
224 -    def walk(self, match=None, mapper=None): 
225          """ 
226          Walk the tree. Optionally filter keys on match parameter, 
227          and optionally map resulting keys with mapper function. 
228          Return an iterator of (message, keys) tuples for each 
229          different message in the tree. 
230          """ 
231          # stack of elements used to walk the tree (depth-first) 
232          estack = [ self._root ] 
233   
234          while estack: 
235              elem = estack.pop() 
236              if len(elem.children) > 0: 
237                  estack += elem.children.values() 
238              if elem.keys: # has some keys 
239                  mkeys = filter(match, elem.keys) 
240                  if len(mkeys): 
241                      yield elem, map(mapper, mkeys) 
242   
243 -    def remove(self, match=None): 
244          """ 
245          Modify the tree by removing any matching key references from the 
246          messages tree. 
247   
248          Example of use: 
249              >>> msgtree.remove(lambda k: k > 3) 
250          """ 
251          estack = [ self._root ] 
252   
253          # walk the tree to keep only matching keys 
254          while estack: 
255              elem = estack.pop() 
256              if len(elem.children) > 0: 
257                  estack += elem.children.values() 
258              if elem.keys: # has some keys 
259                  elem.keys = set(ifilterfalse(match, elem.keys)) 
260   
261          # also remove key(s) from known keys dict 
262          for key in filter(match, self._keys.keys()): 
263              del self._keys[key] 
264