Как управлять часами? Разбор фронтенд-трека второго чемпионата по программированию03.12.2019 15:03

Новый хабрапост в серии разборов недавно прошедшего чемпионата. Участникам квалификации, которые выбрали секцию фронтенда, нужно было решить несколько задач очень разной сложности: первая (по нашим ожиданиям) занимала 20 минут, последняя — около часа. Мы проверяли широкий спектр навыков разработчика интерфейсов, включая способность разобраться в необычной предметной области.

A. Аннигилируй это

Авторы: Максим Сысоев, Константин Петряев

Первая задача — разминочная. Каждому участнику доставался один из четырёх вариантов задачи, похожих между собой. Мы предложили не только текстовое условие, но и «плохое» рекурсивное решение. Нужно было переделать код (написать жадный алгоритм, который выдавал самое быстрое решение), убрав рекурсию и разные глупости вроде лишних операций и вычислений.

Условие

Вы устроились работать в лабораторию по изучению антиматерии, где проводят различные опыты. Ваш отдел изучает процессы, которые происходят при объединении материи и антиматерии. Вам необходимо провести серию опытов над некоторым количеством молекул.
Соседний отдел разработал аппарат, который превращает материю в антиматерию на небольшое время. Он пригодится вам в проведении опытов, в которых используется следующий алгоритм:

— Находим 2 самых тяжёлых молекулы.
— Одну из них превращаем в антиматерию.
— Объединяем их. При этом, если вес одинаковый, они аннигилируются. Если же вес различается, то мы получаем новую молекулу, вес которой равен разнице весов предыдущих двух. Сама получившаяся молекула является материей.
— Если осталась одна молекула — нужно выяснить её вес. Если же молекул много — возвращаемся к пункту 1.

Вам необходимо узнать, молекула какого веса останется в конце опыта, это знание нужно учёным другого отдела.

Предыдущий разработчик набросал код, который занимался этими расчётами, однако код не может закончить расчёты в случае, когда опыт проводится на большом количестве молекул. Вам необходимо усовершенствовать код, чтобы он работал за приемлемое время.

Код, доставшийся вам в «наследство»

В качестве входных данных у вас будет массив с весами молекул. В качестве выходных данных необходимо вернуть число, которое обозначает вес последней молекулы. Если молекул не останется, то необходимо вернуть 0.

var findLatestWeight = function(weights, i = weights.length - 1) {  
  const cur = weights.length - 1 === i;  
 
  if (i === 0) return weights[0];  
 
  weights.sort((a, b) => a - b);  
  weights[i - 1] = (weights[i] === weights[i-1]) ? 0 : weights[i] - weights[i-1];  
 
  return findLatestWeight(weights, i - 1);  
}

function findLatestWeight(weights) {  
  // ...  
}  
 
module.exports = findLatestWeight;

Решение

В предоставленном «плохом» решении есть сразу несколько проблем. Первая — наличие рекурсии. Как заявлено в условии, мы будем обрабатывать большие массивы чисел, что сразу исключает рекурсивное решение.

var findLatestWeight = function(weights) {
    let i = weights.length - 1;
    do {
        if (i === 0) return weights[0] || 0;

        weights.sort((a, b) => a - b);
        weights[i-1] = (weights[i]=== weights[i-1]) ? 0 : weights[i]-weights[i-1];

        i--;
    } while (true);
}

Развернуть рекурсию здесь достаточно просто, однако возникает другая проблема — происходит постоянная пересортировка (от меньших к большим) и работа с концом массива. В результате мы получаем уменьшение предпоследнего элемента в массиве. Но после этого мы не обрезаем массив, и если в функцию был передан массив из миллиона элементов, то мы до самого конца будем заниматься его пересортировкой.

Вариант решения этой проблемы — попробовать постоянно обрезать массив.

var findLatestWeight = function(weights) {
    let i = weights.length - 1;
    do {
        if (i === 0) return weights[0] || 0;

        weights.sort((a, b) => a - b);
        weights[i-1] = (weights[i]=== weights[i-1]) ? 0 : weights[i]-weights[i-1];
	weights.length = i; // <--- вот так
        i--;
    } while (true);
}

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

const maximumTwo = (arr) => {
    let max1 = arr[0];
    let max2 = arr[1];
    let max1I = 0;
    let max2I = 1;
    for(let i = 2; i < arr.length; i++) {
        if (arr[i] > max1) {
            if (max1 > max2) {
                max2 = arr[i];
                max2I = i;
            } else {
                max1 = arr[i];
                max1I = i;
            }
        } else if (arr[i] > max2) {
            max2 = arr[i];
            max2I = i;
        }
    }

    if (max1 > max2) return [max2, max1, max2I, max1I];
    return [max1, max2, max1I, max2I];
};

А саму функцию поиска поменяем следующим образом:

const fn = function(weights) {
    if (weights.length <= 1) {
        return weights[0];
    }

    do {
        const [x, y, xI, yI] =  maximumTwo(weights);
        if (x === 0) {
            return y;
        }

        weights[xI] = 0;
        weights[yI] = y - x;

    } while(true);
};

Таким образом, мы всегда будем обнулять меньший из двух элементов, а больший превращать в разницу между ними. Мы избавились от сортировки и получили вместо нее один линейный проход.

Из замеченных нами частых ошибок — участники брали максимальный элемент, умножали его на –1 и складывали со вторым по величине камнем. В результате получалось отрицательное число, которое потом использовалось в вычислениях «как есть». Кроме того, в задаче есть ментальная ловушка, связанная с тем, что можно попробовать оставить уникальные по весу камни и вычислить разницу из них. Однако этот подход не даёт верного результата.

B. БЭМ

Авторы: Евгений Мищенко, Владимир Гриненко tadatuta

Условие

Верстальщик Александр участвует в множестве проектов с использованием БЭМ-методологии. Он даже создал удобный плагин для любимой IDE, который позволяет ему писать имена классов в сокращённой записи и разворачивать их в полную. Но проблема в том, что для каждого проекта люди устанавливают разные разделители между блоком, элементом и модификатором (block__mod__val—elem, block–mod–val___elem), и ему приходится каждый раз править это в своём плагине вручную. Помогите Александру написать модуль, который будет на основании класса определять разделитель для сущностей. Правило для разделителей — произвольное количество символов (не буквы). Примеры возможных нотаций (модификаторы для блока во входящих данных могут быть без значения):

block_mod__elem // Считаем, что модификатор идёт первым  
block_mod_mod__elem  
block__elem_mod_mod

Уточнения:
— Классы в проектах пишут только маленькими буквами.
— На вход модуля подаётся строка с валидным CSS-классом.

Модуль должен вернуть ответ вида:

{  
  mod: "_", // разделитель для модификатора  
  elem: "__", // разделитель для элемента  
}

Оформить модуль необходимо как commonJS-модуль:

module.exports = function(str) {  
 
}

Решение

На вторую задачу отводилось примерно 20 минут. С её помощью мы хотели проверить у участников знание регулярных выражений.

Из условия мы узнаём, что на вход в функцию будет приходить строка, содержащая валидный CSS-класс с дополнительными ограничениями, в которой буквенные последовательности разделены произвольными последовательностями из небуквенных символов. Наша задача — найти разделители и понять их семантику.

Первой частью имени класса всегда будет название блока. Это последовательность из одной или более букв. Запишем соответствующее регулярное выражение: [a-z]+.

Аналогичные выражения потребуются нам для поиска остальных частей: имени модификатора и его значения либо имени элемента с соответствующими модификатором и значением.

Для поиска разделителей нам нужны небуквенные последовательности, подойдет выражение: [^a-z]+.

Соберём вместе и зададим группы, значения которых будем использовать:

let [, mod, elem ] = str.match(/[a-z]+(?:([^a-z]+)[a-z]+(?:\1)?[a-z]+)([^a-z]+)[a-z]+(?:\2)?[a-z]+/);

Теперь нужно убедиться, что мы правильно определили семантику найденных групп. Можно воспользоваться тем, что встретиться дважды может только модификатор.

Напишем функцию, которая будет принимать исходную строку и найденный разделитель, чтобы посчитать количество вхождений:

const substringCount = (source, substr) => (source.match(new RegExp('[a-z]' + substr + '[a-z]', 'g')) || []).length;

Если окажется, что разделитель elem встречается дважды, а mod — один раз, то на самом деле все наоборот. Итоговое решение:

module.exports = function(str) {
    let [, mod, elem ] = str.match(/[a-z]+(?:([^a-z]+)[a-z]+(?:\1)?[a-z]+)([^a-z]+)[a-z]+(?:\2)?[a-z]+/);
    const substringCount = (source, substr) => (source.match(new RegExp('[a-z]' + substr + '[a-z]', 'g')) || []).length;

    if (substringCount(str, elem) === 2 && substringCount(str, mod) === 1) {
        [mod, elem] = [elem, mod];
    }

    return { mod, elem };
}

