.. _upgrade:

Upgrade

=======

Upgrading from Cheese Shop

--------------------------

.. note::

   Firstly, it is recommended that you **always** perform a database backup 

   before doing an upgrade.

The easiest way to upgrade ``rhodecode`` is to run::

 easy_install -U rhodecode

Or::

 pip install --upgrade rhodecode

Then make sure you run the following command from the installation directory::

 paster make-config RhodeCode production.ini

This will display any changes made by the new version of RhodeCode to your

current configuration. It will try to perform an automerge. It's always better

to make a backup of your configuration file before hand and recheck the 

content after the automerge.

.. note::

It is also recommended that you rebuild the whoosh index after upgrading since 

The final step is to upgrade the database. To do this simply run::

    paster upgrade-db production.ini

This will upgrade the schema and update some of the defaults in the database,

and will always recheck the settings of the application, if there are no new 

options that need to be set.

.. _virtualenv: http://pypi.python.org/pypi/virtualenv  

.. _python: http://www.python.org/

.. _mercurial: http://mercurial.selenic.com/

.. _celery: http://celeryproject.org/

.. _rabbitmq: http://www.rabbitmq.com/

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

"""

    rhodecode.controllers.changeset

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    changeset controller for pylons showoing changes beetween

    revisions

    :created_on: Apr 25, 2010

    :author: marcink

    :copyright: (C) 2010-2012 Marcin Kuzminski <marcin@python-works.com>

    :license: GPLv3, see COPYING for more details.

"""

# 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/>.

import logging

import traceback

from collections import defaultdict

from webob.exc import HTTPForbidden

from pylons import tmpl_context as c, url, request, response

from pylons.i18n.translation import _

from pylons.controllers.util import redirect

from pylons.decorators import jsonify

from rhodecode.lib.vcs.exceptions import RepositoryError, ChangesetError, \

    ChangesetDoesNotExistError

from rhodecode.lib.vcs.nodes import FileNode

import rhodecode.lib.helpers as h

from rhodecode.lib.auth import LoginRequired, HasRepoPermissionAnyDecorator

from rhodecode.lib.base import BaseRepoController, render

from rhodecode.lib.utils import EmptyChangeset

from rhodecode.lib.compat import OrderedDict

from rhodecode.lib import diffs

from rhodecode.model.db import ChangesetComment

from rhodecode.model.comment import ChangesetCommentsModel

from rhodecode.model.meta import Session

from rhodecode.lib.diffs import wrapped_diff

log = logging.getLogger(__name__)

def anchor_url(revision, path):

    fid = h.FID(revision, path)

def get_ignore_ws(fid, GET):

    ig_ws_global = request.GET.get('ignorews')

    ig_ws = filter(lambda k: k.startswith('WS'), GET.getall(fid))

    if ig_ws:

        try:

            return int(ig_ws[0].split(':')[-1])

        except:

            pass

    return ig_ws_global

def _ignorews_url(fileid=None):

    params = defaultdict(list)

    lbl = _('show white space')

    ig_ws = get_ignore_ws(fileid, request.GET)

    ln_ctx = get_line_ctx(fileid, request.GET)

    # global option

    if fileid is None:

        if ig_ws is None:

            params['ignorews'] += [1]

            lbl = _('ignore white space')

        ctx_key = 'context'

        ctx_val = ln_ctx

    # per file options

    else:

        if ig_ws is None:

            params[fileid] += ['WS:1']

            lbl = _('ignore white space')

        ctx_key = fileid

        ctx_val = 'C:%s' % ln_ctx

    # if we have passed in ln_ctx pass it along to our params

    if ln_ctx:

        params[ctx_key] += [ctx_val]

    params['anchor'] = fileid

    img = h.image(h.url('/images/icons/text_strikethrough.png'), lbl, class_='icon')

    return h.link_to(img, h.url.current(**params), title=lbl, class_='tooltip')

def get_line_ctx(fid, GET):

    ln_ctx_global = request.GET.get('context')

    ln_ctx = filter(lambda k: k.startswith('C'), GET.getall(fid))

    if ln_ctx:

        retval = ln_ctx[0].split(':')[-1]

    else:

        retval = ln_ctx_global

    try:

        return int(retval)

    except:

        return

def _context_url(fileid=None):

    """

    Generates url for context lines

    :param fileid:

    """

    ig_ws = get_ignore_ws(fileid, request.GET)

    ln_ctx = (get_line_ctx(fileid, request.GET) or 3) * 2

    params = defaultdict(list)

    # global option

    if fileid is None:

        if ln_ctx > 0:

            params['context'] += [ln_ctx]

        if ig_ws:

            ig_ws_key = 'ignorews'

            ig_ws_val = 1

    # per file option

    else:

        params[fileid] += ['C:%s' % ln_ctx]

        ig_ws_key = fileid

        ig_ws_val = 'WS:%s' % 1

    if ig_ws:

        params[ig_ws_key] += [ig_ws_val]

    lbl = _('%s line context') % ln_ctx

    params['anchor'] = fileid

    img = h.image(h.url('/images/icons/table_add.png'), lbl, class_='icon')

    return h.link_to(img, h.url.current(**params), title=lbl, class_='tooltip')

class ChangesetController(BaseRepoController):

    @LoginRequired()

    @HasRepoPermissionAnyDecorator('repository.read', 'repository.write',

                                   'repository.admin')

    def __before__(self):

        super(ChangesetController, self).__before__()

        c.affected_files_cut_off = 60

    def index(self, revision):

        c.anchor_url = anchor_url

        c.ignorews_url = _ignorews_url

        c.context_url = _context_url

        #get ranges of revisions if preset

        rev_range = revision.split('...')[:2]

        enable_comments = True

        try:

            if len(rev_range) == 2:

                enable_comments = False

                rev_start = rev_range[0]

                rev_end = rev_range[1]

                rev_ranges = c.rhodecode_repo.get_changesets(start=rev_start,

                                                            end=rev_end)

            else:

                rev_ranges = [c.rhodecode_repo.get_changeset(revision)]

            c.cs_ranges = list(rev_ranges)

            if not c.cs_ranges:

                raise RepositoryError('Changeset range returned empty result')

        except (RepositoryError, ChangesetDoesNotExistError, Exception), e:

            log.error(traceback.format_exc())

            h.flash(str(e), category='warning')

            return redirect(url('home'))

        c.changes = OrderedDict()

        c.lines_added = 0  # count of lines added

        c.lines_deleted = 0  # count of lines removes

        cumulative_diff = 0

        c.cut_off = False  # defines if cut off limit is reached

        c.comments = []

        c.inline_comments = []

        c.inline_cnt = 0

        # Iterate over ranges (default changeset view is always one changeset)

        for changeset in c.cs_ranges:

            c.comments.extend(ChangesetCommentsModel()\

                              .get_comments(c.rhodecode_db_repo.repo_id,

                                            changeset.raw_id))

            inlines = ChangesetCommentsModel()\

                        .get_inline_comments(c.rhodecode_db_repo.repo_id,

                                             changeset.raw_id)

            c.inline_comments.extend(inlines)

            c.changes[changeset.raw_id] = []

            try:

                changeset_parent = changeset.parents[0]

            except IndexError:

                changeset_parent = None

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

            # ADDED FILES

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

            for node in changeset.added:

                fid = h.FID(revision, node.path)

                line_context_lcl = get_line_ctx(fid, request.GET)

                ign_whitespace_lcl = get_ignore_ws(fid, request.GET)

                lim = self.cut_off_limit

                if cumulative_diff > self.cut_off_limit:

                    lim = -1

                size, cs1, cs2, diff, st = wrapped_diff(filenode_old=None,

                                         filenode_new=node,

                                         cut_off_limit=lim,

                                         ignore_whitespace=ign_whitespace_lcl,

                                         line_context=line_context_lcl,

                                         enable_comments=enable_comments)

                cumulative_diff += size

                c.lines_added += st[0]

                c.lines_deleted += st[1]

                c.changes[changeset.raw_id].append(('added', node, diff,

                                                    cs1, cs2, st))

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

            # CHANGED FILES

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

            for node in changeset.changed:

                try:

                    filenode_old = changeset_parent.get_node(node.path)

                except ChangesetError:

                    log.warning('Unable to fetch parent node for diff')

                    filenode_old = FileNode(node.path, '', EmptyChangeset())

                fid = h.FID(revision, node.path)

                line_context_lcl = get_line_ctx(fid, request.GET)

                ign_whitespace_lcl = get_ignore_ws(fid, request.GET)

                lim = self.cut_off_limit

                if cumulative_diff > self.cut_off_limit:

                    lim = -1

                size, cs1, cs2, diff, st = wrapped_diff(filenode_old=filenode_old,

                                         filenode_new=node,

                                         cut_off_limit=lim,

                                         ignore_whitespace=ign_whitespace_lcl,

                                         line_context=line_context_lcl,

                                         enable_comments=enable_comments)

                cumulative_diff += size

                c.lines_added += st[0]

                c.lines_deleted += st[1]

                c.changes[changeset.raw_id].append(('changed', node, diff,

                                                    cs1, cs2, st))

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

            # REMOVED FILES

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

            for node in changeset.removed:

                c.changes[changeset.raw_id].append(('removed', node, None,

                                                    None, None, (0, 0)))

        # count inline comments

        for path, lines in c.inline_comments:

            for comments in lines.values():

                c.inline_cnt += len(comments)

        if len(c.cs_ranges) == 1:

            c.changeset = c.cs_ranges[0]

            c.changes = c.changes[c.changeset.raw_id]

            return render('changeset/changeset.html')

        else:

            return render('changeset/changeset_range.html')

    def raw_changeset(self, revision):

        method = request.GET.get('diff', 'show')

        ignore_whitespace = request.GET.get('ignorews') == '1'

        line_context = request.GET.get('context', 3)

        try:

            c.scm_type = c.rhodecode_repo.alias

            c.changeset = c.rhodecode_repo.get_changeset(revision)

        except RepositoryError:

            log.error(traceback.format_exc())

            return redirect(url('home'))

        else:

            try:

                c.changeset_parent = c.changeset.parents[0]

            except IndexError:

                c.changeset_parent = None

            c.changes = []

            for node in c.changeset.added:

                filenode_old = FileNode(node.path, '')

                if filenode_old.is_binary or node.is_binary:

                    diff = _('binary file') + '\n'

                else:

                    f_gitdiff = diffs.get_gitdiff(filenode_old, node,

                                           ignore_whitespace=ignore_whitespace,

                                           context=line_context)

                    diff = diffs.DiffProcessor(f_gitdiff,

                                                format='gitdiff').raw_diff()

                cs1 = None

                cs2 = node.last_changeset.raw_id

                c.changes.append(('added', node, diff, cs1, cs2))

            for node in c.changeset.changed:

                filenode_old = c.changeset_parent.get_node(node.path)

                if filenode_old.is_binary or node.is_binary:

                    diff = _('binary file')

                else:

                    f_gitdiff = diffs.get_gitdiff(filenode_old, node,

                                           ignore_whitespace=ignore_whitespace,

                                           context=line_context)

                    diff = diffs.DiffProcessor(f_gitdiff,

                                                format='gitdiff').raw_diff()

                cs1 = filenode_old.last_changeset.raw_id

                cs2 = node.last_changeset.raw_id

                c.changes.append(('changed', node, diff, cs1, cs2))

        response.content_type = 'text/plain'

        if method == 'download':

            response.content_disposition = 'attachment; filename=%s.patch' \

                                            % revision

        c.parent_tmpl = ''.join(['# Parent  %s\n' % x.raw_id for x in

                                                 c.changeset.parents])

        c.diffs = ''

        for x in c.changes:

            c.diffs += x[2]

        return render('changeset/raw_changeset.html')

    def comment(self, repo_name, revision):

        ChangesetCommentsModel().create(text=request.POST.get('text'),

                                        repo_id=c.rhodecode_db_repo.repo_id,

                                        user_id=c.rhodecode_user.user_id,

                                        revision=revision,

                                        f_path=request.POST.get('f_path'),

                                        line_no=request.POST.get('line'))

        Session.commit()

        return redirect(h.url('changeset_home', repo_name=repo_name,

                              revision=revision))

    @jsonify

    def delete_comment(self, repo_name, comment_id):

        co = ChangesetComment.get(comment_id)

        owner = lambda: co.author.user_id == c.rhodecode_user.user_id

        if h.HasPermissionAny('hg.admin', 'repository.admin')() or owner:

            ChangesetCommentsModel().delete(comment=co)

            Session.commit()

            return True

        else:

            raise HTTPForbidden()

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

"""

    rhodecode.controllers.summary

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    Summary controller for Rhodecode

    :created_on: Apr 18, 2010

    :author: marcink

    :copyright: (C) 2010-2012 Marcin Kuzminski <marcin@python-works.com>

    :license: GPLv3, see COPYING for more details.

"""

# 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/>.

import traceback

import calendar

import logging

from time import mktime

from datetime import timedelta, date

from urlparse import urlparse

from rhodecode.lib.vcs.exceptions import ChangesetError, EmptyRepositoryError, \

    NodeDoesNotExistError

from pylons import tmpl_context as c, request, url, config

from pylons.i18n.translation import _

from beaker.cache import cache_region, region_invalidate

from rhodecode.model.db import Statistics, CacheInvalidation

from rhodecode.lib import ALL_READMES, ALL_EXTS

from rhodecode.lib.auth import LoginRequired, HasRepoPermissionAnyDecorator

from rhodecode.lib.base import BaseRepoController, render

from rhodecode.lib.utils import EmptyChangeset

from rhodecode.lib.markup_renderer import MarkupRenderer

from rhodecode.lib.celerylib import run_task

from rhodecode.lib.celerylib.tasks import get_commits_stats, \

    LANGUAGES_EXTENSIONS_MAP

from rhodecode.lib.helpers import RepoPage

