11929582114

Committed 20 Nov 2024 08:33AM UTC coverage: 81.654% (+0.04%) from 81.61%

Build # 11929582114

Build Type

Pull #1728

github

Committed by

web-flow

Commit Message

Merge c3f0269a5 into 665233634

Pull Request Pull Request #1728: Implement the CSET machine, along with macros

Run Details

3654 of 4864 branches covered (75.12%)

Branch coverage included in aggregate %.

491 of 596 new or added lines in 11 files covered. (82.38%)

1 existing line in 1 file now uncovered.

11474 of 13663 relevant lines covered (83.98%)

143610.35 hits per line

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

64.84

/src/cse-machine/patterns.ts

// a single transformer stored within the transformers component
// will be henceforth referred to as a "transformer".
// it consists of a set of literals used as additional syntax,
// a pattern (for a list to match against)
// and a final template (for the list to be transformed into).
import { List, Pair } from '../stdlib/list'
import { _Symbol } from '../alt-langs/scheme/scm-slang/src/stdlib/base'
import {
  arrayToImproperList,
  arrayToList,
  flattenList,
  improperListLength,
  isImproperList,
  isPair,
  isList
} from './macro-utils'
import { atomic_equals, is_number } from '../alt-langs/scheme/scm-slang/src/stdlib/core-math'

// a single pattern stored within the patterns component
// may have several transformers attributed to it.
export class Transformer {
  literals: string[]
  pattern: List
  template: List

  constructor(literals: string[], pattern: List, template: List) {
    this.literals = literals
    this.pattern = pattern
    this.template = template
  }
}

// given a matching transformer,
// the macro_transform() function will transform a list
// into the template of the transformer.
export function macro_transform(input: any, transformer: Transformer): any {
  const collected = collect(input, transformer.pattern, transformer.literals)
  return transform(transformer.template, collected)
}

// we use the match() function to match a list against a pattern and literals
// and verify if it is a match.
export function match(input: any, pattern: any, literals: string[]): boolean {
  // we should compare the input and pattern based on the possible forms of pattern:
  // 1. an identifier
  // 2. a literal such as null, a number, a string, or a boolean
  // 3. (<pattern>+)
  // 4. (<pattern>+ . <pattern>)
  // 5. (<pattern>+ ... <pattern>+)
  // 6. (<pattern>+ ... <pattern>+ . <pattern>)

  // case 1
  if (pattern instanceof _Symbol && literals.includes(pattern.sym)) {
    return input instanceof _Symbol && input.sym === pattern.sym
  }

  if (pattern instanceof _Symbol) {
    return !(input instanceof _Symbol && literals.includes(input.sym))
  }

  // case 2
  if (pattern === null) {
    return input === null
  }

  if (is_number(pattern)) {
    return is_number(input) && atomic_equals(input, pattern)
  }

  if (typeof pattern === 'string' || typeof pattern === 'boolean' || typeof pattern === 'number') {
    return input === pattern
  }

  // case 3 and 5
  if (isList(pattern)) {
    if (!isList(input)) {
      return false
    }
    const inputList = flattenList(input)
    const patternList = flattenList(pattern)
    // there can be a single ellepsis in the pattern, but it must be behind some element.
    // scan the pattern for the ... symbol.
    // we will need the position of the ... symbol to compare the front and back of the list.
    const ellipsisIndex = patternList.findIndex(
      elem => elem instanceof _Symbol && elem.sym === '...'
    )

    // case 5
    if (ellipsisIndex !== -1) {
      // if the input is shorter than the pattern (minus the ... and matching pattern), it can't match.
      if (inputList.length < patternList.length - 2) {
        return false
      }

      const frontPatternLength = ellipsisIndex - 1
      const ellipsisPattern = patternList[ellipsisIndex - 1]
      const backPatternLength = patternList.length - ellipsisIndex - 1

      // compare the front of the list with the front of the pattern as per normal
      for (let i = 0; i < frontPatternLength; i++) {
        if (!match(inputList[i], patternList[i], literals)) {
          return false
        }
      }

      // compare the items that should be captured by the ellipsis
      for (let i = frontPatternLength; i < inputList.length - backPatternLength; i++) {
        if (!match(inputList[i], ellipsisPattern, literals)) {
          return false
        }
      }

      // now we can compare the back of the list with the rest of the patterns
      for (let i = inputList.length - backPatternLength; i < inputList.length; i++) {
        if (
          !match(inputList[i], patternList[i - (inputList.length - patternList.length)], literals)
        ) {
          return false
        }
      }

      // else all is good and return true
      return true
    }

    // case 3
    if (inputList.length !== patternList.length) {
      return false
    }
    for (let i = 0; i < inputList.length; i++) {
      if (!match(inputList[i], patternList[i], literals)) {
        return false
      }
    }
    return true
  }

  // case 4 and 6
  if (isImproperList(pattern)) {
    // if the input is not a pair, it can't match.
    if (!isPair(input)) {
      return false
    }

    let currEllipsisPattern
    let currentPattern = pattern
    let currentInput = input
    let ellipsisFound = false

    // iterate through currentPattern while it is a pair
    while (isPair(currentPattern)) {
      if (!isPair(currentInput)) {
        return false
      }
      const [headPattern, tailPattern] = currentPattern
      const [headInput, tailInput] = currentInput

      // we can lookahead to see if the ellipsis symbol is the next pattern element.
      if (
        isPair(tailPattern) &&
        tailPattern[0] instanceof _Symbol &&
        tailPattern[0].sym === '...'
      ) {
        ellipsisFound = true
        currEllipsisPattern = headPattern
        // skip ahead to the (cddr pattern) for the next iteration
        // the cddr is what "remains" of the pattern after the ellipsis.
        currentPattern = tailPattern[1]
        continue
      }

      // if the ellipis is found, continue to match the pattern until the ellipsis is exhausted.
      // (this is done by comparing the length of the input to the length of the remaining pattern)
      if (ellipsisFound && improperListLength(currentInput) > improperListLength(currentPattern)) {
        // match the headInput with the currEllipsisPattern
        if (!match(headInput, currEllipsisPattern, literals)) {
          return false
        }
        currentInput = tailInput // move to the next input
        continue
      }

      // if the ellipsis symbol is not found, or we have already matched the ellipsis pattern,
      // match the headInput with the headPattern
      if (!match(headInput, headPattern, literals)) {
        return false
      }
      currEllipsisPattern = headPattern
      currentPattern = tailPattern
      currentInput = tailInput
    }
    // now we can compare the last item in the pattern with the rest of the input
    return match(currentInput, currentPattern, literals)
  }

  return false
}

