feat!: Add `no_std` Support #747

bushrat011899 · 2025-03-11T03:36:59Z

Objective

Alternative to No_std feature switch #238
Alternative to NO_STD #370
Implements Item 6 from Proposal: Future of this crate #551

Solution

Promoted hashbrown to a direct dependency (currently transient through indexmap)
Added a new std feature, and included it in all features which rely on std for documentation purposes.
Added new CI task to ensure no_std support works (using wasm32v1-none as an example no_std target)
Added several lints which help minimise std usage
Adjusted certain public APIs to allow passing a S: BuildHasher instead of implicitly relying on std::hash::RandomState when the std feature is disabled

Notes

I know this has been attempted several times before and delayed due to a desire to refactor the crate first before adding this functionality. Delays in adding no_std support forced Bevy to drop petgraph from its core crates, relying on a specialised alternative. We'd love to keep using petgraph, but no_std support is now a requirement going forward. This will also come up with wgpu which is also pursuing no_std support here.

BREAKING CHANGE:

Petgraph previously assumed the usage of std::hash::RandomState as the hashing implementation across its codebase. In no_std, this is not possible. To minimise friction for libraries supporting both std and no_std with Petgraph, I have made the following changes to the public API:

`petgraph::algo::simple_paths::all_simple_paths`

This function now has a 3rd generic parameter S which controls the hashing implementation used. Because all_simple_paths is a function it cannot have default generic parameters, so users must specify the hasher themselves.

// Before
let foo = all_simple_paths(/* ... */);

// After
let foo = all_simple_paths::<_, _, std::hash::RandomState>(/* ... */);

Switched from `std::collections::{HashMap, HashSet}` to `hashbrown::{HashMap, HashSet}`

To support no_std, we cannot use the standard library's implementations of HashMap or HashSet. Methods and types previously referencing those collections from std will now reference them from hashbrown. Note that hashbrown was already a dependency of Petgraph, so no change in audit requirements.

Added Hashing Parameter

The following types have had a new generic parameter S added to specify the hashing implementation. Note that when std is enabled, these will all default to std::hash::RandomState, as before.

UnGraphMap
DiGraphMap
MatrixGraph
DiMatrix
UnMatrix
NodeIdentifiers
NodeReferences

Note that for MatrixGraph, DiMatrix, UnMatrix the new S parameter is in the 3rd position (all others have S in the last position). The reason is S has a default parameter with std enabled, but is required with std disabled. This means it must be the last required parameter.

// Before
let foo: MatrixGraph<Foo, Bar, Directed, Option<Bar>, DefaultIx>;

// After
let foo: MatrixGraph<Foo, Bar, std::hash::RandomState, Directed, Option<Bar>, DefaultIx>;

Also note that because Default can now be implemented for multiple versions of the above types (generic over the hasher), you may need to either specify the hasher, or explicitly declare it as default (with the std feature enabled):

// Note that N and E are inferred by code below.
// Before
let foo = UnMatrix::default();

// After (Explicitly infer N and E, but use defaults otherwise)
let foo = UnMatrix::<_, _>::default();

`default-features = false` MSRV is 1.81

If you don't enable the std feature, the MSRV increases to 1.81, when core::error::Error was stabilised. To preserve the original MSRV of 1.64, just enable the std feature.

bushrat011899 · 2025-03-19T22:15:06Z

CI issue caused by not fixing up imports in tests. Should be resolved now; tested with cargo clippy --all-features --lib --bins --examples --tests -- -D warnings locally.

starovoid · 2025-03-20T12:28:30Z

Hi, very nice!

I have looked at the proposed changes and feel satisfied. Can you also add no_std support for the matrix_graph and stable_graph features? This will make no_std support more complete.

github-actions · 2025-03-20T21:56:36Z

This PR contains breaking changes to the public Rust API.

cargo-semver-checks summary


--- failure function_requires_different_generic_type_params: function now requires a different number of generic type parameters ---

Description:
A function now requires a different number of generic type parameters than it used to. Uses of this function that supplied the previous number of generic types (e.g. via turbofish syntax) will be broken.
      ref: https://doc.rust-lang.org/reference/items/generics.html
     impl: https://github.com/obi1kenobi/cargo-semver-checks/tree/v0.40.0/src/lints/function_requires_different_generic_type_params.ron

Failed in:
function all_simple_paths (2 -> 3 generic types) in /home/runner/work/petgraph/petgraph/PR_BRANCH/src/algo/simple_paths.rs:55
function all_simple_paths (2 -> 3 generic types) in /home/runner/work/petgraph/petgraph/PR_BRANCH/src/algo/simple_paths.rs:55

bushrat011899 · 2025-03-20T22:41:48Z

I believe semver-checks needs to be re-run to observe the declared breaking changes, but please let me know if that's not the case and what I need to action!

bushrat011899 · 2025-03-20T22:43:22Z

Can you also add no_std support for the matrix_graph and stable_graph features? This will make no_std support more complete.

I have gone back and added no_std support to all features in Petgraph, excluding rayon and std.

BREAKING CHANGE: refer to petgraph#747 PR description for details on changes.

Updated CI task to highlight that `std` is required for Rust versions between 1.64 and 1.80 inclusive. For 1.81 and above, the `std` feature is not required.

