path: root/doc/concepts/anonymous-targets.org

* Anonymous targets
** Motivation

Using [[https://github.com/protocolbuffers/protobuf][Protocol
buffers]] allows to specify, in a language-independent way, a wire
format for structured data. This is done by using description files
from which APIs for various languages can be generated. As protocol
buffers can contain other protocol buffers, the description files
themselves have a dependency structure.

From a software-engeneering point of view, the challenge is to
ensure that the author of the description files does not have to
be aware of the languages for which APIs will be generated later.
In fact, the main benefit of the language-independent description
is that clients in various languages can be implemented using the
same wire protocol (and thus capable of communicating with the
same server).

For a build system that means that we have to expect that language
bindings at places far away from the protocol definition, and
potentially several times. Such a duplication can also occur
implicitly if two buffers, for which language bindings are generated
both use a common buffer for which bindings are never requested
explicitly. Still, we want to avoid duplicate work for common parts
and we have to avoid conflicts with duplicate symbols and staging
conflicts for the libraries for the common part.

Our approach is that a "proto" target only provides the description
files together with their dependency structure. From those, a
consuming target generates "anonymous targets" as additional
dependencies; as those targets will have an appropriate notion of
equality, no duplicate work is done and hence, as a side effect,
staging or symbol conflicts are avoided as well.

** Prelimanary remark: action identifiers

Actions are defined as Merkle-tree hash of the contents. As all
components (input tree, list of output strings, command vector,
environment, and cache pragma) are given by expressions, that can
quickly be computed. This identifier also defines the notion of
equality for actions, and hence action artifacts. Recall that eqality
of artifacts is also (implicitly) used in our notion of disjoint
map union (where the set of keys does not have to be disjoint, as
long as the values for all duplicate keys are equal).

When constructing the action graph for traversal, we can drop
duplicates (i.e., actions with the same identifier, and hence the
same description). For the serialization of the graph as part of
the analyse command, we can afford the preperatory step to compute
a map from action id to list of origins.

** Equality

*** Notions of equality

In the context of builds, there are different concepts of equality
to consider. We recall the definitions, as well as their use in
our build tool.

**** Locational equality ("Defined at the same place")

Names (for targets and rules) are given by repository name, module
name, and target name (inside the module); additionally, for target
names, there's a bit specifying that we explicitly refer to a file.
Names are equal if and only if the respective strings (and the file
bit) are equal.

For targets, we use locational equality, i.e., we consider targets
equal precisely if their names are equal; targets defined at different
places are considered different, even if they're defined in the
same way. The reason we use notion of equality is that we have to
refer to targets (and also check if we already have a pending task
to analyse them) before we have fully explored them with all the
targets referred to in their definition.

**** Intensional equality ("Defined in the same way")

In our expression language we handle definitions; in particular,
we treat artifacts by their definition: a particular source file,
the output of a particular action, etc. Hence we use intensional
equality in our expression language; two objects are equal precisely
if they are defined in the same way. This notion of equality is easy
to determine without the need of reading a source file or running
an action. We implement quick tests by keeping a Merkle-tree hash
of all expression values.

**** Extensional equality ("Defining the same object")

For built artifacts, we use extensional equality, i.e., we consider
two files equal, if they are bit-by-bit identical. Implementation-wise,
we compare an appropriate cryptographic hash. Before running an
action, we built its inputs. In particular (as inputs are considered
extensionally) an action might cause a cache hit with an intensionally
different one.

**** Observable equality ("The defined objects behave in the same way")

Finally, there is the notion of observable equality, i.e., the
property that two binaries behaving the same way in all situations.
As this notion is undecidable, it is never used directly by any
build tool. However, it is often the motivation for a build in the
first place: we want a binary that behaves in a particular way.

*** Relation between these notions

The notions of equality were introduced in order from most fine grained
to most coarse. Targets defined at the same place are obviously defined
in the same way. Intensionally equal artifacts create equal action
graphs; here we can confidently say "equal" and not only isomorphic:
due to our preliminary clean up, even the node names are equal.
Making sure that equal actions produce bit-by-bit equal outputs
is the realm of [[https://reproducible-builds.org/][reproducibe
builds]]. The tool can support this by appropriate sandboxing,
etc, but the rules still have to define actions that don't pick
up non-input information like the current time, user id, readdir
order, etc. Files that are bit-by-bit identical will behave in
the same way.

