diff mbox

Add/modify regex comments

Message ID CAPrifDnfx4dUz8cX7yFTv9yXpJPdFfybuV=HNwWqaDC4y0uc7g@mail.gmail.com
State New
Headers show

Commit Message

Tim Shen March 14, 2014, 6:55 p.m. UTC 
Fix some inaccurate comments, especially the asymptotic complexity
mark: o() => \Omega().

Thanks!

Comments

Jonathan Wakely March 14, 2014, 7:04 p.m. UTC | #1 
On 14/03/14 14:55 -0400, Tim Shen wrote:
>Fix some inaccurate comments, especially the asymptotic complexity
>mark: o() => \Omega().

If all the tests pass this is OK for trunk, thanks.

N.B. the patch is fine but I don't think we usually say

   @brief Class FooBar. Does some Foo and some Bar.

just

   @brief Does some Foo and some Bar.

Because Doxygen always outputs the class details anyway.
Tim Shen March 15, 2014, 6:19 p.m. UTC | #2 
On Fri, Mar 14, 2014 at 3:04 PM, Jonathan Wakely <jwakely@redhat.com> wrote:
> If all the tests pass this is OK for trunk, thanks.

Booted, tested, and committed.

> N.B. the patch is fine but I don't think we usually say
>
>   @brief Class FooBar. Does some Foo and some Bar.
>
> just
>
>   @brief Does some Foo and some Bar.
>
> Because Doxygen always outputs the class details anyway.

Fixed.
diff mbox

Patch

diff --git a/libstdc++-v3/include/bits/regex_compiler.h b/libstdc++-v3/include/bits/regex_compiler.h
index fe2e5f1..6d25b39 100644
--- a/libstdc++-v3/include/bits/regex_compiler.h
+++ b/libstdc++-v3/include/bits/regex_compiler.h
@@ -42,7 +42,11 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
   template<typename, bool, bool>
     struct _BracketMatcher;
 
-  /// Builds an NFA from an input iterator interval.
+  /**
+   * @brief class _Compiler. Builds an NFA from an input iterator interval.
+   *
+   * The %_TraitsT type should fulfill requirements [28.3].
+   */
   template<typename _TraitsT>
     class _Compiler
     {
diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h
index 0885716..4e0e0fb 100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -41,6 +41,13 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
    * @{
    */
 
+  /**
+   * @brief class _Executor. Takes a regex and an input string in and
+   * do the matching.
+   *
+   * The %_Executor class has two modes: DFS mode and BFS mode, controlled
+   * by the template parameter %__dfs_mode.
+   */
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
 	   bool __dfs_mode>
     class _Executor
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
index e1cfcb0..68a5e04 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -72,7 +72,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // TODO: This approach is exponentially slow for certain input.
   //       Try to compile the NFA to a DFA.
   //
-  // Time complexity: o(match_length), O(2^(_M_nfa.size()))
+  // Time complexity: \Omega(match_length), O(2^(_M_nfa.size()))
   // Space complexity: \theta(match_results.size() + match_length)
   //
   // ------------------------------------------------------------
@@ -82,8 +82,9 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // Russ Cox's article (http://swtch.com/~rsc/regexp/regexp1.html)
   // explained this algorithm clearly.
   //
-  // It first computes epsilon closure for every state that's still matching,
-  // using the same DFS algorithm, but doesn't reenter states (set true in
+  // It first computes epsilon closure (states that can be achieved without
+  // consuming characters) for every state that's still matching,
+  // using the same DFS algorithm, but doesn't re-enter states (find a true in
   // _M_visited), nor follows _S_opcode_match.
   //
   // Then apply DFS using every _S_opcode_match (in _M_match_queue) as the start
@@ -92,9 +93,9 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // It significantly reduces potential duplicate states, so has a better
   // upper bound; but it requires more overhead.
   //
-  // Time complexity: o(match_length * match_results.size())
+  // Time complexity: \Omega(match_length * match_results.size())
   //                  O(match_length * _M_nfa.size() * match_results.size())
-  // Space complexity: o(_M_nfa.size() + match_results.size())
+  // Space complexity: \Omega(_M_nfa.size() + match_results.size())
   //                   O(_M_nfa.size() * match_results.size())
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
     bool __dfs_mode>
diff --git a/libstdc++-v3/include/bits/regex_scanner.h b/libstdc++-v3/include/bits/regex_scanner.h
index 6dc2b4e..1becb61 100644
--- a/libstdc++-v3/include/bits/regex_scanner.h
+++ b/libstdc++-v3/include/bits/regex_scanner.h
@@ -188,7 +188,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
   };
 
   /**
-   * @brief struct _Scanner. Scans an input range for regex tokens.
+   * @brief class _Scanner. Scans an input range for regex tokens.
    *
    * The %_Scanner class interprets the regular expression pattern in
    * the input range passed to its constructor as a sequence of parse