Repository: mne-tools/mne-bids
Pull request #1355 (2024-12-18 16:22:50)

WIP Rework mne bids path match
<!--
Thanks for contributing this pull request (PR).
If this is your first time, make sure to read
[CONTRIBUTING.md](https://github.com/mne-tools/mne-bids/blob/main/CONTRIBUTING.md)
-->

PR Description
--------------

When `_return_root_paths` now uses `ignore_nosub`, it can benefit from from only exploring directories within `root/sub-*` instead of exploring the whole tree and subsequently applying the regex filter on visited files.

 `get_entity_vals` is extended by an argument `include_match` to introduce a prefilter on regex path match. This is a whitelist approach, and extends both functionality and performance compared to a equivalent blacklist approach of existing option `ignore_dirs`.


Merge checklist
---------------

Maintainer, please confirm the following before merging.
If applicable:

- [ ] All comments are resolved
- [ ] This is not your own PR
- [ ] All CIs are happy
- [ ] PR title starts with [MRG]
- [ ] [whats_new.rst](https://github.com/mne-tools/mne-bids/blob/main/doc/whats_new.rst) is updated
- [ ] New contributors have been added to [CITATION.cff](https://github.com/mne-tools/mne-bids/blob/main/CITATION.cff)
- [ ] PR description includes phrase "closes <#issue-number>"


welcome[bot]: Hello! 👋 Thanks for opening your first pull request here!
Please read the [contributor guide](https://github.com/mne-tools/mne-bids/blob/main/CONTRIBUTING.md), and please follow the steps outlined in the *"Instructions for first-time contributors"* section therein. ❤️ We will try to get back to you soon. 🚴🏽‍♂️

codecov[bot]: ## [Codecov](https://app.codecov.io/gh/mne-tools/mne-bids/pull/1355?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=mne-tools) Report
Attention: Patch coverage is `75.00000%` with `5 lines` in your changes missing coverage. Please review.
> Project coverage is 97.35%. Comparing base [(`46f284b`)](https://app.codecov.io/gh/mne-tools/mne-bids/commit/46f284bf899e793a8a23a46c42c9ede09b900612?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=mne-tools) to head [(`4863705`)](https://app.codecov.io/gh/mne-tools/mne-bids/commit/48637053fa94ff6eeae4ae7258be2b3c62140bd1?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=mne-tools).

| [Files with missing lines](https://app.codecov.io/gh/mne-tools/mne-bids/pull/1355?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=mne-tools) | Patch % | Lines |
|---|---|---|
| [mne\_bids/path.py](https://app.codecov.io/gh/mne-tools/mne-bids/pull/1355?src=pr&el=tree&filepath=mne_bids%2Fpath.py&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=mne-tools#diff-bW5lX2JpZHMvcGF0aC5weQ==) | 75.00% | [5 Missing :warning: ](https://app.codecov.io/gh/mne-tools/mne-bids/pull/1355?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=mne-tools) |

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##             main    #1355      +/-   ##
==========================================
- Coverage   97.43%   97.35%   -0.09%     
==========================================
  Files          40       40              
  Lines        8903     8912       +9     
==========================================
+ Hits         8675     8676       +1     
- Misses        228      236       +8     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/mne-tools/mne-bids/pull/1355?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=mne-tools).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=mne-tools).

sappelhoff: thanks @waldie11! we have a bit of a backlog right now so please don't worry if we take a bit longer to get back to  you.
waldie11: @sappelhoff happy new year!
no worries, as i had seen some of the api changes in python-mne bringing down the test suite, i already expected priorities to be elsewhere.


waldie11: Hi @sappelhoff ,

I think the true meat is rather a rework of `_return_root_paths`. This is not exactly a API function, so it feels a bit weird to write an example.

`get_entity_vals` seems to undergo some changes within upcoming 0.17 anyhow. I extended the docstring a bit on my feature contribution. Do you think this is sufficient? Neither the `ignore_` parameters have an example. It benefits filtering a `bids_path`, which has deep directory trees for `sourcedata`, `derivatives`, subject or who-knows-what, where one wants to select prehand in which directories to look.

```
my_dataset/
  derivatives/
    downsampled/
      sub-01/
        micr/
          sub-01_sample-01_res-4x_TEM.png
          sub-01_sample-01_res-4x_TEM.json
  sub-01/
    micr/
      sub-01_sample-01_TEM.png
      sub-01_sample-01_TEM.json
```
(BIDS v1.8.0-1 p. 214)

waldie11: Idk how far you are interested in diving into this:

in `test_path_benchmark` I created a dummy bids compliant tree. If I browse this artificial tree with `get_entity_vals`, I extract a performance gain in about one order of magnitude by using `include_match="sub-*/"` in comparison to `ignore_dirs=["derivatives", "sourcedata"]`
waldie11: Thanks for your kind improvements @sappelhoff !

Patch:
diff --git a/doc/authors.rst b/doc/authors.rst
index cc061b1e..22bcd1e4 100644
--- a/doc/authors.rst
+++ b/doc/authors.rst
@@ -5,10 +5,12 @@
 .. _Amaia Benitez: https://github.com/AmaiaBA
 .. _Anand Saini: https://github.com/anandsaini024
 .. _Ariel Rokem: https://github.com/arokem
+.. _Arne Gottwald: https://github.com/waldie11
 .. _Austin Hurst: https://github.com/a-hurst
 .. _Berk Gerçek: https://github.com/berkgercek
 .. _Bruno Hebling Vieira: https://github.com/bhvieira
 .. _Chris Holdgraf: https://bids.berkeley.edu/people/chris-holdgraf
+.. _Christian O'Reilly: https://github.com/christian-oreilly
 .. _Clemens Brunner: https://github.com/cbrnr
 .. _Daniel McCloy: http://dan.mccloy.info
 .. _Denis Engemann: https://github.com/dengemann
@@ -52,4 +54,3 @@
 .. _Tom Donoghue: https://github.com/TomDonoghue
 .. _William Turner: https://bootstrapbill.github.io/
 .. _Yorguin Mantilla: https://github.com/yjmantilla
-.. _Christian O'Reilly: https://github.com/christian-oreilly
diff --git a/doc/whats_new.rst b/doc/whats_new.rst
index fcf11063..9b36f586 100644
--- a/doc/whats_new.rst
+++ b/doc/whats_new.rst
@@ -19,6 +19,7 @@ The following authors contributed for the first time. Thank you so much! 🤩
 
 * `Christian O'Reilly`_
 * `Berk Gerçek`_
+* `Arne Gottwald`_
 
 The following authors had contributed before. Thank you for sticking around! 🤘
 
@@ -35,6 +36,8 @@ Detailed list of changes
 - :func:`mne_bids.write_raw_bids()` can now handle mne `Raw` objects with `eyegaze` and `pupil` channels, by `Christian O'Reilly`_ (:gh:`1344`)
 - :func:`mne_bids.get_entity_vals()` has a new parameter ``ignore_suffixes`` to easily ignore sidecar files, by `Daniel McCloy`_ (:gh:`1362`)
 - Empty-room matching now preferentially finds recordings in the subject directory tagged as `task-noise` before looking in the `sub-emptyroom` directories. This adds support for a part of the BIDS specification for ER recordings, by `Berk Gerçek`_ (:gh:`1364`)
+- Path matching is now implemenented in a more efficient manner within `_return_root_paths`, by `Arne Gottwald` (:gh:`1355`)
+- :func:`mne_bids.get_entity_vals()` has a new parameter ``include_match`` to prefilter item matching and ignore non-matched items from begin of directory scan, by `Arne Gottwald` (:gh:`1355`)
 
 
 🧐 API and behavior changes
@@ -53,6 +56,7 @@ Detailed list of changes
 - :func:`mne_bids.read_raw_bids` can optionally return an ``event_id`` dictionary suitable for use with :func:`mne.events_from_annotations`, and if a ``values`` column is present in ``events.tsv`` it will be used as the source of the integer event ID codes, by `Daniel McCloy`_ (:gh:`1349`)
 - BIDS dictates that the recording entity should be displayed as "_recording-" in the filename. This PR makes :class:`mne_bids.BIDSPath`  correctly display "_recording-" (instead of "_rec-") in BIDSPath.fpath. By `Scott Huberty`_ (:gh:`1348`)
 - :func:`mne_bids.make_dataset_description` now correctly encodes the dataset description as UTF-8 on disk, by `Scott Huberty`_ (:gh:`1357`)
+- Corrects extension match within `_filter_fnames` at end of filename, by `Arne Gottwald` (:gh:`1355`)
 
 ⚕️ Code health
 ^^^^^^^^^^^^^^
diff --git a/mne_bids/path.py b/mne_bids/path.py
index 5c964fee..05ce32a5 100644
--- a/mne_bids/path.py
+++ b/mne_bids/path.py
@@ -12,6 +12,7 @@ import shutil as sh
 from copy import deepcopy
 from datetime import datetime
 from io import StringIO
+from itertools import chain as iter_chain
 from os import path as op
 from pathlib import Path
 from textwrap import indent
@@ -1462,9 +1463,11 @@ def _truncate_tsv_line(line, lim=10):
     """Truncate a line to the specified number of characters."""
     return "".join(
         [
-            str(val) + (lim - len(val)) * " "
-            if len(val) < lim
-            else f"{val[: lim - 1]} "
+            (
+                str(val) + (lim - len(val)) * " "
+                if len(val) < lim
+                else f"{val[: lim - 1]} "
+            )
             for val in line.split("\t")
         ]
     )
@@ -1946,6 +1949,7 @@ def get_entity_vals(
     ignore_datatypes=None,
     ignore_dirs=("derivatives", "sourcedata"),
     ignore_suffixes=None,
+    include_match=None,
     with_key=False,
     verbose=None,
 ):
@@ -2010,6 +2014,9 @@ def get_entity_vals(
     ignore_suffixes : str | array-like of str | None
         Suffixes to ignore. If ``None``, include all suffixes. This can be helpful for
         ignoring non-data sidecars such as `*_scans.tsv` or `*_coordsystem.json`.
+    include_match : str | array-like of str | None
+        Apply a starting match pragma following Unix style pattern syntax from
+        package glob to prefilter search criterion.
 
         .. versionadded:: 0.17
     with_key : bool
@@ -2107,7 +2114,13 @@ def get_entity_vals(
 
     p = re.compile(rf"{entity_long_abbr_map[entity_key]}-(.*?)_")
     values = list()
-    filenames = root.glob(f"**/*{entity_long_abbr_map[entity_key]}-*_*")
+    search_str = f"**/*{entity_long_abbr_map[entity_key]}-*_*"
+    if include_match is not None:
+        include_match = _ensure_tuple(include_match)
+        filenames = [root.glob(im + search_str) for im in include_match]
+        filenames = iter_chain(*filenames)
+    else:
+        filenames = root.glob(search_str)
 
     for filename in filenames:
         # Skip ignored directories
@@ -2358,7 +2371,7 @@ def _filter_fnames(
         r"_desc-(" + "|".join(description) + ")" if description else r"(|_desc-([^_]+))"
     )
     suffix_str = r"_(" + "|".join(suffix) + ")" if suffix else r"_([^_]+)"
-    ext_str = r"(" + "|".join(extension) + ")" if extension else r".([^_]+)"
+    ext_str = r"(" + "|".join(extension) + ")$" if extension else r".([^_]+)"
 
     regexp = (
         leading_path_str
@@ -2502,7 +2515,7 @@ def find_matching_paths(
 
 
 def _return_root_paths(root, datatype=None, ignore_json=True, ignore_nosub=False):
-    """Return all file paths in root.
+    """Return all file paths + .ds paths in root.
 
     Can be filtered by datatype (which is present in the path but not in
     the BIDSPath basename). Can also be list of datatypes.
@@ -2523,29 +2536,50 @@ def _return_root_paths(root, datatype=None, ignore_json=True, ignore_nosub=False
     Returns
     -------
     paths : list of pathlib.Path
-        All paths in `root`, filtered according to the function parameters.
+        All files + .ds paths in `root`, filtered according to the function parameters.
     """
     root = Path(root)  # if root is str
 
-    if datatype is not None:
-        datatype = _ensure_tuple(datatype)
-        search_str = f"*/{'|'.join(datatype)}/*"
-    else:
+    if datatype is None and not ignore_nosub:
         search_str = "*.*"
+        paths = root.rglob(search_str)
+    else:
+        if datatype is not None:
+            datatype = _ensure_tuple(datatype)
+            search_str = f"**/{'|'.join(datatype)}/.*"
+        else:
+            search_str = "**/*.*"
+
+        # only browse files which are of the form root/sub-*,
+        # such that we truely only look in 'sub'-folders:
+
+        if ignore_nosub:
+            search_str = "sub-*/" + search_str
+
+        paths = [
+            Path(root, fn)
+            for fn in glob.iglob(search_str, root_dir=root, recursive=True)
+        ]
 
-    paths = root.rglob(search_str)
     # Only keep files (not directories), ...
     # and omit the JSON sidecars if `ignore_json` is True.
     if ignore_json:
-        paths = [p for p in paths if p.is_file() and p.suffix != ".json"]
+        paths = [
+            p
+            for p in paths
+            if (p.is_file() and p.suffix != ".json")
+            # XXX: generalize with a private func that takes
+            # a config of which "data format" are to be expected like .ds
+            or (p.is_dir() and p.suffix == ".ds")
+        ]
     else:
-        paths = [p for p in paths if p.is_file()]
-
-    # only keep files which are of the form root/sub-*,
-    # such that we only look in 'sub'-folders:
-    if ignore_nosub:
-        root_sub = str(root / "sub-")
-        paths = [p for p in paths if str(p).startswith(root_sub)]
+        paths = [
+            p
+            for p in paths
+            if p.is_file()
+            # XXX: see above, generalize with private func
+            or (p.is_dir() and p.suffix == ".ds")
+        ]
 
     return paths
 


Test patch:
diff --git a/mne_bids/tests/test_path.py b/mne_bids/tests/test_path.py
index c2913d56..43fd2a37 100644
--- a/mne_bids/tests/test_path.py
+++ b/mne_bids/tests/test_path.py
@@ -7,10 +7,12 @@ import os
 import os.path as op
 import shutil
 import shutil as sh
+import timeit
 from datetime import datetime, timezone
 from pathlib import Path
 
 import mne
+import numpy as np
 import pytest
 from mne.datasets import testing
 from mne.io import anonymize_info
@@ -166,6 +168,105 @@ def test_get_entity_vals(entity, expected_vals, kwargs, return_bids_test_dir):
     shutil.rmtree(deriv_path)
 
 
+def test_path_benchmark(tmp_path_factory):
+    """Benchmark exploring bids tree."""
+    # This benchmark is to verify the speed-up in function call get_entity_vals with
+    # `include_match=sub-*/` in face of a bids tree hosting derivatives and sourcedata.
+    n_subjects = 20
+    n_sessions = 10
+    n_derivatives = 17
+    tmp_bids_root = tmp_path_factory.mktemp("mnebids_utils_test_bids_ds")
+
+    derivatives = [
+        Path("derivatives", "derivatives" + str(i)) for i in range(n_derivatives)
+    ]
+
+    bids_subdirectories = ["", "sourcedata", *derivatives]
+
+    # Create a BIDS compliant directory tree with high number of branches
+    for i in range(1, n_subjects):
+        for j in range(1, n_sessions):
+            for subdir in bids_subdirectories:
+                for datatype in ["eeg", "meg"]:
+                    bids_subdir = BIDSPath(
+                        subject=str(i),
+                        session=str(j),
+                        datatype=datatype,
+                        task="audvis",
+                        root=str(tmp_bids_root / subdir),
+                    )
+                    bids_subdir.mkdir(exist_ok=True)
+                    Path(bids_subdir.root / "participants.tsv").touch()
+                    Path(bids_subdir.root / "participants.csv").touch()
+                    Path(bids_subdir.root / "README").touch()
+
+                    # os.makedirs(bids_subdir.directory, exist_ok=True)
+                    Path(
+                        bids_subdir.directory, bids_subdir.basename + "_events.tsv"
+                    ).touch()
+                    Path(
+                        bids_subdir.directory, bids_subdir.basename + "_events.csv"
+                    ).touch()
+
+                    if datatype == "meg":
+                        ctf_path = Path(
+                            bids_subdir.directory, bids_subdir.basename + "_meg.ds"
+                        )
+                        ctf_path.mkdir(exist_ok=True)
+                        Path(ctf_path, bids_subdir.basename + ".meg4").touch()
+                        Path(ctf_path, bids_subdir.basename + ".hc").touch()
+                        Path(ctf_path / "hz.ds").mkdir(exist_ok=True)
+                        Path(ctf_path / "hz.ds" / "hz.meg4").touch()
+                        Path(ctf_path / "hz.ds" / "hz.hc").touch()
+
+    # apply nosub on find_matching_matchs with root level bids directory should
+    # yield a performance boost of order of length from bids_subdirectories.
+    timed_all, timed_ignored_nosub = (
+        timeit.timeit(
+            "mne_bids.find_matching_paths(tmp_bids_root)",
+            setup="import mne_bids\ntmp_bids_root=r'" + str(tmp_bids_root) + "'",
+            number=1,
+        ),
+        timeit.timeit(
+            "mne_bids.find_matching_paths(tmp_bids_root, ignore_nosub=True)",
+            setup="import mne_bids\ntmp_bids_root=r'" + str(tmp_bids_root) + "'",
+            number=10,
+        )
+        / 10,
+    )
+
+    assert (
+        timed_all / (10 * np.maximum(1, np.floor(len(bids_subdirectories) / 10)))
+        # while this should be of same order, lets give it some space by a factor of 2
+        > 0.5 * timed_ignored_nosub
+    )
+
+    # apply include_match on get_entity_vals with root level bids directory should
+    # yield a performance boost of order of length from bids_subdirectories.
+    timed_entity, timed_entity_match = (
+        timeit.timeit(
+            "mne_bids.get_entity_vals(tmp_bids_root, 'session')",
+            setup="import mne_bids\ntmp_bids_root=r'" + str(tmp_bids_root) + "'",
+            number=1,
+        ),
+        timeit.timeit(
+            "mne_bids.get_entity_vals(tmp_bids_root, 'session', include_match='sub-*/')",  # noqa: E501
+            setup="import mne_bids\ntmp_bids_root=r'" + str(tmp_bids_root) + "'",
+            number=10,
+        )
+        / 10,
+    )
+
+    assert (
+        timed_entity / (10 * np.maximum(1, np.floor(len(bids_subdirectories) / 10)))
+        # while this should be of same order, lets give it some space by a factor of 2
+        > 0.5 * timed_entity_match
+    )
+
+    # Clean up
+    shutil.rmtree(tmp_bids_root)
+
+
 def test_search_folder_for_text(capsys):
     """Test finding entries."""
     with pytest.raises(ValueError, match="is not a directory"):