Алгоритмическое определение чистых функций в javascript

JavaScript завершен по Тьюрингу, поэтому он так же способен анализировать и анализировать JavaScript, как и любой другой язык программирования. Итак, вопрос действительно таков: «Можно ли вообще автоматически тестировать функции JavaScript на« чистоту »?»

Краткий ответ

Только иногда.

Длинный ответ

Для некоторых функций, для которых AST является прямым и определенно содержит все символы. Что-то вроде function(X) { return X * X; } является доказуемо чистым (для примитивного ввода), потому что единственные переменные, используемые в теле функции, - это переменные, которые передаются в качестве аргументов функции. Эта функция не полагается на какие-либо дополнительные вызовы API, а только на чистую арифметику. Мы определенно можем показать, что это чисто.

Все меняется, когда мы разрешаем произвольный контент, потому что JavaScript не имеет явных типов, а вместо этого с радостью выполнит приведение типов от сложного к примитивному типу данных (или даже от примитивного к примитивному типу данных), когда ему потребуется выполнить операцию, к которой эта операция не может быть применена. Вызов нашей вышеупомянутой функции с помощью объекта, а не числа, выполняет дальнейшие вызовы функций под водой, и эти функции вообще не гарантируются чистыми (см. Ответ Андреаса по этому поводу)

Подавляющее большинство функций JS не похожи на нашу простую функцию. Для большинства функций нам нужно доказать не только то, что они чистые, но и то, что все функции, которые они вызывают внутри, также чисты. Теперь мы сталкиваемся с проблемой остановки. Возьмем до смешного простой пример:

function(x) {
  if (typeof window !== "undefined") {
    return x * x;
  }
  return x * x * x;
}

Это чисто? Что ж, если мы запустим это в браузере, тогда в браузере это чисто, поскольку window всегда определяется. Но в чем-то вроде Node.js он может быть чистым, но может и не быть: мы не можем доказать, что это так, и не можем доказать, что это не так, потому что мы не можем доказать, что этот загадочный window переменная существует при запуске функции. Хотя в Node.js нет глобальной переменной window, мы можем просто ввести ее, когда захотим, и поведение функции изменится. Теперь мы внезапно столкнулись с необходимостью доказать, будет ли весь наш код когда-либо вводить переменную window (и это может быть сделано очень творчески, например, global["win" + _abc] = true, где _abc - строка "dow"). Это безнадежное дело.

Кроличья нора глубокая, и, прочитав о проблеме остановки, вы поймете, сколько различий имеет проблема остановки.

Даже ваша первая функция не чистая, потому что в JavaScript * может вызывать преобразование ToNumber, которое может вызывать произвольный код пользователя, если x оказывается объектом с определяемым пользователем методом toString или valueOf, или кто-то случайно обнаружил патч-обезьяну. Object.prototype.

Печальная правда заключается в том, что в JS почти ничто не может быть доказано чистым. Единственные операции, которые никогда не могут иметь побочных эффектов, - это ===, !==, !, &&, || и typeof. Кстати, это огромная проблема для оптимизации компиляторов.

образец кода. ограничение: может только * догадываться *, если какой-то код чистый = может давать только подсказку, но не гарантирует

/* programmatically guess if some javascript code is pure or impure
npm install acorn acorn-walk
license is CC0-1.0 */

const acorn_parse = require("acorn").parse;
const acorn_walk = require("acorn-walk");



// the code to analyze
const content = `
  ['k1'].map(key => {
    const val = data[key];
    let local1;
    var local2 = 2;
    var local3, local4;
    global1[key] = val; // find me
    global2.key = val; // find me
    global3.push(val); // find me
    global4.pop(); // find me
    global5.shift(); // find me
    global6 = 'impure'; // find me
    const local7 = global7[1234];
    var local8 = global8.map(x => 2*x);
    var local9 = global9.filter(Boolean);
    const local10 = global10.pop(); // find me
    local1 = 'ok';
    local2.push('ok');
    return [key, val];
  })
`;



// method names for our educated guess
const write_method_set = new Set(['push', 'pop', 'shift']);
const read_method_set = new Set(['map', 'filter', 'reduce', 'forEach']);

const is_write_method = method_name => write_method_set.has(method_name);
const is_read_method = method_name => read_method_set.has(method_name);
const is_local = name => (name != undefined && local_var_set.has(name));
const get_src = node => content.substring(node.start, node.end);

function test_assign(node, left_name) {
  if (left_name == undefined) {
    console.log(`TODO implement: detect write access in:`);
    console.dir(node);
    return;
  }
  if (!is_local(left_name)) console.log(`impure write access to global ${left_name}: ${get_src(node)}`);
  else console.log(`pure? write access to local ${left_name}: ${get_src(node)}`);
}

function test_call(node, left_name, method_name) {
  if (left_name == undefined) {
    console.log(`TODO implement: detect write access in:`)
    console.dir(node);
    return;
  }
  if (is_read_method(method_name)) return console.log(`pure? access to ${left_name}: ${get_src(node)}`);
  if (!is_local(left_name)) {
    if (is_write_method(method_name)) console.log(`impure write access to global ${left_name}: ${get_src(node)}`);
    else console.log(`pure? access to global ${left_name}: ${get_src(node)}`);
  }
  else console.log(`pure? write access to local ${left_name}: ${get_src(node)}`)
}



const local_var_set = new Set();

// throws on syntax error
let ast = acorn_parse(content, { ecmaVersion: 2020, sourceType: "module" });

acorn_walk.full(ast, (node, state, type) => {
  if (node.type == 'VariableDeclaration') {
    node.declarations.forEach(d => {
      local_var_set.add(d.id.name);
      console.log(`declare local: ${d.id.name}`);
    });
  }
  else if (node.type == 'AssignmentExpression') {
    const left_name =
      node.left.type == 'Identifier' ? node.left.name :
      node.left.type == 'MemberExpression' ? node.left.object.name :
      undefined
    ;
    test_assign(node, left_name);
  }
  else if (node.type == 'CallExpression') {
    if (node.callee.object.type == 'ArrayExpression') return; // simply ignore
    const left_name =
      node.callee.type == 'MemberExpression' ? node.callee.object.name :
      undefined
    ;
    const method_name =
      node.callee.type == 'MemberExpression' ? node.callee.property.name :
      undefined
    ;
    test_call(node, left_name, method_name);
  }
  //else console.dir(node);
});

образец вывода

$ node test.js | grep impure
impure write access to global global1: global1[key] = val
impure write access to global global2: global2.key = val
impure write access to global global3: global3.push(val)
impure write access to global global4: global4.pop()
impure write access to global global5: global5.shift()
impure write access to global global6: global6 = 'impure'
impure write access to global global10: global10.pop()