jammy (1) sim_lisp.1.gz

Provided by: similarity-tester_3.0.2-1_amd64 bug

NAME

       sim  -  find similarities in C, Java, Pascal, Modula-2, Lisp, Miranda, 8086 assembler code
       or in text files

SYNOPSIS

       sim_c [ -[adefFiMnOpPRsSTuv] -r N -t N -w N -o F ] file ... [ [ / | ] file ... ]
       sim_text ...
       sim_c++ ...
       sim_java ...
       sim_pasc ...
       sim_m2 ...
       sim_lisp ...
       sim_mira ...
       sim_8086 ...

DESCRIPTION

       Sim_c reads the C files file ...  and looks for segments of text  that  are  similar;  two
       segments  of program text are similar if they only differ in layout, comment, identifiers,
       and the contents of numbers, strings and characters.  If any runs of sufficient length are
       found,  they  are reported on standard output; the number of significant tokens in the run
       is given between square brackets.

       Sim_c++ does the same for  C++,  sim_java  for  Java,  sim_pasc  for  Pascal,  sim_m2  for
       Modula-2,  sim_mira  for Miranda, sim_lisp for Lisp, and sim_8086 for 8086 assembler code.
       Sim_text works on arbitrary text and it is occasionally useful on shell scripts.

       The program can be used for  finding  copied  pieces  of  code  in  purportedly  unrelated
       programs  (with  -s or -S), or for finding accidentally duplicated code in larger projects
       (with -f or -F).

       If a separator / or | is present in the list of input files, the files are divided into  a
       group  of  "new" files (before the / or |) and a group of "old" files; if there is no / or
       |, all files are "new".  Old files are never  compared  to  other  files.   See  also  the
       description of the -s and -S options below.

       Since  the similarity tester needs file names to pinpoint the similarities, it cannot read
       from standard input.

       The similarity tester takes ASCII or UTF-8 text as input, and produces a  sorted  list  of
       runs  in  text form (default or with the -d or -n options) or in percentage form (with the
       -p option).  Input in other formats, e.g.  .pdf or .doc needs to be converted to ASCII  or
       UTF-8   by  preprocessing.   Aggregated  similarity  results  can  be  obtained  by  doing
       postprocessing on one of the forms of output.

       There are the following options:

       -a     All new files are compared to all files.  See the section `Calculating Percentages'
              below.

       -d     The  output  is  in  a  diff(1)-like format instead of the default 2-column format.
              Recommended for text in languages with non-Latin alphabets.

       -e     Each file is compared to each file in isolation. This will  find  all  similarities
              between  all  texts  involved,  regardless  of repetitive text, but may be slow for
              large numbers of files.  See also `Calculating Percentages' below.

       -f     Runs are restricted to segments with balancing parentheses,  to  isolate  potential
              routine bodies (not in sim_text).

       -F     The names of routines in calls are required to match exactly (not in sim_text).

       -i     The  names  of  the  files to be compared are read from standard input, including a
              possible separator / or |; the file names must be  one  to  a  line.   This  option
              allows  a  very  large  number of file names to be specified; it differs from the @
              facility provided by some compilers in that it handles file names  only,  and  does
              not recognize option arguments.

       -M     Memory usage information is displayed on standard error output.

       -n     Similarities  found  are  summarized  by  file name, position and size, rather than
              displayed in full.

       -o F   The output is written to the file named F.

       -O     The option settings used are shown at the beginning of the output.

       -p     The output is given in similarity percentages; see `Calculating Percentages' below;
              implies -s.

       -P     When reporting percentages, only the main contributor for each file is shown.

       -r N   The  minimum  run  length  is  set  to N units; the default is 24 tokens, except in
              sim_text, where it is 8 words.

       -R     Directories in the input list are entered recursively, and all files  they  contain
              are involved in the comparison.

       -s     The contents of a file are not compared to itself (-s for "not self").

       -S     The  contents  of  the  new  files are compared to the old files only - not between
              themselves.

       -t N   In combination with the -p option, sets the threshold  (in  percents)  below  which
              similarities  will  not be reported; the default is 1, except in sim_text, where it
              is 20.

       -T     Suppresses the printing of information about the input files.

       -u     The output is not buffered and not sorted (only when reporting percentages).

       -v     Prints the version number and compilation date on standard output, then stops.

       -w N   The page width used is set to N columns; the default is 80.

       --     (A secret option, which prints the input as the similarity  checker  sees  it,  and
              then stops.)

       The -p option results in lines of the form
               F consists for x % of G material
       meaning  that  x  %  of  F's  text can also be found in G.  Note that this relation is not
       symmetric; it is quite possible for one file to consist for 100 %  of  text  from  another
       file,  while  the  other  file  consists  for only 1 % of text of the first file, if their
       lengths differ enough.  The -P (capital P) option shows the main contributor for each file
       only.   This  simplifies  the  identification  of  a set of files A[1] ... A[n], where the
       concatenation of these files is also present.  A threshold can be set using the -t option.
       Note that the granularity of the recognized text is still governed by the -r option or its
       default.

       The -r option controls the number of "units" that constitute a run.  For the programs that
       compare  programming  language  code, a unit is a lexical token in the pertinent language;
       comment and standard preamble material (file inclusion, etc.) is ignored and  all  strings
       are considered equal.  For sim_text a unit is a "word" which is defined as any sequence of
       one or more letters, digits, or characters over  127  (177  octal),  to  accommodate  full
       Unicode (UTF-8).

       The programs can handle Unicode (UTF-16) file names under Windows.

       Sim_text accepts  s p a c e d   t e x t  as normal text.

       Once sim has read, stored and preprocessed the input, it will no longer run out of memory.
       If memory is short it will change automatically  to  unbuffered,  unsorted  output  (while
       issuing a warning message).

HOW SIMILARITY IS RECOGNIZED

       Since  computers  cannot  test  for  similarity, only for equality, all units in the input
       files are replaced by 16-bit tokens, such that all units that are regarded as similar  are
       reduced to the same token.  For example in sim_c all identifiers are replaced by the token
       IDF and all strings are replaced by the token STR. The secret option -- can be used to see
       the resulting token sequence.

       In  sim_text  each  word  is  reduced  to a 16-bit token using a hash function. There is a
       chance of 1 : 65536 that two different  words  get  the  same  token  value,  but  because
       recognized  runs  of  tokens  are  usually several tokens long, the chances for accidental
       similarities are very low.

       The sequence of tokens obtained this way is then processed as follows.

       The default operation cycle of sim starts at the beginning of the token  sequence  of  the
       first  input  file  or  at a position $X$ in file $F$ at which the previous cycle has left
       off.  Sim then finds the longest segment $S$ such that 1) $S$  is  equal  to  the  segment
       starting  at  $X$; 2) $S$ is situated somewhere between position $X$ in $F$ and the end of
       all files; 3) $S$ does not overlap with the segment starting at $X$.  If the segment is at
       least  of  minimum  run  size,  it  is recorded, and the cycle starts again just after the
       segment at $X$; otherwise it starts again at $X+1$ .

       So if the token sequence at $X$ reads abcabcadefabdabcz, the cycle finds $S$ to be the abc
       just  before  the end; abca at $X+3$ would be longer but overlaps with the abca at $X+0$ .
       The cycle then starts at $X+3$, and will find another match with the  abc  near  the  end.
       Finally  the  ab  after  the  f  will  be  matched with the ab just before the cz.  So the
       following matches are found:

       $ X[0:2] = X[13:15] =$ abc
       $ X[3:5] = X[13:15] =$ abc
       $ X[9:10] = X[13:14] =$ ab

       This way best matches for the text in a file are found in material to  the  right  of  it,
       until  the  end  of all files.  The results are asymmetric: given files F1, F2, F3, F4, no
       matches for F3 are reported from  F1  or  F2,  for  example.   As  explained  below  under
       "Limitations", this avoids duplicate reports of similarity and helps to keep sim fast.

WHAT IS COMPARED TO WHAT

       The area that is searched by sim's cycle is called the range.  The default range, which as
       we have seen above runs from the file under observation  to  the  end  of  all  files,  is
       excellent  for  finding  similarities  in  program files, and, when doing percentages, for
       getting an impression of which files are  related  to  which  files,  but  sometimes  more
       control is needed.  The following modifications to the range are available:

       The  -a option includes all text in the range by not stopping the search at the end of the
       files but rather looping back to the beginning of the files and continuing  to  the  point
       where  the search started.  Now matches are also found in files before the present one and
       the results are symmetric: given files F1, F2,  F3,  F4,  matches  for  F3  will  also  be
       reported  from  F1 or F2, if present.  But matches may be reported twice, once for file Fa
       versus file Fb, and once for file Fb versus file Fa.  The -a option allows a more accurate
       determination of similarity percentages.

       The  -a  option is the only way to obtain symmetrical results, with information about both
       F1 vs. F2 and F2 vs. F1.

       The -S option removes the new files from the range, so files are only compared to the  old
       files.

       The  -s  option  removes the file itself from the range, so a file will not be compared to
       itself. This is the default when reporting percentages.

       In normal operation the whole range is searched as one unit. The -e option divides up  the
       range into the separate files, and causes sim to compare a file to each of the other files
       separately.  This produces the most detailed information when reporting text similarities,
       and  the  best  possible  results  when reporting similarity percentages, but can be quite
       slow.

   A Tabular Representation
       Input files are divided into two groups, new and old.  In the absence of  control  options
       sim compares the files thus (for 4 new files and 6 old ones):
                                 n e w    /     o l d       <- second file
                               1  2  3  4 / 5  6  7  8  9 10
                             |------------/------------
                        n  1 | c  c  c  c / c  c  c  c  c  c
                        e  2 |    c  c  c / c  c  c  c  c  c
                        w  3 |       c  c / c  c  c  c  c  c
                           4 |          c / c  c  c  c  c  c
              first        / / /  /  /  / / /  /  /  /  /  /
              file  ->     5 |            /
                        o  6 |            /
                        l  7 |            /
                        d  8 |            /
                           9 |            /
                          10 |            /
       where  a  c  indicates  that  the  first  file  is  compared to the second file, and the /
       represents the demarcation between new and old files.  The comparison range of  the  first
       files is clearly visible.

       Using the -a option extends this to
                                 n e w    /     o l d       <- second file
                               1  2  3  4 / 5  6  7  8  9 10
                             |------------/------------
                        n  1 | c  c  c  c / c  c  c  c  c  c
                        e  2 | c  c  c  c / c  c  c  c  c  c
                        w  3 | c  c  c  c / c  c  c  c  c  c
                           4 | c  c  c  c / c  c  c  c  c  c
              first        / / /  /  /  / / /  /  /  /  /  /
              file  ->     5 |            /
                        o  6 |            /
                        l  7 |            /
                        d  8 |            /
                           9 |            /
                          10 |            /

       Using the -S option instead reduces this to
                                 n e w    /     o l d       <- second file
                               1  2  3  4 / 5  6  7  8  9 10
                             |------------/------------
                        n  1 |            / c  c  c  c  c  c
                        e  2 |            / c  c  c  c  c  c
                        w  3 |            / c  c  c  c  c  c
                           4 |            / c  c  c  c  c  c
              first        / / /  /  /  / / /  /  /  /  /  /
              file  ->     5 |            /
                        o  6 |            /
                        l  7 |            /
                        d  8 |            /
                           9 |            /
                          10 |            /

       Finally, using the -s option changes the default ranges to
                                 n e w    /     o l d       <- second file
                               1  2  3  4 / 5  6  7  8  9 10
                             |------------/------------
                        n  1 |    c  c  c / c  c  c  c  c  c
                        e  2 |       c  c / c  c  c  c  c  c
                        w  3 |          c / c  c  c  c  c  c
                           4 |            / c  c  c  c  c  c
              first        / / /  /  /  / / /  /  /  /  /  /
              file  ->     5 |            /
                        o  6 |            /
                        l  7 |            /
                        d  8 |            /
                           9 |            /
                          10 |            /
       and the -a-extended ranges to
                                 n e w    /     o l d       <- second file
                               1  2  3  4 / 5  6  7  8  9 10
                             |------------/------------
                        n  1 |    c  c  c / c  c  c  c  c  c
                        e  2 | c     c  c / c  c  c  c  c  c
                        w  3 | c  c     c / c  c  c  c  c  c
                           4 | c  c  c    / c  c  c  c  c  c
              first        / / /  /  /  / / /  /  /  /  /  /
              file  ->     5 |            /
                        o  6 |            /
                        l  7 |            /
                        d  8 |            /
                           9 |            /
                          10 |            /

LIMITATIONS

       Repetitive  input  is  the  bane  of  similarity checking.  If we have a file containing 4
       copies of identical text,
           A1 A2 A3 A4
       where the numbers serve only to  distinguish  the  identical  copies,  there  are  7  non-
       overlapping  identities:  A1=A2,  A1=A3,  A1=A4,  A2=A3,  A2=A4, A3=A4, and A1A2=A3A4.  Of
       these, only 3 are meaningful: A1=A2, A2=A3, and A3=A4.  And for  a  table  with  20  lines
       identical  to  each  other,  not  unusual in a program text, there are 715 non-overlapping
       identities, of which at most 19 are meaningful.  Reporting all  715  of  them  is  clearly
       unacceptable.

       This is remedied by sim's search cycle: for each position in the text, the largest segment
       is found of which a non-overlapping copy occurs in the text following  it.   That  segment
       and  its  copy  are  then  reported  and  scanning  resumes at the position just after the
       segment.  For the above example this results in the two identities  A1A2=A3A4  and  A3=A4,
       which  is  quite  satisfactory,  and for N identical segments roughly 2 log N messages are
       given.

       This also works out well when the four identical segments are in different files:
           File1: A1
           File2: A2
           File3: A3
           File4: A4
       Now combined segments like A1A2 do not occur, and the  algorithm  finds  the  runs  A1=A2,
       A2=A3, and A3=A4, for a total of N-1 runs, all informative.

   Calculating Percentages
       The  above  approach  is unsuitable for obtaining the exact percentage of a file's content
       that can be found in another file, although indicative results can be obtained.  Obtaining
       exact  percentages  requires  comparing  each file pair in isolation; this is what the -ae
       options do.  Under the -ae options a segment File3:A3, recognized in File4, will again  be
       recognized in File1 and File2.  In the example above it produces the runs
           File1:A1=File2:A2
           File1:A1=File3:A3
           File1:A1=File4:A4
           File2:A2=File3:A3
           File2:A2=File4:A4
           File2:A2=File1:A1
           File3:A3=File4:A4
           File3:A3=File1:A1
           File3:A3=File2:A2
           File4:A4=File1:A1
           File4:A4=File2:A2
           File4:A4=File3:A3
       for a total of N(N-1) runs.

       When the -e option is used alone.  sim will find the following runs:
           File1:A1=File2:A2
           File1:A1=File3:A3
           File1:A1=File4:A4
           File2:A2=File3:A3
           File2:A2=File4:A4
           File3:A3=File4:A4
       for  a  total  of  ½N(N-1)  runs, thus missing half the percentage contributions; in fact,
       File4 is found to have 0% in common with the other files.

       If, however, the -a option is used alone.  sim finds the following runs:
           File1:A1=File2:A2
           File2:A2=File3:A3
           File3:A3=File4:A4
           File4:A4=File1:A1
       for a total of N runs. This setting misses many of the percentage contributions, but finds
       something for every file.

TIME AND SPACE REQUIREMENTS

       Care  has  been  taken  to  keep  the time requirements of all internal processes (almost)
       linear in the lengths of the input files, by using various tables.

       The time requirements are quadratic in the number of files.  This means that, for example,
       one 64 MB file processes much faster than 8000 8 kB files.

       The  program  requires  6 bytes of memory for each token in the input; 2 bytes per newline
       (not when doing percentages); and 80 bytes for each run found.

EXAMPLES

       The call
               sim_c *.c
       highlights duplicate C code in the directory.  (It is useful  to  remove  generated  files
       first.)  A call of
               sim_c -f -F *.c
       can pinpoint the duplicate code further.

       A call
               sim_text -peu -S new/* "|" old/*
       compares  each  file  in new/* to each file in old/*, and if any pair has more that 20% in
       common, that fact is reported.  Usually a similarity of 30% or more is significant;  lower
       than 20% is probably coincidence; and in between is doubtful.

       The  u  in  -peu  causes  the output to be unbuffered (and unsorted), so if the program is
       stopped for running out of time, any results already found are not lost.

       For large data sets, using -pu rather than -peu may do the job much more quickly, but less
       accurately.

       The  |  can  be  used as a separator instead of / on systems where the / as a command-line
       parameter gets mangled by the command interpreter.

       These calls are good for plagiarism detection.

BUGS

       Unbuffered, unsorted output is not available for text output, only for percentage output.

AUTHOR

       Dick Grune, Vrije Universiteit, Amsterdam; dick@dickgrune.com.

                                            2017/11/23                                     SIM(1)