// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

use std::collections::HashSet;
use std::fmt::{self, Debug, Display};
use std::num;
use std::result::Result;

use chrono::{DateTime, Utc};
use git_workarea::{
    CommitId, Conflict, GitContext, GitError, Identity, MergeResult, MergeStatus, WorkAreaError,
};
use log::{debug, info, warn};
use thiserror::Error;

/// Why a commit is not a valid staging branch commit.
///
/// The staging branch format is such that its first-parent history consists solely of two-parent
/// merge commits. It must also have the base commit as an ancestor.
#[derive(Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum InvalidCommitReason {
    /// A non-merge commit was found.
    NonMergeCommit,
    /// An octopus merge commit was found.
    OctopusMerge,
    /// The integration branch is not related to the base.
    NotRelated,
    /// The integration branch does not point to a commit.
    NotACommit,
    /// A merge commit has an invalid commit subject.
    InvalidSubject(String),
    /// A merge commit is missing an ID.
    MissingId,
    /// A merge commit is missing a URL.
    MissingUrl,
    /// A topic has in ID of `0`, which is reserved for the base branch.
    ZeroId,
    /// A topic has in ID that is not an unsigned integer.
    UnparseableId(String),
}

impl Display for InvalidCommitReason {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let reason = match self {
            InvalidCommitReason::NonMergeCommit => "non-merge commit",
            InvalidCommitReason::OctopusMerge => "octopus merge",
            InvalidCommitReason::NotRelated => "not related",
            InvalidCommitReason::NotACommit => "not a commit",
            InvalidCommitReason::InvalidSubject(_) => "invalid subject",
            InvalidCommitReason::MissingId => "missing id",
            InvalidCommitReason::MissingUrl => "missing url",
            InvalidCommitReason::ZeroId => "invalid id (0)",
            InvalidCommitReason::UnparseableId(_) => "unparseable id",
        };

        write!(f, "{}", reason)
    }
}

/// Errors which may occur while managing a topic stage branch.
///
/// This enum is `non_exhaustive`, but cannot be marked as such until it is stable. In the
/// meantime, there is a hidden variant.
#[derive(Debug, Error)]
#[non_exhaustive]
pub enum StagerError {
    /// An error occurred when working with Git itself.
    #[error("git error: {}", source)]
    Git {
        /// The cause of the error.
        #[from]
        source: GitError,
    },
    /// An error occurred when working with the workarea.
    #[error("workarea error: {}", source)]
    WorkArea {
        /// The cause of the error.
        #[from]
        source: WorkAreaError,
    },
    /// The integration branch is invalid.
    #[error("invalid integration branch: {}: {}", commit, reason)]
    InvalidIntegrationBranch {
        /// The merge commit into the integration branch.
        commit: CommitId,
        /// Why the branch is invalid.
        reason: InvalidCommitReason,
    },
    /// A topic with the given ID is already on the stage.
    #[error("duplicate stage id: {}", id)]
    DuplicateTopicId {
        /// The topic ID which has duplicate merges.
        id: u64,
    },
    /// An error occurred when creating a stage ref.
    #[error("failed to update the {} ref to {}: {}", stage, base, output)]
    CreateStageRef {
        /// The ref that could not be made.
        stage: CommitId,
        /// What it should have been updated to.
        base: CommitId,
        /// Git's error output.
        output: String,
    },
    /// An error occurred when listing the stage's history.
    #[error(
        "failed to list the first parent history of the stage branch: {}",
        output
    )]
    ListStageHistory {
        /// Git's error output.
        output: String,
    },
    /// An error occurred when extracting topic information from a merge.
    #[error(
        "failed to get information about a merge on the topic stage: {}",
        output
    )]
    ExtractMergeInfo {
        /// Git's error output.
        output: String,
    },
    /// An invalid merge into the stage was found.
    #[error("invalid stage merge commit {} found: {}", commit, log_info)]
    InvalidStageMerge {
        /// The invalid merge commit.
        commit: CommitId,
        /// The log information extracted from the commit.
        log_info: String,
    },
    /// The base commit cannot be unstaged.
    #[error("cannot unstage base")]
    CannotUnstageBase,
    /// An invalid commit date was found.
    #[error("failed to parse date: {}", source)]
    DateParse {
        /// The date parse error.
        #[source]
        source: chrono::ParseError,
    },
    /// An invalid topic ID was found.
    #[deprecated(since = "4.1.0", note = "No longer used.")]
    #[error("failed to parse topic ID: {}", source)]
    IdParse {
        /// The integer parse error.
        #[source]
        source: num::ParseIntError,
    },
}

