functionalscript - npm Package Compare versions

Comparing version 0.4.0 to 0.4.1

bnf/djs/test.f.js

@@ -1,2 +0,2 @@
-import { cp, range, remove, str } from "../func/module.f.js";
+import { cp, range, remove, set, str } from "../func/module.f.js";
 import { parser, toRuleMap } from "./module.f.js";
@@ -117,10 +117,20 @@ import { classic } from "../func/testlib.f.js";
 };
+const repeat0Name = (v) => `${v}Repeat0`;
+const repeat0Body = (v) => [
+    [],
+    [v, repeat0Name(v)]
+];
+const repeat0 = (v) => {
+    const name = repeat0Name(v);
+    const body = repeat0Body(v);
+    return { [name]: body };
+};
 const deterministic = () => {
     const map = {
         json: [
-            ['ws', 'element']
+            ['wsRepeat0', 'element']
         ],
         value: [
-            [cp('{'), 'ws', 'object', cp('}')],
-            [cp('['), 'ws', 'array', cp(']')],
+            [cp('{'), 'wsRepeat0', 'object', cp('}')],
+            [cp('['), 'wsRepeat0', 'array', cp(']')],
             ['string'],
@@ -134,10 +144,10 @@ ['number'],
             [],
-            ['member', 'members'],
+            ['member', 'memberTailRepeat0'],
         ],
-        members: [
-            [],
-            [cp(','), 'ws', 'member', 'members'],
+        memberTail: [
+            [cp(','), 'wsRepeat0', 'member']
         ],
+        ...repeat0('memberTail'),
         member: [
-            ['string', 'ws', cp(':'), 'ws', 'element'],
+            ['string', 'wsRepeat0', cp(':'), 'wsRepeat0', 'element'],
         ],
@@ -150,14 +160,11 @@ array: [
             [],
-            [cp(','), 'ws', 'element', 'elements'],
+            [cp(','), 'wsRepeat0', 'element', 'elements'],
         ],
         element: [
-            ['value', 'ws'],
+            ['value', 'wsRepeat0'],
         ],
         string: [
-            [cp('"'), 'characters', cp('"')],
+            [cp('"'), 'characterRepeat0', cp('"')],
         ],
-        characters: [
-            [],
-            ['character', 'characters'],
-        ],
+        ...repeat0('character'),
         character: [
@@ -168,10 +175,3 @@ ...remove([0x20, 0x10FFFF], [cp('"'), cp('\\')]),
         escape: [
-            [cp('"')],
-            [cp('\\')],
-            [cp('/')],
-            [cp('b')],
-            [cp('f')],
-            [cp('n')],
-            [cp('r')],
-            [cp('t')],
+            ...set('"\\/bfnrt'),
             [cp('u'), 'hex', 'hex', 'hex', 'hex'],
@@ -184,14 +184,14 @@ ],
         ],
+        numberSign: [
+            [],
+            [cp('-')]
+        ],
         number: [
-            ['integer', 'fraction', 'exponent'],
-            [cp('-'), 'integer', 'fraction', 'exponent'],
+            ['numberSign', 'integer', 'fraction', 'exponent'],
         ],
         integer: [
             [cp('0')],
-            ['onenine', 'digits'],
+            ['onenine', 'digitRepeat0'],
         ],
-        digits: [
-            [],
-            ['digit', 'digits'],
-        ],
+        ...repeat0('digit'),
         digit: [
@@ -206,8 +206,8 @@ [cp('0')],
             [],
-            [cp('.'), 'digit', 'digits'],
+            [cp('.'), 'digit', 'digitRepeat0'],
         ],
+        e: set('Ee'),
         exponent: [
             [],
-            [cp('E'), 'sign', 'digit', 'digits'],
-            [cp('e'), 'sign', 'digit', 'digits'],
+            ['e', 'sign', 'digit', 'digitRepeat0'],
         ],
@@ -219,9 +219,4 @@ sign: [
         ],
-        ws: [
-            [],
-            [cp(' '), 'ws'],
-            [cp('\n'), 'ws'],
-            [cp('\r'), 'ws'],
-            [cp('\t'), 'ws'],
-        ],
+        ws: set(' \n\r\t'),
+        ...repeat0('ws'),
     };
@@ -228,0 +223,0 @@ const _map = map;

bnf/func/module.f.d.ts

 /**
- *  Types for defining language grammar using Backus-Naur Form (BNF).
+ * Types for defining language grammar using Backus-Naur Form (BNF).
  *
- * @module
- *
- * @description
- *
  * Utilities for serializing and deserializing BNF grammar
@@ -13,2 +9,4 @@ * and creating a simple LL(1) parser.
  *
+ * @module
+ *
  * @example
@@ -129,2 +127,9 @@ *
 /**
+ * Convert a sequence of character into `OrRangeSet`
+ *
+ * @param s a set of code points
+ * @returns A set compatible with `Or`
+ */
+export declare const set: (s: string) => OrRangeSet;
+/**
  * Removes a terminal range from a set of ranges.
@@ -143,2 +148,4 @@ *
 export declare const remove: (range: TerminalRange, removeSet: RangeSet) => OrRangeSet;
+export declare const repeat0: (rule: Rule) => Rule;
+export declare const join0: (rule: Rule, separator: Rule) => Rule;
 export {};

bnf/func/module.f.js

 /**
- *  Types for defining language grammar using Backus-Naur Form (BNF).
+ * Types for defining language grammar using Backus-Naur Form (BNF).
  *
- * @module
- *
- * @description
- *
  * Utilities for serializing and deserializing BNF grammar
@@ -13,2 +9,4 @@ * and creating a simple LL(1) parser.
  *
+ * @module
+ *
  * @example
@@ -77,2 +75,10 @@ *
 };
+const toOr = (r) => r.map(v => [v]);
+/**
+ * Convert a sequence of character into `OrRangeSet`
+ *
+ * @param s a set of code points
+ * @returns A set compatible with `Or`
+ */
+export const set = (s) => toOr(str(s));
 const removeOne = (set, [a, b]) => {
@@ -112,3 +118,18 @@ let result = [];
     }
-    return result.map(v => [v]);
+    return toOr(result);
 };
+export const repeat0 = (rule) => {
+    const result = () => [
+        [],
+        [rule, result],
+    ];
+    return result;
+};
+export const join0 = (rule, separator) => {
+    const tail = repeat0(() => [[separator, rule]]);
+    const result = () => [
+        [],
+        [rule, tail],
+    ];
+    return result;
+};

bnf/func/test.f.js

 import { stringify } from "../../json/module.f.js";
 import { sort } from "../../types/object/module.f.js";
-import { cp, str, range, remove, } from "./module.f.js";
+import { cp, str, range, remove, set, repeat0, join0, } from "./module.f.js";
 const deterministic = () => {
+    const wsSet = () => set('\t\n\r '); // 9,10,13,32
     // {"empty":true,"map":[[false,8],[true,10],[false,12],[true,13],[false,31],[true,32]]}
-    const ws = () => [
-        [],
-        [cp('\t'), ws], // 9
-        [cp('\n'), ws], // 10
-        [cp('\r'), ws], // 13
-        [cp(' '), ws], // 32
-    ];
+    const ws = repeat0(wsSet);
     // {"empty":true,"map":[[false,42],[true,43],[false,44],[true,45]]}
     const sign = () => [
         [],
-        str('+'), // 43
-        str('-'), // 45
+        ...set('+-'), // 43
     ];
@@ -29,15 +23,12 @@ // {"empty":false,"map":[[false,48],[true,57]]}
     // {"empty":true,"map":[[false,47],[true,57]]}
+    const digits0 = repeat0(digit);
+    // {"empty":false,"map":[[false,47],[true,57]]}
     const digits1 = () => [
-        [],
-        [digit, digits1]
+        [digit, digits0]
     ];
-    // {"empty":false,"map":[[false,47],[true,57]]}
-    const digits = () => [
-        [digit, digits1]
-    ];
+    const e = () => set('Ee'); // 69, 101
     // {"empty":true,"map":[[false,68],[true,69],[false,100],[true,101]]}
     const exponent = () => [
         [],
-        [cp('E'), sign, digits], // 69
-        [cp('e'), sign, digits], // 101
+        [e, sign, digits1], // 69 | 101
     ];
@@ -47,13 +38,13 @@ // {"empty":true,"map":[[false,45],[true,46]]}
         [],
-        [cp('.'), digits] // 46
+        [cp('.'), digits1] // 46
     ];
     // {"empty":false,"map":[[false,47],[true,57]]}
-    const integer1 = () => [
+    const unsignedInteger = () => [
         str('0'), // 48
-        [onenine, digits1], // 49-57
+        [onenine, digits0], // 49-57
     ];
     // {"empty":false,"map":[[false,44],[true,45],[false,47],[true,57]]}
     const integer = () => [
-        [integer1], // 48-57
-        [cp('-'), integer1], // 45
+        [unsignedInteger], // 48-57
+        [cp('-'), unsignedInteger], // 45
     ];
@@ -72,10 +63,3 @@ // {"empty":false,"map":[[false,44],[true,45],[false,47],[true,57]]}
     const escape = () => [
-        str('"'), //  34
-        str('/'), //  47
-        str('\\'), //  92
-        str('b'), //  98
-        str('f'), // 102
-        str('n'), // 110
-        str('r'), // 114
-        str('t'), // 116
+        ...set('"\\/bfnrt'),
         [cp('u'), hex, hex, hex, hex] // 117
@@ -89,6 +73,3 @@ ];
     // {"empty":true,"map":[[false,31],[true,33],[false,34],[true,1114111]]}
-    const characters = () => [
-        [],
-        [character, characters]
-    ];
+    const characters = repeat0(character);
     // {"empty":false,"map":[[false,33],[true,34]]}
@@ -98,58 +79,18 @@ const string = () => [
     ];
+    const comma = () => [[cp(','), ws]];
     // {"empty":false,"map":[[false,33],[true,34],[false,44],[true,45],[false,47],[true,57],[false,90],[true,91],[false,101],[true,102],[false,109],[true,110],[false,115],[true,116],[false,122],[true,123]]}
-    const element1 = () => [
+    const element = () => [
         [value, ws]
     ];
-    // {"empty":false,"map":[[false,8],[true,10],[false,12],[true,13],[false,31],[true,32],[false,33],[true,34],[false,44],[true,45],[false,47],[true,57],[false,90],[true,91],[false,101],[true,102],[false,109],[true,110],[false,115],[true,116],[false,122],[true,123]]}
-    const element = () => [
-        [ws, element1]
+    const list = (open, rule, close) => () => [
+        [cp(open), ws, join0(rule, comma), cp(close)]
     ];
-    // {"empty":true,"map":[[false,43],[true,44]]}
-    const elements2 = () => [
-        [],
-        [cp(','), elements] // 44
-    ];
-    // {"empty":false,"map":[[false,33],[true,34],[false,44],[true,45],[false,47],[true,57],[false,90],[true,91],[false,101],[true,102],[false,109],[true,110],[false,115],[true,116],[false,122],[true,123]]}
-    const elements1 = () => [
-        [element1, elements2]
-    ];
-    // {"empty":false,"map":[[false,8],[true,10],[false,12],[true,13],[false,31],[true,32],[false,33],[true,34],[false,44],[true,45],[false,47],[true,57],[false,90],[true,91],[false,101],[true,102],[false,109],[true,110],[false,115],[true,116],[false,122],[true,123]]}
-    const elements = () => [
-        [ws, elements1]
-    ];
-    // {"empty":false,"map":[[false,33],[true,34],[false,44],[true,45],[false,47],[true,57],[false,90],[true,91],[false,92],[true,93],[false,101],[true,102],[false,109],[true,110],[false,115],[true,116],[false,122],[true,123]]}
-    const array1 = () => [
-        str(']'), // 93
-        [elements1, cp(']')],
-    ];
     // {"empty":false,"map":[[false,90],[true,91]]}
-    const array = () => [
-        [cp('['), ws, array1]
-    ];
+    const array = list('[', element, ']');
     // {"empty":false,"map":[[false,33],[true,34]]}
-    const member1 = () => [
-        [string, ws, cp(':'), element]
+    const member = () => [
+        [string, ws, cp(':'), ws, element]
     ];
-    // {"empty":true,"map":[[false,43],[true,44]]}
-    const members2 = () => [
-        [],
-        [cp(','), members], // 44
-    ];
-    // {"empty":false,"map":[[false,33],[true,34]]}
-    const members1 = () => [
-        [member1, members2]
-    ];
-    // {"empty":false,"map":[[false,8],[true,10],[false,12],[true,13],[false,31],[true,32],[false,33],[true,34]]}
-    const members = () => [
-        [ws, members1]
-    ];
-    // {"empty":false,"map":[[false,33],[true,34],[false,124],[true,125]]}
-    const object1 = () => [
-        str('}'), // 125
-        [members1, cp('}')],
-    ];
     // {"empty":false,"map":[[false,122],[true,123]]}
-    const object = () => [
-        [cp('{'), ws, object1]
-    ];
+    const object = list('{', member, '}');
     // {"empty":false,"map":[[false,33],[true,34],[false,44],[true,45],[false,47],[true,57],[false,90],[true,91],[false,101],[true,102],[false,109],[true,110],[false,115],[true,116],[false,122],[true,123]]}
@@ -166,3 +107,3 @@ const value = () => [
     // {"empty":false,"map":[[false,8],[true,10],[false,12],[true,13],[false,31],[true,32],[false,33],[true,34],[false,44],[true,45],[false,47],[true,57],[false,90],[true,91],[false,101],[true,102],[false,109],[true,110],[false,115],[true,116],[false,122],[true,123]]}
-    const json = element;
+    const json = [ws, element];
     const _ = json;
@@ -169,0 +110,0 @@ };

package.json

 {
   "name": "functionalscript",
-  "version": "0.4.0",
+  "version": "0.4.1",
   "type": "module",
@@ -5,0 +5,0 @@ "files": [

types/array/module.f.d.ts

@@ -9,2 +9,3 @@ /**
 export type Array2<T> = readonly [T, T];
+export declare const isArray2: <T>(a: readonly T[]) => a is Array2<T>;
 export type Tuple2<T0, T1> = readonly [T0, T1];
@@ -11,0 +12,0 @@ export type Index2 = 0 | 1;

types/array/module.f.js

@@ -7,2 +7,3 @@ /**
 import { map } from "../nullable/module.f.js";
+export const isArray2 = (a) => a.length === 2;
 const uncheckTail = (a) => a.slice(1);
@@ -9,0 +10,0 @@ const uncheckHead = (a) => a.slice(0, -1);

types/bigint/module.f.d.ts

@@ -16,2 +16,3 @@ /**
  * const bitmask = mask(5n) // 31n
+ * const m = min(3n)(13n) // 3n
  * ```
@@ -46,2 +47,3 @@ */
  *    determining the exact value of the logarithm.
+ * 3. **Remainder Phase:** Using `Math.log2`.
  */
@@ -83,1 +85,5 @@ export declare const log2: (v: bigint) => bigint;
 export declare const mask: (len: bigint) => bigint;
+/**
+ * A minimal value.
+ */
+export declare const min: (a: bigint) => (b: bigint) => bigint;

types/bigint/module.f.js

@@ -16,2 +16,3 @@ /**
  * const bitmask = mask(5n) // 31n
+ * const m = min(3n)(13n) // 3n
  * ```
@@ -43,2 +44,3 @@ */
  *    determining the exact value of the logarithm.
+ * 3. **Remainder Phase:** Using `Math.log2`.
  */
@@ -49,4 +51,9 @@ export const log2 = (v) => {
     }
-    let result = 31n;
-    let i = 32n;
+    //
+    // 1. Fast Doubling.
+    //
+    let result = -1n;
+    // `bigints` higher than 2**1023 may lead to `Inf` during conversion to `number`.
+    // For example: `Number((1n << 1024n) - (1n << 970n)) === Inf`.
+    let i = 1023n;
     while (true) {
@@ -62,5 +69,8 @@ const n = v >> i;
     }
+    //
+    // 2. Binary Search.
+    //
     // We know that `v` is not 0 so it doesn't make sense to check `n` when `i` is 0.
-    // Because of this, We check if `i` is greater than 32 before we divide it by 2.
-    while (i !== 32n) {
+    // Because of this, We check if `i` is greater than 1023 before we divide it by 2.
+    while (i !== 1023n) {
         i >>= 1n;
@@ -73,3 +83,11 @@ const n = v >> i;
     }
-    return result - BigInt(Math.clz32(Number(v)));
+    //
+    // 3. Remainder Phase.
+    //
+    // We know that `v` is less than `1n << 1023` so we can calculate a remainder using
+    // `Math.log2`.
+    const rem = BigInt(Math.log2(Number(v)) | 0);
+    // (v >> rem) is either `0` or `1`, and it's used as a correction for
+    // Math.log2 rounding.
+    return result + rem + (v >> rem);
 };
@@ -118,1 +136,5 @@ /**
 export const mask = (len) => (1n << len) - 1n;
+/**
+ * A minimal value.
+ */
+export const min = (a) => (b) => a < b ? a : b;

types/bigint/test.f.d.ts

@@ -0,8 +1,11 @@
+export declare const clz32Log2: (v: bigint) => bigint;
 declare const _default: {
     example: () => void;
-    benchmark: {
-        str: () => void;
-        stringHexLog2: () => void;
-        oldLog2: () => void;
-        log2: () => void;
+    benchmark: () => {
+        big: {
+            [k: string]: () => void;
+        };
+        small: {
+            [k: string]: () => void;
+        };
     };
@@ -9,0 +12,0 @@ mask: () => void;

types/bigint/test.f.js

@@ -1,2 +0,2 @@
-import { sum, abs, serialize, log2, bitLength, mask } from "./module.f.js";
+import { sum, abs, serialize, log2, bitLength, mask, min } from "./module.f.js";
 const oldLog2 = (v) => {
@@ -30,16 +30,55 @@ if (v <= 0n) {
 };
-const stringLog2 = (v) => BigInt(v.toString(2).length) - 1n;
-const stringHexLog2 = (v) => {
+const strBinLog2 = (v) => BigInt(v.toString(2).length) - 1n;
+const strHexLog2 = (v) => {
     const len = (BigInt(v.toString(16).length) - 1n) << 2n;
-    const x = v >> len;
-    return len + 31n - BigInt(Math.clz32(Number(x)));
+    return len + 31n - BigInt(Math.clz32(Number(v >> len)));
 };
-const benchmark = (f) => () => {
+const str32Log2 = (v) => {
+    const len = (BigInt(v.toString(32).length) - 1n) * 5n;
+    return len + 31n - BigInt(Math.clz32(Number(v >> len)));
+};
+export const clz32Log2 = (v) => {
+    if (v <= 0n) {
+        return -1n;
+    }
+    let result = 31n;
+    let i = 32n;
+    while (true) {
+        const n = v >> i;
+        if (n === 0n) {
+            // overshot
+            break;
+        }
+        v = n;
+        result += i;
+        i <<= 1n;
+    }
+    // We know that `v` is not 0 so it doesn't make sense to check `n` when `i` is 0.
+    // Because of this, We check if `i` is greater than 32 before we divide it by 2.
+    while (i !== 32n) {
+        i >>= 1n;
+        const n = v >> i;
+        if (n !== 0n) {
+            result += i;
+            v = n;
+        }
+    }
+    return result - BigInt(Math.clz32(Number(v)));
+};
+const benchmark = f => () => {
     let e = 1048575n;
     let c = 1n << e;
-    for (let i = 0n; i < 1_000; ++i) {
-        const x = f(c);
-        if (x !== e) {
-            throw x;
+    for (let i = 0n; i < 1_100; ++i) {
+        {
+            const x = f(c);
+            if (x !== e) {
+                throw x;
+            }
         }
+        {
+            const x = f(c - 1n);
+            if (x !== e - 1n) {
+                throw [e, x];
+            }
+        }
         c >>= 1n;
@@ -49,2 +88,22 @@ --e;
 };
+const benchmarkSmall = f => () => {
+    let e = 2000n;
+    let c = 1n << e;
+    do {
+        {
+            const x = f(c);
+            if (x !== e) {
+                throw [e, x];
+            }
+        }
+        for (let j = 1n; j < min(c >> 1n)(1000n); ++j) {
+            const x = f(c - j);
+            if (x !== e - 1n) {
+                throw [j, e, x];
+            }
+        }
+        c >>= 1n;
+        --e;
+    } while (c !== 0n);
+};
 export default {
@@ -58,22 +117,35 @@ example: () => {
         if (absoluteValue !== 42n) {
-            throw total;
+            throw absoluteValue;
         }
         const logValue = log2(8n); // 3n
         if (logValue !== 3n) {
-            throw total;
+            throw logValue;
         }
         const bitCount = bitLength(255n); // 8n
         if (bitCount !== 8n) {
-            throw total;
+            throw bitCount;
         }
         const bitmask = mask(5n); // 31n
         if (bitmask !== 31n) {
-            throw total;
+            throw benchmark;
         }
+        const m = min(3n)(13n); // 3n
+        if (m !== 3n) {
+            throw m;
+        }
     },
-    benchmark: {
-        str: benchmark(stringLog2),
-        stringHexLog2: benchmark(stringHexLog2),
-        oldLog2: benchmark(oldLog2),
-        log2: benchmark(log2),
+    benchmark: () => {
+        const list = {
+            strBinLog2,
+            strHexLog2,
+            str32Log2,
+            oldLog2,
+            clz32Log2,
+            log2,
+        };
+        const transform = (b) => Object.fromEntries(Object.entries(list).map(([k, f]) => [k, b(f)]));
+        return {
+            big: transform(benchmark),
+            small: transform(benchmarkSmall),
+        };
     },
@@ -80,0 +152,0 @@ mask: () => {

No alert changes

Improved metrics

Total package byte prevSize

552218

increased by2.07%

Number of package files

221

increased by3.76%

Lines of code

15732

increased by2.78%

No dependency changes