text:
package cronapi.database;

import java.lang.annotation.Annotation;
import java.lang.reflect.Field;
import java.util.*;

import javax.persistence.EntityManager;
import javax.persistence.metamodel.EntityType;
import javax.persistence.metamodel.SingularAttribute;

import org.eclipse.persistence.internal.jpa.parsing.DotNode;
import org.eclipse.persistence.internal.jpa.parsing.SelectNode;
import org.eclipse.persistence.internal.jpa.parsing.VariableNode;
import org.eclipse.persistence.internal.jpa.parsing.jpql.JPQLParser;
import org.springframework.security.core.GrantedAuthority;

import cronapi.RestClient;
import cronapi.Var;
import cronapi.database.DataSourceFilter.DataSourceFilterItem;
import cronapi.database.DataSourceFilter.DataSourceOrderItem;
import cronapi.i18n.Messages;
import cronapi.rest.security.CronappSecurity;

public class DataSourceFilter {

  private LinkedList<DataSourceFilterItem> items = new LinkedList<>();
  private LinkedList<DataSourceOrderItem> orders = new LinkedList<>();
  private String type = "AND";

  private String appliedJpql;
  private Var[] appliedParams;

  private DataSourceFilter(String filter, String order, boolean caseInsensitive) {
    if(filter != null && !filter.trim().isEmpty()) {

      String[] values = filter.trim().split(";");
      if(values.length > 0) {
        for(String v : values) {
          boolean cs = caseInsensitive;
          String[] pair = null;
          String operation;
          if(v.contains("@=")) {
            pair = v.trim().split("@=");
            operation = "LIKE";
          }
          else if(v.contains("<=")) {
            pair = v.trim().split("<=");
            operation = "<=";
          }
          else if(v.contains(">=")) {
            pair = v.trim().split(">=");
            operation = ">=";
          }
          else if(v.contains(">")) {
            pair = v.trim().split(">");
            operation = ">";
          }
          else if(v.contains("<")) {
            pair = v.trim().split("<");
            operation = "<";
          }
          else {
            pair = v.trim().split("=");
            operation = "=";
          }

          pair[0] = pair[0].trim();

          if (pair[0].endsWith("/i")) {
            cs = true;
            pair[0] = pair[0].substring(0, pair[0].length()-2);
          }

          if(values.length == 1 && pair.length == 1) {
            items.add(new DataSourceFilter.DataSourceFilterItem("*", Var.valueOf(Var.deserialize(pair[0])), "LIKE", Var.deserializeType(pair[0]), cs));
            break;
          }

          if(pair.length > 0 && !pair[0].trim().isEmpty()) {
            if(pair.length == 1) {
              items.add(new DataSourceFilter.DataSourceFilterItem(pair[0], Var.VAR_NULL, operation, "text", cs));
            }
            if(pair.length > 1) {
              items.add(new DataSourceFilter.DataSourceFilterItem(pair[0], Var.valueOf(Var.deserialize(pair[1])), operation, Var.deserializeType(pair[1]), cs));
            }
          }
        }
      }
    }

    if(order != null && !order.trim().isEmpty()) {

      String[] values = order.trim().split(";");
      if(values.length > 0) {
        for(String v : values) {
          String[] pair = v.trim().split("\\|");

          if(pair.length == 1) {
            orders.add(new DataSourceFilter.DataSourceOrderItem(pair[0], "ASC"));
          }

          if(pair.length == 2) {
            orders.add(new DataSourceFilter.DataSourceOrderItem(pair[0], pair[1]));
          }
        }
      }
    }

  }

  public static DataSourceFilter getInstance(String filter, String order, String filterType, boolean caseInsensitive) {
    if((filter != null && !filter.trim().isEmpty()) || (order != null && !order.trim().isEmpty())) {
      DataSourceFilter dsFilter = new DataSourceFilter(filter, order, caseInsensitive);
      if(filterType != null)
        dsFilter.setType(filterType);

      return dsFilter;
    }

    return null;
  }

  public LinkedList<DataSourceFilterItem> getItems() {
    return items;
  }

  public void setItems(LinkedList<DataSourceFilterItem> items) {
    this.items = items;
  }

  public String getType() {
    return type;
  }

  public void setType(String type) {
    if(type.equalsIgnoreCase("or") || type.equalsIgnoreCase("and")) {
      this.type = type;
    }
  }

  public String getAppliedJpql() {
    return appliedJpql;
  }

  public Var[] getAppliedParams() {
    return appliedParams;
  }

  public List<String> findSearchables(Object obj, boolean filterWithAnnotation) {
    List<String> searchable = new ArrayList<>();
    String baseDomain = obj instanceof Class ? ((Class)obj).getName() : obj.getClass().getName();
    Set<String> processed = new HashSet<>();
    findSearchables(obj, filterWithAnnotation, searchable, baseDomain, null, processed);
    return searchable;
  }

  public void findSearchables(Object obj, boolean filterWithAnnotation, List<String> searchable, String baseDomain, String baseAttribute, Set<String> processed) {
    if (baseAttribute == null)
      baseAttribute = "";

    obj = obj instanceof Class ? ((Class)obj) : obj.getClass();

    if (processed.contains(((Class)obj).getName())) {
      return;
    }

    Field[] fields = ((Class)obj).getDeclaredFields();
    EntityManager em = TransactionManager.getEntityManager((Class)obj);
    EntityType type = em.getMetamodel().entity((Class)obj);

    processed.add(((Class) obj).getName());

    for(Field f : fields) {
      boolean contains = false;
      SingularAttribute attrCurrent = null;
      for (Object attrObj : type.getAttributes()) {
        SingularAttribute attr = (SingularAttribute) attrObj;
        if (attr.getName().equalsIgnoreCase(f.getName())) {
          contains = true;
          attrCurrent = attr;
          continue;
        }
      }

      if (!contains)
        continue;

      Annotation annotation = f.getAnnotation(CronappSecurity.class);
      boolean authorized = true;
      if(annotation != null) {
        CronappSecurity security = (CronappSecurity)annotation;
        String authoritiesStr = security.filter();
        String[] authorities;
        if(authoritiesStr != null && !authoritiesStr.trim().isEmpty()) {
          authorized = false;
          authorities = authoritiesStr.trim().split(";");
          for(String role : authorities) {
            if(role.equalsIgnoreCase("authenticated")) {
              authorized = RestClient.getRestClient().getUser() != null;
              if(authorized)
                break;
            }
            if(role.equalsIgnoreCase("permitAll") || role.equalsIgnoreCase("public")) {
              authorized = true;
              break;
            }
            for(GrantedAuthority authority : RestClient.getRestClient().getAuthorities()) {
              if(role.equalsIgnoreCase(authority.getAuthority())) {
                authorized = true;
                break;
              }
            }

          }
        }
      }
      if(authorized) {
        if (filterWithAnnotation) {
          if (f.getAnnotation(CronappSecurity.class) != null)
            searchable.add(getNameWithBaseAttribute(baseAttribute, f.getName()));
        } else {
          searchable.add(getNameWithBaseAttribute(baseAttribute, f.getName()));
        }

        if (attrCurrent.isAssociation()) {
          Object association = attrCurrent.getType().getJavaType();
          findSearchables(association, filterWithAnnotation, searchable, baseDomain, getNameWithBaseAttribute(baseAttribute, f.getName()), processed);
        }
      }
    }
  }

  public String getNameWithBaseAttribute(String baseAttribute, String attribute) {
    if (baseAttribute!=null && baseAttribute.length() > 0)
      return String.format("%s.%s", baseAttribute, attribute);
    return attribute;
  }

  public void applyTo(Class domainClass, String jpql, Var[] params) {
    this.appliedParams = params;
    this.appliedJpql = jpql;

    if(items.size() == 0 && orders.size() == 0) {
      return;
    }

    String alias = "e";
    boolean hasWhere = false;
    boolean hasOrder = false;
    JPQLParser parser = JPQLParser.buildParserFor(jpql);
    parser.parse();
    if(parser.getParseTree().getQueryNode().isSelectNode()) {
      SelectNode selectNode = (SelectNode)parser.getParseTree().getQueryNode();
      if(selectNode.getSelectExpressions().size() > 0) {
        if(selectNode.getSelectExpressions().get(0) instanceof DotNode) {
          DotNode dotNode = (DotNode)selectNode.getSelectExpressions().get(0);
          alias = dotNode.getAsString();
        }

        if(selectNode.getSelectExpressions().get(0) instanceof VariableNode) {
          VariableNode dotNode = (VariableNode)selectNode.getSelectExpressions().get(0);
          alias = dotNode.getAsString();
        }
      }
    }

    if(parser.getParseTree().getWhereNode() != null) {
      hasWhere = true;
    }

    if(parser.getParseTree().getOrderByNode() != null) {
      hasOrder = true;
    }

    List<String> searchables = null;

    if(items.size() == 1 && items.get(0).key == "*") {
      searchables = findSearchables(domainClass, true);

      if(searchables.isEmpty()) {
        throw new RuntimeException(Messages.getString("notAllowed"));
      }
      else {
        Var value = items.get(0).value;
        String operation = items.get(0).operation;
        items = new LinkedList<>();
        this.type = "OR";
        for(String f : searchables) {
          items.add(new DataSourceFilterItem(f, value, type, operation, false));
        }
      }
    } else {
      searchables = findSearchables(domainClass, false);
    }

    if(items.size() > 0) {
      StringBuilder jpqlText = new StringBuilder();

      if(!hasWhere) {
        if (hasOrder) {
          int pos = jpql.indexOf("order");
          if (pos > -1){
            jpqlText.append(jpql.substring(0, pos -1));
            jpqlText.append(" %s ");
            jpqlText.append(jpql.substring(pos,jpql.length()));
            jpql = " where (";
          }
        } else {
          jpql += " where (";
        }
      }
      else {
        jpql += " AND (";
      }

      Var[] newParams = new Var[params.length + items.size()];
      for(int j = 0; j < params.length; j++) {
        newParams[j] = params[j];
      }
      int i = params.length;
      boolean add = false;
      setTypeBasedOnItemsValue();
      for(DataSourceFilterItem item : items) {
        if(add) {
          jpql += " " + type + " ";
        }
        add = true;

        if (item.dataType != null && item.dataType.equals("date")) {
          jpql += "CAST("+alias + "." + item.key + " as date) " + item.operation + " CAST(:p" + i +" as date)";
        } else {
          if (item.caseInsensitive) {
            jpql += "LOWER(" + alias + "." + item.key + ") " + item.operation + " :p" + i;
          } else {
            jpql += alias + "." + item.key + " " + item.operation + " :p" + i;
          }
        }

        newParams[i] = item.value;
        i++;

        if(!searchables.contains(item.key)) {
          throw new RuntimeException(Messages.getString("notAllowed"));
        }
      }

      jpql += ")";

      if ((!hasWhere) && (hasOrder) && (jpqlText != null)) {
        jpql = String.format(jpqlText.toString(), jpql);
      }

      this.appliedParams = newParams;
    }

    if(orders.size() > 0) {
      if(!hasOrder) {
        jpql += " ORDER BY ";
      }
      else {
        jpql += ", ";
      }

      boolean add = false;
      for(DataSourceOrderItem order : orders) {
        if(add) {
          jpql += ", ";
        }
        add = true;
        jpql += alias + "." + order.key + " " + order.type;
      }
    }

    this.appliedJpql = jpql;
  }

  private void setTypeBasedOnItemsValue() {
    boolean isSameValue = true;
    for(DataSourceFilterItem item : items) {
      for(DataSourceFilterItem itemToCheck : items) {
        if (!item.value.getObjectAsString().equals(itemToCheck.value.getObjectAsString())) {
          isSameValue = false;
          break;
        }
      }
      break;
    }
    if (isSameValue)
      this.type = "or";
    else
      this.type = "and";

  }

  public static class DataSourceFilterItem {
    public String key;
    public Var value;
    public String operation = "=";
    public String dataType = "text";
    public boolean caseInsensitive = false;

    public DataSourceFilterItem(String key, Var value, String operation, String dataType, boolean caseInsensitive) {
      this.key = key;
      this.value = value;

      if (dataType.equals("text") && caseInsensitive) {
        this.value = Var.valueOf(this.value.getObjectAsString().toLowerCase());
        this.caseInsensitive = true;
      }

      if(operation.equalsIgnoreCase("=") || operation.equalsIgnoreCase("like") || operation.equalsIgnoreCase(">")
          || operation.equalsIgnoreCase("<")  || operation.equalsIgnoreCase(">=")  || operation.equalsIgnoreCase("<=")) {
        this.operation = operation;
      }
      this.dataType = dataType;
    }
  }

  public static class DataSourceOrderItem {
    public String key;
    public String type = "ASC";

    public DataSourceOrderItem(String key, String type) {
      this.key = key;
      if(type.equalsIgnoreCase("asc") || type.equalsIgnoreCase("desc"))
        this.type = type;
    }
  }
}


text:
#define CATCH_CONFIG_MAIN
#include "catch2/catch.hpp"

#include "lluvia/core.h"
#include <cstdint>
#include <iostream>

#include "tools/cpp/runfiles/runfiles.h"
using bazel::tools::cpp::runfiles::Runfiles;

TEST_CASE("BufferAssignment", "test_ComputeNode")
{

    auto error    = std::string {};
    auto runfiles = Runfiles::CreateForTest(&error);
    REQUIRE(runfiles != nullptr);

    constexpr const size_t length = 128;
    constexpr const size_t size   = sizeof(float);

    using memflags = ll::MemoryPropertyFlagBits;

    auto session = ll::Session::create(ll::SessionDescriptor().enableDebug(true));
    REQUIRE(session != nullptr);

    const auto hostMemFlags = memflags::HostVisible | memflags::HostCoherent;
    auto       hostMemory   = session->createMemory(hostMemFlags, length * size, false);
    REQUIRE(hostMemory != nullptr);

    auto buffer = hostMemory->createBuffer(length * sizeof(float));
    REQUIRE(buffer != nullptr);

    auto program = session->createProgram(runfiles->Rlocation("lluvia/lluvia/cpp/core/test/glsl/assign.comp.spv"));
    REQUIRE(program != nullptr);

    auto nodeDescriptor = ll::ComputeNodeDescriptor()
                              .setProgram(program)
                              .setFunctionName("main")
                              .setLocalX(length)
                              .addPort({0, "out_buffer", ll::PortDirection::Out, ll::PortType::Buffer});

    // at this point, the node's port binding table and
    // vulkan descriptor set is created. So, it is possible
    // to bind objects to the ports before calling node->init()
    auto node = session->createComputeNode(nodeDescriptor);
    REQUIRE(node != nullptr);

    node->bind("out_buffer", buffer);
    node->init();

    auto cmdBuffer = session->createCommandBuffer();
    REQUIRE(cmdBuffer != nullptr);

    cmdBuffer->begin();
    cmdBuffer->run(*node);
    cmdBuffer->end();

    session->run(*cmdBuffer);

    {
        auto bufferMap = buffer->map<float[]>();
        for (auto i = 0u; i < length; ++i) {
            REQUIRE(bufferMap[i] == static_cast<float>(i));
        }
    } // unamp bufferMap

    REQUIRE_FALSE(session->hasReceivedVulkanWarningMessages());
}

TEST_CASE("ConstructWithInterpreter", "test_ComputeNode")
{

    auto error    = std::string {};
    auto runfiles = Runfiles::CreateForTest(&error);
    REQUIRE(runfiles != nullptr);

    using memflags = ll::MemoryPropertyFlagBits;

    auto session = ll::Session::create(ll::SessionDescriptor().enableDebug(true));
    REQUIRE(session != nullptr);

    const auto hostMemFlags = memflags::HostVisible | memflags::HostCoherent;
    auto       hostMemory   = session->createMemory(hostMemFlags, 1024 * 4, false);
    REQUIRE(hostMemory != nullptr);

    const auto bufferSize = 128;
    auto       buffer     = hostMemory->createBuffer(bufferSize * sizeof(float));
    REQUIRE(buffer != nullptr);

    auto program = session->createProgram(runfiles->Rlocation("lluvia/lluvia/cpp/core/test/glsl/assign.comp.spv"));
    REQUIRE(program != nullptr);

    session->setProgram("assign.comp", program);

    // register the node builder
    session->script(R"(
local builder = ll.class(ll.ComputeNodeBuilder)
builder.name = 'assign'

function builder.newDescriptor()

    local desc = ll.ComputeNodeDescriptor.new()

    desc.builderName  = 'assign'
    desc.localShape   = ll.vec3ui.new(32, 32, 1)
    desc.gridShape    = ll.vec3ui.new(1, 1, 1)
    desc.program      = ll.getProgram('assign.comp')
    desc.functionName = 'main'

    desc:addPort(ll.PortDescriptor.new(0, 'out_buffer', ll.PortDirection.Out, ll.PortType.Buffer))

    return desc
end

function builder.onNodeInit(node)

    -- configure gridShape given the size of out_buffer
    local out_buffer = node:getPort('out_buffer')

    local N = out_buffer.size // 4
    node:configureGridShape(ll.vec3ui.new(N, 1, 1))

end

ll.registerNodeBuilder(builder)
        )");

    auto desc = session->createComputeNodeDescriptor("assign");

    std::cout << "functionName: " << desc.getFunctionName() << std::endl;
    std::cout << "builderName: " << desc.getBuilderName() << std::endl;
    std::cout << "local: " << desc.getLocalX() << ", " << desc.getLocalY() << ", " << desc.getLocalZ() << std::endl;
    std::cout << "grid: " << desc.getGridX() << ", " << desc.getGridY() << ", " << desc.getGridZ() << std::endl;

    auto node = session->createComputeNode(desc);
    REQUIRE(node != nullptr);

    node->bind("out_buffer", buffer);
    node->init();

    std::cout << "node grid: " << node->getGridX() << ", " << node->getGridY() << ", " << node->getGridZ() << std::endl;

    auto cmdBuffer = session->createCommandBuffer();

    cmdBuffer->begin();
    cmdBuffer->run(*node);
    cmdBuffer->end();

    session->run(*cmdBuffer);

    {
        auto bufferMap = buffer->map<float[]>();
        for (auto i = 0u; i < bufferSize; ++i) {
            REQUIRE(bufferMap[i] == static_cast<float>(i));
        }
    } // unamp bufferMap

    REQUIRE_FALSE(session->hasReceivedVulkanWarningMessages());
}

redpajama_set_name: RedPajamaGithub


text:
package org.apache.lucene.util;

import java.io.IOException;

import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.analysis.MockAnalyzer;
import org.apache.lucene.analysis.MockTokenizer;
import org.apache.lucene.analysis.TokenFilter;
import org.apache.lucene.analysis.TokenStream;
import org.apache.lucene.analysis.Tokenizer;
import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
import org.apache.lucene.analysis.tokenattributes.PositionIncrementAttribute;
import org.apache.lucene.index.Term;
import org.apache.lucene.search.BooleanClause;
import org.apache.lucene.search.BooleanQuery;
import org.apache.lucene.search.MultiPhraseQuery;
import org.apache.lucene.search.PhraseQuery;
import org.apache.lucene.search.Query;
import org.apache.lucene.search.TermQuery;
import org.apache.lucene.util.automaton.CharacterRunAutomaton;
import org.apache.lucene.util.automaton.RegExp;

public class TestQueryBuilder extends LuceneTestCase {

  public void testTerm() {
    TermQuery expected = new TermQuery(new Term("field", "test"));
    QueryBuilder builder = new QueryBuilder(new MockAnalyzer(random()));
    assertEquals(expected, builder.createBooleanQuery("field", "test"));
  }

  public void testBoolean() {
    BooleanQuery.Builder expected = new BooleanQuery.Builder();
    expected.add(new TermQuery(new Term("field", "foo")), BooleanClause.Occur.SHOULD);
    expected.add(new TermQuery(new Term("field", "bar")), BooleanClause.Occur.SHOULD);
    QueryBuilder builder = new QueryBuilder(new MockAnalyzer(random()));
    assertEquals(expected.build(), builder.createBooleanQuery("field", "foo bar"));
  }

  public void testBooleanMust() {
    BooleanQuery.Builder expected = new BooleanQuery.Builder();
    expected.add(new TermQuery(new Term("field", "foo")), BooleanClause.Occur.MUST);
    expected.add(new TermQuery(new Term("field", "bar")), BooleanClause.Occur.MUST);
    QueryBuilder builder = new QueryBuilder(new MockAnalyzer(random()));
    assertEquals(expected.build(), builder.createBooleanQuery("field", "foo bar", BooleanClause.Occur.MUST));
  }

  public void testMinShouldMatchNone() {
    QueryBuilder builder = new QueryBuilder(new MockAnalyzer(random()));
    assertEquals(builder.createBooleanQuery("field", "one two three four"),
                 builder.createMinShouldMatchQuery("field", "one two three four", 0f));
  }

  public void testMinShouldMatchAll() {
    QueryBuilder builder = new QueryBuilder(new MockAnalyzer(random()));
    assertEquals(builder.createBooleanQuery("field", "one two three four", BooleanClause.Occur.MUST),
                 builder.createMinShouldMatchQuery("field", "one two three four", 1f));
  }

  public void testMinShouldMatch() {
    BooleanQuery.Builder expectedB = new BooleanQuery.Builder();
    expectedB.add(new TermQuery(new Term("field", "one")), BooleanClause.Occur.SHOULD);
    expectedB.add(new TermQuery(new Term("field", "two")), BooleanClause.Occur.SHOULD);
    expectedB.add(new TermQuery(new Term("field", "three")), BooleanClause.Occur.SHOULD);
    expectedB.add(new TermQuery(new Term("field", "four")), BooleanClause.Occur.SHOULD);
    expectedB.setMinimumNumberShouldMatch(0);
    Query expected = expectedB.build();

    QueryBuilder builder = new QueryBuilder(new MockAnalyzer(random()));
    //assertEquals(expected, builder.createMinShouldMatchQuery("field", "one two three four", 0.1f));
    //assertEquals(expected, builder.createMinShouldMatchQuery("field", "one two three four", 0.24f));

    expectedB.setMinimumNumberShouldMatch(1);
    expected = expectedB.build();
    assertEquals(expected, builder.createMinShouldMatchQuery("field", "one two three four", 0.25f));
    assertEquals(expected, builder.createMinShouldMatchQuery("field", "one two three four", 0.49f));

    expectedB.setMinimumNumberShouldMatch(2);
    expected = expectedB.build();
    assertEquals(expected, builder.createMinShouldMatchQuery("field", "one two three four", 0.5f));
    assertEquals(expected, builder.createMinShouldMatchQuery("field", "one two three four", 0.74f));

    expectedB.setMinimumNumberShouldMatch(3);
    expected = expectedB.build();
    assertEquals(expected, builder.createMinShouldMatchQuery("field", "one two three four", 0.75f));
    assertEquals(expected, builder.createMinShouldMatchQuery("field", "one two three four", 0.99f));
  }

