001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.filter;
019
020import java.io.IOException;
021import java.util.ArrayList;
022import java.util.Collections;
023import java.util.List;
024import java.util.Objects;
025import org.apache.hadoop.hbase.Cell;
026import org.apache.yetus.audience.InterfaceAudience;
027
028/**
029 * FilterListWithAND represents an ordered list of filters which will be evaluated with an AND
030 * operator.
031 */
032@InterfaceAudience.Private
033public class FilterListWithAND extends FilterListBase {
034
035  private List<Filter> seekHintFilters = new ArrayList<>();
036
037  public FilterListWithAND(List<Filter> filters) {
038    super(filters);
039    // For FilterList with AND, when call FL's transformCell(), we should transform cell for all
040    // sub-filters (because all sub-filters return INCLUDE*). So here, fill this array with true. we
041    // keep this in FilterListWithAND for abstracting the transformCell() in FilterListBase.
042    subFiltersIncludedCell = new ArrayList<>(Collections.nCopies(filters.size(), true));
043  }
044
045  @Override
046  public void addFilterLists(List<Filter> filters) {
047    if (checkAndGetReversed(filters, isReversed()) != isReversed()) {
048      throw new IllegalArgumentException("Filters in the list must have the same reversed flag");
049    }
050    this.filters.addAll(filters);
051    this.subFiltersIncludedCell.addAll(Collections.nCopies(filters.size(), true));
052  }
053
054  @Override
055  protected String formatLogFilters(List<Filter> logFilters) {
056    return String.format("FilterList AND (%d/%d): %s", logFilters.size(), this.size(),
057      logFilters.toString());
058  }
059
060  /**
061   * FilterList with MUST_PASS_ALL choose the maximal forward step among sub-filters in filter list.
062   * Let's call it: The Maximal Step Rule. So if filter-A in filter list return INCLUDE and filter-B
063   * in filter list return INCLUDE_AND_NEXT_COL, then the filter list should return
064   * INCLUDE_AND_NEXT_COL. For SEEK_NEXT_USING_HINT, it's more special, and in method
065   * filterCellWithMustPassAll(), if any sub-filter return SEEK_NEXT_USING_HINT, then our filter
066   * list will return SEEK_NEXT_USING_HINT. so we don't care about the SEEK_NEXT_USING_HINT here.
067   * <br/>
068   * <br/>
069   * The jump step will be:
070   *
071   * <pre>
072   * INCLUDE &lt; SKIP &lt; INCLUDE_AND_NEXT_COL &lt; NEXT_COL &lt; INCLUDE_AND_SEEK_NEXT_ROW &lt; NEXT_ROW
073   *     &lt; SEEK_NEXT_USING_HINT
074   * </pre>
075   *
076   * Here, we have the following map to describe The Maximal Step Rule. if current return code (for
077   * previous sub-filters in filter list) is <strong>ReturnCode</strong>, and current filter returns
078   * <strong>localRC</strong>, then we should return map[ReturnCode][localRC] for the merged result,
079   * according to The Maximal Step Rule. <br/>
080   *
081   * <pre>
082   * LocalCode\ReturnCode       INCLUDE                    INCLUDE_AND_NEXT_COL      INCLUDE_AND_SEEK_NEXT_ROW  SKIP                  NEXT_COL              NEXT_ROW              SEEK_NEXT_USING_HINT
083   * INCLUDE                    INCLUDE                    INCLUDE_AND_NEXT_COL      INCLUDE_AND_SEEK_NEXT_ROW  SKIP                  NEXT_COL              NEXT_ROW              SEEK_NEXT_USING_HINT
084   * INCLUDE_AND_NEXT_COL       INCLUDE_AND_NEXT_COL       INCLUDE_AND_NEXT_COL      INCLUDE_AND_SEEK_NEXT_ROW  NEXT_COL              NEXT_COL              NEXT_ROW              SEEK_NEXT_USING_HINT
085   * INCLUDE_AND_SEEK_NEXT_ROW  INCLUDE_AND_SEEK_NEXT_ROW  INCLUDE_AND_SEEK_NEXT_ROW INCLUDE_AND_SEEK_NEXT_ROW  NEXT_ROW              NEXT_ROW              NEXT_ROW              SEEK_NEXT_USING_HINT
086   * SKIP                       SKIP                       NEXT_COL                  NEXT_ROW                   SKIP                  NEXT_COL              NEXT_ROW              SEEK_NEXT_USING_HINT
087   * NEXT_COL                   NEXT_COL                   NEXT_COL                  NEXT_ROW                   NEXT_COL              NEXT_COL              NEXT_ROW              SEEK_NEXT_USING_HINT
088   * NEXT_ROW                   NEXT_ROW                   NEXT_ROW                  NEXT_ROW                   NEXT_ROW              NEXT_ROW              NEXT_ROW              SEEK_NEXT_USING_HINT
089   * SEEK_NEXT_USING_HINT       SEEK_NEXT_USING_HINT       SEEK_NEXT_USING_HINT      SEEK_NEXT_USING_HINT       SEEK_NEXT_USING_HINT  SEEK_NEXT_USING_HINT  SEEK_NEXT_USING_HINT  SEEK_NEXT_USING_HINT
090   * </pre>
091   *
092   * @param rc      Return code which is calculated by previous sub-filter(s) in filter list.
093   * @param localRC Return code of the current sub-filter in filter list.
094   * @return Return code which is merged by the return code of previous sub-filter(s) and the return
095   *         code of current sub-filter.
096   */
097  private ReturnCode mergeReturnCode(ReturnCode rc, ReturnCode localRC) {
098    if (rc == ReturnCode.SEEK_NEXT_USING_HINT) {
099      return ReturnCode.SEEK_NEXT_USING_HINT;
100    }
101    switch (localRC) {
102      case SEEK_NEXT_USING_HINT:
103        return ReturnCode.SEEK_NEXT_USING_HINT;
104      case INCLUDE:
105        return rc;
106      case INCLUDE_AND_NEXT_COL:
107        if (isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.INCLUDE_AND_NEXT_COL)) {
108          return ReturnCode.INCLUDE_AND_NEXT_COL;
109        }
110        if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW)) {
111          return ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW;
112        }
113        if (isInReturnCodes(rc, ReturnCode.SKIP, ReturnCode.NEXT_COL)) {
114          return ReturnCode.NEXT_COL;
115        }
116        if (isInReturnCodes(rc, ReturnCode.NEXT_ROW)) {
117          return ReturnCode.NEXT_ROW;
118        }
119        break;
120      case INCLUDE_AND_SEEK_NEXT_ROW:
121        if (
122          isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.INCLUDE_AND_NEXT_COL,
123            ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW)
124        ) {
125          return ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW;
126        }
127        if (isInReturnCodes(rc, ReturnCode.SKIP, ReturnCode.NEXT_COL, ReturnCode.NEXT_ROW)) {
128          return ReturnCode.NEXT_ROW;
129        }
130        break;
131      case SKIP:
132        if (isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.SKIP)) {
133          return ReturnCode.SKIP;
134        }
135        if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_NEXT_COL, ReturnCode.NEXT_COL)) {
136          return ReturnCode.NEXT_COL;
137        }
138        if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW, ReturnCode.NEXT_ROW)) {
139          return ReturnCode.NEXT_ROW;
140        }
141        break;
142      case NEXT_COL:
143        if (
144          isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.INCLUDE_AND_NEXT_COL, ReturnCode.SKIP,
145            ReturnCode.NEXT_COL)
146        ) {
147          return ReturnCode.NEXT_COL;
148        }
149        if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW, ReturnCode.NEXT_ROW)) {
150          return ReturnCode.NEXT_ROW;
151        }
152        break;
153      case NEXT_ROW:
154        return ReturnCode.NEXT_ROW;
155    }
156    throw new IllegalStateException(
157      "Received code is not valid. rc: " + rc + ", localRC: " + localRC);
158  }
159
160  private boolean isIncludeRelatedReturnCode(ReturnCode rc) {
161    return isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.INCLUDE_AND_NEXT_COL,
162      ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW);
163  }
164
165  @Override
166  public ReturnCode filterCell(Cell c) throws IOException {
167    if (isEmpty()) {
168      return ReturnCode.INCLUDE;
169    }
170    ReturnCode rc = ReturnCode.INCLUDE;
171    this.seekHintFilters.clear();
172    for (int i = 0, n = filters.size(); i < n; i++) {
173      Filter filter = filters.get(i);
174      if (filter.filterAllRemaining()) {
175        return ReturnCode.NEXT_ROW;
176      }
177      ReturnCode localRC;
178      localRC = filter.filterCell(c);
179      if (localRC == ReturnCode.SEEK_NEXT_USING_HINT) {
180        seekHintFilters.add(filter);
181      }
182      rc = mergeReturnCode(rc, localRC);
183      // Only when rc is INCLUDE* case, we should pass the cell to the following sub-filters.
184      // otherwise we may mess up the global state (such as offset, count..) in the following
185      // sub-filters. (HBASE-20565)
186      if (!isIncludeRelatedReturnCode(rc)) {
187        return rc;
188      }
189    }
190    if (!seekHintFilters.isEmpty()) {
191      return ReturnCode.SEEK_NEXT_USING_HINT;
192    }
193    return rc;
194  }
195
196  @Override
197  public void reset() throws IOException {
198    for (int i = 0, n = filters.size(); i < n; i++) {
199      filters.get(i).reset();
200    }
201    seekHintFilters.clear();
202  }
203
204  @Override
205  public boolean filterRowKey(Cell firstRowCell) throws IOException {
206    if (isEmpty()) {
207      return super.filterRowKey(firstRowCell);
208    }
209    boolean retVal = false;
210    for (int i = 0, n = filters.size(); i < n; i++) {
211      Filter filter = filters.get(i);
212      if (filter.filterAllRemaining() || filter.filterRowKey(firstRowCell)) {
213        // Can't just return true here, because there are some filters (such as PrefixFilter) which
214        // will catch the row changed event by filterRowKey(). If we return early here, those
215        // filters will have no chance to update their row state.
216        retVal = true;
217      }
218    }
219    return retVal;
220  }
221
222  @Override
223  public boolean filterAllRemaining() throws IOException {
224    if (isEmpty()) {
225      return super.filterAllRemaining();
226    }
227    for (int i = 0, n = filters.size(); i < n; i++) {
228      if (filters.get(i).filterAllRemaining()) {
229        return true;
230      }
231    }
232    return false;
233  }
234
235  @Override
236  public boolean filterRow() throws IOException {
237    if (isEmpty()) {
238      return super.filterRow();
239    }
240    for (int i = 0, n = filters.size(); i < n; i++) {
241      Filter filter = filters.get(i);
242      if (filter.filterRow()) {
243        return true;
244      }
245    }
246    return false;
247  }
248
249  @Override
250  public Cell getNextCellHint(Cell currentCell) throws IOException {
251    if (isEmpty()) {
252      return super.getNextCellHint(currentCell);
253    }
254    Cell maxHint = null;
255    for (Filter filter : seekHintFilters) {
256      if (filter.filterAllRemaining()) {
257        continue;
258      }
259      Cell curKeyHint = filter.getNextCellHint(currentCell);
260      if (maxHint == null) {
261        maxHint = curKeyHint;
262        continue;
263      }
264      if (this.compareCell(maxHint, curKeyHint) < 0) {
265        maxHint = curKeyHint;
266      }
267    }
268    return maxHint;
269  }
270
271  @Override
272  public boolean equals(Object obj) {
273    if (!(obj instanceof FilterListWithAND)) {
274      return false;
275    }
276    if (this == obj) {
277      return true;
278    }
279    FilterListWithAND f = (FilterListWithAND) obj;
280    return this.filters.equals(f.getFilters()) && this.seekHintFilters.equals(f.seekHintFilters);
281  }
282
283  @Override
284  public int hashCode() {
285    return Objects.hash(this.seekHintFilters, this.filters);
286  }
287}