def lbTreeWalk(lbType, parentElt, lbStruct, roleRefs, dimDef=False, locs=None, arcsFromTo=None, fromPrefix=None, fromName=None):
    order = 1.0
    for lbEntry in lbStruct:
        if lbEntry.isELR:
            if (not lbEntry.childStruct):
                continue
            role = 'unspecified'
            if (lbEntry.role and lbEntry.role.startswith('http://')):
                role = lbEntry.role
            elif lbEntry.name:
                for (linkroleUri, modelRoleTypes) in modelXbrl.roleTypes.items():
                    definition = modelRoleTypes[0].definition
                    if ((lbEntry.name == definition) and (linkroleUri in thisDoc.extensionRoles)):
                        role = linkroleUri
                        break
            if (role == 'unspecified'):
                continue
            if (role not in thisDoc.extensionRoles):
                continue
            if (role == XbrlConst.defaultLinkRole):
                pass
            elif (role in thisDoc.extensionRoles):
                roleRefs.add(('roleRef', role, ((doc.uri + '#roleType_') + role.rpartition('/')[2])))
            elif (role in modelXbrl.roleTypes):
                roleType = modelRoleTypes[0]
                roleRefs.add(('roleRef', role, ((roleType.modelDocument.uri + '#') + roleType.id)))
            else:
                extUnrecognizedRoles.add(role)
            linkElt = XmlUtil.addChild(parentElt, (XbrlConst.gen if (lbType == 'generic') else XbrlConst.link), ('link' if (lbType == 'generic') else (lbType + 'Link')), attributes=(('{http://www.w3.org/1999/xlink}type', 'extended'), ('{http://www.w3.org/1999/xlink}role', role)))
            locs = set()
            arcsFromTo = set()
            lbTreeWalk(lbType, linkElt, lbEntry.childStruct, roleRefs, dimDef, locs, arcsFromTo)
        else:
            toPrefix = lbEntry.prefix
            toName = lbEntry.name
            toHref = LBHref(thisDoc, toPrefix, toName)
            if (toHref is None):
                modelXbrl.error('loadFromExcel:invalidQName', "%(linkbase)s relationship element with prefix '%(prefix)s' localName '%(localName)s' not found", modelXbrl=modelXbrl, linkbase=lbType, prefix=lbEntry.prefix, localName=lbEntry.name)
                continue
            if ((not toPrefix) and (toName in modelXbrl.nameConcepts)):
                toPrefix = modelXbrl.nameConcepts[toName][0].qname.prefix
            toLabel = '{}_{}'.format(toPrefix, toName)
            toLabelAlt = None
            if (not lbEntry.isRoot):
                if ((not fromPrefix) and (fromName in modelXbrl.nameConcepts)):
                    fromPrefix = modelXbrl.nameConcepts[fromName][0].qname.prefix
                fromLabel = '{}_{}'.format(fromPrefix, fromName)
                if ((fromLabel, toLabel) in arcsFromTo):
                    for i in range(1, 1000):
                        toLabelAlt = '{}_{}'.format(toLabel, i)
                        if ((fromLabel, toLabelAlt) not in arcsFromTo):
                            toLabel = toLabelAlt
                            break
            if (((toHref not in locs) or toLabelAlt) and (not dimDef)):
                XmlUtil.addChild(parentElt, XbrlConst.link, 'loc', attributes=(('{http://www.w3.org/1999/xlink}type', 'locator'), ('{http://www.w3.org/1999/xlink}href', toHref), ('{http://www.w3.org/1999/xlink}label', toLabel)))
                locs.add(toHref)
            if (not lbEntry.isRoot):
                arcsFromTo.add((fromLabel, toLabel))
                if ((lbType == 'calculation') and (lbEntry.weight is not None)):
                    otherAttrs = (('weight', lbEntry.weight),)
                elif ((lbType == 'presentation') and lbEntry.role):
                    if (not lbEntry.role.startswith('http://')):
                        _labelRoleMatchPart = ('/' + lbEntry.role)
                        for _roleURI in modelXbrl.roleTypes:
                            if _roleURI.endswith(_labelRoleMatchPart):
                                for _roleType in modelXbrl.roleTypes[_roleURI]:
                                    if (XbrlConst.qnLinkLabel in _roleType.usedOns):
                                        lbEntry.role = _roleURI
                                        break
                    if (not lbEntry.role.startswith('http://')):
                        lbEntry.role = ('http://www.xbrl.org/2003/role/' + lbEntry.role)
                    otherAttrs = (('preferredLabel', lbEntry.role),)
                    if (lbEntry.role and (lbEntry.role not in XbrlConst.standardLabelRoles)):
                        if (lbEntry.role in modelXbrl.roleTypes):
                            roleType = modelXbrl.roleTypes[lbEntry.role][0]
                            roleRefs.add(('roleRef', lbEntry.role, ((roleType.modelDocument.uri + '#') + roleType.id)))
                        else:
                            extUnrecognizedRoles.add(lbEntry.role)
                elif ((lbType == 'generic') and lbEntry.arcrole):
                    if (not lbEntry.arcrole.startswith('http://')):
                        for _arcroleURI in modelXbrl.arcroleTypes:
                            if _arcroleURI.endswith(lbEntry.arcrole):
                                lbEntry.arcrole = _arcroleURI
                                break
                    otherAttrs = tuple(((prefixedNameQName(_key), _value) for (_key, _value) in (lbEntry.relAttrs.items() if (lbEntry.relAttrs is not None) else ())))
                else:
                    otherAttrs = ()
                if (lbEntry.arcrole == '_dimensions_'):
                    fromConcept = hrefConcept(fromPrefix, fromName)
                    toConcept = hrefConcept(toPrefix, toName)
                    if dimDef:
                        if ((lbEntry.role != '_dimensionDefault_') and (not lbTreeHasDimDefault(lbEntry.childStruct))):
                            continue
                        if ((toConcept is not None) and (toConcept.isDimensionItem or (lbEntry.role == '_dimensionDefault_'))):
                            if ((toHref not in locs) or toLabelAlt):
                                XmlUtil.addChild(parentElt, XbrlConst.link, 'loc', attributes=(('{http://www.w3.org/1999/xlink}type', 'locator'), ('{http://www.w3.org/1999/xlink}href', toHref), ('{http://www.w3.org/1999/xlink}label', toLabel)))
                                locs.add(toHref)
                            if (lbEntry.role != '_dimensionDefault_'):
                                lbTreeWalk(lbType, parentElt, lbEntry.childStruct, roleRefs, dimDef, locs, arcsFromTo, toPrefix, toName)
                            else:
                                XmlUtil.addChild(parentElt, XbrlConst.link, 'definitionArc', attributes=((('{http://www.w3.org/1999/xlink}type', 'arc'), ('{http://www.w3.org/1999/xlink}arcrole', XbrlConst.dimensionDefault), ('{http://www.w3.org/1999/xlink}from', fromLabel), ('{http://www.w3.org/1999/xlink}to', toLabel), ('order', order)) + otherAttrs))
                                order += 1.0
                        else:
                            lbTreeWalk(lbType, parentElt, lbEntry.childStruct, roleRefs, dimDef, locs, arcsFromTo, fromPrefix, fromName)
                        continue
                    elif ((toConcept is not None) and toConcept.isHypercubeItem):
                        arcrole = XbrlConst.all
                        otherAttrs += ((XbrlConst.qnXbrldtContextElement, 'segment'), (qnXbrldtClosed, 'true'))
                    elif ((toConcept is not None) and toConcept.isDimensionItem):
                        arcrole = XbrlConst.hypercubeDimension
                    elif ((fromConcept is not None) and fromConcept.isDimensionItem):
                        arcrole = XbrlConst.dimensionDomain
                    else:
                        arcrole = XbrlConst.domainMember
                else:
                    arcrole = lbEntry.arcrole
                if (arcrole in relationshipArcqnames):
                    arcqname = relationshipArcqnames[arcrole]
                    arcNS = arcqname.namespaceURI
                    arcLocalname = arcqname.localName
                elif (lbType == 'generic'):
                    arcNS = XbrlConst.gen
                    arcLocalname = 'arc'
                else:
                    arcNS = XbrlConst.link
                    arcLocalname = (lbType + 'Arc')
                XmlUtil.addChild(parentElt, arcNS, arcLocalname, attributes=((('{http://www.w3.org/1999/xlink}type', 'arc'), ('{http://www.w3.org/1999/xlink}arcrole', arcrole), ('{http://www.w3.org/1999/xlink}from', fromLabel), ('{http://www.w3.org/1999/xlink}to', toLabel), ('order', order)) + otherAttrs))
                order += 1.0
            if ((lbType != 'calculation') or lbEntry.isRoot):
                lbTreeWalk(lbType, parentElt, lbEntry.childStruct, roleRefs, dimDef, locs, arcsFromTo, toPrefix, toName)
