001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.juneau.commons.utils;
018
019import static org.apache.juneau.commons.utils.Shorts.*;
020
021import java.lang.reflect.*;
022import java.util.*;
023import java.util.concurrent.*;
024
025/**
026 * Bounded, iterative walker that validates already-materialized JSON values against structural safety limits.
027 *
028 * <p>
029 * This helper defends against pathological inputs (excessive nesting, unbounded node counts, cyclic references, and
030 * runaway traversal times) before a value is serialized or otherwise consumed.  It walks only in-memory maps,
031 * collections, arrays, and scalar leaves; it never resolves <js>"$ref"</js> or performs any I/O.
032 *
033 * <p>
034 * All violations are reported as neutral {@link IllegalArgumentException}s.  Typed or adaptor callers are responsible
035 * for mapping these to the appropriate JSON-RPC error code, which keeps this core class free of any revision-specific
036 * error policy.
037 */
038public final class JsonValueSafety {
039
040   /** Maximum allowed nesting depth of the walked value. */
041   public static final int MAX_DEPTH = 64;
042
043   /** Maximum allowed number of distinct nodes (containers and leaves) in the walked value. */
044   public static final int MAX_NODES = 10_000;
045
046   /** Maximum allowed wall-clock time, in milliseconds, for a single traversal. */
047   public static final long MAX_TRAVERSAL_MILLIS = 100;
048
049   /**
050    * Deadline value meaning "no wall-clock limit": the depth, {@link #MAX_NODES node-count} and cycle bounds still apply.
051    *
052    * <p>
053    * Use this for server-authored or already size-bounded values, where a slow walk (a loaded host, a GC pause)
054    * must not be reported as a violation.
055    */
056   public static final long NO_DEADLINE = Long.MAX_VALUE;
057
058   private JsonValueSafety() {}
059
060   /**
061    * Computes a fresh traversal deadline from the current time.
062    *
063    * @return An absolute deadline in {@link System#nanoTime()} units, {@link #MAX_TRAVERSAL_MILLIS} milliseconds in the future.
064    */
065   public static long deadlineNanos() {
066      return System.nanoTime() + TimeUnit.MILLISECONDS.toNanos(MAX_TRAVERSAL_MILLIS);
067   }
068
069   /**
070    * Validates the specified value against the structural safety limits using a fresh {@link #deadlineNanos() deadline}.
071    *
072    * @param value The value to walk.  Can be <jk>null</jk>, in which case this method returns immediately.
073    * @param label A human-readable label describing the value; used as a prefix in violation messages.
074    * @throws IllegalArgumentException If the value violates any of the depth, node-count, traversal-time, or JSON-shape constraints.
075    */
076   public static void check(Object value, String label) {
077      check(value, label, deadlineNanos());
078   }
079
080   /**
081    * Validates the specified value against the structural safety limits using the specified traversal deadline.
082    *
083    * @param root The value to walk.  Can be <jk>null</jk>, in which case this method returns immediately.
084    * @param label A human-readable label describing the value; used as a prefix in violation messages.
085    * @param deadlineNanos An absolute deadline in {@link System#nanoTime()} units after which the traversal is aborted.
086    * @throws IllegalArgumentException
087    *    If the value exceeds {@link #MAX_DEPTH}, exceeds {@link #MAX_NODES}, exceeds the traversal deadline, contains a
088    *    non-string JSON object key, or contains a leaf that is not a JSON value type ({@link String}, {@link Number}, or
089    *    {@link Boolean}).
090    */
091   public static void check(Object root, String label, long deadlineNanos) {
092      if (root == null)
093         return;
094      var seen = Collections.newSetFromMap(new IdentityHashMap<Object,Boolean>());
095      var stack = new ArrayDeque<Framed>();
096      stack.push(new Framed(root, 1));
097      var nodes = 0;
098      while (! stack.isEmpty()) {
099         // Bounded per-iteration work runs before the deadline check so a structurally-oversized input
100         // deterministically reports its depth/node-count violation instead of racing the wall clock.
101         var frame = stack.pop();
102         if (frame.depth() > MAX_DEPTH)
103            throw iaex("%s exceeds maximum nesting depth of %s", label, MAX_DEPTH);
104         nodes = visitFrame(frame, label, seen, stack, nodes);
105         if (System.nanoTime() >= deadlineNanos)
106            throw iaex("%s traversal exceeded %s ms", label, MAX_TRAVERSAL_MILLIS);
107      }
108   }
109
110   /**
111    * Processes one popped stack frame: counts it toward the node budget, and - if it's an unseen container -
112    * pushes its children onto {@code stack} for further traversal.
113    *
114    * @return The updated node count.
115    */
116   private static int visitFrame(Framed frame, String label, Set<Object> seen, ArrayDeque<Framed> stack, int nodes) {
117      var value = frame.value();
118      if (value == null)
119         return checkNodeBudget(nodes, label);
120      var container = value instanceof Map<?,?> || value instanceof Collection<?> || value.getClass().isArray();
121      if (container && ! seen.add(value))
122         return nodes;
123      nodes = checkNodeBudget(nodes, label);
124      pushChildren(value, frame.depth(), label, stack);
125      return nodes;
126   }
127
128   private static int checkNodeBudget(int nodes, String label) {
129      if (++nodes > MAX_NODES)
130         throw iaex("%s exceeds maximum node count of %s", label, MAX_NODES);
131      return nodes;
132   }
133
134   private static void pushChildren(Object value, int depth, String label, ArrayDeque<Framed> stack) {
135      if (value instanceof Map<?,?> value2) {
136         for (var entry : value2.entrySet()) {
137            if (! (entry.getKey() instanceof String))
138               throw iaex("%s contains non-string JSON object key %s", label, entry.getKey());
139            stack.push(new Framed(entry.getValue(), depth + 1));
140         }
141      } else if (value instanceof Collection<?> value2) {
142         for (var child : value2)
143            stack.push(new Framed(child, depth + 1));
144      } else if (value.getClass().isArray()) {
145         for (var i = 0; i < Array.getLength(value); i++)
146            stack.push(new Framed(Array.get(value, i), depth + 1));
147      } else if (! (value instanceof String || value instanceof Number || value instanceof Boolean))
148         throw iaex("%s contains non-JSON value type %s", label, value.getClass().getName());
149   }
150
151   /**
152    * Computes the number of nanoseconds remaining before the specified deadline.
153    *
154    * @param deadlineNanos An absolute deadline in {@link System#nanoTime()} units.
155    * @return The remaining nanoseconds, or <c>0</c> if the deadline has already passed.
156    */
157   public static long remainingNanos(long deadlineNanos) {
158      return Math.max(0, deadlineNanos - System.nanoTime());
159   }
160
161   private record Framed(Object value, int depth) {}
162}