beancount.utils

def bisect_left_with_key(sequence, value, key=None):
    """Find the last element before the given value in a sorted list.

    Args:
      sequence: A sorted sequence of elements.
      value: The value to search for.
      key: An optional function used to extract the value from the elements of
        sequence.
    Returns:
      Return the index. May return None.
    """
    # pylint: disable=invalid-name
    if key is None:
        key = lambda x: x  # Identity.

    lo = 0
    hi = len(sequence)

    while lo < hi:
        mid = (lo + hi) // 2
        if key(sequence[mid]) < value:
            lo = mid + 1
        else:
            hi = mid
    return lo

def bisect_right_with_key(a, x, key, lo=0, hi=None):
    """Like bisect.bisect_right, but with a key lookup parameter.

    Args:
      a: The list to search in.
      x: The element to search for.
      key: A function, to extract the value from the list.
      lo: The smallest index to search.
      hi: The largest index to search.
    Returns:
      As in bisect.bisect_right, an element from list 'a'.
    """
    # pylint: disable=invalid-name
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < key(a[mid]):
            hi = mid
        else:
            lo = mid+1
    return lo

def as_rows(string):
    """Split a string as rows of a CSV file.

    Args:
      string: A string to be split, the contents of a CSV file.
    Returns:
      Lists of lists of strings.
    """
    return list(csv.reader(io.StringIO(textwrap.dedent(string))))

def csv_clean_header(header_row):
    """Create a new class for the following rows from the header line.
    This both normalizes the header line and assign

    Args:
      header_row: A list of strings, the row with header titles.
    Returns:
      A list of strings, with possibly modified (cleaned) row titles, of the
      same lengths.
    """
    fieldnames = []
    for index, column in enumerate(header_row):
        field = column.lower()
        field = re.sub(r'\bp/l\b', 'pnl', field)
        field = re.sub('[^a-z0-9]', '_', field)
        field = field.strip(' _')
        field = re.sub('__+', '_', field)
        if not field:
            field = 'col{}'.format(index)
        assert field not in fieldnames, field
        fieldnames.append(field)
    return fieldnames

def csv_dict_reader(fileobj, **kw):
    """Read a CSV file yielding normalized dictionary fields.

    This is basically an alternative constructor for csv.DictReader that
    normalized the field names.

    Args:
      fileobj: A file object to be read.
      **kw: Optional arguments forwarded to csv.DictReader.
    Returns:
      A csv.DictReader object.
    """
    reader = csv.DictReader(fileobj, **kw)
    reader.fieldnames = csv_clean_header(reader.fieldnames)
    return reader

def csv_split_sections(rows):
    """Given rows, split them in at empty lines.
    This is useful for structured CSV files with multiple sections.

    Args:
      rows: A list of rows, which are themselves lists of strings.
    Returns:
      A list of sections, which are lists of rows, which are lists of strings.
    """
    sections = []
    current_section = []
    for row in rows:
        if row:
            current_section.append(row)
        else:
            sections.append(current_section)
            current_section = []
    if current_section:
        sections.append(current_section)
    return sections

def csv_split_sections_with_titles(rows):
    """Given a list of rows, split their sections. If the sections have single
    column titles, consume those lines as their names and return a mapping of
    section names.

    This is useful for CSV files with multiple sections, where the separator is
    a title. We use this to separate the multiple tables within the CSV files.

    Args:
      rows: A list of rows (list-of-strings).
    Returns:
     A list of lists of rows (list-of-strings).

    """
    sections_map = {}
    for index, section in enumerate(csv_split_sections(rows)):
        # Skip too short sections, cannot possibly be a title.
        if len(section) < 2:
            continue
        if len(section[0]) == 1 and len(section[1]) != 1:
            name = section[0][0]
            section = section[1:]
        else:
            name = 'Section {}'.format(index)
        sections_map[name] = section
    return sections_map

def csv_tuple_reader(fileobj, **kw):
    """Read a CSV file yielding namedtuple instances. The CSV file must have a
    header line.

    Args:
      fileobj: A file object to be read.
      **kw: Optional arguments forwarded to csv.DictReader.
    Yields:
      Nametuple instances, one for each row.
    """
    reader = csv.reader(fileobj, **kw)
    ireader = iter(reader)
    fieldnames = csv_clean_header(next(ireader))
    Tuple = collections.namedtuple('Row', fieldnames)
    for row in ireader:
        try:
            yield Tuple(*row)
        except TypeError:
            # If there's an error, it's usually from a line that has a 'END OF
            # LINE' marker at the end, or some comment line.
            assert len(row) in (0, 1)

def iter_sections(fileobj, separating_predicate=None):
    """For a given file object, yield file-like objects for each of the sections
    contained therein. A section is defined as a list of lines that don't match
    the predicate. For example, if you want to split by empty lines, provide a
    predicate that will be true given an empty line, which will cause a new
    section to be begun.

    Args:
      fileobj: A file object to read from.
      separating_predicate: A boolean predicate that is true on separating lines.
    Yields:
      A list of lines that you can use to iterate.
    """
    if separating_predicate is None:
        separating_predicate = lambda line: bool(line.strip())

    lineiter = iter(fileobj)
    for line in lineiter:
        if separating_predicate(line):
            iterator = itertools.chain((line,),
                                       iter_until_empty(lineiter,
                                                        separating_predicate))
            yield iterator
            for _ in iterator:
                pass

def iter_until_empty(iterator, separating_predicate=None):
    """An iterator of lines that will stop at the first empty line.

    Args:
      iterator: An iterator of lines.
      separating_predicate: A boolean predicate that is true on separating lines.
    Yields:
      Non-empty lines. EOF when we hit an empty line.
    """
    if separating_predicate is None:
        separating_predicate = lambda line: bool(line.strip())

    for line in iterator:
        if not separating_predicate(line):
            break
        yield line

@contextlib.contextmanager
def intimezone(tz_value: str):
    """Temporarily reset the value of TZ.

    This is used for testing.

    Args:
      tz_value: The value of TZ to set for the duration of this context.
    Returns:
      A contextmanager in the given timezone locale.
    """
    tz_old = os.environ.get('TZ', None)
    os.environ['TZ'] = tz_value
    time.tzset()
    try:
        yield
    finally:
        if tz_old is None:
            del os.environ['TZ']
        else:
            os.environ['TZ'] = tz_old
        time.tzset()

def iter_dates(start_date, end_date):
    """Yield all the dates between 'start_date' and 'end_date'.

    Args:
      start_date: An instance of datetime.date.
      end_date: An instance of datetime.date.
    Yields:
      Instances of datetime.date.
    """
    oneday = datetime.timedelta(days=1)
    date = start_date
    while date < end_date:
        yield date
        date += oneday

def next_month(date):
    """Compute the date at the beginning of the following month from the given date.

    Args:
      date: A datetime.date instance.
    Returns:
      A datetime.date instance, the first day of the month following 'date'.
    """
    # Compute the date at the beginning of the following month.
    year = date.year
    month = date.month + 1
    if date.month == 12:
        year += 1
        month = 1
    return datetime.date(year, month, 1)

def parse_date_liberally(string, parse_kwargs_dict=None):
    """Parse arbitrary strings to dates.

    This function is intended to support liberal inputs, so that we can use it
    in accepting user-specified dates on command-line scripts.

    Args:
      string: A string to parse.
      parse_kwargs_dict: Dict of kwargs to pass to dateutil parser.
    Returns:
      A datetime.date object.
    """
    # At the moment, rely on the most excellent dateutil.
    if parse_kwargs_dict is None:
        parse_kwargs_dict = {}
    return dateutil.parser.parse(string, **parse_kwargs_dict).date()

def render_ofx_date(dtime):
    """Render a datetime to the OFX format.

    Args:
      dtime: A datetime.datetime instance.
    Returns:
      A string, rendered to milliseconds.
    """
    return '{}.{:03d}'.format(dtime.strftime('%Y%m%d%H%M%S'),
                              int(dtime.microsecond / 1000))

def is_encrypted_file(filename):
    """Return true if the given filename contains an encrypted file.

    Args:
      filename: A path string.
    Returns:
      A boolean, true if the file contains an encrypted file.
    """
    _, ext = path.splitext(filename)
    if ext == '.gpg':
        return True
    if ext == '.asc':
        with open(filename) as encfile:
            head = encfile.read(1024)
            if re.search('--BEGIN PGP MESSAGE--', head):
                return True
    return False

def is_gpg_installed():
    """Return true if GPG 1.4.x or 2.x are installed, which is what we use and support."""
    try:
        pipe = subprocess.Popen(['gpg', '--version'], shell=0,
                                stdout=subprocess.PIPE, stderr=subprocess.PIPE)
        out, err = pipe.communicate()
        version_text = out.decode('utf8')
        return pipe.returncode == 0 and re.match(r'gpg \(GnuPG\) (1\.4|2)\.', version_text)
    except OSError:
        return False

def read_encrypted_file(filename):
    """Decrypt and read an encrypted file without temporary storage.

    Args:
      filename: A string, the path to the encrypted file.
    Returns:
      A string, the contents of the file.
    Raises:
      OSError: If we could not properly decrypt the file.
    """
    command = ['gpg', '--batch', '--decrypt', path.realpath(filename)]
    pipe = subprocess.Popen(command,
                            shell=False,
                            stdout=subprocess.PIPE,
                            stderr=subprocess.PIPE)
    contents, errors = pipe.communicate()
    if pipe.returncode != 0:
        raise OSError("Could not decrypt file ({}): {}".format(pipe.returncode,
                                                               errors.decode('utf8')))
    return contents.decode('utf-8')

def guess_file_type(filename):
    """Attempt to guess the type of the input file.

    Args:
      filename: A string, the name of the file to guess the type for.
    Returns:
      A suitable mimetype string, or None if we could not guess.
    """

    # Try the standard mimetypes association.
    filetype, _ = mimetypes.guess_type(filename, False)
    if filetype:
        return filetype

    # Try out some extra types that only we know about.
    for regexp, mimetype in EXTRA_FILE_TYPES:
        if regexp.match(filename):
            return mimetype

    # Try out libmagic, if it is installed.
    if magic:
        filetype = magic.from_file(filename, mime=True)
        if isinstance(filetype, bytes):
            filetype = filetype.decode('utf8')
        return filetype
    else:
        raise ValueError(("Could not identify the type of file '{}'; "
                          "try installing python-magic").format(filename))

@contextlib.contextmanager
def chdir(directory):
    """Temporarily chdir to the given directory.

    Args:
      directory: The directory to switch do.
    Returns:
      A context manager which restores the cwd after running.
    """
    cwd = os.getcwd()
    os.chdir(directory)
    try:
        yield cwd
    finally:
        os.chdir(cwd)

def find_files(fords,
               ignore_dirs=('.hg', '.svn', '.git'),
               ignore_files=('.DS_Store',)):
    """Enumerate the files under the given directories, stably.

    Invalid file or directory names will be logged to the error log.

    Args:
      fords: A list of strings, file or directory names.
      ignore_dirs: A list of strings, filenames or directories to be ignored.
    Yields:
      Strings, full filenames from the given roots.
    """
    if isinstance(fords, str):
        fords = [fords]
    assert isinstance(fords, (list, tuple))
    for ford in fords:
        if path.isdir(ford):
            for root, dirs, filenames in os.walk(ford):
                dirs[:] = sorted(dirname for dirname in dirs if dirname not in ignore_dirs)
                for filename in sorted(filenames):
                    if filename in ignore_files:
                        continue
                    yield path.join(root, filename)
        elif path.isfile(ford) or path.islink(ford):
            yield ford
        elif not path.exists(ford):
            logging.error("File or directory '{}' does not exist.".format(ford))

def guess_file_format(filename, default=None):
    """Guess the file format from the filename.

    Args:
      filename: A string, the name of the file. This can be None.
    Returns:
      A string, the extension of the format, without a leading period.
    """
    if filename:
        if filename.endswith('.txt') or filename.endswith('.text'):
            format = 'text'
        elif filename.endswith('.csv'):
            format = 'csv'
        elif filename.endswith('.html') or filename.endswith('.xhtml'):
            format = 'html'
        else:
            format = default
    else:
        format = default
    return format

def path_greedy_split(filename):
    """Split a path, returning the longest possible extension.

    Args:
      filename: A string, the filename to split.
    Returns:
      A pair of basename, extension (which includes the leading period).
    """
    basename = path.basename(filename)
    index = basename.find('.')
    if index == -1:
        extension = None
    else:
        extension = basename[index:]
        basename = basename[:index]
    return (path.join(path.dirname(filename), basename), extension)

def touch_file(filename, *otherfiles):
    """Touch a file and wait until its timestamp has been changed.

    Args:
      filename: A string path, the name of the file to touch.
      otherfiles: A list of other files to ensure the timestamp is beyond of.
    """
    # Note: You could set os.stat_float_times() but then the main function would
    # have to set that up as well. It doesn't help so much, however, since
    # filesystems tend to have low resolutions, e.g. one second.
    orig_mtime_ns = max(os.stat(minfile).st_mtime_ns
                        for minfile in (filename,) + otherfiles)
    delay_secs = 0.05
    while True:
        with open(filename, 'a'):
            os.utime(filename)
        time.sleep(delay_secs)
        new_stat = os.stat(filename)
        if new_stat.st_mtime_ns > orig_mtime_ns:
            break

def import_symbol(dotted_name):
    """Import a symbol in an arbitrary module.

    Args:
      dotted_name: A dotted path to a symbol.
    Returns:
      The object referenced by the given name.
    Raises:
      ImportError: If the module not not be imported.
      AttributeError: If the symbol could not be found in the module.
    """
    comps = dotted_name.split('.')
    module_name = '.'.join(comps[:-1])
    symbol_name = comps[-1]
    module = importlib.import_module(module_name)
    return getattr(module, symbol_name)

def instrument_invariants(klass, prefun, postfun):
    """Instrument the class 'klass' with pre/post invariant
    checker functions.

    Args:
      klass: A class object, whose methods to be instrumented.
      prefun: A function that checks invariants pre-call.
      postfun: A function that checks invariants pre-call.
    """
    instrumented = {}
    for attrname, object_ in klass.__dict__.items():
        if attrname.startswith('_'):
            continue
        if not isinstance(object_, types.FunctionType):
            continue
        instrumented[attrname] = object_
        setattr(klass, attrname,
                invariant_check(object_, prefun, postfun))
    klass.__instrumented = instrumented

def invariant_check(method, prefun, postfun):
    """Decorate a method with the pre/post invariant checkers.

    Args:
      method: An unbound method to instrument.
      prefun: A function that checks invariants pre-call.
      postfun: A function that checks invariants post-call.
    Returns:
      An unbound method, decorated.
    """
    reentrant = []
    def new_method(self, *args, **kw):
        reentrant.append(None)
        if len(reentrant) == 1:
            prefun(self)
        result = method(self, *args, **kw)
        if len(reentrant) == 1:
            postfun(self)
        reentrant.pop()
        return result
    return new_method

def uninstrument_invariants(klass):
    """Undo the instrumentation for invariants.

    Args:
      klass: A class object, whose methods to be uninstrumented.
    """
    instrumented = getattr(klass, '__instrumented', None)
    if instrumented:
        for attrname, object_ in instrumented.items():
            setattr(klass, attrname, object_)
    del klass.__instrumented

def memoize_recent_fileobj(function, cache_filename, expiration=None):
    """Memoize recent calls to the given function which returns a file object.

    The results of the cache expire after some time.

    Args:
      function: A callable object.
      cache_filename: A string, the path to the database file to cache to.
      expiration: The time during which the results will be kept valid. Use
        'None' to never expire the cache (this is the default).
    Returns:
      A memoized version of the function.
    """
    urlcache = shelve.open(cache_filename, 'c')
    urlcache.lock = threading.Lock()  # Note: 'shelve' is not thread-safe.
    @functools.wraps(function)
    def memoized(*args, **kw):
        # Encode the arguments, including a date string in order to invalidate
        # results over some time.
        md5 = hashlib.md5()
        md5.update(str(args).encode('utf-8'))
        md5.update(str(sorted(kw.items())).encode('utf-8'))

        hash_ = md5.hexdigest()
        time_now = now()
        try:
            with urlcache.lock:
                time_orig, contents = urlcache[hash_]
            if expiration is not None and (time_now - time_orig) > expiration:
                raise KeyError
        except KeyError:
            fileobj = function(*args, **kw)
            if fileobj:
                contents = fileobj.read()
                with urlcache.lock:
                    urlcache[hash_] = (time_now, contents)
            else:
                contents = None

        return io.BytesIO(contents) if contents else None
    return memoized