from rhodecode.lib.compat import json, OrderedDict

log = logging.getLogger(__name__)

README_FILES = [''.join([x[0][0], x[1][0]]) for x in

                    sorted(list(product(ALL_READMES, ALL_EXTS)),

                           key=lambda y:y[0][1] + y[1][1])]

class SummaryController(BaseRepoController):

    @LoginRequired()

    @HasRepoPermissionAnyDecorator('repository.read', 'repository.write',

                                   'repository.admin')

    def __before__(self):

        super(SummaryController, self).__before__()

    def index(self, repo_name):

        c.dbrepo = dbrepo = c.rhodecode_db_repo

        c.following = self.scm_model.is_following_repo(repo_name,

                                                self.rhodecode_user.user_id)

        def url_generator(**kw):

            return url('shortlog_home', repo_name=repo_name, size=10, **kw)

        c.repo_changesets = RepoPage(c.rhodecode_repo, page=1,

                                     items_per_page=10, url=url_generator)

        if self.rhodecode_user.username == 'default':

            # for default(anonymous) user we don't need to pass credentials

            username = ''

            password = ''

        else:

            username = str(self.rhodecode_user.username)

            password = '@'

        parsed_url = urlparse(url.current(qualified=True))

        default_clone_uri = '{scheme}://{user}{pass}{netloc}{path}'

        uri_tmpl = config.get('clone_uri', default_clone_uri)

        uri_tmpl = uri_tmpl.replace('{', '%(').replace('}', ')s')

        uri_dict = {

           'user': username,

           'pass': password,

           'scheme': parsed_url.scheme,

           'netloc': parsed_url.netloc,

           'path': parsed_url.path

        }

        uri = uri_tmpl % uri_dict

        # generate another clone url by id

        uri_dict.update({'path': '/_%s' % c.dbrepo.repo_id})

        uri_id = uri_tmpl % uri_dict

        c.clone_repo_url = uri

        c.clone_repo_url_id = uri_id

        c.repo_tags = OrderedDict()

        for name, hash in c.rhodecode_repo.tags.items()[:10]:

            try:

                c.repo_tags[name] = c.rhodecode_repo.get_changeset(hash)

            except ChangesetError:

                c.repo_tags[name] = EmptyChangeset(hash)

        c.repo_branches = OrderedDict()

        for name, hash in c.rhodecode_repo.branches.items()[:10]:

            try:

                c.repo_branches[name] = c.rhodecode_repo.get_changeset(hash)

            except ChangesetError:

                c.repo_branches[name] = EmptyChangeset(hash)

        td = date.today() + timedelta(days=1)

        td_1m = td - timedelta(days=calendar.mdays[td.month])

        td_1y = td - timedelta(days=365)

        ts_min_m = mktime(td_1m.timetuple())

        ts_min_y = mktime(td_1y.timetuple())

        ts_max_y = mktime(td.timetuple())

        if dbrepo.enable_statistics:

            c.show_stats = True

            c.no_data_msg = _('No data loaded yet')

            run_task(get_commits_stats, c.dbrepo.repo_name, ts_min_y, ts_max_y)

        else:

            c.show_stats = False

            c.no_data_msg = _('Statistics are disabled for this repository')

        c.ts_min = ts_min_m

        c.ts_max = ts_max_y

        stats = self.sa.query(Statistics)\

            .filter(Statistics.repository == dbrepo)\

            .scalar()

        c.stats_percentage = 0

        if stats and stats.languages:

            c.no_data = False is dbrepo.enable_statistics

            lang_stats_d = json.loads(stats.languages)

            c.commit_data = stats.commit_activity

            c.overview_data = stats.commit_activity_combined

            lang_stats = ((x, {"count": y,

                               "desc": LANGUAGES_EXTENSIONS_MAP.get(x)})

                          for x, y in lang_stats_d.items())

            c.trending_languages = json.dumps(

                sorted(lang_stats, reverse=True, key=lambda k: k[1])[:10]

            )

            last_rev = stats.stat_on_revision + 1

            c.repo_last_rev = c.rhodecode_repo.count()\

                if c.rhodecode_repo.revisions else 0

            if last_rev == 0 or c.repo_last_rev == 0:

                pass

            else:

                c.stats_percentage = '%.2f' % ((float((last_rev)) /

                                                c.repo_last_rev) * 100)

        else:

            c.commit_data = json.dumps({})

            c.overview_data = json.dumps([[ts_min_y, 0], [ts_max_y, 10]])

            c.trending_languages = json.dumps({})

            c.no_data = True

        c.enable_downloads = dbrepo.enable_downloads

        if c.enable_downloads:

            c.download_options = self._get_download_links(c.rhodecode_repo)

        c.readme_data, c.readme_file = self.__get_readme_data(c.rhodecode_repo)

        return render('summary/summary.html')

    def __get_readme_data(self, repo):

        @cache_region('long_term')

        def _get_readme_from_cache(key):

            readme_data = None

            readme_file = None

            log.debug('Fetching readme file')

            try:

                cs = repo.get_changeset('tip')

                renderer = MarkupRenderer()

                for f in README_FILES:

                    try:

                        readme = cs.get_node(f)

                        readme_file = f

                        readme_data = renderer.render(readme.content, f)

                        log.debug('Found readme %s' % readme_file)

                        break

                    except NodeDoesNotExistError:

                        continue

            except ChangesetError:

                pass

            except EmptyRepositoryError:

                pass

            except Exception:

                log.error(traceback.format_exc())

            return readme_data, readme_file

        key = repo.name + '_README'

        inv = CacheInvalidation.invalidate(key)

        if inv is not None:

            region_invalidate(_get_readme_from_cache, None, key)

            CacheInvalidation.set_valid(inv.cache_key)

        return _get_readme_from_cache(key)

    def _get_download_links(self, repo):

        download_l = []

        branches_group = ([], _("Branches"))

        tags_group = ([], _("Tags"))

        for name, chs in c.rhodecode_repo.branches.items():

            #chs = chs.split(':')[-1]

            branches_group[0].append((chs, name),)

        download_l.append(branches_group)

        for name, chs in c.rhodecode_repo.tags.items():

            #chs = chs.split(':')[-1]

            tags_group[0].append((chs, name),)

        download_l.append(tags_group)

        return download_l

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

