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