^ ^                 ^ ^
=(o.o)=  ~byakuren  =(o.o)=
  m m                 m m

Packed Strings (PSTR) in Flowlog

Flowlog implements an internal “packed string” term kind (PL_TERM_PSTR) to represent lists of Unicode characters compactly, while remaining fully list-equivalent at the Prolog level (SECTION 11).

This document explains:

• the on-heap representation
• the “term-view” interface the rest of the engine should use
• where PSTR fast paths exist (and where the representation still leaks through)

Code references (section markers in flowlog.c):

• Layout helpers: SUBSECTION 11.1
• Equality and list-like comparisons: SUBSECTION 11.2 + SECTION 12
• List-like view helpers and PSTR <-> list conversions: SUBSECTION 11.3 (plus deref helpers in SUBSECTION 17.1)
• File-to-list helpers: SUBSECTION 11.4
• PSTR construction during parsing: SUBSECTION 10.5
• Builtin fast paths (length/2, atom_chars/2, number_chars/2, subsumes_term/2): SECTIONS 22/23/24 (interp/WAM/WAMVM)

High-level semantics

PL_TERM_PSTR represents a value that is list-equivalent to a Prolog list of character atoms:

"ab" == [a,b].  % when read with double_quotes=chars
functor("ab", '.', 2).
arg(1, "ab", a).
arg(2, "ab", [b]).

Important: PL_TERM_PSTR is not a new user-visible type. It is an internal optimization that must behave like '.'/2 lists under unification and all ISO list/term operations (SECTIONS 11/12/14/15).

Memory layout

A packed string is stored inline in the term allocation:

  +--------------------+
  | pl_term header     |  (tag = PL_TERM_PSTR)
  +--------------------+
  | bytes[0..n-1]      |  UTF-8 bytes
  | 0                  |  NUL terminator (byte 0)
  | padding '\0' ...   |  to align the next pointer
  +--------------------+
  | pl_term* tail      |  continuation (see below)
  +--------------------+

The pl_term field t->v.pstr.bytes points to the first UTF-8 byte of the inline sequence.

The tail pointer is located by:

1. scanning to the NUL terminator (byte 0)
2. skipping the terminator
3. rounding up to sizeof(void*) alignment
4. reading the pl_term* at that aligned slot

This is implemented by (SUBSECTION 11.1):

• pstr_tail_term_from_nul()
• pstr_tail_term_from_bytes()
• pstr_run_len_bytes()

Tail meaning

The tail cell (pl_term*) is the continuation of the list-like structure. Typical tails:

• [] atom: complete string
• a variable: open/partial list tail (difference-list style)
• another PL_TERM_PSTR: concatenation by chaining packed runs
• a normal '.'/2 term: transition back to a “real” list representation

Construction and normalization

Allocating a packed run

make_pstr_rt(rt_ctrl, dbg_dat_ptr, bytes, len, tail) copies UTF-8 bytes[0..len-1] into the packed run and stores tail in the aligned tail slot (SUBSECTION 10.5, using layout helpers from SUBSECTION 11.1).

Notable behavior:

• If len == 0, it returns tail directly (no allocation).
• The run is immutable: the byte payload and tail pointer are never mutated after allocation.

Empty-run peeling

Empty packed runs should be treated as transparent (equivalent to their tail).

Flowlog centralizes this in (SUBSECTION 11.3 and SUBSECTION 17.1):

• term_peel_pstr_empty_const()
• deref_term_and_peel_pstr_empty() / deref_term_wam_and_peel_pstr_empty()

Many engine operations “peel” before doing further work so empty PSTR segments do not leak into logic.

Term-view interface (preferred)

The goal is for most of the engine to treat packed strings through a small “term-view” API that hides the representation details.

Key helpers (SUBSECTION 11.3, with term predicates in SUBSECTION 17.1):

• List-likeness:
  • term_is_list_pair(t) for real '.'/2
  • term_is_pstr_nonempty(t) for non-empty PSTR
  • term_is_list_like_pair(t) for either
