comparison mercurial/graphmod.py @ 28600:0d6137891114

graphmod: allow for different styles for different edge types

Rather than draw all edges as solid lines, allow for using different styles for
different edge types. For example you could use dotted lines for edges that
do not connect to a parent, and dashed lines when connecting to a grandparent
(implying missing nodes in between).

For example, setting the following configuration:

    [ui]
    graphstyle.grandparent = :
    graphstyle.missing = .

would result in a graph like this:

  o    changeset:   32:d06dffa21a31
  |\   parent:      27:886ed638191b
  | :  parent:      31:621d83e11f67
  | :
  o :  changeset:   31:621d83e11f67
  |\:  parent:      21:d42a756af44d
  | :  parent:      30:6e11cd4b648f
  | :
  o :    changeset:   30:6e11cd4b648f
  |\ \   parent:      28:44ecd0b9ae99
  | . :  parent:      29:cd9bb2be7593
  | . :
  o . :    changeset:   28:44ecd0b9ae99
  |\ \ \   parent:      1:6db2ef61d156
  | . . :  parent:      26:7f25b6c2f0b9
  | . . :
  o . . :    changeset:   26:7f25b6c2f0b9
  |\ \ \ \   parent:      18:1aa84d96232a
  | | . . :  parent:      25:91da8ed57247
  | | . . :
  | o-----+  changeset:   25:91da8ed57247
  | | . . :  parent:      21:d42a756af44d
  | | . . :  parent:      24:a9c19a3d96b7
  | | . . :
  | o . . :    changeset:   24:a9c19a3d96b7
  | |\ \ \ \   parent:      0:e6eb3150255d
  | | . . . :  parent:      23:a01cddf0766d
  | | . . . :
  | o---+ . :  changeset:   23:a01cddf0766d
  | | . . . :  parent:      1:6db2ef61d156
  | | . . . :  parent:      22:e0d9cccacb5d
  | | . . . :
  | o-------+  changeset:   22:e0d9cccacb5d
  | . . . . :  parent:      18:1aa84d96232a
  |/ / / / /   parent:      21:d42a756af44d
  | . . . :
  | . . . o    changeset:   21:d42a756af44d
  | . . . |\   parent:      19:31ddc2c1573b
  | . . . | |  parent:      20:d30ed6450e32
  | . . . | |
  +-+-------o  changeset:   20:d30ed6450e32
  | . . . |    parent:      0:e6eb3150255d
  | . . . |    parent:      18:1aa84d96232a
  | . . . |
  | . . . o    changeset:   19:31ddc2c1573b
  | . . . .\   parent:      15:1dda3f72782d
  | . . . . |  parent:      17:44765d7c06e0
  | . . . . |
  o---+---+ |  changeset:   18:1aa84d96232a
    . . . . |  parent:      1:6db2ef61d156
   / / / / /   parent:      15:1dda3f72782d
  . . . . .


Edge styles can be altered by setting the following one-character config options::

    [ui]
    graphstyle.parent = |
    graphstyle.grandparent = :
    graphstyle.missing = .

The default configuration leaves all 3 types set to |, leaving graph styles
unaffected.

This is part of the work towards moving smartlog upstream; currently smartlog
injects extra nodes into the graph to indicate grandparent relationships (nodes
elided).

28599:0e7a929754aa

CHANGESET = 'C'
PARENT = 'P'
GRANDPARENT = 'G'
MISSINGPARENT = 'M'

