fauton - npm Package Compare versions

Comparing version 0.0.7 to 0.0.8

dist/libs/DeterministicFiniteAutomaton/utils/minimize.js

@@ -15,3 +15,2 @@ "use strict";
     });
-    const finalStateString = automaton.final_states.join('');
     let currentEquivalentStatesGroups = [nonFinalStates, automaton.final_states];
@@ -41,2 +40,3 @@ let previousEquivalentStatesGroups = [];
     });
+    const newStates = currentEquivalentStatesGroups.map((currentEquivalentStatesGroup) => currentEquivalentStatesGroup.join(''));
     return {
@@ -46,5 +46,8 @@ label: minimizedDfaOptions?.label ?? automaton.label,
         description: minimizedDfaOptions?.description ?? automaton.description,
-        final_states: [finalStateString],
+        final_states: newStates.filter((newState) => {
+            const newStateStrings = new Set(newState);
+            return automaton.final_states.find((finalState) => newStateStrings.has(finalState));
+        }),
         start_state: newStartState.join(''),
-        states: currentEquivalentStatesGroups.map((currentEquivalentStatesGroup) => currentEquivalentStatesGroup.join('')),
+        states: newStates,
         transitions: newTransitions,
@@ -51,0 +54,0 @@ epsilon_transitions: null,

dist/libs/FiniteAutomataTest/index.d.ts

@@ -5,7 +5,13 @@ /// <reference types="node" />
 import { FiniteAutomaton } from '../FiniteAutomaton';
+import { RegularExpression } from '../RegularExpression';
 import * as FiniteAutomataTestUtils from './utils';
-export interface IAutomataTestConfig {
+export declare type IAutomataTestConfig = {
     automaton: FiniteAutomaton;
+    regex?: RegularExpression;
     options: InputStringOption;
-}
+} | {
+    automaton?: FiniteAutomaton;
+    regex: RegularExpression;
+    options: InputStringOption;
+};
 declare type IWriteStreams = Record<`${keyof IOutputFiles}WriteStream`, null | fs.WriteStream>;
@@ -27,5 +33,5 @@ export declare class FiniteAutomataTest {
     };
-    testAutomata(finiteAutomaton: FiniteAutomaton, finiteAutomatonTestInfo: FiniteAutomatonTestInfo, writeStreams: IWriteStreams, inputStrings: string[]): void;
+    testAutomata(finiteAutomaton: FiniteAutomaton | RegularExpression, finiteAutomatonTestInfo: FiniteAutomatonTestInfo, writeStreams: IWriteStreams, inputStrings: string[]): void;
     test(configs: {
-        automaton: FiniteAutomaton;
+        automaton: FiniteAutomaton | RegularExpression;
         options: InputStringOption;
@@ -32,0 +38,0 @@ }[]): Promise<void>;

dist/libs/FiniteAutomataTest/utils/test.d.ts

 import { InputStringOption } from '../../../types';
 import { FiniteAutomaton } from '../../FiniteAutomaton';
+import { RegularExpression } from '../../RegularExpression';
 export declare function test(logsPath: string, configs: {
-    automaton: FiniteAutomaton;
+    automaton: FiniteAutomaton | RegularExpression;
     options: InputStringOption;
 }[], preAutomatonTestCb: (totalInputStrings: number) => void, postAutomatonTestCb: () => void): Promise<void>;

dist/libs/FiniteAutomataTest/utils/test.js

@@ -51,3 +51,3 @@ "use strict";
                 else {
-                    generatedStrings = GenerateString_1.GenerateString.generateAllCombosWithinLength(automaton.automaton.alphabets, options.combo.maxLength);
+                    generatedStrings = GenerateString_1.GenerateString.generateAllCombosWithinLength(automaton.automaton.alphabets, options.combo.maxLength, options.combo.startLength ?? 1);
                 }
@@ -54,0 +54,0 @@ }

dist/libs/FiniteAutomataTest/utils/testAutomaton.d.ts

@@ -5,4 +5,5 @@ /// <reference types="node" />
 import { FiniteAutomaton } from '../../FiniteAutomaton';
+import { RegularExpression } from '../../RegularExpression';
 declare type IWriteStreams = Record<`${keyof IOutputFiles}WriteStream`, null | fs.WriteStream>;
