{"thread":{"id":"26610","subject":"[PATCH/RFC] gitweb: Restructure projects list generation","startedAt":"2011-02-26T22:06:50Z","lastAt":"2011-03-02T16:11:19Z","messageCount":5,"participants":["Jakub Narebski","Jonathan Nieder"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"162326","messageId":"20110226215230.5333.92839.stgit@localhost.localdomain","threadId":"26610","inReplyTo":null,"subject":"[PATCH/RFC] gitweb: Restructure projects list generation","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2011-02-26T22:06:50Z","receivedAt":"2011-02-26T22:06:50Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Extract filtering out forks (which is done if 'forks' feature is\nenabled) into filter_forks_from_projects_list subroutine, and\nsearching projects (via projects search form, or via content tags)\ninto search_projects_list subroutine.\n\nBoth are now run _before_ displaying projects, and not while printing;\nthis allow to know upfront if there were any found projects.  Gitweb\nnow can and do print 'No such projects found' if user searches for\nphrase which does not correspond to any project (any repository).\nThis also would allow splitting projects list into pages, if we so\ndesire.\n\nFiltering out forks and marking repository (project) as having forks\nis now consolidated into one subroutine (special case of handling\nforks in git_get_projects_list only for $projects_list being file is\nnow removed).  Forks handling is also cleaned up and simplified, which\nmight mean some changes in output.  $pr->{'forks'} now contains\nun-filled list of forks; we can now also detect situation where the\nway for having forks is prepared, but there are no forks yet.\n\nSorting projects got also refactored in a very straight way into\nsort_projects_list subroutine.\n\nThe interaction between forks, content tags and searching is now made\nmore explicit: searching whether by tag, or via search form turns off\nfork filtering (gitweb searches also forks, and will show all\nresults).  If 'ctags' feature is disabled, then searching by tag is\ntoo.\n\nThe t9500 test now includes some basic test for 'forks' and 'ctags'\nfeatures.\n\n\nGenerating list of projects by scanning given directory is now also a\nbit simplified wrt. handling filtering; it is byproduct of extracting\nforks filtering to separate subroutine.\n\nWhile at it we now detect that there are no projects and respond with\n\"404 No projects found\" also for 'project_index' and 'opml' actions.\n\nSigned-off-by: Jakub Narebski <jnareb@gmail.com>\n---\nIt is marked _currently_ as a RFC, because while it *looks* like it\nfinds forks correctly (at least when $projects_list is directory), the\nalgorithm for detecting forks is changed... though IMVHO the code is\ncleaner.\n\n gitweb/gitweb.perl                     |  219 +++++++++++++++++++++-----------\n t/t9500-gitweb-standalone-no-errors.sh |   49 +++++++\n 2 files changed, 191 insertions(+), 77 deletions(-)\n\ndiff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl\nindex 1b9369d..bc60158 100755\n--- a/gitweb/gitweb.perl\n+++ b/gitweb/gitweb.perl\n@@ -2643,21 +2643,23 @@ sub git_get_project_url_list {\n }\n \n sub git_get_projects_list {\n-\tmy ($filter) = @_;\n+\tmy $filter = shift || '';\n \tmy @list;\n \n-\t$filter ||= '';\n \t$filter =~ s/\\.git$//;\n \n-\tmy $check_forks = gitweb_check_feature('forks');\n-\n \tif (-d $projects_list) {\n \t\t# search in directory\n-\t\tmy $dir = $projects_list . ($filter ? \"/$filter\" : '');\n+\t\tmy $dir = $projects_list;\n \t\t# remove the trailing \"/\"\n \t\t$dir =~ s!/+$!!;\n-\t\tmy $pfxlen = length(\"$dir\");\n-\t\tmy $pfxdepth = ($dir =~ tr!/!!);\n+\t\tmy $pfxlen = length(\"$projects_list\");\n+\t\tmy $pfxdepth = ($projects_list =~ tr!/!!);\n+\t\t# when filtering, search only given subdirectory\n+\t\tif ($filter) {\n+\t\t\t$dir .= \"/$filter\";\n+\t\t\t$dir =~ s!/+$!!;\n+\t\t}\n \n \t\tFile::Find::find({\n \t\t\tfollow_fast => 1, # follow symbolic links\n@@ -2672,14 +2674,14 @@ sub git_get_projects_list {\n \t\t\t\t# only directories can be git repositories\n \t\t\t\treturn unless (-d $_);\n \t\t\t\t# don't traverse too deep (Find is super slow on os x)\n+\t\t\t\t# $project_maxdepth excludes depth of $projectroot\n \t\t\t\tif (($File::Find::name =~ tr!/!!) - $pfxdepth > $project_maxdepth) {\n \t\t\t\t\t$File::Find::prune = 1;\n \t\t\t\t\treturn;\n \t\t\t\t}\n \n-\t\t\t\tmy $subdir = substr($File::Find::name, $pfxlen + 1);\n+\t\t\t\tmy $path = substr($File::Find::name, $pfxlen + 1);\n \t\t\t\t# we check related file in $projectroot\n-\t\t\t\tmy $path = ($filter ? \"$filter/\" : '') . $subdir;\n \t\t\t\tif (check_export_ok(\"$projectroot/$path\")) {\n \t\t\t\t\tpush @list, { path => $path };\n \t\t\t\t\t$File::Find::prune = 1;\n@@ -2692,7 +2694,6 @@ sub git_get_projects_list {\n \t\t# 'git%2Fgit.git Linus+Torvalds'\n \t\t# 'libs%2Fklibc%2Fklibc.git H.+Peter+Anvin'\n \t\t# 'linux%2Fhotplug%2Fudev.git Greg+Kroah-Hartman'\n-\t\tmy %paths;\n \t\topen my $fd, '<', $projects_list or return;\n \tPROJECT:\n \t\twhile (my $line = <$fd>) {\n@@ -2703,32 +2704,9 @@ sub git_get_projects_list {\n \t\t\tif (!defined $path) {\n \t\t\t\tnext;\n \t\t\t}\n-\t\t\tif ($filter ne '') {\n-\t\t\t\t# looking for forks;\n-\t\t\t\tmy $pfx = substr($path, 0, length($filter));\n-\t\t\t\tif ($pfx ne $filter) {\n-\t\t\t\t\tnext PROJECT;\n-\t\t\t\t}\n-\t\t\t\tmy $sfx = substr($path, length($filter));\n-\t\t\t\tif ($sfx !~ /^\\/.*\\.git$/) {\n-\t\t\t\t\tnext PROJECT;\n-\t\t\t\t}\n-\t\t\t} elsif ($check_forks) {\n-\t\t\tPATH:\n-\t\t\t\tforeach my $filter (keys %paths) {\n-\t\t\t\t\t# looking for forks;\n-\t\t\t\t\tmy $pfx = substr($path, 0, length($filter));\n-\t\t\t\t\tif ($pfx ne $filter) {\n-\t\t\t\t\t\tnext PATH;\n-\t\t\t\t\t}\n-\t\t\t\t\tmy $sfx = substr($path, length($filter));\n-\t\t\t\t\tif ($sfx !~ /^\\/.*\\.git$/) {\n-\t\t\t\t\t\tnext PATH;\n-\t\t\t\t\t}\n-\t\t\t\t\t# is a fork, don't include it in\n-\t\t\t\t\t# the list\n-\t\t\t\t\tnext PROJECT;\n-\t\t\t\t}\n+\t\t\t# if $filter is rpovided, check if $path begins with $filter\n+\t\t\tif ($filter && $path !~ m!^\\Q$filter\\E/!) {\n+\t\t\t\tnext;\n \t\t\t}\n \t\t\tif (check_export_ok(\"$projectroot/$path\")) {\n \t\t\t\tmy $pr = {\n@@ -2736,8 +2714,6 @@ sub git_get_projects_list {\n \t\t\t\t\towner => to_utf8($owner),\n \t\t\t\t};\n \t\t\t\tpush @list, $pr;\n-\t\t\t\t(my $forks_path = $path) =~ s/\\.git$//;\n-\t\t\t\t$paths{$forks_path}++;\n \t\t\t}\n \t\t}\n \t\tclose $fd;\n@@ -2745,6 +2721,67 @@ sub git_get_projects_list {\n \treturn @list;\n }\n \n+# this assumes that forks follow immediately forked projects:\n+# [ ..., 'repo.git', 'repo/fork.git', ...]; if not, set second\n+# parameter to true value to sort projects by path first.\n+sub filter_forks_from_projects_list {\n+\tmy ($projects, $need_sorting) = @_;\n+\n+\t@$projects = sort { $a->{'path'} cmp $b->{'path'} } @$projects\n+\t\tif ($need_sorting);\n+\n+\tmy (@filtered, $last_pr);\n+ PROJECT:\n+\tforeach my $pr (@$projects) {\n+\t\tif ($last_pr &&\n+\t\t    $pr->{'path'} =~ m!^\\Q$last_pr\\E/!) {\n+\t\t\t# this is fork, add it to 'forks' and skip it\n+\t\t\tpush @{$filtered[-1]->{'forks'}}, $pr;\n+\t\t\tnext PROJECT;\n+\t\t}\n+\t\t($last_pr = $pr->{'path'}) =~ s/\\.git$//;\n+\t\tif ($last_pr !~ m!/*$! && -d \"$projectroot/$last_pr\") {\n+\t\t\t# it was not foo/.git, and there can be forks\n+\t\t\t$pr->{'forks'} = [];\n+\t\t}\n+\t\tpush @filtered, $pr;\n+\t}\n+\n+\treturn @filtered;\n+}\n+\n+# note: fill_project_list_info must be run first,\n+# for 'descr_long' and 'ctags' to be filled\n+sub search_projects_list {\n+\tmy ($projlist, %opts) = @_;\n+\tmy $tagfilter  = $opts{'tagfilter'};\n+\tmy $searchtext = $opts{'searchtext'};\n+\n+\treturn @$projlist\n+\t\tunless ($tagfilter || $searchtext);\n+\n+\tmy @projects;\n+ PROJECT:\n+\tforeach my $pr (@$projlist) {\n+\n+\t\tif ($tagfilter) {\n+\t\t\tnext unless ref($pr->{'ctags'}) eq 'HASH';\n+\t\t\tnext unless\n+\t\t\t\tgrep { lc($_) eq lc($tagfilter) } keys %{$pr->{'ctags'}};\n+\t\t}\n+\n+\t\tif ($searchtext) {\n+\t\t\tnext unless\n+\t\t\t\t$pr->{'path'} =~ /$searchtext/ ||\n+\t\t\t\t$pr->{'descr_long'} =~ /$searchtext/;\n+\t\t}\n+\n+\t\tpush @projects, $pr;\n+\t}\n+\n+\treturn @projects;\n+}\n+\n our $gitweb_project_owner = undef;\n sub git_get_project_list_from_file {\n \n@@ -4727,7 +4764,7 @@ sub git_patchset_body {\n # project in the list, removing invalid projects from returned list\n # NOTE: modifies $projlist, but does not remove entries from it\n sub fill_project_list_info {\n-\tmy ($projlist, $check_forks) = @_;\n+\tmy $projlist = shift;\n \tmy @projects;\n \n \tmy $show_ctags = gitweb_check_feature('ctags');\n@@ -4747,23 +4784,36 @@ sub fill_project_list_info {\n \t\tif (!defined $pr->{'owner'}) {\n \t\t\t$pr->{'owner'} = git_get_project_owner(\"$pr->{'path'}\") || \"\";\n \t\t}\n-\t\tif ($check_forks) {\n-\t\t\tmy $pname = $pr->{'path'};\n-\t\t\tif (($pname =~ s/\\.git$//) &&\n-\t\t\t    ($pname !~ /\\/$/) &&\n-\t\t\t    (-d \"$projectroot/$pname\")) {\n-\t\t\t\t$pr->{'forks'} = \"-d $projectroot/$pname\";\n-\t\t\t} else {\n-\t\t\t\t$pr->{'forks'} = 0;\n-\t\t\t}\n+\t\tif ($show_ctags) {\n+\t\t\t$pr->{'ctags'} = git_get_project_ctags($pr->{'path'});\n \t\t}\n-\t\t$show_ctags and $pr->{'ctags'} = git_get_project_ctags($pr->{'path'});\n \t\tpush @projects, $pr;\n \t}\n \n \treturn @projects;\n }\n \n+sub sort_projects_list {\n+\tmy ($projlist, $order) = @_;\n+\tmy @projects;\n+\n+\tmy %order_info = (\n+\t\tproject => { key => 'path', type => 'str' },\n+\t\tdescr => { key => 'descr_long', type => 'str' },\n+\t\towner => { key => 'owner', type => 'str' },\n+\t\tage => { key => 'age', type => 'num' }\n+\t);\n+\tmy $oi = $order_info{$order};\n+\treturn @$projlist unless defined $oi;\n+\tif ($oi->{'type'} eq 'str') {\n+\t\t@projects = sort {$a->{$oi->{'key'}} cmp $b->{$oi->{'key'}}} @$projlist;\n+\t} else {\n+\t\t@projects = sort {$a->{$oi->{'key'}} <=> $b->{$oi->{'key'}}} @$projlist;\n+\t}\n+\n+\treturn @projects;\n+}\n+\n # print 'sort by' <th> element, generating 'sort by $name' replay link\n # if that order is not selected\n sub print_sort_th {\n@@ -4790,28 +4840,39 @@ sub format_sort_th {\n sub git_project_list_body {\n \t# actually uses global variable $project\n \tmy ($projlist, $order, $from, $to, $extra, $no_header) = @_;\n+\tmy @projects = @$projlist;\n \n \tmy $check_forks = gitweb_check_feature('forks');\n-\tmy @projects = fill_project_list_info($projlist, $check_forks);\n+\tmy $show_ctags  = gitweb_check_feature('ctags');\n+\tmy $tagfilter = $show_ctags ? $cgi->param('by_tag') : undef;\n+\t$check_forks = undef\n+\t\tif ($tagfilter || $searchtext);\n+\n+\t# filtering out forks before filling info allows to do less work\n+\t@projects = filter_forks_from_projects_list(\\@projects)\n+\t\tif ($check_forks);\n+\t@projects = fill_project_list_info(\\@projects);\n+\t# searching projects require filling to be run before it\n+\t@projects = search_projects_list(\\@projects,\n+\t                                 'searchtext' => $searchtext,\n+\t                                 'tagfilter'  => $tagfilter)\n+\t\tif ($tagfilter || $searchtext);\n \n \t$order ||= $default_projects_order;\n \t$from = 0 unless defined $from;\n \t$to = $#projects if (!defined $to || $#projects < $to);\n \n-\tmy %order_info = (\n-\t\tproject => { key => 'path', type => 'str' },\n-\t\tdescr => { key => 'descr_long', type => 'str' },\n-\t\towner => { key => 'owner', type => 'str' },\n-\t\tage => { key => 'age', type => 'num' }\n-\t);\n-\tmy $oi = $order_info{$order};\n-\tif ($oi->{'type'} eq 'str') {\n-\t\t@projects = sort {$a->{$oi->{'key'}} cmp $b->{$oi->{'key'}}} @projects;\n-\t} else {\n-\t\t@projects = sort {$a->{$oi->{'key'}} <=> $b->{$oi->{'key'}}} @projects;\n+\t# short circuit\n+\tif ($from > $to) {\n+\t\tprint \"<center>\\n\".\n+\t\t      \"<b>No such projects found</b><br />\\n\".\n+\t\t      \"Click \".$cgi->a({-href=>href(project=>undef)},\"here\").\" to view all projects<br />\\n\".\n+\t\t      \"</center>\\n<br />\\n\";\n+\t\treturn;\n \t}\n \n-\tmy $show_ctags = gitweb_check_feature('ctags');\n+\t@projects = sort_projects_list(\\@projects, $order);\n+\n \tif ($show_ctags) {\n \t\tmy %ctags;\n \t\tforeach my $p (@projects) {\n@@ -4837,32 +4898,26 @@ sub git_project_list_body {\n \t\t      \"</tr>\\n\";\n \t}\n \tmy $alternate = 1;\n-\tmy $tagfilter = $cgi->param('by_tag');\n \tfor (my $i = $from; $i <= $to; $i++) {\n \t\tmy $pr = $projects[$i];\n \n-\t\tnext if $tagfilter and $show_ctags and not grep { lc $_ eq lc $tagfilter } keys %{$pr->{'ctags'}};\n-\t\tnext if $searchtext and not $pr->{'path'} =~ /$searchtext/\n-\t\t\tand not $pr->{'descr_long'} =~ /$searchtext/;\n-\t\t# Weed out forks or non-matching entries of search\n-\t\tif ($check_forks) {\n-\t\t\tmy $forkbase = $project; $forkbase ||= ''; $forkbase =~ s#\\.git$#/#;\n-\t\t\t$forkbase=\"^$forkbase\" if $forkbase;\n-\t\t\tnext if not $searchtext and not $tagfilter and $show_ctags\n-\t\t\t\tand $pr->{'path'} =~ m#$forkbase.*/.*#; # regexp-safe\n-\t\t}\n-\n \t\tif ($alternate) {\n \t\t\tprint \"<tr class=\\\"dark\\\">\\n\";\n \t\t} else {\n \t\t\tprint \"<tr class=\\\"light\\\">\\n\";\n \t\t}\n \t\t$alternate ^= 1;\n+\n \t\tif ($check_forks) {\n \t\t\tprint \"<td>\";\n \t\t\tif ($pr->{'forks'}) {\n-\t\t\t\tprint \"<!-- $pr->{'forks'} -->\\n\";\n-\t\t\t\tprint $cgi->a({-href => href(project=>$pr->{'path'}, action=>\"forks\")}, \"+\");\n+\t\t\t\tmy $nforks = scalar @{$pr->{'forks'}};\n+\t\t\t\tif ($nforks > 0) {\n+\t\t\t\t\tprint $cgi->a({-href => href(project=>$pr->{'path'}, action=>\"forks\"),\n+\t\t\t\t\t               -title => \"$nforks forks\"}, \"+\");\n+\t\t\t\t} else {\n+\t\t\t\t\tprint $cgi->span({-title => \"$nforks forks\"}, \"+\");\n+\t\t\t\t}\n \t\t\t}\n \t\t\tprint \"</td>\\n\";\n \t\t}\n@@ -5343,7 +5398,10 @@ sub git_forks {\n }\n \n sub git_project_index {\n-\tmy @projects = git_get_projects_list($project);\n+\tmy @projects = git_get_projects_list();\n+\tif (!@projects) {\n+\t\tdie_error(404, \"No projects found\");\n+\t}\n \n \tprint $cgi->header(\n \t\t-type => 'text/plain',\n@@ -5385,7 +5443,11 @@ sub git_summary {\n \tmy $check_forks = gitweb_check_feature('forks');\n \n \tif ($check_forks) {\n+\t\t# find forks of a project\n \t\t@forklist = git_get_projects_list($project);\n+\t\t# filter out forks of forks\n+\t\t@forklist = filter_forks_from_projects_list(\\@forklist)\n+\t\t\tif (@forklist);\n \t}\n \n \tgit_header_html();\n@@ -7305,6 +7367,9 @@ sub git_atom {\n \n sub git_opml {\n \tmy @list = git_get_projects_list();\n+\tif (!@list) {\n+\t\tdie_error(404, \"No projects found\");\n+\t}\n \n \tprint $cgi->header(\n \t\t-type => 'text/xml',\ndiff --git a/t/t9500-gitweb-standalone-no-errors.sh b/t/t9500-gitweb-standalone-no-errors.sh\nindex 35c151d..0dc573d 100755\n--- a/t/t9500-gitweb-standalone-no-errors.sh\n+++ b/t/t9500-gitweb-standalone-no-errors.sh\n@@ -591,4 +591,53 @@ test_expect_success HIGHLIGHT \\\n \t git commit -m \"Add test.sh\" &&\n \t gitweb_run \"p=.git;a=blob;f=test.sh\"'\n \n+# ----------------------------------------------------------------------\n+# forks of projects\n+\n+cat >>gitweb_config.perl <<-\\EOF &&\n+$feature{'forks'}{'default'} = [1];\n+EOF\n+\n+test_expect_success \\\n+\t'forks: prepare' \\\n+\t'git init --bare foo.git &&\n+\t git --git-dir=foo.git --work-tree=. add file &&\n+\t git --git-dir=foo.git --work-tree=. commit -m \"Initial commit\" &&\n+\t echo \"foo\" > foo.git/description &&\n+\t mkdir -p foo &&\n+\t (cd foo &&\n+\t  git clone --shared --bare ../foo.git foo-forked.git &&\n+\t  echo \"fork of foo\" > foo-forked.git/description)'\n+\n+test_expect_success \\\n+\t'forks: projects list' \\\n+\t'gitweb_run'\n+\n+test_expect_success \\\n+\t'forks: forks action' \\\n+\t'gitweb_run \"p=foo.git;a=forks\"'\n+\n+# ----------------------------------------------------------------------\n+# content tags (tag cloud)\n+\n+cat >>gitweb_config.perl <<-\\EOF &&\n+# we don't test _setting_ content tags, so any true value is good\n+$feature{'ctags'}{'default'} = ['ctags_script.cgi'];\n+EOF\n+\n+test_expect_success \\\n+\t'ctags: tag cloud in projects list' \\\n+\t'mkdir .git/ctags &&\n+\t echo \"2\" > .git/ctags/foo &&\n+\t echo \"1\" > .git/ctags/bar &&\n+\tgitweb_run'\n+\n+test_expect_success \\\n+\t'ctags: search projects by existing tag' \\\n+\t'gitweb_run \"by_tag=foo\"'\n+\n+test_expect_success \\\n+\t'ctags: search projects by non existent tag' \\\n+\t'gitweb_run \"by_tag=non-existent\"'\n+\n test_done\n"},{"id":"162349","messageId":"20110227100838.GA24919@elie","threadId":"26610","inReplyTo":"20110226215230.5333.92839.stgit@localhost.localdomain","subject":"Re: [PATCH/RFC] gitweb: Restructure projects list generation","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-02-27T10:08:38Z","receivedAt":"2011-02-27T10:08:38Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nJakub Narebski wrote:\n\n> Extract filtering out forks (which is done if 'forks' feature is\n> enabled) into filter_forks_from_projects_list subroutine\n\nContext (to remind myself): the git_get_projects_list function decides\nwhich repositories to show on the homepage.  git_project_list_body\ntakes care of actually showing them in a table; it displays a \"+\" sign\nin front of projects with forks and generally the project list it is\npassed omits the forks themselves.\n\ngit_get_projects_list needs to be reasonably fast, since it is used\nto validate the \"project\" parameter in every request.\n\n[...]\n> Both are now run _before_ displaying projects, and not while printing;\n> this allow to know upfront if there were any found projects.  Gitweb\n> now can and do print 'No such projects found' if user searches for\n> phrase which does not correspond to any project (any repository).\n\nAren't forks filtered out by git-get-projects-list already?\n\n[...]\n> Filtering out forks and marking repository (project) as having forks\n> is now consolidated into one subroutine (special case of handling\n> forks in git_get_projects_list only for $projects_list being file is\n> now removed).\n\nAh, no, they aren't.  That's a good change for consistency already.\n\n> Forks handling is also cleaned up and simplified, which\n> might mean some changes in output.\n\n(Not having read the code yet) this part is not obvious to me.  Maybe\nan example could help.\n\n[...]\n> The interaction between forks, content tags and searching is now made\n> more explicit: searching whether by tag, or via search form turns off\n> fork filtering (gitweb searches also forks, and will show all\n> results).\n\nHm, or maybe this is it.\n\n> IMVHO the code is\n> cleaner.\n\nSo some general code tidying is intermixed.\n\n> --- a/gitweb/gitweb.perl\n> +++ b/gitweb/gitweb.perl\n> @@ -2646,18 +2646,20 @@ sub git_get_projects_list {\n[...]\n> -\t\tmy $dir = $projects_list . ($filter ? \"/$filter\" : '');\n> +\t\tmy $dir = $projects_list;\n>  \t\t# remove the trailing \"/\"\n>  \t\t$dir =~ s!/+$!!;\n> -\t\tmy $pfxlen = length(\"$dir\");\n> -\t\tmy $pfxdepth = ($dir =~ tr!/!!);\n> +\t\tmy $pfxlen = length(\"$projects_list\");\n> +\t\tmy $pfxdepth = ($projects_list =~ tr!/!!);\n[...]\n\n$dir is the same as before except that trailing slashes are removed,\nand meanwhile the stripped names of directories returned from find()\nwill include $filter.  Should be almost a no-op (i.e., a nice\nsimplification).\n\n> @@ -2672,14 +2674,14 @@ sub git_get_projects_list {\n>  \t\t\t\t# only directories can be git repositories\n>  \t\t\t\treturn unless (-d $_);\n>  \t\t\t\t# don't traverse too deep (Find is super slow on os x)\n> +\t\t\t\t# $project_maxdepth excludes depth of $projectroot\n>  \t\t\t\tif (($File::Find::name =~ tr!/!!) - $pfxdepth > $project_maxdepth) {\n\nA bugfix.  $project_maxdepth is advertised to be relative to the\nprojectroot but it was relative to $projects_list/$filter.\n\n[...]\n> @@ -2703,32 +2704,9 @@ sub git_get_projects_list {\n>  \t\t\tif (!defined $path) {\n>  \t\t\t\tnext;\n>  \t\t\t}\n> -\t\t\tif ($filter ne '') {\n> -\t\t\t\t# looking for forks;\n> -\t\t\t\tmy $pfx = substr($path, 0, length($filter));\n> -\t\t\t\tif ($pfx ne $filter) {\n> -\t\t\t\t\tnext PROJECT;\n> -\t\t\t\t}\n> -\t\t\t\tmy $sfx = substr($path, length($filter));\n> -\t\t\t\tif ($sfx !~ /^\\/.*\\.git$/) {\n> -\t\t\t\t\tnext PROJECT;\n> -\t\t\t\t}\n[...]\n> +\t\t\t# if $filter is rpovided, check if $path begins with $filter\n\ns/rpovided/provided/ :)\n\n> +\t\t\tif ($filter && $path !~ m!^\\Q$filter\\E/!) {\n> +\t\t\t\tnext;\n\nWhy did the code check for \\Q.git\\E$ before?  If I'm not missing\nsomething, I'm happy to see the condition go.\n\nWhat if $filter is 0?  Silly question, I guess.\n\n[...]\n> @@ -2745,6 +2721,67 @@ sub git_get_projects_list {\n>  \treturn @list;\n>  }\n>  \n> +# this assumes that forks follow immediately forked projects:\n> +# [ ..., 'repo.git', 'repo/fork.git', ...]; if not, set second\n> +# parameter to true value to sort projects by path first.\n> +sub filter_forks_from_projects_list {\n> +\tmy ($projects, $need_sorting) = @_;\n> +\n> +\t@$projects = sort { $a->{'path'} cmp $b->{'path'} } @$projects\n> +\t\tif ($need_sorting);\n\nWhat happens in this scenario?\n\n\tgit.git\n\tgit.related.project.git\n\tgit/platforms.git\n\n[...]\n> @@ -4747,23 +4784,36 @@ sub fill_project_list_info {\n>  \t\tif (!defined $pr->{'owner'}) {\n>  \t\t\t$pr->{'owner'} = git_get_project_owner(\"$pr->{'path'}\") || \"\";\n>  \t\t}\n> -\t\tif ($check_forks) {\n> -\t\t\tmy $pname = $pr->{'path'};\n> -\t\t\tif (($pname =~ s/\\.git$//) &&\n> -\t\t\t    ($pname !~ /\\/$/) &&\n> -\t\t\t    (-d \"$projectroot/$pname\")) {\n> -\t\t\t\t$pr->{'forks'} = \"-d $projectroot/$pname\";\n\nSo currently we treat project.git as having forks when the\ncorresponding project/ directory exists, even when the latter is\nempty.  The proposed new rule is that project.git has forks if and\nonly if there is at least one project/foo.git repository.  Sensible.\n\nThanks for a pleasant read.\n\nHope that helps,\nJonathan\n"},{"id":"162365","messageId":"201102271603.13902.jnareb@gmail.com","threadId":"26610","inReplyTo":"20110227100838.GA24919@elie","subject":"Re: [PATCH/RFC] gitweb: Restructure projects list generation","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2011-02-27T15:03:08Z","receivedAt":"2011-02-27T15:03:08Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On Sun, 27 Feb 2011, Jonathan Nieder wrote:\n> Jakub Narebski wrote:\n> \n> > Extract filtering out forks (which is done if 'forks' feature is\n> > enabled) into filter_forks_from_projects_list subroutine\n> \n> Context (to remind myself): the git_get_projects_list function decides\n> which repositories to show on the homepage.\n\nActually it git_get_projects_list generates list of all exported\nrepositories, whether they are visible in projects list page (homepage)\nor not... at least after this change.\n\nWell... list of directories that look like repositories; it is actually\nchecked further with git_get_last_activity (running actual git command)\nin fill_project_list_info if they are really git repositories.\n\n>                                               git_project_list_body \n> takes care of actually showing them in a table; it displays a \"+\" sign\n> in front of projects with forks and generally the project list it is\n> passed omits the forks themselves.\n\nWell, forks are hidden (listed on 'forks' pages linked to by those \"+\"\nsigns) only if 'forks' feature is enabled.\n\n> \n> git_get_projects_list needs to be reasonably fast, since it is used\n> to validate the \"project\" parameter in every request.\n\nOnly with $strict_export set to true (it defaults to false).\n\n> [...]\n> > Both are now run _before_ displaying projects, and not while printing;\n> > this allow to know upfront if there were any found projects.  Gitweb\n> > now can and do print 'No such projects found' if user searches for\n> > phrase which does not correspond to any project (any repository).\n> \n> Aren't forks filtered out by git-get-projects-list already?\n\nAfter this commit they are not, and they should not be.  If forks were\nfiltered out, then with $strict_export you wouldn't be able to access\npages of repositories which are forks.\n\n> [...]\n> > Filtering out forks and marking repository (project) as having forks\n> > is now consolidated into one subroutine (special case of handling\n> > forks in git_get_projects_list only for $projects_list being file is\n> > now removed).\n> \n> Ah, no, they aren't.  That's a good change for consistency already.\n> \n> > Forks handling is also cleaned up and simplified, which\n> > might mean some changes in output.\n> \n> (Not having read the code yet) this part is not obvious to me.  Maybe\n> an example could help.\n\nWell, the commit message is quite large anyway, so I didn't describe in\ndetailwhat one can read in patch itself...\n\nBut see also comment below about algorithm used.\n\n> [...]\n> > The interaction between forks, content tags and searching is now made\n> > more explicit: searching whether by tag, or via search form turns off\n> > fork filtering (gitweb searches also forks, and will show all\n> > results).\n> \n> Hm, or maybe this is it.\n> \n> > IMVHO the code is\n> > cleaner.\n> \n> So some general code tidying is intermixed.\n> \n> > --- a/gitweb/gitweb.perl\n> > +++ b/gitweb/gitweb.perl\n> > @@ -2646,18 +2646,20 @@ sub git_get_projects_list {\n> [...]\n> > -\t\tmy $dir = $projects_list . ($filter ? \"/$filter\" : '');\n> > +\t\tmy $dir = $projects_list;\n> >  \t\t# remove the trailing \"/\"\n> >  \t\t$dir =~ s!/+$!!;\n> > -\t\tmy $pfxlen = length(\"$dir\");\n> > -\t\tmy $pfxdepth = ($dir =~ tr!/!!);\n> > +\t\tmy $pfxlen = length(\"$projects_list\");\n> > +\t\tmy $pfxdepth = ($projects_list =~ tr!/!!);\n> [...]\n> \n> $dir is the same as before except that trailing slashes are removed,\n> and meanwhile the stripped names of directories returned from find()\n> will include $filter.  Should be almost a no-op (i.e., a nice\n> simplification).\n\nThanks.\n\nThis code could be further simplified if not for the fact that at least\ntheoretically with $projects_list being directory to scan, $projectroot\ncan be different from $projects_list.\n\nI'll try to resend fixed version soon.\n\n> > @@ -2672,14 +2674,14 @@ sub git_get_projects_list {\n> >  \t\t\t\t# only directories can be git repositories\n> >  \t\t\t\treturn unless (-d $_);\n> >  \t\t\t\t# don't traverse too deep (Find is super slow on os x)\n> > +\t\t\t\t# $project_maxdepth excludes depth of $projectroot\n> >  \t\t\t\tif (($File::Find::name =~ tr!/!!) - $pfxdepth > $project_maxdepth) {\n> \n> A bugfix.  $project_maxdepth is advertised to be relative to the\n> projectroot but it was relative to $projects_list/$filter.\n\nI'm not sure if it was advertised in such detail, but I think consistency\nis good to have: we don't go beyond some depth regardless whether $filter\nis set or not, i.e. whether we are getting list of projects for homepage\n('projects_list' action) or for some 'forks' page.\n\n> [...]\n> > @@ -2703,32 +2704,9 @@ sub git_get_projects_list {\n> >  \t\t\tif (!defined $path) {\n> >  \t\t\t\tnext;\n> >  \t\t\t}\n> > -\t\t\tif ($filter ne '') {\n> > -\t\t\t\t# looking for forks;\n> > -\t\t\t\tmy $pfx = substr($path, 0, length($filter));\n> > -\t\t\t\tif ($pfx ne $filter) {\n> > -\t\t\t\t\tnext PROJECT;\n> > -\t\t\t\t}\n> > -\t\t\t\tmy $sfx = substr($path, length($filter));\n> > -\t\t\t\tif ($sfx !~ /^\\/.*\\.git$/) {\n> > -\t\t\t\t\tnext PROJECT;\n> > -\t\t\t\t}\n> [...]\n> > +\t\t\t# if $filter is rpovided, check if $path begins with $filter\n> \n> s/rpovided/provided/ :)\n\nI should have run spellchecker...\n\n> > +\t\t\tif ($filter && $path !~ m!^\\Q$filter\\E/!) {\n> > +\t\t\t\tnext;\n> \n> Why did the code check for \\Q.git\\E$ before?  If I'm not missing\n> something, I'm happy to see the condition go.\n\nThis was about looking for forks, which is now moved out of this\nsubroutine into filter_forks_from_projects_list subroutine.\n\n> What if $filter is 0?  Silly question, I guess.\n\nNot a problem.  \\Q and \\E are for quoting metacharacters, i.e. treating\n$filter as string (as prefix to be matched) rather than as regexp.\n\n> [...]\n> > @@ -2745,6 +2721,67 @@ sub git_get_projects_list {\n> >  \treturn @list;\n> >  }\n> >  \n> > +# this assumes that forks follow immediately forked projects:\n> > +# [ ..., 'repo.git', 'repo/fork.git', ...]; if not, set second\n> > +# parameter to true value to sort projects by path first.\n> > +sub filter_forks_from_projects_list {\n> > +\tmy ($projects, $need_sorting) = @_;\n> > +\n> > +\t@$projects = sort { $a->{'path'} cmp $b->{'path'} } @$projects\n> > +\t\tif ($need_sorting);\n> \n> What happens in this scenario?\n> \n> \tgit.git\n> \tgit.related.project.git\n> \tgit/platforms.git\n\nThanks for catching this.\n\nIt looks like I have oversimplified the algorithm by requiring that \nforked project directly precedes any of its forks (if they exists).\nI'd have to redo this part of patch.\n\n> [...]\n> > @@ -4747,23 +4784,36 @@ sub fill_project_list_info {\n> >  \t\tif (!defined $pr->{'owner'}) {\n> >  \t\t\t$pr->{'owner'} = git_get_project_owner(\"$pr->{'path'}\") || \"\";\n> >  \t\t}\n> > -\t\tif ($check_forks) {\n> > -\t\t\tmy $pname = $pr->{'path'};\n> > -\t\t\tif (($pname =~ s/\\.git$//) &&\n> > -\t\t\t    ($pname !~ /\\/$/) &&\n> > -\t\t\t    (-d \"$projectroot/$pname\")) {\n> > -\t\t\t\t$pr->{'forks'} = \"-d $projectroot/$pname\";\n> \n> So currently we treat project.git as having forks when the\n> corresponding project/ directory exists, even when the latter is\n> empty.  The proposed new rule is that project.git has forks if and\n> only if there is at least one project/foo.git repository.  Sensible.\n\nActually it is marked as having 0 forks, which visually results in \"+\"\nsign which is not a hyperlink to 'forks' view.\n\nThough I am not sure if it is worth it: without mentioned feature code\nwould be slightly simpler.\n\n\nNote also that previous code put _string_ into 'forks' field, with\ncontents \"-d <path to project>\", instead of 1 as one might expect.\n\nEarlier code contained a few leftover debugging things; I am not sure\nif I have removed everything, at least wrt. projects list.\n\n> Hope that helps,\n\nThanks again for your comments.\n\n-- \nJakub Narebski\nPoland\n"},{"id":"162500","messageId":"201103010202.01408.jnareb@gmail.com","threadId":"26610","inReplyTo":"201102271603.13902.jnareb@gmail.com","subject":"Re: [PATCH/RFC] gitweb: Restructure projects list generation","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2011-03-01T01:01:55Z","receivedAt":"2011-03-01T01:01:55Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On Sun, 27 Feb 2011, Jakub Narebski wrote:\n> On Sun, 27 Feb 2011, Jonathan Nieder wrote:\n> > Jakub Narebski wrote:\n\n> > > +# this assumes that forks follow immediately forked projects:\n> > > +# [ ..., 'repo.git', 'repo/fork.git', ...]; if not, set second\n> > > +# parameter to true value to sort projects by path first.\n> > > +sub filter_forks_from_projects_list {\n> > > +\tmy ($projects, $need_sorting) = @_;\n> > > +\n> > > +\t@$projects = sort { $a->{'path'} cmp $b->{'path'} } @$projects\n> > > +\t\tif ($need_sorting);\n> > \n> > What happens in this scenario?\n> > \n> > \tgit.git\n> > \tgit.related.project.git\n> > \tgit/platforms.git\n> \n> Thanks for catching this.\n> \n> It looks like I have oversimplified the algorithm by requiring that \n> forked project directly precedes any of its forks (if they exists).\n> I'd have to redo this part of patch.\n> \n> > [...]\n> > > @@ -4747,23 +4784,36 @@ sub fill_project_list_info {\n> > >  \t\tif (!defined $pr->{'owner'}) {\n> > >  \t\t\t$pr->{'owner'} = git_get_project_owner(\"$pr->{'path'}\") || \"\";\n> > >  \t\t}\n> > > -\t\tif ($check_forks) {\n> > > -\t\t\tmy $pname = $pr->{'path'};\n> > > -\t\t\tif (($pname =~ s/\\.git$//) &&\n> > > -\t\t\t    ($pname !~ /\\/$/) &&\n> > > -\t\t\t    (-d \"$projectroot/$pname\")) {\n> > > -\t\t\t\t$pr->{'forks'} = \"-d $projectroot/$pname\";\n\nLet's examine what's we had, what this commit does, and what we can have.\n\nBefore this commit there were two implementations of detecting and \nfiltering-out forks: one based only on directory structure in\nfill_project_list_info (it detected forks, but didn't filter them out),\nand one in git_get_projects_list, which was based on pathnames and was\nrun only for $projects_list being [index] file (it filtered-out forks).\n\nThis commit replaced both by filter_forks_from_projects_list, which\nmainly detected forks based on path, with directory based detecting\nif there _can_ be forks... but this solution is based on overly strict\nand not true assumption that forks always directly follow forked \nproject, which doesn't need to be true e.g. for scanning $projects_list\ndirectory.\n\n\nHmmm... it looks for me like filtering out forks worked only for \n$projects_list being file; the code in fill_project_list_info() detected\nwhich projects were forked, but didn't detect which projects were forks\nand should be filtered.  The code inside $check_forks conditional that\nused to be in git_projects_list_body() was about filtering out for second\ntime projects that are not forks of current project, for 'forks' action.\n\nNow naive implementation of detecting forks, and also implementation used\nto be used in git_get_projects_list() for $projects_list being file is\nO(n^2) in number of projects.  With a bit of simplification it can be\nO(<projects>*<forked projects>) + O(<projects>)*stat (cost of \"-d <dir>\").\nWithe git.kernel.org having around 1,000 projects, and repo.or.cz having\naround 4,000 projects not counting forks, O(n^2) is out of question.\n\nOf those 4,000 projects around 300 (or 7%) has forks, according to \nrepo.or.cz projects list page.  But assuming that percentage of forked\nrepositories remains constant with growth of number of repositories,\nthis is still quadratic cost... but perhaps acceptable.\n\n\nWe can use more advanced algorithm to find prefixes (to find forks);\nfor example using trie[1][2] to find forks costs O(<projects>*<depth>).\nFor git.kernel.org which has quite deep hierarchy of projects number\nof path components (depth) is no more than 6.\n\nSynthetic benchmark with 2000 repositories, 5% of which are forked,\nwith 5 forks per forked repository shows that trie-based solution is\naround 25 times faster than original solution from git_get_projects_list\nwith %paths.\n\nThe disadvantage of this solution is that even seriously stripped-down\ntrie construction and lookup is around 2 pages of code... or using non-core\nTree::Trie module from CPAN.\n\n[1]: http://en.wikipedia.org/wiki/Trie\n[2]: http://p3rl.org/Tree::Trie\n-- \nJakub Narebski\nPoland\n"},{"id":"162649","messageId":"201103021711.25241.jnareb@gmail.com","threadId":"26610","inReplyTo":"201103010202.01408.jnareb@gmail.com","subject":"[PATCHv2/RFC] gitweb: Restructure projects list generation","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2011-03-02T16:11:19Z","receivedAt":"2011-03-02T16:11:19Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Extract filtering out forks (which is done if 'forks' feature is\nenabled) into filter_forks_from_projects_list subroutine, and\nsearching projects (via projects search form, or via content tags)\ninto search_projects_list subroutine.\n\nBoth are now run _before_ displaying projects, and not while printing;\nthis allow to know upfront if there were any found projects.  Gitweb\nnow can and do print 'No such projects found' if user searches for\nphrase which does not correspond to any project (any repository).\nThis also would allow splitting projects list into pages, if we so\ndesire.\n\nFiltering out forks and marking repository (project) as having forks\nis now consolidated into one subroutine (special case of handling\nforks in git_get_projects_list only for $projects_list being file is\nnow removed).  Forks handling is also cleaned up and simplified.\n$pr->{'forks'} now contains un-filled list of forks; we can now also\ndetect situation where the way for having forks is prepared, but there\nare no forks yet.\n\nSorting projects got also refactored in a very straight way (just\nmoving code) into sort_projects_list subroutine.\n\nThe interaction between forks, content tags and searching is now made\nmore explicit: searching whether by tag, or via search form turns off\nfork filtering (gitweb searches also forks, and will show all\nresults).  If 'ctags' feature is disabled, then searching by tag is\ntoo.\n\nThe t9500 test now includes some basic test for 'forks' and 'ctags'\nfeatures; the t9502 includes test checking if gitweb correctly filters\nout forks.\n\n\nGenerating list of projects by scanning given directory is now also a\nbit simplified wrt. handling filtering; it is byproduct of extracting\nfiltering forks to separate subroutine.\n\nWhile at it we now detect that there are no projects and respond with\n\"404 No projects found\" also for 'project_index' and 'opml' actions.\n\nSigned-off-by: Jakub Narebski <jnareb@gmail.com>\n---\nThe main difference from previous version is that newly introduced\nfilter_forks_from_projects_list() no longer relies on the assumption\nthat forked project immediately precedes all of its forks... which is\nnot true when $porjects_list is a directory and we have e.g. such\nsituation:\n\n  repo.git\n  repo.related.git\n  repo_other.git\n  repo/fork.git\n\nThis issue was noticed by Jonathan Nieder.\n\nfilter_forks_from_projects_list() uses trie[1] (prefix tree) to find\nwhich repositories are forks of other projects; directories are used\nas \"letters\" in trie.  Algorithm to create trie and find prefix match\nwas created with some help of code of Tree::Tree[2] Perl module from\nCPAN.\n\n[1]: http://en.wikipedia.org/wiki/Trie\n[2]: http://p3rl.org/Tree::Trie\n\nThis revision includes additionally tests in t9502 that correct\nprojects are filtered.\n\n\nNote that before this commit filtering out forks worked only for\n$projects_list being a file, it assumed that forks are always after\nforked project (not very unreasonable), and used algorithm which is\nO(<projects>^2).\n\nCurrent code filters out projects only where it should, regardless\nwhether $projects_list is directory or a file, and trie-based\nalgorithm is O(<projects>) + O(<projects forked>*<max depth>).\nCurrent code also consistently finds shortest prefix (important in\ncounting forks in case of forks of forks).\n\n\nThis is an RFC because I am not sure if I did tests in t9502 right\nand efficient enough.\n\nThere is also question whether $pr->{'forks'} should be a list of\nforks, or would having $pr->{'forks'} being number of forks be enough.\n\nRefactoring sort_projects_list and fixing handling of $project_maxdepth\ncould be done in a separate patches.\n\n gitweb/gitweb.perl                        |  250 ++++++++++++++++++++---------\n t/t9500-gitweb-standalone-no-errors.sh    |   49 ++++++\n t/t9502-gitweb-standalone-parse-output.sh |   74 +++++++++\n 3 files changed, 296 insertions(+), 77 deletions(-)\n\ndiff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl\nindex 1b9369d..996b647 100755\n--- a/gitweb/gitweb.perl\n+++ b/gitweb/gitweb.perl\n@@ -2643,21 +2643,23 @@ sub git_get_project_url_list {\n }\n \n sub git_get_projects_list {\n-\tmy ($filter) = @_;\n+\tmy $filter = shift || '';\n \tmy @list;\n \n-\t$filter ||= '';\n \t$filter =~ s/\\.git$//;\n \n-\tmy $check_forks = gitweb_check_feature('forks');\n-\n \tif (-d $projects_list) {\n \t\t# search in directory\n-\t\tmy $dir = $projects_list . ($filter ? \"/$filter\" : '');\n+\t\tmy $dir = $projects_list;\n \t\t# remove the trailing \"/\"\n \t\t$dir =~ s!/+$!!;\n-\t\tmy $pfxlen = length(\"$dir\");\n-\t\tmy $pfxdepth = ($dir =~ tr!/!!);\n+\t\tmy $pfxlen = length(\"$projects_list\");\n+\t\tmy $pfxdepth = ($projects_list =~ tr!/!!);\n+\t\t# when filtering, search only given subdirectory\n+\t\tif ($filter) {\n+\t\t\t$dir .= \"/$filter\";\n+\t\t\t$dir =~ s!/+$!!;\n+\t\t}\n \n \t\tFile::Find::find({\n \t\t\tfollow_fast => 1, # follow symbolic links\n@@ -2672,14 +2674,14 @@ sub git_get_projects_list {\n \t\t\t\t# only directories can be git repositories\n \t\t\t\treturn unless (-d $_);\n \t\t\t\t# don't traverse too deep (Find is super slow on os x)\n+\t\t\t\t# $project_maxdepth excludes depth of $projectroot\n \t\t\t\tif (($File::Find::name =~ tr!/!!) - $pfxdepth > $project_maxdepth) {\n \t\t\t\t\t$File::Find::prune = 1;\n \t\t\t\t\treturn;\n \t\t\t\t}\n \n-\t\t\t\tmy $subdir = substr($File::Find::name, $pfxlen + 1);\n+\t\t\t\tmy $path = substr($File::Find::name, $pfxlen + 1);\n \t\t\t\t# we check related file in $projectroot\n-\t\t\t\tmy $path = ($filter ? \"$filter/\" : '') . $subdir;\n \t\t\t\tif (check_export_ok(\"$projectroot/$path\")) {\n \t\t\t\t\tpush @list, { path => $path };\n \t\t\t\t\t$File::Find::prune = 1;\n@@ -2692,7 +2694,6 @@ sub git_get_projects_list {\n \t\t# 'git%2Fgit.git Linus+Torvalds'\n \t\t# 'libs%2Fklibc%2Fklibc.git H.+Peter+Anvin'\n \t\t# 'linux%2Fhotplug%2Fudev.git Greg+Kroah-Hartman'\n-\t\tmy %paths;\n \t\topen my $fd, '<', $projects_list or return;\n \tPROJECT:\n \t\twhile (my $line = <$fd>) {\n@@ -2703,32 +2704,9 @@ sub git_get_projects_list {\n \t\t\tif (!defined $path) {\n \t\t\t\tnext;\n \t\t\t}\n-\t\t\tif ($filter ne '') {\n-\t\t\t\t# looking for forks;\n-\t\t\t\tmy $pfx = substr($path, 0, length($filter));\n-\t\t\t\tif ($pfx ne $filter) {\n-\t\t\t\t\tnext PROJECT;\n-\t\t\t\t}\n-\t\t\t\tmy $sfx = substr($path, length($filter));\n-\t\t\t\tif ($sfx !~ /^\\/.*\\.git$/) {\n-\t\t\t\t\tnext PROJECT;\n-\t\t\t\t}\n-\t\t\t} elsif ($check_forks) {\n-\t\t\tPATH:\n-\t\t\t\tforeach my $filter (keys %paths) {\n-\t\t\t\t\t# looking for forks;\n-\t\t\t\t\tmy $pfx = substr($path, 0, length($filter));\n-\t\t\t\t\tif ($pfx ne $filter) {\n-\t\t\t\t\t\tnext PATH;\n-\t\t\t\t\t}\n-\t\t\t\t\tmy $sfx = substr($path, length($filter));\n-\t\t\t\t\tif ($sfx !~ /^\\/.*\\.git$/) {\n-\t\t\t\t\t\tnext PATH;\n-\t\t\t\t\t}\n-\t\t\t\t\t# is a fork, don't include it in\n-\t\t\t\t\t# the list\n-\t\t\t\t\tnext PROJECT;\n-\t\t\t\t}\n+\t\t\t# if $filter is rpovided, check if $path begins with $filter\n+\t\t\tif ($filter && $path !~ m!^\\Q$filter\\E/!) {\n+\t\t\t\tnext;\n \t\t\t}\n \t\t\tif (check_export_ok(\"$projectroot/$path\")) {\n \t\t\t\tmy $pr = {\n@@ -2736,8 +2714,6 @@ sub git_get_projects_list {\n \t\t\t\t\towner => to_utf8($owner),\n \t\t\t\t};\n \t\t\t\tpush @list, $pr;\n-\t\t\t\t(my $forks_path = $path) =~ s/\\.git$//;\n-\t\t\t\t$paths{$forks_path}++;\n \t\t\t}\n \t\t}\n \t\tclose $fd;\n@@ -2745,6 +2721,98 @@ sub git_get_projects_list {\n \treturn @list;\n }\n \n+# written with help of Tree::Trie module (Perl Artistic License, GPL compatibile)\n+# as side effects it sets 'forks' field to list of forks for forked projects\n+sub filter_forks_from_projects_list {\n+\tmy $projects = shift;\n+\n+\tmy %trie; # prefix tree of directories (path components)\n+\t# generate trie out of those directories that might contain forks\n+\tforeach my $pr (@$projects) {\n+\t\tmy $path = $pr->{'path'};\n+\t\t$path =~ s/\\.git$//;      # forks of 'repo.git' are in 'repo/' directory\n+\t\tnext if ($path =~ m!/$!); # skip non-bare repositories, e.g. 'repo/.git'\n+\t\tnext unless ($path);      # skip '.git' repository: tests, git-instaweb\n+\t\tnext unless (-d $path);   # containing directory exists\n+\t\t$pr->{'forks'} = [];      # there can be 0 or more forks of project\n+\n+\t\t# add to trie\n+\t\tmy @dirs = split('/', $path);\n+\t\t# walk the trie, until either runs out of components or out of trie\n+\t\tmy $ref = \\%trie;\n+\t\twhile (scalar @dirs &&\n+\t\t       exists($ref->{$dirs[0]})) {\n+\t\t\t$ref = $ref->{shift @dirs};\n+\t\t}\n+\t\t# create rest of trie structure from rest of components\n+\t\tforeach my $dir (@dirs) {\n+\t\t\t$ref = $ref->{$dir} = {};\n+\t\t}\n+\t\t# create end marker, store $pr as a data\n+\t\t$ref->{''} = $pr if (!exists $ref->{''});\n+\t}\n+\n+\t# filter out forks, by finding shortest prefix match for paths\n+\tmy @filtered;\n+ PROJECT:\n+\tforeach my $pr (@$projects) {\n+\t\t# trie lookup\n+\t\tmy $ref = \\%trie;\n+\tDIR:\n+\t\tforeach my $dir (split('/', $pr->{'path'})) {\n+\t\t\tif (exists $ref->{''}) {\n+\t\t\t\t# found [shortest] prefix, is a fork - skip it\n+\t\t\t\tpush @{$ref->{''}{'forks'}}, $pr;\n+\t\t\t\tnext PROJECT;\n+\t\t\t}\n+\t\t\tif (!exists $ref->{$dir}) {\n+\t\t\t\t# not in trie, cannot have prefix, not a fork\n+\t\t\t\tpush @filtered, $pr;\n+\t\t\t\tnext PROJECT;\n+\t\t\t}\n+\t\t\t# If the dir is there, we just walk one step down the trie.\n+\t\t\t$ref = $ref->{$dir};\n+\t\t}\n+\t\t# we ran out of trie\n+\t\t# (shouldn't happen: it's either no match, or end marker)\n+\t\tpush @filtered, $pr;\n+\t}\n+\n+\treturn @filtered;\n+}\n+\n+# note: fill_project_list_info must be run first,\n+# for 'descr_long' and 'ctags' to be filled\n+sub search_projects_list {\n+\tmy ($projlist, %opts) = @_;\n+\tmy $tagfilter  = $opts{'tagfilter'};\n+\tmy $searchtext = $opts{'searchtext'};\n+\n+\treturn @$projlist\n+\t\tunless ($tagfilter || $searchtext);\n+\n+\tmy @projects;\n+ PROJECT:\n+\tforeach my $pr (@$projlist) {\n+\n+\t\tif ($tagfilter) {\n+\t\t\tnext unless ref($pr->{'ctags'}) eq 'HASH';\n+\t\t\tnext unless\n+\t\t\t\tgrep { lc($_) eq lc($tagfilter) } keys %{$pr->{'ctags'}};\n+\t\t}\n+\n+\t\tif ($searchtext) {\n+\t\t\tnext unless\n+\t\t\t\t$pr->{'path'} =~ /$searchtext/ ||\n+\t\t\t\t$pr->{'descr_long'} =~ /$searchtext/;\n+\t\t}\n+\n+\t\tpush @projects, $pr;\n+\t}\n+\n+\treturn @projects;\n+}\n+\n our $gitweb_project_owner = undef;\n sub git_get_project_list_from_file {\n \n@@ -4727,7 +4795,7 @@ sub git_patchset_body {\n # project in the list, removing invalid projects from returned list\n # NOTE: modifies $projlist, but does not remove entries from it\n sub fill_project_list_info {\n-\tmy ($projlist, $check_forks) = @_;\n+\tmy $projlist = shift;\n \tmy @projects;\n \n \tmy $show_ctags = gitweb_check_feature('ctags');\n@@ -4747,23 +4815,36 @@ sub fill_project_list_info {\n \t\tif (!defined $pr->{'owner'}) {\n \t\t\t$pr->{'owner'} = git_get_project_owner(\"$pr->{'path'}\") || \"\";\n \t\t}\n-\t\tif ($check_forks) {\n-\t\t\tmy $pname = $pr->{'path'};\n-\t\t\tif (($pname =~ s/\\.git$//) &&\n-\t\t\t    ($pname !~ /\\/$/) &&\n-\t\t\t    (-d \"$projectroot/$pname\")) {\n-\t\t\t\t$pr->{'forks'} = \"-d $projectroot/$pname\";\n-\t\t\t} else {\n-\t\t\t\t$pr->{'forks'} = 0;\n-\t\t\t}\n+\t\tif ($show_ctags) {\n+\t\t\t$pr->{'ctags'} = git_get_project_ctags($pr->{'path'});\n \t\t}\n-\t\t$show_ctags and $pr->{'ctags'} = git_get_project_ctags($pr->{'path'});\n \t\tpush @projects, $pr;\n \t}\n \n \treturn @projects;\n }\n \n+sub sort_projects_list {\n+\tmy ($projlist, $order) = @_;\n+\tmy @projects;\n+\n+\tmy %order_info = (\n+\t\tproject => { key => 'path', type => 'str' },\n+\t\tdescr => { key => 'descr_long', type => 'str' },\n+\t\towner => { key => 'owner', type => 'str' },\n+\t\tage => { key => 'age', type => 'num' }\n+\t);\n+\tmy $oi = $order_info{$order};\n+\treturn @$projlist unless defined $oi;\n+\tif ($oi->{'type'} eq 'str') {\n+\t\t@projects = sort {$a->{$oi->{'key'}} cmp $b->{$oi->{'key'}}} @$projlist;\n+\t} else {\n+\t\t@projects = sort {$a->{$oi->{'key'}} <=> $b->{$oi->{'key'}}} @$projlist;\n+\t}\n+\n+\treturn @projects;\n+}\n+\n # print 'sort by' <th> element, generating 'sort by $name' replay link\n # if that order is not selected\n sub print_sort_th {\n@@ -4790,28 +4871,39 @@ sub format_sort_th {\n sub git_project_list_body {\n \t# actually uses global variable $project\n \tmy ($projlist, $order, $from, $to, $extra, $no_header) = @_;\n+\tmy @projects = @$projlist;\n \n \tmy $check_forks = gitweb_check_feature('forks');\n-\tmy @projects = fill_project_list_info($projlist, $check_forks);\n+\tmy $show_ctags  = gitweb_check_feature('ctags');\n+\tmy $tagfilter = $show_ctags ? $cgi->param('by_tag') : undef;\n+\t$check_forks = undef\n+\t\tif ($tagfilter || $searchtext);\n+\n+\t# filtering out forks before filling info allows to do less work\n+\t@projects = filter_forks_from_projects_list(\\@projects)\n+\t\tif ($check_forks);\n+\t@projects = fill_project_list_info(\\@projects);\n+\t# searching projects require filling to be run before it\n+\t@projects = search_projects_list(\\@projects,\n+\t                                 'searchtext' => $searchtext,\n+\t                                 'tagfilter'  => $tagfilter)\n+\t\tif ($tagfilter || $searchtext);\n \n \t$order ||= $default_projects_order;\n \t$from = 0 unless defined $from;\n \t$to = $#projects if (!defined $to || $#projects < $to);\n \n-\tmy %order_info = (\n-\t\tproject => { key => 'path', type => 'str' },\n-\t\tdescr => { key => 'descr_long', type => 'str' },\n-\t\towner => { key => 'owner', type => 'str' },\n-\t\tage => { key => 'age', type => 'num' }\n-\t);\n-\tmy $oi = $order_info{$order};\n-\tif ($oi->{'type'} eq 'str') {\n-\t\t@projects = sort {$a->{$oi->{'key'}} cmp $b->{$oi->{'key'}}} @projects;\n-\t} else {\n-\t\t@projects = sort {$a->{$oi->{'key'}} <=> $b->{$oi->{'key'}}} @projects;\n+\t# short circuit\n+\tif ($from > $to) {\n+\t\tprint \"<center>\\n\".\n+\t\t      \"<b>No such projects found</b><br />\\n\".\n+\t\t      \"Click \".$cgi->a({-href=>href(project=>undef)},\"here\").\" to view all projects<br />\\n\".\n+\t\t      \"</center>\\n<br />\\n\";\n+\t\treturn;\n \t}\n \n-\tmy $show_ctags = gitweb_check_feature('ctags');\n+\t@projects = sort_projects_list(\\@projects, $order);\n+\n \tif ($show_ctags) {\n \t\tmy %ctags;\n \t\tforeach my $p (@projects) {\n@@ -4837,32 +4929,26 @@ sub git_project_list_body {\n \t\t      \"</tr>\\n\";\n \t}\n \tmy $alternate = 1;\n-\tmy $tagfilter = $cgi->param('by_tag');\n \tfor (my $i = $from; $i <= $to; $i++) {\n \t\tmy $pr = $projects[$i];\n \n-\t\tnext if $tagfilter and $show_ctags and not grep { lc $_ eq lc $tagfilter } keys %{$pr->{'ctags'}};\n-\t\tnext if $searchtext and not $pr->{'path'} =~ /$searchtext/\n-\t\t\tand not $pr->{'descr_long'} =~ /$searchtext/;\n-\t\t# Weed out forks or non-matching entries of search\n-\t\tif ($check_forks) {\n-\t\t\tmy $forkbase = $project; $forkbase ||= ''; $forkbase =~ s#\\.git$#/#;\n-\t\t\t$forkbase=\"^$forkbase\" if $forkbase;\n-\t\t\tnext if not $searchtext and not $tagfilter and $show_ctags\n-\t\t\t\tand $pr->{'path'} =~ m#$forkbase.*/.*#; # regexp-safe\n-\t\t}\n-\n \t\tif ($alternate) {\n \t\t\tprint \"<tr class=\\\"dark\\\">\\n\";\n \t\t} else {\n \t\t\tprint \"<tr class=\\\"light\\\">\\n\";\n \t\t}\n \t\t$alternate ^= 1;\n+\n \t\tif ($check_forks) {\n \t\t\tprint \"<td>\";\n \t\t\tif ($pr->{'forks'}) {\n-\t\t\t\tprint \"<!-- $pr->{'forks'} -->\\n\";\n-\t\t\t\tprint $cgi->a({-href => href(project=>$pr->{'path'}, action=>\"forks\")}, \"+\");\n+\t\t\t\tmy $nforks = scalar @{$pr->{'forks'}};\n+\t\t\t\tif ($nforks > 0) {\n+\t\t\t\t\tprint $cgi->a({-href => href(project=>$pr->{'path'}, action=>\"forks\"),\n+\t\t\t\t\t               -title => \"$nforks forks\"}, \"+\");\n+\t\t\t\t} else {\n+\t\t\t\t\tprint $cgi->span({-title => \"$nforks forks\"}, \"+\");\n+\t\t\t\t}\n \t\t\t}\n \t\t\tprint \"</td>\\n\";\n \t\t}\n@@ -5343,7 +5429,10 @@ sub git_forks {\n }\n \n sub git_project_index {\n-\tmy @projects = git_get_projects_list($project);\n+\tmy @projects = git_get_projects_list();\n+\tif (!@projects) {\n+\t\tdie_error(404, \"No projects found\");\n+\t}\n \n \tprint $cgi->header(\n \t\t-type => 'text/plain',\n@@ -5385,7 +5474,11 @@ sub git_summary {\n \tmy $check_forks = gitweb_check_feature('forks');\n \n \tif ($check_forks) {\n+\t\t# find forks of a project\n \t\t@forklist = git_get_projects_list($project);\n+\t\t# filter out forks of forks\n+\t\t@forklist = filter_forks_from_projects_list(\\@forklist)\n+\t\t\tif (@forklist);\n \t}\n \n \tgit_header_html();\n@@ -7305,6 +7398,9 @@ sub git_atom {\n \n sub git_opml {\n \tmy @list = git_get_projects_list();\n+\tif (!@list) {\n+\t\tdie_error(404, \"No projects found\");\n+\t}\n \n \tprint $cgi->header(\n \t\t-type => 'text/xml',\ndiff --git a/t/t9500-gitweb-standalone-no-errors.sh b/t/t9500-gitweb-standalone-no-errors.sh\nindex afac5b5..71ef0ac 100755\n--- a/t/t9500-gitweb-standalone-no-errors.sh\n+++ b/t/t9500-gitweb-standalone-no-errors.sh\n@@ -595,4 +595,53 @@ test_expect_success HIGHLIGHT \\\n \t git commit -m \"Add test.sh\" &&\n \t gitweb_run \"p=.git;a=blob;f=test.sh\"'\n \n+# ----------------------------------------------------------------------\n+# forks of projects\n+\n+cat >>gitweb_config.perl <<\\EOF &&\n+$feature{'forks'}{'default'} = [1];\n+EOF\n+\n+test_expect_success \\\n+\t'forks: prepare' \\\n+\t'git init --bare foo.git &&\n+\t git --git-dir=foo.git --work-tree=. add file &&\n+\t git --git-dir=foo.git --work-tree=. commit -m \"Initial commit\" &&\n+\t echo \"foo\" > foo.git/description &&\n+\t mkdir -p foo &&\n+\t (cd foo &&\n+\t  git clone --shared --bare ../foo.git foo-forked.git &&\n+\t  echo \"fork of foo\" > foo-forked.git/description)'\n+\n+test_expect_success \\\n+\t'forks: projects list' \\\n+\t'gitweb_run'\n+\n+test_expect_success \\\n+\t'forks: forks action' \\\n+\t'gitweb_run \"p=foo.git;a=forks\"'\n+\n+# ----------------------------------------------------------------------\n+# content tags (tag cloud)\n+\n+cat >>gitweb_config.perl <<-\\EOF &&\n+# we don't test _setting_ content tags, so any true value is good\n+$feature{'ctags'}{'default'} = ['ctags_script.cgi'];\n+EOF\n+\n+test_expect_success \\\n+\t'ctags: tag cloud in projects list' \\\n+\t'mkdir .git/ctags &&\n+\t echo \"2\" > .git/ctags/foo &&\n+\t echo \"1\" > .git/ctags/bar &&\n+\tgitweb_run'\n+\n+test_expect_success \\\n+\t'ctags: search projects by existing tag' \\\n+\t'gitweb_run \"by_tag=foo\"'\n+\n+test_expect_success \\\n+\t'ctags: search projects by non existent tag' \\\n+\t'gitweb_run \"by_tag=non-existent\"'\n+\n test_done\ndiff --git a/t/t9502-gitweb-standalone-parse-output.sh b/t/t9502-gitweb-standalone-parse-output.sh\nindex dd83890..731e64c 100755\n--- a/t/t9502-gitweb-standalone-parse-output.sh\n+++ b/t/t9502-gitweb-standalone-parse-output.sh\n@@ -112,4 +112,78 @@ test_expect_success 'snapshot: hierarchical branch name (xx/test)' '\n '\n test_debug 'cat gitweb.headers'\n \n+# ----------------------------------------------------------------------\n+# forks of projects\n+\n+test_expect_success 'forks: setup' '\n+\tgit init --bare foo.git &&\n+\techo file > file &&\n+\tgit --git-dir=foo.git --work-tree=. add file &&\n+\tgit --git-dir=foo.git --work-tree=. commit -m \"Initial commit\" &&\n+\techo \"foo\" > foo.git/description &&\n+\tgit clone --bare foo.git foo.bar.git &&\n+\techo \"foo.bar\" > foo.bar.git/description &&\n+\tgit clone --bare foo.git foo_baz.git &&\n+\techo \"foo_baz\" > foo_baz.git/description &&\n+\trm -fr   foo &&\n+\tmkdir -p foo &&\n+\t(\n+\t\tcd foo &&\n+\t\tgit clone --shared --bare ../foo.git foo-forked.git &&\n+\t\techo \"fork of foo\" > foo-forked.git/description\n+\t)\n+'\n+\n+test_expect_success 'forks: not skipped unless \"forks\" feature enabled' '\n+\tgitweb_run \"a=project_list\" &&\n+\tgrep -q \">\\\\.git<\"               gitweb.body &&\n+\tgrep -q \">foo\\\\.git<\"            gitweb.body &&\n+\tgrep -q \">foo_baz\\\\.git<\"        gitweb.body &&\n+\tgrep -q \">foo\\\\.bar\\\\.git<\"      gitweb.body &&\n+\tgrep -q \">foo_baz\\\\.git<\"        gitweb.body &&\n+\tgrep -q \">foo/foo-forked\\\\.git<\" gitweb.body &&\n+\tgrep -q \">fork of .*<\"           gitweb.body\n+'\n+\n+cat >>gitweb_config.perl <<\\EOF &&\n+$feature{'forks'}{'default'} = [1];\n+EOF\n+\n+test_expect_success 'forks: forks skipped if \"forks\" feature enabled' '\n+\tgitweb_run \"a=project_list\" &&\n+\tgrep -q \">\\\\.git<\"               gitweb.body &&\n+\tgrep -q \">foo\\\\.git<\"            gitweb.body &&\n+\tgrep -q \">foo_baz\\\\.git<\"        gitweb.body &&\n+\tgrep -q \">foo\\\\.bar\\\\.git<\"      gitweb.body &&\n+\tgrep -q \">foo_baz\\\\.git<\"        gitweb.body &&\n+\tgrep -v \">foo/foo-forked\\\\.git<\" gitweb.body &&\n+\tgrep -v \">fork of .*<\"           gitweb.body\n+'\n+\n+test_expect_success 'forks: \"forks\" action for forked repository' '\n+\tgitweb_run \"p=foo.git;a=forks\" &&\n+\tgrep -q \">foo/foo-forked\\\\.git<\" gitweb.body &&\n+\tgrep -q \">fork of foo<\"          gitweb.body\n+'\n+\n+test_expect_success 'forks: can access forked repository' '\n+\tgitweb_run \"p=foo/foo-forked.git;a=summary\" &&\n+\tgrep -q \"200 OK\"        gitweb.headers &&\n+\tgrep -q \">fork of foo<\" gitweb.body\n+'\n+\n+test_expect_success 'forks: project_index lists all projects (incl. forks)' '\n+\tcat >expected <<-\\EOF\n+\t.git\n+\tfoo.bar.git\n+\tfoo.git\n+\tfoo/foo-forked.git\n+\tfoo_baz.git\n+\tEOF\n+\tgitweb_run \"a=project_index\" &&\n+\tsed -e \"s/ .*//\" <gitweb.body | sort >actual &&\n+\ttest_cmp expected actual\n+'\n+\n+\n test_done\n-- \n1.7.3\n"}]}