Dashboard: AST Distance Metrics

Relevant source files

The following files were used as context for generating this wiki page:

• frontend/src/components/dashboard/hooks/ast-distance/index.ts
• frontend/src/components/dashboard/hooks/ast-distance/pqgrams-distance.ts
• frontend/src/components/dashboard/hooks/ast-distance/zhangshasha-distance.ts
• frontend/jqgram.d.ts
• frontend/package.json
• backend/src/ast/converters/scratch/tests/scratch-ast-converter.service.spec.ts

The AST Distance Metrics system provides a quantitative method for comparing student code solutions by calculating the "distance" between their Abstract Syntax Trees (ASTs). This functionality is crucial for features in the analysis dashboard, such as identifying dissimilar solutions or grouping similar ones. It abstracts different tree comparison algorithms, allowing the system to use the most appropriate metric for a given analysis task.

The system is designed to operate on a GeneralAst structure, which is an array of ActorNode objects. Each ActorNode represents a component (like a "Sprite" in Scratch) and contains its own tree of event listeners and function declarations. The distance metrics work by traversing these tree structures to compute a similarity score.

Sources: frontend/src/components/dashboard/hooks/ast-distance/index.ts, backend/src/ast/converters/scratch/tests/scratch-ast-converter.service.spec.ts:15-20

Core Abstraction

The core of the system is built around a generic interface and a factory function that provides a specific algorithm implementation on demand. This design allows for easy extension with new distance algorithms in the future.

Sources: frontend/src/components/dashboard/hooks/ast-distance/index.ts

AstDistanceAlgorithm Enum

This enum defines the available AST distance calculation algorithms.

Algorithm	Description
pqGram	Uses the pq-Gram profile-based distance metric.
zhangShasha	Uses the Zhang-Shasha tree edit distance algorithm.

Sources: frontend/src/components/dashboard/hooks/ast-distance/index.ts:10-14

AstDistance Interface

This interface defines the contract for all AST distance algorithms. It requires a single method, distance, which takes two ASTs and returns a numerical value representing the distance between them.

// frontend/src/components/dashboard/hooks/ast-distance/index.ts

export interface AstDistance {
  distance(ast1: GeneralAst, ast2: GeneralAst): number;
}

Sources: frontend/src/components/dashboard/hooks/ast-distance/index.ts:16-18

getAstDistance Factory Function

This factory function is the main entry point for using the distance metrics. It takes an AstDistanceAlgorithm enum member as input and returns an instance of the corresponding algorithm class.

The diagram below illustrates the flow of the getAstDistance factory function.

Implemented Algorithms

The system currently implements two distinct algorithms for calculating AST distance.

pq-Gram Distance

This algorithm calculates the distance based on the "pq-Gram profile" of the trees. A pq-Gram is a specific type of subtree fragment. The distance is computed by comparing the sets of pq-Grams from each tree. This implementation uses the jqgram library.

The PqGramsDistance class implements the AstDistance interface. The distance method converts the GeneralAst into a format compatible with the jqgram library, calculates the distance, and normalizes the result. The p and q values for the pq-Gram calculation are hardcoded to 2 and 3 respectively.

// frontend/src/components/dashboard/hooks/ast-distance/pqgrams-distance.ts

export class PqGramsDistance implements AstDistance {
  private readonly p = 2;
  private readonly q = 3;

  // ...

  distance(ast1: GeneralAst, ast2: GeneralAst): number {
    const tree1 = this.toJqGramTree(ast1);
    const tree2 = this.toJqGramTree(ast2);

    const profile1 = this.treeToProfile(tree1);
    const profile2 = this.treeToProfile(tree2);

    const union = new Set([...profile1, ...profile2]).size;

    if (union === 0) {
      return 0;
    }

    return 1 - intersection(profile1, profile2).size / union;
  }
}

Sources: frontend/src/components/dashboard/hooks/ast-distance/pqgrams-distance.ts:11-37, frontend/jqgram.d.ts

Zhang-Shasha Distance

This algorithm implements the classic Zhang-Shasha algorithm, which calculates the tree edit distance. This distance is the minimum cost of a sequence of operations (insert, delete, rename) to transform one tree into another. This implementation relies on the edit-distance library.

The ZhangShashaDistance class converts the GeneralAst into a tree structure that the zhangShasha function from the library can process. The children function defines how to get child nodes, and the label function provides the node's type as its label for comparison. The cost function for insert and remove is 1, and for update (rename) is 1 if labels are different, and 0 otherwise.

// frontend/src/components/dashboard/hooks/ast-distance/zhangshasha-distance.ts

export class ZhangShashaDistance implements AstDistance {
  distance(ast1: GeneralAst, ast2: GeneralAst): number {
    const tree1 = this.toTree(ast1);
    const tree2 = this.toTree(ast2);

    const result = zhangShasha(tree1, tree2, {
      children: (node) => this.getChildren(node),
      label: (node) => node.nodeType,
      // ... cost functions
    });

    return result;
  }
  // ...
}

Sources: frontend/src/components/dashboard/hooks/ast-distance/zhangshasha-distance.ts:10-33

Comparison of Algorithms

Feature	pq-Gram Distance	Zhang-Shasha Distance
Core Concept	Profile-based similarity	Tree Edit Distance
Measures	Similarity of subtree fragments	Cost to transform one tree into another
Library	jqgram	edit-distance
Complexity	Generally faster for large trees	Can be computationally expensive

Sources: frontend/src/components/dashboard/hooks/ast-distance/pqgrams-distance.ts, frontend/src/components/dashboard/hooks/ast-distance/zhangshasha-distance.ts, frontend/package.json:80,82

Dependencies

The AST distance calculation feature relies on external npm packages.

Package	Version	Purpose
jqgram	^0.2.5	Provides the pq-Gram distance calculation.
edit-distance	^1.0.5	Provides the Zhang-Shasha tree edit distance algorithm.

Sources: frontend/package.json:80,82