Struct ScopeGraph

pub struct ScopeGraph<'storage, LABEL, DATA, CMPL> { /* private fields */ }

Scope Graph data structure.

As a data structure, scope graphs are simple graphs with labeled nodes and labeled, directed edges.

This trait has three type parameters:

• [LABEL]: the type of the edge labels.
• [DATA]: the type of the scope/node labels.
• [CMPL]: metadata that guarantees query stability (i.e., query results remain valid in the future).

The data structure has been designed for typical scope graph usage scenario’s. For example, there is no support for removing scopes or edges, as this usually does not happen in scope graphs. In addition, there is no data type for edges, as edges should only be traversed, but never leak outside the scope graph structure. Finally, although not made explicit, [LABEL] should be a finite, iterable set.

Implementations

impl<'sg, LABEL: Hash + Eq, DATA, CMPL> ScopeGraph<'sg, LABEL, DATA, CMPL>

where CMPL: CriticalEdgeBasedCompleteness<LABEL, DATA>,

pub fn add_scope_with<I>(&mut self, data: DATA, open_edges: I) -> Scope

where I: IntoIterator<Item = LABEL>,

Adds a new scope with some open edges.

pub fn add_scope_closed(&mut self, data: DATA) -> Scope

Adds a new scope with no open edges.

impl<'sg, LABEL: Hash + Eq, DATA, CMPL> ScopeGraph<'sg, LABEL, DATA, CMPL>

where DATA: Default, CMPL: CriticalEdgeBasedCompleteness<LABEL, DATA>,

pub fn add_scope_default_with<I>(&mut self, open_edges: I) -> Scope

where I: IntoIterator<Item = LABEL>,

Adds a new scope with some open edges and default data.

pub fn add_scope_default_closed(&mut self) -> Scope

Adds a new scope with no open edges and default data.

impl<'sg, LABEL: Hash + Eq, DATA> ScopeGraph<'sg, LABEL, DATA, ExplicitClose<LABEL>>

pub fn close(&self, scope: Scope, label: &LABEL)

