"""Module containing the code for parsing string constraints.""" import re from types import FunctionType from constraint.constraints import ( AllDifferentConstraint, AllEqualConstraint, CompilableFunctionConstraint, Constraint, ExactProdConstraint, ExactSumConstraint, FunctionConstraint, MaxProdConstraint, MaxSumConstraint, MinProdConstraint, MinSumConstraint, VariableExactProdConstraint, VariableExactSumConstraint, VariableMaxProdConstraint, # TODO implement parsing for these constraints: # InSetConstraint, # NotInSetConstraint, # SomeInSetConstraint, # SomeNotInSetConstraint, VariableMaxSumConstraint, VariableMinProdConstraint, VariableMinSumConstraint, ) def parse_restrictions(restrictions: list[str], tune_params: dict) -> list[tuple[Constraint | str, list[str]]]: """Parses restrictions (constraints in string format) from a list of strings into compilable functions and constraints. Returns a list of tuples of (strings or constraints) and parameters.""" # noqa: E501 # rewrite the restrictions so variables are singled out regex_match_variable = r"([a-zA-Z_$][a-zA-Z_$0-9]*)" regex_match_variable_or_constant = r"([a-zA-Z_$0-9]*)" def replace_params(match_object): key = match_object.group(1) if key in tune_params: param = str(key) return "params[params_index['" + param + "']]" else: return key def replace_params_split(match_object): # careful: has side-effect of adding to set `params_used` key = match_object.group(1) if key in tune_params: param = str(key) params_used.add(param) return param else: return key def to_multiple_restrictions(restrictions: list[str]) -> list[str]: """Split the restrictions into multiple restriction where possible (e.g. 3 <= x * y < 9 <= z -> [(MinProd(3), [x, y]), (MaxProd(9-1), [x, y]), (MinProd(9), [z])]).""" # noqa: E501 split_restrictions = list() for res in restrictions: # if there are logic chains in the restriction, skip splitting further if " and " in res or " or " in res: split_restrictions.append(res) continue # find the indices of splittable comparators comparators = ["<=", ">=", ">", "<"] comparators_indices = [(m.start(0), m.end(0)) for m in re.finditer("|".join(comparators), res)] if len(comparators_indices) <= 1: # this can't be split further split_restrictions.append(res) continue # split the restrictions from the previous to the next comparator for index in range(len(comparators_indices)): temp_copy = res prev_stop = comparators_indices[index - 1][1] + 1 if index > 0 else 0 next_stop = ( comparators_indices[index + 1][0] if index < len(comparators_indices) - 1 else len(temp_copy) ) split_restrictions.append(temp_copy[prev_stop:next_stop].strip()) return split_restrictions def to_numeric_constraint(restriction: str, params: list[str]) -> MinSumConstraint | VariableMinSumConstraint | ExactSumConstraint | VariableExactSumConstraint | MaxSumConstraint | VariableMaxSumConstraint | MinProdConstraint | VariableMinProdConstraint | ExactProdConstraint | VariableExactProdConstraint | MaxProdConstraint | VariableMaxProdConstraint | None: # noqa: E501 """Converts a restriction to a built-in numeric constraint if possible.""" # first check if all parameters have only numbers as values if len(params) == 0 or not all(all(isinstance(v, (int, float)) for v in tune_params[p]) for p in params): return None comparators = ["<=", "==", ">=", ">", "<"] comparators_found = re.findall("|".join(comparators), restriction) # check if there is exactly one comparator, if not, return None if len(comparators_found) != 1: return None comparator = comparators_found[0] # split the string on the comparison and remove leading and trailing whitespace left, right = tuple(s.strip() for s in restriction.split(comparator)) # if we have an inverse operation, rewrite to the other side operators_left = extract_operators(left) operators_right = extract_operators(right) if len(operators_left) > 0 and len(operators_right) > 0: # if there are operators on both sides, we can't handle this yet return None unique_operators_left = set(operators_left) unique_operators_right = set(operators_right) unique_operators = unique_operators_left.union(unique_operators_right) if len(unique_operators) == 1: variables_on_left = len(unique_operators_left) > 0 swapped_side_first_component = re.search( regex_match_variable_or_constant, left if variables_on_left else right ) # noqa: E501 if swapped_side_first_component is None: # if there is no variable on the left side, we can't handle this yet return None else: swapped_side_first_component = swapped_side_first_component.group(0) if "-" in unique_operators: if not variables_on_left: # e.g. "G == B-M" becomes "G+M == B" right_remainder = right[len(swapped_side_first_component) :] left_swap = right_remainder.replace("-", "+") restriction = f"{left}{left_swap}{comparator}{swapped_side_first_component}" else: # e.g. "B-M == G" becomes "B == G+M" left_remainder = left[len(swapped_side_first_component) :] right_swap = left_remainder.replace("-", "+") restriction = f"{swapped_side_first_component}{comparator}{right}{right_swap}" if "/" in unique_operators: if not variables_on_left: # e.g. "G == B/M" becomes "G*M == B" right_remainder = right[len(swapped_side_first_component) :] left_swap = right_remainder.replace("/", "*") restriction = f"{left}{left_swap}{comparator}{swapped_side_first_component}" else: # e.g. "B/M == G" becomes "B == G*M" left_remainder = left[len(swapped_side_first_component) :] right_swap = left_remainder.replace("/", "*") restriction = f"{swapped_side_first_component}{comparator}{right}{right_swap}" # we have a potentially rewritten restriction, split again left, right = tuple(s.strip() for s in restriction.split(comparator)) operators_left = extract_operators(left) operators_right = extract_operators(right) unique_operators_left = set(operators_left) unique_operators_right = set(operators_right) unique_operators = unique_operators_left.union(unique_operators_right) # find out which side is the constant number # either the left or right side of the equation must evaluate to a constant number, otherwise we use a VariableConstraint # noqa: E501 left_num = is_or_evals_to_number(left) right_num = is_or_evals_to_number(right) if (left_num is None and right_num is None) or (left_num is not None and right_num is not None): # if both sides are parameters, try to use the VariableConstraints variable_supported_operators = ["+", "*"] # variables = [s.strip() for s in list(left + right) if s not in variable_supported_operators] variables = re.findall(regex_match_variable, restriction) # if the restriction contains more than the variables and supported operators, return None if len(variables) == 0: return None if any(var.strip() not in tune_params for var in variables): raise ValueError(f"Variables {variables} not in tune_params {tune_params.keys()}") if ( len(re.findall(r"[+-]?\d+", restriction)) > 0 ): # TODO adjust when we support modifiers such as multipliers (see roadmap) # noqa: E501 # if the restriction contains numbers, return None return None # find all unique variable_supported_operators in the restriction, can have at most one variable_operators_left = list(s.strip() for s in list(left) if s in variable_supported_operators) variable_operators_right = list(s.strip() for s in list(right) if s in variable_supported_operators) variable_unique_operators = list(set(variable_operators_left).union(set(variable_operators_right))) # if there is a mix of operators (e.g. 'x + y * z == a') or multiple variables on both sides, return None if ( len(variable_unique_operators) <= 1 and all(s.strip() in params for s in variables) and (len(unique_operators_left) == 0 or len(unique_operators_right) == 0) ): # noqa: E501 variables_on_left = len(unique_operators_left) > 0 if len(variable_unique_operators) == 0 or variable_unique_operators[0] == "+": if comparator == "==": return ( VariableExactSumConstraint(variables[-1], variables[:-1]) if variables_on_left else VariableExactSumConstraint(variables[0], variables[1:]) ) # noqa: E501 elif comparator == "<=": # "B+C <= A" (maxsum) if variables_on_left else "A <= B+C" (minsum) return ( VariableMaxSumConstraint(variables[-1], variables[:-1]) if variables_on_left else VariableMinSumConstraint(variables[0], variables[1:]) ) # noqa: E501 elif comparator == ">=": # "B+C >= A" (minsum) if variables_on_left else "A >= B+C" (maxsum) return ( VariableMinSumConstraint(variables[-1], variables[:-1]) if variables_on_left else VariableMaxSumConstraint(variables[0], variables[1:]) ) # noqa: E501 elif variable_unique_operators[0] == "*": if comparator == "==": return ( VariableExactProdConstraint(variables[-1], variables[:-1]) if variables_on_left else VariableExactProdConstraint(variables[0], variables[1:]) ) # noqa: E501 elif comparator == "<=": # "B*C <= A" (maxprod) if variables_on_left else "A <= B*C" (minprod) return ( VariableMaxProdConstraint(variables[-1], variables[:-1]) if variables_on_left else VariableMinProdConstraint(variables[0], variables[1:]) ) # noqa: E501 elif comparator == ">=": # "B*C >= A" (minprod) if variables_on_left else "A >= B*C" (maxprod) return ( VariableMinProdConstraint(variables[-1], variables[:-1]) if variables_on_left else VariableMaxProdConstraint(variables[0], variables[1:]) ) # noqa: E501 # left_num and right_num can't both be constants, or for other reasons we can't use a VariableConstraint return None # if one side is a number, the other side must be a variable or expression number, variables, variables_on_left = ( (left_num, right.strip(), False) if left_num is not None else (right_num, left.strip(), True) ) # we can map '>' to '>=' and '<' to '<=' by adding a tiny offset to the number offset = 1e-12 if comparator == "<": if variables_on_left: # (x < 2) == (x <= 2-offset) number -= offset else: # (2 < x) == (2+offset <= x) number += offset elif comparator == ">": if variables_on_left: # (x > 2) == (x >= 2+offset) number += offset else: # (2 > x) == (2-offset >= x) number -= offset # check if an operator is applied on the variables, if not return operators = [r"\*\*", r"\*", r"\+"] operators_found = re.findall(str("|".join(operators)), variables) if len(operators_found) == 0: # no operators found, return only based on comparator if len(params) != 1 or variables not in params: # there were more than one variable but no operator return None # map to a Constraint # if there are restrictions with a single variable, it will be used to prune the domain at the start elif comparator == "==": return ExactSumConstraint(number) elif comparator == "<=" or comparator == "<": return MaxSumConstraint(number) if variables_on_left else MinSumConstraint(number) elif comparator == ">=" or comparator == ">": return MinSumConstraint(number) if variables_on_left else MaxSumConstraint(number) raise ValueError(f"Invalid comparator {comparator}") # check which operator is applied on the variables operator = operators_found[0] if not all(o == operator for o in operators_found): # if there is a mix of operators (e.g. 'x + y * z == 3'), return None return None # split the string on the comparison splitted = variables.split(operator) # check if there are only pure, non-recurring variables (no operations or constants) in the restriction if len(splitted) == len(params) and all(s.strip() in params for s in splitted): # map to a Constraint if operator == "**": # power operations are not (yet) supported, added to avoid matching the double asterisk return None elif operator == "*": if comparator == "==": return ExactProdConstraint(number) elif comparator == "<=" or comparator == "<": return MaxProdConstraint(number) if variables_on_left else MinProdConstraint(number) elif comparator == ">=" or comparator == ">": return MinProdConstraint(number) if variables_on_left else MaxProdConstraint(number) elif operator == "+": if comparator == "==": return ExactSumConstraint(number) elif comparator == "<=" or comparator == "<": # raise ValueError(restriction, comparator) return MaxSumConstraint(number) if variables_on_left else MinSumConstraint(number) elif comparator == ">=" or comparator == ">": return MinSumConstraint(number) if variables_on_left else MaxSumConstraint(number) else: raise ValueError(f"Invalid operator {operator}") return None def to_equality_constraint( restriction: str, params: list[str] ) -> AllEqualConstraint | AllDifferentConstraint | None: """Converts a restriction to either an equality or inequality constraint on all the parameters if possible.""" # check if all parameters are involved if len(params) != len(tune_params): return None # find whether (in)equalities appear in this restriction equalities_found = re.findall("==", restriction) inequalities_found = re.findall("!=", restriction) # check if one of the two have been found, if none or both have been found, return None if not (bool(len(equalities_found) > 0) ^ bool(len(inequalities_found) > 0)): return None comparator = equalities_found[0] if len(equalities_found) > 0 else inequalities_found[0] # split the string on the comparison splitted = restriction.split(comparator) # check if there are only pure, non-recurring variables (no operations or constants) in the restriction if len(splitted) == len(params) and all(s.strip() in params for s in splitted): # map to a Constraint if comparator == "==": return AllEqualConstraint() elif comparator == "!=": return AllDifferentConstraint() return ValueError(f"Not possible: comparator should be '==' or '!=', is {comparator}") return None # remove functionally duplicate restrictions (preserves order and whitespace) if all(isinstance(r, str) for r in restrictions): # clean the restriction strings to functional equivalence restrictions_cleaned = [r.replace(" ", "") for r in restrictions] restrictions_cleaned_unique = list(dict.fromkeys(restrictions_cleaned)) # dict preserves order # get the indices of the unique restrictions, use these to build a new list of restrictions restrictions_unique_indices = [restrictions_cleaned.index(r) for r in restrictions_cleaned_unique] restrictions = [restrictions[i] for i in restrictions_unique_indices] # create the parsed restrictions, split into multiple restrictions where possible restrictions = to_multiple_restrictions(restrictions) # split into functions that only take their relevant parameters parsed_restrictions = list() for res in restrictions: params_used: set[str] = set() parsed_restriction = re.sub(regex_match_variable, replace_params_split, res).strip() params_used_list = list(params_used) finalized_constraint = None if " or " not in res and " and " not in res: # if applicable, strip the outermost round brackets while ( parsed_restriction[0] == "(" and parsed_restriction[-1] == ")" and "(" not in parsed_restriction[1:] and ")" not in parsed_restriction[:1] ): parsed_restriction = parsed_restriction[1:-1] # check if we can turn this into the built-in numeric comparison constraint finalized_constraint = to_numeric_constraint(parsed_restriction, params_used_list) if finalized_constraint is None: # check if we can turn this into the built-in equality comparison constraint finalized_constraint = to_equality_constraint(parsed_restriction, params_used_list) if finalized_constraint is None: # we must turn it into a general function finalized_constraint = f"def r({', '.join(params_used_list)}): return {parsed_restriction} \n" parsed_restrictions.append((finalized_constraint, params_used_list)) return parsed_restrictions def compile_to_constraints( constraints: list[str], domains: dict, picklable=False ) -> list[tuple[Constraint, list[str], str | None]]: # noqa: E501 """Parses constraints in string format (referred to as restrictions) from a list of strings into a list of Constraints, parameters used, and source if applicable. Args: constraints (list[str]): list of constraints in string format to compile. domains (dict): the domains to use. picklable (bool, optional): whether to keep constraints such that they can be pickled for parallel solvers. Defaults to False. Returns: list of tuples with restrictions, parameters used (list[str]), and source (str) if applicable. Returned restrictions are strings, functions, or Constraints depending on the options provided. """ # noqa: E501 parsed_restrictions = parse_restrictions(constraints, domains) compiled_constraints: list[tuple[Constraint, list[str], str | None]] = list() for restriction, params_used in parsed_restrictions: if isinstance(restriction, str): # if it's a string, wrap it in a (compilable or compiled) function constraint if picklable: constraint = CompilableFunctionConstraint(restriction) else: code_object = compile(restriction, "", "exec") func = FunctionType(code_object.co_consts[0], globals()) constraint = FunctionConstraint(func) compiled_constraints.append((constraint, params_used, restriction)) elif isinstance(restriction, Constraint): # otherwise it already is a Constraint, pass it directly compiled_constraints.append((restriction, params_used, None)) else: raise ValueError(f"Restriction {restriction} is neither a string or Constraint {type(restriction)}") # return the restrictions and used parameters return compiled_constraints # Utility functions def is_or_evals_to_number(s: str) -> int | float | None: """Check if the string is a number or can be evaluated to a number.""" try: # check if it's a number or solvable to a number (e.g. '32*2') number = eval(s) assert isinstance(number, (int, float)) return number except Exception: # it's not a solvable subexpression, return None return None def extract_operators(expr: str) -> list[str]: """Extracts all operators from an expression string.""" # Regex for all supported binary operators: # supported_operators = ["**", "*", "+", "-", "/"] # remove any whitespace from the expression expr = expr.strip().replace(" ", "") # Match ** first to avoid matching * twice pattern = r""" (?