Repository: mostjs/core
Pull request #220 (2018-03-21 13:23:56)

Improve slice bounds
Extract slice bounds type and operations so they can be more easily verified.  Also, improve bounds algorithms and slice fusion in a few ways:

1. Rule out negatives to avoid potential min accumulation issues
2. Detect nil (min === max) and infinite bounds (0, Infinity)
3. Return canonical empty for nil bounds
4. Return input for infinite bounds


Patch:
diff --git a/docs/adrs/TEMPLATE.md b/docs/adrs/TEMPLATE.md
new file mode 100644
index 0000000..4470067
--- /dev/null
+++ b/docs/adrs/TEMPLATE.md
@@ -0,0 +1,16 @@
+# ADR [n]: [Title]
+
+Brian Cavalier (@briancavalier),
+David Chase (@davidchase),
+Tylor Steinberger (@TylorS)
+Frederik Krautwald (@Frikki),
+
+## Status
+
+**Proposed** | ~~Accepted~~ | ~~Deprecated~~ | ~~Superseded~~
+
+## Context
+
+## Decision
+
+## Consequences
diff --git a/packages/core/package.json b/packages/core/package.json
index 42d87f4..c3af77e 100644
--- a/packages/core/package.json
+++ b/packages/core/package.json
@@ -51,6 +51,7 @@
     "nyc": "^11.0.2",
     "rollup": "^0.50.0",
     "rollup-plugin-babel": "^3.0.2",
+    "rollup-plugin-local-resolve": "^1.0.7",
     "sinon": "^1.17.7",
     "snazzy": "^7.0.0",
     "standard": "^10.0.3"
diff --git a/packages/core/rollup.config.js b/packages/core/rollup.config.js
index 7071acf..8210f61 100644
--- a/packages/core/rollup.config.js
+++ b/packages/core/rollup.config.js
@@ -1,9 +1,11 @@
 import babel from 'rollup-plugin-babel'
