cxx_gen/syntax/
toposort.rs

1use crate::syntax::map::{Entry, UnorderedMap as Map};
2use crate::syntax::report::Errors;
3use crate::syntax::{Api, Struct, Type, Types};
4
5enum Mark {
6    Visiting,
7    Visited,
8}
9
10pub(crate) fn sort<'a>(cx: &mut Errors, apis: &'a [Api], types: &Types<'a>) -> Vec<&'a Struct> {
11    let mut sorted = Vec::new();
12    let ref mut marks = Map::new();
13    for api in apis {
14        if let Api::Struct(strct) = api {
15            let _ = visit(cx, strct, &mut sorted, marks, types);
16        }
17    }
18    sorted
19}
20
21fn visit<'a>(
22    cx: &mut Errors,
23    strct: &'a Struct,
24    sorted: &mut Vec<&'a Struct>,
25    marks: &mut Map<*const Struct, Mark>,
26    types: &Types<'a>,
27) -> Result<(), ()> {
28    match marks.entry(strct) {
29        Entry::Occupied(entry) => match entry.get() {
30            Mark::Visiting => return Err(()), // not a DAG
31            Mark::Visited => return Ok(()),
32        },
33        Entry::Vacant(entry) => {
34            entry.insert(Mark::Visiting);
35        }
36    }
37    let mut result = Ok(());
38    for field in &strct.fields {
39        if let Type::Ident(ident) = &field.ty {
40            if let Some(inner) = types.structs.get(&ident.rust) {
41                if visit(cx, inner, sorted, marks, types).is_err() {
42                    cx.error(field, "unsupported cyclic data structure");
43                    result = Err(());
44                }
45            }
46        }
47    }
48    marks.insert(strct, Mark::Visited);
49    sorted.push(strct);
50    result
51}
cxx_gen/syntax/toposort.rs

cxx_gen/syntax/
toposort.rs
