A. Охота за сокровищами Сегодня вы — искатель при...

Question

A. Охота за сокровищами

Сегодня вы — искатель приключений. Чтобы упростить себе работу, вы решили сделать прибор, который анализирует древние карты и возвращает конфиг путей. И всё почти получилось. Осталось только написать небольшую функцию‑проводник, которая по переданному конфигу будет показывать, куда приведёт ваш путь.

Конфиг содержит:

text
pathRules — список правил карты.
processors — глобальный набор обработчиков (опционально).
errorPath — путь в который приводят ошибки.

Каждое правило имеет pattern и одно из двух свойств: destination или redirect. В destination и redirect могут использоваться плейсхолдеры {param} - они подставляются значениями найденных параметров из pattern.
Как читать карту

Шаблон pattern:

segment1[param1][param2?][param3~]

text
segment — фиксированная часть пути.
[param] — сегмент‑параметр.
? делает параметр опциональным.
~ означает игнорирование регистра (значение приводится к нижнему регистру).
В параметрах допустимы только символы A-Z a-z 0-9 _ - (минимум 1 символ).

inputPath разбивается по /, пустые сегменты игнорируются.
Пример сопоставления

pattern: cave[id]chamber
path: cave/abc-01/chamber
params: { id: "abc-01" }

Алгоритм

text
match — найти первое правило (слева направо), которое полностью покрывает путь.
redirect — если у правила есть redirect, подставить {param}, заменить текущий путь и начать цикл заново. Процессоры этого правила не выполняются.
processors — если у правила есть список процессоров, выполнить их по порядку. Если процессор вернул строку, это новое правило(путь) и начинается новый цикл (при повторении цикла возвращаем destination).
destination — вернуть destination с подстановками.

При любой ошибке нужно вернуть errorPath.
Примеры ввода и вывода

Пример 1. Простое сопоставление.

const config = {
pathRules: [
{ pattern: "users[id]", destination: "/pages/user.html" }
],
errorPath: "/pages/error.html"
};
await interpretNavConfig(config, "users/abc-01");
// → "/pages/user.html"

Пример 2. Опциональный параметр (?): сегмент может отсутствовать в пути.

const config = {
pathRules: [
{ pattern: "archive[year][month?]", destination: "/pages/archive.html" }
],
errorPath: "/pages/error.html"
};
await interpretNavConfig(config, "archive/2024");
// → "/pages/archive.html"

Пример 3. Путь должен полностью совпадать с шаблоном — лишних сегментов быть не может. Шаблон "a[b?]" допускает 1 сегмент (a) или 2 (a, b); путь из трёх сегментов не подходит.

const config = {
pathRules: [
{ pattern: "a[b?]", destination: "/ok" }
],
errorPath: "/err"
};
await interpretNavConfig(config, "a/b/c");
// → "/err" (нет совпадения — лишний сегмент)

Answer 1

Ниже готовая реализация interpretNavConfig на JavaScript.

js
const PARAM_VALUE_RE = /^[A-Za-z0-9_-]+$/;
const PARAM_NAME_RE = /^[A-Za-z0-9_-]+$/;

async function interpretNavConfig(config, inputPath) {
  try {
    if (
      !config ||
      !Array.isArray(config.pathRules) ||
      typeof config.errorPath !== "string"
    ) {
      return config?.errorPath ?? "";
    }

    const visitedPaths = new Set();
    let currentPath = String(inputPath ?? "");

    const MAX_STEPS = 100;

    for (let step = 0; step < MAX_STEPS; step++) {
      const matched = findMatchingRule(config.pathRules, currentPath);

      if (!matched) {
        return config.errorPath;
      }

      const { rule, params } = matched;

      if (Object.prototype.hasOwnProperty.call(rule, "redirect")) {
        if (typeof rule.redirect !== "string") {
          return config.errorPath;
        }

        const nextPath = fillTemplate(rule.redirect, params);

        if (visitedPaths.has(nextPath)) {
          return config.errorPath;
        }

        visitedPaths.add(currentPath);
        currentPath = nextPath;
        continue;
      }

      if (Array.isArray(rule.processors)) {
        let shouldRestart = false;

        for (const processorRef of rule.processors) {
          const processor = resolveProcessor(config.processors, processorRef);

          if (typeof processor !== "function") {
            return config.errorPath;
          }

          const context = {
            ...params,
            path: currentPath,
            params: { ...params },
            rule,
            config,
          };

          const result = await processor(context, params, currentPath);

          if (typeof result === "string") {
            if (visitedPaths.has(result)) {
              if (typeof rule.destination !== "string") {
                return config.errorPath;
              }

              return fillTemplate(rule.destination, params);
            }

            visitedPaths.add(currentPath);
            currentPath = result;
            shouldRestart = true;
            break;
          }
        }

        if (shouldRestart) {
          continue;
        }
      }

      if (typeof rule.destination !== "string") {
        return config.errorPath;
      }

      return fillTemplate(rule.destination, params);
    }

    return config.errorPath;
  } catch {
    return config?.errorPath ?? "";
  }
}

