Some Background Context

If you know anything about me, it's probably that I'm the lead maintainer of the Jenkins Templating Engine (JTE). While working on JTE 2.0, we refactored how pipeline initialization works.

1. Aggregated Pipeline Configurations: The Jenkins folder structure is used to create a configuration hierarchy. Pipeline configurations are aggregated across the hierarchy into an Aggregated Pipeline Configuration.
2. Interpret Pipeline Configuration: JTE has what are called Pipeline Primitives. They're just objects that get created by parsing the pipeline configuration and instantiating objects defined to be stored in a common Groovy binding.
3. Determine and Execute the Pipeline Template: The configured pipeline template is executed just like any other Jenkinsfile, just with the common binding that's been injected with primitives so that the templated aspects actually do something.

The benefit of this design is that all 3 phases of initialization are totally decoupled. The pipeline configuration files are a custom configuration DSL that get compiled into a PipelineConfigurationObject. Each Pipeline Primitive has a corresponding TemplatePrimitiveInjector that implements an extension point. We then dynamically fetch all the different Injectors and iterate over them 3 times. The first time is to invoke an optional interface on each injector to validate the pipeline configuration. The second time is to invoke an optional interface on each injector to instantiate a primitive and store it in the binding. The third time is to validate the completed binding.

This all happens from a common entry point that has no idea which Injectors exist. This makes it possible for 3rd party plugins to extend JTE's functionality through adding custom Injectors.

The challenge is now: How can certain Injectors ensure that specific other injectors run before them?

Here's an example required iteration order:

The Common Approach: Ordinals

Typically, the way I've seen this problem solved is through a pattern called Ordinals. Ordinals are defined, mathematically, as an integer or character indicating a position in a sequence.

When this pattern is implemented, an annotation is defined and optionally applied to elements in the sequence. Prior to iterating, elements are sorted according to their self-defined ordinal values.

Okay? So What's the Problem?

Every time I've ever seen an Ordinal declared, it's either trying to be first (with a value of 0) or last (with an absurdly high number). I have literally never seen an example where Ordinals are used to reasonably create an order of iteration.

A Better Approach

The thing about that iteration example above is that it looks pretty familiar. It's an example of a pretty classic computer science data structure, the Directed Acyclic Graph.

The most natural way to solve this problem is not ordinals. The most natural way to solve this problem is to:

1. Build a direct graph where the vertices of the graph are TemplatePrimitiveInjectors with edges going from a dependent Injector to the Injector that must proceed it.
2. Ensure the dependency graph is actually acyclic -- meaning that there are no circular dependencies between Injectors.
3. Perform a topological sorting of the graph
4. Iterate over the Injectors according to the sorted order

Immediately after thinking up with this approach, my tenured engineering mind started yelling at me:

Cool. Neat idea, Steven. Is it really worth the level of effort to program this fancy approach just because it's "better"? Just hard code the ordering or use Ordinals like everyone else. The (Return on Investment) / (Level of Effort) Ratio is way too low.

I'm glad I didn't immediately cave. My favorite part of all of this is just how easy it was to implement.

Step 1: Build the Graph

JGraphT did most of the work for me on this one!

Finding the Vertices

We said before that the graph's vertices would be the different TemplatePrimitiveInjector's. Thankfully, the Jenkins plugin ecosystem is built on the idea of extending and creating ExtensionPoint's, so looking them up shouldn't be too hard.

abstract class TemplatePrimitiveInjector implements ExtensionPoint{

  /**
   * fetches all registered TemplatePrimitiveInjectors
   *   
   * @return list of all TemplatePrimitiveInjectors
  */
  static ExtensionList<TemplatePrimitiveInjector> all(){
    return Jenkins.get().getExtensionList(TemplatePrimitiveInjector)
  }
  
  // shorthand for the interface methods that 
  // we're trying to define the order of execution for
  void validateConfiguration(...){}
  void injectPrimitives(...){}
  void validateBinding(...){}
  
}

Invoking the static method TemplatePrimitiveInjector.all() returns the full list of registered Injectors.

Identifying the Edges

Next up, we need a mechanism for identifying the dependencies.

Functional Goals:

1. The TemplatePrimitiveInjector interface has 3 stages and each stage may have its own dependencies, so we can't just define the dependencies on a class-wide basis.
2. Injectors should be able to define this dependency with minimal effort
3. Injectors should be able to define this dependency with minimal coupling to the rest of the code.

