using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

namespace OpenTap.Package
{ 
    /// <summary>
    /// Resolves packages dependencies for an image.This should be able to resolve any set of package dependencies, but
    /// it may take a long time in some edge cases. In most cases however it seems to settle quite quickly.
    /// </summary>
    class ImageResolver
    {
        CancellationToken cancelToken;
        public ImageResolver(CancellationToken cancelToken)
        {
            this.cancelToken = cancelToken;
        }
           

        long Iterations;

        public ImageResolution ResolveImage(ImageSpecifier image, PackageDependencyGraph graph)
        {
            cancelToken.ThrowIfCancellationRequested();
            Iterations++;
            List<PackageSpecifier> packages = image.Packages.ToList();
            
            // make sure that specifications are consistent.
            // 1. remove redundant package specifiers
            for (int i = 0; i < packages.Count; i++)
            {
                var pkg1 = packages[i];
                retry:
                for (int j = i + 1; j < packages.Count; j++)
                {
                    var pkg2 = packages[j];
                    if (pkg2.Name == pkg1.Name)
                    {
                        // Trivially remove one of the completely identical packages
                        if (pkg2.Version == pkg1.Version)
                        {
                            packages.RemoveAt(j);
                            goto retry;
                        } 
                        
                        if (!pkg2.Version.IsSatisfiedBy(pkg1.Version) && !pkg1.Version.IsSatisfiedBy(pkg2.Version))
                            return new FailedImageResolution(image, new MutuallyExclusiveResolutionProblem(pkg1, pkg2), Iterations);

                        if (!pkg1.Version.IsSatisfiedBy(pkg2.Version))
                        {
                            // select pkg1 instead of pkg2
                            packages.RemoveAt(j);
                            goto retry;
                        }
                        if(!pkg2.Version.IsSatisfiedBy(pkg1.Version)) // pkg1 is satisfied by pkg2
                        {
                            // select pkg2 instead of pkg1
                            packages[i] = pkg2;
                            pkg1 = pkg2;
                            packages.RemoveAt(j);
                            goto retry;
                        }
                        // pkg1 might still be different from pkg2 if one is exact and another one isn't.
                    }
                }
            }

            //2. expand dependencies for exact package specifiers
            bool modified = true;
            while (modified)
            {
                modified = false;
                for (int i = 0; i < packages.Count; i++)
                {
                    var pkg1 = packages[i];
                    if (pkg1.Version.TryAsExactSemanticVersion(out var v) == false)
                        continue;

                    var deps = graph.GetDependencies(pkg1.Name, v);
                    foreach (var dep in deps)
                    {
                        for (int j = 0; j < packages.Count; j++)
                        {
                            var pkg2 = packages[j];
                            if (pkg2.Name == dep.Name)
                            {
                                // this dependency can be satisfied?
                                if (!pkg2.Version.IsSatisfiedBy(dep.Version) &&
                                    !dep.Version.IsSatisfiedBy(pkg2.Version))
                                {
                                    // this dependency is unresolvable
                                    return new FailedImageResolution(image, new MutuallyExclusiveResolutionProblem(pkg2, dep), Iterations);
                                }

                                // this dependency is more specific than the existing.
                                if (pkg2.Version != dep.Version && (pkg2.Version.IsSuperSetOf(dep.Version) || !dep.Version.IsSatisfiedBy(pkg2.Version)) && pkg2.Version.MatchBehavior != VersionMatchBehavior.Exact)
                                {
                                    packages[j] = dep;
                                    modified = true;
                                    break;
                                }
                            }
                        }

                        // add the dependency
                        if (!packages.Any(x => x.Name == dep.Name))
                        {
                            packages.Add(dep);
                            modified = true;
                        }
                    }
                }
            }

            graph.EnsurePackagePreReleasesCached(packages);

            List<SemanticVersion[]> allVersions = new List<SemanticVersion[]>();

            // 3. foreach package specifier get all the available versions
            for (int i = 0; i < packages.Count; i++)
            {
                var pkg = packages[i];
                var versions = graph.PackagesSatisfying(pkg).ToArray();
               allVersions.Add(versions);
            }
            
            // 4. prune away the versions which dependencies conflict with the required packages.
            // ok, now we know the results is some pair-wise combination of allVersions.
            // now let's try pruning them a bit
            bool retry = false;
            for (int i = 0; i < packages.Count; i++)
            {
                var pkg = packages[i];
                var versions = allVersions[i];
                var others = packages.Except(x => x == pkg).ToArray();
                var newVersions = versions.Where(x =>
                        graph.CouldSatisfy(pkg.Name, new VersionSpecifier(x, VersionMatchBehavior.Exact), others, image.FixedPackages))
                    .ToArray();
                allVersions[i] = newVersions;
                if (newVersions.Length == 1 && !pkg.Version.IsExact)
                {
                    packages[i] = new PackageSpecifier(pkg.Name,
                        // newVersions[0] will always be exact.
                        new VersionSpecifier(newVersions[0], VersionMatchBehavior.Exact));
                    retry = true;
                }
                else if (newVersions.Length == 1)
                {
                    if (pkg.Version.PreRelease != newVersions[0].PreRelease ||
                        pkg.Version.BuildMetadata != newVersions[0].BuildMetadata)
                    { 
                        // in this case update the version for the package specifier
                        // the exact dependencies has changed, so we need to do another round of resolution.
                        packages[i] = new PackageSpecifier(pkg.Name,
                            new VersionSpecifier(newVersions[0], VersionMatchBehavior.Exact));
                        retry = true;
                    }
                }
            }

            if (retry)
                return ResolveImage(new ImageSpecifier(packages.ToList()){FixedPackages = image.FixedPackages}, graph);
            
            // 5. ok now we have X * Y * Z * ... = K possible solutions all satisfying the constraints.
            // Lets sort all the versions based on version specifiers, then fix  the version and try each combination (brute force)
            long k = allVersions.FirstOrDefault()?.LongLength ?? 0;
            for (int i = 1; i < allVersions.Count; i++)
            {
                k *= allVersions[i].LongLength;
            }

            if (k == 0)
            {
                if (packages.Count == 0) 
                    // special case when no packages are specified.
                    // this is an uncommon trivial corner case.
                    return new ImageResolution([], Iterations);

                {
                    // Handle the edge case where a compatible specifier does not match any package release versions.
                    // In this case, we should fetch all prereleases for packages with no candidates and retry the resolution.
                    // This can happen when trying to install e..g 'Basic Mixins:^0.2' because Basic Mixins (as of now)
                    // does not have any release versions. So even though 0.2.0-beta.1 is available and compatible,
                    // it will not have been fetched at this point because the specifier ^0.2 does not enforce fetching prereleases.
                    var packagesToUpdate = new List<PackageSpecifier>();
                    for (int i = 0; i < allVersions.Count; i++)
                    {
                        if (allVersions[i].Length == 0)
                        {
                            packagesToUpdate.Add(packages[i]);
                        }
                    }

                    // We can only fetch new versions for compatible specifies with no prerelease
                    bool allUpdatable = packagesToUpdate.All(
                        pkg => pkg.Version.MatchBehavior.HasFlag(VersionMatchBehavior.Compatible) &&
                               !pkg.Version.MatchBehavior.HasFlag(VersionMatchBehavior.AnyPrerelease) &&
                               pkg.Version.PreRelease == null
                    );

                    // Don't bother fetching more versions if all specifiers cannot be updated.
                    if (allUpdatable)
                    {
                        bool allUpdated = true;
                        foreach (var pkg in packagesToUpdate)
                        {
                            // Fetch all prereleases for this package.
                            var spec2 = pkg.Version.WithMatchBehavior(pkg.Version.MatchBehavior |
                                                                      VersionMatchBehavior.AnyPrerelease);
                            var fetch = new PackageSpecifier(pkg.Name, spec2, pkg.Architecture, pkg.OS);
                            allUpdated &= graph.EnsurePreReleasesCached(fetch);
                            var fetched = graph.PackagesSatisfying(fetch).Count();
                            allUpdated &= fetched > 0;
                            if (!allUpdated)
                                break;
                        }

                        // If we managed to fetch new versions of all packages with no candidates, retry the resolution
                        if (allUpdated)
                        {
                            return ResolveImage(
                                new ImageSpecifier(packages.ToList()) { FixedPackages = image.FixedPackages }, graph);
                        }
                    }
                }

                List<PackageSpecifier> ResolveProblems = new List<PackageSpecifier>();
                for (int i = 0; i < allVersions.Count; i++)
                {
                    if (allVersions[i].Length == 0)
                    {
                        ResolveProblems.Add(packages[i]);
                    }
                }

                return DetermineResolveError(image, graph, ResolveProblems);  // no solutions
            }

            if (k == 1)
            {
                bool allExact = allVersions.All(x => x.Length  == 1);
                if (allExact)
                {
                    {   // now double check that all packages has their dependencies included in the resolved image.
                        // under rare circumstances this is not the case and we need to re-run the resolution
                        // to add those dependencies.
                        foreach (var pkg in packages)
                        {
                            if (!pkg.Version.TryAsExactSemanticVersion(out var semver))
                                // this should never happen.
                                throw new InvalidOperationException("An unexact package version was resolved.");
                            var deps = graph.GetDependencies(pkg.Name, semver);
                            foreach (var dep in deps)
                            {
                                var satisfied = packages.Any(x => x.Name == dep.Name);
                                if (!satisfied)
                                {
                                    // all packages has only one specific version, but there are still unresolved dependencies.
                                    // this will be fixed in the next iteration, when dependencies are added.
                                    return ResolveImage(
                                        new ImageSpecifier(packages.ToList()) { FixedPackages = image.FixedPackages },
                                        graph);
                                }
                            }
                        }
                    }
                    // this is the final case.
                    return new ImageResolution(packages.ToArray(), Iterations);
                }
            }
            
            // sort the versions based on priorities. ^ -> sort ascending, Exact, but undermined e.g  (9.17.*), sort descending.
            
            for (int i = 0; i < allVersions.Count; i++)
            {
                var pkg = packages[i];
                // skip the following if there is less than two versions.
                if (allVersions[i].Length <= 1) continue;
                var versions = allVersions[i].ToList();
                
                if (pkg.Version == VersionSpecifier.Any)
                {
                    versions.Sort();
                    // any version -> take the newest first.
                    versions.Reverse();
                }
                else if(pkg.Version.MatchBehavior.HasFlag(VersionMatchBehavior.Exact))
                {
                    //exact may be more than one version, even though the match behavior is 'exact'.
                    // for example OpenTAP '9.17' is exact, but many versions matches that.
                    // We are interested in the newest in this case, so order newest -> oldest within the span.
                    versions.Sort();
                    versions.Reverse();
                }
                else if (pkg.Version.MatchBehavior.HasFlag(VersionMatchBehavior.Compatible))
                {
                    // In this case we want the closest possible version. So we use an ascending sorting.
                    // 'SortPartial' is used for sorting within an incomplete version e.g '^9.17'
                    // ^9.17 -> We want the newest 9.17 version, but if we cannot get a 9.17.* a  newer will suffice. 
                    versions = versions.OrderBy(x => x, pkg.Version.SortPartial).ToList();
                }

                allVersions[i] = versions.ToArray();
            }

            // Iterate each package, fixing one variable and iterating the whole available span.
            // note that this is a recursive call so even though we only fix _one_ variable here
            // the rest of the variables will be fixed in the recursions.
            for (int i = 0; i < allVersions.Count; i++)
            {
                var set = allVersions.Select(x => x[0]).ToArray();
                var pkgVersions = allVersions[i];
                if (pkgVersions.Length == 1) continue; // skip all exact versions
                for (int j = 0; j < pkgVersions.Length; j++)
                {
                    set[i] = pkgVersions[j];

                    var newSpecifier = new ImageSpecifier();
                    for (int k3 = 0; k3 < allVersions.Count; k3++)
                    {
                        newSpecifier.Packages.Add(packages[k3]);
                    }
                    for (int k2 = 0; k2 < pkgVersions.Length; k2++)
                    {
                        
                        newSpecifier.Packages[i] = new PackageSpecifier(packages[i].Name, new VersionSpecifier(allVersions[i][k2], VersionMatchBehavior.Exact));

                        // recursive to see if this specifier has a result.
                        var result = this.ResolveImage(newSpecifier, graph);
                        if (result.Success)
                            return result;
                    }
                }
            }
            
            // this probably never happens as we already returned null, when K was 0.
            return new FailedImageResolution(image, new GenericResolutionProblem(Array.Empty<PackageSpecifier>()), Iterations);
        }