C. Фабрика клонов

Авторы: Дмитрий Андриянов dima117, Алексей Гусев

Условие

За окном 2319 год. Корпорации клонируют успешных сотрудников, чтобы они выполняли сложные задачи.

На производстве клонов решили маркировать новые «изделия» с помощью татуировки с баркодом на плече — чтобы отличать клонов между собой.

Помогите сотрудникам фабрики написать функцию, которая будет отрисовывать баркод с информацией о клоне.

Формат информации о клоне

Информация о клоне хранится в следующем виде:

type CloneInfo = {  
    /**  
     * Пол клона — строка ’male’ или ’female’  
     */  
    sex: string;  
    /**  
     * Идентификатор клона — строка из маленьких и больших  
     * латинских букв и цифр, строго 10 символов  
     */  
    id: string;  
    /**  
     * Имя клона — строка из маленьких и больших  
     * латинских букв и пробелов (от 0 до 26 символов)  
     */  
    name: string;  
}

Алгоритм отрисовки баркода

Баркоды, которые используют на фабрике клонов, выглядят так:

Баркод имеет фиксированный размер — 148 на 156 пикселей. По периметру баркода находятся чёрная и белая рамки по 3 пикселя шириной каждая. Внутри рамок находится контент баркода, состоящий из 18 строк по 17 чёрных или белых квадратов в строке. Размер каждого квадрата — 8 на 8 пикселей.

Белые квадраты в контенте кодируют 0, чёрные — 1.

Алгоритм формирования контента баркода

На пересечении первой строки и первого столбца контента отрисовывается квадрат, кодирующий пол клона. Значение female кодируется нулём (белый цвет), male — единицей (чёрный цвет).

Далее из полей id и name формируется строка вида . Поле name дополняется пробелами в конце до 26 символов.

Полученная строка конвертируется в байтовый массив — каждому символу строки ставится соответствующий ASCII-код (число от 0 до 255).

Затем каждый элемент полученного массива переводится в двоичную запись (восемь символов 0 или 1) и кодируется последовательностью из восьми квадратов (0 — белый квардрат, 1 — чёрный квадрат). Квадраты отрисовываются в контенте баркода последовательно и построчно.

В последней строке контента находится контрольная информация.

Алгоритм подсчёта контрольной информации

Каждый квадрат в строке контрольной информации определяет чётность суммы значений контента в соответствующем столбце. Если сумма нулей и единиц в столбце чётная, то в контрольной информации рисуется белый квадрат, в противном случае — чёрный.

/**  
 * Отрисовать баркод для татуировки клона в element  
 * @param cloneInfo {CloneInfo} — информация о клоне  
 * @param element {HTMLDivElement} — div с фиксированным размером  
 *     148x156 пикселей, в который будет отрисовываться баркод  
 */  
function renderBarcode(cloneInfo, element) {  
    // ваш код  
}
Решение будет запускаться в браузере Google Chrome 77.

Пример 1
Информация о клоне:

{  
    "sex": "male",  
    "id": "c5j818dyo5",  
    "name": "Oleg Vladimirovich"  
}

{  
    "sex": "female",  
    "id": "0owrgqqwfw",  
    "name": "Dazdraperma Petrovna"  
}

Решение

Требовалось правильно сформировать бинарное представление данных, посчитать для него контрольную сумму и отрисовать эти данные в верстке. Давайте попробуем сделать это максимально просто и в лоб — без оптимизаций кода.

Начнём с бинарного представления. Для начала объявим вспомогательные функции:

// переводит символ в ASCII-код
function charToByte(char) {
  return char.charCodeAt(0);
}

// переводит байт в строку из 0 и 1 (в двоичную систему счисления с незначащими нулями)
function byteToString(byte) {
  return byte.toString(2).padStart(8, '0');
}

Cформируем из исходных данных строку, состоящую из нулей и единиц:

let dataString =
  (cloneInfo.sex === 'female' ? '0' : '1') +
  cloneInfo.id.split('').map(charToByte).map(byteToString).join('') +
  cloneInfo.name.padEnd(26, ' ').split('').map(charToByte).map(byteToString).join('');

Затем напишем вёрстку и стили для нашего баркода:

