# Provenance and modifications — vendored `dagre`
This directory is a vendored copy of the **`dagre` crate, version 0.1.1**
(<https://crates.io/crates/dagre>, source at <https://github.com/kookyleo/dagre-rs>,
repository sha1 `ad891113d80f5d0305962a0e45e88715e15873f4`; the repository is archived).
- **Copyright (c) kookyleo <kookyleo@gmail.com>**
- **Licensed under the Apache License, Version 2.0** — the full text is in
`LICENSE-APACHE` in this directory. konoma itself is MIT; this subtree stays
Apache-2.0 and cannot be relicensed.
- **Upstream released no `NOTICE` file.** The published `dagre-0.1.1.crate` archive
and the repository both contain only `LICENSE` (checked 2026-08-26), so there is no
`NOTICE` content to carry forward under Apache-2.0 §4(d).
`dagre` is itself a port of `@dagrejs/dagre` **3.0.1-pre**, commit
`4713b59bfa05af56cf58aa01e2027adf5d2dcf88` (recorded in upstream's
`[package.metadata.upstream]`). `cross-validate/reference_data.json` is the recorded
output of that JavaScript implementation for 30 graphs and is what `cross_validate.rs`
asserts against.
## Apache-2.0 §4(b): statement of changes
Every `.rs` file in this directory has been modified by the konoma authors and carries
a notice to that effect at the top of the file. This section is the complete list of
what those changes are.
### 1. Where the files went
The crate was flattened into a konoma module. Paths are otherwise preserved so that a
diff against a future `dagre` release stays readable.
| `src/lib.rs` | `mod.rs` |
| `src/util.rs` | `util.rs` |
| `src/graph/**` | `graph/**` |
| `src/layout/**` | `layout/**` |
| `tests/cross_validate.rs` | `cross_validate.rs` (now a `#[cfg(test)] mod`) |
| `cross-validate/**` | `cross-validate/**` |
| `LICENSE` | `LICENSE-APACHE` |
### 2. Module paths
`crate::` was rewritten to `crate::preview::mermaid::layout::` throughout (91
occurrences). `crate::` now means the konoma binary, not the `dagre` library.
### 3. Let-chains desugared (edition 2024 → edition 2021)
Upstream is `edition = "2024"` and uses let-chains (`if let Some(a) = x && let Some(b)
= y { … }`). konoma is `edition = "2021"`, where those do not parse
(`error: let chains are only allowed in Rust 2024 or later`). Cargo has no per-module
edition, so each chain was **mechanically nested** — `if A && B { X }` became
`if A { if B { X } }`. None of the 30 sites had an `else` branch, so the nesting is
semantically identical; the transformation was applied by script, not by hand.
Sites, by upstream line number:
- `src/graph/mod.rs`: 409, 688, 699, 725, 736
- `src/graph/alg.rs`: 667
- `src/graph/tests.rs`: 3116
- `src/layout/mod.rs`: 76, 84, 351, 400, 414, 519, 563
- `src/layout/coordinate_system.rs`: 62
- `src/layout/order/add_subgraph_constraints.rs`: 40
- `src/layout/order/init_order.rs`: 51
- `src/layout/order/mod.rs`: 154
- `src/layout/order/resolve_conflicts.rs`: 140, 147
- `src/layout/parent_dummy_chains.rs`: 72
- `src/layout/position/bk.rs`: 197, 245, 251, 270, 348, 442, 455, 503, 697
- `src/layout/rank/feasible_tree.rs`: 144
- `src/layout/rank/network_simplex.rs`: 50
- `src/layout/util.rs`: 162, 195, 199, 224, 252
- `tests/cross_validate.rs`: 426
Evidence that the desugaring preserved behaviour: upstream's own suite (538 tests) and
the 30-case cross-validation were run against the edition-2021 form before it was moved
into konoma, and both stayed green.
### 4. Lint allowances
`mod.rs` carries a module-level `#![allow(…)]` covering the whole subtree, with the
reason for each lint written next to it. Nothing was rewritten to satisfy a lint,
because every rewrite spends a piece of the dagre.js cross-validation guarantee.
### 5. Reformatted by konoma's rustfmt
`cargo fmt` runs over `src/`, and konoma's edition-2021 rustfmt sorts `use` lists and
wraps lines differently from upstream's edition-2024 style. This is whitespace and
import ordering only; it touched `layout/tests.rs`, `layout/normalize.rs`,
`layout/order/mod.rs`, `layout/position/bk.rs` and
`layout/rank/network_simplex.rs`.
### 5b. Behaviour added: `EdgeLabel::rank_only`
The one place the vendored engine does something upstream does not. `EdgeLabel` gains a
`rank_only: bool` field (`layout/types.rs`), defaulting to **`false`**, and `layout()`
(`layout/mod.rs`) gains two steps around it:
- **11b**, between `removeEdgeLabelProxies` and `normalize`: `take_rank_only_edges` lifts
every edge with the flag out of the graph, remembering its descriptor and label.
- **24b**, between `translateGraph` and `assignNodeIntersects`: `restore_rank_only_edges`
puts each one back under the exact same key, with `points` cleared, so step 25 gives it
the plain border-to-border pair of points it gives any edge with no waypoints.
Between those two lines the edge does not exist, so it builds no dummy chain, occupies no
lane in the ranks it spans, and reaches neither `order` nor `position`; before and after
them it is an ordinary edge, so it holds its `minlen` through the rank phase and is
un-reversed by `acyclic::undo` like any other. konoma sets the flag for one thing only: an
author-dotted "aside" under `mermaid_routing = "konoma-orthogonal"`
(`docs/FEATURE-MERMAID-RENDERER.md` §10-1 item 4).
**This does not weaken the dagre.js cross-validation.** The flag defaults to `false` and the
two new steps are no-ops on a graph that never sets it, which is every graph in
`cross-validate/reference_data.json`, every one of upstream's own 482 unit tests, and every
diagram konoma renders under the default `mermaid_routing = "splines"`.
### 6. Code that was dropped
- **`src/graph/json.rs` (127 lines)** and its `pub mod json;` declaration. It
(de)serialises a `Graph` through serde and is unreachable from the layout pipeline.
Keeping it would have forced `serde_json` to become a *runtime* dependency of konoma
for a feature konoma never calls; as a dev-dependency it is limited to the
cross-validation test.
- **The shortest-path / spanning-tree half of `src/graph/alg.rs`** (upstream lines
232-686): `PathEntry`, `dijkstra`, `dijkstra_with_edge_fn`, `dijkstra_all`,
`bellman_ford`, `floyd_warshall`, `ExtractedPath`/`extract_path`, `reduce`/
`do_reduce`, `prim` and the private `PriorityQueue`. The layout pipeline never calls
any of them. What is kept — `topsort`, `is_acyclic`, `find_cycles`, `tarjan`, `dfs`,
`preorder`, `postorder`, `components` — is used by `layout/` or by `layout/tests.rs`.
The now-unused `EdgeFn` type alias went with them, and `use super::{Edge, Graph}`
became `use super::Graph` because `Edge` was only referenced by the dropped code.
- **56 tests in `src/graph/tests.rs`** that exercise only the dropped functions
(`dijkstra*`, `bellman_ford*`, `floyd_warshall*`, `prim*`, `extract_path*`,
`reduce*`, `priority_queue*`, `all_shortest_paths*`, `json_*`), plus the
`mod alg_internal` test helper that held a second copy of `PriorityQueue`. 482 of
upstream's 538 unit tests remain.
### 7. `cross_validate.rs`
- `use dagre::…` became `use super::…`; the file is now `#[cfg(test)] mod
cross_validate;` rather than an integration test, because konoma is a binary crate
and `tests/` cannot reach into it.
- `include_str!("../cross-validate/…")` became `include_str!("cross-validate/…")`.
- One let-chain desugared (see §3).
- **A stale comment was corrected.** Upstream's line 473 read *"For now, don't assert —
just report. We'll tighten this as we fix divergences."* immediately above a `panic!`
that does assert. The comment now says what the code does.
### 8. Not carried over
Upstream's `Cargo.toml` (the `json` feature and its optional `serde`/`serde_json`
dependencies), `README.md`, `.github/`, `Cargo.lock` and `.gitignore`. konoma picks up
upstream's one runtime dependency, `log`, as a direct dependency instead.
`cross-validate/SETUP.md` and `cross-validate/generate_reference.mjs` **are** carried
over so the baseline can be regenerated; they need Node and are never run from a test.
### Regenerating the baseline from konoma
`LICENSE-APACHE`, `cross-validate/reference_data.json`,
`cross-validate/generate_reference.mjs` and `cross-validate/SETUP.md` are **byte-identical
to upstream 0.1.1** — deliberately, so that a future upstream release diffs cleanly. That
means `SETUP.md` still describes upstream's repository layout. Read it with this mapping:
| `tests/cross_validate.rs` | `src/preview/mermaid/layout/cross_validate.rs` |
| `cross-validate/…` (from the repo root) | `src/preview/mermaid/layout/cross-validate/…` |
| `ref/dagre-js/` (clone target) | anywhere; it is not tracked here either |
| `Cargo.toml` → `[package.metadata.upstream]` | this file's header |
| `README.md` → "Compatibility" | this file's header |
`node generate_reference.mjs` must be run with `src/preview/mermaid/layout/` as the
working directory, since the script resolves `cross-validate/` and `ref/` relative to it.
## Diffing against a future `dagre` release
The vendored tree can be compared to an upstream tarball by undoing the two mechanical
edits first:
```sh
# for each .rs file: drop the 5-line provenance header + its blank line,
# then map the module path back to the crate root
15 of the 31 files are byte-identical to upstream 0.1.1 after that normalisation.