From 794503b07d16e306d982fcf1640df343b2a6b23c Mon Sep 17 00:00:00 2001 From: Daniel Silverstone Date: Thu, 30 May 2019 10:37:00 +0100 Subject: loader.py: Make _check_circular_deps() static This did not need to be an instance method, making it static might improve performance and definitely makes it clear that it's not actually bound to the loader instances. Signed-off-by: Daniel Silverstone --- src/buildstream/_loader/loader.py | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'src/buildstream/_loader/loader.py') diff --git a/src/buildstream/_loader/loader.py b/src/buildstream/_loader/loader.py index ca058608d..991c517b4 100644 --- a/src/buildstream/_loader/loader.py +++ b/src/buildstream/_loader/loader.py @@ -338,7 +338,8 @@ class Loader(): # Raises: # (LoadError): In case there was a circular dependency error # - def _check_circular_deps(self, element, check_elements=None, validated=None, sequence=None): + @staticmethod + def _check_circular_deps(element, check_elements=None, validated=None, sequence=None): if check_elements is None: check_elements = set() @@ -366,7 +367,7 @@ class Loader(): check_elements.add(element) sequence.append(element.full_name) for dep in element.dependencies: - dep.element._loader._check_circular_deps(dep.element, check_elements, validated, sequence) + Loader._check_circular_deps(dep.element, check_elements, validated, sequence) check_elements.remove(element) sequence.pop() -- cgit v1.2.1 From 10901ea4f7eadb3820a2af2a0f8492671cebb4b3 Mon Sep 17 00:00:00 2001 From: Daniel Silverstone Date: Thu, 30 May 2019 11:05:30 +0100 Subject: loader.py: Rewrite _check_circular_deps() to be iterative In an effort to reduce the places where the stack might be a problem as we Cythonize things, rewrite the circular dependency checker to be iterative. Signed-off-by: Daniel Silverstone --- src/buildstream/_loader/loader.py | 72 +++++++++++++++++++++------------------ 1 file changed, 38 insertions(+), 34 deletions(-) (limited to 'src/buildstream/_loader/loader.py') diff --git a/src/buildstream/_loader/loader.py b/src/buildstream/_loader/loader.py index 991c517b4..5a1819e32 100644 --- a/src/buildstream/_loader/loader.py +++ b/src/buildstream/_loader/loader.py @@ -339,40 +339,44 @@ class Loader(): # (LoadError): In case there was a circular dependency error # @staticmethod - def _check_circular_deps(element, check_elements=None, validated=None, sequence=None): - - if check_elements is None: - check_elements = set() - if validated is None: - validated = set() - if sequence is None: - sequence = [] - - # Skip already validated branches - if element in validated: - return - - if element in check_elements: - # Create `chain`, the loop of element dependencies from this - # element back to itself, by trimming everything before this - # element from the sequence under consideration. - chain = sequence[sequence.index(element.full_name):] - chain.append(element.full_name) - raise LoadError(LoadErrorReason.CIRCULAR_DEPENDENCY, - ("Circular dependency detected at element: {}\n" + - "Dependency chain: {}") - .format(element.full_name, " -> ".join(chain))) - - # Push / Check each dependency / Pop - check_elements.add(element) - sequence.append(element.full_name) - for dep in element.dependencies: - Loader._check_circular_deps(dep.element, check_elements, validated, sequence) - check_elements.remove(element) - sequence.pop() - - # Eliminate duplicate paths - validated.add(element) + def _check_circular_deps(top_element): + + sequence = [top_element] + sequence_indices = [0] + check_elements = set(sequence) + validated = set() + + while sequence: + this_element = sequence[-1] + index = sequence_indices[-1] + if index < len(this_element.dependencies): + element = this_element.dependencies[index].element + sequence_indices[-1] = index + 1 + if element in check_elements: + # Create `chain`, the loop of element dependencies from this + # element back to itself, by trimming everything before this + # element from the sequence under consideration. + chain = [element.full_name for element in sequence[sequence.index(element):]] + chain.append(element.full_name) + raise LoadError(LoadErrorReason.CIRCULAR_DEPENDENCY, + ("Circular dependency detected at element: {}\n" + + "Dependency chain: {}") + .format(element.full_name, " -> ".join(chain))) + if element not in validated: + # We've not already validated this element, so let's + # descend into it to check it out + sequence.append(element) + sequence_indices.append(0) + check_elements.add(element) + # Otherwise we'll head back around the loop to validate the + # next dependency in this entry + else: + # Done with entry, pop it off, indicate we're no longer + # in its chain, and mark it valid + sequence.pop() + sequence_indices.pop() + check_elements.remove(this_element) + validated.add(this_element) # _sort_dependencies(): # -- cgit v1.2.1