Skip to content

Instantly share code, notes, and snippets.

@calebmer

calebmer/PostVirtualizedComments.tsx

Created June 27, 2019 01:36
Show Gist options
  • Save calebmer/2a3bf40baa929115e7f985f876effb6f to your computer and use it in GitHub Desktop.
Save calebmer/2a3bf40baa929115e7f985f876effb6f to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. calebmer created this gist Jun 27, 2019.
    882 changes: 882 additions & 0 deletions PostVirtualizedComments.tsx
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,882 @@
    import {
    Dimensions,
    LayoutChangeEvent,
    Platform,
    ScrollEvent,
    ScrollView,
    StyleSheet,
    View,
    } from "react-native";
    import {Font, Space} from "../atoms";
    import {
    PostCommentsCacheEntry,
    commentCountMore,
    } from "../comment/CommentCache";
    import React, {ReactElement} from "react";
    import {
    unstable_LowPriority,
    unstable_runWithPriority,
    unstable_scheduleCallback,
    } from "scheduler";
    import {Comment} from "../comment/Comment";
    import {CommentShimmer} from "../comment/CommentShimmer";
    import {reactSchedulerFlushSync} from "../utils/forks/reactSchedulerFlushSync";

    // The number of items to render outside of the viewport range.
    //
    // We always overscan by the number of comments we’ll incrementally fetch. That
    // way when we load more comments, we’ll immediately render them and get
    // their heights.
    //
    // This is a bit of a hack to fix the jankiness of loading each comment as it
    // scrolls into view.
    const overscanCount = commentCountMore;

    // The number of items we will always render at the beginning of our list to
    // improve perceived performance.
    const leadingCount = commentCountMore / 2;

    // The number of items we will always render at the end of our list to
    // improve perceived performance.
    const trailingCount = commentCountMore;

    type Props = {
    /**
    * Are we currently loading new comments?
    */
    loading: boolean;

    /**
    * The total number of comments in our list. We will render a list that can
    * fit this many comments.
    */
    commentCount: number;

    /**
    * The underlying array of comments we will render. `undefined` comments are
    * represented with a comment shimmer. We will always render `commentCount`
    * number of comments. Whether or not that’s more or less than the actual
    * number of comments.
    */
    comments: ReadonlyArray<PostCommentsCacheEntry | undefined>;

    /**
    * A reference to the scroll view that our virtualized comment list
    * is inside.
    */
    scrollViewRef: React.RefObject<ScrollView>;

    /**
    * HACK: We want this component to have access to the `onScroll` event but we
    * don’t render the scroll view. Our parent is responsible for rendering the
    * scroll view. So we use a ref to pass “up” an event handler to our
    * parent component.
    */
    handleScroll: React.MutableRefObject<null | ((event: ScrollEvent) => void)>;

    /**
    * When the visible items change, we call this callback. The parent component
    * will use this to load more items.
    */
    onVisibleRangeChange: (range: RenderRange) => void;
    };

    type State = {
    /**
    * Is this the very first render of our component? We start by only rendering
    * the actually visible range. In subsequent renders we’ll render all the
    * overscroll and leading/trailing items.
    */
    initialRender: boolean;

    /**
    * The currently visible range of items.
    */
    visibleRange: RenderRange;

    /**
    * The heights of all the comments we’ve rendered. Gaps in the comment list
    * (`Skimmer.empty`) are represented with `undefined`.
    */
    commentHeights: ReadonlyArray<number | undefined>;

    /**
    * An alternative view of `commentHeights` where a sequence of contiguous
    * comments forms a chunk.
    */
    commentChunks: ReadonlyArray<CommentChunk>;
    };

    /**
    * A range of items to render.
    */
    type RenderRange = {
    first: number;
    last: number;
    };

    /**
    * A sequence of contiguous comments whose layouts have been measured.
    */
    type CommentChunk = {
    /** The index at the start of the chunk. */
    start: number;
    /** The number of comments in the chunk. */
    length: number;
    /** The total height of the chunk. */
    height: number;
    };

    export class PostVirtualizedComments extends React.Component<Props, State> {
    /**
    * The expected scroll event throttle for our component.
    */
    static scrollEventThrottle = 50;

    constructor(props: Props) {
    super(props);

    const first = 0;

    // Estimate the maximum number of comments that can fit on screen at
    // a time.
    const last = Math.min(
    Math.ceil(
    (Dimensions.get("screen").height * 0.75) / (Font.size2.lineHeight * 2),
    ),
    this.props.commentCount,
    );

    this.state = {
    initialRender: true,
    visibleRange: {first, last},
    commentHeights: [],
    commentChunks: [],
    };
    }

    componentDidMount() {
    // HACK: Set our scroll handler to the mutable ref. This is how we “pass up”
    // our event handler.
    this.props.handleScroll.current = this.handleScroll;

    // NOTE: The initial visible range is an estimate! We only get an accurate
    // visible range once we scroll for the first time.
    this.props.onVisibleRangeChange(this.state.visibleRange);

    // After we’ve rendered, schedule a low priority callback to render the rest
    // of the leading/trailing/overscan items.
    unstable_runWithPriority(unstable_LowPriority, () => {
    unstable_scheduleCallback(() => {
    this.setState({initialRender: false});
    });
    });
    }

    componentDidUpdate(_prevProps: Props, prevState: State) {
    // Report a change in the visible if there is one.
    if (
    prevState.visibleRange.first !== this.state.visibleRange.first ||
    prevState.visibleRange.last !== this.state.visibleRange.last
    ) {
    this.props.onVisibleRangeChange(this.state.visibleRange);
    }
    }

    componentWillUnmount() {
    this.props.handleScroll.current = null;
    }

    /**
    * Handles a scroll event by measuring the items we should be rendering and
    * updating state if it changed.
    */
    private handleScroll = (event: ScrollEvent) => {
    // Skip scroll events if we haven’t gotten a layout event yet. This shouldn’t
    // happen? If it does the next scroll after a layout event will fix it.
    const postOffset = this.postOffset;
    if (postOffset === null) return;

    const commentCount = this.props.commentCount;

    // Get the range of visible content in the scroll view from the event.
    const offset = event.nativeEvent.contentOffset.y - postOffset;
    const viewport = event.nativeEvent.layoutMeasurement.height;

    // The viewport height hasn’t been measured yet.
    if (viewport === 0) return;

    // Get the begin and end offset for the visible content.
    const firstOffset = offset;
    const lastOffset = offset + viewport;

    // Get the beginning index of visible items.
    let first = getIndex(
    this.state.commentChunks,
    this.state.commentHeights,
    firstOffset,
    );
    first -= 1;
    if (first < 0) first = 0;

    // Get the ending index of visible items.
    let last = getIndex(
    this.state.commentChunks,
    this.state.commentHeights,
    lastOffset,
    );
    if (last > commentCount) last = commentCount;

    // Update the visible range if it changed.
    this.setState(prevState => {
    if (
    prevState.visibleRange.first === first &&
    prevState.visibleRange.last === last
    ) {
    return null;
    }
    return {
    visibleRange: {first, last},
    };
    });
    };

    /**
    * The offset in measurement units of the post content rendered above our list
    * of comments.
    */
    private postOffset: number | null = null;

    /**
    * When the container’s layout changes we fire this event...
    */
    private handleContainerLayout = (event: LayoutChangeEvent) => {
    this.postOffset = event.nativeEvent.layout.y;
    };

    /**
    * When we detect a layout change in a comment, we wait to see if other
    * comments have layout changes as well.
    */
    private pendingCommentHeights: {
    important: boolean;
    heights: Array<{index: number; height: number}>;
    } | null = null;

    /**
    * Is the next comment height flush important? If true when we call
    * `flushCommentHeights()` then we will automatically make the
    * flush important.
    *
    * If our comment data is loaded when our virtualized comment list is
    * mounted then the next flush is important since we don’t want the
    * shimmers to flicker in.
    */
    private nextCommentHeightsFlushImportant = this.props.loading === false;

    /**
    * When a comment’s layout changes we fire this event...
    */
    private handleCommentLayout: HandleCommentLayout = (
    index: number,
    comment: PostCommentsCacheEntry,
    event: LayoutChangeEvent,
    ) => {
    const height = event.nativeEvent.layout.height;

    // If we already have the correct height for this comment in our state
    // then don’t bother scheduling an update.
    if (height === this.state.commentHeights[index]) return;

    // We will actually update our state after `setTimeout(f, 0)` finishes. That
    // way if we have, say, five comments which fire their layout events
    // together we’ll only update our state once.
    if (this.pendingCommentHeights === null) {
    this.pendingCommentHeights = {important: false, heights: []};
    if (Platform.OS === "web") {
    // On web, schedule the flush in a micro-tick which will fire before the
    // next paint.
    Promise.resolve().then(() => {
    this.flushCommentHeights();
    });
    } else {
    // On native, use a macro-task since that’s what the message queue uses.
    setTimeout(() => {
    this.flushCommentHeights();
    }, 0);
    }
    }

    // Should we make this batch of pending comment heights important? The
    // answer is yes if:
    //
    // 1. If we are immediately rendering comments after the component mounts.
    // We don’t want to flicker the comment shimmers for a millisecond. We
    // want to show our comments immediately. (This is handled
    // by `nextCommentHeightsFlushImportant`.)
    //
    // 2. If the comment is already measured. If a comment changes size then we
    // need to immediately re-layout everything. If we let the browser paint
    // the new comment then the list will look weird since the comment will
    // fill up more or less of its height.
    //
    // 3. If a comment being measured is a realtime comment. When a comment is
    // added in realtime we don’t want to see the flash of an
    // unmeasured comment.
    this.pendingCommentHeights.important =
    this.pendingCommentHeights.important ||
    this.state.commentHeights[index] !== undefined ||
    comment.realtime === true;

    // Add the pending comment height.
    this.pendingCommentHeights.heights.push({index, height});
    };

    /**
    * We wait until we‘ve collected as many comment heights as we can before
    * flushing them to our state.
    */
    private flushCommentHeights() {
    // If we have no pending comment heights do nothing.
    if (this.pendingCommentHeights === null) return;

    // Reset our pending comment heights.
    const pendingCommentHeights = this.pendingCommentHeights;
    this.pendingCommentHeights = null;

    // Escalate the importance of our flush if we were instructed to.
    if (this.nextCommentHeightsFlushImportant === true) {
    pendingCommentHeights.important = true;
    this.nextCommentHeightsFlushImportant = false;
    }

    function updateState(prevState: State) {
    let newCommentHeights: Array<number | undefined> | undefined;

    // Process our pending comment heights...
    for (let i = 0; i < pendingCommentHeights.heights.length; i++) {
    const {index, height} = pendingCommentHeights.heights[i];

    // If the height did not change then do nothing.
    if (prevState.commentHeights[index] === height) continue;

    // If this is the first height that changed then clone our previous
    // comment heights state.
    if (newCommentHeights === undefined) {
    newCommentHeights = prevState.commentHeights.slice();
    }

    // Set the new height in our new comment heights array.
    newCommentHeights[index] = height;
    }

    // If none of our comment heights changed then don’t update our state!
    if (newCommentHeights === undefined) {
    return null;
    } else {
    // Otherwise, let’s compute our new comment chunks!
    const newCommentChunks: Array<CommentChunk> = [];

    // Loop through all of our comment heights...
    let currentChunk: CommentChunk | undefined;
    for (let i = 0; i < newCommentHeights.length; i++) {
    const height = newCommentHeights[i];

    if (height !== undefined) {
    if (currentChunk === undefined) {
    // If we have a comment height but no chunk then let’s create a
    // new chunk.
    currentChunk = {start: i, length: 1, height};
    newCommentChunks.push(currentChunk);
    } else {
    // If we have a height and a chunk then let’s add to the chunk.
    currentChunk.length += 1;
    currentChunk.height += height;
    }
    } else {
    // If we do not have a height but we do have a chunk then unset
    // the chunk. Next time we see a height we’ll want to create a
    // new chunk.
    if (currentChunk !== undefined) {
    currentChunk = undefined;
    }
    }
    }

    return {
    commentHeights: newCommentHeights,
    commentChunks: newCommentChunks,
    };
    }
    }

    // The first time we flush comment heights from layout we do it
    // synchronously. Otherwise React will yield to the browser which will
    // show the comment shimmers to the user which will immediately flash out of
    // existence when we re-render with the actual comments.
    //
    // To avoid the flash of comment shimmers we schedule a synchronous flush.
    // This may cause us to drop animation frames, but the tradeoff is worth it.
    // We’d much rather avoid the flash if we can.
    if (pendingCommentHeights.important === true) {
    reactSchedulerFlushSync(() => this.setState(updateState));
    } else {
    this.setState(updateState);
    }
    }

    // Memoize the filler view.
    private renderFiller = memoizeLast(renderFiller);

    // Memoize each individual item in a cache so we don’t have to recompute it
    // every time. By wrapping a `memoize()` function in a `memoizeLast()` it has
    // the effect of clearing the `memoize()` cache whenever the `memoizeLast()`
    // parameters change.
    private renderItem = memoizeLast(
    (
    comments: ReadonlyArray<PostCommentsCacheEntry | undefined>,
    commentChunks: ReadonlyArray<CommentChunk>,
    commentHeights: ReadonlyArray<number | undefined>,
    ) =>
    memoize((index: number) =>
    renderItem(
    this.handleCommentLayout, // We know this event handler is constant in our class.
    this.props.scrollViewRef, // Refs are constant objects that are changed via imperative mutation.
    comments,
    commentChunks,
    commentHeights,
    index,
    ),
    ),
    );

    render() {
    const commentCount = this.props.commentCount;
    const actualVisibleRange: RenderRange = this.state.visibleRange;

    // The ranges of items we will render...
    let visibleRange: RenderRange = actualVisibleRange;
    let leadingRange: RenderRange | null = null;
    let trailingRange: RenderRange | null = null;

    // On the initial render, only render the _actually_ visible range.
    if (this.state.initialRender === false) {
    // Add overscan to the visible range. We render more comments off-screen
    // but we don’t report them in our visible range state.
    visibleRange = {
    first: Math.max(actualVisibleRange.first - overscanCount, 0),
    last: Math.min(actualVisibleRange.last + overscanCount, commentCount),
    };

    // We always render some items at the very beginning of the list so that
    // “jump to start” are perceived to render quickly.
    leadingRange = {
    first: 0,
    last: Math.min(leadingCount, commentCount),
    };

    // We always render some items at the very end of the list so that
    // “jump to start” are perceived to render quickly.
    trailingRange = {
    first: Math.max(0, commentCount - trailingCount),
    last: commentCount,
    };

    // Merge the leading range with the visible range if needed.
    if (intersects(visibleRange, leadingRange)) {
    visibleRange = {
    first: Math.min(visibleRange.first, leadingRange.first),
    last: Math.max(visibleRange.last, leadingRange.last),
    };
    leadingRange = null;
    }

    // Merge the trailing range with the visible range if needed.
    if (intersects(visibleRange, trailingRange)) {
    visibleRange = {
    first: Math.min(visibleRange.first, trailingRange.first),
    last: Math.max(visibleRange.last, trailingRange.last),
    };
    trailingRange = null;
    }
    }

    const items: Array<ReactElement> = [];

    // Get the render item function based on our state. The render item function
    // is memoized so it comes with a cache.
    const renderItem = this.renderItem(
    this.props.comments,
    this.state.commentChunks,
    this.state.commentHeights,
    );

    // If we have a leading range then render the items in our leading range.
    if (leadingRange) {
    for (let i = 0; i < leadingRange.last - leadingRange.first; i++) {
    items.push(renderItem(leadingRange.first + i));
    }
    }

    // Render the items in our visible range.
    for (let i = 0; i < visibleRange.last - visibleRange.first; i++) {
    items.push(renderItem(visibleRange.first + i));
    }

    // If we have a trailing range then render the items in our trailing range.
    if (trailingRange) {
    for (let i = 0; i < trailingRange.last - trailingRange.first; i++) {
    items.push(renderItem(trailingRange.first + i));
    }
    }

    return (
    <View style={styles.container} onLayout={this.handleContainerLayout}>
    {this.renderFiller(
    this.state.commentChunks,
    this.state.commentHeights,
    this.props.commentCount,
    )}
    {items}
    </View>
    );
    }
    }

    /**
    * Gets the offset above the item at a given index.
    *
    * The dual of this function is `getIndex()` where we can get an index from
    * an offset.
    */
    function getOffset(
    commentChunks: ReadonlyArray<CommentChunk>,
    commentHeights: ReadonlyArray<number | undefined>,
    maxIndex: number,
    ): number {
    // Set the initial offset and index. The offset is a distance in measurement
    // units. The index is a position in our comments list.
    let offset = 0;
    let index = 0;

    // Loop through our comment chunks...
    for (let i = 0; i < commentChunks.length; i++) {
    const commentChunk = commentChunks[i];

    // We expect `commentChunks` to be sorted by `commentChunk.index` and we
    // expect that `index` will never exceed the next comment chunk’s starting
    // position based on our implementation below. If these expectations are
    // violated then throw.
    if (index > commentChunk.start) {
    throw new Error(
    `Expected ${index} to be less than or equal to ${commentChunk.start}.`,
    );
    }

    // If our index is less than the next chunk’s starting position then let’s
    // catch up our index to the chunk start.
    if (index < commentChunk.start) {
    // If moving our index to the chunk’s starting index would take us over
    // the maximum index then move our index to the maximum index and break
    // out of the loop. We done.
    if (maxIndex < commentChunk.start) {
    offset += CommentShimmer.getHeight(maxIndex - index, index);
    index = maxIndex;
    break;
    }

    // The area between comment chunks are occupied by `CommentShimmer`
    // components which have a known height. Add that to our offset.
    offset += CommentShimmer.getHeight(commentChunk.start - index, index);
    index = commentChunk.start;
    }

    // At this point, we expect our index to match the start of our
    // comment chunk. We handle both the less than and greater than cases
    // above which will either break out of the loop or set the index equal
    // to our comment chunk start.
    if (index !== commentChunk.start)
    throw new Error(`Expected ${index} to equal ${commentChunk.start}.`);

    // Add this comment chunk’s height to our offset as long as that wouldn’t
    // put us over our `maxIndex`.
    if (index + commentChunk.length <= maxIndex) {
    offset += commentChunk.height;
    index += commentChunk.length;

    // If `index === maxIndex` now then break out of the loop. We’re
    // done here.
    if (index < maxIndex) {
    continue;
    } else {
    break;
    }
    }

    // If adding the entire chunk height would put us over our `maxIndex` then
    // add each comment height to the offset individually. We expect there
    // to be a height for each comment since the comment’s are inside our
    // current chunk.
    while (index < maxIndex) {
    const height = commentHeights[index];
    if (height === undefined) throw new Error("Expected height.");
    offset += height;
    index += 1;
    }

    break;
    }

    // If we our index is still less than our `maxIndex` then let’s add the
    // remaining shimmer height. This could happen when there are fewer chunks
    // then items in the list.
    if (index < maxIndex) {
    offset += CommentShimmer.getHeight(maxIndex - index, index);
    index = maxIndex;
    }

    // Finally, we expect throughout all of this code that in the end our index
    // will end up equaling our `maxIndex`.
    if (index !== maxIndex)
    throw new Error(`Expected ${index} to equal ${maxIndex}.`);

    return offset;
    }

    /**
    * Gets the index of a comment based on its offset in the list.
    *
    * The dual of this operation is `getOffset()` which gets the offset of an
    * item in the list.
    */
    function getIndex(
    commentChunks: ReadonlyArray<CommentChunk>,
    commentHeights: ReadonlyArray<number | undefined>,
    maxOffset: number,
    ): number {
    // Set the initial offset and index. The offset is a distance in measurement
    // units. The index is a position in our comments list.
    let offset = 0;
    let index = 0;

    // Loop through our comment chunks...
    for (let i = 0; i < commentChunks.length; i++) {
    const commentChunk = commentChunks[i];

    // We expect `commentChunks` to be sorted by `commentChunk.index` and we
    // expect that `index` will never exceed the next comment chunk’s starting
    // position based on our implementation below. If these expectations are
    // violated then throw.
    if (index > commentChunk.start) {
    throw new Error(
    `Expected ${index} to be less than or equal to ${commentChunk.start}.`,
    );
    }

    // Measure the height of comment shimmers between our current index and the
    // start of the next chunk.
    const shimmerHeight = CommentShimmer.getHeight(
    commentChunk.start - index,
    index,
    );

    // If adding the shimmers will surpass the max offset, then let’s get our
    // specific index inside the shimmers and break out of the comment
    // chunk loop.
    if (offset + shimmerHeight >= maxOffset) {
    index += CommentShimmer.getIndex(maxOffset - offset, index);
    offset = maxOffset;
    break;
    }

    // Add our shimmer height and update our index to the chunk’s
    // starting position.
    offset += shimmerHeight;
    index = commentChunk.start;

    // If increasing the offset by the comment chunk length puts us above our
    // desired offset then we move backwards through the comment list to
    // arrive at the correct index.
    if (offset + commentChunk.height >= maxOffset) {
    while (offset < maxOffset) {
    const height = commentHeights[index];
    if (height === undefined) throw new Error("Expected height.");
    offset += height;
    index += 1;
    }
    offset = maxOffset;
    break;
    }

    // Otherwise, increase our index by the comment chunk length.
    offset += commentChunk.height;
    index += commentChunk.length;
    }

    // If we run out of comment chunks but we are still below our desired offset
    // then use comment shimmers to get to our final offset.
    if (offset < maxOffset) {
    index += CommentShimmer.getIndex(maxOffset - offset, index);
    offset = maxOffset;
    }

    return index;
    }

    /**
    * Renders the filler space for the entire list.
    *
    * We implement this outside of the component class so that we’re forced to
    * explicitly declare all of our dependencies. That way a memoization function
    * can correctly determine when the result should change.
    */
    function renderFiller(
    commentChunks: ReadonlyArray<CommentChunk>,
    commentHeights: ReadonlyArray<number | undefined>,
    commentCount: number,
    ) {
    const height =
    getOffset(commentChunks, commentHeights, commentCount) + Space.space3;
    return <View style={{height}} />;
    }

    /**
    * Renders an individual comment in the entire comment list.
    *
    * We implement this outside of the component class so that we’re forced to
    * explicitly declare all of our dependencies. That way a memoization function
    * can correctly determine when the result should change.
    */
    function renderItem(
    handleCommentLayout: HandleCommentLayout,
    scrollViewRef: React.RefObject<ScrollView>,
    comments: ReadonlyArray<PostCommentsCacheEntry | undefined>,
    commentChunks: ReadonlyArray<CommentChunk>,
    commentHeights: ReadonlyArray<number | undefined>,
    index: number,
    ): ReactElement {
    const comment = comments[index];
    const lastComment = comments[index - 1];
    const commentHeight = commentHeights[index];
    const offset = getOffset(commentChunks, commentHeights, index);

    // On web, use a `div` directly which is more efficient since we don’t
    // need the extra component.
    const ViewComponent = Platform.OS === "web" ? "div" : View;

    return (
    <React.Fragment key={index}>
    {comment !== undefined && (
    <View
    style={{
    position: "absolute",
    top: offset,
    left: 0,
    right: 0,
    opacity: commentHeight === undefined ? 0 : 1,
    }}
    onLayout={event => handleCommentLayout(index, comment, event)}
    >
    <Comment
    commentID={comment.id}
    lastCommentID={lastComment !== undefined ? lastComment.id : null}
    scrollViewRef={scrollViewRef}
    />
    </View>
    )}
    {(comment === undefined || commentHeight === undefined) && (
    <ViewComponent
    style={{
    position: "absolute",
    top: offset,
    left: 0,
    right: 0,
    }}
    >
    <CommentShimmer index={index} />
    </ViewComponent>
    )}
    </React.Fragment>
    );
    }

    type HandleCommentLayout = (
    index: number,
    comment: PostCommentsCacheEntry,
    event: LayoutChangeEvent,
    ) => void;

    /**
    * Do the two ranges intersect with one another? Returns true if they intersect.
    */
    function intersects(a: RenderRange, b: RenderRange): boolean {
    return !(a.last < b.first || b.last < a.first);
    }

    const styles = StyleSheet.create({
    container: {
    overflow: "hidden",
    },
    });

    /**
    * Caches the last result of a function. If the function is immediately called
    * again with the same arguments then we will re-use the last result without
    * calling the function again.
    */
    function memoizeLast<Args extends Array<any>, Ret>(
    fn: (...args: Args) => Ret,
    ): (...args: Args) => Ret {
    // The internal cache of our memoization function.
    let cache: {args: Args; ret: Ret} | null = null;

    return (...args: Args): Ret => {
    // If we have a previous cached value...
    if (cache !== null) {
    let equal = true;

    // Determine if the argument arrays are equal...
    if (args.length !== cache.args.length) {
    equal = false;
    } else {
    for (let i = 0; i < args.length; i++) {
    if (args[i] !== cache.args[i]) {
    equal = false;
    break;
    }
    }
    }

    // If the argument arrays are equal then return our cached value.
    if (equal === true) {
    return cache.ret;
    }
    }

    // Otherwise compute the return value and cache the result.
    const ret = fn(...args);
    cache = {args, ret};
    return ret;
    };
    }

    /**
    * Memoize all the results of a function. If we’ve seen an argument before at
    * any point in time then we will return the same value without recomputing
    * anything. If we haven’t seen the argument then we will compute the
    * return value.
    */
    function memoize<Arg, Ret>(fn: (arg: Arg) => Ret): (arg: Arg) => Ret {
    const cache = new Map<Arg, Ret>();
    return arg => {
    let ret = cache.get(arg);
    if (ret === undefined) {
    ret = fn(arg);
    cache.set(arg, ret);
    }
    return ret;
    };
    }

    // Export some of our utility functions for testing.
    export {getIndex as test_getIndex};