def get_app(app_label, emptyOK=False):
    """Return the app with the given label.

    This returns the app from the app registry on Django >= 1.7, and from
    the old-style cache on Django < 1.7.

        app_label (str):
            The label for the app containing the models.

        emptyOK (bool, optional):
            Impacts the return value if the app has no models in it.

    Returns:
        module:
        The app module, if available.

        If the app module is available, but the models module is not and
        ``emptyOK`` is set, this will return ``None``. Otherwise, if modules
        are not available, this will raise
        :py:exc:`~django.core.exceptions.ImproperlyConfigured`.

    Raises:
        django.core.exceptions.ImproperlyConfigured:
            The app module was not found, or it was found but a models module
            was not and ``emptyOK`` was ``False``.
    """
    if apps:
        # Django >= 1.7
        try:
            models_module = apps.get_app_config(app_label).models_module
        except LookupError as e:
            # Convert this to an ImproperlyConfigured.
            raise ImproperlyConfigured(*e.args)

        if models_module is None and not emptyOK:
            # This is the exact error that Django 1.6 provided.
            raise ImproperlyConfigured(
                'App with label %s is missing a models.py module.'
                % app_label)

        return models_module
    else:
        # Django < 1.7
        return cache.get_app(app_label, emptyOK) class Evolution(models.Model):
    version = models.ForeignKey(Version,
                                related_name='evolutions',
                                on_delete=models.CASCADE)
    app_label = models.CharField(max_length=200)
    label = models.CharField(max_length=100)

    def __str__(self):
        return 'Evolution %s, applied to %s' % (self.label, self.app_label)

    class Meta:
        db_table = 'django_evolution'
        ordering = ('id',) class Version(models.Model):
    signature = SignatureField()
    when = models.DateTimeField(default=now)

    objects = VersionManager()

    def is_hinted(self):
        """Return whether this is a hinted version.

        Hinted versions store a signature without any accompanying evolutions.

        Returns:
            bool:
            ``True`` if this is a hinted evolution. ``False`` if it's based on
            explicit evolutions.
        """
        return not self.evolutions.exists()

    def __str__(self):
        if self.is_hinted():
            return 'Hinted version, updated on %s' % self.when

        return 'Stored version, updated on %s' % self.when

    class Meta:
        ordering = ('-when',)
        db_table = 'django_project_version' class MigrationsTestsMixin(object):
    """Mixin for test suites that work with migrations.

    This will ensure that no test migrations are marked as applied before
    the tests run.
    """

    needs_evolution_models = True

    def setUp(self):
        super(MigrationsTestsMixin, self).setUp()

        if supports_migrations:
            connection = connections[DEFAULT_DB_ALIAS]

            for app_label in ('tests', 'migrations_app', 'migrations_app2'):
                unrecord_applied_migrations(connection=connection,
                                            app_label=app_label) class TestCase(DjangoTestCase):
    """Base class for all Django Evolution test cases."""

    ws_re = re.compile(r'\s+')

    needs_evolution_models = False

    # Allow for diffs for large dictionary structures, to help debug
    # signature failures.
    maxDiff = 10000

    # The list of databases we may test against, required by Django 2.2+.
    databases = ['default', 'db_multi']

    default_database_name = 'default'
    sql_mapping_key = None

    builtin_test_app_labels = [
        'evolution_deps_app',
        'evolutions_app',
        'evolutions_app2',
        'migrations_app',
        'migrations_app2',
        'tests',
    ]

    # Override some internal functions on Django's TestCase to avoid setting
    # up transactions. We won't bother documenting these, since we're just
    # trying to turn off logic.
    if django.VERSION[:2] >= (1, 8):
        # Django >= 1.8
        @classmethod
        def _enter_atomics(cls):
            return

        @classmethod
        def _rollback_atomics(cls, atomics):
            return
    else:
        # Django <= 1.7
        def _fixture_setup(self):
            return

        def _fixture_teardown(self):
            return

    def setUp(self):
        super(TestCase, self).setUp()

        # If these are in the database, we need to delete them so we don't
        # carry signatures between tests.
        try:
            Evolution.objects.all().delete()
            Version.objects.all().delete()
        except Exception:
            pass

        # If the test case indicates it needs the Evolution and Version
        # models pre-populated, then do that now.
        if self.needs_evolution_models:
            self.ensure_evolution_models()

    def tearDown(self):
        super(TestCase, self).tearDown()

        self.ensure_deleted_apps()
        unregister_test_models()

    def shortDescription(self):
        """Returns the description of the current test.

        This changes the default behavior to replace all newlines with spaces,
        allowing a test description to span lines. It should still be kept
        short, though.
        """
        doc = self._testMethodDoc

        if doc is not None:
            doc = doc.split('\n\n', 1)[0]
            doc = self.ws_re.sub(' ', doc).strip()

        return doc

    def ensure_evolution_models(self):
        """Create the Evolution and Version models if missing."""
        Evolver()
        assert Version.objects.exists()

    def ensure_deleted_apps(self, app_labels=None):
        """Ensure an app's models and evolutions aren't in the database.

        Args:
            app_labels (list of unicode, optional):
                An explicit list of app labels to delete. This defaults
                to the built-in list of test app labels.
        """
        if app_labels is None:
            app_labels = self.builtin_test_app_labels

        # Do this one-by-one, since we might have some but not all of the
        # apps in the database.
        sql = []

        for app_label in reversed(app_labels):
            try:
                app = get_app(app_label)
            except Exception:
                # This wasn't registered, so we can skip it.
                continue

            sql += sql_delete(app)

        if sql:
            execute_test_sql(sql)

        Evolution.objects.filter(app_label__in=app_labels).delete()

    def ensure_evolved_apps(self, apps):
        """Ensure an app's models and evolutions are applied to the database.

        Args:
            apps (list of module):
                The app modules to evolve.
        """
        evolver = Evolver()

        for app in apps:
            evolver.queue_evolve_app(app)

        evolver.evolve()

    def record_evolutions(self, version, evolutions,
                          database=DEFAULT_DB_ALIAS):
        """Record evolutions in the database.

        This is a convenience around creating and saving `Evolution` models.

        Args:
            version (django_evolution.models.Version):
                The version to associate the evolutions with.

            evolutions (list of tuple):
                The list of evolutions to store. Each item is a tuple in
                ``(app_label, label)`` form.

            database (unicode, optional):
                The name of the database to save these on.
        """
        Evolution.objects.using(database).bulk_create([
            Evolution(version=version,
                      app_label=app_label,
                      label=label)
            for app_label, label in evolutions
        ])

    def record_applied_migrations(self, migration_targets,
                                  database=DEFAULT_DB_ALIAS):
        """Record applied migrations in the database.

        This is a convenience around creating a migration list and then
        recording it in the database.

        Args:
            migration_targets (list of tuple):
                The list of migration targets to store. Each item is a tuple
                in ``(app_label, label)`` form.

            database (unicode, optional):
                The name of the database to save these on.
        """
        assert supports_migrations

        migration_list = MigrationList()
        migration_list.add_migration_targets(migration_targets)

        record_applied_migrations(connection=connections[database],
                                  migrations=migration_list)

    def get_sql_mapping(self, name, sql_mappings_key=None, db_name=None):
        """Return the SQL for the given mapping name and database.

        Args:
            name (unicode):
                The registered name in the list of SQL mappings for this test
                suite and database.

            sql_mappings_key (unicode, optional):
                The key identifying the SQL mappings. This defaults to
                :py:attr:`sql_mapping_key`.

            db_name (unicode, optional):
                The name of the database to return SQL mappings for.

        Returns:
            list of unicode:
            The resulting list of SQL statements.

        Raises:
            ValueError:
                The provided name is not valid.
        """
        sql_mappings_key = sql_mappings_key or self.sql_mapping_key
        assert sql_mappings_key

        db_name = db_name or self.default_database_name
        assert db_name

        sql_mappings = get_sql_mappings(mapping_key=sql_mappings_key,
                                        db_name=db_name)

        try:
            sql = sql_mappings[name]
        except KeyError:
            raise ValueError('"%s" is not a valid SQL mapping name.'
                             % name)

        if isinstance(sql, six.text_type):
            sql = sql.splitlines()

        return sql

    def assertEvolutionsEqual(self, evolutions, expected_evolutions):
        """Assert that a list of evolutions models match expectations.

        Args:
            evolutions (list of django_evolution.models.Evolution):
                The list of evolution models.

            expected_evolutions (list of tuple):
                A list of evolution information to compare against the models.
                Each item is a tuple in ``(app_label, label)`` form.

        Raises:
            AssertionError:
                The lists do not match.
        """
        self.assertEqual(
            [
                (evolution.app_label, evolution.label)
                for evolution in evolutions
            ],
            expected_evolutions)

    def assertAppliedEvolutions(self, expected_evolutions, version=None,
                                database=DEFAULT_DB_ALIAS):
        """Assert that applied evolutions match expectations.

        Args:
            expected_evolutions (list of tuple):
                A list of evolution information to compare against the models.
                Each item is a tuple in ``(app_label, label)`` form.

            version (django_evolution.models.Version, optional):
                The stored project version that the evolutions must be
                associated with. If not provided, all evolutions in the
                database will be used.

            database (unicode, optional):
                The name of the database to query evolutions against. This
                is only used if ``version`` is not provided.

        Raises:
            AssertionError:
                The lists do not match.
        """
        if version is None:
            queryset = Evolution.objects.using(database)
        else:
            queryset = version.evolutions.all()

        applied_evolutions = set(queryset.values_list('app_label', 'label'))

        for app_label, name in expected_evolutions:
            self.assertIn((app_label, name), applied_evolutions)

    def assertAppliedMigrations(self, expected_migration_targets,
                                database=DEFAULT_DB_ALIAS):
        """Assert that applied migrations match expectations.

        Args:
            expected_migration_targets (list of tuple):
                A list of migration targets to compare against the applied
                migrations. Each item is a tuple in ``(app_label, name)``
                form.

            database (unicode, optional):
                The name of the database to query appliedm migrations against.

        Raises:
            AssertionError:
                The lists do not match.
        """
        applied_migrations = MigrationList.from_database(connections[database])

        for app_label, name in expected_migration_targets:
            self.assertTrue(applied_migrations.has_migration_info(
                app_label=app_label,
                name=name))

    def assertSQLMappingEqual(self, sql, sql_mapping_name,
                              sql_mappings_key=None, database=None):
        """Assert generated SQL against database-specific mapped test SQL.

        This will output the provided generated SQL and the expectation test
        SQL mapped by the given key and optional database name, for debugging,
        and will then compare the contents of both.

        The expected SQL may contain regexes, which are used for comparing
        against generated SQL that may depend on some dynamic value pulled from
        the database). If found, the pattern in the regex will be applied to
        the corresponding generated SQL to determine if there's a match. Other
        lines will be compared directly.

        If any part of the SQL does not match, a diff will be shown in the
        test output.

        Args:
            sql (list of unicode):
                The list of generated SQL statements.

            sql_mapping_name (unicode):
                The mapping name in the database-specific test data to compare
                against.

            sql_mappings_key (unicode, optional):
                The key identifying the SQL mappings. This defaults to
                :py:attr:`sql_mapping_key`.

            database (unicode, optional):
                An explicit database name to use for resolving
                ``sql_mapping_name``.

        Raises:
            AssertionError:
                The generated and expected SQL did not match.
        """
        if database is None:
            database = DEFAULT_DB_ALIAS

        # Normalize the generated and expected SQL so that we are
        # guaranteed to have a list with one item per line.
        try:
            generated_sql = '\n'.join(sql).splitlines()
        except TypeError:
            # This probably has an entry that isn't normalized to a flat list
            # of strings. Do that now.
            from django_evolution.utils.sql import SQLExecutor

            with SQLExecutor(database) as sql_executor:
                sql = sql_executor.run_sql(sql,
                                           capture=True,
                                           execute=False)

            generated_sql = '\n'.join(sql).splitlines()

        expected_sql = self.get_sql_mapping(name=sql_mapping_name,
                                            sql_mappings_key=sql_mappings_key,
                                            db_name=database)

        # Output the statements one-by-one, to help with diagnosing
        # differences.

        print()
        print("** Comparing SQL against '%s'" % sql_mapping_name)
        print('** Generated:')
        print()

        for line in generated_sql:
            print('    %s' % line)

        print()
        print('** Expected:')
        print()

        has_regex = False

        for line in expected_sql:
            if (not isinstance(line, six.text_type) and
                hasattr(line, 'pattern')):
                line = '/%s/' % line.pattern
                has_regex = True

            print('    %s' % line)

        print()

        if has_regex:
            # We can't compare directly at first, so let's see if things
            # are otherwise a match and then, if we spot anything wrong,
            # we'll just do an assertListEqual to get detailed output.
            match = (len(generated_sql) == len(expected_sql))

            if match:
                for gen_line, expected_line in zip(generated_sql,
                                                   expected_sql):
                    if ((isinstance(expected_line, six.text_type) and
                         gen_line != expected_line) or
                        (hasattr(line, 'pattern') and
                         not line.match(gen_line))):
                        match = False
                        break

            if not match:
                # Now show that detailed output.
                self.assertListEqual(generated_sql, expected_sql)
        else:
            # Compare as lists, so that we can better spot inconsistencies.
            self.assertListEqual(generated_sql, expected_sql) def _build_requires_support_decorator(flag, skip_message):
    def _decorator(func):
        def _wrapper(*args, **kwargs): class EvolutionsAppTestModel(models.Model):
    char_field = models.CharField(max_length=10, null=True)
    char_field2 = models.CharField(max_length=20, null=True) class EvolutionsApp2TestModel(models.Model):
    char_field = models.CharField(max_length=10)
    fkey = models.ForeignKey(EvolutionsAppTestModel,
                             on_delete=models.CASCADE,
                             null=True) class EvolutionGraph(DependencyGraph):
    """A graph tracking dependencies between migrations and evolutions.

    This is used to model the relationships between all configured migrations
    and evolutions, and to generate batches of consecutive migrations or
    evolutions that can be applied at once.

    Dependencies can be added at any time, and are only applied once the graph
    is finalized. This allows nodes to be added after a dependency referring
    to them is added.

    Version Added:
        2.1
    """

    #: An anchor node.
    #:
    #: These are internal, and are used for clustered dependency management.
    NODE_TYPE_ANCHOR = 'anchor'

    #: A node that results in model creation.
    NODE_TYPE_CREATE_MODEL = 'create-model'

    #: A node that results in applying a single evolution.
    NODE_TYPE_EVOLUTION = 'evolution'

    #: A node that results in applying a single migration.
    NODE_TYPE_MIGRATION = 'migration'

    def __init__(self, *args, **kwargs):
        """Initialize the graph.

        Args:
            *args (tuple):
                Positional arguments for the parent.

            **kwargs (dict):
                Keyword arguments for the parent.
        """
        super(EvolutionGraph, self).__init__(*args, **kwargs)

        self.process_evolution_deps = True
        self.process_migration_deps = supports_migrations

        self._app_evolution_nodes = {}

    def add_evolutions(self, app, evolutions=[], new_models=[],
                       extra_state={}):
        """Add a list of evolutions for a given app.

        Each evolution will gets its own node, and pending dependencies will
        be recorded to ensure the evolutions are applied in the correct order.

        A special ``__first__`` anchor node will be added before the sequence
        of evolutions, and a ``__last__`` node will be added after. This allows
        evolutions to easily reference another app's list of evolutions
        relative to the start or end of a list. It's used only internally.

        Args:
            app (module):
                The app module the evolutions apply to.

            evolutions (list of django_evolution.models.Evolution, optional):
                The list of evolutions to add to the graph. This may be an
                empty list if there are no evolutions but there are new
                models to create.

            new_models (list of type, optional):
                The list of database model classes to create for the app.

            extra_state (dict, optional):
                Extra state to set in each evolution node.
        """
        app_label = get_app_label(app)
        app_deps = get_evolution_app_dependencies(app)

        nodes = []

        # Add the leading anchor node.
        node = self.add_node(
            key='evolution:%s:__first__' % app_label,
            state={
                'anchor': True,
                'app': app,
            })
        prev_node = node

        if app_deps:
            self._add_evolution_node_after_deps(node, app_deps)

        # If we're creating models, add nodes for that.
        for model in new_models:
            node = self._add_create_model(app=app,
                                          model=model,
                                          extra_state=extra_state)
            self.add_dependency(node_key=node.key,
                                dep_node_key=prev_node.key)

            nodes.append(node)
            prev_node = node

        # Add a node for each evolution.
        for evolution in evolutions:
            node = self._add_evolution(app=app,
                                       evolution=evolution,
                                       extra_state=extra_state)
            self.add_dependency(node_key=node.key,
                                dep_node_key=prev_node.key)

            nodes.append(node)
            prev_node = node

        # Add the trailing anchor node.
        node = self.add_node(
            key='evolution:%s:__last__' % app_label,
            state={
                'anchor': True,
                'app': app,
            })
        self.add_dependency(node_key=node.key,
                            dep_node_key=prev_node.key)

        if app_deps:
            self._add_evolution_node_before_deps(node, app_deps)

        self._app_evolution_nodes.setdefault(app, []).extend(nodes)

    def add_migration_plan(self, migration_plan, migration_graph):
        """Add a migration plan to the graph.

        Each migration in the plan will gets its own node, and pending
        dependencies will be recorded to ensure the migrations are applied in
        the order already computed for the plan.

        Args:
            migration_plan (list of tuple):
                The computed migration plan to add to the graph.

            migration_graph (django.db.migrations.graph.MigrationGraph):
                The computed migration graph, used to reference computed
                dependencies.
        """
        assert supports_migrations

        has_node_map = hasattr(migration_graph, 'node_map')

        for plan_item in migration_plan:
            node = self._add_migration_plan_item(plan_item)
            migration_target = node.state['migration_target']

            if has_node_map:
                # Django >= 1.8
                parents = migration_graph.node_map[migration_target].parents
                deps = (
                    migration_graph.nodes[dep_node.key]
                    for dep_node in parents
                )
            else:
                # Django == 1.7
                deps = migration_graph.dependencies.get(migration_target, [])

            for dep in deps:
                self.add_dependency(node_key=node.key,
                                    dep_node_key=self._make_migration_key(dep))

    def mark_evolutions_applied(self, app, evolution_labels):
        """Mark one or more evolutions as applied.

        This will remove any pending dependencies referencing these evolutions
        from the graph.

        Args:
            app (module):
                The app module the evolutions apply to.

            evolution_labels (list of unicode):
                The list of evolutions labels to mark as applied.
        """
        app_label = get_app_label(app)

        if app not in self._app_evolution_nodes:
            # There aren't any evolution nodes for this app, so let's also
            # get rid of any dependencies to the anchors.
            evolution_labels += ['__first__', '__last__']

        self.remove_dependencies({
            self._make_evolution_key((app_label, evolution_label))
            for evolution_label in evolution_labels
        })

    def mark_migrations_applied(self, migrations):
        """Mark one or more migrations as applied.

        This will remove any pending dependencies referencing these migrations
        from the graph.

        Args:
            migrations (django_evolution.utils.migrations.MigrationList):
                The list of migrations to mark as applied.
        """
        self.remove_dependencies(set(
            self._make_migration_key(migration_target)
            for migration_target in migrations.to_targets()
        ))

    def iter_batches(self):
        """Iterate through batches of consecutive evolutions and migrations.

        The nodes will be iterated in dependency order, with each batch
        containing a sequence of either evolutions or migrations that can be
        applied at once.

        Yields:
            tuple:
            A 2-tuple containing:

            1. The batch type (one of :py:attr:`NODE_TYPE_CREATE_MODEL`,
               :py:attr:`NODE_TYPE_EVOLUTION`, or
               :py:attr:`NODE_TYPE_MIGRATION`).
            2. A list of :py:class:`Node` instances.
        """
        batch_nodes = []
        batch_type = None

        for node in self.get_ordered():
            if node.state.get('anchor'):
                continue

            node_type = node.state['type']

            if node_type != batch_type:
                if batch_nodes:
                    yield batch_type, batch_nodes

                batch_nodes = []
                batch_type = node_type

            batch_nodes.append(node)

        if batch_nodes:
            yield batch_type, batch_nodes

    def _add_create_model(self, app, model, extra_state={}):
        """Add a node for creating a model.

        Args:
            app (module):
                The app module the evolution applies to.

            model (type):
                The model class to create.

            extra_state (dict, optional):
                Extra state to set in the evolution node.

        Returns:
            Node:
            The resulting node.
        """
        key = self._make_create_model_key(get_app_label(app), model)
        node = self.add_node(
            key=key,
            state=dict({
                'app': app,
                'model': model,
                'type': self.NODE_TYPE_CREATE_MODEL,
            }, **extra_state))

        return node

    def _add_evolution(self, app, evolution, extra_state={}):
        """Add a node for an evolution.

        Node dependencies will be registered based on any evolution/migration
        dependencies defined by this evolution.

        Args:
            app (module):
                The app module the evolution applies to.

            evolution (django_evolution.models.Evolution):
                The evolution to add.

            extra_state (dict, optional):
                Extra state to set in the evolution node.

        Returns:
            Node:
            The resulting node.
        """
        key = self._make_evolution_key(evolution)
        node = self.add_node(
            key=key,
            state=dict({
                'app': app,
                'evolution': evolution,
                'type': self.NODE_TYPE_EVOLUTION,
            }, **extra_state))

        # Begin adding any dependencies between this evolution and any other
        # evolution or migration.
        deps = get_evolution_dependencies(app=app,
                                          evolution_label=evolution.label)

        if deps:
            self._add_evolution_node_before_deps(node, deps)
            self._add_evolution_node_after_deps(node, deps)

        return node

    def _add_evolution_node_before_deps(self, node, deps):
        """Add dependencies on evolutions/migrations to process before a node.

        Any dependencies in ``before_evolutions`` or ``before_migrations``
        will be registered in the graph.

        Args:
            node (Node):
                The graph node to add dependencies relative to.

            deps (dict):
                The dependencies owned by the evolution backed by this node.
        """
        # Add dependencies for any evolutions/migrations that this should
        # come before.
        key = node.key

        if self.process_evolution_deps:
            for evolution_target in deps['before_evolutions']:
                if isinstance(evolution_target, six.text_type):
                    # If only an app name is specified, then the special
                    # __first__ anchor node for the app will depend on this
                    # node.
                    evolution_target = (evolution_target, '__first__')

                self.add_dependency(
                    node_key=self._make_evolution_key(evolution_target),
                    dep_node_key=key)

        if self.process_migration_deps:
            for migration_target in deps['before_migrations']:
                self.add_dependency(
                    node_key=self._make_migration_key(migration_target),
                    dep_node_key=key)

    def _add_evolution_node_after_deps(self, node, deps):
        """Add dependencies on evolutions/migrations to process after a node.

        Any dependencies in ``after_evolutions`` or ``after_migrations``
        will be registered in the graph.

        Args:
            node (Node):
                The graph node to add dependencies relative to.

            deps (dict):
                The dependencies owned by the evolution backed by this node.
        """
        # Add dependencies for any evolutions/migrations that this should
        # come after.
        key = node.key

        if self.process_evolution_deps:
            for evolution_target in deps.get('after_evolutions', []):
                if isinstance(evolution_target, six.text_type):
                    # If only an app name is specified, then depend on the
                    # special __first__ anchor node for the app.
                    evolution_target = (evolution_target, '__last__')

                self.add_dependency(
                    node_key=key,
                    dep_node_key=self._make_evolution_key(evolution_target))

        if self.process_migration_deps:
            for migration_target in deps.get('after_migrations', []):
                self.add_dependency(
                    node_key=key,
                    dep_node_key=self._make_migration_key(migration_target))

    def _add_migration_plan_item(self, plan_item):
        """Add an item from a migration plan.

        Args:
            plan_item (tuple):
                The item from a migration plan to add.

        Returns:
            Node:
            The resulting node.
        """
        migration = plan_item[0]

        return self.add_node(
            key=self._make_migration_key(migration),
            state={
                'migration_plan_item': plan_item,
                'migration_target': (migration.app_label, migration.name),
                'type': self.NODE_TYPE_MIGRATION,
            })

    def _make_create_model_key(self, app_label, model):
        """Return a key representing a model to create.

        The key will uniquely identify the node for a model to create in the
        graph.

        Args:
            app_label (unicode):
                The app label that owns the model.

            model (django.db.models.Model):
                The model the key will represent.

        Returns:
            unicode:
            The key for the create model node.
        """
        return 'create-model:%s:%s' % (app_label, get_model_name(model))

    def _make_evolution_key(self, evolution):
        """Return a key representing an evolution.

        The key will uniquely identify the node for an evolution in the graph.
        It supports either an evolution or a tuple identifying one.

        Args:
            evolution (tuple or django_evolution.models.Evolution):
                The identifier for an evolution.

                For a tuple, this needs to be in
                ``(app_label, evolution_label)`` form.

        Returns:
            unicode:
            The key for the evolution node.

        Raises:
            TypeError:
                An invalid type was passed for ``evolution``.
        """
        if isinstance(evolution, tuple):
            assert len(evolution) == 2

            app_label, label = evolution
        elif isinstance(evolution, Evolution):
            app_label = evolution.app_label
            label = evolution.label
        else:
            raise TypeError('Invalid type %s: %s' % (type(evolution),
                                                     evolution))

        return 'evolution:%s:%s' % (app_label, label)

    def _make_migration_key(self, migration):
        """Return a key representing a migration.

        The key will uniquely identify the node for an migration in the graph.
        It supports either a migration or a tuple identifying one.

        Args:
            evolution (tuple or django.db.migrations.migration.Migration):
                The identifier for a migration.

                For a tuple, this needs to be in
                ``(app_label, migration_name)`` form.

        Returns:
            unicode:
            The key for the migration node.

        Raises:
            TypeError:
                An invalid type was passed for ``migration``.
        """
        if isinstance(migration, tuple):
            app_label, name = migration
        elif isinstance(migration, Migration):
            app_label = migration.app_label
            name = migration.name
        else:
            raise TypeError('Invalid type %s: %s' % (type(migration),
                                                     migration))

        return 'migration:%s:%s' % (app_label, name) class MigrationExecutor(DjangoMigrationExecutor):
    """Load and execute migrations.

    This is a specialization of Django's own
    :py:class:`~django.db.migrations.executor.MigrationExecutor` that allows
    for providing additional migrations not available on disk, and for
    emitting our own signals when processing migrations.
    """

    def __init__(self, connection, custom_migrations=None, signal_sender=None):
        """Initialize the executor.

        Args:
            connection (django.db.backends.base.BaseDatabaseWrapper):
                The connection to load applied migrations from.

            custom_migrations (dict, optional):
                Custom migrations not available on disk. Each key is a tuple
                of ``(app_label, migration_name)``, and each value is a
                migration.

            signal_sender (object, optional):
                A custom sender to pass when sending signals. This defaults
                to this instance.
        """
        self._signal_sender = signal_sender or self

        super(MigrationExecutor, self).__init__(
            connection=connection,
            progress_callback=self._on_progress)

        # Ideally we would be able to replace this during initialization,
        # or at the very least prevent the default one from loading from
        # disk, but it's not often that these will be constructed, so it's
        # probably fine.
        self.loader = MigrationLoader(connection=connection,
                                      custom_migrations=custom_migrations)

    def run_checks(self):
        """Perform checks on the migrations and any history.

        Raises:
            django_evolution.errors.MigrationConflictsError:
                There are conflicts between migrations loaded from disk.

            django_evolution.errors.MigrationHistoryError:
                There are unapplied dependencies to applied migrations.
        """
        # Make sure that the migration files in the tree form a proper history.
        if hasattr(self.loader, 'check_consistent_history'):
            # Django >= 1.10
            from django.db.migrations.exceptions import \
                InconsistentMigrationHistory

            try:
                self.loader.check_consistent_history(self.connection)
            except InconsistentMigrationHistory as e:
                raise MigrationHistoryError(six.text_type(e))

        # Now check that there aren't any conflicts between any migrations that
        # we may end up working with.
        conflicts = self.loader.detect_conflicts()

        if conflicts:
            raise MigrationConflictsError(conflicts)

    def _on_progress(self, action, migration=None, *args, **kwargs):
        """Handler for progress notifications.

        This will convert certain progress notifications to Django Evolution
        signals.

        Args:
            action (unicode):
                The action reflecting the progress update.

            migration (django.db.migrations.Migration, optional):
                The migration that the progress update applies to. This is
                not provided for all progress updates.

            *args (tuple, unused):
                Additional positional arguments passed for the update.

            **kwargs (dict, unused):
                Additional keyword arguments passed for the update.
        """
        if action == 'apply_start':
            applying_migration.send(sender=self._signal_sender,
                                    migration=migration)
        elif action == 'apply_success':
            applied_migration.send(sender=self._signal_sender,
                                   migration=migration) class MigrationList(object):
    """A list of applied or pending migrations.

    This is used to manage a list of migrations in a way that's independent
    from the underlying representation used in Django. Migrations are tracked
    by app label and name, may be associated with a recorded migration
    database entry, and can be used to convert state to and from both
    signatures and Django migration state.
    """

    @classmethod
    def from_app_sig(cls, app_sig):
        """Create a MigrationList based on an app signature.

        Args:
            app_sig (django_evolution.signature.AppSignature):
                The app signature containing a list of applied migrations.

        Returns:
            MigrationList:
            The new migration list.
        """
        return cls.from_names(app_label=app_sig.app_id,
                              migration_names=app_sig.applied_migrations)

    @classmethod
    def from_names(cls, app_label, migration_names):
        """Create a MigrationList based on a list of migration names.

        Version Added:
            2.1

        Args:
            app_label (unicode):
                The app label common to each migration name.

            migration_names (list of unicode):
                The list of migration names.

        Returns:
            MigrationList:
            The new migration list.
        """
        migration_list = cls()

        if migration_names:
            for name in migration_names:
                migration_list.add_migration_info(app_label=app_label,
                                                  name=name)

        return migration_list

    @classmethod
    def from_database(cls, connection, app_label=None):
        """Create a MigrationList based on recorded migrations.

        Args:
            connection (django.db.backends.base.BaseDatabaseWrapper):
                The database connection used to query for migrations.

            app_label (unicode, optional):
                An app label to filter migrations by.

        Returns:
            MigrationList:
            The new migration list.
        """
        recorder = MigrationRecorder(connection)
        recorder.ensure_schema()

        migration_list = cls()
        queryset = recorder.migration_qs

        if app_label:
            queryset = queryset.filter(app=app_label)

        for recorded_migration in queryset.all():
            migration_list.add_recorded_migration(recorded_migration)

        return migration_list

    def __init__(self):
        """Initialize the list."""
        self._by_app_label = {}
        self._by_id = {}

    def has_migration_info(self, app_label, name):
        """Return whether the list contains an entry for a migration.

        Args:
            app_label (unicode):
                The label for the application that was migrated.

            name (unicode):
                The name of the migration.

        Returns:
            bool:
            ``True`` if the migration is in the list. ``False`` if it is not.
        """
        return (app_label, name) in self._by_id

    def add_migration_targets(self, targets):
        """Add a list of migration targets to the list.

        Args:
            targets (list of tuple):
                The migration targets to each. Each is a tuple containing
                an app label and a migration name.
        """
        for app_label, name in targets:
            self.add_migration_info(app_label=app_label,
                                    name=name)

    def add_migration(self, migration):
        """Add a migration to the list.

        This can only be called on Django 1.7 or higher.

        Args:
            migration (django.db.migrations.Migration):
                The migration instance to add.
        """
        assert Migration is not None
        assert isinstance(migration, Migration)

        self.add_migration_info(app_label=migration.app_label,
                                name=migration.name,
                                migration=migration)

    def add_recorded_migration(self, recorded_migration):
        """Add a recorded migration to the list.

        This can only be called on Django 1.7 or higher.

        Args:
            recorded_migration (django.db.migrations.recorder.
                                MigrationRecorder.Migration):
                The recorded migration model to add.
        """
        assert MigrationRecorder is not None
        assert isinstance(recorded_migration, MigrationRecorder.Migration)

        self.add_migration_info(app_label=recorded_migration.app,
                                name=recorded_migration.name,
                                recorded_migration=recorded_migration)

    def add_migration_info(self, app_label, name, migration=None,
                           recorded_migration=None):
        """Add information on a migration to the list.

        Args:
            app_label (unicode):
                The label for the application that was migrated.

            name (unicode):
                The name of the migration.

            migration (django.db.migrations.Migration, optional):
                An optional migration instance to associate with this entry.

            recorded_migration (django.db.migrations.recorder.
                                MigrationRecorder.Migration, optional):
                An optional recorded migration to associate with this entry.
        """
        info = {
            'app_label': app_label,
            'migration': migration,
            'name': name,
            'recorded_migration': recorded_migration,
        }

        self._by_app_label.setdefault(app_label, []).append(info)
        self._by_id[(app_label, name)] = info

    def update(self, other):
        """Update the list with the contents of another list.

        If there's an entry in another list matching this one, and contains
        information that the entry in this list does not have, this list's
        entry will be updated.

        Args:
            other (MigrationList):
                The list of migrations to put into this list.
        """
        for other_info in other:
            app_label = other_info['app_label']
            name = other_info['name']
            info = self._by_id.get((app_label, name))

            if info is None:
                self.add_migration_info(app_label=app_label,
                                        name=name)
            else:
                for key in ('migration', 'recorded_migration'):
                    if info[key] is None:
                        info[key] = other_info[key]

    def to_targets(self):
        """Return a set of migration targets based on this list.

        Returns:
            set:
            A set of migration targets. Each entry is a tuple containing
            the app label and name.
        """
        return set(
            (info['app_label'], info['name'])
            for info in self
        )

    def get_app_labels(self):
        """Iterate through the app labels.

        Results are sorted alphabetically.

        Returns:
            list of unicode:
            The sorted list of app labels with associated migrations.
        """
        return list(sorted(six.iterkeys(self._by_app_label)))

    def clone(self):
        """Clone the list.

        Returns:
            MigrationList:
            The cloned migration list.
        """
        new_migration_list = MigrationList()

        for info in self:
            new_migration_list.add_migration_info(**info)

        return new_migration_list

    def __bool__(self):
        """Return whether this list is truthy or falsy.

        The list is truthy only if it has items.

        Returns:
            bool:
            ``True`` if the list has items. ``False`` if it's empty.
        """
        return bool(self._by_id)

    def __len__(self):
        """Return the number of items in the list.

        Returns:
            int:
            The number of items in the list.
        """
        return len(self._by_id)

    def __eq__(self, other):
        """Return whether this list is equal to another list.

        The order of migrations is ignored when comparing lists.

        Args:
            other (MigrationList):
                A list of migrations to compare to.

        Returns:
            bool:
            ``True`` if the two lists have the same contents. ``False`` if
            there are differences in contents, or ``other`` is not a
            :py:class:`MigrationList`.
        """
        if other is None or not isinstance(other, MigrationList):
            return False

        return self._by_id == other._by_id

    def __iter__(self):
        """Iterate through the list.

        Entries are sorted first by app label, alphabetically, and then
        the order in which migrations were added for that app label.

        Yields:
            info:
            A dictionary containing the following keys:

            ``app_label`` (:py:class:`unicode`):
                The app label for the migration.

            ``name`` (:py:class:`unicode`):
                The name of the migration.

            ``migration`` (:py:class:`django.db.migrations.Migration`):
                The optional migration instance.

            ``recorded_migration`` (:py:class:`django.db.migrations.recorder.MigrationRecorder.Migration`):
                The optional recorded migration.
        """
        for app_label, info_list in sorted(six.iteritems(self._by_app_label),
                                           key=lambda pair: pair[0]):
            for info in info_list:
                yield info

    def __add__(self, other):
        """Return a combined copy of this list and another list.

        Args:
            other (MigrationList):
                The other list to add to this list.

        Returns:
            MigrationList:
            The new migration list containing contents of both lists.
        """
        new_migration_list = self.clone()
        new_migration_list.update(other)

        return new_migration_list

    def __sub__(self, other):
        """Return a copy of this list with another list's contents excluded.

        Args:
            other (MigrationList):
                The other list containing contents to exclude.

        Returns:
            MigrationList:
            The new migration list containing the contents of this list that
            don't exist in the other list.
        """
        new_migration_list = MigrationList()

        for info in self:
            if not other.has_migration_info(app_label=info['app_label'],
                                            name=info['name']):
                new_migration_list.add_migration_info(**info)

        return new_migration_list

    def __repr__(self):
        """Return a string representation of this list.

        Returns:
            unicode:
            The string representation.
        """
        return '<MigrationList%s>' % list(self) class MigrationLoader(DjangoMigrationLoader):
    """Loads migration files from disk.

    This is a specialization of Django's own
    :py:class:`~django.db.migrations.loader.MigrationLoader` that allows for
    providing additional migrations not available on disk.

    Attributes:
        extra_applied_migrations (MigrationList):
            Migrations to mark as already applied. This can be used to
            augment the results calculated from the database.
    """

    def __init__(self, connection, custom_migrations=None, *args, **kwargs):
        """Initialize the loader.

        Args:
            connection (django.db.backends.base.BaseDatabaseWrapper):
                The connection to load applied migrations from.

            custom_migrations (MigrationList, optional):
                Custom migrations not available on disk.

            *args (tuple):
                Additional positional arguments for the parent class.

            **kwargs (dict):
                Additional keyword arguments for the parent class.
        """
        self._custom_migrations = custom_migrations or MigrationList()
        self._applied_migrations = None
        self._lock_migrations = False

        self.extra_applied_migrations = MigrationList()

        super(MigrationLoader, self).__init__(connection, *args, **kwargs)

    @property
    def applied_migrations(self):
        """The migrations already applied.

        This will contain both the migrations applied from the database
        and any set in :py:attr:`extra_applied_migrations`.
        """
        extra_migrations = self.extra_applied_migrations

        if isinstance(self._applied_migrations, dict):
            # Django >= 3.0
            applied_migrations = self._applied_migrations.copy()

            for info in extra_migrations:
                app_label = info['app_label']
                name = info['name']
                recorded_migration = info['recorded_migration']

                if recorded_migration is None:
                    recorded_migration = MigrationRecorder.Migration(
                        app=app_label,
                        name=name,
                        applied=True)

                applied_migrations[(app_label, name)] = recorded_migration

        elif isinstance(self._applied_migrations, set):
            # Django < 3.0
            applied_migrations = self._applied_migrations | set(
                (info['app_label'], info['name'])
                for info in extra_migrations
            )
        else:
            raise DjangoEvolutionSupportError(
                'Migration.applied_migrations is an unexpected type (%s)'
                % type(self._applied_migrations))

        return applied_migrations

    @applied_migrations.setter
    def applied_migrations(self, value):
        """Set the migrations already applied.

        Args:
            value (set of tuple):
                The migrations already applied to the database.
        """
        if value is not None and not isinstance(value, (dict, set)):
            raise DjangoEvolutionSupportError(
                'Migration.applied_migrations was set to an unexpected type '
                '(%s)'
                % type(value))

        if value is None:
            self._applied_migrations = None
        else:
            if django_version >= (3, 0):
                self._applied_migrations = dict(value)
            else:
                self._applied_migrations = value

    def build_graph(self, reload_migrations=True):
        """Rebuild the migrations graph.

        Args:
            reload_migrations (bool, optional):
                Whether to reload migration instances from disk. If ``False``,
                the ones loaded before will be used.
        """
        if not reload_migrations:
            self._lock_migrations = True

        try:
            super(MigrationLoader, self).build_graph()
        finally:
            self._lock_migrations = False

    def load_disk(self):
        """Load migrations from disk.

        This will also load any custom migrations.
        """
        if self._lock_migrations:
            return

        super(MigrationLoader, self).load_disk()

        for info in self._custom_migrations:
            migration = info['migration']
            assert migration is not None

            app_label = info['app_label']
            name = info['name']

            self.migrated_apps.add(app_label)
            self.unmigrated_apps.discard(app_label)
            self.disk_migrations[(app_label, name)] = migration def record_applied_migrations(connection, migrations):
    """Record a list of applied migrations to the database.

    This can only be called when on Django 1.7 or higher.

    Args:
        connection (django.db.backends.base.BaseDatabaseWrapper):
            The connection used to record applied migrations.

        migrations (MigrationList):
            The list of migration targets to record as applied.
    """
    assert supports_migrations, \
        'This cannot be called on Django 1.6 or earlier.'

    recorder = MigrationRecorder(connection)
    recorder.ensure_schema()

    recorder.migration_qs.bulk_create(
        recorder.Migration(app=info['app_label'],
                           name=info['name'])
        for info in migrations
    )
