identical() for strings is not transitive

[Hixie]

void main() {
  String ab = 'ab';
  print(identical('a' + 'b', 'ab')); // true, compile-time constant evaluation                                                                                                 
  print(identical('ab',       ab)); // true, compile-time constant de-duplication                                                                                              
  print(identical('a' + 'b',  ab)); // false??                                                                                                                                 
}

[lrhn]

I assume this is the VM.

The rules for canonicalization of strings are not trivial.
Basically, string expressions, even compile-time constant ones, are not required to be canonicalized.
However, if both argument expressions of an identical call are compile-time constants, the result is computed at compile-time based on the string contents, not the object identity.

The expression ab is not a compile-time constant expression.
The string literal 'ab' is canonicalized by the VM (it's allowed, but not required, to do that, but if it didn't, things would break everywhere, so we should probably fix that requirement into the spec).
The compile-time constant string expression 'a' + 'b' evaluates to a different string object with the same content.

So, the first test is true because the test is compile-time constant.
The second test is true because the ab variable refers to the same string object as the expression 'ab'.
The third test is false because ab variable refers to a different string object than the compile-time constant 'a' + 'b' evaluated to.

Or, to put it differently: It's not a problem with transitivity - it's the fact that "a"+"b" (which is a compile-time constant) isn't canonicalized unless it's used in a compile-time constant context.
You can get the same result from just:

var x = "a" + "b";
print(identical("a" + "b", x));  // false

Even if "a" + "b" is a compile-time constant expression, it's just not canonicalized, and nothing in the spec says that it has to be.

So, the behavior is allowed by the specification.
I'm marking this as a VM bug for now, so they can consider whether they want to change behavior or not.

I'll check if we have a bug open for changing the language to require canonicalization of compile-time constant string expressions. Otherwise we might want that.

Considering the closing message on #1918, it's probably an oversight that the specification doesn't actually require canonicalization.

[lrhn]

There actually does seem to be a bug in the VM:

var r = [];
for (var i = 0; i < r; i++) r.add("a" + "b");
print(identical(r[0], r[1]));

This prints false, and it must print true. The expression "a" + "b" is a compile-time constant expression and the spec says:

A constant expression is an expression whose value can never change, and that can be evaluated entirely at compile time.

This example shows the value of the constant expression "a" + "b" changing.

Arguably, the spec saying:

The predefined Dart function identical() is defined such that identical(c1, c2) iff:
...
• c1 and c2 are constant strings and c1 == c2, OR

does require that the identical function cannot distinguish constant strings (the problem is that "constant string" isn't a formally defined term - being constant is a property of syntax and evaluation time, not of the resulting value).

[eernstg]

I think this confirms that the vm ought to consistently detect constant expressions of type String and generate code to return the canonicalized result for every such expression every time, in stead of, say, returning a fresh string each time for "a" + "b" in that for loop. It does require a bottom-up propagated bit in the abstract syntax: for instance, myRuntimeString + "a" + "b" associates to the left, so there's no canonical string "ab" inside that expression, only the two canonical strings "a" and "b". The spec needs a clarification to state unambiguously that all constant expressions of type String must yield a canonicalized result, but I don't think it is reasonable to interpret it differently even with the current wording.

About the invocations of identical: Assuming the strict approach I just described, all three of them should return true. The first one is a constant expression; the second one is a dynamic invocation of identical with two arguments which are both a reference to the canonical string 'ab', and so is the third.

[mhausner]

See also issue #25024.

Back when Dart was still Dash, I remember discussions that the language shall not require all expressions that can be compile-time constants to be canonicalized, due to the runt-time cost. You don't want to spend the time to canonicalize every "a"+"b" (xyz+"b", "a"+X.c, ...) for the rare case where it's needed.

[lrhn]

If we don't canonicalize all compile-time constant string expressions, then we need to make it predictable for users when they are canonicalized and when they are not. Is the VM following a rule or is it more ad-hoc which compile-time string expressions are canonicalized and which are not?
I'm guessing that string literals are always canonicalized, and likely also string interpolations and juxtapositions. I guess that only leaves string + operations.

I wouldn't mind if string constant expression + string constant expression was also always canonicalized. It would at least be a simple rule to explain. On the other hand, I expect the Kernel to do that for you, so it might not be worth it to change the VM just now.

[mhausner]

I suspect this will be obsolete with the new front-end, but it needs to be verified.

[liamappelbe]

I tried to verify that this was fixed, and write a regression test. It seems that the behavior has changed since this bug was opened, but 'a' + 'b' is not being canonicalized:

void main() {
  String ab = 'ab';
  print(identical('a' + 'b', 'ab'));  // false
  print(identical('ab',       ab));   // true
  print(identical('a' + 'b',  ab));   // false

  var x = "a" + "b";
  print(identical("a" + "b", x));     // false

  var r = [];
  for (var i = 0; i < 10; i++) r.add("a" + "b");
  print(identical(r[0], r[1]));       // false
}

Note that the first print has switched from true to false. Is this the intended behavior now?

[eernstg]

We don't specify that every constant expression must be evaluated at compile time, only that an expression must satisfy a very strict set of rules in order to be a constant expression, and a compiler is then allowed to evaluate it at compile time. So it's OK for Dart compilers to postpone the evaluation of 'a' + 'b' to run time.

With specific expressions we have a more strict rule: A <constObjectExpression> must be canonicalized (which is currently only possible when it is also evaluated at compile-time). That's a constant expression whose top-level construct invokes a constant constructor, e.g., const C('a' + 'b'). In that case, and with the following declaration of C, the instance of C must be the same as the instance yielded by evaluating const C('ab'), because canonicalization only relies on the type of object (C) and the values of its instance variables:

class C {
  final String s;
  const C(this.s);
}

void main() => print(identical(const C('a' + 'b'), const C('ab'))); // 'true'.

I'll close this issue because the transitivity discrepancy has been resolved, and because the more general issue about canonicalization of strings is handled in dart-lang/language#985.