111.03.00

- Added `Error.to_string_hum_deprecated` that is the same as
  `Error.to_string_hum` pre 109.61.
- Changed `Error.to_string_hum` so that
	`Error.to_string_hum (Error.of_string s) = s`.

		This fixed undesirable sexp escaping introduced in 109.61 and
		restores the pre-109.61 behavior for the special case of
		`Error.of_string`.  A consequence of the removal of the custom
		`to_string_hum` converter in 109.61 was that:

		    Error.to_string_hum (Error.of_string s) = Sexp.to_string_hum (Sexp.Atom s)

		That introduced sexp escaping of `s`.

- Added to `Doubly_linked` functions for moving an element
  within a list.

        val move_to_front : 'a t -> 'a Elt.t -> unit
        val move_to_back  : 'a t -> 'a Elt.t -> unit
        val move_after    : 'a t -> 'a Elt.t -> anchor:'a Elt.t -> unit
        val move_before   : 'a t -> 'a Elt.t -> anchor:'a Elt.t -> unit

- Improved `Core_map_unit_tests.Unit_tests` to allow arbitrary data
  in the map, not just `ints`.

		This was done by eta expansion.
111.06.00

- Added inline benchmarks for `Array`

  Hera are some of the results from the new benchmarks, with some
  indexed tests dropped.

  | Name                                                |    Time/Run | mWd/Run |  mjWd/Run |
  |-----------------------------------------------------|-------------|---------|-----------|
  | [core_array.ml:Alloc] create:0                      |     13.65ns |         |           |
  | [core_array.ml:Alloc] create:100                    |     99.83ns | 101.00w |           |
  | [core_array.ml:Alloc] create:255                    |    201.32ns | 256.00w |           |
  | [core_array.ml:Alloc] create:256                    |  1_432.43ns |         |   257.00w |
  | [core_array.ml:Alloc] create:1000                   |  5_605.58ns |         | 1_001.01w |
  | [core_array.ml:Blit.Poly] blit (tuple):10           |     87.10ns |         |           |
  | [core_array.ml:Blit.Poly] blito (tuple):10          |    112.14ns |   2.00w |           |
  | [core_array.ml:Blit.Poly] blit (int):10             |     85.25ns |         |           |
  | [core_array.ml:Blit.Poly] blito (int):10            |    107.23ns |   2.00w |           |
  | [core_array.ml:Blit.Poly] blit (float):10           |     84.71ns |         |           |
  | [core_array.ml:Blit.Poly] blito (float):10          |     86.71ns |   2.00w |           |
  | [core_array.ml:Blit.Int] blit:10                    |     19.77ns |         |           |
  | [core_array.ml:Blit.Int] blito:10                   |     23.54ns |   2.00w |           |
  | [core_array.ml:Blit.Float] blit:10                  |     19.87ns |         |           |
  | [core_array.ml:Blit.Float] blito:10                 |     24.12ns |   2.00w |           |
  | [core_array.ml:Is empty] Polymorphic '='            |     18.21ns |         |           |
  | [core_array.ml:Is empty] Array.equal                |      8.08ns |   6.00w |           |
  | [core_array.ml:Is empty] phys_equal                 |      2.98ns |         |           |
  | [core_array.ml:Is empty] Array.is_empty (empty)     |      2.98ns |         |           |
  | [core_array.ml:Is empty] Array.is_empty (non-empty) |      3.00ns |         |           |
- Moved `Thread_safe_queue` to core
- Generalized the type of `Exn.handle_uncaught_and_exit` to `(unit ->
  'a) -> 'a`.

  In the case where `handle_uncaught_and_exit` succeeds, it can return
  the value of the supplied function.

  It's type had been:

  ```ocaml
  val handle_uncaught_and_exit : (unit -> never_returns) -> never_returns
  ```
- Added `Int.round*` functions for rounding to a multiple of another
  int.

  ```ocaml
  val round : ?dir:[ `Zero | `Nearest | `Up | `Down ] -> t -> to_multiple_of:t -> t

  val round_towards_zero : t -> to_multiple_of:t -> t
  val round_down         : t -> to_multiple_of:t -> t
  val round_up           : t -> to_multiple_of:t -> t
  val round_nearest      : t -> to_multiple_of:t -> t
  ```

  These functions were added to `Int_intf.S`, implemented by `Int`,
  `Nativeint`, `Int32`, and `Int64`.

  Various int modules were also lightly refactored to make it easier
  in the future to implement common operators available for all
  modules implementing the int interface via a functor to share the
  code.
111.08.00

- Added `Hashtbl.for_all` and `for_alli`.
- Added `Float.to_padded_compact_string` for converting a floating point
  number to a lossy, compact, human-readable representation.

    E.g., `1_000_001.00` becomes `"1m "`.

- Tweaked the form of the definition of `Blang.Stable.V1`.

    Removed a `type t_` that is not necessary now that we can use `nonrec`
    without triggering spurious warnings.
111.11.00

- Added to `String` functions for substring search and replace, based
  on the KMP algorithm.

  Here are some benchmarks, comparing `Re2` for a fixed pattern,
  Mark's kmp from extended_string, and this implementation ("needle").

  The pattern is the usual `abacabadabacabae...`.  The text looks
  similar, with the pattern occurring at the very end.

  For =Re2= and =Needle= search benchmarks, the pattern is
  preprocessed in advance, outside of the benchmark.

  FWIW: I've also tried searches with pattern size = 32767, but =Re2=
  blows up, saying:

  ```
  re2/dfa.cc:447: DFA out of memory: prog size 32771 mem 2664898
  ```

  | Name                          |        Time/Run |       mWd/Run |    mjWd/Run | Prom/Run | Percentage |
  |-------------------------------|-----------------|---------------|-------------|----------|------------|
  | create_needle_15              |        102.56ns |        21.00w |             |          |            |
  | re2_compile_15                |      6_261.48ns |               |       3.00w |          |      0.01% |
  | create_needle_1023            |     13_870.48ns |         5.00w |   1_024.01w |          |      0.03% |
  | re2_compile_1023              |    107_533.32ns |               |       3.03w |          |      0.24% |
  | create_needle_8191            |     90_107.02ns |         5.00w |   8_192.01w |          |      0.20% |
  | re2_compile_8191              |  1_059_873.47ns |               |       3.28w |    0.28w |      2.37% |
  | create_needle_524287          |  6_430_623.96ns |         5.00w | 524_288.09w |          |     14.35% |
  | re2_compile_524287            | 44_799_605.83ns |               |       3.77w |    0.77w |    100.00% |
  | needle_search_15_95           |        349.65ns |         4.00w |             |          |            |
  | re2_search_15_95              |        483.11ns |               |             |          |            |
  | mshinwell_search_15_95        |      1_151.38ns |       781.01w |             |          |            |
  | needle_search_15_815          |      2_838.85ns |         4.00w |             |          |            |
  | re2_search_15_815             |      3_293.06ns |               |             |          |            |
  | mshinwell_search_15_815       |      8_360.57ns |     5_821.07w |       0.55w |    0.55w |      0.02% |
  | needle_search_15_2415         |      8_395.84ns |         4.00w |             |          |      0.02% |
  | re2_search_15_2415            |      9_594.14ns |               |             |          |      0.02% |
  | mshinwell_search_15_2415      |     24_602.09ns |    17_021.16w |       1.62w |    1.62w |      0.05% |
  | needle_search_1023_6143       |     14_825.50ns |         4.00w |             |          |      0.03% |
  | re2_search_1023_6143          |     40_926.59ns |               |             |          |      0.09% |
  | mshinwell_search_1023_6143    |     81_930.46ns |    49_149.66w |   1_025.65w |    1.65w |      0.18% |
  | needle_search_1023_52223      |    126_465.96ns |         4.00w |             |          |      0.28% |
  | re2_search_1023_52223         |    365_359.98ns |               |             |          |      0.82% |
  | mshinwell_search_1023_52223   |    527_323.73ns |   371_715.39w |   1_033.17w |    9.17w |      1.18% |
  | needle_search_1023_154623     |    377_539.53ns |         4.00w |             |          |      0.84% |
  | re2_search_1023_154623        |  1_001_251.93ns |               |             |          |      2.23% |
  | mshinwell_search_1023_154623  |  1_499_835.01ns | 1_088_518.15w |   1_033.19w |    9.19w |      3.35% |
  | needle_search_8191_49151      |    115_223.31ns |         4.00w |             |          |      0.26% |
  | re2_search_8191_49151         |    559_487.38ns |               |             |          |      1.25% |
  | mshinwell_search_8191_49151   |    653_981.19ns |   393_219.50w |   8_201.01w |    9.01w |      1.46% |
  | needle_search_8191_417791     |    976_725.24ns |         4.00w |             |          |      2.18% |
  | re2_search_8191_417791        |  4_713_965.69ns |               |             |          |     10.52% |
  | mshinwell_search_8191_417791  |  4_224_417.93ns | 2_973_709.32w |   8_202.37w |   10.37w |      9.43% |
  | needle_search_8191_1236991    |  2_912_863.78ns |         4.00w |             |          |      6.50% |
  | re2_search_8191_1236991       | 14_039_230.59ns |               |             |          |     31.34% |
  | mshinwell_search_8191_1236991 | 11_997_713.73ns | 8_708_130.87w |   8_202.47w |   10.47w |     26.78% |
- Added to `Set` functions for converting to and from a `Map.t`.

  ```ocaml
  val to_map : ('key, 'cmp) t -> f:('key -> 'data) -> ('key, 'data, 'cmp) Map.t
  val of_map_keys : ('key, _, 'cmp) Map.t -> ('key, 'cmp) t
  ```

  This required adding some additional type trickery to
  `Core_set_intf` to indicate that the comparator for a given module
  may or may not be fixed.
