#!python

"""
Generate random passwords in a hopefully secure manner. By default, `fpw`
generates completely random passwords. To support insecure systems, you can
specify required character groups. To support humans, you can generate
pronounceable passwords. To break things, you can generate passwords from a
large unicode character set.
"""

import argparse
import string
import re
import json
import os
from itertools import chain
import operator
from bisect import bisect
from collections import Counter, defaultdict
from secrets import choice, randbelow


REGEX_LOWERCASE = re.compile("[{:s}]".format("".join(string.ascii_lowercase)))
REGEX_UPPERCASE = re.compile("[{:s}]".format("".join(string.ascii_uppercase)))
REGEX_DIGITS = re.compile("[{:s}]".format("".join(string.digits)))
REGEX_SPECIAL = re.compile("[{:s}]".format(
    re.escape("".join(string.punctuation))))

UNICODE_RANGE = chain(range(0x20, 0x7E), range(0xA1, 0x27F0))

MARKOV_DATA_ENCODED = """
{"null": {"a": 25416, "v": 5330, "b": 18413, "c": 32106, "d": 18732, "e": 14197, "f": 11893, "g": 10953, "h": 13743, "i": 13199, "y": 1143, "j": 2840, "k": 3952, "l": 10002, "m": 19805, "n": 13458, "o": 12681, "p": 34860, "q": 1793, "r": 16783, "s": 38761, "t": 18818, "u": 22767, "w": 6559, "x": 507, "z": 1388}, "a": {"a": 255, "h": 1450, "l": 40559, "m": 11450, "n": 40042, "r": 31754, "s": 16637, "b": 13237, "c": 18023, "y": 2611, "t": 42057, "x": 1286, "d": 9605, "f": 2147, "i": 6588, "k": 3053, "p": 10562, "g": 8545, "u": 5457, "v": 3495, "z": 1474, "e": 6131, "o": 389, "q": 341, "j": 318, "w": 1952}, "h": {"e": 18798, "i": 14800, "s": 836, "h": 112, "r": 4080, "l": 1785, "m": 904, "y": 8173, "o": 14847, "u": 2801, "a": 14065, "t": 2480, "k": 62, "n": 992, "c": 116, "w": 409, "b": 307, "p": 181, "z": 18, "g": 77, "f": 259, "d": 138, "j": 15, "v": 33, "q": 12}, "e": {"d": 30877, "s": 46930, "l": 19587, "h": 1461, "r": 66713, "j": 396, "n": 38434, "e": 7312, "t": 18125, "m": 12725, "y": 1743, "a": 15041, "v": 3385, "c": 13180, "g": 4208, "i": 4366, "p": 8610, "k": 695, "o": 5476, "z": 450, "u": 4490, "w": 2367, "b": 3042, "f": 3774, "q": 931, "x": 5175}, "i": {"n": 60886, "i": 579, "s": 36502, "c": 35999, "t": 24854, "o": 22038, "a": 20666, "e": 13427, "z": 8384, "r": 7287, "l": 15968, "d": 14417, "u": 2242, "p": 7030, "v": 8371, "g": 7040, "b": 4670, "m": 8343, "f": 6241, "k": 2633, "x": 767, "y": 91, "w": 147, "h": 420, "q": 500, "j": 132}, "n": {"g": 29713, "i": 22288, "a": 18634, "c": 13466, "e": 32262, "d": 15069, "m": 1606, "t": 29533, "s": 14510, "n": 3949, "o": 20423, "u": 3301, "r": 2084, "y": 1749, "z": 527, "l": 1794, "v": 1838, "k": 2202, "p": 2539, "b": 1423, "w": 940, "f": 3417, "h": 1407, "j": 522, "q": 489, "x": 108}, "l": {"i": 32897, "s": 2966, "f": 946, "v": 1090, "l": 18756, "y": 20196, "u": 6727, "a": 25052, "o": 18943, "e": 34576, "m": 1399, "t": 3549, "c": 1288, "n": 1085, "d": 2320, "b": 743, "g": 853, "h": 259, "p": 1458, "r": 184, "k": 901, "w": 304, "z": 51, "j": 20, "q": 19, "x": 10}, "r": {"d": 5667, "k": 1927, "g": 3256, "o": 31100, "r": 5751, "u": 6071, "i": 35622, "e": 40022, "s": 11857, "a": 35216, "t": 8440, "y": 7582, "n": 4308, "v": 1730, "m": 6706, "b": 3087, "p": 3508, "h": 2077, "l": 2822, "c": 5741, "f": 1520, "w": 902, "x": 12, "q": 147, "j": 183, "z": 119}, "d": {"v": 375, "w": 494, "e": 22147, "a": 8639, "d": 1822, "o": 8317, "i": 19348, "l": 3017, "u": 3435, "n": 1424, "g": 1029, "s": 2717, "y": 1779, "r": 5029, "h": 479, "p": 184, "c": 201, "f": 343, "j": 294, "m": 619, "t": 145, "z": 40, "b": 358, "k": 46, "q": 12, "x": 2}, "v": {"a": 5021, "e": 17745, "o": 2556, "i": 6761, "u": 459, "v": 46, "t": 8, "y": 134, "r": 105, "d": 9, "g": 8, "n": 13, "s": 26, "l": 19, "c": 7, "w": 2, "k": 6, "z": 4, "h": 1, "p": 3, "m": 3, "b": 1}, "k": {"s": 1770, "a": 2349, "h": 465, "e": 7885, "i": 4525, "r": 392, "z": 3, "m": 242, "n": 769, "t": 258, "b": 258, "o": 1039, "l": 1194, "u": 485, "c": 58, "k": 132, "p": 140, "v": 30, "w": 299, "y": 670, "d": 62, "f": 191, "g": 36, "j": 25, "q": 1, "x": 1}, "w": {"o": 3246, "h": 1459, "a": 4851, "e": 3495, "i": 3643, "l": 615, "n": 959, "s": 719, "r": 739, "t": 166, "m": 145, "u": 112, "y": 160, "b": 243, "p": 103, "w": 82, "g": 50, "d": 250, "f": 137, "k": 180, "c": 71, "j": 5, "z": 20, "q": 2, "v": 2}, "o": {"l": 18296, "n": 47067, "g": 10672, "t": 12894, "r": 28810, "s": 15626, "u": 19518, "i": 5816, "m": 17030, "c": 10904, "z": 761, "a": 3667, "h": 1028, "p": 14881, "v": 6396, "b": 4784, "o": 7476, "w": 4375, "d": 7714, "f": 2145, "x": 1995, "k": 1782, "y": 1060, "e": 2840, "q": 329, "j": 155}, "g": {"h": 2864, "e": 11915, "o": 4842, "a": 7713, "i": 8527, "g": 2113, "l": 5660, "n": 2781, "y": 2064, "s": 1682, "r": 7273, "m": 845, "u": 3820, "b": 198, "c": 34, "d": 124, "k": 35, "p": 69, "t": 213, "w": 211, "f": 121, "v": 5, "j": 12, "q": 1, "z": 12}, "c": {"a": 23273, "i": 11481, "u": 7751, "k": 6525, "l": 5088, "o": 24157, "t": 10302, "e": 14904, "y": 3558, "c": 2386, "h": 19822, "s": 1031, "r": 8335, "m": 52, "n": 228, "p": 42, "q": 178, "x": 1, "d": 53, "b": 23, "f": 19, "w": 20, "g": 14, "v": 2, "z": 45}, "t": {"e": 44229, "i": 49645, "o": 21357, "s": 5670, "u": 7301, "h": 16523, "a": 21117, "r": 20369, "j": 67, "t": 5826, "c": 1778, "n": 717, "l": 3471, "m": 882, "y": 7364, "b": 538, "p": 395, "g": 271, "f": 748, "w": 1133, "k": 69, "z": 340, "d": 196, "v": 82, "q": 20, "x": 7}, "s": {"v": 130, "c": 9519, "t": 34122, "e": 20839, "a": 9273, "s": 20859, "i": 18106, "g": 266, "h": 11197, "l": 3754, "k": 1825, "o": 8826, "m": 7285, "u": 10456, "y": 3007, "r": 281, "f": 485, "q": 1021, "n": 2573, "p": 8548, "b": 483, "w": 1412, "d": 256, "j": 71, "z": 20}, "b": {"a": 8685, "d": 452, "u": 4645, "l": 12411, "o": 6967, "b": 1711, "e": 8859, "y": 596, "i": 8912, "r": 6095, "c": 390, "f": 144, "h": 187, "j": 256, "k": 36, "m": 237, "n": 166, "p": 206, "s": 1525, "t": 492, "v": 141, "w": 78, "g": 87, "x": 4, "z": 10, "q": 10}, "u": {"a": 4130, "s": 19837, "l": 14100, "m": 8779, "r": 14228, "e": 3452, "c": 4527, "v": 450, "n": 27616, "d": 3659, "g": 2365, "t": 9310, "x": 403, "p": 5085, "b": 5296, "i": 4152, "z": 280, "o": 1042, "k": 531, "y": 147, "f": 968, "j": 80, "w": 30, "u": 70, "q": 41, "h": 105}, "x": {"i": 2140, "a": 1050, "e": 1115, "y": 758, "t": 1180, "o": 759, "m": 33, "u": 285, "p": 972, "l": 60, "c": 613, "b": 41, "f": 41, "h": 190, "s": 101, "w": 37, "r": 13, "d": 18, "k": 2, "n": 13, "g": 13, "q": 13, "x": 10, "z": 1, "v": 8}, "j": {"o": 1028, "e": 1055, "u": 1463, "a": 1378, "i": 413, "t": 3, "h": 8, "j": 6, "r": 11, "y": 7, "p": 3, "w": 2, "v": 1, "n": 16, "d": 9, "l": 3, "m": 4, "b": 2, "c": 5, "g": 2, "s": 3, "k": 4}, "f": {"f": 3062, "t": 1219, "a": 3561, "u": 3908, "o": 5545, "i": 7027, "e": 5162, "y": 943, "l": 4104, "r": 2832, "b": 49, "d": 40, "g": 24, "s": 318, "w": 42, "z": 6, "n": 44, "v": 2, "k": 12, "c": 39, "h": 42, "m": 45, "p": 29, "j": 8, "x": 3}, "y": {"a": 2094, "e": 1694, "s": 3655, "m": 2399, "i": 1441, "r": 2038, "c": 2270, "p": 3738, "g": 911, "l": 3861, "n": 2325, "d": 1489, "t": 2194, "x": 200, "o": 1689, "z": 222, "u": 215, "y": 9, "b": 475, "w": 311, "f": 226, "h": 210, "v": 38, "k": 83, "j": 10, "q": 5}, "m": {"a": 19645, "p": 6919, "e": 18876, "b": 4332, "i": 18111, "y": 2804, "o": 12427, "u": 4008, "s": 1851, "h": 80, "m": 3425, "r": 123, "t": 102, "l": 381, "n": 1012, "k": 36, "f": 231, "w": 92, "c": 101, "d": 92, "g": 37, "v": 79, "z": 15, "j": 19, "q": 6, "x": 1}, "p": {"e": 17219, "s": 3871, "i": 10292, "t": 4582, "o": 12574, "y": 1788, "h": 16764, "r": 14814, "a": 12541, "n": 540, "p": 3577, "u": 3814, "l": 7341, "m": 224, "j": 20, "d": 94, "x": 1, "b": 205, "c": 142, "f": 176, "w": 187, "k": 71, "g": 73, "v": 8, "z": 1, "q": 4}, "z": {"e": 6290, "z": 567, "o": 1849, "i": 2309, "a": 2438, "u": 131, "l": 265, "g": 9, "h": 15, "y": 442, "r": 11, "t": 14, "n": 12, "b": 21, "d": 21, "p": 16, "c": 16, "k": 14, "s": 15, "w": 18, "m": 15, "v": 9, "q": 4, "j": 2, "f": 3}, "q": {"u": 5763, "w": 2, "s": 5, "p": 2, "i": 18, "h": 2, "r": 6, "n": 2, "o": 4, "a": 21, "t": 8, "g": 1, "e": 6, "y": 1, "l": 2, "m": 1, "q": 4, "v": 2, "d": 2, "f": 1}}
"""

