[
  { type: 'paren',  value: '('        },
  { type: 'name',   value: 'add'      },
  { type: 'number', value: '2'        },
  { type: 'paren',  value: '('        },
  { type: 'name',   value: 'subtract' },
  { type: 'number', value: '4'        },
  { type: 'number', value: '2'        },
  { type: 'paren',  value: ')'        },
  { type: 'paren',  value: ')'        },
]

{
  type: 'Program',
  body: [{
    type: 'CallExpression',
    name: 'add',
    params: [{
      type: 'NumberLiteral',
      value: '2',
    }, {
      type: 'CallExpression',
      name: 'subtract',
      params: [{
        type: 'NumberLiteral',
        value: '4',
      }, {
        type: 'NumberLiteral',
        value: '2',
      }]
    }]
  }]
}

{
  type: 'NumberLiteral',
  value: '2',
}

{
  type: 'CallExpression',
  name: 'subtract',
  params: [...nested nodes go here...],
}

{
  type: 'Program',
  body: [{
    type: 'CallExpression',
    name: 'add',
    params: [{
      type: 'NumberLiteral',
      value: '2'
    }, {
      type: 'CallExpression',
      name: 'subtract',
      params: [{
        type: 'NumberLiteral',
        value: '4'
      }, {
        type: 'NumberLiteral',
        value: '2'
      }]
    }]
  }]
}

var visitor = {
  NumberLiteral() {},
  CallExpression() {},
};

var visitor = {
  NumberLiteral(node,parent) {},
  CallExpression(node,parent) {},
}

- Program
  - CallExpression
    - NumberLiteral
    - CallExpression
      - NumberLiteral
      - NumberLiteral

-> Program (enter)
  -> CallExpression (enter)
    -> Number Literal (enter)
    <- Number Literal (exit)
    -> Call Expression (enter)
       -> Number Literal (enter)
       <- Number Literal (exit)
       -> Number Literal (enter)
       <- Number Literal (exit)
    <- CallExpression (exit)
  <- CallExpression (exit)
<- Program (exit)

var visitor = {
    NumberLiteral: {
        enter(node, parent){},
        exit(node, parent){},
    }
}

/**
 * ============================================================================
 *                                   (/^▽^)/
 *                                THE TOKENIZER!
 * ============================================================================
 */
// 我们将从解析的第一阶段开始，使用`Tokenizers`的 `lexical analysis`词法分析。

//我们需要做的只是把字符串形式的代码划分成tokens数组

/*
*   (add 2 (subtract 4 2))   =>   [{ type: 'paren', value: '(' }, ...]
*/

// tokennizer分析器
function tokenizer(input){
    // 一个 current 变量作为指针跟踪我们当前位置
    let current = 0;

    // 一个 tokens 数组收集所有tokens
    let tokens = [];

    //我们首先创建一个“while”循环，
    //在其中设置我们的“current”变量，
    //使其在循环“内部”随心所欲地递增。
    
    //我们这样做是因为我们可能想要在一个循环中多次增加 current
    //因为我们的tokens可以是任何长度。
    while (current < input.length){

        // 我们还需要储存在input中,当前current指向的字符
        let char = input[current]

        // 我们首先想要检查的是一个开括号, 
        // 括号一会儿将用于 CallExpression
        // 但现在我们只关心字符
        if( char === '(' ){
            
            // 如果为真,我们push一个类型为 `paren` 的新token, 并设置为一个开括号
            tokens.push({
                type: 'paren',
                value: '(',
            });

            // 然后current指针移动
            current++;

            // 然后继续下一轮循环,相当于已记录为'(',去下一个字符
            continue;
        }

        // 接下来我们检查闭括号,和上面一样
        if( char ===')' ){
            tokens.push({
                type: 'paren',
                value: ')',
            })

            current++;
            continue;
        }

        // 继续, 我们现在来检查空格, 这很有趣，因为我们关心空格是否存在 用于分隔字符，
        // 但将其存储为令牌实际上并不重要。我们只会在以后把它扔掉。

        // 因此, 我们只需要测试空格是否存在,然后continue,并不需要存入tokens
        let WHITESPACE = /\s/;
        if (WHITESPACE.test(char)){
            current ++;
            continue;
        }

        // 下一种类型的令牌是number。这与我们之前看到的不同，
        // 因为一个数字可以是任意数量的字符，我们希望将整个字符序列捕获为一个令牌。
        /* (add 123 456)
                ^^^ ^^^
                Only two separate tokens
        */

        //因此我们需要从遇到序列中的第一个number开始
        let NUMBERS = /[0-9]/;
        if (NUMBERS.test(char)){

            //我们需要创建一个value字符串预存将要push的数据
            let value = '';
            // 然后，我们将循环序列中的每个字符，直到遇到一个不是数字的字符，
            // 将每个是数字的字符推到我们的“值”，并在此过程中current++。
            while(NUMBERS.test(char)){
                value += char;
                current++;
                char = input[current]
            }

            // 最后我们把number加入到tokens数组
            tokens.push({
                type: 'number',
                value
            })

            continue;
        }

        // 我们还将添加语言中对字符串的支持,即任何被 "" 包裹的字符串
        /*(concat "foo" "bar")
                   ^^^   ^^^ string tokens
        */
       // 我们需要检查双引号的开始
       if(char ==='"' ){
            //维护一个value变量预存数据
            let value = '';

            // 在tokens中跳过开头的",不存储进去
            char = input[++current];

            // 然后开始遍历每个字符直到遇到另一个双引号
            while(char != '"'){
                value += char;
                char = input[++current];
            }

            // 同样,需要跳过最后的 ",让current直接指向下一个char
            char = input[++current];

            // 最后把string加入到tokens数组
            tokens.push({
                type: 'string',
                value
            })

            continue;
       }

        // 最后一种类型的token是name, 这是一个由字母组成的序列
        // 它们是 lisp 语法中的函数名,如下
        /*(add 2 4)
            ^^^
            Name token
        */

        let LETTERS = /[a-z]/i;
        if (LETTERS.test(char)){
            let value = '';

            while(LETTERS.test(char)){
                value += char;
                char = input[++current];
            }
        
            tokens.push({
                type: 'name',
                value
            });

            continue;
        }

        // 最后如果到现在还没匹配到当前字符,将会抛出一个错误
        throw new TypeError('I dont know what this character is:' + char)
    }

    return tokens
}


/**
 * ============================================================================
 *                                 ヽ/❀o ل͜ o\ﾉ
 *                                THE PARSER!!!
 * ============================================================================
 */