A sufficient number of proposed changes have accumulated to combine them and publish a new major release numbered `0.8.0`. BREAKING CHANGE: This will require the user to provide extra type parameter in some APIs (Read more in #747). ## List of changes - [x] #747 The main innovation of the current release, the long-awaited feature that has become very relevant due to the transition of dependent projects to support `no_std`. - [x] #662 - [x] #611 - [x] #728 - [x] #686 - [x] #737 - [x] #720 - [x] #718 ## Note There are still a large number of PRs that we want to adopt in the near future, so we should expect at least a release of `0.8.1` soon after the completion of `0.8.0`. Thank you all for participating! --------- Co-authored-by: Agustin Borgna <agustinborgna@gmail.com>

The function 'zip' was introduced in petgraph#747 as a part of adding `no_std` support. However, there is already such a function in `core::iter`. The MSRV stated in the description of petgraph#747 was 1.64 at minimum, but the function in `core` is stable since Rust 1.59. Thus, it is an unnecessary duplication and can be removed without consequences.

…849) The function 'zip' was introduced in #747 as a part of adding `no_std` support. However, there is already such a function in `core::iter`. The MSRV stated in the description of #747 was 1.64 at minimum, but the function in `core` is stable since Rust 1.59. Thus, it is an unnecessary duplication and can be removed without consequences.  Co-authored-by: cactusdualcore <cactusdualcore@noreply.codeberg.org>

…etgraph#849) The function 'zip' was introduced in petgraph#747 as a part of adding `no_std` support. However, there is already such a function in `core::iter`. The MSRV stated in the description of petgraph#747 was 1.64 at minimum, but the function in `core` is stable since Rust 1.59. Thus, it is an unnecessary duplication and can be removed without consequences.  Co-authored-by: cactusdualcore <cactusdualcore@noreply.codeberg.org>

bushrat011899 added 2 commits March 11, 2025 14:28

Add no_std Support

7b3dea8

Include indexmap/std in std feature

10fcfbe

ItsDoot mentioned this pull request Mar 11, 2025

Generalize DiGraph/UnGraph 📊 bevyengine/bevy#18247

Closed

Fix issues in tests caught by CI

dbeed8e

ABorgna changed the title ~~Add no_std Support~~ feat: Add no_std Support Mar 19, 2025

bushrat011899 added 2 commits March 20, 2025 11:15

Fix documentation and ensure std is included in tests

055281b

Merge remote-tracking branch 'upstream/master' into no_std

0a1ccfd

Allow generate, matrix_graph, and stable_graph in no_std

5f39a43

Formatting Imports

7e7fd85

bushrat011899 changed the title ~~feat: Add no_std Support~~ feat!: Add no_std Support Mar 20, 2025

bushrat011899 added 4 commits March 21, 2025 16:28

Fix documentation

592e34e

BREAKING CHANGE: refer to petgraph#747 PR description for details on changes.

Fix MSRV compliance

7c95302

Updated CI task to highlight that `std` is required for Rust versions between 1.64 and 1.80 inclusive. For 1.81 and above, the `std` feature is not required.

Fix warnings and mislabelled import

b971455

Final fix for MSRV

1feb56e

starovoid added this to the 0.8 milestone Mar 21, 2025

Fix type inference for benchmarks

f5399a4

starovoid mentioned this pull request Mar 21, 2025

feat!: Release 0.8.0 #753

Merged

8 tasks

notxvilka approved these changes Mar 21, 2025

View reviewed changes

starovoid added this pull request to the merge queue Mar 21, 2025

Merged via the queue into petgraph:master with commit 5087201 Mar 21, 2025
10 checks passed

starovoid mentioned this pull request Mar 26, 2025

NO_STD #370

Draft

This was referenced Apr 5, 2025

chore: release v0.8.1 #762

Merged

chore: release v0.8.2 starovoid/petgraph#1

Draft

Boshen mentioned this pull request Apr 7, 2025

v0.8.0 impl VisitMap for HashSet breaking change #763

Closed

RaoulLuque mentioned this pull request Jun 21, 2025

No_std feature switch #238

Closed

mnmaita mentioned this pull request Jun 30, 2025

Update petgraph requirement from 0.7 to 0.8 bevyengine/bevy#19878

Merged

cactusdualcore mentioned this pull request Jul 18, 2025

refactor: replace uses of 'crate::util::zip' with 'core::iter::zip' #849

Merged

PanieriLorenzo mentioned this pull request Oct 9, 2025

Add no_std support for dasp_graph, enabling all-no-std feature to include dasp_graph. RustAudio/dasp#195

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

feat!: Add `no_std` Support #747

feat!: Add `no_std` Support #747

Uh oh!

bushrat011899 commented Mar 11, 2025 •

edited

Loading

Uh oh!

bushrat011899 commented Mar 19, 2025

Uh oh!

starovoid commented Mar 20, 2025

Uh oh!

github-actions bot commented Mar 20, 2025 •

edited

Loading

Uh oh!

bushrat011899 commented Mar 20, 2025

Uh oh!

bushrat011899 commented Mar 20, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

feat!: Add no_std Support #747

feat!: Add no_std Support #747

Uh oh!

Conversation

bushrat011899 commented Mar 11, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Objective

Solution

Notes

petgraph::algo::simple_paths::all_simple_paths

Switched from std::collections::{HashMap, HashSet} to hashbrown::{HashMap, HashSet}

Added Hashing Parameter

default-features = false MSRV is 1.81

Uh oh!

bushrat011899 commented Mar 19, 2025

Uh oh!

starovoid commented Mar 20, 2025

Uh oh!

github-actions bot commented Mar 20, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

bushrat011899 commented Mar 20, 2025

Uh oh!

bushrat011899 commented Mar 20, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

feat!: Add `no_std` Support #747

feat!: Add `no_std` Support #747

bushrat011899 commented Mar 11, 2025 •

edited

Loading

`petgraph::algo::simple_paths::all_simple_paths`

Switched from `std::collections::{HashMap, HashSet}` to `hashbrown::{HashMap, HashSet}`

`default-features = false` MSRV is 1.81

github-actions bot commented Mar 20, 2025 •

edited

Loading