Skip to content

fix(AIC-3571): visit every child before its parent in reverse_traverse - #189

Merged
jeffdupont merged 1 commit into
mainfrom
jdupont/aic-3571-reverse-traverse-postorder
Oct 21, 2026
Merged

fix(AIC-3571): visit every child before its parent in reverse_traverse#189
jeffdupont merged 1 commit into
mainfrom
jdupont/aic-3571-reverse-traverse-postorder

Conversation

@jeffdupont

@jeffdupont jeffdupont commented Oct 20, 2026 •
edited by atlassian Bot
Loading

Copy link
Copy Markdown
Contributor

Fixes AIC-3571.

Why

reverse_traverse is meant to visit every child before its parent. It walked up breadth-first from the terminal nodes instead, so a parent was visited as soon as one child was. With root → P, P → T1, P → Q, Q → T2 the order was T1, T2, P, Q, root: P came before its child Q. Anyone building children first from reverse_traverse got a parent without its deeper child. The Python adapters already use their own post-order DFS (_reverse_traverse in claude-agents, _visit in openai-agents), so core now uses the same approach.

Fix

  • packages/client/src/launchdarkly_ai_server/graph.py: reverse_traverse is now a post-order DFS from the root with a visited set. Each node is visited once, every child before its parents, root last. Same signature.
  • packages/openai-agents/.../native_graph.py: a child that is still unbuilt (a cycle back-edge) is dropped with logger.warning instead of raising ValueError.
  • packages/claude-agents/.../native_graph.py: the same case used to be skipped silently. It now logs logger.warning.
  • AGENTS.md no longer says "reverse BFS".

Behaviour changes:

  • Nodes that can't be reached from the root are no longer visited.
  • A graph with no terminal nodes (a pure cycle) is now walked from the root. It used to return None without visiting anything.

Testing

  • make test: 2548 passed, 14 skipped. make typecheck: no issues in 75 files. make lint: all checks passed.
  • New tests: in client test_graph.py, the uneven-depth order (expects T1, T2, Q, P, root) and a cycle visited once each. In openai-agents and claude-agents test_native_graph.py, a cycle back-edge dropped with a warning.
  • With the fix reverted, 3 of the new tests fail: the uneven order ('T2' != 'T1' at index 0 after P), the openai-agents cycle test (ValueError), and the claude-agents cycle test (no warning). The client cycle test also passes on the old code. It stays as a guard that each node is visited once.

Related: js launchdarkly/js-ai-sdk#147 · python #189 · go launchdarkly/go-ai-sdk#12 · spec https://github.com/launchdarkly/ai-sdks-monorepo/pull/73

🤖 Generated with Claude Code

