beancount.core

def commonprefix(accounts):
    """Return the common prefix of a list of account names.

    Args:
      accounts: A sequence of account name strings.
    Returns:
      A string, the common parent account. If none, returns an empty string.
    """
    accounts_lists = [account_.split(sep)
                      for account_ in accounts]
    # Note: the os.path.commonprefix() function just happens to work here.
    # Inspect its code, and even the special case of no common prefix
    # works well with str.join() below.
    common_list = path.commonprefix(accounts_lists)
    return sep.join(common_list)

def has_component(account_name, component):
    """Return true if one of the account contains a given component.

    Args:
      account_name: A string, an account name.
      component: A string, a component of an account name. For instance,
        ``Food`` in ``Expenses:Food:Restaurant``. All components are considered.
    Returns:
      Boolean: true if the component is in the account. Note that a component
      name must be whole, that is ``NY`` is not in ``Expenses:Taxes:StateNY``.
    """
    return bool(re.search('(^|:){}(:|$)'.format(component), account_name))

def is_valid(string):
    """Return true if the given string is a valid account name.
    This does not check for the root account types, just the general syntax.

    Args:
      string: A string, to be checked for account name pattern.
    Returns:
      A boolean, true if the string has the form of an account's name.
    """
    return (isinstance(string, str) and
            bool(re.match('{}$'.format(ACCOUNT_RE), string)))

def join(*components):
    """Join the names with the account separator.

    Args:
      *components: Strings, the components of an account name.
    Returns:
      A string, joined in a single account name.
    """
    return sep.join(components)

def leaf(account_name):
    """Get the name of the leaf of this account.

    Args:
      account_name: A string, the name of the account whose leaf name to return.
    Returns:
      A string, the name of the leaf of the account.
    """
    assert isinstance(account_name, str)
    return account_name.split(sep)[-1] if account_name else None

def parent(account_name):
    """Return the name of the parent account of the given account.

    Args:
      account_name: A string, the name of the account whose parent to return.
    Returns:
      A string, the name of the parent account of this account.
    """
    assert isinstance(account_name, str), account_name
    if not account_name:
        return None
    components = account_name.split(sep)
    components.pop(-1)
    return sep.join(components)

def parent_matcher(account_name):
    """Build a predicate that returns whether an account is under the given one.

    Args:
      account_name: The name of the parent account we want to check for.
    Returns:
      A callable, which, when called, will return true if the given account is a
      child of ``account_name``.
    """
    return re.compile(r'{}($|{})'.format(re.escape(account_name), sep)).match

def parents(account_name):
    """A generator of the names of the parents of this account, including this account.

    Args:
      account_name: The name of the account we want to start iterating from.
    Returns:
      A generator of account name strings.
    """
    while account_name:
        yield account_name
        account_name = parent(account_name)

def root(num_components, account_name):
    """Return the first few components of an account's name.

    Args:
      num_components: An integer, the number of components to return.
      account_name: A string, an account name.
    Returns:
      A string, the account root up to 'num_components' components.
    """
    return join(*(split(account_name)[:num_components]))

def sans_root(account_name):
    """Get the name of the account without the root.

    For example, an input of 'Assets:BofA:Checking' will produce 'BofA:Checking'.

    Args:
      account_name: A string, the name of the account whose leaf name to return.
    Returns:
      A string, the name of the non-root portion of this account name.
    """
    assert isinstance(account_name, str)
    components = account_name.split(sep)[1:]
    return join(*components) if account_name else None

def split(account_name):
    """Split an account's name into its components.

    Args:
      account_name: A string, an account name.
    Returns:
      A list of strings, the components of the account name (without the separators).
    """
    return account_name.split(sep)

def walk(root_directory):
    """A version of os.walk() which yields directories that are valid account names.

    This only yields directories that are accounts... it skips the other ones.
    For convenience, it also yields you the account's name.

    Args:
      root_directory: A string, the name of the root of the hierarchy to be walked.
    Yields:
      Tuples of (root, account-name, dirs, files), similar to os.walk().
    """
    for root, dirs, files in os.walk(root_directory):
        dirs.sort()
        files.sort()
        relroot = root[len(root_directory)+1:]
        account_name = relroot.replace(os.sep, sep)
        if is_valid(account_name):
            yield (root, account_name, dirs, files)

def get_account_sign(account_name, account_types=None):
    """Return the sign of the normal balance of a particular account.

    Args:
      account_name: A string, the name of the account whose sign is to return.
      account_types: An optional instance of the current account_types.
    Returns:
      +1 or -1, depending on the account's type.
    """
    if account_types is None:
        account_types = DEFAULT_ACCOUNT_TYPES
    assert isinstance(account_name, str), "Account is not a string: {}".format(account_name)
    account_type = get_account_type(account_name)
    return (+1
            if account_type in (account_types.assets,
                                account_types.expenses)
            else -1)

def get_account_sort_key(account_types, account_name):
    """Return a tuple that can be used to order/sort account names.

    Args:
      account_types: An instance of AccountTypes, a tuple of account type names.
    Returns:
      A function object to use as the optional 'key' argument to the sort
      function. It accepts a single argument, the account name to sort and
      produces a sortable key.
    """
    return (account_types.index(get_account_type(account_name)), account_name)

def get_account_type(account_name):
    """Return the type of this account's name.

    Warning: No check is made on the validity of the account type. This merely
    returns the root account of the corresponding account name.

    Args:
      account_name: A string, the name of the account whose type is to return.
    Returns:
      A string, the type of the account in 'account_name'.

    """
    assert isinstance(account_name, str), "Account is not a string: {}".format(account_name)
    return account.split(account_name)[0]

def is_account_type(account_type, account_name):
    """Return the type of this account's name.

    Warning: No check is made on the validity of the account type. This merely
    returns the root account of the corresponding account name.

    Args:
      account_type: A string, the prefix type of the account.
      account_name: A string, the name of the account whose type is to return.
    Returns:
      A boolean, true if the account is of the given type.
    """
    return bool(re.match('^{}{}'.format(account_type, account.sep), account_name))

def is_balance_sheet_account(account_name, account_types):
    """Return true if the given account is a balance sheet account.
    Assets, liabilities and equity accounts are balance sheet accounts.

    Args:
      account_name: A string, an account name.
      account_types: An instance of AccountTypes.
    Returns:
      A boolean, true if the account is a balance sheet account.
    """
    assert isinstance(account_name, str), "Account is not a string: {}".format(account_name)
    assert isinstance(account_types, AccountTypes), (
        "Account types has invalid type: {}".format(account_types))
    account_type = get_account_type(account_name)
    return account_type in (account_types.assets,
                            account_types.liabilities,
                            account_types.equity)

def is_equity_account(account_name, account_types):
    """Return true if the given account is an equity account.

    Args:
      account_name: A string, an account name.
      account_types: An instance of AccountTypes.
    Returns:
      A boolean, true if the account is an equity account.
    """
    assert isinstance(account_name, str), "Account is not a string: {}".format(account_name)
    assert isinstance(account_types, AccountTypes), (
        "Account types has invalid type: {}".format(account_types))
    account_type = get_account_type(account_name)
    return account_type == account_types.equity

def is_income_statement_account(account_name, account_types):
    """Return true if the given account is an income statement account.
    Income and expense accounts are income statement accounts.

    Args:
      account_name: A string, an account name.
      account_types: An instance of AccountTypes.
    Returns:
      A boolean, true if the account is an income statement account.
    """
    assert isinstance(account_name, str), "Account is not a string: {}".format(account_name)
    assert isinstance(account_types, AccountTypes), (
        "Account types has invalid type: {}".format(account_types))
    account_type = get_account_type(account_name)
    return account_type in (account_types.income,
                            account_types.expenses)

def is_root_account(account_name, account_types=None):
    """Return true if the account name is a root account.
    This function does not verify whether the account root is a valid
    one, just that it is a root account or not.

    Args:
      account_name: A string, the name of the account to check for.
      account_types: An optional instance of the current account_types;
        if provided, we check against these values. If not provided, we
        merely check that name pattern is that of an account component with
        no separator.
    Returns:
      A boolean, true if the account is root account.
    """
    assert isinstance(account_name, str), "Account is not a string: {}".format(account_name)
    if account_types is not None:
        assert isinstance(account_types, AccountTypes), (
            "Account types has invalid type: {}".format(account_types))
        return account_name in account_types
    else:
        return (account_name and
                bool(re.match(r'([A-Z][A-Za-z0-9\-]+)$', account_name)))

@staticmethod
def from_string(string):
    """Create an amount from a string.

    This is a miniature parser used for building tests.

    Args:
      string: A string of <number> <currency>.
    Returns:
      A new instance of Amount.
    """
    match = re.match(r'\s*([-+]?[0-9.]+)\s+({currency})'.format(currency=CURRENCY_RE),
                     string)
    if not match:
        raise ValueError("Invalid string for amount: '{}'".format(string))
    number, currency = match.group(1, 2)
    return Amount(D(number), currency)

def abs(amount):
    """Return the absolute value of the given amount.

    Args:
      amount: An instance of Amount.
    Returns:
      An instance of Amount.
    """
    return (amount
            if amount.number >= ZERO
            else Amount(-amount.number, amount.currency))

def add(amount1, amount2):
    """Add the given amounts with the same currency.

    Args:
      amount1: An instance of Amount.
      amount2: An instance of Amount.
    Returns:
      An instance of Amount, with the sum the two amount's numbers, in the same
      currency.
    """
    assert isinstance(amount1.number, Decimal), (
        "Amount1's number is not a Decimal instance: {}".format(amount1.number))
    assert isinstance(amount2.number, Decimal), (
        "Amount2's number is not a Decimal instance: {}".format(amount2.number))
    if amount1.currency != amount2.currency:
        raise ValueError(
            "Unmatching currencies for operation on {} and {}".format(
                amount1, amount2))
    return Amount(amount1.number + amount2.number, amount1.currency)

def div(amount, number):
    """Divide the given amount by a number.

    Args:
      amount: An instance of Amount.
      number: A decimal number.
    Returns:
      An Amount, with the same currency, but with amount units divided by 'number'.
    """
    assert isinstance(amount.number, Decimal), (
        "Amount's number is not a Decimal instance: {}".format(amount.number))
    assert isinstance(number, Decimal), (
        "Number is not a Decimal instance: {}".format(number))
    return Amount(amount.number / number, amount.currency)

