CVS commit: othersrc/external/bsd/arfe

["David Young" <dyoung%netbsd.org@localhost>]

Module Name:    othersrc
Committed By:   dyoung
Date:           Wed Dec  2 23:39:51 UTC 2015

Modified Files:
        othersrc/external/bsd/arfe/dt: Makefile README core.c core.h dec.c
            dec.h dt.c hex.c hex.h ipv4.c ipv4.h macaddr.c macaddr.h
            portability.h testit
        othersrc/external/bsd/arfe/dt/rr: daily-output-2-daily-output-5
            daily-output-5-daily-output-2 daily-output-5-daily-output-6
            daily-output-6-daily-output-5 daily-output-6-daily-output-7
            daily-output-7-daily-output-6 if-re0-if-wm0 if-wm0-if-re0
            ifconfig.0-ifconfig.1 ifconfig.0-logger-ifconfig.0
            ifconfig.1-ifconfig.0 logger-ifconfig.0-ifconfig.0
            netstat-s.0-netstat-s.1 netstat-s.1-netstat-s.0
            quack123quack-quack456quack quack456quack-quack123quack
            quackabequack-quackdariaquack quackdariaquack-quackabequack
            wm0-a-wm0-b wm0-b-wm0-a
        othersrc/external/bsd/arfe/it: Makefile README it.c
        othersrc/external/bsd/arfe/tt: Makefile README tt.c
        othersrc/external/bsd/arfe/tt/tests/1: match transform
Removed Files:
        othersrc/external/bsd/arfe/dt/t: abecedarian abracadabra quack123quack
            quack456quack quackabequack quackdariaquack

Log Message:
Executive summary: ARFE now understands C-like symbols.  I'm using a
different algorithm to figure out where to subdivide the longest common
subsequence search.  I'm actually computing an edit distance instead of
the longest common sequence, but the algorithms are duals so there's not
much practical difference.  I've discarded some tests, and added at least
one new one.

Qualify %d for ptrdiff_t, %td.  Quiets compilation on 64-bit Darwin.

Change the type of the dynamic program cells from size_t to cell_t.  For
now, a cell_t is just a struct containing a size_t score.

Add algq(), a routine for finding k such that

        lcs(A[1:m/2], B[1:k]) | lcs(A[m/2+1:m], B[k+1:n]) = lcs(A, B).

algq() is based on the function Half(i, j) defined in Jeff Erickson's
(jeffe%cs.illinois.edu@localhost) lecture notes on advanced dynamic programming.
See http://jeffe.cs.illinois.edu/teaching/algorithms/.

Add to the Makefile (commented out) lines for tracking code coverage.
Use gcov <source file> to see the coverage.

Make the cleandir target remove gcov(1)-related files.

Delete a bunch of dead code and the now unnecessary argument to algc(),
expected_lcs.

