test/unit/org/apache/cassandra/db/rows/UnfilteredRowsGenerator.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.cassandra.db.rows;

import java.nio.ByteBuffer;
import java.util.*;
import java.util.function.Function;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import org.junit.Assert;

import org.apache.cassandra.config.CFMetaData;
import org.apache.cassandra.db.*;
import org.apache.cassandra.db.marshal.Int32Type;
import org.apache.cassandra.db.rows.Unfiltered.Kind;
import org.apache.cassandra.utils.btree.BTree;

public class UnfilteredRowsGenerator
{
    final boolean reversed;
    final Comparator<Clusterable> comparator;

    public UnfilteredRowsGenerator(Comparator<Clusterable> comparator, boolean reversed)
    {
        this.reversed = reversed;
        this.comparator = comparator;
    }

    String str(Clusterable curr)
    {
        if (curr == null)
            return "null";
        String val = Int32Type.instance.getString(curr.clustering().get(0));
        if (curr instanceof RangeTombstoneMarker)
        {
            RangeTombstoneMarker marker = (RangeTombstoneMarker) curr;
            if (marker.isClose(reversed))
                val = "[" + marker.closeDeletionTime(reversed).markedForDeleteAt() + "]" + (marker.closeIsInclusive(reversed) ? "<=" : "<") + val;
            if (marker.isOpen(reversed))
                val = val + (marker.openIsInclusive(reversed) ? "<=" : "<") + "[" + marker.openDeletionTime(reversed).markedForDeleteAt() + "]";
        }
        else if (curr instanceof Row)
        {
            Row row = (Row) curr;
            String delTime = "";
            if (!row.deletion().time().isLive())
                delTime = "D" + row.deletion().time().markedForDeleteAt();
            val = val + "[" + row.primaryKeyLivenessInfo().timestamp() + delTime + "]";
        }
        return val;
    }

    public void verifyValid(List<Unfiltered> list)
    {
        verifyValid(list, reversed);
    }

    void verifyValid(List<Unfiltered> list, boolean reversed)
    {
        int reversedAsMultiplier = reversed ? -1 : 1;
        try {
            RangeTombstoneMarker prev = null;
            Unfiltered prevUnfiltered = null;
            for (Unfiltered unfiltered : list)
            {
                Assert.assertTrue("Order violation prev " + str(prevUnfiltered) + " curr " + str(unfiltered),
                                  prevUnfiltered == null || comparator.compare(prevUnfiltered, unfiltered) * reversedAsMultiplier < 0);
                prevUnfiltered = unfiltered;

                if (unfiltered.kind() == Kind.RANGE_TOMBSTONE_MARKER)
                {
                    RangeTombstoneMarker curr = (RangeTombstoneMarker) unfiltered;
                    if (prev != null)
                    {
                        if (curr.isClose(reversed))
                        {
                            Assert.assertTrue(str(unfiltered) + " follows another close marker " + str(prev), prev.isOpen(reversed));
                            Assert.assertEquals("Deletion time mismatch for open " + str(prev) + " and close " + str(unfiltered),
                                                prev.openDeletionTime(reversed),
                                                curr.closeDeletionTime(reversed));
                        }
                        else
                            Assert.assertFalse(str(curr) + " follows another open marker " + str(prev), prev.isOpen(reversed));
                    }

                    prev = curr;
                }
            }
            Assert.assertFalse("Cannot end in open marker " + str(prev), prev != null && prev.isOpen(reversed));

        } catch (AssertionError e) {
            System.out.println(e);
            dumpList(list);
            throw e;
        }
    }

    public List<Unfiltered> generateSource(Random r, int items, int range, int del_range, Function<Integer, Integer> timeGenerator)
    {
        int[] positions = new int[items + 1];
        for (int i=0; i<items; ++i)
            positions[i] = r.nextInt(range);
        positions[items] = range;
        Arrays.sort(positions);

        List<Unfiltered> content = new ArrayList<>(items);
        int prev = -1;
        for (int i=0; i<items; ++i)
        {
            int pos = positions[i];
            int sz = positions[i + 1] - pos;
            if (sz == 0 && pos == prev)
                // Filter out more than two of the same position.
                continue;
            if (r.nextBoolean() || pos == prev)
            {
                int span;
                boolean includesStart;
                boolean includesEnd;
                if (pos > prev)
                {
                    span = r.nextInt(sz + 1);
                    includesStart = span > 0 ? r.nextBoolean() : true;
                    includesEnd = span > 0 ? r.nextBoolean() : true;
                }
                else
                {
                    span = 1 + r.nextInt(sz);
                    includesStart = false;
                    includesEnd = r.nextBoolean();
                }
                int deltime = r.nextInt(del_range);
                DeletionTime dt = new DeletionTime(deltime, deltime);
                content.add(new RangeTombstoneBoundMarker(boundFor(pos, true, includesStart), dt));
                content.add(new RangeTombstoneBoundMarker(boundFor(pos + span, false, includesEnd), dt));
                prev = pos + span - (includesEnd ? 0 : 1);
            }
            else
            {
                content.add(emptyRowAt(pos, timeGenerator));
                prev = pos;
            }
        }

        attachBoundaries(content);
        if (reversed)
        {
            Collections.reverse(content);
        }
        verifyValid(content);
        if (items <= 20)
            dumpList(content);
        return content;
    }

    /**
     * Constructs a list of unfiltereds with integer clustering according to the specification string.
     *
     * The string is a space-delimited sorted list that can contain:
     *  * open tombstone markers, e.g. xx<[yy] where xx is the clustering, yy is the deletion time, and "<" stands for
     *    non-inclusive (<= for inclusive).
     *  * close tombstone markers, e.g. [yy]<=xx. Adjacent close and open markers (e.g. [yy]<=xx xx<[zz]) are combined
     *    into boundary markers.
     *  * empty rows, e.g. xx or xx[yy] or xx[yyDzz] where xx is the clustering, yy is the live time and zz is deletion
     *    time.
     *
     * @param input Specification.
     * @param default_liveness Liveness to use for rows if not explicitly specified.
     * @return Parsed list.
     */
    public List<Unfiltered> parse(String input, int default_liveness)
    {
        String[] split = input.split(" ");
        Pattern open = Pattern.compile("(\\d+)<(=)?\\[(\\d+)\\]");
        Pattern close = Pattern.compile("\\[(\\d+)\\]<(=)?(\\d+)");
        Pattern row = Pattern.compile("(\\d+)(\\[(\\d+)(?:D(\\d+))?\\])?");
        List<Unfiltered> out = new ArrayList<>(split.length);
        for (String s : split)
        {
            Matcher m = open.matcher(s);
            if (m.matches())
            {
                out.add(openMarker(Integer.parseInt(m.group(1)), Integer.parseInt(m.group(3)), m.group(2) != null));
                continue;
            }
            m = close.matcher(s);
            if (m.matches())
            {
                out.add(closeMarker(Integer.parseInt(m.group(3)), Integer.parseInt(m.group(1)), m.group(2) != null));
                continue;
            }
            m = row.matcher(s);
            if (m.matches())
            {
                int live = m.group(3) != null ? Integer.parseInt(m.group(3)) : default_liveness;
                int delTime = m.group(4) != null ? Integer.parseInt(m.group(4)) : -1;
                out.add(emptyRowAt(Integer.parseInt(m.group(1)), live, delTime));
                continue;
            }
            Assert.fail("Can't parse " + s);
        }
        attachBoundaries(out);
        return out;
    }

    static Row emptyRowAt(int pos, Function<Integer, Integer> timeGenerator)
    {
        final Clustering clustering = clusteringFor(pos);
        final LivenessInfo live = LivenessInfo.create(timeGenerator.apply(pos), UnfilteredRowIteratorsMergeTest.nowInSec);
        return BTreeRow.noCellLiveRow(clustering, live);
    }

    static Row emptyRowAt(int pos, int time, int deletionTime)
    {
        final Clustering clustering = clusteringFor(pos);
        final LivenessInfo live = LivenessInfo.create(time, UnfilteredRowIteratorsMergeTest.nowInSec);
        final DeletionTime delTime = deletionTime == -1 ? DeletionTime.LIVE : new DeletionTime(deletionTime, deletionTime);
        return BTreeRow.create(clustering, live, Row.Deletion.regular(delTime), BTree.empty());
    }

