SetLoad.cpp

/* Transform the Set and Load commands into pure TM commands.
 *
 * The Set command uses the syntax Set [symbol], which loads
 * the specified symbol into the register @Var. You can then
 * use @Var in places where a symbol would be expected. For
 * example:
 *
 *    If @Var Goto Start
 *    Write @Var
 *
 * The Load command loads the currently-scanned TM symbol
 * into @Var.
 *
 * Internally, these work by cloning the entire (!!) program
 * multiple times, once for each legal value of @Var, and
 * adding Gotos to link them together. This can substantially
 * increase the size of the TM, but not by an unbounded
 * amount.
 *
 * We support the "base character set": all printable ASCII
 * characters, plus space, plus tab, plus newline, and
 * the Blank symbol.
 *
 * When nothing has been loaded into @Var, it defaults to
 * Blank.
 *
 * To produce a smaller generated universal TM, we also
 * have the special command LoadLabel, which is like Load
 * but only works if the underlying character is something
 * that can go into a label name.
 */

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <map>
#include <set>
#include <cctype>
#include <iomanip>
#include "Turing/StrUtils/StrUtils.h"
using namespace std;

namespace {
    /* Removes comments and leading/trailing whitespace.
     * Comments begin with the # character. We have to be
     * careful when implementing this to make sure that we
     * don't treat the quoted string '#' as a comment.
     */
    void cleanLine(string& line) {
        /* Search for a comment. This will find the first # mark. It might be
         * in quotes, in which case we should ignore it
         * and search again.
         */
        size_t comment = line.find('#');
        if (comment != string::npos &&
            comment != 0 && comment + 1 != line.size() &&
            line[comment - 1] == '\'' &&
            line[comment + 1] == '\'') {
            /* Look for the next one. */
            comment = line.find(comment + 1);
        }

        /* Now if we have a hash mark, it's definitely a comment. */
        if (comment != string::npos) {
            line.erase(comment);
        }
        
        line = Utilities::trim(line);
    }
    
    /* Information needed to do the translation. This consists of:
     *
     * 1. The program itself. We need to insert new labels as jump
     *    points and need to be able to read the whole program to
     *    clone it multiple times.
     *
     * 2. A map from line numbers to the jump point associated with
     *    that line number. For example, the line "If 'a' Set 'a'" will
     *    have a jump label right after it so that we can conditionally
     *    jump to different copies of the program for different values
     *    of @Var.
     */
    struct ProgramData {
        vector<string> lines;
        map<size_t, string> jumpPoints;
    };
    
    /* Processes the program given to stdin and loads the relevant
     * information.
     */
    ProgramData loadProgram() {
        ProgramData result;
        int nextJumpPoint = 0;
    
        for (string line; getline(cin, line); ) {
            /* Skip blank lines. */
            cleanLine(line);
            if (line.empty()) continue;
            
            /* Always add the line to the stored program. */
            result.lines.push_back(line);
            
            /* If this line contains Set or Load, we need to insert a jump point
             * right after it.
             *
             * There are several forms this could take:
             *
             *   1. Unconditional sets/loads:
             *         Set 'a'
             *         Load Blank
             *   2. Conditional sets/loads:
             *         If 'a' Set 'x'
             *         If Not 'b' Load
             *
             * The "right" way to do this would be to parse the line into a usable
             * format and then match on the type. The "hacky but hey it works so
             * let's ship it" way we actually do this is the following: just look
             * for Set or Load. To avoid false positives with labels or Goto targets,
             * we need to rule out the possibility that we have a Goto or a label.
             */
            if (!line.contains("Goto") && line.back() != ':' &&
                (line.contains("Set") || line.contains("Load") || line.contains("LoadLabel"))) {
                result.jumpPoints[result.lines.size() - 1] = "_JumpPoint" + to_string(nextJumpPoint++);
                
                /* Now add the label to the output stream. */
                result.lines.push_back(result.jumpPoints[result.lines.size() - 1] + ":");
            }
        }
        
        return result;
    }
    
    /* Returns the set of all legal characters that can be in @Var. */
    set<char> legalVarValues() {
        set<char> result;
        for (int i = 0; i < 128; i++) {
            if (i == 0 || i == '\n' || i == ' ' || i == '\t' || isprint(i)) {
                result.insert(i);
            }
        }
        return result;
    }
    
    /* Returns the set of all legal characters that can be in a label. */
    set<char> legalLabelValues() {
        set<char> result;
        for (int i = 0; i < 128; i++) {
            if (isalnum(i) || i == '_') {
                result.insert(i);
            }
        }
        return result;
    }
    
    /* Given a character, converts it to a symbol. */
    string encodeSymbol(char ch) {
        if (ch == 0)    return "Blank";
        if (ch == '\n') return "'\\n'";
        if (ch == '\t') return "'\\t'";
        if (ch == '\\') return "'\\\\'";
        if (ch == '\'') return "'\\''";
        else return '\'' + string(1, ch) + '\'';
    }
    
    /* Replaces all instances of @Var with the proper character. */
    void replaceVarsIn(string& line, char ch) {
        /* Replace all instances of @Var. We could do this more efficiently but these
         * strings are short.
         */
        for (size_t loc = line.find("@Var"); loc != string::npos; loc = line.find("@Var")) {
            line.replace(loc, 4, encodeSymbol(ch));
        }
    }
    
    /* Given a symbol encoded as a string, decodes it to its underlying char. */
    char decodeSymbol(const string& symbol) {
        /* Special cases. */
        if (symbol == "Blank")  return 0;
        if (symbol == "'\\n'")  return '\n';
        if (symbol == "'\\t'")  return '\t';
        if (symbol == "'\\\\'") return '\\';
        if (symbol == "'\\''")  return '\'';
        
        /* Otherwise we should have length three with something in the middle and
         * quotes on the outside.
         */
        if (symbol.length() != 3 || symbol.front() != '\'' || symbol.back() != '\'') {
            throw invalid_argument("Unknown symbol: " + symbol);   
        }
        
        return symbol[1];
    }
    
    /* Generates code for a load. */
    void generateLoad(size_t lineNumber, const string& line, size_t index,
                      char ch, const ProgramData& data, const set<char>& legalValues) {
        /* There are three ways these statements can be structued.
         *
         * 1. Unconditional loads:
         *       Load
         * 2. If loads:
         *       If 'a' Load
         * 3. If Not loads:
         *       If Not 'a' Load
         *
         * For cases (2) and (3), we'll rewrite the If statement to jump to the jump target
         * for the current character value if the condition fails, then fallthrough to the
         * traditional case.
         */
        if (line.starts_with("If")) {
            /* See if there's a negation in there. We know we start with If and that the end
             * is a Load, so we can just see if "Not" is in there.
             */
            auto notIndex = line.find("Not");
                        
            /* Decode the symbol in this line. It will be after the If (or Not, if there is one)
             * and before the Load.
             */
            size_t startIndex = (notIndex != string::npos? notIndex + 3 : 2);
            string symbol = Utilities::trim(string(line.begin() + startIndex, line.begin() + index));
                        
            /* Output a jump around this line. */
            cout << "If " << (notIndex == string::npos? "Not " : "") << symbol
                 << " Goto _V" << int(ch) << "_" << data.jumpPoints.at(lineNumber) << endl;
        }
                    
        /* Now, for each symbol, insert an If and a jump on that symbol. */
        for (char nextCh: legalValues) {
             cout << "If " << encodeSymbol(nextCh) << " Goto _V" << int(nextCh) << "_" << data.jumpPoints.at(lineNumber) << endl;
        }
        /* In case something slips through. */
        cout << "Return False" << endl;
    }
    
    void generateProgram(const ProgramData& data) {
        /* Clone the program once per legal value of @Var. */
        for (char ch: legalVarValues()) {
            for (size_t lineNumber = 0; string line: data.lines) {
                /* First, replace all instances of @Var with what the actual value is. */
                replaceVarsIn(line, ch);
            
                /* We need to figure out what kind of line this is to determine what to do with it. */

                /* Labels must be prefixed with _V[numeric value of ch]_ so that we can track what @Var
                 * is.
                 */
                if (line.back() == ':') {
                    cout << "_V" << int(ch) << "_" << line << endl;
                }
                /* Anything containing a Goto needs to be redirected to the proper label. */
                else if (auto index = line.find("Goto"); index != string::npos) {
                    string target = Utilities::trim(line.substr(index + 4));
                    line.erase(index + 4);
                    line += " _V" + to_string(int(ch)) + "_"  + target;
                    cout << line << endl;
                }
                /* Set statements are handled by jumping to the appropriate jump target. */
                else if (auto index = line.find("Set"); index != string::npos) {
                    /* Decode the symbol to load. */
                    int target = decodeSymbol(Utilities::trim(line.substr(index + 3)));
                    
                    /* Jump to the appropriate jump target. */
                    line.erase(index);
                    
                    line += "Goto _V" + to_string(target) + "_" + data.jumpPoints.at(lineNumber);
                    cout << line << endl;
                    
                }
                /* Load[Label] statements are trickier; we basically need to do a cascade of if
                 * statements to produce the correct output.
                 *
                 * Check for LoadLabel first because we don't want "Load" to match LoadLabel.
                 */
                else if (auto index = line.find("LoadLabel"); index != string::npos) {
                    generateLoad(lineNumber, line, index, ch, data, legalLabelValues());               
                }
                else if (auto index = line.find("Load"); index != string::npos) {
                    generateLoad(lineNumber, line, index, ch, data, legalVarValues());               
                }
                /* Everything else renders as-is. */
                else {
                    cout << line << endl;
                }
                
                lineNumber++;
            }
            
            /* Output a 'return false' here in case we fall off the bottom. */
            cout << "Return False" << endl;
        }
    }
}

int main() {
    /* Step 1: Load the program into memory. */
    auto data = loadProgram();
    
    /* Step 2: Generate multiple copies of the program, each based on different values of @Var. */
    generateProgram(data);
    
    /* Finally, since we no longer have a Start label, add one and have it jump to _V0_Start, the
     * entry point for when @Val is Blank.
     */
    cout << "Start:" << endl;
    cout << "    Goto _V0_Start" << endl;
}