| 1 | /*
|
|---|
| 2 | MIT License http://www.opensource.org/licenses/mit-license.php
|
|---|
| 3 | Author Tobias Koppers @sokra
|
|---|
| 4 | */
|
|---|
| 5 |
|
|---|
| 6 | "use strict";
|
|---|
| 7 |
|
|---|
| 8 | /**
|
|---|
| 9 | * Returns quoted meta.
|
|---|
| 10 | * @param {string} str string
|
|---|
| 11 | * @returns {string} quoted meta
|
|---|
| 12 | */
|
|---|
| 13 | const quoteMeta = (str) => str.replace(/[-[\]\\/{}()*+?.^$|]/g, "\\$&");
|
|---|
| 14 |
|
|---|
| 15 | /**
|
|---|
| 16 | * Quote meta in char class.
|
|---|
| 17 | * @param {string} char character to escape for use in character class
|
|---|
| 18 | * @returns {string} escaped character
|
|---|
| 19 | */
|
|---|
| 20 | const quoteMetaInCharClass = (char) => {
|
|---|
| 21 | // In character class, only these need escaping: ] \ ^ -
|
|---|
| 22 | if (char === "]" || char === "\\" || char === "^" || char === "-") {
|
|---|
| 23 | return `\\${char}`;
|
|---|
| 24 | }
|
|---|
| 25 | return char;
|
|---|
| 26 | };
|
|---|
| 27 |
|
|---|
| 28 | /**
|
|---|
| 29 | * Converts an array of single characters into an optimized character class string
|
|---|
| 30 | * using ranges where possible. E.g., ["1","2","3","4","a"] => "1-4a"
|
|---|
| 31 | * @param {string[]} chars array of single characters (should be sorted)
|
|---|
| 32 | * @returns {string} optimized character class content (without the brackets)
|
|---|
| 33 | */
|
|---|
| 34 | const charsToCharClassContent = (chars) => {
|
|---|
| 35 | if (chars.length === 0) return "";
|
|---|
| 36 | if (chars.length === 1) return quoteMetaInCharClass(chars[0]);
|
|---|
| 37 |
|
|---|
| 38 | // Sort by char code
|
|---|
| 39 | const sorted = [...chars].sort((a, b) => a.charCodeAt(0) - b.charCodeAt(0));
|
|---|
| 40 |
|
|---|
| 41 | /** @type {string[]} */
|
|---|
| 42 | const parts = [];
|
|---|
| 43 | let rangeStart = sorted[0];
|
|---|
| 44 | let rangeEnd = sorted[0];
|
|---|
| 45 |
|
|---|
| 46 | for (let i = 1; i < sorted.length; i++) {
|
|---|
| 47 | const char = sorted[i];
|
|---|
| 48 | const prevCode = rangeEnd.charCodeAt(0);
|
|---|
| 49 | const currCode = char.charCodeAt(0);
|
|---|
| 50 |
|
|---|
| 51 | if (currCode === prevCode + 1) {
|
|---|
| 52 | // Extend the range
|
|---|
| 53 | rangeEnd = char;
|
|---|
| 54 | } else {
|
|---|
| 55 | // Flush the current range
|
|---|
| 56 | parts.push(formatRange(rangeStart, rangeEnd));
|
|---|
| 57 | rangeStart = char;
|
|---|
| 58 | rangeEnd = char;
|
|---|
| 59 | }
|
|---|
| 60 | }
|
|---|
| 61 | // Flush the last range
|
|---|
| 62 | parts.push(formatRange(rangeStart, rangeEnd));
|
|---|
| 63 |
|
|---|
| 64 | return parts.join("");
|
|---|
| 65 | };
|
|---|
| 66 |
|
|---|
| 67 | /**
|
|---|
| 68 | * Formats a range of characters for use in a character class
|
|---|
| 69 | * @param {string} start start character
|
|---|
| 70 | * @param {string} end end character
|
|---|
| 71 | * @returns {string} formatted range
|
|---|
| 72 | */
|
|---|
| 73 | const formatRange = (start, end) => {
|
|---|
| 74 | const startCode = start.charCodeAt(0);
|
|---|
| 75 | const endCode = end.charCodeAt(0);
|
|---|
| 76 | const length = endCode - startCode + 1;
|
|---|
| 77 |
|
|---|
| 78 | if (length === 1) {
|
|---|
| 79 | return quoteMetaInCharClass(start);
|
|---|
| 80 | }
|
|---|
| 81 | if (length === 2) {
|
|---|
| 82 | // For 2 chars, just list them (e.g., "ab" instead of "a-b")
|
|---|
| 83 | return quoteMetaInCharClass(start) + quoteMetaInCharClass(end);
|
|---|
| 84 | }
|
|---|
| 85 | // For 3+ chars, use range notation
|
|---|
| 86 | return `${quoteMetaInCharClass(start)}-${quoteMetaInCharClass(end)}`;
|
|---|
| 87 | };
|
|---|
| 88 |
|
|---|
| 89 | /**
|
|---|
| 90 | * Returns string.
|
|---|
| 91 | * @param {string} str string
|
|---|
| 92 | * @returns {string} string
|
|---|
| 93 | */
|
|---|
| 94 | const toSimpleString = (str) => {
|
|---|
| 95 | if (`${Number(str)}` === str) {
|
|---|
| 96 | return str;
|
|---|
| 97 | }
|
|---|
| 98 | return JSON.stringify(str);
|
|---|
| 99 | };
|
|---|
| 100 |
|
|---|
| 101 | /**
|
|---|
| 102 | * Compile boolean matcher.
|
|---|
| 103 | * @param {Record<string | number, boolean>} map value map
|
|---|
| 104 | * @returns {boolean | ((value: string) => string)} true/false, when unconditionally true/false, or a template function to determine the value at runtime
|
|---|
| 105 | */
|
|---|
| 106 | const compileBooleanMatcher = (map) => {
|
|---|
| 107 | const positiveItems = Object.keys(map).filter((i) => map[i]);
|
|---|
| 108 | const negativeItems = Object.keys(map).filter((i) => !map[i]);
|
|---|
| 109 | if (positiveItems.length === 0) return false;
|
|---|
| 110 | if (negativeItems.length === 0) return true;
|
|---|
| 111 | return compileBooleanMatcherFromLists(positiveItems, negativeItems);
|
|---|
| 112 | };
|
|---|
| 113 |
|
|---|
| 114 | /**
|
|---|
| 115 | * Compile boolean matcher from lists.
|
|---|
| 116 | * @param {string[]} positiveItems positive items
|
|---|
| 117 | * @param {string[]} negativeItems negative items
|
|---|
| 118 | * @returns {(value: string) => string} a template function to determine the value at runtime
|
|---|
| 119 | */
|
|---|
| 120 | const compileBooleanMatcherFromLists = (positiveItems, negativeItems) => {
|
|---|
| 121 | if (positiveItems.length === 0) return () => "false";
|
|---|
| 122 | if (negativeItems.length === 0) return () => "true";
|
|---|
| 123 | if (positiveItems.length === 1) {
|
|---|
| 124 | return (value) => `${toSimpleString(positiveItems[0])} == ${value}`;
|
|---|
| 125 | }
|
|---|
| 126 | if (negativeItems.length === 1) {
|
|---|
| 127 | return (value) => `${toSimpleString(negativeItems[0])} != ${value}`;
|
|---|
| 128 | }
|
|---|
| 129 | const positiveRegexp = itemsToRegexp(positiveItems);
|
|---|
| 130 | const negativeRegexp = itemsToRegexp(negativeItems);
|
|---|
| 131 | if (positiveRegexp.length <= negativeRegexp.length) {
|
|---|
| 132 | return (value) => `/^${positiveRegexp}$/.test(${value})`;
|
|---|
| 133 | }
|
|---|
| 134 | return (value) => `!/^${negativeRegexp}$/.test(${value})`;
|
|---|
| 135 | };
|
|---|
| 136 |
|
|---|
| 137 | /** @typedef {string[][]} ListOfCommonItems */
|
|---|
| 138 |
|
|---|
| 139 | /**
|
|---|
| 140 | * Returns list of common items.
|
|---|
| 141 | * @param {Set<string>} itemsSet items set
|
|---|
| 142 | * @param {(str: string) => string | false} getKey get key function
|
|---|
| 143 | * @param {(str: string[]) => boolean} condition condition
|
|---|
| 144 | * @returns {ListOfCommonItems} list of common items
|
|---|
| 145 | */
|
|---|
| 146 | const popCommonItems = (itemsSet, getKey, condition) => {
|
|---|
| 147 | /** @type {Map<string, string[]>} */
|
|---|
| 148 | const map = new Map();
|
|---|
| 149 | for (const item of itemsSet) {
|
|---|
| 150 | const key = getKey(item);
|
|---|
| 151 | if (key) {
|
|---|
| 152 | let list = map.get(key);
|
|---|
| 153 | if (list === undefined) {
|
|---|
| 154 | /** @type {string[]} */
|
|---|
| 155 | list = [];
|
|---|
| 156 | map.set(key, list);
|
|---|
| 157 | }
|
|---|
| 158 | list.push(item);
|
|---|
| 159 | }
|
|---|
| 160 | }
|
|---|
| 161 | /** @type {ListOfCommonItems} */
|
|---|
| 162 | const result = [];
|
|---|
| 163 | for (const list of map.values()) {
|
|---|
| 164 | if (condition(list)) {
|
|---|
| 165 | for (const item of list) {
|
|---|
| 166 | itemsSet.delete(item);
|
|---|
| 167 | }
|
|---|
| 168 | result.push(list);
|
|---|
| 169 | }
|
|---|
| 170 | }
|
|---|
| 171 | return result;
|
|---|
| 172 | };
|
|---|
| 173 |
|
|---|
| 174 | /**
|
|---|
| 175 | * Gets common prefix.
|
|---|
| 176 | * @param {string[]} items items
|
|---|
| 177 | * @returns {string} common prefix
|
|---|
| 178 | */
|
|---|
| 179 | const getCommonPrefix = (items) => {
|
|---|
| 180 | let prefix = items[0];
|
|---|
| 181 | for (let i = 1; i < items.length; i++) {
|
|---|
| 182 | const item = items[i];
|
|---|
| 183 | for (let p = 0; p < prefix.length; p++) {
|
|---|
| 184 | if (item[p] !== prefix[p]) {
|
|---|
| 185 | prefix = prefix.slice(0, p);
|
|---|
| 186 | break;
|
|---|
| 187 | }
|
|---|
| 188 | }
|
|---|
| 189 | }
|
|---|
| 190 | return prefix;
|
|---|
| 191 | };
|
|---|
| 192 |
|
|---|
| 193 | /**
|
|---|
| 194 | * Gets common suffix.
|
|---|
| 195 | * @param {string[]} items items
|
|---|
| 196 | * @returns {string} common suffix
|
|---|
| 197 | */
|
|---|
| 198 | const getCommonSuffix = (items) => {
|
|---|
| 199 | let suffix = items[0];
|
|---|
| 200 | for (let i = 1; i < items.length; i++) {
|
|---|
| 201 | const item = items[i];
|
|---|
| 202 | for (let p = item.length - 1, s = suffix.length - 1; s >= 0; p--, s--) {
|
|---|
| 203 | if (item[p] !== suffix[s]) {
|
|---|
| 204 | suffix = suffix.slice(s + 1);
|
|---|
| 205 | break;
|
|---|
| 206 | }
|
|---|
| 207 | }
|
|---|
| 208 | }
|
|---|
| 209 | return suffix;
|
|---|
| 210 | };
|
|---|
| 211 |
|
|---|
| 212 | /**
|
|---|
| 213 | * Returns regexp.
|
|---|
| 214 | * @param {string[]} itemsArr array of items
|
|---|
| 215 | * @returns {string} regexp
|
|---|
| 216 | */
|
|---|
| 217 | const itemsToRegexp = (itemsArr) => {
|
|---|
| 218 | if (itemsArr.length === 1) {
|
|---|
| 219 | return quoteMeta(itemsArr[0]);
|
|---|
| 220 | }
|
|---|
| 221 | /** @type {string[]} */
|
|---|
| 222 | const finishedItems = [];
|
|---|
| 223 |
|
|---|
| 224 | // merge single char items: (a|b|c|d|ef) => ([abcd]|ef)
|
|---|
| 225 | let countOfSingleCharItems = 0;
|
|---|
| 226 | for (const item of itemsArr) {
|
|---|
| 227 | if (item.length === 1) {
|
|---|
| 228 | countOfSingleCharItems++;
|
|---|
| 229 | }
|
|---|
| 230 | }
|
|---|
| 231 | // special case for only single char items
|
|---|
| 232 | if (countOfSingleCharItems === itemsArr.length) {
|
|---|
| 233 | return `[${charsToCharClassContent(itemsArr)}]`;
|
|---|
| 234 | }
|
|---|
| 235 | /** @type {Set<string>} */
|
|---|
| 236 | const items = new Set(itemsArr.sort());
|
|---|
| 237 | if (countOfSingleCharItems > 2) {
|
|---|
| 238 | /** @type {string[]} */
|
|---|
| 239 | const singleCharItems = [];
|
|---|
| 240 | for (const item of items) {
|
|---|
| 241 | if (item.length === 1) {
|
|---|
| 242 | singleCharItems.push(item);
|
|---|
| 243 | items.delete(item);
|
|---|
| 244 | }
|
|---|
| 245 | }
|
|---|
| 246 | finishedItems.push(`[${charsToCharClassContent(singleCharItems)}]`);
|
|---|
| 247 | }
|
|---|
| 248 |
|
|---|
| 249 | // special case for 2 items with common prefix/suffix
|
|---|
| 250 | if (finishedItems.length === 0 && items.size === 2) {
|
|---|
| 251 | const prefix = getCommonPrefix(itemsArr);
|
|---|
| 252 | const suffix = getCommonSuffix(
|
|---|
| 253 | itemsArr.map((item) => item.slice(prefix.length))
|
|---|
| 254 | );
|
|---|
| 255 | if (prefix.length > 0 || suffix.length > 0) {
|
|---|
| 256 | return `${quoteMeta(prefix)}${itemsToRegexp(
|
|---|
| 257 | itemsArr.map((i) => i.slice(prefix.length, -suffix.length || undefined))
|
|---|
| 258 | )}${quoteMeta(suffix)}`;
|
|---|
| 259 | }
|
|---|
| 260 | }
|
|---|
| 261 |
|
|---|
| 262 | // special case for 2 items with common suffix
|
|---|
| 263 | if (finishedItems.length === 0 && items.size === 2) {
|
|---|
| 264 | /** @type {SetIterator<string>} */
|
|---|
| 265 | const it = items[Symbol.iterator]();
|
|---|
| 266 | const a = /** @type {string} */ (it.next().value);
|
|---|
| 267 | const b = /** @type {string} */ (it.next().value);
|
|---|
| 268 | if (a.length > 0 && b.length > 0 && a.slice(-1) === b.slice(-1)) {
|
|---|
| 269 | return `${itemsToRegexp([a.slice(0, -1), b.slice(0, -1)])}${quoteMeta(
|
|---|
| 270 | a.slice(-1)
|
|---|
| 271 | )}`;
|
|---|
| 272 | }
|
|---|
| 273 | }
|
|---|
| 274 |
|
|---|
| 275 | // find common prefix: (a1|a2|a3|a4|b5) => (a(1|2|3|4)|b5)
|
|---|
| 276 | const prefixed = popCommonItems(
|
|---|
| 277 | items,
|
|---|
| 278 | (item) => (item.length >= 1 ? item[0] : false),
|
|---|
| 279 | (list) => {
|
|---|
| 280 | if (list.length >= 3) return true;
|
|---|
| 281 | if (list.length <= 1) return false;
|
|---|
| 282 | return list[0][1] === list[1][1];
|
|---|
| 283 | }
|
|---|
| 284 | );
|
|---|
| 285 | for (const prefixedItems of prefixed) {
|
|---|
| 286 | const prefix = getCommonPrefix(prefixedItems);
|
|---|
| 287 | finishedItems.push(
|
|---|
| 288 | `${quoteMeta(prefix)}${itemsToRegexp(
|
|---|
| 289 | prefixedItems.map((i) => i.slice(prefix.length))
|
|---|
| 290 | )}`
|
|---|
| 291 | );
|
|---|
| 292 | }
|
|---|
| 293 |
|
|---|
| 294 | // find common suffix: (a1|b1|c1|d1|e2) => ((a|b|c|d)1|e2)
|
|---|
| 295 | const suffixed = popCommonItems(
|
|---|
| 296 | items,
|
|---|
| 297 | (item) => (item.length >= 1 ? item.slice(-1) : false),
|
|---|
| 298 | (list) => {
|
|---|
| 299 | if (list.length >= 3) return true;
|
|---|
| 300 | if (list.length <= 1) return false;
|
|---|
| 301 | return list[0].slice(-2) === list[1].slice(-2);
|
|---|
| 302 | }
|
|---|
| 303 | );
|
|---|
| 304 | for (const suffixedItems of suffixed) {
|
|---|
| 305 | const suffix = getCommonSuffix(suffixedItems);
|
|---|
| 306 | finishedItems.push(
|
|---|
| 307 | `${itemsToRegexp(
|
|---|
| 308 | suffixedItems.map((i) => i.slice(0, -suffix.length))
|
|---|
| 309 | )}${quoteMeta(suffix)}`
|
|---|
| 310 | );
|
|---|
| 311 | }
|
|---|
| 312 |
|
|---|
| 313 | /** @type {string[]} */
|
|---|
| 314 | const conditional = [...finishedItems, ...Array.from(items, quoteMeta)];
|
|---|
| 315 | if (conditional.length === 1) return conditional[0];
|
|---|
| 316 | return `(${conditional.join("|")})`;
|
|---|
| 317 | };
|
|---|
| 318 |
|
|---|
| 319 | compileBooleanMatcher.fromLists = compileBooleanMatcherFromLists;
|
|---|
| 320 | compileBooleanMatcher.itemsToRegexp = itemsToRegexp;
|
|---|
| 321 |
|
|---|
| 322 | module.exports = compileBooleanMatcher;
|
|---|
