wip

.github/workflows/codeql.yaml

@@ -17,9 +17,9 @@ jobs:
         uses: actions/checkout@v4
 
       - name: Initialize CodeQL
-        uses: github/codeql-action/init@v3
+        uses: github/codeql-action/init@v2
         with:
           languages: javascript, typescript
 
       - name: Build and analyze
-        uses: github/codeql-action/analyze@v3
+        uses: github/codeql-action/analyze@v2

.github/workflows/dependency-review.yaml

@@ -13,4 +13,4 @@ jobs:
         uses: actions/checkout@v4
 
       - name: 'Dependency Review'
-        uses: actions/dependency-review-action@v4
+        uses: actions/dependency-review-action@v3

.github/workflows/tests.yaml

@@ -46,9 +46,7 @@ jobs:
       run: yarn --silent coverage
     - name: run functional tests
       run: yarn ft_test
-    - uses: codecov/codecov-action@v4
+    - uses: codecov/codecov-action@v3
-      with:
-        token: ${{ secrets.CODECOV_TOKEN }}
     - name: run executables tests
       run: yarn install && yarn test
       working-directory: 'lib/executables/pensieveCreds/'
@@ -72,7 +70,7 @@ jobs:
       run: yarn build
       continue-on-error: true # TODO ARSN-97 Remove it when no errors in TS
     - name: Upload artifacts
-      uses: scality/action-artifacts@v4
+      uses: scality/action-artifacts@v3
       with:
         url: https://artifacts.scality.net
         user: ${{ secrets.ARTIFACTS_USER }}

.swcrc

@@ -1,12 +0,0 @@
-{
-  "$schema": "https://swc.rs/schema.json",
-  "jsc": {
-    "parser": {
-      "syntax": "typescript"
-    },
-    "target": "es2017"
-  },
-  "module": {
-    "type": "commonjs"
-  }
-}

documentation/BucketInfoModelVersion.md

@@ -246,15 +246,3 @@ For capacity-enabled buckets, contains the following data:
 ### Usage
 
 Used to store bucket tagging
-
-## Model version 17
-
-### Properties Added
-
-```javascript
-this._quotaMax = quotaMax || 0;
-```
-
-### Usage
-
-Used to store bucket quota

index.ts

@@ -1,9 +1,6 @@
 import * as evaluators from './lib/policyEvaluator/evaluator';
 import evaluatePrincipal from './lib/policyEvaluator/principal';
-import RequestContext, {
+import RequestContext from './lib/policyEvaluator/RequestContext';
-    actionNeedQuotaCheck,
-    actionNeedQuotaCheckCopy,
-    actionWithDataDeletion } from './lib/policyEvaluator/RequestContext';
 import * as requestUtils from './lib/policyEvaluator/requestUtils';
 import * as actionMaps from './lib/policyEvaluator/utils/actionMaps';
 import { validateUserPolicy } from './lib/policy/policyValidator'
