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