muSED.h

Go to the documentation of this file.

#include <cxxtls/foreach.h>
#include <cxxtls/simple_regex.h>
#include <cxxtls/charSetTranslator.h>
#include <list>
#include <memory>
#include <map>
#include <portable_io.h>


namespace cxxtls
{

namespace muSED
{
    using namespace cxxtls;

    // micro sed engine.  Sed is the "string editor" program on unix.
    // muSED lets you execute simplified sed scripts on string containers (vectors, 
    // arrays, lists, dequeues, etc.



    struct ScriptRuntimeContext;  // compiled script plus state variables and buffers

//========================================================================================
     
     
     template<class StringIterator1, class StringIterator2>
     void skipBlanks(StringIterator1 &firstChar,
                     StringIterator2 &lastChar
                    )
     {
    
    
        while(    (firstChar != lastChar)
              &&  (*firstChar <= ' ')
             )
             ++firstChar;
     }

//========================================================================================

     void expandEscapes(std::string &input)
         ;

//========================================================================================
     template<class StringIterator1, class StringIterator2>
     bool parseEscapedString(char            delim, 
                             std::string    &output,
                             StringIterator1 &firstChar,
                             StringIterator2 &lastChar
                            )
     {


        char c;

        StringIterator1 savedFirst = firstChar;

        while(    (firstChar != lastChar)
              &&  (c = *firstChar)
              &&  (c != delim)
             )
        {
           if(c == '\\')
           {
              ++firstChar;

              if(firstChar == lastChar)
              {
                 firstChar = savedFirst;  
                 return false;  //  failure
              }

              output += '\\';
              output += *firstChar++;

           }
           else
           {
              output += c;

              ++firstChar;
           }
        }


        return true;

     }  // parseEscapedString()

//========================================================================================



    struct Filter


    {
        // line number, regex, lastLine or other filter

        enum type { none, regex, lineNumber, lastLine };

        type type_;

        SimpleRegex regex_;

        size_t line_;


        Filter()
        : type_(none)
        , line_(0)
        {
        }

        Filter &operator= (Filter const &rhs)
        {
           type_ = rhs.type_;

           line_ = rhs.line_;

           if(type_ == regex)
           {
              // slight optimization, don't ccopy the regex unnecessarily

              regex_ = rhs.regex_;
           }

           return *this;

        }

        bool passes(size_t lineNo, bool isLast, std::string const &line)
            ;

        template<class StringIterator>
        bool parse(StringIterator &first, StringIterator const &last)
        {
            skipBlanks(first, last);

            if(first == last)
               return false;

            type_ = none;

            StringIterator savedFirst = first;

            char c = *first;

            switch(c)
            {
               case '/':
                   {
                      //
                      //  parse a regex, return false if not found (also restore cp
                      //

                      std::string buf;

                      ++first;

                      if(!parseEscapedString('/', buf, first, last))
                      {
                         first = savedFirst;
                         return false;
                      }

                      type_ = regex;
                      regex_ = buf;
                      ++first;  // skip the trailing /

                   }
                   return true; // if we get here!

               case '$':
                   type_ = lastLine;
                   ++first;
                   return true;

               default:
                   if(!isdigit(c))
                      return false;   // does not indicate an error
                   {
                      
                      char buffer[256];

                      char *p = &buffer[0];
                      char *e = &buffer[sizeof(buffer)-1];

                      while(   (p != e) 
                            && (first != last)
                            && (c = *first)
                            && isdigit(c)
                           )
                      {
                          *p++ = c;
                          ++first;
                      }

                      *p++ = 0;

                      int lineNo = -1;

                      sscanf(buffer, "%d", &lineNo);
                      
                      if(lineNo == -1)
                      {
                         first = savedFirst;
                         return false;
                      }

                      line_ = lineNo;
                      type_ = lineNumber;

                   }
                   return true; // if we get here
            }

            return true;
        }

        virtual std::string debugString() const;




    };  // struct Filter
//========================================================================================
    struct Statement;

    enum LineRangeActivationState
    {
        neverExecuted=0,   
        inRange,           
        lastLine,          
    };


    typedef std::map<Statement*, LineRangeActivationState> ActivationMap;

//========================================================================================

    struct Statement
    {   // struct Statement

         std::list<Statement *>  childStatements_;
         ActivationMap           childStatementActivationMap_;

         Statement *parentStatement_;  // parent owns me, not the other way around

         Statement(Statement *parentStatement)  // null parent only ok for very top level statement
         : parentStatement_(parentStatement)
         {
         }

         LineRangeActivationState activationState() ;

         void setActivationState(LineRangeActivationState newState);