impl StagerError {
    fn invalid_branch(commit: CommitId, reason: InvalidCommitReason) -> Self {
        StagerError::InvalidIntegrationBranch {
            commit,
            reason,
        }
    }

    fn duplicate_topic_id(id: u64) -> Self {
        StagerError::DuplicateTopicId {
            id,
        }
    }

    fn create_stage_ref(stage: CommitId, base: CommitId, output: &[u8]) -> Self {
        StagerError::CreateStageRef {
            stage,
            base,
            output: String::from_utf8_lossy(output).into(),
        }
    }

    fn list_stage_history(output: &[u8]) -> Self {
        StagerError::ListStageHistory {
            output: String::from_utf8_lossy(output).into(),
        }
    }

    fn extract_merge_info(output: &[u8]) -> Self {
        StagerError::ExtractMergeInfo {
            output: String::from_utf8_lossy(output).into(),
        }
    }

    fn invalid_stage_merge(commit: &str, log_info: &[u8]) -> Self {
        StagerError::InvalidStageMerge {
            commit: CommitId::new(commit),
            log_info: String::from_utf8_lossy(log_info).into(),
        }
    }

    fn date_parse(source: chrono::ParseError) -> Self {
        StagerError::DateParse {
            source,
        }
    }
}

type StagerResult<T> = Result<T, StagerError>;

/// A branch for the stager.
///
/// Topics contain additional information so that they may be easily identified and so that the
/// commit messages are useful to humans as well.
#[derive(Debug, Clone)]
pub struct Topic {
    /// The `HEAD` commit of the topic branch.
    pub commit: CommitId,
    /// The author of the stage request.
    pub author: Identity,
    /// When the stage request occurred.
    pub stamp: DateTime<Utc>,
    /// An ID for the topic.
    pub id: u64,
    /// The name of the topic.
    pub name: String,
    /// The URL of the topic.
    pub url: String,
}

impl Topic {
    /// Create a topic.
    ///
    /// The ID must be unique across all topics.
    pub fn new<N, U>(
        commit: CommitId,
        author: Identity,
        stamp: DateTime<Utc>,
        id: u64,
        name: N,
        url: U,
    ) -> Self
    where
        N: Into<String>,
        U: Into<String>,
    {
        Self {
            commit,
            author,
            stamp,
            id,
            name: name.into(),
            url: url.into(),
        }
    }
}

impl Display for Topic {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(
            f,
            "topic {} at {}, staged by {} at {}",
            self.name, self.commit, self.author, self.stamp
        )
    }
}

impl PartialEq for Topic {
    fn eq(&self, rhs: &Self) -> bool {
        // The author and stamp time are explicitly not considered since they are not important to
        // the actual topic comparison once on the stage.
        self.commit == rhs.commit && self.id == rhs.id
    }
}

/// A topic branch which should be integrated into the stage.
#[derive(Debug, Clone, PartialEq)]
pub struct CandidateTopic {
    /// The old revision for the topic (if available).
    pub old_id: Option<Topic>,
    /// The new revision for the topic.
    pub new_id: Topic,
}

impl CandidateTopic {
    fn is_self_consistent(&self) -> bool {
        self.old_id
            .as_ref()
            .map_or(true, |old| old.id == self.new_id.id)
    }
}

impl Display for CandidateTopic {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if let Some(ref old_topic) = self.old_id {
            write!(f, "candidate {}, replacing {}", self.new_id, old_topic)
        } else {
            write!(f, "candidate {}, new", self.new_id)
        }
    }
}

/// A topic branch which has been staged.
#[derive(Debug, Clone, PartialEq)]
pub struct StagedTopic {
    /// The commit where the topic branch has been merged into the staging branch.
    pub merge: CommitId,
    /// The topic branch.
    pub topic: Topic,
}

impl StagedTopic {
    /// The HEAD commit of the topic branch.
    pub fn commit(&self) -> &CommitId {
        &self.topic.commit
    }
}

impl Display for StagedTopic {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "staged {}, via {}", self.topic, self.merge)
    }
}

