Computing a new AST node by combining several AST nodes within scope (cascading partial override)

[shutterfreak]

I am creating a DSL for describing graphs in a textual declarative format, independent of the underlying technology (MermaidJS, GraphML...).

Here's the simplified grammar:

grammar Graph

entry Model:
    (elements+=Element | styles+=Style)* ;

Element: Graph | Node | Link ;

Graph:
    'graph' StyleID? name=ID label=Label?
    '{' (elements+=Element | styles+=Style)* '}' ;

Node:
    'node' StyleID? name=ID label=Label? ;

Link:
    'link' StyleID? ( '(' name=ID ')' )?
    src=[Element:ID] 'to' dst=[Element:ID] label=Label? ;


fragment StyleID:
    ':' style=[Style:ID] ;

Style:
	'style' name=ID StyleBlock ;

StyleBlock:
    ( '{}' ) | (
    '{' ';'* items+=StyleDefinition?
    (';'+ items+=StyleDefinition)* ';'* '}' ) ;

StyleDefinition:
    topic=ID ':' value=STRING ;
    

Label:
	BracketedLabel | StringLabel ;

BracketedLabel:
    label_bracketed=BRACKETED_STRING ;

StringLabel:
    label_string=STRING ;

terminal BRACKETED_STRING:
    /\[(\\.|[^\]\\])*\]/ ;

hidden terminal WS: /\s+/;
terminal ID: /[_a-zA-Z][\w_]*/;
terminal STRING: /"(\\.|[^"\\])*"|'(\\.|[^'\\])*'/;

hidden terminal ML_COMMENT: /\/\*[\s\S]*?\*\//;
hidden terminal SL_COMMENT: /\/\/[^\n\r]*/;

An Element can have an optional style identifier which should (or must) refer to any Style available within the local/global scope.

I am able to validate a document in terms of identifiers and scope for links and styles with:

export class GraphScopeComputation extends DefaultScopeComputation {
    override async computeExports(document: LangiumDocument<AstNode>): Promise<AstNodeDescription[]> {

        const exportedDescriptions: AstNodeDescription[] = [];
        for (const childNode of AstUtils.streamAllContents(document.parseResult.value)) {
            if (isElement(childNode)) {
                // Links can refer to any named Element (all Graph and Node elements, and named Link elements)
                if (childNode.name) {
                    exportedDescriptions.push(this.descriptions.createDescription(childNode, childNode.name, document));
                }
            } else if (isStyle(childNode)) {
                exportedDescriptions.push(this.descriptions.createDescription(childNode, childNode.name, document));
                // TODO: parse stype definitions and overrides
            }
        }

        return exportedDescriptions;
    }
}

I would also like to combine all applicable Style definitions that apply to the scope of any Element, similar to cascading style sheets (CSS). In essence, the root definition is the basis and all StyleDefinition elements of the same style redefined at a lower level gradually overwrite / complement the original style definition.

For instance:

graph g1 "My first graph" {
    node:decision n1 "A decision node"
    node n2 [a generic node]
    link n1 to n2
    link n1 to n3
    // A subgraph
    graph g2 {
        node n3
        link:yes (l1) n3 to n1 // This is the line we will discuss below
        style yes { Color: "bright green (override)" } // Only "Color" should be overridden
        style unreachable { unreachable: "true"} // unreachable for node n10 at top level
    }
}
link:no n3 to n2 // referencing to nodes is global
style yes { Color: "green (top level definition)" ; Label: "yes"}
style no { Color: "red (top level definition)" ; Label: "no" }
style decision { Shape: "diamond" ; Fill: "orange" }
link n1 to n5
node:unreachable n5 // style definition invisible for node n5
node:decision n10

In this example, link:yes (l1) n3 to n1 should obey:

1. style yes { Color: "green (top level definition)" ; Label: "yes"} defined at the top level
2. style yes { Color: "bright green (override)" } defined in graph g2 at the 2nd level.

The end result would be: style yes { Color: "bright green (override)"; Label: "yes" }.

Where should this transformation be implemented? And how could it be done?

[msujew]

Hey @shutterfreak,

generally, it is often an anti-pattern to programmatically compute/modify AST nodes. Depending on what you want to do with the data, I would recommend to create something like an intermediate representation for the style data. You can then either directly create an object of that interface/class directly from a style or compute it via a cascade of style nodes of your AST.

The reason for that is twofold:

• In your own data structure you don't need to adhere to the limitations placed on the interfaces by Langium
• By not modifying/changing the original AST you don't run into very-hard-to-debug behavior such as unexpected synthetic elements in the index and so on.

[cdietrich]

see also #1507

[shutterfreak]

In my DSL I need 2 different scope computations:

1. Style nodes obey the default langium scoping
2. Element nodes with a defined name (i.e., all Graph and Node nodes, and all named Link nodes) are visible globally (across hierarchy). They have unique names at file level.

The uniqueness of a name only matters for Element nodes. I defined a validation service which traverses the AST and checks all names found for uniqueness:

File graph-validator.ts:

import type { ValidationAcceptor, ValidationChecks } from "langium";
import type { GraphAstType, Element, Model } from "./generated/ast.js";
import type { GraphServices } from "./graph-module.js";
import chalk from "chalk";

/**
 * Register custom validation checks.
 */
export function registerValidationChecks(services: GraphServices) {
  const registry = services.validation.ValidationRegistry;
  const validator = services.validation.GraphValidator;
  const checks: ValidationChecks<GraphAstType> = {
    // Person: validator.checkPersonStartsWithCapital
    Model: validator.checkUniqueElementNames,
  };
  registry.register(checks, validator);
}

/**
 * Implementation of custom validations.
 */
export class GraphValidator {

  checkUniqueElementNames(model: Model, accept: ValidationAcceptor): void {
    // Create a set of identifiers while traversing the AST
    const identifiers = new Set<string>();

    function traverseElement(element: Element): void {
      const preamble = `traverseElement(${element.$type} element (${element.name ?? "<no name>"}))`;
      if (element.name !== undefined) {
        // The element has a name (note: links have an optional name)
        if (identifiers.has(element.name)) {
          // report an error if the identifier is not unique
          console.warn(
            chalk.red(
              `${preamble} - Duplicate name ${element.name} found for ${element.$type}.`,
            ),
          );
          accept("error", `Duplicate name '${element.name}'`, {
            node: element,
            property: "name",
          });
        } else {
          identifiers.add(element.name);
        }
      }

      if (element.$type === "Graph") {
        // Recurse
        for (const e of element.elements) {
          traverseElement(e);
        }
      }
    }

    // Traverse the elements in the model:
    for (const element of model.elements) {
      traverseElement(element);
    }
  }
}

To address the scoping requirements, I wrote the following:

File: graph-module.ts:

import {
  AstNode,
  AstNodeDescription,
  AstUtils,
  DefaultScopeComputation,
  LangiumDocument,
  type Module,
  MultiMap,
  PrecomputedScopes,
  inject,
} from "langium";
import {
  createDefaultModule,
  createDefaultSharedModule,
  type DefaultSharedModuleContext,
  type LangiumServices,
  type LangiumSharedServices,
  type PartialLangiumServices,
} from "langium/lsp";
import { GraphGeneratedModule, GraphGeneratedSharedModule } from "./generated/module.js";
import { GraphValidator, registerValidationChecks } from "./graph-validator.js";
import { isElement, isGraph, isModel, isStyle, Model } from "./generated/ast.js";

/**
 * Declaration of custom services - add your own service classes here.
 */
export interface GraphAddedServices {
  validation: {
    GraphValidator: GraphValidator;
  };
  references: {
    ScopeComputation: GraphScopeComputation;
  };
}

/**
 * Union of Langium default services and your custom services - use this as constructor parameter
 * of custom service classes.
 */
export type GraphServices = LangiumServices & GraphAddedServices;

/**
 * Dependency injection module that overrides Langium default services and contributes the
 * declared custom services. The Langium defaults can be partially specified to override only
 * selected services, while the custom services must be fully specified.
 */
export const GraphModule: Module<GraphServices, PartialLangiumServices & GraphAddedServices> = {
  validation: {
    GraphValidator: () => new GraphValidator(),
  },
  references: {
    ScopeComputation: (services) => new GraphScopeComputation(services),
  },
};

/**
 * Create the full set of services required by Langium.
 *
 * First inject the shared services by merging two modules:
 *  - Langium default shared services
 *  - Services generated by langium-cli
 *
 * Then inject the language-specific services by merging three modules:
 *  - Langium default language-specific services
 *  - Services generated by langium-cli
 *  - Services specified in this file
 *
 * @param context Optional module context with the LSP connection
 * @returns An object wrapping the shared services and the language-specific services
 */
