Repository: tweag/nickel (rust)

Issue:
Cloning and droping of Labels take a schoking amount of time
**Describe the bug**
Sorting a list currently takes an insane amount of time with Nickel. After generating flamegraphs, we can notice that a big amount of time is spend on cloning and dropping `Label`s, and especially their field `type`.
![fg-label](https://user-images.githubusercontent.com/4235083/152346530-7467926b-6acc-4c51-bcb2-b56fa6bd2192.png)
(complete flamegraph linked in the `Files` section)

**To Reproduce**
In the linked PR (soon to be open), I added a new stupid benchmark sorting a list of 100 elements.
Running it with `cargo bench sort -- --profile-time=120`, we obtain a flamegraph similar to the one linked below.

**Expected behavior**
Better performances by avoiding a lot of clones.

**Files**
[flamegraph-benchmark.tar.gz](https://github.com/tweag/nickel/files/7994645/flamegraph-benchmark.tar.gz)



Pull request description:
Label: make types field a Rc
Fixes #603 

This was an easy win, simply changing the `types` field in `Label` to an `Rc<Types>` gave instant improvement in performances, as seen on those benchmarks:
[criterion.tar.gz](https://github.com/tweag/nickel/files/8024099/criterion.tar.gz) (decompress and open _report/index.html_)

The flamegraph generated from the same benchmark doesn't even show any `Label` operation anymore:
![image](https://user-images.githubusercontent.com/4235083/152996743-4f27961b-33fe-447d-bee8-dc8e722c8ff4.png)


Patch:
diff --git a/.github/workflows/deploy-preview.yml b/.github/workflows/deploy-preview.yml
index e1434aed..717bd1ec 100644
--- a/.github/workflows/deploy-preview.yml
+++ b/.github/workflows/deploy-preview.yml
@@ -6,6 +6,8 @@ jobs:
   deploy:
     uses: tweag/nickel-lang.org/.github/workflows/deploy.yml@master
     with:
+      nickel_repository: ${{ github.repository }}
+      nickel_ref: ${{ github.sha }}
       production_deploy: false
     secrets:
       CACHIX_AUTH_TOKEN: ${{ secrets.CACHIX_AUTH_TOKEN }}
diff --git a/.github/workflows/update-flake-lock.yml b/.github/workflows/update-flake-lock.yml
index 7febf69b..0e9eaa2e 100644
--- a/.github/workflows/update-flake-lock.yml
+++ b/.github/workflows/update-flake-lock.yml
@@ -16,4 +16,4 @@ jobs:
           extra_nix_config: |
             access-tokens = github.com=${{ secrets.GITHUB_TOKEN }}
       - name: Update flake.lock
-        uses: DeterminateSystems/update-flake-lock@v8
+        uses: DeterminateSystems/update-flake-lock@v7
diff --git a/Cargo.lock b/Cargo.lock
index d73ac2f2..b7306dd3 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -128,9 +128,9 @@ dependencies = [
 
 [[package]]
 name = "beef"
-version = "0.5.1"
+version = "0.4.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "bed554bd50246729a1ec158d08aa3235d1b69d94ad120ebe187e28894787e736"
+checksum = "474a626a67200bd107d44179bb3d4fc61891172d11696609264589be6a0e6a43"
 
 [[package]]
 name = "bit-set"
@@ -788,18 +788,18 @@ dependencies = [
 
 [[package]]
 name = "logos"
-version = "0.12.0"
+version = "0.11.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "427e2abca5be13136da9afdbf874e6b34ad9001dd70f2b103b083a85daa7b345"
+checksum = "b91c49573597a5d6c094f9031617bb1fed15c0db68c81e6546d313414ce107e4"
 dependencies = [
  "logos-derive",
 ]
 
 [[package]]
 name = "logos-derive"
-version = "0.12.0"
+version = "0.11.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "56a7d287fd2ac3f75b11f19a1c8a874a7d55744bd91f7a1b3e7cf87d4343c36d"
+checksum = "797b1f8a0571b331c1b47e7db245af3dc634838da7a92b3bef4e30376ae1c347"
 dependencies = [
  "beef",
  "fnv",
diff --git a/Cargo.toml b/Cargo.toml
index 973fd10f..8a3dc8b5 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -30,7 +30,7 @@ regex = "0.2.1"
 simple-counter = "0.1.0"
 codespan = "0.11"
 codespan-reporting = "0.11"
-logos = "0.12.0"
+logos = "0.11.4"
 serde = { version = "1.0.117", features = ["derive"] }
 serde_json = "1.0.59"
 serde_yaml = "0.8.15"
diff --git a/benches/lists.rs b/benches/lists.rs
index c9054e87..9cc88013 100644
--- a/benches/lists.rs
+++ b/benches/lists.rs
@@ -218,9 +218,21 @@ fn pipe_deepseq(c: &mut Criterion) {
     );
 }
 
+fn sort_normal(c: &mut Criterion) {
+    bench(
+        "sort normal",
+        env!("CARGO_MANIFEST_DIR"),
+        "lists/sort",
+        None,
+        20,
+        EvalMode::Normal,
+        c,
+    );
+}
+
 criterion_group! {
     name = benches;
     config = Criterion::default().with_profiler(PProfProfiler::new(100, Output::Flamegraph(None)));
-    targets = fold_strings, fold_strings_deep, fold_nums, fold_nums_deep, fold_lists, fold_lists_deep, foldl_strings, foldl_strings_deep, foldl_nums, foldl_nums_deep, foldl_lists, foldl_lists_deep, generate_normal, generate_deepseq, map_normal, map_deepseq, pipe_normal, pipe_deepseq
+    targets = fold_strings, fold_strings_deep, fold_nums, fold_nums_deep, fold_lists, fold_lists_deep, foldl_strings, foldl_strings_deep, foldl_nums, foldl_nums_deep, foldl_lists, foldl_lists_deep, generate_normal, generate_deepseq, map_normal, map_deepseq, pipe_normal, pipe_deepseq, sort_normal
 }
 criterion_main!(benches);
diff --git a/benches/lists/sort.ncl b/benches/lists/sort.ncl
new file mode 100644
index 00000000..88f03cc6
--- /dev/null
+++ b/benches/lists/sort.ncl
@@ -0,0 +1,5 @@
+let nums = [3288, 2438, 1462, 437, 17, 1929, 2595, 2702, 831, 3685, 1906, 420, 2646, 1906, 2539, 184, 299, 3455, 2320, 1471, 1812, 3837, 1000, 2097, 945, 1973, 1090, 2285, 2272, 1045, 848, 3194, 2113, 537, 1953, 561, 2082, 2416, 3182, 3660, 3379, 1458, 39, 2720, 2469, 811, 837, 548, 3021, 2961, 2860, 2092, 942, 2511, 1769, 168, 130, 2755, 2552, 1057, 2619, 1848, 2373, 2012, 2339, 2521, 3593, 2784, 3094, 2260, 1994, 690, 828, 1298, 3434, 2929, 2188, 1285, 3783, 3635, 971, 3334, 87, 1578, 1363, 533, 3634, 1874, 830, 3976, 1140, 789, 1483, 1966, 1626, 3552, 2968, 3301, 749, 2576] in
+let ascending = fun x y => if x < y then `Less else if (x == y) then `Equal else `Greater in
+{
+    run = fun n => lists.sort ascending nums
+}
diff --git a/flake.lock b/flake.lock
index bcfdee51..79a3d55d 100644
--- a/flake.lock
+++ b/flake.lock
@@ -2,11 +2,11 @@
   "nodes": {
     "flake-utils": {
       "locked": {
-        "lastModified": 1642700792,
-        "narHash": "sha256-XqHrk7hFb+zBvRg6Ghl+AZDq03ov6OshJLiSWOoX5es=",
+        "lastModified": 1638122382,
+        "narHash": "sha256-sQzZzAbvKEqN9s0bzWuYmRaA03v40gaJ4+iL1LXjaeI=",
         "owner": "numtide",
         "repo": "flake-utils",
-        "rev": "846b2ae0fc4cc943637d3d1def4454213e203cba",
+        "rev": "74f7e4319258e287b0f9cb95426c9853b282730b",
         "type": "github"
       },
       "original": {
@@ -32,11 +32,11 @@
     },
     "nixpkgs": {
       "locked": {
-        "lastModified": 1643805626,
-        "narHash": "sha256-AXLDVMG+UaAGsGSpOtQHPIKB+IZ0KSd9WS77aanGzgc=",
+        "lastModified": 1631118067,
+        "narHash": "sha256-tEcFvm3a6ToeBGwHdjfB2mVQwa4LZCZTQYE2LnY3ycA=",
         "owner": "NixOS",
         "repo": "nixpkgs",
-        "rev": "554d2d8aa25b6e583575459c297ec23750adb6cb",
+        "rev": "09cd65b33c5653d7d2954fef4b9f0e718c899743",
         "type": "github"
       },
       "original": {
@@ -87,11 +87,11 @@
         ]
       },
       "locked": {
-        "lastModified": 1644027577,
-        "narHash": "sha256-PnmH8XLZr2bH/AtdjJX5RDl9j/jvror4Udqwz4ljvSo=",
+        "lastModified": 1642301007,
+        "narHash": "sha256-YKs/KV8Rdv8K33RidbjH78nZeMDqKUCwsdq8bow7Ogc=",
         "owner": "oxalica",
         "repo": "rust-overlay",
-        "rev": "01b7c9b7130faa2856a1d3f226f5e42dcaae744b",
+        "rev": "9c426beb3820ca3ede6349c664eb461ae4603565",
         "type": "github"
       },
       "original": {
diff --git a/flake.nix b/flake.nix
index e82c4e95..f0212b17 100644
--- a/flake.nix
+++ b/flake.nix
@@ -52,8 +52,8 @@
               tarball = final.fetchFromGitHub {
                 owner = "rustwasm";
                 repo = "wasm-bindgen";
-                rev = WasmBindgenVersion;
-                hash = "sha256:041mp2ls78iji4w1v3kka2bbcj0pjwy7svpslk2rhldkymhxmjhs";
+                rev = version;
+                hash = "sha256-GsraYfWzUZjFpPpufTyXF0i2llBzjh04iTKio6m4NRA=";
               };
             in
             final.runCommand "source" { } ''
@@ -61,9 +61,6 @@
               chmod -R +w $out
               cp ${./wasm-bindgen-api-Cargo.lock} $out/Cargo.lock
             '';
-          checkInputs = [ ];
-          cargoTestFlags = [ ];
-          cargoBuildFlags = [ "-p" old.pname ];
           cargoDeps = old.cargoDeps.overrideAttrs (final.lib.const {
             name = "${old.pname}-${version}-vendor.tar.gz";
             inherit src;
@@ -351,8 +348,7 @@
       checks = {
         # wasm-opt can take long: eschew optimizations in checks
         wasm = buildNickelWASM { channel = "stable"; optimize = false; };
-        # out of sync, disabling for now -> https://github.com/tweag/nickel/issue/552
-        #specs = makamSpecs;
+        specs = makamSpecs;
         pre-commit = defaultPackage.pre-commit;
       } // (forEachRustChannel (channel:
         {
diff --git a/src/label.rs b/src/label.rs
index 700c0742..2ee0509e 100644
--- a/src/label.rs
+++ b/src/label.rs
@@ -2,6 +2,8 @@
 //!
 //! A label is a value holding metadata relative to contract checking. It gives the user useful
 //! information about the context of a contract failure.
+use std::rc::Rc;
+
 use crate::eval::lazy::Thunk;
 use crate::position::{RawSpan, TermPos};
 use crate::types::{AbsType, Types};
@@ -232,7 +234,7 @@ pub mod ty_path {
 #[derive(Debug, Clone, PartialEq)]
 pub struct Label {
     /// The type checked by the original contract.
-    pub types: Types,
+    pub types: Rc<Types>,
     /// A string tag to be printed together with the error message.
     pub tag: String,
     /// The position of the original contract.
@@ -252,7 +254,7 @@ impl Label {
     /// Generate a dummy label for testing purpose.
     pub fn dummy() -> Label {
         Label {
-            types: Types(AbsType::Num()),
+            types: Rc::new(Types(AbsType::Num())),
             tag: "testing".to_string(),
             span: RawSpan {
                 src_id: Files::new().add("<test>", String::from("empty")),
diff --git a/src/parser/lexer.rs b/src/parser/lexer.rs
index b98a97da..322843df 100644
--- a/src/parser/lexer.rs
+++ b/src/parser/lexer.rs
@@ -333,7 +333,7 @@ pub enum MultiStringToken<'input> {
     /// The other rules should be sufficient to match this as a double quote followed by a
     /// `CandidateInterpolation`, but if we omit this token, the lexer can fail unexpectedly on
     /// valid inputs because of #200.
-    #[regex("\"#+\\{")]
+    #[token("\"#+\\{")]
     QuotesCandidateInterpolation(&'input str),
     /// Token emitted by the modal lexer for the parser once it has decided that a `CandidateEnd` is
     /// an actual end token.
@@ -437,7 +437,7 @@ impl<'input> Lexer<'input> {
             //  `Normal`
             Some(ModalLexer::Normal(lexer)) => {
                 self.stack.push(ModeElt::Normal(self.count));
-                self.lexer = Some(morph(lexer));
+                self.lexer.replace(morph(lexer));
             }
             _ => panic!("lexer::enter_strlike"),
         }
@@ -457,11 +457,11 @@ impl<'input> Lexer<'input> {
         match self.lexer.take() {
             //count must be zero, and we do not push it on the stack
             Some(ModalLexer::Str(lexer)) => {
-                self.lexer = Some(ModalLexer::Normal(lexer.morph()));
+                self.lexer.replace(ModalLexer::Normal(lexer.morph()));
                 self.stack.push(ModeElt::Str);
             }
             Some(ModalLexer::MultiStr(lexer)) => {
-                self.lexer = Some(ModalLexer::Normal(lexer.morph()));
+                self.lexer.replace(ModalLexer::Normal(lexer.morph()));
                 self.stack.push(ModeElt::MultiStr(self.count));
             }
             _ => panic!("lexer::enter_normal"),
@@ -479,7 +479,7 @@ impl<'input> Lexer<'input> {
                     mode => panic!("lexer::leave_str (popped mode {:?})", mode),
                 };
 
-                self.lexer = Some(ModalLexer::Normal(lexer.morph()));
+                self.lexer.replace(ModalLexer::Normal(lexer.morph()));
             }
             _ => panic!("lexer::leave_str"),
         }
@@ -494,7 +494,7 @@ impl<'input> Lexer<'input> {
                     mode => panic!("lexer::leave_str (popped mode {:?})", mode),
                 };
 
-                self.lexer = Some(ModalLexer::Normal(lexer.morph()));
+                self.lexer.replace(ModalLexer::Normal(lexer.morph()));
             }
             _ => panic!("lexer::leave_str"),
         }
@@ -505,10 +505,10 @@ impl<'input> Lexer<'input> {
             Some(ModalLexer::Normal(lexer)) => {
                 // count must be 0
                 match self.stack.pop() {
-                    Some(ModeElt::Str) => self.lexer = Some(ModalLexer::Str(lexer.morph())),
+                    Some(ModeElt::Str) => self.lexer.replace(ModalLexer::Str(lexer.morph())),
                     Some(ModeElt::MultiStr(count)) => {
                         self.count = count;
-                        self.lexer = Some(ModalLexer::MultiStr(lexer.morph()))
+                        self.lexer.replace(ModalLexer::MultiStr(lexer.morph()))
                     }
                     mode => panic!("lexer::leave_normal (popped mode {:?})", mode),
                 };
@@ -566,36 +566,28 @@ impl<'input> Iterator for Lexer<'input> {
                 token = Some(MultiStr(MultiStringToken::Interpolation));
                 self.enter_normal();
             }
-            // We never lex something as a `MultiStringToken::Interpolation` directly, but rather
-            // generate it in this very function from other tokens. However, such a token could
-            // have still been buffered in the previous iteration, and can thus be matched here,
-            // which is why we need the case below.
-            Some(MultiStr(MultiStringToken::Interpolation)) => self.enter_normal(),
             // If we encouter a `QuotesCandidateInterpolation` token with the right number of
             // characters, we need to split it into two tokens:
-            // - a literal starting by a `"` followed by between 0 and k hashes `#`
-            // - an interpolation token
+            // - a simple `"` literal
+            // - a interpolation token
             // The interpolation token is put in the buffer such that it will be returned next
             // time.
-            //
-            // For example, in `m##""###{exp}"##m`, the `"###{` is a `QuotesCandidateInterpolation`
-            // which is split as a `"#` literal followed by an interpolation token.
             Some(MultiStr(MultiStringToken::QuotesCandidateInterpolation(s)))
-                if s.len() >= self.count =>
+                if s.len() == self.count =>
             {
-                let split_at = s.len() - self.count + 1;
                 let next_token = MultiStr(MultiStringToken::Interpolation);
                 let next_span = Range {
-                    start: span.start + split_at,
+                    start: span.start + 1,
                     end: span.end,
                 };
-                self.buffer = Some((next_token, next_span));
+                self.buffer.replace((next_token, next_span));
 
-                token = Some(MultiStr(MultiStringToken::Literal(&s[0..split_at])));
+                token = Some(MultiStr(MultiStringToken::Literal(&s[0..1])));
                 span = Range {
                     start: span.start,
-                    end: span.start + split_at,
+                    end: span.start + 1,
                 };
+                self.enter_normal();
             }
             // Otherwise, it is just part of the string, so we transform the token into a
             // `FalseInterpolation` one
@@ -645,7 +637,7 @@ impl<'input> Iterator for Lexer<'input> {
             // Ignore comment
             Some(Normal(NormalToken::LineComment)) => return self.next(),
             _ => (),
-        };
+        }
 
         token.map(|t| Ok((span.start, t, span.end)))
     }
diff --git a/src/parser/utils.rs b/src/parser/utils.rs
index 73471720..0f4941f9 100644
--- a/src/parser/utils.rs
+++ b/src/parser/utils.rs
@@ -3,6 +3,7 @@
 use std::collections::hash_map::Entry;
 use std::collections::{HashMap, HashSet};
 use std::fmt::Debug;
+use std::rc::Rc;
 
 use codespan::FileId;
 
@@ -302,7 +303,7 @@ pub fn mk_pos(src_id: FileId, l: usize, r: usize) -> TermPos {
 /// Same as `mk_span`, but for labels.
 pub fn mk_label(types: Types, src_id: FileId, l: usize, r: usize) -> Label {
     Label {
-        types,
+        types: Rc::new(types),
         tag: String::new(),
         span: mk_span(src_id, l, r),
         arg_thunk: None,


Test patch:
diff --git a/src/parser/tests.rs b/src/parser/tests.rs
index 83f9479a..792d979c 100644
--- a/src/parser/tests.rs
+++ b/src/parser/tests.rs
@@ -279,7 +279,8 @@ fn string_lexing() {
         lex_without_pos(r##"m#""#"#m"##),
         Ok(vec![
             Token::Normal(NormalToken::MultiStringStart(3)),
-            Token::MultiStr(MultiStringToken::Literal("\"#")),
+            Token::MultiStr(MultiStringToken::Literal("\"")),
+            Token::MultiStr(MultiStringToken::Literal("#")),
             Token::MultiStr(MultiStringToken::End),
         ])
     );
diff --git a/tests/pass/strings.ncl b/tests/pass/strings.ncl
index 6ed8c7b9..9648f296 100644
--- a/tests/pass/strings.ncl
+++ b/tests/pass/strings.ncl
@@ -15,10 +15,5 @@ let Assert = fun l x => x || %blame% l in
   m#""#{"foo"}""#m == "\"foo\"",
   m#"""#m == "\"",
   m#""#"#"#"#m == "\"#\"#\"#",
-
-  // regression test for issue #596 (https://github.com/tweag/nickel/issues/596)
-  let s = "Hello" in m##""##{s}" World"##m == "\"Hello\" World",
-  let s = "Hello" in m##""###{s}" World"##m == "\"#Hello\" World",
-  m##""##s"##m == "\"##s",
 ]
 |> lists.foldl (fun x y => (x | #Assert) && y) true