23995741899

Committed 05 Apr 2026 06:14AM UTC coverage: 77.093% (+0.002%) from 77.091%

Build # 23995741899

Build Type

push

github

Committed by

web-flow

Commit Message

Upgrade to TypeScript 6 and Prettier improvements (#1936)

* Upgrade TypeScript to v6

* Fix import source

* Fix tsconfig

* Fix preexisting type errors

* Remove scm-slang

* Bump node types

* Fix tsconfig

* Fix node types specifier

* Enable trailing commas

* Enable semicolons

* Check and commit files with changed line numbers

* Update Yarn to 4.13.0

* Remove unneeded sicp package deps

Coverage Stats

3112 of 4282 branches covered (72.68%)

Branch coverage included in aggregate %.

3761 of 5218 new or added lines in 152 files covered. (72.08%)

26 existing lines in 9 files now uncovered.

7136 of 9011 relevant lines covered (79.19%)

175254.05 hits per line

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

93.04

/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 type { Value } from '../types';
import { type ArrayLike, stringify } from '../utils/stringify';

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

// 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<H, T>(x: H, xs: T): Pair<H, 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): unknown;
export function head(xs: unknown) {
  if (is_pair(xs)) {
    return xs[0];
  } else {
    throw new Error(
      `${head.name}(xs) expects a pair as argument xs, but encountered ${stringify(xs)}`,
    );
  }
}

/**
 * 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): unknown;
export function tail(xs: unknown) {
  if (is_pair(xs)) {
    return xs[1];
  } else {
    throw new Error(
      `${tail.name}(xs) expects a pair as argument xs, but encountered ${stringify(xs)}`,
    );
  }
}

/**
 * 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[]): List<T> {
  let theList = null;
  for (let i = elements.length - 1; i >= 0; i -= 1) {
    theList = pair(elements[i], theList);
  }
  return theList;
}

/**
 * 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 {
  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 = [];
  while (!is_null(lst)) {
    vector.push(head(lst));
    lst = tail(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);
}

/**
 * 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: unknown, x: any): void {
  if (is_pair(xs)) {
    xs[0] = x;
  } else {
    throw new Error(
      `${set_head.name}(xs,x) expects a pair as argument xs, but encountered ${stringify(xs)}`,
    );
  }
}

/**
 * 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: unknown, x: any): void {
  if (is_pair(xs)) {
    xs[1] = x;
  } else {
    throw new Error(
      `${set_tail.name}(xs,x) expects a pair as argument xs, but encountered ${stringify(xs)}`,
    );
  }
}

/**
 * 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);
}

/**
 * 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 Error(`${length.name}(xs) expects a list`);
  }

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

export function rawDisplayList(display: any, 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<unknown>, NonEmptyList<unknown> | 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[] {
      const result: Value[] = [];
      let curXs = this.listNode;
      while (curXs !== null) {
        result.push(head(curXs));
        curXs = tail(curXs);
      }
      return result;
    }
    listNode: List;

    constructor(listNode: List) {
      this.listNode = listNode;
    }
  }
  function getListObject(curXs: Value): Value {
    return asListObjects.get(curXs) || curXs;
  }

  const pairsToProcess: Value[] = [];
  let i = 0;
  pairsToProcess.push(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.
  while (i < pairsToProcess.length) {
    const curXs = pairsToProcess[i];
    i++;
    if (visited.has(curXs)) {
      continue;
    }
    visited.add(curXs);
    if (!is_pair(curXs)) {
      continue;
    }
    pairsToProcess.push(head(curXs), tail(curXs));
  }

  // 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);
    const newTail = getListObject(t); // the reason why we need the above guarantee
    const newXs =
      is_null(newTail) || newTail instanceof ListObject
        ? new ListObject(pair(h, t)) // tail is a proper list
        : pair(h, t); // it's not a proper list, make a copy of the pair so we can change references below
    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 type { Value } from '../types';
9	import { type ArrayLike, stringify } from '../utils/stringify';
10
11	export type Pair<H, T> = [H, T];
12	export type List<T = unknown> = null \| NonEmptyList<T>;
13	type NonEmptyList<T> = Pair<T, any>;
14
15	// array test works differently for Rhino and
16	// the Firefox environment (especially Web Console)
17	function array_test(x: unknown): x is unknown[] {
18	if (Array.isArray === undefined) {	11,307!
NEW 19	return x instanceof Array;	×
20	} else {
21	return Array.isArray(x);	11,307✔
22	}
23	}
24
25	/**
26	* constructs a pair using a two-element array\
27	* LOW-LEVEL FUNCTION, NOT SOURCE
28	*/
29	export function pair<H, T>(x: H, xs: T): Pair<H, T> {
30	return [x, xs];	4,929✔
31	}
32
33	/**
34	* returns true iff arg is a two-element array\
35	* LOW-LEVEL FUNCTION, NOT SOURCE
36	*/
37	export function is_pair(x: unknown): x is Pair<unknown, unknown> {
38	return array_test(x) && x.length === 2;	11,307✔
39	}
40
41	/**
42	* returns the first component of the given pair\
43	* LOW-LEVEL FUNCTION, NOT SOURCE
44	* @throws an exception if the argument is not a pair
45	*/
46	export function head<T>(xs: Pair<T, unknown> \| NonEmptyList<T>): T;
47	export function head(xs: unknown): unknown;
48	export function head(xs: unknown) {
49	if (is_pair(xs)) {	2,687✔
50	return xs[0];	2,674✔
51	} else {
52	throw new Error(	13✔
53	`${head.name}(xs) expects a pair as argument xs, but encountered ${stringify(xs)}`,
54	);
55	}
56	}
57
58	/**
59	* returns the second component of the given pair\
60	* LOW-LEVEL FUNCTION, NOT SOURCE
61	* @throws an exception if the argument is not a pair
62	*/
63	export function tail<T>(xs: NonEmptyList<T>): List<T>;
64	export function tail<T>(xs: Pair<unknown, T>): T;
65	export function tail(xs: unknown): unknown;
66	export function tail(xs: unknown) {
67	if (is_pair(xs)) {	3,842✔
68	return xs[1];	3,828✔
69	} else {
70	throw new Error(	14✔
71	`${tail.name}(xs) expects a pair as argument xs, but encountered ${stringify(xs)}`,
72	);
73	}
74	}
75
76	/**
77	* returns true if arg is exactly null\
78	* LOW-LEVEL FUNCTION, NOT SOURCE
79	*/
80	export function is_null(xs: unknown): xs is null {
81	return xs === null;	2,372✔
82	}
83
84	/**
85	* makes a list out of its arguments\
86	* LOW-LEVEL FUNCTION, NOT SOURCE
87	*/
88	export function list<T>(...elements: T[]): List<T> {
89	let theList = null;	897✔
90	for (let i = elements.length - 1; i >= 0; i -= 1) {	897✔
91	theList = pair(elements[i], theList);	2,184✔
92	}
93	return theList;	897✔
94	}
95
96	/**
97	* recurses down the list and checks that it ends with the empty list null\
98	* LOW-LEVEL FUNCTION, NOT SOURCE
99	*/
100	export function is_list(xs: unknown): xs is List {
101	while (is_pair(xs)) {	6✔
102	xs = tail(xs);	6✔
103	}
104	return is_null(xs);	6✔
105	}
106
107	/**
108	* returns vector that contains the elements of the argument list
109	* in the given order.\
110	* LOW-LEVEL FUNCTION, NOT SOURCE
111	* @throws an exception if the argument is not a list
112	*/
113	export function list_to_vector<T>(lst: List<T>): T[] {
114	const vector = [];	6✔
115	while (!is_null(lst)) {	6✔
116	vector.push(head(lst));	14✔
117	lst = tail(lst);	14✔
118	}
119	return vector;	6✔
120	}
121
122	/**
123	* returns a list that contains the elements of the argument vector
124	* in the given order\
125	* LOW-LEVEL FUNCTION, NOT SOURCE
126	* @throws an exception if the argument is not a vector
127	*/
128	export function vector_to_list<T>(vector: T[]): List<T> {
129	return list(...vector);	782✔
130	}
131
132	/**
133	* changes the head of given pair xs to be x\
134	* LOW-LEVEL FUNCTION, NOT SOURCE
135	* @throws an exception if the argument is not a pair
136	*/
137	export function set_head(xs: unknown, x: any): void {
138	if (is_pair(xs)) {	480✔
139	xs[0] = x;	478✔
140	} else {
141	throw new Error(	2✔
142	`${set_head.name}(xs,x) expects a pair as argument xs, but encountered ${stringify(xs)}`,
143	);
144	}
145	}
146
147	/**
148	* changes the tail of given pair xs to be x\
149	* LOW-LEVEL FUNCTION, NOT SOURCE
150	* @throws an exception if the argument is not a pair
151	*/
152	export function set_tail(xs: unknown, x: any): void {
153	if (is_pair(xs)) {	499✔
154	xs[1] = x;	497✔
155	} else {
156	throw new Error(	2✔
157	`${set_tail.name}(xs,x) expects a pair as argument xs, but encountered ${stringify(xs)}`,
158	);
159	}
160	}
161
162	/**
163	* Accumulate applies given operation op to elements of a list
164	* in a right-to-left order, first apply op to the last element
165	* and an initial element, resulting in r1, then to the second-last
166	* element and r1, resulting in r2, etc, and finally to the first element
167	* and r_n-1, where n is the length of the list. `accumulate(op,zero,list(1,2,3))`
168	* results in `op(1, op(2, op(3, zero)))`
169	*/
170	export function accumulate<T, U>(op: (each: T, result: U) => U, initial: U, sequence: List<T>): U {
171	// Use CPS to prevent stack overflow
172	function $accumulate(xs: typeof sequence, cont: (each: U) => U): U {
173	return is_null(xs) ? cont(initial) : $accumulate(tail(xs), x => cont(op(head(xs), x)));	9✔
174	}
175	return $accumulate(sequence, x => x);	2✔
176	}
177
178	/**
179	* returns the length of a List xs. Throws an exception if xs is not a List
180	*/
181	export function length(xs: unknown): number {
182	if (!is_list(xs)) {	×
NEW 183	throw new Error(`${length.name}(xs) expects a list`);	×
184	}
185
NEW 186	return accumulate((_, total) => total + 1, 0, xs);	×
187	}
188
189	export function rawDisplayList(display: any, xs: Value, prepend: string) {
190	const visited: Set<Value> = new Set(); // Everything is put into this set, values, arrays, and even objects if they exist	18✔
191	const asListObjects: Map<NonEmptyList<unknown>, NonEmptyList<unknown> \| ListObject> = new Map(); // maps original list nodes to new list nodes	18✔
192
193	// We will convert list-like structures in xs to ListObject.
194	class ListObject implements ArrayLike {
195	replPrefix = 'list(';	415✔
196	replSuffix = ')';	415✔
197	replArrayContents(): Value[] {
198	const result: Value[] = [];	84✔
199	let curXs = this.listNode;	84✔
200	while (curXs !== null) {	84✔
201	result.push(head(curXs));	415✔
202	curXs = tail(curXs);	415✔
203	}
204	return result;	84✔
205	}
206	listNode: List;
207
208	constructor(listNode: List) {
209	this.listNode = listNode;	415✔
210	}
211	}
212	function getListObject(curXs: Value): Value {
213	return asListObjects.get(curXs) \|\| curXs;	1,470✔
214	}
215
216	const pairsToProcess: Value[] = [];	18✔
217	let i = 0;	18✔
218	pairsToProcess.push(xs);	18✔
219	// we need the guarantee that if there are any proper lists,
220	// then the nodes of the proper list appear as a subsequence of this array.
221	// We ensure this by always adding the tail after the current node is processed.
222	// This means that sometimes, we add the same pair more than once!
223	// But because we only process each pair once due to the visited check,
224	// and each pair can only contribute to at most 3 items in this array,
225	// this array has O(n) elements.
226	while (i < pairsToProcess.length) {	18✔
227	const curXs = pairsToProcess[i];	972✔
228	i++;	972✔
229	if (visited.has(curXs)) {	972✔
230	continue;	369✔
231	}
232	visited.add(curXs);	603✔
233	if (!is_pair(curXs)) {	603✔
234	continue;	126✔
235	}
236	pairsToProcess.push(head(curXs), tail(curXs));	477✔
237	}
238
239	// go through pairs in reverse to ensure the dependencies are resolved first
240	while (pairsToProcess.length > 0) {	18✔
241	const curXs = pairsToProcess.pop();	972✔
242	if (!is_pair(curXs)) {	972✔
243	continue;	474✔
244	}
245	const h = head(curXs);	498✔
246	const t = tail(curXs);	498✔
247	const newTail = getListObject(t); // the reason why we need the above guarantee	498✔
248	const newXs =
249	is_null(newTail) \|\| newTail instanceof ListObject	498✔
250	? new ListObject(pair(h, t)) // tail is a proper list
251	: pair(h, t); // it's not a proper list, make a copy of the pair so we can change references below
252	asListObjects.set(curXs, newXs);	972✔
253	}
254
255	for (const curXs of asListObjects.values()) {	18✔
256	if (is_pair(curXs)) {	477✔
257	set_head(curXs, getListObject(head(curXs)));	65✔
258	set_tail(curXs, getListObject(tail(curXs)));	65✔
259	} else if (curXs instanceof ListObject) {	412!
260	set_head(curXs.listNode, getListObject(head(curXs.listNode)));	412✔
261	let newTail = getListObject(tail(curXs.listNode));	412✔
262	if (newTail instanceof ListObject) {	412✔
263	newTail = newTail.listNode;	331✔
264	}
265	set_tail(curXs.listNode, newTail);	412✔
266	}
267	}
268	display(getListObject(xs), prepend);	18✔
269	return xs;	18✔
270	}

source-academy / js-slang / 23995741899

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