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

97.9

/src/typeChecker/utils.ts

// =======================================
// Helper functions/constants for type checker and type error checker
// =======================================

import { Chapter } from '../langs';
import type {
  AllowedDeclarations,
  BindableType,
  ForAll,
  FunctionType,
  List,
  LiteralType,
  Pair,
  PredicateType,
  Primitive,
  SArray,
  TSBasicType,
  Type,
  TypeEnvironment,
  UnionType,
  Variable,
} from '../types';
import * as tsEs from './tsESTree';

// Name of Unary negative builtin operator
export const NEGATIVE_OP = '-_1';

// Special name used for saving return type in type environment
export const RETURN_TYPE_IDENTIFIER = '//RETURN_TYPE';

export const typeAnnotationKeywordToBasicTypeMap: Record<tsEs.TSTypeKeyword, TSBasicType> = {
  TSAnyKeyword: 'any',
  TSBigIntKeyword: 'bigint',
  TSBooleanKeyword: 'boolean',
  TSNeverKeyword: 'never',
  TSNullKeyword: 'null',
  TSNumberKeyword: 'number',
  TSObjectKeyword: 'object',
  TSStringKeyword: 'string',
  TSSymbolKeyword: 'symbol',
  TSUndefinedKeyword: 'undefined',
  TSUnknownKeyword: 'unknown',
  TSVoidKeyword: 'void',
};

// Helper functions for dealing with type environment
export function lookupType(name: string, env: TypeEnvironment): BindableType | undefined {
  for (let i = env.length - 1; i >= 0; i--) {
    if (env[i].typeMap.has(name)) {
      return env[i].typeMap.get(name);
    }
  }
  return undefined;
}

export function lookupDeclKind(
  name: string,
  env: TypeEnvironment,
): AllowedDeclarations | undefined {
  for (let i = env.length - 1; i >= 0; i--) {
    if (env[i].declKindMap.has(name)) {
      return env[i].declKindMap.get(name);
    }
  }
  return undefined;
}

export function lookupTypeAlias(name: string, env: TypeEnvironment): Type | ForAll | undefined {
  for (let i = env.length - 1; i >= 0; i--) {
    if (env[i].typeAliasMap.has(name)) {
      return env[i].typeAliasMap.get(name);
    }
  }
  return undefined;
}

export function setType(name: string, type: BindableType, env: TypeEnvironment): void {
  env[env.length - 1].typeMap.set(name, type);
}

export function setDeclKind(name: string, kind: AllowedDeclarations, env: TypeEnvironment): void {
  env[env.length - 1].declKindMap.set(name, kind);
}

export function setTypeAlias(name: string, type: Type | ForAll, env: TypeEnvironment): void {
  env[env.length - 1].typeAliasMap.set(name, type);
}

export function pushEnv(env: TypeEnvironment): void {
  env.push({ typeMap: new Map(), declKindMap: new Map(), typeAliasMap: new Map() });
}

// Helper functions for formatting types
export function formatTypeString(type: Type, formatAsLiteral?: boolean): string {
  switch (type.kind) {
    case 'function':
      const paramTypes = type.parameterTypes;
      const paramTypeString = paramTypes
        .map(type => formatTypeString(type, formatAsLiteral))
        .join(', ');
      return `(${paramTypeString}) => ${formatTypeString(type.returnType, formatAsLiteral)}`;
    case 'union':
      // Remove duplicates
      const typeSet = new Set(type.types.map(type => formatTypeString(type, formatAsLiteral)));
      return Array.from(typeSet).join(' | ');
    case 'literal':
      if (typeof type.value === 'string') {
        return `"${type.value.toString()}"`;
      }
      return type.value.toString();
    case 'primitive':
      if (!formatAsLiteral || type.value === undefined) {
        return type.name;
      }
      if (typeof type.value === 'string') {
        return `"${type.value.toString()}"`;
      }
      return type.value.toString();
    case 'pair':
      return `Pair<${formatTypeString(type.headType, formatAsLiteral)}, ${formatTypeString(
        type.tailType,
        formatAsLiteral,
      )}>`;
    case 'list':
      return `List<${formatTypeString(type.elementType, formatAsLiteral)}>`;
    case 'array':
      const elementTypeString = formatTypeString(type.elementType, formatAsLiteral);
      return elementTypeString.includes('|') || elementTypeString.includes('=>')
        ? `(${elementTypeString})[]`
        : `${elementTypeString}[]`;
    case 'variable':
      if (type.typeArgs !== undefined && type.typeArgs.length > 0) {
        return `${type.name}<${type.typeArgs
          .map(param => formatTypeString(param, formatAsLiteral))
          .join(', ')}>`;
      }
      return type.name;
    default:
      return type;
  }
}

// Helper functions and constants for parsing types
export function tPrimitive(name: Primitive['name'], value?: string | number | boolean): Primitive {
  return {
    kind: 'primitive',
    name,
    value,
  };
}

export function tVar(name: string, typeArgs?: Type[]): Variable {
  return {
    kind: 'variable',
    name,
    constraint: 'none',
    typeArgs,
  };
}

export function tAddable(name: string): Variable {
  return {
    kind: 'variable',
    name,
    constraint: 'addable',
  };
}

export function tPair(headType: Type, tailType: Type): Pair {
  return {
    kind: 'pair',
    headType,
    tailType,
  };
}

export function tList(elementType: Type, typeAsPair?: Pair): List {
  return {
    kind: 'list',
    elementType,
    // Used in Source Typed variants to check for type mismatches against pairs
    typeAsPair,
  };
}

export function tForAll(polyType: Type, typeParams?: Variable[]): ForAll {
  return {
    kind: 'forall',
    polyType,
    typeParams,
  };
}

export function tArray(elementType: Type): SArray {
  return {
    kind: 'array',
    elementType,
  };
}

export const tAny = tPrimitive('any');
export const tBool = tPrimitive('boolean');
export const tNumber = tPrimitive('number');
export const tString = tPrimitive('string');
export const tUndef = tPrimitive('undefined');
export const tVoid = tPrimitive('void');
export const tNull = tPrimitive('null');

