0.0.15

Summary

This version introduces Specificity — an ordering and tie-breaking concept for selectors and expressions that allows our runtime to determine which module wins when multiple modules compete for a resource. The idea is borrowed from CSS, where more specific selectors take precedence, and adapted here for globs, selectors, and expressions in ZRX.

Background

ZRX uses selectors to query and subscribe to resources. Selectors can be combined into expressions using ANY, ALL, and NOT operators. Each selector has 6 components, each of which can be a glob pattern:

zrs:<provider>:<resource>:<variant>:<context>:<location>:<fragment>

How Specificity works

Each component contributes to a 4-tuple (A, B, C, L):

• A — literal segments (most specific)
• B — single-wildcard segments (*, ?)
• C — double-wildcard segments (**)
• L — literal character count (tiebreaker)

Tuples are compared lexicographically — higher is more specific. Expressions combine specificities according to their operator: ALL sums them (constraints stack), ANY takes the minimum (only as specific as the broadest arm), and NOT contributes nothing (it filters, but doesn't select).

Examples

zrs:{git,file}:::{docs}:index.md:  # (3, 0, 0, 15)
zrs::::docs:{index,about}.md:      # (2, 0, 0, 12)
zrs:::::index.{md,rst}:            # (1, 0, 0, 8)
zrs:::::{*}:                       # (0, 1, 0, 0)

This is an early alpha — documentation on using specificity in the router and other modules will follow. This release includes the core implementation for selectors and expressions.

Changelog

Breaking changes

• a69615d zrx-graph – replace Graph::with with Graph::adjacent accessor

Features

• b451d42 zrx-id – add ToSpecificity impl for Term and Expression
• a3ea5eb zrx-id – add ToSpecificity impl for Id and Selector
• 38b3ccd zrx-id – add AsRef impl to Id and Selector to obtain Format
• a4b1fd3 zrx-id – add Specificity impl for computing glob ordering
• dd4e3f9 zrx-graph – add Traversal::initial impl to obtain initial nodes

Bug fixes

• 9e6eaa2 zrx-id – computed Specificity for Expression::any not aligned
• 41b3e49 zrx-id – comparison of Id and Selector susceptible to hash collisions

Performance improvements

• dad5ed4 zrx-id – provide dedicated PartialEq impl for Selector
• b2870f5 zrx-id – remove branching in PartialEq impl for Id

Refactorings

• c6fd98e zrx-id – change Specificity computation to non-consuming

0.0.14

Summary

This version includes several improvements to the graph traversal logic, including convergence of traversals, which allows to combine multiple traversals into a single one, as well as several refactorings to improve code clarity and maintainability. Combining traversals is essential for multi-source modules, where traversals are created for each source and then combined and synchronized for execution.

Changelog

Breaking changes

• 6e2a178 zrx-graph – move Graph::empty impl into Graph::default
• 2b23a19 zrx-id – replace IntoExpression with Into<Expression>
• 53cbd20 zrx-executor, zrx-scheduler – make Executor::capacity and Strategy::capacity non-optional
• 12e626f zrx-id – remove Builder::set_* APIs in favor of consuming methods
• 0fb0e31 zrx-graph – rename visitor module into iter

Features

• 8350ec7 zrx-graph – add Traversal::converge impl
• b529775 zrx-graph – add Eq impl for Topology
• fbb9130 zrx-graph – add AsRef impl for Graph
• a84bf3f zrx-graph – add Graph::with and Graph::with_mut operator impls

Bug fixes

• 3679f97 zrx-graph – duplicate initial nodes break Traversal::converge

Performance improvements

• 7f13011 zrx-graph – replace BTreeSet with HashSet in convergence computation

Refactorings

• 565b498 zrx-graph – use CommonDescendants iterator in Traversal::converge
• 3015667 zrx-graph – move Traversal errors into dedicated Error
• 3335e0e zrx-graph – switch to named struct for Topology wrapper
• d23dc3b zrx-id – move Builder construction for Format into Default

0.0.13

Summary

This version fixes a race condition in the computation of running tasks in the executor, which could lead to premature termination of the execution loop. Additionally, it includes various improvements and refactorings across the codebase, such as renaming traits for better clarity, adding missing methods, and optimizing hash computations.

Changelog

Breaking changes

• fb3c836 zrx-id – rename non-consuming TryInto* traits into TryTo*

Features

• 099a9fb zrx-graph – add IntoIterator impl for graph Builder
• 55e9740 zrx-store – add missing StoreMut methods to Collection

Bug fixes

• ac6f0d5 zrx-executor – race condition in task count computation in both strategies
• 2623a30 zrx-id – missing prefix for Default impls of id and selector Builder

Performance improvements

• 0915c4a zrx-id – use ahash for faster precomputing of hashes

Refactorings

• f1c28a7 zrx-executor – simplify Immediate construction methods
• 229fee6 zrx-graph – move Builder instantiation to Default
• d702beb zrx-id, zrx-store – remove elided lifetime on Formatter argument
• 96d4e9a zrx-store – switch Ordered to use BTreeSet for value ordering
• 08c8593 zrx-id – expose Operand and Operator, as they're part of the public API

0.0.12

Summary

This version removes edge weights for Graph, simplifying the implementation, and adds a new Collection trait for dyn-compatible use of Store impls. Additionally, a synchronization bug for barriers was fixed, where deletions of items would not trigger a synchronization event.

Changelog

Breaking changes

• f4a3bd4 zrx-store – require 'static for all keys and values
• 4840dd9 zrx-graph – switch back to Edge for Adjacency construction
• 0ba4522 zrx-graph, zrx-scheduler – remove support for graph weights

Features

• 425cca8 zrx-store – add Collection as a dyn-compatible supertrait for Store*

Bug fixes

• 9ff366c zrx-store – clippy errors for elidable lifetimes
• c5cd1ae zrx-stream – deletions not propagated to barriers

Refactorings

• c72165e zrx-store – require Debug for Key and Value
• ad8d6fb zrx-store – require Debug for Collection

0.0.11

Summary

This version introduces several breaking changes in the zrx-graph and zrx-store crates, along with new features, bug fixes, performance improvements, and refactorings. All of those changes are essential for our work towards a flexible module system.

Changelog

Breaking changes

• 65c5d64 zrx-graph – deprecate Graph::to_edge_graph
• d42b97b zrx-graph – add Graph::weights and adjust trait bounds
• 35556d9 zrx-store – remove Tracked decorator, move tracking into Storage
• 5f9e2ff zrx-store – add StoreWithComparator impl for Tracked decorator
• 71fb1c2 zrx-store – remove with_comparator into trait StoreWithComparator
• cebad3b zrx-store – remove wrong ExactSizeIterator impl for Ordered decorator

Features

• f85a59e zrx-store – add Clone and Eq impls for decorators and queue

Bug fixes

• f6ed3b9 zrx-scheduler – silence deprecation warning before refactoring
• f676de3 zrx-stream – update Stream::sort_* method signatures for StoreWithComparator

Performance improvements

• cd02aa0 zrx-graph – Adjacency creation doesn't require weights
• 5b4f31a zrx-id – improve PartialOrd and Ord impls for Id

Refactorings

• 0dbc6b0 zrx-graph – improve adjacency list construction impl
• 89162e2 zrx-store – relax trait bounds on StoreWithComparator trait
• b114014 zrx-store – relax trait bound of FromIterator impl for Tracked

0.0.10

Summary

This version includes a large refactoring of Iterator impls across various Store decorators, enhancing code clarity and maintainability. Additionally, almost all impl Iterator return-position impl traits (RPITs) have been replaced with concrete Iterator types, which allows to reuse them in other contexts.

Highlights

• Replace impl Iterator RPITs with concrete Iterator types
• Add IntoIterator impls for reference types
• Add Store impls for Slab (ideal for small collections)

Changelog

Breaking changes

• 28e8582 zrx-store – rename Changed to Tracked again and refactor Iterator impls
• 7d21cac zrx – remove litemap from dependencies
• 7f11498 zrx-store – replace impl Iterator in traits with Iterator impls
• b72c6e3 zrx-store – remove litemap impls
• 879a8f4 zrx-store – change behavior of Changes::clear to drop changes

Features

• 381ffa0 zrx-store – add Index impl for Tracked if inner store supports it
• bfebfca zrx-store – add Store impls for Slab
• 03591de zrx-store – export IntoIter impls of decorators
• 20b187d zrx-stream – add back Stream::sort_with and Stream::sort_by

Bug fixes

• 5052bc6 zrx-store – initialize Changed::from_iter with no changed keys

Performance improvements

• 1813573 zrx-store – add inline in Comparator impls
• fbe7f9d zrx-store – improve IntoIterator impl for Ordered decorator
• 04a5761 zrx-store – improve IntoIterator impl for Indexed decorator
• 3b9b02f zrx-store – improve IntoIterator impl for Changed decorator

Refactorings

• 4adbc9e zrx-store – move Indexed::range into own module
• 781d214 zrx-store – add Changes iterator impl for Changed decorator
• 19ebaf6 zrx-id – rename iter.rs into into_iter.rs
• ee9c1a2 zrx-graph – rename iter.rs into into_iter.rs
• e3e5f49 zrx-store – simplify Iterator impl for Indexed decorator
• 98f33c5 zrx-store – remove unnecessary lifetime trait bounds from impls
• 47f6784 zrx-store – remove unnecessary clone in Queue::set_deadline

0.0.9

Summary

This version makes some changes to identifier handling, and introduces custom comparators for ordered decorators. Moreover, a new Changed decorator allows to track modifications for any Store, which is essential for persistent storage.

Highlights

• Ordered decorators now support custom orderings via Comparator
• Converting between Term and Selector is now more convenient
• New Changed decorator for tracking modifications

Changelog

Breaking changes

• 743dcae zrx-store – turn Comparator::cmp into an instance method for flexibility
• d5f939f zrx-store – add Comparator type parameter to Indexed and Ordered decorators
• 6734205 zrx-stream – remove Stream::sort_with and Stream::sort_by
• f59a4a7 zrx-store – add Compare wrapper for customizing ordering
• fd21100 zrx-id – remove Format::iter method
• 44d8423 zrx-id – rename Filter::matches into Filter::candidates

Features

• de089f3 zrx-store – add Comparable::into_inner method
• 0782330 zrx-store – add Changed decorator impl
• 78085df zrx-store – add StoreMut::remove_entry impls
• 21ce47b zrx-id – add TryFrom impl for Term to Selector conversion
• 413a483 zrx-id – export Iter from filter module
• 333edb2 zrx-id – export Builder from filter module
• 38dc727 zrx-id – export IntoExpression from filter module for convenience

Bug fixes

• 69463bb zrx-store – ordering map in Ordered not updated correctly
• 068c5e9 zrx-store – use correct trait bound for PartialEq impls

Performance improvements

• eb05e0e zrx-id – switch Eq for Selector to use pre-computed hash

Refactorings

• adf38be zrx-store – improve Debug impls for decorators
• 7dcaf12 zrx-store – move update_if_changed into collection impl
• de73d23 zrx-store – simplify Litemap::keys and Litemap::values impls

0.0.8

Summary

This version adds extremely fast matching and filtering capabilities for identifiers via the new Filter data type in the zrx-id crate. Fast filtering is essential for efficient inter-communication between modules, and thus an important building block towards a scalable module system.

For instance, it takes less than 3µs to match 10,000 expressions with 100 matches on a common MacBook.

Highlights

• Add Filter for fast and powerful filtering of identifiers

Changelog

Breaking changes

• 1467f79 zrx-id – remove Builder::from for Format
• 10b34a8 zrx-id – add Filter for fast and powerful filtering of identifiers

Bug fixes

• 81cbb3a zrx-id – Filter::matches not correctly handling negations

Performance improvements

• 5cde015 zrx-id – improve Filter matching performance by up to 10x

0.0.7

Summary

This version improves performance of selector matching by up to a factor of 1,000, especially when many components are empty, which is the norm. Additionally, it includes several breaking changes to the API of the zrx-id crate, and makes Distance computation for graphs lazy, saving on O(|V|³) due to the use of Floyd-Warshall.

Highlights

• 1,000x faster selector matching in common cases
• Add id! and selector! creation macros
• Lazy computation of Distance in graphs

Changelog

Breaking changes

• ba0dc92 zrx-id – improve performance of Matcher::matches by up to 1,000x
• ad0ff16 zrx-graph – make Distance matrix creation lazy and use Adjacency
• 19b1de8 zrx-id – remove Builder::new in favor of Selector::builder
• 88b5b1e zrx-id – remove Builder::new in favor of Matcher::builder
• d1ecfcd zrx-id – remove Builder::new in favor of Format::builder
• 872df0b zrx-id – remove Builder::new in favor of Id::builder
• 24f20f3 zrx-graph – remove Builder::new in favor of Graph::builder

Features

• f442b88 zrx-id – add Expression::compile
• 0043407 zrx-id – add Expression traits and impls
• 1f95973 zrx-id – add selector! macro
• f8bf6ca zrx-id – add id! macro
• fc4f9ef zrx-graph – add From impl for graph Builder

Bug fixes

• c7f1b9c zrx-id – qualify calls to id! and selector! macros
• dd99947 zrx-id – Matcher matches any optional component

Refactorings

• f34c272 zrx-id – switch Selector to Id error enum for consistency
• db91466 zrx-id – switch Format to use Box<[u8]> over Vec<u8> for efficiency

0.0.6

Summary

This release adds several Iterator impls and methods to enhance graph traversal and node filtering capabilities, which are necessary to implement a flexible module system.

Highlights

• Add graph! and graph_builder! creation macros
• Add Iterator impls for sources and sinks in embedded subgraphs
• Add Iterator impls for common ancestors and descendants

Changelog

Breaking changes

• 77210a0 zrx-graph, zrx-scheduler – switch Graph iterator to return node indices
• f649076 zrx-graph – use AsRef<[usize]> over IntoIterator for better ergonomics
• d77d178 zrx-graph – remove unnecessary graph algorithm impls

Features

• f6ebfc4 zrx-graph – add Graph::common_descendants to determine common descendants in layers
• 0485b0e zrx-graph – add Graph::common_ancestors to determine common ancestors in layers
• 6f9a6ac zrx-graph – add Graph::filter_sources to determine sources in sets of nodes
• b9e495c zrx-graph – add Graph::filter_sinks to determine sinks in sets of nodes
• e488896 zrx-graph – add methods to check relationships between nodes
• 9d5e6a5 zrx-graph – add graph! and graph_builder! macros

Bug fixes

• 89b9e9e zrx-graph – not all nodes returned in Graph::descendants visitor
• 1162def zrx-graph – not all nodes returned in Graph::ancestors visitor
• d28b60f zrx-graph – visitors don't emit nodes in original order

Refactorings

• 8b261f2 zrx-graph – provide dedicated Iterator impl for Graph::sinks
• bab733d zrx-graph – provide dedicated Iterator impl for Graph::sources
• 4a3fe39 zrx-graph – save a pointer lookup by directly using the adjacency list
• 91be209 zrx-graph – move map method of Graph into operators module
• bed0c61 zrx-graph – reduce number of Rc in Topology to 1