| # |
| # Copyright (C) 2020 Codethink Limited |
| # Copyright (C) 2019 Bloomberg L.P. |
| # |
| # This program is free software; you can redistribute it and/or |
| # modify it under the terms of the GNU Lesser General Public |
| # License as published by the Free Software Foundation; either |
| # version 2 of the License, or (at your option) any later version. |
| # |
| # This library is distributed in the hope that it will be useful, |
| # but WITHOUT ANY WARRANTY; without even the implied warranty of |
| # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| # Lesser General Public License for more details. |
| # |
| # You should have received a copy of the GNU Lesser General Public |
| # License along with this library. If not, see <http://www.gnu.org/licenses/>. |
| # |
| # Authors: |
| # Tristan Van Berkom <tristan.vanberkom@codethink.co.uk> |
| # Daniel Silverstone <daniel.silverstone@codethink.co.uk> |
| # Benjamin Schubert <bschubert@bloomberg.net> |
| |
| import re |
| import sys |
| import itertools |
| |
| from ._exceptions import LoadError |
| from .exceptions import LoadErrorReason |
| from .node cimport MappingNode, Node, ScalarNode, SequenceNode, ProvenanceInformation |
| |
| ######################################################## |
| # Understanding Value Expressions # |
| ######################################################## |
| # |
| # This code uses the term "value expression" a lot to refer to `str` objects |
| # which have references to variables in them, and also to `list` objects which |
| # are effectively broken down strings. |
| # |
| # Ideally we would have a ValueExpression type in order to make this more |
| # comprehensive, but this would unfortunately introduce unnecessary overhead, |
| # making the code measurably slower. |
| # |
| # Value Expression Strings |
| # ------------------------ |
| # Strings which contain variables in them, such as: |
| # |
| # "My name is %{username}, good day." |
| # |
| # |
| # Parsed Value Expression Lists |
| # ----------------------------- |
| # Using `re.split()` from python's regular expression implementation, we |
| # parse the list using our locally defined VALUE_EXPRESSION_REGEX, which |
| # breaks down the string into a list of "literal" and "variable" components. |
| # |
| # The "literal" components are literal portions of the string which need |
| # no substitution, while the "variable" components represent variable names |
| # which need to be substituted with their corresponding resolved values. |
| # |
| # The parsed variable expressions have the following properties: |
| # |
| # * They are sparse, some of the "literal" values contain zero length |
| # strings which can be ignored. |
| # |
| # * Literal values are found only at even indices of the parsed |
| # variable expression |
| # |
| # * Variable names are found only at odd indices |
| # |
| # The above example "My name is %{username}, good day." is broken down |
| # into a parsed value expression as follows: |
| # |
| # [ |
| # "My name is ", # <- Index 0, literal value |
| # "username", # <- Index 1, variable name, '%{ ... }' discarded |
| # ", good day." # <- Index 2, literal value |
| # ] |
| # |
| |
| # Maximum recursion depth using the fast (recursive) variable resolution |
| # algorithm. |
| # |
| cdef Py_ssize_t MAX_RECURSION_DEPTH = 200 |
| |
| # Regular expression used to parse %{variables} in value expressions |
| # |
| # Note that variables are allowed to have dashes |
| # |
| VALUE_EXPRESSION_REGEX = re.compile(r"\%\{([a-zA-Z][a-zA-Z0-9_-]*)\}") |
| |
| # Cache for the parsed expansion strings. |
| # |
| cdef dict VALUE_EXPRESSION_CACHE = { |
| # Prime the cache with the empty string since otherwise that can |
| # cause issues with the parser, complications to which cause slowdown |
| "": [""], |
| } |
| |
| |
| # Variables() |
| # |
| # The Variables object resolves the variable references in the given MappingNode, |
| # expecting that any dictionary values which contain variable references can be |
| # resolved from the same dictionary. |
| # |
| # Each Element creates its own Variables instance to track the configured |
| # variable settings for the element. |
| # |
| # Notably, this object is delegated the responsibility of expanding |
| # variables in yaml Node hierarchies and substituting variables in strings |
| # in the context of a given Element's variable configuration. |
| # |
| # Args: |
| # node (Node): A node loaded and composited with yaml tools |
| # |
| # Raises: |
| # LoadError, if unresolved variables, or cycles in resolution, occur. |
| # |
| cdef class Variables: |
| |
| cdef MappingNode _original |
| cdef dict _values |
| |
| ################################################################# |
| # Dunder Methods # |
| ################################################################# |
| def __init__(self, MappingNode node): |
| |
| # The original MappingNode, we need to keep this |
| # around for proper error reporting. |
| # |
| self._original = node |
| |
| # The value map, this dictionary contains either unresolved |
| # value expressions, or resolved values. |
| # |
| # Each mapping value is a list, in the case that the value |
| # is resolved, then the list is only 1 element long. |
| # |
| self._values = self._init_values(node) |
| |
| # __getitem__() |
| # |
| # Fetches a resolved variable by it's name, allows |
| # addressing the Variables instance like a dictionary. |
| # |
| # Args: |
| # name (str): The name of the variable |
| # |
| # Returns: |
| # (str): The resolved variable value |
| # |
| # Raises: |
| # (LoadError): In the case of an undefined variable or |
| # a cyclic variable reference |
| # |
| def __getitem__(self, str name): |
| if name not in self._values: |
| raise KeyError(name) |
| |
| return self._expand_var(name) |
| |
| # __contains__() |
| # |
| # Checks whether a given variable exists, allows |
| # supporting `if 'foo' in variables` expressions. |
| # |
| # Args: |
| # name (str): The name of the variable to check for |
| # |
| # Returns: |
| # (bool): True if `name` is a valid variable |
| # |
| def __contains__(self, str name): |
| return name in self._values |
| |
| # __iter__() |
| # |
| # Provide an iterator for all variables effective values |
| # |
| # Returns: |
| # (Iterator[Tuple[str, str]]) |
| # |
| def __iter__(self): |
| return _VariablesIterator(self) |
| |
| ################################################################# |
| # Public API # |
| ################################################################# |
| |
| # check() |
| # |
| # Assert that all variables declared on this Variables |
| # instance have been resolved properly, and reports errors |
| # for undefined references and circular references. |
| # |
| # Raises: |
| # (LoadError): In the case of an undefined variable or |
| # a cyclic variable reference |
| # |
| cpdef check(self): |
| cdef object key |
| |
| # Just resolve all variables. |
| for key in self._values.keys(): |
| self._expand_var(<str> key) |
| |
| # get() |
| # |
| # Expand definition of variable by name. If the variable is not |
| # defined, it will return None instead of failing. |
| # |
| # Args: |
| # name (str): Name of the variable to expand |
| # |
| # Returns: |
| # (str|None): The expanded value for the variable or None variable was not defined. |
| # |
| cpdef str get(self, str name): |
| if name not in self._values: |
| return None |
| return self[name] |
| |
| # expand() |
| # |
| # Expand all the variables found in the given Node, recursively. |
| # This does the change in place, modifying the node. If you want to keep |
| # the node untouched, you should use `node.clone()` beforehand |
| # |
| # Args: |
| # (Node): A node for which to substitute the values |
| # |
| # Raises: |
| # (LoadError): In the case of an undefined variable or |
| # a cyclic variable reference |
| # |
| cpdef expand(self, Node node): |
| if isinstance(node, ScalarNode): |
| (<ScalarNode> node).value = self.subst(<ScalarNode> node) |
| elif isinstance(node, SequenceNode): |
| for entry in (<SequenceNode> node).value: |
| self.expand(entry) |
| elif isinstance(node, MappingNode): |
| for entry in (<MappingNode> node).value.values(): |
| self.expand(entry) |
| else: |
| assert False, "Unknown 'Node' type" |
| |
| # subst(): |
| # |
| # Substitutes any variables in 'string' and returns the result. |
| # |
| # Args: |
| # node (ScalarNode): The ScalarNode to substitute variables in |
| # |
| # Returns: |
| # (str): The new string with any substitutions made |
| # |
| # Raises: |
| # (LoadError): In the case of an undefined variable or |
| # a cyclic variable reference |
| # |
| cpdef str subst(self, ScalarNode node): |
| value_expression = _parse_value_expression(node.as_str()) |
| return self._expand_value_expression(value_expression, node) |
| |
| ################################################################# |
| # Private API # |
| ################################################################# |
| |
| # _init_values() |
| # |
| # Initialize the table of values. |
| # |
| # The value table is a dictionary keyed by the variable names where |
| # the values are value expressions (lists) which are initially unresolved. |
| # |
| # Value expressions are later resolved on demand and replaced in this |
| # table with single element lists. |
| # |
| # Args: |
| # node (MappingNode): The original variables mapping node |
| # |
| # Returns: |
| # (dict): A dictionary of value expressions (lists) |
| # |
| cdef dict _init_values(self, MappingNode node): |
| # Special case, if notparallel is specified in the variables for this |
| # element, then override max-jobs to be 1. |
| # Initialize it as a string as all variables are processed as strings. |
| # |
| if node.get_bool('notparallel', False): |
| node['max-jobs'] = str(1) |
| |
| cdef dict ret = {} |
| cdef object key_object |
| cdef str key |
| cdef str value |
| |
| for key_object in node.keys(): |
| key = <str> key_object |
| value = node.get_str(key) |
| ret[sys.intern(key)] = _parse_value_expression(value) |
| |
| return ret |
| |
| # _expand_var() |
| # |
| # Expand and cache a variable definition. |
| # |
| # This will try the fast, recursive path first and fallback to |
| # the slower iterative codepath. |
| # |
| # Args: |
| # name (str): Name of the variable to expand |
| # |
| # Returns: |
| # (str): The expanded value of variable |
| # |
| # Raises: |
| # (LoadError): In the case of an undefined variable or |
| # a cyclic variable reference |
| # |
| cdef str _expand_var(self, str name): |
| try: |
| return self._fast_expand_var(name) |
| except (KeyError, RecursionError): |
| return self._slow_expand_var(name) |
| |
| # _expand_value_expression() |
| # |
| # Expands a value expression |
| # |
| # This will try the fast, recursive path first and fallback to |
| # the slower iterative codepath. |
| # |
| # Args: |
| # value_expression (list): The parsed value expression to be expanded |
| # node (ScalarNode): The toplevel ScalarNode who is asking for an expansion |
| # |
| # Returns: |
| # (str): The expanded value expression |
| # |
| # Raises: |
| # (LoadError): In the case of an undefined variable or |
| # a cyclic variable reference |
| # |
| cdef str _expand_value_expression(self, list value_expression, ScalarNode node): |
| try: |
| return self._fast_expand_value_expression(value_expression) |
| except (KeyError, RecursionError): |
| return self._slow_expand_value_expression(None, value_expression, node) |
| |
| ################################################################# |
| # Resolution algorithm: fast path # |
| ################################################################# |
| |
| # _fast_expand_var() |
| # |
| # Fast, recursive path for variable expansion |
| # |
| # Args: |
| # name (str): Name of the variable to expand |
| # counter (int): Number of recursion cycles (used only in recursion) |
| # |
| # Returns: |
| # (str): The expanded value of variable |
| # |
| # Raises: |
| # (KeyError): If a reference to an undefined variable is encountered |
| # (RecursionError): If MAX_RECURSION_DEPTH recursion cycles is reached |
| # |
| cdef str _fast_expand_var(self, str name, int counter = 0): |
| cdef str sub |
| cdef list value_expression |
| |
| value_expression = <list> self._values[name] |
| if len(value_expression) > 1: |
| sub = self._fast_expand_value_expression(value_expression, counter) |
| value_expression = [sys.intern(sub)] |
| self._values[name] = value_expression |
| |
| return <str> value_expression[0] |
| |
| # _fast_expand_value_expression() |
| # |
| # Fast, recursive path for value expression expansion. |
| # |
| # Args: |
| # value_expression (list): The parsed value expression to be expanded |
| # counter (int): Number of recursion cycles (used only in recursion) |
| # |
| # Returns: |
| # (str): The expanded value expression |
| # |
| # Raises: |
| # (KeyError): If a reference to an undefined variable is encountered |
| # (RecursionError): If MAX_RECURSION_DEPTH recursion cycles is reached |
| # |
| cdef str _fast_expand_value_expression(self, list value_expression, int counter = 0): |
| if counter > MAX_RECURSION_DEPTH: |
| raise RecursionError() |
| |
| cdef Py_ssize_t idx |
| cdef object value |
| cdef list acc = [] |
| |
| for idx, value in enumerate(value_expression): |
| if (idx % 2) == 0: |
| acc.append(value) |
| else: |
| acc.append(self._fast_expand_var(<str> value, counter + 1)) |
| |
| return "".join(acc) |
| |
| ################################################################# |
| # Resolution algorithm: slow path # |
| ################################################################# |
| |
| # _slow_expand_var() |
| # |
| # Slow, iterative path for variable expansion with full error reporting |
| # |
| # Args: |
| # name (str): Name of the variable to expand |
| # |
| # Returns: |
| # (str): The expanded value of variable |
| # |
| # Raises: |
| # (LoadError): In the case of an undefined variable or |
| # a cyclic variable reference |
| # |
| cdef str _slow_expand_var(self, str name): |
| cdef list value_expression |
| cdef str expanded |
| |
| value_expression = self._get_checked_value_expression(name, None, None) |
| if len(value_expression) > 1: |
| expanded = self._slow_expand_value_expression(name, value_expression, None) |
| value_expression = [sys.intern(expanded)] |
| self._values[name] = value_expression |
| |
| return <str> value_expression[0] |
| |
| # _slow_expand_value_expression() |
| # |
| # Slow, iterative path for value expression expansion with full error reporting |
| # |
| # Note that either `varname` or `node` must be provided, these are used to |
| # identify the provenance of this value expression (which might be the value |
| # of a variable, or a value expression found elswhere in project YAML which |
| # needs to be substituted). |
| # |
| # Args: |
| # varname (str|None): The variable name associated with this value expression, if any |
| # value_expression (list): The parsed value expression to be expanded |
| # node (ScalarNode|None): The ScalarNode who is asking for an expansion |
| # |
| # Returns: |
| # (str): The expanded value expression |
| # |
| # Raises: |
| # (LoadError): In the case of an undefined variable or |
| # a cyclic variable reference |
| # |
| cdef str _slow_expand_value_expression(self, str varname, list value_expression, ScalarNode node): |
| cdef ResolutionStep step |
| cdef ResolutionStep new_step |
| cdef ResolutionStep this_step |
| cdef list iter_value_expression |
| cdef Py_ssize_t idx = 0 |
| cdef object value |
| cdef str resolved_varname |
| cdef str resolved_value = None |
| |
| # We will collect the varnames and value expressions which need |
| # to be resolved in the loop, sorted by dependency, and then |
| # finally reverse through them resolving them one at a time |
| # |
| cdef list resolved_varnames = [] |
| cdef list resolved_values = [] |
| |
| step = ResolutionStep() |
| step.init(varname, value_expression, None) |
| while step: |
| # Keep a hold of the current overall step |
| this_step = step |
| step = step.prev |
| |
| # Check for circular dependencies |
| this_step.check_circular(self._original) |
| |
| for idx, value in enumerate(this_step.value_expression): |
| |
| # Skip literal parts of the value expression |
| if (idx % 2) == 0: |
| continue |
| |
| iter_value_expression = self._get_checked_value_expression(<str> value, this_step.referee, node) |
| |
| # Queue up this value. |
| # |
| # Even if the value was already resolved, we need it in context to resolve |
| # previously enqueued variables |
| resolved_values.append(iter_value_expression) |
| resolved_varnames.append(value) |
| |
| # Queue up the values dependencies. |
| # |
| if len(iter_value_expression) > 1: |
| new_step = ResolutionStep() |
| new_step.init(<str> value, iter_value_expression, this_step) |
| |
| # Link it to the end of the stack |
| new_step.prev = step |
| step = new_step |
| |
| # We've now constructed the dependencies queue such that |
| # later dependencies are on the right, we can now safely peddle |
| # backwards and the last (leftmost) resolved value is the one |
| # we want to return. |
| # |
| for iter_value_expression, resolved_varname in zip(reversed(resolved_values), reversed(resolved_varnames)): |
| |
| # Resolve variable expressions as needed |
| # |
| if len(iter_value_expression) > 1: |
| resolved_value = self._resolve_value_expression(iter_value_expression) |
| iter_value_expression = [resolved_value] |
| if resolved_varname is not None: |
| self._values[resolved_varname] = iter_value_expression |
| |
| return resolved_value |
| |
| # _get_checked_value_expression() |
| # |
| # Fetches a value expression from the value table and raises a user |
| # facing error if the value is undefined. |
| # |
| # Args: |
| # varname (str): The variable name to fetch |
| # referee (str): The variable name referring to `varname`, or None |
| # node (ScalarNode): The ScalarNode for which we need to resolve `name` |
| # |
| # Returns: |
| # (list): The value expression for varname |
| # |
| # Raises: |
| # (LoadError): An appropriate error in case of undefined variables |
| # |
| cdef list _get_checked_value_expression(self, str varname, str referee, ScalarNode node): |
| cdef ProvenanceInformation provenance = None |
| cdef Node referee_node |
| cdef str error_message |
| |
| # |
| # Fetch the value and detect undefined references |
| # |
| try: |
| return <list> self._values[varname] |
| except KeyError as e: |
| |
| # Either the provenance is the toplevel calling provenance, |
| # or it is the provenance of the direct referee |
| referee_node = self._original.get_node(referee, allowed_types=None, allow_none=True) |
| if referee_node is not None: |
| provenance = referee_node.get_provenance() |
| elif node: |
| provenance = node.get_provenance() |
| |
| error_message = "Reference to undefined variable '{}'".format(varname) |
| if provenance: |
| error_message = "{}: {}".format(provenance, error_message) |
| raise LoadError(error_message, LoadErrorReason.UNRESOLVED_VARIABLE) from e |
| |
| # _resolve_value_expression() |
| # |
| # Resolves a value expression with the expectation that all |
| # variables within this value expression have already been |
| # resolved and updated in the Variables._values table. |
| # |
| # This is used as a part of the iterative resolution codepath, |
| # where value expressions are first sorted by dependency before |
| # being resolved in one go. |
| # |
| # Args: |
| # value_expression (list): The value expression to resolve |
| # |
| # Returns: |
| # (str): The resolved value expression |
| # |
| cdef str _resolve_value_expression(self, list value_expression): |
| cdef Py_ssize_t idx |
| cdef object value |
| cdef list acc = [] |
| |
| for idx, value in enumerate(value_expression): |
| if (idx % 2) == 0: |
| acc.append(value) |
| else: |
| acc.append(self._values[value][0]) |
| |
| return "".join(acc) |
| |
| |
| # ResolutionStep() |
| # |
| # The context for a single iteration in variable resolution. |
| # |
| cdef class ResolutionStep: |
| cdef str referee |
| cdef list value_expression |
| cdef ResolutionStep parent |
| cdef ResolutionStep prev |
| |
| # init() |
| # |
| # Initialize this ResolutionStep |
| # |
| # Args: |
| # referee (str): The name of the referring variable |
| # value_expression (list): The parsed value expression to be expanded |
| # parent (ResolutionStep): The parent ResolutionStep |
| # |
| cdef init(self, str referee, list value_expression, ResolutionStep parent): |
| self.referee = referee |
| self.value_expression = value_expression |
| self.parent = parent |
| self.prev = None |
| |
| # check_circular() |
| # |
| # Check for circular references in this step. |
| # |
| # Args: |
| # original_values (MappingNode): The original MappingNode for the Variables |
| # |
| # Raises: |
| # (LoadError): Will raise a user facing LoadError with |
| # LoadErrorReason.CIRCULAR_REFERENCE_VARIABLE in case |
| # circular references were encountered. |
| # |
| cdef check_circular(self, MappingNode original_values): |
| cdef ResolutionStep step = self.parent |
| while step: |
| if self.referee is step.referee: |
| self._raise_circular_reference_error(step, original_values) |
| step = step.parent |
| |
| # _raise_circular_reference_error() |
| # |
| # Helper function to construct a full report and raise the LoadError |
| # with LoadErrorReason.CIRCULAR_REFERENCE_VARIABLE. |
| # |
| # Args: |
| # conflict (ResolutionStep): The resolution step which conflicts with this step |
| # original_values (MappingNode): The original node to extract provenances from |
| # |
| # Raises: |
| # (LoadError): Unconditionally |
| # |
| cdef _raise_circular_reference_error(self, ResolutionStep conflict, MappingNode original_values): |
| cdef list error_lines = [] |
| cdef ResolutionStep step = self |
| cdef ScalarNode node |
| cdef str referee |
| |
| while step is not conflict: |
| if step.parent: |
| referee = step.parent.referee |
| else: |
| referee = self.referee |
| |
| node = original_values.get_scalar(referee) |
| |
| error_lines.append("{}: Variable '{}' refers to variable '{}'".format(node.get_provenance(), referee, step.referee)) |
| step = step.parent |
| |
| raise LoadError("Circular dependency detected on variable '{}'".format(self.referee), |
| LoadErrorReason.CIRCULAR_REFERENCE_VARIABLE, |
| detail="\n".join(reversed(error_lines))) |
| |
| |
| # _parse_value_expression() |
| # |
| # Tries to fetch the parsed value expression from the cache, parsing and |
| # caching value expressions on demand and returns the parsed value expression. |
| # |
| # Args: |
| # value_expression (str): The value expression in string form to parse |
| # |
| # Returns: |
| # (list): The parsed value expression in list form. |
| # |
| cdef list _parse_value_expression(str value_expression): |
| cdef list ret |
| |
| try: |
| return <list> VALUE_EXPRESSION_CACHE[value_expression] |
| except KeyError: |
| # This use of the regex turns a string like "foo %{bar} baz" into |
| # a list ["foo ", "bar", " baz"] |
| # |
| # The result is a parsed value expression, where even indicies |
| # contain literal parts of the value and odd indices contain |
| # variable names which need to be replaced by resolved variables. |
| # |
| splits = VALUE_EXPRESSION_REGEX.split(value_expression) |
| |
| # Optimize later routines by discarding any unnecessary trailing |
| # empty strings. |
| # |
| if splits[-1] == '': |
| del splits[-1] |
| |
| # We intern the string parts to try and reduce the memory impact |
| # of the cache. |
| # |
| ret = [sys.intern(<str> s) for s in <list> splits] |
| |
| # Cache and return the value expression |
| # |
| VALUE_EXPRESSION_CACHE[value_expression] = ret |
| return ret |
| |
| |
| # Iterator for all flatten variables. |
| # Used by Variables.__iter__ |
| cdef class _VariablesIterator: |
| cdef Variables _variables |
| cdef object _iter |
| |
| def __init__(self, Variables variables): |
| self._variables = variables |
| self._iter = iter(variables._values) |
| |
| def __iter__(self): |
| return self |
| |
| def __next__(self): |
| name = next(self._iter) |
| return name, self._variables._expand_var(name) |
