Repository: encode/httpx

Issue:
LineDecoder is accidentally quadratic: iter_lines() seems to hang forever
When calling `Response.iter_lines()`, things can seem to hang forever.

The problem is that `LineDecoder` is quadratic in it's string copying behaviour. If a 31MB chunk with 18,768 lines is passed in to `LineDecoder()` then it takes 1m45s to process it vs 0.1s for a simple `text.splitlines()`. This is readily reproduced by simply using `LineDecoder()` to decode a file, like `/usr/share/dict/words` (do not attempt, you may be waiting until the heat death of the universe).

It may be a bug somewhere else that `iter_text()` is returning chunks that are too big.

But either way, you probably want to reconsider the wisdom of slicing the string to chop the beginning off it vs. just keeping an index.

You can slice the string before returning from the decoder so it's only done once per chunk.

Anyhoo, thanks for the great work!

Discussion:
tomchristie: A solution using the built-in `splitlines` would probably be preferable to our own `regex`.
It might be worth taking a look at what `requests` does here?
giannitedesco: > A solution using the built-in `splitlines` would probably be preferable to our own `regex`. It might be worth taking a look at what `requests` does here?

Actually requests is using splitlines, too. So should I just switch to that and update the failing tests?
tomchristie: > So should I just switch to that and update the failing tests?

Switching to a `splitlines` based approach, using the `requests` implementation as a reference point would be a good starting point...

giannitedesco: Haha, yes, the first implementation I did with splitlines happens to be identical to theirs when refactored (ie. theirs is a generator, not based an object :joy: 
giannitedesco: @tomchristie Okay, so I've fixed up the tests, and glad I did because the `splitlines()` implementation was initially buggy when CRLF sequence was split across chunks which is an issue that the [requests implementation](https://github.com/psf/requests/blob/main/requests/models.py#L853-L885) looks like it fails to deal with. I've fixed that now and as long as you're OK with the returned elements being stripped of newlines now. It looks as though all correct, and all other semantics preserved.
giannitedesco: @florimondmanca @tomchristie is this acceptable? I suppose the benefit of this API is that if you do something like `''.join(resp.iter_lines())` you recover the original text and that means you could, for example, hash, encrypt, or compress the response body incrementally by lines without altering its contents? So, while incompatible, maybe it could be considered an improvement? But not sure the reasoning behind the previous normalization of line endings so who can say?
tomchristie: > is this acceptable?

No. I don't believe resolving this issue should require the tests to change.
tomchristie: Him. I'd not appreciated that we have different behaviour from `requests` here. That's interesting.
giannitedesco: Right, I feel like there are 3 options to what the behaviour could be:
1. no newlines (ala requests)
2. all newline types replaced with `"\n"` (ala httpx now)
3. all newlines preserved (result of this patch)

1 and 3 can be done efficiently and simply with `"".splitlines()`, and only 3 allows for reconstructing the exact original document after the fact (and therefore supports, eg. incrementally hashing a document line by line).

Preservation of the existing semantics could be done with a regex perhaps, but it's tricky to get right. Or maybe a straight python implementation that just doesn't start from the beginning every time, it wouldn't be as fast as the ones which call to C code, but it could at least be linear-time?

Lemme know which direction you want to take it and I can give it a go..
tomchristie: > Right, I feel like there are 3 options to what the behaviour could be.

I'd suggest that we've got the current behaviour wrong, and that we need a breaking API change here.
The *sensible* behaviour for `iter_lines` would be to match the same style as the sodlib's `splitlines()`.
So, yeah, I think we want option (1) here. (Right?)
ofek: > I think we want option (1) here. (Right?)

Yes imo
florimondmanca: After reading my comment pointing at à behavior change, it’s true that I would rather be expecting iter_lines() to return lines without new line separators at the end. This is what splitlines() does, but also other languages like Rust’s str.lines() (AdventOfCode season…), or JS when doing `.split(/\r?\n/)`, etc.
giannitedesco: The issue is if that we strip line endings it becomes very difficult to handle the case where a chunk ends with `"\r"` because splitlines() will handle that as an end of line, and we can't defer until the next call.

We can check if the input buffer ends in `"\r"` and defer til next time, but then that breaks the following test case:

```python
assert decoder.decode("a\r\rb\rc\r") == ["a", "", "b"] 
```

so the behaviour changes get bigger...

This is much easier to handle in the case with `splitlines(True)` because we can just see if the last line ends with `"\r"` *after* the split.

Pushed a version with the currently requested changes that demonstrates what I mean (see `test_line_decoder_cr()`)

But having implemented all permutations now, I would recommend going with option 3 for the API behaviour ("all newlines preserved", aka `splitlines(True)` :)
tomchristie: So, I found the `decode()` section a bit difficult to reason about, and figure if it was correct or not.

I tried to rationale it into a different structure, and came up with this...

```python
# See https://docs.python.org/3/library/stdtypes.html#str.splitlines
NEWLINE_CHARS = "\n\r\x0b\x0c\x1c\x1d\x1e\x85\u2028\u2029"

if self.buffer:
    # If we have some buffered text from the previous pass,
    # then we include it before handling the input.
    text = self.buffer + text
    self.buffer = ""

if not text:
    return []
elif text[-1] == "\r":
    # If the last character is "\r", then we might be about to see "\r\n"
    # newline seperator. We buffer the text input and return.
    self.buffer = text
    return []
elif text[-1] in NEWLINE_CHARS:
    # If the last character is a newline separator then we can simply split
    # the text into lines and return them. There is no remaining portion
    # to be dealt with on the next pass.
    return text.splitlines()
else:
    # If the last character is not a newline seperator, then the final portion
    # from `splitlines()` is incomplete and needs to be buffered for the next
    # pass.
    lines = text.splitlines()
    self.buffer = lines.pop()
    return lines
```

🤔
tomchristie: > Looks good, you may want to check if NEWLINE_CHARS is long enough to benefit from being a set() for the faster in check?

```python
>>> NEWLINE_CHARS = "\n\r\x0b\x0c\x1c\x1d\x1e\x85\u2028\u2029"
>>> NEWLINE_SET = set(["\n","\r","\x0b","\x0c","\x1c","\x1d","\x1e","\x85","\u2028","\u2029"])
>>> import timeit
>>> timeit.timeit('"a" in NEWLINE_CHARS', number=100000, globals=globals())
0.0037886500358581543
>>> timeit.timeit('"a" in NEWLINE_SET', number=100000, globals=globals())
0.003081643022596836
```

You'd want to make sure that `NEWLINE_SET` was only being instantiated once, and that you're accessing it as `self.NEWLINE_SET`.
tomchristie: Ugh. Tests are failing after I committed that. Will have to look into that some other time.
cdeler: LGTM (with a small style suggestion which can be easily ignored)
madkinsz: Can we also update this pull request title to note the change in behavior since it's no longer just a change in algo complexity?
tomchristie: Okay, I think we can merge this in now.
The line ending behaviour change means that we should bump the version on this one.

Patch:
diff --git a/httpx/_decoders.py b/httpx/_decoders.py
index 2f3a447..500ce7f 100644
--- a/httpx/_decoders.py
+++ b/httpx/_decoders.py
@@ -259,66 +259,56 @@ class LineDecoder:
     """
     Handles incrementally reading lines from text.
 
-    Uses universal line decoding, supporting any of `\n`, `\r`, or `\r\n`
-    as line endings, normalizing to `\n`.
+    Has the same behaviour as the stdllib splitlines, but handling the input iteratively.
     """
 
     def __init__(self) -> None:
-        self.buffer = ""
+        self.buffer: typing.List[str] = []
+        self.trailing_cr: bool = False
 
     def decode(self, text: str) -> typing.List[str]:
-        lines = []
-
-        if text and self.buffer and self.buffer[-1] == "\r":
-            if text.startswith("\n"):
-                # Handle the case where we have an "\r\n" split across
-                # our previous input, and our new chunk.
-                lines.append(self.buffer[:-1] + "\n")
-                self.buffer = ""
-                text = text[1:]
-            else:
-                # Handle the case where we have "\r" at the end of our
-                # previous input.
-                lines.append(self.buffer[:-1] + "\n")
-                self.buffer = ""
-
-        while text:
-            num_chars = len(text)
-            for idx in range(num_chars):
-                char = text[idx]
-                next_char = None if idx + 1 == num_chars else text[idx + 1]
-                if char == "\n":
-                    lines.append(self.buffer + text[: idx + 1])
-                    self.buffer = ""
-                    text = text[idx + 1 :]
-                    break
-                elif char == "\r" and next_char == "\n":
-                    lines.append(self.buffer + text[:idx] + "\n")
-                    self.buffer = ""
-                    text = text[idx + 2 :]
-                    break
-                elif char == "\r" and next_char is not None:
-                    lines.append(self.buffer + text[:idx] + "\n")
-                    self.buffer = ""
-                    text = text[idx + 1 :]
-                    break
-                elif next_char is None:
-                    self.buffer += text
-                    text = ""
-                    break
+        # See https://docs.python.org/3/library/stdtypes.html#str.splitlines
+        NEWLINE_CHARS = "\n\r\x0b\x0c\x1c\x1d\x1e\x85\u2028\u2029"
+
+        # We always push a trailing `\r` into the next decode iteration.
+        if self.trailing_cr:
+            text = "\r" + text
+            self.trailing_cr = False
+        if text.endswith("\r"):
+            self.trailing_cr = True
+            text = text[:-1]
+
+        if not text:
+            return []
+
+        trailing_newline = text[-1] in NEWLINE_CHARS
+        lines = text.splitlines()
+
+        if len(lines) == 1 and not trailing_newline:
+            # No new lines, buffer the input and continue.
+            self.buffer.append(lines[0])
+            return []
+
+        if self.buffer:
+            # Include any existing buffer in the first portion of the
+            # splitlines result.
+            lines = ["".join(self.buffer) + lines[0]] + lines[1:]
+            self.buffer = []
+
+        if not trailing_newline:
+            # If the last segment of splitlines is not newline terminated,
+            # then drop it from our output and start a new buffer.
+            self.buffer = [lines.pop()]
 
         return lines
 
     def flush(self) -> typing.List[str]:
-        if self.buffer.endswith("\r"):
-            # Handle the case where we had a trailing '\r', which could have
-            # been a '\r\n' pair.
-            lines = [self.buffer[:-1] + "\n"]
-        elif self.buffer:
-            lines = [self.buffer]
-        else:
-            lines = []
-        self.buffer = ""
+        if not self.buffer and not self.trailing_cr:
+            return []
+
+        lines = ["".join(self.buffer)]
+        self.buffer = []
+        self.trailing_cr = False
         return lines
 
 


Test patch:
diff --git a/tests/models/test_responses.py b/tests/models/test_responses.py
index cbd71e8..b0ac418 100644
--- a/tests/models/test_responses.py
+++ b/tests/models/test_responses.py
@@ -639,7 +639,7 @@ def test_iter_lines():
         content=b"Hello,\nworld!",
     )
     content = [line for line in response.iter_lines()]
-    assert content == ["Hello,\n", "world!"]
+    assert content == ["Hello,", "world!"]
 
 
 @pytest.mark.anyio
@@ -652,7 +652,7 @@ async def test_aiter_lines():
     content = []
     async for line in response.aiter_lines():
         content.append(line)
-    assert content == ["Hello,\n", "world!"]
+    assert content == ["Hello,", "world!"]
 
 
 def test_sync_streaming_response():
diff --git a/tests/test_decoders.py b/tests/test_decoders.py
index 35ddad2..728dee9 100644
--- a/tests/test_decoders.py
+++ b/tests/test_decoders.py
@@ -225,69 +225,69 @@ def test_text_decoder_empty_cases():
 def test_line_decoder_nl():
     decoder = LineDecoder()
     assert decoder.decode("") == []
-    assert decoder.decode("a\n\nb\nc") == ["a\n", "\n", "b\n"]
+    assert decoder.decode("a\n\nb\nc") == ["a", "", "b"]
     assert decoder.flush() == ["c"]
 
     decoder = LineDecoder()
     assert decoder.decode("") == []
-    assert decoder.decode("a\n\nb\nc\n") == ["a\n", "\n", "b\n", "c\n"]
+    assert decoder.decode("a\n\nb\nc\n") == ["a", "", "b", "c"]
     assert decoder.flush() == []
 
     # Issue #1033
     decoder = LineDecoder()
     assert decoder.decode("") == []
