iterative dependency solver

First, we go through every environment variable key and record all cases
where there are reference to other variables / dependencies.

We track two sets of variables - resolved and yet-to-be-resolved.
We pass over a list of variables over and over again and when all
variable's dependencies were resolved during previous passes we perform
a replacement for that variable, too.

Over time the size of `toResolve` set should go down to zero, however
circular dependencies may prevent that. We track the size of `toResolve`
between iterations to avoid infinite looping.

At the end we produce an object of the same size and shape as
the original, but with the values replace with resolved versions.

2 files changed, 88 insertions, 0 deletions

diff --git a/editors/code/src/config.ts b/editors/code/src/config.ts
index 0ce538e2e98..87cc2a395ba 100644
--- a/editors/code/src/config.ts
+++ b/editors/code/src/config.ts
@@ -209,3 +209,50 @@ export async function updateConfig(config: vscode.WorkspaceConfiguration) {
         }
     }
 }
+
+export function substituteVariablesInEnv(env: Env): Env {
+    const missingDeps = new Set<string>();
+    // vscode uses `env:ENV_NAME` for env vars resolution, and it's easier
+    // to follow the same convention for our dependency tracking
+    const definedEnvKeys = new Set(Object.keys(env).map(key => `env:${key}`));
+    const envWithDeps = Object.fromEntries(Object.entries(env).map(([key, value]) => {
+        const deps = new Set<string>();
+        const depRe = new RegExp(/\${(?<depName>.+?)}/g);
+        let match = undefined;
+        while ((match = depRe.exec(value))) {
+            const depName = match.groups!.depName;
+            deps.add(depName);
+            // `depName` at this point can have a form of `expression` or
+            // `prefix:expression`
+            if (!definedEnvKeys.has(depName)) {
+                missingDeps.add(depName);
+            }
+        }
+        return [`env:${key}`, { deps: [...deps], value }];
+    }));
+
+    const resolved = new Set<string>();
+    // TODO: handle missing dependencies
+    const toResolve = new Set(Object.keys(envWithDeps));
+
+    let leftToResolveSize;
+    do {
+        leftToResolveSize = toResolve.size;
+        for (const key of toResolve) {
+            if (envWithDeps[key].deps.every(dep => resolved.has(dep))) {
+                envWithDeps[key].value = envWithDeps[key].value.replace(
+                    /\${(?<depName>.+?)}/g, (_wholeMatch, depName) => {
+                        return envWithDeps[depName].value;
+                    });
+                resolved.add(key);
+                toResolve.delete(key);
+            }
+        }
+    } while (toResolve.size > 0 && toResolve.size < leftToResolveSize);
+
+    const resolvedEnv: Env = {};
+    for (const key of Object.keys(env)) {
+        resolvedEnv[key] = envWithDeps[`env:${key}`].value;
+    }
+    return resolvedEnv;
+}
diff --git a/editors/code/tests/unit/settings.test.ts b/editors/code/tests/unit/settings.test.ts
new file mode 100644
index 00000000000..12734d15667
--- /dev/null
+++ b/editors/code/tests/unit/settings.test.ts
@@ -0,0 +1,41 @@
+import * as assert from 'assert';
+import { Context } from '.';
+import { substituteVariablesInEnv } from '../../src/config';
+
+export async function getTests(ctx: Context) {
+    await ctx.suite('Server Env Settings', suite => {
+        suite.addTest('Replacing Env Variables', async () => {
+            const envJson = {
+                USING_MY_VAR: "${env:MY_VAR} test ${env:MY_VAR}",
+                MY_VAR: "test"
+            };
+            const expectedEnv = {
+                USING_MY_VAR: "test test test",
+                MY_VAR: "test"
+            };
+            const actualEnv = await substituteVariablesInEnv(envJson);
+            assert.deepStrictEqual(actualEnv, expectedEnv);
+        });
+
+        suite.addTest('Circular dependencies remain as is', async () => {
+            const envJson = {
+                A_USES_B: "${env:B_USES_A}",
+                B_USES_A: "${env:A_USES_B}",
+                C_USES_ITSELF: "${env:C_USES_ITSELF}",
+                D_USES_C: "${env:C_USES_ITSELF}",
+                E_IS_ISOLATED: "test",
+                F_USES_E: "${env:E_IS_ISOLATED}"
+            };
+            const expectedEnv = {
+                A_USES_B: "${env:B_USES_A}",
+                B_USES_A: "${env:A_USES_B}",
+                C_USES_ITSELF: "${env:C_USES_ITSELF}",
+                D_USES_C: "${env:C_USES_ITSELF}",
+                E_IS_ISOLATED: "test",
+                F_USES_E: "test"
+            };
+            const actualEnv = await substituteVariablesInEnv(envJson);
+            assert.deepStrictEqual(actualEnv, expectedEnv);
+        });
+    });
+}