We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
ERROR: unexpected error - list.remove(x): x not in list, if I execute "dvc diff HEAD~",  after  dvc version is updated from 1.1.15 to 2.0.5
# Bug Report

ERROR: unexpected error - list.remove(x): x not in list, if I execute "dvc diff HEAD~", after dvc version is updated from 1.1.15 to 2.0.5

## Description

"dvc diff" command is wrong in version 2.0.5.


### Reproduce

Step list of how to reproduce the bug

1. I made dvc repository in 1.11.15 and push data into GCS.
2. "pip install dvc --upgrade"
3. Create a file in a directory named foo managed by dvc
4. "dvc add foo"
5. "dvc diff HEAD~"
6. shown "ERROR: unexpected error - list.remove(x): x not in list"

### Expected

"dvc diff" command execute as well as 1.11.15.
looks like below.
```
Added:
    bar.txt
```


### Environment information


**Output of `dvc doctor`:**

```console
$ dvc doctor
```

```console
DVC version: 2.0.5 (pip)
---------------------------------
Platform: Python 3.7.9 on Darwin-19.6.0-x86_64-i386-64bit
Supports: gs, hdfs, webhdfs, http, https
Cache types: reflink, hardlink, symlink
Cache directory: apfs on /dev/disk1s2
Caches: local
Remotes: gs
Workspace directory: apfs on /dev/disk1s2
Repo: dvc, git
```

**Additional Information (if any):**

part of error message of ```dvc diff --verbose HEAD~``` is below.
```
Traceback (most recent call last):
  File "venv/lib/python3.7/site-packages/dvc/main.py", line 50, in main
    ret = cmd.run()
  File "<reposistory>/venv/lib/python3.7/site-packages/dvc/command/diff.py", line 138, in run
    self.args.a_rev, self.args.b_rev, self.args.targets
  File "<reposistory>/venv/lib/python3.7/site-packages/dvc/repo/__init__.py", line 49, in wrapper
    return f(repo, *args, **kwargs)
  File "<reposistory>/venv/lib/python3.7/site-packages/dvc/repo/diff.py", line 79, in diff
    deleted.remove(renamed_item["path"]["old"])
ValueError: list.remove(x): x not in list
```

version 2.0.0 is wrong too.
version 1.11.16 is correct.

Thanks.