def load_markov_data():
    """
    Load Markov chain data from the embedded JSON string.
    """
    raw = json.loads(MARKOV_DATA_ENCODED)
    markov_data = defaultdict(Counter)
    for prev, counter_dict in raw.items():
        # JSON cannot use None as an object key, so None is encoded as "null"
        key = None if prev == "null" else prev
        markov_data[key] = Counter(counter_dict)
    return markov_data


def random_password(opts):
    """
    Generate and return a random password.
    """
    return "".join([choice(opts.alphabet) for _ in range(opts.length)])


def words_from_file(filename):
    """
    Read a file indicated by the string `filename` and return a list of words.
    File should contain words separated by newline.
    """
    with open(filename) as f:
        return f.read().rsplit()


def build_markov_chain(filename):
    """
    Read words from a file and build a Markov chain.
    """
    counts = defaultdict(Counter)
    for word in words_from_file(filename):
        prev = None
        for c in word:
            counts[prev][c] += 1
            prev = c
    return counts


def accumulate(iterable, func=operator.add):
    """
    Return running totals
    """
    it = iter(iterable)
    try:
        total = next(it)
    except StopIteration:
        return
    yield total
    for element in it:
        total = func(total, element)
        yield total


def choices(population, weights=None, cum_weights=None, k=1):
    """
    Return a k sized list of population elements chosen with replacement.

    If the relative weights or cumulative weights are not specified, the
    selections are made with equal probability.

    Adapted from https://github.com/python/cpython/blob/master/Lib/random.py
    """
    n = len(population)
    if cum_weights is None:
        if weights is None:
            _int = int
            return [population[randbelow(n)] for i in range(k)]
        cum_weights = list(accumulate(weights))
    elif weights is not None:
        raise TypeError("Cannot specify both weights and cumulative weights")
    if len(cum_weights) != n:
        raise ValueError("The number of weights does not match the population")
    total = cum_weights[-1]
    hi = n - 1
    return [
        population[bisect(cum_weights, randbelow(total), 0, hi)]
        for i in range(k)
    ]


