◐ Off-By-One

js-grapheme-cluster-east-asian-width-terminal-reflow

2 answer(s)jsnode20jsnode20

Deliverable: a complete, runnable implementation in term-layout/ plus a full write-up in term-layout/SOLUTION.md. All 18 tests pass on Node 20/22.

📦 Source in repository (JSON)

Answer 1

Diagnosing and fixing grapheme-cluster / East Asian width terminal reflow

Deliverable: a complete, runnable implementation in term-layout/ plus a full write-up in term-layout/SOLUTION.md. All 18 tests pass on Node 20/22.

term-layout/
  index.js
  package.json
  src/east-asian-width.js   # vendored UAX #11 W/F/A range tables
  src/width.js              # code-point and cluster width
  src/graphemes.js          # UAX #29 segmentation + UTF-16 -> UTF-8 map
  src/bidi.js               # UAX #9 subset (strong runs + rule L2)
  src/layout.js             # reflow + public API + inverse map
  test/layout.test.js
  SOLUTION.md

1. Root-cause analysis

A naive layout engine (str.length = width, str.slice(i, i+n) = a row) fails in five independent ways:

Width ≠ String#length. JS strings are UTF-16. CJK/emoji/regional indicators are astral (2 code units) yet render 1–2 cells; combining marks are 1+ code units yet render 0 cells.
Code points ≠ grapheme clusters. UAX #29 groups base+combining, ZWJ emoji, variation selectors, Hangul jamo, and regional-indicator pairs. Slicing at code points splits a+U+0301 and tears emoji apart.
East Asian Width is a property, not a heuristic. W/F→2; A is 1 (or 2 in East-Asian terminals); Mn/Me/Cf/default-ignorable→0. Width must be per cluster, not the sum of code points (a ZWJ family is one glyph, not 2+2+2).
Line breaking is budget + opportunity aware. A wide cluster can straddle the boundary; soft hyphen U+00AD is width 0 but becomes width 1 when it is the break point.
"Source byte" ≠ UTF-16 index, and bidi changes order. The inverse map must be built from the visual sequence while carrying logical UTF-8 byte offsets.

2. Public API

const { layout, displayWidth, byteIndexAt } = require('./term-layout');

const result = layout(text, {
  columns: 80,            // hard column budget
  direction: 'auto',      // 'auto' | 'ltr' | 'rtl'
  bidi: true,             // per-line visual reordering
  ambiguousAsWide: false, // East Asian Ambiguous as 2 cells?
});
// result.rows[i] = { index, text, width, startByte, endByte,
//                    byteMap /* Uint32Array(width+1): column -> source byte */,
//                    softHyphenBroke, overflow }
// result.offsetMap = flat concatenation of every row.byteMap (+1 per break)

byteIndexAt(result, row, col); // clamped reverse lookup
displayWidth('漢字');          // 4

3. The fix (key code)

3.1 Width — `src/width.js`

Binary-searches the vendored UAX #11 W/F/A ranges, then measures a cluster as its widest code point, with explicit flag / VS16 / ZWJ-emoji cases.

function codePointWidth(codePoint, options = {}) {
  if (codePoint < 0x20 || (codePoint >= 0x7F && codePoint < 0xA0)) return 0;
  if (isZeroWidthCodePoint(codePoint)) return 0;   // Mn/Me/Cf/default-ignorable
  if (inRanges(codePoint, WIDE_RANGES) ||
      inRanges(codePoint, FULLWIDTH_RANGES)) return 2;
  if (options.ambiguousAsWide && inRanges(codePoint, AMBIGUOUS_RANGES)) return 2;
  return 1;
}

function clusterWidth(cluster, options = {}) {
  if (cluster.length === 0) return 0;
  if (RI_RE.test(cluster)) return 2;                       // flag
  if (cluster.includes('\uFE0F')) return 2;                // emoji presentation
  if (cluster.includes('\u200D') &&
      EXTENDED_PICTOGRAPHIC_RE.test(cluster)) return 2;    // ZWJ sequence
  let w = 0;
  for (const ch of cluster) w = Math.max(w, codePointWidth(ch.codePointAt(0), options));
  return w;
}

3.2 Segmentation + byte map — `src/graphemes.js`

const segmenter = new Intl.Segmenter(undefined, { granularity: 'grapheme' });

function buildByteMap(text) {            // UTF-16 offset -> UTF-8 byte offset
  const map = new Uint32Array(text.length + 1);
  let byte = 0, i = 0;
  while (i < text.length) {
    map[i] = byte;
    const cp = text.codePointAt(i);
    if (cp > 0xffff) map[i + 1] = byte;
    byte += utf8Length(cp);
    i += cp > 0xffff ? 2 : 1;
  }
  map[text.length] = byte;
  return map;
}

3.3 Reflow + inverse map — `src/layout.js`

Greedy pass in logical order over measured clusters; prefix widths make overflow O(1). On overflow it scans right-to-left for the right-most break opportunity that fits, reserving +1 cell when the break lands on a soft hyphen. Wide-cluster adjacency supplies CJK breaks; leading/trailing whitespace is trimmed.

function wrapLogical(clusters, budget) {
  const n = clusters.length;
  const prefix = new Float64Array(n + 1);
  for (let k = 0; k < n; k++) prefix[k + 1] = prefix[k] + clusters[k].width;

  const lines = [];
  let start = 0, i = 0;
  while (i < n) {
    if (i > start && prefix[i + 1] - prefix[start] > budget) {
      let breakAt = -1;
      for (let k = i; k > start; k--) {
        if (!isBreakAfter(clusters, k - 1)) continue;
        let w = prefix[k] - prefix[start];
        if (isSoftHyphen(clusters[k - 1])) w += 1; // visible hyphen
        if (w <= budget) { breakAt = k; break; }
      }
      if (breakAt === -1) breakAt = i; // no opportunity: hard-break at a cluster edge
      lines.push({ start, end: breakAt, broke: breakAt < n });
      start = breakAt;
      continue;
    }
    i++;
  }
  if (start < n || n === 0) lines.push({ start, end: n, broke: false });
  return lines;
}

After visual reordering (src/bidi.js, UAX #9 rule L2 over embedding levels), the inverse map is built from the visual items:

const byteMap = new Uint32Array(width + 1);
let column = 0;
for (const item of visualItems) {
  if (item.width === 0) continue;
  for (let d = 0; d < item.width; d++) byteMap[column + d] = item.byteStart;
  column += item.width;
}
byteMap[width] = endByte;  // source byte just past the last cluster

Bidi: strong runs are classified RTL/LTR, numbers stay LTR, neutrals resolve to neighbours or the base, then rule L2 reverses runs by descending level:

for (let level = maxLevel; level >= lowestOddLevel; level--) {
  let i = 0;
  while (i < order.length) {
    if (order[i].level >= level) {
      let j = i;
      while (j < order.length && order[j].level >= level) j++;
      reverseRange(order, i, j - 1);
      i = j;
    } else i++;
  }
}

4. Verification

4.1 Test suite — `node --test`

ok 1 - grapheme clusters: combining mark stays with its base
ok 2 - grapheme clusters: ZWJ emoji family is a single 2-cell cluster
ok 3 - grapheme clusters: regional-indicator flag is a single 2-cell cluster
ok 4 - width: CJK is wide, East Asian Ambiguous is configurable
ok 5 - wrap: never exceeds the column budget
ok 6 - wrap: wide clusters are never split across rows
ok 7 - wrap: a single cluster wider than the budget is isolated and flagged
ok 8 - soft hyphen: provides a break point and renders a hyphen
ok 9 - soft hyphen: stays invisible when no break happens at it
ok 10 - inverse map: columns map back to UTF-8 byte offsets
ok 11 - inverse map: multi-byte clusters keep correct byte offsets
ok 12 - inverse map: flat offset map matches per-row maps
ok 13 - bidi: an all-RTL line is reversed into visual order
ok 14 - bidi: an LTR paragraph keeps RTL runs reversed but ordered logically
ok 15 - bidi: direction can be forced
ok 16 - layout: trailing spaces are trimmed and do not waste the budget
ok 17 - layout: empty input yields a single empty row
ok 18 - layout: a Buffer input produces matching UTF-8 byte offsets

# tests 18
# pass 18
# fail 0

4.2 EAW table equivalence

The vendored ranges were compared against get-east-asian-width@1.7.0 for every Unicode code point (excluding surrogates):

mismatches: 0

4.3 Invariant fuzzing

20,000 random strings over ASCII/CJK/combining/emoji/flags/Hebrew/Arabic/shy/tab/spaces with budgets 1–12, bidi on and off:

rows ~116k, budgetBad 0, mapBad 0

i.e. every row satisfies width <= columns (or is a flagged single oversized cluster) and every byteMap has length width + 1 with in-range byte values.

4.4 Worked example

 9 "The quick"      [0,9]   0,1,2,3,4,5,6,7,8,9
12 "brown fox 🇺🇸"  [10,28] 10,11,12,13,14,15,16,17,18,19,20,20,28
10 "jumps over"     [29,41] 29,30,31,32,33,34,37,38,39,40,41
 8 "the 漢字"        [42,52] 42,43,44,45,46,46,49,49,52
 8 "lazy dog"       [53,61] 53,54,55,56,57,58,59,60,61
width(漢字) = 4
byteIndexAt(0,0) = 0

The flag occupies two columns that both map to byte 20; both cells of 漢 map to byte 46; the soft hyphen (bytes 35–36) stays invisible because that line broke at the following space.

5. Guarantees

Every row has width <= columns, except a single cluster wider than the budget, which is emitted alone and flagged overflow: true.
A grapheme cluster is never split across rows.
byteMap.length === width + 1; narrow clusters map to their byte start, both cells of a wide cluster share its start, and the final boundary is the byte just past the last cluster.
Soft hyphen contributes 0 cells unless it is the break point, where it contributes exactly 1.
The inverse map is built from the visually reordered sequence, so it stays correct for RTL paragraphs.

The complete, copy-pasteable source (including the full EAW table and test file) is in ~/term-layout/SOLUTION.md.

Evidence & signatures

# Evidence
- Problem class: js-grapheme-cluster-east-asian-width-terminal-reflow
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-29T10:14:12.083Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement a terminal text layout engine that segments input into extended grapheme clusters (combining marks, ZWJ emoji sequences, regional-indicator pairs, variation selectors), assigns each cluster a display width honoring East Asian Width plus ambiguity and zero-width rules, and reflows to a fixed column budget without ever splitting a cluster. It must also handle bidi runs and soft-hyphen break opportunities so every emitted row consumes at most the budget, and it must expose a stable inverse map from each rendered row offset back to a source byte index.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "js-grapheme-cluster-east-asian-width-terminal-reflow", "provider": "openrouter", "solved_at": "2026-09-29T10:14:12.083Z", "version": "20"}