def now():
    "Indirection on datetime.datetime.now() for testing."
    return datetime.datetime.now()

@contextlib.contextmanager
def box(name=None, file=None):
    """A context manager that prints out a box around a block.
    This is useful for printing out stuff from tests in a way that is readable.

    Args:
      name: A string, the name of the box to use.
      file: The file object to print to.
    Yields:
      None.
    """
    file = file or sys.stdout
    file.write('\n')
    if name:
        header = ',--------({})--------\n'.format(name)
        footer = '`{}\n'.format('-' * (len(header)-2))
    else:
        header = ',----------------\n'
        footer = '`----------------\n'

    file.write(header)
    yield
    file.write(footer)
    file.flush()

def cmptuple(name, attributes):
    """Manufacture a comparable namedtuple class, similar to collections.namedtuple.

    A comparable named tuple is a tuple which compares to False if contents are
    equal but the data types are different. We define this to supplement
    collections.namedtuple because by default a namedtuple disregards the type
    and we want to make precise comparisons for tests.

    Args:
      name: The given name of the class.
      attributes: A string or tuple of strings, with the names of the
        attributes.
    Returns:
      A new namedtuple-derived type that compares False with other
      tuples with same contents.
    """
    base = collections.namedtuple('_{}'.format(name), attributes)
    return type(name, (TypeComparable, base,), {})

def compute_unique_clean_ids(strings):
    """Given a sequence of strings, reduce them to corresponding ids without any
    funny characters and insure that the list of ids is unique. Yields pairs
    of (id, string) for the result.

    Args:
      strings: A list of strings.
    Returns:
      A list of (id, string) pairs.
    """
    string_set = set(strings)

    # Try multiple methods until we get one that has no collisions.
    for regexp, replacement in [(r'[^A-Za-z0-9.-]', '_'),
                                (r'[^A-Za-z0-9_]', ''),]:
        seen = set()
        idmap = {}
        mre = re.compile(regexp)
        for string in string_set:
            id_ = mre.sub(replacement, string)
            if id_ in seen:
                break  # Collision.
            seen.add(id_)
            idmap[id_] = string
        else:
            break
    else:
        return None # Could not find a unique mapping.

    return idmap

def deprecated(message):
    """A decorator generator to mark functions as deprecated and log a warning."""
    def decorator(func):
        @functools.wraps(func)
        def new_func(*args, **kwargs):
            warnings.warn("Call to deprecated function {}: {}".format(func.__name__,
                                                                      message),
                          category=DeprecationWarning,
                          stacklevel=2)
            return func(*args, **kwargs)
        return new_func
    return decorator

def dictmap(mdict, keyfun=None, valfun=None):
    """Map a dictionary's value.

    Args:
      mdict: A dict.
      key: A callable to apply to the keys.
      value: A callable to apply to the values.
    """
    if keyfun is None:
        keyfun = lambda x: x
    if valfun is None:
        valfun = lambda x: x
    return {keyfun(key): valfun(val) for key, val in mdict.items()}

def escape_string(string):
    """Escape quotes and backslashes in payee and narration.

    Args:
      string: Any string.
    Returns.
      The input string, with offending characters replaced.
    """
    return string.replace('\\', r'\\')\
                 .replace('"', r'\"')

def filter_type(elist, types):
    """Filter the given list to yield only instances of the given types.

    Args:
      elist: A sequence of elements.
      types: A sequence of types to include in the output list.
    Yields:
      Each element, if it is an instance of 'types'.
    """
    for element in elist:
        if not isinstance(element, types):
            continue
        yield element

def first_paragraph(docstring):
    """Return the first sentence of a docstring.
    The sentence has to be delimited by an empty line.

    Args:
      docstring: A doc string.
    Returns:
      A string with just the first sentence on a single line.
    """
    lines = []
    for line in docstring.strip().splitlines():
        if not line:
            break
        lines.append(line.rstrip())
    return ' '.join(lines)

def get_screen_height():
    """Return the height of the terminal that runs this program.

    Returns:
      An integer, the number of characters the screen is high.
      Return 0 if the terminal cannot be initialized.
    """
    return _get_screen_value('lines', 0)

def get_screen_width():
    """Return the width of the terminal that runs this program.

    Returns:
      An integer, the number of characters the screen is wide.
      Return 0 if the terminal cannot be initialized.
    """
    return _get_screen_value('cols', 0)

def get_tuple_values(ntuple, predicate, memo=None):
    """Return all members referred to by this namedtuple instance that satisfy the
    given predicate. This function also works recursively on its members which
    are lists or tuples, and so it can be used for Transaction instances.

    Args:
      ntuple: A tuple or namedtuple.
      predicate: A predicate function that returns true if an attribute is to be
        output.
      memo: An optional memoizing dictionary. If a tuple has already been seen, the
        recursion will be avoided.
    Yields:
      Attributes of the tuple and its sub-elements if the predicate is true.
    """
    if memo is None:
        memo = set()
    id_ntuple = id(ntuple)
    if id_ntuple in memo:
        return
    memo.add(id_ntuple)

    if predicate(ntuple):
        yield
    for attribute in ntuple:
        if predicate(attribute):
            yield attribute
        if isinstance(attribute, (list, tuple)):
            for value in get_tuple_values(attribute, predicate, memo):
                yield value

def groupby(keyfun, elements):
    """Group the elements as a dict of lists, where the key is computed using the
    function 'keyfun'.

    Args:
      keyfun: A callable, used to obtain the group key from each element.
      elements: An iterable of the elements to group.
    Returns:
      A dict of key to list of sequences.
    """
    # Note: We could allow a custom aggregation function. Another option is
    # provide another method to reduce the list values of a dict, but that can
    # be accomplished using a dict comprehension.
    grouped = defaultdict(list)
    for element in elements:
        grouped[keyfun(element)].append(element)
    return grouped