// Идентификатор для блока, где будет находиться «контент» баркода.
// В принципе, вёрстку можно целиком строить через DOM API без использования innerHTML, и тогда идентификатор не потребуется. 
// Если же реализовывать в лоб, случайный идентификатор защитит нас от того, что два баркода на странице «перемешаются».
// Это было очень частой ошибкой у участников чемпионата — многие не учитывали, что функция отрисовки баркода может вызываться несколько раз.
const contentElId = 'content-' + Math.random();
element.style.display = 'flex';
element.innerHTML = `
  

  

`;

const contentDiv = document.getElementById(contentElId);
element.className += ' barcode';

Отрендерим бинарные данные в вёрстке:

dataString
  .split('')
  .forEach((bit) => {
    const bitDiv = document.createElement('div');
    bitDiv.className = 'content__bit content__bit_' + (bit === '0' ? 'zero' : 'one');
    contentDiv.appendChild(bitDiv);
  });

Осталось посчитать и отобразить контрольную сумму. Это можно сделать так:

for (let i = 0; i < 17; i++) {
  // суммируем столбец
  let sum = 0;
  for (let j = i; j < 17 ** 2; j += 17) {
    sum += parseInt(dataString[j], 2);
  }
  const check = 0;
  const bitDiv = document.createElement('div');
  // рисуем квадрат контрольной суммы для столбца
  bitDiv.className = 'content__bit content__bit_' + (sum % 2 === 0 ? 'zero' : 'one');
  contentDiv.appendChild(bitDiv);
}

D. Автоматизируй это

Авторы: Владимир Русов, Дмитрий Канатников

В каждом из вариантов квалификации была задача, где в качестве входных данных предлагалась HTML-страничка с таблицей или списком. У задач этой серии была разная легенда, но все они сводились к тому, что надо привести страницу к формату, похожему на Markdown. Разберём решение одной из задач.

Условие

На государственном портале предоставления услуг сделали возможность подавать заявление на получение документов полностью автоматически, для этого надо только заполнить таблицу с персональными данными.

Эти данные затем передаются на проверку в несколько инстанций, включая МВД. После начала тестирования выяснилось, что МВД принимает данные в формате Markdown, а Госуслуги пользуются HTML-форматом. Помогите написать скрипт миграции одного формата в другой, чтобы ребята поскорее запустились.

Вам нужно написать функцию, которая на вход принимает HTML-таблицу и преобразует ее в Markdown-подобную разметку.

В качестве решения этого задания отправьте файл .js, в котором объявлена функция solution:

function solution(input) {
    // ...
}

    
        
        
        
    
    

        

            
Command         
            
Description     
            
Is implemented  
        
    
    

        

            
git status
            
List all new or modified    files
            
Yes
        
        

            
git diff
            
Show file differences that haven't been
 staged
            
No
        
    

Решение

Задача решается простым обходом DOM-дерева таблицы. Поддержка DOM-дерева реализована на уровне браузера, является его неотъемлемой частью, поэтому проблем не возникнет. Для решения задачи достаточно транслировать DOM-дерево из HTML в Markdown-разметку.

Рассмотрев примеры, можно заметить, что преобразование осуществляется достаточно просто. Ниже — код, который является телом функции solution (input).

Для начала нам понадобится преобразовать строку из HTML в DOM-дерево:

const div = document.createElement('div');
div.innerHTML = input;
const table = div.firstChild;

Получив DOM-дерево, мы можем просто по нему пройти и обработать данные из разных DOM-узлов. Для этого достаточно рекурсивно обходить последовательноть children различных DOM-элементов:

const processors = {
    'colgroup': processColgroup,
    'thead': processThead,
    'tbody': processTbody,
};

for (let child of table.children) {
    processors[child.tagName.toLowerCase()](child);
}

Из тегов colgroup и col нам интересно узнать выравнивание колонок таблицы:

const alignments = [];
const defaultAlign = 'left';

const processColgroup = (colgroup) => {
    alignments.push(...Array(...colgroup.children).map(col => {
        return col.align || defaultAlign;
    }));
};

В тегах thead,  tbody и tr нас интересуют только дочерние элементы:

const rows = [];

const processThead = (thead) => {
    rows.push(...Array(...thead.children).map(processTr));
};

const processTbody = (tbody) => {
    rows.push(...Array(...tbody.children).map(processTr));
};

const processTr = (tr) => {
    return Array(...tr.children).map(processCell);
};

Важно не забыть, что по условию td и th форматируются по-разному:

const processCell = (cell) => {
    const tag = cell.tagName.toLowerCase();
    const content = clearString(cell.innerHTML);

    return {
        'td': content,
        'th': `**${content}**`,
    }[tag];
};

Для работы с тестовым содержимым DOM необходимо выполнить требования, о которых сказано в условии:

const clearLineBreaks = (str) => str.replace(/\r?\n|\r/g, '');
const clearSpaces = (str) => str.replace(/\s+/g, ' ');
const clearString = (str) => clearSpaces(clearLineBreaks(str)).trim();

После того, как мы обошли DOM-дерево, основная часть нашей таблицы оказалась записана в массив rows:

[
["Command","Description","**Is implemented**"],
["**git status**","List all new or modified files","**Yes**"],
["**git diff**","Show file differences that haven't been staged","No"]
]

Информация о выравнивании колонок оказалась в массиве alignments:

["right","left","center"]

Важно вспомнить, что информация о выравнивании колонок может отсутствовать во входных данных:

const updateAlignments = () => {
    if (alignments.length > 0) return;
    alignments.push(...rows[0].map(x => defaultAlign));
};

updateAlignments();

Преобразуем alignments в конечный вид:

const alignmentsContents = alignments.map(align => {
    return {
        'left': ' :--- ',
        'center': ' :---: ',
        'right': ' ---: '
    }[align];
});
const delimiter = `|${alignmentsContents.join('|')}|`;

Пример значения delimiter:

"| ---: | :--- | :---: |"

Завершающим этапом будет формирование Markdown-строки, содержащей все данные, прочитанные из HTML:

const lineEnd = '\n';

rows.forEach((row, i) => {
    if (i > 0) markdown += lineEnd;

    const mdRow = `| ${row.join(' | ')} |`;
    markdown += mdRow;

    if (i === 0) {
        markdown += lineEnd;
        markdown += delimiter;
    }
});

return markdown;

Конструкция return означает, что весь приведённый код был телом функции solution (input). В результате работы этой функции мы получим желаемый Markdown-код таблицы, показанный в примере выходных данных из условия задачи.

E. Пандемия вируса

Авторы: Андрей Мокроусов, Иван Петухов

Всемирная Организация Здравоохранения опубликовала доклад о признаках надвигающейся пандемии нового вируса, который угрожает фронтенд-разработчикам. Известно, что вирус никак не проявляет себя до тех пор, пока носитель не увидит JS-код, содержащий некоторое выражение. Как только заражённый увидел это выражение, он теряет способность писать код на JS и начинает непроизвольно писать код на Фортране.

В докладе упоминается, что вирус активируется от взгляда на использование первого аргумента функции, передаваемой аргументом в вызов функции Z.y.n, то есть заражённым нельзя показывать выражение, подобное Z.y.n (function (a, b, c){console.log (a)}).

Чтобы не потерять случайно всех своих фронтендеров, в компании AST & Co решили проверить, содержит ли их код упомянутое выражение. Помогите инженерам компании написать такую проверку.

Про код в компании AST & Co известно, что:

— он написан на ES3,
— обращение к свойствам объекта возможно как через точку, так и через скобки (a.b и a['b']),
— часть выражения может быть сохранена в переменной, но никогда не передаётся в функцию параметром (a (x) — запрещено),
— нет функций, которые возвращают часть искомого выражения,
— нет свойств объектов или элементов массивов, которые содержат часть выражения,
— при обращении к свойству объекта название свойства может быть взято из переменной (a[x], x — переменная),
— переменные получают свои значения при декларации и не переписываются, т. е. в коде не будет подобного var a = x; a = y; и var a = b = 1.

module.exports = function (ast) {
  ...
  return [...];
}

/**
 * Функция обхода дерева. Выполняет обход дерева в глубину,
 * передавая в callback-функции onNodeEnter (до посещения потомков)
 * и onNodeLeave (после посещения потомков) каждый узел дерева
 * и текущую область видимости (смотри определение Scope ниже).
 *
 * @param      {object}    ast                              Исходное ast.
 * @param      {Function}  [onNodeEnter=(node, scope)=>{}]  Вызывается для каждого узла до посещения потомков.
 * @param      {Function}  [onNodeLeave=(node, scope)=>{}]  Вызывается для каждого узла после посещения потомков.
 */