We don't need backwards subslices any more, so get rid of that.  When
I got rid of the slice_t member `backward' and all of its uses, GCC
inlined clocc_ends_at() with a really bad effect on performance (>10s
on elmendorf for the t/netstat-s.[01] test, instead of <8s).  I marked
clocc_ends_at() __noinline for a net performance gain.  The gcc version
is (NetBSD nb2 20110806) 4.5.3, btw.

Disable the dbg_assert()s for more reliable performance comparisons.

Rename algq's splitn argument to splitnp since that's my convention
for arguments of that kind.

In algq(), don't get(A, i) m x n times, just get(A, i) m times.

Lightly constify.

Provide __noinline on non-NetBSD systems.

Sprinkle the $ARFE$ keyword.

Rename algc -> findlcs, algq -> findsplitn.

Make Subversion fill $ARFE$ in macaddr.h.

Extract the tags target from {dt,it,tt}/Makefile, put it
in ./Makefile.inc.

We only ever call findsplitn(..., true), so get rid of the do_clocc
argument.

Add an experimental routine, count_records(), that tries to count the
records in its second slice_t argument, using the first slice_t argument
as record template.

Change the class-occurrence (clocc_t) score, clocc_score(), to one plus
the minimum length of the class occurrences, from one plus the product
of the class occurrences' lengths.  This speeds things up a bit.

Simplify findsplitn() by pulling common statements out from if-else
branches, et cetera.

In clocc_starts_in_slice_at(), pass the wlenp argument to
clocc_starts_at().  Nothing passed a non-NULL wlenp to
clocc_starts_in_slice_at(), so this doesn't make any functional
difference.

Compute the edit distance instead of the longest common subsequence.
The one algorithm is a dual of the other.  I may find it easier to
add to the edit distance algorithm improvements like affine gap
penalties, hence the change.

Snapshot of work in progress.  These changes make things quite a bit
slower!  Add affine gap penalties.

Bring count_records() in line with findsplitn(), adding affine gap
penalties.  Update the instrumentation.  Count up the number of gaps
accumulated.

XXX This change makes 'dt netstat-s.0 netstat-s.1' more than twice as
XXX slow as it used to be, owing largely (I think) to the increase in
XXX size of a cell_t, where three ssize_t's track the number of gaps.

Exit with a message and error return code if we run out of slots for
class occurrences.  The class-occurrence array is still statically
allocated---yech.  I'm going to fix it one of these days, I promise.

Stop detecting occurrences of class "string" (KIND_STRING), which
consisted of the names 'abe', 'ada', and 'daria'.  Remove the tests
related to that.

Start detecting occurrences of class "symbol" (KIND_SYMBOL), which
resemble C symbol names: they start with a letter of the alphabet or
underscore.  Following characters are letters, numbers, or underscore.
Update tests to match: the netstat and ifconfig tests produce much more
sensible results, now.  Delete the 'quack<number>quack' tests, since
the symbol detector matches the entire string, now, and the tests don't
stand for any practical use-case.

Add test #5 to tt, which demonstrates how one can use a symbol in the
match template to match a symbol in the input for reproduction in the
transform template.


To generate a diff of this commit:
cvs rdiff -u -r1.6 -r1.7 othersrc/external/bsd/arfe/dt/Makefile \
    othersrc/external/bsd/arfe/dt/hex.c othersrc/external/bsd/arfe/dt/hex.h \
    othersrc/external/bsd/arfe/dt/ipv4.c othersrc/external/bsd/arfe/dt/ipv4.h
cvs rdiff -u -r1.10 -r1.11 othersrc/external/bsd/arfe/dt/README
cvs rdiff -u -r1.3 -r1.4 othersrc/external/bsd/arfe/dt/core.c \
    othersrc/external/bsd/arfe/dt/core.h othersrc/external/bsd/arfe/dt/testit
cvs rdiff -u -r1.1 -r1.2 othersrc/external/bsd/arfe/dt/dec.c \
    othersrc/external/bsd/arfe/dt/dec.h \
    othersrc/external/bsd/arfe/dt/macaddr.h
cvs rdiff -u -r1.14 -r1.15 othersrc/external/bsd/arfe/dt/dt.c
cvs rdiff -u -r1.4 -r1.5 othersrc/external/bsd/arfe/dt/macaddr.c
cvs rdiff -u -r1.2 -r1.3 othersrc/external/bsd/arfe/dt/portability.h
cvs rdiff -u -r1.2 -r1.3 \
    othersrc/external/bsd/arfe/dt/rr/daily-output-2-daily-output-5 \
    othersrc/external/bsd/arfe/dt/rr/daily-output-5-daily-output-2 \
    othersrc/external/bsd/arfe/dt/rr/daily-output-5-daily-output-6 \
    othersrc/external/bsd/arfe/dt/rr/daily-output-6-daily-output-5 \
    othersrc/external/bsd/arfe/dt/rr/daily-output-6-daily-output-7 \
    othersrc/external/bsd/arfe/dt/rr/daily-output-7-daily-output-6
cvs rdiff -u -r1.4 -r1.5 othersrc/external/bsd/arfe/dt/rr/if-re0-if-wm0 \
    othersrc/external/bsd/arfe/dt/rr/if-wm0-if-re0
cvs rdiff -u -r1.5 -r1.6 \
    othersrc/external/bsd/arfe/dt/rr/ifconfig.0-ifconfig.1 \
    othersrc/external/bsd/arfe/dt/rr/ifconfig.0-logger-ifconfig.0 \
    othersrc/external/bsd/arfe/dt/rr/ifconfig.1-ifconfig.0 \
    othersrc/external/bsd/arfe/dt/rr/logger-ifconfig.0-ifconfig.0 \
    othersrc/external/bsd/arfe/dt/rr/wm0-a-wm0-b \
    othersrc/external/bsd/arfe/dt/rr/wm0-b-wm0-a
cvs rdiff -u -r1.1 -r1.2 \
    othersrc/external/bsd/arfe/dt/rr/netstat-s.0-netstat-s.1 \
    othersrc/external/bsd/arfe/dt/rr/netstat-s.1-netstat-s.0 \
    othersrc/external/bsd/arfe/dt/rr/quack123quack-quack456quack \
    othersrc/external/bsd/arfe/dt/rr/quack456quack-quack123quack \
    othersrc/external/bsd/arfe/dt/rr/quackabequack-quackdariaquack \
    othersrc/external/bsd/arfe/dt/rr/quackdariaquack-quackabequack
cvs rdiff -u -r1.1 -r0 othersrc/external/bsd/arfe/dt/t/abecedarian \
    othersrc/external/bsd/arfe/dt/t/abracadabra \
    othersrc/external/bsd/arfe/dt/t/quack123quack \
    othersrc/external/bsd/arfe/dt/t/quack456quack \
    othersrc/external/bsd/arfe/dt/t/quackabequack \
    othersrc/external/bsd/arfe/dt/t/quackdariaquack
cvs rdiff -u -r1.5 -r1.6 othersrc/external/bsd/arfe/it/Makefile
cvs rdiff -u -r1.8 -r1.9 othersrc/external/bsd/arfe/it/README
cvs rdiff -u -r1.1 -r1.2 othersrc/external/bsd/arfe/it/it.c
cvs rdiff -u -r1.3 -r1.4 othersrc/external/bsd/arfe/tt/Makefile
cvs rdiff -u -r1.5 -r1.6 othersrc/external/bsd/arfe/tt/README
cvs rdiff -u -r1.2 -r1.3 othersrc/external/bsd/arfe/tt/tt.c
cvs rdiff -u -r1.1 -r1.2 othersrc/external/bsd/arfe/tt/tests/1/match \
    othersrc/external/bsd/arfe/tt/tests/1/transform

Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.