#!/usr/bin/perl

# gitweb - simple web interface to track changes in git repositories
#
# (C) 2005-2006, Kay Sievers <kay.sievers@vrfy.org>
# (C) 2005, Christian Gierke
#
# This program is licensed under the GPLv2

use strict;
use warnings;
use CGI qw(:standard :escapeHTML -nosticky);
use CGI::Util qw(unescape);
use CGI::Carp qw(fatalsToBrowser);
use Encode;
use Fcntl ':mode';
use File::Find qw();
use File::Basename qw(basename);
binmode STDOUT, ':utf8';

our $t0;
if (eval { require Time::HiRes; 1; }) {
	$t0 = [Time::HiRes::gettimeofday()];
}
our $number_of_git_cmds = 0;

BEGIN {
	CGI->compile() if $ENV{'MOD_PERL'};
}

our $cgi = new CGI;
our $version = "++GIT_VERSION++";
our $my_url = $cgi->url();
our $my_uri = $cgi->url(-absolute => 1);

# Base URL for relative URLs in gitweb ($logo, $favicon, ...),
# needed and used only for URLs with nonempty PATH_INFO
our $base_url = $my_url;

# When the script is used as DirectoryIndex, the URL does not contain the name
# of the script file itself, and $cgi->url() fails to strip PATH_INFO, so we
# have to do it ourselves. We make $path_info global because it's also used
# later on.
#
# Another issue with the script being the DirectoryIndex is that the resulting
# $my_url data is not the full script URL: this is good, because we want
# generated links to keep implying the script name if it wasn't explicitly
# indicated in the URL we're handling, but it means that $my_url cannot be used
# as base URL.
# Therefore, if we needed to strip PATH_INFO, then we know that we have
# to build the base URL ourselves:
our $path_info = $ENV{"PATH_INFO"};
if ($path_info) {
	if ($my_url =~ s,\Q$path_info\E$,, &&
	    $my_uri =~ s,\Q$path_info\E$,, &&
	    defined $ENV{'SCRIPT_NAME'}) {
		$base_url = $cgi->url(-base => 1) . $ENV{'SCRIPT_NAME'};
	}
}

# core git executable to use
# this can just be "git" if your webserver has a sensible PATH
our $GIT = "++GIT_BINDIR++/git";

# absolute fs-path which will be prepended to the project path
#our $projectroot = "/pub/scm";
our $projectroot = "++GITWEB_PROJECTROOT++";

# fs traversing limit for getting project list
# the number is relative to the projectroot
our $project_maxdepth = "++GITWEB_PROJECT_MAXDEPTH++";

# target of the home link on top of all pages
our $home_link = $my_uri || "/";

# string of the home link on top of all pages
our $home_link_str = "++GITWEB_HOME_LINK_STR++";

# name of your site or organization to appear in page titles
# replace this with something more descriptive for clearer bookmarks
our $site_name = "++GITWEB_SITENAME++"
                 || ($ENV{'SERVER_NAME'} || "Untitled") . " Git";

# filename of html text to include at top of each page
our $site_header = "++GITWEB_SITE_HEADER++";
# html text to include at home page
our $home_text = "++GITWEB_HOMETEXT++";
# filename of html text to include at bottom of each page
our $site_footer = "++GITWEB_SITE_FOOTER++";

# URI of stylesheets
our @stylesheets = ("++GITWEB_CSS++");
# URI of a single stylesheet, which can be overridden in GITWEB_CONFIG.
our $stylesheet = undef;
# URI of GIT logo (72x27 size)
our $logo = "++GITWEB_LOGO++";
# URI of GIT favicon, assumed to be image/png type
our $favicon = "++GITWEB_FAVICON++";
# URI of gitweb.js (JavaScript code for gitweb)
our $javascript = "++GITWEB_JS++";

# URI and label (title) of GIT logo link
#our $logo_url = "http://www.kernel.org/pub/software/scm/git/docs/";
#our $logo_label = "git documentation";
our $logo_url = "http://git-scm.com/";
our $logo_label = "git homepage";

# source of projects list
our $projects_list = "++GITWEB_LIST++";

# the width (in characters) of the projects list "Description" column
our $projects_list_description_width = 25;

# default order of projects list
# valid values are none, project, descr, owner, and age
our $default_projects_order = "project";

# show repository only if this file exists
# (only effective if this variable evaluates to true)
our $export_ok = "++GITWEB_EXPORT_OK++";

# show repository only if this subroutine returns true
# when given the path to the project, for example:
#    sub { return -e "$_[0]/git-daemon-export-ok"; }
our $export_auth_hook = undef;

# only allow viewing of repositories also shown on the overview page
our $strict_export = "++GITWEB_STRICT_EXPORT++";

# list of git base URLs used for URL to where fetch project from,
# i.e. full URL is "$git_base_url/$project"
our @git_base_url_list = grep { $_ ne '' } ("++GITWEB_BASE_URL++");

# default blob_plain mimetype and default charset for text/plain blob
our $default_blob_plain_mimetype = 'text/plain';
our $default_text_plain_charset  = undef;

# file to use for guessing MIME types before trying /etc/mime.types
# (relative to the current git repository)
our $mimetypes_file = undef;

# assume this charset if line contains non-UTF-8 characters;
# it should be valid encoding (see Encoding::Supported(3pm) for list),
# for which encoding all byte sequences are valid, for example
# 'iso-8859-1' aka 'latin1' (it is decoded without checking, so it
# could be even 'utf-8' for the old behavior)
our $fallback_encoding = 'latin1';

# rename detection options for git-diff and git-diff-tree
# - default is '-M', with the cost proportional to
#   (number of removed files) * (number of new files).
# - more costly is '-C' (which implies '-M'), with the cost proportional to
#   (number of changed files + number of removed files) * (number of new files)
# - even more costly is '-C', '--find-copies-harder' with cost
#   (number of files in the original tree) * (number of new files)
# - one might want to include '-B' option, e.g. '-B', '-M'
our @diff_opts = ('-M'); # taken from git_commit

# Disables features that would allow repository owners to inject script into
# the gitweb domain.
our $prevent_xss = 0;

# information about snapshot formats that gitweb is capable of serving
our %known_snapshot_formats = (
	# name => {
	# 	'display' => display name,
	# 	'type' => mime type,
	# 	'suffix' => filename suffix,
	# 	'format' => --format for git-archive,
	# 	'compressor' => [compressor command and arguments]
	# 	                (array reference, optional)
	# 	'disabled' => boolean (optional)}
	#
	'tgz' => {
		'display' => 'tar.gz',
		'type' => 'application/x-gzip',
		'suffix' => '.tar.gz',
		'format' => 'tar',
		'compressor' => ['gzip']},

	'tbz2' => {
		'display' => 'tar.bz2',
		'type' => 'application/x-bzip2',
		'suffix' => '.tar.bz2',
		'format' => 'tar',
		'compressor' => ['bzip2']},

	'txz' => {
		'display' => 'tar.xz',
		'type' => 'application/x-xz',
		'suffix' => '.tar.xz',
		'format' => 'tar',
		'compressor' => ['xz'],
		'disabled' => 1},

	'zip' => {
		'display' => 'zip',
		'type' => 'application/x-zip',
		'suffix' => '.zip',
		'format' => 'zip'},
);

# Aliases so we understand old gitweb.snapshot values in repository
# configuration.
our %known_snapshot_format_aliases = (
	'gzip'  => 'tgz',
	'bzip2' => 'tbz2',
	'xz'    => 'txz',

	# backward compatibility: legacy gitweb config support
	'x-gzip' => undef, 'gz' => undef,
	'x-bzip2' => undef, 'bz2' => undef,
	'x-zip' => undef, '' => undef,
);

# Pixel sizes for icons and avatars. If the default font sizes or lineheights
# are changed, it may be appropriate to change these values too via
# $GITWEB_CONFIG.
our %avatar_size = (
	'default' => 16,
	'double'  => 32
);

# Used to set the maximum load that we will still respond to gitweb queries.
# If server load exceed this value then return "503 server busy" error.
# If gitweb cannot determined server load, it is taken to be 0.
# Leave it undefined (or set to 'undef') to turn off load checking.
our $maxload = 300;

# You define site-wide feature defaults here; override them with
# $GITWEB_CONFIG as necessary.
our %feature = (
	# feature => {
	# 	'sub' => feature-sub (subroutine),
	# 	'override' => allow-override (boolean),
	# 	'default' => [ default options...] (array reference)}
	#
	# if feature is overridable (it means that allow-override has true value),
	# then feature-sub will be called with default options as parameters;
	# return value of feature-sub indicates if to enable specified feature
	#
	# if there is no 'sub' key (no feature-sub), then feature cannot be
	# overriden
	#
	# use gitweb_get_feature(<feature>) to retrieve the <feature> value
	# (an array) or gitweb_check_feature(<feature>) to check if <feature>
	# is enabled

	# Enable the 'blame' blob view, showing the last commit that modified
	# each line in the file. This can be very CPU-intensive.

	# To enable system wide have in $GITWEB_CONFIG
	# $feature{'blame'}{'default'} = [1];
	# To have project specific config enable override in $GITWEB_CONFIG
	# $feature{'blame'}{'override'} = 1;
	# and in project config gitweb.blame = 0|1;
	'blame' => {
		'sub' => sub { feature_bool('blame', @_) },
		'override' => 0,
		'default' => [0]},

	# Enable the 'snapshot' link, providing a compressed archive of any
	# tree. This can potentially generate high traffic if you have large
	# project.

	# Value is a list of formats defined in %known_snapshot_formats that
	# you wish to offer.
	# To disable system wide have in $GITWEB_CONFIG
	# $feature{'snapshot'}{'default'} = [];
	# To have project specific config enable override in $GITWEB_CONFIG
	# $feature{'snapshot'}{'override'} = 1;
	# and in project config, a comma-separated list of formats or "none"
	# to disable.  Example: gitweb.snapshot = tbz2,zip;
	'snapshot' => {
		'sub' => \&feature_snapshot,
		'override' => 0,
		'default' => ['tgz']},

	# Enable text search, which will list the commits which match author,
	# committer or commit text to a given string.  Enabled by default.
	# Project specific override is not supported.
	'search' => {
		'override' => 0,
		'default' => [1]},

	# Enable grep search, which will list the files in currently selected
	# tree containing the given string. Enabled by default. This can be
	# potentially CPU-intensive, of course.

	# To enable system wide have in $GITWEB_CONFIG
	# $feature{'grep'}{'default'} = [1];
	# To have project specific config enable override in $GITWEB_CONFIG
	# $feature{'grep'}{'override'} = 1;
	# and in project config gitweb.grep = 0|1;
	'grep' => {
		'sub' => sub { feature_bool('grep', @_) },
		'override' => 0,
		'default' => [1]},

	# Enable the pickaxe search, which will list the commits that modified
	# a given string in a file. This can be practical and quite faster
	# alternative to 'blame', but still potentially CPU-intensive.

	# To enable system wide have in $GITWEB_CONFIG
	# $feature{'pickaxe'}{'default'} = [1];
	# To have project specific config enable override in $GITWEB_CONFIG
	# $feature{'pickaxe'}{'override'} = 1;
	# and in project config gitweb.pickaxe = 0|1;
	'pickaxe' => {
		'sub' => sub { feature_bool('pickaxe', @_) },
		'override' => 0,
		'default' => [1]},

	# Enable showing size of blobs in a 'tree' view, in a separate
	# column, similar to what 'ls -l' does.  This cost a bit of IO.

	# To disable system wide have in $GITWEB_CONFIG
	# $feature{'show-sizes'}{'default'} = [0];
	# To have project specific config enable override in $GITWEB_CONFIG
	# $feature{'show-sizes'}{'override'} = 1;
	# and in project config gitweb.showsizes = 0|1;
	'show-sizes' => {
		'sub' => sub { feature_bool('showsizes', @_) },
		'override' => 0,
		'default' => [1]},

	# Make gitweb use an alternative format of the URLs which can be
	# more readable and natural-looking: project name is embedded
	# directly in the path and the query string contains other
	# auxiliary information. All gitweb installations recognize
	# URL in either format; this configures in which formats gitweb
	# generates links.

	# To enable system wide have in $GITWEB_CONFIG
	# $feature{'pathinfo'}{'default'} = [1];
	# Project specific override is not supported.

	# Note that you will need to change the default location of CSS,
	# favicon, logo and possibly other files to an absolute URL. Also,
	# if gitweb.cgi serves as your indexfile, you will need to force
	# $my_uri to contain the script name in your $GITWEB_CONFIG.
	'pathinfo' => {
		'override' => 0,
		'default' => [0]},

	# Make gitweb consider projects in project root subdirectories
	# to be forks of existing projects. Given project $projname.git,
	# projects matching $projname/*.git will not be shown in the main
	# projects list, instead a '+' mark will be added to $projname
	# there and a 'forks' view will be enabled for the project, listing
	# all the forks. If project list is taken from a file, forks have
	# to be listed after the main project.

	# To enable system wide have in $GITWEB_CONFIG
	# $feature{'forks'}{'default'} = [1];
	# Project specific override is not supported.
	'forks' => {
		'override' => 0,
		'default' => [0]},

	# Insert custom links to the action bar of all project pages.
	# This enables you mainly to link to third-party scripts integrating
	# into gitweb; e.g. git-browser for graphical history representation
	# or custom web-based repository administration interface.

	# The 'default' value consists of a list of triplets in the form
	# (label, link, position) where position is the label after which
	# to insert the link and link is a format string where %n expands
	# to the project name, %f to the project path within the filesystem,
	# %h to the current hash (h gitweb parameter) and %b to the current
	# hash base (hb gitweb parameter); %% expands to %.

	# To enable system wide have in $GITWEB_CONFIG e.g.
	# $feature{'actions'}{'default'} = [('graphiclog',
	# 	'/git-browser/by-commit.html?r=%n', 'summary')];
	# Project specific override is not supported.
	'actions' => {
		'override' => 0,
		'default' => []},

	# Allow gitweb scan project content tags described in ctags/
	# of project repository, and display the popular Web 2.0-ish
	# "tag cloud" near the project list. Note that this is something
	# COMPLETELY different from the normal Git tags.

	# gitweb by itself can show existing tags, but it does not handle
	# tagging itself; you need an external application for that.
	# For an example script, check Girocco's cgi/tagproj.cgi.
	# You may want to install the HTML::TagCloud Perl module to get
	# a pretty tag cloud instead of just a list of tags.

	# To enable system wide have in $GITWEB_CONFIG
	# $feature{'ctags'}{'default'} = ['path_to_tag_script'];
	# Project specific override is not supported.
	'ctags' => {
		'override' => 0,
		'default' => [0]},

	# The maximum number of patches in a patchset generated in patch
	# view. Set this to 0 or undef to disable patch view, or to a
	# negative number to remove any limit.

	# To disable system wide have in $GITWEB_CONFIG
	# $feature{'patches'}{'default'} = [0];
	# To have project specific config enable override in $GITWEB_CONFIG
	# $feature{'patches'}{'override'} = 1;
	# and in project config gitweb.patches = 0|n;
	# where n is the maximum number of patches allowed in a patchset.
	'patches' => {
		'sub' => \&feature_patches,
		'override' => 0,
		'default' => [16]},

	# Avatar support. When this feature is enabled, views such as
	# shortlog or commit will display an avatar associated with
	# the email of the committer(s) and/or author(s).

	# Currently available providers are gravatar and picon.
	# If an unknown provider is specified, the feature is disabled.

	# Gravatar depends on Digest::MD5.
	# Picon currently relies on the indiana.edu database.

	# To enable system wide have in $GITWEB_CONFIG
	# $feature{'avatar'}{'default'} = ['<provider>'];
	# where <provider> is either gravatar or picon.
	# To have project specific config enable override in $GITWEB_CONFIG
	# $feature{'avatar'}{'override'} = 1;
	# and in project config gitweb.avatar = <provider>;
	'avatar' => {
		'sub' => \&feature_avatar,
		'override' => 0,
		'default' => ['']},

	# Enable displaying how much time and how many git commands
	# it took to generate and display page.  Disabled by default.
	# Project specific override is not supported.
	'timed' => {
		'override' => 0,
		'default' => [0]},

	# Enable turning some links into links to actions which require
	# JavaScript to run (like 'blame_incremental').  Not enabled by
	# default.  Project specific override is currently not supported.
	'javascript-actions' => {
		'override' => 0,
		'default' => [0]},
);

sub gitweb_get_feature {
	my ($name) = @_;
	return unless exists $feature{$name};
	my ($sub, $override, @defaults) = (
		$feature{$name}{'sub'},
		$feature{$name}{'override'},
		@{$feature{$name}{'default'}});
	# project specific override is possible only if we have project
	our $git_dir; # global variable, declared later
	if (!$override || !defined $git_dir) {
		return @defaults;
	}
	if (!defined $sub) {
		warn "feature $name is not overridable";
		return @defaults;
	}
	return $sub->(@defaults);
}

# A wrapper to check if a given feature is enabled.
# With this, you can say
#
#   my $bool_feat = gitweb_check_feature('bool_feat');
#   gitweb_check_feature('bool_feat') or somecode;
#
# instead of
#
#   my ($bool_feat) = gitweb_get_feature('bool_feat');
#   (gitweb_get_feature('bool_feat'))[0] or somecode;
#
sub gitweb_check_feature {
	return (gitweb_get_feature(@_))[0];
}


sub feature_bool {
	my $key = shift;
	my ($val) = git_get_project_config($key, '--bool');

	if (!defined $val) {
		return ($_[0]);
	} elsif ($val eq 'true') {
		return (1);
	} elsif ($val eq 'false') {
		return (0);
	}
}

sub feature_snapshot {
	my (@fmts) = @_;

	my ($val) = git_get_project_config('snapshot');

	if ($val) {
		@fmts = ($val eq 'none' ? () : split /\s*[,\s]\s*/, $val);
	}

	return @fmts;
}