-export declare function testAutomaton(finiteAutomaton: FiniteAutomaton, finiteAutomatonTestInfo: FiniteAutomatonTestInfo, writeStreams: IWriteStreams, inputStrings: string[], postAutomatonTestCb?: () => void): void;
+export declare function testAutomaton(finiteAutomaton: FiniteAutomaton | RegularExpression, finiteAutomatonTestInfo: FiniteAutomatonTestInfo, writeStreams: IWriteStreams, inputStrings: string[], postAutomatonTestCb?: () => void): void;
 export {};

dist/libs/FiniteAutomataTest/utils/testAutomaton.js

@@ -10,3 +10,3 @@ "use strict";
         if (inputString.length !== 0) {
-            const { automatonTestResult } = finiteAutomaton.generateGraphFromString(inputString);
+            const automatonTestResult = finiteAutomaton.test(inputString);
             const logicTestResult = finiteAutomaton.testLogic(inputString, automatonTestResult);
@@ -13,0 +13,0 @@ const isWrong = automatonTestResult !== logicTestResult;

dist/libs/FiniteAutomaton/index.d.ts

@@ -15,3 +15,4 @@ import { IAutomatonTestLogicFn, InputFiniteAutomaton, TFiniteAutomatonType, TransformedFiniteAutomaton } from '../../types';
     };
+    test(inputString: string): boolean;
 }
 export { FiniteAutomatonUtils };

dist/libs/FiniteAutomaton/index.js

@@ -49,3 +49,6 @@ "use strict";
     }
+    test(inputString) {
+        return this.generateGraphFromString(inputString).automatonTestResult;
+    }
 }
 exports.FiniteAutomaton = FiniteAutomaton;

dist/libs/GenerateString.d.ts

 export declare class GenerateString {
-    static generateAllCombosWithinLength(alphabet: string[], maxLength: number, cb?: (generatedString: string) => void): string[];
+    static generateAllCombosWithinLength(alphabet: string[], maxLength: number, startLength: number, cb?: (generatedString: string) => void): string[];
     static generateRandomUnique(total: number, alphabet: string[], minLength: number, maxLength: number, initialInputStrings?: string[]): string[];
 }

dist/libs/GenerateString.js