export function createGraphServices(context: DefaultSharedModuleContext): {
  shared: LangiumSharedServices;
  Graph: GraphServices;
} {
  const shared = inject(createDefaultSharedModule(context), GraphGeneratedSharedModule);
  const Graph = inject(createDefaultModule({ shared }), GraphGeneratedModule, GraphModule);
  shared.ServiceRegistry.register(Graph);
  registerValidationChecks(Graph);
  if (!context.connection) {
    // We don't run inside a language server
    // Therefore, initialize the configuration provider instantly
    shared.workspace.ConfigurationProvider.initialized({}).catch((exception) => console.error(exception));
  }
  return { shared, Graph };
}

export class GraphScopeComputation extends DefaultScopeComputation {

  /**
   * Export all named Element nodes using their name (they are available globally)
   * NOTE: style definitions exist only at local level (default scoping) and can be overridden
   */
  // eslint-disable-next-line @typescript-eslint/require-await
  override async computeExports(document: LangiumDocument): Promise<AstNodeDescription[]> {
    const prefix = "GraphScopeComputation.computeExports()";
    const exportedDescriptions: AstNodeDescription[] = [];
    for (const childNode of AstUtils.streamAllContents(document.parseResult.value)) {
      if (isElement(childNode) && childNode.name !== undefined) {
        // `descriptions` is our `AstNodeDescriptionProvider` defined in `DefaultScopeComputation`
        // It allows us to easily create descriptions that point to elements using a name.
        const d = this.descriptions.createDescription(childNode, childNode.name, document);
        exportedDescriptions.push(d);
      }
    }

    return exportedDescriptions;
  }

  /**
   * To facilitate access to prior style (re)definitions in the local scope, we will add all relevant
   * styles to the local scope. This means:
   * (1) the styles defined at the current scope and
   * (2) the styles (re)defined at higer sope level
   *
   * The actual local scope extension (recursively) is implemented with class method processContainer().
   */
  // eslint-disable-next-line @typescript-eslint/require-await
  override async computeLocalScopes(document: LangiumDocument): Promise<PrecomputedScopes> {
    const model = document.parseResult.value as Model;
    // This multi-map stores a list of descriptions for each node in our document
    const scopes = new MultiMap<AstNode, AstNodeDescription>();

    this.processContainer(model, scopes, document);

    return scopes;
  }

  /**
   * Update the local scope of an AST node. This method is called recursively on all relevant
   * nodes which might contain style (re)definitions, relevant for the local scope.
   */
  private processContainer(
    container: AstNode,
    scopes: PrecomputedScopes,
    document: LangiumDocument
  ): AstNodeDescription[] {
    const localDescriptions: AstNodeDescription[] = [];

    // Only add style definitions at (1) the current scope and (2) all parent levels

    if (isModel(container) || isGraph(container)) {
      // Process style definitions at the local scope

      for (const style of container.styles) {
        const description = this.descriptions.createDescription(style, style.name, document);
        localDescriptions.push(description);
      }

      // Recurse on elements
      for (const element of container.elements) {
        this.processContainer(element, scopes, document);
      }
    }

    // Add the newly created local descriptions to the current scope
    scopes.addAll(container, localDescriptions);

    return localDescriptions;
  }
}

In essence:

• computeExports()takes care of exposing all Element nodes that have a name identifier defined to the global scope so they can be used in the linking process.
• computeLocalScopes() extends the local scope by adding Style nodes at the local scope and higher up in the model hierarchy.

Then, there's the selective overwriting of style definitions, a bit akin cascading stylesheets. My current approach doesn't make use of local scope to determine relevant Styledefinitions to consider when parsing a styled Element AST node:

File: model-helpers.ts:

import chalk from "chalk";
import { AstNode } from "langium";
import { inspect } from "util";
import { integer } from "vscode-languageserver";
import { Element, isGraph, isModel, Style, StyleDefinition } from "../language/generated/ast.js";

export function Element_get_style_items(element: Element): StyleDefinition[] | undefined {
  if (element.style !== undefined) {
    // The element has a style assigned (which must refer to at least one Style node in scope having the same name
    const style_name = element.style.$refText; // This is the text used in a reference (e.g., from a Node to a Style)

    // const styles: Style[] = [];
    let container: AstNode | undefined = element; //.$container
    let level: integer = 0;
    interface StyleDefintionDecomposed {
      topic: string;
      level: integer;
      value: string;
      item: StyleDefinition;
    }
    const decomposed_style_definitions: StyleDefintionDecomposed[] = [];
    const decomposed_style_definitions_filtered: StyleDefintionDecomposed[] = [];

    while (container !== undefined) {
      // process the container hierarchy, bottom-up
      if (container.$container === undefined) {
        // At top level (Model)
        container = undefined;
      } else {
        // There is still one level up in the hierarchy
        container = container.$container;
        // Process the style elements in the parent (Model or Graph) container
        if (isModel(container) || isGraph(container)) {
          for (const s of container.styles) {
            if (s.name === style_name) {
              console.debug(chalk.greenBright(`Found matching ${s.$type} '${style_name}' at level ${level}`));

              // Push the style items to decomposed_style_definitions

              const defs: string[] = [];
              for (const it of s.definition.items) {
                console.debug(chalk.gray(`At level ${level} - ${s.name}: ${it.topic}: "${it.value}"`));
                defs.push(`[${it.topic}] := [${it.value}]`);
                // Alternative A. store all matching items (don't overwrite them):
                decomposed_style_definitions.push({
                  topic: it.topic,
                  level,
                  value: it.value,
                  item: it,
                });
                // Alternative B. overwrite items if the topic (e.g., 'FillColor') is the same:
                if (decomposed_style_definitions_filtered.find((dsd) => dsd.topic === it.topic) === undefined) {
                  decomposed_style_definitions_filtered.push({
                    topic: it.topic,
                    level,
                    value: it.value,
                    item: it,
                  });
                }
              }

              // styles.push(s);
            } // skip other AST node types
          }
        } else {
          console.error(chalk.redBright(`Unexpected container type: ${container.$type}`));
        }
      }
      level += 1;
    }

    // Now filter the style items starting from the topmost definition in the model hierarchy:
    decomposed_style_definitions.sort((a, b) => {
      if (a.topic === b.topic) {
        return a.level - b.level;
      }
      return a.topic > b.topic ? -1 : 1;
    });

    console.debug(
      chalk.greenBright(
        style_name,
        "decomposed_style_definitions (before filtering) := ",
        inspect(decomposed_style_definitions)
      )
    );

    console.debug(
      chalk.yellowBright(
        style_name,
        "decomposed_style_definitions (after filtering) := ",
        inspect(decomposed_style_definitions_filtered)
      )
    );

    //return styles
    return decomposed_style_definitions_filtered.map((s) => s.item);
  }
  return undefined;
}

Is this the way to go, or should I use the local scope enriched by my custom computeLocalScopes() method?

[shutterfreak]

Meanwhile I rewrote Element_get_style_items() and also added initial support for resetting style ("Reset" topic).

/**
 * Construct an array of style items that apply to the Element.
 * If the element has no style, or no style items can be found for the style provided, then an empty array is returned.
 * In all other cases, a scoped array of style items will be generated, following the following rules:
 *  - Style items at the same level in the model are combined in the order they appear.
 *  - When combining style items with the same topic, the last item is kept (overrruling previous topic definitions)
 *  - Style items at a given nesting level inherit style definitions from previous levels
 * @param element The element that may have to be styled
 * @returns The array of unique style items applicable to the element, or undefined if element not defined or style not provided
 */
