Branch instructions on most architectures use PC-relative addressingwith a limited range. When the target is too far away, the branchbecomes "out of range" and requires special handling.

Consider a large binary where main() at address 0x10000calls foo() at address 0x8010000-over 128MiB away. OnAArch64, the bl instruction can only reach ±128MiB, so thiscall cannot be encoded directly. Without proper handling, the linkerwould fail with an error like "relocation out of range." The toolchainmust handle this transparently to produce correct executables.

This article explores how compilers, assemblers, and linkers worktogether to solve the long branch problem.

• Compiler (IR to assembly): Handles branches within a function thatexceed the range of conditional branch instructions
• Assembler (assembly to relocatable file): Handles branches within asection where the distance is known at assembly time
• Linker: Handles cross-section and cross-object branches discoveredduring final layout

Branch range limitations

Different architectures have different branch range limitations.Here's a quick comparison of unconditional branch/call ranges:

The following subsections provide detailed per-architectureinformation, including relocation types relevant for linkerimplementation.

AArch32

In A32 state:

• Branch (b/b<cond>), conditionalbranch and link (bl<cond>)(R_ARM_JUMP24): ±32MiB
• Unconditional branch and link (bl/blx,R_ARM_CALL): ±32MiB

Note: R_ARM_CALL is for unconditionalbl/blx which can be relaxed to BLX inline;R_ARM_JUMP24 is for branches which require a veneer forinterworking.

In T32 state (Thumb state pre-ARMv8):

• Conditional branch (b<cond>,R_ARM_THM_JUMP8): ±256 bytes
• Short unconditional branch (b,R_ARM_THM_JUMP11): ±2KiB
• ARMv5T branch and link (bl/blx,R_ARM_THM_CALL): ±4MiB
• ARMv6T2 wide conditional branch (b<cond>.w,R_ARM_THM_JUMP19): ±1MiB
• ARMv6T2 wide branch (b.w,R_ARM_THM_JUMP24): ±16MiB
• ARMv6T2 wide branch and link (bl/blx,R_ARM_THM_CALL): ±16MiB. R_ARM_THM_CALL can berelaxed to BLX.

AArch64

• Test and compare branches(tbnz/tbz/cbnz/cbz):±32KiB
• Conditional branches (b.<cond>): ±1MiB
• Unconditional branches (b/bl):±128MiB

The compiler's BranchRelaxation pass handlesout-of-rangetbz/tbnz/cbz/cbnz byinverting the condition and inserting an unconditional branch. TheAArch64 assembler does not perform branch relaxation; out-of-rangebranches produce linker errors if not handled by the compiler.

PowerPC

• Conditional branch (bc/bcl,R_PPC64_REL14): ±32KiB
• Unconditional branch (b/bl,R_PPC64_REL24/R_PPC64_REL24_NOTOC):±32MiB

RISC-V

• Compressed c.beqz: ±256 bytes
• Compressed c.jal: ±2KiB
• jalr (I-type immediate): ±2KiB
• Conditional branches(beq/bne/blt/bge/bltu/bgeu,B-type immediate): ±4KiB
• jal (J-type immediate, PseudoBR):±1MiB
• PseudoJump (using auipc +jalr): ±2GiB
• beqi/bnei (Zibi extension, 5-bit compareimmediate (1 to 31 and -1)): ±4KiB

Qualcomm uC Branch Immediate extension (Xqcibi):

• qc.beqi/qc.bnei/qc.blti/qc.bgei/qc.bltui/qc.bgeui(32-bit, 5-bit compare immediate): ±4KiB
• qc.e.beqi/qc.e.bnei/qc.e.blti/qc.e.bgei/qc.e.bltui/qc.e.bgeui(48-bit, 16-bit compare immediate): ±4KiB

Qualcomm uC Long Branch extension (Xqcilb):

• qc.e.j/qc.e.jal (48-bit,R_RISCV_VENDOR(QUALCOMM)+R_RISCV_QC_E_CALL_PLT): ±2GiB

SPARC

• Compare and branch (cxbe, R_SPARC_5): ±64bytes
• Conditional branches (bcc,R_SPARC_WDISP19): ±1MiB
• call (R_SPARC_WDISP30): ±2GiB

Note: lld does not implement range extension thunks for SPARC.

x86-64

• Short conditional jump (Jcc rel8): -128 to +127bytes
• Short unconditional jump (JMP rel8): -128 to +127bytes
• Near conditional jump (Jcc rel32): ±2GiB
• Near unconditional jump (JMP rel32): ±2GiB

With a ±2GiB range for near jumps, x86-64 rarely encountersout-of-range branches in practice. A single text section would need toexceed 2GiB before thunks become necessary. For this reason, mostlinkers (including lld) do not implement range extension thunks forx86-64.

Compiler: branch rangehandling

Conditional branch instructions usually have shorter ranges thanunconditional ones, making them less suitable for linker thunks (as wewill explore later). Compilers typically keep conditional branch targetswithin the same section, allowing the compiler to handle out-of-rangecases via branch relaxation.

Within a function, conditional branches may still go out of range.The compiler measures branch distances and relaxes out-of-range branchesby inverting the condition and inserting an unconditional branch:

1
2
3
4
5
6
7

# Before relaxation (out of range)
beq .Lfar_target       # ±4KiB range on RISC-V

# After relaxation
bne .Lskip             # Inverted condition, short range
j .Lfar_target         # Unconditional jump, ±1MiB range
.Lskip:

Some architectures have test and compare branch instructions witheven shorter ranges due to encoding additional immediates. For example,AArch64's cbz/cbnz (compare and branch ifzero/non-zero) and tbz/tbnz (test bit andbranch) have only ±32KiB range. The compiler handles these the sameway:

1
2
3
4
5
6
7

// Before relaxation (cbz has ±32KiB range)
  cbz w0, far

// After relaxation
  cbnz w0, .Lskip       // Inverted condition
  b far                 // Unconditional branch, ±128MiB range
.Lskip:

In LLVM, this is handled by the BranchRelaxation pass,which runs just before AsmPrinter. Different backends havetheir own implementations:

• BranchRelaxation: AArch64, AMDGPU, AVR, RISC-V
• HexagonBranchRelaxation: Hexagon
• PPCBranchSelector: PowerPC
• SystemZLongBranch: SystemZ
• MipsBranchExpansion: MIPS
• MSP430BSel: MSP430

The generic BranchRelaxation pass computes block sizesand offsets, then iterates until all branches are in range. Forconditional branches, it tries to invert the condition and insert anunconditional branch. For unconditional branches that are still out ofrange, it calls TargetInstrInfo::insertIndirectBranch toemit an indirect jump sequence (e.g.,adrp+add+br on AArch64) or a longjump sequence (e.g., pseudo jump on RISC-V).

Unconditional branches and calls can target different sections sincethey have larger ranges. If the target is out of reach, the linker caninsert thunks to extend the range.

For x86-64, the large code model uses multiple instructions for callsand jumps to support text sections larger than 2GiB (see Relocationoverflow and code models: x86-64 large code model). This is apessimization if the callee ends up being within reach.

Assembler: instructionrelaxation

The assembler converts assembly to machine code. When the target of abranch is within the same section and the distance is known at assemblytime, the assembler can select the appropriate encoding. This isdistinct from linker thunks, which handle cross-section or cross-objectreferences where distances aren't known until link time.

Assembler instruction relaxation handles two cases (see Clang-O0 output: branch displacement and size increase for examples):