// 接下来我们将要把tokens数组转化为AST抽象语法树
/*
*   [{ type: 'paren', value: '(' }, ...]   =>   { type: 'Program', body: [...] }
*/
// parser解析器
function parser(tokens){
    // 我们再次维护一个current变量作为指针
    let current = 0;

    // 但是这次我们将要使用递归代替while循环,因此需要一个walk函数
    function walk() {

        // 在递归函数内我们从拿到current指向的token开始
        let token = tokens[current];

        // 我们将把每种类型的token划分到不同路径中,
        // 这里从number开始
        // 我们测试一下看看类型是否为number
        if (token.type === 'number'){

            // 如果是,让current指向下一个token
            current++;

            // 然后我们返回一个新的AST节点名叫"NumberLiteral"
            // 并且把token的value值附给他的value
            return{
                type: 'NumberLiteral',
                value: token.value,
            };
        }

        // 如果是string类型,则创建一个`StringLiteral`节点
        if (token.type === 'string'){
            current++;
            
            return {
                type: 'StringLiteral',
                value: token.value,
            }
        }

        // 接下来我们将寻找CalExpressions, 我们从碰到开括号`(`开始
        if( token.type === 'paren' && token.value === '('){

            // 还记得吗? 上面我们在组成tokens的时候,
            // 如果遇到字符串,需要忽略第一个和最后一个 `"`
            // 这里也一样,我们只关心括号内的内容,不需要存入括号本身

            //跳过括号
            token = tokens[++current];

            // 我们创建了一个类型为' CallExpression '的基节点，
            // 我们将其名称设置为当前令牌的值，
            // 因为开括号后的下一个令牌是函数的名称。

            let node = {
                type: 'CallExpression',
                name: token.value,
                params: [],
            };

            // 我们移动current跳过函数名name
            token = tokens[++current];

            // 现在我们要循环遍历每一个token,这些token将是CallExpression的params
            // 知道我们遇到一个闭括号 `)`

            // 我们将依靠递归来求解。而不是试图解析一组可能无限嵌套的节点

            //为了解释这一点，让我们以我们的Lisp代码为例。你可以看到' add '的参数是一个数字和一个嵌套的' CallExpression '，其中包括它自己的数字。
            // (add 2 (subtract 4 2))

        /*
            [
                { type: 'paren', value: '(' },
                { type: 'name', value: 'add' },
                { type: 'number', value: '2' },
                { type: 'paren', value: '(' },
                { type: 'name', value: 'subtract' },
                { type: 'number', value: '4' },
                { type: 'number', value: '2' },
                { type: 'paren', value: ')' },
                { type: 'paren', value: ')' }
            ]
        */

            // 我们将会依靠嵌套walk()函数来移动current指针变量遍历所有嵌套的`CallExpression`
            
            // 因此我们执行一个while循环持续添加token到params中作为参数

            while(
                (token.type !== 'paren') || 
                (token.type === 'paren' && token.value !== ')')
            ){
                // 我们将调用walk()函数返回一个节点,并把它push到node.params中
                node.params.push(walk())
                token = tokens[current];
            }

            // 参数遍历完毕,我们最后移动current一次来跳过右括号 `)`
            current++;

            // 返回这个函数node
            return node;
        }

        // 如上,如果我们到现在还有未识别的token,就抛出一个错误
        throw new TypeError(token.type)
    }

    // 现在,我们将要从一个type为Program的根节点开始创建我们的AST

    let ast = {
        type: "Program",
        body: [],
    };

    // 然后我们启动walk()函数把节点都push到ast.body数组中
    // 我们在循环中这样做的原因是我们的程序可以一个接一个地使用“CallExpression”，而不是被嵌套。

    while(current < tokens.length){
        ast.body.push(walk())
    }

    // 最后返回所生成的AST
    return ast;
}



/**
 * ============================================================================
 *                                 ⌒(❀>◞౪◟<❀)⌒
 *                               THE TRAVERSER!!!
 * ============================================================================
 */

// 现在我们有了AST,并且我们希望能够访问不同的节点. 
// 我们需要能够在遇到匹配类型的节点时调用访问器上的方法
/*  *  traverse(ast, {
    *     Program: {
    *       enter(node, parent) {
    *         // ...
    *       },
    *       exit(node, parent) {
    *         // ...
    *       },
    *     },
    *
    *     CallExpression: {
    *       enter(node, parent) {
    *         // ...
    *       },
    *       exit(node, parent) {
    *         // ...
    *       },
    *     },
    *
    *     NumberLiteral: {
    *       enter(node, parent) {
    *         // ...
    *       },
    *       exit(node, parent) {
    *         // ...
    *       },
    *     },
    *   });
    */

// 因此我们定义了一个traverser函数来接收一个AST,和一个visitor
// 在访问器函数内我们需要定义两个函数...
function traverser(ast, visitor) {

    // 定义一个' traverseArray '函数，它允许我们遍历一个数组，
    // 并调用我们将定义的下一个函数:' traverseNode '。
    function traverseArray(array, parent) {
        array.forEach(child => {
            traverserNode(child, parent);
        })
    }

    // 定义一个' traverseNode '函数,接收一个node和它的父节点parent,
    // 这样可以把他俩都传递给我们的访问器方法
    function traverseNode(node, parent){

        // 我们首先测试访问器上是否存在一个具有匹配“类型”的方法。
        let mothods = visitor[node.type];

        // 如果对于此节点存在匹配的方法,我们就调用它
        if(methods && methods.enter){
            methods.enter(node, parent);
        }

        // 接下来我们按照节点类型进行拆分
        switch(node.type){

            // 我们将从顶层的“Program”开始。
            // 由于程序节点有一个名为body的属性，该属性有一个节点数组，
            // 我们将调用' traverseArray '向下遍历它们。

            // (请记住，' traverseArray '将依次调用' traverseNode'，
            // 因此我们将导致AST被递归遍历

            case 'Program':
                traverseArray(node.body, node);
                break;
            
            // 接下来对 `CallExpression`做同样的事并遍历其params
            case 'CallExpression':
                traverseArray(node.params, node);
                break;

            // 对于`NumberLiteral` 和 `StringLiteral`,没有子节点需要访问,所以直接break
            case 'NumberLiteral':
            case 'StringLiteral':
                break;

            // 同样,如果没有识别到该类型则抛出错误
            default:
                throw new TypeError(node.type)
        }


        //如果该节点类型有一个“exit”方法，我们将用“node”和它的“parent”来调用它。

        if(methods && methods.exit){
            methods.exit(node, parent)
        }
    }

    // 最后我们通过对ast调用traverseNode来启动,ast没有父节点,所以传入null
    traverseNode(ast, null)
}


/**
 * ============================================================================
 *                                   ⁽(◍˃̵͈̑ᴗ˂̵͈̑)⁽
 *                              THE TRANSFORMER!!!
 * ============================================================================
 */
// 接下来是转化器。我们的转换器将获取我们已经构建的AST，
// 并将其传递给带有visitor的遍历函数，并将创建一个新的AST。
/*----------------------------------------------------------------------------
 *   Original AST                     |   Transformed AST
 * ----------------------------------------------------------------------------
 *   {                                |   {
 *     type: 'Program',               |     type: 'Program',
 *     body: [{                       |     body: [{
 *       type: 'CallExpression',      |       type: 'ExpressionStatement',
 *       name: 'add',                 |       expression: {
 *       params: [{                   |         type: 'CallExpression',
 *         type: 'NumberLiteral',     |         callee: {
 *         value: '2'                 |           type: 'Identifier',
 *       }, {                         |           name: 'add'
 *         type: 'CallExpression',    |         },
 *         name: 'subtract',          |         arguments: [{
 *         params: [{                 |           type: 'NumberLiteral',
 *           type: 'NumberLiteral',   |           value: '2'
 *           value: '4'               |         }, {
 *         }, {                       |           type: 'CallExpression',
 *           type: 'NumberLiteral',   |           callee: {
 *           value: '2'               |             type: 'Identifier',
 *         }]                         |             name: 'subtract'
 *       }]                           |           },
 *     }]                             |           arguments: [{
 *   }                                |             type: 'NumberLiteral',
 *                                    |             value: '4'
 * ---------------------------------- |           }, {
 *                                    |             type: 'NumberLiteral',
 *                                    |             value: '2'
 *                                    |           }]
 *  (sorry the other one is longer.)  |         }
 *                                    |       }
 *                                    |     }]
 *                                    |   }
 * ----------------------------------------------------------------------------
 */

