1# Copyright (c) 2012 The Chromium Authors. All rights reserved.
2# Use of this source code is governed by a BSD-style license that can be
3# found in the LICENSE file.
4import sys
5import os
6import re
7
8class DepsException(Exception):
9  pass
10
11"""
12The core of this script is the calc_load_sequence function. In total, this
13walks over the provided javascript files and figures out their dependencies
14using the module definitions provided in each file. This allows us to, for
15example, have a trio of modules:
16
17foo.js:
18   base.require('bar');
19and bar.js:
20   base.require('baz');
21
22calc_load_sequence(['foo']) will yield:
23   [Module('baz'), Module('bar'), Module('foo')]
24
25which is, based on the dependencies, the correct sequence in which to load
26those modules.
27"""
28
29class ResourceFinder(object):
30  """Helper code for finding a module given a name and current module.
31
32  The dependency resolution code in Module.resolve will find bits of code in the
33  actual javascript that says things require('bar'). This
34  code is responsible for figuring out what filename corresponds to 'bar' given
35  a Module('foo').
36  """
37  def __init__(self, root_dir):
38    self._root_dir = root_dir
39    pass
40
41  def _find_and_load(self, current_module, requested_name, extension):
42    assert current_module.filename
43    pathy_name = requested_name.replace(".", os.sep)
44    filename = pathy_name + extension
45    absolute_path = os.path.join(self._root_dir, filename)
46
47    if not os.path.exists(absolute_path):
48      return None, None
49
50    f = open(absolute_path, 'r')
51    contents = f.read()
52    f.close()
53
54    return absolute_path, contents
55
56  def find_and_load_module(self, current_module, requested_module_name):
57    return self._find_and_load(current_module, requested_module_name, ".js")
58
59  def find_and_load_style_sheet(self,
60                                current_module, requested_style_sheet_name):
61    return self._find_and_load(
62      current_module, requested_style_sheet_name, ".css")
63
64
65class StyleSheet(object):
66  """Represents a stylesheet resource referenced by a module via the
67  base.requireStylesheet(xxx) directive."""
68  def __init__(self, name, filename, contents):
69    self.name = name
70    self.filename = filename
71    self.contents = contents
72
73  def __repr__(self):
74    return "StyleSheet(%s)" % self.name
75
76def _tokenize_js(text):
77  rest = text
78  tokens = ["//", "/*", "*/", "\n"]
79  while len(rest):
80    indices = [rest.find(token) for token in tokens]
81    found_indices = [index for index in indices if index >= 0]
82
83    if len(found_indices) == 0:
84      # end of string
85      yield rest
86      return
87
88    min_index = min(found_indices)
89    token_with_min = tokens[indices.index(min_index)]
90
91    if min_index > 0:
92      yield rest[:min_index]
93
94    yield rest[min_index:min_index + len(token_with_min)]
95    rest = rest[min_index + len(token_with_min):]
96
97def _strip_js_comments(text):
98  result_tokens = []
99  token_stream = _tokenize_js(text).__iter__()
100  while True:
101    try:
102      t = token_stream.next()
103    except StopIteration:
104      break
105
106    if t == "//":
107      while True:
108        try:
109          t2 = token_stream.next()
110          if t2 == "\n":
111            break
112        except StopIteration:
113          break
114    elif t == '/*':
115      nesting = 1
116      while True:
117        try:
118          t2 = token_stream.next()
119          if t2 == "/*":
120            nesting += 1
121          elif t2 == "*/":
122            nesting -= 1
123            if nesting == 0:
124              break
125        except StopIteration:
126          break
127    else:
128      result_tokens.append(t)
129  return "".join(result_tokens)
130
131class Module(object):
132  """Represents a javascript module. It can either be directly requested, e.g.
133  passed in by name to calc_load_sequence, or created by being referenced a
134  module via the base.require(xxx) directive.
135
136  Interesting properties on this object are:
137
138  - filename: the file of the actual module
139  - contents: the actual text contents of the module
140  - style_sheets: StyleSheet objects that this module relies on for styling
141    information.
142  - dependent_modules: other modules that this module needs in order to run
143  """
144  def __init__(self, name = None):
145    self.name = name
146    self.filename = None
147    self.contents = None
148
149    self.dependent_module_names = []
150    self.dependent_modules = []
151    self.style_sheet_names = []
152    self.style_sheets = []
153
154  def __repr__(self):
155    return "Module(%s)" % self.name
156
157  def load_and_parse(self, module_filename,
158                     module_contents = None,
159                     decl_required = True):
160    if not module_contents:
161      f = open(module_filename, 'r')
162      self.contents = f.read()
163      f.close()
164    else:
165      self.contents = module_contents
166    self.filename = module_filename
167    self.parse_definition_(self.contents, decl_required)
168
169  def resolve(self, all_resources, resource_finder):
170    if "scripts" not in all_resources:
171      all_resources["scripts"] = {}
172    if "style_sheets" not in all_resources:
173      all_resources["style_sheets"] = {}
174
175    assert self.filename
176
177    for name in self.dependent_module_names:
178      if name in all_resources["scripts"]:
179        assert all_resources["scripts"][name].contents
180        self.dependent_modules.append(all_resources["scripts"][name])
181        continue
182
183      filename, contents = resource_finder.find_and_load_module(self, name)
184      if not filename:
185        raise DepsException("Could not find a file for module %s" % name)
186
187      module = Module(name)
188      all_resources["scripts"][name] = module
189      self.dependent_modules.append(module)
190      module.load_and_parse(filename, contents)
191      module.resolve(all_resources, resource_finder)
192
193    for name in self.style_sheet_names:
194      if name in all_resources["style_sheets"]:
195        assert all_resources["style_sheets"][name].contents
196        self.style_sheets.append(all_resources["scripts"][name])
197        continue
198
199      filename, contents = resource_finder.find_and_load_style_sheet(self, name)
200      if not filename:
201        raise DepsException("Could not find a file for stylesheet %s" % name)
202
203      style_sheet = StyleSheet(name, filename, contents)
204      all_resources["style_sheets"][name] = style_sheet
205      self.style_sheets.append(style_sheet)
206
207  def compute_load_sequence_recursive(self, load_sequence, already_loaded_set):
208    for dependent_module in self.dependent_modules:
209      dependent_module.compute_load_sequence_recursive(load_sequence,
210                                                       already_loaded_set)
211    if self.name not in already_loaded_set:
212      already_loaded_set.add(self.name)
213      load_sequence.append(self)
214
215  def parse_definition_(self, text, decl_required = True):
216    if not decl_required and not self.name:
217      raise Exception("Module.name must be set for decl_required to be false.")
218
219    stripped_text = _strip_js_comments(text)
220
221    rest = stripped_text
222    while True:
223      # Things to search for.
224      m_r = re.search("""base\s*\.\s*require\((["'])(.+?)\\1\)""",
225                      rest, re.DOTALL)
226      m_s = re.search("""base\s*\.\s*requireStylesheet\((["'])(.+?)\\1\)""",
227                      rest, re.DOTALL)
228
229      # Figure out which was first.
230      if m_r and m_s:
231        if m_r.start() < m_s.start():
232          m = m_r
233        else:
234          m = m_s
235      elif m_r:
236        m = m_r
237      elif m_s:
238        m = m_s
239      else:
240        break
241
242      if m == m_r:
243        dependent_module_name = m.group(2)
244        if '/' in dependent_module_name:
245          raise DepsException("Slashes are not allowed in module names. "
246                              "Use '.' instead: %s" % dependent_module_name)
247        self.dependent_module_names.append(dependent_module_name)
248      elif m == m_s:
249        self.style_sheet_names.append(m.group(2))
250
251      rest = rest[m.end():]
252
253
254def calc_load_sequence(filenames):
255  """Given a list of starting javascript files, figure out all the Module
256  objects that need to be loaded to satisfiy their dependencies.
257
258  The javascript files shoud specify their dependencies in a format that is
259  textually equivalent to base.js' require syntax, namely:
260
261     base.require(module1);
262     base.require(module2);
263     base.requireStylesheet(stylesheet);
264
265  The output of this function is an array of Module objects ordered by
266  dependency.
267  """
268  all_resources = {}
269  all_resources["scripts"] = {}
270  toplevel_modules = []
271  root_dir = ''
272  if filenames:
273    root_dir = os.path.abspath(os.path.dirname(filenames[0]))
274  resource_finder = ResourceFinder(root_dir)
275  for filename in filenames:
276    if not os.path.exists(filename):
277      raise Exception("Could not find %s" % filename)
278    dirname = os.path.dirname(filename)
279    modname  = os.path.splitext(os.path.basename(filename))[0]
280    if len(dirname):
281      name = dirname.replace('/', '.') + '.' + modname
282    else:
283      name = modname
284
285    if name in all_resources["scripts"]:
286      continue
287
288    module = Module(name)
289    module.load_and_parse(filename, decl_required = False)
290    all_resources["scripts"][module.name] = module
291    module.resolve(all_resources, resource_finder)
292
293  # Find the root modules: ones who have no dependencies.
294  module_ref_counts = {}
295  for module in all_resources["scripts"].values():
296    module_ref_counts[module.name] = 0
297
298  def inc_ref_count(name):
299    module_ref_counts[name] = module_ref_counts[name] + 1
300  for module in all_resources["scripts"].values():
301    for dependent_module in module.dependent_modules:
302      inc_ref_count(dependent_module.name)
303
304  root_modules = [all_resources["scripts"][name]
305                  for name, ref_count in module_ref_counts.items()
306                  if ref_count == 0]
307
308  root_modules.sort(lambda x, y: cmp(x.name, y.name))
309
310  already_loaded_set = set()
311  load_sequence = []
312  for module in root_modules:
313    module.compute_load_sequence_recursive(load_sequence, already_loaded_set)
314  return load_sequence
315