• Span-dependent instructions: Select a largerencoding when the displacement exceeds the range of the smallerencoding. For x86, a short jump (jmp rel8) can be relaxedto a near jump (jmp rel32).
• Conditional branch transform: Invert the conditionand insert an unconditional branch. On RISC-V, a blt mightbe relaxed to bge plus an unconditional branch.

The assembler uses an iterative layout algorithm that alternatesbetween fragment offset assignment and relaxation until all fragmentsbecome legalized. See Integratedassembler improvements in LLVM 19 for implementation details.

Linker: range extensionthunks

When the linker resolves relocations, it may discover that a branchtarget is out of range. At this point, the instruction encoding isfixed, so the linker cannot simply change the instruction. Instead, itgenerates range extension thunks (also called veneers,branch stubs, or trampolines).

A thunk is a small piece of linker-generated code that can reach theactual target using a longer sequence of instructions. The originalbranch is redirected to the thunk, which then jumps to the realdestination.

Range extension thunks are one type of linker-generated thunk. Othertypes include:

• ARM interworking veneers: Switch between ARM andThumb instruction sets (see Linker notes onAArch32)
• MIPS LA25 thunks: Enable PIC and non-PIC codeinteroperability (see Toolchain notes onMIPS)
• PowerPC64 TOC/NOTOC thunks: Handle calls betweenfunctions using different TOC pointer conventions (see Linker notes on PowerISA)

Short range vs long rangethunks

