test = require 'tape'
matching = require '../src/matching'
adjacency_graphs = require '../src/adjacency_graphs'

# takes a pattern and list of prefixes/suffixes
# returns a bunch of variants of that pattern embedded
# with each possible prefix/suffix combination, including no prefix/suffix
# returns a list of triplets [variant, i, j] where [i,j] is the start/end of the pattern, inclusive
genpws = (pattern, prefixes, suffixes) ->
  prefixes = prefixes.slice()
  suffixes = suffixes.slice()
  for lst in [prefixes, suffixes]
    lst.unshift '' if '' not in lst
  result = []
  for prefix in prefixes
    for suffix in suffixes
      [i, j] = [prefix.length, prefix.length + pattern.length - 1]
      result.push [prefix + pattern + suffix, i, j]
  result

check_matches = (prefix, t, matches, pattern_names, patterns, ijs, props) ->
  if typeof pattern_names is "string"
    # shortcut: if checking for a list of the same type of patterns,
    # allow passing a string 'pat' instead of array ['pat', 'pat', ...]
    pattern_names = (pattern_names for i in [0...patterns.length])

  is_equal_len_args = pattern_names.length == patterns.length == ijs.length
  for prop, lst of props
    # props is structured as: keys that points to list of values
    is_equal_len_args = is_equal_len_args and (lst.length == patterns.length)
  throw 'unequal argument lists to check_matches' unless is_equal_len_args

  msg = "#{prefix}: matches.length == #{patterns.length}"
  t.equal matches.length, patterns.length, msg
  for k in [0...patterns.length]
    match = matches[k]
    pattern_name = pattern_names[k]
    pattern = patterns[k]
    [i, j] = ijs[k]
    msg = "#{prefix}: matches[#{k}].pattern == '#{pattern_name}'"
    t.equal match.pattern, pattern_name, msg
    msg = "#{prefix}: matches[#{k}] should have [i, j] of [#{i}, #{j}]"
    t.deepEqual [match.i, match.j], [i, j], msg
    msg = "#{prefix}: matches[#{k}].token == '#{pattern}'"
    t.equal match.token, pattern, msg
    for prop_name, prop_list of props
      prop_msg = prop_list[k]
      prop_msg = "'#{prop_msg}'" if typeof(prop_msg) == 'string'
      msg = "#{prefix}: matches[#{k}].#{prop_name} == #{prop_msg}"
      t.deepEqual match[prop_name], prop_list[k], msg


test 'matching utils', (t) ->
  t.ok matching.empty([]), ".empty returns true for an empty array"
  t.ok matching.empty({}), ".empty returns true for an empty object"
  for obj in [
    [1]
    [1, 2]
    [[]]
    {a: 1}
    {0: {}}
    ]
    t.notOk matching.empty(obj), ".empty returns false for non-empty objects and arrays"

  lst = []
  matching.extend lst, []
  t.deepEqual lst, [], "extending an empty list with an empty list leaves it empty"
  matching.extend lst, [1]
  t.deepEqual lst, [1], "extending an empty list with another makes it equal to the other"
  matching.extend lst, [2, 3]
  t.deepEqual lst, [1, 2, 3], "extending a list with another adds each of the other's elements"
  [lst1, lst2] = [[1], [2]]
  matching.extend lst1, lst2
  t.deepEqual lst2, [2], "extending a list by another doesn't affect the other"

  chr_map = {a: 'A', b: 'B'}
  for [string, map, result] in [
    ['a',    chr_map, 'A']
    ['c',    chr_map, 'c']
    ['ab',   chr_map, 'AB']
    ['abc',  chr_map, 'ABc']
    ['aa',   chr_map, 'AA']
    ['abab', chr_map, 'ABAB']
    ['',     chr_map, '']
    ['',     {},      '']
    ['abc',  {},      'abc']
    ]
    msg = "translates '#{string}' to '#{result}' with provided charmap"
    t.equal matching.translate(string, map), result, msg

  for [[dividend, divisor], remainder] in [
    [[ 0, 1],  0]
    [[ 1, 1],  0]
    [[-1, 1],  0]
    [[ 5, 5],  0]
    [[ 3, 5],  3]
    [[-1, 5],  4]
    [[-5, 5],  0]
    [[ 6, 5],  1]
    ]
    msg = "mod(#{dividend}, #{divisor}) == #{remainder}"
    t.equal matching.mod(dividend, divisor), remainder, msg

  t.deepEqual matching.sorted([]), [], "sorting an empty list leaves it empty"
  [m1, m2, m3, m4, m5, m6] = [
    {i: 5, j: 5}
    {i: 6, j: 7}
    {i: 2, j: 5}
    {i: 0, j: 0}
    {i: 2, j: 3}
    {i: 0, j: 3}
  ]
  msg = "matches are sorted on i index primary, j secondary"
  t.deepEqual matching.sorted([m1, m2, m3, m4, m5, m6]), [m4, m6, m5, m3, m1, m2], msg
  t.end()


