@@ -3,6 +3,52 @@ import { LayerNode } from "./layer-node"
33
44type AnyNode = LayerNode . Node < unknown , unknown , any >
55type RuntimeLayer = Layer . Layer < never , unknown , unknown >
6+ type Visit < Result > = ( node : AnyNode , context : VisitContext < Result > ) => Result
7+
8+ type VisitContext < Result > = {
9+ readonly cache : Map < AnyNode , Result >
10+ readonly visit : ( node : AnyNode ) => Result
11+ }
12+
13+ function walk < Result > (
14+ root : AnyNode ,
15+ visit : Visit < Result > ,
16+ options : {
17+ readonly cache ?: Map < AnyNode , Result >
18+ readonly resolve ?: ( node : AnyNode ) => AnyNode
19+ readonly detectCycles ?: boolean
20+ } = { } ,
21+ ) {
22+ const cache = options . cache ?? new Map < AnyNode , Result > ( )
23+ const visiting = new Set < AnyNode > ( )
24+ const stack : AnyNode [ ] = [ ]
25+
26+ const recur = ( node : AnyNode ) : Result => {
27+ const target = options . resolve ?.( node ) ?? node
28+ const cached = cache . get ( target )
29+ if ( cached !== undefined || cache . has ( target ) ) return cached !
30+
31+ if ( options . detectCycles !== false && visiting . has ( target ) ) {
32+ const start = stack . indexOf ( target )
33+ throw new Error (
34+ `Cycle detected in layer tree: ${ [ ...stack . slice ( start ) , target ] . map ( ( item ) => item . name ) . join ( " -> " ) } ` ,
35+ )
36+ }
37+
38+ visiting . add ( target )
39+ stack . push ( target )
40+ try {
41+ const result = visit ( target , { cache, visit : recur } )
42+ if ( ! cache . has ( target ) ) cache . set ( target , result )
43+ return result
44+ } finally {
45+ stack . pop ( )
46+ visiting . delete ( target )
47+ }
48+ }
49+
50+ return recur ( root )
51+ }
652
753export function hoist < A , E , T extends LayerNode . Tag > (
854 root : LayerNode . Node < A , E , any > ,
@@ -11,54 +57,28 @@ export function hoist<A, E, T extends LayerNode.Tag>(
1157 readonly node : LayerNode . Node < A , E >
1258 readonly hoisted : LayerNode . Node < unknown , E >
1359} {
14- const visited = new Map < AnyNode , AnyNode > ( )
1560 const hoisted = new Map < string , AnyNode > ( )
16- const visiting = new Set < AnyNode > ( )
17- const stack : AnyNode [ ] = [ ]
1861
19- const visit = ( node : AnyNode ) : AnyNode => {
62+ const node = walk < AnyNode > ( root , ( node , context ) => {
2063 if ( node . kind === "group" ) {
21- return { ...node , dependencies : node . dependencies . map ( visit ) }
64+ return { ...node , dependencies : node . dependencies . map ( context . visit ) }
2265 }
23-
24- const existingNode = visited . get ( node )
25- if ( existingNode ) return existingNode
26-
2766 if ( node . tag === tag ) {
2867 const existing = hoisted . get ( node . name )
2968 if ( existing && existing !== node ) {
3069 throw new Error ( `Tag ${ tag } has conflicting implementations for ${ node . name } ` )
3170 }
3271 hoisted . set ( node . name , node )
33- const empty = LayerNode . group ( [ ] )
34- visited . set ( node , empty )
35- return empty
72+ return LayerNode . group ( [ ] )
3673 }
3774 if ( node . kind === "unbound" ) {
3875 return node
3976 }
40-
41- if ( visiting . has ( node ) ) {
42- const start = stack . indexOf ( node )
43- throw new Error (
44- `Cycle detected in layer tree: ${ [ ...stack . slice ( start ) , node ] . map ( ( item ) => item . name ) . join ( " -> " ) } ` ,
45- )
46- }
47- visiting . add ( node )
48- stack . push ( node )
49- try {
50- const dependencies = node . dependencies . map ( visit )
51- const clone = { ...node , dependencies }
52- visited . set ( node , clone )
53- return clone
54- } finally {
55- stack . pop ( )
56- visiting . delete ( node )
57- }
58- }
77+ return { ...node , dependencies : node . dependencies . map ( context . visit ) }
78+ } )
5979
6080 return {
61- node : visit ( root ) as LayerNode . Node < A , E > ,
81+ node : node as LayerNode . Node < A , E > ,
6282 hoisted : LayerNode . group ( Array . from ( hoisted . values ( ) ) ) as LayerNode . Node < unknown , E > ,
6383 }
6484}
@@ -68,24 +88,32 @@ export function compile<A, E>(
6888 replacements ?: ReadonlyMap < Layer . Any , Layer . Any > ,
6989) : Layer . Layer < A , E > {
7090 const cache = new Map < AnyNode , RuntimeLayer > ( )
71- const compileNode = ( node : AnyNode ) : RuntimeLayer => {
72- if ( node . kind === "unbound" ) throw new Error ( `Unbound layer node: ${ node . name } ` )
73- const cached = cache . get ( node )
74- if ( cached ) return cached
75- const dependencies = node . dependencies . flatMap ( flatten ) . map ( compileNode )
76- const implementation = ( replacements ?. get ( node . implementation ! ) ?? node . implementation ! ) as RuntimeLayer
77- const layer =
78- dependencies . length === 0
79- ? implementation
80- : implementation . pipe ( Layer . provide ( dependencies as [ RuntimeLayer , ...RuntimeLayer [ ] ] ) )
81- cache . set ( node , layer )
82- return layer
83- }
91+ const compileNode = ( node : AnyNode ) =>
92+ walk < RuntimeLayer > (
93+ node ,
94+ ( node , context ) => {
95+ if ( node . kind === "unbound" ) throw new Error ( `Unbound layer node: ${ node . name } ` )
96+ const dependencies = node . dependencies . flatMap ( flatten ) . map ( context . visit )
97+ const implementation = ( replacements ?. get ( node . implementation ! ) ?? node . implementation ! ) as RuntimeLayer
98+ return dependencies . length === 0
99+ ? implementation
100+ : implementation . pipe ( Layer . provide ( dependencies as [ RuntimeLayer , ...RuntimeLayer [ ] ] ) )
101+ } ,
102+ { cache } ,
103+ )
84104 const layers = flatten ( root ) . map ( ( node ) => compileNode ( node ) )
85105 const layer = layers . reduce < RuntimeLayer > ( ( result , layer ) => layer . pipe ( Layer . provideMerge ( result ) ) , Layer . empty )
86106 return layer as Layer . Layer < A , E >
87107}
88108
109+ export function hasUnbound ( root : LayerNode . Node < unknown , unknown , any > , source : AnyNode ) : boolean {
110+ if ( source . kind !== "unbound" ) throw new Error ( `Cannot check non-unbound layer node: ${ source . name } ` )
111+ return walk < boolean > ( root , ( node , context ) => {
112+ if ( node === source ) return true
113+ return node . dependencies . some ( context . visit )
114+ } )
115+ }
116+
89117export function bind < A , E , T extends LayerNode . Tag | undefined > (
90118 root : LayerNode . Node < A , E , T > ,
91119 source : AnyNode ,
@@ -98,17 +126,18 @@ export function bind<A, E, T extends LayerNode.Tag | undefined>(
98126 if ( source . tag !== replacement . tag ) {
99127 throw new Error ( `Cannot bind ${ source . name } across tags` )
100128 }
101- const visited = new Map < AnyNode , AnyNode > ( )
102- const visit = ( node : AnyNode ) : AnyNode => {
103- if ( node === source ) return replacement
104- const existing = visited . get ( node )
105- if ( existing ) return existing
106- if ( node . kind === "unbound" ) return node
107- const clone = { ...node , dependencies : node . dependencies . map ( visit ) }
108- visited . set ( node , clone )
109- return clone
110- }
111- return visit ( root ) as LayerNode . Node < A , E , T >
129+ return walk < AnyNode > (
130+ root ,
131+ ( target , context ) => {
132+ if ( target . kind === "unbound" ) return target
133+ const dependencies : AnyNode [ ] = [ ]
134+ const clone = { ...target , dependencies }
135+ context . cache . set ( target , clone )
136+ dependencies . push ( ...target . dependencies . map ( context . visit ) )
137+ return clone
138+ } ,
139+ { detectCycles : false , resolve : ( node ) => ( node === source ? replacement : node ) } ,
140+ ) as LayerNode . Node < A , E , T >
112141}
113142
114143function flatten ( node : AnyNode ) : readonly AnyNode [ ] {
0 commit comments