• Generic uncons:
  • term_list_like_uncons_view() (const “view” uncons; no allocations)
  • term_list_like_uncons_rt() (runtime uncons; may allocate a slice term)
• Run scanning:
  • term_list_like_run_len_and_tail_const() (works for both list pairs and PSTR)
  • term_pstr_run_len_and_tail_peeled_const() (PSTR-only, assumes already at a non-empty PSTR)
• Functor/arg view:
  • term_functor_arity_rt() returns '.'/2 for list-like terms (including PSTR)
  • term_compound_arg_rt() returns head/tail for list-like terms (including PSTR)

If you are implementing a built-in that should work on lists, prefer these helpers instead of checking t->tag == PL_TERM_PSTR directly.

Fast paths (where PSTR is referenced outside the core)

Even with a term-view layer, a few hot paths intentionally special-case PSTR to avoid per-element overhead.

length/2 fast path

length/2 uses a PSTR run-scan path that counts codepoints from UTF-8 bytes and jumps by tail pointers instead of repeatedly unconsing:

• term_pstr_run_len_and_tail_peeled_const() (SUBSECTION 11.3)
• engine-level implementations dispatch through term_is_pstr_nonempty() + the above helper (SECTIONS 22/23/24)

atom_chars/2 and number_chars/2 fast paths

These predicates often consume a whole list of characters. If the list is a PSTR (and properly terminated), Flowlog converts directly from packed byte runs into a UTF-8 C string without expanding into per-character terms:

• pstr_list_to_cstr_env() (interpreter/env mode, SUBSECTION 11.3)
• pstr_list_to_cstr_wam() (WAM/WAMVM mode, SUBSECTION 11.3)

The fast path is used for:

• atom_chars/2 (List -> Atom direction, SECTIONS 22/23/24)
• number_chars/2 (List -> Number direction, SECTIONS 22/23/24)

It intentionally rejects *_codes/2 when given a non-empty PSTR, since a PSTR is a list of characters, not integers.

subsumes_term/2 fast path

subsumes_term/2 (and its internal unifier) can be very allocation-heavy when implemented via repeated uncons on a packed run (because each tail step would otherwise allocate a PL_TERM_PSTR slice header).

Flowlog therefore has a scan-fast list-like subsumption path that:

• walks packed runs by codepoint offsets (no per-element slice allocation)
• only allocates a slice if it must materialize a remaining tail to bind a variable

Entry points:

• unify_terms_subsumes_listlike_fast() (interp/env mode, SECTION 14)
• unify_terms_subsumes_wam_tr_listlike_fast() (WAM/WAMVM mode, SECTION 15)

Where the representation still leaks

For correctness, there are still a few places that explicitly mention PL_TERM_PSTR (either for fast paths or because they predate the term-view layer).

Common categories:

• Unification and term equality/ordering:
  • list-equivalence handling needs to compare/unify PSTR runs efficiently (SECTIONS 11/12/14/15/16)
• List conversion helpers:
  • list_to_vec_iso*() expands PSTR into a vector of character atoms (slow path, SUBSECTION 11.3)
• Some term property checks:
  • e.g. occurs-check/groundness/acyclic checks need to follow the tail pointer chain (SECTIONS 14/15)

When adding new features, prefer to:

1. keep PL_TERM_PSTR-specific logic in a small number of helper functions
2. expose list-like behavior via the term-view helpers above
3. add explicit fast paths only when it materially reduces allocations or asymptotic cost

Current limitations / notes

• Packed runs are NUL-terminated (byte 0), so U+0000 is not representable inside a run.
  • When external UTF-8 data contains NUL bytes (e.g. via file_to_chars/2), Flowlog splits packed runs and inserts an explicit '.'/2 list cell with integer 0 for each NUL byte (SUBSECTION 11.4).
• The packed payload is stored as UTF-8 bytes.