*** Example

Consider the following target file.

#+BEGIN_SRC
{ "foo":
  { "type": "generic"
  , "outs": ["out.txt"]
  , "cmds": ["echo Hello World > out.txt"]
  }
, "bar":
  { "type": "generic"
  , "outs": ["out.txt"]
  , "cmds": ["echo Hello World > out.txt"]
  }
, "baz":
  { "type": "generic"
  , "outs": ["out.txt"]
  , "cmds": ["echo -n Hello > out.txt && echo ' World' >> out.txt"]
  }
, "foo upper":
  { "type": "generic"
  , "deps": ["foo"]
  , "outs": ["upper.txt"]
  , "cmds": ["cat out.txt | tr a-z A-Z > upper.txt"]
  }
, "bar upper":
  { "type": "generic"
  , "deps": ["bar"]
  , "outs": ["upper.txt"]
  , "cmds": ["cat out.txt | tr a-z A-Z > upper.txt"]
  }
, "baz upper":
  { "type": "generic"
  , "deps": ["baz"]
  , "outs": ["upper.txt"]
  , "cmds": ["cat out.txt | tr a-z A-Z > upper.txt"]
  }
, "ALL":
  { "type": "install"
  , "files":
    {"foo.txt": "foo upper", "bar.txt": "bar upper", "baz.txt": "baz upper"}
  }
}
#+END_SRC

Assume we build the target ~"ALL"~. Then we will analyse 7 targets,
all the locationally different ones (~"foo"~, ~"bar"~, ~"baz"~,
~"foo upper"~, ~"bar upper"~, ~"baz upper"~). For the targets ~"foo"~
and ~"bar"~, we immediately see that the definition is equal; their
intensional equality also renders ~"foo upper"~ and ~"bar upper"~
intensionally equal. Our action graph will contain 4 actions: one
with origins ~["foo", "bar"]~, one with origins ~["baz"]~, one with
origins ~["foo upper", "bar upper"]~, and one with origins ~["baz
upper"]~. The ~"install"~ target will, of course, not create any
actions. Building sequentially (~-J 1~), we will get one cache hit.
Even though the artifacts of ~"foo"~ and ~"bar"~ and of ~"baz~"
are defined differently, they are extensionally equal; both define
a file with contents ~"Hello World\n"~.

** Anonymous targets

Besides named targets we also have additional targets (and hence also
configured targets) that are not associated with a location they are
defined at. Due to the absence of definition location, their notion
of equality will take care of the necessary deduplication (implicitly,
by the way our dependency exploration works). We will call them
"anonymous targets", even though, technically, they're not fully
anonymous as the rules that are part of their structure will be
given by name, i.e., defining rule location.

*** Value type: target graph node

In order to allow targets to adequately describe a dependency
structure, we have a value type in our expression language, that
of a (target) graph node. As with all value types, equality is
intensional, i.e., nodes defined in the same way are equal even
if defined at different places. This can be achieved by our usual
approach for expressions of having cached Merkle-tree hashes and
comparing them when an equality test is required. This efficient
test for equality also allows using graph nodes as part of a map
key, e.g., for our asynchronous map conumers.

As a graph node can only be defined with all data given, the defined
dependency structure is cycle-free by construction. However, the
tree unfolding will usually be exponentially larger. For internal
handling, this is not a problem: our shared-pointer implementation
can efficently represent a directed acyclic graph and since we
cache hashes in expressions, we can compute the overall hash without
folding the structure to a tree. When presenting nodes to the user,
we only show the map of identifier to definition, to avoid that
exponential unfolding.

We have two kinds of nodes.

**** Value nodes

These represent a target that, in any configuration, returns a fixed
value. Source files would typically be represented this way. The
constructor function ~"VALUE_NODE"~ takes a single argument ~"$1"~
that has to be a result value.

**** Abstract nodes

These represent internal nodes in the dag. Their constructor
~"ABSTRACT_NODE"~ takes the following arguments (all evaluated).
- ~"node_type"~. An arbitrary string, not interpreted in any way, to
  indicate the role that the node has in the dependency structure.
  When we create an anonymous target from a node, this will serve
  as the key into the rule mapping to be applied.
- ~"string_fields"~. This has to be a map of strings.
- ~"target_fields"~. These have to be a map of lists of graph nodes.
Moreover, we require that the keys for maps provided as ~"string_fields"~
and ~"target_fields"~ be disjoint.

*** Graph nodes in ~export~ targets

Graph nodes are completely free of names and hence are eligible
for exporting. As with other values, in the cache the intensional
definition of artifacts implict in them will be replaced by the
corresponding, extensionally equal, known value.

However, some care has to be taken in the serialisation that is
part of the caching, as we do not want to unfold the the dag to
a tree. Therefore, we take as JSON serialisation a simple dict
with ~"type"~ set to ~"NODE"~, and ~"value"~ set to the Merkle-tree
hash. That serialisation respects intensional equality. To allow
deserialisation, we add an additional map to the serialisation from
node hash to its definition.

*** Dependings on anonymous targets

**** Parts of an anonymous target

An anonymous target is given by a pair of a node and a map mapping
the abstract node-type specifying strings to rule names. So, in
the implementation these are just two expression pointers (with
their defined notion of equality, i.e., equality of the respective
Merkle-tree hashes). Such a pair of pointers also forms an additional
variant of a name value, refering to such an anonymous target.

It should be noted that such an anonymous target contains all the
information needed to evaluate it in the same way as a regular (named)
target defined by a user-defined rule. It is an analysis error
analysing an anonymous target where there is no entry in the rules
map for the string given as ~"node_type"~ for the corresponding node.

**** Anonymous targets as additional dependencies

We keep the property that a user can only request named targets.
So anonymous targets have to be requested by other targets. We
also keep the property that other targets are only requested at
certain fixed steps in the evaluation of a target. To still achieve
a meaningful use of anonymous targets our rule language hanldes
anonymous targets in the following way.

***** Rules parameter ~"anonymous"~

In the rule definition a parameter ~"anonymous"~ (with empty map as
default) is allowed. It is used to define an additional dependency on
anonymous targets. The value has to be a map with keys the additional
implicitly defined field names. It is hence a requirement that the
set of keys be disjoint from all other field names (the values of
~"config_fields"~, ~"string_fields"~, and ~"target_fields"~, as well as
the keys of the ~"implict"~ parameter). Another consequence is that
~"config_transitions"~ map may now also have meaningful entries for
the keys of the ~"anonymous"~ map. Each value in the map has to be
itself a map, with entries ~"target"~, ~"provider"~, and ~"rule_map"~.

For ~"target"~, a single string has to be specifed, and the value has
to be a member of the ~"target_fields"~ list. For provider, a single
string has to be specified as well. The idea is that the nodes are
collected from that provider of the targets in the specified target
field. For ~"rule_map"~ a map has to be specified from strings to
rule names; the latter are evaluated in the context of the rule
definition.

****** Example

For generating language bindings for protocol buffers, a rule might
look as follows.

#+BEGIN_SRC
{ "cc_proto_bindings":
  { "target_fields": ["proto_deps"]
  , "anonymous":
    { "protos":
      { "target": "proto_deps"
      , "provider": "proto"
      , "rule_map": {"proto_library": "cc_proto_library"}
      }
    }
  , "expression": {...}
  }
}
#+END_SRC

***** Evaluation mechanism

The evaluation of a target defined by a user-defined rule is handled
as follows. After the target fields are evaluated as usual, an
additional step is carried out.

For each anymous-target field, i.e., for each key in the ~"anonymous"~
map, a list of anymous targets is generated from the corresponding
value: take all targets from the specified ~"target"~ field in all
their specified configuration transitions (they have already been
evaluated) and take the values provided for the specified ~"provider"~
key (using the empty list as default). That value has to be a list
of nodes. All the node lists obtained that way are concatenated.
The configuration transition for the respective field name is
evaluated. Those targets are then evaluated for all the transitioned
configurations requested.

In the final evaluation of the defining expression, the anonymous-target
fields are available in the same way as any other target field.
Also, they contribute to the effective configuration in the same
way as regular target fields.