diff options
Diffstat (limited to 'src/leap')
| -rw-r--r-- | src/leap/base/auth.py | 87 | ||||
| -rwxr-xr-x | src/leap/gui/firstrunwizard.py | 489 | ||||
| -rw-r--r-- | src/leap/util/dicts.py | 258 |
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) |