ClojureScript

Clarify IFind contract to avoid double-lookups

Details

  • Type: Enhancement Enhancement
  • Status: Closed Closed
  • Priority: Minor Minor
  • Resolution: Completed
  • Affects Version/s: 1.9.518, 1.9.521, 1.9.542, 1.9.562, 1.9.655, 1.9.660
  • Fix Version/s: None
  • Component/s: None
  • Labels:
    None
  • Patch:
    Code and Test
  • Approval:
    Accepted

Description

The IFind protocol introduced by CLJS-1497 (early April) had an ambiguity about whether -find implementors were responsible for the key containment checks or should assume the key was already present (i.e., never return nil). CLJS-1497 changed find? such that containment checks were always done first and -find was only looked for after. However CLJS-2013 (MapEntry and tree node fixups) was unclear about the contract and implemented -find with a key check and nil case. It also added this comment to its tests:

cljs.map-entry-test
;; Commented out as unsure about contract of -find 
          ;; in the case where key is not present.
          ;nil (-find e 2)
          ;nil (-find e -1)
          ;; So testing `find` in this case instead as contract is clear.
          nil (find e 2)
          nil (find e -1)

This patch:

  • Clarifies the contract of IFind to require that the implementor also perform the key check. The IFind protocol docstring is updated to reflect this. The advantage of requiring -find to do the key check (vs find) is that for some data structures find can avoid looking up an entry twice.
  • Changes find to test for and use IFind first rather than testing for containment first.
  • Changes all IFind implementations in core to perform key checks. Each implementation is careful to do lookups only once (rather than one lookup to test for key presence and another one to retrieve the value).
  • Adds some more tests for find on a vector using degenerate keys.
  • Changes the above-quoted map entry test to use -find directly, and removes the comment about ambiguity.

Activity

Hide
David Nolen added a comment -

The docstring change to IFind protocol is not desirable.

Show
David Nolen added a comment - The docstring change to IFind protocol is not desirable.
Hide
Francis Avila added a comment -

Removed changes to IFind docstrings. But I really think something should be written in the docstring so implementors know they may need to return nil. This was the point of confusion in CLJS-2013 that motivated this ticket in the first place.

Show
Francis Avila added a comment - Removed changes to IFind docstrings. But I really think something should be written in the docstring so implementors know they may need to return nil. This was the point of confusion in CLJS-2013 that motivated this ticket in the first place.
Hide
Francis Avila added a comment -

Updated patch:

  • After discussion with David Nolen, added back in a IFind docstring on the -find method itself documenting return value (same docstring as find.
  • Thomas Mulvaney noticed the unpacking of RedNode/BlackNode into a vector as done by the PersistentTreeMap impl of -find was unnecessary, so that change was removed.
Show
Francis Avila added a comment - Updated patch:
  • After discussion with David Nolen, added back in a IFind docstring on the -find method itself documenting return value (same docstring as find.
  • Thomas Mulvaney noticed the unpacking of RedNode/BlackNode into a vector as done by the PersistentTreeMap impl of -find was unnecessary, so that change was removed.
Hide
David Nolen added a comment - - edited

Apologies for not being more clear and more specific. I only had issues with discussing implementation details related to containment check in the docstring.

Show
David Nolen added a comment - - edited Apologies for not being more clear and more specific. I only had issues with discussing implementation details related to containment check in the docstring.
Hide
Francis Avila added a comment -

Mentioned docstring change in commit message, and added in the changes to the map-entry tests which somehow got lost in the last uploaded patch.

Show
Francis Avila added a comment - Mentioned docstring change in commit message, and added in the changes to the map-entry tests which somehow got lost in the last uploaded patch.

People

Vote (0)
Watch (1)

Dates

  • Created:
    Updated:
    Resolved: