# -*- coding: utf-8 -*-

# This program is free software: you can redistribute it and/or modify

# it under the terms of the GNU General Public License as published by

# the Free Software Foundation, either version 3 of the License, or

# (at your option) any later version.

#

# This program is distributed in the hope that it will be useful,

# but WITHOUT ANY WARRANTY; without even the implied warranty of

# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

# GNU General Public License for more details.

#

# You should have received a copy of the GNU General Public License

# along with this program.  If not, see <http://www.gnu.org/licenses/>.

"""

Helper functions

Consists of functions to typically be used within templates, but also

available to Controllers. This module is available to both as 'h'.

"""

import random

import hashlib

import StringIO

import math

import logging

import re

import urlparse

import textwrap

from pygments.formatters.html import HtmlFormatter

from pygments import highlight as code_highlight

from pylons import url

from pylons.i18n.translation import _, ungettext

from hashlib import md5

from webhelpers.html import literal, HTML, escape

from webhelpers.html.tools import *

from webhelpers.html.builder import make_tag

from webhelpers.html.tags import auto_discovery_link, checkbox, css_classes, \

    end_form, file, hidden, image, javascript_link, link_to, \

    link_to_if, link_to_unless, ol, required_legend, select, stylesheet_link, \

    submit, text, password, textarea, title, ul, xml_declaration, radio

from webhelpers.html.tools import auto_link, button_to, highlight, \

    js_obfuscate, mail_to, strip_links, strip_tags, tag_re

from webhelpers.number import format_byte_size, format_bit_size

from webhelpers.pylonslib import Flash as _Flash

from webhelpers.pylonslib.secure_form import secure_form as form, authentication_token

from webhelpers.text import chop_at, collapse, convert_accented_entities, \

    convert_misc_entities, lchop, plural, rchop, remove_formatting, \

    replace_whitespace, urlify, truncate, wrap_paragraphs

from webhelpers.date import time_ago_in_words

from webhelpers.paginate import Page as _Page

from webhelpers.html.tags import _set_input_attrs, _set_id_attr, \

    convert_boolean_attrs, NotGiven, _make_safe_id_component

from kallithea.lib.annotate import annotate_highlight

from kallithea.lib.utils import repo_name_slug, get_custom_lexer

from kallithea.lib.utils2 import str2bool, safe_unicode, safe_str, \

    get_changeset_safe, datetime_to_time, time_to_datetime, AttributeDict,\

    safe_int

from kallithea.lib.markup_renderer import MarkupRenderer, url_re

from kallithea.lib.vcs.exceptions import ChangesetDoesNotExistError

from kallithea.lib.vcs.backends.base import BaseChangeset, EmptyChangeset

from kallithea.config.conf import DATE_FORMAT, DATETIME_FORMAT

from kallithea.model.changeset_status import ChangesetStatusModel

from kallithea.model.db import URL_SEP, Permission

log = logging.getLogger(__name__)

def canonical_url(*args, **kargs):

    '''Like url(x, qualified=True), but returns url that not only is qualified

    but also canonical, as configured in canonical_url'''

    from kallithea import CONFIG

    try:

        parts = CONFIG.get('canonical_url', '').split('://', 1)

        kargs['host'] = parts[1].split('/', 1)[0]

        kargs['protocol'] = parts[0]

    except IndexError:

        kargs['qualified'] = True

    return url(*args, **kargs)

def canonical_hostname():

    '''Return canonical hostname of system'''

    from kallithea import CONFIG

    try:

        parts = CONFIG.get('canonical_url', '').split('://', 1)

        return parts[1].split('/', 1)[0]

    except IndexError:

        parts = url('home', qualified=True).split('://', 1)

        return parts[1].split('/', 1)[0]