Closes an edge, (i.e., prohibit future new

For example, the following program will return an error.

let storage = Storage::new();
let mut sg = ScopeGraph::<Lbl, usize, _>::new(&storage, ExplicitClose::default());

let s1 = sg.add_scope_with(0, [Def]);
let s2 = sg.add_scope_closed(42);

sg.close(s1, &Def);
sg.add_edge(s1, Def, s2).expect_err("cannot add edge after closing edge");

Closing is required to permit queries to traverse these edges:

let storage = Storage::new();
let mut sg = ScopeGraph::<Lbl, usize, _>::new(&storage, ExplicitClose::default());

let s1 = sg.add_scope_with(0, [Def]);
let s2 = sg.add_scope_closed(42);

// Note: not calling `sg.close(s1, &Def)`

let query_result = sg.query()
    .with_path_wellformedness(Regex::new()) // regex: `Def`
    .with_data_wellformedness(|x: &usize| *x == 42) // match `42`
    .resolve(s1);

query_result.expect_err("require s1/Def to be closed");

Closing allows queries to resolve:

let storage = Storage::new();
let mut sg = ScopeGraph::<Lbl, usize, _>::new(&storage, ExplicitClose::default());

let s1 = sg.add_scope_with(0, [Def]);
let s2 = sg.add_scope_closed(42);

// Note: closing the edge *after* creating all edges, *before* doing the query
sg.close(s1, &Def);

let query_result = sg.query()
    .with_path_wellformedness(Regex::new()) // regex: `Def`
    .with_data_wellformedness(|x: &usize| *x == 42) // match `42`
    .resolve(s1);

query_result.expect("query should return result");

impl<'sg, LABEL: Hash + Eq + Copy, DATA> ScopeGraph<'sg, LABEL, DATA, FutureCompleteness<LABEL>>

pub fn close(&self, scope: Scope, label: &LABEL)

TODO: update this example to use futures Closes an edge, (i.e., prohibit future new

For example, the following program will return an error.

let storage = Storage::new();
let mut sg = ScopeGraph::<Lbl, usize, _>::new(&storage, ExplicitClose::default());

let s1 = sg.add_scope_with(0, [Def]);
let s2 = sg.add_scope_closed(42);

sg.close(s1, &Def);
sg.add_edge(s1, Def, s2).expect_err("cannot add edge after closing edge");

Closing is required to permit queries to traverse these edges:

let storage = Storage::new();
let mut sg = ScopeGraph::<Lbl, usize, _>::new(&storage, ExplicitClose::default());

let s1 = sg.add_scope_with(0, [Def]);
let s2 = sg.add_scope_closed(42);

// Note: not calling `sg.close(s1, &Def)`

let query_result = sg.query()
    .with_path_wellformedness(Regex::new()) // regex: `Def`
    .with_data_wellformedness(|x: &usize| *x == 42) // match `42`
    .resolve(s1);

query_result.expect_err("require s1/Def to be closed");

Closing allows queries to resolve:

let storage = Storage::new();
let mut sg = ScopeGraph::<Lbl, usize, _>::new(&storage, ExplicitClose::default());

let s1 = sg.add_scope_with(0, [Def]);
let s2 = sg.add_scope_closed(42);

// Note: closing the edge *after* creating all edges, *before* doing the query
sg.close(s1, &Def);

let query_result = sg.query()
    .with_path_wellformedness(Regex::new()) // regex: `Def`
    .with_data_wellformedness(|x: &usize| *x == 42) // match `42`
    .resolve(s1);

query_result.expect("query should return result");

impl<'storage, LABEL, DATA, CMPL> ScopeGraph<'storage, LABEL, DATA, CMPL>

pub fn query<'sg>( &'sg self, ) -> Query<'storage, 'sg, '_, LABEL, DATA, CMPL, (), DefaultDataWellformedness, DefaultLabelOrder, DefaultDataEquiv>

where 'storage: 'sg,

impl<'storage, LABEL, DATA, CMPL> ScopeGraph<'storage, LABEL, DATA, CMPL>

pub fn new(storage: &'storage Storage, completeness: CMPL) -> Self

impl<'sg, LABEL, DATA> ScopeGraph<'sg, LABEL, DATA, UncheckedCompleteness>

pub unsafe fn raw(storage: &'sg Storage) -> Self

Creates a new scope graph with UncheckedCompleteness as its completeness validation.

Safety

Unsafe, because UncheckedCompleteness does not actually guarantee query stability.

impl<'sg, LABEL, DATA, CMPL> ScopeGraph<'sg, LABEL, DATA, CMPL>

where CMPL: Completeness<LABEL, DATA>,

pub fn add_scope(&self, data: DATA) -> Scope

Add a new scope to the scope graph, with data as its label.

pub fn add_edge( &self, src: Scope, lbl: LABEL, dst: Scope, ) -> CMPL::NewEdgeResult

Add a new edge in the scope graph.

Permission for this is checked by CMPL.

pub fn get_data(&self, scope: Scope) -> &DATA

Get the data associated with a scope.

pub fn get_edges(&self, src: Scope, lbl: LABEL) -> CMPL::GetEdgesResult<'_>

Get the targets of the outgoing edges of a scope with some label.

Permission for this operation is checked by CMPL.

pub fn add_decl( &self, src: Scope, lbl: LABEL, data: DATA, ) -> CMPL::NewEdgeResult

Utility function to add declarations (i.e., scopes with data, without any outgoing edges).

It performs (roughly) the following operation:

fn add_decl(&self, src: Scope, lbl: LABEL, data: DATA) -> CMPL::NewEdgeResult {
    let s_data = self.add_scope(data);
    self.add_edge(src, lbl, s_data);
}

impl<'sg, LABEL, DATA, CMPL> ScopeGraph<'sg, LABEL, DATA, CMPL>

where DATA: Default, CMPL: Completeness<LABEL, DATA>,

pub fn add_scope_default(&self) -> Scope

Add a new scope to the scope graph, with default data.

Trait Implementations

impl<'storage, LABEL: Debug, DATA: Debug, CMPL: Debug> Debug for ScopeGraph<'storage, LABEL, DATA, CMPL>

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

Formats the value using the given formatter.