From a0ed5fd377daf5754697636504de8e180abf9ec0 Mon Sep 17 00:00:00 2001 From: Eduardo Julian Date: Wed, 6 Apr 2022 16:07:22 -0400 Subject: More efficient binary parsing. --- stdlib/project.lux | 2 +- stdlib/source/documentation/lux/data/binary.lux | 6 +- .../library/lux/control/concurrency/thread.lux | 2 +- .../source/library/lux/control/parser/binary.lux | 71 +++++++++++++++------- stdlib/source/library/lux/data/binary.lux | 2 +- stdlib/source/library/lux/data/format/tar.lux | 10 +-- .../language/lux/phase/extension/analysis/ruby.lux | 40 +++++++----- stdlib/source/program/aedifex/hash.lux | 14 ++--- stdlib/source/test/lux/data/binary.lux | 12 ++-- stdlib/source/test/lux/target/ruby.lux | 4 +- 10 files changed, 99 insertions(+), 64 deletions(-) (limited to 'stdlib') diff --git a/stdlib/project.lux b/stdlib/project.lux index 248a90a18..6de4fa930 100644 --- a/stdlib/project.lux +++ b/stdlib/project.lux @@ -75,7 +75,7 @@ ] "ruby" - ["lux" ["com.github.luxlang" "lux-ruby" "0.6.6-SNAPSHOT" "jar"] + ["lux" ["com.github.luxlang" "lux-ruby" "0.7.0-SNAPSHOT" "jar"] ... The OS command to use when running Ruby tests. The default is described below. ... "ruby" ["ruby"] ] diff --git a/stdlib/source/documentation/lux/data/binary.lux b/stdlib/source/documentation/lux/data/binary.lux index abfdc044d..ecf9bba44 100644 --- a/stdlib/source/documentation/lux/data/binary.lux +++ b/stdlib/source/documentation/lux/data/binary.lux @@ -17,9 +17,9 @@ "A fresh/empty binary BLOB of the specified size." [(empty size)]) -(documentation: /.aggregate +(documentation: /.mix "" - [(aggregate f init binary)]) + [(mix f init binary)]) (documentation: /.bits_8 "Read 1 byte (8 bits) at the given index." @@ -71,7 +71,7 @@ "" [..Binary ..empty - ..aggregate + ..mix ..bits_8 ..bits_16 ..bits_32 diff --git a/stdlib/source/library/lux/control/concurrency/thread.lux b/stdlib/source/library/lux/control/concurrency/thread.lux index f8d92bc77..619b9733d 100644 --- a/stdlib/source/library/lux/control/concurrency/thread.lux +++ b/stdlib/source/library/lux/control/concurrency/thread.lux @@ -170,7 +170,7 @@ (if started? (in []) (do ! - [_ (atom.has! true ..started?)] + [_ (atom.write! true ..started?)] (loop (again [_ []]) (do ! [threads (atom.read! ..runner)] diff --git a/stdlib/source/library/lux/control/parser/binary.lux b/stdlib/source/library/lux/control/parser/binary.lux index a1c565360..1e360a194 100644 --- a/stdlib/source/library/lux/control/parser/binary.lux +++ b/stdlib/source/library/lux/control/parser/binary.lux @@ -1,6 +1,7 @@ (.using [library [lux {"-" and or nat int rev list type symbol} + [ffi {"+"}] [type {"+" sharing}] [abstract [hash {"+" Hash}] @@ -9,7 +10,8 @@ ["[0]" try {"+" Try}] ["[0]" exception {"+" exception:}]] [data - ["/" binary {"+" Binary}] + ["/" binary "_" + ["[1]" \\unsafe {"+" Binary}]] [text ["%" format {"+" format}] [encoding @@ -17,7 +19,9 @@ [collection ["[0]" list] ["[0]" sequence {"+" Sequence}] - ["[0]" set {"+" Set}]]] + ["[0]" set {"+" Set}] + [array + [\\unsafe {"+"}]]]] [macro ["^" pattern] ["[0]" template]] @@ -39,22 +43,31 @@ "Binary length" (%.nat binary_length) "Bytes read" (%.nat bytes_read))) +(template [ ] + [(template: ( ) + [( )])] + + [n#= "lux i64 ="] + [n#+ "lux i64 +"] + [n#- "lux i64 -"] + ) + (def: .public (result parser input) (All (_ a) (-> (Parser a) Binary (Try a))) (case (parser [0 input]) - {try.#Failure msg} - {try.#Failure msg} - {try.#Success [[end _] output]} (let [length (/.size input)] - (if (n.= end length) + (if (n#= end length) {try.#Success output} - (exception.except ..binary_was_not_fully_read [length end]))))) + (exception.except ..binary_was_not_fully_read [length end]))) + + failure + (as_expected failure))) (def: .public end? (Parser Bit) (function (_ (^.let input [offset data])) - {try.#Success [input (n.= offset (/.size data))]})) + {try.#Success [input (n#= offset (/.size data))]})) (def: .public offset (Parser Offset) @@ -64,7 +77,7 @@ (def: .public remaining (Parser Nat) (function (_ (^.let input [offset data])) - {try.#Success [input (n.- offset (/.size data))]})) + {try.#Success [input (n#- offset (/.size data))]})) (type: .public Size Nat) @@ -74,16 +87,24 @@ (def: .public size_32 Size (n.* 2 size_16)) (def: .public size_64 Size (n.* 2 size_32)) +(exception: .public (range_out_of_bounds [length Nat + start Nat + end Nat]) + (exception.report + "Length" (%.nat length) + "Range start" (%.nat start) + "Range end" (%.nat end))) + (template [ ] [(def: .public (Parser I64) - (function (_ [offset binary]) - (case ( offset binary) - {try.#Success data} - {try.#Success [(n.+ offset) binary] data} - - {try.#Failure error} - {try.#Failure error})))] + (function (_ [start binary]) + (let [end (n#+ start)] + (if (n.< end (/.size binary)) + (exception.except ..range_out_of_bounds [(/.size binary) start end]) + (|> ( start binary) + [[end binary]] + {try.#Success})))))] [bits_8 ..size_8 /.bits_8] [bits_16 ..size_16 /.bits_16] @@ -153,12 +174,16 @@ (def: .public (segment size) (-> Nat (Parser Binary)) - (function (_ [offset binary]) - (case size - 0 {try.#Success [[offset binary] (/.empty 0)]} - _ (|> binary - (/.slice offset size) - (# try.monad each (|>> [[(n.+ size offset) binary]])))))) + (case size + 0 (//#in (/.empty 0)) + _ (function (_ [start binary]) + (let [end (n#+ size start)] + (if (n.< end (/.size binary)) + (exception.except ..range_out_of_bounds [(/.size binary) start end]) + (|> binary + (/.slice start size) + [[end binary]] + {try.#Success})))))) (template [ ] [(`` (def: .public @@ -232,7 +257,7 @@ [raw (..list value) .let [output (set.of_list hash raw)] _ (//.assertion (exception.error ..set_elements_are_not_unique []) - (n.= (list.size raw) + (n#= (list.size raw) (set.size output)))] (in output))) diff --git a/stdlib/source/library/lux/data/binary.lux b/stdlib/source/library/lux/data/binary.lux index 6615131c5..6ccbb0442 100644 --- a/stdlib/source/library/lux/data/binary.lux +++ b/stdlib/source/library/lux/data/binary.lux @@ -31,7 +31,7 @@ (-> Nat Binary) (|>> /.empty)) -(def: .public (aggregate $ init it) +(def: .public (mix $ init it) (All (_ a) (-> (-> I64 a a) a Binary a)) (let [size (/.size it)] (loop (again [index 0 diff --git a/stdlib/source/library/lux/data/format/tar.lux b/stdlib/source/library/lux/data/format/tar.lux index afea5a3dd..4fb3522a6 100644 --- a/stdlib/source/library/lux/data/format/tar.lux +++ b/stdlib/source/library/lux/data/format/tar.lux @@ -172,7 +172,7 @@ (def: checksum (-> Binary Nat) - (binary.aggregate n.+ 0)) + (binary.mix n.+ 0)) (def: checksum_checksum (|> ..dummy_checksum @@ -217,10 +217,10 @@ (def: ascii? (-> Text Bit) (|>> (# utf8.codec encoded) - (binary.aggregate (function (_ char verdict) - (.and verdict - (n.<= ..last_ascii char))) - true))) + (binary.mix (function (_ char verdict) + (.and verdict + (n.<= ..last_ascii char))) + true))) (exception: .public (not_ascii [text Text]) (exception.report diff --git a/stdlib/source/library/lux/tool/compiler/language/lux/phase/extension/analysis/ruby.lux b/stdlib/source/library/lux/tool/compiler/language/lux/phase/extension/analysis/ruby.lux index 32c57de4e..ab9ed4837 100644 --- a/stdlib/source/library/lux/tool/compiler/language/lux/phase/extension/analysis/ruby.lux +++ b/stdlib/source/library/lux/tool/compiler/language/lux/phase/extension/analysis/ruby.lux @@ -9,7 +9,7 @@ ["<[0]>" code {"+" Parser}]]] [data [collection - ["[0]" array {"+" Array}] + ["[0]" array] ["[0]" dictionary] ["[0]" list]]] ["[0]" type @@ -32,11 +32,13 @@ [.any (function (_ extension phase archive lengthC) (<| analysis/type.with_var - (function (_ [@var :var:])) + (function (_ [@read :read:])) + analysis/type.with_var + (function (_ [@write :write:])) (do phase.monad [lengthA (<| (analysis/type.expecting Nat) (phase archive lengthC)) - _ (analysis/type.inference (type (Array :var:)))] + _ (analysis/type.inference (type (array.Array' :read: :write:)))] (in {analysis.#Extension extension (list lengthA)}))))])) (def: array::length @@ -45,9 +47,11 @@ [.any (function (_ extension phase archive arrayC) (<| analysis/type.with_var - (function (_ [@var :var:])) + (function (_ [@read :read:])) + analysis/type.with_var + (function (_ [@write :write:])) (do phase.monad - [arrayA (<| (analysis/type.expecting (type (Array :var:))) + [arrayA (<| (analysis/type.expecting (type (array.Array' :read: :write:))) (phase archive arrayC)) _ (analysis/type.inference Nat)] (in {analysis.#Extension extension (list arrayA)}))))])) @@ -58,13 +62,15 @@ [(<>.and .any .any) (function (_ extension phase archive [indexC arrayC]) (<| analysis/type.with_var - (function (_ [@var :var:])) + (function (_ [@read :read:])) + analysis/type.with_var + (function (_ [@write :write:])) (do phase.monad [indexA (<| (analysis/type.expecting Nat) (phase archive indexC)) - arrayA (<| (analysis/type.expecting (type (Array :var:))) + arrayA (<| (analysis/type.expecting (type (array.Array' :read: :write:))) (phase archive arrayC)) - _ (analysis/type.inference :var:)] + _ (analysis/type.inference :read:)] (in {analysis.#Extension extension (list indexA arrayA)}))))])) (def: array::write @@ -73,15 +79,17 @@ [($_ <>.and .any .any .any) (function (_ extension phase archive [indexC valueC arrayC]) (<| analysis/type.with_var - (function (_ [@var :var:])) + (function (_ [@read :read:])) + analysis/type.with_var + (function (_ [@write :write:])) (do phase.monad [indexA (<| (analysis/type.expecting Nat) (phase archive indexC)) - valueA (<| (analysis/type.expecting :var:) + valueA (<| (analysis/type.expecting :write:) (phase archive valueC)) - arrayA (<| (analysis/type.expecting (type (Array :var:))) + arrayA (<| (analysis/type.expecting (type (array.Array' :read: :write:))) (phase archive arrayC)) - _ (analysis/type.inference (type (Array :var:)))] + _ (analysis/type.inference (type (array.Array' :read: :write:)))] (in {analysis.#Extension extension (list indexA valueA arrayA)}))))])) (def: array::delete @@ -90,13 +98,15 @@ [($_ <>.and .any .any) (function (_ extension phase archive [indexC arrayC]) (<| analysis/type.with_var - (function (_ [@var :var:])) + (function (_ [@read :read:])) + analysis/type.with_var + (function (_ [@write :write:])) (do phase.monad [indexA (<| (analysis/type.expecting Nat) (phase archive indexC)) - arrayA (<| (analysis/type.expecting (type (Array :var:))) + arrayA (<| (analysis/type.expecting (type (array.Array' :read: :write:))) (phase archive arrayC)) - _ (analysis/type.inference (type (Array :var:)))] + _ (analysis/type.inference (type (array.Array' :read: :write:)))] (in {analysis.#Extension extension (list indexA arrayA)}))))])) (def: bundle::array diff --git a/stdlib/source/program/aedifex/hash.lux b/stdlib/source/program/aedifex/hash.lux index 1455fd65f..6b3f973ce 100644 --- a/stdlib/source/program/aedifex/hash.lux +++ b/stdlib/source/program/aedifex/hash.lux @@ -57,13 +57,13 @@ (def: encoded (Format Binary) - (binary.aggregate (function (_ byte representation) - (let [hex (# n.hex encoded byte) - hex (case (text.size hex) - 1 (format "0" hex) - _ hex)] - (format representation hex))) - "")) + (binary.mix (function (_ byte representation) + (let [hex (# n.hex encoded byte) + hex (case (text.size hex) + 1 (format "0" hex) + _ hex)] + (format representation hex))) + "")) (template [ ] [(def: diff --git a/stdlib/source/test/lux/data/binary.lux b/stdlib/source/test/lux/data/binary.lux index 656dbf9bf..badf40980 100644 --- a/stdlib/source/test/lux/data/binary.lux +++ b/stdlib/source/test/lux/data/binary.lux @@ -75,9 +75,9 @@ (def: as_list (-> /.Binary (List Nat)) - (/.aggregate (function (_ head tail) - {.#Item head tail}) - (list))) + (/.mix (function (_ head tail) + {.#Item head tail}) + (list))) (def: test|unsafe Test @@ -160,9 +160,9 @@ ($equivalence.spec /.equivalence (..random size))) (_.for [/.monoid] ($monoid.spec /.equivalence /.monoid (..random size))) - (_.cover [/.aggregate] + (_.cover [/.mix] (n.= (# list.mix mix n.+ 0 (..as_list sample)) - (/.aggregate n.+ 0 sample))) + (/.mix n.+ 0 sample))) (_.cover [/.empty] (# /.equivalence = @@ -212,7 +212,7 @@ {.#Item head tail} (n.= (list.mix n.+ 0 tail) - (/.aggregate n.+ 0 (/.after 1 sample)))))) + (/.mix n.+ 0 (/.after 1 sample)))))) (_.cover [/.copy!] (and (case (/.copy! size 0 sample 0 (/.empty size)) {try.#Success output} diff --git a/stdlib/source/test/lux/target/ruby.lux b/stdlib/source/test/lux/target/ruby.lux index 968d3c7bd..22dee2512 100644 --- a/stdlib/source/test/lux/target/ruby.lux +++ b/stdlib/source/test/lux/target/ruby.lux @@ -20,7 +20,7 @@ [collection ["[0]" list ("[1]#[0]" functor)] ["[0]" set]]] - ["[0]" math + [math ["[0]" random {"+" Random} ("[1]#[0]" monad)] [number {"+" hex} ["n" nat] @@ -122,7 +122,7 @@ [/.* f.* |>] [/./ f./ |>] [/.% f.mod |>] - [/.pow math.pow f.abs] + [/.pow f.pow f.abs] )) (~~ (template [ ] [(_.cover [] -- cgit v1.2.3