CS-MAST

Context-Stratified Merkelized Abstract Syntax Tree — reference TypeScript implementation.

CS-MAST extends an AST with Merkle-style cryptographic signatures (CS-MAST-S) on every node, enabling constant-time fingerprint lookup and deterministic subtree matching in SAST scanners. See the specification paper for the full algorithm description.

---

Install

npm install @shriyanss/cs-mast

---

Quick Start

import { cs_mast_init, cs_mast_s_exists } from "@shriyanss/cs-mast";

const tree = cs_mast_init(`const greet = (name) => "hello " + name;`, {
    hash: "sha256",
    lang: "js",
    lver: "es2022",
    prsr: "@babel/parser",
    scat: ["lit", "val", "id", "name", "decl"],
    sinc: [],
});

console.log(tree.rootSignature);
// $v=1$hash=sha256,lang=js,lver=es2022,prsr=-babel/parser,scat=lit_val_id_name_decl$<hex>

console.log(cs_mast_s_exists(tree, tree.rootSignature)); // true
console.log(cs_mast_s_exists(tree, "$v=1$...$fake")); // false

---

API

cs_mast_init(source, config, adapter?)

Parses source, traverses post-order, attaches cs-mast-s-hash to every actively-hashed Babel node, and builds the O(1) signature hashmap.

interface CsMastTree {
    root: AdapterNode; // File node — every descendant has computedHash set
    rootHash: string; // 64-char hex of the File node
    rootSignature: string; // full PHC signature of root (empty if root not actively hashed)
    config: CsMastConfig;
    adapter: IParserAdapter;
    readonly _signatureMap: ReadonlyMap<string, string>; // full-sig → pathKey
}

cs_mast_s_exists(tree, signature)

O(1) boolean lookup backed by the hashmap built during init. Accepts the full PHC signature string.

cs_mast_init_codebase(files, config, adapter?)

Process multiple files with the same config, derive a codebase-level hash:

const result = cs_mast_init_codebase(
    [
        { filename: "a.js", source: "..." },
        { filename: "b.js", source: "..." },
    ],
    config
);
result.codebaseHash; // sha256(sorted([h1,h2,...]).join('')) — order-independent
result.codebaseSignature; // full PHC string with codebaseHash

parseSignature(sig) / buildSignature(parts)

Encode and decode CS-MAST-S PHC strings. parseSignature returns null for invalid input.

---

Config (CsMastConfig)

Field	Required	Description
hash	yes	Hash algorithm. Only 'sha256' supported.
lang	yes	Shortest file extension, e.g. 'js'.
lver	no	Language version, e.g. 'es6', 'es2022'.
prsr	yes	Parser name. Characters outside [a-zA-Z0-9/+.-] are replaced by -.
scat	yes*	Active scat category codes (see Table I below).
sinc	yes*	Exact Babel node type names to include verbatim.

*At least one of scat or sinc must be non-empty.

scat Categories (Table I from spec)

Code	Babel Node Types	Behaviour
lit	StringLiteral, NumericLiteral, BooleanLiteral, RegExpLiteral, NullLiteral, BigIntLiteral	Hash literal type; add value if val also active
id	Identifier, PrivateName, JSXIdentifier	Hash node type; add name if name also active
op	Binary/Unary/Update/AssignmentExpression	Hash child hashes; add operator symbol if op_name active
decl	VariableDeclaration, FunctionDeclaration, ClassDeclaration, ImportDeclaration	Include node type/kind in hash
loop	For/While/DoWhile/ForIn/ForOfStatement	sha256(NodeType + sortedActiveChildHashes)
cond	IfStatement, SwitchStatement, ConditionalExpression	Double-hash: sha256(sha256(NodeType)+sha256(Test?)+sha256(Consequent))
name	Modifier — adds .name to identifier hashes	—
val	Modifier — adds .value to literal and conditional hashes	—
op_name	Modifier — adds .operator to operator hashes	—

---

CS-MAST-S Signature Format

$v=1$hash=sha256,lang=js,lver=es6,prsr=-babel/parser,scat=lit_val_id,sinc=IfStatement$<64hex>

• No salt — salting would break the determinism required for subtree matching.
• Multiple scat / sinc values joined by _.
• Hash portion: always 64-char lowercase SHA-256 hex.

---

Mutation Guard

Calling any of the following on a CS-MAST tree node path throws MutationError: replaceWith, replaceWithMultiple, replaceWithSourceString, replaceInline, insertBefore, insertAfter, remove, pushContainer, unshiftContainer.

To modify source code, call cs_mast_init again on the updated source.

---

Extending to New Languages

Implement IParserAdapter from src/types/parser-adapter.ts. See src/adapters/README.md.

---

Spec Ambiguities

See CLAUDE.md sections A1–A11 for all documented assumptions where the spec leaves details unspecified (separator policy, unary operator handling, codebase hash construction, etc.).