sub feature_patches {
	my @val = (git_get_project_config('patches', '--int'));

	if (@val) {
		return @val;
	}

	return ($_[0]);
}

sub feature_avatar {
	my @val = (git_get_project_config('avatar'));

	return @val ? @val : @_;
}

# checking HEAD file with -e is fragile if the repository was
# initialized long time ago (i.e. symlink HEAD) and was pack-ref'ed
# and then pruned.
sub check_head_link {
	my ($dir) = @_;
	my $headfile = "$dir/HEAD";
	return ((-e $headfile) ||
		(-l $headfile && readlink($headfile) =~ /^refs\/heads\//));
}

sub check_export_ok {
	my ($dir) = @_;
	return (check_head_link($dir) &&
		(!$export_ok || -e "$dir/$export_ok") &&
		(!$export_auth_hook || $export_auth_hook->($dir)));
}

# process alternate names for backward compatibility
# filter out unsupported (unknown) snapshot formats
sub filter_snapshot_fmts {
	my @fmts = @_;

	@fmts = map {
		exists $known_snapshot_format_aliases{$_} ?
		       $known_snapshot_format_aliases{$_} : $_} @fmts;
	@fmts = grep {
		exists $known_snapshot_formats{$_} &&
		!$known_snapshot_formats{$_}{'disabled'}} @fmts;
}

our $GITWEB_CONFIG = $ENV{'GITWEB_CONFIG'} || "++GITWEB_CONFIG++";
our $GITWEB_CONFIG_SYSTEM = $ENV{'GITWEB_CONFIG_SYSTEM'} || "++GITWEB_CONFIG_SYSTEM++";
# die if there are errors parsing config file
if (-e $GITWEB_CONFIG) {
	do $GITWEB_CONFIG;
	die $@ if $@;
} elsif (-e $GITWEB_CONFIG_SYSTEM) {
	do $GITWEB_CONFIG_SYSTEM;
	die $@ if $@;
}

# Get loadavg of system, to compare against $maxload.
# Currently it requires '/proc/loadavg' present to get loadavg;
# if it is not present it returns 0, which means no load checking.
sub get_loadavg {
	if( -e '/proc/loadavg' ){
		open my $fd, '<', '/proc/loadavg'
			or return 0;
		my @load = split(/\s+/, scalar <$fd>);
		close $fd;

		# The first three columns measure CPU and IO utilization of the last one,
		# five, and 10 minute periods.  The fourth column shows the number of
		# currently running processes and the total number of processes in the m/n
		# format.  The last column displays the last process ID used.
		return $load[0] || 0;
	}
	# additional checks for load average should go here for things that don't export
	# /proc/loadavg

	return 0;
}

# version of the core git binary
our $git_version = qx("$GIT" --version) =~ m/git version (.*)$/ ? $1 : "unknown";
$number_of_git_cmds++;

$projects_list ||= $projectroot;

if (defined $maxload && get_loadavg() > $maxload) {
	die_error(503, "The load average on the server is too high");
}

# ======================================================================
# input validation and dispatch

# input parameters can be collected from a variety of sources (presently, CGI
# and PATH_INFO), so we define an %input_params hash that collects them all
# together during validation: this allows subsequent uses (e.g. href()) to be
# agnostic of the parameter origin

our %input_params = ();

# input parameters are stored with the long parameter name as key. This will
# also be used in the href subroutine to convert parameters to their CGI
# equivalent, and since the href() usage is the most frequent one, we store
# the name -> CGI key mapping here, instead of the reverse.
#
# XXX: Warning: If you touch this, check the search form for updating,
# too.

our @cgi_param_mapping = (
	project => "p",
	action => "a",
	file_name => "f",
	file_parent => "fp",
	hash => "h",
	hash_parent => "hp",
	hash_base => "hb",
	hash_parent_base => "hpb",
	page => "pg",
	order => "o",
	searchtext => "s",
	searchtype => "st",
	snapshot_format => "sf",
	extra_options => "opt",
	search_use_regexp => "sr",
	# this must be last entry (for manipulation from JavaScript)
	javascript => "js"
);
our %cgi_param_mapping = @cgi_param_mapping;

# we will also need to know the possible actions, for validation
our %actions = (
	"blame" => \&git_blame,
	"blame_incremental" => \&git_blame_incremental,
	"blame_data" => \&git_blame_data,
	"blobdiff" => \&git_blobdiff,
	"blobdiff_plain" => \&git_blobdiff_plain,
	"blob" => \&git_blob,
	"blob_plain" => \&git_blob_plain,
	"commitdiff" => \&git_commitdiff,
	"commitdiff_plain" => \&git_commitdiff_plain,
	"commit" => \&git_commit,
	"forks" => \&git_forks,
	"heads" => \&git_heads,
	"history" => \&git_history,
	"log" => \&git_log,
	"patch" => \&git_patch,
	"patches" => \&git_patches,
	"rss" => \&git_rss,
	"atom" => \&git_atom,
	"search" => \&git_search,
	"search_help" => \&git_search_help,
	"shortlog" => \&git_shortlog,
	"summary" => \&git_summary,
	"tag" => \&git_tag,
	"tags" => \&git_tags,
	"tree" => \&git_tree,
	"snapshot" => \&git_snapshot,
	"object" => \&git_object,
	# those below don't need $project
	"opml" => \&git_opml,
	"project_list" => \&git_project_list,
	"project_index" => \&git_project_index,
);

# finally, we have the hash of allowed extra_options for the commands that
# allow them
our %allowed_options = (
	"--no-merges" => [ qw(rss atom log shortlog history) ],
);

# fill %input_params with the CGI parameters. All values except for 'opt'
# should be single values, but opt can be an array. We should probably
# build an array of parameters that can be multi-valued, but since for the time
# being it's only this one, we just single it out
while (my ($name, $symbol) = each %cgi_param_mapping) {
	if ($symbol eq 'opt') {
		$input_params{$name} = [ $cgi->param($symbol) ];
	} else {
		$input_params{$name} = $cgi->param($symbol);
	}
}

# now read PATH_INFO and update the parameter list for missing parameters
sub evaluate_path_info {
	return if defined $input_params{'project'};
	return if !$path_info;
	$path_info =~ s,^/+,,;
	return if !$path_info;

	# find which part of PATH_INFO is project
	my $project = $path_info;
	$project =~ s,/+$,,;
	while ($project && !check_head_link("$projectroot/$project")) {
		$project =~ s,/*[^/]*$,,;
	}
	return unless $project;
	$input_params{'project'} = $project;

	# do not change any parameters if an action is given using the query string
	return if $input_params{'action'};
	$path_info =~ s,^\Q$project\E/*,,;

	# next, check if we have an action
	my $action = $path_info;
	$action =~ s,/.*$,,;
	if (exists $actions{$action}) {
		$path_info =~ s,^$action/*,,;
		$input_params{'action'} = $action;
	}

	# list of actions that want hash_base instead of hash, but can have no
	# pathname (f) parameter
	my @wants_base = (
		'tree',
		'history',
	);

	# we want to catch
	# [$hash_parent_base[:$file_parent]..]$hash_parent[:$file_name]
	my ($parentrefname, $parentpathname, $refname, $pathname) =
		($path_info =~ /^(?:(.+?)(?::(.+))?\.\.)?(.+?)(?::(.+))?$/);

	# first, analyze the 'current' part
	if (defined $pathname) {
		# we got "branch:filename" or "branch:dir/"
		# we could use git_get_type(branch:pathname), but:
		# - it needs $git_dir
		# - it does a git() call
		# - the convention of terminating directories with a slash
		#   makes it superfluous
		# - embedding the action in the PATH_INFO would make it even
		#   more superfluous
		$pathname =~ s,^/+,,;
		if (!$pathname || substr($pathname, -1) eq "/") {
			$input_params{'action'} ||= "tree";
			$pathname =~ s,/$,,;
		} else {
			# the default action depends on whether we had parent info
			# or not
			if ($parentrefname) {
				$input_params{'action'} ||= "blobdiff_plain";
			} else {
				$input_params{'action'} ||= "blob_plain";
			}
		}
		$input_params{'hash_base'} ||= $refname;
		$input_params{'file_name'} ||= $pathname;
	} elsif (defined $refname) {
		# we got "branch". In this case we have to choose if we have to
		# set hash or hash_base.
		#
		# Most of the actions without a pathname only want hash to be
		# set, except for the ones specified in @wants_base that want
		# hash_base instead. It should also be noted that hand-crafted
		# links having 'history' as an action and no pathname or hash
		# set will fail, but that happens regardless of PATH_INFO.
		$input_params{'action'} ||= "shortlog";
		if (grep { $_ eq $input_params{'action'} } @wants_base) {
			$input_params{'hash_base'} ||= $refname;
		} else {
			$input_params{'hash'} ||= $refname;
		}
	}

	# next, handle the 'parent' part, if present
	if (defined $parentrefname) {
		# a missing pathspec defaults to the 'current' filename, allowing e.g.
		# someproject/blobdiff/oldrev..newrev:/filename
		if ($parentpathname) {
			$parentpathname =~ s,^/+,,;
			$parentpathname =~ s,/$,,;
			$input_params{'file_parent'} ||= $parentpathname;
		} else {
			$input_params{'file_parent'} ||= $input_params{'file_name'};
		}
		# we assume that hash_parent_base is wanted if a path was specified,
		# or if the action wants hash_base instead of hash
		if (defined $input_params{'file_parent'} ||
			grep { $_ eq $input_params{'action'} } @wants_base) {
			$input_params{'hash_parent_base'} ||= $parentrefname;
		} else {
			$input_params{'hash_parent'} ||= $parentrefname;
		}
	}

	# for the snapshot action, we allow URLs in the form
	# $project/snapshot/$hash.ext
	# where .ext determines the snapshot and gets removed from the
	# passed $refname to provide the $hash.
	#
	# To be able to tell that $refname includes the format extension, we
	# require the following two conditions to be satisfied:
	# - the hash input parameter MUST have been set from the $refname part
	#   of the URL (i.e. they must be equal)
	# - the snapshot format MUST NOT have been defined already (e.g. from
	#   CGI parameter sf)
	# It's also useless to try any matching unless $refname has a dot,
	# so we check for that too
	if (defined $input_params{'action'} &&
		$input_params{'action'} eq 'snapshot' &&
		defined $refname && index($refname, '.') != -1 &&
		$refname eq $input_params{'hash'} &&
		!defined $input_params{'snapshot_format'}) {
		# We loop over the known snapshot formats, checking for
		# extensions. Allowed extensions are both the defined suffix
		# (which includes the initial dot already) and the snapshot
		# format key itself, with a prepended dot
		while (my ($fmt, $opt) = each %known_snapshot_formats) {
			my $hash = $refname;
			unless ($hash =~ s/(\Q$opt->{'suffix'}\E|\Q.$fmt\E)$//) {
				next;
			}
			my $sfx = $1;
			# a valid suffix was found, so set the snapshot format
			# and reset the hash parameter
			$input_params{'snapshot_format'} = $fmt;
			$input_params{'hash'} = $hash;
			# we also set the format suffix to the one requested
			# in the URL: this way a request for e.g. .tgz returns
			# a .tgz instead of a .tar.gz
			$known_snapshot_formats{$fmt}{'suffix'} = $sfx;
			last;
		}
	}
}
evaluate_path_info();

our $action = $input_params{'action'};
if (defined $action) {
	if (!validate_action($action)) {
		die_error(400, "Invalid action parameter");
	}
}

# parameters which are pathnames
our $project = $input_params{'project'};
if (defined $project) {
	if (!validate_project($project)) {
		undef $project;
		die_error(404, "No such project");
	}
}

our $file_name = $input_params{'file_name'};
if (defined $file_name) {
	if (!validate_pathname($file_name)) {
		die_error(400, "Invalid file parameter");
	}
}

our $file_parent = $input_params{'file_parent'};
if (defined $file_parent) {
	if (!validate_pathname($file_parent)) {
		die_error(400, "Invalid file parent parameter");
	}
}

# parameters which are refnames
our $hash = $input_params{'hash'};
if (defined $hash) {
	if (!validate_refname($hash)) {
		die_error(400, "Invalid hash parameter");
	}
}

our $hash_parent = $input_params{'hash_parent'};
if (defined $hash_parent) {
	if (!validate_refname($hash_parent)) {
		die_error(400, "Invalid hash parent parameter");
	}
}

our $hash_base = $input_params{'hash_base'};
if (defined $hash_base) {
	if (!validate_refname($hash_base)) {
		die_error(400, "Invalid hash base parameter");
	}
}

our @extra_options = @{$input_params{'extra_options'}};
# @extra_options is always defined, since it can only be (currently) set from
# CGI, and $cgi->param() returns the empty array in array context if the param
# is not set
foreach my $opt (@extra_options) {
	if (not exists $allowed_options{$opt}) {
		die_error(400, "Invalid option parameter");
	}
	if (not grep(/^$action$/, @{$allowed_options{$opt}})) {
		die_error(400, "Invalid option parameter for this action");
	}
}

our $hash_parent_base = $input_params{'hash_parent_base'};
if (defined $hash_parent_base) {
	if (!validate_refname($hash_parent_base)) {
		die_error(400, "Invalid hash parent base parameter");
	}
}

# other parameters
our $page = $input_params{'page'};
if (defined $page) {
	if ($page =~ m/[^0-9]/) {
		die_error(400, "Invalid page parameter");
	}
}

our $searchtype = $input_params{'searchtype'};
if (defined $searchtype) {
	if ($searchtype =~ m/[^a-z]/) {
		die_error(400, "Invalid searchtype parameter");
	}
}

our $search_use_regexp = $input_params{'search_use_regexp'};

our $searchtext = $input_params{'searchtext'};
our $search_regexp;
if (defined $searchtext) {
	if (length($searchtext) < 2) {
		die_error(403, "At least two characters are required for search parameter");
	}
	$search_regexp = $search_use_regexp ? $searchtext : quotemeta $searchtext;
}

# path to the current git repository
our $git_dir;
$git_dir = "$projectroot/$project" if $project;

# list of supported snapshot formats
our @snapshot_fmts = gitweb_get_feature('snapshot');
@snapshot_fmts = filter_snapshot_fmts(@snapshot_fmts);

# check that the avatar feature is set to a known provider name,
# and for each provider check if the dependencies are satisfied.
# if the provider name is invalid or the dependencies are not met,
# reset $git_avatar to the empty string.
our ($git_avatar) = gitweb_get_feature('avatar');
if ($git_avatar eq 'gravatar') {
	$git_avatar = '' unless (eval { require Digest::MD5; 1; });
} elsif ($git_avatar eq 'picon') {
	# no dependencies
} else {
	$git_avatar = '';
}

# dispatch
if (!defined $action) {
	if (defined $hash) {
		$action = git_get_type($hash);
	} elsif (defined $hash_base && defined $file_name) {
		$action = git_get_type("$hash_base:$file_name");
	} elsif (defined $project) {
		$action = 'summary';
	} else {
		$action = 'project_list';
	}
}
if (!defined($actions{$action})) {
	die_error(400, "Unknown action");
}
if ($action !~ m/^(?:opml|project_list|project_index)$/ &&
    !$project) {
	die_error(400, "Project needed");
}
$actions{$action}->();
exit;

## ======================================================================
## action links

sub href {
	my %params = @_;
	# default is to use -absolute url() i.e. $my_uri
	my $href = $params{-full} ? $my_url : $my_uri;

	$params{'project'} = $project unless exists $params{'project'};

	if ($params{-replay}) {
		while (my ($name, $symbol) = each %cgi_param_mapping) {
			if (!exists $params{$name}) {
				$params{$name} = $input_params{$name};
			}
		}
	}

	my $use_pathinfo = gitweb_check_feature('pathinfo');
	if ($use_pathinfo and defined $params{'project'}) {
		# try to put as many parameters as possible in PATH_INFO:
		#   - project name
		#   - action
		#   - hash_parent or hash_parent_base:/file_parent
		#   - hash or hash_base:/filename
		#   - the snapshot_format as an appropriate suffix

		# When the script is the root DirectoryIndex for the domain,
		# $href here would be something like http://gitweb.example.com/
		# Thus, we strip any trailing / from $href, to spare us double
		# slashes in the final URL
		$href =~ s,/$,,;

		# Then add the project name, if present
		$href .= "/".esc_url($params{'project'});
		delete $params{'project'};

		# since we destructively absorb parameters, we keep this
		# boolean that remembers if we're handling a snapshot
		my $is_snapshot = $params{'action'} eq 'snapshot';

		# Summary just uses the project path URL, any other action is
		# added to the URL
		if (defined $params{'action'}) {
			$href .= "/".esc_url($params{'action'}) unless $params{'action'} eq 'summary';
			delete $params{'action'};
		}

		# Next, we put hash_parent_base:/file_parent..hash_base:/file_name,
		# stripping nonexistent or useless pieces
		$href .= "/" if ($params{'hash_base'} || $params{'hash_parent_base'}
			|| $params{'hash_parent'} || $params{'hash'});
		if (defined $params{'hash_base'}) {
			if (defined $params{'hash_parent_base'}) {
				$href .= esc_url($params{'hash_parent_base'});
				# skip the file_parent if it's the same as the file_name
				if (defined $params{'file_parent'}) {
					if (defined $params{'file_name'} && $params{'file_parent'} eq $params{'file_name'}) {
						delete $params{'file_parent'};
					} elsif ($params{'file_parent'} !~ /\.\./) {
						$href .= ":/".esc_url($params{'file_parent'});
						delete $params{'file_parent'};
					}
				}
				$href .= "..";
				delete $params{'hash_parent'};
				delete $params{'hash_parent_base'};
			} elsif (defined $params{'hash_parent'}) {
				$href .= esc_url($params{'hash_parent'}). "..";
				delete $params{'hash_parent'};
			}

			$href .= esc_url($params{'hash_base'});
			if (defined $params{'file_name'} && $params{'file_name'} !~ /\.\./) {
				$href .= ":/".esc_url($params{'file_name'});
				delete $params{'file_name'};
			}
			delete $params{'hash'};
			delete $params{'hash_base'};
		} elsif (defined $params{'hash'}) {
			$href .= esc_url($params{'hash'});
			delete $params{'hash'};
		}

		# If the action was a snapshot, we can absorb the
		# snapshot_format parameter too
		if ($is_snapshot) {
			my $fmt = $params{'snapshot_format'};
			# snapshot_format should always be defined when href()
			# is called, but just in case some code forgets, we
			# fall back to the default
			$fmt ||= $snapshot_fmts[0];
			$href .= $known_snapshot_formats{$fmt}{'suffix'};
			delete $params{'snapshot_format'};
		}
	}

	# now encode the parameters explicitly
	my @result = ();
	for (my $i = 0; $i < @cgi_param_mapping; $i += 2) {
		my ($name, $symbol) = ($cgi_param_mapping[$i], $cgi_param_mapping[$i+1]);
		if (defined $params{$name}) {
			if (ref($params{$name}) eq "ARRAY") {
				foreach my $par (@{$params{$name}}) {
					push @result, $symbol . "=" . esc_param($par);
				}
			} else {
				push @result, $symbol . "=" . esc_param($params{$name});
			}
		}
	}
	$href .= "?" . join(';', @result) if scalar @result;

	return $href;
}


## ======================================================================
## validation, quoting/unquoting and escaping

sub validate_action {
	my $input = shift || return undef;
	return undef unless exists $actions{$input};
	return $input;
}

sub validate_project {
	my $input = shift || return undef;
	if (!validate_pathname($input) ||
		!(-d "$projectroot/$input") ||
		!check_export_ok("$projectroot/$input") ||
		($strict_export && !project_in_list($input))) {
		return undef;
	} else {
		return $input;
	}
}

sub validate_pathname {
	my $input = shift || return undef;

	# no '.' or '..' as elements of path, i.e. no '.' nor '..'
	# at the beginning, at the end, and between slashes.
	# also this catches doubled slashes
	if ($input =~ m!(^|/)(|\.|\.\.)(/|$)!) {
		return undef;
	}
	# no null characters
	if ($input =~ m!\0!) {
		return undef;
	}
	return $input;
}

sub validate_refname {
	my $input = shift || return undef;

	# textual hashes are O.K.
	if ($input =~ m/^[0-9a-fA-F]{40}$/) {
		return $input;
	}
	# it must be correct pathname
	$input = validate_pathname($input)
		or return undef;
	# restrictions on ref name according to git-check-ref-format
	if ($input =~ m!(/\.|\.\.|[\000-\040\177 ~^:?*\[]|/$)!) {
		return undef;
	}
	return $input;
}

# decode sequences of octets in utf8 into Perl's internal form,
# which is utf-8 with utf8 flag set if needed.  gitweb writes out
# in utf-8 thanks to "binmode STDOUT, ':utf8'" at beginning
sub to_utf8 {
	my $str = shift;
	return undef unless defined $str;
	if (utf8::valid($str)) {
		utf8::decode($str);
		return $str;
	} else {
		return decode($fallback_encoding, $str, Encode::FB_DEFAULT);
	}
}

# quote unsafe chars, but keep the slash, even when it's not
# correct, but quoted slashes look too horrible in bookmarks
sub esc_param {
	my $str = shift;
	return undef unless defined $str;
	$str =~ s/([^A-Za-z0-9\-_.~()\/:@ ]+)/CGI::escape($1)/eg;
	$str =~ s/ /\+/g;
	return $str;
}

# quote unsafe chars in whole URL, so some charactrs cannot be quoted
sub esc_url {
	my $str = shift;
	return undef unless defined $str;
	$str =~ s/([^A-Za-z0-9\-_.~();\/;?:@&=])/sprintf("%%%02X", ord($1))/eg;
	$str =~ s/\+/%2B/g;
	$str =~ s/ /\+/g;
	return $str;
}

# replace invalid utf8 character with SUBSTITUTION sequence
sub esc_html {
	my $str = shift;
	my %opts = @_;

	return undef unless defined $str;

	$str = to_utf8($str);
	$str = $cgi->escapeHTML($str);
	if ($opts{'-nbsp'}) {
		$str =~ s/ /&nbsp;/g;
	}
	$str =~ s|([[:cntrl:]])|(($1 ne "\t") ? quot_cec($1) : $1)|eg;
	return $str;
}

# quote control characters and escape filename to HTML
sub esc_path {
	my $str = shift;
	my %opts = @_;

	return undef unless defined $str;

	$str = to_utf8($str);
	$str = $cgi->escapeHTML($str);
	if ($opts{'-nbsp'}) {
		$str =~ s/ /&nbsp;/g;
	}
	$str =~ s|([[:cntrl:]])|quot_cec($1)|eg;
	return $str;
}

# Make control characters "printable", using character escape codes (CEC)
sub quot_cec {
	my $cntrl = shift;
	my %opts = @_;
	my %es = ( # character escape codes, aka escape sequences
		"\t" => '\t',   # tab            (HT)
		"\n" => '\n',   # line feed      (LF)
		"\r" => '\r',   # carrige return (CR)
		"\f" => '\f',   # form feed      (FF)
		"\b" => '\b',   # backspace      (BS)
		"\a" => '\a',   # alarm (bell)   (BEL)
		"\e" => '\e',   # escape         (ESC)
		"\013" => '\v', # vertical tab   (VT)
		"\000" => '\0', # nul character  (NUL)
	);
	my $chr = ( (exists $es{$cntrl})
		    ? $es{$cntrl}
		    : sprintf('\%2x', ord($cntrl)) );
	if ($opts{-nohtml}) {
		return $chr;
	} else {
		return "<span class=\"cntrl\">$chr</span>";
	}
}

# Alternatively use unicode control pictures codepoints,
# Unicode "printable representation" (PR)
sub quot_upr {
	my $cntrl = shift;
	my %opts = @_;

	my $chr = sprintf('&#%04d;', 0x2400+ord($cntrl));
	if ($opts{-nohtml}) {
		return $chr;
	} else {
		return "<span class=\"cntrl\">$chr</span>";
	}
}

# git may return quoted and escaped filenames
sub unquote {
	my $str = shift;

	sub unq {
		my $seq = shift;
		my %es = ( # character escape codes, aka escape sequences
			't' => "\t",   # tab            (HT, TAB)
			'n' => "\n",   # newline        (NL)
			'r' => "\r",   # return         (CR)
			'f' => "\f",   # form feed      (FF)
			'b' => "\b",   # backspace      (BS)
			'a' => "\a",   # alarm (bell)   (BEL)
			'e' => "\e",   # escape         (ESC)
			'v' => "\013", # vertical tab   (VT)
		);

		if ($seq =~ m/^[0-7]{1,3}$/) {
			# octal char sequence
			return chr(oct($seq));
		} elsif (exists $es{$seq}) {
			# C escape sequence, aka character escape code
			return $es{$seq};
		}
		# quoted ordinary character
		return $seq;
	}

	if ($str =~ m/^"(.*)"$/) {
		# needs unquoting
		$str = $1;
		$str =~ s/\\([^0-7]|[0-7]{1,3})/unq($1)/eg;
	}
	return $str;
}

# escape tabs (convert tabs to spaces)
sub untabify {
	my $line = shift;

	while ((my $pos = index($line, "\t")) != -1) {
		if (my $count = (8 - ($pos % 8))) {
			my $spaces = ' ' x $count;
			$line =~ s/\t/$spaces/;
		}
	}

	return $line;
}

sub project_in_list {
	my $project = shift;
	my @list = git_get_projects_list();
	return @list && scalar(grep { $_->{'path'} eq $project } @list);
}

## ----------------------------------------------------------------------
## HTML aware string manipulation

# Try to chop given string on a word boundary between position
# $len and $len+$add_len. If there is no word boundary there,
# chop at $len+$add_len. Do not chop if chopped part plus ellipsis
# (marking chopped part) would be longer than given string.
sub chop_str {
	my $str = shift;
	my $len = shift;
	my $add_len = shift || 10;
	my $where = shift || 'right'; # 'left' | 'center' | 'right'

	# Make sure perl knows it is utf8 encoded so we don't
	# cut in the middle of a utf8 multibyte char.
	$str = to_utf8($str);

	# allow only $len chars, but don't cut a word if it would fit in $add_len
	# if it doesn't fit, cut it if it's still longer than the dots we would add
	# remove chopped character entities entirely

	# when chopping in the middle, distribute $len into left and right part
	# return early if chopping wouldn't make string shorter
	if ($where eq 'center') {
		return $str if ($len + 5 >= length($str)); # filler is length 5
		$len = int($len/2);
	} else {
		return $str if ($len + 4 >= length($str)); # filler is length 4
	}

	# regexps: ending and beginning with word part up to $add_len
	my $endre = qr/.{$len}\w{0,$add_len}/;
	my $begre = qr/\w{0,$add_len}.{$len}/;

	if ($where eq 'left') {
		$str =~ m/^(.*?)($begre)$/;
		my ($lead, $body) = ($1, $2);
		if (length($lead) > 4) {
			$lead = " ...";
		}
		return "$lead$body";

	} elsif ($where eq 'center') {
		$str =~ m/^($endre)(.*)$/;
		my ($left, $str)  = ($1, $2);
		$str =~ m/^(.*?)($begre)$/;
		my ($mid, $right) = ($1, $2);
		if (length($mid) > 5) {
			$mid = " ... ";
		}
		return "$left$mid$right";

	} else {
		$str =~ m/^($endre)(.*)$/;
		my $body = $1;
		my $tail = $2;
		if (length($tail) > 4) {
			$tail = "... ";
		}
		return "$body$tail";
	}
}

# takes the same arguments as chop_str, but also wraps a <span> around the
# result with a title attribute if it does get chopped. Additionally, the
# string is HTML-escaped.
sub chop_and_escape_str {
	my ($str) = @_;

	my $chopped = chop_str(@_);
	if ($chopped eq $str) {
		return esc_html($chopped);
	} else {
		$str =~ s/[[:cntrl:]]/?/g;
		return $cgi->span({-title=>$str}, esc_html($chopped));
	}
}

## ----------------------------------------------------------------------
## functions returning short strings

# CSS class for given age value (in seconds)
sub age_class {
	my $age = shift;

	if (!defined $age) {
		return "noage";
	} elsif ($age < 60*60*2) {
		return "age0";
	} elsif ($age < 60*60*24*2) {
		return "age1";
	} else {
		return "age2";
	}
}

# convert age in seconds to "nn units ago" string
sub age_string {
	my $age = shift;
	my $age_str;

	if ($age > 60*60*24*365*2) {
		$age_str = (int $age/60/60/24/365);
		$age_str .= " years ago";
	} elsif ($age > 60*60*24*(365/12)*2) {
		$age_str = int $age/60/60/24/(365/12);
		$age_str .= " months ago";
	} elsif ($age > 60*60*24*7*2) {
		$age_str = int $age/60/60/24/7;
		$age_str .= " weeks ago";
	} elsif ($age > 60*60*24*2) {
		$age_str = int $age/60/60/24;
		$age_str .= " days ago";
	} elsif ($age > 60*60*2) {
		$age_str = int $age/60/60;
		$age_str .= " hours ago";
	} elsif ($age > 60*2) {
		$age_str = int $age/60;
		$age_str .= " min ago";
	} elsif ($age > 2) {
		$age_str = int $age;
		$age_str .= " sec ago";
	} else {
		$age_str .= " right now";
	}
	return $age_str;
}

use constant {
	S_IFINVALID => 0030000,
	S_IFGITLINK => 0160000,
};

# submodule/subproject, a commit object reference
sub S_ISGITLINK {
	my $mode = shift;

	return (($mode & S_IFMT) == S_IFGITLINK)
}

# convert file mode in octal to symbolic file mode string
sub mode_str {
	my $mode = oct shift;

	if (S_ISGITLINK($mode)) {
		return 'm---------';
	} elsif (S_ISDIR($mode & S_IFMT)) {
		return 'drwxr-xr-x';
	} elsif (S_ISLNK($mode)) {
		return 'lrwxrwxrwx';
	} elsif (S_ISREG($mode)) {
		# git cares only about the executable bit
		if ($mode & S_IXUSR) {
			return '-rwxr-xr-x';
		} else {
			return '-rw-r--r--';
		};
	} else {
		return '----------';
	}
}

# convert file mode in octal to file type string
sub file_type {
	my $mode = shift;

	if ($mode !~ m/^[0-7]+$/) {
		return $mode;
	} else {
		$mode = oct $mode;
	}

	if (S_ISGITLINK($mode)) {
		return "submodule";
	} elsif (S_ISDIR($mode & S_IFMT)) {
		return "directory";
	} elsif (S_ISLNK($mode)) {
		return "symlink";
	} elsif (S_ISREG($mode)) {
		return "file";
	} else {
		return "unknown";
	}
}

# convert file mode in octal to file type description string
sub file_type_long {
	my $mode = shift;

	if ($mode !~ m/^[0-7]+$/) {
		return $mode;
	} else {
		$mode = oct $mode;
	}

	if (S_ISGITLINK($mode)) {
		return "submodule";
	} elsif (S_ISDIR($mode & S_IFMT)) {
		return "directory";
	} elsif (S_ISLNK($mode)) {
		return "symlink";
	} elsif (S_ISREG($mode)) {
		if ($mode & S_IXUSR) {
			return "executable";
		} else {
			return "file";
		};
	} else {
		return "unknown";
	}
}


## ----------------------------------------------------------------------
## functions returning short HTML fragments, or transforming HTML fragments
## which don't belong to other sections

# format line of commit message.
sub format_log_line_html {
	my $line = shift;

	$line = esc_html($line, -nbsp=>1);
	$line =~ s{\b([0-9a-fA-F]{8,40})\b}{
		$cgi->a({-href => href(action=>"object", hash=>$1),
					-class => "text"}, $1);
	}eg;

	return $line;
}

# format marker of refs pointing to given object

# the destination action is chosen based on object type and current context:
# - for annotated tags, we choose the tag view unless it's the current view
#   already, in which case we go to shortlog view
# - for other refs, we keep the current view if we're in history, shortlog or
#   log view, and select shortlog otherwise
sub format_ref_marker {
	my ($refs, $id) = @_;
	my $markers = '';

	if (defined $refs->{$id}) {
		foreach my $ref (@{$refs->{$id}}) {
			# this code exploits the fact that non-lightweight tags are the
			# only indirect objects, and that they are the only objects for which
			# we want to use tag instead of shortlog as action
			my ($type, $name) = qw();
			my $indirect = ($ref =~ s/\^\{\}$//);
			# e.g. tags/v2.6.11 or heads/next
			if ($ref =~ m!^(.*?)s?/(.*)$!) {
				$type = $1;
				$name = $2;
			} else {
				$type = "ref";
				$name = $ref;
			}

			my $class = $type;
			$class .= " indirect" if $indirect;

			my $dest_action = "shortlog";

			if ($indirect) {
				$dest_action = "tag" unless $action eq "tag";
			} elsif ($action =~ /^(history|(short)?log)$/) {
				$dest_action = $action;
			}

			my $dest = "";
			$dest .= "refs/" unless $ref =~ m!^refs/!;
			$dest .= $ref;

			my $link = $cgi->a({
				-href => href(
					action=>$dest_action,
					hash=>$dest
				)}, $name);

			$markers .= " <span class=\"$class\" title=\"$ref\">" .
				$link . "</span>";
		}
	}

	if ($markers) {
		return ' <span class="refs">'. $markers . '</span>';
	} else {
		return "";
	}
}

# format, perhaps shortened and with markers, title line
sub format_subject_html {
	my ($long, $short, $href, $extra) = @_;
	$extra = '' unless defined($extra);

	if (length($short) < length($long)) {
		$long =~ s/[[:cntrl:]]/?/g;
		return $cgi->a({-href => $href, -class => "list subject",
		                -title => to_utf8($long)},
		       esc_html($short)) . $extra;
	} else {
		return $cgi->a({-href => $href, -class => "list subject"},
		       esc_html($long)) . $extra;
	}
}

# Rather than recomputing the url for an email multiple times, we cache it
# after the first hit. This gives a visible benefit in views where the avatar
# for the same email is used repeatedly (e.g. shortlog).
# The cache is shared by all avatar engines (currently gravatar only), which
# are free to use it as preferred. Since only one avatar engine is used for any
# given page, there's no risk for cache conflicts.
our %avatar_cache = ();

# Compute the picon url for a given email, by using the picon search service over at
# http://www.cs.indiana.edu/picons/search.html
sub picon_url {
	my $email = lc shift;
	if (!$avatar_cache{$email}) {
		my ($user, $domain) = split('@', $email);
		$avatar_cache{$email} =
			"http://www.cs.indiana.edu/cgi-pub/kinzler/piconsearch.cgi/" .
			"$domain/$user/" .
			"users+domains+unknown/up/single";
	}
	return $avatar_cache{$email};
}

# Compute the gravatar url for a given email, if it's not in the cache already.
# Gravatar stores only the part of the URL before the size, since that's the
# one computationally more expensive. This also allows reuse of the cache for
# different sizes (for this particular engine).
sub gravatar_url {
	my $email = lc shift;
	my $size = shift;
	$avatar_cache{$email} ||=
		"http://www.gravatar.com/avatar/" .
			Digest::MD5::md5_hex($email) . "?s=";
	return $avatar_cache{$email} . $size;
}

# Insert an avatar for the given $email at the given $size if the feature
# is enabled.
sub git_get_avatar {
	my ($email, %opts) = @_;
	my $pre_white  = ($opts{-pad_before} ? "&nbsp;" : "");
	my $post_white = ($opts{-pad_after}  ? "&nbsp;" : "");
	$opts{-size} ||= 'default';
	my $size = $avatar_size{$opts{-size}} || $avatar_size{'default'};
	my $url = "";
	if ($git_avatar eq 'gravatar') {
		$url = gravatar_url($email, $size);
	} elsif ($git_avatar eq 'picon') {
		$url = picon_url($email);
	}
	# Other providers can be added by extending the if chain, defining $url
	# as needed. If no variant puts something in $url, we assume avatars
	# are completely disabled/unavailable.
	if ($url) {
		return $pre_white .
		       "<img width=\"$size\" " .
		            "class=\"avatar\" " .
		            "src=\"$url\" " .
			    "alt=\"\" " .
		       "/>" . $post_white;
	} else {
		return "";
	}
}

sub format_search_author {
	my ($author, $searchtype, $displaytext) = @_;
	my $have_search = gitweb_check_feature('search');

	if ($have_search) {
		my $performed = "";
		if ($searchtype eq 'author') {
			$performed = "authored";
		} elsif ($searchtype eq 'committer') {
			$performed = "committed";
		}

		return $cgi->a({-href => href(action=>"search", hash=>$hash,
				searchtext=>$author,
				searchtype=>$searchtype), class=>"list",
				title=>"Search for commits $performed by $author"},
				$displaytext);

	} else {
		return $displaytext;
	}
}

# format the author name of the given commit with the given tag
# the author name is chopped and escaped according to the other
# optional parameters (see chop_str).
sub format_author_html {
	my $tag = shift;
	my $co = shift;
	my $author = chop_and_escape_str($co->{'author_name'}, @_);
	return "<$tag class=\"author\">" .
	       format_search_author($co->{'author_name'}, "author",
		       git_get_avatar($co->{'author_email'}, -pad_after => 1) .
		       $author) .
	       "</$tag>";
}

# format git diff header line, i.e. "diff --(git|combined|cc) ..."
sub format_git_diff_header_line {
	my $line = shift;
	my $diffinfo = shift;
	my ($from, $to) = @_;

	if ($diffinfo->{'nparents'}) {
		# combined diff
		$line =~ s!^(diff (.*?) )"?.*$!$1!;
		if ($to->{'href'}) {
			$line .= $cgi->a({-href => $to->{'href'}, -class => "path"},
			                 esc_path($to->{'file'}));
		} else { # file was deleted (no href)
			$line .= esc_path($to->{'file'});
		}
	} else {
		# "ordinary" diff
		$line =~ s!^(diff (.*?) )"?a/.*$!$1!;
		if ($from->{'href'}) {
			$line .= $cgi->a({-href => $from->{'href'}, -class => "path"},
			                 'a/' . esc_path($from->{'file'}));
		} else { # file was added (no href)
			$line .= 'a/' . esc_path($from->{'file'});
		}
		$line .= ' ';
		if ($to->{'href'}) {
			$line .= $cgi->a({-href => $to->{'href'}, -class => "path"},
			                 'b/' . esc_path($to->{'file'}));
		} else { # file was deleted
			$line .= 'b/' . esc_path($to->{'file'});
		}
	}

	return "<div class=\"diff header\">$line</div>\n";
}

# format extended diff header line, before patch itself
sub format_extended_diff_header_line {
	my $line = shift;
	my $diffinfo = shift;
	my ($from, $to) = @_;

	# match <path>
	if ($line =~ s!^((copy|rename) from ).*$!$1! && $from->{'href'}) {
		$line .= $cgi->a({-href=>$from->{'href'}, -class=>"path"},
		                       esc_path($from->{'file'}));
	}
	if ($line =~ s!^((copy|rename) to ).*$!$1! && $to->{'href'}) {
		$line .= $cgi->a({-href=>$to->{'href'}, -class=>"path"},
		                 esc_path($to->{'file'}));
	}
	# match single <mode>
	if ($line =~ m/\s(\d{6})$/) {
		$line .= '<span class="info"> (' .
		         file_type_long($1) .
		         ')</span>';
	}
	# match <hash>
	if ($line =~ m/^index [0-9a-fA-F]{40},[0-9a-fA-F]{40}/) {
		# can match only for combined diff
		$line = 'index ';
		for (my $i = 0; $i < $diffinfo->{'nparents'}; $i++) {
			if ($from->{'href'}[$i]) {
				$line .= $cgi->a({-href=>$from->{'href'}[$i],
				                  -class=>"hash"},
				                 substr($diffinfo->{'from_id'}[$i],0,7));
			} else {
				$line .= '0' x 7;
			}
			# separator
			$line .= ',' if ($i < $diffinfo->{'nparents'} - 1);
		}
		$line .= '..';
		if ($to->{'href'}) {
			$line .= $cgi->a({-href=>$to->{'href'}, -class=>"hash"},
			                 substr($diffinfo->{'to_id'},0,7));
		} else {
			$line .= '0' x 7;
		}

	} elsif ($line =~ m/^index [0-9a-fA-F]{40}..[0-9a-fA-F]{40}/) {
		# can match only for ordinary diff
		my ($from_link, $to_link);
		if ($from->{'href'}) {
			$from_link = $cgi->a({-href=>$from->{'href'}, -class=>"hash"},
			                     substr($diffinfo->{'from_id'},0,7));
		} else {
			$from_link = '0' x 7;
		}
		if ($to->{'href'}) {
			$to_link = $cgi->a({-href=>$to->{'href'}, -class=>"hash"},
			                   substr($diffinfo->{'to_id'},0,7));
		} else {
			$to_link = '0' x 7;
		}
		my ($from_id, $to_id) = ($diffinfo->{'from_id'}, $diffinfo->{'to_id'});
		$line =~ s!$from_id\.\.$to_id!$from_link..$to_link!;
	}

	return $line . "<br/>\n";
}

# format from-file/to-file diff header
sub format_diff_from_to_header {
	my ($from_line, $to_line, $diffinfo, $from, $to, @parents) = @_;
	my $line;
	my $result = '';

	$line = $from_line;
	#assert($line =~ m/^---/) if DEBUG;
	# no extra formatting for "^--- /dev/null"
	if (! $diffinfo->{'nparents'}) {
		# ordinary (single parent) diff
		if ($line =~ m!^--- "?a/!) {
			if ($from->{'href'}) {
				$line = '--- a/' .
				        $cgi->a({-href=>$from->{'href'}, -class=>"path"},
				                esc_path($from->{'file'}));
			} else {
				$line = '--- a/' .
				        esc_path($from->{'file'});
			}
		}
		$result .= qq!<div class="diff from_file">$line</div>\n!;

	} else {
		# combined diff (merge commit)
		for (my $i = 0; $i < $diffinfo->{'nparents'}; $i++) {
			if ($from->{'href'}[$i]) {
				$line = '--- ' .
				        $cgi->a({-href=>href(action=>"blobdiff",
				                             hash_parent=>$diffinfo->{'from_id'}[$i],
				                             hash_parent_base=>$parents[$i],
				                             file_parent=>$from->{'file'}[$i],
				                             hash=>$diffinfo->{'to_id'},
				                             hash_base=>$hash,
				                             file_name=>$to->{'file'}),
				                 -class=>"path",
				                 -title=>"diff" . ($i+1)},
				                $i+1) .
				        '/' .
				        $cgi->a({-href=>$from->{'href'}[$i], -class=>"path"},
				                esc_path($from->{'file'}[$i]));
			} else {
				$line = '--- /dev/null';
			}
			$result .= qq!<div class="diff from_file">$line</div>\n!;
		}
	}

	$line = $to_line;
	#assert($line =~ m/^\+\+\+/) if DEBUG;
	# no extra formatting for "^+++ /dev/null"
	if ($line =~ m!^\+\+\+ "?b/!) {
		if ($to->{'href'}) {
			$line = '+++ b/' .
			        $cgi->a({-href=>$to->{'href'}, -class=>"path"},
			                esc_path($to->{'file'}));
		} else {
			$line = '+++ b/' .
			        esc_path($to->{'file'});
		}
	}
	$result .= qq!<div class="diff to_file">$line</div>\n!;

	return $result;
}

# create note for patch simplified by combined diff
sub format_diff_cc_simplified {
	my ($diffinfo, @parents) = @_;
	my $result = '';

	$result .= "<div class=\"diff header\">" .
	           "diff --cc ";
	if (!is_deleted($diffinfo)) {
		$result .= $cgi->a({-href => href(action=>"blob",
		                                  hash_base=>$hash,
		                                  hash=>$diffinfo->{'to_id'},
		                                  file_name=>$diffinfo->{'to_file'}),
		                    -class => "path"},
		                   esc_path($diffinfo->{'to_file'}));
	} else {
		$result .= esc_path($diffinfo->{'to_file'});
	}
	$result .= "</div>\n" . # class="diff header"
	           "<div class=\"diff nodifferences\">" .
	           "Simple merge" .
	           "</div>\n"; # class="diff nodifferences"

	return $result;
}

# format patch (diff) line (not to be used for diff headers)
sub format_diff_line {
	my $line = shift;
	my ($from, $to) = @_;
	my $diff_class = "";

	chomp $line;

	if ($from && $to && ref($from->{'href'}) eq "ARRAY") {
		# combined diff
		my $prefix = substr($line, 0, scalar @{$from->{'href'}});
		if ($line =~ m/^\@{3}/) {
			$diff_class = " chunk_header";
		} elsif ($line =~ m/^\\/) {
			$diff_class = " incomplete";
		} elsif ($prefix =~ tr/+/+/) {
			$diff_class = " add";
		} elsif ($prefix =~ tr/-/-/) {
			$diff_class = " rem";
		}
	} else {
		# assume ordinary diff
		my $char = substr($line, 0, 1);
		if ($char eq '+') {
			$diff_class = " add";
		} elsif ($char eq '-') {
			$diff_class = " rem";
		} elsif ($char eq '@') {
			$diff_class = " chunk_header";
		} elsif ($char eq "\\") {
			$diff_class = " incomplete";
		}
	}
	$line = untabify($line);
	if ($from && $to && $line =~ m/^\@{2} /) {
		my ($from_text, $from_start, $from_lines, $to_text, $to_start, $to_lines, $section) =
			$line =~ m/^\@{2} (-(\d+)(?:,(\d+))?) (\+(\d+)(?:,(\d+))?) \@{2}(.*)$/;

		$from_lines = 0 unless defined $from_lines;
		$to_lines   = 0 unless defined $to_lines;

		if ($from->{'href'}) {
			$from_text = $cgi->a({-href=>"$from->{'href'}#l$from_start",
			                     -class=>"list"}, $from_text);
		}
		if ($to->{'href'}) {
			$to_text   = $cgi->a({-href=>"$to->{'href'}#l$to_start",
			                     -class=>"list"}, $to_text);
		}
		$line = "<span class=\"chunk_info\">@@ $from_text $to_text @@</span>" .
		        "<span class=\"section\">" . esc_html($section, -nbsp=>1) . "</span>";
		return "<div class=\"diff$diff_class\">$line</div>\n";
	} elsif ($from && $to && $line =~ m/^\@{3}/) {
		my ($prefix, $ranges, $section) = $line =~ m/^(\@+) (.*?) \@+(.*)$/;
		my (@from_text, @from_start, @from_nlines, $to_text, $to_start, $to_nlines);

		@from_text = split(' ', $ranges);
		for (my $i = 0; $i < @from_text; ++$i) {
			($from_start[$i], $from_nlines[$i]) =
				(split(',', substr($from_text[$i], 1)), 0);
		}

		$to_text   = pop @from_text;
		$to_start  = pop @from_start;
		$to_nlines = pop @from_nlines;

		$line = "<span class=\"chunk_info\">$prefix ";
		for (my $i = 0; $i < @from_text; ++$i) {
			if ($from->{'href'}[$i]) {
				$line .= $cgi->a({-href=>"$from->{'href'}[$i]#l$from_start[$i]",
				                  -class=>"list"}, $from_text[$i]);
			} else {
				$line .= $from_text[$i];
			}
			$line .= " ";
		}
		if ($to->{'href'}) {
			$line .= $cgi->a({-href=>"$to->{'href'}#l$to_start",
			                  -class=>"list"}, $to_text);
		} else {
			$line .= $to_text;
		}
		$line .= " $prefix</span>" .
		         "<span class=\"section\">" . esc_html($section, -nbsp=>1) . "</span>";
		return "<div class=\"diff$diff_class\">$line</div>\n";
	}
	return "<div class=\"diff$diff_class\">" . esc_html($line, -nbsp=>1) . "</div>\n";
}

# Generates undef or something like "_snapshot_" or "snapshot (_tbz2_ _zip_)",
# linked.  Pass the hash of the tree/commit to snapshot.
sub format_snapshot_links {
	my ($hash) = @_;
	my $num_fmts = @snapshot_fmts;
	if ($num_fmts > 1) {
		# A parenthesized list of links bearing format names.
		# e.g. "snapshot (_tar.gz_ _zip_)"
		return "snapshot (" . join(' ', map
			$cgi->a({
				-href => href(
					action=>"snapshot",
					hash=>$hash,
					snapshot_format=>$_
				)
			}, $known_snapshot_formats{$_}{'display'})
		, @snapshot_fmts) . ")";
	} elsif ($num_fmts == 1) {
		# A single "snapshot" link whose tooltip bears the format name.
		# i.e. "_snapshot_"
		my ($fmt) = @snapshot_fmts;
		return
			$cgi->a({
				-href => href(
					action=>"snapshot",
					hash=>$hash,
					snapshot_format=>$fmt
				),
				-title => "in format: $known_snapshot_formats{$fmt}{'display'}"
			}, "snapshot");
	} else { # $num_fmts == 0
		return undef;
	}
}

## ......................................................................
## functions returning values to be passed, perhaps after some
## transformation, to other functions; e.g. returning arguments to href()

# returns hash to be passed to href to generate gitweb URL
# in -title key it returns description of link
sub get_feed_info {
	my $format = shift || 'Atom';
	my %res = (action => lc($format));

	# feed links are possible only for project views
	return unless (defined $project);
	# some views should link to OPML, or to generic project feed,
	# or don't have specific feed yet (so they should use generic)
	return if ($action =~ /^(?:tags|heads|forks|tag|search)$/x);

	my $branch;
	# branches refs uses 'refs/heads/' prefix (fullname) to differentiate
	# from tag links; this also makes possible to detect branch links
	if ((defined $hash_base && $hash_base =~ m!^refs/heads/(.*)$!) ||
	    (defined $hash      && $hash      =~ m!^refs/heads/(.*)$!)) {
		$branch = $1;
	}
	# find log type for feed description (title)
	my $type = 'log';
	if (defined $file_name) {
		$type  = "history of $file_name";
		$type .= "/" if ($action eq 'tree');
		$type .= " on '$branch'" if (defined $branch);
	} else {
		$type = "log of $branch" if (defined $branch);
	}

	$res{-title} = $type;
	$res{'hash'} = (defined $branch ? "refs/heads/$branch" : undef);
	$res{'file_name'} = $file_name;

	return %res;
}

## ----------------------------------------------------------------------
## git utility subroutines, invoking git commands

# returns path to the core git executable and the --git-dir parameter as list
sub git_cmd {
	$number_of_git_cmds++;
	return $GIT, '--git-dir='.$git_dir;
}

# quote the given arguments for passing them to the shell
# quote_command("command", "arg 1", "arg with ' and ! characters")
# => "'command' 'arg 1' 'arg with '\'' and '\!' characters'"
# Try to avoid using this function wherever possible.
sub quote_command {
	return join(' ',
		map { my $a = $_; $a =~ s/(['!])/'\\$1'/g; "'$a'" } @_ );
}

# get HEAD ref of given project as hash
sub git_get_head_hash {
	return git_get_full_hash(shift, 'HEAD');
}

sub git_get_full_hash {
	return git_get_hash(@_);
}

sub git_get_short_hash {
	return git_get_hash(@_, '--short=7');
}

sub git_get_hash {
	my ($project, $hash, @options) = @_;
	my $o_git_dir = $git_dir;
	my $retval = undef;
	$git_dir = "$projectroot/$project";
	if (open my $fd, '-|', git_cmd(), 'rev-parse',
	    '--verify', '-q', @options, $hash) {
		$retval = <$fd>;
		chomp $retval if defined $retval;
		close $fd;
	}
	if (defined $o_git_dir) {
		$git_dir = $o_git_dir;
	}
	return $retval;
}

# get type of given object
sub git_get_type {
	my $hash = shift;

	open my $fd, "-|", git_cmd(), "cat-file", '-t', $hash or return;
	my $type = <$fd>;
	close $fd or return;
	chomp $type;
	return $type;
}

# repository configuration
our $config_file = '';
our %config;

# store multiple values for single key as anonymous array reference
# single values stored directly in the hash, not as [ <value> ]
sub hash_set_multi {
	my ($hash, $key, $value) = @_;

	if (!exists $hash->{$key}) {
		$hash->{$key} = $value;
	} elsif (!ref $hash->{$key}) {
		$hash->{$key} = [ $hash->{$key}, $value ];
	} else {
		push @{$hash->{$key}}, $value;
	}
}

# return hash of git project configuration
# optionally limited to some section, e.g. 'gitweb'
sub git_parse_project_config {
	my $section_regexp = shift;
	my %config;

	local $/ = "\0";

	open my $fh, "-|", git_cmd(), "config", '-z', '-l',
		or return;

	while (my $keyval = <$fh>) {
		chomp $keyval;
		my ($key, $value) = split(/\n/, $keyval, 2);

		hash_set_multi(\%config, $key, $value)
			if (!defined $section_regexp || $key =~ /^(?:$section_regexp)\./o);
	}
	close $fh;

	return %config;
}

# convert config value