cscope

Hi Hans,

Great work. We need to make sure that all your changes are a-ok with
some testing.

Please commit your work so we can get down to it.

Thanks,

Petr
> let me show you what a flex-optimized scanner.l might look like. It's the
> one I mentioned in yesterday's mail, already. Today, I remembered to bring
> its source in, so I can make diffs and show them to you, to give you an
> idea what we would be talking about, and a quick benchmark on another
> platform than my Linux box at home.
> 
> So here's a diff, heavily edited to isolate the scanner rewrite (The
> full 'diff' is attached, for reference):
> 
> Index: scanner.l
> ===================================================================
> RCS file: /cvsroot/cscope/cscope/src/scanner.l,v
> retrieving revision 1.4
> diff -u -w -B -r1.4 scanner.l
> --- scanner.l   2000/05/05 17:35:00     1.4
> +++ scanner.l   2000/09/27 10:54:59
> @@ -85,11 +86,13 @@
>  static int     templateparens;         /* function template outer parentheses count */
>  static int     typedefbraces = -1;     /* initial typedef brace count */
>  static int     token;                  /* token found */
> +static int     ident_start;            /* begin of preceding identifier */
> 
> That's a new status variable I had to introduce. See below.
> 
> [...]
> @@ -113,6 +128,16 @@
>  %start SDL
>  %a 4000
>  %o 7000
> +/* flex only options, to avoid incompatibilities with AT&T lex: */
> +%array
> +/* 'flex -B' (batch mode) doesn't work, for this scanner. Probably
> + * a usage bug, but let's stay conservative: */
> +%option always-interactive
> +
> +/* Exclusive initial states (not available in 'lex'!) */
> +%x WAS_ENDIF WAS_IDENTIFIER
> +
> +
>  %%
> 
> Flex-specific flags and options. 'lex' can just ignore %array and %option.
> %x could be emulated by %s, and prefixing all rules with a non-default
> initial state, to eliminate the difference between exclusive and inclusive
> initial states.
> 
> [...]
> -\#[ \t]*endif/.*\n[ \t\n]*#[ \t]*if    {
> +<WAS_ENDIF>.*\n[ \t\n]*#[ \t]*ifn?(def)?       {
> 
> This is one of the original 'variable trailing context rules'. To get
> rid of this performance killer (according to flex'es messages and docs),
> I delayed handling of '#endif' lines, and use the initial state
> <WAS_ENDIF> to flag this.
> 
> @@ -203,10 +228,11 @@
>                                 /* NOTREACHED */
>                         }
>                         pseudoelif = YES;
> +                       BEGIN(INITIAL);
>                         goto more;
>                         /* NOTREACHED */
>                 }
> This goes back to normal operation after <WAS_ENDIF> has been taken care
> of.
> 
> -\#[ \t]*ifn?(def)?     { /* #if, #ifdef or #ifndef */
> +<INITIAL>\#[ \t]*ifn?(def)?    { /* #if, #ifdef or #ifndef */
> 
> Don't use this rule if in <WAS_ENDIF> status.
> 
> -\#[ \t]*endif  {       /* #endif */
> +<WAS_ENDIF>.*\n                {       /* an #endif with no #if right after it */
> 
> And endif with no #if right after it now needs special treatment (an
> #endif with nothing between it and the EOF causes a little glitch because
> of this rule --> will be echoed to stdout)
> 
> @@ -249,6 +275,16 @@
>                                         braces = maxifbraces[iflevel];
>                                 }
>                         }
> +                       BEGIN(INITIAL);
> +                       yyless(0); /* rescan */
> +                       goto more;
> +                       /* NOTREACHED */
> +               }
> +
> +\#[ \t]*endif  {       /* #endif */
> +                       /* delay treatment of #endif depending on whether an
> +                        * #if comes right after it, or not */
> +                       BEGIN(WAS_ENDIF);
>                         goto more;
>                         /* NOTREACHED */
>                 }
> 
> And this is the rule that detect #endif, and does nothing but move the
> scanner into <WAS_ENDIF> mode. The original treatment of #endif is now in
> the <WAS_ENDIF>.|\n rule, above.
> 
> @@ -359,16 +395,39 @@
>  class[ \t]+{identifier}[ \t\na-zA-Z0-9_():]*\{ {       /* class definition */
>                         classdef = YES;
>                         tagdef =  'c';
> -                       REJECT;
> +                       /* RE!JECT; */
> +                       yyless(5); /* eat up 'class', and re-scan */
> +                       goto more;
>                         /* NOTREACHED */
>                 }
> 
> Uses yyless() to avoid use of REJECT. I'm not 100% certain that this does
> what it's supposed to, but it seemed to behave the same as the original
> scanner, if used on a C++ source.
> 
> -(enum|struct|union)/([ \t\n]+{identifier})?[ \t\n]*\{  { /* enum/struct/union definition */
> -                       tagdef = *(yytext + first);
> +
> +               /* Notice: three copies of essentially same rule may seem
> +                * strange, but they help flex to avoid slowing down the
> +                * scan (--> 'variable trailing context rules') */
> +enum/([ \t\n]+{identifier})?[ \t\n]*\{ { /* enum definition */
> +                       tagdef = 'e';
>                         goto ident;
>                         /* NOTREACHED */
>                 }
> +struct/([ \t\n]+{identifier})?[ \t\n]*\{       { /* struct definition */
> +                       tagdef = 's';
> +                       goto ident;
> +                       /* NOTREACHED */
> +               }
> +union/([ \t\n]+{identifier})?[ \t\n]*\{        { /* union definition */
> +                       tagdef = 'u';
> +                       goto ident;
> +                       /* NOTREACHED */
> +               }
> 
> This resolves another variable trailing context, by splitting up the rule
> into three. That was simple.
> 
> -{identifier}/[ \t]*\([ \t\na-zA-Z0-9_*&[\]=,.]*\)[ \t\n()]*[:a-zA-Z_#{]        {
> +{identifier}   {       /* identifier found: do nothing, yet. (!) */
> +                       BEGIN(WAS_IDENTIFIER);
> +                       ident_start = first;
> +                       goto more;
> +                       /* NOTREACHED */
> +               }
> +<WAS_IDENTIFIER>[ \t]*\([ \t\na-zA-Z0-9_*&[\]=,.]*\)[ \t\n()]*[:a-zA-Z_#{]     {
> +
> 
> Again, a slew of variable trailing context rules. Treated by first reading
> the identifier, and transforming the trailing contexts into
> (non-accepting) actual rules. 'ident_start' is needed as a new status
> variable to store where the {identifier} is, within the current yytext[].
> 
> -{identifier}/[ \t]*\(  { /* if a function call */
> +<WAS_IDENTIFIER>[ \t]*\(       { /* if a function call */
> 
> -{identifier}/[* \t\n]+[a-zA-Z0-9_]     {       /* typedef name use */
> +<WAS_IDENTIFIER>[* \t\n]+[a-zA-Z0-9_]  {       /* typedef name use */
> 
> -{identifier}   {
> +<WAS_IDENTIFIER>.|\n   {               /* the old {identifier} rule */
> 
> If the none of the trailing contexts gave a match, treat it like the
> original {identifier} rule did.
> 
> @@ -420,6 +480,14 @@
>                 ident:          token = IDENT;
>                         }
>                 fcn:
> +                       if (YYSTATE == WAS_IDENTIFIER) {
> +                               /* Position back to the actual identifier: */
> +                               yyleng = first;
> +                               first = ident_start;
> +                               BEGIN(INITIAL);
> +                               yyless(0);
> +                       }
> 
> This if(YYSTATE == WAS_IDENTIFIER) block is needed because other rules
> 'goto' right into the middle of the {identifier} rule, and not all of them
> belong to the set of variable context matchers that have <WAS_IDENTIFIER>
> as their initial state. Those that do need yyleng and first modified
> to simulate the original behaviour, where {identifier} would have been the
> match, not the trailing context, as we come here.
> 
> We could duplicate the handling code, instead, to avoid all that
> 'goto'ing.
> 
> @@ -622,6 +690,7 @@
>         template = NO;          /* function template */
>         templateparens = -1;    /* function template outer parentheses count */
>         typedefbraces = -1;     /* initial typedef braces count */
> +       ident_start = 0;
> 
>         BEGIN 0;
> 
> 
> Phew. That was that.
> 
> Now, let me show a quick'n'dirty benchmark: cscope current-cvs with
> scanner.l modified as described, and compiled in different 'flex' modes.
> Benchmark is 'cscope -ulR' in its own src dir (build directory is
> elsewhere, so no .o and no scanner.c or egrep.c are in this directry) plus
> my local gnuplot sources tree, to make it a bit bigger. Two consecutive
> runs each time, to allow for caching effects to settle.
> 
> 'flex -l', original scanner:
> 11.337u 0.430s 0:16.87 69.7%    0+2k 623+382io 0pf+0w
> 11.336u 0.422s 0:16.43 71.5%    0+2k 179+346io 0pf+0w
> 
> 'flex -l' mode, but with the modified scanner:
> #endif 10.831u 0.428s 0:15.53 72.4%     0+2k 644+367io 0pf+0w
> #endif 10.851u 0.278s 0:12.73 87.3%     0+2k 0+293io 0pf+0w
> 
> (That '#endif' in the output is from the scanning glitch I mentioned
> earlier.)
> 
> 'flex' without any flags (except those silently activated by '%array'
> and %option I mentioned), with the modified scanner.
> #endif 9.552u 0.403s 0:14.47 68.7%      0+2k 603+374io 0pf+0w
> #endif 9.471u 0.318s 0:12.06 81.0%      0+2k 57+342io 0pf+0w
> 
> 'flex -f' mode ('-F' and the other -C{F|f}... modes are similar):
> #endif 6.254u 0.416s 0:11.81 56.3%      0+2k 699+351io 0pf+0w
> #endif 6.282u 0.265s 0:07.50 87.2%      0+3k 0+281io 0pf+0w
> 
> I.e. roughly 45% reduction of execution time from first to last example.
> This would bring the factor of 5 to 6 reported by Darryl down to about 3,
> then. But currently, it comes at the cost of errors: the #endif glitch is
> easily visible above. The other one may be a heisenbug: -f mode silently
> forces -B mode, which caused errors on my Linux box at home, before. But
> on the Alpha, it seems to function properly.
> 
> Hans-Bernhard Broeker (broeker@...)
> Even if all the snow were burnt, ashes would remain.
> 
>   ------------------------------------------------------------------------
> 
>                         Name: scanner.dif
>    scanner.dif          Type: Plain Text (TEXT/PLAIN)
>                     Encoding: BASE64
>                  Description: Full diff

-- 
--------------------------------------------------------
Petr Sorfa                  Software Engineer
Santa Cruz Operation (SCO)
430 Mountain Ave.           http://www.sco.com
Murray Hill 07974
NJ, USA
--------------------------------------------------------
Disclaimer: All my comments are my own and nobody else's
----------------------------------------------------------

On Mon, 2 Oct 2000, Petr Sorfa wrote:

> Great work. We need to make sure that all your changes are a-ok with
> some testing.

I _know_ that not all of them are cosher.

> Please commit your work so we can get down to it.

Will do, but please expect it to cause problems. It definitely does,
currently. One of them is that it breaks compatibility with 'lex' (by use
of the exclusive initial states, if nothing else).

I put some more work into it, over this weekend (but again forgot to bring
the resulting scanner.l in, for showing it).

Here's some points to be considered:

*) The interactive vs. batch mode problems are gone, now, I think.
*) -Cf mode still doesn't work. If it backs up, it sometimes 
   will kill the contents of yytext conserved by previous yymore()
   calls.
*) I haven't checked recently, but I doubt %pointer mode can ever be
   made to work by anything but a rewrite from scratch.
*) part of the apparent speedup was due to a bug: the modified
   #include rule caused all Files included by <> not to be found,
   and thus they were left out of the cscope.out file.

*) We have at least one major problem with this scanner, at large:
   yymore() usage and yyleng modifications in the same action. 
   'flex' explicitly disallows that. You can do either one, in a rule,
   but not both. But scanner.l relies very heavily on yymore(), in order
   to memorize all previously scanned text in yytext, where putcrossref()
   will read it as the end-of-line is processed. Actually, just about
   all the rules either 'goto more;' or 'goto eol;', eventually.

*) Part of the problems stem from how we switch input methods between
   at least three different ones (normal mode, in-comment, and
   multicharconstant()). flex doesn't seem to deal with that very well,
   causing problems in the #include "file.h" handling, among others.
   It seems that it doesn't like us calling skipcomment_input()
   ourselvesy, rather than the full input(). That was where the
   "ytext"y problem in batch scanners I mentioned came from --- discarded
   readahead was re-delivered in incorrect order.

*) My latest version uses lex rules to treat comments and string/char
   constants, too, but that confuses some of the search patterns, and
   there seems to be no way to just discard comments from yytext, this
   way.  --> they end up in cscope.out, currently. It may be fundamentally
   impossible to parse C in a single pass, as scanner.l is trying to do.
   At the very least, we would need an input() method that unifies
   all three current input modes, properly, i.e. a 'pre-scanner' disguised
   as an input() routine.

> > And endif with no #if right after it now needs special treatment (an
> > #endif with nothing between it and the EOF causes a little glitch because
> > of this rule --> will be echoed to stdout)

This glitch is removed, now, I think, along with an incorrectness in
line number counting, introduced by the same change.


Hans-Bernhard Broeker (broeker@...)
Even if all the snow were burnt, ashes would remain.

Hi Hans,

Maybe don't check in anything until you are pretty sure that we can at
least match our current capabilities.

As an afterthought I'd really like this in post 15.0, there are just too
many 'ifs'

Petr
> > Great work. We need to make sure that all your changes are a-ok with
> > some testing.
> 
> I _know_ that not all of them are cosher.
> 
> > Please commit your work so we can get down to it.
> 
> Will do, but please expect it to cause problems. It definitely does,
> currently. One of them is that it breaks compatibility with 'lex' (by use
> of the exclusive initial states, if nothing else).
> 
> I put some more work into it, over this weekend (but again forgot to bring
> the resulting scanner.l in, for showing it).
> 
> Here's some points to be considered:
> 
> *) The interactive vs. batch mode problems are gone, now, I think.
> *) -Cf mode still doesn't work. If it backs up, it sometimes
>    will kill the contents of yytext conserved by previous yymore()
>    calls.
> *) I haven't checked recently, but I doubt %pointer mode can ever be
>    made to work by anything but a rewrite from scratch.
> *) part of the apparent speedup was due to a bug: the modified
>    #include rule caused all Files included by <> not to be found,
>    and thus they were left out of the cscope.out file.
> 
> *) We have at least one major problem with this scanner, at large:
>    yymore() usage and yyleng modifications in the same action.
>    'flex' explicitly disallows that. You can do either one, in a rule,
>    but not both. But scanner.l relies very heavily on yymore(), in order
>    to memorize all previously scanned text in yytext, where putcrossref()
>    will read it as the end-of-line is processed. Actually, just about
>    all the rules either 'goto more;' or 'goto eol;', eventually.
> 
> *) Part of the problems stem from how we switch input methods between
>    at least three different ones (normal mode, in-comment, and
>    multicharconstant()). flex doesn't seem to deal with that very well,
>    causing problems in the #include "file.h" handling, among others.
>    It seems that it doesn't like us calling skipcomment_input()
>    ourselvesy, rather than the full input(). That was where the
>    "ytext"y problem in batch scanners I mentioned came from --- discarded
>    readahead was re-delivered in incorrect order.
> 
> *) My latest version uses lex rules to treat comments and string/char
>    constants, too, but that confuses some of the search patterns, and
>    there seems to be no way to just discard comments from yytext, this
>    way.  --> they end up in cscope.out, currently. It may be fundamentally
>    impossible to parse C in a single pass, as scanner.l is trying to do.
>    At the very least, we would need an input() method that unifies
>    all three current input modes, properly, i.e. a 'pre-scanner' disguised
>    as an input() routine.
> 
> > > And endif with no #if right after it now needs special treatment (an
> > > #endif with nothing between it and the EOF causes a little glitch because
> > > of this rule --> will be echoed to stdout)
> 
> This glitch is removed, now, I think, along with an incorrectness in
> line number counting, introduced by the same change.
> 
> Hans-Bernhard Broeker (broeker@...)
> Even if all the snow were burnt, ashes would remain.

-- 
--------------------------------------------------------
Petr Sorfa                  Software Engineer
Santa Cruz Operation (SCO) 
430 Mountain Ave.           http://www.sco.com
Murray Hill 07974
NJ, USA
--------------------------------------------------------
Disclaimer: All my comments are my own and nobody else's
----------------------------------------------------------