/******************************************************************************
 * File: kleene.cpp
 * Author: Keith Schwarz (htiek@cs.stanford.edu)
 *
 * A program that uses a special case of Kleene's Second Recursion Theorem to
 * create programs with access to their own source code.  This program accepts
 * as input a C++ source file, then produces a new C++ source file that
 * exports a function called kleene::MySource() that returns the source code of
 * that new file.  In this way, C++ programs can access and manipulate their
 * own source code at runtime.
 *
 * This is primarily of theoretical interest - I can't imagine any particularly
 * good uses cases for this program - but it is interesting to see how easily
 * we can introduce introspection into a programming language that does not
 * possess it.
 *
 * The idea behind this program is as follows.  Before creating this file, I
 * created a quine program that was able to place its own source code into a
 * string.  The logic behind that program, as is often the logic behind most
 * quines, is as follows:
 *
 * 1. Split the program into three pieces - a beginning, middle, and end.
 * 2. Have the beginning of the code handle necessary boilerplate (includes,
 *    global definitions, etc.
 * 3. Have the middle of the code define a function that creates a list of
 *    strings containing the beginning and end of the program and place it
 *    into some buffer.  Note that this isn't self-referential, since we can
 *    make this code by writing the rest of the program and then placing the
 *    source code for it (suitably escaped) into the middle of the program.
 * 4. Have the end of the code take the code for the beginning and end, then
 *    dynamically create a string representation of code that prints out the
 *    beginning and end.  This is essentially recreating the code for the
 *    middle of the program dynamically.
 *
 * Once I had this program, it was trivial to adopt it to accept arbitrary
 * user programs.  This program works by having a cached copy of the source of
 * the Quine that is then updated by having the user code inserted into it, so
 * that the buffer it produces is equal to the source code of the original
 * Quine with the extra user code injected into that.  Thus, when the user code
 * invokes the kleene::MySource() function, it effectively runs the Quine as a
 * subroutine to build up the program source and hand it back to the user code.
 */

#include <iostream>
#include <fstream>
#include <string>
#include <stdexcept>
#include <vector>
using namespace std;

/* The generated program is split into different pieces:
 * 1. The preamble, containing all of the code up to where we need to print the
 *    user's escaped code.
 * 2. The user's escaped code, used in the printing routine.
 * 3. The middle, containing the remainder of the main code.
 * 4. The user's raw code.
 * 5. The postamble.
 *
 * These functions output each piece.
 */
