Implement pop(), popitem() and setdefault() for dict

--
MOS_MIGRATED_REVID=114966513

4 files changed, 207 insertions, 5 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
index 52231c9a92..44cbdb956a 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
@@ -1342,7 +1342,8 @@ public class MethodLibrary {
     returnType = Object.class,
     doc =
         "Removes the item at the given position in the list, and returns it. "
-            + "If no index is specified, it removes and returns the last item in the list.",
+            + "If no <code>index</code> is specified, "
+            + "it removes and returns the last item in the list.",
     mandatoryPositionals = {
       @Param(name = "self", type = MutableList.class, doc = "This list."),
     },
@@ -1370,11 +1371,138 @@ public class MethodLibrary {
         }
       };
 
+  @SkylarkSignature(
+    name = "pop",
+    objectType = SkylarkDict.class,
+    returnType = Object.class,
+    doc =
+        "Removes a <code>key</code> from the dict, and returns the associated value. "
+            + "If entry with that key was found, return the specified <code>default</code> value;"
+            + "if no default value was specified, fail instead.",
+    mandatoryPositionals = {
+      @Param(name = "self", type = SkylarkDict.class, doc = "This dict."),
+      @Param(name = "key", type = Object.class, doc = "The key."),
+    },
+    optionalPositionals = {
+      @Param(name = "default", type = Object.class, defaultValue = "unbound",
+          doc = "a default value if the key is absent."),
+    },
+    useLocation = true,
+    useEnvironment = true
+  )
+  private static BuiltinFunction dictPop =
+      new BuiltinFunction("pop") {
+        public Object invoke(SkylarkDict<Object, Object> self, Object key, Object defaultValue,
+            Location loc, Environment env)
+            throws EvalException {
+          Object value = self.get(key);
+          if (value != null) {
+            self.remove(key, loc, env);
+            return value;
+          }
+          if (defaultValue != Runtime.UNBOUND) {
+            return defaultValue;
+          }
+          throw new EvalException(loc, Printer.format("KeyError: %r", key));
+        }
+      };
+
+  @SkylarkSignature(
+    name = "popitem",
+    objectType = SkylarkDict.class,
+    returnType = Tuple.class,
+    doc =
+        "Remove and return an arbitrary <code>(key, value)</code> pair from the dictionary. "
+            + "<code>popitem()</code> is useful to destructively iterate over a dictionary, "
+            + "as often used in set algorithms. "
+            + "If the dictionary is empty, calling <code>popitem()</code> fails. "
+            + "Note that in Skylark, as opposed to Python, "
+            + "the dictionary keys are actually sorted, "
+            + "and it is deterministic which pair will returned: that with the first key, "
+            + "according to the builtin total order. "
+            + "Thus if keys are numbers, the smallest key is returned first; "
+            + "if they are lists or strings, they are compared lexicographically, etc.",
+    mandatoryPositionals = {
+      @Param(name = "self", type = SkylarkDict.class, doc = "This dict.")
+    },
+    useLocation = true,
+    useEnvironment = true
+  )
+  private static BuiltinFunction dictPopItem =
+      new BuiltinFunction("popitem") {
+        public Tuple<Object> invoke(SkylarkDict<Object, Object> self,
+            Location loc, Environment env)
+            throws EvalException {
+          if (self.isEmpty()) {
+            throw new EvalException(loc, "popitem(): dictionary is empty");
+          }
+          Object key = self.firstKey();
+          Object value = self.get(key);
+          self.remove(key, loc, env);
+          return Tuple.<Object>of(key, value);
+        }
+      };
+
+  @SkylarkSignature(
+    name = "clear",
+    objectType = SkylarkDict.class,
+    returnType = Runtime.NoneType.class,
+    doc = "Remove all items from the dictionary.",
+    mandatoryPositionals = {
+      @Param(name = "self", type = SkylarkDict.class, doc = "This dict.")
+    },
+    useLocation = true,
+    useEnvironment = true
+  )
+  private static BuiltinFunction dictClear =
+      new BuiltinFunction("clear") {
+        public Runtime.NoneType invoke(SkylarkDict<Object, Object> self,
+            Location loc, Environment env)
+            throws EvalException {
+          self.clear(loc, env);
+          return Runtime.NONE;
+        }
+      };
+
+  @SkylarkSignature(
+    name = "setdefault",
+    objectType = SkylarkDict.class,
+    returnType = Object.class,
+    doc =
+        "If <code>key</code> is in the dictionary, return its value. "
+            + "If not, insert key with a value of <code>default</code> "
+            + "and return <code>default</code>. "
+            + "<code>default</code> defaults to <code>None</code>.",
+    mandatoryPositionals = {
+      @Param(name = "self", type = SkylarkDict.class, doc = "This dict."),
+      @Param(name = "key", type = Object.class, doc = "The key."),
+    },
+    optionalPositionals = {
+      @Param(name = "default", type = Object.class, defaultValue = "None",
+          doc = "a default value if the key is absent."),
+    },
+    useLocation = true,
+    useEnvironment = true
+  )
+  private static BuiltinFunction dictSetDefault =
+      new BuiltinFunction("setdefault") {
+        public Object invoke(SkylarkDict<Object, Object> self, Object key, Object defaultValue,
+            Location loc, Environment env)
+            throws EvalException {
+          Object value = self.get(key);
+          if (value != null) {
+            return value;
+          }
+          self.put(key, defaultValue, loc, env);
+          return defaultValue;
+        }
+      };
+
   // dictionary access operator
   @SkylarkSignature(name = "$index", documented = false, objectType = SkylarkDict.class,
       doc = "Looks up a value in a dictionary.",
       mandatoryPositionals = {
-        @Param(name = "self", type = SkylarkDict.class, doc = "This object."),
+        @Param(name = "self", type = SkylarkDict.class, doc = "This dict."),
         @Param(name = "key", type = Object.class, doc = "The index or key to access.")},
       useLocation = true, useEnvironment = true)
   private static BuiltinFunction dictIndexOperator = new BuiltinFunction("$index") {
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java b/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
index f4b55ad4c4..2795da10c2 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
@@ -69,6 +69,31 @@ public final class Runtime {
     }
   }
 
