Verify conflict-freeness in inputs, artifacts, and runfiles

Our maps serve two purposes: on the one hand, they can be a generic
key-value association with arbitrary strings as keys. On the other
hand, we use them to describe arrangements of files (inputs to actions,
artifacts or runfiles generated). In this function, certain keys refer
to the same path and hence have to be identifed. Therefore, at places
where the keys clearly have to be paths in the file system, implicitly
normalize them and check for conflicts.

6 files changed, 282 insertions, 6 deletions

diff --git a/doc/concepts/rules.org b/doc/concepts/rules.org
index 8c84cb2a..f5cfdd8c 100644
--- a/doc/concepts/rules.org
+++ b/doc/concepts/rules.org
@@ -150,6 +150,14 @@ archiver, etc. The action function takes the following arguments.
   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.
@@ -169,12 +177,16 @@ 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 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.
+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
diff --git a/src/buildtool/build_engine/target_map/target_map.cpp b/src/buildtool/build_engine/target_map/target_map.cpp
index 656223a6..2f5df0b5 100644
--- a/src/buildtool/build_engine/target_map/target_map.cpp
+++ b/src/buildtool/build_engine/target_map/target_map.cpp
@@ -369,6 +369,14 @@ void withDependencies(
                                       input_path)};
                   }
               }
+              auto conflict_or_normal =
+                  BuildMaps::Target::Utils::artifacts_tree(inputs_exp);
+              if (std::holds_alternative<std::string>(conflict_or_normal)) {
+                  throw Evaluator::EvaluationError{
+                      fmt::format("inputs conflict on path {}",
+                                  std::get<std::string>(conflict_or_normal))};
+              }
+              inputs_exp = std::get<ExpressionPtr>(conflict_or_normal);
               auto conflict =
                   BuildMaps::Target::Utils::tree_conflict(inputs_exp);
               if (conflict) {
@@ -677,6 +685,21 @@ void withDependencies(
                                       path)};
                   }
               }
+              auto artifacts_normal =
+                  BuildMaps::Target::Utils::artifacts_tree(artifacts);
+              if (std::holds_alternative<std::string>(artifacts_normal)) {
+                  throw Evaluator::EvaluationError{
+                      fmt::format("artifacts conflict on path {}",
+                                  std::get<std::string>(artifacts_normal))};
+              }
+              artifacts = std::get<ExpressionPtr>(artifacts_normal);
+              auto artifacts_conflict =
+                  BuildMaps::Target::Utils::tree_conflict(artifacts);
+              if (artifacts_conflict) {
+                  throw Evaluator::EvaluationError{
+                      fmt::format("artifacts conflicts on subtree {}",
+                                  *artifacts_conflict)};
+              }
               if (not runfiles->IsMap()) {
                   throw Evaluator::EvaluationError{fmt::format(
                       "runfiles has to be a map of artifacts, but found {}",
@@ -691,6 +714,20 @@ void withDependencies(
                                       path)};
                   }
               }
