Repository: iterative/dvc

Issue:
optimize dvcignore
From https://github.com/iterative/dvc/pull/3867 it is apparent that we need to bench dvcignore and research if anything else there requires optimization. A user (@courentin ) reported that something simple like
```
data/something
bash_projects
mlruns
notebooks
externals
examples
.circleci
.vscode
.pytest_cache
wandb
```
takes a significant time.

- [ ] add benchmark for this to dvc-bench project

Discussion:
karajan1001: ```
(0.00 durations hidden.  Use -vv to show these durations.)
=========================== short test summary info ===========================
FAILED tests/func/test_ignore.py::test_multi_ignore_file - AssertionError: as...
===== 1 failed, 1323 passed, 89 skipped, 8 warnings in 713.38s (0:11:53) ======
The command "bash ./scripts/ci/script.sh" exited with 1.
cache.2
store build cache
```

Might there be more details in the log from Travis CI 
pared: @karajan1001 
The log from Travis indicates that `test_ignore_multi` failed.

```
   def test_multi_ignore_file(tmp_dir, dvc, monkeypatch):
        tmp_dir.gen({"dir": {"subdir": {"should_ignore": "1", "not_ignore": "1"}}})
        tmp_dir.gen(DvcIgnore.DVCIGNORE_FILE, "dir/subdir/*_ignore")
        tmp_dir.gen({"dir": {DvcIgnore.DVCIGNORE_FILE: "!subdir/not_ignore"}})
    
>       assert _files_set("dir", dvc.tree) == {
            "dir/subdir/not_ignore",
            "dir/{}".format(DvcIgnore.DVCIGNORE_FILE),
        }
E       AssertionError: assert {'dir/.dvcignore'} == {'dir/.dvcign...r/not_ignore'}
E         Extra items in the right set:
E         'dir/subdir/not_ignore'
E         Full diff:
E         - {'dir/.dvcignore', 'dir/subdir/not_ignore'}
E         + {'dir/.dvcignore'}
```
karajan1001: > @karajan1001
> The log from Travis indicates that `test_ignore_multi` failed.
> 
> ```
>    def test_multi_ignore_file(tmp_dir, dvc, monkeypatch):
>         tmp_dir.gen({"dir": {"subdir": {"should_ignore": "1", "not_ignore": "1"}}})
>         tmp_dir.gen(DvcIgnore.DVCIGNORE_FILE, "dir/subdir/*_ignore")
>         tmp_dir.gen({"dir": {DvcIgnore.DVCIGNORE_FILE: "!subdir/not_ignore"}})
>     
> >       assert _files_set("dir", dvc.tree) == {
>             "dir/subdir/not_ignore",
>             "dir/{}".format(DvcIgnore.DVCIGNORE_FILE),
>         }
> E       AssertionError: assert {'dir/.dvcignore'} == {'dir/.dvcign...r/not_ignore'}
> E         Extra items in the right set:
> E         'dir/subdir/not_ignore'
> E         Full diff:
> E         - {'dir/.dvcignore', 'dir/subdir/not_ignore'}
> E         + {'dir/.dvcignore'}
> ```

Thank you, but the question is where to get this. 


