[cross-repo] Make atomic changes also respect other dependencies

Bug: 421245215
Change-Id: I5bb0169c137d9c7db271050e2bd40edbaa17dcf5
Reviewed-on: https://fuchsia-review.googlesource.com/c/infra/recipes/+/1290604
Reviewed-by: Oliver Newman <olivernewman@google.com>
Commit-Queue: Jiaming Li <lijiaming@google.com>
diff --git a/recipe_modules/checkout/api.py b/recipe_modules/checkout/api.py
index 857a585..2cc967d 100644
--- a/recipe_modules/checkout/api.py
+++ b/recipe_modules/checkout/api.py
@@ -1243,15 +1243,16 @@
         dependencies = self.m.gerrit_dependency_satisfy.read_depends_on_footers(
             commit_message, gerrit_host
         )
-        for dependency in dependencies:
+        for host, change_id in dependencies:
             try:
+                host_id = self.m.gerrit.host_basename(host)
                 changes = self.m.gerrit.change_query(
-                    f"get dependency status for {dependency.host_id}:{dependency.change_id}",
+                    f"get dependency status for {host_id}:{change_id}",
                     # The same Change-Id may appear on multiple branches. Make
                     # sure to only look at changes on the same branch as the
                     # current CL.
-                    f"change:{dependency.change_id} branch:{change_details['branch']}",
-                    host=dependency.host,
+                    f"change:{change_id} branch:{change_details['branch']}",
+                    host=host,
                     query_params=[
                         "ALL_REVISIONS",
                         "CURRENT_COMMIT",
@@ -1295,7 +1296,7 @@
 
             depends_on_patches[key].extend(
                 self._recursively_collect_dependencies(
-                    changes[0], dependency.host, depends_on_patches
+                    changes[0], host, depends_on_patches
                 )
             )
 
diff --git a/recipe_modules/gerrit_dependency_satisfy/api.py b/recipe_modules/gerrit_dependency_satisfy/api.py
index 64fb285..a520322 100644
--- a/recipe_modules/gerrit_dependency_satisfy/api.py
+++ b/recipe_modules/gerrit_dependency_satisfy/api.py
@@ -37,23 +37,41 @@
 
 
 # The return type of api.gerrit.change.change_details().
-Change = dict[str, Any]
+ChangeDetails = dict[str, Any]
+
+
+class BadDependOnException(Exception):
+    """Custom exception raised for bad depends-on footer relationships."""
+
+    def __init__(self, message: str):
+        self.message = message
+        super().__init__(self.message)
+
+    def __str__(self):
+        return f"{type(self).__name__}: Reason: {self.message}"
 
 
 @dataclasses.dataclass
-class Dependency:
-    # Short host name, e.g. "fuchsia".
-    host_id: str
-    change_id: str
+class Change:
+    host: str
+    details: ChangeDetails
 
-    @property
-    def host(self):
-        return f"{self.host_id}-review.googlesource.com"
+    def _key(self):
+        return self.host + ":" + self.details["change_id"]
+
+    def __hash__(self):
+        return hash(self._key())
+
+    def __lt__(self, other: Change) -> bool:
+        return self._key() < other._key()
+
+    def _get_change_url(self) -> str:
+        return f"https://{self.host}/c/{self.details['project']}/+/{self.details['_number']}"
 
 
 class GerritDependencySatisfyApi(recipe_api.RecipeApi):
     def __call__(self, opts: options.Options, dry_run: bool) -> result_pb2.RawResult:
-        results = collections.defaultdict(list)
+        results: dict[str, list[str]] = collections.defaultdict(list)
 
         finish_time = self.m.time.time() + opts.repeat_duration_seconds
 
@@ -98,30 +116,20 @@
                 for change in self._get_eligible_changes(gerrit_host, max_attempts):
                     change_id = self.m.url.unquote(change["id"])
                     with self.m.step.nest(f"change {change_id}") as presentation:
-                        presentation.step_text = self._get_change_url(
-                            gerrit_host, change
-                        )
-                        if not self._check_all_dependencies_submitted(
+                        change_info = Change(gerrit_host, change)
+                        presentation.step_text = change_info._get_change_url()
+                        if self._validate_all_dependencies(
                             opts, gerrit_host, change, dry_run
                         ):
-                            continue
-
-                        self._set_dependency_satisfied(gerrit_host, change, dry_run)
-
-                    labeled_changes.append(change)
-                    results[gerrit_host].append(
-                        self._get_change_url(gerrit_host, change)
-                    )
+                            labeled_changes.append(change_info)
+                            results[gerrit_host].append(change_info._get_change_url())
         return labeled_changes
 
-    def _get_change_url(self, gerrit_host: str, change: Change) -> str:
-        return f"https://{gerrit_host}/c/{change['project']}/+/{change['_number']}"
-
     def _get_eligible_changes(
         self,
         gerrit_host: str,
         max_attempts: int,
-    ) -> list[Change]:
+    ) -> list[ChangeDetails]:
         raw_query = " ".join(
             [
                 "is:open",
@@ -147,37 +155,40 @@
             test_data=self.m.json.test_api.output([]),
         ).json.output
 
-    def _set_dependency_satisfied(
-        self, gerrit_host: str, change: Change, dry_run: bool
-    ):
+    def _set_dependency_satisfied(self, change: Change, dry_run: bool):
         if dry_run:
             return self.m.step.empty("dry run, skipping setting DS+1")
 
         self.m.gerrit.set_review(
             name="set Dependencies-Satisfied +1",
-            change_id=self.m.url.unquote(change["id"]),
+            change_id=self.m.url.unquote(change.details["id"]),
             labels={"Dependencies-Satisfied": 1},
-            host=gerrit_host,
+            host=change.host,
             notify="NONE",
             ok_ret="any",
             timeout=GERRIT_TIMEOUT,
         )
 
-    def _set_cq_plus_one(self, gerrit_host: str, change: Change):
+    def _set_cq_plus_one(self, change: Change):
         self.m.gerrit.set_review(
             name="set CQ +1",
-            change_id=self.m.url.unquote(change["id"]),
+            change_id=self.m.url.unquote(change.details["id"]),
             labels={"Commit-Queue": 1},
-            host=gerrit_host,
+            host=change.host,
             notify="NONE",
             ok_ret="any",
-            on_behalf_of=change["owner"]["_account_id"],
+            on_behalf_of=change.details["owner"]["_account_id"],
             timeout=GERRIT_TIMEOUT,
         )
 
     def _send_change_id_error_comment(
-        self, change_id, gerrit_host, message, parent_change_id
-    ):
+        self,
+        change_id: str,
+        gerrit_host: str,
+        message: str,
+        parent_change_id: str,
+        dry_run: bool,
+    ) -> str:
         full_error_comment = (
             f"`{change_id}` {message}\n"
             "The Depends-on footer value should come from the dependency's Change-Id footer. Example supported formats:\n\n"
@@ -185,170 +196,79 @@
             "- `fuchsia:I8473b95934b5732ac55d26311a706c9c2bde9939`\n"
             "- `turquoise-internal:I8473b95934b5732ac55d26311a706c9c2bde9939`"
         )
-        self.m.gerrit.set_review(
-            "send comments",
-            change_id=parent_change_id,
-            host=gerrit_host,
-            message=full_error_comment,
-            notify="OWNER",
-            tag=BAD_DEPENDS_ON_TAG,
-        )
-
-    def _check_dependency_submitted(
-        self,
-        opts: options.Options,
-        dependency: Dependency,
-        parent_change: Change,
-        parent_gerrit_host: str,
-        dry_run: bool,
-    ) -> bool:
-        parent_cl_change_id = self.m.url.unquote(parent_change["id"])
-        # Fail early if the change_id is malformed
-        if not dependency.change_id.startswith("I"):
-            # The given change_id is malformed
-            message = "is not a valid Depends-on format."
-            self._send_change_id_error_comment(
-                dependency.change_id,
-                parent_gerrit_host,
-                message,
-                parent_cl_change_id,
+        if dry_run:
+            step = self.m.step.empty("dry run, sending comments")
+            step.presentation.logs["comment"] = full_error_comment
+        else:
+            self.m.gerrit.set_review(
+                "send comments",
+                change_id=parent_change_id,
+                host=gerrit_host,
+                message=full_error_comment,
+                notify="OWNER",
+                tag=BAD_DEPENDS_ON_TAG,
             )
-            return False
-
-        if dependency.host not in opts.gerrit_hosts:
-            message = f"uses an invalid Gerrit host shortname {dependency.host_id!r}."
-            self._send_change_id_error_comment(
-                dependency.change_id,
-                parent_gerrit_host,
-                message,
-                parent_cl_change_id,
-            )
-            return False
-
-        changes = self.m.gerrit.change_query(
-            f"get dependency status for {dependency.host_id}:{dependency.change_id}",
-            f"change:{dependency.change_id}",
-            host=dependency.host,
-            query_params=DEFAULT_QUERY_PARAMS,
-            # Only attempt one request; if it fails, we'll retry on
-            # a subsequent dependency check iteration.
-            max_attempts=1,
-            timeout=GERRIT_TIMEOUT,
-            test_data=self.m.json.test_api.output([{"status": "MERGED"}]),
-        ).json.output
-
-        parent_branch = self.m.url.unquote(parent_change["branch"])
-
-        if len(changes) > 1:
-            # If the CL got cherry-picked onto multiple branches, assume the
-            # footer is referring to the one on the same branch as the parent
-            # CL.
-            changes = [c for c in changes if c["branch"] == parent_branch]
-
-        if not changes:
-            message = "cannot be found."
-            self._send_change_id_error_comment(
-                dependency.change_id, parent_gerrit_host, message, parent_cl_change_id
-            )
-            return False
-
-        # Even after filtering by branch, it's possible that a change ID matches
-        # multiple CLs in different repositories.
-        if len(changes) > 1:
-            message = "matches multiple CLs."
-            self._send_change_id_error_comment(
-                dependency.change_id, parent_gerrit_host, message, parent_cl_change_id
-            )
-            return False
-
-        if changes[0]["status"] == "MERGED":
-            return True
-
-        # Check and process circular dependencies
-        self._check_circular_dependency(
-            changes[0], dependency.host, parent_change, parent_gerrit_host, dry_run
-        )
-
-        return False
-
-    def _check_circular_dependency(
-        self,
-        change: Change,
-        gerrit_host: str,
-        parent_change: Change,
-        parent_gerrit_host: str,
-        dry_run: bool,
-    ):
-        # Check if any of the footer matches the parent cl change id
-        current_revision = change["current_revision"]
-        commit_message = change["revisions"][current_revision]["commit"]["message"]
-
-        dependencies = self.read_depends_on_footers(commit_message, gerrit_host)
-        for dep in dependencies:
-            if dep.change_id == self.m.url.unquote(parent_change["change_id"]):
-                self.m.step.empty("detected atomic changes")
-                self._process_atomic_changes(
-                    change, gerrit_host, parent_change, parent_gerrit_host, dry_run
-                )
+        return full_error_comment
 
     def _process_atomic_changes(
         self,
-        change: Change,
-        gerrit_host: str,
-        parent_change: Change,
-        parent_gerrit_host: str,
+        atomic_set: list[Change],
         dry_run: bool,
-    ):
-        change_infos = [(change, gerrit_host), (parent_change, parent_gerrit_host)]
+    ) -> bool:
+        self.m.step.empty("detect atomic changes")
         # Check the eligibility for each of the changes.
-        for change_detail, host in change_infos:
+        for change in atomic_set:
             # Check submission requirements are satisfied except Dependencies-Satisfied. The name of
             # the requirements needs to be kept in sync with submit-requirement entry in Gerrit
             # project.config file. e.g.:
             # https://fuchsia.googlesource.com/All-Projects/+/029c0515d9a0c2ea43d20fbcccb33ebec4b8fbab/project.config#256
-            for requirement in change_detail["submit_requirements"]:
+            details = change.details
+            gerrit_host = change.host
+            for requirement in details["submit_requirements"]:
                 if (
                     requirement["status"] == "UNSATISFIED"
                     and requirement["name"] != "Dependencies-Satisfied"
                 ):
                     self.m.step.empty("pending submit requirements")
-                    return
+                    return False
 
             # If Auto-submit is not set, leave a comment to the CL and return early.
             # If latest message has the NO_AUTO_SUBMIT_TAG, the deps are already checked. We don't
             # repeatedly send comments.
-            if "approved" not in change_detail["labels"].get("Fuchsia-Auto-Submit", {}):
+            if "approved" not in details["labels"].get("Fuchsia-Auto-Submit", {}):
                 if not self._check_latest_message_has_bad_tag(
-                    change, NO_AUTO_SUBMIT_TAG
+                    details, NO_AUTO_SUBMIT_TAG
                 ):
                     self.m.gerrit.set_review(
                         "send auto-submit comments",
-                        change_id=self.m.url.unquote(change_detail["id"]),
-                        host=host,
+                        change_id=self.m.url.unquote(details["id"]),
+                        host=gerrit_host,
                         message="Circular dependency detected, please enable Auto-Submit for atomic submission",
                         notify="OWNER",
                         tag=NO_AUTO_SUBMIT_TAG,
                     )
-                return
+                return False
 
         # Do a presubmit dry run on the changes.
         all_dry_runs_succeeded = True
-        for change_detail, host in change_infos:
+        for change in atomic_set:
             # Make sure there are recent green CV runs for both CLs, to ensure that when auto-submit
             # sets CQ+2 on them, they both submit quickly to minimize the risk of roller blockages.
             project = "turquoise"
-            change_number = change_detail["_number"]
-            patchset = change_detail["current_revision_number"]
+            deatils = change.details
+            gerrit_host = change.host
+            change_number = deatils["_number"]
+            patchset = deatils["current_revision_number"]
             cv_runs = self.m.change_verifier.search_runs(
                 project,
-                (host, change_number),
-                step_name=f"fetch CV status for {host}/{change_number}",
+                (gerrit_host, change_number),
+                step_name=f"fetch CV status for {gerrit_host}/{change_number}",
             )
 
             # If the last CV is not against latest patchset, or not succeeded,
             # trigger a CQ run and return early
             if not cv_runs:
-                self._set_cq_plus_one(host, change_detail)
+                self._set_cq_plus_one(change)
                 all_dry_runs_succeeded = False
                 continue
 
@@ -368,15 +288,18 @@
             ):
                 # If there is no CV running, trigger a new CQ
                 if run_status != run_pb.Run.RUNNING:
-                    self._set_cq_plus_one(host, change_detail)
+                    self._set_cq_plus_one(change)
                 all_dry_runs_succeeded = False
                 continue
 
-        if all_dry_runs_succeeded:
-            # Add label to each of the changes if all the requirements above are
-            # satisfied.
-            for change_detail, host in change_infos:
-                self._set_dependency_satisfied(host, change_detail, dry_run)
+        if not all_dry_runs_succeeded:
+            return False
+
+        # Add label to each of the changes if all the requirements above are
+        # satisfied.
+        for change in atomic_set:
+            self._set_dependency_satisfied(change, dry_run)
+        return True
 
     def _check_latest_message_has_bad_tag(self, details: dict[str, Any], tag: str):
         current_revision_number = details["current_revision_number"]
@@ -389,31 +312,205 @@
                 return True
         return False
 
-    def _check_all_dependencies_submitted(
-        self, opts: options.Options, gerrit_host: str, change: Change, dry_run: bool
+    def _validate_all_dependencies(
+        self,
+        opts: options.Options,
+        gerrit_host: str,
+        change: ChangeDetails,
+        dry_run: bool,
     ) -> bool:
         # If latest message has the BAD_DEPENDS_ON_TAG, the deps are already checked.
         if self._check_latest_message_has_bad_tag(change, BAD_DEPENDS_ON_TAG):
             return False
 
+        try:
+            atomic_set, dependency_set = self._collect_dependencies(
+                gerrit_host, change, opts, dry_run
+            )
+            atomic_urls = [c._get_change_url() for c in atomic_set]
+            dependency_urls = [c._get_change_url() for c in dependency_set]
+            presentation = self.m.step.empty("resolved dependencies").presentation
+            for url in atomic_urls:
+                presentation.links[f"{url} (circular)"] = url
+            for url in dependency_urls:
+                presentation.links[f"{url} (one-way)"] = url
+        except BadDependOnException as e:  # pragma: no cover
+            self.m.step.empty("found bad Depends-on footer").presentation.step_text = (
+                str(e)
+            )
+            return False
+
+        # Check if all changes in dependency_set are submitted
+        for dep in dependency_set:
+            if dep.details["status"] != "MERGED":
+                self.m.step.empty("dependency not satisfied").presentation.links[
+                    "CL"
+                ] = dep._get_change_url()
+                return False
+
+        if len(atomic_set) == 1:
+            # If there is only one change in atomic_set, we can directly set
+            # the DS+1
+            self._set_dependency_satisfied(atomic_set[0], dry_run)
+            return True
+        else:
+            return self._process_atomic_changes(atomic_set, dry_run)
+
+    def _collect_dependencies(
+        self,
+        gerrit_host: str,
+        change: ChangeDetails,
+        opts: options.Options,
+        dryrun: bool,
+    ) -> tuple[list[Change], list[Change]]:
+        # All the changes that needs to be submitted together are saved in
+        # atomic set, along with change itself. Other dependencies are saved
+        # in dependencies set. Only first layer dependencies of atomic changes
+        # will be considered.
+        #
+        # For instance this is the dependency graph:
+        #
+        #             F
+        #             ^
+        #             |
+        # A <- B <--> C <--> D -> E -> G
+        #
+        # Atomics: {B, C, D}
+        # Dependencies: {A, E, F}
+        #
+        atomic_set: set[Change] = set()
+        dependency_set: set[Change] = set()
+
+        main_change = Change(gerrit_host, change)
+        atomic_stack = [main_change]
+        atomic_change_ids: set[str] = set()
+
+        # Dict to avoid repeated change query
+        change_lookup_dict = {
+            self.m.gerrit.host_basename(main_change.host)
+            + ":"
+            + change["change_id"]: change
+        }
+
+        while atomic_stack:
+            atomic_change = atomic_stack.pop()
+            atomic_set.add(atomic_change)
+            atomic_change_ids.add(atomic_change.details["change_id"])
+            dep_infos = self._collect_dependency_of_one_change(
+                atomic_change, opts, dryrun, change_lookup_dict
+            )
+            for dep_info in dep_infos:
+                # If this is part of atomic set, we push it into the stack so
+                # it can be processed later, otherwise we add this info to
+                # dependency_set
+                if self._check_atomic(dep_info, atomic_change_ids):
+                    if dep_info.details["change_id"] not in atomic_change_ids:
+                        atomic_stack.append(dep_info)
+                else:
+                    dependency_set.add(dep_info)
+
+        return sorted(atomic_set), sorted(dependency_set)
+
+    def _check_atomic(self, dep_info: Change, atomic_change_ids: set[str]) -> bool:
+        change = dep_info.details
+        current_revision = change["current_revision"]
+        commit_message = change["revisions"][current_revision]["commit"]["message"]
+
+        # If any of the footer matches cl in the atomic changes set, this is
+        # part of atomic set
+        for _, change_id in self.read_depends_on_footers(commit_message, dep_info.host):
+            if change_id in atomic_change_ids:
+                return True
+        return False
+
+    def _collect_dependency_of_one_change(
+        self,
+        change_info: Change,
+        opts: options.Options,
+        dry_run: bool,
+        change_lookup_dict: dict[str, ChangeDetails],
+    ) -> set[Change]:
+        change = change_info.details
+        gerrit_host = change_info.host
+        change_id = self.m.url.unquote(change["id"])
         current_revision = change["current_revision"]
         commit_message = change["revisions"][current_revision]["commit"]["message"]
 
         # Each Depends-on footer map to one CL this change depends on
         dependencies = self.read_depends_on_footers(commit_message, gerrit_host)
 
-        for dependency in dependencies:
-            # If any of the dependency is not submitted, we return False
-            if not self._check_dependency_submitted(
-                opts, dependency, change, gerrit_host, dry_run
-            ):
-                return False
+        dep_infos = set()
 
-        return True
+        for dep_host, dep_change_id in dependencies:
+            host_id = self.m.gerrit.host_basename(dep_host)
+            lookup_key = host_id + ":" + dep_change_id
+
+            # If we already looked up this change Id, avoid re-querying
+            if lookup_key in change_lookup_dict:
+                dep_infos.add(Change(dep_host, change_lookup_dict[lookup_key]))
+                continue
+
+            # Fail early if the change_id is malformed
+            if not dep_change_id.startswith("I"):
+                # The given change_id is malformed
+                message = "is not a valid Depends-on format."
+                full_error_comment = self._send_change_id_error_comment(
+                    dep_change_id, gerrit_host, message, change_id, dry_run
+                )
+                raise BadDependOnException(full_error_comment)
+
+            if dep_host not in opts.gerrit_hosts:
+                message = f"uses an invalid Gerrit host shortname {host_id!r}. Supported gerrit_hosts: {opts.gerrit_hosts}"
+                full_error_comment = self._send_change_id_error_comment(
+                    dep_change_id, gerrit_host, message, change_id, dry_run
+                )
+                raise BadDependOnException(full_error_comment)
+
+            changes = self.m.gerrit.change_query(
+                f"get dependency status for {lookup_key}",
+                f"change:{dep_change_id}",
+                host=dep_host,
+                query_params=DEFAULT_QUERY_PARAMS,
+                # Only attempt one request; if it fails, we'll retry on
+                # a subsequent dependency check iteration.
+                max_attempts=1,
+                timeout=GERRIT_TIMEOUT,
+                test_data=self.m.json.test_api.output([{"status": "MERGED"}]),
+            ).json.output
+
+            parent_branch = self.m.url.unquote(change["branch"])
+
+            if len(changes) > 1:
+                # If the CL got cherry-picked onto multiple branches, assume the
+                # footer is referring to the one on the same branch as the parent
+                # CL.
+                changes = [c for c in changes if c["branch"] == parent_branch]
+
+            if not changes:
+                message = "cannot be found."
+                full_error_comment = self._send_change_id_error_comment(
+                    dep_change_id, gerrit_host, message, change_id, dry_run
+                )
+                raise BadDependOnException(full_error_comment)
+
+            # Even after filtering by branch, it's possible that a change ID matches
+            # multiple CLs in different repositories.
+            if len(changes) > 1:
+                message = "matches multiple CLs."
+                full_error_comment = self._send_change_id_error_comment(
+                    dep_change_id, gerrit_host, message, change_id, dry_run
+                )
+                raise BadDependOnException(full_error_comment)
+            dep_infos.add(Change(dep_host, changes[0]))
+
+            # Update lookup dict
+            change_lookup_dict[lookup_key] = changes[0]
+
+        return dep_infos
 
     def read_depends_on_footers(
         self, commit_msg: str, gerrit_host: str
-    ) -> list[Dependency]:
+    ) -> list[tuple[str, str]]:
         dependencies = []
         footers = self.m.git.read_commit_footer_multi(commit_msg, "Depends-on")
         for footer in footers:
@@ -423,13 +520,13 @@
             #   Depends-on: turquoise-internal:I9916ccaa4b95b6e9babdee33014fa6bd3d478f2e
             #
             if ":" not in footer:
-                host_id = self.m.gerrit.host_basename(gerrit_host)
+                dep_host = gerrit_host
                 change_id = footer
             else:
                 splits = footer.split(":")
-                host_id = splits[0]
+                dep_host = splits[0] + "-review.googlesource.com"
                 change_id = splits[1].strip()
-            dependencies.append(Dependency(host_id=host_id, change_id=change_id))
+            dependencies.append((dep_host, change_id))
 
         return dependencies
 
diff --git a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/depends_on_footer_disallowed_host.json b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/depends_on_footer_disallowed_host.json
index d141d38..d4a222b 100644
--- a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/depends_on_footer_disallowed_host.json
+++ b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/depends_on_footer_disallowed_host.json
@@ -214,7 +214,7 @@
       "-host",
       "https://other-review.googlesource.com",
       "-input",
-      "{\"change_id\": \"myProject~3965\", \"input\": {\"message\": \"`I12345` uses an invalid Gerrit host shortname 'disallowed-host'.\\nThe Depends-on footer value should come from the dependency's Change-Id footer. Example supported formats:\\n\\n- `I8473b95934b5732ac55d26311a706c9c2bde9939`\\n- `fuchsia:I8473b95934b5732ac55d26311a706c9c2bde9939`\\n- `turquoise-internal:I8473b95934b5732ac55d26311a706c9c2bde9939`\", \"notify\": \"OWNER\", \"tag\": \"autogenerated:cl-deps-checker:bad-depends-on\"}, \"revision_id\": \"current\"}",
+      "{\"change_id\": \"myProject~3965\", \"input\": {\"message\": \"`I12345` uses an invalid Gerrit host shortname 'disallowed-host'. Supported gerrit_hosts: ['fuchsia-review.googlesource.com', 'other-review.googlesource.com']\\nThe Depends-on footer value should come from the dependency's Change-Id footer. Example supported formats:\\n\\n- `I8473b95934b5732ac55d26311a706c9c2bde9939`\\n- `fuchsia:I8473b95934b5732ac55d26311a706c9c2bde9939`\\n- `turquoise-internal:I8473b95934b5732ac55d26311a706c9c2bde9939`\", \"notify\": \"OWNER\", \"tag\": \"autogenerated:cl-deps-checker:bad-depends-on\"}, \"revision_id\": \"current\"}",
       "-output",
       "/path/to/tmp/json"
     ],
