Skip to content

Fix implementation of map #729

@Acaccia

Description

@Acaccia

Here is a new proptest testing the implementation of map:

    #[test]
    fn crosscheck_map_append(
        (ty, seq, elem) in prop_signature().prop_flat_map(|ty| {
            let seq = {
                let ty = ty.clone();
                (1..=10u32, 1..=10u32).prop_flat_map(move |(outer_count, inner_count)| {
                    PropValue::from_type(
                        TypeSignature::list_of(
                            TypeSignature::list_of(ty.clone(), inner_count).unwrap(),
                            outer_count,
                        )
                        .unwrap(),
                    )
                })
            };
            let elem = {
                let ty = ty.clone();
                (1..10u32).prop_flat_map(move |count| {
                    PropValue::from_type(TypeSignature::list_of(ty.clone(), count).unwrap())
                })
            };

            (Just(ty).no_shrink(), seq.no_shrink(), elem.no_shrink())
        })
    ) {
        let snippet = format!(
            r#"
                (define-private (foo (a (list 100 {t})) (b {t}))
                    (append a b)
                ) 

                (map foo {seq} {elem})
            "#,
            t = type_string(&ty)
        );

        let expected = {
            let SequenceData::List(seq) = extract_sequence(seq) else {
                unreachable!()
            };
            let SequenceData::List(elem) = extract_sequence(elem) else {
                unreachable!()
            };

            let mut res = Vec::with_capacity(seq.items().len().min(elem.items().len()));
            for (s, e) in seq.items().iter().zip(elem.items()) {
                let Value::Sequence(SequenceData::List(s)) = s else {
                    unreachable!()
                };

                let mut item = Vec::with_capacity(s.items().len() + 1);
                item.extend(s.items().clone());
                item.push(e.clone());

                res.push(Value::cons_list_unsanitized(item).unwrap());
            }

            Value::cons_list_unsanitized(res).unwrap()
        };

        crosscheck(&snippet, Ok(Some(expected)));
    }

This new test showed multiple errors with the current implementation of map:

  1. the current workaround for the type of the argument lists is wrong in the computation of the max_len
  2. the current workaround only sets the type of the first argument list
  3. the current implementation crashes if the first list is empty
  4. the current implementation can create OOM errors.

Metadata

Metadata

Assignees

Labels

bugSomething isn't working

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions