REBOL3 tracker
  0.9.12 beta
Ticket #0002220 User: anonymous

Project:

Previous Next
rss
TypeBug Statussubmitted Date10-Jun-2015 06:44
Versionr3 master CategoryDatatype Submitted byabolka
PlatformAll Severitymajor Prioritynormal

Summary map!: problem with externally modified keys
Description The key values used in a map! are not deep-copied during map creation (or related map operations). This is, most likely, intentional.

However, this also creates the problem that keys can be modified after they have already been hashed. Which results in the bad behaviour shown in the example code.

NB: You need a map! with 8+ entries to observe this, otherwise a map! won't hash internally.
Example code
;; Create a map with 8+ entries. Keep a ref to the last key in K.
>> m: make map! collect [repeat i 8 [keep k: join "key" i keep i]]
== make map! [
    "key1" 1
    "key2" 2
    "key3" 3
    "key4" 4
    "key5" 5
    "key6" 6
    "key7" 7
    "key8" 8
]

>> k
== "key8"

;; Modify the string of one key.
>> append k "foobar"
== "key8foobar"

;; As keys are not (deep) copied during map! creation, above
;; modification is also reflected in the map:
>> m
== make map! [
    "key1" 1
    "key2" 2
    "key3" 3
    "key4" 4
    "key5" 5
    "key6" 6
    "key7" 7
    "key8foobar" 8
]

;; However ...

>> select m "key8foobar" 
== none  ;; Bad!

>> select m k
== none  ;; Bad!

Assigned ton/a Fixed in- Last Update16-Jul-2015 06:50


Comments
(0004645)
abolka
10-Jun-2015 06:50

So far, I have not really come up with a good solution, only with three bad variations:

1. Always (deep) copy keys. Don't allow them to be modified externally.

2. Document this badness, implement the UPDATE action for map! for forced re-hashing and put the burden on the user to re-hash all affected maps after external key modification.

3. If hashed key lookup fails, fall back on a linear search to ensure the key is really not present.

Approach (3) is just listed for the sake of completeness. As (3) would render map!s at least half useless for their intended use cases, it really is _no_ solution at all.

(NB: Red currently faces a similar problem.)
(0004646)
rgchris
16-Jul-2015 06:50

Current behaviour also allows for seemingly duplicate keys:

probe select m "key8"
change back tail k "1"
probe select m "key 8"
m/("key1"): none
probe select m "key1"

Date User Field Action Change
16-Jul-2015 06:50 rgchris Comment : 0004646 Added -
10-Jun-2015 06:57 abolka Comment : 0004645 Modified -
10-Jun-2015 06:50 abolka Comment : 0004645 Modified -
10-Jun-2015 06:50 abolka Comment : 0004645 Added -
10-Jun-2015 06:44 abolka Ticket Added -