Repository: tweag/nickel (rust)

Issue:
Interpolation in multiline strings doesn't work as expected
**Describe the bug**
In some situation, an interpolation sequence `#{exp}` inside a multi-line string is not interpreted as it should be.

**To Reproduce**
```
nickel> let x = "1" in m#""#{x}""#m
""#{1}""

nickel>
```

**Expected behavior**
`#{x}` should be properly interpolated as `1`

```
nickel> let x = "1" in m#""#{x}""#m
""1""

nickel>
```

**Additional context**
This seems to happen in particular when a double quote `"` precedes the interpolation sequence `#{`. I suspect it is consumed by the lexer as a potential closing delimiter `"#m`, taking precedence over `#{`.  


Pull request description:
Fix interpolation in multiline strings
Fix #361. The grammar definition of the lexer was wrong, but there should have been a simple fix: to get rid of the token `"#+` and just keep `"` and `#` alone for non-significant quotes/hash. The rules for end of string and interpolation would be matched in priority according to the rules of Logos (longest, most specific first).

Unfortunately, if we do that, the lexer fails on valid input, which I highly suspect is a manifestation of https://github.com/maciejhirsz/logos/issues/200 and/or https://github.com/maciejhirsz/logos/issues/181, and seems nowhere near being fixed.

To overcome the problem, this PR uses an additional token for a quote followed by a potential interpolation (`QuotesCandidateInterpolation` in the code) that is superfluous but specific enough to get the lexer working. However, this actually corresponds to two tokens, and since Logos doesn't have look-ahead/peeking capabilities, I had to add a 1-character buffer in the lexer to be able to return the quote token while storing the candidate interpolation as a pending token.

This is a bit of a shame to introduce a look-ahead buffer just for this, but as the buffer is almost never used, we can hope that branch prediction makes a good job at making the additional workload insignificant.

Patch:
diff --git a/examples/config-gcc/config-gcc.ncl b/examples/config-gcc/config-gcc.ncl
index 18a216ab..19301944 100644
--- a/examples/config-gcc/config-gcc.ncl
+++ b/examples/config-gcc/config-gcc.ncl
@@ -16,7 +16,7 @@ let GccFlag =
         //Normalize the tag to a string
         value.flag ++ value.arg
       else
