[FIX JENKINS-20280] Calculates the order to override variables. This …

…is an improved fix for [JENKINS-19488] and [JENKINS-19926].
jenkinsci · Oct 26, 2013 · 4204d22 · 4204d22
1 parent f98c462
commit 4204d22
Show file tree

Hide file tree

Showing 3 changed files with 331 additions and 6 deletions.
diff --git a/core/src/main/java/hudson/EnvVars.java b/core/src/main/java/hudson/EnvVars.java
@@ -26,12 +26,20 @@
 import hudson.remoting.Callable;
 import hudson.remoting.VirtualChannel;
 import hudson.util.CaseInsensitiveComparator;
+import hudson.util.VariableResolver;
 
 import java.io.File;
 import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
 import java.util.Map;
+import java.util.Set;
 import java.util.TreeMap;
 import java.util.Arrays;
+import java.util.TreeSet;
 import java.util.UUID;
 
 /**
@@ -148,6 +156,220 @@ public EnvVars overrideAll(Map<String,String> all) {
         return this;
     }
 
+    /**
+     * Calculates the order to override variables.
+     * 
+     * We should override variables in a following order:
+     * <ol>
+     *   <li>variables that does not contain variable expressions.</li>
+     *   <li>variables that refers variables overridden in 1.</li>
+     *   <li>variables that refers variables overridden in 2.</li>
+     *   <li>...</li>
+     *   <li>(last) variables contains '+' (as PATH+MAVEN)</li>
+     * </ol>
+     * 
+     * This class orders variables in a following way:
+     * <ol>
+     *   <li>scan each overriding variables and list all referred variables (includes indirect references).</li>
+     *   <li>sort variables with a number of referring variables (ascending order).</li>
+     * </ol>
+     */
+    public static class OverrideOrderCalculator {
+        /**
+         * Extract variables referred directly from a variable.
+         */
+        private static class TraceResolver implements VariableResolver<String> {
+            private final Comparator<? super String> comparator;
+            public Set<String> referredVariables;
+
+            public TraceResolver(Comparator<? super String> comparator) {
+                this.comparator = comparator;
+                clear();
+            }
+
+            public void clear() {
+                referredVariables = new TreeSet<String>(comparator);
+            }
+
+            public String resolve(String name) {
+                referredVariables.add(name);
+                return "";
+            }
+        }
+
+        private final Comparator<? super String> comparator;
+
+        private final Map<String,String> overrides;
+        /**
+         * set of variables that a variable is REFERRING.
+         * When A=${B}, refereeSetMap.get("A").contains("B").
+         * Also contains indirect references, when A=${B}, B=${C},
+         * refereeSetMap.get("A").contains("C").
+         */
+        private Map<String, Set<String>> refereeSetMap;
+
+        /**
+         * set of variables that a variable is REFERRED BY.
+         * When A=${B}, referrerSetMap.get("B").contains("A").
+         * Also contains indirect references, when A=${B}, B=${C},
+         * referrerSetMap.get("C").contains("A").
+         */
+        private Map<String, Set<String>> referrerSetMap;
+
+        public OverrideOrderCalculator(EnvVars target, Map<String,String> overrides) {
+            comparator = target.comparator();
+            this.overrides = overrides;
+            refereeSetMap = new TreeMap<String, Set<String>>(comparator);
+            referrerSetMap = new TreeMap<String, Set<String>>(comparator);
+            scan();
+        }
+
+        /**
+         * Return an iterator for keys of overriding variables.
+         * 
+         * Scan variables in this order.
+         * This is only provided for testing purpose to control scanning order.
+         * 
+         * @return an iterator for keys of overriding variables
+         */
+        protected Iterator<String> rawKeyIterator() {
+            return overrides.keySet().iterator();
+        }
+
+        public Set<String> getRefereeSet(String variable) {
+            return refereeSetMap.get(variable);
+        }
+
+        public int getRefereeNum(String variable) {
+            if (refereeSetMap.containsKey(variable)) {
+                return refereeSetMap.get(variable).size();
+            }
+            return 0;
+        }
+
+        public List<Map.Entry<String,String>> getOrderedVariables() {
+            List<Map.Entry<String,String>> varList = new ArrayList<Map.Entry<String,String>>(overrides.entrySet());
+            Collections.sort(varList, new Comparator<Map.Entry<String,String>>() {
+                @Override
+                public int compare(Map.Entry<String, String> o1, Map.Entry<String, String> o2) {
+                    String key1 = o1.getKey();
+                    String key2 = o2.getKey();
+                    if (key1.indexOf('+') > -1) {
+                        if (key2.indexOf('+') > -1) {
+                            // ABC+FOO == XYZ+BAR
+                            return 0;
+                        }
+                        // ABC+FOO > BAR
+                        return 1;
+                    }
+
+                    if (key2.indexOf('+') > -1) {
+                        // FOO < ABC+BAR
+                        return -1;
+                    }
+
+                    // depends on the number of variables each variable refers.
+                    return getRefereeNum(key1) - getRefereeNum(key2);
+                }
+            });
+            return varList;
+        }
+
+        /**
+         * Scan all variables and list all referring variables.
+         */
+        public void scan() {
+            TraceResolver resolver = new TraceResolver(comparator);
+
+            Iterator<String> referrerIterator  = rawKeyIterator();
+            while (referrerIterator.hasNext()) {
+                String currentVar = referrerIterator.next();
+                if (currentVar.indexOf('+') > 0) {
+                    // XYZ+AAA variables should be always processed in last.
+                    continue;
+                }
+                resolver.clear();
+                Util.replaceMacro(overrides.get(currentVar), resolver);
+
+                // Variables directly referred from the current scanning variable.
+                Set<String> refereeSet = resolver.referredVariables;
+
+                if (refereeSet.isEmpty()) {
+                    // nothing to do if this variables does not refer other variables.
+                    continue;
+                }
+
+                // Find indirect referred variables:
+                //   A=${B}
+                //   CurrentVar=${A}
+                //   -> CurrentVar refers B.
+                Set<String> indirectRefereeSet = new TreeSet<String>(comparator);
+                for (String referee: refereeSet) {
+                    if (refereeSetMap.containsKey(referee)) {
+                        indirectRefereeSet.addAll(refereeSetMap.get(referee));
+                    }
+                }
+
+                // now contains variables referred both directly and indirectly.
+                refereeSet.addAll(indirectRefereeSet);
+
+                // Variables refers the current scanning variable.
+                // this contains both direct and indirect reference.
+                Set<String> referrerSet = referrerSetMap.get(currentVar);
+
+                // what I have to do:
+                // 1. Create a link between the current scanning variable and referred variables.
+                //     1-a. register the current variable as a referrer of referred variables.
+                //     1-b. register referred variables as a referee of the current variable.
+                // 2. Create links between referring variables and referred variables.
+                //     2-a. register referring variables as referrers of referred variables.
+                //     2-b. register referred variables as referees of referring variables.
+                // 
+                // Links between referring variables and the current scanning variable
+                // is already created from referring variables.
+                for (String referee: refereeSet) {
+                    if (!referrerSetMap.containsKey(referee)) {
+                        referrerSetMap.put(referee, new TreeSet<String>(comparator));
+                    }
+                    // 1-a. register the current variable as a referrer of referred variables.
+                    referrerSetMap.get(referee).add(currentVar);
+                    // 2-b. register referred variables as referees of referring variables.
+                    if (referrerSet != null) {
+                        referrerSetMap.get(referee).addAll(referrerSet);
+                    }
+                }
+
+                if (!refereeSetMap.containsKey(currentVar)) {
+                    refereeSetMap.put(currentVar, new TreeSet<String>(comparator));
+                }
+                // 1-b. register referred variables as a referee of the current variable.
+                refereeSetMap.get(currentVar).addAll(refereeSet);
+
+                if (referrerSet != null) {
+                    for (String referer: referrerSet) {
+                        // 2-b. register referred variables as referees of referring variables.
+                        // For referrer refers the current scanning variable,
+                        // refereeSetMap.get(referer) always exists.
+                        refereeSetMap.get(referer).addAll(refereeSet);
+                    }
+                }
+            }
+        }
+    }
+
+
+    /**
+     * Overrides all values in the map by the given map. Expressions in values will be expanded.
+     * See {@link #override(String, String)}.
+     * @return this
+     */
+    public EnvVars overrideExpandingAll(Map<String,String> all) {
+        for (Map.Entry<String, String> e : new OverrideOrderCalculator(this, all).getOrderedVariables()) {
+            override(e.getKey(), expand(e.getValue()));
+        }
+        return this;
+    }
+
     /**
      * Resolves environment variables against each other.
      */