test 'dictionary matching', (t) ->
  dm = (pw) -> matching.dictionary_match pw, test_dicts
  test_dicts =
    d1:
      motherboard: 1
      mother: 2
      board: 3
      abcd: 4
      cdef: 5
    d2:
      'z': 1
      '8': 2
      '99': 3
      '$': 4
      'asdf1234&*': 5

  matches = dm 'motherboard'
  patterns = ['mother', 'motherboard', 'board']
  msg = "matches words that contain other words"
  check_matches msg, t, matches, 'dictionary', patterns, [[0,5], [0,10], [6,10]],
    matched_word: ['mother', 'motherboard', 'board']
    rank: [2, 1, 3]
    dictionary_name: ['d1', 'd1', 'd1']

  matches = dm 'abcdef'
  patterns = ['abcd', 'cdef']
  msg = "matches multiple words when they overlap"
  check_matches msg, t, matches, 'dictionary', patterns, [[0,3], [2,5]],
    matched_word: ['abcd', 'cdef']
    rank: [4, 5]
    dictionary_name: ['d1', 'd1']

  matches = dm 'BoaRdZ'
  patterns = ['BoaRd', 'Z']
  msg = "ignores uppercasing"
  check_matches msg, t, matches, 'dictionary', patterns, [[0,4], [5,5]],
    matched_word: ['board', 'z']
    rank: [3, 1]
    dictionary_name: ['d1', 'd2']

  prefixes = ['q', '%%']
  suffixes = ['%', 'qq']
  word = 'asdf1234&*'
  for [password, i, j] in genpws word, prefixes, suffixes
    matches = dm password
    msg = "identifies words surrounded by non-words"
    check_matches msg, t, matches, 'dictionary', [word], [[i,j]],
      matched_word: [word]
      rank: [5]
      dictionary_name: ['d2']

  for name, dict of test_dicts
    for word, rank of dict
      continue if word is 'motherboard' # skip words that contain others
      matches = dm word
      msg = "matches against all words in provided dictionaries"
      check_matches msg, t, matches, 'dictionary', [word], [[0, word.length - 1]],
        matched_word: [word]
        rank: [rank]
        dictionary_name: [name]

  # test the default dictionaries
  matches = matching.dictionary_match 'wow'
  patterns = ['wow']
  ijs = [[0,2]]
  msg = "default dictionaries"
  check_matches msg, t, matches, 'dictionary', patterns, ijs,
    matched_word: patterns
    rank: [322]
    dictionary_name: ['us_tv_and_film']

  matching.set_user_input_dictionary ['foo', 'bar']
  matches = matching.dictionary_match 'foobar'
  matches = matches.filter (match) ->
    match.dictionary_name == 'user_inputs'
  msg = "matches with provided user input dictionary"
  check_matches msg, t, matches, 'dictionary', ['foo', 'bar'], [[0, 2], [3, 5]],
    matched_word: ['foo', 'bar']
    rank: [1, 2]
  t.end()

test 'reverse dictionary matching', (t) ->
  test_dicts =
    d1:
      123: 1
      321: 2
      456: 3
      654: 4
  password = '0123456789'
  matches = matching.reverse_dictionary_match password, test_dicts
  msg = 'matches against reversed words'
  check_matches msg, t, matches, 'dictionary', ['123', '456'], [[1, 3], [4, 6]],
    matched_word: ['321', '654']
    reversed: [true, true]
    dictionary_name: ['d1', 'd1']
    rank: [2, 4]
  t.end()


test 'l33t matching', (t) ->
  test_table =
    a: ['4', '@']
    c: ['(', '{', '[', '<']
    g: ['6', '9']
    o: ['0']

  for [pw, expected] in [
    [ '', {} ]
    [ 'abcdefgo123578!#$&*)]}>', {} ]
    [ 'a',     {} ]
    [ '4',     {'a': ['4']} ]
    [ '4@',    {'a': ['4','@']} ]
    [ '4({60', {'a': ['4'], 'c': ['(','{'], 'g': ['6'], 'o': ['0']} ]
    ]
    msg = "reduces l33t table to only the substitutions that a password might be employing"
    t.deepEquals matching.relevant_l33t_subtable(pw, test_table), expected, msg

  for [table, subs] in [
    [ {},                        [{}] ]
    [ {a: ['@']},                [{'@': 'a'}] ]
    [ {a: ['@','4']},            [{'@': 'a'}, {'4': 'a'}] ]
    [ {a: ['@','4'], c: ['(']},  [{'@': 'a', '(': 'c' }, {'4': 'a', '(': 'c'}] ]
    ]
    msg = "enumerates the different sets of l33t substitutions a password might be using"
    t.deepEquals matching.enumerate_l33t_subs(table), subs, msg

  lm = (pw) -> matching.l33t_match pw, dicts, test_table
  dicts =
    words:
      aac: 1
      password: 3
      paassword: 4
      asdf0: 5
    words2:
      cgo: 1

  t.deepEquals lm(''), [], "doesn't match ''"
  t.deepEquals lm('password'), [], "doesn't match pure dictionary words"
  for [password, pattern, word, dictionary_name, rank, ij, sub] in [
    [ 'p4ssword',    'p4ssword', 'password', 'words',  3, [0,7],  {'4': 'a'} ]
    [ 'p@ssw0rd',    'p@ssw0rd', 'password', 'words',  3, [0,7],  {'@': 'a', '0': 'o'} ]
    [ 'aSdfO{G0asDfO', '{G0',    'cgo',      'words2', 1, [5, 7], {'{': 'c', '0': 'o'} ]
    ]
    msg = "matches against common l33t substitutions"
    check_matches msg, t, lm(password), 'dictionary', [pattern], [ij],
      l33t: [true]
      sub: [sub]
      matched_word: [word]
      rank: [rank]
      dictionary_name: [dictionary_name]

  matches = lm '@a(go{G0'
  msg = "matches against overlapping l33t patterns"
  check_matches msg, t, matches, 'dictionary', ['@a(', '(go', '{G0'], [[0,2], [2,4], [5,7]],
    l33t: [true, true, true]
    sub: [{'@': 'a', '(': 'c'}, {'(': 'c'}, {'{': 'c', '0': 'o'}]
    matched_word: ['aac', 'cgo', 'cgo']
    rank: [1, 1, 1]
    dictionary_name: ['words', 'words2', 'words2']

  msg = "doesn't match when multiple l33t substitutions are needed for the same letter"
  t.deepEqual lm('p4@ssword'), [], msg

  msg = "doesn't match single-character l33ted words"
  matches = matching.l33t_match '4 1 @'
  t.deepEqual matches, [], msg

  # known issue: subsets of substitutions aren't tried.
  # for long inputs, trying every subset of every possible substitution could quickly get large,
  # but there might be a performant way to fix.
  # (so in this example: {'4': a, '0': 'o'} is detected as a possible sub,
  # but the subset {'4': 'a'} isn't tried, missing the match for asdf0.)
  # TODO: consider partially fixing by trying all subsets of size 1 and maybe 2
  msg = "doesn't match with subsets of possible l33t substitutions"
  t.deepEqual lm('4sdf0'), [], msg
  t.end()


test 'spatial matching', (t) ->
  for password in ['', '/', 'qw', '*/']
    msg = "doesn't match 1- and 2-character spatial patterns"
    t.deepEqual matching.spatial_match(password), [], msg

  # for testing, make a subgraph that contains a single keyboard
  _graphs = qwerty: adjacency_graphs.qwerty
  pattern = '6tfGHJ'
  matches = matching.spatial_match "rz!#{pattern}%z", _graphs
  msg = "matches against spatial patterns surrounded by non-spatial patterns"
  check_matches msg, t, matches, 'spatial', [pattern], [[3, 3 + pattern.length - 1]],
    graph: ['qwerty']
    turns: [2]
    shifted_count: [3]

  for [pattern, keyboard, turns, shifts] in [
    [ '12345',        'qwerty',     1, 0 ]
    [ '@WSX',         'qwerty',     1, 4 ]
    [ '6tfGHJ',       'qwerty',     2, 3 ]
    [ 'hGFd',         'qwerty',     1, 2 ]
    [ '/;p09876yhn',  'qwerty',     3, 0 ]
    [ 'Xdr%',         'qwerty',     1, 2 ]
    [ '159-',         'keypad',     1, 0 ]
    [ '*84',          'keypad',     1, 0 ]
    [ '/8520',        'keypad',     1, 0 ]
    [ '369',          'keypad',     1, 0 ]
    [ '/963.',        'mac_keypad', 1, 0 ]
    [ '*-632.0214',   'mac_keypad', 9, 0 ]
    [ 'aoEP%yIxkjq:', 'dvorak',     4, 5 ]
    [ ';qoaOQ:Aoq;a', 'dvorak',    11, 4 ]
    ]
    _graphs = {}
    _graphs[keyboard] = adjacency_graphs[keyboard]
    matches = matching.spatial_match pattern, _graphs
    msg = "matches '#{pattern}' as a #{keyboard} pattern"
    check_matches msg, t, matches, 'spatial', [pattern], [[0, pattern.length - 1]],
      graph: [keyboard]
      turns: [turns]
      shifted_count: [shifts]
  t.end()

