regexp-ast-analysis - npm Package Compare versions

Comparing version 0.1.2 to 0.1.3

CHANGELOG.md

 # Changelog
 
+## 0.1.3 (2021-04-13)
+
+### Fixed
+
+- `isEmptyBackreference`: Fixed stack overflow for circular nested backreferences.
+
+### Changed
+
+- `is{Empty,Strict}Backreference`: More efficient implementation.
+- `hasSome{Ancestor,Descendant}`: Node can now be given to the functions instead of condition functions.
+- `getClosestAncestor`: The return type is now stricter and exported as `ClosestAncestor<A, B>`.
+
+
 ## 0.1.2 (2021-04-12)
@@ -4,0 +17,0 @@

index.d.ts

@@ -128,2 +128,5 @@ // Generated by dts-bundle-generator v5.8.0
  *
+ * If the given condition is an AST node instead of a function, `hasSomeAncestor` will behave as if the condition
+ * function was `d => d === conditionNode`.
+ *
  * The ancestors will be iterated in the order from closest to farthest.
@@ -134,3 +137,3 @@ * The condition function will not be called on the given node.
 	node: T,
-	conditionFn: (ancestor: Ancestor<T>) => boolean
+	condition: ((ancestor: Ancestor<T>) => boolean) | Node
 ): boolean;
@@ -156,14 +159,17 @@ /**
  *
- * This function is short-circuited, so as soon as any `conditionFn` returns `true`, `true` will be returned.
+ * If the given condition is an AST node instead of a function, `hasSomeDescendant` will behave as if the condition
+ * function was `d => d === conditionNode`.
  *
+ * This function is short-circuited, so as soon as any `condition` returns `true`, `true` will be returned.
+ *
  * @param node
- * @param conditionFn
+ * @param condition
  * @param descentConditionFn An optional function to decide whether the descendant of the given node will be checked as
  * well.
  *
- * This function will be called with some node only after `conditionFn` has returned `false` for this node.
+ * This function will be called with some node only after `condition` has returned `false` for this node.
  */
 export declare function hasSomeDescendant<T extends Node>(
-	node: T & Node,
-	conditionFn: (descendant: Descendant<T>) => boolean,
+	node: T,
+	condition: ((descendant: Descendant<T>) => boolean) | Node,
 	descentConditionFn?: (descendant: Descendant<T>) => boolean
@@ -312,10 +318,17 @@ ): boolean;
 /**
+ * The type of the closest ancestor of two nodes with the given types.
+ *
+ * @see {@link getClosestAncestor}
+ */
+export declare type ClosestAncestor<A extends Node, B extends Node> = Exclude<A | B, Descendant<Pattern>> extends never
+	? Exclude<(A | Ancestor<A>) & (B | Ancestor<B>), RegExpLiteral>
+	: (A | Ancestor<A>) & (B | Ancestor<B>);
+/**
  * Returns the closest ancestor of the given nodes.
  *
  * If the two nodes are the same node, the given node will be returned.
+ *
+ * If the two given nodes are not part of the same AST tree, an error will be thrown.
  */
