Angular 2, ngrx/store, RxJS and tree-like data

Question

I've been trying to figure out a way to use the select operator in combination with rxjs's other operators to query a tree data structure (normalized in the store to a flat list) in such a way that it preserves referential integrity for ChangeDetectionStrategy.OnPush semantics but my best attempts cause the entire tree to be rerendered when any part of the tree changes. Does anyone have any ideas? If you consider the following interface as representative of the data in the store:

export interface TreeNodeState {
 id: string;
 text: string;
 children: string[] // the ids of the child nodes
}
export interface ApplicationState {
 nodes: TreeNodeState[]
}

I need to create a selector that denormalizes the state above to return a graph of objects implementing the following interface:

export interface TreeNode {
 id: string;
 text: string;
 children: TreeNode[]
}

That is, I need a function that takes an Observable<ApplicationState> and returns an Observable<TreeNode[]> such that each TreeNode instance maintains referential integrity unless one of its children has changed.

Ideally I'd like to have any one part of the graph only update its children if they've changed rather than return an entirely new graph when any node changes. Does anyone know how such a selector could be constructed using ngrx/store and rxjs?

For more concrete examples of the kinds of things I've attempted check out the snippet below:

// This is the implementation I'm currently using. 
// It works but causes the entire tree to be rerendered
// when any part of the tree changes.
export function getSearchResults(searchText: string = '') {
    return (state$: Observable<ExplorerState>) =>
        Observable.combineLatest(
            state$.let(getFolder(undefined)),
            state$.let(getFolderEntities()),
            state$.let(getDialogEntities()),
            (root, folders, dialogs) =>
                searchFolder(
                    root,
                    id => folders ? folders.get(id) : null,
                    id => folders ? folders.filter(f => f.parentId === id).toArray() : null,
                    id => dialogs ? dialogs.filter(d => d.folderId === id).toArray() : null,
                    searchText
                )
        );
}

function searchFolder(
    folder: FolderState,
    getFolder: (id: string) => FolderState,
    getSubFolders: (id: string) => FolderState[],
    getSubDialogs: (id: string) => DialogSummary[],
    searchText: string
): FolderTree {
  console.log('searching folder', folder ? folder.toJS() : folder);
  const {id, name } = folder;
  const isMatch = (text: string) => !!text && text.toLowerCase().indexOf(searchText) > -1;
  return {
    id,
    name,
    subFolders: getSubFolders(folder.id)
        .map(subFolder => searchFolder(
            subFolder,
            getFolder,
            getSubFolders,
            getSubDialogs,
            searchText))
      .filter(subFolder => subFolder && (!!subFolder.dialogs.length || isMatch(subFolder.name))),
    dialogs: getSubDialogs(id)
      .filter(dialog => dialog && (isMatch(folder.name) || isMatch(dialog.name)))

  } as FolderTree;
}

// This is an alternate implementation using recursion that I'd hoped would do what I wanted
// but is flawed somehow and just never returns a value.
export function getSearchResults2(searchText: string = '', folderId = null)
: (state$: Observable<ExplorerState>) => Observable<FolderTree> {
    console.debug('Searching folder tree', { searchText, folderId });
    const isMatch = (text: string) =>
        !!text && text.search(new RegExp(searchText, 'i')) >= 0;
    return (state$: Observable<ExplorerState>) =>
        Observable.combineLatest(
            state$.let(getFolder(folderId)),
            state$.let(getContainedFolders(folderId))
                .flatMap(subFolders => subFolders.map(sf => sf.id))
                .flatMap(id => state$.let(getSearchResults2(searchText, id)))
                .toArray(),
            state$.let(getContainedDialogs(folderId)),
            (folder: FolderState, folders: FolderTree[], dialogs: DialogSummary[]) => {
                console.debug('Search complete. constructing tree...', {
                    id: folder.id,
                    name: folder.name,
                    subFolders: folders,
                    dialogs
                });
                return Object.assign({}, {
                    id: folder.id,
                    name: folder.name,
                    subFolders: folders
                        .filter(subFolder =>
                            subFolder.dialogs.length > 0 || isMatch(subFolder.name))
                        .sort((a, b) => a.name.localeCompare(b.name)),
                    dialogs: dialogs
                        .map(dialog => dialog as DialogSummary)
                        .filter(dialog =>
                            isMatch(folder.name)
                            || isMatch(dialog.name))
                        .sort((a, b) => a.name.localeCompare(b.name))
                }) as FolderTree;
            }
        );
}

// This is a similar implementation to the one (uses recursion) above but it is also flawed.
export function getFolderTree(folderId: string)
: (state$: Observable<ExplorerState>) => Observable<FolderTree> {
    return (state$: Observable<ExplorerState>) => state$
        .let(getFolder(folderId))
        .concatMap(folder =>
            Observable.combineLatest(
                state$.let(getContainedFolders(folderId))
                    .flatMap(subFolders => subFolders.map(sf => sf.id))
                    .concatMap(id => state$.let(getFolderTree(id)))
                    .toArray(),
                state$.let(getContainedDialogs(folderId)),
                (folders: FolderTree[], dialogs: DialogSummary[]) => Object.assign({}, {
                    id: folder.id,
                    name: folder.name,
                    subFolders: folders.sort((a, b) => a.name.localeCompare(b.name)),
                    dialogs: dialogs.map(dialog => dialog as DialogSummary)
                        .sort((a, b) => a.name.localeCompare(b.name))
                }) as FolderTree
            ));
}

Answer 1

If willing to rethink the problem, you could use Rxjs operator scan:

1. If no previous ApplicationState exists, accept the first one. Translate it to TreeNodes recursively. As this is an actual object, rxjs isn't involved.
2. Whenever a new application state is received, ie when scan fires, implement a function that mutates the previous nodes using the state received, and returns the previous nodes in the scan operator. This will guarantee you referential integrity.
3. You might now be left with a new problem, as changes to mutated tree nodes might not be picked up. If so, either look into track by by making a signature for each node, or consider adding a changeDetectorRef to a node (provided by component rendering node), allowing you to mark a component for update. This will likely perform better, as you can go with change detection strategy OnPush.

Pseudocode:

state$.scan((state, nodes) => nodes ? mutateNodesBy(nodes, state) : stateToNodes(state))

The output is guaranteed to preserve referential integrity (where possible) as nodes are built once, then only mutated.