void PrintPreamble() {
  cout << "/******************************************************************************"<< endl;
  cout << " * An automatically-generated self-referential program generated by kleene."<< endl;
  cout << " * This source file contains a function called kleene::MySource() that produces"<< endl;
  cout << " * a C++ std::string containing the program\'s source code, which can be used"<< endl;
  cout << " * in the remainder of the program."<< endl;
  cout << " *"<< endl;
  cout << " * This program works using a modified version of the construction detailed in"<< endl;
  cout << " * \"Introduction to the Theory of Computation, Second Edition\" by Michael"<< endl;
  cout << " * Sipser in his proof of a special case of Kleene\'s Second Recursion Theorem."<< endl;
  cout << " * In particular, the program works as follows.  We assume that we have the"<< endl;
  cout << " * ability to write a function that, given a program\'s source, produces a new"<< endl;
  cout << " * program that prints out that program\'s source code.  We then produce a"<< endl;
  cout << " * program that given the source code of *some* program, combines the"<< endl;
  cout << " * representation of that program along with a representation of a program that"<< endl;
  cout << " * produces that program.  If we then run this program on its own source, it"<< endl;
  cout << " *"<< endl;
  cout << " * 1. Produces a representation of its own source code."<< endl;
  cout << " * 2. Produces a program that produces a representation of its source code,"<< endl;
  cout << " *    then combines it with a description of a program that prints a"<< endl;
  cout << " *    representation of that source code."<< endl;
  cout << " *"<< endl;
  cout << " * In the case of C++, the \"representation\" of a program is a pair of vectors"<< endl;
  cout << " * of strings, where the concatenation of these vectors represents a program"<< endl;
  cout << " * that takes care of step (2) and has a \"hole\" where the code for (1) should"<< endl;
  cout << " * go.  The program then concatenates together all of the logic for the first"<< endl;
  cout << " * half, then fills in the \"hole\" by producing a program that prints out a" << endl;
  cout << " * representation of a program that prints the source gathered together, and" << endl;
  cout << " * finally prints out the second half of the program.  The user code can then" << endl;
  cout << " * call this function to access the representation." << endl;
  cout << " */" << endl;
  cout << "" << endl;
  cout << "#include <iostream>" << endl;
  cout << "#include <utility>" << endl;
  cout << "#include <string>" << endl;
  cout << "#include <vector>" << endl;
  cout << "#include <sstream>" << endl;
  cout << "" << endl;
  cout << "namespace kleene {" << endl;
  cout << "  /* Private implementation detail namespace; should not be necessary to look" << endl;
  cout << "   * at or modify this code." << endl;
  cout << "   */" << endl;
  cout << "  namespace detail {" << endl;
  cout << "    /* A utility function that prints out the contents of a string, escaping " << endl;
  cout << "     * all quotes and slashes it finds." << endl;
  cout << "     */" << endl;
  cout << "    void OutputEscaped(::std::ostream& out, const ::std::string& line) {" << endl;
  cout << "      out << \'\"\';" << endl;
  cout << "      for (unsigned i = 0; i < line.length(); ++i) {" << endl;
  cout << "        if (line[i] == \'\\\"\')" << endl;
  cout << "          out << \"\\\\\\\"\";" << endl;
  cout << "        else if (line[i] == \'\\\'\')" << endl;
  cout << "          out << \"\\\\\\\'\";" << endl;
  cout << "        else if (line[i] == \'\\\\\')" << endl;
  cout << "          out << \"\\\\\\\\\";" << endl;
  cout << "        else if (line[i] == \'\\t\')" << endl;
  cout << "          out << \"\\\\t\";" << endl;
  cout << "        else" << endl;
  cout << "          out << line[i];" << endl;
  cout << "      }" << endl;
  cout << "      out << \'\"\';" << endl;
  cout << "    }" << endl;
  cout << "  " << endl;
  cout << "    /* This code is automatically generated to place a representation of the" << endl;
  cout << "     * program\'s source into a pair of vectors, as described above." << endl;
  cout << "     */" << endl;
  cout << "    ::std::pair< ::std::vector< ::std::string>, ::std::vector< ::std::string> > PrintThisProgram() {" << endl;
  cout << "      ::std::pair< ::std::vector< ::std::string>, ::std::vector< ::std::string> > result;" << endl;
  cout << "      /* ----- START Escaped copy of the program\'s source code. ----- */" << endl;
  cout << "      result.first.push_back(\"/******************************************************************************\");" << endl;
  cout << "      result.first.push_back(\" * An automatically-generated self-referential program generated by kleene.\");" << endl;
  cout << "      result.first.push_back(\" * This source file contains a function called kleene::MySource() that produces\");" << endl;
  cout << "      result.first.push_back(\" * a C++ std::string containing the program\\\'s source code, which can be used\");" << endl;
  cout << "      result.first.push_back(\" * in the remainder of the program.\");" << endl;
  cout << "      result.first.push_back(\" *\");" << endl;
  cout << "      result.first.push_back(\" * This program works using a modified version of the construction detailed in\");" << endl;
  cout << "      result.first.push_back(\" * \\\"Introduction to the Theory of Computation, Second Edition\\\" by Michael\");" << endl;
  cout << "      result.first.push_back(\" * Sipser in his proof of a special case of Kleene\\\'s Second Recursion Theorem.\");" << endl;
  cout << "      result.first.push_back(\" * In particular, the program works as follows.  We assume that we have the\");" << endl;
  cout << "      result.first.push_back(\" * ability to write a function that, given a program\\\'s source, produces a new\");" << endl;
  cout << "      result.first.push_back(\" * program that prints out that program\\\'s source code.  We then produce a\");" << endl;
  cout << "      result.first.push_back(\" * program that given the source code of *some* program, combines the\");" << endl;
  cout << "      result.first.push_back(\" * representation of that program along with a representation of a program that\");" << endl;
  cout << "      result.first.push_back(\" * produces that program.  If we then run this program on its own source, it\");" << endl;
  cout << "      result.first.push_back(\" *\");" << endl;
  cout << "      result.first.push_back(\" * 1. Produces a representation of its own source code.\");" << endl;
  cout << "      result.first.push_back(\" * 2. Produces a program that produces a representation of its source code,\");" << endl;
  cout << "      result.first.push_back(\" *    then combines it with a description of a program that prints a\");" << endl;
  cout << "      result.first.push_back(\" *    representation of that source code.\");" << endl;
  cout << "      result.first.push_back(\" *\");" << endl;
  cout << "      result.first.push_back(\" * In the case of C++, the \\\"representation\\\" of a program is a pair of vectors\");" << endl;
  cout << "      result.first.push_back(\" * of strings, where the concatenation of these vectors represents a program\");" << endl;
  cout << "      result.first.push_back(\" * that takes care of step (2) and has a \\\"hole\\\" where the code for (1) should\");" << endl;
  cout << "      result.first.push_back(\" * go.  The program then concatenates together all of the logic for the first\");" << endl;
  cout << "      result.first.push_back(\" * half, then fills in the \\\"hole\\\" by producing a program that prints out a\");" << endl;
  cout << "      result.first.push_back(\" * representation of a program that prints the source gathered together, and\");" << endl;
  cout << "      result.first.push_back(\" * finally prints out the second half of the program.  The user code can then\");" << endl;
  cout << "      result.first.push_back(\" * call this function to access the representation.\");" << endl;
  cout << "      result.first.push_back(\" */\");" << endl;
  cout << "      result.first.push_back(\"\");" << endl;
  cout << "      result.first.push_back(\"#include <iostream>\");" << endl;
  cout << "      result.first.push_back(\"#include <utility>\");" << endl;
  cout << "      result.first.push_back(\"#include <string>\");" << endl;
  cout << "      result.first.push_back(\"#include <vector>\");" << endl;
  cout << "      result.first.push_back(\"#include <sstream>\");" << endl;
  cout << "      result.first.push_back(\"\");" << endl;
  cout << "      result.first.push_back(\"namespace kleene {\");" << endl;
  cout << "      result.first.push_back(\"  /* Private implementation detail namespace; should not be necessary to look\");" << endl;
  cout << "      result.first.push_back(\"   * at or modify this code.\");" << endl;
  cout << "      result.first.push_back(\"   */\");" << endl;
  cout << "      result.first.push_back(\"  namespace detail {\");" << endl;
  cout << "      result.first.push_back(\"    /* A utility function that prints out the contents of a string, escaping \");" << endl;
  cout << "      result.first.push_back(\"     * all quotes and slashes it finds.\");" << endl;
  cout << "      result.first.push_back(\"     */\");" << endl;
  cout << "      result.first.push_back(\"    void OutputEscaped(::std::ostream& out, const ::std::string& line) {\");" << endl;
  cout << "      result.first.push_back(\"      out << \\\'\\\"\\\';\");" << endl;
  cout << "      result.first.push_back(\"      for (unsigned i = 0; i < line.length(); ++i) {\");" << endl;
  cout << "      result.first.push_back(\"        if (line[i] == \\\'\\\\\\\"\\\')\");" << endl;
  cout << "      result.first.push_back(\"          out << \\\"\\\\\\\\\\\\\\\"\\\";\");" << endl;
  cout << "      result.first.push_back(\"        else if (line[i] == \\\'\\\\\\\'\\\')\");" << endl;
  cout << "      result.first.push_back(\"          out << \\\"\\\\\\\\\\\\\\\'\\\";\");" << endl;
  cout << "      result.first.push_back(\"        else if (line[i] == \\\'\\\\\\\\\\\')\");" << endl;
  cout << "      result.first.push_back(\"          out << \\\"\\\\\\\\\\\\\\\\\\\";\");" << endl;
  cout << "      result.first.push_back(\"        else if (line[i] == \\\'\\\\t\\\')\");" << endl;
  cout << "      result.first.push_back(\"          out << \\\"\\\\\\\\t\\\";\");" << endl;
  cout << "      result.first.push_back(\"        else\");" << endl;
  cout << "      result.first.push_back(\"          out << line[i];\");" << endl;
  cout << "      result.first.push_back(\"      }\");" << endl;
  cout << "      result.first.push_back(\"      out << \\\'\\\"\\\';\");" << endl;
  cout << "      result.first.push_back(\"    }\");" << endl;
  cout << "      result.first.push_back(\"  \");" << endl;
  cout << "      result.first.push_back(\"    /* This code is automatically generated to place a representation of the\");" << endl;
  cout << "      result.first.push_back(\"     * program\\\'s source into a pair of vectors, as described above.\");" << endl;
  cout << "      result.first.push_back(\"     */\");" << endl;
  cout << "      result.first.push_back(\"    ::std::pair< ::std::vector< ::std::string>, ::std::vector< ::std::string> > PrintThisProgram() {\");" << endl;
  cout << "      result.first.push_back(\"      ::std::pair< ::std::vector< ::std::string>, ::std::vector< ::std::string> > result;\");" << endl;
  cout << "      result.first.push_back(\"      /* ----- START Escaped copy of the program\\\'s source code. ----- */\");" << endl;
  cout << "      result.second.push_back(\"      /* -----  END  Escaped copy of the program\\\'s source code. ----- */\");" << endl;
  cout << "      result.second.push_back(\"      return result;\");" << endl;
  cout << "      result.second.push_back(\"    }\");" << endl;
  cout << "      result.second.push_back(\"  }\");" << endl;
  cout << "      result.second.push_back(\"\");" << endl;
  cout << "      result.second.push_back(\"  /* Function that actually generates the program\\\'s source code. */\");" << endl;
  cout << "      result.second.push_back(\"  ::std::string MySource() {\");" << endl;
  cout << "      result.second.push_back(\"    ::std::stringstream result;\");" << endl;
  cout << "      result.second.push_back(\"    \");" << endl;
  cout << "      result.second.push_back(\"    /* Get a description of some program. */\");" << endl;
  cout << "      result.second.push_back(\"    ::std::pair< ::std::vector< ::std::string>, ::std::vector< ::std::string> > myDescription = \");" << endl;
  cout << "      result.second.push_back(\"        ::kleene::detail::PrintThisProgram();\");" << endl;
  cout << "      result.second.push_back(\"    \");" << endl;
  cout << "      result.second.push_back(\"    /* Print out the preamble by itself. */\");" << endl;
  cout << "      result.second.push_back(\"    for (unsigned i = 0; i < myDescription.first.size(); ++i)\");" << endl;
  cout << "      result.second.push_back(\"      result << myDescription.first[i] << ::std::endl;\");" << endl;
  cout << "      result.second.push_back(\"    \");" << endl;
  cout << "      result.second.push_back(\"    /* Print out the description of a function that would generate all of \");" << endl;
  cout << "      result.second.push_back(\"     * this code.\");" << endl;
  cout << "      result.second.push_back(\"     */\");" << endl;
  cout << "      result.second.push_back(\"    for (unsigned i = 0; i < myDescription.first.size(); ++i) {\");" << endl;
  cout << "      result.second.push_back(\"      result << \\\"      result.first.push_back(\\\";\");" << endl;
  cout << "      result.second.push_back(\"      ::kleene::detail::OutputEscaped(result, myDescription.first[i]);\");" << endl;
  cout << "      result.second.push_back(\"      result << \\\");\\\" << ::std::endl;\");" << endl;
  cout << "      result.second.push_back(\"    }\");" << endl;
  cout << "      result.second.push_back(\"    for (unsigned i = 0; i < myDescription.second.size(); ++i) {\");" << endl;
  cout << "      result.second.push_back(\"      result << \\\"      result.second.push_back(\\\";\");" << endl;
  cout << "      result.second.push_back(\"      ::kleene::detail::OutputEscaped(result, myDescription.second[i]);\");" << endl;
  cout << "      result.second.push_back(\"      result << \\\");\\\" << ::std::endl;\");" << endl;
  cout << "      result.second.push_back(\"    }\");" << endl;
  cout << "      result.second.push_back(\"    \");" << endl;
  cout << "      result.second.push_back(\"    /* Print out the postamble by itself. */\");" << endl;
  cout << "      result.second.push_back(\"    for (unsigned i = 0; i < myDescription.second.size(); ++i)\");" << endl;
  cout << "      result.second.push_back(\"      result << myDescription.second[i] << ::std::endl;\");" << endl;
  cout << "      result.second.push_back(\"    \");" << endl;
  cout << "      result.second.push_back(\"    return result.str();\");" << endl;
  cout << "      result.second.push_back(\"  }\");" << endl;
  cout << "      result.second.push_back(\"}\");" << endl;
  cout << "      result.second.push_back(\"\");" << endl;
  cout << "      result.second.push_back(\"/***** BEGIN User program *****/\");" << endl;
}
void PrintMiddle() {
  cout << "      result.second.push_back(\"/*****  END  User program *****/\");" << endl;
  cout << "      /* -----  END  Escaped copy of the program\'s source code. ----- */" << endl;
  cout << "      return result;" << endl;
  cout << "    }" << endl;
  cout << "  }" << endl;
  cout << "" << endl;
  cout << "  /* Function that actually generates the program\'s source code. */" << endl;
  cout << "  ::std::string MySource() {" << endl;
  cout << "    ::std::stringstream result;" << endl;
  cout << "    " << endl;
  cout << "    /* Get a description of some program. */" << endl;
  cout << "    ::std::pair< ::std::vector< ::std::string>, ::std::vector< ::std::string> > myDescription = " << endl;
  cout << "        ::kleene::detail::PrintThisProgram();" << endl;
  cout << "    " << endl;
  cout << "    /* Print out the preamble by itself. */" << endl;
  cout << "    for (unsigned i = 0; i < myDescription.first.size(); ++i)" << endl;
  cout << "      result << myDescription.first[i] << ::std::endl;" << endl;
  cout << "    " << endl;
  cout << "    /* Print out the description of a function that would generate all of " << endl;
  cout << "     * this code." << endl;
  cout << "     */" << endl;
  cout << "    for (unsigned i = 0; i < myDescription.first.size(); ++i) {" << endl;
  cout << "      result << \"      result.first.push_back(\";" << endl;
  cout << "      ::kleene::detail::OutputEscaped(result, myDescription.first[i]);" << endl;
  cout << "      result << \");\" << ::std::endl;" << endl;
  cout << "    }" << endl;
  cout << "    for (unsigned i = 0; i < myDescription.second.size(); ++i) {" << endl;
  cout << "      result << \"      result.second.push_back(\";" << endl;
  cout << "      ::kleene::detail::OutputEscaped(result, myDescription.second[i]);" << endl;
  cout << "      result << \");\" << ::std::endl;" << endl;
  cout << "    }" << endl;
  cout << "    " << endl;
  cout << "    /* Print out the postamble by itself. */" << endl;
  cout << "    for (unsigned i = 0; i < myDescription.second.size(); ++i)" << endl;
  cout << "      result << myDescription.second[i] << ::std::endl;" << endl;
  cout << "    " << endl;
  cout << "    return result.str();" << endl;
  cout << "  }" << endl;
  cout << "}" << endl;
  cout << "" << endl;
  cout << "/***** BEGIN User program *****/" << endl;
}