  public void testPhraseQueryPositionIncrements() throws Exception {
    PhraseQuery.Builder pqBuilder = new PhraseQuery.Builder();
    pqBuilder.add(new Term("field", "1"), 0);
    pqBuilder.add(new Term("field", "2"), 2);
    PhraseQuery expected = pqBuilder.build();
    CharacterRunAutomaton stopList = new CharacterRunAutomaton(new RegExp("[sS][tT][oO][pP]").toAutomaton());

    Analyzer analyzer = new MockAnalyzer(random(), MockTokenizer.WHITESPACE, false, stopList);

    QueryBuilder builder = new QueryBuilder(analyzer);
    assertEquals(expected, builder.createPhraseQuery("field", "1 stop 2"));
  }

  public void testEmpty() {
    QueryBuilder builder = new QueryBuilder(new MockAnalyzer(random()));
    assertNull(builder.createBooleanQuery("field", ""));
  }

  /** adds synonym of "dog" for "dogs". */
  static class MockSynonymAnalyzer extends Analyzer {
    @Override
    protected TokenStreamComponents createComponents(String fieldName) {
      MockTokenizer tokenizer = new MockTokenizer();
      return new TokenStreamComponents(tokenizer, new MockSynonymFilter(tokenizer));
    }
  }

  /**
   * adds synonym of "dog" for "dogs".
   */
  protected static class MockSynonymFilter extends TokenFilter {
    CharTermAttribute termAtt = addAttribute(CharTermAttribute.class);
    PositionIncrementAttribute posIncAtt = addAttribute(PositionIncrementAttribute.class);
    boolean addSynonym = false;

    public MockSynonymFilter(TokenStream input) {
      super(input);
    }

    @Override
    public final boolean incrementToken() throws IOException {
      if (addSynonym) { // inject our synonym
        clearAttributes();
        termAtt.setEmpty().append("dog");
        posIncAtt.setPositionIncrement(0);
        addSynonym = false;
        return true;
      }

      if (input.incrementToken()) {
        addSynonym = termAtt.toString().equals("dogs");
        return true;
      } else {
        return false;
      }
    }
  }

  /** simple synonyms test */
  public void testSynonyms() throws Exception {
    BooleanQuery.Builder expectedB = new BooleanQuery.Builder();
    expectedB.setDisableCoord(true);
    expectedB.add(new TermQuery(new Term("field", "dogs")), BooleanClause.Occur.SHOULD);
    expectedB.add(new TermQuery(new Term("field", "dog")), BooleanClause.Occur.SHOULD);
    Query expected = expectedB.build();
    QueryBuilder builder = new QueryBuilder(new MockSynonymAnalyzer());
    assertEquals(expected, builder.createBooleanQuery("field", "dogs"));
    assertEquals(expected, builder.createPhraseQuery("field", "dogs"));
    assertEquals(expected, builder.createBooleanQuery("field", "dogs", BooleanClause.Occur.MUST));
    assertEquals(expected, builder.createPhraseQuery("field", "dogs"));
  }

  /** forms multiphrase query */
  public void testSynonymsPhrase() throws Exception {
    MultiPhraseQuery expected = new MultiPhraseQuery();
    expected.add(new Term("field", "old"));
    expected.add(new Term[] { new Term("field", "dogs"), new Term("field", "dog") });
    QueryBuilder builder = new QueryBuilder(new MockSynonymAnalyzer());
    assertEquals(expected, builder.createPhraseQuery("field", "old dogs"));
  }

  protected static class SimpleCJKTokenizer extends Tokenizer {
    private CharTermAttribute termAtt = addAttribute(CharTermAttribute.class);

    public SimpleCJKTokenizer() {
      super();
    }

    @Override
    public final boolean incrementToken() throws IOException {
      int ch = input.read();
      if (ch < 0)
        return false;
      clearAttributes();
      termAtt.setEmpty().append((char) ch);
      return true;
    }
  }

  private class SimpleCJKAnalyzer extends Analyzer {
    @Override
    public TokenStreamComponents createComponents(String fieldName) {
      return new TokenStreamComponents(new SimpleCJKTokenizer());
    }
  }

  public void testCJKTerm() throws Exception {
    // individual CJK chars as terms
    SimpleCJKAnalyzer analyzer = new SimpleCJKAnalyzer();

    BooleanQuery.Builder expected = new BooleanQuery.Builder();
    expected.add(new TermQuery(new Term("field", "中")), BooleanClause.Occur.SHOULD);
    expected.add(new TermQuery(new Term("field", "国")), BooleanClause.Occur.SHOULD);

    QueryBuilder builder = new QueryBuilder(analyzer);
    assertEquals(expected.build(), builder.createBooleanQuery("field", "中国"));
  }

  public void testCJKPhrase() throws Exception {
    // individual CJK chars as terms
    SimpleCJKAnalyzer analyzer = new SimpleCJKAnalyzer();

    PhraseQuery expected = new PhraseQuery("field", "中", "国");

    QueryBuilder builder = new QueryBuilder(analyzer);
    assertEquals(expected, builder.createPhraseQuery("field", "中国"));
  }

  public void testCJKSloppyPhrase() throws Exception {
    // individual CJK chars as terms
    SimpleCJKAnalyzer analyzer = new SimpleCJKAnalyzer();

    PhraseQuery expected = new PhraseQuery(3, "field", "中", "国");

    QueryBuilder builder = new QueryBuilder(analyzer);
    assertEquals(expected, builder.createPhraseQuery("field", "中国", 3));
  }

  /**
   * adds synonym of "國" for "国".
   */
  protected static class MockCJKSynonymFilter extends TokenFilter {
    CharTermAttribute termAtt = addAttribute(CharTermAttribute.class);
    PositionIncrementAttribute posIncAtt = addAttribute(PositionIncrementAttribute.class);
    boolean addSynonym = false;

    public MockCJKSynonymFilter(TokenStream input) {
      super(input);
    }

    @Override
    public final boolean incrementToken() throws IOException {
      if (addSynonym) { // inject our synonym
        clearAttributes();
        termAtt.setEmpty().append("國");
        posIncAtt.setPositionIncrement(0);
        addSynonym = false;
        return true;
      }

      if (input.incrementToken()) {
        addSynonym = termAtt.toString().equals("国");
        return true;
      } else {
        return false;
      }
    }
  }

  static class MockCJKSynonymAnalyzer extends Analyzer {
    @Override
    protected TokenStreamComponents createComponents(String fieldName) {
      Tokenizer tokenizer = new SimpleCJKTokenizer();
      return new TokenStreamComponents(tokenizer, new MockCJKSynonymFilter(tokenizer));
    }
  }

  /** simple CJK synonym test */
  public void testCJKSynonym() throws Exception {
    BooleanQuery.Builder expected = new BooleanQuery.Builder();
    expected.setDisableCoord(true);
    expected.add(new TermQuery(new Term("field", "国")), BooleanClause.Occur.SHOULD);
    expected.add(new TermQuery(new Term("field", "國")), BooleanClause.Occur.SHOULD);
    QueryBuilder builder = new QueryBuilder(new MockCJKSynonymAnalyzer());
    assertEquals(expected.build(), builder.createBooleanQuery("field", "国"));
    assertEquals(expected.build(), builder.createPhraseQuery("field", "国"));
    assertEquals(expected.build(), builder.createBooleanQuery("field", "国", BooleanClause.Occur.MUST));
  }

  /** synonyms with default OR operator */
  public void testCJKSynonymsOR() throws Exception {
    BooleanQuery.Builder expected = new BooleanQuery.Builder();
    expected.add(new TermQuery(new Term("field", "中")), BooleanClause.Occur.SHOULD);
    BooleanQuery.Builder inner = new BooleanQuery.Builder();
    inner.setDisableCoord(true);
    inner.add(new TermQuery(new Term("field", "国")), BooleanClause.Occur.SHOULD);
    inner.add(new TermQuery(new Term("field", "國")), BooleanClause.Occur.SHOULD);
    expected.add(inner.build(), BooleanClause.Occur.SHOULD);
    QueryBuilder builder = new QueryBuilder(new MockCJKSynonymAnalyzer());
    assertEquals(expected.build(), builder.createBooleanQuery("field", "中国"));
  }

  /** more complex synonyms with default OR operator */
  public void testCJKSynonymsOR2() throws Exception {
    BooleanQuery.Builder expected = new BooleanQuery.Builder();
    expected.add(new TermQuery(new Term("field", "中")), BooleanClause.Occur.SHOULD);
    BooleanQuery.Builder inner = new BooleanQuery.Builder();
    inner.setDisableCoord(true);
    inner.add(new TermQuery(new Term("field", "国")), BooleanClause.Occur.SHOULD);
    inner.add(new TermQuery(new Term("field", "國")), BooleanClause.Occur.SHOULD);
    expected.add(inner.build(), BooleanClause.Occur.SHOULD);
    BooleanQuery.Builder inner2 = new BooleanQuery.Builder();
    inner2.setDisableCoord(true);
    inner2.add(new TermQuery(new Term("field", "国")), BooleanClause.Occur.SHOULD);
    inner2.add(new TermQuery(new Term("field", "國")), BooleanClause.Occur.SHOULD);
    expected.add(inner2.build(), BooleanClause.Occur.SHOULD);
    QueryBuilder builder = new QueryBuilder(new MockCJKSynonymAnalyzer());
    assertEquals(expected.build(), builder.createBooleanQuery("field", "中国国"));
  }

  /** synonyms with default AND operator */
  public void testCJKSynonymsAND() throws Exception {
    BooleanQuery.Builder expected = new BooleanQuery.Builder();
    expected.add(new TermQuery(new Term("field", "中")), BooleanClause.Occur.MUST);
    BooleanQuery.Builder inner = new BooleanQuery.Builder();
    inner.setDisableCoord(true);
    inner.add(new TermQuery(new Term("field", "国")), BooleanClause.Occur.SHOULD);
    inner.add(new TermQuery(new Term("field", "國")), BooleanClause.Occur.SHOULD);
    expected.add(inner.build(), BooleanClause.Occur.MUST);
    QueryBuilder builder = new QueryBuilder(new MockCJKSynonymAnalyzer());
    assertEquals(expected.build(), builder.createBooleanQuery("field", "中国", BooleanClause.Occur.MUST));
  }

  /** more complex synonyms with default AND operator */
  public void testCJKSynonymsAND2() throws Exception {
    BooleanQuery.Builder expected = new BooleanQuery.Builder();
    expected.add(new TermQuery(new Term("field", "中")), BooleanClause.Occur.MUST);
    BooleanQuery.Builder inner = new BooleanQuery.Builder();
    inner.setDisableCoord(true);
    inner.add(new TermQuery(new Term("field", "国")), BooleanClause.Occur.SHOULD);
    inner.add(new TermQuery(new Term("field", "國")), BooleanClause.Occur.SHOULD);
    expected.add(inner.build(), BooleanClause.Occur.MUST);
    BooleanQuery.Builder inner2 = new BooleanQuery.Builder();
    inner2.setDisableCoord(true);
    inner2.add(new TermQuery(new Term("field", "国")), BooleanClause.Occur.SHOULD);
    inner2.add(new TermQuery(new Term("field", "國")), BooleanClause.Occur.SHOULD);
    expected.add(inner2.build(), BooleanClause.Occur.MUST);
    QueryBuilder builder = new QueryBuilder(new MockCJKSynonymAnalyzer());
    assertEquals(expected.build(), builder.createBooleanQuery("field", "中国国", BooleanClause.Occur.MUST));
  }

  /** forms multiphrase query */
  public void testCJKSynonymsPhrase() throws Exception {
    MultiPhraseQuery expected = new MultiPhraseQuery();
    expected.add(new Term("field", "中"));
    expected.add(new Term[] { new Term("field", "国"), new Term("field", "國")});
    QueryBuilder builder = new QueryBuilder(new MockCJKSynonymAnalyzer());
    assertEquals(expected, builder.createPhraseQuery("field", "中国"));
    expected.setSlop(3);
    assertEquals(expected, builder.createPhraseQuery("field", "中国", 3));
  }