@@ -52,8 +49,6 @@ export const algorithms = {
         Skip: require('./lib/algos/list/skip'),
     },
     cache: {
-        GapSet: require('./lib/algos/cache/GapSet'),
-        GapCache: require('./lib/algos/cache/GapCache'),
         LRUCache: require('./lib/algos/cache/LRUCache'),
     },
     stream: {
@@ -70,9 +65,6 @@ export const policies = {
     RequestContext,
     requestUtils,
     actionMaps,
-    actionNeedQuotaCheck,
-    actionWithDataDeletion,
-    actionNeedQuotaCheckCopy,
 };
 
 export const testing = {

lib/algos/cache/GapCache.ts

@@ -1,363 +0,0 @@
-import { OrderedSet } from '@js-sdsl/ordered-set';
-import {
-    default as GapSet,
-    GapSetEntry,
-} from './GapSet';
-
-// the API is similar but is not strictly a superset of GapSetInterface
-// so we don't extend from it
-export interface GapCacheInterface {
-    exposureDelayMs: number;
-    maxGapWeight: number;
-    size: number;
-
-    setGap: (firstKey: string, lastKey: string, weight: number) => void;
-    removeOverlappingGaps: (overlappingKeys: string[]) => number;
-    lookupGap: (minKey: string, maxKey?: string) => Promise<GapSetEntry | null>;
-    [Symbol.iterator]: () => Iterator<GapSetEntry>;
-    toArray: () => GapSetEntry[];
-};
-
-class GapCacheUpdateSet {
-    newGaps: GapSet;
-    updatedKeys: OrderedSet<string>;
-
-    constructor(maxGapWeight: number) {
-        this.newGaps = new GapSet(maxGapWeight);
-        this.updatedKeys = new OrderedSet();
-    }
-
-    addUpdateBatch(updatedKeys: OrderedSet<string>): void {
-        this.updatedKeys.union(updatedKeys);
-    }
-};
-
-/**
- * Cache of listing "gaps" i.e. ranges of keys that can be skipped
- * over during listing (because they only contain delete markers as
- * latest versions).
- *
- * Typically, a single GapCache instance would be attached to a raft session.
- *
- * The API usage is as follows:
- *
- * - Initialize a GapCache instance by calling start() (this starts an internal timer)
- *
- * - Insert a gap or update an existing one via setGap()
- *
- * - Lookup existing gaps via lookupGap()
- *
- * - Invalidate gaps that overlap a specific set of keys via removeOverlappingGaps()
- *
- * - Shut down a GapCache instance by calling stop() (this stops the internal timer)
- *
- * Gaps inserted via setGap() are not exposed immediately to lookupGap(), but only:
- *
- * - after a certain delay always larger than 'exposureDelayMs' and usually shorter
- *   than twice this value (but might be slightly longer in rare cases)
- *
- * - and only if they haven't been invalidated by a recent call to removeOverlappingGaps()
- *
- * This ensures atomicity between gap creation and invalidation from updates under
- * the condition that a gap is created from first key to last key within the time defined
- * by 'exposureDelayMs'.
- *
- * The implementation is based on two extra temporary "update sets" on top of the main
- * exposed gap set, one called "staging" and the other "frozen", each containing a
- * temporary updated gap set and a list of updated keys to invalidate gaps with (coming
- * from calls to removeOverlappingGaps()). Every "exposureDelayMs" milliseconds, the frozen
- * gaps are invalidated by all key updates coming from either of the "staging" or "frozen"
- * update set, then merged into the exposed gaps set, after which the staging updates become
- * the frozen updates and won't receive any new gap until the next cycle.
- */
-export default class GapCache implements GapCacheInterface {
-    _exposureDelayMs: number;
-    maxGaps: number;
-
-    _stagingUpdates: GapCacheUpdateSet;
-    _frozenUpdates: GapCacheUpdateSet;
-    _exposedGaps: GapSet;
-    _exposeFrozenInterval: NodeJS.Timeout | null;
-
-    /**
-     * @constructor
-     *
-     * @param {number} exposureDelayMs - minimum delay between
-     * insertion of a gap via setGap() and its exposure via
-     * lookupGap()
-     * @param {number} maxGaps - maximum number of cached gaps, after
-     * which no new gap can be added by setGap(). (Note: a future
-     * improvement could replace this by an eviction strategy)
-     * @param {number} maxGapWeight - maximum "weight" of individual
-     * cached gaps, which is also the granularity for
-     * invalidation. Individual gaps can be chained together,
-     * which lookupGap() transparently consolidates in the response
-     * into a single large gap.
-     */
-    constructor(exposureDelayMs: number, maxGaps: number, maxGapWeight: number) {
-        this._exposureDelayMs = exposureDelayMs;
-        this.maxGaps = maxGaps;
-
-        this._stagingUpdates = new GapCacheUpdateSet(maxGapWeight);
-        this._frozenUpdates = new GapCacheUpdateSet(maxGapWeight);
-        this._exposedGaps = new GapSet(maxGapWeight);
-        this._exposeFrozenInterval = null;
-    }
-
-    /**
-     * Create a GapCache from an array of exposed gap entries (used in tests)
-     *
-     * @return {GapCache} - a new GapCache instance
-     */
-    static createFromArray(
-        gaps: GapSetEntry[],
-        exposureDelayMs: number,
-        maxGaps: number,
-        maxGapWeight: number
-    ): GapCache {
-        const gapCache = new GapCache(exposureDelayMs, maxGaps, maxGapWeight);
-        gapCache._exposedGaps = GapSet.createFromArray(gaps, maxGapWeight)
-        return gapCache;
-    }
-
-    /**
-     * Internal helper to remove gaps in the staging and frozen sets
-     * overlapping with previously updated keys, right before the
-     * frozen gaps get exposed.
-     *
-     * @return {undefined}
-     */
-    _removeOverlappingGapsBeforeExpose(): void {
-        for (const { updatedKeys } of [this._stagingUpdates, this._frozenUpdates]) {
-            if (updatedKeys.size() === 0) {
-                continue;
-            }
-            for (const { newGaps } of [this._stagingUpdates, this._frozenUpdates]) {
-                if (newGaps.size === 0) {
-                    continue;
-                }
-                newGaps.removeOverlappingGaps(updatedKeys);
-            }
-        }
-    }
-
-    /**
-     * This function is the core mechanism that updates the exposed gaps in the
-     * cache. It is called on a regular interval defined by 'exposureDelayMs'.
-     *
-     * It does the following in order:
-     *
-     * - remove gaps from the frozen set that overlap with any key present in a
-     *   batch passed to removeOverlappingGaps() since the last two triggers of
-     *   _exposeFrozen()
-     *
-     * - merge the remaining gaps from the frozen set to the exposed set, which
-     *   makes them visible from calls to lookupGap()
-     *
-     * - rotate by freezing the currently staging updates and initiating a new
-     *   staging updates set
-     *
-     * @return {undefined}
-     */
-    _exposeFrozen(): void {
-        this._removeOverlappingGapsBeforeExpose();
-        for (const gap of this._frozenUpdates.newGaps) {
-            // Use a trivial strategy to keep the cache size within
-            // limits: refuse to add new gaps when the size is above
-            // the 'maxGaps' threshold. We solely rely on
-            // removeOverlappingGaps() to make space for new gaps.
-            if (this._exposedGaps.size < this.maxGaps) {
-                this._exposedGaps.setGap(gap.firstKey, gap.lastKey, gap.weight);
-            }
-        }
-        this._frozenUpdates = this._stagingUpdates;
-        this._stagingUpdates = new GapCacheUpdateSet(this.maxGapWeight);
-    }
-
-    /**
-     * Start the internal GapCache timer
-     *
-     * @return {undefined}
-     */
-    start(): void {
-        if (this._exposeFrozenInterval) {
-            return;
-        }
-        this._exposeFrozenInterval = setInterval(
-            () => this._exposeFrozen(),
-            this._exposureDelayMs);
-    }
-
-    /**
-     * Stop the internal GapCache timer
-     *
-     * @return {undefined}
-     */
-    stop(): void {
-        if (this._exposeFrozenInterval) {
-            clearInterval(this._exposeFrozenInterval);
-            this._exposeFrozenInterval = null;
-        }
-    }
-
-    /**
-     * Record a gap between two keys, associated with a weight to
-     * limit individual gap's spanning ranges in the cache, for a more
-     * granular invalidation.
-     *
-     * The function handles splitting and merging existing gaps to
-     * maintain an optimal weight of cache entries.
-     *
-     * NOTE 1: the caller must ensure that the full length of the gap
-     * between 'firstKey' and 'lastKey' has been built from a listing
-     * snapshot that is more recent than 'exposureDelayMs' milliseconds,
-     * in order to guarantee that the exposed gap will be fully
-     * covered (and potentially invalidated) from recent calls to
-     * removeOverlappingGaps().
-     *
-     * NOTE 2: a usual pattern when building a large gap from multiple
-     * calls to setGap() is to start the next gap from 'lastKey',
-     * which will be passed as 'firstKey' in the next call, so that
-     * gaps can be chained together and consolidated by lookupGap().
-     *
-     * @param {string} firstKey - first key of the gap
-     * @param {string} lastKey - last key of the gap, must be greater
-     * or equal than 'firstKey'
-     * @param {number} weight - total weight between 'firstKey' and 'lastKey'
-     * @return {undefined}
-     */
-    setGap(firstKey: string, lastKey: string, weight: number): void {
-        this._stagingUpdates.newGaps.setGap(firstKey, lastKey, weight);
-    }
-
-    /**
-     * Remove gaps that overlap with a given set of keys. Used to
-     * invalidate gaps when keys are inserted or deleted.
-     *
-     * @param {OrderedSet<string> | string[]} overlappingKeys - remove gaps that
-     * overlap with any of this set of keys
-     * @return {number} - how many gaps were removed from the exposed
-     * gaps only (overlapping gaps not yet exposed are also invalidated
-     * but are not accounted for in the returned value)
-     */
-    removeOverlappingGaps(overlappingKeys: OrderedSet<string> | string[]): number {
-        let overlappingKeysSet;
-        if (Array.isArray(overlappingKeys)) {
-            overlappingKeysSet = new OrderedSet(overlappingKeys);
-        } else {
-            overlappingKeysSet = overlappingKeys;
-        }
-        this._stagingUpdates.addUpdateBatch(overlappingKeysSet);
-        return this._exposedGaps.removeOverlappingGaps(overlappingKeysSet);
-    }
-
-    /**
-     * Lookup the next exposed gap that overlaps with [minKey, maxKey]. Internally
-     * chained gaps are coalesced in the response into a single contiguous large gap.
-     *
-     * @param {string} minKey - minimum key overlapping with the returned gap
-     * @param {string} [maxKey] - maximum key overlapping with the returned gap
-     * @return {Promise<GapSetEntry | null>} - result of the lookup if a gap
-     *   was found, null otherwise, as a Promise
-     */
-    lookupGap(minKey: string, maxKey?: string): Promise<GapSetEntry | null> {
-        return this._exposedGaps.lookupGap(minKey, maxKey);
-    }
-
-    /**
-     * Get the maximum weight setting for individual gaps.
-     *
-     * @return {number} - maximum weight of individual gaps
-     */
-    get maxGapWeight(): number {
-        return this._exposedGaps.maxWeight;
-    }
-
-    /**
-     * Set the maximum weight setting for individual gaps.
-     *
-     * @param {number} gapWeight - maximum weight of individual gaps
-     */
-    set maxGapWeight(gapWeight: number) {
-        this._exposedGaps.maxWeight = gapWeight;
-        // also update transient gap sets
-        this._stagingUpdates.newGaps.maxWeight = gapWeight;
-        this._frozenUpdates.newGaps.maxWeight = gapWeight;
-    }
-
-    /**
-     * Get the exposure delay in milliseconds, which is the minimum
-     * time after which newly cached gaps will be exposed by
-     * lookupGap().
-     *
-     * @return {number} - exposure delay in milliseconds
-     */
-    get exposureDelayMs(): number {
-        return this._exposureDelayMs;
-    }
-
-    /**
-     * Set the exposure delay in milliseconds, which is the minimum
-     * time after which newly cached gaps will be exposed by
-     * lookupGap(). Setting this attribute automatically updates the
-     * internal state to honor the new value.
-     *
-     * @param {number} - exposure delay in milliseconds
-     */
-    set exposureDelayMs(exposureDelayMs: number) {
-        if (exposureDelayMs !== this._exposureDelayMs) {
-            this._exposureDelayMs = exposureDelayMs;
-            if (this._exposeFrozenInterval) {
-                // invalidate all pending gap updates, as the new interval may not be
-                // safe for them
-                this._stagingUpdates = new GapCacheUpdateSet(this.maxGapWeight);
-                this._frozenUpdates = new GapCacheUpdateSet(this.maxGapWeight);
-
-                // reinitialize the _exposeFrozenInterval timer with the updated delay
-                this.stop();
-                this.start();
-            }
-        }
-    }
-
-    /**
-     * Get the number of exposed gaps
-     *
-     * @return {number} number of exposed gaps
-     */
-    get size(): number {
-        return this._exposedGaps.size;
-    }
-
-    /**
-     * Iterate over exposed gaps
-     *
-     * @return {Iterator<GapSetEntry>} an iterator over exposed gaps
-     */
-    [Symbol.iterator](): Iterator<GapSetEntry> {
-        return this._exposedGaps[Symbol.iterator]();
-    }
-
-    /**
-     * Get an array of all exposed gaps
-     *
-     * @return {GapSetEntry[]} array of exposed gaps
-     */
-    toArray(): GapSetEntry[] {
-        return this._exposedGaps.toArray();
-    }
-
-    /**
-     * Clear all exposed and staging gaps from the cache.
-     *
-     * Note: retains invalidating updates from removeOverlappingGaps()
-     * for correctness of gaps inserted afterwards.
-     *
-     * @return {undefined}
-     */
-    clear(): void {
-        this._stagingUpdates.newGaps = new GapSet(this.maxGapWeight);
-        this._frozenUpdates.newGaps = new GapSet(this.maxGapWeight);
-        this._exposedGaps = new GapSet(this.maxGapWeight);
-    }
-}

lib/algos/cache/GapSet.ts

@@ -1,366 +0,0 @@
-import assert from 'assert';
-import { OrderedSet } from '@js-sdsl/ordered-set';
-
-import errors from '../../errors';
-
-export type GapSetEntry = {
-    firstKey: string,
-    lastKey: string,
-    weight: number,
-};
-
-export interface GapSetInterface {
-    maxWeight: number;
-    size: number;
-
-    setGap: (firstKey: string, lastKey: string, weight: number) => GapSetEntry;
-    removeOverlappingGaps: (overlappingKeys: string[]) => number;
-    lookupGap: (minKey: string, maxKey?: string) => Promise<GapSetEntry | null>;
-    [Symbol.iterator]: () => Iterator<GapSetEntry>;
-    toArray: () => GapSetEntry[];
-};
-
-/**
- * Specialized data structure to support caching of listing "gaps",
- * i.e. ranges of keys that can be skipped over during listing
- * (because they only contain delete markers as latest versions)
- */
-export default class GapSet implements GapSetInterface, Iterable<GapSetEntry> {
-    _gaps: OrderedSet<GapSetEntry>;
-    _maxWeight: number;
-
-    /**
-     * @constructor
-
-     * @param {number} maxWeight - weight threshold for each cached
-     * gap (unitless). Triggers splitting gaps when reached
-     */
-    constructor(maxWeight: number) {
-        this._gaps = new OrderedSet(
-            [],
-            (left: GapSetEntry, right: GapSetEntry) => (
-                left.firstKey < right.firstKey ? -1 :
-                left.firstKey > right.firstKey ? 1 : 0
-            )
-        );
-        this._maxWeight = maxWeight;
-    }
-
-    /**
-     * Create a GapSet from an array of gap entries (used in tests)
-     */
-    static createFromArray(gaps: GapSetEntry[], maxWeight: number): GapSet {
-        const gapSet = new GapSet(maxWeight);
-        for (const gap of gaps) {
-            gapSet._gaps.insert(gap);
-        }
-        return gapSet;
-    }
-
-    /**
-     * Record a gap between two keys, associated with a weight to limit
-     * individual gap sizes in the cache.
-     *
-     * The function handles splitting and merging existing gaps to
-     * maintain an optimal weight of cache entries.
-     *
-     * @param {string} firstKey - first key of the gap
-     * @param {string} lastKey - last key of the gap, must be greater
-     * or equal than 'firstKey'
-     * @param {number} weight - total weight between 'firstKey' and 'lastKey'
-     * @return {GapSetEntry} - existing or new gap entry
-     */
-    setGap(firstKey: string, lastKey: string, weight: number): GapSetEntry {
-        assert(lastKey >= firstKey);
-
-        // Step 1/4: Find the closest left-overlapping gap, and either re-use it
-        // or chain it with a new gap depending on the weights if it exists (otherwise
-        // just creates a new gap).
-        const curGapIt = this._gaps.reverseLowerBound(<GapSetEntry>{ firstKey });
-        let curGap;
-        if (curGapIt.isAccessible()) {
-            curGap = curGapIt.pointer;
-            if (curGap.lastKey >= lastKey) {
-                // return fully overlapping gap already cached
-                return curGap;
-            }
-        }
-        let remainingWeight = weight;
-        if (!curGap                         // no previous gap
-            || curGap.lastKey < firstKey    // previous gap not overlapping
-            || (curGap.lastKey === firstKey // previous gap overlapping by one key...
-                && curGap.weight + weight > this._maxWeight) // ...but we can't extend it
-           ) {
-            // create a new gap indexed by 'firstKey'
-            curGap = { firstKey, lastKey: firstKey, weight: 0 };
-            this._gaps.insert(curGap);
-        } else if (curGap.lastKey > firstKey && weight > this._maxWeight) {
-            // previous gap is either fully or partially contained in the new gap
-            // and cannot be extended: substract its weight from the total (heuristic
-            // in case the previous gap doesn't start at 'firstKey', which is the
-            // uncommon case)
-            remainingWeight -= curGap.weight;
-
-            // there may be an existing chained gap starting with the previous gap's
-            // 'lastKey': use it if it exists
-            const chainedGapIt = this._gaps.find(<GapSetEntry>{ firstKey: curGap.lastKey });
-            if (chainedGapIt.isAccessible()) {
-                curGap = chainedGapIt.pointer;
-            } else {
-                // no existing chained gap: chain a new gap to the previous gap
-                curGap = {
-                    firstKey: curGap.lastKey,
-                    lastKey: curGap.lastKey,
-                    weight: 0,
-                };
-                this._gaps.insert(curGap);
-            }
-        }
-        // Step 2/4: Cleanup existing gaps fully included in firstKey -> lastKey, and
-        // aggregate their weights in curGap to define the minimum weight up to the
-        // last merged gap.
-        let nextGap;
-        while (true) {
-            const nextGapIt = this._gaps.upperBound(<GapSetEntry>{ firstKey: curGap.firstKey });
-            nextGap = nextGapIt.isAccessible() && nextGapIt.pointer;
-            // stop the cleanup when no more gap or if the next gap is not fully
-            // included in curGap
-            if (!nextGap || nextGap.lastKey > lastKey) {
-                break;
-            }
-            this._gaps.eraseElementByIterator(nextGapIt);
-            curGap.lastKey = nextGap.lastKey;
-            curGap.weight += nextGap.weight;
-        }
-
-        // Step 3/4: Extend curGap to lastKey, adjusting the weight.
-        // At this point, curGap weight is the minimum weight of the finished gap, save it
-        // for step 4.
-        let minMergedWeight = curGap.weight;
-        if (curGap.lastKey === firstKey && firstKey !== lastKey) {
-            // extend the existing gap by the full amount 'firstKey -> lastKey'
-            curGap.lastKey = lastKey;
-            curGap.weight += remainingWeight;
-        } else if (curGap.lastKey <= lastKey) {
-            curGap.lastKey = lastKey;
-            curGap.weight = remainingWeight;
-        }
-
-        // Step 4/4: Find the closest right-overlapping gap, and if it exists, either merge
-        // it or chain it with curGap depending on the weights.
-        if (nextGap && nextGap.firstKey <= lastKey) {
-            // nextGap overlaps with the new gap: check if we can merge it
-            minMergedWeight += nextGap.weight;
-            let mergedWeight;
-            if (lastKey === nextGap.firstKey) {
-                // nextGap is chained with curGap: add the full weight of nextGap
-                mergedWeight = curGap.weight + nextGap.weight;
-            } else {
-                // strict overlap: don't add nextGap's weight unless
-                // it's larger than the sum of merged ranges (as it is
-                // then included in `minMergedWeight`)
-                mergedWeight = Math.max(curGap.weight, minMergedWeight);
-            }
-            if (mergedWeight <= this._maxWeight) {
-                // merge nextGap into curGap
-                curGap.lastKey = nextGap.lastKey;
-                curGap.weight = mergedWeight;
-                this._gaps.eraseElementByKey(nextGap);
-            } else {
-                // adjust the last key to chain with nextGap and substract the next
-                // gap's weight from curGap (heuristic)
-                curGap.lastKey = nextGap.firstKey;
-                curGap.weight = Math.max(mergedWeight - nextGap.weight, 0);
-                curGap = nextGap;
-            }
-        }
-        // return a copy of curGap
-        return Object.assign({}, curGap);
-    }
-
-    /**
-     * Remove gaps that overlap with one or more keys in a given array or
-     * OrderedSet. Used to invalidate gaps when keys are inserted or deleted.
-     *
-     * @param {OrderedSet<string> | string[]} overlappingKeys - remove gaps that overlap
-     * with any of this set of keys
-     * @return {number} - how many gaps were removed
-     */
-    removeOverlappingGaps(overlappingKeys: OrderedSet<string> | string[]): number {
-        // To optimize processing with a large number of keys and/or gaps, this function:
-        //
-        // 1. converts the overlappingKeys array to a OrderedSet (if not already a OrderedSet)
-        // 2. queries both the gaps set and the overlapping keys set in a loop, which allows:
-        //    - skipping ranges of overlapping keys at once when there is no new overlapping gap
-        //    - skipping ranges of gaps at once when there is no overlapping key
-        //
-        // This way, it is efficient when the number of non-overlapping gaps is large
-        // (which is the most common case in practice).
-
-        let overlappingKeysSet;
-        if (Array.isArray(overlappingKeys)) {
-            overlappingKeysSet = new OrderedSet(overlappingKeys);
-        } else {
-            overlappingKeysSet = overlappingKeys;
-        }
-        const firstKeyIt = overlappingKeysSet.begin();
-        let currentKey = firstKeyIt.isAccessible() && firstKeyIt.pointer;
-        let nRemoved = 0;
-        while (currentKey) {
-            const closestGapIt = this._gaps.reverseUpperBound(<GapSetEntry>{ firstKey: currentKey });
-            if (closestGapIt.isAccessible()) {
-                const closestGap = closestGapIt.pointer;
-                if (currentKey <= closestGap.lastKey) {
-                    // currentKey overlaps closestGap: remove the gap
-                    this._gaps.eraseElementByIterator(closestGapIt);
-                    nRemoved += 1;
-                }
-            }
-            const nextGapIt = this._gaps.lowerBound(<GapSetEntry>{ firstKey: currentKey });
-            if (!nextGapIt.isAccessible()) {
-                // no more gap: we're done
-                return nRemoved;
-            }
-            const nextGap = nextGapIt.pointer;
-            // advance to the last key potentially overlapping with nextGap
-            let currentKeyIt = overlappingKeysSet.reverseLowerBound(nextGap.lastKey);
-            if (currentKeyIt.isAccessible()) {
-                currentKey = currentKeyIt.pointer;
-                if (currentKey >= nextGap.firstKey) {
-                    // currentKey overlaps nextGap: remove the gap
-                    this._gaps.eraseElementByIterator(nextGapIt);
-                    nRemoved += 1;
-                }
-            }
-            // advance to the first key potentially overlapping with another gap
-            currentKeyIt = overlappingKeysSet.lowerBound(nextGap.lastKey);
-            currentKey = currentKeyIt.isAccessible() && currentKeyIt.pointer;
-        }
-        return nRemoved;
-    }
-
-    /**
-     * Internal helper to coalesce multiple chained gaps into a single gap.
-     *
-     * It is only used to construct lookupGap() return values and
-     * doesn't modify the GapSet.
-     *
-     * NOTE: The function may take a noticeable amount of time and CPU
-     * to execute if a large number of chained gaps have to be
-     * coalesced, but it should never take more than a few seconds. In
-     * most cases it should take less than a millisecond. It regularly
-     * yields to the nodejs event loop to avoid blocking it during a
-     * long execution.
-     *
-     * @param {GapSetEntry} firstGap - first gap of the chain to coalesce with
-     * the next ones in the chain
-     * @return {Promise<GapSetEntry>} - a new coalesced entry, as a Promise
-     */
-    _coalesceGapChain(firstGap: GapSetEntry): Promise<GapSetEntry> {
-        return new Promise(resolve => {
-            const coalescedGap: GapSetEntry = Object.assign({}, firstGap);
-            const coalesceGapChainIteration = () => {
-                // efficiency trade-off: 100 iterations of log(N) complexity lookups should
-                // not block the event loop for too long
-                for (let opCounter = 0; opCounter < 100; ++opCounter) {
-                    const chainedGapIt = this._gaps.find(
-                            <GapSetEntry>{ firstKey: coalescedGap.lastKey });
-                    if (!chainedGapIt.isAccessible()) {
-                        // chain is complete
-                        return resolve(coalescedGap);
-                    }
-                    const chainedGap = chainedGapIt.pointer;
-                    if (chainedGap.firstKey === chainedGap.lastKey) {
-                        // found a single-key gap: chain is complete
-                        return resolve(coalescedGap);
-                    }
-                    coalescedGap.lastKey = chainedGap.lastKey;
-                    coalescedGap.weight += chainedGap.weight;
-                }
-                // yield to the event loop before continuing the process
-                // of coalescing the gap chain
-                return process.nextTick(coalesceGapChainIteration);
-            };
-            coalesceGapChainIteration();
-        });
-    }
-
-    /**
-     * Lookup the next gap that overlaps with [minKey, maxKey]. Internally chained
-     * gaps are coalesced in the response into a single contiguous large gap.
-     *
-     * @param {string} minKey - minimum key overlapping with the returned gap
-     * @param {string} [maxKey] - maximum key overlapping with the returned gap
-     * @return {Promise<GapSetEntry | null>} - result of the lookup if a gap
-     *   was found, null otherwise, as a Promise
-     */
-    async lookupGap(minKey: string, maxKey?: string): Promise<GapSetEntry | null> {
-        let firstGap: GapSetEntry | null = null;
-        const minGapIt = this._gaps.reverseLowerBound(<GapSetEntry>{ firstKey: minKey });
-        const minGap = minGapIt.isAccessible() && minGapIt.pointer;
-        if (minGap && minGap.lastKey >= minKey) {
-            firstGap = minGap;
-        } else {
-            const maxGapIt = this._gaps.upperBound(<GapSetEntry>{ firstKey: minKey });
-            const maxGap = maxGapIt.isAccessible() && maxGapIt.pointer;
-            if (maxGap && (maxKey === undefined || maxGap.firstKey <= maxKey)) {
-                firstGap = maxGap;
-            }
-        }
-        if (!firstGap) {
-            return null;
-        }
-        return this._coalesceGapChain(firstGap);
-    }
-
-    /**
-     * Get the maximum weight setting for individual gaps.
-     *
-     * @return {number} - maximum weight of individual gaps
-     */
-    get maxWeight(): number {
-        return this._maxWeight;
-    }
-
-    /**
-     * Set the maximum weight setting for individual gaps.
-     *
-     * @param {number} gapWeight - maximum weight of individual gaps
-     */
-    set maxWeight(gapWeight: number) {
-        this._maxWeight = gapWeight;
-    }
-
-    /**
-     * Get the number of gaps stored in this set.
-     *
-     * @return {number} - number of gaps stored in this set
-     */
-    get size(): number {
-        return this._gaps.size();
-    }
-
-    /**
-     * Iterate over each gap of the set, ordered by first key
-     *
-     * @return {Iterator<GapSetEntry>} - an iterator over all gaps
-     *   Example:
-     *     for (const gap of myGapSet) { ... }
-     */
-    [Symbol.iterator](): Iterator<GapSetEntry> {
-        return this._gaps[Symbol.iterator]();
-    }
-
-    /**
-     * Return an array containing all gaps, ordered by first key
-     *
-     * NOTE: there is a toArray() method in the OrderedSet implementation
-     * but it does not scale well and overflows the stack quickly. This is
-     * why we provide an implementation based on an iterator.
-     *
-     * @return {GapSetEntry[]} - an array containing all gaps
-     */
-    toArray(): GapSetEntry[] {
-        return [...this];
-    }
-}

lib/algos/list/Extension.js

@@ -1,6 +1,6 @@
 'use strict'; // eslint-disable-line strict
 
-const { FILTER_ACCEPT, SKIP_NONE } = require('./tools');
+const { FILTER_SKIP, SKIP_NONE } = require('./tools');
 
 // Use a heuristic to amortize the cost of JSON
 // serialization/deserialization only on largest metadata where the
@@ -92,26 +92,21 @@ class Extension {
      * @param {object} entry - a listing entry from metadata
      *                         expected format: { key, value }
      * @return {number} - result of filtering the entry:
-     *                    FILTER_ACCEPT: entry is accepted and may or not be included
+     *                    > 0: entry is accepted and included in the result
-     *                                   in the result
+     *                    = 0: entry is accepted but not included (skipping)
-     *                    FILTER_SKIP: listing may skip directly (with "gte" param) to
+     *                    < 0: entry is not accepted, listing should finish
-     *                                 the key returned by the skipping() method
-     *                    FILTER_END: the results are complete, listing can be stopped
      */
-    filter(/* entry: { key, value } */) {
+    filter(entry) {
-        return FILTER_ACCEPT;
+        return entry ? FILTER_SKIP : FILTER_SKIP;
     }
 
     /**
-     * Provides the next key at which the listing task is allowed to skip to.
+     * Provides the insight into why filter is skipping an entry. This could be
-     * This could allow to skip over:
+     * because it is skipping a range of delimited keys or a range of specific
-     * - a key prefix ending with the delimiter
+     * version when doing master version listing.
-     * - all remaining versions of an object when doing a current
-     *   versions listing in v0 format
-     * - a cached "gap" of deleted objects when doing a current
-     *   versions listing in v0 format
      *
-     * @return {string} - the next key at which the listing task is allowed to skip to
+     * @return {string} - the insight: a common prefix or a master key,
+     *                                 or SKIP_NONE if there is no insight
      */
     skipping() {
         return SKIP_NONE;

lib/algos/list/MPU.js

@@ -1,7 +1,7 @@
 'use strict'; // eslint-disable-line strict
 
 const { inc, checkLimit, listingParamsMasterKeysV0ToV1,
-    FILTER_END, FILTER_ACCEPT, SKIP_NONE } = require('./tools');
+    FILTER_END, FILTER_ACCEPT } = require('./tools');
 const DEFAULT_MAX_KEYS = 1000;
 const VSConst = require('../../versioning/constants').VersioningConstants;
 const { DbPrefixes, BucketVersioningKeyFormat } = VSConst;
@@ -163,7 +163,7 @@ class MultipartUploads {
     }
 
     skipping() {
-        return SKIP_NONE;
+        return '';
     }
 
     /**

lib/algos/list/basic.js

@@ -2,7 +2,7 @@
 
 const Extension = require('./Extension').default;
 
-const { checkLimit, FILTER_END, FILTER_ACCEPT } = require('./tools');
+const { checkLimit, FILTER_END, FILTER_ACCEPT, FILTER_SKIP } = require('./tools');
 const DEFAULT_MAX_KEYS = 10000;
 
 /**
@@ -91,7 +91,7 @@ class List extends Extension {
      *                     < 0 : listing done
      */
     filter(elem) {
-        // Check if the result array is full
+        // Check first in case of maxkeys <= 0
         if (this.keys >= this.maxKeys) {
             return FILTER_END;
         }
@@ -99,7 +99,7 @@ class List extends Extension {
              this.filterKeyStartsWith !== undefined) &&
             typeof elem === 'object' &&
             !this.customFilter(elem.value)) {
-            return FILTER_ACCEPT;
+            return FILTER_SKIP;
         }
         if (typeof elem === 'object') {
             this.res.push({

lib/algos/list/delimiter.ts

@@ -32,7 +32,7 @@ export interface DelimiterFilterState_SkippingPrefix extends FilterState {
 
 type KeyHandler = (key: string, value: string) => FilterReturnValue;
 
-export type ResultObject = {
+type ResultObject = {
     CommonPrefixes: string[];
     Contents: {
         key: string;
@@ -196,9 +196,6 @@ export class Delimiter extends Extension {
     }
 
     getCommonPrefix(key: string): string | undefined {
-        if (!this.delimiter) {
-            return undefined;
-        }
         const baseIndex = this.prefix ? this.prefix.length : 0;
         const delimiterIndex = key.indexOf(this.delimiter, baseIndex);
         if (delimiterIndex === -1) {
@@ -308,7 +305,7 @@ export class Delimiter extends Extension {
         switch (this.state.id) {
         case DelimiterFilterStateId.SkippingPrefix:
             const { prefix } = <DelimiterFilterState_SkippingPrefix> this.state;
-            return inc(prefix);
+            return prefix;
 
         default:
             return SKIP_NONE;

lib/algos/list/delimiterMaster.ts

@@ -5,23 +5,18 @@ import {
     DelimiterFilterStateId,
     DelimiterFilterState_NotSkipping,
     DelimiterFilterState_SkippingPrefix,
-    ResultObject,
 } from './delimiter';
 const Version = require('../../versioning/Version').Version;
 const VSConst = require('../../versioning/constants').VersioningConstants;
 const { BucketVersioningKeyFormat } = VSConst;
-const { FILTER_ACCEPT, FILTER_SKIP, FILTER_END, SKIP_NONE, inc } = require('./tools');
+const { FILTER_ACCEPT, FILTER_SKIP, FILTER_END } = require('./tools');
-
-import { GapSetEntry } from '../cache/GapSet';
-import { GapCacheInterface } from '../cache/GapCache';
 
 const VID_SEP = VSConst.VersionId.Separator;
 const { DbPrefixes } = VSConst;
 
-export const enum DelimiterMasterFilterStateId {
+const enum DelimiterMasterFilterStateId {
     SkippingVersionsV0 = 101,
     WaitVersionAfterPHDV0 = 102,
-    SkippingGapV0 = 103,
 };
 
 interface DelimiterMasterFilterState_SkippingVersionsV0 extends FilterState {
@@ -34,121 +29,37 @@ interface DelimiterMasterFilterState_WaitVersionAfterPHDV0 extends FilterState {
     masterKey: string,
 };
 
-interface DelimiterMasterFilterState_SkippingGapV0 extends FilterState {
-    id: DelimiterMasterFilterStateId.SkippingGapV0,
-};
-
-export const enum GapCachingState {
-    NoGapCache = 0, // there is no gap cache
-    UnknownGap = 1, // waiting for a cache lookup
-    GapLookupInProgress = 2, // asynchronous gap lookup in progress
-    GapCached = 3, // an upcoming or already skippable gap is cached
-    NoMoreGap = 4, // the cache doesn't have any more gaps inside the listed range
-};
-
-type GapCachingInfo_NoGapCache = {
-    state: GapCachingState.NoGapCache;
-};
-
-type GapCachingInfo_NoCachedGap = {
-    state: GapCachingState.UnknownGap
-        | GapCachingState.GapLookupInProgress
-    gapCache: GapCacheInterface;
-};
-
-type GapCachingInfo_GapCached = {
-    state: GapCachingState.GapCached;
-    gapCache: GapCacheInterface;
-    gapCached: GapSetEntry;
-};
-
-type GapCachingInfo_NoMoreGap = {
-    state: GapCachingState.NoMoreGap;
-};
-
-type GapCachingInfo = GapCachingInfo_NoGapCache
-    | GapCachingInfo_NoCachedGap
-    | GapCachingInfo_GapCached
-    | GapCachingInfo_NoMoreGap;
-
-
-export const enum GapBuildingState {
-    Disabled = 0, // no gap cache or no gap building needed (e.g. in V1 versioning format)
-    NotBuilding = 1, // not currently building a gap (i.e. not listing within a gap)
-    Building = 2, // currently building a gap (i.e. listing within a gap)
-    Expired = 3, // not allowed to build due to exposure delay timeout
-};
-
-type GapBuildingInfo_NothingToBuild = {
-    state: GapBuildingState.Disabled | GapBuildingState.Expired;
-};
-
-type GapBuildingParams = {
-    /**
-     * minimum weight for a gap to be created in the cache
-     */
-    minGapWeight: number;
-    /**
-     * trigger a cache setGap() call every N skippable keys
-     */
-    triggerSaveGapWeight: number;
-    /**
-     * timestamp to assess whether we're still inside the validity period to
-     * be allowed to build gaps
-     */
-    initTimestamp: number;
-};
-
-type GapBuildingInfo_NotBuilding = {
-    state: GapBuildingState.NotBuilding;
-    gapCache: GapCacheInterface;
-    params: GapBuildingParams;
-};
-
-type GapBuildingInfo_Building = {
-    state: GapBuildingState.Building;
-    gapCache: GapCacheInterface;
-    params: GapBuildingParams;
-    /**
-     * Gap currently being created
-     */
-    gap: GapSetEntry;
-    /**
-     * total current weight of the gap being created
-     */
-    gapWeight: number;
-};
-
-type GapBuildingInfo = GapBuildingInfo_NothingToBuild
-    | GapBuildingInfo_NotBuilding
-    | GapBuildingInfo_Building;
-
 /**
  * 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 {
 
-    _gapCaching: GapCachingInfo;
-    _gapBuilding: GapBuildingInfo;
-    _refreshedBuildingParams: GapBuildingParams | null;
-
     /**
      * Delimiter listing of master versions.
      * @param {Object}  parameters            - listing parameters
-     * @param {String}  [parameters.delimiter]  - delimiter per amazon format
+     * @param {String}  parameters.delimiter  - delimiter per amazon format
-     * @param {String}  [parameters.prefix]     - prefix per amazon format
+     * @param {String}  parameters.prefix     - prefix per amazon format
-     * @param {String}  [parameters.marker]     - marker per amazon format
+     * @param {String}  parameters.marker     - marker per amazon format
-     * @param {Number}  [parameters.maxKeys]    - number of keys to list
+     * @param {Number}  parameters.maxKeys    - number of keys to list
-     * @param {Boolean} [parameters.v2]         - indicates whether v2 format
+     * @param {Boolean} parameters.v2         - indicates whether v2 format
-     * @param {String}  [parameters.startAfter] - marker per amazon v2 format
+     * @param {String}  parameters.startAfter - marker per amazon v2 format
-     * @param {String}  [parameters.continuationToken] - obfuscated amazon token
+     * @param {String}  parameters.continuationToken - obfuscated amazon token
-     * @param {RequestLogger} logger            - The logger of the request
+     * @param {RequestLogger} logger          - The logger of the request
-     * @param {String}  [vFormat="v0"]          - versioning key format
+     * @param {String} [vFormat]              - versioning key format
      */
-    constructor(parameters, logger, vFormat?: string) {
+    constructor(parameters, logger, vFormat) {
         super(parameters, logger, vFormat);
 
+        Object.assign(this, {
+            [BucketVersioningKeyFormat.v0]: {
+                skipping: this.skippingV0,
+            },
+            [BucketVersioningKeyFormat.v1]: {
+                skipping: this.skippingV1,
+            },
+        }[this.vFormat]);
+
         if (this.vFormat === BucketVersioningKeyFormat.v0) {
             // override Delimiter's implementation of NotSkipping for
             // DelimiterMaster logic (skipping versions and special
@@ -166,10 +77,6 @@ export class DelimiterMaster extends Delimiter {
                 DelimiterMasterFilterStateId.WaitVersionAfterPHDV0,
                 this.keyHandler_WaitVersionAfterPHDV0.bind(this));
 
-            this.setKeyHandler(
-                DelimiterMasterFilterStateId.SkippingGapV0,
-                this.keyHandler_SkippingGapV0.bind(this));
-
             if (this.marker) {
                 // distinct initial state to include some special logic
                 // before the first master key is found that does not have
@@ -191,178 +98,6 @@ export class DelimiterMaster extends Delimiter {
                 DelimiterFilterStateId.NotSkipping,
                 this.keyHandler_NotSkippingPrefixNorVersionsV1.bind(this));
         }
-        // in v1, we can directly use Delimiter's implementation,
-        // which is already set to the proper state
-
-        // default initialization of the gap cache and building states, can be
-        // set by refreshGapCache()
-        this._gapCaching = {
-            state: GapCachingState.NoGapCache,
-        };
-        this._gapBuilding = {
-            state: GapBuildingState.Disabled,
-        };
-        this._refreshedBuildingParams = null;
-    }
-
-    /**
-     * Get the validity period left before a refresh of the gap cache is needed
-     * to continue building new gaps.
-     *
-     * @return {number|null} one of:
-     * - the remaining time in milliseconds in which gaps can be added to the
-     *   cache before a call to refreshGapCache() is required
-     * - or 0 if there is no time left and a call to refreshGapCache() is required
-     *   to resume caching gaps
-     * - or null if refreshing the cache is never needed (because the gap cache
-     *   is either not available or not used)
-     */
-    getGapBuildingValidityPeriodMs(): number | null {
-        let gapBuilding;
-        switch (this._gapBuilding.state) {
-        case GapBuildingState.Disabled:
-            return null;
-        case GapBuildingState.Expired:
-            return 0;
-        case GapBuildingState.NotBuilding:
-            gapBuilding = <GapBuildingInfo_NotBuilding> this._gapBuilding;
-            break;
-        case GapBuildingState.Building:
-            gapBuilding = <GapBuildingInfo_Building> this._gapBuilding;
-            break;
-        }
-        const { gapCache, params } = gapBuilding;
-        const elapsedTime = Date.now() - params.initTimestamp;
-        return Math.max(gapCache.exposureDelayMs - elapsedTime, 0);
-    }
-
-    /**
-     * Refresh the gaps caching logic (gaps are series of current delete markers
-     * in V0 bucket metadata format). It has two effects:
-     *
-     * - starts exposing existing and future gaps from the cache to efficiently
-     *   skip over series of current delete markers that have been seen and cached
-     *   earlier
-     *
-     * - enables building and caching new gaps (or extend existing ones), for a
-     *   limited time period defined by the `gapCacheProxy.exposureDelayMs` value
-     *   in milliseconds. To refresh the validity period and resume building and
-     *   caching new gaps, one must restart a new listing from the database (starting
-     *   at the current listing key, included), then call refreshGapCache() again.
-     *
-     * @param {GapCacheInterface} gapCacheProxy - API proxy to the gaps cache
-     *   (the proxy should handle prefixing object keys with the bucket name)
-     * @param {number} [minGapWeight=100] - minimum weight of a gap for it to be
-     *   added in the cache
-     * @param {number} [triggerSaveGapWeight] - cumulative weight to wait for
-     *   before saving the current building gap. Cannot be greater than
-     *   `gapCacheProxy.maxGapWeight` (the value is thresholded to `maxGapWeight`
-     *   otherwise). Defaults to `gapCacheProxy.maxGapWeight / 2`.
-     * @return {undefined}
-     */
-    refreshGapCache(
-        gapCacheProxy: GapCacheInterface,
-        minGapWeight?: number,
-        triggerSaveGapWeight?: number
-    ): void {
-        if (this.vFormat !== BucketVersioningKeyFormat.v0) {
-            return;
-        }
-        if (this._gapCaching.state === GapCachingState.NoGapCache) {
-            this._gapCaching = {
-                state: GapCachingState.UnknownGap,
-                gapCache: gapCacheProxy,
-            };
-        }
-        const refreshedBuildingParams: GapBuildingParams = {
-            minGapWeight: minGapWeight || 100,
-            triggerSaveGapWeight: triggerSaveGapWeight
-                || Math.trunc(gapCacheProxy.maxGapWeight / 2),
-            initTimestamp: Date.now(),
-        };
-        if (this._gapBuilding.state === GapBuildingState.Building) {
-            // refreshed params will be applied as soon as the current building gap is saved
-            this._refreshedBuildingParams = refreshedBuildingParams;
-        } else {
-            this._gapBuilding = {
-                state: GapBuildingState.NotBuilding,
-                gapCache: gapCacheProxy,
-                params: refreshedBuildingParams,
-            };
-        }
-    }
-
-    /**
-     * Trigger a lookup of the closest upcoming or already skippable gap.
-     *
-     * @param {string} fromKey - lookup a gap not before 'fromKey'
-     * @return {undefined} - the lookup is asynchronous and its
-     * response is handled inside this function
-     */
-    _triggerGapLookup(gapCaching: GapCachingInfo_NoCachedGap, fromKey: string): void {
-        this._gapCaching = {
-            state: GapCachingState.GapLookupInProgress,
-            gapCache: gapCaching.gapCache,
-        };
-        const maxKey = this.prefix ? inc(this.prefix) : undefined;
-        gapCaching.gapCache.lookupGap(fromKey, maxKey).then(_gap => {
-            const gap = <GapSetEntry | null> _gap;
-            if (gap) {
-                this._gapCaching = {
-                    state: GapCachingState.GapCached,
-                    gapCache: gapCaching.gapCache,
-                    gapCached: gap,
-                };
-            } else {
-                this._gapCaching = {
-                    state: GapCachingState.NoMoreGap,
-                };
-            }
-        });
-    }
-
-    _checkGapOnMasterDeleteMarker(key: string): FilterReturnValue {
-        switch (this._gapBuilding.state) {
-        case GapBuildingState.Disabled:
-        case GapBuildingState.Expired:
-            break;
-        case GapBuildingState.NotBuilding:
-            this._createBuildingGap(key, 1);
-            break;
-        case GapBuildingState.Building:
-            this._updateBuildingGap(key);
-            break;
-        }
-        if (this._gapCaching.state === GapCachingState.GapCached) {
-            const { gapCached } = this._gapCaching;
-            if (key >= gapCached.firstKey) {
-                if (key <= gapCached.lastKey) {
-                    // we are inside the last looked up cached gap: transition to
-                    // 'SkippingGapV0' state
-                    this.setState(<DelimiterMasterFilterState_SkippingGapV0> {
-                        id: DelimiterMasterFilterStateId.SkippingGapV0,
-                    });
-                    // cut the current gap before skipping, it will be merged or
-                    // chained with the existing one (depending on its weight)
-                    if (this._gapBuilding.state === GapBuildingState.Building) {
-                        // substract 1 from the weight because we are going to chain this gap,
-                        // which has an overlap of one key.
-                        this._gapBuilding.gap.weight -= 1;
-                        this._cutBuildingGap();
-                    }
-                    return FILTER_SKIP;
-                }
-                // as we are past the cached gap, we will need another lookup
-                this._gapCaching = {
-                    state: GapCachingState.UnknownGap,
-                    gapCache: this._gapCaching.gapCache,
-                };
-            }
-        }
-        if (this._gapCaching.state === GapCachingState.UnknownGap) {
-            this._triggerGapLookup(this._gapCaching, key);
-        }
-        return FILTER_ACCEPT;
     }
 
     filter_onNewMasterKeyV0(key: string, value: string): FilterReturnValue {
@@ -374,7 +109,7 @@ export class DelimiterMaster extends Delimiter {
                 id: DelimiterMasterFilterStateId.SkippingVersionsV0,
                 masterKey: key,
             });
-            return this._checkGapOnMasterDeleteMarker(key);
+            return FILTER_ACCEPT;
         }
         if (Version.isPHD(value)) {
             // master version is a PHD version: wait for the first
@@ -386,9 +121,6 @@ export class DelimiterMaster extends Delimiter {
             });
             return FILTER_ACCEPT;
         }
-        // cut the current gap as soon as a non-deleted entry is seen
-        this._cutBuildingGap();
-
         if (key.startsWith(DbPrefixes.Replay)) {
             // skip internal replay prefix entirely
             this.setState(<DelimiterFilterState_SkippingPrefix> {
@@ -400,7 +132,6 @@ export class DelimiterMaster extends Delimiter {
         if (this._reachedMaxKeys()) {
             return FILTER_END;
         }
-
         const commonPrefix = this.addCommonPrefixOrContents(key, value);
         if (commonPrefix) {
             // transition into SkippingPrefix state to skip all following keys
@@ -442,11 +173,6 @@ export class DelimiterMaster extends Delimiter {
          * (<key><versionIdSeparator><version>) */
         const versionIdIndex = key.indexOf(VID_SEP);
         if (versionIdIndex !== -1) {
-            // version keys count in the building gap weight because they must
-            // also be listed until skipped
-            if (this._gapBuilding.state === GapBuildingState.Building) {
-                this._updateBuildingGap(key);
-            }
             return FILTER_SKIP;
         }
         return this.filter_onNewMasterKeyV0(key, value);
@@ -470,151 +196,14 @@ export class DelimiterMaster extends Delimiter {
         return this.filter_onNewMasterKeyV0(key, value);
     }
 
-    keyHandler_SkippingGapV0(key: string, value: string): FilterReturnValue {
-        const { gapCache, gapCached } = <GapCachingInfo_GapCached> this._gapCaching;
-        if (key <= gapCached.lastKey) {
-            return FILTER_SKIP;
-        }
-        this._gapCaching = {
-            state: GapCachingState.UnknownGap,
-            gapCache,
-        };
-        this.setState(<DelimiterMasterFilterState_SkippingVersionsV0> {
-            id: DelimiterMasterFilterStateId.SkippingVersionsV0,
-        });
-        // Start a gap with weight=0 from the latest skippable key. This will
-        // allow to extend the gap just skipped with a chained gap in case
-        // other delete markers are seen after the existing gap is skipped.
-        this._createBuildingGap(gapCached.lastKey, 0, gapCached.weight);
-
-        return this.handleKey(key, value);
-    }
-
     skippingBase(): string | undefined {
         switch (this.state.id) {
         case DelimiterMasterFilterStateId.SkippingVersionsV0:
             const { masterKey } = <DelimiterMasterFilterState_SkippingVersionsV0> this.state;
-            return masterKey + inc(VID_SEP);
+            return masterKey + VID_SEP;
-
-        case DelimiterMasterFilterStateId.SkippingGapV0:
-            const { gapCached } = <GapCachingInfo_GapCached> this._gapCaching;
-            return gapCached.lastKey;
 
         default:
             return super.skippingBase();
         }
     }
-
-    result(): ResultObject {
-        this._cutBuildingGap();
-        return super.result();
-    }
-
-    _checkRefreshedBuildingParams(params: GapBuildingParams): GapBuildingParams {
-        if (this._refreshedBuildingParams) {
-            const newParams = this._refreshedBuildingParams;
-            this._refreshedBuildingParams = null;
-            return newParams;
-        }
-        return params;
-    }
-
-    /**
-     * Save the gap being built if allowed (i.e. still within the
-     * allocated exposure time window).
-     *
-     * @return {boolean} - true if the gap was saved, false if we are
-     * outside the allocated exposure time window.
-     */
-    _saveBuildingGap(): boolean {
-        const { gapCache, params, gap, gapWeight } =
-              <GapBuildingInfo_Building> this._gapBuilding;
-        const totalElapsed = Date.now() - params.initTimestamp;
-        if (totalElapsed >= gapCache.exposureDelayMs) {
-            this._gapBuilding = {
-                state: GapBuildingState.Expired,
-            };
-            this._refreshedBuildingParams = null;
-            return false;
-        }
-        const { firstKey, lastKey, weight } = gap;
-        gapCache.setGap(firstKey, lastKey, weight);
-        this._gapBuilding = {
-            state: GapBuildingState.Building,
-            gapCache,
-            params: this._checkRefreshedBuildingParams(params),
-            gap: {
-                firstKey: gap.lastKey,
-                lastKey: gap.lastKey,
-                weight: 0,
-            },
-            gapWeight,
-        };
-        return true;
-    }
-
-    /**
-     * Create a new gap to be extended afterwards
-     *
-     * @param {string} newKey - gap's first key
-     * @param {number} startWeight - initial weight of the building gap (usually 0 or 1)
-     * @param {number} [cachedWeight] - if continuing a cached gap, weight of the existing
-     *   cached portion
-     * @return {undefined}
-     */
-    _createBuildingGap(newKey: string, startWeight: number, cachedWeight?: number): void {
-        if (this._gapBuilding.state === GapBuildingState.NotBuilding) {
-            const { gapCache, params } = <GapBuildingInfo_NotBuilding> this._gapBuilding;
-            this._gapBuilding = {
-                state: GapBuildingState.Building,
-                gapCache,
-                params: this._checkRefreshedBuildingParams(params),
-                gap: {
-                    firstKey: newKey,
-                    lastKey: newKey,
-                    weight: startWeight,
-                },
-                gapWeight: (cachedWeight || 0) + startWeight,
-            };
-        }
-    }
-
-    _updateBuildingGap(newKey: string): void {
-        const gapBuilding = <GapBuildingInfo_Building> this._gapBuilding;
-        const { params, gap } = gapBuilding;
-        gap.lastKey = newKey;
-        gap.weight += 1;
-        gapBuilding.gapWeight += 1;
-        // the GapCache API requires updating a gap regularly because it can only split
-        // it once per update, by the known last key. In practice the default behavior
-        // is to trigger an update after a number of keys that is half the maximum weight.
-        // It is also useful for other listings to benefit from the cache sooner.
-        if (gapBuilding.gapWeight >= params.minGapWeight &&
-            gap.weight >= params.triggerSaveGapWeight) {
-            this._saveBuildingGap();
-        }
-    }
-
-    _cutBuildingGap(): void {
-        if (this._gapBuilding.state === GapBuildingState.Building) {
-            let gapBuilding = <GapBuildingInfo_Building> this._gapBuilding;
-            let { gapCache, params, gap, gapWeight } = gapBuilding;
-            // only set gaps that are significant enough in weight and
-            // with a non-empty extension
-            if (gapWeight >= params.minGapWeight && gap.weight > 0) {
-                // we're done if we were not allowed to save the gap
-                if (!this._saveBuildingGap()) {
-                    return;
-                }
-                // params may have been refreshed, reload them
-                gapBuilding = <GapBuildingInfo_Building> this._gapBuilding;
-                params = gapBuilding.params;
-            }
-            this._gapBuilding = {
-                state: GapBuildingState.NotBuilding,
-                gapCache,
-                params,
-            };
-        }
-    }
 }

lib/algos/list/delimiterVersions.ts

@@ -457,14 +457,11 @@ export class DelimiterVersions extends Extension {
         switch (this.state.id) {
         case DelimiterVersionsFilterStateId.SkippingPrefix:
             const { prefix } = <DelimiterVersionsFilterState_SkippingPrefix> this.state;
-            return inc(prefix);
+            return prefix;
 
         case DelimiterVersionsFilterStateId.SkippingVersions:
             const { gt } = <DelimiterVersionsFilterState_SkippingVersions> this.state;
-            // the contract of skipping() is to return the first key
+            return gt;
-            // that can be skipped to, so adding a null byte to skip
-            // over the existing versioned key set in 'gt'
-            return `${gt}\0`;
 
         default:
             return SKIP_NONE;

lib/algos/list/skip.js

@@ -52,21 +52,21 @@ class Skip {
         assert(this.skipRangeCb);
 
         const filteringResult = this.extension.filter(entry);
-        const skipTo = this.extension.skipping();
+        const skippingRange = this.extension.skipping();
 
         if (filteringResult === FILTER_END) {
             this.listingEndCb();
         } else if (filteringResult === FILTER_SKIP
-                   && skipTo !== SKIP_NONE) {
+                   && skippingRange !== SKIP_NONE) {
             if (++this.streakLength >= MAX_STREAK_LENGTH) {
                 let newRange;
-                if (Array.isArray(skipTo)) {
+                if (Array.isArray(skippingRange)) {
                     newRange = [];
-                    for (let i = 0; i < skipTo.length; ++i) {
+                    for (let i = 0; i < skippingRange.length; ++i) {
-                        newRange.push(skipTo[i]);
+                        newRange.push(this._inc(skippingRange[i]));
                     }
                 } else {
-                    newRange = skipTo;
+                    newRange = this._inc(skippingRange);
                 }
                 /* Avoid to loop on the same range again and again. */
                 if (newRange === this.gteParams) {
@@ -79,6 +79,16 @@ class Skip {
             this.streakLength = 0;
         }
     }
+
+    _inc(str) {
+        if (!str) {
+            return str;
+        }
+        const lastCharValue = str.charCodeAt(str.length - 1);
+        const lastCharNewValue = String.fromCharCode(lastCharValue + 1);
+
+        return `${str.slice(0, str.length - 1)}${lastCharNewValue}`;
+    }
 }
 
 

lib/auth/Vault.ts

@@ -14,7 +14,7 @@ function vaultSignatureCb(
     err: Error | null,
     authInfo: { message: { body: any } },
     log: Logger,
-    callback: (err: Error | null, data?: any, results?: any, params?: any, infos?: any) => void,
+    callback: (err: Error | null, data?: any, results?: any, params?: any) => void,
     streamingV4Params?: any
 ) {
     // vaultclient API guarantees that it returns:
@@ -38,9 +38,7 @@ function vaultSignatureCb(
     }
     // @ts-ignore
     log.addDefaultFields(auditLog);
-    return callback(null, userInfo, authorizationResults, streamingV4Params, {
+    return callback(null, userInfo, authorizationResults, streamingV4Params);
-        accountQuota: info.accountQuota || {},
-    });
 }
 
 export type AuthV4RequestParams = {
@@ -386,19 +384,4 @@ export default class Vault {
             return callback(null, respBody);
         });
     }
-
-    report(log: Logger, callback: (err: Error | null, data?: any) => void) {
-        // call the report function of the client
-        if (!this.client.report) {
-            return callback(null, {});
-        }
-        // @ts-ignore
-        return this.client.report(log.getSerializedUids(), (err: Error | null, obj?: any) => {
-            if (err) {
-                log.debug(`error from ${this.implName}`, { error: err });
-                return callback(err);
-            }
-            return callback(null, obj);
-        });
-    }
 }

lib/auth/backends/ChainBackend.ts

@@ -134,7 +134,7 @@ export default class ChainBackend extends BaseBackend {
             }
 
             const check = (policy) => {
-                const key = (policy.arn || '') + (policy.versionId || '') + (policy.action || '');
+                const key = (policy.arn || '') + (policy.versionId || '');
                 if (!policyMap[key] || !policyMap[key].isAllowed) {
                     policyMap[key] = policy;
                 }
@@ -158,12 +158,8 @@ export default class ChainBackend extends BaseBackend {
             if (policyMap[key].versionId) {
                 policyRes.versionId = policyMap[key].versionId;
             }
-            if (policyMap[key].isImplicit !== undefined) {
+            policyRes.isImplicit = policyMap[key].isImplicit;
-                policyRes.isImplicit = policyMap[key].isImplicit;
+            policyRes.action = policyMap[key].action;
-            }
-            if (policyMap[key].action) {
-                policyRes.action = policyMap[key].action;
-            }
             return policyRes;
         });
     }
@@ -212,22 +208,4 @@ export default class ChainBackend extends BaseBackend {
             return callback(null, res);
         });
     }
-
-    report(reqUid: string, callback: any) {
-        this._forEachClient((client, done) =>
-            client.report(reqUid, done),
-            (err, res) => {
-                if (err) {
-                    return callback(err);
-                }
-                const mergedRes = res.reduce((acc, val) => {
-                    Object.keys(val).forEach(k => {
-                        acc[k] = val[k];
-                    });
-                    return acc;
-                }, {});
-
-                return callback(null, mergedRes);
-            });
-    }
 }

lib/auth/backends/in_memory/Backend.ts

@@ -161,10 +161,6 @@ class InMemoryBackend extends BaseBackend {
         };
         return cb(null, vaultReturnObject);
     }
-
-    report(log: Logger, callback: any) {
-        return callback(null, {});
-    }
 }
 
 

lib/clustering/ClusterRPC.ts

@@ -83,15 +83,13 @@ export type ResultObject = {
 export type CommandPromise = {
     resolve: (results?: ResultObject[]) => void;
     reject: (error: Error) => void;
-    timeout: NodeJS.Timeout | null;
+    timeout: NodeJS.Timer | null;
 };
-export type HandlerCallback = (error: (Error & { code?: number }) | null | undefined, result?: any) => void;
+export type HandlerCallback = (error: Error | null | undefined, result?: any) => void;
 export type HandlerFunction = (payload: object, uids: string, callback: HandlerCallback) => void;
 export type HandlersMap = {
     [index: string]: HandlerFunction;
 };
-export type PrimaryHandlerFunction = (worker: Worker, payload: object, uids: string, callback: HandlerCallback) => void;
-export type PrimaryHandlersMap = Record<string, PrimaryHandlerFunction>;
 
 // private types
 
@@ -108,7 +106,6 @@ type RPCCommandMessage = RPCMessage<'cluster-rpc:command', any> & {
 
 type MarshalledResultObject = {
     error: string | null;
-    errorCode?: number;
     result: any;
 };
 
@@ -122,15 +119,6 @@ type RPCCommandErrorMessage = RPCMessage<'cluster-rpc:commandError', {
     error: string;
 }>;
 
-interface RPCSetupOptions {
-    /**
-     * As werelogs is not a peerDependency, arsenal and a parent project
-     * might have their own separate versions duplicated in dependencies.
-     * The config are therefore not shared.
-     * Use this to propagate werelogs config to arsenal's ClusterRPC.
-     */
-    werelogsConfig?: Parameters<typeof werelogs.configure>[0];
-};
 
 /**
  * In primary: store worker IDs that are waiting to be dispatched
@@ -177,20 +165,12 @@ function _isRpcMessage(message) {
 /**
  * Setup cluster RPC system on the primary
  *
- * @param {object} [handlers] - mapping of handler names to handler functions
- *     handler function:
- *         `handler({Worker} worker, {object} payload, {string} uids, {function} callback)`
- *     handler callback must be called when worker is done with the command:
- *         `callback({Error|null} error, {any} [result])`
  * @return {undefined}
  */
-export function setupRPCPrimary(handlers?: PrimaryHandlersMap, options?: RPCSetupOptions) {
+export function setupRPCPrimary() {
-    if (options?.werelogsConfig) {
-        werelogs.configure(options.werelogsConfig);
-    }
     cluster.on('message', (worker, message) => {
         if (_isRpcMessage(message)) {
-            _handlePrimaryMessage(worker, message, handlers);
+            _handlePrimaryMessage(worker?.id, message);
         }
     });
 }
@@ -206,13 +186,10 @@ export function setupRPCPrimary(handlers?: PrimaryHandlersMap, options?: RPCSetu
  * @return {undefined}
  * }
  */
-export function setupRPCWorker(handlers: HandlersMap, options?: RPCSetupOptions) {
+export function setupRPCWorker(handlers: HandlersMap) {
     if (!process.send) {
         throw new Error('fatal: cannot setup cluster RPC: "process.send" is not available');
     }
-    if (options?.werelogsConfig) {
-        werelogs.configure(options.werelogsConfig);
-    }
     process.on('message', (message: RPCCommandMessage | RPCCommandResultsMessage) => {
         if (_isRpcMessage(message)) {
             _handleWorkerMessage(message, handlers);
@@ -224,9 +201,8 @@ export function setupRPCWorker(handlers: HandlersMap, options?: RPCSetupOptions)
  * Send a command for workers to execute in parallel, and wait for results
  *
  * @param {string} toWorkers - which workers should execute the command
- *     Currently the supported values are:
+ *     Currently the only supported value is "*", meaning all workers will
- *         - "*", meaning all workers will execute the command
+ *     execute the command
- *         - "PRIMARY", meaning primary process will execute the command
  * @param {string} toHandler - name of handler that will execute the
  * command in workers, as declared in setupRPCWorker() parameter object
  * @param {string} uids - unique identifier of the command, must be
@@ -254,7 +230,7 @@ export async function sendWorkerCommand(
     }
     rpcLogger.info('sending command', { toWorkers, toHandler, uids, payload });
     return new Promise((resolve, reject) => {
-        let timeout: NodeJS.Timeout | null = null;
+        let timeout: NodeJS.Timer | null = null;
         if (timeoutMs) {
             timeout = setTimeout(() => {
                 delete uidsToCommandPromise[uids];
@@ -312,27 +288,10 @@ function _dispatchCommandErrorToWorker(
     worker.send(message);
 }
 
-function _sendPrimaryCommandResult(
-    worker: Worker,
-    uids: string,
-    error: (Error & { code?: number }) | null | undefined,
-    result?: any
-): void {
-    const message: RPCCommandResultsMessage = {
-        type: 'cluster-rpc:commandResults',
-        uids,
-        payload: {
-            results: [{ error: error?.message || null, errorCode: error?.code, result }],
-        },
-    };
-    worker.send?.(message);
-}
-
 function _handlePrimaryCommandMessage(
-    fromWorker: Worker,
+    fromWorkerId: number,
     logger: any,
-    message: RPCCommandMessage,
+    message: RPCCommandMessage
-    handlers?: PrimaryHandlersMap
 ): void {
     const { toWorkers, toHandler, uids, payload } = message;
     if (toWorkers === '*') {
@@ -346,7 +305,7 @@ function _handlePrimaryCommandMessage(
         for (const workerId of Object.keys(cluster.workers || {})) {
             commandResults[workerId] = null;
         }
-        uidsToWorkerId[uids] = fromWorker?.id;
+        uidsToWorkerId[uids] = fromWorkerId;
         uidsToCommandResults[uids] = commandResults;
 
         for (const [workerId, worker] of Object.entries(cluster.workers || {})) {
@@ -357,21 +316,11 @@ function _handlePrimaryCommandMessage(
                 worker.send(message);
             }
         }
-    } else if (toWorkers === 'PRIMARY') {
-        const { toHandler, uids, payload } = message;
-        const cb: HandlerCallback = (err, result) => _sendPrimaryCommandResult(fromWorker, uids, err, result);
-
-        if (toHandler in (handlers || {})) {
-            return handlers![toHandler](fromWorker, payload, uids, cb);
-        }
-        logger.error('no such handler in "toHandler" field from worker command message', {
-            toHandler,
-        });
-        return cb(errors.NotImplemented);
     } else {
         logger.error('unsupported "toWorkers" field from worker command message', {
             toWorkers,
         });
+        const fromWorker = cluster.workers?.[fromWorkerId];
         if (fromWorker) {
             _dispatchCommandErrorToWorker(fromWorker, uids, errors.NotImplemented);
         }
@@ -429,23 +378,22 @@ function _handlePrimaryCommandResultMessage(
 }
 
 function _handlePrimaryMessage(
-    fromWorker: Worker,
+    fromWorkerId: number,
-    message: RPCCommandMessage | RPCCommandResultMessage,
+    message: RPCCommandMessage | RPCCommandResultMessage
-    handlers?: PrimaryHandlersMap
 ): void {
     const { type: messageType, uids } = message;
     const logger = rpcLogger.newRequestLoggerFromSerializedUids(uids);
     logger.debug('primary received message from worker', {
-        workerId: fromWorker?.id, rpcMessage: message,
+        workerId: fromWorkerId, rpcMessage: message,
     });
     if (messageType === 'cluster-rpc:command') {
-        return _handlePrimaryCommandMessage(fromWorker, logger, message, handlers);
+        return _handlePrimaryCommandMessage(fromWorkerId, logger, message);
     }
     if (messageType === 'cluster-rpc:commandResult') {
-        return _handlePrimaryCommandResultMessage(fromWorker?.id, logger, message);
+        return _handlePrimaryCommandResultMessage(fromWorkerId, logger, message);
     }
     logger.error('unsupported message type', {
-        workerId: fromWorker?.id, messageType, uids,
+        workerId: fromWorkerId, messageType, uids,
     });
     return undefined;
 }
@@ -507,9 +455,6 @@ function _handleWorkerCommandResultsMessage(
                 workerError = new Error(workerResult.error);
             }
         }
-        if (workerError && workerResult.errorCode) {
-            (workerError as Error & { code: number }).code = workerResult.errorCode;
-        }
         const unmarshalledResult: ResultObject = {
             error: workerError,
             result: workerResult.result,

lib/constants.ts

@@ -172,6 +172,3 @@ export const maxCachedBuckets = process.env.METADATA_MAX_CACHED_BUCKETS ?
 
 export const validRestoreObjectTiers = new Set(['Expedited', 'Standard', 'Bulk']);
 export const maxBatchingConcurrentOperations = 5;
-
-/** For policy resource arn check we allow empty account ID to not break compatibility */
-export const policyArnAllowedEmptyAccountId = ['utapi', 'scuba'];

lib/db.ts

@@ -148,7 +148,7 @@ export class IndexTransaction {
                 'missing condition for conditional put'
             );
         }
-        if (typeof condition.notExists !== 'string' && typeof condition.exists !== 'string') {
+        if (typeof condition.notExists !== 'string') {
             throw propError(
                 'unsupportedConditionalOperation',
                 'missing key or supported condition'

lib/errors/arsenalErrors.ts

@@ -1042,15 +1042,3 @@ export const AuthMethodNotImplemented: ErrorFormat = {
     description: 'AuthMethodNotImplemented',
     code: 501,
 };
-
-// --------------------- quotaErros ---------------------
-
-export const NoSuchQuota: ErrorFormat = {
-    code: 404,
-    description: 'The specified resource does not have a quota.',
-};
-
-export const QuotaExceeded: ErrorFormat = {
-    code: 429,
-    description: 'The quota set for the resource is exceeded.',
-};

lib/models/BackendInfo.ts

@@ -1,5 +1,3 @@
-import { RequestLogger } from 'werelogs';
-
 import { legacyLocations } from '../constants';
 import escapeForXml from '../s3middleware/escapeForXml';
 

lib/models/BucketInfo.ts

@@ -101,7 +101,6 @@ export default class BucketInfo {
     _azureInfo: any | null;
     _ingestion: { status: 'enabled' | 'disabled' } | null;
     _capabilities?: Capabilities;
-    _quotaMax: number | 0;
 
     /**
     * Represents all bucket information.
@@ -158,7 +157,6 @@ export default class BucketInfo {
     * @param [notificationConfiguration] - bucket notification configuration
     * @param [tags] - bucket tag set
     * @param [capabilities] - capabilities for the bucket
-    * @param quotaMax - bucket quota
     */
     constructor(
         name: string,
@@ -187,7 +185,6 @@ export default class BucketInfo {
         notificationConfiguration?: any,
         tags?: Array<BucketTag> | [],
         capabilities?: Capabilities,
-        quotaMax?: number | 0,
     ) {
         assert.strictEqual(typeof name, 'string');
         assert.strictEqual(typeof owner, 'string');
@@ -288,10 +285,6 @@ export default class BucketInfo {
             tags = [] as BucketTag[];
         }
         assert.strictEqual(areTagsValid(tags), true);
-        if (quotaMax) {
-            assert.strictEqual(typeof quotaMax, 'number');
-            assert(quotaMax >= 0, 'Quota cannot be negative');
-        }
 
         // IF UPDATING PROPERTIES, INCREMENT MODELVERSION NUMBER ABOVE
         this._acl = aclInstance;
@@ -320,7 +313,6 @@ export default class BucketInfo {
         this._notificationConfiguration = notificationConfiguration || null;
         this._tags = tags;
         this._capabilities = capabilities || undefined;
-        this._quotaMax = quotaMax || 0;
         return this;
     }
 
@@ -356,7 +348,6 @@ export default class BucketInfo {
             notificationConfiguration: this._notificationConfiguration,
             tags: this._tags,
             capabilities: this._capabilities,
-            quotaMax: this._quotaMax,
         };
         const final = this._websiteConfiguration
             ? {
@@ -383,7 +374,7 @@ export default class BucketInfo {
             obj.bucketPolicy, obj.uid, obj.readLocationConstraint, obj.isNFS,
             obj.ingestion, obj.azureInfo, obj.objectLockEnabled,
             obj.objectLockConfiguration, obj.notificationConfiguration, obj.tags,
-            obj.capabilities, obj.quotaMax);
+            obj.capabilities);
     }
 
     /**
@@ -410,8 +401,7 @@ export default class BucketInfo {
             data._bucketPolicy, data._uid, data._readLocationConstraint,
             data._isNFS, data._ingestion, data._azureInfo,
             data._objectLockEnabled, data._objectLockConfiguration,
-            data._notificationConfiguration, data._tags, data._capabilities,
+            data._notificationConfiguration, data._tags, data._capabilities);
-            data._quotaMax);
     }
 
     /**
@@ -949,22 +939,4 @@ export default class BucketInfo {
         this._capabilities = capabilities;
         return this;
     }
-
-    /**
-     * Get the bucket quota information
-     * @return quotaMax
-     */
-    getQuota() {
-        return this._quotaMax;
-    }
-    
-    /**
-     * Set bucket quota
-     * @param quota - quota to be set
-     * @return - bucket quota info
-     */
-    setQuota(quota: number) {
-        this._quotaMax = quota || 0;
-        return this;
-    }
 }

lib/models/ReplicationConfiguration.ts

@@ -1,8 +1,6 @@
 import assert from 'assert';
 import UUID from 'uuid';
 
-import { RequestLogger } from 'werelogs';
-
 import escapeForXml from '../s3middleware/escapeForXml';
 import errors from '../errors';
 import { isValidBucketName } from '../s3routes/routesUtils';

lib/network/http/server.ts

@@ -435,6 +435,7 @@ export default class Server {
             this._server.on('connection', sock => {
                 // Setting no delay of the socket to the value configured
                 // TODO fix this
+                // @ts-expect-errors
                 sock.setNoDelay(this.isNoDelay());
                 sock.on('error', err => this._logger.info(
                     'socket error - request rejected', { error: err }));

lib/network/probe/HealthProbeServer.ts

@@ -62,7 +62,7 @@ export default class HealthProbeServer extends httpServer {
     _onLiveness(
         _req: http.IncomingMessage,
         res: http.ServerResponse,
-        log: werelogs.RequestLogger,
+        log: RequestLogger,
     ) {
         if (this._livenessCheck(log)) {
             sendSuccess(res, log);
@@ -74,7 +74,7 @@ export default class HealthProbeServer extends httpServer {
     _onReadiness(
         _req: http.IncomingMessage,
         res: http.ServerResponse,
-        log: werelogs.RequestLogger,
+        log: RequestLogger,
     ) {
         if (this._readinessCheck(log)) {
             sendSuccess(res, log);

lib/network/probe/ProbeServer.ts

@@ -16,7 +16,7 @@ export const DEFAULT_METRICS_ROUTE = '/metrics';
  * @param log - Werelogs instance for logging if you choose to
  */
 
-export type ProbeDelegate = (res: http.ServerResponse, log: werelogs.RequestLogger) => string | void
+export type ProbeDelegate = (res: http.ServerResponse, log: RequestLogger) => string | void
 
 export type ProbeServerParams = {
     port: number;

lib/network/probe/Utils.ts

@@ -1,7 +1,4 @@
 import * as http from 'http';
-
-import { RequestLogger } from 'werelogs';
-
 import { ArsenalError } from '../../errors';
 
 /**

lib/network/rest/RESTClient.ts

@@ -119,7 +119,7 @@ export default class RESTClient {
         method: string,
         headers: http.OutgoingHttpHeaders | null,
         key: string | null,
-        log: werelogs.RequestLogger,
+        log: RequestLogger,
         responseCb: (res: http.IncomingMessage) => void,
     ) {
         const reqHeaders = headers || {};

lib/network/rest/RESTServer.ts

@@ -25,7 +25,7 @@ function setContentRange(
 
 function sendError(
     res: http.ServerResponse,
-    log: werelogs.RequestLogger,
+    log: RequestLogger,
     error: ArsenalError,
     optMessage?: string,
 ) {
@@ -141,7 +141,7 @@ export default class RESTServer extends httpServer {
     _onPut(
         req: http.IncomingMessage,
         res: http.ServerResponse,
-        log: werelogs.RequestLogger,
+        log: RequestLogger,
     ) {
         let size: number;
         try {
@@ -183,7 +183,7 @@ export default class RESTServer extends httpServer {
     _onGet(
         req: http.IncomingMessage,
         res: http.ServerResponse,
-        log: werelogs.RequestLogger,
+        log: RequestLogger,
     ) {
         let pathInfo: ReturnType<typeof parseURL>;
         let rangeSpec: ReturnType<typeof httpUtils.parseRangeSpec> | undefined =
@@ -266,7 +266,7 @@ export default class RESTServer extends httpServer {
     _onDelete(
         req: http.IncomingMessage,
         res: http.ServerResponse,
-        log: werelogs.RequestLogger,
+        log: RequestLogger,
     ) {
         let pathInfo: ReturnType<typeof parseURL>;
         try {

lib/policyEvaluator/RequestContext.ts

@@ -12,39 +12,13 @@ import {
     actionMapSSO,
     actionMapSTS,
     actionMapMetadata,
-    actionMapScuba,
 } from './utils/actionMaps';
 
-export const actionNeedQuotaCheck = {
+const _actionNeedQuotaCheck = {
     objectPut: true,
-    objectPutVersion: true,
     objectPutPart: true,
-    objectRestore: true,
 };
 
-/**
- * This variable describes APIs that change the bytes
- * stored, requiring quota updates
- */
-export const actionWithDataDeletion = {
-    objectDelete: true,
-    objectDeleteVersion: true,
-    multipartDelete: true,
-    multiObjectDelete: true,
-};
-
-/**
- * The function returns true if the current API call is a copy object
- * and the action requires a quota evaluation logic, post retrieval
- * of the object metadata.
- * @param {string} action - the action being performed
- * @param {string} currentApi - the current API being called
- * @return {boolean} - whether the action requires a quota check
- */
-export function actionNeedQuotaCheckCopy(action: string, currentApi: string) {
-    return action === 'objectGet' && (currentApi === 'objectCopy' || currentApi === 'objectPutCopyPart');
-}
-
 function _findAction(service: string, method: string) {
     switch (service) {
         case 's3':
@@ -62,8 +36,6 @@ function _findAction(service: string, method: string) {
             return actionMapSTS[method];
         case 'metadata':
             return actionMapMetadata[method];
-        case 'scuba':
-            return actionMapScuba[method];
         default:
             return undefined;
     }
@@ -133,10 +105,6 @@ function _buildArn(
             return `arn:scality:metadata::${requesterInfo!.accountid}:` +
             `${generalResource}/`;
         }
-        case 'scuba': {
-            return `arn:scality:scuba::${requesterInfo!.accountid}:` +
-            `${generalResource}${specificResource ? '/' + specificResource : ''}`;
-        }
         default:
             return undefined;
     }
@@ -256,8 +224,7 @@ export default class RequestContext {
         this._securityToken = securityToken;
         this._policyArn = policyArn;
         this._action = action;
-        this._needQuota = actionNeedQuotaCheck[apiMethod] === true
+        this._needQuota = _actionNeedQuotaCheck[apiMethod] === true;
-            || actionWithDataDeletion[apiMethod] === true;
         this._requestObjTags = requestObjTags || null;
         this._existingObjTag = existingObjTag || null;
         this._needTagEval = needTagEval || false;

lib/policyEvaluator/utils/actionMaps.ts

@@ -52,12 +52,6 @@ const sharedActionMap = {
     objectPutVersion: 's3:PutObjectVersion',
 };
 
-const actionMapBucketQuotas = {
-    bucketGetQuota: 'scality:GetBucketQuota',
-    bucketUpdateQuota: 'scality:UpdateBucketQuota',
-    bucketDeleteQuota: 'scality:DeleteBucketQuota',
-};
-
 // action map used for request context
 const actionMapRQ = {
     bucketPut: 's3:CreateBucket',
@@ -71,7 +65,6 @@ const actionMapRQ = {
     initiateMultipartUpload: 's3:PutObject',
     objectDeleteVersion: 's3:DeleteObjectVersion',
     objectDeleteTaggingVersion: 's3:DeleteObjectVersionTagging',
-    objectGetArchiveInfo: 'scality:GetObjectArchiveInfo',
     objectGetVersion: 's3:GetObjectVersion',
     objectGetACLVersion: 's3:GetObjectVersionAcl',
     objectGetTaggingVersion: 's3:GetObjectVersionTagging',
@@ -86,7 +79,6 @@ const actionMapRQ = {
     objectPutLegalHoldVersion: 's3:PutObjectLegalHold',
     listObjectVersions: 's3:ListBucketVersions',
     ...sharedActionMap,
-    ...actionMapBucketQuotas,
 };
 
 // action map used for bucket policies
@@ -159,15 +151,6 @@ const actionMonitoringMapS3 = {
     objectPutTagging: 'PutObjectTagging',
     objectRestore: 'RestoreObject',
     serviceGet: 'ListBuckets',
-    bucketGetQuota: 'GetBucketQuota',
-    bucketUpdateQuota: 'UpdateBucketQuota',
-    bucketDeleteQuota: 'DeleteBucketQuota', 
-};
-
-const actionMapAccountQuotas = {
-    UpdateAccountQuota : 'scality:UpdateAccountQuota',
-    DeleteAccountQuota : 'scality:DeleteAccountQuota',
-    GetAccountQuota : 'scality:GetAccountQuota',
 };
 
 const actionMapIAM = {
@@ -211,7 +194,6 @@ const actionMapIAM = {
     tagUser: 'iam:TagUser',
     unTagUser: 'iam:UntagUser',
     listUserTags: 'iam:ListUserTags',
-    ...actionMapAccountQuotas,
 };
 
 const actionMapSSO = {
@@ -227,14 +209,6 @@ const actionMapMetadata = {
     default: 'metadata:bucketd',
 };
 
-const actionMapScuba = {
-    GetMetrics: 'scuba:GetMetrics',
-    AdminStartIngest: 'scuba:AdminStartIngest',
-    AdminStopIngest: 'scuba:AdminStopIngest',
-    AdminReadRaftCseq: 'scuba:AdminReadRaftCseq',
-    AdminTriggerRepair: 'scuba:AdminTriggerRepair',
-};
-
 export {
     actionMapRQ,
     actionMapBP,
@@ -244,5 +218,4 @@ export {
     actionMapSSO,
     actionMapSTS,
     actionMapMetadata,
-    actionMapScuba,
 };

lib/policyEvaluator/utils/checkArnMatch.ts

@@ -1,5 +1,5 @@
 import { handleWildcardInResource } from './wildcards';
-import { policyArnAllowedEmptyAccountId } from '../../constants';
+
 /**
  * Checks whether an ARN from a request matches an ARN in a policy
  * to compare against each portion of the ARN from the request
@@ -38,10 +38,9 @@ export default function checkArnMatch(
         const requestSegment = caseSensitive ? requestArnArr[j] :
             requestArnArr[j].toLowerCase();
         const policyArnArr = policyArn.split(':');
-        // We want to allow an empty account ID for utapi and scuba service ARNs to not
+        // We want to allow an empty account ID for utapi service ARNs to not
         // break compatibility.
-        if (j === 4 && policyArnAllowedEmptyAccountId.includes(policyArnArr[2])
+        if (j === 4 && policyArnArr[2] === 'utapi' && policyArnArr[4] === '') {
-            && policyArnArr[4] === '') {
             continue;
         } else if (!segmentRegEx.test(requestSegment)) {
             return false;

lib/s3middleware/azureHelpers/mpuUtils.ts

@@ -2,9 +2,6 @@ import assert from 'assert';
 import * as crypto from 'crypto';
 import * as stream from 'stream';
 import azure from '@azure/storage-blob';
-
-import { RequestLogger } from 'werelogs';
-
 import ResultsCollector from './ResultsCollector';
 import SubStreamInterface from './SubStreamInterface';
 import * as objectUtils from '../objectUtils';

lib/s3routes/routes.ts

@@ -1,7 +1,4 @@
 import assert from 'assert';
-
-import { RequestLogger } from 'werelogs';
-
 import errors from '../errors';
 import routeGET from './routes/routeGET';
 import routePUT from './routes/routePUT';

lib/s3routes/routes/routeDELETE.ts

@@ -1,5 +1,3 @@
-import { RequestLogger } from 'werelogs';
-
 import * as routesUtils from '../routesUtils';
 import errors from '../../errors';
 import StatsClient from '../../metrics/StatsClient';
@@ -43,8 +41,6 @@ export default function routeDELETE(
             return call('bucketDeleteEncryption');
         } else if (query?.tagging !== undefined) {
             return call('bucketDeleteTagging');
-        } else if (query?.quota !== undefined) {
-            return call('bucketDeleteQuota');
         }
         call('bucketDelete');
     } else {

lib/s3routes/routes/routeGET.ts

@@ -1,5 +1,3 @@
-import { RequestLogger } from 'werelogs';
-
 import * as routesUtils from '../routesUtils';
 import errors from '../../errors';
 import * as http from 'http';
@@ -60,8 +58,6 @@ export default function routerGET(
             call('bucketGetEncryption');
         } else if (query.search !== undefined) {
             call('metadataSearch')
-        } else if (query.quota !== undefined) {
-            call('bucketGetQuota');
         } else {
             // GET bucket
             call('bucketGet');

lib/s3routes/routes/routeHEAD.ts

@@ -1,5 +1,3 @@
-import { RequestLogger } from 'werelogs';
-
 import * as routesUtils from '../routesUtils';
 import errors from '../../errors';
 import StatsClient from '../../metrics/StatsClient';

lib/s3routes/routes/routeOPTIONS.ts

@@ -1,5 +1,3 @@
-import { RequestLogger } from 'werelogs';
-
 import * as routesUtils from '../routesUtils';
 import errors from '../../errors';
 import * as http from 'http';

lib/s3routes/routes/routePOST.ts

@@ -1,5 +1,3 @@
-import { RequestLogger } from 'werelogs';
-
 import * as routesUtils from '../routesUtils';
 import errors from '../../errors';
 import * as http from 'http';

lib/s3routes/routes/routePUT.ts

@@ -1,5 +1,3 @@
-import { RequestLogger } from 'werelogs';
-
 import * as routesUtils from '../routesUtils';
 import errors from '../../errors';
 import * as http from 'http';
@@ -105,13 +103,6 @@ export default function routePUT(
                     return routesUtils.responseNoBody(err, corsHeaders,
                         response, 200, log);
                 });
-        } else if (query.quota !== undefined) {
-            api.callApiMethod('bucketUpdateQuota', request, response,
-                log, (err, resHeaders) => {
-                    routesUtils.statsReport500(err, statsClient);
-                    return routesUtils.responseNoBody(err, resHeaders, response,
-                        200, log);
-                });
         } else {
             // PUT bucket
             return api.callApiMethod('bucketPut', request, response, log,

lib/s3routes/routes/routeWebsite.ts

@@ -1,5 +1,3 @@
-import { RequestLogger } from 'werelogs';
-
 import * as routesUtils from '../routesUtils';
 import errors from '../../errors';
 import * as http from 'http';

lib/s3routes/routesUtils.ts

@@ -1,13 +1,10 @@
 import * as url from 'url';
-import * as http from 'http';
-import { eachSeries } from 'async';
-
-import { RequestLogger } from 'werelogs';
-
 import * as ipCheck from '../ipCheck';
 import errors, { ArsenalError } from '../errors';
 import * as constants from '../constants';
+import { eachSeries } from 'async';
 import DataWrapper from '../storage/data/DataWrapper';
+import * as http from 'http';
 import StatsClient from '../metrics/StatsClient';
 import { objectKeyByteLimit } from '../constants';
 const jsutil = require('../jsutil');

lib/storage/data/DataWrapper.js

@@ -2,8 +2,6 @@ const async = require('async');
 const PassThrough = require('stream').PassThrough;
 const assert = require('assert');
 
-const { Logger } = require('werelogs');
-
 const errors = require('../../errors').default;
 const MD5Sum = require('../../s3middleware/MD5Sum').default;
 const NullStream = require('../../s3middleware/nullStream').default;
@@ -29,7 +27,6 @@ class DataWrapper {
         this.metadata = metadata;
         this.locStorageCheckFn = locStorageCheckFn;
         this.vault = vault;
-        this.logger = new Logger('DataWrapper');
     }
 
     put(cipherBundle, value, valueSize, keyContext, backendInfo, log, cb) {
@@ -130,7 +127,7 @@ class DataWrapper {
     }
 
     delete(objectGetInfo, log, cb) {
-        const callback = cb || (() => {});
+        const callback = cb || log.end;
         const isMdModelVersion2 = typeof(objectGetInfo) === 'string';
         const isRequiredStringKey =
             constants.clientsRequireStringKey[this.implName];
@@ -179,9 +176,7 @@ class DataWrapper {
             newObjDataStoreName)) {
             return process.nextTick(cb);
         }
-        const delLog = this.logger.newRequestLoggerFromSerializedUids(
+        log.trace('initiating batch delete', {
-            log.getSerializedUids());
-        delLog.trace('initiating batch delete', {
             keys: locations,
             implName: this.implName,
             method: 'batchDelete',
@@ -207,21 +202,21 @@ class DataWrapper {
             return false;
         });
         if (shouldBatchDelete && keys.length > 1) {
-            return this.client.batchDelete(backendName, { keys }, delLog, cb);
+            return this.client.batchDelete(backendName, { keys }, log, cb);
         }
         return async.eachLimit(locations, 5, (loc, next) => {
-            process.nextTick(() => this.delete(loc, delLog, next));
+            process.nextTick(() => this.delete(loc, log, next));
         },
         err => {
             if (err) {
-                delLog.end().error('batch delete failed', { error: err });
+                log.end().error('batch delete failed', { error: err });
                 // deletion of non-existing objects result in 204
                 if (err.code === 404) {
                     return cb();
                 }
                 return cb(err);
             }
-            delLog.end().trace('batch delete successfully completed');
+            log.end().trace('batch delete successfully completed');
             return cb();
         });
     }

lib/storage/data/LocationConstraintParser.js

@@ -1,10 +1,10 @@
 const { http, https } = require('httpagent');
 const url = require('url');
 const AWS = require('aws-sdk');
+const Sproxy = require('sproxydclient');
+const Hyperdrive = require('hdclient');
 const HttpsProxyAgent = require('https-proxy-agent');
 
-require("aws-sdk/lib/maintenance_mode_message").suppress = true;
-
 const constants = require('../../constants');
 const DataFileBackend = require('./file/DataFileInterface');
 const inMemory = require('./in_memory/datastore').backend;
@@ -25,13 +25,8 @@ function parseLC(config, vault) {
         if (locationObj.type === 'file') {
             clients[location] = new DataFileBackend(config);
         }
-        if (locationObj.type === 'vitastor') {
-            const VitastorBackend = require('./vitastor/VitastorBackend');
-            clients[location] = new VitastorBackend(location, locationObj.details);
-        }
         if (locationObj.type === 'scality') {
             if (locationObj.details.connector.sproxyd) {
-                const Sproxy = require('sproxydclient');
                 clients[location] = new Sproxy({
                     bootstrap: locationObj.details.connector
                         .sproxyd.bootstrap,
@@ -46,7 +41,6 @@ function parseLC(config, vault) {
                 });
                 clients[location].clientType = 'scality';
             } else if (locationObj.details.connector.hdclient) {
-                const Hyperdrive = require('hdclient');
                 clients[location] = new Hyperdrive.hdcontroller.HDProxydClient(
                     locationObj.details.connector.hdclient);
                 clients[location].clientType = 'scality';

lib/storage/data/MultipleBackendGateway.js

@@ -5,7 +5,6 @@ const { parseTagFromQuery } = require('../../s3middleware/tagging');
 const { externalBackendHealthCheckInterval } = require('../../constants');
 const DataFileBackend = require('./file/DataFileInterface');
 const { createLogger, checkExternalBackend } = require('./external/utils');
-const jsutil = require('../../jsutil');
 
 class MultipleBackendGateway {
     constructor(clients, metadata, locStorageCheckFn) {
@@ -200,12 +199,11 @@ class MultipleBackendGateway {
     uploadPart(request, streamingV4Params, stream, size, location, key,
         uploadId, partNumber, bucketName, log, cb) {
         const client = this.clients[location];
-        const cbOnce = jsutil.once(cb);
 
         if (client.uploadPart) {
             return this.locStorageCheckFn(location, size, log, err => {
                 if (err) {
-                    return cbOnce(err);
+                    return cb(err);
                 }
                 return client.uploadPart(request, streamingV4Params, stream,
                     size, key, uploadId, partNumber, bucketName, log,
@@ -219,14 +217,14 @@ class MultipleBackendGateway {
                                     'metric following object PUT failure',
                                         { error: error.message });
                                     }
-                                    return cbOnce(err);
+                                    return cb(err);
                                 });
                         }
-                        return cbOnce(null, partInfo);
+                        return cb(null, partInfo);
                     });
             });
         }
-        return cbOnce();
+        return cb();
     }
 
     listParts(key, uploadId, location, bucketName, partNumberMarker, maxParts,

lib/storage/data/external/AwsClient.js

@@ -8,7 +8,6 @@ const getMetaHeaders =
 const { prepareStream } = require('../../../s3middleware/prepareStream');
 const { createLogger, logHelper, removeQuotes, trimXMetaPrefix } =
     require('./utils');
-const jsutil = require('../../../jsutil');
 
 const missingVerIdInternalError = errors.InternalError.customizeDescription(
     'Invalid state. Please ensure versioning is enabled ' +
@@ -318,11 +317,9 @@ class AwsClient {
     uploadPart(request, streamingV4Params, stream, size, key, uploadId,
         partNumber, bucketName, log, callback) {
         let hashedStream = stream;
-        const cbOnce = jsutil.once(callback);
-
         if (request) {
             const partStream = prepareStream(request, streamingV4Params,
-                this._vault, log, cbOnce);
+                this._vault, log, callback);
             hashedStream = new MD5Sum();
             partStream.pipe(hashedStream);
         }
@@ -336,7 +333,7 @@ class AwsClient {
             if (err) {
                 logHelper(log, 'error', 'err from data backend ' +
                     'on uploadPart', err, this._dataStoreName, this.clientType);
-                return cbOnce(errors.ServiceUnavailable
+                return callback(errors.ServiceUnavailable
                     .customizeDescription('Error returned from ' +
                     `${this.type}: ${err.message}`),
                 );
@@ -350,7 +347,7 @@ class AwsClient {
                 dataStoreName: this._dataStoreName,
                 dataStoreETag: noQuotesETag,
             };
-            return cbOnce(null, dataRetrievalInfo);
+            return callback(null, dataRetrievalInfo);
         });
     }
 

lib/storage/data/vitastor/VitastorBackend.ts

@@ -1,696 +0,0 @@
-// Zenko CloudServer Vitastor data storage backend adapter
-// Copyright (c) Vitaliy Filippov, 2019+
-// License: VNPL-1.1 (see README.md for details)
-
-const stream = require('stream');
-
-const vitastor = require('vitastor');
-
-const VOLUME_MAGIC = 'VstS3Vol';
-const OBJECT_MAGIC = 'VstS3Obj';
-const FLAG_DELETED = 2n;
-
-type Volume = {
-    id: number,
-    partial_sectors: {
-        [key: string]: {
-            buffer: Buffer,
-            refs: number,
-        },
-    },
-    header: {
-        location: string,
-        bucket: string,
-        max_size: number,
-        create_ts: number,
-        used_ts: number,
-        size: number,
-        objects: number,
-        removed_objects: number,
-        object_bytes: number,
-        removed_bytes: number,
-    },
-};
-
-type ObjectHeader = {
-    size: number,
-    key: string,
-    part_num?: number,
-};
-
-class VitastorBackend
-{
-    locationName: string;
-    config: {
-        pool_id: number,
-        metadata_image: string,
-        metadata_pool_id: number,
-        metadata_inode_num: number,
-        size_buckets: number[],
-        size_bucket_mul: number,
-        id_batch_size: number,
-        sector_size: number,
-        write_chunk_size: number,
-        read_chunk_size: number,
-        pack_objects: boolean,
-        // and also other parameters for vitastor itself
-    };
-    next_id: number;
-    alloc_id: number;
-    opened: boolean;
-    on_open: ((...args: any[]) => void)[] | null;
-    open_error: Error | null;
-    cli: any;
-    kv: any;
-    volumes: {
-        [bucket: string]: {
-            [max_size: string]: Volume,
-        },
-    };
-    volumes_by_id: {
-        [id: string]: Volume,
-    };
-    volume_delete_stats: {
-        [id: string]: {
-            count: number,
-            bytes: number,
-        },
-    };
-
-    constructor(locationName, config)
-    {
-        this.locationName = locationName;
-        this.config = config;
-        // validate config
-        this.config.pool_id = Number(this.config.pool_id) || 0;
-        if (!this.config.pool_id)
-            throw new Error('pool_id is required for Vitastor');
-        if (!this.config.metadata_image && (!this.config.metadata_pool_id || !this.config.metadata_inode_num))
-            throw new Error('metadata_image or metadata_inode is required for Vitastor');
-        if (!this.config.size_buckets || !this.config.size_buckets.length)
-            this.config.size_buckets = [ 32*1024, 128*1024, 512*1024, 2*1024, 8*1024 ];
-        this.config.size_bucket_mul = Number(this.config.size_bucket_mul) || 2;
-        this.config.id_batch_size = Number(this.config.id_batch_size) || 100;
-        this.config.sector_size = Number(this.config.sector_size) || 0;
-        if (this.config.sector_size < 4096)
-            this.config.sector_size = 4096;
-        this.config.write_chunk_size = Number(this.config.write_chunk_size) || 0;
-        if (this.config.write_chunk_size < this.config.sector_size)
-            this.config.write_chunk_size = 4*1024*1024; // 4 MB
-        this.config.read_chunk_size = Number(this.config.read_chunk_size) || 0;
-        if (this.config.read_chunk_size < this.config.sector_size)
-            this.config.read_chunk_size = 4*1024*1024; // 4 MB
-        this.config.pack_objects = !!this.config.pack_objects;
-        // state
-        this.next_id = 1;
-        this.alloc_id = 0;
-        this.opened = false;
-        this.on_open = null;
-        this.open_error = null;
-        this.cli = new vitastor.Client(config);
-        this.kv = new vitastor.KV(this.cli);
-        // we group objects into volumes by bucket and size
-        this.volumes = {};
-        this.volumes_by_id = {};
-        this.volume_delete_stats = {};
-    }
-
-    async _makeVolumeId()
-    {
-        if (this.next_id <= this.alloc_id)
-        {
-            return this.next_id++;
-        }
-        const id_key = 'id'+this.config.pool_id;
-        const [ err, prev ] = await new Promise<[ any, string ]>(ok => this.kv.get(id_key, (err, value) => ok([ err, value ])));
-        if (err && err != vitastor.ENOENT)
-        {
-            throw new Error(err);
-        }
-        const new_id = (parseInt(prev) || 0) + 1;
-        this.next_id = new_id;
-        this.alloc_id = this.next_id + this.config.id_batch_size - 1;
-        await new Promise((ok, no) => this.kv.set(id_key, this.alloc_id, err => (err ? no(new Error(err)) : ok(null)), cas_old => cas_old === prev));
-        return this.next_id;
-    }
-
-    async _getVolume(bucketName, size)
-    {
-        if (!this.opened)
-        {
-            if (this.on_open)
-            {
-                await new Promise(ok => this.on_open!.push(ok));
-            }
-            else
-            {
-                this.on_open = [];
-                if (this.config.metadata_image)
-                {
-                    const img = new vitastor.Image(this.cli, this.config.metadata_image);
-                    const info = await new Promise<{ pool_id: number, inode_num: number }>(ok => img.get_info(ok));
-                    this.config.metadata_pool_id = info.pool_id;
-                    this.config.metadata_inode_num = info.inode_num;
-                }
-                const kv_config = {};
-                for (const key in this.config)
-                {
-                    if (key.substr(0, 3) === 'kv_')
-                        kv_config[key] = this.config[key];
-                }
-                this.open_error = await new Promise(ok => this.kv.open(
-                    this.config.metadata_pool_id, this.config.metadata_inode_num,
-                    kv_config, err => ok(err ? new Error(err) : null)
-                ));
-                this.opened = true;
-                this.on_open.map(cb => setImmediate(cb));
-                this.on_open = null;
-            }
-        }
-        if (this.open_error)
-        {
-            throw this.open_error;
-        }
-        let i;
-        for (i = 0; i < this.config.size_buckets.length && size >= this.config.size_buckets[i]; i++) {}
-        let s;
-        if (i < this.config.size_buckets.length)
-            s = this.config.size_buckets[i];
-        else if (this.config.size_bucket_mul > 1)
-        {
-            while (size >= s)
-                s = Math.floor(this.config.size_bucket_mul * s);
-        }
-        if (!this.volumes[bucketName])
-        {
-            this.volumes[bucketName] = {};
-        }
-        if (this.volumes[bucketName][s])
-        {
-            return this.volumes[bucketName][s];
-        }
-        const new_id = await this._makeVolumeId();
-        const new_vol = this.volumes[bucketName][s] = {
-            id: new_id,
-            // FIXME: partial_sectors should be written with CAS because otherwise we may lose quick deletes
-            partial_sectors: {},
-            header: {
-                location: this.locationName,
-                bucket: bucketName,
-                max_size: s,
-                create_ts: Date.now(),
-                used_ts: Date.now(),
-                size: this.config.sector_size, // initial position is right after header
-                objects: 0,
-                removed_objects: 0,
-                object_bytes: 0,
-                removed_bytes: 0,
-            },
-        };
-        this.volumes_by_id[new_id] = new_vol;
-        const header_text = JSON.stringify(this.volumes[bucketName][s].header);
-        const buf = Buffer.alloc(this.config.sector_size);
-        buf.write(VOLUME_MAGIC + header_text, 0);
-        await new Promise((ok, no) => this.cli.write(
-            this.config.pool_id, new_id, 0, buf, err => (err ? no(new Error(err)) : ok(null))
-        ));
-        await new Promise((ok, no) => this.kv.set(
-            'vol_'+this.config.pool_id+'_'+new_id, header_text, err => (err ? no(new Error(err)) : ok(null)), cas_old => !cas_old
-        ));
-        return new_vol;
-    }
-
-    toObjectGetInfo(objectKey, bucketName, storageLocation)
-    {
-        return null;
-    }
-
-    _bufferStart(vol, cur_pos, cur_size, cur_chunks, sector_refs)
-    {
-        if ((cur_pos % this.config.sector_size) ||
-            Math.floor((cur_pos + cur_size) / this.config.sector_size) == Math.floor(cur_pos / this.config.sector_size))
-        {
-            const sect_pos = Math.floor(cur_pos / this.config.sector_size) * this.config.sector_size;
-            const sect = vol.partial_sectors[sect_pos]
-                ? vol.partial_sectors[sect_pos].buffer
-                : Buffer.alloc(this.config.sector_size);
-            if (this.config.pack_objects)
-            {
-                // Save only if <pack_objects>
-                if (!vol.partial_sectors[sect_pos])
-                    vol.partial_sectors[sect_pos] = { buffer: sect, refs: 0 };
-                vol.partial_sectors[sect_pos].refs++;
-                sector_refs.push(sect_pos);
-            }
-            let off = cur_pos % this.config.sector_size;
-            let i = 0;
-            for (; i < cur_chunks.length; i++)
-            {
-                let copy_len = this.config.sector_size - off;
-                copy_len = copy_len > cur_chunks[i].length ? cur_chunks[i].length : copy_len;
-                cur_chunks[i].copy(sect, off, 0, copy_len);
-                off += copy_len;
-                if (copy_len < cur_chunks[i].length)
-                {
-                    cur_chunks[i] = cur_chunks[i].slice(copy_len);
-                    cur_size -= copy_len;
-                    break;
-                }
-                else
-                    cur_size -= cur_chunks[i].length;
-            }
-            cur_chunks.splice(0, i, sect);
-            cur_size += this.config.sector_size;
-            cur_pos = sect_pos;
-        }
-        return [ cur_pos, cur_size ];
-    }
-
-    _bufferEnd(vol, cur_pos, cur_size, cur_chunks, sector_refs, write_all)
-    {
-        const write_pos = cur_pos;
-        const write_chunks = cur_chunks;
-        let write_size = cur_size;
-        cur_chunks = [];
-        cur_pos += cur_size;
-        cur_size = 0;
-        let remain = (cur_pos % this.config.sector_size);
-        if (remain > 0)
-        {
-            cur_pos -= remain;
-            let last_sect = null;
-            if (write_all)
-            {
-                last_sect = vol.partial_sectors[cur_pos]
-                    ? vol.partial_sectors[cur_pos].buffer
-                    : Buffer.alloc(this.config.sector_size);
-                if (this.config.pack_objects)
-                {
-                    // Save only if <pack_objects>
-                    if (!vol.partial_sectors[cur_pos])
-                        vol.partial_sectors[cur_pos] = { buffer: last_sect, refs: 0 };
-                    vol.partial_sectors[cur_pos].refs++;
-                    sector_refs.push(cur_pos);
-                }
-            }
-            write_size -= remain;
-            if (write_size < 0)
-                write_size = 0;
-            for (let i = write_chunks.length-1; i >= 0 && remain > 0; i--)
-            {
-                if (write_chunks[i].length <= remain)
-                {
-                    remain -= write_chunks[i].length;
-                    if (write_all)
-                        write_chunks[i].copy(last_sect, remain);
-                    else
-                        cur_chunks.unshift(write_chunks[i]);
-                    write_chunks.pop();
-                }
-                else
-                {
-                    if (write_all)
-                        write_chunks[i].copy(last_sect, 0, write_chunks[i].length - remain);
-                    else
-                        cur_chunks.unshift(write_chunks[i].slice(write_chunks[i].length - remain));
-                    write_chunks[i] = write_chunks[i].slice(0, write_chunks[i].length - remain);
-                    remain = 0;
-                    i++;
-                }
-            }
-            if (write_all)
-            {
-                write_chunks.push(last_sect);
-                write_size += this.config.sector_size;
-            }
-        }
-        for (const chunk of cur_chunks)
-        {
-            cur_size += chunk.length;
-        }
-        return [ write_pos, write_chunks, write_size, cur_pos, cur_size, cur_chunks ];
-    }
-
-    /**
-     * reqUids: string, // request-ids for log, usually joined by ':'
-     * keyContext: {
-     *     // a lot of shit, basically all metadata
-     *     bucketName,
-     *     objectKey,
-     *     owner?,
-     *     namespace?,
-     *     partNumber?,
-     *     uploadId?,
-     *     metaHeaders?,
-     *     isDeleteMarker?,
-     *     tagging?,
-     *     contentType?,
-     *     cacheControl?,
-     *     contentDisposition?,
-     *     contentEncoding?,
-     * },
-     * callback: (error, objectGetInfo: any) => void,
-     */
-    put(stream, size, keyContext, reqUids, callback)
-    {
-        callback = once(callback);
-        this._getVolume(keyContext.bucketName, size)
-            .then(vol => this._put(vol, stream, size, keyContext, reqUids, callback))
-            .catch(callback);
-    }
-
-    _put(vol, stream, size, keyContext, reqUids, callback)
-    {
-        const object_header: ObjectHeader = {
-            size,
-            key: keyContext.objectKey,
-        };
-        if (keyContext.partNumber)
-        {
-            object_header.part_num = keyContext.partNumber;
-        }
-        // header is: <8 bytes magic> <8 bytes flags> <8 bytes json length> <json>
-        const hdr_begin_buf = Buffer.alloc(24);
-        const hdr_json_buf = Buffer.from(JSON.stringify(object_header), 'utf-8');
-        hdr_begin_buf.write(OBJECT_MAGIC);
-        hdr_begin_buf.writeBigInt64LE(BigInt(hdr_json_buf.length), 16);
-        const object_header_buf = Buffer.concat([ hdr_begin_buf, hdr_json_buf ]);
-        const object_pos = vol.header.size;
-        const object_get_info = { volume: vol.id, offset: object_pos, hdrlen: object_header_buf.length, size };
-        let cur_pos = object_pos;
-        let cur_chunks = [ object_header_buf ];
-        let cur_size = object_header_buf.length;
-        let err: Error|null = null;
-        let waiting = 1; // 1 for end or error, 1 for each write request
-        vol.header.size += object_header_buf.length + size;
-        if (!this.config.pack_objects && (vol.header.size % this.config.sector_size))
-        {
-            vol.header.size += this.config.sector_size - (vol.header.size % this.config.sector_size);
-        }
-        const writeChunk = (last) =>
-        {
-            const sector_refs = [];
-            // Handle partial beginning
-            [ cur_pos, cur_size ] = this._bufferStart(vol, cur_pos, cur_size, cur_chunks, sector_refs);
-            // Handle partial end
-            let write_pos, write_chunks, write_size;
-            [ write_pos, write_chunks, write_size, cur_pos, cur_size, cur_chunks ] = this._bufferEnd(vol, cur_pos, cur_size, cur_chunks, sector_refs, last);
-            waiting++;
-            // FIXME: pool_id: maybe it should be stored in volume metadata to allow to migrate volumes?
-            this.cli.write(this.config.pool_id, vol.id, write_pos, write_chunks, (res) =>
-            {
-                for (const sect of sector_refs)
-                {
-                    vol.partial_sectors[sect].refs--;
-                    if (!vol.partial_sectors[sect].refs &&
-                        vol.header.size >= sect+this.config.sector_size)
-                    {
-                        // Forget partial data when it's not needed anymore
-                        delete(vol.partial_sectors[sect]);
-                    }
-                }
-                waiting--;
-                if (res)
-                {
-                    err = new Error(res);
-                    waiting--;
-                }
-                if (!waiting)
-                {
-                    callback(err, err ? null : object_get_info);
-                }
-            });
-        };
-        // Stream data
-        stream.on('error', (e) =>
-        {
-            err = e;
-            waiting--;
-            if (!waiting)
-            {
-                callback(err, null);
-            }
-        });
-        stream.on('end', () =>
-        {
-            if (err)
-            {
-                return;
-            }
-            waiting--;
-            if (cur_size)
-            {
-                // write last chunk
-                writeChunk(true);
-            }
-            if (!waiting)
-            {
-                callback(null, object_get_info);
-            }
-        });
-        stream.on('data', (chunk) =>
-        {
-            if (err)
-            {
-                return;
-            }
-            cur_chunks.push(chunk);
-            cur_size += chunk.length;
-            if (cur_size >= this.config.write_chunk_size)
-            {
-                // got a complete chunk, write it out
-                writeChunk(false);
-            }
-        });
-    }
-
-    /**
-     * objectGetInfo: {
-     *   key: { volume, offset, hdrlen, size }, // from put
-     *   size,
-     *   start,
-     *   dataStoreName,
-     *   dataStoreETag,
-     *   range,
-     *   response: ServerResponse,
-     * },
-     * range?: [ start, end ], // like in HTTP - first byte index, last byte index
-     * callback: (error, readStream) => void,
-     */
-    get(objectGetInfo, range, reqUids, callback)
-    {
-        if (!(objectGetInfo instanceof Object) || !objectGetInfo.key ||
-            !(objectGetInfo.key instanceof Object) || !objectGetInfo.key.volume ||
-            !objectGetInfo.key.offset || !objectGetInfo.key.hdrlen || !objectGetInfo.key.size)
-        {
-            throw new Error('objectGetInfo must be { key: { volume, offset, hdrlen, size } }, but is '+JSON.stringify(objectGetInfo));
-        }
-        const [ start, end ] = range || [];
-        if (start < 0 || end < 0 || end != null && start != null && end < start || start >= objectGetInfo.key.size)
-        {
-            throw new Error('Invalid range: '+start+'-'+end);
-        }
-        let offset = objectGetInfo.key.offset + objectGetInfo.key.hdrlen + (start || 0);
-        let len = objectGetInfo.key.size - (start || 0);
-        if (end)
-        {
-            const len2 = end - (start || 0) + 1;
-            if (len2 < len)
-                len = len2;
-        }
-        callback(null, new VitastorReadStream(this.cli, objectGetInfo.key.volume, offset, len, this.config));
-    }
-
-    /**
-     * objectGetInfo: {
-     *   key: { volume, offset, hdrlen, size }, // from put
-     *   size,
-     *   start,
-     *   dataStoreName,
-     *   dataStoreETag,
-     *   range,
-     *   response: ServerResponse,
-     * },
-     * callback: (error) => void,
-     */
-    delete(objectGetInfo, reqUids, callback)
-    {
-        callback = once(callback);
-        this._delete(objectGetInfo, reqUids)
-            .then(callback)
-            .catch(callback);
-    }
-
-    async _delete(objectGetInfo, reqUids)
-    {
-        if (!(objectGetInfo instanceof Object) || !objectGetInfo.key ||
-            !(objectGetInfo.key instanceof Object) || !objectGetInfo.key.volume ||
-            !objectGetInfo.key.offset || !objectGetInfo.key.hdrlen || !objectGetInfo.key.size)
-        {
-            throw new Error('objectGetInfo must be { key: { volume, offset, hdrlen, size } }, but is '+JSON.stringify(objectGetInfo));
-        }
-        const in_sect_pos = (objectGetInfo.key.offset % this.config.sector_size);
-        const sect_pos = objectGetInfo.key.offset - in_sect_pos;
-        const vol = this.volumes_by_id[objectGetInfo.key.volume];
-        if (vol && vol.partial_sectors[sect_pos])
-        {
-            // The sector may still be written to in corner cases
-            const sect = vol.partial_sectors[sect_pos];
-            const flags = sect.buffer.readBigInt64LE(in_sect_pos + 8);
-            if (!(flags & FLAG_DELETED))
-            {
-                const del_stat = this.volume_delete_stats[vol.id] = (this.volume_delete_stats[vol.id] || { count: 0, bytes: 0 });
-                del_stat.count++;
-                del_stat.bytes += objectGetInfo.key.size;
-                sect.buffer.writeBigInt64LE(flags | FLAG_DELETED, in_sect_pos + 8);
-                sect.refs++;
-                const err = await new Promise<any>(ok => this.cli.write(this.config.pool_id, objectGetInfo.key.volume, sect_pos, sect.buffer, ok));
-                sect.refs--;
-                if (err)
-                {
-                    sect.buffer.writeBigInt64LE(0n, in_sect_pos + 8);
-                    throw new Error(err);
-                }
-            }
-        }
-        else
-        {
-            // RMW with CAS
-            const [ err, buf, version ] = await new Promise<[ any, Buffer, bigint ]>(ok => this.cli.read(
-                this.config.pool_id, objectGetInfo.key.volume, sect_pos, this.config.sector_size,
-                (err, buf, version) => ok([ err, buf, version ])
-            ));
-            if (err)
-            {
-                throw new Error(err);
-            }
-            // FIXME What if JSON crosses sector boundary? Prevent it if we want to pack objects
-            const magic = buf.slice(in_sect_pos, in_sect_pos+8).toString();
-            const flags = buf.readBigInt64LE(in_sect_pos+8);
-            const json_len = Number(buf.readBigInt64LE(in_sect_pos+16));
-            let json_hdr;
-            if (in_sect_pos+24+json_len <= buf.length)
-            {
-                try
-                {
-                    json_hdr = JSON.parse(buf.slice(in_sect_pos+24, in_sect_pos+24+json_len).toString());
-                }
-                catch (e)
-                {
-                }
-            }
-            if (magic !== OBJECT_MAGIC || !json_hdr || json_hdr.size !== objectGetInfo.key.size)
-            {
-                throw new Error(
-                    'header of object with size '+objectGetInfo.key.size+
-                    ' bytes not found in volume '+objectGetInfo.key.volume+' at '+objectGetInfo.key.offset
-                );
-            }
-            else if (!(flags & FLAG_DELETED))
-            {
-                buf.writeBigInt64LE(flags | FLAG_DELETED, in_sect_pos + 8);
-                const err = await new Promise<any>(ok => this.cli.write(this.config.pool_id, objectGetInfo.key.volume, sect_pos, buf, { version: version+1n }, ok));
-                if (err == vitastor.EINTR)
-                {
-                    // Retry
-                    await this._delete(objectGetInfo, reqUids);
-                }
-                else if (err)
-                {
-                    throw new Error(err);
-                }
-                else
-                {
-                    // FIXME: Write deletion statistics to volumes
-                    // FIXME: Implement defragmentation
-                    const del_stat = this.volume_delete_stats[objectGetInfo.key.volume] = (this.volume_delete_stats[objectGetInfo.key.volume] || { count: 0, bytes: 0 });
-                    del_stat.count++;
-                    del_stat.bytes += objectGetInfo.key.size;
-                }
-            }
-        }
-    }
-
-    /**
-     * config: full zenko server config,
-     * callback: (error, stats) => void, // stats is the returned statistics in arbitrary format
-     */
-    getDiskUsage(config, reqUids, callback)
-    {
-        // FIXME: Iterate all volumes and return its sizes and deletion statistics, or maybe just sizes
-        callback(null, {});
-    }
-}
-
-class VitastorReadStream extends stream.Readable
-{
-    constructor(cli, volume_id, offset, len, config, options = undefined)
-    {
-        super(options);
-        this.cli = cli;
-        this.volume_id = volume_id;
-        this.offset = offset;
-        this.end = offset + len;
-        this.pos = offset;
-        this.config = config;
-        this._reading = false;
-    }
-
-    _read(n)
-    {
-        if (this._reading)
-        {
-            return;
-        }
-        // FIXME: Validate object header
-        const chunk_size = n && this.config.read_chunk_size < n ? n : this.config.read_chunk_size;
-        const read_offset = this.pos;
-        const round_offset = read_offset - (read_offset % this.config.sector_size);
-        let read_end = this.end <= read_offset+chunk_size ? this.end : read_offset+chunk_size;
-        const round_end = (read_end % this.config.sector_size)
-            ? read_end + this.config.sector_size - (read_end % this.config.sector_size)
-            : read_end;
-        if (round_end <= this.end)
-            read_end = round_end;
-        this.pos = read_end;
-        if (read_end <= read_offset)
-        {
-            // EOF
-            this.push(null);
-            return;
-        }
-        this._reading = true;
-        this.cli.read(this.config.pool_id, this.volume_id, round_offset, round_end-round_offset, (err, buf, version) =>
-        {
-            this._reading = false;
-            if (err)
-            {
-                this.destroy(new Error(err));
-                return;
-            }
-            if (read_offset != round_offset || round_end != read_end)
-            {
-                buf = buf.subarray(read_offset-round_offset, buf.length-(round_end-read_end));
-            }
-            if (this.push(buf))
-            {
-                this._read(n);
-            }
-        });
-    }
-}
-
-function once(callback)
-{
-    let called = false;
-    return function()
-    {
-        if (!called)
-        {
-            called = true;
-            callback.apply(null, arguments);
-        }
-    };
-}
-
-module.exports = VitastorBackend;

lib/storage/metadata/MetadataWrapper.js

@@ -226,19 +226,6 @@ class MetadataWrapper {
         });
     }
 
-    getBucketQuota(bucketName, log, cb) {
-        log.debug('getting bucket quota from metadata');
-        this.client.getBucketAttributes(bucketName, log, (err, data) => {
-            if (err) {
-                log.debug('error from metadata', { implName: this.implName,
-                    error: err });
-                return cb(err);
-            }
-            const bucketInfo = BucketInfo.fromObj(data);
-            return cb(err, { quota: bucketInfo.getQuota() });
-        });
-    }
-
     deleteBucket(bucketName, log, cb) {
         log.debug('deleting bucket from metadata');
         this.client.deleteBucket(bucketName, log, err => {

lib/storage/metadata/mongoclient/MongoClientInterface.js

@@ -899,130 +899,35 @@ class MongoClientInterface {
             return cb(errors.InternalError);
         });
     }
+
     /**
-     * Puts an object into a MongoDB collection.
+     * Put object when versioning is not enabled
-     * Depending on the parameters, the object is either directly put into the collection
+     * @param {Object} c bucket collection
-     * or the existing object is marked as deleted and a new object is inserted.
+     * @param {String} bucketName bucket name
-     *
+     * @param {String} objName object name
-     * @param {Object} collection - The MongoDB collection to put the object into.
+     * @param {Object} objVal object metadata
-     * @param {string} bucketName - The name of the bucket the object belongs to.
+     * @param {Object} params params
-     * @param {string} objName - The name of the object.
+     * @param {Object} log logger
-     * @param {Object} value - The value of the object.
+     * @param {Function} cb callback
-     * @param {Object} params - Additional parameters.
+     * @return {undefined}
-     * @param {string} params.vFormat - object key format.
-     * @param {boolean} params.needOplogUpdate - If true, the object is directly put into the collection
-     * with updating the operation log.
-     * @param {Object} log - The logger to use.
-     * @param {Function} cb - The callback function to call when the operation is complete. It is called with an error
-     * if there is an issue with the operation.
-     * @returns {Promise} A promise that resolves when the operation is complete. The promise is rejected with an error
-     * if there is an issue with the operation.
      */
-    putObjectNoVer(collection, bucketName, objName, value, params, log, cb) {
+    putObjectNoVer(c, bucketName, objName, objVal, params, log, cb) {
-        if (params?.needOplogUpdate) {
+        const masterKey = formatMasterKey(objName, params.vFormat);
-            return this.putObjectNoVerWithOplogUpdate(collection, bucketName, objName, value, params, log, cb);
+        c.updateOne({
-        }
+            _id: masterKey,
-        const key = formatMasterKey(objName, params.vFormat);
+        }, {
-        const putFilter = { _id: key };
-        return collection.updateOne(putFilter, {
             $set: {
-                _id: key,
+                _id: masterKey,
-                value,
+                value: objVal,
             },
         }, {
             upsert: true,
-        }).then(() => cb()).catch(err => {
+        }).then(() => cb()).catch((err) => {
             log.error('putObjectNoVer: error putting obect with no versioning', { error: err.message });
             return cb(errors.InternalError);
         });
     }
 
-    /**
-     * Updates an object in a MongoDB collection without changing its version.
-     * If the object doesn't exist, it will be created (upsert is true for the second update operation).
-     * The operation is logged in the oplog.
-     *
-     * @param {Object} collection - The MongoDB collection to update the object in.
-     * @param {string} bucketName - The name of the bucket the object belongs to.
-     * @param {string} objName - The name of the object.
-     * @param {Object} value - The new value of the object.
-     * @param {Object} params - Additional parameters.
-     * @param {string} params.vFormat - object key format
-     * @param {string} params.originOp - origin operation
-     * @param {Object} log - The logger to use.
-     * @param {Function} cb - The callback function to call when the operation is complete.
-     * It is called with an error if there is an issue with the operation.
-     * @returns {void}
-     */
-    putObjectNoVerWithOplogUpdate(collection, bucketName, objName, value, params, log, cb) {
-        const key = formatMasterKey(objName, params.vFormat);
-        const putFilter = { _id: key };
-        // filter used when finding and updating object
-        const findFilter = {
-            ...putFilter,
-            $or: [
-                { 'value.deleted': { $exists: false } },
-                { 'value.deleted': { $eq: false } },
-            ],
-        };
-        const updateDeleteFilter = {
-            ...putFilter,
-            'value.deleted': true,
-        };
-        return async.waterfall([
-            // Adding delete flag when getting the object
-            // to avoid having race conditions.
-            next => collection.findOneAndUpdate(findFilter, {
-                $set: updateDeleteFilter,
-            }, {
-                upsert: false,
-            }).then(doc => {
-                if (!doc.value) {
-                    log.error('internalPutObject: unable to find target object to update',
-                        { bucket: bucketName, object: key });
-                    return next(errors.NoSuchKey);
-                }
-                const obj = doc.value;
-                const objMetadata = new ObjectMD(obj.value);
-                objMetadata.setOriginOp(params.originOp);
-                objMetadata.setDeleted(true);
-                return next(null, objMetadata.getValue());
-            }).catch(err => {
-                log.error('internalPutObject: error getting object',
-                    { bucket: bucketName, object: key, error: err.message });
-                return next(errors.InternalError);
-            }),
-            // We update the full object to get the whole object metadata
-            // in the oplog update event
-            (objMetadata, next) => collection.bulkWrite([
-                {
-                    updateOne: {
-                        filter: updateDeleteFilter,
-                        update: {
-                            $set: { _id: key, value: objMetadata },
-                        },
-                        upsert: false,
-                    },
-                },
-                {
-                    updateOne: {
-                        filter: putFilter,
-                        update: {
-                            $set: { _id: key, value },
-                        },
-                        upsert: true,
-                    },
-                },
-            ], { ordered: true }).then(() => next(null)).catch(next),
-        ], (err) => {
-            if (err) {
-                log.error('internalPutObject: error updating object',
-                    { bucket: bucketName, object: key, error: err.message });
-                return cb(errors.InternalError);
-            }
-            return cb();
-        });
-    }
     /**
      * Returns the putObjectVerCase function to use
      * depending on params
@@ -1068,7 +973,8 @@ class MongoClientInterface {
                 return putObjectVer(c, bucketName, objName, objVal, _params, log,
                     cb);
             }
-            return this.putObjectNoVer(c, bucketName, objName, objVal, _params, log, cb);
+            return this.putObjectNoVer(c, bucketName, objName, objVal,
+                _params, log, cb);
         });
     }
 
@@ -2150,20 +2056,14 @@ class MongoClientInterface {
                 return cb(err);
             }
             const { bucketCount, bucketInfos } = res;
-            let bucketWithQuotaCount = 0;
 
-            const retBucketInfos = bucketInfos.map(bucket => {
+            const retBucketInfos = bucketInfos.map(bucket => ({
-                if (bucket.getQuota()) {
+                name: bucket.getName(),
-                    bucketWithQuotaCount++;
+                location: bucket.getLocationConstraint(),
-                }
+                isVersioned: !!bucket.getVersioningConfiguration(),
-                return {
+                ownerCanonicalId: bucket.getOwner(),
-                    name: bucket.getName(),
+                ingestion: bucket.isIngestionBucket(),
-                    location: bucket.getLocationConstraint(),
+            }));
-                    isVersioned: !!bucket.getVersioningConfiguration(),
-                    ownerCanonicalId: bucket.getOwner(),
-                    ingestion: bucket.isIngestionBucket(),
-                };
-            });
 
             return this.readCountItems(log, (err, results) => {
                 if (err) {
@@ -2173,7 +2073,6 @@ class MongoClientInterface {
                 /* eslint-disable */
                 results.bucketList = retBucketInfos;
                 results.buckets = bucketCount;
-                results.bucketWithQuotaCount = bucketWithQuotaCount;
                 /* eslint-enable */
                 return cb(null, results);
             });

lib/storage/utils.js

@@ -10,21 +10,21 @@ function trySetDirSyncFlag(path) {
 
     const GETFLAGS = 2148034049;
     const SETFLAGS = 1074292226;
-    const FS_DIRSYNC_FL = 65536n;
+    const FS_DIRSYNC_FL = 65536;
     const buffer = Buffer.alloc(8, 0);
     const pathFD = fs.openSync(path, 'r');
     const status = ioctl(pathFD, GETFLAGS, buffer);
     assert.strictEqual(status, 0);
-    const currentFlags = buffer.readBigInt64LE(0);
+    const currentFlags = buffer.readUIntLE(0, 8);
     const flags = currentFlags | FS_DIRSYNC_FL;
-    buffer.writeBigInt64LE(flags, 0);
+    buffer.writeUIntLE(flags, 0, 8);
     const status2 = ioctl(pathFD, SETFLAGS, buffer);
     assert.strictEqual(status2, 0);
     fs.closeSync(pathFD);
     const pathFD2 = fs.openSync(path, 'r');
     const confirmBuffer = Buffer.alloc(8, 0);
     ioctl(pathFD2, GETFLAGS, confirmBuffer);
-    assert.strictEqual(confirmBuffer.readBigInt64LE(0),
+    assert.strictEqual(confirmBuffer.readUIntLE(0, 8),
         currentFlags | FS_DIRSYNC_FL, 'FS_DIRSYNC_FL not set');
     fs.closeSync(pathFD2);
 }

lib/versioning/Version.ts

@@ -3,7 +3,7 @@ import { VersioningConstants } from './constants';
 const VID_SEP = VersioningConstants.VersionId.Separator;
 /**
  * Class for manipulating an object version.
- * The format of a version: { isNull, isNull2, isDeleteMarker, versionId, otherInfo }
+ * The format of a version: { isNull, isDeleteMarker, versionId, otherInfo }
  *
  * @note Some of these functions are optimized based on string search
  * prior to a full JSON parse/stringify. (Vinh: 18K op/s are achieved
@@ -13,31 +13,24 @@ const VID_SEP = VersioningConstants.VersionId.Separator;
 export class Version {
     version: {
         isNull?: boolean;
-        isNull2?: boolean;
         isDeleteMarker?: boolean;
         versionId?: string;
         isPHD?: boolean;
-        nullVersionId?: string;
     };
 
     /**
      * Create a new version instantiation from its data object.
      * @param version - the data object to instantiate
      * @param version.isNull - is a null version
-     * @param version.isNull2 - Whether new version is null or not AND has
-     * been put with a Cloudserver handling null keys (i.e. supporting
-     * S3C-7352)
      * @param version.isDeleteMarker - is a delete marker
      * @param version.versionId - the version id
      * @constructor
      */
     constructor(version?: {
         isNull?: boolean;
-        isNull2?: boolean;
         isDeleteMarker?: boolean;
         versionId?: string;
         isPHD?: boolean;
-        nullVersionId?: string;
     }) {
         this.version = version || {};
     }
@@ -90,33 +83,6 @@ export class Version {
         return `{ "isPHD": true, "versionId": "${versionId}" }`;
     }
 
-    /**
-     * Appends a key-value pair to a JSON object represented as a string. It adds
-     * a comma if the object is not empty (i.e., not just '{}'). It assumes the input
-     * string is formatted as a JSON object.
-     *
-     * @param {string} stringifiedObject The JSON object as a string to which the key-value pair will be appended.
-     * @param {string} key The key to append to the JSON object.
-     * @param {string} value The value associated with the key to append to the JSON object.
-     * @returns {string} The updated JSON object as a string with the new key-value pair appended.
-     * @example
-     * _jsonAppend('{"existingKey":"existingValue"}', 'newKey', 'newValue');
-     * // returns '{"existingKey":"existingValue","newKey":"newValue"}'
-     */
-    static _jsonAppend(stringifiedObject: string, key: string, value: string): string {
-        // stringifiedObject value has the format of '{...}'
-        let index = stringifiedObject.length - 2;
-        while (stringifiedObject.charAt(index) === ' ') {
-            index -= 1;
-        }
-        const needComma = stringifiedObject.charAt(index) !== '{';
-        return (
-            `${stringifiedObject.slice(0, stringifiedObject.length - 1)}` +
-            (needComma ? ',' : '') +
-            `"${key}":"${value}"}`
-        );
-    }
-
     /**
      * Put versionId into an object in the (cheap) way of string manipulation,
      * instead of the more expensive alternative parsing and stringification.
@@ -127,32 +93,14 @@ export class Version {
      */
     static appendVersionId(value: string, versionId: string): string {
         // assuming value has the format of '{...}'
-        return Version._jsonAppend(value, 'versionId', versionId);
+        let index = value.length - 2;
-    }
+        while (value.charAt(index--) === ' ');
-
+        const comma = value.charAt(index + 1) !== '{';
-    /**
+        return (
-    * Updates or appends a `nullVersionId` property to a JSON-formatted string.
+            `${value.slice(0, value.length - 1)}` + // eslint-disable-line
-    * This function first checks if the `nullVersionId` property already exists within the input string.
+            (comma ? ',' : '') +
-    * If it exists, the function updates the `nullVersionId` with the new value provided.
+            `"versionId":"${versionId}"}`
-    * If it does not exist, the function appends a `nullVersionId` property with the provided value.
+        );
-    *
-    * @static
-    * @param {string} value - The JSON-formatted string that may already contain a `nullVersionId` property.
-    * @param {string} nullVersionId - The new value for the `nullVersionId` property to be updated or appended.
-    * @returns {string} The updated JSON-formatted string with the new `nullVersionId` value.
-    */
-    static updateOrAppendNullVersionId(value: string, nullVersionId: string): string {
-        // Check if "nullVersionId" already exists in the string
-        const nullVersionIdPattern = /"nullVersionId":"[^"]*"/;
-        const nullVersionIdExists = nullVersionIdPattern.test(value);
-    
-        if (nullVersionIdExists) {
-            // Replace the existing nullVersionId with the new one
-            return value.replace(nullVersionIdPattern, `"nullVersionId":"${nullVersionId}"`);
-        } else {
-            // Append nullVersionId
-            return Version._jsonAppend(value, 'nullVersionId', nullVersionId);
-        }
     }
 
     /**
@@ -173,19 +121,6 @@ export class Version {
         return this.version.isNull ?? false;
     }
 
-    /**
-     * Check if a version is a null version and has
-     * been put with a Cloudserver handling null keys (i.e. supporting
-     * S3C-7352).
-     *
-     * @return - stating if the value is a null version and has
-     * been put with a Cloudserver handling null keys (i.e. supporting
-     * S3C-7352).
-     */
-    isNull2Version(): boolean {
-        return this.version.isNull2 ?? false;
-    }
-
     /**
      * Check if a stringified object is a delete marker.
      *
@@ -255,19 +190,6 @@ export class Version {
         return this;
     }
 
-    /**
-     * Mark that the null version has been put with a Cloudserver handling null keys (i.e. supporting S3C-7352)
-     * 
-     * If `isNull2` is set, `isNull` is also set to maintain consistency.
-     * Explicitly setting both avoids misunderstandings and mistakes in future updates or fixes.
-     * @return - the updated version
-     */
-    setNull2Version() {
-        this.version.isNull2 = true;
-        this.version.isNull = true;
-        return this;
-    }
-
     /**
      * Serialize the version.
      *

lib/versioning/VersioningRequestProcessor.ts

@@ -1,8 +1,6 @@
-import { RequestLogger } from 'werelogs';
-
 import errors, { ArsenalError } from '../errors';
 import { Version } from './Version';
-import { generateVersionId as genVID, getInfVid } from './VersionID';
+import { generateVersionId as genVID } from './VersionID';
 import WriteCache from './WriteCache';
 import WriteGatheringManager from './WriteGatheringManager';
 
@@ -483,113 +481,19 @@ export default class VersioningRequestProcessor {
             const versionId = request.options.versionId;
             const versionKey = formatVersionKey(key, versionId);
             const ops: any = [];
-            const masterVersion = data !== undefined &&
+            if (!request.options.isNull) {
-                  Version.from(data);
+                ops.push({ key: versionKey, value: request.value });
-            // push a version key if we're not updating the null
-            // version (or in legacy Cloudservers not sending the
-            // 'isNull' parameter, but this has an issue, see S3C-7526)
-            if (request.options.isNull !== true) {
-                const versionOp = { key: versionKey, value: request.value };
-                ops.push(versionOp);
             }
-            if (masterVersion) {
+            if (data === undefined ||
-                // master key exists
+                (Version.from(data).getVersionId() ?? '') >= versionId) {
-                // note that older versions have a greater version ID
+                // master does not exist or is not newer than put
-                const versionIdFromMaster = masterVersion.getVersionId();
+                // version and needs to be updated as well.
-                if (versionIdFromMaster === undefined ||
+                // Note that older versions have a greater version ID.
-                    versionIdFromMaster >= versionId) {
+                ops.push({ key: request.key, value: request.value });
-                    let value = request.value;
+            } else if (request.options.isNull) {
-                    logger.debug('version to put is not older than master');
+                logger.debug('create or update null key');
-                    // Delete the deprecated, null key for backward compatibility
+                const nullKey = formatVersionKey(key, '');
-                    // to avoid storing both deprecated and new null keys.
+                ops.push({ key: nullKey, value: request.value });
-                    // If master null version was put with an older Cloudserver (or in compat mode),
-                    // there is a possibility that it also has a null versioned key
-                    // associated, so we need to delete it as we write the null key.
-                    // Deprecated null key gets deleted when the new CloudServer:
-                    // - updates metadata of a null master (options.isNull=true)
-                    // - puts metadata on top of a master null key (options.isNull=false)
-                    if (request.options.isNull !== undefined && // new null key behavior when isNull is defined.
-                        masterVersion.isNullVersion() && // master is null
-                        !masterVersion.isNull2Version()) { // master does not support the new null key behavior yet.
-                        const masterNullVersionId = masterVersion.getVersionId();
-                        // The deprecated null key is referenced in the "versionId" property of the master key.
-                        if (masterNullVersionId) {
-                            const oldNullVersionKey = formatVersionKey(key, masterNullVersionId);
-                            ops.push({ key: oldNullVersionKey, type: 'del' });
-                        }
-                    }
-                    // new behavior when isNull is defined is to only
-                    // update the master key if it is the latest
-                    // version, old behavior needs to copy master to
-                    // the null version because older Cloudservers
-                    // rely on version-specific PUT to copy master
-                    // contents to a new null version key (newer ones
-                    // use special versionId="null" requests for this
-                    // purpose).
-                    if (versionIdFromMaster !== versionId ||
-                        request.options.isNull === undefined) {
-                        // master key is strictly older than the put version
-                        let masterVersionId;
-                        if (masterVersion.isNullVersion() && versionIdFromMaster) {
-                            logger.debug('master key is a null version');
-                            masterVersionId = versionIdFromMaster;
-                        } else if (versionIdFromMaster === undefined) {
-                            logger.debug('master key is nonversioned');
-                            // master key does not have a versionID
-                            // => create one with the "infinite" version ID
-                            masterVersionId = getInfVid(this.replicationGroupId);
-                            masterVersion.setVersionId(masterVersionId);
-                        } else {
-                            logger.debug('master key is a regular version');
-                        }
-                        if (request.options.isNull === true) {
-                            if (!masterVersionId) {
-                                // master is a regular version: delete the null key that
-                                // may exist (older null version)
-                                logger.debug('delete null key');
-                                const nullKey = formatVersionKey(key, '');
-                                ops.push({ key: nullKey, type: 'del' });
-                            }
-                        } else if (masterVersionId) {
-                            logger.debug('create version key from master version');
-                            // isNull === false means Cloudserver supports null keys,
-                            // so create a null key in this case, and a version key otherwise
-                            const masterKeyVersionId = request.options.isNull === false ?
-                                  '' : masterVersionId;
-                            const masterVersionKey = formatVersionKey(key, masterKeyVersionId);
-                            masterVersion.setNullVersion();
-                            // isNull === false means Cloudserver supports null keys,
-                            // so create a null key with the isNull2 flag
-                            if (request.options.isNull === false) {
-                                masterVersion.setNull2Version();
-                            // else isNull === undefined means Cloudserver does not support null keys,
-                            // and versionIdFromMaster !== versionId means that a version is PUT on top of a null version
-                            // hence set/update the new master nullVersionId for backward compatibility
-                            } else if (versionIdFromMaster !== versionId) {
-                                // => set the nullVersionId to the master version if put version on top of null version.
-                                value = Version.updateOrAppendNullVersionId(request.value, masterVersionId);
-                            }
-                            ops.push({ key: masterVersionKey,
-                                       value: masterVersion.toString() });
-                        }
-                    } else {
-                        logger.debug('version to put is the master');
-                    }
-                    ops.push({ key, value: value });
-                } else {
-                    logger.debug('version to put is older than master');
-                    if (request.options.isNull === true && !masterVersion.isNullVersion()) {
-                        logger.debug('create or update null key');
-                        const nullKey = formatVersionKey(key, '');
-                        const nullKeyOp = { key: nullKey, value: request.value };
-                        ops.push(nullKeyOp);
-                        // for backward compatibility: remove null version key
-                        ops.push({ key: versionKey, type: 'del' });
-                    }
-                }
-            } else {
-                // master key does not exist: create it
-                ops.push({ key, value: request.value });
             }
             return callback(null, ops, versionId);
         });

lib/versioning/WriteCache.ts

@@ -1,5 +1,3 @@
-import { RequestLogger } from 'werelogs';
-
 import errors, { ArsenalError } from '../errors';
 import WriteGatheringManager from './WriteGatheringManager';
 

lib/versioning/WriteGatheringManager.ts

@@ -1,5 +1,3 @@
-import { RequestLogger } from 'werelogs';
-
 import { ArsenalError } from '../errors';
 
 const WG_TIMEOUT = 5; // batching period in milliseconds

package.json

@@ -3,7 +3,7 @@
   "engines": {
     "node": ">=16"
   },
-  "version": "8.1.134",
+  "version": "8.1.121",
   "description": "Common utilities for the S3 project components",
   "main": "build/index.js",
   "repository": {
@@ -19,38 +19,39 @@
   "dependencies": {
     "@azure/identity": "^3.1.1",
     "@azure/storage-blob": "^12.12.0",
-    "@js-sdsl/ordered-set": "^4.4.2",
+    "@types/async": "^3.2.12",
-    "@swc/cli": "^0.4.0",
+    "@types/utf8": "^3.0.1",
-    "@swc/core": "^1.7.4",
+    "JSONStream": "^1.0.0",
     "agentkeepalive": "^4.1.3",
-    "ajv": "^6.12.3",
+    "ajv": "6.12.3",
-    "async": "^2.6.4",
+    "async": "~2.6.4",
     "aws-sdk": "^2.1005.0",
     "backo": "^1.1.0",
-    "base-x": "^3.0.8",
+    "base-x": "3.0.8",
-    "base62": "^2.0.1",
+    "base62": "2.0.1",
-    "bson": "^4.0.0",
+    "bson": "4.0.0",
-    "debug": "^4.1.0",
+    "debug": "~4.1.0",
     "diskusage": "^1.1.1",
-    "fcntl": "git+https://git.yourcmc.ru/vitalif/zenko-fcntl.git",
+    "fcntl": "github:scality/node-fcntl#0.2.2",
-    "httpagent": "git+https://git.yourcmc.ru/vitalif/zenko-httpagent.git#development/1.0",
+    "hdclient": "scality/hdclient#1.1.7",
+    "httpagent": "scality/httpagent#1.0.6",
     "https-proxy-agent": "^2.2.0",
     "ioredis": "^4.28.5",
-    "ipaddr.js": "^1.9.1",
+    "ipaddr.js": "1.9.1",
     "joi": "^17.6.0",
-    "JSONStream": "^1.0.0",
+    "level": "~5.0.1",
-    "level": "^5.0.1",
+    "level-sublevel": "~6.6.5",
-    "level-sublevel": "^6.6.5",
     "mongodb": "^5.2.0",
     "node-forge": "^1.3.0",
-    "prom-client": "^14.2.0",
+    "prom-client": "14.2.0",
     "simple-glob": "^0.2.0",
-    "socket.io": "^4.6.1",
+    "socket.io": "~4.6.1",
-    "socket.io-client": "^4.6.1",
+    "socket.io-client": "~4.6.1",
-    "utf8": "^3.0.0",
+    "sproxydclient": "git+https://github.com/scality/sproxydclient#8.0.10",
+    "utf8": "3.0.0",
     "uuid": "^3.0.1",
-    "werelogs": "git+https://git.yourcmc.ru/vitalif/zenko-werelogs.git#development/8.1",
+    "werelogs": "scality/werelogs#8.1.2",
-    "xml2js": "^0.4.23"
+    "xml2js": "~0.4.23"
   },
   "optionalDependencies": {
     "ioctl": "^2.0.2"
@@ -59,24 +60,22 @@
     "@babel/preset-env": "^7.16.11",
     "@babel/preset-typescript": "^7.16.7",
     "@sinonjs/fake-timers": "^6.0.1",
-    "@types/async": "^3.2.12",
-    "@types/utf8": "^3.0.1",
     "@types/ioredis": "^4.28.10",
     "@types/jest": "^27.4.1",
-    "@types/node": "^18.19.41",
+    "@types/node": "^17.0.21",
     "@types/xml2js": "^0.4.11",
     "eslint": "^8.14.0",
-    "eslint-config-airbnb-base": "^15.0.0",
+    "eslint-config-airbnb": "6.2.0",
-    "eslint-config-scality": "git+https://git.yourcmc.ru/vitalif/zenko-eslint-config-scality.git",
+    "eslint-config-scality": "scality/Guidelines#ec33dfb",
     "eslint-plugin-react": "^4.3.0",
     "jest": "^27.5.1",
     "mongodb-memory-server": "^8.12.2",
     "nyc": "^15.1.0",
     "sinon": "^9.0.2",
-    "temp": "^0.9.1",
+    "temp": "0.9.1",
     "ts-jest": "^27.1.3",
     "ts-node": "^10.6.0",
-    "typescript": "^4.9.5"
+    "typescript": "^4.6.2"
   },
   "scripts": {
     "lint": "eslint $(git ls-files '*.js')",
@@ -84,8 +83,7 @@
     "lint_yml": "yamllint $(git ls-files '*.yml')",
     "test": "jest tests/unit",
     "build": "tsc",
-    "prepack": "tsc",
+    "prepare": "yarn build",
-    "postinstall": "[ -d build ] || swc -d build --copy-files package.json index.ts lib",
     "ft_test": "jest tests/functional --testTimeout=120000 --forceExit",
     "coverage": "nyc --clean jest tests --coverage --testTimeout=120000 --forceExit",
     "build_doc": "cd documentation/listingAlgos/pics; dot -Tsvg delimiterStateChart.dot > delimiterStateChart.svg; dot -Tsvg delimiterMasterV0StateChart.dot > delimiterMasterV0StateChart.svg; dot -Tsvg delimiterVersionsStateChart.dot > delimiterVersionsStateChart.svg"

tests/functional/clustering/ClusterRPC-test-server.js

@@ -1,5 +1,4 @@
 const async = require('async');
-const assert = require('assert');
 const cluster = require('cluster');
 const http = require('http');
 
@@ -66,15 +65,6 @@ const rpcHandlers = {
     TestHandlerWithNoResponse: () => {},
 };
 
-const primaryHandlers = {
-    echoHandler: (worker, payload, uids, callback) => {
-        callback(null, { workerId: worker.id, payload, uids });
-    },
-    errorWithHttpCodeHandler: (_worker, _payload, _uids, callback) => {
-        callback({ name: 'ErrorMock', code: 418, message: 'An error message from primary' });
-    },
-};
-
 function respondOnTestFailure(message, error, results) {
     console.error('After sendWorkerCommand() resolve/reject: ' +
                   `${message}, error=${error}, results=${JSON.stringify(results)}`);
@@ -224,27 +214,6 @@ async function workerTimeoutTest() {
     }
 }
 
-async function workerToPrimaryEcho() {
-    const uids = genUIDS();
-    const payload = { testing: true };
-    const expected = { workerId: cluster.worker.id, payload, uids };
-
-    const results = await sendWorkerCommand('PRIMARY', 'echoHandler', uids, payload);
-    assert.strictEqual(results.length, 1, 'There is 1 and only 1 primary');
-    assert.ifError(results[0].error);
-    assert.deepStrictEqual(results[0].result, expected);
-}
-
-async function workerToPrimaryErrorWithHttpCode() {
-    const uids = genUIDS();
-    const payload = { testing: true };
-    const results = await sendWorkerCommand('PRIMARY', 'errorWithHttpCodeHandler', uids, payload);
-    assert.strictEqual(results.length, 1, 'There is 1 and only 1 primary');
-    assert.ok(results[0].error);
-    assert.strictEqual(results[0].error.message, 'An error message from primary');
-    assert.strictEqual(results[0].error.code, 418);
-}
-
 const TEST_URLS = {
     '/successful-command': successfulCommandTest,
     '/successful-command-with-extra-worker': successfulCommandWithExtraWorkerTest,
@@ -254,8 +223,6 @@ const TEST_URLS = {
     '/duplicate-uids': duplicateUidsTest,
     '/unsuccessful-worker': unsuccessfulWorkerTest,
     '/worker-timeout': workerTimeoutTest,
-    '/worker-to-primary/echo': workerToPrimaryEcho,
-    '/worker-to-primary/error-with-http-code': workerToPrimaryErrorWithHttpCode,
 };
 
 if (process.argv.length !== 4) {
@@ -280,7 +247,7 @@ if (cluster.isPrimary) {
         N_WORKERS,
         (i, wcb) => cluster.fork().on('online', wcb),
         () => {
-            setupRPCPrimary(primaryHandlers);
+            setupRPCPrimary();
         },
     );
 } else {
@@ -296,22 +263,8 @@ if (cluster.isPrimary) {
                 res.writeHead(200);
                 res.end();
             }).catch(err => {
-                // serialize AssertionError to be displayed nicely in jest
+                res.writeHead(err.code);
-                if (err instanceof assert.AssertionError) {
+                res.end(err.message);
-                    const serializedErr = JSON.stringify({
-                        code: err.code,
-                        message: err.message,
-                        stack: err.stack,
-                        actual: err.actual,
-                        expected: err.expected,
-                        operator: err.operator,
-                    });
-                    res.writeHead(500);
-                    res.end(serializedErr);
-                } else {
-                    res.writeHead(err.code || 500);
-                    res.end(err.message);
-                }
             });
         }
         console.error(`Invalid test URL ${req.url}`);

tests/functional/clustering/ClusterRPC.spec.js

@@ -1,5 +1,5 @@
 'use strict'; // eslint-disable-line
-const assert = require('assert');
+
 const http = require('http');
 const readline = require('readline');
 const spawn = require('child_process').spawn;
@@ -46,45 +46,13 @@ function stopTestServer(done) {
     testServer.on('close', done);
 }
 
-/**
- * Try to deserialize and recreate AssertionError with stackTrace from spawned server
- * @param {string} responseBody maybe serialized AssertionError
- * @throws {assert.AssertionError}
- * @returns {undefined}
- */
-function handleAssertionError(responseBody) {
-    let parsed;
-    try {
-        parsed = JSON.parse(responseBody);
-    } catch (_) {
-        return;
-    }
-
-    if (parsed && parsed.code === 'ERR_ASSERTION') {
-        const err = new assert.AssertionError(parsed);
-        err.stack = parsed.stack;
-        throw err;
-    }
-}
-
 function runTest(testUrl, cb) {
     const req = http.request(`http://localhost:${TEST_SERVER_PORT}/${testUrl}`, res => {
-        let responseBody = '';
         res
-            .on('data', (chunk) => {
+            .on('data', () => {})
-                responseBody += chunk;
-            })
             .on('end', () => {
-                try {
+                expect(res.statusCode).toEqual(200);
-                    handleAssertionError(responseBody);
+                cb();
-                    expect(res.statusCode).toEqual(200);
-                } catch (err) {
-                    if (!(err instanceof assert.AssertionError)) {
-                        err.message += `\n\nBody:\n${responseBody}`;
-                    }
-                    return cb(err);
-                }
-                return cb();
             })
             .on('error', err => cb(err));
     });
@@ -138,14 +106,4 @@ describe('ClusterRPC', () => {
         // The test server spawns a new worker when it receives SIGUSR1
         testServer.kill('SIGUSR1');
     });
-
-    describe('worker to primary', () => {
-        it('should succeed and return a result', done => {
-            runTest('worker-to-primary/echo', done);
-        });
-
-        it('should return an error with a code', done => {
-            runTest('worker-to-primary/error-with-http-code', done);
-        });
-    });
 });

tests/unit/algos/cache/GapCache.spec.ts

@@ -1,265 +0,0 @@
-import GapCache from '../../../../lib/algos/cache/GapCache';
-
-describe('GapCache', () => {
-    let gapCache;
-
-    beforeEach(() => {
-        // exposureDelayMs=100, maxGaps=10, maxGapWeight=100
-        gapCache = new GapCache(100, 10, 100);
-        gapCache.start();
-    });
-    afterEach(() => {
-        gapCache.stop();
-    });
-
-    describe('getters and setters', () => {
-        it('maxGapWeight getter', () => {
-            expect(gapCache.maxGapWeight).toEqual(100);
-        });
-
-        it('maxGapWeight setter', () => {
-            gapCache.maxGapWeight = 123;
-            expect(gapCache.maxGapWeight).toEqual(123);
-            // check that internal gap sets have also been updated
-            expect(gapCache._stagingUpdates.newGaps.maxWeight).toEqual(123);
-            expect(gapCache._frozenUpdates.newGaps.maxWeight).toEqual(123);
-        });
-
-        it('exposureDelayMs getter', () => {
-            expect(gapCache.exposureDelayMs).toEqual(100);
-        });
-
-        it('exposureDelayMs setter', async () => {
-            // insert a first gap
-            gapCache.setGap('bar', 'baz', 10);
-
-            // change the exposure delay to 50ms
-            gapCache.exposureDelayMs = 50;
-            expect(gapCache.exposureDelayMs).toEqual(50);
-
-            gapCache.setGap('qux', 'quz', 10);
-
-            // wait for more than twice the new exposure delay
-            await new Promise(resolve => setTimeout(resolve, 200));
-
-            // only the second gap should have been exposed, due to the change of
-            // exposure delay subsequent to the first call to setGap()
-            expect(await gapCache.lookupGap('ape', 'zoo')).toEqual(
-                { firstKey: 'qux', lastKey: 'quz', weight: 10 }
-            );
-        });
-    });
-
-    describe('clear()', () => {
-        it('should clear all exposed gaps', async () => {
-            gapCache.setGap('bar', 'baz', 10);
-            gapCache.setGap('qux', 'quz', 20);
-            await new Promise(resolve => setTimeout(resolve, 300));
-
-            expect(await gapCache.lookupGap('ape', 'zoo')).toEqual(
-                { firstKey: 'bar', lastKey: 'baz', weight: 10 }
-            );
-            gapCache.clear();
-            expect(await gapCache.lookupGap('ape', 'zoo')).toBeNull();
-        });
-
-        it('should clear all staging gaps', async () => {
-            gapCache.setGap('bar', 'baz', 10);
-            gapCache.setGap('qux', 'quz', 20);
-
-            gapCache.clear();
-            await new Promise(resolve => setTimeout(resolve, 300));
-
-            expect(await gapCache.lookupGap('ape', 'zoo')).toBeNull();
-        });
-
-        it('should keep existing invalidating updates against the next new gaps', async () => {
-            // invalidate future gaps containing 'dog'
-            expect(gapCache.removeOverlappingGaps(['dog'])).toEqual(0);
-
-            // then, clear the cache
-            gapCache.clear();
-
-            // wait for 50ms (half of exposure delay of 100ms) before
-            // setting a new gap overlapping with 'dog'
-            await new Promise(resolve => setTimeout(resolve, 50));
-            gapCache.setGap('cat', 'fox', 10);
-
-            // also set a non-overlapping gap to make sure it is not invalidated
-            gapCache.setGap('goat', 'hog', 20);
-
-            // wait an extra 250ms to ensure all valid gaps have been exposed
-            await new Promise(resolve => setTimeout(resolve, 250));
-            // the next gap is indeed 'goat'... because 'cat'... should have been invalidated
-            expect(await gapCache.lookupGap('bat', 'zoo')).toEqual(
-                { firstKey: 'goat', lastKey: 'hog', weight: 20 });
-        });
-    });
-
-    it('should expose gaps after at least exposureDelayMs milliseconds', async () => {
-        gapCache.setGap('bar', 'baz', 10);
-        expect(await gapCache.lookupGap('ape', 'cat')).toBeNull();
-
-        // wait for 50ms which is half of the minimum time to exposure
-        await new Promise(resolve => setTimeout(resolve, 50));
-        // the gap should not be exposed yet
-        expect(await gapCache.lookupGap('ape', 'cat')).toBeNull();
-
-        // wait for an extra 250ms (total 300ms): the upper bound for exposure of any
-        // setGap() call is twice the exposureDelayMs value, so 200ms, wait an extra
-        // 100ms to cope with scheduling uncertainty and GapSet processing time, after
-        // which the gap introduced by setGap() should always be exposed.
-        await new Promise(resolve => setTimeout(resolve, 250));
-        expect(await gapCache.lookupGap('ape', 'cat')).toEqual(
-            { firstKey: 'bar', lastKey: 'baz', weight: 10 });
-
-        // check getters
-        expect(gapCache.maxGaps).toEqual(10);
-        expect(gapCache.maxGapWeight).toEqual(100);
-        expect(gapCache.size).toEqual(1);
-
-        // check iteration over the exposed gaps
-        let nGaps = 0;
-        for (const gap of gapCache) {
-            expect(gap).toEqual({ firstKey: 'bar', lastKey: 'baz', weight: 10 });
-            nGaps += 1;
-        }
-        expect(nGaps).toEqual(1);
-
-        // check toArray()
-        expect(gapCache.toArray()).toEqual([
-            { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-        ]);
-    });
-
-    it('removeOverlappingGaps() should invalidate all overlapping gaps that are already exposed',
-    async () => {
-        gapCache.setGap('cat', 'fox', 10);
-        gapCache.setGap('lion', 'seal', 20);
-        // wait for 3x100ms to ensure all setGap() calls have been exposed
-        await new Promise(resolve => setTimeout(resolve, 300));
-        // expect 0 gap removed because 'hog' is not in any gap
-        expect(gapCache.removeOverlappingGaps(['hog'])).toEqual(0);
-        // expect 1 gap removed because 'cat' -> 'fox' should be already exposed
-        expect(gapCache.removeOverlappingGaps(['dog'])).toEqual(1);
-        // the gap should have been invalidated permanently
-        expect(await gapCache.lookupGap('dog', 'fox')).toBeNull();
-        // the other gap should still be present
-        expect(await gapCache.lookupGap('rat', 'tiger')).toEqual(
-            { firstKey: 'lion', lastKey: 'seal', weight: 20 });
-    });
-
-    it('removeOverlappingGaps() should invalidate all overlapping gaps that are not yet exposed',
-    async () => {
-        gapCache.setGap('cat', 'fox', 10);
-        gapCache.setGap('lion', 'seal', 20);
-        // make the following calls asynchronous for the sake of the
-        // test, but not waiting for the exposure delay
-        await new Promise(resolve => setImmediate(resolve));
-        // expect 0 gap removed because 'hog' is not in any gap
-        expect(gapCache.removeOverlappingGaps(['hog'])).toEqual(0);
-        // expect 0 gap removed because 'cat' -> 'fox' is not exposed yet,
-        // but internally it should have been removed from the staging or
-        // frozen gap set
-        expect(gapCache.removeOverlappingGaps(['dog'])).toEqual(0);
-
-        // wait for 3x100ms to ensure all non-invalidated setGap() calls have been exposed
-        await new Promise(resolve => setTimeout(resolve, 300));
-        // the gap should have been invalidated permanently
-        expect(await gapCache.lookupGap('dog', 'fox')).toBeNull();
-        // the other gap should now be exposed
-        expect(await gapCache.lookupGap('rat', 'tiger')).toEqual(
-            { firstKey: 'lion', lastKey: 'seal', weight: 20 });
-    });
-
-    it('removeOverlappingGaps() should invalidate gaps created later by setGap() but ' +
-    'within the exposure delay', async () => {
-        // wait for 80ms (slightly less than exposure delay of 100ms)
-        // before calling removeOverlappingGaps(), so that the next
-        // exposure timer kicks in before the call to setGap()
-        await new Promise(resolve => setTimeout(resolve, 80));
-
-        // there is no exposed gap yet, so expect 0 gap removed
-        expect(gapCache.removeOverlappingGaps(['dog'])).toEqual(0);
-
-        // wait for 50ms (half of exposure delay of 100ms) before
-        // setting a new gap overlapping with 'dog'
-        await new Promise(resolve => setTimeout(resolve, 50));
-        gapCache.setGap('cat', 'fox', 10);
-
-        // also set a non-overlapping gap to make sure it is not invalidated
-        gapCache.setGap('goat', 'hog', 20);
-
-        // wait an extra 250ms to ensure all valid gaps have been exposed
-        await new Promise(resolve => setTimeout(resolve, 250));
-        // the next gap is indeed 'goat'... because 'cat'... should have been invalidated
-        expect(await gapCache.lookupGap('bat', 'zoo')).toEqual(
-            { firstKey: 'goat', lastKey: 'hog', weight: 20 });
-    });
-
-    it('removeOverlappingGaps() should not invalidate gaps created more than twice ' +
-    'the exposure delay later', async () => {
-        // there is no exposed gap yet, so expect 0 gap removed
-        expect(gapCache.removeOverlappingGaps(['dog'])).toEqual(0);
-
-        // wait for 250ms (more than twice the exposure delay of 100ms) before
-        // setting a new gap overlapping with 'dog'
-        await new Promise(resolve => setTimeout(resolve, 250));
-        gapCache.setGap('cat', 'fox', 10);
-
-        // also set a non-overlapping gap to make sure it is not invalidated
-        gapCache.setGap('goat', 'hog', 20);
-
-        // wait for an extra 250ms to ensure the new gap is exposed
-        await new Promise(resolve => setTimeout(resolve, 250));
-        // should find the inserted gap as it should not have been invalidated
-        expect(await gapCache.lookupGap('bat', 'zoo')).toEqual(
-            { firstKey: 'cat', lastKey: 'fox', weight: 10 });
-    });
-
-    it('exposed gaps should be merged when possible', async () => {
-        gapCache.setGap('bar', 'baz', 10);
-        gapCache.setGap('baz', 'qux', 10);
-        // wait until the merged gap is exposed
-        await new Promise(resolve => setTimeout(resolve, 300));
-        expect(await gapCache.lookupGap('ape', 'cat')).toEqual(
-            { firstKey: 'bar', lastKey: 'qux', weight: 20 });
-    });
-
-    it('exposed gaps should be split when above maxGapWeight', async () => {
-        gapCache.setGap('bar', 'baz', gapCache.maxGapWeight - 1);
-        gapCache.setGap('baz', 'qux', 10);
-        // wait until the gaps are exposed
-        await new Promise(resolve => setTimeout(resolve, 300));
-        expect(await gapCache.lookupGap('cat', 'dog')).toEqual(
-            { firstKey: 'baz', lastKey: 'qux', weight: 10 });
-    });
-
-    it('gaps should not be exposed when reaching the maxGaps limit', async () => {
-        const gapsArray = new Array(gapCache.maxGaps).fill(undefined).map(
-            (_, i) => {
-                const firstKey = `0000${i}`.slice(-4);
-                return {
-                    firstKey,
-                    lastKey: `${firstKey}foo`,
-                    weight: 10,
-                };
-            }
-        );
-        for (const gap of gapsArray) {
-            gapCache.setGap(gap.firstKey, gap.lastKey, gap.weight);
-        }
-        // wait until the gaps are exposed
-        await new Promise(resolve => setTimeout(resolve, 300));
-        expect(gapCache.size).toEqual(gapCache.maxGaps);
-
-        gapCache.setGap('noroomforthisgap', 'noroomforthisgapfoo');
-        // wait until the gaps are exposed
-        await new Promise(resolve => setTimeout(resolve, 300));
-
-        // the number of gaps should still be 'maxGaps'
-        expect(gapCache.size).toEqual(gapCache.maxGaps);
-        // the gaps should correspond to the original array
-        expect(gapCache.toArray()).toEqual(gapsArray);
-    });
-});

tests/unit/algos/cache/GapSet.spec.ts

@@ -1,878 +0,0 @@
-import { OrderedSet } from '@js-sdsl/ordered-set';
-import GapSet from '../../../../lib/algos/cache/GapSet';
-
-function genRandomKey(): string {
-    const CHARS = 'abcdefghijklmnopqrstuvwxyz0123456789';
-    return new Array(16).fill(undefined).map(
-        () => CHARS[Math.trunc(Math.random() * CHARS.length)]
-    ).join('');
-}
-
-function genRandomUnchainedGaps(nGaps) {
-    const gapBounds = new Array(nGaps * 2).fill(undefined).map(
-        () => genRandomKey()
-    );
-    gapBounds.sort();
-    const gapsArray = new Array(nGaps).fill(undefined).map(
-        (_, i) => ({
-            firstKey: gapBounds[2 * i],
-            lastKey: gapBounds[2 * i + 1],
-            weight: 10,
-        })
-    );
-    return gapsArray;
-}
-
-function genRandomChainedGaps(nGaps) {
-    const gapBounds = new Array(nGaps + 1).fill(undefined).map(
-        () => genRandomKey()
-    );
-    gapBounds.sort();
-    const gapsArray = new Array(nGaps).fill(undefined).map(
-        (_, i) => ({
-            firstKey: gapBounds[i],
-            lastKey: gapBounds[i + 1],
-            weight: 10,
-        })
-    );
-    return gapsArray;
-}
-
-/**
- * Shuffle an array in-place
- *
- * @param {any[]} - The array to shuffle
- * @return {undefined}
- */
-function shuffleArray(array) {
-    for (let i = array.length - 1; i > 0; i--) {
-        const randIndex = Math.trunc(Math.random() * (i + 1));
-        /* eslint-disable no-param-reassign */
-        const randIndexVal = array[randIndex];
-        array[randIndex] = array[i];
-        array[i] = randIndexVal;
-        /* eslint-enable no-param-reassign */
-    }
-}
-
-describe('GapSet', () => {
-    const INITIAL_GAPSET = [
-        { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-        { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-    ];
-    const INITIAL_GAPSET_WITH_CHAIN = [
-        // single-key gap
-        { firstKey: 'ape', lastKey: 'ape', weight: 1 },
-        // start of chain
-        { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-        { firstKey: 'baz', lastKey: 'qux', weight: 15 },
-        { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-        { firstKey: 'quz', lastKey: 'rat', weight: 25 },
-        { firstKey: 'rat', lastKey: 'yak', weight: 30 },
-        // end of chain
-    ]
-
-    let gapsArray;
-    let gapSet;
-    let gapsArrayWithChain;
-    let gapSetWithChain;
-    beforeEach(() => {
-        gapsArray = JSON.parse(
-            JSON.stringify(INITIAL_GAPSET)
-        );
-        gapSet = GapSet.createFromArray(gapsArray, 100);
-        gapsArrayWithChain = JSON.parse(
-            JSON.stringify(INITIAL_GAPSET_WITH_CHAIN)
-        );
-        gapSetWithChain = GapSet.createFromArray(gapsArrayWithChain, 100);
-    });
-
-    describe('GapSet::size', () => {
-        it('should return 0 for an empty gap set', () => {
-            const emptyGapSet = new GapSet(100);
-            expect(emptyGapSet.size).toEqual(0);
-        });
-
-        it('should return the size of the gap set', () => {
-            expect(gapSet.size).toEqual(2);
-        });
-
-        it('should reflect the new size after removal of gaps', () => {
-            gapSet._gaps.eraseElementByKey({ firstKey: 'bar' });
-            expect(gapSet.size).toEqual(1);
-        });
-    });
-
-    describe('GapSet::maxWeight', () => {
-        it('getter', () => {
-            const emptyGapSet = new GapSet(123);
-            expect(emptyGapSet.maxWeight).toEqual(123);
-        });
-
-        it('setter', () => {
-            const emptyGapSet = new GapSet(123);
-            emptyGapSet.maxWeight = 456;
-            expect(emptyGapSet.maxWeight).toEqual(456);
-        });
-    });
-
-    describe('GapSet::setGap()', () => {
-        it('should start a gap with a single key in empty gap set', () => {
-            const emptyGapSet = new GapSet(100);
-            const gap = emptyGapSet.setGap('foo', 'foo', 1);
-            expect(gap).toEqual({ firstKey: 'foo', lastKey: 'foo', weight: 1 });
-            expect(emptyGapSet.toArray()).toEqual([
-                { firstKey: 'foo', lastKey: 'foo', weight: 1 },
-            ]);
-        });
-
-        it('should start a gap with a single key in non-empty gap set', () => {
-            const gap = gapSet.setGap('foo', 'foo', 1);
-            expect(gap).toEqual({ firstKey: 'foo', lastKey: 'foo', weight: 1 });
-            expect(gapSet.toArray()).toEqual([
-                { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                { firstKey: 'foo', lastKey: 'foo', weight: 1 },
-                { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-            ]);
-        });
-
-        it('should start a gap with multiple keys in empty gap set', () => {
-            const emptyGapSet = new GapSet(100);
-            const gap = emptyGapSet.setGap('foo', 'qux', 5);
-            expect(gap).toEqual({ firstKey: 'foo', lastKey: 'qux', weight: 5 });
-            expect(emptyGapSet.toArray()).toEqual([
-                { firstKey: 'foo', lastKey: 'qux', weight: 5 },
-            ]);
-        });
-
-        it('should return a new object rather than a gap managed by GapSet', () => {
-            const emptyGapSet = new GapSet(100);
-            const gap = emptyGapSet.setGap('foo', 'qux', 5);
-            gap.lastKey = 'quz';
-            // check that modifying the returned gap doesn't affect the GapSet
-            expect(emptyGapSet.toArray()).toEqual([
-                { firstKey: 'foo', lastKey: 'qux', weight: 5 },
-            ]);
-        });
-
-        it('should return an existing gap that includes the wanted gap', () => {
-            const gap = gapSet.setGap('bat', 'bay', 5);
-            expect(gap).toEqual({ firstKey: 'bar', lastKey: 'baz', weight: 10 });
-            expect(gapSet.toArray()).toEqual(INITIAL_GAPSET);
-        });
-
-        it('should return an existing gap that starts with the wanted gap first key', () => {
-            const gap = gapSet.setGap('bar', 'bay', 5);
-            expect(gap).toEqual({ firstKey: 'bar', lastKey: 'baz', weight: 10 });
-            expect(gapSet.toArray()).toEqual(INITIAL_GAPSET);
-        });
-
-        it('should return an existing gap that ends with the wanted gap last key', () => {
-            const gap = gapSet.setGap('bat', 'baz', 5);
-            expect(gap).toEqual({ firstKey: 'bar', lastKey: 'baz', weight: 10 });
-            expect(gapSet.toArray()).toEqual(INITIAL_GAPSET);
-        });
-
-        it('should return the existing chained gap that starts with the first key', () => {
-            const gap = gapSetWithChain.setGap('baz', 'quo', 10);
-            expect(gap).toEqual({ firstKey: 'baz', lastKey: 'qux', weight: 15 });
-            expect(gapSetWithChain.toArray()).toEqual(INITIAL_GAPSET_WITH_CHAIN);
-        });
-
-        it('should extend a single-key gap with no other gap', () => {
-            const singleKeyGap = { firstKey: 'foo', lastKey: 'foo', weight: 1 };
-            const singleKeyGapSet = GapSet.createFromArray([singleKeyGap], 100);
-
-            const extendedGap = singleKeyGapSet.setGap('foo', 'qux', 30);
-            expect(extendedGap).toEqual({ firstKey: 'foo', lastKey: 'qux', weight: 31 });
-            expect(singleKeyGapSet.toArray()).toEqual([
-                { firstKey: 'foo', lastKey: 'qux', weight: 31 },
-            ]);
-        });
-
-        it('should extend a gap with no next gap', () => {
-            // existing gap: 'qux' -> 'quz'
-            const extendedGap = gapSet.setGap('qux', 'rat', 25);
-            expect(extendedGap).toEqual({ firstKey: 'qux', lastKey: 'rat', weight: 25 });
-            expect(gapSet.toArray()).toEqual([
-                { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                { firstKey: 'qux', lastKey: 'rat', weight: 25 },
-            ]);
-        });
-
-        it('should extend a gap without overlap with next gap', () => {
-            // existing gap: 'bar' -> 'baz'
-            const extendedGap = gapSet.setGap('bar', 'dog', 15);
-            expect(extendedGap).toEqual({ firstKey: 'bar', lastKey: 'dog', weight: 15 });
-            expect(gapSet.toArray()).toEqual([
-                { firstKey: 'bar', lastKey: 'dog', weight: 15 },
-                { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-            ]);
-        });
-
-        it('should extend a gap starting from its last key', () => {
-            // existing gap: 'qux' -> 'quz'
-            const extendedGap = gapSet.setGap('quz', 'rat', 5);
-            expect(extendedGap).toEqual({ firstKey: 'qux', lastKey: 'rat', weight: 25 });
-            expect(gapSet.toArray()).toEqual([
-                { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                { firstKey: 'qux', lastKey: 'rat', weight: 25 },
-            ]);
-        });
-
-        it('should merge with next gap with single-key overlap if total weight is ' +
-        'under maxWeight', () => {
-            const extendedGap = gapSet.setGap('bar', 'qux', 80);
-            // updated weight is accurately set as the sum of
-            // overlapping individual gap weights
-            expect(extendedGap).toEqual({ firstKey: 'bar', lastKey: 'quz', weight: 80 + 20 });
-            expect(gapSet.toArray()).toEqual([
-                { firstKey: 'bar', lastKey: 'quz', weight: 80 + 20 },
-            ]);
-        });
-
-        it('should chain with next gap with single-key overlap if total weight is ' +
-        'above maxWeight', () => {
-            const extendedGap = gapSet.setGap('bar', 'qux', 90);
-            expect(extendedGap).toEqual({ firstKey: 'qux', lastKey: 'quz', weight: 20 });
-            expect(gapSet.toArray()).toEqual([
-                { firstKey: 'bar', lastKey: 'qux', weight: 90 },
-                { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-            ]);
-        });
-
-        it('should merge with both previous and next gap if bounds overlap by a ' +
-        'single key and total weight is under maxWeight', () => {
-            const extendedGap = gapSet.setGap('baz', 'qux', 30);
-            // updated weight is accurately set as the sum of
-            // overlapping individual gap weights
-            expect(extendedGap).toEqual({ firstKey: 'bar', lastKey: 'quz', weight: 10 + 30 + 20 });
-            expect(gapSet.toArray()).toEqual([
-                { firstKey: 'bar', lastKey: 'quz', weight: 10 + 30 + 20 },
-            ]);
-        });
-
-        it('should merge with previous gap and chain with next gap if bounds overlap by a ' +
-        'single key on either side and weight is above maxWeight when merging on right side', () => {
-            const extendedGap = gapSet.setGap('baz', 'qux', 90);
-            expect(extendedGap).toEqual({ firstKey: 'qux', lastKey: 'quz', weight: 20 });
-            expect(gapSet.toArray()).toEqual([
-                { firstKey: 'bar', lastKey: 'qux', weight: 100 },
-                { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-            ]);
-        });
-
-        it('should chain with previous gap and merge with next gap if bounds overlap by a ' +
-        'single key on either side and weight is above maxWeight when merging on left side', () => {
-            // modified version of the common test set with increased weight
-            // for 'bar' -> 'baz'
-            const gapSet = GapSet.createFromArray([
-                { firstKey: 'bar', lastKey: 'baz', weight: 80 },
-                { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-            ], 100);
-            const extendedGap = gapSet.setGap('baz', 'qux', 70);
-            expect(extendedGap).toEqual({ firstKey: 'baz', lastKey: 'quz', weight: 90 });
-            expect(gapSet.toArray()).toEqual([
-                { firstKey: 'bar', lastKey: 'baz', weight: 80 },
-                { firstKey: 'baz', lastKey: 'quz', weight: 90 },
-            ]);
-        });
-
-        it('should merge with both previous and next gap if left bound overlaps by a ' +
-        'single key and total weight is under maxWeight', () => {
-            const extendedGap = gapSet.setGap('baz', 'quxxx', 40);
-            // updated weight is heuristically set as the sum of the
-            // previous chained gap's weight and the new weight
-            // (excluding the overlapping gap on right side)
-            expect(extendedGap).toEqual({ firstKey: 'bar', lastKey: 'quz', weight: 10 + 40 });
-            expect(gapSet.toArray()).toEqual([
-                { firstKey: 'bar', lastKey: 'quz', weight: 10 + 40 },
-            ]);
-        });
-
-        it('should chain with previous gap and merge with next gap if left bound overlaps by a ' +
-        'single key and total weight is above maxWeight', () => {
-            const extendedGap = gapSet.setGap('baz', 'quxxx', 95);
-            // updated weight is accurately set as the sum of
-            // overlapping individual gap weights
-            expect(extendedGap).toEqual({ firstKey: 'baz', lastKey: 'quz', weight: 95 });
-            expect(gapSet.toArray()).toEqual([
-                { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                { firstKey: 'baz', lastKey: 'quz', weight: 95 },
-            ]);
-        });
-
-        it('should extend a gap with overlap with next gap and large weight', () => {
-            const extendedGap = gapSet.setGap('bar', 'quxxx', 80);
-            // updated weight is heuristically chosen to be the new
-            // gap weight which is larger than the sum of the existing merged
-            // gap weights
-            expect(extendedGap).toEqual({ firstKey: 'bar', lastKey: 'quz', weight: 80 });
-            expect(gapSet.toArray()).toEqual([
-                { firstKey: 'bar', lastKey: 'quz', weight: 80 },
-            ]);
-        });
-
-        it('should extend a gap with overlap with next gap and small weight', () => {
-            const extendedGap = gapSet.setGap('bar', 'quxxx', 11);
-            // updated weight is heuristically chosen to be the sum of the existing merged
-            // gap weights which is larger than the new gap weight
-            expect(extendedGap).toEqual({ firstKey: 'bar', lastKey: 'quz', weight: 10 + 20 });
-            expect(gapSet.toArray()).toEqual([
-                { firstKey: 'bar', lastKey: 'quz', weight: 10 + 20 },
-            ]);
-        });
-
-        it('should extend a gap with overlap beyond last key of next gap', () => {
-            const extendedGap = gapSet.setGap('bar', 'rat', 80);
-            // updated weight is the new gap weight
-            expect(extendedGap).toEqual({ firstKey: 'bar', lastKey: 'rat', weight: 80 });
-            expect(gapSet.toArray()).toEqual([
-                { firstKey: 'bar', lastKey: 'rat', weight: 80 },
-            ]);
-        });
-
-        it('should extend a gap with overlap beyond last key of next gap with a chained gap ' +
-        'if above maxWeight', () => {
-            // gapSet was initialized with maxWeight=100
-            const extendedGap = gapSet.setGap('bar', 'rat', 105);
-            // returned new gap is the right-side chained gap
-            // updated weight is the new gap weight minus the left-side chained gap's weight
-            expect(extendedGap).toEqual({ firstKey: 'baz', lastKey: 'rat', weight: 105 - 10 });
-            expect(gapSet.toArray()).toEqual([
-                { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                { firstKey: 'baz', lastKey: 'rat', weight: 105 - 10 },
-            ]);
-        });
-
-        it('should extend a single-key gap with overlap on chained gaps', () => {
-            // existing gap: 'ape' -> 'ape' (weight=1)
-            const extendedGap = gapSetWithChain.setGap('ape', 'dog', 30);
-            // updated weight heuristically including the new gap
-            // weight, which is larger than the overlapping gaps cumulated
-            // weights (10+15=25)
-            expect(extendedGap).toEqual({ firstKey: 'ape', lastKey: 'qux', weight: 30 });
-            expect(gapSetWithChain.toArray()).toEqual([
-                { firstKey: 'ape', lastKey: 'qux', weight: 30 },
-                { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                { firstKey: 'quz', lastKey: 'rat', weight: 25 },
-                { firstKey: 'rat', lastKey: 'yak', weight: 30 },
-            ]);
-        });
-
-        it('should merge and extend + update weight a gap with overlap not past end of chained gaps',
-        () => {
-            const extendedGap = gapSetWithChain.setGap('baz', 'sea', 80);
-            expect(extendedGap).toEqual({ firstKey: 'baz', lastKey: 'yak', weight: 90 });
-            expect(gapSetWithChain.toArray()).toEqual([
-                { firstKey: 'ape', lastKey: 'ape', weight: 1 },
-                { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                { firstKey: 'baz', lastKey: 'yak', weight: 90 },
-            ]);
-        });
-
-        it('should merge and extend + update weight a gap with overlap past end of chained gaps',
-        () => {
-            const extendedGap = gapSetWithChain.setGap('baz', 'zoo', 95);
-            expect(extendedGap).toEqual({ firstKey: 'baz', lastKey: 'zoo', weight: 95 });
-            expect(gapSetWithChain.toArray()).toEqual([
-                { firstKey: 'ape', lastKey: 'ape', weight: 1 },
-                { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                { firstKey: 'baz', lastKey: 'zoo', weight: 95 },
-            ]);
-        });
-
-        it('should extend gap + update weight with overlap past end of chained gaps and ' +
-        'above maxWeight', () => {
-            const extendedGap = gapSetWithChain.setGap('baz', 'zoo', 105);
-            // updated weight is the new gap weight minus the left-side chained gap's weight
-            expect(extendedGap).toEqual({ firstKey: 'qux', lastKey: 'zoo', weight: 105 - 15 });
-            expect(gapSetWithChain.toArray()).toEqual([
-                { firstKey: 'ape', lastKey: 'ape', weight: 1 },
-                { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                { firstKey: 'baz', lastKey: 'qux', weight: 15 },
-                { firstKey: 'qux', lastKey: 'zoo', weight: 105 - 15 },
-            ]);
-        });
-
-        it('should return existing chained gap with overlap above maxWeight', () => {
-            const chainedGapsArray = [
-                { firstKey: 'ant', lastKey: 'cat', weight: 90 },
-                { firstKey: 'cat', lastKey: 'fox', weight: 40 },
-            ];
-            const chainedGapsSet = GapSet.createFromArray(chainedGapsArray, 100);
-            const extendedGap = chainedGapsSet.setGap('bat', 'dog', 105);
-            expect(extendedGap).toEqual({ firstKey: 'cat', lastKey: 'fox', weight: 40 });
-            expect(chainedGapsSet.toArray()).toEqual([
-                { firstKey: 'ant', lastKey: 'cat', weight: 90 },
-                { firstKey: 'cat', lastKey: 'fox', weight: 40 },
-            ]);
-        });
-
-        it('should merge but not extend nor update weight with overlap on chained gaps', () => {
-            // existing chained gap: 'baz' -> 'qux'
-            const extendedGap = gapSetWithChain.setGap('baz', 'quxxx', 25);
-            // updated weight is the sum of the two merged gap's weights
-            expect(extendedGap).toEqual({ firstKey: 'baz', lastKey: 'quz', weight: 15 + 20 });
-            expect(gapSetWithChain.toArray()).toEqual([
-                { firstKey: 'ape', lastKey: 'ape', weight: 1 },
-                { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                { firstKey: 'baz', lastKey: 'quz', weight: 15 + 20 },
-                { firstKey: 'quz', lastKey: 'rat', weight: 25 },
-                { firstKey: 'rat', lastKey: 'yak', weight: 30 },
-            ]);
-        });
-    });
-
-    describe('GapSet::removeOverlappingGaps()', () => {
-        describe('with zero key as parameter', () => {
-            it('passed in an array: should not remove any gap', () => {
-                const nRemoved = gapSet.removeOverlappingGaps([]);
-                expect(nRemoved).toEqual(0);
-                expect(gapSet.toArray()).toEqual(INITIAL_GAPSET);
-            });
-            it('passed in a OrderedSet: should not remove any gap', () => {
-                const nRemoved = gapSet.removeOverlappingGaps(new OrderedSet());
-                expect(nRemoved).toEqual(0);
-                expect(gapSet.toArray()).toEqual(INITIAL_GAPSET);
-            });
-        });
-        describe('with an array of one key as parameter', () => {
-            it('should not remove any gap if no overlap', () => {
-                const nRemoved = gapSet.removeOverlappingGaps(['rat']);
-                expect(nRemoved).toEqual(0);
-                expect(gapSet.toArray()).toEqual(INITIAL_GAPSET);
-            });
-
-            it('should remove a single gap if overlaps', () => {
-                const nRemoved = gapSet.removeOverlappingGaps(['bat']);
-                expect(nRemoved).toEqual(1);
-                expect(gapSet.toArray()).toEqual([
-                    // removed: { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                ]);
-            });
-
-            it('should remove a single gap if overlaps with first key of first gap', () => {
-                const nRemoved = gapSet.removeOverlappingGaps(['bar']);
-                expect(nRemoved).toEqual(1);
-                expect(gapSet.toArray()).toEqual([
-                    // removed: { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                ]);
-            });
-
-            it('should remove a single gap if overlaps with first key of non-first gap', () => {
-                const nRemoved = gapSet.removeOverlappingGaps(['qux']);
-                expect(nRemoved).toEqual(1);
-                expect(gapSet.toArray()).toEqual([
-                    { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    // removed: { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                ]);
-            });
-
-            it('should remove a single gap if overlaps with last key', () => {
-                const nRemoved = gapSet.removeOverlappingGaps(['quz']);
-                expect(nRemoved).toEqual(1);
-                expect(gapSet.toArray()).toEqual([
-                    { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    // removed: { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                ]);
-            });
-
-            it('should remove a single gap in chain if overlaps with one chained gap', () => {
-                const nRemoved = gapSetWithChain.removeOverlappingGaps(['dog']);
-                expect(nRemoved).toEqual(1);
-                expect(gapSetWithChain.toArray()).toEqual([
-                    { firstKey: 'ape', lastKey: 'ape', weight: 1 },
-                    { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    // removed: { firstKey: 'baz', lastKey: 'qux', weight: 15 },
-                    { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                    { firstKey: 'quz', lastKey: 'rat', weight: 25 },
-                    { firstKey: 'rat', lastKey: 'yak', weight: 30 },
-                ]);
-            });
-
-            it('should remove two gaps in chain if overlaps with two chained gap', () => {
-                const nRemoved = gapSetWithChain.removeOverlappingGaps(['qux']);
-                expect(nRemoved).toEqual(2);
-                expect(gapSetWithChain.toArray()).toEqual([
-                    { firstKey: 'ape', lastKey: 'ape', weight: 1 },
-                    { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    // removed: { firstKey: 'baz', lastKey: 'qux', weight: 15 },
-                    // removed: { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                    { firstKey: 'quz', lastKey: 'rat', weight: 25 },
-                    { firstKey: 'rat', lastKey: 'yak', weight: 30 },
-                ]);
-            });
-        });
-
-        describe('with an array of two keys as parameter', () => {
-            it('should not remove any gap if no overlap', () => {
-                const nRemoved = gapSet.removeOverlappingGaps(['rat', `rat\0v100`]);
-                expect(nRemoved).toEqual(0);
-                expect(gapSet.toArray()).toEqual(INITIAL_GAPSET);
-            });
-
-            it('should remove a single gap if both keys overlap', () => {
-                const nRemoved = gapSet.removeOverlappingGaps(['bat', 'bat\0v100']);
-                expect(nRemoved).toEqual(1);
-                expect(gapSet.toArray()).toEqual([
-                    // removed: { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                ]);
-            });
-
-            it('should remove a single gap if min key overlaps with first key of first gap', () => {
-                const nRemoved = gapSet.removeOverlappingGaps(['bar\0v100', 'bar']);
-                expect(nRemoved).toEqual(1);
-                expect(gapSet.toArray()).toEqual([
-                    // removed: { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                ]);
-            });
-
-            it('should remove a single gap if max key overlaps with first key of first gap', () => {
-                const nRemoved = gapSet.removeOverlappingGaps(['ape', 'bar']);
-                expect(nRemoved).toEqual(1);
-                expect(gapSet.toArray()).toEqual([
-                    // removed: { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                ]);
-            });
-
-            it('should not remove any gap if both keys straddle an existing gap without overlap',
-            () => {
-                const nRemoved = gapSet.removeOverlappingGaps(['cow', 'ape']);
-                expect(nRemoved).toEqual(0);
-                expect(gapSet.toArray()).toEqual([
-                    { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                ]);
-            });
-
-            it('should remove the two last gaps in chained gaps if last gap bounds match ' +
-            'the two keys', () => {
-                const nRemoved = gapSetWithChain.removeOverlappingGaps(['yak', 'rat']);
-                expect(nRemoved).toEqual(2);
-                expect(gapSetWithChain.toArray()).toEqual([
-                    { firstKey: 'ape', lastKey: 'ape', weight: 1 },
-                    { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    { firstKey: 'baz', lastKey: 'qux', weight: 15 },
-                    { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                    // removed: { firstKey: 'quz', lastKey: 'rat', weight: 25 },
-                    // removed: { firstKey: 'rat', lastKey: 'yak', weight: 30 },
-                ]);
-            });
-
-            it('should remove first and last gap in chained gaps if their bounds match ' +
-            'the two keys', () => {
-                const nRemoved = gapSetWithChain.removeOverlappingGaps(['yak', 'bar']);
-                expect(nRemoved).toEqual(2);
-                expect(gapSetWithChain.toArray()).toEqual([
-                    { firstKey: 'ape', lastKey: 'ape', weight: 1 },
-                    // removed: { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    { firstKey: 'baz', lastKey: 'qux', weight: 15 },
-                    { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                    { firstKey: 'quz', lastKey: 'rat', weight: 25 },
-                    // removed: { firstKey: 'rat', lastKey: 'yak', weight: 30 },
-                ]);
-            });
-        });
-
-        describe('with an array of three keys as parameter', () => {
-            it('should remove a single gap if only median key overlaps with gap', () => {
-                const nRemoved = gapSet.removeOverlappingGaps(['ape', 'bat', 'cow']);
-                expect(nRemoved).toEqual(1);
-                expect(gapSet.toArray()).toEqual([
-                    // removed: { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                ]);
-            });
-
-            it('should remove a single-key gap and two contiguous chained gaps each overlapping' +
-            'with one key', () => {
-                const nRemoved = gapSetWithChain.removeOverlappingGaps(['ape', 'bat', 'cow']);
-                expect(nRemoved).toEqual(3);
-                expect(gapSetWithChain.toArray()).toEqual([
-                    // removed: { firstKey: 'ape', lastKey: 'ape', weight: 1 },
-                    // removed: { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    // removed: { firstKey: 'baz', lastKey: 'qux', weight: 15 },
-                    { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                    { firstKey: 'quz', lastKey: 'rat', weight: 25 },
-                    { firstKey: 'rat', lastKey: 'yak', weight: 30 },
-                ]);
-            });
-
-            it('should not remove any gap if all keys are intermingled but do not overlap', () => {
-                const nRemoved = gapSet.removeOverlappingGaps(['ape', 'rat', 'cow']);
-                expect(nRemoved).toEqual(0);
-                expect(gapSet.toArray()).toEqual([
-                    { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                ]);
-            });
-
-            it('should remove three discontiguous chained gaps each overlapping with one key', () => {
-                const nRemoved = gapSetWithChain.removeOverlappingGaps(['bat', 'quxxx', 'tiger']);
-                expect(nRemoved).toEqual(3);
-                expect(gapSetWithChain.toArray()).toEqual([
-                    { firstKey: 'ape', lastKey: 'ape', weight: 1 },
-                    // removed: { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    { firstKey: 'baz', lastKey: 'qux', weight: 15 },
-                    // removed: { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                    { firstKey: 'quz', lastKey: 'rat', weight: 25 },
-                    // { firstKey: 'rat', lastKey: 'yak', weight: 30 },
-                ]);
-            });
-        });
-
-        describe('with a OrderedSet of three keys as parameter', () => {
-            it('should remove a single gap if only median key overlaps with gap', () => {
-                const nRemoved = gapSet.removeOverlappingGaps(
-                    new OrderedSet(['ape', 'bat', 'cow']));
-                expect(nRemoved).toEqual(1);
-                expect(gapSet.toArray()).toEqual([
-                    // removed: { firstKey: 'bar', lastKey: 'baz', weight: 10 },
-                    { firstKey: 'qux', lastKey: 'quz', weight: 20 },
-                ]);
-            });
-        });
-
-        // this helper checks that:
-        // - the gaps not overlapping with any key are still present in newGapsArray
-        // - and the gaps overlapping with at least one key have been removed from oldGapsArray
-        // NOTE: It uses a sorted list of keys for efficiency, otherwise it would require
-        // O(n^2) compute time which would be expensive with 50K keys.
-        function checkOverlapInvariant(sortedKeys, oldGapsArray, newGapsArray) {
-            let oldGapIdx = 0;
-            let newGapIdx = 0;
-            for (const key of sortedKeys) {
-                // for all gaps not overlapping with any key in 'sortedKeys',
-                // check that they are still in 'newGapsArray'
-                while (oldGapIdx < oldGapsArray.length &&
-                       oldGapsArray[oldGapIdx].lastKey < key) {
-                    expect(oldGapsArray[oldGapIdx]).toEqual(newGapsArray[newGapIdx]);
-                    oldGapIdx += 1;
-                    newGapIdx += 1;
-                }
-                // for the gap(s) overlapping with the current key,
-                // check that they have been removed from 'newGapsArray'
-                while (oldGapIdx < oldGapsArray.length &&
-                       oldGapsArray[oldGapIdx].firstKey <= key) {
-                    if (newGapIdx < newGapsArray.length) {
-                        expect(oldGapsArray[oldGapIdx]).not.toEqual(newGapsArray[newGapIdx]);
-                    }
-                    ++oldGapIdx;
-                }
-            }
-            // check the range after the last key in 'sortedKeys'
-            while (oldGapIdx < oldGapsArray.length) {
-                expect(oldGapsArray[oldGapIdx]).toEqual(newGapsArray[newGapIdx]);
-                oldGapIdx += 1;
-                newGapIdx += 1;
-            }
-            // check that no extra range is in newGapsArray
-            expect(newGapIdx).toEqual(newGapsArray.length);
-        }
-
-        [false, true].forEach(chained => {
-            describe(`with 10K random ${chained ? 'chained' : 'unchained'} gaps`, () => {
-                let largeGapsArray;
-                let largeGapSet;
-                beforeEach(() => {
-                    largeGapsArray = chained ?
-                        genRandomChainedGaps(10000) :
-                        genRandomUnchainedGaps(10000);
-                    largeGapSet = GapSet.createFromArray(largeGapsArray, 100);
-                });
-
-                [{
-                    desc: 'equal to their first key',
-                    getGapKey: gap => gap.firstKey,
-                }, {
-                    desc: 'equal to their last key',
-                    getGapKey: gap => gap.lastKey,
-                }, {
-                    desc: 'neither their first nor last key',
-                    getGapKey: gap => `${gap.firstKey}/foo`,
-                }].forEach(testCase => {
-                    it(`should remove the overlapping gap(s) with one key ${testCase.desc}`, () => {
-                        const gapIndex = 5000;
-                        const gap = largeGapsArray[gapIndex];
-                        const overlappingKey = testCase.getGapKey(gap);
-                        const nRemoved = largeGapSet.removeOverlappingGaps([overlappingKey]);
-                        let firstRemovedGapIndex, lastRemovedGapIndex;
-                        if (chained && overlappingKey === gap.firstKey) {
-                            expect(nRemoved).toEqual(2);
-                            [firstRemovedGapIndex, lastRemovedGapIndex] = [4999, 5000];
-                        } else if (chained && overlappingKey === gap.lastKey) {
-                            expect(nRemoved).toEqual(2);
-                            [firstRemovedGapIndex, lastRemovedGapIndex] = [5000, 5001];
-                        } else {
-                            expect(nRemoved).toEqual(1);
-                            [firstRemovedGapIndex, lastRemovedGapIndex] = [5000, 5000];
-                        }
-                        const expectedGaps = [
-                            ...largeGapsArray.slice(0, firstRemovedGapIndex),
-                            ...largeGapsArray.slice(lastRemovedGapIndex + 1)
-                        ];
-                        const newGaps = largeGapSet.toArray();
-                        expect(newGaps).toEqual(expectedGaps);
-                    });
-
-                    it(`should remove all gaps when they all overlap with one key ${testCase.desc}`,
-                       () => {
-                           // simulate a scenario made of 200 batches of 50 operations, each with
-                           // random keys scattered across all gaps that each overlaps a distinct gap
-                           // (supposedly a worst-case performance scenario for such batch sizes)
-                           const overlappingKeys = largeGapsArray.map(testCase.getGapKey);
-                           shuffleArray(overlappingKeys);
-                           for (let i = 0; i < overlappingKeys.length; i += 50) {
-                               const nRemoved = largeGapSet.removeOverlappingGaps(
-                                   overlappingKeys.slice(i, i + 50));
-                               // with unchained gaps, we expect to have removed exactly
-                               // 50 gaps (the size of 'overlappingKeys').
-                               if (!chained) {
-                                   expect(nRemoved).toEqual(50);
-                               }
-                           }
-                           const newGaps = largeGapSet.toArray();
-                           expect(newGaps).toEqual([]);
-                       });
-                });
-
-                it('should remove only and all overlapping gaps with 50K randomized keys', () => {
-                    const randomizedKeys = new Array(50000).fill(undefined).map(
-                        () => genRandomKey()
-                    );
-                    for (let i = 0; i < randomizedKeys.length; i += 50) {
-                        largeGapSet.removeOverlappingGaps(
-                            randomizedKeys.slice(i, i + 50));
-                    }
-                    const newGaps = largeGapSet.toArray();
-                    randomizedKeys.sort();
-                    checkOverlapInvariant(randomizedKeys, largeGapsArray, newGaps);
-                });
-            });
-        });
-    });
-
-    describe('GapSet::_coalesceGapChain()', () => {
-        afterEach(() => {
-            // check that the gap sets were not modified by the operation
-            expect(gapSet.toArray()).toEqual(INITIAL_GAPSET);
-            expect(gapSetWithChain.toArray()).toEqual(INITIAL_GAPSET_WITH_CHAIN);
-        });
-        it('should not coalesce if gaps are not chained', async () => {
-            const gap = { firstKey: 'bar', lastKey: 'baz', weight: 10 };
-            const coalescedGap = await gapSet._coalesceGapChain(gap);
-            expect(coalescedGap).toEqual({ firstKey: 'bar', lastKey: 'baz', weight: 10 });
-        });
-
-        it('should coalesce one chained gap', async () => {
-            const gap = { firstKey: 'quz', lastKey: 'rat', weight: 25 };
-            const coalescedGap = await gapSetWithChain._coalesceGapChain(gap);
-            expect(coalescedGap).toEqual({ firstKey: 'quz', lastKey: 'yak', weight: 55 });
-        });
-
-        it('should coalesce a chain of five gaps', async () => {
-            const gap = { firstKey: 'bar', lastKey: 'baz', weight: 10 };
-            const coalescedGap = await gapSetWithChain._coalesceGapChain(gap);
-            expect(coalescedGap).toEqual({ firstKey: 'bar', lastKey: 'yak', weight: 100 });
-        });
-
-        it('should coalesce a chain of one thousand gaps', async () => {
-            const getKey = i => `000${i}`.slice(-4);
-            const thousandGapsArray = new Array(1000).fill(undefined).map(
-                (_, i) => ({ firstKey: getKey(i), lastKey: getKey(i + 1), weight: 10 })
-            );
-            const thousandGapsSet = GapSet.createFromArray(thousandGapsArray, 100);
-            const gap = { firstKey: '0000', lastKey: '0001', weight: 10 };
-            const coalescedGap = await thousandGapsSet._coalesceGapChain(gap);
-            expect(coalescedGap).toEqual({ firstKey: '0000', lastKey: '1000', weight: 10000 });
-        });
-
-        it('should coalesce a single-key gap', async () => {
-            const singleKeyGapSet = GapSet.createFromArray([
-                { firstKey: '0000', lastKey: '0000', weight: 1 },
-            ], 100);
-            const gap = { firstKey: '0000', lastKey: '0000', weight: 1 };
-            const coalescedGap = await singleKeyGapSet._coalesceGapChain(gap);
-            expect(coalescedGap).toEqual({ firstKey: '0000', lastKey: '0000', weight: 1 });
-        });
-
-        it('should coalesce a chain of two gaps ending with a single-key gap', async () => {
-            const singleKeyGapSet = GapSet.createFromArray([
-                { firstKey: '0000', lastKey: '0003', weight: 9 },
-                { firstKey: '0003', lastKey: '0003', weight: 1 },
-            ], 100);
-            const gap = { firstKey: '0000', lastKey: '0003', weight: 9 };
-            const coalescedGap = await singleKeyGapSet._coalesceGapChain(gap);
-            expect(coalescedGap).toEqual({ firstKey: '0000', lastKey: '0003', weight: 9 });
-        });
-    });
-
-    describe('GapSet::lookupGap()', () => {
-        afterEach(() => {
-            // check that the gap sets were not modified by the operation
-            expect(gapSet.toArray()).toEqual(INITIAL_GAPSET);
-            expect(gapSetWithChain.toArray()).toEqual(INITIAL_GAPSET_WITH_CHAIN);
-        });
-
-        it('should return null with empty cache', async () => {
-            const emptyGapSet = new GapSet(100);
-            const gap = await emptyGapSet.lookupGap('cat', 'dog');
-            expect(gap).toBeNull();
-        });
-
-        it('should return null if no gap overlaps [minKey, maxKey]', async () => {
-            const gap = await gapSet.lookupGap('cat', 'dog');
-            expect(gap).toBeNull();
-        });
-
-        it('should return the first gap that overlaps if all gaps overlap', async () => {
-            const gap = await gapSet.lookupGap('ape', 'zoo');
-            expect(gap).toEqual({ firstKey: 'bar', lastKey: 'baz', weight: 10 });
-        });
-
-        it('should return an existing gap that contains [minKey, maxKey]', async () => {
-            const gap1 = await gapSet.lookupGap('bat', 'bay');
-            expect(gap1).toEqual({ firstKey: 'bar', lastKey: 'baz', weight: 10 });
-            const gap2 = await gapSet.lookupGap('quxxx', 'quy');
-            expect(gap2).toEqual({ firstKey: 'qux', lastKey: 'quz', weight: 20 });
-        });
-
-        it('should return an existing gap that overlaps with minKey but not maxKey', async () => {
-            const gap = await gapSet.lookupGap('ape', 'bat');
-            expect(gap).toEqual({ firstKey: 'bar', lastKey: 'baz', weight: 10 });
-        });
-
-        it('should return an existing gap that overlaps just with minKey when no maxKey is provided',
-        async () => {
-            const gap = await gapSet.lookupGap('ape');
-            expect(gap).toEqual({ firstKey: 'bar', lastKey: 'baz', weight: 10 });
-        });
-
-        it('should return an existing gap that overlaps with maxKey but not minKey', async () => {
-            const gap = await gapSet.lookupGap('bat', 'cat');
-            expect(gap).toEqual({ firstKey: 'bar', lastKey: 'baz', weight: 10 });
-        });
-
-        it('should return an existing gap that is contained in [minKey, maxKey] strictly', async () => {
-            const gap = await gapSet.lookupGap('dog', 'rat');
-            expect(gap).toEqual({ firstKey: 'qux', lastKey: 'quz', weight: 20 });
-        });
-
-        it('should return a coalesced gap from chained gaps that fully overlaps [minKey, maxKey]', async () => {
-            const gap = await gapSetWithChain.lookupGap('bat', 'zoo');
-            expect(gap).toEqual({ firstKey: 'bar', lastKey: 'yak', weight: 100 });
-        });
-
-        it('should return a coalesced gap from chained gaps that contain [minKey, maxKey] strictly',
-        async () => {
-            const gap = await gapSetWithChain.lookupGap('bog', 'dog');
-            expect(gap).toEqual({ firstKey: 'baz', lastKey: 'yak', weight: 90 });
-        });
-    });
-});

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

@@ -727,7 +727,7 @@ function getTestListing(mdParams, data, vFormat) {
                 });
             }
             assert.strictEqual(delimiter.skipping(),
-                `${vFormat === 'v1' ? DbPrefixes.Master : ''}foo0`);
+                `${vFormat === 'v1' ? DbPrefixes.Master : ''}foo/`);
         });
 
         tests.forEach(test => {

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

@@ -2,12 +2,8 @@
 
 const assert = require('assert');
 
-import {
+const DelimiterMaster =
-    DelimiterMaster,
+    require('../../../../lib/algos/list/delimiterMaster').DelimiterMaster;
-    DelimiterMasterFilterStateId,
-    GapCachingState,
-    GapBuildingState,
-} from '../../../../lib/algos/list/delimiterMaster';
 const {
     FILTER_ACCEPT,
     FILTER_SKIP,
@@ -15,8 +11,6 @@ const {
     SKIP_NONE,
     inc,
 } = require('../../../../lib/algos/list/tools');
-import { default as GapSet, GapSetEntry } from '../../../../lib/algos/cache/GapSet';
-import { GapCacheInterface } from '../../../../lib/algos/cache/GapCache';
 const VSConst =
     require('../../../../lib/versioning/constants').VersioningConstants;
 const Version = require('../../../../lib/versioning/Version').Version;
@@ -190,7 +184,7 @@ function getListingKey(key, vFormat) {
         });
 
         if (vFormat === 'v0') {
-            it('skipping() should return <key>inc(<VersionIdSeparator>) for DelimiterMaster when ' +
+            it('should return <key><VersionIdSeparator> for DelimiterMaster when ' +
             'NextMarker is set and there is a delimiter', () => {
                 const key = 'key';
                 const delimiter = new DelimiterMaster(
@@ -201,10 +195,14 @@ function getListingKey(key, vFormat) {
                 const listingKey = getListingKey(key, vFormat);
                 delimiter.filter({ key: listingKey, value: '' });
                 assert.strictEqual(delimiter.nextMarker, key);
-                assert.strictEqual(delimiter.skipping(), `${listingKey}${inc(VID_SEP)}`);
+
+                /* With a delimiter skipping should return previous key + VID_SEP
+                 * (except when a delimiter is set and the NextMarker ends with the
+                 * delimiter) . */
+                assert.strictEqual(delimiter.skipping(), listingKey + VID_SEP);
             });
 
-            it('skipping() should return <key>inc(<VersionIdSeparator>) for DelimiterMaster when ' +
+            it('should return <key><VersionIdSeparator> for DelimiterMaster when ' +
             'NextContinuationToken is set and there is a delimiter', () => {
                 const key = 'key';
                 const delimiter = new DelimiterMaster(
@@ -216,7 +214,7 @@ function getListingKey(key, vFormat) {
                 delimiter.filter({ key: listingKey, value: '' });
                 assert.strictEqual(delimiter.nextMarker, key);
 
-                assert.strictEqual(delimiter.skipping(), `${listingKey}${inc(VID_SEP)}`);
+                assert.strictEqual(delimiter.skipping(), listingKey + VID_SEP);
             });
 
             it('should accept a PHD version as first input', () => {
@@ -447,7 +445,7 @@ function getListingKey(key, vFormat) {
                         }),
                         FILTER_SKIP);
                     // ...it should skip the whole replay prefix
-                    assert.strictEqual(delimiter.skipping(), inc(DbPrefixes.Replay));
+                    assert.strictEqual(delimiter.skipping(), DbPrefixes.Replay);
 
                     // simulate a listing that reaches regular object keys
                     // beyond the replay prefix, ...
@@ -462,27 +460,8 @@ function getListingKey(key, vFormat) {
                     // as usual
                     assert.strictEqual(delimiter.skipping(),
                         delimiterChar ?
-                            `${inc(DbPrefixes.Replay)}foo0` :
+                            `${inc(DbPrefixes.Replay)}foo/` :
-                            `${inc(DbPrefixes.Replay)}foo/bar${inc(VID_SEP)}`);
+                            `${inc(DbPrefixes.Replay)}foo/bar${VID_SEP}`);
-                });
-            });
-
-            it('should not crash if key contains "undefined" with no delimiter', () => {
-                const delimiter = new DelimiterMaster({}, fakeLogger, vFormat);
-                const listingKey = getListingKey('undefinedfoo', vFormat);
-                assert.strictEqual(
-                    delimiter.filter({
-                        key: listingKey,
-                        value: '{}',
-                    }),
-                    FILTER_ACCEPT);
-
-                assert.deepStrictEqual(delimiter.result(), {
-                    CommonPrefixes: [],
-                    Contents: [{ key: 'undefinedfoo', value: '{}' }],
-                    IsTruncated: false,
-                    NextMarker: undefined,
-                    Delimiter: undefined,
                 });
             });
         }
@@ -508,12 +487,12 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                     key: `foo/deleted${VID_SEP}v1`,
                     isDeleteMarker: true,
                     res: FILTER_SKIP,
-                    skipping: `foo/deleted${inc(VID_SEP)}`,
+                    skipping: `foo/deleted${VID_SEP}`,
                 },
                 {
                     key: `foo/deleted${VID_SEP}v2`,
                     res: FILTER_SKIP,
-                    skipping: `foo/deleted${inc(VID_SEP)}`,
+                    skipping: `foo/deleted${VID_SEP}`,
                 },
                 {
                     key: 'foo/notdeleted',
@@ -522,7 +501,7 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                 {
                     key: `foo/notdeleted${VID_SEP}v1`,
                     res: FILTER_SKIP,
-                    skipping: `foo/notdeleted${inc(VID_SEP)}`,
+                    skipping: `foo/notdeleted${VID_SEP}`,
                 },
                 {
                     key: 'foo/subprefix/key-1',
@@ -531,7 +510,7 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                 {
                     key: `foo/subprefix/key-1${VID_SEP}v1`,
                     res: FILTER_SKIP,
-                    skipping: `foo/subprefix/key-1${inc(VID_SEP)}`,
+                    skipping: `foo/subprefix/key-1${VID_SEP}`,
                 },
             ],
             result: {
@@ -562,7 +541,7 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                     key: `foo/01${VID_SEP}v1`,
                     isDeleteMarker: true,
                     res: FILTER_SKIP, // versions get skipped after master
-                    skipping: `foo/01${inc(VID_SEP)}`,
+                    skipping: `foo/01${VID_SEP}`,
                 },
                 {
                     key: 'foo/02',
@@ -573,7 +552,7 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                     key: `foo/02${VID_SEP}v1`,
                     isDeleteMarker: true,
                     res: FILTER_SKIP,
-                    skipping: `foo/02${inc(VID_SEP)}`,
+                    skipping: `foo/02${VID_SEP}`,
                 },
                 {
                     key: 'foo/03',
@@ -582,7 +561,7 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                 {
                     key: `foo/03${VID_SEP}v1`,
                     res: FILTER_SKIP,
-                    skipping: `foo/03${inc(VID_SEP)}`,
+                    skipping: `foo/03${VID_SEP}`,
                 },
             ],
             result: {
@@ -612,7 +591,7 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                     key: `foo/bar/01${VID_SEP}v1`,
                     isDeleteMarker: true,
                     res: FILTER_SKIP, // versions get skipped after master
-                    skipping: `foo/bar/01${inc(VID_SEP)}`,
+                    skipping: `foo/bar/01${VID_SEP}`,
                 },
                 {
                     key: 'foo/bar/02',
@@ -623,12 +602,12 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                     key: `foo/bar/02${VID_SEP}v1`,
                     isDeleteMarker: true,
                     res: FILTER_SKIP,
-                    skipping: `foo/bar/02${inc(VID_SEP)}`,
+                    skipping: `foo/bar/02${VID_SEP}`,
                 },
                 {
                     key: `foo/bar/02${VID_SEP}v2`,
                     res: FILTER_SKIP,
-                    skipping: `foo/bar/02${inc(VID_SEP)}`,
+                    skipping: `foo/bar/02${VID_SEP}`,
                 },
                 {
                     key: 'foo/bar/03',
@@ -638,19 +617,19 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                     key: `foo/bar/03${VID_SEP}v1`,
                     res: FILTER_SKIP,
                     // from now on, skip the 'foo/bar/' prefix because we have already seen it
-                    skipping: 'foo/bar0',
+                    skipping: 'foo/bar/',
                 },
                 {
                     key: 'foo/bar/04',
                     isDeleteMarker: true,
                     res: FILTER_SKIP,
-                    skipping: 'foo/bar0',
+                    skipping: 'foo/bar/',
                 },
                 {
                     key: `foo/bar/04${VID_SEP}v1`,
                     isDeleteMarker: true,
                     res: FILTER_SKIP,
-                    skipping: 'foo/bar0',
+                    skipping: 'foo/bar/',
                 },
                 {
                     key: 'foo/baz/01',
@@ -660,7 +639,7 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                     key: `foo/baz/01${VID_SEP}v1`,
                     res: FILTER_SKIP,
                     // skip the 'foo/baz/' prefix because we have already seen it
-                    skipping: 'foo/baz0',
+                    skipping: 'foo/baz/',
                 },
             ],
             result: {
@@ -689,7 +668,7 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                 {
                     key: `foo/${VID_SEP}v1`,
                     res: FILTER_SKIP,
-                    skipping: `foo/${inc(VID_SEP)}`,
+                    skipping: `foo/${VID_SEP}`,
                 },
                 {
                     key: 'foo/deleted',
@@ -700,12 +679,12 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                     key: `foo/deleted${VID_SEP}v1`,
                     isDeleteMarker: true,
                     res: FILTER_SKIP,
-                    skipping: `foo/deleted${inc(VID_SEP)}`,
+                    skipping: `foo/deleted${VID_SEP}`,
                 },
                 {
                     key: `foo/deleted${VID_SEP}v2`,
                     res: FILTER_SKIP,
-                    skipping: `foo/deleted${inc(VID_SEP)}`,
+                    skipping: `foo/deleted${VID_SEP}`,
                 },
                 {
                     key: 'foo/notdeleted',
@@ -714,7 +693,7 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                 {
                     key: `foo/notdeleted${VID_SEP}v1`,
                     res: FILTER_SKIP,
-                    skipping: `foo/notdeleted${inc(VID_SEP)}`,
+                    skipping: `foo/notdeleted${VID_SEP}`,
                 },
                 {
                     key: 'foo/subprefix/key-1',
@@ -723,17 +702,17 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                 {
                     key: `foo/subprefix/key-1${VID_SEP}v1`,
                     res: FILTER_SKIP,
-                    skipping: 'foo/subprefix0',
+                    skipping: 'foo/subprefix/',
                 },
                 {
                     key: 'foo/subprefix/key-2',
                     res: FILTER_SKIP,
-                    skipping: 'foo/subprefix0',
+                    skipping: 'foo/subprefix/',
                 },
                 {
                     key: `foo/subprefix/key-2${VID_SEP}v1`,
                     res: FILTER_SKIP,
-                    skipping: 'foo/subprefix0',
+                    skipping: 'foo/subprefix/',
                 },
             ],
             result: {
@@ -764,7 +743,7 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                 {
                     key: `foo${VID_SEP}v1`,
                     res: FILTER_SKIP,
-                    skipping: `foo${inc(VID_SEP)}`,
+                    skipping: `foo${VID_SEP}`,
                 },
                 {
                     key: 'foo/deleted',
@@ -775,12 +754,12 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                     key: `foo/deleted${VID_SEP}v1`,
                     isDeleteMarker: true,
                     res: FILTER_SKIP,
-                    skipping: `foo/deleted${inc(VID_SEP)}`,
+                    skipping: `foo/deleted${VID_SEP}`,
                 },
                 {
                     key: `foo/deleted${VID_SEP}v2`,
                     res: FILTER_SKIP,
-                    skipping: `foo/deleted${inc(VID_SEP)}`,
+                    skipping: `foo/deleted${VID_SEP}`,
                 },
                 {
                     key: 'foo/notdeleted',
@@ -789,17 +768,17 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                 {
                     key: `foo/notdeleted${VID_SEP}v1`,
                     res: FILTER_SKIP,
-                    skipping: 'foo0',
+                    skipping: 'foo/',
                 },
                 {
                     key: 'foo/subprefix/key-1',
                     res: FILTER_SKIP,
-                    skipping: 'foo0',
+                    skipping: 'foo/',
                 },
                 {
                     key: `foo/subprefix/key-1${VID_SEP}v1`,
                     res: FILTER_SKIP,
-                    skipping: 'foo0',
+                    skipping: 'foo/',
                 },
             ],
             result: {
@@ -831,7 +810,7 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                     key: `foo/${VID_SEP}v1`,
                     isDeleteMarker: true,
                     res: FILTER_SKIP,
-                    skipping: `foo/${inc(VID_SEP)}`,
+                    skipping: `foo/${VID_SEP}`,
                 },
                 {
                     key: 'foo/subprefix',
@@ -844,7 +823,7 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                 {
                     key: 'foo/subprefix/02',
                     res: FILTER_SKIP,
-                    skipping: 'foo/subprefix0', // already added to common prefix
+                    skipping: 'foo/subprefix/', // already added to common prefix
                 },
             ],
             result: {
@@ -879,7 +858,7 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                 {
                     key: `foo/01${VID_SEP}v2`,
                     res: FILTER_SKIP,
-                    skipping: `foo/01${inc(VID_SEP)}`,
+                    skipping: `foo/01${VID_SEP}`,
                 },
                 {
                     key: 'foo/02',
@@ -890,12 +869,12 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                     key: `foo/02${VID_SEP}v1`,
                     isDeleteMarker: true,
                     res: FILTER_SKIP,
-                    skipping: `foo/02${inc(VID_SEP)}`,
+                    skipping: `foo/02${VID_SEP}`,
                 },
                 {
                     key: `foo/02${VID_SEP}v2`,
                     res: FILTER_SKIP,
-                    skipping: `foo/02${inc(VID_SEP)}`,
+                    skipping: `foo/02${VID_SEP}`,
                 },
             ],
             result: {
@@ -970,7 +949,7 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                 {
                     key: `${DbPrefixes.Master}foo/subprefix/key-2`,
                     res: FILTER_SKIP,
-                    skipping: `${DbPrefixes.Master}foo/subprefix0`,
+                    skipping: `${DbPrefixes.Master}foo/subprefix/`,
                 },
             ],
             result: {
@@ -1005,7 +984,7 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
                 {
                     key: `${DbPrefixes.Master}foo/subprefix/key-1`,
                     res: FILTER_SKIP,
-                    skipping: `${DbPrefixes.Master}foo0`,
+                    skipping: `${DbPrefixes.Master}foo/`,
                 },
             ],
             result: {
@@ -1025,7 +1004,7 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
         it(`vFormat=${testCase.vFormat}: ${testCase.desc}`, () => {
             const delimiter = new DelimiterMaster(testCase.params, fakeLogger, testCase.vFormat);
             const resultEntries = testCase.entries.map(testEntry => {
-                const entry: any = {
+                const entry = {
                     key: testEntry.key,
                 };
                 if (testEntry.isDeleteMarker) {
@@ -1049,567 +1028,3 @@ describe('DelimiterMaster listing algorithm: sequence of filter() scenarii', ()
         });
     });
 });
-
-/**
- * Test class that provides a GapCache-compatible interface via a
- * GapSet implementation, i.e. without introducing a delay to expose
- * gaps like the GapCache class does, so tests can check more easily
- * which gaps have been updated.
- */
-class GapCacheAsSet extends GapSet implements GapCacheInterface {
-    exposureDelayMs: number;
-
-    constructor(maxGapWeight: number) {
-        super(maxGapWeight);
-        this.exposureDelayMs = 1000;
-    }
-
-    static createFromArray(gaps: GapSetEntry[], maxWeight: number): GapCacheAsSet {
-        const gs = new GapCacheAsSet(maxWeight);
-        for (const gap of gaps) {
-            gs._gaps.insert(gap);
-        }
-        return gs;
-    }
-
-    get maxGapWeight(): number {
-        return super.maxWeight;
-    }
-}
-
-type FilterEntriesResumeState = {
-    i: number,
-    version: number,
-};
-
-/**
- * Convenience test helper to build listing entries and pass them to
- * the DelimiterMaster.filter() function in order, and checks the
- * return code. It is also useful to check the state of the gap cache
- * afterwards.
- *
- * The first object key is "pre/0001" and is incremented on each master key.
- *
- * The current object version is "v100" and the version is then incremented
- * for each noncurrent version ("v101" etc.).
- *
- * @param {DelimiterMaster} listing - listing algorithm instance
- * @param {string} pattern - pattern of keys to create:
- *   - an upper-case letter is a master key
- *   - a lower-case letter is a version key
- *   - a 'd' (or 'D') letter is a delete marker
- *   - any other letter (e.g. 'v' or 'V') is a regular version
- *   - space characters ' ' are allowed and must be matched by
- *     a space character at the same position in 'expectedCodes'
-
- * @param {string} expectedCodes - string of expected codes from filter()
- * matching each entry from 'pattern':
- *   - 'a' stands for FILTER_ACCEPT
- *   - 's' stands for FILTER_SKIP
- *   - 'e' stands for FILTER_END
- *   - ' ' must be matched by a space character in 'pattern'
- * @return {FilterEntriesResumeState} - a state that can be passed in
- * the next call as 'resumeFromState' to resume filtering the next
- * keys
- */
-function filterEntries(
-    listing: DelimiterMaster,
-    pattern: string,
-    expectedCodes: string,
-    resumeFromState?: FilterEntriesResumeState,
-): FilterEntriesResumeState {
-    const ExpectedCodeMap: string[] = [];
-    ExpectedCodeMap[FILTER_ACCEPT] = 'a';
-    ExpectedCodeMap[FILTER_SKIP] = 's';
-    ExpectedCodeMap[FILTER_END] = 'e';
-    let { i, version } = resumeFromState || { i: 0, version: 100 };
-    const obtainedCodes = pattern.split('').map(p => {
-        if (p === ' ') {
-            return ' ';
-        }
-        if (p.toUpperCase() === p) {
-            // master key
-            i += 1;
-            version = 100;
-        }
-        const keyId = `0000${i}`.slice(-4);
-        const key = `pre/${keyId}`;
-        const md: any = ('Dd'.includes(p)) ? { isDeleteMarker: true } : {};
-        md.versionId = `v${version}`;
-        const value = JSON.stringify(md);
-        const entry = (p.toUpperCase() === p) ? { key, value } : { key: `${key}\0v${version}`, value };
-        const ret = listing.filter(entry);
-        if (p.toLowerCase() === p) {
-            // version key
-            version += 1;
-        }
-        return ExpectedCodeMap[<number> <unknown> ret];
-    }).join('');
-    expect(obtainedCodes).toEqual(expectedCodes);
-
-    return { i, version };
-}
-
-describe('DelimiterMaster listing algorithm: gap caching and lookup', () => {
-    it('should not cache a gap of weight smaller than minGapWeight', () => {
-        const listing = new DelimiterMaster({}, fakeLogger, 'v0');
-        const gapCache = new GapCacheAsSet(100);
-        listing.refreshGapCache(gapCache, 7); // minGapWeight=7
-
-        filterEntries(listing, 'Vv Ddv Ddv Vv Ddv', 'as ass ass as ass');
-        expect(gapCache.toArray()).toEqual([]);
-    });
-
-    it('should cache a gap of weight equal to minGapWeight', () => {
-        const listing = new DelimiterMaster({}, fakeLogger, 'v0');
-        const gapCache = new GapCacheAsSet(100);
-        listing.refreshGapCache(gapCache, 9); // minGapWeight=9
-
-        filterEntries(listing, 'Vv Ddv Ddv Ddv Vv Ddv', 'as ass ass ass as ass');
-        expect(gapCache.toArray()).toEqual([
-            { firstKey: 'pre/0002', lastKey: `pre/0004${VID_SEP}v101`, weight: 9 },
-        ]);
-    });
-
-    it('should cache a gap of weight equal to maxWeight in a single gap', () => {
-        const listing = new DelimiterMaster({}, fakeLogger, 'v0');
-        const gapCache = new GapCacheAsSet(13); // maxWeight=13
-        listing.refreshGapCache(gapCache, 5); // minGapWeight=5
-
-        filterEntries(listing, 'Vv Ddv Ddvv Ddv Ddv Vv Ddv', 'as ass asss ass ass as ass');
-        expect(gapCache.toArray()).toEqual([
-            { firstKey: 'pre/0002', lastKey: `pre/0005${VID_SEP}v101`, weight: 13 },
-        ]);
-    });
-
-    it('should not cache a gap if listing has been running for more than exposureDelayMs',
-    async () => {
-        const listing = new DelimiterMaster({}, fakeLogger, 'v0');
-        const gapsArray = [
-            { firstKey: 'pre/0006', lastKey: `pre/0007${VID_SEP}v100`, weight: 6 },
-        ];
-        const gapCache = GapCacheAsSet.createFromArray(JSON.parse(
-            JSON.stringify(gapsArray)
-        ), 100);
-        listing.refreshGapCache(gapCache, 1, 1);
-
-        let resumeFromState = filterEntries(listing, 'Vv', 'as');
-        let validityPeriod = listing.getGapBuildingValidityPeriodMs();
-        expect(validityPeriod).toBeGreaterThan(gapCache.exposureDelayMs - 10);
-        expect(validityPeriod).toBeLessThan(gapCache.exposureDelayMs + 10);
-
-        await new Promise(resolve => setTimeout(resolve, gapCache.exposureDelayMs + 10));
-        validityPeriod = listing.getGapBuildingValidityPeriodMs();
-        expect(validityPeriod).toEqual(0);
-        resumeFromState = filterEntries(listing, 'Ddv Ddv Ddv Vvv', 'ass ass ass ass',
-                                        resumeFromState);
-        expect(gapCache.toArray()).toEqual(gapsArray);
-        // gap building should be in expired state
-        expect(listing._gapBuilding.state).toEqual(GapBuildingState.Expired);
-        // remaining validity period should still be 0 because gap building has expired
-        validityPeriod = listing.getGapBuildingValidityPeriodMs();
-        expect(validityPeriod).toEqual(0);
-
-        // we should still be able to skip over the existing cached gaps
-        expect(listing._gapCaching.state).toEqual(GapCachingState.GapLookupInProgress);
-        await new Promise(resolve => setTimeout(resolve, 1));
-        expect(listing._gapCaching.state).toEqual(GapCachingState.GapCached);
-        filterEntries(listing, 'Ddv Ddv Ddv', 'sss sss ass', resumeFromState);
-    });
-
-    [1, 3, 5, 10].forEach(triggerSaveGapWeight => {
-        it('should cache a gap of weight maxWeight + 1 in two chained gaps ' +
-        `(triggerSaveGapWeight=${triggerSaveGapWeight})`, () => {
-            const listing = new DelimiterMaster({}, fakeLogger, 'v0');
-            const gapCache = new GapCacheAsSet(12); // maxWeight=12
-            listing.refreshGapCache(gapCache, 5, triggerSaveGapWeight);
-
-            filterEntries(listing, 'Vv Ddv Ddvv Ddv Ddv Vv Ddv', 'as ass asss ass ass as ass');
-            if (triggerSaveGapWeight === 1) {
-                // trigger=1 guarantees that the weight of split gaps is maximized
-                expect(gapCache.toArray()).toEqual([
-                    { firstKey: 'pre/0002', lastKey: `pre/0005${VID_SEP}v100`, weight: 12 },
-                    { firstKey: `pre/0005${VID_SEP}v100`, lastKey: `pre/0005${VID_SEP}v101`, weight: 1 },
-                ]);
-            } else if (triggerSaveGapWeight === 3) {
-                // - the first trigger happens after 'minGapWeight' listing entries, so 5
-                // - the second and third triggers happen after 'triggerSaveGapWeight' listing
-                //   entries, so 3 then 3 - same gap because 5+3+3=11 and 11 <= 12 (maxWeight)
-                // - finally, 2 more entries to complete the gap, at which point the
-                //   entry is split, hence we get two entries weights 11 and 2 respectively.
-                expect(gapCache.toArray()).toEqual([
-                    { firstKey: 'pre/0002', lastKey: 'pre/0005', weight: 11 },
-                    { firstKey: 'pre/0005', lastKey: `pre/0005${VID_SEP}v101`, weight: 2 },
-                ]);
-            } else {
-                // trigger=5|10
-                expect(gapCache.toArray()).toEqual([
-                    { firstKey: 'pre/0002', lastKey: `pre/0004${VID_SEP}v101`, weight: 10 },
-                    { firstKey: `pre/0004${VID_SEP}v101`, lastKey: `pre/0005${VID_SEP}v101`, weight: 3 },
-                ]);
-            }
-        });
-    });
-
-    [1, 2, 3].forEach(triggerSaveGapWeight => {
-        it('should cache a gap of weight more than twice maxWeight in as many chained gaps ' +
-        `as needed (triggerSaveGapWeight=${triggerSaveGapWeight})`, () => {
-            const listing = new DelimiterMaster({}, fakeLogger, 'v0');
-            const gapCache = new GapCacheAsSet(5); // maxWeight=5
-            // minGapWeight=4 prevents the last gap starting at "0008" from being cached
-            listing.refreshGapCache(gapCache, 4, triggerSaveGapWeight);
-
-            filterEntries(listing, 'Vv Ddv Ddvv Ddv Ddv Ddv Vv Ddv', 'as ass asss ass ass ass as ass');
-            // the slight differences in weight between different values of
-            // 'triggerSaveGapWeight' are due to the combination of the trigger
-            // frequency and the 'minGapWeight' value (3), but in all cases a
-            // reasonable splitting job should be obtained.
-            //
-            // NOTE: in practice, the default trigger is half the maximum weight, any value
-            // equal or lower should yield gap weights close enough to the maximum allowed.
-            if (triggerSaveGapWeight === 1) {
-                // a trigger at every key guarantees gaps to maximize their weight
-                expect(gapCache.toArray()).toEqual([
-                    { firstKey: 'pre/0002', lastKey: `pre/0003${VID_SEP}v100`, weight: 5 },
-                    { firstKey: `pre/0003${VID_SEP}v100`, lastKey: `pre/0004${VID_SEP}v101`, weight: 5 },
-                    { firstKey: `pre/0004${VID_SEP}v101`, lastKey: `pre/0006${VID_SEP}v100`, weight: 5 },
-                    { firstKey: `pre/0006${VID_SEP}v100`, lastKey: `pre/0006${VID_SEP}v101`, weight: 1 },
-                ]);
-            } else if (triggerSaveGapWeight === 2) {
-                expect(gapCache.toArray()).toEqual([
-                    { firstKey: 'pre/0002', lastKey: 'pre/0003', weight: 4 },
-                    { firstKey: 'pre/0003', lastKey: 'pre/0004', weight: 4 },
-                    { firstKey: 'pre/0004', lastKey: `pre/0005${VID_SEP}v100`, weight: 4 },
-                    { firstKey: `pre/0005${VID_SEP}v100`, lastKey: `pre/0006${VID_SEP}v101`, weight: 4 },
-                ]);
-            } else {
-                // trigger=3
-                expect(gapCache.toArray()).toEqual([
-                    { firstKey: 'pre/0002', lastKey: 'pre/0003', weight: 4 },
-                    { firstKey: 'pre/0003', lastKey: `pre/0003${VID_SEP}v102`, weight: 3 },
-                    { firstKey: `pre/0003${VID_SEP}v102`, lastKey: `pre/0004${VID_SEP}v101`, weight: 3 },
-                    { firstKey: `pre/0004${VID_SEP}v101`, lastKey: `pre/0005${VID_SEP}v101`, weight: 3 },
-                    { firstKey: `pre/0005${VID_SEP}v101`, lastKey: `pre/0006${VID_SEP}v101`, weight: 3 },
-                ]);
-            }
-        });
-    });
-
-    it('should cut the current gap when seeing a non-deleted object, and start a new ' +
-    'gap on the next deleted object', () => {
-        const listing = new DelimiterMaster({}, fakeLogger, 'v0');
-        const gapCache = new GapCacheAsSet(100);
-        listing.refreshGapCache(gapCache, 2); // minGapWeight=2
-
-        filterEntries(listing, 'Vv Ddv Vv Ddv Vv', 'as ass as ass as');
-        expect(gapCache.toArray()).toEqual([
-            { firstKey: 'pre/0002', lastKey: `pre/0002${VID_SEP}v101`, weight: 3 },
-            { firstKey: 'pre/0004', lastKey: `pre/0004${VID_SEP}v101`, weight: 3 },
-        ]);
-    });
-
-    it('should complete the current gap when returning a result', () => {
-        const listing = new DelimiterMaster({}, fakeLogger, 'v0');
-        const gapCache = new GapCacheAsSet(100);
-        listing.refreshGapCache(gapCache, 2); // ensure the gap above minGapWeight=2 gets saved
-
-        filterEntries(listing, 'Vv Ddv Ddv', 'as ass ass');
-        const result = listing.result();
-        expect(result).toEqual({
-            CommonPrefixes: [],
-            Contents: [
-                { key: 'pre/0001', value: '{"versionId":"v100"}' },
-            ],
-            Delimiter: undefined,
-            IsTruncated: false,
-            NextMarker: undefined,
-        });
-        expect(gapCache.toArray()).toEqual([
-            { firstKey: 'pre/0002', lastKey: `pre/0003${VID_SEP}v101`, weight: 6 },
-        ]);
-    });
-
-    it('should refresh the building params when refreshGapCache() is called in NonBuilding state',
-    () => {
-        const listing = new DelimiterMaster({}, fakeLogger, 'v0');
-        const gapCache = new GapCacheAsSet(100);
-        // ensure the first gap with weight=9 gets saved
-        listing.refreshGapCache(gapCache, 9);
-        let resumeFromState = filterEntries(listing, 'Vv', 'as');
-        // refresh with a different value for minGapWeight (12)
-        listing.refreshGapCache(gapCache, 12);
-
-        resumeFromState = filterEntries(listing, 'Ddv Ddv Ddv Vv', 'ass ass ass as',
-                                        resumeFromState);
-        // for the building gap, minGapWeight should have been updated to 12, hence the
-        // gap should not have been created
-        expect(gapCache.toArray()).toEqual([]);
-        filterEntries(listing, 'Ddv Ddv Ddv Ddv Vv', 'ass ass ass ass as', resumeFromState);
-        // there should now be a new gap with weight=12
-        expect(gapCache.toArray()).toEqual([
-            { firstKey: 'pre/0006', lastKey: `pre/0009${VID_SEP}v101`, weight: 12 },
-        ]);
-    });
-
-    it('should save the refreshed building params when refreshGapCache() is called in Building state',
-    () => {
-        const listing = new DelimiterMaster({}, fakeLogger, 'v0');
-        const gapCache = new GapCacheAsSet(100);
-        // ensure the first gap with weight=9 gets saved
-        listing.refreshGapCache(gapCache, 9);
-
-        let resumeFromState = filterEntries(listing, 'Vv Ddv Ddv', 'as ass ass');
-        // refresh with a different value for minGapWeight (12)
-        listing.refreshGapCache(gapCache, 12);
-        resumeFromState = filterEntries(listing, 'Ddv Vv', 'ass as', resumeFromState);
-        // for the building gap, minGapWeight should still be 9, hence the gap should
-        // have been created
-        expect(gapCache.toArray()).toEqual([
-            { firstKey: 'pre/0002', lastKey: `pre/0004${VID_SEP}v101`, weight: 9 },
-        ]);
-        filterEntries(listing, 'Ddv Ddv Ddv Vv', 'ass ass ass as', resumeFromState);
-        // there should still be only one gap because the next gap's weight is 9 and 9 < 12
-        expect(gapCache.toArray()).toEqual([
-            { firstKey: 'pre/0002', lastKey: `pre/0004${VID_SEP}v101`, weight: 9 },
-        ]);
-    });
-
-    it('should not build a new gap when skipping a prefix', () => {
-        const listing = new DelimiterMaster({
-            delimiter: '/',
-        }, fakeLogger, 'v0');
-        const gapCache = new GapCacheAsSet(100);
-        // force immediate creation of gaps with 1, 1
-        listing.refreshGapCache(gapCache, 1, 1);
-
-        // prefix should be skipped, but no new gap should be created
-        filterEntries(listing, 'Vv Ddv Ddv Ddv', 'as sss sss sss');
-        expect(gapCache.toArray()).toEqual([]);
-    });
-
-    it('should trigger gap lookup and continue filtering without skipping when encountering ' +
-    'a delete marker', () => {
-        const listing = new DelimiterMaster({}, fakeLogger, 'v0');
-        const gapsArray = [
-            { firstKey: 'pre/0002', lastKey: `pre/0003${VID_SEP}v100`, weight: 6 },
-        ];
-        const gapCache = GapCacheAsSet.createFromArray(JSON.parse(
-            JSON.stringify(gapsArray)
-        ), 100);
-        listing.refreshGapCache(gapCache);
-
-        let resumeState = filterEntries(listing, 'Vv', 'as');
-        // state should still be UnknownGap since no delete marker has been seen yet
-        expect(listing._gapCaching.state).toEqual(GapCachingState.UnknownGap);
-
-        resumeState = filterEntries(listing, 'D', 'a', resumeState);
-        // since the lookup is asynchronous (Promise-based), it should now be in progress
-        expect(listing._gapCaching.state).toEqual(GapCachingState.GapLookupInProgress);
-
-        filterEntries(listing, 'dv Ddv Vv Ddv', 'ss ass as ass', resumeState);
-        // the lookup should still be in progress
-        expect(listing._gapCaching.state).toEqual(GapCachingState.GapLookupInProgress);
-
-        // the gap cache shouldn't have been updated
-        expect(gapCache.toArray()).toEqual(gapsArray);
-    });
-
-    it('should cache a gap after lookup completes, and use it to skip over keys ' +
-    'within the gap range', async () => {
-        const listing = new DelimiterMaster({}, fakeLogger, 'v0');
-        const gapsArray = [
-            { firstKey: 'pre/0002', lastKey: `pre/0006${VID_SEP}v101`, weight: 14 },
-        ];
-        const gapCache = GapCacheAsSet.createFromArray(JSON.parse(
-            JSON.stringify(gapsArray)
-        ), 100);
-        listing.refreshGapCache(gapCache);
-
-        let resumeState = filterEntries(listing, 'Vv D', 'as a');
-        // since the lookup is asynchronous (Promise-based), it should now be in progress
-        expect(listing._gapCaching.state).toEqual(GapCachingState.GapLookupInProgress);
-        expect(listing.state.id).toEqual(DelimiterMasterFilterStateId.SkippingVersionsV0);
-        // wait until the lookup completes (should happen in the next
-        // event loop iteration so always quicker than a non-immediate timer)
-        await new Promise(resolve => setTimeout(resolve, 1));
-
-        // the lookup should have completed now and the next gap should be cached
-        expect(listing._gapCaching.state).toEqual(GapCachingState.GapCached);
-        expect(listing.state.id).toEqual(DelimiterMasterFilterStateId.SkippingVersionsV0);
-
-        // the state should stay in SkippingVersionsV0 until filter() is called with
-        // a new master delete marker
-        resumeState = filterEntries(listing, 'dvvv', 'ssss', resumeState);
-        expect(listing.state.id).toEqual(DelimiterMasterFilterStateId.SkippingVersionsV0);
-
-        // here comes the next master delete marker, it should be skipped as it is still within
-        // the cached gap's range (its key is "0003" and version "v100")
-        resumeState = filterEntries(listing, 'D', 's', resumeState);
-        // the listing algorithm should now be actively skipping the gap
-        expect(listing.state.id).toEqual(DelimiterMasterFilterStateId.SkippingGapV0);
-
-        // the skipping() function should return the gap's last key.
-        // NOTE: returning a key to jump to that is the actual gap's last key
-        // (instead of a key just after) allows the listing algorithm to build
-        // a chained gap when the database listing is restarted from that point
-        // and there are more delete markers to skip.
-        expect(listing.skipping()).toEqual(`pre/0006${VID_SEP}v101`);
-
-        // - The next master delete markers with key "0004" and "0005" are still within the
-        //   gap's range, so filter() should return FILTER_SKIP ('s')
-        //
-        // - Master key "0006" is NOT a delete marker, although this means that the update
-        //   happened after the gap was looked up and the listing is allowed to skip it as
-        //   well (it actually doesn't even check so doesn't know what type of key it is).
-        //
-        // - The following master delete marker "0007" is past the gap so returns
-        //   FILTER_ACCEPT ('a') and should have triggered a new cache lookup, and
-        //   the listing state should have been switched back to SkippingVersionsV0.
-        resumeState = filterEntries(listing, 'dv Ddv Ddv Vvvv Ddv', 'ss sss sss ssss ass',
-                                    resumeState);
-        expect(listing._gapCaching.state).toEqual(GapCachingState.GapLookupInProgress);
-        expect(listing.state.id).toEqual(DelimiterMasterFilterStateId.SkippingVersionsV0);
-
-        // the gap cache must not have been updated in the process
-        expect(gapCache.toArray()).toEqual(gapsArray);
-    });
-
-    it('should extend a cached gap forward if current delete markers are listed beyond',
-    async () => {
-        const listing = new DelimiterMaster({}, fakeLogger, 'v0');
-        const gapsArray = [
-            { firstKey: 'pre/0002', lastKey: `pre/0005${VID_SEP}v100`, weight: 12 },
-        ];
-        const gapCache = GapCacheAsSet.createFromArray(JSON.parse(
-            JSON.stringify(gapsArray)
-        ), 100);
-        listing.refreshGapCache(gapCache, 2);
-
-        let resumeState = filterEntries(listing, 'Vv D', 'as a');
-        // wait until the lookup completes (should happen in the next
-        // event loop iteration so always quicker than a non-immediate timer)
-        await new Promise(resolve => setTimeout(resolve, 1));
-
-        // the lookup should have completed now and the next gap should be cached,
-        // continue with filtering
-        resumeState = filterEntries(listing, 'dv Ddv Ddv Ddv Ddv Ddvvv Vv Ddv Vv',
-                                    'ss sss sss sss ass assss as ass as',
-                                    resumeState);
-        // the cached gap should be extended to the last key before the last regular
-        // master version ('V')
-        expect(gapCache.toArray()).toEqual([
-            // this gap has been extended forward up to right before the first non-deleted
-            // current version following the gap, and its weight updated with how many
-            // extra keys are skippable
-            { firstKey: 'pre/0002', lastKey: `pre/0007${VID_SEP}v103`, weight: 21 },
-            // this gap has been created from the next deleted current version
-            { firstKey: 'pre/0009', lastKey: `pre/0009${VID_SEP}v101`, weight: 3 },
-        ]);
-    });
-
-    it('should extend a cached gap backwards if current delete markers are listed ahead, ' +
-    'and forward if more skippable keys are seen', async () => {
-        const listing = new DelimiterMaster({}, fakeLogger, 'v0');
-        const gapsArray = [
-            { firstKey: 'pre/0004', lastKey: `pre/0005${VID_SEP}v100`, weight: 4 },
-        ];
-        const gapCache = GapCacheAsSet.createFromArray(JSON.parse(
-            JSON.stringify(gapsArray)
-        ), 100);
-        listing.refreshGapCache(gapCache, 2);
-
-        let resumeState = filterEntries(listing, 'Vv D', 'as a');
-        // wait until the lookup completes (should happen in the next
-        // event loop iteration so always quicker than a non-immediate timer)
-        await new Promise(resolve => setTimeout(resolve, 1));
-
-        // the lookup should have completed now and the next gap should be cached,
-        // continue with filtering
-        expect(listing._gapCaching.state).toEqual(GapCachingState.GapCached);
-        resumeState = filterEntries(listing, 'dv Ddv Ddv Ddv Vv Ddv Vv',
-                                    'ss ass sss sss as ass as', resumeState);
-        // the cached gap should be extended to the last key before the last regular
-        // master version ('V')
-        expect(gapCache.toArray()).toEqual([
-            // this gap has been extended:
-            // - backwards up to the first listed delete marker
-            // - forward up to the last skippable key
-            // and its weight updated with how many extra keys are skippable
-            { firstKey: 'pre/0002', lastKey: `pre/0005${VID_SEP}v101`, weight: 11 },
-            // this gap has been created from the next deleted current version
-            { firstKey: 'pre/0007', lastKey: `pre/0007${VID_SEP}v101`, weight: 3 },
-        ]);
-    });
-
-    it('should not extend a cached gap forward if extension weight is 0',
-    async () => {
-        const listing = new DelimiterMaster({}, fakeLogger, 'v0');
-        const gapsArray = [
-            { firstKey: 'pre/0002', lastKey: `pre/0005${VID_SEP}v101`, weight: 13 },
-        ];
-        const gapCache = GapCacheAsSet.createFromArray(JSON.parse(
-            JSON.stringify(gapsArray)
-        ), 100);
-        listing.refreshGapCache(gapCache, 2);
-
-        let resumeState = filterEntries(listing, 'Vv D', 'as a');
-        // wait until the lookup completes (should happen in the next
-        // event loop iteration so always quicker than a non-immediate timer)
-        await new Promise(resolve => setTimeout(resolve, 1));
-
-        // the lookup should have completed now and the next gap should
-        // be cached, simulate a concurrent invalidation by removing the
-        // existing gap immediately, then continue with filtering
-        resumeState = filterEntries(listing, 'dv Ddv Ddv Ddv',
-                                    'ss sss sss sss', resumeState);
-        gapCache.removeOverlappingGaps(['pre/0002']);
-        resumeState = filterEntries(listing, 'Vv', 'as', resumeState);
-        // no new gap should have been added
-        expect(gapCache.toArray()).toEqual([]);
-    });
-
-    it('should ignore gap with 0 listed key in it (e.g. due to skipping a prefix)', async () => {
-        const listing = new DelimiterMaster({}, fakeLogger, 'v0');
-        const gapsArray = [
-            { firstKey: 'pre/0004/a', lastKey: 'pre/0004/b', weight: 10 },
-        ];
-        const gapCache = GapCacheAsSet.createFromArray(JSON.parse(
-            JSON.stringify(gapsArray)
-        ), 100);
-        listing.refreshGapCache(gapCache);
-
-        let resumeState = filterEntries(listing, 'Dd Vv Vv', 'as as as');
-        // wait until the lookup completes (should happen in the next
-        // event loop iteration so always quicker than a non-immediate timer)
-        await new Promise(resolve => setTimeout(resolve, 1));
-
-        expect(listing._gapCaching.state).toEqual(GapCachingState.GapCached);
-        expect(gapCache.toArray()).toEqual([
-            { firstKey: 'pre/0004/a', lastKey: 'pre/0004/b', weight: 10 },
-        ]);
-        // "0004" keys are still prior to the gap's first key
-        resumeState = filterEntries(listing, 'Ddv', 'ass', resumeState);
-        expect(listing._gapCaching.state).toEqual(GapCachingState.GapCached);
-
-        // the next delete marker "0005" should trigger a new lookup...
-        resumeState = filterEntries(listing, 'D', 'a', resumeState);
-        expect(listing._gapCaching.state).toEqual(GapCachingState.GapLookupInProgress);
-        await new Promise(resolve => setTimeout(resolve, 1));
-
-        // ...which returns 'null' and sets the state to NoMoreGap
-        expect(listing._gapCaching.state).toEqual(GapCachingState.NoMoreGap);
-        filterEntries(listing, 'dv Vv', 'ss as', resumeState);
-    });
-
-    it('should disable gap fetching and building if using V1 format', async () => {
-        const listing = new DelimiterMaster({}, fakeLogger, 'v1');
-        const gapCache = new GapCacheAsSet(100);
-        listing.refreshGapCache(gapCache);
-
-        expect(listing.getGapBuildingValidityPeriodMs()).toBeNull();
-        expect(listing._gapCaching.state).toEqual(GapCachingState.NoGapCache);
-        // mimic V1 listing of master prefix
-        filterEntries(listing, 'V V', 'a a');
-        expect(listing._gapBuilding.state).toEqual(GapBuildingState.Disabled);
-    });
-});

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

@@ -846,11 +846,11 @@ function getTestListing(mdParams, data, vFormat) {
             }
             if (vFormat === 'v1') {
                 assert.deepStrictEqual(delimiter.skipping(), [
-                    `${DbPrefixes.Master}foo0`,
+                    `${DbPrefixes.Master}foo/`,
-                    `${DbPrefixes.Version}foo0`,
+                    `${DbPrefixes.Version}foo/`,
                 ]);
             } else {
-                assert.strictEqual(delimiter.skipping(), 'foo0');
+                assert.strictEqual(delimiter.skipping(), 'foo/');
             }
         });
 
@@ -871,7 +871,7 @@ function getTestListing(mdParams, data, vFormat) {
                     }),
                     FILTER_SKIP);
                 // ...it should skip the whole replay prefix
-                assert.strictEqual(delimiter.skipping(), inc(DbPrefixes.Replay));
+                assert.strictEqual(delimiter.skipping(), DbPrefixes.Replay);
 
                 // simulate a listing that reaches regular object keys
                 // beyond the replay prefix, ...
@@ -882,7 +882,7 @@ function getTestListing(mdParams, data, vFormat) {
                     }),
                     FILTER_ACCEPT);
                 // ...it should return to skipping by prefix as usual
-                assert.strictEqual(delimiter.skipping(), `${inc(DbPrefixes.Replay)}foo0`);
+                assert.strictEqual(delimiter.skipping(), `${inc(DbPrefixes.Replay)}foo/`);
             });
         }
 
@@ -937,11 +937,11 @@ function getTestListing(mdParams, data, vFormat) {
             assert.strictEqual(delimiter.nextKeyMarker, 'foo/');
 
             if (vFormat === 'v0') {
-                assert.strictEqual(delimiter.skipping(), 'foo0');
+                assert.strictEqual(delimiter.skipping(), 'foo/');
             } else {
                 assert.deepStrictEqual(delimiter.skipping(), [
-                    `${DbPrefixes.Master}foo0`,
+                    `${DbPrefixes.Master}foo/`,
-                    `${DbPrefixes.Version}foo0`,
+                    `${DbPrefixes.Version}foo/`,
                 ]);
             }
         });
@@ -958,11 +958,11 @@ function getTestListing(mdParams, data, vFormat) {
             assert.strictEqual(delimiter.nextKeyMarker, 'foo/');
 
             if (vFormat === 'v0') {
-                assert.strictEqual(delimiter.skipping(), 'foo0');
+                assert.strictEqual(delimiter.skipping(), 'foo/');
             } else {
                 assert.deepStrictEqual(delimiter.skipping(), [
-                    `${DbPrefixes.Master}foo0`,
+                    `${DbPrefixes.Master}foo/`,
-                    `${DbPrefixes.Version}foo0`,
+                    `${DbPrefixes.Version}foo/`,
                 ]);
             }
         });
@@ -1249,11 +1249,11 @@ function getTestListing(mdParams, data, vFormat) {
             }), FILTER_SKIP);
 
             if (vFormat === 'v0') {
-                assert.deepStrictEqual(listing.skipping(), `key${VID_SEP}version3\0`);
+                assert.deepStrictEqual(listing.skipping(), `key${VID_SEP}version3`);
             } else {
                 assert.deepStrictEqual(listing.skipping(), [
-                    `${DbPrefixes.Master}key${VID_SEP}version3\0`,
+                    `${DbPrefixes.Master}key${VID_SEP}version3`,
-                    `${DbPrefixes.Version}key${VID_SEP}version3\0`,
+                    `${DbPrefixes.Version}key${VID_SEP}version3`,
                 ]);
             }
 
@@ -1335,11 +1335,11 @@ function getTestListing(mdParams, data, vFormat) {
             }), FILTER_SKIP);
 
             if (vFormat === 'v0') {
-                assert.deepStrictEqual(listing.skipping(), `key${VID_SEP}version3\0`);
+                assert.deepStrictEqual(listing.skipping(), `key${VID_SEP}version3`);
             } else {
                 assert.deepStrictEqual(listing.skipping(), [
-                    `${DbPrefixes.Master}key${VID_SEP}version3\0`,
+                    `${DbPrefixes.Master}key${VID_SEP}version3`,
-                    `${DbPrefixes.Version}key${VID_SEP}version3\0`,
+                    `${DbPrefixes.Version}key${VID_SEP}version3`,
                 ]);
             }
 

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

@@ -116,7 +116,7 @@ describe('Skip Algorithm', () => {
         // Skipping algo params
         const extension = {
             filter: () => FILTER_SKIP,
-            skipping: () => 'entry1',
+            skipping: () => 'entry0',
         };
         const gte = 'some-other-entry';
         // Setting spy functions
@@ -138,7 +138,7 @@ describe('Skip Algorithm', () => {
         // Skipping algo params
         const extension = {
             filter: () => FILTER_SKIP,
-            skipping: () => ['first-entry-1', 'second-entry-1'],
+            skipping: () => ['first-entry-0', 'second-entry-0'],
         };
         const gte = 'some-other-entry';
         // Setting spy functions
@@ -160,7 +160,7 @@ describe('Skip Algorithm', () => {
         // Skipping algo params
         const extension = {
             filter: () => FILTER_SKIP,
-            skipping: () => 'entry-1',
+            skipping: () => 'entry-0',
         };
         const gte = 'entry-1';
         // Setting spy functions

tests/unit/auth/chainBackend.spec.js

@@ -306,31 +306,6 @@ describe('Auth Backend: Chain Backend', () => {
                 ],
             );
         });
-
-        it('should correctly merge policies with implicit denies and actions', () => {
-            const policyResps = [
-                { message: { body: [
-                    { isAllowed: false, arn: 'arn:aws:s3:::policybucket/true1', action: 'action1', isImplicit: true },
-                    { isAllowed: true, arn: 'arn:aws:s3:::policybucket/true2', action: 'action2', isImplicit: false },
-                    { isAllowed: false, arn: 'arn:aws:s3:::policybucket/false1', action: 'action3', isImplicit: false },
-                ] } },
-                { message: { body: [
-                    { isAllowed: true, arn: 'arn:aws:s3:::policybucket/true1', action: 'action1', isImplicit: false },
-                    { isAllowed: false, arn: 'arn:aws:s3:::policybucket/true2', action: 'action1', isImplicit: true },
-                    { isAllowed: false, arn: 'arn:aws:s3:::policybucket/false2', action: 'action1', isImplicit: true },
-                ] } },
-            ];
-            assert.deepStrictEqual(
-                ChainBackend._mergePolicies(policyResps),
-                [
-                    { isAllowed: true, arn: 'arn:aws:s3:::policybucket/true1', action: 'action1', isImplicit: false },
-                    { isAllowed: true, arn: 'arn:aws:s3:::policybucket/true2', action: 'action2', isImplicit: false },
-                    { isAllowed: false, arn: 'arn:aws:s3:::policybucket/false1', action: 'action3', isImplicit: false },
-                    { isAllowed: false, arn: 'arn:aws:s3:::policybucket/true2', action: 'action1', isImplicit: true },
-                    { isAllowed: false, arn: 'arn:aws:s3:::policybucket/false2', action: 'action1', isImplicit: true },
-                ],
-            );
-        });
     });
 
     describe('::checkhealth', () => {

tests/unit/db.spec.js

@@ -53,21 +53,12 @@ function checkKeyNotExistsInDB(db, key, cb) {
             return cb(err);
         }
         if (value) {
-            return cb(errors.EntityAlreadyExists);
+            return cb(errors.PreconditionFailed);
         }
         return cb();
     });
 }
 
-function checkKeyExistsInDB(db, key, callback) {
-    return db.get(key, err => {
-        if (err) {
-            return callback(err.notFound ? errors.NoSuchEntity : err);
-        }
-        return callback();
-    });
-}
-
 class ConditionalLevelDB {
     constructor() {
         this.db = createDb();
@@ -79,9 +70,6 @@ class ConditionalLevelDB {
             case ('notExists' in cond):
                 checkKeyNotExistsInDB(this.db, cond.notExists, asyncCallback);
                 break;
-            case ('exists' in cond):
-                checkKeyExistsInDB(this.db, cond.exists, asyncCallback);
-                break;
             default:
                 asyncCallback(new Error('unsupported conditional operation'));
             }
@@ -437,7 +425,7 @@ describe('IndexTransaction', () => {
                 value: value3,
             });
             return transaction.commit(err => {
-                if (!err || !err.is.EntityAlreadyExists) {
+                if (!err || !err.is.PreconditionFailed) {
                     return done(new Error('should not be able to conditional put for duplicate key'));
                 }
                 return async.parallel([
@@ -469,87 +457,11 @@ describe('IndexTransaction', () => {
     it('should not allow batch operation with unsupported condition', done => {
         const transaction = new IndexTransaction();
         try {
-            transaction.addCondition({ like: key1 });
+            transaction.addCondition({ exists: key1 });
             done(new Error('should fail for unsupported condition, currently supported - notExists'));
         } catch (err) {
             assert.strictEqual(err.unsupportedConditionalOperation, true);
             done();
         }
     });
-
-    it('should allow batch operation with key specified in exists condition is present in db', done => {
-        const db = new ConditionalLevelDB();
-        const { client } = db;
-        let transaction = new IndexTransaction(db);
-        transaction.put(key1, value1);
-        return async.series([
-            next => transaction.commit(next),
-            next => client.get(key1, next),
-        ], err => {
-            assert.ifError(err);
-            // create new transaction as previous transaction is already committed
-            transaction = new IndexTransaction(db);
-            transaction.addCondition({ exists: key1 });
-            transaction.push({
-                type: 'put',
-                key: key1,
-                value: value2,
-            });
-            return async.series([
-                next => transaction.commit(next),
-                next => client.get(key1, next),
-            ], (err, res) => {
-                assert.ifError(err);
-                assert.strictEqual(res[1], value2);
-                return done();
-            });
-        });
-    });
-
-    it('should not allow batch operation with key specified in exists condition is not in db', done => {
-        const db = new ConditionalLevelDB();
-        const { client } = db;
-        const transaction = new IndexTransaction(db);
-        transaction.addCondition({ exists: key1 });
-        transaction.push({
-            type: 'put',
-            key: key1,
-            value: value1,
-        });
-        return transaction.commit(err => {
-            assert.strictEqual(err && err.NoSuchEntity, true);
-            return checkKeyNotExistsInDB(client, key1, done);
-        });
-    });
-
-    it('should handle batch operations with multiple conditions correctly', done => {
-        const db = new ConditionalLevelDB();
-        const { client } = db;
-        let transaction = new IndexTransaction(db);
-        transaction.put(key1, value1);
-        return async.series([
-            next => transaction.commit(next),
-            next => client.get(key1, next),
-        ], err => {
-            assert.ifError(err);
-            // create new transaction as previous transaction is already committed
-            transaction = new IndexTransaction(db);
-            transaction.addCondition({ exists: key1 });
-            transaction.addCondition({ notExists: key2 });
-            transaction.push({
-                type: 'put',
-                key: key1,
-                value: value2,
-            });
-
-            return async.series([
-                next => transaction.commit(next),
-                next => client.get(key1, next),
-            ], (err, res) => {
-                assert.ifError(err);
-                assert.strictEqual(res[1], value2);
-                return done();
-            });
-        });
-    });
 });

tests/unit/models/BucketInfo.spec.js

@@ -228,8 +228,6 @@ const testBucketCapabilities = {
     },
 };
 
-const testBucketQuota = 100000;
-
 // create a dummy bucket to test getters and setters
 Object.keys(acl).forEach(
     aclObj => describe(`different acl configurations : ${aclObj}`, () => {
@@ -254,7 +252,6 @@ Object.keys(acl).forEach(
             testNotificationConfiguration,
             testBucketTagging,
             testBucketCapabilities,
-            testBucketQuota,
         );
 
         describe('serialize/deSerialize on BucketInfo class', () => {
@@ -293,7 +290,6 @@ Object.keys(acl).forEach(
                     notificationConfiguration: dummyBucket._notificationConfiguration,
                     tags: dummyBucket._tags,
                     capabilities: dummyBucket._capabilities,
-                    quotaMax: dummyBucket._quotaMax,
                 };
                 assert.strictEqual(serialized, JSON.stringify(bucketInfos));
                 done();
@@ -343,7 +339,6 @@ Object.keys(acl).forEach(
                         dummyBucket._notificationConfiguration,
                     _tags: dummyBucket._tags,
                     _capabilities: dummyBucket._capabilities,
-                    _quotaMax: dummyBucket._quotaMax,
                 };
                 const fromObj = BucketInfo.fromObj(dataObj);
                 assert(fromObj instanceof BucketInfo);
@@ -699,17 +694,6 @@ Object.keys(acl).forEach(
                 assert.deepStrictEqual(
                     dummyBucket.getCapabilities(), testCapabilities);
             });
-            it('setQuota should set bucket quota', () => {
-                const testQuota = testBucketQuota;
-                dummyBucket.setQuota(testQuota);
-                assert.deepStrictEqual(
-                    dummyBucket.getQuota(), testQuota);
-            });
-            it('setQuota should set bucket quota', () => {
-                dummyBucket.setQuota();
-                assert.deepStrictEqual(
-                    dummyBucket.getQuota(), 0);
-            });
         });
     }),
 );

tests/unit/versioning/Version.spec.js

@@ -1,72 +0,0 @@
-const { Version } = require('../../../lib/versioning/Version');
-
-describe('Version', () => {
-    describe('_jsonAppend', () => {
-        it('should append key-value pair to an empty object', () => {
-            const result = Version._jsonAppend('{}', 'versionId', '123');
-            expect(result).toBe('{"versionId":"123"}');
-        });
-
-        it('should append key-value pair to an object with existing properties', () => {
-            const result = Version._jsonAppend('{"existingKey":"existingValue"}', 'versionId', '123');
-            expect(result).toBe('{"existingKey":"existingValue","versionId":"123"}');
-        });
-
-        it('should append key-value pair to an object with existing key', () => {
-            const result = Version._jsonAppend('{"versionId":"0"}', 'versionId', '123');
-            expect(result).toBe('{"versionId":"0","versionId":"123"}');
-        });
-    });
-
-    describe('appendVersionId', () => {
-        it('should append versionId to an empty object', () => {
-            const emptyObject = '{}';
-            const versionId = '123';
-            const expected = '{"versionId":"123"}';
-            const result = Version.appendVersionId(emptyObject, versionId);
-            expect(result).toEqual(expected);
-        });
-
-        it('should append versionId to an object with existing properties', () => {
-            const existingObject = '{"key":"value"}';
-            const versionId = '456';
-            const expected = '{"key":"value","versionId":"456"}';
-            const result = Version.appendVersionId(existingObject, versionId);
-            expect(result).toEqual(expected);
-        });
-
-        it('should append versionId to an object with existing versionId', () => {
-            const objectWithVersionId = '{"key":"value","versionId":"old"}';
-            const versionId = 'new';
-            const expected = '{"key":"value","versionId":"old","versionId":"new"}';
-            const result = Version.appendVersionId(objectWithVersionId, versionId);
-            expect(result).toEqual(expected);
-        });
-    });
-
-    describe('updateOrAppendNullVersionId', () => {
-        it('should append nullVersionId when it does not exist', () => {
-            const initialValue = '{"key":"value"}';
-            const nullVersionId = '12345';
-            const expectedValue = '{"key":"value","nullVersionId":"12345"}';
-            const result = Version.updateOrAppendNullVersionId(initialValue, nullVersionId);
-            expect(result).toEqual(expectedValue);
-        });
-
-        it('should update nullVersionId when it exists', () => {
-            const initialValue = '{"key":"value","nullVersionId":"initial"}';
-            const nullVersionId = 'updated12345';
-            const expectedValue = '{"key":"value","nullVersionId":"updated12345"}';
-            const result = Version.updateOrAppendNullVersionId(initialValue, nullVersionId);
-            expect(result).toEqual(expectedValue);
-        });
-
-        it('should handle empty string by appending nullVersionId', () => {
-            const initialValue = '{}';
-            const nullVersionId = 'emptyCase12345';
-            const expectedValue = '{"nullVersionId":"emptyCase12345"}';
-            const result = Version.updateOrAppendNullVersionId(initialValue, nullVersionId);
-            expect(result).toEqual(expectedValue);
-        });
-    });
-});

tests/unit/versioning/VersioningRequestProcessor.spec.js

@@ -254,588 +254,6 @@ describe('test VRP', () => {
         }],
         done);
     });
-
-    it('should be able to put Metadata on top of a standalone null version', done => {
-        const versionId = '00000000000000999999PARIS  ';
-
-        async.waterfall([next => {
-            // simulate the creation of a standalone null version.
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: '{"qux":"quz"}',
-                options: {},
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            // simulate a BackbeatClient.putMetadata
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: `{"qux":"quz2","versionId":"${versionId}"}`,
-                options: {
-                    versioning: true,
-                    versionId,
-                    // isNull === false means Cloudserver supports the new "null key" logic.
-                    isNull: false,
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            wgm.list({}, logger, next);
-        },
-        (res, next) => {
-            const expectedListing = [
-                // master version should have the provided version id
-                {
-                    key: 'bar',
-                    value: `{"qux":"quz2","versionId":"${versionId}"}`,
-                },
-                // The null version will get the highest version number.
-                // It should have "isNull" and "isNul2" set to true,
-                // showing it's a null version made by Cloudserver that works with null keys.
-                {
-                    key: `bar${VID_SEP}`,
-                    value: '{"qux":"quz","versionId":"99999999999999999999PARIS  ","isNull":true,"isNull2":true}',
-                },
-                // the new version
-                {
-                    key: `bar${VID_SEP}${versionId}`,
-                    value: `{"qux":"quz2","versionId":"${versionId}"}`,
-                },
-            ];
-            assert.deepStrictEqual(res, expectedListing);
-            const request = {
-                db: 'foo',
-                key: 'bar',
-            };
-            vrp.get(request, logger, next);
-        },
-        (res, next) => {
-            const expectedGet = {
-                qux: 'quz2',
-                versionId,
-            };
-            assert.deepStrictEqual(JSON.parse(res), expectedGet);
-            next();
-        }],
-        done);
-    });
-
-    it('should be able to put Metadata on top of a standalone null version in backward compatibility mode', done => {
-        const versionId = '00000000000000999999PARIS  ';
-
-        async.waterfall([next => {
-            // simulate the creation of a standalone null version.
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: '{"qux":"quz"}',
-                options: {},
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            // simulate a BackbeatClient.putMetadata
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: `{"qux":"quz2","versionId":"${versionId}"}`,
-                options: {
-                    versioning: true,
-                    versionId,
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            wgm.list({}, logger, next);
-        },
-        (res, next) => {
-            const expectedListing = [
-                // master version should have the provided version id and a reference of the null version id.
-                {
-                    key: 'bar',
-                    value: `{"qux":"quz2","versionId":"${versionId}","nullVersionId":"99999999999999999999PARIS  "}`,
-                },
-                // the "internal" master version should have the provided version id.
-                {
-                    key: `bar${VID_SEP}${versionId}`,
-                    value: `{"qux":"quz2","versionId":"${versionId}"}`,
-                },
-                // should create a version that represents the old null master with the infinite version id and
-                // the isNull property set to true.
-                {
-                    key: `bar${VID_SEP}99999999999999999999PARIS  `,
-                    value: '{"qux":"quz","versionId":"99999999999999999999PARIS  ","isNull":true}',
-                },
-            ];
-            assert.deepStrictEqual(res, expectedListing);
-            const request = {
-                db: 'foo',
-                key: 'bar',
-            };
-            vrp.get(request, logger, next);
-        },
-        (res, next) => {
-            const expectedGet = {
-                qux: 'quz2',
-                versionId,
-                nullVersionId: '99999999999999999999PARIS  ',
-            };
-            assert.deepStrictEqual(JSON.parse(res), expectedGet);
-            next();
-        }],
-        done);
-    });
-
-    it('should be able to put Metadata on top of a null suspended version', done => {
-        const versionId = '00000000000000999999PARIS  ';
-        let nullVersionId;
-
-        async.waterfall([next => {
-            // simulate the creation of a null suspended version.
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: '{"qux":"quz","isNull":true}',
-                options: {
-                    versionId: '',
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            nullVersionId = JSON.parse(res).versionId;
-            // simulate a BackbeatClient.putMetadata
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: `{"qux":"quz2","versionId":"${versionId}"}`,
-                options: {
-                    versioning: true,
-                    versionId,
-                    // isNull === false means Cloudserver supports the new "null key" logic.
-                    isNull: false,
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            wgm.list({}, logger, next);
-        },
-        (res, next) => {
-            const expectedListing = [
-                // master version should have the provided version id
-                {
-                    key: 'bar',
-                    value: `{"qux":"quz2","versionId":"${versionId}"}`,
-                },
-                // The null version will get the highest version number.
-                // It should have "isNull" and "isNul2" set to true,
-                // showing it's a null version made by Cloudserver that works with null keys.
-                {
-                    key: `bar${VID_SEP}`,
-                    value: `{"qux":"quz","isNull":true,"versionId":"${nullVersionId}","isNull2":true}`,
-                },
-                // the new version
-                {
-                    key: `bar${VID_SEP}${versionId}`,
-                    value: `{"qux":"quz2","versionId":"${versionId}"}`,
-                },
-            ];
-            assert.deepStrictEqual(res, expectedListing);
-            const request = {
-                db: 'foo',
-                key: 'bar',
-            };
-            vrp.get(request, logger, next);
-        },
-        (res, next) => {
-            const expectedGet = {
-                qux: 'quz2',
-                versionId,
-            };
-            assert.deepStrictEqual(JSON.parse(res), expectedGet);
-            next();
-        }],
-        done);
-    });
-
-    it('should be able to put Metadata on top of a null suspended version in backward compatibility mode', done => {
-        const versionId = '00000000000000999999PARIS  ';
-        let nullVersionId;
-
-        async.waterfall([next => {
-            // simulate the creation of a null suspended version.
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: '{"qux":"quz","isNull":true}',
-                options: {
-                    versionId: '',
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            nullVersionId = JSON.parse(res).versionId;
-            // simulate a BackbeatClient.putMetadata
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: `{"qux":"quz2","versionId":"${versionId}"}`,
-                options: {
-                    versioning: true,
-                    versionId,
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            wgm.list({}, logger, next);
-        },
-        (res, next) => {
-            const expectedListing = [
-                // master version should have the provided version id and a reference of the null version id.
-                {
-                    key: 'bar',
-                    value: `{"qux":"quz2","versionId":"${versionId}","nullVersionId":"${nullVersionId}"}`,
-                },
-                // the "internal" master version should have the provided version id.
-                {
-                    key: `bar${VID_SEP}${versionId}`,
-                    value: `{"qux":"quz2","versionId":"${versionId}"}`,
-                },
-                // should create a version that represents the old null master with the infinite version id and
-                // the isNull property set to true.
-                {
-                    key: `bar${VID_SEP}${nullVersionId}`,
-                    value: `{"qux":"quz","isNull":true,"versionId":"${nullVersionId}"}`,
-                },
-            ];
-            assert.deepStrictEqual(res, expectedListing);
-            const request = {
-                db: 'foo',
-                key: 'bar',
-            };
-            vrp.get(request, logger, next);
-        },
-        (res, next) => {
-            const expectedGet = {
-                qux: 'quz2',
-                versionId,
-                nullVersionId,
-            };
-            assert.deepStrictEqual(JSON.parse(res), expectedGet);
-            next();
-        }],
-        done);
-    });
-
-    it('should be able to update a null suspended version in backward compatibility mode', done => {
-        let nullVersionId;
-
-        async.waterfall([next => {
-            // simulate the creation of a null suspended version.
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: '{"qux":"quz","isNull":true}',
-                options: {
-                    versionId: '',
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            nullVersionId = JSON.parse(res).versionId;
-            // simulate update null version with BackbeatClient.putMetadata
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: `{"qux":"quz2","isNull":true,"versionId":"${nullVersionId}"}`,
-                options: {
-                    versioning: true,
-                    versionId: nullVersionId,
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            wgm.list({}, logger, next);
-        },
-        (res, next) => {
-            const expectedListing = [
-                // NOTE: should not set nullVersionId to the master version if updating a null version.
-                {
-                    key: 'bar',
-                    value: `{"qux":"quz2","isNull":true,"versionId":"${nullVersionId}"}`,
-                },
-                {
-                    key: `bar\x00${nullVersionId}`,
-                    value: `{"qux":"quz","isNull":true,"versionId":"${nullVersionId}"}`,
-                },
-            ];
-            assert.deepStrictEqual(res, expectedListing);
-
-            const request = {
-                db: 'foo',
-                key: 'bar',
-            };
-            vrp.get(request, logger, next);
-        },
-        (res, next) => {
-            const expectedGet = {
-                qux: 'quz2',
-                isNull: true,
-                versionId: nullVersionId,
-            };
-            assert.deepStrictEqual(JSON.parse(res), expectedGet);
-            next();
-        }],
-        done);
-    });
-
-    it('should delete the deprecated null key after put Metadata on top of an old null master', done => {
-        const versionId = '00000000000000999999PARIS  ';
-        let nullVersionId;
-
-        async.waterfall([next => {
-            // simulate the creation of a null suspended version.
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: '{"qux":"quz","isNull":true}',
-                options: {
-                    versionId: '',
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            nullVersionId = JSON.parse(res).versionId;
-            // update metadata of the same null version with compat mode (options.isNull not defined)
-            // to generate a deprecated null key.
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: `{"qux":"quz2","isNull":true,"versionId":"${nullVersionId}"}`,
-                options: {
-                    versionId: nullVersionId,
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            // put metadata with the new keys implementation (options.isNull defined)
-            // on top of the null master with a deprecated null key.
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: `{"qux":"quz3","versionId":"${versionId}"}`,
-                options: {
-                    versionId,
-                    isNull: false,
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            wgm.list({}, logger, next);
-        },
-        (res, next) => {
-            const expectedListing = [
-                // master version should have the provided version id.
-                {
-                    key: 'bar',
-                    value: `{"qux":"quz3","versionId":"${versionId}"}`,
-                },
-                // the null key
-                {
-                    key: `bar${VID_SEP}`,
-                    value: `{"qux":"quz2","isNull":true,"versionId":"${nullVersionId}","isNull2":true}`,
-                },
-                // version key
-                {
-                    key: `bar${VID_SEP}${versionId}`,
-                    value: `{"qux":"quz3","versionId":"${versionId}"}`,
-                },
-            ];
-            assert.deepStrictEqual(res, expectedListing);
-            const request = {
-                db: 'foo',
-                key: 'bar',
-            };
-            vrp.get(request, logger, next);
-        },
-        (res, next) => {
-            const expectedGet = {
-                qux: 'quz3',
-                versionId,
-            };
-            assert.deepStrictEqual(JSON.parse(res), expectedGet);
-            next();
-        }],
-        done);
-    });
-
-    it('should delete the deprecated null key after updating metadata of an old null master', done => {
-        let nullVersionId;
-
-        async.waterfall([next => {
-            // simulate the creation of a null suspended version.
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: '{"qux":"quz","isNull":true}',
-                options: {
-                    versionId: '',
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            nullVersionId = JSON.parse(res).versionId;
-            // update metadata of the same null version with compat mode (options.isNull not defined)
-            // to generate a deprecated null key.
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: `{"qux":"quz2","isNull":true,"versionId":"${nullVersionId}"}`,
-                options: {
-                    versionId: nullVersionId,
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            // update the null version metadata with the new keys implementation (options.isNull defined)
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: `{"qux":"quz3","isNull2":true,"isNull":true,"versionId":"${nullVersionId}"}`,
-                options: {
-                    versionId: nullVersionId,
-                    isNull: true,
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            wgm.list({}, logger, next);
-        },
-        (res, next) => {
-            const expectedListing = [
-                // the internal null version should be deleted.
-                {
-                    key: 'bar',
-                    value: `{"qux":"quz3","isNull2":true,"isNull":true,"versionId":"${nullVersionId}"}`,
-                },
-            ];
-            assert.deepStrictEqual(res, expectedListing);
-            const request = {
-                db: 'foo',
-                key: 'bar',
-            };
-            vrp.get(request, logger, next);
-        },
-        (res, next) => {
-            const expectedGet = {
-                qux: 'quz3',
-                isNull2: true,
-                isNull: true,
-                versionId: nullVersionId,
-            };
-            assert.deepStrictEqual(JSON.parse(res), expectedGet);
-            next();
-        }],
-        done);
-    });
-
-    it('should delete the deprecated null key after updating a non-latest null key', done => {
-        const versionId = '00000000000000999999PARIS  ';
-        let nullVersionId;
-
-        async.waterfall([next => {
-            // simulate the creation of a null suspended version.
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: '{"qux":"quz","isNull":true}',
-                options: {
-                    versionId: '',
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            nullVersionId = JSON.parse(res).versionId;
-            // simulate a BackbeatClient.putMetadata
-            // null key is not the latest = master is not null.
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: `{"qux":"quz2","versionId":"${versionId}"}`,
-                options: {
-                    versioning: true,
-                    versionId,
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            // update the null version metadata with the new keys implementation (options.isNull defined)
-            const request = {
-                db: 'foo',
-                key: 'bar',
-                value: `{"qux":"quz3","isNull2":true,"isNull":true,"versionId":"${nullVersionId}"}`,
-                options: {
-                    versionId: nullVersionId,
-                    isNull: true,
-                },
-            };
-            vrp.put(request, logger, next);
-        },
-        (res, next) => {
-            wgm.list({}, logger, next);
-        },
-        (res, next) => {
-            const expectedListing = [
-                {
-                    key: 'bar',
-                    value: `{"qux":"quz2","versionId":"${versionId}","nullVersionId":"${nullVersionId}"}`,
-                },
-                {
-                    key: 'bar\x00',
-                    value: `{"qux":"quz3","isNull2":true,"isNull":true,"versionId":"${nullVersionId}"}`,
-                },
-                {
-                    key: `bar\x00${versionId}`,
-                    value: `{"qux":"quz2","versionId":"${versionId}"}`,
-                },
-            ];
-            assert.deepStrictEqual(res, expectedListing);
-
-            const request = {
-                db: 'foo',
-                key: 'bar',
-            };
-            vrp.get(request, logger, next);
-        },
-        (res, next) => {
-            const expectedGet = {
-                qux: 'quz2',
-                versionId,
-                nullVersionId,
-            };
-            assert.deepStrictEqual(JSON.parse(res), expectedGet);
-            next();
-        }],
-        done);
-    });
 });
 
 

tsconfig.json

@@ -1,6 +1,6 @@
 {
     "compilerOptions": {
-        "target": "es2020",
+        "target": "es6",
         "module": "commonjs",
         "rootDir": "./",
         "resolveJsonModule": true,