bids validation: unclear purpose of an O(N^2) code

[yarikoptic]

Looking at https://github.com/dandi/dandi-cli/blob/HEAD/dandi/upload.py#L430, the O complexity doesn't matter much besides if I do smth like _bids_discover_and_validate(glob('openneuro/*')) it could eventually cost some CPU cycles, but overall goal is not clear to me there: are we trying to identify "root" BIDS datasets, or what?

whatever we find the reason to be for that code, if warranted, should provide a comment in the code on the purpose. But may be we could just avoid that O(N^2) looping through all possible combinations of bids datasets paths.

[TheChymera]

@yarikoptic I don't think I understand the issue.

dandi-cli/dandi/upload.py

Line 430 in 1c94736

pluralize(len(bids_datasets), "BIDS dataset"),

points to a logger line — or did it use to point to something else?

[yarikoptic]

code changed . it is that block under it

            for p in bids_datasets:
                for bd in bids_datasets:
                    try:
                        p.relative_to(bd)
                    except ValueError:
                        try:
                            bd.relative_to(p)
                        except ValueError:
                            pass
                        else:
                            bids_datasets_to_validate.append(bd)
                    else:
                        bids_datasets_to_validate.append(bd)

[TheChymera]

The purpose is to determine whether any of the datasets are actually subdirectories of any of the others. I guess we could use os.path.abspath(os.path.expanduser()) on all of them and then only compare longer to shorter paths, but that's pretty roundabout and could lead to a lot of unforeseen issues. if you want I can use itertools.product() instead of nested for loops, but I'm not sure whether we can avoid $O(n^2)$ without causing a bigger mess.

[yarikoptic]

ah, this should be achievable in O(N*log(N)) * M where M is maximal depth, typically small... But why do we even need to know that?
I thought that simply "descending" into BIDS dataset can stop when reading another BIDS dataset below. But besides that we do not care and just need to validate all BIDS datasets we find regardless of their "composition" ATM.

[TheChymera]

I thought that simply "descending" into BIDS dataset can stop when reading another BIDS dataset below.

This is implemented upstream, but not yet in DANDI (and also not in #1050 ). I suggest we keep this code until we link to the upstream library at which point this and numerous other issues will evaporate :)