pared: @karajan1001, you don't see the 'Details' link near check?
![travis](https://user-images.githubusercontent.com/10195618/85918303-c6827b80-b861-11ea-802d-c350a17dc43e.png)

If you follow it, there should be build summary, and you should see Jobs and Stages section, where you can see particular builds.
codecov[bot]: # [Codecov](https://codecov.io/gh/iterative/dvc/pull/4120?src=pr&el=h1) Report
> Merging [#4120](https://codecov.io/gh/iterative/dvc/pull/4120?src=pr&el=desc) into [master](https://codecov.io/gh/iterative/dvc/commit/efcf4e331258ea0893b98275cf5ca28c8bb87b8d&el=desc) will **increase** coverage by `0.31%`.
> The diff coverage is `96.29%`.

[![Impacted file tree graph](https://codecov.io/gh/iterative/dvc/pull/4120/graphs/tree.svg?width=650&height=150&src=pr&token=VOfa1EJWC4)](https://codecov.io/gh/iterative/dvc/pull/4120?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master    #4120      +/-   ##
==========================================
+ Coverage   92.45%   92.76%   +0.31%     
==========================================
  Files         162      162              
  Lines       11274    11278       +4     
==========================================
+ Hits        10423    10462      +39     
+ Misses        851      816      -35     
```


| [Impacted Files](https://codecov.io/gh/iterative/dvc/pull/4120?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [dvc/command/destroy.py](https://codecov.io/gh/iterative/dvc/pull/4120/diff?src=pr&el=tree#diff-ZHZjL2NvbW1hbmQvZGVzdHJveS5weQ==) | `59.09% <0.00%> (ø)` | |
| [dvc/command/install.py](https://codecov.io/gh/iterative/dvc/pull/4120/diff?src=pr&el=tree#diff-ZHZjL2NvbW1hbmQvaW5zdGFsbC5weQ==) | `64.70% <0.00%> (ø)` | |
| [dvc/logger.py](https://codecov.io/gh/iterative/dvc/pull/4120/diff?src=pr&el=tree#diff-ZHZjL2xvZ2dlci5weQ==) | `87.50% <0.00%> (ø)` | |
| [dvc/remote/base.py](https://codecov.io/gh/iterative/dvc/pull/4120/diff?src=pr&el=tree#diff-ZHZjL3JlbW90ZS9iYXNlLnB5) | `95.54% <ø> (+0.13%)` | :arrow_up: |
| [dvc/repo/plots/\_\_init\_\_.py](https://codecov.io/gh/iterative/dvc/pull/4120/diff?src=pr&el=tree#diff-ZHZjL3JlcG8vcGxvdHMvX19pbml0X18ucHk=) | `92.42% <ø> (ø)` | |
| [dvc/stage/\_\_init\_\_.py](https://codecov.io/gh/iterative/dvc/pull/4120/diff?src=pr&el=tree#diff-ZHZjL3N0YWdlL19faW5pdF9fLnB5) | `99.12% <ø> (ø)` | |
| [dvc/utils/fs.py](https://codecov.io/gh/iterative/dvc/pull/4120/diff?src=pr&el=tree#diff-ZHZjL3V0aWxzL2ZzLnB5) | `92.85% <ø> (-0.06%)` | :arrow_down: |
| [dvc/api.py](https://codecov.io/gh/iterative/dvc/pull/4120/diff?src=pr&el=tree#diff-ZHZjL2FwaS5weQ==) | `97.67% <100.00%> (ø)` | |
| [dvc/command/base.py](https://codecov.io/gh/iterative/dvc/pull/4120/diff?src=pr&el=tree#diff-ZHZjL2NvbW1hbmQvYmFzZS5weQ==) | `96.87% <100.00%> (+0.20%)` | :arrow_up: |
| [dvc/command/diff.py](https://codecov.io/gh/iterative/dvc/pull/4120/diff?src=pr&el=tree#diff-ZHZjL2NvbW1hbmQvZGlmZi5weQ==) | `94.20% <100.00%> (ø)` | |
| ... and [32 more](https://codecov.io/gh/iterative/dvc/pull/4120/diff?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/iterative/dvc/pull/4120?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/iterative/dvc/pull/4120?src=pr&el=footer). Last update [efcf4e3...25bfcd3](https://codecov.io/gh/iterative/dvc/pull/4120?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

karajan1001: Needs more tests. And Some Improvements
karajan1001: > If you follow it, there should be build summary, and you should see Jobs and Stages section, where you can see particular builds.
@pared 

For example in
https://travis-ci.com/github/iterative/dvc/jobs/354665083

I can only get this.
![image](https://user-images.githubusercontent.com/6745454/85938779-c312f100-b942-11ea-8151-df662cc4c177.png)

No more detail.


efiop: Hi @karajan1001 ! Full logs are starting here https://travis-ci.com/github/iterative/dvc/jobs/354665083#L3357 
karajan1001: > Hi @karajan1001 ! Full logs are starting here https://travis-ci.com/github/iterative/dvc/jobs/354665083#L3357

@efiop  Thank you, it seems that only members of the DVC have the permission. 
![image](https://user-images.githubusercontent.com/6745454/85968700-565a2e00-b9f8-11ea-98d3-495f58dbe4af.png)

karajan1001: More tests are needed.
skshetry: @karajan1001, from your https://github.com/iterative/dvc/pull/4120#issuecomment-650699341, it looks like you are able to access it. You have to search manually in that huge log for specific test failure. Or, download the raw log and grep locally.

If you are not able to, you can download the log of a specific job with following url: 

`https://api.travis-ci.com/v3/job/{job-id}/log.txt` (subsitute job id)

Eg: https://api.travis-ci.com/v3/job/354665083/log.txt
karajan1001: > @karajan1001, from your [#4120 (comment)](https://github.com/iterative/dvc/pull/4120#issuecomment-650699341), it looks like you are able to access it. You have to search manually in that huge log for specific test failure. Or, download the raw log and grep locally.
> 
> If you are not able to, you can download the log of a specific job with following url:
> 
> `https://api.travis-ci.com/v3/job/{job-id}/log.txt` (subsitute job id)
> 
> Eg: https://api.travis-ci.com/v3/job/354665083/log.txt

@skshetry Thank you, but, I had tried this on this PR 2 days ago. The result is the same as what is in the `https://api.travis-ci.com/v3/job/354665083/log.txt`

![image](https://user-images.githubusercontent.com/6745454/85993815-7c4bf680-ba29-11ea-99ee-8bf6d93a6899.png)

karajan1001: > 1 thing that I found.
> 
> > More tests are needed, especially the merging of two ignore files and the influence of the changing of the dirname .
> 
> Besides that LGTM. @karajan1001 Do you intend to introduce those tests in this PR?

Of course. I would like to add every test I could think of according to the [gitignore document](https://git-scm.com/docs/gitignore).
It would be a systematic test. It may make DVC users in trouble if this algorithm changed frequently.
Like what `PathSpec`'s author says in [cpburnz/python-path-specification#19](https://github.com/cpburnz/python-path-specification/issues/19)

> I suspect the discrepancy is that a .gitignore does additional filtering beyond that of Git's wildmatch algorithm. If I fixed this in my implementation of wildmatch, it could unexpectedly change the results of anyone already using this for a purpose other than emulating .gitingore.



karajan1001: ![Screenshot from 2020-07-05 16-06-01](https://user-images.githubusercontent.com/6745454/86528324-806c8e00-bed9-11ea-800c-e7fdd0e86ee2.png)

Current benchmark result
karajan1001: > No output has been received in the last 10m0s, this potentially indicates a stalled build or something wrong with the build itself.
Check the details on how to adjust your build configuration on: https://docs.travis-ci.com/user/common-build-problems/#build-times-out-because-no-output-was-received
The build has been terminated

What is this error?
pared: @karajan1001 That does not seem like like an issue with your PR, I got the same error in other repository handled by Travis. Maybe it's their issue. For now, I am restarting the build, lets see how does it go this time.
karajan1001: > @karajan1001 That does not seem like like an issue with your PR, I got the same error in other repository handled by Travis. Maybe it's their issue. For now, I am restarting the build, lets see how does it go this time.

@pared Thank you very much.
karajan1001: > It looks like you are reimplementing or completing implementing `GitWildMatchPattern`:
> 
> 1. Is this unavodable?
> 2. If it is then can this be made in `GitWildMatchPattern`?
> 3. If it can't then can it be separated from `dvc/ignore`, i.e. any logic not specific to dvc moved separately?

@Suor Thank you.
I learned a lot from your following advice. 
But, I didn't reimplement `GitWildMatchPattern`. What I'm doing is only changing the relative path of the `.dvcignore` file. And this is required if we merged two `.dvcignore` rules in different paths.
For example, if we had 
```
a
b
```
in  `/home/.dvcignore`
and 
```
!aa
!bb
```
in `/home/dir/.dvcignore`

And if we want to replace these two files in one.  We must translate one of them to another's directory.

We can choose:
1. change `/home/.dvcignore` into `/home/dir` but it is harder  
> But quicker I think because we can drop those rules which only influence other directories.  I was not as familiar with `gitignore` as now when I made this decision and overestimated the difficulty. I'd like to redo it this way this week.

2. change `/home/dir/.dvcignore` into `/home/` and then it would be
```
!/dir/**/aa
!/dir/**/bb
```
Suor: @karajan1001 Yes, this what I meant. You are implementing some math on top of `GitWildMatchPattern`. It looks like `pathspec` is a proper place to place this math or at least make it separate from `dvc/ignore`, i.e. make some `pathspec_math.py` with all those ops, which might be used from `dvc/ignore`:

```python
pattern = pathspec_add(
    (prefix1, pattern1),
    (prefix2, pattern2),
    ...
)
```

Then this `pathspec_math` might be separated or even contributed back to `pathspec`.
karajan1001: > @karajan1001 Yes, this what I meant. You are implementing some math on top of `GitWildMatchPattern`. It looks like `pathspec` is a proper place to place this math or at least make it separate from `dvc/ignore`, i.e. make some `pathspec_math.py` with all those ops, which might be used from `dvc/ignore`:
> 
> ```python
> pattern = join_patterns(
>     (prefix1, pattern1),
>     (prefix2, pattern2),
>     ...
> )
> ```
> 
> Then this `pathspec_math` might be separated or even contributed back to `pathspec`.

@Suor . Thank you. 
Sorry that I overlooked point 3.

I'm busy at work and can't pay much attention here.  

Suor: @karajan1001 NP. This is really nice performance tuning work.
efiop: Thank you @karajan1001 ! 

Patch:
diff --git a/dvc/ignore.py b/dvc/ignore.py
index 946e5077e..2ab78ea00 100644
--- a/dvc/ignore.py
+++ b/dvc/ignore.py
@@ -6,8 +6,10 @@ from itertools import groupby
 from funcy import cached_property
 from pathspec.patterns import GitWildMatchPattern
 from pathspec.util import normalize_file
+from pygtrie import StringTrie
 
 from dvc.path_info import PathInfo
+from dvc.pathspec_math import merge_patterns
 from dvc.scm.tree import BaseTree
 from dvc.system import System
 from dvc.utils import relpath
@@ -23,25 +25,33 @@ class DvcIgnore:
 
 
 class DvcIgnorePatterns(DvcIgnore):
-    def __init__(self, ignore_file_path, tree):
-        assert os.path.isabs(ignore_file_path)
+    def __init__(self, pattern_list, dirname):
+
+        self.pattern_list = pattern_list
+        self.dirname = dirname
+        self.prefix = self.dirname + os.sep
 
-        self.ignore_file_path = ignore_file_path
-        self.dirname = os.path.normpath(os.path.dirname(ignore_file_path))
+        regex_pattern_list = map(
+            GitWildMatchPattern.pattern_to_regex, pattern_list
+        )
 
+        self.ignore_spec = [
+            (ignore, re.compile("|".join(item[0] for item in group)))
+            for ignore, group in groupby(regex_pattern_list, lambda x: x[1])
+            if ignore is not None
+        ]
+
+    @classmethod
+    def from_files(cls, ignore_file_path, tree):
+        assert os.path.isabs(ignore_file_path)
+        dirname = os.path.normpath(os.path.dirname(ignore_file_path))
         with tree.open(ignore_file_path, encoding="utf-8") as fobj:
-            path_spec_lines = fobj.readlines()
-            regex_pattern_list = map(
-                GitWildMatchPattern.pattern_to_regex, path_spec_lines
-            )
-            self.ignore_spec = [
-                (ignore, re.compile("|".join(item[0] for item in group)))
-                for ignore, group in groupby(
-                    regex_pattern_list, lambda x: x[1]
-                )
-                if ignore is not None
+            path_spec_lines = [
+                line for line in map(str.strip, fobj.readlines()) if line
             ]
 
+        return cls(path_spec_lines, dirname)
+
     def __call__(self, root, dirs, files):
         files = [f for f in files if not self.matches(root, f)]
         dirs = [d for d in dirs if not self.matches(root, d, True)]
@@ -51,11 +61,10 @@ class DvcIgnorePatterns(DvcIgnore):
     def matches(self, dirname, basename, is_dir=False):
         # NOTE: `relpath` is too slow, so we have to assume that both
         # `dirname` and `self.dirname` are relative or absolute together.
-        prefix = self.dirname + os.sep
         if dirname == self.dirname:
             path = basename
-        elif dirname.startswith(prefix):
-            rel = dirname[len(prefix) :]
+        elif dirname.startswith(self.prefix):
+            rel = dirname[len(self.prefix) :]
             # NOTE: `os.path.join` is ~x5.5 slower
             path = f"{rel}{os.sep}{basename}"
         else:
@@ -79,13 +88,47 @@ class DvcIgnorePatterns(DvcIgnore):
         return result
 
     def __hash__(self):
-        return hash(self.ignore_file_path)
+        return hash(self.dirname + ":" + "\n".join(self.pattern_list))
 
     def __eq__(self, other):
         if not isinstance(other, DvcIgnorePatterns):
             return NotImplemented
+        return (self.dirname == other.dirname) & (
+            self.pattern_list == other.pattern_list
+        )
+
+    def __bool__(self):
+        return bool(self.pattern_list)
 
-        return self.ignore_file_path == other.ignore_file_path
+
+class DvcIgnorePatternsTrie(DvcIgnore):
+    trie = None
+
+    def __init__(self):
+        if self.trie is None:
+            self.trie = StringTrie(separator=os.sep)
+
+    def __call__(self, root, dirs, files):
+        ignore_pattern = self[root]
+        if ignore_pattern:
+            return ignore_pattern(root, dirs, files)
+        return dirs, files
+
+    def __setitem__(self, root, ignore_pattern):
+        base_pattern = self[root]
+        common_dirname, merged_pattern = merge_patterns(
+            base_pattern.dirname,
+            base_pattern.pattern_list,
+            ignore_pattern.dirname,
+            ignore_pattern.pattern_list,
+        )
+        self.trie[root] = DvcIgnorePatterns(merged_pattern, common_dirname)
+
+    def __getitem__(self, root):
+        ignore_pattern = self.trie.longest_prefix(root)
+        if ignore_pattern:
+            return ignore_pattern.value
+        return DvcIgnorePatterns([], root)
 
 
 class DvcIgnoreDirs(DvcIgnore):
@@ -127,14 +170,19 @@ class DvcIgnoreFilter:
             DvcIgnoreDirs([".git", ".hg", ".dvc"]),
             DvcIgnoreRepo(),
         }
-        for root, dirs, files in self.tree.walk(self.root_dir):
-            self._update(root)
-            dirs[:], files[:] = self(root, dirs, files)
-
-    def _update(self, dirname):
+        ignore_pattern_trie = DvcIgnorePatternsTrie()
+        for root, dirs, _ in self.tree.walk(self.root_dir):
+            ignore_pattern = self._get_ignore_pattern(root)
+            if ignore_pattern:
+                ignore_pattern_trie[root] = ignore_pattern
+                self.ignores.add(ignore_pattern_trie)
+            dirs[:], _ = self(root, dirs, [])
+
+    def _get_ignore_pattern(self, dirname):
         ignore_file_path = os.path.join(dirname, DvcIgnore.DVCIGNORE_FILE)
         if self.tree.exists(ignore_file_path):
-            self.ignores.add(DvcIgnorePatterns(ignore_file_path, self.tree))
+            return DvcIgnorePatterns.from_files(ignore_file_path, self.tree)
+        return None
 
     def __call__(self, root, dirs, files):
         for ignore in self.ignores:
diff --git a/dvc/pathspec_math.py b/dvc/pathspec_math.py
new file mode 100644
index 000000000..7377fe4bc
--- /dev/null
+++ b/dvc/pathspec_math.py
@@ -0,0 +1,85 @@
+# Path Specification Pattern Math
+# Including changing base dir of path specification patterns and merging
+# of two path specification patterns with different base
+# All the operations follow the documents of `gitignore`
+import os
+
+from pathspec.util import normalize_file
+
+
+def _not_ignore(rule):
+    return (True, rule[1:]) if rule.startswith("!") else (False, rule)
+
+
+def _is_comment(rule):
+    return rule.startswith("#")
+
+
+def _remove_slash(rule):
+    if rule.startswith("\\"):
+        return rule[1:]
+    return rule
+
+
+def _match_all_level(rule):
+    if rule[:-1].find("/") >= 0 and not rule.startswith("**/"):
+        if rule.startswith("/"):
+            rule = rule[1:]
+        return False, rule
+    if rule.startswith("**/"):
+        rule = rule[3:]
+    return True, rule
+
+
+def change_rule(rule, rel):
+    rule = rule.strip()
+    if _is_comment(rule):
+        return rule
+    not_ignore, rule = _not_ignore(rule)
+    match_all, rule = _match_all_level(rule)
+    rule = _remove_slash(rule)
+    if not match_all:
+        rule = f"/{rule}"
+    else:
+        rule = f"/**/{rule}"
+    if not_ignore:
+        rule = f"!/{rel}{rule}"
+    else:
+        rule = f"/{rel}{rule}"
+    rule = normalize_file(rule)
+    return rule
+
+
+def _change_dirname(dirname, pattern_list, new_dirname):
+    if new_dirname == dirname:
+        return pattern_list
+    rel = os.path.relpath(dirname, new_dirname)
+    if rel.startswith(".."):
+        raise ValueError("change dirname can only change to parent path")
+
+    return [change_rule(rule, rel) for rule in pattern_list]
+
+
+def merge_patterns(prefix_a, pattern_a, prefix_b, pattern_b):
+    """
+    Merge two path specification patterns.
+
+    This implementation merge two path specification patterns on different
+    bases. It returns the longest common parent directory, and the patterns
+    based on this new base directory.
+    """
+    if not pattern_a:
+        return prefix_b, pattern_b
+    elif not pattern_b:
+        return prefix_a, pattern_a
+
+    longest_common_dir = os.path.commonpath([prefix_a, prefix_b])
+    new_pattern_a = _change_dirname(prefix_a, pattern_a, longest_common_dir)
+    new_pattern_b = _change_dirname(prefix_b, pattern_b, longest_common_dir)
+
+    if len(prefix_a) < len(prefix_b):
+        merged_pattern = new_pattern_a + new_pattern_b
+    else:
+        merged_pattern = new_pattern_b + new_pattern_a
+
+    return longest_common_dir, merged_pattern
diff --git a/setup.cfg b/setup.cfg
index f9dc5b216..826c5f64f 100644
--- a/setup.cfg
+++ b/setup.cfg
@@ -17,7 +17,7 @@ count=true
 [isort]
 include_trailing_comma=true
 known_first_party=dvc,tests
-known_third_party=PyInstaller,RangeHTTPServer,boto3,colorama,configobj,distro,dpath,flaky,flufl,funcy,git,grandalf,mock,moto,nanotime,networkx,packaging,pathspec,pylint,pytest,requests,ruamel,setuptools,shortuuid,shtab,tqdm,voluptuous,yaml,zc
+known_third_party=PyInstaller,RangeHTTPServer,boto3,colorama,configobj,distro,dpath,flaky,flufl,funcy,git,grandalf,mock,moto,nanotime,networkx,packaging,pathspec,pygtrie,pylint,pytest,requests,ruamel,setuptools,shortuuid,shtab,tqdm,voluptuous,yaml,zc
 line_length=79
 force_grid_wrap=0
 use_parentheses=True


Test patch:
diff --git a/tests/func/test_ignore.py b/tests/func/test_ignore.py
index ee9abd943..c9b9feea1 100644
--- a/tests/func/test_ignore.py
+++ b/tests/func/test_ignore.py
@@ -8,6 +8,7 @@ from dvc.ignore import (
     DvcIgnore,
     DvcIgnoreDirs,
     DvcIgnorePatterns,
+    DvcIgnorePatternsTrie,
     DvcIgnoreRepo,
 )
 from dvc.repo import Repo
@@ -98,12 +99,19 @@ def test_ignore_collecting_dvcignores(tmp_dir, dvc, dname):
 
     assert len(dvc.tree.dvcignore.ignores) == 3
     assert DvcIgnoreDirs([".git", ".hg", ".dvc"]) in dvc.tree.dvcignore.ignores
+    ignore_pattern_trie = None
+    for ignore in dvc.tree.dvcignore.ignores:
+        if isinstance(ignore, DvcIgnorePatternsTrie):
+            ignore_pattern_trie = ignore
+
+    assert ignore_pattern_trie is not None
     assert (
-        DvcIgnorePatterns(
+        DvcIgnorePatterns.from_files(
             os.fspath(top_ignore_file), WorkingTree(dvc.root_dir)
         )
-        in dvc.tree.dvcignore.ignores
+        == ignore_pattern_trie[os.fspath(ignore_file)]
     )
+
     assert any(
         i for i in dvc.tree.dvcignore.ignores if isinstance(i, DvcIgnoreRepo)
     )
@@ -236,3 +244,102 @@ def test_ignore_directory(tmp_dir, dvc):
     assert _files_set("dir", dvc.tree) == {
         "dir/{}".format(DvcIgnore.DVCIGNORE_FILE),
     }
+
+
+def test_multi_ignore_file(tmp_dir, dvc, monkeypatch):
+    tmp_dir.gen({"dir": {"subdir": {"should_ignore": "1", "not_ignore": "1"}}})
+    tmp_dir.gen(DvcIgnore.DVCIGNORE_FILE, "dir/subdir/*_ignore")
+    tmp_dir.gen({"dir": {DvcIgnore.DVCIGNORE_FILE: "!subdir/not_ignore"}})
+
+    assert _files_set("dir", dvc.tree) == {
+        "dir/subdir/not_ignore",
+        "dir/{}".format(DvcIgnore.DVCIGNORE_FILE),
+    }
+
+
+def test_pattern_trie_tree(tmp_dir, dvc):
+    tmp_dir.gen(
+        {
+            "top": {
+                "first": {
+                    DvcIgnore.DVCIGNORE_FILE: "a\nb\nc",
+                    "middle": {
+                        "second": {
+                            DvcIgnore.DVCIGNORE_FILE: "d\ne\nf",
+                            "bottom": {},
+                        }
+                    },
+                },
+            },
+            "other": {DvcIgnore.DVCIGNORE_FILE: "1\n2\n3"},
+        }
+    )
+    ignore_pattern_trie = None
+    for ignore in dvc.tree.dvcignore.ignores:
+        if isinstance(ignore, DvcIgnorePatternsTrie):
+            ignore_pattern_trie = ignore
+            break
+
+    assert ignore_pattern_trie is not None
+    ignore_pattern_top = ignore_pattern_trie[os.fspath(tmp_dir / "top")]
+    ignore_pattern_other = ignore_pattern_trie[os.fspath(tmp_dir / "other")]
+    ignore_pattern_first = ignore_pattern_trie[
+        os.fspath(tmp_dir / "top" / "first")
+    ]
+    ignore_pattern_middle = ignore_pattern_trie[
+        os.fspath(tmp_dir / "top" / "first" / "middle")
+    ]
+    ignore_pattern_second = ignore_pattern_trie[
+        os.fspath(tmp_dir / "top" / "first" / "middle" / "second")
+    ]
+    ignore_pattern_bottom = ignore_pattern_trie[
+        os.fspath(tmp_dir / "top" / "first" / "middle" / "second" / "bottom")
+    ]
+    assert not ignore_pattern_top
+    assert (
+        DvcIgnorePatterns([], os.fspath(tmp_dir / "top")) == ignore_pattern_top
+    )
+    assert (
+        DvcIgnorePatterns(["1", "2", "3"], os.fspath(tmp_dir / "other"))
+        == ignore_pattern_other
+    )
+    assert (
+        DvcIgnorePatterns(
+            ["a", "b", "c"], os.fspath(tmp_dir / "top" / "first")
+        )
+        == ignore_pattern_first
+    )
+    assert (
+        DvcIgnorePatterns(
+            ["a", "b", "c"], os.fspath(tmp_dir / "top" / "first")
+        )
+        == ignore_pattern_middle
+    )
+    assert (
+        DvcIgnorePatterns(
+            [
+                "a",
+                "b",
+                "c",
+                "/middle/second/**/d",
+                "/middle/second/**/e",
+                "/middle/second/**/f",
+            ],
+            os.fspath(tmp_dir / "top" / "first"),
+        )
+        == ignore_pattern_second
+    )
+    assert (
+        DvcIgnorePatterns(
+            [
+                "a",
+                "b",
+                "c",
+                "/middle/second/**/d",
+                "/middle/second/**/e",
+                "/middle/second/**/f",
+            ],
+            os.fspath(tmp_dir / "top" / "first"),
+        )
+        == ignore_pattern_bottom
+    )
diff --git a/tests/unit/test_ignore.py b/tests/unit/test_ignore.py
index 85c46edee..0dcde9c91 100644
--- a/tests/unit/test_ignore.py
+++ b/tests/unit/test_ignore.py
@@ -9,7 +9,7 @@ from dvc.ignore import DvcIgnoreDirs, DvcIgnorePatterns
 def mock_dvcignore(dvcignore_path, patterns):
     tree = MagicMock()
     with patch.object(tree, "open", mock_open(read_data="\n".join(patterns))):
-        ignore_patterns = DvcIgnorePatterns(dvcignore_path, tree)
+        ignore_patterns = DvcIgnorePatterns.from_files(dvcignore_path, tree)
 
     return ignore_patterns
 
diff --git a/tests/unit/test_pathspec_math.py b/tests/unit/test_pathspec_math.py
new file mode 100644
index 000000000..1cc683715
--- /dev/null
+++ b/tests/unit/test_pathspec_math.py
@@ -0,0 +1,72 @@
+import pytest
+
+from dvc.pathspec_math import _change_dirname
+
+
+@pytest.mark.parametrize(
+    "patterns, dirname, changed",
+    [
+        # A line starting with # serves as a comment.
+        ("#comment", "/dir", "#comment"),
+        # Put a backslash ("\") in front of the first hash for patterns that
+        # begin with a hash.
+        ("\\#hash", "/dir", "/dir/**/#hash"),
+        ("\\#hash", "/#dir", "/#dir/**/#hash"),
+        # Trailing spaces are ignored unless they are quoted with
+        # backslash ("\").
+        (" space", "/dir", "/dir/**/space"),
+        ("\\ space", "/dir", "/dir/**/ space"),
+        # An optional prefix "!" which negates the pattern;
+        ("!include", "/dir", "!/dir/**/include"),
+        # Put a backslash ("\") in front of the first "!" for patterns that
+        # begin with a literal "!", for example, "\!important!.txt".
+        ("\\!important!.txt", "/dir", "/dir/**/!important!.txt"),
+        # If there is a separator at the beginning or middle (or both) of the
+        # pattern, then the pattern is relative to the directory level of the
+        # particular .gitignore file itself.
+        ("/separator.txt", "/dir", "/dir/separator.txt"),
+        ("subdir/separator.txt", "/dir", "/dir/subdir/separator.txt"),
+        # Otherwise the pattern may also match at any level below
+        # the .gitignore level.
+        ("no_sep", "/dir", "/dir/**/no_sep"),
+        # If there is a separator at the end of the pattern then the pattern
+        # will only match directories, otherwise the pattern can match both
+        # files and directories.
+        ("doc/fortz/", "/dir", "/dir/doc/fortz/"),
+        ("fortz/", "/dir", "/dir/**/fortz/"),
+        # An asterisk "*" matches anything except a slash.
+        ("*aste*risk*", "/dir", "/dir/**/*aste*risk*"),
+        # The character "?" matches any one character except "/".
+        ("?fi?le?", "/dir", "/dir/**/?fi?le?"),
+        # The range notation, e.g. [a-zA-Z], can be used to match one of the
+        # characters in a range. See fnmatch(3) and the FNM_PATHNAME flag
+        # for a more detailed description.
+        ("[a-zA-Z]file[a-zA-Z]", "/dir", "/dir/**/[a-zA-Z]file[a-zA-Z]"),
+        # Two consecutive asterisks ("**") in patterns matched against full
+        # pathname may have special meaning:
+        # A leading "**" followed by a slash means match in all directories.
+        # For example, "**/foo" matches file or directory "foo" anywhere,
+        # the same as pattern "foo".
+        ("**/foo", "/dir", "/dir/**/foo"),
+        # "**/foo/bar" matches file or directory "bar" anywhere that is
+        # directly under directory "foo".
+        ("**/foo/bar", "/dir", "/dir/**/foo/bar"),
+        # A trailing "/**" matches everything inside.
+        # For example, "abc/**" matches all files inside directory "abc",
+        # relative to the location of the .gitignore file, with infinite depth.
+        ("abc/**", "/dir", "/dir/abc/**"),
+        # A slash followed by two consecutive asterisks then a slash matches
+        # zero or more directories. For example, "a/**/b"
+        # matches "a/b", "a/x/b", "a/x/y/b" and so on.
+        ("a/**/b", "/dir", "/dir/a/**/b"),
+        # Other consecutive asterisks are considered regular asterisks and
+        # will match according to the previous rules.
+        ("/***.txt", "/dir", "/dir/***.txt"),
+        ("data/***", "/dir", "/dir/data/***"),
+        ("***/file.txt", "/dir", "/dir/***/file.txt"),
+        ("***file", "/dir", "/dir/**/***file"),
+        ("a/***/b", "/dir", "/dir/a/***/b"),
+    ],
+)
+def test_dvcignore_pattern_change_dir(tmp_dir, patterns, dirname, changed):
+    assert _change_dirname(dirname, [patterns], "/") == [changed]