export function tFunc(...types: Type[]): FunctionType {
  const parameterTypes = types.slice(0, -1);
  const returnType = types.slice(-1)[0];
  return {
    kind: 'function',
    parameterTypes,
    returnType,
  };
}

export function tUnion(...types: Type[]): UnionType {
  return {
    kind: 'union',
    types,
  };
}

export function tLiteral(value: string | number | boolean): LiteralType {
  return {
    kind: 'literal',
    value,
  };
}

export function tPred(ifTrueType: Type | ForAll): PredicateType {
  return {
    kind: 'predicate',
    ifTrueType,
  };
}

export const headType = tVar('headType');
export const tailType = tVar('tailType');

// Stream type used in Source Typed
export function tStream(elementType: Type): FunctionType {
  return tFunc(tPair(elementType, tVar('Stream', [elementType])));
}

// Types for preludes
export const predeclaredNames: [string, BindableType][] = [
  // constants
  ['Infinity', tPrimitive('number', Infinity)],
  ['NaN', tPrimitive('number', NaN)],
  ['undefined', tUndef],
  ['math_E', tPrimitive('number', Math.E)],
  ['math_LN2', tPrimitive('number', Math.LN2)],
  ['math_LN10', tPrimitive('number', Math.LN10)],
  ['math_LOG2E', tPrimitive('number', Math.LOG2E)],
  ['math_LOG10E', tPrimitive('number', Math.LOG10E)],
  ['math_PI', tPrimitive('number', Math.PI)],
  ['math_SQRT1_2', tPrimitive('number', Math.SQRT1_2)],
  ['math_SQRT2', tPrimitive('number', Math.SQRT2)],
  // predicate functions
  ['is_boolean', tPred(tBool)],
  ['is_number', tPred(tNumber)],
  ['is_string', tPred(tString)],
  ['is_undefined', tPred(tUndef)],
  ['is_function', tPred(tForAll(tFunc(tVar('T'), tVar('U'))))],
  // math functions
  ['math_abs', tFunc(tNumber, tNumber)],
  ['math_acos', tFunc(tNumber, tNumber)],
  ['math_acosh', tFunc(tNumber, tNumber)],
  ['math_asin', tFunc(tNumber, tNumber)],
  ['math_asinh', tFunc(tNumber, tNumber)],
  ['math_atan', tFunc(tNumber, tNumber)],
  ['math_atan2', tFunc(tNumber, tNumber, tNumber)],
  ['math_atanh', tFunc(tNumber, tNumber)],
  ['math_cbrt', tFunc(tNumber, tNumber)],
  ['math_ceil', tFunc(tNumber, tNumber)],
  ['math_clz32', tFunc(tNumber, tNumber)],
  ['math_cos', tFunc(tNumber, tNumber)],
  ['math_cosh', tFunc(tNumber, tNumber)],
  ['math_exp', tFunc(tNumber, tNumber)],
  ['math_expm1', tFunc(tNumber, tNumber)],
  ['math_floor', tFunc(tNumber, tNumber)],
  ['math_fround', tFunc(tNumber, tNumber)],
  ['math_hypot', tForAll(tVar('T'))],
  ['math_imul', tFunc(tNumber, tNumber, tNumber)],
  ['math_log', tFunc(tNumber, tNumber)],
  ['math_log1p', tFunc(tNumber, tNumber)],
  ['math_log2', tFunc(tNumber, tNumber)],
  ['math_log10', tFunc(tNumber, tNumber)],
  ['math_max', tForAll(tVar('T'))],
  ['math_min', tForAll(tVar('T'))],
  ['math_pow', tFunc(tNumber, tNumber, tNumber)],
  ['math_random', tFunc(tNumber)],
  ['math_round', tFunc(tNumber, tNumber)],
  ['math_sign', tFunc(tNumber, tNumber)],
  ['math_sin', tFunc(tNumber, tNumber)],
  ['math_sinh', tFunc(tNumber, tNumber)],
  ['math_sqrt', tFunc(tNumber, tNumber)],
  ['math_tan', tFunc(tNumber, tNumber)],
  ['math_tanh', tFunc(tNumber, tNumber)],
  ['math_trunc', tFunc(tNumber, tNumber)],
  // misc functions
  ['parse_int', tFunc(tString, tNumber, tNumber)],
  ['prompt', tFunc(tString, tString)],
  ['get_time', tFunc(tNumber)],
  ['stringify', tForAll(tFunc(tVar('T'), tString))],
  ['display', tForAll(tVar('T'))],
  ['error', tForAll(tVar('T'))],
];

export const pairFuncs: [string, BindableType][] = [
  ['pair', tForAll(tFunc(headType, tailType, tPair(headType, tailType)))],
  ['head', tForAll(tFunc(tPair(headType, tailType), headType))],
  ['tail', tForAll(tFunc(tPair(headType, tailType), tailType))],
  ['is_pair', tPred(tForAll(tPair(headType, tailType)))],
  ['is_null', tPred(tForAll(tList(tVar('T'))))],
  ['is_list', tPred(tForAll(tList(tVar('T'))))],
];

export const mutatingPairFuncs: [string, BindableType][] = [
  ['set_head', tForAll(tFunc(tPair(headType, tailType), headType, tUndef))],
  ['set_tail', tForAll(tFunc(tPair(headType, tailType), tailType, tUndef))],
];

export const arrayFuncs: [string, BindableType][] = [
  ['is_array', tPred(tForAll(tArray(tVar('T'))))],
  ['array_length', tForAll(tFunc(tArray(tVar('T')), tNumber))],
];

export const listFuncs: [string, BindableType][] = [['list', tForAll(tVar('T1'))]];

export const primitiveFuncs: [string, BindableType][] = [
  [NEGATIVE_OP, tFunc(tNumber, tNumber)],
  ['!', tFunc(tBool, tBool)],
  ['&&', tForAll(tFunc(tBool, tVar('T'), tVar('T')))],
  ['||', tForAll(tFunc(tBool, tVar('T'), tVar('T')))],
  ['<', tForAll(tFunc(tAddable('A'), tAddable('A'), tBool))],
  ['<=', tForAll(tFunc(tAddable('A'), tAddable('A'), tBool))],
  ['>', tForAll(tFunc(tAddable('A'), tAddable('A'), tBool))],
  ['>=', tForAll(tFunc(tAddable('A'), tAddable('A'), tBool))],
  ['+', tForAll(tFunc(tAddable('A'), tAddable('A'), tAddable('A')))],
  ['%', tFunc(tNumber, tNumber, tNumber)],
  ['-', tFunc(tNumber, tNumber, tNumber)],
  ['*', tFunc(tNumber, tNumber, tNumber)],
  ['/', tFunc(tNumber, tNumber, tNumber)],
];

// Source 2 and below restricts === to addables
export const preS3equalityFuncs: [string, BindableType][] = [
  ['===', tForAll(tFunc(tAddable('A'), tAddable('A'), tBool))],
  ['!==', tForAll(tFunc(tAddable('A'), tAddable('A'), tBool))],
];

// Source 3 and above allows any values as arguments for ===
export const postS3equalityFuncs: [string, BindableType][] = [
  ['===', tForAll(tFunc(tVar('T1'), tVar('T2'), tBool))],
  ['!==', tForAll(tFunc(tVar('T1'), tVar('T2'), tBool))],
];

export const temporaryStreamFuncs: [string, BindableType][] = [
  ['is_stream', tForAll(tFunc(tVar('T1'), tBool))],
  ['list_to_stream', tForAll(tFunc(tList(tVar('T1')), tVar('T2')))],
  ['stream_to_list', tForAll(tFunc(tVar('T1'), tList(tVar('T2'))))],
  ['stream_length', tForAll(tFunc(tVar('T1'), tNumber))],
  ['stream_map', tForAll(tFunc(tVar('T1'), tVar('T2')))],
  ['build_stream', tForAll(tFunc(tNumber, tFunc(tNumber, tVar('T1')), tVar('T2')))],
  ['stream_for_each', tForAll(tFunc(tFunc(tVar('T1'), tVar('T2')), tBool))],
  ['stream_reverse', tForAll(tFunc(tVar('T1'), tVar('T1')))],
  ['stream_append', tForAll(tFunc(tVar('T1'), tVar('T1'), tVar('T1')))],
  ['stream_member', tForAll(tFunc(tVar('T1'), tVar('T2'), tVar('T2')))],
  ['stream_remove', tForAll(tFunc(tVar('T1'), tVar('T2'), tVar('T2')))],
  ['stream_remove_all', tForAll(tFunc(tVar('T1'), tVar('T2'), tVar('T2')))],
  ['stream_filter', tForAll(tFunc(tFunc(tVar('T1'), tBool), tVar('T2'), tVar('T2')))],
  ['enum_stream', tForAll(tFunc(tNumber, tNumber, tVar('T1')))],
  ['integers_from', tForAll(tFunc(tNumber, tVar('T1')))],
  ['eval_stream', tForAll(tFunc(tVar('T1'), tNumber, tList(tVar('T2'))))],
  ['stream_ref', tForAll(tFunc(tVar('T1'), tNumber, tVar('T2')))],
];

// Prelude function type overrides for Source Typed variant
// No need to override predicate functions as they are automatically handled by type checker
export const source1TypeOverrides: [string, BindableType][] = [
  // math functions
  // TODO: Add support for type checking of functions with variable no. of args
  ['math_hypot', tForAll(tNumber)],
  ['math_max', tForAll(tNumber)],
  ['math_min', tForAll(tNumber)],
  // misc functions
  ['stringify', tFunc(tAny, tString)],
  ['arity', tFunc(tAny, tNumber)],
  ['char_at', tFunc(tString, tNumber, tUnion(tString, tUndef))],
  // TODO: Add support for type checking of functions with variable no. of args
  ['display', tForAll(tAny)],
  ['error', tForAll(tAny)],
];

export const source2TypeOverrides: [string, BindableType][] = [
  // list library functions
  [
    'accumulate',
    tForAll(tFunc(tFunc(tVar('T'), tVar('U'), tVar('U')), tVar('U'), tList(tVar('T')), tVar('U'))),
  ],
  [
    'append',
    tForAll(tFunc(tList(tVar('T')), tList(tVar('U')), tList(tUnion(tVar('T'), tVar('U'))))),
  ],
  ['build_list', tForAll(tFunc(tFunc(tNumber, tVar('T')), tNumber, tList(tVar('T'))))],
  ['enum_list', tFunc(tNumber, tNumber, tList(tNumber))],
  ['filter', tForAll(tFunc(tFunc(tVar('T'), tBool), tList(tVar('T')), tList(tVar('T'))))],
  ['for_each', tForAll(tFunc(tFunc(tVar('T'), tAny), tList(tVar('T')), tLiteral(true)))],
  ['length', tFunc(tList(tAny), tNumber)],
  ['list_ref', tForAll(tFunc(tList(tVar('T')), tNumber, tVar('T')))],
  ['list_to_string', tFunc(tList(tAny), tString)],
  ['map', tForAll(tFunc(tFunc(tVar('T'), tVar('U')), tList(tVar('T')), tList(tVar('U'))))],
  ['member', tForAll(tFunc(tVar('T'), tList(tVar('T')), tList(tVar('T'))))],
  ['remove', tForAll(tFunc(tVar('T'), tList(tVar('T')), tList(tVar('T'))))],
  ['remove_all', tForAll(tFunc(tVar('T'), tList(tVar('T')), tList(tVar('T'))))],
  ['reverse', tForAll(tFunc(tList(tVar('T')), tList(tVar('T'))))],
  // misc functions
  // TODO: Add support for type checking of functions with variable no. of args
  ['display_list', tForAll(tAny)],
  ['draw_data', tForAll(tAny)],
  ['equal', tFunc(tAny, tAny, tBool)],
];

export const source3TypeOverrides: [string, BindableType][] = [
  // array functions
  ['array_length', tFunc(tArray(tAny), tNumber)],
  // stream library functions
  ['build_stream', tForAll(tFunc(tFunc(tNumber, tVar('T')), tNumber, tStream(tVar('T'))))],
  ['enum_stream', tFunc(tNumber, tNumber, tStream(tNumber))],
  ['eval_stream', tForAll(tFunc(tStream(tVar('T')), tNumber, tList(tVar('T'))))],
  ['integers_from', tFunc(tNumber, tStream(tNumber))],
  ['is_stream', tFunc(tAny, tBool)],
  ['list_to_stream', tForAll(tFunc(tList(tVar('T')), tStream(tVar('T'))))],
  [
    'stream_append',
    tForAll(tFunc(tStream(tVar('T')), tStream(tVar('U')), tStream(tUnion(tVar('T'), tVar('U'))))),
  ],
  [
    'stream_filter',
    tForAll(tFunc(tFunc(tVar('T'), tBool), tStream(tVar('T')), tStream(tVar('T')))),
  ],
  ['stream_for_each', tForAll(tFunc(tFunc(tVar('T'), tAny), tStream(tVar('T')), tLiteral(true)))],
  ['stream_length', tFunc(tStream(tAny), tNumber)],
  [
    'stream_map',
    tForAll(tFunc(tFunc(tVar('T'), tVar('U')), tStream(tVar('T')), tStream(tVar('U')))),
  ],
  ['stream_member', tForAll(tFunc(tVar('T'), tStream(tVar('T')), tStream(tVar('T'))))],
  ['stream_ref', tForAll(tFunc(tStream(tVar('T')), tNumber, tVar('T')))],
  ['stream_remove', tForAll(tFunc(tVar('T'), tStream(tVar('T')), tStream(tVar('T'))))],
  ['stream_remove_all', tForAll(tFunc(tVar('T'), tStream(tVar('T')), tStream(tVar('T'))))],
  ['stream_reverse', tForAll(tFunc(tStream(tVar('T')), tStream(tVar('T'))))],
  ['stream_tail', tForAll(tFunc(tStream(tVar('T')), tStream(tVar('T'))))],
  ['stream_to_list', tForAll(tFunc(tStream(tVar('T')), tList(tVar('T'))))],
];

export const source4TypeOverrides: [string, BindableType][] = [
  ['apply_in_underlying_javascript', tFunc(tAny, tList(tAny), tAny)],
  ['tokenize', tFunc(tString, tList(tString))],
  // For parse tree types, see parseTreeTypes.prelude.ts
  ['parse', tFunc(tString, tUnion(tVar('Program', []), tVar('Statement', [])))],
];

const predeclaredConstTypes: [string, Type][] = [];

const pairTypeAlias: [string, ForAll] = [
  'Pair',
  tForAll(tPair(headType, tailType), [headType, tailType]),
];
const listTypeAlias: [string, ForAll] = ['List', tForAll(tList(tVar('T')), [tVar('T')])];
const streamTypeAlias: [string, ForAll] = ['Stream', tForAll(tStream(tVar('T')), [tVar('T')])];

// Creates type environment for the appropriate Source chapter
export function createTypeEnvironment(chapter: Chapter): TypeEnvironment {
  const initialTypeMappings = [...predeclaredNames, ...primitiveFuncs];
  const initialTypeAliasMappings: [string, Type | ForAll][] = [...predeclaredConstTypes];
  if (chapter >= 2) {
    initialTypeMappings.push(...pairFuncs, ...listFuncs);
    initialTypeAliasMappings.push(pairTypeAlias, listTypeAlias);
  }
  if (chapter >= 3) {
    initialTypeMappings.push(...postS3equalityFuncs, ...mutatingPairFuncs, ...arrayFuncs);
    initialTypeAliasMappings.push(streamTypeAlias);
  } else {
    initialTypeMappings.push(...preS3equalityFuncs);
  }

  return [
    {
      typeMap: new Map(initialTypeMappings),
      declKindMap: new Map(initialTypeMappings.map(val => [val[0], 'const'])),
      typeAliasMap: new Map(initialTypeAliasMappings),
    },
  ];
}

export function getTypeOverrides(chapter: Chapter): [string, BindableType][] {
  const typeOverrides = [...source1TypeOverrides];
  if (chapter >= 2) {
    typeOverrides.push(...source2TypeOverrides);
  }
  if (chapter >= 3) {
    typeOverrides.push(...source3TypeOverrides);
  }
  if (chapter >= 4) {
    typeOverrides.push(...source4TypeOverrides);
  }
  return typeOverrides;
}