@@ -229,7 +229,7 @@
       "@@@STEP_LOG_LINE@json.input@{@@@",
       "@@@STEP_LOG_LINE@json.input@  \"change_id\": \"myProject~3965\",@@@",
       "@@@STEP_LOG_LINE@json.input@  \"input\": {@@@",
-      "@@@STEP_LOG_LINE@json.input@    \"message\": \"`I12345` uses an invalid Gerrit host shortname 'disallowed-host'.\\nThe Depends-on footer value should come from the dependency's Change-Id footer. Example supported formats:\\n\\n- `I8473b95934b5732ac55d26311a706c9c2bde9939`\\n- `fuchsia:I8473b95934b5732ac55d26311a706c9c2bde9939`\\n- `turquoise-internal:I8473b95934b5732ac55d26311a706c9c2bde9939`\",@@@",
+      "@@@STEP_LOG_LINE@json.input@    \"message\": \"`I12345` uses an invalid Gerrit host shortname 'disallowed-host'. Supported gerrit_hosts: ['fuchsia-review.googlesource.com', 'other-review.googlesource.com']\\nThe Depends-on footer value should come from the dependency's Change-Id footer. Example supported formats:\\n\\n- `I8473b95934b5732ac55d26311a706c9c2bde9939`\\n- `fuchsia:I8473b95934b5732ac55d26311a706c9c2bde9939`\\n- `turquoise-internal:I8473b95934b5732ac55d26311a706c9c2bde9939`\",@@@",
       "@@@STEP_LOG_LINE@json.input@    \"notify\": \"OWNER\",@@@",
       "@@@STEP_LOG_LINE@json.input@    \"tag\": \"autogenerated:cl-deps-checker:bad-depends-on\"@@@",
       "@@@STEP_LOG_LINE@json.input@  },@@@",
@@ -240,6 +240,14 @@
     ]
   },
   {
+    "cmd": [],
+    "name": "other.change myProject~3965.found bad Depends-on footer",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@",
+      "@@@STEP_TEXT@BadDependOnException: Reason: `I12345` uses an invalid Gerrit host shortname 'disallowed-host'. Supported gerrit_hosts: ['fuchsia-review.googlesource.com', 'other-review.googlesource.com']<br/>The Depends-on footer value should come from the dependency's Change-Id footer. Example supported formats:<br/><br/>- `I8473b95934b5732ac55d26311a706c9c2bde9939`<br/>- `fuchsia:I8473b95934b5732ac55d26311a706c9c2bde9939`<br/>- `turquoise-internal:I8473b95934b5732ac55d26311a706c9c2bde9939`@@@"
+    ]
+  },
+  {
     "name": "$result"
   }
 ]
\ No newline at end of file
diff --git a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/dry_run_multiple.json b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/dry_run_multiple.json
index de6e61b..71527ed 100644
--- a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/dry_run_multiple.json
+++ b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/dry_run_multiple.json
@@ -212,6 +212,7 @@
       "@@@STEP_LOG_LINE@json.output@    \"owner\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"_account_id\": 3873@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"project\": \"myProject\",@@@",
       "@@@STEP_LOG_LINE@json.output@    \"revisions\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"27cc4558b5a3d3387dd11ee2df7a117e7e581822\": {@@@",
       "@@@STEP_LOG_LINE@json.output@        \"commit\": {@@@",