diff --git a/core/src/main/java/hudson/Launcher.java b/core/src/main/java/hudson/Launcher.java
@@ -1087,12 +1087,7 @@ private static EnvVars inherit(String[] env) {
      */
     private static EnvVars inherit(Map<String,String> overrides) {
         EnvVars m = new EnvVars(EnvVars.masterEnvVars);
-        // first add all new values and then eventually expand them as values can refer other newly added values (see JENKINS-19488)
-        for (Map.Entry<String,String> o : overrides.entrySet())
-            if(m.get(o.getKey()) == null)
-                m.put(o.getKey(), o.getValue());
-        for (Map.Entry<String,String> o : overrides.entrySet()) 
-            m.override(o.getKey(),m.expand(o.getValue()));
+        m.overrideExpandingAll(overrides);
         return m;
     }
 

diff --git a/core/src/test/java/hudson/EnvVarsTest.java b/core/src/test/java/hudson/EnvVarsTest.java
@@ -23,9 +23,14 @@
  */
 package hudson;
 
+import hudson.EnvVars.OverrideOrderCalculator;
 import junit.framework.TestCase;
 
+import java.util.Arrays;
 import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
 
 /**
  * @author Kohsuke Kawaguchi
@@ -39,4 +44,107 @@ public void test1() {
         assertTrue(ev.containsKey("PATH"));
         assertEquals("A:B:C",ev.get("PATH"));
     }
+
+    public void testOverrideExpandingAll() throws Exception {
+        EnvVars env = new EnvVars();
+        env.put("PATH", "orig");
+        env.put("A", "Value1");
+
+        EnvVars overrides = new EnvVars();
+        overrides.put("PATH", "append" + Platform.current().pathSeparator + "${PATH}");
+        overrides.put("B", "${A}Value2");
+        overrides.put("C", "${B}${D}");
+        overrides.put("D", "${E}");
+        overrides.put("E", "Value3");
+        overrides.put("PATH+TEST", "another");
+
+        env.overrideExpandingAll(overrides);
+
+        assertEquals("Value1Value2Value3", env.get("C"));
+        assertEquals("another" + Platform.current().pathSeparator + "append" + Platform.current().pathSeparator + "orig", env.get("PATH"));
+    }
+
+    public void testOverrideOrderCalculatorSimple() {
+        EnvVars env = new EnvVars();
+        EnvVars overrides = new EnvVars();
+        overrides.put("A", "NoReference");
+        overrides.put("A+B", "NoReference");
+        overrides.put("B", "Refer1${A}");
+        overrides.put("C", "Refer2${B}");
+        overrides.put("D", "Refer3${B}${Nosuch}");
+
+        OverrideOrderCalculator calc = new OverrideOrderCalculator(env, overrides);
+        assertEquals(0, calc.getRefereeNum("A"));
+        assertEquals(0, calc.getRefereeNum("A+B"));
+        assertEquals(0, calc.getRefereeNum("Nosuch"));
+        assertEquals(1, calc.getRefereeNum("B"));
+        assertEquals(2, calc.getRefereeNum("C"));
+        assertEquals(3, calc.getRefereeNum("D"));
+
+        List<Map.Entry<String,String>> order = calc.getOrderedVariables();
+        assertEquals(5, order.size());
+        assertEquals("A", order.get(0).getKey());
+        assertEquals("B", order.get(1).getKey());
+        assertEquals("C", order.get(2).getKey());
+        assertEquals("D", order.get(3).getKey());
+        assertEquals("A+B", order.get(4).getKey());
+    }
+
+    public void testOverrideOrderCalculatorInOrder() {
+        EnvVars env = new EnvVars();
+        EnvVars overrides = new EnvVars();
+        overrides.put("A", "NoReference");
+        overrides.put("B", "${A}");
+        overrides.put("C", "${B}"); // refers A, B
+        overrides.put("D", "${E}"); // refers A, B, C, E
+        overrides.put("E", "${C}"); // refers A, B, C
+
+        OverrideOrderCalculator calc = new OverrideOrderCalculator(env, overrides) {
+            @Override
+            protected Iterator<String> rawKeyIterator() {
+                // should process in this order.
+                return Arrays.asList("A", "B", "C", "D", "E", "F").iterator();
+            }
+        };
+        assertEquals(0, calc.getRefereeNum("A"));
+        assertEquals(1, calc.getRefereeNum("B"));
+        assertEquals(2, calc.getRefereeNum("C"));
+        assertEquals(4, calc.getRefereeNum("D"));
+        assertEquals(3, calc.getRefereeNum("E"));
+    }
+
+    public void testOverrideOrderCalculatorMultiple() {
+        EnvVars env = new EnvVars();
+        EnvVars overrides = new EnvVars();
+        overrides.put("A", "Noreference");
+        overrides.put("B", "${A}");
+        overrides.put("C", "${A}${B}");
+
+        OverrideOrderCalculator calc = new OverrideOrderCalculator(env, overrides);
+        assertEquals(0, calc.getRefereeNum("A"));
+        assertEquals(1, calc.getRefereeNum("B"));
+        assertEquals(2, calc.getRefereeNum("C"));
+    }
+
+    public void testOverrideOrderCalculatorSelfReference() {
+        EnvVars env = new EnvVars();
+        EnvVars overrides = new EnvVars();
+        overrides.put("PATH", "some;${PATH}");
+
+        OverrideOrderCalculator calc = new OverrideOrderCalculator(env, overrides);
+        assertEquals(1, calc.getRefereeNum("PATH"));
+    }
+
+    public void testOverrideOrderCalculatorCyclic() {
+        EnvVars env = new EnvVars();
+        EnvVars overrides = new EnvVars();
+        overrides.put("A", "${B}");
+        overrides.put("B", "${C}");
+        overrides.put("C", "${A}");
+
+        OverrideOrderCalculator calc = new OverrideOrderCalculator(env, overrides);
+        assertEquals(3, calc.getRefereeNum("A"));
+        assertEquals(3, calc.getRefereeNum("B"));
+        assertEquals(3, calc.getRefereeNum("C"));
+    }
 }