summaryrefslogtreecommitdiff
path: root/src/leap
diff options
context:
space:
mode:
Diffstat (limited to 'src/leap')
-rw-r--r--src/leap/base/auth.py87
-rwxr-xr-xsrc/leap/gui/firstrunwizard.py489
-rw-r--r--src/leap/util/dicts.py258
3 files changed, 670 insertions, 164 deletions
diff --git a/src/leap/base/auth.py b/src/leap/base/auth.py
new file mode 100644
index 00000000..c34ad39b
--- /dev/null
+++ b/src/leap/base/auth.py
@@ -0,0 +1,87 @@
+import binascii
+import logging
+
+import requests
+import srp
+
+from leap.base import constants as baseconstants
+
+logger = logging.getLogger(__name__)
+
+SIGNUP_TIMEOUT = getattr(baseconstants, 'SIGNUP_TIMEOUT', 5)
+
+
+class LeapSRPRegister(object):
+
+ def __init__(self,
+ schema="https",
+ provider=None,
+ port=None,
+ register_path="1/users.json",
+ method="POST",
+ fetcher=requests,
+ srp=srp,
+ hashfun=srp.SHA256,
+ ng_constant=srp.NG_1024):
+
+ self.schema = schema
+ self.provider = provider
+ self.port = port
+ self.register_path = register_path
+ self.method = method
+ self.fetcher = fetcher
+ self.srp = srp
+ self.HASHFUN = hashfun
+ self.NG = ng_constant
+
+ self.init_session()
+
+ def init_session(self):
+ self.session = self.fetcher.session()
+
+ def get_registration_uri(self):
+ # XXX assert is https!
+ # use urlparse
+ if self.port:
+ uri = "%s://%s:%s/%s" % (
+ self.schema,
+ self.provider,
+ self.port,
+ self.register_path)
+ else:
+ uri = "%s://%s/%s" % (
+ self.schema,
+ self.provider,
+ self.register_path)
+
+ return uri
+
+ def register_user(self, username, password, keep=False):
+ """
+ @rtype: tuple
+ @rparam: (ok, request)
+ """
+ salt, vkey = self.srp.create_salted_verification_key(
+ username,
+ password,
+ self.HASHFUN,
+ self.NG)
+
+ user_data = {
+ 'user[login]': username,
+ 'user[password_verifier]': binascii.hexlify(vkey),
+ 'user[password_salt]': binascii.hexlify(salt)}
+
+ uri = self.get_registration_uri()
+ logger.debug('post to uri: %s' % uri)
+
+ # XXX get self.method
+ req = self.session.post(
+ uri, data=user_data,
+ timeout=SIGNUP_TIMEOUT)
+ logger.debug(req)
+ logger.debug('user_data: %s', user_data)
+ #logger.debug('response: %s', req.text)
+ # we catch it in the form
+ #req.raise_for_status()
+ return (req.ok, req)
diff --git a/src/leap/gui/firstrunwizard.py b/src/leap/gui/firstrunwizard.py
index a76865fd..bc36a35f 100755
--- a/src/leap/gui/firstrunwizard.py
+++ b/src/leap/gui/firstrunwizard.py
@@ -10,101 +10,23 @@ sip.setapi('QVariant', 2)
from PyQt4 import QtCore
from PyQt4 import QtGui
+from leap.base.auth import LeapSRPRegister
from leap.crypto import leapkeyring
from leap.gui import mainwindow_rc
+try:
+ from collections import OrderedDict
+except ImportError:
+ # We must be in 2.6
+ from leap.util.dicts import OrderedDict
+
+# XXX DEBUG
+logging.basicConfig()
logger = logging.getLogger(__name__)
+logger.setLevel(logging.DEBUG)
APP_LOGO = ':/images/leap-color-small.png'
-# registration ######################
-# move to base/
-import binascii
-
-import requests
-import srp
-
-from leap.base import constants as baseconstants
-
-SIGNUP_TIMEOUT = getattr(baseconstants, 'SIGNUP_TIMEOUT', 5)
-
-
-class LeapSRPRegister(object):
-
- def __init__(self,
- schema="https",
- provider=None,
- port=None,
- register_path="1/users.json",
- method="POST",
- fetcher=requests,
- srp=srp,
- hashfun=srp.SHA256,
- ng_constant=srp.NG_1024):
-
- self.schema = schema
- self.provider = provider
- self.port = port
- self.register_path = register_path
- self.method = method
- self.fetcher = fetcher
- self.srp = srp
- self.HASHFUN = hashfun
- self.NG = ng_constant
-
- self.init_session()
-
- def init_session(self):
- self.session = self.fetcher.session()
-
- def get_registration_uri(self):
- # XXX assert is https!
- # use urlparse
- if self.port:
- uri = "%s://%s:%s/%s" % (
- self.schema,
- self.provider,
- self.port,
- self.register_path)
- else:
- uri = "%s://%s/%s" % (
- self.schema,
- self.provider,
- self.register_path)
-
- return uri
-
- def register_user(self, username, password, keep=False):
- """
- @rtype: tuple
- @rvalue: (ok, request)
- """
- salt, vkey = self.srp.create_salted_verification_key(
- username,
- password,
- self.HASHFUN,
- self.NG)
-
- user_data = {
- 'user[login]': username,
- 'user[password_verifier]': binascii.hexlify(vkey),
- 'user[password_salt]': binascii.hexlify(salt)}
-
- uri = self.get_registration_uri()
- logger.debug('post to uri: %s' % uri)
-
- # XXX get self.method
- req = self.session.post(
- uri, data=user_data,
- timeout=SIGNUP_TIMEOUT)
- logger.debug(req)
- logger.debug('user_data: %s', user_data)
- #logger.debug('response: %s', req.text)
- # we catch it in the form
- #req.raise_for_status()
- return (req.ok, req)
-
-######################################
ErrorLabelStyleSheet = """
QLabel { color: red;
@@ -116,25 +38,48 @@ class FirstRunWizard(QtGui.QWizard):
def __init__(
self, parent=None, providers=None,
- success_cb=None):
+ success_cb=None, is_provider_setup=False,
+ is_previously_registered=False):
super(FirstRunWizard, self).__init__(
parent,
QtCore.Qt.WindowStaysOnTopHint)
# XXX hardcoded for tests
- if not providers:
- providers = ('springbok',)
+ #if not providers:
+ #providers = ('springbok',)
self.providers = providers
# success callback
self.success_cb = success_cb
- self.addPage(IntroPage())
- self.addPage(SelectProviderPage(providers=providers))
-
- self.addPage(RegisterUserPage(wizard=self))
- #self.addPage(GlobalEIPSettings())
- self.addPage(LastPage())
+ # is provider setup?
+ self.is_provider_setup = is_provider_setup
+
+ # previously registered
+ # if True, jumps to LogIn page.
+ self.is_previously_registered = is_previously_registered
+
+ # FIXME remove kwargs, we can access
+ # wizard as self.wizard()
+
+ # FIXME add param for previously_registered
+ # should start at login page.
+
+ pages_dict = OrderedDict((
+ # (name, (WizardPage, **kwargs))
+ ('intro', (IntroPage, {})),
+ ('providerselection', (
+ SelectProviderPage,
+ {'providers': providers})),
+ ('login', (LogInPage, {})),
+ ('providerinfo', (ProviderInfoPage, {})),
+ ('providersetup', (ProviderSetupPage, {})),
+ ('signup', (
+ RegisterUserPage, {})),
+ ('connecting', (ConnectingPage, {})),
+ ('lastpage', (LastPage, {}))
+ ))
+ self.add_pages_from_dict(pages_dict)
self.setPixmap(
QtGui.QWizard.BannerPixmap,
@@ -148,6 +93,28 @@ class FirstRunWizard(QtGui.QWizard):
# TODO: set style for MAC / windows ...
#self.setWizardStyle()
+ def add_pages_from_dict(self, pages_dict):
+ """
+ @param pages_dict: the dictionary with pages, where
+ values are a tuple of InstanceofWizardPage, kwargs.
+ @type pages_dict: dict
+ """
+ for name, (page, page_args) in pages_dict.items():
+ # XXX check for is_previously registered
+ # and skip adding the signup branch if so
+ self.addPage(page(**page_args))
+ self.pages_dict = pages_dict
+
+ def get_page_index(self, page_name):
+ """
+ returns the index of the given page
+ @param page_name: the name of the desired page
+ @type page_name: str
+ @rparam: index of page in wizard
+ @rtype: int
+ """
+ return self.pages_dict.keys().index(page_name)
+
def setWindowFlags(self, flags):
logger.debug('setting window flags')
QtGui.QWizard.setWindowFlags(self, flags)
@@ -195,7 +162,7 @@ class FirstRunWizard(QtGui.QWizard):
if cb and callable(cb):
self.success_cb()
- def get_provider(self):
+ def get_provider_by_index(self):
provider = self.field('provider_index')
return self.providers[provider]
@@ -218,20 +185,50 @@ class IntroPage(QtGui.QWizardPage):
#QtGui.QWizard.WatermarkPixmap,
#QtGui.QPixmap(':/images/watermark1.png'))
+ self.setPixmap(
+ QtGui.QWizard.LogoPixmap,
+ QtGui.QPixmap(APP_LOGO))
+
label = QtGui.QLabel(
"Now we will guide you through "
"some configuration that is needed before you "
"can connect for the first time.<br><br>"
"If you ever need to modify these options again, "
"you can find the wizard in the '<i>Settings</i>' menu from the "
- "main window of the Leap App.")
-
+ "main window.<br><br>"
+ "Do you want to <b>sign up</b> for a new account, or <b>log "
+ "in</b> with an already existing username?<br>")
label.setWordWrap(True)
+ self.sign_up = QtGui.QRadioButton(
+ "Sign up for a new account.")
+ self.sign_up.setChecked(True)
+ self.log_in = QtGui.QRadioButton(
+ "Log In with my credentials.")
+
layout = QtGui.QVBoxLayout()
layout.addWidget(label)
+ layout.addWidget(self.sign_up)
+ layout.addWidget(self.log_in)
self.setLayout(layout)
+ self.registerField('is_signup', self.sign_up)
+
+ def validatePage(self):
+ return True
+
+ def nextId(self):
+ """
+ returns next id
+ in a non-linear wizard
+ """
+ if self.sign_up.isChecked():
+ next_ = 'providerselection'
+ if self.log_in.isChecked():
+ next_ = 'login'
+ wizard = self.wizard()
+ return wizard.get_page_index(next_)
+
class SelectProviderPage(QtGui.QWizardPage):
def __init__(self, parent=None, providers=None):
@@ -239,7 +236,7 @@ class SelectProviderPage(QtGui.QWizardPage):
self.setTitle("Select Provider")
self.setSubTitle(
- "Please select which provider do you want "
+ "Please enter the domain of the provider you want "
"to use for your connection."
)
self.setPixmap(
@@ -247,90 +244,98 @@ class SelectProviderPage(QtGui.QWizardPage):
QtGui.QPixmap(APP_LOGO))
providerNameLabel = QtGui.QLabel("&Provider:")
+ providerNameEdit = QtGui.QLineEdit()
+ providerNameEdit.cursorPositionChanged.connect(
+ self.reset_validation_status)
+ providerNameLabel.setBuddy(providerNameEdit)
- providercombo = QtGui.QComboBox()
- if providers:
- for provider in providers:
- providercombo.addItem(provider)
- providerNameSelect = providercombo
+ # add regex validator
+ providerDomainRe = QtCore.QRegExp(r"^[a-z\d_-.]+$")
+ providerNameEdit.setValidator(
+ QtGui.QRegExpValidator(providerDomainRe, self))
+ self.providerNameEdit = providerNameEdit
+
+ # Eventually we will seed a list of
+ # well known providers here.
- providerNameLabel.setBuddy(providerNameSelect)
+ #providercombo = QtGui.QComboBox()
+ #if providers:
+ #for provider in providers:
+ #providercombo.addItem(provider)
+ #providerNameSelect = providercombo
- self.registerField('provider_index', providerNameSelect)
+ self.registerField('provider_domain*', self.providerNameEdit)
+ #self.registerField('provider_name_index', providerNameSelect)
+
+ validationMsg = QtGui.QLabel("")
+ validationMsg.setStyleSheet(ErrorLabelStyleSheet)
+
+ self.validationMsg = validationMsg
layout = QtGui.QGridLayout()
- layout.addWidget(providerNameLabel, 0, 0)
- layout.addWidget(providerNameSelect, 0, 1)
+ layout.addWidget(validationMsg, 0, 0)
+ layout.addWidget(providerNameLabel, 0, 1)
+ layout.addWidget(providerNameEdit, 0, 2)
self.setLayout(layout)
+ def reset_validation_status(self):
+ """
+ empty the validation msg
+ """
+ self.validationMsg.setText('')
-class RegisterUserPage(QtGui.QWizardPage):
- setSigningUpStatus = QtCore.pyqtSignal([])
+ def validatePage(self):
+ return True
- def __init__(self, parent=None, wizard=None):
- super(RegisterUserPage, self).__init__(parent)
+ def nextId(self):
+ wizard = self.wizard()
+ if not wizard:
+ return
+ return wizard.get_page_index('providerinfo')
- # bind wizard page signals
- self.setSigningUpStatus.connect(
- self.set_status_validating)
- # XXX check for no wizard pased
- # getting provider from previous step
- provider = wizard.get_provider()
+class ProviderInfoPage(QtGui.QWizardPage):
+ def __init__(self, parent=None):
+ super(ProviderInfoPage, self).__init__(parent)
+
+ self.setTitle("Provider Info")
+ self.setSubTitle("Available information about chosen provider.")
- self.setTitle("User registration")
- self.setSubTitle(
- "Register a new user with provider %s." %
- provider)
self.setPixmap(
QtGui.QWizard.LogoPixmap,
QtGui.QPixmap(APP_LOGO))
- rememberPasswordCheckBox = QtGui.QCheckBox(
- "&Remember password.")
- rememberPasswordCheckBox.setChecked(True)
-
- userNameLabel = QtGui.QLabel("User &name:")
- userNameLineEdit = QtGui.QLineEdit()
- userNameLineEdit.cursorPositionChanged.connect(
- self.reset_validation_status)
- userNameLabel.setBuddy(userNameLineEdit)
-
- # add regex validator
- usernameRe = QtCore.QRegExp(r"^[A-Za-z\d_]+$")
- userNameLineEdit.setValidator(
- QtGui.QRegExpValidator(usernameRe, self))
- self.userNameLineEdit = userNameLineEdit
-
- userPasswordLabel = QtGui.QLabel("&Password:")
- self.userPasswordLineEdit = QtGui.QLineEdit()
- self.userPasswordLineEdit.setEchoMode(
- QtGui.QLineEdit.Password)
+ def nextId(self):
+ wizard = self.wizard()
+ if not wizard:
+ return
+ return wizard.get_page_index('providersetup')
- userPasswordLabel.setBuddy(self.userPasswordLineEdit)
- self.registerField('userName', self.userNameLineEdit)
- self.registerField('userPassword', self.userPasswordLineEdit)
- self.registerField('rememberPassword', rememberPasswordCheckBox)
-
- layout = QtGui.QGridLayout()
- layout.setColumnMinimumWidth(0, 20)
-
- validationMsg = QtGui.QLabel("")
- validationMsg.setStyleSheet(ErrorLabelStyleSheet)
+class ProviderSetupPage(QtGui.QWizardPage):
+ def __init__(self, parent=None):
+ super(ProviderSetupPage, self).__init__(parent)
- self.validationMsg = validationMsg
+ self.setTitle("Provider Setup")
+ self.setSubTitle("Setting up provider.")
- layout.addWidget(validationMsg, 0, 3)
+ self.setPixmap(
+ QtGui.QWizard.LogoPixmap,
+ QtGui.QPixmap(APP_LOGO))
- layout.addWidget(userNameLabel, 1, 0)
- layout.addWidget(self.userNameLineEdit, 1, 3)
+ def nextId(self):
+ wizard = self.wizard()
+ if not wizard:
+ return
+ is_signup = self.field('is_signup')
+ if is_signup is True:
+ next_ = 'signup'
+ if is_signup is False:
+ next_ = 'connecting'
+ return wizard.get_page_index(next_)
- layout.addWidget(userPasswordLabel, 2, 0)
- layout.addWidget(self.userPasswordLineEdit, 2, 3)
- layout.addWidget(rememberPasswordCheckBox, 3, 3, 3, 4)
- self.setLayout(layout)
+class UserFormMixIn(object):
def reset_validation_status(self):
"""
@@ -352,6 +357,8 @@ class RegisterUserPage(QtGui.QWizardPage):
self.validationMsg.setText('registering...')
# need to call update somehow???
+ # XXX refactor set_status_foo
+
def set_status_invalid_username(self):
"""
set validation msg to
@@ -387,7 +394,130 @@ class RegisterUserPage(QtGui.QWizardPage):
set validation msg to
unknown error
"""
- self.validationMsg.setText("Error during signup")
+ self.validationMsg.setText("Error during sign up")
+
+
+class LogInPage(QtGui.QWizardPage, UserFormMixIn):
+ def __init__(self, parent=None):
+ super(LogInPage, self).__init__(parent)
+
+ self.setTitle("Log In")
+ self.setSubTitle("Log in with your credentials.")
+
+ self.setPixmap(
+ QtGui.QWizard.LogoPixmap,
+ QtGui.QPixmap(APP_LOGO))
+
+ userNameLabel = QtGui.QLabel("User &name:")
+ userNameLineEdit = QtGui.QLineEdit()
+ userNameLineEdit.cursorPositionChanged.connect(
+ self.reset_validation_status)
+ userNameLabel.setBuddy(userNameLineEdit)
+
+ # add regex validator
+ usernameRe = QtCore.QRegExp(r"^[A-Za-z\d_]+$")
+ userNameLineEdit.setValidator(
+ QtGui.QRegExpValidator(usernameRe, self))
+ self.userNameLineEdit = userNameLineEdit
+
+ userPasswordLabel = QtGui.QLabel("&Password:")
+ self.userPasswordLineEdit = QtGui.QLineEdit()
+ self.userPasswordLineEdit.setEchoMode(
+ QtGui.QLineEdit.Password)
+ userPasswordLabel.setBuddy(self.userPasswordLineEdit)
+
+ self.registerField('log_in_userName*', self.userNameLineEdit)
+ self.registerField('log_in_userPassword*', self.userPasswordLineEdit)
+
+ layout = QtGui.QGridLayout()
+ layout.setColumnMinimumWidth(0, 20)
+
+ validationMsg = QtGui.QLabel("")
+ validationMsg.setStyleSheet(ErrorLabelStyleSheet)
+
+ self.validationMsg = validationMsg
+
+ layout.addWidget(validationMsg, 0, 3)
+
+ layout.addWidget(userNameLabel, 1, 0)
+ layout.addWidget(self.userNameLineEdit, 1, 3)
+
+ layout.addWidget(userPasswordLabel, 2, 0)
+ layout.addWidget(self.userPasswordLineEdit, 2, 3)
+
+ self.setLayout(layout)
+
+ def nextId(self):
+ wizard = self.wizard()
+ if not wizard:
+ return
+ if wizard.is_provider_setup is True:
+ next_ = 'connecting'
+ if wizard.is_provider_setup is False:
+ next_ = 'providersetup'
+ return wizard.get_page_index(next_)
+
+
+class RegisterUserPage(QtGui.QWizardPage, UserFormMixIn):
+ setSigningUpStatus = QtCore.pyqtSignal([])
+
+ def __init__(self, parent=None):
+ super(RegisterUserPage, self).__init__(parent)
+
+ # bind wizard page signals
+ self.setSigningUpStatus.connect(
+ self.set_status_validating)
+
+ self.setTitle("Sign Up")
+
+ self.setPixmap(
+ QtGui.QWizard.LogoPixmap,
+ QtGui.QPixmap(APP_LOGO))
+
+ userNameLabel = QtGui.QLabel("User &name:")
+ userNameLineEdit = QtGui.QLineEdit()
+ userNameLineEdit.cursorPositionChanged.connect(
+ self.reset_validation_status)
+ userNameLabel.setBuddy(userNameLineEdit)
+
+ # add regex validator
+ usernameRe = QtCore.QRegExp(r"^[A-Za-z\d_]+$")
+ userNameLineEdit.setValidator(
+ QtGui.QRegExpValidator(usernameRe, self))
+ self.userNameLineEdit = userNameLineEdit
+
+ userPasswordLabel = QtGui.QLabel("&Password:")
+ self.userPasswordLineEdit = QtGui.QLineEdit()
+ self.userPasswordLineEdit.setEchoMode(
+ QtGui.QLineEdit.Password)
+ userPasswordLabel.setBuddy(self.userPasswordLineEdit)
+
+ rememberPasswordCheckBox = QtGui.QCheckBox(
+ "&Remember username and password.")
+ rememberPasswordCheckBox.setChecked(True)
+
+ self.registerField('userName*', self.userNameLineEdit)
+ self.registerField('userPassword*', self.userPasswordLineEdit)
+ self.registerField('rememberPassword', rememberPasswordCheckBox)
+
+ layout = QtGui.QGridLayout()
+ layout.setColumnMinimumWidth(0, 20)
+
+ validationMsg = QtGui.QLabel("")
+ validationMsg.setStyleSheet(ErrorLabelStyleSheet)
+
+ self.validationMsg = validationMsg
+
+ layout.addWidget(validationMsg, 0, 3)
+
+ layout.addWidget(userNameLabel, 1, 0)
+ layout.addWidget(self.userNameLineEdit, 1, 3)
+
+ layout.addWidget(userPasswordLabel, 2, 0)
+ layout.addWidget(self.userPasswordLineEdit, 2, 3)
+
+ layout.addWidget(rememberPasswordCheckBox, 3, 3, 3, 4)
+ self.setLayout(layout)
# overwritten methods
@@ -395,6 +525,10 @@ class RegisterUserPage(QtGui.QWizardPage):
"""
inits wizard page
"""
+ provider = self.field('provider_domain')
+ self.setSubTitle(
+ "Register a new user with provider %s." %
+ provider)
self.validationMsg.setText('')
def validatePage(self):
@@ -456,23 +590,50 @@ class RegisterUserPage(QtGui.QWizardPage):
logger.debug('validation errors: %s' % validation_msgs)
errors = validation_msgs.get('errors', None)
if errors and errors.get('login', None):
+ # XXX this sometimes catch the blank username
+ # but we're not allowing that (soon)
self.set_status_invalid_username()
else:
self.set_status_unknown_error()
return False
+ def nextId(self):
+ wizard = self.wizard()
+ if not wizard:
+ return
+ return wizard.get_page_index('connecting')
+
class GlobalEIPSettings(QtGui.QWizardPage):
+ """
+ not in use right now
+ """
def __init__(self, parent=None):
super(GlobalEIPSettings, self).__init__(parent)
+class ConnectingPage(QtGui.QWizardPage):
+ def __init__(self, parent=None):
+ super(ConnectingPage, self).__init__(parent)
+
+ self.setTitle("Connecting")
+ self.setSubTitle('Connecting to provider.')
+
+ self.setPixmap(
+ QtGui.QWizard.LogoPixmap,
+ QtGui.QPixmap(APP_LOGO))
+
+
class LastPage(QtGui.QWizardPage):
def __init__(self, parent=None):
super(LastPage, self).__init__(parent)
self.setTitle("Ready to go!")
+ self.setPixmap(
+ QtGui.QWizard.LogoPixmap,
+ QtGui.QPixmap(APP_LOGO))
+
#self.setPixmap(
#QtGui.QWizard.WatermarkPixmap,
#QtGui.QPixmap(':/images/watermark2.png'))
@@ -502,6 +663,6 @@ if __name__ == '__main__':
logger.setLevel(logging.DEBUG)
app = QtGui.QApplication(sys.argv)
- wizard = FirstRunWizard()
+ wizard = FirstRunWizard(providers=('springbok',))
wizard.show()
sys.exit(app.exec_())
diff --git a/src/leap/util/dicts.py b/src/leap/util/dicts.py
new file mode 100644
index 00000000..d8177973
--- /dev/null
+++ b/src/leap/util/dicts.py
@@ -0,0 +1,258 @@
+# Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7 and pypy.
+# Passes Python2.7's test suite and incorporates all the latest updates.
+
+try:
+ from thread import get_ident as _get_ident
+except ImportError:
+ from dummy_thread import get_ident as _get_ident
+
+try:
+ from _abcoll import KeysView, ValuesView, ItemsView
+except ImportError:
+ pass
+
+
+class OrderedDict(dict):
+ 'Dictionary that remembers insertion order'
+ # An inherited dict maps keys to values.
+ # The inherited dict provides __getitem__, __len__, __contains__, and get.
+ # The remaining methods are order-aware.
+ # Big-O running times for all methods are the same as for regular dictionaries.
+
+ # The internal self.__map dictionary maps keys to links in a doubly linked list.
+ # The circular doubly linked list starts and ends with a sentinel element.
+ # The sentinel element never gets deleted (this simplifies the algorithm).
+ # Each link is stored as a list of length three: [PREV, NEXT, KEY].
+
+ def __init__(self, *args, **kwds):
+ '''Initialize an ordered dictionary. Signature is the same as for
+ regular dictionaries, but keyword arguments are not recommended
+ because their insertion order is arbitrary.
+
+ '''
+ if len(args) > 1:
+ raise TypeError('expected at most 1 arguments, got %d' % len(args))
+ try:
+ self.__root
+ except AttributeError:
+ self.__root = root = [] # sentinel node
+ root[:] = [root, root, None]
+ self.__map = {}
+ self.__update(*args, **kwds)
+
+ def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
+ 'od.__setitem__(i, y) <==> od[i]=y'
+ # Setting a new item creates a new link which goes at the end of the linked
+ # list, and the inherited dictionary is updated with the new key/value pair.
+ if key not in self:
+ root = self.__root
+ last = root[0]
+ last[1] = root[0] = self.__map[key] = [last, root, key]
+ dict_setitem(self, key, value)
+
+ def __delitem__(self, key, dict_delitem=dict.__delitem__):
+ 'od.__delitem__(y) <==> del od[y]'
+ # Deleting an existing item uses self.__map to find the link which is
+ # then removed by updating the links in the predecessor and successor nodes.
+ dict_delitem(self, key)
+ link_prev, link_next, key = self.__map.pop(key)
+ link_prev[1] = link_next
+ link_next[0] = link_prev
+
+ def __iter__(self):
+ 'od.__iter__() <==> iter(od)'
+ root = self.__root
+ curr = root[1]
+ while curr is not root:
+ yield curr[2]
+ curr = curr[1]
+
+ def __reversed__(self):
+ 'od.__reversed__() <==> reversed(od)'
+ root = self.__root
+ curr = root[0]
+ while curr is not root:
+ yield curr[2]
+ curr = curr[0]
+
+ def clear(self):
+ 'od.clear() -> None. Remove all items from od.'
+ try:
+ for node in self.__map.itervalues():
+ del node[:]
+ root = self.__root
+ root[:] = [root, root, None]
+ self.__map.clear()
+ except AttributeError:
+ pass
+ dict.clear(self)
+
+ def popitem(self, last=True):
+ '''od.popitem() -> (k, v), return and remove a (key, value) pair.
+ Pairs are returned in LIFO order if last is true or FIFO order if false.
+
+ '''
+ if not self:
+ raise KeyError('dictionary is empty')
+ root = self.__root
+ if last:
+ link = root[0]
+ link_prev = link[0]
+ link_prev[1] = root
+ root[0] = link_prev
+ else:
+ link = root[1]
+ link_next = link[1]
+ root[1] = link_next
+ link_next[0] = root
+ key = link[2]
+ del self.__map[key]
+ value = dict.pop(self, key)
+ return key, value
+
+ # -- the following methods do not depend on the internal structure --
+
+ def keys(self):
+ 'od.keys() -> list of keys in od'
+ return list(self)
+
+ def values(self):
+ 'od.values() -> list of values in od'
+ return [self[key] for key in self]
+
+ def items(self):
+ 'od.items() -> list of (key, value) pairs in od'
+ return [(key, self[key]) for key in self]
+
+ def iterkeys(self):
+ 'od.iterkeys() -> an iterator over the keys in od'
+ return iter(self)
+
+ def itervalues(self):
+ 'od.itervalues -> an iterator over the values in od'
+ for k in self:
+ yield self[k]
+
+ def iteritems(self):
+ 'od.iteritems -> an iterator over the (key, value) items in od'
+ for k in self:
+ yield (k, self[k])
+
+ def update(*args, **kwds):
+ '''od.update(E, **F) -> None. Update od from dict/iterable E and F.
+
+ If E is a dict instance, does: for k in E: od[k] = E[k]
+ If E has a .keys() method, does: for k in E.keys(): od[k] = E[k]
+ Or if E is an iterable of items, does: for k, v in E: od[k] = v
+ In either case, this is followed by: for k, v in F.items(): od[k] = v
+
+ '''
+ if len(args) > 2:
+ raise TypeError('update() takes at most 2 positional '
+ 'arguments (%d given)' % (len(args),))
+ elif not args:
+ raise TypeError('update() takes at least 1 argument (0 given)')
+ self = args[0]
+ # Make progressively weaker assumptions about "other"
+ other = ()
+ if len(args) == 2:
+ other = args[1]
+ if isinstance(other, dict):
+ for key in other:
+ self[key] = other[key]
+ elif hasattr(other, 'keys'):
+ for key in other.keys():
+ self[key] = other[key]
+ else:
+ for key, value in other:
+ self[key] = value
+ for key, value in kwds.items():
+ self[key] = value
+
+ __update = update # let subclasses override update without breaking __init__
+
+ __marker = object()
+
+ def pop(self, key, default=__marker):
+ '''od.pop(k[,d]) -> v, remove specified key and return the corresponding value.
+ If key is not found, d is returned if given, otherwise KeyError is raised.
+
+ '''
+ if key in self:
+ result = self[key]
+ del self[key]
+ return result
+ if default is self.__marker:
+ raise KeyError(key)
+ return default
+
+ def setdefault(self, key, default=None):
+ 'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
+ if key in self:
+ return self[key]
+ self[key] = default
+ return default
+
+ def __repr__(self, _repr_running={}):
+ 'od.__repr__() <==> repr(od)'
+ call_key = id(self), _get_ident()
+ if call_key in _repr_running:
+ return '...'
+ _repr_running[call_key] = 1
+ try:
+ if not self:
+ return '%s()' % (self.__class__.__name__,)
+ return '%s(%r)' % (self.__class__.__name__, self.items())
+ finally:
+ del _repr_running[call_key]
+
+ def __reduce__(self):
+ 'Return state information for pickling'
+ items = [[k, self[k]] for k in self]
+ inst_dict = vars(self).copy()
+ for k in vars(OrderedDict()):
+ inst_dict.pop(k, None)
+ if inst_dict:
+ return (self.__class__, (items,), inst_dict)
+ return self.__class__, (items,)
+
+ def copy(self):
+ 'od.copy() -> a shallow copy of od'
+ return self.__class__(self)
+
+ @classmethod
+ def fromkeys(cls, iterable, value=None):
+ '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S
+ and values equal to v (which defaults to None).
+
+ '''
+ d = cls()
+ for key in iterable:
+ d[key] = value
+ return d
+
+ def __eq__(self, other):
+ '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive
+ while comparison to a regular mapping is order-insensitive.
+
+ '''
+ if isinstance(other, OrderedDict):
+ return len(self)==len(other) and self.items() == other.items()
+ return dict.__eq__(self, other)
+
+ def __ne__(self, other):
+ return not self == other
+
+ # -- the following methods are only used in Python 2.7 --
+
+ def viewkeys(self):
+ "od.viewkeys() -> a set-like object providing a view on od's keys"
+ return KeysView(self)
+
+ def viewvalues(self):
+ "od.viewvalues() -> an object providing a view on od's values"
+ return ValuesView(self)
+
+ def viewitems(self):
+ "od.viewitems() -> a set-like object providing a view on od's items"
+ return ItemsView(self)