/*  CSci 658, Software Language Engineering
    Scala Combinator-based Parser and AST Builder 
    Custom External State Machine DSL (Secret Panel)
    H. Conrad Cunningham

1234567890123456789012345678901234567890123456789012345678901234567890

2009-04-28: (V1) Original 
2009-05-03: (V2b) Documentation and other improvements.  
2009-05-13: (V2c) Minor Scala programming style changes.  
2018-02-02: (V3) Replaced parse by parseAll in test.
            Modified StateMachineParserASTBuilder methods machine
            and afterreset to eliminate compiler warning.
            Added StateMachineBuilder companion object.
            Updated comments. Created compile script.

This is an implementation of Martin Fowler's Custom External State
Machine DSL (Secret Panel) that uses the Scala parser combinator
library.  It utilizes Fowler's Syntax-Directed Translation and Tree
Construction DSL patterns to build a full abstract syntax tree (AST)
of the input.

Note: This is the program author's first significant use of the Scala
parser combinator library, so the construction of grammar and parser
involved quite a bit of trial and error. It need to be cleaned up.

This program uses two phases.  First, the parser reads the input and
builds the AST.  It applies transformation functions to the output
returned by the parsers to build a tree consisting of ASTNode objects.
Second, the program walks the AST and populates the State Machine
Semantic Model appropriately.

This is new work by the program author that does not use Fowler's
code from his book, except it uses the State Machine Semantic Model
constructed from his code.  In its present state, it may not make use
of Scala features particularly well.  So far, error checking and
program testing are minimal.

The Custom External DSL is defined in the chapter "Tree Construction" 
of Fowler's book Domain-Specific Languages.

Below is Fowler's example input file from the Tree Construction
chapter of the DSL book.  Note that it differs slightly from that used
for Fowler''s Delimiter-Directed Translation chapter example (and this
author's Scala example)--the actions are enclosed in braces.  (The
example input below also appears in Fowler's "An Introductory Example"
chapter.

events
  doorClosed  D1CL
  drawOpened  D2OP
  lightOn     L1ON
  doorOpened  D1OP
  panelClosed PNCL
end

resetEvents
  doorOpened
end

commands
  unlockPanel PNUL
  lockPanel   PNLK
  lockDoor    D1LK
  unlockDoor  D1UL
end

state idle
  actions { unlockDoor lockPanel }
  doorClosed => active
end

state active
  drawOpened => waitingForLight
  lightOn    => waitingForDraw
end

state waitingForLight
  lightOn => unlockedPanel
end

state waitingForDraw
  drawOpened => unlockedPanel
end

state unlockedPanel
  actions { unlockPanel lockDoor }
  panelClosed => idle
end

*/

/*

Below is my first attempt to construct a grammar and express it in
BNF.  Elements within (unquoted) square brackets [ and ] are optional
and within (unquoted) braces { and } are repeated 0 or more times.

<Machine>        ::= <EventList> [<ResetEventList>] [<CommandList>]
                     {<State>} 
<EventList>      ::= "events" {<EventDec>} "end".
<EventDec>       ::= <Identifier> <Identifier>.
<ResetEventList> ::= "resetEvents" {<Identifier>} "end".
<CommandList>    ::= "commands" {<CommandDec>} "end".
<CommandDec>     ::= <Identifier> <Identifier>.
<State>          ::= "state" <Identifier> [<ActionList>] 
                     {<Transition>} "end"
<ActionList>     ::= "actions" "{" {<Identifier>} "}".
<Transition>     ::= <Identifier> "=>" <Identifier>.

Diagnostic Notes and Comments of the Grammar:

(1)) Initial changes: The parser for the above grammar seemed to fail
to recognize the syntax when there was complex usage of options and
repetitions.  To get a parser that recognizes the language as I
expected, I experimented with modifications of the grammar until I
found that the one below seemed to parse correctly.

(2) Further diagnostic analysis: Further investigation revealed that
the parser tended to treat "end" as an identifier.  This problem
seemed to occur first in parsing the <EventList> where the parser
could not distinguish between the first <Identifier> in <EventDec> and
the keyword "end" that terminated the "events" block.  After further
study of the Scala combinator parser library, I realized that the
lexical analyzer in JavaTokenParsers does not distinguish between
keywords and identifiers at its level.  I fixed this problem in the
grammar by breaking up each of <EventList>, <ResetEventList>, and
<CommandList> into two rules as in the modified grammar below.  With
this grammar, the Scala parser library checks for the "end" before
checking for an <Identifier>.

Thus, the refactoring of the complex <Machine> rule might not have
been needed.  This was done because the initial suspect was a problem
parsing some of the optional or repeated terms marked by [ ] and { },
respectively.  However, I have not tried to back it out.

(3) A perhaps better, but more complex, alternative would be to design
a custom subclass of Parsers (to replace JavaTokenParsers), which
would use a lexical analyzer that recognizes the difference between
identifiers and keywords.  It may be necessary to go to such an
arrangement to integrate better error reporting and recovery
mechanisms into the parsing.

(4) The version of the combinator parser that builds the State Machine
directly required further refactoring of the grammar to attach the
needed semantic actions.  The issue of what grammar is needed should
be studied further.

(5) For further thought: I don't yet fully understand the operation of
the parsers.  The grammar needs to be studied to make sure no
backtracking is required to parse the DSL.

<Machine>        ::= <EventList> <AfterEvent>.
<AfterEvent>     ::= <ResetEventList> <AfterReset> | <AfterReset>.
<AfterReset>     ::= <CommandList> {<State>} | {<State>}.

<EventList>      ::= "events" <EventEnd>.
<EventEnd>       ::= "end" | <EventDec> <EventEnd>.

<EventDec>       ::= <Identifier> <Identifier>.

<ResetEventList> ::= "resetEvents" <ResetEnd>.
<ResetEnd>       ::= "end" | <Identifier> <ResetEnd>.

<CommandList>    ::= "commands" <CommandEnd>.
<CommandEnd>     ::= "end" | <CommandDec> <CommandEnd>.

<CommandDec>     ::= <Identifier> <Identifier>.

<State>          ::= "state" <Identifier> [<ActionList>]
                     {<Transition>} "end".
<ActionList>     ::= "actions" "{" {<Identifier>} "}".
<Transition>     ::= <Identifier> "=>" <Identifier>.

*/

import scala.util.parsing.combinator._
import scala.collection.mutable.ArrayBuffer
import java.io._

/* The StateMachineASTBuilder uses a set of Scala parser combinators
   constructed according to the above grammar to build an abstract
   syntax tree.  It uses transformer functions (following the ^^) to
   change the standard parser return values into AST node classes.
*/

class StateMachineASTBuilder extends JavaTokenParsers {

  /* Top-level statement parsers.  The transformer functions
     associated with these parsers construct the root node of the AST,
     which is of type MachineNode.  This technique follows Fowler's
     Tree Construction DSL pattern.
   */

  // <Machine> ::= <EventList> <AfterEvent>
  def machine: Parser[Any] = 
    (eventList~afterEvent) ^^ {
      case en~ae =>
        ae match {
          case MachineNode(_,rn,cn,sl) =>
            MachineNode(en.asInstanceOf[EventNode],rn,cn,sl)
          case _ =>
            println("Syntax error after EventList")
            StateMachineBuilder.theNull
        }
    }

  // <AfterEvent> ::= <ResetEventList> <AfterReset> | <AfterReset>
  def afterEvent: Parser[Any] = 
    (resetEventList~afterReset) ^^ 
      { case rn~ar =>
          ar match {
            case MachineNode(_,_,cn,sl) =>
              MachineNode(null,rn.asInstanceOf[ResetNode],cn,sl) }
            case _ =>
              println("Syntax error after ResetEventList")
              StateMachineBuilder.theNull
      } |
    afterReset ^^ 
      { case MachineNode(_,_,cn,sl) => MachineNode(null,null,cn,sl) }

  // <AfterReset> ::= <CommandList> {<State>} | {<State>}
  def afterReset: Parser[Any] = 
    (commandList~rep(state)) ^^ 
      { case cn~sl => 
          MachineNode(null,null,cn.asInstanceOf[CommandNode],
                      sl.asInstanceOf[List[StateNode]]) } |
    rep(state) ^^ 
      { sl => MachineNode(null,null,null,
        sl.asInstanceOf[List[StateNode]]) }
    // Can we detect end of file

  /* Events block parsers.  The transformer functions associated with
     these parsers construct the EventNode of the AST and the various
     Event objects it contains.  An EventNode is one of the four
     components of the MachineNode.
  */

  // <EventList> ::= "events" <EventEnd>
  def eventList: Parser[Any] =
    ("events"~>eventEnd) ^^
      { case el => EventNode(el.asInstanceOf[List[Event]]) }

  // <EventEnd> ::= "end" | <EventDec> <EventEnd>
  def eventEnd:  Parser[Any] = 
    "end"               ^^ { _ => List[Event]() }  | 
    (eventDec~eventEnd) ^^ { case h~t => 
                               h::t.asInstanceOf[List[Event]] }

  // <EventDec> ::= <Identifier> <Identifier>
  def eventDec: Parser[Any] = 
    (ident~ident) ^^ { case n~c => Event(n,Symbol(c)) }


  /* Reset events block parsers. The transformer functions associated
     with these parsers construct the ResetNode of the AST, which
     holds a list of the reset event names.  A ResetNode is one of the
     four components of the MachineNode.
  */

  // <ResetEventList> ::= "resetEvents" <ResetEnd>
  def resetEventList: Parser[Any] = 
    ("resetEvents"~>resetEnd) ^^
      { case rl => ResetNode(rl.asInstanceOf[List[String]]) }

  // <ResetEnd> ::= "end" | <Identifier> <ResetEnd>.
  def resetEnd: Parser[Any] = 
    "end"            ^^ { _ => List[String]() }  | 
    (ident~resetEnd) ^^ { case h~t =>
                            h::t.asInstanceOf[List[String]] }


  /* Commands block parsers.  The transformer functions associated
     with these parsers construct the CommandNode of the AST and the
     various Command objects it contains. A CommandNode is one of the
     four components of the MachineNode.
  */

  // <CommandList> ::= "commands" <CommandEnd>
  def commandList: Parser[Any] = 
    ("commands"~>commandEnd) ^^
      { case cl => CommandNode(cl.asInstanceOf[List[Command]]) }

  // <CommandEnd> ::= "end" | <CommandDec> <CommandEnd>
  def commandEnd:  Parser[Any] = 
    "end"                   ^^ { _ => List[Command]() }  |
    (commandDec~commandEnd) ^^ 
      { case h~t => h::t.asInstanceOf[List[Command]] }

  // <CommandDec> ::= <Identifier> <Identifier>
  def commandDec: Parser[Any] = 
    (ident~ident) ^^ { case n~c => Command(n,Symbol(c)) }


  /* State block sequence parsers. The transformer functions
     associated with these parsers construct the list of StateNode
     objects of the AST.  Each StateNode has an ActionNode object and
     a list of TransitionNode objects associated with that State.  A
     list of StateNode objects forms one of the four components of the
     MachineNode.
  */

  // <State> ::= "state" <Identifier> [<ActionList>] {<Transition>} 
  //             "end"
  def state: Parser[Any] = 
    ("state"~>ident~opt(actionList)~rep(transition)<~"end") ^^
      { case sn~Some(al)~tl => 
          StateNode(sn,al.asInstanceOf[ActionNode],
                    tl.asInstanceOf[List[TransitionNode]])
        case sn~None~tl => 
          StateNode(sn,null,tl.asInstanceOf[List[TransitionNode]])
      }

  // <ActionList> ::= "actions"  "{" {<Identifier>} "}"
  def actionList: Parser[Any] = 
    ("actions"~>"{"~>rep(ident)<~"}") ^^ { case a => ActionNode(a) }

  // <Transition> ::= <Identifier> "=>" <Identifier>
  def transition: Parser[Any] = 
    (ident~"=>"~ident) ^^ { case e~_~d => TransitionNode(e,d) }
}


/* The ASTNode hierarchy of case classes form the nodes of the AST.  */

abstract class ASTNode

// Root node
case class MachineNode(enode: EventNode, rnode: ResetNode, 
                       cnode:CommandNode,
                       snlist: List[StateNode]) extends ASTNode {
  override def toString = 
    "\nMACHINE\n" + enode + "\n" + rnode + "\n" + cnode + 
  "\n" + snlist
}

// Second-level nodes (inside MachineNode)
case class EventNode(events: List[Event])  extends ASTNode
case class ResetNode(resets: List[String]) extends ASTNode
case class CommandNode(commands: List[Command]) extends ASTNode
case class StateNode(name: String, stateActions: ActionNode, 
                     transitions: List[TransitionNode]) 
                     extends ASTNode

// Third-level nodes (inside StateNode)
case class ActionNode(actions: List[String]) extends ASTNode
case class TransitionNode(trigger: String, target: String) 
     extends ASTNode


/* Class StateMachineBuilder defines an object whose "build" method
   walks its AST argument and populates a State Machine Semantic Model.
*/

class StateMachineBuilder(ast: MachineNode) {

  private var stateMachine: StateMachine         = null
  private var startState: State                  = null
  private var allStates: List[(State,StateNode)] = null

  def build: StateMachine = {
    if (ast.snlist.isEmpty) { 
      throw new RuntimeException("No states in state machine.")
    }
    allStates = 
      for (sn <- ast.snlist) yield (new State(sn.name),sn)
    startState    = allStates.head._1
    stateMachine = new StateMachine(startState)
    for ((st,sn) <- allStates) { addConnections(st,sn) }
    var resetEvents = new ArrayBuffer[Event]
    for (r <- ast.rnode.resets) {
      getEvent(r) match { // might not be defined
        case Some(e) => resetEvents += e
        case None    => throw new RuntimeException(
                          "Undefined reset Event " + r)
      }
    }
    stateMachine.addResetEvents(resetEvents.toArray: _*)
    stateMachine
  }

  /* Accessor to return State Machine that was built.  */

  def getMachine: StateMachine = stateMachine

  /* Look up events, commands, and states to make sure defined.  */

  private def getEvent(str: String) = 
    ast.enode.events.find(_.name == str)

  private def getCommand(str: String) = 
    ast.cnode.commands.find(_.name == str)

  private def getState(str: String) = 
    allStates.find(x => x._1.name == str) match {
      case Some((st,sn)) => Some(st)
      case None          => None
    }

  /* Add the actions and transitions to the states.  */

  private def addConnections(st: State, sn: StateNode) {
    if (sn.stateActions != null ) {
      for (ac <- sn.stateActions.actions) {
        getCommand(ac) match {
          case Some(c) => st.addAction(c)
          case None => 
            throw new RuntimeException(
              "Undefined action " + ac + " on state " + st.name +".")
        }
      }
    }
    for (tn <- sn.transitions) {
      val trig = getEvent(tn.trigger)
      val targ = getState(tn.target)
      (trig,targ) match {
        case (Some(e),Some(s)) => 
          st.addTransition(e.asInstanceOf[Event], 
          s.asInstanceOf[State])
        case _ => 
          throw new RuntimeException(
                    "Undefined transition " + tn + "in state " + st)
      }
    }
  }
}

/* StateMachineBuilder companion object */

object StateMachineBuilder {

  val theNull = MachineNode(null,null,null,List[StateNode]())

}

/*  Object to do some simple testing of the parser.  */

object CombinatorParserASTTest extends StateMachineASTBuilder {

  def main(args: Array[String]) {
    println("\nCombinator Parser External DSL test beginning.\n")

    // Load and parse the DSL to configure the State Machine
    val reader = 
      new FileReader("CustomExternalStateMachineDSL2.dsl")
//    new FileReader("CustomExternalStateMachineErr2.dsl")

    var machineAST = StateMachineBuilder.theNull
    parseAll(machine,reader) match {
      case Success(res,_) => 
        machineAST = res.asInstanceOf[MachineNode]
      case NoSuccess(msg,inp) =>
        println("Error: " + msg)
        println("Input remaining:\n" + inp.source)
        System.exit(1)
    }

    println(machineAST)

    // Walk the AST to populate the State Machine Semantic Model
    val stateMachine = (new StateMachineBuilder(machineAST)).build
    println(stateMachine)

    // Build the controller for some testing
    val commandsChannel = new CommandChannel
    val control = new Controller(stateMachine,commandsChannel)
    println(control.toString)

    // Execute the model a few steps
    control.handle('D1CL)
    control.handle('L1ON)
    control.handle('D2OP)
    control.handle('PNCL)

    println("\nCommands output:  " + commandsChannel.getOutput)

    println("\nCombinator Parser External DSL test ending.\n")
  }
}