/// Reasons for which a branch can be unstaged.
pub enum UnstageReason {
    /// Conflicts occurred while merging the topic.
    MergeConflict(Vec<Conflict>),
}

impl Debug for UnstageReason {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match *self {
            UnstageReason::MergeConflict(ref conflicts) => {
                write!(f, "MergeConflict ( {} conflicts )", conflicts.len())
            },
        }
    }
}

/// Reasons an old topic was removed from the stage.
#[derive(Debug)]
pub enum OldTopicRemoval {
    /// The topic branch has been obsoleted by an update.
    Obsoleted {
        /// The old topic, as staged.
        old_merge: StagedTopic,
        /// The staged topic branch which has replaced the old topic branch.
        replacement: Option<StagedTopic>,
    },
    /// The topic branch has been removed, without replacement, from the stage.
    Removed(StagedTopic),
}

impl OldTopicRemoval {
    /// The topic branch which was removed.
    pub fn topic(&self) -> &Topic {
        match *self {
            OldTopicRemoval::Obsoleted {
                old_merge: ref ob, ..
            } => &ob.topic,
            OldTopicRemoval::Removed(ref rb) => &rb.topic,
        }
    }
}

/// Results from integrating a topic.
#[derive(Debug)]
pub enum IntegrationResult {
    /// The topic is successfully staged into the integration branch.
    Staged(StagedTopic),
    /// The topic is kicked out of the integration branch.
    Unstaged(Topic, UnstageReason),
    /// The topic is not mergeable.
    Unmerged(Topic, MergeStatus),
}

impl IntegrationResult {
    /// The topic branch.
    pub fn topic(&self) -> &Topic {
        match *self {
            IntegrationResult::Staged(ref sb) => &sb.topic,
            IntegrationResult::Unstaged(ref u, _) => u,
            IntegrationResult::Unmerged(ref t, _) => t,
        }
    }

    /// Whether the topic branch is currently staged or not.
    pub fn on_stage(&self) -> bool {
        match *self {
            IntegrationResult::Staged(_) => true,
            IntegrationResult::Unstaged(_, _) | IntegrationResult::Unmerged(_, _) => false,
        }
    }
}

/// The result of rewinding the stage back to a point where new commits may be applied.
///
/// The order is such that the first pair represents the old state of the staged topics while the
/// last pair represents the topics which need to be re-integrated into the staging branch.
type RewoundStage = (Option<StagedTopic>, Vec<StagedTopic>, Option<Topic>);

/// The results of a stage operation.
#[derive(Debug)]
pub struct StageResult {
    /// The branch which the operation removed from the stage.
    pub old_topic: Option<OldTopicRemoval>,
    /// Results from reintegrating the other staged topics.
    ///
    /// Other topics may need to be merged into the integration result again and may fail to merge
    /// once another topic is removed from the branch.
    pub results: Vec<IntegrationResult>,
}

/// A manager for an integration branch.
///
/// This stores the state of a staging branch and the representative topics.
#[derive(Debug)]
pub struct Stager {
    /// The git context for the stager to work in.
    ctx: GitContext,
    /// The ordered set of topics currently merged into the topic stage.
    topics: Vec<StagedTopic>,
}

/// The summary prefix to use when staging topics.
const STAGE_TOPIC_PREFIX: &str = "Stage topic '";
/// The summary suffix to use when staging topics.
const STAGE_TOPIC_SUFFIX: &str = "'";
/// The trailer to use for the ID of the topic.
const TOPIC_ID_TRAILER: &str = "Topic-id: ";
/// The trailer to use for the URL of the topic.
const TOPIC_URL_TRAILER: &str = "Topic-url: ";

impl Stager {
    /// Create a new stage from the given commit.
    pub fn new(ctx: &GitContext, base: CommitId) -> Self {
        Self {
            ctx: ctx.clone(),
            topics: vec![Self::make_base_staged_topic(base)],
        }
    }