@jeffdupont @claude
fix(AIC-3571): visit every child before its parent in reverse_traverse
4714753 
reverse_traverse walked up from terminal nodes breadth-first, so a parent
was visited as soon as one child was, even when another child sat deeper.
It now does a post-order DFS from the root: each node once, every child
before its parent, root last. The OpenAI and Claude agents adapters drop
an edge whose child is still unbuilt (a cycle back-edge) with a warning
instead of raising or dropping it silently.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
This was referenced Oct 20, 2026
Merged
Merged
@jeffdupont
jeffdupont requested a review from a team October 21, 2026 15:21
jeffdupont added a commit to launchdarkly/go-ai-sdk that referenced this pull request Oct 21, 2026
@jeffdupont @claude
fix(AIC-3571): visit every child before its parent in ReverseTraverse (…
43f86d0 
…#12)

Fixes [AIC-3571](https://launchdarkly.atlassian.net/browse/AIC-3571).

## Why

`ReverseTraverse` is meant to visit every child before its parent. It
walked up breadth-first from the terminal nodes instead, so a parent was
visited as soon as one child was. With root → P, P → T1, P → Q, Q → T2
the order was T1, T2, P, Q, root. `ToClaudeAgents` then built P without
Q's sub-agent tool and logged nothing, so the model could never reach Q.
The Python adapters already use a post-order DFS; this PR makes core
match.

## Fix

- `aiserver/graph.go`: `ReverseTraverse` is now a post-order DFS from
the root with a visited set. Each node is visited once, every child
before its parents, root last. Same signature.
- `claudeagents/native.go`: a child that is still unbuilt (now only a
cycle back-edge) is still dropped, but now with a `Warn` on the SDK
logger (`bridge.Logger()`, which follows `aiserver.SetLogger`).
- `openaiagents` and `langchainagents` don't build from
`ReverseTraverse`, so they need no change.

Behaviour changes:
- Nodes that can't be reached from the root are no longer visited.
- A graph with no terminal nodes (a pure cycle) is now walked from the
root. It used to return nil. The `!ok` fallback in
`claudeagents/native.go` `execute` is now hit only when there is no
root. I left it in place.

## Testing

- `make test` (`go test -race ./...`): 845 passed, 0 failed. `go vet
./...` and `make lint`: clean.
- New tests:
`aiserver.TestReverseTraverseVisitsEveryChildBeforeItsParent` covers the
uneven order (expects T1, T2, Q, P, root) and a cycle visited once each.
`claudeagents.TestToClaudeAgentsCycleBackEdgeDropped` covers the
warning.
- With the fix reverted, both fail: `uneven: reverse order = [T1 T2 P Q
root]`, and the claudeagents test finds no warning in the log.

Related: js launchdarkly/js-ai-sdk#147 · python
launchdarkly/python-ai-sdk#189 · go
#12 · spec
launchdarkly/ai-sdks-monorepo#73

🤖 Generated with [Claude Code](https://claude.com/claude-code)


[AIC-3571]:
https://launchdarkly.atlassian.net/browse/AIC-3571?atlOrigin=eyJpIjoiNWRkNTljNzYxNjVmNDY3MDlhMDU5Y2ZhYzA5YTRkZjUiLCJwIjoiZ2l0aHViLWNvbS1KU1cifQ

Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
@jeffdupont
jeffdupont merged commit 87c73d9 into main Oct 21, 2026
8 checks passed
@jeffdupont
jeffdupont deleted the jdupont/aic-3571-reverse-traverse-postorder branch October 21, 2026 20:12
jeffdupont added a commit to launchdarkly/js-ai-sdk that referenced this pull request Oct 21, 2026
@jeffdupont @claude
fix(AIC-3571): visit every child before its parent in reverseTraverse (…
a17a2ce 
…#147)

Fixes [AIC-3571](https://launchdarkly.atlassian.net/browse/AIC-3571).

## Why

`reverseTraverse` is meant to visit every child before its parent, so
adapters can build children first. It walked up breadth-first from the
terminal nodes instead, so a parent was visited as soon as one child
was. With root → P, P → T1, P → Q, Q → T2 the order was T1, T2, P, Q,
root: P came before its child Q. `toOpenAIAgents` then threw `Child
agent "Q" was not built before parent "P"`, and `toClaudeAgents` built P
without Q's tool and said nothing. The Python adapters already use a
post-order DFS (`_reverse_traverse` in claude-agents, `_visit` in
openai-agents); this PR makes core match.

## Fix

- `packages/client/src/graph.ts`: `reverseTraverse` is now a post-order
DFS from the root with a visited set. Each node is visited once, every
child before its parent, root last. Same signature.
- `packages/openai-agents/src/native-graph.ts`: a child that is still
unbuilt (only possible on a cycle back-edge now) is dropped with a
`console.warn` instead of throwing.
- `packages/claude-agents/src/native-graph.ts`: the same case used to be
dropped silently by `.filter(Boolean)`. It now logs a `console.warn`.
- Doc comments in `types.ts` and `AGENTS.md` no longer say "reverse
BFS".

Behaviour changes:
- Nodes that can't be reached from the root are no longer visited.
- A graph with no terminal nodes (a pure cycle) is now walked from the
root. It used to return `undefined` without visiting anything.

## Testing

- `yarn build`, `yarn typecheck`, `yarn code:check`, `yarn api:check`
(client): all pass.
- `yarn test`: 2335 passed, 11 skipped, 0 failed across 11 suites
(openai-agents: 128 passed).
- New tests: in client, the uneven-depth order (expects T1, T2, Q, P,
root) and a cycle visited once each. In openai-agents, the uneven graph
built through the real `resolveGraph` and `reverseTraverse` (no mock),
plus the cycle back-edge dropped with a warning. In claude-agents, the
cycle back-edge warning.
- With the fix reverted, these fail: the client uneven test (`Q` out of
order), the openai-agents uneven test (`Child agent "Q" was not built
before parent "P"`), and the claude-agents cycle test (no warning). The
client cycle test also passes on the old code. It stays as a guard that
each node is visited once.
- The openai-agents OTel mock gains `setGlobalTracerProvider: vi.fn()`
because the real `initClient` (BYOC path) registers a tracer provider.

Related: js #147 · python
launchdarkly/python-ai-sdk#189 · go
launchdarkly/go-ai-sdk#12 · spec
launchdarkly/ai-sdks-monorepo#73

🤖 Generated with [Claude Code](https://claude.com/claude-code)

<!-- CURSOR_SUMMARY -->
---

> [!NOTE]
> **Overview**
> **`reverseTraverse`** in the core client no longer walks upward
breadth-first from leaves. It now does a **post-order DFS from the
root**: each node is visited once, every descendant before its parent,
root last. That matches Python adapters and fixes uneven graphs where a
parent was visited before a deeper child (e.g. `P` before `Q`), which
broke `toOpenAIAgents` and left `toClaudeAgents` with missing child
tools.
> 
> **Semantics shift:** only nodes reachable from the root are visited; a
graph with no leaves but a cycle from the root is traversed instead of
returning without visiting anything.
> 
> **Native graph adapters** (`toOpenAIAgents`, `toClaudeAgents`) **drop
cycle back-edges** when the child agent/tool was not built yet, emitting
**`[LaunchDarkly] Dropping cyclic edge "…" -> "…"`** via `console.warn`
instead of throwing (OpenAI) or failing silently (Claude).
> 
> Docs/comments in `types.ts` and `AGENTS.md` describe post-order rather
than “reverse BFS.” Tests cover uneven depth order, single visit in
cycles, and end-to-end adapter builds with real `resolveGraph`.
> 
> <sup>Reviewed by [Cursor Bugbot](https://cursor.com/bugbot) for commit
2fb274a. Bugbot is set up for automated
code reviews on this repo. Configure
[here](https://www.cursor.com/dashboard/bugbot).</sup>
<!-- /CURSOR_SUMMARY -->

[AIC-3571]:
https://launchdarkly.atlassian.net/browse/AIC-3571?atlOrigin=eyJpIjoiNWRkNTljNzYxNjVmNDY3MDlhMDU5Y2ZhYzA5YTRkZjUiLCJwIjoiZ2l0aHViLWNvbS1KU1cifQ

Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
@github-actions github-actions Bot mentioned this pull request Oct 21, 2026
Merged
jeffdupont pushed a commit that referenced this pull request Oct 23, 2026
@github-actions
chore: release main (#166)
662d3f2 
🤖 I have created a release *beep* *boop*
---


<details><summary>launchdarkly-ai-server: 0.4.0</summary>

##
[0.4.0](launchdarkly-ai-server-0.3.0...launchdarkly-ai-server-0.4.0)
(2026-10-23)


### ⚠ BREAKING CHANGES

* **evaluations:** keep the management API client internal
([#202](#202))
* **evaluations:** rename base uri to match spec
([#199](#199))
* **evaluations:** add test proving harness edge case matches spec
([#200](#200))
* **evaluations:** route handlers by provider and mode
* **evaluations:** mark evaluations from code as experimental
([#157](#157))

### Experimental

* **evaluations:** add test proving harness edge case matches spec
([#200](#200))
([fa7162e](fa7162e))
* **evaluations:** keep the management API client internal
([#202](#202))
([17270ed](17270ed))
* **evaluations:** mark evaluations from code as experimental
([#157](#157))
([1389765](1389765))
* **evaluations:** rename base uri to match spec
([#199](#199))
([7d93f9c](7d93f9c))
* **evaluations:** route handlers by provider and mode
([f62591f](f62591f))
* **evaluations:** Set JSON as standard for output to pass to judge
([#203](#203))
([ffc728b](ffc728b))
* **skills:** Correct the HTTP 403 advice now that server-side FDv2 is
available to every account
([#178](#178))
([b17e322](b17e322))


### Features

* **agui:** add a shared reader for handler streams
([#164](#164))
([fc08dd5](fc08dd5))
* **AIC-3534:** add a TypeSafe Jev judge handler
([#149](#149))
([1b41ea4](1b41ea4))
* **client:** add configure for SDK defaults
([#158](#158))
([3736767](3736767))
* **langchain:** emit AG-UI text and tool events
([#163](#163))
([ab5e9e1](ab5e9e1))
* **openai:** emit AG-UI text and tool events
([#161](#161))
([2b1b2d4](2b1b2d4))


### Bug Fixes

* **AIC-3570:** re-resolve graph flags on every invoke and stream
([#187](#187))
([8fdc4d4](8fdc4d4))
* **AIC-3571:** visit every child before its parent in reverse_traverse
([#189](#189))
([87c73d9](87c73d9))
* **AIC-3572:** treat a variation without _ldMeta.enabled as disabled
([#184](#184))
([7a0d260](7a0d260))
* **AIC-3574:** build the LaunchDarkly client off the event loop
([#185](#185))
([bf03b6c](bf03b6c))
* **AIC-3576:** record deferred judge scores under the evaluated config
([#190](#190))
([354d3f1](354d3f1))
* **AIC-3577:** send object tool results to the model as JSON
([#188](#188))
([dead4bd](dead4bd))
* **AIC-3596:** name the [otel] extra in the missing-OTel warning
([#186](#186))
([90ce7bf](90ce7bf))
* **client:** match a handler's provides_for after normalizing its mode
([f62591f](f62591f))
* give native graph spans their LaunchDarkly identity
([#121](#121))
([e863b6d](e863b6d))
</details>

<details><summary>launchdarkly-ai-python: 0.3.0</summary>

##
[0.3.0](launchdarkly-ai-python-0.2.0...launchdarkly-ai-python-0.3.0)
(2026-10-23)


### ⚠ BREAKING CHANGES

* **evaluations:** mark evaluations from code as experimental
([#157](#157))

### Experimental

* **evaluations:** mark evaluations from code as experimental
([#157](#157))
([1389765](1389765))
</details>

<details><summary>launchdarkly-ai-claude-agents: 0.2.6</summary>

##
[0.2.6](launchdarkly-ai-claude-agents-0.2.5...launchdarkly-ai-claude-agents-0.2.6)
(2026-10-23)


### Features

* **claude:** emit AG-UI text and tool events
([#165](#165))
([3f3a0ce](3f3a0ce))
* **client:** add configure for SDK defaults
([#158](#158))
([3736767](3736767))


### Bug Fixes

* **AIC-3571:** visit every child before its parent in reverse_traverse
([#189](#189))
([87c73d9](87c73d9))
* **AIC-3577:** send object tool results to the model as JSON
([#188](#188))
([dead4bd](dead4bd))
* **claude-agents:** fail the run when the CLI reports an API error as
success
([#174](#174))
([3d1a768](3d1a768))
* give native graph spans their LaunchDarkly identity
([#121](#121))
([e863b6d](e863b6d))
</details>

<details><summary>launchdarkly-ai-claude-messages: 0.2.5</summary>

##
[0.2.5](launchdarkly-ai-claude-messages-0.2.4...launchdarkly-ai-claude-messages-0.2.5)
(2026-10-23)


### Features

* **claude:** emit AG-UI text and tool events
([#165](#165))
([3f3a0ce](3f3a0ce))
* **client:** add configure for SDK defaults
([#158](#158))
([3736767](3736767))


### Bug Fixes

* **AIC-3577:** send object tool results to the model as JSON
([#188](#188))
([dead4bd](dead4bd))
</details>

<details><summary>launchdarkly-ai-openai-agents: 0.2.6</summary>

##
[0.2.6](launchdarkly-ai-openai-agents-0.2.5...launchdarkly-ai-openai-agents-0.2.6)
(2026-10-23)


### Features

* **client:** add configure for SDK defaults
([#158](#158))
([3736767](3736767))
* **openai:** emit AG-UI text and tool events
([#161](#161))
([2b1b2d4](2b1b2d4))


### Bug Fixes

* **AIC-3571:** visit every child before its parent in reverse_traverse
([#189](#189))
([87c73d9](87c73d9))
* **AIC-3577:** send object tool results to the model as JSON
([#188](#188))
([dead4bd](dead4bd))
* give native graph spans their LaunchDarkly identity
([#121](#121))
([e863b6d](e863b6d))
</details>

<details><summary>launchdarkly-ai-vercel-agents: 0.1.1</summary>

##
[0.1.1](launchdarkly-ai-vercel-agents-0.1.0...launchdarkly-ai-vercel-agents-0.1.1)
(2026-10-23)


### Features

* **AIC-3408:** add Vercel AI SDK messages and agents adapters
([#103](#103))
([64d679e](64d679e))
</details>

<details><summary>launchdarkly-ai-litellm-agents: 0.1.1</summary>

##
[0.1.1](launchdarkly-ai-litellm-agents-0.1.0...launchdarkly-ai-litellm-agents-0.1.1)
(2026-10-23)


### Features

* add LiteLLM messages and agents integrations
([#102](#102))
([f2e9886](f2e9886))
</details>

<details><summary>launchdarkly-ai-openai-messages: 0.2.5</summary>

##
[0.2.5](launchdarkly-ai-openai-messages-0.2.4...launchdarkly-ai-openai-messages-0.2.5)
(2026-10-23)


### Features

* **client:** add configure for SDK defaults
([#158](#158))
([3736767](3736767))
* **openai:** emit AG-UI text and tool events
([#161](#161))
([2b1b2d4](2b1b2d4))


### Bug Fixes

* **AIC-3577:** send object tool results to the model as JSON
([#188](#188))
([dead4bd](dead4bd))
</details>

<details><summary>launchdarkly-ai-vercel-messages: 0.1.1</summary>

##
[0.1.1](launchdarkly-ai-vercel-messages-0.1.0...launchdarkly-ai-vercel-messages-0.1.1)
(2026-10-23)


### Features

* **AIC-3408:** add Vercel AI SDK messages and agents adapters
([#103](#103))
([64d679e](64d679e))
</details>

<details><summary>launchdarkly-ai-litellm-messages: 0.1.1</summary>

##
[0.1.1](launchdarkly-ai-litellm-messages-0.1.0...launchdarkly-ai-litellm-messages-0.1.1)
(2026-10-23)


### Features

* add LiteLLM messages and agents integrations
([#102](#102))
([f2e9886](f2e9886))
</details>

<details><summary>launchdarkly-ai-langchain-agents: 0.2.6</summary>

##
[0.2.6](launchdarkly-ai-langchain-agents-0.2.5...launchdarkly-ai-langchain-agents-0.2.6)
(2026-10-23)


### Features

* **client:** add configure for SDK defaults
([#158](#158))
([3736767](3736767))
* **langchain:** emit AG-UI text and tool events
([#163](#163))
([ab5e9e1](ab5e9e1))


### Bug Fixes

* **AIC-3577:** send object tool results to the model as JSON
([#188](#188))
([dead4bd](dead4bd))
* give native graph spans their LaunchDarkly identity
([#121](#121))
([e863b6d](e863b6d))
</details>

<details><summary>launchdarkly-ai-langchain-messages: 0.2.5</summary>

##
[0.2.5](launchdarkly-ai-langchain-messages-0.2.4...launchdarkly-ai-langchain-messages-0.2.5)
(2026-10-23)


### Features

* **client:** add configure for SDK defaults
([#158](#158))
([3736767](3736767))
* **langchain:** emit AG-UI text and tool events
([#163](#163))
([ab5e9e1](ab5e9e1))


### Bug Fixes

* **AIC-3577:** send object tool results to the model as JSON
([#188](#188))
([dead4bd](dead4bd))
</details>

<details><summary>launchdarkly-ai-opencode-agents: 0.2.0</summary>

##
[0.2.0](launchdarkly-ai-opencode-agents-0.1.0...launchdarkly-ai-opencode-agents-0.2.0)
(2026-10-23)


### ⚠ BREAKING CHANGES

* **opencode:** start and stop opencode serve in the handler
([#198](#198))

### Features

* **opencode-agents:** add an OpenCode handler
([#159](#159))
([fc08e8c](fc08e8c))
* **opencode-agents:** emit the AG-UI text and tool subset
([#162](#162))
([7677621](7677621))
* **opencode-agents:** open one OpenCode session per call
([#179](#179))
([b225113](b225113))
* **opencode-agents:** render agent instruction templates
([#182](#182))
([83175aa](83175aa))
* **opencode:** start and stop opencode serve in the handler
([#198](#198))
([0748dcf](0748dcf))


### Bug Fixes

* **opencode-agents:** own the HTTP client
([#194](#194))
([ed2d419](ed2d419))
* **opencode-agents:** skip judges and record structured history
([#177](#177))
([6fadf1d](6fadf1d))
</details>

<details><summary>launchdarkly-ai-typesafe: 0.1.1</summary>

##
[0.1.1](launchdarkly-ai-typesafe-0.1.0...launchdarkly-ai-typesafe-0.1.1)
(2026-10-23)


### Features

* **AIC-3534:** add a TypeSafe Jev judge handler
([#149](#149))
([1b41ea4](1b41ea4))
</details>

---
This PR was generated with [Release
Please](https://github.com/googleapis/release-please). See
[documentation](https://github.com/googleapis/release-please#release-please).

Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@andrewklatzke andrewklatzke andrewklatzke approved these changes

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@jeffdupont @andrewklatzke