def idify(string):
    """Replace characters objectionable for a filename with underscores.

    Args:
      string: Any string.
    Returns:
      The input string, with offending characters replaced.
    """
    for sfrom, sto in [(r'[ \(\)]+', '_'),
                      (r'_*\._*', '.')]:
        string = re.sub(sfrom, sto, string)
    string = string.strip('_')
    return string

def import_curses():
    """Try to import the 'curses' module.
    (This is used here in order to override for tests.)

    Returns:
      The curses module, if it was possible to import it.
    Raises:
      ImportError: If the module could not be imported.
    """
    # Note: There's a recipe for getting terminal size on Windows here, without
    # curses, I should probably implement that at some point:
    # https://stackoverflow.com/questions/263890/how-do-i-find-the-width-height-of-a-terminal-window
    # Also, consider just using 'blessings' instead, which provides this across
    # multiple platforms.
    # pylint: disable=import-outside-toplevel
    import curses
    return curses

def is_sorted(iterable, key=lambda x: x, cmp=lambda x, y: x <= y):
    """Return true if the sequence is sorted.

    Args:
      iterable: An iterable sequence.
      key: A function to extract the quantity by which to sort.
      cmp: A function that compares two elements of a sequence.
    Returns:
      A boolean, true if the sequence is sorted.
    """
    iterator = map(key, iterable)
    prev = next(iterator)
    for element in iterator:
        if not cmp(prev, element):
            return False
        prev = element
    return True

@contextlib.contextmanager
def log_time(operation_name, log_timings, indent=0):
    """A context manager that times the block and logs it to info level.

    Args:
      operation_name: A string, a label for the name of the operation.
      log_timings: A function to write log messages to. If left to None,
        no timings are written (this becomes a no-op).
      indent: An integer, the indentation level for the format of the timing
        line. This is useful if you're logging timing to a hierarchy of
        operations.
    Yields:
      The start time of the operation.
    """
    time1 = time()
    yield time1
    time2 = time()
    if log_timings:
        log_timings("Operation: {:48} Time: {}{:6.0f} ms".format(
            "'{}'".format(operation_name), '      '*indent, (time2 - time1) * 1000))

def longest(seq):
    """Return the longest of the given subsequences.

    Args:
      seq: An iterable sequence of lists.
    Returns:
      The longest list from the sequence.
    """
    longest, length = None, -1
    for element in seq:
        len_element = len(element)
        if len_element > length:
            longest, length = element, len_element
    return longest

def map_namedtuple_attributes(attributes, mapper, object_):
    """Map the value of the named attributes of object by mapper.

    Args:
      attributes: A sequence of string, the attribute names to map.
      mapper: A callable that accepts the value of a field and returns
        the new value.
      object_: Some namedtuple object with attributes on it.
    Returns:
      A new instance of the same namedtuple with the named fields mapped by
      mapper.
    """
    return object_._replace(**{attribute: mapper(getattr(object_, attribute))
                               for attribute in attributes})

def replace_namedtuple_values(ntuple, predicate, mapper, memo=None):
    """Recurse through all the members of namedtuples and lists, and for
    members that match the given predicate, run them through the given mapper.

    Args:
      ntuple: A namedtuple instance.
      predicate: A predicate function that returns true if an attribute is to be
        output.
      mapper: A callable, that will accept a single argument and return its
        replacement value.
      memo: An optional memoizing dictionary. If a tuple has already been seen, the
        recursion will be avoided.
    Yields:
      Attributes of the tuple and its sub-elements if the predicate is true.
    """
    if memo is None:
        memo = set()
    id_ntuple = id(ntuple)
    if id_ntuple in memo:
        return None
    memo.add(id_ntuple)

    # pylint: disable=unidiomatic-typecheck
    if not (type(ntuple) is not tuple and isinstance(ntuple, tuple)):
        return ntuple
    replacements = {}
    for attribute_name, attribute in zip(ntuple._fields, ntuple):
        if predicate(attribute):
            replacements[attribute_name] = mapper(attribute)
        elif type(attribute) is not tuple and isinstance(attribute, tuple):
            replacements[attribute_name] = replace_namedtuple_values(
                attribute, predicate, mapper, memo)
        elif type(attribute) in (list, tuple):
            replacements[attribute_name] = [
                replace_namedtuple_values(member, predicate, mapper, memo)
                for member in attribute]
    return ntuple._replace(**replacements)

def skipiter(iterable, num_skip):
    """Skip some elements from an iterator.

    Args:
      iterable: An iterator.
      num_skip: The number of elements in the period.
    Yields:
      Elements from the iterable, with num_skip elements skipped.
      For example, skipiter(range(10), 3) yields [0, 3, 6, 9].
    """
    assert num_skip > 0
    sit = iter(iterable)
    while 1:
        try:
            value = next(sit)
        except StopIteration:
            return
        yield value
        for _ in range(num_skip-1):
            try:
                next(sit)
            except StopIteration:
                return

def sorted_uniquify(iterable, keyfunc=None, last=False):
    """Given a sequence of elements, sort and remove duplicates of the given key.
    Keep either the first or the last (by key) element of a sequence of
    key-identical elements. This does _not_ maintain the ordering of the
    original elements, they are returned sorted (by key) instead.

    Args:
      iterable: An iterable sequence.
      keyfunc: A function that extracts from the elements the sort key
        to use and uniquify on. If left unspecified, the identify function
        is used and the uniquification occurs on the elements themselves.
      last: A boolean, True if we should keep the last item of the same keys.
        Otherwise keep the first.
    Yields:
      Elements from the iterable.
    """
    if keyfunc is None:
        keyfunc = lambda x: x
    if last:
        prev_obj = UNSET
        prev_key = UNSET
        for obj in sorted(iterable, key=keyfunc):
            key = keyfunc(obj)
            if key != prev_key and prev_obj is not UNSET:
                yield prev_obj
            prev_obj = obj
            prev_key = key
        if prev_obj is not UNSET:
            yield prev_obj
    else:
        prev_key = UNSET
        for obj in sorted(iterable, key=keyfunc):
            key = keyfunc(obj)
            if key != prev_key:
                yield obj
                prev_key = key

def staticvar(varname, initial_value):
    """Returns a decorator that defines a Python function attribute.

    This is used to simulate a static function variable in Python.

    Args:
      varname: A string, the name of the variable to define.
      initial_value: The value to initialize the variable to.
    Returns:
      A function decorator.
    """
    def deco(fun):
        setattr(fun, varname, initial_value)
        return fun
    return deco

@contextlib.contextmanager
def swallow(*exception_types):
    """Catch and ignore certain exceptions.

    Args:
      exception_types: A tuple of exception classes to ignore.
    Yields:
      None.
    """
    try:
        yield
    except Exception as exc:
        if not isinstance(exc, exception_types):
            raise

def uniquify(iterable, keyfunc=None, last=False):
    """Given a sequence of elements, remove duplicates of the given key. Keep either
    the first or the last element of a sequence of key-identical elements. Order
    is maintained as much as possible. This does maintain the ordering of the
    original elements, they are returned in the same order as the original
    elements.

    Args:
      iterable: An iterable sequence.
      keyfunc: A function that extracts from the elements the sort key
        to use and uniquify on. If left unspecified, the identify function
        is used and the uniquification occurs on the elements themselves.
      last: A boolean, True if we should keep the last item of the same keys.
        Otherwise keep the first.
    Yields:
      Elements from the iterable.
    """
    if keyfunc is None:
        keyfunc = lambda x: x
    seen = set()
    if last:
        unique_reversed_list = []
        for obj in reversed(iterable):
            key = keyfunc(obj)
            if key not in seen:
                seen.add(key)
                unique_reversed_list.append(obj)
        yield from reversed(unique_reversed_list)
    else:
        for obj in iterable:
            key = keyfunc(obj)
            if key not in seen:
                seen.add(key)
                yield obj

def retrying_urlopen(url, timeout=5, max_retry=5):
    """Open and download the given URL, retrying if it times out.

    Args:
      url: A string, the URL to fetch.
      timeout: A timeout after which to stop waiting for a response and return an
        error.
      max_retry: The maximum number of times to retry.
    Returns:
      The contents of the fetched URL.
    """
    for _ in range(max_retry):
        logging.debug("Reading %s", url)
        try:
            response = request.urlopen(url, timeout=timeout)
            if response:
                break
        except error.URLError:
            return None
    if response and response.getcode() != 200:
        return None
    return response

def create_pager(command, file):
    """Try to create and return a pager subprocess.

    Args:
      command: A string, the shell command to run as a pager.
      file: The file object for the pager write to. This is also used as a
        default if we failed to create the pager subprocess.
    Returns:
      A pair of (file, pipe), a file object and an optional subprocess.Popen instance
      to wait on. The pipe instance may be set to None if we failed to create a subprocess.
    """

    if command is None:
        command = os.environ.get('PAGER', DEFAULT_PAGER)
    if not command:
        command = DEFAULT_PAGER

    pipe = None

    # In case of using 'less', make sure the charset is set properly. In theory
    # you could override this by setting PAGER to "LESSCHARSET=utf-8 less" but
    # this shouldn't affect other programs and is unlikely to cause problems, so
    # we set it here to make default behavior work for most people (we always
    # write UTF-8).
    env = os.environ.copy()
    env['LESSCHARSET'] = "utf-8"

    try:
        pipe = subprocess.Popen(command, shell=True,
                                stdin=subprocess.PIPE,
                                stdout=file,
                                env=env)
    except OSError as exc:
        logging.error("Invalid pager: {}".format(exc))
    else:
        stdin_wrapper = io.TextIOWrapper(pipe.stdin, 'utf-8')
        file = stdin_wrapper
    return file, pipe

@contextlib.contextmanager
def flush_only(fileobj):
    """A contextmanager around a file object that does not close the file.

    This is used to return a context manager on a file object but not close it.
    We flush it instead. This is useful in order to provide an alternative to a
    pager class as above.

    Args:
      fileobj: A file object, to remain open after running the context manager.
    Yields:
      A context manager that yields this object.
    """
    try:
        yield fileobj
    finally:
        fileobj.flush()

def re_replace_unicode(regexp):
    """Substitute Unicode Properties in regular expressions with their
    corresponding expanded ranges.

    Args:
      regexp: A regular expression string.
    Returns:
      Return the regular expression with Unicode Properties substituted.
    """
    for category, rangestr in UNICODE_RANGES.items():
        regexp = regexp.replace(r'\p{' + category + '}', rangestr)
    return regexp

def snoopify(function):
    """Decorate a function as snoopable.

    This is meant to reassign existing functions to a snoopable version of them.
    For example, if you wanted 're.match' to be automatically snoopable, just
    decorate it like this:

      re.match = snoopify(re.match)

    and then you can just call 're.match' in a conditional and then access
    're.match.value' to get to the last returned value.
    """
    @functools.wraps(function)
    def wrapper(*args, **kw):
        value = function(*args, **kw)
        wrapper.value = value
        return value
    wrapper.value = None
    return wrapper

