Struct Graph

pub struct Graph<Q, R> { /* private fields */ }

The Graph struct represents a concurrent query dependency graph. It provides the infrastructure for managing, resolving, and optimizing a wide range of queries across a variety of applications, including but not limited to concurrent incremental compilers.

Overview

A Graph instance serves as the central data structure for tracking and managing dependencies between queries (Q) and their respective results (R). This data structure is completely agnostic to the specific use case, and its generic nature makes it adaptable to a multitude of scenarios beyond compiler optimization.

Query Resolution

The Graph type allows for concurrent query resolution, where queries can be resolved in parallel, enhancing performance significantly. The increment method does not block and returns a new iteration of the graph immediately. In fact, the Graph.query method is designed to block as little as possible. In the general case it will block extremely infrequently. This means that queries will be able to continue chugging away as fast as possible with little to no interruptions.

Structure

• new: A QueryNodeMap representing the current state of queries for the current iteration. All new queries and their results are stored in this map. It begins each iteration as an empty map.

• old: A QueryNodeMap serving as a reference to the map from the previous iteration. It is used for validating queries and their results from the current iteration. This reference mechanism provides an efficient way to track and compare query changes across iterations.

• resolver: An associated type (ResolveQuery) used to resolve queries and obtain their results. This type may carry its own state as long as it implements the Sync and Send traits, enabling it to work seamlessly in a multithreaded environment.

Incremental Compilation

In the context of a concurrent incremental compiler, only queries that are determined to be outdated are resolved again. This approach greatly reduces the time required to resolve queries, making the example compiler incremental. The semantic model is still built every time you mutate the compiler’s state, but most of the work is already done and can be reused, resulting in extremely fast model building.

Usage

The Graph type can be employed in a wide range of applications, from compilers to data processing pipelines and more. Its flexibility allows developers to adapt it to their specific use cases.

Considerations

• The Graph is a versatile data structure that can be applied in various scenarios beyond compilers. Its flexibility allows developers to adapt it to their specific use cases.

• The resolver associated with the Graph should be chosen based on the requirements of the application and its thread safety characteristics.

Implementations

impl<Q: Clone + Eq + Hash + Send + Sync, R: Clone + Eq + Send + Sync> Graph<Q, R>

pub fn new(resolver: impl ResolveQuery<Q, R> + 'static) -> Arc<Self>

pub fn query(self: &Arc<Self>, q: Q) -> R

pub fn increment( self: &Arc<Self>, resolver: impl ResolveQuery<Q, R> + 'static, ) -> Arc<Self>

Trait Implementations

impl<Q: Debug + Clone + Eq + Hash, R: Debug + Clone> Debug for Graph<Q, R>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.