test 'sequence matching', (t) ->
  for password in ['', 'a', '1']
    msg = "doesn't match length-#{password.length} sequences"
    t.deepEqual matching.sequence_match(password), [], msg

  matches = matching.sequence_match 'abcbabc'
  msg = "matches overlapping patterns"
  check_matches msg, t, matches, 'sequence', ['abc', 'cba', 'abc'], [[0, 2], [2, 4], [4, 6]],
    ascending: [true, false, true]

  prefixes = ['!', '22']
  suffixes = ['!', '22']
  pattern = 'jihg'
  for [password, i, j] in genpws pattern, prefixes, suffixes
    matches = matching.sequence_match password
    msg = "matches embedded sequence patterns #{password}"
    check_matches msg, t, matches, 'sequence', [pattern], [[i, j]],
      sequence_name: ['lower']
      ascending: [false]

  for [pattern, name, is_ascending] in [
    ['ABC',   'upper',  true]
    ['CBA',   'upper',  false]
    ['PQR',   'upper',  true]
    ['RQP',   'upper',  false]
    ['XYZ',   'upper',  true]
    ['ZYX',   'upper',  false]
    ['abcd',  'lower',  true]
    ['dcba',  'lower',  false]
    ['jihg',  'lower',  false]
    ['wxyz',  'lower',  true]
    ['zxvt',  'lower',  false]
    ['0369', 'digits', true]
    ['97531', 'digits', false]
    ]
    matches = matching.sequence_match pattern
    msg = "matches '#{pattern}' as a '#{name}' sequence"
    check_matches msg, t, matches, 'sequence', [pattern], [[0, pattern.length - 1]],
      sequence_name: [name]
      ascending: [is_ascending]
  t.end()


test 'repeat matching', (t) ->
  for password in ['', '#']
    msg = "doesn't match length-#{password.length} repeat patterns"
    t.deepEqual matching.repeat_match(password), [], msg

  # test single-character repeats
  prefixes = ['@', 'y4@']
  suffixes = ['u', 'u%7']
  pattern = '&&&&&'
  for [password, i, j] in genpws pattern, prefixes, suffixes
    matches = matching.repeat_match password
    msg = "matches embedded repeat patterns"
    check_matches msg, t, matches, 'repeat', [pattern], [[i, j]],
      base_token: ['&']

  for length in [3, 12]
    for chr in ['a', 'Z', '4', '&']
      pattern = Array(length + 1).join(chr)
      matches = matching.repeat_match pattern
      msg = "matches repeats with base character '#{chr}'"
      check_matches msg, t, matches, 'repeat', [pattern], [[0, pattern.length - 1]],
        base_token: [chr]

  matches = matching.repeat_match 'BBB1111aaaaa@@@@@@'
  patterns = ['BBB','1111','aaaaa','@@@@@@']
  msg = 'matches multiple adjacent repeats'
  check_matches msg, t, matches, 'repeat', patterns, [[0, 2],[3, 6],[7, 11],[12, 17]],
    base_token: ['B', '1', 'a', '@']

  matches = matching.repeat_match '2818BBBbzsdf1111@*&@!aaaaaEUDA@@@@@@1729'
  msg = 'matches multiple repeats with non-repeats in-between'
  check_matches msg, t, matches, 'repeat', patterns, [[4, 6],[12, 15],[21, 25],[30, 35]],
    base_token: ['B', '1', 'a', '@']

  # test multi-character repeats
  pattern = 'abab'
  matches = matching.repeat_match pattern
  msg = 'matches multi-character repeat pattern'
  check_matches msg, t, matches, 'repeat', [pattern], [[0, pattern.length - 1]],
    base_token: ['ab']

  pattern = 'aabaab'
  matches = matching.repeat_match pattern
  msg = 'matches aabaab as a repeat instead of the aa prefix'
  check_matches msg, t, matches, 'repeat', [pattern], [[0, pattern.length - 1]],
    base_token: ['aab']

  pattern = 'abababab'
  matches = matching.repeat_match pattern
  msg = 'identifies ab as repeat string, even though abab is also repeated'
  check_matches msg, t, matches, 'repeat', [pattern], [[0, pattern.length - 1]],
    base_token: ['ab']
  t.end()


