1#! /usr/bin/python2
2import os
3import sys
4import shlex
5import re
6
7from headerutils import *
8import Queue
9
10file_list = list ()
11usage = False
12
13ignore_conditional = False
14
15order = [
16  "system.h",
17  "coretypes.h",
18  "backend.h",
19  "target.h",
20  "rtl.h",
21  "c-family/c-target.h",
22  "c-family/c-target-def.h",
23  "tree.h",
24  "cp/cp-tree.h",
25  "c-family/c-common.h",  # these must come before diagnostic.h
26  "c/c-tree.h",
27  "fortran/gfortran.h",
28  "gimple.h",
29  "cfghooks.h",
30  "df.h",
31  "tm_p.h",
32  "gimple-iterators.h",
33  "ssa.h",
34  "expmed.h",
35  "optabs.h",
36  "regs.h",
37  "ira.h",
38  "ira-int.h",
39  "gimple-streamer.h"
40
41]
42
43exclude_special = [  "bversion.h", "obstack.h", "insn-codes.h", "hooks.h" ]
44
45# includes is a dictionary indexed by a header files basename.
46# it consists of a 2 element tuple:
47# [0] - Name of header file which included this header.
48# [1] - vector of header file names included by this file.
49
50includes = { }
51
52# when a header is included multiple times, indexing this dictionary will
53# return a vector of all the headers which included it.
54dups = { }
55
56# When creating the master list, do not descend into these files for what 
57# they include. Simply put the file itself in the list.  This is primarily
58# required because the front end files inlcude orders tend to be at odds with
59# the order of middle end files, and its impossible to synchronize them.\
60# They are ordered such that everything resolves properly.
61exclude_processing = [ "tree-vectorizer.h" , "c-target.h", "c-target-def.h", "cp-tree.h", "c-common.h", "c-tree.h", "gfortran.h" ]
62
63master_list = list ()
64# where include file comes from in src
65h_from = { }
66
67# create the master ordering list... this is the desired order of headers
68def create_master_list (fn, verbose):
69  if fn not in exclude_processing:
70    for x in includes[fn][1]:
71      create_master_list (x, verbose)
72  if not fn in master_list:
73    # Don't put diagnostic*.h into the ordering list. It is special since
74    # various front ends have to set GCC_DIAG_STYLE before including it.
75    # for each file, we'll tailor where it belongs by looking at the include
76    # list and determine its position appropriately.
77    if fn != "diagnostic.h" and fn != "diagnostic-core.h":
78      master_list.append (fn)
79      if (verbose):
80        print fn + "      included by: " + includes[fn][0]
81
82
83
84def print_dups ():
85  if dups:
86    print "\nduplicated includes"
87  for i in dups:
88    string =  "dup : " + i + " : "
89    string += includes[i][0] 
90    for i2 in dups[i]:
91      string += ", "+i2
92    print string
93
94
95def process_known_dups ():
96  # rtl.h gets tagged as a duplicate includer for all of coretypes.h, but that
97  # is really for only generator files
98  rtl_remove = includes["coretypes.h"][1] + ["statistics.h", "vec.h"]
99  if dups:
100    for i in rtl_remove:
101      if dups[i] and "rtl.h" in dups[i]:
102        dups[i].remove("rtl.h")
103      if not dups[i]:
104        dups.pop (i, None)
105
106  # make sure diagnostic.h is the owner of diagnostic-core.h
107  if includes["diagnostic-core.h"][0] != "diagnostic.h":
108    dups["diagnostic-core.h"].append (includes["diagnostic-core.h"][0])
109    includes["diagnostic-core.h"] = ("diagnostic.h", includes["diagnostic-core.h"][1])
110
111# This function scans back thorugh the list of headers which included other
112# headers to determine what file in HEADER_LIST brought 'HEADER' in.
113def indirectly_included (header, header_list):
114  nm = os.path.basename (header)
115  while nm and includes.get(nm):
116    if includes[nm][0] in header_list:
117      return includes[nm][0]
118    nm = includes[nm][0]
119
120  # diagnostic.h and diagnostic-core.h may not show up because we removed them
121  # from the header list to manually position in an appropriate place. They have
122  # specific requirements that they need to occur after certain FE files which
123  # may overide the definition of GCC_DIAG_STYLE.
124  # Check the dup list for whete they may have been included from and return
125  # that header.
126  if header == "diagnostic-core.h":
127    if dups.get("diagnostic-core.h"):
128      for f in dups["diagnostic-core.h"]:
129        if f in header_list:
130          return f
131    else:
132      if header in header_list:
133        return header
134    # Now check if diagnostics is included indirectly anywhere
135    header = "diagnostic.h"
136
137  if header == "diagnostic.h":
138    if dups.get("diagnostic.h"):
139      for f in dups["diagnostic.h"]:
140        if f in header_list:
141          return f
142    else:
143      if header in header_list:
144        return header 
145
146  return ""
147
148
149# This function will take a list of headers from a source file and return 
150# the desired new new order of the canonical headers in DESIRED_ORDER. 
151def get_new_order (src_h, desired_order):
152  new_order = list ()
153  for h in desired_order:
154    if h in master_list:
155      # Create the list of nested headers which included this file.
156      iclist = list ()
157      ib = includes[h][0]
158      while ib:
159        iclist.insert(0, ib)
160        ib = includes[ib][0]
161      if iclist:
162        for x in iclist:
163          # If header is in the source code, and we are allowed to look inside
164          if x in src_h and x not in exclude_processing:
165            if x not in new_order and x[:10] != "diagnostic" and h not in exclude_special:
166              new_order.append (x)
167              break;
168      else:
169        if h not in new_order:
170          new_order.append (h)
171
172  f = ""
173  if "diagnostic.h" in src_h:
174    f = "diagnostic.h"
175  elif "diagnostic-core.h" in src_h:
176    f = "diagnostic-core.h"
177
178 
179  # If either diagnostic header was directly included in the main file, check to
180  # see if its already included indirectly, or whether we need to add it to the
181  # end of the canonically orders headers.
182  if f:
183    ii = indirectly_included (f, src_h)
184    if not ii or ii == f:
185      new_order.append (f)
186
187  return new_order
188        
189    
190
191# stack of files to process
192process_stack = list ()
193
194def process_one (info):
195  i = info[0]
196  owner = info[1]
197  name = os.path.basename(i)
198  if os.path.exists (i):
199    if includes.get(name) == None:
200      l = find_unique_include_list (i)
201      # create a list which has just basenames in it
202      new_list = list ()
203      for x in l:
204        new_list.append (os.path.basename (x))
205        process_stack.append((x, name))
206      includes[name] = (owner, new_list)
207    elif owner:
208      if dups.get(name) == None:
209        dups[name] = [ owner ]
210      else:
211        dups[name].append (owner)
212  else:
213    # seed tm.h with options.h since it is a build file and won't be seen. 
214    if not includes.get(name):
215      if name == "tm.h":
216        includes[name] = (owner, [ "options.h" ])
217        includes["options.h"] = ("tm.h", list ())
218      else:
219        includes[name] = (owner, list ())
220
221
222show_master = False
223
224for arg in sys.argv[1:]:
225  if arg[0:1] == "-":
226    if arg[0:2] == "-h":
227      usage = True
228    elif arg[0:2] == "-i":
229      ignore_conditional = True
230    elif arg[0:2] == "-v":
231      show_master = True
232    else:
233      print "Error: unrecognized option " + arg
234  elif os.path.exists(arg):
235    file_list.append (arg)
236  else:
237    print "Error: file " + arg + " Does not exist."
238    usage = True
239
240if not file_list and not show_master:
241  usage = True
242
243if not usage and not os.path.exists ("coretypes.h"):
244  usage = True
245  print "Error: Must run command in main gcc source directory containing coretypes.h\n"
246
247# process diagnostic.h first.. it's special since GCC_DIAG_STYLE can be
248# overridden by languages, but must be done so by a file included BEFORE it.
249# so make sure it isn't seen as included by one of those files by making it 
250# appear to be included by the src file.
251process_stack.insert (0, ("diagnostic.h", ""))
252
253# Add the list of files in reverse order since it is processed as a stack later
254for i in order:
255  process_stack.insert (0, (i, "") )
256
257# build up the library of what header files include what other files.
258while process_stack:
259  info = process_stack.pop ()
260  process_one (info)
261
262# Now create the master ordering list
263for i in order:
264  create_master_list (os.path.basename (i), show_master)
265
266# handle warts in the duplicate list
267process_known_dups ()
268desired_order = master_list
269
270if show_master:
271  print " Canonical order of gcc include files: "
272  for x in master_list:
273    print x
274  print " "
275
276if usage:
277  print "gcc-order-headers [-i] [-v] file1 [filen]"
278  print "    Ensures gcc's headers files are included in a normalized form with"
279  print "    redundant headers removed.  The original files are saved in filename.bak"
280  print "    Outputs a list of files which changed."
281  print " -i ignore conditional compilation."
282  print "    Use after examining the file to be sure includes within #ifs are safe"
283  print "    Any headers within conditional sections will be ignored."
284  print " -v Show the canonical order of known headers"
285  sys.exit(0)
286
287
288didnt_do = list ()
289
290for fn in file_list:
291  nest = 0
292  src_h = list ()
293  src_line = { }
294
295  master_list = list ()
296
297  includes = { }
298  dups = { }
299
300  iinfo = process_ii_src (fn)
301  src = ii_src (iinfo)
302  include_list = ii_include_list (iinfo)
303
304  if ii_include_list_cond (iinfo):
305    if not ignore_conditional:
306      print fn + ": Cannot process due to conditional compilation of includes"
307      didnt_do.append (fn)
308      src = list ()
309
310  if not src:
311    continue
312
313  process_stack = list ()
314  # prime the stack with headers in the main ordering list so we get them in
315  # this order.
316  for d in order:
317    if d in include_list:
318      process_stack.insert (0, (d, ""))
319
320  for d in include_list:
321      nm = os.path.basename(d)
322      src_h.append (nm)
323      iname = d
324      iname2 = os.path.dirname (fn) + "/" + d
325      if not os.path.exists (d) and os.path.exists (iname2):
326        iname = iname2
327      if iname not in process_stack:
328        process_stack.insert (0, (iname, ""))
329      src_line[nm] = ii_src_line(iinfo)[d]
330      if src_line[nm].find("/*") != -1 and src_line[nm].find("*/") == -1:
331        # this means we have a multi line comment, abort!'
332        print fn + ": Cannot process due to a multi-line comment :"
333        print "        " + src_line[nm]
334        if fn not in didnt_do:
335          didnt_do.append (fn)
336        src = list ()
337
338  if not src:
339    continue
340
341  # Now create the list of includes as seen by the source file.
342  while process_stack:
343    info = process_stack.pop ()
344    process_one (info)
345 
346  for i in include_list:
347    create_master_list (os.path.basename (i), False)
348
349  new_src = list ()
350  header_added = list ()
351  new_order = list ()
352  for line in src:
353    d = find_pound_include (line, True, True)
354    if not d or d[-2:] != ".h":
355      new_src.append (line)
356    else:
357      if d == order[0] and not new_order:
358        new_order = get_new_order (src_h, desired_order)
359        for i in new_order:
360          new_src.append (src_line[i])
361          # if not seen, add it.
362          if i not in header_added:
363            header_added.append (i)
364      else:
365        nm = os.path.basename(d)
366        if nm not in header_added:
367          iby = indirectly_included (nm, src_h)
368          if not iby:
369            new_src.append (line)
370            header_added.append (nm)
371
372  if src != new_src:
373    os.rename (fn, fn + ".bak")
374    fl = open(fn,"w")
375    for line in new_src:
376      fl.write (line)
377    fl.close ()
378    print fn 
379
380 
381if didnt_do:
382  print "\n\n Did not process the following files due to conditional dependencies:"
383  str = ""
384  for x in didnt_do:
385    str += x + " "
386  print str
387  print "\n"
388  print "Please examine to see if they are safe to process, and re-try with -i. "
389  print "Safeness is determined by checking whether any of the reordered headers are"
390  print "within a conditional and could be hauled out of the conditional, thus changing"
391  print "what the compiler will see."
392  print "Multi-line comments after a #include can also cause failuer, they must be turned"
393  print "into single line comments or removed."
394
395
396
397
398