1	// =======================================
2	// Helper functions/constants for type checker and type error checker
3	// =======================================
4
5	import { Chapter } from '../langs';
6	import type {
7	AllowedDeclarations,
8	BindableType,
9	ForAll,
10	FunctionType,
11	List,
12	LiteralType,
13	Pair,
14	PredicateType,
15	Primitive,
16	SArray,
17	TSBasicType,
18	Type,
19	TypeEnvironment,
20	UnionType,
21	Variable,
22	} from '../types';
23	import * as tsEs from './tsESTree';
24
25	// Name of Unary negative builtin operator
26	export const NEGATIVE_OP = '-_1';	65✔
27
28	// Special name used for saving return type in type environment
29	export const RETURN_TYPE_IDENTIFIER = '//RETURN_TYPE';	65✔
30
31	export const typeAnnotationKeywordToBasicTypeMap: Record<tsEs.TSTypeKeyword, TSBasicType> = {	65✔
32	TSAnyKeyword: 'any',
33	TSBigIntKeyword: 'bigint',
34	TSBooleanKeyword: 'boolean',
35	TSNeverKeyword: 'never',
36	TSNullKeyword: 'null',
37	TSNumberKeyword: 'number',
38	TSObjectKeyword: 'object',
39	TSStringKeyword: 'string',
40	TSSymbolKeyword: 'symbol',
41	TSUndefinedKeyword: 'undefined',
42	TSUnknownKeyword: 'unknown',
43	TSVoidKeyword: 'void',
44	};
45
46	// Helper functions for dealing with type environment
47	export function lookupType(name: string, env: TypeEnvironment): BindableType \| undefined {
48	for (let i = env.length - 1; i >= 0; i--) {	1,077✔
49	if (env[i].typeMap.has(name)) {	1,417✔
50	return env[i].typeMap.get(name);	1,076✔
51	}
52	}
53	return undefined;	1✔
54	}
55
56	export function lookupDeclKind(
57	name: string,
58	env: TypeEnvironment,
59	): AllowedDeclarations \| undefined {
60	for (let i = env.length - 1; i >= 0; i--) {	25✔
61	if (env[i].declKindMap.has(name)) {	32✔
62	return env[i].declKindMap.get(name);	25✔
63	}
64	}
NEW 65	return undefined;	×
66	}
67
68	export function lookupTypeAlias(name: string, env: TypeEnvironment): Type \| ForAll \| undefined {
69	for (let i = env.length - 1; i >= 0; i--) {	2,210✔
70	if (env[i].typeAliasMap.has(name)) {	4,693✔
71	return env[i].typeAliasMap.get(name);	603✔
72	}
73	}
74	return undefined;	1,607✔
75	}
76
77	export function setType(name: string, type: BindableType, env: TypeEnvironment): void {
78	env[env.length - 1].typeMap.set(name, type);	5,461✔
79	}
80
81	export function setDeclKind(name: string, kind: AllowedDeclarations, env: TypeEnvironment): void {
82	env[env.length - 1].declKindMap.set(name, kind);	910✔
83	}
84
85	export function setTypeAlias(name: string, type: Type \| ForAll, env: TypeEnvironment): void {
86	env[env.length - 1].typeAliasMap.set(name, type);	1,681✔
87	}
88
89	export function pushEnv(env: TypeEnvironment): void {
90	env.push({ typeMap: new Map(), declKindMap: new Map(), typeAliasMap: new Map() });	489✔
91	}
92
93	// Helper functions for formatting types
94	export function formatTypeString(type: Type, formatAsLiteral?: boolean): string {
95	switch (type.kind) {	817!
96	case 'function':
97	const paramTypes = type.parameterTypes;	22✔
98	const paramTypeString = paramTypes	22✔
99	.map(type => formatTypeString(type, formatAsLiteral))	30✔
100	.join(', ');
101	return `(${paramTypeString}) => ${formatTypeString(type.returnType, formatAsLiteral)}`;	22✔
102	case 'union':
103	// Remove duplicates
104	const typeSet = new Set(type.types.map(type => formatTypeString(type, formatAsLiteral)));	138✔
105	return Array.from(typeSet).join(' \| ');	48✔
106	case 'literal':
107	if (typeof type.value === 'string') {	34✔
108	return `"${type.value.toString()}"`;	27✔
109	}
110	return type.value.toString();	7✔
111	case 'primitive':
112	if (!formatAsLiteral \|\| type.value === undefined) {	632✔
113	return type.name;	625✔
114	}
115	if (typeof type.value === 'string') {	7✔
116	return `"${type.value.toString()}"`;	3✔
117	}
118	return type.value.toString();	4✔
119	case 'pair':
120	return `Pair<${formatTypeString(type.headType, formatAsLiteral)}, ${formatTypeString(	6✔
121	type.tailType,
122	formatAsLiteral,
123	)}>`;
124	case 'list':
125	return `List<${formatTypeString(type.elementType, formatAsLiteral)}>`;	6✔
126	case 'array':
127	const elementTypeString = formatTypeString(type.elementType, formatAsLiteral);	10✔
128	return elementTypeString.includes('\|') \|\| elementTypeString.includes('=>')	10✔
129	? `(${elementTypeString})[]`
130	: `${elementTypeString}[]`;
131	case 'variable':
132	if (type.typeArgs !== undefined && type.typeArgs.length > 0) {	59✔
133	return `${type.name}<${type.typeArgs	28✔
134	.map(param => formatTypeString(param, formatAsLiteral))	38✔
135	.join(', ')}>`;
136	}
137	return type.name;	31✔
138	default:
NEW 139	return type;	×
140	}
141	}
142
143	// Helper functions and constants for parsing types
144	export function tPrimitive(name: Primitive['name'], value?: string \| number \| boolean): Primitive {
145	return {	4,100✔
146	kind: 'primitive',
147	name,
148	value,
149	};
150	}
151
152	export function tVar(name: string, typeArgs?: Type[]): Variable {
153	return {	38,558✔
154	kind: 'variable',
155	name,
156	constraint: 'none',
157	typeArgs,
158	};
159	}
160
161	export function tAddable(name: string): Variable {
162	return {	975✔
163	kind: 'variable',
164	name,
165	constraint: 'addable',
166	};
167	}
168
169	export function tPair(headType: Type, tailType: Type): Pair {
170	return {	2,878✔
171	kind: 'pair',
172	headType,
173	tailType,
174	};
175	}
176
177	export function tList(elementType: Type, typeAsPair?: Pair): List {
178	return {	2,257✔
179	kind: 'list',
180	elementType,
181	// Used in Source Typed variants to check for type mismatches against pairs
182	typeAsPair,
183	};
184	}
185
186	export function tForAll(polyType: Type, typeParams?: Variable[]): ForAll {
187	return {	25,713✔
188	kind: 'forall',
189	polyType,
190	typeParams,
191	};
192	}
193
194	export function tArray(elementType: Type): SArray {
195	return {	247✔
196	kind: 'array',
197	elementType,
198	};
199	}
200
201	export const tAny = tPrimitive('any');	65✔
202	export const tBool = tPrimitive('boolean');	65✔
203	export const tNumber = tPrimitive('number');	65✔
204	export const tString = tPrimitive('string');	65✔
205	export const tUndef = tPrimitive('undefined');	65✔
206	export const tVoid = tPrimitive('void');	65✔
207	export const tNull = tPrimitive('null');	65✔
208
209	export function tFunc(...types: Type[]): FunctionType {
210	const parameterTypes = types.slice(0, -1);	10,454✔
211	const returnType = types.slice(-1)[0];	10,454✔
212	return {	10,454✔
213	kind: 'function',
214	parameterTypes,
215	returnType,
216	};
217	}
218
219	export function tUnion(...types: Type[]): UnionType {
220	return {	872✔
221	kind: 'union',
222	types,
223	};
224	}
225
226	export function tLiteral(value: string \| number \| boolean): LiteralType {
227	return {	2,212✔
228	kind: 'literal',
229	value,
230	};
231	}
232
233	export function tPred(ifTrueType: Type \| ForAll): PredicateType {
234	return {	585✔
235	kind: 'predicate',
236	ifTrueType,
237	};
238	}
239
240	export const headType = tVar('headType');	65✔
241	export const tailType = tVar('tailType');	65✔
242
243	// Stream type used in Source Typed
244	export function tStream(elementType: Type): FunctionType {
245	return tFunc(tPair(elementType, tVar('Stream', [elementType])));	1,757✔
246	}
247
248	// Types for preludes
249	export const predeclaredNames: [string, BindableType][] = [	65✔
250	// constants
251	['Infinity', tPrimitive('number', Infinity)],
252	['NaN', tPrimitive('number', NaN)],
253	['undefined', tUndef],
254	['math_E', tPrimitive('number', Math.E)],
255	['math_LN2', tPrimitive('number', Math.LN2)],
256	['math_LN10', tPrimitive('number', Math.LN10)],
257	['math_LOG2E', tPrimitive('number', Math.LOG2E)],
258	['math_LOG10E', tPrimitive('number', Math.LOG10E)],
259	['math_PI', tPrimitive('number', Math.PI)],
260	['math_SQRT1_2', tPrimitive('number', Math.SQRT1_2)],
261	['math_SQRT2', tPrimitive('number', Math.SQRT2)],
262	// predicate functions
263	['is_boolean', tPred(tBool)],
264	['is_number', tPred(tNumber)],
265	['is_string', tPred(tString)],
266	['is_undefined', tPred(tUndef)],
267	['is_function', tPred(tForAll(tFunc(tVar('T'), tVar('U'))))],
268	// math functions
269	['math_abs', tFunc(tNumber, tNumber)],
270	['math_acos', tFunc(tNumber, tNumber)],
271	['math_acosh', tFunc(tNumber, tNumber)],
272	['math_asin', tFunc(tNumber, tNumber)],
273	['math_asinh', tFunc(tNumber, tNumber)],
274	['math_atan', tFunc(tNumber, tNumber)],
275	['math_atan2', tFunc(tNumber, tNumber, tNumber)],
276	['math_atanh', tFunc(tNumber, tNumber)],
277	['math_cbrt', tFunc(tNumber, tNumber)],
278	['math_ceil', tFunc(tNumber, tNumber)],
279	['math_clz32', tFunc(tNumber, tNumber)],
280	['math_cos', tFunc(tNumber, tNumber)],
281	['math_cosh', tFunc(tNumber, tNumber)],
282	['math_exp', tFunc(tNumber, tNumber)],
283	['math_expm1', tFunc(tNumber, tNumber)],
284	['math_floor', tFunc(tNumber, tNumber)],
285	['math_fround', tFunc(tNumber, tNumber)],
286	['math_hypot', tForAll(tVar('T'))],
287	['math_imul', tFunc(tNumber, tNumber, tNumber)],
288	['math_log', tFunc(tNumber, tNumber)],
289	['math_log1p', tFunc(tNumber, tNumber)],
290	['math_log2', tFunc(tNumber, tNumber)],
291	['math_log10', tFunc(tNumber, tNumber)],
292	['math_max', tForAll(tVar('T'))],
293	['math_min', tForAll(tVar('T'))],
294	['math_pow', tFunc(tNumber, tNumber, tNumber)],
295	['math_random', tFunc(tNumber)],
296	['math_round', tFunc(tNumber, tNumber)],
297	['math_sign', tFunc(tNumber, tNumber)],
298	['math_sin', tFunc(tNumber, tNumber)],
299	['math_sinh', tFunc(tNumber, tNumber)],
300	['math_sqrt', tFunc(tNumber, tNumber)],
301	['math_tan', tFunc(tNumber, tNumber)],
302	['math_tanh', tFunc(tNumber, tNumber)],
303	['math_trunc', tFunc(tNumber, tNumber)],
304	// misc functions
305	['parse_int', tFunc(tString, tNumber, tNumber)],
306	['prompt', tFunc(tString, tString)],
307	['get_time', tFunc(tNumber)],
308	['stringify', tForAll(tFunc(tVar('T'), tString))],
309	['display', tForAll(tVar('T'))],
310	['error', tForAll(tVar('T'))],
311	];
312
313	export const pairFuncs: [string, BindableType][] = [	65✔
314	['pair', tForAll(tFunc(headType, tailType, tPair(headType, tailType)))],
315	['head', tForAll(tFunc(tPair(headType, tailType), headType))],
316	['tail', tForAll(tFunc(tPair(headType, tailType), tailType))],
317	['is_pair', tPred(tForAll(tPair(headType, tailType)))],
318	['is_null', tPred(tForAll(tList(tVar('T'))))],
319	['is_list', tPred(tForAll(tList(tVar('T'))))],
320	];
321
322	export const mutatingPairFuncs: [string, BindableType][] = [	65✔
323	['set_head', tForAll(tFunc(tPair(headType, tailType), headType, tUndef))],
324	['set_tail', tForAll(tFunc(tPair(headType, tailType), tailType, tUndef))],
325	];
326
327	export const arrayFuncs: [string, BindableType][] = [	65✔
328	['is_array', tPred(tForAll(tArray(tVar('T'))))],
329	['array_length', tForAll(tFunc(tArray(tVar('T')), tNumber))],
330	];
331
332	export const listFuncs: [string, BindableType][] = [['list', tForAll(tVar('T1'))]];	65✔
333
334	export const primitiveFuncs: [string, BindableType][] = [	65✔
335	[NEGATIVE_OP, tFunc(tNumber, tNumber)],
336	['!', tFunc(tBool, tBool)],
337	['&&', tForAll(tFunc(tBool, tVar('T'), tVar('T')))],
338	['\|\|', tForAll(tFunc(tBool, tVar('T'), tVar('T')))],
339	['<', tForAll(tFunc(tAddable('A'), tAddable('A'), tBool))],
340	['<=', tForAll(tFunc(tAddable('A'), tAddable('A'), tBool))],
341	['>', tForAll(tFunc(tAddable('A'), tAddable('A'), tBool))],
342	['>=', tForAll(tFunc(tAddable('A'), tAddable('A'), tBool))],
343	['+', tForAll(tFunc(tAddable('A'), tAddable('A'), tAddable('A')))],
344	['%', tFunc(tNumber, tNumber, tNumber)],
345	['-', tFunc(tNumber, tNumber, tNumber)],
346	['*', tFunc(tNumber, tNumber, tNumber)],
347	['/', tFunc(tNumber, tNumber, tNumber)],
348	];
349
350	// Source 2 and below restricts === to addables
351	export const preS3equalityFuncs: [string, BindableType][] = [	65✔
352	['===', tForAll(tFunc(tAddable('A'), tAddable('A'), tBool))],
353	['!==', tForAll(tFunc(tAddable('A'), tAddable('A'), tBool))],
354	];
355
356	// Source 3 and above allows any values as arguments for ===
357	export const postS3equalityFuncs: [string, BindableType][] = [	65✔
358	['===', tForAll(tFunc(tVar('T1'), tVar('T2'), tBool))],
359	['!==', tForAll(tFunc(tVar('T1'), tVar('T2'), tBool))],
360	];
361
362	export const temporaryStreamFuncs: [string, BindableType][] = [	65✔
363	['is_stream', tForAll(tFunc(tVar('T1'), tBool))],
364	['list_to_stream', tForAll(tFunc(tList(tVar('T1')), tVar('T2')))],
365	['stream_to_list', tForAll(tFunc(tVar('T1'), tList(tVar('T2'))))],
366	['stream_length', tForAll(tFunc(tVar('T1'), tNumber))],
367	['stream_map', tForAll(tFunc(tVar('T1'), tVar('T2')))],
368	['build_stream', tForAll(tFunc(tNumber, tFunc(tNumber, tVar('T1')), tVar('T2')))],
369	['stream_for_each', tForAll(tFunc(tFunc(tVar('T1'), tVar('T2')), tBool))],
370	['stream_reverse', tForAll(tFunc(tVar('T1'), tVar('T1')))],
371	['stream_append', tForAll(tFunc(tVar('T1'), tVar('T1'), tVar('T1')))],
372	['stream_member', tForAll(tFunc(tVar('T1'), tVar('T2'), tVar('T2')))],
373	['stream_remove', tForAll(tFunc(tVar('T1'), tVar('T2'), tVar('T2')))],
374	['stream_remove_all', tForAll(tFunc(tVar('T1'), tVar('T2'), tVar('T2')))],
375	['stream_filter', tForAll(tFunc(tFunc(tVar('T1'), tBool), tVar('T2'), tVar('T2')))],
376	['enum_stream', tForAll(tFunc(tNumber, tNumber, tVar('T1')))],
377	['integers_from', tForAll(tFunc(tNumber, tVar('T1')))],
378	['eval_stream', tForAll(tFunc(tVar('T1'), tNumber, tList(tVar('T2'))))],
379	['stream_ref', tForAll(tFunc(tVar('T1'), tNumber, tVar('T2')))],
380	];
381
382	// Prelude function type overrides for Source Typed variant
383	// No need to override predicate functions as they are automatically handled by type checker
384	export const source1TypeOverrides: [string, BindableType][] = [	65✔
385	// math functions
386	// TODO: Add support for type checking of functions with variable no. of args
387	['math_hypot', tForAll(tNumber)],
388	['math_max', tForAll(tNumber)],
389	['math_min', tForAll(tNumber)],
390	// misc functions
391	['stringify', tFunc(tAny, tString)],
392	['arity', tFunc(tAny, tNumber)],
393	['char_at', tFunc(tString, tNumber, tUnion(tString, tUndef))],
394	// TODO: Add support for type checking of functions with variable no. of args
395	['display', tForAll(tAny)],
396	['error', tForAll(tAny)],
397	];
398
399	export const source2TypeOverrides: [string, BindableType][] = [	65✔
400	// list library functions
401	[
402	'accumulate',
403	tForAll(tFunc(tFunc(tVar('T'), tVar('U'), tVar('U')), tVar('U'), tList(tVar('T')), tVar('U'))),
404	],
405	[
406	'append',
407	tForAll(tFunc(tList(tVar('T')), tList(tVar('U')), tList(tUnion(tVar('T'), tVar('U'))))),
408	],
409	['build_list', tForAll(tFunc(tFunc(tNumber, tVar('T')), tNumber, tList(tVar('T'))))],
410	['enum_list', tFunc(tNumber, tNumber, tList(tNumber))],
411	['filter', tForAll(tFunc(tFunc(tVar('T'), tBool), tList(tVar('T')), tList(tVar('T'))))],
412	['for_each', tForAll(tFunc(tFunc(tVar('T'), tAny), tList(tVar('T')), tLiteral(true)))],
413	['length', tFunc(tList(tAny), tNumber)],
414	['list_ref', tForAll(tFunc(tList(tVar('T')), tNumber, tVar('T')))],
415	['list_to_string', tFunc(tList(tAny), tString)],
416	['map', tForAll(tFunc(tFunc(tVar('T'), tVar('U')), tList(tVar('T')), tList(tVar('U'))))],
417	['member', tForAll(tFunc(tVar('T'), tList(tVar('T')), tList(tVar('T'))))],
418	['remove', tForAll(tFunc(tVar('T'), tList(tVar('T')), tList(tVar('T'))))],
419	['remove_all', tForAll(tFunc(tVar('T'), tList(tVar('T')), tList(tVar('T'))))],
420	['reverse', tForAll(tFunc(tList(tVar('T')), tList(tVar('T'))))],
421	// misc functions
422	// TODO: Add support for type checking of functions with variable no. of args
423	['display_list', tForAll(tAny)],
424	['draw_data', tForAll(tAny)],
425	['equal', tFunc(tAny, tAny, tBool)],
426	];
427
428	export const source3TypeOverrides: [string, BindableType][] = [	65✔
429	// array functions
430	['array_length', tFunc(tArray(tAny), tNumber)],
431	// stream library functions
432	['build_stream', tForAll(tFunc(tFunc(tNumber, tVar('T')), tNumber, tStream(tVar('T'))))],
433	['enum_stream', tFunc(tNumber, tNumber, tStream(tNumber))],
434	['eval_stream', tForAll(tFunc(tStream(tVar('T')), tNumber, tList(tVar('T'))))],
435	['integers_from', tFunc(tNumber, tStream(tNumber))],
436	['is_stream', tFunc(tAny, tBool)],
437	['list_to_stream', tForAll(tFunc(tList(tVar('T')), tStream(tVar('T'))))],
438	[
439	'stream_append',
440	tForAll(tFunc(tStream(tVar('T')), tStream(tVar('U')), tStream(tUnion(tVar('T'), tVar('U'))))),
441	],
442	[
443	'stream_filter',
444	tForAll(tFunc(tFunc(tVar('T'), tBool), tStream(tVar('T')), tStream(tVar('T')))),
445	],
446	['stream_for_each', tForAll(tFunc(tFunc(tVar('T'), tAny), tStream(tVar('T')), tLiteral(true)))],
447	['stream_length', tFunc(tStream(tAny), tNumber)],
448	[
449	'stream_map',
450	tForAll(tFunc(tFunc(tVar('T'), tVar('U')), tStream(tVar('T')), tStream(tVar('U')))),
451	],
452	['stream_member', tForAll(tFunc(tVar('T'), tStream(tVar('T')), tStream(tVar('T'))))],
453	['stream_ref', tForAll(tFunc(tStream(tVar('T')), tNumber, tVar('T')))],
454	['stream_remove', tForAll(tFunc(tVar('T'), tStream(tVar('T')), tStream(tVar('T'))))],
455	['stream_remove_all', tForAll(tFunc(tVar('T'), tStream(tVar('T')), tStream(tVar('T'))))],
456	['stream_reverse', tForAll(tFunc(tStream(tVar('T')), tStream(tVar('T'))))],
457	['stream_tail', tForAll(tFunc(tStream(tVar('T')), tStream(tVar('T'))))],
458	['stream_to_list', tForAll(tFunc(tStream(tVar('T')), tList(tVar('T'))))],
459	];
460
461	export const source4TypeOverrides: [string, BindableType][] = [	65✔
462	['apply_in_underlying_javascript', tFunc(tAny, tList(tAny), tAny)],
463	['tokenize', tFunc(tString, tList(tString))],
464	// For parse tree types, see parseTreeTypes.prelude.ts
465	['parse', tFunc(tString, tUnion(tVar('Program', []), tVar('Statement', [])))],
466	];
467
468	const predeclaredConstTypes: [string, Type][] = [];	65✔
469
470	const pairTypeAlias: [string, ForAll] = [	65✔
471	'Pair',
472	tForAll(tPair(headType, tailType), [headType, tailType]),
473	];
474	const listTypeAlias: [string, ForAll] = ['List', tForAll(tList(tVar('T')), [tVar('T')])];	65✔
475	const streamTypeAlias: [string, ForAll] = ['Stream', tForAll(tStream(tVar('T')), [tVar('T')])];	65✔
476
477	// Creates type environment for the appropriate Source chapter
478	export function createTypeEnvironment(chapter: Chapter): TypeEnvironment {
479	const initialTypeMappings = [...predeclaredNames, ...primitiveFuncs];	3,017✔
480	const initialTypeAliasMappings: [string, Type \| ForAll][] = [...predeclaredConstTypes];	3,017✔
481	if (chapter >= 2) {	3,017✔
482	initialTypeMappings.push(...pairFuncs, ...listFuncs);	1,594✔
483	initialTypeAliasMappings.push(pairTypeAlias, listTypeAlias);	1,594✔
484	}
485	if (chapter >= 3) {	3,017✔
486	initialTypeMappings.push(...postS3equalityFuncs, ...mutatingPairFuncs, ...arrayFuncs);	1,319✔
487	initialTypeAliasMappings.push(streamTypeAlias);	1,319✔
488	} else {
489	initialTypeMappings.push(...preS3equalityFuncs);	1,698✔
490	}
491
492	return [	3,017✔
493	{
494	typeMap: new Map(initialTypeMappings),
495	declKindMap: new Map(initialTypeMappings.map(val => [val[0], 'const'])),	233,658✔
496	typeAliasMap: new Map(initialTypeAliasMappings),
497	},
498	];
499	}
500
501	export function getTypeOverrides(chapter: Chapter): [string, BindableType][] {
502	const typeOverrides = [...source1TypeOverrides];	139✔
503	if (chapter >= 2) {	139✔
504	typeOverrides.push(...source2TypeOverrides);	82✔
505	}
506	if (chapter >= 3) {	139✔
507	typeOverrides.push(...source3TypeOverrides);	67✔
508	}
509	if (chapter >= 4) {	139✔
510	typeOverrides.push(...source4TypeOverrides);	54✔
511	}
512	return typeOverrides;	139✔
513	}

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