4591476433

Build Type

push

github

Committed by GitHub

Commit Message

Make stdlib available to modules (#1388)

Run Details

3486 of 4560 branches covered (76.45%)

Branch coverage included in aggregate %.

173 of 173 new or added lines in 17 files covered. (100.0%)

10321 of 11973 relevant lines covered (86.2%)

136574.04 hits per line

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

91.34

/src/stdlib/list.ts

import { Value } from '../types'
import { ArrayLike, stringify } from '../utils/stringify'

// 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
export type Pair<H, T> = [H, T]
export type List = null | NonEmptyList
type NonEmptyList = Pair<any, any>

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

// pair 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]
}

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

// head returns the first component of the given pair,
// throws an exception if the argument is not a pair
// LOW-LEVEL FUNCTION, NOT SOURCE
export function head(xs: any) {
  if (is_pair(xs)) {
    return xs[0]
  } else {
    throw new Error('head(xs) expects a pair as argument xs, but encountered ' + stringify(xs))
  }
}

// tail returns the second component of the given pair
// throws an exception if the argument is not a pair
// LOW-LEVEL FUNCTION, NOT SOURCE
export function tail(xs: any) {
  if (is_pair(xs)) {
    return xs[1]
  } else {
    throw new Error('tail(xs) expects a pair as argument xs, but encountered ' + stringify(xs))
  }
}

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

// list makes a list out of its arguments
// LOW-LEVEL FUNCTION, NOT SOURCE
export function list(...elements: any[]): List {
  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: List) {
  while (is_pair(xs)) {
    xs = tail(xs)
  }
  return is_null(xs)
}

// list_to_vector returns vector that contains the elements of the argument list
// in the given order.
// list_to_vector throws an exception if the argument is not a list
// LOW-LEVEL FUNCTION, NOT SOURCE
export function list_to_vector(lst: List) {
  const vector = []
  while (!is_null(lst)) {
    vector.push(head(lst))
    lst = tail(lst)
  }
  return vector
}

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

// set_head(xs,x) changes the head of given pair xs to be x,
// throws an exception if the argument is not a pair
// LOW-LEVEL FUNCTION, NOT SOURCE

export function set_head(xs: any, x: any) {
  if (is_pair(xs)) {
    xs[0] = x
    return undefined
  } else {
    throw new Error(
      'set_head(xs,x) expects a pair as argument xs, but encountered ' + stringify(xs)
    )
  }
}

// set_tail(xs,x) changes the tail of given pair xs to be x,
// throws an exception if the argument is not a pair
// LOW-LEVEL FUNCTION, NOT SOURCE

export function set_tail(xs: any, x: any) {
  if (is_pair(xs)) {
    xs[1] = x
    return undefined
  } else {
    throw new Error(
      'set_tail(xs,x) expects a pair as argument xs, but encountered ' + stringify(xs)
    )
  }
}

export function accumulate<T, U>(acc: (each: T, result: U) => any, init: U, xs: List): U {
  const recurser = (xs: List, result: U): U => {
    if (is_null(xs)) return result

    return recurser(tail(xs), acc(head(xs), result))
  }

  return recurser(xs, init)
}

