view src/grapher.cpp @ 633:db62a0cb3037

* Added setting to specify that diff command should be run once for each selected file, rather than passing all file names to diff command (p4merge doesn't like being given many files)

/* -*- c-basic-offset: 4 indent-tabs-mode: nil -*-  vi:set ts=8 sts=4 sw=4: */

/*
    EasyMercurial

    Based on HgExplorer by Jari Korhonen
    Copyright (c) 2010 Jari Korhonen
    Copyright (c) 2012 Chris Cannam
    Copyright (c) 2012 Queen Mary, University of London
    
    This program is free software; you can redistribute it and/or
    modify it under the terms of the GNU General Public License as
    published by the Free Software Foundation; either version 2 of the
    License, or (at your option) any later version.  See the file
    COPYING included with this distribution for more information.
*/

#include "grapher.h"
#include "connectionitem.h"
#include "debug.h"
#include "changesetscene.h"

#include <QSettings>

#include <iostream>

Grapher::Grapher(ChangesetScene *scene) :
    m_scene(scene)
{
    QSettings settings;
    settings.beginGroup("Presentation");
    m_showDates = (settings.value("dateformat", 0) == 1);
    m_showClosedBranches = (settings.value("showclosedbranches", false).toBool());
}

int Grapher::findAvailableColumn(int row, int parent, bool preferParentCol)
{
    int col = parent;
    if (preferParentCol) {
        if (isAvailable(row, col)) return col;
    }
    while (col > 0) {
        if (isAvailable(row, --col)) return col;
    }
    while (col < 0) {
        if (isAvailable(row, ++col)) return col;
    }
    col = parent;
    int sign = (col < 0 ? -1 : 1);
    while (1) {
        col += sign;
        if (isAvailable(row, col)) return col;
    }
}

bool Grapher::isAvailable(int row, int col)
{
    if (m_alloc.contains(row) && m_alloc[row].contains(col)) return false;
    if (!m_haveAllocatedUncommittedColumn) return true;
    if (!m_uncommitted) return true;
    return !(row <= m_uncommittedParentRow && col == m_uncommitted->column());
}

void Grapher::layoutRow(QString id)
{
    if (m_handled.contains(id)) {
        return;
    }
    if (!m_changesets.contains(id)) {
        throw LayoutException(QString("Changeset %1 not in ID map").arg(id));
    }
    if (!m_items.contains(id)) {
        return;
    }
    Changeset *cs = m_changesets[id];
    ChangesetItem *item = m_items[id];
    DEBUG << "layoutRow: Looking at " << id.toStdString() << endl;

    int row = 0;
    int nparents = cs->parents().size();

    if (nparents > 0) {
        bool haveRow = false;
        foreach (QString parentId, cs->parents()) {

            if (!m_changesets.contains(parentId)) continue;
            if (!m_items.contains(parentId)) continue;

            if (!m_handled.contains(parentId)) {
                layoutRow(parentId);
            }

            ChangesetItem *parentItem = m_items[parentId];
            if (!haveRow || parentItem->row() < row) {
                row = parentItem->row();
                haveRow = true;
            }
        }
        row = row - 1;
    }

    // row is now an upper bound on our eventual row (because we want
    // to be above all parents).  But we also want to ensure we are
    // above all nodes that have earlier dates (to the nearest day).
    // m_rowDates maps each row to a date: use that.

    QString date;
    if (m_showDates) {
        date = cs->date();
    } else {
        date = cs->age();
    }
    while (m_rowDates.contains(row) && m_rowDates[row] != date) {
        --row;
    }

    // We have already laid out all nodes that have earlier timestamps
    // than this one, so we know (among other things) that we can
    // safely fill in this row has having this date, if it isn't in
    // the map yet (it cannot have an earlier date)

    if (!m_rowDates.contains(row)) {
        m_rowDates[row] = date;
    }

    // If we're the parent of the uncommitted item, make a note of our
    // row (we need it later, to avoid overwriting the connecting line)
    if (!m_uncommittedParents.empty() && m_uncommittedParents[0] == id) {
        m_uncommittedParentRow = row;
    }

    DEBUG << "putting " << cs->id().toStdString() << " at row " << row 
          << endl;

    item->setRow(row);
    m_handled.insert(id);
}

void Grapher::layoutCol(QString id)
{
    if (m_handled.contains(id)) {
        DEBUG << "Already looked at " << id.toStdString() << endl;
        return;
    }
    if (!m_changesets.contains(id)) {
        throw LayoutException(QString("Changeset %1 not in ID map").arg(id));
    }
    if (!m_items.contains(id)) {
        return;
    }

    Changeset *cs = m_changesets[id];
    DEBUG << "layoutCol: Looking at " << id.toStdString() << endl;

    ChangesetItem *item = m_items[id];

    int col = 0;
    int row = item->row();
    QString branch = cs->branch();

    int nparents = cs->parents().size();
    QString parentId;
    int parentsOnSameBranch = 0;

    switch (nparents) {

    case 0:
        col = m_branchHomes[cs->branch()];
        col = findAvailableColumn(row, col, true);
        break;

    case 1:
        parentId = cs->parents()[0];

        if (!m_changesets.contains(parentId) ||
            !m_changesets[parentId]->isOnBranch(branch)) {
            // new branch
            col = m_branchHomes[branch];
        } else if (m_items.contains(parentId)) {
            col = m_items[parentId]->column();
        }

        col = findAvailableColumn(row, col, true);
        break;

    case 2:
        // a merge: behave differently if parents are both on the same
        // branch (we also want to behave differently for nodes that
        // have multiple children on the same branch -- spreading them
        // out rather than having affinity to a specific branch)

        foreach (QString parentId, cs->parents()) {
            if (!m_changesets.contains(parentId)) continue;
            if (m_changesets[parentId]->isOnBranch(branch)) {
                if (m_items.contains(parentId)) {
                    ChangesetItem *parentItem = m_items[parentId];
                    col += parentItem->column();
                    parentsOnSameBranch++;
                }
            }
        }

        if (parentsOnSameBranch > 0) {
            col /= parentsOnSameBranch;
            col = findAvailableColumn(item->row(), col, true);
        } else {
            col = findAvailableColumn(item->row(), col, false);
        }
        break;
    }

    DEBUG << "putting " << cs->id().toStdString() << " at col " << col << endl;

    m_alloc[row].insert(col);
    item->setColumn(col);
    m_handled.insert(id);

    // If we're the first parent of the uncommitted item, it should be
    // given the same column as us (we already noted that its
    // connecting line would end at our row)

    if (m_uncommittedParents.contains(id)) {
        if (m_uncommittedParents[0] == id) {
            int ucol = findAvailableColumn(row-1, col, true);
            m_uncommitted->setColumn(ucol);
            m_haveAllocatedUncommittedColumn = true;
        }
        // also, if the uncommitted item has a different branch from
        // any of its parents, tell it to show the branch
        if (!cs->isOnBranch(m_uncommitted->branch())) {
            DEBUG << "Uncommitted branch " << m_uncommitted->branch()
                  << " differs from my branch " << cs->branch()
                  << ", asking it to show branch" << endl;
            m_uncommitted->setShowBranch(true);
        }
    }


    // Normally the children will lay out themselves, but we can do
    // a better job in some special cases:

    int nchildren = cs->children().size();

    // look for merging children and children distant from us but in a
    // straight line, and make sure nobody is going to overwrite their
    // connection lines

    foreach (QString childId, cs->children()) {
        DEBUG << "reserving connection line space" << endl;
        if (!m_items.contains(childId)) continue;
        Changeset *child = m_changesets[childId];
        int childRow = m_items[childId]->row();
        if (child->parents().size() > 1 ||
            child->isOnBranch(cs->branch())) {
            for (int r = row-1; r > childRow; --r) {
                m_alloc[r].insert(col);
            }
        }
    }

    // look for the case where exactly two children have the same
    // branch as us: split them to a little either side of our position

    if (nchildren > 1) {
        QList<QString> special;
        foreach (QString childId, cs->children()) {
            if (!m_items.contains(childId)) continue;
            Changeset *child = m_changesets[childId];
            if (child->isOnBranch(branch) &&
                child->parents().size() == 1) {
                special.push_back(childId);
            }
        }
        if (special.size() == 2) {
            DEBUG << "handling split-in-two for children " << special[0] << " and " << special[1] << endl;
            for (int i = 0; i < 2; ++i) {
                int off = i * 2 - 1; // 0 -> -1, 1 -> 1
                ChangesetItem *it = m_items[special[i]];
                it->setColumn(findAvailableColumn(it->row(), col + off, true));
                for (int r = row-1; r >= it->row(); --r) {
                    m_alloc[r].insert(it->column());
                }
                m_handled.insert(special[i]);
            }
        }
    }
}

bool Grapher::rangesConflict(const Range &r1, const Range &r2)
{
    // allow some additional space at edges.  we really ought also to
    // permit space at the end of a branch up to the point where the
    // merge happens
    int a1 = r1.first - 2, b1 = r1.second + 2;
    int a2 = r2.first - 2, b2 = r2.second + 2;
    if (a1 > b2 || b1 < a2) return false;
    if (a2 > b1 || b2 < a1) return false;
    return true;
}

void Grapher::allocateBranchHomes(Changesets csets)
{
    foreach (Changeset *cs, csets) {
        QString id = cs->id();
        if (!m_items.contains(id)) continue;
        ChangesetItem *item = m_items[id];
        QString branch = cs->branch();
        int row = item->row();
        if (!m_branchRanges.contains(branch)) {
            m_branchRanges[branch] = Range(row, row);
        } else {
            Range p = m_branchRanges[branch];
            if (row < p.first) p.first = row;
            if (row > p.second) p.second = row;
            m_branchRanges[branch] = p;
        }
    }

    m_branchHomes[""] = 0;
    m_branchHomes["default"] = 0;

    foreach (QString branch, m_branchRanges.keys()) {
        if (branch == "") continue;
        QSet<int> taken;
        taken.insert(0);
        Range myRange = m_branchRanges[branch];
        foreach (QString other, m_branchRanges.keys()) {
            if (other == branch || other == "") continue;
            Range otherRange = m_branchRanges[other];
            if (rangesConflict(myRange, otherRange)) {
                if (m_branchHomes.contains(other)) {
                    taken.insert(m_branchHomes[other]);
                }
            }
        }
        int home = 2;
        while (taken.contains(home)) {
            if (home > 0) {
                if (home % 2 == 1) {
                    home = -home;
                } else {
                    home = home + 1;
                }
            } else {
                if ((-home) % 2 == 1) {
                    home = home + 1;
                } else {
                    home = -(home-2);
                }
            }
        }
        m_branchHomes[branch] = home;
    }

    foreach (QString branch, m_branchRanges.keys()) {
        DEBUG << branch.toStdString() << ": " << m_branchRanges[branch].first << " - " << m_branchRanges[branch].second << ", home " << m_branchHomes[branch] << endl;
    }
}

static bool
compareChangesetsByDate(Changeset *const &a, Changeset *const &b)
{
    return a->timestamp() < b->timestamp();
}

ChangesetItem *
Grapher::getItemFor(Changeset *cs)
{
    if (!cs) return 0;
    return getItemFor(cs->id());
}

ChangesetItem *
Grapher::getItemFor(QString id)
{
    if (!m_items.contains(id)) return 0;
    return m_items[id];
}

void
Grapher::markClosedChangesets()
{
    // Ensure the closed branch changesets are all marked as closed.

    QSet<QString> deferred;

    foreach (QString id, m_closedIds) {
        markClosedChangesetsFrom(id, deferred);
//        std::cerr << "after closed id " << id << ": candidates now contains " << deferred.size() << " element(s)" << std::endl;
    }

    while (!deferred.empty()) {
        foreach (QString id, deferred) {
            markClosedChangesetsFrom(id, deferred);
            deferred.remove(id);
//        std::cerr << "after id " << id << ": deferred now contains " << deferred.size() << " element(s)" << std::endl;
        }
    }
}

void
Grapher::markClosedChangesetsFrom(QString id, QSet<QString> &deferred)
{
    // A changeset should be marked as closed (i) if it is in the list
    // of closed heads [and has no children]; or (ii) all of its
    // children that have the same branch name as it are marked as
    // closed [and there is at least one of those]

    if (!m_changesets.contains(id)) {
//        std::cerr << "no good" << std::endl;
        return;
    }

//    std::cerr << "looking at id " << id << std::endl;
            
    Changeset *cs = m_changesets[id];
    QString branch = cs->branch();
            
    bool closed = false;

    if (m_closedIds.contains(id)) {

        closed = true;

    } else {

        closed = false;
        foreach (QString childId, cs->children()) {
            if (!m_changesets.contains(childId)) {
                continue;
            }
            Changeset *ccs = m_changesets[childId];
            if (ccs->isOnBranch(branch)) {
                if (ccs->closed()) {
                    // closed becomes true only when we see a closed
                    // child on the same branch
                    closed = true;
                } else {
                    // and it becomes false as soon as we see any
                    // un-closed child on the same branch
                    closed = false;
                    break;
                }
            }
        }
    }

    if (closed) {
        // set closed on this cset and its direct simple parents
        QString csid = id;
        while (cs) {
            cs->setClosed(true);
            if (cs->parents().size() == 1) {
                QString pid = cs->parents()[0];
                if (!m_changesets.contains(pid)) break;
                cs = m_changesets[pid];
                if (cs->children().size() > 1) {
//                    std::cerr << "adding pid " << pid << " (it has more than one child)" << std::endl;
                    deferred.insert(pid); // examine later
                    cs = 0;
                }
            } else if (cs->parents().size() > 1) {
                foreach (QString pid, cs->parents()) {
//                    std::cerr << "recursing to pid " << pid << " (it is one of multiple parents)" << std::endl;
                    markClosedChangesetsFrom(pid, deferred);
                }
                cs = 0;
            } else {
                cs = 0;
            }
        }
    } else {
        cs->setClosed(false);
    }
    
//    std::cerr << "finished with id " << id << std::endl;
}

void Grapher::layout(Changesets csets,
                     QStringList uncommittedParents,
                     QString uncommittedBranch)
{
    m_changesets.clear();
    m_items.clear();
    m_alloc.clear();
    m_branchHomes.clear();

    m_uncommittedParents = uncommittedParents;
    m_haveAllocatedUncommittedColumn = false;
    m_uncommittedParentRow = 0;
    m_uncommitted = 0;

    DEBUG << "Grapher::layout: Have " << csets.size() << " changesets" << endl;

    if (csets.empty()) return;

    // Initialise changesets hash

    foreach (Changeset *cs, csets) {

        QString id = cs->id();

        if (id == "") {
            throw LayoutException("Changeset has no ID");
        }
        if (m_changesets.contains(id)) {
            DEBUG << "Duplicate changeset ID " << id
                  << " in Grapher::layout()" << endl;
            throw LayoutException(QString("Duplicate changeset ID %1").arg(id));
        }

        m_changesets[id] = cs;
    }
    
    // Set the children for each changeset

    foreach (Changeset *cs, csets) {
        QString id = cs->id();
        foreach (QString parentId, cs->parents()) {
            if (!m_changesets.contains(parentId)) continue;
            Changeset *parent = m_changesets[parentId];
            parent->addChild(id);
        }
    }
    
    // Ensure the closed branch changesets are all marked as closed.

    markClosedChangesets();

    // Create (but don't yet position) the changeset items

    foreach (Changeset *cs, csets) {
        if (cs->closed() && !m_showClosedBranches) continue;
        QString id = cs->id();
        ChangesetItem *item = new ChangesetItem(cs);
        item->setX(0);
        item->setY(0);
        item->setZValue(0);
        m_items[id] = item;
        m_scene->addChangesetItem(item);
    }
    
    // Ensure the closing changeset items are appropriately marked

    foreach (QString closedId, m_closedIds) {
        if (!m_items.contains(closedId)) continue;
        m_items[closedId]->setClosingCommit(true);
    }

    // Add the connecting lines

    foreach (Changeset *cs, csets) {
        QString id = cs->id();
        if (!m_items.contains(id)) continue;
        ChangesetItem *item = m_items[id];
        bool merge = (cs->parents().size() > 1);
        foreach (QString parentId, cs->parents()) {
            if (!m_changesets.contains(parentId)) continue;
            ConnectionItem *conn = new ConnectionItem();
            if (merge) conn->setConnectionType(ConnectionItem::Merge);
            conn->setChild(item);
            conn->setZValue(-1);
            if (m_items.contains(parentId)) {
                conn->setParent(m_items[parentId]);
            } else {
                conn->setMergedBranch(m_changesets[parentId]->branch());
            }
            m_scene->addItem(conn);
        }
    }

    // Add uncommitted item and connecting line as necessary

    if (!m_uncommittedParents.empty()) {

        m_uncommitted = new UncommittedItem();
        m_uncommitted->setBranch(uncommittedBranch);
        m_uncommitted->setZValue(10);
        m_scene->addUncommittedItem(m_uncommitted);

        bool haveParentOnBranch = false;
        foreach (QString p, m_uncommittedParents) {
            if (!m_items.contains(p)) continue;
            ConnectionItem *conn = new ConnectionItem();
            conn->setConnectionType(ConnectionItem::Merge);
            ChangesetItem *pitem = m_items[p];
            conn->setParent(pitem);
            conn->setChild(m_uncommitted);
            conn->setZValue(-1);
            m_scene->addItem(conn);
            if (pitem) {
                if (pitem->getChangeset()->isOnBranch(uncommittedBranch)) {
                    haveParentOnBranch = true;
                }
            }
        }

        // If the uncommitted item has no parents on the same branch,
        // tell it it has a new branch (the "show branch" flag is set
        // elsewhere for this item)
        m_uncommitted->setIsNewBranch(!haveParentOnBranch);

        // Uncommitted is a merge if it has more than one parent
        m_uncommitted->setIsMerge(m_uncommittedParents.size() > 1);
    }

    // Add the branch labels

    foreach (Changeset *cs, csets) {
        QString id = cs->id();
        if (!m_items.contains(id)) continue;
        ChangesetItem *item = m_items[id];
        bool haveChildOnSameBranch = false;
        foreach (QString childId, cs->children()) {
            Changeset *child = m_changesets[childId];
            if (child->branch() == cs->branch()) {
                haveChildOnSameBranch = true;
                break;
            }
        }
        item->setShowBranch(!haveChildOnSameBranch);
    }

    // We need to lay out the changesets in forward chronological
    // order.  We have no guarantees about the order in which
    // changesets appear in the list -- in a simple repository they
    // will generally be reverse chronological, but that's far from
    // guaranteed.  So, sort explicitly using the date comparator
    // above

    qStableSort(csets.begin(), csets.end(), compareChangesetsByDate);

    foreach (Changeset *cs, csets) {
        DEBUG << "id " << cs->id().toStdString() << ", ts " << cs->timestamp()
              << ", date " << cs->datetime().toStdString() << endl;
    }

    m_handled.clear();
    foreach (Changeset *cs, csets) {
        layoutRow(cs->id());
    }

    allocateBranchHomes(csets);

    m_handled.clear();
    foreach (Changeset *cs, csets) {
        foreach (QString parentId, cs->parents()) {
            if (!m_handled.contains(parentId) &&
                m_changesets.contains(parentId)) {
                layoutCol(parentId);
            }
        }
        layoutCol(cs->id());
    }

    // Find row and column extents.  We know that 0 is an upper bound
    // on row, and that mincol must be <= 0 and maxcol >= 0, so these
    // initial values are good

    int minrow = 0, maxrow = 0;
    int mincol = 0, maxcol = 0;

    foreach (int r, m_alloc.keys()) {
        if (r < minrow) minrow = r;
        if (r > maxrow) maxrow = r;
        ColumnSet &c = m_alloc[r];
        foreach (int i, c) {
            if (i < mincol) mincol = i;
            if (i > maxcol) maxcol = i;
        }
    }

    int datemincol = mincol, datemaxcol = maxcol;

    if (mincol == maxcol) {
        --datemincol;
        ++datemaxcol;
    } else if (m_alloc[minrow].contains(mincol)) {
        --datemincol;
    }

    // We've given the uncommitted item a column, but not a row yet --
    // it always goes at the top

    if (m_uncommitted) {
        --minrow;
        DEBUG << "putting uncommitted item at row " << minrow << endl;
        m_uncommitted->setRow(minrow);
    }

    // Changeset items that have nothing to either side of them can be
    // made double-width

    foreach (Changeset *cs, csets) {
        QString id = cs->id();
        if (!m_items.contains(id)) continue;
        ChangesetItem *item = m_items[id];
        if (isAvailable(item->row(), item->column()-1) &&
            isAvailable(item->row(), item->column()+1)) {
            item->setWide(true);
        }
    }

    if (m_uncommitted) {
        if (isAvailable(m_uncommitted->row(), m_uncommitted->column()-1) &&
            isAvailable(m_uncommitted->row(), m_uncommitted->column()+1)) {
            m_uncommitted->setWide(true);
        }
    }

    QString prevDate;
    int changeRow = 0;

    bool even = false;
    int n = 0;

    for (int row = minrow; row <= maxrow; ++row) {

        QString date = m_rowDates[row];
        n++;

        if (date != prevDate) {
            if (prevDate != "") {
                m_scene->addDateRange(prevDate, changeRow, n, even);
                even = !even;
            }
            prevDate = date;
            changeRow = row;
            n = 0;
        }
    }
    
    if (n > 0) {
        m_scene->addDateRange(prevDate, changeRow, n+1, even);
        even = !even;
    }

    m_scene->itemAddCompleted();
}