import functools
import re
from itertools import chain

from django.conf import settings
from django.db import models
from django.db.migrations import operations
from django.db.migrations.migration import Migration
from django.db.migrations.operations.models import AlterModelOptions
from django.db.migrations.optimizer import MigrationOptimizer
from django.db.migrations.questioner import MigrationQuestioner
from django.db.migrations.utils import (
    COMPILED_REGEX_TYPE, RegexObject, get_migration_name_timestamp,
)

from .topological_sort import stable_topological_sort


class MigrationAutodetector:
    """
    Take a pair of ProjectStates and compare them to see what the first would
    need doing to make it match the second (the second usually being the
    project's current state).

    Note that this naturally operates on entire projects at a time,
    as it's likely that changes interact (for example, you can't
    add a ForeignKey without having a migration to add the table it
    depends on first). A user interface may offer single-app usage
    if it wishes, with the caveat that it may not always be possible.
    """

    def __init__(self, from_state, to_state, questioner=None):
        self.from_state = from_state
        self.to_state = to_state
        self.questioner = questioner or MigrationQuestioner()
        self.existing_apps = {app for app, model in from_state.models}

    def changes(self, graph, trim_to_apps=None, convert_apps=None, migration_name=None):
        """
        Main entry point to produce a list of applicable changes.
        Take a graph to base names on and an optional set of apps
        to try and restrict to (restriction is not guaranteed)
        """
        changes = self._detect_changes(convert_apps, graph)
        changes = self.arrange_for_graph(changes, graph, migration_name)
        if trim_to_apps:
            changes = self._trim_to_apps(changes, trim_to_apps)
        return changes

    def deep_deconstruct(self, obj):
        """
        Recursive deconstruction for a field and its arguments.
        Used for full comparison for rename/alter; sometimes a single-level
        deconstruction will not compare correctly.
        """
        if isinstance(obj, list):
            return [self.deep_deconstruct(value) for value in obj]
        elif isinstance(obj, tuple):
            return tuple(self.deep_deconstruct(value) for value in obj)
        elif isinstance(obj, dict):
            return {
                key: self.deep_deconstruct(value)
                for key, value in obj.items()
            }
        elif isinstance(obj, functools.partial):
            return (obj.func, self.deep_deconstruct(obj.args), self.deep_deconstruct(obj.keywords))
        elif isinstance(obj, COMPILED_REGEX_TYPE):
            return RegexObject(obj)
        elif isinstance(obj, type):
            # If this is a type that implements 'deconstruct' as an instance method,
            # avoid treating this as being deconstructible itself - see #22951
            return obj
        elif hasattr(obj, 'deconstruct'):
            deconstructed = obj.deconstruct()
            if isinstance(obj, models.Field):
                # we have a field which also returns a name
                deconstructed = deconstructed[1:]
            path, args, kwargs = deconstructed
            return (
                path,
                [self.deep_deconstruct(value) for value in args],
                {
                    key: self.deep_deconstruct(value)
                    for key, value in kwargs.items()
                },
            )
        else:
            return obj

    def only_relation_agnostic_fields(self, fields):
        """
        Return a definition of the fields that ignores field names and
        what related fields actually relate to. Used for detecting renames (as,
        of course, the related fields change during renames).
        """
        fields_def = []
        for name, field in sorted(fields):
            deconstruction = self.deep_deconstruct(field)
            if field.remote_field and field.remote_field.model:
                del deconstruction[2]['to']
            fields_def.append(deconstruction)
        return fields_def

    def _detect_changes(self, convert_apps=None, graph=None):
        """
        Return a dict of migration plans which will achieve the
        change from from_state to to_state. The dict has app labels
        as keys and a list of migrations as values.

        The resulting migrations aren't specially named, but the names
        do matter for dependencies inside the set.

        convert_apps is the list of apps to convert to use migrations
        (i.e. to make initial migrations for, in the usual case)

        graph is an optional argument that, if provided, can help improve
        dependency generation and avoid potential circular dependencies.
        """
        # The first phase is generating all the operations for each app
        # and gathering them into a big per-app list.
        # Then go through that list, order it, and split into migrations to
        # resolve dependencies caused by M2Ms and FKs.
        self.generated_operations = {}
        self.altered_indexes = {}

        # Prepare some old/new state and model lists, separating
        # proxy models and ignoring unmigrated apps.
        self.old_apps = self.from_state.concrete_apps
        self.new_apps = self.to_state.apps
        self.old_model_keys = []
        self.old_proxy_keys = []
        self.old_unmanaged_keys = []
        self.new_model_keys = []
        self.new_proxy_keys = []
        self.new_unmanaged_keys = []
        for al, mn in sorted(self.from_state.models):
            model = self.old_apps.get_model(al, mn)
            if not model._meta.managed:
                self.old_unmanaged_keys.append((al, mn))
            elif al not in self.from_state.real_apps:
                if model._meta.proxy:
                    self.old_proxy_keys.append((al, mn))
                else:
                    self.old_model_keys.append((al, mn))

        for al, mn in sorted(self.to_state.models):
            model = self.new_apps.get_model(al, mn)
            if not model._meta.managed:
                self.new_unmanaged_keys.append((al, mn))
            elif (
                al not in self.from_state.real_apps or
                (convert_apps and al in convert_apps)
            ):
                if model._meta.proxy:
                    self.new_proxy_keys.append((al, mn))
                else:
                    self.new_model_keys.append((al, mn))

        # Renames have to come first
        self.generate_renamed_models()

        # Prepare lists of fields and generate through model map
        self._prepare_field_lists()
        self._generate_through_model_map()

        # Generate non-rename model operations
        self.generate_deleted_models()
        self.generate_created_models()
        self.generate_deleted_proxies()
        self.generate_created_proxies()
        self.generate_altered_options()
        self.generate_altered_managers()

        # Create the altered indexes and store them in self.altered_indexes.
        # This avoids the same computation in generate_removed_indexes()
        # and generate_added_indexes().
        self.create_altered_indexes()
        # Generate index removal operations before field is removed
        self.generate_removed_indexes()
        # Generate field operations
        self.generate_renamed_fields()
        self.generate_removed_fields()
        self.generate_added_fields()
        self.generate_altered_fields()
        self.generate_altered_unique_together()
        self.generate_altered_index_together()
        self.generate_added_indexes()
        self.generate_altered_db_table()
        self.generate_altered_order_with_respect_to()

        self._sort_migrations()
        self._build_migration_list(graph)
        self._optimize_migrations()

        return self.migrations

    def _prepare_field_lists(self):
        """
        Prepare field lists and a list of the fields that used through models
        in the old state so dependencies can be made from the through model
        deletion to the field that uses it.
        """
        self.kept_model_keys = set(self.old_model_keys).intersection(self.new_model_keys)
        self.kept_proxy_keys = set(self.old_proxy_keys).intersection(self.new_proxy_keys)
        self.kept_unmanaged_keys = set(self.old_unmanaged_keys).intersection(self.new_unmanaged_keys)
        self.through_users = {}
        self.old_field_keys = set()
        self.new_field_keys = set()
        for app_label, model_name in sorted(self.kept_model_keys):
            old_model_name = self.renamed_models.get((app_label, model_name), model_name)
            old_model_state = self.from_state.models[app_label, old_model_name]
            new_model_state = self.to_state.models[app_label, model_name]
            self.old_field_keys.update((app_label, model_name, x) for x, y in old_model_state.fields)
            self.new_field_keys.update((app_label, model_name, x) for x, y in new_model_state.fields)

    def _generate_through_model_map(self):
        """Through model map generation."""
        for app_label, model_name in sorted(self.old_model_keys):
            old_model_name = self.renamed_models.get((app_label, model_name), model_name)
            old_model_state = self.from_state.models[app_label, old_model_name]
            for field_name, field in old_model_state.fields:
                old_field = self.old_apps.get_model(app_label, old_model_name)._meta.get_field(field_name)
                if (hasattr(old_field, "remote_field") and getattr(old_field.remote_field, "through", None) and
                        not old_field.remote_field.through._meta.auto_created):
                    through_key = (
                        old_field.remote_field.through._meta.app_label,
                        old_field.remote_field.through._meta.model_name,
                    )
                    self.through_users[through_key] = (app_label, old_model_name, field_name)

    def _build_migration_list(self, graph=None):
        """
        Chop the lists of operations up into migrations with dependencies on
        each other. Do this by going through an app's list of operations until
        one is found that has an outgoing dependency that isn't in another
        app's migration yet (hasn't been chopped off its list). Then chop off
        the operations before it into a migration and move onto the next app.
        If the loops completes without doing anything, there's a circular
        dependency (which _should_ be impossible as the operations are
        all split at this point so they can't depend and be depended on).
        """
        self.migrations = {}
        num_ops = sum(len(x) for x in self.generated_operations.values())
        chop_mode = False
        while num_ops:
            # On every iteration, we step through all the apps and see if there
            # is a completed set of operations.
            # If we find that a subset of the operations are complete we can
            # try to chop it off from the rest and continue, but we only
            # do this if we've already been through the list once before
            # without any chopping and nothing has changed.
            for app_label in sorted(self.generated_operations):
                chopped = []
                dependencies = set()
                for operation in list(self.generated_operations[app_label]):
                    deps_satisfied = True
                    operation_dependencies = set()
                    for dep in operation._auto_deps:
                        is_swappable_dep = False
                        if dep[0] == "__setting__":
                            # We need to temporarily resolve the swappable dependency to prevent
                            # circular references. While keeping the dependency checks on the
                            # resolved model we still add the swappable dependencies.
                            # See #23322
                            resolved_app_label, resolved_object_name = getattr(settings, dep[1]).split('.')
                            original_dep = dep
                            dep = (resolved_app_label, resolved_object_name.lower(), dep[2], dep[3])
                            is_swappable_dep = True
                        if dep[0] != app_label and dep[0] != "__setting__":
                            # External app dependency. See if it's not yet
                            # satisfied.
                            for other_operation in self.generated_operations.get(dep[0], []):
                                if self.check_dependency(other_operation, dep):
                                    deps_satisfied = False
                                    break
                            if not deps_satisfied:
                                break
                            else:
                                if is_swappable_dep:
                                    operation_dependencies.add((original_dep[0], original_dep[1]))
                                elif dep[0] in self.migrations:
                                    operation_dependencies.add((dep[0], self.migrations[dep[0]][-1].name))
                                else:
                                    # If we can't find the other app, we add a first/last dependency,
                                    # but only if we've already been through once and checked everything
                                    if chop_mode:
                                        # If the app already exists, we add a dependency on the last migration,
                                        # as we don't know which migration contains the target field.
                                        # If it's not yet migrated or has no migrations, we use __first__
                                        if graph and graph.leaf_nodes(dep[0]):
                                            operation_dependencies.add(graph.leaf_nodes(dep[0])[0])
                                        else:
                                            operation_dependencies.add((dep[0], "__first__"))
                                    else:
                                        deps_satisfied = False
                    if deps_satisfied:
                        chopped.append(operation)
                        dependencies.update(operation_dependencies)
                        self.generated_operations[app_label] = self.generated_operations[app_label][1:]
                    else:
                        break
                # Make a migration! Well, only if there's stuff to put in it
                if dependencies or chopped:
                    if not self.generated_operations[app_label] or chop_mode:
                        subclass = type("Migration", (Migration,), {"operations": [], "dependencies": []})
                        instance = subclass("auto_%i" % (len(self.migrations.get(app_label, [])) + 1), app_label)
                        instance.dependencies = list(dependencies)
                        instance.operations = chopped
                        instance.initial = app_label not in self.existing_apps
                        self.migrations.setdefault(app_label, []).append(instance)
                        chop_mode = False
                    else:
                        self.generated_operations[app_label] = chopped + self.generated_operations[app_label]
            new_num_ops = sum(len(x) for x in self.generated_operations.values())
            if new_num_ops == num_ops:
                if not chop_mode:
                    chop_mode = True
                else:
                    raise ValueError("Cannot resolve operation dependencies: %r" % self.generated_operations)
            num_ops = new_num_ops

    def _sort_migrations(self):
        """
        Reorder to make things possible. Reordering may be needed so FKs work
        nicely inside the same app.
        """
        for app_label, ops in sorted(self.generated_operations.items()):
            # construct a dependency graph for intra-app dependencies
            dependency_graph = {op: set() for op in ops}
            for op in ops:
                for dep in op._auto_deps:
                    if dep[0] == app_label:
                        for op2 in ops:
                            if self.check_dependency(op2, dep):
                                dependency_graph[op].add(op2)

            # we use a stable sort for deterministic tests & general behavior
            self.generated_operations[app_label] = stable_topological_sort(ops, dependency_graph)

    def _optimize_migrations(self):
        # Add in internal dependencies among the migrations
        for app_label, migrations in self.migrations.items():
            for m1, m2 in zip(migrations, migrations[1:]):
                m2.dependencies.append((app_label, m1.name))

        # De-dupe dependencies
        for app_label, migrations in self.migrations.items():
            for migration in migrations:
                migration.dependencies = list(set(migration.dependencies))

        # Optimize migrations
        for app_label, migrations in self.migrations.items():
            for migration in migrations:
                migration.operations = MigrationOptimizer().optimize(migration.operations, app_label=app_label)

    def check_dependency(self, operation, dependency):
        """
        Return True if the given operation depends on the given dependency,
        False otherwise.
        """
        # Created model
        if dependency[2] is None and dependency[3] is True:
            return (
                isinstance(operation, operations.CreateModel) and
                operation.name_lower == dependency[1].lower()
            )
        # Created field
        elif dependency[2] is not None and dependency[3] is True:
            return (
                (
                    isinstance(operation, operations.CreateModel) and
                    operation.name_lower == dependency[1].lower() and
                    any(dependency[2] == x for x, y in operation.fields)
                ) or
                (
                    isinstance(operation, operations.AddField) and
                    operation.model_name_lower == dependency[1].lower() and
                    operation.name_lower == dependency[2].lower()
                )
            )
        # Removed field
        elif dependency[2] is not None and dependency[3] is False:
            return (
                isinstance(operation, operations.RemoveField) and
                operation.model_name_lower == dependency[1].lower() and
                operation.name_lower == dependency[2].lower()
            )
        # Removed model
        elif dependency[2] is None and dependency[3] is False:
            return (
                isinstance(operation, operations.DeleteModel) and
                operation.name_lower == dependency[1].lower()
            )
        # Field being altered
        elif dependency[2] is not None and dependency[3] == "alter":
            return (
                isinstance(operation, operations.AlterField) and
                operation.model_name_lower == dependency[1].lower() and
                operation.name_lower == dependency[2].lower()
            )
        # order_with_respect_to being unset for a field
        elif dependency[2] is not None and dependency[3] == "order_wrt_unset":
            return (
                isinstance(operation, operations.AlterOrderWithRespectTo) and
                operation.name_lower == dependency[1].lower() and
                (operation.order_with_respect_to or "").lower() != dependency[2].lower()
            )
        # Field is removed and part of an index/unique_together
        elif dependency[2] is not None and dependency[3] == "foo_together_change":
            return (
                isinstance(operation, (operations.AlterUniqueTogether,
                                       operations.AlterIndexTogether)) and
                operation.name_lower == dependency[1].lower()
            )
        # Unknown dependency. Raise an error.
        else:
            raise ValueError("Can't handle dependency %r" % (dependency, ))

    def add_operation(self, app_label, operation, dependencies=None, beginning=False):
        # Dependencies are (app_label, model_name, field_name, create/delete as True/False)
        operation._auto_deps = dependencies or []
        if beginning:
            self.generated_operations.setdefault(app_label, []).insert(0, operation)
        else:
            self.generated_operations.setdefault(app_label, []).append(operation)

    def swappable_first_key(self, item):
        """
        Place potential swappable models first in lists of created models (only
        real way to solve #22783).
        """
        try:
            model = self.new_apps.get_model(item[0], item[1])
            base_names = [base.__name__ for base in model.__bases__]
            string_version = "%s.%s" % (item[0], item[1])
            if (
                model._meta.swappable or
                "AbstractUser" in base_names or
                "AbstractBaseUser" in base_names or
                settings.AUTH_USER_MODEL.lower() == string_version.lower()
            ):
                return ("___" + item[0], "___" + item[1])
        except LookupError:
            pass
        return item

    def generate_renamed_models(self):
        """
        Find any renamed models, generate the operations for them, and remove
        the old entry from the model lists. Must be run before other
        model-level generation.
        """
        self.renamed_models = {}
        self.renamed_models_rel = {}
        added_models = set(self.new_model_keys) - set(self.old_model_keys)
        for app_label, model_name in sorted(added_models):
            model_state = self.to_state.models[app_label, model_name]
            model_fields_def = self.only_relation_agnostic_fields(model_state.fields)

            removed_models = set(self.old_model_keys) - set(self.new_model_keys)
            for rem_app_label, rem_model_name in removed_models:
                if rem_app_label == app_label:
                    rem_model_state = self.from_state.models[rem_app_label, rem_model_name]
                    rem_model_fields_def = self.only_relation_agnostic_fields(rem_model_state.fields)
                    if model_fields_def == rem_model_fields_def:
                        if self.questioner.ask_rename_model(rem_model_state, model_state):
                            self.add_operation(
                                app_label,
                                operations.RenameModel(
                                    old_name=rem_model_state.name,
                                    new_name=model_state.name,
                                )
                            )
                            self.renamed_models[app_label, model_name] = rem_model_name
                            renamed_models_rel_key = '%s.%s' % (rem_model_state.app_label, rem_model_state.name)
                            self.renamed_models_rel[renamed_models_rel_key] = '%s.%s' % (
                                model_state.app_label,
                                model_state.name,
                            )
                            self.old_model_keys.remove((rem_app_label, rem_model_name))
                            self.old_model_keys.append((app_label, model_name))
                            break

    def generate_created_models(self):
        """
        Find all new models (both managed and unmanaged) and make create
        operations for them as well as separate operations to create any
        foreign key or M2M relationships (these are optimized later, if
        possible).

        Defer any model options that refer to collections of fields that might
        be deferred (e.g. unique_together, index_together).
        """
        old_keys = set(self.old_model_keys).union(self.old_unmanaged_keys)
        added_models = set(self.new_model_keys) - old_keys
        added_unmanaged_models = set(self.new_unmanaged_keys) - old_keys
        all_added_models = chain(
            sorted(added_models, key=self.swappable_first_key, reverse=True),
            sorted(added_unmanaged_models, key=self.swappable_first_key, reverse=True)
        )
        for app_label, model_name in all_added_models:
            model_state = self.to_state.models[app_label, model_name]
            model_opts = self.new_apps.get_model(app_label, model_name)._meta
            # Gather related fields
            related_fields = {}
            primary_key_rel = None
            for field in model_opts.local_fields:
                if field.remote_field:
                    if field.remote_field.model:
                        if field.primary_key:
                            primary_key_rel = field.remote_field.model
                        elif not field.remote_field.parent_link:
                            related_fields[field.name] = field
                    # through will be none on M2Ms on swapped-out models;
                    # we can treat lack of through as auto_created=True, though.
                    if (getattr(field.remote_field, "through", None) and
                            not field.remote_field.through._meta.auto_created):
                        related_fields[field.name] = field
            for field in model_opts.local_many_to_many:
                if field.remote_field.model:
                    related_fields[field.name] = field
                if getattr(field.remote_field, "through", None) and not field.remote_field.through._meta.auto_created: