Describe the bug
flow_path traces downstream paths through a D8 flow direction grid by following direction codes from each start cell. The numpy kernel (_flow_path_cpu) and the dask path (_flow_path_dask) both walk downstream in a while True loop with no cycle guard. The loop only stops on NaN, a pit (code 0), or a grid-edge exit.
If the supplied flow direction grid contains a cycle (say, two cells pointing at each other: code 1 East and code 16 West), the walk never hits a terminating condition and loops forever. _flow_path_cpu runs under numba nopython mode, so the loop doesn't check Python signals: you can't Ctrl-C out of it, and the process has to be killed.
flow_path is public and accepts any user-supplied D8 grid, including grids built by hand or produced by other tools. flow_direction() returns acyclic grids, but nothing forces the input to come from flow_direction(). The test suite already notes that "randomly assigned D8 codes can create cycles" (see test_flow_accumulation_d8.py), so cyclic input is a known possibility.
The other hydro D8 kernels survive cycles. The ones built on Kahn's BFS topological sort (flow_accumulation, stream_order, stream_link, flow_length, hand) leave cycle cells unprocessed because they never reach in-degree zero. watershed uses an in-trace state marker that breaks on re-entry. flow_path is the one that doesn't protect itself.
Reproduction
import numpy as np
from xrspatial.hydro import flow_path
from xrspatial.tests.general_checks import create_test_raster
# 2-cycle: (0,0) flows East to (0,1); (0,1) flows West to (0,0)
fd = create_test_raster(np.array([[1.0, 16.0]]), backend='numpy')
sp = create_test_raster(np.array([[5.0, np.nan]]), backend='numpy')
flow_path(fd, sp) # hangs forever
Expected behavior
flow_path should terminate on any input. A downstream path can visit each cell at most once, so the walk can be capped at H*W steps. Past that, the path is in a cycle and should stop.
Affected backends
numpy and dask+numpy directly. cupy and dask+cupy route through _flow_path_cpu / _flow_path_dask, so they inherit the same hang.
Additional context
Found during a security sweep of the hydro D8 modules (denial of service via logic error). The fix is scoped to xrspatial/hydro/flow_path_d8.py.
Describe the bug
flow_pathtraces downstream paths through a D8 flow direction grid by following direction codes from each start cell. The numpy kernel (_flow_path_cpu) and the dask path (_flow_path_dask) both walk downstream in awhile Trueloop with no cycle guard. The loop only stops on NaN, a pit (code 0), or a grid-edge exit.If the supplied flow direction grid contains a cycle (say, two cells pointing at each other: code 1 East and code 16 West), the walk never hits a terminating condition and loops forever.
_flow_path_cpuruns under numbanopythonmode, so the loop doesn't check Python signals: you can't Ctrl-C out of it, and the process has to be killed.flow_pathis public and accepts any user-supplied D8 grid, including grids built by hand or produced by other tools.flow_direction()returns acyclic grids, but nothing forces the input to come fromflow_direction(). The test suite already notes that "randomly assigned D8 codes can create cycles" (seetest_flow_accumulation_d8.py), so cyclic input is a known possibility.The other hydro D8 kernels survive cycles. The ones built on Kahn's BFS topological sort (flow_accumulation, stream_order, stream_link, flow_length, hand) leave cycle cells unprocessed because they never reach in-degree zero. watershed uses an in-trace state marker that breaks on re-entry. flow_path is the one that doesn't protect itself.
Reproduction
Expected behavior
flow_pathshould terminate on any input. A downstream path can visit each cell at most once, so the walk can be capped at H*W steps. Past that, the path is in a cycle and should stop.Affected backends
numpy and dask+numpy directly. cupy and dask+cupy route through
_flow_path_cpu/_flow_path_dask, so they inherit the same hang.Additional context
Found during a security sweep of the hydro D8 modules (denial of service via logic error). The fix is scoped to
xrspatial/hydro/flow_path_d8.py.