1  import { $, fact, Data, Math, Memory, API, Link, Collection } from './lib.js'
  2  
  3  const id = Memory.entity
  4  
  5  const db = Memory.create([
  6    // bafyr4ibnhlpn74i3mhyuzcdogwx2anttnxgypj2ne624cuicexiplexccm
  7    { of: id(0), the: 'data/type', is: 'list' },
  8    // bafyr4ici7rzb7o6bolqjex5cplywohpcew5je4juqauzrmikcvukdcdffm
  9    { of: id(1), the: 'meta/name', is: 'a' },
 10    // bafyr4iflco7n6qxijoxa67dcy7owvcw2k4piqkn623vflaqx6a3bwxrf2a
 11    { of: id(2), the: 'meta/name', is: 'b' },
 12    // bafyr4ihb4dub23vdtmgprodp7vcasiibd5luadf4h53krilrsbvjxdlvau
 13    { of: id(3), the: 'meta/name', is: 'c' },
 14    { of: id(0), the: 'list/next', is: id(1) },
 15    { of: id(1), the: 'list/next', is: id(2) },
 16    { of: id(2), the: 'list/next', is: id(3) },
 17  ])
 18  
 19  /**
 20   * @type {import('entail').Suite}
 21   */
 22  export const testRecursion = {
 23    'test ancestor': async (assert) => {
 24      const Parent = fact({
 25        the: 'child',
 26        parent: Object,
 27      })
 28  
 29      const Ancestor = fact({ of: Object })
 30        .with({ parent: Object })
 31        .when(({ this: ancestor, of: child, parent }) => ({
 32          direct: [Parent({ parent: ancestor, this: child })],
 33          transitive: [
 34            Parent({ parent, this: child }),
 35            Ancestor({ this: ancestor, of: parent }),
 36          ],
 37        }))
 38  
 39      const eve = {
 40        'person/name': 'Eve',
 41      }
 42      const adam = {
 43        'person/name': 'Adam',
 44        'child/parent': eve,
 45      }
 46      const jack = {
 47        'person/name': 'Jack',
 48        'child/parent': adam,
 49      }
 50      const mallory = {
 51        'person/name': 'Mallory',
 52        'child/parent': jack,
 53      }
 54      const bob = {
 55        'person/name': 'Bob',
 56        'child/parent': mallory,
 57      }
 58      const alice = {
 59        'person/name': 'Alice',
 60        'child/parent': bob,
 61      }
 62  
 63      const people = {
 64        alice,
 65        bob,
 66        mallory,
 67        jack,
 68        adam,
 69        eve,
 70      }
 71  
 72      const ancestors = await Ancestor().query({
 73        from: Memory.create({ people }),
 74      })
 75  
 76      assert.deepEqual(
 77        new Set(ancestors),
 78        new Set([
 79          Ancestor.assert({ this: Link.of(bob), of: Link.of(alice) }),
 80          Ancestor.assert({ this: Link.of(mallory), of: Link.of(bob) }),
 81          Ancestor.assert({ this: Link.of(jack), of: Link.of(mallory) }),
 82          Ancestor.assert({ this: Link.of(adam), of: Link.of(jack) }),
 83          Ancestor.assert({ this: Link.of(mallory), of: Link.of(alice) }),
 84          Ancestor.assert({ this: Link.of(jack), of: Link.of(bob) }),
 85          Ancestor.assert({ this: Link.of(adam), of: Link.of(mallory) }),
 86          Ancestor.assert({ this: Link.of(jack), of: Link.of(alice) }),
 87          Ancestor.assert({ this: Link.of(adam), of: Link.of(bob) }),
 88          Ancestor.assert({ this: Link.of(adam), of: Link.of(alice) }),
 89          Ancestor.assert({ this: Link.of(eve), of: Link.of(alice) }),
 90          Ancestor.assert({ this: Link.of(eve), of: Link.of(bob) }),
 91          Ancestor.assert({ this: Link.of(eve), of: Link.of(mallory) }),
 92          Ancestor.assert({ this: Link.of(eve), of: Link.of(jack) }),
 93          Ancestor.assert({ this: Link.of(eve), of: Link.of(adam) }),
 94        ])
 95      )
 96    },
 97  
 98    'complex ancestor test': async (assert) => {
 99      const Parent = fact({
100        the: 'child',
101        parent: Object,
102      })
103  
104      const Ancestor = fact({ of: Object })
105        .with({ parent: Object })
106        .when(({ this: ancestor, of: child, parent }) => ({
107          direct: [Parent({ parent: ancestor, this: child })],
108          transitive: [
109            Parent({ parent, this: child }),
110            Ancestor({ this: ancestor, of: parent }),
111          ],
112        }))
113  
114      // Create a complex family tree with multiple paths to the same nodes
115      //
116      // Family Tree Structure (→ means "has parent"):
117      //
118      //      david → mallory
119      //     /               \
120      // alice → bob         jack
121      //     \     \        /   \
122      //      \     mallory     adam → eve
123      //       \                /
124      //        charlie → dave
125      //
126      // Note: Both bob and david have mallory as parent
127      // Note: Both mallory and dave have jack as parent
128      // Note: There are multiple paths from alice to jack (and thus to adam and eve)
129  
130      const alice = Link.of('alice')
131      const bob = Link.of('bob')
132      const charlie = Link.of('charlie')
133      const david = Link.of('david')
134      const mallory = Link.of('mallory')
135      const jack = Link.of('jack')
136      const adam = Link.of('adam')
137      const eve = Link.of('eve')
138      const dave = Link.of('dave')
139      const db = Memory.create([
140        // First branch
141        { of: alice, the: 'child/parent', is: bob },
142        { of: bob, the: 'child/parent', is: mallory },
143        { of: mallory, the: 'child/parent', is: jack },
144  
145        // Second branch
146        { of: alice, the: 'child/parent', is: charlie },
147        { of: charlie, the: 'child/parent', is: dave },
148        { of: dave, the: 'child/parent', is: jack },
149  
150        // Third branch
151        { of: alice, the: 'child/parent', is: david },
152        { of: david, the: 'child/parent', is: mallory },
153  
154        // Common descendants
155        { of: jack, the: 'child/parent', is: adam },
156        { of: adam, the: 'child/parent', is: eve },
157      ])
158  
159      const ancestors = await Ancestor().query({ from: db })
160  
161      // Define the expected ancestor relationships
162      const expectedAncestors = [
163        // Direct parent relationships (10)
164        Ancestor.assert({ this: bob, of: alice }),
165        Ancestor.assert({ this: charlie, of: alice }),
166        Ancestor.assert({ this: david, of: alice }),
167        Ancestor.assert({ this: mallory, of: bob }),
168        Ancestor.assert({ this: mallory, of: david }),
169        Ancestor.assert({ this: jack, of: mallory }),
170        Ancestor.assert({ this: dave, of: charlie }),
171        Ancestor.assert({ this: jack, of: dave }),
172        Ancestor.assert({ this: adam, of: jack }),
173        Ancestor.assert({ this: eve, of: adam }),
174  
175        // Transitive relationships (19)
176        Ancestor.assert({ this: mallory, of: alice }), // via bob or via david
177        Ancestor.assert({ this: jack, of: alice }), // via bob/mallory or via david/mallory or via charlie/dave
178        Ancestor.assert({ this: jack, of: bob }), // via mallory
179        Ancestor.assert({ this: jack, of: david }), // via mallory
180        Ancestor.assert({ this: jack, of: charlie }), // via dave
181        Ancestor.assert({ this: adam, of: alice }), // via any path to jack
182        Ancestor.assert({ this: adam, of: bob }), // via mallory/jack
183        Ancestor.assert({ this: adam, of: david }), // via mallory/jack
184        Ancestor.assert({ this: adam, of: mallory }), // via jack
185        Ancestor.assert({ this: adam, of: charlie }), // via dave/jack
186        Ancestor.assert({ this: adam, of: dave }), // via jack
187        Ancestor.assert({ this: dave, of: alice }), // via charlie
188        Ancestor.assert({ this: eve, of: alice }), // via any path to adam
189        Ancestor.assert({ this: eve, of: bob }), // via mallory/jack/adam
190        Ancestor.assert({ this: eve, of: david }), // via mallory/jack/adam
191        Ancestor.assert({ this: eve, of: mallory }), // via jack/adam
192        Ancestor.assert({ this: eve, of: jack }), // via adam
193        Ancestor.assert({ this: eve, of: charlie }), // via dave/jack/adam
194        Ancestor.assert({ this: eve, of: dave }), // via jack/adam
195      ]
196  
197      // Create sets for comparison (using string representations for equality comparison)
198      const expectedSet = new Set(
199        expectedAncestors.map((rel) =>
200          JSON.stringify({ this: rel.this, of: rel.of })
201        )
202      )
203  
204      const actualSet = new Set(
205        ancestors.map((rel) => JSON.stringify({ this: rel.this, of: rel.of }))
206      )
207  
208      // Find missing and extra relationships
209      const missing = [...expectedSet].filter((rel) => !actualSet.has(rel))
210      const extra = [...actualSet].filter((rel) => !expectedSet.has(rel))
211  
212      if (missing.length > 0 || extra.length > 0) {
213        console.log(
214          'Missing relationships:',
215          missing.map((r) => JSON.parse(r))
216        )
217        console.log(
218          'Extra relationships:',
219          extra.map((r) => JSON.parse(r))
220        )
221      }
222  
223      // Verify we have the correct total number of unique ancestor relationships
224      // Direct relationships: 10
225      // Transitive relationships: 19
226      // Total: 29 unique relationships
227      assert.strictEqual(
228        actualSet.size,
229        29,
230        `Should have 29 total unique ancestor relationships, but got ${actualSet.size}`
231      )
232    },
233    'test traverse': async (assert) => {
234      const Range = fact({ n: Number, from: Number, to: Number })
235        .with({ m: Number })
236        .when(({ n, from, to, m }) => ({
237          base: [
238            Data.less({ this: from, than: to }),
239            Data.same({ this: from, as: n }),
240            Range.claim({ n, from, to }),
241          ],
242          step: [
243            Data.less({ this: from, than: to }),
244            Math.Sum({ of: from, with: 1, is: m }),
245            Range({ n, from: m, to: to }),
246          ],
247        }))
248  
249      assert.deepEqual(
250        await Range.match({ from: 1, to: 5 }).query({ from: db }),
251        [
252          Range.assert({ from: 1, n: 1, to: 5 }),
253          Range.assert({
254            this: Range.assert({ from: 2, n: 2, to: 5 }).this,
255            from: 1,
256            n: 2,
257            to: 5,
258          }),
259          Range.assert({
260            this: Range.assert({ from: 3, n: 3, to: 5 }).this,
261            from: 1,
262            n: 3,
263            to: 5,
264          }),
265          Range.assert({
266            this: Range.assert({ from: 4, n: 4, to: 5 }).this,
267            from: 1,
268            n: 4,
269            to: 5,
270          }),
271        ]
272      )
273    },
274  
275    'test recursion': async (assert) => {
276      const Head = fact({ the: 'list', next: Object })
277  
278      const List = Head.with({ transient: Object }).when(
279        ({ transient, ...head }) => ({
280          head: [Head(head)],
281          child: [
282            Head({ this: head.this, next: transient }),
283            List({ this: transient, next: head.next }),
284          ],
285        })
286      )
287  
288      const Meta = fact({
289        the: 'meta',
290        name: String,
291      })
292  
293      const Connection = fact({
294        from: Object,
295        to: Object,
296        name: String,
297      }).where(({ from, to, name }) => [
298        List({ this: from, next: to }),
299        Meta({ this: to, name: name }),
300        Connection.claim({ from, to, name }),
301      ])
302  
303      return assert.deepEqual(await Connection().query({ from: db }), [
304        Connection.assert({ from: id(0), to: id(1), name: 'a' }),
305        Connection.assert({ from: id(1), to: id(2), name: 'b' }),
306        Connection.assert({ from: id(0), to: id(2), name: 'b' }),
307        Connection.assert({ from: id(2), to: id(3), name: 'c' }),
308        Connection.assert({ from: id(1), to: id(3), name: 'c' }),
309        Connection.assert({ from: id(0), to: id(3), name: 'c' }),
310      ])
311    },
312    'test rooted recursion': async (assert) => {
313      // return 'seems to enter infinite loop'
314      const Content = fact({ the: 'data', type: String })
315      const Head = fact({ the: 'list', next: Object })
316      const Meta = fact({ the: 'meta', name: String })
317      const List = Head.with({ trasitive: Object }).when(
318        ({ trasitive, ...head }) => ({
319          direct: [Head(head)],
320          trasitive: [
321            Head({ this: head.this, next: trasitive }),
322            List({ this: trasitive, next: head.next }),
323          ],
324        })
325      )
326  
327      const Node = fact({
328        node: Object,
329        name: String,
330      })
331        .with({ root: Object })
332        .where(({ node, name, root }) => [
333          Content({ this: root, type: 'list' }),
334          List({ this: root, next: node }),
335          Meta({ this: node, name }),
336          Node.claim({ node, name }),
337        ])
338  
339      assert.deepEqual(await Node().query({ from: db }), [
340        Node.assert({ node: id(1), name: 'a' }),
341        Node.assert({ node: id(2), name: 'b' }),
342        Node.assert({ node: id(3), name: 'c' }),
343      ])
344    },
345    'test implicit': async (assert) => {
346      const Content = fact({ the: 'data', type: String })
347      const Head = fact({ the: 'list', next: Object })
348      const Meta = fact({ the: 'meta', name: String })
349      const List = Head.with({ transient: Object }).when(
350        ({ transient, ...head }) => ({
351          head: [Head(head)],
352          child: [
353            Head({ this: head.this, next: transient }),
354            List({ this: transient, next: head.next }),
355          ],
356        })
357      )
358  
359      const Implicit = fact({
360        at: String,
361        is: Object,
362        default: null,
363      }).when(({ at, this: of, is, default: implicit, _ }) => ({
364        explicit: [
365          Collection({ this: of, at, of: is }),
366          Data.Type({ of: implicit, is: _ }),
367        ],
368        implicit: [
369          Collection.not({ this: of, at }),
370          Data.same({ this: implicit, as: is }),
371        ],
372      }))
373  
374      const Node = fact({
375        each: Object,
376        name: String,
377        next: Object,
378      })
379        .with({ root: Object })
380        .where(({ each, name, next, root }) => [
381          Content({ this: root, type: 'list' }),
382          List({ this: root, next: each }),
383          Meta({ this: each, name }),
384          Implicit({
385            this: each,
386            at: 'list/next',
387            is: next,
388            default: null,
389          }),
390          Node.claim({ each, name, next }),
391        ])
392  
393      assert.deepEqual(await Node().query({ from: db }), [
394        Node.assert({ each: id(1), name: 'a', next: id(2) }),
395        Node.assert({ each: id(2), name: 'b', next: id(3) }),
396        // @ts-expect-error - inference doesn't know next is entity | null
397        Node.assert({ each: id(3), name: 'c', next: null }),
398      ])
399    },
400  
401    'test recursion termination': async (assert) => {
402      const Content = fact({ the: 'data', type: String })
403      const Head = fact({ the: 'list', next: Object })
404      const Meta = fact({ the: 'meta', name: String })
405      const List = Head.with({ trasitive: Object }).when(
406        ({ trasitive, ...head }) => ({
407          direct: [Head(head)],
408          trasitive: [
409            Head({ this: head.this, next: trasitive }),
410            List({ this: trasitive, next: head.next }),
411          ],
412        })
413      )
414  
415      const Node = fact({
416        node: Object,
417        name: String,
418      })
419        .with({ root: Object })
420        .where(({ node, name, root }) => [
421          Content({ this: root, type: 'list' }),
422          List({ this: root, next: node }),
423          Meta({ this: node, name }),
424          Node.claim({ node, name }),
425        ])
426  
427      assert.deepEqual(await Node().query({ from: db }), [
428        Node.assert({
429          node: id(1),
430          name: 'a',
431        }),
432        Node.assert({
433          node: id(2),
434          name: 'b',
435        }),
436        Node.assert({
437          node: id(3),
438          name: 'c',
439        }),
440      ])
441    },
442  
443    'test not really recursive': async (assert) => {
444      const Person = fact({
445        the: 'meta',
446        name: String,
447      })
448  
449      const Query = Person.when((person) => ({
450        base: [Person(person)],
451        recur: [Query(person)],
452      }))
453  
454      const results = await Query().query({ from: db })
455      // Check result length rather than exact content due to ID/hash mismatches
456      assert.strictEqual(results.length, 3, 'Should return 3 people')
457  
458      // Check each object has the correct name
459      const names = results.map((r) => r.name).sort()
460      assert.deepEqual(names, ['a', 'b', 'c'], 'Should include all 3 names')
461    },
462  
463    'test tautology': async (assert) => {
464      const Person = fact({
465        the: 'meta',
466        name: String,
467      })
468  
469      const Tautology = Person.where((person) => [
470        Person(person),
471        Tautology(person),
472      ])
473  
474      const results = await Tautology().query({ from: db })
475      // Check result length rather than exact content due to ID/hash mismatches
476      assert.strictEqual(results.length, 3, 'Should return 3 people')
477  
478      // Check each object has the correct name
479      const names = results.map((r) => r.name).sort()
480      assert.deepEqual(names, ['a', 'b', 'c'], 'Should include all 3 names')
481    },
482  
483    'test partial binding tautology': async (assert) => {
484      const Person = fact({
485        the: 'meta',
486        name: String,
487      })
488  
489      // Define a relationship that introduces a second unbound variable
490      const PartialTautology = fact({
491        name: String,
492        extra: Object, // This will remain unbound in the recursive case
493      }).where(({ this: person, name, extra }) => [
494        Person({ this: person, name }),
495        PartialTautology({ this: person, name, extra }),
496      ])
497  
498      // This test should complete without infinite recursion
499      // The query should return results only for valid bindings
500      const results = await PartialTautology().query({ from: db })
501  
502      assert.strictEqual(results.length, 0, 'Should have no results')
503    },
504  }