1 use crate::syntax::map::{Entry, UnorderedMap as Map};
2 use crate::syntax::report::Errors;
3 use crate::syntax::{Api, Struct, Type, Types};
4
5 enum Mark {
6 Visiting,
7 Visited,
8 }
9
sort<'a>(cx: &mut Errors, apis: &'a [Api], types: &Types<'a>) -> Vec<&'a Struct>10 pub 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
visit<'a>( cx: &mut Errors, strct: &'a Struct, sorted: &mut Vec<&'a Struct>, marks: &mut Map<*const Struct, Mark>, types: &Types<'a>, ) -> Result<(), ()>21 fn 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 }
52