@@ -250,6 +251,23 @@
   },
   {
     "cmd": [],
+    "name": "fuchsia.change myProject~3965.resolved dependencies",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@",
+      "@@@STEP_LINK@https://fuchsia-review.googlesource.com/c/myProject/+/3965 (circular)@https://fuchsia-review.googlesource.com/c/myProject/+/3965@@@",
+      "@@@STEP_LINK@https://fuchsia-review.googlesource.com/c/myProject/+/13532 (one-way)@https://fuchsia-review.googlesource.com/c/myProject/+/13532@@@"
+    ]
+  },
+  {
+    "cmd": [],
+    "name": "fuchsia.change myProject~3965.dependency not satisfied",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@",
+      "@@@STEP_LINK@CL@https://fuchsia-review.googlesource.com/c/myProject/+/13532@@@"
+    ]
+  },
+  {
+    "cmd": [],
     "name": "other"
   },
   {
@@ -373,6 +391,7 @@
       "@@@STEP_LOG_LINE@json.output@    \"owner\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"_account_id\": 3873@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"project\": \"myProject\",@@@",
       "@@@STEP_LOG_LINE@json.output@    \"revisions\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"27cc4558b5a3d3387dd11ee2df7a117e7e581822\": {@@@",
       "@@@STEP_LOG_LINE@json.output@        \"commit\": {@@@",
@@ -451,6 +470,7 @@
       "@@@STEP_LOG_LINE@json.output@    \"owner\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"_account_id\": 3873@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"project\": \"myProject\",@@@",
       "@@@STEP_LOG_LINE@json.output@    \"revisions\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"27cc4558b5a3d3387dd11ee2df7a117e7e581822\": {@@@",
       "@@@STEP_LOG_LINE@json.output@        \"commit\": {@@@",
@@ -489,6 +509,16 @@
   },
   {
     "cmd": [],
+    "name": "other.change myProject~3965.resolved dependencies",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@",
+      "@@@STEP_LINK@https://other-review.googlesource.com/c/myProject/+/3965 (circular)@https://other-review.googlesource.com/c/myProject/+/3965@@@",
+      "@@@STEP_LINK@https://fuchsia-review.googlesource.com/c/myProject/+/13532 (one-way)@https://fuchsia-review.googlesource.com/c/myProject/+/13532@@@",
+      "@@@STEP_LINK@https://other-review.googlesource.com/c/myProject/+/13532 (one-way)@https://other-review.googlesource.com/c/myProject/+/13532@@@"
+    ]
+  },
+  {
+    "cmd": [],
     "name": "other.change myProject~3965.dry run, skipping setting DS+1",
     "~followup_annotations": [
       "@@@STEP_NEST_LEVEL@2@@@"
diff --git a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/malformed_depends_on_footer.json b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/malformed_depends_on_footer.json
index 110233a..dfc3780 100644
--- a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/malformed_depends_on_footer.json
+++ b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/malformed_depends_on_footer.json
@@ -240,6 +240,14 @@
     ]
   },
   {
+    "cmd": [],
+    "name": "other.change myProject~3965.found bad Depends-on footer",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@",
+      "@@@STEP_TEXT@BadDependOnException: Reason: `123` is not a valid Depends-on format.<br/>The Depends-on footer value should come from the dependency's Change-Id footer. Example supported formats:<br/><br/>- `I8473b95934b5732ac55d26311a706c9c2bde9939`<br/>- `fuchsia:I8473b95934b5732ac55d26311a706c9c2bde9939`<br/>- `turquoise-internal:I8473b95934b5732ac55d26311a706c9c2bde9939`@@@"
+    ]
+  },
+  {
     "name": "$result"
   }
 ]
\ No newline at end of file
diff --git a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/repeat_duration.json b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/repeat_duration.json
index 9d59169..4c7d284 100644
--- a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/repeat_duration.json
+++ b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/repeat_duration.json
@@ -262,6 +262,7 @@
       "@@@STEP_LOG_LINE@json.output@    \"owner\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"_account_id\": 3873@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"project\": \"myProject\",@@@",
       "@@@STEP_LOG_LINE@json.output@    \"revisions\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"27cc4558b5a3d3387dd11ee2df7a117e7e581822\": {@@@",
       "@@@STEP_LOG_LINE@json.output@        \"commit\": {@@@",
@@ -340,6 +341,7 @@
       "@@@STEP_LOG_LINE@json.output@    \"owner\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"_account_id\": 3873@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"project\": \"myProject\",@@@",
       "@@@STEP_LOG_LINE@json.output@    \"revisions\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"27cc4558b5a3d3387dd11ee2df7a117e7e581822\": {@@@",
       "@@@STEP_LOG_LINE@json.output@        \"commit\": {@@@",
@@ -377,6 +379,16 @@
     ]
   },
   {
+    "cmd": [],
+    "name": "0.other.change myProject~3965.resolved dependencies",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@3@@@",
+      "@@@STEP_LINK@https://other-review.googlesource.com/c/myProject/+/3965 (circular)@https://other-review.googlesource.com/c/myProject/+/3965@@@",
+      "@@@STEP_LINK@https://fuchsia-review.googlesource.com/c/myProject/+/13532 (one-way)@https://fuchsia-review.googlesource.com/c/myProject/+/13532@@@",
+      "@@@STEP_LINK@https://other-review.googlesource.com/c/myProject/+/13532 (one-way)@https://other-review.googlesource.com/c/myProject/+/13532@@@"
+    ]
+  },
+  {
     "cmd": [
       "[START_DIR]/cipd_tool/infra/tools/luci/gerrit/0e548aa33f8113a45a5b3b62201e114e98e63d00f97296912380138f44597b07/gerrit",
       "set-review",
diff --git a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing.json b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing.json
index 30b5984..3b7c50a 100644
--- a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing.json
+++ b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing.json
@@ -253,10 +253,11 @@
       "@@@STEP_LOG_LINE@json.output@    \"owner\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"_account_id\": 3873@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"project\": \"myProject\",@@@",
       "@@@STEP_LOG_LINE@json.output@    \"revisions\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"27cc4558b5a3d3387dd11ee2df7a117e7e581822\": {@@@",
       "@@@STEP_LOG_LINE@json.output@        \"commit\": {@@@",
-      "@@@STEP_LOG_LINE@json.output@          \"message\": \"Implementing Feature X\\n\\nBug: 123456\\nChange-Id: I12345\\nDepends-on: I8473b95934b5732ac55d26311a706c9c2bde9939\"@@@",
+      "@@@STEP_LOG_LINE@json.output@          \"message\": \"Implementing Feature X\\n\\nBug: 123456\\nChange-Id: I12345\\nDepends-on: other:I8473b95934b5732ac55d26311a706c9c2bde9939\"@@@",
       "@@@STEP_LOG_LINE@json.output@        }@@@",
       "@@@STEP_LOG_LINE@json.output@      }@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
@@ -291,7 +292,16 @@
   },
   {
     "cmd": [],
-    "name": "other.change myProject~3965.detected atomic changes",
+    "name": "other.change myProject~3965.resolved dependencies",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@",
+      "@@@STEP_LINK@https://fuchsia-review.googlesource.com/c/myProject/+/13532 (circular)@https://fuchsia-review.googlesource.com/c/myProject/+/13532@@@",
+      "@@@STEP_LINK@https://other-review.googlesource.com/c/myProject/+/3965 (circular)@https://other-review.googlesource.com/c/myProject/+/3965@@@"
+    ]
+  },
+  {
+    "cmd": [],
+    "name": "other.change myProject~3965.detect atomic changes",
     "~followup_annotations": [
       "@@@STEP_NEST_LEVEL@2@@@"
     ]
diff --git a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_change_id_error_dryrun.json b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_change_id_error_dryrun.json
new file mode 100644
index 0000000..ad6a3ec
--- /dev/null
+++ b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_change_id_error_dryrun.json
@@ -0,0 +1,239 @@
+[
+  {
+    "cmd": [],
+    "name": "fuchsia"
+  },
+  {
+    "cmd": [],
+    "name": "fuchsia.ensure infra/tools/luci/gerrit/${platform}",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@1@@@"
+    ]
+  },
+  {
+    "cmd": [],
+    "name": "fuchsia.ensure infra/tools/luci/gerrit/${platform}.get packages",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@"
+    ]
+  },
+  {
+    "cmd": [
+      "vpython3",
+      "-u",
+      "RECIPE_MODULE[recipe_engine::file]/resources/fileutil.py",
+      "--json-output",
+      "/path/to/tmp/json",
+      "copy",
+      "RECIPE_MODULE[fuchsia::gerrit]/resources/cipd.ensure",
+      "/path/to/tmp/"
+    ],
+    "infra_step": true,
+    "name": "fuchsia.ensure infra/tools/luci/gerrit/${platform}.get packages.read ensure file",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@3@@@",
+      "@@@STEP_LOG_LINE@cipd.ensure@infra/tools/luci/gerrit/${platform} version:pinned-version@@@",
+      "@@@STEP_LOG_END@cipd.ensure@@@"
+    ]
+  },
+  {
+    "cmd": [],
+    "name": "fuchsia.ensure infra/tools/luci/gerrit/${platform}.install infra/tools/luci/gerrit",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@"
+    ]
+  },
+  {
+    "cmd": [
+      "vpython3",
+      "-u",
+      "RECIPE_MODULE[recipe_engine::file]/resources/fileutil.py",
+      "--json-output",
+      "/path/to/tmp/json",
+      "ensure-directory",
+      "--mode",
+      "0o777",
+      "[START_DIR]/cipd_tool/infra/tools/luci/gerrit/0e548aa33f8113a45a5b3b62201e114e98e63d00f97296912380138f44597b07"
+    ],
+    "infra_step": true,
+    "name": "fuchsia.ensure infra/tools/luci/gerrit/${platform}.install infra/tools/luci/gerrit.ensure package directory",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@3@@@"
+    ]
+  },
+  {
+    "cmd": [
+      "cipd",
+      "ensure",
+      "-root",
+      "[START_DIR]/cipd_tool/infra/tools/luci/gerrit/0e548aa33f8113a45a5b3b62201e114e98e63d00f97296912380138f44597b07",
+      "-ensure-file",
+      "infra/tools/luci/gerrit/${platform} version:pinned-version",
+      "-max-threads",
+      "0",
+      "-json-output",
+      "/path/to/tmp/json"
+    ],
+    "infra_step": true,
+    "name": "fuchsia.ensure infra/tools/luci/gerrit/${platform}.install infra/tools/luci/gerrit.ensure_installed",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@3@@@",
+      "@@@STEP_LOG_LINE@json.output@{@@@",
+      "@@@STEP_LOG_LINE@json.output@  \"result\": {@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"\": [@@@",
+      "@@@STEP_LOG_LINE@json.output@      {@@@",
+      "@@@STEP_LOG_LINE@json.output@        \"instance_id\": \"resolved-instance_id-of-version:pinned-v\",@@@",
+      "@@@STEP_LOG_LINE@json.output@        \"package\": \"infra/tools/luci/gerrit/resolved-platform\"@@@",
+      "@@@STEP_LOG_LINE@json.output@      }@@@",
+      "@@@STEP_LOG_LINE@json.output@    ]@@@",
+      "@@@STEP_LOG_LINE@json.output@  }@@@",
+      "@@@STEP_LOG_LINE@json.output@}@@@",
+      "@@@STEP_LOG_END@json.output@@@"
+    ]
+  },
+  {
+    "cmd": [
+      "[START_DIR]/cipd_tool/infra/tools/luci/gerrit/0e548aa33f8113a45a5b3b62201e114e98e63d00f97296912380138f44597b07/gerrit",
+      "change-query",
+      "-host",
+      "https://fuchsia-review.googlesource.com",
+      "-input",
+      "{\"params\": {\"o\": [\"LABELS\", \"CURRENT_REVISION\", \"CURRENT_COMMIT\", \"MESSAGES\", \"SUBMIT_REQUIREMENTS\"], \"q\": \"is:open -is:wip hasfooter:Depends-on -label:Dependencies-Satisfied+1 -age:30d\"}}",
+      "-output",
+      "/path/to/tmp/json"
+    ],
+    "infra_step": true,
+    "name": "fuchsia.get changes",
+    "timeout": 120.0,
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@1@@@",
+      "@@@STEP_LOG_LINE@json.output@[]@@@",
+      "@@@STEP_LOG_END@json.output@@@",
+      "@@@STEP_LOG_LINE@json.input@{@@@",
+      "@@@STEP_LOG_LINE@json.input@  \"params\": {@@@",
+      "@@@STEP_LOG_LINE@json.input@    \"o\": [@@@",
+      "@@@STEP_LOG_LINE@json.input@      \"LABELS\",@@@",
+      "@@@STEP_LOG_LINE@json.input@      \"CURRENT_REVISION\",@@@",
+      "@@@STEP_LOG_LINE@json.input@      \"CURRENT_COMMIT\",@@@",
+      "@@@STEP_LOG_LINE@json.input@      \"MESSAGES\",@@@",
+      "@@@STEP_LOG_LINE@json.input@      \"SUBMIT_REQUIREMENTS\"@@@",
+      "@@@STEP_LOG_LINE@json.input@    ],@@@",
+      "@@@STEP_LOG_LINE@json.input@    \"q\": \"is:open -is:wip hasfooter:Depends-on -label:Dependencies-Satisfied+1 -age:30d\"@@@",
+      "@@@STEP_LOG_LINE@json.input@  }@@@",
+      "@@@STEP_LOG_LINE@json.input@}@@@",
+      "@@@STEP_LOG_END@json.input@@@"
+    ]
+  },
+  {
+    "cmd": [],
+    "name": "other"
+  },
+  {
+    "cmd": [
+      "[START_DIR]/cipd_tool/infra/tools/luci/gerrit/0e548aa33f8113a45a5b3b62201e114e98e63d00f97296912380138f44597b07/gerrit",
+      "change-query",
+      "-host",
+      "https://other-review.googlesource.com",
+      "-input",
+      "{\"params\": {\"o\": [\"LABELS\", \"CURRENT_REVISION\", \"CURRENT_COMMIT\", \"MESSAGES\", \"SUBMIT_REQUIREMENTS\"], \"q\": \"is:open -is:wip hasfooter:Depends-on -label:Dependencies-Satisfied+1 -age:30d\"}}",
+      "-output",
+      "/path/to/tmp/json"
+    ],
+    "infra_step": true,
+    "name": "other.get changes",
+    "timeout": 120.0,
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@1@@@",
+      "@@@STEP_LOG_LINE@json.output@[@@@",
+      "@@@STEP_LOG_LINE@json.output@  {@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"_number\": 3965,@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"branch\": \"main\",@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"change_id\": \"I8473b95934b5732ac55d26311a706c9c2bde9939\",@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"current_revision\": \"27cc4558b5a3d3387dd11ee2df7a117e7e581822\",@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"current_revision_number\": 2,@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"id\": \"myProject~3965\",@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"labels\": {@@@",
+      "@@@STEP_LOG_LINE@json.output@      \"Fuchsia-Auto-Submit\": {@@@",
+      "@@@STEP_LOG_LINE@json.output@        \"approved\": {@@@",
+      "@@@STEP_LOG_LINE@json.output@          \"_account_id\": 3873@@@",
+      "@@@STEP_LOG_LINE@json.output@        }@@@",
+      "@@@STEP_LOG_LINE@json.output@      }@@@",
+      "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"messages\": [@@@",
+      "@@@STEP_LOG_LINE@json.output@      {@@@",
+      "@@@STEP_LOG_LINE@json.output@        \"_revision_number\": 1@@@",
+      "@@@STEP_LOG_LINE@json.output@      },@@@",
+      "@@@STEP_LOG_LINE@json.output@      {@@@",
+      "@@@STEP_LOG_LINE@json.output@        \"_revision_number\": 2,@@@",
+      "@@@STEP_LOG_LINE@json.output@        \"tag\": \"\"@@@",
+      "@@@STEP_LOG_LINE@json.output@      }@@@",
+      "@@@STEP_LOG_LINE@json.output@    ],@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"owner\": {@@@",
+      "@@@STEP_LOG_LINE@json.output@      \"_account_id\": 3873@@@",
+      "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"project\": \"myProject\",@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"revisions\": {@@@",
+      "@@@STEP_LOG_LINE@json.output@      \"27cc4558b5a3d3387dd11ee2df7a117e7e581822\": {@@@",
+      "@@@STEP_LOG_LINE@json.output@        \"commit\": {@@@",
+      "@@@STEP_LOG_LINE@json.output@          \"message\": \"Implementing Feature X\\n\\nBug: 123456\\nChange-Id: I8473b95934b5732ac55d26311a706c9c2bde9939\\nDepends-on: fuchsia: 12345\"@@@",
+      "@@@STEP_LOG_LINE@json.output@        }@@@",
+      "@@@STEP_LOG_LINE@json.output@      }@@@",
+      "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"submit_requirements\": [@@@",
+      "@@@STEP_LOG_LINE@json.output@      {@@@",
+      "@@@STEP_LOG_LINE@json.output@        \"name\": \"Dependencies-Satisfied\",@@@",
+      "@@@STEP_LOG_LINE@json.output@        \"status\": \"UNSATISFIED\"@@@",
+      "@@@STEP_LOG_LINE@json.output@      }@@@",
+      "@@@STEP_LOG_LINE@json.output@    ]@@@",
+      "@@@STEP_LOG_LINE@json.output@  }@@@",
+      "@@@STEP_LOG_LINE@json.output@]@@@",
+      "@@@STEP_LOG_END@json.output@@@",
+      "@@@STEP_LOG_LINE@json.input@{@@@",
+      "@@@STEP_LOG_LINE@json.input@  \"params\": {@@@",
+      "@@@STEP_LOG_LINE@json.input@    \"o\": [@@@",
+      "@@@STEP_LOG_LINE@json.input@      \"LABELS\",@@@",
+      "@@@STEP_LOG_LINE@json.input@      \"CURRENT_REVISION\",@@@",
+      "@@@STEP_LOG_LINE@json.input@      \"CURRENT_COMMIT\",@@@",
+      "@@@STEP_LOG_LINE@json.input@      \"MESSAGES\",@@@",
+      "@@@STEP_LOG_LINE@json.input@      \"SUBMIT_REQUIREMENTS\"@@@",
+      "@@@STEP_LOG_LINE@json.input@    ],@@@",
+      "@@@STEP_LOG_LINE@json.input@    \"q\": \"is:open -is:wip hasfooter:Depends-on -label:Dependencies-Satisfied+1 -age:30d\"@@@",
+      "@@@STEP_LOG_LINE@json.input@  }@@@",
+      "@@@STEP_LOG_LINE@json.input@}@@@",
+      "@@@STEP_LOG_END@json.input@@@"
+    ]
+  },
+  {
+    "cmd": [],
+    "name": "other.change myProject~3965",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@1@@@",
+      "@@@STEP_TEXT@https://other-review.googlesource.com/c/myProject/+/3965@@@"
+    ]
+  },
+  {
+    "cmd": [],
+    "name": "other.change myProject~3965.dry run, sending comments",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@",
+      "@@@STEP_LOG_LINE@comment@`12345` is not a valid Depends-on format.@@@",
+      "@@@STEP_LOG_LINE@comment@The Depends-on footer value should come from the dependency's Change-Id footer. Example supported formats:@@@",
+      "@@@STEP_LOG_LINE@comment@@@@",
+      "@@@STEP_LOG_LINE@comment@- `I8473b95934b5732ac55d26311a706c9c2bde9939`@@@",
+      "@@@STEP_LOG_LINE@comment@- `fuchsia:I8473b95934b5732ac55d26311a706c9c2bde9939`@@@",
+      "@@@STEP_LOG_LINE@comment@- `turquoise-internal:I8473b95934b5732ac55d26311a706c9c2bde9939`@@@",
+      "@@@STEP_LOG_END@comment@@@"
+    ]
+  },
+  {
+    "cmd": [],
+    "name": "other.change myProject~3965.found bad Depends-on footer",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@",
+      "@@@STEP_TEXT@BadDependOnException: Reason: `12345` is not a valid Depends-on format.<br/>The Depends-on footer value should come from the dependency's Change-Id footer. Example supported formats:<br/><br/>- `I8473b95934b5732ac55d26311a706c9c2bde9939`<br/>- `fuchsia:I8473b95934b5732ac55d26311a706c9c2bde9939`<br/>- `turquoise-internal:I8473b95934b5732ac55d26311a706c9c2bde9939`@@@"
+    ]
+  },
+  {
+    "name": "$result"
+  }
+]
\ No newline at end of file
diff --git a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_no_cv_executed.json b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_no_cv_executed.json
index 9ba355b..24071f7 100644
--- a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_no_cv_executed.json
+++ b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_no_cv_executed.json
@@ -253,10 +253,11 @@
       "@@@STEP_LOG_LINE@json.output@    \"owner\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"_account_id\": 3873@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"project\": \"myProject\",@@@",
       "@@@STEP_LOG_LINE@json.output@    \"revisions\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"27cc4558b5a3d3387dd11ee2df7a117e7e581822\": {@@@",
       "@@@STEP_LOG_LINE@json.output@        \"commit\": {@@@",
