Skip to main content

dive_value/
construction.rs

1//! Cooperative construction of closed, already materialized values.
2//!
3//! These helpers are used at Core's graph-value boundary. Symbolic values
4//! retain the existing conversion path; they are not certified by this module.
5
6use std::borrow::Cow;
7use std::cmp::Ordering;
8
9use crate::value::{Fcn, FcnRepr, Set, SetRepr};
10use crate::{Atom, Ctx, ErrorKind, Value, ValueError, ValueOrder};
11
12/// Failure while constructing a materialized graph value.
13#[derive(Debug)]
14pub enum ConstructionError {
15    /// The same value error as an uncontrolled constructor.
16    Value(ValueError),
17    /// The caller's cooperative checkpoint requested interruption.
18    Interrupted,
19    /// Temporary construction storage could not be reserved.
20    Allocation,
21}
22
23impl From<ValueError> for ConstructionError {
24    fn from(error: ValueError) -> Self {
25        Self::Value(error)
26    }
27}
28
29impl std::fmt::Display for ConstructionError {
30    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
31        match self {
32            Self::Value(error) => error.fmt(f),
33            Self::Interrupted => f.write_str("graph value construction interrupted"),
34            Self::Allocation => f.write_str("graph value construction storage unavailable"),
35        }
36    }
37}
38
39impl std::error::Error for ConstructionError {}
40
41type Result<T> = std::result::Result<T, ConstructionError>;
42type Poll<'a> = dyn FnMut() -> bool + 'a;
43
44pub(crate) fn checkpoint(poll: &mut Poll<'_>) -> Result<()> {
45    if poll() {
46        Ok(())
47    } else {
48        Err(ConstructionError::Interrupted)
49    }
50}
51
52pub(crate) fn reserve<T>(out: &mut Vec<T>, additional: usize, poll: &mut Poll<'_>) -> Result<()> {
53    checkpoint(poll)?;
54    out.try_reserve(additional)
55        .map_err(|_| ConstructionError::Allocation)
56}
57
58/// Stable merge sort with fallible scratch allocation and comparison.
59fn sort<T: Clone>(
60    items: &mut [T],
61    poll: &mut Poll<'_>,
62    compare: &mut dyn FnMut(&T, &T, &mut Poll<'_>) -> Result<Ordering>,
63) -> Result<()> {
64    checkpoint(poll)?;
65    if items.len() < 2 {
66        return Ok(());
67    }
68    let mut sorted = true;
69    for pair in items.windows(2) {
70        checkpoint(poll)?;
71        if compare(&pair[0], &pair[1], poll)? == Ordering::Greater {
72            sorted = false;
73            break;
74        }
75    }
76    if sorted {
77        return Ok(());
78    }
79    let mut scratch = Vec::new();
80    scratch
81        .try_reserve_exact(items.len())
82        .map_err(|_| ConstructionError::Allocation)?;
83    let mut width = 1;
84    while width < items.len() {
85        scratch.clear();
86        for start in (0..items.len()).step_by(width.saturating_mul(2)) {
87            let mid = start.saturating_add(width).min(items.len());
88            let end = mid.saturating_add(width).min(items.len());
89            let (mut left, mut right) = (start, mid);
90            while left < mid || right < end {
91                checkpoint(poll)?;
92                let take_left = right == end
93                    || left < mid
94                        && compare(&items[left], &items[right], poll)? != Ordering::Greater;
95                let at = if take_left {
96                    let at = left;
97                    left += 1;
98                    at
99                } else {
100                    let at = right;
101                    right += 1;
102                    at
103                };
104                scratch.push(items[at].clone());
105            }
106        }
107        for (destination, source) in items.iter_mut().zip(&scratch) {
108            checkpoint(poll)?;
109            destination.clone_from(source);
110        }
111        width = width.saturating_mul(2);
112    }
113    Ok(())
114}
115
116fn domain(f: &Fcn, at: usize) -> Value {
117    match &f.0.repr {
118        FcnRepr::Tuple(_) => Value::Int(i64::try_from(at).unwrap_or(i64::MAX).saturating_add(1)),
119        FcnRepr::Record(fields) => Value::Str(fields[at].0.clone()),
120        FcnRepr::General(pairs) => pairs.domain.keys[at].clone(),
121    }
122}
123
124fn image(f: &Fcn, at: usize) -> &Value {
125    match &f.0.repr {
126        FcnRepr::Tuple(values) => &values[at],
127        FcnRepr::Record(fields) => &fields[at].1,
128        FcnRepr::General(pairs) => &pairs.values[at],
129    }
130}
131
132fn explicit(s: &Set) -> Option<&[Value]> {
133    if matches!(s.repr(), SetRepr::Enum) {
134        s.stored_elements()
135    } else {
136        None
137    }
138}
139
140/// Whether every node is explicit and uses this construction's name order.
141/// The walk itself is cooperative and never materializes a symbolic value.
142pub(crate) fn closed(value: &Value, ctx: Ctx, poll: &mut Poll<'_>) -> Result<bool> {
143    explicit_tree(value, ctx, poll, true)
144}
145
146/// Raw explicit storage has exact finite children even before normalization.
147/// The strict mode is retained for fingerprinting and controlled constructors.
148fn explicit_tree(value: &Value, ctx: Ctx, poll: &mut Poll<'_>, normalized: bool) -> Result<bool> {
149    if !matches!(value, Value::Set(_) | Value::Fcn(_)) {
150        checkpoint(poll)?;
151        return Ok(true);
152    }
153    if !needs_walk(value) {
154        checkpoint(poll)?;
155        return Ok(true);
156    }
157    let mut work = Vec::new();
158    reserve(&mut work, 1, poll)?;
159    work.push(value);
160    while let Some(value) = work.pop() {
161        checkpoint(poll)?;
162        match value {
163            Value::Set(set) => {
164                let elements = match set.repr() {
165                    SetRepr::Enum => set.stored_elements(),
166                    SetRepr::Raw(elements) if !normalized => Some(elements.as_ref()),
167                    _ => None,
168                };
169                let Some(elements) = elements else {
170                    return Ok(false);
171                };
172                if normalized && set.order() != ctx.order {
173                    return Ok(false);
174                }
175                reserve(&mut work, elements.len(), poll)?;
176                work.extend(elements.iter().filter(|v| needs_walk(v)));
177            }
178            Value::Fcn(f) => {
179                if normalized && !matches!(f.0.repr, FcnRepr::Tuple(_)) && f.order() != ctx.order {
180                    return Ok(false);
181                }
182                reserve(&mut work, f.len().saturating_mul(2), poll)?;
183                match &f.0.repr {
184                    FcnRepr::Tuple(values) => work.extend(values.iter().filter(|v| needs_walk(v))),
185                    FcnRepr::Record(fields) => work.extend(
186                        fields
187                            .iter()
188                            .map(|(_, value)| value)
189                            .filter(|v| needs_walk(v)),
190                    ),
191                    FcnRepr::General(pairs) => {
192                        work.extend(pairs.domain.keys.iter().filter(|v| needs_walk(v)));
193                        work.extend(pairs.values.iter().filter(|v| needs_walk(v)));
194                    }
195                }
196            }
197            _ => {}
198        }
199    }
200    Ok(true)
201}
202
203/// Whether [`explicit_tree`] must look inside `value`: a scalar, or a tuple
204/// of scalars (the common element of a set of sequences), is explicit
205/// whatever the name order.
206fn needs_walk(value: &Value) -> bool {
207    match value {
208        Value::Set(_) => true,
209        Value::Fcn(f) => match &f.0.repr {
210            FcnRepr::Tuple(values) => values
211                .iter()
212                .any(|v| matches!(v, Value::Set(_) | Value::Fcn(_))),
213            _ => true,
214        },
215        _ => false,
216    }
217}
218
219fn ordered_elements<'a>(set: &'a Set, ctx: Ctx, poll: &mut Poll<'_>) -> Result<Cow<'a, [Value]>> {
220    let Some(elements) = explicit(set) else {
221        return Err(not_closed());
222    };
223    checkpoint(poll)?;
224    if set.order() == ctx.order {
225        return Ok(Cow::Borrowed(elements));
226    }
227    let mut out = Vec::new();
228    reserve(&mut out, elements.len(), poll)?;
229    for value in elements {
230        checkpoint(poll)?;
231        out.push(value.clone());
232    }
233    sort(&mut out, poll, &mut |a, b, poll| total(a, b, ctx, poll))?;
234    Ok(Cow::Owned(out))
235}
236
237enum Pairs<'a> {
238    Stored(&'a Fcn),
239    Sorted(Vec<(Value, Value)>),
240}
241impl Pairs<'_> {
242    fn key(&self, at: usize) -> Value {
243        match self {
244            Self::Stored(f) => domain(f, at),
245            Self::Sorted(pairs) => pairs[at].0.clone(),
246        }
247    }
248    fn value(&self, at: usize) -> &Value {
249        match self {
250            Self::Stored(f) => image(f, at),
251            Self::Sorted(pairs) => &pairs[at].1,
252        }
253    }
254}
255
256fn ordered_pairs<'a>(f: &'a Fcn, ctx: Ctx, poll: &mut Poll<'_>) -> Result<Pairs<'a>> {
257    checkpoint(poll)?;
258    if matches!(f.0.repr, FcnRepr::Tuple(_)) || f.order() == ctx.order {
259        return Ok(Pairs::Stored(f));
260    }
261    let mut out = Vec::new();
262    reserve(&mut out, f.len(), poll)?;
263    for at in 0..f.len() {
264        checkpoint(poll)?;
265        out.push((domain(f, at), image(f, at).clone()));
266    }
267    sort(&mut out, poll, &mut |a, b, poll| {
268        total(&a.0, &b.0, ctx, poll)
269    })?;
270    Ok(Pairs::Sorted(out))
271}
272
273fn total(a: &Value, b: &Value, ctx: Ctx, poll: &mut Poll<'_>) -> Result<Ordering> {
274    checkpoint(poll)?;
275    if let Some(comparison) = crate::order::scalar_cmp(a, b, ctx.order) {
276        return Ok(comparison);
277    }
278    let kinds = crate::order::rank(a).cmp(&crate::order::rank(b));
279    if kinds != Ordering::Equal {
280        return Ok(kinds);
281    }
282    let _guard = crate::depth::Guard::enter()?;
283    match (a, b) {
284        (Value::Set(s), Value::Set(t)) => {
285            let (s, t) = (
286                ordered_elements(s, ctx, poll)?,
287                ordered_elements(t, ctx, poll)?,
288            );
289            if s.len() != t.len() {
290                return Ok(s.len().cmp(&t.len()));
291            }
292            for (a, b) in s.iter().zip(t.iter()) {
293                let comparison = total(a, b, ctx, poll)?;
294                if comparison != Ordering::Equal {
295                    return Ok(comparison);
296                }
297            }
298        }
299        (Value::Fcn(f), Value::Fcn(g)) => {
300            if f.len() != g.len() {
301                return Ok(f.len().cmp(&g.len()));
302            }
303            // Two tuples of one length have the same domain, `1..n`: only
304            // their components, in order, decide.
305            if let (FcnRepr::Tuple(xs), FcnRepr::Tuple(ys)) = (&f.0.repr, &g.0.repr) {
306                for (x, y) in xs.iter().zip(ys.iter()) {
307                    let comparison = match crate::order::scalar_cmp(x, y, ctx.order) {
308                        Some(comparison) => comparison,
309                        None => total(x, y, ctx, poll)?,
310                    };
311                    if comparison != Ordering::Equal {
312                        return Ok(comparison);
313                    }
314                }
315                return Ok(Ordering::Equal);
316            }
317            let (first, second) = (ordered_pairs(f, ctx, poll)?, ordered_pairs(g, ctx, poll)?);
318            for at in 0..f.len() {
319                let comparison = total(&first.key(at), &second.key(at), ctx, poll)?;
320                if comparison != Ordering::Equal {
321                    return Ok(comparison);
322                }
323            }
324            for at in 0..f.len() {
325                let comparison = total(first.value(at), second.value(at), ctx, poll)?;
326                if comparison != Ordering::Equal {
327                    return Ok(comparison);
328                }
329            }
330        }
331        _ => {}
332    }
333    Ok(Ordering::Equal)
334}
335
336fn not_closed() -> ConstructionError {
337    ValueError::new(
338        ErrorKind::NotEnumerable,
339        "controlled construction requires closed materialized values",
340    )
341    .into()
342}
343
344fn checked_compare(a: &Value, b: &Value, ctx: Ctx, poll: &mut Poll<'_>) -> Result<Ordering> {
345    checkpoint(poll)?;
346    match (a, b) {
347        (Value::Set(s), Value::Set(t)) => {
348            let _guard = crate::depth::Guard::enter()?;
349            let (s, t) = (
350                ordered_elements(s, ctx, poll)?,
351                ordered_elements(t, ctx, poll)?,
352            );
353            if s.len() != t.len() {
354                return Ok(s.len().cmp(&t.len()));
355            }
356            for (a, b) in s.iter().zip(t.iter()) {
357                let comparison = checked_compare(a, b, ctx, poll)?;
358                if comparison != Ordering::Equal {
359                    return Ok(comparison);
360                }
361            }
362            Ok(Ordering::Equal)
363        }
364        (Value::Fcn(f), Value::Fcn(g)) => {
365            let _guard = crate::depth::Guard::enter()?;
366            // A literal record compares only with another string-domain
367            // function (or the empty tuple), exactly as TLC's toRcd does.
368            if f.is_record_literal() && !(matches!(g.0.repr, FcnRepr::Record(_)) || g.is_empty()) {
369                return crate::tlc::compare(a, b, ctx).map_err(Into::into);
370            }
371            if f.len() != g.len() {
372                return Ok(f.len().cmp(&g.len()));
373            }
374            let (first, second) = (ordered_pairs(f, ctx, poll)?, ordered_pairs(g, ctx, poll)?);
375            for at in 0..f.len() {
376                let (a, b) = (first.key(at), second.key(at));
377                // Tuple/general-function comparisons reject a noninteger
378                // general domain before invoking a scalar compare.
379                if matches!(f.0.repr, FcnRepr::Tuple(_))
380                    && !matches!(g.0.repr, FcnRepr::Tuple(_))
381                    && b.as_int().is_none()
382                {
383                    return Err(crate::tlc::non_int_domain(&b, ctx, false).into());
384                }
385                if !matches!(f.0.repr, FcnRepr::Tuple(_))
386                    && matches!(g.0.repr, FcnRepr::Tuple(_))
387                    && a.as_int().is_none()
388                {
389                    return Err(crate::tlc::non_int_domain(&a, ctx, false).into());
390                }
391                let comparison = checked_compare(&a, &b, ctx, poll)?;
392                if comparison != Ordering::Equal {
393                    return Ok(comparison);
394                }
395            }
396            for at in 0..f.len() {
397                let comparison = checked_compare(first.value(at), second.value(at), ctx, poll)?;
398                if comparison != Ordering::Equal {
399                    return Ok(comparison);
400                }
401            }
402            Ok(Ordering::Equal)
403        }
404        // Scalar comparisons and kind errors have no nested comparison work.
405        _ => crate::tlc::compare(a, b, ctx).map_err(Into::into),
406    }
407}
408
409fn duplicate(value: &Value, ctx: Ctx) -> ConstructionError {
410    ValueError::new(
411        ErrorKind::Duplicate,
412        format!(
413            "The value\n{}\noccurs multiple times in the function domain.",
414            crate::print::to_tlc_string_lenient(value, ctx)
415        ),
416    )
417    .into()
418}
419
420/// Canonical order is mathematical only for the complete materialized tree.
421pub(crate) fn canonical_set(
422    mut elements: Vec<Value>,
423    ctx: Ctx,
424    poll: &mut Poll<'_>,
425) -> Result<Value> {
426    for value in &mut elements {
427        // A closed value is its own materialized identity, and closed
428        // implies the raw explicit tree `require_closed` checks.
429        if closed(value, ctx, poll)? {
430            continue;
431        }
432        *value = materialized_identity(value, ctx, poll, 0)?;
433        require_closed(value, ctx, poll)?;
434    }
435    // Elements already in strictly ascending order (a set enumerated in
436    // canonical order, such as a function set's) are sorted and distinct.
437    let mut ascending = true;
438    for pair in elements.windows(2) {
439        if total(&pair[0], &pair[1], ctx, poll)? != Ordering::Less {
440            ascending = false;
441            break;
442        }
443    }
444    if ascending {
445        return Ok(Value::Set(Set::from_sorted(ctx.order, elements)));
446    }
447    sort(&mut elements, poll, &mut |a, b, poll| {
448        total(a, b, ctx, poll)
449    })?;
450    let mut out = Vec::new();
451    reserve(&mut out, elements.len(), poll)?;
452    for value in elements {
453        if let Some(last) = out.last()
454            && total(&value, last, ctx, poll)? == Ordering::Equal
455        {
456            continue;
457        }
458        out.push(value);
459    }
460    Ok(Value::Set(Set::from_sorted(ctx.order, out)))
461}
462
463/// Materialize explicit/deferred results, never infer symbolic identity.
464pub(crate) fn materialized_identity(
465    value: &Value,
466    ctx: Ctx,
467    poll: &mut Poll<'_>,
468    depth: usize,
469) -> Result<Value> {
470    if closed(value, ctx, poll)? {
471        return Ok(value.clone());
472    }
473    if depth >= 64 {
474        return Err(not_materialized());
475    }
476    match value {
477        Value::Set(set) => {
478            let elements = match set.repr() {
479                SetRepr::Enum => set.stored_elements().unwrap_or_default().to_vec(),
480                SetRepr::Raw(elements) => elements.to_vec(),
481                SetRepr::Interval(..) => {
482                    // Match Core's existing finite materialization ceiling;
483                    // large interval domains remain symbolic operators.
484                    if !set.size(ctx).is_ok_and(|size| size <= 1 << 24) {
485                        return Err(not_materialized());
486                    }
487                    set.elements(ctx)?.to_vec()
488                }
489                SetRepr::Subset(_)
490                | SetRepr::FcnSet(..)
491                | SetRepr::Product(_)
492                | SetRepr::RcdSet(_) => {
493                    if !crate::stream::bounded_concrete(set, ctx, 1 << 24) {
494                        return Err(not_materialized());
495                    }
496                    set.concrete_element_stream(ctx)?
497                        .ok_or_else(not_materialized)?
498                        .collect()
499                }
500                SetRepr::Deferred(source) => source.elements(ctx).map_err(|error| {
501                    if error.kind() == ErrorKind::NotEnumerable {
502                        not_materialized()
503                    } else {
504                        error.into()
505                    }
506                })?,
507                _ => return Err(not_materialized()),
508            };
509            let mut out = Vec::new();
510            reserve(&mut out, elements.len(), poll)?;
511            for child in elements {
512                // `canonical_set` keeps a closed child as it is.
513                if closed(&child, ctx, poll)? {
514                    out.push(child);
515                } else {
516                    out.push(materialized_identity(&child, ctx, poll, depth + 1)?);
517                }
518            }
519            canonical_set(out, ctx, poll)
520        }
521        Value::Fcn(function) => {
522            let mut out = Vec::new();
523            reserve(&mut out, function.len(), poll)?;
524            for (key, value) in function.iter() {
525                out.push((
526                    materialized_identity(&key, ctx, poll, depth + 1)?,
527                    materialized_identity(value, ctx, poll, depth + 1)?,
528                ));
529            }
530            Ok(match &function.0.repr {
531                FcnRepr::Tuple(_) if function.is_tuple_literal() => {
532                    Value::tuple(out.into_iter().map(|(_, value)| value).collect())
533                }
534                FcnRepr::Tuple(_) => {
535                    Value::tuple_fcn(out.into_iter().map(|(_, value)| value).collect())
536                }
537                FcnRepr::Record(fields) => Value::Fcn(Fcn::record(
538                    crate::value::sort_fields(
539                        fields
540                            .iter()
541                            .zip(out)
542                            .map(|((name, _), (_, value))| (name.clone(), value))
543                            .collect(),
544                        ctx.order,
545                    )?,
546                    ctx.order,
547                    function.is_record_literal(),
548                )),
549                FcnRepr::General(_) => Value::fcn(out, ctx)?,
550            })
551        }
552        _ => Err(not_materialized()),
553    }
554}
555
556fn not_materialized() -> ConstructionError {
557    ValueError::new(
558        ErrorKind::Unsupported,
559        "mathematical identity requires materialized values; symbolic or cross-order children are unsupported",
560    ).into()
561}
562
563pub(crate) fn require_closed(value: &Value, ctx: Ctx, poll: &mut Poll<'_>) -> Result<()> {
564    if explicit_tree(value, ctx, poll, false)? {
565        Ok(())
566    } else {
567        Err(not_materialized())
568    }
569}
570
571pub(crate) fn set(elements: Vec<Value>, ctx: Ctx, poll: &mut Poll<'_>) -> Result<Value> {
572    if crate::order::all_comparable_controlled(&elements, poll)? {
573        let mut elements = elements;
574        sort(&mut elements, poll, &mut |a, b, poll| {
575            total(a, b, ctx, poll)
576        })?;
577        let mut out = Vec::new();
578        reserve(&mut out, elements.len(), poll)?;
579        for value in elements {
580            checkpoint(poll)?;
581            if let Some(last) = out.last()
582                && total(&value, last, ctx, poll)? == Ordering::Equal
583            {
584                continue;
585            }
586            out.push(value);
587        }
588        return Ok(Value::Set(Set::from_sorted(ctx.order, out)));
589    }
590    let mut out = Vec::new();
591    reserve(&mut out, elements.len(), poll)?;
592    for element in elements {
593        checkpoint(poll)?;
594        if out.is_empty() {
595            out.push(element);
596            continue;
597        }
598        let (mut low, mut high) = (0, out.len());
599        let mut equal = false;
600        while low < high {
601            let mid = low + (high - low) / 2;
602            match checked_compare(
603                &element,
604                &out[mid],
605                Ctx {
606                    order: ValueOrder::Tlc,
607                    ..ctx
608                },
609                poll,
610            )? {
611                Ordering::Equal => {
612                    equal = true;
613                    break;
614                }
615                Ordering::Less => high = mid,
616                Ordering::Greater => low = mid + 1,
617            }
618        }
619        if !equal {
620            // Shift explicitly to keep interruption checks inside wide moves.
621            out.push(element);
622            for at in (low..out.len() - 1).rev() {
623                checkpoint(poll)?;
624                out.swap(at, at + 1);
625            }
626        }
627    }
628    if ctx.order != ValueOrder::Tlc {
629        sort(&mut out, poll, &mut |a, b, poll| total(a, b, ctx, poll))?;
630    }
631    checkpoint(poll)?;
632    Ok(Value::Set(Set::from_sorted(ctx.order, out)))
633}
634
635pub(crate) fn fcn(mut pairs: Vec<(Value, Value)>, ctx: Ctx, poll: &mut Poll<'_>) -> Result<Value> {
636    let mut domains = Vec::new();
637    reserve(&mut domains, pairs.len(), poll)?;
638    for (domain, _) in &pairs {
639        checkpoint(poll)?;
640        domains.push(domain.clone());
641    }
642    if crate::order::all_comparable_controlled(&domains, poll)? {
643        sort(&mut pairs, poll, &mut |a, b, poll| {
644            total(&a.0, &b.0, ctx, poll)
645        })?;
646        for pair in pairs.windows(2) {
647            if total(&pair[0].0, &pair[1].0, ctx, poll)? == Ordering::Equal {
648                return Err(duplicate(&pair[1].0, ctx));
649            }
650        }
651    } else {
652        let tlc = Ctx {
653            order: ValueOrder::Tlc,
654            ..ctx
655        };
656        for at in 1..pairs.len() {
657            match checked_compare(&pairs[0].0, &pairs[at].0, tlc, poll)? {
658                Ordering::Equal => return Err(duplicate(&pairs[at].0, tlc)),
659                Ordering::Greater => pairs.swap(0, at),
660                Ordering::Less => {}
661            }
662        }
663        for at in 2..pairs.len() {
664            let item = pairs[at].clone();
665            let mut to = at;
666            let mut comparison = Ordering::Less;
667            while to > 0 {
668                comparison = checked_compare(&item.0, &pairs[to - 1].0, tlc, poll)?;
669                if comparison != Ordering::Less {
670                    break;
671                }
672                pairs[to] = pairs[to - 1].clone();
673                to -= 1;
674            }
675            if comparison == Ordering::Equal {
676                return Err(duplicate(&pairs[at].0, tlc));
677            }
678            pairs[to] = item;
679        }
680        if ctx.order != ValueOrder::Tlc {
681            sort(&mut pairs, poll, &mut |a, b, poll| {
682                total(&a.0, &b.0, ctx, poll)
683            })?;
684        }
685    }
686    let mut tuple = true;
687    let mut record = true;
688    for (at, (key, _)) in pairs.iter().enumerate() {
689        checkpoint(poll)?;
690        tuple &= matches!(key, Value::Int(k) if i64::try_from(at).is_ok_and(|at| *k == at + 1));
691        record &= matches!(key, Value::Str(_));
692    }
693    if tuple {
694        let mut values = Vec::new();
695        reserve(&mut values, pairs.len(), poll)?;
696        for (_, value) in pairs {
697            checkpoint(poll)?;
698            values.push(value);
699        }
700        Ok(Value::tuple_fcn(values))
701    } else if record {
702        let mut fields = Vec::new();
703        reserve(&mut fields, pairs.len(), poll)?;
704        for (key, value) in pairs {
705            checkpoint(poll)?;
706            if let Value::Str(name) = key {
707                fields.push((name, value));
708            }
709        }
710        Ok(Value::Fcn(Fcn::record(fields, ctx.order, false)))
711    } else {
712        checkpoint(poll)?;
713        Ok(Value::Fcn(Fcn::general(pairs, ctx.order)))
714    }
715}
716
717pub(crate) fn record(
718    mut fields: Vec<(Atom, Value)>,
719    ctx: Ctx,
720    poll: &mut Poll<'_>,
721) -> Result<Value> {
722    sort(&mut fields, poll, &mut |a, b, poll| {
723        checkpoint(poll)?;
724        Ok(a.0.cmp_with(&b.0, ctx.order))
725    })?;
726    for pair in fields.windows(2) {
727        checkpoint(poll)?;
728        if pair[0].0 == pair[1].0 {
729            return Err(ValueError::new(
730                ErrorKind::Duplicate,
731                format!("Field name {} occurs multiple times in record.", pair[1].0),
732            )
733            .into());
734        }
735    }
736    checkpoint(poll)?;
737    if fields.is_empty() {
738        Ok(Value::tuple(Vec::new()))
739    } else {
740        Ok(Value::Fcn(Fcn::record(fields, ctx.order, true)))
741    }
742}
743
744#[cfg(test)]
745mod allocation_tests {
746    use super::*;
747
748    #[test]
749    fn scratch_capacity_failure_is_distinct_from_interruption() {
750        let result = reserve(&mut Vec::<u64>::new(), usize::MAX, &mut || true);
751        assert!(matches!(result, Err(ConstructionError::Allocation)));
752        let result = reserve(&mut Vec::<u64>::new(), usize::MAX, &mut || false);
753        assert!(matches!(result, Err(ConstructionError::Interrupted)));
754    }
755}