         virtual bool execute(ScriptRuntimeContext *context) = 0; 

         void clear()
         {
            CXXTLS_FOREACH(Statement *cur, childStatements_)
            {
               delete cur;
            }

            childStatements_.clear();
         }

         void adoptChild(Statement *newbie)
         {
             childStatements_.push_back(newbie);
         }


         virtual ~Statement()
         {
            clear();
         }

         std::string debugPrefix() const
         {
             char buffer[256];

             snprintf(buffer, sizeof(buffer), "ST[%p]=", this);

             return buffer;
         }


         virtual std::string debugString() const
         {
            return "<invalid>";
         }

         static void debugPrint(Statement *p)
         {
            printf("%s\n", p->debugString().c_str());
            fflush(stdout);
         }


    
    };  // struct statement
//========================================================================================
    struct OuterStatement
    :  public Statement
    {
        OuterStatement()
        :  Statement(0)
        {
        }


        virtual bool execute(ScriptRuntimeContext *context);


         virtual std::string debugString() const
         {
            return "<Outer>";
         }




    };
//========================================================================================

    struct FilterableStatement
    :  public Statement
    {  // struct FilterableStatement

       virtual ~FilterableStatement(){}

       int filters_;

       Filter filter1_;
       Filter filter2_;
       bool   inverted_;


       FilterableStatement(Statement*         parent,
                           int                fc, 
                           Filter const      &f1, 
                           Filter const      &f2,
                           bool               inverted
                          )
        :  Statement(parent)
        ,  filters_(fc)
        ,  filter1_(f1)
        ,  filter2_(f2)
        ,  inverted_(inverted)
        {
        }


        bool active(ScriptRuntimeContext *context, Statement *statement);  

        virtual std::string debugStringPrefix() const;

            
    }; // struct FilterableStatement

//========================================================================================

    struct BlockStatement
    : public FilterableStatement
    {

        std::auto_ptr<SimpleRegex>  whileCondition_;

        bool execute(ScriptRuntimeContext *context);

        BlockStatement(Statement *parent,
                       int filterCount,
                       Filter &fc1,
                       Filter &fc2,
                       bool    filterInverted,
                       SimpleRegex *condition
                      )
        :  FilterableStatement(parent, filterCount, fc1, fc2, filterInverted)
        ,  whileCondition_(condition)
        {
        }
           
         virtual std::string debugString() const;

         // note that there is no parse() function here because the compileStream() method, below(),
         // parses the block statement for you.


    }; // BlockStatement

//========================================================================================

    struct SubstStatement
    :  public FilterableStatement
    {

        virtual ~SubstStatement(){}

        int count_;  // number of substitutions

        SimpleRegex target_;
        SimpleRegex replacement_;

        SubstStatement(Statement         *parent,
                       int                fc, 
                       Filter const      &f1,
                       Filter const      &f2,
                       bool               filtersInverted,
                       std::string const &tgt,
                       std::string const &rep,
                       int                count,
                       bool               insensitive
                      )
        : FilterableStatement(parent, fc, f1, f2, filtersInverted)
        , count_(count)
        , target_(tgt, (insensitive? "i" : ""))
        , replacement_(rep)
        {
        }

        bool execute(ScriptRuntimeContext *context);
            
        template<class StringIterator1, class StringIterator2, class CompiledScript>
        static Statement* parse(Statement             *parent,
                                int                   filterCount, 
                                Filter const          &f1, 
                                Filter const          &f2, 
                                bool                   inverted,
                                StringIterator1       &firstChar,
                                StringIterator2 const &lastChar,
                                size_t                 line,
                                CompiledScript        &script
                               )
        {
        
            // parse the sed 's' command
        
            ++firstChar;
        
            if(firstChar == lastChar)
            {
               script.fail("missing / in s command", line);
               return 0;
            }
        
            char c = *firstChar++;
        
            if(    (c <= ' ') 
               ||  (c >= 'a' && c <= 'z')
               ||  (c >= 'A' && c <= 'Z')
              )
            {
               std::string tmp = "invalid s command delimiter '";
               tmp += c;
               tmp += "'";
        
               script.fail(tmp, line);
               return 0;
        
            }
        
            char delim = c;
        
            std::string target;
            std::string replacement;
            int count=0;
        
            // we are currently here in the parsing of an s command:
            //
            //   s/target/replacement/1
            //     ^
        
            if(!parseEscapedString(delim, target, firstChar, lastChar))
            {
               script.fail("badly formed LHS in s command", line);
               return 0;
            }


        
            ++firstChar;
        
            // we are currently here in the parsing of an s command:
            //
            //   s/target/replacement/1
            //            ^
        
            
            if(!parseEscapedString(delim, replacement, firstChar, lastChar))
            {
               script.fail("badly formed RHS in s command", line);
               return 0;
            }
        
            ++firstChar;
        
            if(   (firstChar == lastChar)
               || (   (*firstChar != '1')
                   && (*firstChar != 'g')
                  )
              )
            {
               script.fail("badly formed count in s command -- expected 1 or g", line);
               return 0;
                
            }
        
            if(*firstChar == '1')
               count=1;
        
            // hah!  good syntax
        
            ++firstChar;  // skip the g or the 1

            bool insensitive=false;

            if(firstChar != lastChar && *firstChar == 'i')
            {
               ++firstChar;
               insensitive = true;
            }

        
            expandEscapes(target);       // replace \n in target with newline, and so on.
            expandEscapes(replacement);  // replace \n in target with newline, and so on.


            return new SubstStatement(   parent,
                                         filterCount,
                                         f1,
                                         f2,
                                         inverted,
                                         target,
                                         replacement,
                                         count,
                                         insensitive
                                     );
        }

         virtual std::string debugString() const;


          
    }; // struct SubstStatement

//========================================================================================

    struct TranslateStatement
    :  public FilterableStatement
    {

        virtual ~TranslateStatement(){}

        std::string target_;
        std::string replacement_;

        CharSetTranslator translator_;

        TranslateStatement(Statement         *parent,
                       int                fc, 
                       Filter const      &f1,
                       Filter const      &f2,
                       bool               filtersInverted,
                       std::string const &tgt,
                       std::string const &rep
                      )
        : FilterableStatement(parent, fc, f1, f2, filtersInverted)
        , target_(tgt)
        , replacement_(rep)
        , translator_(tgt,rep)
        {
        }

        bool execute(ScriptRuntimeContext *context);
            
        template<class StringIterator1, class StringIterator2, class CompiledScript>
        static Statement* parse(Statement             *parent,
                                int                   filterCount, 
                                Filter const          &f1, 
                                Filter const          &f2, 
                                bool                   inverted,
                                StringIterator1       &firstChar,
                                StringIterator2 const &lastChar,
                                size_t                 line,
                                CompiledScript        &script
                               )
        {
        
            // parse the sed 'y' command
        
            ++firstChar;
        
            if(firstChar == lastChar)
            {
               script.fail("missing / in s command", line);
               return 0;
            }
        
            char c = *firstChar++;
        
            if(    (c <= ' ') 
               ||  (c >= 'a' && c <= 'z')
               ||  (c >= 'A' && c <= 'Z')
              )
            {
               std::string tmp = "invalid y command delimiter '";
               tmp += c;
               tmp += "'";
        
               script.fail(tmp, line);
               return 0;
        
            }
        
            char delim = c;
        
            std::string target;
            std::string replacement;
        
            // we are currently here in the parsing of an y command:
            //
            //   y/target/replacement/
            //     ^
        
            if(!parseEscapedString(delim, target, firstChar, lastChar))
            {
               script.fail("badly formed LHS in 'y' command", line);
               return 0;
            }
        
            ++firstChar;
        
            // we are currently here in the parsing of an s command:
            //
            //   y/target/replacement/
            //            ^
        
            
            if(!parseEscapedString(delim, replacement, firstChar, lastChar))
            {
               script.fail("badly formed RHS in 'y' command", line);
               return 0;
            }
        
            ++firstChar;
        
        
            // hah!  good syntax
        
            expandEscapes(target);       // replace \n in target with newline, and so on.
            expandEscapes(replacement);  // replace \n in target with newline, and so on.


            return new TranslateStatement(   parent,
                                             filterCount,
                                             f1,
                                             f2,
                                             inverted,
                                             target,
                                             replacement
                                         );
        }

         virtual std::string debugString() const;


          
    }; // struct TranslateStatement

//========================================================================================

    struct PrintStatement
    :  public FilterableStatement
    {

        virtual ~PrintStatement(){}

        bool firstLineOnly_;   




        PrintStatement(Statement         *parent,
                       int                fc,
                       Filter const      &f1,
                       Filter const      &f2,
                       bool               filtersInverted,
                       bool               firstLineOnly
                      )
        : FilterableStatement(parent, fc, f1, f2, filtersInverted)
        , firstLineOnly_(firstLineOnly)
        {
        }


        bool execute(ScriptRuntimeContext *context);

        template<class StringIterator1, class StringIterator2, class CompiledScript>
        static Statement* parse(Statement             *parent,
                                int                   filterCount, 
                                Filter const          &f1, 
                                Filter const          &f2, 
                                bool                   inverted,
                                StringIterator1       &firstChar,
                                StringIterator2 const &lastChar,
                                size_t                 line,
                                CompiledScript        &script
                               )
        {

            bool firstLineOnly = *firstChar == 'P';

            ++firstChar;  // skip the p

            return new PrintStatement(   parent,
                                         filterCount,
                                         f1,
                                         f2,
                                         inverted,
                                         firstLineOnly
                                     );
        }

         virtual std::string debugString() const;



          
    }; // struct PrintStatement

//========================================================================================

