functionalscript · sergey-shandar · Aug 9, 2026 · Aug 9, 2026 · Aug 9, 2026 · Aug 9, 2026
diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -20,6 +20,13 @@ history.
 
 ## Unreleased
 
+- **BREAKING CHANGES:** `fjs/types/btree/find` migrates from authored
+  TypeScript (`.f.ts`) to JSDoc-typed JavaScript (`.f.mjs`) under the
+  stage-1 TypeScript-to-mjs migration — importers must use the `.f.mjs`
+  specifier; implementation-only typedefs (`FirstLeaf1`, `FirstBranch3`,
+  `FirstLeaf2`, `FirstBranch5`, `PathItem3`, `PathItem5`) are renamed to
+  their private `_`-prefixed forms
+  [#1470](https://github.com/functionalscript/functionalscript/pull/1470)
 - **BREAKING CHANGES:** `fjs/types/btree/types` migrates from authored
   TypeScript (`.f.ts`) to JSDoc-typed JavaScript (`.f.mjs`) under the
   stage-1 TypeScript-to-mjs migration — importers must use the `.f.mjs`

diff --git a/fjs/types/btree/find/module.f.mjs b/fjs/types/btree/find/module.f.mjs
@@ -0,0 +1,133 @@
+/**
+ * Lookup operations for persistent B-tree structures.
+ *
+ * @module
+ */
+/** @import { Leaf1, Leaf2, Branch3, Branch5, TNode } from '../types/module.f.mjs' */
+/** @import { List } from '../../list/module.f.mjs' */
+
+import { index3, index5 } from '../../function/compare/module.f.mjs'
+/** @import { Compare } from '../../function/compare/module.f.mjs' */
+
+/** @import { KeyOf, Index } from '../../array/module.f.mjs' */
+
+/**
+ * @template T
+ * @typedef {readonly[Index<3>, Leaf1<T>]} _FirstLeaf1
+ */
+
+/**
+ * @template T
+ * @typedef {readonly[1, Branch3<T>]} _FirstBranch3
+ */
+
+/**
+ * @template T
+ * @typedef {readonly[Index<5>, Leaf2<T>]} _FirstLeaf2
+ */
+
+/**
+ * @template T
+ * @typedef {readonly[1|3, Branch5<T>]} _FirstBranch5
+ */
+
+/**
+ * @template T
+ * @typedef {_FirstLeaf1<T> | _FirstBranch3<T> | _FirstLeaf2<T> | _FirstBranch5<T>} First
+ */
+
+/**
+ * @template T
+ * @typedef {readonly[0|2, Branch3<T>]} _PathItem3
+ */
+
+/**
+ * @template T
+ * @typedef {readonly[0|2|4, Branch5<T>]} _PathItem5
+ */
+
+/**
+ * @template T
+ * @typedef {_PathItem3<T> | _PathItem5<T>} PathItem
+ */
+
+/** @type {<T>(item: PathItem<T>) => TNode<T>} */
+const child = item => {
+    /** @typedef {typeof item extends PathItem<infer T> ? T : never} T */
+    return /** @type {TNode<T>} */ (item[1][item[0]])
+}
+
+/**
+ * @template T
+ * @typedef {List<PathItem<T>>} Path
+ */
+
+/**
+ * @template T
+ * @typedef {{
+ *   readonly first: First<T>,
+ *   readonly tail: Path<T>
+ * }} Result
+ */
+
+/** @type {<T>(c: Compare<T>) => (node: TNode<T>) => Result<T>} */
+export const find = c => {
+    /** @typedef {typeof c extends Compare<infer T> ? T : never} T */
+    const i3 = index3(c)
+    const i5 = index5(c)
+    /** @type {(tail: Path<T>) => (node: TNode<T>) => Result<T>} */
+    const f = tail => node => {
+        /** @type {(index: KeyOf<typeof node>) => Result<T>} */
+        const append = index => {
+            const first = /** @type {PathItem<T>} */ ([index, node])
+            return f({ first, tail })(child(first))
+        }
+        /** @type {(index: KeyOf<typeof node>) => Result<T>} */
+        const done = index => ({ first: /** @type {First<T>} */ ([index, node]), tail })
+        switch (node.length) {
+            case 1: { return done(i3(node[0])) }
+            case 2: { return done(i5(node)) }
+            case 3: {
+                const i = i3(node[1])
+                switch (i) {
+                    case 0: case 2: { return append(i) }
+                    case 1: { return done(i) }
+                }
+            }
+            case 5: {
+                const i = i5([node[1], node[3]])
+                switch (i) {
+                    case 0: case 2: case 4: { return append(i) }
+                    case 1: case 3: { return done(i) }
+                }
+            }
+        }
+    }
+    return f(null)
+}
+
+/** @type {<T>(first: First<T>) => boolean} */
+export const isFound = ([i]) => {
+    switch (i) {
+        case 1: case 3: { return true }
+        default: { return false }
+    }
+}
+
+/** @type {<T>(first: First<T>) => T | null} */
+export const value = ([i, r]) => {
+    switch (i) {
+        case 1: {
+            switch (r.length) {
+                case 1: case 2: { return r[0] }
+                default: { return r[1] }
+            }
+        }
+        case 3: {
+            return r.length === 2 ? r[1] : r[3]
+        }
+        default: {
+            return null
+        }
+    }
+}
diff --git a/fjs/types/btree/find/module.f.ts b/fjs/types/btree/find/module.f.ts
diff --git a/fjs/types/btree/find/proof.f.ts b/fjs/types/btree/find/proof.f.ts
@@ -1,4 +1,4 @@
-import { type Result, find as btreeFind } from './module.f.ts'
+import { type Result, find as btreeFind } from './module.f.mjs'
 import { map, toArray } from '../../list/module.f.mjs'
 import { stringify, type Unknown } from '../../../media/json/module.f.ts'
 import { sort } from '../../object/module.f.ts'

diff --git a/fjs/types/btree/proof.f.ts b/fjs/types/btree/proof.f.ts
@@ -5,7 +5,7 @@ import { sort } from '../object/module.f.ts'
 import { cmp } from '../string/module.f.ts'
 import { next, toArray, type List, type Result } from '../list/module.f.mjs'
 import { set as setSet } from './set/module.f.ts'
-import { value, find as findFind } from './find/module.f.ts'
+import { value, find as findFind } from './find/module.f.mjs'
 import { assertEq } from '../../asserts/module.f.mjs'
 
 const jsonStr = jsonStringify(sort)

diff --git a/fjs/types/btree/remove/module.f.ts b/fjs/types/btree/remove/module.f.ts
@@ -5,7 +5,7 @@
  */
 import { collapseRoot, type Leaf1, type TNode, type Branch1, type Branch3, type Branch5, type Tree } from '../types/module.f.mjs'
 import type { Compare } from '../../function/compare/module.f.mjs'
-import { type Path, type PathItem, find } from '../find/module.f.ts'
+import { type Path, type PathItem, find } from '../find/module.f.mjs'
 import { fold, concat, next } from '../../list/module.f.mjs'
 import type { Tuple } from '../../array/module.f.mjs'
 import { map } from '../../nullable/module.f.mjs'

diff --git a/fjs/types/btree/set/module.f.ts b/fjs/types/btree/set/module.f.ts
@@ -4,7 +4,7 @@
  * @module
  */
 import { collapseRoot, type Branch1, type Branch3, type Branch5, type Branch7, type TNode, type Tree } from '../types/module.f.mjs'
-import { find, type First, type PathItem, type Result } from '../find/module.f.ts'
+import { find, type First, type PathItem, type Result } from '../find/module.f.mjs'
 import type { Compare } from '../../function/compare/module.f.mjs'
 import { fold } from '../../list/module.f.mjs'
 

diff --git a/fjs/types/ordered_map/module.f.ts b/fjs/types/ordered_map/module.f.ts
@@ -4,7 +4,7 @@
  * @module
  */
 import type { Tree } from '../btree/types/module.f.mjs'
-import { value, find } from '../btree/find/module.f.ts'
+import { value, find } from '../btree/find/module.f.mjs'
 import { set } from '../btree/set/module.f.ts'
 import { remove as btreeRemove } from '../btree/remove/module.f.ts'
 import { values } from '../btree/module.f.ts'

diff --git a/fjs/types/string_set/module.f.ts b/fjs/types/string_set/module.f.ts
@@ -22,7 +22,7 @@
 
 import type { Tree } from '../btree/types/module.f.mjs'
 import { empty as btEmpty, values as btValues } from '../btree/module.f.ts'
-import { find, isFound } from '../btree/find/module.f.ts'
+import { find, isFound } from '../btree/find/module.f.mjs'
 import { remove as btreeRemove } from '../btree/remove/module.f.ts'
 import { set as btreeSet } from '../btree/set/module.f.ts'
 import { cmp } from "../string/module.f.ts"