Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

feat: handle nested arrays with wildcard keys #120

Conversation

mart-jansink
Copy link
Contributor

What: Handle nested arrays with one or more wildcard keys. As an example

const nestedObjList = [
  {aliases: [{name: {first: 'Janice'}},{name: {first: 'Jen'}}]},
  {aliases: [{name: {first: 'Fred'}},{name: {first: 'Frederic'}}]},
  {aliases: [{name: {first: 'George'}},{name: {first: 'Georgie'}}]},
]
matchSorter(nestedObjList, 'jen', {keys: ['aliases.*.name.first']})
// [{aliases: [{name: {first: 'Janice'}},{name: {first: 'Jen'}}]}]
matchSorter(nestedObjList, 'jen', {keys: ['aliases.name.first']})
// [{aliases: [{name: {first: 'Janice'}},{name: {first: 'Jen'}}]}]
matchSorter(nestedObjList, 'jen', {keys: ['aliases.0.name.first']})
// []

Why: Arrays like the above are relatively common in some applications that I'm working on. I really like the intuitive sorting of match-sorter so I'd love to be able to use this. However, using property callbacks for such a common case isn't ideal. So I thought I'd try making a pull request, hoping that this is something you might consider for merging.

How: The .reduce callback inside the getNestedValue function has gotten a lot more logic to possibly handle arrays. The calling getItemValues function now always returns an array, which simplifies the logic that returns the value a bit. Both the explicit 'aliases.*.name.first' and implicit 'aliases.name.first' wildcards are supported with this implementation; it was simpler to implement the latter while the former is clearer in use.

Checklist:

  • Documentation
  • Tests
  • Ready to be merged

I sadly had some trouble running npm run test:update: it complains that not all branches are covered by the test cases. However, the lines that it says are uncovered are actually called, as far as I can tell, so I couldn't fix this..

Copy link
Owner

@kentcdodds kentcdodds left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks for your work on this. I'm worried that this is adding a little too much magic to the library, especially when you can already work around this limitation in a pretty reasonable way using "Property Callbacks" (see the README).

@mart-jansink
Copy link
Contributor Author

Thanks for your feedback. I understand the concern, but to me it seems that this library is already doing quite a bit of "magic" when it comes to sorting the results, and supporting nested keys in the first place. Of course that "magic" is well documented but so can this.

Since the applications I'm working on use the pattern of nested objects in arrays relatively often, writing similar property callbacks all the time isn't really DRY nor as performant as this can be. But if I'm the outlier in this, I'm more than happy to keep using a fork.

@kentcdodds
Copy link
Owner

Fair points. Luckily the added code isn't all that complex which is nice. I think this will be ok, but I'd like to see what this looks like documented first. Also, could you make sure we hit 100% test coverage with your new changes. Thanks!

@mart-jansink mart-jansink force-pushed the pr/handle-nested-arrays-with-wildcard-keys branch 2 times, most recently from 2b5a576 to eb19d72 Compare December 25, 2020 21:41
@mart-jansink mart-jansink force-pushed the pr/handle-nested-arrays-with-wildcard-keys branch from eb19d72 to 0195d3e Compare December 25, 2020 21:43
@codecov
Copy link

codecov bot commented Dec 25, 2020

Codecov Report

Merging #120 (d91842f) into master (4c2e927) will not change coverage.
The diff coverage is 100.00%.

Impacted file tree graph

@@            Coverage Diff            @@
##            master      #120   +/-   ##
=========================================
  Coverage   100.00%   100.00%           
=========================================
  Files            1         1           
  Lines          137       163   +26     
  Branches        31        38    +7     
=========================================
+ Hits           137       163   +26     
Impacted Files Coverage Δ
src/index.ts 100.00% <100.00%> (ø)

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 4c2e927...d91842f. Read the comment docs.

@mart-jansink
Copy link
Contributor Author

Thanks. The coverage is now back up to 100% again. And I've documented the changes more clearly.

While doing this I also found a few simple performance improvements that end up to matching about 20% faster. The biggest improvements were

  • not .concatenating arrays anymore, since they are never modified anyway there's no harm in using any given arrays directly
  • caching the length of the strings that are being for-looped over

I can't directly share the data that I used for benchmarking this, but I can look for something similar if you want?

src/index.ts Outdated
return value
}

return value.reduce((values: Array<object | string>, arrayValue: object | null):
Copy link
Owner

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This looks a lot like the first part of the function. I wonder if we could use recursion instead of duplication here. Could you try it out and see whether it's any simpler?

Copy link
Contributor Author

@mart-jansink mart-jansink Dec 27, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Sure, see the last commit which is my attempt at doing so. It seems possible without any performance implications.

However, there is the downside that the implicit wildcard no longer works, except if the array is a top-level property of the object. So {favoriteIceCream: ['mint', 'chocolate']} is fine when matching 'favoriteIceCream', but {favorite: {iceCream: ['mint', 'chocolate']}} won't work with 'favorite.iceCream' and instead needs 'favorite.iceCream.*'. I personally don't care about implicit wildcards: I never added this intentionally. It just worked due to the checks that made this new feature backwards compatible with all tests. And it's these checks that caused the duplication and are now gone. Supporting nested array values without explicit wildcards again would require more duplication I'm afraid.

The README doesn't explicitly say that nested array values are supported. It says that array values are supported and nested values are supported, but nothing about combining that. But as a user I'd assume that they would be, so now this new feature would be a breaking change.

Copy link
Owner

@kentcdodds kentcdodds left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think we should be able to make this work with recursion. Care to take another whack at it?

{favorite: {iceCream: ['birthday cake', 'rocky road', 'strawberry']}},
],
'cc',
{keys: ['favorite.iceCream.*']},
Copy link
Owner

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm fine with this working, but I'd also like to support favorite.iceCream here as well. We should be able to process an item of String | Array<String> and favorite.icCream is Array<String>.

