diff options
Diffstat (limited to 'doc/concepts/rules.md')
| -rw-r--r-- | doc/concepts/rules.md | 567 |
1 files changed, 567 insertions, 0 deletions
diff --git a/doc/concepts/rules.md b/doc/concepts/rules.md new file mode 100644 index 00000000..2ab4c334 --- /dev/null +++ b/doc/concepts/rules.md @@ -0,0 +1,567 @@ +User-defined Rules +================== + +Targets are defined in terms of high-level concepts like "libraries", +"binaries", etc. In order to translate these high-level definitions +into actionable tasks, the user defines rules, explaining at a single +point how all targets of a given type are built. + +Rules files +----------- + +Rules are defined in rules files (by default named `RULES`). Those +contain a JSON object mapping rule names to their rule definition. For +rules, the same naming scheme as for targets applies. However, built-in +rules (always named by a single string) take precedence in naming; to +explicitly refer to a rule defined in the current module, the module has +to be specified, possibly by a relative path, e.g., +`["./", ".", "install"]`. + +Basic components of a rule +-------------------------- + +A rule is defined through a JSON object with various keys. The only +mandatory key is `"expression"` containing the defining expression of +the rule. + +### `"config_fields"`, `"string_fields"` and `"target_fields"` + +These keys specify the fields that a target defined by that rule can +have. In particular, those have to be disjoint lists of strings. + +For `"config_fields"` and `"string_fields"` the respective field has to +evaluate to a list of strings, whereas `"target_fields"` have to +evaluate to a list of target references. Those references are evaluated +immediately, and in the name context of the target they occur in. + +The difference between `"config_fields"` and `"string_fields"` is that +`"config_fields"` are evaluated before the target fields and hence can +be used by the rule to specify config transitions for the target fields. +`"string_fields"` on the other hand are evaluated *after* +the target fields; hence the rule cannot use them to specify a +configuration transition, however the target definition in those fields +may use the `"outs"` and `"runfiles"` functions to have access to the +names of the artifacts or runfiles of a target specified in one of the +target fields. + +### `"implicit"` + +This key specifies a map of implicit dependencies. The keys of the map +are additional target fields, the values are the fixed list of targets +for those fields. If a short-form name of a target is used (e.g., only a +string instead of a module-target pair), it is interpreted relative to +the repository and module the rule is defined in, not the one the rule +is used in. Other than this, those fields are evaluated the same way as +target fields settable on invocation of the rule. + +### `"config_vars"` + +This is a list of strings specifying which parts of the configuration +the rule uses. The defining expression of the rule is evaluated in an +environment that is the configuration restricted to those variables; if +one of those variables is not specified in the configuration the value +in the restriction is `null`. + +### `"config_transitions"` + +This key specifies a map of (some of) the target fields (whether +declared as `"target_fields"` or as `"implicit"`) to a configuration +expression. Here, a configuration expression is any expression in our +language. It has access to the `"config_vars"` and the `"config_fields"` +and has to evaluate to a list of maps. Each map specifies a transition +to the current configuration by amending it on the domain of that map to +the given value. + +### `"imports"` + +This specifies a map of expressions that can later be used by +`CALL_EXPRESSION`. In this way, duplication of (rule) code can be +avoided. For each key, we have to have a name of an expression; +expressions are named following the same naming scheme as targets and +rules. The names are resolved in the context of the rule. Expressions +themselves are defined in expression files, the default name being +`EXPRESSIONS`. + +Each expression is a JSON object. The only mandatory key is +`"expression"` which has to be an expression in our language. It +optionally can have a key `"vars"` where the value has to be a list of +strings (and the default is the empty list). Additionally, it can have +another optional key `"imports"` following the same scheme as the +`"imports"` key of a rule; in the `"imports"` key of an expression, +names are resolved in the context of that expression. It is a +requirement that the `"imports"` graph be cycle free. + +### `"expression"` + +This specifies the defining expression of the rule. The value has to be +an expression of our expression language (basically, an abstract syntax +tree serialized as JSON). It has access to the following extra functions +and, when evaluated, has to return a result value. + +#### `FIELD` + +The field function takes one argument, `name` which has to evaluate +to the name of a field. For string fields, the given list of strings +is returned; for target fields, the list of abstract names for the +given target is returned. These abstract names are opaque within the +rule language (but meaningful when reported in error messages) and +should only be used to be passed on to other functions that expect +names as inputs. + +#### `DEP_ARTIFACTS` and `DEP_RUNFILES` + +These functions give access to the artifacts, or runfiles, +respectively, of one of the targets depended upon. It takes two +(evaluated) arguments, the mandatory `"dep"` and the optional +`"transition"`. + +The argument `"dep"` has to evaluate to an abstract name (as can be +obtained from the `FIELD` function) of some target specified in one +of the target fields. The `"transition"` argument has to evaluate to +a configuration transition (i.e., a map) and the empty transition is +taken as default. It is an error to request a target-transition pair +for a target that was not requested in the given transition through +one of the target fields. + +#### `DEP_PROVIDES` + +This function gives access to a particular entry of the provides map +of one of the targets depended upon. The arguments `"dep"` and +`"transition"` are as for `DEP_ARTIFACTS`; additionally, there is +the mandatory argument `"provider"` which has to evaluate to a +string. The function returns the value of the provides map of the +target at the given provider. If the key is not in the provides map +(or the value at that key is `null`), the optional argument +`"default"` is evaluated and returned. The default for `"default"` +is the empty list. + +#### `BLOB` + +The `BLOB` function takes a single (evaluated) argument `data` which +is optional and defaults to the empty string. This argument has to +evaluate to a string. The function returns an artifact that is a +non-executable file with the given string as content. + +#### `TREE` + +The `TREE` function takes a single (evaluated) argument `$1` which +has to be a map of artifacts. The result is a single tree artifact +formed from the input map. It is an error if the map cannot be +transformed into a tree (e.g., due to staging conflicts). + +#### `ACTION` + +Actions are a way to define new artifacts from (zero or more) +already defined artifacts by running a command, typically a +compiler, linker, archiver, etc. The action function takes the +following arguments. + + - `"inputs"` A map of artifacts. These artifacts are present when + the command is executed; the keys of the map are the relative + path from the working directory of the command. The command must + not make any assumption about the location of the working + directory in the file system (and instead should refer to files + by path relative to the working directory). Moreover, the + command must not modify the input files in any way. (In-place + operations can be simulated by staging, as is shown in the + example later in this document.) + + It is an additional requirement that no conflicts occur when + interpreting the keys as paths. For example, `"foo.txt"` and + `"./foo.txt"` are different as strings and hence legitimately + can be assigned different values in a map. When interpreted as a + path, however, they name the same path; so, if the `"inputs"` + map contains both those keys, the corresponding values have to + be equal. + + - `"cmd"` The command to execute, given as `argv` vector, i.e., a + non-empty list of strings. The 0'th element of that list will + also be the program to be executed. + + - `"env"` The environment in which the command should be executed, + given as a map of strings to strings. + + - `"outs"` and `"out_dirs"` Two list of strings naming the files + and directories, respectively, the command is expected to + create. It is an error if the command fails to create the + promised output files. These two lists have to be disjoint, but + an entry of `"outs"` may well name a location inside one of the + `"out_dirs"`. + +This function returns a map with keys the strings mentioned in +`"outs"` and `"out_dirs"`. As values this map has artifacts defined +to be the ones created by running the given command (in the given +environment with the given inputs). + +#### `RESULT` + +The `RESULT` function is the only way to obtain a result value. It +takes three (evaluated) arguments, `"artifacts"`, `"runfiles"`, and +`"provides"`, all of which are optional and default to the empty +map. It defines the result of a target that has the given artifacts, +runfiles, and provided data, respectively. In particular, +`"artifacts"` and `"runfiles"` have to be maps to artifacts, and +`"provides"` has to be a map. Moreover, they keys in `"runfiles"` +and `"artifacts"` are treated as paths; it is an error if this +interpretation yields to conflicts. The keys in the artifacts or +runfile maps as seen by other targets are the normalized paths of +the keys given. + +Result values themselves are opaque in our expression language and +cannot be deconstructed in any way. Their only purpose is to be the +result of the evaluation of the defining expression of a target. + +#### `CALL_EXPRESSION` + +This function takes one mandatory argument `"name"` which is +unevaluated; it has to a be a string literal. The expression +imported by that name through the imports field is evaluated in the +current environment restricted to the variables of that expression. +The result of that evaluation is the result of the `CALL_EXPRESSION` +statement. + +During the evaluation of an expression, rule fields can still be +accessed through the functions `FIELD`, `DEP_ARTIFACTS`, etc. In +particular, even an expression with no variables (that, hence, is +always evaluated in the empty environment) can carry out non-trivial +computations and be non-constant. The special functions `BLOB`, +`ACTION`, and `RESULT` are also available. If inside the evaluation +of an expression the function `CALL_EXPRESSION` is used, the name +argument refers to the `"imports"` map of that expression. So the +call graph is deliberately recursion free. + +Evaluation of a target +---------------------- + +A target defined by a user-defined rule is evaluated in the following +way. + + - First, the config fields are evaluated. + + - Then, the target-fields are evaluated. This happens for each field + as follows. + + - The configuration transition for this field is evaluated and the + transitioned configurations determined. + - The argument expression for this field is evaluated. The result + is interpreted as a list of target names. Each of those targets + is analyzed in all the specified configurations. + + - The string fields are evaluated. If the expression for a string + field queries a target (via `outs` or `runfiles`), the value for + that target is returned in the first configuration. The rational + here is that such generator expressions are intended to refer to the + corresponding target in its "main" configuration; they are hardly + used anyway for fields branching their targets over many + configurations. + + - The effective configuration for the target is determined. The target + effectively has used of the configuration the variables used by the + `arguments_config` in the rule invocation, the `config_vars` the + rule specified, and the parts of the configuration used by a target + dependent upon. For a target dependent upon, all parts it used of + its configuration are relevant expect for those fixed by the + configuration transition. + + - The rule expression is evaluated and the result of that evaluation + is the result of the rule. + +Example of developing a rule +---------------------------- + +Let's consider step by step an example of writing a rule. Say we want +to write a rule that programmatically patches some files. + +### Framework: The minimal rule + +Every rule has to have a defining expression evaluating to a `RESULT`. +So the minimally correct rule is the `"null"` rule in the following +example rule file. + + { "null": {"expression": {"type": "RESULT"}}} + +This rule accepts no parameters, and has the empty map as artifacts, +runfiles, and provided data. So it is not very useful. + +### String inputs + +Let's allow the target definition to have some fields. The most simple +fields are `string_fields`; they are given by a list of strings. In the +defining expression we can access them directly via the `FIELD` +function. Strings can be used when defining maps, but we can also create +artifacts from them, using the `BLOB` function. To create a map, we can +use the `singleton_map` function. We define values step by step, using +the `let*` construct. + +``` jsonc +{ "script only": + { "string_fields": ["script"] + , "expression": + { "type": "let*" + , "bindings": + [ [ "script content" + , { "type": "join" + , "separator": "\n" + , "$1": + { "type": "++" + , "$1": + [["H"], {"type": "FIELD", "name": "script"}, ["w", "q", ""]] + } + } + ] + , [ "script" + , { "type": "singleton_map" + , "key": "script.ed" + , "value": + {"type": "BLOB", "data": {"type": "var", "name": "script content"}} + } + ] + ] + , "body": + {"type": "RESULT", "artifacts": {"type": "var", "name": "script"}} + } + } +} +``` + +### Target inputs and derived artifacts + +Now it is time to add the input files. Source files are targets like any +other target (and happen to contain precisely one artifact). So we add a +target field `"srcs"` for the file to be patched. Here we have to keep +in mind that, on the one hand, target fields accept a list of targets +and, on the other hand, the artifacts of a target are a whole map. We +chose to patch all the artifacts of all given `"srcs"` targets. We can +iterate over lists with `foreach` and maps with `foreach_map`. + +Next, we have to keep in mind that targets may place their artifacts at +arbitrary logical locations. For us that means that first we have to +make a decision at which logical locations we want to place the output +artifacts. As one thinks of patching as an in-place operation, we chose +to logically place the outputs where the inputs have been. Of course, we +do not modify the input files in any way; after all, we have to define a +mathematical function computing the output artifacts, not a collection +of side effects. With that choice of logical artifact placement, we have +to decide what to do if two (or more) input targets place their +artifacts at logically the same location. We could simply take a +"latest wins" semantics (keep in mind that target fields give a list +of targets, not a set) as provided by the `map_union` function. We chose +to consider it a user error if targets with conflicting artifacts are +specified. This is provided by the `disjoint_map_union` that also allows +to specify an error message to be provided the user. Here, conflict +means that values for the same map position are defined in a different +way. + +The actual patching is done by an `ACTION`. We have the script already; +to make things easy, we stage the input to a fixed place and also expect +a fixed output location. Then the actual command is a simple shell +script. The only thing we have to keep in mind is that we want useful +output precisely if the action fails. Also note that, while we define +our actions sequentially, they will be executed in parallel, as none of +them depends on the output of another one of them. + +``` jsonc +{ "ed patch": + { "string_fields": ["script"] + , "target_fields": ["srcs"] + , "expression": + { "type": "let*" + , "bindings": + [ [ "script content" + , { "type": "join" + , "separator": "\n" + , "$1": + { "type": "++" + , "$1": + [["H"], {"type": "FIELD", "name": "script"}, ["w", "q", ""]] + } + } + ] + , [ "script" + , { "type": "singleton_map" + , "key": "script.ed" + , "value": + {"type": "BLOB", "data": {"type": "var", "name": "script content"}} + } + ] + , [ "patched files per target" + , { "type": "foreach" + , "var": "src" + , "range": {"type": "FIELD", "name": "srcs"} + , "body": + { "type": "foreach_map" + , "var_key": "file_name" + , "var_val": "file" + , "range": + {"type": "DEP_ARTIFACTS", "dep": {"type": "var", "name": "src"}} + , "body": + { "type": "let*" + , "bindings": + [ [ "action output" + , { "type": "ACTION" + , "inputs": + { "type": "map_union" + , "$1": + [ {"type": "var", "name": "script"} + , { "type": "singleton_map" + , "key": "in" + , "value": {"type": "var", "name": "file"} + } + ] + } + , "cmd": + [ "/bin/sh" + , "-c" + , "cp in out && chmod 644 out && /bin/ed out < script.ed > log 2>&1 || (cat log && exit 1)" + ] + , "outs": ["out"] + } + ] + ] + , "body": + { "type": "singleton_map" + , "key": {"type": "var", "name": "file_name"} + , "value": + { "type": "lookup" + , "map": {"type": "var", "name": "action output"} + , "key": "out" + } + } + } + } + } + ] + , [ "artifacts" + , { "type": "disjoint_map_union" + , "msg": "srcs artifacts must not overlap" + , "$1": + { "type": "++" + , "$1": {"type": "var", "name": "patched files per target"} + } + } + ] + ] + , "body": + {"type": "RESULT", "artifacts": {"type": "var", "name": "artifacts"}} + } + } +} +``` + +A typical invocation of that rule would be a target file like the +following. + +``` jsonc +{ "input.txt": + { "type": "ed patch" + , "script": ["%g/world/s//user/g", "%g/World/s//USER/g"] + , "srcs": [["FILE", null, "input.txt"]] + } +} +``` + +As the input file has the same name as a target (in the same module), we +use the explicit file reference in the specification of the sources. + +### Implicit dependencies and config transitions + +Say, instead of patching a file, we want to generate source files from +some high-level description using our actively developed code generator. +Then we have to do some additional considerations. + + - First of all, every target defined by this rule not only depends on + the targets the user specifies. Additionally, our code generator is + also an implicit dependency. And as it is under active development, + we certainly do not want it to be taken from the ambient build + environment (as we did in the previous example with `ed` which, + however, is a pretty stable tool). So we use an `implicit` target + for this. + - Next, we notice that our code generator is used during the build. In + particular, we want that tool (written in some compiled language) to + be built for the platform we run our actions on, not the target + platform we build our final binaries for. Therefore, we have to use + a configuration transition. + - As our defining expression also needs the configuration transition + to access the artifacts of that implicit target, we better define it + as a reusable expression. Other rules in our rule collection might + also have the same task; so `["transitions", "for host"]` might be a + good place to define it. In fact, it can look like the expression + with that name in our own code base. + +So, the overall organization of our rule might be as follows. + +``` jsonc +{ "generated code": + { "target_fields": ["srcs"] + , "implicit": {"generator": [["generators", "foogen"]]} + , "config_vars": ["HOST_ARCH"] + , "imports": {"for host": ["transitions", "for host"]} + , "config_transitions": + {"generator": [{"type": "CALL_EXPRESSION", "name": "for host"}]} + , "expression": ... + } +} +``` + +### Providing information to consuming targets + +In the simple case of patching, the resulting file is indeed the only +information the consumer of that target needs; in fact, the main point +was that the resulting target could be a drop-in replacement of a source +file. A typical rule, however, defines something like a library and a +library is much more, than just the actual library file and the public +headers: a library may depend on other libraries; therefore, in order to +use it, we need + + - to have the header files of dependencies available that might be + included by the public header files of that library, + - to have the libraries transitively depended upon available during + linking, and + - to know the order in which to link the dependencies (as they might + have dependencies among each other). + +In order to keep a maintainable build description, all this should be +taken care of by simply depending on that library. We do +*not* want the consumer of a target having to be aware of +such transitive dependencies (e.g., when constructing the link command +line), as it used to be the case in early build tools like `make`. + +It is a deliberate design choice that a target is given only by the +result of its analysis, regardless of where it is coming from. +Therefore, all this information needs to be part of the result of a +target. Such kind of information is precisely, what the mentioned +`"provides"` map is for. As a map, it can contain an arbitrary amount of +information and the interface function `"DEP_PROVIDES"` is in such a way +that adding more providers does not affect targets not aware of them +(there is no function asking for all providers of a target). The keys +and their meaning have to be agreed upon by a target and its consumers. +As the latter, however, typically are a target of the same family +(authored by the same group), this usually is not a problem. + +A typical example of computing a provided value is the `"link-args"` in +the rules used by `just` itself. They are defined by the following +expression. + +``` jsonc +{ "type": "nub_right" +, "$1": + { "type": "++" + , "$1": + [ {"type": "keys", "$1": {"type": "var", "name": "lib"}} + , {"type": "CALL_EXPRESSION", "name": "link-args-deps"} + , {"type": "var", "name": "link external", "default": []} + ] + } +} +``` + +This expression + + - collects the respective provider of its dependencies, + - adds itself in front, and + - deduplicates the resulting list, keeping only the right-most + occurrence of each entry. + +In this way, the invariant is kept, that the `"link-args"` from a +topological ordering of the dependencies (in the order that a each entry +is mentioned before its dependencies). |