// Copyright 2023 The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.

use std::{
    collections::{HashMap, HashSet},
    fmt,
    sync::Arc,
};

use fixedbitset::FixedBitSet;
use petgraph::{
    dot::{self, Dot},
    graph::{Neighbors, NodeIndex},
    visit::Dfs,
    Directed, Direction, Graph,
};

use crate::{
    project::{
        manifest::{self, Manifest},
        File,
    },
    target::{Provider, Target},
    Error, Result,
};

/// A node in the dependency graph.
#[derive(Debug)]
pub enum Dependency {
    /// A resolved dependency.
    Resolved(Arc<Target>),

    /// An unresolved dependency.  This occurs when a target declares a
    /// dependency for a target that has not been seen.
    Unresolved(String),
}

impl fmt::Display for Dependency {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Resolved(target) => write!(f, "{}", target.full_name()),
            Self::Unresolved(name) => write!(f, "{name}"),
        }
    }
}

/// An edge in the dependency graph.
/// We define an empty struct for edges instead of using the unit type
/// to allow us to implement `fmt::Display` for it.  This is needed for
/// graphviz output.
#[derive(Debug)]
pub struct Edge {}

impl fmt::Display for Edge {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "")
    }
}

/// An identifier for a node in the dependency graph.
pub type NodeId = NodeIndex<u32>;

/// An iterator of target dependencies.
pub struct Dependencies<'a> {
    registry: &'a Registry,
    dfs: Dfs<NodeIndex, FixedBitSet>,
}

impl<'a> Iterator for Dependencies<'a> {
    type Item = &'a Dependency;

    fn next(&mut self) -> Option<Self::Item> {
        self.dfs
            .next(&self.registry.dependency_graph)
            .and_then(|node_id| self.registry.dependency_graph.node_weight(node_id))
    }
}

/// A database of packages known to `qg`.
#[derive(Debug)]
pub struct Registry {
    /// Mapping of package slug to package. Slugs are globally unique.
    targets: HashMap<String, Arc<Target>>,

    /// All known package providers by name.
    providers: HashMap<String, Provider>,

    /// Unknown target dependencies.
    unresolved_dependencies: HashSet<String>,

    /// Dependency Graph of targets.
    ///
    /// Nodes that have a `None` weight are unresolved.
    dependency_graph: Graph<Dependency, Edge, Directed, u32>,

    /// Map from target full name to dependency graph node IDe.
    node_id_map: HashMap<String, NodeId>,
}

impl Registry {
    /// Initializes an empty package registry.
    #[must_use]
    pub fn new() -> Self {
        Self {
            targets: HashMap::new(),
            providers: HashMap::new(),
            unresolved_dependencies: HashSet::new(),
            dependency_graph: Graph::new(),
            node_id_map: HashMap::new(),
        }
    }

    /// Reads `qg` manifest files starting from the project root into a registry
    /// of available packages.
    ///
    /// # Errors
    /// Returns an error if manifest files could not be read or are improperly
    /// structured.
    pub fn parse_manifests(root_manifest_file: &File) -> Result<Self> {
        let root_manifest = root_manifest_file.deserialize_toml::<Manifest>()?;
        let mut registry = Registry::new();

        let project_provider = Provider::new(
            &root_manifest.project.name,
            root_manifest_file.path(),
            false,
        );
        registry.add_provider(project_provider)?;

        for (name, target) in root_manifest.targets {
            registry.add_target(crate::Target::from_manifest(
                &name,
                &root_manifest.project.name,
                target.namespace.is_global(),
                target,
            )?)?;
        }

        for (provider, desc) in &root_manifest.providers {
            if let Some(manifest) = &desc.manifest {
                let provider_file = root_manifest_file.relative_file(manifest);

                let provider_data = provider_file.deserialize_toml::<manifest::ProviderFile>()?;
                let global_provider = if let Some(desc) = &provider_data.provider {
                    desc.namespace.is_global()
                } else {
                    false
                };

                registry.add_provider(Provider::new(
                    provider,
                    provider_file.path(),
                    global_provider,
                ))?;

                for (name, target) in provider_data.targets {
                    registry.add_target(crate::Target::from_manifest(
                        &name,
                        provider,
                        global_provider || target.namespace.is_global(),
                        target,
                    )?)?;
                }
            }
        }

        Ok(registry)
    }

    /// Returns the number of registered targets.
    #[must_use]
    pub fn target_count(&self) -> usize {
        self.targets.len()
    }

    /// Returns an iterator over all known targets, in arbitrary order.
    pub fn targets(&self) -> impl Iterator<Item = &Target> {
        self.targets.values().map(Arc::as_ref)
    }