  public void testNoTermAttribute() {
    //Can't use MockTokenizer because it adds TermAttribute and we don't want that
    Analyzer analyzer = new Analyzer() {
      @Override
      protected TokenStreamComponents createComponents(String fieldName) {
        return new TokenStreamComponents(
            new Tokenizer() {
              boolean wasReset = false;
              @Override
              public void reset() throws IOException {
                super.reset();
                assertFalse(wasReset);
                wasReset = true;
              }

              @Override
              public boolean incrementToken() throws IOException {
                assertTrue(wasReset);
                return false;
              }
            }
        );
      }
    };
    QueryBuilder builder = new QueryBuilder(analyzer);
    assertNull(builder.createBooleanQuery("field", "whatever"));
  }
}


text:
START_ATF_NAMESPACE
    struct  CNationSettingDataCN : CNationSettingData
    {
    public:
        CNationSettingDataCN();
        void ctor_CNationSettingDataCN();
        struct CBilling* CreateBilling();
        void CreateComplete(struct CPlayer* pOne);
        struct CashDbWorker* CreateWorker();
        int GetCashItemPrice(struct _CashShop_str_fld* pFld);
        char* GetItemName(struct _NameTxt_fld* pFld);
        int Init();
        void Loop();
        void NetClose(struct CPlayer* pOne);
        bool ReadSystemPass();
    };
END_ATF_NAMESPACE


text:
using System;

namespace AbstactFactory
{
    class OSXFactory : GUIFactory
    {
        public override Button createButton()
        {
            return (new OSXButton());
        }
    }

}


text:
require 'zlib'

class Game < ActiveRecord::Base
  # Plugins
  acts_as_rated
  acts_as_taggable

  # Associations
  belongs_to 	:category
  belongs_to 	:user
  has_many 		:comments, :include => :user, :dependent => :destroy
  has_many 		:admirers, :through => :favorites, :source => :user, :dependent => :destroy
  has_many 		:favorites, :dependent => :destroy
  has_and_belongs_to_many  :pages, :join_table => :pages_games

  # Bucket
  flash_bucket = Rails.env == 'production' ? 'gamegum-flash' : 'gamegum-flash-development'
  icon_bucket = Rails.env == 'production' ? 'gamegum-icons' : 'gamegum-icons-development'

  has_attached_file	:icon,
                    :styles => {
                      :original => {
                        :geometry 	=> '48x48#'
                      }
                    },
                  	:path           => ':id_original.:extension',
                  	:default_url    => '/assets/default.gif',
                  	:storage        => 's3',
                  	:s3_credentials => 'config/amazon_s3.yml',
                  	:bucket         => icon_bucket

  has_attached_file	:flash,
                  	:path			=> ':id_original.:extension',
                  	:storage        => 's3',
                  	:s3_credentials => 'config/amazon_s3.yml',
                  	:bucket         => flash_bucket

  # Callbacks
  after_create             :add_pulse
  after_flash_post_process :set_dimensions

  # Validations
  validates_presence_of				      :category, :message => 'must be submitted'
  validates_length_of				        :title, :within => 2..120
  validates_length_of				        :description, :within => 10..5000
  validates_attachment_presence     :flash
  validates_attachment_content_type	:flash, :content_type => 'application/x-shockwave-flash'
  validates_attachment_size			    :flash, :in => 1..15.megabytes

  attr_accessible :title, :description, :category_id, :tag_list, :violence, :langauge, :nudity, :touch_compatible, :language, :flash, :icon

  # Methods
  def rating_by(rater)
    r = ratings.find(:first, :conditions => ['rater_id = ?', rater.id])
    r.rating if !r.nil?
  end

  def self.find_within(within_days, options = {})
    conditions = [ "games.created_at > ?", within_days.days.ago.to_s(:db) ] unless within_days.zero?

    with_scope :find => { :conditions => conditions } do
      paginate options
    end
  end

  def to_param
    "#{id}/#{title.parameterize}"
  end

  def slug
    self.title.parameterize
  end

  def adult
    self.nudity
  end

  def to_label
    title
  end

  # PRIVATE
  private

  def add_pulse
    Pulse.create({:category => 'game', :description => self.description[0,180], :user => self.user, :game => self, :adult => self.nudity})
  end

  def set_dimensions
    begin
      stream = open(flash.queued_for_write[:original].path, 'rb')

      # Read the entire stream into memory because the
      # dimensions aren't stored in a standard location
      stream.rewind
      contents = stream.read

      # Our 'signature' is the first 3 bytes
      # Either FWS or CWS.  CWS indicates compression
      signature = contents[0..2]

      # Determine the length of the uncompressed stream
      length = contents[4..7].unpack('V').join.to_i

      # If we do, in fact, have compression
      if signature == 'CWS'
        # Decompress the body of the SWF
        begin
          zstream = Zlib::Inflate.new
          body = zstream.inflate( contents[8..length] )
          zstream.close
        rescue
          puts "ERROR: Could not inflate"
          return [0,0]
        end

        # And reconstruct the stream contents to the first 8 bytes (header)
        # Plus our decompressed body
        contents = contents[0..7] + body
      end

      # Determine the nbits of our dimensions rectangle
      nbits = contents[8].ord >> 3

      # Determine how many bits long this entire RECT structure is
      rectbits = 5 + nbits * 4    # 5 bits for nbits, as well as nbits * number of fields (4)

      # Determine how many bytes rectbits composes (ceil(rectbits/8))
      rectbytes = (rectbits.to_f / 8).ceil

      # Unpack the RECT structure from the stream in little-endian bit order, then join it into a string
      rect = contents[8..(8 + rectbytes)].unpack("#{'B8' * rectbytes}").join()
      contents = nil

      # Read in nbits incremenets starting from 5
      dimensions = Array.new
      4.times do |n|
        s = 5 + (n * nbits)     # Calculate our start index
        e = s + (nbits - 1)     # Calculate our end index
        dimensions[n] = rect[s..e].to_i(2)    # Read that range (binary) and convert it to an integer
      end

      # The values we have here are in "twips"
      # 20 twips to a pixel (that's why SWFs are fuzzy sometimes!)
      width   = (dimensions[1] - dimensions[0]) / 20
      height  = (dimensions[3] - dimensions[2]) / 20

      # If you can't figure this one out, you probably shouldn't have read this far
      self.width, self.height = [width, height]
    rescue Exception => e
      logger.error e.message
      logger.error e.backtrace.join("\n")
    end
  end
end


text:
namespace System.Web.UI.WebControls.WebParts {

    using System;
    using System.Collections;
    using System.Globalization;

    /// <devdoc>
    /// Read-only collection of WebPartZones.  Collection cannot be modified after contstruction.
    /// </devdoc>
    public sealed class WebPartZoneCollection : ReadOnlyCollectionBase {

        public WebPartZoneCollection() {
        }

        public WebPartZoneCollection(ICollection webPartZones) {
            if (webPartZones == null) {
                throw new ArgumentNullException("webPartZones");
            }

            foreach (object obj in webPartZones) {
                if (obj == null) {
                    throw new ArgumentException(SR.GetString(SR.Collection_CantAddNull), "webPartZones");
                }
                if (!(obj is WebPartZone)) {
                    throw new ArgumentException(SR.GetString(SR.Collection_InvalidType, "WebPartZone"), "webPartZones");
                }
                InnerList.Add(obj);
            }
        }

        internal int Add(WebPartZoneBase value) {
            return InnerList.Add(value);
        }

        public bool Contains(WebPartZoneBase value) {
            return InnerList.Contains(value);
        }

        public int IndexOf(WebPartZoneBase value) {
            return InnerList.IndexOf(value);
        }

        public WebPartZoneBase this[int index] {
            get {
                return (WebPartZoneBase) InnerList[index];
            }
        }

        public WebPartZoneBase this[string id] {
            get {
                WebPartZoneBase selectedZone = null;

                foreach (WebPartZoneBase zone in InnerList) {
                    if (String.Equals(zone.ID, id, StringComparison.OrdinalIgnoreCase)) {
                        selectedZone = zone;
                        break;
                    }
                }

                return selectedZone;
            }
        }

        /// <devdoc>
        /// <para>Copies contents from the collection to a specified array with a
        /// specified starting index.</para>
        /// </devdoc>
        public void CopyTo(WebPartZoneBase[] array, int index) {
            InnerList.CopyTo(array, index);
        }

    }
}


text:
package com.palantir.atlasdb.keyvalue.impl;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Future;

import com.google.common.base.Function;
import com.google.common.base.Preconditions;
import com.google.common.base.Predicate;
import com.google.common.base.Predicates;
import com.google.common.collect.AbstractIterator;
import com.google.common.collect.HashMultimap;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Multimap;
import com.google.common.collect.Ordering;
import com.google.common.collect.Sets;
import com.google.common.primitives.UnsignedBytes;
import com.google.common.util.concurrent.Futures;
import com.palantir.atlasdb.AtlasDbConstants;
import com.palantir.atlasdb.keyvalue.api.Cell;
import com.palantir.atlasdb.keyvalue.api.ColumnSelection;
import com.palantir.atlasdb.keyvalue.api.KeyValueService;
import com.palantir.atlasdb.keyvalue.api.RangeRequest;
import com.palantir.atlasdb.keyvalue.api.RowResult;
import com.palantir.atlasdb.keyvalue.api.Value;
import com.palantir.common.base.ClosableIterator;
import com.palantir.common.collect.IteratorUtils;
import com.palantir.common.concurrent.PTExecutors;
import com.palantir.util.AssertUtils;
import com.palantir.util.Pair;
import com.palantir.util.paging.SimpleTokenBackedResultsPage;
import com.palantir.util.paging.TokenBackedBasicResultsPage;

public class TieredKeyValueService implements KeyValueService {
    /**
     * We keep track of and report only the tables we're actually tiering
     * so the TieredKvsMover can know what tables need to be moved between
     * tiers.
     */
    private final Set<String> tieredTables;
    private final KeyValueService primary;
    private final KeyValueService secondary;
    private final ExecutorService executor;

    public static TieredKeyValueService create(Set<String> tieredTables,
                                               KeyValueService primary,
                                               KeyValueService secondary) {
        return create(tieredTables, primary, secondary,
                PTExecutors.newCachedThreadPool(PTExecutors.newNamedThreadFactory()));
    }

    public static TieredKeyValueService create(Set<String> tieredTables,
                                               KeyValueService primary,
                                               KeyValueService secondary,
                                               ExecutorService executor) {
        return new TieredKeyValueService(tieredTables, primary, secondary, executor);
    }

    private TieredKeyValueService(Set<String> tieredTables,
                                  KeyValueService primary,
                                  KeyValueService secondary,
                                  ExecutorService executor) {
        Set<String> badTables = Sets.intersection(AtlasDbConstants.hiddenTables, tieredTables);
        Preconditions.checkArgument(badTables.isEmpty(), "The hidden tables %s cannot be tiered.", badTables);
        this.tieredTables = ImmutableSet.copyOf(tieredTables);
        this.primary = primary;
        this.secondary = secondary;
        this.executor = executor;
    }

    /**
     * Returns the primary key value service.
     *

     * All new writes and all operations on tables that are not tiered (including system tables)
     * go only to the primary tier.
     */
    public KeyValueService getPrimaryTier() {
        return primary;
    }

    /**
     * Returns the secondary key value service.
     *

     * The secondary tier is only written to by TieredKvsMover during batch operations
     * that move the contents of tiered tables from the primary tier to the secondary tier.
     */
    public KeyValueService getSecondaryTier() {
        return secondary;
    }

    private boolean isNotTiered(String tableName) {
        if (tieredTables.isEmpty()) {
            return AtlasDbConstants.hiddenTables.contains(tableName);
        }
        return !tieredTables.contains(tableName);
    }

