import { setUnionInto , setFilter , iterableFirst , setSubtract , setIntersect } from "collection-utils" ; import { TypeGraph } from "./TypeGraph" ; import { Type } from "./Type" ; import { panic , defined , assert } from "./support/Support" ; import { Graph } from "./Graph" ; import { messageError } from "./Messages" ; export type DeclarationKind = "forward" | "define" ; export interface Declaration { readonly kind : DeclarationKind ; readonly type : Type ; } export class DeclarationIR { readonly declarations : ReadonlyArray < Declaration > ; constructor ( declarations , readonly forwardedTypes ) { this . declarations = Array . from ( declarations ) ; } } function findBreaker ( t , path , canBreak ) { const index = path . indexOf ( t ) ; if ( index < 0 ) return undefined ; if ( canBreak === undefined ) { return path [ index ] ; } const potentialBreakers = path . slice ( 0 , index + 1 ) . reverse ( ) ; const maybeBreaker = potentialBreakers . find ( canBreak ) ; if ( maybeBreaker === undefined ) { return panic ( "Found a cycle that cannot be broken" ) ; } return maybeBreaker ; } export function cycleBreakerTypesForGraph ( graph , isImplicitCycleBreaker , canBreakCycles ) { const visitedTypes = new Set < Type > ( ) ; const cycleBreakerTypes = new Set < Type > ( ) ; const queue = Array . from ( graph . topLevels . values ( ) ) ; function visit ( t , path ) { if ( visitedTypes . has ( t ) ) return ; if ( isImplicitCycleBreaker ( t ) ) { for ( const c of t . getChildren ( ) ) { queue . push ( c ) ; } } else { const maybeBreaker = findBreaker ( t , path , canBreakCycles ) ; if ( maybeBreaker !== undefined ) { cycleBreakerTypes . add ( maybeBreaker ) ; return ; } for ( const c of t . getChildren ( ) ) { path . unshift ( t ) ; visit ( c , path ) ; path . shift ( ) ; } } visitedTypes . add ( t ) ; } for ( ; ; ) { const maybeType = queue . pop ( ) ; if ( maybeType === undefined ) break ; const path = [ ] ; visit ( maybeType , path ) ; assert ( path . length === 0 ) ; } return cycleBreakerTypes ; } export function declarationsForGraph ( typeGraph , canBeForwardDeclared , childrenOfType , needsDeclaration ) { const topDown = canBeForwardDeclared === undefined ; const declarations = [ ] ; const forwardedTypes = new Set < Type > ( ) ; const visitedComponents = new Set < ReadonlySet < Type > > ( ) ; function processGraph ( graph , _writeComponents ) { const componentsGraph = graph . stronglyConnectedComponents ( ) ; function visitComponent ( component ) { if ( visitedComponents . has ( component ) ) return ; visitedComponents . add ( component ) ; const declarationNeeded = setFilter ( component , needsDeclaration ) ; if ( declarationNeeded . size === 1 ) { declarations . push ( { kind : "define" , type : defined ( iterableFirst ( declarationNeeded ) ) } ) ; return ; } if ( declarationNeeded . size === 0 && component . size === 1 ) { return ; } if ( declarationNeeded . size === 0 ) { declarations . push ( { kind : "define" , type : defined ( iterableFirst ( component ) ) } ) ; return ; } if ( canBeForwardDeclared === undefined ) { for ( const t of declarationNeeded ) { declarations . push ( { kind : "define" , type : t } ) ; } return ; } const forwardDeclarable = setFilter ( component , canBeForwardDeclared ) ; if ( forwardDeclarable . size === 0 ) { return messageError ( "IRNoForwardDeclarableTypeInCycle" , { } ) ; } for ( const t of forwardDeclarable ) { declarations . push ( { kind : "forward" , type : t } ) ; } setUnionInto ( forwardedTypes , forwardDeclarable ) ; const rest = setSubtract ( component , forwardDeclarable ) ; const restGraph = new Graph ( rest , true , t => setIntersect ( childrenOfType ( t ) , rest ) ) ; processGraph ( restGraph , false ) ; for ( const t of forwardDeclarable ) { declarations . push ( { kind : "define" , type : t } ) ; } return ; } const rootsUnordered = componentsGraph . findRoots ( ) ; const roots = rootsUnordered ; for ( const component of roots ) { componentsGraph . dfsTraversal ( component , topDown , visitComponent ) ; } } const fullGraph = typeGraph . makeGraph ( false , childrenOfType ) ; processGraph ( fullGraph , true ) ; return new DeclarationIR ( declarations , forwardedTypes ) ; }