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.
• patternsdocumentation
  Common patterns in scope graphs
• renderdot
  Render scope graphs to graphviz .dot files.
• resolve
  This module contains code to query scope graphs.

Macros

• 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.