// once a pattern is matched, we need to collect all of the matched variables.
// ONLY called on matching patterns.
export function collect(input: any, pattern: any, literals: string[]): Map<string, any[]> {
  const collected = new Map<string, (List | _Symbol)[]>()
  // we should compare the input and pattern based on the possible forms of pattern:
  // 1. an identifier
  // 2. a literal such as null, a number, a string, or a boolean
  // 3. (<pattern>+)
  // 4. (<pattern>+ . <pattern>)
  // 5. (<pattern>+ ... <pattern>+)
  // 6. (<pattern>+ ... <pattern>+ . <pattern>)

  // case 1
  if (pattern instanceof _Symbol && !literals.includes(pattern.sym)) {
    if (!collected.has(pattern.sym)) {
      collected.set(pattern.sym, [])
    }
    collected.get(pattern.sym)?.push(input)
    return collected
  }

  // case 2
  if (pattern === null) {
    return collected
  }

  if (is_number(pattern)) {
    return collected
  }

  if (typeof pattern === 'string' || typeof pattern === 'boolean' || typeof pattern === 'number') {
    return collected
  }

  // cases 3 and 5
  if (isList(pattern)) {
    const inputList = flattenList(input)
    const patternList = flattenList(pattern)
    const ellipsisIndex = patternList.findIndex(
      elem => elem instanceof _Symbol && elem.sym === '...'
    )

    // case 5
    if (ellipsisIndex !== -1) {
      const frontPatternLength = ellipsisIndex - 1
      const ellipsisPattern = patternList[ellipsisIndex - 1]
      const backPatternLength = patternList.length - ellipsisIndex - 1

      for (let i = 0; i < frontPatternLength; i++) {
        const val = collect(inputList[i], patternList[i], literals)
        for (let [key, value] of val) {
          if (!collected.has(key)) {
            collected.set(key, [])
          }
          collected.get(key)?.push(...value)
        }
      }

      for (let i = frontPatternLength; i < inputList.length - backPatternLength; i++) {
        const val = collect(inputList[i], ellipsisPattern, literals)
        for (let [key, value] of val) {
          if (!collected.has(key)) {
            collected.set(key, [])
          }
          collected.get(key)?.push(...value)
        }
      }

      for (let i = inputList.length - backPatternLength; i < inputList.length; i++) {
        const val = collect(
          inputList[i],
          patternList[i - (inputList.length - patternList.length)],
          literals
        )
        for (let [key, value] of val) {
          if (!collected.has(key)) {
            collected.set(key, [])
          }
          collected.get(key)?.push(...value)
        }
      }
      return collected
    }

    // case 3
    for (let i = 0; i < inputList.length; i++) {
      const val = collect(inputList[i], patternList[i], literals)
      for (let [key, value] of val) {
        if (!collected.has(key)) {
          collected.set(key, [])
        }
        collected.get(key)?.push(...value)
      }
    }
    return collected
  }

  // case 4 and 6
  if (isImproperList(pattern)) {
    let currEllipsisPattern
    let currentPattern = pattern
    let currentInput = input
    let ellipsisFound = false

    // iterate through currentPattern while it is a pair
    while (isPair(currentPattern)) {
      const [headPattern, tailPattern] = currentPattern
      const [headInput, tailInput] = currentInput

      // we can lookahead to see if the ellipsis symbol is the next pattern element.
      if (
        isPair(tailPattern) &&
        tailPattern[0] instanceof _Symbol &&
        tailPattern[0].sym === '...'
      ) {
        ellipsisFound = true
        currEllipsisPattern = headPattern
        // skip ahead to the (cddr pattern) for the next iteration
        // the cddr is what "remains" of the pattern after the ellipsis.
        currentPattern = tailPattern[1]
        continue
      }

      // if the ellipis is found, continue to match the pattern until the ellipsis is exhausted.
      // (this is done by comparing the length of the input to the length of the remaining pattern)
      // it may be the case that the ellipsis pattern is not matched at all.
      if (ellipsisFound && improperListLength(currentInput) > improperListLength(currentPattern)) {
        const val = collect(headInput, currEllipsisPattern, literals)
        for (let [key, value] of val) {
          if (!collected.has(key)) {
            collected.set(key, [])
          }
          collected.get(key)?.push(...value)
        }
        currentInput = tailInput // move to the next input
        continue
      }

      // if the ellipsis symbol is not found, or we have already matched the ellipsis pattern,
      // match the headInput with the headPattern
      const val = collect(headInput, headPattern, literals)
      for (let [key, value] of val) {
        if (!collected.has(key)) {
          collected.set(key, [])
        }
        collected.get(key)?.push(...value)
      }
      currEllipsisPattern = headPattern
      currentPattern = tailPattern
      currentInput = tailInput
    }
    // now we can compare the last item in the pattern with the rest of the input
    const val = collect(currentInput, currentPattern, literals)
    for (let [key, value] of val) {
      if (!collected.has(key)) {
        collected.set(key, [])
      }
      collected.get(key)?.push(...value)
    }
    return collected
  }

  return collected
}