test 'regex matching', (t) ->
  for [pattern, name] in [
    ['1922', 'recent_year']
    ['2017', 'recent_year']
    ]
    matches = matching.regex_match pattern
    msg = "matches #{pattern} as a #{name} pattern"
    check_matches msg, t, matches, 'regex', [pattern], [[0, pattern.length - 1]],
      regex_name: [name]
  t.end()


test 'date matching', (t) ->
  for sep in ['', ' ', '-', '/', '\\', '_', '.']
    password = "13#{sep}2#{sep}1921"
    matches = matching.date_match password
    msg = "matches dates that use '#{sep}' as a separator"
    check_matches msg, t, matches, 'date', [password], [[0, password.length - 1]],
      separator: [sep]
      year: [1921]
      month: [2]
      day: [13]

  for order in ['mdy', 'dmy', 'ymd', 'ydm']
    [d,m,y] = [8,8,88]
    password = order
      .replace 'y', y
      .replace 'm', m
      .replace 'd', d
    matches = matching.date_match password
    msg = "matches dates with '#{order}' format"
    check_matches msg, t, matches, 'date', [password], [[0, password.length - 1]],
      separator: ['']
      year: [1988]
      month: [8]
      day: [8]

  password = '111504'
  matches = matching.date_match password
  msg = "matches the date with year closest to REFERENCE_YEAR when ambiguous"
  check_matches msg, t, matches, 'date', [password], [[0, password.length - 1]],
    separator: ['']
    year: [2004] # picks '04' -> 2004 as year, not '1504'
    month: [11]
    day: [15]

  for [day, month, year] in [
    [1,  1,  1999]
    [11, 8,  2000]
    [9,  12, 2005]
    [22, 11, 1551]
    ]
    password = "#{year}#{month}#{day}"
    matches = matching.date_match password
    msg = "matches #{password}"
    check_matches msg, t, matches, 'date', [password], [[0, password.length - 1]],
      separator: ['']
      year: [year]
    password = "#{year}.#{month}.#{day}"
    matches = matching.date_match password
    msg = "matches #{password}"
    check_matches msg, t, matches, 'date', [password], [[0, password.length - 1]],
      separator: ['.']
      year: [year]

  password = "02/02/02"
  matches = matching.date_match password
  msg = "matches zero-padded dates"
  check_matches msg, t, matches, 'date', [password], [[0, password.length - 1]],
    separator: ['/']
    year: [2002]
    month: [2]
    day: [2]

  prefixes = ['a', 'ab']
  suffixes = ['!']
  pattern = '1/1/91'
  for [password, i, j] in genpws pattern, prefixes, suffixes
    matches = matching.date_match password
    msg = "matches embedded dates"
    check_matches msg, t, matches, 'date', [pattern], [[i, j]],
      year: [1991]
      month: [1]
      day: [1]

  matches = matching.date_match '12/20/1991.12.20'
  msg = "matches overlapping dates"
  check_matches msg, t, matches, 'date', ['12/20/1991', '1991.12.20'], [[0, 9], [6,15]],
    separator: ['/', '.']
    year: [1991, 1991]
    month: [12, 12]
    day: [20, 20]

  matches = matching.date_match '912/20/919'
  msg = "matches dates padded by non-ambiguous digits"
  check_matches msg, t, matches, 'date', ['12/20/91'], [[1, 8]],
    separator: ['/']
    year: [1991]
    month: [12]
    day: [20]
  t.end()


test 'omnimatch', (t) ->
  t.deepEquals matching.omnimatch(''), [], "doesn't match ''"
  password = 'r0sebudmaelstrom11/20/91aaaa'
  matches = matching.omnimatch password
  for [pattern_name, [i, j]] in [
    [ 'dictionary',  [0, 6] ]
    [ 'dictionary',  [7, 15] ]
    [ 'date',        [16, 23] ]
    [ 'repeat',      [24, 27] ]
    ]
    included = false
    for match in matches
      included = true if match.i == i and match.j == j and match.pattern == pattern_name
    msg = "for #{password}, matches a #{pattern_name} pattern at [#{i}, #{j}]"
    t.ok included, msg
  t.end()