    /// Create a new stage, discovering topics which have been merged into an integration branch.
    ///
    /// This constructor takes a base branch and the name of the stage branch. It queries the given
    /// Git context for the history of the stage branch from the base and constructs its state from
    /// its first parent history.
    ///
    /// If the stage does not exist, it is created with the base commit as its start.
    ///
    /// Fails if the stage branch history does not appear to be a proper stage branch. A proper
    /// stage branch's first parent history from the base consists only of merge commits with
    /// exactly two parents with required information in its commit message.
    pub fn from_branch(ctx: &GitContext, base: CommitId, stage: CommitId) -> StagerResult<Self> {
        let cat_file = ctx
            .git()
            .arg("cat-file")
            .arg("-t")
            .arg(stage.as_str())
            .output()
            .map_err(|err| GitError::subcommand("cat-file", err))?;
        if cat_file.status.success() {
            // Ensure that the stage ref is a commit.
            let stage_type = String::from_utf8_lossy(&cat_file.stdout);
            if stage_type.trim() != "commit" {
                return Err(StagerError::invalid_branch(
                    stage,
                    InvalidCommitReason::NotACommit,
                ));
            }
        } else {
            // Create the stage ref.
            let update_ref = ctx
                .git()
                .arg("update-ref")
                .arg(stage.as_str())
                .arg(base.as_str())
                .output()
                .map_err(|err| GitError::subcommand("update-ref", err))?;
            if !update_ref.status.success() {
                return Err(StagerError::create_stage_ref(
                    stage,
                    base,
                    &update_ref.stderr,
                ));
            }
        }

        // Check if the stage ref needs updated for the new base.
        let is_ancestor = ctx
            .git()
            .arg("merge-base")
            .arg("--is-ancestor")
            .arg(base.as_str())
            .arg(stage.as_str())
            .status()
            .map_err(|err| GitError::subcommand("merge-base --is-ancestor", err))?;
        let needs_base_update = !is_ancestor.success();

        debug!(target: "git-topic-stage", "creating a stage branch from {} -> {}", base, stage);

        // Find the merge base to create the base topic.
        let merge_base = ctx
            .git()
            .arg("merge-base")
            .arg(base.as_str())
            .arg(stage.as_str())
            .output()
            .map_err(|err| GitError::subcommand("merge-base", err))?;
        if !merge_base.status.success() {
            return Err(StagerError::invalid_branch(
                stage,
                InvalidCommitReason::NotRelated,
            ));
        }
        let merge_base = String::from_utf8_lossy(&merge_base.stdout);

        let mut topics = vec![Self::make_base_staged_topic(CommitId::new(
            merge_base.trim(),
        ))];

        // Get the first parent history of the stage ref that are not in the base. Also include the
        // parents of the commits so the topic set can be reconstructed.
        let rev_list = ctx
            .git()
            .arg("rev-list")
            .arg("--first-parent")
            .arg("--reverse")
            .arg("--parents")
            .arg(stage.as_str())
            .arg(&format!("^{}", base))
            .output()
            .map_err(|err| GitError::subcommand("rev-list --first-parent", err))?;
        if !rev_list.status.success() {
            return Err(StagerError::list_stage_history(&rev_list.stderr));
        }
        let merges = String::from_utf8_lossy(&rev_list.stdout);

        // Parse out our merge history.
        let new_topics = merges
            .lines()
            .map(|merge| {
                // Get the parents of the merge commit.
                let revs = merge.split_whitespace().collect::<Vec<_>>();
                let (rev, parents) = revs[..].split_first().expect("invalid rev-list format");
                let rev_commit = CommitId::new(*rev);

                // The stage should be constructed only of merge commits.
                //
                // This may happen if the target branch has been rewound while the stage has the
                // original history.
                if parents.len() == 1 {
                    return Err(StagerError::invalid_branch(
                        rev_commit,
                        InvalidCommitReason::NonMergeCommit,
                    ));
                }

                // Though octopus merges are also not allowed.
                if parents.len() > 2 {
                    return Err(StagerError::invalid_branch(
                        rev_commit,
                        InvalidCommitReason::OctopusMerge,
                    ));
                }

                // Extract all of the information from a commit in order to recreate the
                // `StageTopic` structure.
                let commit_info = ctx
                    .git()
                    .arg("log")
                    .arg("--max-count=1")
                    .arg("--pretty=%an%n%ae%n%aI%n%B")
                    .arg(rev)
                    .output()
                    .map_err(|err| GitError::subcommand("log", err))?;
                if !commit_info.status.success() {
                    return Err(StagerError::extract_merge_info(&commit_info.stderr));
                }
                let info = String::from_utf8_lossy(&commit_info.stdout);
                let info = info.lines().collect::<Vec<_>>();

                // Sanity check that we got the information we want.
                if info.len() <= 6 {
                    return Err(StagerError::invalid_stage_merge(rev, &commit_info.stdout));
                }

                // Extract out the name of the topic from the merge commit message summary.
                let subject = info[3];
                if !subject.starts_with(STAGE_TOPIC_PREFIX)
                    || !subject.ends_with(STAGE_TOPIC_SUFFIX)
                {
                    let reason = InvalidCommitReason::InvalidSubject(subject.into());
                    return Err(StagerError::invalid_branch(rev_commit, reason));
                }
                let name =
                    &subject[STAGE_TOPIC_PREFIX.len()..subject.len() - STAGE_TOPIC_SUFFIX.len()];

                let mut id = None;
                let mut url = None;

                // Parse trailers from the commit message.
                for line in info[5..info.len() - 1].iter().rev() {
                    if line.is_empty() {
                        break;
                    } else if let Some(topic_id) = line.strip_prefix(TOPIC_ID_TRAILER) {
                        id = Some(topic_id.parse().map_err(|err| {
                            let reason = InvalidCommitReason::UnparseableId(format!("{}", err));
                            StagerError::invalid_branch(rev_commit.clone(), reason)
                        })?);
                    } else if let Some(topic_url) = line.strip_prefix(TOPIC_URL_TRAILER) {
                        url = Some(topic_url.to_string());
                    } else {
                        // Not a real issue, but this is unexpected.
                        warn!(
                            target: "git-topic-stage",
                            "unrecognized trailer in {}: {}",
                            parents[1],
                            line,
                        );
                    }
                }

                // Check that we have the information we need to create a `StagedTopic`.
                let url = if let Some(url) = url {
                    url
                } else {
                    return Err(StagerError::invalid_branch(
                        rev_commit,
                        InvalidCommitReason::MissingUrl,
                    ));
                };

                let id = match id {
                    Some(0) => {
                        return Err(StagerError::invalid_branch(
                            rev_commit,
                            InvalidCommitReason::ZeroId,
                        ));
                    },
                    Some(id) => id,
                    None => {
                        return Err(StagerError::invalid_branch(
                            rev_commit,
                            InvalidCommitReason::MissingId,
                        ));
                    },
                };

                info!(
                    target: "git-topic-stage",
                    "found staged topic '{}' from {}",
                    name, url,
                );

                Ok(StagedTopic {
                    merge: rev_commit,
                    topic: Topic::new(
                        CommitId::new(parents[1]),
                        Identity::new(info[0], info[1]),
                        info[2].parse().map_err(StagerError::date_parse)?,
                        id,
                        name,
                        url,
                    ),
                })
            })
            .collect::<StagerResult<Vec<_>>>()?;

        topics.extend(new_topics.into_iter());

        // Verify that there are no duplicate topic IDs.
        let mut ids = HashSet::new();
        for topic in &topics {
            if !ids.insert(topic.topic.id) {
                return Err(StagerError::duplicate_topic_id(topic.topic.id));
            }
        }

        let mut stager = Self {
            ctx: ctx.clone(),
            topics,
        };

        // If the target branch for the stage branch has been updated, perform a stage of a topic
        // which updates to the current state of the branch.
        if needs_base_update {
            let base_update = CandidateTopic {
                old_id: Some(Self::make_base_topic(CommitId::new(merge_base.trim()))),
                new_id: Self::make_base_topic(base),
            };

            stager.stage(base_update)?;
        }

        Ok(stager)
    }

