API pagination: offset, cursor va keyset sahifalash, Link sarlavhasi

$ curl -i $A/vazifalar?limit=2&offset=0&jami=true&fields=matn
HTTP/1.1 200 OK
Link: </vazifalar?limit=2&jami=true&fields=matn&offset=2>; rel="next"

{"vazifalar":[{"id":1,"matn":"Non olish #uy"},
  {"id":2,"matn":"Hisobot yozish #ish"}],
  "sahifa":{"limit":2,"offset":0,"jami":5}}

let keyingiId = 31;
const royxat = Array.from({ length: 30 }, (_, i) => ({ id: i + 1 }));
const tartiblangan = () => [...royxat].sort((a, b) => b.id - a.id);
const qosh = (n) => {
  for (let i = 0; i < n; i++) royxat.push({ id: keyingiId++ });
};

function offsetSahifa(offset, limit) {
  return tartiblangan().slice(offset, offset + limit);
}
// keyset: oxirgi ko'rilgan id dan QAT'IY keyingilar
// (kamayish tartibi)
function kursorSahifa(oxirgiId, limit) {
  const qolgan = oxirgiId === undefined
    ? tartiblangan()
    : tartiblangan().filter((v) => v.id < oxirgiId);
  return qolgan.slice(0, limit);
}

const korildi = { offset: [], kursor: [] };
let oxirgi;
for (let s = 0; s < 3; s++) {
  korildi.offset.push(...offsetSahifa(s * 5, 5).map((v) => v.id));
  const sahifa = kursorSahifa(oxirgi, 5);
  korildi.kursor.push(...sahifa.map((v) => v.id));
  oxirgi = sahifa.at(-1).id;
  qosh(2); // foydalanuvchi o'qiyotganda yangi vazifalar
}
for (const [usul, idlar] of Object.entries(korildi)) {
  const takror = idlar.length - new Set(idlar).size;
  console.log(`${usul}: ${idlar.join(" ")} | takror ${takror}`);
}

offset: 30 29 28 27 26 27 26 25 24 23 24 23 22 21 20 | takror 4
kursor: 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 | takror 0

const keyin = sorov.sahifa.keyin;
// Keyset: kursordan qat'iy keyingi birinchi qator
// (kursor qatori o'chirilgan bo'lsa ham ishlaydi)
const i = mos.findIndex(
  (v) => tartibda(kalitQiymatlari(v, k), keyin, k) > 0);
boshi = i === -1 ? mos.length : i;

const b64url = (s) => btoa(String.fromCharCode(
  ...new TextEncoder().encode(s)))
  .replaceAll("+", "-").replaceAll("/", "_").replace(/=+$/, "");
const b64urlOch = (s) => new TextDecoder().decode(Uint8Array.from(
  atob(s.replaceAll("-", "+").replaceAll("_", "/")),
  (c) => c.charCodeAt(0)));

const kursorYoz = (v, imzo) => b64url(JSON.stringify({ v, i: imzo }));
function kursorOqi(kursor, imzo) {
  try {
    const ichki = JSON.parse(b64urlOch(kursor));
    const yaroqli = ichki.i === imzo && Array.isArray(ichki.v);
    return yaroqli ? ichki.v : null;
  } catch {
    return null; // buzuq kursor
  }
}

const imzo = JSON.stringify([[], {}]); // saralash va filtr
const k = kursorYoz([2], imzo);
console.log(k);
console.log(kursorOqi(k, imzo));
console.log(kursorOqi(k, JSON.stringify([[{ maydon: "matn" }], {}])));
console.log(kursorOqi("buzuq", imzo));

eyJ2IjpbMl0sImkiOiJbW10se31dIn0
[ 2 ]
null
null

$ curl -i $A/vazifalar?limit=2&fields=matn
Link: </vazifalar?limit=2&fields=matn&cursor=eyJ2IjpbMl0sImkiOiJbW10se31dIn0>; rel="next"
{"vazifalar":[{"id":1,…},{"id":2,…}],
  "sahifa":{"limit":2,"keyingi":"eyJ2IjpbMl0sImkiOiJbW10se31dIn0"}}
$ curl $A/vazifalar?limit=2&sort=matn&cursor=eyJ2IjpbMl0sImkiOiJbW10se31dIn0
{"xato":"cursor yaroqsiz yoki boshqa saralash/filtr uchun"}