def groupbranchiter(revs, parentsfunc, firstbranch=()):
    """Yield revisions from heads to roots one (topo) branch at a time.

    This function aims to be used by a graph generator that wishes to minimize

    for ptype, parent in parents:
        if parent in seen:
            knownparents.append(parent)
        else:
            newparents.append(parent)

    ncols = len(seen)
    nextseen = seen[:]
    nextseen[nodeidx:nodeidx + 1] = newparents
    edges = [(nodeidx, nextseen.index(p)) for p in knownparents if p != nullrev]

    while len(newparents) > 2:
        # ascii() only knows how to add or remove a single column between two
        # calls. Nodes with more than two parents break this constraint so we
        # introduce intermediate expansion lines to grow the active node list

        edges.append((nodeidx, nodeidx))
    if len(newparents) > 1:
        edges.append((nodeidx, nodeidx + 1))
    nmorecols = len(nextseen) - ncols
    seen[:] = nextseen
    yield (type, char, lines, (nodeidx, edges, ncols, nmorecols))

def _fixlongrightedges(edges):
    for (i, (start, end)) in enumerate(edges):
        if end > start:
            edges[i] = (start, end + 1)

def _getnodelineedgestail(
        node_index, p_node_index, n_columns, n_columns_diff, p_diff, fix_tail):
    if fix_tail and n_columns_diff == p_diff and n_columns_diff != 0:
        # Still going in the same non-vertical direction.
        if n_columns_diff == -1:
            start = max(node_index + 1, p_node_index)
            tail = ["|", " "] * (start - node_index - 1)
            tail.extend(["/", " "] * (n_columns - start))
            return tail
        else:
            return ["\\", " "] * (n_columns - node_index - 1)
    else:
        return ["|", " "] * (n_columns - node_index - 1)

def _drawedges(edges, nodeline, interline):
    for (start, end) in edges:
        if start == end + 1:
            interline[2 * end + 1] = "/"
        elif start == end - 1:
            interline[2 * start + 1] = "\\"
        elif start == end:
            interline[2 * start] = "|"
        else:
            if 2 * end >= len(nodeline):
                continue
            nodeline[2 * end] = "+"
            if start > end:
                (start, end) = (end, start)
            for i in range(2 * start + 1, 2 * end):
                if nodeline[i] != "+":
                    nodeline[i] = "-"

def _getpaddingline(ni, n_columns, edges):
    line = []
    line.extend(["|", " "] * ni)
    if (ni, ni - 1) in edges or (ni, ni) in edges:
        # (ni, ni - 1)      (ni, ni)
        # | | | |           | | | |
        # +---o |           | o---+
        # | | c |           | c | |
        # | |/ /            | |/ /
        # | | |             | | |
        c = "|"
    else:
        c = " "
    line.extend([c, " "])
    line.extend(["|", " "] * (n_columns - ni - 1))
    return line

def asciistate():
    """returns the initial value for the "state" argument to ascii()"""
    return {'seen': [], 'lastcoldiff': 0, 'lastindex': 0}

def ascii(ui, state, type, char, text, coldata):
    """prints an ASCII graph of the DAG

    takes the following arguments (one call per node in the graph):

      - The difference between the number of columns (ongoing edges)
        in the next revision and the number of columns (ongoing edges)
        in the current revision. That is: -1 means one column removed;
        0 means no columns added or removed; 1 means one column added.
    """

    idx, edges, ncols, coldiff = coldata
    assert -2 < coldiff < 2
    if coldiff == -1:
        # Transform
        #
        #     | | |        | | |
        #     o | |  into  o---+

    #     | |/ /           | |/ /
    #     o | |            o | |
    fix_nodeline_tail = len(text) <= 2 and not add_padding_line

    # nodeline is the line containing the node character (typically o)
    nodeline = ["|", " "] * idx
    nodeline.extend([char, " "])

    nodeline.extend(
        _getnodelineedgestail(idx, state['lastindex'], ncols, coldiff,
                              state['lastcoldiff'], fix_nodeline_tail))

    # shift_interline is the line containing the non-vertical
    # edges between this entry and the next
    shift_interline = ["|", " "] * idx
    if coldiff == -1:
        n_spaces = 1
        edge_ch = "/"
    elif coldiff == 0:
        n_spaces = 2
        edge_ch = "|"
    else:
        n_spaces = 3
        edge_ch = "\\"
    shift_interline.extend(n_spaces * [" "])
    shift_interline.extend([edge_ch, " "] * (ncols - idx - 1))

    # draw edges from the current node to its parents
    _drawedges(edges, nodeline, shift_interline)

    # lines is the list of all graph lines to print
    lines = [nodeline]
    if add_padding_line:
        lines.append(_getpaddingline(idx, ncols, edges))
    lines.append(shift_interline)

    # make sure that there are as many graph lines as there are
    # log strings
    while len(text) < len(lines):
        text.append("")
    if len(lines) < len(text):
        extra_interline = ["|", " "] * (ncols + coldiff)
        while len(lines) < len(text):
            lines.append(extra_interline)

    # print lines
    indentation_level = max(ncols, ncols + coldiff)

28600:0d6137891114

CHANGESET = 'C'
PARENT = 'P'
GRANDPARENT = 'G'
MISSINGPARENT = 'M'
EDGES = {PARENT: '|', GRANDPARENT: '|', MISSINGPARENT: '|'}

def groupbranchiter(revs, parentsfunc, firstbranch=()):
    """Yield revisions from heads to roots one (topo) branch at a time.

    This function aims to be used by a graph generator that wishes to minimize

    for ptype, parent in parents:
        if parent in seen:
            knownparents.append(parent)
        else:
            newparents.append(parent)
            state['edges'][parent] = state['styles'].get(ptype, '|')

    ncols = len(seen)
    nextseen = seen[:]
    nextseen[nodeidx:nodeidx + 1] = newparents
    edges = [(nodeidx, nextseen.index(p))
             for p in knownparents if p != nullrev]

    while len(newparents) > 2:
        # ascii() only knows how to add or remove a single column between two
        # calls. Nodes with more than two parents break this constraint so we
        # introduce intermediate expansion lines to grow the active node list

        edges.append((nodeidx, nodeidx))
    if len(newparents) > 1:
        edges.append((nodeidx, nodeidx + 1))
    nmorecols = len(nextseen) - ncols
    seen[:] = nextseen
    # remove current node from edge characters, no longer needed
    state['edges'].pop(rev, None)
    yield (type, char, lines, (nodeidx, edges, ncols, nmorecols))

