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 Guillaume Chazarain <guichaz@yahoo.fr>
  18
  19 import os
  20 import stat
  21
  22 from pysize.core import chdir_browsing
  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_subtracted
  26
  27 def _extract_prefix_suffixes(paths):
  28     """['/prefix/suffix1', '/prefix/suffix2', '/prefix/suffix3'] =>
  29         ('/prefix', ['suffix1', 'suffix2', 'suffix3'])"""
  30     prefix_len = os.path.commonprefix(paths).rfind('/') + 1
  31     prefix = paths[0][:prefix_len - 1]
  32     suffixes = [p[prefix_len:] for p in paths]
  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
  43 def _sort_nodes(nodes):
  44     def cmp_fn(n1, n2):
  45         return cmp(n2.size, n1.size) or cmp(n1.get_name(), n2.get_name())
  46     nodes.sort(cmp=cmp_fn)
  47
  48 class _pysize_node(object):
  49     """The parent class of all displayed nodes, as these nodes are displayed on
  50     screen, there should be few instances."""
  51     def __init__(self, parent, basename, options):
  52         self.rectangle = 0, 0, 0, 0
  53         self.parent = parent
  54         self.children = []
  55         self.basename = basename
  56         if basename:
  57             self.size = compute_size.slow(basename, options.cross_device)
  58         else:
  59             self.size = 0
  60
  61     def compute_height(self):
  62         if self.children:
  63             children_height = max([c.compute_height() for c in self.children])
  64             return children_height + 1
  65         return 0
  66
  67     def compute_depth(self):
  68         depth = 0
  69         node = self
  70         while node:
  71             node = node.parent
  72             depth += 1
  73         return depth
  74
  75     def minimum_node_size(self):
  76         res = self.size
  77         for child in self.children:
  78             child_min_node_size = child.minimum_node_size()
  79             res = min(res, child_min_node_size)
  80         return res
  81
  82     def get_dirname(self):
  83         return os.path.dirname(self.get_fullpaths()[0])
  84
  85     def get_useful_size(self):
  86         return self.size
  87
  88     def is_dir(self):
  89         return False
  90
  91     def is_real(self):
  92         """Does the node correspond to a path that actually exists?"""
  93         return True
  94
  95     def get_fullname(self):
  96         fullpaths = self.get_fullpaths()
  97         prefix, suffixes = _extract_prefix_suffixes(fullpaths)
  98         fullname = _join_prefix_suffixes(prefix, suffixes)
  99         return fullname
 100
 101     def get_fullpaths(self):
 102         parent = self.parent
 103         fullpath = self.basename
 104         while parent:
 105             fullpath = os.path.join(parent.basename, fullpath)
 106             parent = parent.parent
 107         return [fullpath]
 108
 109     def get_name(self):
 110         """Return the name that should be displayed for this node."""
 111         return self.basename
 112
 113     def __iter__(self):
 114         """The iterator is a depth first traversal."""
 115         yield self
 116         for child in self.children:
 117             for node in child:
 118                 yield node
 119
 120     def contains_point(self, p):
 121         """Is the point p in the graphical representation of this node?"""
 122         x0, x1, y0, y1 = self.rectangle
 123         return x0 < p.x and p.x < x1 and y0 < p.y and p.y < y1
 124
 125 class _pysize_node_collection(_pysize_node):
 126     """A directory"""
 127     def __init__(self, parent, prefix, children, max_depth, min_size, options):
 128         super(_pysize_node_collection, self).__init__(parent, None, options)
 129         self.basename = prefix
 130         fullpaths = [os.path.join(prefix, p) for p in children]
 131         if max_depth == 0:
 132             self.size = compute_size.slow_sum(fullpaths, options.cross_device)
 133         else:
 134             children_size = 0
 135             remaining_size = 0
 136             remaining_nodes = []
 137             cookie = chdir_browsing.init(prefix)
 138             try:
 139                 for child in children:
 140                     node = create_node(self, child, max_depth - 1, min_size,
 141                                        options)
 142                     if node.is_real():
 143                         self.children.append(node)
 144                         children_size += node.size
 145                     else:
 146                         node.__name = child
 147                         remaining_nodes.append(node)
 148                         remaining_size += node.size
 149
 150                 _sort_nodes(self.children)
 151                 if remaining_size > min_size:
 152                     _sort_nodes(remaining_nodes)
 153                     names = [n.__name for n in remaining_nodes]
 154                     rem = _pysize_node_remaining(self, names, options)
 155                     self.children.append(rem)
 156             finally:
 157                 chdir_browsing.finalize(cookie)
 158             self.size = children_size + remaining_size
 159
 160     def is_real(self):
 161         """This node does not actually exists, it is an aggregate."""
 162         return False
 163
 164 class _pysize_node_forest(_pysize_node_collection):
 165     def __init__(self, parent, children, max_depth, min_size, options):
 166         prefix, suffixes = _extract_prefix_suffixes(children)
 167         super(_pysize_node_forest, self).__init__(parent, prefix, suffixes,
 168                                                   max_depth, min_size, options)
 169         self.basename = prefix
 170         self.forest_paths = suffixes
 171         self.forest_name = _join_prefix_suffixes(prefix, suffixes)
 172
 173     def get_name(self):
 174         return self.forest_name
 175
 176     def get_dirname(self):
 177         return self.basename
 178
 179     def get_fullpaths(self):
 180         fullpaths = self.forest_paths
 181         parent = self
 182         while parent:
 183             fullpaths = [os.path.join(parent.basename, fp) for fp in fullpaths]
 184             parent = parent.parent
 185         return fullpaths
 186
 187 class _pysize_node_dir(_pysize_node_collection):
 188     """A directory"""
 189     def __init__(self, parent, basename, max_depth, min_size, options):
 190         listing = chdir_browsing.listdir(basename, options.cross_device)
 191         super(_pysize_node_dir, self).__init__(parent, basename,
 192                                                listing, max_depth,
 193                                                min_size, options)
 194         self.basename = basename
 195         self.size += os.lstat(basename).st_blocks * 512
 196         # update size in cache, in case files were added/removed
 197         dev_ino = get_dev_ino(basename)
 198         cache_add_dir(dev_ino, self.size + get_subtracted(dev_ino))
 199
 200     def is_dir(self):
 201         return True
 202
 203     def is_real(self):
 204         return True
 205
 206     def get_name(self):
 207         name = self.basename
 208         if name != '/':
 209             name += '/'
 210         return name
 211
 212 class _pysize_node_remaining(_pysize_node_collection):
 213     """The sum of a directory's children that are too small to be drawn."""
 214     def __init__(self, parent, elements, options):
 215         _pysize_node.__init__(self, parent, None, options)
 216         # The parent constructor would visit the files
 217         self.size = compute_size.slow_sum(elements, options.cross_device)
 218         self.remaining_elements = elements
 219         if elements:
 220             median = elements[len(elements) / 2]
 221             self.useful_size = compute_size.slow(median)
 222         else:
 223             self.useful_size = 0
 224
 225     def get_name(self):
 226         return '{' + ','.join(self.remaining_elements) + '}'
 227
 228     def get_fullname(self):
 229         if self.remaining_elements:
 230             return _pysize_node_collection.get_fullname(self)
 231         return '' # This is the initial node
 232
 233     def get_fullpaths(self):
 234         fullpaths = self.remaining_elements
 235         parent = self.parent
 236         while parent:
 237             fullpaths = [os.path.join(parent.basename, fp) for fp in fullpaths]
 238             parent = parent.parent
 239         return fullpaths
 240
 241     def get_useful_size(self):
 242         return self.useful_size
 243
 244 class _pysize_node_file(_pysize_node):
 245     """A file"""
 246     def __init__(self, parent, basename, options):
 247         super(_pysize_node_file, self).__init__(parent, basename, options)
 248
 249 class _pysize_node_hardlink(_pysize_node_file):
 250     """A hardlink, the canonical one, or a link"""
 251     def __init__(self, parent, basename, options):
 252         super(_pysize_node_hardlink, self).__init__(parent, basename, options)
 253
 254 def create_node(parent, what, max_depth, min_size, options):
 255     """Return a pysize_node for parent/basename traversing up to max_depth
 256     levels and only taking into account elements bigger than min_size."""
 257     if not what:
 258         return _pysize_node_remaining(parent, [], options)
 259
 260     if isinstance(what, list):
 261         size = compute_size.slow_sum(what, options.cross_device)
 262         if len(what) == 1:
 263             what = what[0]
 264     else:
 265         size = compute_size.slow(what, options.cross_device)
 266
 267     if size < min_size:
 268         if isinstance(what, str):
 269             what = [what]
 270         node = _pysize_node_remaining(parent, what, options)
 271     elif isinstance(what, list):
 272         node = _pysize_node_forest(parent, what, max_depth, min_size, options)
 273     else:
 274         st = os.lstat(what)
 275         if stat.S_ISDIR(st.st_mode):
 276             node = _pysize_node_dir(parent, what, max_depth, min_size, options)
 277         elif st.st_nlink > 1:
 278             node = _pysize_node_hardlink(parent, what, options)
 279         else:
 280             node = _pysize_node_file(parent, what, options)
 281     return node