#41 执行任意表达式


  • 0
    administrators

    在开发前端框架、模版引擎的时候,经常会需要我们在特定的上下文中,动态分析、执行特定的表达式。例如:在 { x: 1, y: 2, z: 3 } 的上下文中执行表达式 x + y 那么就会得到 3,执行 z - x 就会得到 2。

    请你完成 execute 函数,接受一个字符串和对象作为参数,它可以在特定的上下文中执行任意的表达式,例如:

    execute(`'My name is ' + name`, { name: 'Jerry' }) // => My name is Jerry
    execute('monkeys.length + 1', { monkeys: [1, 2, 3] }) // => 4
    execute('user.name + user.age', { user: { name: 'Jerry', age: 12 } }) // => Jerry12
    execute('run()', { run: () => 'Good Night' }) // => Good Night
    ...
    

    (你能否想出不使用 with 的方案?)


  • 0

    @胡子大哈 大哈..这道题我是用with 和 eval 解的,虽然成功了,但是记得这两个要少用,有性能问题。也想过正则,但是感觉太过于麻烦。可不可以麻烦您给提供一个其他的答案或者思路。谢谢了。


  • 0
    administrators

    @ackerMan 可以思考一下,看看能不能想出不使用 with 的方法。


  • 0

    想知道 execute 是否有沙箱效果

    我的代码是通过了,但没有作用域保护,

    比如:

    var a = 123
    execute(`'My name is ' + a`, {})  // My name is 123
    

    测试有覆盖这种情况吗?execute 允许访问上层作用域是期望的吗?


  • 0
    administrators

    @Sunjourney 不是期望的,但是没有测试用例没有覆盖。因为覆盖可能会稍微增加这道题的难度,设计的时候希望这道题灵活一点,当初也在权衡这个问题。后续可以开这道题的稍微升级的版本。


  • 0

    @胡子大哈 用 with 的版本感觉和解析 Vue 的 template 里的 directives 的实现挺像的。


  • 0

    既然开了 functional programming 系列,还可以继续加 reactive programming, oop, meta programming,这个就可以移到 meta programming 系列里,感觉用 es6+ 的语法解决这一系列问题会很有意思。


  • 0
    administrators

    @Sunjourney reactive programming 我也不是很了解,一个人的知识还是很有限。这两天准备开放用户出题功能,这位朋友有兴趣的话可以一起来出题。


  • 0

    @胡子大哈 吼啊吼啊!不过感觉写oj specs 对边际条件的要求挺高,好难保证质量


  • 0
    administrators

    @Sunjourney 没关系,大家会反馈的(就像我写 specs 的时候也会有很多问题,靠大家反馈提意见)。说不定未来可以搞成类似 github 那样的开放社区,一起来保证质量。😄


  • 2

    嗯,确实没有用with/eval/new Function

    class Stream {
      constructor(tokens) {
        this.tokens = tokens
        this.pos = 0
      }
      
      get next() {
        return this.tokens[this.pos++] || ''
      }
      
      cancel() {
        this.pos--
      }
      
      get done() {
        return this.pos >= this.tokens.length
      }
      
      get rest() {
        return this.tokens.slice(this.pos)
      }
      
      transaction(fn) {
        const rpos = this.pos
        const ret = fn()
        if (ret === failure) {
          this.pos = rpos
          return failure
        }
        return ret
      }
    }
    
    function preventRec(fn) {
      const stack = []
      return stream => {
        if (stack.includes(stream.pos)) {
          return ignore
        }
        stack.push(stream.pos)
        const ret = fn(stream)
        stack.pop()
        return ret
      }
    }
    
    const failure = Symbol('failure')
    const ignore = Symbol('ignore')
    
    const eq = str => stream => stream.transaction(() => stream.next == str ? ignore : failure)
    
    const re = regex => fn => stream => stream.transaction(() => {
      const ret = stream.next.match(regex)
      if (!ret) return failure
      return fn(ret)
    })
    
    const assembly = (...parsers) => stream => stream.transaction(() => {
      console.log('assembly')
      let result = ignore
      for (const parser of parsers) {
        result = parser(result)(stream)
        if (result == failure)
          return failure
      }
      return result
    })
    
    const chain = (...parsers) => fn => stream => stream.transaction(() => {
      const arr = []
      for (const parser of parsers) {
        const result = parser(stream)
        if (result == failure)
          return failure
        if (result != ignore)
          arr.push(result)
      }
      return fn(...arr)
    })
    
    const choice = (...parsers) => stream => {
      for (const parser of parsers) {
        const result = parser(stream)
        if (result != failure)
          return result
      }
      return failure
    }
    
    const repeatRange = parser => (low, high = Number.MAX_SAFE_INTEGER) => stream => stream.transaction(() => {
      const arr = []
      let i = 0
      for (; i < high; i++) {
        const result = parser(stream)
        if (result == failure)
          break
        if (result != ignore)
          arr.push(result)
      }
      if (i < low || i > high) return failure
      return arr
    })
    
    const repeat = parser => number => repeatRange(parser)(number, number)
    
    const many = parser => repeatRange(parser)(1)
    
    const zeroOrMany = parser => repeatRange(parser)(0)
    
    const maybe = parser => repeatRange(parser)(0, 1)
    
    const must = parser => repeatRange(parser)(1, 1)
    
    const packer = parser => fn => stream => {
      const ret = parser(stream)
      if (ret === failure)
        return failure
      return fn(ret)
    }
    
    const $log = (...param) => stream => {
      //console.log(...param, stream.rest)
      return ignore
    }
    
    const $lazy = fn => a => b => fn(a)(b)
    
    let Parser
    Parser = (() => {
      const number = re(/^\d+(\.\d+)?$/)(x => ({op: 'immi', value: parseFloat(x[0])}))
      const string = re(/^'((?:\\'|[^'])+)'$/)(x => ({op: 'imms', value: JSON.parse(`"${x[1].replace('"', '\\"')}"`)}))
      const name = re(/^\w+$/)(x => x[0])
      let expression
      const variable = chain(
        name,
        zeroOrMany(chain(
          eq('.'),
          name
        )(x => x))
      )((x, xs) => ({op: 'arg', path: [x, ...xs]}))
      const func_call = chain(
        preventRec(s => expression(s)),
        eq('('),
        maybe(
          chain(
            s => expression(s),
            zeroOrMany(
              chain(
                eq(','),
                s => expression(s)
              )(x => x)
            )
          )((x, xs) => [x, ...xs])
        ),
        eq(')')
      )((func, params) => ({op: 'call', func, params: params[0] || []}))
      const factor = choice(
        number,
        string,
        chain(
          eq('('),
          s => expression(s),
          eq(')')
        )(ex => ex),
        func_call,
        variable
      )
      const term = choice(
        chain(
          factor,
          many(
            chain(
              re(/^[*/%]$/g)(x => x[0]),
              factor
            )((...x) => x)
          )
        )((x, xs) => xs.reduce((a, [op, b]) => ({op, a, b}), x)),
        factor
      )
      expression = choice(
        chain(
          term,
          many(
            chain(
              re(/^[+-]$/g)(x => x[0]),
              term
            )((...x) => x)
          )
        )((x, xs) => xs.reduce((a, [op, b]) => ({op, a, b}), x)),
        term
      )
      return expression
    })()
    
    class Compiler {
      compile(code) {
        return this.pass3(this.pass2(this.pass1(code)))
      }
      
      tokenizer(str) {
        return str.match(/(?:'(?:\\'|[^'])+'|[\+\-\*\/\.\(\),]|\w+)/g)
      }
      
      pass1(code) {
        return Parser(new Stream(this.tokenizer(code)))
      }
      
      pass2(ast) {
        const opmap = {
          '+': (a, b) => a + b,
          '-': (a, b) => a - b,
          '*': (a, b) => a * b,
          '/': (a, b) => a / b,
        }
        let simp
        simp = snode => {
          const node = Object.assign({}, snode)
          if (node.op in opmap) {
            node.a = simp(node.a)
            node.b = simp(node.b)
            if (node.a.op == 'immi' && node.b.op == 'immi')
              return {op: 'immi', value: opmap[node.op](node.a.value, node.b.value)}
          } else if (node.op == 'call') {
            node.params = node.params.map(param => simp(param))
          }
          return node
        }
        return simp(ast)
      }
      
      pass3(ast) {
        console.log(JSON.stringify(ast))
        const opmap = {
          '+': node => load => [...load(node.a), 'PUSH', ...load(node.b), 'SWAP', 'POP_', 'ADD_'],
          '-': node => load => [...load(node.a), 'PUSH', ...load(node.b), 'SWAP', 'POP_', 'SUB_'],
          '*': node => load => [...load(node.a), 'PUSH', ...load(node.b), 'SWAP', 'POP_', 'MUL_'],
          '/': node => load => [...load(node.a), 'PUSH', ...load(node.b), 'SWAP', 'POP_', 'DIV_'],
          'immi': node => load => [`IMMI ${node.value}`],
          'imms': node => load => [`IMMS ${node.value}`],
          'arg': node => load => [`ARG_ ${node.path[0]}`, ...node.path.slice(1).map(x => `PROP ${x}`)],
          'call': node => load => [...node.params.map(param => [...load(param), 'PUSH']).reduce((p, c) => [...p, ...c], []), `IMMI ${node.params.length}`, 'SWAP', ...load(node.func), 'CALL']
        }
        let walk
        walk = node => opmap[node.op](node)(walk)
        return walk(ast)
      }
    }
    
    class VM {
      load(code) {
        this.code = code
        return this
      }
      
      execute(variable) {
        let r0, r1
        const stack = []
        const opmap = {
          'ADD_': rest => r0 = r0 + r1,
          'SUB_': rest => r0 = r0 - r1,
          'MUL_': rest => r0 = r0 * r1,
          'DIV_': rest => r0 = r0 / r1,
          'IMMI': rest => r0 = parseFloat(rest),
          'IMMS': rest => r0 = rest,
          'ARG_': rest => r0 = variable[rest],
          'PROP': rest => r0 = r0[rest],
          'CALL': rest => r0 = r0(...[...Array(parseInt(r1))].map(() => stack.pop()).reverse()),
          'PUSH': rest => stack.push(r0),
          'POP_': rest => r0 = stack.pop(),
          'SWAP': rest => {
            const tmp = r0
            r0 = r1
            r1 = tmp
          }
        }
        for (const item of this.code) {
          const instruction = item.substring(0, 4).toUpperCase()
          const rest = item.substring(5)
          console.log(instruction, rest, {r0, r1, stack})
          opmap[instruction](rest)
        }
        return r0
      }
    }
    
    const execute = (code, variable) => {
      const compiler = new Compiler()
      const vm = new VM()
      return vm.load(compiler.compile(code)).execute(variable)
    }
    

  • 0
    administrators

    @CodeHz 这个厉害了...居然写了个编译器,还自带虚拟机。


  • 1
    管理员

    简单实现版

    // Function
    const execute = (exp, data) => new Function(...Object.keys(data),`return ${exp}`)(...Object.values(data))
    
    // with
    const execute = (exp, data) => eval(`with(data){${exp}}`)
    

登录后回复
 

与 ScriptOJ 的连接断开,我们正在尝试重连,请耐心等待