def _fixlongrightedges(edges):
    for (i, (start, end)) in enumerate(edges):
        if end > start:
            edges[i] = (start, end + 1)

def _getnodelineedgestail(
        echars, idx, pidx, ncols, coldiff, pdiff, fix_tail):
    if fix_tail and coldiff == pdiff and coldiff != 0:
        # Still going in the same non-vertical direction.
        if coldiff == -1:
            start = max(idx + 1, pidx)
            tail = echars[idx * 2:(start - 1) * 2]
            tail.extend(["/", " "] * (ncols - start))
            return tail
        else:
            return ["\\", " "] * (ncols - idx - 1)
    else:
        remainder = (ncols - idx - 1)
        return echars[-(remainder * 2):] if remainder > 0 else []

def _drawedges(echars, edges, nodeline, interline):
    for (start, end) in edges:
        if start == end + 1:
            interline[2 * end + 1] = "/"
        elif start == end - 1:
            interline[2 * start + 1] = "\\"
        elif start == end:
            interline[2 * start] = echars[2 * start]
        else:
            if 2 * end >= len(nodeline):
                continue
            nodeline[2 * end] = "+"
            if start > end:
                (start, end) = (end, start)
            for i in range(2 * start + 1, 2 * end):
                if nodeline[i] != "+":
                    nodeline[i] = "-"

def _getpaddingline(echars, idx, ncols, edges):
    # all edges up to the current node
    line = echars[:idx * 2]
    # an edge for the current node, if there is one
    if (idx, idx - 1) in edges or (idx, idx) in edges:
        # (idx, idx - 1)      (idx, idx)
        # | | | |           | | | |
        # +---o |           | o---+
        # | | X |           | X | |
        # | |/ /            | |/ /
        # | | |             | | |
        line.extend(echars[idx * 2:(idx + 1) * 2])
    else:
        line.extend('  ')
    # all edges to the right of the current node
    remainder = ncols - idx - 1
    if remainder > 0:
        line.extend(echars[-(remainder * 2):])
    return line

def asciistate():
    """returns the initial value for the "state" argument to ascii()"""
    return {
        'seen': [],
        'edges': {},
        'lastcoldiff': 0,
        'lastindex': 0,
        'styles': EDGES.copy(),
    }

def ascii(ui, state, type, char, text, coldata):
    """prints an ASCII graph of the DAG

    takes the following arguments (one call per node in the graph):

      - The difference between the number of columns (ongoing edges)
        in the next revision and the number of columns (ongoing edges)
        in the current revision. That is: -1 means one column removed;
        0 means no columns added or removed; 1 means one column added.
    """
    idx, edges, ncols, coldiff = coldata
    assert -2 < coldiff < 2

    edgemap, seen = state['edges'], state['seen']
    # Be tolerant of history issues; make sure we have at least ncols + coldiff
    # elements to work with. See test-glog.t for broken history test cases.
    echars = [c for p in seen for c in (edgemap.get(p, '|'), ' ')]
    echars.extend(('|', ' ') * max(ncols + coldiff - len(seen), 0))

    if coldiff == -1:
        # Transform
        #
        #     | | |        | | |
        #     o | |  into  o---+

    #     | |/ /           | |/ /
    #     o | |            o | |
    fix_nodeline_tail = len(text) <= 2 and not add_padding_line

    # nodeline is the line containing the node character (typically o)
    nodeline = echars[:idx * 2]
    nodeline.extend([char, " "])

    nodeline.extend(
        _getnodelineedgestail(
            echars, idx, state['lastindex'], ncols, coldiff,
            state['lastcoldiff'], fix_nodeline_tail))

    # shift_interline is the line containing the non-vertical
    # edges between this entry and the next
    shift_interline = echars[:idx * 2]
    shift_interline.extend(' ' * (2 + coldiff))
    count = ncols - idx - 1
    if coldiff == -1:
        shift_interline.extend('/ ' * count)
    elif coldiff == 0:
        shift_interline.extend(echars[(idx + 1) * 2:ncols * 2])
    else:
        shift_interline.extend(r'\ ' * count)

    # draw edges from the current node to its parents
    _drawedges(echars, edges, nodeline, shift_interline)

    # lines is the list of all graph lines to print
    lines = [nodeline]
    if add_padding_line:
        lines.append(_getpaddingline(echars, idx, ncols, edges))
    lines.append(shift_interline)

    # make sure that there are as many graph lines as there are
    # log strings
    while len(text) < len(lines):
        text.append("")
    if len(lines) < len(text):
        extra_interline = echars[:(ncols + coldiff) * 2]
        while len(lines) < len(text):
            lines.append(extra_interline)

    # print lines
    indentation_level = max(ncols, ncols + coldiff)