# This file is part of Nit Language ( http://nitlanguage.org ).
#
# Copyright 2008 Etienne M. Gagnon <egagnon@j-meg.com>
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

package glob

{ A glob is a string pattern where:
   "*" is 0 or more character except "/" (cannot be adjacent to another "*")
   "**/" is 0 or more directory levels (must be preceded by "/" or the start)
   "?" : any character except "/"

Examples:

   "**/*.prm" => any *.prm file in current directory or below
   "/**/*.nit" => any *.nit file in the entire file system
   "src/**/*.bak" => any *.bak file in the src subdirectory
   "a**/" => invalid glob (instead, you might want to write "a*/**/")
   "a?*/" => any direct subdirectory that starts with an "a",
             and is at least 2 characters long

Usage

  printn("toto".match_glob("t*o")) # prints => true
}#

class Glob

  # class that encapsulates a glob pattern

  var _chars = new Array[GlobChar]

    # the glob-chars of the pattern

  var _string : String
    delegate to_s

    # cached string representation

  init(pattern: String)
    with error(message: String)
      is final

    # contructor that expects the glob is a string

    # calls error when the glob string is invalid

  do
    _string = string

    if not pattern.valid_glob then
      error("invalid glob pattern")
    end

    var star_seen = false
    for c in pattern.chars do
      if star_seen then
        if c == '*' then
          _chars.add(dstar)
        else
          _chars.add('*')
          _chars.add(c)
        end

        star_seen = false

      else if c == '*' then
        star_seen = true

      else
        _chars.add(c)
      end
    end
  end

  fun match(string: String): boolean
  do
    var pat_pos = new GlobPosition(_chars)
    var str_pos = new StringPosition(string.chars)

    pat_pos.match(str_pos)
    on success do return true

    return false
  end
end

redef String

  fun match_glob(pattern: String): Bool
    with error(message: String)
      is final

    # returns true if self matches the given glob pattern

    # calls error when the glob pattern is invalid

  do
    var pat = new Glob(pattern)
    on error(message) do error(message)

    return pat.match(self)
  end

  fun valid_glob: Bool
    is private

    # returns true if self is a valid glob

  do
    var state = state0

    for c in chars do
      state = state.target(c.to_symbol)
      if state == null then return false
    end

    return state.accept
  end
end

redef Char
  special GlobChar

  # Char has a new super class

  fun to_symbol: Symbol
    is private

    # converts self into a Symbol

  do
    if self == '/' then return slash
    if self == '*' then return star
    if self == '?' then return qmark
    return other
  end
end

class GlobChar
  is private
  is universal

  # super class of Char, which has an additional constant for '**'

  const dstar

    # the constant for '**'

end

class Position
  is private

  # class that encapsulate a position

  var _pos: Int = 0

  fun next do _pos += 1
  fun prev do _pos -= 1
end

class GlobPosition
  special Position
  is private

  # class that encapsulate a position in a pattern

  var _chars: Array[GlobChar]
end

class StringPosition
  special Position
  is private

  # class that encapsulate a position in a string

  var _chars: Array[Char]

  fun match(pattern: GlobPosition)
    with success
      is final

    # match the rest of this string with the rest of the given pattern

    # calls success when there is a match

    # the implemented algorithm does a recursive exhaustive search
    # until a match is found.

  do
    if _pos == _chars.len then
      # end of string

      if pattern._pos == pattern._chars.len then success

      # not end of pattern

      var pc = pattern._chars[pattern._pos]
      if pc == '*' or pc == dstar or pc == '/' then
        pattern.next
        match(pattern)
        pattern.prev
      end

    else if pattern._pos != pattern._chars.len then
      # not end of pattern

      var sc = _chars[_pos]
      var pc = pattern._chars[pattern._pos]
      if pc == dstar then
        if sc == '/' then
          pattern.next
          match(pattern)
          pattern.prev
        else
          next
          match(pattern)
          prev
        end

      else if pc == '*' then
        pattern.next
        match(pattern)
        pattern.prev
        next
        match(pattern)
        prev

      else if pc == '?' or sc == pc then
        pattern.next
        next
        match(pattern)
        prev
        pattern.prev
      end
    end
  end
end

#
# Automaton for Glob validation
#

class State
  is private
  is universal

  # automaton state class

  const state0, state1, state2, state3, state4, state5, state6

    # states of the automaton

  fun target(symbol: Symbol): nullable State

    # returns the target state, given a symbol

  case state0 do return symbol.state0_target
  case state1 do return symbol.state1_target
  case state2 do return symbol.state2_target
  case state3 do return symbol.state3_target
  case state4 do return symbol.state4_target
  case state5 do return symbol.state5_target
  case state6 do return symbol.state6_target
  default do abort

  fun accept: Bool

    # returns true if self is an accept state

  case state5 do return false
  default do return true
end

class Symbol
  is private
  is universal

  # automaton symbol class

  const slash, star, qmark, other

  fun state0_target: nullable State

    # returns the target of state0 (start)

  case slash do return state1
  case star do return state2
  case qmark do return state3
  case other do return state4
  default do return null

  fun state1_target: nullable State

    # returns the target of state1 (".../")

  case star do return state2
  case qmark do return state3
  case other do return state4
  default do return null

  fun state2_target: nullable State

    # returns the target of state2 (".../*")

  case slash do return state1
  case star do return state5
  case qmark do return state3
  case other do return state4
  default do return null

  fun state3_target: nullable State

    # returns the target of state3 ("...?")

  case slash do return state1
  case star do return state6
  case qmark do return state3
  case other do return state4
  default do return null

  fun state4_target: nullable State

    # returns the target of state4 ("...o")

  case slash do return state1
  case star do return state6
  case qmark do return state3
  case other do return state4
  default do return null

  fun state5_target: nullable State

    # returns the target of state5 (".../**")

  case slash do return state1
  default do return null

  fun state6_target: nullable State

    # returns the target of state6 ("...o*" or "...?*")

  case slash do return state1
  case qmark do return state3
  case other do return state4
  default do return null
end