pub mod dependency;
pub mod error;

pub use crate::version::semver;
pub use dependency::Dependency;

use crate::{
    lock::PackageInLockFile,
    package::{
        OrganizationToResolveFor, PackageSet, PackageVersion, PackageVersionWithRegistryMetadata,
    },
    registry::Registry,
    version::SemanticVersion,
    ORGANIZATION, ORGANIZATION_NAME, ORGANIZATION_VERSION,
};

use pubgrub::{
    range::Range,
    report::Reporter,
    solver::{DependencyConstraints, DependencyProvider},
};

use std::{
    borrow::Borrow,
    collections::BTreeMap,
    convert::{From, Into},
};

use anyhow::Result;
use fallible_iterator::FallibleIterator;
use itertools::Itertools;

use self::error::ResolverError;
use std::str::FromStr;

/// A trait for different dependency resolver implementations.
pub trait Resolver {
    /// Resolves a set of requested dependencies to a set of package versions.
    fn resolve_dependencies(
        &self,
        organization_to_resolve_for: OrganizationToResolveFor,
        locked_dependencies: Option<&[PackageInLockFile]>,
    ) -> Result<PackageSet, ResolverError>;
}

/// A type which is used in resolver to collect all available versions of a package.
pub type SemanticVersionAndRangePair = (SemanticVersion, Range<SemanticVersion>);

/// A type which is used in resolver to collect all available versions of a package.
pub type AvailablePackagesWithDepConstraints =
    BTreeMap<SemanticVersion, DependencyConstraints<String, SemanticVersion>>;

/// A type which is used in resolver to collect valid versions of a package to be picked later.
pub type ValidPackagesIntermediateCache = BTreeMap<String, Vec<SemanticVersion>>;

/// A cache to use across resolver iterations.
pub type AvailablePackagesCache = BTreeMap<String, Vec<PackageVersionWithRegistryMetadata>>;
/// A resolver which uses pubgrub algorithm to resolve dependencies with semantic version requests.
pub struct VersionRequestResolver<'req_resolver> {
    // Access to registry.
    registry: &'req_resolver dyn Registry,
    // A cache to use across a single resolver iteration.
    valid_versions_intermediate_cache: std::cell::RefCell<ValidPackagesIntermediateCache>,
    // A cache to use across resolver iterations.
    available_packages_cache: std::cell::RefCell<AvailablePackagesCache>,
    locked_dependencies: std::cell::RefCell<Option<BTreeMap<String, SemanticVersion>>>,
}

impl<'req_resolver> From<&'req_resolver dyn Registry> for VersionRequestResolver<'req_resolver> {
    fn from(registry: &'req_resolver dyn Registry) -> Self {
        Self {
            registry,
            valid_versions_intermediate_cache: std::cell::RefCell::new(
                ValidPackagesIntermediateCache::default(),
            ),
            available_packages_cache: std::cell::RefCell::new(AvailablePackagesCache::default()),
            locked_dependencies: std::cell::RefCell::new(None),
        }
    }
}

impl<'req_resolver> VersionRequestResolver<'req_resolver> {
    /// Handles the errors originate directly from dependency resolution.
    fn handle_resolution_errors(
        error: pubgrub::error::PubGrubError<String, SemanticVersion>,
    ) -> ResolverError {
        // Error in resolution
        use pubgrub::error::PubGrubError::*;
        match error {
            NoSolution(mut tree) => {
                tree.collapse_no_versions();
                let report = pubgrub::report::DefaultStringReporter::report(&tree);
                ResolverError::SolutionError(report.replace(ORGANIZATION, "organization").replace(
                    "Organization is forbidden",
                    "Dependencies of the organization could not be resolved",
                ))
            }
            ErrorRetrievingDependencies {
                package,
                version,
                source,
            } => {
                let mut message = format!("Error retrieving dependencies for package {package} at version {version}.\n Error: {source}");
                message = message.replace(
                    &format!("package {ORGANIZATION_NAME} at version {ORGANIZATION_VERSION}"),
                    "organization",
                );
                ResolverError::SolutionError(message)
            }
            DependencyOnTheEmptySet {
                package,
                version,
                dependent,
            } => {
                let mut message = format!("Returned a dependency on an empty range.\nThe package {dependent} requires us to pick from an empty set.\nThe package which was being tried to be picked: name {package}, version {version}.");
                message = message.replace(
                    &format!("package {ORGANIZATION_NAME} at version {ORGANIZATION_VERSION}"),
                    "organization",
                );
                ResolverError::SolutionError(message)
            }
            SelfDependency { package, version } => {
                let mut message = format!("Self dependency detected.\nThe package {package} requires itself at version {version}.");
                message = message.replace(
                    &format!("The package {ORGANIZATION_NAME} requires itself at version {ORGANIZATION_VERSION}"),
                    "Organization can not depend on itself",
                );
                ResolverError::SolutionError(message)
            }
            ErrorChoosingPackageVersion(err) => {
                ResolverError::SolutionError(format!("Error choosing package version.\n{err}"))
            }
            ErrorInShouldCancel(err) => {
                ResolverError::SolutionError(format!("Error in should_cancel.\n{err}"))
            }
            Failure(reason) => ResolverError::SolutionError(reason),
        }
    }

    /// Post processes the resolved dependencies.
    ///
    /// This includes removing duplicates, sorting and validating if there are multiple
    /// versions of the same package.
    fn post_process_and_deliver_resolved_dependencies(
        &self,
        resolved_dependencies: Vec<PackageVersion>,
    ) -> Result<PackageSet, ResolverError> {
        // Here we apply any post processing to resolved dependencies
        let packages: Vec<PackageVersion> = resolved_dependencies
            .into_iter()
            // Filter the root package which represents the organization which we resolve for.
            .filter(|package| package.package_name != ORGANIZATION_NAME)
            // Sort
            .sorted()
            // Remove duplicates
            .dedup()
            .collect();

        // Collect packages which are the same but have multiple different versions for a possible future error message.
        let same_packages_with_multiple_versions: Vec<&PackageVersion> = packages
            .iter()
            .filter(|package_checking| {
                packages.iter().any(|package_comparing| {
                    // Note: Duplicates are removed at this point

                    // Same package name
                    package_checking.package_name == package_comparing.package_name
                            // Different versions
                                && package_checking.version != package_comparing.version
                            // Other than the package we're currently checking.
                                && package_checking != &package_comparing
                })
            })
            .collect();

        if same_packages_with_multiple_versions.is_empty() {
            // Clear the cache.
            self.available_packages_cache.borrow_mut().clear();
            // Solved
            return Ok(PackageSet { packages });
        }

        // There are multiple versions of same packages so we should inform the user about it with an error.
        let error_message = same_packages_with_multiple_versions.into_iter().fold(
                    "Packages or dependencies may not have multiple versions of the same package.\nThe packages which have multiple versions defined are:\n"
                        .to_owned(),
                    |mut message, package| {
                        message
                            .push_str(&format!("\t{} {}\n", package.package_name, package.version));
                        message
                    },
                );
        Err(ResolverError::SolutionError(error_message))
    }

    fn get_valid_packages<U: std::borrow::Borrow<Range<SemanticVersion>>>(
        available_packages: &[PackageVersionWithRegistryMetadata],
        requested_range: &U,
    ) -> Result<Vec<SemanticVersion>, ResolverError> {
        fallible_iterator::convert(available_packages.iter()
        .try_fold(
            AvailablePackagesWithDepConstraints::default(),
            |mut available_versions_of_package_and_their_dependency_constraints,
             metadata|
             -> Result<AvailablePackagesWithDepConstraints, ResolverError> {
                // For the value of the map we need to create a new DependencyConstraints type.
                // For this we need to get all the dependencies of this package.
                let dependencies = metadata.dependencies.iter().try_fold(
                    DependencyConstraints::<String, SemanticVersion>::default(),
                    |mut dependencies,
                     dep|
                     -> Result<
                        DependencyConstraints<String, SemanticVersion>,
                        ResolverError,
                    > {
                        dependencies.insert(dep.full_name.clone(), dep.version_range.clone());
                        Ok(dependencies)
                    },
                );
                match dependencies {
                    Ok(dependencies) => {
                        // Collect all available packages.
                        available_versions_of_package_and_their_dependency_constraints
                            .insert(metadata.version, dependencies);
                        Ok(available_versions_of_package_and_their_dependency_constraints)
                    }
                    Err(err) => Err(err),
                }
            },
        )?
        // Transform the retrieval to the type we need.
        .borrow()
        .keys()
        .sorted()
        .into_iter()
        .copied().map(Ok))
        // We give the constraint here.
        .filter(|v| Ok(requested_range.borrow().contains(v.borrow())))
        .collect()
    }

    /// Counts and caches the valid versions of a package.
    ///
    /// By valid version we mean that the version of a package
    /// which falls in to the provided version requirement range.
    fn cache_and_count_valid_versions_of_package<
        T: std::borrow::Borrow<String>,
        U: std::borrow::Borrow<Range<SemanticVersion>>,
    >(
        &self,
        available_packages: &[PackageVersionWithRegistryMetadata],
        requested_package: &T,
        requested_range: &U,
    ) -> Result<usize, ResolverError> {
        let valid_packages = Self::get_valid_packages(available_packages, requested_range)?;

        // Quantity of valid versions of a package
        let count = valid_packages.len();

        // Store them in an intermediate cache for the picking operation for this run, indexed by package name.
        // This is a step to share the state out of the closure calling this function.
        self.valid_versions_intermediate_cache
            .borrow_mut()
            .insert(requested_package.borrow().clone(), valid_packages);

        Ok(count)
    }
}

impl<'req_resolver> Resolver for VersionRequestResolver<'req_resolver> {
    /// Resolves a set of requested dependencies to a set of package versions
    fn resolve_dependencies(
        &self,
        organization_to_resolve_for: OrganizationToResolveFor,
        locked_dependencies: Option<&[PackageInLockFile]>,
        // TODO: A user requested update will be added here.
    ) -> Result<PackageSet, ResolverError> {
        // In our use case we solve for organizations but not packages.
        // An organization has dependencies but itself is not a package but more of an entity.
        // You can not depend on an organization or add it as a dependency.
        // Organization can depend on packages and it is always our entry point to the resolution.
        // To cover for this case we always start with 1 item in our cache, our root organization which we solve for.
        // This way the resolver will find it in the first hit and continue resolving real packages.
        // Store the organization in the cache.
        self.available_packages_cache.borrow_mut().insert(
            organization_to_resolve_for.package_name.clone(),
            vec![PackageVersionWithRegistryMetadata {
                package_name: organization_to_resolve_for.package_name.clone(),
                version: organization_to_resolve_for.package_version,
                ontology_iri: None,
                dependencies: organization_to_resolve_for.dependencies,
                cksum: None,
                private: false,
            }],
        );

        // Collect locked dependencies if there are some.
        // Derives versions assuming there can only be one version of a dependency in a lock file.
        if let Some(packages) = locked_dependencies {
            *self.locked_dependencies.borrow_mut() = Some(packages.iter().fold(
                BTreeMap::new(),
                |mut locked_dependencies: BTreeMap<String, SemanticVersion>,
                 package: &PackageInLockFile|
                 -> BTreeMap<String, SemanticVersion> {
                    // Dependencies of a single package in a lock file.
                    let deps = &package.dependencies;
                    // Find the right versions in the lock file.
                    for dep_name in deps {
                        for package in packages {
                            if &package.name == dep_name
                                && locked_dependencies.get(&package.name).is_none()
                            {
                                locked_dependencies
                                    .insert(package.name.clone(), semver!(&package.version));
                            }
                        }
                    }
                    locked_dependencies
                },
            ));
        }

        // Now we are ready to start the resolution.
        pubgrub::solver::resolve(
            self,
            organization_to_resolve_for.package_name,
            organization_to_resolve_for.package_version,
        )
        .map_or_else(Err, |solved| {
            // Transform to PackageVersion structs.

            Ok(solved.iter().map_into().collect::<Vec<PackageVersion>>())
        })
        .map_or_else(
            |err| Err(Self::handle_resolution_errors(err)),
            |resolved_dependencies| {
                // Post process and deliver
                self.post_process_and_deliver_resolved_dependencies(resolved_dependencies)
            },
        )
    }
}

impl<'req_resolver> DependencyProvider<String, SemanticVersion>
    for VersionRequestResolver<'req_resolver>
{
    // Chooses a valid package  version for the given package.
    // There may be multiple versions of the package in focus.
    // We first find all available versions of a package and pick the highest version in our specified constrains.

    // Unwraps used here will not panic and they're explained.
    #[allow(clippy::unwrap_in_result)]
    // I sincerely think that the first match in this function is the most readable way to write it.
    #[allow(clippy::single_match_else)]
    fn choose_package_version<
        T: std::borrow::Borrow<String>,
        U: std::borrow::Borrow<Range<SemanticVersion>>,
    >(
        &self,
        potential_packages: impl Iterator<Item = (T, U)>,
    ) -> Result<(T, Option<SemanticVersion>), Box<dyn std::error::Error>> {
        // This function is a re-implementation of the pubgrub `choose_package_with_fewest_versions` function with some minor changes.
        // You may check the original at (https://github.com/pubgrub-rs/pubgrub/blob/717289be5722dd5caaa0d1f4ed13047d11a7f7fd/src/solver.rs#L279-L300)
        let count_valid = |(package, range): &(T, U)| -> Result<usize, ResolverError> {
            // Early return if a package in potential_packages hits the lock file,

            // TODO: A way to update individual packages in the lock file.
            // Ignore this for the package if it has an update flag.
            // Change package type to include update flags.

            if let Some(ref locked_dependencies) = *self.locked_dependencies.borrow() {
                if let Some(locked_dependency_version) = locked_dependencies.get(package.borrow()) {
                    self.valid_versions_intermediate_cache.borrow_mut().insert(
                        package.borrow().clone(),
                        // We know that this is always a valid, single, complete and exact version.
                        vec![*locked_dependency_version],
                    );
                    // Pick only one valid version since we exactly want that version.
                    return Ok(1);
                }
            }
            // if let Some(ref locked_dependencies) = *self.locked_dependencies.borrow() {
            //     if let Some((locked_dependency_version, locked_dependency_range)) =
            //         locked_dependencies.get(package.borrow())
            //     {
            //         if locked_dependency_range.intersection(range.borrow()) != Range::none() {
            //             self.valid_versions_intermediate_cache.borrow_mut().insert(
            //                 package.borrow().clone(),
            //                 // We know that this is always a valid, single, complete and exact version.
            //                 vec![*locked_dependency_version],
            //             );

            //             // Pick only one valid version since we exactly want that version.
            //             return Ok(1);
            //         }
            //     }
            // }

            // TODO: In future iterations we'll add other resources for checking for dependencies such as the local file system.
            // Currently we only check registry.

            // Check if we already retrieved this information and stored it in cache.
            let mut available_package_cache = self.available_packages_cache.borrow_mut();
            let available_packages = match available_package_cache.get(package.borrow()) {
                Some(packages) => packages,
                None => {
                    // Cache miss, retrieve from registry.
                    let mut available_packages = self
                        .registry
                        .all_available_versions_of_a_package(package.borrow().clone());

                    // Sort by version, descending.
                    available_packages.sort_by(|a, b| b.version.cmp(&a.version));

                    // Cache available packages for the next run.
                    available_package_cache.insert(package.borrow().clone(), available_packages);

                    #[allow(clippy::unwrap_used)]
                    // This is fine, we have just inserted it.
                    available_package_cache.get(package.borrow()).unwrap()
                }
            };

            // Pick valid versions of available packages regarding the requested version range.
            // Cache them to share the state out of this closure.
            // Return the count of valid versions.
            self.cache_and_count_valid_versions_of_package(available_packages, package, range)
        };

        let (package, range) = fallible_iterator::convert(potential_packages.map(Ok))
            .min_by_key(count_valid)?
            // Handle the error?
            // Since this piece was copied from a helper function from the pubgrub crate
            // maybe it is ok to leave it as is.
            .expect("potential_packages gave us an empty iterator");

        #[allow(clippy::unwrap_used)]
        let mut valid_versions_for_package = self
            .valid_versions_intermediate_cache
            .borrow_mut()
            .get(package.borrow())
            // This is fine, we've just filled this intermediate cache in `count_valid` closure.
            .unwrap()
            .clone();

        // Order by descending versions.
        valid_versions_for_package.sort_by(|a, b| b.cmp(a));

        let version = valid_versions_for_package.iter().copied().find(|v| {
            // Pick the first valid version, which will always be the highest version because we've sorted it.
            range.borrow().contains(v.borrow())
        });

        // We need to clear our intermediate cache in the end of this iteration to have it ready and empty for the next run.
        self.valid_versions_intermediate_cache.borrow_mut().clear();

        // Deliver the solution.
        Ok((package, version))
    }

    // Validates dependencies.
    fn get_dependencies(
        &self,
        package: &String,
        version: &SemanticVersion,
    ) -> Result<pubgrub::solver::Dependencies<String, SemanticVersion>, Box<dyn std::error::Error>>
    {
        // We need to work with our own type to query the registry.
        let package_version = (package, version).into();

        if package == ORGANIZATION_NAME {
            return Ok(pubgrub::solver::Dependencies::Known(
                // We explicitly insert and always know that we'll have the organization package in cache.
                #[allow(clippy::indexing_slicing)]
                self.available_packages_cache.borrow()[package][0]
                    .dependencies
                    .iter()
                    .try_fold(
                        DependencyConstraints::<String, SemanticVersion>::default(),
                        |mut dependencies,
                         dep|
                         -> Result<
                            DependencyConstraints<String, SemanticVersion>,
                            ResolverError,
                        > {
                            // Insert dependencies of the organization.
                            dependencies.insert(dep.full_name.clone(), dep.version_range.clone());
                            Ok(dependencies)
                        },
                    )?,
            ));
        }

        Ok(
            // TODO: In future iterations we'll add other resources for checking for dependencies such as the local file system.
            // Currently we only check registry.
            match self.registry.get_package_version_metadata(&package_version) {
                // Something went wrong and we couldn't retrieve the picked package from registry.
                Err(_) => pubgrub::solver::Dependencies::Unknown,
                // Deliver the dependencies of the picked package for this run.
                Ok(package) => {
                    let dependencies = package.dependencies.iter().try_fold(
                        DependencyConstraints::<String, SemanticVersion>::default(),
                        |mut dependencies,
                         dep|
                         -> Result<
                            DependencyConstraints<String, SemanticVersion>,
                            ResolverError,
                        > {
                            dependencies.insert(dep.full_name.clone(), dep.version_range.clone());
                            Ok(dependencies)
                        },
                    );
                    pubgrub::solver::Dependencies::Known(dependencies?)
                }
            },
        )
    }

    // An error might be returned here to terminate the operation abruptly.
    fn should_cancel(&self) -> Result<(), Box<dyn std::error::Error>> {
        Ok(())
    }
}