export function Element_get_style_items(
  element: Element,
): StyleDefinition[] | undefined {
  if (element.style === undefined) {
    return undefined;
  }
  // The element has a style
  const filtered_style_definitions: StyleDefinition[] = [];

  //collect the element's ancestry (bottom-up):
  const ancestry: AstNode[] = [];
  let container: AstNode = element;
  while (container.$container) {
    ancestry.push(container.$container);
    container = container.$container;
  }

  // Process the ancestry top-down:
  for (const ancestor of ancestry.reverse()) {
    // Search for style definitions with the proper style identifier:
    if (isModel(ancestor) || isGraph(ancestor)) {
      // Useless check (required for linter)
      for (const s of ancestor.styles) {
        if (s.name === element.style.$refText) {
          // Matching style found - Process the style items, taking care of scope, redefinition and reset rules
          for (const d of s.definition.items) {
            // First check reset topic:
            if (d.topic === "Reset") {
              // Check which topics must be reset
              if (["All", "*"].includes(d.value)) {
                // Reset entire style definition:
                filtered_style_definitions.length = 0;
              } else {
                console.error(
                  chalk.redBright(
                    `ERROR: NOT YET IMPLEMENTED: reset style with argument '${d.value}'`,
                  ),
                );
              }
            } else {
              // Retrieve the index of the style definition with the same topic (returns -1 if no match)
              const index = filtered_style_definitions.findIndex(
                (it) => it.topic === d.topic,
              );
              if (index < 0) {
                // No match: add to array
                filtered_style_definitions.push(d);
              } else {
                // Match: replace existing style defintion with new one
                filtered_style_definitions.splice(index, 1, d);
              }
            }
          }
        }
      }
    }
  }

  // Debug statements:
  for (const d of filtered_style_definitions) {
    console.log(
      chalk.bgWhite.blueBright(`Filtered: ${d.topic}: "${d.value}";`),
    );
  }

  return filtered_style_definitions;
}

Right now I am using this code in my generator.

I now also warn the user when several Style entries have been defined at the same level (Model or a given Graph node):

/**
   * Check the Style nodes through the entire Model hierarchy:
   *  - Report if multiple Style defintions share the same name at ehe same hierarchy level
   *
   * @param model
   * @param accept
   */
  checkStyles(model: Model, accept: ValidationAcceptor): void {
    console.info(chalk.cyanBright("checkStyles(model)"));

    // Traverse the model top-down) and store the graph nodes and their levels:
    const style_dict: _find_style_dict[] = find_styles(model, 0, 0, accept);
    for (const item of style_dict) {
      console.info(
        chalk.cyan(
          `checkStyles(model): ${item.containerID} - ${item.level} : Style '${item.style.name}' : [ ${StyleDefinition_toString(item.style.definition.items)} ]`,
        ),
      );
    }

    // Check style_dict at all (container_name, level) for duplicate style declarations:

    // Iterate over all containers (Model + Graph)

    const d: Record<string, Record<string, Style[]>> = {};

    for (const item of style_dict) {
      if (!(item.containerID in d)) {
        // Initialize:
        d[item.containerID] = {};
      }
      if (!(item.style.name in d[item.containerID])) {
        d[item.containerID][item.style.name] = [];
      }
      // Push to array:
      d[item.containerID][item.style.name].push(item.style);
    }

    // Now compute counts per node:
    for (const container_id in d) {
      // Count occurrences of style name
      for (const style_name in d[container_id]) {
        if (d[container_id][style_name].length > 1) {
          // Multiple Style definitions with same name: issue warning
          for (const duplicate_style_definition of d[container_id][
            style_name
          ]) {
            console.warn(
              chalk.red(
                `Warning: Multiple style definitions with name '${style_name}' at the same level should be merged. Found: ${StyleDefinition_toString(duplicate_style_definition.definition.items)}`,
              ),
            );
            accept(
              "warning",
              `Multiple style definitions with name '${style_name}' at the same level should be merged.`,
              {
                node: duplicate_style_definition,
                property: "name",
              },
            );
          }
        }
      }
    }
  }
}

interface _find_style_dict {
  level: number;
  containerID: string;
  style: Style;
}

function find_styles(
  container: Model | Graph,
  level: number,
  seq: number,
  accept: ValidationAcceptor,
): _find_style_dict[] {
  const style_dict: _find_style_dict[] = [];

  // Iterate over all styles defined in the container:
  for (const style of container.styles) {
    // Add the style:
    style_dict.push({
      level,
      containerID:
        `${seq}::` + (isModel(container) === true ? "" : container.name),
      style,
    });
  }
  // Traverse the graph elements recursively for styles:
  for (const graph of container.elements.filter((e) => e.$type === Graph)) {
    style_dict.push(...find_styles(graph, level + 1, seq + 1, accept));
  }
  return style_dict;
}

I'll add code later on to:

• Report duplicate style redefinitions (requires comparing the StyleItem entries in each Style)
• Recommend the user to place style definitions before graph elements (Graph / Node / Link) This will require changes to the current scope computation.