function traverse(
    ast,
    onNodeEnter = (node, scope) => {},
    onNodeLeave = (node, scope) => {}
) {
    const rootScope = new Scope(ast);

    _inner(ast, rootScope);

    /**
     * Определение области видимости узла.
     * Может либо вернуть текущий scope, либо создать новый.
     *
     * @param      {object}  astNode       ast-узел.
     * @param      {Scope}   currentScope  Текущая область видимости.
     * @return     {Scope}   Область видимости для внутренних узлов astNode.
     */
    function resolveScope(astNode, currentScope) {
        let isFunctionExpression = ast.type === 'FunctionExpression',
            isFunctionDeclaration = ast.type === 'FunctionDeclaration';

        if (!isFunctionExpression &&
            !isFunctionDeclaration) {
            // Новые области видимости порождают только функции.
            return currentScope;
        }

        // Каждая функция порождает новую область видимости.
        const newScope = new Scope(ast, currentScope);

        ast.params.forEach(param => {
            // Параметры функции доступны внутри функции.
            newScope.add(param.name);
        });

        if (isFunctionDeclaration) {
            // Имя функции при декларации доступно снаружи функции.
            currentScope.add(ast.id.name);
        } else {
            // Имя функции-выражения доступно только внутри неё.
            newScope.add(ast.id.name);
        }

        return newScope;
    }

    /**
     * Рекурсивная функция обхода ast.
     *
     * @param      {object}  astNode  Текущий ast-узел.
     * @param      {Scope}  scope     Область видимости для текущего ast-узла.
     */
    function _inner(astNode, scope) {
        if (Array.isArray(astNode)) {
            astNode.forEach(node => {
                /* Рекурсивный обход элементов списков.
                 * Списками являются, например, параметры функций.
                 */
                _inner(node, scope);
            });
        } else if (astNode && typeof astNode === 'object') {
            onNodeEnter(astNode, scope);

            const innerScope = resolveScope(astNode, scope),
                keys = Object.keys(astNode).filter(key => {
                    // loc - служебное свойство, а не ast-узел.
                    return key !== 'loc' &&
                        astNode[key] && typeof astNode[key] === 'object';
                });

            keys.forEach(key => {
                // Обход всех потомков.
                _inner(astNode[key], innerScope);
            });

            onNodeLeave(astNode, scope);
        }
    }
}

/**
 * Представление области видимости.
 *
 * @class      Scope (name)
 * @param      {object}  astNode      ast-узел, породивший эту область видимости.
 * @param      {object}  parentScope  Родительская область видимости.
 */
function Scope(astNode, parentScope) {
    this._node = astNode;
    this._parent = parentScope;
    this._vars = new Set();
}

Scope.prototype = {
    /**
     * Добавление имени переменной в область видимости.
     *
     * @param      {string}  name    Имя переменной.
     */
    add(name) {
        this._vars.add(name);
    },
    /**
     * Была ли определена переменная с таким именем.
     *
     * @param      {string}   name    Имя переменной.
     * @return     {boolean}  Встречалась ли переменная с таким именем в доступных областях видимости.
     */
    isDefined(name) {
        return this._vars.has(name) || (this._parent && this._parent.isDefined(name));
    }
};

Решение

Сначала разберёмся с ограничениями.

— он написан на ES3

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

— обращение к свойствам объекта возможно как через точку, так и через скобки (a.b и a['b'])

То есть нужно искать не только Z.y.n, но и Z['y'].n, Z.y['n'] и Z['y']['n'].

часть выражения может быть сохранена в переменной, но никогда не передаётся в функцию параметром (a (x) — запрещено)

Этот пункт сразу делает задачу в несколько раз сложнее, потому что придётся отслеживать значения переменных и области видимостей. Например, нужно будет назодить такой код: var x = Z.y; x.n (…).

— нет функций, которые возвращают часть искомого выражения,
— нет свойств объектов или элементов массивов, которые содержат часть выражения,
— переменные получают свои значения при декларации и не переписываются, т.е. в коде не будет подобного var a = x; a = y; и var a = b = 1.

Эти пункты (как и запрет на передачу выражения в функции) упрощают задачу, но учитывать значения переменных и области видимости всё-таки придётся.

— при обращении к свойству объекта, название свойства может быть взято из переменной (a[x], x — переменная)

Этот пункт окрывает ещё один способ обращения к свойствам объекта, за которым нужно следить: var x = 'y'; Z[x].n (…).

Cтановится понятен примерный план решения:
1. Обойти всё дерево, собрав информацию о значениях переменных, которые они получают при декларации.
2. Найти искомую конструкцию, учитывая информацию из предыдущего пункта.

