Function dfs

packages/cli/src/cli/utils/buckets.ts:339–368

(i: number, j: number)

  const forbid = options?.forbid;
  const key = (i: number, j: number) => `${i}|${j}`;
  const dfs = (i: number, j: number): boolean => {
    const memoKey = key(i, j);
    if (memo.has(memoKey)) {
      return memo.get(memoKey)!;
    }
    if (i === patternLength) {
      const done = j === sourceLength;
      memo.set(memoKey, done);
      return done;
    }
    let matched = false;
    if (isDoubleStar(pattern[i])) {
      for (let k = j; k <= sourceLength; k += 1) {
        if (dfs(i + 1, k)) {
          parent.set(memoKey, { i2: i + 1, j2: k });
          matched = true;
          break;
        }
      }
    } else if (j < sourceLength && segmentMatches(pattern[i], source[j])) {
      const blocked =
        forbid && forbid.patternIndex === i && forbid.sourceIndex === j;
      if (!blocked && dfs(i + 1, j + 1)) {
        parent.set(memoKey, { i2: i + 1, j2: j + 1 });
        matched = true;
      }
    }
    memo.set(memoKey, matched);
    return matched;
  };

  if (!dfs(0, 0)) {
    return null;