/******************************************************************************
 * Copyright 2021 TypeFox GmbH
 * This program and the accompanying materials are made available under the
 * terms of the MIT License, which is available in the project root.
 ******************************************************************************/ import _ from 'lodash' ; import * as langium from 'langium' ; import { getDocument , getRuleType , getTypeName , isDataTypeRule , isParserRule , LangiumDocuments , resolveImport } from 'langium' ; import { CompositeGeneratorNode , IndentNode , NL } from 'langium' ; import { processGeneratorNode } from 'langium' ; import { Cardinality , isOptional } from 'langium' ; import { URI } from 'vscode-uri' ; type TypeAlternative = { name : string ; super : string [ ] ; fields : Field [ ] ; ruleCalls : string [ ] ; hasAction : boolean ; } ; type Field = { name : string ; array : boolean ; optional : boolean ; types : string [ ] ; reference : boolean ; } ; type TypeCollection = { types : string [ ] ; reference : boolean ; } ; type CollectorState = { tree : TypeTree ; types : TypeAlternative [ ] ; cardinalities : Cardinality [ ] ; lastRuleCall ? : langium . RuleCall ; } ; export class Interface { name : string ; superTypes : string [ ] ; subTypes : string [ ] = [ ] ; containerTypes : string [ ] = [ ] ; fields : Field [ ] ; constructor ( name , superTypes , fields ) { this . name = name ; this . superTypes = Array . from ( new Set < string > ( superTypes ) ) ; this . fields = fields ; } toString ( ) { const interfaceNode = new CompositeGeneratorNode ( ) ; const superTypes = this . superTypes . length > 0 ? this . superTypes : [ 'AstNode' ] ; interfaceNode . contents . push ( 'export interface ' , this . name , ' extends ' , superTypes . join ( ', ' ) , ' {' , NL ) ; const fieldsNode = new IndentNode ( ) ; if ( this . containerTypes . length > 0 ) { fieldsNode . contents . push ( 'readonly $container: ' , Array . from ( new Set < string > ( this . containerTypes ) ) . join ( ' | ' ) , ';' , NL ) ; } for ( const field of this . fields . sort ( ( a , b ) => a . name . localeCompare ( b . name ) ) ) { const option = field . optional && field . reference && ! field . array ? '?' : '' ; let type = field . types . join ( ' | ' ) ; type = field . reference ? 'Reference<' + type + '>' : type ; type = field . array ? 'Array<' + type + '>' : type ; fieldsNode . contents . push ( field . name , option , ': ' , type , NL ) ; } interfaceNode . contents . push ( fieldsNode , '}' , NL , NL ) ; interfaceNode . contents . push ( `export const ${ this . name } = '${ this . name }';` , NL , NL ) ; interfaceNode . contents . push ( 'export function is' , this . name , '(item: unknown): item is ' , this . name , ' {' , NL ) ; const methodBody = new IndentNode ( ) ; methodBody . contents . push ( `return reflection.isInstance(item, ${ this . name });` , NL ) ; interfaceNode . contents . push ( methodBody , '}' , NL ) ; return processGeneratorNode ( interfaceNode ) ; } } class TypeTree { descendents : Map < TypeAlternative , TypeAlternative [ ] > = new Map ( ) ; addRoot ( root ) { this . descendents . set ( root , [ ] ) ; } split ( type , count ) { const descendents = [ ] ; for ( let i = 0 ; i < count ; i ++ ) { const clone = _ . cloneDeep ( type ) ; descendents . push ( clone ) ; this . descendents . set ( clone , [ ] ) ; } this . descendents . set ( type , descendents ) ; return descendents ; } getLeafNodesOf ( type ) { const leaves = [ ] ; const direct = this . descendents . get ( type ) ?? [ ] ; for ( const directDesc of direct ) { if ( ! this . hasLeaves ( directDesc ) ) { leaves . push ( directDesc ) ; } else { leaves . push ( ... this . getLeafNodesOf ( directDesc ) ) ; } } if ( leaves . length === 0 ) { leaves . push ( type ) ; } return leaves ; } getLeafNodes ( ) { const leaves = [ ] ; for ( const [ type , children ] of this . descendents . entries ( ) ) { if ( children . length === 0 ) { leaves . push ( type ) ; } } return leaves ; } hasLeaves ( type ) { return ( this . descendents . get ( type ) ?? [ ] ) . length > 0 ; } } export function collectAst ( documents , grammars ) { const state = createState ( ) ; const parserRules = collectAllParserRules ( documents , grammars ) ; const allTypes = [ ] ; for ( const rule of parserRules ) { state . tree = new TypeTree ( ) ; const type = simpleType ( rule ) ; state . tree . addRoot ( type ) ; collectElement ( state , type , rule . alternatives ) ; allTypes . push ( ... state . tree . getLeafNodes ( ) ) ; } return calculateAst ( allTypes ) ; } function collectAllParserRules ( documents , grammars , rules = new Set ( ) , visited = new Set ( ) ) { for ( const grammar of grammars ) { const doc = getDocument ( grammar ) ; if ( visited . has ( doc . uri ) ) { continue ; } visited . add ( doc . uri ) ; for ( const rule of grammar . rules ) { if ( langium . isParserRule ( rule ) && ! rule . fragment && ! isDataTypeRule ( rule ) ) { rules . add ( rule ) ; } } const importedGrammars = grammar . imports . map ( e => resolveImport ( documents , e ) ! ) ; collectAllParserRules ( documents , importedGrammars , rules , visited ) ; } return Array . from ( rules ) ; } function createState ( type ? ) { const state = { types : [ ] , cardinalities : [ ] , tree : new TypeTree ( ) } ; if ( type ) { state . tree . addRoot ( type ) ; } return state ; } function simpleType ( rule ) { return { name : getTypeName ( rule ) , super : [ ] , fields : [ ] , ruleCalls : [ ] , hasAction : false } ; } function enterGroup ( state , cardinality ) { state . cardinalities . push ( cardinality ) ; } function leaveGroup ( state ) { state . cardinalities . pop ( ) ; } function isStateOptional ( state ) { return state . cardinalities . some ( e => isOptional ( e ) ) ; } function collectElement ( state , type , element ) { enterGroup ( state , element . cardinality ) ; if ( isOptional ( element . cardinality ) ) { const [ item ] = state . tree . split ( type , 2 ) ; type = item ; } if ( langium . isAlternatives ( element ) ) { const splits = state . tree . split ( type , element . elements . length ) ; for ( let i = 0 ; i < splits . length ; i ++ ) { const item = element . elements [ i ] ; const splitType = splits [ i ] ; collectElement ( state , splitType , item ) ; } } else if ( langium . isGroup ( element ) || langium . isUnorderedGroup ( element ) ) { for ( const item of element . elements ) { const leaves = state . tree . getLeafNodesOf ( type ) ; for ( const leaf of leaves ) { collectElement ( state , leaf , item ) ; } } } else if ( langium . isAction ( element ) ) { addAction ( state , type , element ) ; } else if ( langium . isAssignment ( element ) ) { addAssignment ( state , type , element ) ; } else if ( langium . isRuleCall ( element ) ) { addRuleCall ( state , type , element ) ; } leaveGroup ( state ) ; } function addAction ( state , type , action ) { if ( action . type !== type . name ) { type . super . push ( type . name ) ; } type . hasAction = true ; type . name = action . type ; if ( action . feature && action . operator ) { if ( state . lastRuleCall ) { type . fields . push ( { name : action . feature , array : action . operator === '+=' , optional : false , reference : false , types : [ getTypeName ( state . lastRuleCall . rule ?. ref ) ] } ) ; } else { throw new Error ( 'Actions with features can only be called after an unassigned rule call' ) ; } } } function addAssignment ( state , type , assignment ) { const typeItems = { types : [ ] , reference : false } ; findTypes ( assignment . terminal , typeItems ) ; type . fields . push ( { name : assignment . feature , array : assignment . operator === '+=' , optional : isOptional ( assignment . cardinality ) || isStateOptional ( state ) , types : assignment . operator === '?=' ? [ 'boolean' ] : typeItems . types , reference : typeItems . reference } ) ; } function findTypes ( terminal , types ) { if ( langium . isAlternatives ( terminal ) || langium . isUnorderedGroup ( terminal ) || langium . isGroup ( terminal ) ) { findInCollection ( terminal , types ) ; } else if ( langium . isKeyword ( terminal ) ) { types . types . push ( `'${ terminal . value }'` ) ; } else if ( langium . isRuleCall ( terminal ) ) { if ( isParserRule ( terminal . rule . ref ) && isDataTypeRule ( terminal . rule . ref ) ) { types . types . push ( terminal . rule . ref . name ) ; } else { types . types . push ( getRuleType ( terminal . rule . ref ) ) ; } } else if ( langium . isCrossReference ( terminal ) ) { types . types . push ( getRuleType ( terminal . type . ref ) ) ; types . reference = true ; } } function findInCollection ( collection , types ) { for ( const element of collection . elements ) { findTypes ( element , types ) ; } } function addRuleCall ( state , type , ruleCall ) { const rule = ruleCall . rule . ref ; if ( langium . isParserRule ( rule ) && rule . fragment ) { const fragmentType = simpleType ( rule ) ; const fragmentState = createState ( fragmentType ) ; collectElement ( fragmentState , fragmentType , rule . alternatives ) ; const types = calculateAst ( fragmentState . tree . getLeafNodes ( ) ) ; const foundType = types . find ( e => e . name === rule . name ) ; if ( foundType ) { type . fields . push ( ... foundType . fields ) ; } } else if ( langium . isParserRule ( rule ) ) { type . ruleCalls . push ( getRuleType ( rule ) ) ; state . lastRuleCall = ruleCall ; } } function flattenTypes ( alternatives ) { const names = new Set < string > ( alternatives . map ( e => e . name ) ) ; const types = [ ] ; for ( const name of names ) { const fields = [ ] ; const ruleCalls = new Set < string > ( ) ; const type = { name , fields , ruleCalls : < string [ ] > [ ] , super : < string [ ] > [ ] , hasAction : false } ; const namedAlternatives = alternatives . filter ( e => e . name === name ) ; for ( const alt of namedAlternatives ) { type . super . push ( ... alt . super ) ; type . hasAction = type . hasAction || alt . hasAction ; const altFields = alt . fields ; for ( const altField of altFields ) { const existingField = fields . find ( e => e . name === altField . name ) ; if ( existingField ) { existingField . optional = existingField . optional && altField . optional ; const typeSet = new Set ( existingField . types ) ; for ( const type of altField . types ) { typeSet . add ( type ) ; } existingField . types = Array . from ( typeSet . values ( ) ) ; } else { fields . push ( { ... altField } ) ; } } if ( altFields . length === 0 ) { for ( const ruleCall of alt . ruleCalls ) { ruleCalls . add ( ruleCall ) ; } } } type . ruleCalls = Array . from ( ruleCalls ) ; types . push ( type ) ; } return types ; } function calculateAst ( alternatives ) { const interfaces = [ ] ; const ruleCallAlternatives = [ ] ; const flattened = flattenTypes ( alternatives ) ; for ( const flat of flattened ) { const type = new Interface ( flat . name , flat . super , flat . fields ) ; interfaces . push ( type ) ; if ( flat . ruleCalls . length > 0 ) { ruleCallAlternatives . push ( flat ) ; } } for ( const ruleCallType of ruleCallAlternatives ) { let exists = false ; for ( const ruleCall of ruleCallType . ruleCalls ) { const calledInterface = interfaces . find ( e => e . name === ruleCall ) ; if ( calledInterface && calledInterface . name === ruleCallType . name ) { exists = true ; } else if ( calledInterface ) { calledInterface . superTypes . push ( ruleCallType . name ) ; } } if ( ! exists && ! interfaces . some ( e => e . name === ruleCallType . name ) ) { interfaces . push ( new Interface ( ruleCallType . name , ruleCallType . super , [ ] ) ) ; } } for ( const type of interfaces ) { type . superTypes = Array . from ( new Set ( type . superTypes ) ) ; } removeInvalidSuperTypes ( interfaces ) ; liftFields ( interfaces ) ; buildContainerTypes ( interfaces ) ; return sortTypes ( interfaces ) ; } function removeInvalidSuperTypes ( interfaces ) { for ( const type of interfaces ) { const toRemove = [ ] ; for ( const superType of type . superTypes ) { if ( ! interfaces . some ( e => e . name === superType ) ) { toRemove . push ( superType ) ; } } type . superTypes = type . superTypes . filter ( e => ! toRemove . includes ( e ) ) ; } } function buildContainerTypes ( interfaces ) { for ( const type of interfaces ) { for ( const field of type . fields . filter ( e => ! e . reference ) ) { for ( const fieldTypeName of field . types ) { const fieldType = interfaces . find ( e => e . name === fieldTypeName ) ; if ( fieldType ) { fieldType . containerTypes . push ( type . name ) ; } } } } const connectedComponents = [ ] ; calculateSubTypes ( interfaces ) ; calculateConnectedComponents ( connectedComponents , interfaces ) ; shareAndLiftContainerTypes ( connectedComponents ) ; } function calculateSubTypes ( interfaces ) { for ( const type of interfaces ) { for ( const superTypeName of type . superTypes ) { const superType = interfaces . find ( e => e . name === superTypeName ) ; if ( superType ) { superType . subTypes . push ( type . name ) ; } } type . subTypes = Array . from ( new Set < string > ( type . subTypes ) ) ; } } function calculateConnectedComponents ( connectedComponents , interfaces ) { const visited = new Set ( ) ; function dfs ( type ) { let component = [ type ] ; visited . add ( type . name ) ; for ( const nextTypeName of type . subTypes . concat ( type . superTypes ) ) { if ( ! visited . has ( nextTypeName ) ) { const superType = interfaces . find ( e => e . name === nextTypeName ) ; if ( superType ) { component = component . concat ( dfs ( superType ) ) ; } } } return component ; } for ( const type of interfaces ) { if ( ! visited . has ( type . name ) ) { connectedComponents . push ( dfs ( type ) ) ; } } } function shareAndLiftContainerTypes ( connectedComponents ) { for ( const component of connectedComponents ) { let containerTypes = [ ] ; component . forEach ( type => containerTypes = containerTypes . concat ( type . containerTypes ) ) ; for ( const type of component ) { if ( type . superTypes . length > 0 ) { type . containerTypes = [ ] ; } else { type . containerTypes = containerTypes ; } } } } function liftFields ( interfaces ) { for ( const interfaceType of interfaces ) { const subInterfaces = interfaces . filter ( e => e . superTypes . includes ( interfaceType . name ) ) ; const first = subInterfaces [ 0 ] ; if ( first ) { const removal = [ ] ; for ( const field of first . fields ) { const fieldTypeSet = new Set ( field . types ) ; if ( subInterfaces . every ( e => e . fields . some ( f => f . name === field . name && _ . isEqual ( new Set ( f . types ) , fieldTypeSet ) ) ) ) { if ( ! interfaceType . fields . some ( e => e . name === field . name ) ) { interfaceType . fields . push ( field ) ; } removal . push ( field ) ; } } for ( const remove of removal ) { for ( const subInterface of subInterfaces ) { const index = subInterface . fields . findIndex ( e => e . name === remove . name ) ; subInterface . fields . splice ( index , 1 ) ; } } } } } type TypeNode = { value : Interface ; nodes : TypeNode [ ] ; } ; param interfaces returns function sortTypes ( interfaces ) { const nodes = interfaces . sort ( ( a , b ) => a . name . localeCompare ( b . name ) ) . map ( e => < TypeNode > { value : e , nodes : [ ] } ) ; for ( const node of nodes ) { node . nodes = nodes . filter ( e => node . value . superTypes . includes ( e . value . name ) ) ; } const l = [ ] ; const s = nodes . filter ( e => e . nodes . length === 0 ) ; while ( s . length > 0 ) { const n = s . shift ( ) ! ; if ( ! l . includes ( n ) ) { l . push ( n ) ; for ( const m of nodes . filter ( e => e . nodes . includes ( n ) ) ) { s . push ( m ) ; } } } return l . map ( e => e . value ) ; }