339 lines
11 KiB
TypeScript
339 lines
11 KiB
TypeScript
/**
|
|
* GraphAdjacencyIndex Pagination Tests (v5.8.0, updated for the 8.0 u64 contract)
|
|
*
|
|
* Tests for pagination support in GraphIndex methods:
|
|
* - getNeighbors() with limit/offset
|
|
* - getVerbIdsBySource() with limit/offset
|
|
* - getVerbIdsByTarget() with limit/offset
|
|
*
|
|
* 8.0 BigInt boundary: entity ints in (resolved via the metadata index's
|
|
* idMapper), entity/verb ints out (`bigint[]`). Entity ints map back to UUIDs
|
|
* via `idMapper.getUuid(Number(int))`; verb ints via `verbIntsToIds()`.
|
|
*/
|
|
|
|
import { describe, it, expect, beforeEach } from 'vitest'
|
|
import { Brainy } from '../../src/brainy.js'
|
|
import { NounType, VerbType } from '../../src/types/graphTypes.js'
|
|
|
|
describe('GraphAdjacencyIndex Pagination', () => {
|
|
let brain: Brainy
|
|
let centralId: string
|
|
let neighborIds: string[]
|
|
|
|
/** The brain's graph index (BigInt provider contract). */
|
|
const graphIndex = () => (brain as any).graphIndex
|
|
|
|
/** The shared UUID ↔ int resolver. */
|
|
const idMapper = () => (brain as any).metadataIndex.getIdMapper()
|
|
|
|
/** Resolve a UUID to its entity int (must already be mapped). */
|
|
const entityInt = (uuid: string): bigint => {
|
|
const intId = idMapper().getInt(uuid)
|
|
expect(intId).toBeDefined()
|
|
return BigInt(intId!)
|
|
}
|
|
|
|
/** Map returned entity ints back to UUIDs. */
|
|
const intsToUuids = (ints: bigint[]): string[] =>
|
|
ints
|
|
.map((i) => idMapper().getUuid(Number(i)))
|
|
.filter((u: string | undefined): u is string => u !== undefined)
|
|
|
|
beforeEach(async () => {
|
|
brain = new Brainy({ requireSubtype: false })
|
|
await brain.init()
|
|
|
|
// Create central entity
|
|
centralId = await brain.add({
|
|
data: { name: 'Central Hub' },
|
|
type: NounType.Thing
|
|
})
|
|
|
|
// Create 50 neighbor entities with relationships
|
|
neighborIds = []
|
|
for (let i = 0; i < 50; i++) {
|
|
const neighborId = await brain.add({
|
|
data: { name: `Neighbor ${i}`, index: i },
|
|
type: NounType.Thing
|
|
})
|
|
neighborIds.push(neighborId)
|
|
|
|
// Create outgoing relationship from central to neighbor
|
|
await brain.relate({
|
|
from: centralId,
|
|
to: neighborId,
|
|
type: VerbType.RelatesTo
|
|
})
|
|
}
|
|
})
|
|
|
|
describe('getNeighbors() Pagination', () => {
|
|
it('should return all neighbors without pagination', async () => {
|
|
const neighborInts = await graphIndex().getNeighbors(entityInt(centralId))
|
|
const neighbors = intsToUuids(neighborInts)
|
|
|
|
// Should return all 50 neighbors
|
|
expect(neighbors).toHaveLength(50)
|
|
expect(neighbors.every((id: string) => neighborIds.includes(id))).toBe(true)
|
|
})
|
|
|
|
it('should return all outgoing neighbors with direction option', async () => {
|
|
const neighbors = await graphIndex().getNeighbors(entityInt(centralId), { direction: 'out' })
|
|
|
|
expect(neighbors).toHaveLength(50)
|
|
})
|
|
|
|
it('should paginate with limit only', async () => {
|
|
const page1Ints = await graphIndex().getNeighbors(entityInt(centralId), { limit: 10 })
|
|
const page1 = intsToUuids(page1Ints)
|
|
|
|
expect(page1).toHaveLength(10)
|
|
expect(page1.every((id: string) => neighborIds.includes(id))).toBe(true)
|
|
})
|
|
|
|
it('should paginate with offset only', async () => {
|
|
const all = await graphIndex().getNeighbors(entityInt(centralId))
|
|
const offsetResults = await graphIndex().getNeighbors(entityInt(centralId), { offset: 10 })
|
|
|
|
// Offset 10 should return all after first 10
|
|
expect(offsetResults).toHaveLength(all.length - 10)
|
|
})
|
|
|
|
it('should paginate with both limit and offset', async () => {
|
|
const central = entityInt(centralId)
|
|
const page1: bigint[] = await graphIndex().getNeighbors(central, { limit: 10, offset: 0 })
|
|
const page2: bigint[] = await graphIndex().getNeighbors(central, { limit: 10, offset: 10 })
|
|
const page3: bigint[] = await graphIndex().getNeighbors(central, { limit: 10, offset: 20 })
|
|
|
|
// Each page should have 10 results
|
|
expect(page1).toHaveLength(10)
|
|
expect(page2).toHaveLength(10)
|
|
expect(page3).toHaveLength(10)
|
|
|
|
// Pages should not overlap
|
|
const page2Set = new Set(page2)
|
|
const page3Set = new Set(page3)
|
|
|
|
const overlap12 = page1.filter((id) => page2Set.has(id))
|
|
const overlap23 = page2.filter((id) => page3Set.has(id))
|
|
|
|
expect(overlap12).toHaveLength(0)
|
|
expect(overlap23).toHaveLength(0)
|
|
})
|
|
|
|
it('should handle offset beyond total count', async () => {
|
|
const results = await graphIndex().getNeighbors(entityInt(centralId), { offset: 100 })
|
|
|
|
// Offset 100 > 50 total → empty array
|
|
expect(results).toHaveLength(0)
|
|
})
|
|
|
|
it('should handle limit = 0', async () => {
|
|
const results = await graphIndex().getNeighbors(entityInt(centralId), { limit: 0 })
|
|
|
|
expect(results).toHaveLength(0)
|
|
})
|
|
|
|
it('should paginate with direction filter', async () => {
|
|
// Get first 10 outgoing neighbors
|
|
const page1 = await graphIndex().getNeighbors(entityInt(centralId), {
|
|
direction: 'out',
|
|
limit: 10,
|
|
offset: 0
|
|
})
|
|
|
|
expect(page1).toHaveLength(10)
|
|
})
|
|
|
|
it('should handle pagination with incoming direction', async () => {
|
|
// Create some incoming relationships
|
|
const sourceId = await brain.add({
|
|
data: { name: 'Source' },
|
|
type: NounType.Thing
|
|
})
|
|
|
|
await brain.relate({
|
|
from: sourceId,
|
|
to: centralId,
|
|
type: VerbType.RelatesTo
|
|
})
|
|
|
|
// Get incoming neighbors with pagination
|
|
const incoming = await graphIndex().getNeighbors(entityInt(centralId), {
|
|
direction: 'in',
|
|
limit: 10
|
|
})
|
|
|
|
expect(incoming.length).toBeGreaterThan(0)
|
|
})
|
|
})
|
|
|
|
describe('getVerbIdsBySource() Pagination', () => {
|
|
it('should return all verb ints without pagination and resolve them back to ids', async () => {
|
|
const verbInts: bigint[] = await graphIndex().getVerbIdsBySource(entityInt(centralId))
|
|
|
|
// Should return all 50 verb ints
|
|
expect(verbInts).toHaveLength(50)
|
|
|
|
// Every int must resolve back to a verb-id string
|
|
const verbIds: (string | null)[] = await graphIndex().verbIntsToIds(verbInts)
|
|
expect(verbIds).toHaveLength(50)
|
|
expect(verbIds.every((id) => typeof id === 'string')).toBe(true)
|
|
})
|
|
|
|
it('should paginate verb ints with limit', async () => {
|
|
const page1 = await graphIndex().getVerbIdsBySource(entityInt(centralId), { limit: 10 })
|
|
|
|
expect(page1).toHaveLength(10)
|
|
})
|
|
|
|
it('should paginate verb ints with offset', async () => {
|
|
const all = await graphIndex().getVerbIdsBySource(entityInt(centralId))
|
|
const offsetResults = await graphIndex().getVerbIdsBySource(entityInt(centralId), { offset: 10 })
|
|
|
|
expect(offsetResults).toHaveLength(all.length - 10)
|
|
})
|
|
|
|
it('should paginate verb ints with limit and offset', async () => {
|
|
const central = entityInt(centralId)
|
|
const page1: bigint[] = await graphIndex().getVerbIdsBySource(central, { limit: 10, offset: 0 })
|
|
const page2: bigint[] = await graphIndex().getVerbIdsBySource(central, { limit: 10, offset: 10 })
|
|
const page3: bigint[] = await graphIndex().getVerbIdsBySource(central, { limit: 10, offset: 20 })
|
|
|
|
// Each page should have 10 results
|
|
expect(page1).toHaveLength(10)
|
|
expect(page2).toHaveLength(10)
|
|
expect(page3).toHaveLength(10)
|
|
|
|
// Pages should not overlap
|
|
const combined = [...page1, ...page2, ...page3]
|
|
const unique = new Set(combined)
|
|
expect(unique.size).toBe(30) // All unique
|
|
})
|
|
|
|
it('should handle pagination edge cases for verb ints', async () => {
|
|
// Offset beyond total
|
|
const beyondTotal = await graphIndex().getVerbIdsBySource(entityInt(centralId), { offset: 100 })
|
|
expect(beyondTotal).toHaveLength(0)
|
|
|
|
// Limit = 0
|
|
const zeroLimit = await graphIndex().getVerbIdsBySource(entityInt(centralId), { limit: 0 })
|
|
expect(zeroLimit).toHaveLength(0)
|
|
})
|
|
})
|
|
|
|
describe('getVerbIdsByTarget() Pagination', () => {
|
|
it('should return all verb ints targeting an entity', async () => {
|
|
// Pick a neighbor that's a target of relationships
|
|
const targetId = neighborIds[0]
|
|
const verbInts = await graphIndex().getVerbIdsByTarget(entityInt(targetId))
|
|
|
|
// Should have at least 1 (the relationship from central)
|
|
expect(verbInts.length).toBeGreaterThanOrEqual(1)
|
|
})
|
|
|
|
it('should paginate verb ints by target with limit', async () => {
|
|
// Create entity with many incoming relationships
|
|
const popularTarget = await brain.add({
|
|
data: { name: 'Popular Target' },
|
|
type: NounType.Thing
|
|
})
|
|
|
|
// Create 30 relationships pointing to it
|
|
for (let i = 0; i < 30; i++) {
|
|
const sourceId = await brain.add({
|
|
data: { name: `Source ${i}` },
|
|
type: NounType.Thing
|
|
})
|
|
await brain.relate({
|
|
from: sourceId,
|
|
to: popularTarget,
|
|
type: VerbType.RelatesTo
|
|
})
|
|
}
|
|
|
|
// Paginate
|
|
const target = entityInt(popularTarget)
|
|
const page1: bigint[] = await graphIndex().getVerbIdsByTarget(target, { limit: 10 })
|
|
const page2: bigint[] = await graphIndex().getVerbIdsByTarget(target, { limit: 10, offset: 10 })
|
|
|
|
expect(page1).toHaveLength(10)
|
|
expect(page2).toHaveLength(10)
|
|
|
|
// No overlap
|
|
const overlap = page1.filter((id) => page2.includes(id))
|
|
expect(overlap).toHaveLength(0)
|
|
})
|
|
})
|
|
|
|
describe('Performance with Pagination', () => {
|
|
it('should maintain sub-5ms performance with pagination', async () => {
|
|
const central = entityInt(centralId)
|
|
|
|
// Multiple paginated queries should be fast
|
|
const startTime = performance.now()
|
|
|
|
await graphIndex().getNeighbors(central, { limit: 10, offset: 0 })
|
|
await graphIndex().getNeighbors(central, { limit: 10, offset: 10 })
|
|
await graphIndex().getNeighbors(central, { limit: 10, offset: 20 })
|
|
|
|
const elapsed = performance.now() - startTime
|
|
|
|
// 3 paginated queries should complete in < 15ms (< 5ms each)
|
|
expect(elapsed).toBeLessThan(15)
|
|
})
|
|
})
|
|
|
|
describe('Real-World Use Cases', () => {
|
|
it('should efficiently paginate through high-degree node', async () => {
|
|
// Simulate popular entity with 100+ relationships
|
|
const hub = await brain.add({
|
|
data: { name: 'Popular Hub' },
|
|
type: NounType.Thing
|
|
})
|
|
|
|
// Create 100 relationships
|
|
const targetIds: string[] = []
|
|
for (let i = 0; i < 100; i++) {
|
|
const targetId = await brain.add({
|
|
data: { name: `Target ${i}` },
|
|
type: NounType.Thing
|
|
})
|
|
targetIds.push(targetId)
|
|
await brain.relate({
|
|
from: hub,
|
|
to: targetId,
|
|
type: VerbType.RelatesTo
|
|
})
|
|
}
|
|
|
|
// Paginate in chunks of 25
|
|
const hubInt = entityInt(hub)
|
|
const chunks: bigint[][] = []
|
|
for (let offset = 0; offset < 100; offset += 25) {
|
|
const chunk = await graphIndex().getNeighbors(hubInt, {
|
|
direction: 'out',
|
|
limit: 25,
|
|
offset
|
|
})
|
|
chunks.push(chunk)
|
|
}
|
|
|
|
// Should have 4 chunks
|
|
expect(chunks).toHaveLength(4)
|
|
|
|
// Each chunk should have 25 items
|
|
chunks.forEach(chunk => {
|
|
expect(chunk).toHaveLength(25)
|
|
})
|
|
|
|
// All chunks combined should equal total
|
|
const allNeighbors = chunks.flat()
|
|
expect(allNeighbors).toHaveLength(100)
|
|
|
|
// No duplicates
|
|
const uniqueNeighbors = new Set(allNeighbors)
|
|
expect(uniqueNeighbors.size).toBe(100)
|
|
})
|
|
})
|
|
})
|