defmodule GenFST do
  @moduledoc """
  GenFST implements a generic finite state transducer with
  customizable rules expressed in a DSL.

  A finite-state transducer (FST) is a finite-state machine 
  with two memory tapes, following the terminology for Turing 
  machines: an input tape and an output tape.

  A FST will read a set of strings on the input tape and 
  generates a set of relations on the output tape. An FST 
  can be thought of as a translator or relater between strings in a set.

  In morphological parsing, an example would be inputting a string of letters 
  into the FST, the FST would then output a string of 
  [morphemes](https://en.wikipedia.org/wiki/Morphemes).

  ## Example

  Here we implement a simple morphological parser for English language. This
  morphological parser recognize different inflectional morphology of the verbs.

  ```elixir
  defmodule MorphologicalParser do
    use GenFST

    rule ["play", {"s", "^s"}]
    rule ["act", {"s", "^s"}]

  end
  assert MorphologicalParser.parse("plays") == "play^s"
  ```

  For example if we pass the third-person singluar tense of the verb _act_,
  `MorphologicalParser.parse("acts")`, the morphological parser will output
  `"act^s"`. The semantic of rule definition is given at `rule/1`.

  """

  defmacro __using__(_opts) do
    quote location: :keep do 
      @rules []
      @before_compile GenFST

      import GenFST
    end
  end

  @doc """
  Define a transducing rule.

  A transducing rule is a `List` of `String | {String, String}`.

  For example: `rule ["play", {"s", "^s"}]` means outputing `"play"` verbatimly,
  and transform `"s"` into `"^s"`. If a finite state transducer built with
  this rule is fed with string `"plays"`, then the output will be `"play^s"`
  """
  defmacro rule(r) do
    quote do 
      @rules [unquote(r) | @rules]
    end
  end

  @doc false
  def process_rule(fst_graph, rule) do
    {fst_graph, _, _} =  Enum.reduce(rule, {fst_graph, :root, ""}, fn(rule_item, {fst_graph, vertex, prefix}) ->
      process_rule_item(fst_graph, vertex, prefix, rule_item)
    end)
    fst_graph
  end

  @doc false
  def process_rule_item(fst_graph, vertex, prefix, rule_item) do
    if is_binary rule_item do
      Enum.reduce(String.codepoints(rule_item), {fst_graph, vertex, prefix}, fn(char, {fst_graph, vertex, prefix}) -> 
        process_rule_item_char(fst_graph, vertex, prefix, {char, char})
      end)
    else
      {from, to} = rule_item
      from_len = String.length from
      to_len = String.length to
      cond do
        from_len > to_len ->
          h_from = String.slice(from, 0, to_len)
          h_to = String.slice(from, 0, to_len)
          h_cps_pairs = Enum.zip(String.codepoints(h_from), String.codepoints(h_to))

          {fst_graph, vertex, prefix} = Enum.reduce(h_cps_pairs,
                      {fst_graph, vertex, prefix}, 
                      fn({from_cp, to_cp}, {fst_graph, vertex, prefix}) -> 
            process_rule_item_char(fst_graph, vertex, prefix, {from_cp, to_cp})
          end)

          t_from_cps = String.codepoints(String.slice(from, to_len, from_len))
          {fst_graph, vertex, prefix} = Enum.reduce(t_from_cps,
                      {fst_graph, vertex, prefix}, 
                      fn(t_from_cp, {fst_graph, vertex, prefix}) -> 
            process_rule_item_char(fst_graph, vertex, prefix, {t_from_cp, ""})
          end)

        from_len < to_len -> 
          h_from = String.slice(from, 0, from_len - 1)
          h_to = String.slice(to, 0, from_len - 1)
          h_cps_pairs = Enum.zip(String.codepoints(h_from), String.codepoints(h_to))
          {fst_graph, vertex, prefix} = Enum.reduce(h_cps_pairs,
                      {fst_graph, vertex, prefix}, 
                      fn({from_cp, to_cp}, {fst_graph, vertex, prefix}) -> 
            process_rule_item_char(fst_graph, vertex, prefix, {from_cp, to_cp})
          end)
          process_rule_item_char(fst_graph, vertex, prefix, {
            String.slice(from, from_len - 1, from_len),
            String.slice(to, from_len - 1, to_len)
          })

        from_len == to_len ->
          cps_pairs = Enum.zip(String.codepoints(from), String.codepoints(to))
          Enum.reduce(cps_pairs,
                      {fst_graph, vertex, prefix}, 
                      fn({from_cp, to_cp}, {fst_graph, vertex, prefix}) -> 
            process_rule_item_char(fst_graph, vertex, prefix, {from_cp, to_cp})
          end)

      end
    end
  end

  @doc false
  def process_rule_item_char(fst_graph, vertex, prefix, {from, to}) do
    new_prefix = prefix <> from
    target_v = String.to_atom(new_prefix)
    edge = Graph.Edge.new(vertex, target_v, label: {from, to})
    fst_graph = fst_graph
    |> Graph.add_edge(edge)
    {fst_graph, target_v, new_prefix}
  end

  # Invoked right before target module compiled, used to inject
  # GenStateMachine event handlers.
  @doc false
  defmacro __before_compile__(_env) do
    quote location: :keep do
      @fst_graph Enum.reduce(@rules, Graph.new(), fn(rule, fst_graph) -> 
        fst_graph |> process_rule(rule)
      end)

      def transduce(alphabet, state, transduced) do
        edge = Enum.find(Graph.out_edges(@fst_graph, state), nil, fn(edge) -> 
          {e_from, e_to} = edge.label
          e_from == alphabet
        end)

        transduced = transduced <> elem(edge.label, 1)
        {edge.v2, transduced}
      end

      @initial_state_data {:root, ""}
      def parse(input) do
        input_cps = String.codepoints(input)
        {final_state, transduced} = Enum.reduce(input_cps, @initial_state_data, 
          fn(a, {state, transduced}) -> 
          transduce(a, state, transduced)
        end)
        transduced
      end
    end
  end
end