Architecture for overriding "trait" implementations many times in different contexts?

Scala uses the given system for a superset of what Rust traits do. For example, this Rust (pseudo-)code

trait Show {
  fn show(&self) -> String;
}

impl Show for String {
  fn show(&self) -> String {
    format!("\"{}\"", self)
  }
}

fn show(x: &impl Show) {
  x.show()
}

converts to this Scala code:

trait Show[+A]:
  def show(a: A): String

given Show[String] where
  def show(str: String) = s"\"$str\""

def show[A](a: A)(using sh: Show[A]) = sh(a)

The important difference is that givens act as variables - that is, they can be scoped.

def foo() =
  given Show[String] where
    def show(str: String) = s"[${str.length}]$str"
  println(show("hi"))

println(show("hi")) // outputs "hi"
foo() // outputs [2]hi

Multiple libraries can export givens of the same type and you can choose which to use when you import them:

import lib.{given Show[String]}
println(show("hi")) // calls the library's implementation

And of course, you can mix the two things and use imports inside a block to override the default given

import bar.{given Show[String]}
def q() =
  import foo.{given Show[String]}
  println(show("hi"))
println(show("hi"))
q()

You can also decide to explicitly pass an instance to a function without having it as a given:

object A extends Show[String]:
  def show(str: String) = s"$str from A"
object B extends Show[String]:
  def show(str: String) = s"$str from B"
given Show[String] = A
println(show("hi")) // hi from A
println(show("hi")(using B)) // hi from B

All these features combined can make Scala givens much more powerful than Rust-style traits or traditional Haskell-like typeclasses, if used correctly.

Your traits calls library code

By multiple times, I mean a library might define some errors and renderings for them. Then another library might override that. Then an application might override that, so 3 layers of definitions, the last one which will take precedence (and all internal/external error messages will use that final formatter).

In existing languages, this level of configuration is possible if the default implementation is published in a public vtable, and default trait implementations calls into these vtables, that in turn are initially filled with the default implementation. Any library or user code can, then, change that. It's only a form of dependency pointer injection, as noted.

impl in Rust, is more in direction of dependency code injection, in comptime no less. After the code is compiled, there is only functionality, no extension points.

Aspect-oriented programming

So if you want both, your language will need some form of virtual trait that accepts a default implementation, so that any library or user code can modify latter. If these 3 layers of (re)definitions are to occur at comptime, then your language will need some syntax to declare some aspect syntax rewriting rules.

You will note, in above Wikipedia link, that logging is a prime case in aspect-oriented programming.

It appears Rust doesn't allow you to override trait implementations (for some reason I'm unaware of, waiting to hear about that!).

This is because of "coherency": given a list of types (or a single type if the language doesn't support multi-parameter typeclasses) and a typeclass (or trait as Rust calls them), there should be only one implementation of the typeclass. This is considered a useful property: for example, if you have a Hash trait that allows hashing a type, you won't get different hashes in different parts of the program for the same value.

If you guarantee coherence by restricting where can a typeclass be implemented and on which types, that also allows fancier (non-deterministic) type checking algorithms as regardless of how you derive a typeclass implementation for a list of types, you'll get the right (only) one.

What about other languages, what is a good example how another language solves this problem?

Implicits also solve this problem. Example in Koka:

import std/data/rb-set

fun main()
  val set1: rbset<int> = empty().add(123).add(456)
  val set2: rbset<int> = empty().add(789).add(901)
  val list = [set1, set2]

  // Print using the defaults.
  println(list.show)

  // Print with custom element printer.
  println(list.show(?show = fn(set: rbset<int>) {
    set.show(?k/show = int/show-hex)
  }))

fun int/show-hex(i: int): string
  "0x123" // doesn't matter

In this example I have a list of maps of integers. In the first println I don't specify the show function, so the lists, maps, and integers are printed using the show functions defined in the standard library. In the second println, I override how integers are printed.

Scala's given system shown in the other answer seems like a more convenient way to do the same. I suspect under the hood it should also be some form of implicit parameter passing.

Orphan Rule

It appears Rust doesn't allow you to override trait implementations (for some reason I'm unaware of, waiting to hear about that!

In short, because it's opening a can of worms.

Let's imagine it were possible, and work through the issues as they present themselves.

Firstly, which trait implementation should be used, then? Keeping to your idea of better error messages, what if my application has two dependencies A and B each of which overrides the error message: which one should be used A's or B's?

There's not really any good way to decide. You could have arbitrary rules -- such as the closest to the top-level, the last dependency, etc... -- but in the end users will keep running into surprises. And violating the Principle of Least Surprise generally means angry users.

Secondly, even if users are happy enough with the selection rules, this is still brittle. Imagine, library B has been improved, and now it only depends on library C if it needs its functionality -- which you can request with a flag. Great, your application is lighter! Bonus point, you're no longer exposed to vulnerabilities in C or its upstream dependencies.

Oh, on the downside, if your application was relying on C's override of some functionality, it's now broken. No big deal, eh?

Thirdly... it only really works with Late Binding. Remember that in Rust, traits are used both for compile-time polymorphism and run-time polymorphism. Injecting trait implementations from downstream libraries back into their upstream dependencies when compiling them -- ie, before compiling said downstream dependencies -- is not going to be a picnic.

The conservative thing, then, is to simply implement the orphan rule, which Rust did. SO much simpler.

Virtual Table & Virtual Pointer

In most mainstream OO languages -- C++, C#, Java, Python -- a polymorphic value embeds type information, often in the form of a virtual pointer, which itself points to a static virtual table.

Overriding the methods of the object is thus simple: they are executed by looking them up in the virtual table via the virtual pointer, thus swapping out the pointer for one which points to a different virtual table will let you control which implementation of each method is called.

In a statically typed language, the creator of the object will decide the object's exact type, which in turn decides which virtual pointer is "installed" in the object.

In dynamically typed languages, such as JavaScript, Python, or Ruby, it's generally possible to monkey-patch an object, by overriding the methods registered in the v-table. In this case, all objects using this v-table, whether created by the overridder, or not, will start using the newly overridden implementation from then on.

Do note that the distinction between static & dynamic here is fairly arbitrary. In theory, a statically typed language could very well allow monkey-patching. It could even do so in a typed manner: enforcing that the method which overrides accepts the same receiver.

There are downsides, of course:

1. Even if you authored some code, you're never sure whether your method implementation was called, or some random method written by a random stranger, and nobody else is, in fact. This makes reasoning about code MUCH harder.
2. If multiple libraries keep overriding a given method, it's going to be a hot mess.
3. You're basically relying on all the developers of your codebase and all its upstream dependencies to "be nice citizens": they need to document the invariants of each overridable method in detail, and never to modify them on patch/minor updates, and those who override those methods need to very carefully make sure they abide by those invariants. In practice? It'll break, hopefully not often, but when it ineluctably does, it'll be a big pain to diagnose.