    @Override
    public void initializeFromFreshInstance() {
        primary.initializeFromFreshInstance();
        secondary.initializeFromFreshInstance();
    }

    @Override
    public void close() {
        primary.close();
        secondary.close();
        executor.shutdown();
    }

    @Override
    public void teardown() {
        primary.teardown();
        secondary.teardown();
        executor.shutdown();
    }

    @Override
    public Collection<? extends KeyValueService> getDelegates() {
        return ImmutableList.of(primary, secondary);
    }

    public Set<String> getTieredTablenames() {
        if (tieredTables.isEmpty()) {
            return Sets.difference(getAllTableNames(), AtlasDbConstants.hiddenTables);
        } else {
            return tieredTables;
        }
    }

    @Override
    public Map<Cell, Value> getRows(final String tableName,
                                    final Iterable<byte[]> rows,
                                    final ColumnSelection columnSelection,
                                    final long timestamp) {
        if (isNotTiered(tableName)) {
            return primary.getRows(tableName, rows, columnSelection, timestamp);
        }
        Map<Cell, Value> primaryResults = primary.getRows(tableName, rows, columnSelection, timestamp);
        Map<Cell, Value> results = Maps.newHashMap(secondary.getRows(tableName, rows, columnSelection, timestamp));
        results.putAll(primaryResults);
        return results;
    }

    @Override
    public Map<Cell, Value> get(String tableName, Map<Cell, Long> timestampByCell) {
        if (isNotTiered(tableName)) {
            return primary.get(tableName, timestampByCell);
        }
        Map<Cell, Value> results;
        Map<Cell, Value> primaryResults = primary.get(tableName, timestampByCell);
        if (primaryResults.size() == timestampByCell.size()) {
            results = primaryResults;
        } else {
            Map<Cell, Long> missingCells = Maps.newHashMapWithExpectedSize(timestampByCell.size() - primaryResults.size());
            results = Maps.newHashMapWithExpectedSize(timestampByCell.size());
            for (Entry<Cell, Long> entry : timestampByCell.entrySet()) {
                Value value = primaryResults.get(entry.getKey());
                if (value == null) {
                    missingCells.put(entry.getKey(), entry.getValue());
                } else {
                    results.put(entry.getKey(), value);
                }
            }
            results.putAll(secondary.get(tableName, missingCells));
        }
        return results;
    }

    @Override
    public Map<Cell, Long> getLatestTimestamps(String tableName, Map<Cell, Long> timestampByCell) {
        if (isNotTiered(tableName)) {
            return primary.getLatestTimestamps(tableName, timestampByCell);
        }
        Map<Cell, Long> results;
        Map<Cell, Long> primaryResults = primary.getLatestTimestamps(tableName, timestampByCell);
        if (primaryResults.size() == timestampByCell.size()) {
            results = primaryResults;
        } else {
            Map<Cell, Long> missingCells = Maps.newHashMapWithExpectedSize(timestampByCell.size() - primaryResults.size());
            results = Maps.newHashMapWithExpectedSize(timestampByCell.size());
            for (Entry<Cell, Long> entry : timestampByCell.entrySet()) {
                Long timestamp = primaryResults.get(entry.getKey());
                if (timestamp == null) {
                    missingCells.put(entry.getKey(), entry.getValue());
                } else {
                    results.put(entry.getKey(), timestamp);
                }
            }
            results.putAll(secondary.getLatestTimestamps(tableName, missingCells));
        }
        return results;
    }

    @Override
    public Multimap<Cell, Long> getAllTimestamps(final String tableName,
                                                 final Set<Cell> cells,
                                                 final long timestamp) {
        if (isNotTiered(tableName)) {
            return primary.getAllTimestamps(tableName, cells, timestamp);
        }
        Multimap<Cell, Long> primaryResults = primary.getAllTimestamps(tableName, cells, timestamp);
        Multimap<Cell, Long> results = HashMultimap.create(secondary.getAllTimestamps(tableName, cells, timestamp));
        results.putAll(primaryResults);
        return results;
    }

    @Override
    public void truncateTable(final String tableName) {
        if (isNotTiered(tableName)) {
            primary.truncateTable(tableName);
            return;
        }
        Future<?> primaryFuture = executor.submit(new Runnable() {
            @Override
            public void run() {
                primary.truncateTable(tableName);
            }
        });
        secondary.truncateTable(tableName);
        Futures.getUnchecked(primaryFuture);
    }

    @Override
    public void truncateTables(final Set<String> tableNames) {
        final Set<String> truncateOnPrimary = Sets.newHashSet();
        final Set<String> truncateOnSecondary = Sets.newHashSet();

        for (String tableName : tableNames) {
            if (isNotTiered(tableName)) {
                truncateOnPrimary.add(tableName);
            } else {
                truncateOnPrimary.add(tableName);
                truncateOnSecondary.add(tableName);
            }

            Future<?> primaryFuture = executor.submit(new Runnable() {
                @Override
                public void run() {
                    primary.truncateTables(truncateOnPrimary);
                }
            });
            secondary.truncateTables(truncateOnSecondary);
            Futures.getUnchecked(primaryFuture);
        }
    }

    @Override
    public void put(String tableName, Map<Cell, byte[]> values, long timestamp) {
        primary.put(tableName, values, timestamp);
    }

    @Override
    public void multiPut(Map<String, ? extends Map<Cell, byte[]>> valuesByTable, long timestamp) {
        primary.multiPut(valuesByTable, timestamp);
    }

    @Override
    public void putWithTimestamps(String tableName, Multimap<Cell, Value> values) {
        primary.putWithTimestamps(tableName, values);
    }

    @Override
    public void putUnlessExists(String tableName, Map<Cell, byte[]> values) {
        if (isNotTiered(tableName)) {
            primary.putUnlessExists(tableName, values);
            return;
        }
        throw new UnsupportedOperationException("TieredKeyValueService does not " +
                "support putUnlessExists on tiered tables. tableName=" + tableName + ".");
    }

    @Override
    public void delete(final String tableName, final Multimap<Cell, Long> keys) {
        if (isNotTiered(tableName)) {
            primary.delete(tableName, keys);
            return;
        }
        Future<?> primaryFuture = executor.submit(new Runnable() {
            @Override
            public void run() {
                primary.delete(tableName, keys);
            }
        });
        secondary.delete(tableName, keys);
        Futures.getUnchecked(primaryFuture);
    }

    @Override
    public ClosableIterator<RowResult<Value>> getRange(final String tableName,
                                                       final RangeRequest rangeRequest,
                                                       final long timestamp) {
        if (isNotTiered(tableName)) {
            return primary.getRange(tableName, rangeRequest, timestamp);
        }
        ClosableIterator<RowResult<Value>> primaryIter = primary.getRange(tableName, rangeRequest, timestamp);
        return new ClosableMergedIterator<Value>(rangeRequest, primaryIter,
                new Function<RangeRequest, ClosableIterator<RowResult<Value>>>() {
                    @Override
                    public ClosableIterator<RowResult<Value>> apply(RangeRequest request) {
                        return secondary.getRange(tableName, request, timestamp);
                    }});
    }

    @Override
    public ClosableIterator<RowResult<Set<Long>>> getRangeOfTimestamps(final String tableName,
                                                                       final RangeRequest rangeRequest,
                                                                       final long timestamp) {
        if (isNotTiered(tableName)) {
            return primary.getRangeOfTimestamps(tableName, rangeRequest, timestamp);
        }
        ClosableIterator<RowResult<Set<Long>>> primaryIter = primary.getRangeOfTimestamps(tableName, rangeRequest, timestamp);
        return new ClosableMergedIterator<Set<Long>>(rangeRequest, primaryIter,
                new Function<RangeRequest, ClosableIterator<RowResult<Set<Long>>>>() {
                    @Override
                    public ClosableIterator<RowResult<Set<Long>>> apply(RangeRequest request) {
                        return secondary.getRangeOfTimestamps(tableName, request, timestamp);
                    }});
    }

    @Override
    public ClosableIterator<RowResult<Set<Value>>> getRangeWithHistory(final String tableName,
                                                                       final RangeRequest rangeRequest,
                                                                       final long timestamp) {
        if (isNotTiered(tableName)) {
            return primary.getRangeWithHistory(tableName, rangeRequest, timestamp);
        }
        ClosableIterator<RowResult<Set<Value>>> primaryIter = primary.getRangeWithHistory(tableName, rangeRequest, timestamp);
        return new ClosableMergedIterator<Set<Value>>(rangeRequest, primaryIter,
                new Function<RangeRequest, ClosableIterator<RowResult<Set<Value>>>>() {
                    @Override
                    public ClosableIterator<RowResult<Set<Value>>> apply(RangeRequest request) {
                        return secondary.getRangeWithHistory(tableName, request, timestamp);
                    }});
    }

    @Override
    public Map<RangeRequest, TokenBackedBasicResultsPage<RowResult<Value>, byte[]>>
            getFirstBatchForRanges(final String tableName,
                                   final Iterable<RangeRequest> rangeRequests,
                                   final long timestamp) {
        if (isNotTiered(tableName)) {
            return primary.getFirstBatchForRanges(tableName, rangeRequests, timestamp);
        }
        Map<RangeRequest, TokenBackedBasicResultsPage<RowResult<Value>, byte[]>> primaryResults =
                primary.getFirstBatchForRanges(tableName, rangeRequests, timestamp);
        Map<RangeRequest, TokenBackedBasicResultsPage<RowResult<Value>, byte[]>> secondaryResults =
                secondary.getFirstBatchForRanges(tableName, rangeRequests, timestamp);
        Map<RangeRequest, TokenBackedBasicResultsPage<RowResult<Value>, byte[]>> results =
                Maps.newHashMapWithExpectedSize(primaryResults.size());
        for (Entry<RangeRequest, TokenBackedBasicResultsPage<RowResult<Value>, byte[]>> entry : primaryResults.entrySet()) {
            RangeRequest rangeRequest = entry.getKey();
            boolean isReversed = rangeRequest.isReverse();
            TokenBackedBasicResultsPage<RowResult<Value>, byte[]> primaryPage = entry.getValue();
            TokenBackedBasicResultsPage<RowResult<Value>, byte[]> secondaryPage = secondaryResults.get(rangeRequest);
            boolean moreAvailable = primaryPage.moreResultsAvailable() || secondaryPage.moreResultsAvailable();
            byte[] pageToken = getNextPageToken(primaryPage, secondaryPage, isReversed);
            Predicate<RowResult<Value>> limiter = getLimitingPredicate(pageToken, isReversed, moreAvailable);
            Iterable<RowResult<Value>> pageResults = getMergedPageResults(primaryPage, secondaryPage, limiter, isReversed);
            results.put(rangeRequest, SimpleTokenBackedResultsPage.create(pageToken, pageResults, moreAvailable));
        }
        return results;
    }

    /**
     * Returns the smaller of the page tokens from the given pages (or greater if isReversed).
     */
    private byte[] getNextPageToken(TokenBackedBasicResultsPage<RowResult<Value>, byte[]> primaryPage,
                                    TokenBackedBasicResultsPage<RowResult<Value>, byte[]> secondaryPage,
                                    boolean isReversed) {
        if (!primaryPage.moreResultsAvailable()) {
            return secondaryPage.getTokenForNextPage();
        } else if (!secondaryPage.moreResultsAvailable()) {
            return primaryPage.getTokenForNextPage();
        } else {
            if (compare(primaryPage.getTokenForNextPage(), secondaryPage.getTokenForNextPage(), isReversed) < 0) {
                return primaryPage.getTokenForNextPage();
            } else {
                return secondaryPage.getTokenForNextPage();
            }
        }
    }

    /**
     * Returns a predicate accepting only row results with row names less than or equal to the given
     * page token (or greater than or equal if isReversed).
     */
    private Predicate<RowResult<Value>> getLimitingPredicate(final byte[] pageToken,
                                                             final boolean isReversed,
                                                             boolean moreAvailable) {
        if (!moreAvailable) {
            return Predicates.alwaysTrue();
        }
        return new Predicate<RowResult<Value>>() {
            @Override
            public boolean apply(RowResult<Value> rowResult) {
                return compare(rowResult.getRowName(), pageToken, isReversed) <= 0;
            }
        };
    }

    /**
     * Return a lexicographical comparison of the byte arrays, reversing the results if
     * reverseOrdering is true.
     */
    private static int compare(byte[] first, byte[] second, boolean reverseOrdering) {
        int comparison = UnsignedBytes.lexicographicalComparator().compare(first, second);
        if (reverseOrdering) {
            return -comparison;
        } else {
            return comparison;
        }
    }

    /**
     * Returns the merged page results from both pages in the proper order, limited by the given predicate.
     */
    private Iterable<RowResult<Value>> getMergedPageResults(
            final TokenBackedBasicResultsPage<RowResult<Value>, byte[]> primaryPage,
            final TokenBackedBasicResultsPage<RowResult<Value>, byte[]> secondaryPage,
            final Predicate<RowResult<Value>> limiter,
            final boolean isReversed) {
        return new Iterable<RowResult<Value>>() {
            @Override
            public Iterator<RowResult<Value>> iterator() {
                return mergeIterators(takeWhile(primaryPage.getResults().iterator(), limiter),
                        takeWhile(secondaryPage.getResults().iterator(), limiter), isReversed);
            }
        };
    }

    private static <T> Iterator<RowResult<T>> mergeIterators(Iterator<RowResult<T>> primaryIter,
                                                             Iterator<RowResult<T>> secondaryIter,
                                                             boolean isReversed) {
        Ordering<RowResult<T>> comparator = RowResult.getOrderingByRowName();
        if (isReversed) {
            comparator = comparator.reverse();
        }
        return IteratorUtils.mergeIterators(
                primaryIter,
                secondaryIter,
                comparator,
                new Function<Pair<RowResult<T>, RowResult<T>>, RowResult<T>>() {
                    @Override
                    public RowResult<T> apply(Pair<RowResult<T>, RowResult<T>> rows) {
                        RowResult<T> primaryResult = rows.getLhSide();
                        RowResult<T> secondaryResult = rows.getRhSide();
                        for (Entry<byte[], T> entry : primaryResult.getColumns().entrySet()) {
                            T secondaryValue = secondaryResult.getColumns().get(entry.getKey());
                            if (secondaryValue instanceof Value) {
                                long primaryTimestamp = ((Value)entry.getValue()).getTimestamp();
                                long secondaryTimestamp = ((Value)secondaryValue).getTimestamp();
                                AssertUtils.assertAndLog(primaryTimestamp >= secondaryTimestamp,
                                        "The secondary kvs has a row with timestamp %s, while the " +
                                        "same row in the primary has timestamp %s. This should be " +
                                        "extremely uncommon.",
                                        secondaryTimestamp, primaryTimestamp);
                            }
                        }
                        // Order is important here, overwrite results from the
                        // secondary tier with results from the primary tier.
                        return RowResults.merge(secondaryResult, primaryResult);
                    }
                });
    }

    /**
     * Returns an iterator that returns elements from the delegate until the predicate returns false.
     */
    private static <T> Iterator<T> takeWhile(final Iterator<T> delegate, final Predicate<T> predicate) {
        return new AbstractIterator<T>() {
            @Override
            protected T computeNext() {
                if (!delegate.hasNext()) {
                    return endOfData();
                }
                T next = delegate.next();
                if (predicate.apply(next)) {
                    return next;
                }
                return endOfData();
            }
        };
    }

    @Override
    public void dropTable(final String tableName) {
        dropTables(ImmutableSet.of(tableName));
    }

    @Override
    public void dropTables(Set<String> tableNames) {
        Map<KeyValueService, Set<String>> tableNamesPerDelegate = Maps.newHashMapWithExpectedSize(2);
        for (String tableName : tableNames) {
            Set<String> splitTableNames;

            // always place in primary
            if (tableNamesPerDelegate.containsKey(primary)) {
                splitTableNames = tableNamesPerDelegate.get(primary);
            } else {
                splitTableNames = Sets.newHashSet();
            }
            splitTableNames.add(tableName);
            tableNamesPerDelegate.put(primary, splitTableNames);

            if (!isNotTiered(tableName)) { // if tiered also place in secondary
                if (tableNamesPerDelegate.containsKey(secondary)) {
                    splitTableNames = tableNamesPerDelegate.get(secondary);
                } else {
                    splitTableNames = Sets.newHashSet();
                }
                splitTableNames.add(tableName);
                tableNamesPerDelegate.put(secondary, splitTableNames);
            }
        }

        List<Future<?>> futures = Lists.newArrayListWithExpectedSize(2);
        for (final Entry<KeyValueService, Set<String>> tableNamesPerKVS : tableNamesPerDelegate.entrySet()) {
            futures.add(executor.submit(new Runnable() {
                @Override
                public void run() {
                    tableNamesPerKVS.getKey().dropTables(tableNamesPerKVS.getValue());
                }
            }));
        }

        for (Future<?> future : futures) {
            Futures.getUnchecked(future);
        }
    }

    @Override
    public void createTable(final String tableName, final int maxValueSizeInBytes) {
        if (isNotTiered(tableName)) {
            primary.createTable(tableName, maxValueSizeInBytes);
            return;
        }
        primary.createTable(tableName, maxValueSizeInBytes);
        secondary.createTable(tableName, maxValueSizeInBytes);
    }

    @Override
    public void createTables(Map<String, Integer> tableNamesToMaxValueSizeInBytes) {
        Map<KeyValueService, Map<String, Integer>> delegateToTablenameMaxValueSize = Maps.newHashMapWithExpectedSize(2);
        for (Entry<String, Integer> tableEntry : tableNamesToMaxValueSizeInBytes.entrySet()) {
            String tableName = tableEntry.getKey();
            int maxValueSize = tableEntry.getValue();
            Map<String, Integer> splitTableToValueSize = ImmutableMap.of();

            // always place in primary
            if (delegateToTablenameMaxValueSize.containsKey(primary)) {
                splitTableToValueSize = delegateToTablenameMaxValueSize.get(primary);
            } else {
                splitTableToValueSize = Maps.newHashMap();
            }
            splitTableToValueSize.put(tableName, maxValueSize);
            delegateToTablenameMaxValueSize.put(primary, splitTableToValueSize);

            if (!isNotTiered(tableName)) { // if tiered also place in secondary
                if (delegateToTablenameMaxValueSize.containsKey(secondary)) {
                    splitTableToValueSize = delegateToTablenameMaxValueSize.get(secondary);
                } else {
                    splitTableToValueSize = Maps.newHashMap();
                }
                splitTableToValueSize.put(tableName, maxValueSize);
                delegateToTablenameMaxValueSize.put(secondary, splitTableToValueSize);
            }
        }

        for (KeyValueService kvs : delegateToTablenameMaxValueSize.keySet()) {
            kvs.createTables(delegateToTablenameMaxValueSize.get(kvs));
        }
    }

    @Override
    public Set<String> getAllTableNames() {
        return primary.getAllTableNames();
    }

    @Override
    public byte[] getMetadataForTable(String tableName) {
        return primary.getMetadataForTable(tableName);
    }

    @Override
    public Map<String, byte[]> getMetadataForTables() {
        return primary.getMetadataForTables();
    }

    @Override
    public void putMetadataForTable(final String tableName, final byte[] metadata) {
        if (isNotTiered(tableName)) {
            primary.putMetadataForTable(tableName, metadata);
            return;
        }
        primary.putMetadataForTable(tableName, metadata);
        secondary.putMetadataForTable(tableName, metadata);
    }

    @Override
    public void putMetadataForTables(Map<String, byte[]> tableNameToMetadata) {
        Map<KeyValueService, Map<String, byte[]>> delegateToTablenameToMetadata = Maps.newHashMapWithExpectedSize(2);
        for (Entry<String, byte[]> tableEntry : tableNameToMetadata.entrySet()) {
            String tableName = tableEntry.getKey();
            byte[] metadata = tableEntry.getValue();
            Map<String, byte[]> splitTableToMetadata = ImmutableMap.of();

            // always place in primary
            if (delegateToTablenameToMetadata.containsKey(primary)) {
                splitTableToMetadata = delegateToTablenameToMetadata.get(primary);
            } else {
                splitTableToMetadata = Maps.newHashMap();
            }
            splitTableToMetadata.put(tableName, metadata);
            delegateToTablenameToMetadata.put(primary, splitTableToMetadata);

            if (!isNotTiered(tableName)) {
                if (delegateToTablenameToMetadata.containsKey(secondary)) {
                    splitTableToMetadata = delegateToTablenameToMetadata.get(secondary);
                } else {
                    splitTableToMetadata = Maps.newHashMap();
                }
                splitTableToMetadata.put(tableName, metadata);
                delegateToTablenameToMetadata.put(secondary, splitTableToMetadata);
            }
        }
        for (KeyValueService kvs : delegateToTablenameToMetadata.keySet()) {
            kvs.putMetadataForTables(delegateToTablenameToMetadata.get(kvs));
        }
    }

    @Override
    public void addGarbageCollectionSentinelValues(final String tableName, final Set<Cell> cells) {
        secondary.addGarbageCollectionSentinelValues(tableName, cells);
    }

    public static Collection<TieredKeyValueService> getTieredServices(KeyValueService kvs) {
        List<TieredKeyValueService> tieredServices = Lists.newArrayList();
        if (kvs instanceof TieredKeyValueService) {
            tieredServices.add((TieredKeyValueService) kvs);
        }
        for (KeyValueService delegate : kvs.getDelegates()) {
            tieredServices.addAll(getTieredServices(delegate));
        }
        return tieredServices;
    }

    @Override
    public void compactInternally(String tableName) {
        throw new UnsupportedOperationException();
    }
}