def call_command(command):
    """Run the script with a subprocess.

    Args:
      script_args: A list of strings, the arguments to the subprocess,
        including the script name.
    Returns:
      A triplet of (return code integer, stdout ext, stderr text).
    """
    assert isinstance(command, list), command
    p = subprocess.Popen(command,
                         stdout=subprocess.PIPE,
                         stderr=subprocess.PIPE)
    stdout, stderr = p.communicate()
    return p.returncode, stdout.decode(), stderr.decode()

def capture(*attributes):
    """A context manager that captures what's printed to stdout.

    Args:
      *attributes: A tuple of strings, the name of the sys attributes to override
        with StringIO instances.
    Yields:
      A StringIO string accumulator.
    """
    if not attributes:
        attributes = 'stdout'
    elif len(attributes) == 1:
        attributes = attributes[0]
    return patch(sys, attributes, io.StringIO)

def create_temporary_files(root, contents_map):
    """Create a number of temporary files under 'root'.

    This routine is used to initialize the contents of multiple files under a
    temporary directory.

    Args:
      root: A string, the name of the directory under which to create the files.
      contents_map: A dict of relative filenames to their contents. The content
        strings will be automatically dedented for convenience. In addition, the
        string 'ROOT' in the contents will be automatically replaced by the root
        directory name.
    """
    os.makedirs(root, exist_ok=True)
    for relative_filename, contents in contents_map.items():
        assert not path.isabs(relative_filename)
        filename = path.join(root, relative_filename)
        os.makedirs(path.dirname(filename), exist_ok=True)

        clean_contents = textwrap.dedent(contents.replace('{root}', root))
        with open(filename, 'w') as f:
            f.write(clean_contents)

def docfile(function, **kwargs):
    """A decorator that write the function's docstring to a temporary file
    and calls the decorated function with the temporary filename.  This is
    useful for writing tests.

    Args:
      function: A function to decorate.
    Returns:
      The decorated function.
    """
    @functools.wraps(function)
    def new_function(self):
        allowed = ('buffering', 'encoding', 'newline', 'dir', 'prefix', 'suffix')
        if any([key not in allowed for key in kwargs]):
            raise ValueError("Invalid kwarg to docfile_extra")
        with tempfile.NamedTemporaryFile('w', **kwargs) as file:
            text = function.__doc__
            file.write(textwrap.dedent(text))
            file.flush()
            return function(self, file.name)
    new_function.__doc__ = None
    return new_function

def docfile_extra(**kwargs):
    """
    A decorator identical to @docfile,
    but it also takes kwargs for the temporary file,
    Kwargs:
      e.g. buffering, encoding, newline, dir, prefix, and suffix.
    Returns:
      docfile
    """
    return functools.partial(docfile, **kwargs)

@contextlib.contextmanager
def environ(varname, newvalue):
    """A context manager which pushes varname's value and restores it later.

    Args:
      varname: A string, the environ variable name.
      newvalue: A string, the desired value.
    """
    oldvalue = os.environ.get(varname, None)
    os.environ[varname] = newvalue
    yield
    if oldvalue is not None:
        os.environ[varname] = oldvalue
    else:
        del os.environ[varname]

def find_python_lib():
    """Return the path to the root of the Python libraries.

    Returns:
      A string, the root directory.
    """
    return path.dirname(path.dirname(path.dirname(__file__)))

def find_repository_root(filename=None):
    """Return the path to the repository root.

    Args:
      filename: A string, the name of a file within the repository.
    Returns:
      A string, the root directory.
    """
    if filename is None:
        filename = __file__

    # Support root directory under Bazel.
    match = re.match(r"(.*\.runfiles/beancount)/", filename)
    if match:
        return match.group(1)

    while not all(path.exists(path.join(filename, sigfile))
                  for sigfile in ('PKG-INFO', 'COPYING', 'README.rst')):
        prev_filename = filename
        filename = path.dirname(filename)
        if prev_filename == filename:
            raise ValueError("Failed to find the root directory.")
    return filename

def make_failing_importer(*removed_module_names):
    """Make an importer that raise an ImportError for some modules.

    Use it like this:

      @mock.patch('builtins.__import__', make_failing_importer('setuptools'))
      def test_...

    Args:
      removed_module_name: The name of the module import that should raise an exception.
    Returns:
      A decorated test decorator.
    """
    def failing_import(name, *args, **kwargs):
        if name in removed_module_names:
            raise ImportError("Could not import {}".format(name))
        return builtins.__import__(name, *args, **kwargs)
    return failing_import

def nottest(func):
    "Make the given function not testable."
    func.__test__ = False
    return func

@contextlib.contextmanager
def patch(obj, attributes, replacement_type):
    """A context manager that temporarily patches an object's attributes.

    All attributes in 'attributes' are saved and replaced by new instances
    of type 'replacement_type'.

    Args:
      obj: The object to patch up.
      attributes: A string or a sequence of strings, the names of attributes to replace.
      replacement_type: A callable to build replacement objects.
    Yields:
      An instance of a list of sequences of 'replacement_type'.
    """
    single = isinstance(attributes, str)
    if single:
        attributes = [attributes]

    saved = []
    replacements = []
    for attribute in attributes:
        replacement = replacement_type()
        replacements.append(replacement)
        saved.append(getattr(obj, attribute))
        setattr(obj, attribute, replacement)

    yield replacements[0] if single else replacements

    for attribute, saved_attr in zip(attributes, saved):
        setattr(obj, attribute, saved_attr)