    /// Registers a new provider.
    pub(crate) fn add_provider(&mut self, provider: Provider) -> Result<()> {
        if self.providers.contains_key(&provider.name) {
            // TODO(frolv): Provider names must be unique.
            return Err(Error::GenericErrorPlaceholder);
        }
        self.providers.insert(provider.name.clone(), provider);
        Ok(())
    }

    /// Returns the dependency graph in graphviz dot format.
    #[must_use]
    pub fn dot_dependency_graph(&self) -> String {
        format!(
            "{:}",
            Dot::with_config(&self.dependency_graph, &[dot::Config::EdgeNoLabel])
        )
    }

    /// Inserts a target into the registry.
    pub(crate) fn add_target(&mut self, target: Target) -> Result<()> {
        if !self.providers.contains_key(target.provider()) {
            // TODO(frolv): Target must have a known provider.
            return Err(Error::GenericErrorPlaceholder);
        };

        let target_name = target.full_name();
        for dep in target
            .dependencies()
            .filter(|&d| !self.targets.contains_key(d))
        {
            self.unresolved_dependencies.insert(dep.into());
        }

        self.unresolved_dependencies.remove(&target_name);

        let target = Arc::new(target);
        self.update_dependency_graph_for_new_target(&target);
        self.targets.insert(target_name.clone(), target);

        Ok(())
    }

    fn update_dependency_graph_for_new_target(&mut self, target: &Arc<Target>) {
        let target_name = target.full_name();

        let node_id = if let Some(id) = self.node_id_map.get(&target_name) {
            // If the target is already in the graph, it is because a previous
            // target as taken an unresolved dependency on it.  Update the node
            // with the resolved target.
            *self
                .dependency_graph
                .node_weight_mut(*id)
                .expect("node should exist in graph") = Dependency::Resolved(target.clone());
            *id
        } else {
            let id = self
                .dependency_graph
                .add_node(Dependency::Resolved(target.clone()));
            self.node_id_map.insert(target_name, id);
            id
        };

        for dep in target.dependencies() {
            // Get the node id of the dependency.  Insert an unresolved
            // dependency if the node does not already exist.
            let dep_node_id = *self.node_id_map.entry(dep.to_string()).or_insert_with(|| {
                self.dependency_graph
                    .add_node(Dependency::Unresolved(dep.to_string()))
            });
            self.dependency_graph
                .add_edge(node_id, dep_node_id, Edge {});
        }
    }

    /// Returns the build target with the specified name, if it exists.
    ///
    /// # Errors
    /// Returns an error if the named target does not exist or is an unresolved
    /// dependency.
    pub fn get_target(&self, name: &str) -> Result<Arc<Target>> {
        self.get_node_id(name)
            .and_then(|id| self.get_target_by_id(id))
    }

    /// Returns the node ID for a node.
    ///
    /// # Errors
    /// Returns an error if the given node name does not exist.
    pub fn get_node_id(&self, name: &str) -> Result<NodeId> {
        self.node_id_map
            .get(name)
            .ok_or(
                // Node not found.
                Error::GenericErrorPlaceholder,
            )
            .map(|id| *id)
    }

    /// Returns an iterator of dependencies for the node.
    #[must_use]
    pub fn node_deps(&self, node: NodeId) -> Neighbors<Edge, u32> {
        self.dependency_graph
            .neighbors_directed(node, Direction::Outgoing)
    }

    /// Returns the `Target` associated with the `node_id`.
    ///
    /// # Errors
    /// Returns an error if:
    /// - `node_id` does not refer to a valid node in the dependency graph.
    /// - the referenced node is an unresolved dependency.
    pub fn get_target_by_id(&self, node_id: NodeId) -> Result<Arc<Target>> {
        let target = self.dependency_graph.node_weight(node_id).ok_or(
            // Node not found.
            Error::GenericErrorPlaceholder,
        )?;
        match target {
            Dependency::Resolved(target) => Ok(target.clone()),
            Dependency::Unresolved(_) => Err(Error::GenericErrorPlaceholder),
        }
    }

    /// Returns an iterator for traversing a target's transitive dependencies.
    ///
    /// # Errors
    /// Returns an error if `target_name` does not name a valid target.
    #[allow(unused)]
    pub fn transitive_dependencies(&self, target_name: &str) -> Result<Dependencies> {
        let node_id = self.get_node_id(target_name)?;
        let dfs = Dfs::new(&self.dependency_graph, node_id);

        Ok(Dependencies {
            registry: self,
            dfs,
        })
    }
}

impl Default for Registry {
    fn default() -> Self {
        Self::new()
    }
}