taskSavannah Administration - Tasks: task #13451, Submission of Hybrid Self-Tuning...

 
 

task #13451: Submission of Hybrid Self-Tuning Boyer-Moore

Submitter:  Brenton Hoff <behoffski>
Submitted:  Mon 19 Jan 2015 03:55:19 AM UTC
   
 
Should Start On:  Mon 19 Jan 2015 12:00:00 AM UTC Should be Finished on:  Thu 29 Jan 2015 12:00:00 AM UTC
Category:  Project Approval Priority:  * 5 - Normal
Status:  Done Privacy:  Public
Assigned to:  agn Open/Closed:  Closed
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Sun 01 Feb 2015 09:36:09 PM UTC, comment #8: 

Hello Brenton,

Thank you for the update.
The project was approved, and you should receive an email with further instructions.

Regarding the copyright statement:
The copyright of the existing GNU Grep code is owned by FSF,
but any additions and modifications you make on top of the code are your own.
Thus,
The copyright statement should mention the FSF owning the changes until 2014/2015 (depending on when you've forked the code),
and in addition, changes by you should be copyrighted by you.

One example of such multiple copyrights is here:
https://git.kernel.org/cgit/linux/kernel/git/stable/linux-stable.git/tree/arch/parisc/kernel/drivers.c

In many GNU package you don't see multiple copyright statements, because those were explicitly re-assigned to the FSF.
But in the case of 'hstbm', it is not (yet) a GNU package, and copyright of code additions by you can not be re-assigned to the FSF.

If you choose to make 'hstbm' a GNU package, and it is accepted as a GNU package, then you'll have to option to re-assign copyright to FSF, see here: http://www.gnu.org/prep/maintain/html_node/Copyright-Papers.html .

If you choose to submit a patch of the hstbm feature to GNU Grep,
you will be asked (or already been asked) to sign a copyright assignment agreement, as explained here: https://www.gnu.org/licenses/why-assign.html .

Unless one of these two things happen, the hstbm code is copyrighted by you.

In any case, Happy hacking!
 - Assaf

Assaf Gordon <agn>
Site Administrator
Sun 25 Jan 2015 10:34:54 AM UTC, comment #7: 

Here's hstbm, Version 0.11.

The README has been expanded a little, to give some guidance on how to set up the Lua environment expected by the test rig.

I've adapted GNU Grep's git-version-gen script to provide a Git-aware version number for "--version".  The code falls back to a generic message if Git isn't available.

Finally, copyright notices have been fixed, as requested.  I've undertaken a wider review, and have added or refined notices to be more consistent.

My hope and intention is that some of the code from this program may end up in GNU Grep.  In the longer term, it's possible that this program may, in turn, become a framework that can be used to work on other parts of GNU Grep in isolation.  On that basis, I've decided to leave the copyright notices naming the FSF as the copyright owner, as before. 

I acknowledge again that nearly all of my code in hstbm (excluding the very raw and experimental test rig) is derived from, or influenced by, GNU Grep, starting from April 1998 onwards (but excluding the previous work, especially the 1997 publication). 


(file #32913)

Brenton Hoff <behoffski>
Thu 22 Jan 2015 07:03:49 PM UTC, comment #6: 

hi again brenton,

regarding the fsf assignment. i am well aware of the policy.  the point is that this new project is not part of gnu grep, but rather a new package based on gnu grep.  unless the ultimate goal is for your work to get folded back into grep, but i didn't get that impression.

i see that you did an assignment for grep years ago in your own name, and then in 2013 for grouse.  that's great, but that's about your contributions to grep itself, not new stuff you do outside of grep.  the fsf does not accept copyright assignments except on official gnu packages (like grep, unlike hstbm).

thus, i still believe that new material you write should be copyrighted in your name.

p.s. regardless of all this niggling, the project itself sounds great!


Karl Berry <karl>
Site Administrator
Thu 22 Jan 2015 06:50:32 PM UTC, comment #5: 

hi brenton - yes, please submit the updated tarball via the web interface (just attach it to another comment here).  the name is fine.

the scrollbar of licenses is a bad ui on our part.  totally understandable that you missed it.  anyway, we can fix that easily in the approval, so that's fine.

there's no practical way to list every possible combination; almost all projects use several different licenses.  the idea is to specify the principal one.  so no problem there either.

you'll be able to change the long description (and lots of other things) after approval.  i agree that "string search" would be useful to have in the title -- not everyone knows what "boyer-moore" means, amazingly enough :).

it sounds like all is fine.  please just upload the new tarball and we'll approve it.




Karl Berry <karl>
Site Administrator
Tue 20 Jan 2015 02:21:43 AM UTC, comment #4: 

Re: #1, License queries

[Oops, I originally sent this as an email reply... now using the Web interface.  The reply was sent about 5 hours ago, and is reproduced here verbatim... including the email-versus-web-interface query.  -- behoffski]


G'day,

Thanks for the quick reply.

Taking on an industrial-strength program such as GNU Grep, and in
an area such as the performance of string searching, has been a
daunting task, and much of my effort has been in trying to make my
code worthy of comparison in the nominated areas, without having
too many differences in other areas that could affect the relative
performance profiles.  This pressure, plus my relative
inexperience in managing Internet-hosted software, has led to the
slip-ups you've seen.

Paul Eggert and Jim Meyering, two of the principal maintainers of
GNU Grep, are aware of (some of) my efforts, and Paul, in
particular, was the person who suggested that I try hosting this
project on Savannah.  If this project requires some evaluation,
perhaps they would be appropriate reviewers.

So, to address your concerns, plus a couple of things that I've
thought of, since submitting:

1. The selection of "GPLv2 or later" was a mistake on my part.
   On my browser, I scanned the drop-down list of license options,
   and did not see GPLv3 listed... but upon re-reading the form
   just now, I see that the list has a scrollbar, and this item is
   indeed listed.  I understood that forking the GPLv3+ GNU Grep
   would result in a project that required the GPLv3+ license,
   and I believe that the files with explicit GPL marking, plus
   the license file, reflect this.

   For a project that has mixed GPLv3+ and MIT files, there isn't
   a drop-down menu item that explicitly names this combination;

2. I think the "GNU All permissive license" is sufficient for the
   small files;

3. The project name perhaps should include "String Search" in its
   long title; the current title is possibly a little cryptic;

4. In the "Other dependencies" project list, there are two
   omissions:

   4a. Gnulib is explicitly fetched, and packages imported, as
       part of the bootstrap process; and

   4b. The bootstrap script also explicitly uses Autotools,
       specifically "autoreconf" and "automake --add-missing".


I'm happy to resubmit the tarball with fixes; I would like your
guidance in the most appropriate way to do this -- for example:

  - Should I use a Web interface?
  - The revised tarball (with the additional small license
    annotations) could be called "hstbm-0.10-r1.tar.gz"; is
    this acceptable?

cheers,

behoffski

Brenton Hoff <behoffski>
Tue 20 Jan 2015 02:05:17 AM UTC, comment #3: 

Re: #2, Copyright assignment for GNU Grep:

No, in the case of GNU Grep, there is a requirement for all
(non-trivial) portions to be explicitly assigned to the FSF (with
trivial changes automatically given FSF ownership).  I have
executed such an assignment/disclaimer for myself, with explicit
authority from my employer (Grouse Software):


    Subject: [gnu.org #599112] Brenton James Hoff
    From: "Donald R Robertson III via RT" <copyright-clerk@fsf.org>
    Reply-To: -email is unavailable-
    Date: Fri, 20 Dec 2013 15:31:16 -0500
    To: -email is unavailable-

    RT-Ticket: gnu.org #599112

    Hello,

    Your assignment/disclaimer process with the FSF is currently
    complete; your fully executed PDF will be sent to you in a separate
    email immediately following this one.

    Please remember to let us know when your employment status changes, as
    this may affect your assignment status.

    Thank you for your contribution!

    All the best,

    Donald R. Robertson, III, J.D.
    Assignment Administrator
    Free Software Foundation
    51 Franklin Street, Fifth Floor
    Boston, MA 02110
    Phone +1-617-542-5942=20
    Fax +1-617-542-2652

    cc - maintainer

    [...]

cheers,

behoffski

Brenton Hoff <behoffski>
Mon 19 Jan 2015 11:29:28 PM UTC, comment #2: 

it's good for the material written for gnu grep to be copyright fsf.  but the material that you write, including modifications to grep files, should be copyright you, not fsf.

thanks,
karl

Karl Berry <karl>
Site Administrator
Mon 19 Jan 2015 07:07:12 PM UTC, comment #1: 

Hello Brenton,

Thank you for submitting a new project to host on GNU Savannah.

To clarify the license:
You've entered "GPLv2 or later" in the submission form,
but all the included source code files are GPLv3+ (or MIT-style license),
and the 'COPYING' file contains the GPLv3 license.
Is there a specific reason to list it as 'GPLv2 or later' ?

An additional minor issue:
Few small supporting files do not have a copyright statement or a license notice,
for these, please consider adding either the GPL, or the simpler 'GNU All permissive license' ( http://www.gnu.org/prep/maintain/html_node/License-Notices-for-Other-Files.html ).
The files are:
  hstbm/bootstrap
  hstbm/po/Makefile.am
  hstbm/tests/Makefile.am

Regards,
 - Assaf

Assaf Gordon <agn>
Site Administrator
Mon 19 Jan 2015 03:55:19 AM UTC, original submission:  

A new project has been registered at Savannah
This project account will remain inactive until a site admin approves or discards the registration.


Registration Administration


While this item will be useful to track the registration process, approving or discarding the registration must be done using the specific Group Administration page, accessible only to site administrators, effectively logged as site administrators (superuser):



Registration Details


  • Name: Hybrid Self-Tuning Boyer-Moore
  • System Name:  hstbm
  • Type: non-GNU software and documentation
  • License: GNU General Public License v2 or later (The vast majority of the code here is a direct fork, or closely related to, the code in GNU Grep, and so the FSF is named as the Copyright holder and the code is licensed under GPL3. 


The only exception is the regression test rig, which has no GNU Grep input and is written Lua:  Grouse Software is the Copyright holder, and the files have the MIT Licence attached, so that these files are free to participate in the Lua ecosystem. 
)




Description:

hstbm is an "exploratory fork" of GNU Grep, intended to sidestep the heavyweight capabilities and machinery of that program, so that a developer can focus exclusively on the performance of the Hybrid Tuned Boyer-Moore search in GNU Grep (in src/kwset.c) versus the performance of the Hybrid Self-Tuning Boyer-Moore algorithm pesented here. 

Portions of this algorithm were first published in 2000 as part of "Grouse Grep", and that program, especially having character class matching in string searches, in turn is partially based on the version published in the November 1997 edition of Dr. Dobb's Journal.

hstbm can outperform GNU Grep on some searches; in some cases (e.g. "tr[[=e=]]s") it is faster as GNU Grep conservatively reverts to the slow regex matcher. 

The Lua script "untangle", posted occasionally to the GNU Grep list, is a partner to this program:  "untangle" takes a bottom-up approach to refactoring GNU Grep, whereas "hstbm" is a top-down program to give direct access to the search algorithm.


Other Software Required:

Lua 5.1 or 5.2:   www.lua.org;  MIT License
luarocks:         luarocks.org: MIT License
strictness      (via Luarocks): MIT License
luaposix        (via Luarocks): MIT/X11 License



Tarball URL:

http://savannah.gnu.org/submissions_uploads/hstbm-0.10.tar.gz


Brenton Hoff <behoffski>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #32913:  hstbm-0.11.tar.gz added by behoffski (282KiB - application/gzip)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by karl (Posted a comment)
  • -email is unavailable- added by agn (Posted a comment)
  • -email is unavailable- added by behoffski (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 5 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2015-02-01 agn StatusWait reply Done
        Open/ClosedOpen Closed
    2015-01-25 behoffski Attached File- Added hstbm-0.11.tar.gz, #32913
    2015-01-19 agn StatusNone Wait reply
        Assigned toNone agn

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code