void PrintPostamble() {
  cout << "/*****  END  User program *****/" << endl;
  cout << endl;
}

/* A utility function that prints out the contents of a string, escaping all 
 * quotes and slashes it finds.  This logic is necessary for outputting the 
 * escaped version of the user's program source.
 */
void OutputEscaped(ostream& out, string line) {
  out << '"';
  for (size_t i = 0; i < line.length(); ++i) {
    if (line[i] == '\"')
      out << "\\\"";
    else if (line[i] == '\'')
      out << "\\\'";
    else if (line[i] == '\\')
      out << "\\\\";
    else if (line[i] == '\t')
      out << "\\t";
    else
      out << line[i];
  }
  out << '"';
}

/* A utility function to load the user program into a vector of its lines. */
vector<string> ReadUserFile(const char* filename) {
  ifstream input(filename);
  if (!input.is_open())
    throw runtime_error("Can't find file: " + string(filename));

  vector<string> result;
  for (string line; getline(input, line); )
    result.push_back(line);

  return result;
}

int main(int argc, char** argv) try {
  if (argc != 2)
    throw runtime_error("Usage: kleene source-file");

  /* Read the user's file into a list of its lines so we can process it. */
  vector<string> contents = ReadUserFile(argv[1]);

  /* Output the generated file. */
  PrintPreamble();

  /* Output the printing code for the user's file. */
  for (unsigned i = 0; i < contents.size(); ++i) {
    cout << "      result.second.push_back(";
    OutputEscaped(cout, contents[i]);
    cout << ");" << endl;
  }  

  PrintMiddle();

  /* Output the user's code. */
  for (unsigned i = 0; i < contents.size(); ++i)
    cout << contents[i] << endl;

  PrintPostamble();
}
catch (const exception& e) {
  cerr << "Error: " << e.what() << endl;
}