Fix nondeterminism when types in dwarf have conflicting names

3 files changed, 62 insertions, 10 deletions

diff --git a/rust/Cargo.lock b/rust/Cargo.lock
index 694be754..e922d98e 100644
--- a/rust/Cargo.lock
+++ b/rust/Cargo.lock
@@ -340,6 +340,7 @@ dependencies = [
  "cpp_demangle",
  "dwarfreader",
  "gimli",
+ "indexmap",
  "iset",
  "log",
  "regex",
@@ -501,9 +502,9 @@ dependencies = [
 
 [[package]]
 name = "indexmap"
-version = "2.2.6"
+version = "2.5.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "168fb715dda47215e360912c096649d23d58bf392ac62f73919e831745e40f26"
+checksum = "68b900aa2f7301e21c36462b170ee99994de34dff39a4a6a528e80e7376d07e5"
 dependencies = [
  "equivalent",
  "hashbrown",
diff --git a/rust/examples/dwarf/dwarf_import/Cargo.toml b/rust/examples/dwarf/dwarf_import/Cargo.toml
index 838e435e..1736535f 100644
--- a/rust/examples/dwarf/dwarf_import/Cargo.toml
+++ b/rust/examples/dwarf/dwarf_import/Cargo.toml
@@ -15,3 +15,4 @@ log = "0.4.20"
 iset = "0.2.2"
 cpp_demangle = "0.4.3"
 regex = "1"
+indexmap = "2.5.0"
diff --git a/rust/examples/dwarf/dwarf_import/src/dwarfdebuginfo.rs b/rust/examples/dwarf/dwarf_import/src/dwarfdebuginfo.rs
index 140e3af5..d1208cc0 100644
--- a/rust/examples/dwarf/dwarf_import/src/dwarfdebuginfo.rs
+++ b/rust/examples/dwarf/dwarf_import/src/dwarfdebuginfo.rs
@@ -26,10 +26,11 @@ use binaryninja::{
 
 use gimli::{DebuggingInformationEntry, Dwarf, Unit};
 
+use indexmap::{map::Values, IndexMap};
 use log::{debug, error, warn};
 use std::{
     cmp::Ordering,
-    collections::{hash_map::Values, HashMap},
+    collections::HashMap,
     hash::Hash,
 };
 
@@ -198,7 +199,7 @@ pub(crate) struct DebugInfoBuilder {
     functions: Vec<FunctionInfoBuilder>,
     raw_function_name_indices: HashMap<String, usize>,
     full_function_name_indices: HashMap<String, usize>,
-    types: HashMap<TypeUID, DebugType>,
+    types: IndexMap<TypeUID, DebugType>,
     data_variables: HashMap<u64, (Option<String>, TypeUID)>,
     range_data_offsets: iset::IntervalMap<u64, i64>
 }
@@ -209,7 +210,7 @@ impl DebugInfoBuilder {
             functions: vec![],
             raw_function_name_indices: HashMap::new(),
             full_function_name_indices: HashMap::new(),
-            types: HashMap::new(),
+            types: IndexMap::new(),
             data_variables: HashMap::new(),
             range_data_offsets: iset::IntervalMap::new(),
         }
@@ -313,6 +314,7 @@ impl DebugInfoBuilder {
         &self.functions
     }
 
+    #[allow(dead_code)]
     pub(crate) fn types(&self) -> Values<'_, TypeUID, DebugType> {
         self.types.values()
     }
@@ -342,7 +344,7 @@ impl DebugInfoBuilder {
     }
 
     pub(crate) fn remove_type(&mut self, type_uid: TypeUID) {
-        self.types.remove(&type_uid);
+        self.types.swap_remove(&type_uid);
     }
 
     pub(crate) fn get_type(&self, type_uid: TypeUID) -> Option<&DebugType> {
@@ -440,11 +442,59 @@ impl DebugInfoBuilder {
     }
 
     fn commit_types(&self, debug_info: &mut DebugInfo) {
-        for debug_type in self.types() {
-            if debug_type.commit {
-                debug_info.add_type(debug_type.name.clone(), debug_type.t.as_ref(), &[]);
-                // TODO : Components
+        let mut type_uids_by_name: HashMap<String, TypeUID> = HashMap::new();
+
+        for (debug_type_uid, debug_type) in self.types.iter() {
+            if !debug_type.commit {
+                continue;
             }
+
+            let mut debug_type_name = debug_type.name.clone();
+
+            // Prevent storing two types with the same name and differing definitions
+            if let Some(stored_uid) = type_uids_by_name.get(&debug_type_name) {
+                let Some(stored_debug_type) = self.types.get(stored_uid) else {
+                    error!("Stored type name without storing a type! Please report this error. UID: {}, name: {}", stored_uid, debug_type_name);
+                    continue;
+                };
+
+                let mut skip_adding_type = false;
+                if stored_debug_type.t != debug_type.t {
+                    // We already stored a type with this name and it's a different type, deconflict the name and try again
+                    let mut i = 1;
+                    loop {
+                        if let Some(stored_uid) = type_uids_by_name.get(&debug_type_name) {
+                            if debug_type_uid == stored_uid {
+                                // We already have a type with this name but it's the same type so we're ok
+                                skip_adding_type = true;
+                                break;
+                            }
+                            if let Some(stored_debug_type) = self.types.get(stored_uid) {
+                                if stored_debug_type.t == debug_type.t {
+                                    // We already have a type with this name but it's the same type so we're ok
+                                    skip_adding_type = true;
+                                    break;
+                                }
+                            }
+
+                            debug_type_name = format!("{}_{}", debug_type.name, i);
+                            i += 1;
+                        }
+                        else {
+                            // We found a unique name
+                            break;
+                        }
+                    }
+                }
+
+                if skip_adding_type {
+                    continue;
+                }
+            };
+
+            type_uids_by_name.insert(debug_type_name.clone(), *debug_type_uid);
+            debug_info.add_type(debug_type_name, debug_type.t.as_ref(), &[]);
+            // TODO : Components
         }
     }