linting

Remove a range check and prefix check on the keys passed to
`Delimiter.filter()`: they are useless, as all callers (Metadata,
MongoDB) always provide a proper range of keys via parameters passed
to the database, so those checks can be spared.

lib/algos/list/delimiter.ts

@@ -2,21 +2,41 @@
 
 const Extension = require('./Extension').default;
 const { inc, listingParamsMasterKeysV0ToV1,
-    FILTER_END, FILTER_ACCEPT, FILTER_SKIP } = require('./tools');
+    FILTER_END, FILTER_ACCEPT, FILTER_SKIP, SKIP_NONE } = require('./tools');
 const VSConst = require('../../versioning/constants').VersioningConstants;
 const { DbPrefixes, BucketVersioningKeyFormat } = VSConst;
 
-/**
- * Find the common prefix in the path
- *
- * @param {String} key            - path of the object
- * @param {String} delimiter      - separator
- * @param {Number} delimiterIndex - 'folder' index in the path
- * @return {String}               - CommonPrefix
- */
-function getCommonPrefix(key, delimiter, delimiterIndex) {
-    return key.substring(0, delimiterIndex + delimiter.length);
-}
+export interface FilterState {
+    id: number,
+};
+
+export const enum DelimiterFilterStateId {
+    NotSkipping = 1,
+    SkippingPrefix = 2,
+};
+
+export interface DelimiterFilterState_NotSkipping extends FilterState {
+    id: DelimiterFilterStateId.NotSkipping,
+};
+
+export interface DelimiterFilterState_SkippingPrefix extends FilterState {
+    id: DelimiterFilterStateId.SkippingPrefix,
+    prefix: string;
+};
+
+type KeyHandler = (key: string, value: string) => number;
+
+type ResultObject = {
+    CommonPrefixes: string[];
+    Contents: {
+        key: string;
+        value: string;
+    }[];
+    IsTruncated: boolean;
+    Delimiter ?: string;
+    NextMarker ?: string;
+    NextContinuationToken ?: string;
+};
 
 /**
  * Handle object listing with parameters
@@ -30,7 +50,11 @@ function getCommonPrefix(key, delimiter, delimiterIndex) {
  * @prop {String|undefined} prefix     - prefix per amazon format
  * @prop {Number} maxKeys              - number of keys to list
  */