    struct SwapStatement
    :  public FilterableStatement
    {

        virtual ~SwapStatement(){}

        SwapStatement(Statement         *parent,
                       int                fc,
                       Filter const      &f1,
                       Filter const      &f2,
                       bool               filtersInverted
                      )
        : FilterableStatement(parent, fc, f1, f2, filtersInverted)
        {
        }


        bool execute(ScriptRuntimeContext *context);

        template<class StringIterator1, class StringIterator2, class CompiledScript>
        static Statement* parse(Statement             *parent,
                                int                   filterCount, 
                                Filter const          &f1, 
                                Filter const          &f2, 
                                bool                   inverted,
                                StringIterator1       &firstChar,
                                StringIterator2 const &lastChar,
                                size_t                 line,
                                CompiledScript        &script
                               )
        {

            ++firstChar;  // skip the p

            return new SwapStatement(   parent,
                                         filterCount,
                                         f1,
                                         f2,
                                         inverted
                                     );
        }

         virtual std::string debugString() const;


          
    }; // struct SwapStatement


//========================================================================================

    struct DeleteStatement
    :  public FilterableStatement
    {

        virtual ~DeleteStatement(){}

        DeleteStatement(Statement         *parent,
                       int                fc,
                       Filter const      &f1,
                       Filter const      &f2,
                       bool               filtersInverted
                      )
        : FilterableStatement(parent, fc, f1, f2, filtersInverted)
        {
        }


        bool execute(ScriptRuntimeContext *context);

        template<class StringIterator1, class StringIterator2, class CompiledScript>
        static Statement* parse(Statement             *parent,
                                int                   filterCount, 
                                Filter const          &f1, 
                                Filter const          &f2, 
                                bool                   inverted,
                                StringIterator1       &firstChar,
                                StringIterator2 const &lastChar,
                                size_t                 line,
                                CompiledScript        &script
                               )
        {

            ++firstChar;  // skip the d

            return new DeleteStatement(   parent,
                                         filterCount,
                                         f1,
                                         f2,
                                         inverted
                                     );
        }

         virtual std::string debugString() const;


          
    }; // struct DeleteStatement


//========================================================================================

    struct QuitStatement
    :  public FilterableStatement
    {
        bool printCurrent_;             


        virtual ~QuitStatement(){}

        QuitStatement(Statement         *parent,
                       int                fc,
                       Filter const      &f1,
                       Filter const      &f2,
                       bool               filtersInverted,
                       bool               printCurrent
                      )
        : FilterableStatement(parent, fc, f1, f2, filtersInverted)
        , printCurrent_(printCurrent)
        {
        }


        bool execute(ScriptRuntimeContext *context);

        template<class StringIterator1, class StringIterator2, class CompiledScript>
        static Statement* parse(Statement             *parent,
                                int                   filterCount, 
                                Filter const          &f1, 
                                Filter const          &f2, 
                                bool                   inverted,
                                StringIterator1       &firstChar,
                                StringIterator2 const &lastChar,
                                size_t                 line,
                                CompiledScript        &script
                               )
        {
            bool printCurrent = (*firstChar) == 'q';

            ++firstChar;  // skip the q

            return new QuitStatement(   parent,
                                         filterCount,
                                         f1,
                                         f2,
                                         inverted,
                                         printCurrent
                                     );
        }

         virtual std::string debugString() const;


          
    }; // struct QuitStatement


//========================================================================================

    struct HoldStatement
    :  public FilterableStatement

    {

        bool append_;

        virtual ~HoldStatement(){}

        HoldStatement(Statement         *parent,
                       int                fc,
                       Filter const      &f1,
                       Filter const      &f2,
                       bool               filtersInverted,
                       bool               append=false
                      )
        : FilterableStatement(parent, fc, f1, f2, filtersInverted)
        , append_(append)
        {
        }


        bool execute(ScriptRuntimeContext *context);

        template<class StringIterator1, class StringIterator2, class CompiledScript>
        static Statement* parse(Statement             *parent,
                                int                   filterCount, 
                                Filter const          &f1, 
                                Filter const          &f2, 
                                bool                   inverted,
                                StringIterator1       &firstChar,
                                StringIterator2 const &lastChar,
                                size_t                 line,
                                CompiledScript        &script,
                                bool                   append
                               )
        {

            ++firstChar;  // skip the p

            return new HoldStatement(   parent,
                                         filterCount,
                                         f1,
                                         f2,
                                         inverted,
                                         append
                                     );
        }


         virtual std::string debugString() const;


          
    }; // struct HoldStatement


//========================================================================================