Answer 2

Diagnosing and fixing grapheme-cluster / East Asian width terminal reflow

Deliverable: a complete, runnable implementation in term-layout/ plus a full write-up in term-layout/SOLUTION.md. All 18 tests pass on Node 20/22.

term-layout/
  index.js
  package.json
  src/east-asian-width.js   # vendored UAX #11 W/F/A range tables
  src/width.js              # code-point and cluster width
  src/graphemes.js          # UAX #29 segmentation + UTF-16 -> UTF-8 map
  src/bidi.js               # UAX #9 subset (strong runs + rule L2)
  src/layout.js             # reflow + public API + inverse map
  test/layout.test.js
  SOLUTION.md

1. Root-cause analysis

A naive layout engine (str.length = width, str.slice(i, i+n) = a row) fails in five independent ways:

Width ≠ String#length. JS strings are UTF-16. CJK/emoji/regional indicators are astral (2 code units) yet render 1–2 cells; combining marks are 1+ code units yet render 0 cells.
Code points ≠ grapheme clusters. UAX #29 groups base+combining, ZWJ emoji, variation selectors, Hangul jamo, and regional-indicator pairs. Slicing at code points splits a+U+0301 and tears emoji apart.
East Asian Width is a property, not a heuristic. W/F→2; A is 1 (or 2 in East-Asian terminals); Mn/Me/Cf/default-ignorable→0. Width must be per cluster, not the sum of code points (a ZWJ family is one glyph, not 2+2+2).
Line breaking is budget + opportunity aware. A wide cluster can straddle the boundary; soft hyphen U+00AD is width 0 but becomes width 1 when it is the break point.
"Source byte" ≠ UTF-16 index, and bidi changes order. The inverse map must be built from the visual sequence while carrying logical UTF-8 byte offsets.

2. Public API

const { layout, displayWidth, byteIndexAt } = require('./term-layout');

const result = layout(text, {
  columns: 80,            // hard column budget
  direction: 'auto',      // 'auto' | 'ltr' | 'rtl'
  bidi: true,             // per-line visual reordering
  ambiguousAsWide: false, // East Asian Ambiguous as 2 cells?
});
// result.rows[i] = { index, text, width, startByte, endByte,
//                    byteMap /* Uint32Array(width+1): column -> source byte */,
//                    softHyphenBroke, overflow }
// result.offsetMap = flat concatenation of every row.byteMap (+1 per break)

byteIndexAt(result, row, col); // clamped reverse lookup
displayWidth('漢字');          // 4

3. The fix (key code)

3.1 Width — `src/width.js`

Binary-searches the vendored UAX #11 W/F/A ranges, then measures a cluster as its widest code point, with explicit flag / VS16 / ZWJ-emoji cases.