export function length(xs: List): number {
  if (!is_list(xs)) {
    throw new Error('length(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, NonEmptyList | 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	import { Value } from '../types'
2	import { ArrayLike, stringify } from '../utils/stringify'	62✔
3
4	// list.ts: Supporting lists in the Scheme style, using pairs made
5	// up of two-element JavaScript array (vector)
6	// Author: Martin Henz
7	// Translated to TypeScript by Evan Sebastian
8	export type Pair<H, T> = [H, T]
9	export type List = null \| NonEmptyList
10	type NonEmptyList = Pair<any, any>
11
12	// array test works differently for Rhino and
13	// the Firefox environment (especially Web Console)
14	function array_test(x: any) {
15	if (Array.isArray === undefined) {	68,506!
16	return x instanceof Array	×
17	} else {
18	return Array.isArray(x)	68,506✔
19	}
20	}
21
22	// pair constructs a pair using a two-element array
23	// LOW-LEVEL FUNCTION, NOT SOURCE
24	export function pair<H, T>(x: H, xs: T): Pair<H, T> {	62✔
25	return [x, xs]	26,839✔
26	}
27
28	// is_pair returns true iff arg is a two-element array
29	// LOW-LEVEL FUNCTION, NOT SOURCE
30	export function is_pair(x: any) {	62✔
31	return array_test(x) && x.length === 2	68,506✔
32	}
33
34	// head returns the first component of the given pair,
35	// throws an exception if the argument is not a pair
36	// LOW-LEVEL FUNCTION, NOT SOURCE
37	export function head(xs: any) {	62✔
38	if (is_pair(xs)) {	25,274✔
39	return xs[0]	25,251✔
40	} else {
41	throw new Error('head(xs) expects a pair as argument xs, but encountered ' + stringify(xs))	23✔
42	}
43	}
44
45	// tail returns the second component of the given pair
46	// throws an exception if the argument is not a pair
47	// LOW-LEVEL FUNCTION, NOT SOURCE
48	export function tail(xs: any) {	62✔
49	if (is_pair(xs)) {	33,188✔
50	return xs[1]	33,162✔
51	} else {
52	throw new Error('tail(xs) expects a pair as argument xs, but encountered ' + stringify(xs))	26✔
53	}
54	}
55
56	// is_null returns true if arg is exactly null
57	// LOW-LEVEL FUNCTION, NOT SOURCE
58	export function is_null(xs: List) {	62✔
59	return xs === null	38,309✔
60	}
61
62	// list makes a list out of its arguments
63	// LOW-LEVEL FUNCTION, NOT SOURCE
64	export function list(...elements: any[]): List {	62✔
65	let theList = null	4,940✔
66	for (let i = elements.length - 1; i >= 0; i -= 1) {	4,940✔
67	theList = pair(elements[i], theList)	20,155✔
68	}
69	return theList	4,940✔
70	}
71
72	// recurses down the list and checks that it ends with the empty list null
73	// LOW-LEVEL FUNCTION, NOT SOURCE
74	export function is_list(xs: List) {	62✔
75	while (is_pair(xs)) {	11✔
76	xs = tail(xs)	13✔
77	}
78	return is_null(xs)	11✔
79	}
80
81	// list_to_vector returns vector that contains the elements of the argument list
82	// in the given order.
83	// list_to_vector throws an exception if the argument is not a list
84	// LOW-LEVEL FUNCTION, NOT SOURCE
85	export function list_to_vector(lst: List) {	62✔
86	const vector = []	2✔
87	while (!is_null(lst)) {	2✔
88	vector.push(head(lst))	6✔
89	lst = tail(lst)	6✔
90	}
91	return vector	2✔
92	}
93
94	// vector_to_list returns a list that contains the elements of the argument vector
95	// in the given order.
96	// vector_to_list throws an exception if the argument is not a vector
97	// LOW-LEVEL FUNCTION, NOT SOURCE
98	export function vector_to_list(vector: any[]): List {	62✔
99	return list(...vector)	1,446✔
100	}
101
102	// set_head(xs,x) changes the head of given pair xs to be x,
103	// throws an exception if the argument is not a pair
104	// LOW-LEVEL FUNCTION, NOT SOURCE
105
106	export function set_head(xs: any, x: any) {	62✔
107	if (is_pair(xs)) {	903✔
108	xs[0] = x	901✔
109	return undefined	901✔
110	} else {
111	throw new Error(	2✔
112	'set_head(xs,x) expects a pair as argument xs, but encountered ' + stringify(xs)
113	)
114	}
115	}
116
117	// set_tail(xs,x) changes the tail of given pair xs to be x,
118	// throws an exception if the argument is not a pair
119	// LOW-LEVEL FUNCTION, NOT SOURCE
120
121	export function set_tail(xs: any, x: any) {	62✔
122	if (is_pair(xs)) {	942✔
123	xs[1] = x	940✔
124	return undefined	940✔
125	} else {
126	throw new Error(	2✔
127	'set_tail(xs,x) expects a pair as argument xs, but encountered ' + stringify(xs)
128	)
129	}
130	}
131
132	export function accumulate<T, U>(acc: (each: T, result: U) => any, init: U, xs: List): U {	62✔
133	const recurser = (xs: List, result: U): U => {	×
134	if (is_null(xs)) return result	×
135
136	return recurser(tail(xs), acc(head(xs), result))	×
137	}
138
139	return recurser(xs, init)	×
140	}
141
142	export function length(xs: List): number {	62✔
143	if (!is_list(xs)) {	×
144	throw new Error('length(xs) expects a list')	×
145	}
146
147	return accumulate((_, total) => total + 1, 0, xs)	×
148	}
149
150	export function rawDisplayList(display: any, xs: Value, prepend: string) {	62✔
151	const visited: Set<Value> = new Set() // Everything is put into this set, values, arrays, and even objects if they exist	36✔
152	const asListObjects: Map<NonEmptyList, NonEmptyList \| ListObject> = new Map() // maps original list nodes to new list nodes	36✔
153
154	// We will convert list-like structures in xs to ListObject.
155	class ListObject implements ArrayLike {
156	replPrefix = 'list('	775✔
157	replSuffix = ')'	775✔
158	replArrayContents(): Value[] {
159	const result: Value[] = []	168✔
160	let curXs = this.listNode	168✔
161	while (curXs !== null) {	168✔
162	result.push(head(curXs))	775✔
163	curXs = tail(curXs)	775✔
164	}
165	return result	168✔
166	}
167	listNode: List
168
169	constructor(listNode: List) {
170	this.listNode = listNode	775✔
171	}
172	}
173	function getListObject(curXs: Value): Value {
174	return asListObjects.get(curXs) \|\| curXs	2,775✔
175	}
176
177	const pairsToProcess: Value[] = []	36✔
178	let i = 0	36✔
179	pairsToProcess.push(xs)	36✔
180	// we need the guarantee that if there are any proper lists,
181	// then the nodes of the proper list appear as a subsequence of this array.
182	// We ensure this by always adding the tail after the current node is processed.
183	// This means that sometimes, we add the same pair more than once!
184	// But because we only process each pair once due to the visited check,
185	// and each pair can only contribute to at most 3 items in this array,
186	// this array has O(n) elements.
187	while (i < pairsToProcess.length) {	36✔
188	const curXs = pairsToProcess[i]	1,834✔
189	i++	1,834✔
190	if (visited.has(curXs)) {	1,834✔
191	continue	710✔
192	}
193	visited.add(curXs)	1,124✔
194	if (!is_pair(curXs)) {	1,124✔
195	continue	225✔
196	}
197	pairsToProcess.push(head(curXs), tail(curXs))	899✔
198	}
199
200	// go through pairs in reverse to ensure the dependencies are resolved first
201	while (pairsToProcess.length > 0) {	36✔
202	const curXs = pairsToProcess.pop()	1,834✔
203	if (!is_pair(curXs)) {	1,834✔
204	continue	893✔
205	}
206	const h = head(curXs)	941✔
207	const t = tail(curXs)	941✔
208	const newTail = getListObject(t) // the reason why we need the above guarantee	941✔
209	const newXs =
210	is_null(newTail) \|\| newTail instanceof ListObject	941✔
211	? new ListObject(pair(h, t)) // tail is a proper list	941✔
212	: pair(h, t) // it's not a proper list, make a copy of the pair so we can change references below
213	asListObjects.set(curXs, newXs)	941✔
214	}
215
216	for (const curXs of asListObjects.values()) {	36✔
217	if (is_pair(curXs)) {	899✔
218	set_head(curXs, getListObject(head(curXs)))	130✔
219	set_tail(curXs, getListObject(tail(curXs)))	130✔
220	} else if (curXs instanceof ListObject) {	769✔
221	set_head(curXs.listNode, getListObject(head(curXs.listNode)))	769✔
222	let newTail = getListObject(tail(curXs.listNode))	769✔
223	if (newTail instanceof ListObject) {	769✔
224	newTail = newTail.listNode	607✔
225	}
226	set_tail(curXs.listNode, newTail)	769✔
227	}
228	}
229	display(getListObject(xs), prepend)	36✔
230	return xs	36✔
231	}

source-academy / js-slang / 4591476433

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