null,
],
'ba',
{keys: ['aliases.name.first']},
Copy link
Owner

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't want to support this. It's too much magic. So I'm glad that it's gone.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Me too.

@mart-jansink
Copy link
Contributor Author

Yeah, I'll have another go at it.

@mart-jansink
Copy link
Contributor Author

mart-jansink commented Dec 27, 2020

How do you feel about the use of .flat()? That could solve the problem but it isn't supported by IE, see https://caniuse.com/mdn-javascript_builtins_array_flat.

@kentcdodds
Copy link
Owner

I'm fine with flat. Folks should have standard polyfills by now

tsconfig.json Outdated
"extends": "./node_modules/kcd-scripts/shared-tsconfig.json"
"extends": "./node_modules/kcd-scripts/shared-tsconfig.json",
"compilerOptions": {
"lib": ["es2019"]
Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm not sure if this is the best way / place / solution, but without this addition type checking fails with the error Property 'flat' does not exist on type 'string[]'. Do you need to change your target library? Try changing the lib compiler option to 'es2019' or later..

@mart-jansink
Copy link
Contributor Author

OK, it now supports 'favorite.iceCream' again. The validation fails because node v10 doesn't have .flat() yet. We can also use a small polyfill like [].concat.apply([],values) instead?

@kentcdodds
Copy link
Owner

Let's use the small polyfill idea 👍

@mart-jansink mart-jansink force-pushed the pr/handle-nested-arrays-with-wildcard-keys branch from 3030099 to 895c231 Compare December 28, 2020 15:13
@mart-jansink
Copy link
Contributor Author

There you go. I'm kinda stumped by the typing of the result, so I had to expect a few more errors than I'd like. Also, I've added a check to see if flattening is needed because it's quite expensive for the performance.

Copy link
Owner

@kentcdodds kentcdodds left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I made a couple commits to hopefully improve things a bit. I think it'll help perf, but I'm pretty sure removing the reduces and using for..of loops improves readability.

I also removed all // @ts-expect-errors in favor of casting which I think is the lesser of the two evils.

I'd love your feedback. I'm happy to make adjustments to my changes before we merge this.

Thanks again for all your work on this!

@mart-jansink
Copy link
Contributor Author

That's perfect, it's much more readable indeed. I've never been a big fan of functional programming because it typically comes with a large performance penalty. But in this case I just stuck with how you had coded it.

Looking at the performance there was some degradation due to the use of for-of loops which are transpiled to support arbitrary iterators besides plain arrays. So I've refactored that once more using old-fashioned for loops, also including those in the getAllValuesToRank function.

My basic benchmark now gives the following results, comparing the last variations this branch to the master:

master x 409 ops/sec ±0.64% (86 runs sampled)
reduce x 448 ops/sec ±1.75% (83 runs sampled)
for-of x 424 ops/sec ±0.48% (85 runs sampled)
for    x 475 ops/sec ±0.34% (87 runs sampled)

So I'm perfectly happy with merging it like this.

On a side note: I can make pull request for a benchmark like this if you'd want? And, looking at my use-case of this module, I see room for more performance improvements by doing some memoization. My apps show 1000+ rows that are recursively processed multiple times while users type, or when just a few of those rows change due to server updates. Memoizing getAllValuesToRank, getHighestRanking and / or getMatchRanking would greatly reduce the amount of duplicate work that's done.

Copy link
Owner

@kentcdodds kentcdodds left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks great to me. Thank you!

If you'd like to add a benchmark test in the future that would be welcome 👍

@kentcdodds kentcdodds merged commit b3d9d8d into kentcdodds:master Dec 31, 2020
@kentcdodds
Copy link
Owner

@all-contributors please add @mart-jansink for code, tests, and docs

@allcontributors
Copy link
Contributor

@kentcdodds

I've put up a pull request to add @mart-jansink! 🎉

@kentcdodds
Copy link
Owner

Thanks so much for your help! I've added you as a collaborator on the project. Please make sure that you review the other/MAINTAINING.md and CONTRIBUTING.md files (specifically the bit about the commit messages and the git hooks) and familiarize yourself with the code of conduct (we're using the contributor covenant). You might also want to watch the repo to be notified when someone files an issue/PR. Please continue to make PRs as you feel the need (you can make your branches directly on the repo rather than your fork if you want). Thanks! And welcome to the team :)

@github-actions
Copy link

🎉 This PR is included in version 6.1.0 🎉

The release is available on:

Your semantic-release bot 📦🚀

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants