[Notes] [Git][BuildStream/buildstream][bschubert/rework-circular-check] Eagerly check for circular dependencies

[Benjamin Schubert <gitlab mg gitlab com>]

Title: GitLab

Benjamin Schubert pushed to branch bschubert/rework-circular-check at BuildStream / buildstream

Commits:

• 4c626bad
  by Benjamin Schubert at 2019-02-12T16:55:38Z

  Eagerly check for circular dependencies
  
  Whenever we finish loading a package's dependencies, we can check
  if it's part of a cycle, this allows us to not have to go through
  the whole graph a second time
  

3 changed files:

• buildstream/_loader/loadelement.py
• buildstream/_loader/loader.py
• buildstream/_profile.py

Changes:

buildstream/_loader/loadelement.py

---

...	...	@@ -129,6 +129,58 @@ class LoadElement():
129	129	def depends(self, other):
130	130	return other._node_id in self._dep_cache
131	131
	132	+ # _ensure_no_circular_deps()
	133	+ #
	134	+ # Ensure the node is not part of a dependency cycle
	135	+ #
	136	+ # Raises:
	137	+ # (LoadError): In case there was a circular dependency
	138	+ #
	139	+ def _ensure_no_circular_deps(self):
	140	+ if self._node_id in self._dep_cache:
	141	+ self._find_circular_deps(set(), set(), [])
	142	+
	143	+ # _find_circular_deps():
	144	+ #
	145	+ # Detect circular dependencies on LoadElements with
	146	+ # dependencies already resolved.
	147	+ #
	148	+ # Args:
	149	+ # check_elements (set[LoadElement]): The elements in the chain being checked
	150	+ # validated (set[LoadElement]): The elements already validated to not have
	151	+ # circular dependencies
	152	+ # sequence (list[Element]): current sequence of elements that is checked
	153	+ #
	154	+ # Raises:
	155	+ # (LoadError): In case there was a circular dependency error
	156	+ #
	157	+ def _find_circular_deps(self, check_elements, validated, sequence):
	158	+ # Skip already validated branches
	159	+ if self in validated:
	160	+ return
	161	+
	162	+ if self in check_elements:
	163	+ # Create `chain`, the loop of element dependencies from this
	164	+ # element back to itself, by trimming everything before this
	165	+ # element from the sequence under consideration.
	166	+ chain = sequence[sequence.index(self.full_name):]
	167	+ chain.append(self.full_name)
	168	+ raise LoadError(LoadErrorReason.CIRCULAR_DEPENDENCY,
	169	+ ("Circular dependency detected at element: {}\n" +
	170	+ "Dependency chain: {}")
	171	+ .format(self.full_name, " -> ".join(chain)))
	172	+
	173	+ # Push / Check each dependency / Pop
	174	+ check_elements.add(self)
	175	+ sequence.append(self.full_name)
	176	+ for dep in self.dependencies:
	177	+ dep.element._check_circular_deps(check_elements, validated, sequence)
	178	+ check_elements.remove(self)
	179	+ sequence.pop()
	180	+
	181	+ # Eliminate duplicate paths
	182	+ validated.add(self)
	183	+
132	184
133	185	# _extract_depends_from_node():
134	186	#

buildstream/_loader/loader.py

---

...	...	@@ -127,23 +127,6 @@ class Loader():
127	127	target_elements.append(element)
128	128	profile_end(Topics.LOAD_PROJECT, target)
129	129
130		- #
131		- # Now that we've resolve the dependencies, scan them for circular dependencies
132		- #
133		-
134		- # Set up a dummy element that depends on all top-level targets
135		- # to resolve potential circular dependencies between them
136		- dummy_target = LoadElement("", "", self)
137		- dummy_target.dependencies.extend(
138		- LoadElement.Dependency(element, Symbol.RUNTIME)
139		- for element in target_elements
140		- )
141		-
142		- profile_key = "_".join(t for t in targets)
143		- profile_start(Topics.CIRCULAR_CHECK, profile_key)
144		- self._check_circular_deps(dummy_target)
145		- profile_end(Topics.CIRCULAR_CHECK, profile_key)
146		-
147	130	ret = []
148	131	#
149	132	# Sort direct dependencies of elements by their dependency ordering
...	...	@@ -278,53 +261,9 @@ class Loader():
278	261	deps_names = [dep.name for dep in dependencies]
279	262	self._warn_invalid_elements(deps_names)
280	263
281		- return element
	264	+ element._ensure_no_circular_deps()
282	265
283		- # _check_circular_deps():
284		- #
285		- # Detect circular dependencies on LoadElements with
286		- # dependencies already resolved.
287		- #
288		- # Args:
289		- # element (str): The element to check
290		- #
291		- # Raises:
292		- # (LoadError): In case there was a circular dependency error
293		- #
294		- def _check_circular_deps(self, element, check_elements=None, validated=None, sequence=None):
295		-
296		- if check_elements is None:
297		- check_elements = {}
298		- if validated is None:
299		- validated = {}
300		- if sequence is None:
301		- sequence = []
302		-
303		- # Skip already validated branches
304		- if validated.get(element) is not None:
305		- return
306		-
307		- if check_elements.get(element) is not None:
308		- # Create `chain`, the loop of element dependencies from this
309		- # element back to itself, by trimming everything before this
310		- # element from the sequence under consideration.
311		- chain = sequence[sequence.index(element.full_name):]
312		- chain.append(element.full_name)
313		- raise LoadError(LoadErrorReason.CIRCULAR_DEPENDENCY,
314		- ("Circular dependency detected at element: {}\n" +
315		- "Dependency chain: {}")
316		- .format(element.full_name, " -> ".join(chain)))
317		-
318		- # Push / Check each dependency / Pop
319		- check_elements[element] = True
320		- sequence.append(element.full_name)
321		- for dep in element.dependencies:
322		- dep.element._loader._check_circular_deps(dep.element, check_elements, validated, sequence)
323		- del check_elements[element]
324		- sequence.pop()
325		-
326		- # Eliminate duplicate paths
327		- validated[element] = True
	266	+ return element
328	267
329	268	# _sort_dependencies():
330	269	#

buildstream/_profile.py

---

...	...	@@ -42,7 +42,6 @@ initialized = False
42	42	#
43	43	# The special 'all' value will enable all profiles.
44	44	class Topics():
45		- CIRCULAR_CHECK = 'circ-dep-check'
46	45	SORT_DEPENDENCIES = 'sort-deps'
47	46	LOAD_LOADER = 'load-loader'
48	47	LOAD_CONTEXT = 'load-context'

—
View it on GitLab.
You're receiving this email because of your account on gitlab.com. If you'd like to receive fewer emails, you can adjust your notification settings.