    struct GetStatement
    :  public FilterableStatement

    {

        bool append_;

        virtual ~GetStatement(){}

        GetStatement(Statement         *parent,
                       int                fc,
                       Filter const      &f1,
                       Filter const      &f2,
                       bool               filtersInverted,
                       bool               append=false
                      )
        : FilterableStatement(parent, fc, f1, f2, filtersInverted)
        , append_(append)
        {
        }


        bool execute(ScriptRuntimeContext *context);

        template<class StringIterator1, class StringIterator2, class CompiledScript>
        static Statement* parse(Statement             *parent,
                                int                   filterCount, 
                                Filter const          &f1, 
                                Filter const          &f2, 
                                bool                   inverted,
                                StringIterator1       &firstChar,
                                StringIterator2 const &lastChar,
                                size_t                 line,
                                CompiledScript        &script,
                                bool                   append
                               )
        {

            ++firstChar;  // skip the p

            return new GetStatement(   parent,
                                         filterCount,
                                         f1,
                                         f2,
                                         inverted,
                                         append
                                     );
        }

         virtual std::string debugString() const;


          
    }; // struct GetStatement


//========================================================================================

    struct CompiledScript

    {

         OuterStatement  outerStatement_; // this statement alone has a null parent

         void clear()
         {
             outerStatement_.clear();
         }

         ~CompiledScript()
         {
            clear();
         }


         bool ok_;  // script has valid contents.

         std::string error_;


         template<class StringContainer>
         CompiledScript(StringContainer const &script)
         : ok_(false)
         , error_("Error:  no script specified")
         {

             compile(script.begin(), script.end());

         }

         bool ok() const { return ok_; }

         std::string const &error() const { return error_; }

         bool execute(ScriptRuntimeContext *context)
         {
             // execute all statements on the specified line

             if(!ok_)
                return true; // can't execute trash


             return outerStatement_.execute(context);
         }


         void fail(std::string const &errormsg, int line)
         {
            ok_    = false;

            char buffer[40];

            snprintf(buffer, sizeof(buffer), " at line %d",  line);


            error_ = errormsg + buffer;

            clear();  // it must all compile or none of it does.
            
         }

         typedef std::pair<std::string::const_iterator&, std::string::const_iterator&> CharRange;


         template<class LineRange>
         static void compileStream(  LineRange lineRange,                  // pair of REFERENCES to iterators
                                     CharRange charRange,                  // pair of REFERENCES to iterators
                                     Statement *parent,                    // owner of statements to be created
                                     int &line,
                                     CompiledScript *script
                                  )
         {




             std::string::const_iterator &firstChar = charRange.first;   // aliases to charRange references
             std::string::const_iterator &lastChar  = charRange.second;


             while(lineRange.first != lineRange.second)
             {
                // parse all lines in the script

                ++line;


                Filter filter1;
                Filter filter2;
                int    filterCount=0;

                while(firstChar != lastChar)
                {
                    // process all characters on the current line, with the
                    // possibility that if we hit a new line within an unclosed
                    // curly-brace block that the current line will be replaced
                    // with the next line, ad infinitum, until we hit the end
                    // of the curly block and all it's nested components...


                    skipBlanks(firstChar, lastChar);

                    if(firstChar == lastChar)
                       break;


                    if( *firstChar == ';' || *firstChar == '\n')
                    {
                       ++firstChar;
                       continue;
                    }


                    if(filterCount == 0)
                    {
                        if(filter1.parse(firstChar, lastChar))
                        {
                           ++filterCount;

                           if(firstChar != lastChar && *firstChar == ',')
                           {
                               ++firstChar;  // skip the comma

                               if(filter2.parse(firstChar, lastChar))
                                  ++filterCount;

                               if(filterCount != 2)
                               {
                                  script->fail("Error, expected filter expression after ','", line);
                               }
                           }
                        }
                    }



                    // filterCount will tell us if there are any filters
                    // at all.

                    // now parse the statement

                    skipBlanks(firstChar, lastChar);

                    bool filterInverted = false;

                    if(firstChar != lastChar && *firstChar == '!')
                    {
                        filterInverted = true;
                        ++firstChar;
                        skipBlanks(firstChar, lastChar);
                    }


                    if(firstChar != lastChar)
                    { // there is a command still on this line


                       // we have a statement, now parse it!

                       char cmd = *firstChar;

                       // NOTE:  the following code is stupid.
                       // Since all sed commands have a unique 1 character identifier,
                       // we should have a table matching that character with the
                       // kind of statement it matches, and let the parsing code
                       // reside in the statement itself.  As it is, this function is
                       // too big and is coupled to statement contstructors...


                       if(cmd == '#')
                       {
                          // this line is a comment
                          firstChar = lastChar;
                       }
                       else
                       if(cmd ==  's')
                       {

                         std::auto_ptr<Statement> s(SubstStatement::parse(parent,
                                                                          filterCount,
                                                                          filter1,
                                                                          filter2,
                                                                          filterInverted,
                                                                          firstChar,
                                                                          lastChar,
                                                                          line,
                                                                          *script
                                                    )
                                              );
                         if(s.get())
                         {
                             parent->adoptChild(s.release());
                         }  
                         else
                         {
                            return;
                         }

                       }
                       else
                       if(cmd ==  'y')
                       {

                         std::auto_ptr<Statement> s(TranslateStatement::parse(parent,
                                                                          filterCount,
                                                                          filter1,
                                                                          filter2,
                                                                          filterInverted,
                                                                          firstChar,
                                                                          lastChar,
                                                                          line,
                                                                          *script
                                                    )
                                              );
                         if(s.get())
                         {
                             parent->adoptChild(s.release());
                         }  
                         else
                         {
                            return;
                         }

                       }
                       else
                       if( cmd == 'p' || cmd == 'P')
                       {
                                                 
                           std::auto_ptr<Statement> s(PrintStatement::parse(parent,
                                                                            filterCount,
                                                                            filter1,
                                                                            filter2,
                                                                            filterInverted,
                                                                            firstChar,
                                                                            lastChar,
                                                                            line,
                                                                            *script
                                                                            )
                                                     );
                           
                          if(s.get())
                          {
                              parent->adoptChild(s.release());
                          }
                          else
                          {
                              return;
                          }

                       }
                       else
                       if( cmd == 'd')
                       {
                                                 
                           std::auto_ptr<Statement> s(DeleteStatement::parse(parent,
                                                                            filterCount,
                                                                            filter1,
                                                                            filter2,
                                                                            filterInverted,
                                                                            firstChar,
                                                                            lastChar,
                                                                            line,
                                                                            *script
                                                                            )
                                                     );
                           
                          if(s.get())
                          {
                              parent->adoptChild(s.release());
                          }
                          else
                          {
                              return;
                          }

                       }
                       else
                       if( cmd == 'q' || cmd == 'Q' )
                       {
                                                 
                           std::auto_ptr<Statement> s(QuitStatement::parse(parent,
                                                                            filterCount,
                                                                            filter1,
                                                                            filter2,
                                                                            filterInverted,
                                                                            firstChar,
                                                                            lastChar,
                                                                            line,
                                                                            *script
                                                                            )
                                                     );
                           
                          if(s.get())
                          {
                              parent->adoptChild(s.release());
                          }
                          else
                          {
                              return;
                          }

                       }
                       else
                       if( cmd == 'h'  || cmd == 'H' )
                       {
                                                 
                           std::auto_ptr<Statement> s(HoldStatement::parse(parent,
                                                                            filterCount,
                                                                            filter1,
                                                                            filter2,
                                                                            filterInverted,
                                                                            firstChar,
                                                                            lastChar,
                                                                            line,
                                                                            *script,
                                                                            cmd == 'H'
                                                                            )
                                                     );
                           
                          if(s.get())
                          {
                              parent->adoptChild(s.release());
                          }
                          else
                          {
                              return;
                          }

                       }
                       else
                       if( cmd == 'g'  || cmd == 'G' )
                       {
                                                 
                           std::auto_ptr<Statement> s(GetStatement::parse(parent,
                                                                            filterCount,
                                                                            filter1,
                                                                            filter2,
                                                                            filterInverted,
                                                                            firstChar,
                                                                            lastChar,
                                                                            line,
                                                                            *script,
                                                                            cmd == 'G'
                                                                            )
                                                     );
                           
                          if(s.get())
                          {
                              parent->adoptChild(s.release());
                          }
                          else
                          {
                              return;
                          }

                       }
                       else
                       if( cmd == 'x')
                       {
                                                 
                           std::auto_ptr<Statement> s(SwapStatement::parse(parent,
                                                                            filterCount,
                                                                            filter1,
                                                                            filter2,
                                                                            filterInverted,
                                                                            firstChar,
                                                                            lastChar,
                                                                            line,
                                                                            *script
                                                                            )
                                                     );
                           
                          if(s.get())
                          {
                              parent->adoptChild(s.release());
                          }
                          else
                          {
                              return;
                          }

                       }
                       else
                       if(cmd == '{' || cmd == 'W')
                       {
                          // handle block statements here, recursively

                         std::auto_ptr<SimpleRegex> regex;

                         if(cmd == 'W')
                         {
                             // parse the regex

                             ++firstChar;  // skip the W

                             skipBlanks(firstChar, lastChar);

                             char c = ' ';

                             if(firstChar != lastChar)
                                 c = *firstChar;

                             if(    (c <= ' ') 
                                ||  (c >= 'a' && c <= 'z')
                                ||  (c >= 'A' && c <= 'Z')
                               )
                             {
                                std::string tmp = "invalid W command regex delimiter '";
                                tmp += c;
                                tmp += "'";
                         
                                script->fail(tmp, line);
                                return ;
                         
                             }

                             std::string target;
                             
                             // we are currently here in the parsing of an s command:
                             //
                             //     /regex/
                             //     ^
                             
                             ++firstChar;
                             if(!parseEscapedString(c, target, firstChar, lastChar))
                             {
                                script->fail("badly formed W command regex", line);
                                return;
                             }

                             ++firstChar;

                             // we are currently here in the parsing of an s command:
                             //
                             //     /regex/
                             //            ^

                             skipBlanks(firstChar, lastChar);

                             if(firstChar == lastChar || *firstChar != '{')
                             {
                                script->fail("Missing '{' after 'W' command regex", line);
                                return ;
                             }

                             expandEscapes(target);
                             regex.reset( new SimpleRegex(target) );

                         }


                         ++firstChar;

                         Statement *childBlock;

                         parent->adoptChild( childBlock =
                                             new BlockStatement(parent,
                                                              filterCount,
                                                              filter1,
                                                              filter2,
                                                              filterInverted,
                                                              regex.release()
                                                             )
                                                );

                         // note:  lineRange and charRange are pairs of references to
                         // iterators, so the call below passes this function's input
                         // references to its child.  

                         compileStream(lineRange, charRange, childBlock, line, script);

                         if( (firstChar == lastChar) || *firstChar != '}')
                         {
                            if(script->ok())
                                script->fail("block statement missing }", line);

                            return;
                         }

                         ++firstChar;



                       }
                       else
                       if(cmd == '}')
                       {
                          // although this might be an error, treat the }
                          // character as an end of script flag.  This is
                          // needed or at least helpful to recursive block
                          // parsing.

                          return;

                       }
                       else
                       {
                           std::string tmp = "unexpected command: ";

                           tmp += cmd;

                           script->fail(tmp, line);

                           return;
                          
                       }



                    } // there is a command still on this line


                    // by this point, the statement on the currentline has been processed,
                    // but we must deal with whatever comes after the valid syntax on the line.
                    // we will handle it by skipping blanks and then interpreting what we 
                    // see.

                    skipBlanks(firstChar, lastChar);

                    if(firstChar != lastChar)
                    { // there may be more on this same line

                        if(*firstChar == ';')
                        {
                           ++firstChar;     // the skip the ';'
                           filterCount=0;

                        }
                        else
                        if(*firstChar == '#')
                        {
                           firstChar = lastChar;  // end of line comment
                        }

                       
                    } // there may be more on this same line


                    
                }  // process the current line






                ++lineRange.first;  // step to next line

                if(lineRange.first != lineRange.second)
                {
                   firstChar = lineRange.first->begin();
                   lastChar  = lineRange.first->end();
                }


             }

             
         }


         template<class StringIterator>
         void compile(StringIterator first, StringIterator last)
         {
             if(first == last)
               return;  // leave the CompiledScript in the current
                        // error state

             ok_    = true;
             error_ = "";

             int line=0;

             std::string::const_iterator firstChar = first->begin(),
                                         lastChar  = first->end();

             typedef std::pair<StringIterator&, StringIterator&>                           LineRange;

             compileStream( LineRange(first,last), 
                            CharRange(firstChar,lastChar),
                            &outerStatement_, 
                            line, 
                            this 
                          );

         }


    };  // struct CompiledScript

//========================================================================================

    struct ScriptRuntimeContext
    {
       CompiledScript &script_;

       bool running_;                               


       std::list<std::string> *output_;             


       size_t lineNumber_;                          
                                                                                                    
       bool   isLast_;                              



       std::map<Statement*, bool>  activationMap_;  









       std::string buffer1_, buffer2_;              

       std::string *pattern_;                       


       int maxWhileIterations_;                     



       ScriptRuntimeContext(CompiledScript &s)
       : script_(s)
       , running_(false)
       , output_(0)
       , lineNumber_(0)
       , isLast_(false)
       , pattern_(&buffer1_)
       , maxWhileIterations_(1000 * 1000)
       {
       }

       void stop() 
       {
          running_ = false;  // the apply() functions set this to true
       }