-class Delimiter extends Extension {
+export class Delimiter extends Extension {
+
+    state: FilterState;
+    keyHandlers: { [id: number]: KeyHandler };
+
     /**
      * Create a new Delimiter instance
      * @constructor
@@ -48,9 +72,6 @@ class Delimiter extends Extension {
      *                                                   format
      * @param {String}  [parameters.continuationToken] - obfuscated amazon
      *                                                   token
-     * @param {Boolean} [parameters.alphabeticalOrder] - Either the result is
-     *                                                   alphabetically ordered
-     *                                                   or not
      * @param {RequestLogger} logger                   - The logger of the
      *                                                   request
      * @param {String} [vFormat]                       - versioning key format
@@ -60,38 +81,21 @@ class Delimiter extends Extension {
         // original listing parameters
         this.delimiter = parameters.delimiter;
         this.prefix = parameters.prefix;
-        this.marker = parameters.marker;
         this.maxKeys = parameters.maxKeys || 1000;
-        this.startAfter = parameters.startAfter;
-        this.continuationToken = parameters.continuationToken;
-        this.alphabeticalOrder =
-          typeof parameters.alphabeticalOrder !== 'undefined' ?
-              parameters.alphabeticalOrder : true;
+
+        if (parameters.v2) {
+            this.marker = parameters.continuationToken || parameters.startAfter;
+        } else {
+            this.marker = parameters.marker;
+        }
+        this.nextMarker = this.marker;
 
         this.vFormat = vFormat || BucketVersioningKeyFormat.v0;
         // results
         this.CommonPrefixes = [];
         this.Contents = [];
         this.IsTruncated = false;
-        this.NextMarker = parameters.marker;
-        this.NextContinuationToken =
-            parameters.continuationToken || parameters.startAfter;
-
-        this.startMarker = parameters.v2 ? 'startAfter' : 'marker';
-        this.continueMarker = parameters.v2 ? 'continuationToken' : 'marker';
-        this.nextContinueMarker = parameters.v2 ?
-            'NextContinuationToken' : 'NextMarker';
-
-        if (this.delimiter !== undefined &&
-            this[this.nextContinueMarker] !== undefined &&
-            this[this.nextContinueMarker].startsWith(this.prefix || '')) {
-            const nextDelimiterIndex =
-                this[this.nextContinueMarker].indexOf(this.delimiter,
-                    this.prefix ? this.prefix.length : 0);
-            this[this.nextContinueMarker] =
-                this[this.nextContinueMarker].slice(0, nextDelimiterIndex +
-                                        this.delimiter.length);
-        }
+        this.keyHandlers = {};
 
         Object.assign(this, {
             [BucketVersioningKeyFormat.v0]: {
@@ -105,21 +109,49 @@ class Delimiter extends Extension {
                 skipping: this.skippingV1,
             },
         }[this.vFormat]);
+
+        // if there is a delimiter, we may skip ranges by prefix,
+        // hence using the NotSkippingPrefix flavor that checks the
+        // subprefix up to the delimiter for the NotSkipping state
+        if (this.delimiter) {
+            this.setKeyHandler(
+                DelimiterFilterStateId.NotSkipping,
+                this.keyHandler_NotSkippingPrefix.bind(this));
+
+            this.setKeyHandler(
+                DelimiterFilterStateId.SkippingPrefix,
+                this.keyHandler_SkippingPrefix.bind(this));
+        } else {
+            // listing without a delimiter never has to skip over any
+            // prefix -> use NeverSkipping flavor for the NotSkipping
+            // state
+            this.setKeyHandler(
+                DelimiterFilterStateId.NotSkipping,
+                this.keyHandler_NeverSkipping.bind(this));
+        }
+        this.state = <DelimiterFilterState_NotSkipping> {
+            id: DelimiterFilterStateId.NotSkipping,
+        };
     }
 
     genMDParamsV0() {
-        const params = {};
+        const params: { gt ?: string, gte ?: string, lt ?: string } = {};
         if (this.prefix) {
             params.gte = this.prefix;
             params.lt = inc(this.prefix);
         }
-        const startVal = this[this.continueMarker] || this[this.startMarker];
-        if (startVal) {
-            if (params.gte && params.gte > startVal) {
-                return params;
+        if (this.marker && this.delimiter) {
+            const commonPrefix = this.getCommonPrefix(this.marker);
+            if (commonPrefix) {
+                const afterPrefix = inc(commonPrefix);
+                if (!params.gte || afterPrefix > params.gte) {
+                    params.gte = afterPrefix;
+                }
             }
+        }
+        if (this.marker && (!params.gte || this.marker >= params.gte)) {
             delete params.gte;
-            params.gt = startVal;
+            params.gt = this.marker;
         }
         return params;
     }
@@ -151,21 +183,62 @@ class Delimiter extends Extension {
      *  @param {String} value - The value of the key
      *  @return {number}      - indicates if iteration should continue
      */
-    addContents(key, value) {
+    addContents(key: string, value: string): number {
         if (this._reachedMaxKeys()) {
             return FILTER_END;
         }
         this.Contents.push({ key, value: this.trimMetadata(value) });
-        this[this.nextContinueMarker] = key;
         ++this.keys;
+        this.nextMarker = key;
         return FILTER_ACCEPT;
     }
 
-    getObjectKeyV0(obj) {
+    getCommonPrefix(key: string): string | undefined {
+        const baseIndex = this.prefix ? this.prefix.length : 0;
+        const delimiterIndex = key.indexOf(this.delimiter, baseIndex);
+        if (delimiterIndex === -1) {
+            return undefined;
+        }
+        return key.substring(0, delimiterIndex + this.delimiter.length);
+    }
+
+    /**
+     * Add a Common Prefix in the list
+     * @param {String} commonPrefix   - common prefix to add
+     * @param {String} key            - full key starting with commonPrefix
+     * @return {Boolean}     - indicates if iteration should continue
+     */
+    addCommonPrefix(commonPrefix: string, key: string): number {
+        if (this._reachedMaxKeys()) {
+            return FILTER_END;
+        }
+        // add the new prefix to the list
+        this.CommonPrefixes.push(commonPrefix);
+        ++this.keys;
+        this.nextMarker = key;
+        // transition into SkippingPrefix state to skip all following keys
+        // while they start with the same prefix
+        this.setState(<DelimiterFilterState_SkippingPrefix> {
+            id: DelimiterFilterStateId.SkippingPrefix,
+            prefix: commonPrefix,
+        });
+        return FILTER_ACCEPT;
+    }
+
+    addCommonPrefixOrContents(key: string, value: string): number {
+        // add the subprefix to the common prefixes if the key has the delimiter
+        const commonPrefix = this.getCommonPrefix(key);
+        if (commonPrefix) {
+            return this.addCommonPrefix(commonPrefix, key);
+        }
+        return this.addContents(key, value);
+    }
+
+    getObjectKeyV0(obj: { key: string }): string {
         return obj.key;
     }
 
-    getObjectKeyV1(obj) {
+    getObjectKeyV1(obj: { key: string }): string {
         return obj.key.slice(DbPrefixes.Master.length);
     }
 
@@ -180,67 +253,65 @@ class Delimiter extends Extension {
      *  @param {String} obj.value - The value of the element
      *  @return {number}          - indicates if iteration should continue
      */
-    filter(obj) {
+    filter(obj: { key: string, value: string }): number {
         const key = this.getObjectKey(obj);
         const value = obj.value;
-        if ((this.prefix && !key.startsWith(this.prefix))
-            || (this.alphabeticalOrder
-                && typeof this[this.nextContinueMarker] === 'string'
-                && key <= this[this.nextContinueMarker])) {
-            return FILTER_SKIP;
-        }
-        if (this.delimiter) {
-            const baseIndex = this.prefix ? this.prefix.length : 0;
-            const delimiterIndex = key.indexOf(this.delimiter, baseIndex);
-            if (delimiterIndex === -1) {
-                return this.addContents(key, value);
-            }
-            return this.addCommonPrefix(key, delimiterIndex);
-        }
+
+        return this.handleKey(key, value);
+    }
+
+    setState(state: FilterState): void {
+        this.state = state;
+    }
+
+    setKeyHandler(stateId: number, keyHandler: KeyHandler): void {
+        this.keyHandlers[stateId] = keyHandler;
+    }
+
+    handleKey(key: string, value: string): number {
+        return this.keyHandlers[this.state.id](key, value);
+    }
+
+    keyHandler_NeverSkipping(key, value) {
         return this.addContents(key, value);
     }
 
-    /**
-     * Add a Common Prefix in the list
-     * @param {String} key   - object name
-     * @param {Number} index - after prefix starting point
-     * @return {Boolean}     - indicates if iteration should continue
-     */
-    addCommonPrefix(key, index) {
-        const commonPrefix = getCommonPrefix(key, this.delimiter, index);
-        if (this.CommonPrefixes.indexOf(commonPrefix) === -1
-                && this[this.nextContinueMarker] !== commonPrefix) {
-            if (this._reachedMaxKeys()) {
-                return FILTER_END;
-            }
-            this.CommonPrefixes.push(commonPrefix);
-            this[this.nextContinueMarker] = commonPrefix;
-            ++this.keys;
-            return FILTER_ACCEPT;
+    keyHandler_NotSkippingPrefix(key, value) {
+        return this.addCommonPrefixOrContents(key, value);
+    }
+
+    keyHandler_SkippingPrefix(key, value) {
+        const { prefix } = <DelimiterFilterState_SkippingPrefix> this.state;
+        if (key.startsWith(prefix)) {
+            return FILTER_SKIP;
+        }
+        this.setState(<DelimiterFilterState_NotSkipping> {
+            id: DelimiterFilterStateId.NotSkipping,
+        });
+        return this.handleKey(key, value);
+    }
+
+    skippingBase(): string | undefined {
+        switch (this.state.id) {
+        case DelimiterFilterStateId.SkippingPrefix:
+            const { prefix } = <DelimiterFilterState_SkippingPrefix> this.state;
+            return prefix;
+
+        default:
+            return SKIP_NONE;
         }
-        return FILTER_SKIP;
     }
 
-    /**
-     * If repd happens to want to skip listing on a bucket in v0
-     * versioning key format, here is an idea.
-     *
-     * @return {string} - the present range (NextMarker) if repd believes
-     *                    that it's enough and should move on
-     */
     skippingV0() {
-        return this[this.nextContinueMarker];
+        return this.skippingBase();
     }
 
-    /**
-     * If repd happens to want to skip listing on a bucket in v1
-     * versioning key format, here is an idea.
-     *
-     * @return {string} - the present range (NextMarker) if repd believes
-     *                    that it's enough and should move on
-     */
     skippingV1() {
-        return DbPrefixes.Master + this[this.nextContinueMarker];
+        const skipTo = this.skippingBase();
+        if (skipTo === SKIP_NONE) {
+            return SKIP_NONE;
+        }
+        return DbPrefixes.Master + skipTo;
     }
 
     /**
@@ -249,12 +320,12 @@ class Delimiter extends Extension {
      *  isn't truncated
      *  @return {Object} - following amazon format
      */
-    result() {
+    result(): ResultObject {
         /* NextMarker is only provided when delimiter is used.
          * specified in v1 listing documentation
          * http://docs.aws.amazon.com/AmazonS3/latest/API/RESTBucketGET.html
          */
-        const result = {
+        const result: ResultObject = {
             CommonPrefixes: this.CommonPrefixes,
             Contents: this.Contents,
             IsTruncated: this.IsTruncated,
@@ -262,13 +333,11 @@ class Delimiter extends Extension {
         };
         if (this.parameters.v2) {
             result.NextContinuationToken = this.IsTruncated
-                ? this.NextContinuationToken : undefined;
+                ? this.nextMarker : undefined;
         } else {
             result.NextMarker = (this.IsTruncated && this.delimiter)
-                ? this.NextMarker : undefined;
+                ? this.nextMarker : undefined;
         }
         return result;
     }
 }
-
-module.exports = { Delimiter, getCommonPrefix };

lib/algos/list/delimiterMaster.js

@@ -1,230 +0,0 @@
-'use strict'; // eslint-disable-line strict
-
-const Delimiter = require('./delimiter').Delimiter;
-const Version = require('../../versioning/Version').Version;
-const VSConst = require('../../versioning/constants').VersioningConstants;
-const { BucketVersioningKeyFormat } = VSConst;
-const { FILTER_ACCEPT, FILTER_SKIP, SKIP_NONE } = require('./tools');
-
-const VID_SEP = VSConst.VersionId.Separator;
-const { DbPrefixes } = VSConst;
-
-/**
- * Handle object listing with parameters. This extends the base class Delimiter
- * to return the raw master versions of existing objects.
- */
-class DelimiterMaster extends Delimiter {
-    /**
-     * Delimiter listing of master versions.
-     * @param {Object}  parameters            - listing parameters
-     * @param {String}  parameters.delimiter  - delimiter per amazon format
-     * @param {String}  parameters.prefix     - prefix per amazon format
-     * @param {String}  parameters.marker     - marker per amazon format
-     * @param {Number}  parameters.maxKeys    - number of keys to list
-     * @param {Boolean} parameters.v2         - indicates whether v2 format
-     * @param {String}  parameters.startAfter - marker per amazon v2 format
-     * @param {String}  parameters.continuationToken - obfuscated amazon token
-     * @param {RequestLogger} logger          - The logger of the request
-     * @param {String} [vFormat]              - versioning key format
-     */
-    constructor(parameters, logger, vFormat) {
-        super(parameters, logger, vFormat);
-        // non-PHD master version or a version whose master is a PHD version
-        this.prvKey = undefined;
-        this.prvPHDKey = undefined;
-        this.inReplayPrefix = false;
-        this.prefixKeySeen = false;
-        this.prefixEndsWithDelim = this.prefix && this.prefix.endsWith(this.delimiter);
-
-        Object.assign(this, {
-            [BucketVersioningKeyFormat.v0]: {
-                filter: this.filterV0,
-                skipping: this.skippingV0,
-            },
-            [BucketVersioningKeyFormat.v1]: {
-                filter: this.filterV1,
-                skipping: this.skippingV1,
-            },
-        }[this.vFormat]);
-    }
-
-    /**
-     *  Filter to apply on each iteration for buckets in v0 format,
-     *  based on:
-     *  - prefix
-     *  - delimiter
-     *  - maxKeys
-     *  The marker is being handled directly by levelDB
-     *  @param {Object} obj       - The key and value of the element
-     *  @param {String} obj.key   - The key of the element
-     *  @param {String} obj.value - The value of the element
-     *  @return {number}          - indicates if iteration should continue
-     */
-    filterV0(obj) {
-        let key = obj.key;
-        const value = obj.value;
-
-        if (key === this.prefix) {
-            this.prefixKeySeen = true;
-        }
-
-        if (key.startsWith(DbPrefixes.Replay)) {
-            this.inReplayPrefix = true;
-            return FILTER_SKIP;
-        }
-        this.inReplayPrefix = false;
-
-        /* Skip keys not starting with the prefix or not alphabetically
-         * ordered. */
-        if ((this.prefix && !key.startsWith(this.prefix))
-                || (typeof this[this.nextContinueMarker] === 'string' &&
-                    key <= this[this.nextContinueMarker])) {
-            return FILTER_SKIP;
-        }
-
-        /* Skip version keys (<key><versionIdSeparator><version>) if we already
-         * have a master version. */
-        const versionIdIndex = key.indexOf(VID_SEP);
-        if (versionIdIndex >= 0) {
-            key = key.slice(0, versionIdIndex);
-            /* - key === this.prvKey is triggered when a master version has
-             *   been accepted for this key,
-             * - key === this.NextMarker or this.NextContinueToken is triggered
-             *   when a listing page ends on an accepted obj and the next page
-             *   starts with a version of this object.
-             *   In that case prvKey is default set to undefined
-             *   in the constructor and comparing to NextMarker is the only
-             *   way to know  we should not accept this version. This test is
-             *   not redundant with the one at the beginning of this function,
-             *   we are comparing here the key without the version suffix,
-             * - key startsWith the previous NextMarker happens because we set
-             *   NextMarker to the common prefix instead of the whole key
-             *   value. (TODO: remove this test once ZENKO-1048 is fixed)
-             *   */
-            if (key === this.prvKey || key === this[this.nextContinueMarker]
-                || (this.delimiter && key.startsWith(this[this.nextContinueMarker]))) {
-                /* master version already filtered */
-                return FILTER_SKIP;
-            }
-        }
-        if (Version.isPHD(value)) {
-            /* master version is a PHD version, we want to wait for the next
-             * one:
-             * - Set the prvKey to undefined to not skip the next version,
-             * - return accept to avoid users to skip the next values in range
-             *   (skip scan mechanism in metadata backend like Metadata or
-             *   MongoClient). */
-            this.prvKey = undefined;
-            this.prvPHDKey = key;
-            return FILTER_ACCEPT;
-        }
-        if (Version.isDeleteMarker(value)) {
-            /* This entry is a deleteMarker which has not been filtered by the
-             * version test. Either :
-             * - it is a deleteMarker on the master version, we want to SKIP
-             *   all the following entries with this key (no master version),
-             * - or a deleteMarker following a PHD (setting prvKey to undefined
-             *   when an entry is a PHD avoids the skip on version for the
-             *   next entry). In that case we expect the master version to
-             *   follow. */
-            if (key === this.prvPHDKey) {
-                this.prvKey = undefined;
-                return FILTER_ACCEPT;
-            }
-            this.prvKey = key;
-            if (this.prefixEndsWithDelim) {
-                /* When the prefix ends with a delimiter, update nextContinueMarker
-                 * to be able to skip ranges of the form prefix/subprefix/ as an optimization.
-                 * The marker may also end up being prefix/, in which case .skipping will determine
-                 * if a skip over the full range is allowed or a smaller skipping range of prefix/{VID_SEP}
-                 * must be used. */
-                this[this.nextContinueMarker] = key.slice(0, key.lastIndexOf(this.delimiter) + 1);
-            }
-            return FILTER_SKIP;
-        }
-
-        this.prvKey = key;
-        if (this.delimiter) {
-            // check if the key has the delimiter
-            const baseIndex = this.prefix ? this.prefix.length : 0;
-            const delimiterIndex = key.indexOf(this.delimiter, baseIndex);
-            if (delimiterIndex >= 0) {
-                // try to add the prefix to the list
-                return this.addCommonPrefix(key, delimiterIndex);
-            }
-        }
-        return this.addContents(key, value);
-    }
-
-    /**
-     *  Filter to apply on each iteration for buckets in v1 format,
-     *  based on:
-     *  - prefix
-     *  - delimiter
-     *  - maxKeys
-     *  The marker is being handled directly by levelDB
-     *  @param {Object} obj       - The key and value of the element
-     *  @param {String} obj.key   - The key of the element
-     *  @param {String} obj.value - The value of the element
-     *  @return {number}          - indicates if iteration should continue
-     */
-    filterV1(obj) {
-        // Filtering master keys in v1 is simply listing the master
-        // keys, as the state of version keys do not change the
-        // result, so we can use Delimiter method directly.
-        return super.filter(obj);
-    }
-
-    /**
-     * Determine if a nextContinueMarker ending with a delimiter
-     * can be skipped.
-     * @returns {bool}
-     */
-
-    allowDelimiterRangeSkip() {
-        if (!this.prefixKeySeen) {
-            // A prefix key is a master key equal to the prefix. If it has
-            // not been encountered, can skip.
-            return true;
-        }
-        const marker = this[this.nextContinueMarker];
-        // prefix = prefix, key = prefix/. Can skip since key will be part of commonPrefixes.
-        if (marker.length > this.prefix.length && marker.startsWith(this.prefix)) {
-            return true;
-        }
-        const lastIdx = marker.lastIndexOf(this.delimiter); // prefix/foo is a masterKey following a prefix key.
-        return marker.slice(0, lastIdx + 1) !== this.prefix; // cannot skip the full range prefix/ range.
-    }
-
-    skippingBase() {
-        if (this[this.nextContinueMarker]) {
-            // next marker or next continuation token:
-            // - foo/ : skipping foo/
-            // - foo  : skipping foo.
-            const index = this[this.nextContinueMarker].
-                lastIndexOf(this.delimiter);
-            if (index === this[this.nextContinueMarker].length - 1 && this.allowDelimiterRangeSkip()) {
-                return this[this.nextContinueMarker];
-            }
-            return this[this.nextContinueMarker] + VID_SEP;
-        }
-        return SKIP_NONE;
-    }
-
-    skippingV0() {
-        if (this.inReplayPrefix) {
-            return DbPrefixes.Replay;
-        }
-        return this.skippingBase();
-    }
-
-    skippingV1() {
-        const skipTo = this.skippingBase();
-        if (skipTo === SKIP_NONE) {
-            return SKIP_NONE;
-        }
-        return DbPrefixes.Master + skipTo;
-    }
-}
-
-module.exports = { DelimiterMaster };

lib/algos/list/delimiterMaster.ts

@@ -0,0 +1,171 @@
+import {
+    Delimiter,
+    FilterState,
+    DelimiterFilterStateId,
+    DelimiterFilterState_NotSkipping,
+    DelimiterFilterState_SkippingPrefix,
+} from './delimiter';
+const Version = require('../../versioning/Version').Version;
+const VSConst = require('../../versioning/constants').VersioningConstants;
+const { BucketVersioningKeyFormat } = VSConst;
+const { FILTER_ACCEPT, FILTER_SKIP } = require('./tools');
+
+const VID_SEP = VSConst.VersionId.Separator;
+const { DbPrefixes } = VSConst;
+
+const enum DelimiterMasterFilterStateId {
+    SkippingVersionsV0 = 101,
+    WaitVersionAfterPHDV0 = 102,
+};
+
+interface DelimiterMasterFilterState_SkippingVersionsV0 extends FilterState {
+    id: DelimiterMasterFilterStateId.SkippingVersionsV0,
+    masterKey: string,
+};
+
+interface DelimiterMasterFilterState_WaitVersionAfterPHDV0 extends FilterState {
+    id: DelimiterMasterFilterStateId.WaitVersionAfterPHDV0,
+    masterKey: string,
+};
+
+/**
+ * Handle object listing with parameters. This extends the base class Delimiter
+ * to return the raw master versions of existing objects.
+ */
+export class DelimiterMaster extends Delimiter {
+
+    /**
+     * Delimiter listing of master versions.
+     * @param {Object}  parameters            - listing parameters
+     * @param {String}  parameters.delimiter  - delimiter per amazon format
+     * @param {String}  parameters.prefix     - prefix per amazon format
+     * @param {String}  parameters.marker     - marker per amazon format
+     * @param {Number}  parameters.maxKeys    - number of keys to list
+     * @param {Boolean} parameters.v2         - indicates whether v2 format
+     * @param {String}  parameters.startAfter - marker per amazon v2 format
+     * @param {String}  parameters.continuationToken - obfuscated amazon token
+     * @param {RequestLogger} logger          - The logger of the request
+     * @param {String} [vFormat]              - versioning key format
+     */
+    constructor(parameters, logger, vFormat) {
+        super(parameters, logger, vFormat);
+
+        Object.assign(this, {
+            [BucketVersioningKeyFormat.v0]: {
+                skipping: this.skippingV0,
+            },
+            [BucketVersioningKeyFormat.v1]: {
+                skipping: this.skippingV1,
+            },
+        }[this.vFormat]);
+
+        if (vFormat === BucketVersioningKeyFormat.v0) {
+            // override Delimiter's implementation of NotSkipping for
+            // DelimiterMaster logic (skipping versions and special
+            // handling of delete markers and PHDs)
+            this.setKeyHandler(
+                DelimiterFilterStateId.NotSkipping,
+                this.keyHandler_NotSkippingPrefixNorVersionsV0.bind(this));
+
+            // add extra state handlers specific to DelimiterMaster with v0 format
+            this.setKeyHandler(
+                DelimiterMasterFilterStateId.SkippingVersionsV0,
+                this.keyHandler_SkippingVersionsV0.bind(this));
+
+            this.setKeyHandler(
+                DelimiterMasterFilterStateId.WaitVersionAfterPHDV0,
+                this.keyHandler_WaitVersionAfterPHDV0.bind(this));
+
+            if (this.marker) {
+                // distinct initial state to include some special logic
+                // before the first master key is found that does not have
+                // to be checked afterwards
+                this.state = <DelimiterMasterFilterState_SkippingVersionsV0> {
+                    id: DelimiterMasterFilterStateId.SkippingVersionsV0,
+                    masterKey: this.marker,
+                };
+            } else {
+                this.state = <DelimiterFilterState_NotSkipping> {
+                    id: DelimiterFilterStateId.NotSkipping,
+                };
+            }
+        }
+        // in v1, we can directly use Delimiter's implementation,
+        // which is already set to the proper state
+    }
+
+    filter_onNewMasterKeyV0(key, value) {
+        // update the state to start skipping versions of the new master key
+        this.setState(<DelimiterMasterFilterState_SkippingVersionsV0> {
+            id: DelimiterMasterFilterStateId.SkippingVersionsV0,
+            masterKey: key,
+        });
+        // if this master key is a delete marker, accept it without
+        // adding the version to the contents
+        if (Version.isDeleteMarker(value)) {
+            return FILTER_ACCEPT;
+        }
+        if (Version.isPHD(value)) {
+            // master version is a PHD version: wait for the first
+            // following version that will be considered as the actual
+            // master key
+            this.setState(<DelimiterMasterFilterState_WaitVersionAfterPHDV0> {
+                id: DelimiterMasterFilterStateId.WaitVersionAfterPHDV0,
+                masterKey: key,
+            });
+            return FILTER_ACCEPT;
+        }
+        if (key.startsWith(DbPrefixes.Replay)) {
+            // skip internal replay prefix entirely
+            this.setState(<DelimiterFilterState_SkippingPrefix> {
+                id: DelimiterFilterStateId.SkippingPrefix,
+                prefix: DbPrefixes.Replay,
+            });
+            return FILTER_SKIP;
+        }
+        return this.addCommonPrefixOrContents(key, value);
+    }
+
+    keyHandler_NotSkippingPrefixNorVersionsV0(key, value) {
+        return this.filter_onNewMasterKeyV0(key, value);
+    }
+
+    keyHandler_SkippingVersionsV0(key, value) {
+        /* In the SkippingVersionsV0 state, skip all version keys
+         * (<key><versionIdSeparator><version>) */
+        const versionIdIndex = key.indexOf(VID_SEP);
+        if (versionIdIndex !== -1) {
+            return FILTER_SKIP;
+        }
+        return this.filter_onNewMasterKeyV0(key, value);
+    }
+
+    keyHandler_WaitVersionAfterPHDV0(key, value) {
+        // After a PHD key is encountered, the next version key of the
+        // same object if it exists is the new master key, hence
+        // consider it as such and call 'onNewMasterKeyV0' (the test
+        // 'masterKey == phdKey' is probably redundant when we already
+        // know we have a versioned key, since all objects in v0 have
+        // a master key, but keeping it in doubt)
+        const { masterKey: phdKey } = <DelimiterMasterFilterState_WaitVersionAfterPHDV0> this.state;
+        const versionIdIndex = key.indexOf(VID_SEP);
+        if (versionIdIndex !== -1) {
+            const masterKey = key.slice(0, versionIdIndex);
+            if (masterKey === phdKey) {
+                return this.filter_onNewMasterKeyV0(masterKey, value);
+            }
+        }
+        return this.filter_onNewMasterKeyV0(key, value);
+    }
+
+    skippingBase(): string | undefined {
+        switch (this.state.id) {
+        case DelimiterMasterFilterStateId.SkippingVersionsV0:
+            const { masterKey } = <DelimiterMasterFilterState_SkippingVersionsV0> this.state;
+            return masterKey + VID_SEP;
+
+        default:
+            return super.skippingBase();
+        }
+    }
+}

lib/algos/list/delimiterVersions.js

@@ -151,6 +151,27 @@ class DelimiterVersions extends Delimiter {
         return FILTER_ACCEPT;
     }
 
+    /**
+     * Add a Common Prefix in the list
+     * @param {String} key   - object name
+     * @param {Number} index - after prefix starting point
+     * @return {Boolean}     - indicates if iteration should continue
+     */
+    addCommonPrefix(key, index) {
+        const commonPrefix = key.substring(0, index + this.delimiter.length);
+        if (this.CommonPrefixes.indexOf(commonPrefix) === -1
+                && this.NextMarker !== commonPrefix) {
+            if (this._reachedMaxKeys()) {
+                return FILTER_END;
+            }
+            this.CommonPrefixes.push(commonPrefix);
+            this.NextMarker = commonPrefix;
+            ++this.keys;
+            return FILTER_ACCEPT;
+        }
+        return FILTER_SKIP;
+    }
+
     /**
      *  Filter to apply on each iteration if bucket is in v0
      *  versioning key format, based on:

package.json

@@ -62,7 +62,6 @@
     "@types/jest": "^27.4.1",
     "@types/node": "^17.0.21",
     "@types/xml2js": "^0.4.11",
-    "chance": "^1.1.8",
     "eslint": "^8.12.0",
     "eslint-config-airbnb": "6.2.0",
     "eslint-config-scality": "scality/Guidelines#7.10.2",

tests/unit/algos/list/delimiter.spec.js

@@ -7,23 +7,17 @@ const DelimiterMaster =
     require('../../../../lib/algos/list/delimiterMaster').DelimiterMaster;
 const Werelogs = require('werelogs').Logger;
 const logger = new Werelogs('listTest');
-const performListing = require('../../../utils/performListing');
 const zpad = require('../../helpers').zpad;
 const { inc } = require('../../../../lib/algos/list/tools');
 const VSConst = require('../../../../lib/versioning/constants').VersioningConstants;
 const { DbPrefixes } = VSConst;
 
 class Test {
-    constructor(name, input, genMDParams, output, filter) {
+    constructor(name, input, genMDParams, output) {
         this.name = name;
         this.input = input;
         this.genMDParams = genMDParams;
         this.output = output;
-        this.filter = filter || this._defaultFilter;
-    }
-
-    _defaultFilter() {
-        return true;
     }
 }
 
@@ -33,7 +27,7 @@ const valueDeleteMarker = '{"hello":"world","isDeleteMarker":"true"}';
 const data = [
     { key: 'Pâtisserie=中文-español-English', value },
     { key: 'notes/spring/1.txt', value },
-    { key: 'notes/spring/2.txt', value },
+    { key: 'notes/spring/4.txt', value },
     { key: 'notes/spring/march/1.txt', value },
     { key: 'notes/summer/1.txt', value },
     { key: 'notes/summer/2.txt', value },
@@ -56,6 +50,9 @@ const dataVersioned = [
     { key: 'notes/spring/2.txt\0foo', value },
     { key: 'notes/spring/3.txt', value: valueDeleteMarker },
     { key: 'notes/spring/3.txt\0foo', value },
+    { key: 'notes/spring/4.txt', value: valuePHD },
+    { key: 'notes/spring/4.txt\0bar', value },
+    { key: 'notes/spring/4.txt\0foo', value },
     { key: 'notes/spring/march/1.txt', value },
     { key: 'notes/spring/march/1.txt\0bar', value },
     { key: 'notes/spring/march/1.txt\0foo', value },
@@ -78,15 +75,8 @@ const dataVersioned = [
     { key: 'notes/yore.rs', value },
     { key: 'notes/zaphod/Beeblebrox.txt', value },
 ];
-const nonAlphabeticalData = [
-    { key: 'zzz', value },
-    { key: 'aaa', value },
-];
 
 const receivedData = data.map(item => ({ key: item.key, value: item.value }));
-const receivedNonAlphaData = nonAlphabeticalData.map(
-    item => ({ key: item.key, value: item.value }),
-);
 
 const tests = [
     new Test('all elements', {}, {
@@ -124,7 +114,7 @@ const tests = [
         Delimiter: undefined,
         IsTruncated: false,
         NextMarker: undefined,
-    }, (e, input) => e.key > input.marker),
+    }),
     new Test('with bad marker', {
         marker: 'zzzz',
         delimiter: '/',
@@ -142,7 +132,7 @@ const tests = [
         Delimiter: '/',
         IsTruncated: false,
         NextMarker: undefined,
-    }, (e, input) => e.key > input.marker),
+    }),
     new Test('with makKeys', {
         maxKeys: 3,
     }, {
@@ -219,12 +209,12 @@ const tests = [
         marker: 'notes/summer0',
     }, {
         v0: {
-            gt: `notes/summer${inc('/')}`,
-            lt: `notes/summer${inc('/')}`,
+            gt: 'notes/summer0',
+            lt: 'notes/summer0',
         },
         v1: {
-            gt: `${DbPrefixes.Master}notes/summer${inc('/')}`,
-            lt: `${DbPrefixes.Master}notes/summer${inc('/')}`,
+            gt: `${DbPrefixes.Master}notes/summer0`,
+            lt: `${DbPrefixes.Master}notes/summer0`,
         },
     }, {
         Contents: [],
@@ -232,18 +222,18 @@ const tests = [
         Delimiter: '/',
         IsTruncated: false,
         NextMarker: undefined,
-    }, (e, input) => e.key > input.marker),
+    }),
     new Test('delimiter and prefix (related to #147)', {
         delimiter: '/',
         prefix: 'notes/',
     }, {
         v0: {
             gte: 'notes/',
-            lt: `notes${inc('/')}`,
+            lt: 'notes0',
         },
         v1: {
             gte: `${DbPrefixes.Master}notes/`,
-            lt: `${DbPrefixes.Master}notes${inc('/')}`,
+            lt: `${DbPrefixes.Master}notes0`,
         },
     }, {
         Contents: [
@@ -266,11 +256,11 @@ const tests = [
     }, {
         v0: {
             gt: 'notes/year.txt',
-            lt: `notes${inc('/')}`,
+            lt: 'notes0',
         },
         v1: {
             gt: `${DbPrefixes.Master}notes/year.txt`,
-            lt: `${DbPrefixes.Master}notes${inc('/')}`,
+            lt: `${DbPrefixes.Master}notes0`,
         },
     }, {
         Contents: [
@@ -282,8 +272,8 @@ const tests = [
         Delimiter: '/',
         IsTruncated: false,
         NextMarker: undefined,
-    }, (e, input) => e.key > input.marker),
-    new Test('all parameters 1/3', {
+    }),
+    new Test('all parameters 1/5', {
         delimiter: '/',
         prefix: 'notes/',
         marker: 'notes/',
@@ -291,55 +281,55 @@ const tests = [
     }, {
         v0: {
             gt: 'notes/',
-            lt: `notes${inc('/')}`,
+            lt: 'notes0',
         },
         v1: {
             gt: `${DbPrefixes.Master}notes/`,
-            lt: `${DbPrefixes.Master}notes${inc('/')}`,
+            lt: `${DbPrefixes.Master}notes0`,
         },
     }, {
         Contents: [],
         CommonPrefixes: ['notes/spring/'],
         Delimiter: '/',
         IsTruncated: true,
-        NextMarker: 'notes/spring/',
-    }, (e, input) => e.key > input.marker),
+        NextMarker: 'notes/spring/1.txt',
+    }),
 
-    new Test('all parameters 2/3', {
+    new Test('all parameters 2/5', {
         delimiter: '/',
-        prefix: 'notes/', // prefix
-        marker: 'notes/spring/',
+        prefix: 'notes/',
+        marker: 'notes/spring/1.txt',
         maxKeys: 1,
     }, {
         v0: {
-            gt: 'notes/spring/',
-            lt: `notes${inc('/')}`,
+            gte: 'notes/spring0',
+            lt: 'notes0',
         },
         v1: {
-            gt: `${DbPrefixes.Master}notes/spring/`,
-            lt: `${DbPrefixes.Master}notes${inc('/')}`,
+            gte: `${DbPrefixes.Master}notes/spring0`,
+            lt: `${DbPrefixes.Master}notes0`,
         },
     }, {
         Contents: [],
         CommonPrefixes: ['notes/summer/'],
         Delimiter: '/',
         IsTruncated: true,
-        NextMarker: 'notes/summer/',
-    }, (e, input) => e.key > input.marker),
+        NextMarker: 'notes/summer/1.txt',
+    }),
 
-    new Test('all parameters 3/3', {
+    new Test('all parameters 3/5', {
         delimiter: '/',
-        prefix: 'notes/', // prefix
-        marker: 'notes/summer/',
+        prefix: 'notes/',
+        marker: 'notes/summer/1.txt',
         maxKeys: 1,
     }, {
         v0: {
-            gt: 'notes/summer/',
-            lt: `notes${inc('/')}`,
+            gte: 'notes/summer0',
+            lt: 'notes0',
         },
         v1: {
-            gt: `${DbPrefixes.Master}notes/summer/`,
-            lt: `${DbPrefixes.Master}notes${inc('/')}`,
+            gte: `${DbPrefixes.Master}notes/summer0`,
+            lt: `${DbPrefixes.Master}notes0`,
         },
     }, {
         Contents: [
@@ -349,21 +339,21 @@ const tests = [
         Delimiter: '/',
         IsTruncated: true,
         NextMarker: 'notes/year.txt',
-    }, (e, input) => e.key > input.marker),
+    }),
 
-    new Test('all parameters 4/3', {
+    new Test('all parameters 4/5', {
         delimiter: '/',
-        prefix: 'notes/', // prefix
+        prefix: 'notes/',
         marker: 'notes/year.txt',
         maxKeys: 1,
     }, {
         v0: {
             gt: 'notes/year.txt',
-            lt: `notes${inc('/')}`,
+            lt: 'notes0',
         },
         v1: {
             gt: `${DbPrefixes.Master}notes/year.txt`,
-            lt: `${DbPrefixes.Master}notes${inc('/')}`,
+            lt: `${DbPrefixes.Master}notes0`,
         },
     }, {
         Contents: [
@@ -373,9 +363,9 @@ const tests = [
         Delimiter: '/',
         IsTruncated: true,
         NextMarker: 'notes/yore.rs',
-    }, (e, input) => e.key > input.marker),
+    }),
 
-    new Test('all parameters 5/3', {
+    new Test('all parameters 5/5', {
         delimiter: '/',
         prefix: 'notes/',
         marker: 'notes/yore.rs',
@@ -383,11 +373,11 @@ const tests = [
     }, {
         v0: {
             gt: 'notes/yore.rs',
-            lt: `notes${inc('/')}`,
+            lt: 'notes0',
         },
         v1: {
             gt: `${DbPrefixes.Master}notes/yore.rs`,
-            lt: `${DbPrefixes.Master}notes${inc('/')}`,
+            lt: `${DbPrefixes.Master}notes0`,
         },
     }, {
         Contents: [],
@@ -395,7 +385,7 @@ const tests = [
         Delimiter: '/',
         IsTruncated: false,
         NextMarker: undefined,
-    }, (e, input) => e.key > input.marker),
+    }),
 
     new Test('all elements v2', {
         v2: true,
@@ -435,7 +425,7 @@ const tests = [
         Delimiter: undefined,
         IsTruncated: false,
         NextContinuationToken: undefined,
-    }, (e, input) => e.key > input.startAfter),
+    }),
     new Test('with bad startAfter', {
         startAfter: 'zzzz',
         delimiter: '/',
@@ -454,7 +444,7 @@ const tests = [
         Delimiter: '/',
         IsTruncated: false,
         NextContinuationToken: undefined,
-    }, (e, input) => e.key > input.startAfter),
+    }),
     new Test('with valid continuationToken', {
         continuationToken: receivedData[4].key,
         v2: true,
@@ -478,7 +468,7 @@ const tests = [
         Delimiter: undefined,
         IsTruncated: false,
         NextContinuationToken: undefined,
-    }, (e, input) => e.key > input.continuationToken),
+    }),
     new Test('with bad continuationToken', {
         continuationToken: 'zzzz',
         delimiter: '/',
@@ -497,47 +487,49 @@ const tests = [
         Delimiter: '/',
         IsTruncated: false,
         NextContinuationToken: undefined,
-    }, (e, input) => e.key > input.continuationToken),
+    }),
     new Test('bad startAfter and good prefix', {
         delimiter: '/',
         prefix: 'notes/summer/',
         startAfter: 'notes/summer0',
+        v2: true,
     }, {
         v0: {
-            gte: 'notes/summer/',
-            lt: `notes/summer${inc('/')}`,
+            gt: 'notes/summer0',
+            lt: 'notes/summer0',
         },
         v1: {
-            gte: `${DbPrefixes.Master}notes/summer/`,
-            lt: `${DbPrefixes.Master}notes/summer${inc('/')}`,
+            gt: `${DbPrefixes.Master}notes/summer0`,
+            lt: `${DbPrefixes.Master}notes/summer0`,
         },
     }, {
         Contents: [],
         CommonPrefixes: [],
         Delimiter: '/',
         IsTruncated: false,
-        NextMarker: undefined,
-    }, (e, input) => e.key > input.startAfter),
+        NextContinuationToken: undefined,
+    }),
     new Test('bad continuation token and good prefix', {
         delimiter: '/',
         prefix: 'notes/summer/',
         continuationToken: 'notes/summer0',
+        v2: true,
     }, {
         v0: {
-            gte: 'notes/summer/',
-            lt: `notes/summer${inc('/')}`,
+            gt: 'notes/summer0',
+            lt: 'notes/summer0',
         },
         v1: {
-            gte: `${DbPrefixes.Master}notes/summer/`,
-            lt: `${DbPrefixes.Master}notes/summer${inc('/')}`,
+            gt: `${DbPrefixes.Master}notes/summer0`,
+            lt: `${DbPrefixes.Master}notes/summer0`,
         },
     }, {
         Contents: [],
         CommonPrefixes: [],
         Delimiter: '/',
         IsTruncated: false,
-        NextMarker: undefined,
-    }, (e, input) => e.key > input.continuationToken),
+        NextContinuationToken: undefined,
+    }),
 
     new Test('no delimiter v2', {
         startAfter: 'notes/year.txt',
@@ -559,9 +551,9 @@ const tests = [
         Delimiter: undefined,
         IsTruncated: true,
         NextContinuationToken: 'notes/yore.rs',
-    }, (e, input) => e.key > input.startAfter),
+    }),
 
-    new Test('all parameters v2 1/6', {
+    new Test('all parameters v2 1/5', {
         delimiter: '/',
         prefix: 'notes/',
         startAfter: 'notes/',
@@ -570,57 +562,57 @@ const tests = [
     }, {
         v0: {
             gt: 'notes/',
-            lt: `notes${inc('/')}`,
+            lt: 'notes0',
         },
         v1: {
             gt: `${DbPrefixes.Master}notes/`,
-            lt: `${DbPrefixes.Master}notes${inc('/')}`,
+            lt: `${DbPrefixes.Master}notes0`,
         },
     }, {
         Contents: [],
         CommonPrefixes: ['notes/spring/'],
         Delimiter: '/',
         IsTruncated: true,
-        NextContinuationToken: 'notes/spring/',
-    }, (e, input) => e.key > input.startAfter),
+        NextContinuationToken: 'notes/spring/1.txt',
+    }),
 
-    new Test('all parameters v2 2/6', {
+    new Test('all parameters v2 2/5', {
         delimiter: '/',
         prefix: 'notes/',
-        continuationToken: 'notes/spring/',
+        continuationToken: 'notes/spring/1.txt',
         maxKeys: 1,
         v2: true,
     }, {
         v0: {
-            gt: 'notes/spring/',
-            lt: `notes${inc('/')}`,
+            gte: 'notes/spring0',
+            lt: 'notes0',
         },
         v1: {
-            gt: `${DbPrefixes.Master}notes/spring/`,
-            lt: `${DbPrefixes.Master}notes${inc('/')}`,
+            gte: `${DbPrefixes.Master}notes/spring0`,
+            lt: `${DbPrefixes.Master}notes0`,
         },
     }, {
         Contents: [],
         CommonPrefixes: ['notes/summer/'],
         Delimiter: '/',
         IsTruncated: true,
-        NextContinuationToken: 'notes/summer/',
-    }, (e, input) => e.key > input.continuationToken),
+        NextContinuationToken: 'notes/summer/1.txt',
+    }),
 
     new Test('all parameters v2 3/5', {
         delimiter: '/',
         prefix: 'notes/',
-        continuationToken: 'notes/summer/',
+        continuationToken: 'notes/summer/1.txt',
         maxKeys: 1,
         v2: true,
     }, {
         v0: {
-            gt: 'notes/summer/',
-            lt: `notes${inc('/')}`,
+            gte: 'notes/summer0',
+            lt: 'notes0',
         },
         v1: {
-            gt: `${DbPrefixes.Master}notes/summer/`,
-            lt: `${DbPrefixes.Master}notes${inc('/')}`,
+            gte: `${DbPrefixes.Master}notes/summer0`,
+            lt: `${DbPrefixes.Master}notes0`,
         },
     }, {
         Contents: [
@@ -630,7 +622,7 @@ const tests = [
         Delimiter: '/',
         IsTruncated: true,
         NextContinuationToken: 'notes/year.txt',
-    }, (e, input) => e.key > input.continuationToken),
+    }),
 
     new Test('all parameters v2 4/5', {
         delimiter: '/',
@@ -641,11 +633,11 @@ const tests = [
     }, {
         v0: {
             gt: 'notes/year.txt',
-            lt: `notes${inc('/')}`,
+            lt: 'notes0',
         },
         v1: {
             gt: `${DbPrefixes.Master}notes/year.txt`,
-            lt: `${DbPrefixes.Master}notes${inc('/')}`,
+            lt: `${DbPrefixes.Master}notes0`,
         },
     }, {
         Contents: [
@@ -655,7 +647,7 @@ const tests = [
         Delimiter: '/',
         IsTruncated: true,
         NextContinuationToken: 'notes/yore.rs',
-    }, (e, input) => e.key > input.startAfter),
+    }),
 
     new Test('all parameters v2 5/5', {
         delimiter: '/',
@@ -666,11 +658,11 @@ const tests = [
     }, {
         v0: {
             gt: 'notes/yore.rs',
-            lt: `notes${inc('/')}`,
+            lt: 'notes0',
         },
         v1: {
             gt: `${DbPrefixes.Master}notes/yore.rs`,
-            lt: `${DbPrefixes.Master}notes${inc('/')}`,
+            lt: `${DbPrefixes.Master}notes0`,
         },
     }, {
         Contents: [],
@@ -678,35 +670,11 @@ const tests = [
         Delimiter: '/',
         IsTruncated: false,
         NextContinuationToken: undefined,
-    }, (e, input) => e.key > input.startAfter),
-
+    }),
 ];
 
-const alphabeticalOrderTests = [
-    {
-        params: {},
-        expectedValue: true,
-    }, {
-        params: {
-            alphabeticalOrder: undefined,
-        },
-        expectedValue: true,
-    }, {
-        params: {
-            alphabeticalOrder: true,
-        },
-        expectedValue: true,
-    }, {
-        params: {
-            alphabeticalOrder: false,
-        },
-        expectedValue: false,
-    },
-];
-
-function getTestListing(test, data, vFormat) {
+function getTestListing(mdParams, data, vFormat) {
     return data
-        .filter(e => test.filter(e, test.input))
         .map(obj => {
             if (vFormat === 'v0') {
                 return obj;
@@ -718,7 +686,12 @@ function getTestListing(test, data, vFormat) {
                 };
             }
             return assert.fail(`bad format ${vFormat}`);
-        });
+        })
+        .filter(e =>
+            (!mdParams.gt || e.key > mdParams.gt) &&
+            (!mdParams.gte || e.key >= mdParams.gte) &&
+            (!mdParams.lt || e.key < mdParams.lt),
+        );
 }
 
 ['v0', 'v1'].forEach(vFormat => {
@@ -735,15 +708,6 @@ function getTestListing(test, data, vFormat) {
                 `${vFormat === 'v1' ? DbPrefixes.Master : ''}foo/`);
         });
 
-        it('Should set Delimiter alphabeticalOrder field to the expected value', () => {
-            alphabeticalOrderTests.forEach(test => {
-                const delimiter = new Delimiter(test.params);
-                assert.strictEqual(delimiter.alphabeticalOrder,
-                    test.expectedValue,
-                    `${JSON.stringify(test.params)}`);
-            });
-        });
-
         tests.forEach(test => {
             it(`Should return metadata listing params to list ${test.name}`, () => {
                 const listing = new Delimiter(test.input, logger, vFormat);
@@ -751,9 +715,13 @@ function getTestListing(test, data, vFormat) {
                 assert.deepStrictEqual(params, test.genMDParams[vFormat]);
             });
             it(`Should list ${test.name}`, () => {
-                // Simulate skip scan done by LevelDB
-                const d = getTestListing(test, data, vFormat);
-                const res = performListing(d, Delimiter, test.input, logger, vFormat);
+                const listing = new Delimiter(test.input, logger, vFormat);
+                const mdParams = listing.genMDParams();
+                const rawEntries = getTestListing(mdParams, data, vFormat);
+                for (const entry of rawEntries) {
+                    listing.filter(entry);
+                }
+                const res = listing.result();
                 assert.deepStrictEqual(res, test.output);
             });
         });
@@ -762,49 +730,16 @@ function getTestListing(test, data, vFormat) {
         if (vFormat === 'v0') {
             tests.forEach(test => {
                 it(`Should list master versions ${test.name}`, () => {
-                    // Simulate skip scan done by LevelDB
-                    const d = dataVersioned.filter(e => test.filter(e, test.input));
-                    const res = performListing(d, DelimiterMaster, test.input, logger, vFormat);
+                    const listing = new DelimiterMaster(test.input, logger, vFormat);
+                    const mdParams = listing.genMDParams();
+                    const rawEntries = getTestListing(mdParams, dataVersioned, vFormat);
+                    for (const entry of rawEntries) {
+                        listing.filter(entry);
+                    }
+                    const res = listing.result();
                     assert.deepStrictEqual(res, test.output);
                 });
             });
         }
-
-        it('Should filter values according to alphabeticalOrder parameter', () => {
-            let test = new Test('alphabeticalOrder parameter set', {
-                delimiter: '/',
-                alphabeticalOrder: true,
-            }, {
-            }, {
-                Contents: [
-                    receivedNonAlphaData[0],
-                ],
-                Delimiter: '/',
-                CommonPrefixes: [],
-                IsTruncated: false,
-                NextMarker: undefined,
-            });
-            let d = getTestListing(test, nonAlphabeticalData, vFormat);
-            let res = performListing(d, Delimiter, test.input, logger, vFormat);
-            assert.deepStrictEqual(res, test.output);
-
-            test = new Test('alphabeticalOrder parameter set', {
-                delimiter: '/',
-                alphabeticalOrder: false,
-            }, {
-            }, {
-                Contents: [
-                    receivedNonAlphaData[0],
-                    receivedNonAlphaData[1],
-                ],
-                Delimiter: '/',
-                CommonPrefixes: [],
-                IsTruncated: false,
-                NextMarker: undefined,
-            });
-            d = getTestListing(test, nonAlphabeticalData, vFormat);
-            res = performListing(d, Delimiter, test.input, logger, vFormat);
-            assert.deepStrictEqual(res, test.output);
-        });
     });
 });

yarn.lock

@@ -2144,11 +2144,6 @@ chalk@^4.0.0:
     ansi-styles "^4.1.0"
     supports-color "^7.1.0"
 
-chance@^1.1.8:
-  version "1.1.8"
-  resolved "https://registry.yarnpkg.com/chance/-/chance-1.1.8.tgz#5d6c2b78c9170bf6eb9df7acdda04363085be909"
-  integrity sha512-v7fi5Hj2VbR6dJEGRWLmJBA83LJMS47pkAbmROFxHWd9qmE1esHRZW8Clf1Fhzr3rjxnNZVCjOEv/ivFxeIMtg==
-
 char-regex@^1.0.2:
   version "1.0.2"
   resolved "https://registry.yarnpkg.com/char-regex/-/char-regex-1.0.2.tgz#d744358226217f981ed58f479b1d6bcc29545dcf"