    /// Returns the git context the stager uses for operations.
    pub fn git_context(&self) -> &GitContext {
        &self.ctx
    }

    /// Returns the base branch for the integration branch.
    pub fn base(&self) -> &CommitId {
        self.topics[0].commit()
    }

    /// The topics which have been merged into the stage.
    pub fn topics(&self) -> &[StagedTopic] {
        &self.topics[1..]
    }

    /// The a topic on the stage by its ID.
    pub fn find_topic_by_id(&self, id: u64) -> Option<&StagedTopic> {
        self.topics()
            .iter()
            .find(|staged_topic| id == staged_topic.topic.id)
    }

    /// Find where a topic has been merged into the integration branch.
    pub fn find_topic(&self, topic: &Topic) -> Option<&StagedTopic> {
        self.topics()
            .iter()
            .find(|staged_topic| topic == &staged_topic.topic)
    }

    /// Returns the newest commit in the integration branch.
    pub fn head(&self) -> &CommitId {
        &self
            .topics
            .iter()
            .last()
            .expect("expected there to be a HEAD topic on the stage")
            .merge
    }

    /// Make a new staged topic structure from a commit, assuming it is the base of the stage.
    fn make_base_staged_topic(base: CommitId) -> StagedTopic {
        StagedTopic {
            merge: base.clone(),
            topic: Self::make_base_topic(base),
        }
    }

