Caml1999I0314(  ٠'Diffing$DefsM$leftU8@@@A@@@@@1utils/diffing.mli | ~ | @@@@@A@%rightV8@@@A@@@@@ @   @  @@@@AA@"eqW8@@@A@@@@@A  A  @@@@$BA@$diffX8@@@A@@@@@D  D  @@@@-CA@%stateY8@@@A@@@@@%G  &G  @@@@6DA@@@)~ e e*I & )@:E@+change_kindN8@@(Deletion@@8N  9N  @@IG)Insertion@@AO  BO  @@RH,Modification@@JP  KP  @@[I,Preservation@@SQ  TQ  @@dJ@@A@@@@@WM  @@A@gFA@&prefixO@&Stdlib&Format)formatter@@@@#intA@@@K@@@@@$unitF@@@@@@@@R  R  @@K@%styleP@@@@$listI$Misc%Color%style@@@@@@@@@S  S  F@@L@&changeQ8$left@%right@"eq@$diff@@D&Delete @@W p rW p @@N&Insert @@X  X  @@O$Keep .*&@@Y  Y  @@P&Change:6-@@Z  Z  @@Q@@A@YYYY@@@@@@@@V I I @@@@MA@(classifyR@Y@@@@@@@@@@@@@@ \   \ @@R@Ӡ&DefineS@!DT&&changeZ8@@@A'$left@@@%right@@@ "eq@@@$diff@@@@@@@@@@?f  @f =@@@@PT@@%patch[8@@@A1@@@@@@@@@@Rg>@Sg>X@@@@cUA@*Parameters\-update_resulta8@@@A@@@@@bkck@@@@sVA@&weightb@ @@@@@@@@@tmum@@W@$testc@Y%state@@@@`$left@@@@g%right@@@0&resultq"eq@@@ؠw$diff@@@@@@@@@@@@@qGKqG@@X@&updated@a@@@@%state@@@\@@@@@@@@ww.@@Y@@@j|@Z@!S]$diffe@%state@@@@%arrayH$left@@@@@@@%right@@@@@@@@@@@@@@@@.@@[@@@~@ \@Ӡ&Simple^@@f@@@@@@@@@@@@@g@@@@@@@@@@@@@@@ @@@@@@@@@@@@@'@@h@@@@@@@@!%state@@@@@@@@;@@@@NO@_^@@Ӡ-Left_variadic_@@i@@@@@@@@@@fg@@@j@I@@@@O@@@@U@@@]@@@b@@@@@@@@@@@@@'@@k@F@@@@r@@@y%state@@@̠$left@@@@@@@@@@@@@I@@@c@@`@@Ӡ.Right_variadic`@@Vl@u@@@U@@@@@@:@@T@Sm@R@@@@Q@@@@P@@@ON@@@M@@@@@@@@@@@@@'@I@Hn@@@@@G@@@%state@@@.%right@@@@@@@@@@@@@I@R@@@@@#b@@@@bBE@'c@@@Kᠠ'Diffing0n$2d:ī6 -Stdlib__Uchar0*Ujmyc6]]W.Stdlib__String0I3UK# +Stdlib__Set0.z9FX+Stdlib__Seq05"g1<)b+Stdlib__Map0kZ,ҷ'V/Stdlib__Hashtbl04$*uկdD.Stdlib__Format0{hXsHW#ȼ.Stdlib__Either0&]XF.Stdlib__Digest0aI]2t*x4%".Stdlib__Buffer0K ɦb+Z8)#KH"&Stdlib0yӶ~*$Misc0,Z3XI`3y/8CamlinternalFormatBasics0cEXy). We provide the following guarantee: Given two lists [l] and [r], if different patches result in different states, we say that the state diverges. - We always return the optimal patch on prefixes of [l] and [r] on which state does not diverge. - Otherwise, we return a correct but non-optimal patch where subpatches with no divergent states are optimal for the given initial state. More precisely, the optimality of Wagner-Fischer depends on the property that the edit-distance between a k-prefix of the left input and a l-prefix of the right input d(k,l) satisfies d(k,l) = min ( del_cost + d(k-1,l), insert_cost + d(k,l-1), change_cost + d(k-1,l-1) ) Under this hypothesis, it is optimal to choose greedily the state of the minimal patch transforming the left k-prefix into the right l-prefix as a representative of the states of all possible patches transforming the left k-prefix into the right l-prefix. If this property is not satisfied, we can still choose greedily a representative state. However, the computed patch is no more guaranteed to be globally optimal. Nevertheless, it is still a correct patch, which is even optimal among all explored patches. 1utils/diffing.mliP77{ / 1@@@@@@0@@@@@@%arrayH8@@M@A@A@@@@@@8@@@$boolE8@@%false^@@B@$true_@@H@@@A@@@@@I@A@$charB8@@@A@@@@@M@A@#exnG8@@AA@@@@@Q@@@5extension_constructorP8@@@A@@@@@U@@@%floatD8@@@A@@@@@Y@@@*floatarrayQ8@@@A@@@@@]@@@#intA8@@@A@@@@@a@A@%int32L8@@@A@@@@@e@@@%int64M8@@@A@@@@@i@@@&lazy_tN8@@O@A@A@Y@@@@@r@@@$listI8@@P@A"[]a@@@"::b@@@Q@@@ @@A@Y@@@@@@@@)nativeintK8@@@A@@@@@@@@&optionJ8@@S@A$Nonec@@@$Somed@@@@@A@Y@@@@@@@@&stringO8@@@A@@@@@@@@$unitF8@@"()`@@@@@A@@@@@@A@ .Assert_failure\ p@@@@Jm@@@@@@V@@A͠=ocaml.warn_on_literal_patternѐ@@0Division_by_zeroY @@@Aנ  @+End_of_fileX !@@@Aߠ@'FailureU )@%@@A蠰@0Invalid_argumentT 2@.@@A񠰠$#@-Match_failureR ;@:67@@\@@A21@ )Not_foundV I@@@A: 9 @-Out_of_memoryS Q@@@ABA@.Stack_overflowZ Y@@@AJI@.Sys_blocked_io[ a@@@AR"Q"@)Sys_errorW i@e@@A([+Z+@:Undefined_recursive_module] r@qmn@@c@@A6i9h9@ %bytesC8@@@A@@@@@=@@@&Stdlib@A6б$DefsF=~ e q>~ e u@БA($left AL | M | @@8@@@A@@@@@P | ~@@@@g@@@A@@@0ONNOOOOO@M@A@A(%right B]@  ^@  @@8@@@A@@@@@a@  @@@@xA@@A@@@0`__`````@_@A@A("eq CoA  pA  @@8@@@A@@@@@sA  @)ocaml.doc9 Detailed equality trace B  B  @@@@@@@@@B@@A@@0@"-'@A@A($diffDD  D  @@8@@@A@@@@@D  @!; Detailed difference trace E  E  @@@@@@@@@C@@A@@0@ :4@A@A(%stateEG  G  @@8@@@A@@@@@G  @@ environment of a partial patch H  H  %@@@@@@@@@D@@A@@0@ 82@A@@yA@pjA@`ZA@A;A@$A@@0@& @A 0@@A~ e xI & )@@b , The core types of a diffing implementation } 3 3} 3 d@@@@@@@~ e e@@A(+change_kindGM  M  @@8@@(Deletion@@N  N  @@G)Insertion@@O  O  @@H,Modification@@ P   P  @@#I,Preservation@@Q  Q  @@,J@@A@@@@@M  @ Z The kind of changes which is used to share printing and styling across implementation$K + +%L o @@@@@@@A@Q  *@@@@-@@A@)'@0=<<=====@< A@A@A@A@A@@yleE@A9<@&prefixYR  ZR  @б@г/&Format)formattergR  hR  @@ @@@ 0ihhiiiii@-}@A@@б@Вг%#int{R  |R  @@ @@@ @@г+change_kindR  R  @@ @@@ "@@@@@ ' @@г$unitR  R  @@ @@@ 4@@@@@ 7R   @@@>@@ ;A @@@R  @@K@@@A%style S  S  @б@гѠ+change_kindS  "S  -@@ @@@ 0@Zr@A@@гd$listS  BS  F@г$Misc%Color%style$MiscS  1S  A@@@@@!@@@@@@& @@@,@@)/@@@S  "@@L@$@@/A(&change HV I gV I m@А$left@0@DY8@@@@@@@@@D@A@GGGG@BBBB@@@ V I I!Z  @@@@8M@A$V I O%V I T@@BAА%right@(0V I U1V I [@@ А"eq@3;V I \<V I _@@А$diff@>FV I `GV I e@@"@8F @D&Delete RJ@@@WW p rXW p @@oN&Insert 6J@@@cX  dX  @@{O$Keep jJ@EJ@=J@@@uY  vY  @@P&Change|J@WJ@DJ@@@Z  g@@Q@@A@YYYY@@@@@@@@r@@@o@DDW p tW p z@@А$leftIW p ~G@@@@I@EEX  X  @@А%rightJX  H@@@@J@FFY  Y  @@А$leftKY  Y  @@А%rightOY  Y  @@А"eqSY  Q@@@@S@OOZ  Z  @@А$leftT˰Z  Z  @@А%rightXҰZ  Z  @@А$diff\ٰZ  @@@@\@@A@@@0@@A@(classify\  \  @б@г&change\  \  @@@@0@@A\  \  @@@@@ @@@@  @@@@@@ @@@@@г.+change_kind\  \ @@ @@@%@@@@@(&@@@(\   @@?R@ @@.&Define2I5b6b@@Т!DJ@bAb@Р $DefsIbJb@0IHHIIIII@Pf(@A@@Бࠐ!D\c]c@@A0[ZZ[[[[[@'@ @%zS*@Afc @@0dccddddd@@A @@(&changeKrf sf @@8@@@A&$left@@@Р,%right@@@Ѡ2"eq@@@Ҡ8$diff@@@@@@@@@@f  f =@! * The type of potential changes on a list. ee @@@@@@@@@T@@Aг.&changef 7@г23f #f '@@9U@@г56f (f -@@<^@@г89f .f 0@@?g@@г;<f 1f 5@@Bp@@@Yqf "=@@?<@s?>@A(%patchLg>Eg>J@@8@@@A{x@@@@@@@@@@g>@g>X@w ( A patch is an ordered list of changes. hY[hY@@@@@@@@@U@@Aг$listg>T@г&changeg>M g>S@@'0@68@@@A=@@M@M@@@@@-*@@@A @@@7 -@@/,@0@ @A0/@б*ParametersN!j"j@БA(-update_resultM0k1k@@8@@@A@@@@@4k@@@@KV@@A@@@032233333@,a[@A@&weightAmBm@б@гڠ&changeLmMm@@ @@@0NMMNNNNN@'!@A@@г#int[m\m@@ @@@@@@@@@@@fm @󐠠 ] [weight ch] returns the weight of the change [ch]. Used to find the smallest patch. rnsoE@@@@@@@W@@%$test~qGOqGS@б@г.%stateqGUqGZ@@ @@@0@>S,@A@@б@г?$leftqG^qGb@@ @@@@@б@гN%rightqGfqGk@@ @@@ @@г&resultqGzqG@гe"eqqGpqGr@@ @@@7@@гs$diffqGtqGx@@ @@@E@@@%@@@KqGo$@@@2 @@ O5'@@@D@@ RG*@@@X@@ U[-@@@qGK0@s r [test st xl xr] tests if the elements [xl] and [xr] are co mpatible ([Ok]) or not ([Error]). ru@@@@@@@ X@?@h&updateww @б@г&change w w@@ @@@ 0        @,@A@@б@г%stateww@@ @@@ @@г-update_result'w!(w.@@ @@@@@@@@!@@@'@@$* @@@5w@ [update ch st] returns the new state after applying a change. The [update_result] type also contains expansions in the variadic case. Ax/3B{@@@@@@@YY@@7@A@ @g@S@@0JIIJJJJJ@@U@A 0MLLMMMMM@@ARjS|@@@Uj@0SRRSSSSS@ @A@б!SO`~a~@Б$diffno@б@г%stateyz@@ @@@0{zz{{{{{@IcYSA@J#@@X@@@7Z@A@@б@гn%array@гE$left @@ @@@'@@@@@@, @@б@г%array %@гc%right@@ @@@E@@@@@@J @@г%patch).@@ @@@W@@@@@Z@@@5@@]< @@@c@@`f@@@@n o [diff state l r] computes the optimal patch between [l] and [r], using the initial state [state]. /3@@@@@@@[@ @s@@@0@v@A0@x@A~@@@~@0@~@A@&Simple!P @@Т@@УР*Parameters@0@B@@@'7\@A  @@-update_result*+@(@8@@@A%state@@@@@@@78@@@@O]@@Aг  @ @@' @@ @@@@@@Q@@@P@@O@9@@@@@@N@@@@M@@@@L7@@@J@@@K@@@I@@H@@G@@F@%@| @x@@@E@+l@@@D/R@@@C@@B@@A@8QD@@m8@Р.!S@w@@@Rz@@@ @~ @-Left_variadic)R@@Т@@УР*Parameters@0@@@xw@ml@KJ@@9@,^@A@@-update_result@(@8@@@A%state@@@R$left@@@S@@@U@@V@@@@@@@@_@@AВг@@?@@г%array@г @@&P@@@+Q @@@5R!@@#@@&@@@@@@@@@@d/@@'@@@@@@@@@@@@}w@@@n@@@@@@@@@@@@@%SF@B(@>@@@@2@@@w@@@vu@@@@@@@@@@@@@D#@@D@Р!S`a@@@@^g@@ {1 Variadic diffing} Variadic diffing allows to expand the lists being diffed during diffing. in one specific direction. st@@@@@@@v@°@.Right_variadic1T@@Т@@УРp*Parameters @0@@@@@dc@@F9,`@A@@z-update_result#@(@8@@@A`%state@@@j%right@@@@@@@@@@@@:@@@@a@@AВг',@@?@@г%array5@г /4@@&P@@@+Q @@@5R!@@#@@.@@@@@@@@@@d/@@}/@y@@@@n@@@@e@@@\V@@@ԠM@@@@@@@@@@@@@%2%@!0@@@@@@@@w@@@ˠvu@@@@@@@@@@@@@D@@D@Рߠ!S ?? @@@@@@^ F@@@ H @ @@@@wqA@3@@a@\5@U@@@@@@@@@ ub@@@0 ] \ \ ] ] ] ] ]@@@~}@sr@QP@@3@&@A$0 k j j k k k k k@@A pb qBE@@:)0 q p p q q q q q@(@A@@@ [Define(Defs)] creates the diffing types from the types defined in [Defs] and the functors that need to be instantatied with the diffing algorithm parameters  ^ a@@@@@@@ b@@@O;@A@9@@JA@n@f@%! c@@@0        @Mj@cZ3-@@A@~xA@oH@4@}@@@\%@VM@@@@@@zy@on@ML@@;@.@@(@@@@@@vi\0@@V@@@@@@@@@@h[G@A@ H************************************************************************ A@@ A@L@ H  BMM BM@ H OCaml  C C@ H  D D3@ H Gabriel Radanne, projet Cambium, Inria Paris  E44 E4@ H  F F@ H Copyright 2020 Institut National de Recherche en Informatique et  G G@ H en Automatique.  H Hg@ H  Ihh Ih@ H All rights reserved. This file is distributed under the terms of  J J@ H the GNU Lesser General Public License version 2.1, with the  K KN@ H special exception on linking described in the file LICENSE.  $LOO %LO@ H  *M +M@ H************************************************************************ 0N 1N5@ * Parametric diffing This module implements diffing over lists of arbitrary content. It is parameterized by - The content of the two lists - The equality witness when an element is kept - The diffing witness when an element is changed Diffing is extended to maintain state depending on the computed changes while walking through the two lists. The underlying algorithm is a modified Wagner-Fischer algorithm (see ). We provide the following guarantee: Given two lists [l] and [r], if different patches result in different states, we say that the state diverges. - We always return the optimal patch on prefixes of [l] and [r] on which state does not diverge. - Otherwise, we return a correct but non-optimal patch where subpatches with no divergent states are optimal for the given initial state. More precisely, the optimality of Wagner-Fischer depends on the property that the edit-distance between a k-prefix of the left input and a l-prefix of the right input d(k,l) satisfies d(k,l) = min ( del_cost + d(k-1,l), insert_cost + d(k,l-1), change_cost + d(k-1,l-1) ) Under this hypothesis, it is optimal to choose greedily the state of the minimal patch transforming the left k-prefix into the right l-prefix as a representative of the states of all possible patches transforming the left k-prefix into the right l-prefix. If this property is not satisfied, we can still choose greedily a representative state. However, the computed patch is no more guaranteed to be globally optimal. Nevertheless, it is still a correct patch, which is even optimal among all explored patches.  6 -* The core types of a diffing implementation X:* Detailed equality trace <* Detailed difference trace  !* environment of a partial patch  [* The kind of changes which is used to share printing and styling across implementation! * [Define(Defs)] creates the diffing types from the types defined in [Defs] and the functors that need to be instantatied with the diffing algorithm parameters Ǡ +* The type of potential changes on a list.  )* A patch is an ordered list of changes. X ^* [weight ch] returns the weight of the change [ch]. Used to find the smallest patch. ߠ s* [test st xl xr] tests if the elements [xl] and [xr] are co mpatible ([Ok]) or not ([Error]). b * [update ch st] returns the new state after applying a change. The [update_result] type also contains expansions in the variadic case.  p* [diff state l r] computes the optimal patch between [l] and [r], using the initial state [state]. m * {1 Variadic diffing} Variadic diffing allows to expand the lists being diffed during diffing. in one specific direction. @-./boot/ocamlc"-g)-nostdlib"-I$boot*-use-prims2runtime/primitives0-strict-sequence*-principal(-absname"-w>+a-4-9-40-41-42-44-45-48-66-70+-warn-error"+a*-bin-annot,-safe-string/-strict-formats"-I%utils"-I'parsing"-I&typing"-I(bytecomp"-I,file_formats"-I&lambda"-I*middle_end"-I2middle_end/closure"-I2middle_end/flambda"-I=middle_end/flambda/base_types"-I'asmcomp"-I&driver"-I(toplevel"-c  3/home/barsac/ci/builds/workspace/step-by-step-build - @0y{Ph7_xmL0        @ @@5Build_path_prefix_map0xөvĠ8CamlinternalFormatBasics0cEXy