24868044425

Committed 24 Apr 2026 01:47AM UTC coverage: 78.522% (+0.1%) from 78.391%

Build # 24868044425

Build Type

push

github

Committed by

web-flow

Commit Message

Error Handling and Stringify Changes (#1893)

* Modify stringify to prioritize toReplString

* Make the extract declarations helper actually work

* Add ability to change loader for source modules

* Add a new option for controlling how Source modules are loaded

* Improve typing for CSE machine

* Add ability to check if modules are loaded with the wrong Source chapter

* Refactor errors to extend from Error class

* Refactor modules errors

* Refactor parser errors

* Refactor cse machine errors

* Mostly fix error handling in the tracer

* Tidy up generator and explainer implementations for tracer

* Remove unnecessary imports and type guards

* Adjust rttc checks to be type guards instead of returning errors

* Adjust miscellanous error changes

* Add eslint rule for useless constructor

* Fix incorrect ordering for checking exceptionerrors

* Minor changes

* Run format

* Run linting

* Override the message property, but also enable noImplicitOverride to prevent accidental overriding

* Add some documentation to some errors

* Add errors to possible imports for modules

* Update getIds helper

* Minor fix to test case

* Run format

* Allow modules to try and load the context of other modules without crashing

* Fix incorrect stdlib name

* Add some more functions to the stdlib list library

* Change to use GeneralRuntimeError for list

* Revert "Change to use GeneralRuntimeError for list"

This reverts commit 642bd99e6.

* Update src/errors/errors.ts

Co-authored-by: gemini-code-assist[bot] <176961590+gemini-code-assist[bot]@users.noreply.github.com>

* Add ability to change manifest and docs importers

* Change how external builtins are defined

* Fix typings and list lib overloads

* Miscellanous changes

* Add the Source equality function to stdlib/misc

* Merge from main branch for tracer

* Add handling for the new importers

* Change errors and made redex a local variable

* Improve tracer typing

* Relocate... (continued)

Coverage Stats

3125 of 4193 branches covered (74.53%)

Branch coverage included in aggregate %.

899 of 1089 new or added lines in 96 files covered. (82.55%)

21 existing lines in 12 files now uncovered.

7031 of 8741 relevant lines covered (80.44%)

185057.72 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.95

/src/stdlib/list.ts

/**
 * list.ts: Supporting lists in the Scheme style, using pairs made
 *          up of two-element JavaScript array (vector)
 * @author: Martin Henz
 * Translated to TypeScript by Evan Sebastian
 */

import { GeneralRuntimeError } from '../errors/base';
import { InvalidParameterTypeError } from '../errors/rttcErrors';
import type { Value } from '../types';
import { assertFunctionOfLength, assertNumberWithinRange } from '../utils/rttc';
import type { ArrayLike } from '../utils/stringify';

export type Pair<H, T> = [H, T];
export type List<T = unknown> = null | NonEmptyList<T>;
export type NonEmptyList<T> = [T, List<T>];

// array test works differently for Rhino and
// the Firefox environment (especially Web Console)
function array_test(x: unknown): x is unknown[] {
  if (Array.isArray === undefined) {
    return x instanceof Array;
  } else {
    return Array.isArray(x);
  }
}

/**
 * constructs a pair using a two-element array\
 * LOW-LEVEL FUNCTION, NOT SOURCE
 */
export function pair<T>(x: T, xs: List<T>): NonEmptyList<T>;
export function pair<H, T>(x: H, xs: T): Pair<H, T>;
export function pair<H, T>(x: H, xs: T) {
  return [x, xs];
}

/**
 * returns true iff arg is a two-element array\
 * LOW-LEVEL FUNCTION, NOT SOURCE
 */
export function is_pair(x: unknown): x is Pair<unknown, unknown> {
  return array_test(x) && x.length === 2;
}

/**
 * returns the first component of the given pair\
 * LOW-LEVEL FUNCTION, NOT SOURCE
 * @throws an exception if the argument is not a pair
 */
export function head<T>(xs: Pair<T, unknown> | NonEmptyList<T>): T;
export function head(xs: unknown) {
  if (!is_pair(xs)) {
    throw new InvalidParameterTypeError('pair', xs, head.name);
  }

  return xs[0];
}

/**
 * returns the second component of the given pair\
 * LOW-LEVEL FUNCTION, NOT SOURCE
 * @throws an exception if the argument is not a pair
 */
export function tail<T>(xs: NonEmptyList<T>): List<T>;
export function tail<T>(xs: Pair<unknown, T>): T;
export function tail(xs: unknown) {
  if (!is_pair(xs)) {
    throw new InvalidParameterTypeError('pair', xs, tail.name);
  }

  return xs[1];
}

/**
 * changes the head of given pair xs to be x\
 * LOW-LEVEL FUNCTION, NOT SOURCE
 * @throws an exception if the argument is not a pair
 */
export function set_head(xs: Pair<any, any>, x: any): void;
export function set_head(xs: unknown, x: any): void {
  if (!is_pair(xs)) {
    throw new InvalidParameterTypeError('pair', xs, set_head.name);
  }

  xs[0] = x;
}

/**
 * changes the tail of given pair xs to be x\
 * LOW-LEVEL FUNCTION, NOT SOURCE
 * @throws an exception if the argument is not a pair
 */
export function set_tail(xs: Pair<any, any>, x: any): void;
export function set_tail(xs: unknown, x: any): void {
  if (!is_pair(xs)) {
    throw new InvalidParameterTypeError('pair', xs, set_tail.name);
  }

  xs[1] = x;
}

/**
 * returns true if arg is exactly null\
 * LOW-LEVEL FUNCTION, NOT SOURCE
 */
export function is_null(xs: unknown): xs is null {
  return xs === null;
}

/**
 * makes a list out of its arguments\
 * LOW-LEVEL FUNCTION, NOT SOURCE
 */
export function list<T>(...elements: T[]): NonEmptyList<T>;
export function list<T>(): List<T>;
export function list<T>(...elements: T[]): List<T> {
  return elements.reduceRight((res, each) => pair(each, res), null);
}

/**
 * recurses down the list and checks that it ends with the empty list null\
 * LOW-LEVEL FUNCTION, NOT SOURCE
 */
export function is_list(xs: unknown): xs is List<unknown> {
  while (is_pair(xs)) {
    xs = tail(xs);
  }
  return is_null(xs);
}

/**
 * returns vector that contains the elements of the argument list
 * in the given order.\
 * LOW-LEVEL FUNCTION, NOT SOURCE
 * @throws an exception if the argument is not a list
 */
export function list_to_vector<T>(lst: List<T>): T[] {
  const vector: T[] = [];
  for_each(each => vector.push(each), lst);
  return vector;
}

/**
 * returns a list that contains the elements of the argument vector
 * in the given order\
 * LOW-LEVEL FUNCTION, NOT SOURCE
 * @throws an exception if the argument is not a vector
 */
export function vector_to_list<T>(vector: T[]): List<T> {
  return list(...vector);
}

/**
 * Accumulate applies given operation op to elements of a list
 * in a right-to-left order, first apply op to the last element
 * and an initial element, resulting in r1, then to the second-last
 * element and r1, resulting in r2, etc, and finally to the first element
 * and r_n-1, where n is the length of the list. `accumulate(op,zero,list(1,2,3))`
 * results in `op(1, op(2, op(3, zero)))`
 */
export function accumulate<T, U>(op: (each: T, result: U) => U, initial: U, sequence: List<T>): U {
  // Use CPS to prevent stack overflow
  function $accumulate(xs: typeof sequence, cont: (each: U) => U): U {
    return is_null(xs) ? cont(initial) : $accumulate(tail(xs), x => cont(op(head(xs), x)));
  }
  return $accumulate(sequence, x => x);
}

/**
 * Appends the list `ys` to the end of list `xs` and returns the
 * resulting list
 */
export function append<T>(xs: List<T>, ys: List<T>): List<T> {
  function $append(xs: List<T>, ys: List<T>, cont: (res: List<T>) => List<T>): List<T> {
    return is_null(xs) ? cont(ys) : $append(tail(xs), ys, zs => cont(pair(head(xs), zs)));
  }

  return $append(xs, ys, xs => xs);
}

/**
 * Takes a unary function `f` and a non-negative integer `n`. Returns the list
 * of `n` elements that results from applying `f` to the numbers from 0 to `n-1`.
 */
export function build_list<T>(f: (arg: number) => T, n: number): List<T> {
  assertNumberWithinRange(n, build_list.name, 0);
  assertFunctionOfLength(f, 1, build_list.name);

  function $build_list(i: number, already_built: List<T>): List<T> {
    return i < 0 ? already_built : $build_list(i - 1, pair(f(i), already_built));
  }

  return $build_list(n - 1, null);
}

/**
 * Takes two numbers, `start` and `end` and returns the list containing numbers between `start` and `end`,
 * beginning with `start` and then incrementing by 1 until the value exceeds `end`.
 */
export function enum_list(start: number, end: number): List<number> {
  assertNumberWithinRange(start, {
    func_name: enum_list.name,
    param_name: 'start',
    integer: false,
  });
  assertNumberWithinRange(end, enum_list.name, start, undefined, false, 'end');

  return build_list(x => x + start, Math.floor(end - start) + 1);
}

/**
 * Returns a new list that only contains elements that the predicate function returned `true`
 * for
 */
export function filter<T, U extends T>(pred: (arg: T) => arg is U, xs: List<T>): List<U>;
export function filter<T>(pred: (arg: T) => boolean, xs: List<T>): List<T>;
export function filter<T>(pred: (arg: T) => boolean, xs: List<T>): List<T> {
  return accumulate((each, result) => (pred(each) ? pair(each, result) : result), list(), xs);
}

/**
 * Applies the provided function to each element in the list. Returns `true`.
 */
export function for_each<T>(op: (arg: T) => void, xs: List<T>): true {
  if (is_null(xs)) return true;
  op(head(xs));
  return for_each(op, tail(xs));
}

/**
 * returns the length of a List xs. Throws an exception if xs is not a List
 */
export function length(xs: unknown): number {
  if (!is_list(xs)) {
    throw new InvalidParameterTypeError('list', xs, length.name);
  }

  return accumulate((_, total) => total + 1, 0, xs);
}

/**
 * Returns the element at the `n`th index in the provided list
 */
export function list_ref<T>(xs: List<T>, n: number) {
  if (is_null(xs)) {
    throw new GeneralRuntimeError(`${list_ref.name}: Index ${n} is out of bounds.`);
  }

  let res: NonEmptyList<T> = xs;
  let i = n;
  while (i > 0) {
    const temp = tail(res);

    if (is_null(temp)) {
      throw new GeneralRuntimeError(`${list_ref.name}: Index ${n} is out of bounds.`);
    }

    res = temp;
    i--;
  }

  return head(res);
}

/**
 * Calls the provided function on each element of the provided list, and returns
 * a new list containing the results
 */
export function map<T, U>(op: (each: T) => U, sequence: List<T>): List<U> {
  return accumulate((each, result) => pair(op(each), result), list(), sequence);
}

/**
 * Returns the first postfix sublist that starts with the given element `v`. If
 * the element is not in `xs`, returns an empty list.
 */
export function member<T>(v: T, xs: List<T>): List<T> {
  return is_null(xs) ? null : v === head(xs) ? xs : member(v, tail(xs));
}

/**
 * Removes the first instance of `v` in the given List `xs`.
 */
export function remove<T>(v: T, xs: List<T>): List<T> {
  if (is_null(xs)) return xs;

  const current = head(xs);
  if (current === v) return tail(xs);

  return pair(head(xs), remove(v, tail(xs)));
}

/**
 * Removes all instances of `v` from the given list `xs`.
 */
export function remove_all<T>(v: T, xs: List<T>): List<T> {
  return filter(x => x !== v, xs);
}

/**
 * Reverses the given list `xs`.
 */
export function reverse<T>(xs: List<T>): List<T> {
  function $reverse(original: List<T>, reversed: List<T>): List<T> {
    return is_null(original) ? reversed : $reverse(tail(original), pair(head(original), reversed));
  }

  return $reverse(xs, null);
}

export function rawDisplayList(
  display: (v: Value, ...s: string[]) => Value,
  xs: Value,
  prepend: string,
) {
  const visited: Set<Value> = new Set(); // Everything is put into this set, values, arrays, and even objects if they exist
  const asListObjects: Map<NonEmptyList<Value>, NonEmptyList<Value> | ListObject> = new Map(); // maps original list nodes to new list nodes

  // We will convert list-like structures in xs to ListObject.
  class ListObject implements ArrayLike {
    replPrefix = 'list(';
    replSuffix = ')';
    replArrayContents(): Value[] {
      return list_to_vector(this.listNode);
    }

    constructor(readonly listNode: NonEmptyList<Value>) {}
  }
  function getListObject(curXs: Value): Value {
    return asListObjects.get(curXs) || curXs;
  }

  const pairsToProcess: Value[] = [xs];
  // we need the guarantee that if there are any proper lists,
  // then the nodes of the proper list appear as a subsequence of this array.
  // We ensure this by always adding the tail after the current node is processed.
  // This means that sometimes, we add the same pair more than once!
  // But because we only process each pair once due to the visited check,
  // and each pair can only contribute to at most 3 items in this array,
  // this array has O(n) elements.
  for (let i = 0; i < pairsToProcess.length; i++) {
    const curXs = pairsToProcess[i];
    if (visited.has(curXs)) {
      continue;
    }
    visited.add(curXs);
    if (!is_pair(curXs)) {
      continue;
    }
    pairsToProcess.push(head(curXs), tail(curXs));
  }

  function isListObject(x: Value): x is NonEmptyList<Value> {
    return asListObjects.has(x);
  }

  // go through pairs in reverse to ensure the dependencies are resolved first
  while (pairsToProcess.length > 0) {
    const curXs = pairsToProcess.pop();
    if (!is_pair(curXs)) {
      continue;
    }
    const h = head(curXs);
    const t = tail(curXs);

    let newXs: Value;
    if (isListObject(t)) {
      const newTail = asListObjects.get(t)!;
      newXs =
        is_null(newTail) || newTail instanceof ListObject ? new ListObject(pair(h, t)) : pair(h, t);
    } else {
      newXs = is_null(t) ? new ListObject(pair(h, t)) : pair(h, t);
    }

    // @ts-ignore
    asListObjects.set(curXs, newXs);
  }

  for (const curXs of asListObjects.values()) {
    if (is_pair(curXs)) {
      set_head(curXs, getListObject(head(curXs)));
      set_tail(curXs, getListObject(tail(curXs)));
    } else if (curXs instanceof ListObject) {
      set_head(curXs.listNode, getListObject(head(curXs.listNode)));
      let newTail = getListObject(tail(curXs.listNode));
      if (newTail instanceof ListObject) {
        newTail = newTail.listNode;
      }
      set_tail(curXs.listNode, newTail);
    }
  }
  display(getListObject(xs), prepend);
  return xs;
}

1	/**
2	* list.ts: Supporting lists in the Scheme style, using pairs made
3	* up of two-element JavaScript array (vector)
4	* @author: Martin Henz
5	* Translated to TypeScript by Evan Sebastian
6	*/
7
8	import { GeneralRuntimeError } from '../errors/base';
9	import { InvalidParameterTypeError } from '../errors/rttcErrors';
10	import type { Value } from '../types';
11	import { assertFunctionOfLength, assertNumberWithinRange } from '../utils/rttc';
12	import type { ArrayLike } from '../utils/stringify';
13
14	export type Pair<H, T> = [H, T];
15	export type List<T = unknown> = null \| NonEmptyList<T>;
16	export type NonEmptyList<T> = [T, List<T>];
17
18	// array test works differently for Rhino and
19	// the Firefox environment (especially Web Console)
20	function array_test(x: unknown): x is unknown[] {
21	if (Array.isArray === undefined) {	13,429!
22	return x instanceof Array;	×
23	} else {
24	return Array.isArray(x);	13,429✔
25	}
26	}
27
28	/**
29	* constructs a pair using a two-element array\
30	* LOW-LEVEL FUNCTION, NOT SOURCE
31	*/
32	export function pair<T>(x: T, xs: List<T>): NonEmptyList<T>;
33	export function pair<H, T>(x: H, xs: T): Pair<H, T>;
34	export function pair<H, T>(x: H, xs: T) {
35	return [x, xs];	6,039✔
36	}
37
38	/**
39	* returns true iff arg is a two-element array\
40	* LOW-LEVEL FUNCTION, NOT SOURCE
41	*/
42	export function is_pair(x: unknown): x is Pair<unknown, unknown> {
43	return array_test(x) && x.length === 2;	13,429✔
44	}
45
46	/**
47	* returns the first component of the given pair\
48	* LOW-LEVEL FUNCTION, NOT SOURCE
49	* @throws an exception if the argument is not a pair
50	*/
51	export function head<T>(xs: Pair<T, unknown> \| NonEmptyList<T>): T;
52	export function head(xs: unknown) {
53	if (!is_pair(xs)) {	2,792✔
54	throw new InvalidParameterTypeError('pair', xs, head.name);	13✔
55	}
56
57	return xs[0];	2,779✔
58	}
59
60	/**
61	* returns the second component of the given pair\
62	* LOW-LEVEL FUNCTION, NOT SOURCE
63	* @throws an exception if the argument is not a pair
64	*/
65	export function tail<T>(xs: NonEmptyList<T>): List<T>;
66	export function tail<T>(xs: Pair<unknown, T>): T;
67	export function tail(xs: unknown) {
68	if (!is_pair(xs)) {	4,879✔
69	throw new InvalidParameterTypeError('pair', xs, tail.name);	15✔
70	}
71
72	return xs[1];	4,864✔
73	}
74
75	/**
76	* changes the head of given pair xs to be x\
77	* LOW-LEVEL FUNCTION, NOT SOURCE
78	* @throws an exception if the argument is not a pair
79	*/
80	export function set_head(xs: Pair<any, any>, x: any): void;
81	export function set_head(xs: unknown, x: any): void {
82	if (!is_pair(xs)) {	480✔
83	throw new InvalidParameterTypeError('pair', xs, set_head.name);	2✔
84	}
85
86	xs[0] = x;	478✔
87	}
88
89	/**
90	* changes the tail of given pair xs to be x\
91	* LOW-LEVEL FUNCTION, NOT SOURCE
92	* @throws an exception if the argument is not a pair
93	*/
94	export function set_tail(xs: Pair<any, any>, x: any): void;
95	export function set_tail(xs: unknown, x: any): void {
96	if (!is_pair(xs)) {	499✔
97	throw new InvalidParameterTypeError('pair', xs, set_tail.name);	2✔
98	}
99
100	xs[1] = x;	497✔
101	}
102
103	/**
104	* returns true if arg is exactly null\
105	* LOW-LEVEL FUNCTION, NOT SOURCE
106	*/
107	export function is_null(xs: unknown): xs is null {
108	return xs === null;	3,927✔
109	}
110
111	/**
112	* makes a list out of its arguments\
113	* LOW-LEVEL FUNCTION, NOT SOURCE
114	*/
115	export function list<T>(...elements: T[]): NonEmptyList<T>;
116	export function list<T>(): List<T>;
117	export function list<T>(...elements: T[]): List<T> {
118	return elements.reduceRight((res, each) => pair(each, res), null);	2,254✔
119	}
120
121	/**
122	* recurses down the list and checks that it ends with the empty list null\
123	* LOW-LEVEL FUNCTION, NOT SOURCE
124	*/
125	export function is_list(xs: unknown): xs is List<unknown> {
126	while (is_pair(xs)) {	8✔
127	xs = tail(xs);	10✔
128	}
129	return is_null(xs);	8✔
130	}
131
132	/**
133	* returns vector that contains the elements of the argument list
134	* in the given order.\
135	* LOW-LEVEL FUNCTION, NOT SOURCE
136	* @throws an exception if the argument is not a list
137	*/
138	export function list_to_vector<T>(lst: List<T>): T[] {
139	const vector: T[] = [];	90✔
140	for_each(each => vector.push(each), lst);	429✔
141	return vector;	90✔
142	}
143
144	/**
145	* returns a list that contains the elements of the argument vector
146	* in the given order\
147	* LOW-LEVEL FUNCTION, NOT SOURCE
148	* @throws an exception if the argument is not a vector
149	*/
150	export function vector_to_list<T>(vector: T[]): List<T> {
151	return list(...vector);	782✔
152	}
153
154	/**
155	* Accumulate applies given operation op to elements of a list
156	* in a right-to-left order, first apply op to the last element
157	* and an initial element, resulting in r1, then to the second-last
158	* element and r1, resulting in r2, etc, and finally to the first element
159	* and r_n-1, where n is the length of the list. `accumulate(op,zero,list(1,2,3))`
160	* results in `op(1, op(2, op(3, zero)))`
161	*/
162	export function accumulate<T, U>(op: (each: T, result: U) => U, initial: U, sequence: List<T>): U {
163	// Use CPS to prevent stack overflow
164	function $accumulate(xs: typeof sequence, cont: (each: U) => U): U {
165	return is_null(xs) ? cont(initial) : $accumulate(tail(xs), x => cont(op(head(xs), x)));	41✔
166	}
167	return $accumulate(sequence, x => x);	10✔
168	}
169
170	/**
171	* Appends the list `ys` to the end of list `xs` and returns the
172	* resulting list
173	*/
174	export function append<T>(xs: List<T>, ys: List<T>): List<T> {
175	function $append(xs: List<T>, ys: List<T>, cont: (res: List<T>) => List<T>): List<T> {
176	return is_null(xs) ? cont(ys) : $append(tail(xs), ys, zs => cont(pair(head(xs), zs)));	15✔
177	}
178
179	return $append(xs, ys, xs => xs);	5✔
180	}
181
182	/**
183	* Takes a unary function `f` and a non-negative integer `n`. Returns the list
184	* of `n` elements that results from applying `f` to the numbers from 0 to `n-1`.
185	*/
186	export function build_list<T>(f: (arg: number) => T, n: number): List<T> {
187	assertNumberWithinRange(n, build_list.name, 0);	9✔
188	assertFunctionOfLength(f, 1, build_list.name);	9✔
189
190	function $build_list(i: number, already_built: List<T>): List<T> {
191	return i < 0 ? already_built : $build_list(i - 1, pair(f(i), already_built));	20✔
192	}
193
194	return $build_list(n - 1, null);	9✔
195	}
196
197	/**
198	* Takes two numbers, `start` and `end` and returns the list containing numbers between `start` and `end`,
199	* beginning with `start` and then incrementing by 1 until the value exceeds `end`.
200	*/
201	export function enum_list(start: number, end: number): List<number> {
202	assertNumberWithinRange(start, {	7✔
203	func_name: enum_list.name,
204	param_name: 'start',
205	integer: false,
206	});
207	assertNumberWithinRange(end, enum_list.name, start, undefined, false, 'end');	7✔
208
209	return build_list(x => x + start, Math.floor(end - start) + 1);	11✔
210	}
211
212	/**
213	* Returns a new list that only contains elements that the predicate function returned `true`
214	* for
215	*/
216	export function filter<T, U extends T>(pred: (arg: T) => arg is U, xs: List<T>): List<U>;
217	export function filter<T>(pred: (arg: T) => boolean, xs: List<T>): List<T>;
218	export function filter<T>(pred: (arg: T) => boolean, xs: List<T>): List<T> {
219	return accumulate((each, result) => (pred(each) ? pair(each, result) : result), list(), xs);	17✔
220	}
221
222	/**
223	* Applies the provided function to each element in the list. Returns `true`.
224	*/
225	export function for_each<T>(op: (arg: T) => void, xs: List<T>): true {
226	if (is_null(xs)) return true;	524✔
227	op(head(xs));	432✔
228	return for_each(op, tail(xs));	432✔
229	}
230
231	/**
232	* returns the length of a List xs. Throws an exception if xs is not a List
233	*/
234	export function length(xs: unknown): number {
235	if (!is_list(xs)) {	2!
NEW 236	throw new InvalidParameterTypeError('list', xs, length.name);	×
237	}
238
239	return accumulate((_, total) => total + 1, 0, xs);	4✔
240	}
241
242	/**
243	* Returns the element at the `n`th index in the provided list
244	*/
245	export function list_ref<T>(xs: List<T>, n: number) {
246	if (is_null(xs)) {	3✔
247	throw new GeneralRuntimeError(`${list_ref.name}: Index ${n} is out of bounds.`);	1✔
248	}
249
250	let res: NonEmptyList<T> = xs;	2✔
251	let i = n;	2✔
252	while (i > 0) {	2✔
253	const temp = tail(res);	2✔
254
255	if (is_null(temp)) {	2✔
256	throw new GeneralRuntimeError(`${list_ref.name}: Index ${n} is out of bounds.`);	1✔
257	}
258
259	res = temp;	1✔
260	i--;	1✔
261	}
262
263	return head(res);	1✔
264	}
265
266	/**
267	* Calls the provided function on each element of the provided list, and returns
268	* a new list containing the results
269	*/
270	export function map<T, U>(op: (each: T) => U, sequence: List<T>): List<U> {
271	return accumulate((each, result) => pair(op(each), result), list(), sequence);	3✔
272	}
273
274	/**
275	* Returns the first postfix sublist that starts with the given element `v`. If
276	* the element is not in `xs`, returns an empty list.
277	*/
278	export function member<T>(v: T, xs: List<T>): List<T> {
279	return is_null(xs) ? null : v === head(xs) ? xs : member(v, tail(xs));	12✔
280	}
281
282	/**
283	* Removes the first instance of `v` in the given List `xs`.
284	*/
285	export function remove<T>(v: T, xs: List<T>): List<T> {
286	if (is_null(xs)) return xs;	11✔
287
288	const current = head(xs);	10✔
289	if (current === v) return tail(xs);	10✔
290
291	return pair(head(xs), remove(v, tail(xs)));	6✔
292	}
293
294	/**
295	* Removes all instances of `v` from the given list `xs`.
296	*/
297	export function remove_all<T>(v: T, xs: List<T>): List<T> {
298	return filter(x => x !== v, xs);	12✔
299	}
300
301	/**
302	* Reverses the given list `xs`.
303	*/
304	export function reverse<T>(xs: List<T>): List<T> {
305	function $reverse(original: List<T>, reversed: List<T>): List<T> {
306	return is_null(original) ? reversed : $reverse(tail(original), pair(head(original), reversed));	5✔
307	}
308
309	return $reverse(xs, null);	2✔
310	}
311
312	export function rawDisplayList(
313	display: (v: Value, ...s: string[]) => Value,
314	xs: Value,
315	prepend: string,
316	) {
317	const visited: Set<Value> = new Set(); // Everything is put into this set, values, arrays, and even objects if they exist	18✔
318	const asListObjects: Map<NonEmptyList<Value>, NonEmptyList<Value> \| ListObject> = new Map(); // maps original list nodes to new list nodes	18✔
319
320	// We will convert list-like structures in xs to ListObject.
321	class ListObject implements ArrayLike {
322	replPrefix = 'list(';	415✔
323	replSuffix = ')';	415✔
324	replArrayContents(): Value[] {
325	return list_to_vector(this.listNode);	84✔
326	}
327
328	constructor(readonly listNode: NonEmptyList<Value>) {}	415✔
329	}
330	function getListObject(curXs: Value): Value {
331	return asListObjects.get(curXs) \|\| curXs;	972✔
332	}
333
334	const pairsToProcess: Value[] = [xs];	18✔
335	// we need the guarantee that if there are any proper lists,
336	// then the nodes of the proper list appear as a subsequence of this array.
337	// We ensure this by always adding the tail after the current node is processed.
338	// This means that sometimes, we add the same pair more than once!
339	// But because we only process each pair once due to the visited check,
340	// and each pair can only contribute to at most 3 items in this array,
341	// this array has O(n) elements.
342	for (let i = 0; i < pairsToProcess.length; i++) {	18✔
343	const curXs = pairsToProcess[i];	972✔
344	if (visited.has(curXs)) {	972✔
345	continue;	369✔
346	}
347	visited.add(curXs);	603✔
348	if (!is_pair(curXs)) {	603✔
349	continue;	126✔
350	}
351	pairsToProcess.push(head(curXs), tail(curXs));	477✔
352	}
353
354	function isListObject(x: Value): x is NonEmptyList<Value> {
355	return asListObjects.has(x);	498✔
356	}
357
358	// go through pairs in reverse to ensure the dependencies are resolved first
359	while (pairsToProcess.length > 0) {	18✔
360	const curXs = pairsToProcess.pop();	972✔
361	if (!is_pair(curXs)) {	972✔
362	continue;	474✔
363	}
364	const h = head(curXs);	498✔
365	const t = tail(curXs);	498✔
366
367	let newXs: Value;
368	if (isListObject(t)) {	498✔
369	const newTail = asListObjects.get(t)!;	376✔
370	newXs =	376✔
371	is_null(newTail) \|\| newTail instanceof ListObject ? new ListObject(pair(h, t)) : pair(h, t);	1,128✔
372	} else {
373	newXs = is_null(t) ? new ListObject(pair(h, t)) : pair(h, t);	122✔
374	}
375
376	// @ts-ignore
377	asListObjects.set(curXs, newXs);	498✔
378	}
379
380	for (const curXs of asListObjects.values()) {	18✔
381	if (is_pair(curXs)) {	477✔
382	set_head(curXs, getListObject(head(curXs)));	65✔
383	set_tail(curXs, getListObject(tail(curXs)));	65✔
384	} else if (curXs instanceof ListObject) {	412!
385	set_head(curXs.listNode, getListObject(head(curXs.listNode)));	412✔
386	let newTail = getListObject(tail(curXs.listNode));	412✔
387	if (newTail instanceof ListObject) {	412✔
388	newTail = newTail.listNode;	331✔
389	}
390	set_tail(curXs.listNode, newTail);	412✔
391	}
392	}
393	display(getListObject(xs), prepend);	18✔
394	return xs;	18✔
395	}

source-academy / js-slang / 24868044425

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous