/* Engr 691-6, Special Topics, Software Language Engineering
   Scala Combinator-based Parser and AST Builder for Fowler's 
     Custom External State Machine DSL (Secret Panel)
   H. Conrad Cunningham
   Version 1:   28 April 2009
   Version 2b:   3 May 2009 Documentation and other improvements
   Version 2c:  13 May 2009 Minor Scala programming style changes.

123456789012345678901234567890123456789012345678901234567890123456789012345678

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.

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 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 "Tree Construction" chapter
of Fowler's in-progress DSL book:

    http://www.martinfowler.com/dslwip/intro.html.  

Below is Fowler's example input file from the Tree Construction
chapter of the in-progress 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 Constrcution DSL pattern.
  */

  // <Machine> ::= <EventList> <AfterEvent>
  def machine: Parser[Any] = 
    (eventList~afterEvent) ^^ {
      case en~MachineNode(_,rn,cn,sl) => 
        MachineNode(en.asInstanceOf[EventNode],rn,cn,sl) 
    }

  // <AfterEvent> ::= <ResetEventList> <AfterReset> | <AfterReset>
  def afterEvent: Parser[Any] = 
    (resetEventList~afterReset) ^^ 
      { case rn~MachineNode(_,_,cn,sl) => 
          MachineNode(null,rn.asInstanceOf[ResetNode],cn,sl) } | 
    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]]) }


  /* 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)
      }
    }
  }
}


/*  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")
    val machineAST = parse(machine,reader).get.asInstanceOf[MachineNode]
    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")
  }
}