@staticmethod
def from_string(string):
    """Create an amount from a string.

    This is a miniature parser used for building tests.

    Args:
      string: A string of <number> <currency>.
    Returns:
      A new instance of Amount.
    """
    match = re.match(r'\s*([-+]?[0-9.]+)\s+({currency})'.format(currency=CURRENCY_RE),
                     string)
    if not match:
        raise ValueError("Invalid string for amount: '{}'".format(string))
    number, currency = match.group(1, 2)
    return Amount(D(number), currency)

def mul(amount, number):
    """Multiply the given amount by a number.

    Args:
      amount: An instance of Amount.
      number: A decimal number.
    Returns:
      An Amount, with the same currency, but with 'number' times units.
    """
    assert isinstance(amount.number, Decimal), (
        "Amount's number is not a Decimal instance: {}".format(amount.number))
    assert isinstance(number, Decimal), (
        "Number is not a Decimal instance: {}".format(number))
    return Amount(amount.number * number, amount.currency)

def sortkey(amount):
    """A comparison function that sorts by currency first.

    Args:
      amount: An instance of Amount.
    Returns:
      A sort key, composed of the currency first and then the number.
    """
    return (amount.currency, amount.number)

def sub(amount1, amount2):
    """Subtract the given amounts with the same currency.

    Args:
      amount1: An instance of Amount.
      amount2: An instance of Amount.
    Returns:
      An instance of Amount, with the difference between the two amount's
      numbers, in the same currency.
    """
    assert isinstance(amount1.number, Decimal), (
        "Amount1's number is not a Decimal instance: {}".format(amount1.number))
    assert isinstance(amount2.number, Decimal), (
        "Amount2's number is not a Decimal instance: {}".format(amount2.number))
    if amount1.currency != amount2.currency:
        raise ValueError(
            "Unmatching currencies for operation on {} and {}".format(
                amount1, amount2))
    return Amount(amount1.number - amount2.number, amount1.currency)

def compare_entries(entries1, entries2):
    """Compare two lists of entries. This is used for testing.

    The entries are compared with disregard for their file location.

    Args:
      entries1: A list of directives of any type.
      entries2: Another list of directives of any type.
    Returns:
      A tuple of (success, not_found1, not_found2), where the fields are:
        success: A boolean, true if all the values are equal.
        missing1: A list of directives from 'entries1' not found in
          'entries2'.
        missing2: A list of directives from 'entries2' not found in
          'entries1'.
    Raises:
      ValueError: If a duplicate entry is found.
    """
    hashes1, errors1 = hash_entries(entries1, exclude_meta=True)
    hashes2, errors2 = hash_entries(entries2, exclude_meta=True)
    keys1 = set(hashes1.keys())
    keys2 = set(hashes2.keys())

    if errors1 or errors2:
        error = (errors1 + errors2)[0]
        raise ValueError(str(error))

    same = keys1 == keys2
    missing1 = data.sorted([hashes1[key] for key in keys1 - keys2])
    missing2 = data.sorted([hashes2[key] for key in keys2 - keys1])
    return (same, missing1, missing2)

def excludes_entries(subset_entries, entries):
    """Check that a list of entries does not appear in another list.

    Args:
      subset_entries: The set of entries to look for in 'entries'.
      entries: The larger list of entries that should not include 'subset_entries'.
    Returns:
      A boolean and a list of entries that are not supposed to appear.
    Raises:
      ValueError: If a duplicate entry is found.
    """
    subset_hashes, subset_errors = hash_entries(subset_entries, exclude_meta=True)
    subset_keys = set(subset_hashes.keys())
    hashes, errors = hash_entries(entries, exclude_meta=True)
    keys = set(hashes.keys())

    if subset_errors or errors:
        error = (subset_errors + errors)[0]
        raise ValueError(str(error))

    intersection = keys.intersection(subset_keys)
    excludes = not bool(intersection)
    extra = data.sorted([subset_hashes[key] for key in intersection])
    return (excludes, extra)

def hash_entries(entries, exclude_meta=False):
    """Compute unique hashes of each of the entries and return a map of them.

    This is used for comparisons between sets of entries.

    Args:
      entries: A list of directives.
      exclude_meta: If set, exclude the metadata from the hash. Use this for
        unit tests comparing entries coming from different sources as the
        filename and lineno will be distinct. However, when you're using the
        hashes to uniquely identify transactions, you want to include the
        filenames and line numbers (the default).
    Returns:
      A dict of hash-value to entry (for all entries) and a list of errors.
      Errors are created when duplicate entries are found.
    """
    entry_hash_dict = {}
    errors = []
    num_legal_duplicates = 0
    for entry in entries:
        hash_ = hash_entry(entry, exclude_meta)

        if hash_ in entry_hash_dict:
            if isinstance(entry, Price):
                # Note: Allow duplicate Price entries, they should be common
                # because of the nature of stock markets (if they're closed, the
                # data source is likely to return an entry for the previously
                # available date, which may already have been fetched).
                num_legal_duplicates += 1
            else:
                other_entry = entry_hash_dict[hash_]
                errors.append(
                    CompareError(entry.meta,
                                 "Duplicate entry: {} == {}".format(entry, other_entry),
                                 entry))
        entry_hash_dict[hash_] = entry

    if not errors:
        assert len(entry_hash_dict) + num_legal_duplicates == len(entries), (
            len(entry_hash_dict), len(entries), num_legal_duplicates)
    return entry_hash_dict, errors

def hash_entry(entry, exclude_meta=False):
    """Compute the stable hash of a single entry.

    Args:
      entry: A directive instance.
      exclude_meta: If set, exclude the metadata from the hash. Use this for
        unit tests comparing entries coming from different sources as the
        filename and lineno will be distinct. However, when you're using the
        hashes to uniquely identify transactions, you want to include the
        filenames and line numbers (the default).
    Returns:
      A stable hexadecimal hash of this entry.

    """
    return stable_hash_namedtuple(entry,
                                  IGNORED_FIELD_NAMES if exclude_meta else frozenset())

def includes_entries(subset_entries, entries):
    """Check if a list of entries is included in another list.

    Args:
      subset_entries: The set of entries to look for in 'entries'.
      entries: The larger list of entries that could include 'subset_entries'.
    Returns:
      A boolean and a list of missing entries.
    Raises:
      ValueError: If a duplicate entry is found.
    """
    subset_hashes, subset_errors = hash_entries(subset_entries, exclude_meta=True)
    subset_keys = set(subset_hashes.keys())
    hashes, errors = hash_entries(entries, exclude_meta=True)
    keys = set(hashes.keys())

    if subset_errors or errors:
        error = (subset_errors + errors)[0]
        raise ValueError(str(error))

    includes = subset_keys.issubset(keys)
    missing = data.sorted([subset_hashes[key] for key in subset_keys - keys])
    return (includes, missing)

def stable_hash_namedtuple(objtuple, ignore=frozenset()):
    """Hash the given namedtuple and its child fields.

    This iterates over all the members of objtuple, skipping the attributes from
    the 'ignore' set, and computes a unique hash string code. If the elements
    are lists or sets, sorts them for stability.

    Args:
      objtuple: A tuple object or other.
      ignore: A set of strings, attribute names to be skipped in
        computing a stable hash. For instance, circular references to objects
        or irrelevant data.

    """
    # Note: this routine is slow and would stand to be implemented in C.
    hashobj = hashlib.md5()
    for attr_name, attr_value in zip(objtuple._fields, objtuple):
        if attr_name in ignore:
            continue
        if isinstance(attr_value, (list, set, frozenset)):
            subhashes = set()
            for element in attr_value:
                if isinstance(element, tuple):
                    subhashes.add(stable_hash_namedtuple(element, ignore))
                else:
                    md5 = hashlib.md5()
                    md5.update(str(element).encode())
                    subhashes.add(md5.hexdigest())
            for subhash in sorted(subhashes):
                hashobj.update(subhash.encode())
        else:
            hashobj.update(str(attr_value).encode())
    return hashobj.hexdigest()

def convert_amount(amt, target_currency, price_map, date=None, via=None):
    """Return the market value of an Amount in a particular currency.

    In addition, if a conversion rate isn't available, you can provide a list of
    currencies to attempt to synthesize a rate for via implied rates.

    Args:
      amt: An instance of Amount.
      target_currency: The target currency to convert to.
      price_map: A dict of prices, as built by prices.build_price_map().
      date: A datetime.date instance to evaluate the value at, or None.
      via: A list of currencies to attempt to synthesize an implied rate if the
        direct conversion fails.
    Returns:
      An Amount, either with a successful value currency conversion, or if we
      could not convert the value, the amount itself, unmodified.

    """
    # First, attempt to convert directly. This should be the most
    # straightforward conversion.
    base_quote = (amt.currency, target_currency)
    _, rate = prices.get_price(price_map, base_quote, date)
    if rate is not None:
        # On success, just make the conversion directly.
        return Amount(amt.number * rate, target_currency)
    elif via:
        assert isinstance(via, (tuple, list))

        # A price is unavailable, attempt to convert via cost/price currency
        # hop, if the value currency isn't the target currency.
        for implied_currency in via:
            if implied_currency == target_currency:
                continue
            base_quote1 = (amt.currency, implied_currency)
            _, rate1 = prices.get_price(price_map, base_quote1, date)
            if rate1 is not None:
                base_quote2 = (implied_currency, target_currency)
                _, rate2 = prices.get_price(price_map, base_quote2, date)
                if rate2 is not None:
                    return Amount(amt.number * rate1 * rate2, target_currency)

    # We failed to infer a conversion rate; return the amt.
    return amt

def convert_position(pos, target_currency, price_map, date=None):
    """Return the market value of a Position or Posting in a particular currency.

    In addition, if the rate from the position's currency to target_currency
    isn't available, an attempt is made to convert from its cost currency, if
    one is available.

    Args:
      pos: An instance of Position or Posting, equivalently.
      target_currency: The target currency to convert to.
      price_map: A dict of prices, as built by prices.build_price_map().
      date: A datetime.date instance to evaluate the value at, or None.
    Returns:
      An Amount, either with a successful value currency conversion, or if we
      could not convert the value, just the units, unmodified. (See get_value()
      above for details.)
    """
    cost = pos.cost
    value_currency = (
        (isinstance(cost, Cost) and cost.currency) or
        (hasattr(pos, 'price') and pos.price and pos.price.currency) or
        None)
    return convert_amount(pos.units, target_currency, price_map,
                          date=date, via=(value_currency,))

def get_cost(pos):
    """Return the total cost of a Position or Posting.

    Args:
      pos: An instance of Position or Posting, equivalently.
    Returns:
      An Amount.
    """
    assert isinstance(pos, Position) or type(pos).__name__ == 'Posting'
    cost = pos.cost
    return (Amount(cost.number * pos.units.number, cost.currency)
            if (isinstance(cost, Cost) and isinstance(cost.number, Decimal))
            else pos.units)

def get_units(pos):
    """Return the units of a Position or Posting.

    Args:
      pos: An instance of Position or Posting, equivalently.
    Returns:
      An Amount.
    """
    assert isinstance(pos, Position) or type(pos).__name__ == 'Posting'
    return pos.units

def get_value(pos, price_map, date=None):
    """Return the market value of a Position or Posting.

    Note that if the position is not held at cost, this does not convert
    anything, even if a price is available in the 'price_map'. We don't specify
    a target currency here. If you're attempting to make such a conversion, see
    ``convert_*()`` functions below.

    Args:
      pos: An instance of Position or Posting, equivalently.
      price_map: A dict of prices, as built by prices.build_price_map().
      date: A datetime.date instance to evaluate the value at, or None.
    Returns:
      An Amount, either with a successful value currency conversion, or if we
      could not convert the value, just the units, unmodified. This is designed
      so that you could reduce an inventory with this and not lose any
      information silently in case of failure to convert (possibly due to an
      empty price map). Compare the returned currency to that of the input
      position if you need to check for success.
    """
    assert isinstance(pos, Position) or type(pos).__name__ == 'Posting'
    units = pos.units
    cost = pos.cost

    # Try to infer what the cost/price currency should be.
    value_currency = (
        (isinstance(cost, Cost) and cost.currency) or
        (hasattr(pos, 'price') and pos.price and pos.price.currency) or
        None)

    if isinstance(value_currency, str):
        # We have a value currency; hit the price database.
        base_quote = (units.currency, value_currency)
        _, price_number = prices.get_price(price_map, base_quote, date)
        if price_number is not None:
            return Amount(units.number * price_number, value_currency)

    # We failed to infer a conversion rate; return the units.
    return units

def get_weight(pos):
    """Return the weight of a Position or Posting.

    This is the amount that will need to be balanced from a posting of a
    transaction.

    This is a *key* element of the semantics of transactions in this software. A
    balance amount is the amount used to check the balance of a transaction.
    Here are all relevant examples, with the amounts used to balance the
    postings:

        Assets:Account  5234.50 USD                             ->  5234.50 USD
        Assets:Account  3877.41 EUR @ 1.35 USD                  ->  5234.50 USD
        Assets:Account       10 HOOL {523.45 USD}               ->  5234.50 USD
        Assets:Account       10 HOOL {523.45 USD} @ 545.60 CAD  ->  5234.50 USD

    Args:
      pos: An instance of Position or Posting, equivalently.
    Returns:
      An Amount.
    """
    assert isinstance(pos, Position) or type(pos).__name__ == 'Posting'
    units = pos.units
    cost = pos.cost

    # It the object has a cost, use that as the weight, to balance.
    if isinstance(cost, Cost) and isinstance(cost.number, Decimal):
        weight = Amount(cost.number * pos.units.number, cost.currency)
    else:
        # Otherwise use the postings.
        weight = units

        # Unless there is a price available; use that if present.
        if not isinstance(pos, Position):
            price = pos.price
            if price is not None:
                # Note: Here we could assert that price.currency == units.currency.
                if price.number is MISSING or units.number is MISSING:
                    converted_number = MISSING
                else:
                    converted_number = price.number * units.number
                weight = Amount(converted_number, price.currency)

    return weight

def create_simple_posting(entry, account, number, currency):
    """Create a simple posting on the entry, with just a number and currency (no cost).

    Args:
      entry: The entry instance to add the posting to.
      account: A string, the account to use on the posting.
      number: A Decimal number or string to use in the posting's Amount.
      currency: A string, the currency for the Amount.
    Returns:
      An instance of Posting, and as a side-effect the entry has had its list of
      postings modified with the new Posting instance.
    """
    if isinstance(account, str):
        pass
    if number is None:
        units = None
    else:
        if not isinstance(number, Decimal):
            number = D(number)
        units = Amount(number, currency)
    posting = Posting(account, units, None, None, None, None)
    if entry is not None:
        entry.postings.append(posting)
    return posting

def create_simple_posting_with_cost(entry, account,
                                    number, currency,
                                    cost_number, cost_currency):
    """Create a simple posting on the entry, with just a number and currency (no cost).

    Args:
      entry: The entry instance to add the posting to.
      account: A string, the account to use on the posting.
      number: A Decimal number or string to use in the posting's Amount.
      currency: A string, the currency for the Amount.
      cost_number: A Decimal number or string to use for the posting's cost Amount.
      cost_currency: a string, the currency for the cost Amount.
    Returns:
      An instance of Posting, and as a side-effect the entry has had its list of
      postings modified with the new Posting instance.
    """
    if isinstance(account, str):
        pass
    if not isinstance(number, Decimal):
        number = D(number)
    if cost_number and not isinstance(cost_number, Decimal):
        cost_number = D(cost_number)
    units = Amount(number, currency)
    cost = Cost(cost_number, cost_currency, None, None)
    posting = Posting(account, units, cost, None, None, None)
    if entry is not None:
        entry.postings.append(posting)
    return posting

def entry_sortkey(entry):
    """Sort-key for entries. We sort by date, except that checks
    should be placed in front of every list of entries of that same day,
    in order to balance linearly.

    Args:
      entry: An entry instance.
    Returns:
      A tuple of (date, integer, integer), that forms the sort key for the
      entry.
    """
    return (entry.date, SORT_ORDER.get(type(entry), 0), entry.meta["lineno"])

def filter_txns(entries):
    """A generator that yields only the Transaction instances.

    This is such an incredibly common operation that it deserves a terse
    filtering mechanism.

    Args:
      entries: A list of directives.
    Yields:
      A sorted list of only the Transaction directives.
    """
    for entry in entries:
        if isinstance(entry, Transaction):
            yield entry

def find_closest(entries, filename, lineno):
    """Find the closest entry from entries to (filename, lineno).

    Args:
      entries: A list of directives.
      filename: A string, the name of the ledger file to look for. Be careful
        to provide the very same filename, and note that the parser stores the
        absolute path of the filename here.
      lineno: An integer, the line number closest after the directive we're
        looking for. This may be the exact/first line of the directive.
    Returns:
      The closest entry found in the given file for the given filename, or
      None, if none could be found.
    """
    min_diffline = sys.maxsize
    closest_entry = None
    for entry in entries:
        emeta = entry.meta
        if emeta["filename"] == filename and emeta["lineno"] > 0:
            diffline = lineno - emeta["lineno"]
            if 0 <= diffline < min_diffline:
                min_diffline = diffline
                closest_entry = entry
    return closest_entry

def get_entry(posting_or_entry):
    """Return the entry associated with the posting or entry.

    Args:
      entry: A TxnPosting or entry instance
    Returns:
      A datetime instance.
    """
    return (posting_or_entry.txn
            if isinstance(posting_or_entry, TxnPosting)
            else posting_or_entry)

def has_entry_account_component(entry, component):
    """Return true if one of the entry's postings has an account component.

    Args:
      entry: A Transaction entry.
      component: A string, a component of an account name. For instance,
        ``Food`` in ``Expenses:Food:Restaurant``. All components are considered.
    Returns:
      Boolean: true if the component is in the account. Note that a component
      name must be whole, that is ``NY`` is not in ``Expenses:Taxes:StateNY``.
    """
    return (isinstance(entry, Transaction) and
            any(has_component(posting.account, component)
                for posting in entry.postings))

def iter_entry_dates(entries, date_begin, date_end):
    """Iterate over the entries in a date window.

    Args:
      entries: A date-sorted list of dated directives.
      date_begin: A datetime.date instance, the first date to include.
      date_end: A datetime.date instance, one day beyond the last date.
    Yields:
      Instances of the dated directives, between the dates, and in the order in
      which they appear.
    """
    getdate = lambda entry: entry.date
    index_begin = bisect_left_with_key(entries, date_begin, key=getdate)
    index_end = bisect_left_with_key(entries, date_end, key=getdate)
    for index in range(index_begin, index_end):
        yield entries[index]

def new_directive(clsname, fields: List[Tuple]) -> NamedTuple:
    """Create a directive class. Do not include default fields.
    This should probably be carried out through inheritance.

    Args:
      name: A string, the capitalized name of the directive.
      fields: A string or the list of strings, names for the fields
        to add to the base tuple.
    Returns:
      A type object for the new directive type.
    """
    return NamedTuple(
        clsname,
        [('meta', Meta), ('date', datetime.date)] + fields)

def new_metadata(filename, lineno, kvlist=None):
    """Create a new metadata container from the filename and line number.

    Args:
      filename: A string, the filename for the creator of this directive.
      lineno: An integer, the line number where the directive has been created.
      kvlist: An optional container of key-values.
    Returns:
      A metadata dict.
    """
    meta = {'filename': filename,
            'lineno': lineno}
    if kvlist:
        meta.update(kvlist)
    return meta

def posting_has_conversion(posting):
    """Return true if this position involves a conversion.

    A conversion is when there is a price attached to the amount but no cost.
    This is used on transactions to convert between units.

    Args:
      posting: an instance of Posting
    Return:
      A boolean, true if this posting has a price conversion.
    """
    return (posting.cost is None and
            posting.price is not None)

def posting_sortkey(entry):
    """Sort-key for entries or postings. We sort by date, except that checks
    should be placed in front of every list of entries of that same day,
    in order to balance linearly.

    Args:
      entry: A Posting or entry instance
    Returns:
      A tuple of (date, integer, integer), that forms the sort key for the
      posting or entry.
    """
    if isinstance(entry, TxnPosting):
        entry = entry.txn
    return (entry.date, SORT_ORDER.get(type(entry), 0), entry.meta["lineno"])

