Skip to content
Newer
Older
100644 436 lines (339 sloc) 8.85 KB
affb3f0 Added DependencyGrapher.
Brian Ford authored Oct 1, 2009
1 # A simple processor to create a list of dependencies for a given source code
2 # file based on the #include files in the source file.
3 #
4 # The process involves three phases:
5 #
6 # 1. Parsing the source file for all C/C++ preprocessor control directives
7 # (#include, #ifdef, #ifndef, #else, #endif, #define, #undef, #if, #elif)
8 # 2. Executing the tree derived from step 1 in the context of a set of
9 # macro definitions.
10 # 3. Collecting the dependency list for each source file.
11 #
12 # In step 1, the tree resulting from parsing each included file is cached. If
13 # a later file of the same expanded relative path is included, the parse tree
14 # from the cache is returned.
15 #
16 # The system level macro definitions are retrieved using `cpp -dM`. This
17 # system set may be updated with new definitions or removed definitions while
18 # the parse tree is executed.
19
20 require 'set'
21
22 class DependencyGrapher
32cf036 Abstract /dev/null for Windows (luislavena).
Brian Ford authored Oct 13, 2010
23 DEV_NULL = RUBY_PLATFORM =~ /mingw|mswin/ ? 'NUL' : '/dev/null'
24
affb3f0 Added DependencyGrapher.
Brian Ford authored Oct 2, 2009
25 class ExpressionEvaluator
26 def initialize(expression)
27 @expression = expression
28 end
29
30 # TODO: when melbourne is running in MRI, use it to parse
31 # the expression and then evaluate it.
32 def evaluate(defines)
33 @expression == "0" ? false : true
34 end
35 end
36
37 class Node
38 def initialize(parser)
39 @parser = parser
40 end
41
42 def close
43 message = "unbalanced \#endif for #{@parser.stack_top.class} at line #{@parser.line}"
44 raise ParseError, message
45 end
46
47 def add_else
48 message = "invalid \#else for #{@parser.stack_top.class} at line #{@parser.line}"
49 end
50
51 # TODO: remove
52 def execute(defines, node)
53 puts "#execute not implemented for #{self.class}"
54 end
55 end
56
57 module Container
58 attr_accessor :body
59
60 def initialize(parser)
61 super parser
62 @body = []
63 end
64
65 def close
66 @parser.stack_pop
67 end
68
69 def execute_body(defines, node)
70 body.each { |x| x.execute(defines, node) }
71 end
72 end
73
74 module Conditional
75 def initialize(parser)
76 super parser
77 @else = nil
78 end
79
80 def add_else(node)
81 @else = node
82 end
83 end
84
85
86 class SourceFile < Node
87 include Container
88
89 attr_reader :name, :object_name, :includes, :dependencies
90
91 def initialize(name, parser)
92 super parser
93 @name = name
94 @object_name = name.sub(/((c(pp)?)|S)$/, 'o')
95 @includes = []
96 end
97
98 def execute(defines)
99 execute_body defines, self
100 end
101
102 def collect_dependencies
103 set = Set.new
104
105 set << @name
106 @includes.each { |x| x.collect_dependencies(set) }
107
108 @dependencies = set.to_a.sort
109 end
110
111 def print_dependencies(out, max)
112 str = "#{@object_name}:"
113 out.print str
114
115 width = str.size
116 @dependencies.each do |name|
179f7ea Omit drive letter on Windows for dependencies.
Brian Ford authored Oct 18, 2010
117 # Omit drive letter on Windows.
118 name = name[2..-1] if name[1] == ?:
9527512 Emit paths without drive letters in dependency grapher.
Brian Ford authored Oct 18, 2010
119
affb3f0 Added DependencyGrapher.
Brian Ford authored Oct 2, 2009
120 size = name.size + 1
121 if width + size > max
122 width = 0
123 out.print " \\\n "
124 end
125
126 out.print " ", name
127 width += size
128 end
129
130 out.print "\n"
131 end
132 end
133
134 class IncludedFile < Node
135 include Container
136
137 attr_reader :name, :includes
138
139 def self.cache
140 @cache ||= {}
141 end
142
143 def initialize(name, parser)
144 super parser
145 @name = name
146 @includes = []
147 end
148
4e59bdd Report the file has a bad include
Evan Phoenix authored Oct 29, 2009
149 def expand_filename(node)
affb3f0 Added DependencyGrapher.
Brian Ford authored Oct 2, 2009
150 return if File.exist? @name
151
152 @parser.directories.each do |dir|
153 path = File.join dir, @name
154 return @name = path if File.file? path
155 end
156
4e59bdd Report the file has a bad include
Evan Phoenix authored Oct 29, 2009
157 raise Errno::ENOENT, "unable to find file to include: #{@name} from #{node.name}"
affb3f0 Added DependencyGrapher.
Brian Ford authored Oct 2, 2009
158 end
159
160 def execute(defines, node)
4e59bdd Report the file has a bad include
Evan Phoenix authored Oct 29, 2009
161 expand_filename(node)
affb3f0 Added DependencyGrapher.
Brian Ford authored Oct 2, 2009
162
163 if cached = self.class.cache[@name.to_sym]
164 @body = cached.body
165 else
166 parser = FileParser.new self, @parser.directories
167 parser.parse_file @name
168 self.class.cache[@name.to_sym] = self
169 end
170
171 execute_body defines, self
172
173 node.includes << self
174 end
175
176 def collect_dependencies(set)
177 return if set.include? @name
178
179 set << @name
180 @includes.each { |x| x.collect_dependencies(set) }
181 end
182 end
183
184 class IfDefined < Node
185 include Conditional, Container
186
187 def initialize(macro, parser)
188 super parser
189 @macro = macro.strip
190 end
191
192 def execute(defines, node)
193 if defines.key? @macro
194 execute_body defines, node
195 elsif @else
196 @else.execute(defines, node)
197 end
198 end
199 end
200
201 class IfNotDefined < Node
202 include Conditional, Container
203
204 def initialize(macro, parser)
205 super parser
206 @macro = macro.strip
207 end
208
209 def execute(defines, node)
210 if !defines.key? @macro
211 execute_body defines, node
212 elsif @else
213 @else.execute(defines, node)
214 end
215 end
216 end
217
218 class If < Node
219 include Conditional, Container
220
221 def initialize(expression, parser)
222 super parser
223 @value = nil
224 @expression = expression.strip
225 end
226
227 def execute(defines, node)
228 @value = ExpressionEvaluator.new(@expression).evaluate defines
229
230 if @value
231 execute_body(defines, node)
232 elsif @else
233 @else.execute(defines, node)
234 end
235 end
236 end
237
238 class Else < Node
239 include Container
240
241 def execute(defines, node)
242 execute_body defines, node
243 end
244 end
245
246 class ElseIf < If; end
247
248 class Define < Node
249 def initialize(macro, parser)
250 super parser
251
252 macro.strip!
253 if index = macro.index(" ")
254 @name = macro[0..index-1]
255 @value = macro[index+1..-1]
256 @name, @value = macro.strip.split
257 else
258 @name = macro
259 @value = "1"
260 end
261 end
262
263 def execute(defines, node)
264 defines[@name] = @value
265 end
266 end
267
268 class Undefine < Node
269 def initialize(macro, parser)
270 super parser
271 @macro = macro.strip
272 end
273
274 def execute(defines, node)
275 defines.delete @macro
276 end
277 end
278
279 class ParseError < Exception; end
280
281 # Parses a file for all preprocessor control directives into a tree of Node
282 # objects. The parser can operate on a file or an array of lines.
283 class FileParser
284 attr_reader :line, :directories
285
286 def initialize(root, directories)
287 @stack = [root]
288 @directories = directories
289 end
290
291 # Parser operations
292
293 def add_body(node)
294 @stack.last.body << node
295 end
296
297 def add_else(node)
298 @stack.last.add_else node
299 end
300
301 def stack_push(node)
302 @stack.push node
303 end
304
305 def stack_pop
306 @stack.pop
307 end
308
309 def stack_top
310 @stack.last
311 end
312
313 def close
314 @stack.last.close
315 end
316
317 # Events
318
319 def process_include(name)
320 # We do not process any <files>. This could be enabled as
321 # an option, but we don't need it or want it now.
322 name =~ /\s*"([^"]+)".*$/
323 return unless $1
324
325 node = IncludedFile.new $1, self
326 add_body node
327 end
328
329 def process_ifdef(macro)
330 node = IfDefined.new macro, self
331 add_body node
332 stack_push node
333 end
334
335 def process_ifndef(macro)
336 node = IfNotDefined.new macro, self
337 add_body node
338 stack_push node
339 end
340
341 def process_endif(rest)
342 close
343 end
344
345 def process_else(rest)
346 node = Else.new self
347 add_else node
348 end
349
350 def process_define(macro)
351 node = Define.new macro, self
352 add_body node
353 end
354
355 def process_undef(macro)
356 node = Undefine.new macro, self
357 add_body node
358 end
359
360 def process_if(expression)
361 node = If.new expression, self
362 add_body node
363 stack_push node
364 end
365
366 def process_elif(expression)
367 node = ElseIf.new expression, self
368 add_else node
369 add_body node
370 stack_push node
371 end
372
373 # Parse methods
374
375 def parse_file(name)
376 parse IO.readlines(name)
377 end
378
379 def parse(lines)
380 @line = 0
381
382 lines.each do |line|
383 @line += 1
384 m = line.match(/^\s*#(include|ifdef|ifndef|endif|else|define|undef|if|elif)(.*)$/)
385
386 # TODO: continue reading if line ends in \
387
388 send :"process_#{m[1]}", m[2] if m
389 end
390 end
391 end
392
393 attr_accessor :file_names, :directories, :defines, :system_defines
394 attr_reader :sources
395
396 def initialize(files, directories=[], defines=nil)
397 @file_names = files
398 @directories = directories
399 @defines = defines
400
401 @system_defines = {}
402 @sources = []
403 end
404
405 def get_system_defines
32cf036 Abstract /dev/null for Windows (luislavena).
Brian Ford authored Oct 14, 2010
406 lines = `cpp -dM #{@defines} #{DEV_NULL}`.split("\n")
affb3f0 Added DependencyGrapher.
Brian Ford authored Oct 2, 2009
407
408 source = SourceFile.new "sytem_defines", self
409 parser = FileParser.new source, @directories
410 parser.parse lines
411
412 source.execute @system_defines
413 end
414
415 def process
416 get_system_defines
417
418 @file_names.each do |name|
419 source = SourceFile.new name, self
420 parser = FileParser.new source, @directories
421
422 parser.parse_file name
423 source.execute @system_defines.dup
424 source.collect_dependencies
425
426 @sources << source
427 end
428 end
429
430 def print_dependencies(out, max=72)
431 @sources.each do |source|
432 source.print_dependencies out, max
433 end
434 end
435 end
Something went wrong with that request. Please try again.