// when matched against a pattern, we use the transform() function
// to transform the list into the template.
// returns a list, a pair, or any value, as determined by the template.
export function transform(
  template: any,
  collected: Map<string, any[]>,
  indexToCollect: number = 0
): any {
  // there are 5 possible forms of the template:
  // 1. an identifier
  // 2. a literal such as null, a number, a string, or a boolean
  // 3. (... <template>)
  // 4. (<element>+)
  // 5. (<element>+ . <template>)
  // where <element> is <template> | <template> ...

  // case 1
  if (template instanceof _Symbol) {
    if (collected.has(template.sym)) {
      // get the item from the collected list,
      // remove it from the collected list,
      // and return it.
      const item = (collected.get(template.sym) as any[])[indexToCollect]
      return item
    }
    return template
  }

  // case 2
  if (template === null) {
    return null
  }

  if (
    typeof template === 'string' ||
    typeof template === 'boolean' ||
    typeof template === 'number'
  ) {
    return template
  }

  if (is_number(template)) {
    return template
  }

  // case 3
  if (
    isList(template) &&
    template !== null &&
    template[0] instanceof _Symbol &&
    template[0].sym === '...'
  ) {
    // parser should ensure that the ellipsis is followed by a single value.
    // this value is the template to be used.
    // get the cadr of the template and return it.
    return template[1][0]
  }

  // collects all items in an ellipsis template to be used in the final list.
  // helper function for dealing with ellipsis templates.
  function deepFlatten(pair: Pair<any, any>): _Symbol[] {
    const items: _Symbol[] = []
    function flattenHelper(item: any) {
      if (item instanceof _Symbol && item.sym !== '...') {
        items.push(item)
      } else if (item === null) {
        return
      } else if (item instanceof Array && item.length === 2) {
        // based on the usage of (... <value>),
        // and our previous discussion on the viability
        // of ... within the ellipsis template
        // we can assume that any ellipsis used is used to halt macro expansion of <value>.
        if (item[0] instanceof _Symbol && item[0].sym === '...') {
          // do not collect any items here, this halts the collection
          return
        }
        // if its a pair, traverse both car and cdr
        flattenHelper(item[0])
        flattenHelper(item[1])
      }
    }
    flattenHelper(pair)
    return items
  }

  // case 4
  if (isList(template)) {
    const templateList = flattenList(template)
    const transformedList: any[] = []
    for (let i = 0; i < templateList.length; i++) {
      if (templateList[i] instanceof _Symbol && templateList[i].sym === '...') {
        // if the ellipsis symbol is found, we can skip ahead to the next template
        // as the ellipsis symbol is not used in the transformation.
        continue
      }
      // lookahead for the ellipsis symbol
      if (
        i + 1 < templateList.length &&
        templateList[i + 1] instanceof _Symbol &&
        templateList[i + 1].sym === '...'
      ) {
        const currEllipsisPattern = templateList[i]
        const items = deepFlatten(currEllipsisPattern)
        // add items to the transformed list
        // until the templates are exhausted.
        let currIndex = 0
        while (true) {
          // check if all items are exhausted
          let itemsAreExhausted = false
          for (let j = 0; j < items.length; j++) {
            if (!collected.has(items[j].sym)) {
              itemsAreExhausted = true
              break
            }
            if (
              collected.has(items[j].sym) &&
              currIndex >= (collected.get(items[j].sym) as any[]).length
            ) {
              itemsAreExhausted = true
              break
            }
          }
          if (itemsAreExhausted) {
            break
          }
          // apply the last ellipsis template again
          transformedList.push(transform(currEllipsisPattern, collected, currIndex))
          currIndex++
        }
        continue
      }
      transformedList.push(transform(templateList[i], collected))
    }
    return arrayToList(transformedList)
  }

  // case 5
  if (isImproperList(template)) {
    let currEllipsisPattern: any = undefined
    let currentPattern = template

    let collectedItems: any[] = []

    // iterate through currentPattern while it is a pair
    while (isPair(currentPattern)) {
      const [headPattern, tailPattern] = currentPattern

      // we can lookahead to see if the ellipsis symbol is the next pattern element.
      if (
        isPair(tailPattern) &&
        tailPattern[0] instanceof _Symbol &&
        tailPattern[0].sym === '...'
      ) {
        currEllipsisPattern = headPattern
        // skip ahead to the (cddr pattern) for the next iteration
        // the cddr is what "remains" of the pattern after the ellipsis.
        currentPattern = tailPattern[1]
        continue
      }

      // if a current ellipsis pattern exists, we continue collecting items from it until it is exhausted.
      // then we undefine the current ellipsis pattern.
      if (currEllipsisPattern !== undefined) {
        const items = deepFlatten(currEllipsisPattern)
        let currIndex = 0
        while (true) {
          // check if all items are exhausted
          let itemsAreExhausted = false
          for (let i = 0; i < items.length; i++) {
            if (!collected.has(items[i].sym)) {
              itemsAreExhausted = true
              break
            }
            if (
              collected.has(items[i].sym) &&
              currIndex >= (collected.get(items[i].sym) as any[]).length
            ) {
              itemsAreExhausted = true
              break
            }
          }
          if (itemsAreExhausted) {
            break
          }
          // add the ellipsis pattern to the collected items
          collectedItems.push(transform(currEllipsisPattern, collected, currIndex))
          currIndex++
        }
        currEllipsisPattern = undefined
        continue
      }
      collectedItems.push(transform(headPattern, collected))
      currentPattern = tailPattern
    }
    // now we can compare the last item in the pattern with the rest of the input
    const val = transform(currentPattern, collected)
    return arrayToImproperList(collectedItems, val)
  }
  return template
}

