Problem 644333 · hard · Level 06 Heuristics & Optimization

Pipeline Steps That Put Themselves in Order

py-metaprogramming · py-classes · __init_subclass__ · topological sort · plugin registry

A data-cleaning tool lets anyone add a processing step by writing a class. A step names itself and the steps that must run before it, right in the class line, and the tool works out the running order:

class TextSteps(Step, root=True):         # a new family of steps
    pass

class Tokenise(TextSteps, name="tokenise", after=["lower"]):
    def run(self, text):
        return text.split()

class Lower(TextSteps, name="lower"):
    def run(self, text):
        return text.lower()

Write the base class Step:

  • class F(Step, root=True) starts a new family with its own, empty set of steps. Families never share steps, so two families may use the same step names.
  • Every other subclass (directly or indirectly below a family root) is a step of that family and must give name=...; after=... is optional and is a list or tuple of step names, or a single string for one name. A step defined directly below Step without root=True, a step without a name, a name already used in its family, or a step without a callable run method raises TypeError when the class is defined. A step's after names may refer to steps that are defined later.
  • order(), a class method callable on the root or on any step of a family, returns the list of the family's step names in running order: every step comes after all the steps in its after. Whenever several steps could come next, the one defined first goes first. A name in after that is not a step of the family raises KeyError; steps that can never run because they wait for each other in a cycle raise ValueError.
  • run_all(data), also a class method, creates an instance of each step (with no arguments) in running order and passes the data through them: each run receives the previous result and returns the next. It returns the last result.

The tests define families on your Step inside setup helpers you can call with Run: text_family(), text_report(text), definition_errors(), order_errors(), two_families() and random_family(n, seed) (which creates its steps with type(...)). outcome(call) returns a result or the exception's name.

Examples

Input:  text_report("The cats and the dogs of the town and the cats")
Output: (["lower", "tokenise", "stem", "stopwords", "count"], [("cat", 2), ("dog", 1), ("town", 1)])
Explanation: after "tokenise", both "stem" and "stopwords" may run; "stem" was defined first.

Input:  order_errors()
Output: ("KeyError", ["fetch", "load"], 2, "ValueError", "ValueError")

Constraints

  • At most 500 steps per family; defining a step and asking for the order must stay fast.

Goals

  • Use `__init_subclass__` with keyword arguments in the `class` line to register and check subclasses
  • Keep a separate registry per family of classes, found through ordinary inheritance
  • Order registered steps by their declared dependencies, deterministically, and report cycles and unknown names
Starting Python…