-export declare function getClosestAncestor<A extends Node, B extends Node>(
-	a: A,
-	b: B
-): (A | Ancestor<A>) & (B | Ancestor<B>);
+export declare function getClosestAncestor<A extends Node, B extends Node>(a: A, b: B): ClosestAncestor<A, B>;
 /**
@@ -322,0 +335,0 @@ * Returns how many times the regex engine can match the given element at most.

index.js

@@ -1,1 +0,1 @@
-"use strict";Object.defineProperty(exports,"__esModule",{value:!0});var e=require("regexpp"),t=require("refa");function r(e,t){throw new Error(t||e)}function n(e,t){if(Array.isArray(e)){const r=e;return r.length>0&&r.every(t)}return t(e)}function a(e,t){return Array.isArray(e)?e.some(t):t(e)}function s(e){return n(e,c)}function c(e){switch(e.type){case"Alternative":return e.elements.every(c);case"Assertion":return!0;case"Character":case"CharacterClass":case"CharacterSet":return!1;case"Quantifier":return 0===e.max||c(e.element);case"Backreference":return g(e);case"CapturingGroup":case"Group":return e.alternatives.length>0&&e.alternatives.every(c);default:throw r(e)}}function i(e,t){return function e(n){switch(n.type){case"Alternative":return n.elements.every(e);case"Assertion":return!0;case"Backreference":return l(n,t);case"Character":case"CharacterClass":case"CharacterSet":return!1;case"CapturingGroup":case"Group":return n.alternatives.some(e);case"Quantifier":return 0===n.min||e(n.element);default:throw r(n)}}(e)}function o(e){switch(e.type){case"Alternative":return e.elements.every(o);case"Assertion":return!1;case"Backreference":return g(e);case"Character":case"CharacterClass":case"CharacterSet":return!1;case"CapturingGroup":case"Group":return e.alternatives.length>0&&e.alternatives.every(o);case"Quantifier":return 0===e.max||o(e.element);default:throw r(e)}}function u(e){return function t(n){switch(n.type){case"Alternative":return n.elements.every(t);case"Assertion":return!1;case"Backreference":return l(n,e);case"Character":case"CharacterClass":case"CharacterSet":return!1;case"CapturingGroup":case"Group":return n.alternatives.some(t);case"Quantifier":return 0===n.min||t(n.element);default:throw r(n)}}(e)}function l(e,t){return!!g(e)||!!p(e.resolved,(e=>e===t))&&(!x(e)||i(e.resolved,t))}function p(e,t){let r=e.parent;for(;r;){if(t(r))return!0;r=r.parent}return!1}function h(e,t,r){if(t(e))return!0;if(r&&!r(e))return!1;switch(e.type){case"Alternative":return e.elements.some((e=>h(e,t,r)));case"Assertion":return("lookahead"===e.kind||"lookbehind"===e.kind)&&e.alternatives.some((e=>h(e,t,r)));case"CapturingGroup":case"Group":case"Pattern":return e.alternatives.some((e=>h(e,t,r)));case"CharacterClass":return e.elements.some((e=>h(e,t,r)));case"CharacterClassRange":return h(e.min,t,r)||h(e.max,t,r);case"Quantifier":return h(e.element,t,r);case"RegExpLiteral":return h(e.pattern,t,r)||h(e.flags,t,r)}return!1}function f(e){switch(e.type){case"RegExpLiteral":return e.pattern;case"Pattern":return e;case"Flags":if(e.parent)return e.parent.pattern;throw new Error("Unable to find the pattern of flags without a RegExp literal.");default:{let t=e.parent;for(;"Pattern"!==t.type;)t=t.parent;return t}}}function m(e){let t;return p(e,(e=>"Assertion"===e.type&&(t=e,!0))),void 0===t||"lookahead"===t.kind?"ltr":"rtl"}function d(e){return"end"===e||"lookahead"===e?"ltr":"rtl"}function g(e){const t=e.resolved;if(p(e,(e=>e===t)))return!0;if(s(t))return!0;return!function t(r){const n=r.parent;switch(n.type){case"Alternative":{const a=n.elements.indexOf(r);let s;if(s="ltr"===m(r)?n.elements.slice(a+1):n.elements.slice(0,a),s.some((t=>h(t,(t=>t===e)))))return!0;const c=n.parent;return"Pattern"!==c.type&&(("Assertion"!==c.type||!c.negate)&&t(c))}case"Quantifier":return t(n);default:throw new Error("What happened?")}}(t)}function x(e){const t=e.resolved;if(p(e,(e=>e===t)))return!1;return function t(r){const n=r.parent;switch(n.type){case"Alternative":{const a=n.elements.indexOf(r);let s;if(s="ltr"===m(r)?n.elements.slice(a+1):n.elements.slice(0,a),s.some((t=>h(t,(t=>t===e)))))return!0;const c=n.parent;return"Pattern"!==c.type&&(("Assertion"!==c.type||!c.negate)&&(!(c.alternatives.length>1)&&t(c)))}case"Quantifier":return 0!==n.min&&t(n);default:throw new Error("What happened?")}}(t)}const C={min:0,max:0},y={min:1,max:1};function v(e){return Array.isArray(e)?k(e):A(e)}function k(e){let t=1/0,r=0;for(const n of e){const e=A(n);e&&(t=Math.min(t,e.min),r=Math.max(r,e.max))}return t>r?void 0:{min:t,max:r}}function A(e){switch(e.type){case"Assertion":return C;case"Character":case"CharacterClass":case"CharacterSet":return y;case"Quantifier":{if(0===e.max)return C;const t=A(e.element);return t?0===t.max?C:{min:t.min*e.min,max:t.max*e.max}:0===e.min?C:void 0}case"Alternative":{let t=0,r=0;for(const n of e.elements){const e=A(n);if(!e)return;t+=e.min,r+=e.max}return{min:t,max:r}}case"CapturingGroup":case"Group":return k(e.alternatives);case"Backreference":if(g(e))return C;{const t=A(e.resolved);return t?t.min>0&&!x(e)?{min:0,max:t.max}:t:x(e)?C:void 0}default:throw r(e)}}function w(e,r){const{positive:n,negated:a}=function(e){if(Array.isArray(e)){const t=e;if(function(e){for(let t=0,r=e.length;t<r;t++)if("CharacterClass"===e[t].type)return!1;return!0}(t))return{positive:t,negated:void 0};if(function(e){for(let t=0,r=e.length;t<r;t++){const r=e[t];if("CharacterClass"!==r.type||!r.negate)return!1}return!0}(t))return{positive:void 0,negated:t};{const e=[],r=[];for(let n=0,a=t.length;n<a;n++){const a=t[n];"CharacterClass"===a.type?a.negate?r.push(a):e.push(...a.elements):e.push(a)}return{positive:e,negated:r}}}{const t=e;return"CharacterClass"===t.type?t.negate?{positive:void 0,negated:[t]}:{positive:t.elements,negated:void 0}:{positive:[t],negated:void 0}}}(e);return a?n?t.JS.createCharSet(S(n),r).union(...a.map((e=>t.JS.createCharSet(S(e.elements),r).negate()))):1===a.length?t.JS.createCharSet(S(a[0].elements),r).negate():exports.Chars.empty(r).union(...a.map((e=>t.JS.createCharSet(S(e.elements),r).negate()))):n?t.JS.createCharSet(S(n),r):exports.Chars.empty(r)}function S(e){return e.map((e=>{switch(e.type){case"Character":return e.value;case"CharacterClassRange":return{min:e.min.value,max:e.max.value};case"CharacterSet":return e;default:throw r(e)}}))}function E(e,t){if(e==t)return!0;if(!e||!t||e.type!=t.type)return!1;switch(e.type){case"Alternative":{const r=t;return b(e.elements,r.elements)}case"Assertion":{const r=t;if(e.kind===r.kind){if("lookahead"===e.kind||"lookbehind"===e.kind){const r=t;return e.negate===r.negate&&b(e.alternatives,r.alternatives)}return e.raw===r.raw}return!1}case"Backreference":{const r=t;return g(e)?g(r):E(e.resolved,r.resolved)&&x(e)==x(r)}case"Character":{const r=t;return e.value===r.value}case"CharacterClass":{const r=t;return e.negate===r.negate&&b(e.elements,r.elements)}case"CharacterClassRange":{const r=t;return E(e.min,r.min)&&E(e.max,r.max)}case"CharacterSet":{const r=t;return"property"===e.kind&&"property"===r.kind?e.negate===r.negate&&e.key===r.key:e.raw===r.raw}case"Flags":{const r=t;return e.dotAll===r.dotAll&&e.global===r.global&&e.ignoreCase===r.ignoreCase&&e.multiline===r.multiline&&e.sticky===r.sticky&&e.unicode===r.unicode}case"CapturingGroup":case"Group":case"Pattern":{const r=t;return b(e.alternatives,r.alternatives)}case"Quantifier":{const r=t;return e.min===r.min&&e.max===r.max&&e.greedy===r.greedy&&E(e.element,r.element)}case"RegExpLiteral":{const r=t;return E(e.flags,r.flags)&&E(e.pattern,r.pattern)}default:throw r(e)}}function b(e,t){if(e.length!==t.length)return!1;for(let r=0;r<e.length;r++)if(!E(e[r],t[r]))return!1;return!0}function G(e,t,n,a,s){function c(e,t,r){var n,s;a.enter&&(t=a.enter(e,t,r));if(null===(s=null===(n=a.continueInto)||void 0===n?void 0:n.call(a,e,t,r))||void 0===s||s)switch(e.type){case"Assertion":if("lookahead"===e.kind||"lookbehind"===e.kind){const n=d(e.kind),s=a.join(e.alternatives.map((e=>i(e,F(a,t,r),n))),n);a.endPath&&(t=a.endPath(t,n,"assertion")),a.assert&&(t=a.assert(t,r,s,n))}break;case"Group":case"CapturingGroup":t=a.join(e.alternatives.map((e=>i(e,F(a,t,r),r))),r);break;case"Quantifier":0===e.max||(t=0===e.min?a.join([t,c(e.element,F(a,t,r),r)],r):c(e.element,t,r))}return a.leave&&(t=a.leave(e,t,r)),t}function i(e,t,r){var n,s;let i="ltr"===r?0:e.elements.length-1;const o="ltr"===r?1:-1;let u;for(;u=e.elements[i];i+=o){t=c(u,t,r);if(!(null===(s=null===(n=a.continueAfter)||void 0===n?void 0:n.call(a,u,t,r))||void 0===s||s))break}return t}return s||(s=m(e)),"enter"===t&&(n=c(e,n,s)),function(e,t,n){function s(e){var c,i;const o=e.parent;if("CharacterClass"===o.type||"CharacterClassRange"===o.type)throw new Error("The given element cannot be part of a character class.");if(!(null===(i=null===(c=a.continueAfter)||void 0===c?void 0:c.call(a,e,t,n))||void 0===i||i))return!1;if("Quantifier"===o.type)return o.max<=1?s(o):[o,s(o)];{const t=o.elements.indexOf(e)+("ltr"===n?1:-1),a=o.elements[t];if(a)return a;{const e=o.parent;if("Pattern"===e.type)return"pattern";if("Assertion"===e.type)return"assertion";if("CapturingGroup"===e.type||"Group"===e.type)return s(e);throw r(e)}}}for(;;){let r=s(e);for(;Array.isArray(r);){const[e,s]=r;t=a.join([t,c(e,F(a,t,n),n)],n),r=s}if(!1===r)return t;if("assertion"===r||"pattern"===r)return a.endPath&&(t=a.endPath(t,n,r)),t;t=c(r,t,n),e=r}}(e,n,s)}function F(e,t,r){return e.fork?e.fork(t,r):t}function J(e,t,r){return Array.isArray(e)?P(e,t,r):Q(e,t,r)}function P(e,t,r){return j(e.map((e=>Q(e,t,r))),r)}function Q(e,t,n){switch(e.type){case"Assertion":switch(e.kind){case"word":return a();case"end":case"start":return d(e.kind)===t?n.multiline?s({char:exports.Chars.lineTerminator(n),edge:!0,exact:!0}):s(function(e){return{char:exports.Chars.empty(e),edge:!0,exact:!0}}(n)):a();case"lookahead":case"lookbehind":if(d(e.kind)===t){if(e.negate){if(h(e,(t=>t!==e&&"Assertion"===t.type)))return a();const r=P(e.alternatives,t,n),c=v(e.alternatives);return r.empty||!c?{char:exports.Chars.empty(n),empty:!1,exact:!0}:r.exact&&1===c.max?s({char:r.char.negate(),edge:!0,exact:!0}):a()}return s(O(P(e.alternatives,t,n)))}return a();default:throw r(e)}case"Character":case"CharacterSet":case"CharacterClass":return{char:w(e,n),empty:!1,exact:!0};case"Quantifier":{if(0===e.max)return s();const r=Q(e.element,t,n);return 0===e.min?j([s(),r],n):r}case"Alternative":{let r=e.elements;return"rtl"===t&&(r=[...r],r.reverse()),L(function*(){for(const e of r)yield Q(e,t,n)}(),n)}case"CapturingGroup":case"Group":return P(e.alternatives,t,n);case"Backreference":{if(g(e))return s();const r=Q(e.resolved,t,n);return r.exact=r.exact&&r.char.size<=1,x(e)?r:j([r,s()],n)}default:throw r(e)}function a(){return s({char:exports.Chars.all(n),edge:!0,exact:!1})}function s(e){return B(n,e)}}function R(e){return{char:exports.Chars.all(e),edge:!0,exact:!0}}function B(e,t){return{char:exports.Chars.empty(e),empty:!0,exact:!0,look:null!=t?t:R(e)}}exports.Chars=void 0,function(e){const r=t.CharSet.empty(65535),n=t.CharSet.empty(1114111);e.empty=function(e){return e.unicode?n:r};const a=t.CharSet.all(65535),s=t.CharSet.all(1114111);e.all=function(e){return e.unicode?s:a};const c=t.JS.createCharSet([{kind:"any"}],{unicode:!1}).negate(),i=t.JS.createCharSet([{kind:"any"}],{unicode:!0}).negate();e.lineTerminator=function(e){return e.unicode?i:c};const o=t.JS.createCharSet([{kind:"word",negate:!1}],{unicode:!1}),u=t.JS.createCharSet([{kind:"word",negate:!1}],{unicode:!0,ignoreCase:!1}),l=t.JS.createCharSet([{kind:"word",negate:!1}],{unicode:!0,ignoreCase:!0});e.word=function(e){return e.unicode?e.ignoreCase?l:u:o};const p=t.JS.createCharSet([{kind:"digit",negate:!1}],{unicode:!1}),h=t.JS.createCharSet([{kind:"digit",negate:!1}],{unicode:!0});e.digit=function(e){return e.unicode?h:p};const f=t.JS.createCharSet([{kind:"space",negate:!1}],{unicode:!1}),m=t.JS.createCharSet([{kind:"space",negate:!1}],{unicode:!0});e.space=function(e){return e.unicode?m:f}}(exports.Chars||(exports.Chars={}));class M{constructor(e){this.char=e,this.exact=!0}add(e,t){!this.exact||t||this.char.isSupersetOf(e)?!this.exact&&t&&e.isSupersetOf(this.char)&&(this.exact=!0):this.exact=!1,this.char=this.char.union(e)}static emptyFromFlags(e){return new M(exports.Chars.empty(e))}static emptyFromMaximum(e){return new M(t.CharSet.empty(e))}}function j(e,t){const r=M.emptyFromFlags(t),n=[];for(const t of e)r.add(t.char,t.exact),t.empty&&n.push(t.look);if(n.length>0){const e=M.emptyFromFlags(t);let a=!1;for(const t of n)e.add(t.char,t.exact),a=a||t.edge;return{char:r.char,exact:r.exact,empty:!0,look:{char:e.char,exact:e.exact,edge:a}}}return{char:r.char,exact:r.exact,empty:!1}}function L(e,t){const r=M.emptyFromFlags(t);let n=R(t);for(const t of e){if(r.add(t.char.intersect(n.char),n.exact&&t.exact),!t.empty)return{char:r.char,exact:r.exact,empty:!1};{const e=n.char.intersect(t.look.char);n={char:e,exact:n.exact&&t.look.exact||e.isEmpty,edge:n.edge&&t.look.edge}}}return{char:r.char,exact:r.exact,empty:!0,look:n}}function O(e){if(e.empty){const t=M.emptyFromMaximum(e.char.maximum);return t.add(e.char,e.exact),t.add(e.look.char,e.look.exact),{char:t.char,exact:t.exact,edge:e.look.edge}}return{char:e.char,exact:e.exact,edge:!1}}function T(e,t,r){return G(e,"next",B(r),{join:e=>j(e,r),enter:(e,t,n)=>L([t,J(e,n,r)],r),continueInto:()=>!1,continueAfter:(e,t)=>t.empty},t)}function D(e,t,r){return G(e,"next",{char:B(r),contributors:[]},{join(e){const t=new Set;return e.forEach((e=>e.contributors.forEach((e=>t.add(e))))),{char:j(e.map((e=>e.char)),r),contributors:[...t]}},enter(e,t,n){const a=J(e,n,r);return{char:L([t.char,a],r),contributors:[...t.contributors,e]}},continueInto:()=>!1,continueAfter:(e,t)=>t.char.empty},t)}exports.followPaths=G,exports.getCapturingGroupNumber=function(t){let r=0;try{throw e.visitRegExpAST(f(t),{onCapturingGroupEnter(e){if(r++,e===t)throw new Error}}),new Error("Unable to find the given capturing group in its parent pattern.")}catch(e){return r}},exports.getClosestAncestor=function(e,t){if(e===t)return e;if(e.parent&&e.parent===t.parent)return e.parent;if(p(e,(e=>e===t)))return t;if(p(t,(t=>t===e)))return e;if(e.parent&&t.parent){const r=[],n=[];for(let t=e.parent;t;t=t.parent)r.push(t);for(let e=t.parent;e;e=e.parent)n.push(e);for(;r.length&&n.length&&r[r.length-1]===n[n.length-1];)r.pop(),n.pop();if(0===r.length)return e.parent;if(0===n.length)return t.parent;const a=r.pop().parent;if(a)return a}throw new Error("The two nodes are not part of the same tree.")},exports.getEffectiveMaximumRepetition=function(e){let t=1;for(let r=e.parent;r;r=r.parent)if("Quantifier"===r.type){if(t*=r.max,0===t)return 0}else if("Assertion"===r.type)break;return t},exports.getFirstCharAfter=function(e,t,r){return O(T(e,t,r))},exports.getFirstCharAfterWithContributors=function(e,t,r){const{char:n,contributors:a}=D(e,t,r);return{char:O(n),contributors:a}},exports.getFirstConsumedChar=J,exports.getFirstConsumedCharAfter=T,exports.getFirstConsumedCharAfterWithContributors=D,exports.getLengthRange=v,exports.getMatchingDirection=m,exports.getMatchingDirectionFromAssertionKind=d,exports.getPattern=f,exports.hasSomeAncestor=p,exports.hasSomeDescendant=h,exports.invertMatchingDirection=function(e){return"ltr"===e?"rtl":"ltr"},exports.isEmpty=function(e){return n(e,o)},exports.isEmptyBackreference=g,exports.isPotentiallyEmpty=function(e){return a(e,u)},exports.isPotentiallyZeroLength=function(e){return a(e,(e=>i(e,e)))},exports.isStrictBackreference=x,exports.isZeroLength=s,exports.matchesAllCharacters=function(e,r){return"Character"!==e.type&&("CharacterClassRange"===e.type?0===e.min.value&&e.max.value===(r.unicode?1114111:65535):"CharacterSet"===e.type?"property"===e.kind?t.JS.createCharSet([e],r).isAll:"any"===e.kind&&!!r.dotAll:!(!e.negate||0!==e.elements.length)||(e.negate?w(e.elements,r).isEmpty:w(e.elements,r).isAll))},exports.matchesNoCharacters=function(e,r){return"Character"!==e.type&&"CharacterClassRange"!==e.type&&("CharacterSet"===e.type?"property"===e.kind&&t.JS.createCharSet([e],r).isEmpty:!e.negate&&0===e.elements.length||(e.negate?w(e.elements,r).isAll:w(e.elements,r).isEmpty))},exports.structurallyEqual=E,exports.toCharSet=w;
+"use strict";Object.defineProperty(exports,"__esModule",{value:!0});var e=require("regexpp"),t=require("refa");function r(e,t){throw new Error(t||e)}function n(e,t){if(Array.isArray(e)){const r=e;return r.length>0&&r.every(t)}return t(e)}function a(e,t){return Array.isArray(e)?e.some(t):t(e)}function s(e){return n(e,c)}function c(e){switch(e.type){case"Alternative":return e.elements.every(c);case"Assertion":return!0;case"Character":case"CharacterClass":case"CharacterSet":return!1;case"Quantifier":return 0===e.max||c(e.element);case"Backreference":return x(e);case"CapturingGroup":case"Group":return e.alternatives.length>0&&e.alternatives.every(c);default:throw r(e)}}function o(e,t){return function e(n){switch(n.type){case"Alternative":return n.elements.every(e);case"Assertion":return!0;case"Backreference":return l(n,t);case"Character":case"CharacterClass":case"CharacterSet":return!1;case"CapturingGroup":case"Group":return n.alternatives.some(e);case"Quantifier":return 0===n.min||e(n.element);default:throw r(n)}}(e)}function i(e){switch(e.type){case"Alternative":return e.elements.every(i);case"Assertion":return!1;case"Backreference":return x(e);case"Character":case"CharacterClass":case"CharacterSet":return!1;case"CapturingGroup":case"Group":return e.alternatives.length>0&&e.alternatives.every(i);case"Quantifier":return 0===e.max||i(e.element);default:throw r(e)}}function u(e){return function t(n){switch(n.type){case"Alternative":return n.elements.every(t);case"Assertion":return!1;case"Backreference":return l(n,e);case"Character":case"CharacterClass":case"CharacterSet":return!1;case"CapturingGroup":case"Group":return n.alternatives.some(t);case"Quantifier":return 0===n.min||t(n.element);default:throw r(n)}}(e)}function l(e,t){return!!x(e)||!!p(e.resolved,(e=>e===t))&&(!C(e)||o(e.resolved,t))}function p(e,t){return"function"==typeof t?function(e,t){let r=e.parent;for(;r;){if(t(r))return!0;r=r.parent}return!1}(e,t):function(e,t){let r=e.parent;for(;r;){if(r===t)return!0;r=r.parent}return!1}(e,t)}function h(e,t,r){return"function"==typeof t?f(e,t,r):r?f(e,(e=>e===t),r):e===t||p(t,e)}function f(e,t,r){if(t(e))return!0;if(r&&!r(e))return!1;switch(e.type){case"Alternative":return e.elements.some((e=>f(e,t,r)));case"Assertion":return("lookahead"===e.kind||"lookbehind"===e.kind)&&e.alternatives.some((e=>f(e,t,r)));case"CapturingGroup":case"Group":case"Pattern":return e.alternatives.some((e=>f(e,t,r)));case"CharacterClass":return e.elements.some((e=>f(e,t,r)));case"CharacterClassRange":return f(e.min,t,r)||f(e.max,t,r);case"Quantifier":return f(e.element,t,r);case"RegExpLiteral":return f(e.pattern,t,r)||f(e.flags,t,r)}return!1}function m(e){switch(e.type){case"RegExpLiteral":return e.pattern;case"Pattern":return e;case"Flags":if(e.parent)return e.parent.pattern;throw new Error("Unable to find the pattern of flags without a RegExp literal.");default:{let t=e.parent;for(;"Pattern"!==t.type;)t=t.parent;return t}}}function d(e){let t;return p(e,(e=>"Assertion"===e.type&&(t=e,!0))),void 0===t||"lookahead"===t.kind?"ltr":"rtl"}function g(e){return"end"===e||"lookahead"===e?"ltr":"rtl"}function x(e){const t=e.resolved,r=S(e,t);if(r===t)return!0;if("Alternative"!==r.type)return!0;const n=new Set;for(let t=e;t;t=t.parent)n.add(t);return!function e(t){const r=t.parent;switch(r.type){case"Alternative":{const a=r.elements.indexOf(t);let s;if(s="ltr"===d(t)?r.elements.slice(a+1):r.elements.slice(0,a),s.some((e=>n.has(e))))return!0;const c=r.parent;return"Pattern"!==c.type&&(("Assertion"!==c.type||!c.negate)&&e(c))}case"Quantifier":return e(r);default:throw new Error("What happened?")}}(t)||s(t)}function C(e){const t=e.resolved,r=S(e,t);if(r===t)return!1;if("Alternative"!==r.type)return!1;const n=new Set;for(let t=e;t;t=t.parent)n.add(t);return function e(t){const r=t.parent;switch(r.type){case"Alternative":{const a=r.elements.indexOf(t);let s;if(s="ltr"===d(t)?r.elements.slice(a+1):r.elements.slice(0,a),s.some((e=>n.has(e))))return!0;const c=r.parent;return"Pattern"!==c.type&&(("Assertion"!==c.type||!c.negate)&&(!(c.alternatives.length>1)&&e(c)))}case"Quantifier":return 0!==r.min&&e(r);default:throw new Error("What happened?")}}(t)}const y={min:0,max:0},v={min:1,max:1};function k(e){return Array.isArray(e)?A(e):w(e)}function A(e){let t=1/0,r=0;for(const n of e){const e=w(n);e&&(t=Math.min(t,e.min),r=Math.max(r,e.max))}return t>r?void 0:{min:t,max:r}}function w(e){switch(e.type){case"Assertion":return y;case"Character":case"CharacterClass":case"CharacterSet":return v;case"Quantifier":{if(0===e.max)return y;const t=w(e.element);return t?0===t.max?y:{min:t.min*e.min,max:t.max*e.max}:0===e.min?y:void 0}case"Alternative":{let t=0,r=0;for(const n of e.elements){const e=w(n);if(!e)return;t+=e.min,r+=e.max}return{min:t,max:r}}case"CapturingGroup":case"Group":return A(e.alternatives);case"Backreference":if(x(e))return y;{const t=w(e.resolved);return t?t.min>0&&!C(e)?{min:0,max:t.max}:t:C(e)?y:void 0}default:throw r(e)}}function S(e,t){if(e===t)return e;if(e.parent&&e.parent===t.parent)return e.parent;{const r=b(e),n=b(t);for(;;){if(0===r.length)return e;if(0===n.length)return t;if(r[r.length-1]!==n[n.length-1])break;r.pop(),n.pop()}const a=r[r.length-1].parent;if(a)return a;throw new Error("The two nodes are not part of the same tree.")}}function b(e){const t=[];for(let r=e;r;r=r.parent)t.push(r);return t}function E(e,r){const{positive:n,negated:a}=function(e){if(Array.isArray(e)){const t=e;if(function(e){for(let t=0,r=e.length;t<r;t++)if("CharacterClass"===e[t].type)return!1;return!0}(t))return{positive:t,negated:void 0};if(function(e){for(let t=0,r=e.length;t<r;t++){const r=e[t];if("CharacterClass"!==r.type||!r.negate)return!1}return!0}(t))return{positive:void 0,negated:t};{const e=[],r=[];for(let n=0,a=t.length;n<a;n++){const a=t[n];"CharacterClass"===a.type?a.negate?r.push(a):e.push(...a.elements):e.push(a)}return{positive:e,negated:r}}}{const t=e;return"CharacterClass"===t.type?t.negate?{positive:void 0,negated:[t]}:{positive:t.elements,negated:void 0}:{positive:[t],negated:void 0}}}(e);return a?n?t.JS.createCharSet(G(n),r).union(...a.map((e=>t.JS.createCharSet(G(e.elements),r).negate()))):1===a.length?t.JS.createCharSet(G(a[0].elements),r).negate():exports.Chars.empty(r).union(...a.map((e=>t.JS.createCharSet(G(e.elements),r).negate()))):n?t.JS.createCharSet(G(n),r):exports.Chars.empty(r)}function G(e){return e.map((e=>{switch(e.type){case"Character":return e.value;case"CharacterClassRange":return{min:e.min.value,max:e.max.value};case"CharacterSet":return e;default:throw r(e)}}))}function F(e,t){if(e==t)return!0;if(!e||!t||e.type!=t.type)return!1;switch(e.type){case"Alternative":{const r=t;return J(e.elements,r.elements)}case"Assertion":{const r=t;if(e.kind===r.kind){if("lookahead"===e.kind||"lookbehind"===e.kind){const r=t;return e.negate===r.negate&&J(e.alternatives,r.alternatives)}return e.raw===r.raw}return!1}case"Backreference":{const r=t;return x(e)?x(r):F(e.resolved,r.resolved)&&C(e)==C(r)}case"Character":{const r=t;return e.value===r.value}case"CharacterClass":{const r=t;return e.negate===r.negate&&J(e.elements,r.elements)}case"CharacterClassRange":{const r=t;return F(e.min,r.min)&&F(e.max,r.max)}case"CharacterSet":{const r=t;return"property"===e.kind&&"property"===r.kind?e.negate===r.negate&&e.key===r.key:e.raw===r.raw}case"Flags":{const r=t;return e.dotAll===r.dotAll&&e.global===r.global&&e.ignoreCase===r.ignoreCase&&e.multiline===r.multiline&&e.sticky===r.sticky&&e.unicode===r.unicode}case"CapturingGroup":case"Group":case"Pattern":{const r=t;return J(e.alternatives,r.alternatives)}case"Quantifier":{const r=t;return e.min===r.min&&e.max===r.max&&e.greedy===r.greedy&&F(e.element,r.element)}case"RegExpLiteral":{const r=t;return F(e.flags,r.flags)&&F(e.pattern,r.pattern)}default:throw r(e)}}function J(e,t){if(e.length!==t.length)return!1;for(let r=0;r<e.length;r++)if(!F(e[r],t[r]))return!1;return!0}function P(e,t,n,a,s){function c(e,t,r){var n,s;a.enter&&(t=a.enter(e,t,r));if(null===(s=null===(n=a.continueInto)||void 0===n?void 0:n.call(a,e,t,r))||void 0===s||s)switch(e.type){case"Assertion":if("lookahead"===e.kind||"lookbehind"===e.kind){const n=g(e.kind),s=a.join(e.alternatives.map((e=>o(e,Q(a,t,r),n))),n);a.endPath&&(t=a.endPath(t,n,"assertion")),a.assert&&(t=a.assert(t,r,s,n))}break;case"Group":case"CapturingGroup":t=a.join(e.alternatives.map((e=>o(e,Q(a,t,r),r))),r);break;case"Quantifier":0===e.max||(t=0===e.min?a.join([t,c(e.element,Q(a,t,r),r)],r):c(e.element,t,r))}return a.leave&&(t=a.leave(e,t,r)),t}function o(e,t,r){var n,s;let o="ltr"===r?0:e.elements.length-1;const i="ltr"===r?1:-1;let u;for(;u=e.elements[o];o+=i){t=c(u,t,r);if(!(null===(s=null===(n=a.continueAfter)||void 0===n?void 0:n.call(a,u,t,r))||void 0===s||s))break}return t}return s||(s=d(e)),"enter"===t&&(n=c(e,n,s)),function(e,t,n){function s(e){var c,o;const i=e.parent;if("CharacterClass"===i.type||"CharacterClassRange"===i.type)throw new Error("The given element cannot be part of a character class.");if(!(null===(o=null===(c=a.continueAfter)||void 0===c?void 0:c.call(a,e,t,n))||void 0===o||o))return!1;if("Quantifier"===i.type)return i.max<=1?s(i):[i,s(i)];{const t=i.elements.indexOf(e)+("ltr"===n?1:-1),a=i.elements[t];if(a)return a;{const e=i.parent;if("Pattern"===e.type)return"pattern";if("Assertion"===e.type)return"assertion";if("CapturingGroup"===e.type||"Group"===e.type)return s(e);throw r(e)}}}for(;;){let r=s(e);for(;Array.isArray(r);){const[e,s]=r;t=a.join([t,c(e,Q(a,t,n),n)],n),r=s}if(!1===r)return t;if("assertion"===r||"pattern"===r)return a.endPath&&(t=a.endPath(t,n,r)),t;t=c(r,t,n),e=r}}(e,n,s)}function Q(e,t,r){return e.fork?e.fork(t,r):t}function R(e,t,r){return Array.isArray(e)?B(e,t,r):M(e,t,r)}function B(e,t,r){return T(e.map((e=>M(e,t,r))),r)}function M(e,t,n){switch(e.type){case"Assertion":switch(e.kind){case"word":return a();case"end":case"start":return g(e.kind)===t?n.multiline?s({char:exports.Chars.lineTerminator(n),edge:!0,exact:!0}):s(function(e){return{char:exports.Chars.empty(e),edge:!0,exact:!0}}(n)):a();case"lookahead":case"lookbehind":if(g(e.kind)===t){if(e.negate){if(h(e,(t=>t!==e&&"Assertion"===t.type)))return a();const r=B(e.alternatives,t,n),c=k(e.alternatives);return r.empty||!c?{char:exports.Chars.empty(n),empty:!1,exact:!0}:r.exact&&1===c.max?s({char:r.char.negate(),edge:!0,exact:!0}):a()}return s(W(B(e.alternatives,t,n)))}return a();default:throw r(e)}case"Character":case"CharacterSet":case"CharacterClass":return{char:E(e,n),empty:!1,exact:!0};case"Quantifier":{if(0===e.max)return s();const r=M(e.element,t,n);return 0===e.min?T([s(),r],n):r}case"Alternative":{let r=e.elements;return"rtl"===t&&(r=[...r],r.reverse()),D(function*(){for(const e of r)yield M(e,t,n)}(),n)}case"CapturingGroup":case"Group":return B(e.alternatives,t,n);case"Backreference":{if(x(e))return s();const r=M(e.resolved,t,n);return r.exact=r.exact&&r.char.size<=1,C(e)?r:T([r,s()],n)}default:throw r(e)}function a(){return s({char:exports.Chars.all(n),edge:!0,exact:!1})}function s(e){return L(n,e)}}function j(e){return{char:exports.Chars.all(e),edge:!0,exact:!0}}function L(e,t){return{char:exports.Chars.empty(e),empty:!0,exact:!0,look:null!=t?t:j(e)}}exports.Chars=void 0,function(e){const r=t.CharSet.empty(65535),n=t.CharSet.empty(1114111);e.empty=function(e){return e.unicode?n:r};const a=t.CharSet.all(65535),s=t.CharSet.all(1114111);e.all=function(e){return e.unicode?s:a};const c=t.JS.createCharSet([{kind:"any"}],{unicode:!1}).negate(),o=t.JS.createCharSet([{kind:"any"}],{unicode:!0}).negate();e.lineTerminator=function(e){return e.unicode?o:c};const i=t.JS.createCharSet([{kind:"word",negate:!1}],{unicode:!1}),u=t.JS.createCharSet([{kind:"word",negate:!1}],{unicode:!0,ignoreCase:!1}),l=t.JS.createCharSet([{kind:"word",negate:!1}],{unicode:!0,ignoreCase:!0});e.word=function(e){return e.unicode?e.ignoreCase?l:u:i};const p=t.JS.createCharSet([{kind:"digit",negate:!1}],{unicode:!1}),h=t.JS.createCharSet([{kind:"digit",negate:!1}],{unicode:!0});e.digit=function(e){return e.unicode?h:p};const f=t.JS.createCharSet([{kind:"space",negate:!1}],{unicode:!1}),m=t.JS.createCharSet([{kind:"space",negate:!1}],{unicode:!0});e.space=function(e){return e.unicode?m:f}}(exports.Chars||(exports.Chars={}));class O{constructor(e){this.char=e,this.exact=!0}add(e,t){!this.exact||t||this.char.isSupersetOf(e)?!this.exact&&t&&e.isSupersetOf(this.char)&&(this.exact=!0):this.exact=!1,this.char=this.char.union(e)}static emptyFromFlags(e){return new O(exports.Chars.empty(e))}static emptyFromMaximum(e){return new O(t.CharSet.empty(e))}}function T(e,t){const r=O.emptyFromFlags(t),n=[];for(const t of e)r.add(t.char,t.exact),t.empty&&n.push(t.look);if(n.length>0){const e=O.emptyFromFlags(t);let a=!1;for(const t of n)e.add(t.char,t.exact),a=a||t.edge;return{char:r.char,exact:r.exact,empty:!0,look:{char:e.char,exact:e.exact,edge:a}}}return{char:r.char,exact:r.exact,empty:!1}}function D(e,t){const r=O.emptyFromFlags(t);let n=j(t);for(const t of e){if(r.add(t.char.intersect(n.char),n.exact&&t.exact),!t.empty)return{char:r.char,exact:r.exact,empty:!1};{const e=n.char.intersect(t.look.char);n={char:e,exact:n.exact&&t.look.exact||e.isEmpty,edge:n.edge&&t.look.edge}}}return{char:r.char,exact:r.exact,empty:!0,look:n}}function W(e){if(e.empty){const t=O.emptyFromMaximum(e.char.maximum);return t.add(e.char,e.exact),t.add(e.look.char,e.look.exact),{char:t.char,exact:t.exact,edge:e.look.edge}}return{char:e.char,exact:e.exact,edge:!1}}function q(e,t,r){return P(e,"next",L(r),{join:e=>T(e,r),enter:(e,t,n)=>D([t,R(e,n,r)],r),continueInto:()=>!1,continueAfter:(e,t)=>t.empty},t)}function I(e,t,r){return P(e,"next",{char:L(r),contributors:[]},{join(e){const t=new Set;return e.forEach((e=>e.contributors.forEach((e=>t.add(e))))),{char:T(e.map((e=>e.char)),r),contributors:[...t]}},enter(e,t,n){const a=R(e,n,r);return{char:D([t.char,a],r),contributors:[...t.contributors,e]}},continueInto:()=>!1,continueAfter:(e,t)=>t.char.empty},t)}exports.followPaths=P,exports.getCapturingGroupNumber=function(t){let r=0;try{throw e.visitRegExpAST(m(t),{onCapturingGroupEnter(e){if(r++,e===t)throw new Error}}),new Error("Unable to find the given capturing group in its parent pattern.")}catch(e){return r}},exports.getClosestAncestor=S,exports.getEffectiveMaximumRepetition=function(e){let t=1;for(let r=e.parent;r;r=r.parent)if("Quantifier"===r.type){if(t*=r.max,0===t)return 0}else if("Assertion"===r.type)break;return t},exports.getFirstCharAfter=function(e,t,r){return W(q(e,t,r))},exports.getFirstCharAfterWithContributors=function(e,t,r){const{char:n,contributors:a}=I(e,t,r);return{char:W(n),contributors:a}},exports.getFirstConsumedChar=R,exports.getFirstConsumedCharAfter=q,exports.getFirstConsumedCharAfterWithContributors=I,exports.getLengthRange=k,exports.getMatchingDirection=d,exports.getMatchingDirectionFromAssertionKind=g,exports.getPattern=m,exports.hasSomeAncestor=p,exports.hasSomeDescendant=h,exports.invertMatchingDirection=function(e){return"ltr"===e?"rtl":"ltr"},exports.isEmpty=function(e){return n(e,i)},exports.isEmptyBackreference=x,exports.isPotentiallyEmpty=function(e){return a(e,u)},exports.isPotentiallyZeroLength=function(e){return a(e,(e=>o(e,e)))},exports.isStrictBackreference=C,exports.isZeroLength=s,exports.matchesAllCharacters=function(e,r){return"Character"!==e.type&&("CharacterClassRange"===e.type?0===e.min.value&&e.max.value===(r.unicode?1114111:65535):"CharacterSet"===e.type?"property"===e.kind?t.JS.createCharSet([e],r).isAll:"any"===e.kind&&!!r.dotAll:!(!e.negate||0!==e.elements.length)||(e.negate?E(e.elements,r).isEmpty:E(e.elements,r).isAll))},exports.matchesNoCharacters=function(e,r){return"Character"!==e.type&&"CharacterClassRange"!==e.type&&("CharacterSet"===e.type?"property"===e.kind&&t.JS.createCharSet([e],r).isEmpty:!e.negate&&0===e.elements.length||(e.negate?E(e.elements,r).isAll:E(e.elements,r).isEmpty))},exports.structurallyEqual=F,exports.toCharSet=E;

package.json

 {
   "name": "regexp-ast-analysis",
-  "version": "0.1.2",
+  "version": "0.1.3",
   "description": "A library for analysing JS RegExp",
@@ -5,0 +5,0 @@ "main": "index",

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

51703

increased by2.78%

Lines of code

825

increased by1.6%

No dependency changes