perf(engine): optimize wavefront obj parsing

2 files changed, 291 insertions, 266 deletions

diff --git a/engine/src/file_format/wavefront/common.rs b/engine/src/file_format/wavefront/common.rs
index 8cdfb34..83fd8af 100644
--- a/engine/src/file_format/wavefront/common.rs
+++ b/engine/src/file_format/wavefront/common.rs
@@ -1,5 +1,7 @@
 use std::num::{ParseFloatError, ParseIntError};
 
+use engine_ecs::util::array_vec::ArrayVec;
+
 macro_rules! keyword {
     (
         $(#[$attr: meta])*
@@ -68,9 +70,11 @@ where
     let mut parts = line.split(' ');
     let keyword = KeywordT::from_str(parts.next().unwrap(), line_no)?;
 
-    let arguments = parts
-        .map(|part| Value::parse::<KeywordT>(part, line_no))
-        .collect::<Result<Vec<_>, _>>()?;
+    let mut arguments = ArrayVec::<Value, 16>::default();
+
+    for part in parts {
+        arguments.push(Value::parse::<KeywordT>(part, line_no)?);
+    }
 
     Ok(Some(Statement { keyword, arguments }))
 }
@@ -265,7 +269,7 @@ impl Value
 pub struct Statement<KeywordT: Keyword>
 {
     pub keyword: KeywordT,
-    pub arguments: Vec<Value>,
+    pub arguments: ArrayVec<Value, 16>,
 }
 
 impl<KeywordT: Keyword> Statement<KeywordT>
diff --git a/engine/src/file_format/wavefront/obj.rs b/engine/src/file_format/wavefront/obj.rs
index 3fcb17b..bebe291 100644
--- a/engine/src/file_format/wavefront/obj.rs
+++ b/engine/src/file_format/wavefront/obj.rs
@@ -6,9 +6,12 @@ use std::collections::HashMap;
 use std::fs::read_to_string;
 use std::path::PathBuf;
 
+use engine_ecs::util::Either;
+
 use crate::file_format::wavefront::common::{
     keyword,
     parse_statement_line,
+    Keyword as _,
     ParsingError,
     Statement,
     Triplet,
@@ -20,7 +23,6 @@ use crate::mesh::vertex_buffer::{
     VertexLabel,
 };
 use crate::mesh::{Mesh, VertexAttrType};
-use crate::util::try_option;
 use crate::vector::{Vec2, Vec3};
 
 /// Parses the content of a Wavefront `.obj`.
@@ -34,34 +36,37 @@ pub fn parse(obj_content: &str) -> Result<Obj, Error>
         .enumerate()
         .map(|(line_index, line)| (line_index + 1, line));
 
-    let statements = lines
-        .map(|(line_no, line)| (line_no, parse_statement_line::<Keyword>(line, line_no)))
-        .filter_map(|(line_no, result)| {
-            let opt_statement = match result {
-                Ok(opt_statement) => opt_statement,
-                Err(err) => {
-                    return Some(Err(err));
-                }
-            };
-
-            Some(Ok((line_no, opt_statement?)))
-        })
-        .collect::<Result<Vec<_>, _>>()?;
-
-    let vertex_positions = get_vertex_positions_from_statements(&statements)?;
-    let texture_positions = get_texture_positions_from_statements(&statements)?;
-    let vertex_normals = get_vertex_normals_from_statements(&statements)?;
-    let material_specs = get_material_specs_from_statements(&statements)?;
-    let faces = get_faces_from_statements(&statements, &material_specs)?;
-    let mtl_libs = get_mtl_libs_from_statements(&statements)?;
-
-    Ok(Obj {
-        vertex_positions,
-        vertex_normals,
-        texture_positions,
-        faces,
-        mtl_libs,
-    })
+    let mut item_counts = ItemCounts::default();
+
+    for (line_index, line) in obj_content.lines().enumerate() {
+        if line.is_empty() || line.starts_with('#') {
+            continue;
+        }
+
+        let Some((keyword, _)) = line.split_once(" ") else {
+            continue;
+        };
+
+        let Ok(keyword) = Keyword::from_str(keyword, line_index + 1) else {
+            continue;
+        };
+
+        item_counts.increment_item_cnt_by_keyword(keyword);
+    }
+
+    let mut obj = Obj::with_capacities_from_item_cnts(item_counts);
+
+    let mut parsing_state = ParsingState::default();
+
+    for (line_no, line) in lines {
+        let Some(statement) = parse_statement_line::<Keyword>(line, line_no)? else {
+            continue;
+        };
+
+        obj.handle_statement(line_no, statement, &mut parsing_state)?;
+    }
+
+    Ok(obj)
 }
 
 /// The data of a Wavefront object file.
@@ -73,7 +78,8 @@ pub struct Obj
     pub vertex_normals: Vec<Vec3<f32>>,
     pub texture_positions: Vec<Vec2<f32>>,
     pub faces: Vec<Face>,
-    pub mtl_libs: Vec<Vec<PathBuf>>,
+    pub mtl_libs: Vec<PathBuf>,
+    pub unique_used_material_names: Vec<Box<str>>,
 }
 
 impl Obj
@@ -214,7 +220,6 @@ impl Obj
     {
         self.mtl_libs
             .iter()
-            .flatten()
             .map(|mtl_lib| {
                 Ok(parse_material_lib(&read_to_string(mtl_lib).map_err(
                     |err| MaterialLibsError::ReadingMaterialLibFailed {
@@ -229,6 +234,207 @@ impl Obj
             })
             .collect::<Result<Vec<_>, _>>()
     }
+
+    fn with_capacities_from_item_cnts(item_counts: ItemCounts) -> Self
+    {
+        Self {
+            vertex_positions: Vec::with_capacity(item_counts.pos_cnt),
+            vertex_normals: Vec::with_capacity(item_counts.normal_cnt),
+            texture_positions: Vec::with_capacity(item_counts.uv_cnt),
+            faces: Vec::with_capacity(item_counts.face_cnt),
+            mtl_libs: Vec::with_capacity(item_counts.mtl_lib_cnt),
+            unique_used_material_names: Vec::with_capacity(
+                item_counts.material_usage_cnt,
+            ),
+        }
+    }
+
+    fn handle_statement(
+        &mut self,
+        line_no: usize,
+        statement: Statement<Keyword>,
+        parsing_state: &mut ParsingState,
+    ) -> Result<(), Error>
+    {
+        match statement.keyword {
+            Keyword::V => self.handle_position_statement(line_no, statement),
+            Keyword::Vn => self.handle_normal_statement(line_no, statement),
+            Keyword::Vt => self.handle_uv_statement(line_no, statement),
+            Keyword::F => self.handle_face_statement(line_no, statement, parsing_state),
+            Keyword::Mtllib => self.handle_material_lib_statement(line_no, statement),
+            Keyword::Usemtl => {
+                self.handle_material_usage_statement(line_no, statement, parsing_state)
+            }
+            Keyword::O | Keyword::S => Ok(()),
+        }
+    }
+
+    fn handle_position_statement(
+        &mut self,
+        line_no: usize,
+        statement: Statement<Keyword>,
+    ) -> Result<(), Error>
+    {
+        debug_assert_eq!(statement.keyword, Keyword::V);
+
+        if statement.arguments.len() == 4 {
+            return Err(Error::UnsupportedArgumentCount {
+                keyword: statement.keyword.to_string(),
+                arg_count: statement.arguments.len(),
+                line_no: line_no,
+            });
+        }
+
+        if statement.arguments.len() > 4 {
+            return Err(Error::InvalidArgumentCount {
+                keyword: statement.keyword.to_string(),
+                arg_count: statement.arguments.len(),
+                line_no: line_no,
+            });
+        }
+
+        let x = statement.get_float_arg(0, line_no)?;
+        let y = statement.get_float_arg(1, line_no)?;
+        let z = statement.get_float_arg(2, line_no)?;
+
+        self.vertex_positions.push(Vec3 { x, y, z });
+
+        Ok(())
+    }
+
+    fn handle_uv_statement(
+        &mut self,
+        line_no: usize,
+        statement: Statement<Keyword>,
+    ) -> Result<(), Error>
+    {
+        debug_assert_eq!(statement.keyword, Keyword::Vt);
+
+        if statement.arguments.len() == 3 {
+            return Err(Error::UnsupportedArgumentCount {
+                keyword: statement.keyword.to_string(),
+                arg_count: statement.arguments.len(),
+                line_no: line_no,
+            });
+        }
+
+        if statement.arguments.len() > 3 {
+            return Err(Error::InvalidArgumentCount {
+                keyword: statement.keyword.to_string(),
+                arg_count: statement.arguments.len(),
+                line_no: line_no,
+            });
+        }
+
+        let u = statement.get_float_arg(0, line_no)?;
+        let v = statement.get_float_arg(1, line_no)?;
+
+        self.texture_positions.push(Vec2 { x: u, y: v });
+
+        Ok(())
+    }
+
+    fn handle_normal_statement(
+        &mut self,
+        line_no: usize,
+        statement: Statement<Keyword>,
+    ) -> Result<(), Error>
+    {
+        debug_assert_eq!(statement.keyword, Keyword::Vn);
+
+        if statement.arguments.len() > 3 {
+            return Err(Error::InvalidArgumentCount {
+                keyword: statement.keyword.to_string(),
+                arg_count: statement.arguments.len(),
+                line_no: line_no,
+            });
+        }
+
+        let i = statement.get_float_arg(0, line_no)?;
+        let j = statement.get_float_arg(1, line_no)?;
+        let k = statement.get_float_arg(2, line_no)?;
+
+        self.vertex_normals.push(Vec3 { x: i, y: j, z: k });
+
+        Ok(())
+    }
+
+    fn handle_material_usage_statement(
+        &mut self,
+        line_no: usize,
+        statement: Statement<Keyword>,
+        parsing_state: &mut ParsingState,
+    ) -> Result<(), Error>
+    {
+        debug_assert_eq!(statement.keyword, Keyword::Usemtl);
+
+        if statement.arguments.len() > 1 {
+            return Err(Error::InvalidArgumentCount {
+                keyword: statement.keyword.to_string(),
+                arg_count: statement.arguments.len(),
+                line_no: line_no,
+            });
+        }
+
+        let material_name = statement
+            .get_text_arg(0, line_no)?
+            .to_owned()
+            .into_boxed_str();
+
+        if !self.unique_used_material_names.contains(&material_name) {
+            self.unique_used_material_names.push(material_name.clone());
+        }
+
+        parsing_state.current_material_name = Some(material_name);
+
+        Ok(())
+    }
+
+    fn handle_face_statement(
+        &mut self,
+        line_no: usize,
+        statement: Statement<Keyword>,
+        parsing_state: &mut ParsingState,
+    ) -> Result<(), Error>
+    {
+        debug_assert_eq!(statement.keyword, Keyword::F);
+
+        if statement.arguments.len() > 3 {
+            return Err(Error::UnsupportedArgumentCount {
+                keyword: statement.keyword.to_string(),
+                arg_count: statement.arguments.len(),
+                line_no: line_no,
+            });
+        }
+
+        let vertex_a = statement.get_triplet_arg(0, line_no)?;
+        let vertex_b = statement.get_triplet_arg(1, line_no)?;
+        let vertex_c = statement.get_triplet_arg(2, line_no)?;
+
+        self.faces.push(Face {
+            vertices: [vertex_a.into(), vertex_b.into(), vertex_c.into()],
+            material_name: parsing_state.current_material_name.clone(),
+        });
+
+        Ok(())
+    }
+
+    fn handle_material_lib_statement(
+        &mut self,
+        line_no: usize,
+        statement: Statement<Keyword>,
+    ) -> Result<(), Error>
+    {
+        debug_assert_eq!(statement.keyword, Keyword::Mtllib);
+
+        for (index, value) in statement.arguments.iter().enumerate() {
+            let mtl_lib = PathBuf::from(value.to_text(index, line_no)?);
+
+            self.mtl_libs.push(mtl_lib);
+        }
+
+        Ok(())
+    }
 }
 
 #[derive(Debug)]
@@ -236,7 +442,7 @@ impl Obj
 pub struct Face
 {
     pub vertices: [FaceVertex; 3],
-    pub material_name: Option<String>,
+    pub material_name: Option<Box<str>>,
 }
 
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
@@ -326,6 +532,39 @@ pub enum MaterialLibsError<MaterialLibParseError>
     },
 }
 
+#[derive(Debug, Default)]
+struct ParsingState
+{
+    current_material_name: Option<Box<str>>,
+}
+
+#[derive(Debug, Default)]
+struct ItemCounts
+{
+    pos_cnt: usize,
+    uv_cnt: usize,
+    normal_cnt: usize,
+    face_cnt: usize,
+    mtl_lib_cnt: usize,
+    material_usage_cnt: usize,
+}
+
+impl ItemCounts
+{
+    fn increment_item_cnt_by_keyword(&mut self, keyword: Keyword)
+    {
+        match keyword {
+            Keyword::V => self.pos_cnt += 1,
+            Keyword::Vn => self.normal_cnt += 1,
+            Keyword::Vt => self.uv_cnt += 1,
+            Keyword::F => self.face_cnt += 1,
+            Keyword::Mtllib => self.mtl_lib_cnt += 1,
+            Keyword::Usemtl => self.material_usage_cnt += 1,
+            Keyword::O | Keyword::S => {}
+        }
+    }
+}
+
 keyword! {
     #[derive(Debug, PartialEq, Eq, Clone, Copy)]
     enum Keyword {
@@ -355,233 +594,6 @@ keyword! {
     }
 }
 
-#[derive(Debug)]
-struct MaterialSpecifier
-{
-    material_name: String,
-    line_no: usize,
-}
-
-fn find_material_specifier_for_line_no(
-    material_specifiers: &[MaterialSpecifier],
-    line_no: usize,
-) -> Option<&MaterialSpecifier>
-{
-    material_specifiers
-        .iter()
-        .rev()
-        .find(|material_specifier| material_specifier.line_no < line_no)
-}
-
-enum Either<ValA, ValB>
-{
-    A(ValA),
-    B(ValB),
-}
-
-impl<ValA, ValB, Item> Iterator for Either<ValA, ValB>
-where
-    ValA: Iterator<Item = Item>,
-    ValB: Iterator<Item = Item>,
-{
-    type Item = Item;
-
-    fn next(&mut self) -> Option<Self::Item>
-    {
-        match self {
-            Self::A(iter_a) => iter_a.next(),
-            Self::B(iter_b) => iter_b.next(),
-        }
-    }
-}
-
-fn get_vertex_positions_from_statements(
-    statements: &[(usize, Statement<Keyword>)],
-) -> Result<Vec<Vec3<f32>>, Error>
-{
-    statements
-        .iter()
-        .filter_map(|(line_no, statement)| {
-            if statement.keyword != Keyword::V {
-                return None;
-            }
-
-            if statement.arguments.len() == 4 {
-                return Some(Err(Error::UnsupportedArgumentCount {
-                    keyword: statement.keyword.to_string(),
-                    arg_count: statement.arguments.len(),
-                    line_no: *line_no,
-                }));
-            }
-
-            if statement.arguments.len() > 4 {
-                return Some(Err(Error::InvalidArgumentCount {
-                    keyword: statement.keyword.to_string(),
-                    arg_count: statement.arguments.len(),
-                    line_no: *line_no,
-                }));
-            }
-
-            let x = try_option!(statement.get_float_arg(0, *line_no));
-            let y = try_option!(statement.get_float_arg(1, *line_no));
-            let z = try_option!(statement.get_float_arg(2, *line_no));
-
-            Some(Ok(Vec3 { x, y, z }))
-        })
-        .collect::<Result<Vec<_>, Error>>()
-}
-
-fn get_texture_positions_from_statements(
-    statements: &[(usize, Statement<Keyword>)],
-) -> Result<Vec<Vec2<f32>>, Error>
-{
-    statements
-        .iter()
-        .filter_map(|(line_no, statement)| {
-            if statement.keyword != Keyword::Vt {
-                return None;
-            }
-
-            if statement.arguments.len() == 3 {
-                return Some(Err(Error::UnsupportedArgumentCount {
-                    keyword: statement.keyword.to_string(),
-                    arg_count: statement.arguments.len(),
-                    line_no: *line_no,
-                }));
-            }
-
-            if statement.arguments.len() > 3 {
-                return Some(Err(Error::InvalidArgumentCount {
-                    keyword: statement.keyword.to_string(),
-                    arg_count: statement.arguments.len(),
-                    line_no: *line_no,
-                }));
-            }
-
-            let u = try_option!(statement.get_float_arg(0, *line_no));
-            let v = try_option!(statement.get_float_arg(1, *line_no));
-
-            Some(Ok(Vec2 { x: u, y: v }))
-        })
-        .collect::<Result<Vec<_>, Error>>()
-}
-
-fn get_vertex_normals_from_statements(
-    statements: &[(usize, Statement<Keyword>)],
-) -> Result<Vec<Vec3<f32>>, Error>
-{
-    statements
-        .iter()
-        .filter_map(|(line_no, statement)| {
-            if statement.keyword != Keyword::Vn {
-                return None;
-            }
-
-            if statement.arguments.len() > 3 {
-                return Some(Err(Error::InvalidArgumentCount {
-                    keyword: statement.keyword.to_string(),
-                    arg_count: statement.arguments.len(),
-                    line_no: *line_no,
-                }));
-            }
-
-            let i = try_option!(statement.get_float_arg(0, *line_no));
-            let j = try_option!(statement.get_float_arg(1, *line_no));
-            let k = try_option!(statement.get_float_arg(2, *line_no));
-
-            Some(Ok(Vec3 { x: i, y: j, z: k }))
-        })
-        .collect::<Result<Vec<_>, Error>>()
-}
-
-fn get_material_specs_from_statements(
-    statements: &[(usize, Statement<Keyword>)],
-) -> Result<Vec<MaterialSpecifier>, Error>
-{
-    statements
-        .iter()
-        .filter_map(|(line_no, statement)| {
-            if statement.keyword != Keyword::Usemtl {
-                return None;
-            }
-
-            if statement.arguments.len() > 1 {
-                return Some(Err(Error::InvalidArgumentCount {
-                    keyword: statement.keyword.to_string(),
-                    arg_count: statement.arguments.len(),
-                    line_no: *line_no,
-                }));
-            }
-
-            let material_name = try_option!(statement.get_text_arg(0, *line_no));
-
-            Some(Ok(MaterialSpecifier {
-                material_name: material_name.to_string(),
-                line_no: *line_no,
-            }))
-        })
-        .collect::<Result<Vec<_>, Error>>()
-}
-
-fn get_faces_from_statements(
-    statements: &[(usize, Statement<Keyword>)],
-    material_specifiers: &[MaterialSpecifier],
-) -> Result<Vec<Face>, Error>
-{
-    statements
-        .iter()
-        .filter_map(|(line_no, statement)| {
-            if statement.keyword != Keyword::F {
-                return None;
-            }
-
-            if statement.arguments.len() > 3 {
-                return Some(Err(Error::UnsupportedArgumentCount {
-                    keyword: statement.keyword.to_string(),
-                    arg_count: statement.arguments.len(),
-                    line_no: *line_no,
-                }));
-            }
-
-            let vertex_a = try_option!(statement.get_triplet_arg(0, *line_no)).into();
-            let vertex_b = try_option!(statement.get_triplet_arg(1, *line_no)).into();
-            let vertex_c = try_option!(statement.get_triplet_arg(2, *line_no)).into();
-
-            let material_name =
-                find_material_specifier_for_line_no(material_specifiers, *line_no)
-                    .map(|material_specifier| material_specifier.material_name.clone());
-
-            Some(Ok(Face {
-                vertices: [vertex_a, vertex_b, vertex_c],
-                material_name,
-            }))
-        })
-        .collect::<Result<Vec<Face>, Error>>()
-}
-
-fn get_mtl_libs_from_statements(
-    statements: &[(usize, Statement<Keyword>)],
-) -> Result<Vec<Vec<PathBuf>>, Error>
-{
-    statements
-        .iter()
-        .filter_map(|(line_no, statement)| {
-            if statement.keyword != Keyword::Mtllib {
-                return None;
-            }
-
-            let mtl_lib_paths = try_option!(statement
-                .arguments
-                .iter()
-                .enumerate()
-                .map(|(index, value)| Ok(PathBuf::from(value.to_text(index, *line_no)?)))
-                .collect::<Result<Vec<_>, ParsingError>>());
-
-            Some(Ok(mtl_lib_paths))
-        })
-        .collect::<Result<Vec<_>, Error>>()
-}
-
 #[cfg(test)]
 mod tests
 {
@@ -602,17 +614,26 @@ mod tests
         assert_eq!(obj.faces.len(), 3);
 
         assert_eq!(
-            obj.faces[0].material_name.as_ref().expect("Expected Some"),
+            obj.faces[0]
+                .material_name
+                .as_deref()
+                .expect("Expected Some"),
             "dark-green"
         );
 
         assert_eq!(
-            obj.faces[1].material_name.as_ref().expect("Expected Some"),
+            obj.faces[1]
+                .material_name
+                .as_deref()
+                .expect("Expected Some"),
             "dark-green"
         );
 
         assert_eq!(
-            obj.faces[2].material_name.as_ref().expect("Expected Some"),
+            obj.faces[2]
+                .material_name
+                .as_deref()
+                .expect("Expected Some"),
             "light-pink"
         );
     }