Tracking Issue: Core Language Extension Checklist

[archaephyrryx]

Core Language Extension Checklist

This document is designed to act as an ongoing tracker for any specification-level problems
that our Format/Expr/Pattern model in doodle is not well-enough-equipped to handle at present.

Certain issues may be labeled with the binary format that most notably benefits from their
resolution, but may apply more broadly than one format.

Furthermore, each problem will be given values across several metrics, indicating various aspects of solving it:

• Complexity: How difficult we estimate it will be to implement an appropriate solution
  • trivial, simple, moderate, complex
• Commonness: How many formats, whether currently-implemented and not-yet-implemented, the issue may appear in
  • niche, narrow, common
• Category: The metric on which our definitions will 'improve' as a result of having an on-hand solution
  • spec - Specification compliance
  • sem - Semantic transparency
  • cons - Model-internal consistency
  • expr - Expressivity of novel constructions
  • ergo - Ergonomics of existing usage-idioms

Proposals

• [lang-model]: First-Class Option-type at all layers #187
• [lang-model]: Numerically-predicated repeat-intercalation (moderate, niche, spec) #191
• [lang-model]: const-enum Format (simple, common, sem) #192
• [lang-model]: Dynamic-order parsing based on absolute offset linkage (complex, narrow, expr) #194
• [lang-model]: Format primitive for working with buffer-offsets (simple, narrow, expr) #195
• [lang-model]: ForEach format over sequence-valued expr using fused lambda (moderate, narrow, expr) #197
• [lang-model] Decode an Expr of type Seq(U8) using a given Format #201
• [lang-model]: First-class tuple-destructuring within Expr::Lambda argument capture (moderate, common, sem) #208
• [lang-model]: Signed integer types #213
• [lang-model]: Expr::DupSeq for Seq-based instead of Tuple-based reptition #214
• [lang-model] Format::AccumUntil for fused fold-and-repeat operations #215
• [lang-model]: 'Forgetful' Format chaining (>> ~ >>= : X ~ Format::LetFormat) (trivial, narrow, sem) #227
• [lang-model]: Integer-rep/Machine-type agnostic basic unary ops (e.g. Pred/Succ) (trivial, narrow, sem) #229
• [lang-model]: Polymorphic Expr::Zero (or Expr::PolyConst(u8)) (trivial, common, ergo) #231

No-Issue-Assigned

• Repetition-Scope abstractions (Format::LocalScope / Format::UniqueInScope

Designated fields in a repetition that are supposed to be unique within that repetition

E.g.

Format::LocalScope("#unique-id", repeat(record(vec![("unique-id", Format::UniqueInScope(base.u8(), "#unique-id")), ...other fields...])))

• Format::ValueInSet

Values that belong to a set of values accessed by a relative projective lens

E.g.

Format::record(
   vec![
      ("original", Format::LocalScope("#orig-values",
            repeat(Format::UniqueInScope(base.u8(), "#orig-values")))).
      ("permutation", Format:LocalScope("#permutation", 
            repeat(Format::UniqueInScope(Format::ValueInSet(Lens::Var("original").set_from_seq()), "#permutation"))))
   ]
)

Suggested by OpenType

• Expr::UnaryOp primitive with associated enum including certain base-2 related transformations
  • UnaryOp::ILog2 (would be enough for our validation purposes)
  • Suggested by: table_directory.search_range and subsequent fields
• Expr-level construct for detecting and asserting relative sort-order of a sequence, either raw-value or with a key-getter Expr::Lambda (or impl Fn(Expr) -> Expr)
  • We can do this with a primitive Expr that evaluates to an Option-wrapped copy of the last iteration of a Format::Repeat*, but this might be complicated; alternatively, a Format primitive that bakes such a value into its parsing logic
  • Another way would be to have an Expr primitive that takes Expr::Lambda :: (Expr@T, Expr@T) -> Expr@Bool and applies it to every pair of adjacent elements of a sequence, aggregating with BoolAnd
• Expr-level construct for performing a binary search over a (key-)sorted list whose sort-order is known in advance (either as a simple enum param, or inferred dynamically based on the relative order of the first and last element of the sequence)
  • This is really a matter of efficiency more-so than necessity, but we shouldn't have to open-code find operations that don't even have the right short-circuiting logic...
• Expr that computes the maximum value within a sequence
  • Technically speaking we can define this with what we have, but it might be better off as a primitive, or at least with an extra primitive to simplify the definition
• Simple Expr for the first and last elements of a sequence that don't use SeqLength
• Expr to extract the sole element of a List, failing if len >= 2 and evaluating to None if empty
• Multi-field delimited Slice, or record-flattening/-concatenating constructions
  • This isn't quite necessary as of current implementation, but is hinted at by cmap subtable formats that just so happen to be implementable using other constructions as