python/tools/check_imports.py - third_party/perfetto - Git at Google

 #!/usr/bin/env python3
 # Copyright (C) 2023 The Android Open Source Project
 #
 # Licensed under the Apache License, Version 2.0 (the "License");
 # you may not use this file except in compliance with the License.
 # You may obtain a copy of the License at
 #
 #      http://www.apache.org/licenses/LICENSE-2.0
 #
 # Unless required by applicable law or agreed to in writing, software
 # distributed under the License is distributed on an "AS IS" BASIS,
 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 # See the License for the specific language governing permissions and
 # limitations under the License.
 """
 Enforce import rules for https://ui.perfetto.dev.
 Directory structure encodes ideas about the expected dependency graph
 of the code in those directories. Both in a fuzzy sense: we expect code
 withing a directory to have high cohesion within the directory and low
 coupling (aka fewer imports) outside of the directory - but also
 concrete rules:
 - "base should not depend on the fronted"
 - "plugins should only directly depend on the public API"
 - "we should not have circular dependencies"

 Without enforcement exceptions to this rule quickly slip in. This
 script allows such rules to be enforced at presubmit time.
 """

 import sys
 import os
 import re
 import collections
 import argparse

 ROOT_DIR = os.path.dirname(
     os.path.dirname(os.path.dirname(os.path.abspath(__file__))))
 UI_SRC_DIR = os.path.join(ROOT_DIR, 'ui', 'src')

 # Current plan for the dependency tree of the UI code (2023-09-21)
 # black = current
 # red = planning to remove
 # green = planning to add
 PLAN_DOT = """
 digraph g {
     mithril [shape=rectangle, label="mithril"];
     protos [shape=rectangle, label="//protos/perfetto"];

     _gen [shape=ellipse, label="/gen"];
     _base [shape=ellipse, label="/base"];
     _core [shape=ellipse, label="/core"];
     _engine [shape=ellipse, label="/engine"];

     _frontend [shape=ellipse, label="/frontend" color=red];
     _common [shape=ellipse, label="/common" color=red];
     _controller [shape=ellipse, label="/controller" color=red];
     _tracks [shape=ellipse, label="/tracks" color=red];

     _widgets [shape=ellipse, label="/widgets"];

     _public [shape=ellipse, label="/public"];
     _plugins [shape=ellipse, label="/plugins"];
     _chrome_extension [shape=ellipse, label="/chrome_extension"];
     _trace_processor [shape=ellipse, label="/trace_processor" color="green"];
     _protos [shape=ellipse, label="/protos"];
     engine_worker_bundle [shape=cds, label="Engine worker bundle"];
     frontend_bundle [shape=cds, label="Frontend bundle"];

     engine_worker_bundle -> _engine;
     frontend_bundle -> _core [color=green];
     frontend_bundle -> _frontend [color=red];

     _core -> _public;
     _plugins -> _public;

     _widgets -> _base;
     _core -> _base;
     _core -> _widgets;


     _widgets -> mithril;
     _plugins -> mithril;
     _core -> mithril

     _plugins -> _widgets;

     _core -> _chrome_extension;

     _frontend -> _widgets [color=red];
     _common -> _core [color=red];
     _frontend -> _core [color=red];
     _controller -> _core [color=red];

     _frontend -> _controller [color=red];
     _frontend -> _common [color=red];
     _controller -> _frontend  [color=red];
     _controller -> _common [color=red];
     _common -> _controller [color=red];
     _common -> _frontend [color=red];
     _tracks -> _frontend  [color=red];
     _tracks -> _controller  [color=red];
     _common -> _chrome_extension [color=red];

     _core -> _trace_processor [color=green];

     _engine -> _trace_processor [color=green];
     _engine -> _common [color=red];
     _engine -> _base;

     _gen -> protos;
     _core -> _gen [color=red];

     _core -> _protos;
     _protos -> _gen;
     _trace_processor -> _protos [color=green];

     _trace_processor -> _public [color=green];

     npm_trace_processor [shape=cds, label="npm trace_processor" color="green"];
     npm_trace_processor -> engine_worker_bundle [color="green"];
     npm_trace_processor -> _trace_processor [color="green"];
 }
 """


 class Failure(object):

   def __init__(self, path, rule):
     self.path = path
     self.rule = rule

   def __str__(self):
     nice_path = ["ui/src" + name + ".ts" for name in self.path]
     return ''.join([
         'Forbidden dependency path:\n\n ',
         '\n    -> '.join(nice_path),
         '\n',
         '\n',
         str(self.rule),
         '\n',
     ])


 class AllowList(object):

   def __init__(self, allowed, dst, reasoning):
     self.allowed = allowed
     self.dst = dst
     self.reasoning = reasoning

   def check(self, graph):
     for node, edges in graph.items():
       for edge in edges:
         if re.match(self.dst, edge):
           if not any(re.match(a, node) for a in self.allowed):
             yield Failure([node, edge], self)

   def __str__(self):
     return f'Only items in the allowlist ({self.allowed}) may directly depend on "{self.dst}" ' + self.reasoning


 class NoDirectDep(object):

   def __init__(self, src, dst, reasoning):
     self.src = src
     self.dst = dst
     self.reasoning = reasoning

   def check(self, graph):
     for node, edges in graph.items():
       if re.match(self.src, node):
         for edge in edges:
           if re.match(self.dst, edge):
             yield Failure([node, edge], self)

   def __str__(self):
     return f'"{self.src}" may not directly depend on "{self.dst}" ' + self.reasoning


 class NoDep(object):

   def __init__(self, src, dst, reasoning):
     self.src = src
     self.dst = dst
     self.reasoning = reasoning

   def check(self, graph):
     for node in graph:
       if re.match(self.src, node):
         for connected, path in bfs(graph, node):
           if re.match(self.dst, connected):
             yield Failure(path, self)

   def __str__(self):
     return f'"{self.src}" may not depend on "{self.dst}" ' + self.reasoning


 class NoCircularDeps(object):

   def __init__(self):
     pass

   def check(self, graph):
     for node in graph:
       for child in graph[node]:
         for reached, path in dfs(graph, child):
           if reached == node:
             yield Failure([node] + path, self)

   def __str__(self):
     return f'circular dependencies can cause complex issues'


 # We have three kinds of rules:
 # NoDirectDep(a, b) = files matching regex 'a' cannot *directly* import
 #   files matching regex 'b' - but they may indirectly depend on them.
 # NoDep(a, b) = as above but 'a' may not even transitively import 'b'.
 # NoCircularDeps = forbid introduction of circular dependencies
 RULES = [
     AllowList(
         ['/protos/index'],
         r'/gen/protos',
         'protos should be re-exported from /protos/index without the nesting.',
     ),
     NoDirectDep(
         r'/plugins/.*',
         r'/core/.*',
         'instead plugins should depend on the API exposed at ui/src/public.',
     ),
     NoDirectDep(
         r"/frontend/.*",
         r"/core_plugins/.*",
         "core code should not depend on plugins.",
     ),
     NoDirectDep(
         r"/core/.*",
         r"/core_plugins/.*",
         "core code should not depend on plugins.",
     ),
     NoDirectDep(
         r"/base/.*",
         r"/core_plugins/.*",
         "core code should not depend on plugins.",
     ),
     #NoDirectDep(
     #    r'/tracks/.*',
     #    r'/core/.*',
     #    'instead tracks should depend on the API exposed at ui/src/public.',
     #),
     NoDep(
         r'/core/.*',
         r'/plugins/.*',
         'otherwise the plugins are no longer optional.',
     ),
     NoDep(
         r'/core/.*',
         r'/frontend/.*',
         'trying to reduce the dependency mess as we refactor into core',
     ),
     NoDep(
         r'/core/.*',
         r'/common/.*',
         'trying to reduce the dependency mess as we refactor into core',
     ),
     NoDep(
         r'/core/.*',
         r'/controller/.*',
         'trying to reduce the dependency mess as we refactor into core',
     ),
     NoDep(
         r'/base/.*',
         r'/core/.*',
         'core should depend on base not the other way round',
     ),
     NoDep(
         r'/base/.*',
         r'/common/.*',
         'common should depend on base not the other way round',
     ),
     NoDep(
         r'/common/.*',
         r'/chrome_extension/.*',
         'chrome_extension must be a leaf',
     ),

     # Widgets
     NoDep(
         r'/widgets/.*',
         r'/frontend/.*',
         'widgets should only depend on base',
     ),
     NoDep(
         r'/widgets/.*',
         r'/core/.*',
         'widgets should only depend on base',
     ),
     NoDep(
         r'/widgets/.*',
         r'/plugins/.*',
         'widgets should only depend on base',
     ),
     NoDep(
         r'/widgets/.*',
         r'/common/.*',
         'widgets should only depend on base',
     ),

     # Bigtrace
     NoDep(
         r'/bigtrace/.*',
         r'/frontend/.*',
         'bigtrace should not depend on frontend',
     ),
     NoDep(
         r'/bigtrace/.*',
         r'/common/.*',
         'bigtrace should not depend on common',
     ),
     NoDep(
         r'/bigtrace/.*',
         r'/engine/.*',
         'bigtrace should not depend on engine',
     ),
     NoDep(
         r'/bigtrace/.*',
         r'/trace_processor/.*',
         'bigtrace should not depend on trace_processor',
     ),
     NoDep(
         r'/bigtrace/.*',
         r'/traceconv/.*',
         'bigtrace should not depend on traceconv',
     ),
     NoDep(
         r'/bigtrace/.*',
         r'/tracks/.*',
         'bigtrace should not depend on tracks',
     ),
     NoDep(
         r'/bigtrace/.*',
         r'/controller/.*',
         'bigtrace should not depend on controller',
     ),

     # Fails at the moment as we have several circular dependencies. One
     # example:
     # ui/src/frontend/cookie_consent.ts
     #    -> ui/src/frontend/globals.ts
     #    -> ui/src/frontend/router.ts
     #    -> ui/src/frontend/pages.ts
     #    -> ui/src/frontend/cookie_consent.ts
     #NoCircularDeps(),
 ]


 def all_source_files():
   for root, dirs, files in os.walk(UI_SRC_DIR, followlinks=False):
     for name in files:
       if name.endswith('.ts') and not name.endswith('.d.ts'):
         yield os.path.join(root, name)


 def is_dir(path, cache={}):
   try:
     return cache[path]
   except KeyError:
     result = cache[path] = os.path.isdir(path)
     return result


 def remove_prefix(s, prefix):
   return s[len(prefix):] if s.startswith(prefix) else s


 def remove_suffix(s, suffix):
   return s[:-len(suffix)] if s.endswith(suffix) else s


 def find_imports(path):
   src = path
   src = remove_prefix(src, UI_SRC_DIR)
   src = remove_suffix(src, '.ts')
   directory, _ = os.path.split(src)
   with open(path) as f:
     s = f.read()
     for m in re.finditer("^import[^']*'([^']*)';", s, flags=re.MULTILINE):
       raw_target = m[1]
       if raw_target.startswith('.'):
         target = os.path.normpath(os.path.join(directory, raw_target))
         if is_dir(UI_SRC_DIR + target):
           target = os.path.join(target, 'index')
       else:
         target = raw_target
       yield (src, target)


 def path_to_id(path):
   path = path.replace('/', '_')
   path = path.replace('-', '_')
   path = path.replace('@', '_at_')
   path = path.replace('.', '_')
   return path


 def is_external_dep(path):
   return not path.startswith('/')


 def bfs(graph, src):
   seen = set()
   queue = [(src, [])]

   while queue:
     node, path = queue.pop(0)
     if node in seen:
       continue

     seen.add(node)

     path = path[:]
     path.append(node)

     yield node, path
     queue.extend([(child, path) for child in graph[node]])


 def dfs(graph, src):
   seen = set()
   queue = [(src, [])]

   while queue:
     node, path = queue.pop()
     if node in seen:
       continue

     seen.add(node)

     path = path[:]
     path.append(node)

     yield node, path
     queue.extend([(child, path) for child in graph[node]])


 def write_dot(graph, f):
   print('digraph g {', file=f)
   for node, edges in graph.items():
     node_id = path_to_id(node)
     shape = 'rectangle' if is_external_dep(node) else 'ellipse'
     print(f'{node_id} [shape={shape}, label="{node}"];', file=f)

     for edge in edges:
       edge_id = path_to_id(edge)
       print(f'{node_id} -> {edge_id};', file=f)
   print('}', file=f)


 def do_check(options, graph):
   for rule in RULES:
     for failure in rule.check(graph):
       print(failure)
       return 1
   return 0


 def do_desc(options, graph):
   print('Rules:')
   for rule in RULES:
     print("  - ", end='')
     print(rule)


 def do_print(options, graph):
   for node, edges in graph.items():
     for edge in edges:
       print("{}\t{}".format(node, edge))


 def do_dot(options, graph):

   def simplify(path):
     if is_external_dep(path):
       return path
     return os.path.dirname(path)

   if options.simplify:
     new_graph = collections.defaultdict(set)
     for node, edges in graph.items():
       for edge in edges:
         new_graph[simplify(edge)]
         new_graph[simplify(node)].add(simplify(edge))
     graph = new_graph

   if options.ignore_external:
     new_graph = collections.defaultdict(set)
     for node, edges in graph.items():
       if is_external_dep(node):
         continue
       for edge in edges:
         if is_external_dep(edge):
           continue
         new_graph[edge]
         new_graph[node].add(edge)
     graph = new_graph

   write_dot(graph, sys.stdout)
   return 0


 def do_plan_dot(options, _):
   print(PLAN_DOT, file=sys.stdout)
   return 0


 def main():
   parser = argparse.ArgumentParser(description=__doc__)
   parser.set_defaults(func=do_check)
   subparsers = parser.add_subparsers()

   check_command = subparsers.add_parser(
       'check', help='Check the rules (default)')
   check_command.set_defaults(func=do_check)

   desc_command = subparsers.add_parser('desc', help='Print the rules')
   desc_command.set_defaults(func=do_desc)

   print_command = subparsers.add_parser('print', help='Print all imports')
   print_command.set_defaults(func=do_print)

   dot_command = subparsers.add_parser(
       'dot',
       help='Output dependency graph in dot format suitble for use in graphviz (e.g. ./tools/check_imports dot | dot -Tpng -ograph.png)'
   )
   dot_command.set_defaults(func=do_dot)
   dot_command.add_argument(
       '--simplify',
       action='store_true',
       help='Show directories rather than files',
   )
   dot_command.add_argument(
       '--ignore-external',
       action='store_true',
       help='Don\'t show external dependencies',
   )

   plan_dot_command = subparsers.add_parser(
       'plan-dot',
       help='Output planned dependency graph in dot format suitble for use in graphviz (e.g. ./tools/check_imports plan-dot | dot -Tpng -ograph.png)'
   )
   plan_dot_command.set_defaults(func=do_plan_dot)

   graph = collections.defaultdict(set)
   for path in all_source_files():
     for src, target in find_imports(path):
       graph[src].add(target)
       graph[target]

   options = parser.parse_args()
   return options.func(options, graph)


 if __name__ == '__main__':
   sys.exit(main())
	#!/usr/bin/env python3
	# Copyright (C) 2023 The Android Open Source Project
	#
	# Licensed under the Apache License, Version 2.0 (the "License");
	# you may not use this file except in compliance with the License.
	# You may obtain a copy of the License at
	#
	# http://www.apache.org/licenses/LICENSE-2.0
	#
	# Unless required by applicable law or agreed to in writing, software
	# distributed under the License is distributed on an "AS IS" BASIS,
	# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	# See the License for the specific language governing permissions and
	# limitations under the License.
	"""
	Enforce import rules for https://ui.perfetto.dev.
	Directory structure encodes ideas about the expected dependency graph
	of the code in those directories. Both in a fuzzy sense: we expect code
	withing a directory to have high cohesion within the directory and low
	coupling (aka fewer imports) outside of the directory - but also
	concrete rules:
	- "base should not depend on the fronted"
	- "plugins should only directly depend on the public API"
	- "we should not have circular dependencies"

	Without enforcement exceptions to this rule quickly slip in. This
	script allows such rules to be enforced at presubmit time.
	"""

	import sys
	import os
	import re
	import collections
	import argparse

	ROOT_DIR = os.path.dirname(
	os.path.dirname(os.path.dirname(os.path.abspath(__file__))))
	UI_SRC_DIR = os.path.join(ROOT_DIR, 'ui', 'src')

	# Current plan for the dependency tree of the UI code (2023-09-21)
	# black = current
	# red = planning to remove
	# green = planning to add
	PLAN_DOT = """
	digraph g {
	mithril [shape=rectangle, label="mithril"];
	protos [shape=rectangle, label="//protos/perfetto"];

	_gen [shape=ellipse, label="/gen"];
	_base [shape=ellipse, label="/base"];
	_core [shape=ellipse, label="/core"];
	_engine [shape=ellipse, label="/engine"];

	_frontend [shape=ellipse, label="/frontend" color=red];
	_common [shape=ellipse, label="/common" color=red];
	_controller [shape=ellipse, label="/controller" color=red];
	_tracks [shape=ellipse, label="/tracks" color=red];

	_widgets [shape=ellipse, label="/widgets"];

	_public [shape=ellipse, label="/public"];
	_plugins [shape=ellipse, label="/plugins"];
	_chrome_extension [shape=ellipse, label="/chrome_extension"];
	_trace_processor [shape=ellipse, label="/trace_processor" color="green"];
	_protos [shape=ellipse, label="/protos"];
	engine_worker_bundle [shape=cds, label="Engine worker bundle"];
	frontend_bundle [shape=cds, label="Frontend bundle"];

	engine_worker_bundle -> _engine;
	frontend_bundle -> _core [color=green];
	frontend_bundle -> _frontend [color=red];

	_core -> _public;
	_plugins -> _public;

	_widgets -> _base;
	_core -> _base;
	_core -> _widgets;


	_widgets -> mithril;
	_plugins -> mithril;
	_core -> mithril

	_plugins -> _widgets;

	_core -> _chrome_extension;

	_frontend -> _widgets [color=red];
	_common -> _core [color=red];
	_frontend -> _core [color=red];
	_controller -> _core [color=red];

	_frontend -> _controller [color=red];
	_frontend -> _common [color=red];
	_controller -> _frontend [color=red];
	_controller -> _common [color=red];
	_common -> _controller [color=red];
	_common -> _frontend [color=red];
	_tracks -> _frontend [color=red];
	_tracks -> _controller [color=red];
	_common -> _chrome_extension [color=red];

	_core -> _trace_processor [color=green];

	_engine -> _trace_processor [color=green];
	_engine -> _common [color=red];
	_engine -> _base;

	_gen -> protos;
	_core -> _gen [color=red];

	_core -> _protos;
	_protos -> _gen;
	_trace_processor -> _protos [color=green];

	_trace_processor -> _public [color=green];

	npm_trace_processor [shape=cds, label="npm trace_processor" color="green"];
	npm_trace_processor -> engine_worker_bundle [color="green"];
	npm_trace_processor -> _trace_processor [color="green"];
	}
	"""


	class Failure(object):

	def __init__(self, path, rule):
	self.path = path
	self.rule = rule

	def __str__(self):
	nice_path = ["ui/src" + name + ".ts" for name in self.path]
	return ''.join([
	'Forbidden dependency path:\n\n ',
	'\n -> '.join(nice_path),
	'\n',
	'\n',
	str(self.rule),
	'\n',
	])


	class AllowList(object):

	def __init__(self, allowed, dst, reasoning):
	self.allowed = allowed
	self.dst = dst
	self.reasoning = reasoning

	def check(self, graph):
	for node, edges in graph.items():
	for edge in edges:
	if re.match(self.dst, edge):
	if not any(re.match(a, node) for a in self.allowed):
	yield Failure([node, edge], self)

	def __str__(self):
	return f'Only items in the allowlist ({self.allowed}) may directly depend on "{self.dst}" ' + self.reasoning


	class NoDirectDep(object):

	def __init__(self, src, dst, reasoning):
	self.src = src
	self.dst = dst
	self.reasoning = reasoning

	def check(self, graph):
	for node, edges in graph.items():
	if re.match(self.src, node):
	for edge in edges:
	if re.match(self.dst, edge):
	yield Failure([node, edge], self)

	def __str__(self):
	return f'"{self.src}" may not directly depend on "{self.dst}" ' + self.reasoning


	class NoDep(object):

	def __init__(self, src, dst, reasoning):
	self.src = src
	self.dst = dst
	self.reasoning = reasoning

	def check(self, graph):
	for node in graph:
	if re.match(self.src, node):
	for connected, path in bfs(graph, node):
	if re.match(self.dst, connected):
	yield Failure(path, self)

	def __str__(self):
	return f'"{self.src}" may not depend on "{self.dst}" ' + self.reasoning


	class NoCircularDeps(object):

	def __init__(self):
	pass

	def check(self, graph):
	for node in graph:
	for child in graph[node]:
	for reached, path in dfs(graph, child):
	if reached == node:
	yield Failure([node] + path, self)

	def __str__(self):
	return f'circular dependencies can cause complex issues'


	# We have three kinds of rules:
	# NoDirectDep(a, b) = files matching regex 'a' cannot directly import
	# files matching regex 'b' - but they may indirectly depend on them.
	# NoDep(a, b) = as above but 'a' may not even transitively import 'b'.
	# NoCircularDeps = forbid introduction of circular dependencies
	RULES = [
	AllowList(
	['/protos/index'],
	r'/gen/protos',
	'protos should be re-exported from /protos/index without the nesting.',
	),
	NoDirectDep(
	r'/plugins/.*',
	r'/core/.*',
	'instead plugins should depend on the API exposed at ui/src/public.',
	),
	NoDirectDep(
	r"/frontend/.*",
	r"/core_plugins/.*",
	"core code should not depend on plugins.",
	),
	NoDirectDep(
	r"/core/.*",
	r"/core_plugins/.*",
	"core code should not depend on plugins.",
	),
	NoDirectDep(
	r"/base/.*",
	r"/core_plugins/.*",
	"core code should not depend on plugins.",
	),
	#NoDirectDep(
	# r'/tracks/.*',
	# r'/core/.*',
	# 'instead tracks should depend on the API exposed at ui/src/public.',
	#),
	NoDep(
	r'/core/.*',
	r'/plugins/.*',
	'otherwise the plugins are no longer optional.',
	),
	NoDep(
	r'/core/.*',
	r'/frontend/.*',
	'trying to reduce the dependency mess as we refactor into core',
	),
	NoDep(
	r'/core/.*',
	r'/common/.*',
	'trying to reduce the dependency mess as we refactor into core',
	),
	NoDep(
	r'/core/.*',
	r'/controller/.*',
	'trying to reduce the dependency mess as we refactor into core',
	),
	NoDep(
	r'/base/.*',
	r'/core/.*',
	'core should depend on base not the other way round',
	),
	NoDep(
	r'/base/.*',
	r'/common/.*',
	'common should depend on base not the other way round',
	),
	NoDep(
	r'/common/.*',
	r'/chrome_extension/.*',
	'chrome_extension must be a leaf',
	),

	# Widgets
	NoDep(
	r'/widgets/.*',
	r'/frontend/.*',
	'widgets should only depend on base',
	),
	NoDep(
	r'/widgets/.*',
	r'/core/.*',
	'widgets should only depend on base',
	),
	NoDep(
	r'/widgets/.*',
	r'/plugins/.*',
	'widgets should only depend on base',
	),
	NoDep(
	r'/widgets/.*',
	r'/common/.*',
	'widgets should only depend on base',
	),

	# Bigtrace
	NoDep(
	r'/bigtrace/.*',
	r'/frontend/.*',
	'bigtrace should not depend on frontend',
	),
	NoDep(
	r'/bigtrace/.*',
	r'/common/.*',
	'bigtrace should not depend on common',
	),
	NoDep(
	r'/bigtrace/.*',
	r'/engine/.*',
	'bigtrace should not depend on engine',
	),
	NoDep(
	r'/bigtrace/.*',
	r'/trace_processor/.*',
	'bigtrace should not depend on trace_processor',
	),
	NoDep(
	r'/bigtrace/.*',
	r'/traceconv/.*',
	'bigtrace should not depend on traceconv',
	),
	NoDep(
	r'/bigtrace/.*',
	r'/tracks/.*',
	'bigtrace should not depend on tracks',
	),
	NoDep(
	r'/bigtrace/.*',
	r'/controller/.*',
	'bigtrace should not depend on controller',
	),

	# Fails at the moment as we have several circular dependencies. One
	# example:
	# ui/src/frontend/cookie_consent.ts
	# -> ui/src/frontend/globals.ts
	# -> ui/src/frontend/router.ts
	# -> ui/src/frontend/pages.ts
	# -> ui/src/frontend/cookie_consent.ts
	#NoCircularDeps(),
	]


	def all_source_files():
	for root, dirs, files in os.walk(UI_SRC_DIR, followlinks=False):
	for name in files:
	if name.endswith('.ts') and not name.endswith('.d.ts'):
	yield os.path.join(root, name)


	def is_dir(path, cache={}):
	try:
	return cache[path]
	except KeyError:
	result = cache[path] = os.path.isdir(path)
	return result


	def remove_prefix(s, prefix):
	return s[len(prefix):] if s.startswith(prefix) else s


	def remove_suffix(s, suffix):
	return s[:-len(suffix)] if s.endswith(suffix) else s


	def find_imports(path):
	src = path
	src = remove_prefix(src, UI_SRC_DIR)
	src = remove_suffix(src, '.ts')
	directory, _ = os.path.split(src)
	with open(path) as f:
	s = f.read()
	for m in re.finditer("^import[^']'([^'])';", s, flags=re.MULTILINE):
	raw_target = m[1]
	if raw_target.startswith('.'):
	target = os.path.normpath(os.path.join(directory, raw_target))
	if is_dir(UI_SRC_DIR + target):
	target = os.path.join(target, 'index')
	else:
	target = raw_target
	yield (src, target)


	def path_to_id(path):
	path = path.replace('/', '_')
	path = path.replace('-', '_')
	path = path.replace('@', '_at_')
	path = path.replace('.', '_')
	return path


	def is_external_dep(path):
	return not path.startswith('/')


	def bfs(graph, src):
	seen = set()
	queue = [(src, [])]

	while queue:
	node, path = queue.pop(0)
	if node in seen:
	continue

	seen.add(node)

	path = path[:]
	path.append(node)

	yield node, path
	queue.extend([(child, path) for child in graph[node]])


	def dfs(graph, src):
	seen = set()
	queue = [(src, [])]

	while queue:
	node, path = queue.pop()
	if node in seen:
	continue

	seen.add(node)

	path = path[:]
	path.append(node)

	yield node, path
	queue.extend([(child, path) for child in graph[node]])


	def write_dot(graph, f):
	print('digraph g {', file=f)
	for node, edges in graph.items():
	node_id = path_to_id(node)
	shape = 'rectangle' if is_external_dep(node) else 'ellipse'
	print(f'{node_id} [shape={shape}, label="{node}"];', file=f)

	for edge in edges:
	edge_id = path_to_id(edge)
	print(f'{node_id} -> {edge_id};', file=f)
	print('}', file=f)


	def do_check(options, graph):
	for rule in RULES:
	for failure in rule.check(graph):
	print(failure)
	return 1
	return 0


	def do_desc(options, graph):
	print('Rules:')
	for rule in RULES:
	print(" - ", end='')
	print(rule)


	def do_print(options, graph):
	for node, edges in graph.items():
	for edge in edges:
	print("{}\t{}".format(node, edge))


	def do_dot(options, graph):

	def simplify(path):
	if is_external_dep(path):
	return path
	return os.path.dirname(path)

	if options.simplify:
	new_graph = collections.defaultdict(set)
	for node, edges in graph.items():
	for edge in edges:
	new_graph[simplify(edge)]
	new_graph[simplify(node)].add(simplify(edge))
	graph = new_graph

	if options.ignore_external:
	new_graph = collections.defaultdict(set)
	for node, edges in graph.items():
	if is_external_dep(node):
	continue
	for edge in edges:
	if is_external_dep(edge):
	continue
	new_graph[edge]
	new_graph[node].add(edge)
	graph = new_graph

	write_dot(graph, sys.stdout)
	return 0


	def do_plan_dot(options, _):
	print(PLAN_DOT, file=sys.stdout)
	return 0


	def main():
	parser = argparse.ArgumentParser(description=__doc__)
	parser.set_defaults(func=do_check)
	subparsers = parser.add_subparsers()

	check_command = subparsers.add_parser(
	'check', help='Check the rules (default)')
	check_command.set_defaults(func=do_check)

	desc_command = subparsers.add_parser('desc', help='Print the rules')
	desc_command.set_defaults(func=do_desc)

	print_command = subparsers.add_parser('print', help='Print all imports')
	print_command.set_defaults(func=do_print)

	dot_command = subparsers.add_parser(
	'dot',
	help='Output dependency graph in dot format suitble for use in graphviz (e.g. ./tools/check_imports dot \| dot -Tpng -ograph.png)'
	)
	dot_command.set_defaults(func=do_dot)
	dot_command.add_argument(
	'--simplify',
	action='store_true',
	help='Show directories rather than files',
	)
	dot_command.add_argument(
	'--ignore-external',
	action='store_true',
	help='Don\'t show external dependencies',
	)

	plan_dot_command = subparsers.add_parser(
	'plan-dot',
	help='Output planned dependency graph in dot format suitble for use in graphviz (e.g. ./tools/check_imports plan-dot \| dot -Tpng -ograph.png)'
	)
	plan_dot_command.set_defaults(func=do_plan_dot)

	graph = collections.defaultdict(set)
	for path in all_source_files():
	for src, target in find_imports(path):
	graph[src].add(target)
	graph[target]

	options = parser.parse_args()
	return options.func(options, graph)


	if __name__ == '__main__':
	sys.exit(main())