def remove_account_postings(account, entries):
    """Remove all postings with the given account.

    Args:
      account: A string, the account name whose postings we want to remove.
    Returns:
      A list of entries without the rounding postings.
    """
    new_entries = []
    for entry in entries:
        if isinstance(entry, Transaction) and (
                any(posting.account == account for posting in entry.postings)):
            entry = entry._replace(postings=[posting
                                             for posting in entry.postings
                                             if posting.account != account])
        new_entries.append(entry)
    return new_entries

def sanity_check_types(entry, allow_none_for_tags_and_links=False):
    """Check that the entry and its postings has all correct data types.

    Args:
      entry: An instance of one of the entries to be checked.
      allow_none_for_tags_and_links: A boolean, whether to allow plugins to
        generate Transaction objects with None as value for the 'tags' or 'links'
        attributes.
    Raises:
      AssertionError: If there is anything that is unexpected, raises an exception.
    """
    assert isinstance(entry, ALL_DIRECTIVES), "Invalid directive type"
    assert isinstance(entry.meta, dict), "Invalid type for meta"
    assert 'filename' in entry.meta, "Missing filename in metadata"
    assert 'lineno' in entry.meta, "Missing line number in metadata"
    assert isinstance(entry.date, datetime.date), "Invalid date type"
    if isinstance(entry, Transaction):
        assert isinstance(entry.flag, (NoneType, str)), "Invalid flag type"
        assert isinstance(entry.payee, (NoneType, str)), "Invalid payee type"
        assert isinstance(entry.narration, (NoneType, str)), "Invalid narration type"
        set_types = ((NoneType, set, frozenset)
                     if allow_none_for_tags_and_links
                     else (set, frozenset))
        assert isinstance(entry.tags, set_types), (
            "Invalid tags type: {}".format(type(entry.tags)))
        assert isinstance(entry.links, set_types), (
            "Invalid links type: {}".format(type(entry.links)))
        assert isinstance(entry.postings, list), "Invalid postings list type"
        for posting in entry.postings:
            assert isinstance(posting, Posting), "Invalid posting type"
            assert isinstance(posting.account, str), "Invalid account type"
            assert isinstance(posting.units, (Amount, NoneType)), "Invalid units type"
            assert isinstance(posting.cost, (Cost, CostSpec, NoneType)), "Invalid cost type"
            assert isinstance(posting.price, (Amount, NoneType)), "Invalid price type"
            assert isinstance(posting.flag, (str, NoneType)), "Invalid flag type"

def sorted(entries):
    """A convenience to sort a list of entries, using entry_sortkey().

    Args:
      entries: A list of directives.
    Returns:
      A sorted list of directives.
    """
    return builtins.sorted(entries, key=entry_sortkey)

def transaction_has_conversion(transaction):
    """Given a Transaction entry, return true if at least one of
    the postings has a price conversion (without an associated
    cost). These are the source of non-zero conversion balances.

    Args:
      transaction: an instance of a Transaction entry.
    Returns:
      A boolean, true if this transaction contains at least one posting with a
      price conversion.
    """
    assert isinstance(transaction, Transaction), (
        "Invalid type of entry for transaction: {}".format(transaction))
    for posting in transaction.postings:
        if posting_has_conversion(posting):
            return True
    return False

def get_account_components(entries):
    """Gather all the account components available in the given directives.

    Args:
      entries: A list of directive instances.
    Returns:
      A list of strings, the unique account components, including the root
      account names.
    """
    accounts = get_accounts(entries)
    components = set()
    for account_name in accounts:
        components.update(account.split(account_name))
    return sorted(components)

def get_account_open_close(entries):
    """Fetch the open/close entries for each of the accounts.

    If an open or close entry happens to be duplicated, accept the earliest
    entry (chronologically).

    Args:
      entries: A list of directive instances.
    Returns:
      A map of account name strings to pairs of (open-directive, close-directive)
      tuples.
    """
    # A dict of account name to (open-entry, close-entry).
    open_close_map = defaultdict(lambda: [None, None])
    for entry in entries:
        if not isinstance(entry, (Open, Close)):
            continue
        open_close = open_close_map[entry.account]
        index = 0 if isinstance(entry, Open) else 1
        previous_entry = open_close[index]
        if previous_entry is not None:
            if previous_entry.date <= entry.date:
                entry = previous_entry
        open_close[index] = entry

    return dict(open_close_map)

def get_accounts(entries):
    """Gather all the accounts references by a list of directives.

    Args:
      entries: A list of directive instances.
    Returns:
      A set of account strings.
    """
    _, accounts_last = _GetAccounts.get_accounts_use_map(entries)
    return accounts_last.keys()

def get_accounts_use_map(entries):
    """Gather all the accounts references by a list of directives.

    Args:
      entries: A list of directive instances.
    Returns:
      A pair of dictionaries of account name to date, one for first date
      used and one for last date used. The keys should be identical.
    """
    return _GetAccounts.get_accounts_use_map(entries)

def get_active_years(entries):
    """Yield all the years that have at least one entry in them.

    Args:
      entries: A list of directive instances.
    Yields:
      Unique dates see in the list of directives.
    """
    seen = set()
    prev_year = None
    for entry in entries:
        year = entry.date.year
        if year != prev_year:
            prev_year = year
            assert year not in seen
            seen.add(year)
            yield year

def get_all_links(entries):
    """Return a list of all the links seen in the given entries.

    Args:
      entries: A list of directive instances.
    Returns:
      A set of links strings.
    """
    all_links = set()
    for entry in entries:
        if not isinstance(entry, Transaction):
            continue
        if entry.links:
            all_links.update(entry.links)
    return sorted(all_links)

def get_all_payees(entries):
    """Return a list of all the unique payees seen in the given entries.

    Args:
      entries: A list of directive instances.
    Returns:
      A set of payee strings.
    """
    all_payees = set()
    for entry in entries:
        if not isinstance(entry, Transaction):
            continue
        all_payees.add(entry.payee)
    all_payees.discard(None)
    return sorted(all_payees)

def get_all_tags(entries):
    """Return a list of all the tags seen in the given entries.

    Args:
      entries: A list of directive instances.
    Returns:
      A set of tag strings.
    """
    all_tags = set()
    for entry in entries:
        if not isinstance(entry, Transaction):
            continue
        if entry.tags:
            all_tags.update(entry.tags)
    return sorted(all_tags)

def get_commodity_map(entries, create_missing=True):
    """Create map of commodity names to Commodity entries.

    Args:
      entries: A list of directive instances.
      create_missing: A boolean, true if you want to automatically generate
        missing commodity directives if not present in the output map.
    Returns:
      A map of commodity name strings to Commodity directives.
    """
    if not entries:
        return {}

    commodities_map = {}
    for entry in entries:
        if isinstance(entry, Commodity):
            commodities_map[entry.currency] = entry

        elif isinstance(entry, Transaction):
            for posting in entry.postings:

                # Main currency.
                units = posting.units
                commodities_map.setdefault(units.currency, None)

                # Currency in cost.
                cost = posting.cost
                if cost:
                    commodities_map.setdefault(cost.currency, None)

                # Currency in price.
                price = posting.price
                if price:
                    commodities_map.setdefault(price.currency, None)

        elif isinstance(entry, Balance):
            commodities_map.setdefault(entry.amount.currency, None)

        elif isinstance(entry, Price):
            commodities_map.setdefault(entry.currency, None)

    if create_missing:
        # Create missing Commodity directives when they haven't been specified explicitly.
        # (I think it might be better to always do this from the loader.)
        date = entries[0].date
        meta = data.new_metadata('<getters>', 0)
        commodities_map = {
            commodity: (entry
                        if entry is not None
                        else Commodity(meta, date, commodity))
            for commodity, entry in commodities_map.items()}

    return commodities_map

def get_dict_accounts(account_names):
    """Return a nested dict of all the unique leaf names.
    account names are labelled with LABEL=True

    Args:
      account_names: An iterable of account names (strings)
    Returns:
      A nested OrderedDict of account leafs
    """
    leveldict = OrderedDict()
    for account_name in account_names:
        nested_dict = leveldict
        for component in account.split(account_name):
            nested_dict = nested_dict.setdefault(component, OrderedDict())
        nested_dict[get_dict_accounts.ACCOUNT_LABEL] = True
    return leveldict

def get_entry_accounts(entry):
    """Gather all the accounts references by a single directive.

    Note: This should get replaced by a method on each directive eventually,
    that would be the clean way to do this.

    Args:
      entries: A directive instance.
    Returns:
      A set of account strings.
    """
    return _GetAccounts.get_entry_accounts(entry)

def get_leveln_parent_accounts(account_names, level, nrepeats=0):
    """Return a list of all the unique leaf names at level N in an account hierarchy.

    Args:
      account_names: A list of account names (strings)
      level: The level to cross-cut. 0 is for root accounts.
      nrepeats: A minimum number of times a leaf is required to be present in the
        the list of unique account names in order to be returned by this function.
    Returns:
      A list of leaf node names.
    """
    leveldict = defaultdict(int)
    for account_name in set(account_names):
        components = account.split(account_name)
        if level < len(components):
            leveldict[components[level]] += 1
    levels = {level_
              for level_, count in leveldict.items()
              if count > nrepeats}
    return sorted(levels)

def get_min_max_dates(entries, types=None):
    """Return the minimum and maximum dates in the list of entries.

    Args:
      entries: A list of directive instances.
      types: An optional tuple of types to restrict the entries to.
    Returns:
      A pair of datetime.date dates, the minimum and maximum dates seen in the
      directives.
    """
    date_first = date_last = None

    for entry in entries:
        if types and not isinstance(entry, types):
            continue
        date_first = entry.date
        break

    for entry in reversed(entries):
        if types and not isinstance(entry, types):
            continue
        date_last = entry.date
        break

    return (date_first, date_last)

def get_values_meta(name_to_entries_map, *meta_keys, default=None):
    """Get a map of the metadata from a map of entries values.

    Given a dict of some key to a directive instance (or None), return a mapping
    of the key to the metadata extracted from each directive, or a default
    value. This can be used to gather a particular piece of metadata from an
    accounts map or a commodities map.

    Args:
      name_to_entries_map: A dict of something to an entry or None.
      meta_keys: A list of strings, the keys to fetch from the metadata.
      default: The default value to use if the metadata is not available or if
        the value/entry is None.
    Returns:
      A mapping of the keys of name_to_entries_map to the values of the 'meta_keys'
      metadata. If there are multiple 'meta_keys', each value is a tuple of them.
      On the other hand, if there is only a single one, the value itself is returned.
    """
    value_map = {}
    for key, entry in name_to_entries_map.items():
        value_list = []
        for meta_key in meta_keys:
            value_list.append(entry.meta.get(meta_key, default)
                              if entry is not None
                              else default)
        value_map[key] = (value_list[0]
                          if len(meta_keys) == 1
                          else tuple(value_list))
    return value_map

def compute_entries_balance(entries, prefix=None, date=None):
    """Compute the balance of all postings of a list of entries.

    Sum up all the positions in all the postings of all the transactions in the
    list of entries and return an inventory of it.

    Args:
      entries: A list of directives.
      prefix: If specified, a prefix string to restrict by account name. Only
        postings with an account that starts with this prefix will be summed up.
      date: A datetime.date instance at which to stop adding up the balance.
        The date is exclusive.
    Returns:
      An instance of Inventory.
    """
    total_balance = Inventory()
    for entry in entries:
        if not (date is None or entry.date < date):
            break
        if isinstance(entry, Transaction):
            for posting in entry.postings:
                if prefix is None or posting.account.startswith(prefix):
                    total_balance.add_position(posting)
    return total_balance

def compute_entry_context(entries, context_entry):
    """Compute the balances of all accounts referenced by entry up to entry.

    This provides the inventory of the accounts to which the entry is to be
    applied, before and after.

    Args:
      entries: A list of directives.
      context_entry: The entry for which we want to obtain the before and after
        context.
    Returns:
      Two dicts of account-name to Inventory instance, one which represents the
      context before the entry is applied, and one that represents the context
      after it has been applied.
    """
    assert context_entry is not None, "context_entry is missing."

    # Get the set of accounts for which to compute the context.
    context_accounts = getters.get_entry_accounts(context_entry)

    # Iterate over the entries until we find the target one and accumulate the
    # balance.
    context_before = collections.defaultdict(inventory.Inventory)
    for entry in entries:
        if entry is context_entry:
            break
        if isinstance(entry, Transaction):
            for posting in entry.postings:
                if not any(posting.account == account
                           for account in context_accounts):
                    continue
                balance = context_before[posting.account]
                balance.add_position(posting)

    # Compute the after context for the entry.
    context_after = copy.deepcopy(context_before)
    if isinstance(context_entry, Transaction):
        for posting in entry.postings:
            balance = context_after[posting.account]
            balance.add_position(posting)

    return context_before, context_after

def compute_residual(postings):
    """Compute the residual of a set of complete postings, and the per-currency precision.

    This is used to cross-check a balanced transaction.

    The precision is the maximum fraction that is being used for each currency
    (a dict). We use the currency of the weight amount in order to infer the
    quantization precision for each currency. Integer amounts aren't
    contributing to the determination of precision.

    Args:
      postings: A list of Posting instances.
    Returns:
      An instance of Inventory, with the residual of the given list of postings.
    """
    inventory = Inventory()
    for posting in postings:
        # Skip auto-postings inserted to absorb the residual (rounding error).
        if posting.meta and posting.meta.get(AUTOMATIC_RESIDUAL, False):
            continue
        # Add to total residual balance.
        inventory.add_amount(convert.get_weight(posting))
    return inventory

def fill_residual_posting(entry, account_rounding):
    """If necessary, insert a posting to absorb the residual.
    This makes the transaction balance exactly.

    Note: This was developed in order to tweak transactions before exporting
    them to Ledger. A better method would be to enable the feature that
    automatically inserts these rounding postings on all transactions, and so
    maybe this method can be deprecated if we do so.

    Args:
      entry: An instance of a Transaction.
      account_rounding: A string, the name of the rounding account that
        absorbs residuals / rounding errors.
    Returns:
      A possibly new, modified entry with a new posting. If a residual
      was not needed - the transaction already balanced perfectly - no new
      leg is inserted.

    """
    residual = compute_residual(entry.postings)
    if not residual.is_empty():
        new_postings = list(entry.postings)
        new_postings.extend(get_residual_postings(residual, account_rounding))
        entry = entry._replace(postings=new_postings)
    return entry

def get_residual_postings(residual, account_rounding):
    """Create postings to book the given residuals.

    Args:
      residual: An Inventory, the residual positions.
      account_rounding: A string, the name of the rounding account that
        absorbs residuals / rounding errors.
    Returns:
      A list of new postings to be inserted to reduce the given residual.
    """
    meta = {AUTOMATIC_META: True,
            AUTOMATIC_RESIDUAL: True}
    return [Posting(account_rounding, -position.units, position.cost, None, None,
                    meta.copy())
            for position in residual.get_positions()]

def has_nontrivial_balance(posting):
    """Return True if a Posting has a balance amount that would have to be calculated.

    Args:
      posting: A Posting instance.
    Returns:
      A boolean.
    """
    return posting.cost or posting.price

def infer_tolerances(postings, options_map, use_cost=None):
    """Infer tolerances from a list of postings.

    The tolerance is the maximum fraction that is being used for each currency
    (a dict). We use the currency of the weight amount in order to infer the
    quantization precision for each currency. Integer amounts aren't
    contributing to the determination of precision.

    The 'use_cost' option allows one to experiment with letting postings at cost
    and at price influence the maximum value of the tolerance. It's tricky to
    use and alters the definition of the tolerance in a non-trivial way, if you
    use it. The tolerance is expanded by the sum of the cost times a fraction 'M'
    of the smallest digits in the number of units for all postings held at cost.

    For example, in this transaction:

        2006-01-17 * "Plan Contribution"
          Assets:Investments:VWELX 18.572 VWELX {30.96 USD}
          Assets:Investments:VWELX 18.572 VWELX {30.96 USD}
          Assets:Investments:Cash -1150.00 USD

    The tolerance for units of USD will calculated as the MAXIMUM of:

      0.01 * M = 0.005 (from the 1150.00 USD leg)

      The sum of
        0.001 * M x 30.96 = 0.01548 +
        0.001 * M x 30.96 = 0.01548
                          = 0.03096

    So the tolerance for USD in this case is max(0.005, 0.03096) = 0.03096. Prices
    contribute similarly to the maximum tolerance allowed.

    Note that 'M' above is the inferred_tolerance_multiplier and its default
    value is 0.5.

    Args:
      postings: A list of Posting instances.
      options_map: A dict of options.
      use_cost: A boolean, true if we should be using a combination of the smallest
        digit of the number times the cost or price in order to infer the tolerance.
        If the value is left unspecified (as 'None'), the default value can be
        overridden by setting an option.
    Returns:
      A dict of currency to the tolerated difference amount to be used for it,
      e.g. 0.005.
    """
    if use_cost is None:
        use_cost = options_map["infer_tolerance_from_cost"]

    inferred_tolerance_multiplier = options_map["inferred_tolerance_multiplier"]

    default_tolerances = options_map["inferred_tolerance_default"]
    tolerances = default_tolerances.copy()

    cost_tolerances = collections.defaultdict(D)
    for posting in postings:
        # Skip the precision on automatically inferred postings.
        if posting.meta and AUTOMATIC_META in posting.meta:
            continue
        units = posting.units
        if not (isinstance(units, Amount) and isinstance(units.number, Decimal)):
            continue

        # Compute bounds on the number.
        currency = units.currency
        expo = units.number.as_tuple().exponent
        if expo < 0:
            # Note: the exponent is a negative value.
            tolerance = ONE.scaleb(expo) * inferred_tolerance_multiplier
            tolerances[currency] = max(tolerance,
                                       tolerances.get(currency, -1024))

            if not use_cost:
                continue

            # Compute bounds on the smallest digit of the number implied as cost.
            cost = posting.cost
            if cost is not None:
                cost_currency = cost.currency
                if isinstance(cost, Cost):
                    cost_tolerance = min(tolerance * cost.number, MAXIMUM_TOLERANCE)
                else:
                    assert isinstance(cost, CostSpec)
                    cost_tolerance = MAXIMUM_TOLERANCE
                    for cost_number in cost.number_total, cost.number_per:
                        if cost_number is None or cost_number is MISSING:
                            continue
                        cost_tolerance = min(tolerance * cost_number, cost_tolerance)
                cost_tolerances[cost_currency] += cost_tolerance

            # Compute bounds on the smallest digit of the number implied as cost.
            price = posting.price
            if isinstance(price, Amount) and isinstance(price.number, Decimal):
                price_currency = price.currency
                price_tolerance = min(tolerance * price.number, MAXIMUM_TOLERANCE)
                cost_tolerances[price_currency] += price_tolerance

    for currency, tolerance in cost_tolerances.items():
        tolerances[currency] = max(tolerance, tolerances.get(currency, -1024))

    default = tolerances.pop('*', ZERO)
    return defdict.ImmutableDictWithDefault(tolerances, default=default)

def is_tolerance_user_specified(tolerance):
    """Return true if the given tolerance number was user-specified.

    This would allow the user to provide a tolerance like # 0.1234 but not
    0.123456. This is used to detect whether a tolerance value # is input by the
    user and not inferred automatically.

    Args:
      tolerance: An instance of Decimal.
    Returns:
      A boolean.
    """
    return len(tolerance.as_tuple().digits) < MAX_TOLERANCE_DIGITS

def quantize_with_tolerance(tolerances, currency, number):
    """Quantize the units using the tolerance dict.

    Args:
      tolerances: A dict of currency to tolerance Decimalvalues.
      number: A number to quantize.
      currency: A string currency.
    Returns:
      A Decimal, the number possibly quantized.
    """
    # Applying rounding to the default tolerance, if there is one.
    tolerance = tolerances.get(currency)
    if tolerance:
        quantum = (tolerance * 2).normalize()

        # If the tolerance is a neat number provided by the user,
        # quantize the inferred numbers. See doc on quantize():
        #
        # Unlike other operations, if the length of the coefficient
        # after the quantize operation would be greater than
        # precision, then an InvalidOperation is signaled. This
        # guarantees that, unless there is an error condition, the
        # quantized exponent is always equal to that of the
        # right-hand operand.
        if is_tolerance_user_specified(quantum):
            number = number.quantize(quantum)
    return number

def check_invariants(inv):
    """Check the invariants of the Inventory.

    Args:
      inventory: An instance of Inventory.
    Returns:
      True if the invariants are respected.
    """
    # Check that all the keys are unique.
    lots = set((pos.units.currency, pos.cost) for pos in inv)
    assert len(lots) == len(inv), "Invalid inventory: {}".format(inv)
    # Check that none of the amounts is zero.
    for pos in inv:
        assert pos.units.number != ZERO, "Invalid position size: {}".format(pos)