@@ -6,3 +6,3 @@ "use strict";
 class GenerateString {
-    static generateAllCombosWithinLength(alphabet, maxLength, cb) {
+    static generateAllCombosWithinLength(alphabet, maxLength, startLength, cb) {
         const generatedStrings = new Set();
@@ -20,3 +20,3 @@ function generateAllKLength(generatedString, stringLength) {
         }
-        for (let length = 1; length <= maxLength; length += 1) {
+        for (let length = startLength; length <= maxLength; length += 1) {
             generateAllKLength('', length);
@@ -23,0 +23,0 @@ }

dist/libs/index.d.ts

@@ -7,2 +7,3 @@ import { GenerateString } from './GenerateString';
 export * from './NonDeterministicFiniteAutomaton';
+export * from './RegularExpression';
 export { Render, GenerateString };

dist/libs/index.js

@@ -22,1 +22,2 @@ "use strict";
 __exportStar(require("./NonDeterministicFiniteAutomaton"), exports);
+__exportStar(require("./RegularExpression"), exports);

dist/libs/NonDeterministicFiniteAutomaton/utils/convertToRegularNfa.js

@@ -5,40 +5,22 @@ "use strict";
 const epsilonClosureOfState_1 = require("./epsilonClosureOfState");
+const moveAndEpsilonClosureStateSet_1 = require("./moveAndEpsilonClosureStateSet");
 function convertToRegularNfa(automaton) {
     const { transitions, states, alphabets, epsilon_transitions: epsilonTransitions } = automaton;
     const epsilonClosureOfStateCache = {};
-    alphabets.forEach((alphabet) => {
+    alphabets.forEach((symbol) => {
         states.forEach((state) => {
             if (epsilonTransitions && epsilonTransitions[state]) {
-                const firstPhaseStates = !epsilonClosureOfStateCache[state]
+                const epsilonClosuredStates = !epsilonClosureOfStateCache[state]
                     ? (0, epsilonClosureOfState_1.epsilonClosureOfState)(automaton.epsilon_transitions, state)
                     : epsilonClosureOfStateCache[state];
                 if (!epsilonClosureOfStateCache[state]) {
-                    epsilonClosureOfStateCache[state] = firstPhaseStates;
+                    epsilonClosureOfStateCache[state] = epsilonClosuredStates;
                 }
-                const secondPhaseStates = new Set();
-                const thirdPhaseSet = new Set();
-                firstPhaseStates.forEach((firstPhaseState) => {
-                    if (transitions[firstPhaseState]) {
-                        transitions[firstPhaseState][alphabet]?.forEach((transitionRecordState) => {
-                            secondPhaseStates.add(transitionRecordState);
-                        });
-                    }
-                });
-                secondPhaseStates.forEach((secondPhaseState) => {
-                    const epsilonClosuredStates = !epsilonClosureOfStateCache[secondPhaseState]
-                        ? (0, epsilonClosureOfState_1.epsilonClosureOfState)(automaton.epsilon_transitions, secondPhaseState)
-                        : epsilonClosureOfStateCache[secondPhaseState];
-                    if (!epsilonClosureOfStateCache[secondPhaseState]) {
-                        epsilonClosureOfStateCache[secondPhaseState] = epsilonClosuredStates;
-                    }
-                    epsilonClosuredStates.forEach((closuredState) => {
-                        thirdPhaseSet.add(closuredState);
-                    });
-                });
+                const epsilonClosuredStatesForSymbol = (0, moveAndEpsilonClosureStateSet_1.moveAndEpsilonClosureStateSet)(transitions, epsilonTransitions, Array.from(epsilonClosuredStates), symbol);
                 if (transitions[state]) {
-                    transitions[state][alphabet] = Array.from(thirdPhaseSet);
+                    transitions[state][symbol] = epsilonClosuredStatesForSymbol;
                 }
                 else {
                     transitions[state] = {
-                        [alphabet]: Array.from(thirdPhaseSet),
+                        [symbol]: epsilonClosuredStatesForSymbol,
                     };
@@ -45,0 +27,0 @@ }

dist/types.d.ts

@@ -66,2 +66,3 @@ export interface InputFiniteAutomaton {
         maxLength: number;
+        startLength?: number;
     };
@@ -83,1 +84,7 @@ random?: undefined | null;
 export declare type TMergeOperation = 'or' | 'and' | 'not';
+export interface IRegularExpression {
+    alphabets: string[];
+    regex: RegExp;
+    label: string;
+    description?: string;
+}

dist/utils/countFileLines.js

@@ -13,8 +13,5 @@ "use strict";
             .on('data', (buffer) => {
-            let idx = -1;
-            lineCount = -1;
-            do {
-                idx = buffer.indexOf(10, idx + 1);
-                lineCount += 1;
-            } while (idx !== -1);
+            for (let i = 0; i < buffer.length; i += 1)
+                if (buffer[i] === 10)
+                    lineCount += 1;
         })
@@ -21,0 +18,0 @@ .on('end', () => {

package.json

 {
   "name": "fauton",
-  "version": "0.0.7",
+  "version": "0.0.8",
   "description": "A library to test any finite automaton with arbitrary alphabets",
@@ -79,2 +79,2 @@ "main": "dist/index.js",
   }
-}
+}

readme.md

@@ -13,3 +13,3 @@ <div align="center"> <h1>Fauton</h1> </div>
   <img src="https://img.shields.io/github/commit-activity/m/devorein/fauton?color=yellow" />
-  <img src="https://img.shields.io/github/repo-size/devorein/fauton?style=flat-square&color=orange"/>
+  <img src="https://img.shields.io/github/repo-size/devorein/fauton?style=flat-square&color=ocombo"/>
   <img src="https://img.shields.io/github/contributors/devorein/fauton?label=contributors&color=red"/>
@@ -31,2 +31,4 @@ <img src="https://img.shields.io/librariesio/release/npm/fauton"/>
   - [Dfa minimization](#dfa-minimization)
+  - [Dfa equivalency by testing](#dfa-equivalency-by-testing)
+  - [Testing regular expressions](#testing-regular-expressions)
 - [Conditions for DFA](#conditions-for-dfa)
@@ -56,2 +58,4 @@ - [Transitions Record Transformation](#transitions-record-transformation)
 - [Contributors](#contributors)
+- [Algorithm Sources](#algorithm-sources)
+- [Credits](#credits)
 
@@ -62,3 +66,3 @@ **Please note that I won't be following semver at the initial stages, as there could be a lot of (breaking) changes between each release which will all be patch**
 
-1. Test any dfa/nfa/ε-nfa
+1. Test any valid dfa/nfa/ε-nfa/regex
 2. Supports arbitrary alphabets
@@ -133,3 +137,3 @@ 3. Easy to use api to generate input strings
 			type: 'generate',
-			range: {
+			combo: {
 				maxLength: 10,
@@ -202,3 +206,3 @@ },
 			type: 'generate',
-			range: {
+			combo: {
 				maxLength: 10,
@@ -264,3 +268,3 @@ },
 			type: 'generate',
-			range: {
+			combo: {
 				maxLength: 10,
@@ -580,2 +584,91 @@ },
 
+## Dfa equivalency by testing
+
+Testing if two dfa are equal through testing. One of the dfa is the minimized version of the other dfa, all the input string should return similar test result for both of them.
+
+```js
+import { DeterministicFiniteAutomaton, FiniteAutomataTest, FiniteAutomatonUtils } from 'fauton';
+import path from 'path';
+
+const dfa = new DeterministicFiniteAutomaton(() => true, {
+	states: [0, 1, 2, 3, 4, 5, 6, 7],
+	alphabets: ['0', '1'],
+	final_states: [2],
+	start_state: 0,
+	label: 'dfa',
+	transitions: {
+		0: [1, 5],
+		1: [6, 2],
+		2: [0, 2],
+		3: [2, 6],
+		4: [7, 5],
+		5: [2, 6],
+		6: [6, 4],
+		7: [6, 2],
+	},
+});
+
+const minimized_dfa = dfa.minimize();
+
+minimized_dfa.testLogic = (inputString) => {
+	return FiniteAutomatonUtils.generateGraphFromString(dfa.automaton, inputString)
+		.automatonTestResult;
+};
+
+const finiteAutomataTest = new FiniteAutomataTest(path.join(__dirname, 'logs'));
+
+finiteAutomataTest.test([
+	{
+		automaton: minimized_dfa,
+		options: {
+			type: 'generate',
+			combo: {
+				maxLength: 10,
+			},
+		},
+	},
+]);
+```
+
+## Testing regular expressions
+
+Rather than testing only a finite automaton, you can also test your regular expressions against generated strings
+
+```js
+import { FiniteAutomataTest, RegularExpression } from 'fauton';
+import path from 'path';
+
+const regex = new RegularExpression(
+	(inputString) => {
+		return (
+			inputString[0] === 'a' &&
+			inputString[1] === 'b' &&
+			inputString
+				.slice(2)
+				.split('')
+				.every((char) => char === 'c')
+		);
+	},
+	{
+		alphabets: ['a', 'b', 'c'],
+		label: 'Starts with a and b, ends with any number of c',
+		regex: /^abc*$/g,
+	}
+);
+
+const finiteAutomataTest = new FiniteAutomataTest(path.join(__dirname, 'logs'));
+
+finiteAutomataTest.test([
+	{
+		automaton: regex,
+		options: {
+			type: 'generate',
+			combo: {
+				maxLength: 10,
+			},
+		},
+	},
+]);
+```
+
 Take a look at [examples](./examples) folder for more examples.
@@ -762,3 +855,3 @@
 			type: 'generate',
-			range: {
+			combo: {
 				maxLength: 3,
@@ -828,3 +921,3 @@ },
 
-Contains all the input strings. Useful when you are generating random or ranged strings and want to reuse it for later
+Contains all the input strings. Useful when you are generating random or combo strings and want to reuse it for later
 
@@ -884,2 +977,17 @@ Same as `<fa.label>.accepted.txt`
 
+# Algorithm Sources
+
+Wikipedia sources for all the algorithms used in the package
+
+1. [Thompson-McNaughton-Yamada](https://en.wikipedia.org/wiki/Thompson%27s_construction) algorithm for converting regex to e-nfa
+2. [Hopcroft](https://en.wikipedia.org/wiki/DFA_minimization#Hopcroft's_algorithm) algorithm for dfa-minimization
+3. [Rabin–Scott powerset construction](https://en.wikipedia.org/wiki/Powerset_construction) algorithm to convert nfa to dfa
+4. [Shunting-Yard](https://en.wikipedia.org/wiki/Shunting-yard_algorithm) algorithm to convert regex string from infix to postfix
+
+# Credits
+
+Big thanks to all these wonderful repos.
+
+1. [Orban](https://github.com/wevial/orban) Regular expression engine that uses the Thompson-McNaughton-Yamada algorithm implemented in Python.
+
 Feel free to submit a pull request or open a new issue, contributions are more than welcome !!!

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

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

117848

increased by8.85%

Number of package files

79

increased by8.22%

Lines of code

1739

increased by10.34%

Number of lines in readme file

983

increased by12.34%

Number of medium supply chain risk alerts

0

decreased by-100%

No dependency changes