"""

    rhodecode.lib.compat

    ~~~~~~~~~~~~~~~~~~~~

    Python backward compatibility functions and common libs

    :created_on: Oct 7, 2011

    :author: marcink

    :copyright: (C) 2010-2010 Marcin Kuzminski <marcin@python-works.com>

    :license: GPLv3, see COPYING for more details.

"""

# 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/>.

import os

from rhodecode import __platform__, PLATFORM_WIN

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

# json

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

try:

    import json

except ImportError:

    import simplejson as json

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

# izip_longest

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

try:

    from itertools import izip_longest

except ImportError:

    import itertools

    def izip_longest(*args, **kwds): # noqa

        fillvalue = kwds.get("fillvalue")

        def sentinel(counter=([fillvalue] * (len(args) - 1)).pop):

            yield counter() # yields the fillvalue, or raises IndexError

        fillers = itertools.repeat(fillvalue)

        iters = [itertools.chain(it, sentinel(), fillers)

                    for it in args]

        try:

            for tup in itertools.izip(*iters):

                yield tup

        except IndexError:

            pass

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

# OrderedDict

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

# Python Software Foundation License

# XXX: it feels like using the class with "is" and "is not" instead of "==" and

# "!=" should be faster.

class _Nil(object):

    def __repr__(self):

        return "nil"

    def __eq__(self, other):

        if (isinstance(other, _Nil)):

            return True

        else:

            return NotImplemented

    def __ne__(self, other):

        if (isinstance(other, _Nil)):

            return False

        else:

            return NotImplemented

