From 70452d226e5c551c3e86984690edf99eae0fc6a7 Mon Sep 17 00:00:00 2001
From: Eric Fellheimer <felly@google.com>
Date: Thu, 11 Aug 2016 18:58:47 +0000
Subject: Stream the right-hand side of subtractive query expressions. This
 means only the left-hand side needs to be pinned fully into memory.

Intersection is not associative, so we can't do the same thing there. For example, "abc" ^ "abc" = "abc", but "abc" ^ "a" ^ "b" ^ "c" = <null>.

--
MOS_MIGRATED_REVID=130015098
---
 .../query2/engine/BinaryOperatorExpression.java    | 49 ++++++++++++++--------
 1 file changed, 31 insertions(+), 18 deletions(-)

(limited to 'src/main/java/com/google/devtools/build/lib')

diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java
index 987e8fd9b4..364485354a 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java
@@ -16,7 +16,6 @@ package com.google.devtools.build.lib.query2.engine;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.query2.engine.Lexer.TokenKind;
 import com.google.devtools.build.lib.util.Preconditions;
-
 import java.util.Collection;
 import java.util.List;
 import java.util.Set;
@@ -62,24 +61,38 @@ public class BinaryOperatorExpression extends QueryExpression {
       }
       return;
     }
-    // We cannot do differences with partial results. So we fully evaluate the operands
-    Set<T> lhsValue = QueryUtil.evalAll(env, context, operands.get(0));
-    for (int i = 1; i < operands.size(); i++) {
-      Set<T> rhsValue = QueryUtil.evalAll(env, context, operands.get(i));
-      switch (operator) {
-        case INTERSECT:
-        case CARET:
-          lhsValue.retainAll(rhsValue);
-          break;
-        case EXCEPT:
-        case MINUS:
-          lhsValue.removeAll(rhsValue);
-          break;
-        case UNION:
-        case PLUS:
-        default:
-          throw new IllegalStateException("operator=" + operator);
+
+    // Once we have fully evaluated the left-hand side, we can stream-process the right-hand side
+    // for minus operations. Note that this is suboptimal if the left-hand side results are very
+    // large compared to the right-hand side. Which is the case is hard to know before evaluating.
+    // We could consider determining this dynamically, however, by evaluating both the left and
+    // right hand side partially until one side finishes sooner.
+    final Set<T> lhsValue = QueryUtil.evalAll(env, context, operands.get(0));
+    if (operator == TokenKind.EXCEPT || operator == TokenKind.MINUS) {
+      for (int i = 1; i < operands.size(); i++) {
+        env.eval(operands.get(i), context,
+            new Callback<T>() {
+              @Override
+              public void process(Iterable<T> partialResult)
+                  throws QueryException, InterruptedException {
+                for (T target : partialResult) {
+                  lhsValue.remove(target);
+                }
+              }
+            });
       }
+      callback.process(lhsValue);
+      return;
+    }
+
+    // Intersection is not associative, so we are forced to pin both the left-hand and right-hand
+    // side of the operation at the same time.
+    // TODO(bazel-team): Consider keeping just the name / label of the right-hand side results
+    // instead of the potentially heavy-weight instances of type T.
+    Preconditions.checkState(operator == TokenKind.INTERSECT || operator == TokenKind.CARET,
+        operator);
+    for (int i = 1; i < operands.size(); i++) {
+      lhsValue.retainAll(QueryUtil.evalAll(env, context, operands.get(i)));
     }
     callback.process(lhsValue);
   }
-- 
cgit v1.2.3