greedy regexp matching

test.js

const getFirstSub = str => {
  if (str.length == 0) {
    return {}
  }
  let subLength = 1
  if (str[1] === '*') {
    subLength = 2
  }

  const sub = str.substr(0, subLength)
  const rest = str.substr(subLength, str.length)
  return {sub, rest}
}

const getAllSubs = str => {
  const result = []
  let mutableStr = str
  while(true) {
    const obj = getFirstSub(mutableStr)
    if (obj.sub) {
      result.push(obj.sub)
      mutableStr = obj.rest
    } else {
      break
    }
  }
  return result
}

const matchAsterisk = (str, sub) => {
  const needle = sub[0]
  let rest = str
  while (needle === '.' || rest[0] === needle) {
    if (rest.length === 0) { break }
    rest = rest.substr(1, rest.length)
  }
  return {result: true, rest}
}

const matchSub = (str, sub) => {
  if (sub.length > 1) {
    return matchAsterisk(str, sub)
  }

  const ret = {}
  if (str.length === 0) {
    return {result: false, rest: ''}
  }
  if (sub === '.') {
    ret.result = true
    ret.rest = str.substr(1, str.length)
  } else {
    ret.result = str[0] === sub
    ret.rest = str.substr(1, str.length)
  }

  return ret
}

const match = (str, pattern) => {
  const subs = getAllSubs(pattern)
  let mutablePattern = str

  for(let i=0; i<subs.length; i++) {
    let sub = subs[i]
    const ret = matchSub(mutablePattern, sub)
    if (ret.result === false) {
      return false
    } else {
      mutablePattern = ret.rest
    }
  }
  return true
}

describe('regexp', () => {
  it('match(', () => {
    let result = match('abc', 'ab.')
    expect(result).toEqual(true)

    result = match('abc', 'ac.')
    expect(result).toEqual(false)

    result = match('a', 'ac.')
    expect(result).toEqual(false)

    result = match('', '.')
    expect(result).toEqual(false)

    result = match('abbcd', 'ab*c.')
    expect(result).toEqual(true)

    result = match('abbdd', 'ab*c.')
    expect(result).toEqual(false)
  })

  it('matchSub()', () => {
    let result = matchSub('abcd', 'a')
    expect(result).toEqual({result: true, rest: 'bcd'})

    result = matchSub('abcd', 'b')
    expect(result).toEqual({result: false, rest: 'bcd'})

    result = matchSub('abcd', '.')
    expect(result).toEqual({result: true, rest: 'bcd'})

    result = matchSub('', '.')
    expect(result).toEqual({result: false, rest: ''})

    result = matchSub('a', 'b')
    expect(result).toEqual({result: false, rest: ''})
  })

  it('matchAsterisk()', () => {
    let result = matchSub('aaaa', 'a*')
    expect(result).toEqual({result: true, rest: ''})

    result = matchSub('aabcd', 'a*')
    expect(result).toEqual({result: true, rest: 'bcd'})

    result = matchSub('bcd', 'a*')
    expect(result).toEqual({result: true, rest: 'bcd'})

    result = matchSub('', 'a*')
    expect(result).toEqual({result: true, rest: ''})

    result = matchSub('asdf', '.*')
    expect(result).toEqual({result: true, rest: ''})

    result = matchSub('', '.*')
    expect(result).toEqual({result: true, rest: ''})
  })

  it('getFirstSub( works', () => {
    let result = getFirstSub('abcd')
    expect(result).toEqual({sub: 'a', rest: 'bcd'})

    result = getFirstSub('.*')
    expect(result).toEqual({sub: '.*', rest: ''})
  })

  it('getSubs works', () => {
    const result = getAllSubs('abcd.*')
    expect(result).toEqual(['a', 'b', 'c', 'd', '.*'])
  })
})