Support user-ordered YANG lists (synthetic order field + authoritative alternative)

[steiler]

Yang defined two types of ordering for lists and leaf-lists, that is system ordered and user ordered.

7.7.5.1. ordered-by system

The entries in the list are sorted according to an unspecified order.
Thus, an implementation is free to sort the entries in the most
appropriate order. An implementation SHOULD use the same order for
the same data, regardless of how the data were created. Using a
deterministic order will make comparisons possible using simple tools
like "diff".

This is the default order.

7.7.5.2. ordered-by user

The entries in the list are sorted according to an order defined by
the user. This order is controlled by using special XML attributes
in the request. See Section 7.7.7 for details.

So leaf-lists is not an issue, since we opted to take in leaf-lists as a single value and do not perform any merging of leaf-lists from different intents.
Taking a look at lists, the situation presents itself rather differently.
system ordering is not an issue and we do sort list elements by key by default. However we do not have the capability for "user ordered" so far.

So lets discuss, how can we provide user defined ordering of lists.

Synthetic ordering - proposal

• Expose a user-facing intent field: __sdc_order__ on list entries (never sent to devices).
• Merge semantics: __sdc_order__ follows existing attribute merge rules (highest intent priority wins; if equal, newest creation timestamp wins). The effective __sdc_order__ is the merged value.
• Final list order: sort entries by tuple:
  1. numeric __sdc_order__ ascending
  2. winning intent priority descending
  3. winning intent creation_time descending (newer wins)
  4. element key ascending
• Elements without explicit __sdc_order__ get implicit __sdc_order__ assigned during reconciliation:
  • On device ingest, assign spaced values preserving device sequence (e.g., 1000, 2000, ...).
  • New entries appended get next gap value (or midpoint insertion).
• Insert algorithm & rebalancing:
  • Insert using numeric midpoints; if gap exhausted, run a deterministic rebalancing pass that renumbers entries to spaced multiples (configurable step, e.g., 1000).
  • Record/emit a log/audit entry when rebalancing occurs.

Scenarios

• Multiple intents, no ordering

  • Example input: device has [A,B,C]; intents I1 and I2 add D and E without __sdc_order__.
  • Reconciliation: preserve device sequence for A,B,C; assign implicit __sdc_order__ values to D and E (appended in deterministic order, e.g. by intent priority/timestamp).
  • Checks: final list should be A,B,C,D,E; implicit order values spaced; provenance shows which intent created D/E.

• Mixed explicit orders

  • Example input: device [A,B,C]; I1 sets A.__sdc_order__=2500, I2 sets A.__sdc_order__=2200 (higher priority), I3 adds D with __sdc_order__=1500.
  • Reconciliation: merge __sdc_order__ per-attribute rules (priority → timestamp) producing effective orders D=1500, A=2200, B=2000, C=3000; sort numerically.
  • Checks: final order D,B,A,C; merged winner for A recorded; equal-order tie-breaker applied if needed.

• Brownfield + device out-of-band inserts

  • Example input: initial ingest assigns A=1000,B=2000,C=3000. Device later reorders and inserts X between B and C (out-of-band).
  • Reconciliation: map X to midpoint order (e.g. 2500) on detection; if no midpoint available, perform deterministic rebalancing to restore gaps.
  • Checks: device-originated changes preserved in sequence; reconciliation logs out-of-band insert handling and any rebalances.

• Collisions (identical numeric orders)

  • Example input: I1 and I2 (different intents) both cause elements D and E to have effective __sdc_order__=1500.
  • Reconciliation: apply deterministic tie-breaker: numeric order → intent priority → intent creation_time → element key. Auto-resolve ordering and emit a warning/audit entry pointing to conflicting intents.
  • Checks: ordering is deterministic; audit shows which intents conflicted and which value won; optionally surface a validation warning to authors.

• Authoritative ordering (alternative)

  • Example input: an intent marked orderOwnership=authoritative supplies full list ordering [Z,Y,X]; other intents provide elements but no ordering authority.
  • Reconciliation: authoritative ordering supersedes composed ordering; other intents still merge element attributes but their __sdc_order__ is ignored for ordering while authority is in effect.
  • Checks: final order exactly matches authoritative intent; policy for claiming/releasing authority is enforced and auditable.

Alternative: Full-authoritative ordering

• Introduce an orderOwnership: authoritative flag (intent-level) or a dedicated authoritative-order intent type.
• If an authoritative intent exists for a list, its explicit ordering replaces any composed ordering from other intents and device state.
• Pros: simple deterministic semantics, easy testing. Cons: breaks composability, requires lifecycle rules for claiming/relinquishing authority and RBAC.

[steiler]

closes sdcio/data-server#394