-        contracts.blame (contracts.tag "unknown flag #{value.flag}")
+        contracts.blame (contracts.tag "unkown flag #{value.flag}")
     else
       contracts.blame (contracts.tag "bad record structure: missing field
         `flag` or `arg`" label)
diff --git a/src/error.rs b/src/error.rs
index 35c04dd3..b2bf96cf 100644
--- a/src/error.rs
+++ b/src/error.rs
@@ -481,7 +481,7 @@ fn secondary(span: &RawSpan) -> Label<FileId> {
 ///
 /// ```ignore
 /// error: some error
-///   -- <unknown> (generated by evaluation):1:2
+///   -- <unkown> (generated by evaluation):1:2
 ///   |
 /// 1 | { ... }
 ///     ^^^^^^^ some annotation
@@ -524,7 +524,7 @@ fn label_alt(
             let range = 0..alt_term.len();
             Label::new(
                 style,
-                files.add("<unknown> (generated by evaluation)", alt_term),
+                files.add("<unkown> (generated by evaluation)", alt_term),
                 range,
             )
         }
@@ -1452,7 +1452,7 @@ impl ToDiagnostic<FileId> for REPLError {
     ) -> Vec<Diagnostic<FileId>> {
         match self {
             REPLError::UnknownCommand(s) => vec![Diagnostic::error()
-                .with_message(format!("unknown command `{}`", s))
+                .with_message(format!("unkown command `{}`", s))
                 .with_notes(vec![String::from(
                     "type `:?` or `:help` for a list of available commands.",
                 )])],
diff --git a/src/grammar.lalrpop b/src/grammar.lalrpop
index a33a316e..fa1ce65a 100644
--- a/src/grammar.lalrpop
+++ b/src/grammar.lalrpop
@@ -307,10 +307,7 @@ StaticString: String = StringStart <s: ChunkLiteral> StringEnd => s;
 
 ChunkLiteralPart: ChunkLiteralPart<'input> = {
     "str literal" => ChunkLiteralPart::Str(<>),
-    "str #" => ChunkLiteralPart::Str(<>),
     "multstr literal" => ChunkLiteralPart::Str(<>),
-    "false interpolation" => ChunkLiteralPart::Str(<>),
-    "false end" => ChunkLiteralPart::Str(<>),
     "str esc char" => ChunkLiteralPart::Char(<>),
     };
 
@@ -568,11 +565,8 @@ extern {
     enum Token<'input> {
         "identifier" => Token::Normal(NormalToken::Identifier(<&'input str>)),
         "str literal" => Token::Str(StringToken::Literal(<&'input str>)),
-        "str #" => Token::Str(StringToken::Hash(<&'input str>)),
         "str esc char" => Token::Str(StringToken::EscapedChar(<char>)),
         "multstr literal" => Token::MultiStr(MultiStringToken::Literal(<&'input str>)),
-        "false end" => Token::MultiStr(MultiStringToken::FalseEnd(<&'input str>)),
-        "false interpolation" => Token::MultiStr(MultiStringToken::FalseInterpolation(<&'input str>)),
         "num literal" => Token::Normal(NormalToken::NumLiteral(<f64>)),
 
         "if" => Token::Normal(NormalToken::If),
diff --git a/src/parser/lexer.rs b/src/parser/lexer.rs
index 5c73d6bf..021bdbc5 100644
--- a/src/parser/lexer.rs
+++ b/src/parser/lexer.rs
@@ -30,6 +30,7 @@
 //! go back to string mode. In our example, this is the second `}`: at this point, the lexer knows
 //! that the coming characters must be lexed as string tokens, and not as normal tokens.
 use logos::Logos;
+use std::ops::Range;
 
 /// The tokens in normal mode.
 #[derive(Logos, Debug, PartialEq, Clone)]
@@ -281,13 +282,12 @@ pub enum StringToken<'input> {
     Error,
 
     #[regex("[^\"#\\\\]+")]
+    // Has lower matching priority than `HashBrace` according to Logos' rules.
+    #[token("#")]
     Literal(&'input str),
 
     #[token("\"")]
     DoubleQuote,
-    // Has lower matching priority than `HashBrace` according to Logos' rules.
-    #[token("#")]
-    Hash(&'input str),
     #[token("#{")]
     HashBrace,
     #[regex("\\\\.", |lex| lex.slice().chars().nth(1))]
@@ -304,27 +304,30 @@ pub enum MultiStringToken<'input> {
     Error,
 
     #[regex("[^\"#]+")]
+    // A token that starts as a multiline end delimiter or an interpolation sequence but is not
+    // one.  These ones should have lowest matching priority according to Logos' rules, and
+    // CandidateEnd and CandidateInterpolation should be matched first.
+    #[token("\"")]
+    #[regex("#+")]
     Literal(&'input str),
 
-    // A token that starts as a multiline end delimiter, but is not one. To avoid hacking
-    // look-aheads in the lexer (which Logos doesn't support for performance reason), we just use a
-    // separate token. This one has lowest matching priority according to Logos' rules, so it is
-    // matched only if `CandidateEnd` cannot be
-    #[regex("\"#*")]
-    FalseEnd(&'input str),
-    // A candidate end. A multiline string starting delimiter `MultiStringStart` can have a
-    // variable number of `#` character, so the lexer matchs candidate end delimiter, compare the
-    // number of characters, and either emit the `End` token above, or turn the `CandidateEnd` to a
-    // `FalseEnd` otherwise
+    /// A candidate end. A multiline string starting delimiter `MultiStringStart` can have a
+    /// variable number of `#` character, so the lexer matches candidate end delimiter, compare the
+    /// number of characters, and either emit the `End` token above, or turn the `CandidateEnd` to a
+    /// `FalseEnd` otherwise
     #[regex("\"#+m")]
     CandidateEnd(&'input str),
-    // Same as `FalseEnd` and `CandidateEnd` but for an interpolation sequence.
-    #[regex("#+")]
-    FalseInterpolation(&'input str),
+    /// Same as `CandidateEnd`, but for interpolation
     #[regex("#+\\{")]
     CandidateInterpolation(&'input str),
-    // Token emitted by the modal lexer for the parser once it has decided that a `CandidateEnd` is
-    // an actual end token.
+    /// Unfortunate consequence of Logos' issue #200 (https://github.com/maciejhirsz/logos/issues/200).
+    /// 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.
+    #[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.
     End,
     Interpolation,
 }
@@ -412,6 +415,10 @@ pub struct Lexer<'input> {
     /// already inside an interpolated expression. In this case, once this string ends, we must
     /// restore the original brace counter, which is what this stack is used for.
     pub stack: Vec<ModeElt>,
+    /// A token that has been buffered and must be returned at the next call to `next()`. This is
+    /// made necessary by an issue of Logos (https://github.com/maciejhirsz/logos/issues/200). See
+    /// `MultiStringToken::QuotesCandidateInterpolation`.
+    pub buffer: Option<(Token<'input>, Range<usize>)>,
 }
 
 impl<'input> Lexer<'input> {
@@ -420,6 +427,7 @@ impl<'input> Lexer<'input> {
             lexer: Some(ModalLexer::Normal(NormalToken::lexer(s))),
             stack: Vec::new(),
             count: 0,
+            buffer: None,
         }
     }
 
@@ -519,9 +527,14 @@ impl<'input> Iterator for Lexer<'input> {
     fn next(&mut self) -> Option<Self::Item> {
         use Token::*;
 
-        let lexer = self.lexer.as_mut().unwrap();
-        let mut token = lexer.next();
-        let span = lexer.span();
+        let (mut token, mut span) = if let Some((token, span)) = self.buffer.take() {
+            (Some(token), span)
+        } else {
+            let lexer = self.lexer.as_mut().unwrap();
+            let token = lexer.next();
+            let span = lexer.span();
+            (token, span)
+        };
 
         match token.as_ref() {
             Some(Normal(NormalToken::DoubleQuote)) => self.enter_str(),
@@ -554,10 +567,34 @@ impl<'input> Iterator for Lexer<'input> {
                 token = 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 simple `"` literal
+            // - a interpolation token
+            // The interpolation token is put in the buffer such that it will be returned next
+            // time.
+            Some(MultiStr(MultiStringToken::QuotesCandidateInterpolation(s)))
+                if s.len() == self.count =>
+            {
+                let next_token = MultiStr(MultiStringToken::Interpolation);
+                let next_span = Range {
+                    start: span.start + 1,
+                    end: span.end,
+                };
+                self.buffer.replace((next_token, next_span));
+
+                token = Some(MultiStr(MultiStringToken::Literal(&s[0..1])));
+                span = Range {
+                    start: span.start,
+                    end: span.start + 1,
+                };
+                self.enter_normal();
+            }
             // Otherwise, it is just part of the string, so we transform the token into a
             // `FalseInterpolation` one
-            Some(MultiStr(MultiStringToken::CandidateInterpolation(s))) => {
-                token = Some(MultiStr(MultiStringToken::FalseInterpolation(s)))
+            Some(MultiStr(MultiStringToken::CandidateInterpolation(s)))
+            | Some(MultiStr(MultiStringToken::QuotesCandidateInterpolation(s))) => {
+                token = Some(MultiStr(MultiStringToken::Literal(s)))
             }
             Some(Str(StringToken::HashBrace)) => self.enter_normal(),
             // Convert escape sequences to the corresponding character.
@@ -584,7 +621,7 @@ impl<'input> Iterator for Lexer<'input> {
             // Otherwise, it is just part of the string, so we transform the token into a
             // `FalseEnd` one
             Some(MultiStr(MultiStringToken::CandidateEnd(s))) => {
-                token = Some(MultiStr(MultiStringToken::FalseEnd(s)))
+                token = Some(MultiStr(MultiStringToken::Literal(s)))
             }
             // Early report errors for now. This could change in the future
             Some(Normal(NormalToken::Error))


Test patch:
diff --git a/src/parser/tests.rs b/src/parser/tests.rs
index d9c0e39d..ac133d07 100644
--- a/src/parser/tests.rs
+++ b/src/parser/tests.rs
@@ -1,4 +1,4 @@
-use super::lexer::{Lexer, LexicalError, NormalToken, StringToken, Token};
+use super::lexer::{Lexer, LexicalError, MultiStringToken, NormalToken, StringToken, Token};
 use crate::error::ParseError;
 use crate::identifier::Ident;
 use crate::term::make as mk_term;
@@ -252,6 +252,16 @@ fn string_lexing() {
             Token::Normal(NormalToken::DoubleQuote),
         ])
     );
+
+    assert_eq!(
+        lex_without_pos(r##"m#""#"#m"##),
+        Ok(vec![
+            Token::Normal(NormalToken::MultiStringStart(3)),
+            Token::MultiStr(MultiStringToken::Literal("\"")),
+            Token::MultiStr(MultiStringToken::Literal("#")),
+            Token::MultiStr(MultiStringToken::End),
+        ])
+    );
 }
 
 #[test]
diff --git a/tests/pass/strings.ncl b/tests/pass/strings.ncl
index 7f96a6fa..5ae7aed0 100644
--- a/tests/pass/strings.ncl
+++ b/tests/pass/strings.ncl
@@ -13,5 +13,11 @@ let Assert = fun l x => x || %blame% l in
 ((let x = "world" in
   "Hello, #{x}! Welcome in #{let y = "universe" in "the #{x}-#{y}"}")
   == "Hello, world! Welcome in the world-universe" | #Assert) &&
+
+// regression test for issue #361 (https://github.com/tweag/nickel/issues/361)
+(m#""#{"foo"}""#m == "\"foo\"" | #Assert) &&
+(m#"""#m == "\"" | #Assert) &&
+(m#""#"#"#"#m == "\"#\"#\"#" | #Assert) &&
+
 true