+              auto runfiles_normal =
+                  BuildMaps::Target::Utils::artifacts_tree(runfiles);
+              if (std::holds_alternative<std::string>(runfiles_normal)) {
+                  throw Evaluator::EvaluationError{
+                      fmt::format("runfiles conflict on path {}",
+                                  std::get<std::string>(runfiles_normal))};
+              }
+              runfiles = std::get<ExpressionPtr>(runfiles_normal);
+              auto runfiles_conflict =
+                  BuildMaps::Target::Utils::tree_conflict(runfiles);
+              if (runfiles_conflict) {
+                  throw Evaluator::EvaluationError{fmt::format(
+                      "runfiles conflicts on subtree {}", *runfiles_conflict)};
+              }
               if (not provides->IsMap()) {
                   throw Evaluator::EvaluationError{
                       fmt::format("provides has to be a map, but found {}",
diff --git a/src/buildtool/build_engine/target_map/utils.cpp b/src/buildtool/build_engine/target_map/utils.cpp
index 2368f03e..bdd5dd11 100644
--- a/src/buildtool/build_engine/target_map/utils.cpp
+++ b/src/buildtool/build_engine/target_map/utils.cpp
@@ -75,6 +75,20 @@ auto BuildMaps::Target::Utils::keys_expr(const ExpressionPtr& map)
     return ExpressionPtr{result};
 }
 
+auto BuildMaps::Target::Utils::artifacts_tree(const ExpressionPtr& map)
+    -> std::variant<std::string, ExpressionPtr> {
+    auto result = Expression::map_t::underlying_map_t{};
+    for (auto const& [key, artifact] : map->Map()) {
+        auto location = ToNormalPath(std::filesystem::path{key}).string();
+        if (auto it = result.find(location);
+            it != result.end() && !(it->second == artifact)) {
+            return location;
+        }
+        result.emplace(std::move(location), artifact);
+    }
+    return ExpressionPtr{Expression::map_t{result}};
+}
+
 auto BuildMaps::Target::Utils::tree_conflict(const ExpressionPtr& map)
     -> std::optional<std::string> {
     std::vector<std::filesystem::path> trees{};
diff --git a/src/buildtool/build_engine/target_map/utils.hpp b/src/buildtool/build_engine/target_map/utils.hpp
index 96bfd1fa..2d6690c1 100644
--- a/src/buildtool/build_engine/target_map/utils.hpp
+++ b/src/buildtool/build_engine/target_map/utils.hpp
@@ -3,6 +3,7 @@
 
 #include <optional>
 #include <unordered_map>
+#include <variant>
 
 #include "gsl-lite/gsl-lite.hpp"
 #include "src/buildtool/build_engine/analysed_target/analysed_target.hpp"
@@ -35,6 +36,9 @@ auto obtainTarget(const SubExprEvaluator&,
 
 auto keys_expr(const ExpressionPtr& map) -> ExpressionPtr;
 
+auto artifacts_tree(const ExpressionPtr& map)
+    -> std::variant<std::string, ExpressionPtr>;
+
 auto tree_conflict(const ExpressionPtr& /* map */)
     -> std::optional<std::string>;
 
diff --git a/test/end-to-end/actions/TARGETS b/test/end-to-end/actions/TARGETS
index 9575d724..f8aa354f 100644
--- a/test/end-to-end/actions/TARGETS
+++ b/test/end-to-end/actions/TARGETS
@@ -12,6 +12,15 @@
   , "keep": ["blobs.json", "trees.json", "out/index.txt"]
   , "deps": [["test/end-to-end", "tool-under-test"]]
   }
+, "conflicts":
+  { "type": ["@", "rules", "shell/test", "script"]
+  , "name": ["conflicts"]
+  , "test": ["conflicts.sh"]
+  , "deps": [["test/end-to-end", "tool-under-test"]]
+  }
 , "TESTS":
-  {"type": "install", "tainted": ["test"], "deps": ["equality", "trees"]}
+  { "type": "install"
+  , "tainted": ["test"]
+  , "deps": ["equality", "trees", "conflicts"]
+  }
 }
diff --git a/test/end-to-end/actions/conflicts.sh b/test/end-to-end/actions/conflicts.sh
new file mode 100755
index 00000000..089e742a
--- /dev/null
+++ b/test/end-to-end/actions/conflicts.sh
@@ -0,0 +1,200 @@
+#!/bin/sh
+set -e
+
+touch ROOT
+cat > RULES <<'EOI'
+{ "no-conflict":
+  { "expression":
+    { "type": "let*"
+    , "bindings":
+      [ [ "map"
+        , { "type": "map_union"
+          , "$1":
+            [ { "type": "singleton_map"
+              , "key": "foo.txt"
+              , "value": {"type": "BLOB", "data": "Same String"}
+              }
+            , { "type": "singleton_map"
+              , "key": "./foo.txt"
+              , "value": {"type": "BLOB", "data": "Same String"}
+              }
+            ]
+          }
+        ]
+      , [ "out"
+        , { "type": "ACTION"
+          , "inputs": {"type": "var", "name": "map"}
+          , "outs": ["out"]
+          , "cmd": ["cp", "foo.txt", "out"]
+          }
+        ]
+      ]
+    , "body": {"type": "RESULT", "artifacts": {"type": "var", "name": "out"}}
+    }
+  }
+, "input-conflict":
+  { "expression":
+    { "type": "let*"
+    , "bindings":
+      [ [ "map"
+        , { "type": "map_union"
+          , "$1":
+            [ { "type": "singleton_map"
+              , "key": "foo.txt"
+              , "value": {"type": "BLOB", "data": "Some content"}
+              }
+            , { "type": "singleton_map"
+              , "key": "./foo.txt"
+              , "value": {"type": "BLOB", "data": "A different content"}
+              }
+            ]
+          }
+        ]
+      , [ "out"
+        , { "type": "ACTION"
+          , "inputs": {"type": "var", "name": "map"}
+          , "outs": ["out"]
+          , "cmd": ["cp", "foo.txt", "out"]
+          }
+        ]
+      ]
+    , "body": {"type": "RESULT", "artifacts": {"type": "var", "name": "out"}}
+    }
+  }
+, "artifacts-conflict":
+  { "expression":
+    { "type": "RESULT"
+    , "artifacts":
+      { "type": "map_union"
+      , "$1":
+        [ { "type": "singleton_map"
+          , "key": "foo.txt"
+          , "value": {"type": "BLOB", "data": "Some content"}
+          }
+        , { "type": "singleton_map"
+          , "key": "./foo.txt"
+          , "value": {"type": "BLOB", "data": "A different content"}
+          }
+        ]
+      }
+    }
+  }
+, "runfiles-conflict":
+  { "expression":
+    { "type": "RESULT"
+    , "runfiles":
+      { "type": "map_union"
+      , "$1":
+        [ { "type": "singleton_map"
+          , "key": "foo.txt"
+          , "value": {"type": "BLOB", "data": "Some content"}
+          }
+        , { "type": "singleton_map"
+          , "key": "./foo.txt"
+          , "value": {"type": "BLOB", "data": "A different content"}
+          }
+        ]
+      }
+    }
+  }
+, "input-tree-conflict":
+  { "expression":
+    { "type": "let*"
+    , "bindings":
+      [ [ "map"
+        , { "type": "map_union"
+          , "$1":
+            [ { "type": "singleton_map"
+              , "key": "foo"
+              , "value": {"type": "TREE"}
+              }
+            , { "type": "singleton_map"
+              , "key": "./foo/bar.txt"
+              , "value": {"type": "BLOB"}
+              }
+            ]
+          }
+        ]
+      , [ "out"
+        , { "type": "ACTION"
+          , "inputs": {"type": "var", "name": "map"}
+          , "outs": ["out"]
+          , "cmd": ["cp", "foo.txt", "out"]
+          }
+        ]
+      ]
+    , "body": {"type": "RESULT", "artifacts": {"type": "var", "name": "out"}}
+    }
+  }
+, "artifacts-tree-conflict":
+  { "expression":
+    { "type": "RESULT"
+    , "artifacts":
+      { "type": "map_union"
+      , "$1":
+        [ {"type": "singleton_map", "key": "foo", "value": {"type": "TREE"}}
+        , { "type": "singleton_map"
+          , "key": "./foo/bar.txt"
+          , "value": {"type": "BLOB"}
+          }
+        ]
+      }
+    }
+  }
+, "runfiles-tree-conflict":
+  { "expression":
+    { "type": "RESULT"
+    , "runfiles":
+      { "type": "map_union"
+      , "$1":
+        [ {"type": "singleton_map", "key": "foo", "value": {"type": "TREE"}}
+        , { "type": "singleton_map"
+          , "key": "./foo/bar.txt"
+          , "value": {"type": "BLOB"}
+          }
+        ]
+      }
+    }
+  }
+}
+EOI
+cat > TARGETS <<'EOI'
+{ "no-conflict": {"type": "no-conflict"}
+, "input-conflict": {"type": "input-conflict"}
+, "artifacts-conflict": {"type": "artifacts-conflict"}
+, "runfiles-conflict": {"type": "runfiles-conflict"}
+, "input-tree-conflict": {"type": "input-tree-conflict"}
+, "artifacts-tree-conflict": {"type": "artifacts-tree-conflict"}
+, "runfiles-tree-conflict": {"type": "runfiles-tree-conflict"}
+}
+EOI
+
+echo
+./bin/tool-under-test analyse no-conflict --dump-actions - 2>&1
+
+echo
+./bin/tool-under-test analyse -f log input-conflict 2>&1 && exit 1 || :
+grep -i 'error.*input.*conflict.*foo\.txt' log
+
+echo
+./bin/tool-under-test analyse -f log artifacts-conflict 2>&1 && exit 1 || :
+grep -i 'error.*artifacts.*conflict.*foo\.txt' log
+
+echo
+./bin/tool-under-test analyse -f log runfiles-conflict 2>&1 && exit 1 || :
+grep -i 'error.*runfiles.*conflict.*foo\.txt' log
+
+echo
+./bin/tool-under-test analyse -f log input-tree-conflict 2>&1 && exit 1 || :
+grep -i 'error.*input.*conflict.*tree.*foo' log
+
+echo
+./bin/tool-under-test analyse -f log artifacts-tree-conflict 2>&1 && exit 1 || :
+grep -i 'error.*artifacts.*conflict.*tree.*foo' log
+
+echo
+./bin/tool-under-test analyse -f log runfiles-tree-conflict 2>&1 && exit 1 || :
+grep -i 'error.*runfiles.*conflict.*tree.*foo' log
+
+echo
+echo DONE