[Sync] Generalize StringOrdinal to handle ordinal_in_parent field

sync/protocol/sync.proto

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 //
 // Sync protocol for communication between sync client and server.
 
 // Update proto_value_conversions{.h,.cc,_unittest.cc} if you change
 // any fields in this file.
 
 syntax = "proto2";
@@ skipping 290 matching lines @@
   // If present in Commit updates for the entity, it will be ignored.
   //
   // Available in version 24+.
   //
   // May be returned in GetUpdatesMessage and sent up in CommitMessage.
   //
   optional string client_defined_unique_tag = 23;
 
   // Supplies an ordinal for this item, relative to other items with the
   // same parent.  Ordinals are ordered lexicographically bytewise.
-  // Ordinals must be a least 8 bytes (for backwards compatibility), and
+  // Ordinals must be at least 8 bytes (for backwards compatibility), and
   // must not be all zeroes.
   //
   // Clients should not make sure that each item they know of has a
   // unique ordinal-in-parent.  However, updates from the server might
   // break this invariant.  In that case, among the items with the
   // same ordinal-in-parent, a client should randomly pick one, and

[rlarocque, 2012/09/05 21:43:46]

"randomly pick one" will limit our ability to test this code.  I'd prefer if the
ordering were based on some known value.  The ID, for example, which is more or
less guaranteed to be unique, would be a good choice.  

[akalin, 2012/09/06 19:25:14]

A secondary goal was to minimize the number of conflicting nodes whenever two
end up with the same ordinal.  The most common case I'm guessing will be when
two clients both create the initial node at the same time, say, N1 and N2, with
N1's ID < N2's ID.  If both clients make a consistent choice regarding which
ordinal to leave alone, say, N1, then they will both end up perturbing N2's
ordinal, likely resulting in a conflict, which is theoretically harmless, but
you know how a lot of our bugs come from conflicts.

With a random choice of which ordinal to perturb, there's a 50% chance that each
client will perturb a different ordinal, resulting in no conflicts.

Of course, this breaks down for more than 2 nodes, but those should be rare
anyway.

[rlarocque, 2012/09/06 21:25:55]

I'm not convinced, but this is the wrong place for this discussion.  I shouldn't
have brought it up here.

Let's defer this discussion until later.

   // then perturb the ordinal-in-parents of all the other ones (within
   // the bounds of the preceding and succeeding ordinal-in-parent)
   // until they're unique; a byte of randomness per item should be
   // more than enough.
   //
   // Available in version 31+.
   //
   // Present in both GetUpdatesResponse and CommitMessage.
   //
   // In a CommitMessage context, server implementations may choose whether
@@ skipping 345 matching lines @@
     optional string url                     = 3;
     optional SyncEnums.Action action        = 4 [default = UNKNOWN_ACTION];
 
     // Currently only meaningful if |error_type| is throttled. If this field
     // is absent then the whole client (all datatypes) is throttled.
     repeated int32 error_data_type_ids = 5;
   }
   optional Error error = 13;
 };