+import localResolve from 'rollup-plugin-local-resolve'
 import pkg from './package.json'
 
 export default {
   input: 'src/index.js',
   plugins: [
+    localResolve(),
     babel({
       exclude: 'node_modules/**',
       plugins: ['external-helpers']
diff --git a/packages/core/src/combinator/slice/bounds.js b/packages/core/src/combinator/slice/bounds.js
new file mode 100644
index 0000000..a06badc
--- /dev/null
+++ b/packages/core/src/combinator/slice/bounds.js
@@ -0,0 +1,38 @@
+/** @license MIT License (c) copyright 2010 original author or authors */
+
+// A slice Bounds type that narrows min values via accumulation
+// and max values via Math.min.
+// type Bounds = { min: number, max: number }
+// Notes:
+// 0 <= min <= max
+// slice(min2, max2, slice(min1, max1, s)) ~ slice(min1 + min2, Math.min(max1, min1 + max2), s)
+// A bounds has a 1d coord system with origin 0, extending to Infinity.  Both min and max
+// are relative to the origin (0).  However, when merging bounds b1 and b2, we
+// *interpret* b2 as being relative to b1, hence adding min1 to *both* min2 and max2.
+// This essentially translates b2's coordinates back into origin coordinates
+// as bounds are merged.
+
+// Construct a constrained bounds
+export const boundsFrom = (unsafeMin, unsafeMax) => {
+  const min = Math.max(0, unsafeMin)
+  const max = Math.max(min, unsafeMax)
+  return { min, max }
+}
+
+export const minBounds = min =>
+  boundsFrom(min, Infinity)
+
+export const maxBounds = max =>
+  boundsFrom(0, max)
+
+// Combine 2 bounds by narrowing min and max
+export const mergeBounds = (b1, b2) =>
+  boundsFrom(b1.min + b2.min, Math.min(b1.max, b1.min + b2.max))
+
+// Nil bounds excludes all slice indices
+export const isNilBounds = b =>
+  b.min >= b.max
+
+// Infinite bounds includes all slice indices
+export const isInfiniteBounds = b =>
+  b.min <= 0 && b.max === Infinity
diff --git a/packages/core/src/combinator/slice.js b/packages/core/src/combinator/slice/index.js
similarity index 73%
rename from packages/core/src/combinator/slice.js
rename to packages/core/src/combinator/slice/index.js
index a40f7f1..c2e04e2 100644
--- a/packages/core/src/combinator/slice.js
+++ b/packages/core/src/combinator/slice/index.js
@@ -1,9 +1,8 @@
-/** @license MIT License (c) copyright 2010 original author or authors */
-
-import Pipe from '../sink/Pipe'
-import { empty, isCanonicalEmpty } from '../source/empty'
-import Map from '../fusion/Map'
-import SettableDisposable from '../disposable/SettableDisposable'
+import { empty, isCanonicalEmpty } from '../../source/empty'
+import { maxBounds, minBounds, boundsFrom, isNilBounds, isInfiniteBounds, mergeBounds } from './bounds'
+import Map from '../../fusion/Map'
+import Pipe from '../../sink/Pipe'
+import SettableDisposable from '../../disposable/SettableDisposable'
 
 /**
  * @param {number} n
@@ -11,7 +10,7 @@ import SettableDisposable from '../disposable/SettableDisposable'
  * @returns {Stream} new stream containing only up to the first n items from stream
  */
 export const take = (n, stream) =>
-  slice(0, n, stream)
+  sliceBounds(maxBounds(n), stream)
 
 /**
  * @param {number} n
@@ -19,7 +18,7 @@ export const take = (n, stream) =>
  * @returns {Stream} new stream with the first n items removed
  */
 export const skip = (n, stream) =>
-  slice(n, Infinity, stream)
+  sliceBounds(minBounds(n), stream)
 
 /**
  * Slice a stream by index. Negative start/end indexes are not supported
@@ -29,34 +28,35 @@ export const skip = (n, stream) =>
  * @returns {Stream} stream containing items where start <= index < end
  */
 export const slice = (start, end, stream) =>
-  end <= start || isCanonicalEmpty(stream)
-    ? empty()
-    : sliceSource(start, end, stream)
-
-const sliceSource = (start, end, stream) =>
-  stream instanceof Map ? commuteMapSlice(start, end, stream)
-    : stream instanceof Slice ? fuseSlice(start, end, stream)
-    : new Slice(start, end, stream)
-
-const commuteMapSlice = (start, end, mapStream) =>
-  Map.create(mapStream.f, slice(start, end, mapStream.source))
-
-function fuseSlice (start, end, sliceStream) {
-  const fusedStart = start + sliceStream.min
-  const fusedEnd = Math.min(end + sliceStream.min, sliceStream.max)
-  return slice(fusedStart, fusedEnd, sliceStream.source)
-}
+  sliceBounds(boundsFrom(start, end), stream)
+
+const sliceBounds = (bounds, stream) =>
+  isSliceEmpty(bounds, stream) ? empty()
+    : stream instanceof Map ? commuteMapSlice(bounds, stream)
+    : stream instanceof Slice ? fuseSlice(bounds, stream)
+    : createSlice(bounds, stream)
+
+const isSliceEmpty = (bounds, stream) =>
+  isCanonicalEmpty(stream) || isNilBounds(bounds)
+
+const createSlice = (bounds, stream) =>
+  isInfiniteBounds(bounds) ? stream : new Slice(bounds, stream)
+
+const commuteMapSlice = (bounds, mapStream) =>
+  Map.create(mapStream.f, sliceBounds(bounds, mapStream.source))
+
+const fuseSlice = (bounds, sliceStream) =>
+  sliceBounds(mergeBounds(bounds, sliceStream.bounds), sliceStream.source)
 
 class Slice {
-  constructor (min, max, source) {
+  constructor (bounds, source) {
     this.source = source
-    this.min = min
-    this.max = max
+    this.bounds = bounds
   }
 
   run (sink, scheduler) {
     const disposable = new SettableDisposable()
-    const sliceSink = new SliceSink(this.min, this.max - this.min, sink, disposable)
+    const sliceSink = new SliceSink(this.bounds.min, this.bounds.max - this.bounds.min, sink, disposable)
 
     disposable.setDisposable(this.source.run(sliceSink, scheduler))
 
diff --git a/packages/disposable/src/disposeAll.js b/packages/disposable/src/disposeAll.js
index 1004d78..6953678 100644
--- a/packages/disposable/src/disposeAll.js
+++ b/packages/disposable/src/disposeAll.js
@@ -1,14 +1,22 @@
-/** @license MIT License (c) copyright 2010-2017 original author or authors */
-import { reduce, curry2 } from '@most/prelude'
+/** @license MIT License (c) copyright 2010 original author or authors */
+import { append, reduce, curry2 } from '@most/prelude'
+import { disposeNone, isDisposeNone } from './disposeNone'
 
 // Aggregate a list of disposables into a DisposeAll
-export const disposeAll = ds =>
-  new DisposeAll(ds)
+export const disposeAll = ds => {
+  const merged = reduce(merge, [], ds)
+  return merged.length === 0 ? disposeNone() : new DisposeAll(merged)
+}
 
 // Convenience to aggregate 2 disposables
 export const disposeBoth = curry2((d1, d2) =>
   disposeAll([d1, d2]))
 
+const merge = (ds, d) =>
+  isDisposeNone(d) ? ds
+    : d instanceof DisposeAll ? ds.concat(d.disposables)
+    : append(d, ds)
+
 class DisposeAll {
   constructor (disposables) {
     this.disposables = disposables
diff --git a/packages/disposable/src/disposeNone.js b/packages/disposable/src/disposeNone.js
index d8bb9f4..b7bf61d 100644
--- a/packages/disposable/src/disposeNone.js
+++ b/packages/disposable/src/disposeNone.js
@@ -4,3 +4,6 @@ export const disposeNone = () => NONE
 const NONE = new (class DisposeNone {
   dispose () {}
 })()
+
+export const isDisposeNone = d =>
+  d === NONE


Test patch:
diff --git a/packages/core/test/combinator/slice/bounds-test.js b/packages/core/test/combinator/slice/bounds-test.js
new file mode 100644
index 0000000..d2d5fc8
--- /dev/null
+++ b/packages/core/test/combinator/slice/bounds-test.js
@@ -0,0 +1,87 @@
+// @flow
+import { assert, eq } from '@briancavalier/assert'
+import { describe, it } from 'mocha'
+
+import {
+  isInfiniteBounds,
+  isNilBounds,
+  maxBounds,
+  mergeBounds,
+  minBounds,
+  boundsFrom
+} from '../../../src/combinator/slice/bounds'
+
+const rInt = (min = 0, max = Number.MAX_SAFE_INTEGER) =>
+  Math.floor(min + (Math.random() * (max - min)))
+
+const rBound = () => rInt(-Number.MAX_SAFE_INTEGER)
+
+const assertValidBounds = gen => {
+  for (let i = 0; i < 100; ++i) {
+    const b = gen()
+    assert(b.min >= 0 && b.max >= b.min)
+  }
+}
+
+describe('slice/bounds', () => {
+  describe('boundsFrom', () => {
+    it('should create valid bounds', () => {
+      assertValidBounds(() => boundsFrom(rBound(), rBound()))
+    })
+  })
+
+  describe('minBounds', () => {
+    it('should create valid bounds', () => {
+      assertValidBounds(() => minBounds(rBound()))
+    })
+  })
+
+  describe('maxBounds', () => {
+    it('should create valid bounds', () => {
+      assertValidBounds(() => maxBounds(rBound()))
+    })
+  })
+
+  describe('mergeBounds', () => {
+    it('should create valid bounds', () => {
+      assertValidBounds(
+        () => mergeBounds(boundsFrom(rBound(), rBound()), boundsFrom(rBound(), rBound()))
+      )
+    })
+    it('should accumulate min and keep lower max, relative to previously accumulated min', () => {
+      const b1 = boundsFrom(2, 10)
+      const b2 = boundsFrom(1, 5)
+      const b = mergeBounds(b1, b2)
+      eq(boundsFrom(3, 7), b)
+    })
+    it('should accumulate min and keep lower max, relative to previously accumulated min', () => {
+      const b1 = boundsFrom(2, 5)
+      const b2 = boundsFrom(1, 10)
+      const b = mergeBounds(b1, b2)
+      eq(boundsFrom(3, 5), b)
+    })
+  })
+
+  describe('isNilBounds', () => {
+    it('given min < max, should be false', () => {
+      const min = rInt()
+      assert(!isNilBounds(boundsFrom(min, rInt(min))))
+    })
+    it('given min >= max, should be true', () => {
+      const min = rInt()
+      assert(isNilBounds(boundsFrom(min, min - rInt())))
+    })
+  })
+
+  describe('isInfiniteBounds', () => {
+    it('given min <= 0 and max === Infinity, should be true', () => {
+      assert(isInfiniteBounds(boundsFrom(-rInt(), Infinity)))
+    })
+    it('given min > 0, should be false', () => {
+      assert(!isInfiniteBounds(boundsFrom(rInt(1), Infinity)))
+    })
+    it('given max < Infinity, should be false', () => {
+      assert(!isInfiniteBounds(boundsFrom(0, rInt(1))))
+    })
+  })
+})
diff --git a/packages/core/test/slice-test.js b/packages/core/test/combinator/slice/index-test.js
similarity index 87%
rename from packages/core/test/slice-test.js
rename to packages/core/test/combinator/slice/index-test.js
index 0f731b2..4b5bbd8 100644
--- a/packages/core/test/slice-test.js
+++ b/packages/core/test/combinator/slice/index-test.js
@@ -1,14 +1,15 @@
 import { describe, it } from 'mocha'
 import { eq, is, assert } from '@briancavalier/assert'
 
-import { slice, take, skip, takeWhile, skipWhile, skipAfter } from '../src/combinator/slice'
-import { map } from '../src/combinator/transform'
-import { now } from '../src/source/now'
-import { empty, isCanonicalEmpty } from '../src/source/empty'
-import { default as Map } from '../src/fusion/Map'
+import { slice, take, skip, takeWhile, skipWhile, skipAfter } from '../../../src/combinator/slice'
+import { boundsFrom } from '../../../src/combinator/slice/bounds'
+import { map } from '../../../src/combinator/transform'
+import { now } from '../../../src/source/now'
+import { empty, isCanonicalEmpty } from '../../../src/source/empty'
+import { default as Map } from '../../../src/fusion/Map'
 
-import { makeEventsFromArray, collectEventsFor, makeEvents } from './helper/testEnv'
-import { assertSame } from './helper/stream-helper'
+import { makeEventsFromArray, collectEventsFor, makeEvents } from '../../helper/testEnv'
+import { assertSame } from '../../helper/stream-helper'
 
 describe('slice', function () {
   describe('fusion', function () {
@@ -27,14 +28,12 @@ describe('slice', function () {
 
     it('should narrow when second slice is smaller', function () {
       const s = slice(1, 5, slice(1, 10, now('')))
-      eq(2, s.min)
-      eq(6, s.max)
+      eq(boundsFrom(2, 5), s.bounds)
     })
 
     it('should narrow when second slice is larger', function () {
       const s = slice(1, 10, slice(1, 5, now('')))
-      eq(2, s.min)
-      eq(5, s.max)
+      eq(boundsFrom(2, 6), s.bounds)
     })
 
     it('should commute map', function () {
@@ -63,6 +62,11 @@ describe('slice', function () {
           { time: 6, value: 6 }
         ]))
     })
+
+    it('given infinite bounds, should be identity', () => {
+      const s = makeEvents(1, 3)
+      is(s, slice(0, Infinity, s))
+    })
   })
 
   describe('take', function () {
diff --git a/packages/disposable/test/disposeAll-test.js b/packages/disposable/test/disposeAll-test.js
index 0d6551a..4ba4be6 100644
--- a/packages/disposable/test/disposeAll-test.js
+++ b/packages/disposable/test/disposeAll-test.js
@@ -1,6 +1,7 @@
 import { describe, it } from 'mocha'
 import { eq, assert, throws } from '@briancavalier/assert'
 import { spy } from 'sinon'
+import { disposeNone, isDisposeNone } from '../src/disposeNone'
 import { disposeAll, disposeBoth, DisposeAllError } from '../src/disposeAll'
 
 const noop = () => {}
@@ -29,6 +30,22 @@ describe('disposeAll', () => {
       assertAllDisposed(disposables)
     })
 
+    it('should fuse disposeNone', () => {
+      const d = disposeAll([disposeNone(), disposeNone()])
+      assert(isDisposeNone(d))
+    })
+
+    it('should fuse disposeAll', () => {
+      const d1 = disposableSpies()
+      const d2 = disposableSpies()
+
+      const d = disposeAll([disposeAll(d1), disposeAll(d2)])
+      eq(d1.length + d2.length, d.disposables.length)
+
+      d.dispose()
+      assertAllDisposed(d1.concat(d2))
+    })
+
     it('should dispose all and aggregate errors', function () {
       const errors = [new Error(), new Error()]
       const errorDisposables = errors.map(e => disposableSpy(rethrow(e)))
diff --git a/packages/disposable/test/disposeNone-test.js b/packages/disposable/test/disposeNone-test.js
index bfe7c46..03e075f 100644
--- a/packages/disposable/test/disposeNone-test.js
+++ b/packages/disposable/test/disposeNone-test.js
@@ -1,9 +1,21 @@
 import { describe, it } from 'mocha'
-import { is } from '@briancavalier/assert'
-import { disposeNone } from '../src/disposeNone'
+import { assert, is } from '@briancavalier/assert'
+import { disposeNone, isDisposeNone } from '../src/disposeNone'
 
 describe('disposeNone', () => {
-  it('should return same instance', () => {
-    is(disposeNone(), disposeNone())
+  describe('disposeNone', () => {
+    it('should return same instance', () => {
+      is(disposeNone(), disposeNone())
+    })
+  })
+
+  describe('isDisposeNone', () => {
+    it('should be true for disposeNone', () => {
+      assert(isDisposeNone(disposeNone()))
+    })
+
+    it('should be false for non-disposeNone', () => {
+      assert(!isDisposeNone({ dispose () {} }))
+    })
   })
 })