Код, который дан в примечании задачи, может сэкономить немного времени в самом скучном месте — обходе дерева и сборе информации о названиях и параметрах функций. Поэтому возьмём его и начнём с пункта 2.

Поиск выражения

Разобьём поиск на две части: сначала найдём Z.y.n (function (a, b, c){…}), затем — использование первого аргумента внутри функции.

Первая часть соответствует FunctionExpression — первому и единственному параметру в CallExpression, у которого callee — MemberExpression. Причём имя property — n, а object (ещё один MemberExpression с object и property под именем y) — Z.

Вторая часть соответствует любому обращению к первому аргументу, потому что единственное допустимое действие — перезапись — запрещено условием. Обращение к первому аргументу — это Identifier с тем же именем, который встретился где угодно кроме MemberExpression и ObjectLiteral в качестве свойства (x.a и var x = {a: …} соответственно).

+++ b/traverse.js
@@ -120,3 +120,59 @@ Scope.prototype = {
         return this._vars.has(name) || (this._parent && this._parent.isDefined(name));
     }
 };
+
+module.exports = function (ast) {
+    var result = [];
+
+    traverse(ast, (node, scope) => {
+        if (node.type !== 'CallExpression') {
+            return;
+        }
+        let args = node.arguments;
+        if (args.length !== 1 ||
+            args[0].type !== 'FunctionExpression') {
+            return;
+        }
+        let callee = node.callee;
+        if (callee.type !== 'MemberExpression') {
+            return;
+        }
+        let property = callee.property,
+            object = callee.object;
+        if (property.name !== 'n') {
+            return;
+        }
+        if (object.type !== 'MemberExpression') {
+            return;
+        }
+        property = object.property;
+        object = object.object;
+        if (property.name !== 'y') {
+            return;
+        }
+        if (object.type !== 'Identifier' ||
+            object.name !== 'Z') {
+            return;
+        }
+
+        checkFunction(args[0]);
+    });
+
+    function checkFunction(ast) {
+        let firstArg = ast.params[0];
+        if (!firstArg) {
+            return;
+        }
+
+        traverse(ast.body, (node, scope) => {
+            if (node.type !== 'Identifier') {
+                return;
+            }
+            if (node.name === firstArg.name) {
+                result.push(node);
+            }
+        });
+    }
+
+    return result;
+};

По последнему вызову traverse видно, что при обходе требуется информация о родителях, чтобы корректно отфильтровать идентификаторы в MemberExpression и ObjectProperty. Добавляем:

--- a/traverse.js
+++ b/traverse.js
@@ -60,16 +60,16 @@ function traverse(
      * @param      {object}  astNode  Текущий ast-узел
      * @param      {Scope}  scope     Область видимости для текущего ast-узла
      */
-    function _inner(astNode, scope) {
+    function _inner(astNode, scope, parent) {
         if (Array.isArray(astNode)) {
             astNode.forEach(node => {
                 /* Рекурсивный обход элементов списков.
                  * Списками являются, например, параметры функций
                  */
-                _inner(node, scope);
+                _inner(node, scope, parent);
             });
         } else if (astNode && typeof astNode === 'object') {
-            onNodeEnter(astNode, scope);
+            onNodeEnter(astNode, scope, parent);

             const innerScope = resolveScope(astNode, scope),
                 keys = Object.keys(astNode).filter(key => {
@@ -80,10 +80,10 @@ function traverse(

             keys.forEach(key => {
                 // Обход всех потомков
-                _inner(astNode[key], innerScope);
+                _inner(astNode[key], innerScope, astNode);
             });

-            onNodeLeave(astNode, scope);
+            onNodeLeave(astNode, scope, parent);
         }
     }
 }
@@ -164,10 +164,22 @@ module.exports = function (ast) {
             return;
         }

-        traverse(ast.body, (node, scope) => {
+        traverse(ast.body, (node, scope, parent) => {
             if (node.type !== 'Identifier') {
                 return;
             }
+            if (!parent) {
+                return;
+            }
+            if (parent.type === 'MemberExpression' &&
+                parent.computed === false &&
+                parent.property === node) {
+                return;
+            }
+            if (parent.type === 'ObjectProperty' &&
+                parent.key === node) {
+                return;
+            }
             if (node.name === firstArg.name) {
                 result.push(node);
             }

Нужно учесть и обращение к свойствам объектов через скобки. Создадим функцию getPropName:

--- a/traverse.js
+++ b/traverse.js
@@ -121,6 +121,18 @@ Scope.prototype = {
     }
 };

+function getPropName(node) {
+    let prop = node.property;
+
+    if (!node.computed) {
+        return prop.name;
+    }
+
+    if (prop.type === 'StringLiteral') {
+        return prop.value;
+    }
+}
+
 module.exports = function (ast) {
     var result = [];

@@ -137,17 +149,17 @@ module.exports = function (ast) {
         if (callee.type !== 'MemberExpression') {
             return;
         }
-        let property = callee.property,
+        let property = getPropName(callee),
             object = callee.object;
-        if (property.name !== 'n') {
+        if (property !== 'n') {
             return;
         }
         if (object.type !== 'MemberExpression') {
             return;
         }
-        property = object.property;
+        property = getPropName(object);
         object = object.object;
-        if (property.name !== 'y') {
+        if (property !== 'y') {
             return;
         }
         if (object.type !== 'Identifier' ||

Этот код всё ещё содержит недостатки: он никак не использует области видимости и переменые. Однако он хотя бы проходит первые три теста. Теперь переходим к пункту 1.

Улучшение Scope

Нужно добавить в Scope сбор информации о переменных и их значениях. Кроме того, нужно сделать так, чтобы собранная информация не терялась между вызовами traverse:

--- a/traverse.js
+++ b/traverse.js
@@ -1,3 +1,12 @@
+const scopeStorage = new Map();
+
+function getScopeFor(ast, outerScope) {
+    if (!scopeStorage.has(ast)) {
+        scopeStorage.set(ast, new Scope(ast, outerScope));
+    }
+
+    return scopeStorage.get(ast);
+}
 /**
  * Функция обхода дерева. Выполняет обход дерева в глубину,
  * передавая в callback-функции onNodeEnter (до посещения потомков).
@@ -13,7 +22,7 @@ function traverse(
     onNodeEnter = (node, scope) => {},
     onNodeLeave = (node, scope) => {}
 ) {
-    const rootScope = new Scope(ast);
+    const rootScope = getScopeFor(ast);

     _inner(ast, rootScope);

@@ -36,19 +45,19 @@ function traverse(
         }

         // Каждая функция порождает новую область видимости.
-        const newScope = new Scope(ast, currentScope);
+        const newScope = getScopeFor(ast, currentScope);

         ast.params.forEach(param => {
             // Параметры функции доступны внутри функции.
-            newScope.add(param.name);
+            newScope.add(param.name, param);
         });

         if (isFunctionDeclaration) {
             // Имя функции при декларации доступно снаружи функции.
-            currentScope.add(ast.id.name);
+            currentScope.add(ast.id.name, ast);
         } else if (ast.id) {
             // Имя функции-выражения доступно только внутри неё.
-            newScope.add(ast.id.name);
+            newScope.add(ast.id.name, ast);
         }

         return newScope;
@@ -98,7 +107,7 @@ function traverse(
 function Scope(astNode, parentScope) {
     this._node = astNode;
     this._parent = parentScope;
-    this._vars = new Set();
+    this._vars = new Map();
 }

 Scope.prototype = {
@@ -107,8 +116,24 @@ Scope.prototype = {
      *
      * @param      {string}  name    имя переменной
      */
-    add(name) {
-        this._vars.add(name);
+    add(name, value) {
+        this._vars.set(name, {
+            value: value,
+            scope: this
+        });
+    },
+    resolve(node) {
+        if (!node) {
+            return node;
+        }
+        if (node.type === 'Identifier') {
+            let value = this._vars.get(node.name);
+            if (value) {
+                return value;
+            }
+            value = (this._parent && this._parent.resolve(node));
+            return value;
+        }
     },
     /**
      * Была ли определена переменная с таким именем.
@@ -136,6 +161,12 @@ function getPropName(node) {
 module.exports = function (ast) {
     var result = [];

+    traverse(ast, (node, scope) => {
+        if (node.type === 'VariableDeclarator') {
+            scope.add(node.id.name, node.init);
+        }
+    });
+
     traverse(ast, (node, scope) => {
         if (node.type !== 'CallExpression') {
             return;

Использование Scope

Теперь добавим использование знаний о переменных. Каждая часть выражения может быть помещена в переменную, поэтому будем обращаться к Scope после после каждой части. Заметьте, что сам Scope тоже может меняться, поскольку значения переменных привязаны к своей области видимос

© Habrahabr.ru