diff --git a/src/main/java/com/android/tools/r8/graph/DexType.java b/src/main/java/com/android/tools/r8/graph/DexType.java
index c97e609..594ea9b 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -82,6 +82,14 @@
     return descriptor.toString();
   }
 
+  public String toBinaryName() {
+    String descriptor = toDescriptorString();
+    assert descriptor.length() > 1
+        && descriptor.charAt(0) == 'L'
+        && descriptor.charAt(descriptor.length() - 1) == ';';
+    return descriptor.substring(1, descriptor.length() - 1);
+  }
+
   @Override
   public String toSourceString() {
     if (toStringCache == null) {
@@ -323,4 +331,8 @@
     assert isClassType() || isArrayType();
     return DescriptorUtils.descriptorToInternalName(toDescriptorString());
   }
+
+  public String getPackageName() {
+    return DescriptorUtils.getPackageNameFromBinaryName(toBinaryName());
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
index 7c33d52..29d2028 100644
--- a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
@@ -20,6 +20,7 @@
 import com.android.tools.r8.graph.InnerClassAttribute;
 import com.android.tools.r8.naming.signature.GenericSignatureRewriter;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.ProguardPackageNameList;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.InternalOptions.PackageObfuscationMode;
@@ -34,7 +35,6 @@
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.Set;
-import java.util.stream.Collectors;
 
 class ClassNameMinifier {
 
@@ -54,8 +54,6 @@
   private final List<String> classDictionary;
   private final boolean keepInnerClassStructure;
 
-  private final Set<DexType> keepPackageName;
-
   private final Namespace topLevelState;
 
   ClassNameMinifier(
@@ -74,9 +72,6 @@
     this.packageDictionary = options.getProguardConfiguration().getPackageObfuscationDictionary();
     this.classDictionary = options.getProguardConfiguration().getClassObfuscationDictionary();
     this.keepInnerClassStructure = options.getProguardConfiguration().getKeepAttributes().signature;
-    this.keepPackageName =
-        DexReference.filterDexType(appView.rootSet().keepPackageName.stream())
-            .collect(Collectors.toSet());
 
     // Initialize top-level naming state.
     topLevelState = new Namespace(
@@ -261,8 +256,9 @@
     String packageName = getPackageBinaryNameFromJavaType(type.getPackageDescriptor());
     // Check whether the given class should be kept.
     // or check whether the given class belongs to a package that is kept for another class.
-    if (keepPackageName.contains(type)
-        || noObfuscationPrefixes.contains(packageName)) {
+    ProguardPackageNameList keepPackageNames =
+        appView.options().getProguardConfiguration().getKeepPackageNamesPatterns();
+    if (noObfuscationPrefixes.contains(packageName) || keepPackageNames.matches(type)) {
       return states.computeIfAbsent(packageName, Namespace::new);
     }
     Namespace state = topLevelState;
diff --git a/src/main/java/com/android/tools/r8/shaking/ProguardConfiguration.java b/src/main/java/com/android/tools/r8/shaking/ProguardConfiguration.java
index 894f4e8..360a11a 100644
--- a/src/main/java/com/android/tools/r8/shaking/ProguardConfiguration.java
+++ b/src/main/java/com/android/tools/r8/shaking/ProguardConfiguration.java
@@ -42,6 +42,8 @@
     private boolean verbose;
     private String renameSourceFileAttribute;
     private final List<String> keepAttributePatterns = new ArrayList<>();
+    private final ProguardPackageNameList.Builder keepPackageNamesPatterns =
+        ProguardPackageNameList.builder();
     private final ProguardClassFilter.Builder dontWarnPatterns = ProguardClassFilter.builder();
     private final ProguardClassFilter.Builder dontNotePatterns = ProguardClassFilter.builder();
     protected final Set<ProguardConfigurationRule> rules = Sets.newLinkedHashSet();
@@ -180,6 +182,10 @@
       this.rules.add(rule);
     }
 
+    public void addKeepPackageNamesPattern(boolean isNegated, ProguardPackageMatcher pattern) {
+      keepPackageNamesPatterns.addPackageName(isNegated, pattern);
+    }
+
     public void addDontWarnPattern(ProguardClassNameList pattern) {
       dontWarnPatterns.addPattern(pattern);
     }
@@ -283,42 +289,44 @@
     }
 
     public ProguardConfiguration buildRaw() {
-      ProguardConfiguration configuration = new ProguardConfiguration(
-          String.join(System.lineSeparator(), parsedConfiguration),
-          dexItemFactory,
-          injars,
-          libraryjars,
-          packageObfuscationMode,
-          packagePrefix,
-          allowAccessModification,
-          ignoreWarnings,
-          optimizing,
-          obfuscating,
-          shrinking,
-          printConfiguration,
-          printConfigurationFile,
-          printUsage,
-          printUsageFile,
-          printMapping,
-          printMappingFile,
-          applyMappingFile,
-          verbose,
-          renameSourceFileAttribute,
-          ProguardKeepAttributes.fromPatterns(keepAttributePatterns),
-          dontWarnPatterns.build(),
-          dontNotePatterns.build(),
-          rules,
-          printSeeds,
-          seedFile,
-          overloadAggressively,
-          DictionaryReader.readAllNames(obfuscationDictionary, reporter),
-          DictionaryReader.readAllNames(classObfuscationDictionary, reporter),
-          DictionaryReader.readAllNames(packageObfuscationDictionary, reporter),
-          keepParameterNames,
-          adaptClassStrings.build(),
-          adaptResourceFilenames.build(),
-          adaptResourceFileContents.build(),
-          keepDirectories.build());
+      ProguardConfiguration configuration =
+          new ProguardConfiguration(
+              String.join(System.lineSeparator(), parsedConfiguration),
+              dexItemFactory,
+              injars,
+              libraryjars,
+              packageObfuscationMode,
+              packagePrefix,
+              allowAccessModification,
+              ignoreWarnings,
+              optimizing,
+              obfuscating,
+              shrinking,
+              printConfiguration,
+              printConfigurationFile,
+              printUsage,
+              printUsageFile,
+              printMapping,
+              printMappingFile,
+              applyMappingFile,
+              verbose,
+              renameSourceFileAttribute,
+              ProguardKeepAttributes.fromPatterns(keepAttributePatterns),
+              keepPackageNamesPatterns.build(),
+              dontWarnPatterns.build(),
+              dontNotePatterns.build(),
+              rules,
+              printSeeds,
+              seedFile,
+              overloadAggressively,
+              DictionaryReader.readAllNames(obfuscationDictionary, reporter),
+              DictionaryReader.readAllNames(classObfuscationDictionary, reporter),
+              DictionaryReader.readAllNames(packageObfuscationDictionary, reporter),
+              keepParameterNames,
+              adaptClassStrings.build(),
+              adaptResourceFilenames.build(),
+              adaptResourceFileContents.build(),
+              keepDirectories.build());
 
       reporter.failIfPendingErrors();
 
@@ -370,6 +378,7 @@
   private final boolean verbose;
   private final String renameSourceFileAttribute;
   private final ProguardKeepAttributes keepAttributes;
+  private final ProguardPackageNameList keepPackageNamesPatterns;
   private final ProguardClassFilter dontWarnPatterns;
   private final ProguardClassFilter dontNotePatterns;
   protected final ImmutableList<ProguardConfigurationRule> rules;
@@ -407,6 +416,7 @@
       boolean verbose,
       String renameSourceFileAttribute,
       ProguardKeepAttributes keepAttributes,
+      ProguardPackageNameList keepPackageNamesPatterns,
       ProguardClassFilter dontWarnPatterns,
       ProguardClassFilter dontNotePatterns,
       Set<ProguardConfigurationRule> rules,
@@ -442,6 +452,7 @@
     this.verbose = verbose;
     this.renameSourceFileAttribute = renameSourceFileAttribute;
     this.keepAttributes = keepAttributes;
+    this.keepPackageNamesPatterns = keepPackageNamesPatterns;
     this.dontWarnPatterns = dontWarnPatterns;
     this.dontNotePatterns = dontNotePatterns;
     this.rules = ImmutableList.copyOf(rules);
@@ -554,6 +565,10 @@
     return keepAttributes;
   }
 
+  public ProguardPackageNameList getKeepPackageNamesPatterns() {
+    return keepPackageNamesPatterns;
+  }
+
   public ProguardClassFilter getDontWarnPatterns() {
     return dontWarnPatterns;
   }
diff --git a/src/main/java/com/android/tools/r8/shaking/ProguardConfigurationParser.java b/src/main/java/com/android/tools/r8/shaking/ProguardConfigurationParser.java
index 3857aca..f58990f 100644
--- a/src/main/java/com/android/tools/r8/shaking/ProguardConfigurationParser.java
+++ b/src/main/java/com/android/tools/r8/shaking/ProguardConfigurationParser.java
@@ -38,6 +38,7 @@
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.List;
+import java.util.function.BiConsumer;
 import java.util.function.Consumer;
 import java.util.function.Predicate;
 
@@ -172,6 +173,7 @@
   }
 
   private enum IdentifierType {
+    PACKAGE_NAME,
     CLASS_NAME,
     ANY
   }
@@ -225,8 +227,7 @@
       } else if (acceptString("keepattributes")) {
         parseKeepAttributes();
       } else if (acceptString("keeppackagenames")) {
-        ProguardKeepPackageNamesRule rule = parseKeepPackageNamesRule(optionStart);
-        configurationBuilder.addRule(rule);
+        parsePackageFilter(configurationBuilder::addKeepPackageNamesPattern);
       } else if (acceptString("keepparameternames")) {
         configurationBuilder.setKeepParameterNames(true, origin, getPosition(optionStart));
       } else if (acceptString("checkdiscard")) {
@@ -608,17 +609,6 @@
       return keepRuleBuilder.build();
     }
 
-    private ProguardKeepPackageNamesRule parseKeepPackageNamesRule(Position start)
-        throws ProguardRuleParserException {
-      ProguardKeepPackageNamesRule.Builder keepRuleBuilder =
-          ProguardKeepPackageNamesRule.builder().setOrigin(origin).setStart(start);
-      keepRuleBuilder.setClassNames(parseClassNames());
-      Position end = getPosition();
-      keepRuleBuilder.setSource(getSourceSnippet(contents, start, end));
-      keepRuleBuilder.setEnd(end);
-      return keepRuleBuilder.build();
-    }
-
     private ProguardCheckDiscardRule parseCheckDiscardRule(Position start)
         throws ProguardRuleParserException {
       ProguardCheckDiscardRule.Builder keepRuleBuilder = ProguardCheckDiscardRule.builder()
@@ -1461,6 +1451,13 @@
                 || codePoint == '['
                 || codePoint == ']';
 
+    private final Predicate<Integer> PACKAGE_NAME_PREDICATE =
+        codePoint ->
+            IdentifierUtils.isDexIdentifierPart(codePoint)
+                || codePoint == '.'
+                || codePoint == '*'
+                || codePoint == '?';
+
     private String acceptClassName() {
       return acceptString(CLASS_NAME_PREDICATE);
     }
@@ -1559,9 +1556,11 @@
         } else if (current == '?' || current == '%') {
           wildcardsCollector.add(new ProguardWildcard.Pattern(String.valueOf((char) current)));
           end += Character.charCount(current);
-        } else if (CLASS_NAME_PREDICATE.test(current) || current == '>') {
+        } else if (kind == IdentifierType.PACKAGE_NAME
+            ? PACKAGE_NAME_PREDICATE.test(current)
+            : (CLASS_NAME_PREDICATE.test(current) || current == '>')) {
           end += Character.charCount(current);
-        } else if (current == '<') {
+        } else if (kind != IdentifierType.PACKAGE_NAME && current == '<') {
           currentBackreference = new StringBuilder();
           end += Character.charCount(current);
         } else {
@@ -1671,6 +1670,25 @@
       }
     }
 
+    private void parsePackageFilter(BiConsumer<Boolean, ProguardPackageMatcher> consumer)
+        throws ProguardRuleParserException {
+      skipWhitespace();
+      if (isOptionalArgumentGiven()) {
+        do {
+          IdentifierPatternWithWildcardsAndNegation name =
+              acceptIdentifierWithBackreference(IdentifierType.PACKAGE_NAME, true);
+          if (name == null) {
+            throw parseError("Package name expected");
+          }
+          consumer.accept(
+              name.negated, new ProguardPackageMatcher(name.patternWithWildcards.pattern));
+          skipWhitespace();
+        } while (acceptChar(','));
+      } else {
+        consumer.accept(false, new ProguardPackageMatcher("**"));
+      }
+    }
+
     private void parseClassFilter(Consumer<ProguardClassNameList> consumer)
         throws ProguardRuleParserException {
       skipWhitespace();
diff --git a/src/main/java/com/android/tools/r8/shaking/ProguardKeepPackageNamesRule.java b/src/main/java/com/android/tools/r8/shaking/ProguardKeepPackageNamesRule.java
deleted file mode 100644
index 767ecf7..0000000
--- a/src/main/java/com/android/tools/r8/shaking/ProguardKeepPackageNamesRule.java
+++ /dev/null
@@ -1,59 +0,0 @@
-// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-package com.android.tools.r8.shaking;
-
-import com.android.tools.r8.origin.Origin;
-import com.android.tools.r8.position.Position;
-import java.util.List;
-
-public class ProguardKeepPackageNamesRule extends ProguardConfigurationRule {
-
-  public static class Builder
-      extends ProguardConfigurationRule.Builder<ProguardKeepPackageNamesRule, Builder> {
-
-    private Builder() {
-      super();
-    }
-
-    @Override
-    public Builder self() {
-      return this;
-    }
-
-    @Override
-    public ProguardKeepPackageNamesRule build() {
-      return new ProguardKeepPackageNamesRule(origin, getPosition(), source, classAnnotation,
-          classAccessFlags, negatedClassAccessFlags, classTypeNegated, classType, classNames,
-          inheritanceAnnotation, inheritanceClassName, inheritanceIsExtends, memberRules);
-    }
-  }
-
-  private ProguardKeepPackageNamesRule(
-      Origin origin,
-      Position position,
-      String source,
-      ProguardTypeMatcher classAnnotation,
-      ProguardAccessFlags classAccessFlags,
-      ProguardAccessFlags negatedClassAccessFlags,
-      boolean classTypeNegated,
-      ProguardClassType classType,
-      ProguardClassNameList classNames,
-      ProguardTypeMatcher inheritanceAnnotation,
-      ProguardTypeMatcher inheritanceClassName,
-      boolean inheritanceIsExtends,
-      List<ProguardMemberRule> memberRules) {
-    super(origin, position, source, classAnnotation, classAccessFlags, negatedClassAccessFlags,
-        classTypeNegated, classType, classNames, inheritanceAnnotation, inheritanceClassName,
-        inheritanceIsExtends, memberRules);
-  }
-
-  public static Builder builder() {
-    return new Builder();
-  }
-
-  @Override
-  String typeString() {
-    return "keeppackagenames";
-  }
-}
diff --git a/src/main/java/com/android/tools/r8/shaking/ProguardPackageMatcher.java b/src/main/java/com/android/tools/r8/shaking/ProguardPackageMatcher.java
new file mode 100644
index 0000000..48c4703
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/ProguardPackageMatcher.java
@@ -0,0 +1,96 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.shaking;
+
+import com.android.tools.r8.graph.DexType;
+
+public class ProguardPackageMatcher {
+  private final String pattern;
+
+  public ProguardPackageMatcher(String pattern) {
+    this.pattern = pattern;
+  }
+
+  public boolean matches(DexType type) {
+    return matchPackageNameImpl(pattern, 0, type.getPackageName(), 0);
+  }
+
+  private static boolean matchPackageNameImpl(
+      String pattern, int patternIndex, String name, int nameIndex) {
+    for (int i = patternIndex; i < pattern.length(); i++) {
+      char patternChar = pattern.charAt(i);
+      switch (patternChar) {
+        case '*':
+          int nextPatternIndex = i + 1;
+          // Check for **.
+          boolean includeSeparators =
+              pattern.length() > (nextPatternIndex) && pattern.charAt(nextPatternIndex) == '*';
+          if (includeSeparators) {
+            nextPatternIndex += 1;
+          }
+
+          // Fast cases for the common case where a pattern ends with '*' or '**'.
+          if (nextPatternIndex == pattern.length()) {
+            if (includeSeparators) {
+              return true;
+            }
+            boolean hasSeparators = containsSeparatorsStartingAt(name, nameIndex);
+            return !hasSeparators;
+          }
+
+          // Match the rest of the pattern against the (non-empty) rest of the class name.
+          for (int nextNameIndex = nameIndex; nextNameIndex < name.length(); nextNameIndex++) {
+            if (!includeSeparators) {
+              // Stop at the first separator for just *.
+              if (name.charAt(nextNameIndex) == '.') {
+                return matchPackageNameImpl(pattern, nextPatternIndex, name, nextNameIndex);
+              }
+            }
+            if (matchPackageNameImpl(pattern, nextPatternIndex, name, nextNameIndex)) {
+              return true;
+            }
+          }
+
+          // Finally, check the case where the '*' or '**' eats all of the package name.
+          return matchPackageNameImpl(pattern, nextPatternIndex, name, name.length());
+
+        case '?':
+          if (nameIndex == name.length() || name.charAt(nameIndex) == '.') {
+            return false;
+          }
+          nameIndex++;
+          break;
+
+        default:
+          if (nameIndex == name.length() || patternChar != name.charAt(nameIndex++)) {
+            return false;
+          }
+          break;
+      }
+    }
+    return nameIndex == name.length();
+  }
+
+  private static boolean containsSeparatorsStartingAt(String className, int nameIndex) {
+    return className.indexOf('.', nameIndex) != -1;
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) {
+      return true;
+    }
+    if (!(o instanceof ProguardPackageMatcher)) {
+      return false;
+    }
+    ProguardPackageMatcher other = (ProguardPackageMatcher) o;
+    return pattern.equals(other.pattern);
+  }
+
+  @Override
+  public int hashCode() {
+    return pattern.hashCode();
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/ProguardPackageNameList.java b/src/main/java/com/android/tools/r8/shaking/ProguardPackageNameList.java
new file mode 100644
index 0000000..6d45459
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/ProguardPackageNameList.java
@@ -0,0 +1,107 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.shaking;
+
+import com.android.tools.r8.graph.DexType;
+import it.unimi.dsi.fastutil.objects.Object2BooleanArrayMap;
+import it.unimi.dsi.fastutil.objects.Object2BooleanMap;
+import it.unimi.dsi.fastutil.objects.ObjectIterator;
+
+public class ProguardPackageNameList {
+
+  public static Builder builder() {
+    return new Builder();
+  }
+
+  public static class Builder {
+
+    /** Map used to store pairs of patterns and whether they are negated. */
+    private final Object2BooleanMap<ProguardPackageMatcher> matchers =
+        new Object2BooleanArrayMap<>();
+
+    private Builder() {}
+
+    public ProguardPackageNameList.Builder addPackageName(
+        boolean isNegated, ProguardPackageMatcher className) {
+      matchers.put(className, isNegated);
+      return this;
+    }
+
+    ProguardPackageNameList build() {
+      return new ProguardPackageNameList(matchers);
+    }
+  }
+
+  private final Object2BooleanMap<ProguardPackageMatcher> packageNames;
+
+  private ProguardPackageNameList(Object2BooleanMap<ProguardPackageMatcher> pacakgeNames) {
+    this.packageNames = pacakgeNames;
+  }
+
+  public void writeTo(StringBuilder builder) {
+    boolean first = true;
+    for (Object2BooleanMap.Entry<ProguardPackageMatcher> packageName :
+        packageNames.object2BooleanEntrySet()) {
+      if (!first) {
+        builder.append(',');
+      }
+      if (packageName.getBooleanValue()) {
+        builder.append('!');
+      }
+      builder.append(packageName.getKey().toString());
+      first = false;
+    }
+  }
+
+  public boolean matches(DexType type) {
+    for (Object2BooleanMap.Entry<ProguardPackageMatcher> packageName :
+        packageNames.object2BooleanEntrySet()) {
+      if (packageName.getKey().matches(type)) {
+        // If we match a negation, abort as non-match. If we match a positive, return true.
+        return !packageName.getBooleanValue();
+      }
+    }
+    return false;
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) {
+      return true;
+    }
+    if (!(o instanceof ProguardPackageNameList)) {
+      return false;
+    }
+    ProguardPackageNameList other = (ProguardPackageNameList) o;
+    if (packageNames.size() != other.packageNames.size()) {
+      return false;
+    }
+    ObjectIterator<Object2BooleanMap.Entry<ProguardPackageMatcher>> i1 =
+        packageNames.object2BooleanEntrySet().iterator();
+    ObjectIterator<Object2BooleanMap.Entry<ProguardPackageMatcher>> i2 =
+        other.packageNames.object2BooleanEntrySet().iterator();
+    while (i1.hasNext()) {
+      Object2BooleanMap.Entry<ProguardPackageMatcher> e1 = i1.next();
+      Object2BooleanMap.Entry<ProguardPackageMatcher> e2 = i2.next();
+      if (!e1.equals(e2)) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  @Override
+  public int hashCode() {
+    int hash = 0;
+    ObjectIterator<Object2BooleanMap.Entry<ProguardPackageMatcher>> iterator =
+        packageNames.object2BooleanEntrySet().iterator();
+    while (iterator.hasNext()) {
+      Object2BooleanMap.Entry<ProguardPackageMatcher> packageMatcher = iterator.next();
+      hash = hash * (packageMatcher.getBooleanValue() ? 1 : 2);
+      hash = hash * 13 + packageMatcher.getKey().hashCode();
+    }
+    return hash;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
index 18db8ea..a793cfb 100644
--- a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
+++ b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
@@ -67,7 +67,6 @@
   private final Set<DexReference> noOptimization = Sets.newIdentityHashSet();
   private final Set<DexReference> noObfuscation = Sets.newIdentityHashSet();
   private final LinkedHashMap<DexReference, DexReference> reasonAsked = new LinkedHashMap<>();
-  private final Set<DexReference> keepPackageName = Sets.newIdentityHashSet();
   private final Set<ProguardConfigurationRule> rulesThatUseExtendsOrImplementsWrong =
       Sets.newIdentityHashSet();
   private final Set<DexReference> checkDiscarded = Sets.newIdentityHashSet();
@@ -175,8 +174,7 @@
           markMatchingFields(clazz, memberKeepRules, rule, preconditionSupplier);
           markMatchingMethods(clazz, memberKeepRules, rule, preconditionSupplier);
         }
-      } else if (rule instanceof ProguardWhyAreYouKeepingRule
-          || rule instanceof ProguardKeepPackageNamesRule) {
+      } else if (rule instanceof ProguardWhyAreYouKeepingRule) {
         markClass(clazz, rule);
         markMatchingVisibleMethods(clazz, memberKeepRules, rule, null, true);
         markMatchingVisibleFields(clazz, memberKeepRules, rule, null, true);
@@ -266,7 +264,6 @@
         noOptimization,
         noObfuscation,
         ImmutableList.copyOf(reasonAsked.values()),
-        keepPackageName,
         checkDiscarded,
         alwaysInline,
         forceInline,
@@ -952,8 +949,6 @@
       noSideEffects.put(item.toReference(), rule);
     } else if (context instanceof ProguardWhyAreYouKeepingRule) {
       reasonAsked.computeIfAbsent(item.toReference(), i -> i);
-    } else if (context instanceof ProguardKeepPackageNamesRule) {
-      keepPackageName.add(item.toReference());
     } else if (context instanceof ProguardAssumeValuesRule) {
       assumedValues.put(item.toReference(), rule);
     } else if (context instanceof ProguardCheckDiscardRule) {
@@ -1037,7 +1032,6 @@
     public final Set<DexReference> noOptimization;
     public final Set<DexReference> noObfuscation;
     public final ImmutableList<DexReference> reasonAsked;
-    public final Set<DexReference> keepPackageName;
     public final Set<DexReference> checkDiscarded;
     public final Set<DexMethod> alwaysInline;
     public final Set<DexMethod> forceInline;
@@ -1060,7 +1054,6 @@
         Set<DexReference> noOptimization,
         Set<DexReference> noObfuscation,
         ImmutableList<DexReference> reasonAsked,
-        Set<DexReference> keepPackageName,
         Set<DexReference> checkDiscarded,
         Set<DexMethod> alwaysInline,
         Set<DexMethod> forceInline,
@@ -1080,7 +1073,6 @@
       this.noOptimization = noOptimization;
       this.noObfuscation = noObfuscation;
       this.reasonAsked = reasonAsked;
-      this.keepPackageName = Collections.unmodifiableSet(keepPackageName);
       this.checkDiscarded = Collections.unmodifiableSet(checkDiscarded);
       this.alwaysInline = Collections.unmodifiableSet(alwaysInline);
       this.forceInline = Collections.unmodifiableSet(forceInline);
@@ -1103,7 +1095,6 @@
       this.noOptimization = lense.rewriteMutableReferencesConservatively(previous.noOptimization);
       this.noObfuscation = lense.rewriteMutableReferencesConservatively(previous.noObfuscation);
       this.reasonAsked = lense.rewriteReferencesConservatively(previous.reasonAsked);
-      this.keepPackageName = lense.rewriteReferencesConservatively(previous.keepPackageName);
       this.checkDiscarded = lense.rewriteReferencesConservatively(previous.checkDiscarded);
       this.alwaysInline = lense.rewriteMethodsConservatively(previous.alwaysInline);
       this.forceInline = lense.rewriteMethodsConservatively(previous.forceInline);
@@ -1346,7 +1337,6 @@
       builder.append("\nnoOptimization: " + noOptimization.size());
       builder.append("\nnoObfuscation: " + noObfuscation.size());
       builder.append("\nreasonAsked: " + reasonAsked.size());
-      builder.append("\nkeepPackageName: " + keepPackageName.size());
       builder.append("\ncheckDiscarded: " + checkDiscarded.size());
       builder.append("\nnoSideEffects: " + noSideEffects.size());
       builder.append("\nassumedValues: " + assumedValues.size());
diff --git a/src/test/java/com/android/tools/r8/naming/KeepPackageNamesTest.java b/src/test/java/com/android/tools/r8/naming/KeepPackageNamesTest.java
index 6167a56..e57c596 100644
--- a/src/test/java/com/android/tools/r8/naming/KeepPackageNamesTest.java
+++ b/src/test/java/com/android/tools/r8/naming/KeepPackageNamesTest.java
@@ -10,7 +10,6 @@
 import static org.hamcrest.MatcherAssert.assertThat;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertNotEquals;
-import static org.junit.Assume.assumeTrue;
 
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.errors.Unreachable;
@@ -60,8 +59,7 @@
               getPackageNameFromDescriptor(sub.getOriginalDescriptor()),
               getPackageNameFromDescriptor(sub.getFinalDescriptor()));
           assertThat(
-              getPackageNameFromDescriptor(sub.getFinalDescriptor()),
-              containsString(PACKAGE_NAME));
+              getPackageNameFromDescriptor(sub.getFinalDescriptor()), containsString(PACKAGE_NAME));
           break;
         case DOUBLE_ASTERISKS:
           assertEquals(
@@ -95,7 +93,6 @@
 
   @Test
   public void testR8() throws Exception {
-    assumeTrue("b/130135768", config == TestConfig.DOUBLE_ASTERISKS);
     testForR8(Backend.DEX)
         .addProgramClasses(CLASSES)
         .addKeepAndMinifyAllClassesRule()
diff --git a/src/test/java/com/android/tools/r8/shaking/ProguardConfigurationParserTest.java b/src/test/java/com/android/tools/r8/shaking/ProguardConfigurationParserTest.java
index 430f263..6b7401d 100644
--- a/src/test/java/com/android/tools/r8/shaking/ProguardConfigurationParserTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/ProguardConfigurationParserTest.java
@@ -1303,6 +1303,51 @@
     testKeepattributes(expected, config);
   }
 
+  private void testKeeppackagenames(ProguardPackageNameList expected, String config) {
+    ProguardConfigurationParser parser =
+        new ProguardConfigurationParser(new DexItemFactory(), reporter);
+    parser.parse(createConfigurationForTesting(ImmutableList.of(config)));
+    verifyParserEndsCleanly();
+    assertEquals(expected, parser.getConfigRawForTesting().getKeepPackageNamesPatterns());
+  }
+
+  @Test
+  public void parseKeeppackagenames() {
+    ProguardPackageNameList xxxYYY =
+        ProguardPackageNameList.builder()
+            .addPackageName(false, new ProguardPackageMatcher("xxx"))
+            .addPackageName(false, new ProguardPackageMatcher("yyy"))
+            .build();
+    testKeeppackagenames(xxxYYY, "-keeppackagenames xxx,yyy");
+    testKeeppackagenames(xxxYYY, "-keeppackagenames xxx, yyy");
+    testKeeppackagenames(xxxYYY, "-keeppackagenames xxx ,yyy");
+    testKeeppackagenames(xxxYYY, "-keeppackagenames xxx   ,   yyy");
+    testKeeppackagenames(xxxYYY, "-keeppackagenames       xxx   ,   yyy     ");
+    testKeeppackagenames(xxxYYY, "-keeppackagenames       xxx   ,   yyy     \n");
+    testKeeppackagenames(xxxYYY, "-keeppackagenames \"xxx\",\"yyy\"");
+
+    testKeeppackagenames(
+        ProguardPackageNameList.builder()
+            .addPackageName(false, new ProguardPackageMatcher("com.**"))
+            .addPackageName(false, new ProguardPackageMatcher("org.*"))
+            .build(),
+        "-keeppackagenames com.**, org.*");
+
+    testKeeppackagenames(
+        ProguardPackageNameList.builder()
+            .addPackageName(false, new ProguardPackageMatcher("c?m.**"))
+            .addPackageName(false, new ProguardPackageMatcher("?r?.*"))
+            .build(),
+        "-keeppackagenames c?m.**, ?r?.*");
+
+    testKeeppackagenames(
+        ProguardPackageNameList.builder()
+            .addPackageName(true, new ProguardPackageMatcher("c?m.**"))
+            .addPackageName(true, new ProguardPackageMatcher("?r?.*"))
+            .build(),
+        "-keeppackagenames !c?m.**, !?r?.*");
+  }
+
   @Test
   public void parseInvalidKeepattributes() {
     try {
diff --git a/src/test/java/com/android/tools/r8/shaking/ProguardPackageNameMatcherTest.java b/src/test/java/com/android/tools/r8/shaking/ProguardPackageNameMatcherTest.java
new file mode 100644
index 0000000..d730c34
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/ProguardPackageNameMatcherTest.java
@@ -0,0 +1,146 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.shaking;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.graph.DexItemFactory;
+import org.junit.Test;
+
+public class ProguardPackageNameMatcherTest {
+  private DexItemFactory dexItemFactory = new DexItemFactory();
+
+  private boolean matches(ProguardPackageNameList matcher, String packageName) {
+    return matcher.matches(dexItemFactory.createType("L" + packageName.replace('.', '/') + "/A;"));
+  }
+
+  @Test
+  public void testSimple() {
+    ProguardPackageNameList matcher =
+        ProguardPackageNameList.builder()
+            .addPackageName(false, new ProguardPackageMatcher("com.example"))
+            .build();
+    assertTrue(matches(matcher, "com.example"));
+    assertFalse(matches(matcher, "com.exampl"));
+    assertFalse(matches(matcher, "com.example.a"));
+  }
+
+  @Test
+  public void testSingleEnd() {
+    ProguardPackageNameList matcher =
+        ProguardPackageNameList.builder()
+            .addPackageName(false, new ProguardPackageMatcher("com.example*"))
+            .build();
+    assertTrue(matches(matcher, "com.example"));
+    assertTrue(matches(matcher, "com.example1"));
+    assertTrue(matches(matcher, "com.example2"));
+    assertFalse(matches(matcher, "com.exampl"));
+    assertFalse(matches(matcher, "com.example.a"));
+  }
+
+  @Test
+  public void testSingleBeginning() {
+    ProguardPackageNameList matcher =
+        ProguardPackageNameList.builder()
+            .addPackageName(false, new ProguardPackageMatcher("*.example"))
+            .build();
+    assertTrue(matches(matcher, "com.example"));
+    assertTrue(matches(matcher, "org.example"));
+    assertFalse(matches(matcher, "com.example1"));
+    assertFalse(matches(matcher, "org.example1"));
+    assertFalse(matches(matcher, "com.exampl"));
+    assertFalse(matches(matcher, "com.example.a"));
+  }
+
+  @Test
+  public void testDoubleEnd() {
+    ProguardPackageNameList matcher =
+        ProguardPackageNameList.builder()
+            .addPackageName(false, new ProguardPackageMatcher("com.example**"))
+            .build();
+    assertTrue(matches(matcher, "com.example"));
+    assertTrue(matches(matcher, "com.example1"));
+    assertTrue(matches(matcher, "com.example2"));
+    assertTrue(matches(matcher, "com.example.a"));
+    assertTrue(matches(matcher, "com.example.a.a"));
+    assertFalse(matches(matcher, "com.exampl"));
+  }
+
+  @Test
+  public void testDoubleBeginning() {
+    ProguardPackageNameList matcher =
+        ProguardPackageNameList.builder()
+            .addPackageName(false, new ProguardPackageMatcher("**example"))
+            .build();
+    assertTrue(matches(matcher, "com.example"));
+    assertTrue(matches(matcher, "org.example"));
+    assertTrue(matches(matcher, "com.a.example"));
+    assertTrue(matches(matcher, "com.a.a.example"));
+    assertTrue(matches(matcher, "comexample"));
+    assertFalse(matches(matcher, "com.example1"));
+  }
+
+  @Test
+  public void testQuestionMark() {
+    ProguardPackageNameList matcher =
+        ProguardPackageNameList.builder()
+            .addPackageName(false, new ProguardPackageMatcher("com.e?ample"))
+            .build();
+    assertTrue(matches(matcher, "com.example"));
+    assertTrue(matches(matcher, "com.eyample"));
+    assertFalse(matches(matcher, "com.example1"));
+    assertFalse(matches(matcher, "com.example.a"));
+  }
+
+  @Test
+  public void testList() {
+    ProguardPackageNameList matcher =
+        ProguardPackageNameList.builder()
+            .addPackageName(false, new ProguardPackageMatcher("com.example"))
+            .addPackageName(false, new ProguardPackageMatcher("org.example"))
+            .build();
+    assertTrue(matches(matcher, "com.example"));
+    assertTrue(matches(matcher, "org.example"));
+    assertFalse(matches(matcher, "com.example1"));
+    assertFalse(matches(matcher, "com.example.a"));
+    assertFalse(matches(matcher, "org.example1"));
+    assertFalse(matches(matcher, "org.example.a"));
+  }
+
+  @Test
+  public void testListNegation() {
+    ProguardPackageNameList matcher =
+        ProguardPackageNameList.builder()
+            .addPackageName(true, new ProguardPackageMatcher("!org.example"))
+            .addPackageName(false, new ProguardPackageMatcher("*.example"))
+            .build();
+    assertTrue(matches(matcher, "com.example"));
+    assertTrue(matches(matcher, "org.example"));
+  }
+
+  @Test
+  public void testListNegationNotMatched() {
+    ProguardPackageNameList matcher =
+        ProguardPackageNameList.builder()
+            .addPackageName(false, new ProguardPackageMatcher("*.example"))
+            .addPackageName(true, new ProguardPackageMatcher("!org.example"))
+            .build();
+    assertTrue(matches(matcher, "com.example"));
+    // Negations only stops attempts on subsequent names.
+    assertTrue(matches(matcher, "org.example"));
+  }
+
+  @Test
+  public void testNegateAll() {
+    ProguardPackageNameList matcher =
+        ProguardPackageNameList.builder()
+            .addPackageName(true, new ProguardPackageMatcher("!**"))
+            .build();
+    assertFalse(matches(matcher, "com"));
+    assertFalse(matches(matcher, "com.example"));
+    assertFalse(matches(matcher, "com.example.a"));
+  }
+}