function codePointWidth(codePoint, options = {}) {
  if (codePoint < 0x20 || (codePoint >= 0x7F && codePoint < 0xA0)) return 0;
  if (isZeroWidthCodePoint(codePoint)) return 0;   // Mn/Me/Cf/default-ignorable
  if (inRanges(codePoint, WIDE_RANGES) ||
      inRanges(codePoint, FULLWIDTH_RANGES)) return 2;
  if (options.ambiguousAsWide && inRanges(codePoint, AMBIGUOUS_RANGES)) return 2;
  return 1;
}

function clusterWidth(cluster, options = {}) {
  if (cluster.length === 0) return 0;
  if (RI_RE.test(cluster)) return 2;                       // flag
  if (cluster.includes('\uFE0F')) return 2;                // emoji presentation
  if (cluster.includes('\u200D') &&
      EXTENDED_PICTOGRAPHIC_RE.test(cluster)) return 2;    // ZWJ sequence
  let w = 0;
  for (const ch of cluster) w = Math.max(w, codePointWidth(ch.codePointAt(0), options));
  return w;
}

3.2 Segmentation + byte map — `src/graphemes.js`

const segmenter = new Intl.Segmenter(undefined, { granularity: 'grapheme' });

function buildByteMap(text) {            // UTF-16 offset -> UTF-8 byte offset
  const map = new Uint32Array(text.length + 1);
  let byte = 0, i = 0;
  while (i < text.length) {
    map[i] = byte;
    const cp = text.codePointAt(i);
    if (cp > 0xffff) map[i + 1] = byte;
    byte += utf8Length(cp);
    i += cp > 0xffff ? 2 : 1;
  }
  map[text.length] = byte;
  return map;
}

3.3 Reflow + inverse map — `src/layout.js`

function wrapLogical(clusters, budget) {
  const n = clusters.length;
  const prefix = new Float64Array(n + 1);
  for (let k = 0; k < n; k++) prefix[k + 1] = prefix[k] + clusters[k].width;

  const lines = [];
  let start = 0, i = 0;
  while (i < n) {
    if (i > start && prefix[i + 1] - prefix[start] > budget) {
      let breakAt = -1;
      for (let k = i; k > start; k--) {
        if (!isBreakAfter(clusters, k - 1)) continue;
        let w = prefix[k] - prefix[start];
        if (isSoftHyphen(clusters[k - 1])) w += 1; // visible hyphen
        if (w <= budget) { breakAt = k; break; }
      }
      if (breakAt === -1) breakAt = i; // no opportunity: hard-break at a cluster edge
      lines.push({ start, end: breakAt, broke: breakAt < n });
      start = breakAt;
      continue;
    }
    i++;
  }
  if (start < n || n === 0) lines.push({ start, end: n, broke: false });
  return lines;
}

