Better handling of ANSI escape codes in TextFlow

The new implementation keeps track of found escape codes in a separate
vector, which has two advantages:
1) The handling of inputs without any escape codes is much faster. As
   this will be the case for majority of inputs, this should provide
   nice speedup all around.
2) We no longer mangle unrelated 0xFFs in the user-provided input.

Closes #3199

2 files changed, 116 insertions, 73 deletions

diff --git a/src/catch2/internal/catch_textflow.cpp b/src/catch2/internal/catch_textflow.cpp
index 0646b10f..e85e0934 100644
--- a/src/catch2/internal/catch_textflow.cpp
+++ b/src/catch2/internal/catch_textflow.cpp
@@ -35,6 +35,15 @@ namespace {
 namespace Catch {
     namespace TextFlow {
         void AnsiSkippingString::preprocessString() {
+            // If there are no potential escapes, we can use fast path
+            if ( m_string.find( '\033' ) == std::string::npos ) {
+                size_t size = 0;
+                for ( const char c : m_string ) {
+                    size += !isUtf8ContinuationByte( c );
+                }
+                m_size = size;
+                return;
+            }
             for ( auto it = m_string.begin(); it != m_string.end(); ) {
                 // try to read through an ansi sequence
                 while ( it != m_string.end() && *it == '\033' &&
@@ -47,8 +56,10 @@ namespace Catch {
                     if ( cursor == m_string.end() || *cursor != 'm' ) {
                         break;
                     }
-                    // 'm' -> 0xff
-                    *cursor = AnsiSkippingString::sentinel;
+                    // record the escape sequence's byte range
+                    m_escapes.push_back(
+                        { std::distance( m_string.begin(), it ),
+                          std::distance( m_string.begin(), cursor + 1 ) } );
                     // if we've read an ansi sequence, set the iterator and
                     // return to the top of the loop
                     it = cursor + 1;
@@ -76,79 +87,102 @@ namespace Catch {
         }
 
         AnsiSkippingString::const_iterator AnsiSkippingString::begin() const {
-            return const_iterator( m_string );
+            return const_iterator( *this );
         }
 
         AnsiSkippingString::const_iterator AnsiSkippingString::end() const {
-            return const_iterator( m_string, const_iterator::EndTag{} );
+            return const_iterator( *this, const_iterator::EndTag{} );
         }
 
-        std::string AnsiSkippingString::substring( const_iterator begin,
-                                                   const_iterator end ) const {
+        std::string AnsiSkippingString::substring( const_iterator first,
+                                                   const_iterator last ) const {
+            std::string ret;
+            appendSubstringTo( ret, first, last );
+            return ret;
+        }
+
+        void
+        AnsiSkippingString::appendSubstringTo( std::string& out,
+                                               const_iterator first,
+                                               const_iterator last ) const {
             // There's one caveat here to an otherwise simple substring: when
             // making a begin iterator we might have skipped ansi sequences at
-            // the start. If `begin` here is a begin iterator, skipped over
+            // the start. If `first` here is a begin iterator, skipped over
             // initial ansi sequences, we'll use the true beginning of the
-            // string. Lastly: We need to transform any chars we replaced with
-            // 0xff back to 'm'
-            auto str = std::string( begin == this->begin() ? m_string.begin()
-                                                           : begin.m_it,
-                                    end.m_it );
-            std::transform( str.begin(), str.end(), str.begin(), []( char c ) {
-                return c == AnsiSkippingString::sentinel ? 'm' : c;
-            } );
-            return str;
-        }
-
-        void AnsiSkippingString::const_iterator::tryParseAnsiEscapes() {
-            // check if we've landed on an ansi sequence, and if so read through
-            // it
-            while ( m_it != m_string->end() && *m_it == '\033' &&
-                    m_it + 1 != m_string->end() &&  *( m_it + 1 ) == '[' ) {
-                auto cursor = m_it + 2;
-                while ( cursor != m_string->end() &&
-                        ( isdigit( *cursor ) || *cursor == ';' ) ) {
-                    ++cursor;
-                }
-                if ( cursor == m_string->end() ||
-                     *cursor != AnsiSkippingString::sentinel ) {
+            // string.
+            if ( hasEscapes() && first == begin() ) {
+                out.append( m_string.begin(), last.m_it );
+            } else {
+                out.append( first.m_it, last.m_it );
+            }
+        }
+
+        void AnsiSkippingString::const_iterator::jumpForwardOverEscapes() {
+            // Escapes can only start with '\033'
+            if ( m_it == m_string->m_string.end() || *m_it != '\033' ) {
+                return;
+            }
+            // If we are at '\033', check if we are at an actual escape
+            auto current_pos = std::distance( m_string->m_string.begin(), m_it );
+
+            auto const& escapes = m_string->m_escapes;
+            auto candidate =
+                std::lower_bound( escapes.begin(),
+                                  escapes.end(),
+                                  current_pos,
+                                  []( AnsiSkippingString::EscapeRange const& r,
+                                      std::ptrdiff_t o ) { return r.start < o; } );
+            // Escapes can be consecutive, we need to jump over all of them
+            while ( candidate != escapes.end() && candidate->start == current_pos ) {
+                current_pos = candidate->end;
+                ++candidate;
+            }
+            m_it = m_string->m_string.begin() + current_pos;
+        }
+
+        void AnsiSkippingString::const_iterator::jumpBackOverEscapes() {
+            auto strBegin = m_string->m_string.begin();
+            // Escapes only end with 'm'
+            while ( *m_it == 'm' ) {
+                // If we are at 'm', check if we are at an actual escape
+                const auto current_pos = std::distance( strBegin, m_it );
+
+                auto const& escapes = m_string->m_escapes;
+                auto range = std::lower_bound(
+                    escapes.begin(),
+                    escapes.end(),
+                    current_pos + 1, // to half-open range
+                    []( AnsiSkippingString::EscapeRange const& r,
+                        std::ptrdiff_t o ) { return r.end < o; } );
+                if ( range == escapes.end() || range->end != current_pos + 1 ) {
                     break;
                 }
-                // if we've read an ansi sequence, set the iterator and
-                // return to the top of the loop
-                m_it = cursor + 1;
+                assert( range->start != 0 &&
+                        "Trying to go back with begin iterator" );
+                m_it = strBegin + range->start - 1;
             }
         }
 
+
         void AnsiSkippingString::const_iterator::advance() {
-            assert( m_it != m_string->end() );
+            auto strEnd = m_string->m_string.end();
+            assert( m_it != strEnd );
             m_it++;
             // Skip UTF-8 continuation bytes
-            while ( m_it != m_string->end() &&
+            while ( m_it != strEnd &&
                     isUtf8ContinuationByte( *m_it ) ) {
                 m_it++;
             }
-            tryParseAnsiEscapes();
+            if ( m_string->hasEscapes() ) { jumpForwardOverEscapes(); }
         }
 
         void AnsiSkippingString::const_iterator::unadvance() {
-            assert( m_it != m_string->begin() );
+            auto strBegin = m_string->m_string.begin();
+            assert( m_it != strBegin );
             m_it--;
-            // if *m_it is 0xff, scan back to the \033 and then m_it-- once more
-            // (and repeat check)
-            while ( *m_it == AnsiSkippingString::sentinel ) {
-                while ( *m_it != '\033' ) {
-                    assert( m_it != m_string->begin() );
-                    m_it--;
-                }
-                // if this happens, we must have been a begin iterator that had
-                // skipped over ansi sequences at the start of a string
-                assert( m_it != m_string->begin() );
-                assert( *m_it == '\033' );
-                m_it--;
-            }
+            if ( m_string->hasEscapes() ) { jumpBackOverEscapes(); }
             // Skip back over UTF-8 continuation bytes to the leading byte
-            while ( m_it != m_string->begin() &&
+            while ( m_it != strBegin &&
                     isUtf8ContinuationByte( *m_it ) ) {
                 m_it--;
             }
@@ -226,10 +260,8 @@ namespace Catch {
             AnsiSkippingString::const_iterator end ) const {
             std::string ret;
             const auto desired_indent = indentSize();
-            // ret.reserve( desired_indent + (end - start) + m_addHyphen );
             ret.append( desired_indent, ' ' );
-            // ret.append( start, end );
-            ret += m_column.m_string.substring( start, end );
+            m_column.m_string.appendSubstringTo( ret, start, end );
             if ( m_addHyphen ) { ret.push_back( '-' ); }
 
             return ret;
diff --git a/src/catch2/internal/catch_textflow.hpp b/src/catch2/internal/catch_textflow.hpp
index 2d9d78a5..27c6f043 100644
--- a/src/catch2/internal/catch_textflow.hpp
+++ b/src/catch2/internal/catch_textflow.hpp
@@ -26,25 +26,30 @@ namespace Catch {
          * escape sequences are considered.
          *
          * Internal representation:
-         * An escape sequence looks like \033[39;49m
-         * We need bidirectional iteration and the unbound length of escape
-         * sequences poses a problem for operator-- To make this work we'll
-         * replace the last `m` with a 0xff (this is a codepoint that won't have
-         * any utf-8 meaning).
+         * * An escape sequence looks like \033[39;49m
+         * * The string is stored unmodified
+         * * Index ranges of escape sequences are stored in separate vector
          */
         class AnsiSkippingString {
+        public:
+            //! Byte offsets of an escape sequence: [start, end)
+            struct EscapeRange {
+                std::ptrdiff_t start;
+                std::ptrdiff_t end;
+            };
+
+        private:
             std::string m_string;
             std::size_t m_size = 0;
+            // Sorted, non-overlapping. Empty -> no escapes in input
+            std::vector<EscapeRange> m_escapes;
 
-            // perform 0xff replacement and calculate m_size
+            // find escape sequences and calculate m_size
             void preprocessString();
 
         public:
             class const_iterator;
             using iterator = const_iterator;
-            // note: must be u-suffixed or this will cause a "truncation of
-            // constant value" warning on MSVC
-            static constexpr char sentinel = static_cast<char>( 0xffu );
 
             explicit AnsiSkippingString( std::string const& text );
             explicit AnsiSkippingString( std::string&& text );
@@ -53,22 +58,28 @@ namespace Catch {
             const_iterator end() const;
 
             size_t size() const { return m_size; }
-
-            std::string substring( const_iterator begin,
-                                   const_iterator end ) const;
+            bool hasEscapes() const { return !m_escapes.empty(); }
+
+            std::string substring( const_iterator first,
+                                   const_iterator last ) const;
+            // Support for appending without extra allocations
+            void appendSubstringTo( std::string& out,
+                                    const_iterator first,
+                                    const_iterator last ) const;
         };
 
         class AnsiSkippingString::const_iterator {
             friend AnsiSkippingString;
             struct EndTag {};
 
-            const std::string* m_string;
+            const AnsiSkippingString* m_string;
             std::string::const_iterator m_it;
 
-            explicit const_iterator( const std::string& string, EndTag ):
-                m_string( &string ), m_it( string.end() ) {}
+            explicit const_iterator( const AnsiSkippingString& string, EndTag ):
+                m_string( &string ), m_it( string.m_string.end() ) {}
 
-            void tryParseAnsiEscapes();
+            void jumpForwardOverEscapes();
+            void jumpBackOverEscapes();
             void advance();
             void unadvance();
 
@@ -79,9 +90,9 @@ namespace Catch {
             using reference = value_type&;
             using iterator_category = std::bidirectional_iterator_tag;
 
-            explicit const_iterator( const std::string& string ):
-                m_string( &string ), m_it( string.begin() ) {
-                tryParseAnsiEscapes();
+            explicit const_iterator( const AnsiSkippingString& string ):
+                m_string( &string ), m_it( string.m_string.begin() ) {
+                if ( m_string->hasEscapes() ) { jumpForwardOverEscapes(); }
             }
 
             char operator*() const { return *m_it; }