_nil = _Nil()

class _odict(object):

    """Ordered dict data structure, with O(1) complexity for dict operations

    that modify one element.

    Overwriting values doesn't change their original sequential order.

    """

    def _dict_impl(self):

        return None

    def __init__(self, data=(), **kwds):

        """This doesn't accept keyword initialization as normal dicts to avoid

        a trap - inside a function or method the keyword args are accessible

        only as a dict, without a defined order, so their original order is

        lost.

        """

        if kwds:

            raise TypeError("__init__() of ordered dict takes no keyword "

                            "arguments to avoid an ordering trap.")

        self._dict_impl().__init__(self)

        # If you give a normal dict, then the order of elements is undefined

        if hasattr(data, "iteritems"):

            for key, val in data.iteritems():

                self[key] = val

        else:

            for key, val in data:

                self[key] = val

    # Double-linked list header

    def _get_lh(self):

        dict_impl = self._dict_impl()

        if not hasattr(self, '_lh'):

            dict_impl.__setattr__(self, '_lh', _nil)

        return dict_impl.__getattribute__(self, '_lh')

    def _set_lh(self, val):

        self._dict_impl().__setattr__(self, '_lh', val)

    lh = property(_get_lh, _set_lh)

    # Double-linked list tail

    def _get_lt(self):

        dict_impl = self._dict_impl()

        if not hasattr(self, '_lt'):

            dict_impl.__setattr__(self, '_lt', _nil)

        return dict_impl.__getattribute__(self, '_lt')

    def _set_lt(self, val):

        self._dict_impl().__setattr__(self, '_lt', val)

    lt = property(_get_lt, _set_lt)

    def __getitem__(self, key):

        return self._dict_impl().__getitem__(self, key)[1]

    def __setitem__(self, key, val):

        dict_impl = self._dict_impl()

        try:

            dict_impl.__getitem__(self, key)[1] = val

        except KeyError:

            new = [dict_impl.__getattribute__(self, 'lt'), val, _nil]

            dict_impl.__setitem__(self, key, new)

            if dict_impl.__getattribute__(self, 'lt') == _nil:

                dict_impl.__setattr__(self, 'lh', key)

            else:

                dict_impl.__getitem__(

                    self, dict_impl.__getattribute__(self, 'lt'))[2] = key

            dict_impl.__setattr__(self, 'lt', key)

    def __delitem__(self, key):

        dict_impl = self._dict_impl()

        pred, _, succ = self._dict_impl().__getitem__(self, key)

        if pred == _nil:

            dict_impl.__setattr__(self, 'lh', succ)

        else:

            dict_impl.__getitem__(self, pred)[2] = succ

        if succ == _nil:

            dict_impl.__setattr__(self, 'lt', pred)

        else:

            dict_impl.__getitem__(self, succ)[0] = pred

        dict_impl.__delitem__(self, key)

    def __contains__(self, key):

        return key in self.keys()

    def __len__(self):

        return len(self.keys())

    def __str__(self):

        pairs = ("%r: %r" % (k, v) for k, v in self.iteritems())

        return "{%s}" % ", ".join(pairs)

    def __repr__(self):

        if self:

            pairs = ("(%r, %r)" % (k, v) for k, v in self.iteritems())

            return "odict([%s])" % ", ".join(pairs)

        else:

            return "odict()"

    def get(self, k, x=None):

        if k in self:

            return self._dict_impl().__getitem__(self, k)[1]

        else:

            return x

    def __iter__(self):

        dict_impl = self._dict_impl()

        curr_key = dict_impl.__getattribute__(self, 'lh')

        while curr_key != _nil:

            yield curr_key