def markov_password(markov_data, opts):
    """
    Generate and return a pronounceable password.
    """
    word = ""
    prev = None
    for _ in range(opts.length):
        if not markov_data[prev]:
            prev = None
        prev = choices(list(markov_data[prev].keys()),
                       list(markov_data[prev].values()))[0]
        word += prev
    return word

def sample(population, k):
    population = list(population)
    result = []
    for _ in range(k):
        i = randbelow(len(population))
        result.append(population.pop(i))
    return result


def add_password_requirement(pw, alphabet, regex, n):
    """
    If necessary, add the specified password requirement to string `pw` and
    return it.
    """
    if n > 0:
        # Get positions of matches of regex in pw
        matches = [markov_data.start()
                   for markov_data in re.finditer(regex, pw)]
        # We need to replace this many characters to meet the requirement
        k = max(n - len(matches), 0)
        # Make a list of fields to change (must be in positions which are NOT
        # matches for regex)
        change = sample(list(set(range(len(pw))) - set(matches)), k)
        # Make the replacements
        for i in change:
            pw = pw[:i] + choice(alphabet) + pw[i + 1:]
    return pw


def add_password_requirements(pw, opts):
    """
    Make any necessary modifications to the password `pw` so that it conforms to
    the password requirements specified in `opts`.
    """
    pw = add_password_requirement(
        pw, string.ascii_lowercase, REGEX_LOWERCASE, opts.minimum_lower
    )
    pw = add_password_requirement(
        pw, string.ascii_uppercase, REGEX_UPPERCASE, opts.minimum_upper
    )
    pw = add_password_requirement(
        pw, string.digits, REGEX_DIGITS, opts.minimum_digits)
    pw = add_password_requirement(
        pw, string.punctuation, REGEX_SPECIAL, opts.minimum_special
    )
    return pw


def build_markov(opts,
                 input_file=os.path.realpath(__file__),
                 output_file=os.path.realpath(__file__)):
    """
    Build Markov chain using input and output files.
    """
    # Create the data
    markov_data = build_markov_chain(opts.build_markov)

    # Convert to JSON-serializable form
    serializable = {}
    for prev, counter in markov_data.items():
        key = "null" if prev is None else prev
        serializable[key] = dict(counter)
    # Read in the script file

    with open(input_file, "r") as f:
        contents = f.read()
        # Build the markov chain and write back to script file
        contents = re.sub(
            re.compile(
                r'^MARKOV_DATA_ENCODED = """\n.*?"""',
                re.MULTILINE | re.DOTALL),
            'MARKOV_DATA_ENCODED = """\n'
            + json.dumps(serializable)
            + '\n"""',
            contents,
        )
    with open(output_file, "w") as f:
        f.write(contents)


def pronounceable(opts):
    """
    Make pronounceable passwords
    """
    markov_data = load_markov_data()
    pws = []
    for _ in range(opts.number):
        pws.append(add_password_requirements(
            markov_password(markov_data, opts), opts))
    return pws


def random(opts):
    """
    Generate random passwords.
    """
    # Make completely random passwords
    if any([opts.lower, opts.upper, opts.digits, opts.special,
            opts.characters]):
        # use only specified character sets
        opts.alphabet = ""
        if opts.lower:
            opts.alphabet += string.ascii_lowercase
        if opts.upper:
            opts.alphabet += string.ascii_uppercase
        if opts.digits:
            opts.alphabet += string.digits
        if opts.special:
            opts.alphabet += string.punctuation
        opts.alphabet += opts.characters
    elif opts.unicode:
        opts.alphabet = "".join([chr(c) for c in UNICODE_RANGE])
    else:
        # no specific character sets were specified so use the defaults
        opts.alphabet = string.digits + string.ascii_letters + \
            string.punctuation
    # Generate and print some passwords
    pws = []
    for _ in range(opts.number):
        pws.append(add_password_requirements(random_password(opts), opts))

    return pws


def parse_args():
    """
    Parse the command line args and return them in object form.
    """
    parser = argparse.ArgumentParser(
        description=" Generate random passwords in a hopefully secure manner."
    )

    parser.add_argument(
        "length", nargs="?", type=int, default=16, help="Length of password"
    )
    parser.add_argument(
        "--number", "-n", type=int, default=1,
        help="Number of passwords to generate"
    )
    parser.add_argument(
        "--pronounceable",
        "-p",
        default=False,
        action="store_true",
        help="Create human pronounceable passwords",
    )
    parser.add_argument(
        "--lower",
        "-l",
        default=False,
        action="store_true",
        help="Use lower case letters",
    )
    parser.add_argument(
        "--require-lower",
        "-L",
        default=False,
        action="store_true",
        help="Require at least one lowercase character",
    )
    parser.add_argument(
        "--upper",
        "-u",
        default=False,
        action="store_true",
        help="Use upper case letters",
    )
    parser.add_argument(
        "--require-upper",
        "-U",
        default=False,
        action="store_true",
        help="Require at least one upper character",
    )
    parser.add_argument(
        "--digits", "-d", default=False, action="store_true", help="Use digits"
    )
    parser.add_argument(
        "--require-digits",
        "-D",
        default=False,
        action="store_true",
        help="Require at least one digit character",
    )
    parser.add_argument(
        "--special",
        "-s",
        default=False,
        action="store_true",
        help="Use special characters (punctuation)",
    )
    parser.add_argument(
        "--require-special",
        "-S",
        default=False,
        action="store_true",
        help="Require at least one special character",
    )
    parser.add_argument(
        "--characters", "-c", default="", help="Specify individual characters"
    )
    parser.add_argument(
        "--unicode",
        "-z",
        default=False,
        action="store_true",
        help="Use a large unicode character set",
    )
    parser.add_argument(
        "--active-directory",
        "-a",
        default=False,
        action="store_true",
        help="""
Output passwords that exceed the default requirements in Microsoft Active
Directory environments (`-LUDS`)""",
    )
    parser.add_argument(
        "--build-markov",
        "-b",
        action="store",
        metavar="FILE",
        help="Build a markov chain using the words in FILE.",
    )

    opts = parser.parse_args()

    opts.minimum_lower = 1 if opts.require_lower or opts.active_directory \
        else 0
    opts.minimum_upper = 1 if opts.require_upper or opts.active_directory \
        else 0
    opts.minimum_digits = 1 if opts.require_digits or opts.active_directory \
        else 0
    opts.minimum_special = 1 if opts.require_special or opts.active_directory \
        else 0

    return opts


def main():
    """
    Print some passwords.
    """

    opts = parse_args()

    if opts.build_markov:
        build_markov(opts)
    elif opts.pronounceable:
        for p in pronounceable(opts):
            print(p)
    else:
        for p in random(opts):
            print(p)


if __name__ == "__main__":
    main()