- Added an optional `iter` parameter to `Container.Make`.

  A direct implementation of `iter` is often more efficient than
  defining `iter` in terms of `fold`, and in these cases, the results
  of `Container.Make` that are defined in terms of `iter` will be more
  efficient also.
- Added `Int.pow` (and for other integer types), for bounds-checked
  integer exponentiation.
improved the format of CHANGES.md
111.13.00

- Added a `Sequence` module that implements polymorphic, on-demand
  sequences.

    Also implemented conversion to `Sequence.t` from various containers.

- Improved the explicitness and expressiveness of
  `Binary_searchable.binary_search`.

    `binary_search` now takes an additional (polymorphic variant)
    argument describing the relationship of the returned position to the
    element being searched for.

        val binary_search
          :  ?pos:int
          -> ?len:int
          -> t
          -> compare:(elt -> elt -> int)
          -> [ `Last_strictly_less_than         (** {v | < elt X |                       v} *)
             | `Last_less_than_or_equal_to      (** {v |      <= elt       X |           v} *)
             | `Last_equal_to                   (** {v           |   = elt X |           v} *)
             | `First_equal_to                  (** {v           | X = elt   |           v} *)
             | `First_greater_than_or_equal_to  (** {v           | X       >= elt      | v} *)
             | `First_strictly_greater_than     (** {v                       | X > elt | v} *)
             ]
          -> elt
          -> int option

- Added a new function, `Binary_searchable.binary_search_segmented`,
that can search an array consisting of two segments, rather than ordered
by `compare`.

        (** [binary_search_segmented ?pos ?len t ~segment_of which] takes an [segment_of]
            function that divides [t] into two (possibly empty) segments:

            {v
              | segment_of elt = `Left | segment_of elt = `Right |
            v}

            [binary_search_segmented] returns the index of the element on the boundary of the
            segments as specified by [which]: [`Last_on_left] yields the index of the last
            element of the left segment, while [`First_on_right] yields the index of the first
            element of the right segment.  It returns [None] if the segment is empty.

            By default, [binary_search] searches the entire [t].  One can supply [?pos] or
            [?len] to search a slice of [t].

            [binary_search_segmented] does not check that [segment_of] segments [t] as in the
            diagram, and behavior is unspecified if [segment_of] doesn't segment [t].  Behavior
            is also unspecified if [segment_of] mutates [t]. *)
        val binary_search_segmented
          :  ?pos:int
          -> ?len:int
          -> t
          -> segment_of:(elt -> [ `Left | `Right ])
          -> [ `Last_on_left | `First_on_right ]
          -> int option

- Made `Queue` match `Binary_searchable.S1`.
- Made `Gc.Stat` and `Gc.Control` match `Comparable`.
- Fixed some unit tests in `Type_immediacy` that were fragile due to GC.
update CHANGES.md
111.17.00

- In `Bigstring`, made many operations use compiler primitives new in
  OCaml 4.01.

  Exposed `Bigstring.get` and `set` as compiler primitives in the
  interface.

  Added `Bigstring.unsafe_get_int64_{le,be}_trunc`.
- Made `Error` round trip `exn`, i.e. `Error.to_exn (Error.of_exn exn)
  = exn`.
- Added to `failwiths` an optional `?here:Lexing.position` argument.
- Added `with typerep` to `Flags.S`.
- Optimized `List.dedup []` to return immediately.
- Added `data` argument to polymorphic type `Hashtbl_intf.Creators.create_options`.

  This allows implementations of `Hashtbl_intf.Creators` to have
  constructor arguments that depend on the type of both key and data
  values.  For example:

  ```ocaml
  module type Hashtbl_creators_with_typerep =
    Hashtbl_intf.Creators
    with type ('key, 'data, 'z) create_options
      =  typerep_of_key:'key Typerep.t
      -> typerep_of_data:'data Typerep.t
      -> 'z
  ```
- Improved the interface for getting `Monad.Make` to define `map` in
  terms of `bind`.

  Instead of passing a `map` function and requiring everyone who wants
  to define `map` using `bind` to call a special function, we use a
  variant type to allow the user to say what they want:

  ```ocaml
  val map : [ `Define_using_bind
            | `Custom of ('a t -> f:('a -> 'b) -> 'b t)
            ]
  ```
- Improved the performance of many `Dequeue` functions.

  Previously, many `Dequeue.dequeue`-type functions worked by raising
  and then catching an exception when the dequeue is empty.  This is
  much slower than just testing for emptiness, which is what the code
  now does.

  This improves the performance of `Async.Writer`, which uses
  `Dequeue.dequeue_front`.
Merge remote-tracking branch 'upstream/master'