diff --git a/mercurial/filesetlang.py b/mercurial/filesetlang.py
--- a/mercurial/filesetlang.py
+++ b/mercurial/filesetlang.py
@@ -149,10 +149,12 @@ def _analyze(x):
     if op == 'not':
         t = _analyze(x[1])
         return (op, t)
-    if op in {'and', 'minus'}:
+    if op == 'and':
         ta = _analyze(x[1])
         tb = _analyze(x[2])
         return (op, ta, tb)
+    if op == 'minus':
+        return _analyze(('and', x[1], ('not', x[2])))
     if op in {'list', 'or'}:
         ts = tuple(_analyze(y) for y in x[1:])
         return (op,) + ts
@@ -171,6 +173,11 @@ def analyze(x):
     """
     return _analyze(x)
 
+def _optimizeandops(op, ta, tb):
+    if tb is not None and tb[0] == 'not':
+        return ('minus', ta, tb[1])
+    return (op, ta, tb)
+
 def _optimize(x):
     if x is None:
         return 0, x
@@ -188,13 +195,9 @@ def _optimize(x):
         wa, ta = _optimize(x[1])
         wb, tb = _optimize(x[2])
         if wa <= wb:
-            return wa, (op, ta, tb)
+            return wa, _optimizeandops(op, ta, tb)
         else:
-            return wb, (op, tb, ta)
-    if op == 'minus':
-        wa, ta = _optimize(x[1])
-        wb, tb = _optimize(x[2])
-        return max(wa, wb), (op, ta, tb)
+            return wb, _optimizeandops(op, tb, ta)
     if op == 'or':
         ws, ts = zip(*(_optimize(y) for y in x[1:]))
         return max(ws), (op,) + ts
diff --git a/tests/test-fileset.t b/tests/test-fileset.t
--- a/tests/test-fileset.t
+++ b/tests/test-fileset.t
@@ -203,6 +203,73 @@ Show parsed tree at stages:
   b1
   b2
 
+Use differencematcher for 'x and not y':
+
+  $ fileset -p optimized -s 'a* and not a1'
+  * optimized:
+  (minus
+    (symbol 'a*')
+    (symbol 'a1'))
+  * matcher:
+  <differencematcher
+    m1=<patternmatcher patterns='(?:a[^/]*$)'>,
+    m2=<patternmatcher patterns='(?:a1$)'>>
+  a2
+
+  $ fileset -p optimized -s '!binary() and a*'
+  * optimized:
+  (minus
+    (symbol 'a*')
+    (func
+      (symbol 'binary')
+      None))
+  * matcher:
+  <differencematcher
+    m1=<patternmatcher patterns='(?:a[^/]*$)'>,
+    m2=<predicatenmatcher pred=binary>>
+  a1
+  a2
+
+'x - y' is rewritten to 'x and not y' first so the operands can be reordered:
+
+  $ fileset -p analyzed -p optimized -s 'a* - a1'
+  * analyzed:
+  (and
+    (symbol 'a*')
+    (not
+      (symbol 'a1')))
+  * optimized:
+  (minus
+    (symbol 'a*')
+    (symbol 'a1'))
+  * matcher:
+  <differencematcher
+    m1=<patternmatcher patterns='(?:a[^/]*$)'>,
+    m2=<patternmatcher patterns='(?:a1$)'>>
+  a2
+
+  $ fileset -p analyzed -p optimized -s 'binary() - a*'
+  * analyzed:
+  (and
+    (func
+      (symbol 'binary')
+      None)
+    (not
+      (symbol 'a*')))
+  * optimized:
+  (and
+    (not
+      (symbol 'a*'))
+    (func
+      (symbol 'binary')
+      None))
+  * matcher:
+  <intersectionmatcher
+    m1=<predicatenmatcher
+      pred=<not
+        <patternmatcher patterns='(?:a[^/]*$)'>>>,
+    m2=<predicatenmatcher pred=binary>>
+
 Test files status
 
   $ rm a1