@staticmethod
def from_string(string):
    """Create an Inventory from a string. This is useful for writing tests.

    Args:
      string: A comma-separated string of <number> <currency> with an
        optional {<number> <currency>} for the cost.
    Returns:
      A new instance of Inventory with the given balances.
    """
    new_inventory = Inventory()
    # We need to split the comma-separated positions but ignore commas
    # occurring within a {...cost...} specification.
    position_strs = re.split(
        r'([-+]?[0-9,.]+\s+[A-Z]+\s*(?:{[^}]*})?)\s*,?\s*', string)[1::2]
    for position_str in position_strs:
        new_inventory.add_position(position_from_string(position_str))
    return new_inventory

def D(strord=None):
    """Convert a string into a Decimal object.

    This is used in parsing amounts from files in the importers. This is the
    main function you should use to build all numbers the system manipulates
    (never use floating-point in an accounting system). Commas are stripped and
    ignored, as they are assumed to be thousands separators (the French comma
    separator as decimal is not supported). This function just returns the
    argument if it is already a Decimal object, for convenience.

    Args:
      strord: A string or Decimal instance.
    Returns:
      A Decimal instance.
    """
    try:
        # Note: try a map lookup and optimize performance here.
        if strord is None or strord == '':
            return Decimal()
        elif isinstance(strord, str):
            return Decimal(_CLEAN_NUMBER_RE.sub('', strord))
        elif isinstance(strord, Decimal):
            return strord
        elif isinstance(strord, (int, float)):
            return Decimal(strord)
        else:
            assert strord is None, "Invalid value to convert: {}".format(strord)
    except Exception as exc:
        raise ValueError("Impossible to create Decimal instance from {!s}: {}".format(
                         strord, exc))

def is_fast_decimal(decimal_module):
    "Return true if a fast C decimal implementation is installed."
    return isinstance(decimal_module.Decimal().sqrt, types.BuiltinFunctionType)

def round_to(number, increment):
    """Round a number *down* to a particular increment.

    Args:
      number: A Decimal, the number to be rounded.
      increment: A Decimal, the size of the increment.
    Returns:
      A Decimal, the rounded number.
    """
    return int((number / increment)) * increment

def same_sign(number1, number2):
    """Return true if both numbers have the same sign.

    Args:
      number1: An instance of Decimal.
      number2: An instance of Decimal.
    Returns:
      A boolean.
    """
    return (number1 >= 0) == (number2 >= 0)

def cost_to_str(cost, dformat, detail=True):
    """Format an instance of Cost or a CostSpec to a string.

    Args:
      cost: An instance of Cost or CostSpec.
      dformat: A DisplayFormatter object.
      detail: A boolean, true if we should render the non-amount components.
    Returns:
      A string, suitable for formatting.
    """
    strlist = []

    if isinstance(cost, Cost):
        if isinstance(cost.number, Decimal):
            strlist.append(Amount(cost.number, cost.currency).to_string(dformat))
        if detail:
            if cost.date:
                strlist.append(cost.date.isoformat())
            if cost.label:
                strlist.append('"{}"'.format(cost.label))

    elif isinstance(cost, CostSpec):
        if isinstance(cost.number_per, Decimal) or isinstance(cost.number_total, Decimal):
            amountlist = []
            if isinstance(cost.number_per, Decimal):
                amountlist.append(dformat.format(cost.number_per))
            if isinstance(cost.number_total, Decimal):
                amountlist.append('#')
                amountlist.append(dformat.format(cost.number_total))
            if isinstance(cost.currency, str):
                amountlist.append(cost.currency)
            strlist.append(' '.join(amountlist))
        if detail:
            if cost.date:
                strlist.append(cost.date.isoformat())
            if cost.label:
                strlist.append('"{}"'.format(cost.label))
            if cost.merge:
                strlist.append('*')

    return ', '.join(strlist)

@staticmethod
def from_amounts(units, cost_amount=None):
    """Create a position from an amount and a cost.

    Args:
      amount: An amount, that represents the number of units and the lot currency.
      cost_amount: If not None, represents the cost amount.
    Returns:
      A Position instance.
    """
    assert cost_amount is None or isinstance(cost_amount, Amount), (
        "Invalid type for cost: {}".format(cost_amount))
    cost = (Cost(cost_amount.number, cost_amount.currency, None, None)
            if cost_amount else
            None)
    return Position(units, cost)

@staticmethod
def from_string(string):
    """Create a position from a string specification.

    This is a miniature parser used for building tests.

    Args:
      string: A string of <number> <currency> with an optional {<number>
        <currency>} for the cost, similar to the parser syntax.
    Returns:
      A new instance of Position.
    """
    match = re.match(
        (r'\s*({})\s+({})'
         r'(?:\s+{{([^}}]*)}})?'
         r'\s*$').format(NUMBER_RE, CURRENCY_RE),
        string)
    if not match:
        raise ValueError("Invalid string for position: '{}'".format(string))

    number = D(match.group(1))
    currency = match.group(2)

    # Parse a cost expression.
    cost_number = None
    cost_currency = None
    date = None
    label = None
    cost_expression = match.group(3)
    if match.group(3):
        expressions = [expr.strip() for expr in re.split('[,/]', cost_expression)]
        for expr in expressions:

            # Match a compound number.
            match = re.match(
                r'({NUMBER_RE})\s*(?:#\s*({NUMBER_RE}))?\s+({CURRENCY_RE})$'
                .format(NUMBER_RE=NUMBER_RE, CURRENCY_RE=CURRENCY_RE),
                expr
            )
            if match:
                per_number, total_number, cost_currency = match.group(1, 2, 3)
                per_number = D(per_number) if per_number else ZERO
                total_number = D(total_number) if total_number else ZERO
                if total_number:
                    # Calculate the per-unit cost.
                    total = number * per_number + total_number
                    per_number = total / number
                cost_number = per_number
                continue

            # Match a date.
            match = re.match(r'(\d\d\d\d)[-/](\d\d)[-/](\d\d)$', expr)
            if match:
                date = datetime.date(*map(int, match.group(1, 2, 3)))
                continue

            # Match a label.
            match = re.match(r'"([^"]+)*"$', expr)
            if match:
                label = match.group(1)
                continue

            # Match a merge-cost marker.
            match = re.match(r'\*$', expr)
            if match:
                raise ValueError("Merge-code not supported in string constructor.")

            raise ValueError("Invalid cost component: '{}'".format(expr))
        cost = Cost(cost_number, cost_currency, date, label)
    else:
        cost = None

    return Position(Amount(number, currency), cost)

def get_position(posting):
    """Build a Position instance from a Posting instance.

    Args:
      posting: An instance of Posting.
    Returns:
      An instance of Position.
    """
    return Position(posting.units, posting.cost)

def to_string(pos, dformat=DEFAULT_FORMATTER, detail=True):
    """Render the Position or Posting instance to a string.

    Args:
      pos: An instance of Position or Posting.
      dformat: An instance of DisplayFormatter.
      detail: A boolean, true if we should only render the lot details
       beyond the cost (lot-date, label, etc.). If false, we only render
       the cost, if present.
    Returns:
      A string, the rendered position.
    """
    pos_str = pos.units.to_string(dformat)
    if pos.cost is not None:
        pos_str = '{} {{{}}}'.format(pos_str, cost_to_str(pos.cost, dformat, detail))
    return pos_str

def build_price_map(entries):
    """Build a price map from a list of arbitrary entries.

    If multiple prices are found for the same (currency, cost-currency) pair at
    the same date, the latest date is kept and the earlier ones (for that day)
    are discarded.

    If inverse price pairs are found, e.g. USD in AUD and AUD in USD, the
    inverse that has the smallest number of price points is converted into the
    one that has the most price points. In that way they are reconciled into a
    single one.

    Args:
      entries: A list of directives, hopefully including some Price and/or
      Transaction entries.
    Returns:
      A dict of (currency, cost-currency) keys to sorted lists of (date, number)
      pairs, where 'date' is the date the price occurs at and 'number' a Decimal
      that represents the price, or rate, between these two
      currencies/commodities. Each date occurs only once in the sorted list of
      prices of a particular key. All of the inverses are automatically
      generated in the price map.
    """
    # Fetch a list of all the price entries seen in the ledger.
    price_entries = [entry
                     for entry in entries
                     if isinstance(entry, Price)]

    # Build a map of exchange rates between these units.
    # (base-currency, quote-currency) -> List of (date, rate).
    price_map = collections.defaultdict(list)
    for price in price_entries:
        base_quote = (price.currency, price.amount.currency)
        price_map[base_quote].append((price.date, price.amount.number))

    # Find pairs of inversed units.
    inversed_units = []
    for base_quote, values in price_map.items():
        base, quote = base_quote
        if (quote, base) in price_map:
            inversed_units.append(base_quote)

    # Find pairs of inversed units, and swallow the conversion with the smaller
    # number of rates into the other one.
    for base, quote in inversed_units:
        bq_prices = price_map[(base, quote)]
        qb_prices = price_map[(quote, base)]
        remove = ((base, quote)
                  if len(bq_prices) < len(qb_prices)
                  else (quote, base))
        base, quote = remove

        remove_list = price_map[remove]
        insert_list = price_map[(quote, base)]
        del price_map[remove]

        inverted_list = [(date, ONE/rate)
                         for (date, rate) in remove_list
                         if rate != ZERO]
        insert_list.extend(inverted_list)

    # Unzip and sort each of the entries and eliminate duplicates on the date.
    sorted_price_map = PriceMap({
        base_quote: list(misc_utils.sorted_uniquify(date_rates, lambda x: x[0], last=True))
        for (base_quote, date_rates) in price_map.items()})

    # Compute and insert all the inverted rates.
    forward_pairs = list(sorted_price_map.keys())
    for (base, quote), price_list in list(sorted_price_map.items()):
        # Note: You have to filter out zero prices for zero-cost postings, like
        # gifted options.
        sorted_price_map[(quote, base)] = [
            (date, ONE/price) for date, price in price_list
            if price != ZERO]

    sorted_price_map.forward_pairs = forward_pairs
    return sorted_price_map

