Match Argument Type Lists Against Function Signatures with Variadic Parameters

A function library stores function signatures. Each function has a unique name, an ordered list of parameter types, and a flag that says whether it is variadic. A non-variadic function accepts exactly its parameter list. A variadic function accepts its parameter list with the last parameter type repeated one or more times.

Given the library and a list of queries, where each query is the ordered list of argument types at a call site, return for every query the names of all functions that accept that call.

Function Signature

def find_matching_functions(names: list[str], param_types: list[list[str]], is_variadic: list[bool], queries: list[list[str]]) -> list[list[str]]:

Function i is named names[i], has parameter types param_types[i] in order, and is variadic exactly when is_variadic[i] is True.

Rules

• A non-variadic function with parameter types p matches a query q exactly when q == p: the same length and the same type at every position.
• A variadic function with parameter types p of length m matches a query q exactly when len(q) >= m, q[j] == p[j] for every j < m - 1, and q[j] == p[m - 1] for every j >= m - 1. In other words, the leading parameters match position by position, and the last parameter type fills every remaining position, at least once.
• Types are compared as exact, case-sensitive strings. There is no subtyping or conversion between types.
• For each query, list the names of the matching functions in ascending order by plain string comparison (the order Python's sorted produces). If no function matches, the list is empty. The result contains one list per query, in query order.

Constraints

• 1 <= len(names) <= 10^4, and len(param_types) == len(is_variadic) == len(names).
• Names are unique and are 1 to 30 characters drawn from A-Z, a-z, 0-9 and _.
• 0 <= len(param_types[i]) <= 20, and len(param_types[i]) >= 1 whenever is_variadic[i] is True.
• Every type is 1 to 20 characters drawn from A-Z, a-z, 0-9 and _.
• 1 <= len(queries) <= 10^4 and 0 <= len(queries[j]) <= 100.
• The total number of types across all queries is at most 2 * 10^5.
• The total number of names across all returned lists is at most 10^6.

Examples

Example 1

Input:
 names = ["add", "sum", "format", "concat", "now"]
 param_types = [["int", "int"], ["int"], ["string", "int"], ["string"], []]
 is_variadic = [False, True, True, True, False]
 queries = [["int", "int"], ["string", "int", "int"], ["string"], [], ["int", "string"]]
Output:
 [["add", "sum"], ["format"], ["concat"], ["now"], []]

• ["int", "int"] matches add exactly, and sum, whose single int parameter repeats twice.
• ["string", "int", "int"] matches format: string, then int twice. It does not match concat, because every argument after the first would also have to be string.
• ["string"] matches concat. It does not match format, which needs at least two arguments.
• [] matches only now, the non-variadic function with no parameters. A variadic function needs at least one argument for its last parameter.
• ["int", "string"] matches nothing.

Example 2

Input:
 names = ["log", "logAll", "pair"]
 param_types = [["int", "string"], ["string"], ["int", "string"]]
 is_variadic = [True, True, False]
 queries = [["int"], ["int", "string", "string", "string"], ["int", "string"], ["string", "string"]]
Output:
 [[], ["log"], ["log", "pair"], ["logAll"]]

• ["int"] is too short for log, which needs at least two arguments, and does not start with string as logAll requires.
• ["int", "string", "string", "string"] matches log: int, then string three times.
• ["int", "string"] matches log, whose last parameter appears once, and pair exactly; "log" sorts before "pair".
• ["string", "string"] matches logAll.