-      "@@@STEP_LOG_LINE@json.output@          \"message\": \"Implementing Feature X\\n\\nBug: 123456\\nChange-Id: I12345\\nDepends-on: I8473b95934b5732ac55d26311a706c9c2bde9939\"@@@",
+      "@@@STEP_LOG_LINE@json.output@          \"message\": \"Implementing Feature X\\n\\nBug: 123456\\nChange-Id: I12345\\nDepends-on: other:I8473b95934b5732ac55d26311a706c9c2bde9939\"@@@",
       "@@@STEP_LOG_LINE@json.output@        }@@@",
       "@@@STEP_LOG_LINE@json.output@      }@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
@@ -291,7 +292,16 @@
   },
   {
     "cmd": [],
-    "name": "other.change myProject~3965.detected atomic changes",
+    "name": "other.change myProject~3965.resolved dependencies",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@",
+      "@@@STEP_LINK@https://fuchsia-review.googlesource.com/c/myProject/+/13532 (circular)@https://fuchsia-review.googlesource.com/c/myProject/+/13532@@@",
+      "@@@STEP_LINK@https://other-review.googlesource.com/c/myProject/+/3965 (circular)@https://other-review.googlesource.com/c/myProject/+/3965@@@"
+    ]
+  },
+  {
+    "cmd": [],
+    "name": "other.change myProject~3965.detect atomic changes",
     "~followup_annotations": [
       "@@@STEP_NEST_LEVEL@2@@@"
     ]
diff --git a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_no_success_cv.json b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_no_success_cv.json
index f965a67..0a79f91 100644
--- a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_no_success_cv.json
+++ b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_no_success_cv.json
@@ -253,10 +253,11 @@
       "@@@STEP_LOG_LINE@json.output@    \"owner\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"_account_id\": 3873@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"project\": \"myProject\",@@@",
       "@@@STEP_LOG_LINE@json.output@    \"revisions\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"27cc4558b5a3d3387dd11ee2df7a117e7e581822\": {@@@",
       "@@@STEP_LOG_LINE@json.output@        \"commit\": {@@@",
-      "@@@STEP_LOG_LINE@json.output@          \"message\": \"Implementing Feature X\\n\\nBug: 123456\\nChange-Id: I12345\\nDepends-on: I8473b95934b5732ac55d26311a706c9c2bde9939\"@@@",
+      "@@@STEP_LOG_LINE@json.output@          \"message\": \"Implementing Feature X\\n\\nBug: 123456\\nChange-Id: I12345\\nDepends-on: other:I8473b95934b5732ac55d26311a706c9c2bde9939\"@@@",
       "@@@STEP_LOG_LINE@json.output@        }@@@",
       "@@@STEP_LOG_LINE@json.output@      }@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
@@ -291,7 +292,16 @@
   },
   {
     "cmd": [],
-    "name": "other.change myProject~3965.detected atomic changes",
+    "name": "other.change myProject~3965.resolved dependencies",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@",
+      "@@@STEP_LINK@https://fuchsia-review.googlesource.com/c/myProject/+/13532 (circular)@https://fuchsia-review.googlesource.com/c/myProject/+/13532@@@",
+      "@@@STEP_LINK@https://other-review.googlesource.com/c/myProject/+/3965 (circular)@https://other-review.googlesource.com/c/myProject/+/3965@@@"
+    ]
+  },
+  {
+    "cmd": [],
+    "name": "other.change myProject~3965.detect atomic changes",
     "~followup_annotations": [
       "@@@STEP_NEST_LEVEL@2@@@"
     ]
diff --git a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_one_change_not_auto_submit.json b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_one_change_not_auto_submit.json
index e68d7d5..99ccabe 100644
--- a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_one_change_not_auto_submit.json
+++ b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_one_change_not_auto_submit.json
@@ -249,10 +249,11 @@
       "@@@STEP_LOG_LINE@json.output@    \"owner\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"_account_id\": 3873@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"project\": \"myProject\",@@@",
       "@@@STEP_LOG_LINE@json.output@    \"revisions\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"27cc4558b5a3d3387dd11ee2df7a117e7e581822\": {@@@",
       "@@@STEP_LOG_LINE@json.output@        \"commit\": {@@@",
-      "@@@STEP_LOG_LINE@json.output@          \"message\": \"Implementing Feature X\\n\\nBug: 123456\\nChange-Id: I12345\\nDepends-on: I8473b95934b5732ac55d26311a706c9c2bde9939\"@@@",
+      "@@@STEP_LOG_LINE@json.output@          \"message\": \"Implementing Feature X\\n\\nBug: 123456\\nChange-Id: I12345\\nDepends-on: other:I8473b95934b5732ac55d26311a706c9c2bde9939\"@@@",
       "@@@STEP_LOG_LINE@json.output@        }@@@",
       "@@@STEP_LOG_LINE@json.output@      }@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
@@ -287,7 +288,16 @@
   },
   {
     "cmd": [],
-    "name": "other.change myProject~3965.detected atomic changes",
+    "name": "other.change myProject~3965.resolved dependencies",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@",
+      "@@@STEP_LINK@https://fuchsia-review.googlesource.com/c/myProject/+/13532 (circular)@https://fuchsia-review.googlesource.com/c/myProject/+/13532@@@",
+      "@@@STEP_LINK@https://other-review.googlesource.com/c/myProject/+/3965 (circular)@https://other-review.googlesource.com/c/myProject/+/3965@@@"
+    ]
+  },
+  {
+    "cmd": [],
+    "name": "other.change myProject~3965.detect atomic changes",
     "~followup_annotations": [
       "@@@STEP_NEST_LEVEL@2@@@"
     ]
diff --git a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_sub_requirements_not_satisfied.json b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_sub_requirements_not_satisfied.json
index 6cb7902..3a6acaf 100644
--- a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_sub_requirements_not_satisfied.json
+++ b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_atomic_changes_processing_sub_requirements_not_satisfied.json
@@ -253,10 +253,11 @@
       "@@@STEP_LOG_LINE@json.output@    \"owner\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"_account_id\": 3873@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"project\": \"myProject\",@@@",
       "@@@STEP_LOG_LINE@json.output@    \"revisions\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"27cc4558b5a3d3387dd11ee2df7a117e7e581822\": {@@@",
       "@@@STEP_LOG_LINE@json.output@        \"commit\": {@@@",
-      "@@@STEP_LOG_LINE@json.output@          \"message\": \"Implementing Feature X\\n\\nBug: 123456\\nChange-Id: I12345\\nDepends-on: I8473b95934b5732ac55d26311a706c9c2bde9939\"@@@",
+      "@@@STEP_LOG_LINE@json.output@          \"message\": \"Implementing Feature X\\n\\nBug: 123456\\nChange-Id: I12345\\nDepends-on: other:I8473b95934b5732ac55d26311a706c9c2bde9939\"@@@",
       "@@@STEP_LOG_LINE@json.output@        }@@@",
       "@@@STEP_LOG_LINE@json.output@      }@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
@@ -291,7 +292,16 @@
   },
   {
     "cmd": [],
-    "name": "other.change myProject~3965.detected atomic changes",
+    "name": "other.change myProject~3965.resolved dependencies",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@",
+      "@@@STEP_LINK@https://fuchsia-review.googlesource.com/c/myProject/+/13532 (circular)@https://fuchsia-review.googlesource.com/c/myProject/+/13532@@@",
+      "@@@STEP_LINK@https://other-review.googlesource.com/c/myProject/+/3965 (circular)@https://other-review.googlesource.com/c/myProject/+/3965@@@"
+    ]
+  },
+  {
+    "cmd": [],
+    "name": "other.change myProject~3965.detect atomic changes",
     "~followup_annotations": [
       "@@@STEP_NEST_LEVEL@2@@@"
     ]
diff --git a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_submission.json b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_submission.json
index 86bb3a2..031e95c 100644
--- a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_submission.json
+++ b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_submission.json
@@ -249,6 +249,7 @@
       "@@@STEP_LOG_LINE@json.output@    \"owner\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"_account_id\": 3873@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"project\": \"myProject\",@@@",
       "@@@STEP_LOG_LINE@json.output@    \"revisions\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"27cc4558b5a3d3387dd11ee2df7a117e7e581822\": {@@@",
       "@@@STEP_LOG_LINE@json.output@        \"commit\": {@@@",
@@ -327,6 +328,7 @@
       "@@@STEP_LOG_LINE@json.output@    \"owner\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"_account_id\": 3873@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"project\": \"myProject\",@@@",
       "@@@STEP_LOG_LINE@json.output@    \"revisions\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"27cc4558b5a3d3387dd11ee2df7a117e7e581822\": {@@@",
       "@@@STEP_LOG_LINE@json.output@        \"commit\": {@@@",
@@ -364,6 +366,16 @@
     ]
   },
   {
+    "cmd": [],
+    "name": "other.change myProject~3965.resolved dependencies",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@",
+      "@@@STEP_LINK@https://other-review.googlesource.com/c/myProject/+/3965 (circular)@https://other-review.googlesource.com/c/myProject/+/3965@@@",
+      "@@@STEP_LINK@https://fuchsia-review.googlesource.com/c/myProject/+/13532 (one-way)@https://fuchsia-review.googlesource.com/c/myProject/+/13532@@@",
+      "@@@STEP_LINK@https://other-review.googlesource.com/c/myProject/+/13532 (one-way)@https://other-review.googlesource.com/c/myProject/+/13532@@@"
+    ]
+  },
+  {
     "cmd": [
       "[START_DIR]/cipd_tool/infra/tools/luci/gerrit/0e548aa33f8113a45a5b3b62201e114e98e63d00f97296912380138f44597b07/gerrit",
       "set-review",
diff --git a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_submission_change_id_dupes.json b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_submission_change_id_dupes.json
index fa2fc70..93c1039 100644
--- a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_submission_change_id_dupes.json
+++ b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_submission_change_id_dupes.json
@@ -249,6 +249,7 @@
       "@@@STEP_LOG_LINE@json.output@    \"owner\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"_account_id\": 3873@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"project\": \"myProject\",@@@",
       "@@@STEP_LOG_LINE@json.output@    \"revisions\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"27cc4558b5a3d3387dd11ee2df7a117e7e581822\": {@@@",
       "@@@STEP_LOG_LINE@json.output@        \"commit\": {@@@",
@@ -293,6 +294,7 @@
       "@@@STEP_LOG_LINE@json.output@    \"owner\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"_account_id\": 3873@@@",
       "@@@STEP_LOG_LINE@json.output@    },@@@",
+      "@@@STEP_LOG_LINE@json.output@    \"project\": \"myProject\",@@@",
       "@@@STEP_LOG_LINE@json.output@    \"revisions\": {@@@",
       "@@@STEP_LOG_LINE@json.output@      \"27cc4558b5a3d3387dd11ee2df7a117e7e581822\": {@@@",
       "@@@STEP_LOG_LINE@json.output@        \"commit\": {@@@",
@@ -362,6 +364,14 @@
     ]
   },
   {
+    "cmd": [],
+    "name": "other.change myProject~3965.found bad Depends-on footer",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@",
+      "@@@STEP_TEXT@BadDependOnException: Reason: `Iabcdef` matches multiple CLs.<br/>The Depends-on footer value should come from the dependency's Change-Id footer. Example supported formats:<br/><br/>- `I8473b95934b5732ac55d26311a706c9c2bde9939`<br/>- `fuchsia:I8473b95934b5732ac55d26311a706c9c2bde9939`<br/>- `turquoise-internal:I8473b95934b5732ac55d26311a706c9c2bde9939`@@@"
+    ]
+  },
+  {
     "name": "$result"
   }
 ]