def get_all_prices(price_map, base_quote):
    """Return a sorted list of all (date, number) price pairs.

    Args:
      price_map: A price map, which is a dict of (base, quote) -> list of (date,
        number) tuples, as created by build_price_map.
      base_quote: A pair of strings, the base currency to lookup, and the quote
        currency to lookup, which expresses which units the base currency is
        denominated in. This may also just be a string, with a '/' separator.
    Returns:
      A list of (date, Decimal) pairs, sorted by date.
    Raises:
      KeyError: If the base/quote could not be found.
    """
    base_quote = normalize_base_quote(base_quote)
    return _lookup_price_and_inverse(price_map, base_quote)

def get_last_price_entries(entries, date):
    """Run through the entries until the given date and return the last
    Price entry encountered for each (currency, cost-currency) pair.

    Args:
      entries: A list of directives.
      date: An instance of datetime.date. If None, the very latest price
        is returned.
    Returns:
      A list of price entries.
    """
    price_entry_map = {}
    for entry in entries:
        if date is not None and entry.date >= date:
            break
        if isinstance(entry, Price):
            base_quote = (entry.currency, entry.amount.currency)
            price_entry_map[base_quote] = entry
    return sorted(price_entry_map.values(), key=data.entry_sortkey)

def get_latest_price(price_map, base_quote):
    """Return the latest price/rate from a price map for the given base/quote pair.
    This is often used to just get the 'current' price if you're looking at the
    entire set of entries.

    Args:
      price_map: A price map, which is a dict of (base, quote) -> list of (date,
        number) tuples, as created by build_price_map.
    Returns:
      A pair of (date, number), where 'date' is a datetime.date instance and
      'number' is a Decimal of the price, or rate, at that date. The date is the
      latest date which we have an available price for in the price map.
    """
    base_quote = normalize_base_quote(base_quote)

    # Handle the degenerate case of a currency priced into its own.
    base, quote = base_quote
    if quote is None or base == quote:
        return (None, ONE)

    # Look up the list and return the latest element. The lists are assumed to
    # be sorted.
    try:
        price_list = _lookup_price_and_inverse(price_map, base_quote)
    except KeyError:
        price_list = None
    if price_list:
        return price_list[-1]
    else:
        return None, None

def get_price(price_map, base_quote, date=None):
    """Return the price as of the given date.

    If the date is unspecified, return the latest price.

    Args:
      price_map: A price map, which is a dict of (base, quote) -> list of (date,
        number) tuples, as created by build_price_map.
      base_quote: A pair of strings, the base currency to lookup, and the quote
        currency to lookup, which expresses which units the base currency is
        denominated in. This may also just be a string, with a '/' separator.
      date: A datetime.date instance, the date at which we want the conversion
        rate.
    Returns:
      A pair of (datetime.date, Decimal) instance. If no price information could
      be found, return (None, None).
    """
    if date is None:
        return get_latest_price(price_map, base_quote)

    base_quote = normalize_base_quote(base_quote)

    # Handle the degenerate case of a currency priced into its own.
    base, quote = base_quote
    if quote is None or base == quote:
        return (None, ONE)

    try:
        price_list = _lookup_price_and_inverse(price_map, base_quote)
        index = bisect_key.bisect_right_with_key(price_list, date, key=lambda x: x[0])
        if index == 0:
            return None, None
        else:
            return price_list[index-1]
    except KeyError:
        return None, None

def normalize_base_quote(base_quote):
    """Convert a slash-separated string to a pair of strings.

    Args:
      base_quote: A pair of strings, the base currency to lookup, and the quote
        currency to lookup, which expresses which units the base currency is
        denominated in. This may also just be a string, with a '/' separator.
    Returns:
      A pair of strings.
    """
    if isinstance(base_quote, str):
        base_quote_norm = tuple(base_quote.split('/'))
        assert len(base_quote_norm) == 2, base_quote
        base_quote = base_quote_norm
    assert isinstance(base_quote, tuple), base_quote
    return base_quote

def compute_balance(real_account, leaf_only=False):
    """Compute the total balance of this account and all its subaccounts.

    Args:
      real_account: A RealAccount instance.
      leaf_only: A boolean flag, true if we should yield only leaves.
    Returns:
      An Inventory.
    """
    return functools.reduce(operator.add, [
        ra.balance for ra in iter_children(real_account, leaf_only)])

def compute_postings_balance(txn_postings):
    """Compute the balance of a list of Postings's or TxnPosting's positions.

    Args:
      postings: A list of Posting instances and other directives (which are
        skipped).
    Returns:
      An Inventory.
    """
    final_balance = inventory.Inventory()
    for txn_posting in txn_postings:
        if isinstance(txn_posting, Posting):
            final_balance.add_position(txn_posting)
        elif isinstance(txn_posting, TxnPosting):
            final_balance.add_position(txn_posting.posting)
    return final_balance

def contains(real_account, account_name):
    """True if the given account node contains the subaccount name.

    Args:
      account_name: A string, the name of a direct or indirect subaccount of
        this node.
    Returns:
      A boolean, true the name is a child of this node.
    """
    return get(real_account, account_name) is not None

def dump(root_account):
    """Convert a RealAccount node to a line of lines.

    Note: this is not meant to be used to produce text reports; the reporting
    code should produce an intermediate object that contains the structure of
    it, which can then be rendered to ASCII, HTML or CSV formats. This is
    intended as a convenient little function for dumping trees of data for
    debugging purposes.

    Args:
      root_account: A RealAccount instance.
    Returns:
      A list of tuples of (first_line, continuation_line, real_account) where
        first_line: A string, the first line to render, which includes the
          account name.
        continuation_line: A string, further line to render if necessary.
        real_account: The RealAccount instance which corresponds to this
          line.
    """
    # Compute all the lines ahead of time in order to calculate the width.
    lines = []

    # Start with the root node. We push the constant prefix before this node,
    # the account name, and the RealAccount instance. We will maintain a stack
    # of children nodes to render.
    stack = [('', root_account.account, root_account, True)]
    while stack:
        prefix, name, real_account, is_last = stack.pop(-1)

        if real_account is root_account:
            # For the root node, we don't want to render any prefix.
            first = cont = ''
        else:
            # Compute the string that precedes the name directly and the one below
            # that for the continuation lines.
            #  |
            #  @@@ Bank1    <----------------
            #  @@@ |
            #  |   |-- Checking
            if is_last:
                first = prefix + PREFIX_LEAF_1
                cont = prefix + PREFIX_LEAF_C
            else:
                first = prefix + PREFIX_CHILD_1
                cont = prefix + PREFIX_CHILD_C

        # Compute the name to render for continuation lines.
        #  |
        #  |-- Bank1
        #  |   @@@       <----------------
        #  |   |-- Checking
        if len(real_account) > 0:
            cont_name = PREFIX_CHILD_C
        else:
            cont_name = PREFIX_LEAF_C

        # Add a line for this account.
        if not (real_account is root_account and not name):
            lines.append((first + name,
                          cont + cont_name,
                          real_account))

        # Push the children onto the stack, being careful with ordering and
        # marking the last node as such.
        child_items = sorted(real_account.items(), reverse=True)
        if child_items:
            child_iter = iter(child_items)
            child_name, child_account = next(child_iter)
            stack.append((cont, child_name, child_account, True))
            for child_name, child_account in child_iter:
                stack.append((cont, child_name, child_account, False))

    if not lines:
        return lines

    # Compute the maximum width of the lines and convert all of them to the same
    # maximal width. This makes it easy on the client.
    max_width = max(len(first_line) for first_line, _, __ in lines)
    line_format = '{{:{width}}}'.format(width=max_width)
    return [(line_format.format(first_line),
             line_format.format(cont_line),
             real_node)
            for (first_line, cont_line, real_node) in lines]

def dump_balances(real_root, dformat, at_cost=False, fullnames=False, file=None):
    """Dump a realization tree with balances.

    Args:
      real_root: An instance of RealAccount.
      dformat: An instance of DisplayFormatter to format the numbers with.
      at_cost: A boolean, if true, render the values at cost.
      fullnames: A boolean, if true, don't render a tree of accounts and
        render the full account names.
      file: A file object to dump the output to. If not specified, we
        return the output as a string.
    Returns:
      A string, the rendered tree, or nothing, if 'file' was provided.
    """
    if fullnames:
        # Compute the maximum account name length;
        maxlen = max(len(real_child.account)
                     for real_child in iter_children(real_root, leaf_only=True))
        line_format = '{{:{width}}} {{}}\n'.format(width=maxlen)
    else:
        line_format = '{}       {}\n'

    output = file or io.StringIO()
    for first_line, cont_line, real_account in dump(real_root):
        if not real_account.balance.is_empty():
            if at_cost:
                rinv = real_account.balance.reduce(convert.get_cost)
            else:
                rinv = real_account.balance.reduce(convert.get_units)
            amounts = [position.units for position in rinv.get_positions()]
            positions = [amount_.to_string(dformat)
                         for amount_ in sorted(amounts, key=amount.sortkey)]
        else:
            positions = ['']

        if fullnames:
            for position in positions:
                if not position and len(real_account) > 0:
                    continue  # Skip parent accounts with no position to render.
                output.write(line_format.format(real_account.account, position))
        else:
            line = first_line
            for position in positions:
                output.write(line_format.format(line, position))
                line = cont_line

    if file is None:
        return output.getvalue()

def filter(real_account, predicate):
    """Filter a RealAccount tree of nodes by the predicate.

    This function visits the tree and applies the predicate on each node. It
    returns a partial clone of RealAccount whereby on each node
    - either the predicate is true, or
    - for at least one child of the node the predicate is true.
    All the leaves have the predicate be true.

    Args:
      real_account: An instance of RealAccount.
      predicate: A callable/function which accepts a real_account and returns
        a boolean. If the function returns True, the node is kept.
    Returns:
      A shallow clone of RealAccount is always returned.
    """
    assert isinstance(real_account, RealAccount)

    real_copy = RealAccount(real_account.account)
    real_copy.balance = real_account.balance
    real_copy.txn_postings = real_account.txn_postings

    for child_name, real_child in real_account.items():
        real_child_copy = filter(real_child, predicate)
        if real_child_copy is not None:
            real_copy[child_name] = real_child_copy

    if len(real_copy) > 0 or predicate(real_account):
        return real_copy

