Repository: source-academy/js-slang
Pull request #490 (2020-04-02 09:02:56)

Scope highlighting
## Overview
This PR adds the functionality to get the scope of an identifier, in terms of a list of location ranges to be used by the frontend for highlighting purposes.

## Implementation
Using the tree generated by #471, we find the parent block of the given declaration and remove all child blocks that have an overriding declaration of the same identifier, and return the resulting ranges.

Here's a demo when integrated with the frontend using a hotkey:

![ezgif com-crop](https://user-images.githubusercontent.com/25262251/78230242-a57ce980-7503-11ea-992d-c16546782f58.gif)



coveralls: ## Pull Request Test Coverage Report for [Build 2451](https://coveralls.io/builds/29791071)

* **29** of **34**   **(85.29%)**  changed or added relevant lines in **2** files are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage decreased (**-0.05%**) to **89.296%**

---

|  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
| :-----|--------------|--------|---: |
| [src/scope-refactoring.ts](https://coveralls.io/builds/29791071/source?filename=src%2Fscope-refactoring.ts#L244) | 20 | 22 | 90.91%
| [src/index.ts](https://coveralls.io/builds/29791071/source?filename=src%2Findex.ts#L185) | 9 | 12 | 75.0%
<!-- | **Total:** | **29** | **34** | **85.29%** | -->


|  Totals | [![Coverage Status](https://coveralls.io/builds/29791071/badge)](https://coveralls.io/builds/29791071) |
| :-- | --: |
| Change from base [Build 2442](https://coveralls.io/builds/29789029): |  -0.05% |
| Covered Lines: | 4038 |
| Relevant Lines: | 4383 |

---
##### 💛  - [Coveralls](https://coveralls.io)


Patch:
diff --git a/src/index.ts b/src/index.ts
index cad4e8ba..1deb1a92 100644
--- a/src/index.ts
+++ b/src/index.ts
@@ -14,7 +14,7 @@ import { findDeclarationNode, findIdentifierNode } from './finder'
 import { evaluate } from './interpreter/interpreter'
 import { parse, parseAt } from './parser/parser'
 import { AsyncScheduler, PreemptiveScheduler } from './schedulers'
-import { getAllOccurrencesInScopeHelper } from './scope-refactoring'
+import { getAllOccurrencesInScopeHelper, getScopeHelper } from './scope-refactoring'
 import { areBreakpointsSet, setBreakpointAtLine } from './stdlib/inspector'
 import { getEvaluationSteps } from './stepper/stepper'
 import { sandboxedEval } from './transpiler/evalContainer'
@@ -175,6 +175,27 @@ export function findDeclaration(
   return declarationNode.loc
 }
 
+export function getScope(
+  code: string,
+  context: Context,
+  loc: { line: number; column: number }
+): SourceLocation[] {
+  const program = parse(code, context, true)
+  if (!program) {
+    return []
+  }
+  const identifierNode = findIdentifierNode(program, context, loc)
+  if (!identifierNode) {
+    return []
+  }
+  const declarationNode = findDeclarationNode(program, identifierNode)
+  if (!declarationNode || declarationNode.loc == null || identifierNode !== declarationNode) {
+    return []
+  }
+
+  return getScopeHelper(declarationNode.loc, program, identifierNode.name)
+}
+
 export function getAllOccurrencesInScope(
   code: string,
   context: Context,
diff --git a/src/scope-refactoring.ts b/src/scope-refactoring.ts
index d690330c..8c2f805a 100644
--- a/src/scope-refactoring.ts
+++ b/src/scope-refactoring.ts
@@ -209,6 +209,65 @@ function scopeForStatement(node: es.ForStatement): BlockFrame {
   return block
 }
 
+/*
+This function finds the list of location ranges
+where a given identifier is in scope.
+ */
+export function getScopeHelper(
+  definitionLocation: es.SourceLocation,
+  program: es.Program,
+  target: string
+): es.SourceLocation[] {
+  const lookupTree = scopeVariables(program)
+
+  // Find closest ancestor of node.
+  const block = getBlockFromLoc(definitionLocation, lookupTree)
+  const parentRange = block.loc
+
+  // Recurse on the children to find other
+  // definitions of the same identifier
+  const childBlocks = block.children.filter(isBlockFrame)
+  const childBlocksWithDefinitions = childBlocks
+    .map(child => getChildBlocksWithDefinitions(child, target))
+    .reduce((x, y) => [...x, ...y], [])
+
+  const rangeToExclude = childBlocksWithDefinitions.map(b => b.enclosingLoc)
+
+  if (parentRange && rangeToExclude.length === 0) {
+    return [parentRange]
+  }
+
+  const ranges: es.SourceLocation[] = []
+  let prevRange = rangeToExclude.shift()
+  ranges.push({ start: (parentRange as any).start, end: (prevRange as any).start })
+  rangeToExclude.map(range => {
+    ranges.push({ start: (prevRange as any).end, end: (rangeToExclude.shift() as any).start })
+    prevRange = range
+  })
+  ranges.push({ start: (prevRange as any).end, end: (parentRange as any).end })
+
+  return ranges
+}
+
+// Returns a list of the definitions of the
+// given identifier in block
+function getChildBlocksWithDefinitions(block: BlockFrame, target: string): BlockFrame[] {
+  const definitionNodes = block.children
+    .filter(isDefinitionNode)
+    .filter(node => node.name === target)
+
+  if (definitionNodes.length !== 0) {
+    return [block]
+  }
+
+  const childBlocks = block.children.filter(isBlockFrame)
+  const childBlocksWithDefinitions = childBlocks.map(child =>
+    getChildBlocksWithDefinitions(child, target)
+  )
+
+  return childBlocksWithDefinitions.reduce((x, y) => [...x, ...y], [])
+}
+
 /**
  * Gets all instances of a variable being used in the child scope.
  * Given the definition location on the variable, get the BlockFrame it resides in.


Test patch:
diff --git a/src/__tests__/__snapshots__/index.ts.snap b/src/__tests__/__snapshots__/index.ts.snap
index d663b9d8..d76de914 100644
--- a/src/__tests__/__snapshots__/index.ts.snap
+++ b/src/__tests__/__snapshots__/index.ts.snap
@@ -564,6 +564,111 @@ exports[`Find no declaration from occurrence when there is no declaration (synta
 
 exports[`Find no declaration from selection that does not refer to a declaration 1`] = `null`;
 
+exports[`Find scope of a function declaration 1`] = `
+Array [
+  SourceLocation {
+    "end": Position {
+      "column": 5,
+      "line": 8,
+    },
+    "start": Position {
+      "column": 4,
+      "line": 3,
+    },
+  },
+]
+`;
+
+exports[`Find scope of a function parameter 1`] = `
+Array [
+  SourceLocation {
+    "end": Position {
+      "column": 9,
+      "line": 7,
+    },
+    "start": Position {
+      "column": 22,
+      "line": 5,
+    },
+  },
+]
+`;
+
+exports[`Find scope of a nested variable declaration 1`] = `
+Array [
+  SourceLocation {
+    "end": Position {
+      "column": 5,
+      "line": 8,
+    },
+    "start": Position {
+      "column": 4,
+      "line": 3,
+    },
+  },
+]
+`;
+
+exports[`Find scope of a variable declaration 1`] = `
+Array [
+  Object {
+    "end": Position {
+      "column": 4,
+      "line": 3,
+    },
+    "start": Position {
+      "column": 0,
+      "line": 1,
+    },
+  },
+  Object {
+    "end": Position {
+      "column": 3,
+      "line": 10,
+    },
+    "start": Position {
+      "column": 5,
+      "line": 8,
+    },
+  },
+]
+`;
+
+exports[`Find scope of a variable declaration with more nesting 1`] = `
+Array [
+  Object {
+    "end": Position {
+      "column": 12,
+      "line": 6,
+    },
+    "start": Position {
+      "column": 4,
+      "line": 3,
+    },
+  },
+  Object {
+    "end": Position {
+      "column": 8,
+      "line": 11,
+    },
+    "start": Position {
+      "column": 13,
+      "line": 8,
+    },
+  },
+  Object {
+    "end": Position {
+      "column": 5,
+      "line": 14,
+    },
+    "start": Position {
+      "column": 9,
+      "line": 13,
+    },
+  },
+]
+`;
+
 exports[`Find variable declaration in block statement 1`] = `
 SourceLocation {
   "end": Position {
diff --git a/src/__tests__/index.ts b/src/__tests__/index.ts
index ce75c4b9..c9da5c84 100644
--- a/src/__tests__/index.ts
+++ b/src/__tests__/index.ts
@@ -9,7 +9,7 @@ import {
   expectToLooselyMatchJS,
   expectToMatchJS
 } from '../utils/testing'
-import { findDeclaration } from '../index'
+import { findDeclaration, getScope } from '../index'
 import { Position } from 'acorn/dist/acorn'
 import { SourceLocation } from 'estree'
 
@@ -686,3 +686,146 @@ test('Find declaration of of variable in update statement of a for loop', () =>
   expectResultsToMatch(actual, expected)
   expect(actual).toMatchSnapshot()
 })
+
+test('Find scope of a variable declaration', () => {
+  const context = createTestContext({ chapter: 4 })
+  const code = `{
+    const x = 1;
+    {
+        const x = 2;
+        function f(y) {
+            return x + y;
+        }
+    }
+    display(x);
+  }`
+  const expected = [
+    new SourceLocationTestResult(1, 0, 3, 4),
+    new SourceLocationTestResult(8, 5, 10, 3)
+  ]
+  const actual = getScope(code, context, { line: 2, column: 10 })
+  expected.forEach((expectedRange, index) => {
+    const actualRange = new SourceLocationTestResult(
+      actual[index].start.line,
+      actual[index].start.column,
+      actual[index].end.line,
+      actual[index].end.column
+    )
+    expectResultsToMatch(actualRange, expectedRange)
+  })
+  expect(actual).toMatchSnapshot()
+})
+
+test('Find scope of a nested variable declaration', () => {
+  const context = createTestContext({ chapter: 4 })
+  const code = `{
+    const x = 1;
+    {
+        const x = 2;
+        function f(y) {
+            return x + y;
+        }
+    }
+    display(x);
+  }`
+  const expected = [new SourceLocationTestResult(3, 4, 8, 5)]
+  const actual = getScope(code, context, { line: 4, column: 15 })
+  expected.forEach((expectedRange, index) => {
+    const actualRange = new SourceLocationTestResult(
+      actual[index].start.line,
+      actual[index].start.column,
+      actual[index].end.line,
+      actual[index].end.column
+    )
+    expectResultsToMatch(actualRange, expectedRange)
+  })
+  expect(actual).toMatchSnapshot()
+})
+
+test('Find scope of a function parameter', () => {
+  const context = createTestContext({ chapter: 4 })
+  const code = `{
+    const x = 1;
+    {
+        const x = 2;
+        function f(y) {
+            return x + y;
+        }
+    }
+    display(x);
+  }`
+  const expected = [new SourceLocationTestResult(5, 22, 7, 9)]
+  const actual = getScope(code, context, { line: 5, column: 19 })
+  expected.forEach((expectedRange, index) => {
+    const actualRange = new SourceLocationTestResult(
+      actual[index].start.line,
+      actual[index].start.column,
+      actual[index].end.line,
+      actual[index].end.column
+    )
+    expectResultsToMatch(actualRange, expectedRange)
+  })
+  expect(actual).toMatchSnapshot()
+})
+
+test('Find scope of a function declaration', () => {
+  const context = createTestContext({ chapter: 4 })
+  const code = `{
+    const x = 1;
+    {
+        const x = 2;
+        function f(y) {
+            return x + y;
+        }
+    }
+    display(x);
+  }`
+  const expected = [new SourceLocationTestResult(3, 4, 8, 5)]
+  const actual = getScope(code, context, { line: 5, column: 17 })
+  expected.forEach((expectedRange, index) => {
+    const actualRange = new SourceLocationTestResult(
+      actual[index].start.line,
+      actual[index].start.column,
+      actual[index].end.line,
+      actual[index].end.column
+    )
+    expectResultsToMatch(actualRange, expectedRange)
+  })
+  expect(actual).toMatchSnapshot()
+})
+
+test('Find scope of a variable declaration with more nesting', () => {
+  const context = createTestContext({ chapter: 4 })
+  const code = `{
+    const x = 1;
+    {
+        const x = 2;
+        function f(y) {
+            for (let x = 10; x < 20; x = x + 1) {
+                display(x);
+            }
+            return x + y;
+        }
+        for (let x = 10; x < 20; x = x + 1) {
+            display(x);
+        }
+    }
+    display(x);
+  }`
+  const expected = [
+    new SourceLocationTestResult(3, 4, 6, 12),
+    new SourceLocationTestResult(8, 13, 11, 8),
+    new SourceLocationTestResult(13, 9, 14, 5)
+  ]
+  const actual = getScope(code, context, { line: 4, column: 15 })
+  expected.forEach((expectedRange, index) => {
+    const actualRange = new SourceLocationTestResult(
+      actual[index].start.line,
+      actual[index].start.column,
+      actual[index].end.line,
+      actual[index].end.column
+    )
+    expectResultsToMatch(actualRange, expectedRange)
+  })
+  expect(actual).toMatchSnapshot()
+})
diff --git a/src/__tests__/scope-refactoring.ts b/src/__tests__/scope-refactoring.ts
index 11d71206..9225c50e 100644
--- a/src/__tests__/scope-refactoring.ts
+++ b/src/__tests__/scope-refactoring.ts
@@ -7,7 +7,8 @@ import {
   getBlockFromLoc,
   getAllIdentifiers,
   getNodeLocsInCurrentBlockFrame,
-  getBlockFramesInCurrentBlockFrame
+  getBlockFramesInCurrentBlockFrame,
+  getScopeHelper
 } from '../scope-refactoring'
 import { parse } from '../parser/parser'
 /* tslint:disable:max-classes-per-file */
@@ -476,3 +477,43 @@ if (true) {
     ).length
   ).toBe(6)
 })
+
+test('getScopeHelper', () => {
+  const program = `{
+    const x = 1;
+    {
+        const x = 2;
+        function f(y) {
+            return x + y;
+        }
+    }
+    display(x);
+  }`
+  const definitionLocation = {
+    start: { line: 2, column: 10 },
+    end: { line: 2, column: 11 }
+  }
+  expect(getScopeHelper(definitionLocation, parse(program, context, true) as any, 'x').length).toBe(
+    2
+  )
+})
+
+test('getScopeHelperNested', () => {
+  const program = `{
+    const x = 1;
+    {
+        const x = 2;
+        function f(y) {
+            return x + y;
+        }
+    }
+    display(x);
+  }`
+  const definitionLocation = {
+    start: { line: 4, column: 15 },
+    end: { line: 4, column: 16 }
+  }
+  expect(getScopeHelper(definitionLocation, parse(program, context, true) as any, 'x').length).toBe(
+    1
+  )
+})