A short range thunk (see lld/ELF's AArch64implementation) contains just a single branch instruction. Since ituses a branch, its reach is also limited by the branch range—it can onlyextend coverage by one branch distance. For targets further away,multiple short range thunks can be chained, or a long range thunk withaddress computation must be used.

Long range thunks use indirection and can jump to (practically)arbitrary locations.

1
2
3
4
5
6
7
8
9

// Short range thunk: single branch, 4 bytes
__AArch64AbsLongThunk_dst:
  b dst                         // ±128MiB range

// Long range thunk: address computation, 12 bytes
__AArch64ADRPThunk_dst:
  adrp x16, dst                 // Load page address (±4GiB range)
  add x16, x16, :lo12:dst       // Add page offset
  br x16                        // Indirect branch

Thunk examples

AArch32 (PIC) (see Linker notes onAArch32):

1
2
3
4
5

__ARMV7PILongThunk_dst:
  movw ip, :lower16:(dst - .)   ; ip = intra-procedure-call scratch register
  movt ip, :upper16:(dst - .)
  add ip, ip, pc
  bx ip

PowerPC64 ELFv2 (see Linker notes on PowerISA):

1
2
3
4
5

__long_branch_dst:
  addis 12, 2, .branch_lt@ha    # Load high bits from branch lookup table
  ld 12, .branch_lt@l(12)       # Load target address
  mtctr 12                      # Move to count register
  bctr                          # Branch to count register

Thunk impact ondebugging and profiling

Thunks are transparent at the source level but visible in low-leveltools:

• Stack traces: May show thunk symbols (e.g.,__AArch64ADRPThunk_foo) between caller and callee
• Profilers: Samples may attribute time to thunkcode; some profilers aggregate thunk time with the target function
• Disassembly: objdump orllvm-objdump will show thunk sections interspersed withregular code
• Code size: Each thunk adds bytes; large binariesmay have thousands of thunks

lld/ELF's thunk creationalgorithm

lld/ELF uses a multi-pass algorithm infinalizeAddressDependentContent:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

assignAddresses();
for (pass = 0; pass < 30; ++pass) {
  if (pass == 0)
    createInitialThunkSections();  // pre-create empty ThunkSections
  bool changed = false;
  for (relocation : all_relocations) {
    if (pass > 0 && normalizeExistingThunk(rel))
      continue;  // existing thunk still in range
    if (!needsThunk(rel)) continue;
    Thunk *t = getOrCreateThunk(rel);
    ts = findOrCreateThunkSection(rel, src);
    ts->addThunk(t);
    rel.sym = t->getThunkTargetSym();  // redirect
    changed = true;
  }
  mergeThunks();  // insert ThunkSections into output
  if (!changed) break;
  assignAddresses();  // recalculate with new thunks
}

Key details:

• Multi-pass: Iterates until convergence (max 30passes). Adding thunks changes addresses, potentially puttingpreviously-in-range calls out of range.
• Pre-allocated ThunkSections: On pass 0,createInitialThunkSections places emptyThunkSections at regular intervals(thunkSectionSpacing). For AArch64: 128 MiB - 0x30000 ≈127.8 MiB.
• Thunk reuse: getThunk returns existingthunk if one exists for the same target;normalizeExistingThunk checks if a previously-created thunkis still in range.
• ThunkSection placement: getISDThunkSecfinds a ThunkSection within branch range of the call site, or createsone adjacent to the calling InputSection.

lld/MachO's thunk creationalgorithm

lld/MachO uses a single-pass algorithm inTextOutputSection::finalize:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

for (callIdx = 0; callIdx < inputs.size(); ++callIdx) {
  // Finalize sections within forward branch range (minus slop)
  while (finalIdx < endIdx && fits_in_range(inputs[finalIdx]))
    finalizeOne(inputs[finalIdx++]);

  // Process branch relocations in this section
  for (Relocation &r : reverse(isec->relocs)) {
    if (!isBranchReloc(r)) continue;
    if (targetInRange(r)) continue;
    if (existingThunkInRange(r)) { reuse it; continue; }
    // Create new thunk and finalize it
    createThunk(r);
  }
}

Key differences from lld/ELF:

• Single pass: Addresses are assigned monotonicallyand never revisited
• Slop reservation: ReservesslopScale * thunkSize bytes (default: 256 × 12 = 3072 byteson ARM64) to leave room for future thunks
• Thunk naming:<function>.thunk.<sequence> where sequenceincrements per target

Thunkstarvation problem: If many consecutive branches need thunks, eachthunk (12 bytes) consumes slop faster than call sites (4 bytes apart)advance. The test lld/test/MachO/arm64-thunk-starvation.sdemonstrates this edge case. Mitigation is increasing--slop-scale, but pathological cases with hundreds ofconsecutive out-of-range callees can still fail.

mold's thunk creationalgorithm

mold uses a two-pass approach:

• Pessimistically over-allocate thunks. Out-of-section relocations andrelocations referencing to a section not assigned address yetpessimistically need thunks.
• Then remove unnecessary ones.

Intuition: It's safe to allocate thunk space andlater shrink it, but unsafe to add thunks after addresses are assigned(would create gaps breaking existing references).

Linker pass ordering:

1. compute_section_sizes() callscreate_range_extension_thunks() — final section addressesare NOT yet known
2. set_osec_offsets() assigns final section addresses
3. remove_redundant_thunks() is called AFTER addresses areknown — can now check actual ranges

The pessimism in pass 1 is implemented inrequires_thunk(ctx, isec, rel, first_pass). Whenfirst_pass=true, it assumes all out-of-section referencesneed thunks. When first_pass=false (in pass 2), it performsactual range checking.

Pass 1 (create_range_extension_thunks):Process sections in batches using a sliding window. The window tracksfour positions:

1
2
3
4
5
6
7
8
9

Sections:   [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] ...
             ^       ^       ^           ^
             A       B       C           D
             |       |_______|           |
             |         batch             |
             |                           |
             earliest                    thunk
             reachable                   placement
             from C

• [B, C) = current batch of sections to process (size≤ branch_distance/5)
• A = earliest section still reachable from C (forthunk expiration)
• D = where to place the thunk (furthest pointreachable from B)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

// Simplified from OutputSection<E>::create_range_extension_thunks
while (b < sections.size()) {
  // Advance D: find furthest point where thunk is reachable from B
  while (d < size && thunk_at_d_reachable_from_b)
    assign_address(sections[d++]);

  // Compute batch [B, C)
  c = b + 1;
  while (c < d && sections[c] < sections[b] + batch_size) c++;

  // Advance A: expire thunks no longer reachable
  while (a < b && sections[a] + branch_distance < sections[c]) a++;
  // Expire thunk groups before A: clear symbol flags.
  for (; t < thunks.size() && thunks[t].offset < sections[a]; t++)
    for (sym in thunks[t].symbols) sym->flags = 0;

  // Scan [B,C) relocations. If a symbol is not assigned to a thunk group yet,
  // assign it to the new thunk group at D.
  auto &thunk = thunks.emplace_back(new Thunk(offset));
  parallel_for(b, c, [&](i64 i) {
    for (rel in sections[i].relocs) {
      if (requires_thunk(rel)) {
        Symbol &sym = rel.symbol;
        if (!sym.flags.test_and_set()) {  // atomic: skip if already set
          lock_guard lock(mu);
          thunk.symbols.push_back(&sym);
        }
      }
    }
  });
  offset += thunk.size();
  b = c;  // Move to next batch
}

Pass 2 (remove_redundant_thunks): Afterfinal addresses are known, remove thunk entries for symbols actually inrange.

Key characteristics:

• Pessimistic over-allocation: Assumes allout-of-section calls need thunks; safe to shrink later
• Batch size: branch_distance/5 (25.6 MiB forAArch64, 3.2 MiB for AArch32)
• Parallelism: Uses TBB for parallel relocationscanning within each batch
• Single branch range: Uses one conservativebranch_distance per architecture. For AArch32, uses ±16 MiB(Thumb limit) for all branches, whereas lld/ELF uses ±32 MiB for A32branches.
• Thunk size not accounted in D-advancement: Theactual thunk group size is unknown when advancing D, so the end of alarge thunk group may be unreachable from the beginning of thebatch.
• No convergence loop: Single forward pass foraddress assignment, no risk of non-convergence

GNU ld's thunk creationalgorithm

Each port implements the algorithm on their own. There is no codesharing.

GNU ld's ppc64 port (bfd/elf64-ppc.c) uses an iterativemulti-pass algorithm with a branch lookup table(.branch_lt) for long-range stubs.

Main iteration loop(ppc64_elf_size_stubs()):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

while (1) {
  // Scan all relocations in all input sections
  for (input_bfd; section; irela) {
    // Only process branch relocations (R_PPC64_REL24, R_PPC64_REL14, etc.)
    stub_type = ppc_type_of_stub(section, irela, ...);
    if (stub_type == ppc_stub_none)
      continue;
    // Create or merge stub entry
    stub_entry = ppc_add_stub(...);
  }

  // Size all stubs, potentially upgrading long_branch to plt_branch
  bfd_hash_traverse(&stub_hash_table, ppc_size_one_stub, ...);

  // Check for convergence
  if (!stub_changed && all_sizes_stable)
    break;

  // Re-layout sections
  layout_sections_again();
}

Convergence control:

• STUB_SHRINK_ITER = 20 (PR28827): After 20 iterations,stub sections only grow (prevents oscillation)
• Convergence when:!stub_changed && all section sizes stable

Two-tier stub approach:

1. ppc_stub_long_branch: Simple 4-byte direct branch(b dest) when the stub section is within ±32MiB of thetarget
2. ppc_stub_plt_branch: When even the stub's branch can'treach, loads the destination address from .branch_lt tablevia TOC

Stub type upgrade: ppc_type_of_stub()initially returns ppc_stub_long_branch for out-of-rangebranches. Later, ppc_size_one_stub() checks if the stub'sbranch can reach; if not, it upgrades toppc_stub_plt_branch and allocates an 8-byte entry in.branch_lt.

Section grouping: Sections are grouped bystub_group_size (~28-30 MiB default); each group gets onestub section. For 14-bit conditional branches(R_PPC64_REL14, ±32KiB range), group size is reduced by1024x.

Comparing linker thunkalgorithms

Linker relaxation (RISC-V)

RISC-V takes a different approach: instead of only expandingbranches, it can also shrink instruction sequences whenthe target is close enough.

Consider a function call using the callpseudo-instruction, which expands to auipc +jalr:

1
2
3
4
5

# Before linking (8 bytes)
call ext
# Expands to:
#   auipc ra, %pcrel_hi(ext)
#   jalr ra, ra, %pcrel_lo(ext)

If ext is within ±1MiB, the linker can relax this to:

1
2

# After relaxation (4 bytes)
jal ext

This is enabled by R_RISCV_RELAX relocations thataccompany R_RISCV_CALL relocations. TheR_RISCV_RELAX relocation signals to the linker that thisinstruction sequence is a candidate for shrinking.

Example object code before linking:

1
2
3
4
5
6
7
8
9

0000000000000006 <foo>:
       6: 97 00 00 00   auipc   ra, 0
                R_RISCV_CALL ext
                R_RISCV_RELAX *ABS*
       a: e7 80 00 00   jalr    ra
       e: 97 00 00 00   auipc   ra, 0
                R_RISCV_CALL ext
                R_RISCV_RELAX *ABS*
      12: e7 80 00 00   jalr    ra

After linking with relaxation enabled, the 8-byteauipc+jalr pairs become 4-bytejal instructions:

1
2
3
4
5
6

0000000000000244 <foo>:
     244: 41 11         addi    sp, sp, -16
     246: 06 e4         sd      ra, 8(sp)
     248: ef 00 80 01   jal     ext
     24c: ef 00 40 01   jal     ext
     250: ef 00 00 01   jal     ext

When the linker deletes instructions, it must also adjust:

• Subsequent instruction offsets within the section
• Symbol addresses
• Other relocations that reference affected locations
• Alignment directives (R_RISCV_ALIGN)

This makes RISC-V linker relaxation more complex than thunkinsertion, but it provides code size benefits that other architecturescannot achieve at link time.

Diagnosing out-of-rangeerrors

When you encounter a "relocation out of range" error, here are somediagnostic steps:

1. Check the error message: lld reports the sourcelocation, relocation type, and the distance. For example:

   1	ld.lld: error: a.o:(.text+0x1000): relocation R_AARCH64_CALL26 out of range: 150000000 is not in [-134217728, 134217727]

2. Use --verbose or-Map: Generate a link map to see sectionlayout and identify which sections are far apart.

3. Consider -ffunction-sections:Splitting functions into separate sections gives the linker moreflexibility in placement, potentially reducing distances.

4. Check for large data in .text:Embedded data (jump tables, constant pools) can push functions apart.Some compilers have options to place these elsewhere.

5. LTO considerations: Link-time optimization candramatically change code layout. If thunk-related issues appear onlywith LTO, the optimizer may be creating larger functions or differentinlining decisions.

Summary

Handling long branches requires coordination across thetoolchain:

The linker's thunk generation is particularly important for largeprograms where cross-compilation-unit calls may exceed branch ranges.Different linkers use different algorithms with various tradeoffsbetween complexity, optimality, and robustness.

RISC-V's linker relaxation is unique in that it can both expand andshrink code, optimizing for both correctness and code size.

Branch instructions on most architectures use PC-relative addressingwith a limited range. When the target is too far away, the branchbecomes "out of range" and requires special handling.

Consider a large binary where main() at address 0x10000calls foo() at address 0x8010000-over 128MiB away. OnAArch64, the bl instruction can only reach ±128MiB, so thiscall cannot be encoded directly. Without proper handling, the linkerwould fail with an error like "relocation out of range." The toolchainmust handle this transparently to produce correct executables.

This article explores how compilers, assemblers, and linkers worktogether to solve the long branch problem.

• Compiler (IR to assembly): Handles branches within a function thatexceed the range of conditional branch instructions
• Assembler (assembly to relocatable file): Handles branches within asection where the distance is known at assembly time
• Linker: Handles cross-section and cross-object branches discoveredduring final layout

Branch range limitations

Different architectures have different branch range limitations.Here's a quick comparison of unconditional branch/call ranges:

The following subsections provide detailed per-architectureinformation, including relocation types relevant for linkerimplementation.

AArch32

In A32 state:

• Branch (b/b<cond>), conditionalbranch and link (bl<cond>)(R_ARM_JUMP24): ±32MiB
• Unconditional branch and link (bl/blx,R_ARM_CALL): ±32MiB

Note: R_ARM_CALL is for unconditionalbl/blx which can be relaxed to BLX inline;R_ARM_JUMP24 is for branches which require a veneer forinterworking.

In T32 state:

• Conditional branch (b<cond>,R_ARM_THM_JUMP8): ±256 bytes
• Short unconditional branch (b,R_ARM_THM_JUMP11): ±2KiB
• ARMv5T branch and link (bl/blx,R_ARM_THM_CALL): ±4MiB
• ARMv6T2 wide conditional branch (b<cond>.w,R_ARM_THM_JUMP19): ±1MiB
• ARMv6T2 wide branch (b.w,R_ARM_THM_JUMP24): ±16MiB
• ARMv6T2 wide branch and link (bl/blx,R_ARM_THM_CALL): ±16MiB. R_ARM_THM_CALL can berelaxed to BLX.

AArch64

• Test and compare branches(tbnz/tbz/cbnz/cbz):±32KiB
• Conditional branches (b.<cond>): ±1MiB
• Unconditional branches (b/bl):±128MiB

PowerPC

• Conditional branch (bc/bcl,R_PPC64_REL14): ±32KiB
• Unconditional branch (b/bl,R_PPC64_REL24/R_PPC64_REL24_NOTOC):±32MiB

RISC-V

• Compressed c.beqz: ±256 bytes
• Compressed c.jal: ±2KiB
• jalr (I-type immediate): ±2KiB
• Conditional branches(beq/bne/blt/bge/bltu/bgeu,B-type immediate): ±4KiB
• jal (J-type immediate, PseudoBR):±1MiB
• PseudoJump (using auipc +jalr): ±2GiB

Qualcomm uC Branch Immediate extension (Xqcibi):

• qc.beqi/qc.bnei/qc.blti/qc.bgei/qc.bltui/qc.bgeui(32-bit, 5-bit compare immediate): ±4KiB
• qc.e.beqi/qc.e.bnei/qc.e.blti/qc.e.bgei/qc.e.bltui/qc.e.bgeui(48-bit, 16-bit compare immediate): ±4KiB

Qualcomm uC Long Branch extension (Xqcilb):

• qc.e.j/qc.e.jal (48-bit,R_RISCV_VENDOR(QUALCOMM)+R_RISCV_QC_E_CALL_PLT): ±2GiB

SPARC

• Compare and branch (cxbe, R_SPARC_5): ±64bytes
• Conditional branches (bcc,R_SPARC_WDISP19): ±1MiB
• call (R_SPARC_WDISP30): ±2GiB

Note: lld does not implement range extension thunks for SPARC.

x86-64

• Short conditional jump (Jcc rel8): -128 to +127bytes
• Short unconditional jump (JMP rel8): -128 to +127bytes
• Near conditional jump (Jcc rel32): ±2GiB
• Near unconditional jump (JMP rel32): ±2GiB

With a ±2GiB range for near jumps, x86-64 rarely encountersout-of-range branches in practice. A single text section would need toexceed 2GiB before thunks become necessary. For this reason, mostlinkers (including lld) do not implement range extension thunks forx86-64.

Compiler: branch relaxation

The compiler typically generates branches using a form with a largerange. However, certain conditional branches may still go out of rangewithin a function.

The compiler measures branch distances and relaxes out-of-rangebranches. In LLVM, this is handled by the BranchRelaxationpass, which runs just before AsmPrinter.

Different backends have their own implementations:

• BranchRelaxation: AArch64, AMDGPU, AVR, RISC-V
• HexagonBranchRelaxation: Hexagon
• PPCBranchSelector: PowerPC
• SystemZLongBranch: SystemZ
• MipsBranchExpansion: MIPS
• MSP430BSel: MSP430

For a conditional branch that is out of range, the pass typicallyinverts the condition and inserts an unconditional branch:

1
2
3
4
5
6
7

# Before relaxation (out of range)
beq .Lfar_target       # ±4KiB range on RISC-V

# After relaxation
bne .Lskip             # Inverted condition, short range
j .Lfar_target         # Unconditional jump, ±1MiB range
.Lskip:

Assembler: instructionrelaxation

The assembler converts assembly to machine code. When the target of abranch is within the same section and the distance is known at assemblytime, the assembler can select the appropriate encoding. This isdistinct from linker thunks, which handle cross-section or cross-objectreferences where distances aren't known until link time.

Assembler instruction relaxation handles two cases (see Clang-O0 output: branch displacement and size increase for examples):

• Span-dependent instructions: Select a largerencoding when the displacement exceeds the range of the smallerencoding. For x86, a short jump (jmp rel8) can be relaxedto a near jump (jmp rel32).
• Conditional branch transform: Invert the conditionand insert an unconditional branch. On RISC-V, a blt mightbe relaxed to bge plus an unconditional branch.

The assembler uses an iterative layout algorithm that alternatesbetween fragment offset assignment and relaxation until all fragmentsbecome legalized. See Integratedassembler improvements in LLVM 19 for implementation details.

Linker: range extensionthunks

When the linker resolves relocations, it may discover that a branchtarget is out of range. At this point, the instruction encoding isfixed, so the linker cannot simply change the instruction. Instead, itgenerates range extension thunks (also called veneers,branch stubs, or trampolines).

A thunk is a small piece of linker-generated code that can reach theactual target using a longer sequence of instructions. The originalbranch is redirected to the thunk, which then jumps to the realdestination.

Range extension thunks are one type of linker-generated thunk. Othertypes include:

• ARM interworking veneers: Switch between ARM andThumb instruction sets (see Linker notes onAArch32)
• MIPS LA25 thunks: Enable PIC and non-PIC codeinteroperability (see Toolchain notes onMIPS)
• PowerPC64 TOC/NOTOC thunks: Handle calls betweenfunctions using different TOC pointer conventions (see Linker notes on PowerISA)

Short range vs long rangethunks

A short range thunk (see lld/ELF's AArch64implementation) contains just a single branch instruction. Since ituses a branch, its reach is also limited by the branch range—it can onlyextend coverage by one branch distance. For targets further away,multiple short range thunks can be chained, or a long range thunk withaddress computation must be used.

Long range thunks use indirection and can jump to (practically)arbitrary locations.

1
2
3
4
5
6
7
8
9

// Short range thunk: single branch, 4 bytes
__AArch64AbsLongThunk_dst:
  b dst                         // ±128MiB range

// Long range thunk: address computation, 12 bytes
__AArch64ADRPThunk_dst:
  adrp x16, dst                 // Load page address (±4GiB range)
  add x16, x16, :lo12:dst       // Add page offset
  br x16                        // Indirect branch

Thunk examples

AArch32 (PIC) (see Linker notes onAArch32):

1
2
3
4
5

__ARMV7PILongThunk_dst:
  movw ip, :lower16:(dst - .)   ; ip = intra-procedure-call scratch register
  movt ip, :upper16:(dst - .)
  add ip, ip, pc
  bx ip

PowerPC64 ELFv2 (see Linker notes on PowerISA):

1
2
3
4
5

__long_branch_dst:
  addis 12, 2, .branch_lt@ha    # Load high bits from branch lookup table
  ld 12, .branch_lt@l(12)       # Load target address
  mtctr 12                      # Move to count register
  bctr                          # Branch to count register

Thunk impact ondebugging and profiling

Thunks are transparent at the source level but visible in low-leveltools:

• Stack traces: May show thunk symbols (e.g.,__AArch64ADRPThunk_foo) between caller and callee
• Profilers: Samples may attribute time to thunkcode; some profilers aggregate thunk time with the target function
• Disassembly: objdump orllvm-objdump will show thunk sections interspersed withregular code
• Code size: Each thunk adds bytes; large binariesmay have thousands of thunks

lld/ELF's thunk creationalgorithm

lld/ELF uses a multi-pass algorithm infinalizeAddressDependentContent:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

assignAddresses();
for (pass = 0; pass < 30; ++pass) {
  if (pass == 0)
    createInitialThunkSections();  // pre-create empty ThunkSections
  bool changed = false;
  for (relocation : all_relocations) {
    if (pass > 0 && normalizeExistingThunk(rel))
      continue;  // existing thunk still in range
    if (!needsThunk(rel)) continue;
    Thunk *t = getOrCreateThunk(rel);
    ts = findOrCreateThunkSection(rel, src);
    ts->addThunk(t);
    rel.sym = t->getThunkTargetSym();  // redirect
    changed = true;
  }
  mergeThunks();  // insert ThunkSections into output
  if (!changed) break;
  assignAddresses();  // recalculate with new thunks
}

Key details:

• Multi-pass: Iterates until convergence (max 30passes). Adding thunks changes addresses, potentially puttingpreviously-in-range calls out of range.
• Pre-allocated ThunkSections: On pass 0,createInitialThunkSections places emptyThunkSections at regular intervals(thunkSectionSpacing). For AArch64: 128 MiB - 0x30000 ≈127.8 MiB.
• Thunk reuse: getThunk returns existingthunk if one exists for the same target;normalizeExistingThunk checks if a previously-created thunkis still in range.
• ThunkSection placement: getISDThunkSecfinds a ThunkSection within branch range of the call site, or createsone adjacent to the calling InputSection.

lld/MachO's thunk creationalgorithm

lld/MachO uses a single-pass algorithm inTextOutputSection::finalize:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

for (callIdx = 0; callIdx < inputs.size(); ++callIdx) {
  // Finalize sections within forward branch range (minus slop)
  while (finalIdx < endIdx && fits_in_range(inputs[finalIdx]))
    finalizeOne(inputs[finalIdx++]);

  // Process branch relocations in this section
  for (Relocation &r : reverse(isec->relocs)) {
    if (!isBranchReloc(r)) continue;
    if (targetInRange(r)) continue;
    if (existingThunkInRange(r)) { reuse it; continue; }
    // Create new thunk and finalize it
    createThunk(r);
  }
}

Key differences from lld/ELF:

• Single pass: Addresses are assigned monotonicallyand never revisited
• Slop reservation: ReservesslopScale * thunkSize bytes (default: 256 × 12 = 3072 byteson ARM64) to leave room for future thunks
• Thunk naming:<function>.thunk.<sequence> where sequenceincrements per target

Thunkstarvation problem: If many consecutive branches need thunks, eachthunk (12 bytes) consumes slop faster than call sites (4 bytes apart)advance. The test lld/test/MachO/arm64-thunk-starvation.sdemonstrates this edge case. Mitigation is increasing--slop-scale, but pathological cases with hundreds ofconsecutive out-of-range callees can still fail.

mold's thunk creationalgorithm

mold uses a two-pass approach: first pessimistically over-allocatethunks, then remove unnecessary ones.

Intuition: It's safe to allocate thunk space andlater shrink it, but unsafe to add thunks after addresses are assigned(would create gaps breaking existing references).

Pass 1 (create_range_extension_thunks):Process sections in batches using a sliding window. The window tracksfour positions:

1
2
3
4
5
6
7
8
9

Sections:   [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] ...
             ^       ^       ^           ^
             A       B       C           D
             |       |_______|           |
             |         batch             |
             |                           |
             earliest                    thunk
             reachable                   placement
             from C

• [B, C) = current batch of sections to process (size≤ branch_distance/5)
• A = earliest section still reachable from C (forthunk expiration)
• D = where to place the thunk (furthest pointreachable from B)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

// Simplified from OutputSection<E>::create_range_extension_thunks
while (b < sections.size()) {
  // Advance D: find furthest point where thunk is reachable from B
  while (d < size && thunk_at_d_reachable_from_b)
    assign_address(sections[d++]);

  // Compute batch [B, C)
  c = b + 1;
  while (c < d && sections[c] < sections[b] + batch_size) c++;

  // Advance A: expire thunks no longer reachable
  while (a < b && sections[a] + branch_distance < sections[c]) a++;
  // Expire thunk groups before A: clear symbol flags.
  for (; t < thunks.size() && thunks[t].offset < sections[a]; t++)
    for (sym in thunks[t].symbols) sym->flags = 0;

  // Scan [B,C) relocations. If a symbol is not assigned to a thunk group yet,
  // assign it to the new thunk group at D.
  auto &thunk = thunks.emplace_back(new Thunk(offset));
  parallel_for(b, c, [&](i64 i) {
    for (rel in sections[i].relocs) {
      if (requires_thunk(rel)) {
        Symbol &sym = rel.symbol;
        if (!sym.flags.test_and_set()) {  // atomic: skip if already set
          lock_guard lock(mu);
          thunk.symbols.push_back(&sym);
        }
      }
    }
  });
  offset += thunk.size();
  b = c;  // Move to next batch
}

Pass 2 (remove_redundant_thunks): Afterfinal addresses are known, remove thunk entries for symbols actually inrange.

Key characteristics:

• Pessimistic over-allocation: Assumes allout-of-section calls need thunks; safe to shrink later
• Batch size: branch_distance/5 (25.6 MiB forAArch64, 3.2 MiB for AArch32)
• Parallelism: Uses TBB for parallel relocationscanning within each batch
• Single branch range: Uses one conservativebranch_distance per architecture. For AArch32, uses ±16 MiB(Thumb limit) for all branches, whereas lld/ELF uses ±32 MiB for A32branches.
• Thunk size not accounted in D-advancement: Theactual thunk group size is unknown when advancing D, so the end of alarge thunk group may be unreachable from the beginning of thebatch.
• No convergence loop: Single forward pass foraddress assignment, no risk of non-convergence

Comparing thunk algorithms

Linker relaxation (RISC-V)

RISC-V takes a different approach: instead of only expandingbranches, it can also shrink instruction sequences whenthe target is close enough.

Consider a function call using the callpseudo-instruction, which expands to auipc +jalr:

1
2
3
4
5

# Before linking (8 bytes)
call ext
# Expands to:
#   auipc ra, %pcrel_hi(ext)
#   jalr ra, ra, %pcrel_lo(ext)

If ext is within ±1MiB, the linker can relax this to:

1
2

# After relaxation (4 bytes)
jal ext

This is enabled by R_RISCV_RELAX relocations thataccompany R_RISCV_CALL relocations. TheR_RISCV_RELAX relocation signals to the linker that thisinstruction sequence is a candidate for shrinking.

Example object code before linking:

1
2
3
4
5
6
7
8
9

0000000000000006 <foo>:
       6: 97 00 00 00   auipc   ra, 0
                R_RISCV_CALL ext
                R_RISCV_RELAX *ABS*
       a: e7 80 00 00   jalr    ra
       e: 97 00 00 00   auipc   ra, 0
                R_RISCV_CALL ext
                R_RISCV_RELAX *ABS*
      12: e7 80 00 00   jalr    ra

After linking with relaxation enabled, the 8-byteauipc+jalr pairs become 4-bytejal instructions:

1
2
3
4
5
6

0000000000000244 <foo>:
     244: 41 11         addi    sp, sp, -16
     246: 06 e4         sd      ra, 8(sp)
     248: ef 00 80 01   jal     ext
     24c: ef 00 40 01   jal     ext
     250: ef 00 00 01   jal     ext

When the linker deletes instructions, it must also adjust:

• Subsequent instruction offsets within the section
• Symbol addresses
• Other relocations that reference affected locations
• Alignment directives (R_RISCV_ALIGN)

This makes RISC-V linker relaxation more complex than thunkinsertion, but it provides code size benefits that other architecturescannot achieve at link time.

Diagnosing out-of-rangeerrors

When you encounter a "relocation out of range" error, here are somediagnostic steps:

1. Check the error message: lld reports the sourcelocation, relocation type, and the distance. For example:

   1	ld.lld: error: a.o:(.text+0x1000): relocation R_AARCH64_CALL26 out of range: 150000000 is not in [-134217728, 134217727]

2. Use --verbose or-Map: Generate a link map to see sectionlayout and identify which sections are far apart.

3. Consider -ffunction-sections:Splitting functions into separate sections gives the linker moreflexibility in placement, potentially reducing distances.

4. Check for large data in .text:Embedded data (jump tables, constant pools) can push functions apart.Some compilers have options to place these elsewhere.

5. LTO considerations: Link-time optimization candramatically change code layout. If thunk-related issues appear onlywith LTO, the optimizer may be creating larger functions or differentinlining decisions.

Summary

Handling long branches requires coordination across thetoolchain:

The linker's thunk generation is particularly important for largeprograms where cross-compilation-unit calls may exceed branch ranges.Different linkers use different algorithms with various tradeoffsbetween complexity, optimality, and robustness.

RISC-V's linker relaxation is unique in that it can both expand andshrink code, optimizing for both correctness and code size.

• Milestone

This is a release focussing on bug fixing, in particular regressions from the release 1.28.0.

Selected new features ✨:

• New customisable message for closed registrations
• Add username in Apache access logs (also in Docker logs): for GReader API, and for HTTP Basic Auth from reverse proxy

Improved performance 🏎️:

• Disable counting articles in user labels for Ajax requests (unused)

Many bug fixes 🐛

This release has been made by @Alkarex, @Frenzie, @Inverle and newcomers @ciro-mota, @eveiscoull, @hackerman70000, @Hufschmidt, @johan456789, @martgnz, @mmeier86, @netsho, @neuhaus, @RobLoach, @rupakbajgain.

Full changelog:

• Features
  • Handle Web scraping of text/plain as <pre class="text-plain"> #8340
  • New customisable message for closed registrations #8462
• Bug fixing
  • Fix unwanted expansion of user queries (saved searches) applied to filters #8395
  • Fix encoding of filter actions for labels #8368
  • Fix searching of tags #8425
  • Fix refreshing feeds with token while anonymous refresh is disabled #8371
  • Fix RSS and OPML access by token #8434
  • Fix MySQL/MariaDB transliterator_transliterate fallback (when the php-intl extension is unavailable) #8427
  • Fix regression with MySQL/MariaDB index hint #8460
  • Auto-add lastUserModified database column also during mark-as-read action #8346
  • Do not include hidden feeds when counting unread articles in categories #8357
  • Remove wrong PHP deprecation of OPML export action #8399
  • Fix shortcut for next unread article #8466
  • Fix custom session.cookie-lifetime #8446
  • Fix feed validator button when changing the feed URL #8436
• Performance
  • Disable counting articles in user labels for Ajax requests (unused) #8352
• Security
  • Change Content-Disposition: inline to attachment in f.php #8344
  • Hardened user methods exists, mtime, ctime #26c1102
• Deployment
  • Add username in Apache access logs (also in Docker logs): for GReader API, and for HTTP Basic Auth from reverse proxy #8392
• SimplePie
  • Update of CURLOPT_ACCEPT_ENCODING #8376, simplepie#960, simplepie#962
  • Fix don’t preserve children inside disallowed <template> element #8443
  • Fixes before PHPStan 2 #8445, simplepie#957
• Extensions
  • Update .gitignore to ignore installed extensions #8372
• UI
  • Add data-category="3" to ease custom CSS styling of articles #8397
  • Fix space between By: and the author’s name #8422
• I18n
  • Improve Brazilian Portuguese #8411
  • Improve Dutch #8403
  • Improve German #8402
  • Improve Polish #8408
  • Improve Spanish #8464
• Misc.
  • Update dev dependencies #8387, #8388, #8389,
    #8390, #8391, #8393,
    #8453

前言

前阵子写的日志分析工具NginxPulse，自开源以来，已过去2周时间，目前GitHub已收获1.5k的star。收到了不少用户的反馈建议，花了点时间将这些问题都处理了下。

本文就跟大家分享下新版本都解决了哪些问题，优化了哪些内容，欢迎各位感兴趣的开发者阅读本文。

抛弃SQLite

有不少用户反馈说日志文件很大的时候（10G+），解析速度非常慢，需要解析好几个小时，解析完成之后数据看板的查询也比较慢（接口响应在5秒左右）。

于是，我重写了日志解析策略（解析阶段不做IP归属地查询，仅入库其他数据，将日志中IP记录起来），日志解析完毕后，将记录的IP做去重处理，随后去做归属地的查询处理（优先本地的ip2region库，远程的API调用查询做兜底），最后将解析到的归属地回填至对应的数据库表中，这样一套下来就可以大大提升日志的解析速度。

数据库的数据量大了之后，SQLite的表现就有点差强人意了，请教了一些后端朋友，他们给了我一些方案，结合我自身的实际场景后，最后选定了PostgreSQL作为新的数据库选型。

这套方案落地后，用户群的好兄弟说：他原先需要解析1个小时的日志，新版只需要10多分钟。

UI配置可视化使用

有一部分用户反馈说他非专业人士，这些晦涩的配置对他来说使用门槛太高了，希望能有一个UI配置页面，他只需要点一点、敲敲键盘，就能完成这些配置。

我将整个配置流程做成了4步，同时也准备一个演示视频 - www.bilibili.com/video/BV1hq…

• 配置站点
• 配置数据库
• 配置运行参数
• 确认最终配置

新增wiki文档

因为配置过于庞大，仓库主页浏览README.md比较费劲，希望能整理一份wiki文档发上去。

花了点时间，简化了下README，整理了一份：github.com/likaia/ngin…

访问明细模块优化

有部分用户反馈说希望增加更多的筛选条件以及导出Excel功能，现在它来了：

概况模块优化

概况页面的日期筛选之前放在趋势分析卡片的上方，但是他的切换影响的维度还包含了指标，于是我就调整了下它的位置，新版如下图所示：

项目地址

• GitHub地址：github.com/likaia/ngin…
• dockerhub地址：hub.docker.com/r/magiccode…

写在最后

至此，文章就分享完毕了。

我是神奇的程序员，一位前端开发工程师。

如果你对我感兴趣，请移步我的个人网站，进一步了解。

给你个整数数组 arr，其中每个元素都 不相同。

请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。

每对元素对 [a,b] 如下：

• a , b 均为数组 arr 中的元素
• a < b
• b - a 等于 arr 中任意两个元素的最小绝对差

示例 1：

输入：arr = [4,2,1,3]
输出：[[1,2],[2,3],[3,4]]

示例 2：

输入：arr = [1,3,6,10,15]
输出：[[1,3]]

示例 3：

输入：arr = [3,8,-10,23,19,-4,-14,27]
输出：[[-14,-10],[19,23],[23,27]]

提示：

• 2 <= arr.length <= 10^5
• -10^6 <= arr[i] <= 10^6

Button Pattern 详解：构建无障碍按钮组件

按钮是 Web 界面中最基础的交互元素之一，它让用户能够触发特定的操作或事件，如提交表单、打开对话框、取消操作或执行删除操作。根据 W3C WAI-ARIA Button Pattern 规范，正确实现的按钮组件不仅要具备良好的视觉效果，更需要确保所有用户都能顺利使用，包括依赖屏幕阅读器等辅助技术的用户。本文将深入探讨 Button Pattern 的核心概念、实现要点以及最佳实践。

一、按钮的定义与核心功能

按钮是一个允许用户触发动作或事件的界面组件。从功能角度来看，按钮执行的是动作而非导航，这是按钮与链接的本质区别。常见的按钮功能包括：提交表单数据、打开对话框窗口、取消正在进行的操作、删除特定内容等。一个设计良好的按钮应当让用户清晰地感知到点击它将产生什么效果，这种可预期性是良好用户体验的重要组成部分。

在实际开发中，有一个广为接受的约定值得注意：如果按钮的操作会打开一个对话框或其他需要进一步交互的界面，应该在按钮标签后加上省略号（...）来提示用户。例如，**保存为...**这样的标签能够告诉用户，点击这个按钮后会弹出额外的对话框需要填写。这种细节虽然看似微小，却能显著提升用户对界面行为的理解。

二、按钮的三种类型

WAI-ARIA 规范支持三种类型的按钮，每种类型都有其特定的用途和实现要求。理解这三种类型的区别对于构建正确无障碍的界面至关重要。

2.1 普通按钮

普通按钮是最常见的按钮类型，它执行单一的操作而不涉及状态的切换。提交表单的提交按钮、触发某个动作的执行按钮都属于这一类别。普通按钮在激活时会执行预定义的操作，操作完成后通常会根据操作的性质决定焦点的移动位置。例如，打开对话框的按钮在激活后，焦点应移动到对话框内部；而执行原地操作的按钮则可能保持焦点在原位。

<button type="submit">提交表单</button>

2.2 切换按钮

切换按钮是一种具有两种状态的按钮，可以处于未按下或已按下的状态。这种按钮通过 aria-pressed 属性向辅助技术传达其当前状态。例如，音频播放器中的静音按钮就可以实现为切换按钮：当声音处于静音状态时，按钮的 aria-pressed 值为 true；当声音正常播放时，该值为 false。

实现切换按钮时有一个关键原则需要牢记：按钮的标签在状态改变时不应发生变化。无论按钮是处于按下还是未按下状态，其可访问名称应该保持一致。屏幕阅读器用户依赖这个稳定的标签来理解按钮的功能。如果设计要求在状态改变时显示不同的文本，那么就不应使用 aria-pressed 属性，而是应该通过其他方式传达状态变化。

<button
  type="button"
  aria-pressed="false"
  id="muteButton">
  静音
</button>

<script>
  muteButton.addEventListener('click', function () {
    const isMuted = this.getAttribute('aria-pressed') === 'true';
    this.setAttribute('aria-pressed', !isMuted);
  });
</script>

2.3 菜单按钮

菜单按钮是一种特殊的按钮，点击后会展开一个菜单或其他弹出式界面。根据 WAI-ARIA 规范，通过将 aria-haspopup 属性设置为 menu 或 true，可以将按钮向辅助技术揭示为菜单按钮。这种按钮在用户界面中非常常见，例如许多应用中的文件菜单、编辑菜单等。

菜单按钮的实现需要遵循菜单模式的相关规范，确保用户能够通过键盘导航菜单项，屏幕阅读器能够正确播报菜单状态，视觉用户能够清晰地看到菜单的展开和收起状态。正确实现的菜单按钮应当提供平滑的用户体验，无论用户使用何种输入方式或辅助技术。

<button
  type="button"
  aria-haspopup="menu"
  id="fileMenu">
  文件
</button>

三、键盘交互规范

键盘可访问性是 Web 无障碍设计的核心要素之一。按钮组件必须支持完整的键盘交互，确保无法使用鼠标的用户也能顺利操作。根据 Button Pattern 规范，当按钮获得焦点时，用户应能通过以下按键与按钮交互：

空格键和回车键是激活按钮的主要方式。当用户按下空格键或回车键时，按钮被触发执行其预定义的操作。这个设计遵循了用户对表单控件的既有认知，与传统桌面应用的交互模式保持一致。

按钮激活后焦点的处理需要根据具体情境来决定，这是实现良好键盘体验的关键。如果按钮打开了一个对话框，焦点应移动到对话框内部，通常是对话框的第一个可聚焦元素或默认焦点元素。如果按钮关闭了对话框，焦点通常应返回到打开该对话框的按钮，除非对话框中的操作逻辑上应该导致焦点移动到其他位置。例如，在确认删除操作的对话框中点击确认后，焦点可能会移动到页面上的其他相关元素。

对于不会关闭当前上下文的按钮（如应用按钮、重新计算按钮），激活后焦点通常应保持在原位。如果按钮的操作表示上下文将要发生变化（如向导中的下一步），则应将焦点移动到该操作的起始位置。对于通过快捷键触发的按钮，焦点通常应保持在触发快捷键时的上下文中。

四、WAI-ARIA 角色、状态和属性

正确使用 WAI-ARIA 属性是构建无障碍按钮组件的技术基础。虽然语义化的 HTML 按钮元素（button）本身已经具备正确的角色和基本行为，但在某些情况下需要使用自定义实现或 ARIA 属性来增强可访问性。

角色声明是基础要求。按钮元素的 role 属性应设置为 button，向辅助技术表明这是一个按钮组件。对于使用 button 这样的原生 HTML 元素，浏览器会自动处理角色声明，无需开发者手动添加。

示例：使用 div 元素模拟按钮时需要添加 role="button"：

<div
  role="button"
  tabindex="0"
  onclick="handleClick()">
  提交
</div>

可访问名称是按钮最重要的可访问性特征之一。按钮必须有可访问的名称，这个名称可以通过多种方式提供：按钮内部的文本内容是最常见的来源；在某些情况下，可以使用 aria-labelledby 引用页面上的其他元素作为标签；或者使用 aria-label 直接提供标签文本。屏幕阅读器用户主要依赖这个名称来理解按钮的功能。

示例 1：使用 aria-labelledby 引用其他元素作为标签：

<h2 id="save-heading">保存设置</h2>
<button
  role="button"
  aria-labelledby="save-heading">
  图标
</button>

示例 2：使用 aria-label 直接提供标签文本：

<button
  aria-label="关闭对话框"
  onclick="closeDialog()">
  ×
</button>

描述信息可以通过 aria-describedby 属性关联。如果页面上存在对按钮功能的详细描述说明，应将描述元素的 ID 赋给这个属性，辅助技术会在播报按钮名称后继续播报描述内容。

示例：使用 aria-describedby 提供详细描述：

<button aria-describedby="delete-warning">删除</button>
<p id="delete-warning">此操作无法撤销，将永久删除所选数据。</p>

禁用状态需要正确使用 aria-disabled 属性。当按钮的关联操作不可用时，应设置 aria-disabled="true"。这个属性向辅助技术传达按钮当前处于禁用状态，用户无法与之交互。需要注意的是，对于原生 HTML button 元素，应使用 disabled 属性而非 aria-disabled。

示例：使用 aria-disabled 禁用非原生按钮：

<div
  role="button"
  tabindex="-1"
  aria-disabled="true"
  aria-label="保存">
  保存
</div>

切换状态使用 aria-pressed 属性来传达，这个属性只用于实现为切换按钮的组件。属性值应为 true（按下状态）、false（未按下状态）或 mixed（部分选中状态，用于三态树节点等场景）。

示例：使用 aria-pressed 实现切换按钮：

<button
  type="button"
  aria-pressed="false"
  id="toggleBtn"
  onclick="toggleState()">
  夜间模式
</button>

五、按钮与链接的区别

在 Web 开发中，一个常见的混淆点是何时应该使用按钮，何时应该使用链接。这两者的功能定位有着本质的区别，理解这个区别对于构建语义正确的页面至关重要。

按钮用于触发动作，如提交表单、打开对话框、执行计算、删除数据等。这些操作会产生副作用，改变应用的状态或数据。链接用于导航，将用户带到另一个页面、页面的不同位置或不同的应用状态。链接的本质是超文本引用，它告诉用户这里有你可能感兴趣的另一个资源。

从技术实现角度，这个区别直接影响了可访问性。屏幕阅读器对按钮和链接的播报方式不同，用户会根据这些提示形成对界面功能的预期。如果一个元素看起来像链接（蓝色下划线文本）但点击后执行的是按钮的动作（提交表单），会给用户造成困惑。即使出于设计考虑必须使用这种视觉与功能的组合，也应通过 role="button" 属性明确告诉辅助技术这个元素的真实功能，避免给依赖辅助技术的用户带来困惑。

更好的做法是调整视觉设计，使其与功能保持一致。如果某个元素执行的是动作，就应该看起来像一个按钮；如果用户需要被导航到新页面，就应该使用标准的链接样式。这种设计上的统一能够减少所有用户的认知负担。

六、其他示例

以下是一个常见按钮场景的实现示例——打开对话框的按钮，展示了如何正确应用 Button Pattern 规范。

使用 HTML 原生 <dialog> 元素配合按钮实现对话框功能：

<button
  type="button"
  aria-haspopup="dialog"
  aria-expanded="false"
  id="openDialog">
  设置...
</button>

<dialog id="settingsDialog">
  <form method="dialog">
    <label> <input type="checkbox" /> 启用通知 </label>
    <button value="confirm">确定</button>
  </form>
</dialog>

<script>
  const dialog = document.getElementById('settingsDialog');
  const openBtn = document.getElementById('openDialog');

  openBtn.addEventListener('click', () => {
    dialog.showModal();
    openBtn.setAttribute('aria-expanded', 'true');
  });

  dialog.addEventListener('close', () => {
    openBtn.setAttribute('aria-expanded', 'false');
  });
</script>

当按钮会打开对话框时，使用省略号提示用户后面还有额外交互。aria-haspopup 表明按钮会弹出内容，aria-expanded 用于传达弹出内容的当前状态。

七、CSS 伪类与交互样式

以下 CSS 伪类可用于增强按钮的键盘交互体验：

/* Tab 键导航到按钮时显示焦点框 */
button:focus {
  outline: 2px solid blue;
  outline-offset: 2px;
}

/* 仅键盘焦点显示样式，鼠标点击不显示 */
button:focus-visible {
  outline: 2px solid currentColor;
  outline-offset: 2px;
}

/* 空格键或回车键按下时的样式 */
button:active {
  transform: scale(0.98);
}

/* 鼠标悬停效果（可选，增强视觉反馈） */
button:hover {
  opacity: 0.9;
}

/* Tab + Space 组合键激活样式（需 JS 添加类） */
button.keyboard-active {
  transform: scale(0.95);
  background-color: oklch(from currentColor 0.8);
}

/* Tab + Enter 组合键激活样式（需 JS 添加类） */
button.keyboard-enter {
  transform: scale(0.95);
  background-color: oklch(from currentColor 0.8);
}

各伪类说明：

7.1 组合键交互示例

CSS 本身无法直接检测组合键，但可以通过 JavaScript 增强体验：

<button id="submitBtn">提交</button>

<style>
  /* Tab + Space 激活状态 */
  button.space-pressed {
    transform: scale(0.95);
    box-shadow: inset 0 2px 4px rgba(0, 0, 0, 0.2);
  }

  /* Tab + Enter 激活状态 */
  button.enter-pressed {
    transform: scale(0.95);
    background-color: oklch(from var(--btn-bg, currentColor) 0.8);
  }
</style>

<script>
  const btn = document.getElementById('submitBtn');

  // Tab + Space 组合键
  btn.addEventListener('keydown', (e) => {
    if (e.key === ' ' && e.target === document.activeElement) {
      btn.classList.add('space-pressed');
    }
    if (e.key === 'Enter' && e.target === document.activeElement) {
      btn.classList.add('enter-pressed');
    }
  });

  btn.addEventListener('keyup', (e) => {
    if (e.key === ' ') {
      btn.classList.remove('space-pressed');
    }
    if (e.key === 'Enter') {
      btn.classList.remove('enter-pressed');
    }
  });
</script>

组合键说明：

原生 HTML 按钮的行为：

• <button>：Tab 聚焦后按 Space/Enter 都会触发点击
• <div role="button">：需要额外 JS 处理 Space 键

八、总结

构建无障碍的按钮组件需要关注多个层面的细节。从视觉设计角度，按钮应该让用户清晰地感知到它是一个可交互的元素；从键盘交互角度，必须支持空格键和回车键的激活操作；从 ARIA 属性角度，需要正确使用角色、状态和属性来传达组件的语义和当前状态。

按钮与链接的功能区分是 Web 语义化的基础之一，遵循这个原则不仅有助于辅助技术用户理解页面结构，也能提升所有用户的使用体验。在实际开发中，优先使用语义化的原生 HTML 元素，只有在必要时才考虑使用自定义实现，并确保为这些实现添加完整的无障碍支持。

WAI-ARIA Button Pattern 为我们提供了清晰的指导方针，将这些规范内化为开发习惯，能够帮助我们创建更加包容和易用的 Web 应用。每一个正确实现的按钮组件，都是构建无障碍网络环境的重要一步。

排序 + 模拟

数据范围为 $1e5$，我们不能通过枚举的方式遍历所有的点对找最小值。

我们可以对 arr 进行排序，容易得知差值最小值必然发生在排序数组的相邻元素之间，此时我们可以通过遍历排序数组并使用变量 min 记录当前差值最小值来统计答案。

代码：

###Java

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        List<List<Integer>> ans = new ArrayList<>();
        int n = arr.length, min = arr[1] - arr[0];
        for (int i = 0; i < n - 1; i++) {
            int cur = arr[i + 1] - arr[i];
            if (cur < min) {
                ans.clear();
                min = cur;
            }
            if (cur == min) {
                List<Integer> temp = new ArrayList<>();
                temp.add(arr[i]); temp.add(arr[i + 1]);
                ans.add(temp);
            }
        }
        return ans;
    }
}

• 时间复杂度：$O(n\log{n})$
• 空间复杂度：$O(\log{n})$

同类型加餐

题太简单？今日份加餐：【面试高频题】难度 1.5/5，数据结构运用题 🎉 🎉

或是考虑加练如下「模拟」题 🍭🍭🍭

注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~