    /// Make a topic structure from a commit, assuming it is the base of the stage.
    fn make_base_topic(base: CommitId) -> Topic {
        Topic {
            commit: base,
            author: Identity::new("stager", "stager@example.com"),
            stamp: Utc::now(),
            id: 0,
            name: "base".into(),
            url: "url".into(),
        }
    }

    /// Rewind a stage to the topic right before a topic was merged.
    fn rewind_stage(&mut self, topic: CandidateTopic) -> RewoundStage {
        // Find the topic branch's old commit in the current stage.
        let root = topic
            .old_id
            .and_then(|old| {
                self.topics
                    .iter()
                    .position(|staged_topic| old == staged_topic.topic)
            })
            .unwrap_or_else(|| self.topics.len());

        // Grab the branches which must be restaged.
        let mut old_stage = self.topics.drain(root..).collect::<Vec<_>>();

        if self.topics.is_empty() {
            debug!(target: "git-topic-stage", "rewinding the stage to its base");
        } else {
            debug!(target: "git-topic-stage", "rewinding the stage to {}", self.head());
        }

        let (old_topic, new_topic) = if self.topics.is_empty() {
            // The base is being replaced.
            self.topics
                .push(Self::make_base_staged_topic(topic.new_id.commit));

            // The old topic branch is the first one in the list of branches that need to be
            // restaged, so remove it from the vector.
            (Some(old_stage.remove(0)), None)
        } else if old_stage.is_empty() {
            // This topic is brand new.
            (None, Some(topic.new_id))
        } else {
            // The old topic branch is the first one in the list of branches that need to be
            // restaged, so remove it from the vector.
            (Some(old_stage.remove(0)), Some(topic.new_id))
        };

        (old_topic, old_stage, new_topic)
    }

    /// Replay a set of topics onto the stage.
    fn replay_stage(
        &mut self,
        old_stage: Vec<StagedTopic>,
    ) -> StagerResult<Vec<IntegrationResult>> {
        debug!(target: "git-topic-stage", "replaying {} branches into the stage", old_stage.len());

        // Restage old branches.
        old_stage
            .into_iter()
            .map(|old_staged_topic| {
                let (staged, res) = self.merge_to_stage(old_staged_topic.topic)?;
                if let Some(t) = staged {
                    self.topics.push(t);
                }
                Ok(res)
            })
            .collect()
    }

    /// Remove a topic from the stage.
    pub fn unstage(&mut self, topic: StagedTopic) -> StagerResult<StageResult> {
        info!(target: "git-topic-stage", "unstaging a topic: {}", topic);

        if topic.commit() == self.base() {
            debug!(target: "git-topic-stage", "ignoring a request to unstage the base");

            return Err(StagerError::CannotUnstageBase);
        }

        let (old_topic, old_stage, new_topic) = self.rewind_stage(CandidateTopic {
            old_id: Some(topic.topic.clone()),
            new_id: topic.topic,
        });

        let results = self.replay_stage(old_stage)?;

        if new_topic.is_none() {
            // Requested the unstaging of the base branch.
            warn!(target: "git-topic-stage", "unstage called on the base branch");
        }

        if let Some(ref old_topic) = old_topic {
            debug!(target: "git-topic-stage", "unstaged {}", old_topic);
        }

        // Give some information about the old topic branch (if it existed).
        let old_branch_result = old_topic.map(OldTopicRemoval::Removed);

        Ok(StageResult {
            old_topic: old_branch_result,
            results,
        })
    }