+  /** Marker for unbound variables in cases where neither Java null nor Skylark None is suitable. */
+  @Immutable
+  public static final class UnboundMarker implements SkylarkValue {
+    private UnboundMarker() {}
+
+    @Override
+    public String toString() {
+      return "<unbound>";
+    }
+
+    @Override
+    public boolean isImmutable() {
+      return true;
+    }
+
+    @Override
+    public void write(Appendable buffer, char quotationMark) {
+      Printer.append(buffer, "<unbound>");
+    }
+  }
+
+  @SkylarkSignature(name = "<unbound>", returnType = UnboundMarker.class, documented = false,
+      doc = "Marker for unbound values in cases where neither Skylark None nor Java null can do.")
+  public static final UnboundMarker UNBOUND = new UnboundMarker();
+
   /**
    * Load {@link #NONE} on the stack.
    * <p>Kept close to the definition to avoid reflection errors when changing it.
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java
index 3c8db4ee1c..8cb1926bb5 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java
@@ -94,7 +94,7 @@ public final class SkylarkDict<K, V>
   }
 
   /**
-   * The underlying contents is a (usually) mutable data structure.
+   * @return The underlying contents is a (usually) mutable data structure.
    * Read access is forwarded to these contents.
    * This object must not be modified outside an {@link Environment}
    * with a correct matching {@link Mutability},
@@ -106,16 +106,64 @@ public final class SkylarkDict<K, V>
     return contents;
   }
 
+  /**
+   * Put an entry into a SkylarkDict.
+   * @param k the key
+   * @param v the associated value
+   * @param loc a {@link Location} in case of error
+   * @param env an {@link Environment}, to check Mutability
+   * @throws EvalException if the key is invalid
+   */
   public void put(K k, V v, Location loc, Environment env) throws EvalException {
     checkMutable(loc, env);
     EvalUtils.checkValidDictKey(k);
     contents.put(k, v);
   }
 
-  public void putAll(Map<? extends K, ? extends V> m, Location loc, Environment env)
+  /**
+   * Put all the entries from a given dict into the SkylarkDict.
+   * @param m the map to copy
+   * @param loc a {@link Location} in case of error
+   * @param env an {@link Environment}, to check Mutability
+   * @throws EvalException if some key is invalid
+   */
+  public <KK extends K, VV extends V> void putAll(Map<KK, VV> m, Location loc, Environment env)
       throws EvalException {
     checkMutable(loc, env);
-    putAllUnsafe(m);
+    for (Map.Entry<KK, VV> e : m.entrySet()) {
+      KK k = e.getKey();
+      EvalUtils.checkValidDictKey(k);
+      contents.put(k, e.getValue());
+    }
+  }
+
+  /** @return the first key in the dict */
+  K firstKey() {
+    return contents.firstKey();
+  }
+
+  /**
+   * Delete the entry associated to a key.
+   * @param key the key to delete
+   * @param loc a {@link Location} in case of error
+   * @param env an {@link Environment}, to check Mutability
+   * @return the value associated to the key, or {@code null} if not present
+   * @throws EvalException if the dict is frozen.
+   */
+  V remove(Object key, Location loc, Environment env) throws EvalException {
+    checkMutable(loc, env);
+    return contents.remove(key);
+  }
+
+  /**
+   * Clear the dict.
+   * @param loc a {@link Location} in case of error
+   * @param env an {@link Environment}, to check Mutability
+   * @throws EvalException if the dict is frozen.
+   */
+  void clear(Location loc, Environment env) throws EvalException {
+    checkMutable(loc, env);
+    contents.clear();
   }
 
   // Other methods
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
index c27da119ed..1348267540 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
@@ -189,6 +189,7 @@ public class SkylarkSignatureProcessor {
             .setGlobals(Environment.CONSTANTS_ONLY)
             .setEventHandler(Environment.FAIL_FAST_HANDLER)
             .build()
+            .update("unbound", Runtime.UNBOUND)
             .eval(param.defaultValue());
       } catch (Exception e) {
         throw new RuntimeException(String.format(