    static Clustering clusteringFor(int i)
    {
        return Clustering.make(Int32Type.instance.decompose(i));
    }

    static ClusteringBound boundFor(int pos, boolean start, boolean inclusive)
    {
        return ClusteringBound.create(ClusteringBound.boundKind(start, inclusive), new ByteBuffer[] {Int32Type.instance.decompose(pos)});
    }

    static void attachBoundaries(List<Unfiltered> content)
    {
        int di = 0;
        RangeTombstoneMarker prev = null;
        for (int si = 0; si < content.size(); ++si)
        {
            Unfiltered currUnfiltered = content.get(si);
            RangeTombstoneMarker curr = currUnfiltered.kind() == Kind.RANGE_TOMBSTONE_MARKER ?
                                        (RangeTombstoneMarker) currUnfiltered :
                                        null;
            if (prev != null && curr != null && prev.isClose(false) && curr.isOpen(false) && prev.clustering().invert().equals(curr.clustering()))
            {
                // Join. Prefer not to use merger to check its correctness.
                ClusteringBound b = (ClusteringBound) prev.clustering();
                ClusteringBoundary boundary = ClusteringBoundary.create(
                        b.isInclusive() ? ClusteringBound.Kind.INCL_END_EXCL_START_BOUNDARY : ClusteringBound.Kind.EXCL_END_INCL_START_BOUNDARY,
                        b.getRawValues());
                prev = new RangeTombstoneBoundaryMarker(boundary, prev.closeDeletionTime(false), curr.openDeletionTime(false));
                currUnfiltered = prev;
                --di;
            }
            content.set(di++, currUnfiltered);
            prev = curr;
        }
        for (int pos = content.size() - 1; pos >= di; --pos)
            content.remove(pos);
    }

    static RangeTombstoneMarker openMarker(int pos, int delTime, boolean inclusive)
    {
        return marker(pos, delTime, true, inclusive);
    }

    static RangeTombstoneMarker closeMarker(int pos, int delTime, boolean inclusive)
    {
        return marker(pos, delTime, false, inclusive);
    }

    private static RangeTombstoneMarker marker(int pos, int delTime, boolean isStart, boolean inclusive)
    {
        return new RangeTombstoneBoundMarker(ClusteringBound.create(ClusteringBound.boundKind(isStart, inclusive),
                                                                    new ByteBuffer[] {clusteringFor(pos).get(0)}),
                                             new DeletionTime(delTime, delTime));
    }

    public static UnfilteredRowIterator source(Iterable<Unfiltered> content, CFMetaData metadata, DecoratedKey partitionKey)
    {
        return source(content, metadata, partitionKey, DeletionTime.LIVE);
    }

    public static UnfilteredRowIterator source(Iterable<Unfiltered> content, CFMetaData metadata, DecoratedKey partitionKey, DeletionTime delTime)
    {
        return new Source(content.iterator(), metadata, partitionKey, delTime, false);
    }

    static class Source extends AbstractUnfilteredRowIterator implements UnfilteredRowIterator
    {
        Iterator<Unfiltered> content;

        protected Source(Iterator<Unfiltered> content, CFMetaData metadata, DecoratedKey partitionKey, DeletionTime partitionLevelDeletion, boolean reversed)
        {
            super(metadata,
                  partitionKey,
                  partitionLevelDeletion,
                  metadata.partitionColumns(),
                  Rows.EMPTY_STATIC_ROW,
                  reversed,
                  EncodingStats.NO_STATS);
            this.content = content;
        }

        @Override
        protected Unfiltered computeNext()
        {
            return content.hasNext() ? content.next() : endOfData();
        }
    }

    public String str(List<Unfiltered> list)
    {
        StringBuilder builder = new StringBuilder();
        for (Unfiltered u : list)
        {
            builder.append(str(u));
            builder.append(' ');
        }
        return builder.toString();
    }

    public void dumpList(List<Unfiltered> list)
    {
        System.out.println(str(list));
    }
}