       void start() 
       {
          running_ = true;
       }

       bool running() const
       {
           return running_;
       }


       bool ok() const { return script_.ok(); }     


       std::string const &error() const { return script_.error(); }

       std::string *patternBuffer()
       {
           return pattern_;
       }

       std::string *holdBuffer()
       {


           if(pattern_ == &buffer1_)
              return &buffer2_;

           return &buffer1_;
       }

       void bufferSwap()
       {

          if(pattern_ == &buffer1_)
             pattern_ = &buffer2_;
          else
             pattern_ = &buffer1_;
         
       }

       void hold()
       {
           *holdBuffer() = *patternBuffer();
       }

       void Hold()
       {
          // a script will typically not execute H until it has first executed h

          *holdBuffer() += '\n';
          *holdBuffer() += *patternBuffer();
       }

       void get()
       {
          *patternBuffer() = *holdBuffer();
       }

       void Get()
       {
          *patternBuffer() += '\n';
          *patternBuffer() += *holdBuffer();
       }

       int maxWhileIterations() const { return maxWhileIterations_; }

       void setMaxWhileIterations(int count) { maxWhileIterations_ = count; }




       void print(bool firstLineOnly);  






       bool execute(std::string const &currentLine, 
                    size_t             lineNumber, 
                    bool               isLast, 
                    std::list<std::string> &tmp,
                    ActivationMap          *activationMap
                   )
       {
          if(!ok())
              return false;

          output_          = &tmp;

          *patternBuffer() = currentLine;
          lineNumber_      = lineNumber;
          isLast_          = isLast;

          running_ = true;  // the q command will call stop() to set this to false.

          return script_.execute(this);
       }


    };  // struct ScriptRuntimeContext

//========================================================================================

    template<class StringContainer1, class StringContainer2>
    std::string apply(CompiledScript          &script,
                      StringContainer1 const  &input,
                      StringContainer2        &output,
                      int                      maxIter=0
                     )
    {



      ScriptRuntimeContext context(script);
      ActivationMap        activationMap;

      if(!context.ok())
          return context.error(); //  check the script's error if you get false here
      

      if(maxIter)
         context.setMaxWhileIterations(maxIter);

      std::string currentLine;

      size_t lineNo = 1;



      output.clear();


      typename StringContainer1::const_iterator first =input.begin(),
                                                last  = input.end();

      if(first == last)
         return std::string();  // success

      context.start();


      do
      {
          currentLine =  *first++;

          bool eof = (first == last);

          if(apply(context, currentLine, lineNo, eof, output, &activationMap))
          {
             if(!context.running())
                  break;
          }

          ++lineNo;

      }
      while(first != last);

      return std::string();  // success

    }  // apply()

//========================================================================================

    template<class ScriptContainer, class StringContainer1, class StringContainer2>
    std::string apply(ScriptContainer const  &scriptText, 
                      StringContainer1 const &input,
                      StringContainer2       &output,
                      int                     maxIter=0
                     )

    {
        CompiledScript script(scriptText);

        if(!script.ok())
          return script.error();

        apply(script, input, output, maxIter);

        return std::string();

    }

//========================================================================================

    template<class StringContainer1, class StringContainer2>
    std::string oneLiner(std::string      const &scriptText, 
                         StringContainer1 const &input,
                         StringContainer2       &output,
                         int                     maxIter=0
                        )

    {
        std::list<std::string>  scriptContainer;

        scriptContainer.push_back(scriptText);

        CompiledScript script(scriptContainer);

        if(!script.ok())
            return script.error();

        apply(scriptContainer, input, output, maxIter);

        return std::string();

    }

//========================================================================================

   template<class StringContainer>
   bool apply(ScriptRuntimeContext &context, 
              std::string const    &currentLine,
              size_t                lineNumber,
              bool                  isLast,
              StringContainer      &output,
              ActivationMap        *activationMap
             )
   {
       
       std::list<std::string> tmp;

       bool rv = context.execute(currentLine, lineNumber, isLast, tmp, activationMap);

       CXXTLS_FOREACH(std::string const &outputString, tmp)
       {
          output.push_back(outputString);
       }

       return rv;

   }









}; // namespace muSED

}; // namespace cxxtls