psteckler
commented
1 year ago In berkeley, Hashtbl functions:
$ git grep Hashtbl.iter
src/lib/crypto/kimchi_backend/common/plonk_constraint_system.ml: Hashtbl.iteri sys.equivalence_classes ~f:(fun ~key ~data ->
// (1) result placed in a set
src/lib/crypto/kimchi_backend/common/plonk_constraint_system.ml: Hashtbl.iter equivalence_classes ~f:(fun ps ->
// ***
src/lib/downloader/downloader.ml: Hashtbl.iter temporary_ignores ~f:(fun e ->
// (7) order doesn't matter here; this data structure only used internally; here it's only doing cleaning-ups
src/lib/downloader/downloader.ml: Hashtbl.iter knowledge ~f:Knowledge.clear ;
// (7) order doesn't matter here; this data structure only used internally; here it's only doing cleaning-ups
src/lib/downloader/downloader.ml: Hashtbl.iter t.knowledge ~f:(fun s ->
// (7) order doesn't matter here; this data structure is only used internally; here it's only doing cleaning-ups
src/lib/downloader/downloader.ml: Hashtbl.iter t.knowledge ~f:(fun s ->
// (7) order doesn't matter here; this data structure is only used internally; here it's only doing cleaning-ups
src/lib/downloader/downloader.ml: Hashtbl.iter downloading ~f:(fun (_, j, _) -> kill_job t j) ;
// (7) order doesn't matter here; this data structure is only used internally; here it's only doing cleaning-ups
src/lib/downloader/downloader.ml: Hashtbl.iter jobs ~f:(fun x ->
// (7) the order of things that we enqueue doesn't matter; this data structure is only used internally; here it's used for cleaning up
--
src/lib/ledger_catchup/super_catchup.ml: let iter_vertex (f : V.t -> unit) (t : t) = Hashtbl.iter t.nodes ~f
// (3) used in argument to Graphviz functor to enumerate vertice, edges, not part of protocol
src/lib/ledger_catchup/super_catchup.ml: Hashtbl.iter t.nodes ~f:(fun child ->
// (3) used in argument to Graphviz functor to enumerate vertice, edges, not part of protocol
--
src/lib/ledger_catchup/super_catchup.ml: Hashtbl.iter t.nodes ~f:(fun node ->
// (3) used in debug logs, not part of protocol
src/lib/ledger_catchup/super_catchup.ml: Hashtbl.iter t.nodes ~f:(fun node ->
// (3) used in debug logs, not part of protocol
--
src/lib/mina_net2/libp2p_helper.ml: Hashtbl.iter t.outstanding_requests ~f:(fun iv ->
// (7) fills Ivar for all outstanding requests, order doesn't seem important
--
src/lib/network_pool/snark_pool.ml: Hashtbl.iteri t.rebroadcastable ~f:(fun ~key ~data:(x, r) ->
// (1) used to construct another hash table
--
src/lib/o1trace/plugins.ml:let dispatch f = Hashtbl.iter plugins ~f
// (3) plugins for tracing, not part of protocol
--
src/lib/o1trace/thread.ml:let iter_threads ~f = Hashtbl.iter threads ~f
// (3) for tracing, not part of protocol
--
src/lib/rocksdb/database.ml: Hashtbl.iteri db_hashtbl ~f:(fun ~key ~data ->
// (3) in unit test to set values in db, not part of protocol
--
src/lib/transition_frontier/full_catchup_tree.ml: Hashtbl.iter nodes ~f:(fun x ->
// (7) in `tear_down`, fills `Ivar` for some nodes, order doesn't seem important
--
src/lib/transition_frontier/full_frontier/full_frontier.ml:let iter t ~f = Hashtbl.iter t.table ~f:(fun n -> f n.breadcrumb)
// (8) Full_frontier.iter required by interface, not called anywhere
src/lib/transition_frontier/full_frontier/full_frontier.ml: Hashtbl.iter t.table ~f:(fun node ->
// (1, 8) used to build another hash table used only for metrics
--
src/lib/transition_handler/catchup_scheduler.ml: Hashtbl.iter collected_transitions
// (7) internal cleanup, order doesn't seem important
src/lib/transition_handler/catchup_scheduler.ml: Hashtbl.iter parent_root_timeouts ~f:(fun timeout ->
// (7) internal cleanup, order doesn't seem important
--
$ git grep Hashtbl.to_alist
--
src/lib/consensus/proof_of_stake.ml: ( Hashtbl.to_alist delegatee_table
// (4) JSON output, not part of protocol
src/lib/consensus/proof_of_stake.ml: ( Hashtbl.to_alist delegators
// (4) JSON output, not part of protocol
src/lib/consensus/proof_of_stake.ml: |> Option.value_map ~f:Hashtbl.to_alist ~default:[]
// @nholland94 says OK
--
src/lib/downloader/downloader.ml: (List.map (Hashtbl.to_alist knowledge) ~f:(fun (p, s) ->
// (4) used for logging
src/lib/downloader/downloader.ml: (List.map (Hashtbl.to_alist t.downloading)
// (4) used for logging
src/lib/ledger_catchup/super_catchup.ml: (List.map (Hashtbl.to_alist s) ~f:(fun (k, v) ->
// (4) used for logging
src/lib/ledger_catchup/super_catchup.ml: (List.map (Hashtbl.to_alist s) ~f:(fun (k, v) ->
// (4) used for logging
--
src/lib/mina_commands/mina_commands.ml: (List.map (Hashtbl.to_alist full.states) ~f:(fun (state, hashes) ->
// (3) catchup state in daemon status, not part of protocol
--
src/lib/network_pool/snark_pool.ml: let p t = (Hashtbl.to_alist t.all, Hashtbl.to_alist t.rebroadcastable) in
// fixed in #13511
src/lib/network_pool/snark_pool.ml: Hashtbl.to_alist t.snark_tables.rebroadcastable
// code no longer there
--
src/lib/network_pool/transaction_pool.ml: Hashtbl.to_alist t.locally_generated_uncommitted
// (2) result is sorted
--
src/lib/rocksdb/database.ml: (Hashtbl.to_alist db_hashtbl)
// (2) in unit test, values are sorted anyway, not part of protocol
src/lib/rocksdb/database.ml: (Hashtbl.to_alist cp_hashtbl)
// (2) in unit test, values are sorted anyway, not part of protocol
---
src/lib/staged_ledger_diff/bitswap_block.ml: ( Blake2.Map.of_alist_exn (Hashtbl.to_alist blocks)
// (1) used to build a map, order unimportant
--
src/lib/transaction_snark_scan_state/transaction_snark_scan_state.ml: (List.map (Hashtbl.to_alist t) ~f:(fun (k, info) ->
// (4) logging
--
src/lib/transition_frontier/full_catchup_tree.ml: @@ List.map (Hashtbl.to_alist t.states) ~f:(fun (state, hashes) ->
// (4) for JSON
--
$ git grep Hashtbl.fold
src/lib/downloader/downloader.ml: @ Hashtbl.fold t.knowledge ~init:[] ~f:(fun ~key:p ~data:k acc ->
// (6) There's no preferred order for this collection; the result is only used inside this module
--
src/lib/gossip_net/fake.ml: Hashtbl.fold t.nodes ~init:Deferred.unit
// (8) fake network, not part of protocol
--
src/lib/merkle_mask/masking_merkle_tree.ml: Hashtbl.fold t.token_owners ~init:Account_id.Set.empty
// (1) used to create a set, order irrelevant
--
src/lib/transition_frontier/catchup_hash_tree.ml: Hashtbl.fold t.nodes ~init:[] ~f:(fun ~key ~data acc ->
// (7) used to build a list which is iterated over
---
src/lib/transition_frontier/full_catchup_tree.ml: Hashtbl.fold t.states ~init ~f:(fun ~key ~data acc ->
// (3, 8) for node status report
src/lib/transition_frontier/full_catchup_tree.ml: Hashtbl.fold t.nodes ~init:0 ~f:(fun ~key:_ ~data acc ->
// (7) finding a max element
src/lib/transition_frontier/full_catchup_tree.ml: Hashtbl.fold t.nodes ~init:[] ~f:(fun ~key:_ ~data acc ->
// (7) builds a list for node for removal, order not important
--
src/lib/transition_frontier/full_frontier/full_frontier.ml: let fold t ~f = Hashtbl.fold t.table ~f:(fun ~key:_ ~data -> f data)
// (8) for visualization
--
$ git grep Hashtbl.keys
src/app/best_tip_merger/best_tip_merger.ml: List.iter (Hashtbl.keys acc'.init_states) ~f:(fun root ->
// (8) an app, not part of protocol
src/app/cli/src/init/mina_run.ml: Hashtbl.keys child_pids
// (8) kills child processes on crash
src/lib/cache_lib/impl.ml: let to_list t = Hashtbl.keys t.set
// (8) Cache_lib.to_list needed for interface, apparently not used
src/lib/downloader/downloader.ml: , list (List.map ~f:Peer.to_yojson (Hashtbl.keys temporary_ignores))
// (4) used for logs
src/lib/mina_lib/mina_subscriptions.ml: @@ List.filter_opt (Hashtbl.keys subscribed_block_users)
// (1) creates set from list
--
src/lib/transition_frontier/catchup_hash_tree.ml: List.iter (Hashtbl.keys t.nodes) ~f:(fun h ->
// (7) used for pruning, order doesn't seem relevant
--
$ git grep Hashtbl.data
src/app/best_tip_merger/best_tip_merger.ml: List.fold (Hashtbl.data input.init_states) ~init:State_hash.Map.empty
// (8) app, not protocol
src/lib/consensus/proof_of_stake_fuzzer.ml: Option.map (Hashtbl.find dist slot) ~f:Hashtbl.data
// (8), in fuzzer, code is commented out
src/lib/downloader/downloader.ml: @ List.map (Hashtbl.data t.downloading) ~f:(fun (_, j, _) -> j)
// (6) there's no preferred order for this collection, it's only used as an aggregation of things; the client code also didn't depend on order
--
src/lib/gossip_net/fake.ml: Hashtbl.data nodes |> List.concat
// (8) not part of protocol
src/lib/gossip_net/fake.ml: let peers { peer_table; _ } = Hashtbl.data peer_table |> Deferred.return
// (8) not part of protocol
src/lib/gossip_net/fake.ml: Hashtbl.data t.peer_table
// (8) not part of protocol
--
src/lib/mina_net2/mina_net2.ml: Hashtbl.data t.subscriptions
// (7) argument to `List.exists`, so order not important
--
src/lib/transition_frontier/full_frontier/full_frontier.ml: List.map (Hashtbl.data t.table) ~f:(fun { breadcrumb; _ } -> breadcrumb)
// (6) `all_breadcrumbs` clients don't depend on order
Viable Systems recently raised an issue regarding OCaml hashtables having non-deterministic ordering of elements (https://github.com/MinaProtocol/mina/issues/13433). Hash tables in OCaml will iterate over elements in different orders dependent on the initial allocation size of the hash table and insertion order of the elements.
We need to audit our usage of hash tables in the code and make sure that we are not relying on the iteration order of elements in the table for any code which generates values that are stored in types which can be hashed or serialized.