Hacker News Reader

anderskaseorgon Parallel Parentheses Matching

You have ignored the much larger space and time cost of constructing the range minimum query tree in the first place. Furthermore, nobody would arbitrarily cut off a problem at “billions” and then consider O(√billions) or O(∜billions) to be “effectively O(1)”: a theoretician would complain that O() by definition measures the limiting behavior as the problem size tends to ∞, an engineer would complain that 65536 or 256 is very a important factor in practice, and both types are better served by leaving O(√n) or O(∜n) as-is instead of trying to hand-wave it away.

anderskaseorgon Show HN: A game where you build a GPU

The “next level” button takes you to the next level even if you haven’t solved that level’s prerequisites.

anderskaseorgon Tell HN: Litellm 1.82.7 and 1.82.8 on PyPI are compromised

Right, the public was able to spend manual effort hand-auditing one specific tarball after it had already been singled out as suspicious for other reasons. In order for verification to effectively increase supply chain security, it needs to become uniformly standardized, fully automated, and ubiquitous. That’s the ultimate goal of the provenance attestation mechanisms that would be defeated by indirection through private repositories.

If you want to require extra maintainer intervention for releases, there are better mechanisms available for that, such as workflow_dispatch.

anderskaseorgon Tell HN: Litellm 1.82.7 and 1.82.8 on PyPI are compromised

The maintainer can verify the correspondence between source and release, but the public has been deprived of this verifiability.

This matters. Consider the XZ Utils compromise where a malicious maintainer hid the line that triggers compilation of the (otherwise dormant) backdoor payload in a generated file present only in the release tarball: https://www.openwall.com/lists/oss-security/2024/03/29/4. If the public had the ability to audit that the release tarball was correctly built from the version-controlled code, this would have been much more difficult to hide.

anderskaseorgon Tell HN: Litellm 1.82.7 and 1.82.8 on PyPI are compromised

The point of trusted publishing is supposed to be that the public can verifiably audit the exact source from which the published artifacts were generated. Breaking that chain via a private repo is a step backwards.

https://docs.npmjs.com/generating-provenance-statements

https://packaging.python.org/en/latest/specifications/index-...

anderskaseorgon Subsecond: A runtime hotpatching engine for Rust hot-reloading

There is a well-defined reload point—it’s the `subsecond::call` wrapper around `tick()`. But the hypothetical design that you seem to have in mind where this doesn’t exist would not have a well-defined reload point, so it would need to be able to preempt your program anywhere.

Layout changes are supported for structs that don’t persist across the well-defined reload point.

anderskaseorgon uv: An extremely fast Python package and project manager, written in Rust

Yes, uv has a standard permissive open source license (Apache-2.0 OR MIT): https://github.com/astral-sh/uv/?tab=readme-ov-file#license

anderskaseorgon Rust's Sneaky Deadlock With `if let` Blocks

Of course (but that’s not relevant to the original scenario, where the programmer is hypothetically not aware that the read lock is still being held, let alone that they could manually upgrade it after changing to a different lock library).

anderskaseorgon Rust's Sneaky Deadlock With `if let` Blocks

Yes, allowing this to execute would be very unsound:

    let lock = RwLock::new(Box::new(111));
    let r: &i32 = &**lock.read().unwrap(); // points to 111
    *lock.write().unwrap() = Box::new(222); // allocates a new Box and deallocates 111
    println!("{}", *r); // use after free

anderskaseorgon Rust's Sneaky Deadlock With `if let` Blocks

Clippy already has an error for this pattern with Mutex. It should be trivial to extend it to cover RwLock.

    error: calling `Mutex::lock` inside the scope of another `Mutex::lock` causes a deadlock
      --> src/main.rs:5:5
       |
    5  |       if let Some(num) = *map.lock().unwrap() {
       |       ^                   --- this Mutex will remain locked for the entire `if let`-block...
       |  _____|
       | |
    6  | |         eprintln!("There's a number in there: {num}");
    7  | |     } else {
    8  | |         let mut lock2 = map.lock().unwrap();
       | |                         --- ... and is tried to lock again here, which will always deadlock.
    9  | |         *lock2 = Some(5);
    10 | |         eprintln!("There will now be a number {lock2:?}");
    11 | |     }
       | |_____^
       |
       = help: move the lock call outside of the `if let ...` expression
       = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#if_let_mutex
       = note: `#[deny(clippy::if_let_mutex)]` on by default

anderskaseorgon An illustrated proof of the CAP theorem (2018)

There are plenty of systems that sacrifice consistency even while the network is fully connected, in the name of performance—for example, DNS, or any system with a caching proxy server.

anderskaseorgon An illustrated proof of the CAP theorem (2018)

You’re certainly allowed to make the client a more active participant in your consensus protocol, but then it needs to play by the same rules if you want the system to have guarantees. For example, you need to handle network partitions between clients and some servers, and you need to be able to reconcile multiple reads from servers that might have seen different sets of writes. The CAP theorem still applies to the system as a whole.

anderskaseorgon Rewrite cname uncloaking code to account for new ipaddress= option

They’re doing a slow phase-out over a long time to try to avert a wave of bad publicity that threatens their browser monopoly, but that timeline has already started as of June.

https://developer.chrome.com/docs/extensions/develop/migrate...

https://www.bleepingcomputer.com/news/google/google-chrome-w...

anderskaseorgon Bootstrappable Builds

The mechanism is a clever application of quines (self-reproducing programs), first explained in the classic lecture “Reflections on Trusting Trust” by Ken Thompson:

https://dl.acm.org/doi/pdf/10.1145/358198.358210

Russ Cox obtained the actual code for Thompson’s compiler backdoor and presented it here:

https://research.swtch.com/nih

anderskaseorgon tolower() with AVX-512

When the term “undefined behavior” appears within the C standard, yes, that’s what it means. There is no way for another document to alter the meaning of “undefined behavior” as it appears within the C standard.

When the term “undefined behavior” appears in different context, we use our writing and reading comprehension skills to agree on what it means. If we’re programming in standard C, it refers to one class of behavior. If we’re programming in POSIX C, it refers to a smaller class of behavior (even according to the C standards committee: see the usage of “otherwise undefined behavior” in N2464). If we’re programming in Rust, it refers to a completely different class of behavior.

From my very first message, I did my part by providing the context explicitly: “undefined behavior in the Rust and LLVM memory model”. You complained that it’s nonsense to talk about “undefined behavior” in any context other than the C standard, but I provided references showing that it’s not. Yet you persist in intentionally misinterpreting what I wrote in order to accuse me of gaslighting. Does that make you feel superior?

anderskaseorgon .INTERNAL is now reserved for private-use applications

The jurisdictional status of .local and other standards-reserved special use domains is explained by RFC 6761 section 3:

https://datatracker.ietf.org/doc/html/rfc6761#section-3

And ICANN is bound by the IETF/ICANN Memorandum of Understanding Concerning the Technical Work of the IANA, which prevents it from usurping that jurisdiction:

https://www.icann.org/resources/pages/agreements-en

anderskaseorgon tolower() with AVX-512

If a program’s behavior is undefined in one specification and defined in a second, then insofar as both specifications apply to it, that is defined behavior, not undefined behavior. That’s not an obscure property of terms of art and specific formal definitions about which I need to be educated, it’s just basic logic about which we obviously agree. The conclusion would be the same if one specification explicitly said “this may return an empty allocation or NULL or format your hard drive” and a second specification said “this will return an empty allocation or NULL”; the conjunction of those two specifications entails that it will not format your hard drive.

There’s nothing wrong or misleading in what I wrote. If, hypothetically, there were a second specification that constrained the Rust compiler’s translation of programs that over-read memory, then it would have been wrong to write that over-reading memory in Rust is undefined behavior, and misleading to suggest that a statement about “any undefined behavior” is applicable to it. But there is no such second specification (as confirmed by comments on the issue I linked from RalfJung, whose formal specification hat is much pointier than either of ours), and you aren’t even disputing that. Instead, you have deliberately misapplied a statement about “any undefined behavior” to other unrelated behavior that is in fact defined, in order to construct a pretense for calling someone else dishonest. Find better hobbies.

anderskaseorgon tolower() with AVX-512

It seems like you think I’m saying that all compilers are required to recognize all forms of UB and format your hard drive. Of course not; some UB in one specification may be defined in another more restrictive spec, some UB may be defined by compiler flags like -fwrapv, some UB might be detected and converted to a compile-time or runtime error, and some UB might happen to behave like you expect because your compiler didn’t implement certain optimizations yet or you just got lucky.

It sounds like you agree that programmers should avoid relying on luck for UB safety. If you have a way to prove that this UB is actually safe and not just lucky, feel free to present it. Until then, I stand by everything I’ve said.

anderskaseorgon tolower() with AVX-512

You may not like it, and it’s within your rights not to like it, but the reality is that compilers do treat UB this way, and it’s not “grossly dishonest FUD” to point out that this is the reality. Here’s a test case demonstrating that UB can actually format your hard drive: https://bugs.llvm.org/show_bug.cgi?id=49599.

Note that one of the differences between C and Rust is that integer overflow is not UB in Rust (it panics in debug mode and wraps in release mode: https://doc.rust-lang.org/book/ch03-02-data-types.html#integ...). But there are other sources of UB in unsafe Rust, such reads through a pointer not allowed by the memory model.

anderskaseorgon tolower() with AVX-512

Both (unsafe) Rust and LLVM have their own concepts of undefined behavior (https://doc.rust-lang.org/reference/behavior-considered-unde..., https://llvm.org/docs/LangRef.html#undefined-values), and while some of the details vary by language, compilers for all of these languages do in fact optimize based on the assumption that undefined behavior is not invoked in the abstract execution model. This is a real thing (https://blog.llvm.org/2011/05/what-every-c-programmer-should..., https://highassurance.rs/chp3/undef.html), and any debate about whether it’s “justified” is many decades late and entirely academic (but we don’t have any other methodology for building optimizers of the quality that programmers expect from compiled languages).

anderskaseorgon tolower() with AVX-512

Note that the “unsafe read beyond of death” trick is considered undefined behavior in the Rust and LLVM memory model, even if it’s allowed by the underlying hardware. Like any undefined behavior, compilers are allowed to assume it doesn’t happen for the purpose of optimization, leading to results you don’t expect. The only way around this is to use inline assembly.

https://github.com/ogxd/gxhash/issues/82

anderskaseorgon Zulip 9.0: Organized chat for distributed teams

Here’s a message where you can see what this feature looks like (no login required): https://chat.zulip.org/#narrow/stream/101-design/topic/clock...

(Note that the sender opts in to this with a specific syntax; we don’t try to heuristically match anything that looks like a time.)

anderskaseorgon Zulip 9.0: Organized chat for distributed teams

Not yet, though there’s been some progress on developing this feature. You can upvote https://github.com/zulip/zulip/issues/23995 to help us prioritize it.

anderskaseorgon Zulip 9.0: Organized chat for distributed teams

We’d like to fix this! You can upvote https://github.com/zulip/zulip/issues/21881 to help us prioritize this feature.

anderskaseorgon HTML Tags Memory Test

It worked in all major browsers until it was removed around 2017–2019. I personally used it, as part of MIT’s authentication systems.

anderskaseorgon Special-use domain 'home.arpa.' (2018)

That will never happen, but RFC 6762 suggests some other options for private networks: .intranet, .internal, .private, .corp, .lan.

https://datatracker.ietf.org/doc/html/rfc6762#appendix-G

ICANN seems to be in the process of finalizing a proposal to officially reserve .internal for this purpose.

https://www.icann.org/en/announcements/details/icann-seeks-f...

anderskaseorgon Cve-rs: Fast memory vulnerabilities, written in safe Rust

We could choose to design the language as I wrote where the constraint is implicitly present and variance consequently ought to preserve it, or as you wrote where it is not present at all and variance is unsound. But we want Rust to be sound, so we should choose the former design. We would need a very compelling reason to prefer the latter—for example, some evidence that “it would break too much code” or “it’s impossible to implement”—but I don’t see anyone claiming to actually have such evidence. The only reason the implementation has not been updated to align with the sound design is that it takes work and that work is still ongoing.

anderskaseorgon Cve-rs: Fast memory vulnerabilities, written in safe Rust

https://github.com/rust-lang/rust/issues/25860#issuecomment-...

“Similarly, the reason why niko's approach is not yet implemented is simply that getting the type system to a point where we even can implement this is Hard. Fixing this bug is blocked on replacing the existing trait solver(s): #107374. A clean fix for this issue (and the ability to even consider using proof objects), will then also be blocked blocked on coinductive trait goals and explicit well formed bounds. We should then be able to add implications to the trait solver.

So I guess the status is that we're slowly getting there but it is very hard, especially as we have to be incredibly careful to not break backwards compatibility.”

https://blog.rust-lang.org/inside-rust/2023/07/17/trait-syst...

“The new trait solver implementation should also unblock many future changes, most notably around implied bounds and coinduction. For example, it will allow us to remove many of the current restrictions on GATs and to fix many long-standing unsound issues, like #25860. Some unsound issues will already be fixed at the point of stabilization while others will require additional work afterwards.”

anderskaseorgon Cve-rs: Fast memory vulnerabilities, written in safe Rust

In the language,

    fn foo<'a, 'b, T>(_: &'a &'b (), v: &'b T) -> &'a T { v }

should be equivalent to

    fn foo<'a, 'b, T>(_: &'a &'b (), v: &'b T) -> &'a T where 'b: 'a { v }

because the type &'a &'b is only well-formed if 'b: 'a. However, in the implementation, only the first form where the constraint is left implicit is subject to the bug: the implicit constraint is incorrectly lost when 'static is substituted for 'b. This is clearly an implementation bug, not a language bug (insofar as there is a distinction at all—ideally there would be a written formal specification that we could point to, but I don’t think there’s any disagreement in principle about what it should say about this issue).