// 所以我们创建一个接收lispAST的转化器函数
function transformer(ast){

    // 接下来我们将创建一个新AST,它像我们之前创建的AST一样,有一个Program节点

    let newAst = {
        type: 'Program',
        body: [],
    };

    // 接下来我要耍点小聪明，创建一个小hack。
    // 我们将在父节点上使用名为context的属性我们将把节点推到它们的父节点的context中。
    // 通常你会有一个比这个更好的抽象，但为了我们的目的，这样可以使事情简单。

    // 请注意，context是一个从旧ast到新ast的引用。
    // 意味着我们在旧ast上操作context,实际上也在操作新ast的body
    ast._context = newAst.body;

    // 我们从一个traverser函数开始,传入一个旧ast和一个visitor
    traverser(ast, {

        // 第一个访问器方法接收所有的NumberLiteral
        NumberLiteral: {
            enter(node, parent){

                //我们将创建一个同样名为' NumberLiteral '的新节点，我们将把它push到父上下文context。
                parent._context.push({
                    type: 'NumberLiteral',
                    value: node.value
                })
            }
        }

        // 接下来是`StringLiteral`
        StringLiteral: {
            enter(node, parent){
                parent._context.push({
                    type: 'StringLiteral',
                    value: node.value,
                });
            }
        }

        // 然后是`CallExpression`
        CallExpression: {
            enter(node, parent){

                // 我们开始创建一个带有嵌套的`Identifier`的新`CallExpression`节点
                let expression = {
                    type: 'CallExpression',
                    callee: {
                        type: 'Identifier',
                        name: node.name,
                    },
                    arguments: [],
                }

                // * 接下来我们将在原`CallExpression`定义一个新的上下文,
                // 他将引用expression的参数,以便我们可以push参数(著名的函数作用域)
                node._context = expression.arguments;

                // 然后我们将要检查父节点是否为`CallExpression`.
                // 如果不是...
                if(parent.type !== 'CallExpression'){

                    // 我们要用一个" ExpressionStatement "来包装" CallExpression "节点。
                    // 我们这样做是因为JavaScript中的顶层' CallExpression '实际上是语句。
                    expression = {
                        type: 'ExpressionStatement',
                        expression: expression,
                    }
                }

                // 最后，我们push我们的(可能是包装好的)' CallExpression '到parent的“上下文”。
                parent._context.push(expression);
            }
        }
    })

    //在我们的transformer函数结束时，我们将返回我们刚刚创建的新ast。
    return newAst;
}


/**
 * ============================================================================
 *                               ヾ（〃＾∇＾）ﾉ♪
 *                            THE CODE GENERATOR!!!!
 * ============================================================================
 */
// 现在,让我们进入最后一个阶段: 代码生成器

//我们的代码生成器将会递归自调用,将AST中每个节点打印成一个巨大的字符串
function codeGenerator(node){

    // 我们将按照节点的类型来分解
    switch(node.type){

        // 如果我们有一个' Program '节点。我们将映射“body”中的每个节点，
        // 并通过代码生成器运行它们，并用换行符将它们连接起来。
        case 'Program':
            return node.body.map(codeGenerator) //等同于.map(item => codeGenerator(item))
                .join('\n');

        // 对于' ExpressionStatement '，我们将调用嵌套表达式上的代码生成器，并添加一个分号…
        case 'ExpressionStatement':
            return (
                codeGenerator(node.expression) + ';'
            );

        // 对于'CallExpression'，我们将打印'callee'，添加一个开括号，映射' arguments '数组中的每个节点，
        // 并在代码生成器中运行它们，用逗号连接它们，然后我们将添加一个闭括号。
        case 'CallExpression':
            return (
                codeGenerator(node.callee) +
                '(' + 
                node.arguments.map(codeGenerator)
                    .join(', ') + 
                ')'
            )

        // 对于`Indentifier`,只需要return节点的name
        case 'Indentifier':
            return node.name;
        
        // 对于`NumberLiteral`,只需return节点的value
        case 'NumberLiteral':
            return node.value;

        // 对于`StringLiteral`,只需要给节点的value包裹双引号
        case 'StringLiteral':
            return '"' + node.value + '"';

        // 最后如果有没有识别到的node, 就抛出错误
        default:
            throw new TypeError(node.type);
    }
}

/**
 * ============================================================================
 *                                  (۶* ‘ヮ’)۶”
 *                         !!!!!!!!THE COMPILER!!!!!!!!
 * ============================================================================
 */

//  终于!我们将创建“compiler”函数。在这里，我们将把管道的每个部分连接在一起。
/* 
 *   1. input  => tokenizer   => tokens
 *   2. tokens => parser      => ast
 *   3. ast    => transformer => newAst
 *   4. newAst => generator   => output
*/

function compiler(input){
    let tokens = tokenizer(input);
    let ast    = parser(tokens);
    let newAst = transformer(ast);
    let output = codeGenerator(newAst);

    return output;
}

/**
 * ============================================================================
 *                                   (๑˃̵ᴗ˂̵)و
 * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!YOU MADE IT!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 * ============================================================================
 */

// Now I'm just exporting everything...
module.exports = {
    tokenizer,
    parser,
    traverser,
    transformer,
    codeGenerator,
    compiler,
  };