def record(fun):
    """Decorates the function to intercept and record all calls and return values.

    Args:
      fun: A callable to be decorated.
    Returns:
      A wrapper function with a .calls attribute, a list of RCall instances.
    """
    @functools.wraps(fun)
    def wrapped(*args, **kw):
        return_value = fun(*args, **kw)
        wrapped.calls.append(RCall(args, kw, return_value))
        return return_value
    wrapped.calls = []
    return wrapped

def run_with_args(function, args):
    """Run the given function with sys.argv set to argv. The first argument is
    automatically inferred to be where the function object was defined. sys.argv
    is restored after the function is called.

    Args:
      function: A function object to call with no arguments.
      argv: A list of arguments, excluding the script name, to be temporarily
        set on sys.argv.
    Returns:
      The return value of the function run.
    """
    saved_argv = sys.argv
    saved_handlers = logging.root.handlers
    try:
        module = sys.modules[function.__module__]
        sys.argv = [module.__file__] + args
        logging.root.handlers = []
        return function()
    finally:
        sys.argv = saved_argv
        logging.root.handlers = saved_handlers

def search_words(words, line):
    """Search for a sequence of words in a line.

    Args:
      words: A list of strings, the words to look for, or a space-separated string.
      line: A string, the line to search into.
    Returns:
      A MatchObject, or None.
    """
    if isinstance(words, str):
        words = words.split()
    return re.search('.*'.join(r'\b{}\b'.format(word) for word in words), line)

@contextlib.contextmanager
def skipIfRaises(*exc_types):
    """A context manager (or decorator) that skips a test if an exception is raised.

    Args:
      exc_type
    Yields:
      Nothing, for you to execute the function code.
    Raises:
      SkipTest: if the test raised the expected exception.
    """
    try:
        yield
    except exc_types as exception:
        raise unittest.SkipTest(exception)

def subprocess_env():
    """Return a dict to use as environment for running subprocesses.

    Returns:
      A string, the root directory.
    """
    # Ensure we have locations to invoke our Python executable and our
    # runnable binaries in the test environment to run subprocesses.
    binpath = ':'.join([
        path.dirname(sys.executable),
        path.join(find_repository_root(__file__), 'bin'),
        os.environ.get('PATH', '').strip(':')]).strip(':')
    return {'PATH': binpath,
            'PYTHONPATH': find_python_lib()}

@contextlib.contextmanager
def tempdir(delete=True, **kw):
    """A context manager that creates a temporary directory and deletes its
    contents unconditionally once done.

    Args:
      delete: A boolean, true if we want to delete the directory after running.
      **kw: Keyword arguments for mkdtemp.
    Yields:
      A string, the name of the temporary directory created.
    """
    tempdir = tempfile.mkdtemp(prefix="beancount-test-tmpdir.", **kw)
    try:
        yield tempdir
    finally:
        if delete:
            shutil.rmtree(tempdir, ignore_errors=True)

def entitize_ampersand(filename):
    """Convert unescaped ampersand characters (&) to XML entities.

    This is used to fix code that has been programmed by bad developers who
    didn't think about escaping the entities in their strings.
    file does not contain
    Args:
      filename: A string, the name of the file to convert.
    Returns:
      A self-destructing NamedTemporaryFile object that has been flushed and
      which you may read to obtain the fixed contents.
    """
    tidy_file = tempfile.NamedTemporaryFile(suffix='.xls', mode='w', delete=False)
    with open(filename) as infile:
        contents = infile.read()
    new_contents = re.sub('&([^;&]{12})', '&\\1', contents)
    tidy_file.write(new_contents)
    tidy_file.flush()
    return tidy_file

def replace_number(match):
    """Replace a single number matched from text into X'es.
    'match' is a MatchObject from a regular expressions match.
    (Use this with re.sub()).

    Args:
      match: A MatchObject.
    Returns:
      A replacement string, consisting only of X'es.
    """
    return re.sub('[0-9]', 'X', match.group(1)) + match.group(2)

def replace_numbers(text):
    """Replace all numbers found within text.

    Note that this is a heuristic used to filter out private numbers from web
    pages in incognito mode and thus may not be perfect. It should let through
    numbers which are part of URLs.

    Args:
      text: An input string object.
    Returns:
      A string, with relevant numbers hopefully replaced with X'es.

    """
    return re.sub(r'\b([0-9,]+(?:\.[0-9]*)?)\b([ \t<]+[^0-9,.]|$)', replace_number, text)

def ArgumentParser(*args, **kwargs):
    """Add a standard --version option to an ArgumentParser.

    Args:
      *args: Arguments for the parser.
      *kwargs: Keyword arguments for the parser.
    Returns:
      An instance of ArgumentParser, with our default options set.
    """
    parser = argparse.ArgumentParser(*args, **kwargs)

    parser.add_argument('--version', '-V', action='version',
                        version=compute_version_string(
                            beancount.__version__,
                            _parser.__vc_changeset__,
                            _parser.__vc_timestamp__))

    return parser

def compute_version_string(version, changeset, timestamp):
    """Compute a version string from the changeset and timestamp baked in the parser.

    Args:
      version: A string, the version number.
      changeset: A string, a version control string identifying the commit of the version.
      timestamp: An integer, the UNIX epoch timestamp of the changeset.
    Returns:
      A human-readable string for the version.
    """
    # Shorten changeset.
    if changeset:
        if re.match('hg:', changeset):
            changeset = changeset[:15]
        elif re.match('git:', changeset):
            changeset = changeset[:12]

    # Convert timestamp to a date.
    date = None
    if timestamp > 0:
        date = datetime.datetime.utcfromtimestamp(timestamp).date()

    version = 'Beancount {}'.format(version)
    if changeset or date:
        version = '{} ({})'.format(
            version, '; '.join(map(str, filter(None, [changeset, date]))))

    return version