text:
body {
  background-color: #1d1f21;
  color: #c9cacc;
  font-size: 14px;
  font-family: "Menlo", "Meslo LG", monospace;
  font-weight: 400;
  line-height: 1.725;
  text-rendering: geometricPrecision;
  -webkit-font-smoothing: antialiased;
  min-height: 100%;
}
.blog-single .text a {
  color: #c9cacc;
  background-repeat: repeat-x;
  background-position: bottom;
  background-size: 100% 6px;
  background-image: linear-gradient(transparent, transparent 5px, #c9cacc 5px, #c9cacc);
}

.blog-single .text a:hover {
  background-image: linear-gradient(transparent, transparent 4px, #d480aa 4px, #d480aa);
  color: #c9cacc;
}

.wrapper {
  lost-center: 1070px;
}
.content {
  lost-column: 2/3;
}
.main-inner {
  padding: 40px 35px;
}
@media screen and (max-width:1100px) {
  .content {
    lost-column: 2/4;
  }
  .main-inner {
    padding: 35px 20px;
  }
}
@media screen and (max-width:900px) {
  .content {
    lost-column: 7/12;
  }
  .main-inner {
    padding: 30px 20px;
  }
}
@media screen and (max-width:500px) {
  .content {
    lost-column: 4/4;
  }
  .main-inner {
    padding: 25px 20px;
  }
}

footer a {
  color: #c9cacc;
  background-repeat: repeat-x;
  background-position: bottom;
  background-size: 100% 6px;
  background-image: linear-gradient(transparent, transparent 5px, #c9cacc 5px, #c9cacc);
}

footer a:hover {
  background-image: linear-gradient(transparent, transparent 4px, #d480aa 4px, #d480aa);
  color: #c9cacc;
}


text:
On an x86_64 machine:
make install PREFIX=../../

On an arm64 machine: UNIMPLEMENTED

# On x86_32 machine: UNSUPPORTED

Notes:
Binary files are automatically placed in PREFIX/`uname -m`/. Everything is installed "in place" as siblings of src,
i.e., create "include", "lib", "<mach>/lib", etc..

If you wish particular languages not to be built, add one of more of the following to the make command:
* `SKNOBS_C=0`
* `SKNOBS_PERL=0`
* `SKNOBS_PYTHON=0`
* `SKNOBS_TCL=0`
* `SKNOBS_VERILOG=0`

System Package Dependencies (RPM package names)
* perl-devel
* python3
* python3-devel
* python3-setuptools

Python Package Dependencies.  It is expected that you are running in an
appropriate virtal environment for the version of python for which you wish to
build.
* pip install wheel


text:
package archive

import (
	"archive/tar"
	"context"
	"errors"
	"fmt"
	"io"
	"os"
	"path/filepath"
	"runtime"
	"strings"
	"sync"
	"syscall"
	"time"

	"github.com/containerd/containerd/log"
	"github.com/containerd/containerd/pkg/userns"
	"github.com/containerd/continuity/fs"
)

var bufPool = &sync.Pool{
	New: func() interface{} {
		buffer := make([]byte, 32*1024)
		return &buffer
	},
}

var errInvalidArchive = errors.New("invalid archive")

// Diff returns a tar stream of the computed filesystem
// difference between the provided directories.
//
// Produces a tar using OCI style file markers for deletions. Deleted
// files will be prepended with the prefix ".wh.". This style is
// based off AUFS whiteouts.
// See https://github.com/opencontainers/image-spec/blob/main/layer.md
func Diff(ctx context.Context, a, b string) io.ReadCloser {
	r, w := io.Pipe()

	go func() {
		err := WriteDiff(ctx, w, a, b)
		if err != nil {
			log.G(ctx).WithError(err).Debugf("write diff failed")
		}
		if err = w.CloseWithError(err); err != nil {
			log.G(ctx).WithError(err).Debugf("closing tar pipe failed")
		}
	}()

	return r
}

// WriteDiff writes a tar stream of the computed difference between the
// provided paths.
//
// Produces a tar using OCI style file markers for deletions. Deleted
// files will be prepended with the prefix ".wh.". This style is
// based off AUFS whiteouts.
// See https://github.com/opencontainers/image-spec/blob/main/layer.md
func WriteDiff(ctx context.Context, w io.Writer, a, b string, opts ...WriteDiffOpt) error {
	var options WriteDiffOptions
	for _, opt := range opts {
		if err := opt(&options); err != nil {
			return fmt.Errorf("failed to apply option: %w", err)
		}
	}
	if options.writeDiffFunc == nil {
		options.writeDiffFunc = writeDiffNaive
	}

	return options.writeDiffFunc(ctx, w, a, b, options)
}

// writeDiffNaive writes a tar stream of the computed difference between the
// provided directories on disk.
//
// Produces a tar using OCI style file markers for deletions. Deleted
// files will be prepended with the prefix ".wh.". This style is
// based off AUFS whiteouts.
// See https://github.com/opencontainers/image-spec/blob/main/layer.md
func writeDiffNaive(ctx context.Context, w io.Writer, a, b string, _ WriteDiffOptions) error {
	cw := NewChangeWriter(w, b)
	err := fs.Changes(ctx, a, b, cw.HandleChange)
	if err != nil {
		return fmt.Errorf("failed to create diff tar stream: %w", err)
	}
	return cw.Close()
}

const (
	// whiteoutPrefix prefix means file is a whiteout. If this is followed by a
	// filename this means that file has been removed from the base layer.
	// See https://github.com/opencontainers/image-spec/blob/main/layer.md#whiteouts
	whiteoutPrefix = ".wh."

	// whiteoutMetaPrefix prefix means whiteout has a special meaning and is not
	// for removing an actual file. Normally these files are excluded from exported
	// archives.
	whiteoutMetaPrefix = whiteoutPrefix + whiteoutPrefix

	// whiteoutOpaqueDir file means directory has been made opaque - meaning
	// readdir calls to this directory do not follow to lower layers.
	whiteoutOpaqueDir = whiteoutMetaPrefix + ".opq"

	paxSchilyXattr = "SCHILY.xattr."
)

// Apply applies a tar stream of an OCI style diff tar.
// See https://github.com/opencontainers/image-spec/blob/main/layer.md#applying-changesets
func Apply(ctx context.Context, root string, r io.Reader, opts ...ApplyOpt) (int64, error) {
	root = filepath.Clean(root)

	var options ApplyOptions
	for _, opt := range opts {
		if err := opt(&options); err != nil {
			return 0, fmt.Errorf("failed to apply option: %w", err)
		}
	}
	if options.Filter == nil {
		options.Filter = all
	}
	if options.applyFunc == nil {
		options.applyFunc = applyNaive
	}

	return options.applyFunc(ctx, root, r, options)
}

// applyNaive applies a tar stream of an OCI style diff tar to a directory
// applying each file as either a whole file or whiteout.
// See https://github.com/opencontainers/image-spec/blob/main/layer.md#applying-changesets
func applyNaive(ctx context.Context, root string, r io.Reader, options ApplyOptions) (size int64, err error) {
	var (
		dirs []*tar.Header

		tr = tar.NewReader(r)

		// Used for handling opaque directory markers which
		// may occur out of order
		unpackedPaths = make(map[string]struct{})

		convertWhiteout = options.ConvertWhiteout
	)

	if convertWhiteout == nil {
		// handle whiteouts by removing the target files
		convertWhiteout = func(hdr *tar.Header, path string) (bool, error) {
			base := filepath.Base(path)
			dir := filepath.Dir(path)
			if base == whiteoutOpaqueDir {
				_, err := os.Lstat(dir)
				if err != nil {
					return false, err
				}
				err = filepath.Walk(dir, func(path string, info os.FileInfo, err error) error {
					if err != nil {
						if os.IsNotExist(err) {
							err = nil // parent was deleted
						}
						return err
					}
					if path == dir {
						return nil
					}
					if _, exists := unpackedPaths[path]; !exists {
						err := os.RemoveAll(path)
						return err
					}
					return nil
				})
				return false, err
			}

			if strings.HasPrefix(base, whiteoutPrefix) {
				originalBase := base[len(whiteoutPrefix):]
				originalPath := filepath.Join(dir, originalBase)

				return false, os.RemoveAll(originalPath)
			}

			return true, nil
		}
	}

	// Iterate through the files in the archive.
	for {
		select {
		case <-ctx.Done():
			return 0, ctx.Err()
		default:
		}

		hdr, err := tr.Next()
		if err == io.EOF {
			// end of tar archive
			break
		}
		if err != nil {
			return 0, err
		}

		size += hdr.Size

		// Normalize name, for safety and for a simple is-root check
		hdr.Name = filepath.Clean(hdr.Name)

		accept, err := options.Filter(hdr)
		if err != nil {
			return 0, err
		}
		if !accept {
			continue
		}

		if skipFile(hdr) {
			log.G(ctx).Warnf("file %q ignored: archive may not be supported on system", hdr.Name)
			continue
		}

		// Split name and resolve symlinks for root directory.
		ppath, base := filepath.Split(hdr.Name)
		ppath, err = fs.RootPath(root, ppath)
		if err != nil {
			return 0, fmt.Errorf("failed to get root path: %w", err)
		}

		// Join to root before joining to parent path to ensure relative links are
		// already resolved based on the root before adding to parent.
		path := filepath.Join(ppath, filepath.Join("/", base))
		if path == root {
			log.G(ctx).Debugf("file %q ignored: resolved to root", hdr.Name)
			continue
		}

		// If file is not directly under root, ensure parent directory
		// exists or is created.
		if ppath != root {
			parentPath := ppath
			if base == "" {
				parentPath = filepath.Dir(path)
			}
			if err := mkparent(ctx, parentPath, root, options.Parents); err != nil {
				return 0, err
			}
		}

		// Naive whiteout convert function which handles whiteout files by
		// removing the target files.
		if err := validateWhiteout(path); err != nil {
			return 0, err
		}
		writeFile, err := convertWhiteout(hdr, path)
		if err != nil {
			return 0, fmt.Errorf("failed to convert whiteout file %q: %w", hdr.Name, err)
		}
		if !writeFile {
			continue
		}
		// If path exits we almost always just want to remove and replace it.
		// The only exception is when it is a directory *and* the file from
		// the layer is also a directory. Then we want to merge them (i.e.
		// just apply the metadata from the layer).
		if fi, err := os.Lstat(path); err == nil {
			if !(fi.IsDir() && hdr.Typeflag == tar.TypeDir) {
				if err := os.RemoveAll(path); err != nil {
					return 0, err
				}
			}
		}

		srcData := io.Reader(tr)
		srcHdr := hdr

		if err := createTarFile(ctx, path, root, srcHdr, srcData); err != nil {
			return 0, err
		}

		// Directory mtimes must be handled at the end to avoid further
		// file creation in them to modify the directory mtime
		if hdr.Typeflag == tar.TypeDir {
			dirs = append(dirs, hdr)
		}
		unpackedPaths[path] = struct{}{}
	}

	for _, hdr := range dirs {
		path, err := fs.RootPath(root, hdr.Name)
		if err != nil {
			return 0, err
		}
		if err := chtimes(path, boundTime(latestTime(hdr.AccessTime, hdr.ModTime)), boundTime(hdr.ModTime)); err != nil {
			return 0, err
		}
	}

	return size, nil
}

func createTarFile(ctx context.Context, path, extractDir string, hdr *tar.Header, reader io.Reader) error {
	// hdr.Mode is in linux format, which we can use for syscalls,
	// but for os.Foo() calls we need the mode converted to os.FileMode,
	// so use hdrInfo.Mode() (they differ for e.g. setuid bits)
	hdrInfo := hdr.FileInfo()

	switch hdr.Typeflag {
	case tar.TypeDir:
		// Create directory unless it exists as a directory already.
		// In that case we just want to merge the two
		if fi, err := os.Lstat(path); !(err == nil && fi.IsDir()) {
			if err := mkdir(path, hdrInfo.Mode()); err != nil {
				return err
			}
		}

	case tar.TypeReg, tar.TypeRegA:
		file, err := openFile(path, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, hdrInfo.Mode())
		if err != nil {
			return err
		}

		_, err = copyBuffered(ctx, file, reader)
		if err1 := file.Close(); err == nil {
			err = err1
		}
		if err != nil {
			return err
		}

	case tar.TypeBlock, tar.TypeChar:
		// Handle this is an OS-specific way
		if err := handleTarTypeBlockCharFifo(hdr, path); err != nil {
			return err
		}

	case tar.TypeFifo:
		// Handle this is an OS-specific way
		if err := handleTarTypeBlockCharFifo(hdr, path); err != nil {
			return err
		}

	case tar.TypeLink:
		targetPath, err := hardlinkRootPath(extractDir, hdr.Linkname)
		if err != nil {
			return err
		}

		if err := os.Link(targetPath, path); err != nil {
			return err
		}

	case tar.TypeSymlink:
		if err := os.Symlink(hdr.Linkname, path); err != nil {
			return err
		}

	case tar.TypeXGlobalHeader:
		log.G(ctx).Debug("PAX Global Extended Headers found and ignored")
		return nil

	default:
		return fmt.Errorf("unhandled tar header type %d", hdr.Typeflag)
	}

	// Lchown is not supported on Windows.
	if runtime.GOOS != "windows" {
		if err := os.Lchown(path, hdr.Uid, hdr.Gid); err != nil {
			err = fmt.Errorf("failed to Lchown %q for UID %d, GID %d: %w", path, hdr.Uid, hdr.Gid, err)
			if errors.Is(err, syscall.EINVAL) && userns.RunningInUserNS() {
				err = fmt.Errorf("%w (Hint: try increasing the number of subordinate IDs in /etc/subuid and /etc/subgid)", err)
			}
			return err
		}
	}

	for key, value := range hdr.PAXRecords {
		if strings.HasPrefix(key, paxSchilyXattr) {
			key = key[len(paxSchilyXattr):]
			if err := setxattr(path, key, value); err != nil {
				if errors.Is(err, syscall.ENOTSUP) {
					log.G(ctx).WithError(err).Warnf("ignored xattr %s in archive", key)
					continue
				}
				return err
			}
		}
	}

	// call lchmod after lchown since lchown can modify the file mode
	if err := lchmod(path, hdrInfo.Mode()); err != nil {
		return err
	}

	return chtimes(path, boundTime(latestTime(hdr.AccessTime, hdr.ModTime)), boundTime(hdr.ModTime))
}

func mkparent(ctx context.Context, path, root string, parents []string) error {
	if dir, err := os.Lstat(path); err == nil {
		if dir.IsDir() {
			return nil
		}
		return &os.PathError{
			Op:   "mkparent",
			Path: path,
			Err:  syscall.ENOTDIR,
		}
	} else if !os.IsNotExist(err) {
		return err
	}

	i := len(path)
	for i > len(root) && !os.IsPathSeparator(path[i-1]) {
		i--
	}

	if i > len(root)+1 {
		if err := mkparent(ctx, path[:i-1], root, parents); err != nil {
			return err
		}
	}

	if err := mkdir(path, 0755); err != nil {
		// Check that still doesn't exist
		dir, err1 := os.Lstat(path)
		if err1 == nil && dir.IsDir() {
			return nil
		}
		return err
	}

	for _, p := range parents {
		ppath, err := fs.RootPath(p, path[len(root):])
		if err != nil {
			return err
		}

		dir, err := os.Lstat(ppath)
		if err == nil {
			if !dir.IsDir() {
				// Replaced, do not copy attributes
				break
			}
			if err := copyDirInfo(dir, path); err != nil {
				return err
			}
			return copyUpXAttrs(path, ppath)
		} else if !os.IsNotExist(err) {
			return err
		}
	}

	log.G(ctx).Debugf("parent directory %q not found: default permissions(0755) used", path)

	return nil
}

// ChangeWriter provides tar stream from filesystem change information.
// The privided tar stream is styled as an OCI layer. Change information
// (add/modify/delete/unmodified) for each file needs to be passed to this
// writer through HandleChange method.
//
// This should be used combining with continuity's diff computing functionality
// (e.g. `fs.Change` of github.com/containerd/continuity/fs).
//
// See also https://github.com/opencontainers/image-spec/blob/main/layer.md for details
// about OCI layers
type ChangeWriter struct {
	tw        *tar.Writer
	source    string
	whiteoutT time.Time
	inodeSrc  map[uint64]string
	inodeRefs map[uint64][]string
	addedDirs map[string]struct{}
}

// NewChangeWriter returns ChangeWriter that writes tar stream of the source directory
// to the privided writer. Change information (add/modify/delete/unmodified) for each
// file needs to be passed through HandleChange method.
func NewChangeWriter(w io.Writer, source string) *ChangeWriter {
	return &ChangeWriter{
		tw:        tar.NewWriter(w),
		source:    source,
		whiteoutT: time.Now(),
		inodeSrc:  map[uint64]string{},
		inodeRefs: map[uint64][]string{},
		addedDirs: map[string]struct{}{},
	}
}

// HandleChange receives filesystem change information and reflect that information to
// the result tar stream. This function implements `fs.ChangeFunc` of continuity
// (github.com/containerd/continuity/fs) and should be used with that package.
func (cw *ChangeWriter) HandleChange(k fs.ChangeKind, p string, f os.FileInfo, err error) error {
	if err != nil {
		return err
	}
	if k == fs.ChangeKindDelete {
		whiteOutDir := filepath.Dir(p)
		whiteOutBase := filepath.Base(p)
		whiteOut := filepath.Join(whiteOutDir, whiteoutPrefix+whiteOutBase)
		hdr := &tar.Header{
			Typeflag:   tar.TypeReg,
			Name:       whiteOut[1:],
			Size:       0,
			ModTime:    cw.whiteoutT,
			AccessTime: cw.whiteoutT,
			ChangeTime: cw.whiteoutT,
		}
		if err := cw.includeParents(hdr); err != nil {
			return err
		}
		if err := cw.tw.WriteHeader(hdr); err != nil {
			return fmt.Errorf("failed to write whiteout header: %w", err)
		}
	} else {
		var (
			link   string
			err    error
			source = filepath.Join(cw.source, p)
		)

		switch {
		case f.Mode()&os.ModeSocket != 0:
			return nil // ignore sockets
		case f.Mode()&os.ModeSymlink != 0:
			if link, err = os.Readlink(source); err != nil {
				return err
			}
		}

		hdr, err := tar.FileInfoHeader(f, link)
		if err != nil {
			return err
		}

		hdr.Mode = int64(chmodTarEntry(os.FileMode(hdr.Mode)))

		// truncate timestamp for compatibility. without PAX stdlib rounds timestamps instead
		hdr.Format = tar.FormatPAX
		hdr.ModTime = hdr.ModTime.Truncate(time.Second)
		hdr.AccessTime = time.Time{}
		hdr.ChangeTime = time.Time{}

		name := p
		if strings.HasPrefix(name, string(filepath.Separator)) {
			name, err = filepath.Rel(string(filepath.Separator), name)
			if err != nil {
				return fmt.Errorf("failed to make path relative: %w", err)
			}
		}
		name, err = tarName(name)
		if err != nil {
			return fmt.Errorf("cannot canonicalize path: %w", err)
		}
		// suffix with '/' for directories
		if f.IsDir() && !strings.HasSuffix(name, "/") {
			name += "/"
		}
		hdr.Name = name

		if err := setHeaderForSpecialDevice(hdr, name, f); err != nil {
			return fmt.Errorf("failed to set device headers: %w", err)
		}

		// additionalLinks stores file names which must be linked to
		// this file when this file is added
		var additionalLinks []string
		inode, isHardlink := fs.GetLinkInfo(f)
		if isHardlink {
			// If the inode has a source, always link to it
			if source, ok := cw.inodeSrc[inode]; ok {
				hdr.Typeflag = tar.TypeLink
				hdr.Linkname = source
				hdr.Size = 0
			} else {
				if k == fs.ChangeKindUnmodified {
					cw.inodeRefs[inode] = append(cw.inodeRefs[inode], name)
					return nil
				}
				cw.inodeSrc[inode] = name
				additionalLinks = cw.inodeRefs[inode]
				delete(cw.inodeRefs, inode)
			}
		} else if k == fs.ChangeKindUnmodified {
			// Nothing to write to diff
			return nil
		}

		if capability, err := getxattr(source, "security.capability"); err != nil {
			return fmt.Errorf("failed to get capabilities xattr: %w", err)
		} else if len(capability) > 0 {
			if hdr.PAXRecords == nil {
				hdr.PAXRecords = map[string]string{}
			}
			hdr.PAXRecords[paxSchilyXattr+"security.capability"] = string(capability)
		}

		if err := cw.includeParents(hdr); err != nil {
			return err
		}
		if err := cw.tw.WriteHeader(hdr); err != nil {
			return fmt.Errorf("failed to write file header: %w", err)
		}

		if hdr.Typeflag == tar.TypeReg && hdr.Size > 0 {
			file, err := open(source)
			if err != nil {
				return fmt.Errorf("failed to open path: %v: %w", source, err)
			}
			defer file.Close()

			n, err := copyBuffered(context.TODO(), cw.tw, file)
			if err != nil {
				return fmt.Errorf("failed to copy: %w", err)
			}
			if n != hdr.Size {
				return errors.New("short write copying file")
			}
		}

		if additionalLinks != nil {
			source = hdr.Name
			for _, extra := range additionalLinks {
				hdr.Name = extra
				hdr.Typeflag = tar.TypeLink
				hdr.Linkname = source
				hdr.Size = 0

				if err := cw.includeParents(hdr); err != nil {
					return err
				}
				if err := cw.tw.WriteHeader(hdr); err != nil {
					return fmt.Errorf("failed to write file header: %w", err)
				}
			}
		}
	}
	return nil
}

// Close closes this writer.
func (cw *ChangeWriter) Close() error {
	if err := cw.tw.Close(); err != nil {
		return fmt.Errorf("failed to close tar writer: %w", err)
	}
	return nil
}

func (cw *ChangeWriter) includeParents(hdr *tar.Header) error {
	if cw.addedDirs == nil {
		return nil
	}
	name := strings.TrimRight(hdr.Name, "/")
	fname := filepath.Join(cw.source, name)
	parent := filepath.Dir(name)
	pname := filepath.Join(cw.source, parent)

	// Do not include root directory as parent
	if fname != cw.source && pname != cw.source {
		_, ok := cw.addedDirs[parent]
		if !ok {
			cw.addedDirs[parent] = struct{}{}
			fi, err := os.Stat(pname)
			if err != nil {
				return err
			}
			if err := cw.HandleChange(fs.ChangeKindModify, parent, fi, nil); err != nil {
				return err
			}
		}
	}
	if hdr.Typeflag == tar.TypeDir {
		cw.addedDirs[name] = struct{}{}
	}
	return nil
}

func copyBuffered(ctx context.Context, dst io.Writer, src io.Reader) (written int64, err error) {
	buf := bufPool.Get().(*[]byte)
	defer bufPool.Put(buf)

	for {
		select {
		case <-ctx.Done():
			err = ctx.Err()
			return
		default:
		}

		nr, er := src.Read(*buf)
		if nr > 0 {
			nw, ew := dst.Write((*buf)[0:nr])
			if nw > 0 {
				written += int64(nw)
			}
			if ew != nil {
				err = ew
				break
			}
			if nr != nw {
				err = io.ErrShortWrite
				break
			}
		}
		if er != nil {
			if er != io.EOF {
				err = er
			}
			break
		}
	}
	return written, err

}

// hardlinkRootPath returns target linkname, evaluating and bounding any
// symlink to the parent directory.
//
// NOTE: Allow hardlink to the softlink, not the real one. For example,
//
//	touch /tmp/zzz
//	ln -s /tmp/zzz /tmp/xxx
//	ln /tmp/xxx /tmp/yyy
//
// /tmp/yyy should be softlink which be same of /tmp/xxx, not /tmp/zzz.
func hardlinkRootPath(root, linkname string) (string, error) {
	ppath, base := filepath.Split(linkname)
	ppath, err := fs.RootPath(root, ppath)
	if err != nil {
		return "", err
	}

	targetPath := filepath.Join(ppath, base)
	if !strings.HasPrefix(targetPath, root) {
		targetPath = root
	}
	return targetPath, nil
}

func validateWhiteout(path string) error {
	base := filepath.Base(path)
	dir := filepath.Dir(path)

	if base == whiteoutOpaqueDir {
		return nil
	}

	if strings.HasPrefix(base, whiteoutPrefix) {
		originalBase := base[len(whiteoutPrefix):]
		originalPath := filepath.Join(dir, originalBase)

		// Ensure originalPath is under dir
		if dir[len(dir)-1] != filepath.Separator {
			dir += string(filepath.Separator)
		}
		if !strings.HasPrefix(originalPath, dir) {
			return fmt.Errorf("invalid whiteout name: %v: %w", base, errInvalidArchive)
		}
	}
	return nil
}