\ No newline at end of file
diff --git a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_submission_change_id_not_found.json b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_submission_change_id_not_found.json
index 7caf1a5..3f450d1 100644
--- a/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_submission_change_id_not_found.json
+++ b/recipe_modules/gerrit_dependency_satisfy/tests/full.expected/test_submission_change_id_not_found.json
@@ -273,6 +273,14 @@
     ]
   },
   {
+    "cmd": [],
+    "name": "other.change myProject~3965.found bad Depends-on footer",
+    "~followup_annotations": [
+      "@@@STEP_NEST_LEVEL@2@@@",
+      "@@@STEP_TEXT@BadDependOnException: Reason: `Iabcdef` cannot be found.<br/>The Depends-on footer value should come from the dependency's Change-Id footer. Example supported formats:<br/><br/>- `I8473b95934b5732ac55d26311a706c9c2bde9939`<br/>- `fuchsia:I8473b95934b5732ac55d26311a706c9c2bde9939`<br/>- `turquoise-internal:I8473b95934b5732ac55d26311a706c9c2bde9939`@@@"
+    ]
+  },
+  {
     "name": "$result"
   }
 ]
\ No newline at end of file
diff --git a/recipe_modules/gerrit_dependency_satisfy/tests/full.py b/recipe_modules/gerrit_dependency_satisfy/tests/full.py
index 3221a4d..9564998 100644
--- a/recipe_modules/gerrit_dependency_satisfy/tests/full.py
+++ b/recipe_modules/gerrit_dependency_satisfy/tests/full.py
@@ -191,6 +191,7 @@
             {
                 "id": change_id,
                 "change_id": change_id,
+                "project": "myProject",
                 "_number": 13532,
                 "branch": "main",
                 "status": "MERGED" if submitted else "NEW",
@@ -368,7 +369,7 @@
             "I12345",
             "myProject~3965",
             dep_host="fuchsia",
-            depends_on=["I8473b95934b5732ac55d26311a706c9c2bde9939"],
+            depends_on=["other:I8473b95934b5732ac55d26311a706c9c2bde9939"],
             submitted=False,
         )
     )