function findMatchingRule(pathRules, inputPath) {
  for (const rule of pathRules) {
    if (!rule || typeof rule.pattern !== "string") {
      continue;
    }

    const tokens = parsePattern(rule.pattern);
    const segments = splitPath(inputPath);
    const params = matchTokens(tokens, segments);

    if (params) {
      return { rule, params };
    }
  }

  return null;
}

function splitPath(path) {
  return String(path)
    .split("/")
    .filter(Boolean);
}

function parsePattern(pattern) {
  const tokens = [];
  let buffer = "";

  for (let i = 0; i < pattern.length; i++) {
    const ch = pattern[i];

    if (ch === "/") {
      if (buffer) {
        tokens.push({ type: "fixed", value: buffer });
        buffer = "";
      }
      continue;
    }

    if (ch === "[") {
      if (buffer) {
        tokens.push({ type: "fixed", value: buffer });
        buffer = "";
      }

      const closeIndex = pattern.indexOf("]", i);

      if (closeIndex === -1) {
        throw new Error("Invalid pattern");
      }

      const rawParam = pattern.slice(i + 1, closeIndex);

      if (!rawParam) {
        throw new Error("Empty parameter");
      }

      const optional = rawParam.includes("?");
      const lower = rawParam.includes("~");
      const name = rawParam.replace(/[?~]/g, "");

      if (!PARAM_NAME_RE.test(name)) {
        throw new Error("Invalid parameter name");
      }

      tokens.push({
        type: "param",
        name,
        optional,
        lower,
      });

      i = closeIndex;
      continue;
    }

    buffer += ch;
  }

  if (buffer) {
    tokens.push({ type: "fixed", value: buffer });
  }

  return tokens;
}

function matchTokens(tokens, segments) {
  function dfs(tokenIndex, segmentIndex, params) {
    if (tokenIndex === tokens.length && segmentIndex === segments.length) {
      return params;
    }

    if (tokenIndex >= tokens.length) {
      return null;
    }

    const token = tokens[tokenIndex];

    if (token.type === "fixed") {
      if (segmentIndex >= segments.length) {
        return null;
      }

      if (segments[segmentIndex] !== token.value) {
        return null;
      }

      return dfs(tokenIndex + 1, segmentIndex + 1, params);
    }

    if (token.type === "param") {
      if (segmentIndex < segments.length) {
        const value = segments[segmentIndex];

        if (PARAM_VALUE_RE.test(value)) {
          const nextParams = {
            ...params,
            [token.name]: token.lower ? value.toLowerCase() : value,
          };

          const consumed = dfs(tokenIndex + 1, segmentIndex + 1, nextParams);

          if (consumed) {
            return consumed;
          }
        }
      }

      if (token.optional) {
        return dfs(tokenIndex + 1, segmentIndex, params);
      }

      return null;
    }

    return null;
  }

  return dfs(0, 0, {});
}

function fillTemplate(template, params) {
  return template.replace(/\{([A-Za-z0-9_-]+)\}/g, (_, name) => {
    return Object.prototype.hasOwnProperty.call(params, name)
      ? String(params[name])
      : "";
  });
}

function resolveProcessor(processors, processorRef) {
  if (typeof processorRef === "function") {
    return processorRef;
  }

  if (!processors) {
    return null;
  }

  if (typeof processorRef === "string") {
    if (processors instanceof Map) {
      return processors.get(processorRef);
    }

    return processors[processorRef];
  }

  if (typeof processorRef === "number" && Array.isArray(processors)) {
    return processors[processorRef];
  }

  return null;
}

// Для Node.js:
// module.exports = { interpretNavConfig };

Проверка на ваших примерах:

js
const config1 = {
  pathRules: [
    { pattern: "users[id]", destination: "/pages/user.html" }
  ],
  errorPath: "/pages/error.html"
};

console.log(await interpretNavConfig(config1, "users/abc-01"));
// "/pages/user.html"


const config2 = {
  pathRules: [
    { pattern: "archive[year][month?]", destination: "/pages/archive.html" }
  ],
  errorPath: "/pages/error.html"
};

console.log(await interpretNavConfig(config2, "archive/2024"));
// "/pages/archive.html"


const config3 = {
  pathRules: [
    { pattern: "a[b?]", destination: "/ok" }
  ],
  errorPath: "/err"
};

console.log(await interpretNavConfig(config3, "a/b/c"));
// "/err"

A. Охота за сокровищами Сегодня вы — искатель при...

Domanda

Pensiero

Risposta

Condividi questa Q&A