Types of inputs and outputs : Explicit versus Implicit

In a previous post, I mentioned the terms explicit inputs and outputs, and implicit inputs.

Here I'll take the opportunity to explain what I mean by these terms.

Explicit Inputs and Outputs

Explicit I/Os are file names that can be fully determined by the parameters to a build command.

Implicit Inputs and Outputs

Implicit I/Os are file names that can only be determined by inspecting the contents of an input file. In the general case, they are only knowable by executing a Translation.

Let's do an example of C++ compilation. Assume foo.cpp includes stdio.h.

cl.exe foo.cpp /c /Fo:foo.obj

foo.cpp is an explicit input.

foo.obj is an explicit output.

stdio.h is an implicit input. We cannot figure this out by looking at the command-line; we must look inside foo.cpp to figure that out.

There are no implicit outputs.

Why are these classes of inputs and outputs important?

They represent different frontiers of knowledge that the build engine can have when constructing a graph.

Let's take a simplified look at how QRBuild does things. QRBuild constructs a graph of Translations, where each Translation is a unit of execution that advertises its inputs and outputs.

At the start of a build, dependency information between Translations can only be determined algorithmically based on each Translation's explicit inputs and outputs. At this stage, we cannot attempt to open any output-files to figure out implicit inputs or outputs, because said files probably don't exist yet! In an arbitrary build graph, any file may be generated (including headers or cpp files).

Based on the user-selected targets (which outputs to produce), now the build begins. The initial Translations don't depend on any other Translations' outputs. Once those are complete, other Translations that depend on the produced outputs are allowed to run, until all required Translations are executed.

If there were no such thing as implicit inputs, we'd be done. Of course, we're not even close to done here :-) We know implicit inputs exist (like in C++ code), and we want them to cause dependency edges in the build graph. Without this automatic behavior, we'd have to manually add the same dependencies between Translations.

QRBuild basically employs a strategy of retrying each build command until all of its implicit inputs have been created.

When all inputs of a Translation are available, the engine requests for it to update its implicit inputs. The Translation implementation does this by either running a special command on the input files, or by simply attempting to execute the real build command. If additional implicit inputs are found, they are reported back to the build engine.

At this point, the build engine checks to see if all inputs exist. If they all exist, then the Translation is allowed to execute normally. If some are missing, then the build graph is updated so that the Translation instance in question now depends on some other stuff. The engine then makes sure the other stuff runs before attempting our Translation again.

Case in point : the MsvcCompile translation. It invokes the pre-processor with /showIncludes to get the list of includes (the implicit inputs).

What is the performance implication here?

Given a graph G containing N nodes (each node is a Translation), let's figure out how many Translation.Execute() calls we need to make.

1. With only explicit I/O, at most O(N) executions. Each node will be visited at most once, in dependency order, so it's exactly N.
2. With implicit inputs, at most O(N) executions. Worst case is actually 2*N.

Intuitively, I was worried that the implicit inputs algorithm would be N^2. Fortunately this is not the case. The proof goes something like this:

• Consider translation T1.
• Base case : No implicit inputs found. T1 is executed.
• Inductive case : implicit inputs found.
  • All inputs exist : T1 is executed.
  • One input missing : dependency established to translations T2.
    T1 is put back in the "sleep pool".
  • T2 must complete before T1 is retried.
• → Each time a new implicit input is found on some translation T1, some other translation T2 is enqueued and eventually completed. Since there are N total translations, there are a maximum of N retries. Therefore, the overall runtime is O(N).