@@ -384,7 +385,7 @@
             "I12345",
             "myProject~3965",
             dep_host="fuchsia",
-            depends_on=["I8473b95934b5732ac55d26311a706c9c2bde9939"],
+            depends_on=["other:I8473b95934b5732ac55d26311a706c9c2bde9939"],
             submitted=False,
         )
         + fetch_cv_run_test_data("other", "13532", "myProject~3965")
@@ -404,7 +405,7 @@
             "I12345",
             "myProject~3965",
             dep_host="fuchsia",
-            depends_on=["I8473b95934b5732ac55d26311a706c9c2bde9939"],
+            depends_on=["other:I8473b95934b5732ac55d26311a706c9c2bde9939"],
             submitted=False,
         )
         + fetch_cv_run_test_data("other", "13532", "myProject~3965", has_runs=False)
@@ -424,7 +425,7 @@
             "I12345",
             "myProject~3965",
             dep_host="fuchsia",
-            depends_on=["I8473b95934b5732ac55d26311a706c9c2bde9939"],
+            depends_on=["other:I8473b95934b5732ac55d26311a706c9c2bde9939"],
             submitted=False,
             submit_requirements_satified=False,
         )
@@ -441,10 +442,19 @@
             "I12345",
             "myProject~3965",
             dep_host="fuchsia",
-            depends_on=["I8473b95934b5732ac55d26311a706c9c2bde9939"],
+            depends_on=["other:I8473b95934b5732ac55d26311a706c9c2bde9939"],
             submitted=False,
         )
         + fetch_cv_run_test_data("other", "13532", "myProject~3965")
         + fetch_cv_run_test_data("other", "3965", "myProject~3965", dep_host="other")
         + set_satisfied("other", "myProject~3965")
     )
+
+    yield (
+        api.test("test_atomic_changes_processing_change_id_error_dryrun")
+        + options()
+        + api.properties(dry_run=True)
+        + change_query_test_data(
+            "other", depends_on=["fuchsia: 12345"], auto_submit=True
+        )
+    )