def lbTreeWalk(lbType, parentElt, lbStruct, roleRefs, dimDef=False, locs=None, arcsFromTo=None, fromPrefix=None, fromName=None):
    order = 1.0
    for lbEntry in lbStruct:
        if lbEntry.isELR:
            if (not lbEntry.childStruct):
                continue
            role = 'unspecified'
            if (lbEntry.role and lbEntry.role.startswith('http://')):
                role = lbEntry.role
            elif lbEntry.name:
                for (linkroleUri, modelRoleTypes) in modelXbrl.roleTypes.items():
                    definition = modelRoleTypes[0].definition
                    if ((lbEntry.name == definition) and (linkroleUri in thisDoc.extensionRoles)):
                        role = linkroleUri
                        break
            if (role == 'unspecified'):
                continue
            if (role not in thisDoc.extensionRoles):
                continue
            if (role == XbrlConst.defaultLinkRole):
                pass
            elif (role in thisDoc.extensionRoles):
                roleRefs.add(('roleRef', role, ((doc.uri + '#roleType_') + role.rpartition('/')[2])))
            elif (role in modelXbrl.roleTypes):
                roleType = modelRoleTypes[0]
                roleRefs.add(('roleRef', role, ((roleType.modelDocument.uri + '#') + roleType.id)))
            else:
                extUnrecognizedRoles.add(role)
            linkElt = XmlUtil.addChild(parentElt, (XbrlConst.gen if (lbType == 'generic') else XbrlConst.link), ('link' if (lbType == 'generic') else (lbType + 'Link')), attributes=(('{http://www.w3.org/1999/xlink}type', 'extended'), ('{http://www.w3.org/1999/xlink}role', role)))
            locs = set()
            arcsFromTo = set()
            lbTreeWalk(lbType, linkElt, lbEntry.childStruct, roleRefs, dimDef, locs, arcsFromTo)
        else:
            toPrefix = lbEntry.prefix
            toName = lbEntry.name
            toHref = LBHref(thisDoc, toPrefix, toName)
            if (toHref is None):
                modelXbrl.error('loadFromExcel:invalidQName', "%(linkbase)s relationship element with prefix '%(prefix)s' localName '%(localName)s' not found", modelXbrl=modelXbrl, linkbase=lbType, prefix=lbEntry.prefix, localName=lbEntry.name)
                continue
            if ((not toPrefix) and (toName in modelXbrl.nameConcepts)):
                toPrefix = modelXbrl.nameConcepts[toName][0].qname.prefix
            toLabel = '{}_{}'.format(toPrefix, toName)
            toLabelAlt = None
            if (not lbEntry.isRoot):
                if ((not fromPrefix) and (fromName in modelXbrl.nameConcepts)):
                    fromPrefix = modelXbrl.nameConcepts[fromName][0].qname.prefix
                fromLabel = '{}_{}'.format(fromPrefix, fromName)
                if ((fromLabel, toLabel) in arcsFromTo):
                    for i in range(1, 1000):
                        toLabelAlt = '{}_{}'.format(toLabel, i)
                        if ((fromLabel, toLabelAlt) not in arcsFromTo):
                            toLabel = toLabelAlt
                            break
            if (((toHref not in locs) or toLabelAlt) and (not dimDef)):
                XmlUtil.addChild(parentElt, XbrlConst.link, 'loc', attributes=(('{http://www.w3.org/1999/xlink}type', 'locator'), ('{http://www.w3.org/1999/xlink}href', toHref), ('{http://www.w3.org/1999/xlink}label', toLabel)))
                locs.add(toHref)
            if (not lbEntry.isRoot):
                arcsFromTo.add((fromLabel, toLabel))
                if ((lbType == 'calculation') and (lbEntry.weight is not None)):
                    otherAttrs = (('weight', lbEntry.weight),)
                elif ((lbType == 'presentation') and lbEntry.role):
                    if (not lbEntry.role.startswith('http://')):
                        _labelRoleMatchPart = ('/' + lbEntry.role)
                        for _roleURI in modelXbrl.roleTypes:
                            if _roleURI.endswith(_labelRoleMatchPart):
                                for _roleType in modelXbrl.roleTypes[_roleURI]:
                                    if (XbrlConst.qnLinkLabel in _roleType.usedOns):
                                        lbEntry.role = _roleURI
                                        break
                    if (not lbEntry.role.startswith('http://')):
                        lbEntry.role = ('http://www.xbrl.org/2003/role/' + lbEntry.role)
                    otherAttrs = (('preferredLabel', lbEntry.role),)
                    if (lbEntry.role and (lbEntry.role not in XbrlConst.standardLabelRoles)):
                        if (lbEntry.role in modelXbrl.roleTypes):
                            roleType = modelXbrl.roleTypes[lbEntry.role][0]
                            roleRefs.add(('roleRef', lbEntry.role, ((roleType.modelDocument.uri + '#') + roleType.id)))
                        else:
                            extUnrecognizedRoles.add(lbEntry.role)
                elif ((lbType == 'generic') and lbEntry.arcrole):
                    if (not lbEntry.arcrole.startswith('http://')):
                        for _arcroleURI in modelXbrl.arcroleTypes:
                            if _arcroleURI.endswith(lbEntry.arcrole):
                                lbEntry.arcrole = _arcroleURI
                                break
                    otherAttrs = tuple(((prefixedNameQName(_key), _value) for (_key, _value) in (lbEntry.relAttrs.items() if (lbEntry.relAttrs is not None) else ())))
                else:
                    otherAttrs = ()
                if (lbEntry.arcrole == '_dimensions_'):
                    fromConcept = hrefConcept(fromPrefix, fromName)
                    toConcept = hrefConcept(toPrefix, toName)
                    if dimDef:
                        if ((lbEntry.role != '_dimensionDefault_') and (not lbTreeHasDimDefault(lbEntry.childStruct))):
                            continue
                        if ((toConcept is not None) and (toConcept.isDimensionItem or (lbEntry.role == '_dimensionDefault_'))):
                            if ((toHref not in locs) or toLabelAlt):
                                XmlUtil.addChild(parentElt, XbrlConst.link, 'loc', attributes=(('{http://www.w3.org/1999/xlink}type', 'locator'), ('{http://www.w3.org/1999/xlink}href', toHref), ('{http://www.w3.org/1999/xlink}label', toLabel)))
                                locs.add(toHref)
                            if (lbEntry.role != '_dimensionDefault_'):
                                lbTreeWalk(lbType, parentElt, lbEntry.childStruct, roleRefs, dimDef, locs, arcsFromTo, toPrefix, toName)
                            else:
                                XmlUtil.addChild(parentElt, XbrlConst.link, 'definitionArc', attributes=((('{http://www.w3.org/1999/xlink}type', 'arc'), ('{http://www.w3.org/1999/xlink}arcrole', XbrlConst.dimensionDefault), ('{http://www.w3.org/1999/xlink}from', fromLabel), ('{http://www.w3.org/1999/xlink}to', toLabel), ('order', order)) + otherAttrs))
                                order += 1.0
                        else:
                            lbTreeWalk(lbType, parentElt, lbEntry.childStruct, roleRefs, dimDef, locs, arcsFromTo, fromPrefix, fromName)
                        continue
                    elif ((toConcept is not None) and toConcept.isHypercubeItem):
                        arcrole = XbrlConst.all
                        otherAttrs += ((XbrlConst.qnXbrldtContextElement, 'segment'), (qnXbrldtClosed, 'true'))
                    elif ((toConcept is not None) and toConcept.isDimensionItem):
                        arcrole = XbrlConst.hypercubeDimension
                    elif ((fromConcept is not None) and fromConcept.isDimensionItem):
                        arcrole = XbrlConst.dimensionDomain
                    else:
                        arcrole = XbrlConst.domainMember
                else:
                    arcrole = lbEntry.arcrole
                if (arcrole in relationshipArcqnames):
                    arcqname = relationshipArcqnames[arcrole]
                    arcNS = arcqname.namespaceURI
                    arcLocalname = arcqname.localName
                elif (lbType == 'generic'):
                    arcNS = XbrlConst.gen
                    arcLocalname = 'arc'
                else:
                    arcNS = XbrlConst.link
                    arcLocalname = (lbType + 'Arc')
                XmlUtil.addChild(parentElt, arcNS, arcLocalname, attributes=((('{http://www.w3.org/1999/xlink}type', 'arc'), ('{http://www.w3.org/1999/xlink}arcrole', arcrole), ('{http://www.w3.org/1999/xlink}from', fromLabel), ('{http://www.w3.org/1999/xlink}to', toLabel), ('order', order)) + otherAttrs))
                order += 1.0
            if ((lbType != 'calculation') or lbEntry.isRoot):
                lbTreeWalk(lbType, parentElt, lbEntry.childStruct, roleRefs, dimDef, locs, arcsFromTo, toPrefix, toName)