        private FailedImageResolution DetermineResolveError(ImageSpecifier image, PackageDependencyGraph graph,
            List<PackageSpecifier> ResolveProblems)
        {
            ResolutionProblem problem = null;
            // Provide a different error message depending on the actual conflict
            // 1. The specified package does not exist
            // 2. The requested version could not be satisfied
            // 3. The requested package has a level 1 dependency conflict with the requested image
            var allSpecs = graph.PackageSpecifiers().ToArray();
            if (ResolveProblems.All(rp => false == allSpecs.Any(s => s.Name == rp.Name)))
            {
                problem = new DoesNotExistResolutionProblem(ResolveProblems);
            }
            else if (ResolveProblems.Count == 1)
            {
                var version = graph.PackagesSatisfying(ResolveProblems[0]).ToArray();
                if (version.Length == 0)
                {
                    problem = new NoPackagesSatisfyingResolutionProblem(ResolveProblems);
                }
                else
                {
                    var deps = graph.GetDependencies(ResolveProblems[0].Name, version[0]).ToArray();
                    foreach (var d in deps)
                    {
                        if (image.Packages.FirstOrDefault(p => p.Name == d.Name && !d.Version.IsSatisfiedBy(p.Version))
                            is { } requested)
                        {
                            problem = new IncompatbileResolutionProblem(requested, d, ResolveProblems[0]);
                            break;
                        }
                    }
                }
            }

            problem ??= new GenericResolutionProblem(ResolveProblems);
            return new FailedImageResolution(image, problem, Iterations);
        }
    }

    abstract class ResolutionProblem
    {
        public abstract string Description();

        public static string SpecifierString(PackageSpecifier x) => x.Version == VersionSpecifier.AnyRelease ? x.Name :  $"{x.Name}: {x.Version}";
        public string GetCommaSeparatedString() => string.Join(", ", Packages.Select(SpecifierString));
        public PackageSpecifier[] Packages;

        public ResolutionProblem(IEnumerable<PackageSpecifier> packages)
        {
            Packages = packages.ToArray();
        }

        public PackageSpecifier this[int index] => Packages[index];

        public int Count => Packages.Length;
    }

    class GenericResolutionProblem : ResolutionProblem
    {
        public GenericResolutionProblem(IEnumerable<PackageSpecifier> packages) : base(packages)
        {
        }

        public override string Description() =>
            this.GetCommaSeparatedString() + " could not be satisfied.";
    }

    class DoesNotExistResolutionProblem : ResolutionProblem
    {
        public DoesNotExistResolutionProblem(IEnumerable<PackageSpecifier> packages) : base(packages)
        {
        }

        public override string Description()
        {
            return "The following required packages do not exist: " + string.Join(", ", this.Packages.Select(p => p.Name));
        }
    }

    class IncompatbileResolutionProblem : ResolutionProblem
    {
        public IncompatbileResolutionProblem(PackageSpecifier requested, PackageSpecifier required, PackageSpecifier depender) : base(new[] { requested, required, depender })
        {
            Requested = requested;
            Required = required;
            Depender = depender;
        }

