]> git.proxmox.com Git - ceph.git/blob - ceph/src/boost/tools/build/test/tree.py
add subtree-ish sources for 12.0.3
[ceph.git] / ceph / src / boost / tools / build / test / tree.py
1 # Copyright 2003 Dave Abrahams
2 # Copyright 2001, 2002 Vladimir Prus
3 # Copyright 2012 Jurko Gospodnetic
4 # Distributed under the Boost Software License, Version 1.0.
5 # (See accompanying file LICENSE_1_0.txt or copy at
6 # http://www.boost.org/LICENSE_1_0.txt)
7
8 ###############################################################################
9 #
10 # Based in part on an old Subversion tree.py source file (tools for comparing
11 # directory trees). See http://subversion.tigris.org for more information.
12 #
13 # Copyright (c) 2001 Sam Tobin-Hochstadt. All rights reserved.
14 #
15 # This software is licensed as described in the file COPYING, which you should
16 # have received as part of this distribution. The terms are also available at
17 # http://subversion.tigris.org/license-1.html. If newer versions of this
18 # license are posted there, you may use a newer version instead, at your
19 # option.
20 #
21 ###############################################################################
22
23 import os
24 import os.path
25 import stat
26 import sys
27
28
29 class TreeNode:
30 """
31 Fundamental data type used to build file system tree structures.
32
33 If CHILDREN is None, then the node represents a file. Otherwise, CHILDREN
34 is a list of the nodes representing that directory's children.
35
36 NAME is simply the name of the file or directory. CONTENTS is a string
37 holding the file's contents (if a file).
38
39 """
40
41 def __init__(self, name, children=None, contents=None):
42 assert children is None or contents is None
43 self.name = name
44 self.mtime = 0
45 self.children = children
46 self.contents = contents
47 self.path = name
48
49 def add_child(self, newchild):
50 assert not self.is_file()
51 for a in self.children:
52 if a.name == newchild.name:
53 if newchild.is_file():
54 a.contents = newchild.contents
55 a.path = os.path.join(self.path, newchild.name)
56 else:
57 for i in newchild.children:
58 a.add_child(i)
59 break
60 else:
61 self.children.append(newchild)
62 newchild.path = os.path.join(self.path, newchild.name)
63
64 def get_child(self, name):
65 """
66 If the given TreeNode directory NODE contains a child named NAME,
67 return the child; else, return None.
68
69 """
70 for n in self.children:
71 if n.name == name:
72 return n
73
74 def is_file(self):
75 return self.children is None
76
77 def pprint(self):
78 print(" * Node name: %s" % self.name)
79 print(" Path: %s" % self.path)
80 print(" Contents: %s" % self.contents)
81 if self.is_file():
82 print(" Children: is a file.")
83 else:
84 print(" Children: %d" % len(self.children))
85
86
87 class TreeDifference:
88 def __init__(self):
89 self.added_files = []
90 self.removed_files = []
91 self.modified_files = []
92 self.touched_files = []
93
94 def append(self, other):
95 self.added_files.extend(other.added_files)
96 self.removed_files.extend(other.removed_files)
97 self.modified_files.extend(other.modified_files)
98 self.touched_files.extend(other.touched_files)
99
100 def ignore_directories(self):
101 """Removes directories from our lists of found differences."""
102 not_dir = lambda x : x[-1] != "/"
103 self.added_files = filter(not_dir, self.added_files)
104 self.removed_files = filter(not_dir, self.removed_files)
105 self.modified_files = filter(not_dir, self.modified_files)
106 self.touched_files = filter(not_dir, self.touched_files)
107
108 def pprint(self, file=sys.stdout):
109 file.write("Added files : %s\n" % self.added_files)
110 file.write("Removed files : %s\n" % self.removed_files)
111 file.write("Modified files: %s\n" % self.modified_files)
112 file.write("Touched files : %s\n" % self.touched_files)
113
114 def empty(self):
115 return not (self.added_files or self.removed_files or
116 self.modified_files or self.touched_files)
117
118
119 def build_tree(path):
120 """
121 Takes PATH as the folder path, walks the file system below that path, and
122 creates a tree structure based on any files and folders found there.
123 Returns the prepared tree structure plus the maximum file modification
124 timestamp under the given folder.
125
126 """
127 return _handle_dir(os.path.normpath(path))
128
129
130 def tree_difference(a, b):
131 """Compare TreeNodes A and B, and create a TreeDifference instance."""
132 return _do_tree_difference(a, b, "", True)
133
134
135 def _do_tree_difference(a, b, parent_path, root=False):
136 """Internal recursive worker function for tree_difference()."""
137
138 # We do not want to list root node names.
139 if root:
140 assert not parent_path
141 assert not a.is_file()
142 assert not b.is_file()
143 full_path = ""
144 else:
145 assert a.name == b.name
146 full_path = parent_path + a.name
147 result = TreeDifference()
148
149 # A and B are both files.
150 if a.is_file() and b.is_file():
151 if a.contents != b.contents:
152 result.modified_files.append(full_path)
153 elif a.mtime != b.mtime:
154 result.touched_files.append(full_path)
155 return result
156
157 # Directory converted to file.
158 if not a.is_file() and b.is_file():
159 result.removed_files.extend(_traverse_tree(a, parent_path))
160 result.added_files.append(full_path)
161
162 # File converted to directory.
163 elif a.is_file() and not b.is_file():
164 result.removed_files.append(full_path)
165 result.added_files.extend(_traverse_tree(b, parent_path))
166
167 # A and B are both directories.
168 else:
169 if full_path:
170 full_path += "/"
171 accounted_for = [] # Children present in both trees.
172 for a_child in a.children:
173 b_child = b.get_child(a_child.name)
174 if b_child:
175 accounted_for.append(b_child)
176 result.append(_do_tree_difference(a_child, b_child, full_path))
177 else:
178 result.removed_files.append(full_path + a_child.name)
179 for b_child in b.children:
180 if b_child not in accounted_for:
181 result.added_files.extend(_traverse_tree(b_child, full_path))
182
183 return result
184
185
186 def _traverse_tree(t, parent_path):
187 """Returns a list of all names in a tree."""
188 assert not parent_path or parent_path[-1] == "/"
189 full_node_name = parent_path + t.name
190 if t.is_file():
191 result = [full_node_name]
192 else:
193 name_prefix = full_node_name + "/"
194 result = [name_prefix]
195 for i in t.children:
196 result.extend(_traverse_tree(i, name_prefix))
197 return result
198
199
200 def _get_text(path):
201 """Return a string with the textual contents of a file at PATH."""
202 fp = open(path, 'r')
203 try:
204 return fp.read()
205 finally:
206 fp.close()
207
208
209 def _handle_dir(path):
210 """
211 Main recursive worker function for build_tree(). Returns a newly created
212 tree node representing the given normalized folder path as well as the
213 maximum file/folder modification time detected under the same path.
214
215 """
216 files = []
217 dirs = []
218 node = TreeNode(os.path.basename(path), children=[])
219 max_mtime = node.mtime = os.stat(path).st_mtime
220
221 # List files & folders.
222 for f in os.listdir(path):
223 f = os.path.join(path, f)
224 if os.path.isdir(f):
225 dirs.append(f)
226 elif os.path.isfile(f):
227 files.append(f)
228
229 # Add a child node for each file.
230 for f in files:
231 fcontents = _get_text(f)
232 new_file_node = TreeNode(os.path.basename(f), contents=fcontents)
233 new_file_node.mtime = os.stat(f).st_mtime
234 max_mtime = max(max_mtime, new_file_node.mtime)
235 node.add_child(new_file_node)
236
237 # For each subdir, create a node, walk its tree, add it as a child.
238 for d in dirs:
239 new_dir_node, new_max_mtime = _handle_dir(d)
240 max_mtime = max(max_mtime, new_max_mtime)
241 node.add_child(new_dir_node)
242
243 return node, max_mtime