    /// Add a topic branch to the stage.
    ///
    /// If the branch already existed on the staging branch, it is first removed from the stage and
    /// then any topics which were merged after it are merged again, in order. The updated topic is
    /// then merged as the last operation.
    pub fn stage(&mut self, topic: CandidateTopic) -> StagerResult<StageResult> {
        info!(target: "git-topic-stage", "staging a topic: {}", topic);

        let self_consistent = topic.is_self_consistent();
        if !self_consistent || topic.old_id.is_none() {
            if !self_consistent {
                warn!(
                    target: "git-topic-stage",
                    "inconsistent candidate topic submission: {}",
                    topic,
                );
            }

            if self
                .topics
                .iter()
                .any(|staged| staged.topic.id == topic.new_id.id)
            {
                return Err(StagerError::duplicate_topic_id(topic.new_id.id));
            }
        }

        // Rewind the stage.
        let (old_topic, old_stage, new_topic) = self.rewind_stage(topic);

        let mut results = self.replay_stage(old_stage)?;

        let old_branch_result = if let Some(topic) = new_topic {
            // Apply the new topic branch.
            let (staged, res) = self.merge_to_stage(topic)?;

            if let Some(sb) = staged.clone() {
                self.topics.push(sb);
            }
            results.push(res);

            // Give some information about the old topic branch (if it existed).
            old_topic.map(|topic| {
                OldTopicRemoval::Obsoleted {
                    old_merge: topic,
                    replacement: staged,
                }
            })
        } else {
            // The base of the branch was replaced; return the old stage base.
            old_topic.map(|topic| {
                OldTopicRemoval::Obsoleted {
                    old_merge: topic,
                    replacement: Some(self.topics[0].clone()),
                }
            })
        };

        Ok(StageResult {
            old_topic: old_branch_result,
            results,
        })
    }

    /// Remove all staged topics from the staging branch.
    ///
    /// Previously staged topics are returned.
    pub fn clear(&mut self) -> Vec<StagedTopic> {
        let new_id = Self::make_base_staged_topic(self.base().clone()).topic;
        let old_id = Some(new_id.clone());

        info!(target: "git-topic-stage", "clearing the stage");

        self.rewind_stage(CandidateTopic {
            old_id,
            new_id,
        })
        .1
    }

    /// Merge a topic into the stage.
    fn merge_to_stage(
        &self,
        topic: Topic,
    ) -> StagerResult<(Option<StagedTopic>, IntegrationResult)> {
        let base_commit = self.base();
        let head_commit = self.head();
        let topic_commit = topic.commit.clone();

        debug!(target: "git-topic-stage", "merging {} into the stage", topic);

        // Check that the topic is mergeable against the *base* commit. New root commits may have
        // appeared in topic branches that have since been merged. Checking against the base commit
        // ensures that it at least has a chance if it becomes the first branch on the stage again.
        let merge_status = self.ctx.mergeable(base_commit, &topic_commit)?;
        let bases = if let MergeStatus::Mergeable(bases) = merge_status {
            bases
        } else {
            // Reject branches which are not mergeable.
            debug!(target: "git-topic-stage", "rejecting: unmergeable: {}", merge_status);
            return Ok((None, IntegrationResult::Unmerged(topic, merge_status)));
        };

        // Prepare a workarea in which to perform the merge.
        let workarea = self.ctx.prepare(head_commit)?;

        // Prepare the merged tree.
        let merge_result = workarea.setup_merge(&bases, head_commit, &topic_commit)?;

        let mut merge_command = match merge_result {
            MergeResult::Conflict(conflicts) => {
                debug!(target: "git-topic-stage", "rejecting: conflicts: {}", conflicts.len());

                return Ok((
                    None,
                    IntegrationResult::Unstaged(topic, UnstageReason::MergeConflict(conflicts)),
                ));
            },
            MergeResult::Ready(command) => command,
        };

        // Add metadata about the stage request to the commit.
        merge_command.author(&topic.author).author_date(topic.stamp);

        // Commit the merged tree.
        let merge_commit = merge_command.commit(self.create_message(self.base(), &topic))?;
        let staged_topic = StagedTopic {
            merge: merge_commit,
            topic,
        };

        debug!(target: "git-topic-stage", "successfully staged as {}", staged_topic);

        Ok((
            Some(staged_topic.clone()),
            IntegrationResult::Staged(staged_topic),
        ))
    }

    /// Create the merge commit message for a topic.
    fn create_message(&self, _: &CommitId, topic: &Topic) -> String {
        format!(
            "{}{}{}\n\n{}{}\n{}{}\n",
            STAGE_TOPIC_PREFIX,
            topic.name,
            STAGE_TOPIC_SUFFIX,
            TOPIC_ID_TRAILER,
            topic.id,
            TOPIC_URL_TRAILER,
            topic.url,
        )
    }
}