001: /*
002: * @(#)IdempotentSequence.java 0.3-2 18/06/1999
003: *
004: * This file is part of the HTTPClient package
005: * Copyright (C) 1996-1999 Ronald Tschalär
006: *
007: * This library is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU Lesser General Public
009: * License as published by the Free Software Foundation; either
010: * version 2 of the License, or (at your option) any later version.
011: *
012: * This library is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * Lesser General Public License for more details.
016: *
017: * You should have received a copy of the GNU Lesser General Public
018: * License along with this library; if not, write to the Free
019: * Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,
020: * MA 02111-1307, USA
021: *
022: * For questions, suggestions, bug-reports, enhancement-requests etc.
023: * I may be contacted at:
024: *
025: * ronald@innovation.ch
026: *
027: */
028:
029: package HTTPClient;
030:
031: import java.util.Hashtable;
032: import java.util.Enumeration;
033:
034: /**
035: * <P>This class checks whether a sequence of requests is idempotent. This
036: * is used to determine which requests may be automatically retried. This
037: * class also serves as a central place to record which methods have side
038: * effects and which methods are idempotent.
039: *
040: * <P>Note: unknown methods (i.e. a method which is not HEAD, GET, POST,
041: * PUT, DELETE, OPTIONS or TRACE) are treated conservatively, meaning
042: * they are assumed to have side effects and are not idempotent.
043: *
044: * <P>Usage:
045: * <PRE>
046: * IdempotentSequence seq = new IdempotentSequence();
047: * seq.add(r1);
048: * ...
049: * if (seq.isIdempotent(r1)) ...
050: * ...
051: * </PRE>
052: *
053: * @version 0.3-2 18/06/1999
054: * @author Ronald Tschalär
055: */
056:
057: class IdempotentSequence {
058: /** method number definitions */
059: private static final int UNKNOWN = 0, HEAD = 1, GET = 2, POST = 3,
060: PUT = 4, DELETE = 5, OPTIONS = 6, TRACE = 7;
061:
062: /** these are the history of previous requests */
063: private int[] m_history;
064: private String[] r_history;
065: private int m_len, r_len;
066:
067: /** trigger analysis of threads */
068: private boolean analysis_done = false;
069: private Hashtable threads = new Hashtable();
070:
071: // Constructors
072:
073: /**
074: * Start a new sequence of requests.
075: */
076: public IdempotentSequence() {
077: m_history = new int[10];
078: r_history = new String[10];
079: m_len = 0;
080: r_len = 0;
081: }
082:
083: // Methods
084:
085: /**
086: * Add the request to the end of the list of requests. This is used
087: * to build the complete sequence of requests before determining
088: * whether the sequence is idempotent.
089: *
090: * @param req the next request
091: */
092: public void add(Request req) {
093: if (m_len >= m_history.length)
094: m_history = Util.resizeArray(m_history,
095: m_history.length + 10);
096: m_history[m_len++] = methodNum(req.getMethod());
097:
098: if (r_len >= r_history.length)
099: r_history = Util.resizeArray(r_history,
100: r_history.length + 10);
101: r_history[r_len++] = req.getRequestURI();
102: }
103:
104: /**
105: * Is this request part of an idempotent sequence? This method <em>must
106: * not</em> be called before all requests have been added to this
107: * sequence; similarly, <var>add()</var> <em>must not</em> be called
108: * after this method was invoked.
109: *
110: * <P>We split up the sequence of requests into individual sub-sequences,
111: * or threads, with all requests in a thread having the same request-URI
112: * and no two threads having the same request-URI. Each thread is then
113: * marked as idempotent or not according to the following rules:
114: *
115: * <OL>
116: * <LI>If any method is UNKNOWN then the thread is not idempotent;
117: * <LI>else, if no method has side effects then the thread is idempotent;
118: * <LI>else, if the first method has side effects and is complete then
119: * the thread is idempotent;
120: * <LI>else, if the first method has side effects, is not complete,
121: * and no other method has side effects then the thread is idempotent;
122: * <LI>else the thread is not idempotent.
123: * </OL>
124: *
125: * <P>The major assumption here is that the side effects of any method
126: * only apply to resource specified. E.g. a <tt>"PUT /barbara.html"</tt>
127: * will only affect the resource "/barbara.html" and nothing else.
128: * This assumption is violated by POST of course; however, POSTs are
129: * not pipelined and will therefore never show up here.
130: *
131: * @param req the request
132: */
133: public boolean isIdempotent(Request req) {
134: if (!analysis_done)
135: do_analysis();
136:
137: return ((Boolean) threads.get(req.getRequestURI()))
138: .booleanValue();
139: }
140:
141: private static final Object INDET = new Object();
142:
143: private void do_analysis() {
144: for (int idx = 0; idx < r_len; idx++) {
145: Object t_state = threads.get(r_history[idx]);
146:
147: if (m_history[idx] == UNKNOWN)
148: threads.put(r_history[idx], Boolean.FALSE);
149: else if (t_state == null) // new thread
150: {
151: if (methodHasSideEffects(m_history[idx])
152: && methodIsComplete(m_history[idx])) // is idempotent
153: threads.put(r_history[idx], Boolean.TRUE);
154: else
155: // indeterminate
156: threads.put(r_history[idx], INDET);
157: } else // update thread
158: {
159: if (t_state == INDET
160: && methodHasSideEffects(m_history[idx]))
161: threads.put(r_history[idx], Boolean.FALSE);
162: }
163: }
164:
165: // any thread still indeterminate must be idempotent
166: Enumeration te = threads.keys();
167: while (te.hasMoreElements()) {
168: String res = (String) te.nextElement();
169: if (threads.get(res) == INDET)
170: threads.put(res, Boolean.TRUE);
171: }
172: }
173:
174: /**
175: * A method is idempotent if the side effects of N identical
176: * requests is the same as for a single request (Section 9.1.2
177: * of RFC-????).
178: *
179: * @return true if method is idempotent
180: */
181: public static boolean methodIsIdempotent(String method) {
182: return methodIsIdempotent(methodNum(method));
183: }
184:
185: private static boolean methodIsIdempotent(int method) {
186: switch (method) {
187: case HEAD:
188: case GET:
189: case PUT:
190: case DELETE:
191: case OPTIONS:
192: case TRACE:
193: return true;
194: default:
195: return false;
196: }
197: }
198:
199: /**
200: * A method is complete if any side effects of the request affect
201: * the complete resource. For example, a PUT is complete but a
202: * PUT with byte-ranges wouldn't be. In essence, if a request uses
203: * a method which has side effects and is complete then the state
204: * of the resource after the request is independent of the state of
205: * the resource before the request.
206: *
207: * @return true if method is complete
208: */
209: public static boolean methodIsComplete(String method) {
210: return methodIsComplete(methodNum(method));
211: }
212:
213: private static boolean methodIsComplete(int method) {
214: switch (method) {
215: case HEAD:
216: case GET:
217: case PUT:
218: case DELETE:
219: case OPTIONS:
220: case TRACE:
221: return true;
222: default:
223: return false;
224: }
225: }
226:
227: public static boolean methodHasSideEffects(String method) {
228: return methodHasSideEffects(methodNum(method));
229: }
230:
231: private static boolean methodHasSideEffects(int method) {
232: switch (method) {
233: case HEAD:
234: case GET:
235: case OPTIONS:
236: case TRACE:
237: return false;
238: default:
239: return true;
240: }
241: }
242:
243: private static int methodNum(String method) {
244: if (method.equals("GET"))
245: return GET;
246: if (method.equals("POST"))
247: return POST;
248: if (method.equals("HEAD"))
249: return HEAD;
250: if (method.equals("PUT"))
251: return PUT;
252: if (method.equals("DELETE"))
253: return DELETE;
254: if (method.equals("OPTIONS"))
255: return OPTIONS;
256: if (method.equals("TRACE"))
257: return TRACE;
258:
259: return UNKNOWN;
260: }
261:
262: /**
263: * Test code.
264: */
265: public static void main(String args[]) {
266: IdempotentSequence seq = new IdempotentSequence();
267:
268: seq
269: .add(new Request(null, "GET", "/b1", null, null, null,
270: false));
271: seq
272: .add(new Request(null, "PUT", "/b2", null, null, null,
273: false));
274: seq
275: .add(new Request(null, "GET", "/b1", null, null, null,
276: false));
277: seq
278: .add(new Request(null, "PUT", "/b3", null, null, null,
279: false));
280: seq
281: .add(new Request(null, "GET", "/b2", null, null, null,
282: false));
283: seq
284: .add(new Request(null, "PUT", "/b3", null, null, null,
285: false));
286: seq
287: .add(new Request(null, "GET", "/b1", null, null, null,
288: false));
289: seq.add(new Request(null, "TRACE", "/b4", null, null, null,
290: false));
291: seq.add(new Request(null, "LINK", "/b4", null, null, null,
292: false));
293: seq
294: .add(new Request(null, "GET", "/b4", null, null, null,
295: false));
296: seq
297: .add(new Request(null, "PUT", "/b5", null, null, null,
298: false));
299: seq.add(new Request(null, "HEAD", "/b5", null, null, null,
300: false));
301: seq
302: .add(new Request(null, "PUT", "/b5", null, null, null,
303: false));
304: seq
305: .add(new Request(null, "GET", "/b6", null, null, null,
306: false));
307: seq.add(new Request(null, "DELETE", "/b6", null, null, null,
308: false));
309: seq.add(new Request(null, "HEAD", "/b6", null, null, null,
310: false));
311: seq.add(new Request(null, "OPTIONS", "/b7", null, null, null,
312: false));
313: seq.add(new Request(null, "TRACE", "/b7", null, null, null,
314: false));
315: seq
316: .add(new Request(null, "GET", "/b7", null, null, null,
317: false));
318: seq
319: .add(new Request(null, "PUT", "/b7", null, null, null,
320: false));
321:
322: if (!seq.isIdempotent(new Request(null, null, "/b1", null,
323: null, null, false)))
324: System.err.println("Sequence b1 failed");
325: if (!seq.isIdempotent(new Request(null, null, "/b2", null,
326: null, null, false)))
327: System.err.println("Sequence b2 failed");
328: if (!seq.isIdempotent(new Request(null, null, "/b3", null,
329: null, null, false)))
330: System.err.println("Sequence b3 failed");
331: if (seq.isIdempotent(new Request(null, null, "/b4", null, null,
332: null, false)))
333: System.err.println("Sequence b4 failed");
334: if (!seq.isIdempotent(new Request(null, null, "/b5", null,
335: null, null, false)))
336: System.err.println("Sequence b5 failed");
337: if (seq.isIdempotent(new Request(null, null, "/b6", null, null,
338: null, false)))
339: System.err.println("Sequence b6 failed");
340: if (seq.isIdempotent(new Request(null, null, "/b7", null, null,
341: null, false)))
342: System.err.println("Sequence b7 failed");
343:
344: System.out.println("Tests finished");
345: }
346: }
|