Caml1999I0314(  ٠'Diffing$DefsL$leftT8@@@A@@@@@1utils/diffing.mli | ~ | @@@@@A@%rightU8@@@A@@@@@ @   @  @@@@AA@"eqV8@@@A@@@@@A  A  @@@@$BA@$diffW8@@@A@@@@@D  D  @@@@-CA@%stateX8@@@A@@@@@%G  &G  @@@@6DA@@@)~ e e*I & )@:E@+change_kindM8@@(Deletion@@8N  9N  @@IG)Insertion@@AO  BO  @@RH,Modification@@JP  KP  @@[I,Preservation@@SQ  TQ  @@dJ@@A@@@@@WM  @@A@gFA@&prefixN@&Stdlib&Format)formatter@@@@#intA@@@K@@@@@$unitF@@@@@@@@R  R  @@K@%styleO@@@@$listI$Misc%Color%style@@@@@@@@@S  S  F@@L@&changeP8$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@(classifyQ@Y@@@@@@@@@@@@@@ \   \ @@R@Ӡ&DefineR@!DS&&changeY8@@@A'$left@@@%right@@@ "eq@@@$diff@@@@@@@@@@?f  @f =@@@@PT@@%patchZ8@@@A1@@@@@@@@@@Rg>@Sg>X@@@@cUA@*Parameters[-update_result`8@@@A@@@@@bkck@@@@sVA@&weighta@ @@@@@@@@@tmum@@W@$testb@Y%state@@@@`$left@@@@g%right@@@0&resultq"eq@@@ؠw$diff@@@@@@@@@@@@@qGKqG@@X@&updatec@a@@@@%state@@@\@@@@@@@@ww.@@Y@@@j|@Z@!S\$diffd@%state@@@@%arrayH$left@@@@@@@%right@@@@@@@@@@@@@@@@.@@[@@@~@ \@Ӡ&Simple]@@e@@@@@@@@@@@@@f@@@@@@@@@@@@@@@ @@@@@@@@@@@@@'@@g@@@@@@@@!%state@@@@@@@@;@@@@NO@_^@@Ӡ-Left_variadic^@@h@@@@@@@@@@fg@@@i@I@@@@O@@@@U@@@]@@@b@@@@@@@@@@@@@'@@j@F@@@@r@@@y%state@@@̠$left@@@@@@@@@@@@@I@@@c@@`@@Ӡ.Right_variadic_@@Vk@u@@@U@@@@@@:@@T@Sl@R@@@@Q@@@@P@@@ON@@@M@@@@@@@@@@@@@'@I@Hm@@@@@G@@@%state@@@.%right@@@@@@@@@@@@@I@R@@@@@#b@@@@bBE@'c@@@Kᠠ'Diffing0cM5mCR-Stdlib__Uchar0 |K?bޣ ˠ.Stdlib__String0L%BWx:6+Stdlib__Set0PSVl8 ;+Stdlib__Seq0yt\eǟ&Q,}+Stdlib__Map0ҭfȨ؜ׇ0/Stdlib__Hashtbl0!z9ϸ@`VǠ.Stdlib__Format0=z+.m׸.Stdlib__Either0 }rCT0J){9).Stdlib__Digest0@~8x2.Stdlib__Buffer0'ON͋[h#ڗA&Stdlib0>,W:($Misc0KH(1Xk5o\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($diff DD  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%styleS  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@ @@.&Define1I5b6b@@Т!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г  @ @@' @@ @@@@@@K@@@J@@I@9@@@@@@H@@@@G@@@@F7@@@D@@@E@@@C@@B@@A@@@@%@|@x@@@?@+l@@@>/R@@@=@@<@@;@8QD@@m8@Р.!S@w@@@Rz@@@ @~ @-Left_variadic(R@@Т@@УР*Parameters@0@@@xw@ml@KJ@@9@,^@A@@-update_result@(@8@@@A%state@@@L$left@@@M@@@O@@P@@@@@@@@_@@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_variadic0T@@Т@@УР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%@!/@@@@@@@@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  */home/barsac/ci/builds/workspace/bootstrap - @0y{Ph7_xmL0        @ @@5Build_path_prefix_map0 5 ttY8CamlinternalFormatBasics0cEXy,W:(.Stdlib__Buffer0'ON͋[h#ڗA.Stdlib__Digest0@~8x2.Stdlib__Either0 }rCT0J){9).Stdlib__Format0=z+.m׸/Stdlib__Hashtbl0!z9ϸ@`VǠ+Stdlib__Map0ҭfȨ؜ׇ0+Stdlib__Seq0yt\eǟ&Q,}+Stdlib__Set0PSVl8 ;.Stdlib__String0L%BWx:6-Stdlib__Uchar0 |K?bޣ @0cM5mCRAX@Ui @-YN^@@ڰ P _@~@ʰ  @Uİ@@@ 8 G w @pQP@    @  @@@ @@P@