Crate scopegraphs

Warning

This software is actively being developed, tested and documented. Most features work, but we cannot guarantee api stability just yet, nor is the documentation as good as we want it to be. If you don’t understand something, feel free to either document it for us, or let us know.

This library is not ready for production usage

Scope graphs are an abstraction that allow you to express the complicated name resolution patterns that many programming languages have. Put simply, a scope graph encodes what names are defined in which scopes of a program, and how scopes relate to each other. Then, we can run queries over this graph to create links from usages of names to definitions of names. However, to make name resolution flexible, the building of the graph and the querying over the graph can happen concurrently: we don’t need an entire graph before we can start querying it.

This library, and its documentation serve as both a kind of reference implementation of scope graphs, a usable library for your programming language, a tutorial of how to use scope graphs and a tutorial of how you could implement scope graphs yourself.

Research

Scope graphs are based on research. These are some papers that introduce the topic in a more scientific fashion than we will here. That is on purpose: The documentation of this library are meant to be the more informal explanation of scope graphs.

• Néron, P., Tolmach, A., Visser, E., & Wachsmuth, G. (2015). A theory of name resolution. Containing first introduction of scope graphs.
• van Antwerpen, H., Bach Poulsen, C., Rouvoet, A., & Visser, E. (2018). Scopes as types. Presents a refinement of the older scope graphs, which this library is based on.
• Zwaan, A., & van Antwerpen, H. (2023). Scope graphs: The story so far. Provides a more detailed overview of all work that involved scope graphs until the date of publication.

But more research is ongoing! See our research overview page for an overview of all research that involves scope graphs.

This Documentation

• Explanation of Concepts used in scope graphs
• Examples:
  • Standard patterns
• API Docs

Modules

completeness

This module contains several utilities to guarantee query stability.

conceptsdocumentation

Concepts of scope graphs

containers

This module contains some generic containers for data used by the resolution algorithm.

future_wrapper

Defines a cloneable pointer to a future.

patternsdocumentation

Common patterns in scope graphs

renderdot

Render scope graphs to graphviz .dot files.

resolve

This module contains code to query scope graphs.

Macros

add_edge

Adds an edge to the scope graph

add_scope

Creates a scope (with some data if specified), and permission to extend it for each label specified in the label list argument.

compile_regex

Compile a regular expression into Rust code.

label_order

Define a label ordering, an implementation of LabelOrder

query_regex

query_regex is a wrapper around compile_regex that should be used when you’re using the resulting regex only once, inline. This is often the case in scope graph queries.

Structs

Automaton

A regex automaton is a compiled regular expression.

DynamicMatcher

Matched regular expressions that are compiled at runtime.

Scope

Representation of scopes (nodes in the scope graph).

ScopeGraph

Scope Graph data structure.

Storage

Holds data for a ScopeGraph. Required to construct a ScopeGraph.

Enums

ParseError

An error that can ocur while parsing a regular expression.

Regex

A regular expression that can specify a path through a scope graph.

Traits

Label

Represents types that can be used as labels on scopegraph edges.

RegexMatcher

A type that can match a regex. Can be created at compile time through the compile_regex macro, or at runtime with the dynamic feature through Automaton::matcher.

Functions

parse_regex

parse a string to a regular expression

Derive Macros

Label

Derive Label implementation.