{"v":["2026-10-24T00:00:21.000Z",21],"i":"[[{\"maydon\":\"yaratildi\"…

function keyingiHavola(
  req: Request, ozgartir: Record<string, string>,
): string {
  const p = new URLSearchParams(req.originalUrl.split("?")[1] ?? "");
  p.delete("offset");
  p.delete("cursor");
  for (const [k, v] of Object.entries(ozgartir)) p.set(k, v);
  return `${req.baseUrl}?${p.toString()}`;
}
// …
if (keyingi !== undefined) res.links({ next: keyingi });

// kursor.ts — shaffof bo'lmagan (opaque) kursor: base64url(JSON).
// Mijoz ichini o'qimasligi, faqat qaytarib yuborishi kerak.
// Imzo (saralash + filtr) kursor bilan birga — boshqa saralash
// yoki filtr bilan ishlatilsa rad etiladi
import type { KursorQiymati } from "../vazifalar/ombor.ts";

type Ichki = { v: KursorQiymati; i: string };

export function kursorYoz(
  qiymatlar: KursorQiymati, imzo: string,
): string {
  return Buffer.from(
    JSON.stringify({ v: qiymatlar, i: imzo } satisfies Ichki),
  ).toString("base64url");
}

function qiymatmi(x: unknown): x is string | number | boolean {
  return typeof x === "string" || typeof x === "number" ||
    typeof x === "boolean";
}

/** @returns undefined — kursor buzilgan yoki boshqa so'rovniki */
export function kursorOqi(
  kursor: string, imzo: string,
): KursorQiymati | undefined {
  if (!/^[\w-]{1,1000}$/.test(kursor)) return undefined;
  let ichki: unknown;
  try {
    ichki = JSON.parse(
      Buffer.from(kursor, "base64url").toString("utf8"));
  } catch {
    return undefined;
  }
  if (typeof ichki !== "object" || ichki === null ||
    !("v" in ichki) || !("i" in ichki)) return undefined;
  const { v, i } = ichki;
  if (i !== imzo || !Array.isArray(v) || !v.every(qiymatmi)) {
    return undefined;
  }
  return v;
}

/** Keyset kursori: oxirgi qatorning saralash kalitlari qiymatlari
 *  (saralash tartibida) + id */
export type KursorQiymati = (string | number | boolean)[];

export type Sahifalash =
  | { tur: "offset"; offset: number }
  | { tur: "kursor"; keyin?: KursorQiymati };

export type RoyxatNatija = {
  vazifalar: Vazifa[];
  /** keyingi sahifa bormi — kursor rejimida keyingi kursor
   *  qiymatlari */
  keyingi?: KursorQiymati;
  borKeyingi: boolean;
  jami?: number;
};

function solishtir(a: string | number | boolean,
  b: string | number | boolean): number {
  // Satrlar — kod nuqtasi bo'yicha (localeCompare emas):
  // deterministik. Postgres collation boshqacha tartiblashi
  // mumkin — 26-qismda kursor DB tartibi bilan mos bo'lishi kerak
  if (a === b) return 0;
  return a < b ? -1 : 1;
}

function kalitQiymatlari(v: Vazifa,
  k: readonly Saralash[]): KursorQiymati {
  return k.map((s) => v[s.maydon]);
}

/** a kalitlari b dan saralash tartibida oldinmi (<0), tengmi (0),
 *  keyinmi (>0) */
function tartibda(a: KursorQiymati, b: KursorQiymati,
  k: readonly Saralash[]): number {
  for (const [i, s] of k.entries()) {
    const x = a[i];
    const y = b[i];
    if (x === undefined || y === undefined) return 0;
    const n = solishtir(x, y);
    if (n !== 0) return s.kamayish ? -n : n;
  }
  return 0;
}

export function sahifala(hammasi: readonly Vazifa[],
  sorov: RoyxatSorovi): RoyxatNatija {
  const k = kalitlar(sorov.saralash);
  const mos = filtrla(hammasi, sorov.filtr).sort((a, b) =>
    tartibda(kalitQiymatlari(a, k), kalitQiymatlari(b, k), k));
  let boshi = 0;
  if (sorov.sahifa.tur === "offset") {
    boshi = sorov.sahifa.offset;
  } else if (sorov.sahifa.keyin !== undefined) {
    const keyin = sorov.sahifa.keyin;
    // Keyset: kursordan qat'iy keyingi birinchi qator
    // (kursor qatori o'chirilgan bo'lsa ham ishlaydi)
    const i = mos.findIndex(
      (v) => tartibda(kalitQiymatlari(v, k), keyin, k) > 0);
    boshi = i === -1 ? mos.length : i;
  }
  const sahifa = mos.slice(boshi, boshi + sorov.limit);
  const borKeyingi = boshi + sorov.limit < mos.length;
  const oxirgi = sahifa.at(-1);
  const natija: RoyxatNatija = {
    vazifalar: structuredClone(sahifa), borKeyingi };
  if (borKeyingi && oxirgi !== undefined) {
    natija.keyingi = kalitQiymatlari(oxirgi, k);
  }
  if (sorov.jami === true) natija.jami = mos.length;
  return natija;
}

export const SUKUT_LIMIT = 20;
export const MAKS_LIMIT = 100;
export const MAKS_OFFSET = 10_000;
// … royxatSorovi() ichida, filtr va saralashdan keyin:
  const limit = butun(q, "limit", 1, MAKS_LIMIT) ?? SUKUT_LIMIT;
  const offset = butun(q, "offset", 0, MAKS_OFFSET);
  const kursor = bitta(q, "cursor");
  // Imzo — kursor boshqa filtr/saralash bilan qayta ishlatilmasin
  const imzo = JSON.stringify([saralash, filtr]);
  let sahifa: RoyxatSorovi["sahifa"] =
    { tur: "offset", offset: offset ?? 0 };
  if (kursor !== undefined) {
    if (offset !== undefined) {
      throw new HttpXato(400, "offset va cursor birga berilmaydi");
    }
    const keyin = kursorOqi(kursor, imzo);
    if (keyin === undefined) {
      throw new HttpXato(400,
        "cursor yaroqsiz yoki boshqa saralash/filtr uchun");
    }
    sahifa = { tur: "kursor", keyin };
  } else if (offset === undefined) {
    // Parametrsiz — kursor rejimi (birinchi sahifa);
    // offset faqat aniq so'ralganda
    sahifa = { tur: "kursor" };
  }

.get(async (req, res) => {
  const { sorov, maydonlar, imzo } = royxatSorovi(req.query);
  const natija = await xizmat.royxat(sorov);
  const sahifa: Record<string, unknown> = { limit: sorov.limit };
  let keyingi: string | undefined;
  if (sorov.sahifa.tur === "offset") {
    sahifa.offset = sorov.sahifa.offset;
    if (natija.borKeyingi) {
      keyingi = keyingiHavola(req,
        { offset: String(sorov.sahifa.offset + sorov.limit) });
    }
  } else {
    const kursor = natija.keyingi && kursorYoz(natija.keyingi, imzo);
    sahifa.keyingi = kursor ?? null;
    if (kursor !== undefined) {
      keyingi = keyingiHavola(req, { cursor: kursor });
    }
  }
  if (natija.jami !== undefined) sahifa.jami = natija.jami;
  // Link sarlavhasi (RFC 8288) — mijoz URL'ni o'zi yig'masin
  if (keyingi !== undefined) res.links({ next: keyingi });
  res.json({
    vazifalar: natija.vazifalar.map((v) => proyeksiya(v, maydonlar)),
    sahifa,
  });
})

// xotira-ombor.ts — VazifaOmbori ning xotiradagi amalga oshirilishi
// (jarayon to'xtasa — ma'lumot yo'qoladi)
import { teglariniOl } from "./vazifa.ts";
import type { Vazifa, VazifaOzgarishi, YangiVazifa } from "./vazifa.ts";
import { filtrla, sahifala } from "./royxat-mantiq.ts";
import type { Filtr, RoyxatNatija, RoyxatSorovi, TegSoni,
  VazifaOmbori } from "./ombor.ts";

export class XotiraOmbori implements VazifaOmbori {
  readonly #vazifalar = new Map<number, Vazifa>();
  #keyingiId = 1;
  readonly #soat: () => Date;

  constructor(soat: () => Date = () => new Date()) {
    this.#soat = soat;
  }

  // structuredClone (sahifala ichida ham): chaqiruvchi qaytgan
  // obyektni o'zgartirsa ombordagi nusxa buzilmaydi
  royxat(sorov: RoyxatSorovi): Promise<RoyxatNatija> {
    return Promise.resolve(
      sahifala([...this.#vazifalar.values()], sorov));
  }

  soni(filtr: Filtr): Promise<number> {
    return Promise.resolve(
      filtrla([...this.#vazifalar.values()], filtr).length);
  }

  ol(id: number): Promise<Vazifa | undefined> {
    const v = this.#vazifalar.get(id);
    return Promise.resolve(v && structuredClone(v));
  }

  yarat(yangi: YangiVazifa): Promise<Vazifa> {
    const hozir = this.#soat().toISOString();
    const v: Vazifa = {
      id: this.#keyingiId++,
      matn: yangi.matn,
      bajarildi: yangi.bajarildi ?? false,
      teglar: teglariniOl(yangi.matn),
      yaratildi: hozir,
      yangilandi: hozir,
    };
    this.#vazifalar.set(v.id, v);
    return Promise.resolve(structuredClone(v));
  }

  yangila(id: number,
    ozgarish: VazifaOzgarishi): Promise<Vazifa | undefined> {
    const v = this.#vazifalar.get(id);
    if (!v) return Promise.resolve(undefined);
    if (ozgarish.matn !== undefined) {
      v.matn = ozgarish.matn;
      v.teglar = teglariniOl(ozgarish.matn);
    }
    if (ozgarish.bajarildi !== undefined) {
      v.bajarildi = ozgarish.bajarildi;
    }
    v.yangilandi = this.#soat().toISOString();
    return Promise.resolve(structuredClone(v));
  }

  ochir(id: number): Promise<boolean> {
    return Promise.resolve(this.#vazifalar.delete(id));
  }

  teglar(): Promise<TegSoni[]> {
    const sanoq = new Map<string, number>();
    for (const v of this.#vazifalar.values()) {
      for (const t of v.teglar) sanoq.set(t, (sanoq.get(t) ?? 0) + 1);
    }
    return Promise.resolve(
      [...sanoq].map(([teg, soni]) => ({ teg, soni }))
        .sort((a, b) => b.soni - a.soni || (a.teg < b.teg ? -1 : 1)),
    );
  }
}

// xizmat.ts — biznes qoidalari (service qatlami): HTTP'ni bilmaydi,
// omborni interfeys orqali oladi
import { HttpXato } from "../umumiy/http-xato.ts";
import type { RoyxatNatija, RoyxatSorovi, TegSoni, VazifaOmbori }
  from "./ombor.ts";
import type { ToliqVazifa, Vazifa, VazifaOzgarishi, YangiVazifa }
  from "./vazifa.ts";

export const MAKS_VAZIFA = 1000;

// DI framework'siz: factory funksiya bog'liqlikni parametr sifatida
// oladi (testda — boshqa ombor)
export function vazifaXizmati(ombor: VazifaOmbori) {
  async function topilsin(id: number): Promise<Vazifa> {
    const v = await ombor.ol(id);
    if (!v) throw new HttpXato(404, `Vazifa ${String(id)} topilmadi`);
    return v;
  }
  async function yangila(id: number,
    ozgarish: VazifaOzgarishi): Promise<Vazifa> {
    const v = await ombor.yangila(id, ozgarish);
    if (!v) throw new HttpXato(404, `Vazifa ${String(id)} topilmadi`);
    return v;
  }
  return {
    royxat: (sorov: RoyxatSorovi): Promise<RoyxatNatija> =>
      ombor.royxat(sorov),
    teglar: (): Promise<TegSoni[]> => ombor.teglar(),
    ol: topilsin,
    async yarat(yangi: YangiVazifa): Promise<Vazifa> {
      if ((await ombor.soni({})) >= MAKS_VAZIFA) {
        throw new HttpXato(409,
          `Ro'yxat to'lgan (${String(MAKS_VAZIFA)})`);
      }
      return ombor.yarat(yangi);
    },
    yangila,
    /** PUT: butun resurs (matn va bajarildi) almashtiriladi —
     *  idempotent */
    almashtir: (id: number, toliq: ToliqVazifa): Promise<Vazifa> =>
      yangila(id, toliq),
    async ochir(id: number): Promise<void> {
      if (!(await ombor.ochir(id))) {
        throw new HttpXato(404, `Vazifa ${String(id)} topilmadi`);
      }
    },
  };
}

export type VazifaXizmati = ReturnType<typeof vazifaXizmati>;

test("kursor: hammasi bir martadan", async () => {
  const korildi: number[] = [];
  let yol = "/vazifalar?limit=2&sort=-yaratildi";
  for (let i = 0; i < 10; i++) {
    const r = await ol(yol);
    korildi.push(...r.tana.vazifalar.map((v) => v.id ?? 0));
    if (r.tana.sahifa.keyingi === null) break;
    yol = "/vazifalar?limit=2&sort=-yaratildi" +
      `&cursor=${String(r.tana.sahifa.keyingi)}`;
  }
  assert.deepEqual([...korildi].sort((a, b) => a - b),
    [1, 2, 3, 4, 5, 6]);
});

test("sahifala: kursor qatori o'chirilsa ham davom etadi", () => {
  // … 1..5 vazifa, birinchi sahifa → keyingi [2]; 2 o'chiriladi
  assert.deepEqual(s2.vazifalar.map((x) => x.id), [3, 4]);
  // offset esa 3 ni o'tkazib yubordi:
  assert.deepEqual(o2.vazifalar.map((x) => x.id), [4, 5]);
});

npm run check
git add -A
git commit -m "REST: PUT/PATCH (merge-patch), filtr, saralash, fields, offset va kursor sahifalash, Link, /teglar"