It turns out, a method-based annotation works perfect for this.

Let's define a @RunAfter annotation that accepts as a parameter the class names of other Injectors that must be executed first.

@Retention(RUNTIME)         // be discoverable at runtime 
@Target(ElementType.METHOD) // annotate methods (not class-wide)
@interface RunAfter{
  
  /** define a list of other Injectors */ 
  Class<? extends TemplatePrimitiveInjector>[] value();

}

Through this annotation, we can now easily construct dependencies. Here's a short hand example:

class A extends TemplatePrimitiveInjector{
  void validateConfiguration(...){}
  void injectPrimitives(...){}
  void validateBinding(...){}
}

class B extends TemplatePrimitiveInjector{
  void validateConfiguration(...){}
  
  @RunAfter(A)
  void injectPrimitives(...){}
 
  void validateBinding(...){}
}

class C extends TemplatePrimitiveInjector{
  void validateConfiguration(...){}
  void injectPrimitives(...){}
  
  @RunAfter([A, B])
  void validateBinding(...){}
}

Now we just need a way to look up a method's dependency's:

/**
 * returns the dependencies listed in the RunAfter annotation if present
 * on the given Injector's methodname
 */
private static List<Class<? extends TemplatePrimitiveInjector>> getPrerequisites(TemplatePrimitiveInjector injector, String methodName, Object... methodArgs){
  List<TemplatePrimitiveInjector> prereqs = []
  MetaMethod metaMethod = injector.metaClass.pickMethod(methodName, methodArgs*.class as Class[])
  if(metaMethod instanceof CachedMethod) {
    Method method = metaMethod.getCachedMethod()
    RunAfter annotation = method.getAnnotation(RunAfter)
    if (annotation) {
      prereqs = [annotation.value()].flatten() as List<Class<? extends TemplatePrimitiveInjector>>
    }
  }
  return prereqs
}

Creating the Graph

private static Graph<Class<? extends TemplatePrimitiveInjector>, DefaultEdge> createGraph(String methodName, Object... methodArgs){

  Graph<Class<? extends TemplatePrimitiveInjector>, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge)
  ExtensionList<TemplatePrimitiveInjector> injectors = TemplatePrimitiveInjector.all()

  // add each injector as a node in the graph
  injectors.each{ injector -> graph.addVertex(injector.class) }

  // for each injector, connect edges
  injectors.each{ injector ->
    List<Class<? extends TemplatePrimitiveInjector>> prereqs = getPrerequisites(injector, methodName, methodArgs)    
    prereqs.each{ req ->
      graph.addEdge(req, injector.class)
    }
  }

  // check for infinite loops
  CycleDetector detector = new CycleDetector(graph)
  Set<TemplatePrimitiveInjector> cycles = detector.findCycles()
  if(cycles){
    throw new JTEException("There are cyclic dependencies preventing initialization: ${cycles}")
  }

  return graph

}

Iterating over the Graph

Finally, we can create a method that takes a phase (either validateConfiguration, injectPrimitives, or validateBinding) and method arguments and ties all of this together!

private static void invoke(String phase, Object... args){
  
  List<Class<? extends TemplatePrimitiveInjector>> failedInjectors = []
  Graph<Class<? extends TemplatePrimitiveInjector>, DefaultEdge> graph = createGraph(phase, args)
  AggregateException errors = new AggregateException()

  new TopologicalOrderIterator<>(graph).each{ injectorClazz ->
    TemplatePrimitiveInjector injector = injectorClazz.getDeclaredConstructor().newInstance()
    try{
      // check if a dependent injector has failed, if so, don't execute
      if(!(getPrerequisites(injector, phase, args).intersect(failedInjectors))){
        injector.invokeMethod(phase, args)
      }
    } catch(any){
      errors.add(any)
      failedInjectors << injectorClazz
    }
  }
  
  if(errors.size()) { // this phase failed throw an exception
    throw errors
  }
  
}

Conclusion

I like to say that, "the line between brilliant and hacky is often thin". Let me know which side you think this falls on in the comments :).

Feel free to check out the actual code for this within the Jenkins Templating Engine: TemplatePrimitiveInjector, RunAfter, TemplateBindingFactory