pysize/core/pysize_fs_node.py

   1 # This program is free software; you can redistribute it and/or modify
   2 # it under the terms of the GNU General Public License as published by
   3 # the Free Software Foundation; either version 2 of the License, or
   4 # (at your option) any later version.
   5 #
   6 # This program is distributed in the hope that it will be useful,
   7 # but WITHOUT ANY WARRANTY; without even the implied warranty of
   8 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   9 # GNU Library General Public License for more details.
  10 #
  11 # You should have received a copy of the GNU General Public License
  12 # along with this program; if not, write to the Free Software
  13 # Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  14 #
  15 # See the COPYING file for license information.
  16 #
  17 # Copyright (c) 2006, 2007, 2008  Guillaume Chazarain <guichaz@gmail.com>
  18
  19 import os
  20 import stat
  21
  22 from pysize.core.browsing import browsedir
  23 from pysize.core import compute_size
  24 from pysize.core.pysize_global_fs_cache import get_dev_ino, cache_add_dir
  25 from pysize.core.deletion import get_deletion_info, DELETED
  26
  27 def _extract_prefix_suffixes(fullpaths):
  28     """['/prefix/suffix1', '/prefix/suffix2', '/prefix/suffix3'] =>
  29         ('/prefix', ['suffix1', 'suffix2', 'suffix3'])"""
  30     prefix_len = os.path.commonprefix(fullpaths).rfind('/') + 1
  31     prefix = fullpaths[0][:prefix_len - 1] or '/'
  32     suffixes = [p[prefix_len:] for p in fullpaths]
  33     return prefix, suffixes
  34
  35 def _join_prefix_suffixes(prefix, suffixes):
  36     if len(suffixes) == 1:
  37         suffix = suffixes[0]
  38     else:
  39         suffix = '{' + ','.join(suffixes) + '}'
  40     return os.path.join(prefix, suffix)
  41
  42 def pretty_paths(fullpaths):
  43     prefix, suffixes = _extract_prefix_suffixes(fullpaths)
  44     return _join_prefix_suffixes(prefix, suffixes)
  45
  46 class _pysize_node(object):
  47     """The parent class of all displayed nodes, as these nodes are displayed on
  48     screen, there should be few instances."""
  49     def __init__(self, parent, basename, options):
  50         self.rectangle = None
  51         self.parent = parent
  52         self.children = []
  53         self.basename = basename
  54         if basename:
  55             self.size = compute_size.slow(self.get_fullname(),
  56                                           options.cross_device)
  57         else:
  58             self.size = 0
  59
  60     def compute_height(self):
  61         if self.children:
  62             children_height = max([c.compute_height() for c in self.children])
  63             return children_height + 1
  64         return 0
  65
  66     def compute_depth(self):
  67         depth = 0
  68         node = self
  69         while node:
  70             node = node.parent
  71             depth += 1
  72         return depth
  73
  74     def minimum_node_size(self):
  75         res = self.size
  76         for child in self.children:
  77             child_min_node_size = child.minimum_node_size()
  78             res = min(res, child_min_node_size)
  79         return res
  80
  81     def get_dirname(self):
  82         return os.path.dirname(self.get_fullpaths()[0])
  83
  84     def is_dir(self):
  85         return False
  86
  87     def is_real(self):
  88         """Does the node correspond to a path that actually exists?"""
  89         return True
  90
  91     def get_fullname(self):
  92         return pretty_paths(self.get_fullpaths())
  93
  94     def get_fullpaths(self):
  95         parent = self.parent
  96         fullpath = self.basename
  97         while parent:
  98             fullpath = os.path.join(parent.basename, fullpath)
  99             parent = parent.parent
 100         return [fullpath]
 101
 102     def get_name(self):
 103         """Return the name that should be displayed for this node."""
 104         return self.basename
 105
 106     def __iter__(self):
 107         """The iterator is a depth first traversal."""
 108         yield self
 109         for child in self.children:
 110             for node in child:
 111                 yield node
 112
 113     def contains_point(self, p):
 114         """Is the point p in the graphical representation of this node?"""
 115         if not self.rectangle:
 116             return False
 117         x0, x1, y0, y1 = self.rectangle
 118         return x0 < p.x and p.x < x1 and y0 < p.y and p.y < y1
 119
 120 class _pysize_node_collection(_pysize_node):
 121     """A directory"""
 122     def __init__(self, parent, prefix_basename, children_fullpaths, max_depth,
 123                  min_size, options):
 124         _pysize_node.__init__(self, parent, None, options)
 125         self.basename = prefix_basename
 126         if max_depth == 0:
 127             self.size = compute_size.slow_sum(children_fullpaths,
 128                                               options.cross_device)
 129         else:
 130             children_size = 0
 131             remaining_fullpaths = []
 132             remaining_size = 0
 133             for child_fullpath in children_fullpaths:
 134                 child_basename = os.path.basename(child_fullpath)
 135                 try:
 136                     node = create_node(self, [child_basename], [child_fullpath],
 137                                        max_depth - 1, min_size, options)
 138                 except OSError:
 139                     print child_fullpath, 'disappeared'
 140                     continue
 141                 if node.is_real():
 142                     self.children.append(node)
 143                     children_size += node.size
 144                 else:
 145                     remaining_fullpaths.append(child_fullpath)
 146                     remaining_size += node.size
 147
 148             self.children.sort(cmp=lambda n1, n2: cmp(n2.size, n1.size) or
 149                                               cmp(n1.get_name(), n2.get_name()))
 150             if remaining_size > min_size:
 151                 rem = _pysize_node_remaining(self, remaining_fullpaths, options)
 152                 self.children.append(rem)
 153             self.size = children_size + remaining_size
 154
 155     def is_real(self):
 156         """This node does not actually exists, it is an aggregate."""
 157         return False
 158
 159 class _pysize_node_forest(_pysize_node_collection):
 160     def __init__(self, parent, children_fullpaths, max_depth, min_size,
 161                  options):
 162         assert parent is None
 163         prefix, suffixes = _extract_prefix_suffixes(children_fullpaths)
 164         self.trees = suffixes
 165         _pysize_node_collection.__init__(self, parent, prefix,
 166                                          children_fullpaths, max_depth,
 167                                          min_size, options)
 168
 169     def get_name(self):
 170         return _join_prefix_suffixes(self.basename, self.trees)
 171
 172     def get_fullpaths(self):
 173         return [self.basename + '/' + t for t in self.trees]
 174
 175     def get_dirname(self):
 176         return self.basename
 177
 178 class _pysize_node_dir(_pysize_node_collection):
 179     """A directory"""
 180     def __init__(self, parent, basename, st, max_depth, min_size, options):
 181         # Needed for get_fullname() before _pysize_node_collection.__init__()
 182         self.parent = parent
 183         self.basename = basename
 184         fullpath = self.get_fullname()
 185         listing = browsedir(fullpath, options.cross_device)
 186         _pysize_node_collection.__init__(self, parent, basename, listing,
 187                                          max_depth, min_size, options)
 188         self.basename = basename
 189         self.size += st.st_blocks * 512
 190         # update size in cache, in case files were added/removed
 191         deletion_info = get_deletion_info(fullpath)
 192         if deletion_info is not DELETED:
 193             dev_ino = (st.st_dev, st.st_ino)
 194             cache_add_dir(dev_ino, self.size + deletion_info)
 195
 196     def is_dir(self):
 197         return True
 198
 199     def is_real(self):
 200         return True
 201
 202     def get_name(self):
 203         name = self.basename
 204         if name != '/':
 205             name += '/'
 206         return name
 207
 208 class _pysize_node_remaining(_pysize_node_collection):
 209     """The sum of a directory's children that are too small to be drawn."""
 210     def __init__(self, parent, fullpaths, options):
 211         _pysize_node.__init__(self, parent, None, options)
 212         # The parent constructor would visit the files
 213         self.size = compute_size.slow_sum(fullpaths, options.cross_device)
 214         size_basename = [(compute_size.slow(fp), os.path.basename(fp)) for
 215                                                                 fp in fullpaths]
 216         size_basename.sort(key=lambda s_b: s_b[0], reverse=True)
 217         self.remaining_elements = [b for s, b in size_basename]
 218
 219     def get_name(self):
 220         return '{' + ','.join(self.remaining_elements) + '}'
 221
 222     def get_fullname(self):
 223         if self.remaining_elements:
 224             return _pysize_node_collection.get_fullname(self)
 225         return '' # This is the initial node
 226
 227     def get_fullpaths(self):
 228         fullpaths = self.remaining_elements
 229         parent = self.parent
 230         while parent:
 231             fullpaths = [os.path.join(parent.basename, fp) for fp in fullpaths]
 232             parent = parent.parent
 233         return fullpaths
 234
 235 class _pysize_node_file(_pysize_node):
 236     """A file"""
 237     def __init__(self, parent, basename, options):
 238         _pysize_node.__init__(self, parent, basename, options)
 239
 240 class _pysize_node_hardlink(_pysize_node_file):
 241     """A hardlink, the canonical one, or a link"""
 242     def __init__(self, parent, basename, options):
 243         _pysize_node_file.__init__(self, parent, basename, options)
 244
 245 def create_node(parent, basenames, fullpaths, max_depth, min_size, options):
 246     """Return a pysize_node for parent/basename traversing up to max_depth
 247     levels and only taking into account elements bigger than min_size."""
 248     if not basenames:
 249         return _pysize_node_remaining(parent, [], options)
 250
 251     assert len(basenames) == len(fullpaths)
 252     size = compute_size.slow_sum(fullpaths, options.cross_device)
 253     if size < min_size:
 254         node = _pysize_node_remaining(parent, fullpaths, options)
 255     elif len(basenames) > 1:
 256         node = _pysize_node_forest(parent, basenames, max_depth, min_size,
 257                                    options)
 258     else:
 259         try:
 260             st = os.lstat(fullpaths[0])
 261         except OSError, e:
 262             print e
 263             return _pysize_node_remaining(parent, [], options)
 264         if stat.S_ISDIR(st.st_mode):
 265             node = _pysize_node_dir(parent, basenames[0], st, max_depth,
 266                                     min_size, options)
 267         elif st.st_nlink > 1:
 268             node = _pysize_node_hardlink(parent, basenames[0], options)
 269         else:
 270             node = _pysize_node_file(parent, basenames[0], options)
 271     return node