annotate mercurial/crecord.py @ 46149:294d5aca4ff5

copies: iterate over children directly (instead of parents)

Before this change we would gather all parent → child edges and iterate on
all parent, gathering copy information for children and aggregating them from
there.

They are not strict requirement for edges to be processed in that specific
order. We could also simply iterate over all "children" revision and aggregate
data from both parents at the same time. This patch does that.

It make various things simpler:

 * since both parents are processed at the same time, we no longer need to
   cache data for merge (see next changeset for details),

 * we no longer need nested loop to process data,

 * we no longer need to store partial merge data for a rev from distinct loop
   interaction to another when processing merges,

 * we no longer need to build a full parent -> children mapping (we only rely on
   a simpler "parent -> number of children" map (for memory efficiency),

 * the data access pattern is now simpler (from lower revisions to higher
   revisions) and entirely predicable. That predictability open the way to
   prefetching and parallel processing.

So that new iterations order requires simpler code and open the way to
interesting optimisation.

The effect on performance is quite good. In the worse case, we don't see any
significant negative impact. And in the best case, the reduction of roundtrip
to Python provide us with a significant speed. Some example below:

Repo            Case                                  Source-Rev   Dest-Rev      # of revisions  old time    new time      Difference    Factor    time per rev
---------------------------------------------------------------------------------------------------------------------------------------------------------------
mozilla-try     x00000_revs_x00000_added_0_copies     dc8a3ca7010e d16fde900c9c :  34414 revs,   0.962867 s,   0.502584 s,  -0.460283 s, × 0.5220,    14 µs/rev
mozilla-try     x0000_revs_xx000_added_x_copies       156f6e2674f2 4d0f2c178e66 :   8598 revs,   0.110717 s,   0.076323 s,  -0.034394 s, × 0.6894,     8 µs/rev



# full comparison between the previous changeset and this one

Repo            Case                                  Source-Rev   Dest-Rev      # of revisions  old time    new time      Difference    Factor    time per rev
---------------------------------------------------------------------------------------------------------------------------------------------------------------
mercurial       x_revs_x_added_0_copies               ad6b123de1c7 39cfcef4f463 :      1 revs,   0.000048 s,   0.000041 s,  -0.000007 s, × 0.8542,    41 µs/rev
mercurial       x_revs_x_added_x_copies               2b1c78674230 0c1d10351869 :      6 revs,   0.000153 s,   0.000102 s,  -0.000051 s, × 0.6667,    17 µs/rev
mercurial       x000_revs_x000_added_x_copies         81f8ff2a9bf2 dd3267698d84 :   1032 revs,   0.004209 s,   0.004254 s,  +0.000045 s, × 1.0107,     4 µs/rev
pypy            x_revs_x_added_0_copies               aed021ee8ae8 099ed31b181b :      9 revs,   0.000203 s,   0.000282 s,  +0.000079 s, × 1.3892,    31 µs/rev
pypy            x_revs_x000_added_0_copies            4aa4e1f8e19a 359343b9ac0e :      1 revs,   0.000059 s,   0.000048 s,  -0.000011 s, × 0.8136,    48 µs/rev
pypy            x_revs_x_added_x_copies               ac52eb7bbbb0 72e022663155 :      7 revs,   0.000194 s,   0.000211 s,  +0.000017 s, × 1.0876,    30 µs/rev
pypy            x_revs_x00_added_x_copies             c3b14617fbd7 ace7255d9a26 :      1 revs,   0.000380 s,   0.000375 s,  -0.000005 s, × 0.9868,   375 µs/rev
pypy            x_revs_x000_added_x000_copies         df6f7a526b60 a83dc6a2d56f :      6 revs,   0.010588 s,   0.010574 s,  -0.000014 s, × 0.9987,  1762 µs/rev
pypy            x000_revs_xx00_added_0_copies         89a76aede314 2f22446ff07e :   4785 revs,   0.048961 s,   0.049974 s,  +0.001013 s, × 1.0207,    10 µs/rev
pypy            x000_revs_x000_added_x_copies         8a3b5bfd266e 2c68e87c3efe :   6780 revs,   0.083612 s,   0.084300 s,  +0.000688 s, × 1.0082,    12 µs/rev
pypy            x000_revs_x000_added_x000_copies      89a76aede314 7b3dda341c84 :   5441 revs,   0.058579 s,   0.060128 s,  +0.001549 s, × 1.0264,    11 µs/rev
pypy            x0000_revs_x_added_0_copies           d1defd0dc478 c9cb1334cc78 :  43645 revs,   0.736783 s,   0.686542 s,  -0.050241 s, × 0.9318,    15 µs/rev
pypy            x0000_revs_xx000_added_0_copies       bf2c629d0071 4ffed77c095c :      2 revs,   0.022050 s,   0.009277 s,  -0.012773 s, × 0.4207,  4638 µs/rev
pypy            x0000_revs_xx000_added_x000_copies    08ea3258278e d9fa043f30c0 :  11316 revs,   0.120800 s,   0.114733 s,  -0.006067 s, × 0.9498,    10 µs/rev
netbeans        x_revs_x_added_0_copies               fb0955ffcbcd a01e9239f9e7 :      2 revs,   0.000140 s,   0.000081 s,  -0.000059 s, × 0.5786,    40 µs/rev
netbeans        x_revs_x000_added_0_copies            6f360122949f 20eb231cc7d0 :      2 revs,   0.000114 s,   0.000107 s,  -0.000007 s, × 0.9386,    53 µs/rev
netbeans        x_revs_x_added_x_copies               1ada3faf6fb6 5a39d12eecf4 :      3 revs,   0.000224 s,   0.000173 s,  -0.000051 s, × 0.7723,    57 µs/rev
netbeans        x_revs_x00_added_x_copies             35be93ba1e2c 9eec5e90c05f :      9 revs,   0.000723 s,   0.000698 s,  -0.000025 s, × 0.9654,    77 µs/rev
netbeans        x000_revs_xx00_added_0_copies         eac3045b4fdd 51d4ae7f1290 :   1421 revs,   0.009665 s,   0.009248 s,  -0.000417 s, × 0.9569,     6 µs/rev
netbeans        x000_revs_x000_added_x_copies         e2063d266acd 6081d72689dc :   1533 revs,   0.014820 s,   0.015446 s,  +0.000626 s, × 1.0422,    10 µs/rev
netbeans        x000_revs_x000_added_x000_copies      ff453e9fee32 411350406ec2 :   5750 revs,   0.076049 s,   0.074373 s,  -0.001676 s, × 0.9780,    12 µs/rev
netbeans        x0000_revs_xx000_added_x000_copies    588c2d1ced70 1aad62e59ddd :  66949 revs,   0.683603 s,   0.639870 s,  -0.043733 s, × 0.9360,     9 µs/rev
mozilla-central x_revs_x_added_0_copies               3697f962bb7b 7015fcdd43a2 :      2 revs,   0.000161 s,   0.000088 s,  -0.000073 s, × 0.5466,    44 µs/rev
mozilla-central x_revs_x000_added_0_copies            dd390860c6c9 40d0c5bed75d :      8 revs,   0.000234 s,   0.000199 s,  -0.000035 s, × 0.8504,    24 µs/rev
mozilla-central x_revs_x_added_x_copies               8d198483ae3b 14207ffc2b2f :      9 revs,   0.000247 s,   0.000171 s,  -0.000076 s, × 0.6923,    19 µs/rev
mozilla-central x_revs_x00_added_x_copies             98cbc58cc6bc 446a150332c3 :      7 revs,   0.000630 s,   0.000592 s,  -0.000038 s, × 0.9397,    84 µs/rev
mozilla-central x_revs_x000_added_x000_copies         3c684b4b8f68 0a5e72d1b479 :      3 revs,   0.003286 s,   0.003151 s,  -0.000135 s, × 0.9589,  1050 µs/rev
mozilla-central x_revs_x0000_added_x0000_copies       effb563bb7e5 c07a39dc4e80 :      6 revs,   0.062441 s,   0.061612 s,  -0.000829 s, × 0.9867, 10268 µs/rev
mozilla-central x000_revs_xx00_added_0_copies         6100d773079a 04a55431795e :   1593 revs,   0.005423 s,   0.005381 s,  -0.000042 s, × 0.9923,     3 µs/rev
mozilla-central x000_revs_x000_added_x_copies         9f17a6fc04f9 2d37b966abed :     41 revs,   0.005919 s,   0.003742 s,  -0.002177 s, × 0.6322,    91 µs/rev
mozilla-central x000_revs_x000_added_x000_copies      7c97034feb78 4407bd0c6330 :   7839 revs,   0.062597 s,   0.061983 s,  -0.000614 s, × 0.9902,     7 µs/rev
mozilla-central x0000_revs_xx000_added_0_copies       9eec5917337d 67118cc6dcad :    615 revs,   0.043551 s,   0.019861 s,  -0.023690 s, × 0.4560,    32 µs/rev
mozilla-central x0000_revs_xx000_added_x000_copies    f78c615a656c 96a38b690156 :  30263 revs,   0.192475 s,   0.188101 s,  -0.004374 s, × 0.9773,     6 µs/rev
mozilla-central x00000_revs_x0000_added_x0000_copies  6832ae71433c 4c222a1d9a00 : 153721 revs,   1.955575 s,   1.806696 s,  -0.148879 s, × 0.9239,    11 µs/rev
mozilla-central x00000_revs_x00000_added_x000_copies  76caed42cf7c 1daa622bbe42 : 204976 revs,   2.886501 s,   2.682987 s,  -0.203514 s, × 0.9295,    13 µs/rev
mozilla-try     x_revs_x_added_0_copies               aaf6dde0deb8 9790f499805a :      2 revs,   0.001181 s,   0.000852 s,  -0.000329 s, × 0.7214,   426 µs/rev
mozilla-try     x_revs_x000_added_0_copies            d8d0222927b4 5bb8ce8c7450 :      2 revs,   0.001189 s,   0.000859 s,  -0.000330 s, × 0.7225,   429 µs/rev
mozilla-try     x_revs_x_added_x_copies               092fcca11bdb 936255a0384a :      4 revs,   0.000563 s,   0.000150 s,  -0.000413 s, × 0.2664,    37 µs/rev
mozilla-try     x_revs_x00_added_x_copies             b53d2fadbdb5 017afae788ec :      2 revs,   0.001548 s,   0.001158 s,  -0.000390 s, × 0.7481,   579 µs/rev
mozilla-try     x_revs_x000_added_x000_copies         20408ad61ce5 6f0ee96e21ad :      1 revs,   0.027782 s,   0.027240 s,  -0.000542 s, × 0.9805, 27240 µs/rev
mozilla-try     x_revs_x0000_added_x0000_copies       effb563bb7e5 c07a39dc4e80 :      6 revs,   0.062781 s,   0.062824 s,  +0.000043 s, × 1.0007, 10470 µs/rev
mozilla-try     x000_revs_xx00_added_0_copies         6100d773079a 04a55431795e :   1593 revs,   0.005778 s,   0.005463 s,  -0.000315 s, × 0.9455,     3 µs/rev
mozilla-try     x000_revs_x000_added_x_copies         9f17a6fc04f9 2d37b966abed :     41 revs,   0.006192 s,   0.004238 s,  -0.001954 s, × 0.6844,   103 µs/rev
mozilla-try     x000_revs_x000_added_x000_copies      1346fd0130e4 4c65cbdabc1f :   6657 revs,   0.065391 s,   0.064113 s,  -0.001278 s, × 0.9805,     9 µs/rev
mozilla-try     x0000_revs_x_added_0_copies           63519bfd42ee a36a2a865d92 :  40314 revs,   0.317216 s,   0.294063 s,  -0.023153 s, × 0.9270,     7 µs/rev
mozilla-try     x0000_revs_x_added_x_copies           9fe69ff0762d bcabf2a78927 :  38690 revs,   0.303119 s,   0.281493 s,  -0.021626 s, × 0.9287,     7 µs/rev
mozilla-try     x0000_revs_xx000_added_x_copies       156f6e2674f2 4d0f2c178e66 :   8598 revs,   0.110717 s,   0.076323 s,  -0.034394 s, × 0.6894,     8 µs/rev
mozilla-try     x0000_revs_xx000_added_0_copies       9eec5917337d 67118cc6dcad :    615 revs,   0.045739 s,   0.020390 s,  -0.025349 s, × 0.4458,    33 µs/rev
mozilla-try     x0000_revs_xx000_added_x000_copies    89294cd501d9 7ccb2fc7ccb5 :  97052 revs,   3.098021 s,   3.023879 s,  -0.074142 s, × 0.9761,    31 µs/rev
mozilla-try     x0000_revs_x0000_added_x0000_copies   e928c65095ed e951f4ad123a :  52031 revs,   0.771480 s,   0.735549 s,  -0.035931 s, × 0.9534,    14 µs/rev
mozilla-try     x00000_revs_x_added_0_copies          6a320851d377 1ebb79acd503 : 363753 revs,  18.813422 s,  18.568900 s,  -0.244522 s, × 0.9870,    51 µs/rev
mozilla-try     x00000_revs_x00000_added_0_copies     dc8a3ca7010e d16fde900c9c :  34414 revs,   0.962867 s,   0.502584 s,  -0.460283 s, × 0.5220,    14 µs/rev
mozilla-try     x00000_revs_x_added_x_copies          5173c4b6f97c 95d83ee7242d : 362229 revs,  18.684923 s,  18.356645 s,  -0.328278 s, × 0.9824,    50 µs/rev
mozilla-try     x00000_revs_x000_added_x_copies       9126823d0e9c ca82787bb23c : 359344 revs,  18.296305 s,  18.250393 s,  -0.045912 s, × 0.9975,    50 µs/rev
mozilla-try     x00000_revs_x0000_added_x0000_copies  8d3fafa80d4b eb884023b810 : 192665 revs,   3.061887 s,   2.792459 s,  -0.269428 s, × 0.9120,    14 µs/rev
mozilla-try     x00000_revs_x00000_added_x0000_copies 1b661134e2ca 1ae03d022d6d : 228985 revs, 103.869641 s, 107.697264 s,  +3.827623 s, × 1.0369,   470 µs/rev
mozilla-try     x00000_revs_x00000_added_x000_copies  9b2a99adc05e 8e29777b48e6 : 382065 revs,  64.262957 s,  63.961040 s,  -0.301917 s, × 0.9953,   167 µs/rev

Differential Revision: https://phab.mercurial-scm.org/D9422

# stuff related specifically to patch manipulation / parsing
#
# Copyright 2008 Mark Edgington <[e-mail]>
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.
#
# This code is based on the Mark Edgington's crecord extension.
# (Itself based on Bryan O'Sullivan's record extension.)

from __future__ import absolute_import

import os
import re
import signal

from .i18n import _
from .pycompat import (
    getattr,
    open,
)
from . import (
    diffhelper,
    encoding,
    error,
    patch as patchmod,
    pycompat,
    scmutil,
    util,
)
from .utils import stringutil

stringio = util.stringio

# patch comments based on the git one
diffhelptext = _(
    """# To remove '-' lines, make them ' ' lines (context).
# To remove '+' lines, delete them.
# Lines starting with # will be removed from the patch.
"""
)

hunkhelptext = _(
    """#
# If the patch applies cleanly, the edited hunk will immediately be
# added to the record list. If it does not apply cleanly, a rejects file
# will be generated. You can use that when you try again. If all lines
# of the hunk are removed, then the edit is aborted and the hunk is left
# unchanged.
"""
)

patchhelptext = _(
    """#
# If the patch applies cleanly, the edited patch will immediately
# be finalised. If it does not apply cleanly, rejects files will be
# generated. You can use those when you try again.
"""
)

try:
    import curses
    import curses.ascii

    curses.error
except (ImportError, AttributeError):
    curses = False


class fallbackerror(error.Abort):
    """Error that indicates the client should try to fallback to text mode."""

    # Inherits from error.Abort so that existing behavior is preserved if the
    # calling code does not know how to fallback.


def checkcurses(ui):
    """Return True if the user wants to use curses

    This method returns True if curses is found (and that python is built with
    it) and that the user has the correct flag for the ui.
    """
    return curses and ui.interface(b"chunkselector") == b"curses"


class patchnode(object):
    """abstract class for patch graph nodes
    (i.e. patchroot, header, hunk, hunkline)
    """

    def firstchild(self):
        raise NotImplementedError(b"method must be implemented by subclass")

    def lastchild(self):
        raise NotImplementedError(b"method must be implemented by subclass")

    def allchildren(self):
        """Return a list of all of the direct children of this node"""
        raise NotImplementedError(b"method must be implemented by subclass")

    def nextsibling(self):
        """
        Return the closest next item of the same type where there are no items
        of different types between the current item and this closest item.
        If no such item exists, return None.
        """
        raise NotImplementedError(b"method must be implemented by subclass")

    def prevsibling(self):
        """
        Return the closest previous item of the same type where there are no
        items of different types between the current item and this closest item.
        If no such item exists, return None.
        """
        raise NotImplementedError(b"method must be implemented by subclass")

    def parentitem(self):
        raise NotImplementedError(b"method must be implemented by subclass")

    def nextitem(self, skipfolded=True):
        """
        Try to return the next item closest to this item, regardless of item's
        type (header, hunk, or hunkline).

        If skipfolded == True, and the current item is folded, then the child
        items that are hidden due to folding will be skipped when determining
        the next item.

        If it is not possible to get the next item, return None.
        """
        try:
            itemfolded = self.folded
        except AttributeError:
            itemfolded = False
        if skipfolded and itemfolded:
            nextitem = self.nextsibling()
            if nextitem is None:
                try:
                    nextitem = self.parentitem().nextsibling()
                except AttributeError:
                    nextitem = None
            return nextitem
        else:
            # try child
            item = self.firstchild()
            if item is not None:
                return item

            # else try next sibling
            item = self.nextsibling()
            if item is not None:
                return item

            try:
                # else try parent's next sibling
                item = self.parentitem().nextsibling()
                if item is not None:
                    return item

                # else return grandparent's next sibling (or None)
                return self.parentitem().parentitem().nextsibling()

            except AttributeError:  # parent and/or grandparent was None
                return None

    def previtem(self):
        """
        Try to return the previous item closest to this item, regardless of
        item's type (header, hunk, or hunkline).

        If it is not possible to get the previous item, return None.
        """
        # try previous sibling's last child's last child,
        # else try previous sibling's last child, else try previous sibling
        prevsibling = self.prevsibling()
        if prevsibling is not None:
            prevsiblinglastchild = prevsibling.lastchild()
            if (prevsiblinglastchild is not None) and not prevsibling.folded:
                prevsiblinglclc = prevsiblinglastchild.lastchild()
                if (
                    prevsiblinglclc is not None
                ) and not prevsiblinglastchild.folded:
                    return prevsiblinglclc
                else:
                    return prevsiblinglastchild
            else:
                return prevsibling

        # try parent (or None)
        return self.parentitem()


class patch(patchnode, list):  # todo: rename patchroot
    """
    list of header objects representing the patch.
    """

    def __init__(self, headerlist):
        self.extend(headerlist)
        # add parent patch object reference to each header
        for header in self:
            header.patch = self


class uiheader(patchnode):
    """patch header

    xxx shouldn't we move this to mercurial/patch.py ?
    """

    def __init__(self, header):
        self.nonuiheader = header
        # flag to indicate whether to apply this chunk
        self.applied = True
        # flag which only affects the status display indicating if a node's
        # children are partially applied (i.e. some applied, some not).
        self.partial = False

        # flag to indicate whether to display as folded/unfolded to user
        self.folded = True

        # list of all headers in patch
        self.patch = None

        # flag is False if this header was ever unfolded from initial state
        self.neverunfolded = True
        self.hunks = [uihunk(h, self) for h in self.hunks]

    def prettystr(self):
        x = stringio()
        self.pretty(x)
        return x.getvalue()

    def nextsibling(self):
        numheadersinpatch = len(self.patch)
        indexofthisheader = self.patch.index(self)

        if indexofthisheader < numheadersinpatch - 1:
            nextheader = self.patch[indexofthisheader + 1]
            return nextheader
        else:
            return None

    def prevsibling(self):
        indexofthisheader = self.patch.index(self)
        if indexofthisheader > 0:
            previousheader = self.patch[indexofthisheader - 1]
            return previousheader
        else:
            return None

    def parentitem(self):
        """
        there is no 'real' parent item of a header that can be selected,
        so return None.
        """
        return None

    def firstchild(self):
        """return the first child of this item, if one exists.  otherwise
        None."""
        if len(self.hunks) > 0:
            return self.hunks[0]
        else:
            return None

    def lastchild(self):
        """return the last child of this item, if one exists.  otherwise
        None."""
        if len(self.hunks) > 0:
            return self.hunks[-1]
        else:
            return None

    def allchildren(self):
        """return a list of all of the direct children of this node"""
        return self.hunks

    def __getattr__(self, name):
        return getattr(self.nonuiheader, name)


class uihunkline(patchnode):
    """represents a changed line in a hunk"""

    def __init__(self, linetext, hunk):
        self.linetext = linetext
        self.applied = True
        # the parent hunk to which this line belongs
        self.hunk = hunk
        # folding lines currently is not used/needed, but this flag is needed
        # in the previtem method.
        self.folded = False

    def prettystr(self):
        return self.linetext

    def nextsibling(self):
        numlinesinhunk = len(self.hunk.changedlines)
        indexofthisline = self.hunk.changedlines.index(self)

        if indexofthisline < numlinesinhunk - 1:
            nextline = self.hunk.changedlines[indexofthisline + 1]
            return nextline
        else:
            return None

    def prevsibling(self):
        indexofthisline = self.hunk.changedlines.index(self)
        if indexofthisline > 0:
            previousline = self.hunk.changedlines[indexofthisline - 1]
            return previousline
        else:
            return None

    def parentitem(self):
        """return the parent to the current item"""
        return self.hunk

    def firstchild(self):
        """return the first child of this item, if one exists.  otherwise
        None."""
        # hunk-lines don't have children
        return None

    def lastchild(self):
        """return the last child of this item, if one exists.  otherwise
        None."""
        # hunk-lines don't have children
        return None


class uihunk(patchnode):
    """ui patch hunk, wraps a hunk and keep track of ui behavior """

    maxcontext = 3

    def __init__(self, hunk, header):
        self._hunk = hunk
        self.changedlines = [uihunkline(line, self) for line in hunk.hunk]
        self.header = header
        # used at end for detecting how many removed lines were un-applied
        self.originalremoved = self.removed

        # flag to indicate whether to display as folded/unfolded to user
        self.folded = True
        # flag to indicate whether to apply this chunk
        self.applied = True
        # flag which only affects the status display indicating if a node's
        # children are partially applied (i.e. some applied, some not).
        self.partial = False

    def nextsibling(self):
        numhunksinheader = len(self.header.hunks)
        indexofthishunk = self.header.hunks.index(self)

        if indexofthishunk < numhunksinheader - 1:
            nexthunk = self.header.hunks[indexofthishunk + 1]
            return nexthunk
        else:
            return None

    def prevsibling(self):
        indexofthishunk = self.header.hunks.index(self)
        if indexofthishunk > 0:
            previoushunk = self.header.hunks[indexofthishunk - 1]
            return previoushunk
        else:
            return None

    def parentitem(self):
        """return the parent to the current item"""
        return self.header

    def firstchild(self):
        """return the first child of this item, if one exists.  otherwise
        None."""
        if len(self.changedlines) > 0:
            return self.changedlines[0]
        else:
            return None

    def lastchild(self):
        """return the last child of this item, if one exists.  otherwise
        None."""
        if len(self.changedlines) > 0:
            return self.changedlines[-1]
        else:
            return None

    def allchildren(self):
        """return a list of all of the direct children of this node"""
        return self.changedlines

    def countchanges(self):
        """changedlines -> (n+,n-)"""
        add = len(
            [
                l
                for l in self.changedlines
                if l.applied and l.prettystr().startswith(b'+')
            ]
        )
        rem = len(
            [
                l
                for l in self.changedlines
                if l.applied and l.prettystr().startswith(b'-')
            ]
        )
        return add, rem

    def getfromtoline(self):
        # calculate the number of removed lines converted to context lines
        removedconvertedtocontext = self.originalremoved - self.removed

        contextlen = (
            len(self.before) + len(self.after) + removedconvertedtocontext
        )
        if self.after and self.after[-1] == diffhelper.MISSING_NEWLINE_MARKER:
            contextlen -= 1
        fromlen = contextlen + self.removed
        tolen = contextlen + self.added

        # diffutils manual, section "2.2.2.2 detailed description of unified
        # format": "an empty hunk is considered to end at the line that
        # precedes the hunk."
        #
        # so, if either of hunks is empty, decrease its line start. --immerrr
        # but only do this if fromline > 0, to avoid having, e.g fromline=-1.
        fromline, toline = self.fromline, self.toline
        if fromline != 0:
            if fromlen == 0:
                fromline -= 1
            if tolen == 0 and toline > 0:
                toline -= 1

        fromtoline = b'@@ -%d,%d +%d,%d @@%s\n' % (
            fromline,
            fromlen,
            toline,
            tolen,
            self.proc and (b' ' + self.proc),
        )
        return fromtoline

    def write(self, fp):
        # updated self.added/removed, which are used by getfromtoline()
        self.added, self.removed = self.countchanges()
        fp.write(self.getfromtoline())

        hunklinelist = []
        # add the following to the list: (1) all applied lines, and
        # (2) all unapplied removal lines (convert these to context lines)
        for changedline in self.changedlines:
            changedlinestr = changedline.prettystr()
            if changedline.applied:
                hunklinelist.append(changedlinestr)
            elif changedlinestr.startswith(b"-"):
                hunklinelist.append(b" " + changedlinestr[1:])

        fp.write(b''.join(self.before + hunklinelist + self.after))

    pretty = write

    def prettystr(self):
        x = stringio()
        self.pretty(x)
        return x.getvalue()

    def reversehunk(self):
        """return a recordhunk which is the reverse of the hunk

        Assuming the displayed patch is diff(A, B) result. The returned hunk is
        intended to be applied to B, instead of A.

        For example, when A is "0\n1\n2\n6\n" and B is "0\n3\n4\n5\n6\n", and
        the user made the following selection:

                 0
            [x] -1           [x]: selected
            [ ] -2           [ ]: not selected
            [x] +3
            [ ] +4
            [x] +5
                 6

        This function returns a hunk like:

                 0
                -3
                -4
                -5
                +1
                +4
                 6

        Note "4" was first deleted then added. That's because "4" exists in B
        side and "-4" must exist between "-3" and "-5" to make the patch
        applicable to B.
        """
        dels = []
        adds = []
        noeol = False
        for line in self.changedlines:
            text = line.linetext
            if line.linetext == diffhelper.MISSING_NEWLINE_MARKER:
                noeol = True
                break
            if line.applied:
                if text.startswith(b'+'):
                    dels.append(text[1:])
                elif text.startswith(b'-'):
                    adds.append(text[1:])
            elif text.startswith(b'+'):
                dels.append(text[1:])
                adds.append(text[1:])
        hunk = [b'-%s' % l for l in dels] + [b'+%s' % l for l in adds]
        if noeol and hunk:
            # Remove the newline from the end of the hunk.
            hunk[-1] = hunk[-1][:-1]
        h = self._hunk
        return patchmod.recordhunk(
            h.header, h.toline, h.fromline, h.proc, h.before, hunk, h.after
        )

    def __getattr__(self, name):
        return getattr(self._hunk, name)

    def __repr__(self):
        return '<hunk %r@%d>' % (self.filename(), self.fromline)


def filterpatch(ui, chunks, chunkselector, operation=None):
    """interactively filter patch chunks into applied-only chunks"""
    chunks = list(chunks)
    # convert chunks list into structure suitable for displaying/modifying
    # with curses.  create a list of headers only.
    headers = [c for c in chunks if isinstance(c, patchmod.header)]

    # if there are no changed files
    if len(headers) == 0:
        return [], {}
    uiheaders = [uiheader(h) for h in headers]
    # let user choose headers/hunks/lines, and mark their applied flags
    # accordingly
    ret = chunkselector(ui, uiheaders, operation=operation)
    appliedhunklist = []
    for hdr in uiheaders:
        if hdr.applied and (
            hdr.special() or len([h for h in hdr.hunks if h.applied]) > 0
        ):
            appliedhunklist.append(hdr)
            fixoffset = 0
            for hnk in hdr.hunks:
                if hnk.applied:
                    appliedhunklist.append(hnk)
                    # adjust the 'to'-line offset of the hunk to be correct
                    # after de-activating some of the other hunks for this file
                    if fixoffset:
                        # hnk = copy.copy(hnk) # necessary??
                        hnk.toline += fixoffset
                else:
                    fixoffset += hnk.removed - hnk.added

    return (appliedhunklist, ret)


def chunkselector(ui, headerlist, operation=None):
    """
    curses interface to get selection of chunks, and mark the applied flags
    of the chosen chunks.
    """
    ui.write(_(b'starting interactive selection\n'))
    chunkselector = curseschunkselector(headerlist, ui, operation)
    origsigtstp = sentinel = object()
    if util.safehasattr(signal, b'SIGTSTP'):
        origsigtstp = signal.getsignal(signal.SIGTSTP)
    try:
        with util.with_lc_ctype():
            curses.wrapper(chunkselector.main)
        if chunkselector.initexc is not None:
            raise chunkselector.initexc
        # ncurses does not restore signal handler for SIGTSTP
    finally:
        if origsigtstp is not sentinel:
            signal.signal(signal.SIGTSTP, origsigtstp)
    return chunkselector.opts


def testdecorator(testfn, f):
    def u(*args, **kwargs):
        return f(testfn, *args, **kwargs)

    return u


def testchunkselector(testfn, ui, headerlist, operation=None):
    """
    test interface to get selection of chunks, and mark the applied flags
    of the chosen chunks.
    """
    chunkselector = curseschunkselector(headerlist, ui, operation)

    class dummystdscr(object):
        def clear(self):
            pass

        def refresh(self):
            pass

    chunkselector.stdscr = dummystdscr()
    if testfn and os.path.exists(testfn):
        testf = open(testfn, 'r')
        testcommands = [x.rstrip('\n') for x in testf.readlines()]
        testf.close()
        while True:
            if chunkselector.handlekeypressed(testcommands.pop(0), test=True):
                break
    return chunkselector.opts


_headermessages = {  # {operation: text}
    b'apply': _(b'Select hunks to apply'),
    b'discard': _(b'Select hunks to discard'),
    b'keep': _(b'Select hunks to keep'),
    None: _(b'Select hunks to record'),
}


class curseschunkselector(object):
    def __init__(self, headerlist, ui, operation=None):
        # put the headers into a patch object
        self.headerlist = patch(headerlist)

        self.ui = ui
        self.opts = {}

        self.errorstr = None
        # list of all chunks
        self.chunklist = []
        for h in headerlist:
            self.chunklist.append(h)
            self.chunklist.extend(h.hunks)

        # dictionary mapping (fgcolor, bgcolor) pairs to the
        # corresponding curses color-pair value.
        self.colorpairs = {}
        # maps custom nicknames of color-pairs to curses color-pair values
        self.colorpairnames = {}

        # Honor color setting of ui section. Keep colored setup as
        # long as not explicitly set to a falsy value - especially,
        # when not set at all. This is to stay most compatible with
        # previous (color only) behaviour.
        uicolor = stringutil.parsebool(self.ui.config(b'ui', b'color'))
        self.usecolor = uicolor is not False

        # the currently selected header, hunk, or hunk-line
        self.currentselecteditem = self.headerlist[0]
        self.lastapplieditem = None

        # updated when printing out patch-display -- the 'lines' here are the
        # line positions *in the pad*, not on the screen.
        self.selecteditemstartline = 0
        self.selecteditemendline = None

        # define indentation levels
        self.headerindentnumchars = 0
        self.hunkindentnumchars = 3
        self.hunklineindentnumchars = 6

        # the first line of the pad to print to the screen
        self.firstlineofpadtoprint = 0

        # keeps track of the number of lines in the pad
        self.numpadlines = None

        self.numstatuslines = 1

        # keep a running count of the number of lines printed to the pad
        # (used for determining when the selected item begins/ends)
        self.linesprintedtopadsofar = 0

        # stores optional text for a commit comment provided by the user
        self.commenttext = b""

        # if the last 'toggle all' command caused all changes to be applied
        self.waslasttoggleallapplied = True

        # affects some ui text
        if operation not in _headermessages:
            raise error.ProgrammingError(
                b'unexpected operation: %s' % operation
            )
        self.operation = operation

    def uparrowevent(self):
        """
        try to select the previous item to the current item that has the
        most-indented level.  for example, if a hunk is selected, try to select
        the last hunkline of the hunk prior to the selected hunk.  or, if
        the first hunkline of a hunk is currently selected, then select the
        hunk itself.
        """
        currentitem = self.currentselecteditem

        nextitem = currentitem.previtem()

        if nextitem is None:
            # if no parent item (i.e. currentitem is the first header), then
            # no change...
            nextitem = currentitem

        self.currentselecteditem = nextitem

    def uparrowshiftevent(self):
        """
        select (if possible) the previous item on the same level as the
        currently selected item.  otherwise, select (if possible) the
        parent-item of the currently selected item.
        """
        currentitem = self.currentselecteditem
        nextitem = currentitem.prevsibling()
        # if there's no previous sibling, try choosing the parent
        if nextitem is None:
            nextitem = currentitem.parentitem()
        if nextitem is None:
            # if no parent item (i.e. currentitem is the first header), then
            # no change...
            nextitem = currentitem

        self.currentselecteditem = nextitem
        self.recenterdisplayedarea()

    def downarrowevent(self):
        """
        try to select the next item to the current item that has the
        most-indented level.  for example, if a hunk is selected, select
        the first hunkline of the selected hunk.  or, if the last hunkline of
        a hunk is currently selected, then select the next hunk, if one exists,
        or if not, the next header if one exists.
        """
        # self.startprintline += 1 #debug
        currentitem = self.currentselecteditem

        nextitem = currentitem.nextitem()
        # if there's no next item, keep the selection as-is
        if nextitem is None:
            nextitem = currentitem

        self.currentselecteditem = nextitem

    def downarrowshiftevent(self):
        """
        select (if possible) the next item on the same level as the currently
        selected item.  otherwise, select (if possible) the next item on the
        same level as the parent item of the currently selected item.
        """
        currentitem = self.currentselecteditem
        nextitem = currentitem.nextsibling()
        # if there's no next sibling, try choosing the parent's nextsibling
        if nextitem is None:
            try:
                nextitem = currentitem.parentitem().nextsibling()
            except AttributeError:
                # parentitem returned None, so nextsibling() can't be called
                nextitem = None
        if nextitem is None:
            # if parent has no next sibling, then no change...
            nextitem = currentitem

        self.currentselecteditem = nextitem
        self.recenterdisplayedarea()

    def nextsametype(self, test=False):
        currentitem = self.currentselecteditem
        sametype = lambda item: isinstance(item, type(currentitem))
        nextitem = currentitem.nextitem()

        while nextitem is not None and not sametype(nextitem):
            nextitem = nextitem.nextitem()

        if nextitem is None:
            nextitem = currentitem
        else:
            parent = nextitem.parentitem()
            if parent is not None and parent.folded:
                self.togglefolded(parent)

        self.currentselecteditem = nextitem
        if not test:
            self.recenterdisplayedarea()

    def rightarrowevent(self):
        """
        select (if possible) the first of this item's child-items.
        """
        currentitem = self.currentselecteditem
        nextitem = currentitem.firstchild()

        # turn off folding if we want to show a child-item
        if currentitem.folded:
            self.togglefolded(currentitem)

        if nextitem is None:
            # if no next item on parent-level, then no change...
            nextitem = currentitem

        self.currentselecteditem = nextitem

    def leftarrowevent(self):
        """
        if the current item can be folded (i.e. it is an unfolded header or
        hunk), then fold it.  otherwise try select (if possible) the parent
        of this item.
        """
        currentitem = self.currentselecteditem

        # try to fold the item
        if not isinstance(currentitem, uihunkline):
            if not currentitem.folded:
                self.togglefolded(item=currentitem)
                return

        # if it can't be folded, try to select the parent item
        nextitem = currentitem.parentitem()

        if nextitem is None:
            # if no item on parent-level, then no change...
            nextitem = currentitem
            if not nextitem.folded:
                self.togglefolded(item=nextitem)

        self.currentselecteditem = nextitem

    def leftarrowshiftevent(self):
        """
        select the header of the current item (or fold current item if the
        current item is already a header).
        """
        currentitem = self.currentselecteditem

        if isinstance(currentitem, uiheader):
            if not currentitem.folded:
                self.togglefolded(item=currentitem)
                return

        # select the parent item recursively until we're at a header
        while True:
            nextitem = currentitem.parentitem()
            if nextitem is None:
                break
            else:
                currentitem = nextitem

        self.currentselecteditem = currentitem

    def updatescroll(self):
        """scroll the screen to fully show the currently-selected"""
        selstart = self.selecteditemstartline
        selend = self.selecteditemendline

        padstart = self.firstlineofpadtoprint
        padend = padstart + self.yscreensize - self.numstatuslines - 1
        # 'buffered' pad start/end values which scroll with a certain
        # top/bottom context margin
        padstartbuffered = padstart + 3
        padendbuffered = padend - 3

        if selend > padendbuffered:
            self.scrolllines(selend - padendbuffered)
        elif selstart < padstartbuffered:
            # negative values scroll in pgup direction
            self.scrolllines(selstart - padstartbuffered)

    def scrolllines(self, numlines):
        """scroll the screen up (down) by numlines when numlines >0 (<0)."""
        self.firstlineofpadtoprint += numlines
        if self.firstlineofpadtoprint < 0:
            self.firstlineofpadtoprint = 0
        if self.firstlineofpadtoprint > self.numpadlines - 1:
            self.firstlineofpadtoprint = self.numpadlines - 1

    def toggleapply(self, item=None):
        """
        toggle the applied flag of the specified item.  if no item is specified,
        toggle the flag of the currently selected item.
        """
        if item is None:
            item = self.currentselecteditem
            # Only set this when NOT using 'toggleall'
            self.lastapplieditem = item

        item.applied = not item.applied

        if isinstance(item, uiheader):
            item.partial = False
            if item.applied:
                # apply all its hunks
                for hnk in item.hunks:
                    hnk.applied = True
                    # apply all their hunklines
                    for hunkline in hnk.changedlines:
                        hunkline.applied = True
            else:
                # un-apply all its hunks
                for hnk in item.hunks:
                    hnk.applied = False
                    hnk.partial = False
                    # un-apply all their hunklines
                    for hunkline in hnk.changedlines:
                        hunkline.applied = False
        elif isinstance(item, uihunk):
            item.partial = False
            # apply all it's hunklines
            for hunkline in item.changedlines:
                hunkline.applied = item.applied

            siblingappliedstatus = [hnk.applied for hnk in item.header.hunks]
            allsiblingsapplied = not (False in siblingappliedstatus)
            nosiblingsapplied = not (True in siblingappliedstatus)

            siblingspartialstatus = [hnk.partial for hnk in item.header.hunks]
            somesiblingspartial = True in siblingspartialstatus

            # cases where applied or partial should be removed from header

            # if no 'sibling' hunks are applied (including this hunk)
            if nosiblingsapplied:
                if not item.header.special():
                    item.header.applied = False
                    item.header.partial = False
            else:  # some/all parent siblings are applied
                item.header.applied = True
                item.header.partial = (
                    somesiblingspartial or not allsiblingsapplied
                )

        elif isinstance(item, uihunkline):
            siblingappliedstatus = [ln.applied for ln in item.hunk.changedlines]
            allsiblingsapplied = not (False in siblingappliedstatus)
            nosiblingsapplied = not (True in siblingappliedstatus)

            # if no 'sibling' lines are applied
            if nosiblingsapplied:
                item.hunk.applied = False
                item.hunk.partial = False
            elif allsiblingsapplied:
                item.hunk.applied = True
                item.hunk.partial = False
            else:  # some siblings applied
                item.hunk.applied = True
                item.hunk.partial = True

            parentsiblingsapplied = [
                hnk.applied for hnk in item.hunk.header.hunks
            ]
            noparentsiblingsapplied = not (True in parentsiblingsapplied)
            allparentsiblingsapplied = not (False in parentsiblingsapplied)

            parentsiblingspartial = [
                hnk.partial for hnk in item.hunk.header.hunks
            ]
            someparentsiblingspartial = True in parentsiblingspartial

            # if all parent hunks are not applied, un-apply header
            if noparentsiblingsapplied:
                if not item.hunk.header.special():
                    item.hunk.header.applied = False
                    item.hunk.header.partial = False
            # set the applied and partial status of the header if needed
            else:  # some/all parent siblings are applied
                item.hunk.header.applied = True
                item.hunk.header.partial = (
                    someparentsiblingspartial or not allparentsiblingsapplied
                )

    def toggleall(self):
        """toggle the applied flag of all items."""
        if self.waslasttoggleallapplied:  # then unapply them this time
            for item in self.headerlist:
                if item.applied:
                    self.toggleapply(item)
        else:
            for item in self.headerlist:
                if not item.applied:
                    self.toggleapply(item)
        self.waslasttoggleallapplied = not self.waslasttoggleallapplied

    def flipselections(self):
        """
        Flip all selections. Every selected line is unselected and vice
        versa.
        """
        for header in self.headerlist:
            for hunk in header.allchildren():
                for line in hunk.allchildren():
                    self.toggleapply(line)

    def toggleallbetween(self):
        """toggle applied on or off for all items in range [lastapplied,
        current]."""
        if (
            not self.lastapplieditem
            or self.currentselecteditem == self.lastapplieditem
        ):
            # Treat this like a normal 'x'/' '
            self.toggleapply()
            return

        startitem = self.lastapplieditem
        enditem = self.currentselecteditem
        # Verify that enditem is "after" startitem, otherwise swap them.
        for direction in [b'forward', b'reverse']:
            nextitem = startitem.nextitem()
            while nextitem and nextitem != enditem:
                nextitem = nextitem.nextitem()
            if nextitem:
                break
            # Looks like we went the wrong direction :)
            startitem, enditem = enditem, startitem

        if not nextitem:
            # We didn't find a path going either forward or backward? Don't know
            # how this can happen, let's not crash though.
            return

        nextitem = startitem
        # Switch all items to be the opposite state of the currently selected
        # item. Specifically:
        #  [ ] startitem
        #  [x] middleitem
        #  [ ] enditem  <-- currently selected
        # This will turn all three on, since the currently selected item is off.
        # This does *not* invert each item (i.e. middleitem stays marked/on)
        desiredstate = not self.currentselecteditem.applied
        while nextitem != enditem.nextitem():
            if nextitem.applied != desiredstate:
                self.toggleapply(item=nextitem)
            nextitem = nextitem.nextitem()

    def togglefolded(self, item=None, foldparent=False):
        """toggle folded flag of specified item (defaults to currently
        selected)"""
        if item is None:
            item = self.currentselecteditem
        if foldparent or (isinstance(item, uiheader) and item.neverunfolded):
            if not isinstance(item, uiheader):
                # we need to select the parent item in this case
                self.currentselecteditem = item = item.parentitem()
            elif item.neverunfolded:
                item.neverunfolded = False

            # also fold any foldable children of the parent/current item
            if isinstance(item, uiheader):  # the original or 'new' item
                for child in item.allchildren():
                    child.folded = not item.folded

        if isinstance(item, (uiheader, uihunk)):
            item.folded = not item.folded

    def alignstring(self, instr, window):
        """
        add whitespace to the end of a string in order to make it fill
        the screen in the x direction.  the current cursor position is
        taken into account when making this calculation.  the string can span
        multiple lines.
        """
        y, xstart = window.getyx()
        width = self.xscreensize
        # turn tabs into spaces
        instr = instr.expandtabs(4)
        strwidth = encoding.colwidth(instr)
        numspaces = width - ((strwidth + xstart) % width)
        return instr + b" " * numspaces

    def printstring(
        self,
        window,
        text,
        fgcolor=None,
        bgcolor=None,
        pair=None,
        pairname=None,
        attrlist=None,
        towin=True,
        align=True,
        showwhtspc=False,
    ):
        """
        print the string, text, with the specified colors and attributes, to
        the specified curses window object.

        the foreground and background colors are of the form
        curses.color_xxxx, where xxxx is one of: [black, blue, cyan, green,
        magenta, red, white, yellow].  if pairname is provided, a color
        pair will be looked up in the self.colorpairnames dictionary.

        attrlist is a list containing text attributes in the form of
        curses.a_xxxx, where xxxx can be: [bold, dim, normal, standout,
        underline].

        if align == True, whitespace is added to the printed string such that
        the string stretches to the right border of the window.

        if showwhtspc == True, trailing whitespace of a string is highlighted.
        """
        # preprocess the text, converting tabs to spaces
        text = text.expandtabs(4)
        # strip \n, and convert control characters to ^[char] representation
        text = re.sub(
            br'[\x00-\x08\x0a-\x1f]',
            lambda m: b'^' + pycompat.sysbytes(chr(ord(m.group()) + 64)),
            text.strip(b'\n'),
        )

        if pair is not None:
            colorpair = pair
        elif pairname is not None:
            colorpair = self.colorpairnames[pairname]
        else:
            if fgcolor is None:
                fgcolor = -1
            if bgcolor is None:
                bgcolor = -1
            if (fgcolor, bgcolor) in self.colorpairs:
                colorpair = self.colorpairs[(fgcolor, bgcolor)]
            else:
                colorpair = self.getcolorpair(fgcolor, bgcolor)
        # add attributes if possible
        if attrlist is None:
            attrlist = []
        if colorpair < 256:
            # then it is safe to apply all attributes
            for textattr in attrlist:
                colorpair |= textattr
        else:
            # just apply a select few (safe?) attributes
            for textattr in (curses.A_UNDERLINE, curses.A_BOLD):
                if textattr in attrlist:
                    colorpair |= textattr

        y, xstart = self.chunkpad.getyx()
        t = b""  # variable for counting lines printed
        # if requested, show trailing whitespace
        if showwhtspc:
            origlen = len(text)
            text = text.rstrip(b' \n')  # tabs have already been expanded
            strippedlen = len(text)
            numtrailingspaces = origlen - strippedlen

        if towin:
            window.addstr(text, colorpair)
        t += text

        if showwhtspc:
            wscolorpair = colorpair | curses.A_REVERSE
            if towin:
                for i in range(numtrailingspaces):
                    window.addch(curses.ACS_CKBOARD, wscolorpair)
            t += b" " * numtrailingspaces

        if align:
            if towin:
                extrawhitespace = self.alignstring(b"", window)
                window.addstr(extrawhitespace, colorpair)
            else:
                # need to use t, since the x position hasn't incremented
                extrawhitespace = self.alignstring(t, window)
            t += extrawhitespace

        # is reset to 0 at the beginning of printitem()

        linesprinted = (xstart + len(t)) // self.xscreensize
        self.linesprintedtopadsofar += linesprinted
        return t

    def _getstatuslinesegments(self):
        """-> [str]. return segments"""
        selected = self.currentselecteditem.applied
        spaceselect = _(b'space/enter: select')
        spacedeselect = _(b'space/enter: deselect')
        # Format the selected label into a place as long as the longer of the
        # two possible labels.  This may vary by language.
        spacelen = max(len(spaceselect), len(spacedeselect))
        selectedlabel = b'%-*s' % (
            spacelen,
            spacedeselect if selected else spaceselect,
        )
        segments = [
            _headermessages[self.operation],
            b'-',
            _(b'[x]=selected **=collapsed'),
            _(b'c: confirm'),
            _(b'q: abort'),
            _(b'arrow keys: move/expand/collapse'),
            selectedlabel,
            _(b'?: help'),
        ]
        return segments

    def _getstatuslines(self):
        """() -> [str]. return short help used in the top status window"""
        if self.errorstr is not None:
            lines = [self.errorstr, _(b'Press any key to continue')]
        else:
            # wrap segments to lines
            segments = self._getstatuslinesegments()
            width = self.xscreensize
            lines = []
            lastwidth = width
            for s in segments:
                w = encoding.colwidth(s)
                sep = b' ' * (1 + (s and s[0] not in b'-['))
                if lastwidth + w + len(sep) >= width:
                    lines.append(s)
                    lastwidth = w
                else:
                    lines[-1] += sep + s
                    lastwidth += w + len(sep)
        if len(lines) != self.numstatuslines:
            self.numstatuslines = len(lines)
            self.statuswin.resize(self.numstatuslines, self.xscreensize)
        return [stringutil.ellipsis(l, self.xscreensize - 1) for l in lines]

    def updatescreen(self):
        self.statuswin.erase()
        self.chunkpad.erase()

        printstring = self.printstring

        # print out the status lines at the top
        try:
            for line in self._getstatuslines():
                printstring(self.statuswin, line, pairname=b"legend")
            self.statuswin.refresh()
        except curses.error:
            pass
        if self.errorstr is not None:
            return

        # print out the patch in the remaining part of the window
        try:
            self.printitem()
            self.updatescroll()
            self.chunkpad.refresh(
                self.firstlineofpadtoprint,
                0,
                self.numstatuslines,
                0,
                self.yscreensize - self.numstatuslines,
                self.xscreensize - 1,
            )
        except curses.error:
            pass

    def getstatusprefixstring(self, item):
        """
        create a string to prefix a line with which indicates whether 'item'
        is applied and/or folded.
        """

        # create checkbox string
        if item.applied:
            if not isinstance(item, uihunkline) and item.partial:
                checkbox = b"[~]"
            else:
                checkbox = b"[x]"
        else:
            checkbox = b"[ ]"

        try:
            if item.folded:
                checkbox += b"**"
                if isinstance(item, uiheader):
                    # one of "m", "a", or "d" (modified, added, deleted)
                    filestatus = item.changetype

                    checkbox += filestatus + b" "
            else:
                checkbox += b"  "
                if isinstance(item, uiheader):
                    # add two more spaces for headers
                    checkbox += b"  "
        except AttributeError:  # not foldable
            checkbox += b"  "

        return checkbox

    def printheader(
        self, header, selected=False, towin=True, ignorefolding=False
    ):
        """
        print the header to the pad.  if countlines is True, don't print
        anything, but just count the number of lines which would be printed.
        """

        outstr = b""
        text = header.prettystr()
        chunkindex = self.chunklist.index(header)

        if chunkindex != 0 and not header.folded:
            # add separating line before headers
            outstr += self.printstring(
                self.chunkpad, b'_' * self.xscreensize, towin=towin, align=False
            )
        # select color-pair based on if the header is selected
        colorpair = self.getcolorpair(
            name=selected and b"selected" or b"normal", attrlist=[curses.A_BOLD]
        )

        # print out each line of the chunk, expanding it to screen width

        # number of characters to indent lines on this level by
        indentnumchars = 0
        checkbox = self.getstatusprefixstring(header)
        if not header.folded or ignorefolding:
            textlist = text.split(b"\n")
            linestr = checkbox + textlist[0]
        else:
            linestr = checkbox + header.filename()
        outstr += self.printstring(
            self.chunkpad, linestr, pair=colorpair, towin=towin
        )
        if not header.folded or ignorefolding:
            if len(textlist) > 1:
                for line in textlist[1:]:
                    linestr = b" " * (indentnumchars + len(checkbox)) + line
                    outstr += self.printstring(
                        self.chunkpad, linestr, pair=colorpair, towin=towin
                    )

        return outstr

    def printhunklinesbefore(
        self, hunk, selected=False, towin=True, ignorefolding=False
    ):
        """includes start/end line indicator"""
        outstr = b""
        # where hunk is in list of siblings
        hunkindex = hunk.header.hunks.index(hunk)

        if hunkindex != 0:
            # add separating line before headers
            outstr += self.printstring(
                self.chunkpad, b' ' * self.xscreensize, towin=towin, align=False
            )

        colorpair = self.getcolorpair(
            name=selected and b"selected" or b"normal", attrlist=[curses.A_BOLD]
        )

        # print out from-to line with checkbox
        checkbox = self.getstatusprefixstring(hunk)

        lineprefix = b" " * self.hunkindentnumchars + checkbox
        frtoline = b"   " + hunk.getfromtoline().strip(b"\n")

        outstr += self.printstring(
            self.chunkpad, lineprefix, towin=towin, align=False
        )  # add uncolored checkbox/indent
        outstr += self.printstring(
            self.chunkpad, frtoline, pair=colorpair, towin=towin
        )

        if hunk.folded and not ignorefolding:
            # skip remainder of output
            return outstr

        # print out lines of the chunk preceeding changed-lines
        for line in hunk.before:
            linestr = (
                b" " * (self.hunklineindentnumchars + len(checkbox)) + line
            )
            outstr += self.printstring(self.chunkpad, linestr, towin=towin)

        return outstr

    def printhunklinesafter(self, hunk, towin=True, ignorefolding=False):
        outstr = b""
        if hunk.folded and not ignorefolding:
            return outstr

        # a bit superfluous, but to avoid hard-coding indent amount
        checkbox = self.getstatusprefixstring(hunk)
        for line in hunk.after:
            linestr = (
                b" " * (self.hunklineindentnumchars + len(checkbox)) + line
            )
            outstr += self.printstring(self.chunkpad, linestr, towin=towin)

        return outstr

    def printhunkchangedline(self, hunkline, selected=False, towin=True):
        outstr = b""
        checkbox = self.getstatusprefixstring(hunkline)

        linestr = hunkline.prettystr().strip(b"\n")

        # select color-pair based on whether line is an addition/removal
        if selected:
            colorpair = self.getcolorpair(name=b"selected")
        elif linestr.startswith(b"+"):
            colorpair = self.getcolorpair(name=b"addition")
        elif linestr.startswith(b"-"):
            colorpair = self.getcolorpair(name=b"deletion")
        elif linestr.startswith(b"\\"):
            colorpair = self.getcolorpair(name=b"normal")

        lineprefix = b" " * self.hunklineindentnumchars + checkbox
        outstr += self.printstring(
            self.chunkpad, lineprefix, towin=towin, align=False
        )  # add uncolored checkbox/indent
        outstr += self.printstring(
            self.chunkpad, linestr, pair=colorpair, towin=towin, showwhtspc=True
        )
        return outstr

    def printitem(
        self, item=None, ignorefolding=False, recursechildren=True, towin=True
    ):
        """
        use __printitem() to print the the specified item.applied.
        if item is not specified, then print the entire patch.
        (hiding folded elements, etc. -- see __printitem() docstring)
        """

        if item is None:
            item = self.headerlist
        if recursechildren:
            self.linesprintedtopadsofar = 0

        outstr = []
        self.__printitem(
            item, ignorefolding, recursechildren, outstr, towin=towin
        )
        return b''.join(outstr)

    def outofdisplayedarea(self):
        y, _ = self.chunkpad.getyx()  # cursor location
        # * 2 here works but an optimization would be the max number of
        # consecutive non selectable lines
        # i.e the max number of context line for any hunk in the patch
        miny = min(0, self.firstlineofpadtoprint - self.yscreensize)
        maxy = self.firstlineofpadtoprint + self.yscreensize * 2
        return y < miny or y > maxy

    def handleselection(self, item, recursechildren):
        selected = item is self.currentselecteditem
        if selected and recursechildren:
            # assumes line numbering starting from line 0
            self.selecteditemstartline = self.linesprintedtopadsofar
            selecteditemlines = self.getnumlinesdisplayed(
                item, recursechildren=False
            )
            self.selecteditemendline = (
                self.selecteditemstartline + selecteditemlines - 1
            )
        return selected

    def __printitem(
        self, item, ignorefolding, recursechildren, outstr, towin=True
    ):
        """
        recursive method for printing out patch/header/hunk/hunk-line data to
        screen.  also returns a string with all of the content of the displayed
        patch (not including coloring, etc.).

        if ignorefolding is True, then folded items are printed out.

        if recursechildren is False, then only print the item without its
        child items.
        """

        if towin and self.outofdisplayedarea():
            return

        selected = self.handleselection(item, recursechildren)

        # patch object is a list of headers
        if isinstance(item, patch):
            if recursechildren:
                for hdr in item:
                    self.__printitem(
                        hdr, ignorefolding, recursechildren, outstr, towin
                    )
        # todo: eliminate all isinstance() calls
        if isinstance(item, uiheader):
            outstr.append(
                self.printheader(
                    item, selected, towin=towin, ignorefolding=ignorefolding
                )
            )
            if recursechildren:
                for hnk in item.hunks:
                    self.__printitem(
                        hnk, ignorefolding, recursechildren, outstr, towin
                    )
        elif isinstance(item, uihunk) and (
            (not item.header.folded) or ignorefolding
        ):
            # print the hunk data which comes before the changed-lines
            outstr.append(
                self.printhunklinesbefore(
                    item, selected, towin=towin, ignorefolding=ignorefolding
                )
            )
            if recursechildren:
                for l in item.changedlines:
                    self.__printitem(
                        l, ignorefolding, recursechildren, outstr, towin
                    )
                outstr.append(
                    self.printhunklinesafter(
                        item, towin=towin, ignorefolding=ignorefolding
                    )
                )
        elif isinstance(item, uihunkline) and (
            (not item.hunk.folded) or ignorefolding
        ):
            outstr.append(
                self.printhunkchangedline(item, selected, towin=towin)
            )

        return outstr

    def getnumlinesdisplayed(
        self, item=None, ignorefolding=False, recursechildren=True
    ):
        """
        return the number of lines which would be displayed if the item were
        to be printed to the display.  the item will not be printed to the
        display (pad).
        if no item is given, assume the entire patch.
        if ignorefolding is True, folded items will be unfolded when counting
        the number of lines.
        """

        # temporarily disable printing to windows by printstring
        patchdisplaystring = self.printitem(
            item, ignorefolding, recursechildren, towin=False
        )
        numlines = len(patchdisplaystring) // self.xscreensize
        return numlines

    def sigwinchhandler(self, n, frame):
        """handle window resizing"""
        try:
            curses.endwin()
            self.xscreensize, self.yscreensize = scmutil.termsize(self.ui)
            self.statuswin.resize(self.numstatuslines, self.xscreensize)
            self.numpadlines = self.getnumlinesdisplayed(ignorefolding=True) + 1
            self.chunkpad = curses.newpad(self.numpadlines, self.xscreensize)
        except curses.error:
            pass

    def getcolorpair(
        self, fgcolor=None, bgcolor=None, name=None, attrlist=None
    ):
        """
        get a curses color pair, adding it to self.colorpairs if it is not
        already defined.  an optional string, name, can be passed as a shortcut
        for referring to the color-pair.  by default, if no arguments are
        specified, the white foreground / black background color-pair is
        returned.

        it is expected that this function will be used exclusively for
        initializing color pairs, and not curses.init_pair().

        attrlist is used to 'flavor' the returned color-pair.  this information
        is not stored in self.colorpairs.  it contains attribute values like
        curses.A_BOLD.
        """

        if (name is not None) and name in self.colorpairnames:
            # then get the associated color pair and return it
            colorpair = self.colorpairnames[name]
        else:
            if fgcolor is None:
                fgcolor = -1
            if bgcolor is None:
                bgcolor = -1
            if (fgcolor, bgcolor) in self.colorpairs:
                colorpair = self.colorpairs[(fgcolor, bgcolor)]
            else:
                pairindex = len(self.colorpairs) + 1
                if self.usecolor:
                    curses.init_pair(pairindex, fgcolor, bgcolor)
                    colorpair = self.colorpairs[
                        (fgcolor, bgcolor)
                    ] = curses.color_pair(pairindex)
                    if name is not None:
                        self.colorpairnames[name] = curses.color_pair(pairindex)
                else:
                    cval = 0
                    if name is not None:
                        if name == b'selected':
                            cval = curses.A_REVERSE
                        self.colorpairnames[name] = cval
                    colorpair = self.colorpairs[(fgcolor, bgcolor)] = cval

        # add attributes if possible
        if attrlist is None:
            attrlist = []
        if colorpair < 256:
            # then it is safe to apply all attributes
            for textattr in attrlist:
                colorpair |= textattr
        else:
            # just apply a select few (safe?) attributes
            for textattrib in (curses.A_UNDERLINE, curses.A_BOLD):
                if textattrib in attrlist:
                    colorpair |= textattrib
        return colorpair

    def initcolorpair(self, *args, **kwargs):
        """same as getcolorpair."""
        self.getcolorpair(*args, **kwargs)

    def helpwindow(self):
        """print a help window to the screen.  exit after any keypress."""
        helptext = _(
            """            [press any key to return to the patch-display]

The curses hunk selector allows you to interactively choose among the
changes you have made, and confirm only those changes you select for
further processing by the command you are running (such as commit,
shelve, or revert). After confirming the selected changes, the
unselected changes are still present in your working copy, so you can
use the hunk selector multiple times to split large changes into
smaller changesets. the following are valid keystrokes:

              x [space] : (un-)select item ([~]/[x] = partly/fully applied)
                [enter] : (un-)select item and go to next item of same type
                      A : (un-)select all items
                      X : (un-)select all items between current and most-recent
    up/down-arrow [k/j] : go to previous/next unfolded item
        pgup/pgdn [K/J] : go to previous/next item of same type
 right/left-arrow [l/h] : go to child item / parent item
 shift-left-arrow   [H] : go to parent header / fold selected header
                      g : go to the top
                      G : go to the bottom
                      f : fold / unfold item, hiding/revealing its children
                      F : fold / unfold parent item and all of its ancestors
                 ctrl-l : scroll the selected line to the top of the screen
                      m : edit / resume editing the commit message
                      e : edit the currently selected hunk
                      a : toggle all selections
                      c : confirm selected changes
                      r : review/edit and confirm selected changes
                      q : quit without confirming (no changes will be made)
                      ? : help (what you're currently reading)"""
        )

        helpwin = curses.newwin(self.yscreensize, 0, 0, 0)
        helplines = helptext.split(b"\n")
        helplines = helplines + [b" "] * (
            self.yscreensize - self.numstatuslines - len(helplines) - 1
        )
        try:
            for line in helplines:
                self.printstring(helpwin, line, pairname=b"legend")
        except curses.error:
            pass
        helpwin.refresh()
        try:
            with self.ui.timeblockedsection(b'crecord'):
                helpwin.getkey()
        except curses.error:
            pass

    def commitMessageWindow(self):
        """Create a temporary commit message editing window on the screen."""

        curses.raw()
        curses.def_prog_mode()
        curses.endwin()
        self.commenttext = self.ui.edit(self.commenttext, self.ui.username())
        curses.cbreak()
        self.stdscr.refresh()
        self.stdscr.keypad(1)  # allow arrow-keys to continue to function

    def handlefirstlineevent(self):
        """
        Handle 'g' to navigate to the top most file in the ncurses window.
        """
        self.currentselecteditem = self.headerlist[0]
        currentitem = self.currentselecteditem
        # select the parent item recursively until we're at a header
        while True:
            nextitem = currentitem.parentitem()
            if nextitem is None:
                break
            else:
                currentitem = nextitem

        self.currentselecteditem = currentitem

    def handlelastlineevent(self):
        """
        Handle 'G' to navigate to the bottom most file/hunk/line depending
        on the whether the fold is active or not.

        If the bottom most file is folded, it navigates to that file and
        stops there. If the bottom most file is unfolded, it navigates to
        the bottom most hunk in that file and stops there. If the bottom most
        hunk is unfolded, it navigates to the bottom most line in that hunk.
        """
        currentitem = self.currentselecteditem
        nextitem = currentitem.nextitem()
        # select the child item recursively until we're at a footer
        while nextitem is not None:
            nextitem = currentitem.nextitem()
            if nextitem is None:
                break
            else:
                currentitem = nextitem

        self.currentselecteditem = currentitem
        self.recenterdisplayedarea()

    def confirmationwindow(self, windowtext):
        """display an informational window, then wait for and return a
        keypress."""

        confirmwin = curses.newwin(self.yscreensize, 0, 0, 0)
        try:
            lines = windowtext.split(b"\n")
            for line in lines:
                self.printstring(confirmwin, line, pairname=b"selected")
        except curses.error:
            pass
        self.stdscr.refresh()
        confirmwin.refresh()
        try:
            with self.ui.timeblockedsection(b'crecord'):
                response = chr(self.stdscr.getch())
        except ValueError:
            response = None

        return response

    def reviewcommit(self):
        """ask for 'y' to be pressed to confirm selected. return True if
        confirmed."""
        confirmtext = _(
            """If you answer yes to the following, your currently chosen patch chunks
will be loaded into an editor. To modify the patch, make the changes in your
editor and save. To accept the current patch as-is, close the editor without
saving.

note: don't add/remove lines unless you also modify the range information.
      failing to follow this rule will result in the commit aborting.

are you sure you want to review/edit and confirm the selected changes [yn]?
"""
        )
        with self.ui.timeblockedsection(b'crecord'):
            response = self.confirmationwindow(confirmtext)
        if response is None:
            response = "n"
        if response.lower().startswith("y"):
            return True
        else:
            return False

    def recenterdisplayedarea(self):
        """
        once we scrolled with pg up pg down we can be pointing outside of the
        display zone. we print the patch with towin=False to compute the
        location of the selected item even though it is outside of the displayed
        zone and then update the scroll.
        """
        self.printitem(towin=False)
        self.updatescroll()

    def toggleedit(self, item=None, test=False):
        """
        edit the currently selected chunk
        """

        def updateui(self):
            self.numpadlines = self.getnumlinesdisplayed(ignorefolding=True) + 1
            self.chunkpad = curses.newpad(self.numpadlines, self.xscreensize)
            self.updatescroll()
            self.stdscr.refresh()
            self.statuswin.refresh()
            self.stdscr.keypad(1)

        def editpatchwitheditor(self, chunk):
            if chunk is None:
                self.ui.write(_(b'cannot edit patch for whole file'))
                self.ui.write(b"\n")
                return None
            if chunk.header.binary():
                self.ui.write(_(b'cannot edit patch for binary file'))
                self.ui.write(b"\n")
                return None

            # write the initial patch
            patch = stringio()
            patch.write(diffhelptext + hunkhelptext)
            chunk.header.write(patch)
            chunk.write(patch)

            # start the editor and wait for it to complete
            try:
                patch = self.ui.edit(patch.getvalue(), b"", action=b"diff")
            except error.Abort as exc:
                self.errorstr = exc.message
                return None
            finally:
                self.stdscr.clear()
                self.stdscr.refresh()

            # remove comment lines
            patch = [
                line + b'\n'
                for line in patch.splitlines()
                if not line.startswith(b'#')
            ]
            return patchmod.parsepatch(patch)

        if item is None:
            item = self.currentselecteditem
        if isinstance(item, uiheader):
            return
        if isinstance(item, uihunkline):
            item = item.parentitem()
        if not isinstance(item, uihunk):
            return

        # To go back to that hunk or its replacement at the end of the edit
        itemindex = item.parentitem().hunks.index(item)

        beforeadded, beforeremoved = item.added, item.removed
        newpatches = editpatchwitheditor(self, item)
        if newpatches is None:
            if not test:
                updateui(self)
            return
        header = item.header
        editedhunkindex = header.hunks.index(item)
        hunksbefore = header.hunks[:editedhunkindex]
        hunksafter = header.hunks[editedhunkindex + 1 :]
        newpatchheader = newpatches[0]
        newhunks = [uihunk(h, header) for h in newpatchheader.hunks]
        newadded = sum([h.added for h in newhunks])
        newremoved = sum([h.removed for h in newhunks])
        offset = (newadded - beforeadded) - (newremoved - beforeremoved)

        for h in hunksafter:
            h.toline += offset
        for h in newhunks:
            h.folded = False
        header.hunks = hunksbefore + newhunks + hunksafter
        if self.emptypatch():
            header.hunks = hunksbefore + [item] + hunksafter
        self.currentselecteditem = header
        if len(header.hunks) > itemindex:
            self.currentselecteditem = header.hunks[itemindex]

        if not test:
            updateui(self)

    def emptypatch(self):
        item = self.headerlist
        if not item:
            return True
        for header in item:
            if header.hunks:
                return False
        return True

    def handlekeypressed(self, keypressed, test=False):
        """
        Perform actions based on pressed keys.

        Return true to exit the main loop.
        """
        if keypressed in ["k", "KEY_UP"]:
            self.uparrowevent()
        elif keypressed in ["K", "KEY_PPAGE"]:
            self.uparrowshiftevent()
        elif keypressed in ["j", "KEY_DOWN"]:
            self.downarrowevent()
        elif keypressed in ["J", "KEY_NPAGE"]:
            self.downarrowshiftevent()
        elif keypressed in ["l", "KEY_RIGHT"]:
            self.rightarrowevent()
        elif keypressed in ["h", "KEY_LEFT"]:
            self.leftarrowevent()
        elif keypressed in ["H", "KEY_SLEFT"]:
            self.leftarrowshiftevent()
        elif keypressed in ["q"]:
            raise error.CanceledError(_(b'user quit'))
        elif keypressed in ['a']:
            self.flipselections()
        elif keypressed in ["c"]:
            return True
        elif keypressed in ["r"]:
            if self.reviewcommit():
                self.opts[b'review'] = True
                return True
        elif test and keypressed in ["R"]:
            self.opts[b'review'] = True
            return True
        elif keypressed in [" ", "x"]:
            self.toggleapply()
        elif keypressed in ["\n", "KEY_ENTER"]:
            self.toggleapply()
            self.nextsametype(test=test)
        elif keypressed in ["X"]:
            self.toggleallbetween()
        elif keypressed in ["A"]:
            self.toggleall()
        elif keypressed in ["e"]:
            self.toggleedit(test=test)
        elif keypressed in ["f"]:
            self.togglefolded()
        elif keypressed in ["F"]:
            self.togglefolded(foldparent=True)
        elif keypressed in ["m"]:
            self.commitMessageWindow()
        elif keypressed in ["g", "KEY_HOME"]:
            self.handlefirstlineevent()
        elif keypressed in ["G", "KEY_END"]:
            self.handlelastlineevent()
        elif keypressed in ["?"]:
            self.helpwindow()
            self.stdscr.clear()
            self.stdscr.refresh()
        elif keypressed in [curses.ascii.ctrl("L")]:
            # scroll the current line to the top of the screen, and redraw
            # everything
            self.scrolllines(self.selecteditemstartline)
            self.stdscr.clear()
            self.stdscr.refresh()

    def main(self, stdscr):
        """
        method to be wrapped by curses.wrapper() for selecting chunks.
        """

        origsigwinch = sentinel = object()
        if util.safehasattr(signal, b'SIGWINCH'):
            origsigwinch = signal.signal(signal.SIGWINCH, self.sigwinchhandler)
        try:
            return self._main(stdscr)
        finally:
            if origsigwinch is not sentinel:
                signal.signal(signal.SIGWINCH, origsigwinch)

    def _main(self, stdscr):
        self.stdscr = stdscr
        # error during initialization, cannot be printed in the curses
        # interface, it should be printed by the calling code
        self.initexc = None
        self.yscreensize, self.xscreensize = self.stdscr.getmaxyx()

        curses.start_color()
        try:
            curses.use_default_colors()
        except curses.error:
            self.usecolor = False

        # In some situations we may have some cruft left on the "alternate
        # screen" from another program (or previous iterations of ourself), and
        # we won't clear it if the scroll region is small enough to comfortably
        # fit on the terminal.
        self.stdscr.clear()

        # don't display the cursor
        try:
            curses.curs_set(0)
        except curses.error:
            pass

        # available colors: black, blue, cyan, green, magenta, white, yellow
        # init_pair(color_id, foreground_color, background_color)
        self.initcolorpair(None, None, name=b"normal")
        self.initcolorpair(
            curses.COLOR_WHITE, curses.COLOR_MAGENTA, name=b"selected"
        )
        self.initcolorpair(curses.COLOR_RED, None, name=b"deletion")
        self.initcolorpair(curses.COLOR_GREEN, None, name=b"addition")
        self.initcolorpair(
            curses.COLOR_WHITE, curses.COLOR_BLUE, name=b"legend"
        )
        # newwin([height, width,] begin_y, begin_x)
        self.statuswin = curses.newwin(self.numstatuslines, 0, 0, 0)
        self.statuswin.keypad(1)  # interpret arrow-key, etc. esc sequences

        # figure out how much space to allocate for the chunk-pad which is
        # used for displaying the patch

        # stupid hack to prevent getnumlinesdisplayed from failing
        self.chunkpad = curses.newpad(1, self.xscreensize)

        # add 1 so to account for last line text reaching end of line
        self.numpadlines = self.getnumlinesdisplayed(ignorefolding=True) + 1

        try:
            self.chunkpad = curses.newpad(self.numpadlines, self.xscreensize)
        except curses.error:
            self.initexc = fallbackerror(
                _(b'this diff is too large to be displayed')
            )
            return
        # initialize selecteditemendline (initial start-line is 0)
        self.selecteditemendline = self.getnumlinesdisplayed(
            self.currentselecteditem, recursechildren=False
        )

        while True:
            self.updatescreen()
            try:
                with self.ui.timeblockedsection(b'crecord'):
                    keypressed = self.statuswin.getkey()
                if self.errorstr is not None:
                    self.errorstr = None
                    continue
            except curses.error:
                keypressed = b"foobar"
            if self.handlekeypressed(keypressed):
                break

        if self.commenttext != b"":
            whitespaceremoved = re.sub(
                br"(?m)^\s.*(\n|$)", b"", self.commenttext
            )
            if whitespaceremoved != b"":
                self.opts[b'message'] = self.commenttext