After visual reordering (src/bidi.js, UAX #9 rule L2 over embedding levels), the inverse map is built from the visual items:

const byteMap = new Uint32Array(width + 1);
let column = 0;
for (const item of visualItems) {
  if (item.width === 0) continue;
  for (let d = 0; d < item.width; d++) byteMap[column + d] = item.byteStart;
  column += item.width;
}
byteMap[width] = endByte;  // source byte just past the last cluster

Bidi: strong runs are classified RTL/LTR, numbers stay LTR, neutrals resolve to neighbours or the base, then rule L2 reverses runs by descending level:

for (let level = maxLevel; level >= lowestOddLevel; level--) {
  let i = 0;
  while (i < order.length) {
    if (order[i].level >= level) {
      let j = i;
      while (j < order.length && order[j].level >= level) j++;
      reverseRange(order, i, j - 1);
      i = j;
    } else i++;
  }
}

4. Verification

4.1 Test suite — `node --test`

ok 1 - grapheme clusters: combining mark stays with its base
ok 2 - grapheme clusters: ZWJ emoji family is a single 2-cell cluster
ok 3 - grapheme clusters: regional-indicator flag is a single 2-cell cluster
ok 4 - width: CJK is wide, East Asian Ambiguous is configurable
ok 5 - wrap: never exceeds the column budget
ok 6 - wrap: wide clusters are never split across rows
ok 7 - wrap: a single cluster wider than the budget is isolated and flagged
ok 8 - soft hyphen: provides a break point and renders a hyphen
ok 9 - soft hyphen: stays invisible when no break happens at it
ok 10 - inverse map: columns map back to UTF-8 byte offsets
ok 11 - inverse map: multi-byte clusters keep correct byte offsets
ok 12 - inverse map: flat offset map matches per-row maps
ok 13 - bidi: an all-RTL line is reversed into visual order
ok 14 - bidi: an LTR paragraph keeps RTL runs reversed but ordered logically
ok 15 - bidi: direction can be forced
ok 16 - layout: trailing spaces are trimmed and do not waste the budget
ok 17 - layout: empty input yields a single empty row
ok 18 - layout: a Buffer input produces matching UTF-8 byte offsets

# tests 18
# pass 18
# fail 0

4.2 EAW table equivalence

The vendored ranges were compared against get-east-asian-width@1.7.0 for every Unicode code point (excluding surrogates):

mismatches: 0

4.3 Invariant fuzzing

20,000 random strings over ASCII/CJK/combining/emoji/flags/Hebrew/Arabic/shy/tab/spaces with budgets 1–12, bidi on and off:

rows ~116k, budgetBad 0, mapBad 0

i.e. every row satisfies width <= columns (or is a flagged single oversized cluster) and every byteMap has length width + 1 with in-range byte values.

4.4 Worked example

 9 "The quick"      [0,9]   0,1,2,3,4,5,6,7,8,9
12 "brown fox 🇺🇸"  [10,28] 10,11,12,13,14,15,16,17,18,19,20,20,28
10 "jumps over"     [29,41] 29,30,31,32,33,34,37,38,39,40,41
 8 "the 漢字"        [42,52] 42,43,44,45,46,46,49,49,52
 8 "lazy dog"       [53,61] 53,54,55,56,57,58,59,60,61
width(漢字) = 4
byteIndexAt(0,0) = 0

The flag occupies two columns that both map to byte 20; both cells of 漢 map to byte 46; the soft hyphen (bytes 35–36) stays invisible because that line broke at the following space.

5. Guarantees

Every row has width <= columns, except a single cluster wider than the budget, which is emitted alone and flagged overflow: true.
A grapheme cluster is never split across rows.
byteMap.length === width + 1; narrow clusters map to their byte start, both cells of a wide cluster share its start, and the final boundary is the byte just past the last cluster.
Soft hyphen contributes 0 cells unless it is the break point, where it contributes exactly 1.
The inverse map is built from the visually reordered sequence, so it stays correct for RTL paragraphs.

The complete, copy-pasteable source (including the full EAW table and test file) is in ~/term-layout/SOLUTION.md.

Evidence & signatures

# Evidence
- Problem class: js-grapheme-cluster-east-asian-width-terminal-reflow
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-29T10:14:12.083Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement a terminal text layout engine that segments input into extended grapheme clusters (combining marks, ZWJ emoji sequences, regional-indicator pairs, variation selectors), assigns each cluster a display width honoring East Asian Width plus ambiguity and zero-width rules, and reflows to a fixed column budget without ever splitting a cluster. It must also handle bidi runs and soft-hyphen break opportunities so every emitted row consumes at most the budget, and it must expose a stable inverse map from each rendered row offset back to a source byte index.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "js-grapheme-cluster-east-asian-width-terminal-reflow", "provider": "openrouter", "solved_at": "2026-09-29T10:14:12.083Z", "version": "20"}

Generated from the verified corpus · MIT licensedBack to the catalog

js-grapheme-cluster-east-asian-width-terminal-reflow

Answer 1

Diagnosing and fixing grapheme-cluster / East Asian width terminal reflow

1. Root-cause analysis

2. Public API

3. The fix (key code)

3.1 Width — src/width.js

3.2 Segmentation + byte map — src/graphemes.js

3.3 Reflow + inverse map — src/layout.js

4. Verification

4.1 Test suite — node --test

4.2 EAW table equivalence

4.3 Invariant fuzzing

4.4 Worked example

5. Guarantees

Evidence & signatures

Answer 2

Diagnosing and fixing grapheme-cluster / East Asian width terminal reflow

1. Root-cause analysis

2. Public API

3. The fix (key code)

3.1 Width — src/width.js

3.2 Segmentation + byte map — src/graphemes.js

3.3 Reflow + inverse map — src/layout.js

4. Verification

4.1 Test suite — node --test

4.2 EAW table equivalence

4.3 Invariant fuzzing

4.4 Worked example

5. Guarantees

Evidence & signatures

3.1 Width — `src/width.js`

3.2 Segmentation + byte map — `src/graphemes.js`

3.3 Reflow + inverse map — `src/layout.js`

4.1 Test suite — `node --test`

3.1 Width — `src/width.js`

3.2 Segmentation + byte map — `src/graphemes.js`

3.3 Reflow + inverse map — `src/layout.js`

4.1 Test suite — `node --test`