def html_escape(text, html_escape_table=None):

    """Produce entities within text."""

    if not html_escape_table:

        html_escape_table = {

            "&": "&",

            '"': """,

            "'": "'",

            ">": ">",

            "<": "&lt;",

        }

    return "".join(html_escape_table.get(c, c) for c in text)

def shorter(text, size=20):

    postfix = '...'

    if len(text) > size:

        return text[:size - len(postfix)] + postfix

    return text

def _reset(name, value=None, id=NotGiven, type="reset", **attrs):

    """

    Reset button

    """

    _set_input_attrs(attrs, type, name, value)

    _set_id_attr(attrs, id, name)

    convert_boolean_attrs(attrs, ["disabled"])

    return HTML.input(**attrs)

reset = _reset

safeid = _make_safe_id_component

def FID(raw_id, path):

    """

    Creates a unique ID for filenode based on it's hash of path and revision

    it's safe to use in urls

    :param raw_id:

    :param path:

    """

    return 'C-%s-%s' % (short_id(raw_id), md5(safe_str(path)).hexdigest()[:12])

class _GetError(object):

    """Get error from form_errors, and represent it as span wrapped error

    message

    :param field_name: field to fetch errors for

    :param form_errors: form errors dict

    """

    def __call__(self, field_name, form_errors):

        tmpl = """<span class="error_msg">%s</span>"""

        if form_errors and field_name in form_errors:

            return literal(tmpl % form_errors.get(field_name))

get_error = _GetError()

class _ToolTip(object):

    def __call__(self, tooltip_title, trim_at=50):

        """

        Special function just to wrap our text into nice formatted

        autowrapped text

        :param tooltip_title:

        """

        tooltip_title = escape(tooltip_title)

        tooltip_title = tooltip_title.replace('<', '&lt;').replace('>', '&gt;')

        return tooltip_title

tooltip = _ToolTip()

class _FilesBreadCrumbs(object):

    def __call__(self, repo_name, rev, paths):

        if isinstance(paths, str):

            paths = safe_unicode(paths)

        url_l = [link_to(repo_name, url('files_home',

                                        repo_name=repo_name,

                                        revision=rev, f_path=''),

                         class_='ypjax-link')]

        paths_l = paths.split('/')

        for cnt, p in enumerate(paths_l):

            if p != '':

                url_l.append(link_to(p,

                                     url('files_home',

                                         repo_name=repo_name,

                                         revision=rev,

                                         f_path='/'.join(paths_l[:cnt + 1])

                                         ),

                                     class_='ypjax-link'

                                     )

                             )

        return literal('/'.join(url_l))

files_breadcrumbs = _FilesBreadCrumbs()

class CodeHtmlFormatter(HtmlFormatter):

    """

    My code Html Formatter for source codes

    """

    def wrap(self, source, outfile):

        return self._wrap_div(self._wrap_pre(self._wrap_code(source)))

    def _wrap_code(self, source):

        for cnt, it in enumerate(source):

            i, t = it

            t = '<div id="L%s">%s</div>' % (cnt + 1, t)

            yield i, t

    def _wrap_tablelinenos(self, inner):

        dummyoutfile = StringIO.StringIO()

        lncount = 0

        for t, line in inner:

            if t:

                lncount += 1

            dummyoutfile.write(line)

        fl = self.linenostart

        mw = len(str(lncount + fl - 1))

        sp = self.linenospecial

        st = self.linenostep

        la = self.lineanchors

        aln = self.anchorlinenos

        nocls = self.noclasses

        if sp:

            lines = []

            for i in range(fl, fl + lncount):

                if i % st == 0:

                    if i % sp == 0:

                        if aln:

                            lines.append('<a href="#%s%d" class="special">%*d</a>' %

                                         (la, i, mw, i))

                        else:

                            lines.append('<span class="special">%*d</span>' % (mw, i))

                    else:

                        if aln:

                            lines.append('<a href="#%s%d">%*d</a>' % (la, i, mw, i))

                        else:

                            lines.append('%*d' % (mw, i))

                else:

                    lines.append('')

            ls = '\n'.join(lines)

        else:

            lines = []

            for i in range(fl, fl + lncount):

                if i % st == 0:

                    if aln:

                        lines.append('<a href="#%s%d">%*d</a>' % (la, i, mw, i))

                    else:

                        lines.append('%*d' % (mw, i))

                else:

                    lines.append('')

            ls = '\n'.join(lines)

        # in case you wonder about the seemingly redundant <div> here: since the

        # content in the other cell also is wrapped in a div, some browsers in

        # some configurations seem to mess up the formatting...

        if nocls:

            yield 0, ('<table class="%stable">' % self.cssclass +

                      '<tr><td><div class="linenodiv" '

                      'style="background-color: #f0f0f0; padding-right: 10px">'

                      '<pre style="line-height: 125%">' +

                      ls + '</pre></div></td><td id="hlcode" class="code">')

        else:

            yield 0, ('<table class="%stable">' % self.cssclass +

                      '<tr><td class="linenos"><div class="linenodiv"><pre>' +

                      ls + '</pre></div></td><td id="hlcode" class="code">')

        yield 0, dummyoutfile.getvalue()

        yield 0, '</td></tr></table>'

_whitespace_re = re.compile(r'(\t)|( )(?=\n|</div>)')

def _markup_whitespace(m):

    groups = m.groups()

    if groups[0]:

        return '<u>\t</u>'

    if groups[1]:

        return ' <i></i>'

def markup_whitespace(s):

    return _whitespace_re.sub(_markup_whitespace, s)

def pygmentize(filenode, **kwargs):

    """

    pygmentize function using pygments

    :param filenode:

    """

    lexer = get_custom_lexer(filenode.extension) or filenode.lexer

    return literal(markup_whitespace(

        code_highlight(filenode.content, lexer, CodeHtmlFormatter(**kwargs))))

def pygmentize_annotation(repo_name, filenode, **kwargs):

    """

    pygmentize function for annotation

    :param filenode:

    """

    color_dict = {}

    def gen_color(n=10000):

        """generator for getting n of evenly distributed colors using

        hsv color and golden ratio. It always return same order of colors

        :returns: RGB tuple

        """

        def hsv_to_rgb(h, s, v):

            if s == 0.0:

                return v, v, v

            i = int(h * 6.0)  # XXX assume int() truncates!

            f = (h * 6.0) - i

            p = v * (1.0 - s)

            q = v * (1.0 - s * f)

            t = v * (1.0 - s * (1.0 - f))

            i = i % 6

            if i == 0:

                return v, t, p

            if i == 1:

                return q, v, p

            if i == 2:

                return p, v, t

            if i == 3:

                return p, q, v

            if i == 4:

                return t, p, v

            if i == 5:

                return v, p, q

        golden_ratio = 0.618033988749895

        h = 0.22717784590367374

        for _unused in xrange(n):

            h += golden_ratio

            h %= 1

            HSV_tuple = [h, 0.95, 0.95]

            RGB_tuple = hsv_to_rgb(*HSV_tuple)

            yield map(lambda x: str(int(x * 256)), RGB_tuple)

    cgenerator = gen_color()

    def get_color_string(cs):

        if cs in color_dict:

            col = color_dict[cs]

        else:

            col = color_dict[cs] = cgenerator.next()

        return "color: rgb(%s)! important;" % (', '.join(col))

    def url_func(repo_name):

        def _url_func(changeset):

            date = changeset.date

            tooltip_html = ("<div style='font-size:0.8em'><b>Author:</b>"

                            " %s<br/><b>Date:</b> %s</b><br/><b>Message:"

                            "</b> %s<br/></div>")

            tooltip_html = tooltip_html % (author, date, message)

            lnk_format = show_id(changeset)

            uri = link_to(

                    lnk_format,

                    url('changeset_home', repo_name=repo_name,

                        revision=changeset.raw_id),

                    style=get_color_string(changeset.raw_id),

                    title=tooltip_html

                  )

            uri += '\n'

            return uri

        return _url_func

    return literal(markup_whitespace(annotate_highlight(filenode, url_func(repo_name), **kwargs)))

def is_following_repo(repo_name, user_id):

    from kallithea.model.scm import ScmModel

    return ScmModel().is_following_repo(repo_name, user_id)

class _Message(object):

    """A message returned by ``Flash.pop_messages()``.

    Converting the message to a string returns the message text. Instances

    also have the following attributes:

    * ``message``: the message text.

    * ``category``: the category specified when the message was created.

    """

    def __init__(self, category, message):

        self.category = category

        self.message = message

    def __str__(self):

        return self.message

    __unicode__ = __str__

    def __html__(self):

        return escape(safe_unicode(self.message))

class Flash(_Flash):

    def pop_messages(self):

        """Return all accumulated messages and delete them from the session.

        The return value is a list of ``Message`` objects.

        """

        from pylons import session

        messages = session.pop(self.session_key, [])

        session.save()

        return [_Message(*m) for m in messages]

flash = Flash()

#==============================================================================

# SCM FILTERS available via h.

#==============================================================================

from kallithea.lib.vcs.utils import author_name, author_email

from kallithea.lib.utils2 import credentials_filter, age as _age

from kallithea.model.db import User, ChangesetStatus

age = lambda  x, y=False: _age(x, y)

capitalize = lambda x: x.capitalize()

email = author_email

short_id = lambda x: x[:12]

hide_credentials = lambda x: ''.join(credentials_filter(x))

def show_id(cs):

    """

    Configurable function that shows ID

    by default it's r123:fffeeefffeee

    :param cs: changeset instance

    """

    from kallithea import CONFIG

    def_len = safe_int(CONFIG.get('show_sha_length', 12))

    show_rev = str2bool(CONFIG.get('show_revision_number', False))

    raw_id = cs.raw_id[:def_len]

    if show_rev:

        return 'r%s:%s' % (cs.revision, raw_id)

    else:

        return '%s' % (raw_id)

def fmt_date(date):

    if date:

        return date.strftime("%Y-%m-%d %H:%M:%S").decode('utf8')

    return ""

def is_git(repository):

    if hasattr(repository, 'alias'):

        _type = repository.alias

    elif hasattr(repository, 'repo_type'):

        _type = repository.repo_type

    else:

        _type = repository

    return _type == 'git'

def is_hg(repository):

    if hasattr(repository, 'alias'):

        _type = repository.alias

    elif hasattr(repository, 'repo_type'):

        _type = repository.repo_type

    else:

        _type = repository

    return _type == 'hg'

def user_or_none(author):

    email = author_email(author)

    if email:

        user = User.get_by_email(email, case_insensitive=True, cache=True)

        if user is not None:

            return user

    user = User.get_by_username(author_name(author), case_insensitive=True, cache=True)

    if user is not None:

        return user

    return None

def email_or_none(author):

    if not author:

        return None

    user = user_or_none(author)

    if user is not None:

        return user.email # always use main email address - not necessarily the one used to find user

    # extract email from the commit string

    email = author_email(author)

    if email:

        return email

    # No valid email, not a valid user in the system, none!

    return None

def person(author, show_attr="username"):

    """Find the user identified by 'author', return one of the users attributes,

    default to the username attribute, None if there is no user"""

    # attr to return from fetched user

    person_getter = lambda usr: getattr(usr, show_attr)

    # if author is already an instance use it for extraction

    if isinstance(author, User):

        return person_getter(author)

    user = user_or_none(author)

    if user is not None:

        return person_getter(user)

    # Still nothing?  Just pass back the author name if any, else the email

    return author_name(author) or email(author)

def person_by_id(id_, show_attr="username"):

    # attr to return from fetched user

    person_getter = lambda usr: getattr(usr, show_attr)

    #maybe it's an ID ?

    if str(id_).isdigit() or isinstance(id_, int):

        id_ = int(id_)

        user = User.get(id_)

        if user is not None:

            return person_getter(user)

    return id_

def desc_stylize(value):

    """

    converts tags from value into html equivalent

    :param value:

    """

    if not value:

        return ''

    value = re.sub(r'\[see\ \=\>\ *([a-zA-Z0-9\/\=\?\&\ \:\/\.\-]*)\]',

                   '<div class="metatag" tag="see">see =&gt; \\1 </div>', value)

    value = re.sub(r'\[license\ \=\>\ *([a-zA-Z0-9\/\=\?\&\ \:\/\.\-]*)\]',

                   '<div class="metatag" tag="license"><a href="http:\/\/www.opensource.org/licenses/\\1">\\1</a></div>', value)

    value = re.sub(r'\[(requires|recommends|conflicts|base)\ \=\>\ *([a-zA-Z0-9\-\/]*)\]',

                   '<div class="metatag" tag="\\1">\\1 =&gt; <a href="/\\2">\\2</a></div>', value)

    value = re.sub(r'\[(lang|language)\ \=\>\ *([a-zA-Z\-\/\#\+]*)\]',

                   '<div class="metatag" tag="lang">\\2</div>', value)

    value = re.sub(r'\[([a-z]+)\]',

                  '<div class="metatag" tag="\\1">\\1</div>', value)

    return value

def boolicon(value):

    """Returns boolean value of a value, represented as small html image of true/false

    icons

    :param value: value

    """

    if value:

        return HTML.tag('i', class_="icon-ok")

    else:

        return HTML.tag('i', class_="icon-minus-circled")

def action_parser(user_log, feed=False, parse_cs=False):

    """

    This helper will action_map the specified string action into translated

    fancy names with icons and links

    :param user_log: user log instance

    :param feed: use output for feeds (no html and fancy icons)

    :param parse_cs: parse Changesets into VCS instances

    """

    action = user_log.action

    action_params = ' '

    x = action.split(':')

    if len(x) > 1:

        action, action_params = x

    def get_cs_links():

        revs_limit = 3  # display this amount always

        revs_top_limit = 50  # show upto this amount of changesets hidden

        revs_ids = action_params.split(',')

        deleted = user_log.repository is None

        if deleted:

            return ','.join(revs_ids)

        repo_name = user_log.repository.repo_name

        def lnk(rev, repo_name):

            if isinstance(rev, BaseChangeset) or isinstance(rev, AttributeDict):

                lazy_cs = True

                if getattr(rev, 'op', None) and getattr(rev, 'ref_name', None):

                    lazy_cs = False

                    lbl = '?'

                    if rev.op == 'delete_branch':

                        lbl = '%s' % _('Deleted branch: %s') % rev.ref_name

                        title = ''

                    elif rev.op == 'tag':

                        lbl = '%s' % _('Created tag: %s') % rev.ref_name

                        title = ''

                    _url = '#'

                else:

                    lbl = '%s' % (rev.short_id[:8])

                    _url = url('changeset_home', repo_name=repo_name,

                               revision=rev.raw_id)

                    title = tooltip(rev.message)

            else:

                ## changeset cannot be found/striped/removed etc.

                lbl = ('%s' % rev)[:12]

                _url = '#'

                title = _('Changeset not found')

            if parse_cs:

                return link_to(lbl, _url, title=title, class_='tooltip')

            return link_to(lbl, _url, raw_id=rev.raw_id, repo_name=repo_name,

                           class_='lazy-cs' if lazy_cs else '')

        def _get_op(rev_txt):

            _op = None

            _name = rev_txt

            if len(rev_txt.split('=>')) == 2:

                _op, _name = rev_txt.split('=>')

            return _op, _name

        revs = []

        if len(filter(lambda v: v != '', revs_ids)) > 0:

            repo = None

            for rev in revs_ids[:revs_top_limit]:

                _op, _name = _get_op(rev)

                # we want parsed changesets, or new log store format is bad

                if parse_cs:

                    try:

                        if repo is None:

                            repo = user_log.repository.scm_instance

                        _rev = repo.get_changeset(rev)

                        revs.append(_rev)

                    except ChangesetDoesNotExistError:

                        log.error('cannot find revision %s in this repo' % rev)

                        revs.append(rev)

                        continue

                else:

                    _rev = AttributeDict({

                        'short_id': rev[:12],

                        'raw_id': rev,

                        'message': '',

                        'op': _op,

                        'ref_name': _name

                    })

                    revs.append(_rev)

        cs_links = [" " + ', '.join(

            [lnk(rev, repo_name) for rev in revs[:revs_limit]]

        )]

        _op1, _name1 = _get_op(revs_ids[0])

        _op2, _name2 = _get_op(revs_ids[-1])

        _rev = '%s...%s' % (_name1, _name2)

        compare_view = (

            ' <div class="compare_view tooltip" title="%s">'

            '<a href="%s">%s</a> </div>' % (

                _('Show all combined changesets %s->%s') % (

                    revs_ids[0][:12], revs_ids[-1][:12]

                ),

                url('changeset_home', repo_name=repo_name,

                    revision=_rev

                ),

                _('compare view')

            )

        )

        # if we have exactly one more than normally displayed

        # just display it, takes less space than displaying

        # "and 1 more revisions"

        if len(revs_ids) == revs_limit + 1:

            cs_links.append(", " + lnk(revs[revs_limit], repo_name))

        # hidden-by-default ones

        if len(revs_ids) > revs_limit + 1:

            uniq_id = revs_ids[0]

            html_tmpl = (

                '<span> %s <a class="show_more" id="_%s" '

                'href="#more">%s</a> %s</span>'

            )

            if not feed:

                cs_links.append(html_tmpl % (

                      _('and'),

                      uniq_id, _('%s more') % (len(revs_ids) - revs_limit),

                      _('revisions')

                    )

                )

            if not feed:

                html_tmpl = '<span id="%s" style="display:none">, %s </span>'

            else:

                html_tmpl = '<span id="%s"> %s </span>'

            morelinks = ', '.join(

              [lnk(rev, repo_name) for rev in revs[revs_limit:]]

            )

            if len(revs_ids) > revs_top_limit:

                morelinks += ', ...'

            cs_links.append(html_tmpl % (uniq_id, morelinks))

        if len(revs) > 1:

            cs_links.append(compare_view)

        return ''.join(cs_links)

    def get_fork_name():

        repo_name = action_params

        _url = url('summary_home', repo_name=repo_name)

        return _('fork name %s') % link_to(action_params, _url)

    def get_user_name():

        user_name = action_params

        return user_name

    def get_users_group():

        group_name = action_params

        return group_name

    def get_pull_request():

        pull_request_id = action_params

        deleted = user_log.repository is None

        if deleted:

            repo_name = user_log.repository_name

        else:

            repo_name = user_log.repository.repo_name

        return link_to(_('Pull request #%s') % pull_request_id,

                    url('pullrequest_show', repo_name=repo_name,

                    pull_request_id=pull_request_id))

    def get_archive_name():

        archive_name = action_params

        return archive_name

    # action : translated str, callback(extractor), icon

    action_map = {

    'user_deleted_repo':           (_('[deleted] repository'),

        return res;

    };

}

/**

 * A customized version of PyRoutes.JS from https://pypi.python.org/pypi/pyroutes.js/

 * which is copyright Stephane Klein and was made available under the BSD License.

 *

 * Usage pyroutes.url('mark_error_fixed',{"error_id":error_id}) // /mark_error_fixed/<error_id>

 */

var pyroutes = (function() {

    // access global map defined in special file pyroutes

    var matchlist = PROUTES_MAP;

    var sprintf = (function() {

        function get_type(variable) {

            return Object.prototype.toString.call(variable).slice(8, -1).toLowerCase();

        }

        function str_repeat(input, multiplier) {

            for (var output = []; multiplier > 0; output[--multiplier] = input) {/* do nothing */}

            return output.join('');

        }

        var str_format = function() {

            if (!str_format.cache.hasOwnProperty(arguments[0])) {

                str_format.cache[arguments[0]] = str_format.parse(arguments[0]);

            }

            return str_format.format.call(null, str_format.cache[arguments[0]], arguments);

        };

        str_format.format = function(parse_tree, argv) {

            var cursor = 1, tree_length = parse_tree.length, node_type = '', arg, output = [], i, k, match, pad, pad_character, pad_length;

            for (i = 0; i < tree_length; i++) {

                node_type = get_type(parse_tree[i]);

                if (node_type === 'string') {

                    output.push(parse_tree[i]);

                }

                else if (node_type === 'array') {

                    match = parse_tree[i]; // convenience purposes only

                    if (match[2]) { // keyword argument

                        arg = argv[cursor];

                        for (k = 0; k < match[2].length; k++) {

                            if (!arg.hasOwnProperty(match[2][k])) {

                                throw(sprintf('[sprintf] property "%s" does not exist', match[2][k]));

                            }

                            arg = arg[match[2][k]];

                        }

                    }

                    else if (match[1]) { // positional argument (explicit)

                        arg = argv[match[1]];

                    }

                    else { // positional argument (implicit)

                        arg = argv[cursor++];

                    }

                    if (/[^s]/.test(match[8]) && (get_type(arg) != 'number')) {

                        throw(sprintf('[sprintf] expecting number but found %s', get_type(arg)));

                    }

                    switch (match[8]) {

                        case 'b': arg = arg.toString(2); break;

                        case 'c': arg = String.fromCharCode(arg); break;

                        case 'd': arg = parseInt(arg, 10); break;

                        case 'e': arg = match[7] ? arg.toExponential(match[7]) : arg.toExponential(); break;

                        case 'f': arg = match[7] ? parseFloat(arg).toFixed(match[7]) : parseFloat(arg); break;

                        case 'o': arg = arg.toString(8); break;

                        case 's': arg = ((arg = String(arg)) && match[7] ? arg.substring(0, match[7]) : arg); break;

                        case 'u': arg = Math.abs(arg); break;

                        case 'x': arg = arg.toString(16); break;

                        case 'X': arg = arg.toString(16).toUpperCase(); break;

                    }

                    arg = (/[def]/.test(match[8]) && match[3] && arg >= 0 ? '+'+ arg : arg);

                    pad_character = match[4] ? match[4] == '0' ? '0' : match[4].charAt(1) : ' ';

                    pad_length = match[6] - String(arg).length;

                    pad = match[6] ? str_repeat(pad_character, pad_length) : '';

                    output.push(match[5] ? arg + pad : pad + arg);

                }

            }

            return output.join('');

        };

        str_format.cache = {};

        str_format.parse = function(fmt) {

            var _fmt = fmt, match = [], parse_tree = [], arg_names = 0;

            while (_fmt) {

                if ((match = /^[^\x25]+/.exec(_fmt)) !== null) {

                    parse_tree.push(match[0]);

                }

                else if ((match = /^\x25{2}/.exec(_fmt)) !== null) {

                    parse_tree.push('%');

                }

                else if ((match = /^\x25(?:([1-9]\d*)\$|\(([^\)]+)\))?(\+)?(0|'[^$])?(-)?(\d+)?(?:\.(\d+))?([b-fosuxX])/.exec(_fmt)) !== null) {

                    if (match[2]) {

                        arg_names |= 1;

                        var field_list = [], replacement_field = match[2], field_match = [];

                        if ((field_match = /^([a-z_][a-z_\d]*)/i.exec(replacement_field)) !== null) {

                            field_list.push(field_match[1]);

                            while ((replacement_field = replacement_field.substring(field_match[0].length)) !== '') {

                                if ((field_match = /^\.([a-z_][a-z_\d]*)/i.exec(replacement_field)) !== null) {

                                    field_list.push(field_match[1]);

                                }

                                else if ((field_match = /^\[(\d+)\]/.exec(replacement_field)) !== null) {

                                    field_list.push(field_match[1]);

                                }

                                else {

                                    throw('[sprintf] huh?');

                                }

                            }

                        }

                        else {

                            throw('[sprintf] huh?');

                        }

                        match[2] = field_list;

                    }