graphviz-sys 1.0.1

use bindgen::builder;
use bindgen::callbacks::ParseCallbacks;

use std::collections::HashSet;
use std::env;
use std::fs::{self};
use std::io::Write;
use std::path::{Path, PathBuf};
use std::process::Command;
use std::time::Instant;

// Verbose logging for build process
const VERBOSE_LOGGING: bool = true;

// Logging macro for build diagnostics
macro_rules! build_log {
    ($($arg:tt)*) => {
        if VERBOSE_LOGGING {
            println!("cargo:warning={}", format!($($arg)*));
        }
    };
}

#[derive(Debug)]
struct IgnoreMacros(HashSet<String>);

impl ParseCallbacks for IgnoreMacros {
    fn will_parse_macro(&self, name: &str) -> bindgen::callbacks::MacroParsingBehavior {
        if self.0.contains(name) {
            bindgen::callbacks::MacroParsingBehavior::Ignore
        } else {
            bindgen::callbacks::MacroParsingBehavior::Default
        }
    }
}

// Platform detection
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Platform {
    Windows,
    MacOS,
    Linux,
    FreeBSD,
    OpenBSD,
    NetBSD,
    Other,
}

impl Platform {
    fn detect() -> Self {
        match env::consts::OS {
            "windows" => Platform::Windows,
            "macos" => Platform::MacOS,
            "linux" => Platform::Linux,
            "freebsd" => Platform::FreeBSD,
            "openbsd" => Platform::OpenBSD,
            "netbsd" => Platform::NetBSD,
            _ => Platform::Other,
        }
    }
}

// Architecture detection
#[derive(Debug, Clone, Copy)]
enum Architecture {
    X86,
    X86_64,
    ARM,
    ARM64,
    Other,
}

impl Architecture {
    fn detect() -> Self {
        match env::consts::ARCH {
            "x86" => Architecture::X86,
            "x86_64" => Architecture::X86_64,
            "arm" => Architecture::ARM,
            "aarch64" => Architecture::ARM64,
            _ => Architecture::Other,
        }
    }
}

// Package manager types
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum PackageManager {
    Apt,       // Debian, Ubuntu
    Yum,       // RHEL, Fedora, CentOS
    Pacman,    // Arch
    Apk,       // Alpine
    Homebrew,  // macOS/Linux
    MacPorts,  // macOS
    Vcpkg,     // Windows
    Chocolatey,// Windows
    Scoop,     // Windows
    Conda,     // Cross-platform
    Nix,       // Cross-platform
    Guix,      // Cross-platform
    Pkg,       // FreeBSD
    Unknown,
}

// Structure to hold all discovery information
struct GraphvizInfo {
    libraries: Vec<String>,
    library_dirs: Vec<PathBuf>,
    include_dirs: Vec<PathBuf>,
    header_path: PathBuf,
    version: Option<String>,
    platform: Platform,
    architecture: Architecture,
    package_managers: Vec<PackageManager>,
    static_linking: bool,
    searched_paths: Vec<String>,
    discovery_time: std::time::Duration,
}

impl GraphvizInfo {
    fn new(libraries: Vec<&str>) -> Self {
        GraphvizInfo {
            libraries: libraries.iter().map(|s| s.to_string()).collect(),
            library_dirs: Vec::new(),
            include_dirs: Vec::new(),
            header_path: PathBuf::new(),
            version: None,
            platform: Platform::detect(),
            architecture: Architecture::detect(),
            package_managers: Vec::new(),
            static_linking: env::var("GRAPHVIZ_STATIC").is_ok(),
            searched_paths: Vec::new(),
            discovery_time: std::time::Duration::default(),
        }
    }
    
    fn add_search_path(&mut self, path: &Path) {
        self.searched_paths.push(path.display().to_string());
    }
    
    fn add_lib_dir(&mut self, path: PathBuf) {
        if !self.library_dirs.contains(&path) {
            self.library_dirs.push(path);
        }
    }
    
    fn add_include_dir(&mut self, path: PathBuf) {
        if !self.include_dirs.contains(&path) {
            self.include_dirs.push(path);
        }
    }
    
    fn print_summary(&self) {
        build_log!("=== Graphviz Discovery Summary ===");
        build_log!("Platform: {:?}", self.platform);
        build_log!("Architecture: {:?}", self.architecture);
        build_log!("Package Managers: {:?}", self.package_managers);
        build_log!("Version: {:?}", self.version);
        build_log!("Static Linking: {}", self.static_linking);
        build_log!("Discovery Time: {:?}", self.discovery_time);
        build_log!("Library Dirs: {:?}", self.library_dirs);
        build_log!("Include Dirs: {:?}", self.include_dirs);
        build_log!("Header Path: {:?}", self.header_path);
        build_log!("Searched Paths: {:?}", self.searched_paths);
    }
}

fn main() {
    let start_time = Instant::now();
    
    // Make cargo rerun this script if relevant environment variables change
    println!("cargo:rerun-if-changed=wrapper.h");
    println!("cargo:rerun-if-env-changed=GRAPHVIZ_DIR");
    println!("cargo:rerun-if-env-changed=GRAPHVIZ_VERSION");
    println!("cargo:rerun-if-env-changed=GRAPHVIZ_STATIC");
    println!("cargo:rerun-if-env-changed=GRAPHVIZ_INCLUDE_DIR");
    println!("cargo:rerun-if-env-changed=GRAPHVIZ_LIB_DIR");
    println!("cargo:rerun-if-env-changed=PKG_CONFIG_PATH");
    println!("cargo:rerun-if-env-changed=VERBOSE_BUILD");
    
    // Libraries to link against - core Graphviz libraries
    let libraries = vec!["gvc", "cgraph", "pathplan", "cdt"];
    
    // Initialize discovery info
    let mut info = GraphvizInfo::new(libraries);
    
    // Detect installed package managers
    detect_package_managers(&mut info);
    
    // Detect Graphviz version
    detect_graphviz_version(&mut info);
    
    // Try to locate Graphviz
    if !discover_graphviz(&mut info) {
        // Suggest installation based on platform and detected package managers
        let install_cmd = suggest_installation(&info);
        panic!(
            "Could not find Graphviz libraries or headers.\n\
             Searched paths: {:?}\n\
             Installation suggestion: {}",
            info.searched_paths, install_cmd
        );
    }
    
    // Record discovery time
    info.discovery_time = start_time.elapsed();
    
    // Print summary of what we found
    info.print_summary();
    
    // Add library search paths to cargo
    for dir in &info.library_dirs {
        println!("cargo:rustc-link-search={}", dir.display());
    }
    
    // Link against required libraries
    for lib in &info.libraries {
        if info.static_linking {
            // Try to find static libraries
            let static_lib_exists = info.library_dirs.iter().any(|dir| {
                dir.join(format!("lib{}.a", lib)).exists()
            });
            
            if static_lib_exists {
                println!("cargo:rustc-link-lib=static={}", lib);
            } else {
                println!("cargo:rustc-link-lib={}", lib);
                build_log!("Static library for {} not found, using dynamic linking", lib);
            }
        } else {
            println!("cargo:rustc-link-lib={}", lib);
        }
    }
    
    // Define common macros to ignore
    let ignored_macros = IgnoreMacros(
        vec![
            "FP_INFINITE".into(),
            "FP_NAN".into(),
            "FP_NORMAL".into(),
            "FP_SUBNORMAL".into(),
            "FP_ZERO".into(),
            "IPPORT_RESERVED".into(),
        ]
        .into_iter()
        .collect(),
    );

    // Generate bindings with explicit include paths
    build_log!("Using header at: {}", info.header_path.display());
    let mut builder = builder()
        .header(info.header_path.to_str().unwrap())
        .parse_callbacks(Box::new(ignored_macros))
        .allowlist_file(".*/graphviz/.*")
        .opaque_type("FILE");
    
    // Add all include paths to the builder
    for path in &info.include_dirs {
        builder = builder.clang_arg(format!("-I{}", path.display()));
    }
    
    // Generate the bindings
    let bindings = builder
        .generate()
        .expect("Unable to generate bindings");

    // Write the bindings to the output directory
    let out_path = PathBuf::from(env::var("OUT_DIR").unwrap());
    bindings
        .write_to_file(out_path.join("bindings.rs"))
        .expect("Couldn't write bindings!");
        
    build_log!("Build completed successfully in {:?}", start_time.elapsed());
}

/// Try to discover Graphviz libraries and headers through all available methods
fn discover_graphviz(info: &mut GraphvizInfo) -> bool {
    build_log!("Starting Graphviz discovery...");
    
    // First check explicit environment variables
    if discover_from_environment(info) {
        build_log!("Found Graphviz using environment variables");
        return true;
    }
    
    // Try pkg-config next (most reliable cross-platform method)
    if discover_from_pkg_config(info) {
        build_log!("Found Graphviz using pkg-config");
        return true;
    }
    
    // Try platform-specific methods
    if discover_from_platform_specific(info) {
        build_log!("Found Graphviz using platform-specific detection");
        return true;
    }
    
    // Try common locations as fallback
    if discover_from_common_locations(info) {
        build_log!("Found Graphviz in common locations");
        return true;
    }
    
    // Try recursive search as last resort
    if discover_from_recursive_search(info) {
        build_log!("Found Graphviz through recursive search");
        return true;
    }
    
    false
}

/// Detect available package managers on the system
fn detect_package_managers(info: &mut GraphvizInfo) {
    // Clear any existing entries
    info.package_managers.clear();
    
    match info.platform {
        Platform::Windows => {
            // Check for vcpkg
            if Command::new("vcpkg").arg("--version").output().is_ok() {
                info.package_managers.push(PackageManager::Vcpkg);
            }
            
            // Check for Chocolatey
            if Path::new("C:\\ProgramData\\chocolatey\\bin\\choco.exe").exists() {
                info.package_managers.push(PackageManager::Chocolatey);
            }
            
            // Check for Scoop
            if let Ok(user_profile) = env::var("USERPROFILE") {
                if Path::new(&format!("{}\\scoop", user_profile)).exists() {
                    info.package_managers.push(PackageManager::Scoop);
                }
            }
        },
        Platform::MacOS => {
            // Check for Homebrew
            if Path::new("/usr/local/bin/brew").exists() || Path::new("/opt/homebrew/bin/brew").exists() {
                info.package_managers.push(PackageManager::Homebrew);
            }
            
            // Check for MacPorts
            if Path::new("/opt/local/bin/port").exists() {
                info.package_managers.push(PackageManager::MacPorts);
            }
        },
        Platform::Linux => {
            // Check for apt (Debian/Ubuntu)
            if Command::new("apt").arg("--version").output().is_ok() {
                info.package_managers.push(PackageManager::Apt);
            }
            
            // Check for yum/dnf (RHEL/Fedora)
            if Command::new("yum").arg("--version").output().is_ok() || 
               Command::new("dnf").arg("--version").output().is_ok() {
                info.package_managers.push(PackageManager::Yum);
            }
            
            // Check for pacman (Arch)
            if Command::new("pacman").arg("--version").output().is_ok() {
                info.package_managers.push(PackageManager::Pacman);
            }
            
            // Check for apk (Alpine)
            if Command::new("apk").arg("--version").output().is_ok() {
                info.package_managers.push(PackageManager::Apk);
            }
            
            // Check for Homebrew on Linux
            if Path::new("/home/linuxbrew/.linuxbrew/bin/brew").exists() {
                info.package_managers.push(PackageManager::Homebrew);
            }
        },
        Platform::FreeBSD | Platform::OpenBSD | Platform::NetBSD => {
            if Command::new("pkg").arg("--version").output().is_ok() {
                info.package_managers.push(PackageManager::Pkg);
            }
        },
        _ => {}
    }
    
    // Cross-platform package managers
    
    // Check for Conda
    if env::var("CONDA_PREFIX").is_ok() || 
       Command::new("conda").arg("--version").output().is_ok() {
        info.package_managers.push(PackageManager::Conda);
    }
    
    // Check for Nix
    if Path::new("/nix").exists() || env::var("NIX_PATH").is_ok() {
        info.package_managers.push(PackageManager::Nix);
    }
    
    // Check for Guix
    if Command::new("guix").arg("--version").output().is_ok() {
        info.package_managers.push(PackageManager::Guix);
    }
    
    if info.package_managers.is_empty() {
        info.package_managers.push(PackageManager::Unknown);
    }
    
    build_log!("Detected package managers: {:?}", info.package_managers);
}