def find_last_active_posting(txn_postings):
    """Look at the end of the list of postings, and find the last
    posting or entry that is not an automatically added directive.
    Note that if the account is closed, the last posting is assumed
    to be a Close directive (this is the case if the input is valid
    and checks without errors.

    Args:
      txn_postings: a list of postings or entries.
    Returns:
      An entry, or None, if the input list was empty.
    """
    for txn_posting in reversed(txn_postings):
        assert not isinstance(txn_posting, Posting)

        if not isinstance(txn_posting, (TxnPosting, Open, Close, Pad, Balance, Note)):
            continue

        # pylint: disable=bad-continuation
        if (isinstance(txn_posting, TxnPosting) and
            txn_posting.txn.flag == flags.FLAG_UNREALIZED):
            continue
        return txn_posting

def get(real_account, account_name, default=None):
    """Fetch the subaccount name from the real_account node.

    Args:
      real_account: An instance of RealAccount, the parent node to look for
        children of.
      account_name: A string, the name of a possibly indirect child leaf
        found down the tree of 'real_account' nodes.
      default: The default value that should be returned if the child
        subaccount is not found.
    Returns:
      A RealAccount instance for the child, or the default value, if the child
      is not found.
    """
    if not isinstance(account_name, str):
        raise ValueError
    components = account.split(account_name)
    for component in components:
        real_child = real_account.get(component, default)
        if real_child is default:
            return default
        real_account = real_child
    return real_account

def get_or_create(real_account, account_name):
    """Fetch the subaccount name from the real_account node.

    Args:
      real_account: An instance of RealAccount, the parent node to look for
        children of, or create under.
      account_name: A string, the name of the direct or indirect child leaf
        to get or create.
    Returns:
      A RealAccount instance for the child, or the default value, if the child
      is not found.
    """
    if not isinstance(account_name, str):
        raise ValueError
    components = account.split(account_name)
    path = []
    for component in components:
        path.append(component)
        real_child = real_account.get(component, None)
        if real_child is None:
            real_child = RealAccount(account.join(*path))
            real_account[component] = real_child
        real_account = real_child
    return real_account

def get_postings(real_account):
    """Return a sorted list a RealAccount's postings and children.

    Args:
      real_account: An instance of RealAccount.
    Returns:
      A list of Posting or directories.
    """
    # We accumulate all the postings at once here instead of incrementally
    # because we need to return them sorted.
    accumulator = []
    for real_child in iter_children(real_account):
        accumulator.extend(real_child.txn_postings)
    accumulator.sort(key=data.posting_sortkey)
    return accumulator

def index_key(sequence, value, key, cmp):
    """Find the index of the first element in 'sequence' which is equal to 'value'.
    If 'key' is specified, the value compared to the value returned by this
    function. If the value is not found, return None.

    Args:
      sequence: The sequence to search.
      value: The value to search for.
      key: A predicate to call to obtain the value to compare against.
      cmp: A comparison predicate.
    Returns:
      The index of the first element found, or None, if the element was not found.
    """
    for index, element in enumerate(sequence):
        if cmp(key(element), value):
            return index
    return

def iter_children(real_account, leaf_only=False):
    """Iterate this account node and all its children, depth-first.

    Args:
      real_account: An instance of RealAccount.
      leaf_only: A boolean flag, true if we should yield only leaves.
    Yields:
      Instances of RealAccount, beginning with this account. The order is
      undetermined.
    """
    if leaf_only:
        if len(real_account) == 0:
            yield real_account
        else:
            for key, real_child in sorted(real_account.items()):
                for real_subchild in iter_children(real_child, leaf_only):
                    yield real_subchild
    else:
        yield real_account
        for key, real_child in sorted(real_account.items()):
            for real_subchild in iter_children(real_child):
                yield real_subchild

def iterate_with_balance(txn_postings):
    """Iterate over the entries, accumulating the running balance.

    For each entry, this yields tuples of the form:

      (entry, postings, change, balance)

    entry: This is the directive for this line. If the list contained Posting
      instance, this yields the corresponding Transaction object.
    postings: A list of postings on this entry that affect the balance. Only the
      postings encountered in the input list are included; only those affect the
      balance. If 'entry' is not a Transaction directive, this should always be
      an empty list. We preserve the original ordering of the postings as they
      appear in the input list.
    change: An Inventory object that reflects the total change due to the
      postings from this entry that appear in the list. For example, if a
      Transaction has three postings and two are in the input list, the sum of
      the two postings will be in the 'change' Inventory object. However, the
      position for the transactions' third posting--the one not included in the
      input list--will not be in this inventory.
    balance: An Inventory object that reflects the balance *after* adding the
      'change' inventory due to this entry's transaction. The 'balance' yielded
      is never None, even for entries that do not affect the balance, that is,
      with an empty 'change' inventory. It's up to the caller, the one rendering
      the entry, to decide whether to render this entry's change for a
      particular entry type.

    Note that if the input list of postings-or-entries is not in sorted date
    order, two postings for the same entry appearing twice with a different date
    in between will cause the entry appear twice. This is correct behavior, and
    it is expected that in practice this should never happen anyway, because the
    list of postings or entries should always be sorted. This method attempts to
    detect this and raises an assertion if this is seen.

    Args:
      txn_postings: A list of postings or directive instances.
        Postings affect the balance; other entries do not.
    Yields:
      Tuples of (entry, postings, change, balance) as described above.
    """

    # The running balance.
    running_balance = inventory.Inventory()

    # Previous date.
    prev_date = None

    # A list of entries at the current date.
    date_entries = []

    first = lambda pair: pair[0]
    for txn_posting in txn_postings:

        # Get the posting if we are dealing with one.
        assert not isinstance(txn_posting, Posting)
        if isinstance(txn_posting, TxnPosting):
            posting = txn_posting.posting
            entry = txn_posting.txn
        else:
            posting = None
            entry = txn_posting

        if entry.date != prev_date:
            assert prev_date is None or entry.date > prev_date, (
                "Invalid date order for postings: {} > {}".format(prev_date, entry.date))
            prev_date = entry.date

            # Flush the dated entries.
            for date_entry, date_postings in date_entries:
                change = inventory.Inventory()
                if date_postings:
                    # Compute the change due to this transaction and update the
                    # total balance at the same time.
                    for date_posting in date_postings:
                        change.add_position(date_posting)
                        running_balance.add_position(date_posting)
                yield date_entry, date_postings, change, running_balance

            date_entries.clear()
            assert not date_entries

        if posting is not None:
            # De-dup multiple postings on the same transaction entry by
            # grouping their positions together.
            index = index_key(date_entries, entry, first, operator.is_)
            if index is None:
                date_entries.append((entry, [posting]))
            else:
                # We are indeed de-duping!
                postings = date_entries[index][1]
                postings.append(posting)
        else:
            # This is a regular entry; nothing to add/remove.
            date_entries.append((entry, []))

    # Flush the final dated entries if any, same as above.
    for date_entry, date_postings in date_entries:
        change = inventory.Inventory()
        if date_postings:
            for date_posting in date_postings:
                change.add_position(date_posting)
                running_balance.add_position(date_posting)
        yield date_entry, date_postings, change, running_balance
    date_entries.clear()

def postings_by_account(entries):
    """Create lists of postings and balances by account.

    This routine aggregates postings and entries grouping them by account name.
    The resulting lists contain postings in-lieu of Transaction directives, but
    the other directives are stored as entries. This yields a list of postings
    or other entries by account. All references to accounts are taken into
    account.

    Args:
      entries: A list of directives.
    Returns:
       A mapping of account name to list of TxnPosting instances or
       non-Transaction directives, sorted in the same order as the entries.
    """
    txn_postings_map = collections.defaultdict(list)
    for entry in entries:

        if isinstance(entry, Transaction):
            # Insert an entry for each of the postings.
            for posting in entry.postings:
                txn_postings_map[posting.account].append(
                    TxnPosting(entry, posting))

        elif isinstance(entry, (Open, Close, Balance, Note, Document)):
            # Append some other entries in the realized list.
            txn_postings_map[entry.account].append(entry)

        elif isinstance(entry, Pad):
            # Insert the pad entry in both realized accounts.
            txn_postings_map[entry.account].append(entry)
            txn_postings_map[entry.source_account].append(entry)

        elif isinstance(entry, Custom):
            # Insert custom entry for each account in its values.
            for custom_value in entry.values:
                if custom_value.dtype == account.TYPE:
                    txn_postings_map[custom_value.value].append(entry)

    return txn_postings_map

def realize(entries, min_accounts=None, compute_balance=True):
    r"""Group entries by account, into a "tree" of realized accounts. RealAccount's
    are essentially containers for lists of postings and the final balance of
    each account, and may be non-leaf accounts (used strictly for organizing
    accounts into a hierarchy). This is then used to issue reports.

    The lists of postings in each account my be any of the entry types, except
    for Transaction, whereby Transaction entries are replaced by the specific
    Posting legs that belong to the account. Here's a simple diagram that
    summarizes this seemingly complex, but rather simple data structure:

       +-------------+ postings  +------+
       | RealAccount |---------->| Open |
       +-------------+           +------+
                                     |
                                     v
                              +------------+     +-------------+
                              | TxnPosting |---->| Transaction |
                              +------------+     +-------------+
                                     |      \                 \\\
                                     v       `\.__          +---------+
                                  +-----+         `-------->| Posting |
                                  | Pad |                   +---------+
                                  +-----+
                                     |
                                     v
                                +---------+
                                | Balance |
                                +---------+
                                     |
                                     v
                                 +-------+
                                 | Close |
                                 +-------+
                                     |
                                     .

    Args:
      entries: A list of directives.
      min_accounts: A list of strings, account names to ensure we create,
        regardless of whether there are postings on those accounts or not.
        This can be used to ensure the root accounts all exist.
      compute_balance: A boolean, true if we should compute the final
        balance on the realization.
    Returns:
      The root RealAccount instance.
    """
    # Create lists of the entries by account.
    txn_postings_map = postings_by_account(entries)

    # Create a RealAccount tree and compute the balance for each.
    real_root = RealAccount('')
    for account_name, txn_postings in txn_postings_map.items():
        real_account = get_or_create(real_root, account_name)
        real_account.txn_postings = txn_postings
        if compute_balance:
            real_account.balance = compute_postings_balance(txn_postings)

    # Ensure a minimum set of accounts that should exist. This is typically
    # called with an instance of AccountTypes to make sure that those exist.
    if min_accounts:
        for account_name in min_accounts:
            get_or_create(real_root, account_name)

    return real_root