--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `dvc/repo/diff.py`
Content:
```
1 import logging
2 import os
3 
4 from dvc.exceptions import PathMissingError
5 from dvc.objects.stage import get_file_hash
6 from dvc.objects.stage import stage as ostage
7 from dvc.repo import locked
8 
9 logger = logging.getLogger(__name__)
10 
11 
12 @locked
13 def diff(self, a_rev="HEAD", b_rev=None, targets=None):
14     """
15     By default, it compares the workspace with the last commit's fs.
16 
17     This implementation differs from `git diff` since DVC doesn't have
18     the concept of `index`, but it keeps the same interface, thus,
19     `dvc diff` would be the same as `dvc diff HEAD`.
20     """
21 
22     if self.scm.no_commits:
23         return {}
24 
25     from dvc.fs.repo import RepoFileSystem
26 
27     repo_fs = RepoFileSystem(self)
28 
29     b_rev = b_rev if b_rev else "workspace"
30     results = {}
31     missing_targets = {}
32     for rev in self.brancher(revs=[a_rev, b_rev]):
33         if rev == "workspace" and rev != b_rev:
34             # brancher always returns workspace, but we only need to compute
35             # workspace paths/checksums if b_rev was None
36             continue
37 
38         targets_path_infos = None
39         if targets is not None:
40             # convert targets to path_infos, and capture any missing targets
41             targets_path_infos, missing_targets[rev] = _targets_to_path_infos(
42                 repo_fs, targets
43             )
44 
45         results[rev] = _paths_checksums(self, repo_fs, targets_path_infos)
46 
47     if targets is not None:
48         # check for overlapping missing targets between a_rev and b_rev
49         for target in set(missing_targets[a_rev]) & set(
50             missing_targets[b_rev]
51         ):
52             raise PathMissingError(target, self)
53 
54     old = results[a_rev]
55     new = results[b_rev]
56 
57     # Compare paths between the old and new fs.
58     # set() efficiently converts dict keys to a set
59     added = sorted(set(new) - set(old))
60     deleted_or_missing = set(old) - set(new)
61     if b_rev == "workspace":
62         # missing status is only applicable when diffing local workspace
63         # against a commit
64         missing = sorted(_filter_missing(repo_fs, deleted_or_missing))
65     else:
66         missing = []
67     deleted = sorted(deleted_or_missing - set(missing))
68     modified = sorted(set(old) & set(new))
69 
70     # Cases when file was changed and renamed are resulted
71     # in having deleted and added record
72     # To cover such cases we need to change hashing function
73     # to produce rolling/chunking hash
74 
75     renamed = _calculate_renamed(new, old, added, deleted)
76 
77     for renamed_item in renamed:
78         added.remove(renamed_item["path"]["new"])
79         deleted.remove(renamed_item["path"]["old"])
80 
81     ret = {
82         "added": [{"path": path, "hash": new[path]} for path in added],
83         "deleted": [{"path": path, "hash": old[path]} for path in deleted],
84         "modified": [
85             {"path": path, "hash": {"old": old[path], "new": new[path]}}
86             for path in modified
87             if old[path] != new[path]
88         ],
89         "renamed": renamed,
90         "not in cache": [
91             {"path": path, "hash": old[path]} for path in missing
92         ],
93     }
94 
95     return ret if any(ret.values()) else {}
96 
97 
98 def _paths_checksums(repo, repo_fs, targets):
99     """
100     A dictionary of checksums addressed by relpaths collected from
101     the current fs outputs.
102 
103     To help distinguish between a directory and a file output,
104     the former one will come with a trailing slash in the path:
105 
106         directory: "data/"
107         file:      "data"
108     """
109 
110     return dict(_output_paths(repo, repo_fs, targets))
111 
112 
113 def _output_paths(repo, repo_fs, targets):
114     from dvc.fs.local import LocalFileSystem
115 
116     on_working_fs = isinstance(repo.fs, LocalFileSystem)
117 
118     def _exists(output):
119         if on_working_fs:
120             return output.exists
121         return True
122 
123     def _to_path(output):
124         return (
125             str(output)
126             if not output.is_dir_checksum
127             else os.path.join(str(output), "")
128         )
129 
130     def _to_checksum(output):
131         if on_working_fs:
132             return ostage(
133                 repo.odb.local, output.path_info, repo.odb.local.fs, "md5",
134             ).hash_info.value
135         return output.hash_info.value
136 
137     for stage in repo.stages:
138         for output in stage.outs:
139             if _exists(output):
140                 yield_output = targets is None or any(
141                     output.path_info.isin_or_eq(target) for target in targets
142                 )
143 
144                 if yield_output:
145                     yield _to_path(output), _to_checksum(output)
146 
147                 if output.is_dir_checksum and (
148                     yield_output
149                     or any(target.isin(output.path_info) for target in targets)
150                 ):
151                     yield from _dir_output_paths(repo_fs, output, targets)
152 
153 
154 def _dir_output_paths(repo_fs, output, targets=None):
155     from dvc.config import NoRemoteError
156 
157     try:
158         for fname in repo_fs.walk_files(output.path_info):
159             if targets is None or any(
160                 fname.isin_or_eq(target) for target in targets
161             ):
162                 yield str(fname), get_file_hash(fname, repo_fs, "md5").value
163     except NoRemoteError:
164         logger.warning("dir cache entry for '%s' is missing", output)
165 
166 
167 def _filter_missing(repo_fs, paths):
168     for path in paths:
169         try:
170             metadata = repo_fs.metadata(path)
171             if metadata.is_dvc:
172                 out = metadata.outs[0]
173                 if out.status().get(str(out)) == "not in cache":
174                     yield path
175         except FileNotFoundError:
176             pass
177 
178 
179 def _targets_to_path_infos(repo_fs, targets):
180     path_infos = []
181     missing = []
182 
183     for target in targets:
184         if repo_fs.exists(target):
185             path_infos.append(repo_fs.metadata(target).path_info)
186         else:
187             missing.append(target)
188 
189     return path_infos, missing
190 
191 
192 def _calculate_renamed(new, old, added, deleted):
193     old_inverted = {}
194     # It is needed to be dict of lists to cover cases
195     # when repo has paths with same hash
196     for path, path_hash in old.items():
197         bucket = old_inverted.get(path_hash, None)
198         if bucket is None:
199             old_inverted[path_hash] = [path]
200         else:
201             bucket.append(path)
202 
203     renamed = []
204     for path in added:
205         path_hash = new[path]
206         old_paths = old_inverted.get(path_hash, None)
207         if not old_paths:
208             continue
209         old_path = None
210         for tmp_old_path in old_paths:
211             if tmp_old_path in deleted:
212                 old_path = tmp_old_path
213                 break
214         if not old_path:
215             continue
216         renamed.append(
217             {"path": {"old": old_path, "new": path}, "hash": path_hash}
218         )
219 
220     return renamed
221
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/dvc/repo/diff.py b/dvc/repo/diff.py
--- a/dvc/repo/diff.py
+++ b/dvc/repo/diff.py
@@ -1,5 +1,7 @@
 import logging
 import os
+from collections import defaultdict
+from typing import Dict, List
 
 from dvc.exceptions import PathMissingError
 from dvc.objects.stage import get_file_hash
@@ -190,29 +192,23 @@
 
 
 def _calculate_renamed(new, old, added, deleted):
-    old_inverted = {}
+    old_inverted: Dict[str, List[str]] = defaultdict(list)
     # It is needed to be dict of lists to cover cases
     # when repo has paths with same hash
     for path, path_hash in old.items():
-        bucket = old_inverted.get(path_hash, None)
-        if bucket is None:
-            old_inverted[path_hash] = [path]
-        else:
-            bucket.append(path)
+        old_inverted[path_hash].append(path)
 
     renamed = []
     for path in added:
         path_hash = new[path]
-        old_paths = old_inverted.get(path_hash, None)
-        if not old_paths:
-            continue
-        old_path = None
-        for tmp_old_path in old_paths:
-            if tmp_old_path in deleted:
-                old_path = tmp_old_path
-                break
-        if not old_path:
+        old_paths = old_inverted[path_hash]
+        try:
+            iterator = enumerate(old_paths)
+            index = next(idx for idx, path in iterator if path in deleted)
+        except StopIteration:
             continue
+
+        old_path = old_paths.pop(index)
         renamed.append(
             {"path": {"old": old_path, "new": path}, "hash": path_hash}
         )

{"golden_diff": "diff --git a/dvc/repo/diff.py b/dvc/repo/diff.py\n--- a/dvc/repo/diff.py\n+++ b/dvc/repo/diff.py\n@@ -1,5 +1,7 @@\n import logging\n import os\n+from collections import defaultdict\n+from typing import Dict, List\n \n from dvc.exceptions import PathMissingError\n from dvc.objects.stage import get_file_hash\n@@ -190,29 +192,23 @@\n \n \n def _calculate_renamed(new, old, added, deleted):\n-    old_inverted = {}\n+    old_inverted: Dict[str, List[str]] = defaultdict(list)\n     # It is needed to be dict of lists to cover cases\n     # when repo has paths with same hash\n     for path, path_hash in old.items():\n-        bucket = old_inverted.get(path_hash, None)\n-        if bucket is None:\n-            old_inverted[path_hash] = [path]\n-        else:\n-            bucket.append(path)\n+        old_inverted[path_hash].append(path)\n \n     renamed = []\n     for path in added:\n         path_hash = new[path]\n-        old_paths = old_inverted.get(path_hash, None)\n-        if not old_paths:\n-            continue\n-        old_path = None\n-        for tmp_old_path in old_paths:\n-            if tmp_old_path in deleted:\n-                old_path = tmp_old_path\n-                break\n-        if not old_path:\n+        old_paths = old_inverted[path_hash]\n+        try:\n+            iterator = enumerate(old_paths)\n+            index = next(idx for idx, path in iterator if path in deleted)\n+        except StopIteration:\n             continue\n+\n+        old_path = old_paths.pop(index)\n         renamed.append(\n             {\"path\": {\"old\": old_path, \"new\": path}, \"hash\": path_hash}\n         )\n", "issue": "ERROR: unexpected error - list.remove(x): x not in list, if I execute \"dvc diff HEAD~\",  after  dvc version is updated from 1.1.15 to 2.0.5\n# Bug Report\r\n\r\nERROR: unexpected error - list.remove(x): x not in list, if I execute \"dvc diff HEAD~\", after dvc version is updated from 1.1.15 to 2.0.5\r\n\r\n## Description\r\n\r\n\"dvc diff\" command is wrong in version 2.0.5.\r\n\r\n\r\n### Reproduce\r\n\r\nStep list of how to reproduce the bug\r\n\r\n1. I made dvc repository in 1.11.15 and push data into GCS.\r\n2. \"pip install dvc --upgrade\"\r\n3. Create a file in a directory named foo managed by dvc\r\n4. \"dvc add foo\"\r\n5. \"dvc diff HEAD~\"\r\n6. shown \"ERROR: unexpected error - list.remove(x): x not in list\"\r\n\r\n### Expected\r\n\r\n\"dvc diff\" command execute as well as 1.11.15.\r\nlooks like below.\r\n```\r\nAdded:\r\n    bar.txt\r\n```\r\n\r\n\r\n### Environment information\r\n\r\n\r\n**Output of `dvc doctor`:**\r\n\r\n```console\r\n$ dvc doctor\r\n```\r\n\r\n```console\r\nDVC version: 2.0.5 (pip)\r\n---------------------------------\r\nPlatform: Python 3.7.9 on Darwin-19.6.0-x86_64-i386-64bit\r\nSupports: gs, hdfs, webhdfs, http, https\r\nCache types: reflink, hardlink, symlink\r\nCache directory: apfs on /dev/disk1s2\r\nCaches: local\r\nRemotes: gs\r\nWorkspace directory: apfs on /dev/disk1s2\r\nRepo: dvc, git\r\n```\r\n\r\n**Additional Information (if any):**\r\n\r\npart of error message of ```dvc diff --verbose HEAD~``` is below.\r\n```\r\nTraceback (most recent call last):\r\n  File \"venv/lib/python3.7/site-packages/dvc/main.py\", line 50, in main\r\n    ret = cmd.run()\r\n  File \"<reposistory>/venv/lib/python3.7/site-packages/dvc/command/diff.py\", line 138, in run\r\n    self.args.a_rev, self.args.b_rev, self.args.targets\r\n  File \"<reposistory>/venv/lib/python3.7/site-packages/dvc/repo/__init__.py\", line 49, in wrapper\r\n    return f(repo, *args, **kwargs)\r\n  File \"<reposistory>/venv/lib/python3.7/site-packages/dvc/repo/diff.py\", line 79, in diff\r\n    deleted.remove(renamed_item[\"path\"][\"old\"])\r\nValueError: list.remove(x): x not in list\r\n```\r\n\r\nversion 2.0.0 is wrong too.\r\nversion 1.11.16 is correct.\r\n\r\nThanks.\n", "before_files": [{"content": "import logging\nimport os\n\nfrom dvc.exceptions import PathMissingError\nfrom dvc.objects.stage import get_file_hash\nfrom dvc.objects.stage import stage as ostage\nfrom dvc.repo import locked\n\nlogger = logging.getLogger(__name__)\n\n\n@locked\ndef diff(self, a_rev=\"HEAD\", b_rev=None, targets=None):\n    \"\"\"\n    By default, it compares the workspace with the last commit's fs.\n\n    This implementation differs from `git diff` since DVC doesn't have\n    the concept of `index`, but it keeps the same interface, thus,\n    `dvc diff` would be the same as `dvc diff HEAD`.\n    \"\"\"\n\n    if self.scm.no_commits:\n        return {}\n\n    from dvc.fs.repo import RepoFileSystem\n\n    repo_fs = RepoFileSystem(self)\n\n    b_rev = b_rev if b_rev else \"workspace\"\n    results = {}\n    missing_targets = {}\n    for rev in self.brancher(revs=[a_rev, b_rev]):\n        if rev == \"workspace\" and rev != b_rev:\n            # brancher always returns workspace, but we only need to compute\n            # workspace paths/checksums if b_rev was None\n            continue\n\n        targets_path_infos = None\n        if targets is not None:\n            # convert targets to path_infos, and capture any missing targets\n            targets_path_infos, missing_targets[rev] = _targets_to_path_infos(\n                repo_fs, targets\n            )\n\n        results[rev] = _paths_checksums(self, repo_fs, targets_path_infos)\n\n    if targets is not None:\n        # check for overlapping missing targets between a_rev and b_rev\n        for target in set(missing_targets[a_rev]) & set(\n            missing_targets[b_rev]\n        ):\n            raise PathMissingError(target, self)\n\n    old = results[a_rev]\n    new = results[b_rev]\n\n    # Compare paths between the old and new fs.\n    # set() efficiently converts dict keys to a set\n    added = sorted(set(new) - set(old))\n    deleted_or_missing = set(old) - set(new)\n    if b_rev == \"workspace\":\n        # missing status is only applicable when diffing local workspace\n        # against a commit\n        missing = sorted(_filter_missing(repo_fs, deleted_or_missing))\n    else:\n        missing = []\n    deleted = sorted(deleted_or_missing - set(missing))\n    modified = sorted(set(old) & set(new))\n\n    # Cases when file was changed and renamed are resulted\n    # in having deleted and added record\n    # To cover such cases we need to change hashing function\n    # to produce rolling/chunking hash\n\n    renamed = _calculate_renamed(new, old, added, deleted)\n\n    for renamed_item in renamed:\n        added.remove(renamed_item[\"path\"][\"new\"])\n        deleted.remove(renamed_item[\"path\"][\"old\"])\n\n    ret = {\n        \"added\": [{\"path\": path, \"hash\": new[path]} for path in added],\n        \"deleted\": [{\"path\": path, \"hash\": old[path]} for path in deleted],\n        \"modified\": [\n            {\"path\": path, \"hash\": {\"old\": old[path], \"new\": new[path]}}\n            for path in modified\n            if old[path] != new[path]\n        ],\n        \"renamed\": renamed,\n        \"not in cache\": [\n            {\"path\": path, \"hash\": old[path]} for path in missing\n        ],\n    }\n\n    return ret if any(ret.values()) else {}\n\n\ndef _paths_checksums(repo, repo_fs, targets):\n    \"\"\"\n    A dictionary of checksums addressed by relpaths collected from\n    the current fs outputs.\n\n    To help distinguish between a directory and a file output,\n    the former one will come with a trailing slash in the path:\n\n        directory: \"data/\"\n        file:      \"data\"\n    \"\"\"\n\n    return dict(_output_paths(repo, repo_fs, targets))\n\n\ndef _output_paths(repo, repo_fs, targets):\n    from dvc.fs.local import LocalFileSystem\n\n    on_working_fs = isinstance(repo.fs, LocalFileSystem)\n\n    def _exists(output):\n        if on_working_fs:\n            return output.exists\n        return True\n\n    def _to_path(output):\n        return (\n            str(output)\n            if not output.is_dir_checksum\n            else os.path.join(str(output), \"\")\n        )\n\n    def _to_checksum(output):\n        if on_working_fs:\n            return ostage(\n                repo.odb.local, output.path_info, repo.odb.local.fs, \"md5\",\n            ).hash_info.value\n        return output.hash_info.value\n\n    for stage in repo.stages:\n        for output in stage.outs:\n            if _exists(output):\n                yield_output = targets is None or any(\n                    output.path_info.isin_or_eq(target) for target in targets\n                )\n\n                if yield_output:\n                    yield _to_path(output), _to_checksum(output)\n\n                if output.is_dir_checksum and (\n                    yield_output\n                    or any(target.isin(output.path_info) for target in targets)\n                ):\n                    yield from _dir_output_paths(repo_fs, output, targets)\n\n\ndef _dir_output_paths(repo_fs, output, targets=None):\n    from dvc.config import NoRemoteError\n\n    try:\n        for fname in repo_fs.walk_files(output.path_info):\n            if targets is None or any(\n                fname.isin_or_eq(target) for target in targets\n            ):\n                yield str(fname), get_file_hash(fname, repo_fs, \"md5\").value\n    except NoRemoteError:\n        logger.warning(\"dir cache entry for '%s' is missing\", output)\n\n\ndef _filter_missing(repo_fs, paths):\n    for path in paths:\n        try:\n            metadata = repo_fs.metadata(path)\n            if metadata.is_dvc:\n                out = metadata.outs[0]\n                if out.status().get(str(out)) == \"not in cache\":\n                    yield path\n        except FileNotFoundError:\n            pass\n\n\ndef _targets_to_path_infos(repo_fs, targets):\n    path_infos = []\n    missing = []\n\n    for target in targets:\n        if repo_fs.exists(target):\n            path_infos.append(repo_fs.metadata(target).path_info)\n        else:\n            missing.append(target)\n\n    return path_infos, missing\n\n\ndef _calculate_renamed(new, old, added, deleted):\n    old_inverted = {}\n    # It is needed to be dict of lists to cover cases\n    # when repo has paths with same hash\n    for path, path_hash in old.items():\n        bucket = old_inverted.get(path_hash, None)\n        if bucket is None:\n            old_inverted[path_hash] = [path]\n        else:\n            bucket.append(path)\n\n    renamed = []\n    for path in added:\n        path_hash = new[path]\n        old_paths = old_inverted.get(path_hash, None)\n        if not old_paths:\n            continue\n        old_path = None\n        for tmp_old_path in old_paths:\n            if tmp_old_path in deleted:\n                old_path = tmp_old_path\n                break\n        if not old_path:\n            continue\n        renamed.append(\n            {\"path\": {\"old\": old_path, \"new\": path}, \"hash\": path_hash}\n        )\n\n    return renamed\n", "path": "dvc/repo/diff.py"}], "after_files": [{"content": "import logging\nimport os\nfrom collections import defaultdict\nfrom typing import Dict, List\n\nfrom dvc.exceptions import PathMissingError\nfrom dvc.objects.stage import get_file_hash\nfrom dvc.objects.stage import stage as ostage\nfrom dvc.repo import locked\n\nlogger = logging.getLogger(__name__)\n\n\n@locked\ndef diff(self, a_rev=\"HEAD\", b_rev=None, targets=None):\n    \"\"\"\n    By default, it compares the workspace with the last commit's fs.\n\n    This implementation differs from `git diff` since DVC doesn't have\n    the concept of `index`, but it keeps the same interface, thus,\n    `dvc diff` would be the same as `dvc diff HEAD`.\n    \"\"\"\n\n    if self.scm.no_commits:\n        return {}\n\n    from dvc.fs.repo import RepoFileSystem\n\n    repo_fs = RepoFileSystem(self)\n\n    b_rev = b_rev if b_rev else \"workspace\"\n    results = {}\n    missing_targets = {}\n    for rev in self.brancher(revs=[a_rev, b_rev]):\n        if rev == \"workspace\" and rev != b_rev:\n            # brancher always returns workspace, but we only need to compute\n            # workspace paths/checksums if b_rev was None\n            continue\n\n        targets_path_infos = None\n        if targets is not None:\n            # convert targets to path_infos, and capture any missing targets\n            targets_path_infos, missing_targets[rev] = _targets_to_path_infos(\n                repo_fs, targets\n            )\n\n        results[rev] = _paths_checksums(self, repo_fs, targets_path_infos)\n\n    if targets is not None:\n        # check for overlapping missing targets between a_rev and b_rev\n        for target in set(missing_targets[a_rev]) & set(\n            missing_targets[b_rev]\n        ):\n            raise PathMissingError(target, self)\n\n    old = results[a_rev]\n    new = results[b_rev]\n\n    # Compare paths between the old and new fs.\n    # set() efficiently converts dict keys to a set\n    added = sorted(set(new) - set(old))\n    deleted_or_missing = set(old) - set(new)\n    if b_rev == \"workspace\":\n        # missing status is only applicable when diffing local workspace\n        # against a commit\n        missing = sorted(_filter_missing(repo_fs, deleted_or_missing))\n    else:\n        missing = []\n    deleted = sorted(deleted_or_missing - set(missing))\n    modified = sorted(set(old) & set(new))\n\n    # Cases when file was changed and renamed are resulted\n    # in having deleted and added record\n    # To cover such cases we need to change hashing function\n    # to produce rolling/chunking hash\n\n    renamed = _calculate_renamed(new, old, added, deleted)\n\n    for renamed_item in renamed:\n        added.remove(renamed_item[\"path\"][\"new\"])\n        deleted.remove(renamed_item[\"path\"][\"old\"])\n\n    ret = {\n        \"added\": [{\"path\": path, \"hash\": new[path]} for path in added],\n        \"deleted\": [{\"path\": path, \"hash\": old[path]} for path in deleted],\n        \"modified\": [\n            {\"path\": path, \"hash\": {\"old\": old[path], \"new\": new[path]}}\n            for path in modified\n            if old[path] != new[path]\n        ],\n        \"renamed\": renamed,\n        \"not in cache\": [\n            {\"path\": path, \"hash\": old[path]} for path in missing\n        ],\n    }\n\n    return ret if any(ret.values()) else {}\n\n\ndef _paths_checksums(repo, repo_fs, targets):\n    \"\"\"\n    A dictionary of checksums addressed by relpaths collected from\n    the current fs outputs.\n\n    To help distinguish between a directory and a file output,\n    the former one will come with a trailing slash in the path:\n\n        directory: \"data/\"\n        file:      \"data\"\n    \"\"\"\n\n    return dict(_output_paths(repo, repo_fs, targets))\n\n\ndef _output_paths(repo, repo_fs, targets):\n    from dvc.fs.local import LocalFileSystem\n\n    on_working_fs = isinstance(repo.fs, LocalFileSystem)\n\n    def _exists(output):\n        if on_working_fs:\n            return output.exists\n        return True\n\n    def _to_path(output):\n        return (\n            str(output)\n            if not output.is_dir_checksum\n            else os.path.join(str(output), \"\")\n        )\n\n    def _to_checksum(output):\n        if on_working_fs:\n            return ostage(\n                repo.odb.local, output.path_info, repo.odb.local.fs, \"md5\",\n            ).hash_info.value\n        return output.hash_info.value\n\n    for stage in repo.stages:\n        for output in stage.outs:\n            if _exists(output):\n                yield_output = targets is None or any(\n                    output.path_info.isin_or_eq(target) for target in targets\n                )\n\n                if yield_output:\n                    yield _to_path(output), _to_checksum(output)\n\n                if output.is_dir_checksum and (\n                    yield_output\n                    or any(target.isin(output.path_info) for target in targets)\n                ):\n                    yield from _dir_output_paths(repo_fs, output, targets)\n\n\ndef _dir_output_paths(repo_fs, output, targets=None):\n    from dvc.config import NoRemoteError\n\n    try:\n        for fname in repo_fs.walk_files(output.path_info):\n            if targets is None or any(\n                fname.isin_or_eq(target) for target in targets\n            ):\n                yield str(fname), get_file_hash(fname, repo_fs, \"md5\").value\n    except NoRemoteError:\n        logger.warning(\"dir cache entry for '%s' is missing\", output)\n\n\ndef _filter_missing(repo_fs, paths):\n    for path in paths:\n        try:\n            metadata = repo_fs.metadata(path)\n            if metadata.is_dvc:\n                out = metadata.outs[0]\n                if out.status().get(str(out)) == \"not in cache\":\n                    yield path\n        except FileNotFoundError:\n            pass\n\n\ndef _targets_to_path_infos(repo_fs, targets):\n    path_infos = []\n    missing = []\n\n    for target in targets:\n        if repo_fs.exists(target):\n            path_infos.append(repo_fs.metadata(target).path_info)\n        else:\n            missing.append(target)\n\n    return path_infos, missing\n\n\ndef _calculate_renamed(new, old, added, deleted):\n    old_inverted: Dict[str, List[str]] = defaultdict(list)\n    # It is needed to be dict of lists to cover cases\n    # when repo has paths with same hash\n    for path, path_hash in old.items():\n        old_inverted[path_hash].append(path)\n\n    renamed = []\n    for path in added:\n        path_hash = new[path]\n        old_paths = old_inverted[path_hash]\n        try:\n            iterator = enumerate(old_paths)\n            index = next(idx for idx, path in iterator if path in deleted)\n        except StopIteration:\n            continue\n\n        old_path = old_paths.pop(index)\n        renamed.append(\n            {\"path\": {\"old\": old_path, \"new\": path}, \"hash\": path_hash}\n        )\n\n    return renamed\n", "path": "dvc/repo/diff.py"}]}