[Refactor]: Extract inline DFS inheritance walk in is/index.ts to a named algorithm

[martyy-code]

Current State

In packages/errors/src/is/index.ts:82-111, the inheritance walk is implemented as an inline DFS using a Set for cycle detection, with a // DFS walk of inheritance tree using stack (prevents GC pressure) comment that names the algorithm but does not extract it.

// DFS walk of inheritance tree using stack (prevents GC pressure)
const stack: ErrorFactory[] = [factory as ErrorFactory];
const seen = new Set<ErrorFactory>();

while (stack.length > 0) {
  const current = stack.pop()!;
  if (seen.has(current)) continue;
  seen.add(current);
  if (current === ErrorType) return true;
  const inherits = (current as ErrorFactory).inherits;
  if (inherits !== undefined) {
    if (Array.isArray(inherits)) {
      for (let i = 0; i < inherits.length; i++) {
        stack.push(inherits[i]);
      }
    } else {
      stack.push(inherits);
    }
  }
}

This is the canonical violation of rule 0005 (Named Algorithms and Independent Data Structures):

"A depth-first search described in three lines of inline code with a // DFS walk comment is not a named algorithm. It is a comment that happens to be near code. A named algorithm is a function, a type, or a class whose name is the concept, and whose body is the implementation."

The rule 0005 "What this looks like in violation" section uses exactly this example to illustrate the smell.

Located in:

• packages/errors/src/is/index.ts:82-111

Problems with current implementation:

• The algorithm is inlined with a comment that names it. The comment is a deferred definition; the code that follows is responsible for delivering on the promise.
• The stack is a primitive Array<ErrorFactory> whose only contract is push / pop. A second algorithm (e.g. a BFS variant) cannot reuse it without duplicating the type.
• The is() function is 60+ lines; the DFS walk is 30 of them. The walk obscures the function's purpose: is is() about discrimination, or about graph traversal?
• The variable names (stack, seen, current, inherits) are local; a reader scanning the function does not know which is which.

Proposed State

After refactoring, the algorithm is extracted to a named function in a shared module, and the data structure is independent:

// error/inheritance-walk.ts
type Stack<T> = {
  push(item: T): void;
  pop(): T | undefined;
  isEmpty(): boolean;
};

const arrayStack = <T>(): Stack<T> => {
  const items: T[] = [];
  return {
    push: (item) => items.push(item),
    pop: () => items.pop(),
    isEmpty: () => items.length === 0,
  };
};

const walkInheritanceDepthFirst = <T>(
  start: T,
  expand: (node: T) => Iterable<T>,
  visit: (node: T) => boolean | void
): boolean => {
  const stack = arrayStack<T>();
  const seen = new Set<T>();
  stack.push(start);
  while (!stack.isEmpty()) {
    const current = stack.pop()!;
    if (seen.has(current)) continue;
    seen.add(current);
    if (visit(current)) return true;
    for (const parent of expand(current)) {
      stack.push(parent);
    }
  }
  return false;
};

// is/index.ts — the consumer
const factoryMatchesType = (
  start: ErrorFactory,
  target: ErrorFactory
): boolean => {
  return walkInheritanceDepthFirst(
    start,
    (factory) => {
      const inherits = factory.inherits;
      if (inherits === undefined) return [];
      return Array.isArray(inherits) ? inherits : [inherits];
    },
    (current) => current === target
  );
};

Expected improvements:

• Rule 0005 compliance: the algorithm is named (walkInheritanceDepthFirst); the data structure is named (Stack<T>) and independent of the algorithm.
• Rule 0007 compliance: is() reads top-down; the first line says what the function does; every subsequent step is a name the reader follows.
• A second algorithm (e.g. walkInheritanceBreadthFirst) can be added by writing the strategy and reusing Stack<T> / Queue<T>.
• The Stack<T> type is reusable across BFS, DFS, and any future undo-log implementation.

Motivation

This refactoring is needed because:

• The inline DFS with a comment-naming-it is the canonical violation of rule 0005. The library should not be a counter-example to its own rules.
• The is() function is 60+ lines; pulling the algorithm out brings the function back to its essence (discriminate an error against a factory).
• The Stack<T> type is a small, focused module that ages well; it does not encode the algorithm that first used it.

Triggers for this work:

• Technical debt accumulation
• Maintainability concerns

Risks

Potential risks:

• Risk 1: The new walkInheritanceDepthFirst introduces function-call overhead in a hot path. — Mitigation: the function is called once per is(err, factory) call; the cost is negligible compared to the Set operations and the instanceof check. The stack.push indirection through a closure is also negligible in modern V8.
• Risk 2: A consumer relies on the iteration order of the inheritance walk. — Mitigation: the order is not part of the public contract; the extracted function preserves the same order (LIFO, newest first).
• Risk 3: The Stack<T> type conflicts with a future Stack class the project might want to add. — Mitigation: the type is in error/inheritance-walk.ts (or similar), scoped to the algorithm module; the name is local. If a Stack class is added later, the type can be renamed without touching the public API.

Migration Plan

Migration approach:

1. Create packages/errors/src/error/inheritance-walk.ts with the Stack<T> type, the arrayStack constructor, and the walkInheritanceDepthFirst function.
2. Update is/index.ts to call the new function; remove the inline DFS.
3. Add tests for the new function in isolation (cycle detection, single inheritance, multiple inheritance, empty inheritance).
4. Run the existing test suite; the public API is unchanged.

Rollback plan: revert the PR.

Backward Compatibility