1	// a single transformer stored within the transformers component
2	// will be henceforth referred to as a "transformer".
3	// it consists of a set of literals used as additional syntax,
4	// a pattern (for a list to match against)
5	// and a final template (for the list to be transformed into).
6	import { List, Pair } from '../stdlib/list'
7	import { _Symbol } from '../alt-langs/scheme/scm-slang/src/stdlib/base'	80✔
8	import {	80✔
9	arrayToImproperList,
10	arrayToList,
11	flattenList,
12	improperListLength,
13	isImproperList,
14	isPair,
15	isList
16	} from './macro-utils'
17	import { atomic_equals, is_number } from '../alt-langs/scheme/scm-slang/src/stdlib/core-math'	80✔
18
19	// a single pattern stored within the patterns component
20	// may have several transformers attributed to it.
21	export class Transformer {	80✔
22	literals: string[]
23	pattern: List
24	template: List
25
26	constructor(literals: string[], pattern: List, template: List) {
27	this.literals = literals	476✔
28	this.pattern = pattern	476✔
29	this.template = template	476✔
30	}
31	}
32
33	// given a matching transformer,
34	// the macro_transform() function will transform a list
35	// into the template of the transformer.
36	export function macro_transform(input: any, transformer: Transformer): any {	80✔
37	const collected = collect(input, transformer.pattern, transformer.literals)	10✔
38	return transform(transformer.template, collected)	10✔
39	}
40
41	// we use the match() function to match a list against a pattern and literals
42	// and verify if it is a match.
43	export function match(input: any, pattern: any, literals: string[]): boolean {	80✔
44	// we should compare the input and pattern based on the possible forms of pattern:
45	// 1. an identifier
46	// 2. a literal such as null, a number, a string, or a boolean
47	// 3. (<pattern>+)
48	// 4. (<pattern>+ . <pattern>)
49	// 5. (<pattern>+ ... <pattern>+)
50	// 6. (<pattern>+ ... <pattern>+ . <pattern>)
51
52	// case 1
53	if (pattern instanceof _Symbol && literals.includes(pattern.sym)) {	104✔
54	return input instanceof _Symbol && input.sym === pattern.sym	1!
55	}
56
57	if (pattern instanceof _Symbol) {	103✔
58	return !(input instanceof _Symbol && literals.includes(input.sym))	50✔
59	}
60
61	// case 2
62	if (pattern === null) {	53✔
63	return input === null	5✔
64	}
65
66	if (is_number(pattern)) {	48!
NEW 67	return is_number(input) && atomic_equals(input, pattern)	×
68	}
69
70	if (typeof pattern === 'string' \|\| typeof pattern === 'boolean' \|\| typeof pattern === 'number') {	48✔
71	return input === pattern	9✔
72	}
73
74	// case 3 and 5
75	if (isList(pattern)) {	39✔
76	if (!isList(input)) {	28✔
77	return false	2✔
78	}
79	const inputList = flattenList(input)	26✔
80	const patternList = flattenList(pattern)	26✔
81	// there can be a single ellepsis in the pattern, but it must be behind some element.
82	// scan the pattern for the ... symbol.
83	// we will need the position of the ... symbol to compare the front and back of the list.
84	const ellipsisIndex = patternList.findIndex(	26✔
85	elem => elem instanceof _Symbol && elem.sym === '...'	75✔
86	)
87
88	// case 5
89	if (ellipsisIndex !== -1) {	26✔
90	// if the input is shorter than the pattern (minus the ... and matching pattern), it can't match.
91	if (inputList.length < patternList.length - 2) {	4!
NEW 92	return false	×
93	}
94
95	const frontPatternLength = ellipsisIndex - 1	4✔
96	const ellipsisPattern = patternList[ellipsisIndex - 1]	4✔
97	const backPatternLength = patternList.length - ellipsisIndex - 1	4✔
98
99	// compare the front of the list with the front of the pattern as per normal
100	for (let i = 0; i < frontPatternLength; i++) {	4✔
101	if (!match(inputList[i], patternList[i], literals)) {	4✔
102	return false	1✔
103	}
104	}
105
106	// compare the items that should be captured by the ellipsis
107	for (let i = frontPatternLength; i < inputList.length - backPatternLength; i++) {	3✔
108	if (!match(inputList[i], ellipsisPattern, literals)) {	5✔
109	return false	1✔
110	}
111	}
112
113	// now we can compare the back of the list with the rest of the patterns
114	for (let i = inputList.length - backPatternLength; i < inputList.length; i++) {	2✔
NEW 115	if (	×
116	!match(inputList[i], patternList[i - (inputList.length - patternList.length)], literals)
117	) {
NEW 118	return false	×
119	}
120	}
121
122	// else all is good and return true
123	return true	2✔
124	}
125
126	// case 3
127	if (inputList.length !== patternList.length) {	22!
NEW 128	return false	×
129	}
130	for (let i = 0; i < inputList.length; i++) {	22✔
131	if (!match(inputList[i], patternList[i], literals)) {	55✔
132	return false	8✔
133	}
134	}
135	return true	14✔
136	}
137
138	// case 4 and 6
139	if (isImproperList(pattern)) {	11✔
140	// if the input is not a pair, it can't match.
141	if (!isPair(input)) {	11✔
142	return false	5✔
143	}
144
145	let currEllipsisPattern
146	let currentPattern = pattern	6✔
147	let currentInput = input	6✔
148	let ellipsisFound = false	6✔
149
150	// iterate through currentPattern while it is a pair
151	while (isPair(currentPattern)) {	6✔
152	if (!isPair(currentInput)) {	6!
NEW 153	return false	×
154	}
155	const [headPattern, tailPattern] = currentPattern	6✔
156	const [headInput, tailInput] = currentInput	6✔
157
158	// we can lookahead to see if the ellipsis symbol is the next pattern element.
159	if (	6!
160	isPair(tailPattern) &&	6!
161	tailPattern[0] instanceof _Symbol &&
162	tailPattern[0].sym === '...'
163	) {
NEW 164	ellipsisFound = true	×
NEW 165	currEllipsisPattern = headPattern	×
166	// skip ahead to the (cddr pattern) for the next iteration
167	// the cddr is what "remains" of the pattern after the ellipsis.
NEW 168	currentPattern = tailPattern[1]	×
NEW 169	continue	×
170	}
171
172	// if the ellipis is found, continue to match the pattern until the ellipsis is exhausted.
173	// (this is done by comparing the length of the input to the length of the remaining pattern)
174	if (ellipsisFound && improperListLength(currentInput) > improperListLength(currentPattern)) {	6!
175	// match the headInput with the currEllipsisPattern
NEW 176	if (!match(headInput, currEllipsisPattern, literals)) {	×
NEW 177	return false	×
178	}
NEW 179	currentInput = tailInput // move to the next input	×
NEW 180	continue	×
181	}
182
183	// if the ellipsis symbol is not found, or we have already matched the ellipsis pattern,
184	// match the headInput with the headPattern
185	if (!match(headInput, headPattern, literals)) {	6!
NEW 186	return false	×
187	}
188	currEllipsisPattern = headPattern	6✔
189	currentPattern = tailPattern	6✔
190	currentInput = tailInput	6✔
191	}
192	// now we can compare the last item in the pattern with the rest of the input
193	return match(currentInput, currentPattern, literals)	6✔
194	}
195
NEW 196	return false	×
197	}
198
199	// once a pattern is matched, we need to collect all of the matched variables.
200	// ONLY called on matching patterns.
201	export function collect(input: any, pattern: any, literals: string[]): Map<string, any[]> {	80✔
202	const collected = new Map<string, (List \| _Symbol)[]>()	54✔
203	// we should compare the input and pattern based on the possible forms of pattern:
204	// 1. an identifier
205	// 2. a literal such as null, a number, a string, or a boolean
206	// 3. (<pattern>+)
207	// 4. (<pattern>+ . <pattern>)
208	// 5. (<pattern>+ ... <pattern>+)
209	// 6. (<pattern>+ ... <pattern>+ . <pattern>)
210
211	// case 1
212	if (pattern instanceof _Symbol && !literals.includes(pattern.sym)) {	54✔
213	if (!collected.has(pattern.sym)) {	35✔
214	collected.set(pattern.sym, [])	35✔
215	}
216	collected.get(pattern.sym)?.push(input)	35✔
217	return collected	35✔
218	}
219
220	// case 2
221	if (pattern === null) {	19✔
222	return collected	2✔
223	}
224
225	if (is_number(pattern)) {	17!
NEW 226	return collected	×
227	}
228
229	if (typeof pattern === 'string' \|\| typeof pattern === 'boolean' \|\| typeof pattern === 'number') {	17!
NEW 230	return collected	×
231	}
232
233	// cases 3 and 5
234	if (isList(pattern)) {	17✔
235	const inputList = flattenList(input)	13✔
236	const patternList = flattenList(pattern)	13✔
237	const ellipsisIndex = patternList.findIndex(	13✔
238	elem => elem instanceof _Symbol && elem.sym === '...'	37✔
239	)
240
241	// case 5
242	if (ellipsisIndex !== -1) {	13✔
243	const frontPatternLength = ellipsisIndex - 1	2✔
244	const ellipsisPattern = patternList[ellipsisIndex - 1]	2✔
245	const backPatternLength = patternList.length - ellipsisIndex - 1	2✔
246
247	for (let i = 0; i < frontPatternLength; i++) {	2✔
248	const val = collect(inputList[i], patternList[i], literals)	2✔
249	for (let [key, value] of val) {	2✔
250	if (!collected.has(key)) {	3✔
251	collected.set(key, [])	3✔
252	}
253	collected.get(key)?.push(...value)	3✔
254	}
255	}
256
257	for (let i = frontPatternLength; i < inputList.length - backPatternLength; i++) {	2✔
258	const val = collect(inputList[i], ellipsisPattern, literals)	3✔
259	for (let [key, value] of val) {	3✔
260	if (!collected.has(key)) {	5✔
261	collected.set(key, [])	3✔
262	}
263	collected.get(key)?.push(...value)	5✔
264	}
265	}
266
267	for (let i = inputList.length - backPatternLength; i < inputList.length; i++) {	2✔
NEW 268	const val = collect(	×
269	inputList[i],
270	patternList[i - (inputList.length - patternList.length)],
271	literals
272	)
NEW 273	for (let [key, value] of val) {	×
NEW 274	if (!collected.has(key)) {	×
NEW 275	collected.set(key, [])	×
276	}
NEW 277	collected.get(key)?.push(...value)	×
278	}
279	}
280	return collected	2✔
281	}
282
283	// case 3
284	for (let i = 0; i < inputList.length; i++) {	11✔
285	const val = collect(inputList[i], patternList[i], literals)	31✔
286	for (let [key, value] of val) {	31✔
287	if (!collected.has(key)) {	33✔
288	collected.set(key, [])	33✔
289	}
290	collected.get(key)?.push(...value)	33✔
291	}
292	}
293	return collected	11✔
294	}
295
296	// case 4 and 6
297	if (isImproperList(pattern)) {	4✔
298	let currEllipsisPattern
299	let currentPattern = pattern	4✔
300	let currentInput = input	4✔
301	let ellipsisFound = false	4✔
302
303	// iterate through currentPattern while it is a pair
304	while (isPair(currentPattern)) {	4✔
305	const [headPattern, tailPattern] = currentPattern	4✔
306	const [headInput, tailInput] = currentInput	4✔
307
308	// we can lookahead to see if the ellipsis symbol is the next pattern element.
309	if (	4!
310	isPair(tailPattern) &&	4!
311	tailPattern[0] instanceof _Symbol &&
312	tailPattern[0].sym === '...'
313	) {
NEW 314	ellipsisFound = true	×
NEW 315	currEllipsisPattern = headPattern	×
316	// skip ahead to the (cddr pattern) for the next iteration
317	// the cddr is what "remains" of the pattern after the ellipsis.
NEW 318	currentPattern = tailPattern[1]	×
NEW 319	continue	×
320	}
321
322	// if the ellipis is found, continue to match the pattern until the ellipsis is exhausted.
323	// (this is done by comparing the length of the input to the length of the remaining pattern)
324	// it may be the case that the ellipsis pattern is not matched at all.
325	if (ellipsisFound && improperListLength(currentInput) > improperListLength(currentPattern)) {	4!
NEW 326	const val = collect(headInput, currEllipsisPattern, literals)	×
NEW 327	for (let [key, value] of val) {	×
NEW 328	if (!collected.has(key)) {	×
NEW 329	collected.set(key, [])	×
330	}
NEW 331	collected.get(key)?.push(...value)	×
332	}
NEW 333	currentInput = tailInput // move to the next input	×
NEW 334	continue	×
335	}
336
337	// if the ellipsis symbol is not found, or we have already matched the ellipsis pattern,
338	// match the headInput with the headPattern
339	const val = collect(headInput, headPattern, literals)	4✔
340	for (let [key, value] of val) {	4✔
341	if (!collected.has(key)) {	4✔
342	collected.set(key, [])	4✔
343	}
344	collected.get(key)?.push(...value)	4✔
345	}
346	currEllipsisPattern = headPattern	4✔
347	currentPattern = tailPattern	4✔
348	currentInput = tailInput	4✔
349	}
350	// now we can compare the last item in the pattern with the rest of the input
351	const val = collect(currentInput, currentPattern, literals)	4✔
352	for (let [key, value] of val) {	4✔
353	if (!collected.has(key)) {	4✔
354	collected.set(key, [])	4✔
355	}
356	collected.get(key)?.push(...value)	4✔
357	}
358	return collected	4✔
359	}
360
NEW 361	return collected	×
362	}
363
364	// when matched against a pattern, we use the transform() function
365	// to transform the list into the template.
366	// returns a list, a pair, or any value, as determined by the template.
367	export function transform(	80✔
368	template: any,
369	collected: Map<string, any[]>,
370	indexToCollect: number = 0	120✔
371	): any {
372	// there are 5 possible forms of the template:
373	// 1. an identifier
374	// 2. a literal such as null, a number, a string, or a boolean
375	// 3. (... <template>)
376	// 4. (<element>+)
377	// 5. (<element>+ . <template>)
378	// where <element> is <template> \| <template> ...
379
380	// case 1
381	if (template instanceof _Symbol) {	125✔
382	if (collected.has(template.sym)) {	73✔
383	// get the item from the collected list,
384	// remove it from the collected list,
385	// and return it.
386	const item = (collected.get(template.sym) as any[])[indexToCollect]	31✔
387	return item	31✔
388	}
389	return template	42✔
390	}
391
392	// case 2
393	if (template === null) {	52!
NEW 394	return null	×
395	}
396
397	if (	52✔
398	typeof template === 'string' \|\|	144✔
399	typeof template === 'boolean' \|\|
400	typeof template === 'number'
401	) {
402	return template	8✔
403	}
404
405	if (is_number(template)) {	44!
NEW 406	return template	×
407	}
408
409	// case 3
410	if (	44!
411	isList(template) &&	175✔
412	template !== null &&
413	template[0] instanceof _Symbol &&
414	template[0].sym === '...'
415	) {
416	// parser should ensure that the ellipsis is followed by a single value.
417	// this value is the template to be used.
418	// get the cadr of the template and return it.
NEW 419	return template[1][0]	×
420	}
421
422	// collects all items in an ellipsis template to be used in the final list.
423	// helper function for dealing with ellipsis templates.
424	function deepFlatten(pair: Pair<any, any>): _Symbol[] {
425	const items: _Symbol[] = []	3✔
426	function flattenHelper(item: any) {
427	if (item instanceof _Symbol && item.sym !== '...') {	3!
428	items.push(item)	3✔
NEW 429	} else if (item === null) {	×
NEW 430	return	×
NEW 431	} else if (item instanceof Array && item.length === 2) {	×
432	// based on the usage of (... <value>),
433	// and our previous discussion on the viability
434	// of ... within the ellipsis template
435	// we can assume that any ellipsis used is used to halt macro expansion of <value>.
NEW 436	if (item[0] instanceof _Symbol && item[0].sym === '...') {	×
437	// do not collect any items here, this halts the collection
NEW 438	return	×
439	}
440	// if its a pair, traverse both car and cdr
NEW 441	flattenHelper(item[0])	×
NEW 442	flattenHelper(item[1])	×
443	}
444	}
445	flattenHelper(pair)	3✔
446	return items	3✔
447	}
448
449	// case 4
450	if (isList(template)) {	44✔
451	const templateList = flattenList(template)	44✔
452	const transformedList: any[] = []	44✔
453	for (let i = 0; i < templateList.length; i++) {	44✔
454	if (templateList[i] instanceof _Symbol && templateList[i].sym === '...') {	116✔
455	// if the ellipsis symbol is found, we can skip ahead to the next template
456	// as the ellipsis symbol is not used in the transformation.
457	continue	3✔
458	}
459	// lookahead for the ellipsis symbol
460	if (	113✔
461	i + 1 < templateList.length &&	216✔
462	templateList[i + 1] instanceof _Symbol &&
463	templateList[i + 1].sym === '...'
464	) {
465	const currEllipsisPattern = templateList[i]	3✔
466	const items = deepFlatten(currEllipsisPattern)	3✔
467	// add items to the transformed list
468	// until the templates are exhausted.
469	let currIndex = 0	3✔
470	while (true) {	3✔
471	// check if all items are exhausted
472	let itemsAreExhausted = false	8✔
473	for (let j = 0; j < items.length; j++) {	8✔
474	if (!collected.has(items[j].sym)) {	8!
NEW 475	itemsAreExhausted = true	×
NEW 476	break	×
477	}
478	if (	8✔
479	collected.has(items[j].sym) &&	16✔
480	currIndex >= (collected.get(items[j].sym) as any[]).length
481	) {
482	itemsAreExhausted = true	3✔
483	break	3✔
484	}
485	}
486	if (itemsAreExhausted) {	8✔
487	break	3✔
488	}
489	// apply the last ellipsis template again
490	transformedList.push(transform(currEllipsisPattern, collected, currIndex))	5✔
491	currIndex++	5✔
492	}
493	continue	3✔
494	}
495	transformedList.push(transform(templateList[i], collected))	110✔
496	}
497	return arrayToList(transformedList)	44✔
498	}
499
500	// case 5
NEW 501	if (isImproperList(template)) {	×
NEW 502	let currEllipsisPattern: any = undefined	×
NEW 503	let currentPattern = template	×
504
NEW 505	let collectedItems: any[] = []	×
506
507	// iterate through currentPattern while it is a pair
NEW 508	while (isPair(currentPattern)) {	×
NEW 509	const [headPattern, tailPattern] = currentPattern	×
510
511	// we can lookahead to see if the ellipsis symbol is the next pattern element.
NEW 512	if (	×
513	isPair(tailPattern) &&	×
514	tailPattern[0] instanceof _Symbol &&
515	tailPattern[0].sym === '...'
516	) {
NEW 517	currEllipsisPattern = headPattern	×
518	// skip ahead to the (cddr pattern) for the next iteration
519	// the cddr is what "remains" of the pattern after the ellipsis.
NEW 520	currentPattern = tailPattern[1]	×
NEW 521	continue	×
522	}
523
524	// if a current ellipsis pattern exists, we continue collecting items from it until it is exhausted.
525	// then we undefine the current ellipsis pattern.
NEW 526	if (currEllipsisPattern !== undefined) {	×
NEW 527	const items = deepFlatten(currEllipsisPattern)	×
NEW 528	let currIndex = 0	×
NEW 529	while (true) {	×
530	// check if all items are exhausted
NEW 531	let itemsAreExhausted = false	×
NEW 532	for (let i = 0; i < items.length; i++) {	×
NEW 533	if (!collected.has(items[i].sym)) {	×
NEW 534	itemsAreExhausted = true	×
NEW 535	break	×
536	}
NEW 537	if (	×
538	collected.has(items[i].sym) &&	×
539	currIndex >= (collected.get(items[i].sym) as any[]).length
540	) {
NEW 541	itemsAreExhausted = true	×
NEW 542	break	×
543	}
544	}
NEW 545	if (itemsAreExhausted) {	×
NEW 546	break	×
547	}
548	// add the ellipsis pattern to the collected items
NEW 549	collectedItems.push(transform(currEllipsisPattern, collected, currIndex))	×
NEW 550	currIndex++	×
551	}
NEW 552	currEllipsisPattern = undefined	×
NEW 553	continue	×
554	}
NEW 555	collectedItems.push(transform(headPattern, collected))	×
NEW 556	currentPattern = tailPattern	×
557	}
558	// now we can compare the last item in the pattern with the rest of the input
NEW 559	const val = transform(currentPattern, collected)	×
NEW 560	return arrayToImproperList(collectedItems, val)	×
561	}
NEW 562	return template	×
563	}

source-academy / js-slang / 11929582114

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