        public PackageSpecifier Requested { get; }
        public PackageSpecifier Required { get; }
        public PackageSpecifier Depender { get; }

        public override string Description() =>
            $"'{Requested.Name}:{Requested.Version}' was explicitly requested, but '{Depender.Name}:{Depender.Version}' requires '{Required.Name}:{Required.Version}'";
    }

    class NoPackagesSatisfyingResolutionProblem : ResolutionProblem
    {
        public NoPackagesSatisfyingResolutionProblem(IEnumerable<PackageSpecifier> packages) : base(packages)
        {
        }

        public override string Description() =>
            $"No packages exist satisfying: " + this.GetCommaSeparatedString();
    }

    class MutuallyExclusiveResolutionProblem : ResolutionProblem
    {
        public MutuallyExclusiveResolutionProblem(PackageSpecifier left, PackageSpecifier right) : base(new []{ left, right })
        {
        }

        public override string Description() =>
            $"{SpecifierString(this[0])} and {SpecifierString(this[1])} are mutually exclusive.";
    }

    class FailedImageResolution : ImageResolution
    {
        internal readonly ResolutionProblem resolveProblems;
        readonly ImageSpecifier image;
        public FailedImageResolution(ImageSpecifier img, ResolutionProblem resolveProblems, long iterations) : base(Array.Empty<PackageSpecifier>(), iterations)
        {
            image = img;
            this.resolveProblems = resolveProblems;
        }

        public override bool Success => false;

        public override string ToString()
        {
            string packages = $"Packages: {image}";
            string repositories = image.Repositories.Any() ? $" from {string.Join(", ", image.Repositories)}" : "";
            return $"{resolveProblems.Description()} ({packages}{repositories})";
        }
    }
}