• This refactoring maintains full backward compatibility

Scope

Files/Folders affected:

• packages/errors/src/error/inheritance-walk.ts (new file)
• packages/errors/src/is/index.ts (DFS replaced with named call)
• packages/errors/tests/ (regression tests + new tests for the extracted algorithm)

Component(s) Affected

• Multiple Components

Note: the component_affected dropdown is calibrated for a web template project. The actual affected component is packages/errors.

Priority

• p0: Critical - Blocking major work or causing bugs
• p1: High - Important, should do soon
• p2: Medium - Normal priority
• p3: Low - Nice to have

Estimated Effort

• effort: xs - Few minutes
• effort: s - Half a day
• effort: m - 1-2 days

Test Coverage Requirements

• Existing tests cover this code area (will update)
• Need to add new tests for this refactor

Testing Approach

Testing strategy:

• Unit tests for the extracted function: cycle detection, single inheritance, multiple inheritance, empty inheritance, no-match case.
• Regression tests: existing is() test cases pass without modification.

Verification steps:

1. pnpm --filter @deessejs/errors test:run
2. pnpm --filter @deessejs/errors type-check
3. pnpm --filter @deessejs/errors build — public dist/ output matches the previous version's behaviour.

Related Issues / Pull Requests

• Related audit: « Hors-P0 mais notables » in the internal audit of packages/errors/src/ against rules 0001-0016, August 2026.
• Related rule: docs/engineering/architecture/rules/0005-named-algorithms-and-independent-data-structures.md.
• Related rule: docs/engineering/architecture/rules/0007-top-down-composition.md.

Relevant Documentation

• Architecture doc: docs/engineering/architecture/rules/0005-named-algorithms-and-independent-data-structures.md
• Architecture doc: docs/engineering/architecture/rules/0007-top-down-composition.md

Pre-Submission Checklist

• I have searched existing issues for related refactoring requests
• Risks and migration plan are documented
• Test coverage approach is defined
• I understand this issue will be labeled according to the project taxonomy
• This is NOT a security vulnerability (see security note above)

[codewizdave]

@martyy-code any thoughts on this issue ?

[marty-action]

Here are my thoughts on this issue.

Summary of issue #79

Title: [Refactor]: Extract inline DFS inheritance walk in is/index.ts to a named algorithm

Opened by: martyy-code
Your comment: Asking @martyy-code for their thoughts
Labels: p1: high, type: refactor
Milestone: arch-rules-audit

The proposal in brief

In packages/errors/src/is/index.ts (lines 82–111) there's an inline depth-first walk over an error inheritance tree using a Set for cycle detection. The author argues:

• It's documented inline as a // DFS walk ... (prevents GC pressure) — a "deferred definition," not a named algorithm.
• The local stack: Array<ErrorFactory> is really a contract (push/pop) but is locked to DFS by being a primitive array.
• The is() function is 60+ lines, and the walk is ~30 of those, obscuring intent.
• This is the canonical violation of rule 0005 (Named Algorithms and Independent Data Structures) and also touches rule 0007 (top-down composition).

The proposed refactor:

1. New file packages/errors/src/error/inheritance-walk.ts containing:
   • a Stack<T> type,
   • an arrayStack<T>() constructor,
   • a walkInheritanceDepthFirst<T>(start, expand, visit) named function.
2. Update is/index.ts to use it, with a factoryMatchesType() helper at the call site.
3. New isolated tests + regression tests.

Priority is p1 (high), effort s (half a day), full backward compatibility, rollback = revert the PR.

My thoughts

The argument is sound and matches good engineering hygiene:

• Rule 0005 is a real concern. An algorithm named only in a comment isn't actually extracted — a reader has to mentally re-implement DFS to verify the code does what's claimed. A named function with a type signature (start, expand, visit) makes the contract explicit.
• The Stack<T> abstraction is genuinely reusable. Right now the array's "stackness" is a convention; if you later need a BFS over the inheritance tree (e.g., for diagnostics or pretty-printing), you'd either reinvent it or copy-paste. Extracting walkInheritanceDepthFirst plus a small Stack<T> is a cheap hedge against that.
• 30 lines inside a 60-line function is the real readability cost. Even if you disagree with the named-algorithm rule, splitting the walk out shrinks is() to its core job (matching a type against a factory), which is independently valuable.

A few things worth checking before approving:

1. Iteration order must be preserved. The current code walks the tree in a specific order so that is() returns the closest-matching type. Any extraction must keep that order — the proposal acknowledges this, but it should be locked in by a regression test against the existing test suite, not just a new isolated test.
2. "Negligible" function-call overhead is fine here. This is type-checking on error construction, not a hot loop. Don't let anyone bikeshed it into inlining again.
3. Naming conflict with a future Stack class. The proposal scopes Stack to inheritance-walk.ts, which is fine. I'd just suggest not exporting it from a barrel/index yet — let it stay module-local until there's a second consumer.
4. Where does walkInheritanceDepthFirst belong? packages/errors/src/error/inheritance-walk.ts is reasonable, but if there's a more general internal/ or algorithms/ directory, that might be a better home so it doesn't read as error-specific. Worth a quick check of the package layout.

Overall: I'd lean toward approve / LGTM once a regression test pinning iteration order is in place. The refactor is small, well-scoped, has a clear rollback path, and aligns with the documented architecture rules.

Want me to:

• pull the actual is/index.ts file and the cited rule docs (0005, 0007) to double-check the claims before you weigh in, or
• draft a review comment on the issue with these points?