-    assert decoder.decode("12345\n") == ["12345\n"]
+    assert decoder.decode("12345\n") == ["12345"]
     assert decoder.decode("foo ") == []
     assert decoder.decode("bar ") == []
-    assert decoder.decode("baz\n") == ["foo bar baz\n"]
+    assert decoder.decode("baz\n") == ["foo bar baz"]
     assert decoder.flush() == []
 
 
 def test_line_decoder_cr():
     decoder = LineDecoder()
     assert decoder.decode("") == []
-    assert decoder.decode("a\r\rb\rc") == ["a\n", "\n", "b\n"]
+    assert decoder.decode("a\r\rb\rc") == ["a", "", "b"]
     assert decoder.flush() == ["c"]
 
     decoder = LineDecoder()
     assert decoder.decode("") == []
-    assert decoder.decode("a\r\rb\rc\r") == ["a\n", "\n", "b\n"]
-    assert decoder.flush() == ["c\n"]
+    assert decoder.decode("a\r\rb\rc\r") == ["a", "", "b"]
+    assert decoder.flush() == ["c"]
 
     # Issue #1033
     decoder = LineDecoder()
     assert decoder.decode("") == []
     assert decoder.decode("12345\r") == []
-    assert decoder.decode("foo ") == ["12345\n"]
+    assert decoder.decode("foo ") == ["12345"]
     assert decoder.decode("bar ") == []
     assert decoder.decode("baz\r") == []
-    assert decoder.flush() == ["foo bar baz\n"]
+    assert decoder.flush() == ["foo bar baz"]
 
 
 def test_line_decoder_crnl():
     decoder = LineDecoder()
     assert decoder.decode("") == []
-    assert decoder.decode("a\r\n\r\nb\r\nc") == ["a\n", "\n", "b\n"]
+    assert decoder.decode("a\r\n\r\nb\r\nc") == ["a", "", "b"]
     assert decoder.flush() == ["c"]
 
     decoder = LineDecoder()
     assert decoder.decode("") == []
-    assert decoder.decode("a\r\n\r\nb\r\nc\r\n") == ["a\n", "\n", "b\n", "c\n"]
+    assert decoder.decode("a\r\n\r\nb\r\nc\r\n") == ["a", "", "b", "c"]
     assert decoder.flush() == []
 
     decoder = LineDecoder()
     assert decoder.decode("") == []
     assert decoder.decode("a\r") == []
-    assert decoder.decode("\n\r\nb\r\nc") == ["a\n", "\n", "b\n"]
+    assert decoder.decode("\n\r\nb\r\nc") == ["a", "", "b"]
     assert decoder.flush() == ["c"]
 
     # Issue #1033
     decoder = LineDecoder()
     assert decoder.decode("") == []
-    assert decoder.decode("12345\r\n") == ["12345\n"]
+    assert decoder.decode("12345\r\n") == ["12345"]
     assert decoder.decode("foo ") == []
     assert decoder.decode("bar ") == []
-    assert decoder.decode("baz\r\n") == ["foo bar baz\n"]
+    assert decoder.decode("baz\r\n") == ["foo bar baz"]
     assert decoder.flush() == []