diff options
Diffstat (limited to 'src/buildstream/_loader/utils.pyx')
| -rw-r--r-- | src/buildstream/_loader/utils.pyx | 59 |
1 files changed, 59 insertions, 0 deletions
diff --git a/src/buildstream/_loader/utils.pyx b/src/buildstream/_loader/utils.pyx index 258a34ab7..1546fafa2 100644 --- a/src/buildstream/_loader/utils.pyx +++ b/src/buildstream/_loader/utils.pyx @@ -18,6 +18,9 @@ # Benjamin Schubert <bschubert@bloomberg.net> # +from .._exceptions import LoadError, LoadErrorReason +from .loadelement cimport LoadElement + # Check if given filename containers valid characters. # @@ -50,3 +53,59 @@ def valid_chars_name(str name): return False return True + + +# _check_circular_deps(): +# +# Detect circular dependencies on LoadElements with +# dependencies already resolved. +# +# Args: +# element (LoadElement): The element to check +# +# Raises: +# (LoadError): In case there was a circular dependency error +# +def check_circular_deps(LoadElement top_element): + + cdef list sequence = [top_element] + cdef list sequence_indices = [0] + # TODO: if pyroaring exported BitMap objects, we could use this here + cdef set check_elements = set(sequence) + cdef set validated = set() + + cdef LoadElement this_element, element + cdef Py_ssize_t index + + while sequence: + this_element = sequence[-1] + index = sequence_indices[-1] + + if index < len(this_element.dependencies): + element = <LoadElement> 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 = [(<LoadElement> elem).full_name for elem 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) |