from django.db import DEFAULT_DB_ALIAS, connections
from django_evolution.compat.apps import get_app
from django_evolution.models import Evolution, Version
from django_evolution.support import supports_migrations
from django_evolution.tests.base_test_case import (MigrationsTestsMixin,
                                                   TestCase)
from django_evolution.tests.decorators import requires_migrations
from django_evolution.tests.evolutions_app.models import EvolutionsAppTestModel
from django_evolution.tests.evolutions_app2.models import \
    EvolutionsApp2TestModel
from django_evolution.utils.graph import EvolutionGraph
from django_evolution.utils.migrations import (MigrationExecutor,
                                               MigrationList,
                                               MigrationLoader,
                                               record_applied_migrations)
    from django.db import migrations
    from django.db.migrations.graph import MigrationGraph
        graph = EvolutionGraph()
        graph.process_migration_deps = False

        graph.add_evolutions(app=app,
                             evolutions=evolutions)
        graph.mark_evolutions_applied(app=get_app('evolutions_app'),
                                      evolution_labels=['first_evolution'])
        graph.mark_evolutions_applied(app=get_app('evolutions_app2'),
                                      evolution_labels=['second_evolution'])
        graph.finalize()

        nodes = graph.get_ordered()
        self.assertEqual(len(nodes), 3)

        self._check_node(
            nodes[0],
            insert_index=0,
            key='evolution:app_deps_app:__first__',
            required_by={
                'evolution:app_deps_app:test_evolution',
            },
            state={
                'anchor': True,
                'app': app,
            })

        self._check_node(
            nodes[1],
            insert_index=1,
            key='evolution:app_deps_app:test_evolution',
            dependencies={
                'evolution:app_deps_app:__first__',
            },
            required_by={
                'evolution:app_deps_app:__last__',
            },
            state={
                'app': app,
                'evolution': evolutions[0],
                'type': graph.NODE_TYPE_EVOLUTION,
            })

        self._check_node(
            nodes[2],
            insert_index=2,
            key='evolution:app_deps_app:__last__',
            dependencies={
                'evolution:app_deps_app:test_evolution',
            },
            state={
                'anchor': True,
                'app': app,
            })

    @requires_migrations
    def test_mark_migrations_applied(self):
        """Testing EvolutionGraph.mark_migrations_applied"""
        class TestsInitialMigration(migrations.Migration):
            pass

        class TestsAddFieldMigration(migrations.Migration):
            dependencies = [
                ('tests', '0001_initial'),
            ]

        class OtherInitialMigration(migrations.Migration):
            dependencies = [('tests', '0002_add_field')]

        graph = EvolutionGraph()
        migration_plan = self._add_migrations(
            graph=graph,
            migrations_info=[
                ('tests', '0001_initial', TestsInitialMigration),
                ('tests', '0002_add_field', TestsAddFieldMigration),
                ('other', '0001_initial', OtherInitialMigration),
            ],
            leaf_migration_targets=[('other', '0001_initial')],
            mark_applied=[
                ('tests', '0001_initial'),
                ('tests', '0002_add_field'),
            ])
        self.assertEqual(len(migration_plan), 1)

        graph.finalize()

        nodes = graph.get_ordered()
        self.assertEqual(len(nodes), 1)

        self._check_node(
            nodes[0],
            insert_index=0,
            key='migration:other:0001_initial',
            state={
                'migration_plan_item': migration_plan[0],
                'migration_target': ('other', '0001_initial'),
                'type': graph.NODE_TYPE_MIGRATION,
            })

    def test_iter_batches(self):
        """Testing EvolutionGraph.iter_batches"""
        evolutions_app = get_app('evolutions_app')
        evolutions_app2 = get_app('evolutions_app2')
        evolution_deps_app = get_app('evolution_deps_app')

        # evolutions_app
        evolutions1 = [
            Evolution(app_label='evolutions_app',
                      label='first_evolution'),
            Evolution(app_label='evolutions_app',
                      label='second_evolution'),
        ]
        models1 = [EvolutionsAppTestModel]

        # evolutions_app2
        evolutions2 = [
            Evolution(app_label='evolutions_app2',
                      label='first_evolution'),
            Evolution(app_label='evolutions_app2',
                      label='second_evolution'),
        ]

        models2 = [EvolutionsApp2TestModel]