/// Detect Graphviz version if installed
fn detect_graphviz_version(info: &mut GraphvizInfo) {
    // Try using dot -V first (most common method)
    if let Ok(output) = Command::new("dot").arg("-V").output() {
        if output.status.success() {
            // Graphviz may output to stderr or stdout depending on version
            let version_str = if !output.stderr.is_empty() {
                String::from_utf8_lossy(&output.stderr)
            } else {
                String::from_utf8_lossy(&output.stdout)
            };
            
            let version = version_str.trim().to_string();
            build_log!("Detected Graphviz version: {}", version);
            info.version = Some(version);
            return;
        }
    }
    
    // Try pkg-config as fallback
    if let Ok(output) = Command::new("pkg-config")
        .args(&["--modversion", "libgvc"])
        .output() 
    {
        if output.status.success() {
            let version = String::from_utf8_lossy(&output.stdout).trim().to_string();
            build_log!("Detected Graphviz version via pkg-config: {}", version);
            info.version = Some(version);
            return;
        }
    }
    
    build_log!("Could not detect Graphviz version");
}

/// Discover Graphviz from environment variables
fn discover_from_environment(info: &mut GraphvizInfo) -> bool {
    let mut found_libs = false;
    let mut found_headers = false;
    
    // Check GRAPHVIZ_DIR for complete installation
    if let Ok(graphviz_dir) = env::var("GRAPHVIZ_DIR") {
        let path = PathBuf::from(graphviz_dir);
        info.add_search_path(&path);
        
        // Check for libraries
        let lib_dirs = [
            path.join("lib"),
            path.join("lib64"),
        ];
        
        for lib_dir in &lib_dirs {
            if lib_dir.exists() && has_libraries(lib_dir, &info.libraries) {
                info.add_lib_dir(lib_dir.clone());
                found_libs = true;
            }
        }
        
        // Check for headers
        let include_dir = path.join("include");
        if include_dir.exists() {
            info.add_include_dir(include_dir.clone());
            
            let graphviz_include = include_dir.join("graphviz");
            let gvc_header = graphviz_include.join("gvc.h");
            
            if gvc_header.exists() {
                info.header_path = create_wrapper_header("graphviz/gvc.h");
                found_headers = true;
            }
        }
    }
    
    // Check separate GRAPHVIZ_LIB_DIR and GRAPHVIZ_INCLUDE_DIR
    if let Ok(lib_dir) = env::var("GRAPHVIZ_LIB_DIR") {
        let path = PathBuf::from(lib_dir);
        info.add_search_path(&path);
        
        if path.exists() && has_libraries(&path, &info.libraries) {
            info.add_lib_dir(path);
            found_libs = true;
        }
    }
    
    if let Ok(include_dir) = env::var("GRAPHVIZ_INCLUDE_DIR") {
        let path = PathBuf::from(include_dir);
        info.add_search_path(&path);
        
        if path.exists() {
            info.add_include_dir(path.clone());
            
            // Check for direct header
            let direct_header = path.join("gvc.h");
            if direct_header.exists() {
                info.header_path = create_wrapper_header("gvc.h");
                found_headers = true;
            }
            
            // Check for graphviz subdirectory
            let graphviz_header = path.join("graphviz/gvc.h");
            if graphviz_header.exists() {
                info.header_path = create_wrapper_header("graphviz/gvc.h");
                found_headers = true;
            }
        }
    }
    
    found_libs && found_headers
}

/// Discover Graphviz using pkg-config
fn discover_from_pkg_config(info: &mut GraphvizInfo) -> bool {
    // Check if pkg-config is available
    if Command::new("pkg-config").arg("--version").output().is_err() {
        build_log!("pkg-config not available");
        return false;
    }
    
    let mut lib_found = false;
    let mut paths_to_add = Vec::new(); // Collect paths here first
    let mut headers_to_check = Vec::new();
    
    // Try each library with pkg-config
    for lib in &info.libraries {
        let pkg_name = format!("lib{}", lib);
        
        // Get library paths
        match Command::new("pkg-config")
            .args(&["--libs-only-L", &pkg_name])
            .output()
        {
            Ok(output) => {
                if output.status.success() {
                    let paths = String::from_utf8_lossy(&output.stdout);
                    for path in paths.split_whitespace() {
                        if path.starts_with("-L") {
                            let path_str = path.trim_start_matches("-L");
                            let path = PathBuf::from(path_str);
                            // Store for later
                            paths_to_add.push((path, true)); // (path, is_lib_dir)
                            lib_found = true;
                        }
                    }
                }
            }
            Err(_) => {
                build_log!("pkg-config failed for {}", pkg_name);
                continue;
            }
        }
        
        // Get include paths
        match Command::new("pkg-config")
            .args(&["--cflags-only-I", &pkg_name])
            .output()
        {
            Ok(output) => {
                if output.status.success() {
                    let paths = String::from_utf8_lossy(&output.stdout);
                    for path in paths.split_whitespace() {
                        if path.starts_with("-I") {
                            let path_str = path.trim_start_matches("-I");
                            let path = PathBuf::from(path_str);
                            // Store for later
                            paths_to_add.push((path.clone(), false)); // (path, is_lib_dir)
                            headers_to_check.push(path);
                        }
                    }
                }
            }
            Err(_) => {} // Ignore errors for include paths
        }
    }
    
    // Now process all the paths after collecting them
    for (path, is_lib_dir) in paths_to_add {
        if is_lib_dir {
            info.add_lib_dir(path.clone());
        } else {
            info.add_include_dir(path.clone());
        }
        info.add_search_path(&path);
    }
    
    // Check for headers in collected paths
    if info.header_path.as_os_str().is_empty() {
        for path in headers_to_check {
            let gvc_header = path.join("graphviz/gvc.h");
            if gvc_header.exists() {
                info.header_path = create_wrapper_header("graphviz/gvc.h");
                break;
            }
        }
    }
    
    // If we found libraries but not the header, try harder to find the header
    if lib_found && info.header_path.as_os_str().is_empty() {
        let include_dirs = info.include_dirs.clone(); // Clone to avoid borrowing issues
        for include_dir in include_dirs {
            // Try with graphviz/ prefix
            let gvc_header = include_dir.join("graphviz/gvc.h");
            if gvc_header.exists() {
                info.header_path = create_wrapper_header("graphviz/gvc.h");
                break;
            }
            
            // Try without graphviz/ prefix
            let direct_header = include_dir.join("gvc.h");
            if direct_header.exists() {
                info.header_path = create_wrapper_header("gvc.h");
                break;
            }
        }
    }
    
    // Create a wrapper file if we found headers
    if !info.header_path.as_os_str().is_empty() {
        return true;
    }
    
    if lib_found {
        // If we found libraries but not headers, create a default wrapper
        // and rely on the include paths we collected
        info.header_path = create_wrapper_header("graphviz/gvc.h");
        return true;
    }
    
    false
}

/// Discover Graphviz using platform-specific methods
fn discover_from_platform_specific(info: &mut GraphvizInfo) -> bool {
    match info.platform {
        Platform::Windows => discover_windows_specific(info),
        Platform::MacOS => discover_macos_specific(info),
        Platform::Linux => discover_linux_specific(info),
        Platform::FreeBSD | Platform::OpenBSD | Platform::NetBSD => discover_bsd_specific(info),
        _ => false,
    }
}

/// Windows-specific discovery methods
fn discover_windows_specific(info: &mut GraphvizInfo) -> bool {
    let mut found = false;
    
    // Check Program Files locations
    let program_files_paths = [
        "C:\\Program Files\\Graphviz",
        "C:\\Program Files (x86)\\Graphviz",
        "C:\\Graphviz",
    ];
    
    for &base_path in &program_files_paths {
        let base = PathBuf::from(base_path);
        info.add_search_path(&base);
        
        if !base.exists() {
            continue;
        }
        
        // Check lib directory
        let lib_dir = base.join("lib");
        if lib_dir.exists() && has_libraries(&lib_dir, &info.libraries) {
            info.add_lib_dir(lib_dir);
            found = true;
        }
        
        // Check bin directory for DLLs
        let bin_dir = base.join("bin");
        if bin_dir.exists() && has_libraries(&bin_dir, &info.libraries) {
            info.add_lib_dir(bin_dir);
            found = true;
        }
        
        // Check include directory
        let include_dir = base.join("include");
        if include_dir.exists() {
            info.add_include_dir(include_dir.clone());
            
            let graphviz_header = include_dir.join("graphviz/gvc.h");
            if graphviz_header.exists() {
                info.header_path = create_wrapper_header("graphviz/gvc.h");
            }
        }
    }
    
    // Check vcpkg installed packages
    if info.package_managers.contains(&PackageManager::Vcpkg) {
        if let Ok(vcpkg_root) = env::var("VCPKG_ROOT") {
            let vcpkg_path = PathBuf::from(vcpkg_root);
            
            let triplets = [
                "x64-windows",
                "x86-windows",
                "x64-windows-static",
                "x86-windows-static",
            ];
            
            for &triplet in &triplets {
                let install_dir = vcpkg_path.join("installed").join(triplet);
                if !install_dir.exists() {
                    continue;
                }
                
                info.add_search_path(&install_dir);
                
                let lib_dir = install_dir.join("lib");
                if lib_dir.exists() && has_libraries(&lib_dir, &info.libraries) {
                    info.add_lib_dir(lib_dir);
                    found = true;
                }
                
                let include_dir = install_dir.join("include");
                if include_dir.exists() {
                    info.add_include_dir(include_dir.clone());
                    
                    let graphviz_header = include_dir.join("graphviz/gvc.h");
                    if graphviz_header.exists() {
                        info.header_path = create_wrapper_header("graphviz/gvc.h");
                    }
                }
            }
        }
    }
    
    found && !info.header_path.as_os_str().is_empty()
}

/// macOS-specific discovery methods
fn discover_macos_specific(info: &mut GraphvizInfo) -> bool {
    let mut found = false;
    
    // Check Homebrew locations
    if info.package_managers.contains(&PackageManager::Homebrew) {
        let homebrew_paths = [
            // Intel Mac
            PathBuf::from("/usr/local/opt/graphviz"),
            // Apple Silicon
            PathBuf::from("/opt/homebrew/opt/graphviz"),
        ];
        
        for path in &homebrew_paths {
            info.add_search_path(path);
            
            if !path.exists() {
                continue;
            }
            
            let lib_dir = path.join("lib");
            if lib_dir.exists() && has_libraries(&lib_dir, &info.libraries) {
                info.add_lib_dir(lib_dir);
                found = true;
            }
            
            let include_dir = path.join("include");
            if include_dir.exists() {
                info.add_include_dir(include_dir.clone());
                
                let graphviz_header = include_dir.join("graphviz/gvc.h");
                if graphviz_header.exists() {
                    info.header_path = create_wrapper_header("graphviz/gvc.h");
                }
            }
        }
        
        // Check Homebrew Cellar paths
        let cellar_base_paths = [
            PathBuf::from("/usr/local/Cellar/graphviz"),
            PathBuf::from("/opt/homebrew/Cellar/graphviz"),
        ];
        
        for cellar_base in &cellar_base_paths {
            info.add_search_path(cellar_base);
            
            if !cellar_base.exists() {
                continue;
            }
            
            // Get all version directories and sort them
            if let Ok(entries) = fs::read_dir(cellar_base) {
                let mut version_dirs: Vec<PathBuf> = entries
                    .filter_map(Result::ok)
                    .filter(|e| e.path().is_dir())
                    .map(|e| e.path())
                    .collect();
                
                // Sort by version (newest first)
                version_dirs.sort_by(|a, b| {
                    b.file_name().unwrap_or_default().cmp(a.file_name().unwrap_or_default())
                });
                
                // Check if user specified a preferred version
                let preferred_version = env::var("GRAPHVIZ_VERSION").ok();
                
                for dir in version_dirs {
                    let version = dir.file_name().unwrap().to_string_lossy();
                    if let Some(ref pref) = preferred_version {
                        if !version.contains(pref) {
                            continue;
                        }
                    }
                    
                    let lib_dir = dir.join("lib");
                    if lib_dir.exists() && has_libraries(&lib_dir, &info.libraries) {
                        info.add_lib_dir(lib_dir);
                        found = true;
                    }
                    
                    let include_dir = dir.join("include");
                    if include_dir.exists() {
                        info.add_include_dir(include_dir.clone());
                        
                        let graphviz_header = include_dir.join("graphviz/gvc.h");
                        if graphviz_header.exists() {
                            info.header_path = create_wrapper_header("graphviz/gvc.h");
                        }
                    }
                    
                    if preferred_version.is_some() && found && !info.header_path.as_os_str().is_empty() {
                        break; // Stop if we found everything for the preferred version
                    }
                }
            }
        }
    }
    
    // Check MacPorts locations
    if info.package_managers.contains(&PackageManager::MacPorts) {
        let macports_prefix = PathBuf::from("/opt/local");
        info.add_search_path(&macports_prefix);
        
        let lib_dir = macports_prefix.join("lib");
        if lib_dir.exists() && has_libraries(&lib_dir, &info.libraries) {
            info.add_lib_dir(lib_dir);
            found = true;
        }
        
        let include_dir = macports_prefix.join("include");
        if include_dir.exists() {
            info.add_include_dir(include_dir.clone());
            
            let graphviz_header = include_dir.join("graphviz/gvc.h");
            if graphviz_header.exists() {
                info.header_path = create_wrapper_header("graphviz/gvc.h");
            }
        }
    }
    
    found && !info.header_path.as_os_str().is_empty()
}

/// Linux-specific discovery methods
fn discover_linux_specific(info: &mut GraphvizInfo) -> bool {
    let mut found = false;
    
    // Check distribution-specific paths
    let lib_paths = match info.architecture {
        Architecture::X86_64 => vec![
            PathBuf::from("/usr/lib/x86_64-linux-gnu"),
            PathBuf::from("/usr/lib64"),
        ],
        Architecture::X86 => vec![
            PathBuf::from("/usr/lib/i386-linux-gnu"),
            PathBuf::from("/usr/lib"),
        ],
        Architecture::ARM => vec![
            PathBuf::from("/usr/lib/arm-linux-gnueabihf"),
            PathBuf::from("/usr/lib"),
        ],
        Architecture::ARM64 => vec![
            PathBuf::from("/usr/lib/aarch64-linux-gnu"),
            PathBuf::from("/usr/lib64"),
        ],
        _ => vec![
            PathBuf::from("/usr/lib"),
            PathBuf::from("/usr/lib64"),
        ],
    };
    
    for lib_path in &lib_paths {
        info.add_search_path(lib_path);
        
        if lib_path.exists() && has_libraries(lib_path, &info.libraries) {
            info.add_lib_dir(lib_path.clone());
            found = true;
        }
    }
    
    // Check common include paths
    let include_paths = [
        PathBuf::from("/usr/include/graphviz"),
        PathBuf::from("/usr/local/include/graphviz"),
    ];
    
    for include_path in &include_paths {
        info.add_search_path(include_path);
        
        if include_path.exists() {
            info.add_include_dir(include_path.parent().unwrap().to_path_buf());
            
            let gvc_header = include_path.join("gvc.h");
            if gvc_header.exists() {
                info.header_path = create_wrapper_header("graphviz/gvc.h");
                break;
            }
        }
    }
    
    // Check for Homebrew on Linux
    if info.package_managers.contains(&PackageManager::Homebrew) {
        let homebrew_prefix = PathBuf::from("/home/linuxbrew/.linuxbrew");
        info.add_search_path(&homebrew_prefix);
        
        let lib_dir = homebrew_prefix.join("lib");
        if lib_dir.exists() && has_libraries(&lib_dir, &info.libraries) {
            info.add_lib_dir(lib_dir);
            found = true;
        }
        
        let include_dir = homebrew_prefix.join("include");
        if include_dir.exists() {
            info.add_include_dir(include_dir.clone());
            
            let graphviz_header = include_dir.join("graphviz/gvc.h");
            if graphviz_header.exists() {
                info.header_path = create_wrapper_header("graphviz/gvc.h");
            }
        }
    }
    
    found && !info.header_path.as_os_str().is_empty()
}

/// BSD-specific discovery methods
fn discover_bsd_specific(info: &mut GraphvizInfo) -> bool {
    let mut found = false;
    
    // Check common BSD paths
    let lib_paths = [
        PathBuf::from("/usr/local/lib"),
        PathBuf::from("/usr/lib"),
    ];
    
    for lib_path in &lib_paths {
        info.add_search_path(lib_path);
        
        if lib_path.exists() && has_libraries(lib_path, &info.libraries) {
            info.add_lib_dir(lib_path.clone());
            found = true;
        }
    }
    
    // Check common include paths
    let include_paths = [
        PathBuf::from("/usr/local/include/graphviz"),
        PathBuf::from("/usr/include/graphviz"),
    ];
    
    for include_path in &include_paths {
        info.add_search_path(include_path);
        
        if include_path.exists() {
            info.add_include_dir(include_path.parent().unwrap().to_path_buf());
            
            let gvc_header = include_path.join("gvc.h");
            if gvc_header.exists() {
                info.header_path = create_wrapper_header("graphviz/gvc.h");
                break;
            }
        }
    }
    
    found && !info.header_path.as_os_str().is_empty()
}

/// Discover from common locations across different platforms
fn discover_from_common_locations(info: &mut GraphvizInfo) -> bool {
    let mut found_libs = false;
    
    // These paths are common across multiple platforms
    let common_lib_paths = [
        PathBuf::from("/usr/lib"),
        PathBuf::from("/usr/local/lib"),
        PathBuf::from("/opt/local/lib"),
    ];
    
    for lib_path in &common_lib_paths {
        info.add_search_path(lib_path);
        
        if lib_path.exists() && has_libraries(lib_path, &info.libraries) {
            info.add_lib_dir(lib_path.clone());
            found_libs = true;
        }
    }
    
    // Common include paths
    let common_include_paths = [
        PathBuf::from("/usr/include"),
        PathBuf::from("/usr/local/include"),
        PathBuf::from("/opt/local/include"),
    ];
    
    for include_path in &common_include_paths {
        info.add_search_path(include_path);
        
        if include_path.exists() {
            info.add_include_dir(include_path.clone());
            
            // Check for graphviz subdirectory
            let graphviz_path = include_path.join("graphviz");
            if graphviz_path.exists() {
                let gvc_header = graphviz_path.join("gvc.h");
                if gvc_header.exists() {
                    info.header_path = create_wrapper_header("graphviz/gvc.h");
                }
            }
        }
    }
    
    // Check LD_LIBRARY_PATH (Unix) or PATH (Windows)
    let lib_path_var = if info.platform == Platform::Windows { "PATH" } else { "LD_LIBRARY_PATH" };
    if let Ok(lib_path) = env::var(lib_path_var) {
        let separator = if info.platform == Platform::Windows { ";" } else { ":" };
        for dir in lib_path.split(separator) {
            let path = PathBuf::from(dir);
            info.add_search_path(&path);
            
            if path.exists() && has_libraries(&path, &info.libraries) {
                info.add_lib_dir(path);
                found_libs = true;
            }
        }
    }
    
    // If we found libraries but no header, try to derive include paths from lib paths
    if found_libs && info.header_path.as_os_str().is_empty() {
        let lib_dirs = info.library_dirs.clone(); // Clone to avoid borrowing conflict
        let mut include_paths = Vec::new();
        let mut header_path = None;
        
        for lib_dir in &lib_dirs {
            let lib_path = lib_dir.to_str().unwrap_or("");
            let include_path = if lib_path.ends_with("/lib") || lib_path.ends_with("\\lib") {
                PathBuf::from(lib_path.trim_end_matches("/lib").trim_end_matches("\\lib")).join("include")
            } else if lib_path.ends_with("/lib64") || lib_path.ends_with("\\lib64") {
                PathBuf::from(lib_path.trim_end_matches("/lib64").trim_end_matches("\\lib64")).join("include")
            } else {
                continue;
            };
            
            if include_path.exists() {
                include_paths.push(include_path.clone());
                
                // Check for graphviz subdirectory
                let graphviz_path = include_path.join("graphviz");
                if graphviz_path.exists() {
                    let gvc_header = graphviz_path.join("gvc.h");
                    if gvc_header.exists() {
                        header_path = Some("graphviz/gvc.h");
                        break;
                    }
                }
            }
        }
        
        // Now apply the collected changes
        for path in include_paths {
            info.add_include_dir(path);
        }
        
        if let Some(header) = header_path {
            info.header_path = create_wrapper_header(header);
        }
    }
    
    found_libs && !info.header_path.as_os_str().is_empty()
}

/// Last resort: recursive search for libraries and headers
fn discover_from_recursive_search(info: &mut GraphvizInfo) -> bool {
    let mut found_libs = false;
    
    // Base directories to start recursive search
    let root_dirs = match info.platform {
        Platform::Windows => vec![
            PathBuf::from("C:\\"),
            PathBuf::from("C:\\Program Files"),
            PathBuf::from("C:\\Program Files (x86)"),
        ],
        Platform::MacOS => vec![
            PathBuf::from("/usr"),
            PathBuf::from("/usr/local"),
            PathBuf::from("/opt"),
        ],
        _ => vec![
            PathBuf::from("/usr"),
            PathBuf::from("/usr/local"),
            PathBuf::from("/opt"),
        ],
    };
    
    for root in &root_dirs {
        // Look for libraries first
        if let Some(lib_paths) = find_libraries_recursively(root, &info.libraries, 3) {
            for lib_path in lib_paths {
                info.add_lib_dir(lib_path);
                found_libs = true;
            }
        }
    }
    
    // If we found libraries, search for headers
    if found_libs {
        for root in &root_dirs {
            if let Some(header_path) = find_header_recursively(root, "gvc.h", 4) {
                let parent_path = header_path.parent().unwrap();
                let is_in_graphviz_dir = parent_path.file_name().map_or(false, |name| name == "graphviz");
                
                if is_in_graphviz_dir {
                    // If found in a graphviz/ subdirectory
                    info.add_include_dir(parent_path.parent().unwrap().to_path_buf());
                    info.header_path = create_wrapper_header("graphviz/gvc.h");
                } else {
                    // If found directly
                    info.add_include_dir(parent_path.to_path_buf());
                    info.header_path = create_wrapper_header("gvc.h");
                }
                break;
            }
        }
    }
    
    // If we still can't find the header, create a default wrapper as last resort
    if found_libs && info.header_path.as_os_str().is_empty() {
        build_log!("Creating default wrapper as last resort");
        info.header_path = create_wrapper_header("graphviz/gvc.h");
    }
    
    found_libs && !info.header_path.as_os_str().is_empty()
}

/// Suggest installation commands based on platform and detected package managers
fn suggest_installation(info: &GraphvizInfo) -> String {
    match info.platform {
        Platform::Windows => {
            if info.package_managers.contains(&PackageManager::Vcpkg) {
                "vcpkg install graphviz".to_string()
            } else if info.package_managers.contains(&PackageManager::Chocolatey) {
                "choco install graphviz".to_string()
            } else if info.package_managers.contains(&PackageManager::Scoop) {
                "scoop install graphviz".to_string()
            } else {
                "Install Graphviz from https://graphviz.org/download/".to_string()
            }
        },
        Platform::MacOS => {
            if info.package_managers.contains(&PackageManager::Homebrew) {
                "brew install graphviz".to_string()
            } else if info.package_managers.contains(&PackageManager::MacPorts) {
                "sudo port install graphviz".to_string()
            } else {
                "Install Graphviz from https://graphviz.org/download/ or using Homebrew or MacPorts".to_string()
            }
        },
        Platform::Linux => {
            if info.package_managers.contains(&PackageManager::Apt) {
                "sudo apt-get install libgraphviz-dev".to_string()
            } else if info.package_managers.contains(&PackageManager::Yum) {
                "sudo yum install graphviz-devel".to_string()
            } else if info.package_managers.contains(&PackageManager::Pacman) {
                "sudo pacman -S graphviz".to_string()
            } else if info.package_managers.contains(&PackageManager::Apk) {
                "sudo apk add graphviz-dev".to_string()
            } else if info.package_managers.contains(&PackageManager::Homebrew) {
                "brew install graphviz".to_string()
            } else {
                "Install graphviz development package using your distribution's package manager".to_string()
            }
        },
        Platform::FreeBSD => "pkg install graphviz".to_string(),
        Platform::OpenBSD => "pkg_add graphviz".to_string(),
        Platform::NetBSD => "pkgin install graphviz".to_string(),
        _ => "Install Graphviz from https://graphviz.org/download/".to_string(),
    }
}

/// Check if a directory contains the required libraries
fn has_libraries(dir: &Path, libraries: &[String]) -> bool {
    let lib_ext = get_lib_extension(Platform::detect());
    let lib_prefixes = if Platform::detect() == Platform::Windows {
        vec!["", "lib"]  // Windows might have both lib*.dll and *.dll
    } else {
        vec!["lib"]      // Unix systems typically use lib*.so
    };
    
    for lib in libraries {
        let mut found = false;
        
        for prefix in &lib_prefixes {
            let lib_filename = format!("{}{}.{}", prefix, lib, lib_ext);
            let lib_path = dir.join(&lib_filename);
            
            if lib_path.exists() {
                found = true;
                break;
            }
            
            // Check for static libraries
            let static_lib_filename = format!("{}{}.a", prefix, lib);
            let static_lib_path = dir.join(&static_lib_filename);
            
            if static_lib_path.exists() {
                found = true;
                break;
            }
            
            // On Windows, also check .lib files
            if Platform::detect() == Platform::Windows {
                let windows_lib_filename = format!("{}{}.lib", prefix, lib);
                let windows_lib_path = dir.join(&windows_lib_filename);
                
                if windows_lib_path.exists() {
                    found = true;
                    break;
                }
            }
        }
        
        if !found {
            return false;
        }
    }
    
    true
}

/// Find libraries recursively up to a maximum depth
fn find_libraries_recursively(start_dir: &Path, libraries: &[String], max_depth: usize) -> Option<Vec<PathBuf>> {
    let mut found_paths = Vec::new();
    let mut dirs_to_search = vec![(start_dir.to_path_buf(), 0)];
    
    // Skip these directories for better performance
    let skip_dirs = [
        "proc", "sys", "dev", "tmp", "var", "run", "media", "mnt",
        "cdrom", "boot", "home", "bin", "sbin"
    ];
    
    while let Some((dir, depth)) = dirs_to_search.pop() {
        if depth > max_depth || !dir.is_dir() {
            continue;
        }
        
        // Check if this directory has relevant libraries
        if has_libraries(&dir, libraries) {
            found_paths.push(dir.clone());
        }
        
        // Avoid searching too deeply in filesystem
        if depth == max_depth {
            continue;
        }
        
        // Read directory entries
        if let Ok(entries) = fs::read_dir(&dir) {
            for entry in entries.filter_map(Result::ok) {
                let path = entry.path();
                
                if path.is_dir() {
                    let dir_name = path.file_name()
                        .and_then(|n| n.to_str())
                        .unwrap_or("");
                    
                    // Skip unlikely directories
                    if skip_dirs.contains(&dir_name) || dir_name.starts_with(".") {
                        continue;
                    }
                    
                    // If we're at depth 0, only search in likely directories
                    if depth == 0 {
                        let likely_dirs = ["lib", "lib64", "usr", "opt", "program files", "graphviz"];
                        let lower_name = dir_name.to_lowercase();
                        
                        if !likely_dirs.iter().any(|&d| lower_name.contains(d)) {
                            continue;
                        }
                    }
                    
                    dirs_to_search.push((path, depth + 1));
                }
            }
        }
    }
    
    if found_paths.is_empty() {
        None
    } else {
        Some(found_paths)
    }
}

/// Find a header file recursively up to a maximum depth
fn find_header_recursively(start_dir: &Path, header_name: &str, max_depth: usize) -> Option<PathBuf> {
    let mut dirs_to_search = vec![(start_dir.to_path_buf(), 0)];
    
    // Skip these directories for better performance
    let skip_dirs = [
        "proc", "sys", "dev", "tmp", "var", "run", "media", "mnt",
        "cdrom", "boot", "home", "bin", "sbin"
    ];
    
    // Prioritize "include" and "graphviz" directories
    let priority_dirs = ["include", "graphviz"];
    
    // First, search only in priority directories
    while let Some((dir, depth)) = dirs_to_search.pop() {
        if depth > max_depth || !dir.is_dir() {
            continue;
        }
        
        // Check if header exists directly
        let header_path = dir.join(header_name);
        if header_path.exists() {
            return Some(header_path);
        }
        
        // Check if there's a graphviz subdirectory with the header
        let graphviz_header = dir.join("graphviz").join(header_name);
        if graphviz_header.exists() {
            return Some(graphviz_header);
        }
        
        if depth == max_depth {
            continue;
        }
        
        // Search subdirectories, but only priority ones in the first pass
        if let Ok(entries) = fs::read_dir(&dir) {
            for entry in entries.filter_map(Result::ok) {
                let path = entry.path();
                
                if path.is_dir() {
                    let dir_name = path.file_name()
                        .and_then(|n| n.to_str())
                        .unwrap_or("");
                    
                    if priority_dirs.iter().any(|&p| dir_name.to_lowercase() == p) {
                        dirs_to_search.push((path, depth + 1));
                    }
                }
            }
        }
    }
    
    // If not found in priority directories, try a broader search
    dirs_to_search = vec![(start_dir.to_path_buf(), 0)];
    
    while let Some((dir, depth)) = dirs_to_search.pop() {
        if depth > max_depth || !dir.is_dir() {
            continue;
        }
        
        // Check if header exists directly (already checked in priority pass)
        if depth > 0 {
            let header_path = dir.join(header_name);
            if header_path.exists() {
                return Some(header_path);
            }
            
            // Check if there's a graphviz subdirectory with the header
            let graphviz_header = dir.join("graphviz").join(header_name);
            if graphviz_header.exists() {
                return Some(graphviz_header);
            }
        }
        
        if depth == max_depth {
            continue;
        }
        
        // Search subdirectories
        if let Ok(entries) = fs::read_dir(&dir) {
            for entry in entries.filter_map(Result::ok) {
                let path = entry.path();
                
                if path.is_dir() {
                    let dir_name = path.file_name()
                        .and_then(|n| n.to_str())
                        .unwrap_or("");
                    
                    // Skip unlikely directories
                    if skip_dirs.contains(&dir_name) || dir_name.starts_with(".") {
                        continue;
                    }
                    
                    dirs_to_search.push((path, depth + 1));
                }
            }
        }
    }
    
    None
}

/// Create a wrapper header file
fn create_wrapper_header(header_include: &str) -> PathBuf {
    let out_dir = env::var("OUT_DIR").unwrap();
    let wrapper_path = PathBuf::from(&out_dir).join("wrapper.h");
    
    let mut file = fs::File::create(&wrapper_path).expect("Failed to create wrapper header file");
    writeln!(file, "#include <{}>", header_include)
        .expect("Failed to write to wrapper header file");
    
    wrapper_path
}

/// Get the library file extension for the current platform
fn get_lib_extension(platform: Platform) -> &'static str {
    match platform {
        Platform::Windows => "dll",
        Platform::MacOS => "dylib",
        _ => "so",
    }
}